Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (41 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

    
34
#ifdef OSPFv2
35
static inline u32
36
fibnode_to_lsaid(struct proto_ospf *po, struct fib_node *fn)
37
{
38
  /* We have to map IP prefixes to u32 in such manner that resulting
39
     u32 interpreted as IP address is a member of given
40
     prefix. Therefore, /32 prefix have to be mapped on itself.
41
     All received prefixes have to be mapped on different u32s.
42

43
     We have an assumption that if there is nontrivial (non-/32)
44
     network prefix, then there is not /32 prefix for the first
45
     and the last IP address of the network (these are usually
46
     reserved, therefore it is not an important restriction).
47
     The network prefix is mapped to the first or the last
48
     IP address in the manner that disallow collisions - we
49
     use IP address that cannot be used by parent prefix.
50

51
     For example:
52
     192.168.0.0/24 maps to 192.168.0.255
53
     192.168.1.0/24 maps to 192.168.1.0
54
     because 192.168.0.0 and 192.168.1.255 might be used by
55
     192.168.0.0/23 .
56

57
     This is not compatible with older RFC 1583, so we have an option
58
     to the RFC 1583 compatible assignment (that always uses the first
59
     address) which disallows subnetting.
60

61
     Appendig E of RFC 2328 suggests different algorithm, that tries
62
     to maximize both compatibility and subnetting. But as it is not
63
     possible to have both reliably and the suggested algorithm was
64
     unnecessary complicated and it does crazy things like changing
65
     LSA ID for a network because different network appeared, we
66
     choose a different way. */
67

    
68
  u32 id = _I(fn->prefix);
69

    
70
  if ((po->rfc1583) || (fn->pxlen == 0) || (fn->pxlen == 32))
71
    return id;
72

    
73
  if (id & (1 << (32 - fn->pxlen)))
74
    return id;
75
  else
76
    return id | ~u32_mkmask(fn->pxlen);
77
}
78

    
79
#else /* OSPFv3 */
80

    
81
static inline u32
82
fibnode_to_lsaid(struct proto_ospf *po, struct fib_node *fn)
83
{
84
  /* In OSPFv3, it is simpler. There is not a requirement
85
     for membership of the result in input network, so we
86
     just use hash-based unique ID. */
87

    
88
  return fn->uid;
89
}
90

    
91
#endif
92

    
93

    
94
static void *
95
lsab_alloc(struct proto_ospf *po, unsigned size)
96
{
97
  unsigned offset = po->lsab_used;
98
  po->lsab_used += size;
99
  if (po->lsab_used > po->lsab_size)
100
    {
101
      po->lsab_size = MAX(po->lsab_used, 2 * po->lsab_size);
102
      po->lsab = mb_realloc(po->proto.pool, po->lsab, po->lsab_size);
103
    }
104
  return ((byte *) po->lsab) + offset;
105
}
106

    
107
static inline void *
108
lsab_allocz(struct proto_ospf *po, unsigned size)
109
{
110
  void *r = lsab_alloc(po, size);
111
  bzero(r, size);
112
  return r;
113
}
114

    
115
static inline void *
116
lsab_flush(struct proto_ospf *po)
117
{
118
  void *r = mb_alloc(po->proto.pool, po->lsab_size);
119
  memcpy(r, po->lsab, po->lsab_used);
120
  po->lsab_used = 0;
121
  return r;
122
}
123

    
124
static inline void *
125
lsab_offset(struct proto_ospf *po, unsigned offset)
126
{
127
  return ((byte *) po->lsab) + offset;
128
}
129

    
130
static inline void *
131
lsab_end(struct proto_ospf *po)
132
{
133
  return ((byte *) po->lsab) + po->lsab_used;
134
}
135

    
136

    
137
static int
138
configured_stubnet(struct ospf_area *oa, struct ifa *a)
139
{
140
  struct ospf_stubnet_config *sn;
141
  WALK_LIST(sn, oa->ac->stubnet_list)
142
    {
143
      if (sn->summary)
144
        {
145
          if (ipa_in_net(a->prefix, sn->px.addr, sn->px.len) && (a->pxlen >= sn->px.len))
146
            return 1;
147
        }
148
      else
149
        {
150
          if (ipa_equal(a->prefix, sn->px.addr) && (a->pxlen == sn->px.len))
151
            return 1;
152
        }
153
    }
154
  return 0;
155
}
156

    
157
int
158
bcast_net_active(struct ospf_iface *ifa)
159
{
160
  struct ospf_neighbor *neigh;
161

    
162
  if (ifa->state == OSPF_IS_WAITING)
163
    return 0;
164

    
165
  WALK_LIST(neigh, ifa->neigh_list)
166
    {
167
      if (neigh->state == NEIGHBOR_FULL)
168
        {
169
          if (neigh->rid == ifa->drid)
170
            return 1;
171

    
172
          if (ifa->state == OSPF_IS_DR)
173
            return 1;
174
        }
175
    }
176

    
177
  return 0;
178
}
179

    
180

    
181
#ifdef OSPFv2
182

    
183
static void *
184
originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
185
{
186
  struct proto_ospf *po = oa->po;
187
  struct ospf_iface *ifa;
188
  int i = 0, bitv = 0;
189
  struct ospf_lsa_rt *rt;
190
  struct ospf_lsa_rt_link *ln;
191
  struct ospf_neighbor *neigh;
192

    
193
  ASSERT(po->lsab_used == 0);
194
  rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt));
195

    
196
  rt->options = 0;
197

    
198
  if (po->areano > 1)
199
    rt->options |= OPT_RT_B;
200

    
201
  if ((po->ebit) && (!oa->stub))
202
    rt->options |= OPT_RT_E;
203

    
204
  rt = NULL; /* buffer might be reallocated later */
205

    
206
  WALK_LIST(ifa, po->iface_list)
207
  {
208
    int master = 0;
209

    
210
    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
211
        (!EMPTY_LIST(ifa->neigh_list)))
212
    {
213
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
214
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
215
        bitv = 1;
216
    }
217

    
218
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
219
      continue;
220

    
221
    /* BIRD does not support interface loops */
222
    ASSERT(ifa->state != OSPF_IS_LOOP);
223

    
224
    switch (ifa->type)
225
      {
226
      case OSPF_IT_PTP:        /* RFC2328 - 12.4.1.1 */
227
        neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
228
        if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL))
229
        {
230
          ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
231
          ln->type = LSART_PTP;
232
          ln->id = neigh->rid;
233
          ln->data = (ifa->iface->addr->flags & IA_UNNUMBERED) ?
234
            ifa->iface->index : ipa_to_u32(ifa->iface->addr->ip);
235
          ln->metric = ifa->cost;
236
          ln->padding = 0;
237
          i++;
238
          master = 1;
239
        }
240
        break;
241

    
242
      case OSPF_IT_BCAST: /* RFC2328 - 12.4.1.2 */
243
      case OSPF_IT_NBMA:
244
        if (bcast_net_active(ifa))
245
          {
246
            ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
247
            ln->type = LSART_NET;
248
            ln->id = ipa_to_u32(ifa->drip);
249
            ln->data = ipa_to_u32(ifa->iface->addr->ip);
250
            ln->metric = ifa->cost;
251
            ln->padding = 0;
252
            i++;
253
            master = 1;
254
          }
255
        break;
256

    
257
      case OSPF_IT_VLINK: /* RFC2328 - 12.4.1.3 */
258
        neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
259
        if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
260
        {
261
          ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
262
          ln->type = LSART_VLNK;
263
          ln->id = neigh->rid;
264
          ln->data = ipa_to_u32(ifa->iface->addr->ip);
265
          ln->metric = ifa->cost;
266
          ln->padding = 0;
267
          i++;
268
          master = 1;
269
        }
270
        break;
271

    
272
      default:
273
        log("Unknown interface type %s", ifa->iface->name);
274
        break;
275
      }
276

    
277
    /* Now we will originate stub areas for interfaces addresses */
278
    struct ifa *a;
279
    WALK_LIST(a, ifa->iface->addrs)
280
      {
281
        if (((a == ifa->iface->addr) && master) ||
282
            (a->flags & IA_SECONDARY) ||
283
            (a->flags & IA_UNNUMBERED) ||
284
            configured_stubnet(oa, a))
285
          continue;
286

    
287

    
288
        ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
289
        ln->type = LSART_STUB;
290
        ln->id = ipa_to_u32(a->prefix);
291
        ln->data = ipa_to_u32(ipa_mkmask(a->pxlen));
292
        ln->metric = ifa->cost;
293
        ln->padding = 0;
294
        i++;
295
      }
296
  }
297

    
298
  struct ospf_stubnet_config *sn;
299
  WALK_LIST(sn, oa->ac->stubnet_list)
300
    if (!sn->hidden)
301
      {
302
        ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
303
        ln->type = LSART_STUB;
304
        ln->id = ipa_to_u32(sn->px.addr);
305
        ln->data = ipa_to_u32(ipa_mkmask(sn->px.len));
306
        ln->metric = sn->cost;
307
        ln->padding = 0;
308
        i++;
309
      }
310

    
311
  rt = po->lsab;
312
  rt->links = i;
313

    
314
  if (bitv) 
315
    rt->options |= OPT_RT_V;
316

    
317
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
318
  return lsab_flush(po);
319
}
320

    
321
#else /* OSPFv3 */
322

    
323
static void
324
add_lsa_rt_link(struct proto_ospf *po, struct ospf_iface *ifa, u8 type, u32 nif, u32 id)
325
{
326
  struct ospf_lsa_rt_link *ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
327
  ln->type = type;
328
  ln->padding = 0;
329
  ln->metric = ifa->cost;
330
  ln->lif = ifa->iface->index;
331
  ln->nif = nif;
332
  ln->id = id;
333
}
334

    
335
static void *
336
originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
337
{
338
  struct proto_ospf *po = oa->po;
339
  struct ospf_iface *ifa;
340
  int bitv = 0;
341
  struct ospf_lsa_rt *rt;
342
  struct ospf_neighbor *neigh;
343

    
344
  ASSERT(po->lsab_used == 0);
345
  rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt));
346

    
347
  rt->options = oa->options & OPTIONS_MASK;
348

    
349
  if (po->areano > 1)
350
    rt->options |= OPT_RT_B;
351

    
352
  if ((po->ebit) && (!oa->stub))
353
    rt->options |= OPT_RT_E;
354

    
355
  rt = NULL; /* buffer might be reallocated later */
356

    
357
  WALK_LIST(ifa, po->iface_list)
358
  {
359
    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
360
        (!EMPTY_LIST(ifa->neigh_list)))
361
    {
362
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
363
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
364
        bitv = 1;
365
    }
366

    
367
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
368
      continue;
369

    
370
    /* BIRD does not support interface loops */
371
    ASSERT(ifa->state != OSPF_IS_LOOP);
372

    
373
    /* RFC5340 - 4.4.3.2 */
374
    switch (ifa->type)
375
      {
376
      case OSPF_IT_PTP:
377
        neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
378
        if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL))
379
          add_lsa_rt_link(po, ifa, LSART_PTP, neigh->iface_id, neigh->rid);
380
        break;
381

    
382
      case OSPF_IT_BCAST:
383
      case OSPF_IT_NBMA:
384
        if (bcast_net_active(ifa))
385
          add_lsa_rt_link(po, ifa, LSART_NET, ifa->dr_iface_id, ifa->drid);
386
        break;
387

    
388
      case OSPF_IT_VLINK:
389
        neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
390
        if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
391
          add_lsa_rt_link(po, ifa, LSART_VLNK, neigh->iface_id, neigh->rid);
392
        break;
393

    
394
      default:
395
        log("Unknown interface type %s", ifa->iface->name);
396
        break;
397
      }
398
  }
399

    
400
  if (bitv)
401
    {
402
      rt = po->lsab;
403
      rt->options |= OPT_RT_V;
404
    }
405

    
406
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
407
  return lsab_flush(po);
408
}
409

    
410
#endif
411

    
412
/**
413
 * originate_rt_lsa - build new instance of router LSA
414
 * @oa: ospf_area which is LSA built to
415
 *
416
 * It builds router LSA walking through all OSPF interfaces in
417
 * specified OSPF area. This function is mostly called from
418
 * area_disp(). Builds new LSA, increases sequence number (if old
419
 * instance exists) and sets age of LSA to zero.
420
 */
421
void
422
originate_rt_lsa(struct ospf_area *oa)
423
{
424
  struct ospf_lsa_header lsa;
425
  struct proto_ospf *po = oa->po;
426
  struct proto *p = &po->proto;
427
  void *body;
428

    
429
  OSPF_TRACE(D_EVENTS, "Originating router-LSA for area %R", oa->areaid);
430

    
431
  lsa.age = 0;
432
  lsa.type = LSA_T_RT;
433
  
434
#ifdef OSPFv2
435
  lsa.options = oa->options;
436
  lsa.id = po->router_id;
437
#else /* OSPFv3 */
438
  lsa.id = 0;
439
#endif
440

    
441
  lsa.rt = po->router_id;
442
  lsa.sn = oa->rt ? (oa->rt->lsa.sn + 1) : LSA_INITSEQNO;
443
  u32 dom = oa->areaid;
444

    
445
  body = originate_rt_lsa_body(oa, &lsa.length);
446
  lsasum_calculate(&lsa, body);
447
  oa->rt = lsa_install_new(po, &lsa, dom, body);
448
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
449
}
450

    
451
void
452
update_rt_lsa(struct ospf_area *oa)
453
{
454
  struct proto_ospf *po = oa->po;
455

    
456
  if ((oa->rt) && ((oa->rt->inst_t + MINLSINTERVAL)) > now)
457
    return;
458
  /*
459
   * Tick is probably set to very low value. We cannot
460
   * originate new LSA before MINLSINTERVAL. We will
461
   * try to do it next tick.
462
   */
463

    
464
  originate_rt_lsa(oa);
465
#ifdef OSPFv3
466
  originate_prefix_rt_lsa(oa);
467
#endif
468

    
469
  schedule_rtcalc(po);
470
  oa->origrt = 0;
471
}
472

    
473
static void *
474
originate_net_lsa_body(struct ospf_iface *ifa, u16 *length,
475
                       struct proto_ospf *po)
476
{
477
  u16 i = 1;
478
  struct ospf_neighbor *n;
479
  struct ospf_lsa_net *net;
480
  int nodes = ifa->fadj + 1;
481

    
482
  net = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_net)
483
                 + nodes * sizeof(u32));
484

    
485
#ifdef OSPFv2
486
  net->netmask = ipa_mkmask(ifa->iface->addr->pxlen);
487
#endif
488

    
489
#ifdef OSPFv3
490
  /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */
491
  struct top_hash_entry *en;
492
  u32 options = 0;
493
#endif
494

    
495
  net->routers[0] = po->router_id;
496

    
497
  WALK_LIST(n, ifa->neigh_list)
498
  {
499
    if (n->state == NEIGHBOR_FULL)
500
    {
501
#ifdef OSPFv3
502
      en = ospf_hash_find(po->gr, ifa->iface->index, n->iface_id, n->rid, LSA_T_LINK);
503
      if (en)
504
        options |= ((struct ospf_lsa_link *) en->lsa_body)->options;
505
#endif
506

    
507
      net->routers[i] = n->rid;
508
      i++;
509
    }
510
  }
511
  ASSERT(i == nodes);
512

    
513
#ifdef OSPFv3
514
  net->options = options & OPTIONS_MASK;
515
#endif
516
  
517
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_net)
518
    + nodes * sizeof(u32);
519
  return net;
520
}
521

    
522

    
523
/**
524
 * originate_net_lsa - originates of deletes network LSA
525
 * @ifa: interface which is LSA originated for
526
 *
527
 * Interface counts number of adjacent neighbors. If this number is
528
 * lower than one or interface is not in state %OSPF_IS_DR it deletes
529
 * and premature ages instance of network LSA for specified interface.
530
 * In other case, new instance of network LSA is originated.
531
 */
532
void
533
originate_net_lsa(struct ospf_iface *ifa)
534
{
535
  struct proto_ospf *po = ifa->oa->po;
536
  struct proto *p = &po->proto;
537
  struct ospf_lsa_header lsa;
538
  u32 dom = ifa->oa->areaid;
539
  
540
  void *body;
541

    
542
  OSPF_TRACE(D_EVENTS, "Originating network-LSA for iface %s",
543
             ifa->iface->name);
544

    
545
  lsa.age = 0;
546
  lsa.type = LSA_T_NET;
547

    
548
#ifdef OSPFv2
549
  lsa.options = ifa->oa->options;
550
  lsa.id = ipa_to_u32(ifa->iface->addr->ip);
551
#else /* OSPFv3 */
552
  lsa.id = ifa->iface->index;
553
#endif
554

    
555
  lsa.rt = po->router_id;
556
  lsa.sn = ifa->net_lsa ? (ifa->net_lsa->lsa.sn + 1) : LSA_INITSEQNO;
557

    
558
  body = originate_net_lsa_body(ifa, &lsa.length, po);
559
  lsasum_calculate(&lsa, body);
560
  ifa->net_lsa = lsa_install_new(po, &lsa, dom, body);
561
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
562
}
563

    
564
void
565
flush_net_lsa(struct ospf_iface *ifa)
566
{
567
  struct proto_ospf *po = ifa->oa->po;
568
  struct proto *p = &po->proto;
569
  u32 dom = ifa->oa->areaid;
570

    
571
  if (ifa->net_lsa == NULL)
572
    return;
573

    
574
  OSPF_TRACE(D_EVENTS, "Flushing network-LSA for iface %s",
575
             ifa->iface->name);
576
  ifa->net_lsa->lsa.sn += 1;
577
  ifa->net_lsa->lsa.age = LSA_MAXAGE;
578
  lsasum_calculate(&ifa->net_lsa->lsa, ifa->net_lsa->lsa_body);
579
  ospf_lsupd_flood(po, NULL, NULL, &ifa->net_lsa->lsa, dom, 0);
580
  flush_lsa(ifa->net_lsa, po);
581
  ifa->net_lsa = NULL;
582
}
583

    
584
void
585
update_net_lsa(struct ospf_iface *ifa)
586
{
587
  struct proto_ospf *po = ifa->oa->po;
588
 
589
  if (ifa->net_lsa && ((ifa->net_lsa->inst_t + MINLSINTERVAL) > now))
590
    return;
591
  /*
592
   * It's too early to originate new network LSA. We will
593
   * try to do it next tick
594
   */
595

    
596
  if ((ifa->state != OSPF_IS_DR) || (ifa->fadj == 0))
597
    {
598
      flush_net_lsa(ifa);
599
#ifdef OSPFv3
600
      flush_prefix_net_lsa(ifa);
601
#endif
602
    }
603
  else
604
    {
605
      originate_net_lsa(ifa);
606
#ifdef OSPFv3
607
      originate_prefix_net_lsa(ifa);
608
#endif
609
    }
610

    
611
  schedule_rtcalc(po);
612
  ifa->orignet = 0;
613
}
614

    
615
#ifdef OSPFv2
616

    
617
static inline void *
618
originate_sum_lsa_body(struct proto_ospf *po, u16 *length, u32 mlen, u32 metric)
619
{
620
  struct ospf_lsa_sum *sum = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_sum));
621
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_sum);
622

    
623
  sum->netmask = ipa_mkmask(mlen);
624
  sum->metric = metric;
625

    
626
  return sum;
627
}
628

    
629
#define originate_sum_net_lsa_body(po,length,fn,metric) \
630
  originate_sum_lsa_body(po, length, (fn)->pxlen, metric)
631

    
632
#define originate_sum_rt_lsa_body(po,length,drid,metric,options) \
633
  originate_sum_lsa_body(po, length, 0, metric)
634

    
635
static inline int
636
check_sum_net_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en)
637
{
638
  struct ospf_lsa_sum *sum = en->lsa_body;
639
  return fn->pxlen != ipa_mklen(sum->netmask);
640
}
641

    
642
static inline int
643
check_ext_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en)
644
{
645
  struct ospf_lsa_ext *ext = en->lsa_body;
646
  return fn->pxlen != ipa_mklen(ext->netmask);
647
}
648

    
649
#else /* OSPFv3 */
650

    
651
static inline void *
652
originate_sum_net_lsa_body(struct proto_ospf *po, u16 *length, struct fib_node *fn, u32 metric)
653
{
654
  int size = sizeof(struct ospf_lsa_sum_net) + IPV6_PREFIX_SPACE(fn->pxlen);
655
  struct ospf_lsa_sum_net *sum = mb_alloc(po->proto.pool, size);
656
  *length = sizeof(struct ospf_lsa_header) + size;
657

    
658
  sum->metric = metric;
659
  put_ipv6_prefix(sum->prefix, fn->prefix, fn->pxlen, 0, 0);
660

    
661
  return sum;
662
}
663

    
664
static inline int
665
check_sum_net_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en)
666
{
667
  struct ospf_lsa_sum_net *sum = en->lsa_body;
668
  ip_addr prefix;
669
  int pxlen;
670
  u8 pxopts;
671
  u16 rest;
672

    
673
  lsa_get_ipv6_prefix(sum->prefix, &prefix, &pxlen, &pxopts, &rest);
674
  return (fn->pxlen != pxlen) || !ipa_equal(fn->prefix, prefix);
675
}
676

    
677
static inline int
678
check_ext_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en)
679
{
680
  struct ospf_lsa_ext *ext = en->lsa_body;
681
  ip_addr prefix;
682
  int pxlen;
683
  u8 pxopts;
684
  u16 rest;
685

    
686
  lsa_get_ipv6_prefix(ext->rest, &prefix, &pxlen, &pxopts, &rest);
687
  return (fn->pxlen != pxlen) || !ipa_equal(fn->prefix, prefix);
688
}
689

    
690
static inline void *
691
originate_sum_rt_lsa_body(struct proto_ospf *po, u16 *length, u32 drid, u32 metric, u32 options)
692
{
693
  struct ospf_lsa_sum_rt *sum = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_sum_rt));
694
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_sum_rt);
695

    
696
  sum->options = options & OPTIONS_MASK;
697
  sum->metric = metric;
698
  sum->drid = drid;
699

    
700
  return sum;
701
}
702

    
703
#endif
704

    
705
void
706
originate_sum_net_lsa(struct ospf_area *oa, struct fib_node *fn, int metric)
707
{
708
  struct proto_ospf *po = oa->po;
709
  struct proto *p = &po->proto;
710
  struct top_hash_entry *en;
711
  u32 dom = oa->areaid;
712
  struct ospf_lsa_header lsa;
713
  void *body;
714

    
715
  OSPF_TRACE(D_EVENTS, "Originating net-summary-LSA for %I/%d (metric %d)",
716
             fn->prefix, fn->pxlen, metric);
717

    
718
  /* options argument is used in ORT_NET and OSPFv3 only */
719
  lsa.age = 0;
720
#ifdef OSPFv2
721
  lsa.options = oa->options;
722
#endif
723
  lsa.type = LSA_T_SUM_NET;
724
  lsa.id = fibnode_to_lsaid(po, fn);
725
  lsa.rt = po->router_id;
726
  lsa.sn = LSA_INITSEQNO;
727

    
728
  if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
729
  {
730
    if (check_sum_net_lsaid_collision(fn, en))
731
      {
732
        log(L_ERR, "%s: LSAID collision for %I/%d",
733
            p->name, fn->prefix, fn->pxlen);
734
        return;
735
      }
736

    
737
    lsa.sn = en->lsa.sn + 1;
738
  }
739

    
740
  body = originate_sum_net_lsa_body(po, &lsa.length, fn, metric);
741
  lsasum_calculate(&lsa, body);
742
  en = lsa_install_new(po, &lsa, dom, body);
743
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
744
}
745

    
746
void
747
originate_sum_rt_lsa(struct ospf_area *oa, struct fib_node *fn, int metric, u32 options UNUSED)
748
{
749
  struct proto_ospf *po = oa->po;
750
  struct proto *p = &po->proto;
751
  struct top_hash_entry *en;
752
  u32 dom = oa->areaid;  
753
  struct ospf_lsa_header lsa;
754
  void *body;
755

    
756
  OSPF_TRACE(D_EVENTS, "Originating rt-summary-LSA for %R (metric %d)",
757
             lsa.id, metric);
758

    
759
  lsa.age = 0;
760
#ifdef OSPFv2
761
  lsa.options = oa->options;
762
#endif
763
  lsa.type = LSA_T_SUM_RT;
764
  /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */
765
  lsa.id = ipa_to_rid(fn->prefix);
766
  lsa.rt = po->router_id;
767
  lsa.sn = LSA_INITSEQNO;
768

    
769
  if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
770
    lsa.sn = en->lsa.sn + 1;
771

    
772
  body = originate_sum_rt_lsa_body(po, &lsa.length, lsa.id, metric, options);
773
  lsasum_calculate(&lsa, body);
774
  en = lsa_install_new(po, &lsa, dom, body);
775
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
776
}
777

    
778

    
779
void
780
originate_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type, int metric, u32 options)
781
{
782
  if (type == ORT_NET)
783
    originate_sum_net_lsa(oa, fn, metric);
784
  else
785
    originate_sum_rt_lsa(oa, fn, metric, options);
786
}
787

    
788

    
789
void
790
flush_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type)
791
{
792
  struct proto_ospf *po = oa->po;
793
  struct proto *p = &po->proto;
794
  struct top_hash_entry *en;
795
  struct ospf_lsa_header lsa;
796

    
797
  lsa.rt = po->router_id;
798
  if (type == ORT_NET)
799
    {
800
      lsa.id = fibnode_to_lsaid(po, fn);
801
      lsa.type = LSA_T_SUM_NET;
802
    }
803
  else
804
    {
805
      /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */
806
      lsa.id = ipa_to_rid(fn->prefix);
807
      lsa.type = LSA_T_SUM_RT;
808
    }
809

    
810
  if ((en = ospf_hash_find_header(po->gr, oa->areaid, &lsa)) != NULL)
811
    {
812
      if ((type == ORT_NET) && check_sum_net_lsaid_collision(fn, en))
813
        {
814
          log(L_ERR, "%s: LSAID collision for %I/%d",
815
              p->name, fn->prefix, fn->pxlen);
816
          return;
817
        }
818

    
819
      struct ospf_lsa_sum *sum = en->lsa_body;
820
      en->lsa.age = LSA_MAXAGE;
821
      en->lsa.sn = LSA_MAXSEQNO;
822
      lsasum_calculate(&en->lsa, sum);
823

    
824
      OSPF_TRACE(D_EVENTS, "Flushing summary-LSA (id=%R, type=%d)",
825
                 en->lsa.id, en->lsa.type);
826
      ospf_lsupd_flood(po, NULL, NULL, &en->lsa, oa->areaid, 1);
827
      if (can_flush_lsa(po)) flush_lsa(en, po);
828
    }
829
}
830

    
831

    
832
void
833
check_sum_lsa(struct proto_ospf *po, ort *nf, int dest)
834
{
835
  struct ospf_area *oa;
836
  int flush, mlen;
837
  ip_addr ip;
838

    
839
  if (po->areano < 2) return;
840

    
841
  if ((nf->n.type > RTS_OSPF_IA) && (nf->o.type > RTS_OSPF_IA)) return;
842

    
843
#ifdef LOCAL_DEBUG
844
  DBG("Checking...dest = %d, %I/%d\n", dest, nf->fn.prefix, nf->fn.pxlen);
845
  if (nf->n.oa) DBG("New: met=%d, oa=%d\n", nf->n.metric1, nf->n.oa->areaid);
846
  if (nf->o.oa) DBG("Old: met=%d, oa=%d\n", nf->o.metric1, nf->o.oa->areaid);
847
#endif
848

    
849
  WALK_LIST(oa, po->area_list)
850
  {
851
    flush = 0;
852
    if ((nf->n.metric1 >= LSINFINITY) || (nf->n.type > RTS_OSPF_IA))
853
      flush = 1;
854
    if ((dest == ORT_ROUTER) && (!(nf->n.options & ORTA_ASBR)))
855
      flush = 1;
856
    if ((!nf->n.oa) || (nf->n.oa->areaid == oa->areaid))
857
      flush = 1;
858

    
859
    if (nf->n.ifa) {
860
      if (nf->n.ifa->oa->areaid == oa->areaid)
861
        flush = 1;
862
      }
863
    else flush = 1;
864

    
865
    /* Don't send summary into stub areas
866
     * We send just default route (and later) */
867
    if (oa->stub)
868
      flush = 1;
869
    
870
    mlen = nf->fn.pxlen;
871
    ip = ipa_and(nf->fn.prefix, ipa_mkmask(mlen));
872

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

    
876
    if ((!flush) && (dest == ORT_NET) && fib_route(&nf->n.oa->net_fib, ip, mlen))
877
    {
878
      /* The route fits into area networks */
879
      flush = 1;
880
      if ((nf->n.oa == po->backbone) && (oa->trcap)) flush = 0;
881
    }
882

    
883
    if (flush)
884
      flush_sum_lsa(oa, &nf->fn, dest);
885
    else
886
      originate_sum_lsa(oa, &nf->fn, dest, nf->n.metric1, nf->n.options);
887
  }
888
}
889

    
890

    
891
static void *
892
originate_ext_lsa_body(net *n, rte *e, u16 *length, struct proto_ospf *po,
893
                       struct ea_list *attrs)
894
{
895
  struct proto *p = &po->proto;
896
  struct ospf_lsa_ext *ext;
897
  u32 m1 = ea_get_int(attrs, EA_OSPF_METRIC1, LSINFINITY);
898
  u32 m2 = ea_get_int(attrs, EA_OSPF_METRIC2, 10000);
899
  u32 tag = ea_get_int(attrs, EA_OSPF_TAG, 0);
900
  int gw = 0;
901
  int size = sizeof(struct ospf_lsa_ext);
902

    
903
  if ((e->attrs->dest == RTD_ROUTER) &&
904
      !ipa_equal(e->attrs->gw, IPA_NONE) &&
905
      !ipa_has_link_scope(e->attrs->gw) &&
906
      (ospf_iface_find((struct proto_ospf *) p, e->attrs->iface) != NULL))
907
    gw = 1;
908

    
909
#ifdef OSPFv3
910
  size += IPV6_PREFIX_SPACE(n->n.pxlen);
911

    
912
  if (gw)
913
    size += 16;
914
  
915
  if (tag)
916
    size += 4;
917
#endif
918
  
919
  ext = mb_alloc(p->pool, size);
920
  *length = sizeof(struct ospf_lsa_header) + size;
921

    
922
  ext->metric = (m1 != LSINFINITY) ? m1 : (m2 | LSA_EXT_EBIT); 
923

    
924
#ifdef OSPFv2
925
  ext->netmask = ipa_mkmask(n->n.pxlen);
926
  ext->fwaddr = gw ? e->attrs->gw : IPA_NONE;
927
  ext->tag = tag;
928
#else /* OSPFv3 */
929
  u32 *buf = ext->rest;
930
  buf = put_ipv6_prefix(buf, n->n.prefix, n->n.pxlen, 0, 0);
931

    
932
  if (gw)
933
    {
934
      ext->metric |= LSA_EXT_FBIT;
935
      buf = put_ipv6_addr(buf, e->attrs->gw);
936
    }
937

    
938
  if (tag)
939
    {
940
      ext->metric |= LSA_EXT_TBIT;
941
      *buf++ = tag;
942
    }
943
#endif
944

    
945
  return ext;
946
}
947

    
948
/**
949
 * originate_ext_lsa - new route received from nest and filters
950
 * @n: network prefix and mask
951
 * @e: rte
952
 * @po: current instance of OSPF
953
 * @attrs: list of extended attributes
954
 *
955
 * If I receive a message that new route is installed, I try to originate an
956
 * external LSA. The LSA header of such LSA does not contain information about
957
 * prefix length, so if I have to originate multiple LSAs for route with
958
 * different prefixes I try to increment prefix id to find a "free" one.
959
 *
960
 * The function also sets flag ebit. If it's the first time, the new router lsa
961
 * origination is necessary.
962
 */
963
void
964
originate_ext_lsa(net * n, rte * e, struct proto_ospf *po,
965
                  struct ea_list *attrs)
966
{
967
  struct proto *p = &po->proto;
968
  struct fib_node *fn = &n->n;
969
  struct ospf_lsa_header lsa;
970
  struct top_hash_entry *en = NULL;
971
  void *body;
972
  struct ospf_area *oa;
973

    
974
  OSPF_TRACE(D_EVENTS, "Originating AS-external-LSA for %I/%d",
975
             fn->prefix, fn->pxlen);
976

    
977
  lsa.age = 0;
978
#ifdef OSPFv2
979
  lsa.options = 0; /* or oa->options ? */
980
#endif
981
  lsa.type = LSA_T_EXT;
982
  lsa.id = fibnode_to_lsaid(po, fn);
983
  lsa.rt = po->router_id;
984
  lsa.sn = LSA_INITSEQNO;
985

    
986
  if ((en = ospf_hash_find_header(po->gr, 0, &lsa)) != NULL)
987
    {
988
      if (check_ext_lsaid_collision(fn, en))
989
        {
990
          log(L_ERR, "%s: LSAID collision for %I/%d",
991
              p->name, fn->prefix, fn->pxlen);
992
          return;
993
        }
994

    
995
      lsa.sn = en->lsa.sn + 1;
996
    }
997

    
998
  body = originate_ext_lsa_body(n, e, &lsa.length, po, attrs);
999
  lsasum_calculate(&lsa, body);
1000

    
1001
  en = lsa_install_new(po, &lsa, 0, body);
1002
  ospf_lsupd_flood(po, NULL, NULL, &lsa, 0, 1);
1003

    
1004
  if (po->ebit == 0)
1005
  {
1006
    po->ebit = 1;
1007
    WALK_LIST(oa, po->area_list)
1008
    {
1009
      schedule_rt_lsa(oa);
1010
    }
1011
  }
1012
}
1013

    
1014
void
1015
flush_ext_lsa(net *n, struct proto_ospf *po)
1016
{
1017
  struct proto *p = &po->proto;
1018
  struct fib_node *fn = &n->n;
1019
  struct top_hash_entry *en;
1020

    
1021
  OSPF_TRACE(D_EVENTS, "Flushing AS-external-LSA for %I/%d",
1022
             fn->prefix, fn->pxlen);
1023

    
1024
  u32 lsaid = fibnode_to_lsaid(po, fn);
1025

    
1026
  if (en = ospf_hash_find(po->gr, 0, lsaid, po->router_id, LSA_T_EXT))
1027
    {
1028
      if (check_ext_lsaid_collision(fn, en))
1029
        {
1030
          log(L_ERR, "%s: LSAID collision for %I/%d",
1031
              p->name, fn->prefix, fn->pxlen);
1032
          return;
1033
        }
1034

    
1035
      ospf_lsupd_flush_nlsa(po, en);
1036
    }
1037
}
1038

    
1039

    
1040
#ifdef OSPFv3
1041

    
1042
static void *
1043
originate_link_lsa_body(struct ospf_iface *ifa, u16 *length)
1044
{
1045
  struct proto_ospf *po = ifa->oa->po;
1046
  struct ospf_lsa_link *ll;
1047
  int i = 0;
1048
  u8 flags;
1049

    
1050
  ASSERT(po->lsab_used == 0);
1051
  ll = lsab_allocz(po, sizeof(struct ospf_lsa_link));
1052
  ll->options = ifa->oa->options | (ifa->priority << 24);
1053
  ll->lladdr = ifa->lladdr;
1054
  ll = NULL; /* buffer might be reallocated later */
1055

    
1056
  struct ifa *a;
1057
  WALK_LIST(a, ifa->iface->addrs)
1058
    {
1059
      if ((a->flags & IA_SECONDARY) ||
1060
          (a->scope < SCOPE_SITE))
1061
        continue;
1062

    
1063
      flags = (a->pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
1064
      put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(a->pxlen)),
1065
                      a->ip, a->pxlen, flags, 0);
1066
      i++;
1067
    }
1068

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

    
1075
void
1076
originate_link_lsa(struct ospf_iface *ifa)
1077
{
1078
  struct ospf_lsa_header lsa;
1079
  struct proto_ospf *po = ifa->oa->po;
1080
  struct proto *p = &po->proto;
1081
  void *body;
1082

    
1083
  /* FIXME check for vlink and skip that? */
1084
  OSPF_TRACE(D_EVENTS, "Originating link-LSA for iface %s", ifa->iface->name);
1085

    
1086
  lsa.age = 0;
1087
  lsa.type = LSA_T_LINK;
1088
  lsa.id = ifa->iface->index;
1089
  lsa.rt = po->router_id;
1090
  lsa.sn = ifa->link_lsa ? (ifa->link_lsa->lsa.sn + 1) : LSA_INITSEQNO;
1091
  u32 dom = ifa->iface->index;
1092

    
1093
  body = originate_link_lsa_body(ifa, &lsa.length);
1094
  lsasum_calculate(&lsa, body);
1095
  ifa->link_lsa = lsa_install_new(po, &lsa, dom, body);
1096
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
1097

    
1098
  /* Just to be sure to not forget on our link LSA */
1099
  if (ifa->state == OSPF_IS_DR)
1100
    schedule_net_lsa(ifa);
1101
}
1102

    
1103
void
1104
update_link_lsa(struct ospf_iface *ifa)
1105
{
1106
  if (ifa->link_lsa && ((ifa->link_lsa->inst_t + MINLSINTERVAL) > now))
1107
    return;
1108
  /*
1109
   * It's too early to originate new link LSA. We will
1110
   * try to do it next tick
1111
   */
1112
  originate_link_lsa(ifa);
1113
  ifa->origlink = 0;
1114
}
1115

    
1116
static void *
1117
originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length)
1118
{
1119
  struct proto_ospf *po = oa->po;
1120
  struct ospf_iface *ifa;
1121
  struct ospf_lsa_prefix *lp;
1122
  int net_lsa;
1123
  int i = 0;
1124
  u8 flags;
1125

    
1126
  ASSERT(po->lsab_used == 0);
1127
  lp = lsab_allocz(po, sizeof(struct ospf_lsa_prefix));
1128
  lp->ref_type = LSA_T_RT;
1129
  lp->ref_id = 0;
1130
  lp->ref_rt = po->router_id;
1131
  lp = NULL; /* buffer might be reallocated later */
1132

    
1133
  WALK_LIST(ifa, po->iface_list)
1134
  {
1135
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
1136
      continue;
1137

    
1138
    if ((ifa->type == OSPF_IT_BCAST) ||
1139
        (ifa->type == OSPF_IT_NBMA))
1140
      net_lsa = bcast_net_active(ifa);
1141
    else
1142
      net_lsa = 0;
1143

    
1144
    struct ifa *a;
1145
    WALK_LIST(a, ifa->iface->addrs)
1146
      {
1147
        if (((a->pxlen < MAX_PREFIX_LENGTH) && net_lsa) ||
1148
            (a->flags & IA_SECONDARY) ||
1149
            (a->flags & IA_UNNUMBERED) ||
1150
            (a->scope <= SCOPE_LINK) ||
1151
            configured_stubnet(oa, a))
1152
          continue;
1153

    
1154
        flags = (a->pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
1155
        put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(a->pxlen)),
1156
                        a->ip, a->pxlen, flags, ifa->cost);
1157
        i++;
1158
      }
1159
  }
1160

    
1161
  /* FIXME Handle vlinks? see RFC5340, page 38 */
1162

    
1163
  struct ospf_stubnet_config *sn;
1164
  WALK_LIST(sn, oa->ac->stubnet_list)
1165
    if (!sn->hidden)
1166
      {
1167
        flags = (sn->px.len < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
1168
        put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(sn->px.len)),
1169
                        sn->px.addr, sn->px.len, flags, sn->cost);
1170
        i++;
1171
      }
1172

    
1173
  lp = po->lsab;
1174
  lp->pxcount = i;
1175
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
1176
  return lsab_flush(po);
1177
}
1178

    
1179
void
1180
originate_prefix_rt_lsa(struct ospf_area *oa)
1181
{
1182
  struct proto_ospf *po = oa->po;
1183
  struct proto *p = &po->proto;  
1184
  struct ospf_lsa_header lsa;
1185
  void *body;
1186

    
1187
  OSPF_TRACE(D_EVENTS, "Originating router prefix-LSA for area %R", oa->areaid);
1188

    
1189
  lsa.age = 0;
1190
  lsa.type = LSA_T_PREFIX;
1191
  lsa.id = 0;
1192
  lsa.rt = po->router_id;
1193
  lsa.sn = oa->pxr_lsa ? (oa->pxr_lsa->lsa.sn + 1) : LSA_INITSEQNO;
1194
  u32 dom = oa->areaid;
1195

    
1196
  body = originate_prefix_rt_lsa_body(oa, &lsa.length);
1197
  lsasum_calculate(&lsa, body);
1198
  oa->pxr_lsa = lsa_install_new(po, &lsa, dom, body);
1199
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
1200
}
1201

    
1202

    
1203
static inline int
1204
prefix_space(u32 *buf)
1205
{
1206
  int pxl = *buf >> 24;
1207
  return IPV6_PREFIX_SPACE(pxl);
1208
}
1209

    
1210
static inline int
1211
prefix_same(u32 *b1, u32 *b2)
1212
{
1213
  int pxl1 = *b1 >> 24;
1214
  int pxl2 = *b2 >> 24;
1215
  int pxs, i;
1216
  
1217
  if (pxl1 != pxl2)
1218
    return 0;
1219

    
1220
  pxs = IPV6_PREFIX_WORDS(pxl1);
1221
  for (i = 1; i < pxs; i++)
1222
    if (b1[i] != b2[i])
1223
      return 0;
1224

    
1225
  return 1;
1226
}
1227

    
1228
static inline u32 *
1229
prefix_advance(u32 *buf)
1230
{
1231
  int pxl = *buf >> 24;
1232
  return buf + IPV6_PREFIX_WORDS(pxl);
1233
}
1234

    
1235
static void
1236
add_prefix(struct proto_ospf *po, u32 *px, int offset, int *pxc)
1237
{
1238
  u32 *pxl = lsab_offset(po, offset);
1239
  int i;
1240
  for (i = 0; i < *pxc; i++)
1241
    {
1242
      if (prefix_same(px, pxl))
1243
        {
1244
          /* Options should be logically OR'ed together */
1245
          *pxl |= *px;
1246
          return;
1247
        }
1248
      pxl = prefix_advance(pxl);
1249
    }
1250

    
1251
  ASSERT(pxl == lsab_end(po));
1252

    
1253
  int pxspace = prefix_space(px);
1254
  pxl = lsab_alloc(po, pxspace);
1255
  memcpy(pxl, px, pxspace);
1256
  (*pxc)++;
1257
}
1258

    
1259
static void
1260
add_link_lsa(struct proto_ospf *po, struct top_hash_entry *en, int offset, int *pxc)
1261
{
1262
  struct ospf_lsa_link *ll = en->lsa_body;
1263
  u32 *pxb = ll->rest;
1264
  int j;
1265

    
1266
  for (j = 0; j < ll->pxcount; j++)
1267
    {
1268
      add_prefix(po, pxb, offset, pxc);
1269
      pxb = prefix_advance(pxb);
1270
    }
1271
}
1272

    
1273

    
1274

    
1275
static void *
1276
originate_prefix_net_lsa_body(struct ospf_iface *ifa, u16 *length)
1277
{
1278
  struct proto_ospf *po = ifa->oa->po;
1279
  struct ospf_lsa_prefix *lp;
1280
  struct ospf_neighbor *n;
1281
  struct top_hash_entry *en;
1282
  int pxc, offset;
1283

    
1284
  ASSERT(po->lsab_used == 0);
1285
  lp = lsab_allocz(po, sizeof(struct ospf_lsa_prefix));
1286
  lp->ref_type = LSA_T_NET;
1287
  lp->ref_id = ifa->net_lsa->lsa.id;
1288
  lp->ref_rt = po->router_id;
1289
  lp = NULL; /* buffer might be reallocated later */
1290

    
1291
  pxc = 0;
1292
  offset = po->lsab_used;
1293

    
1294
  /* Find all Link LSAs associated with the link and merge their prefixes */
1295
  if (ifa->link_lsa)
1296
    add_link_lsa(po, ifa->link_lsa, offset, &pxc);
1297

    
1298
  WALK_LIST(n, ifa->neigh_list)
1299
    if ((n->state == NEIGHBOR_FULL) &&
1300
              (en = ospf_hash_find(po->gr, ifa->iface->index, n->iface_id, n->rid, LSA_T_LINK)))
1301
      add_link_lsa(po, en, offset, &pxc);
1302

    
1303
  lp = po->lsab;
1304
  lp->pxcount = pxc;
1305
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
1306
  return lsab_flush(po);
1307
}
1308

    
1309
void
1310
originate_prefix_net_lsa(struct ospf_iface *ifa)
1311
{
1312
  struct proto_ospf *po = ifa->oa->po;
1313
  struct proto *p = &po->proto;
1314
  struct ospf_lsa_header lsa;
1315
  void *body;
1316

    
1317
  OSPF_TRACE(D_EVENTS, "Originating network prefix-LSA for iface %s",
1318
             ifa->iface->name);
1319

    
1320
  lsa.age = 0;
1321
  lsa.type = LSA_T_PREFIX;
1322
  lsa.id = ifa->iface->index;
1323
  lsa.rt = po->router_id;
1324
  lsa.sn = ifa->pxn_lsa ? (ifa->pxn_lsa->lsa.sn + 1) : LSA_INITSEQNO;
1325
  u32 dom = ifa->oa->areaid;
1326

    
1327
  body = originate_prefix_net_lsa_body(ifa, &lsa.length);
1328
  lsasum_calculate(&lsa, body);
1329
  ifa->pxn_lsa = lsa_install_new(po, &lsa, dom, body);
1330
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
1331
}
1332

    
1333
void
1334
flush_prefix_net_lsa(struct ospf_iface *ifa)
1335
{
1336
  struct proto_ospf *po = ifa->oa->po;
1337
  struct proto *p = &po->proto;
1338
  struct top_hash_entry *en = ifa->pxn_lsa;
1339
  u32 dom = ifa->oa->areaid;
1340

    
1341
  if (en == NULL)
1342
    return;
1343

    
1344
  OSPF_TRACE(D_EVENTS, "Flushing network prefix-LSA for iface %s",
1345
             ifa->iface->name);
1346

    
1347
  en->lsa.sn += 1;
1348
  en->lsa.age = LSA_MAXAGE;
1349
  lsasum_calculate(&en->lsa, en->lsa_body);
1350
  ospf_lsupd_flood(po, NULL, NULL, &en->lsa, dom, 0);
1351
  flush_lsa(en, po);
1352
  ifa->pxn_lsa = NULL;
1353
}
1354

    
1355

    
1356
#endif
1357

    
1358

    
1359
static void
1360
ospf_top_ht_alloc(struct top_graph *f)
1361
{
1362
  f->hash_size = 1 << f->hash_order;
1363
  f->hash_mask = f->hash_size - 1;
1364
  if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
1365
    f->hash_entries_max = ~0;
1366
  else
1367
    f->hash_entries_max = f->hash_size HASH_HI_MARK;
1368
  if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
1369
    f->hash_entries_min = 0;
1370
  else
1371
    f->hash_entries_min = f->hash_size HASH_LO_MARK;
1372
  DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
1373
      f->hash_order, f->hash_size, f->hash_entries_min, f->hash_entries_max);
1374
  f->hash_table =
1375
    mb_alloc(f->pool, f->hash_size * sizeof(struct top_hash_entry *));
1376
  bzero(f->hash_table, f->hash_size * sizeof(struct top_hash_entry *));
1377
}
1378

    
1379
static inline void
1380
ospf_top_ht_free(struct top_hash_entry **h)
1381
{
1382
  mb_free(h);
1383
}
1384

    
1385
static inline u32
1386
ospf_top_hash_u32(u32 a)
1387
{
1388
  /* Shamelessly stolen from IP address hashing in ipv4.h */
1389
  a ^= a >> 16;
1390
  a ^= a << 10;
1391
  return a;
1392
}
1393

    
1394
static inline unsigned
1395
ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type)
1396
{
1397
  /* In OSPFv2, we don't know Router ID when looking for network LSAs.
1398
     In OSPFv3, we don't know LSA ID when looking for router LSAs.
1399
     In both cases, there is (usually) just one (or small number)
1400
     appropriate LSA, so we just clear unknown part of key. */
1401

    
1402
  return (
1403
#ifdef OSPFv2
1404
          ((type == LSA_T_NET) ? 0 : ospf_top_hash_u32(rtrid)) +
1405
          ospf_top_hash_u32(lsaid) + 
1406
#else /* OSPFv3 */
1407
          ospf_top_hash_u32(rtrid) +
1408
          ((type == LSA_T_RT) ? 0 : ospf_top_hash_u32(lsaid)) +
1409
#endif
1410
          type + domain) & f->hash_mask;
1411

    
1412
  /*
1413
  return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
1414
          type + areaid) & f->hash_mask;
1415
  */
1416
}
1417

    
1418
/**
1419
 * ospf_top_new - allocated new topology database
1420
 * @p: current instance of ospf
1421
 *
1422
 * this dynamically hashed structure is often used for keeping lsas. mainly
1423
 * its used in @ospf_area structure.
1424
 */
1425
struct top_graph *
1426
ospf_top_new(pool *pool)
1427
{
1428
  struct top_graph *f;
1429

    
1430
  f = mb_allocz(pool, sizeof(struct top_graph));
1431
  f->pool = pool;
1432
  f->hash_slab = sl_new(f->pool, sizeof(struct top_hash_entry));
1433
  f->hash_order = HASH_DEF_ORDER;
1434
  ospf_top_ht_alloc(f);
1435
  f->hash_entries = 0;
1436
  f->hash_entries_min = 0;
1437
  return f;
1438
}
1439

    
1440
void
1441
ospf_top_free(struct top_graph *f)
1442
{
1443
  rfree(f->hash_slab);
1444
  ospf_top_ht_free(f->hash_table);
1445
  mb_free(f);
1446
}
1447

    
1448
static void
1449
ospf_top_rehash(struct top_graph *f, int step)
1450
{
1451
  unsigned int oldn, oldh;
1452
  struct top_hash_entry **n, **oldt, **newt, *e, *x;
1453

    
1454
  oldn = f->hash_size;
1455
  oldt = f->hash_table;
1456
  DBG("re-hashing topology hash from order %d to %d\n", f->hash_order,
1457
      f->hash_order + step);
1458
  f->hash_order += step;
1459
  ospf_top_ht_alloc(f);
1460
  newt = f->hash_table;
1461

    
1462
  for (oldh = 0; oldh < oldn; oldh++)
1463
  {
1464
    e = oldt[oldh];
1465
    while (e)
1466
    {
1467
      x = e->next;
1468
      n = newt + ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa.type);
1469
      e->next = *n;
1470
      *n = e;
1471
      e = x;
1472
    }
1473
  }
1474
  ospf_top_ht_free(oldt);
1475
}
1476

    
1477
#ifdef OSPFv2
1478

    
1479
u32
1480
ospf_lsa_domain(u32 type, struct ospf_iface *ifa)
1481
{
1482
  return (type == LSA_T_EXT) ? 0 : ifa->oa->areaid;
1483
}
1484

    
1485
#else /* OSPFv3 */
1486

    
1487
u32
1488
ospf_lsa_domain(u32 type, struct ospf_iface *ifa)
1489
{
1490
  switch (type & LSA_SCOPE_MASK)
1491
    {
1492
    case LSA_SCOPE_LINK:
1493
      return ifa->iface->index;
1494

    
1495
    case LSA_SCOPE_AREA:
1496
      return ifa->oa->areaid;
1497

    
1498
    case LSA_SCOPE_AS:
1499
    default:
1500
      return 0;
1501
    }
1502
}
1503

    
1504
#endif
1505

    
1506
struct top_hash_entry *
1507
ospf_hash_find_header(struct top_graph *f, u32 domain, struct ospf_lsa_header *h)
1508
{
1509
  return ospf_hash_find(f, domain, h->id, h->rt, h->type);
1510
}
1511

    
1512
struct top_hash_entry *
1513
ospf_hash_get_header(struct top_graph *f, u32 domain, struct ospf_lsa_header *h)
1514
{
1515
  return ospf_hash_get(f, domain, h->id, h->rt, h->type);
1516
}
1517

    
1518
struct top_hash_entry *
1519
ospf_hash_find(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1520
{
1521
  struct top_hash_entry *e;
1522
  e = f->hash_table[ospf_top_hash(f, domain, lsa, rtr, type)];
1523

    
1524
  while (e && (e->lsa.id != lsa || e->lsa.type != type || e->lsa.rt != rtr || e->domain != domain))
1525
    e = e->next;
1526

    
1527
  return e;
1528
}
1529

    
1530

    
1531
#ifdef OSPFv2
1532

    
1533
/* In OSPFv2, sometimes we don't know Router ID when looking for network LSAs.
1534
   There should be just one, so we find any match. */
1535
struct top_hash_entry *
1536
ospf_hash_find_net(struct top_graph *f, u32 domain, u32 lsa)
1537
{
1538
  struct top_hash_entry *e;
1539
  e = f->hash_table[ospf_top_hash(f, domain, lsa, 0, LSA_T_NET)];
1540

    
1541
  while (e && (e->lsa.id != lsa || e->lsa.type != LSA_T_NET || e->domain != domain))
1542
    e = e->next;
1543

    
1544
  return e;
1545
}
1546

    
1547
#endif
1548

    
1549

    
1550
#ifdef OSPFv3
1551

    
1552
/* In OSPFv3, usually we don't know LSA ID when looking for router
1553
   LSAs. We return matching LSA with smallest LSA ID. */
1554
struct top_hash_entry *
1555
ospf_hash_find_rt(struct top_graph *f, u32 domain, u32 rtr)
1556
{
1557
  struct top_hash_entry *rv = NULL;
1558
  struct top_hash_entry *e;
1559
  e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)];
1560
  
1561
  while (e)
1562
    {
1563
      if (e->lsa.rt == rtr && e->lsa.type == LSA_T_RT && e->domain == domain)
1564
        if (!rv || e->lsa.id < rv->lsa.id)
1565
          rv = e;
1566
      e = e->next;
1567
    }
1568

    
1569
  return rv;
1570
}
1571

    
1572
static inline struct top_hash_entry *
1573
find_matching_rt(struct top_hash_entry *e, u32 domain, u32 rtr)
1574
{
1575
  while (e && (e->lsa.rt != rtr || e->lsa.type != LSA_T_RT || e->domain != domain))
1576
    e = e->next;
1577
  return e;
1578
}
1579

    
1580
struct top_hash_entry *
1581
ospf_hash_find_rt_first(struct top_graph *f, u32 domain, u32 rtr)
1582
{
1583
  struct top_hash_entry *e;
1584
  e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)];
1585
  return find_matching_rt(e, domain, rtr);
1586
}
1587

    
1588
struct top_hash_entry *
1589
ospf_hash_find_rt_next(struct top_hash_entry *e)
1590
{
1591
  return find_matching_rt(e->next, e->domain, e->lsa.rt);
1592
}
1593

    
1594
#endif
1595

    
1596

    
1597
struct top_hash_entry *
1598
ospf_hash_get(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1599
{
1600
  struct top_hash_entry **ee;
1601
  struct top_hash_entry *e;
1602

    
1603
  ee = f->hash_table + ospf_top_hash(f, domain, lsa, rtr, type);
1604
  e = *ee;
1605

    
1606
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type || e->domain != domain))
1607
    e = e->next;
1608

    
1609
  if (e)
1610
    return e;
1611

    
1612
  e = sl_alloc(f->hash_slab);
1613
  e->color = OUTSPF;
1614
  e->dist = LSINFINITY;
1615
  e->nhi = NULL;
1616
  e->nh = IPA_NONE;
1617
  e->lb = IPA_NONE;
1618
  e->lsa.id = lsa;
1619
  e->lsa.rt = rtr;
1620
  e->lsa.type = type;
1621
  e->lsa_body = NULL;
1622
  e->nhi = NULL;
1623
  e->domain = domain;
1624
  e->next = *ee;
1625
  *ee = e;
1626
  if (f->hash_entries++ > f->hash_entries_max)
1627
    ospf_top_rehash(f, HASH_HI_STEP);
1628
  return e;
1629
}
1630

    
1631
void
1632
ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
1633
{
1634
  struct top_hash_entry **ee = f->hash_table + 
1635
    ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa.type);
1636

    
1637
  while (*ee)
1638
  {
1639
    if (*ee == e)
1640
    {
1641
      *ee = e->next;
1642
      sl_free(f->hash_slab, e);
1643
      if (f->hash_entries-- < f->hash_entries_min)
1644
        ospf_top_rehash(f, -HASH_LO_STEP);
1645
      return;
1646
    }
1647
    ee = &((*ee)->next);
1648
  }
1649
  bug("ospf_hash_delete() called for invalid node");
1650
}
1651

    
1652
/*
1653
static void
1654
ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
1655
{
1656

1657
  struct ospf_lsa_rt *rt = NULL;
1658
  struct ospf_lsa_rt_link *rr = NULL;
1659
  struct ospf_lsa_net *ln = NULL;
1660
  u32 *rts = NULL;
1661
  u32 i, max;
1662

1663
  OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
1664
             he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
1665
             he->lsa.checksum, he->domain);
1666

1667

1668
  switch (he->lsa.type)
1669
    {
1670
    case LSA_T_RT:
1671
      rt = he->lsa_body;
1672
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
1673

1674
      for (i = 0; i < lsa_rt_items(&he->lsa); i++)
1675
        OSPF_TRACE(D_EVENTS, "  - %1x %-1R %-1R %5u",
1676
                   rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
1677
      break;
1678

1679
    case LSA_T_NET:
1680
      ln = he->lsa_body;
1681
      rts = (u32 *) (ln + 1);
1682

1683
      for (i = 0; i < lsa_net_items(&he->lsa); i++)
1684
        OSPF_TRACE(D_EVENTS, "  - %-1R", rts[i]);
1685
      break;
1686

1687
    default:
1688
      break;
1689
    }
1690
}
1691

1692
void
1693
ospf_top_dump(struct top_graph *f, struct proto *p)
1694
{
1695
  unsigned int i;
1696
  OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
1697

1698
  for (i = 0; i < f->hash_size; i++)
1699
  {
1700
    struct top_hash_entry *e;
1701
    for (e = f->hash_table[i]; e != NULL; e = e->next)
1702
      ospf_dump_lsa(e, p);
1703
  }
1704
}
1705
*/
1706

    
1707
/* This is very inefficient, please don't call it often */
1708

    
1709
/* I should also test for every LSA if it's in some link state
1710
 * retransmission list for every neighbor. I will not test it.
1711
 * It could happen that I'll receive some strange ls ack's.
1712
 */
1713

    
1714
int
1715
can_flush_lsa(struct proto_ospf *po)
1716
{
1717
  struct ospf_iface *ifa;
1718
  struct ospf_neighbor *n;
1719

    
1720
  WALK_LIST(ifa, po->iface_list)
1721
  {
1722
    WALK_LIST(n, ifa->neigh_list)
1723
    {
1724
      if ((n->state == NEIGHBOR_EXCHANGE) || (n->state == NEIGHBOR_LOADING))
1725
        return 0;
1726

    
1727
      break;
1728
    }
1729
  }
1730

    
1731
  return 1;
1732
}