Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / topology.c @ a7a7372a

History | View | Annotate | Download (50.8 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 = now;
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 = now;
132
      lsasum_calculate(&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 = now;
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 == 0) && en->inst_time && ((en->inst_time + MINLSINTERVAL) > now))
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 is not universally true,
228
   * but it holds for all OSPFv2 types currently supported by BIRD.
229
   */
230

    
231
  if (ospf_is_v2(p))
232
    lsa_set_options(&en->lsa, lsa_opts);
233

    
234
  mb_free(en->lsa_body);
235
  en->lsa_body = lsa_body;
236
  en->lsa.length = sizeof(struct ospf_lsa_header) + lsa_blen;
237
  en->lsa.sn++;
238
  en->lsa.age = 0;
239
  en->init_age = 0;
240
  en->inst_time = now;
241
  lsasum_calculate(&en->lsa, en->lsa_body);
242

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

    
246
  ospf_flood_lsa(p, en, NULL);
247

    
248
  if (en->mode == LSA_M_BASIC)
249
    ospf_schedule_rtcalc(p);
250

    
251
  return 1;
252
}
253

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

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

    
278
  if (!SNODE_VALID(en))
279
    s_add_tail(&p->lsal, SNODE en);
280

    
281
  if (en->lsa_body == NULL)
282
    en->nf = lsa->nf;
283

    
284
  if (en->nf != lsa->nf)
285
  {
286
    log(L_ERR "%s: LSA ID collision for %I/%d",
287
        p->p.name, lsa->nf->fn.prefix, lsa->nf->fn.pxlen);
288

    
289
    en = NULL;
290
    goto drop;
291
  }
292

    
293
  if (en->mode != lsa->mode)
294
    en->mode = lsa->mode;
295

    
296
  if (en->next_lsa_body)
297
  {
298
    /* Ignore the new LSA if it is the same as the scheduled one */
299
    if ((lsa_blen == en->next_lsa_blen) &&
300
        !memcmp(lsa_body, en->next_lsa_body, lsa_blen) &&
301
        (!ospf_is_v2(p) || (lsa->opts == en->next_lsa_opts)))
302
      goto drop;
303

    
304
    /* Free scheduled LSA */
305
    mb_free(en->next_lsa_body);
306
    en->next_lsa_body = NULL;
307
    en->next_lsa_blen = 0;
308
    en->next_lsa_opts = 0;
309
  }
310

    
311
  /* Ignore the the new LSA if is the same as the current one */
312
  if ((en->lsa.age < LSA_MAXAGE) &&
313
      (lsa_length == en->lsa.length) &&
314
      !memcmp(lsa_body, en->lsa_body, lsa_blen) &&
315
      (!ospf_is_v2(p) || (lsa->opts == lsa_get_options(&en->lsa))))
316
    goto drop;
317

    
318
  lsa_body = lsab_flush(p);
319

    
320
  if (! ospf_do_originate_lsa(p, en, lsa_body, lsa_blen, lsa->opts))
321
  {
322
    OSPF_TRACE(D_EVENTS, "Postponing LSA: Type: %04x, Id: %R, Rt: %R",
323
               en->lsa_type, en->lsa.id, en->lsa.rt);
324

    
325
    en->next_lsa_body = lsa_body;
326
    en->next_lsa_blen = lsa_blen;
327
    en->next_lsa_opts = lsa->opts;
328
  }
329

    
330
  return en;
331

    
332
 drop:
333
  lsab_reset(p);
334
  return en;
335
}
336

    
337
static void
338
ospf_originate_next_lsa(struct ospf_proto *p, struct top_hash_entry *en)
339
{
340
  /* Called by ospf_update_lsadb() to handle scheduled origination */
341

    
342
  if (! ospf_do_originate_lsa(p, en, en->next_lsa_body, en->next_lsa_blen, en->next_lsa_opts))
343
    return;
344
  
345
  en->next_lsa_body = NULL;
346
  en->next_lsa_blen = 0;
347
  en->next_lsa_opts = 0;
348
}
349

    
350
static void
351
ospf_refresh_lsa(struct ospf_proto *p, struct top_hash_entry *en)
352
{
353
  /*
354
   * Called by ospf_update_lsadb() for periodic LSA refresh.
355
   *
356
   * We know that lsa.age < LSA_MAXAGE and lsa.rt is our router ID. We can also
357
   * assume that there is no scheduled LSA, because inst_time is deep in past,
358
   * therefore ospf_originate_next_lsa() called before would either succeed or
359
   * switched lsa.age to LSA_MAXAGE.
360
   */
361

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

    
365
  ASSERT(en->next_lsa_body == NULL);
366

    
367
  /* Handle wrapping sequence number */
368
  if (en->lsa.sn == LSA_MAXSEQNO)
369
  {
370
    /* Copy LSA body as next LSA to get automatic origination after flush is finished */
371
    en->next_lsa_blen = en->lsa.length - sizeof(struct ospf_lsa_header);
372
    en->next_lsa_body = mb_alloc(p->p.pool, en->next_lsa_blen);
373
    memcpy(en->next_lsa_body, en->lsa_body, en->next_lsa_blen);
374
    en->next_lsa_opts = ospf_is_v2(p) ? lsa_get_options(&en->lsa) : 0;
375

    
376
    en->lsa.age = LSA_MAXAGE;
377
    ospf_flood_lsa(p, en, NULL);
378
    return;
379
  }
380

    
381
  en->lsa.sn++;
382
  en->lsa.age = 0;
383
  en->init_age = 0;
384
  en->inst_time = now;
385
  lsasum_calculate(&en->lsa, en->lsa_body);
386
  ospf_flood_lsa(p, en, NULL);
387
}
388

    
389
/**
390
 * ospf_flush_lsa - flush LSA from OSPF domain
391
 * @p: OSPF protocol instance
392
 * @en: LSA entry to flush
393
 *
394
 * This function flushes @en from the OSPF domain by setting its age to
395
 * %LSA_MAXAGE and flooding it. That also triggers subsequent events in LSA
396
 * lifecycle leading to removal of the LSA from the LSA database (e.g. the LSA
397
 * content is freed when flushing is acknowledged by neighbors). The function
398
 * does nothing if the LSA is already being flushed. LSA entries are not
399
 * immediately removed when being flushed, the caller may assume that @en still
400
 * exists after the call. The function is the opposite of ospf_originate_lsa()
401
 * and is supposed to do the right thing even in cases of postponed
402
 * origination.
403
 */
404
void
405
ospf_flush_lsa(struct ospf_proto *p, struct top_hash_entry *en)
406
{
407
  OSPF_TRACE(D_EVENTS, "Flushing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
408
             en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
409

    
410
  if (en->next_lsa_body)
411
  {
412
    mb_free(en->next_lsa_body);
413
    en->next_lsa_body = NULL;
414
    en->next_lsa_blen = 0;
415
    en->next_lsa_opts = 0;
416
  }
417

    
418
  if (en->lsa.age == LSA_MAXAGE)
419
    return;
420

    
421
  en->lsa.age = LSA_MAXAGE;
422
  ospf_flood_lsa(p, en, NULL);
423

    
424
  if (en->mode == LSA_M_BASIC)
425
    ospf_schedule_rtcalc(p);
426

    
427
  en->mode = LSA_M_BASIC;
428
}
429

    
430
static void
431
ospf_clear_lsa(struct ospf_proto *p, struct top_hash_entry *en)
432
{
433
  /*
434
   * Called by ospf_update_lsadb() as part of LSA flushing process.
435
   * Flushed LSA was acknowledged by neighbors and we can free its content.
436
   */
437

    
438
  if (en->lsa.sn == LSA_MAXSEQNO)
439
    en->lsa.sn = LSA_ZEROSEQNO;
440

    
441
  mb_free(en->lsa_body);
442
  en->lsa_body = NULL;
443
}
444

    
445
static void
446
ospf_remove_lsa(struct ospf_proto *p, struct top_hash_entry *en)
447
{
448
  /*
449
   * Called by ospf_update_lsadb() as part of LSA flushing process.
450
   * Both lsa_body and next_lsa_body are NULL.
451
   */
452

    
453
  s_rem_node(SNODE en);
454
  ospf_hash_delete(p->gr, en);
455
}
456

    
457
/**
458
 * ospf_update_lsadb - update LSA database
459
 * @p: OSPF protocol instance
460
 *
461
 * This function is periodicaly invoked from ospf_disp(). It does some periodic
462
 * or postponed processing related to LSA entries. It originates postponed LSAs
463
 * scheduled by ospf_originate_lsa(), It continues in flushing processes started
464
 * by ospf_flush_lsa(). It also periodically refreshs locally originated LSAs --
465
 * when the current instance is older %LSREFRESHTIME, a new instance is originated.
466
 * Finally, it also ages stored LSAs and flushes ones that reached %LSA_MAXAGE.
467
 *
468
 * The RFC 2328 says that a router should periodically check checksums of all
469
 * stored LSAs to detect hardware problems. This is not implemented.
470
 */
471
void
472
ospf_update_lsadb(struct ospf_proto *p)
473
{
474
  struct top_hash_entry *en, *nxt;
475
  bird_clock_t real_age;
476

    
477
  WALK_SLIST_DELSAFE(en, nxt, p->lsal)
478
  {
479
    if (en->next_lsa_body)
480
      ospf_originate_next_lsa(p, en);
481

    
482
    real_age = en->init_age + (now - en->inst_time);
483

    
484
    if (en->lsa.age == LSA_MAXAGE)
485
    {
486
      if (en->lsa_body && (p->padj == 0) && (en->ret_count == 0))
487
        ospf_clear_lsa(p, en);
488

    
489
      if ((en->lsa_body == NULL) && (en->next_lsa_body == NULL) &&
490
          ((en->lsa.rt != p->router_id) || (real_age >= LSA_MAXAGE)))
491
        ospf_remove_lsa(p, en);
492

    
493
      continue;
494
    }
495

    
496
    if ((en->lsa.rt == p->router_id) && (real_age >= LSREFRESHTIME))
497
    {
498
      ospf_refresh_lsa(p, en);
499
      continue;
500
    }
501

    
502
    if (real_age >= LSA_MAXAGE)
503
    {
504
      ospf_flush_lsa(p, en);
505
      continue;
506
    }
507

    
508
    en->lsa.age = real_age;
509
  }
510
}
511

    
512

    
513
static inline u32
514
ort_to_lsaid(struct ospf_proto *p, ort *nf)
515
{
516
  /*
517
   * In OSPFv2, We have to map IP prefixes to u32 in such manner that resulting
518
   * u32 interpreted as IP address is a member of given prefix. Therefore, /32
519
   * prefix have to be mapped on itself.  All received prefixes have to be
520
   * mapped on different u32s.
521
   *
522
   * We have an assumption that if there is nontrivial (non-/32) network prefix,
523
   * then there is not /32 prefix for the first and the last IP address of the
524
   * network (these are usually reserved, therefore it is not an important
525
   * restriction).  The network prefix is mapped to the first or the last IP
526
   * address in the manner that disallow collisions - we use the IP address that
527
   * cannot be used by the parent prefix.
528
   *
529
   * For example:
530
   * 192.168.0.0/24 maps to 192.168.0.255
531
   * 192.168.1.0/24 maps to 192.168.1.0
532
   * because 192.168.0.0 and 192.168.1.255 might be used by 192.168.0.0/23 .
533
   *
534
   * Appendig E of RFC 2328 suggests different algorithm, that tries to maximize
535
   * both compatibility and subnetting. But as it is not possible to have both
536
   * reliably and the suggested algorithm was unnecessary complicated and it
537
   * does crazy things like changing LSA ID for a network because different
538
   * network appeared, we choose a different way.
539
   *
540
   * In OSPFv3, it is simpler. There is not a requirement for membership of the
541
   * result in the input network, so we just use a hash-based unique ID of a
542
   * routing table entry for a route that originated given LSA. For ext-LSA, it
543
   * is an imported route in the nest's routing table (p->table). For summary-LSA,
544
   * it is a 'source' route in the protocol internal routing table (p->rtf).
545
   */
546

    
547
  if (ospf_is_v3(p))
548
    return nf->fn.uid;
549

    
550
  u32 id = ipa_to_u32(nf->fn.prefix);
551
  int pxlen = nf->fn.pxlen;
552

    
553
  if ((pxlen == 0) || (pxlen == 32))
554
    return id;
555

    
556
  if (id & (1 << (32 - pxlen)))
557
    return id;
558
  else
559
    return id | ~u32_mkmask(pxlen);
560
}
561

    
562

    
563
static void *
564
lsab_alloc(struct ospf_proto *p, uint size)
565
{
566
  uint offset = p->lsab_used;
567
  p->lsab_used += size;
568
  if (p->lsab_used > p->lsab_size)
569
  {
570
    p->lsab_size = MAX(p->lsab_used, 2 * p->lsab_size);
571
    p->lsab = p->lsab ? mb_realloc(p->lsab, p->lsab_size):
572
      mb_alloc(p->p.pool, p->lsab_size);
573
  }
574
  return ((byte *) p->lsab) + offset;
575
}
576

    
577
static inline void *
578
lsab_allocz(struct ospf_proto *p, uint size)
579
{
580
  void *r = lsab_alloc(p, size);
581
  bzero(r, size);
582
  return r;
583
}
584

    
585
static inline void *
586
lsab_flush(struct ospf_proto *p)
587
{
588
  void *r = mb_alloc(p->p.pool, p->lsab_used);
589
  memcpy(r, p->lsab, p->lsab_used);
590
  p->lsab_used = 0;
591
  return r;
592
}
593

    
594
static inline void
595
lsab_reset(struct ospf_proto *p)
596
{
597
  p->lsab_used = 0;
598
}
599

    
600
static inline void *
601
lsab_offset(struct ospf_proto *p, uint offset)
602
{
603
  return ((byte *) p->lsab) + offset;
604
}
605

    
606
static inline void *
607
lsab_end(struct ospf_proto *p)
608
{
609
  return ((byte *) p->lsab) + p->lsab_used;
610
}
611

    
612

    
613
/*
614
 *        Router-LSA handling
615
 *        Type = LSA_T_RT
616
 */
617

    
618
static int
619
configured_stubnet(struct ospf_area *oa, struct ifa *a)
620
{
621
  /* Does not work for IA_PEER addresses, but it is not called on these */
622
  struct ospf_stubnet_config *sn;
623
  WALK_LIST(sn, oa->ac->stubnet_list)
624
  {
625
    if (sn->summary)
626
    {
627
      if (ipa_in_net(a->prefix, sn->px.addr, sn->px.len) && (a->pxlen >= sn->px.len))
628
        return 1;
629
    }
630
    else
631
    {
632
      if (ipa_equal(a->prefix, sn->px.addr) && (a->pxlen == sn->px.len))
633
        return 1;
634
    }
635
  }
636

    
637
  return 0;
638
}
639

    
640
static int
641
bcast_net_active(struct ospf_iface *ifa)
642
{
643
  struct ospf_neighbor *neigh;
644

    
645
  if (ifa->state == OSPF_IS_WAITING)
646
    return 0;
647

    
648
  WALK_LIST(neigh, ifa->neigh_list)
649
  {
650
    if (neigh->state == NEIGHBOR_FULL)
651
    {
652
      if (neigh->rid == ifa->drid)
653
        return 1;
654

    
655
      if (ifa->state == OSPF_IS_DR)
656
        return 1;
657
    }
658
  }
659

    
660
  return 0;
661
}
662

    
663
static inline u32
664
get_rt_options(struct ospf_proto *p, struct ospf_area *oa, int bitv)
665
{
666
  u32 opts = 0;
667

    
668
  if (p->areano > 1)
669
    opts |= OPT_RT_B;
670

    
671
  if ((p->areano > 1) && oa_is_nssa(oa) && oa->ac->translator)
672
    opts |= OPT_RT_NT;
673

    
674
  if (p->asbr && !oa_is_stub(oa))
675
    opts |= OPT_RT_E;
676

    
677
  if (bitv)
678
    opts |= OPT_RT_V;
679

    
680
  return opts;
681
}
682

    
683
static inline void
684
add_rt2_lsa_link(struct ospf_proto *p, u8 type, u32 id, u32 data, u16 metric)
685
{
686
  struct ospf_lsa_rt2_link *ln = lsab_alloc(p, sizeof(struct ospf_lsa_rt2_link));
687
  ln->type = type;
688
  ln->id = id;
689
  ln->data = data;
690
  ln->metric = metric;
691
  ln->no_tos = 0;
692
}
693

    
694
static void
695
prepare_rt2_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
696
{
697
  struct ospf_iface *ifa;
698
  int i = 0, bitv = 0;
699
  struct ospf_neighbor *neigh;
700

    
701
  ASSERT(p->lsab_used == 0);
702
  lsab_allocz(p, sizeof(struct ospf_lsa_rt));
703
  /* ospf_lsa_rt header will be filled later */
704

    
705
  WALK_LIST(ifa, p->iface_list)
706
  {
707
    int net_lsa = 0;
708
    u32 link_cost = p->stub_router ? 0xffff : ifa->cost;
709

    
710
    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
711
        (!EMPTY_LIST(ifa->neigh_list)))
712
    {
713
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
714
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
715
        bitv = 1;
716
    }
717

    
718
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
719
      continue;
720

    
721
    ifa->rt_pos_beg = i;
722

    
723
    /* RFC 2328 - 12.4.1.1-4 */
724
    switch (ifa->type)
725
    {
726
    case OSPF_IT_PTP:
727
    case OSPF_IT_PTMP:
728
      WALK_LIST(neigh, ifa->neigh_list)
729
        if (neigh->state == NEIGHBOR_FULL)
730
        {
731
          /*
732
           * ln->data should be ifa->iface_id in case of no/ptp
733
           * address (ifa->addr->flags & IA_PEER) on PTP link (see
734
           * RFC 2328 12.4.1.1.), but the iface ID value has no use,
735
           * while using IP address even in this case is here for
736
           * compatibility with some broken implementations that use
737
           * this address as a next-hop.
738
           */
739
          add_rt2_lsa_link(p, LSART_PTP, neigh->rid, ipa_to_u32(ifa->addr->ip), link_cost);
740
          i++;
741
        }
742
      break;
743

    
744
    case OSPF_IT_BCAST:
745
    case OSPF_IT_NBMA:
746
      if (bcast_net_active(ifa))
747
      {
748
        add_rt2_lsa_link(p, LSART_NET, ipa_to_u32(ifa->drip), ipa_to_u32(ifa->addr->ip), link_cost);
749
        i++;
750
        net_lsa = 1;
751
      }
752
      break;
753

    
754
    case OSPF_IT_VLINK:
755
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
756
      if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
757
        add_rt2_lsa_link(p, LSART_VLNK, neigh->rid, ipa_to_u32(ifa->addr->ip), link_cost), i++;
758
      break;
759

    
760
    default:
761
      log("Unknown interface type %s", ifa->ifname);
762
      break;
763
    }
764

    
765
    ifa->rt_pos_end = i;
766

    
767
    /* Now we will originate stub area if there is no primary */
768
    if (net_lsa ||
769
        (ifa->type == OSPF_IT_VLINK) ||
770
        ((ifa->addr->flags & IA_PEER) && ! ifa->cf->stub) ||
771
        configured_stubnet(oa, ifa->addr))
772
      continue;
773

    
774
      /* Host or network stub entry */
775
    if ((ifa->addr->flags & IA_HOST) ||
776
        (ifa->state == OSPF_IS_LOOP) ||
777
        (ifa->type == OSPF_IT_PTMP))
778
      add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(ifa->addr->ip), 0xffffffff, 0);
779
    else 
780
      add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(ifa->addr->prefix), u32_mkmask(ifa->addr->pxlen), ifa->cost);
781
    i++;
782

    
783
    ifa->rt_pos_end = i;
784
  }
785

    
786
  struct ospf_stubnet_config *sn;
787
  WALK_LIST(sn, oa->ac->stubnet_list)
788
    if (!sn->hidden)
789
      add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(sn->px.addr), u32_mkmask(sn->px.len), sn->cost), i++;
790

    
791
  struct ospf_lsa_rt *rt = p->lsab;
792
  /* Store number of links in lower half of options */ 
793
  rt->options = get_rt_options(p, oa, bitv) | (u16) i;
794
}
795

    
796
static inline void
797
add_rt3_lsa_link(struct ospf_proto *p, u8 type, struct ospf_iface *ifa, u32 nif, u32 id)
798
{
799
  struct ospf_lsa_rt3_link *ln = lsab_alloc(p, sizeof(struct ospf_lsa_rt3_link));
800
  ln->type = type;
801
  ln->padding = 0;
802
  ln->metric = ifa->cost;
803
  ln->lif = ifa->iface_id;
804
  ln->nif = nif;
805
  ln->id = id;
806
}
807

    
808
static void
809
prepare_rt3_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
810
{
811
  struct ospf_iface *ifa;
812
  struct ospf_neighbor *neigh;
813
  int bitv = 0;
814
  int i = 0;
815

    
816
  ASSERT(p->lsab_used == 0);
817
  lsab_allocz(p, sizeof(struct ospf_lsa_rt));
818
  /* ospf_lsa_rt header will be filled later */
819

    
820
  WALK_LIST(ifa, p->iface_list)
821
  {
822
    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
823
        (!EMPTY_LIST(ifa->neigh_list)))
824
    {
825
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
826
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
827
        bitv = 1;
828
    }
829

    
830
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
831
      continue;
832

    
833
    ifa->rt_pos_beg = i;
834

    
835
    /* RFC 5340 - 4.4.3.2 */
836
    switch (ifa->type)
837
    {
838
    case OSPF_IT_PTP:
839
    case OSPF_IT_PTMP:
840
      WALK_LIST(neigh, ifa->neigh_list)
841
        if (neigh->state == NEIGHBOR_FULL)
842
          add_rt3_lsa_link(p, LSART_PTP, ifa, neigh->iface_id, neigh->rid), i++;
843
      break;
844

    
845
    case OSPF_IT_BCAST:
846
    case OSPF_IT_NBMA:
847
      if (bcast_net_active(ifa))
848
        add_rt3_lsa_link(p, LSART_NET, ifa, ifa->dr_iface_id, ifa->drid), i++;
849
      break;
850

    
851
    case OSPF_IT_VLINK:
852
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
853
      if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
854
        add_rt3_lsa_link(p, LSART_VLNK, ifa, neigh->iface_id, neigh->rid), i++;
855
      break;
856

    
857
    default:
858
      log("Unknown interface type %s", ifa->ifname);
859
      break;
860
    }
861

    
862
    ifa->rt_pos_end = i;
863
  }
864

    
865
  struct ospf_lsa_rt *rt = p->lsab;
866
  rt->options = get_rt_options(p, oa, bitv) | (oa->options & LSA_OPTIONS_MASK);
867
}
868

    
869
static void
870
ospf_originate_rt_lsa(struct ospf_proto *p, struct ospf_area *oa)
871
{
872
  struct ospf_new_lsa lsa = {
873
    .type = LSA_T_RT,
874
    .dom  = oa->areaid,
875
    .id   = ospf_is_v2(p) ? p->router_id : 0,
876
    .opts = oa->options
877
  };
878

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

    
881
  if (ospf_is_v2(p))
882
    prepare_rt2_lsa_body(p, oa);
883
  else
884
    prepare_rt3_lsa_body(p, oa);
885

    
886
  oa->rt = ospf_originate_lsa(p, &lsa);
887
}
888

    
889

    
890
/*
891
 *        Net-LSA handling
892
 *        Type = LSA_T_NET
893
 */
894

    
895
static void
896
prepare_net2_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
897
{
898
  struct ospf_lsa_net *net;
899
  struct ospf_neighbor *n;
900
  int nodes = ifa->fadj + 1;
901
  u16 i = 1;
902

    
903
  ASSERT(p->lsab_used == 0);
904
  net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes);
905

    
906
  net->optx = u32_mkmask(ifa->addr->pxlen);
907
  net->routers[0] = p->router_id;
908

    
909
  WALK_LIST(n, ifa->neigh_list)
910
  {
911
    if (n->state == NEIGHBOR_FULL)
912
    {
913
      net->routers[i] = n->rid;
914
      i++;
915
    }
916
  }
917
  ASSERT(i == nodes);
918
}
919

    
920
static void
921
prepare_net3_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
922
{
923
  struct ospf_lsa_net *net;
924
  int nodes = ifa->fadj + 1;
925
  u32 options = 0;
926
  u16 i = 1;
927

    
928
  ASSERT(p->lsab_used == 0);
929
  net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes);
930

    
931
  net->routers[0] = p->router_id;
932

    
933
  struct ospf_neighbor *n;
934
  WALK_LIST(n, ifa->neigh_list)
935
  {
936
    if (n->state == NEIGHBOR_FULL)
937
    {
938
      /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */
939

    
940
      struct top_hash_entry *en =
941
        ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK);
942

    
943
      if (en)
944
        options |= ((struct ospf_lsa_link *) en->lsa_body)->options;
945

    
946
      net->routers[i] = n->rid;
947
      i++;
948
    }
949
  }
950
  ASSERT(i == nodes);
951

    
952
  net->optx = options & LSA_OPTIONS_MASK;
953
}
954

    
955
static void
956
ospf_originate_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
957
{
958
  struct ospf_new_lsa lsa = {
959
    .type = LSA_T_NET,
960
    .dom  = ifa->oa->areaid,
961
    .id   = ospf_is_v2(p) ? ipa_to_u32(ifa->addr->ip) : ifa->iface_id,
962
    .opts = ifa->oa->options,
963
    .ifa  = ifa
964
  };
965

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

    
968
  if (ospf_is_v2(p))
969
    prepare_net2_lsa_body(p, ifa);
970
  else
971
    prepare_net3_lsa_body(p, ifa);
972

    
973
  ifa->net_lsa = ospf_originate_lsa(p, &lsa);
974
}
975

    
976

    
977
/*
978
 *        (Net|Rt)-summary-LSA handling
979
 *        (a.k.a. Inter-Area-(Prefix|Router)-LSA)
980
 *        Type = LSA_T_SUM_NET, LSA_T_SUM_RT
981
 */
982

    
983
static inline void
984
prepare_sum2_lsa_body(struct ospf_proto *p, uint pxlen, u32 metric)
985
{
986
  struct ospf_lsa_sum2 *sum;
987

    
988
  sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum2));
989
  sum->netmask = u32_mkmask(pxlen);
990
  sum->metric = metric;
991
}
992

    
993
static inline void
994
prepare_sum3_net_lsa_body(struct ospf_proto *p, ort *nf, u32 metric)
995
{
996
  struct ospf_lsa_sum3_net *sum;
997

    
998
  sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_net) + IPV6_PREFIX_SPACE(nf->fn.pxlen));
999
  sum->metric = metric;
1000
  put_ipv6_prefix(sum->prefix, nf->fn.prefix, nf->fn.pxlen, 0, 0);
1001
}
1002

    
1003
static inline void
1004
prepare_sum3_rt_lsa_body(struct ospf_proto *p, u32 drid, u32 metric, u32 options)
1005
{
1006
  struct ospf_lsa_sum3_rt *sum;
1007

    
1008
  sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_rt));
1009
  sum->options = options;
1010
  sum->metric = metric;
1011
  sum->drid = drid;
1012
}
1013

    
1014
void
1015
ospf_originate_sum_net_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, int metric)
1016
{
1017
  struct ospf_new_lsa lsa = {
1018
    .type = LSA_T_SUM_NET,
1019
    .mode = LSA_M_RTCALC,
1020
    .dom  = oa->areaid,
1021
    .id   = ort_to_lsaid(p, nf),
1022
    .opts = oa->options,
1023
    .nf   = nf
1024
  };
1025

    
1026
  if (ospf_is_v2(p))
1027
    prepare_sum2_lsa_body(p, nf->fn.pxlen, metric);
1028
  else
1029
    prepare_sum3_net_lsa_body(p, nf, metric);
1030

    
1031
  ospf_originate_lsa(p, &lsa);
1032
}
1033

    
1034
void
1035
ospf_originate_sum_rt_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, int metric, u32 options)
1036
{
1037
  struct ospf_new_lsa lsa = {
1038
    .type = LSA_T_SUM_RT,
1039
    .mode = LSA_M_RTCALC,
1040
    .dom  = oa->areaid,
1041
    .id   = ipa_to_rid(nf->fn.prefix),        /* Router ID of ASBR, irrelevant for OSPFv3 */
1042
    .opts = oa->options
1043
  };
1044

    
1045
  if (ospf_is_v2(p))
1046
    prepare_sum2_lsa_body(p, 0, metric);
1047
  else
1048
    prepare_sum3_rt_lsa_body(p, lsa.id, metric, options & LSA_OPTIONS_MASK);
1049

    
1050
  ospf_originate_lsa(p, &lsa);
1051
}
1052

    
1053

    
1054
/*
1055
 *        AS-external-LSA and NSSA-LSA handling
1056
 *        Type = LSA_T_EXT, LSA_T_NSSA
1057
 */
1058

    
1059
static inline void
1060
prepare_ext2_lsa_body(struct ospf_proto *p, uint pxlen,
1061
                      u32 metric, u32 ebit, ip_addr fwaddr, u32 tag)
1062
{
1063
  struct ospf_lsa_ext2 *ext;
1064

    
1065
  ext = lsab_allocz(p, sizeof(struct ospf_lsa_ext2));
1066
  ext->metric = metric & LSA_METRIC_MASK;
1067
  ext->netmask = u32_mkmask(pxlen);
1068
  ext->fwaddr = ipa_to_u32(fwaddr);
1069
  ext->tag = tag;
1070

    
1071
  if (ebit)
1072
    ext->metric |= LSA_EXT2_EBIT;
1073
}
1074

    
1075
static inline void
1076
prepare_ext3_lsa_body(struct ospf_proto *p, ort *nf,
1077
                      u32 metric, u32 ebit, ip_addr fwaddr, u32 tag, int pbit)
1078
{
1079
  struct ospf_lsa_ext3 *ext;
1080
  int bsize = sizeof(struct ospf_lsa_ext3)
1081
    + IPV6_PREFIX_SPACE(nf->fn.pxlen)
1082
    + (ipa_nonzero(fwaddr) ? 16 : 0)
1083
    + (tag ? 4 : 0);
1084

    
1085
  ext = lsab_allocz(p, bsize);
1086
  ext->metric = metric & LSA_METRIC_MASK;
1087
  u32 *buf = ext->rest;
1088

    
1089
  buf = put_ipv6_prefix(buf, nf->fn.prefix, nf->fn.pxlen, pbit ? OPT_PX_P : 0, 0);
1090

    
1091
  if (ebit)
1092
    ext->metric |= LSA_EXT3_EBIT;
1093

    
1094
  if (ipa_nonzero(fwaddr))
1095
  {
1096
    ext->metric |= LSA_EXT3_FBIT;
1097
    buf = put_ipv6_addr(buf, fwaddr);
1098
  }
1099

    
1100
  if (tag)
1101
  {
1102
    ext->metric |= LSA_EXT3_TBIT;
1103
    *buf++ = tag;
1104
  }
1105
}
1106

    
1107
/**
1108
 * originate_ext_lsa - new route received from nest and filters
1109
 * @p: OSPF protocol instance
1110
 * @oa: ospf_area for which LSA is originated
1111
 * @nf: network prefix and mask
1112
 * @mode: the mode of the LSA (LSA_M_EXPORT or LSA_M_RTCALC)
1113
 * @metric: the metric of a route
1114
 * @ebit: E-bit for route metric (bool)
1115
 * @fwaddr: the forwarding address
1116
 * @tag: the route tag
1117
 * @pbit: P-bit for NSSA LSAs (bool), ignored for external LSAs
1118
 *
1119
 * If I receive a message that new route is installed, I try to originate an
1120
 * external LSA. If @oa is an NSSA area, NSSA-LSA is originated instead.
1121
 * @oa should not be a stub area. @src does not specify whether the LSA
1122
 * is external or NSSA, but it specifies the source of origination - 
1123
 * the export from ospf_rt_notify(), or the NSSA-EXT translation.
1124
 */
1125
void
1126
ospf_originate_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, u8 mode,
1127
                       u32 metric, u32 ebit, ip_addr fwaddr, u32 tag, int pbit)
1128
{
1129
  struct ospf_new_lsa lsa = {
1130
    .type = oa ? LSA_T_NSSA : LSA_T_EXT,
1131
    .mode = mode, /* LSA_M_EXPORT or LSA_M_RTCALC */
1132
    .dom  = oa ? oa->areaid : 0,
1133
    .id   = ort_to_lsaid(p, nf),
1134
    .opts = oa ? (pbit ? OPT_P : 0) : OPT_E,
1135
    .nf   = nf
1136
  };
1137

    
1138
  if (ospf_is_v2(p))
1139
    prepare_ext2_lsa_body(p, nf->fn.pxlen, metric, ebit, fwaddr, tag);
1140
  else
1141
    prepare_ext3_lsa_body(p, nf, metric, ebit, fwaddr, tag, oa && pbit);
1142

    
1143
  ospf_originate_lsa(p, &lsa);
1144
}
1145

    
1146
static void
1147
ospf_flush_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf)
1148
{
1149
  struct top_hash_entry *en;
1150

    
1151
  u32 type = oa ? LSA_T_NSSA : LSA_T_EXT;
1152
  u32 dom = oa ? oa->areaid : 0;
1153
  u32 id = ort_to_lsaid(p, nf);
1154

    
1155
  en = ospf_hash_find(p->gr, dom, id, p->router_id, type);
1156

    
1157
  if (!en || (en->nf != nf))
1158
    return;
1159

    
1160
  ospf_flush_lsa(p, en);
1161
}
1162

    
1163
static inline int
1164
use_gw_for_fwaddr(struct ospf_proto *p, ip_addr gw, struct iface *iface)
1165
{
1166
  struct ospf_iface *ifa;
1167

    
1168
  if (ipa_zero(gw) || ipa_is_link_local(gw))
1169
    return 0;
1170

    
1171
  WALK_LIST(ifa, p->iface_list)
1172
    if ((ifa->iface == iface) &&
1173
        ((ifa->type == OSPF_IT_BCAST) || (ifa->type == OSPF_IT_NBMA)) &&
1174
        (!ospf_is_v2(p) || ipa_in_net(gw, ifa->addr->prefix, ifa->addr->pxlen)) &&
1175
        (!ifa->cf->stub))
1176
      return 1;
1177

    
1178
  return 0;
1179
}
1180

    
1181
static inline ip_addr
1182
find_surrogate_fwaddr(struct ospf_proto *p, struct ospf_area *oa)
1183
{
1184
  struct ospf_iface *ifa;
1185
  struct ifa *a, *cur_addr = NULL;
1186
  int np, cur_np = 0;
1187

    
1188
  /* RFC 3101 2.3 - surrogate forwarding address selection */
1189

    
1190
  WALK_LIST(ifa, p->iface_list)
1191
  {
1192
    if ((ifa->oa != oa) ||
1193
        (ifa->type == OSPF_IT_VLINK))
1194
      continue;
1195

    
1196
    if (ospf_is_v2(p))
1197
    {
1198
      a = ifa->addr;
1199
      if (a->flags & IA_PEER)
1200
        continue;
1201

    
1202
      np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1);
1203
      if (np > cur_np)
1204
      {
1205
        cur_addr = a;
1206
        cur_np = np;
1207
      }
1208
    }
1209
    else /* OSPFv3 */
1210
    {
1211
      WALK_LIST(a, ifa->iface->addrs)
1212
      {
1213
        if ((a->flags & IA_SECONDARY) ||
1214
            (a->flags & IA_PEER) ||
1215
            (a->scope <= SCOPE_LINK))
1216
          continue;
1217

    
1218
        np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1);
1219
        if (np > cur_np)
1220
        {
1221
          cur_addr = a;
1222
          cur_np = np;
1223
        }
1224
      }
1225
    }
1226
  }
1227

    
1228
  return cur_addr ? cur_addr->ip : IPA_NONE;
1229
}
1230

    
1231
void
1232
ospf_rt_notify(struct proto *P, rtable *tbl UNUSED, net *n, rte *new, rte *old UNUSED, ea_list *ea)
1233
{
1234
  struct ospf_proto *p = (struct ospf_proto *) P;
1235
  struct ospf_area *oa = NULL;        /* non-NULL for NSSA-LSA */
1236
  ort *nf;
1237

    
1238
  /*
1239
   * There are several posibilities:
1240
   * 1) router in regular area - originate external LSA with global scope
1241
   * 2) router in NSSA area - originate area-specific NSSA-LSA
1242
   * 3) router in stub area - cannot export routes
1243
   * 4) area border router - same as (1), it is attached to backbone
1244
   */
1245

    
1246
  if ((p->areano == 1) && oa_is_nssa(HEAD(p->area_list)))
1247
    oa = HEAD(p->area_list);
1248

    
1249
  if (!new)
1250
  {
1251
    nf = (ort *) fib_find(&p->rtf, &n->n.prefix, n->n.pxlen);
1252

    
1253
    if (!nf || !nf->external_rte)
1254
      return;
1255

    
1256
    ospf_flush_ext_lsa(p, oa, nf);
1257
    nf->external_rte = 0;
1258

    
1259
    /* Old external route might blocked some NSSA translation */
1260
    if ((p->areano > 1) && rt_is_nssa(nf) && nf->n.oa->translate)
1261
      ospf_schedule_rtcalc(p);
1262

    
1263
    return;
1264
  }
1265

    
1266
  ASSERT(p->asbr);
1267

    
1268
  /* Get route attributes */
1269
  rta *a = new->attrs;
1270
  u32 m1 = ea_get_int(ea, EA_OSPF_METRIC1, LSINFINITY);
1271
  u32 m2 = ea_get_int(ea, EA_OSPF_METRIC2, 10000);
1272
  int ebit = (m1 == LSINFINITY);
1273
  u32 metric = ebit ? m2 : m1;
1274
  u32 tag = ea_get_int(ea, EA_OSPF_TAG, 0);
1275
  ip_addr fwd = IPA_NONE;
1276

    
1277

    
1278
  if ((a->dest == RTD_ROUTER) && use_gw_for_fwaddr(p, a->gw, a->iface))
1279
    fwd = a->gw;
1280

    
1281
  /* NSSA-LSA with P-bit set must have non-zero forwarding address */
1282
  if (oa && ipa_zero(fwd))
1283
  {
1284
    fwd = find_surrogate_fwaddr(p, oa);
1285

    
1286
    if (ipa_zero(fwd))
1287
    {
1288
      log(L_ERR "%s: Cannot find forwarding address for NSSA-LSA %I/%d",
1289
          p->p.name, n->n.prefix, n->n.pxlen);
1290
      return;
1291
    }
1292
  }
1293

    
1294
  nf = (ort *) fib_get(&p->rtf, &n->n.prefix, n->n.pxlen);
1295
  ospf_originate_ext_lsa(p, oa, nf, LSA_M_EXPORT, metric, ebit, fwd, tag, 1);
1296
  nf->external_rte = 1;
1297
}
1298

    
1299

    
1300
/*
1301
 *        Link-LSA handling (assume OSPFv3)
1302
 *        Type = LSA_T_LINK
1303
 */
1304

    
1305
static inline void
1306
lsab_put_prefix(struct ospf_proto *p, ip_addr prefix, u32 pxlen, u32 cost)
1307
{
1308
  void *buf = lsab_alloc(p, IPV6_PREFIX_SPACE(pxlen));
1309
  u8 flags = (pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
1310
  put_ipv6_prefix(buf, prefix, pxlen, flags, cost);
1311
}
1312

    
1313
static void
1314
prepare_link_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
1315
{
1316
  struct ospf_lsa_link *ll;
1317
  int i = 0;
1318

    
1319
  ASSERT(p->lsab_used == 0);
1320
  ll = lsab_allocz(p, sizeof(struct ospf_lsa_link));
1321
  ll->options = ifa->oa->options | (ifa->priority << 24);
1322
  ll->lladdr = ifa->addr->ip;
1323
  ll = NULL; /* buffer might be reallocated later */
1324

    
1325
  struct ifa *a;
1326
  WALK_LIST(a, ifa->iface->addrs)
1327
  {
1328
    if ((a->flags & IA_SECONDARY) ||
1329
        (a->scope < SCOPE_SITE))
1330
      continue;
1331

    
1332
    lsab_put_prefix(p, a->prefix, a->pxlen, 0);
1333
    i++;
1334
  }
1335

    
1336
  ll = p->lsab;
1337
  ll->pxcount = i;
1338
}
1339

    
1340
static void
1341
ospf_originate_link_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
1342
{
1343
  if (ospf_is_v2(p))
1344
    return;
1345

    
1346
  struct ospf_new_lsa lsa = {
1347
    .type = LSA_T_LINK,
1348
    .dom  = ifa->iface_id,
1349
    .id   = ifa->iface_id,
1350
    .ifa  = ifa
1351
  };
1352

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

    
1355
  prepare_link_lsa_body(p, ifa);
1356

    
1357
  ifa->link_lsa = ospf_originate_lsa(p, &lsa);
1358
}
1359

    
1360

    
1361
/*
1362
 *        Prefix-Rt-LSA handling (assume OSPFv3)
1363
 *        Type = LSA_T_PREFIX, referred type = LSA_T_RT
1364
 */
1365

    
1366
static void
1367
prepare_prefix_rt_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
1368
{
1369
  struct ospf_config *cf = (struct ospf_config *) (p->p.cf);
1370
  struct ospf_iface *ifa;
1371
  struct ospf_lsa_prefix *lp;
1372
  int host_addr = 0;
1373
  int net_lsa;
1374
  int i = 0;
1375

    
1376
  ASSERT(p->lsab_used == 0);
1377
  lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix));
1378
  lp->ref_type = LSA_T_RT;
1379
  lp->ref_id = 0;
1380
  lp->ref_rt = p->router_id;
1381
  lp = NULL; /* buffer might be reallocated later */
1382

    
1383
  WALK_LIST(ifa, p->iface_list)
1384
  {
1385
    if ((ifa->oa != oa) || (ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
1386
      continue;
1387

    
1388
    ifa->px_pos_beg = i;
1389

    
1390
    if ((ifa->type == OSPF_IT_BCAST) ||
1391
        (ifa->type == OSPF_IT_NBMA))
1392
      net_lsa = bcast_net_active(ifa);
1393
    else
1394
      net_lsa = 0;
1395

    
1396
    struct ifa *a;
1397
    WALK_LIST(a, ifa->iface->addrs)
1398
    {
1399
      if ((a->flags & IA_SECONDARY) ||
1400
          (a->flags & IA_PEER) ||
1401
          (a->scope <= SCOPE_LINK))
1402
        continue;
1403

    
1404
      if (((a->pxlen < MAX_PREFIX_LENGTH) && net_lsa) ||
1405
          configured_stubnet(oa, a))
1406
        continue;
1407

    
1408
      if ((a->flags & IA_HOST) ||
1409
          (ifa->state == OSPF_IS_LOOP) ||
1410
          (ifa->type == OSPF_IT_PTMP))
1411
      {
1412
        lsab_put_prefix(p, a->ip, MAX_PREFIX_LENGTH, 0);
1413
        host_addr = 1;
1414
      }
1415
      else
1416
        lsab_put_prefix(p, a->prefix, a->pxlen, ifa->cost);
1417
      i++;
1418
    }
1419

    
1420
    ifa->px_pos_end = i;
1421
  }
1422

    
1423
  struct ospf_stubnet_config *sn;
1424
  WALK_LIST(sn, oa->ac->stubnet_list)
1425
    if (!sn->hidden)
1426
    {
1427
      lsab_put_prefix(p, sn->px.addr, sn->px.len, sn->cost);
1428
      if (sn->px.len == MAX_PREFIX_LENGTH)
1429
        host_addr = 1;
1430
      i++;
1431
    }
1432

    
1433
  /* If there are some configured vlinks, find some global address
1434
     (even from another area), which will be used as a vlink endpoint. */
1435
  if (!EMPTY_LIST(cf->vlink_list) && !host_addr)
1436
  {
1437
    WALK_LIST(ifa, p->iface_list)
1438
    {
1439
      if ((ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
1440
        continue;
1441

    
1442
      struct ifa *a;
1443
      WALK_LIST(a, ifa->iface->addrs)
1444
      {
1445
        if ((a->flags & IA_SECONDARY) || (a->scope <= SCOPE_LINK))
1446
          continue;
1447

    
1448
        /* Found some IP */
1449
        lsab_put_prefix(p, a->ip, MAX_PREFIX_LENGTH, 0);
1450
        i++;
1451
        goto done;
1452
      }
1453
    }
1454
  }
1455

    
1456
 done:
1457
  lp = p->lsab;
1458
  lp->pxcount = i;
1459
}
1460

    
1461
static void
1462
ospf_originate_prefix_rt_lsa(struct ospf_proto *p, struct ospf_area *oa)
1463
{
1464
  if (ospf_is_v2(p))
1465
    return;
1466

    
1467
  struct ospf_new_lsa lsa = {
1468
    .type = LSA_T_PREFIX,
1469
    .dom  = oa->areaid,
1470
    .id   = 0
1471
  };
1472

    
1473
  prepare_prefix_rt_lsa_body(p, oa);
1474

    
1475
  ospf_originate_lsa(p, &lsa);
1476
}
1477

    
1478

    
1479
/*
1480
 *        Prefix-Net-LSA handling (assume OSPFv3)
1481
 *        Type = LSA_T_PREFIX, referred type = LSA_T_NET
1482
 */
1483

    
1484
static inline int
1485
prefix_space(u32 *buf)
1486
{
1487
  int pxl = *buf >> 24;
1488
  return IPV6_PREFIX_SPACE(pxl);
1489
}
1490

    
1491
static inline int
1492
prefix_same(u32 *b1, u32 *b2)
1493
{
1494
  int pxl1 = *b1 >> 24;
1495
  int pxl2 = *b2 >> 24;
1496
  int pxs, i;
1497
  
1498
  if (pxl1 != pxl2)
1499
    return 0;
1500

    
1501
  pxs = IPV6_PREFIX_WORDS(pxl1);
1502
  for (i = 1; i < pxs; i++)
1503
    if (b1[i] != b2[i])
1504
      return 0;
1505

    
1506
  return 1;
1507
}
1508

    
1509
static inline u32 *
1510
prefix_advance(u32 *buf)
1511
{
1512
  int pxl = *buf >> 24;
1513
  return buf + IPV6_PREFIX_WORDS(pxl);
1514
}
1515

    
1516
/* FIXME eliminate items with LA bit set? see 4.4.3.9 */
1517
static void
1518
add_prefix(struct ospf_proto *p, u32 *px, int offset, int *pxc)
1519
{
1520
  u32 *pxl = lsab_offset(p, offset);
1521
  int i;
1522
  for (i = 0; i < *pxc; pxl = prefix_advance(pxl), i++)
1523
    if (prefix_same(px, pxl))
1524
    {
1525
      /* Options should be logically OR'ed together */
1526
      *pxl |= (*px & 0x00FF0000);
1527
      return;
1528
    }
1529

    
1530
  ASSERT(pxl == lsab_end(p));
1531

    
1532
  int pxspace = prefix_space(px);
1533
  pxl = lsab_alloc(p, pxspace);
1534
  memcpy(pxl, px, pxspace);
1535
  *pxl &= 0xFFFF0000;        /* Set metric to zero */
1536
  (*pxc)++;
1537
}
1538

    
1539
static void
1540
add_link_lsa(struct ospf_proto *p, struct ospf_lsa_link *ll, int offset, int *pxc)
1541
{
1542
  u32 *pxb = ll->rest;
1543
  int j;
1544

    
1545
  for (j = 0; j < ll->pxcount; pxb = prefix_advance(pxb), j++)
1546
  {
1547
    u8 pxlen = (pxb[0] >> 24);
1548
    u8 pxopts = (pxb[0] >> 16);
1549

    
1550
    /* Skip NU or LA prefixes */
1551
    if (pxopts & (OPT_PX_NU | OPT_PX_LA))
1552
      continue;
1553

    
1554
    /* Skip link-local prefixes */
1555
    if ((pxlen >= 10) && ((pxb[1] & 0xffc00000) == 0xfe800000))
1556
      continue;
1557

    
1558
    add_prefix(p, pxb, offset, pxc);
1559
  }
1560
}
1561

    
1562
static void
1563
prepare_prefix_net_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
1564
{
1565
  struct ospf_lsa_prefix *lp;
1566
  struct ospf_neighbor *n;
1567
  struct top_hash_entry *en;
1568
  int pxc, offset;
1569

    
1570
  ASSERT(p->lsab_used == 0);
1571
  lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix));
1572
  lp->ref_type = LSA_T_NET;
1573
  lp->ref_id = ifa->net_lsa->lsa.id;
1574
  lp->ref_rt = p->router_id;
1575
  lp = NULL; /* buffer might be reallocated later */
1576

    
1577
  pxc = 0;
1578
  offset = p->lsab_used;
1579

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

    
1584
  WALK_LIST(n, ifa->neigh_list)
1585
    if ((n->state == NEIGHBOR_FULL) &&
1586
              (en = ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK)))
1587
      add_link_lsa(p, en->lsa_body, offset, &pxc);
1588

    
1589
  lp = p->lsab;
1590
  lp->pxcount = pxc;
1591
}
1592

    
1593
static void
1594
ospf_originate_prefix_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
1595
{
1596
  if (ospf_is_v2(p))
1597
    return;
1598

    
1599
  struct ospf_new_lsa lsa = {
1600
    .type = LSA_T_PREFIX,
1601
    .dom  = ifa->oa->areaid,
1602
    .id   = ifa->iface_id,
1603
    .ifa  = ifa
1604
  };
1605

    
1606
  prepare_prefix_net_lsa_body(p, ifa);
1607

    
1608
  ifa->pxn_lsa = ospf_originate_lsa(p, &lsa);
1609
}
1610

    
1611
static inline int breaks_minlsinterval(struct top_hash_entry *en)
1612
{ return en && (en->lsa.age < LSA_MAXAGE) && ((en->inst_time + MINLSINTERVAL) > now); }
1613

    
1614
void
1615
ospf_update_topology(struct ospf_proto *p)
1616
{
1617
  struct ospf_area *oa;
1618
  struct ospf_iface *ifa;
1619

    
1620
  WALK_LIST(oa, p->area_list)
1621
  {
1622
    if (oa->update_rt_lsa)
1623
    {
1624
      /*
1625
       * Generally, MinLSInterval is enforced in ospf_do_originate_lsa(), but
1626
       * origination of (prefix) router LSA is a special case. We do not want to
1627
       * prepare a new router LSA body and then postpone it in en->next_lsa_body
1628
       * for later origination, because there are side effects (updates of
1629
       * rt_pos_* and px_pos_* in ospf_iface structures) during that, which may
1630
       * confuse routing table calculation if executed after LSA body
1631
       * preparation but before final LSA origination (as rtcalc would use
1632
       * current rt_pos_* indexes but the old router LSA body).
1633
       *
1634
       * Here, we ensure that MinLSInterval is observed and we do not even try
1635
       * to originate these LSAs if it is not. Therefore, origination, when
1636
       * requested, will succeed unless there is also a seqnum wrapping, which
1637
       * is not a problem because in that case rtcalc is blocked by MaxAge.
1638
       */
1639

    
1640
      if (breaks_minlsinterval(oa->rt) || breaks_minlsinterval(oa->pxr_lsa))
1641
        continue;
1642

    
1643
      ospf_originate_rt_lsa(p, oa);
1644
      ospf_originate_prefix_rt_lsa(p, oa);
1645
      oa->update_rt_lsa = 0;
1646
    }
1647
  }
1648

    
1649
  WALK_LIST(ifa, p->iface_list)
1650
  {
1651
    if (ifa->type == OSPF_IT_VLINK)
1652
      continue;
1653

    
1654
    if (ifa->update_link_lsa)
1655
    {
1656
      if ((ifa->state > OSPF_IS_LOOP) && !ifa->link_lsa_suppression)
1657
        ospf_originate_link_lsa(p, ifa);
1658
      else
1659
        ospf_flush2_lsa(p, &ifa->link_lsa);
1660

    
1661
      ifa->update_link_lsa = 0;
1662
    }
1663

    
1664
    if (ifa->update_net_lsa)
1665
    {
1666
      if ((ifa->state == OSPF_IS_DR) && (ifa->fadj > 0))
1667
      {
1668
        ospf_originate_net_lsa(p, ifa);
1669
        ospf_originate_prefix_net_lsa(p, ifa);
1670
      }
1671
      else
1672
      {
1673
        ospf_flush2_lsa(p, &ifa->net_lsa);
1674
        ospf_flush2_lsa(p, &ifa->pxn_lsa);
1675
      }
1676

    
1677
      ifa->update_net_lsa = 0;
1678
    }
1679
  }
1680
}
1681

    
1682

    
1683
static void
1684
ospf_top_ht_alloc(struct top_graph *f)
1685
{
1686
  f->hash_size = 1 << f->hash_order;
1687
  f->hash_mask = f->hash_size - 1;
1688
  if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
1689
    f->hash_entries_max = ~0;
1690
  else
1691
    f->hash_entries_max = f->hash_size HASH_HI_MARK;
1692
  if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
1693
    f->hash_entries_min = 0;
1694
  else
1695
    f->hash_entries_min = f->hash_size HASH_LO_MARK;
1696
  DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
1697
      f->hash_order, f->hash_size, f->hash_entries_min, f->hash_entries_max);
1698
  f->hash_table =
1699
    mb_alloc(f->pool, f->hash_size * sizeof(struct top_hash_entry *));
1700
  bzero(f->hash_table, f->hash_size * sizeof(struct top_hash_entry *));
1701
}
1702

    
1703
static inline void
1704
ospf_top_ht_free(struct top_hash_entry **h)
1705
{
1706
  mb_free(h);
1707
}
1708

    
1709
static inline u32
1710
ospf_top_hash_u32(u32 a)
1711
{
1712
  /* Shamelessly stolen from IP address hashing in ipv4.h */
1713
  a ^= a >> 16;
1714
  a ^= a << 10;
1715
  return a;
1716
}
1717

    
1718
static uint
1719
ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type)
1720
{
1721
  /* In OSPFv2, we don't know Router ID when looking for network LSAs.
1722
     In OSPFv3, we don't know LSA ID when looking for router LSAs.
1723
     In both cases, there is (usually) just one (or small number)
1724
     appropriate LSA, so we just clear unknown part of key. */
1725

    
1726
  return (((f->ospf2 && (type == LSA_T_NET)) ? 0 : ospf_top_hash_u32(rtrid)) +
1727
          ((!f->ospf2 && (type == LSA_T_RT)) ? 0 : ospf_top_hash_u32(lsaid)) +
1728
          type + domain) & f->hash_mask;
1729

    
1730
  /*
1731
  return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
1732
          type + areaid) & f->hash_mask;
1733
  */
1734
}
1735

    
1736
/**
1737
 * ospf_top_new - allocated new topology database
1738
 * @p: OSPF protocol instance
1739
 * @pool: pool for allocation
1740
 *
1741
 * This dynamically hashed structure is used for keeping LSAs. Mainly it is used
1742
 * for the LSA database of the OSPF protocol, but also for LSA retransmission
1743
 * and request lists of OSPF neighbors.
1744
 */
1745
struct top_graph *
1746
ospf_top_new(struct ospf_proto *p, pool *pool)
1747
{
1748
  struct top_graph *f;
1749

    
1750
  f = mb_allocz(pool, sizeof(struct top_graph));
1751
  f->pool = pool;
1752
  f->hash_slab = sl_new(f->pool, sizeof(struct top_hash_entry));
1753
  f->hash_order = HASH_DEF_ORDER;
1754
  ospf_top_ht_alloc(f);
1755
  f->hash_entries = 0;
1756
  f->hash_entries_min = 0;
1757
  f->ospf2 = ospf_is_v2(p);
1758
  return f;
1759
}
1760

    
1761
void
1762
ospf_top_free(struct top_graph *f)
1763
{
1764
  rfree(f->hash_slab);
1765
  ospf_top_ht_free(f->hash_table);
1766
  mb_free(f);
1767
}
1768

    
1769
static void
1770
ospf_top_rehash(struct top_graph *f, int step)
1771
{
1772
  struct top_hash_entry **n, **oldt, **newt, *e, *x;
1773
  uint oldn, oldh;
1774

    
1775
  oldn = f->hash_size;
1776
  oldt = f->hash_table;
1777
  DBG("re-hashing topology hash from order %d to %d\n", f->hash_order,
1778
      f->hash_order + step);
1779
  f->hash_order += step;
1780
  ospf_top_ht_alloc(f);
1781
  newt = f->hash_table;
1782

    
1783
  for (oldh = 0; oldh < oldn; oldh++)
1784
  {
1785
    e = oldt[oldh];
1786
    while (e)
1787
    {
1788
      x = e->next;
1789
      n = newt + ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type);
1790
      e->next = *n;
1791
      *n = e;
1792
      e = x;
1793
    }
1794
  }
1795
  ospf_top_ht_free(oldt);
1796
}
1797

    
1798
struct top_hash_entry *
1799
ospf_hash_find(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1800
{
1801
  struct top_hash_entry *e;
1802
  e = f->hash_table[ospf_top_hash(f, domain, lsa, rtr, type)];
1803

    
1804
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr ||
1805
               e->lsa_type != type || e->domain != domain))
1806
    e = e->next;
1807

    
1808
  /* Hide hash entry with empty lsa_body */
1809
  return (e && e->lsa_body) ? e : NULL;
1810
}
1811

    
1812
/* In OSPFv2, lsa.id is the same as lsa.rt for router LSA. In OSPFv3, we don't know
1813
   lsa.id when looking for router LSAs. We return matching LSA with smallest lsa.id. */
1814
struct top_hash_entry *
1815
ospf_hash_find_rt(struct top_graph *f, u32 domain, u32 rtr)
1816
{
1817
  struct top_hash_entry *rv = NULL;
1818
  struct top_hash_entry *e;
1819
  /* We can put rtr for lsa.id to hash fn, it is ignored in OSPFv3 */
1820
  e = f->hash_table[ospf_top_hash(f, domain, rtr, rtr, LSA_T_RT)];
1821

    
1822
  while (e)
1823
  {
1824
    if (e->lsa.rt == rtr && e->lsa_type == LSA_T_RT && e->domain == domain && e->lsa_body)
1825
    {
1826
      if (f->ospf2 && (e->lsa.id == rtr))
1827
        return e;
1828
      if (!f->ospf2 && (!rv || e->lsa.id < rv->lsa.id))
1829
        rv = e;
1830
    }
1831
    e = e->next;
1832
  }
1833

    
1834
  return rv;
1835
}
1836

    
1837
/*
1838
 * ospf_hash_find_rt3_first() and ospf_hash_find_rt3_next() are used exclusively
1839
 * for lsa_walk_rt_init(), lsa_walk_rt(), therefore they skip MaxAge entries.
1840
 */
1841
static inline struct top_hash_entry *
1842
find_matching_rt3(struct top_hash_entry *e, u32 domain, u32 rtr)
1843
{
1844
  while (e && (e->lsa.rt != rtr || e->lsa_type != LSA_T_RT ||
1845
               e->domain != domain || e->lsa.age == LSA_MAXAGE))
1846
    e = e->next;
1847
  return e;
1848
}
1849

    
1850
struct top_hash_entry *
1851
ospf_hash_find_rt3_first(struct top_graph *f, u32 domain, u32 rtr)
1852
{
1853
  struct top_hash_entry *e;
1854
  e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)];
1855
  return find_matching_rt3(e, domain, rtr);
1856
}
1857

    
1858
struct top_hash_entry *
1859
ospf_hash_find_rt3_next(struct top_hash_entry *e)
1860
{
1861
  return find_matching_rt3(e->next, e->domain, e->lsa.rt);
1862
}
1863

    
1864
/* In OSPFv2, we don't know Router ID when looking for network LSAs.
1865
   There should be just one, so we find any match. */
1866
struct top_hash_entry *
1867
ospf_hash_find_net2(struct top_graph *f, u32 domain, u32 id)
1868
{
1869
  struct top_hash_entry *e;
1870
  e = f->hash_table[ospf_top_hash(f, domain, id, 0, LSA_T_NET)];
1871

    
1872
  while (e && (e->lsa.id != id || e->lsa_type != LSA_T_NET ||
1873
               e->domain != domain || e->lsa_body == NULL))
1874
    e = e->next;
1875

    
1876
  return e;
1877
}
1878

    
1879

    
1880
struct top_hash_entry *
1881
ospf_hash_get(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1882
{
1883
  struct top_hash_entry **ee;
1884
  struct top_hash_entry *e;
1885

    
1886
  ee = f->hash_table + ospf_top_hash(f, domain, lsa, rtr, type);
1887
  e = *ee;
1888

    
1889
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || 
1890
               e->lsa_type != type || e->domain != domain))
1891
    e = e->next;
1892

    
1893
  if (e)
1894
    return e;
1895

    
1896
  e = sl_alloc(f->hash_slab);
1897
  bzero(e, sizeof(struct top_hash_entry));
1898

    
1899
  e->color = OUTSPF;
1900
  e->dist = LSINFINITY;
1901
  e->lsa.type_raw = type;
1902
  e->lsa.id = lsa;
1903
  e->lsa.rt = rtr;
1904
  e->lsa.sn = LSA_ZEROSEQNO;
1905
  e->lsa_type = type;
1906
  e->domain = domain;
1907
  e->next = *ee;
1908
  *ee = e;
1909
  if (f->hash_entries++ > f->hash_entries_max)
1910
    ospf_top_rehash(f, HASH_HI_STEP);
1911
  return e;
1912
}
1913

    
1914
void
1915
ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
1916
{
1917
  struct top_hash_entry **ee = f->hash_table + 
1918
    ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type);
1919

    
1920
  while (*ee)
1921
  {
1922
    if (*ee == e)
1923
    {
1924
      *ee = e->next;
1925
      sl_free(f->hash_slab, e);
1926
      if (f->hash_entries-- < f->hash_entries_min)
1927
        ospf_top_rehash(f, -HASH_LO_STEP);
1928
      return;
1929
    }
1930
    ee = &((*ee)->next);
1931
  }
1932
  bug("ospf_hash_delete() called for invalid node");
1933
}
1934

    
1935
/*
1936
static void
1937
ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
1938
{
1939

1940
  struct ospf_lsa_rt *rt = NULL;
1941
  struct ospf_lsa_rt_link *rr = NULL;
1942
  struct ospf_lsa_net *ln = NULL;
1943
  u32 *rts = NULL;
1944
  u32 i, max;
1945

1946
  OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
1947
             he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
1948
             he->lsa.checksum, he->domain);
1949

1950

1951
  switch (he->lsa.type)
1952
    {
1953
    case LSA_T_RT:
1954
      rt = he->lsa_body;
1955
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
1956

1957
      for (i = 0; i < lsa_rt_items(&he->lsa); i++)
1958
        OSPF_TRACE(D_EVENTS, "  - %1x %-1R %-1R %5u",
1959
                   rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
1960
      break;
1961

1962
    case LSA_T_NET:
1963
      ln = he->lsa_body;
1964
      rts = (u32 *) (ln + 1);
1965

1966
      for (i = 0; i < lsa_net_items(&he->lsa); i++)
1967
        OSPF_TRACE(D_EVENTS, "  - %-1R", rts[i]);
1968
      break;
1969

1970
    default:
1971
      break;
1972
    }
1973
}
1974

1975
void
1976
ospf_top_dump(struct top_graph *f, struct proto *p)
1977
{
1978
  uint i;
1979
  OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
1980

1981
  for (i = 0; i < f->hash_size; i++)
1982
  {
1983
    struct top_hash_entry *e;
1984
    for (e = f->hash_table[i]; e != NULL; e = e->next)
1985
      ospf_dump_lsa(e, p);
1986
  }
1987
}
1988
*/