Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (51.2 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
      lsa_generate_checksum(&en->lsa, en->lsa_body);
133

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

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

    
159
      en->lsa_body = body;
160
      en->lsa = *lsa;
161
      en->lsa.age = LSA_MAXAGE;
162
      en->init_age = lsa->age;
163
      en->inst_time = 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
  lsa_generate_checksum(&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 %N",
287
        p->p.name, lsa->nf->fn.addr);
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
  lsa_generate_checksum(&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 has to be mapped on itself.  All received prefixes have to be mapped
524
   * 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
  net_addr_ip4 *net = (void *) nf->fn.addr;
555
  u32 id = ip4_to_u32(net->prefix);
556
  int pxlen = net->pxlen;
557

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

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

    
567

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

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

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

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

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

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

    
617

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

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

    
642
  return 0;
643
}
644

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

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

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

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

    
665
  return 0;
666
}
667

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

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

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

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

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

    
685
  return opts;
686
}
687

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

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

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

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

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

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

    
726
    ifa->rt_pos_beg = i;
727

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

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

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

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

    
770
    ifa->rt_pos_end = i;
771

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

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

    
788
    ifa->rt_pos_end = i;
789
  }
790

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

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

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

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

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

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

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

    
838
    ifa->rt_pos_beg = i;
839

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

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

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

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

    
867
    ifa->rt_pos_end = i;
868
  }
869

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

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

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

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

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

    
894

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
981

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

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

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

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

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

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

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

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

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

    
1037
  ospf_originate_lsa(p, &lsa);
1038
}
1039

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

    
1051
  if (ospf_is_v2(p))
1052
    prepare_sum2_lsa_body(p, 0, metric);
1053
  else
1054
    prepare_sum3_rt_lsa_body(p, drid, metric, options & LSA_OPTIONS_MASK);
1055

    
1056
  ospf_originate_lsa(p, &lsa);
1057
}
1058

    
1059

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

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

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

    
1077
  if (ebit)
1078
    ext->metric |= LSA_EXT2_EBIT;
1079
}
1080

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

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

    
1095
  buf = ospf_put_ipv6_prefix(buf, nf->fn.addr, pbit ? OPT_PX_P : 0, 0);
1096

    
1097
  if (ebit)
1098
    ext->metric |= LSA_EXT3_EBIT;
1099

    
1100
  if (ipa_nonzero(fwaddr))
1101
  {
1102
    ext->metric |= LSA_EXT3_FBIT;
1103
    buf = ospf_put_ipv6_addr(buf, fwaddr);
1104
  }
1105

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

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

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

    
1149
  ospf_originate_lsa(p, &lsa);
1150
}
1151

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

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

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

    
1164
  en = ospf_hash_find_(p->gr, dom, id, p->router_id, type);
1165

    
1166
  if (!en || (en->nf != nf))
1167
    return;
1168

    
1169
  ospf_flush_lsa(p, en);
1170
}
1171

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

    
1177
  if (ipa_zero(gw) || ipa_is_link_local(gw))
1178
    return 0;
1179

    
1180
  WALK_LIST(ifa, p->iface_list)
1181
    if ((ifa->iface == iface) &&
1182
        (!ospf_is_v2(p) || ipa_in_net(gw, ifa->addr->prefix, ifa->addr->pxlen)))
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 = fib_find(&p->rtf, n->n.addr);
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 %N",
1296
          p->p.name, n->n.addr);
1297
      return;
1298
    }
1299
  }
1300

    
1301
  nf = fib_get(&p->rtf, n->n.addr);
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, ip6_addr prefix, u32 pxlen, u32 cost)
1314
{
1315
  net_addr_ip6 net = NET_ADDR_IP6(prefix, pxlen);
1316
  void *buf = lsab_alloc(p, IPV6_PREFIX_SPACE(pxlen));
1317
  u8 flags = (pxlen < IP6_MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
1318
  ospf_put_ipv6_prefix(buf, (net_addr *) &net, flags, cost);
1319
}
1320

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

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

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

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

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

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

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

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

    
1363
  prepare_link_lsa_body(p, ifa);
1364

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

    
1368

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

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

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

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

    
1396
    ifa->px_pos_beg = i;
1397

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

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

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

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

    
1428
    ifa->px_pos_end = i;
1429
  }
1430

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

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

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

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

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

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

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

    
1481
  prepare_prefix_rt_lsa_body(p, oa);
1482

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

    
1486

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

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

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

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

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

    
1514
  return 1;
1515
}
1516

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
1614
  prepare_prefix_net_lsa_body(p, ifa);
1615

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

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

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

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

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

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

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

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

    
1669
      ifa->update_link_lsa = 0;
1670
    }
1671

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

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

    
1690

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
1816
  return e;
1817
}
1818

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

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

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

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

    
1850
  return rv;
1851
}
1852

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

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

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

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

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

    
1892
  return e;
1893
}
1894

    
1895

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

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

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

    
1909
  if (e)
1910
    return e;
1911

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

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

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

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

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

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

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

1966

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

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

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

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

1986
    default:
1987
      break;
1988
    }
1989
}
1990

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

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