Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (51.3 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
  if (en->next_lsa_body)
408
  {
409
    mb_free(en->next_lsa_body);
410
    en->next_lsa_body = NULL;
411
    en->next_lsa_blen = 0;
412
    en->next_lsa_opts = 0;
413
  }
414

    
415
  if (en->lsa.age == LSA_MAXAGE)
416
    return;
417

    
418
  OSPF_TRACE(D_EVENTS, "Flushing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
419
             en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
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
   * The log message is for 'remove' - we hide empty LSAs from users.
437
   */
438

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

    
442
  if (en->lsa.sn == LSA_MAXSEQNO)
443
    en->lsa.sn = LSA_ZEROSEQNO;
444

    
445
  mb_free(en->lsa_body);
446
  en->lsa_body = NULL;
447
}
448

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

    
457
  s_rem_node(SNODE en);
458
  ospf_hash_delete(p->gr, en);
459
}
460

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

    
481
  WALK_SLIST_DELSAFE(en, nxt, p->lsal)
482
  {
483
    if (en->next_lsa_body)
484
      ospf_originate_next_lsa(p, en);
485

    
486
    real_age = en->init_age + (now - en->inst_time);
487

    
488
    if (en->lsa.age == LSA_MAXAGE)
489
    {
490
      if (en->lsa_body && (p->padj == 0) && (en->ret_count == 0))
491
        ospf_clear_lsa(p, en);
492

    
493
      if ((en->lsa_body == NULL) && (en->next_lsa_body == NULL) &&
494
          ((en->lsa.rt != p->router_id) || (real_age >= LSA_MAXAGE)))
495
        ospf_remove_lsa(p, en);
496

    
497
      continue;
498
    }
499

    
500
    if ((en->lsa.rt == p->router_id) && (real_age >= LSREFRESHTIME))
501
    {
502
      ospf_refresh_lsa(p, en);
503
      continue;
504
    }
505

    
506
    if (real_age >= LSA_MAXAGE)
507
    {
508
      ospf_flush_lsa(p, en);
509
      continue;
510
    }
511

    
512
    en->lsa.age = real_age;
513
  }
514
}
515

    
516

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

    
551
  if (ospf_is_v3(p))
552
    return nf->fn.uid;
553

    
554
  u32 id = ipa_to_u32(nf->fn.prefix);
555
  int pxlen = nf->fn.pxlen;
556

    
557
  if ((pxlen == 0) || (pxlen == 32))
558
    return id;
559

    
560
  if (id & (1 << (32 - pxlen)))
561
    return id;
562
  else
563
    return id | ~u32_mkmask(pxlen);
564
}
565

    
566

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

    
581
static inline void *
582
lsab_allocz(struct ospf_proto *p, uint size)
583
{
584
  void *r = lsab_alloc(p, size);
585
  bzero(r, size);
586
  return r;
587
}
588

    
589
static inline void *
590
lsab_flush(struct ospf_proto *p)
591
{
592
  void *r = mb_alloc(p->p.pool, p->lsab_used);
593
  memcpy(r, p->lsab, p->lsab_used);
594
  p->lsab_used = 0;
595
  return r;
596
}
597

    
598
static inline void
599
lsab_reset(struct ospf_proto *p)
600
{
601
  p->lsab_used = 0;
602
}
603

    
604
static inline void *
605
lsab_offset(struct ospf_proto *p, uint offset)
606
{
607
  return ((byte *) p->lsab) + offset;
608
}
609

    
610
static inline void *
611
lsab_end(struct ospf_proto *p)
612
{
613
  return ((byte *) p->lsab) + p->lsab_used;
614
}
615

    
616

    
617
/*
618
 *        Router-LSA handling
619
 *        Type = LSA_T_RT
620
 */
621

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

    
641
  return 0;
642
}
643

    
644
static int
645
bcast_net_active(struct ospf_iface *ifa)
646
{
647
  struct ospf_neighbor *neigh;
648

    
649
  if (ifa->state == OSPF_IS_WAITING)
650
    return 0;
651

    
652
  WALK_LIST(neigh, ifa->neigh_list)
653
  {
654
    if (neigh->state == NEIGHBOR_FULL)
655
    {
656
      if (neigh->rid == ifa->drid)
657
        return 1;
658

    
659
      if (ifa->state == OSPF_IS_DR)
660
        return 1;
661
    }
662
  }
663

    
664
  return 0;
665
}
666

    
667
static inline u32
668
get_rt_options(struct ospf_proto *p, struct ospf_area *oa, int bitv)
669
{
670
  u32 opts = 0;
671

    
672
  if (p->areano > 1)
673
    opts |= OPT_RT_B;
674

    
675
  if ((p->areano > 1) && oa_is_nssa(oa) && oa->ac->translator)
676
    opts |= OPT_RT_NT;
677

    
678
  if (p->asbr && !oa_is_stub(oa))
679
    opts |= OPT_RT_E;
680

    
681
  if (bitv)
682
    opts |= OPT_RT_V;
683

    
684
  return opts;
685
}
686

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

    
698
static void
699
prepare_rt2_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
700
{
701
  struct ospf_iface *ifa;
702
  int i = 0, bitv = 0;
703
  struct ospf_neighbor *neigh;
704

    
705
  ASSERT(p->lsab_used == 0);
706
  lsab_allocz(p, sizeof(struct ospf_lsa_rt));
707
  /* ospf_lsa_rt header will be filled later */
708

    
709
  WALK_LIST(ifa, p->iface_list)
710
  {
711
    int net_lsa = 0;
712
    u32 link_cost = p->stub_router ? 0xffff : ifa->cost;
713

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

    
722
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
723
      continue;
724

    
725
    ifa->rt_pos_beg = i;
726

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

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

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

    
764
    default:
765
      log(L_BUG "OSPF: Unknown interface type");
766
      break;
767
    }
768

    
769
    ifa->rt_pos_end = i;
770

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

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

    
787
    ifa->rt_pos_end = i;
788
  }
789

    
790
  struct ospf_stubnet_config *sn;
791
  WALK_LIST(sn, oa->ac->stubnet_list)
792
    if (!sn->hidden)
793
      add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(sn->px.addr), u32_mkmask(sn->px.len), sn->cost), i++;
794

    
795
  struct ospf_lsa_rt *rt = p->lsab;
796
  /* Store number of links in lower half of options */
797
  rt->options = get_rt_options(p, oa, bitv) | (u16) i;
798
}
799

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

    
812
static void
813
prepare_rt3_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
814
{
815
  struct ospf_iface *ifa;
816
  struct ospf_neighbor *neigh;
817
  int bitv = 0;
818
  int i = 0;
819

    
820
  ASSERT(p->lsab_used == 0);
821
  lsab_allocz(p, sizeof(struct ospf_lsa_rt));
822
  /* ospf_lsa_rt header will be filled later */
823

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

    
834
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
835
      continue;
836

    
837
    ifa->rt_pos_beg = i;
838

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

    
849
    case OSPF_IT_BCAST:
850
    case OSPF_IT_NBMA:
851
      if (bcast_net_active(ifa))
852
        add_rt3_lsa_link(p, LSART_NET, ifa, ifa->dr_iface_id, ifa->drid), i++;
853
      break;
854

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

    
861
    default:
862
      log(L_BUG "OSPF: Unknown interface type");
863
      break;
864
    }
865

    
866
    ifa->rt_pos_end = i;
867
  }
868

    
869
  struct ospf_lsa_rt *rt = p->lsab;
870
  rt->options = get_rt_options(p, oa, bitv) | (oa->options & LSA_OPTIONS_MASK);
871
}
872

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

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

    
885
  if (ospf_is_v2(p))
886
    prepare_rt2_lsa_body(p, oa);
887
  else
888
    prepare_rt3_lsa_body(p, oa);
889

    
890
  oa->rt = ospf_originate_lsa(p, &lsa);
891
}
892

    
893

    
894
/*
895
 *        Net-LSA handling
896
 *        Type = LSA_T_NET
897
 */
898

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

    
907
  ASSERT(p->lsab_used == 0);
908
  net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes);
909

    
910
  net->optx = u32_mkmask(ifa->addr->pxlen);
911
  net->routers[0] = p->router_id;
912

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

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

    
932
  ASSERT(p->lsab_used == 0);
933
  net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes);
934

    
935
  net->routers[0] = p->router_id;
936

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

    
944
      struct top_hash_entry *en =
945
        ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK);
946

    
947
      if (en)
948
        options |= ((struct ospf_lsa_link *) en->lsa_body)->options;
949

    
950
      net->routers[i] = n->rid;
951
      i++;
952
    }
953
  }
954
  ASSERT(i == nodes);
955

    
956
  net->optx = options & LSA_OPTIONS_MASK;
957
}
958

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

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

    
972
  if (ospf_is_v2(p))
973
    prepare_net2_lsa_body(p, ifa);
974
  else
975
    prepare_net3_lsa_body(p, ifa);
976

    
977
  ifa->net_lsa = ospf_originate_lsa(p, &lsa);
978
}
979

    
980

    
981
/*
982
 *        (Net|Rt)-summary-LSA handling
983
 *        (a.k.a. Inter-Area-(Prefix|Router)-LSA)
984
 *        Type = LSA_T_SUM_NET, LSA_T_SUM_RT
985
 */
986

    
987
static inline void
988
prepare_sum2_lsa_body(struct ospf_proto *p, uint pxlen, u32 metric)
989
{
990
  struct ospf_lsa_sum2 *sum;
991

    
992
  sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum2));
993
  sum->netmask = u32_mkmask(pxlen);
994
  sum->metric = metric;
995
}
996

    
997
static inline void
998
prepare_sum3_net_lsa_body(struct ospf_proto *p, ort *nf, u32 metric)
999
{
1000
  struct ospf_lsa_sum3_net *sum;
1001

    
1002
  sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_net) + IPV6_PREFIX_SPACE(nf->fn.pxlen));
1003
  sum->metric = metric;
1004
  put_ipv6_prefix(sum->prefix, nf->fn.prefix, nf->fn.pxlen, 0, 0);
1005
}
1006

    
1007
static inline void
1008
prepare_sum3_rt_lsa_body(struct ospf_proto *p, u32 drid, u32 metric, u32 options)
1009
{
1010
  struct ospf_lsa_sum3_rt *sum;
1011

    
1012
  sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_rt));
1013
  sum->options = options;
1014
  sum->metric = metric;
1015
  sum->drid = drid;
1016
}
1017

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

    
1030
  if (ospf_is_v2(p))
1031
    prepare_sum2_lsa_body(p, nf->fn.pxlen, metric);
1032
  else
1033
    prepare_sum3_net_lsa_body(p, nf, metric);
1034

    
1035
  ospf_originate_lsa(p, &lsa);
1036
}
1037

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

    
1049
  if (ospf_is_v2(p))
1050
    prepare_sum2_lsa_body(p, 0, metric);
1051
  else
1052
    prepare_sum3_rt_lsa_body(p, lsa.id, metric, options & LSA_OPTIONS_MASK);
1053

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

    
1057

    
1058
/*
1059
 *        AS-external-LSA and NSSA-LSA handling
1060
 *        Type = LSA_T_EXT, LSA_T_NSSA
1061
 */
1062

    
1063
static inline void
1064
prepare_ext2_lsa_body(struct ospf_proto *p, uint pxlen,
1065
                      u32 metric, u32 ebit, ip_addr fwaddr, u32 tag)
1066
{
1067
  struct ospf_lsa_ext2 *ext;
1068

    
1069
  ext = lsab_allocz(p, sizeof(struct ospf_lsa_ext2));
1070
  ext->metric = metric & LSA_METRIC_MASK;
1071
  ext->netmask = u32_mkmask(pxlen);
1072
  ext->fwaddr = ipa_to_u32(fwaddr);
1073
  ext->tag = tag;
1074

    
1075
  if (ebit)
1076
    ext->metric |= LSA_EXT2_EBIT;
1077
}
1078

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

    
1089
  ext = lsab_allocz(p, bsize);
1090
  ext->metric = metric & LSA_METRIC_MASK;
1091
  u32 *buf = ext->rest;
1092

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

    
1095
  if (ebit)
1096
    ext->metric |= LSA_EXT3_EBIT;
1097

    
1098
  if (ipa_nonzero(fwaddr))
1099
  {
1100
    ext->metric |= LSA_EXT3_FBIT;
1101
    buf = put_ipv6_addr(buf, fwaddr);
1102
  }
1103

    
1104
  if (tag)
1105
  {
1106
    ext->metric |= LSA_EXT3_TBIT;
1107
    *buf++ = tag;
1108
  }
1109
}
1110

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

    
1142
  if (ospf_is_v2(p))
1143
    prepare_ext2_lsa_body(p, nf->fn.pxlen, metric, ebit, fwaddr, tag);
1144
  else
1145
    prepare_ext3_lsa_body(p, nf, metric, ebit, fwaddr, tag, oa && pbit);
1146

    
1147
  ospf_originate_lsa(p, &lsa);
1148
}
1149

    
1150
static struct top_hash_entry *
1151
ospf_hash_find_(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type);
1152

    
1153
static void
1154
ospf_flush_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf)
1155
{
1156
  struct top_hash_entry *en;
1157

    
1158
  u32 type = oa ? LSA_T_NSSA : LSA_T_EXT;
1159
  u32 dom = oa ? oa->areaid : 0;
1160
  u32 id = ort_to_lsaid(p, nf);
1161

    
1162
  en = ospf_hash_find_(p->gr, dom, id, p->router_id, type);
1163

    
1164
  if (!en || (en->nf != nf))
1165
    return;
1166

    
1167
  ospf_flush_lsa(p, en);
1168
}
1169

    
1170
static inline int
1171
use_gw_for_fwaddr(struct ospf_proto *p, ip_addr gw, struct iface *iface)
1172
{
1173
  struct ospf_iface *ifa;
1174

    
1175
  if (ipa_zero(gw) || ipa_is_link_local(gw))
1176
    return 0;
1177

    
1178
  WALK_LIST(ifa, p->iface_list)
1179
    if ((ifa->iface == iface) &&
1180
        ((ifa->type == OSPF_IT_BCAST) || (ifa->type == OSPF_IT_NBMA)) &&
1181
        (!ospf_is_v2(p) || ipa_in_net(gw, ifa->addr->prefix, ifa->addr->pxlen)) &&
1182
        (!ifa->cf->stub))
1183
      return 1;
1184

    
1185
  return 0;
1186
}
1187

    
1188
static inline ip_addr
1189
find_surrogate_fwaddr(struct ospf_proto *p, struct ospf_area *oa)
1190
{
1191
  struct ospf_iface *ifa;
1192
  struct ifa *a, *cur_addr = NULL;
1193
  int np, cur_np = 0;
1194

    
1195
  /* RFC 3101 2.3 - surrogate forwarding address selection */
1196

    
1197
  WALK_LIST(ifa, p->iface_list)
1198
  {
1199
    if ((ifa->oa != oa) ||
1200
        (ifa->type == OSPF_IT_VLINK))
1201
      continue;
1202

    
1203
    if (ospf_is_v2(p))
1204
    {
1205
      a = ifa->addr;
1206
      if (a->flags & IA_PEER)
1207
        continue;
1208

    
1209
      np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1);
1210
      if (np > cur_np)
1211
      {
1212
        cur_addr = a;
1213
        cur_np = np;
1214
      }
1215
    }
1216
    else /* OSPFv3 */
1217
    {
1218
      WALK_LIST(a, ifa->iface->addrs)
1219
      {
1220
        if ((a->flags & IA_SECONDARY) ||
1221
            (a->flags & IA_PEER) ||
1222
            (a->scope <= SCOPE_LINK))
1223
          continue;
1224

    
1225
        np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1);
1226
        if (np > cur_np)
1227
        {
1228
          cur_addr = a;
1229
          cur_np = np;
1230
        }
1231
      }
1232
    }
1233
  }
1234

    
1235
  return cur_addr ? cur_addr->ip : IPA_NONE;
1236
}
1237

    
1238
void
1239
ospf_rt_notify(struct proto *P, rtable *tbl UNUSED, net *n, rte *new, rte *old UNUSED, ea_list *ea)
1240
{
1241
  struct ospf_proto *p = (struct ospf_proto *) P;
1242
  struct ospf_area *oa = NULL;        /* non-NULL for NSSA-LSA */
1243
  ort *nf;
1244

    
1245
  /*
1246
   * There are several posibilities:
1247
   * 1) router in regular area - originate external LSA with global scope
1248
   * 2) router in NSSA area - originate area-specific NSSA-LSA
1249
   * 3) router in stub area - cannot export routes
1250
   * 4) area border router - same as (1), it is attached to backbone
1251
   */
1252

    
1253
  if ((p->areano == 1) && oa_is_nssa(HEAD(p->area_list)))
1254
    oa = HEAD(p->area_list);
1255

    
1256
  if (!new)
1257
  {
1258
    nf = (ort *) fib_find(&p->rtf, &n->n.prefix, n->n.pxlen);
1259

    
1260
    if (!nf || !nf->external_rte)
1261
      return;
1262

    
1263
    ospf_flush_ext_lsa(p, oa, nf);
1264
    nf->external_rte = 0;
1265

    
1266
    /* Old external route might blocked some NSSA translation */
1267
    if ((p->areano > 1) && rt_is_nssa(nf) && nf->n.oa->translate)
1268
      ospf_schedule_rtcalc(p);
1269

    
1270
    return;
1271
  }
1272

    
1273
  ASSERT(p->asbr);
1274

    
1275
  /* Get route attributes */
1276
  rta *a = new->attrs;
1277
  u32 m1 = ea_get_int(ea, EA_OSPF_METRIC1, LSINFINITY);
1278
  u32 m2 = ea_get_int(ea, EA_OSPF_METRIC2, 10000);
1279
  int ebit = (m1 == LSINFINITY);
1280
  u32 metric = ebit ? m2 : m1;
1281
  u32 tag = ea_get_int(ea, EA_OSPF_TAG, 0);
1282
  ip_addr fwd = IPA_NONE;
1283

    
1284

    
1285
  if ((a->dest == RTD_ROUTER) && use_gw_for_fwaddr(p, a->gw, a->iface))
1286
    fwd = a->gw;
1287

    
1288
  /* NSSA-LSA with P-bit set must have non-zero forwarding address */
1289
  if (oa && ipa_zero(fwd))
1290
  {
1291
    fwd = find_surrogate_fwaddr(p, oa);
1292

    
1293
    if (ipa_zero(fwd))
1294
    {
1295
      log(L_ERR "%s: Cannot find forwarding address for NSSA-LSA %I/%d",
1296
          p->p.name, n->n.prefix, n->n.pxlen);
1297
      return;
1298
    }
1299
  }
1300

    
1301
  nf = (ort *) fib_get(&p->rtf, &n->n.prefix, n->n.pxlen);
1302
  ospf_originate_ext_lsa(p, oa, nf, LSA_M_EXPORT, metric, ebit, fwd, tag, 1);
1303
  nf->external_rte = 1;
1304
}
1305

    
1306

    
1307
/*
1308
 *        Link-LSA handling (assume OSPFv3)
1309
 *        Type = LSA_T_LINK
1310
 */
1311

    
1312
static inline void
1313
lsab_put_prefix(struct ospf_proto *p, ip_addr prefix, u32 pxlen, u32 cost)
1314
{
1315
  void *buf = lsab_alloc(p, IPV6_PREFIX_SPACE(pxlen));
1316
  u8 flags = (pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
1317
  put_ipv6_prefix(buf, prefix, pxlen, flags, cost);
1318
}
1319

    
1320
static void
1321
prepare_link_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
1322
{
1323
  struct ospf_lsa_link *ll;
1324
  int i = 0;
1325

    
1326
  ASSERT(p->lsab_used == 0);
1327
  ll = lsab_allocz(p, sizeof(struct ospf_lsa_link));
1328
  ll->options = ifa->oa->options | (ifa->priority << 24);
1329
  ll->lladdr = ipa_to_ip6(ifa->addr->ip);
1330
  ll = NULL; /* buffer might be reallocated later */
1331

    
1332
  struct ifa *a;
1333
  WALK_LIST(a, ifa->iface->addrs)
1334
  {
1335
    if ((a->flags & IA_SECONDARY) ||
1336
        (a->scope < SCOPE_SITE))
1337
      continue;
1338

    
1339
    lsab_put_prefix(p, a->prefix, a->pxlen, 0);
1340
    i++;
1341
  }
1342

    
1343
  ll = p->lsab;
1344
  ll->pxcount = i;
1345
}
1346

    
1347
static void
1348
ospf_originate_link_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
1349
{
1350
  if (ospf_is_v2(p))
1351
    return;
1352

    
1353
  struct ospf_new_lsa lsa = {
1354
    .type = LSA_T_LINK,
1355
    .dom  = ifa->iface_id,
1356
    .id   = ifa->iface_id,
1357
    .ifa  = ifa
1358
  };
1359

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

    
1362
  prepare_link_lsa_body(p, ifa);
1363

    
1364
  ifa->link_lsa = ospf_originate_lsa(p, &lsa);
1365
}
1366

    
1367

    
1368
/*
1369
 *        Prefix-Rt-LSA handling (assume OSPFv3)
1370
 *        Type = LSA_T_PREFIX, referred type = LSA_T_RT
1371
 */
1372

    
1373
static void
1374
prepare_prefix_rt_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
1375
{
1376
  struct ospf_config *cf = (struct ospf_config *) (p->p.cf);
1377
  struct ospf_iface *ifa;
1378
  struct ospf_lsa_prefix *lp;
1379
  int host_addr = 0;
1380
  int net_lsa;
1381
  int i = 0;
1382

    
1383
  ASSERT(p->lsab_used == 0);
1384
  lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix));
1385
  lp->ref_type = LSA_T_RT;
1386
  lp->ref_id = 0;
1387
  lp->ref_rt = p->router_id;
1388
  lp = NULL; /* buffer might be reallocated later */
1389

    
1390
  WALK_LIST(ifa, p->iface_list)
1391
  {
1392
    if ((ifa->oa != oa) || (ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
1393
      continue;
1394

    
1395
    ifa->px_pos_beg = i;
1396

    
1397
    if ((ifa->type == OSPF_IT_BCAST) ||
1398
        (ifa->type == OSPF_IT_NBMA))
1399
      net_lsa = bcast_net_active(ifa);
1400
    else
1401
      net_lsa = 0;
1402

    
1403
    struct ifa *a;
1404
    WALK_LIST(a, ifa->iface->addrs)
1405
    {
1406
      if ((a->flags & IA_SECONDARY) ||
1407
          (a->flags & IA_PEER) ||
1408
          (a->scope <= SCOPE_LINK))
1409
        continue;
1410

    
1411
      if (((a->pxlen < MAX_PREFIX_LENGTH) && net_lsa) ||
1412
          configured_stubnet(oa, a))
1413
        continue;
1414

    
1415
      if ((a->flags & IA_HOST) ||
1416
          (ifa->state == OSPF_IS_LOOP) ||
1417
          (ifa->type == OSPF_IT_PTMP))
1418
      {
1419
        lsab_put_prefix(p, a->ip, MAX_PREFIX_LENGTH, 0);
1420
        host_addr = 1;
1421
      }
1422
      else
1423
        lsab_put_prefix(p, a->prefix, a->pxlen, ifa->cost);
1424
      i++;
1425
    }
1426

    
1427
    ifa->px_pos_end = i;
1428
  }
1429

    
1430
  struct ospf_stubnet_config *sn;
1431
  WALK_LIST(sn, oa->ac->stubnet_list)
1432
    if (!sn->hidden)
1433
    {
1434
      lsab_put_prefix(p, sn->px.addr, sn->px.len, sn->cost);
1435
      if (sn->px.len == MAX_PREFIX_LENGTH)
1436
        host_addr = 1;
1437
      i++;
1438
    }
1439

    
1440
  /* If there are some configured vlinks, find some global address
1441
     (even from another area), which will be used as a vlink endpoint. */
1442
  if (!EMPTY_LIST(cf->vlink_list) && !host_addr)
1443
  {
1444
    WALK_LIST(ifa, p->iface_list)
1445
    {
1446
      if ((ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
1447
        continue;
1448

    
1449
      struct ifa *a;
1450
      WALK_LIST(a, ifa->iface->addrs)
1451
      {
1452
        if ((a->flags & IA_SECONDARY) || (a->scope <= SCOPE_LINK))
1453
          continue;
1454

    
1455
        /* Found some IP */
1456
        lsab_put_prefix(p, a->ip, MAX_PREFIX_LENGTH, 0);
1457
        i++;
1458
        goto done;
1459
      }
1460
    }
1461
  }
1462

    
1463
 done:
1464
  lp = p->lsab;
1465
  lp->pxcount = i;
1466
}
1467

    
1468
static void
1469
ospf_originate_prefix_rt_lsa(struct ospf_proto *p, struct ospf_area *oa)
1470
{
1471
  if (ospf_is_v2(p))
1472
    return;
1473

    
1474
  struct ospf_new_lsa lsa = {
1475
    .type = LSA_T_PREFIX,
1476
    .dom  = oa->areaid,
1477
    .id   = 0
1478
  };
1479

    
1480
  prepare_prefix_rt_lsa_body(p, oa);
1481

    
1482
  ospf_originate_lsa(p, &lsa);
1483
}
1484

    
1485

    
1486
/*
1487
 *        Prefix-Net-LSA handling (assume OSPFv3)
1488
 *        Type = LSA_T_PREFIX, referred type = LSA_T_NET
1489
 */
1490

    
1491
static inline int
1492
prefix_space(u32 *buf)
1493
{
1494
  int pxl = *buf >> 24;
1495
  return IPV6_PREFIX_SPACE(pxl);
1496
}
1497

    
1498
static inline int
1499
prefix_same(u32 *b1, u32 *b2)
1500
{
1501
  int pxl1 = *b1 >> 24;
1502
  int pxl2 = *b2 >> 24;
1503
  int pxs, i;
1504

    
1505
  if (pxl1 != pxl2)
1506
    return 0;
1507

    
1508
  pxs = IPV6_PREFIX_WORDS(pxl1);
1509
  for (i = 1; i < pxs; i++)
1510
    if (b1[i] != b2[i])
1511
      return 0;
1512

    
1513
  return 1;
1514
}
1515

    
1516
static inline u32 *
1517
prefix_advance(u32 *buf)
1518
{
1519
  int pxl = *buf >> 24;
1520
  return buf + IPV6_PREFIX_WORDS(pxl);
1521
}
1522

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

    
1537
  ASSERT(pxl == lsab_end(p));
1538

    
1539
  int pxspace = prefix_space(px);
1540
  pxl = lsab_alloc(p, pxspace);
1541
  memcpy(pxl, px, pxspace);
1542
  *pxl &= 0xFFFF0000;        /* Set metric to zero */
1543
  (*pxc)++;
1544
}
1545

    
1546
static void
1547
add_link_lsa(struct ospf_proto *p, struct ospf_lsa_link *ll, int offset, int *pxc)
1548
{
1549
  u32 *pxb = ll->rest;
1550
  int j;
1551

    
1552
  for (j = 0; j < ll->pxcount; pxb = prefix_advance(pxb), j++)
1553
  {
1554
    u8 pxlen = (pxb[0] >> 24);
1555
    u8 pxopts = (pxb[0] >> 16);
1556

    
1557
    /* Skip NU or LA prefixes */
1558
    if (pxopts & (OPT_PX_NU | OPT_PX_LA))
1559
      continue;
1560

    
1561
    /* Skip link-local prefixes */
1562
    if ((pxlen >= 10) && ((pxb[1] & 0xffc00000) == 0xfe800000))
1563
      continue;
1564

    
1565
    add_prefix(p, pxb, offset, pxc);
1566
  }
1567
}
1568

    
1569
static void
1570
prepare_prefix_net_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
1571
{
1572
  struct ospf_lsa_prefix *lp;
1573
  struct ospf_neighbor *n;
1574
  struct top_hash_entry *en;
1575
  int pxc, offset;
1576

    
1577
  ASSERT(p->lsab_used == 0);
1578
  lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix));
1579
  lp->ref_type = LSA_T_NET;
1580
  lp->ref_id = ifa->net_lsa->lsa.id;
1581
  lp->ref_rt = p->router_id;
1582
  lp = NULL; /* buffer might be reallocated later */
1583

    
1584
  pxc = 0;
1585
  offset = p->lsab_used;
1586

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

    
1591
  WALK_LIST(n, ifa->neigh_list)
1592
    if ((n->state == NEIGHBOR_FULL) &&
1593
        (en = ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK)))
1594
      add_link_lsa(p, en->lsa_body, offset, &pxc);
1595

    
1596
  lp = p->lsab;
1597
  lp->pxcount = pxc;
1598
}
1599

    
1600
static void
1601
ospf_originate_prefix_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
1602
{
1603
  if (ospf_is_v2(p))
1604
    return;
1605

    
1606
  struct ospf_new_lsa lsa = {
1607
    .type = LSA_T_PREFIX,
1608
    .dom  = ifa->oa->areaid,
1609
    .id   = ifa->iface_id,
1610
    .ifa  = ifa
1611
  };
1612

    
1613
  prepare_prefix_net_lsa_body(p, ifa);
1614

    
1615
  ifa->pxn_lsa = ospf_originate_lsa(p, &lsa);
1616
}
1617

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

    
1621
void
1622
ospf_update_topology(struct ospf_proto *p)
1623
{
1624
  struct ospf_area *oa;
1625
  struct ospf_iface *ifa;
1626

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

    
1647
      if (breaks_minlsinterval(oa->rt) || breaks_minlsinterval(oa->pxr_lsa))
1648
        continue;
1649

    
1650
      ospf_originate_rt_lsa(p, oa);
1651
      ospf_originate_prefix_rt_lsa(p, oa);
1652
      oa->update_rt_lsa = 0;
1653
    }
1654
  }
1655

    
1656
  WALK_LIST(ifa, p->iface_list)
1657
  {
1658
    if (ifa->type == OSPF_IT_VLINK)
1659
      continue;
1660

    
1661
    if (ifa->update_link_lsa)
1662
    {
1663
      if ((ifa->state > OSPF_IS_LOOP) && !ifa->link_lsa_suppression)
1664
        ospf_originate_link_lsa(p, ifa);
1665
      else
1666
        ospf_flush2_lsa(p, &ifa->link_lsa);
1667

    
1668
      ifa->update_link_lsa = 0;
1669
    }
1670

    
1671
    if (ifa->update_net_lsa)
1672
    {
1673
      if ((ifa->state == OSPF_IS_DR) && (ifa->fadj > 0))
1674
      {
1675
        ospf_originate_net_lsa(p, ifa);
1676
        ospf_originate_prefix_net_lsa(p, ifa);
1677
      }
1678
      else
1679
      {
1680
        ospf_flush2_lsa(p, &ifa->net_lsa);
1681
        ospf_flush2_lsa(p, &ifa->pxn_lsa);
1682
      }
1683

    
1684
      ifa->update_net_lsa = 0;
1685
    }
1686
  }
1687
}
1688

    
1689

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

    
1710
static inline void
1711
ospf_top_ht_free(struct top_hash_entry **h)
1712
{
1713
  mb_free(h);
1714
}
1715

    
1716
static inline u32
1717
ospf_top_hash_u32(u32 a)
1718
{
1719
  /* Shamelessly stolen from IP address hashing in ipv4.h */
1720
  a ^= a >> 16;
1721
  a ^= a << 10;
1722
  return a;
1723
}
1724

    
1725
static uint
1726
ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type)
1727
{
1728
  /* In OSPFv2, we don't know Router ID when looking for network LSAs.
1729
     In OSPFv3, we don't know LSA ID when looking for router LSAs.
1730
     In both cases, there is (usually) just one (or small number)
1731
     appropriate LSA, so we just clear unknown part of key. */
1732

    
1733
  return (((f->ospf2 && (type == LSA_T_NET)) ? 0 : ospf_top_hash_u32(rtrid)) +
1734
          ((!f->ospf2 && (type == LSA_T_RT)) ? 0 : ospf_top_hash_u32(lsaid)) +
1735
          type + domain) & f->hash_mask;
1736

    
1737
  /*
1738
  return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
1739
          type + areaid) & f->hash_mask;
1740
  */
1741
}
1742

    
1743
/**
1744
 * ospf_top_new - allocated new topology database
1745
 * @p: OSPF protocol instance
1746
 * @pool: pool for allocation
1747
 *
1748
 * This dynamically hashed structure is used for keeping LSAs. Mainly it is used
1749
 * for the LSA database of the OSPF protocol, but also for LSA retransmission
1750
 * and request lists of OSPF neighbors.
1751
 */
1752
struct top_graph *
1753
ospf_top_new(struct ospf_proto *p, pool *pool)
1754
{
1755
  struct top_graph *f;
1756

    
1757
  f = mb_allocz(pool, sizeof(struct top_graph));
1758
  f->pool = pool;
1759
  f->hash_slab = sl_new(f->pool, sizeof(struct top_hash_entry));
1760
  f->hash_order = HASH_DEF_ORDER;
1761
  ospf_top_ht_alloc(f);
1762
  f->hash_entries = 0;
1763
  f->hash_entries_min = 0;
1764
  f->ospf2 = ospf_is_v2(p);
1765
  return f;
1766
}
1767

    
1768
void
1769
ospf_top_free(struct top_graph *f)
1770
{
1771
  rfree(f->hash_slab);
1772
  ospf_top_ht_free(f->hash_table);
1773
  mb_free(f);
1774
}
1775

    
1776
static void
1777
ospf_top_rehash(struct top_graph *f, int step)
1778
{
1779
  struct top_hash_entry **n, **oldt, **newt, *e, *x;
1780
  uint oldn, oldh;
1781

    
1782
  oldn = f->hash_size;
1783
  oldt = f->hash_table;
1784
  DBG("re-hashing topology hash from order %d to %d\n", f->hash_order,
1785
      f->hash_order + step);
1786
  f->hash_order += step;
1787
  ospf_top_ht_alloc(f);
1788
  newt = f->hash_table;
1789

    
1790
  for (oldh = 0; oldh < oldn; oldh++)
1791
  {
1792
    e = oldt[oldh];
1793
    while (e)
1794
    {
1795
      x = e->next;
1796
      n = newt + ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type);
1797
      e->next = *n;
1798
      *n = e;
1799
      e = x;
1800
    }
1801
  }
1802
  ospf_top_ht_free(oldt);
1803
}
1804

    
1805
static struct top_hash_entry *
1806
ospf_hash_find_(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1807
{
1808
  struct top_hash_entry *e;
1809
  e = f->hash_table[ospf_top_hash(f, domain, lsa, rtr, type)];
1810

    
1811
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr ||
1812
               e->lsa_type != type || e->domain != domain))
1813
    e = e->next;
1814

    
1815
  return e;
1816
}
1817

    
1818
struct top_hash_entry *
1819
ospf_hash_find(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1820
{
1821
  struct top_hash_entry *e = ospf_hash_find_(f, domain, lsa, rtr, type);
1822

    
1823
  /* Hide hash entry with empty lsa_body */
1824
  return (e && e->lsa_body) ? e : NULL;
1825
}
1826

    
1827
/* In OSPFv2, lsa.id is the same as lsa.rt for router LSA. In OSPFv3, we don't know
1828
   lsa.id when looking for router LSAs. We return matching LSA with smallest lsa.id. */
1829
struct top_hash_entry *
1830
ospf_hash_find_rt(struct top_graph *f, u32 domain, u32 rtr)
1831
{
1832
  struct top_hash_entry *rv = NULL;
1833
  struct top_hash_entry *e;
1834
  /* We can put rtr for lsa.id to hash fn, it is ignored in OSPFv3 */
1835
  e = f->hash_table[ospf_top_hash(f, domain, rtr, rtr, LSA_T_RT)];
1836

    
1837
  while (e)
1838
  {
1839
    if (e->lsa.rt == rtr && e->lsa_type == LSA_T_RT && e->domain == domain && e->lsa_body)
1840
    {
1841
      if (f->ospf2 && (e->lsa.id == rtr))
1842
        return e;
1843
      if (!f->ospf2 && (!rv || e->lsa.id < rv->lsa.id))
1844
        rv = e;
1845
    }
1846
    e = e->next;
1847
  }
1848

    
1849
  return rv;
1850
}
1851

    
1852
/*
1853
 * ospf_hash_find_rt3_first() and ospf_hash_find_rt3_next() are used exclusively
1854
 * for lsa_walk_rt_init(), lsa_walk_rt(), therefore they skip MaxAge entries.
1855
 */
1856
static inline struct top_hash_entry *
1857
find_matching_rt3(struct top_hash_entry *e, u32 domain, u32 rtr)
1858
{
1859
  while (e && (e->lsa.rt != rtr || e->lsa_type != LSA_T_RT ||
1860
               e->domain != domain || e->lsa.age == LSA_MAXAGE))
1861
    e = e->next;
1862
  return e;
1863
}
1864

    
1865
struct top_hash_entry *
1866
ospf_hash_find_rt3_first(struct top_graph *f, u32 domain, u32 rtr)
1867
{
1868
  struct top_hash_entry *e;
1869
  e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)];
1870
  return find_matching_rt3(e, domain, rtr);
1871
}
1872

    
1873
struct top_hash_entry *
1874
ospf_hash_find_rt3_next(struct top_hash_entry *e)
1875
{
1876
  return find_matching_rt3(e->next, e->domain, e->lsa.rt);
1877
}
1878

    
1879
/* In OSPFv2, we don't know Router ID when looking for network LSAs.
1880
   There should be just one, so we find any match. */
1881
struct top_hash_entry *
1882
ospf_hash_find_net2(struct top_graph *f, u32 domain, u32 id)
1883
{
1884
  struct top_hash_entry *e;
1885
  e = f->hash_table[ospf_top_hash(f, domain, id, 0, LSA_T_NET)];
1886

    
1887
  while (e && (e->lsa.id != id || e->lsa_type != LSA_T_NET ||
1888
               e->domain != domain || e->lsa_body == NULL))
1889
    e = e->next;
1890

    
1891
  return e;
1892
}
1893

    
1894

    
1895
struct top_hash_entry *
1896
ospf_hash_get(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1897
{
1898
  struct top_hash_entry **ee;
1899
  struct top_hash_entry *e;
1900

    
1901
  ee = f->hash_table + ospf_top_hash(f, domain, lsa, rtr, type);
1902
  e = *ee;
1903

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

    
1908
  if (e)
1909
    return e;
1910

    
1911
  e = sl_alloc(f->hash_slab);
1912
  bzero(e, sizeof(struct top_hash_entry));
1913

    
1914
  e->color = OUTSPF;
1915
  e->dist = LSINFINITY;
1916
  e->lsa.type_raw = type;
1917
  e->lsa.id = lsa;
1918
  e->lsa.rt = rtr;
1919
  e->lsa.sn = LSA_ZEROSEQNO;
1920
  e->lsa_type = type;
1921
  e->domain = domain;
1922
  e->next = *ee;
1923
  *ee = e;
1924
  if (f->hash_entries++ > f->hash_entries_max)
1925
    ospf_top_rehash(f, HASH_HI_STEP);
1926
  return e;
1927
}
1928

    
1929
void
1930
ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
1931
{
1932
  struct top_hash_entry **ee = f->hash_table +
1933
    ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type);
1934

    
1935
  while (*ee)
1936
  {
1937
    if (*ee == e)
1938
    {
1939
      *ee = e->next;
1940
      sl_free(f->hash_slab, e);
1941
      if (f->hash_entries-- < f->hash_entries_min)
1942
        ospf_top_rehash(f, -HASH_LO_STEP);
1943
      return;
1944
    }
1945
    ee = &((*ee)->next);
1946
  }
1947
  bug("ospf_hash_delete() called for invalid node");
1948
}
1949

    
1950
/*
1951
static void
1952
ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
1953
{
1954

1955
  struct ospf_lsa_rt *rt = NULL;
1956
  struct ospf_lsa_rt_link *rr = NULL;
1957
  struct ospf_lsa_net *ln = NULL;
1958
  u32 *rts = NULL;
1959
  u32 i, max;
1960

1961
  OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
1962
             he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
1963
             he->lsa.checksum, he->domain);
1964

1965

1966
  switch (he->lsa.type)
1967
    {
1968
    case LSA_T_RT:
1969
      rt = he->lsa_body;
1970
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
1971

1972
      for (i = 0; i < lsa_rt_items(&he->lsa); i++)
1973
        OSPF_TRACE(D_EVENTS, "  - %1x %-1R %-1R %5u",
1974
                   rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
1975
      break;
1976

1977
    case LSA_T_NET:
1978
      ln = he->lsa_body;
1979
      rts = (u32 *) (ln + 1);
1980

1981
      for (i = 0; i < lsa_net_items(&he->lsa); i++)
1982
        OSPF_TRACE(D_EVENTS, "  - %-1R", rts[i]);
1983
      break;
1984

1985
    default:
1986
      break;
1987
    }
1988
}
1989

1990
void
1991
ospf_top_dump(struct top_graph *f, struct proto *p)
1992
{
1993
  uint i;
1994
  OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
1995

1996
  for (i = 0; i < f->hash_size; i++)
1997
  {
1998
    struct top_hash_entry *e;
1999
    for (e = f->hash_table[i]; e != NULL; e = e->next)
2000
      ospf_dump_lsa(e, p);
2001
  }
2002
}
2003
*/