Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / rt.c @ 62e64905

History | View | Annotate | Download (47.2 KB)

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

    
11
#include "ospf.h"
12

    
13
static void add_cand(list * l, struct top_hash_entry *en,
14
                     struct top_hash_entry *par, u32 dist,
15
                     struct ospf_area *oa, int i);
16
static void rt_sync(struct ospf_proto *p);
17

    
18

    
19
static inline void reset_ri(ort *ort)
20
{
21
  bzero(&ort->n, sizeof(orta));
22
}
23

    
24
static inline int
25
nh_is_vlink(struct nexthop *nhs)
26
{
27
  return !nhs->iface;
28
}
29

    
30
static inline int
31
unresolved_vlink(ort *ort)
32
{
33
  return ort->n.nhs && nh_is_vlink(ort->n.nhs);
34
}
35

    
36
static inline struct nexthop *
37
new_nexthop(struct ospf_proto *p, ip_addr gw, struct iface *iface, byte weight)
38
{
39
  struct nexthop *nh = lp_allocz(p->nhpool, sizeof(struct nexthop));
40
  nh->gw = gw;
41
  nh->iface = iface;
42
  nh->weight = weight;
43
  return nh;
44
}
45

    
46
/* Returns true if there are device nexthops in n */
47
static inline int
48
has_device_nexthops(const struct nexthop *n)
49
{
50
  for (; n; n = n->next)
51
    if (ipa_zero(n->gw))
52
      return 1;
53

    
54
  return 0;
55
}
56

    
57
/* Replace device nexthops with nexthops to gw */
58
static struct nexthop *
59
fix_device_nexthops(struct ospf_proto *p, const struct nexthop *n, ip_addr gw)
60
{
61
  struct nexthop *root1 = NULL;
62
  struct nexthop *root2 = NULL;
63
  struct nexthop **nn1 = &root1;
64
  struct nexthop **nn2 = &root2;
65

    
66
  if (!p->ecmp)
67
    return new_nexthop(p, gw, n->iface, n->weight);
68

    
69
  /* This is a bit tricky. We cannot just copy the list and update n->gw,
70
     because the list should stay sorted, so we create two lists, one with new
71
     gateways and one with old ones, and then merge them. */
72

    
73
  for (; n; n = n->next)
74
  {
75
    struct nexthop *nn = new_nexthop(p, ipa_zero(n->gw) ? gw : n->gw, n->iface, n->weight);
76

    
77
    if (ipa_zero(n->gw))
78
    {
79
      *nn1 = nn;
80
      nn1 = &(nn->next);
81
    }
82
    else
83
    {
84
      *nn2 = nn;
85
      nn2 = &(nn->next);
86
    }
87
  }
88

    
89
  return nexthop_merge(root1, root2, 1, 1, p->ecmp, p->nhpool);
90
}
91

    
92

    
93
/* Whether the ASBR or the forward address destination is preferred
94
   in AS external route selection according to 16.4.1. */
95
static inline int
96
epath_preferred(const orta *ep)
97
{
98
  return (ep->type == RTS_OSPF) && (ep->oa->areaid != 0);
99
}
100

    
101
/* Whether the ext route has ASBR/next_hop marked as preferred. */
102
static inline int
103
orta_pref(const orta *nf)
104
{
105
  return !!(nf->options & ORTA_PREF);
106
}
107

    
108
/* Classify orta entries according to RFC 3101 2.5 (6e) priorities:
109
   Type-7 LSA with P-bit, Type-5 LSA, Type-7 LSA without P-bit */
110
static int
111
orta_prio(const orta *nf)
112
{
113
  /* RFC 3103 2.5 (6e) priorities */
114
  u32 opts = nf->options & (ORTA_NSSA | ORTA_PROP);
115

    
116
  /* A Type-7 LSA with the P-bit set */
117
  if (opts == (ORTA_NSSA | ORTA_PROP))
118
    return 2;
119

    
120
  /* A Type-5 LSA */
121
  if (opts == 0)
122
    return 1;
123

    
124
  return 0;
125
}
126

    
127
/* Whether the route is better according to RFC 3101 2.5 (6e):
128
   Prioritize Type-7 LSA with P-bit, then Type-5 LSA, then higher router ID */
129
static int
130
orta_prefer_lsa(const orta *new, const orta *old)
131
{
132
  int pn = orta_prio(new);
133
  int po = orta_prio(old);
134

    
135
  return (pn > po) || ((pn == po) && (new->en->lsa.rt > old->en->lsa.rt));
136
}
137

    
138
/*
139
 * Compare an existing routing table entry with a new one. Applicable for
140
 * intra-area routes, inter-area routes and router entries. Returns integer
141
 * <, = or > than 0 if the new orta is less, equal or more preferred than
142
 * the old orta.
143
 */
144
static int
145
orta_compare(const struct ospf_proto *p, const orta *new, const orta *old)
146
{
147
  int r;
148

    
149
  if (old->type == RTS_DUMMY)
150
    return 1;
151

    
152
  /* Prefer intra-area to inter-area to externals */
153
  r = ((int) old->type) - ((int) new->type);
154
  if (r) return r;
155

    
156
  /* Prefer lowest type 1 metric */
157
  r = ((int) old->metric1) - ((int) new->metric1);
158
  if (r) return r;
159

    
160

    
161
  /* Rest is BIRD-specific */
162

    
163
  /* Area-wide routes should not mix next-hops from different areas.
164
     This generally should not happen unless there is some misconfiguration. */
165
  if (new->oa->areaid != old->oa->areaid)
166
    return (new->oa->areaid > old->oa->areaid) ? 1 : -1;
167

    
168
  /* Prefer routes for configured stubnets (!nhs) to regular routes to dummy
169
     vlink nexthops. We intentionally return -1 if both are stubnets or vlinks. */
170
  if (!old->nhs)
171
    return -1;
172
  if (!new->nhs)
173
    return 1;
174
  if (nh_is_vlink(new->nhs))
175
    return -1;
176
  if (nh_is_vlink(old->nhs))
177
    return 1;
178

    
179

    
180
  if (p->ecmp)
181
    return 0;
182

    
183
  /* Prefer routes with higher Router ID, just to be more deterministic */
184
  if (new->rid > old->rid)
185
    return 1;
186

    
187
  return -1;
188
}
189

    
190
/*
191
 * Compare ASBR routing table entry with a new one, used for precompute ASBRs
192
 * for AS external route selection (RFC 2328 16.4 (3)), Returns integer < or >
193
 * than 0 if the new ASBR is less or more preferred than the old ASBR.
194
 */
195
static int
196
orta_compare_asbr(const struct ospf_proto *p, const orta *new, const orta *old)
197
{
198
  int r;
199

    
200
  if (old->type == RTS_DUMMY)
201
    return 1;
202

    
203
  if (!p->rfc1583)
204
  {
205
    r = epath_preferred(new) - epath_preferred(old);
206
    if (r) return r;
207
  }
208

    
209
  r = ((int) old->metric1) - ((int) new->metric1);
210
  if (r) return r;
211

    
212
  /* Larger area ID is preferred */
213
  if (new->oa->areaid > old->oa->areaid)
214
    return 1;
215

    
216
  /* There is just one ASBR of that RID per area, so tie is not possible */
217
  return -1;
218
}
219

    
220
/*
221
 * Compare a routing table entry with a new one, for AS external routes
222
 * (RFC 2328 16.4) and NSSA routes (RFC 3103 2.5), Returns integer <, = or >
223
 * than 0 if the new orta is less, equal or more preferred than the old orta.
224
 */
225
static int
226
orta_compare_ext(const struct ospf_proto *p, const orta *new, const orta *old)
227
{
228
  int r;
229

    
230
  if (old->type == RTS_DUMMY)
231
    return 1;
232

    
233
  /* 16.4 (6a) - prefer routes with lower type */
234
  r = ((int) old->type) - ((int) new->type);
235
  if (r) return r;
236

    
237
  /* 16.4 (6b) - prefer routes with lower type 2 metric */
238
  if (new->type == RTS_OSPF_EXT2)
239
  {
240
    r = ((int) old->metric2) - ((int) new->metric2);
241
    if (r) return r;
242
  }
243

    
244
  /* 16.4 (6c) - if not RFC1583, prefer routes with preferred ASBR/next_hop */
245
  if (!p->rfc1583)
246
  {
247
    r = orta_pref(new) - orta_pref(old);
248
    if (r) return r;
249
  }
250

    
251
  /* 16.4 (6d) - prefer routes with lower type 1 metric */
252
  r = ((int) old->metric1) - ((int) new->metric1);
253
  if (r) return r;
254

    
255

    
256
  if (p->ecmp && p->merge_external)
257
    return 0;
258

    
259
  /*
260
   * RFC 3101 2.5 (6e) - prioritize Type-7 LSA with P-bit, then Type-5 LSA, then
261
   * LSA with higher router ID. Although this should apply just to functionally
262
   * equivalent LSAs (i.e. ones with the same non-zero forwarding address), we
263
   * use it also to disambiguate otherwise equally preferred nexthops.
264
   */
265
  if (orta_prefer_lsa(new, old))
266
    return 1;
267

    
268
  return -1;
269
}
270

    
271

    
272
static inline void
273
ort_replace(ort *o, const orta *new)
274
{
275
  memcpy(&o->n, new, sizeof(orta));
276
}
277

    
278
static void
279
ort_merge(struct ospf_proto *p, ort *o, const orta *new)
280
{
281
  orta *old = &o->n;
282

    
283
  if (old->nhs != new->nhs)
284
  {
285
    old->nhs = nexthop_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
286
                          p->ecmp, p->nhpool);
287
    old->nhs_reuse = 1;
288
  }
289

    
290
  if (old->rid < new->rid)
291
    old->rid = new->rid;
292
}
293

    
294
static void
295
ort_merge_ext(struct ospf_proto *p, ort *o, const orta *new)
296
{
297
  orta *old = &o->n;
298

    
299
  if (old->nhs != new->nhs)
300
  {
301
    old->nhs = nexthop_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
302
                          p->ecmp, p->nhpool);
303
    old->nhs_reuse = 1;
304
  }
305

    
306
  if (old->tag != new->tag)
307
    old->tag = 0;
308

    
309
  /*
310
   * Even with multipath, we store only one LSA in orta.en for the purpose of
311
   * NSSA/ext translation. Therefore, we apply procedures from RFC 3101 2.5 (6e)
312
   * to all chosen LSAs for given network, not just to functionally equivalent
313
   * ones (i.e. ones with the same non-zero forwarding address).
314
   */
315
  if (orta_prefer_lsa(new, old))
316
  {
317
    old->options = new->options;
318
    old->rid = new->rid;
319
    old->oa = new->oa;
320
    old->en = new->en;
321
  }
322
}
323

    
324

    
325

    
326
static inline void
327
ri_install_net(struct ospf_proto *p, net_addr *net, const orta *new)
328
{
329
  ort *old = fib_get(&p->rtf, net);
330
  int cmp = orta_compare(p, new, &old->n);
331

    
332
  if (cmp > 0)
333
    ort_replace(old, new);
334
  else if (cmp == 0)
335
    ort_merge(p, old, new);
336
}
337

    
338
static inline void
339
ri_install_rt(struct ospf_area *oa, u32 rid, const orta *new)
340
{
341
  net_addr_ip4 nrid = net_from_rid(rid);
342
  ort *old = fib_get(&oa->rtr, (net_addr *) &nrid);
343
  int cmp = orta_compare(oa->po, new, &old->n);
344

    
345
  if (cmp > 0)
346
    ort_replace(old, new);
347
  else if (cmp == 0)
348
    ort_merge(oa->po, old, new);
349
}
350

    
351
static inline void
352
ri_install_asbr(struct ospf_proto *p, u32 rid, const orta *new)
353
{
354
  net_addr_ip4 nrid = net_from_rid(rid);
355
  ort *old = fib_get(&p->backbone->rtr, (net_addr *) &nrid);
356

    
357
  if (orta_compare_asbr(p, new, &old->n) > 0)
358
    ort_replace(old, new);
359
}
360

    
361
static inline void
362
ri_install_ext(struct ospf_proto *p, net_addr *net, const orta *new)
363
{
364
  ort *old = fib_get(&p->rtf, net);
365
  int cmp = orta_compare_ext(p, new, &old->n);
366

    
367
  if (cmp > 0)
368
    ort_replace(old, new);
369
  else if (cmp == 0)
370
    ort_merge_ext(p, old, new);
371
}
372

    
373
static inline struct ospf_iface *
374
rt_pos_to_ifa(struct ospf_area *oa, int pos)
375
{
376
  struct ospf_iface *ifa;
377

    
378
  WALK_LIST(ifa, oa->po->iface_list)
379
    if (ifa->oa == oa && pos >= ifa->rt_pos_beg && pos < ifa->rt_pos_end)
380
      return ifa;
381

    
382
  return NULL;
383
}
384

    
385
static inline struct ospf_iface *
386
px_pos_to_ifa(struct ospf_area *oa, int pos)
387
{
388
  struct ospf_iface *ifa;
389

    
390
  WALK_LIST(ifa, oa->po->iface_list)
391
    if (ifa->oa == oa && pos >= ifa->px_pos_beg && pos < ifa->px_pos_end)
392
      return ifa;
393

    
394
  return NULL;
395
}
396

    
397

    
398
static void
399
add_network(struct ospf_area *oa, net_addr *net, int metric, struct top_hash_entry *en, int pos)
400
{
401
  struct ospf_proto *p = oa->po;
402

    
403
  orta nf = {
404
    .type = RTS_OSPF,
405
    .options = 0,
406
    .metric1 = metric,
407
    .metric2 = LSINFINITY,
408
    .tag = 0,
409
    .rid = en->lsa.rt,
410
    .oa = oa,
411
    .nhs = en->nhs
412
  };
413

    
414
  if (!ospf_valid_prefix(net))
415
  {
416
    log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
417
        p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
418
    return;
419
  }
420

    
421
  if (en == oa->rt)
422
  {
423
    /*
424
     * Local stub networks does not have proper iface in en->nhi
425
     * (because they all have common top_hash_entry en).
426
     * We have to find iface responsible for that stub network.
427
     * Configured stubnets does not have any iface. They will
428
     * be removed in rt_sync().
429
     */
430

    
431
    struct ospf_iface *ifa;
432
    ifa = ospf_is_v2(p) ? rt_pos_to_ifa(oa, pos) : px_pos_to_ifa(oa, pos);
433
    nf.nhs = ifa ? new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight) : NULL;
434
  }
435

    
436
  ri_install_net(p, net, &nf);
437
}
438

    
439

    
440

    
441
static inline void
442
spfa_process_rt(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
443
{
444
  struct ospf_lsa_rt *rt = act->lsa_body;
445
  struct ospf_lsa_rt_walk rtl;
446
  struct top_hash_entry *tmp;
447
  int i;
448

    
449
  if (rt->options & OPT_RT_V)
450
    oa->trcap = 1;
451

    
452
  /*
453
   * In OSPFv3, all routers are added to per-area routing
454
   * tables. But we use it just for ASBRs and ABRs. For the
455
   * purpose of the last step in SPF - prefix-LSA processing in
456
   * spfa_process_prefixes(), we use information stored in LSA db.
457
   */
458
  if (((rt->options & OPT_RT_E) || (rt->options & OPT_RT_B))
459
      && (act->lsa.rt != p->router_id))
460
  {
461
    orta nf = {
462
      .type = RTS_OSPF,
463
      .options = rt->options,
464
      .metric1 = act->dist,
465
      .metric2 = LSINFINITY,
466
      .tag = 0,
467
      .rid = act->lsa.rt,
468
      .oa = oa,
469
      .nhs = act->nhs
470
    };
471
    ri_install_rt(oa, act->lsa.rt, &nf);
472
  }
473

    
474
  /* Errata 2078 to RFC 5340 4.8.1 - skip links from non-routing nodes */
475
  if (ospf_is_v3(p) && (act != oa->rt) && !(rt->options & OPT_R))
476
    return;
477

    
478
  /* Now process Rt links */
479
  for (lsa_walk_rt_init(p, act, &rtl), i = 0; lsa_walk_rt(&rtl); i++)
480
  {
481
    tmp = NULL;
482

    
483
    switch (rtl.type)
484
    {
485
    case LSART_STUB:
486

    
487
      /* Should not happen, LSART_STUB is not defined in OSPFv3 */
488
      if (ospf_is_v3(p))
489
        break;
490

    
491
      /*
492
       * RFC 2328 in 16.1. (2a) says to handle stub networks in an
493
       * second phase after the SPF for an area is calculated. We get
494
       * the same result by handing them here because add_network()
495
       * will keep the best (not the first) found route.
496
       */
497
      net_addr_ip4 net =
498
        NET_ADDR_IP4(ip4_from_u32(rtl.id & rtl.data), u32_masklen(rtl.data));
499

    
500
      add_network(oa, (net_addr *) &net, act->dist + rtl.metric, act, i);
501
      break;
502

    
503
    case LSART_NET:
504
      tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
505
      break;
506

    
507
    case LSART_VLNK:
508
    case LSART_PTP:
509
      tmp = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
510
      break;
511
    }
512

    
513
    add_cand(&oa->cand, tmp, act, act->dist + rtl.metric, oa, i);
514
  }
515
}
516

    
517
static inline void
518
spfa_process_net(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
519
{
520
  struct ospf_lsa_net *ln = act->lsa_body;
521
  struct top_hash_entry *tmp;
522
  int i, cnt;
523

    
524
  if (ospf_is_v2(p))
525
  {
526
    net_addr_ip4 net =
527
      NET_ADDR_IP4(ip4_from_u32(act->lsa.id & ln->optx), u32_masklen(ln->optx));
528

    
529
    add_network(oa, (net_addr *) &net, act->dist, act, -1);
530
  }
531

    
532
  cnt = lsa_net_count(&act->lsa);
533
  for (i = 0; i < cnt; i++)
534
  {
535
    tmp = ospf_hash_find_rt(p->gr, oa->areaid, ln->routers[i]);
536
    add_cand(&oa->cand, tmp, act, act->dist, oa, -1);
537
  }
538
}
539

    
540
static inline void
541
spfa_process_prefixes(struct ospf_proto *p, struct ospf_area *oa)
542
{
543
  struct top_hash_entry *en, *src;
544
  struct ospf_lsa_prefix *px;
545
  u32 *buf;
546
  int i;
547

    
548
  WALK_SLIST(en, p->lsal)
549
  {
550
    if (en->lsa_type != LSA_T_PREFIX)
551
      continue;
552

    
553
    if (en->domain != oa->areaid)
554
      continue;
555

    
556
    if (en->lsa.age == LSA_MAXAGE)
557
      continue;
558

    
559
    px = en->lsa_body;
560

    
561
    /* For router prefix-LSA, we would like to find the first router-LSA */
562
    if (px->ref_type == LSA_T_RT)
563
      src = ospf_hash_find_rt(p->gr, oa->areaid, px->ref_rt);
564
    else
565
      src = ospf_hash_find(p->gr, oa->areaid, px->ref_id, px->ref_rt, px->ref_type);
566

    
567
    if (!src)
568
      continue;
569

    
570
    /* Reachable in SPF */
571
    if (src->color != INSPF)
572
      continue;
573

    
574
    if ((src->lsa_type != LSA_T_RT) && (src->lsa_type != LSA_T_NET))
575
      continue;
576

    
577
    buf = px->rest;
578
    for (i = 0; i < px->pxcount; i++)
579
    {
580
      net_addr_ip6 net;
581
      u8 pxopts;
582
      u16 metric;
583

    
584
      buf = ospf_get_ipv6_prefix(buf, (net_addr *) &net, &pxopts, &metric);
585

    
586
      if (pxopts & OPT_PX_NU)
587
        continue;
588

    
589
      /* Store the first global address to use it later as a vlink endpoint */
590
      if ((pxopts & OPT_PX_LA) && ipa_zero(src->lb))
591
        src->lb = ipa_from_ip6(net.prefix);
592

    
593
      add_network(oa, (net_addr *) &net, src->dist + metric, src, i);
594
    }
595
  }
596
}
597

    
598
/* RFC 2328 16.1. calculating shortest paths for an area */
599
static void
600
ospf_rt_spfa(struct ospf_area *oa)
601
{
602
  struct ospf_proto *p = oa->po;
603
  struct top_hash_entry *act;
604
  node *n;
605

    
606
  if (oa->rt == NULL)
607
    return;
608
  if (oa->rt->lsa.age == LSA_MAXAGE)
609
    return;
610

    
611
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for area %R", oa->areaid);
612

    
613
  /* 16.1. (1) */
614
  init_list(&oa->cand);                /* Empty list of candidates */
615
  oa->trcap = 0;
616

    
617
  DBG("LSA db prepared, adding me into candidate list.\n");
618

    
619
  oa->rt->dist = 0;
620
  oa->rt->color = CANDIDATE;
621
  add_head(&oa->cand, &oa->rt->cn);
622
  DBG("RT LSA: rt: %R, id: %R, type: %u\n",
623
      oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa_type);
624

    
625
  while (!EMPTY_LIST(oa->cand))
626
  {
627
    n = HEAD(oa->cand);
628
    act = SKIP_BACK(struct top_hash_entry, cn, n);
629
    rem_node(n);
630

    
631
    DBG("Working on LSA: rt: %R, id: %R, type: %u\n",
632
        act->lsa.rt, act->lsa.id, act->lsa_type);
633

    
634
    act->color = INSPF;
635
    switch (act->lsa_type)
636
    {
637
    case LSA_T_RT:
638
      spfa_process_rt(p, oa, act);
639
      break;
640

    
641
    case LSA_T_NET:
642
      spfa_process_net(p, oa, act);
643
      break;
644

    
645
    default:
646
      log(L_WARN "%s: Unknown LSA type in SPF: %d", p->p.name, act->lsa_type);
647
    }
648
  }
649

    
650
  if (ospf_is_v3(p))
651
    spfa_process_prefixes(p, oa);
652
}
653

    
654
static int
655
link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par)
656
{
657
  struct ospf_proto *p = oa->po;
658
  struct ospf_lsa_rt_walk rtl;
659
  struct top_hash_entry *tmp;
660
  struct ospf_lsa_net *ln;
661
  u32 i, cnt;
662

    
663
  if (!en || !par) return 0;
664

    
665
  /* We should check whether there is a link back from en to par,
666
     this is used in SPF calc (RFC 2328 16.1. (2b)). According to RFC 2328
667
     note 23, we don't have to find the same link that is used for par
668
     to en, any link is enough. This we do for ptp links. For net-rt
669
     links, we have to find the same link to compute proper lb/lb_id,
670
     which may be later used as the next hop. */
671

    
672
  /* In OSPFv2, en->lb is set here. In OSPFv3, en->lb is just cleared here,
673
     it is set in process_prefixes() to any global address in the area */
674

    
675
  en->lb = IPA_NONE;
676
  en->lb_id = 0;
677

    
678
  switch (en->lsa_type)
679
  {
680
  case LSA_T_RT:
681
    lsa_walk_rt_init(p, en, &rtl);
682
    while (lsa_walk_rt(&rtl))
683
    {
684
      switch (rtl.type)
685
      {
686
      case LSART_STUB:
687
        break;
688

    
689
      case LSART_NET:
690
        tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
691
        if (tmp == par)
692
        {
693
          if (ospf_is_v2(p))
694
            en->lb = ipa_from_u32(rtl.data);
695
          else
696
            en->lb_id = rtl.lif;
697

    
698
          return 1;
699
        }
700
        break;
701

    
702
      case LSART_VLNK:
703
      case LSART_PTP:
704
        /* Not necessary the same link, see RFC 2328 [23] */
705
        tmp = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
706
        if (tmp == par)
707
          return 1;
708
        break;
709
      }
710
    }
711
    break;
712

    
713
  case LSA_T_NET:
714
    ln = en->lsa_body;
715
    cnt = lsa_net_count(&en->lsa);
716
    for (i = 0; i < cnt; i++)
717
    {
718
      tmp = ospf_hash_find_rt(p->gr, oa->areaid, ln->routers[i]);
719
      if (tmp == par)
720
        return 1;
721
    }
722
    break;
723

    
724
  default:
725
    log(L_WARN "%s: Unknown LSA type in SPF: %d", p->p.name, en->lsa_type);
726
  }
727
  return 0;
728
}
729

    
730

    
731
/* RFC 2328 16.2. calculating inter-area routes */
732
static void
733
ospf_rt_sum(struct ospf_area *oa)
734
{
735
  struct ospf_proto *p = oa->po;
736
  struct top_hash_entry *en;
737
  net_addr net;
738
  u32 dst_rid, metric, options;
739
  ort *abr;
740
  int type;
741
  u8 pxopts;
742

    
743
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for inter-area (area %R)", oa->areaid);
744

    
745
  WALK_SLIST(en, p->lsal)
746
  {
747
    if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
748
      continue;
749

    
750
    if (en->domain != oa->areaid)
751
      continue;
752

    
753
    /* 16.2. (1a) */
754
    if (en->lsa.age == LSA_MAXAGE)
755
      continue;
756

    
757
    /* 16.2. (2) */
758
    if (en->lsa.rt == p->router_id)
759
      continue;
760

    
761
    /* 16.2. (3) is handled later in ospf_rt_abr() by resetting such rt entry */
762

    
763
    if (en->lsa_type == LSA_T_SUM_NET)
764
    {
765
      lsa_parse_sum_net(en, ospf_is_v2(p), &net, &pxopts, &metric);
766

    
767
      if (!ospf_valid_prefix(&net))
768
      {
769
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
770
            p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
771
        continue;
772
      }
773

    
774
      if (pxopts & OPT_PX_NU)
775
        continue;
776

    
777
      options = 0;
778
      type = ORT_NET;
779
    }
780
    else /* LSA_T_SUM_RT */
781
    {
782
      lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);
783

    
784
      /* We don't want local router in ASBR routing table */
785
      if (dst_rid == p->router_id)
786
        continue;
787

    
788
      options |= ORTA_ASBR;
789
      type = ORT_ROUTER;
790
    }
791

    
792
    /* 16.2. (1b) */
793
    if (metric == LSINFINITY)
794
      continue;
795

    
796
    /* 16.2. (4) */
797
    net_addr_ip4 nrid = net_from_rid(en->lsa.rt);
798
    abr = fib_find(&oa->rtr, (net_addr *) &nrid);
799
    if (!abr || !abr->n.type)
800
      continue;
801

    
802
    if (!(abr->n.options & ORTA_ABR))
803
      continue;
804

    
805
    /* This check is not mentioned in RFC 2328 */
806
    if (abr->n.type != RTS_OSPF)
807
      continue;
808

    
809
    /* 16.2. (5) */
810
    orta nf = {
811
      .type = RTS_OSPF_IA,
812
      .options = options,
813
      .metric1 = abr->n.metric1 + metric,
814
      .metric2 = LSINFINITY,
815
      .tag = 0,
816
      .rid = en->lsa.rt, /* ABR ID */
817
      .oa = oa,
818
      .nhs = abr->n.nhs
819
    };
820

    
821
    if (type == ORT_NET)
822
      ri_install_net(p, &net, &nf);
823
    else
824
      ri_install_rt(oa, dst_rid, &nf);
825
  }
826
}
827

    
828
/* RFC 2328 16.3. examining summary-LSAs in transit areas */
829
static void
830
ospf_rt_sum_tr(struct ospf_area *oa)
831
{
832
  struct ospf_proto *p = oa->po;
833
  struct ospf_area *bb = p->backbone;
834
  struct top_hash_entry *en;
835
  ort *re, *abr;
836
  u32 metric;
837

    
838
  if (!bb)
839
    return;
840

    
841
  WALK_SLIST(en, p->lsal)
842
  {
843
    if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
844
      continue;
845

    
846
    if (en->domain != oa->areaid)
847
      continue;
848

    
849
    /* 16.3 (1a) */
850
    if (en->lsa.age == LSA_MAXAGE)
851
      continue;
852

    
853
    /* 16.3 (2) */
854
    if (en->lsa.rt == p->router_id)
855
      continue;
856

    
857
    if (en->lsa_type == LSA_T_SUM_NET)
858
    {
859
      net_addr net;
860
      u8 pxopts;
861

    
862
      lsa_parse_sum_net(en, ospf_is_v2(p), &net, &pxopts, &metric);
863

    
864
      if (!ospf_valid_prefix(&net))
865
      {
866
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
867
            p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
868
        continue;
869
      }
870

    
871
      if (pxopts & OPT_PX_NU)
872
        continue;
873

    
874
      re = fib_find(&p->rtf, &net);
875
    }
876
    else // en->lsa_type == LSA_T_SUM_RT
877
    {
878
      u32 dst_rid, options;
879

    
880
      lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);
881

    
882
      net_addr_ip4 nrid = net_from_rid(dst_rid);
883
      re = fib_find(&bb->rtr, (net_addr *) &nrid);
884
    }
885

    
886
    /* 16.3 (1b) */
887
    if (metric == LSINFINITY)
888
      continue;
889

    
890
    /* 16.3 (3) */
891
    if (!re || !re->n.type)
892
      continue;
893

    
894
    if (re->n.oa->areaid != 0)
895
      continue;
896

    
897
    if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA))
898
      continue;
899

    
900
    /* 16.3. (4) */
901
    net_addr_ip4 nrid = net_from_rid(en->lsa.rt);
902
    abr = fib_find(&oa->rtr, (net_addr *) &nrid);
903
    if (!abr || !abr->n.type)
904
      continue;
905

    
906
    metric = abr->n.metric1 + metric; /* IAC */
907

    
908
    /* 16.3. (5) */
909
    if ((metric < re->n.metric1) ||
910
        ((metric == re->n.metric1) && unresolved_vlink(re)))
911
    {
912
      /* We want to replace the next-hop even if the metric is equal
913
         to replace a virtual next-hop through vlink with a real one.
914
         Proper ECMP would merge nexthops here, but we do not do that.
915
         We restrict nexthops to fit one area to simplify check
916
         12.4.3 p4 in decide_sum_lsa() */
917

    
918
      re->n.metric1 = metric;
919
      re->n.voa = oa;
920
      re->n.nhs = abr->n.nhs;
921
    }
922
  }
923
}
924

    
925
/* Decide about originating or flushing summary LSAs for condensed area networks */
926
static int
927
decide_anet_lsa(struct ospf_area *oa, struct area_net *anet, struct ospf_area *anet_oa)
928
{
929
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
930
  if (!oa_is_ext(oa) && !oa->ac->summary)
931
    return 0;
932

    
933
  if (oa == anet_oa)
934
    return 0;
935

    
936
  /* Do not condense routing info when exporting from backbone to the transit area */
937
  if ((anet_oa == oa->po->backbone) && oa->trcap)
938
    return 0;
939

    
940
  return (anet->active && !anet->hidden);
941
}
942

    
943
/* Decide about originating or flushing summary LSAs (12.4.3) */
944
static int
945
decide_sum_lsa(struct ospf_area *oa, ort *nf, int dest)
946
{
947
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
948
  if (!oa_is_ext(oa) && !oa->ac->summary)
949
    return 0;
950

    
951
  /* Invalid field - no route */
952
  if (!nf->n.type)
953
    return 0;
954

    
955
  /* 12.4.3 p2 */
956
  if (nf->n.type > RTS_OSPF_IA)
957
    return 0;
958

    
959
  /* 12.4.3 p3 */
960
  if ((nf->n.oa->areaid == oa->areaid))
961
    return 0;
962

    
963
  /* 12.4.3 p4 */
964
  if (nf->n.voa && (nf->n.voa->areaid == oa->areaid))
965
    return 0;
966

    
967
  /* 12.4.3 p5 */
968
  if (nf->n.metric1 >= LSINFINITY)
969
    return 0;
970

    
971
  /* 12.4.3 p6 - AS boundary router */
972
  if (dest == ORT_ROUTER)
973
  {
974
    /* We call decide_sum_lsa() on preferred ASBR entries, no need for 16.4. (3) */
975
    /* 12.4.3 p1 */
976
    return oa_is_ext(oa) && (nf->n.options & ORTA_ASBR);
977
  }
978

    
979
  /* 12.4.3 p7 - inter-area route */
980
  if (nf->n.type == RTS_OSPF_IA)
981
  {
982
    /* Inter-area routes are not repropagated into the backbone */
983
    return (oa != oa->po->backbone);
984
  }
985

    
986
  /* 12.4.3 p8 - intra-area route */
987

    
988
  /* Do not condense routing info when exporting from backbone to the transit area */
989
  if ((nf->n.oa == oa->po->backbone) && oa->trcap)
990
    return 1;
991

    
992
  struct area_net *anet = (struct area_net *)
993
    fib_route(&nf->n.oa->net_fib, nf->fn.addr);
994

    
995
  /* Condensed area network found */
996
  if (anet)
997
    return 0;
998

    
999
  return 1;
1000
}
1001

    
1002
/* RFC 2328 16.7. p1 - originate or flush summary LSAs */
1003
static inline void
1004
check_sum_net_lsa(struct ospf_proto *p, ort *nf)
1005
{
1006
  struct area_net *anet = NULL;
1007
  struct ospf_area *anet_oa = NULL;
1008

    
1009
  if (nf->area_net)
1010
  {
1011
    /* It is a default route for stub areas, handled entirely in ospf_rt_abr() */
1012
    if (nf->fn.addr->pxlen == 0)
1013
      return;
1014

    
1015
    /* Find that area network */
1016
    WALK_LIST(anet_oa, p->area_list)
1017
    {
1018
      anet = fib_find(&anet_oa->net_fib, nf->fn.addr);
1019
      if (anet)
1020
        break;
1021
    }
1022
  }
1023

    
1024
  struct ospf_area *oa;
1025
  WALK_LIST(oa, p->area_list)
1026
  {
1027
    if (anet && decide_anet_lsa(oa, anet, anet_oa))
1028
      ospf_originate_sum_net_lsa(p, oa, nf, anet->metric);
1029
    else if (decide_sum_lsa(oa, nf, ORT_NET))
1030
      ospf_originate_sum_net_lsa(p, oa, nf, nf->n.metric1);
1031
  }
1032
}
1033

    
1034
static inline void
1035
check_sum_rt_lsa(struct ospf_proto *p, ort *nf)
1036
{
1037
  u32 rid = rid_from_net(nf->fn.addr);
1038

    
1039
  struct ospf_area *oa;
1040
  WALK_LIST(oa, p->area_list)
1041
    if (decide_sum_lsa(oa, nf, ORT_ROUTER))
1042
      ospf_originate_sum_rt_lsa(p, oa, rid, nf->n.metric1, nf->n.options);
1043
}
1044

    
1045
static inline int
1046
decide_nssa_lsa(struct ospf_proto *p, ort *nf, struct ospf_lsa_ext_local *rt)
1047
{
1048
  struct ospf_area *oa = nf->n.oa;
1049
  struct top_hash_entry *en = nf->n.en;
1050

    
1051
  if (!rt_is_nssa(nf) || !oa->translate)
1052
    return 0;
1053

    
1054
  /* Condensed area network found */
1055
  if (fib_route(&oa->enet_fib, nf->fn.addr))
1056
    return 0;
1057

    
1058
  if (!en || (en->lsa_type != LSA_T_NSSA))
1059
    return 0;
1060

    
1061
  /* We do not store needed data in struct orta, we have to parse the LSA */
1062
  lsa_parse_ext(en, ospf_is_v2(p), rt);
1063

    
1064
  if (rt->pxopts & OPT_PX_NU)
1065
    return 0;
1066

    
1067
  if (!rt->propagate || ipa_zero(rt->fwaddr))
1068
    return 0;
1069

    
1070
  return 1;
1071
}
1072

    
1073
/* RFC 3103 3.2 - translating Type-7 LSAs into Type-5 LSAs */
1074
static inline void
1075
check_nssa_lsa(struct ospf_proto *p, ort *nf)
1076
{
1077
  struct area_net *anet = NULL;
1078
  struct ospf_area *oa = NULL;
1079
  struct ospf_lsa_ext_local rt;
1080

    
1081
  /* Do not translate LSA if there is already the external LSA from route export */
1082
  if (nf->external_rte)
1083
    return;
1084

    
1085
  if (nf->area_net)
1086
  {
1087
    /* Find that area network */
1088
    WALK_LIST(oa, p->area_list)
1089
    {
1090
      anet = fib_find(&oa->enet_fib, nf->fn.addr);
1091
      if (anet)
1092
        break;
1093
    }
1094
  }
1095

    
1096
  /* RFC 3103 3.2 (3) - originate the aggregated address range */
1097
  if (anet && anet->active && !anet->hidden && oa->translate)
1098
    ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, anet->metric,
1099
                           (anet->metric & LSA_EXT3_EBIT), IPA_NONE, anet->tag, 0);
1100

    
1101
  /* RFC 3103 3.2 (2) - originate the same network */
1102
  else if (decide_nssa_lsa(p, nf, &rt))
1103
    ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, rt.metric, rt.ebit, rt.fwaddr, rt.tag, 0);
1104
}
1105

    
1106
/* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1107
static void
1108
ospf_check_vlinks(struct ospf_proto *p)
1109
{
1110
  struct ospf_iface *ifa;
1111
  WALK_LIST(ifa, p->iface_list)
1112
  {
1113
    if (ifa->type == OSPF_IT_VLINK)
1114
    {
1115
      struct top_hash_entry *tmp;
1116
      tmp = ospf_hash_find_rt(p->gr, ifa->voa->areaid, ifa->vid);
1117

    
1118
      if (tmp && (tmp->color == INSPF) && ipa_nonzero(tmp->lb) && tmp->nhs)
1119
      {
1120
        struct ospf_iface *nhi = ospf_iface_find(p, tmp->nhs->iface);
1121

    
1122
        if ((ifa->state != OSPF_IS_PTP)
1123
            || (ifa->vifa != nhi)
1124
            || !ipa_equal(ifa->vip, tmp->lb))
1125
        {
1126
          OSPF_TRACE(D_EVENTS, "Vlink peer %R found", ifa->vid);
1127
          ospf_iface_sm(ifa, ISM_DOWN);
1128
          ifa->vifa = nhi;
1129
          ifa->addr = nhi->addr;
1130
          ifa->cost = tmp->dist;
1131
          ifa->vip = tmp->lb;
1132
          ospf_iface_sm(ifa, ISM_UP);
1133
        }
1134
        else if ((ifa->state == OSPF_IS_PTP) && (ifa->cost != tmp->dist))
1135
        {
1136
          ifa->cost = tmp->dist;
1137

    
1138
          /* RFC 2328 12.4 Event 8 - vlink state change */
1139
          ospf_notify_rt_lsa(ifa->oa);
1140
        }
1141
      }
1142
      else
1143
      {
1144
        if (ifa->state > OSPF_IS_DOWN)
1145
        {
1146
          OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", ifa->vid);
1147
          ospf_iface_sm(ifa, ISM_DOWN);
1148
        }
1149
      }
1150
    }
1151
  }
1152
}
1153

    
1154

    
1155
/* Miscellaneous route processing that needs to be done by ABRs */
1156
static void
1157
ospf_rt_abr1(struct ospf_proto *p)
1158
{
1159
  struct area_net *anet;
1160
  ort *default_nf;
1161
  net_addr default_net;
1162

    
1163
  /* RFC 2328 G.3 - incomplete resolution of virtual next hops - routers */
1164
  FIB_WALK(&p->backbone->rtr, ort, nf)
1165
  {
1166
    if (nf->n.type && unresolved_vlink(nf))
1167
      reset_ri(nf);
1168
  }
1169
  FIB_WALK_END;
1170

    
1171

    
1172
  FIB_WALK(&p->rtf, ort, nf)
1173
  {
1174
    /* RFC 2328 G.3 - incomplete resolution of virtual next hops - networks */
1175
    if (nf->n.type && unresolved_vlink(nf))
1176
      reset_ri(nf);
1177

    
1178

    
1179
    /* Compute condensed area networks */
1180
    if (nf->n.type == RTS_OSPF)
1181
    {
1182
      anet = (struct area_net *) fib_route(&nf->n.oa->net_fib, nf->fn.addr);
1183
      if (anet)
1184
      {
1185
        if (!anet->active)
1186
        {
1187
          anet->active = 1;
1188

    
1189
          /* Get a RT entry and mark it to know that it is an area network */
1190
          ort *nfi = fib_get(&p->rtf, anet->fn.addr);
1191
          nfi->area_net = 1;
1192

    
1193
          /* 16.2. (3) */
1194
          if (nfi->n.type == RTS_OSPF_IA)
1195
            reset_ri(nfi);
1196
        }
1197

    
1198
        if (anet->metric < nf->n.metric1)
1199
          anet->metric = nf->n.metric1;
1200
      }
1201
    }
1202
  }
1203
  FIB_WALK_END;
1204

    
1205

    
1206
  if (ospf_is_v2(p))
1207
    net_fill_ip4(&default_net, IP4_NONE, 0);
1208
  else
1209
    net_fill_ip6(&default_net, IP6_NONE, 0);
1210

    
1211
  default_nf = fib_get(&p->rtf, &default_net);
1212
  default_nf->area_net = 1;
1213

    
1214
  struct ospf_area *oa;
1215
  WALK_LIST(oa, p->area_list)
1216
  {
1217

    
1218
    /* 12.4.3.1. - originate or flush default route for stub/NSSA areas */
1219
    if (oa_is_stub(oa) || (oa_is_nssa(oa) && !oa->ac->summary))
1220
      ospf_originate_sum_net_lsa(p, oa, default_nf, oa->ac->default_cost);
1221

    
1222
    /*
1223
     * Originate type-7 default route for NSSA areas
1224
     *
1225
     * Because type-7 default LSAs are originated by ABRs, they do not
1226
     * collide with other type-7 LSAs (as ABRs generate type-5 LSAs
1227
     * for both external route export or external-NSSA translation),
1228
     * so we use 0 for the src arg.
1229
     */
1230

    
1231
    if (oa_is_nssa(oa) && oa->ac->default_nssa)
1232
      ospf_originate_ext_lsa(p, oa, default_nf, LSA_M_RTCALC, oa->ac->default_cost,
1233
                             (oa->ac->default_cost & LSA_EXT3_EBIT), IPA_NONE, 0, 0);
1234

    
1235
    /* RFC 2328 16.4. (3) - precompute preferred ASBR entries */
1236
    if (oa_is_ext(oa))
1237
    {
1238
      FIB_WALK(&oa->rtr, ort, nf)
1239
      {
1240
        if (nf->n.options & ORTA_ASBR)
1241
          ri_install_asbr(p, rid_from_net(nf->fn.addr), &nf->n);
1242
      }
1243
      FIB_WALK_END;
1244
    }
1245
  }
1246

    
1247

    
1248
  /* Originate or flush ASBR summary LSAs */
1249
  FIB_WALK(&p->backbone->rtr, ort, nf)
1250
  {
1251
    check_sum_rt_lsa(p, nf);
1252
  }
1253
  FIB_WALK_END;
1254

    
1255

    
1256
  /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1257
  ospf_check_vlinks(p);
1258
}
1259

    
1260

    
1261
static void
1262
translator_timer_hook(timer *timer)
1263
{
1264
  struct ospf_area *oa = timer->data;
1265

    
1266
  if (oa->translate != TRANS_WAIT)
1267
    return;
1268

    
1269
  oa->translate = TRANS_OFF;
1270
  ospf_schedule_rtcalc(oa->po);
1271
}
1272

    
1273
static void
1274
ospf_rt_abr2(struct ospf_proto *p)
1275
{
1276
  struct ospf_area *oa;
1277
  struct top_hash_entry *en;
1278

    
1279
  /* RFC 3103 3.1 - type-7 translator election */
1280
  struct ospf_area *bb = p->backbone;
1281
  WALK_LIST(oa, p->area_list)
1282
    if (oa_is_nssa(oa))
1283
    {
1284
      int translate = 1;
1285

    
1286
      if (oa->ac->translator)
1287
        goto decided;
1288

    
1289
      FIB_WALK(&oa->rtr, ort, nf)
1290
      {
1291
        if (!nf->n.type || !(nf->n.options & ORTA_ABR))
1292
          continue;
1293

    
1294
        ort *nf2 = fib_find(&bb->rtr, nf->fn.addr);
1295
        if (!nf2 || !nf2->n.type || !(nf2->n.options & ORTA_ABR))
1296
          continue;
1297

    
1298
        en = ospf_hash_find_rt(p->gr, oa->areaid, nf->n.rid);
1299
        if (!en || (en->color != INSPF))
1300
          continue;
1301

    
1302
        struct ospf_lsa_rt *rt = en->lsa_body;
1303
        /* There is better candidate - Nt-bit or higher Router ID */
1304
        if ((rt->options & OPT_RT_NT) || (p->router_id < nf->n.rid))
1305
        {
1306
          translate = 0;
1307
          goto decided;
1308
        }
1309
      }
1310
      FIB_WALK_END;
1311

    
1312
    decided:
1313
      if (translate && (oa->translate != TRANS_ON))
1314
      {
1315
        if (oa->translate == TRANS_WAIT)
1316
          tm_stop(oa->translator_timer);
1317

    
1318
        oa->translate = TRANS_ON;
1319
      }
1320

    
1321
      if (!translate && (oa->translate == TRANS_ON))
1322
      {
1323
        if (oa->translator_timer == NULL)
1324
          oa->translator_timer = tm_new_set(p->p.pool, translator_timer_hook, oa, 0, 0);
1325

    
1326
        /* Schedule the end of translation */
1327
        tm_start(oa->translator_timer, oa->ac->transint);
1328
        oa->translate = TRANS_WAIT;
1329
      }
1330
    }
1331

    
1332

    
1333
  /* Compute condensed external networks */
1334
  FIB_WALK(&p->rtf, ort, nf)
1335
  {
1336
    if (rt_is_nssa(nf) && (nf->n.options & ORTA_PROP))
1337
    {
1338
      struct area_net *anet = fib_route(&nf->n.oa->enet_fib, nf->fn.addr);
1339

    
1340
      if (anet)
1341
      {
1342
        if (!anet->active)
1343
        {
1344
          anet->active = 1;
1345

    
1346
          /* Get a RT entry and mark it to know that it is an area network */
1347
          ort *nf2 = fib_get(&p->rtf, anet->fn.addr);
1348
          nf2->area_net = 1;
1349
        }
1350

    
1351
        u32 metric = (nf->n.type == RTS_OSPF_EXT1) ?
1352
          nf->n.metric1 : ((nf->n.metric2 + 1) | LSA_EXT3_EBIT);
1353

    
1354
        if (anet->metric < metric)
1355
          anet->metric = metric;
1356
      }
1357
    }
1358
  }
1359
  FIB_WALK_END;
1360

    
1361

    
1362
  FIB_WALK(&p->rtf, ort, nf)
1363
  {
1364
    check_sum_net_lsa(p, nf);
1365
    check_nssa_lsa(p, nf);
1366
  }
1367
  FIB_WALK_END;
1368
}
1369

    
1370

    
1371
/* Like fib_route(), but ignores dummy rt entries */
1372
static void *
1373
ospf_fib_route_ip4(struct fib *f, ip4_addr a, int len)
1374
{
1375
  net_addr_ip4 net = NET_ADDR_IP4(a, len);
1376
  ort *nf;
1377

    
1378
loop:
1379
  nf = fib_find(f, (net_addr *) &net);
1380
  if (nf && nf->n.type)
1381
    return nf;
1382

    
1383
  if (net.pxlen > 0)
1384
  {
1385
    net.pxlen--;
1386
    ip4_clrbit(&net.prefix, net.pxlen);
1387
    goto loop;
1388
  }
1389

    
1390
  return NULL;
1391
}
1392

    
1393
static void *
1394
ospf_fib_route_ip6(struct fib *f, ip6_addr a, int len)
1395
{
1396
  net_addr_ip6 net = NET_ADDR_IP6(a, len);
1397
  ort *nf;
1398

    
1399
loop:
1400
  nf = fib_find(f, (net_addr *) &net);
1401
  if (nf && nf->n.type)
1402
    return nf;
1403

    
1404
  if (net.pxlen > 0)
1405
  {
1406
    net.pxlen--;
1407
    ip6_clrbit(&net.prefix, net.pxlen);
1408
    goto loop;
1409
  }
1410

    
1411
  return NULL;
1412
}
1413

    
1414
static void *
1415
ospf_fib_route(struct fib *f, ip_addr a)
1416
{
1417
  if (f->addr_type == NET_IP4)
1418
    return ospf_fib_route_ip4(f, ipa_to_ip4(a), IP4_MAX_PREFIX_LENGTH);
1419
  else
1420
    return ospf_fib_route_ip6(f, ipa_to_ip6(a), IP6_MAX_PREFIX_LENGTH);
1421
}
1422

    
1423

    
1424
/* RFC 2328 16.4. calculating external routes */
1425
static void
1426
ospf_ext_spf(struct ospf_proto *p)
1427
{
1428
  struct top_hash_entry *en;
1429
  struct ospf_lsa_ext_local rt;
1430
  ort *nf1, *nf2;
1431
  orta nfa = {};
1432
  u32 br_metric;
1433
  struct ospf_area *atmp;
1434

    
1435
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
1436

    
1437
  WALK_SLIST(en, p->lsal)
1438
  {
1439
    /* 16.4. (1) */
1440
    if ((en->lsa_type != LSA_T_EXT) && (en->lsa_type != LSA_T_NSSA))
1441
      continue;
1442

    
1443
    if (en->lsa.age == LSA_MAXAGE)
1444
      continue;
1445

    
1446
    /* 16.4. (2) */
1447
    if (en->lsa.rt == p->router_id)
1448
      continue;
1449

    
1450
    DBG("%s: Working on LSA. ID: %R, RT: %R, Type: %u\n",
1451
        p->p.name, en->lsa.id, en->lsa.rt, en->lsa_type);
1452

    
1453
    lsa_parse_ext(en, ospf_is_v2(p), &rt);
1454

    
1455
    if (!ospf_valid_prefix(&rt.net))
1456
    {
1457
      log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
1458
          p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
1459
      continue;
1460
    }
1461

    
1462
    if (rt.metric == LSINFINITY)
1463
      continue;
1464

    
1465
    if (rt.pxopts & OPT_PX_NU)
1466
      continue;
1467

    
1468
    /* 16.4. (3) */
1469
    /* If there are more areas, we already precomputed preferred ASBR
1470
       entries in ospf_rt_abr1() and stored them in the backbone
1471
       table. For NSSA, we examine the area to which the LSA is assigned */
1472
    if (en->lsa_type == LSA_T_EXT)
1473
      atmp = ospf_main_area(p);
1474
    else /* NSSA */
1475
      atmp = ospf_find_area(p, en->domain);
1476

    
1477
    if (!atmp)
1478
      continue;                        /* Should not happen */
1479

    
1480
    net_addr_ip4 nrid = net_from_rid(en->lsa.rt);
1481
    nf1 = fib_find(&atmp->rtr, (net_addr *) &nrid);
1482

    
1483
    if (!nf1 || !nf1->n.type)
1484
      continue;                        /* No AS boundary router found */
1485

    
1486
    if (!(nf1->n.options & ORTA_ASBR))
1487
      continue;                        /* It is not ASBR */
1488

    
1489
    /* 16.4. (3) NSSA - special rule for default routes */
1490
    /* ABR should use default only if P-bit is set and summaries are active */
1491
    if ((en->lsa_type == LSA_T_NSSA) && (rt.net.pxlen == 0) &&
1492
        (p->areano > 1) && !(rt.propagate && atmp->ac->summary))
1493
      continue;
1494

    
1495
    if (!rt.fbit)
1496
    {
1497
      nf2 = nf1;
1498
      nfa.nhs = nf1->n.nhs;
1499
      br_metric = nf1->n.metric1;
1500
    }
1501
    else
1502
    {
1503
      nf2 = ospf_fib_route(&p->rtf, rt.fwaddr);
1504
      if (!nf2)
1505
        continue;
1506

    
1507
      if (en->lsa_type == LSA_T_EXT)
1508
      {
1509
        /* For ext routes, we accept intra-area or inter-area routes */
1510
        if ((nf2->n.type != RTS_OSPF) && (nf2->n.type != RTS_OSPF_IA))
1511
          continue;
1512
      }
1513
      else /* NSSA */
1514
      {
1515
        /* For NSSA routes, we accept just intra-area in the same area */
1516
        if ((nf2->n.type != RTS_OSPF) || (nf2->n.oa != atmp))
1517
          continue;
1518
      }
1519

    
1520
      /* Next-hop is a part of a configured stubnet */
1521
      if (!nf2->n.nhs)
1522
        continue;
1523

    
1524
      nfa.nhs = nf2->n.nhs;
1525
      br_metric = nf2->n.metric1;
1526

    
1527
      /* Replace device nexthops with nexthops to forwarding address from LSA */
1528
      if (has_device_nexthops(nfa.nhs))
1529
      {
1530
        nfa.nhs = fix_device_nexthops(p, nfa.nhs, rt.fwaddr);
1531
        nfa.nhs_reuse = 1;
1532
      }
1533
    }
1534

    
1535
    if (rt.ebit)
1536
    {
1537
      nfa.type = RTS_OSPF_EXT2;
1538
      nfa.metric1 = br_metric;
1539
      nfa.metric2 = rt.metric;
1540
    }
1541
    else
1542
    {
1543
      nfa.type = RTS_OSPF_EXT1;
1544
      nfa.metric1 = br_metric + rt.metric;
1545
      nfa.metric2 = LSINFINITY;
1546
    }
1547

    
1548
    /* Mark the LSA as reachable */
1549
    en->color = INSPF;
1550

    
1551
    /* Whether the route is preferred in route selection according to 16.4.1 */
1552
    nfa.options = epath_preferred(&nf2->n) ? ORTA_PREF : 0;
1553
    if (en->lsa_type == LSA_T_NSSA)
1554
    {
1555
      nfa.options |= ORTA_NSSA;
1556
      if (rt.propagate)
1557
        nfa.options |= ORTA_PROP;
1558
    }
1559

    
1560
    nfa.tag = rt.tag;
1561
    nfa.rid = en->lsa.rt;
1562
    nfa.oa = atmp; /* undefined in RFC 2328 */
1563
    nfa.en = en; /* store LSA for later (NSSA processing) */
1564

    
1565
    ri_install_ext(p, &rt.net, &nfa);
1566
  }
1567
}
1568

    
1569
/* Cleanup of routing tables and data */
1570
void
1571
ospf_rt_reset(struct ospf_proto *p)
1572
{
1573
  struct ospf_area *oa;
1574
  struct top_hash_entry *en;
1575

    
1576
  /* Reset old routing table */
1577
  FIB_WALK(&p->rtf, ort, ri)
1578
  {
1579
    ri->area_net = 0;
1580
    reset_ri(ri);
1581
  }
1582
  FIB_WALK_END;
1583

    
1584
  /* Reset SPF data in LSA db */
1585
  WALK_SLIST(en, p->lsal)
1586
  {
1587
    en->color = OUTSPF;
1588
    en->dist = LSINFINITY;
1589
    en->nhs = NULL;
1590
    en->lb = IPA_NONE;
1591

    
1592
    if (en->mode == LSA_M_RTCALC)
1593
      en->mode = LSA_M_STALE;
1594
  }
1595

    
1596
  WALK_LIST(oa, p->area_list)
1597
  {
1598
    /* Reset ASBR routing tables */
1599
    FIB_WALK(&oa->rtr, ort, ri)
1600
    {
1601
      reset_ri(ri);
1602
    }
1603
    FIB_WALK_END;
1604

    
1605
    /* Reset condensed area networks */
1606
    if (p->areano > 1)
1607
    {
1608
      FIB_WALK(&oa->net_fib, struct area_net, anet)
1609
      {
1610
        anet->active = 0;
1611
        anet->metric = 0;
1612
      }
1613
      FIB_WALK_END;
1614

    
1615
      FIB_WALK(&oa->enet_fib, struct area_net, anet)
1616
      {
1617
        anet->active = 0;
1618
        anet->metric = 0;
1619
      }
1620
      FIB_WALK_END;
1621
    }
1622
  }
1623
}
1624

    
1625
/**
1626
 * ospf_rt_spf - calculate internal routes
1627
 * @p: OSPF protocol instance
1628
 *
1629
 * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
1630
 * It's based on Dijkstra's shortest path tree algorithms.
1631
 * This function is invoked from ospf_disp().
1632
 */
1633
void
1634
ospf_rt_spf(struct ospf_proto *p)
1635
{
1636
  struct ospf_area *oa;
1637

    
1638
  if (p->areano == 0)
1639
    return;
1640

    
1641
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
1642

    
1643
  /* 16. (1) */
1644
  ospf_rt_reset(p);
1645

    
1646
  /* 16. (2) */
1647
  WALK_LIST(oa, p->area_list)
1648
    ospf_rt_spfa(oa);
1649

    
1650
  /* 16. (3) */
1651
  ospf_rt_sum(ospf_main_area(p));
1652

    
1653
  /* 16. (4) */
1654
  WALK_LIST(oa, p->area_list)
1655
    if (oa->trcap && (oa->areaid != 0))
1656
      ospf_rt_sum_tr(oa);
1657

    
1658
  if (p->areano > 1)
1659
    ospf_rt_abr1(p);
1660

    
1661
  /* 16. (5) */
1662
  ospf_ext_spf(p);
1663

    
1664
  if (p->areano > 1)
1665
    ospf_rt_abr2(p);
1666

    
1667
  rt_sync(p);
1668
  lp_flush(p->nhpool);
1669

    
1670
  p->calcrt = 0;
1671
}
1672

    
1673

    
1674
static inline int
1675
inherit_nexthops(struct nexthop *pn)
1676
{
1677
  /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */
1678
  return pn && (ipa_nonzero(pn->gw) || !pn->iface);
1679
}
1680

    
1681
static struct nexthop *
1682
calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
1683
              struct top_hash_entry *par, int pos)
1684
{
1685
  struct ospf_proto *p = oa->po;
1686
  struct nexthop *pn = par->nhs;
1687
  struct ospf_iface *ifa;
1688
  u32 rid = en->lsa.rt;
1689

    
1690
  /* 16.1.1. The next hop calculation */
1691
  DBG("     Next hop calculating for id: %R rt: %R type: %u\n",
1692
      en->lsa.id, en->lsa.rt, en->lsa_type);
1693

    
1694
  /* Usually, we inherit parent nexthops */
1695
  if (inherit_nexthops(pn))
1696
    return pn;
1697

    
1698
  /*
1699
   * There are three cases:
1700
   * 1) en is a local network (and par is root)
1701
   * 2) en is a ptp or ptmp neighbor (and par is root)
1702
   * 3) en is a bcast or nbma neighbor (and par is local network)
1703
   */
1704

    
1705
  /* The first case - local network */
1706
  if ((en->lsa_type == LSA_T_NET) && (par == oa->rt))
1707
  {
1708
    ifa = rt_pos_to_ifa(oa, pos);
1709
    if (!ifa)
1710
      return NULL;
1711

    
1712
    return new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight);
1713
  }
1714

    
1715
  /* The second case - ptp or ptmp neighbor */
1716
  if ((en->lsa_type == LSA_T_RT) && (par == oa->rt))
1717
  {
1718
    ifa = rt_pos_to_ifa(oa, pos);
1719
    if (!ifa)
1720
      return NULL;
1721

    
1722
    if (ifa->type == OSPF_IT_VLINK)
1723
      return new_nexthop(p, IPA_NONE, NULL, 0);
1724

    
1725
    struct ospf_neighbor *m = find_neigh(ifa, rid);
1726
    if (!m || (m->state != NEIGHBOR_FULL))
1727
      return NULL;
1728

    
1729
    return new_nexthop(p, m->ip, ifa->iface, ifa->ecmp_weight);
1730
  }
1731

    
1732
  /* The third case - bcast or nbma neighbor */
1733
  if ((en->lsa_type == LSA_T_RT) && (par->lsa_type == LSA_T_NET))
1734
  {
1735
    /* par->nhi should be defined from parent's calc_next_hop() */
1736
    if (!pn)
1737
      goto bad;
1738

    
1739
    if (ospf_is_v2(p))
1740
    {
1741
      /*
1742
       * In this case, next-hop is the same as link-back, which is
1743
       * already computed in link_back().
1744
       */
1745
      if (ipa_zero(en->lb))
1746
        goto bad;
1747

    
1748
      return new_nexthop(p, en->lb, pn->iface, pn->weight);
1749
    }
1750
    else /* OSPFv3 */
1751
    {
1752
      /*
1753
       * Next-hop is taken from lladdr field of Link-LSA, en->lb_id
1754
       * is computed in link_back().
1755
       */
1756
      struct top_hash_entry *lhe;
1757
      lhe = ospf_hash_find(p->gr, pn->iface->index, en->lb_id, rid, LSA_T_LINK);
1758

    
1759
      if (!lhe)
1760
        return NULL;
1761

    
1762
      struct ospf_lsa_link *llsa = lhe->lsa_body;
1763

    
1764
      if (ip6_zero(llsa->lladdr))
1765
        return NULL;
1766

    
1767
      return new_nexthop(p, ipa_from_ip6(llsa->lladdr), pn->iface, pn->weight);
1768
    }
1769
  }
1770

    
1771
 bad:
1772
  /* Probably bug or some race condition, we log it */
1773
  log(L_ERR "%s: Unexpected case in next hop calculation", p->p.name);
1774
  return NULL;
1775
}
1776

    
1777

    
1778
/* Add LSA into list of candidates in Dijkstra's algorithm */
1779
static void
1780
add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
1781
         u32 dist, struct ospf_area *oa, int pos)
1782
{
1783
  struct ospf_proto *p = oa->po;
1784
  node *prev, *n;
1785
  int added = 0;
1786
  struct top_hash_entry *act;
1787

    
1788
  /* 16.1. (2b) */
1789
  if (en == NULL)
1790
    return;
1791
  if (en->lsa.age == LSA_MAXAGE)
1792
    return;
1793

    
1794
  if (ospf_is_v3(p) && (en->lsa_type == LSA_T_RT))
1795
  {
1796
    /* In OSPFv3, check V6 flag */
1797
    struct ospf_lsa_rt *rt = en->lsa_body;
1798
    if (!(rt->options & OPT_V6))
1799
      return;
1800
  }
1801

    
1802
  /* 16.1. (2c) */
1803
  if (en->color == INSPF)
1804
    return;
1805

    
1806
  /* 16.1. (2d), also checks that dist < LSINFINITY */
1807
  if (dist > en->dist)
1808
    return;
1809

    
1810
  /* We should check whether there is a reverse link from en to par, */
1811
  if (!link_back(oa, en, par))
1812
    return;
1813

    
1814
  struct nexthop *nhs = calc_next_hop(oa, en, par, pos);
1815
  if (!nhs)
1816
  {
1817
    log(L_WARN "%s: Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
1818
        p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
1819
    return;
1820
  }
1821

    
1822
  /* If en->dist > 0, we know that en->color == CANDIDATE and en->nhs is defined. */
1823
  if ((dist == en->dist) && !nh_is_vlink(en->nhs))
1824
  {
1825
    /*
1826
     * For multipath, we should merge nexthops. We merge regular nexthops only.
1827
     * Dummy vlink nexthops are less preferred and handled as a special case.
1828
     *
1829
     * During merging, new nexthops (nhs) can be reused if they are not
1830
     * inherited from the parent (i.e. they are allocated in calc_next_hop()).
1831
     * Current nexthops (en->nhs) can be reused if they weren't inherited in
1832
     * previous steps (that is stored in nhs_reuse, i.e. created by merging or
1833
     * allocated in calc_next_hop()).
1834
     *
1835
     * Generally, a node first inherits shared nexthops from its parent and
1836
     * later possibly gets reusable (private) copy during merging. This is more
1837
     * or less same for both top_hash_entry nodes and orta nodes.
1838
     *
1839
     * Note that when a child inherits a private nexthop from its parent, it
1840
     * should make the nexthop shared for both parent and child, while we only
1841
     * update nhs_reuse for the child node. This makes nhs_reuse field for the
1842
     * parent technically incorrect, but it is not a problem as parent's nhs
1843
     * will not be modified (and nhs_reuse examined) afterwards.
1844
     */
1845

    
1846
    /* Keep old ones */
1847
    if (!p->ecmp || nh_is_vlink(nhs) || (nhs == en->nhs))
1848
      return;
1849

    
1850
    /* Merge old and new */
1851
    int new_reuse = (par->nhs != nhs);
1852
    en->nhs = nexthop_merge(en->nhs, nhs, en->nhs_reuse, new_reuse, p->ecmp, p->nhpool);
1853
    en->nhs_reuse = 1;
1854
    return;
1855
  }
1856

    
1857
  DBG("     Adding candidate: rt: %R, id: %R, type: %u\n",
1858
      en->lsa.rt, en->lsa.id, en->lsa_type);
1859

    
1860
  if (en->color == CANDIDATE)
1861
  {                                /* We found a shorter path */
1862
    rem_node(&en->cn);
1863
  }
1864
  en->nhs = nhs;
1865
  en->dist = dist;
1866
  en->color = CANDIDATE;
1867
  en->nhs_reuse = (par->nhs != nhs);
1868

    
1869
  prev = NULL;
1870

    
1871
  if (EMPTY_LIST(*l))
1872
  {
1873
    add_head(l, &en->cn);
1874
  }
1875
  else
1876
  {
1877
    WALK_LIST(n, *l)
1878
    {
1879
      act = SKIP_BACK(struct top_hash_entry, cn, n);
1880
      if ((act->dist > dist) ||
1881
          ((act->dist == dist) && (act->lsa_type == LSA_T_RT)))
1882
      {
1883
        if (prev == NULL)
1884
          add_head(l, &en->cn);
1885
        else
1886
          insert_node(&en->cn, prev);
1887
        added = 1;
1888
        break;
1889
      }
1890
      prev = n;
1891
    }
1892

    
1893
    if (!added)
1894
    {
1895
      add_tail(l, &en->cn);
1896
    }
1897
  }
1898
}
1899

    
1900
static inline int
1901
ort_changed(ort *nf, rta *nr)
1902
{
1903
  rta *or = nf->old_rta;
1904
  return !or ||
1905
    (nf->n.metric1 != nf->old_metric1) || (nf->n.metric2 != nf->old_metric2) ||
1906
    (nf->n.tag != nf->old_tag) || (nf->n.rid != nf->old_rid) ||
1907
    (nr->source != or->source) || (nr->dest != or->dest) ||
1908
    !nexthop_same(&(nr->nh), &(or->nh));
1909
}
1910

    
1911
static void
1912
rt_sync(struct ospf_proto *p)
1913
{
1914
  struct top_hash_entry *en;
1915
  struct fib_iterator fit;
1916
  struct fib *fib = &p->rtf;
1917
  struct ospf_area *oa;
1918

    
1919
  /* This is used for forced reload of routes */
1920
  int reload = (p->calcrt == 2);
1921

    
1922
  OSPF_TRACE(D_EVENTS, "Starting routing table synchronization");
1923

    
1924
  DBG("Now syncing my rt table with nest's\n");
1925
  FIB_ITERATE_INIT(&fit, fib);
1926
again1:
1927
  FIB_ITERATE_START(fib, &fit, ort, nf)
1928
  {
1929
    /* Sanity check of next-hop addresses, failure should not happen */
1930
    if (nf->n.type)
1931
    {
1932
      struct nexthop *nh;
1933
      for (nh = nf->n.nhs; nh; nh = nh->next)
1934
        if (ipa_nonzero(nh->gw))
1935
        {
1936
          neighbor *ng = neigh_find2(&p->p, &nh->gw, nh->iface, 0);
1937
          if (!ng || (ng->scope == SCOPE_HOST))
1938
            { reset_ri(nf); break; }
1939
        }
1940
    }
1941

    
1942
    /* Remove configured stubnets */
1943
    if (!nf->n.nhs)
1944
      reset_ri(nf);
1945

    
1946
    if (nf->n.type) /* Add the route */
1947
    {
1948
      rta a0 = {
1949
        .src = p->p.main_source,
1950
        .source = nf->n.type,
1951
        .scope = SCOPE_UNIVERSE,
1952
        .dest = RTD_UNICAST,
1953
        .nh = *(nf->n.nhs),
1954
      };
1955

    
1956
      if (reload || ort_changed(nf, &a0))
1957
      {
1958
        rta *a = rta_lookup(&a0);
1959
        rte *e = rte_get_temp(a);
1960

    
1961
        rta_free(nf->old_rta);
1962
        nf->old_rta = rta_clone(a);
1963
        e->u.ospf.metric1 = nf->old_metric1 = nf->n.metric1;
1964
        e->u.ospf.metric2 = nf->old_metric2 = nf->n.metric2;
1965
        e->u.ospf.tag = nf->old_tag = nf->n.tag;
1966
        e->u.ospf.router_id = nf->old_rid = nf->n.rid;
1967
        e->pflags = 0;
1968

    
1969
        DBG("Mod rte type %d - %N via %I on iface %s, met %d\n",
1970
            a0.source, nf->fn.addr, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
1971
        rte_update(&p->p, nf->fn.addr, e);
1972
      }
1973
    }
1974
    else if (nf->old_rta)
1975
    {
1976
      /* Remove the route */
1977
      rta_free(nf->old_rta);
1978
      nf->old_rta = NULL;
1979

    
1980
      rte_update(&p->p, nf->fn.addr, NULL);
1981
    }
1982

    
1983
    /* Remove unused rt entry, some special entries are persistent */
1984
    if (!nf->n.type && !nf->external_rte && !nf->area_net)
1985
    {
1986
      if (nf->lsa_id)
1987
        idm_free(&p->idm, nf->lsa_id);
1988

    
1989
      FIB_ITERATE_PUT(&fit);
1990
      fib_delete(fib, nf);
1991
      goto again1;
1992
    }
1993
  }
1994
  FIB_ITERATE_END;
1995

    
1996

    
1997
  WALK_LIST(oa, p->area_list)
1998
  {
1999
    /* Cleanup ASBR hash tables */
2000
    FIB_ITERATE_INIT(&fit, &oa->rtr);
2001
again2:
2002
    FIB_ITERATE_START(&oa->rtr, &fit, ort, nf)
2003
    {
2004
      if (!nf->n.type)
2005
      {
2006
        FIB_ITERATE_PUT(&fit);
2007
        fib_delete(&oa->rtr, nf);
2008
        goto again2;
2009
      }
2010
    }
2011
    FIB_ITERATE_END;
2012
  }
2013

    
2014
  /* Cleanup stale LSAs */
2015
  WALK_SLIST(en, p->lsal)
2016
    if (en->mode == LSA_M_STALE)
2017
      ospf_flush_lsa(p, en);
2018
}