Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / rt.c @ 600998fc

History | View | Annotate | Download (47.5 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 mpnh *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 mpnh *
37
new_nexthop(struct ospf_proto *p, ip_addr gw, struct iface *iface, byte weight)
38
{
39
  struct mpnh *nh = lp_alloc(p->nhpool, sizeof(struct mpnh));
40
  nh->gw = gw;
41
  nh->iface = iface;
42
  nh->next = NULL;
43
  nh->weight = weight;
44
  return nh;
45
}
46

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

    
55
  return 0;
56
}
57

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

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

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

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

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

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

    
93

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

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

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

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

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

    
125
  return 0;
126
}
127

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

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

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

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

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

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

    
161

    
162
  /* Rest is BIRD-specific */
163

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

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

    
180

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

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

    
188
  return -1;
189
}
190

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

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

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

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

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

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

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

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

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

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

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

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

    
256

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

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

    
269
  return -1;
270
}
271

    
272

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

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

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

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

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

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

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

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

    
325

    
326

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

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

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

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

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

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

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

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

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

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

    
383
  return NULL;
384
}
385

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

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

    
395
  return NULL;
396
}
397

    
398

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

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

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

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

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

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

    
440

    
441

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
560
    px = en->lsa_body;
561

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

    
568
    if (!src)
569
      continue;
570

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

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

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

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

    
587
      if (pxopts & OPT_PX_NU)
588
        continue;
589

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
699
          return 1;
700
        }
701
        break;
702

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

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

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

    
731

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

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

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

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

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

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

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

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

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

    
775
      if (pxopts & OPT_PX_NU)
776
        continue;
777

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

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

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

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

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

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

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

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

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

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

    
839
  if (!bb)
840
    return;
841

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

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

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

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

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

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

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

    
872
      if (pxopts & OPT_PX_NU)
873
        continue;
874

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
1000
  return 1;
1001
}
1002

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

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

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

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

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

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

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

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

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

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

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

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

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

    
1071
  return 1;
1072
}
1073

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

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

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

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

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

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

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

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

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

    
1155

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

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

    
1172

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

    
1179

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

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

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

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

    
1206

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

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

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

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

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

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

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

    
1248

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

    
1256

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

    
1261

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

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

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

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

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

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

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

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

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

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

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

    
1319
        oa->translate = TRANS_ON;
1320
      }
1321

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

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

    
1333

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

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

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

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

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

    
1362

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

    
1371

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

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

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

    
1391
  return NULL;
1392
}
1393

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

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

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

    
1412
  return NULL;
1413
}
1414

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

    
1424

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
1671
  p->calcrt = 0;
1672
}
1673

    
1674

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
1760
      if (!lhe)
1761
        return NULL;
1762

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

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

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

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

    
1778

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

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

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

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

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

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

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

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

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

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

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

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

    
1870
  prev = NULL;
1871

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

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

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

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

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

    
1924
  OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation");
1925

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

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

    
1948
    if (nf->n.type) /* Add the route */
1949
    {
1950
      rta a0 = {
1951
        .src = p->p.main_source,
1952
        .source = nf->n.type,
1953
        .scope = SCOPE_UNIVERSE,
1954
        .cast = RTC_UNICAST
1955
      };
1956

    
1957
      if (nf->n.nhs->next)
1958
      {
1959
        a0.dest = RTD_MULTIPATH;
1960
        a0.nexthops = nf->n.nhs;
1961
      }
1962
      else if (ipa_nonzero(nf->n.nhs->gw))
1963
      {
1964
        a0.dest = RTD_ROUTER;
1965
        a0.iface = nf->n.nhs->iface;
1966
        a0.gw = nf->n.nhs->gw;
1967
      }
1968
      else
1969
      {
1970
        a0.dest = RTD_DEVICE;
1971
        a0.iface = nf->n.nhs->iface;
1972
      }
1973

    
1974
      if (reload || ort_changed(nf, &a0))
1975
      {
1976
        net *ne = net_get(p->p.table, nf->fn.addr);
1977
        rta *a = rta_lookup(&a0);
1978
        rte *e = rte_get_temp(a);
1979

    
1980
        rta_free(nf->old_rta);
1981
        nf->old_rta = rta_clone(a);
1982
        e->u.ospf.metric1 = nf->old_metric1 = nf->n.metric1;
1983
        e->u.ospf.metric2 = nf->old_metric2 = nf->n.metric2;
1984
        e->u.ospf.tag = nf->old_tag = nf->n.tag;
1985
        e->u.ospf.router_id = nf->old_rid = nf->n.rid;
1986
        e->pflags = 0;
1987
        e->net = ne;
1988
        e->pref = p->p.preference;
1989

    
1990
        DBG("Mod rte type %d - %N via %I on iface %s, met %d\n",
1991
            a0.source, nf->fn.addr, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
1992
        rte_update(&p->p, ne, e);
1993
      }
1994
    }
1995
    else if (nf->old_rta)
1996
    {
1997
      /* Remove the route */
1998
      rta_free(nf->old_rta);
1999
      nf->old_rta = NULL;
2000

    
2001
      net *ne = net_get(p->p.table, nf->fn.addr);
2002
      rte_update(&p->p, ne, NULL);
2003
    }
2004

    
2005
    /* Remove unused rt entry, some special entries are persistent */
2006
    if (!nf->n.type && !nf->external_rte && !nf->area_net)
2007
    {
2008
      FIB_ITERATE_PUT(&fit);
2009
      fib_delete(fib, nf);
2010
      goto again1;
2011
    }
2012
  }
2013
  FIB_ITERATE_END;
2014

    
2015

    
2016
  WALK_LIST(oa, p->area_list)
2017
  {
2018
    /* Cleanup ASBR hash tables */
2019
    FIB_ITERATE_INIT(&fit, &oa->rtr);
2020
again2:
2021
    FIB_ITERATE_START(&oa->rtr, &fit, ort, nf)
2022
    {
2023
      if (!nf->n.type)
2024
      {
2025
        FIB_ITERATE_PUT(&fit);
2026
        fib_delete(&oa->rtr, nf);
2027
        goto again2;
2028
      }
2029
    }
2030
    FIB_ITERATE_END;
2031
  }
2032

    
2033
  /* Cleanup stale LSAs */
2034
  WALK_SLIST(en, p->lsal)
2035
    if (en->mode == LSA_M_STALE)
2036
      ospf_flush_lsa(p, en);
2037
}