Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / topology.c @ 74c838a8

History | View | Annotate | Download (51.3 KB)

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

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

    
15
#include "ospf.h"
16

    
17

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

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

    
29

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

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

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

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

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

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

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

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

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

    
88
  return en;
89
}
90

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

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

    
126
      mb_free(body);
127

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

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

    
553
    return nf->lsa_id;
554
  }
555

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

    
560
  if ((pxlen == 0) || (pxlen == 32))
561
    return id;
562

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

    
569

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

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

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

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

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

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

    
619

    
620
/*
621
 *        Router-LSA handling
622
 *        Type = LSA_T_RT
623
 */
624

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

    
644
  return 0;
645
}
646

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

    
652
  if (ifa->state == OSPF_IS_WAITING)
653
    return 0;
654

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

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

    
667
  return 0;
668
}
669

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

    
675
  if (p->areano > 1)
676
    opts |= OPT_RT_B;
677

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

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

    
684
  if (bitv)
685
    opts |= OPT_RT_V;
686

    
687
  return opts;
688
}
689

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

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

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

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

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

    
725
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
726
      continue;
727

    
728
    ifa->rt_pos_beg = i;
729

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

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

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

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

    
772
    ifa->rt_pos_end = i;
773

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

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

    
791
    ifa->rt_pos_end = i;
792
  }
793

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

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

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

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

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

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

    
839
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
840
      continue;
841

    
842
    ifa->rt_pos_beg = i;
843

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

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

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

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

    
871
    ifa->rt_pos_end = i;
872
  }
873

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

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

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

    
890
  if (ospf_is_v2(p))
891
    prepare_rt2_lsa_body(p, oa);
892
  else
893
    prepare_rt3_lsa_body(p, oa);
894

    
895
  oa->rt = ospf_originate_lsa(p, &lsa);
896
}
897

    
898

    
899
/*
900
 *        Net-LSA handling
901
 *        Type = LSA_T_NET
902
 */
903

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

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

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

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

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

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

    
940
  net->routers[0] = p->router_id;
941

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

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

    
952
      if (en)
953
        options |= ((struct ospf_lsa_link *) en->lsa_body)->options;
954

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

    
961
  net->optx = options & LSA_OPTIONS_MASK;
962
}
963

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

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

    
977
  if (ospf_is_v2(p))
978
    prepare_net2_lsa_body(p, ifa);
979
  else
980
    prepare_net3_lsa_body(p, ifa);
981

    
982
  ifa->net_lsa = ospf_originate_lsa(p, &lsa);
983
}
984

    
985

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

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

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

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

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

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

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

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

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

    
1041
  ospf_originate_lsa(p, &lsa);
1042
}
1043

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

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

    
1060
  ospf_originate_lsa(p, &lsa);
1061
}
1062

    
1063

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

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

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

    
1081
  if (ebit)
1082
    ext->metric |= LSA_EXT2_EBIT;
1083
}
1084

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

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

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

    
1101
  if (ebit)
1102
    ext->metric |= LSA_EXT3_EBIT;
1103

    
1104
  if (ipa_nonzero(fwaddr))
1105
  {
1106
    ext->metric |= LSA_EXT3_FBIT;
1107
    buf = ospf_put_ipv6_addr(buf, fwaddr);
1108
  }
1109

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

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

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

    
1153
  ospf_originate_lsa(p, &lsa);
1154
}
1155

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

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

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

    
1168
  en = ospf_hash_find_(p->gr, dom, id, p->router_id, type);
1169

    
1170
  if (!en || (en->nf != nf))
1171
    return;
1172

    
1173
  ospf_flush_lsa(p, en);
1174
}
1175

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

    
1181
  if (ipa_zero(gw) || ipa_is_link_local(gw))
1182
    return 0;
1183

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

    
1189
  return 0;
1190
}
1191

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

    
1199
  /* RFC 3101 2.3 - surrogate forwarding address selection */
1200

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

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

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

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

    
1240
  return cur_addr ? cur_addr->ip : IPA_NONE;
1241
}
1242

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

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

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

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

    
1265
    if (!nf || !nf->external_rte)
1266
      return;
1267

    
1268
    ospf_flush_ext_lsa(p, oa, nf);
1269
    nf->external_rte = 0;
1270

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

    
1275
    return;
1276
  }
1277

    
1278
  ASSERT(p->asbr);
1279

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

    
1289

    
1290
  if ((a->dest == RTD_ROUTER) && use_gw_for_fwaddr(p, a->gw, a->iface))
1291
    fwd = a->gw;
1292

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

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

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

    
1311

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

    
1317
static inline void
1318
lsab_put_prefix(struct ospf_proto *p, net_addr *net, u32 cost)
1319
{
1320
  void *buf = lsab_alloc(p, IPV6_PREFIX_SPACE(net6_pxlen(net)));
1321
  u8 flags = (net6_pxlen(net) < IP6_MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
1322
  ospf_put_ipv6_prefix(buf, net, flags, cost);
1323
}
1324

    
1325
static void
1326
prepare_link_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
1327
{
1328
  struct ospf_lsa_link *ll;
1329
  int i = 0;
1330

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

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

    
1345
    lsab_put_prefix(p, &a->prefix, 0);
1346
    i++;
1347
  }
1348

    
1349
  ll = p->lsab;
1350
  ll->pxcount = i;
1351
}
1352

    
1353
static void
1354
ospf_originate_link_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
1355
{
1356
  if (ospf_is_v2(p))
1357
    return;
1358

    
1359
  struct ospf_new_lsa lsa = {
1360
    .type = LSA_T_LINK,
1361
    .dom  = ifa->iface_id,
1362
    .id   = ifa->iface_id,
1363
    .ifa  = ifa
1364
  };
1365

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

    
1368
  prepare_link_lsa_body(p, ifa);
1369

    
1370
  ifa->link_lsa = ospf_originate_lsa(p, &lsa);
1371
}
1372

    
1373

    
1374
/*
1375
 *        Prefix-Rt-LSA handling (assume OSPFv3)
1376
 *        Type = LSA_T_PREFIX, referred type = LSA_T_RT
1377
 */
1378

    
1379
static void
1380
prepare_prefix_rt_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
1381
{
1382
  struct ospf_config *cf = (struct ospf_config *) (p->p.cf);
1383
  struct ospf_iface *ifa;
1384
  struct ospf_lsa_prefix *lp;
1385
  int host_addr = 0;
1386
  int net_lsa;
1387
  int i = 0;
1388

    
1389
  ASSERT(p->lsab_used == 0);
1390
  lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix));
1391
  lp->ref_type = LSA_T_RT;
1392
  lp->ref_id = 0;
1393
  lp->ref_rt = p->router_id;
1394
  lp = NULL; /* buffer might be reallocated later */
1395

    
1396
  WALK_LIST(ifa, p->iface_list)
1397
  {
1398
    if ((ifa->oa != oa) || (ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
1399
      continue;
1400

    
1401
    ifa->px_pos_beg = i;
1402

    
1403
    if ((ifa->type == OSPF_IT_BCAST) ||
1404
        (ifa->type == OSPF_IT_NBMA))
1405
      net_lsa = bcast_net_active(ifa);
1406
    else
1407
      net_lsa = 0;
1408

    
1409
    struct ifa *a;
1410
    WALK_LIST(a, ifa->iface->addrs)
1411
    {
1412
      if ((a->prefix.type != NET_IP6) ||
1413
          (a->flags & IA_SECONDARY) ||
1414
          (a->flags & IA_PEER) ||
1415
          (a->scope <= SCOPE_LINK))
1416
        continue;
1417

    
1418
      if (((a->prefix.pxlen < IP6_MAX_PREFIX_LENGTH) && net_lsa) ||
1419
          configured_stubnet(oa, a))
1420
        continue;
1421

    
1422
      if ((a->flags & IA_HOST) ||
1423
          (ifa->state == OSPF_IS_LOOP) ||
1424
          (ifa->type == OSPF_IT_PTMP))
1425
      {
1426
        net_addr_ip6 net = NET_ADDR_IP6(a->ip, IP6_MAX_PREFIX_LENGTH);
1427
        lsab_put_prefix(p, (net_addr *) &net, 0);
1428
        host_addr = 1;
1429
      }
1430
      else
1431
        lsab_put_prefix(p, &a->prefix, ifa->cost);
1432
      i++;
1433
    }
1434

    
1435
    ifa->px_pos_end = i;
1436
  }
1437

    
1438
  struct ospf_stubnet_config *sn;
1439
  WALK_LIST(sn, oa->ac->stubnet_list)
1440
    if (!sn->hidden)
1441
    {
1442
      lsab_put_prefix(p, &sn->prefix, sn->cost);
1443
      if (sn->prefix.pxlen == IP6_MAX_PREFIX_LENGTH)
1444
        host_addr = 1;
1445
      i++;
1446
    }
1447

    
1448
  /* If there are some configured vlinks, find some global address
1449
     (even from another area), which will be used as a vlink endpoint. */
1450
  if (!EMPTY_LIST(cf->vlink_list) && !host_addr)
1451
  {
1452
    WALK_LIST(ifa, p->iface_list)
1453
    {
1454
      if ((ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
1455
        continue;
1456

    
1457
      struct ifa *a;
1458
      WALK_LIST(a, ifa->iface->addrs)
1459
      {
1460
        if ((a->prefix.type != NET_IP6) ||
1461
            (a->flags & IA_SECONDARY) ||
1462
            (a->scope <= SCOPE_LINK))
1463
          continue;
1464

    
1465
        /* Found some IP */
1466
        net_addr_ip6 net = NET_ADDR_IP6(a->ip, IP6_MAX_PREFIX_LENGTH);
1467
        lsab_put_prefix(p, (net_addr *) &net, 0);
1468
        i++;
1469
        goto done;
1470
      }
1471
    }
1472
  }
1473

    
1474
 done:
1475
  lp = p->lsab;
1476
  lp->pxcount = i;
1477
}
1478

    
1479
static void
1480
ospf_originate_prefix_rt_lsa(struct ospf_proto *p, struct ospf_area *oa)
1481
{
1482
  if (ospf_is_v2(p))
1483
    return;
1484

    
1485
  struct ospf_new_lsa lsa = {
1486
    .type = LSA_T_PREFIX,
1487
    .dom  = oa->areaid,
1488
    .id   = 0
1489
  };
1490

    
1491
  prepare_prefix_rt_lsa_body(p, oa);
1492

    
1493
  ospf_originate_lsa(p, &lsa);
1494
}
1495

    
1496

    
1497
/*
1498
 *        Prefix-Net-LSA handling (assume OSPFv3)
1499
 *        Type = LSA_T_PREFIX, referred type = LSA_T_NET
1500
 */
1501

    
1502
static inline int
1503
prefix_space(u32 *buf)
1504
{
1505
  int pxl = *buf >> 24;
1506
  return IPV6_PREFIX_SPACE(pxl);
1507
}
1508

    
1509
static inline int
1510
prefix_same(u32 *b1, u32 *b2)
1511
{
1512
  int pxl1 = *b1 >> 24;
1513
  int pxl2 = *b2 >> 24;
1514
  int pxs, i;
1515

    
1516
  if (pxl1 != pxl2)
1517
    return 0;
1518

    
1519
  pxs = IPV6_PREFIX_WORDS(pxl1);
1520
  for (i = 1; i < pxs; i++)
1521
    if (b1[i] != b2[i])
1522
      return 0;
1523

    
1524
  return 1;
1525
}
1526

    
1527
static inline u32 *
1528
prefix_advance(u32 *buf)
1529
{
1530
  int pxl = *buf >> 24;
1531
  return buf + IPV6_PREFIX_WORDS(pxl);
1532
}
1533

    
1534
/* FIXME eliminate items with LA bit set? see 4.4.3.9 */
1535
static void
1536
add_prefix(struct ospf_proto *p, u32 *px, int offset, int *pxc)
1537
{
1538
  u32 *pxl = lsab_offset(p, offset);
1539
  int i;
1540
  for (i = 0; i < *pxc; pxl = prefix_advance(pxl), i++)
1541
    if (prefix_same(px, pxl))
1542
    {
1543
      /* Options should be logically OR'ed together */
1544
      *pxl |= (*px & 0x00FF0000);
1545
      return;
1546
    }
1547

    
1548
  ASSERT(pxl == lsab_end(p));
1549

    
1550
  int pxspace = prefix_space(px);
1551
  pxl = lsab_alloc(p, pxspace);
1552
  memcpy(pxl, px, pxspace);
1553
  *pxl &= 0xFFFF0000;        /* Set metric to zero */
1554
  (*pxc)++;
1555
}
1556

    
1557
static void
1558
add_link_lsa(struct ospf_proto *p, struct ospf_lsa_link *ll, int offset, int *pxc)
1559
{
1560
  u32 *pxb = ll->rest;
1561
  int j;
1562

    
1563
  for (j = 0; j < ll->pxcount; pxb = prefix_advance(pxb), j++)
1564
  {
1565
    u8 pxlen = (pxb[0] >> 24);
1566
    u8 pxopts = (pxb[0] >> 16);
1567

    
1568
    /* Skip NU or LA prefixes */
1569
    if (pxopts & (OPT_PX_NU | OPT_PX_LA))
1570
      continue;
1571

    
1572
    /* Skip link-local prefixes */
1573
    if ((pxlen >= 10) && ((pxb[1] & 0xffc00000) == 0xfe800000))
1574
      continue;
1575

    
1576
    add_prefix(p, pxb, offset, pxc);
1577
  }
1578
}
1579

    
1580
static void
1581
prepare_prefix_net_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
1582
{
1583
  struct ospf_lsa_prefix *lp;
1584
  struct ospf_neighbor *n;
1585
  struct top_hash_entry *en;
1586
  int pxc, offset;
1587

    
1588
  ASSERT(p->lsab_used == 0);
1589
  lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix));
1590
  lp->ref_type = LSA_T_NET;
1591
  lp->ref_id = ifa->net_lsa->lsa.id;
1592
  lp->ref_rt = p->router_id;
1593
  lp = NULL; /* buffer might be reallocated later */
1594

    
1595
  pxc = 0;
1596
  offset = p->lsab_used;
1597

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

    
1602
  WALK_LIST(n, ifa->neigh_list)
1603
    if ((n->state == NEIGHBOR_FULL) &&
1604
        (en = ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK)))
1605
      add_link_lsa(p, en->lsa_body, offset, &pxc);
1606

    
1607
  lp = p->lsab;
1608
  lp->pxcount = pxc;
1609
}
1610

    
1611
static void
1612
ospf_originate_prefix_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
1613
{
1614
  if (ospf_is_v2(p))
1615
    return;
1616

    
1617
  struct ospf_new_lsa lsa = {
1618
    .type = LSA_T_PREFIX,
1619
    .dom  = ifa->oa->areaid,
1620
    .id   = ifa->iface_id,
1621
    .ifa  = ifa
1622
  };
1623

    
1624
  prepare_prefix_net_lsa_body(p, ifa);
1625

    
1626
  ifa->pxn_lsa = ospf_originate_lsa(p, &lsa);
1627
}
1628

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

    
1632
void
1633
ospf_update_topology(struct ospf_proto *p)
1634
{
1635
  struct ospf_area *oa;
1636
  struct ospf_iface *ifa;
1637

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

    
1658
      if (breaks_minlsinterval(oa->rt) || breaks_minlsinterval(oa->pxr_lsa))
1659
        continue;
1660

    
1661
      ospf_originate_rt_lsa(p, oa);
1662
      ospf_originate_prefix_rt_lsa(p, oa);
1663
      oa->update_rt_lsa = 0;
1664
    }
1665
  }
1666

    
1667
  WALK_LIST(ifa, p->iface_list)
1668
  {
1669
    if (ifa->type == OSPF_IT_VLINK)
1670
      continue;
1671

    
1672
    if (ifa->update_link_lsa)
1673
    {
1674
      if ((ifa->state > OSPF_IS_LOOP) && !ifa->link_lsa_suppression)
1675
        ospf_originate_link_lsa(p, ifa);
1676
      else
1677
        ospf_flush2_lsa(p, &ifa->link_lsa);
1678

    
1679
      ifa->update_link_lsa = 0;
1680
    }
1681

    
1682
    if (ifa->update_net_lsa)
1683
    {
1684
      if ((ifa->state == OSPF_IS_DR) && (ifa->fadj > 0))
1685
      {
1686
        ospf_originate_net_lsa(p, ifa);
1687
        ospf_originate_prefix_net_lsa(p, ifa);
1688
      }
1689
      else
1690
      {
1691
        ospf_flush2_lsa(p, &ifa->net_lsa);
1692
        ospf_flush2_lsa(p, &ifa->pxn_lsa);
1693
      }
1694

    
1695
      ifa->update_net_lsa = 0;
1696
    }
1697
  }
1698
}
1699

    
1700

    
1701
static void
1702
ospf_top_ht_alloc(struct top_graph *f)
1703
{
1704
  f->hash_size = 1 << f->hash_order;
1705
  f->hash_mask = f->hash_size - 1;
1706
  if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
1707
    f->hash_entries_max = ~0;
1708
  else
1709
    f->hash_entries_max = f->hash_size HASH_HI_MARK;
1710
  if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
1711
    f->hash_entries_min = 0;
1712
  else
1713
    f->hash_entries_min = f->hash_size HASH_LO_MARK;
1714
  DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
1715
      f->hash_order, f->hash_size, f->hash_entries_min, f->hash_entries_max);
1716
  f->hash_table =
1717
    mb_alloc(f->pool, f->hash_size * sizeof(struct top_hash_entry *));
1718
  bzero(f->hash_table, f->hash_size * sizeof(struct top_hash_entry *));
1719
}
1720

    
1721
static inline void
1722
ospf_top_ht_free(struct top_hash_entry **h)
1723
{
1724
  mb_free(h);
1725
}
1726

    
1727
static inline u32
1728
ospf_top_hash_u32(u32 a)
1729
{
1730
  /* Shamelessly stolen from IP address hashing in ipv4.h */
1731
  a ^= a >> 16;
1732
  a ^= a << 10;
1733
  return a;
1734
}
1735

    
1736
static uint
1737
ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type)
1738
{
1739
  /* In OSPFv2, we don't know Router ID when looking for network LSAs.
1740
     In OSPFv3, we don't know LSA ID when looking for router LSAs.
1741
     In both cases, there is (usually) just one (or small number)
1742
     appropriate LSA, so we just clear unknown part of key. */
1743

    
1744
  return (((f->ospf2 && (type == LSA_T_NET)) ? 0 : ospf_top_hash_u32(rtrid)) +
1745
          ((!f->ospf2 && (type == LSA_T_RT)) ? 0 : ospf_top_hash_u32(lsaid)) +
1746
          type + domain) & f->hash_mask;
1747

    
1748
  /*
1749
  return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
1750
          type + areaid) & f->hash_mask;
1751
  */
1752
}
1753

    
1754
/**
1755
 * ospf_top_new - allocated new topology database
1756
 * @p: OSPF protocol instance
1757
 * @pool: pool for allocation
1758
 *
1759
 * This dynamically hashed structure is used for keeping LSAs. Mainly it is used
1760
 * for the LSA database of the OSPF protocol, but also for LSA retransmission
1761
 * and request lists of OSPF neighbors.
1762
 */
1763
struct top_graph *
1764
ospf_top_new(struct ospf_proto *p, pool *pool)
1765
{
1766
  struct top_graph *f;
1767

    
1768
  f = mb_allocz(pool, sizeof(struct top_graph));
1769
  f->pool = pool;
1770
  f->hash_slab = sl_new(f->pool, sizeof(struct top_hash_entry));
1771
  f->hash_order = HASH_DEF_ORDER;
1772
  ospf_top_ht_alloc(f);
1773
  f->hash_entries = 0;
1774
  f->hash_entries_min = 0;
1775
  f->ospf2 = ospf_is_v2(p);
1776
  return f;
1777
}
1778

    
1779
void
1780
ospf_top_free(struct top_graph *f)
1781
{
1782
  rfree(f->hash_slab);
1783
  ospf_top_ht_free(f->hash_table);
1784
  mb_free(f);
1785
}
1786

    
1787
static void
1788
ospf_top_rehash(struct top_graph *f, int step)
1789
{
1790
  struct top_hash_entry **n, **oldt, **newt, *e, *x;
1791
  uint oldn, oldh;
1792

    
1793
  oldn = f->hash_size;
1794
  oldt = f->hash_table;
1795
  DBG("re-hashing topology hash from order %d to %d\n", f->hash_order,
1796
      f->hash_order + step);
1797
  f->hash_order += step;
1798
  ospf_top_ht_alloc(f);
1799
  newt = f->hash_table;
1800

    
1801
  for (oldh = 0; oldh < oldn; oldh++)
1802
  {
1803
    e = oldt[oldh];
1804
    while (e)
1805
    {
1806
      x = e->next;
1807
      n = newt + ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type);
1808
      e->next = *n;
1809
      *n = e;
1810
      e = x;
1811
    }
1812
  }
1813
  ospf_top_ht_free(oldt);
1814
}
1815

    
1816
static struct top_hash_entry *
1817
ospf_hash_find_(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1818
{
1819
  struct top_hash_entry *e;
1820
  e = f->hash_table[ospf_top_hash(f, domain, lsa, rtr, type)];
1821

    
1822
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr ||
1823
               e->lsa_type != type || e->domain != domain))
1824
    e = e->next;
1825

    
1826
  return e;
1827
}
1828

    
1829
struct top_hash_entry *
1830
ospf_hash_find(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1831
{
1832
  struct top_hash_entry *e = ospf_hash_find_(f, domain, lsa, rtr, type);
1833

    
1834
  /* Hide hash entry with empty lsa_body */
1835
  return (e && e->lsa_body) ? e : NULL;
1836
}
1837

    
1838
/* In OSPFv2, lsa.id is the same as lsa.rt for router LSA. In OSPFv3, we don't know
1839
   lsa.id when looking for router LSAs. We return matching LSA with smallest lsa.id. */
1840
struct top_hash_entry *
1841
ospf_hash_find_rt(struct top_graph *f, u32 domain, u32 rtr)
1842
{
1843
  struct top_hash_entry *rv = NULL;
1844
  struct top_hash_entry *e;
1845
  /* We can put rtr for lsa.id to hash fn, it is ignored in OSPFv3 */
1846
  e = f->hash_table[ospf_top_hash(f, domain, rtr, rtr, LSA_T_RT)];
1847

    
1848
  while (e)
1849
  {
1850
    if (e->lsa.rt == rtr && e->lsa_type == LSA_T_RT && e->domain == domain && e->lsa_body)
1851
    {
1852
      if (f->ospf2 && (e->lsa.id == rtr))
1853
        return e;
1854
      if (!f->ospf2 && (!rv || e->lsa.id < rv->lsa.id))
1855
        rv = e;
1856
    }
1857
    e = e->next;
1858
  }
1859

    
1860
  return rv;
1861
}
1862

    
1863
/*
1864
 * ospf_hash_find_rt3_first() and ospf_hash_find_rt3_next() are used exclusively
1865
 * for lsa_walk_rt_init(), lsa_walk_rt(), therefore they skip MaxAge entries.
1866
 */
1867
static inline struct top_hash_entry *
1868
find_matching_rt3(struct top_hash_entry *e, u32 domain, u32 rtr)
1869
{
1870
  while (e && (e->lsa.rt != rtr || e->lsa_type != LSA_T_RT ||
1871
               e->domain != domain || e->lsa.age == LSA_MAXAGE))
1872
    e = e->next;
1873
  return e;
1874
}
1875

    
1876
struct top_hash_entry *
1877
ospf_hash_find_rt3_first(struct top_graph *f, u32 domain, u32 rtr)
1878
{
1879
  struct top_hash_entry *e;
1880
  e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)];
1881
  return find_matching_rt3(e, domain, rtr);
1882
}
1883

    
1884
struct top_hash_entry *
1885
ospf_hash_find_rt3_next(struct top_hash_entry *e)
1886
{
1887
  return find_matching_rt3(e->next, e->domain, e->lsa.rt);
1888
}
1889

    
1890
/* In OSPFv2, we don't know Router ID when looking for network LSAs.
1891
   There should be just one, so we find any match. */
1892
struct top_hash_entry *
1893
ospf_hash_find_net2(struct top_graph *f, u32 domain, u32 id)
1894
{
1895
  struct top_hash_entry *e;
1896
  e = f->hash_table[ospf_top_hash(f, domain, id, 0, LSA_T_NET)];
1897

    
1898
  while (e && (e->lsa.id != id || e->lsa_type != LSA_T_NET ||
1899
               e->domain != domain || e->lsa_body == NULL))
1900
    e = e->next;
1901

    
1902
  return e;
1903
}
1904

    
1905

    
1906
struct top_hash_entry *
1907
ospf_hash_get(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1908
{
1909
  struct top_hash_entry **ee;
1910
  struct top_hash_entry *e;
1911

    
1912
  ee = f->hash_table + ospf_top_hash(f, domain, lsa, rtr, type);
1913
  e = *ee;
1914

    
1915
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr ||
1916
               e->lsa_type != type || e->domain != domain))
1917
    e = e->next;
1918

    
1919
  if (e)
1920
    return e;
1921

    
1922
  e = sl_alloc(f->hash_slab);
1923
  bzero(e, sizeof(struct top_hash_entry));
1924

    
1925
  e->color = OUTSPF;
1926
  e->dist = LSINFINITY;
1927
  e->lsa.type_raw = type;
1928
  e->lsa.id = lsa;
1929
  e->lsa.rt = rtr;
1930
  e->lsa.sn = LSA_ZEROSEQNO;
1931
  e->lsa_type = type;
1932
  e->domain = domain;
1933
  e->next = *ee;
1934
  *ee = e;
1935
  if (f->hash_entries++ > f->hash_entries_max)
1936
    ospf_top_rehash(f, HASH_HI_STEP);
1937
  return e;
1938
}
1939

    
1940
void
1941
ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
1942
{
1943
  struct top_hash_entry **ee = f->hash_table +
1944
    ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type);
1945

    
1946
  while (*ee)
1947
  {
1948
    if (*ee == e)
1949
    {
1950
      *ee = e->next;
1951
      sl_free(f->hash_slab, e);
1952
      if (f->hash_entries-- < f->hash_entries_min)
1953
        ospf_top_rehash(f, -HASH_LO_STEP);
1954
      return;
1955
    }
1956
    ee = &((*ee)->next);
1957
  }
1958
  bug("ospf_hash_delete() called for invalid node");
1959
}
1960

    
1961
/*
1962
static void
1963
ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
1964
{
1965

1966
  struct ospf_lsa_rt *rt = NULL;
1967
  struct ospf_lsa_rt_link *rr = NULL;
1968
  struct ospf_lsa_net *ln = NULL;
1969
  u32 *rts = NULL;
1970
  u32 i, max;
1971

1972
  OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
1973
             he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
1974
             he->lsa.checksum, he->domain);
1975

1976

1977
  switch (he->lsa.type)
1978
    {
1979
    case LSA_T_RT:
1980
      rt = he->lsa_body;
1981
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
1982

1983
      for (i = 0; i < lsa_rt_items(&he->lsa); i++)
1984
        OSPF_TRACE(D_EVENTS, "  - %1x %-1R %-1R %5u",
1985
                   rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
1986
      break;
1987

1988
    case LSA_T_NET:
1989
      ln = he->lsa_body;
1990
      rts = (u32 *) (ln + 1);
1991

1992
      for (i = 0; i < lsa_net_items(&he->lsa); i++)
1993
        OSPF_TRACE(D_EVENTS, "  - %-1R", rts[i]);
1994
      break;
1995

1996
    default:
1997
      break;
1998
    }
1999
}
2000

2001
void
2002
ospf_top_dump(struct top_graph *f, struct proto *p)
2003
{
2004
  uint i;
2005
  OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
2006

2007
  for (i = 0; i < f->hash_size; i++)
2008
  {
2009
    struct top_hash_entry *e;
2010
    for (e = f->hash_table[i]; e != NULL; e = e->next)
2011
      ospf_dump_lsa(e, p);
2012
  }
2013
}
2014
*/