Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / topology.c @ 6ff81197

History | View | Annotate | Download (53.4 KB)

1
/*
2
 *        BIRD -- OSPF Topological Database
3
 *
4
 *        (c) 1999       Martin Mares <mj@ucw.cz>
5
 *        (c) 1999--2004 Ondrej Filip <feela@network.cz>
6
 *        (c) 2009--2014 Ondrej Zajicek <santiago@crfreenet.org>
7
 *        (c) 2009--2014 CZ.NIC z.s.p.o.
8
 *
9
 *        Can be freely distributed and used under the terms of the GNU GPL.
10
 */
11

    
12
#include "nest/bird.h"
13
#include "lib/string.h"
14

    
15
#include "ospf.h"
16

    
17

    
18
#define HASH_DEF_ORDER 6
19
#define HASH_HI_MARK *4
20
#define HASH_HI_STEP 2
21
#define HASH_HI_MAX 16
22
#define HASH_LO_MARK /5
23
#define HASH_LO_STEP 2
24
#define HASH_LO_MIN 8
25

    
26
static inline void * lsab_flush(struct ospf_proto *p);
27
static inline void lsab_reset(struct ospf_proto *p);
28

    
29

    
30
/**
31
 * ospf_install_lsa - install new LSA into database
32
 * @p: OSPF protocol instance
33
 * @lsa: LSA header
34
 * @type: type of LSA
35
 * @domain: domain of LSA
36
 * @body: pointer to LSA body
37
 *
38
 * This function ensures installing new LSA received in LS update into LSA
39
 * database. Old instance is replaced. Several actions are taken to detect if
40
 * new routing table calculation is necessary. This is described in 13.2 of RFC
41
 * 2328. This function is for received LSA only, locally originated LSAs are
42
 * installed by ospf_originate_lsa().
43
 *
44
 * The LSA body in @body is expected to be mb_allocated by the caller and its
45
 * ownership is transferred to the LSA entry structure.
46
 */
47
struct top_hash_entry *
48
ospf_install_lsa(struct ospf_proto *p, struct ospf_lsa_header *lsa, u32 type, u32 domain, void *body)
49
{
50
  struct top_hash_entry *en;
51
  int change = 0;
52

    
53
  en = ospf_hash_get(p->gr, domain, lsa->id, lsa->rt, type);
54

    
55
  if (!SNODE_VALID(en))
56
    s_add_tail(&p->lsal, SNODE en);
57

    
58
  if ((en->lsa_body == NULL) ||                        /* No old LSA */
59
      (en->lsa.length != lsa->length) ||
60
      (en->lsa.type_raw != lsa->type_raw) ||        /* Check for OSPFv2 options */
61
      (en->lsa.age == LSA_MAXAGE) ||
62
      (lsa->age == LSA_MAXAGE) ||
63
      memcmp(en->lsa_body, body, lsa->length - sizeof(struct ospf_lsa_header)))
64
    change = 1;
65

    
66
  if ((en->lsa.age == LSA_MAXAGE) && (lsa->age == LSA_MAXAGE))
67
    change = 0;
68

    
69
  mb_free(en->lsa_body);
70
  en->lsa_body = body;
71
  en->lsa = *lsa;
72
  en->init_age = en->lsa.age;
73
  en->inst_time = current_time();
74

    
75
  /*
76
   * We do not set en->mode. It is either default LSA_M_BASIC, or in a special
77
   * case when en is local but flushed, there is postponed LSA, self-originated
78
   * LSA is received and ospf_install_lsa() is called from ospf_advance_lse(),
79
   * then we have en->mode from the postponed LSA origination.
80
   */
81

    
82
  OSPF_TRACE(D_EVENTS, "Installing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x, Age: %u",
83
             en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn, en->lsa.age);
84

    
85
  if (change)
86
    ospf_schedule_rtcalc(p);
87

    
88
  return en;
89
}
90

    
91
/**
92
 * ospf_advance_lsa - handle received unexpected self-originated LSA
93
 * @p: OSPF protocol instance
94
 * @en: current LSA entry or NULL
95
 * @lsa: new LSA header
96
 * @type: type of LSA
97
 * @domain: domain of LSA
98
 * @body: pointer to LSA body
99
 *
100
 * This function handles received unexpected self-originated LSA (@lsa, @body)
101
 * by either advancing sequence number of the local LSA instance (@en) and
102
 * propagating it, or installing the received LSA and immediately flushing it
103
 * (if there is no local LSA; i.e., @en is NULL or MaxAge).
104
 *
105
 * The LSA body in @body is expected to be mb_allocated by the caller and its
106
 * ownership is transferred to the LSA entry structure or it is freed.
107
 */
108
void
109
ospf_advance_lsa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_lsa_header *lsa, u32 type, u32 domain, void *body)
110
{
111
  /* RFC 2328 13.4 */
112

    
113
  if (en && (en->lsa.age < LSA_MAXAGE))
114
  {
115
    if (lsa->sn != LSA_MAXSEQNO)
116
    {
117
      /*
118
       * We simply advance current LSA to have higher seqnum than received LSA.
119
       * The received LSA is ignored and the advanced LSA is propagated instead.
120
       *
121
       * Although this is an origination of distinct LSA instance and therefore
122
       * should be limited by MinLSInterval, we do not enforce it here. Fast
123
       * reaction is needed and we are already limited by MinLSArrival.
124
       */
125

    
126
      mb_free(body);
127

    
128
      en->lsa.sn = lsa->sn + 1;
129
      en->lsa.age = 0;
130
      en->init_age = 0;
131
      en->inst_time = current_time();
132
      lsa_generate_checksum(&en->lsa, en->lsa_body);
133

    
134
      OSPF_TRACE(D_EVENTS, "Advancing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
135
                 en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
136
    }
137
    else
138
    {
139
      /*
140
       * Received LSA has maximal sequence number, so we cannot simply override
141
       * it. We have to install it to the database, immediately flush it to
142
       * implement sequence number wrapping, and schedule our current LSA to be
143
       * originated after the received instance is flushed.
144
       */
145

    
146
      if (en->next_lsa_body == NULL)
147
      {
148
        /* Schedule current LSA */
149
        en->next_lsa_blen = en->lsa.length - sizeof(struct ospf_lsa_header);
150
        en->next_lsa_body = en->lsa_body;
151
        en->next_lsa_opts = ospf_is_v2(p) ? lsa_get_options(&en->lsa) : 0;
152
      }
153
      else
154
      {
155
        /* There is already scheduled LSA, so we just free current one */
156
        mb_free(en->lsa_body);
157
      }
158

    
159
      en->lsa_body = body;
160
      en->lsa = *lsa;
161
      en->lsa.age = LSA_MAXAGE;
162
      en->init_age = lsa->age;
163
      en->inst_time = current_time();
164

    
165
      OSPF_TRACE(D_EVENTS, "Resetting LSA:  Type: %04x, Id: %R, Rt: %R, Seq: %08x",
166
                 en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
167
      OSPF_TRACE(D_EVENTS, "Postponing LSA: Type: %04x, Id: %R, Rt: %R",
168
                 en->lsa_type, en->lsa.id, en->lsa.rt);
169
    }
170
  }
171
  else
172
  {
173
    /*
174
     * We do not have received LSA in the database. We have to flush the
175
     * received LSA. It has to be installed in the database to secure
176
     * retransmissions. Note that the received LSA may already be MaxAge.
177
     * Also note that en->next_lsa_* may be defined.
178
     */
179

    
180
    lsa->age = LSA_MAXAGE;
181
    en = ospf_install_lsa(p, lsa, type, domain, body);
182
  }
183

    
184
  /*
185
   * We flood the updated LSA. Although in some cases the to-be-flooded LSA is
186
   * the same as the received LSA, and therefore we should propagate it as
187
   * regular received LSA (send the acknowledgement instead of the update to
188
   * the neighbor we received it from), we cheat a bit here.
189
   */
190

    
191
  ospf_flood_lsa(p, en, NULL);
192
}
193

    
194

    
195
static int
196
ospf_do_originate_lsa(struct ospf_proto *p, struct top_hash_entry *en, void *lsa_body, u16 lsa_blen, u16 lsa_opts)
197
{
198
  /* Enforce MinLSInterval */
199
  if (!en->init_age && en->inst_time && (lsa_inst_age(en) < MINLSINTERVAL))
200
    return 0;
201

    
202
  /* Handle wrapping sequence number */
203
  if (en->lsa.sn == LSA_MAXSEQNO)
204
  {
205
    /* Prepare to flush old LSA */
206
    if (en->lsa.age != LSA_MAXAGE)
207
    {
208
      OSPF_TRACE(D_EVENTS, "Resetting LSA:  Type: %04x, Id: %R, Rt: %R, Seq: %08x",
209
                 en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
210

    
211
      en->lsa.age = LSA_MAXAGE;
212
      ospf_flood_lsa(p, en, NULL);
213
      return 0;
214
    }
215

    
216
    /* Already flushing */
217
    if ((p->padj != 0) || (en->ret_count != 0))
218
      return 0;
219

    
220
    /* Flush done, just clean up seqnum, lsa_body is freed below */
221
    en->lsa.sn = LSA_ZEROSEQNO;
222
  }
223

    
224
  /*
225
   * lsa.type_raw is initialized by ospf_hash_get() to OSPFv3 LSA type.
226
   * lsa_set_options() implicitly converts it to OSPFv2 LSA type, assuming that
227
   * old type is just new type masked by 0xff. That holds for most OSPFv2 types,
228
   * but we have to fix it for opaque LSAs.
229
   */
230

    
231
  if (ospf_is_v2(p))
232
  {
233
    if (lsa_is_opaque(en->lsa_type))
234
      en->lsa.type_raw = LSA_T_V2_OPAQUE_ + LSA_SCOPE_ORDER(en->lsa_type);
235

    
236
    lsa_set_options(&en->lsa, lsa_opts);
237
  }
238

    
239
  mb_free(en->lsa_body);
240
  en->lsa_body = lsa_body;
241
  en->lsa.length = sizeof(struct ospf_lsa_header) + lsa_blen;
242
  en->lsa.sn++;
243
  en->lsa.age = 0;
244
  en->init_age = 0;
245
  en->inst_time = current_time();
246
  lsa_generate_checksum(&en->lsa, en->lsa_body);
247

    
248
  OSPF_TRACE(D_EVENTS, "Originating LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
249
             en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
250

    
251
  ospf_flood_lsa(p, en, NULL);
252

    
253
  if (en->mode == LSA_M_BASIC)
254
    ospf_schedule_rtcalc(p);
255

    
256
  return 1;
257
}
258

    
259
/**
260
 * ospf_originate_lsa - originate new LSA
261
 * @p: OSPF protocol instance
262
 * @lsa: New LSA specification
263
 *
264
 * This function prepares a new LSA, installs it into the LSA database and
265
 * floods it. If the new LSA cannot be originated now (because the old instance
266
 * was originated within MinLSInterval, or because the LSA seqnum is currently
267
 * wrapping), the origination is instead scheduled for later. If the new LSA is
268
 * equivalent to the current LSA, the origination is skipped. In all cases, the
269
 * corresponding LSA entry is returned. The new LSA is based on the LSA
270
 * specification (@lsa) and the LSA body from lsab buffer of @p, which is
271
 * emptied after the call. The opposite of this function is ospf_flush_lsa().
272
 */
273
struct top_hash_entry *
274
ospf_originate_lsa(struct ospf_proto *p, struct ospf_new_lsa *lsa)
275
{
276
  struct top_hash_entry *en;
277
  void *lsa_body = p->lsab;
278
  u16 lsa_blen = p->lsab_used;
279
  u16 lsa_length = sizeof(struct ospf_lsa_header) + lsa_blen;
280

    
281
  /* For OSPFv2 Opaque LSAs, LS ID consists of Opaque Type and Opaque ID */
282
  if (ospf_is_v2(p) && lsa_is_opaque(lsa->type))
283
    lsa->id |= (u32) lsa_get_opaque_type(lsa->type) << 24;
284

    
285
  en = ospf_hash_get(p->gr, lsa->dom, lsa->id, p->router_id, lsa->type);
286

    
287
  if (!SNODE_VALID(en))
288
    s_add_tail(&p->lsal, SNODE en);
289

    
290
  if (!en->nf || !en->lsa_body)
291
    en->nf = lsa->nf;
292

    
293
  if (en->nf != lsa->nf)
294
  {
295
    log(L_ERR "%s: LSA ID collision for %N",
296
        p->p.name, lsa->nf->fn.addr);
297

    
298
    en = NULL;
299
    goto drop;
300
  }
301

    
302
  if (en->mode != lsa->mode)
303
    en->mode = lsa->mode;
304

    
305
  if (en->next_lsa_body)
306
  {
307
    /* Ignore the new LSA if it is the same as the scheduled one */
308
    if ((lsa_blen == en->next_lsa_blen) &&
309
        !memcmp(lsa_body, en->next_lsa_body, lsa_blen) &&
310
        (!ospf_is_v2(p) || (lsa->opts == en->next_lsa_opts)))
311
      goto drop;
312

    
313
    /* Free scheduled LSA */
314
    mb_free(en->next_lsa_body);
315
    en->next_lsa_body = NULL;
316
    en->next_lsa_blen = 0;
317
    en->next_lsa_opts = 0;
318
  }
319

    
320
  /* Ignore the the new LSA if is the same as the current one */
321
  if ((en->lsa.age < LSA_MAXAGE) &&
322
      (lsa_length == en->lsa.length) &&
323
      !memcmp(lsa_body, en->lsa_body, lsa_blen) &&
324
      (!ospf_is_v2(p) || (lsa->opts == lsa_get_options(&en->lsa))))
325
    goto drop;
326

    
327
  lsa_body = lsab_flush(p);
328

    
329
  if (! ospf_do_originate_lsa(p, en, lsa_body, lsa_blen, lsa->opts))
330
  {
331
    OSPF_TRACE(D_EVENTS, "Postponing LSA: Type: %04x, Id: %R, Rt: %R",
332
               en->lsa_type, en->lsa.id, en->lsa.rt);
333

    
334
    en->next_lsa_body = lsa_body;
335
    en->next_lsa_blen = lsa_blen;
336
    en->next_lsa_opts = lsa->opts;
337
  }
338

    
339
  return en;
340

    
341
 drop:
342
  lsab_reset(p);
343
  return en;
344
}
345

    
346
static void
347
ospf_originate_next_lsa(struct ospf_proto *p, struct top_hash_entry *en)
348
{
349
  /* Called by ospf_update_lsadb() to handle scheduled origination */
350

    
351
  if (! ospf_do_originate_lsa(p, en, en->next_lsa_body, en->next_lsa_blen, en->next_lsa_opts))
352
    return;
353

    
354
  en->next_lsa_body = NULL;
355
  en->next_lsa_blen = 0;
356
  en->next_lsa_opts = 0;
357
}
358

    
359
static void
360
ospf_refresh_lsa(struct ospf_proto *p, struct top_hash_entry *en)
361
{
362
  /*
363
   * Called by ospf_update_lsadb() for periodic LSA refresh.
364
   *
365
   * We know that lsa.age < LSA_MAXAGE and lsa.rt is our router ID. We can also
366
   * assume that there is no scheduled LSA, because inst_time is deep in past,
367
   * therefore ospf_originate_next_lsa() called before would either succeed or
368
   * switched lsa.age to LSA_MAXAGE.
369
   */
370

    
371
  OSPF_TRACE(D_EVENTS, "Refreshing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
372
             en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
373

    
374
  ASSERT(en->next_lsa_body == NULL);
375

    
376
  /* Handle wrapping sequence number */
377
  if (en->lsa.sn == LSA_MAXSEQNO)
378
  {
379
    /* Copy LSA body as next LSA to get automatic origination after flush is finished */
380
    en->next_lsa_blen = en->lsa.length - sizeof(struct ospf_lsa_header);
381
    en->next_lsa_body = mb_alloc(p->p.pool, en->next_lsa_blen);
382
    memcpy(en->next_lsa_body, en->lsa_body, en->next_lsa_blen);
383
    en->next_lsa_opts = ospf_is_v2(p) ? lsa_get_options(&en->lsa) : 0;
384

    
385
    en->lsa.age = LSA_MAXAGE;
386
    ospf_flood_lsa(p, en, NULL);
387
    return;
388
  }
389

    
390
  en->lsa.sn++;
391
  en->lsa.age = 0;
392
  en->init_age = 0;
393
  en->inst_time = current_time();
394
  lsa_generate_checksum(&en->lsa, en->lsa_body);
395
  ospf_flood_lsa(p, en, NULL);
396
}
397

    
398
/**
399
 * ospf_flush_lsa - flush LSA from OSPF domain
400
 * @p: OSPF protocol instance
401
 * @en: LSA entry to flush
402
 *
403
 * This function flushes @en from the OSPF domain by setting its age to
404
 * %LSA_MAXAGE and flooding it. That also triggers subsequent events in LSA
405
 * lifecycle leading to removal of the LSA from the LSA database (e.g. the LSA
406
 * content is freed when flushing is acknowledged by neighbors). The function
407
 * does nothing if the LSA is already being flushed. LSA entries are not
408
 * immediately removed when being flushed, the caller may assume that @en still
409
 * exists after the call. The function is the opposite of ospf_originate_lsa()
410
 * and is supposed to do the right thing even in cases of postponed
411
 * origination.
412
 */
413
void
414
ospf_flush_lsa(struct ospf_proto *p, struct top_hash_entry *en)
415
{
416
  en->nf = NULL;
417

    
418
  if (en->next_lsa_body)
419
  {
420
    mb_free(en->next_lsa_body);
421
    en->next_lsa_body = NULL;
422
    en->next_lsa_blen = 0;
423
    en->next_lsa_opts = 0;
424
  }
425

    
426
  if (en->lsa.age == LSA_MAXAGE)
427
    return;
428

    
429
  OSPF_TRACE(D_EVENTS, "Flushing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
430
             en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
431

    
432
  en->lsa.age = LSA_MAXAGE;
433
  ospf_flood_lsa(p, en, NULL);
434

    
435
  if (en->mode == LSA_M_BASIC)
436
    ospf_schedule_rtcalc(p);
437

    
438
  en->mode = LSA_M_BASIC;
439
}
440

    
441
static void
442
ospf_clear_lsa(struct ospf_proto *p, struct top_hash_entry *en)
443
{
444
  /*
445
   * Called by ospf_update_lsadb() as part of LSA flushing process.
446
   * Flushed LSA was acknowledged by neighbors and we can free its content.
447
   * The log message is for 'remove' - we hide empty LSAs from users.
448
   */
449

    
450
  OSPF_TRACE(D_EVENTS, "Removing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
451
             en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
452

    
453
  if (en->lsa.sn == LSA_MAXSEQNO)
454
    en->lsa.sn = LSA_ZEROSEQNO;
455

    
456
  mb_free(en->lsa_body);
457
  en->lsa_body = NULL;
458
}
459

    
460
static void
461
ospf_remove_lsa(struct ospf_proto *p, struct top_hash_entry *en)
462
{
463
  /*
464
   * Called by ospf_update_lsadb() as part of LSA flushing process.
465
   * Both lsa_body and next_lsa_body are NULL.
466
   */
467

    
468
  s_rem_node(SNODE en);
469
  ospf_hash_delete(p->gr, en);
470
}
471

    
472
/**
473
 * ospf_update_lsadb - update LSA database
474
 * @p: OSPF protocol instance
475
 *
476
 * This function is periodicaly invoked from ospf_disp(). It does some periodic
477
 * or postponed processing related to LSA entries. It originates postponed LSAs
478
 * scheduled by ospf_originate_lsa(), It continues in flushing processes started
479
 * by ospf_flush_lsa(). It also periodically refreshs locally originated LSAs --
480
 * when the current instance is older %LSREFRESHTIME, a new instance is originated.
481
 * Finally, it also ages stored LSAs and flushes ones that reached %LSA_MAXAGE.
482
 *
483
 * The RFC 2328 says that a router should periodically check checksums of all
484
 * stored LSAs to detect hardware problems. This is not implemented.
485
 */
486
void
487
ospf_update_lsadb(struct ospf_proto *p)
488
{
489
  struct top_hash_entry *en, *nxt;
490
  btime now_ = current_time();
491
  int real_age;
492

    
493
  WALK_SLIST_DELSAFE(en, nxt, p->lsal)
494
  {
495
    if (en->next_lsa_body)
496
      ospf_originate_next_lsa(p, en);
497

    
498
    real_age = en->init_age + (now_ - en->inst_time) TO_S;
499

    
500
    if (en->lsa.age == LSA_MAXAGE)
501
    {
502
      if (en->lsa_body && (p->padj == 0) && (en->ret_count == 0))
503
        ospf_clear_lsa(p, en);
504

    
505
      if ((en->lsa_body == NULL) && (en->next_lsa_body == NULL) &&
506
          ((en->lsa.rt != p->router_id) || (real_age >= LSA_MAXAGE)))
507
        ospf_remove_lsa(p, en);
508

    
509
      continue;
510
    }
511

    
512
    if ((en->lsa.rt == p->router_id) && (real_age >= LSREFRESHTIME))
513
    {
514
      ospf_refresh_lsa(p, en);
515
      continue;
516
    }
517

    
518
    if (real_age >= LSA_MAXAGE)
519
    {
520
      ospf_flush_lsa(p, en);
521
      continue;
522
    }
523

    
524
    en->lsa.age = real_age;
525
  }
526
}
527

    
528

    
529
static u32
530
ort_to_lsaid(struct ospf_proto *p, ort *nf)
531
{
532
  /*
533
   * In OSPFv2, We have to map IP prefixes to u32 in such manner that resulting
534
   * u32 interpreted as IP address is a member of given prefix. Therefore, /32
535
   * prefix has to be mapped on itself.  All received prefixes have to be mapped
536
   * on different u32s.
537
   *
538
   * We have an assumption that if there is nontrivial (non-/32) network prefix,
539
   * then there is not /32 prefix for the first and the last IP address of the
540
   * network (these are usually reserved, therefore it is not an important
541
   * restriction).  The network prefix is mapped to the first or the last IP
542
   * address in the manner that disallow collisions - we use the IP address that
543
   * cannot be used by the parent prefix.
544
   *
545
   * For example:
546
   * 192.168.0.0/24 maps to 192.168.0.255
547
   * 192.168.1.0/24 maps to 192.168.1.0
548
   * because 192.168.0.0 and 192.168.1.255 might be used by 192.168.0.0/23 .
549
   *
550
   * Appendig E of RFC 2328 suggests different algorithm, that tries to maximize
551
   * both compatibility and subnetting. But as it is not possible to have both
552
   * reliably and the suggested algorithm was unnecessary complicated and it
553
   * does crazy things like changing LSA ID for a network because different
554
   * network appeared, we choose a different way.
555
   *
556
   * In OSPFv3, it is simpler. There is not a requirement for membership of the
557
   * result in the input network, so we just allocate a unique ID from ID map
558
   * and store it in nf->lsa_id for further reference.
559
   */
560

    
561
  if (ospf_is_v3(p))
562
  {
563
    if (!nf->lsa_id)
564
      nf->lsa_id = idm_alloc(&p->idm);
565

    
566
    return nf->lsa_id;
567
  }
568

    
569
  net_addr_ip4 *net = (void *) nf->fn.addr;
570
  u32 id = ip4_to_u32(net->prefix);
571
  int pxlen = net->pxlen;
572

    
573
  if ((pxlen == 0) || (pxlen == 32))
574
    return id;
575

    
576
  if (id & (1 << (32 - pxlen)))
577
    return id;
578
  else
579
    return id | ~u32_mkmask(pxlen);
580
}
581

    
582

    
583
static void *
584
lsab_alloc(struct ospf_proto *p, uint size)
585
{
586
  uint offset = p->lsab_used;
587
  p->lsab_used += size;
588
  if (p->lsab_used > p->lsab_size)
589
  {
590
    p->lsab_size = MAX(p->lsab_used, 2 * p->lsab_size);
591
    p->lsab = p->lsab ? mb_realloc(p->lsab, p->lsab_size):
592
      mb_alloc(p->p.pool, p->lsab_size);
593
  }
594
  return ((byte *) p->lsab) + offset;
595
}
596

    
597
static inline void *
598
lsab_allocz(struct ospf_proto *p, uint size)
599
{
600
  void *r = lsab_alloc(p, size);
601
  bzero(r, size);
602
  return r;
603
}
604

    
605
static inline void *
606
lsab_flush(struct ospf_proto *p)
607
{
608
  void *r = mb_alloc(p->p.pool, p->lsab_used);
609
  memcpy(r, p->lsab, p->lsab_used);
610
  p->lsab_used = 0;
611
  return r;
612
}
613

    
614
static inline void
615
lsab_reset(struct ospf_proto *p)
616
{
617
  p->lsab_used = 0;
618
}
619

    
620
static inline void *
621
lsab_offset(struct ospf_proto *p, uint offset)
622
{
623
  return ((byte *) p->lsab) + offset;
624
}
625

    
626
static inline void * UNUSED
627
lsab_end(struct ospf_proto *p)
628
{
629
  return ((byte *) p->lsab) + p->lsab_used;
630
}
631

    
632

    
633
/*
634
 *        Router-LSA handling
635
 *        Type = LSA_T_RT
636
 */
637

    
638
static int
639
configured_stubnet(struct ospf_area *oa, struct ifa *a)
640
{
641
  /* Does not work for IA_PEER addresses, but it is not called on these */
642
  struct ospf_stubnet_config *sn;
643
  WALK_LIST(sn, oa->ac->stubnet_list)
644
  {
645
    if (sn->summary)
646
    {
647
      if (net_in_netX(&a->prefix, &sn->prefix))
648
        return 1;
649
    }
650
    else
651
    {
652
      if (net_equal(&a->prefix, &sn->prefix))
653
        return 1;
654
    }
655
  }
656

    
657
  return 0;
658
}
659

    
660
static int
661
bcast_net_active(struct ospf_iface *ifa)
662
{
663
  struct ospf_neighbor *neigh;
664

    
665
  if (ifa->state == OSPF_IS_WAITING)
666
    return 0;
667

    
668
  WALK_LIST(neigh, ifa->neigh_list)
669
  {
670
    if (neigh->state == NEIGHBOR_FULL)
671
    {
672
      if (neigh->rid == ifa->drid)
673
        return 1;
674

    
675
      if (ifa->state == OSPF_IS_DR)
676
        return 1;
677
    }
678
  }
679

    
680
  return 0;
681
}
682

    
683
static inline u32
684
get_rt_options(struct ospf_proto *p, struct ospf_area *oa, int bitv)
685
{
686
  u32 opts = 0;
687

    
688
  if (p->areano > 1)
689
    opts |= OPT_RT_B;
690

    
691
  if ((p->areano > 1) && oa_is_nssa(oa) && oa->ac->translator)
692
    opts |= OPT_RT_NT;
693

    
694
  if (p->asbr && !oa_is_stub(oa))
695
    opts |= OPT_RT_E;
696

    
697
  if (bitv)
698
    opts |= OPT_RT_V;
699

    
700
  return opts;
701
}
702

    
703
static inline void
704
add_rt2_lsa_link(struct ospf_proto *p, u8 type, u32 id, u32 data, u16 metric)
705
{
706
  struct ospf_lsa_rt2_link *ln = lsab_alloc(p, sizeof(struct ospf_lsa_rt2_link));
707
  ln->type = type;
708
  ln->id = id;
709
  ln->data = data;
710
  ln->metric = metric;
711
  ln->no_tos = 0;
712
}
713

    
714
static void
715
prepare_rt2_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
716
{
717
  struct ospf_iface *ifa;
718
  int i = 0, bitv = 0;
719
  struct ospf_neighbor *neigh;
720

    
721
  ASSERT(p->lsab_used == 0);
722
  lsab_allocz(p, sizeof(struct ospf_lsa_rt));
723
  /* ospf_lsa_rt header will be filled later */
724

    
725
  WALK_LIST(ifa, p->iface_list)
726
  {
727
    int net_lsa = 0;
728
    u32 link_cost = p->stub_router ? 0xffff : ifa->cost;
729

    
730
    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
731
        (!EMPTY_LIST(ifa->neigh_list)))
732
    {
733
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
734
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
735
        bitv = 1;
736
    }
737

    
738
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
739
      continue;
740

    
741
    ifa->rt_pos_beg = i;
742

    
743
    /* RFC 2328 - 12.4.1.1-4 */
744
    switch (ifa->type)
745
    {
746
    case OSPF_IT_PTP:
747
    case OSPF_IT_PTMP:
748
      WALK_LIST(neigh, ifa->neigh_list)
749
        if (neigh->state == NEIGHBOR_FULL)
750
        {
751
          /*
752
           * ln->data should be ifa->iface_id in case of no/ptp
753
           * address (ifa->addr->flags & IA_PEER) on PTP link (see
754
           * RFC 2328 12.4.1.1.), but the iface ID value has no use,
755
           * while using IP address even in this case is here for
756
           * compatibility with some broken implementations that use
757
           * this address as a next-hop.
758
           */
759
          add_rt2_lsa_link(p, LSART_PTP, neigh->rid, ipa_to_u32(ifa->addr->ip), link_cost);
760
          i++;
761
        }
762
      break;
763

    
764
    case OSPF_IT_BCAST:
765
    case OSPF_IT_NBMA:
766
      if (bcast_net_active(ifa))
767
      {
768
        add_rt2_lsa_link(p, LSART_NET, ipa_to_u32(ifa->drip), ipa_to_u32(ifa->addr->ip), link_cost);
769
        i++;
770
        net_lsa = 1;
771
      }
772
      break;
773

    
774
    case OSPF_IT_VLINK:
775
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
776
      if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
777
        add_rt2_lsa_link(p, LSART_VLNK, neigh->rid, ipa_to_u32(ifa->addr->ip), link_cost), i++;
778
      break;
779

    
780
    default:
781
      log(L_BUG "OSPF: Unknown interface type");
782
      break;
783
    }
784

    
785
    ifa->rt_pos_end = i;
786

    
787
    /* Now we will originate stub area if there is no primary */
788
    if (net_lsa ||
789
        (ifa->type == OSPF_IT_VLINK) ||
790
        ((ifa->addr->flags & IA_PEER) && ! ifa->cf->stub) ||
791
        configured_stubnet(oa, ifa->addr))
792
      continue;
793

    
794
      /* Host or network stub entry */
795
    if ((ifa->addr->flags & IA_HOST) ||
796
        (ifa->state == OSPF_IS_LOOP) ||
797
        (ifa->type == OSPF_IT_PTMP))
798
      add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(ifa->addr->ip), 0xffffffff, 0);
799
    else
800
      add_rt2_lsa_link(p, LSART_STUB, ip4_to_u32(net4_prefix(&ifa->addr->prefix)),
801
                       u32_mkmask(net4_pxlen(&ifa->addr->prefix)), ifa->cost);
802
    i++;
803

    
804
    ifa->rt_pos_end = i;
805
  }
806

    
807
  struct ospf_stubnet_config *sn;
808
  WALK_LIST(sn, oa->ac->stubnet_list)
809
    if (!sn->hidden)
810
      add_rt2_lsa_link(p, LSART_STUB, ip4_to_u32(net4_prefix(&sn->prefix)),
811
                       u32_mkmask(net4_pxlen(&sn->prefix)), sn->cost), i++;
812

    
813
  struct ospf_lsa_rt *rt = p->lsab;
814
  /* Store number of links in lower half of options */
815
  rt->options = get_rt_options(p, oa, bitv) | (u16) i;
816
}
817

    
818
static inline void
819
add_rt3_lsa_link(struct ospf_proto *p, u8 type, struct ospf_iface *ifa, u32 nif, u32 id)
820
{
821
  struct ospf_lsa_rt3_link *ln = lsab_alloc(p, sizeof(struct ospf_lsa_rt3_link));
822
  ln->type = type;
823
  ln->padding = 0;
824
  ln->metric = ifa->cost;
825
  ln->lif = ifa->iface_id;
826
  ln->nif = nif;
827
  ln->id = id;
828
}
829

    
830
static void
831
prepare_rt3_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
832
{
833
  struct ospf_iface *ifa;
834
  struct ospf_neighbor *neigh;
835
  int bitv = 0;
836
  int i = 0;
837

    
838
  ASSERT(p->lsab_used == 0);
839
  lsab_allocz(p, sizeof(struct ospf_lsa_rt));
840
  /* ospf_lsa_rt header will be filled later */
841

    
842
  WALK_LIST(ifa, p->iface_list)
843
  {
844
    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
845
        (!EMPTY_LIST(ifa->neigh_list)))
846
    {
847
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
848
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
849
        bitv = 1;
850
    }
851

    
852
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
853
      continue;
854

    
855
    ifa->rt_pos_beg = i;
856

    
857
    /* RFC 5340 - 4.4.3.2 */
858
    switch (ifa->type)
859
    {
860
    case OSPF_IT_PTP:
861
    case OSPF_IT_PTMP:
862
      WALK_LIST(neigh, ifa->neigh_list)
863
        if (neigh->state == NEIGHBOR_FULL)
864
          add_rt3_lsa_link(p, LSART_PTP, ifa, neigh->iface_id, neigh->rid), i++;
865
      break;
866

    
867
    case OSPF_IT_BCAST:
868
    case OSPF_IT_NBMA:
869
      if (bcast_net_active(ifa))
870
        add_rt3_lsa_link(p, LSART_NET, ifa, ifa->dr_iface_id, ifa->drid), i++;
871
      break;
872

    
873
    case OSPF_IT_VLINK:
874
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
875
      if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
876
        add_rt3_lsa_link(p, LSART_VLNK, ifa, neigh->iface_id, neigh->rid), i++;
877
      break;
878

    
879
    default:
880
      log(L_BUG "OSPF: Unknown interface type");
881
      break;
882
    }
883

    
884
    ifa->rt_pos_end = i;
885
  }
886

    
887
  struct ospf_lsa_rt *rt = p->lsab;
888
  rt->options = get_rt_options(p, oa, bitv) | (oa->options & LSA_OPTIONS_MASK);
889
}
890

    
891
static void
892
ospf_originate_rt_lsa(struct ospf_proto *p, struct ospf_area *oa)
893
{
894
  struct ospf_new_lsa lsa = {
895
    .type = LSA_T_RT,
896
    .dom  = oa->areaid,
897
    .id   = ospf_is_v2(p) ? p->router_id : 0,
898
    .opts = oa->options
899
  };
900

    
901
  OSPF_TRACE(D_EVENTS, "Updating router state for area %R", oa->areaid);
902

    
903
  if (ospf_is_v2(p))
904
    prepare_rt2_lsa_body(p, oa);
905
  else
906
    prepare_rt3_lsa_body(p, oa);
907

    
908
  oa->rt = ospf_originate_lsa(p, &lsa);
909
}
910

    
911

    
912
/*
913
 *        Net-LSA handling
914
 *        Type = LSA_T_NET
915
 */
916

    
917
static void
918
prepare_net2_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
919
{
920
  struct ospf_lsa_net *net;
921
  struct ospf_neighbor *n;
922
  int nodes = ifa->fadj + 1;
923
  u16 i = 1;
924

    
925
  ASSERT(p->lsab_used == 0);
926
  net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes);
927

    
928
  net->optx = u32_mkmask(ifa->addr->prefix.pxlen);
929
  net->routers[0] = p->router_id;
930

    
931
  WALK_LIST(n, ifa->neigh_list)
932
  {
933
    if (n->state == NEIGHBOR_FULL)
934
    {
935
      net->routers[i] = n->rid;
936
      i++;
937
    }
938
  }
939
  ASSERT(i == nodes);
940
}
941

    
942
static void
943
prepare_net3_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
944
{
945
  struct ospf_lsa_net *net;
946
  int nodes = ifa->fadj + 1;
947
  u32 options = 0;
948
  u16 i = 1;
949

    
950
  ASSERT(p->lsab_used == 0);
951
  net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes);
952

    
953
  net->routers[0] = p->router_id;
954

    
955
  struct ospf_neighbor *n;
956
  WALK_LIST(n, ifa->neigh_list)
957
  {
958
    if (n->state == NEIGHBOR_FULL)
959
    {
960
      /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */
961

    
962
      struct top_hash_entry *en =
963
        ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK);
964

    
965
      if (en)
966
        options |= ((struct ospf_lsa_link *) en->lsa_body)->options;
967

    
968
      net->routers[i] = n->rid;
969
      i++;
970
    }
971
  }
972
  ASSERT(i == nodes);
973

    
974
  net->optx = options & LSA_OPTIONS_MASK;
975
}
976

    
977
static void
978
ospf_originate_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
979
{
980
  struct ospf_new_lsa lsa = {
981
    .type = LSA_T_NET,
982
    .dom  = ifa->oa->areaid,
983
    .id   = ospf_is_v2(p) ? ipa_to_u32(ifa->addr->ip) : ifa->iface_id,
984
    .opts = ifa->oa->options,
985
    .ifa  = ifa
986
  };
987

    
988
  OSPF_TRACE(D_EVENTS, "Updating network state for %s (Id: %R)", ifa->ifname, lsa.id);
989

    
990
  if (ospf_is_v2(p))
991
    prepare_net2_lsa_body(p, ifa);
992
  else
993
    prepare_net3_lsa_body(p, ifa);
994

    
995
  ifa->net_lsa = ospf_originate_lsa(p, &lsa);
996
}
997

    
998

    
999
/*
1000
 *        (Net|Rt)-summary-LSA handling
1001
 *        (a.k.a. Inter-Area-(Prefix|Router)-LSA)
1002
 *        Type = LSA_T_SUM_NET, LSA_T_SUM_RT
1003
 */
1004

    
1005
static inline void
1006
prepare_sum2_lsa_body(struct ospf_proto *p, uint pxlen, u32 metric)
1007
{
1008
  struct ospf_lsa_sum2 *sum;
1009

    
1010
  sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum2));
1011
  sum->netmask = u32_mkmask(pxlen);
1012
  sum->metric = metric;
1013
}
1014

    
1015
static inline void
1016
prepare_sum3_net_lsa_body(struct ospf_proto *p, ort *nf, u32 metric)
1017
{
1018
  struct ospf_lsa_sum3_net *sum;
1019

    
1020
  sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_net) +
1021
                    IPV6_PREFIX_SPACE(nf->fn.addr->pxlen));
1022
  sum->metric = metric;
1023
  ospf3_put_prefix(sum->prefix, nf->fn.addr, 0, 0);
1024
}
1025

    
1026
static inline void
1027
prepare_sum3_rt_lsa_body(struct ospf_proto *p, u32 drid, u32 metric, u32 options)
1028
{
1029
  struct ospf_lsa_sum3_rt *sum;
1030

    
1031
  sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_rt));
1032
  sum->options = options;
1033
  sum->metric = metric;
1034
  sum->drid = drid;
1035
}
1036

    
1037
void
1038
ospf_originate_sum_net_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, int metric)
1039
{
1040
  struct ospf_new_lsa lsa = {
1041
    .type = LSA_T_SUM_NET,
1042
    .mode = LSA_M_RTCALC,
1043
    .dom  = oa->areaid,
1044
    .id   = ort_to_lsaid(p, nf),
1045
    .opts = oa->options,
1046
    .nf   = nf
1047
  };
1048

    
1049
  if (ospf_is_v2(p))
1050
    prepare_sum2_lsa_body(p, nf->fn.addr->pxlen, metric);
1051
  else
1052
    prepare_sum3_net_lsa_body(p, nf, metric);
1053

    
1054
  ospf_originate_lsa(p, &lsa);
1055
}
1056

    
1057
void
1058
ospf_originate_sum_rt_lsa(struct ospf_proto *p, struct ospf_area *oa, u32 drid, int metric, u32 options)
1059
{
1060
  struct ospf_new_lsa lsa = {
1061
    .type = LSA_T_SUM_RT,
1062
    .mode = LSA_M_RTCALC,
1063
    .dom  = oa->areaid,
1064
    .id   = drid,        /* Router ID of ASBR, irrelevant for OSPFv3 */
1065
    .opts = oa->options
1066
  };
1067

    
1068
  if (ospf_is_v2(p))
1069
    prepare_sum2_lsa_body(p, 0, metric);
1070
  else
1071
    prepare_sum3_rt_lsa_body(p, drid, metric, options & LSA_OPTIONS_MASK);
1072

    
1073
  ospf_originate_lsa(p, &lsa);
1074
}
1075

    
1076

    
1077
/*
1078
 *        AS-external-LSA and NSSA-LSA handling
1079
 *        Type = LSA_T_EXT, LSA_T_NSSA
1080
 */
1081

    
1082
static inline void
1083
prepare_ext2_lsa_body(struct ospf_proto *p, uint pxlen,
1084
                      u32 metric, u32 ebit, ip_addr fwaddr, u32 tag)
1085
{
1086
  struct ospf_lsa_ext2 *ext;
1087

    
1088
  ext = lsab_allocz(p, sizeof(struct ospf_lsa_ext2));
1089
  ext->metric = metric & LSA_METRIC_MASK;
1090
  ext->netmask = u32_mkmask(pxlen);
1091
  ext->fwaddr = ipa_to_u32(fwaddr);
1092
  ext->tag = tag;
1093

    
1094
  if (ebit)
1095
    ext->metric |= LSA_EXT2_EBIT;
1096
}
1097

    
1098
static inline void
1099
prepare_ext3_lsa_body(struct ospf_proto *p, ort *nf,
1100
                      u32 metric, u32 ebit, ip_addr fwaddr, u32 tag, int pbit, int dn)
1101
{
1102
  struct ospf_lsa_ext3 *ext;
1103
  int bsize = sizeof(struct ospf_lsa_ext3)
1104
    + IPV6_PREFIX_SPACE(nf->fn.addr->pxlen)
1105
    + (ipa_nonzero(fwaddr) ? 16 : 0)
1106
    + (tag ? 4 : 0);
1107

    
1108
  ext = lsab_allocz(p, bsize);
1109
  ext->metric = metric & LSA_METRIC_MASK;
1110
  u32 *buf = ext->rest;
1111

    
1112
  uint flags = (pbit ? OPT_PX_P : 0) | (dn ? OPT_PX_DN : 0);
1113
  buf = ospf3_put_prefix(buf, nf->fn.addr, flags, 0);
1114

    
1115
  if (ebit)
1116
    ext->metric |= LSA_EXT3_EBIT;
1117

    
1118
  if (ipa_nonzero(fwaddr))
1119
  {
1120
    ext->metric |= LSA_EXT3_FBIT;
1121
    buf = ospf3_put_addr(buf, fwaddr);
1122
  }
1123

    
1124
  if (tag)
1125
  {
1126
    ext->metric |= LSA_EXT3_TBIT;
1127
    *buf++ = tag;
1128
  }
1129
}
1130

    
1131
/**
1132
 * originate_ext_lsa - new route received from nest and filters
1133
 * @p: OSPF protocol instance
1134
 * @oa: ospf_area for which LSA is originated
1135
 * @nf: network prefix and mask
1136
 * @mode: the mode of the LSA (LSA_M_EXPORT or LSA_M_RTCALC)
1137
 * @metric: the metric of a route
1138
 * @ebit: E-bit for route metric (bool)
1139
 * @fwaddr: the forwarding address
1140
 * @tag: the route tag
1141
 * @pbit: P-bit for NSSA LSAs (bool), ignored for external LSAs
1142
 *
1143
 * If I receive a message that new route is installed, I try to originate an
1144
 * external LSA. If @oa is an NSSA area, NSSA-LSA is originated instead.
1145
 * @oa should not be a stub area. @src does not specify whether the LSA
1146
 * is external or NSSA, but it specifies the source of origination -
1147
 * the export from ospf_rt_notify(), or the NSSA-EXT translation.
1148
 */
1149
void
1150
ospf_originate_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, u8 mode,
1151
                       u32 metric, u32 ebit, ip_addr fwaddr, u32 tag, int pbit, int dn)
1152
{
1153
  struct ospf_new_lsa lsa = {
1154
    .type = oa ? LSA_T_NSSA : LSA_T_EXT,
1155
    .mode = mode, /* LSA_M_EXPORT or LSA_M_RTCALC */
1156
    .dom  = oa ? oa->areaid : 0,
1157
    .id   = ort_to_lsaid(p, nf),
1158
    .opts = (oa ? (pbit ? OPT_P : 0) : OPT_E) | (dn ? OPT_DN : 0),
1159
    .nf   = nf
1160
  };
1161

    
1162
  if (ospf_is_v2(p))
1163
    prepare_ext2_lsa_body(p, nf->fn.addr->pxlen, metric, ebit, fwaddr, tag);
1164
  else
1165
    prepare_ext3_lsa_body(p, nf, metric, ebit, fwaddr, tag, oa && pbit, dn);
1166

    
1167
  ospf_originate_lsa(p, &lsa);
1168
}
1169

    
1170
static struct top_hash_entry *
1171
ospf_hash_find_(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type);
1172

    
1173
static void
1174
ospf_flush_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf)
1175
{
1176
  struct top_hash_entry *en;
1177

    
1178
  u32 type = oa ? LSA_T_NSSA : LSA_T_EXT;
1179
  u32 dom = oa ? oa->areaid : 0;
1180
  u32 id = ort_to_lsaid(p, nf);
1181

    
1182
  en = ospf_hash_find_(p->gr, dom, id, p->router_id, type);
1183

    
1184
  if (!en || (en->nf != nf))
1185
    return;
1186

    
1187
  ospf_flush_lsa(p, en);
1188
}
1189

    
1190
static inline int
1191
use_gw_for_fwaddr(struct ospf_proto *p, ip_addr gw, struct iface *iface)
1192
{
1193
  struct ospf_iface *ifa;
1194

    
1195
  if (ipa_zero(gw) || ipa_is_link_local(gw))
1196
    return 0;
1197

    
1198
  WALK_LIST(ifa, p->iface_list)
1199
    if ((ifa->iface == iface) &&
1200
        (!ospf_is_v2(p) || ipa_in_netX(gw, &ifa->addr->prefix)))
1201
      return 1;
1202

    
1203
  return 0;
1204
}
1205

    
1206
static inline ip_addr
1207
find_surrogate_fwaddr(struct ospf_proto *p, struct ospf_area *oa)
1208
{
1209
  struct ospf_iface *ifa;
1210
  struct ifa *a, *cur_addr = NULL;
1211
  int np, cur_np = 0;
1212

    
1213
  /* RFC 3101 2.3 - surrogate forwarding address selection */
1214

    
1215
  WALK_LIST(ifa, p->iface_list)
1216
  {
1217
    if ((ifa->oa != oa) ||
1218
        (ifa->type == OSPF_IT_VLINK))
1219
      continue;
1220

    
1221
    if (ospf_is_v2(p))
1222
    {
1223
      a = ifa->addr;
1224
      if (a->flags & IA_PEER)
1225
        continue;
1226

    
1227
      np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1);
1228
      if (np > cur_np)
1229
      {
1230
        cur_addr = a;
1231
        cur_np = np;
1232
      }
1233
    }
1234
    else /* OSPFv3 */
1235
    {
1236
      WALK_LIST(a, ifa->iface->addrs)
1237
      {
1238
        if ((a->prefix.type != ospf_get_af(p)) ||
1239
            (a->flags & IA_SECONDARY) ||
1240
            (a->flags & IA_PEER) ||
1241
            (a->scope <= SCOPE_LINK))
1242
          continue;
1243

    
1244
        np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1);
1245
        if (np > cur_np)
1246
        {
1247
          cur_addr = a;
1248
          cur_np = np;
1249
        }
1250
      }
1251
    }
1252
  }
1253

    
1254
  return cur_addr ? cur_addr->ip : IPA_NONE;
1255
}
1256

    
1257
void
1258
ospf_rt_notify(struct proto *P, struct channel *ch UNUSED, net *n, rte *new, rte *old UNUSED)
1259
{
1260
  struct ospf_proto *p = (struct ospf_proto *) P;
1261
  struct ospf_area *oa = NULL;        /* non-NULL for NSSA-LSA */
1262
  ort *nf;
1263

    
1264
  /*
1265
   * There are several posibilities:
1266
   * 1) router in regular area - originate external LSA with global scope
1267
   * 2) router in NSSA area - originate area-specific NSSA-LSA
1268
   * 3) router in stub area - cannot export routes
1269
   * 4) area border router - same as (1), it is attached to backbone
1270
   */
1271

    
1272
  if ((p->areano == 1) && oa_is_nssa(HEAD(p->area_list)))
1273
    oa = HEAD(p->area_list);
1274

    
1275
  if (!new)
1276
  {
1277
    nf = fib_find(&p->rtf, n->n.addr);
1278

    
1279
    if (!nf || !nf->external_rte)
1280
      return;
1281

    
1282
    ospf_flush_ext_lsa(p, oa, nf);
1283
    nf->external_rte = 0;
1284

    
1285
    /* Old external route might blocked some NSSA translation */
1286
    if ((p->areano > 1) && rt_is_nssa(nf) && nf->n.oa->translate)
1287
      ospf_schedule_rtcalc(p);
1288

    
1289
    return;
1290
  }
1291

    
1292
  ASSERT(p->asbr);
1293

    
1294
  /* Get route attributes */
1295
  rta *a = new->attrs;
1296
  eattr *m1a = ea_find(a->eattrs, EA_OSPF_METRIC1);
1297
  eattr *m2a = ea_find(a->eattrs, EA_OSPF_METRIC2);
1298
  uint m1 = m1a ? m1a->u.data : 0;
1299
  uint m2 = m2a ? m2a->u.data : 10000;
1300

    
1301
  if (m1 > LSINFINITY)
1302
  {
1303
    log(L_WARN "%s: Invalid ospf_metric1 value %u for route %N",
1304
        p->p.name, m1, n->n.addr);
1305
    m1 = LSINFINITY;
1306
  }
1307

    
1308
  if (m2 > LSINFINITY)
1309
  {
1310
    log(L_WARN "%s: Invalid ospf_metric2 value %u for route %N",
1311
        p->p.name, m2, n->n.addr);
1312
    m2 = LSINFINITY;
1313
  }
1314

    
1315
  /* Ensure monotonicity of metric if both m1 and m2 are used */
1316
  if ((m1 > 0) && (m2 < LSINFINITY))
1317
    m2++;
1318

    
1319
  uint ebit = m2a || !m1a;
1320
  uint metric = ebit ? m2 : m1;
1321
  uint tag = ea_get_int(a->eattrs, EA_OSPF_TAG, 0);
1322

    
1323
  ip_addr fwd = IPA_NONE;
1324
  if ((a->dest == RTD_UNICAST) && use_gw_for_fwaddr(p, a->nh.gw, a->nh.iface))
1325
    fwd = a->nh.gw;
1326

    
1327
  /* NSSA-LSA with P-bit set must have non-zero forwarding address */
1328
  if (oa && ipa_zero(fwd))
1329
  {
1330
    fwd = find_surrogate_fwaddr(p, oa);
1331

    
1332
    if (ipa_zero(fwd))
1333
    {
1334
      log(L_ERR "%s: Cannot find forwarding address for NSSA-LSA %N",
1335
          p->p.name, n->n.addr);
1336
      return;
1337
    }
1338
  }
1339

    
1340
  nf = fib_get(&p->rtf, n->n.addr);
1341
  ospf_originate_ext_lsa(p, oa, nf, LSA_M_EXPORT, metric, ebit, fwd, tag, 1, p->vpn_pe);
1342
  nf->external_rte = 1;
1343
}
1344

    
1345

    
1346
/*
1347
 *        Link-LSA handling (assume OSPFv3)
1348
 *        Type = LSA_T_LINK
1349
 */
1350

    
1351
static inline void
1352
lsab_put_prefix(struct ospf_proto *p, net_addr *n, u32 cost)
1353
{
1354
  void *buf = lsab_alloc(p, IPV6_PREFIX_SPACE(net_pxlen(n)));
1355
  uint max = (n->type == NET_IP4) ? IP4_MAX_PREFIX_LENGTH : IP6_MAX_PREFIX_LENGTH;
1356
  u8 flags = (net_pxlen(n) < max) ? 0 : OPT_PX_LA;
1357
  ospf3_put_prefix(buf, n, flags, cost);
1358
}
1359

    
1360
static void
1361
prepare_link_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
1362
{
1363
  ip_addr nh = ospf_is_ip4(p) ? IPA_NONE : ifa->addr->ip;
1364
  int i = 0;
1365

    
1366
  /* Preallocating space for header */
1367
  ASSERT(p->lsab_used == 0);
1368
  lsab_allocz(p, sizeof(struct ospf_lsa_link));
1369

    
1370
  struct ifa *a;
1371
  WALK_LIST(a, ifa->iface->addrs)
1372
  {
1373
    if ((a->prefix.type != ospf_get_af(p)) ||
1374
        (a->flags & IA_SECONDARY) ||
1375
        (a->scope <= SCOPE_LINK))
1376
      continue;
1377

    
1378
    if (ospf_is_ip4(p) && ipa_zero(nh))
1379
      nh = a->ip;
1380

    
1381
    lsab_put_prefix(p, &a->prefix, 0);
1382
    i++;
1383
  }
1384

    
1385
  /* Filling the preallocated header */
1386
  struct ospf_lsa_link *ll = p->lsab;
1387
  ll->options = ifa->oa->options | (ifa->priority << 24);
1388
  ll->lladdr = ospf_is_ip4(p) ? ospf3_4to6(ipa_to_ip4(nh)) : ipa_to_ip6(nh);
1389
  ll->pxcount = i;
1390

    
1391
  if (ipa_zero(nh))
1392
    log(L_ERR "%s: Cannot find next hop address for %s", p->p.name, ifa->ifname);
1393
}
1394

    
1395
static void
1396
ospf_originate_link_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
1397
{
1398
  if (ospf_is_v2(p))
1399
    return;
1400

    
1401
  struct ospf_new_lsa lsa = {
1402
    .type = LSA_T_LINK,
1403
    .dom  = ifa->iface_id,
1404
    .id   = ifa->iface_id,
1405
    .ifa  = ifa
1406
  };
1407

    
1408
  OSPF_TRACE(D_EVENTS, "Updating link state for %s (Id: %R)", ifa->ifname, lsa.id);
1409

    
1410
  prepare_link_lsa_body(p, ifa);
1411

    
1412
  ifa->link_lsa = ospf_originate_lsa(p, &lsa);
1413
}
1414

    
1415

    
1416
/*
1417
 *        Prefix-Rt-LSA handling (assume OSPFv3)
1418
 *        Type = LSA_T_PREFIX, referred type = LSA_T_RT
1419
 */
1420

    
1421
static void
1422
prepare_prefix_rt_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
1423
{
1424
  struct ospf_config *cf = (struct ospf_config *) (p->p.cf);
1425
  struct ospf_iface *ifa;
1426
  struct ospf_lsa_prefix *lp;
1427
  uint max = ospf_is_ip4(p) ? IP4_MAX_PREFIX_LENGTH : IP6_MAX_PREFIX_LENGTH;
1428
  int host_addr = 0;
1429
  int net_lsa;
1430
  int i = 0;
1431

    
1432
  ASSERT(p->lsab_used == 0);
1433
  lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix));
1434
  lp->ref_type = LSA_T_RT;
1435
  lp->ref_id = 0;
1436
  lp->ref_rt = p->router_id;
1437
  lp = NULL; /* buffer might be reallocated later */
1438

    
1439
  WALK_LIST(ifa, p->iface_list)
1440
  {
1441
    if ((ifa->oa != oa) || (ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
1442
      continue;
1443

    
1444
    ifa->px_pos_beg = i;
1445

    
1446
    if ((ifa->type == OSPF_IT_BCAST) ||
1447
        (ifa->type == OSPF_IT_NBMA))
1448
      net_lsa = bcast_net_active(ifa);
1449
    else
1450
      net_lsa = 0;
1451

    
1452
    struct ifa *a;
1453
    WALK_LIST(a, ifa->iface->addrs)
1454
    {
1455
      if ((a->prefix.type != ospf_get_af(p)) ||
1456
          (a->flags & IA_SECONDARY) ||
1457
          (a->flags & IA_PEER) ||
1458
          (a->scope <= SCOPE_LINK))
1459
        continue;
1460

    
1461
      if (((a->prefix.pxlen < max) && net_lsa) ||
1462
          configured_stubnet(oa, a))
1463
        continue;
1464

    
1465
      if ((a->flags & IA_HOST) ||
1466
          (ifa->state == OSPF_IS_LOOP) ||
1467
          (ifa->type == OSPF_IT_PTMP))
1468
      {
1469
        net_addr net;
1470
        if (a->prefix.type == NET_IP4)
1471
          net_fill_ip4(&net, ipa_to_ip4(a->ip), IP4_MAX_PREFIX_LENGTH);
1472
        else
1473
          net_fill_ip6(&net, ipa_to_ip6(a->ip), IP6_MAX_PREFIX_LENGTH);
1474

    
1475
        lsab_put_prefix(p, &net, 0);
1476
        host_addr = 1;
1477
      }
1478
      else
1479
        lsab_put_prefix(p, &a->prefix, ifa->cost);
1480
      i++;
1481
    }
1482

    
1483
    ifa->px_pos_end = i;
1484
  }
1485

    
1486
  struct ospf_stubnet_config *sn;
1487
  WALK_LIST(sn, oa->ac->stubnet_list)
1488
    if (!sn->hidden)
1489
    {
1490
      lsab_put_prefix(p, &sn->prefix, sn->cost);
1491
      if (sn->prefix.pxlen == max)
1492
        host_addr = 1;
1493
      i++;
1494
    }
1495

    
1496
  /* If there are some configured vlinks, find some global address
1497
     (even from another area), which will be used as a vlink endpoint. */
1498
  if (!EMPTY_LIST(cf->vlink_list) && !host_addr && ospf_is_ip6(p))
1499
  {
1500
    WALK_LIST(ifa, p->iface_list)
1501
    {
1502
      if ((ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
1503
        continue;
1504

    
1505
      struct ifa *a;
1506
      WALK_LIST(a, ifa->iface->addrs)
1507
      {
1508
        if ((a->prefix.type != NET_IP6) ||
1509
            (a->flags & IA_SECONDARY) ||
1510
            (a->scope <= SCOPE_LINK))
1511
          continue;
1512

    
1513
        /* Found some IP */
1514
        net_addr_ip6 net = NET_ADDR_IP6(a->ip, IP6_MAX_PREFIX_LENGTH);
1515
        lsab_put_prefix(p, (net_addr *) &net, 0);
1516
        i++;
1517
        goto done;
1518
      }
1519
    }
1520
  }
1521

    
1522
 done:
1523
  lp = p->lsab;
1524
  lp->pxcount = i;
1525
}
1526

    
1527
static void
1528
ospf_originate_prefix_rt_lsa(struct ospf_proto *p, struct ospf_area *oa)
1529
{
1530
  if (ospf_is_v2(p))
1531
    return;
1532

    
1533
  struct ospf_new_lsa lsa = {
1534
    .type = LSA_T_PREFIX,
1535
    .dom  = oa->areaid,
1536
    .id   = 0
1537
  };
1538

    
1539
  prepare_prefix_rt_lsa_body(p, oa);
1540

    
1541
  ospf_originate_lsa(p, &lsa);
1542
}
1543

    
1544

    
1545
/*
1546
 *        Prefix-Net-LSA handling (assume OSPFv3)
1547
 *        Type = LSA_T_PREFIX, referred type = LSA_T_NET
1548
 */
1549

    
1550
static inline int
1551
prefix_space(u32 *buf)
1552
{
1553
  int pxl = *buf >> 24;
1554
  return IPV6_PREFIX_SPACE(pxl);
1555
}
1556

    
1557
static inline int
1558
prefix_same(u32 *b1, u32 *b2)
1559
{
1560
  int pxl1 = *b1 >> 24;
1561
  int pxl2 = *b2 >> 24;
1562
  int pxs, i;
1563

    
1564
  if (pxl1 != pxl2)
1565
    return 0;
1566

    
1567
  pxs = IPV6_PREFIX_WORDS(pxl1);
1568
  for (i = 1; i < pxs; i++)
1569
    if (b1[i] != b2[i])
1570
      return 0;
1571

    
1572
  return 1;
1573
}
1574

    
1575
static inline u32 *
1576
prefix_advance(u32 *buf)
1577
{
1578
  int pxl = *buf >> 24;
1579
  return buf + IPV6_PREFIX_WORDS(pxl);
1580
}
1581

    
1582
/* FIXME eliminate items with LA bit set? see 4.4.3.9 */
1583
static void
1584
add_prefix(struct ospf_proto *p, u32 *px, int offset, int *pxc)
1585
{
1586
  u32 *pxl = lsab_offset(p, offset);
1587
  int i;
1588
  for (i = 0; i < *pxc; pxl = prefix_advance(pxl), i++)
1589
    if (prefix_same(px, pxl))
1590
    {
1591
      /* Options should be logically OR'ed together */
1592
      *pxl |= (*px & 0x00FF0000);
1593
      return;
1594
    }
1595

    
1596
  ASSERT(pxl == lsab_end(p));
1597

    
1598
  int pxspace = prefix_space(px);
1599
  pxl = lsab_alloc(p, pxspace);
1600
  memcpy(pxl, px, pxspace);
1601
  *pxl &= 0xFFFF0000;        /* Set metric to zero */
1602
  (*pxc)++;
1603
}
1604

    
1605
static void
1606
add_link_lsa(struct ospf_proto *p, struct ospf_lsa_link *ll, int offset, int *pxc)
1607
{
1608
  u32 *pxb = ll->rest;
1609
  uint j;
1610

    
1611
  for (j = 0; j < ll->pxcount; pxb = prefix_advance(pxb), j++)
1612
  {
1613
    u8 pxlen = (pxb[0] >> 24);
1614
    u8 pxopts = (pxb[0] >> 16);
1615

    
1616
    /* Skip NU or LA prefixes */
1617
    if (pxopts & (OPT_PX_NU | OPT_PX_LA))
1618
      continue;
1619

    
1620
    /* Skip link-local prefixes */
1621
    if (ospf_is_ip6(p) && (pxlen >= 10) && ((pxb[1] & 0xffc00000) == 0xfe800000))
1622
      continue;
1623

    
1624
    add_prefix(p, pxb, offset, pxc);
1625
  }
1626
}
1627

    
1628
static void
1629
prepare_prefix_net_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
1630
{
1631
  struct ospf_lsa_prefix *lp;
1632
  struct ospf_neighbor *n;
1633
  struct top_hash_entry *en;
1634
  int pxc, offset;
1635

    
1636
  ASSERT(p->lsab_used == 0);
1637
  lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix));
1638
  lp->ref_type = LSA_T_NET;
1639
  lp->ref_id = ifa->net_lsa->lsa.id;
1640
  lp->ref_rt = p->router_id;
1641
  lp = NULL; /* buffer might be reallocated later */
1642

    
1643
  pxc = 0;
1644
  offset = p->lsab_used;
1645

    
1646
  /* Find all Link LSAs associated with the link and merge their prefixes */
1647
  if (en = ifa->link_lsa)
1648
    add_link_lsa(p, en->next_lsa_body ?: en->lsa_body, offset, &pxc);
1649

    
1650
  WALK_LIST(n, ifa->neigh_list)
1651
    if ((n->state == NEIGHBOR_FULL) &&
1652
        (en = ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK)))
1653
      add_link_lsa(p, en->lsa_body, offset, &pxc);
1654

    
1655
  lp = p->lsab;
1656
  lp->pxcount = pxc;
1657
}
1658

    
1659
static void
1660
ospf_originate_prefix_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
1661
{
1662
  if (ospf_is_v2(p))
1663
    return;
1664

    
1665
  struct ospf_new_lsa lsa = {
1666
    .type = LSA_T_PREFIX,
1667
    .dom  = ifa->oa->areaid,
1668
    .id   = ifa->iface_id,
1669
    .ifa  = ifa
1670
  };
1671

    
1672
  prepare_prefix_net_lsa_body(p, ifa);
1673

    
1674
  ifa->pxn_lsa = ospf_originate_lsa(p, &lsa);
1675
}
1676

    
1677

    
1678
/*
1679
 *        Router Information LSA handling
1680
 *        Type = LSA_T_RI_AREA, opaque type = LSA_OT_RI
1681
 */
1682

    
1683
void
1684
ospf_add_ric_tlv(struct ospf_proto *p)
1685
{
1686
  struct ospf_tlv *ri = lsab_allocz(p, sizeof(struct ospf_tlv) + sizeof(u32));
1687
  ri->type = LSA_RI_RIC;
1688
  ri->length = sizeof(struct ospf_tlv) + sizeof(u32);
1689

    
1690
  BIT32R_SET(ri->data, LSA_RIC_STUB_ROUTER);
1691
}
1692

    
1693
void
1694
ospf_originate_ri_lsa(struct ospf_proto *p, struct ospf_area *oa)
1695
{
1696
  struct ospf_new_lsa lsa = {
1697
    .type = LSA_T_RI_AREA,
1698
    .dom  = oa->areaid,
1699
    .id   = p->instance_id
1700
  };
1701

    
1702
  ospf_add_ric_tlv(p);
1703

    
1704
  ospf_originate_lsa(p, &lsa);
1705
}
1706

    
1707

    
1708
/*
1709
 *        Generic topology code
1710
 */
1711

    
1712
static inline int breaks_minlsinterval(struct top_hash_entry *en)
1713
{ return en && (en->lsa.age < LSA_MAXAGE) && (lsa_inst_age(en) < MINLSINTERVAL); }
1714

    
1715
void
1716
ospf_update_topology(struct ospf_proto *p)
1717
{
1718
  struct ospf_area *oa;
1719
  struct ospf_iface *ifa;
1720

    
1721
  WALK_LIST(oa, p->area_list)
1722
  {
1723
    if (oa->update_rt_lsa)
1724
    {
1725
      /*
1726
       * Generally, MinLSInterval is enforced in ospf_do_originate_lsa(), but
1727
       * origination of (prefix) router LSA is a special case. We do not want to
1728
       * prepare a new router LSA body and then postpone it in en->next_lsa_body
1729
       * for later origination, because there are side effects (updates of
1730
       * rt_pos_* and px_pos_* in ospf_iface structures) during that, which may
1731
       * confuse routing table calculation if executed after LSA body
1732
       * preparation but before final LSA origination (as rtcalc would use
1733
       * current rt_pos_* indexes but the old router LSA body).
1734
       *
1735
       * Here, we ensure that MinLSInterval is observed and we do not even try
1736
       * to originate these LSAs if it is not. Therefore, origination, when
1737
       * requested, will succeed unless there is also a seqnum wrapping, which
1738
       * is not a problem because in that case rtcalc is blocked by MaxAge.
1739
       */
1740

    
1741
      if (breaks_minlsinterval(oa->rt) || breaks_minlsinterval(oa->pxr_lsa))
1742
        continue;
1743

    
1744
      ospf_originate_rt_lsa(p, oa);
1745
      ospf_originate_prefix_rt_lsa(p, oa);
1746
      // ospf_originate_ri_lsa(p, oa);
1747
      oa->update_rt_lsa = 0;
1748
    }
1749
  }
1750

    
1751
  WALK_LIST(ifa, p->iface_list)
1752
  {
1753
    if (ifa->type == OSPF_IT_VLINK)
1754
      continue;
1755

    
1756
    if (ifa->update_link_lsa)
1757
    {
1758
      if ((ifa->state > OSPF_IS_LOOP) && !ifa->link_lsa_suppression)
1759
        ospf_originate_link_lsa(p, ifa);
1760
      else
1761
        ospf_flush2_lsa(p, &ifa->link_lsa);
1762

    
1763
      ifa->update_link_lsa = 0;
1764
    }
1765

    
1766
    if (ifa->update_net_lsa)
1767
    {
1768
      if ((ifa->state == OSPF_IS_DR) && (ifa->fadj > 0))
1769
      {
1770
        ospf_originate_net_lsa(p, ifa);
1771
        ospf_originate_prefix_net_lsa(p, ifa);
1772
      }
1773
      else
1774
      {
1775
        ospf_flush2_lsa(p, &ifa->net_lsa);
1776
        ospf_flush2_lsa(p, &ifa->pxn_lsa);
1777
      }
1778

    
1779
      ifa->update_net_lsa = 0;
1780
    }
1781
  }
1782
}
1783

    
1784

    
1785
static void
1786
ospf_top_ht_alloc(struct top_graph *f)
1787
{
1788
  f->hash_size = 1 << f->hash_order;
1789
  f->hash_mask = f->hash_size - 1;
1790
  if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
1791
    f->hash_entries_max = ~0;
1792
  else
1793
    f->hash_entries_max = f->hash_size HASH_HI_MARK;
1794
  if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
1795
    f->hash_entries_min = 0;
1796
  else
1797
    f->hash_entries_min = f->hash_size HASH_LO_MARK;
1798
  DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
1799
      f->hash_order, f->hash_size, f->hash_entries_min, f->hash_entries_max);
1800
  f->hash_table =
1801
    mb_alloc(f->pool, f->hash_size * sizeof(struct top_hash_entry *));
1802
  bzero(f->hash_table, f->hash_size * sizeof(struct top_hash_entry *));
1803
}
1804

    
1805
static inline void
1806
ospf_top_ht_free(struct top_hash_entry **h)
1807
{
1808
  mb_free(h);
1809
}
1810

    
1811
static inline u32
1812
ospf_top_hash_u32(u32 a)
1813
{
1814
  /* Shamelessly stolen from IP address hashing in ipv4.h */
1815
  a ^= a >> 16;
1816
  a ^= a << 10;
1817
  return a;
1818
}
1819

    
1820
static uint
1821
ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type)
1822
{
1823
  /* In OSPFv2, we don't know Router ID when looking for network LSAs.
1824
     In OSPFv3, we don't know LSA ID when looking for router LSAs.
1825
     In both cases, there is (usually) just one (or small number)
1826
     appropriate LSA, so we just clear unknown part of key. */
1827

    
1828
  return (((f->ospf2 && (type == LSA_T_NET)) ? 0 : ospf_top_hash_u32(rtrid)) +
1829
          ((!f->ospf2 && (type == LSA_T_RT)) ? 0 : ospf_top_hash_u32(lsaid)) +
1830
          type + domain) & f->hash_mask;
1831

    
1832
  /*
1833
  return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
1834
          type + areaid) & f->hash_mask;
1835
  */
1836
}
1837

    
1838
/**
1839
 * ospf_top_new - allocated new topology database
1840
 * @p: OSPF protocol instance
1841
 * @pool: pool for allocation
1842
 *
1843
 * This dynamically hashed structure is used for keeping LSAs. Mainly it is used
1844
 * for the LSA database of the OSPF protocol, but also for LSA retransmission
1845
 * and request lists of OSPF neighbors.
1846
 */
1847
struct top_graph *
1848
ospf_top_new(struct ospf_proto *p, pool *pool)
1849
{
1850
  struct top_graph *f;
1851

    
1852
  f = mb_allocz(pool, sizeof(struct top_graph));
1853
  f->pool = pool;
1854
  f->hash_slab = sl_new(f->pool, sizeof(struct top_hash_entry));
1855
  f->hash_order = HASH_DEF_ORDER;
1856
  ospf_top_ht_alloc(f);
1857
  f->hash_entries = 0;
1858
  f->hash_entries_min = 0;
1859
  f->ospf2 = ospf_is_v2(p);
1860
  return f;
1861
}
1862

    
1863
void
1864
ospf_top_free(struct top_graph *f)
1865
{
1866
  rfree(f->hash_slab);
1867
  ospf_top_ht_free(f->hash_table);
1868
  mb_free(f);
1869
}
1870

    
1871
static void
1872
ospf_top_rehash(struct top_graph *f, int step)
1873
{
1874
  struct top_hash_entry **n, **oldt, **newt, *e, *x;
1875
  uint oldn, oldh;
1876

    
1877
  oldn = f->hash_size;
1878
  oldt = f->hash_table;
1879
  DBG("re-hashing topology hash from order %d to %d\n", f->hash_order,
1880
      f->hash_order + step);
1881
  f->hash_order += step;
1882
  ospf_top_ht_alloc(f);
1883
  newt = f->hash_table;
1884

    
1885
  for (oldh = 0; oldh < oldn; oldh++)
1886
  {
1887
    e = oldt[oldh];
1888
    while (e)
1889
    {
1890
      x = e->next;
1891
      n = newt + ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type);
1892
      e->next = *n;
1893
      *n = e;
1894
      e = x;
1895
    }
1896
  }
1897
  ospf_top_ht_free(oldt);
1898
}
1899

    
1900
static struct top_hash_entry *
1901
ospf_hash_find_(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1902
{
1903
  struct top_hash_entry *e;
1904
  e = f->hash_table[ospf_top_hash(f, domain, lsa, rtr, type)];
1905

    
1906
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr ||
1907
               e->lsa_type != type || e->domain != domain))
1908
    e = e->next;
1909

    
1910
  return e;
1911
}
1912

    
1913
struct top_hash_entry *
1914
ospf_hash_find(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1915
{
1916
  struct top_hash_entry *e = ospf_hash_find_(f, domain, lsa, rtr, type);
1917

    
1918
  /* Hide hash entry with empty lsa_body */
1919
  return (e && e->lsa_body) ? e : NULL;
1920
}
1921

    
1922
/* In OSPFv2, lsa.id is the same as lsa.rt for router LSA. In OSPFv3, we don't know
1923
   lsa.id when looking for router LSAs. We return matching LSA with smallest lsa.id. */
1924
struct top_hash_entry *
1925
ospf_hash_find_rt(struct top_graph *f, u32 domain, u32 rtr)
1926
{
1927
  struct top_hash_entry *rv = NULL;
1928
  struct top_hash_entry *e;
1929
  /* We can put rtr for lsa.id to hash fn, it is ignored in OSPFv3 */
1930
  e = f->hash_table[ospf_top_hash(f, domain, rtr, rtr, LSA_T_RT)];
1931

    
1932
  while (e)
1933
  {
1934
    if (e->lsa.rt == rtr && e->lsa_type == LSA_T_RT && e->domain == domain && e->lsa_body)
1935
    {
1936
      if (f->ospf2 && (e->lsa.id == rtr))
1937
        return e;
1938
      if (!f->ospf2 && (!rv || e->lsa.id < rv->lsa.id))
1939
        rv = e;
1940
    }
1941
    e = e->next;
1942
  }
1943

    
1944
  return rv;
1945
}
1946

    
1947
/*
1948
 * ospf_hash_find_rt3_first() and ospf_hash_find_rt3_next() are used exclusively
1949
 * for lsa_walk_rt_init(), lsa_walk_rt(), therefore they skip MaxAge entries.
1950
 */
1951
static inline struct top_hash_entry *
1952
find_matching_rt3(struct top_hash_entry *e, u32 domain, u32 rtr)
1953
{
1954
  while (e && (e->lsa.rt != rtr || e->lsa_type != LSA_T_RT ||
1955
               e->domain != domain || e->lsa.age == LSA_MAXAGE))
1956
    e = e->next;
1957
  return e;
1958
}
1959

    
1960
struct top_hash_entry *
1961
ospf_hash_find_rt3_first(struct top_graph *f, u32 domain, u32 rtr)
1962
{
1963
  struct top_hash_entry *e;
1964
  e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)];
1965
  return find_matching_rt3(e, domain, rtr);
1966
}
1967

    
1968
struct top_hash_entry *
1969
ospf_hash_find_rt3_next(struct top_hash_entry *e)
1970
{
1971
  return find_matching_rt3(e->next, e->domain, e->lsa.rt);
1972
}
1973

    
1974
/* In OSPFv2, we don't know Router ID when looking for network LSAs.
1975
   There should be just one, so we find any match. */
1976
struct top_hash_entry *
1977
ospf_hash_find_net2(struct top_graph *f, u32 domain, u32 id)
1978
{
1979
  struct top_hash_entry *e;
1980
  e = f->hash_table[ospf_top_hash(f, domain, id, 0, LSA_T_NET)];
1981

    
1982
  while (e && (e->lsa.id != id || e->lsa_type != LSA_T_NET ||
1983
               e->domain != domain || e->lsa_body == NULL))
1984
    e = e->next;
1985

    
1986
  return e;
1987
}
1988

    
1989

    
1990
struct top_hash_entry *
1991
ospf_hash_get(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1992
{
1993
  struct top_hash_entry **ee;
1994
  struct top_hash_entry *e;
1995

    
1996
  ee = f->hash_table + ospf_top_hash(f, domain, lsa, rtr, type);
1997
  e = *ee;
1998

    
1999
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr ||
2000
               e->lsa_type != type || e->domain != domain))
2001
    e = e->next;
2002

    
2003
  if (e)
2004
    return e;
2005

    
2006
  e = sl_alloc(f->hash_slab);
2007
  bzero(e, sizeof(struct top_hash_entry));
2008

    
2009
  e->color = OUTSPF;
2010
  e->dist = LSINFINITY;
2011
  e->lsa.type_raw = type;
2012
  e->lsa.id = lsa;
2013
  e->lsa.rt = rtr;
2014
  e->lsa.sn = LSA_ZEROSEQNO;
2015
  e->lsa_type = type;
2016
  e->domain = domain;
2017
  e->next = *ee;
2018
  *ee = e;
2019
  if (f->hash_entries++ > f->hash_entries_max)
2020
    ospf_top_rehash(f, HASH_HI_STEP);
2021
  return e;
2022
}
2023

    
2024
void
2025
ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
2026
{
2027
  struct top_hash_entry **ee = f->hash_table +
2028
    ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type);
2029

    
2030
  while (*ee)
2031
  {
2032
    if (*ee == e)
2033
    {
2034
      *ee = e->next;
2035
      sl_free(f->hash_slab, e);
2036
      if (f->hash_entries-- < f->hash_entries_min)
2037
        ospf_top_rehash(f, -HASH_LO_STEP);
2038
      return;
2039
    }
2040
    ee = &((*ee)->next);
2041
  }
2042
  bug("ospf_hash_delete() called for invalid node");
2043
}
2044

    
2045
/*
2046
static void
2047
ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
2048
{
2049

2050
  struct ospf_lsa_rt *rt = NULL;
2051
  struct ospf_lsa_rt_link *rr = NULL;
2052
  struct ospf_lsa_net *ln = NULL;
2053
  u32 *rts = NULL;
2054
  u32 i, max;
2055

2056
  OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
2057
             he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
2058
             he->lsa.checksum, he->domain);
2059

2060

2061
  switch (he->lsa.type)
2062
    {
2063
    case LSA_T_RT:
2064
      rt = he->lsa_body;
2065
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
2066

2067
      for (i = 0; i < lsa_rt_items(&he->lsa); i++)
2068
        OSPF_TRACE(D_EVENTS, "  - %1x %-1R %-1R %5u",
2069
                   rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
2070
      break;
2071

2072
    case LSA_T_NET:
2073
      ln = he->lsa_body;
2074
      rts = (u32 *) (ln + 1);
2075

2076
      for (i = 0; i < lsa_net_items(&he->lsa); i++)
2077
        OSPF_TRACE(D_EVENTS, "  - %-1R", rts[i]);
2078
      break;
2079

2080
    default:
2081
      break;
2082
    }
2083
}
2084

2085
void
2086
ospf_top_dump(struct top_graph *f, struct proto *p)
2087
{
2088
  uint i;
2089
  OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
2090

2091
  for (i = 0; i < f->hash_size; i++)
2092
  {
2093
    struct top_hash_entry *e;
2094
    for (e = f->hash_table[i]; e != NULL; e = e->next)
2095
      ospf_dump_lsa(e, p);
2096
  }
2097
}
2098
*/