Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / topology.c @ 061ab802

History | View | Annotate | Download (35.8 KB)

1
/*
2
 *        BIRD -- OSPF Topological Database
3
 *
4
 *        (c) 1999       Martin Mares <mj@ucw.cz>
5
 *        (c) 1999--2004 Ondrej Filip <feela@network.cz>
6
 *
7
 *        Can be freely distributed and used under the terms of the GNU GPL.
8
 */
9

    
10
#include "nest/bird.h"
11
#include "lib/string.h"
12

    
13
#include "ospf.h"
14

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

    
23
void originate_prefix_rt_lsa(struct ospf_area *oa);
24
void originate_prefix_net_lsa(struct ospf_iface *ifa);
25
void flush_prefix_net_lsa(struct ospf_iface *ifa);
26

    
27
#ifdef OSPFv2
28
#define ipa_to_rid(x) _I(x)
29
#else /* OSPFv3 */
30
#define ipa_to_rid(x) _I3(x)
31
#endif
32

    
33
/* FIXME very ugly hack */
34
#ifdef OSPFv2
35
#define ipa_to_lsaid(x) _I(x)
36
#else /* OSPFv3 */
37
#define ipa_to_lsaid(x) _I0(x) ^ _I1(x) ^ _I2(x) ^ _I3(x)
38
#endif
39

    
40

    
41
static void *
42
lsab_alloc(struct proto_ospf *po, unsigned size)
43
{
44
  unsigned offset = po->lsab_used;
45
  po->lsab_used += size;
46
  if (po->lsab_used > po->lsab_size)
47
    {
48
      po->lsab_size = MAX(po->lsab_used, 2 * po->lsab_size);
49
      po->lsab = mb_realloc(po->proto.pool, po->lsab, po->lsab_size);
50
    }
51
  return ((byte *) po->lsab) + offset;
52
}
53

    
54
static inline void *
55
lsab_allocz(struct proto_ospf *po, unsigned size)
56
{
57
  void *r = lsab_alloc(po, size);
58
  bzero(r, size);
59
  return r;
60
}
61

    
62
static inline void *
63
lsab_flush(struct proto_ospf *po)
64
{
65
  void *r = mb_alloc(po->proto.pool, po->lsab_size);
66
  memcpy(r, po->lsab, po->lsab_used);
67
  po->lsab_used = 0;
68
  return r;
69
}
70

    
71
static inline void *
72
lsab_offset(struct proto_ospf *po, unsigned offset)
73
{
74
  return ((byte *) po->lsab) + offset;
75
}
76

    
77
static inline void *
78
lsab_end(struct proto_ospf *po)
79
{
80
  return ((byte *) po->lsab) + po->lsab_used;
81
}
82

    
83
#ifdef OSPFv3
84

    
85
#define IPV6_PREFIX_SPACE(x) ((((x) + 63) / 32) * 4)
86
#define IPV6_PREFIX_WORDS(x) (((x) + 63) / 32)
87

    
88
static inline u32 *
89
put_ipv6_prefix(u32 *buf, ip_addr addr, u8 pxlen, u8 pxopts, u16 lh)
90
{
91
  *buf++ = ((pxlen << 24) | (pxopts << 16) | lh);
92

    
93
  if (pxlen > 0)
94
    *buf++ = _I0(addr);
95
  if (pxlen > 32)
96
    *buf++ = _I1(addr);
97
  if (pxlen > 64)
98
    *buf++ = _I2(addr);
99
  if (pxlen > 96)
100
    *buf++ = _I3(addr);
101
  return buf;
102
}
103

    
104

    
105
static inline u32 *
106
put_ipv6_addr(u32 *buf, ip_addr addr)
107
{
108
  *(ip_addr *) buf = addr;
109
  return buf + 4;
110
}
111

    
112
#endif
113

    
114

    
115
static int
116
configured_stubnet(struct ospf_area *oa, struct ifa *a)
117
{
118
  struct ospf_stubnet_config *sn;
119
  WALK_LIST(sn, oa->ac->stubnet_list)
120
    {
121
      if (sn->summary)
122
        {
123
          if (ipa_in_net(a->prefix, sn->px.addr, sn->px.len) && (a->pxlen >= sn->px.len))
124
            return 1;
125
        }
126
      else
127
        {
128
          if (ipa_equal(a->prefix, sn->px.addr) && (a->pxlen == sn->px.len))
129
            return 1;
130
        }
131
    }
132
  return 0;
133
}
134

    
135
int
136
bcast_net_active(struct ospf_iface *ifa)
137
{
138
  struct ospf_neighbor *neigh;
139

    
140
  if (ifa->state == OSPF_IS_WAITING)
141
    return 0;
142

    
143
  WALK_LIST(neigh, ifa->neigh_list)
144
    {
145
      if (neigh->state == NEIGHBOR_FULL)
146
        {
147
          if (neigh->rid == ifa->drid)
148
            return 1;
149

    
150
          if (ifa->state == OSPF_IS_DR)
151
            return 1;
152
        }
153
    }
154

    
155
  return 0;
156
}
157

    
158

    
159
#ifdef OSPFv2
160

    
161
static void *
162
originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
163
{
164
  struct proto_ospf *po = oa->po;
165
  struct ospf_iface *ifa;
166
  int i = 0, bitv = 0;
167
  struct ospf_lsa_rt *rt;
168
  struct ospf_lsa_rt_link *ln;
169
  struct ospf_neighbor *neigh;
170

    
171
  DBG("%s: Originating RT_lsa body for area %R.\n", po->proto.name,
172
      oa->areaid);
173
    
174
  ASSERT(po->lsab_used == 0);
175
  rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt));
176

    
177
  rt->options = 0
178

    
179
  if (po->areano > 1)
180
    rt->options |= OPT_RT_B;
181

    
182
  if ((po->ebit) && (!oa->stub))
183
    rt->options |= OPT_RT_E;
184

    
185
  rt = NULL; /* buffer might be reallocated later */
186

    
187
  WALK_LIST(ifa, po->iface_list)
188
  {
189
    int master = 0;
190

    
191
    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
192
        (!EMPTY_LIST(ifa->neigh_list)))
193
    {
194
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
195
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
196
        bitv = 1;
197
    }
198

    
199
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
200
      continue;
201

    
202
    /* BIRD does not support interface loops */
203
    ASSERT(ifa->state != OSPF_IS_LOOP);
204

    
205
    switch (ifa->type)
206
      {
207
      case OSPF_IT_PTP:        /* RFC2328 - 12.4.1.1 */
208
        neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
209
        if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL))
210
        {
211
          ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
212
          ln->type = LSART_PTP;
213
          ln->id = neigh->rid;
214
          ln->data = (ifa->iface->addr->flags & IA_UNNUMBERED) ?
215
            ifa->iface->index : ipa_to_u32(ifa->iface->addr->ip);
216
          ln->metric = ifa->cost;
217
          ln->notos = 0;
218
          i++;
219
          master = 1;
220
        }
221
        break;
222

    
223
      case OSPF_IT_BCAST: /* RFC2328 - 12.4.1.2 */
224
      case OSPF_IT_NBMA:
225
        if (bcast_net_active(ifa))
226
          {
227
            ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
228
            ln->type = LSART_NET;
229
            ln->id = ipa_to_u32(ifa->drip);
230
            ln->data = ipa_to_u32(ifa->iface->addr->ip);
231
            ln->metric = ifa->cost;
232
            ln->notos = 0;
233
            i++;
234
            master = 1;
235
          }
236
        break;
237

    
238
      case OSPF_IT_VLINK: /* RFC2328 - 12.4.1.3 */
239
        neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
240
        if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
241
        {
242
          ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
243
          ln->type = LSART_VLNK;
244
          ln->id = neigh->rid;
245
          ln->data = ipa_to_u32(ifa->iface->addr->ip);
246
          ln->metric = ifa->cost;
247
          ln->notos = 0;
248
          i++;
249
          master = 1;
250
        }
251
        break;
252

    
253
      default:
254
        log("Unknown interface type %s", ifa->iface->name);
255
        break;
256
      }
257

    
258
    /* Now we will originate stub areas for interfaces addresses */
259
    struct ifa *a;
260
    WALK_LIST(a, ifa->iface->addrs)
261
      {
262
        if (((a == ifa->iface->addr) && master) ||
263
            (a->flags & IA_SECONDARY) ||
264
            (a->flags & IA_UNNUMBERED) ||
265
            configured_stubnet(oa, a))
266
          continue;
267

    
268

    
269
        ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
270
        ln->type = LSART_STUB;
271
        ln->id = ipa_to_u32(a->prefix);
272
        ln->data = ipa_to_u32(ipa_mkmask(a->pxlen));
273
        ln->metric = ifa->cost;
274
        ln->notos = 0;
275
        i++;
276
      }
277
  }
278

    
279
  struct ospf_stubnet_config *sn;
280
  WALK_LIST(sn, oa->ac->stubnet_list)
281
    if (!sn->hidden)
282
      {
283
        ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
284
        ln->type = LSART_STUB;
285
        ln->id = ipa_to_u32(sn->px.addr);
286
        ln->data = ipa_to_u32(ipa_mkmask(sn->px.len));
287
        ln->metric = sn->cost;
288
        ln->notos = 0;
289
        i++;
290
      }
291

    
292
  rt = po->lsab;
293
  rt->links = i;
294

    
295
  if (bitv) 
296
    rt->options |= OPT_RT_V;
297

    
298
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
299
  return lsab_flush(po);
300
}
301

    
302
#else /* OSPFv3 */
303

    
304
static void
305
add_lsa_rt_link(struct proto_ospf *po, struct ospf_iface *ifa, u8 type, u32 nif, u32 id)
306
{
307
  struct ospf_lsa_rt_link *ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
308
  ln->type = type;
309
  ln->padding = 0;
310
  ln->metric = ifa->cost;
311
  ln->lif = ifa->iface->index;
312
  ln->nif = nif;
313
  ln->id = id;
314
}
315

    
316
static void *
317
originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
318
{
319
  struct proto_ospf *po = oa->po;
320
  struct ospf_iface *ifa;
321
  int bitv = 0;
322
  struct ospf_lsa_rt *rt;
323
  struct ospf_neighbor *neigh;
324

    
325
  DBG("%s: Originating RT_lsa body for area %R.\n", po->proto.name,
326
      oa->areaid);
327
  
328
  ASSERT(po->lsab_used == 0);
329
  rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt));
330

    
331
  rt->options = oa->options & OPTIONS_MASK;
332

    
333
  if (po->areano > 1)
334
    rt->options |= OPT_RT_B;
335

    
336
  if ((po->ebit) && (!oa->stub))
337
    rt->options |= OPT_RT_E;
338

    
339
  rt = NULL; /* buffer might be reallocated later */
340

    
341
  WALK_LIST(ifa, po->iface_list)
342
  {
343
    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
344
        (!EMPTY_LIST(ifa->neigh_list)))
345
    {
346
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
347
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
348
        bitv = 1;
349
    }
350

    
351
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
352
      continue;
353

    
354
    /* BIRD does not support interface loops */
355
    ASSERT(ifa->state != OSPF_IS_LOOP);
356

    
357
    /* RFC5340 - 4.4.3.2 */
358
    switch (ifa->type)
359
      {
360
      case OSPF_IT_PTP:
361
        neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
362
        if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL))
363
          add_lsa_rt_link(po, ifa, LSART_PTP, neigh->iface_id, neigh->rid);
364
        break;
365

    
366
      case OSPF_IT_BCAST:
367
      case OSPF_IT_NBMA:
368
        if (bcast_net_active(ifa))
369
          add_lsa_rt_link(po, ifa, LSART_NET, ifa->dr_iface_id, ifa->drid);
370
        break;
371

    
372
      case OSPF_IT_VLINK:
373
        neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
374
        if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
375
          add_lsa_rt_link(po, ifa, LSART_VLNK, neigh->iface_id, neigh->rid);
376
        break;
377

    
378
      default:
379
        log("Unknown interface type %s", ifa->iface->name);
380
        break;
381
      }
382
  }
383

    
384
  if (bitv)
385
    {
386
      rt = po->lsab;
387
      rt->options |= OPT_RT_V;
388
    }
389

    
390
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
391
  return lsab_flush(po);
392
}
393

    
394
#endif
395

    
396
/**
397
 * originate_rt_lsa - build new instance of router LSA
398
 * @oa: ospf_area which is LSA built to
399
 *
400
 * It builds router LSA walking through all OSPF interfaces in
401
 * specified OSPF area. This function is mostly called from
402
 * area_disp(). Builds new LSA, increases sequence number (if old
403
 * instance exists) and sets age of LSA to zero.
404
 */
405
void
406
originate_rt_lsa(struct ospf_area *oa)
407
{
408
  struct ospf_lsa_header lsa;
409
  struct proto_ospf *po = oa->po;
410
  struct proto *p = &po->proto;
411
  u32 rid = po->proto.cf->global->router_id;
412
  void *body;
413

    
414
  OSPF_TRACE(D_EVENTS, "Originating RT_lsa for area %R.", oa->areaid);
415

    
416
  lsa.age = 0;
417
  lsa.type = LSA_T_RT;
418
  
419
#ifdef OSPFv2
420
  lsa.options = oa->options;
421
#endif
422
  
423
  lsa.id = rid;
424
  lsa.rt = rid;
425
  lsa.sn = oa->rt ? (oa->rt->lsa.sn + 1) : LSA_INITSEQNO;
426
  u32 dom = oa->areaid;
427

    
428
  body = originate_rt_lsa_body(oa, &lsa.length);
429
  lsasum_calculate(&lsa, body);
430
  oa->rt = lsa_install_new(po, &lsa, dom, body);
431
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
432
}
433

    
434
void
435
update_rt_lsa(struct ospf_area *oa)
436
{
437
  struct proto_ospf *po = oa->po;
438

    
439
  if ((oa->rt) && ((oa->rt->inst_t + MINLSINTERVAL)) > now)
440
    return;
441
  /*
442
   * Tick is probably set to very low value. We cannot
443
   * originate new LSA before MINLSINTERVAL. We will
444
   * try to do it next tick.
445
   */
446

    
447
  originate_rt_lsa(oa);
448
  originate_prefix_rt_lsa(oa);
449

    
450
  schedule_rtcalc(po);
451
  oa->origrt = 0;
452
}
453

    
454
static void *
455
originate_net_lsa_body(struct ospf_iface *ifa, u16 *length,
456
                       struct proto_ospf *po)
457
{
458
  u16 i = 1;
459
  struct ospf_neighbor *n;
460
  struct ospf_lsa_net *net;
461
  int nodes = ifa->fadj + 1;
462

    
463
  net = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_net)
464
                 + nodes * sizeof(u32));
465

    
466
#ifdef OSPFv2
467
  net->netmask = ipa_mkmask(ifa->iface->addr->pxlen);
468
#endif
469

    
470
#ifdef OSPFv3
471
  /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */
472
  struct top_hash_entry *en;
473
  u32 options = 0;
474
#endif
475

    
476
  net->routers[0] = po->proto.cf->global->router_id;
477

    
478
  WALK_LIST(n, ifa->neigh_list)
479
  {
480
    if (n->state == NEIGHBOR_FULL)
481
    {
482
#ifdef OSPFv3
483
      en = ospf_hash_find(po->gr, ifa->iface->index, n->iface_id, n->rid, LSA_T_LINK);
484
      if (en)
485
        options |= ((struct ospf_lsa_link *) en->lsa_body)->options;
486
#endif
487

    
488
      net->routers[i] = n->rid;
489
      i++;
490
    }
491
  }
492
  ASSERT(i == nodes);
493

    
494
#ifdef OSPFv3
495
  net->options = options & OPTIONS_MASK;
496
#endif
497
  
498
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_net)
499
    + nodes * sizeof(u32);
500
  return net;
501
}
502

    
503

    
504
/**
505
 * originate_net_lsa - originates of deletes network LSA
506
 * @ifa: interface which is LSA originated for
507
 *
508
 * Interface counts number of adjacent neighbors. If this number is
509
 * lower than one or interface is not in state %OSPF_IS_DR it deletes
510
 * and premature ages instance of network LSA for specified interface.
511
 * In other case, new instance of network LSA is originated.
512
 */
513
void
514
originate_net_lsa(struct ospf_iface *ifa)
515
{
516
  struct proto_ospf *po = ifa->oa->po;
517
  struct ospf_lsa_header lsa;
518
  u32 rid = po->proto.cf->global->router_id;
519
  u32 dom = ifa->oa->areaid;
520
  struct proto *p = &po->proto;
521
  void *body;
522

    
523
  OSPF_TRACE(D_EVENTS, "Originating Net lsa for iface \"%s\".",
524
             ifa->iface->name);
525

    
526
  lsa.age = 0;
527
  lsa.type = LSA_T_NET;
528

    
529
#ifdef OSPFv2
530
  lsa.options = ifa->oa->options;
531
  lsa.id = ipa_to_u32(ifa->iface->addr->ip);
532
#else /* OSPFv3 */
533
  lsa.id = ifa->iface->index;
534
#endif
535

    
536
  lsa.rt = rid;
537
  lsa.sn = ifa->net_lsa ? (ifa->net_lsa->lsa.sn + 1) : LSA_INITSEQNO;
538

    
539
  body = originate_net_lsa_body(ifa, &lsa.length, po);
540
  lsasum_calculate(&lsa, body);
541
  ifa->net_lsa = lsa_install_new(po, &lsa, dom, body);
542
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
543
}
544

    
545
void
546
flush_net_lsa(struct ospf_iface *ifa)
547
{
548
  struct proto_ospf *po = ifa->oa->po;
549
  struct proto *p = &po->proto;
550
  u32 dom = ifa->oa->areaid;
551

    
552
  if (ifa->net_lsa == NULL)
553
    return;
554

    
555
  OSPF_TRACE(D_EVENTS, "Deleting Net lsa for iface \"%s\".",
556
             ifa->iface->name);
557
  ifa->net_lsa->lsa.sn += 1;
558
  ifa->net_lsa->lsa.age = LSA_MAXAGE;
559
  lsasum_calculate(&ifa->net_lsa->lsa, ifa->net_lsa->lsa_body);
560
  ospf_lsupd_flood(po, NULL, NULL, &ifa->net_lsa->lsa, dom, 0);
561
  flush_lsa(ifa->net_lsa, po);
562
  ifa->net_lsa = NULL;
563
}
564

    
565
void
566
update_net_lsa(struct ospf_iface *ifa)
567
{
568
  struct proto_ospf *po = ifa->oa->po;
569
 
570
  if (ifa->net_lsa && ((ifa->net_lsa->inst_t + MINLSINTERVAL) > now))
571
    return;
572
  /*
573
   * It's too early to originate new network LSA. We will
574
   * try to do it next tick
575
   */
576

    
577
  if ((ifa->state != OSPF_IS_DR) || (ifa->fadj == 0))
578
    {
579
      flush_net_lsa(ifa);
580
      flush_prefix_net_lsa(ifa);
581
    }
582
  else
583
    {
584
      originate_net_lsa(ifa);
585
      originate_prefix_net_lsa(ifa);
586
    }
587

    
588
  schedule_rtcalc(po);
589
  ifa->orignet = 0;
590
}
591

    
592
#ifdef OSPFv2
593

    
594
static void *
595
originate_sum_lsa_body(struct proto_ospf *po, u16 *length, u32 mlen, u32 metric)
596
{
597
  struct ospf_lsa_sum *sum = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_sum));
598
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_sum);
599

    
600
  sum->netmask = ipa_mkmask(mlen);
601
  sum->metric = metric;
602

    
603
  return sum;
604
}
605

    
606
#define originate_sum_net_lsa_body(po,length,fn,metric) \
607
  originate_sum_lsa_body(po, length, (fn)->pxlen, metric)
608

    
609
#define originate_sum_rt_lsa_body(po,length,drid,metric,options) \
610
  originate_sum_lsa_body(po, length, 0, metric)
611

    
612
#else /* OSPFv3 */
613

    
614
static void *
615
originate_sum_net_lsa_body(struct proto_ospf *po, u16 *length, struct fib_node *fn, u32 metric)
616
{
617
  int size = sizeof(struct ospf_lsa_sum_net) + IPV6_PREFIX_SPACE(fn->pxlen);
618
  struct ospf_lsa_sum_net *sum = mb_alloc(po->proto.pool, size);
619
  *length = sizeof(struct ospf_lsa_header) + size;
620

    
621
  sum->metric = metric;
622
  put_ipv6_prefix(sum->prefix, fn->prefix, fn->pxlen, 0, 0);
623

    
624
  return sum;
625
}
626

    
627
static void *
628
originate_sum_rt_lsa_body(struct proto_ospf *po, u16 *length, u32 drid, u32 metric, u32 options)
629
{
630
  struct ospf_lsa_sum_rt *sum = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_sum_rt));
631
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_sum_rt);
632

    
633
  sum->options = options & OPTIONS_MASK;
634
  sum->metric = metric;
635
  sum->drid = drid;
636

    
637
  return sum;
638
}
639

    
640
#endif
641

    
642
void
643
originate_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type, int metric, u32 options)
644
{
645
  struct proto_ospf *po = oa->po;
646
  struct proto *p = &po->proto;
647
  struct top_hash_entry *en;
648
  u32 rid = po->proto.cf->global->router_id;
649
  struct ospf_lsa_header lsa;
650
  void *body;
651

    
652
  /* options argument is used in ORT_NET and OSPFv3 only */
653

    
654
  lsa.age = 0;
655
  lsa.rt = rid;
656
  lsa.sn = LSA_INITSEQNO;
657
#ifdef OSPFv2
658
  lsa.options = oa->options;
659
#endif
660

    
661
  if (type == ORT_NET)
662
    {
663
      /* FIXME proper handling of LSA IDs and check for the same network */
664
      lsa.id = ipa_to_lsaid(fn->prefix);
665
      lsa.type = LSA_T_SUM_NET;
666
    }
667
  else
668
    {
669
      /* In OSPFv6, LSA ID is meaningless, but we still use Router ID of ASBR */
670
      lsa.id = ipa_to_rid(fn->prefix);
671
      lsa.type = LSA_T_SUM_RT;
672
    }
673

    
674
  u32 dom = oa->areaid;  
675

    
676
  /* FIXME check for the same LSA */
677
  if ((en = ospf_hash_find_header(po->gr, oa->areaid, &lsa)) != NULL)
678
    lsa.sn = en->lsa.sn + 1;
679

    
680
  if (type == ORT_NET)
681
    {
682
      OSPF_TRACE(D_EVENTS, "Originating Net-Summary-LSA for %I/%d (metric %d).",
683
                 fn->prefix, fn->pxlen, metric);
684

    
685
      body = originate_sum_net_lsa_body(po, &lsa.length, fn, metric);
686
    }
687
  else
688
    {
689
      OSPF_TRACE(D_EVENTS, "Originating RT-Summary-LSA for %R (metric %d).",
690
                 lsa.id, metric);
691

    
692
      body = originate_sum_rt_lsa_body(po, &lsa.length, lsa.id, metric, options);
693
    }
694

    
695
  lsasum_calculate(&lsa, body);
696
  en = lsa_install_new(po, &lsa, dom, body);
697
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
698
}
699

    
700

    
701
void
702
flush_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type)
703
{
704
  struct proto_ospf *po = oa->po;
705
  struct proto *p = &po->proto;
706
  struct top_hash_entry *en;
707
  u32 rid = po->proto.cf->global->router_id;
708
  struct ospf_lsa_header lsa;
709

    
710
  lsa.rt = rid;
711
  if (type == ORT_NET)
712
    {
713
      /* FIXME proper handling of LSA IDs and check for the same network */
714
      lsa.id = ipa_to_lsaid(fn->prefix);
715
      lsa.type = LSA_T_SUM_NET;
716
    }
717
  else
718
    {
719
      /* In OSPFv6, LSA ID is meaningless, but we still use Router ID of ASBR */
720
      lsa.id = ipa_to_rid(fn->prefix);
721
      lsa.type = LSA_T_SUM_RT;
722
    }
723

    
724
  if ((en = ospf_hash_find_header(po->gr, oa->areaid, &lsa)) != NULL)
725
    {
726
      struct ospf_lsa_sum *sum = en->lsa_body;
727
      en->lsa.age = LSA_MAXAGE;
728
      en->lsa.sn = LSA_MAXSEQNO;
729
      lsasum_calculate(&en->lsa, sum);
730

    
731
      OSPF_TRACE(D_EVENTS, "Flushing summary lsa. (id=%R, type=%d)",
732
                 en->lsa.id, en->lsa.type);
733
      ospf_lsupd_flood(po, NULL, NULL, &en->lsa, oa->areaid, 1);
734
      if (can_flush_lsa(po)) flush_lsa(en, po);
735
    }
736
}
737

    
738

    
739
void
740
check_sum_lsa(struct proto_ospf *po, ort *nf, int dest)
741
{
742
  struct ospf_area *oa;
743
  int flush, mlen;
744
  ip_addr ip;
745

    
746
  if (po->areano < 2) return;
747

    
748
  if ((nf->n.type > RTS_OSPF_IA) && (nf->o.type > RTS_OSPF_IA)) return;
749

    
750
#ifdef LOCAL_DEBUG
751
  DBG("Checking...dest = %d, %I/%d\n", dest, nf->fn.prefix, nf->fn.pxlen);
752
  if (nf->n.oa) DBG("New: met=%d, oa=%d\n", nf->n.metric1, nf->n.oa->areaid);
753
  if (nf->o.oa) DBG("Old: met=%d, oa=%d\n", nf->o.metric1, nf->o.oa->areaid);
754
#endif
755

    
756
  WALK_LIST(oa, po->area_list)
757
  {
758
    flush = 0;
759
    if ((nf->n.metric1 >= LSINFINITY) || (nf->n.type > RTS_OSPF_IA))
760
      flush = 1;
761
    if ((dest == ORT_ROUTER) && (!(nf->n.options & ORTA_ASBR)))
762
      flush = 1;
763
    if ((!nf->n.oa) || (nf->n.oa->areaid == oa->areaid))
764
      flush = 1;
765

    
766
    if (nf->n.ifa) {
767
      if (nf->n.ifa->oa->areaid == oa->areaid)
768
        flush = 1;
769
      }
770
    else flush = 1;
771

    
772
    /* Don't send summary into stub areas
773
     * We send just default route (and later) */
774
    if (oa->stub)
775
      flush = 1;
776
    
777
    mlen = nf->fn.pxlen;
778
    ip = ipa_and(nf->fn.prefix, ipa_mkmask(mlen));
779

    
780
    if ((oa == po->backbone) && (nf->n.type == RTS_OSPF_IA))
781
      flush = 1;        /* Only intra-area can go to the backbone */
782

    
783
    if ((!flush) && (dest == ORT_NET) && fib_route(&nf->n.oa->net_fib, ip, mlen))
784
    {
785
      /* The route fits into area networks */
786
      flush = 1;
787
      if ((nf->n.oa == po->backbone) && (oa->trcap)) flush = 0;
788
    }
789

    
790
    if (flush)
791
      flush_sum_lsa(oa, &nf->fn, dest);
792
    else
793
      originate_sum_lsa(oa, &nf->fn, dest, nf->n.metric1, nf->n.options);
794
  }
795
}
796

    
797

    
798
static void *
799
originate_ext_lsa_body(net *n, rte *e, u16 *length, struct proto_ospf *po,
800
                       struct ea_list *attrs)
801
{
802
  struct proto *p = &po->proto;
803
  struct ospf_lsa_ext *ext;
804
  u32 m1 = ea_get_int(attrs, EA_OSPF_METRIC1, LSINFINITY);
805
  u32 m2 = ea_get_int(attrs, EA_OSPF_METRIC2, 10000);
806
  u32 tag = ea_get_int(attrs, EA_OSPF_TAG, 0);
807
  int gw = 0;
808
  int size = sizeof(struct ospf_lsa_ext);
809
  u32 *buf;
810

    
811
  if (!ipa_equal(e->attrs->gw, IPA_NONE))
812
  {
813
    /* FIXME: check for link-local in OSPFv3 ? */
814
    if (ospf_iface_find((struct proto_ospf *) p, e->attrs->iface) != NULL)
815
      gw = 1;
816
  }
817

    
818
#ifdef OSPFv3
819
  size += IPV6_PREFIX_SPACE(n->n.pxlen);
820

    
821
  if (gw)
822
    size += 16;
823
  
824
  if (tag)
825
    size += 4;
826
#endif
827
  
828
  ext = mb_alloc(p->pool, size);
829
  *length = sizeof(struct ospf_lsa_header) + size;
830

    
831
  ext->metric = (m1 != LSINFINITY) ? m1 : (m2 & LSA_EXT_EBIT); 
832

    
833
#ifdef OSPFv2
834
  ext->netmask = ipa_mkmask(n->n.pxlen);
835
  ext->fwaddr = gw ? IPA_NONE : e->attrs->gw;
836
  ext->tag = tag;
837
#else /* OSPFv3 */
838
  buf = ext->rest;
839
  buf = put_ipv6_prefix(buf, n->n.prefix, n->n.pxlen, 0, 0);
840

    
841
  if (gw)
842
    {
843
      ext->metric |= LSA_EXT_FBIT;
844
      buf = put_ipv6_addr(buf, e->attrs->gw);
845
    }
846

    
847
  if (tag)
848
    {
849
      ext->metric |= LSA_EXT_TBIT;
850
      *buf++ = tag;
851
    }
852
#endif
853

    
854
  return ext;
855
}
856

    
857
/**
858
 * originate_ext_lsa - new route received from nest and filters
859
 * @n: network prefix and mask
860
 * @e: rte
861
 * @po: current instance of OSPF
862
 * @attrs: list of extended attributes
863
 *
864
 * If I receive a message that new route is installed, I try to originate an
865
 * external LSA. The LSA header of such LSA does not contain information about
866
 * prefix length, so if I have to originate multiple LSAs for route with
867
 * different prefixes I try to increment prefix id to find a "free" one.
868
 *
869
 * The function also sets flag ebit. If it's the first time, the new router lsa
870
 * origination is necessary.
871
 */
872
void
873
originate_ext_lsa(net * n, rte * e, struct proto_ospf *po,
874
                  struct ea_list *attrs)
875
{
876
  struct ospf_lsa_header lsa;
877
  u32 rid = po->proto.cf->global->router_id;
878
  struct top_hash_entry *en = NULL;
879
  void *body;
880
  struct proto *p = &po->proto;
881
  struct ospf_area *oa;
882

    
883
  OSPF_TRACE(D_EVENTS, "Originating Ext lsa for %I/%d.", n->n.prefix,
884
             n->n.pxlen);
885

    
886
  lsa.age = 0;
887
  lsa.type = LSA_T_EXT;
888
  lsa.rt = rid;
889
  lsa.sn = LSA_INITSEQNO;
890
#ifdef OSPFv2
891
  lsa.options = 0; /* or oa->options ? */
892
#endif
893

    
894
  /* FIXME proper handling of LSA IDs and check for the same network */
895
  lsa.id = ipa_to_lsaid(n->n.prefix);
896

    
897
  if ((en = ospf_hash_find_header(po->gr, 0, &lsa)) != NULL)
898
    {
899
      lsa.sn = en->lsa.sn + 1;
900
    }
901

    
902
  body = originate_ext_lsa_body(n, e, &lsa.length, po, attrs);
903
  lsasum_calculate(&lsa, body);
904

    
905
  en = lsa_install_new(po, &lsa, 0, body);
906
  ospf_lsupd_flood(po, NULL, NULL, &lsa, 0, 1);
907

    
908
  if (po->ebit == 0)
909
  {
910
    po->ebit = 1;
911
    WALK_LIST(oa, po->area_list)
912
    {
913
      schedule_rt_lsa(oa);
914
    }
915
  }
916
}
917

    
918
void
919
flush_ext_lsa(net *n, struct proto_ospf *po)
920
{
921
  u32 rid = po->proto.cf->global->router_id;
922
  struct ospf_area *oa;
923
  struct top_hash_entry *en;
924

    
925
  /* FIXME proper handling of LSA IDs and check for the same network */
926
  u32 lsaid = ipa_to_lsaid(n->n.prefix);
927

    
928
  if (en = ospf_hash_find(po->gr, 0, lsaid, rid, LSA_T_EXT))
929
    {
930
      /* FIXME this is nonsense */
931
      WALK_LIST(oa, po->area_list)
932
        {
933
          ospf_lsupd_flush_nlsa(po, en);
934
        }
935
    }
936
}
937

    
938

    
939
#ifdef OSPFv3
940

    
941
static void *
942
originate_link_lsa_body(struct ospf_iface *ifa, u16 *length)
943
{
944
  struct proto_ospf *po = ifa->oa->po;
945
  struct ospf_lsa_link *ll;
946
  int i = 0;
947
  u8 flags;
948

    
949
  ASSERT(po->lsab_used == 0);
950
  ll = lsab_allocz(po, sizeof(struct ospf_lsa_link));
951
  ll->options = ifa->oa->options | (ifa->priority << 24);
952
  ll->lladdr = ifa->lladdr;
953
  ll = NULL; /* buffer might be reallocated later */
954

    
955
  struct ifa *a;
956
  WALK_LIST(a, ifa->iface->addrs)
957
    {
958
      if ((a->flags & IA_SECONDARY) ||
959
          (a->scope < SCOPE_SITE))
960
        continue;
961

    
962
      flags = (a->pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
963
      put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(a->pxlen)),
964
                      a->ip, a->pxlen, flags, 0);
965
      i++;
966
    }
967

    
968
  ll = po->lsab;
969
  ll->pxcount = i;
970
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
971
  return lsab_flush(po);
972
}
973

    
974
void
975
originate_link_lsa(struct ospf_iface *ifa)
976
{
977
  struct ospf_lsa_header lsa;
978
  struct proto_ospf *po = ifa->oa->po;
979
  struct proto *p = &po->proto;
980
  u32 rid = po->proto.cf->global->router_id;
981
  void *body;
982

    
983
  /* FIXME check for vlink and skip that? */
984
  OSPF_TRACE(D_EVENTS, "Originating Link_lsa for iface %s.", ifa->iface->name);
985

    
986
  lsa.age = 0;
987
  lsa.type = LSA_T_LINK;
988
  lsa.id = ifa->iface->index;
989
  lsa.rt = rid;
990
  lsa.sn = ifa->link_lsa ? (ifa->link_lsa->lsa.sn + 1) : LSA_INITSEQNO;
991
  u32 dom = ifa->iface->index;
992

    
993
  body = originate_link_lsa_body(ifa, &lsa.length);
994
  lsasum_calculate(&lsa, body);
995
  ifa->link_lsa = lsa_install_new(po, &lsa, dom, body);
996
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
997
}
998

    
999
void
1000
update_link_lsa(struct ospf_iface *ifa)
1001
{
1002
  if (ifa->link_lsa && ((ifa->link_lsa->inst_t + MINLSINTERVAL) > now))
1003
    return;
1004
  /*
1005
   * It's too early to originate new link LSA. We will
1006
   * try to do it next tick
1007
   */
1008
  originate_link_lsa(ifa);
1009
  ifa->origlink = 0;
1010
}
1011

    
1012
static void *
1013
originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length)
1014
{
1015
  struct proto_ospf *po = oa->po;
1016
  struct ospf_iface *ifa;
1017
  struct ospf_lsa_prefix *lp;
1018
  u32 rid = po->proto.cf->global->router_id;
1019
  int net_lsa;
1020
  int i = 0;
1021
  u8 flags;
1022

    
1023
  ASSERT(po->lsab_used == 0);
1024
  lp = lsab_allocz(po, sizeof(struct ospf_lsa_prefix));
1025
  lp->ref_type = LSA_T_RT;
1026
  lp->ref_id = 0;
1027
  lp->ref_rt = rid;
1028
  lp = NULL; /* buffer might be reallocated later */
1029

    
1030
  WALK_LIST(ifa, po->iface_list)
1031
  {
1032
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
1033
      continue;
1034

    
1035
    if ((ifa->type == OSPF_IT_BCAST) ||
1036
        (ifa->type == OSPF_IT_NBMA))
1037
      net_lsa = bcast_net_active(ifa);
1038
    else
1039
      net_lsa = 0;
1040

    
1041
    struct ifa *a;
1042
    WALK_LIST(a, ifa->iface->addrs)
1043
      {
1044
        if (((a->pxlen < MAX_PREFIX_LENGTH) && net_lsa) ||
1045
            (a->flags & IA_SECONDARY) ||
1046
            (a->flags & IA_UNNUMBERED) ||
1047
            configured_stubnet(oa, a))
1048
          continue;
1049

    
1050
        flags = (a->pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
1051
        put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(a->pxlen)),
1052
                        a->ip, a->pxlen, flags, ifa->cost);
1053
        i++;
1054
      }
1055
  }
1056

    
1057
  /* FIXME Handle vlinks? see RFC5340, page 38 */
1058

    
1059
  struct ospf_stubnet_config *sn;
1060
  WALK_LIST(sn, oa->ac->stubnet_list)
1061
    if (!sn->hidden)
1062
      {
1063
        flags = (sn->px.len < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
1064
        put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(sn->px.len)),
1065
                        sn->px.addr, sn->px.len, flags, sn->cost);
1066
        i++;
1067
      }
1068

    
1069
  lp = po->lsab;
1070
  lp->pxcount = i;
1071
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
1072
  return lsab_flush(po);
1073
}
1074

    
1075
void
1076
originate_prefix_rt_lsa(struct ospf_area *oa)
1077
{
1078
  struct ospf_lsa_header lsa;
1079
  struct proto_ospf *po = oa->po;
1080
  u32 rid = po->proto.cf->global->router_id;
1081
  void *body;
1082

    
1083
  lsa.age = 0;
1084
  lsa.type = LSA_T_PREFIX;
1085
  lsa.id = 1 << 31;
1086
  lsa.rt = rid;
1087
  lsa.sn = oa->pxr_lsa ? (oa->pxr_lsa->lsa.sn + 1) : LSA_INITSEQNO;
1088
  u32 dom = oa->areaid;
1089

    
1090
  body = originate_prefix_rt_lsa_body(oa, &lsa.length);
1091
  lsasum_calculate(&lsa, body);
1092
  oa->pxr_lsa = lsa_install_new(po, &lsa, dom, body);
1093
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
1094
}
1095

    
1096

    
1097
static inline int
1098
prefix_space(u32 *buf)
1099
{
1100
  int pxl = *buf >> 24;
1101
  return IPV6_PREFIX_SPACE(pxl);
1102
}
1103

    
1104
static inline int
1105
prefix_same(u32 *b1, u32 *b2)
1106
{
1107
  int pxl1 = *b1 >> 24;
1108
  int pxl2 = *b2 >> 24;
1109
  int pxs, i;
1110
  
1111
  if (pxl1 != pxl2)
1112
    return 0;
1113

    
1114
  pxs = IPV6_PREFIX_WORDS(pxl1);
1115
  for (i = 1; i < pxs; i++)
1116
    if (b1[i] != b2[i])
1117
      return 0;
1118

    
1119
  return 1;
1120
}
1121

    
1122
static inline u32 *
1123
prefix_advance(u32 *buf)
1124
{
1125
  return buf + prefix_space(buf);
1126
}
1127

    
1128
static void
1129
add_prefix(struct proto_ospf *po, u32 *px, u32 *pxl, int *pxc)
1130
{
1131
  int i;
1132
  for (i = 0; i < *pxc; i++)
1133
    {
1134
      if (prefix_same(px, pxl))
1135
        {
1136
          /* Options should be logically OR'ed together */
1137
          *pxl |= *px;
1138
          return;
1139
        }
1140
      pxl = prefix_advance(pxl);
1141
    }
1142

    
1143
  ASSERT(pxl == lsab_end(po));
1144

    
1145
  int pxspace = prefix_space(px);
1146
  pxl = lsab_alloc(po, pxspace);
1147
  memcpy(pxl, px, pxspace);
1148
  (*pxc)++;
1149
}
1150

    
1151

    
1152
static void *
1153
originate_prefix_net_lsa_body(struct ospf_iface *ifa, u16 *length)
1154
{
1155
  struct proto_ospf *po = ifa->oa->po;
1156
  struct ospf_lsa_prefix *lp;
1157
  struct ospf_lsa_link *ll;
1158
  struct ospf_neighbor *n;
1159
  struct top_hash_entry *en;
1160
  u32 rid = po->proto.cf->global->router_id;
1161
  u32 *pxb;
1162
  int i, j, offset;
1163

    
1164

    
1165
  ASSERT(po->lsab_used == 0);
1166
  lp = lsab_allocz(po, sizeof(struct ospf_lsa_prefix));
1167
  lp->ref_type = LSA_T_NET;
1168
  lp->ref_id = ifa->net_lsa->lsa.id;
1169
  lp->ref_rt = rid;
1170
  lp = NULL; /* buffer might be reallocated later */
1171

    
1172
  i = 0;
1173
  offset = po->lsab_used;
1174

    
1175
  /* Find all Link LSA associated with the link and merge their prefixes */
1176
  WALK_LIST(n, ifa->neigh_list)
1177
    if ((n->state == NEIGHBOR_FULL) &&
1178
              (en = ospf_hash_find(po->gr, ifa->iface->index, n->iface_id, n->rid, LSA_T_LINK)))
1179
      {
1180
        ll = en->lsa_body;
1181
        pxb = ll->rest;
1182

    
1183
        for (j = 0; j < ll->pxcount; j++)
1184
          {
1185
            add_prefix(po, pxb, lsab_offset(po, offset), &i);
1186
            pxb = prefix_advance(pxb);
1187
          }
1188
      }
1189

    
1190
  lp = po->lsab;
1191
  lp->pxcount = i;
1192
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
1193
  return lsab_flush(po);
1194
}
1195

    
1196
void
1197
originate_prefix_net_lsa(struct ospf_iface *ifa)
1198
{
1199
  struct ospf_lsa_header lsa;
1200
  struct proto_ospf *po = ifa->oa->po;
1201
  u32 rid = po->proto.cf->global->router_id;
1202
  void *body;
1203

    
1204
  lsa.age = 0;
1205
  lsa.type = LSA_T_PREFIX;
1206
  lsa.id = ifa->iface->index;
1207
  lsa.rt = rid;
1208
  lsa.sn = ifa->pxn_lsa ? (ifa->pxn_lsa->lsa.sn + 1) : LSA_INITSEQNO;
1209
  u32 dom = ifa->oa->areaid;
1210

    
1211
  body = originate_prefix_net_lsa_body(ifa, &lsa.length);
1212
  lsasum_calculate(&lsa, body);
1213
  ifa->pxn_lsa = lsa_install_new(po, &lsa, dom, body);
1214
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
1215
}
1216

    
1217
void
1218
flush_prefix_net_lsa(struct ospf_iface *ifa)
1219
{
1220
  struct proto_ospf *po = ifa->oa->po;
1221
  struct proto *p = &po->proto;
1222
  struct top_hash_entry *en = ifa->pxn_lsa;
1223
  u32 dom = ifa->oa->areaid;
1224

    
1225
  if (en == NULL)
1226
    return;
1227

    
1228
  OSPF_TRACE(D_EVENTS, "Flushing Net Prefix lsa for iface \"%s\".",
1229
             ifa->iface->name);
1230
  en->lsa.sn += 1;
1231
  en->lsa.age = LSA_MAXAGE;
1232
  lsasum_calculate(&en->lsa, en->lsa_body);
1233
  ospf_lsupd_flood(po, NULL, NULL, &en->lsa, dom, 0);
1234
  flush_lsa(en, po);
1235
  ifa->pxn_lsa = NULL;
1236
}
1237

    
1238

    
1239
#endif
1240

    
1241

    
1242
static void
1243
ospf_top_ht_alloc(struct top_graph *f)
1244
{
1245
  f->hash_size = 1 << f->hash_order;
1246
  f->hash_mask = f->hash_size - 1;
1247
  if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
1248
    f->hash_entries_max = ~0;
1249
  else
1250
    f->hash_entries_max = f->hash_size HASH_HI_MARK;
1251
  if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
1252
    f->hash_entries_min = 0;
1253
  else
1254
    f->hash_entries_min = f->hash_size HASH_LO_MARK;
1255
  DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
1256
      f->hash_order, f->hash_size, f->hash_entries_min, f->hash_entries_max);
1257
  f->hash_table =
1258
    mb_alloc(f->pool, f->hash_size * sizeof(struct top_hash_entry *));
1259
  bzero(f->hash_table, f->hash_size * sizeof(struct top_hash_entry *));
1260
}
1261

    
1262
static inline void
1263
ospf_top_ht_free(struct top_hash_entry **h)
1264
{
1265
  mb_free(h);
1266
}
1267

    
1268
static inline u32
1269
ospf_top_hash_u32(u32 a)
1270
{
1271
  /* Shamelessly stolen from IP address hashing in ipv4.h */
1272
  a ^= a >> 16;
1273
  a ^= a << 10;
1274
  return a;
1275
}
1276

    
1277
static inline unsigned
1278
ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type)
1279
{
1280
  /* In OSPFv2, we don't know Router ID when looking for network lsas.
1281
     dirty patch to make rt table calculation work. */
1282

    
1283
  return (ospf_top_hash_u32(lsaid) + type +
1284
#ifdef OSPFv2
1285
          ((type == LSA_T_NET) ? 0 : ospf_top_hash_u32(rtrid)) +
1286
#else /* OSPFv3 */
1287
          ospf_top_hash_u32(rtrid) +
1288
#endif
1289
          domain) & f->hash_mask;
1290

    
1291
  /*
1292
  return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
1293
          type + areaid) & f->hash_mask;
1294
  */
1295
}
1296

    
1297
/**
1298
 * ospf_top_new - allocated new topology database
1299
 * @p: current instance of ospf
1300
 *
1301
 * this dynamically hashed structure is often used for keeping lsas. mainly
1302
 * its used in @ospf_area structure.
1303
 */
1304
struct top_graph *
1305
ospf_top_new(pool *pool)
1306
{
1307
  struct top_graph *f;
1308

    
1309
  f = mb_allocz(pool, sizeof(struct top_graph));
1310
  f->pool = pool;
1311
  f->hash_slab = sl_new(f->pool, sizeof(struct top_hash_entry));
1312
  f->hash_order = HASH_DEF_ORDER;
1313
  ospf_top_ht_alloc(f);
1314
  f->hash_entries = 0;
1315
  f->hash_entries_min = 0;
1316
  return f;
1317
}
1318

    
1319
void
1320
ospf_top_free(struct top_graph *f)
1321
{
1322
  rfree(f->hash_slab);
1323
  ospf_top_ht_free(f->hash_table);
1324
  mb_free(f);
1325
}
1326

    
1327
static void
1328
ospf_top_rehash(struct top_graph *f, int step)
1329
{
1330
  unsigned int oldn, oldh;
1331
  struct top_hash_entry **n, **oldt, **newt, *e, *x;
1332

    
1333
  oldn = f->hash_size;
1334
  oldt = f->hash_table;
1335
  DBG("re-hashing topology hash from order %d to %d\n", f->hash_order,
1336
      f->hash_order + step);
1337
  f->hash_order += step;
1338
  ospf_top_ht_alloc(f);
1339
  newt = f->hash_table;
1340

    
1341
  for (oldh = 0; oldh < oldn; oldh++)
1342
  {
1343
    e = oldt[oldh];
1344
    while (e)
1345
    {
1346
      x = e->next;
1347
      n = newt + ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa.type);
1348
      e->next = *n;
1349
      *n = e;
1350
      e = x;
1351
    }
1352
  }
1353
  ospf_top_ht_free(oldt);
1354
}
1355

    
1356
u32
1357
ospf_lsa_domain(u32 type, struct ospf_iface *ifa)
1358
{
1359
  switch (type & LSA_SCOPE_MASK)
1360
    {
1361
    case LSA_SCOPE_LINK:
1362
      return ifa->iface->index;
1363

    
1364
    case LSA_SCOPE_AREA:
1365
      return ifa->oa->areaid;
1366

    
1367
    case LSA_SCOPE_AS:
1368
    default:
1369
      return 0;
1370
    }
1371
}
1372

    
1373
struct top_hash_entry *
1374
ospf_hash_find_header(struct top_graph *f, u32 domain, struct ospf_lsa_header *h)
1375
{
1376
  return ospf_hash_find(f, domain, h->id, h->rt, h->type);
1377
}
1378

    
1379
struct top_hash_entry *
1380
ospf_hash_get_header(struct top_graph *f, u32 domain, struct ospf_lsa_header *h)
1381
{
1382
  return ospf_hash_get(f, domain, h->id, h->rt, h->type);
1383
}
1384

    
1385
struct top_hash_entry *
1386
ospf_hash_find(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1387
{
1388
  struct top_hash_entry *e;
1389

    
1390
  e = f->hash_table[ospf_top_hash(f, domain, lsa, rtr, type)];
1391

    
1392
#ifdef OSPFv2
1393
  /* dirty patch to make rt table calculation work. */
1394
  if (type == LSA_T_NET)
1395
  {
1396
    while (e && (e->lsa.id != lsa || e->lsa.type != LSA_T_NET || e->domain != domain))
1397
      e = e->next;
1398

    
1399
    return e;
1400
  }
1401

    
1402
#endif
1403

    
1404
  while (e && (e->lsa.id != lsa || e->lsa.type != type || e->lsa.rt != rtr || e->domain != domain))
1405
    e = e->next;
1406

    
1407
  return e;
1408
}
1409

    
1410
struct top_hash_entry *
1411
ospf_hash_get(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1412
{
1413
  struct top_hash_entry **ee;
1414
  struct top_hash_entry *e;
1415

    
1416
  ee = f->hash_table + ospf_top_hash(f, domain, lsa, rtr, type);
1417
  e = *ee;
1418

    
1419
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type || e->domain != domain))
1420
    e = e->next;
1421

    
1422
  if (e)
1423
    return e;
1424

    
1425
  e = sl_alloc(f->hash_slab);
1426
  e->color = OUTSPF;
1427
  e->dist = LSINFINITY;
1428
  e->nhi = NULL;
1429
  e->nh = IPA_NONE;
1430
  e->lb = IPA_NONE;
1431
  e->lsa.id = lsa;
1432
  e->lsa.rt = rtr;
1433
  e->lsa.type = type;
1434
  e->lsa_body = NULL;
1435
  e->nhi = NULL;
1436
  e->domain = domain;
1437
  e->next = *ee;
1438
  *ee = e;
1439
  if (f->hash_entries++ > f->hash_entries_max)
1440
    ospf_top_rehash(f, HASH_HI_STEP);
1441
  return e;
1442
}
1443

    
1444
void
1445
ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
1446
{
1447
  struct top_hash_entry **ee = f->hash_table + 
1448
    ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa.type);
1449

    
1450
  while (*ee)
1451
  {
1452
    if (*ee == e)
1453
    {
1454
      *ee = e->next;
1455
      sl_free(f->hash_slab, e);
1456
      if (f->hash_entries-- < f->hash_entries_min)
1457
        ospf_top_rehash(f, -HASH_LO_STEP);
1458
      return;
1459
    }
1460
    ee = &((*ee)->next);
1461
  }
1462
  bug("ospf_hash_delete() called for invalid node");
1463
}
1464

    
1465
static void
1466
ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
1467
{
1468
  /*
1469
  struct ospf_lsa_rt *rt = NULL;
1470
  struct ospf_lsa_rt_link *rr = NULL;
1471
  struct ospf_lsa_net *ln = NULL;
1472
  u32 *rts = NULL;
1473
  u32 i, max;
1474

1475
  OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
1476
             he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
1477
             he->lsa.checksum, he->domain);
1478

1479

1480
  switch (he->lsa.type)
1481
    {
1482
    case LSA_T_RT:
1483
      rt = he->lsa_body;
1484
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
1485

1486
      for (i = 0; i < lsa_rt_items(&he->lsa); i++)
1487
        OSPF_TRACE(D_EVENTS, "  - %1x %-1R %-1R %5u",
1488
                   rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
1489
      break;
1490

1491
    case LSA_T_NET:
1492
      ln = he->lsa_body;
1493
      rts = (u32 *) (ln + 1);
1494

1495
      for (i = 0; i < lsa_net_items(&he->lsa); i++)
1496
        OSPF_TRACE(D_EVENTS, "  - %-1R", rts[i]);
1497
      break;
1498

1499
    default:
1500
      break;
1501
    }
1502
  */
1503
}
1504

    
1505
void
1506
ospf_top_dump(struct top_graph *f, struct proto *p)
1507
{
1508
  unsigned int i;
1509
  OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
1510

    
1511
  for (i = 0; i < f->hash_size; i++)
1512
  {
1513
    struct top_hash_entry *e;
1514
    for (e = f->hash_table[i]; e != NULL; e = e->next)
1515
      ospf_dump_lsa(e, p);
1516
  }
1517
}
1518

    
1519
/* This is very inefficient, please don't call it often */
1520

    
1521
/* I should also test for every LSA if it's in some link state
1522
 * retransmission list for every neighbor. I will not test it.
1523
 * It could happen that I'll receive some strange ls ack's.
1524
 */
1525

    
1526
int
1527
can_flush_lsa(struct proto_ospf *po)
1528
{
1529
  struct ospf_iface *ifa;
1530
  struct ospf_neighbor *n;
1531

    
1532
  WALK_LIST(ifa, po->iface_list)
1533
  {
1534
    WALK_LIST(n, ifa->neigh_list)
1535
    {
1536
      if ((n->state == NEIGHBOR_EXCHANGE) || (n->state == NEIGHBOR_LOADING))
1537
        return 0;
1538

    
1539
      break;
1540
    }
1541
  }
1542

    
1543
  return 1;
1544
}