Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / topology.c @ 48e5f32d

History | View | Annotate | Download (45.7 KB)

1
/*
2
 *        BIRD -- OSPF Topological Database
3
 *
4
 *        (c) 1999       Martin Mares <mj@ucw.cz>
5
 *        (c) 1999--2004 Ondrej Filip <feela@network.cz>
6
 *
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
  /*
85
   * In OSPFv3, it is simpler. There is not a requirement for
86
   * membership of the result in the input network, so we just use a
87
   * hash-based unique ID of a routing table entry for a route that
88
   * originated given LSA. For ext-LSA, it is an imported route in the
89
   * nest's routing table (p->table). For summary-LSA, it is a
90
   * 'source' route in the protocol internal routing table (po->rtf).
91
   */
92
  return fn->uid;
93
}
94

    
95
#endif
96

    
97

    
98
static void *
99
lsab_alloc(struct proto_ospf *po, unsigned size)
100
{
101
  unsigned offset = po->lsab_used;
102
  po->lsab_used += size;
103
  if (po->lsab_used > po->lsab_size)
104
    {
105
      po->lsab_size = MAX(po->lsab_used, 2 * po->lsab_size);
106
      po->lsab = po->lsab ? mb_realloc(po->lsab, po->lsab_size):
107
        mb_alloc(po->proto.pool, po->lsab_size);
108
    }
109
  return ((byte *) po->lsab) + offset;
110
}
111

    
112
static inline void *
113
lsab_allocz(struct proto_ospf *po, unsigned size)
114
{
115
  void *r = lsab_alloc(po, size);
116
  bzero(r, size);
117
  return r;
118
}
119

    
120
static inline void *
121
lsab_flush(struct proto_ospf *po)
122
{
123
  void *r = mb_alloc(po->proto.pool, po->lsab_used);
124
  memcpy(r, po->lsab, po->lsab_used);
125
  po->lsab_used = 0;
126
  return r;
127
}
128

    
129
static inline void *
130
lsab_offset(struct proto_ospf *po, unsigned offset)
131
{
132
  return ((byte *) po->lsab) + offset;
133
}
134

    
135
static inline void *
136
lsab_end(struct proto_ospf *po)
137
{
138
  return ((byte *) po->lsab) + po->lsab_used;
139
}
140

    
141
static s32
142
get_seqnum(struct top_hash_entry *en)
143
{
144
  if (!en)
145
    return LSA_INITSEQNO;
146

    
147
  if (en->lsa.sn == LSA_MAXSEQNO)
148
  {
149
    log(L_WARN "OSPF: Premature origination of LSA (Type: %04x, Id: %R, Rt: %R)",
150
        en->lsa.type, en->lsa.id, en->lsa.rt);
151
    return LSA_INITSEQNO;
152
  }
153

    
154
  return en->lsa.sn + 1;
155
}
156

    
157

    
158
static int
159
configured_stubnet(struct ospf_area *oa, struct ifa *a)
160
{
161
  if (!oa->ac)
162
    return 0;
163

    
164
  /* Does not work for IA_PEER addresses, but it is not called on these */
165
  struct ospf_stubnet_config *sn;
166
  WALK_LIST(sn, oa->ac->stubnet_list)
167
    {
168
      if (sn->summary)
169
        {
170
          if (ipa_in_net(a->prefix, sn->px.addr, sn->px.len) && (a->pxlen >= sn->px.len))
171
            return 1;
172
        }
173
      else
174
        {
175
          if (ipa_equal(a->prefix, sn->px.addr) && (a->pxlen == sn->px.len))
176
            return 1;
177
        }
178
    }
179
  return 0;
180
}
181

    
182
int
183
bcast_net_active(struct ospf_iface *ifa)
184
{
185
  struct ospf_neighbor *neigh;
186

    
187
  if (ifa->state == OSPF_IS_WAITING)
188
    return 0;
189

    
190
  WALK_LIST(neigh, ifa->neigh_list)
191
    {
192
      if (neigh->state == NEIGHBOR_FULL)
193
        {
194
          if (neigh->rid == ifa->drid)
195
            return 1;
196

    
197
          if (ifa->state == OSPF_IS_DR)
198
            return 1;
199
        }
200
    }
201

    
202
  return 0;
203
}
204

    
205

    
206
#ifdef OSPFv2
207

    
208
static void *
209
originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
210
{
211
  struct proto_ospf *po = oa->po;
212
  struct ospf_iface *ifa;
213
  int i = 0, bitv = 0;
214
  struct ospf_lsa_rt *rt;
215
  struct ospf_lsa_rt_link *ln;
216
  struct ospf_neighbor *neigh;
217

    
218
  ASSERT(po->lsab_used == 0);
219
  rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt));
220

    
221
  rt->options = 0;
222

    
223
  if (po->areano > 1)
224
    rt->options |= OPT_RT_B;
225

    
226
  if ((po->areano > 1) && oa_is_nssa(oa) && oa->ac->translator)
227
    rt->options |= OPT_RT_NT;
228

    
229
  if (po->ebit && !oa_is_stub(oa))
230
    rt->options |= OPT_RT_E;
231

    
232
  rt = NULL; /* buffer might be reallocated later */
233

    
234
  WALK_LIST(ifa, po->iface_list)
235
  {
236
    int net_lsa = 0;
237
    u32 link_cost = po->stub_router ? 0xffff : ifa->cost;
238

    
239
    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
240
        (!EMPTY_LIST(ifa->neigh_list)))
241
    {
242
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
243
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
244
        bitv = 1;
245
    }
246

    
247
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
248
      continue;
249

    
250
    ifa->rt_pos_beg = i;
251

    
252
    /* RFC2328 - 12.4.1.1-4 */
253
    switch (ifa->type)
254
      {
255
      case OSPF_IT_PTP:
256
      case OSPF_IT_PTMP:
257
        WALK_LIST(neigh, ifa->neigh_list)
258
          if (neigh->state == NEIGHBOR_FULL)
259
          {
260
            ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
261
            ln->type = LSART_PTP;
262
            ln->id = neigh->rid;
263

    
264
            /*
265
             * ln->data should be ifa->iface_id in case of no/ptp
266
             * address (ifa->addr->flags & IA_PEER) on PTP link (see
267
             * RFC 2328 12.4.1.1.), but the iface ID value has no use,
268
             * while using IP address even in this case is here for
269
             * compatibility with some broken implementations that use
270
             * this address as a next-hop.
271
             */
272
            ln->data = ipa_to_u32(ifa->addr->ip);
273
            ln->metric = link_cost;
274
            ln->padding = 0;
275
            i++;
276
          }
277
        break;
278

    
279
      case OSPF_IT_BCAST:
280
      case OSPF_IT_NBMA:
281
        if (bcast_net_active(ifa))
282
          {
283
            ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
284
            ln->type = LSART_NET;
285
            ln->id = ipa_to_u32(ifa->drip);
286
            ln->data = ipa_to_u32(ifa->addr->ip);
287
            ln->metric = link_cost;
288
            ln->padding = 0;
289
            i++;
290
            net_lsa = 1;
291
          }
292
        break;
293

    
294
      case OSPF_IT_VLINK:
295
        neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
296
        if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
297
        {
298
          ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
299
          ln->type = LSART_VLNK;
300
          ln->id = neigh->rid;
301
          ln->data = ipa_to_u32(ifa->addr->ip);
302
          ln->metric = link_cost;
303
          ln->padding = 0;
304
          i++;
305
        }
306
        break;
307

    
308
      default:
309
        log("Unknown interface type %s", ifa->ifname);
310
        break;
311
      }
312

    
313
    ifa->rt_pos_end = i;
314

    
315
    /* Now we will originate stub area if there is no primary */
316
    if (net_lsa ||
317
        (ifa->type == OSPF_IT_VLINK) ||
318
        ((ifa->addr->flags & IA_PEER) && ! ifa->cf->stub) ||
319
        configured_stubnet(oa, ifa->addr))
320
      continue;
321

    
322
    ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
323
    if ((ifa->addr->flags & IA_HOST) ||
324
        (ifa->state == OSPF_IS_LOOP) ||
325
        (ifa->type == OSPF_IT_PTMP))
326
    {
327
      /* Host stub entry */
328
      ln->type = LSART_STUB;
329
      ln->id = ipa_to_u32(ifa->addr->ip);
330
      ln->data = 0xffffffff;
331
      ln->metric = 0;
332
      ln->padding = 0;
333
    }
334
    else 
335
    {
336
      /* Network stub entry */
337
      ln->type = LSART_STUB;
338
      ln->id = ipa_to_u32(ifa->addr->prefix);
339
      ln->data = ipa_to_u32(ipa_mkmask(ifa->addr->pxlen));
340
      ln->metric = ifa->cost;
341
      ln->padding = 0;
342
    }
343
    i++;
344

    
345
    ifa->rt_pos_end = i;
346
  }
347

    
348
  struct ospf_stubnet_config *sn;
349
  if (oa->ac)
350
    WALK_LIST(sn, oa->ac->stubnet_list)
351
      if (!sn->hidden)
352
      {
353
        ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
354
        ln->type = LSART_STUB;
355
        ln->id = ipa_to_u32(sn->px.addr);
356
        ln->data = ipa_to_u32(ipa_mkmask(sn->px.len));
357
        ln->metric = sn->cost;
358
        ln->padding = 0;
359
        i++;
360
      }
361

    
362
  rt = po->lsab;
363
  rt->links = i;
364

    
365
  if (bitv) 
366
    rt->options |= OPT_RT_V;
367

    
368
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
369
  return lsab_flush(po);
370
}
371

    
372
#else /* OSPFv3 */
373

    
374
static void
375
add_lsa_rt_link(struct proto_ospf *po, struct ospf_iface *ifa, u8 type, u32 nif, u32 id)
376
{
377
  struct ospf_lsa_rt_link *ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link));
378
  ln->type = type;
379
  ln->padding = 0;
380
  ln->metric = ifa->cost;
381
  ln->lif = ifa->iface_id;
382
  ln->nif = nif;
383
  ln->id = id;
384
}
385

    
386
static void *
387
originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
388
{
389
  struct proto_ospf *po = oa->po;
390
  struct ospf_iface *ifa;
391
  int bitv = 0;
392
  int i = 0;
393
  struct ospf_lsa_rt *rt;
394
  struct ospf_neighbor *neigh;
395

    
396
  ASSERT(po->lsab_used == 0);
397
  rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt));
398

    
399
  rt->options = oa->options & OPTIONS_MASK;
400

    
401
  if (po->areano > 1)
402
    rt->options |= OPT_RT_B;
403

    
404
  if ((po->areano > 1) && oa_is_nssa(oa) && oa->ac->translator)
405
    rt->options |= OPT_RT_NT;
406

    
407
  if (po->ebit && !oa_is_stub(oa))
408
    rt->options |= OPT_RT_E;
409

    
410
  rt = NULL; /* buffer might be reallocated later */
411

    
412
  WALK_LIST(ifa, po->iface_list)
413
  {
414
    if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
415
        (!EMPTY_LIST(ifa->neigh_list)))
416
    {
417
      neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
418
      if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
419
        bitv = 1;
420
    }
421

    
422
    if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
423
      continue;
424

    
425
    ifa->rt_pos_beg = i;
426

    
427
    /* RFC5340 - 4.4.3.2 */
428
    switch (ifa->type)
429
      {
430
      case OSPF_IT_PTP:
431
      case OSPF_IT_PTMP:
432
        WALK_LIST(neigh, ifa->neigh_list)
433
          if (neigh->state == NEIGHBOR_FULL)
434
            add_lsa_rt_link(po, ifa, LSART_PTP, neigh->iface_id, neigh->rid), i++;
435
        break;
436

    
437
      case OSPF_IT_BCAST:
438
      case OSPF_IT_NBMA:
439
        if (bcast_net_active(ifa))
440
          add_lsa_rt_link(po, ifa, LSART_NET, ifa->dr_iface_id, ifa->drid), i++;
441
        break;
442

    
443
      case OSPF_IT_VLINK:
444
        neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
445
        if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
446
          add_lsa_rt_link(po, ifa, LSART_VLNK, neigh->iface_id, neigh->rid), i++;
447
        break;
448

    
449
      default:
450
        log("Unknown interface type %s", ifa->ifname);
451
        break;
452
      }
453

    
454
    ifa->rt_pos_end = i;
455
  }
456

    
457
  if (bitv)
458
    {
459
      rt = po->lsab;
460
      rt->options |= OPT_RT_V;
461
    }
462

    
463
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
464
  return lsab_flush(po);
465
}
466

    
467
#endif
468

    
469
/**
470
 * originate_rt_lsa - build new instance of router LSA
471
 * @oa: ospf_area which is LSA built to
472
 *
473
 * It builds router LSA walking through all OSPF interfaces in
474
 * specified OSPF area. This function is mostly called from
475
 * area_disp(). Builds new LSA, increases sequence number (if old
476
 * instance exists) and sets age of LSA to zero.
477
 */
478
void
479
originate_rt_lsa(struct ospf_area *oa)
480
{
481
  struct ospf_lsa_header lsa;
482
  struct proto_ospf *po = oa->po;
483
  struct proto *p = &po->proto;
484
  void *body;
485

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

    
488
  lsa.age = 0;
489
  lsa.type = LSA_T_RT;
490
  
491
#ifdef OSPFv2
492
  lsa.options = oa->options;
493
  lsa.id = po->router_id;
494
#else /* OSPFv3 */
495
  lsa.id = 0;
496
#endif
497

    
498
  lsa.rt = po->router_id;
499
  lsa.sn = get_seqnum(oa->rt);
500
  u32 dom = oa->areaid;
501

    
502
  body = originate_rt_lsa_body(oa, &lsa.length);
503
  lsasum_calculate(&lsa, body);
504
  oa->rt = lsa_install_new(po, &lsa, dom, body);
505
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
506
}
507

    
508
void
509
update_rt_lsa(struct ospf_area *oa)
510
{
511
  struct proto_ospf *po = oa->po;
512

    
513
  if ((oa->rt) && ((oa->rt->inst_t + MINLSINTERVAL)) > now)
514
    return;
515
  /*
516
   * Tick is probably set to very low value. We cannot
517
   * originate new LSA before MINLSINTERVAL. We will
518
   * try to do it next tick.
519
   */
520

    
521
  originate_rt_lsa(oa);
522
#ifdef OSPFv3
523
  originate_prefix_rt_lsa(oa);
524
#endif
525

    
526
  schedule_rtcalc(po);
527
  oa->origrt = 0;
528
}
529

    
530
static void *
531
originate_net_lsa_body(struct ospf_iface *ifa, u16 *length,
532
                       struct proto_ospf *po)
533
{
534
  u16 i = 1;
535
  struct ospf_neighbor *n;
536
  struct ospf_lsa_net *net;
537
  int nodes = ifa->fadj + 1;
538

    
539
  net = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_net)
540
                 + nodes * sizeof(u32));
541

    
542
#ifdef OSPFv2
543
  net->netmask = ipa_mkmask(ifa->addr->pxlen);
544
#endif
545

    
546
#ifdef OSPFv3
547
  /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */
548
  struct top_hash_entry *en;
549
  u32 options = 0;
550
#endif
551

    
552
  net->routers[0] = po->router_id;
553

    
554
  WALK_LIST(n, ifa->neigh_list)
555
  {
556
    if (n->state == NEIGHBOR_FULL)
557
    {
558
#ifdef OSPFv3
559
      en = ospf_hash_find(po->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK);
560
      if (en)
561
        options |= ((struct ospf_lsa_link *) en->lsa_body)->options;
562
#endif
563

    
564
      net->routers[i] = n->rid;
565
      i++;
566
    }
567
  }
568
  ASSERT(i == nodes);
569

    
570
#ifdef OSPFv3
571
  net->options = options & OPTIONS_MASK;
572
#endif
573
  
574
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_net)
575
    + nodes * sizeof(u32);
576
  return net;
577
}
578

    
579

    
580
/**
581
 * originate_net_lsa - originates of deletes network LSA
582
 * @ifa: interface which is LSA originated for
583
 *
584
 * Interface counts number of adjacent neighbors. If this number is
585
 * lower than one or interface is not in state %OSPF_IS_DR it deletes
586
 * and premature ages instance of network LSA for specified interface.
587
 * In other case, new instance of network LSA is originated.
588
 */
589
void
590
originate_net_lsa(struct ospf_iface *ifa)
591
{
592
  struct proto_ospf *po = ifa->oa->po;
593
  struct proto *p = &po->proto;
594
  struct ospf_lsa_header lsa;
595
  u32 dom = ifa->oa->areaid;
596
  
597
  void *body;
598

    
599
  OSPF_TRACE(D_EVENTS, "Originating network-LSA for iface %s", ifa->ifname);
600

    
601
  lsa.age = 0;
602
  lsa.type = LSA_T_NET;
603

    
604
#ifdef OSPFv2
605
  lsa.options = ifa->oa->options;
606
  lsa.id = ipa_to_u32(ifa->addr->ip);
607
#else /* OSPFv3 */
608
  lsa.id = ifa->iface_id;
609
#endif
610

    
611
  lsa.rt = po->router_id;
612
  lsa.sn = get_seqnum(ifa->net_lsa);
613

    
614
  body = originate_net_lsa_body(ifa, &lsa.length, po);
615
  lsasum_calculate(&lsa, body);
616
  ifa->net_lsa = lsa_install_new(po, &lsa, dom, body);
617
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
618
}
619

    
620
void
621
flush_net_lsa(struct ospf_iface *ifa)
622
{
623
  struct proto_ospf *po = ifa->oa->po;
624
  struct proto *p = &po->proto;
625
  u32 dom = ifa->oa->areaid;
626

    
627
  if (ifa->net_lsa == NULL)
628
    return;
629

    
630
  OSPF_TRACE(D_EVENTS, "Flushing network-LSA for iface %s", ifa->ifname);
631
  ifa->net_lsa->lsa.sn += 1;
632
  ifa->net_lsa->lsa.age = LSA_MAXAGE;
633
  lsasum_calculate(&ifa->net_lsa->lsa, ifa->net_lsa->lsa_body);
634
  ospf_lsupd_flood(po, NULL, NULL, &ifa->net_lsa->lsa, dom, 0);
635
  flush_lsa(ifa->net_lsa, po);
636
  ifa->net_lsa = NULL;
637
}
638

    
639
void
640
update_net_lsa(struct ospf_iface *ifa)
641
{
642
  struct proto_ospf *po = ifa->oa->po;
643
 
644
  if (ifa->net_lsa && ((ifa->net_lsa->inst_t + MINLSINTERVAL) > now))
645
    return;
646
  /*
647
   * It's too early to originate new network LSA. We will
648
   * try to do it next tick
649
   */
650

    
651
  if ((ifa->state != OSPF_IS_DR) || (ifa->fadj == 0))
652
    {
653
      flush_net_lsa(ifa);
654
#ifdef OSPFv3
655
      flush_prefix_net_lsa(ifa);
656
#endif
657
    }
658
  else
659
    {
660
      originate_net_lsa(ifa);
661
#ifdef OSPFv3
662
      originate_prefix_net_lsa(ifa);
663
#endif
664
    }
665

    
666
  schedule_rtcalc(po);
667
  ifa->orignet = 0;
668
}
669

    
670
#ifdef OSPFv2
671

    
672
static inline void *
673
originate_sum_lsa_body(struct proto_ospf *po, u16 *length, u32 mlen, u32 metric)
674
{
675
  struct ospf_lsa_sum *sum = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_sum));
676
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_sum);
677

    
678
  sum->netmask = ipa_mkmask(mlen);
679
  sum->metric = metric;
680

    
681
  return sum;
682
}
683

    
684
#define originate_sum_net_lsa_body(po,length,fn,metric) \
685
  originate_sum_lsa_body(po, length, (fn)->pxlen, metric)
686

    
687
#define originate_sum_rt_lsa_body(po,length,drid,metric,options) \
688
  originate_sum_lsa_body(po, length, 0, metric)
689

    
690
static inline int
691
check_sum_net_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en)
692
{
693
  struct ospf_lsa_sum *sum = en->lsa_body;
694
  return fn->pxlen != ipa_mklen(sum->netmask);
695
}
696

    
697
static inline int
698
check_sum_lsa_same(struct top_hash_entry *en, u32 metric)
699
{
700
  /* Netmask already checked in check_sum_net_lsaid_collision() */
701
  struct ospf_lsa_sum *sum = en->lsa_body;
702
  return (en->lsa.sn != LSA_MAXSEQNO) && (sum->metric == metric);
703
}
704

    
705
#define check_sum_net_lsa_same(en,metric) \
706
  check_sum_lsa_same(en, metric)
707

    
708
#define check_sum_rt_lsa_same(en,drid,metric,options) \
709
  check_sum_lsa_same(en, metric)
710

    
711

    
712
#else /* OSPFv3 */
713

    
714
static inline void *
715
originate_sum_net_lsa_body(struct proto_ospf *po, u16 *length, struct fib_node *fn, u32 metric)
716
{
717
  int size = sizeof(struct ospf_lsa_sum_net) + IPV6_PREFIX_SPACE(fn->pxlen);
718
  struct ospf_lsa_sum_net *sum = mb_alloc(po->proto.pool, size);
719
  *length = sizeof(struct ospf_lsa_header) + size;
720

    
721
  sum->metric = metric;
722
  put_ipv6_prefix(sum->prefix, fn->prefix, fn->pxlen, 0, 0);
723

    
724
  return sum;
725
}
726

    
727
static inline int
728
check_sum_net_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en)
729
{
730
  struct ospf_lsa_sum_net *sum = en->lsa_body;
731
  ip_addr prefix;
732
  int pxlen;
733
  u8 pxopts;
734
  u16 rest;
735

    
736
  lsa_get_ipv6_prefix(sum->prefix, &prefix, &pxlen, &pxopts, &rest);
737
  return (fn->pxlen != pxlen) || !ipa_equal(fn->prefix, prefix);
738
}
739

    
740
static inline int
741
check_sum_net_lsa_same(struct top_hash_entry *en, u32 metric)
742
{
743
  /* Prefix already checked in check_sum_net_lsaid_collision() */
744
  struct ospf_lsa_sum_net *sum = en->lsa_body;
745
  return (en->lsa.sn != LSA_MAXSEQNO) && (sum->metric == metric);
746
}
747

    
748
static inline void *
749
originate_sum_rt_lsa_body(struct proto_ospf *po, u16 *length, u32 drid, u32 metric, u32 options)
750
{
751
  struct ospf_lsa_sum_rt *sum = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_sum_rt));
752
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_sum_rt);
753

    
754
  sum->options = options;
755
  sum->metric = metric;
756
  sum->drid = drid;
757

    
758
  return sum;
759
}
760

    
761
static inline int
762
check_sum_rt_lsa_same(struct top_hash_entry *en, u32 drid, u32 metric, u32 options)
763
{
764
  struct ospf_lsa_sum_rt *sum = en->lsa_body;
765
  return (en->lsa.sn != LSA_MAXSEQNO) && (sum->options == options) &&
766
    (sum->metric == metric) && (sum->drid == drid);
767
}
768

    
769
#endif
770

    
771
void
772
originate_sum_net_lsa(struct ospf_area *oa, struct fib_node *fn, int metric)
773
{
774
  struct proto_ospf *po = oa->po;
775
  struct proto *p = &po->proto;
776
  struct top_hash_entry *en;
777
  u32 dom = oa->areaid;
778
  struct ospf_lsa_header lsa;
779
  void *body;
780

    
781
  OSPF_TRACE(D_EVENTS, "Originating net-summary-LSA for %I/%d (metric %d)",
782
             fn->prefix, fn->pxlen, metric);
783

    
784
  /* options argument is used in ORT_NET and OSPFv3 only */
785
  lsa.age = 0;
786
#ifdef OSPFv2
787
  lsa.options = oa->options;
788
#endif
789
  lsa.type = LSA_T_SUM_NET;
790
  lsa.id = fibnode_to_lsaid(po, fn);
791
  lsa.rt = po->router_id;
792

    
793
  if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
794
  {
795
    if (check_sum_net_lsaid_collision(fn, en))
796
    {
797
      log(L_ERR "%s: LSAID collision for %I/%d",
798
          p->name, fn->prefix, fn->pxlen);
799
      return;
800
    }
801

    
802
    if (check_sum_net_lsa_same(en, metric))
803
      return;
804
  }
805
  lsa.sn = get_seqnum(en);
806

    
807
  body = originate_sum_net_lsa_body(po, &lsa.length, fn, metric);
808
  lsasum_calculate(&lsa, body);
809
  lsa_install_new(po, &lsa, dom, body);
810
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
811
}
812

    
813
void
814
originate_sum_rt_lsa(struct ospf_area *oa, struct fib_node *fn, int metric, u32 options UNUSED)
815
{
816
  struct proto_ospf *po = oa->po;
817
  struct proto *p = &po->proto;
818
  struct top_hash_entry *en;
819
  u32 dom = oa->areaid;
820
  u32 rid = ipa_to_rid(fn->prefix);
821
  struct ospf_lsa_header lsa;
822
  void *body;
823

    
824
  OSPF_TRACE(D_EVENTS, "Originating rt-summary-LSA for %R (metric %d)",
825
             rid, metric);
826

    
827
  lsa.age = 0;
828
#ifdef OSPFv2
829
  lsa.options = oa->options;
830
#endif
831
  lsa.type = LSA_T_SUM_RT;
832
  /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */
833
  lsa.id = rid;
834
  lsa.rt = po->router_id;
835

    
836
  options &= OPTIONS_MASK;
837
  if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
838
  {
839
    if (check_sum_rt_lsa_same(en, lsa.id, metric, options))
840
      return;
841
  }
842
  lsa.sn = get_seqnum(en);
843

    
844
  body = originate_sum_rt_lsa_body(po, &lsa.length, lsa.id, metric, options);
845
  lsasum_calculate(&lsa, body);
846
  lsa_install_new(po, &lsa, dom, body);
847
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
848
}
849

    
850
void
851
flush_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type)
852
{
853
  struct proto_ospf *po = oa->po;
854
  struct proto *p = &po->proto;
855
  struct top_hash_entry *en;
856
  struct ospf_lsa_header lsa;
857

    
858
  lsa.rt = po->router_id;
859
  if (type == ORT_NET)
860
    {
861
      lsa.id = fibnode_to_lsaid(po, fn);
862
      lsa.type = LSA_T_SUM_NET;
863
    }
864
  else
865
    {
866
      /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */
867
      lsa.id = ipa_to_rid(fn->prefix);
868
      lsa.type = LSA_T_SUM_RT;
869
    }
870

    
871
  if ((en = ospf_hash_find_header(po->gr, oa->areaid, &lsa)) != NULL)
872
    {
873
      OSPF_TRACE(D_EVENTS, "Flushing summary-LSA (id=%R, type=%d)",
874
                 en->lsa.id, en->lsa.type);
875

    
876
      if ((type == ORT_NET) && check_sum_net_lsaid_collision(fn, en))
877
        {
878
          log(L_ERR "%s: LSAID collision for %I/%d",
879
              p->name, fn->prefix, fn->pxlen);
880
          return;
881
        }
882

    
883
      struct ospf_lsa_sum *sum = en->lsa_body;
884
      en->lsa.age = LSA_MAXAGE;
885
      en->lsa.sn = LSA_MAXSEQNO;
886
      lsasum_calculate(&en->lsa, sum);
887
      ospf_lsupd_flood(po, NULL, NULL, &en->lsa, oa->areaid, 1);
888
      if (can_flush_lsa(po)) flush_lsa(en, po);
889
    }
890
}
891

    
892
#ifdef OSPFv2
893

    
894
static inline void *
895
originate_ext_lsa_body(struct proto_ospf *po, u16 *length, struct fib_node *fn,
896
                       u32 metric, ip_addr fwaddr, u32 tag, int pbit UNUSED)
897
{
898
  struct ospf_lsa_ext *ext = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_ext));
899
  *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_ext);
900

    
901
  ext->metric = metric; 
902
  ext->netmask = ipa_mkmask(fn->pxlen);
903
  ext->fwaddr = fwaddr;
904
  ext->tag = tag;
905

    
906
  return ext;
907
}
908

    
909
/*
910
 * check_ext_lsa() combines functions of check_*_lsaid_collision() and
911
 * check_*_lsa_same(). 'en' is existing ext LSA, and rest parameters
912
 * are parameters of new ext route.  Function returns -1 if there is
913
 * LSAID collision, returns 1 if the existing LSA is the same and
914
 * returns 0 otherwise (in that case, we need to originate a new LSA).
915
 *
916
 * Really, checking for the same parameters is not as important as in
917
 * summary LSA origination, because in most cases the duplicate
918
 * external route propagation would be stopped by the nest. But there
919
 * are still some cases (route reload, the same route propagated through
920
 * different protocol) so it is also done here.
921
 */
922

    
923
static inline int
924
check_ext_lsa(struct top_hash_entry *en, struct fib_node *fn, u32 metric, ip_addr fwaddr, u32 tag)
925
{
926
  struct ospf_lsa_ext *ext = en->lsa_body;
927

    
928
  /* LSAID collision */
929
  if  (fn->pxlen != ipa_mklen(ext->netmask))
930
    return -1;
931

    
932
  return (en->lsa.sn != LSA_MAXSEQNO) && (ext->metric == metric) &&
933
    (ext->tag == tag) && ipa_equal(ext->fwaddr,fwaddr);
934
}
935

    
936
#else /* OSPFv3 */
937

    
938
static inline void *
939
originate_ext_lsa_body(struct proto_ospf *po, u16 *length, struct fib_node *fn,
940
                       u32 metric, ip_addr fwaddr, u32 tag, int pbit)
941
{
942
  int size = sizeof(struct ospf_lsa_ext)
943
    + IPV6_PREFIX_SPACE(fn->pxlen)
944
    + (ipa_nonzero(fwaddr) ? 16 : 0)
945
    + (tag ? 4 : 0);
946

    
947
  struct ospf_lsa_ext *ext = mb_alloc(po->proto.pool, size);
948
  *length = sizeof(struct ospf_lsa_header) + size;
949

    
950
  ext->metric = metric;
951

    
952
  u32 *buf = ext->rest;
953
  buf = put_ipv6_prefix(buf, fn->prefix, fn->pxlen, pbit ? OPT_PX_P : 0, 0);
954

    
955
  if (ipa_nonzero(fwaddr))
956
  {
957
    ext->metric |= LSA_EXT_FBIT;
958
    buf = put_ipv6_addr(buf, fwaddr);
959
  }
960

    
961
  if (tag)
962
  {
963
    ext->metric |= LSA_EXT_TBIT;
964
    *buf++ = tag;
965
  }
966

    
967
  return ext;
968
}
969

    
970
static inline int
971
check_ext_lsa(struct top_hash_entry *en, struct fib_node *fn, u32 metric, ip_addr fwaddr, u32 tag)
972
{
973
  struct ospf_lsa_ext *ext = en->lsa_body;
974
  ip_addr prefix;
975
  int pxlen;
976
  u8 pxopts;
977
  u16 rest;
978

    
979
  u32 *buf = lsa_get_ipv6_prefix(ext->rest, &prefix, &pxlen, &pxopts, &rest);
980

    
981
  /* LSAID collision */
982
  if ((fn->pxlen != pxlen) || !ipa_equal(fn->prefix, prefix))
983
    return -1;
984

    
985
  if (en->lsa.sn == LSA_MAXSEQNO)
986
    return 0;
987

    
988
  u32 rt_metric = ext->metric & METRIC_MASK;
989
  ip_addr rt_fwaddr = IPA_NONE;
990
  u32 rt_tag = 0;
991

    
992
  if (ext->metric & LSA_EXT_FBIT)
993
    buf = lsa_get_ipv6_addr(buf, &rt_fwaddr);
994

    
995
  if (ext->metric & LSA_EXT_TBIT)
996
    rt_tag = *buf++;
997

    
998
  return (rt_metric == metric) && ipa_equal(rt_fwaddr, fwaddr) && (rt_tag == tag);
999
}
1000

    
1001

    
1002
#endif
1003

    
1004
static inline ip_addr
1005
find_surrogate_fwaddr(struct ospf_area *oa)
1006
{
1007
  struct proto_ospf *po = oa->po;
1008
  struct ospf_iface *ifa;
1009
  struct ifa *a, *cur_addr = NULL;
1010
  int np, cur_np = 0;
1011

    
1012
  WALK_LIST(ifa, po->iface_list)
1013
  {
1014
    if ((ifa->oa != oa) ||
1015
        (ifa->type == OSPF_IT_VLINK))
1016
      continue;
1017

    
1018
#ifdef OSPFv2
1019
    a = ifa->addr;
1020
    if (a->flags & IA_PEER)
1021
      continue;
1022

    
1023
    np = ((a->flags & IA_HOST) || ifa->stub) ? 2 : 1;
1024
    if (np > cur_np)
1025
    {
1026
      cur_addr = a;
1027
      cur_np = np;
1028
    }
1029

    
1030
#else /* OSPFv3 */
1031
    WALK_LIST(a, ifa->iface->addrs)
1032
    {
1033
      if ((a->flags & IA_SECONDARY) ||
1034
          (a->flags & IA_PEER) ||
1035
          (a->scope <= SCOPE_LINK))
1036
        continue;
1037

    
1038
      np = ((a->flags & IA_HOST) || ifa->stub) ? 2 : 1;
1039
      if (np > cur_np)
1040
      {
1041
        cur_addr = a;
1042
        cur_np = np;
1043
      }
1044
    }
1045
#endif
1046
  }
1047

    
1048
  return cur_addr ? cur_addr->ip : IPA_NONE;
1049
}
1050

    
1051

    
1052
/**
1053
 * originate_ext_lsa - new route received from nest and filters
1054
 * @oa: ospf_area for which LSA is originated
1055
 * @fn: network prefix and mask
1056
 * @src: the source of origination of the LSA (EXT_EXPORT/EXT_NSSA)
1057
 * @metric: the metric of a route
1058
 * @fwaddr: the forwarding address
1059
 * @tag: the route tag
1060
 * @pbit: P-bit for NSSA LSAs, ignored for external LSAs
1061
 *
1062
 * If I receive a message that new route is installed, I try to originate an
1063
 * external LSA. If @oa is an NSSA area, NSSA-LSA is originated instead.
1064
 * @oa should not be a stub area. @src does not specify whether the LSA
1065
 * is external or NSSA, but it specifies the source of origination - 
1066
 * the export from ospf_rt_notify(), or the NSSA-EXT translation.
1067
 *
1068
 * The function also sets flag ebit. If it's the first time, the new router lsa
1069
 * origination is necessary.
1070
 */
1071
void
1072
originate_ext_lsa(struct ospf_area *oa, struct fib_node *fn, int src,
1073
                  u32 metric, ip_addr fwaddr, u32 tag, int pbit)
1074
{
1075
  struct proto_ospf *po = oa->po;
1076
  struct proto *p = &po->proto;
1077
  struct ospf_lsa_header lsa;
1078
  struct top_hash_entry *en = NULL;
1079
  void *body;
1080
  int nssa = oa_is_nssa(oa);
1081
  u32 dom = nssa ? oa->areaid : 0;
1082

    
1083
  OSPF_TRACE(D_EVENTS, "Originating %s-LSA for %I/%d",
1084
             nssa ? "NSSA" : "AS-external", fn->prefix, fn->pxlen);
1085

    
1086
  lsa.age = 0;
1087
#ifdef OSPFv2
1088
  lsa.options = nssa ? (pbit ? OPT_P : 0) : OPT_E;
1089
#endif
1090
  lsa.type = nssa ? LSA_T_NSSA : LSA_T_EXT;
1091
  lsa.id = fibnode_to_lsaid(po, fn);
1092
  lsa.rt = po->router_id;
1093

    
1094
  if (nssa && pbit && ipa_zero(fwaddr))
1095
  {
1096
    /* NSSA-LSA with P-bit set must have non-zero forwarding address */
1097

    
1098
    fwaddr = find_surrogate_fwaddr(oa);
1099
    if (ipa_zero(fwaddr))
1100
    {
1101
      log(L_ERR "%s: Cannot find forwarding address for NSSA-LSA %I/%d",
1102
          p->name, fn->prefix, fn->pxlen);
1103
      return;
1104
    }
1105
  }
1106

    
1107
  if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL)
1108
  {
1109
    int rv = check_ext_lsa(en, fn, metric, fwaddr, tag);
1110
    if (rv < 0)
1111
    {
1112
      log(L_ERR "%s: LSAID collision for %I/%d",
1113
          p->name, fn->prefix, fn->pxlen);
1114
      return;
1115
    }
1116

    
1117
    if (rv > 0)
1118
      return;
1119
  }
1120
  lsa.sn = get_seqnum(en);
1121

    
1122
  body = originate_ext_lsa_body(po, &lsa.length, fn, metric, fwaddr, tag, pbit);
1123
  lsasum_calculate(&lsa, body);
1124

    
1125
  if (src) 
1126
    fn->x1 = src;
1127

    
1128
  lsa_install_new(po, &lsa, dom, body);
1129
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
1130

    
1131
  if (po->ebit == 0)
1132
  {
1133
    po->ebit = 1;
1134
    WALK_LIST(oa, po->area_list)
1135
    {
1136
      schedule_rt_lsa(oa);
1137
    }
1138
  }
1139
}
1140

    
1141
void
1142
flush_ext_lsa(struct ospf_area *oa, struct fib_node *fn, int nssa)
1143
{
1144
  struct proto_ospf *po = oa->po;
1145
  struct proto *p = &po->proto;
1146
  struct top_hash_entry *en;
1147

    
1148
  u32 dom = nssa ? oa->areaid : 0;
1149
  u32 type = nssa ? LSA_T_NSSA : LSA_T_EXT;
1150
  u32 lsaid = fibnode_to_lsaid(po, fn);
1151

    
1152
  if (en = ospf_hash_find(po->gr, dom, lsaid, po->router_id, type))
1153
    {
1154
      OSPF_TRACE(D_EVENTS, "Flushing %s-LSA for %I/%d",
1155
                 nssa ? "NSSA" : "AS-external", fn->prefix, fn->pxlen);
1156

    
1157
      if (check_ext_lsa(en, fn, 0, IPA_NONE, 0) < 0)
1158
        {
1159
          log(L_ERR "%s: LSAID collision for %I/%d",
1160
              p->name, fn->prefix, fn->pxlen);
1161
          return;
1162
        }
1163

    
1164
      fn->x1 = 0;
1165
      ospf_lsupd_flush_nlsa(po, en);
1166
    }
1167
}
1168

    
1169

    
1170
#ifdef OSPFv3
1171

    
1172
static void *
1173
originate_link_lsa_body(struct ospf_iface *ifa, u16 *length)
1174
{
1175
  struct proto_ospf *po = ifa->oa->po;
1176
  struct ospf_lsa_link *ll;
1177
  int i = 0;
1178
  u8 flags;
1179

    
1180
  ASSERT(po->lsab_used == 0);
1181
  ll = lsab_allocz(po, sizeof(struct ospf_lsa_link));
1182
  ll->options = ifa->oa->options | (ifa->priority << 24);
1183
  ll->lladdr = ifa->addr->ip;
1184
  ll = NULL; /* buffer might be reallocated later */
1185

    
1186
  struct ifa *a;
1187
  WALK_LIST(a, ifa->iface->addrs)
1188
    {
1189
      if ((a->flags & IA_SECONDARY) ||
1190
          (a->scope < SCOPE_SITE))
1191
        continue;
1192

    
1193
      flags = (a->pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
1194
      put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(a->pxlen)),
1195
                      a->ip, a->pxlen, flags, 0);
1196
      i++;
1197
    }
1198

    
1199
  ll = po->lsab;
1200
  ll->pxcount = i;
1201
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
1202
  return lsab_flush(po);
1203
}
1204

    
1205
void
1206
originate_link_lsa(struct ospf_iface *ifa)
1207
{
1208
  struct ospf_lsa_header lsa;
1209
  struct proto_ospf *po = ifa->oa->po;
1210
  struct proto *p = &po->proto;
1211
  void *body;
1212

    
1213
  /* Vlinks do not have link-LSAs */
1214
  if (ifa->type == OSPF_IT_VLINK)
1215
    return;
1216

    
1217
  OSPF_TRACE(D_EVENTS, "Originating link-LSA for iface %s", ifa->ifname);
1218

    
1219
  lsa.age = 0;
1220
  lsa.type = LSA_T_LINK;
1221
  lsa.id = ifa->iface_id;
1222
  lsa.rt = po->router_id;
1223
  lsa.sn = get_seqnum(ifa->link_lsa);
1224
  u32 dom = ifa->iface_id;
1225

    
1226
  body = originate_link_lsa_body(ifa, &lsa.length);
1227
  lsasum_calculate(&lsa, body);
1228
  ifa->link_lsa = lsa_install_new(po, &lsa, dom, body);
1229
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
1230

    
1231
  /* Just to be sure to not forget on our link LSA */
1232
  if (ifa->state == OSPF_IS_DR)
1233
    schedule_net_lsa(ifa);
1234
}
1235

    
1236
void
1237
update_link_lsa(struct ospf_iface *ifa)
1238
{
1239
  if (ifa->link_lsa && ((ifa->link_lsa->inst_t + MINLSINTERVAL) > now))
1240
    return;
1241
  /*
1242
   * It's too early to originate new link LSA. We will
1243
   * try to do it next tick
1244
   */
1245
  originate_link_lsa(ifa);
1246
  ifa->origlink = 0;
1247
}
1248

    
1249
static inline void
1250
lsa_put_prefix(struct proto_ospf *po, ip_addr prefix, u32 pxlen, u32 cost)
1251
{
1252
  put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(pxlen)), prefix, pxlen,
1253
                  (pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA, cost);
1254
}
1255

    
1256
static void *
1257
originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length)
1258
{
1259
  struct proto_ospf *po = oa->po;
1260
  struct ospf_config *cf = (struct ospf_config *) (po->proto.cf);
1261
  struct ospf_iface *ifa;
1262
  struct ospf_lsa_prefix *lp;
1263
  int host_addr = 0;
1264
  int net_lsa;
1265
  int i = 0;
1266

    
1267
  ASSERT(po->lsab_used == 0);
1268
  lp = lsab_allocz(po, sizeof(struct ospf_lsa_prefix));
1269
  lp->ref_type = LSA_T_RT;
1270
  lp->ref_id = 0;
1271
  lp->ref_rt = po->router_id;
1272
  lp = NULL; /* buffer might be reallocated later */
1273

    
1274
  WALK_LIST(ifa, po->iface_list)
1275
  {
1276
    if ((ifa->oa != oa) || (ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
1277
      continue;
1278

    
1279
    ifa->px_pos_beg = i;
1280

    
1281
    if ((ifa->type == OSPF_IT_BCAST) ||
1282
        (ifa->type == OSPF_IT_NBMA))
1283
      net_lsa = bcast_net_active(ifa);
1284
    else
1285
      net_lsa = 0;
1286

    
1287
    struct ifa *a;
1288
    WALK_LIST(a, ifa->iface->addrs)
1289
      {
1290
        if ((a->flags & IA_SECONDARY) ||
1291
            (a->flags & IA_PEER) ||
1292
            (a->scope <= SCOPE_LINK))
1293
          continue;
1294

    
1295
        if (((a->pxlen < MAX_PREFIX_LENGTH) && net_lsa) ||
1296
            configured_stubnet(oa, a))
1297
          continue;
1298

    
1299
        if ((a->flags & IA_HOST) ||
1300
            (ifa->state == OSPF_IS_LOOP) ||
1301
            (ifa->type == OSPF_IT_PTMP))
1302
        {
1303
          lsa_put_prefix(po, a->ip, MAX_PREFIX_LENGTH, 0);
1304
          host_addr = 1;
1305
        }
1306
        else
1307
          lsa_put_prefix(po, a->prefix, a->pxlen, ifa->cost);
1308
        i++;
1309
      }
1310

    
1311
    ifa->px_pos_end = i;
1312
  }
1313

    
1314
  struct ospf_stubnet_config *sn;
1315
  if (oa->ac)
1316
    WALK_LIST(sn, oa->ac->stubnet_list)
1317
      if (!sn->hidden)
1318
      {
1319
        lsa_put_prefix(po, sn->px.addr, sn->px.len, sn->cost);
1320
        if (sn->px.len == MAX_PREFIX_LENGTH)
1321
          host_addr = 1;
1322
        i++;
1323
      }
1324

    
1325
  /* If there are some configured vlinks, find some global address
1326
     (even from another area), which will be used as a vlink endpoint. */
1327
  if (!EMPTY_LIST(cf->vlink_list) && !host_addr)
1328
  {
1329
    WALK_LIST(ifa, po->iface_list)
1330
    {
1331
      if ((ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
1332
        continue;
1333

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

    
1340
        /* Found some IP */
1341
        lsa_put_prefix(po, a->ip, MAX_PREFIX_LENGTH, 0);
1342
        i++;
1343
        goto done;
1344
      }
1345
    }
1346
  }
1347

    
1348
 done:
1349
  lp = po->lsab;
1350
  lp->pxcount = i;
1351
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
1352
  return lsab_flush(po);
1353
}
1354

    
1355
void
1356
originate_prefix_rt_lsa(struct ospf_area *oa)
1357
{
1358
  struct proto_ospf *po = oa->po;
1359
  struct proto *p = &po->proto;  
1360
  struct ospf_lsa_header lsa;
1361
  void *body;
1362

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

    
1365
  lsa.age = 0;
1366
  lsa.type = LSA_T_PREFIX;
1367
  lsa.id = 0;
1368
  lsa.rt = po->router_id;
1369
  lsa.sn = get_seqnum(oa->pxr_lsa);
1370
  u32 dom = oa->areaid;
1371

    
1372
  body = originate_prefix_rt_lsa_body(oa, &lsa.length);
1373
  lsasum_calculate(&lsa, body);
1374
  oa->pxr_lsa = lsa_install_new(po, &lsa, dom, body);
1375
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
1376
}
1377

    
1378

    
1379
static inline int
1380
prefix_space(u32 *buf)
1381
{
1382
  int pxl = *buf >> 24;
1383
  return IPV6_PREFIX_SPACE(pxl);
1384
}
1385

    
1386
static inline int
1387
prefix_same(u32 *b1, u32 *b2)
1388
{
1389
  int pxl1 = *b1 >> 24;
1390
  int pxl2 = *b2 >> 24;
1391
  int pxs, i;
1392
  
1393
  if (pxl1 != pxl2)
1394
    return 0;
1395

    
1396
  pxs = IPV6_PREFIX_WORDS(pxl1);
1397
  for (i = 1; i < pxs; i++)
1398
    if (b1[i] != b2[i])
1399
      return 0;
1400

    
1401
  return 1;
1402
}
1403

    
1404
static inline u32 *
1405
prefix_advance(u32 *buf)
1406
{
1407
  int pxl = *buf >> 24;
1408
  return buf + IPV6_PREFIX_WORDS(pxl);
1409
}
1410

    
1411
/* FIXME eliminate items with LA bit set? see 4.4.3.9 */
1412
static void
1413
add_prefix(struct proto_ospf *po, u32 *px, int offset, int *pxc)
1414
{
1415
  u32 *pxl = lsab_offset(po, offset);
1416
  int i;
1417
  for (i = 0; i < *pxc; pxl = prefix_advance(pxl), i++)
1418
    if (prefix_same(px, pxl))
1419
    {
1420
      /* Options should be logically OR'ed together */
1421
      *pxl |= (*px & 0x00FF0000);
1422
      return;
1423
    }
1424

    
1425
  ASSERT(pxl == lsab_end(po));
1426

    
1427
  int pxspace = prefix_space(px);
1428
  pxl = lsab_alloc(po, pxspace);
1429
  memcpy(pxl, px, pxspace);
1430
  *pxl &= 0xFFFF0000;        /* Set metric to zero */
1431
  (*pxc)++;
1432
}
1433

    
1434
static void
1435
add_link_lsa(struct proto_ospf *po, struct top_hash_entry *en, int offset, int *pxc)
1436
{
1437
  struct ospf_lsa_link *ll = en->lsa_body;
1438
  u32 *pxb = ll->rest;
1439
  int j;
1440

    
1441
  for (j = 0; j < ll->pxcount; pxb = prefix_advance(pxb), j++)
1442
  {
1443
    u8 pxlen = (pxb[0] >> 24);
1444
    u8 pxopts = (pxb[0] >> 16);
1445

    
1446
    /* Skip NU or LA prefixes */
1447
    if (pxopts & (OPT_PX_NU | OPT_PX_LA))
1448
      continue;
1449

    
1450
    /* Skip link-local prefixes */
1451
    if ((pxlen >= 10) && ((pxb[1] & 0xffc00000) == 0xfe800000))
1452
      continue;
1453

    
1454
    add_prefix(po, pxb, offset, pxc);
1455
  }
1456
}
1457

    
1458

    
1459

    
1460
static void *
1461
originate_prefix_net_lsa_body(struct ospf_iface *ifa, u16 *length)
1462
{
1463
  struct proto_ospf *po = ifa->oa->po;
1464
  struct ospf_lsa_prefix *lp;
1465
  struct ospf_neighbor *n;
1466
  struct top_hash_entry *en;
1467
  int pxc, offset;
1468

    
1469
  ASSERT(po->lsab_used == 0);
1470
  lp = lsab_allocz(po, sizeof(struct ospf_lsa_prefix));
1471
  lp->ref_type = LSA_T_NET;
1472
  lp->ref_id = ifa->net_lsa->lsa.id;
1473
  lp->ref_rt = po->router_id;
1474
  lp = NULL; /* buffer might be reallocated later */
1475

    
1476
  pxc = 0;
1477
  offset = po->lsab_used;
1478

    
1479
  /* Find all Link LSAs associated with the link and merge their prefixes */
1480
  if (ifa->link_lsa)
1481
    add_link_lsa(po, ifa->link_lsa, offset, &pxc);
1482

    
1483
  WALK_LIST(n, ifa->neigh_list)
1484
    if ((n->state == NEIGHBOR_FULL) &&
1485
              (en = ospf_hash_find(po->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK)))
1486
      add_link_lsa(po, en, offset, &pxc);
1487

    
1488
  lp = po->lsab;
1489
  lp->pxcount = pxc;
1490
  *length = po->lsab_used + sizeof(struct ospf_lsa_header);
1491
  return lsab_flush(po);
1492
}
1493

    
1494
void
1495
originate_prefix_net_lsa(struct ospf_iface *ifa)
1496
{
1497
  struct proto_ospf *po = ifa->oa->po;
1498
  struct proto *p = &po->proto;
1499
  struct ospf_lsa_header lsa;
1500
  void *body;
1501

    
1502
  OSPF_TRACE(D_EVENTS, "Originating network prefix-LSA for iface %s", ifa->ifname);
1503

    
1504
  lsa.age = 0;
1505
  lsa.type = LSA_T_PREFIX;
1506
  lsa.id = ifa->iface_id;
1507
  lsa.rt = po->router_id;
1508
  lsa.sn = get_seqnum(ifa->pxn_lsa);
1509
  u32 dom = ifa->oa->areaid;
1510

    
1511
  body = originate_prefix_net_lsa_body(ifa, &lsa.length);
1512
  lsasum_calculate(&lsa, body);
1513
  ifa->pxn_lsa = lsa_install_new(po, &lsa, dom, body);
1514
  ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1);
1515
}
1516

    
1517
void
1518
flush_prefix_net_lsa(struct ospf_iface *ifa)
1519
{
1520
  struct proto_ospf *po = ifa->oa->po;
1521
  struct proto *p = &po->proto;
1522
  struct top_hash_entry *en = ifa->pxn_lsa;
1523
  u32 dom = ifa->oa->areaid;
1524

    
1525
  if (en == NULL)
1526
    return;
1527

    
1528
  OSPF_TRACE(D_EVENTS, "Flushing network prefix-LSA for iface %s", ifa->ifname);
1529

    
1530
  en->lsa.sn += 1;
1531
  en->lsa.age = LSA_MAXAGE;
1532
  lsasum_calculate(&en->lsa, en->lsa_body);
1533
  ospf_lsupd_flood(po, NULL, NULL, &en->lsa, dom, 0);
1534
  flush_lsa(en, po);
1535
  ifa->pxn_lsa = NULL;
1536
}
1537

    
1538

    
1539
#endif
1540

    
1541

    
1542
static void
1543
ospf_top_ht_alloc(struct top_graph *f)
1544
{
1545
  f->hash_size = 1 << f->hash_order;
1546
  f->hash_mask = f->hash_size - 1;
1547
  if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
1548
    f->hash_entries_max = ~0;
1549
  else
1550
    f->hash_entries_max = f->hash_size HASH_HI_MARK;
1551
  if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
1552
    f->hash_entries_min = 0;
1553
  else
1554
    f->hash_entries_min = f->hash_size HASH_LO_MARK;
1555
  DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
1556
      f->hash_order, f->hash_size, f->hash_entries_min, f->hash_entries_max);
1557
  f->hash_table =
1558
    mb_alloc(f->pool, f->hash_size * sizeof(struct top_hash_entry *));
1559
  bzero(f->hash_table, f->hash_size * sizeof(struct top_hash_entry *));
1560
}
1561

    
1562
static inline void
1563
ospf_top_ht_free(struct top_hash_entry **h)
1564
{
1565
  mb_free(h);
1566
}
1567

    
1568
static inline u32
1569
ospf_top_hash_u32(u32 a)
1570
{
1571
  /* Shamelessly stolen from IP address hashing in ipv4.h */
1572
  a ^= a >> 16;
1573
  a ^= a << 10;
1574
  return a;
1575
}
1576

    
1577
static inline unsigned
1578
ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type)
1579
{
1580
  /* In OSPFv2, we don't know Router ID when looking for network LSAs.
1581
     In OSPFv3, we don't know LSA ID when looking for router LSAs.
1582
     In both cases, there is (usually) just one (or small number)
1583
     appropriate LSA, so we just clear unknown part of key. */
1584

    
1585
  return (
1586
#ifdef OSPFv2
1587
          ((type == LSA_T_NET) ? 0 : ospf_top_hash_u32(rtrid)) +
1588
          ospf_top_hash_u32(lsaid) + 
1589
#else /* OSPFv3 */
1590
          ospf_top_hash_u32(rtrid) +
1591
          ((type == LSA_T_RT) ? 0 : ospf_top_hash_u32(lsaid)) +
1592
#endif
1593
          type + domain) & f->hash_mask;
1594

    
1595
  /*
1596
  return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
1597
          type + areaid) & f->hash_mask;
1598
  */
1599
}
1600

    
1601
/**
1602
 * ospf_top_new - allocated new topology database
1603
 * @p: current instance of ospf
1604
 *
1605
 * this dynamically hashed structure is often used for keeping lsas. mainly
1606
 * its used in @ospf_area structure.
1607
 */
1608
struct top_graph *
1609
ospf_top_new(pool *pool)
1610
{
1611
  struct top_graph *f;
1612

    
1613
  f = mb_allocz(pool, sizeof(struct top_graph));
1614
  f->pool = pool;
1615
  f->hash_slab = sl_new(f->pool, sizeof(struct top_hash_entry));
1616
  f->hash_order = HASH_DEF_ORDER;
1617
  ospf_top_ht_alloc(f);
1618
  f->hash_entries = 0;
1619
  f->hash_entries_min = 0;
1620
  return f;
1621
}
1622

    
1623
void
1624
ospf_top_free(struct top_graph *f)
1625
{
1626
  rfree(f->hash_slab);
1627
  ospf_top_ht_free(f->hash_table);
1628
  mb_free(f);
1629
}
1630

    
1631
static void
1632
ospf_top_rehash(struct top_graph *f, int step)
1633
{
1634
  unsigned int oldn, oldh;
1635
  struct top_hash_entry **n, **oldt, **newt, *e, *x;
1636

    
1637
  oldn = f->hash_size;
1638
  oldt = f->hash_table;
1639
  DBG("re-hashing topology hash from order %d to %d\n", f->hash_order,
1640
      f->hash_order + step);
1641
  f->hash_order += step;
1642
  ospf_top_ht_alloc(f);
1643
  newt = f->hash_table;
1644

    
1645
  for (oldh = 0; oldh < oldn; oldh++)
1646
  {
1647
    e = oldt[oldh];
1648
    while (e)
1649
    {
1650
      x = e->next;
1651
      n = newt + ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa.type);
1652
      e->next = *n;
1653
      *n = e;
1654
      e = x;
1655
    }
1656
  }
1657
  ospf_top_ht_free(oldt);
1658
}
1659

    
1660
#ifdef OSPFv2
1661

    
1662
u32
1663
ospf_lsa_domain(u32 type, struct ospf_iface *ifa)
1664
{
1665
  return (type == LSA_T_EXT) ? 0 : ifa->oa->areaid;
1666
}
1667

    
1668
#else /* OSPFv3 */
1669

    
1670
u32
1671
ospf_lsa_domain(u32 type, struct ospf_iface *ifa)
1672
{
1673
  switch (type & LSA_SCOPE_MASK)
1674
    {
1675
    case LSA_SCOPE_LINK:
1676
      return ifa->iface_id;
1677

    
1678
    case LSA_SCOPE_AREA:
1679
      return ifa->oa->areaid;
1680

    
1681
    case LSA_SCOPE_AS:
1682
    default:
1683
      return 0;
1684
    }
1685
}
1686

    
1687
#endif
1688

    
1689
struct top_hash_entry *
1690
ospf_hash_find_header(struct top_graph *f, u32 domain, struct ospf_lsa_header *h)
1691
{
1692
  return ospf_hash_find(f, domain, h->id, h->rt, h->type);
1693
}
1694

    
1695
struct top_hash_entry *
1696
ospf_hash_get_header(struct top_graph *f, u32 domain, struct ospf_lsa_header *h)
1697
{
1698
  return ospf_hash_get(f, domain, h->id, h->rt, h->type);
1699
}
1700

    
1701
struct top_hash_entry *
1702
ospf_hash_find(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1703
{
1704
  struct top_hash_entry *e;
1705
  e = f->hash_table[ospf_top_hash(f, domain, lsa, rtr, type)];
1706

    
1707
  while (e && (e->lsa.id != lsa || e->lsa.type != type || e->lsa.rt != rtr || e->domain != domain))
1708
    e = e->next;
1709

    
1710
  return e;
1711
}
1712

    
1713

    
1714
#ifdef OSPFv2
1715

    
1716
/* In OSPFv2, sometimes we don't know Router ID when looking for network LSAs.
1717
   There should be just one, so we find any match. */
1718
struct top_hash_entry *
1719
ospf_hash_find_net(struct top_graph *f, u32 domain, u32 lsa)
1720
{
1721
  struct top_hash_entry *e;
1722
  e = f->hash_table[ospf_top_hash(f, domain, lsa, 0, LSA_T_NET)];
1723

    
1724
  while (e && (e->lsa.id != lsa || e->lsa.type != LSA_T_NET || e->domain != domain))
1725
    e = e->next;
1726

    
1727
  return e;
1728
}
1729

    
1730
#endif
1731

    
1732

    
1733
#ifdef OSPFv3
1734

    
1735
/* In OSPFv3, usually we don't know LSA ID when looking for router
1736
   LSAs. We return matching LSA with smallest LSA ID. */
1737
struct top_hash_entry *
1738
ospf_hash_find_rt(struct top_graph *f, u32 domain, u32 rtr)
1739
{
1740
  struct top_hash_entry *rv = NULL;
1741
  struct top_hash_entry *e;
1742
  e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)];
1743
  
1744
  while (e)
1745
    {
1746
      if (e->lsa.rt == rtr && e->lsa.type == LSA_T_RT && e->domain == domain)
1747
        if (!rv || e->lsa.id < rv->lsa.id)
1748
          rv = e;
1749
      e = e->next;
1750
    }
1751

    
1752
  return rv;
1753
}
1754

    
1755
static inline struct top_hash_entry *
1756
find_matching_rt(struct top_hash_entry *e, u32 domain, u32 rtr)
1757
{
1758
  while (e && (e->lsa.rt != rtr || e->lsa.type != LSA_T_RT || e->domain != domain))
1759
    e = e->next;
1760
  return e;
1761
}
1762

    
1763
struct top_hash_entry *
1764
ospf_hash_find_rt_first(struct top_graph *f, u32 domain, u32 rtr)
1765
{
1766
  struct top_hash_entry *e;
1767
  e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)];
1768
  return find_matching_rt(e, domain, rtr);
1769
}
1770

    
1771
struct top_hash_entry *
1772
ospf_hash_find_rt_next(struct top_hash_entry *e)
1773
{
1774
  return find_matching_rt(e->next, e->domain, e->lsa.rt);
1775
}
1776

    
1777
#endif
1778

    
1779

    
1780
struct top_hash_entry *
1781
ospf_hash_get(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
1782
{
1783
  struct top_hash_entry **ee;
1784
  struct top_hash_entry *e;
1785

    
1786
  ee = f->hash_table + ospf_top_hash(f, domain, lsa, rtr, type);
1787
  e = *ee;
1788

    
1789
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type || e->domain != domain))
1790
    e = e->next;
1791

    
1792
  if (e)
1793
    return e;
1794

    
1795
  e = sl_alloc(f->hash_slab);
1796
  e->color = OUTSPF;
1797
  e->dist = LSINFINITY;
1798
  e->nhs = NULL;
1799
  e->lb = IPA_NONE;
1800
  e->lsa.id = lsa;
1801
  e->lsa.rt = rtr;
1802
  e->lsa.type = type;
1803
  e->lsa_body = NULL;
1804
  e->domain = domain;
1805
  e->next = *ee;
1806
  *ee = e;
1807
  if (f->hash_entries++ > f->hash_entries_max)
1808
    ospf_top_rehash(f, HASH_HI_STEP);
1809
  return e;
1810
}
1811

    
1812
void
1813
ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
1814
{
1815
  struct top_hash_entry **ee = f->hash_table + 
1816
    ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa.type);
1817

    
1818
  while (*ee)
1819
  {
1820
    if (*ee == e)
1821
    {
1822
      *ee = e->next;
1823
      sl_free(f->hash_slab, e);
1824
      if (f->hash_entries-- < f->hash_entries_min)
1825
        ospf_top_rehash(f, -HASH_LO_STEP);
1826
      return;
1827
    }
1828
    ee = &((*ee)->next);
1829
  }
1830
  bug("ospf_hash_delete() called for invalid node");
1831
}
1832

    
1833
/*
1834
static void
1835
ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
1836
{
1837

1838
  struct ospf_lsa_rt *rt = NULL;
1839
  struct ospf_lsa_rt_link *rr = NULL;
1840
  struct ospf_lsa_net *ln = NULL;
1841
  u32 *rts = NULL;
1842
  u32 i, max;
1843

1844
  OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
1845
             he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
1846
             he->lsa.checksum, he->domain);
1847

1848

1849
  switch (he->lsa.type)
1850
    {
1851
    case LSA_T_RT:
1852
      rt = he->lsa_body;
1853
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
1854

1855
      for (i = 0; i < lsa_rt_items(&he->lsa); i++)
1856
        OSPF_TRACE(D_EVENTS, "  - %1x %-1R %-1R %5u",
1857
                   rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
1858
      break;
1859

1860
    case LSA_T_NET:
1861
      ln = he->lsa_body;
1862
      rts = (u32 *) (ln + 1);
1863

1864
      for (i = 0; i < lsa_net_items(&he->lsa); i++)
1865
        OSPF_TRACE(D_EVENTS, "  - %-1R", rts[i]);
1866
      break;
1867

1868
    default:
1869
      break;
1870
    }
1871
}
1872

1873
void
1874
ospf_top_dump(struct top_graph *f, struct proto *p)
1875
{
1876
  unsigned int i;
1877
  OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
1878

1879
  for (i = 0; i < f->hash_size; i++)
1880
  {
1881
    struct top_hash_entry *e;
1882
    for (e = f->hash_table[i]; e != NULL; e = e->next)
1883
      ospf_dump_lsa(e, p);
1884
  }
1885
}
1886
*/
1887

    
1888
/* This is very inefficient, please don't call it often */
1889

    
1890
/* I should also test for every LSA if it's in some link state
1891
 * retransmission list for every neighbor. I will not test it.
1892
 * It could happen that I'll receive some strange ls ack's.
1893
 */
1894

    
1895
int
1896
can_flush_lsa(struct proto_ospf *po)
1897
{
1898
  struct ospf_iface *ifa;
1899
  struct ospf_neighbor *n;
1900

    
1901
  WALK_LIST(ifa, po->iface_list)
1902
  {
1903
    WALK_LIST(n, ifa->neigh_list)
1904
    {
1905
      if ((n->state == NEIGHBOR_EXCHANGE) || (n->state == NEIGHBOR_LOADING))
1906
        return 0;
1907

    
1908
      break;
1909
    }
1910
  }
1911

    
1912
  return 1;
1913
}