Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / proto / ospf / topology.c @ 6b3f1a54

History | View | Annotate | Download (51.7 KB)

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

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

    
15
#include "ospf.h"
16

    
17

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

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

    
29

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

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

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

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

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

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

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

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

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

    
88
  return en;
89
}
90

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

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

    
126
      mb_free(body);
127

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

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

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

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

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

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

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

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

    
194

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

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

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

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

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

    
224
  /*
225
   * lsa.type_raw is initialized by ospf_hash_get() to OSPFv3 LSA type.
226
   * lsa_set_options() implicitly converts it to OSPFv2 LSA type, assuming that
227
   * old type is just new type masked by 0xff.  That 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 = current_time();
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->nf || !en->lsa_body)
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 = current_time();
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
  btime now_ = current_time();
480
  int real_age;
481

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

    
487
    real_age = en->init_age + (now_ - en->inst_time) TO_S;
488

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

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

    
498
      continue;
499
    }
500

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

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

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

    
517

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

    
550
  if (ospf_is_v3(p))
551
  {
552
    if (!nf->lsa_id)
553
      nf->lsa_id = idm_alloc(&p->idm);
554

    
555
    return nf->lsa_id;
556
  }
557

    
558
  net_addr_ip4 *net = (void *) nf->fn.addr;
559
  u32 id = ip4_to_u32(net->prefix);
560
  int pxlen = net->pxlen;
561

    
562
  if ((pxlen == 0) || (pxlen == 32))
563
    return id;
564

    
565
  if (id & (1 << (32 - pxlen)))
566
    return id;
567
  else
568
    return id | ~u32_mkmask(pxlen);
569
}
570

    
571

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

    
586
static inline void *
587
lsab_allocz(struct ospf_proto *p, uint size)
588
{
589
  void *r = lsab_alloc(p, size);
590
  bzero(r, size);
591
  return r;
592
}
593

    
594
static inline void *
595
lsab_flush(struct ospf_proto *p)
596
{
597
  void *r = mb_alloc(p->p.pool, p->lsab_used);
598
  memcpy(r, p->lsab, p->lsab_used);
599
  p->lsab_used = 0;
600
  return r;
601
}
602

    
603
static inline void
604
lsab_reset(struct ospf_proto *p)
605
{
606
  p->lsab_used = 0;
607
}
608

    
609
static inline void *
610
lsab_offset(struct ospf_proto *p, uint offset)
611
{
612
  return ((byte *) p->lsab) + offset;
613
}
614

    
615
static inline void * UNUSED
616
lsab_end(struct ospf_proto *p)
617
{
618
  return ((byte *) p->lsab) + p->lsab_used;
619
}
620

    
621

    
622
/*
623
 *        Router-LSA handling
624
 *        Type = LSA_T_RT
625
 */
626

    
627
static int
628
configured_stubnet(struct ospf_area *oa, struct ifa *a)
629
{
630
  /* Does not work for IA_PEER addresses, but it is not called on these */
631
  struct ospf_stubnet_config *sn;
632
  WALK_LIST(sn, oa->ac->stubnet_list)
633
  {
634
    if (sn->summary)
635
    {
636
      if (net_in_netX(&a->prefix, &sn->prefix))
637
        return 1;
638
    }
639
    else
640
    {
641
      if (net_equal(&a->prefix, &sn->prefix))
642
        return 1;
643
    }
644
  }
645

    
646
  return 0;
647
}
648

    
649
static int
650
bcast_net_active(struct ospf_iface *ifa)
651
{
652
  struct ospf_neighbor *neigh;
653

    
654
  if (ifa->state == OSPF_IS_WAITING)
655
    return 0;
656

    
657
  WALK_LIST(neigh, ifa->neigh_list)
658
  {
659
    if (neigh->state == NEIGHBOR_FULL)
660
    {
661
      if (neigh->rid == ifa->drid)
662
        return 1;
663

    
664
      if (ifa->state == OSPF_IS_DR)
665
        return 1;
666
    }
667
  }
668

    
669
  return 0;
670
}
671

    
672
static inline u32
673
get_rt_options(struct ospf_proto *p, struct ospf_area *oa, int bitv)
674
{
675
  u32 opts = 0;
676

    
677
  if (p->areano > 1)
678
    opts |= OPT_RT_B;
679

    
680
  if ((p->areano > 1) && oa_is_nssa(oa) && oa->ac->translator)
681
    opts |= OPT_RT_NT;
682

    
683
  if (p->asbr && !oa_is_stub(oa))
684
    opts |= OPT_RT_E;
685

    
686
  if (bitv)
687
    opts |= OPT_RT_V;
688

    
689
  return opts;
690
}
691

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

    
703
static void
704
prepare_rt2_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
705
{
706
  struct ospf_iface *ifa;
707
  int i = 0, bitv = 0;
708
  struct ospf_neighbor *neigh;
709

    
710
  ASSERT(p->lsab_used == 0);
711
  lsab_allocz(p, sizeof(struct ospf_lsa_rt));
712
  /* ospf_lsa_rt header will be filled later */
713

    
714
  WALK_LIST(ifa, p->iface_list)
715
  {
716
    int net_lsa = 0;
717
    u32 link_cost = p->stub_router ? 0xffff : ifa->cost;
718

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

    
727
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
728
      continue;
729

    
730
    ifa->rt_pos_beg = i;
731

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

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

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

    
769
    default:
770
      log(L_BUG "OSPF: Unknown interface type");
771
      break;
772
    }
773

    
774
    ifa->rt_pos_end = i;
775

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

    
783
      /* Host or network stub entry */
784
    if ((ifa->addr->flags & IA_HOST) ||
785
        (ifa->state == OSPF_IS_LOOP) ||
786
        (ifa->type == OSPF_IT_PTMP))
787
      add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(ifa->addr->ip), 0xffffffff, 0);
788
    else
789
      add_rt2_lsa_link(p, LSART_STUB, ip4_to_u32(net4_prefix(&ifa->addr->prefix)),
790
                       u32_mkmask(net4_pxlen(&ifa->addr->prefix)), ifa->cost);
791
    i++;
792

    
793
    ifa->rt_pos_end = i;
794
  }
795

    
796
  struct ospf_stubnet_config *sn;
797
  WALK_LIST(sn, oa->ac->stubnet_list)
798
    if (!sn->hidden)
799
      add_rt2_lsa_link(p, LSART_STUB, ip4_to_u32(net4_prefix(&sn->prefix)),
800
                       u32_mkmask(net4_pxlen(&sn->prefix)), sn->cost), i++;
801

    
802
  struct ospf_lsa_rt *rt = p->lsab;
803
  /* Store number of links in lower half of options */
804
  rt->options = get_rt_options(p, oa, bitv) | (u16) i;
805
}
806

    
807
static inline void
808
add_rt3_lsa_link(struct ospf_proto *p, u8 type, struct ospf_iface *ifa, u32 nif, u32 id)
809
{
810
  struct ospf_lsa_rt3_link *ln = lsab_alloc(p, sizeof(struct ospf_lsa_rt3_link));
811
  ln->type = type;
812
  ln->padding = 0;
813
  ln->metric = ifa->cost;
814
  ln->lif = ifa->iface_id;
815
  ln->nif = nif;
816
  ln->id = id;
817
}
818

    
819
static void
820
prepare_rt3_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
821
{
822
  struct ospf_iface *ifa;
823
  struct ospf_neighbor *neigh;
824
  int bitv = 0;
825
  int i = 0;
826

    
827
  ASSERT(p->lsab_used == 0);
828
  lsab_allocz(p, sizeof(struct ospf_lsa_rt));
829
  /* ospf_lsa_rt header will be filled later */
830

    
831
  WALK_LIST(ifa, p->iface_list)
832
  {
833
    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
834
        (!EMPTY_LIST(ifa->neigh_list)))
835
    {
836
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
837
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
838
        bitv = 1;
839
    }
840

    
841
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
842
      continue;
843

    
844
    ifa->rt_pos_beg = i;
845

    
846
    /* RFC 5340 - 4.4.3.2 */
847
    switch (ifa->type)
848
    {
849
    case OSPF_IT_PTP:
850
    case OSPF_IT_PTMP:
851
      WALK_LIST(neigh, ifa->neigh_list)
852
        if (neigh->state == NEIGHBOR_FULL)
853
          add_rt3_lsa_link(p, LSART_PTP, ifa, neigh->iface_id, neigh->rid), i++;
854
      break;
855

    
856
    case OSPF_IT_BCAST:
857
    case OSPF_IT_NBMA:
858
      if (bcast_net_active(ifa))
859
        add_rt3_lsa_link(p, LSART_NET, ifa, ifa->dr_iface_id, ifa->drid), i++;
860
      break;
861

    
862
    case OSPF_IT_VLINK:
863
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
864
      if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
865
        add_rt3_lsa_link(p, LSART_VLNK, ifa, neigh->iface_id, neigh->rid), i++;
866
      break;
867

    
868
    default:
869
      log(L_BUG "OSPF: Unknown interface type");
870
      break;
871
    }
872

    
873
    ifa->rt_pos_end = i;
874
  }
875

    
876
  struct ospf_lsa_rt *rt = p->lsab;
877
  rt->options = get_rt_options(p, oa, bitv) | (oa->options & LSA_OPTIONS_MASK);
878
}
879

    
880
static void
881
ospf_originate_rt_lsa(struct ospf_proto *p, struct ospf_area *oa)
882
{
883
  struct ospf_new_lsa lsa = {
884
    .type = LSA_T_RT,
885
    .dom  = oa->areaid,
886
    .id   = ospf_is_v2(p) ? p->router_id : 0,
887
    .opts = oa->options
888
  };
889

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

    
892
  if (ospf_is_v2(p))
893
    prepare_rt2_lsa_body(p, oa);
894
  else
895
    prepare_rt3_lsa_body(p, oa);
896

    
897
  oa->rt = ospf_originate_lsa(p, &lsa);
898
}
899

    
900

    
901
/*
902
 *        Net-LSA handling
903
 *        Type = LSA_T_NET
904
 */
905

    
906
static void
907
prepare_net2_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
908
{
909
  struct ospf_lsa_net *net;
910
  struct ospf_neighbor *n;
911
  int nodes = ifa->fadj + 1;
912
  u16 i = 1;
913

    
914
  ASSERT(p->lsab_used == 0);
915
  net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes);
916

    
917
  net->optx = u32_mkmask(ifa->addr->prefix.pxlen);
918
  net->routers[0] = p->router_id;
919

    
920
  WALK_LIST(n, ifa->neigh_list)
921
  {
922
    if (n->state == NEIGHBOR_FULL)
923
    {
924
      net->routers[i] = n->rid;
925
      i++;
926
    }
927
  }
928
  ASSERT(i == nodes);
929
}
930

    
931
static void
932
prepare_net3_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
933
{
934
  struct ospf_lsa_net *net;
935
  int nodes = ifa->fadj + 1;
936
  u32 options = 0;
937
  u16 i = 1;
938

    
939
  ASSERT(p->lsab_used == 0);
940
  net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes);
941

    
942
  net->routers[0] = p->router_id;
943

    
944
  struct ospf_neighbor *n;
945
  WALK_LIST(n, ifa->neigh_list)
946
  {
947
    if (n->state == NEIGHBOR_FULL)
948
    {
949
      /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */
950

    
951
      struct top_hash_entry *en =
952
        ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK);
953

    
954
      if (en)
955
        options |= ((struct ospf_lsa_link *) en->lsa_body)->options;
956

    
957
      net->routers[i] = n->rid;
958
      i++;
959
    }
960
  }
961
  ASSERT(i == nodes);
962

    
963
  net->optx = options & LSA_OPTIONS_MASK;
964
}
965

    
966
static void
967
ospf_originate_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
968
{
969
  struct ospf_new_lsa lsa = {
970
    .type = LSA_T_NET,
971
    .dom  = ifa->oa->areaid,
972
    .id   = ospf_is_v2(p) ? ipa_to_u32(ifa->addr->ip) : ifa->iface_id,
973
    .opts = ifa->oa->options,
974
    .ifa  = ifa
975
  };
976

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

    
979
  if (ospf_is_v2(p))
980
    prepare_net2_lsa_body(p, ifa);
981
  else
982
    prepare_net3_lsa_body(p, ifa);
983

    
984
  ifa->net_lsa = ospf_originate_lsa(p, &lsa);
985
}
986

    
987

    
988
/*
989
 *        (Net|Rt)-summary-LSA handling
990
 *        (a.k.a. Inter-Area-(Prefix|Router)-LSA)
991
 *        Type = LSA_T_SUM_NET, LSA_T_SUM_RT
992
 */
993

    
994
static inline void
995
prepare_sum2_lsa_body(struct ospf_proto *p, uint pxlen, u32 metric)
996
{
997
  struct ospf_lsa_sum2 *sum;
998

    
999
  sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum2));
1000
  sum->netmask = u32_mkmask(pxlen);
1001
  sum->metric = metric;
1002
}
1003

    
1004
static inline void
1005
prepare_sum3_net_lsa_body(struct ospf_proto *p, ort *nf, u32 metric)
1006
{
1007
  struct ospf_lsa_sum3_net *sum;
1008

    
1009
  sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_net) +
1010
                    IPV6_PREFIX_SPACE(nf->fn.addr->pxlen));
1011
  sum->metric = metric;
1012
  ospf3_put_prefix(sum->prefix, nf->fn.addr, 0, 0);
1013
}
1014

    
1015
static inline void
1016
prepare_sum3_rt_lsa_body(struct ospf_proto *p, u32 drid, u32 metric, u32 options)
1017
{
1018
  struct ospf_lsa_sum3_rt *sum;
1019

    
1020
  sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_rt));
1021
  sum->options = options;
1022
  sum->metric = metric;
1023
  sum->drid = drid;
1024
}
1025

    
1026
void
1027
ospf_originate_sum_net_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, int metric)
1028
{
1029
  struct ospf_new_lsa lsa = {
1030
    .type = LSA_T_SUM_NET,
1031
    .mode = LSA_M_RTCALC,
1032
    .dom  = oa->areaid,
1033
    .id   = ort_to_lsaid(p, nf),
1034
    .opts = oa->options,
1035
    .nf   = nf
1036
  };
1037

    
1038
  if (ospf_is_v2(p))
1039
    prepare_sum2_lsa_body(p, nf->fn.addr->pxlen, metric);
1040
  else
1041
    prepare_sum3_net_lsa_body(p, nf, metric);
1042

    
1043
  ospf_originate_lsa(p, &lsa);
1044
}
1045

    
1046
void
1047
ospf_originate_sum_rt_lsa(struct ospf_proto *p, struct ospf_area *oa, u32 drid, int metric, u32 options)
1048
{
1049
  struct ospf_new_lsa lsa = {
1050
    .type = LSA_T_SUM_RT,
1051
    .mode = LSA_M_RTCALC,
1052
    .dom  = oa->areaid,
1053
    .id   = drid,        /* Router ID of ASBR, irrelevant for OSPFv3 */
1054
    .opts = oa->options
1055
  };
1056

    
1057
  if (ospf_is_v2(p))
1058
    prepare_sum2_lsa_body(p, 0, metric);
1059
  else
1060
    prepare_sum3_rt_lsa_body(p, drid, metric, options & LSA_OPTIONS_MASK);
1061

    
1062
  ospf_originate_lsa(p, &lsa);
1063
}
1064

    
1065

    
1066
/*
1067
 *        AS-external-LSA and NSSA-LSA handling
1068
 *        Type = LSA_T_EXT, LSA_T_NSSA
1069
 */
1070

    
1071
static inline void
1072
prepare_ext2_lsa_body(struct ospf_proto *p, uint pxlen,
1073
                      u32 metric, u32 ebit, ip_addr fwaddr, u32 tag)
1074
{
1075
  struct ospf_lsa_ext2 *ext;
1076

    
1077
  ext = lsab_allocz(p, sizeof(struct ospf_lsa_ext2));
1078
  ext->metric = metric & LSA_METRIC_MASK;
1079
  ext->netmask = u32_mkmask(pxlen);
1080
  ext->fwaddr = ipa_to_u32(fwaddr);
1081
  ext->tag = tag;
1082

    
1083
  if (ebit)
1084
    ext->metric |= LSA_EXT2_EBIT;
1085
}
1086

    
1087
static inline void
1088
prepare_ext3_lsa_body(struct ospf_proto *p, ort *nf,
1089
                      u32 metric, u32 ebit, ip_addr fwaddr, u32 tag, int pbit)
1090
{
1091
  struct ospf_lsa_ext3 *ext;
1092
  int bsize = sizeof(struct ospf_lsa_ext3)
1093
    + IPV6_PREFIX_SPACE(nf->fn.addr->pxlen)
1094
    + (ipa_nonzero(fwaddr) ? 16 : 0)
1095
    + (tag ? 4 : 0);
1096

    
1097
  ext = lsab_allocz(p, bsize);
1098
  ext->metric = metric & LSA_METRIC_MASK;
1099
  u32 *buf = ext->rest;
1100

    
1101
  buf = ospf3_put_prefix(buf, nf->fn.addr, pbit ? OPT_PX_P : 0, 0);
1102

    
1103
  if (ebit)
1104
    ext->metric |= LSA_EXT3_EBIT;
1105

    
1106
  if (ipa_nonzero(fwaddr))
1107
  {
1108
    ext->metric |= LSA_EXT3_FBIT;
1109
    buf = ospf3_put_addr(buf, fwaddr);
1110
  }
1111

    
1112
  if (tag)
1113
  {
1114
    ext->metric |= LSA_EXT3_TBIT;
1115
    *buf++ = tag;
1116
  }
1117
}
1118

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

    
1150
  if (ospf_is_v2(p))
1151
    prepare_ext2_lsa_body(p, nf->fn.addr->pxlen, metric, ebit, fwaddr, tag);
1152
  else
1153
    prepare_ext3_lsa_body(p, nf, metric, ebit, fwaddr, tag, oa && pbit);
1154

    
1155
  ospf_originate_lsa(p, &lsa);
1156
}
1157

    
1158
static struct top_hash_entry *
1159
ospf_hash_find_(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type);
1160

    
1161
static void
1162
ospf_flush_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf)
1163
{
1164
  struct top_hash_entry *en;
1165

    
1166
  u32 type = oa ? LSA_T_NSSA : LSA_T_EXT;
1167
  u32 dom = oa ? oa->areaid : 0;
1168
  u32 id = ort_to_lsaid(p, nf);
1169

    
1170
  en = ospf_hash_find_(p->gr, dom, id, p->router_id, type);
1171

    
1172
  if (!en || (en->nf != nf))
1173
    return;
1174

    
1175
  ospf_flush_lsa(p, en);
1176
}
1177

    
1178
static inline int
1179
use_gw_for_fwaddr(struct ospf_proto *p, ip_addr gw, struct iface *iface)
1180
{
1181
  struct ospf_iface *ifa;
1182

    
1183
  if (ipa_zero(gw) || ipa_is_link_local(gw))
1184
    return 0;
1185

    
1186
  WALK_LIST(ifa, p->iface_list)
1187
    if ((ifa->iface == iface) &&
1188
        (!ospf_is_v2(p) || ipa_in_netX(gw, &ifa->addr->prefix)))
1189
      return 1;
1190

    
1191
  return 0;
1192
}
1193

    
1194
static inline ip_addr
1195
find_surrogate_fwaddr(struct ospf_proto *p, struct ospf_area *oa)
1196
{
1197
  struct ospf_iface *ifa;
1198
  struct ifa *a, *cur_addr = NULL;
1199
  int np, cur_np = 0;
1200

    
1201
  /* RFC 3101 2.3 - surrogate forwarding address selection */
1202

    
1203
  WALK_LIST(ifa, p->iface_list)
1204
  {
1205
    if ((ifa->oa != oa) ||
1206
        (ifa->type == OSPF_IT_VLINK))
1207
      continue;
1208

    
1209
    if (ospf_is_v2(p))
1210
    {
1211
      a = ifa->addr;
1212
      if (a->flags & IA_PEER)
1213
        continue;
1214

    
1215
      np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1);
1216
      if (np > cur_np)
1217
      {
1218
        cur_addr = a;
1219
        cur_np = np;
1220
      }
1221
    }
1222
    else /* OSPFv3 */
1223
    {
1224
      WALK_LIST(a, ifa->iface->addrs)
1225
      {
1226
        if ((a->prefix.type != ospf_get_af(p)) ||
1227
            (a->flags & IA_SECONDARY) ||
1228
            (a->flags & IA_PEER) ||
1229
            (a->scope <= SCOPE_LINK))
1230
          continue;
1231

    
1232
        np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1);
1233
        if (np > cur_np)
1234
        {
1235
          cur_addr = a;
1236
          cur_np = np;
1237
        }
1238
      }
1239
    }
1240
  }
1241

    
1242
  return cur_addr ? cur_addr->ip : IPA_NONE;
1243
}
1244

    
1245
void
1246
ospf_rt_notify(struct proto *P, struct channel *ch UNUSED, net *n, rte *new, rte *old UNUSED, ea_list *ea)
1247
{
1248
  struct ospf_proto *p = (struct ospf_proto *) P;
1249
  struct ospf_area *oa = NULL;        /* non-NULL for NSSA-LSA */
1250
  ort *nf;
1251

    
1252
  /*
1253
   * There are several posibilities:
1254
   * 1) router in regular area - originate external LSA with global scope
1255
   * 2) router in NSSA area - originate area-specific NSSA-LSA
1256
   * 3) router in stub area - cannot export routes
1257
   * 4) area border router - same as (1), it is attached to backbone
1258
   */
1259

    
1260
  if ((p->areano == 1) && oa_is_nssa(HEAD(p->area_list)))
1261
    oa = HEAD(p->area_list);
1262

    
1263
  if (!new)
1264
  {
1265
    nf = fib_find(&p->rtf, n->n.addr);
1266

    
1267
    if (!nf || !nf->external_rte)
1268
      return;
1269

    
1270
    ospf_flush_ext_lsa(p, oa, nf);
1271
    nf->external_rte = 0;
1272

    
1273
    /* Old external route might blocked some NSSA translation */
1274
    if ((p->areano > 1) && rt_is_nssa(nf) && nf->n.oa->translate)
1275
      ospf_schedule_rtcalc(p);
1276

    
1277
    return;
1278
  }
1279

    
1280
  ASSERT(p->asbr);
1281

    
1282
  /* Get route attributes */
1283
  rta *a = new->attrs;
1284
  u32 m1 = ea_get_int(ea, EA_OSPF_METRIC1, LSINFINITY);
1285
  u32 m2 = ea_get_int(ea, EA_OSPF_METRIC2, 10000);
1286
  int ebit = (m1 == LSINFINITY);
1287
  u32 metric = ebit ? m2 : m1;
1288
  u32 tag = ea_get_int(ea, EA_OSPF_TAG, 0);
1289
  ip_addr fwd = IPA_NONE;
1290

    
1291

    
1292
  if ((a->dest == RTD_UNICAST) && use_gw_for_fwaddr(p, a->nh.gw, a->nh.iface))
1293
    fwd = a->nh.gw;
1294

    
1295
  /* NSSA-LSA with P-bit set must have non-zero forwarding address */
1296
  if (oa && ipa_zero(fwd))
1297
  {
1298
    fwd = find_surrogate_fwaddr(p, oa);
1299

    
1300
    if (ipa_zero(fwd))
1301
    {
1302
      log(L_ERR "%s: Cannot find forwarding address for NSSA-LSA %N",
1303
          p->p.name, n->n.addr);
1304
      return;
1305
    }
1306
  }
1307

    
1308
  nf = fib_get(&p->rtf, n->n.addr);
1309
  ospf_originate_ext_lsa(p, oa, nf, LSA_M_EXPORT, metric, ebit, fwd, tag, 1);
1310
  nf->external_rte = 1;
1311
}
1312

    
1313

    
1314
/*
1315
 *        Link-LSA handling (assume OSPFv3)
1316
 *        Type = LSA_T_LINK
1317
 */
1318

    
1319
static inline void
1320
lsab_put_prefix(struct ospf_proto *p, net_addr *n, u32 cost)
1321
{
1322
  void *buf = lsab_alloc(p, IPV6_PREFIX_SPACE(net_pxlen(n)));
1323
  uint max = (n->type == NET_IP4) ? IP4_MAX_PREFIX_LENGTH : IP6_MAX_PREFIX_LENGTH;
1324
  u8 flags = (net_pxlen(n) < max) ? 0 : OPT_PX_LA;
1325
  ospf3_put_prefix(buf, n, flags, cost);
1326
}
1327

    
1328
static void
1329
prepare_link_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
1330
{
1331
  ip_addr nh = ospf_is_ip4(p) ? IPA_NONE : ifa->addr->ip;
1332
  int i = 0;
1333

    
1334
  /* Preallocating space for header */
1335
  ASSERT(p->lsab_used == 0);
1336
  lsab_allocz(p, sizeof(struct ospf_lsa_link));
1337

    
1338
  struct ifa *a;
1339
  WALK_LIST(a, ifa->iface->addrs)
1340
  {
1341
    if ((a->prefix.type != ospf_get_af(p)) ||
1342
        (a->flags & IA_SECONDARY) ||
1343
        (a->scope <= SCOPE_LINK))
1344
      continue;
1345

    
1346
    if (ospf_is_ip4(p) && ipa_zero(nh))
1347
      nh = a->ip;
1348

    
1349
    lsab_put_prefix(p, &a->prefix, 0);
1350
    i++;
1351
  }
1352

    
1353
  /* Filling the preallocated header */
1354
  struct ospf_lsa_link *ll = p->lsab;
1355
  ll->options = ifa->oa->options | (ifa->priority << 24);
1356
  ll->lladdr = ospf_is_ip4(p) ? ospf3_4to6(ipa_to_ip4(nh)) : ipa_to_ip6(nh);
1357
  ll->pxcount = i;
1358

    
1359
  if (ipa_zero(nh))
1360
    log(L_ERR "%s: Cannot find next hop address for %s", p->p.name, ifa->ifname);
1361
}
1362

    
1363
static void
1364
ospf_originate_link_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
1365
{
1366
  if (ospf_is_v2(p))
1367
    return;
1368

    
1369
  struct ospf_new_lsa lsa = {
1370
    .type = LSA_T_LINK,
1371
    .dom  = ifa->iface_id,
1372
    .id   = ifa->iface_id,
1373
    .ifa  = ifa
1374
  };
1375

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

    
1378
  prepare_link_lsa_body(p, ifa);
1379

    
1380
  ifa->link_lsa = ospf_originate_lsa(p, &lsa);
1381
}
1382

    
1383

    
1384
/*
1385
 *        Prefix-Rt-LSA handling (assume OSPFv3)
1386
 *        Type = LSA_T_PREFIX, referred type = LSA_T_RT
1387
 */
1388

    
1389
static void
1390
prepare_prefix_rt_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
1391
{
1392
  struct ospf_config *cf = (struct ospf_config *) (p->p.cf);
1393
  struct ospf_iface *ifa;
1394
  struct ospf_lsa_prefix *lp;
1395
  int host_addr = 0;
1396
  int net_lsa;
1397
  int i = 0;
1398

    
1399
  ASSERT(p->lsab_used == 0);
1400
  lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix));
1401
  lp->ref_type = LSA_T_RT;
1402
  lp->ref_id = 0;
1403
  lp->ref_rt = p->router_id;
1404
  lp = NULL; /* buffer might be reallocated later */
1405

    
1406
  WALK_LIST(ifa, p->iface_list)
1407
  {
1408
    if ((ifa->oa != oa) || (ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
1409
      continue;
1410

    
1411
    ifa->px_pos_beg = i;
1412

    
1413
    if ((ifa->type == OSPF_IT_BCAST) ||
1414
        (ifa->type == OSPF_IT_NBMA))
1415
      net_lsa = bcast_net_active(ifa);
1416
    else
1417
      net_lsa = 0;
1418

    
1419
    struct ifa *a;
1420
    WALK_LIST(a, ifa->iface->addrs)
1421
    {
1422
      if ((a->prefix.type != ospf_get_af(p)) ||
1423
          (a->flags & IA_SECONDARY) ||
1424
          (a->flags & IA_PEER) ||
1425
          (a->scope <= SCOPE_LINK))
1426
        continue;
1427

    
1428
      if (((a->prefix.pxlen < IP6_MAX_PREFIX_LENGTH) && net_lsa) ||
1429
          configured_stubnet(oa, a))
1430
        continue;
1431

    
1432
      if ((a->flags & IA_HOST) ||
1433
          (ifa->state == OSPF_IS_LOOP) ||
1434
          (ifa->type == OSPF_IT_PTMP))
1435
      {
1436
        net_addr_ip6 net = NET_ADDR_IP6(a->ip, IP6_MAX_PREFIX_LENGTH);
1437
        lsab_put_prefix(p, (net_addr *) &net, 0);
1438
        host_addr = 1;
1439
      }
1440
      else
1441
        lsab_put_prefix(p, &a->prefix, ifa->cost);
1442
      i++;
1443
    }
1444

    
1445
    ifa->px_pos_end = i;
1446
  }
1447

    
1448
  struct ospf_stubnet_config *sn;
1449
  WALK_LIST(sn, oa->ac->stubnet_list)
1450
    if (!sn->hidden)
1451
    {
1452
      lsab_put_prefix(p, &sn->prefix, sn->cost);
1453
      if (sn->prefix.pxlen == IP6_MAX_PREFIX_LENGTH)
1454
        host_addr = 1;
1455
      i++;
1456
    }
1457

    
1458
  /* If there are some configured vlinks, find some global address
1459
     (even from another area), which will be used as a vlink endpoint. */
1460
  if (!EMPTY_LIST(cf->vlink_list) && !host_addr && ospf_is_ip6(p))
1461
  {
1462
    WALK_LIST(ifa, p->iface_list)
1463
    {
1464
      if ((ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
1465
        continue;
1466

    
1467
      struct ifa *a;
1468
      WALK_LIST(a, ifa->iface->addrs)
1469
      {
1470
        if ((a->prefix.type != NET_IP6) ||
1471
            (a->flags & IA_SECONDARY) ||
1472
            (a->scope <= SCOPE_LINK))
1473
          continue;
1474

    
1475
        /* Found some IP */
1476
        net_addr_ip6 net = NET_ADDR_IP6(a->ip, IP6_MAX_PREFIX_LENGTH);
1477
        lsab_put_prefix(p, (net_addr *) &net, 0);
1478
        i++;
1479
        goto done;
1480
      }
1481
    }
1482
  }
1483

    
1484
 done:
1485
  lp = p->lsab;
1486
  lp->pxcount = i;
1487
}
1488

    
1489
static void
1490
ospf_originate_prefix_rt_lsa(struct ospf_proto *p, struct ospf_area *oa)
1491
{
1492
  if (ospf_is_v2(p))
1493
    return;
1494

    
1495
  struct ospf_new_lsa lsa = {
1496
    .type = LSA_T_PREFIX,
1497
    .dom  = oa->areaid,
1498
    .id   = 0
1499
  };
1500

    
1501
  prepare_prefix_rt_lsa_body(p, oa);
1502

    
1503
  ospf_originate_lsa(p, &lsa);
1504
}
1505

    
1506

    
1507
/*
1508
 *        Prefix-Net-LSA handling (assume OSPFv3)
1509
 *        Type = LSA_T_PREFIX, referred type = LSA_T_NET
1510
 */
1511

    
1512
static inline int
1513
prefix_space(u32 *buf)
1514
{
1515
  int pxl = *buf >> 24;
1516
  return IPV6_PREFIX_SPACE(pxl);
1517
}
1518

    
1519
static inline int
1520
prefix_same(u32 *b1, u32 *b2)
1521
{
1522
  int pxl1 = *b1 >> 24;
1523
  int pxl2 = *b2 >> 24;
1524
  int pxs, i;
1525

    
1526
  if (pxl1 != pxl2)
1527
    return 0;
1528

    
1529
  pxs = IPV6_PREFIX_WORDS(pxl1);
1530
  for (i = 1; i < pxs; i++)
1531
    if (b1[i] != b2[i])
1532
      return 0;
1533

    
1534
  return 1;
1535
}
1536

    
1537
static inline u32 *
1538
prefix_advance(u32 *buf)
1539
{
1540
  int pxl = *buf >> 24;
1541
  return buf + IPV6_PREFIX_WORDS(pxl);
1542
}
1543

    
1544
/* FIXME eliminate items with LA bit set? see 4.4.3.9 */
1545
static void
1546
add_prefix(struct ospf_proto *p, u32 *px, int offset, int *pxc)
1547
{
1548
  u32 *pxl = lsab_offset(p, offset);
1549
  int i;
1550
  for (i = 0; i < *pxc; pxl = prefix_advance(pxl), i++)
1551
    if (prefix_same(px, pxl))
1552
    {
1553
      /* Options should be logically OR'ed together */
1554
      *pxl |= (*px & 0x00FF0000);
1555
      return;
1556
    }
1557

    
1558
  ASSERT(pxl == lsab_end(p));
1559

    
1560
  int pxspace = prefix_space(px);
1561
  pxl = lsab_alloc(p, pxspace);
1562
  memcpy(pxl, px, pxspace);
1563
  *pxl &= 0xFFFF0000;        /* Set metric to zero */
1564
  (*pxc)++;
1565
}
1566

    
1567
static void
1568
add_link_lsa(struct ospf_proto *p, struct ospf_lsa_link *ll, int offset, int *pxc)
1569
{
1570
  u32 *pxb = ll->rest;
1571
  uint j;
1572

    
1573
  for (j = 0; j < ll->pxcount; pxb = prefix_advance(pxb), j++)
1574
  {
1575
    u8 pxlen = (pxb[0] >> 24);
1576
    u8 pxopts = (pxb[0] >> 16);
1577

    
1578
    /* Skip NU or LA prefixes */
1579
    if (pxopts & (OPT_PX_NU | OPT_PX_LA))
1580
      continue;
1581

    
1582
    /* Skip link-local prefixes */
1583
    if (ospf_is_ip6(p) && (pxlen >= 10) && ((pxb[1] & 0xffc00000) == 0xfe800000))
1584
      continue;
1585

    
1586
    add_prefix(p, pxb, offset, pxc);
1587
  }
1588
}
1589

    
1590
static void
1591
prepare_prefix_net_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
1592
{
1593
  struct ospf_lsa_prefix *lp;
1594
  struct ospf_neighbor *n;
1595
  struct top_hash_entry *en;
1596
  int pxc, offset;
1597

    
1598
  ASSERT(p->lsab_used == 0);
1599
  lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix));
1600
  lp->ref_type = LSA_T_NET;
1601
  lp->ref_id = ifa->net_lsa->lsa.id;
1602
  lp->ref_rt = p->router_id;
1603
  lp = NULL; /* buffer might be reallocated later */
1604

    
1605
  pxc = 0;
1606
  offset = p->lsab_used;
1607

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

    
1612
  WALK_LIST(n, ifa->neigh_list)
1613
    if ((n->state == NEIGHBOR_FULL) &&
1614
        (en = ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK)))
1615
      add_link_lsa(p, en->lsa_body, offset, &pxc);
1616

    
1617
  lp = p->lsab;
1618
  lp->pxcount = pxc;
1619
}
1620

    
1621
static void
1622
ospf_originate_prefix_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
1623
{
1624
  if (ospf_is_v2(p))
1625
    return;
1626

    
1627
  struct ospf_new_lsa lsa = {
1628
    .type = LSA_T_PREFIX,
1629
    .dom  = ifa->oa->areaid,
1630
    .id   = ifa->iface_id,
1631
    .ifa  = ifa
1632
  };
1633

    
1634
  prepare_prefix_net_lsa_body(p, ifa);
1635

    
1636
  ifa->pxn_lsa = ospf_originate_lsa(p, &lsa);
1637
}
1638

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

    
1642
void
1643
ospf_update_topology(struct ospf_proto *p)
1644
{
1645
  struct ospf_area *oa;
1646
  struct ospf_iface *ifa;
1647

    
1648
  WALK_LIST(oa, p->area_list)
1649
  {
1650
    if (oa->update_rt_lsa)
1651
    {
1652
      /*
1653
       * Generally, MinLSInterval is enforced in ospf_do_originate_lsa(), but
1654
       * origination of (prefix) router LSA is a special case. We do not want to
1655
       * prepare a new router LSA body and then postpone it in en->next_lsa_body
1656
       * for later origination, because there are side effects (updates of
1657
       * rt_pos_* and px_pos_* in ospf_iface structures) during that, which may
1658
       * confuse routing table calculation if executed after LSA body
1659
       * preparation but before final LSA origination (as rtcalc would use
1660
       * current rt_pos_* indexes but the old router LSA body).
1661
       *
1662
       * Here, we ensure that MinLSInterval is observed and we do not even try
1663
       * to originate these LSAs if it is not. Therefore, origination, when
1664
       * requested, will succeed unless there is also a seqnum wrapping, which
1665
       * is not a problem because in that case rtcalc is blocked by MaxAge.
1666
       */
1667

    
1668
      if (breaks_minlsinterval(oa->rt) || breaks_minlsinterval(oa->pxr_lsa))
1669
        continue;
1670

    
1671
      ospf_originate_rt_lsa(p, oa);
1672
      ospf_originate_prefix_rt_lsa(p, oa);
1673
      oa->update_rt_lsa = 0;
1674
    }
1675
  }
1676

    
1677
  WALK_LIST(ifa, p->iface_list)
1678
  {
1679
    if (ifa->type == OSPF_IT_VLINK)
1680
      continue;
1681

    
1682
    if (ifa->update_link_lsa)
1683
    {
1684
      if ((ifa->state > OSPF_IS_LOOP) && !ifa->link_lsa_suppression)
1685
        ospf_originate_link_lsa(p, ifa);
1686
      else
1687
        ospf_flush2_lsa(p, &ifa->link_lsa);
1688

    
1689
      ifa->update_link_lsa = 0;
1690
    }
1691

    
1692
    if (ifa->update_net_lsa)
1693
    {
1694
      if ((ifa->state == OSPF_IS_DR) && (ifa->fadj > 0))
1695
      {
1696
        ospf_originate_net_lsa(p, ifa);
1697
        ospf_originate_prefix_net_lsa(p, ifa);
1698
      }
1699
      else
1700
      {
1701
        ospf_flush2_lsa(p, &ifa->net_lsa);
1702
        ospf_flush2_lsa(p, &ifa->pxn_lsa);
1703
      }
1704

    
1705
      ifa->update_net_lsa = 0;
1706
    }
1707
  }
1708
}
1709

    
1710

    
1711
static void
1712
ospf_top_ht_alloc(struct top_graph *f)
1713
{
1714
  f->hash_size = 1 << f->hash_order;
1715
  f->hash_mask = f->hash_size - 1;
1716
  if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
1717
    f->hash_entries_max = ~0;
1718
  else
1719
    f->hash_entries_max = f->hash_size HASH_HI_MARK;
1720
  if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
1721
    f->hash_entries_min = 0;
1722
  else
1723
    f->hash_entries_min = f->hash_size HASH_LO_MARK;
1724
  DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
1725
      f->hash_order, f->hash_size, f->hash_entries_min, f->hash_entries_max);
1726
  f->hash_table =
1727
    mb_alloc(f->pool, f->hash_size * sizeof(struct top_hash_entry *));
1728
  bzero(f->hash_table, f->hash_size * sizeof(struct top_hash_entry *));
1729
}
1730

    
1731
static inline void
1732
ospf_top_ht_free(struct top_hash_entry **h)
1733
{
1734
  mb_free(h);
1735
}
1736

    
1737
static inline u32
1738
ospf_top_hash_u32(u32 a)
1739
{
1740
  /* Shamelessly stolen from IP address hashing in ipv4.h */
1741
  a ^= a >> 16;
1742
  a ^= a << 10;
1743
  return a;
1744
}
1745

    
1746
static uint
1747
ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type)
1748
{
1749
  /* In OSPFv2, we don't know Router ID when looking for network LSAs.
1750
     In OSPFv3, we don't know LSA ID when looking for router LSAs.
1751
     In both cases, there is (usually) just one (or small number)
1752
     appropriate LSA, so we just clear unknown part of key. */
1753

    
1754
  return (((f->ospf2 && (type == LSA_T_NET)) ? 0 : ospf_top_hash_u32(rtrid)) +
1755
          ((!f->ospf2 && (type == LSA_T_RT)) ? 0 : ospf_top_hash_u32(lsaid)) +
1756
          type + domain) & f->hash_mask;
1757

    
1758
  /*
1759
  return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
1760
          type + areaid) & f->hash_mask;
1761
  */
1762
}
1763

    
1764
/**
1765
 * ospf_top_new - allocated new topology database
1766
 * @p: OSPF protocol instance
1767
 * @pool: pool for allocation
1768
 *
1769
 * This dynamically hashed structure is used for keeping LSAs. Mainly it is used
1770
 * for the LSA database of the OSPF protocol, but also for LSA retransmission
1771
 * and request lists of OSPF neighbors.
1772
 */
1773
struct top_graph *
1774
ospf_top_new(struct ospf_proto *p, pool *pool)
1775
{
1776
  struct top_graph *f;
1777

    
1778
  f = mb_allocz(pool, sizeof(struct top_graph));
1779
  f->pool = pool;
1780
  f->hash_slab = sl_new(f->pool, sizeof(struct top_hash_entry));
1781
  f->hash_order = HASH_DEF_ORDER;
1782
  ospf_top_ht_alloc(f);
1783
  f->hash_entries = 0;
1784
  f->hash_entries_min = 0;
1785
  f->ospf2 = ospf_is_v2(p);
1786
  return f;
1787
}
1788

    
1789
void
1790
ospf_top_free(struct top_graph *f)
1791
{
1792
  rfree(f->hash_slab);
1793
  ospf_top_ht_free(f->hash_table);
1794
  mb_free(f);
1795
}
1796

    
1797
static void
1798
ospf_top_rehash(struct top_graph *f, int step)
1799
{
1800
  struct top_hash_entry **n, **oldt, **newt, *e, *x;
1801
  uint oldn, oldh;
1802

    
1803
  oldn = f->hash_size;
1804
  oldt = f->hash_table;
1805
  DBG("re-hashing topology hash from order %d to %d\n", f->hash_order,
1806
      f->hash_order + step);
1807
  f->hash_order += step;
1808
  ospf_top_ht_alloc(f);
1809
  newt = f->hash_table;
1810

    
1811
  for (oldh = 0; oldh < oldn; oldh++)
1812
  {
1813
    e = oldt[oldh];
1814
    while (e)
1815
    {
1816
      x = e->next;
1817
      n = newt + ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type);
1818
      e->next = *n;
1819
      *n = e;
1820
      e = x;
1821
    }
1822
  }
1823
  ospf_top_ht_free(oldt);
1824
}
1825

    
1826
static struct top_hash_entry *
1827
ospf_hash_find_(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1828
{
1829
  struct top_hash_entry *e;
1830
  e = f->hash_table[ospf_top_hash(f, domain, lsa, rtr, type)];
1831

    
1832
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr ||
1833
               e->lsa_type != type || e->domain != domain))
1834
    e = e->next;
1835

    
1836
  return e;
1837
}
1838

    
1839
struct top_hash_entry *
1840
ospf_hash_find(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1841
{
1842
  struct top_hash_entry *e = ospf_hash_find_(f, domain, lsa, rtr, type);
1843

    
1844
  /* Hide hash entry with empty lsa_body */
1845
  return (e && e->lsa_body) ? e : NULL;
1846
}
1847

    
1848
/* In OSPFv2, lsa.id is the same as lsa.rt for router LSA. In OSPFv3, we don't know
1849
   lsa.id when looking for router LSAs. We return matching LSA with smallest lsa.id. */
1850
struct top_hash_entry *
1851
ospf_hash_find_rt(struct top_graph *f, u32 domain, u32 rtr)
1852
{
1853
  struct top_hash_entry *rv = NULL;
1854
  struct top_hash_entry *e;
1855
  /* We can put rtr for lsa.id to hash fn, it is ignored in OSPFv3 */
1856
  e = f->hash_table[ospf_top_hash(f, domain, rtr, rtr, LSA_T_RT)];
1857

    
1858
  while (e)
1859
  {
1860
    if (e->lsa.rt == rtr && e->lsa_type == LSA_T_RT && e->domain == domain && e->lsa_body)
1861
    {
1862
      if (f->ospf2 && (e->lsa.id == rtr))
1863
        return e;
1864
      if (!f->ospf2 && (!rv || e->lsa.id < rv->lsa.id))
1865
        rv = e;
1866
    }
1867
    e = e->next;
1868
  }
1869

    
1870
  return rv;
1871
}
1872

    
1873
/*
1874
 * ospf_hash_find_rt3_first() and ospf_hash_find_rt3_next() are used exclusively
1875
 * for lsa_walk_rt_init(), lsa_walk_rt(), therefore they skip MaxAge entries.
1876
 */
1877
static inline struct top_hash_entry *
1878
find_matching_rt3(struct top_hash_entry *e, u32 domain, u32 rtr)
1879
{
1880
  while (e && (e->lsa.rt != rtr || e->lsa_type != LSA_T_RT ||
1881
               e->domain != domain || e->lsa.age == LSA_MAXAGE))
1882
    e = e->next;
1883
  return e;
1884
}
1885

    
1886
struct top_hash_entry *
1887
ospf_hash_find_rt3_first(struct top_graph *f, u32 domain, u32 rtr)
1888
{
1889
  struct top_hash_entry *e;
1890
  e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)];
1891
  return find_matching_rt3(e, domain, rtr);
1892
}
1893

    
1894
struct top_hash_entry *
1895
ospf_hash_find_rt3_next(struct top_hash_entry *e)
1896
{
1897
  return find_matching_rt3(e->next, e->domain, e->lsa.rt);
1898
}
1899

    
1900
/* In OSPFv2, we don't know Router ID when looking for network LSAs.
1901
   There should be just one, so we find any match. */
1902
struct top_hash_entry *
1903
ospf_hash_find_net2(struct top_graph *f, u32 domain, u32 id)
1904
{
1905
  struct top_hash_entry *e;
1906
  e = f->hash_table[ospf_top_hash(f, domain, id, 0, LSA_T_NET)];
1907

    
1908
  while (e && (e->lsa.id != id || e->lsa_type != LSA_T_NET ||
1909
               e->domain != domain || e->lsa_body == NULL))
1910
    e = e->next;
1911

    
1912
  return e;
1913
}
1914

    
1915

    
1916
struct top_hash_entry *
1917
ospf_hash_get(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1918
{
1919
  struct top_hash_entry **ee;
1920
  struct top_hash_entry *e;
1921

    
1922
  ee = f->hash_table + ospf_top_hash(f, domain, lsa, rtr, type);
1923
  e = *ee;
1924

    
1925
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr ||
1926
               e->lsa_type != type || e->domain != domain))
1927
    e = e->next;
1928

    
1929
  if (e)
1930
    return e;
1931

    
1932
  e = sl_alloc(f->hash_slab);
1933
  bzero(e, sizeof(struct top_hash_entry));
1934

    
1935
  e->color = OUTSPF;
1936
  e->dist = LSINFINITY;
1937
  e->lsa.type_raw = type;
1938
  e->lsa.id = lsa;
1939
  e->lsa.rt = rtr;
1940
  e->lsa.sn = LSA_ZEROSEQNO;
1941
  e->lsa_type = type;
1942
  e->domain = domain;
1943
  e->next = *ee;
1944
  *ee = e;
1945
  if (f->hash_entries++ > f->hash_entries_max)
1946
    ospf_top_rehash(f, HASH_HI_STEP);
1947
  return e;
1948
}
1949

    
1950
void
1951
ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
1952
{
1953
  struct top_hash_entry **ee = f->hash_table +
1954
    ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type);
1955

    
1956
  while (*ee)
1957
  {
1958
    if (*ee == e)
1959
    {
1960
      *ee = e->next;
1961
      sl_free(f->hash_slab, e);
1962
      if (f->hash_entries-- < f->hash_entries_min)
1963
        ospf_top_rehash(f, -HASH_LO_STEP);
1964
      return;
1965
    }
1966
    ee = &((*ee)->next);
1967
  }
1968
  bug("ospf_hash_delete() called for invalid node");
1969
}
1970

    
1971
/*
1972
static void
1973
ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
1974
{
1975

1976
  struct ospf_lsa_rt *rt = NULL;
1977
  struct ospf_lsa_rt_link *rr = NULL;
1978
  struct ospf_lsa_net *ln = NULL;
1979
  u32 *rts = NULL;
1980
  u32 i, max;
1981

1982
  OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
1983
             he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
1984
             he->lsa.checksum, he->domain);
1985

1986

1987
  switch (he->lsa.type)
1988
    {
1989
    case LSA_T_RT:
1990
      rt = he->lsa_body;
1991
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
1992

1993
      for (i = 0; i < lsa_rt_items(&he->lsa); i++)
1994
        OSPF_TRACE(D_EVENTS, "  - %1x %-1R %-1R %5u",
1995
                   rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
1996
      break;
1997

1998
    case LSA_T_NET:
1999
      ln = he->lsa_body;
2000
      rts = (u32 *) (ln + 1);
2001

2002
      for (i = 0; i < lsa_net_items(&he->lsa); i++)
2003
        OSPF_TRACE(D_EVENTS, "  - %-1R", rts[i]);
2004
      break;
2005

2006
    default:
2007
      break;
2008
    }
2009
}
2010

2011
void
2012
ospf_top_dump(struct top_graph *f, struct proto *p)
2013
{
2014
  uint i;
2015
  OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
2016

2017
  for (i = 0; i < f->hash_size; i++)
2018
  {
2019
    struct top_hash_entry *e;
2020
    for (e = f->hash_table[i]; e != NULL; e = e->next)
2021
      ospf_dump_lsa(e, p);
2022
  }
2023
}
2024
*/