Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / rt.c @ c8cafc8e

History | View | Annotate | Download (47.7 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
void
25
ospf_rt_initort(struct fib_node *fn)
26
{
27
  ort *ri = (ort *) fn;
28
  reset_ri(ri);
29
  ri->old_rta = NULL;
30
  ri->fn.flags = 0;
31
}
32

    
33
static inline int
34
nh_is_vlink(struct mpnh *nhs)
35
{
36
  return !nhs->iface;
37
}
38

    
39
static inline int
40
unresolved_vlink(ort *ort)
41
{
42
  return ort->n.nhs && nh_is_vlink(ort->n.nhs);
43
}
44

    
45
static inline struct mpnh *
46
new_nexthop(struct ospf_proto *p, ip_addr gw, struct iface *iface, byte weight)
47
{
48
  struct mpnh *nh = lp_alloc(p->nhpool, sizeof(struct mpnh));
49
  nh->gw = gw;
50
  nh->iface = iface;
51
  nh->next = NULL;
52
  nh->weight = weight;
53
  return nh;
54
}
55

    
56
/* Returns true if there are device nexthops in n */
57
static inline int
58
has_device_nexthops(const struct mpnh *n)
59
{
60
  for (; n; n = n->next)
61
    if (ipa_zero(n->gw))
62
      return 1;
63

    
64
  return 0;
65
}
66

    
67
/* Replace device nexthops with nexthops to gw */
68
static struct mpnh *
69
fix_device_nexthops(struct ospf_proto *p, const struct mpnh *n, ip_addr gw)
70
{
71
  struct mpnh *root1 = NULL;
72
  struct mpnh *root2 = NULL;
73
  struct mpnh **nn1 = &root1;
74
  struct mpnh **nn2 = &root2;
75

    
76
  if (!p->ecmp)
77
    return new_nexthop(p, gw, n->iface, n->weight);
78

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

    
83
  for (; n; n = n->next)
84
  {
85
    struct mpnh *nn = new_nexthop(p, ipa_zero(n->gw) ? gw : n->gw, n->iface, n->weight);
86

    
87
    if (ipa_zero(n->gw))
88
    {
89
      *nn1 = nn;
90
      nn1 = &(nn->next);
91
    }
92
    else
93
    {
94
      *nn2 = nn;
95
      nn2 = &(nn->next);
96
    }
97
  }
98

    
99
  return mpnh_merge(root1, root2, 1, 1, p->ecmp, p->nhpool);
100
}
101

    
102

    
103
/* Whether the ASBR or the forward address destination is preferred
104
   in AS external route selection according to 16.4.1. */
105
static inline int
106
epath_preferred(const orta *ep)
107
{
108
  return (ep->type == RTS_OSPF) && (ep->oa->areaid != 0);
109
}
110

    
111
/* Whether the ext route has ASBR/next_hop marked as preferred. */
112
static inline int
113
orta_pref(const orta *nf)
114
{
115
  return !!(nf->options & ORTA_PREF);
116
}
117

    
118
/* Classify orta entries according to RFC 3101 2.5 (6e) priorities:
119
   Type-7 LSA with P-bit, Type-5 LSA, Type-7 LSA without P-bit */
120
static int
121
orta_prio(const orta *nf)
122
{
123
  /* RFC 3103 2.5 (6e) priorities */
124
  u32 opts = nf->options & (ORTA_NSSA | ORTA_PROP);
125

    
126
  /* A Type-7 LSA with the P-bit set */
127
  if (opts == (ORTA_NSSA | ORTA_PROP))
128
    return 2;
129

    
130
  /* A Type-5 LSA */
131
  if (opts == 0)
132
    return 1;
133

    
134
  return 0;
135
}
136

    
137
/* Whether the route is better according to RFC 3101 2.5 (6e):
138
   Prioritize Type-7 LSA with P-bit, then Type-5 LSA, then higher router ID */
139
static int
140
orta_prefer_lsa(const orta *new, const orta *old)
141
{
142
  int pn = orta_prio(new);
143
  int po = orta_prio(old);
144

    
145
  return (pn > po) || ((pn == po) && (new->en->lsa.rt > old->en->lsa.rt));
146
}
147

    
148
/*
149
 * Compare an existing routing table entry with a new one. Applicable for
150
 * intra-area routes, inter-area routes and router entries. Returns integer
151
 * <, = or > than 0 if the new orta is less, equal or more preferred than
152
 * the old orta.
153
 */
154
static int
155
orta_compare(const struct ospf_proto *p, const orta *new, const orta *old)
156
{
157
  int r;
158

    
159
  if (old->type == RTS_DUMMY)
160
    return 1;
161

    
162
  /* Prefer intra-area to inter-area to externals */
163
  r = ((int) old->type) - ((int) new->type);
164
  if (r) return r;
165

    
166
  /* Prefer lowest type 1 metric */
167
  r = ((int) old->metric1) - ((int) new->metric1);
168
  if (r) return r;
169

    
170

    
171
  /* Rest is BIRD-specific */
172

    
173
  /* Area-wide routes should not mix next-hops from different areas.
174
     This generally should not happen unless there is some misconfiguration. */
175
  if (new->oa->areaid != old->oa->areaid)
176
    return (new->oa->areaid > old->oa->areaid) ? 1 : -1;
177

    
178
  /* Prefer routes for configured stubnets (!nhs) to regular routes to dummy
179
     vlink nexthops. We intentionally return -1 if both are stubnets or vlinks. */
180
  if (!old->nhs)
181
    return -1;
182
  if (!new->nhs)
183
    return 1;
184
  if (nh_is_vlink(new->nhs))
185
    return -1;
186
  if (nh_is_vlink(old->nhs))
187
    return 1;
188

    
189

    
190
  if (p->ecmp)
191
    return 0;
192

    
193
  /* Prefer routes with higher Router ID, just to be more deterministic */
194
  if (new->rid > old->rid)
195
    return 1;
196

    
197
  return -1;
198
}
199

    
200
/*
201
 * Compare ASBR routing table entry with a new one, used for precompute ASBRs
202
 * for AS external route selection (RFC 2328 16.4 (3)), Returns integer < or >
203
 * than 0 if the new ASBR is less or more preferred than the old ASBR.
204
 */
205
static int
206
orta_compare_asbr(const struct ospf_proto *p, const orta *new, const orta *old)
207
{
208
  int r;
209

    
210
  if (old->type == RTS_DUMMY)
211
    return 1;
212

    
213
  if (!p->rfc1583)
214
  {
215
    r = epath_preferred(new) - epath_preferred(old);
216
    if (r) return r;
217
  }
218

    
219
  r = ((int) old->metric1) - ((int) new->metric1);
220
  if (r) return r;
221

    
222
  /* Larger area ID is preferred */
223
  if (new->oa->areaid > old->oa->areaid)
224
    return 1;
225

    
226
  /* There is just one ASBR of that RID per area, so tie is not possible */
227
  return -1;
228
}
229

    
230
/*
231
 * Compare a routing table entry with a new one, for AS external routes
232
 * (RFC 2328 16.4) and NSSA routes (RFC 3103 2.5), Returns integer <, = or >
233
 * than 0 if the new orta is less, equal or more preferred than the old orta.
234
 */
235
static int
236
orta_compare_ext(const struct ospf_proto *p, const orta *new, const orta *old)
237
{
238
  int r;
239

    
240
  if (old->type == RTS_DUMMY)
241
    return 1;
242

    
243
  /* 16.4 (6a) - prefer routes with lower type */
244
  r = ((int) old->type) - ((int) new->type);
245
  if (r) return r;
246

    
247
  /* 16.4 (6b) - prefer routes with lower type 2 metric */
248
  if (new->type == RTS_OSPF_EXT2)
249
  {
250
    r = ((int) old->metric2) - ((int) new->metric2);
251
    if (r) return r;
252
  }
253

    
254
  /* 16.4 (6c) - if not RFC1583, prefer routes with preferred ASBR/next_hop */
255
  if (!p->rfc1583)
256
  {
257
    r = orta_pref(new) - orta_pref(old);
258
    if (r) return r;
259
  }
260

    
261
  /* 16.4 (6d) - prefer routes with lower type 1 metric */
262
  r = ((int) old->metric1) - ((int) new->metric1);
263
  if (r) return r;
264

    
265

    
266
  if (p->ecmp && p->merge_external)
267
    return 0;
268

    
269
  /*
270
   * RFC 3101 2.5 (6e) - prioritize Type-7 LSA with P-bit, then Type-5 LSA, then
271
   * LSA with higher router ID. Although this should apply just to functionally
272
   * equivalent LSAs (i.e. ones with the same non-zero forwarding address), we
273
   * use it also to disambiguate otherwise equally preferred nexthops.
274
   */
275
  if (orta_prefer_lsa(new, old))
276
    return 1;
277

    
278
  return -1;
279
}
280

    
281

    
282
static inline void
283
ort_replace(ort *o, const orta *new)
284
{
285
  memcpy(&o->n, new, sizeof(orta));
286
}
287

    
288
static void
289
ort_merge(struct ospf_proto *p, ort *o, const orta *new)
290
{
291
  orta *old = &o->n;
292

    
293
  if (old->nhs != new->nhs)
294
  {
295
    old->nhs = mpnh_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
296
                          p->ecmp, p->nhpool);
297
    old->nhs_reuse = 1;
298
  }
299

    
300
  if (old->rid < new->rid)
301
    old->rid = new->rid;
302
}
303

    
304
static void
305
ort_merge_ext(struct ospf_proto *p, ort *o, const orta *new)
306
{
307
  orta *old = &o->n;
308

    
309
  if (old->nhs != new->nhs)
310
  {
311
    old->nhs = mpnh_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
312
                          p->ecmp, p->nhpool);
313
    old->nhs_reuse = 1;
314
  }
315

    
316
  if (old->tag != new->tag)
317
    old->tag = 0;
318

    
319
  /*
320
   * Even with multipath, we store only one LSA in orta.en for the purpose of
321
   * NSSA/ext translation. Therefore, we apply procedures from RFC 3101 2.5 (6e)
322
   * to all chosen LSAs for given network, not just to functionally equivalent
323
   * ones (i.e. ones with the same non-zero forwarding address).
324
   */
325
  if (orta_prefer_lsa(new, old))
326
  {
327
    old->options = new->options;
328
    old->rid = new->rid;
329
    old->oa = new->oa;
330
    old->en = new->en;
331
  }
332
}
333

    
334

    
335

    
336
static inline void
337
ri_install_net(struct ospf_proto *p, ip_addr prefix, int pxlen, const orta *new)
338
{
339
  ort *old = (ort *) fib_get(&p->rtf, &prefix, pxlen);
340
  int cmp = orta_compare(p, new, &old->n);
341

    
342
  if (cmp > 0)
343
    ort_replace(old, new);
344
  else if (cmp == 0)
345
    ort_merge(p, old, new);
346
}
347

    
348
static inline void
349
ri_install_rt(struct ospf_area *oa, u32 rid, const orta *new)
350
{
351
  ip_addr addr = ipa_from_rid(rid);
352
  ort *old = (ort *) fib_get(&oa->rtr, &addr, MAX_PREFIX_LENGTH);
353
  int cmp = orta_compare(oa->po, new, &old->n);
354

    
355
  if (cmp > 0)
356
    ort_replace(old, new);
357
  else if (cmp == 0)
358
    ort_merge(oa->po, old, new);
359
}
360

    
361
static inline void
362
ri_install_asbr(struct ospf_proto *p, ip_addr *addr, const orta *new)
363
{
364
  ort *old = (ort *) fib_get(&p->backbone->rtr, addr, MAX_PREFIX_LENGTH);
365
  if (orta_compare_asbr(p, new, &old->n) > 0)
366
    ort_replace(old, new);
367
}
368

    
369
static inline void
370
ri_install_ext(struct ospf_proto *p, ip_addr prefix, int pxlen, const orta *new)
371
{
372
  ort *old = (ort *) fib_get(&p->rtf, &prefix, pxlen);
373
  int cmp = orta_compare_ext(p, new, &old->n);
374

    
375
  if (cmp > 0)
376
    ort_replace(old, new);
377
  else if (cmp == 0)
378
    ort_merge_ext(p, old, new);
379
}
380

    
381
static inline struct ospf_iface *
382
rt_pos_to_ifa(struct ospf_area *oa, int pos)
383
{
384
  struct ospf_iface *ifa;
385

    
386
  WALK_LIST(ifa, oa->po->iface_list)
387
    if (ifa->oa == oa && pos >= ifa->rt_pos_beg && pos < ifa->rt_pos_end)
388
      return ifa;
389

    
390
  return NULL;
391
}
392

    
393
static inline struct ospf_iface *
394
px_pos_to_ifa(struct ospf_area *oa, int pos)
395
{
396
  struct ospf_iface *ifa;
397

    
398
  WALK_LIST(ifa, oa->po->iface_list)
399
    if (ifa->oa == oa && pos >= ifa->px_pos_beg && pos < ifa->px_pos_end)
400
      return ifa;
401

    
402
  return NULL;
403
}
404

    
405

    
406
static void
407
add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en, int pos)
408
{
409
  struct ospf_proto *p = oa->po;
410

    
411
  orta nf = {
412
    .type = RTS_OSPF,
413
    .options = 0,
414
    .metric1 = metric,
415
    .metric2 = LSINFINITY,
416
    .tag = 0,
417
    .rid = en->lsa.rt,
418
    .oa = oa,
419
    .nhs = en->nhs
420
  };
421

    
422
  if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
423
  {
424
    log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
425
        p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
426
    return;
427
  }
428

    
429
  if (en == oa->rt)
430
  {
431
    /*
432
     * Local stub networks does not have proper iface in en->nhi
433
     * (because they all have common top_hash_entry en).
434
     * We have to find iface responsible for that stub network.
435
     * Configured stubnets does not have any iface. They will
436
     * be removed in rt_sync().
437
     */
438

    
439
    struct ospf_iface *ifa;
440
    ifa = ospf_is_v2(p) ? rt_pos_to_ifa(oa, pos) : px_pos_to_ifa(oa, pos);
441
    nf.nhs = ifa ? new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight) : NULL;
442
  }
443

    
444
  ri_install_net(p, px, pxlen, &nf);
445
}
446

    
447

    
448

    
449
static inline void
450
spfa_process_rt(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
451
{
452
  struct ospf_lsa_rt *rt = act->lsa_body;
453
  struct ospf_lsa_rt_walk rtl;
454
  struct top_hash_entry *tmp;
455
  ip_addr prefix;
456
  int pxlen, i;
457

    
458
  if (rt->options & OPT_RT_V)
459
    oa->trcap = 1;
460

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

    
483
  /* Errata 2078 to RFC 5340 4.8.1 - skip links from non-routing nodes */
484
  if (ospf_is_v3(p) && (act != oa->rt) && !(rt->options & OPT_R))
485
    return;
486

    
487
  /* Now process Rt links */
488
  for (lsa_walk_rt_init(p, act, &rtl), i = 0; lsa_walk_rt(&rtl); i++)
489
  {
490
    tmp = NULL;
491

    
492
    switch (rtl.type)
493
    {
494
    case LSART_STUB:
495

    
496
      /* Should not happen, LSART_STUB is not defined in OSPFv3 */
497
      if (ospf_is_v3(p))
498
        break;
499

    
500
      /*
501
       * RFC 2328 in 16.1. (2a) says to handle stub networks in an
502
       * second phase after the SPF for an area is calculated. We get
503
       * the same result by handing them here because add_network()
504
       * will keep the best (not the first) found route.
505
       */
506
      prefix = ipa_from_u32(rtl.id & rtl.data);
507
      pxlen = u32_masklen(rtl.data);
508
      add_network(oa, prefix, pxlen, act->dist + rtl.metric, act, i);
509
      break;
510

    
511
    case LSART_NET:
512
      tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
513
      break;
514

    
515
    case LSART_VLNK:
516
    case LSART_PTP:
517
      tmp = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
518
      break;
519
    }
520

    
521
    add_cand(&oa->cand, tmp, act, act->dist + rtl.metric, oa, i);
522
  }
523
}
524

    
525
static inline void
526
spfa_process_net(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
527
{
528
  struct ospf_lsa_net *ln = act->lsa_body;
529
  struct top_hash_entry *tmp;
530
  ip_addr prefix;
531
  int pxlen, i, cnt;
532

    
533
  if (ospf_is_v2(p))
534
  {
535
    prefix = ipa_from_u32(act->lsa.id & ln->optx);
536
    pxlen = u32_masklen(ln->optx);
537
    add_network(oa, prefix, pxlen, act->dist, act, -1);
538
  }
539

    
540
  cnt = lsa_net_count(&act->lsa);
541
  for (i = 0; i < cnt; i++)
542
  {
543
    tmp = ospf_hash_find_rt(p->gr, oa->areaid, ln->routers[i]);
544
    add_cand(&oa->cand, tmp, act, act->dist, oa, -1);
545
  }
546
}
547

    
548
static inline void
549
spfa_process_prefixes(struct ospf_proto *p, struct ospf_area *oa)
550
{
551
  struct top_hash_entry *en, *src;
552
  struct ospf_lsa_prefix *px;
553
  ip_addr pxa;
554
  int pxlen;
555
  u8 pxopts;
556
  u16 metric;
557
  u32 *buf;
558
  int i;
559

    
560
  WALK_SLIST(en, p->lsal)
561
  {
562
    if (en->lsa_type != LSA_T_PREFIX)
563
      continue;
564

    
565
    if (en->domain != oa->areaid)
566
      continue;
567

    
568
    if (en->lsa.age == LSA_MAXAGE)
569
      continue;
570

    
571
    px = en->lsa_body;
572

    
573
    /* For router prefix-LSA, we would like to find the first router-LSA */
574
    if (px->ref_type == LSA_T_RT)
575
      src = ospf_hash_find_rt(p->gr, oa->areaid, px->ref_rt);
576
    else
577
      src = ospf_hash_find(p->gr, oa->areaid, px->ref_id, px->ref_rt, px->ref_type);
578

    
579
    if (!src)
580
      continue;
581

    
582
    /* Reachable in SPF */
583
    if (src->color != INSPF)
584
      continue;
585

    
586
    if ((src->lsa_type != LSA_T_RT) && (src->lsa_type != LSA_T_NET))
587
      continue;
588

    
589
    buf = px->rest;
590
    for (i = 0; i < px->pxcount; i++)
591
      {
592
        buf = lsa_get_ipv6_prefix(buf, &pxa, &pxlen, &pxopts, &metric);
593

    
594
        if (pxopts & OPT_PX_NU)
595
          continue;
596

    
597
        /* Store the first global address to use it later as a vlink endpoint */
598
        if ((pxopts & OPT_PX_LA) && ipa_zero(src->lb))
599
          src->lb = pxa;
600

    
601
        add_network(oa, pxa, pxlen, src->dist + metric, src, i);
602
      }
603
  }
604
}
605

    
606
/* RFC 2328 16.1. calculating shortest paths for an area */
607
static void
608
ospf_rt_spfa(struct ospf_area *oa)
609
{
610
  struct ospf_proto *p = oa->po;
611
  struct top_hash_entry *act;
612
  node *n;
613

    
614
  if (oa->rt == NULL)
615
    return;
616
  if (oa->rt->lsa.age == LSA_MAXAGE)
617
    return;
618

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

    
621
  /* 16.1. (1) */
622
  init_list(&oa->cand);                /* Empty list of candidates */
623
  oa->trcap = 0;
624

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

    
627
  oa->rt->dist = 0;
628
  oa->rt->color = CANDIDATE;
629
  add_head(&oa->cand, &oa->rt->cn);
630
  DBG("RT LSA: rt: %R, id: %R, type: %u\n",
631
      oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa_type);
632

    
633
  while (!EMPTY_LIST(oa->cand))
634
  {
635
    n = HEAD(oa->cand);
636
    act = SKIP_BACK(struct top_hash_entry, cn, n);
637
    rem_node(n);
638

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

    
642
    act->color = INSPF;
643
    switch (act->lsa_type)
644
    {
645
    case LSA_T_RT:
646
      spfa_process_rt(p, oa, act);
647
      break;
648

    
649
    case LSA_T_NET:
650
      spfa_process_net(p, oa, act);
651
      break;
652

    
653
    default:
654
      log(L_WARN "%s: Unknown LSA type in SPF: %d", p->p.name, act->lsa_type);
655
    }
656
  }
657

    
658
  if (ospf_is_v3(p))
659
    spfa_process_prefixes(p, oa);
660
}
661

    
662
static int
663
link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par)
664
{
665
  struct ospf_proto *p = oa->po;
666
  struct ospf_lsa_rt_walk rtl;
667
  struct top_hash_entry *tmp;
668
  struct ospf_lsa_net *ln;
669
  u32 i, cnt;
670

    
671
  if (!en || !par) return 0;
672

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

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

    
683
  en->lb = IPA_NONE;
684
  en->lb_id = 0;
685

    
686
  switch (en->lsa_type)
687
  {
688
  case LSA_T_RT:
689
    lsa_walk_rt_init(p, en, &rtl);
690
    while (lsa_walk_rt(&rtl))
691
    {
692
      switch (rtl.type)
693
      {
694
      case LSART_STUB:
695
        break;
696

    
697
      case LSART_NET:
698
        tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
699
        if (tmp == par)
700
        {
701
          if (ospf_is_v2(p))
702
            en->lb = ipa_from_u32(rtl.data);
703
          else
704
            en->lb_id = rtl.lif;
705

    
706
          return 1;
707
        }
708
        break;
709

    
710
      case LSART_VLNK:
711
      case LSART_PTP:
712
        /* Not necessary the same link, see RFC 2328 [23] */
713
        tmp = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
714
        if (tmp == par)
715
          return 1;
716
        break;
717
      }
718
    }
719
    break;
720

    
721
  case LSA_T_NET:
722
    ln = en->lsa_body;
723
    cnt = lsa_net_count(&en->lsa);
724
    for (i = 0; i < cnt; i++)
725
    {
726
      tmp = ospf_hash_find_rt(p->gr, oa->areaid, ln->routers[i]);
727
      if (tmp == par)
728
        return 1;
729
    }
730
    break;
731

    
732
  default:
733
    log(L_WARN "%s: Unknown LSA type in SPF: %d", p->p.name, en->lsa_type);
734
  }
735
  return 0;
736
}
737

    
738

    
739
/* RFC 2328 16.2. calculating inter-area routes */
740
static void
741
ospf_rt_sum(struct ospf_area *oa)
742
{
743
  struct ospf_proto *p = oa->po;
744
  struct top_hash_entry *en;
745
  ip_addr ip, abrip;
746
  u32 dst_rid, metric, options;
747
  ort *abr;
748
  int pxlen = -1, type = -1;
749
  u8 pxopts;
750

    
751

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

    
754
  WALK_SLIST(en, p->lsal)
755
  {
756
    if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
757
      continue;
758

    
759
    if (en->domain != oa->areaid)
760
      continue;
761

    
762
    /* 16.2. (1a) */
763
    if (en->lsa.age == LSA_MAXAGE)
764
      continue;
765

    
766
    /* 16.2. (2) */
767
    if (en->lsa.rt == p->router_id)
768
      continue;
769

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

    
772
    if (en->lsa_type == LSA_T_SUM_NET)
773
    {
774
      lsa_parse_sum_net(en, ospf_is_v2(p), &ip, &pxlen, &pxopts, &metric);
775

    
776
      if (pxopts & OPT_PX_NU)
777
        continue;
778

    
779
      if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
780
      {
781
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
782
            p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
783
        continue;
784
      }
785

    
786
      options = 0;
787
      type = ORT_NET;
788
    }
789
    else /* LSA_T_SUM_RT */
790
    {
791
      lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);
792

    
793
      /* We don't want local router in ASBR routing table */
794
      if (dst_rid == p->router_id)
795
        continue;
796

    
797
      options |= ORTA_ASBR;
798
      type = ORT_ROUTER;
799
    }
800

    
801
    /* 16.2. (1b) */
802
    if (metric == LSINFINITY)
803
      continue;
804

    
805
    /* 16.2. (4) */
806
    abrip = ipa_from_rid(en->lsa.rt);
807
    abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
808
    if (!abr || !abr->n.type)
809
      continue;
810

    
811
    if (!(abr->n.options & ORTA_ABR))
812
      continue;
813

    
814
    /* This check is not mentioned in RFC 2328 */
815
    if (abr->n.type != RTS_OSPF)
816
      continue;
817

    
818
    /* 16.2. (5) */
819
    orta nf = {
820
      .type = RTS_OSPF_IA,
821
      .options = options,
822
      .metric1 = abr->n.metric1 + metric,
823
      .metric2 = LSINFINITY,
824
      .tag = 0,
825
      .rid = en->lsa.rt, /* ABR ID */
826
      .oa = oa,
827
      .nhs = abr->n.nhs
828
    };
829

    
830
    if (type == ORT_NET)
831
      ri_install_net(p, ip, pxlen, &nf);
832
    else
833
      ri_install_rt(oa, dst_rid, &nf);
834
  }
835
}
836

    
837
/* RFC 2328 16.3. examining summary-LSAs in transit areas */
838
static void
839
ospf_rt_sum_tr(struct ospf_area *oa)
840
{
841
  struct ospf_proto *p = oa->po;
842
  struct ospf_area *bb = p->backbone;
843
  struct top_hash_entry *en;
844
  ort *re, *abr;
845
  ip_addr ip, abrip;
846
  u32 dst_rid, metric, options;
847
  int pxlen;
848
  u8 pxopts;
849

    
850

    
851
  if (!bb)
852
    return;
853

    
854
  WALK_SLIST(en, p->lsal)
855
  {
856
    if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
857
      continue;
858

    
859
    if (en->domain != oa->areaid)
860
      continue;
861

    
862
    /* 16.3 (1a) */
863
    if (en->lsa.age == LSA_MAXAGE)
864
      continue;
865

    
866
    /* 16.3 (2) */
867
    if (en->lsa.rt == p->router_id)
868
      continue;
869

    
870
    if (en->lsa_type == LSA_T_SUM_NET)
871
    {
872
      lsa_parse_sum_net(en, ospf_is_v2(p), &ip, &pxlen, &pxopts, &metric);
873

    
874
      if (pxopts & OPT_PX_NU)
875
        continue;
876

    
877
      if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
878
      {
879
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
880
            p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
881
        continue;
882
      }
883

    
884
      re = fib_find(&p->rtf, &ip, pxlen);
885
    }
886
    else // en->lsa_type == LSA_T_SUM_RT
887
    {
888
      lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);
889

    
890
      ip = ipa_from_rid(dst_rid);
891
      re = fib_find(&bb->rtr, &ip, MAX_PREFIX_LENGTH);
892
    }
893

    
894
    /* 16.3 (1b) */
895
    if (metric == LSINFINITY)
896
      continue;
897

    
898
    /* 16.3 (3) */
899
    if (!re || !re->n.type)
900
      continue;
901

    
902
    if (re->n.oa->areaid != 0)
903
      continue;
904

    
905
    if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA))
906
      continue;
907

    
908
    /* 16.3. (4) */
909
    abrip = ipa_from_rid(en->lsa.rt);
910
    abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
911
    if (!abr || !abr->n.type)
912
      continue;
913

    
914
    metric = abr->n.metric1 + metric; /* IAC */
915

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

    
926
      re->n.metric1 = metric;
927
      re->n.voa = oa;
928
      re->n.nhs = abr->n.nhs;
929
    }
930
  }
931
}
932

    
933
/* Decide about originating or flushing summary LSAs for condensed area networks */
934
static int
935
decide_anet_lsa(struct ospf_area *oa, struct area_net *anet, struct ospf_area *anet_oa)
936
{
937
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
938
  if (!oa_is_ext(oa) && !oa->ac->summary)
939
    return 0;
940

    
941
  if (oa == anet_oa)
942
    return 0;
943

    
944
  /* Do not condense routing info when exporting from backbone to the transit area */
945
  if ((anet_oa == oa->po->backbone) && oa->trcap)
946
    return 0;
947

    
948
  return (anet->active && !anet->hidden);
949
}
950

    
951
/* Decide about originating or flushing summary LSAs (12.4.3) */
952
static int
953
decide_sum_lsa(struct ospf_area *oa, ort *nf, int dest)
954
{
955
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
956
  if (!oa_is_ext(oa) && !oa->ac->summary)
957
    return 0;
958

    
959
  /* Invalid field - no route */
960
  if (!nf->n.type)
961
    return 0;
962

    
963
  /* 12.4.3 p2 */
964
  if (nf->n.type > RTS_OSPF_IA)
965
    return 0;
966

    
967
  /* 12.4.3 p3 */
968
  if ((nf->n.oa->areaid == oa->areaid))
969
    return 0;
970

    
971
  /* 12.4.3 p4 */
972
  if (nf->n.voa && (nf->n.voa->areaid == oa->areaid))
973
    return 0;
974

    
975
  /* 12.4.3 p5 */
976
  if (nf->n.metric1 >= LSINFINITY)
977
    return 0;
978

    
979
  /* 12.4.3 p6 - AS boundary router */
980
  if (dest == ORT_ROUTER)
981
  {
982
    /* We call decide_sum_lsa() on preferred ASBR entries, no need for 16.4. (3) */
983
    /* 12.4.3 p1 */
984
    return oa_is_ext(oa) && (nf->n.options & ORTA_ASBR);
985
  }
986

    
987
  /* 12.4.3 p7 - inter-area route */
988
  if (nf->n.type == RTS_OSPF_IA)
989
  {
990
    /* Inter-area routes are not repropagated into the backbone */
991
    return (oa != oa->po->backbone);
992
  }
993

    
994
  /* 12.4.3 p8 - intra-area route */
995

    
996
  /* Do not condense routing info when exporting from backbone to the transit area */
997
  if ((nf->n.oa == oa->po->backbone) && oa->trcap)
998
    return 1;
999

    
1000
  struct area_net *anet = (struct area_net *)
1001
    fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen);
1002

    
1003
  /* Condensed area network found */
1004
  if (anet)
1005
    return 0;
1006

    
1007
  return 1;
1008
}
1009

    
1010
/* RFC 2328 16.7. p1 - originate or flush summary LSAs */
1011
static inline void
1012
check_sum_net_lsa(struct ospf_proto *p, ort *nf)
1013
{
1014
  struct area_net *anet = NULL;
1015
  struct ospf_area *anet_oa = NULL;
1016

    
1017
  if (nf->area_net)
1018
  {
1019
    /* It is a default route for stub areas, handled entirely in ospf_rt_abr() */
1020
    if (nf->fn.pxlen == 0)
1021
      return;
1022

    
1023
    /* Find that area network */
1024
    WALK_LIST(anet_oa, p->area_list)
1025
    {
1026
      anet = (struct area_net *) fib_find(&anet_oa->net_fib, &nf->fn.prefix, nf->fn.pxlen);
1027
      if (anet)
1028
        break;
1029
    }
1030
  }
1031

    
1032
  struct ospf_area *oa;
1033
  WALK_LIST(oa, p->area_list)
1034
  {
1035
    if (anet && decide_anet_lsa(oa, anet, anet_oa))
1036
      ospf_originate_sum_net_lsa(p, oa, nf, anet->metric);
1037
    else if (decide_sum_lsa(oa, nf, ORT_NET))
1038
      ospf_originate_sum_net_lsa(p, oa, nf, nf->n.metric1);
1039
  }
1040
}
1041

    
1042
static inline void
1043
check_sum_rt_lsa(struct ospf_proto *p, ort *nf)
1044
{
1045
  struct ospf_area *oa;
1046
  WALK_LIST(oa, p->area_list)
1047
    if (decide_sum_lsa(oa, nf, ORT_ROUTER))
1048
      ospf_originate_sum_rt_lsa(p, oa, nf, nf->n.metric1, nf->n.options);
1049
}
1050

    
1051
static inline int
1052
decide_nssa_lsa(struct ospf_proto *p UNUSED4 UNUSED6, ort *nf, struct ospf_lsa_ext_local *rt)
1053
{
1054
  struct ospf_area *oa = nf->n.oa;
1055
  struct top_hash_entry *en = nf->n.en;
1056

    
1057
  if (!rt_is_nssa(nf) || !oa->translate)
1058
    return 0;
1059

    
1060
  /* Condensed area network found */
1061
  if (fib_route(&oa->enet_fib, nf->fn.prefix, nf->fn.pxlen))
1062
    return 0;
1063

    
1064
  if (!en || (en->lsa_type != LSA_T_NSSA))
1065
    return 0;
1066

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

    
1070
  if (rt->pxopts & OPT_PX_NU)
1071
    return 0;
1072

    
1073
  if (!rt->propagate || ipa_zero(rt->fwaddr))
1074
    return 0;
1075

    
1076
  return 1;
1077
}
1078

    
1079
/* RFC 3103 3.2 - translating Type-7 LSAs into Type-5 LSAs */
1080
static inline void
1081
check_nssa_lsa(struct ospf_proto *p, ort *nf)
1082
{
1083
  struct area_net *anet = NULL;
1084
  struct ospf_area *oa = NULL;
1085
  struct ospf_lsa_ext_local rt;
1086

    
1087
  /* Do not translate LSA if there is already the external LSA from route export */
1088
  if (nf->external_rte)
1089
    return;
1090

    
1091
  if (nf->area_net)
1092
  {
1093
    /* Find that area network */
1094
    WALK_LIST(oa, p->area_list)
1095
    {
1096
      anet = (struct area_net *) fib_find(&oa->enet_fib, &nf->fn.prefix, nf->fn.pxlen);
1097
      if (anet)
1098
        break;
1099
    }
1100
  }
1101

    
1102
  /* RFC 3103 3.2 (3) - originate the aggregated address range */
1103
  if (anet && anet->active && !anet->hidden && oa->translate)
1104
    ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, anet->metric,
1105
                           (anet->metric & LSA_EXT3_EBIT), IPA_NONE, anet->tag, 0);
1106

    
1107
  /* RFC 3103 3.2 (2) - originate the same network */
1108
  else if (decide_nssa_lsa(p, nf, &rt))
1109
    ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, rt.metric, rt.ebit, rt.fwaddr, rt.tag, 0);
1110
}
1111

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

    
1124
      if (tmp && (tmp->color == INSPF) && ipa_nonzero(tmp->lb) && tmp->nhs)
1125
      {
1126
        struct ospf_iface *nhi = ospf_iface_find(p, tmp->nhs->iface);
1127

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

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

    
1160

    
1161
/* Miscellaneous route processing that needs to be done by ABRs */
1162
static void
1163
ospf_rt_abr1(struct ospf_proto *p)
1164
{
1165
  struct area_net *anet;
1166
  ort *nf, *default_nf;
1167

    
1168
  /* RFC 2328 G.3 - incomplete resolution of virtual next hops - routers */
1169
  FIB_WALK(&p->backbone->rtr, nftmp)
1170
  {
1171
    nf = (ort *) nftmp;
1172

    
1173
    if (nf->n.type && unresolved_vlink(nf))
1174
      reset_ri(nf);
1175
  }
1176
  FIB_WALK_END;
1177

    
1178

    
1179
  FIB_WALK(&p->rtf, nftmp)
1180
  {
1181
    nf = (ort *) nftmp;
1182

    
1183

    
1184
    /* RFC 2328 G.3 - incomplete resolution of virtual next hops - networks */
1185
    if (nf->n.type && unresolved_vlink(nf))
1186
      reset_ri(nf);
1187

    
1188

    
1189
    /* Compute condensed area networks */
1190
    if (nf->n.type == RTS_OSPF)
1191
    {
1192
      anet = (struct area_net *) fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen);
1193
      if (anet)
1194
      {
1195
        if (!anet->active)
1196
        {
1197
          anet->active = 1;
1198

    
1199
          /* Get a RT entry and mark it to know that it is an area network */
1200
          ort *nfi = (ort *) fib_get(&p->rtf, &anet->fn.prefix, anet->fn.pxlen);
1201
          nfi->area_net = 1;
1202

    
1203
          /* 16.2. (3) */
1204
          if (nfi->n.type == RTS_OSPF_IA)
1205
            reset_ri(nfi);
1206
        }
1207

    
1208
        if (anet->metric < nf->n.metric1)
1209
          anet->metric = nf->n.metric1;
1210
      }
1211
    }
1212
  }
1213
  FIB_WALK_END;
1214

    
1215
  ip_addr addr = IPA_NONE;
1216
  default_nf = (ort *) fib_get(&p->rtf, &addr, 0);
1217
  default_nf->area_net = 1;
1218

    
1219
  struct ospf_area *oa;
1220
  WALK_LIST(oa, p->area_list)
1221
  {
1222

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

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

    
1236
    if (oa_is_nssa(oa) && oa->ac->default_nssa)
1237
      ospf_originate_ext_lsa(p, oa, default_nf, LSA_M_RTCALC, oa->ac->default_cost,
1238
                             (oa->ac->default_cost & LSA_EXT3_EBIT), IPA_NONE, 0, 0);
1239

    
1240
    /* RFC 2328 16.4. (3) - precompute preferred ASBR entries */
1241
    if (oa_is_ext(oa))
1242
    {
1243
      FIB_WALK(&oa->rtr, nftmp)
1244
      {
1245
        nf = (ort *) nftmp;
1246
        if (nf->n.options & ORTA_ASBR)
1247
          ri_install_asbr(p, &nf->fn.prefix, &nf->n);
1248
      }
1249
      FIB_WALK_END;
1250
    }
1251
  }
1252

    
1253

    
1254
  /* Originate or flush ASBR summary LSAs */
1255
  FIB_WALK(&p->backbone->rtr, nftmp)
1256
  {
1257
    check_sum_rt_lsa(p, (ort *) nftmp);
1258
  }
1259
  FIB_WALK_END;
1260

    
1261

    
1262
  /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1263
  ospf_check_vlinks(p);
1264
}
1265

    
1266

    
1267
static void
1268
translator_timer_hook(timer *timer)
1269
{
1270
  struct ospf_area *oa = timer->data;
1271

    
1272
  if (oa->translate != TRANS_WAIT)
1273
    return;
1274

    
1275
  oa->translate = TRANS_OFF;
1276
  ospf_schedule_rtcalc(oa->po);
1277
}
1278

    
1279
static void
1280
ospf_rt_abr2(struct ospf_proto *p)
1281
{
1282
  struct ospf_area *oa;
1283
  struct top_hash_entry *en;
1284
  ort *nf, *nf2;
1285

    
1286

    
1287
  /* RFC 3103 3.1 - type-7 translator election */
1288
  struct ospf_area *bb = p->backbone;
1289
  WALK_LIST(oa, p->area_list)
1290
    if (oa_is_nssa(oa))
1291
    {
1292
      int translate = 1;
1293

    
1294
      if (oa->ac->translator)
1295
        goto decided;
1296

    
1297
      FIB_WALK(&oa->rtr, nftmp)
1298
      {
1299
        nf = (ort *) nftmp;
1300
        if (!nf->n.type || !(nf->n.options & ORTA_ABR))
1301
          continue;
1302

    
1303
        nf2 = fib_find(&bb->rtr, &nf->fn.prefix, MAX_PREFIX_LENGTH);
1304
        if (!nf2 || !nf2->n.type || !(nf2->n.options & ORTA_ABR))
1305
          continue;
1306

    
1307
        en = ospf_hash_find_rt(p->gr, oa->areaid, nf->n.rid);
1308
        if (!en || (en->color != INSPF))
1309
          continue;
1310

    
1311
        struct ospf_lsa_rt *rt = en->lsa_body;
1312
        /* There is better candidate - Nt-bit or higher Router ID */
1313
        if ((rt->options & OPT_RT_NT) || (p->router_id < nf->n.rid))
1314
        {
1315
          translate = 0;
1316
          goto decided;
1317
        }
1318
      }
1319
      FIB_WALK_END;
1320

    
1321
    decided:
1322
      if (translate && (oa->translate != TRANS_ON))
1323
      {
1324
        if (oa->translate == TRANS_WAIT)
1325
          tm_stop(oa->translator_timer);
1326

    
1327
        oa->translate = TRANS_ON;
1328
      }
1329

    
1330
      if (!translate && (oa->translate == TRANS_ON))
1331
      {
1332
        if (oa->translator_timer == NULL)
1333
          oa->translator_timer = tm_new_set(p->p.pool, translator_timer_hook, oa, 0, 0);
1334

    
1335
        /* Schedule the end of translation */
1336
        tm_start(oa->translator_timer, oa->ac->transint);
1337
        oa->translate = TRANS_WAIT;
1338
      }
1339
    }
1340

    
1341

    
1342
  /* Compute condensed external networks */
1343
  FIB_WALK(&p->rtf, nftmp)
1344
  {
1345
    nf = (ort *) nftmp;
1346
    if (rt_is_nssa(nf) && (nf->n.options & ORTA_PROP))
1347
    {
1348
      struct area_net *anet = (struct area_net *)
1349
        fib_route(&nf->n.oa->enet_fib, nf->fn.prefix, nf->fn.pxlen);
1350

    
1351
      if (anet)
1352
      {
1353
        if (!anet->active)
1354
        {
1355
          anet->active = 1;
1356

    
1357
          /* Get a RT entry and mark it to know that it is an area network */
1358
          nf2 = (ort *) fib_get(&p->rtf, &anet->fn.prefix, anet->fn.pxlen);
1359
          nf2->area_net = 1;
1360
        }
1361

    
1362
        u32 metric = (nf->n.type == RTS_OSPF_EXT1) ?
1363
          nf->n.metric1 : ((nf->n.metric2 + 1) | LSA_EXT3_EBIT);
1364

    
1365
        if (anet->metric < metric)
1366
          anet->metric = metric;
1367
      }
1368
    }
1369
  }
1370
  FIB_WALK_END;
1371

    
1372

    
1373
  FIB_WALK(&p->rtf, nftmp)
1374
  {
1375
    nf = (ort *) nftmp;
1376

    
1377
    check_sum_net_lsa(p, nf);
1378
    check_nssa_lsa(p, nf);
1379
  }
1380
  FIB_WALK_END;
1381
}
1382

    
1383

    
1384
/* Like fib_route(), but ignores dummy rt entries */
1385
static void *
1386
ospf_fib_route(struct fib *f, ip_addr a, int len)
1387
{
1388
  ip_addr a0;
1389
  ort *nf;
1390

    
1391
  while (len >= 0)
1392
  {
1393
    a0 = ipa_and(a, ipa_mkmask(len));
1394
    nf = fib_find(f, &a0, len);
1395
    if (nf && nf->n.type)
1396
      return nf;
1397
    len--;
1398
  }
1399
  return NULL;
1400
}
1401

    
1402
/* RFC 2328 16.4. calculating external routes */
1403
static void
1404
ospf_ext_spf(struct ospf_proto *p)
1405
{
1406
  struct top_hash_entry *en;
1407
  struct ospf_lsa_ext_local rt;
1408
  ort *nf1, *nf2;
1409
  orta nfa = {};
1410
  ip_addr rtid;
1411
  u32 br_metric;
1412
  struct ospf_area *atmp;
1413

    
1414
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
1415

    
1416
  WALK_SLIST(en, p->lsal)
1417
  {
1418
    /* 16.4. (1) */
1419
    if ((en->lsa_type != LSA_T_EXT) && (en->lsa_type != LSA_T_NSSA))
1420
      continue;
1421

    
1422
    if (en->lsa.age == LSA_MAXAGE)
1423
      continue;
1424

    
1425
    /* 16.4. (2) */
1426
    if (en->lsa.rt == p->router_id)
1427
      continue;
1428

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

    
1432
    lsa_parse_ext(en, ospf_is_v2(p), &rt);
1433

    
1434
    if (rt.metric == LSINFINITY)
1435
      continue;
1436

    
1437
    if (rt.pxopts & OPT_PX_NU)
1438
      continue;
1439

    
1440
    if (rt.pxlen < 0 || rt.pxlen > MAX_PREFIX_LENGTH)
1441
    {
1442
      log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
1443
          p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
1444
      continue;
1445
    }
1446

    
1447

    
1448
    /* 16.4. (3) */
1449
    /* If there are more areas, we already precomputed preferred ASBR
1450
       entries in ospf_rt_abr1() and stored them in the backbone
1451
       table. For NSSA, we examine the area to which the LSA is assigned */
1452
    if (en->lsa_type == LSA_T_EXT)
1453
      atmp = ospf_main_area(p);
1454
    else /* NSSA */
1455
      atmp = ospf_find_area(p, en->domain);
1456

    
1457
    if (!atmp)
1458
      continue;                        /* Should not happen */
1459

    
1460
    rtid = ipa_from_rid(en->lsa.rt);
1461
    nf1 = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH);
1462

    
1463
    if (!nf1 || !nf1->n.type)
1464
      continue;                        /* No AS boundary router found */
1465

    
1466
    if (!(nf1->n.options & ORTA_ASBR))
1467
      continue;                        /* It is not ASBR */
1468

    
1469
    /* 16.4. (3) NSSA - special rule for default routes */
1470
    /* ABR should use default only if P-bit is set and summaries are active */
1471
    if ((en->lsa_type == LSA_T_NSSA) && ipa_zero(rt.ip) && (rt.pxlen == 0) &&
1472
        (p->areano > 1) && !(rt.propagate && atmp->ac->summary))
1473
      continue;
1474

    
1475
    if (!rt.fbit)
1476
    {
1477
      nf2 = nf1;
1478
      nfa.nhs = nf1->n.nhs;
1479
      br_metric = nf1->n.metric1;
1480
    }
1481
    else
1482
    {
1483
      nf2 = ospf_fib_route(&p->rtf, rt.fwaddr, MAX_PREFIX_LENGTH);
1484
      if (!nf2)
1485
        continue;
1486

    
1487
      if (en->lsa_type == LSA_T_EXT)
1488
      {
1489
        /* For ext routes, we accept intra-area or inter-area routes */
1490
        if ((nf2->n.type != RTS_OSPF) && (nf2->n.type != RTS_OSPF_IA))
1491
          continue;
1492
      }
1493
      else /* NSSA */
1494
      {
1495
        /* For NSSA routes, we accept just intra-area in the same area */
1496
        if ((nf2->n.type != RTS_OSPF) || (nf2->n.oa != atmp))
1497
          continue;
1498
      }
1499

    
1500
      /* Next-hop is a part of a configured stubnet */
1501
      if (!nf2->n.nhs)
1502
        continue;
1503

    
1504
      nfa.nhs = nf2->n.nhs;
1505
      br_metric = nf2->n.metric1;
1506

    
1507
      /* Replace device nexthops with nexthops to forwarding address from LSA */
1508
      if (has_device_nexthops(nfa.nhs))
1509
      {
1510
        nfa.nhs = fix_device_nexthops(p, nfa.nhs, rt.fwaddr);
1511
        nfa.nhs_reuse = 1;
1512
      }
1513
    }
1514

    
1515
    if (rt.ebit)
1516
    {
1517
      nfa.type = RTS_OSPF_EXT2;
1518
      nfa.metric1 = br_metric;
1519
      nfa.metric2 = rt.metric;
1520
    }
1521
    else
1522
    {
1523
      nfa.type = RTS_OSPF_EXT1;
1524
      nfa.metric1 = br_metric + rt.metric;
1525
      nfa.metric2 = LSINFINITY;
1526
    }
1527

    
1528
    /* Mark the LSA as reachable */
1529
    en->color = INSPF;
1530

    
1531
    /* Whether the route is preferred in route selection according to 16.4.1 */
1532
    nfa.options = epath_preferred(&nf2->n) ? ORTA_PREF : 0;
1533
    if (en->lsa_type == LSA_T_NSSA)
1534
    {
1535
      nfa.options |= ORTA_NSSA;
1536
      if (rt.propagate)
1537
        nfa.options |= ORTA_PROP;
1538
    }
1539

    
1540
    nfa.tag = rt.tag;
1541
    nfa.rid = en->lsa.rt;
1542
    nfa.oa = atmp; /* undefined in RFC 2328 */
1543
    nfa.en = en; /* store LSA for later (NSSA processing) */
1544

    
1545
    ri_install_ext(p, rt.ip, rt.pxlen, &nfa);
1546
  }
1547
}
1548

    
1549
/* Cleanup of routing tables and data */
1550
void
1551
ospf_rt_reset(struct ospf_proto *p)
1552
{
1553
  struct ospf_area *oa;
1554
  struct top_hash_entry *en;
1555
  struct area_net *anet;
1556
  ort *ri;
1557

    
1558
  /* Reset old routing table */
1559
  FIB_WALK(&p->rtf, nftmp)
1560
  {
1561
    ri = (ort *) nftmp;
1562
    ri->area_net = 0;
1563
    reset_ri(ri);
1564
  }
1565
  FIB_WALK_END;
1566

    
1567
  /* Reset SPF data in LSA db */
1568
  WALK_SLIST(en, p->lsal)
1569
  {
1570
    en->color = OUTSPF;
1571
    en->dist = LSINFINITY;
1572
    en->nhs = NULL;
1573
    en->lb = IPA_NONE;
1574

    
1575
    if (en->mode == LSA_M_RTCALC)
1576
      en->mode = LSA_M_STALE;
1577
  }
1578

    
1579
  WALK_LIST(oa, p->area_list)
1580
  {
1581
    /* Reset ASBR routing tables */
1582
    FIB_WALK(&oa->rtr, nftmp)
1583
    {
1584
      ri = (ort *) nftmp;
1585
      reset_ri(ri);
1586
    }
1587
    FIB_WALK_END;
1588

    
1589
    /* Reset condensed area networks */
1590
    if (p->areano > 1)
1591
    {
1592
      FIB_WALK(&oa->net_fib, nftmp)
1593
      {
1594
        anet = (struct area_net *) nftmp;
1595
        anet->active = 0;
1596
        anet->metric = 0;
1597
      }
1598
      FIB_WALK_END;
1599

    
1600
      FIB_WALK(&oa->enet_fib, nftmp)
1601
      {
1602
        anet = (struct area_net *) nftmp;
1603
        anet->active = 0;
1604
        anet->metric = 0;
1605
      }
1606
      FIB_WALK_END;
1607
    }
1608
  }
1609
}
1610

    
1611
/**
1612
 * ospf_rt_spf - calculate internal routes
1613
 * @p: OSPF protocol instance
1614
 *
1615
 * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
1616
 * It's based on Dijkstra's shortest path tree algorithms.
1617
 * This function is invoked from ospf_disp().
1618
 */
1619
void
1620
ospf_rt_spf(struct ospf_proto *p)
1621
{
1622
  struct ospf_area *oa;
1623

    
1624
  if (p->areano == 0)
1625
    return;
1626

    
1627
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
1628

    
1629
  /* 16. (1) */
1630
  ospf_rt_reset(p);
1631

    
1632
  /* 16. (2) */
1633
  WALK_LIST(oa, p->area_list)
1634
    ospf_rt_spfa(oa);
1635

    
1636
  /* 16. (3) */
1637
  ospf_rt_sum(ospf_main_area(p));
1638

    
1639
  /* 16. (4) */
1640
  WALK_LIST(oa, p->area_list)
1641
    if (oa->trcap && (oa->areaid != 0))
1642
      ospf_rt_sum_tr(oa);
1643

    
1644
  if (p->areano > 1)
1645
    ospf_rt_abr1(p);
1646

    
1647
  /* 16. (5) */
1648
  ospf_ext_spf(p);
1649

    
1650
  if (p->areano > 1)
1651
    ospf_rt_abr2(p);
1652

    
1653
  rt_sync(p);
1654
  lp_flush(p->nhpool);
1655

    
1656
  p->calcrt = 0;
1657
}
1658

    
1659

    
1660
static inline int
1661
inherit_nexthops(struct mpnh *pn)
1662
{
1663
  /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */
1664
  return pn && (ipa_nonzero(pn->gw) || !pn->iface);
1665
}
1666

    
1667
static struct mpnh *
1668
calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
1669
              struct top_hash_entry *par, int pos)
1670
{
1671
  struct ospf_proto *p = oa->po;
1672
  struct mpnh *pn = par->nhs;
1673
  struct ospf_iface *ifa;
1674
  u32 rid = en->lsa.rt;
1675

    
1676
  /* 16.1.1. The next hop calculation */
1677
  DBG("     Next hop calculating for id: %R rt: %R type: %u\n",
1678
      en->lsa.id, en->lsa.rt, en->lsa_type);
1679

    
1680
  /* Usually, we inherit parent nexthops */
1681
  if (inherit_nexthops(pn))
1682
    return pn;
1683

    
1684
  /*
1685
   * There are three cases:
1686
   * 1) en is a local network (and par is root)
1687
   * 2) en is a ptp or ptmp neighbor (and par is root)
1688
   * 3) en is a bcast or nbma neighbor (and par is local network)
1689
   */
1690

    
1691
  /* The first case - local network */
1692
  if ((en->lsa_type == LSA_T_NET) && (par == oa->rt))
1693
  {
1694
    ifa = rt_pos_to_ifa(oa, pos);
1695
    if (!ifa)
1696
      return NULL;
1697

    
1698
    return new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight);
1699
  }
1700

    
1701
  /* The second case - ptp or ptmp neighbor */
1702
  if ((en->lsa_type == LSA_T_RT) && (par == oa->rt))
1703
  {
1704
    ifa = rt_pos_to_ifa(oa, pos);
1705
    if (!ifa)
1706
      return NULL;
1707

    
1708
    if (ifa->type == OSPF_IT_VLINK)
1709
      return new_nexthop(p, IPA_NONE, NULL, 0);
1710

    
1711
    struct ospf_neighbor *m = find_neigh(ifa, rid);
1712
    if (!m || (m->state != NEIGHBOR_FULL))
1713
      return NULL;
1714

    
1715
    return new_nexthop(p, m->ip, ifa->iface, ifa->ecmp_weight);
1716
  }
1717

    
1718
  /* The third case - bcast or nbma neighbor */
1719
  if ((en->lsa_type == LSA_T_RT) && (par->lsa_type == LSA_T_NET))
1720
  {
1721
    /* par->nhi should be defined from parent's calc_next_hop() */
1722
    if (!pn)
1723
      goto bad;
1724

    
1725
    if (ospf_is_v2(p))
1726
    {
1727
      /*
1728
       * In this case, next-hop is the same as link-back, which is
1729
       * already computed in link_back().
1730
       */
1731
      if (ipa_zero(en->lb))
1732
        goto bad;
1733

    
1734
      return new_nexthop(p, en->lb, pn->iface, pn->weight);
1735
    }
1736
    else /* OSPFv3 */
1737
    {
1738
      /*
1739
       * Next-hop is taken from lladdr field of Link-LSA, en->lb_id
1740
       * is computed in link_back().
1741
       */
1742
      struct top_hash_entry *lhe;
1743
      lhe = ospf_hash_find(p->gr, pn->iface->index, en->lb_id, rid, LSA_T_LINK);
1744

    
1745
      if (!lhe)
1746
        return NULL;
1747

    
1748
      struct ospf_lsa_link *llsa = lhe->lsa_body;
1749

    
1750
      if (ip6_zero(llsa->lladdr))
1751
        return NULL;
1752

    
1753
      return new_nexthop(p, ipa_from_ip6(llsa->lladdr), pn->iface, pn->weight);
1754
    }
1755
  }
1756

    
1757
 bad:
1758
  /* Probably bug or some race condition, we log it */
1759
  log(L_ERR "%s: Unexpected case in next hop calculation", p->p.name);
1760
  return NULL;
1761
}
1762

    
1763

    
1764
/* Add LSA into list of candidates in Dijkstra's algorithm */
1765
static void
1766
add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
1767
         u32 dist, struct ospf_area *oa, int pos)
1768
{
1769
  struct ospf_proto *p = oa->po;
1770
  node *prev, *n;
1771
  int added = 0;
1772
  struct top_hash_entry *act;
1773

    
1774
  /* 16.1. (2b) */
1775
  if (en == NULL)
1776
    return;
1777
  if (en->lsa.age == LSA_MAXAGE)
1778
    return;
1779

    
1780
  if (ospf_is_v3(p) && (en->lsa_type == LSA_T_RT))
1781
  {
1782
    /* In OSPFv3, check V6 flag */
1783
    struct ospf_lsa_rt *rt = en->lsa_body;
1784
    if (!(rt->options & OPT_V6))
1785
      return;
1786
  }
1787

    
1788
  /* 16.1. (2c) */
1789
  if (en->color == INSPF)
1790
    return;
1791

    
1792
  /* 16.1. (2d), also checks that dist < LSINFINITY */
1793
  if (dist > en->dist)
1794
    return;
1795

    
1796
  /* We should check whether there is a reverse link from en to par, */
1797
  if (!link_back(oa, en, par))
1798
    return;
1799

    
1800
  struct mpnh *nhs = calc_next_hop(oa, en, par, pos);
1801
  if (!nhs)
1802
  {
1803
    log(L_WARN "%s: Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
1804
        p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
1805
    return;
1806
  }
1807

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

    
1832
    /* Keep old ones */
1833
    if (!p->ecmp || nh_is_vlink(nhs) || (nhs == en->nhs))
1834
      return;
1835

    
1836
    /* Merge old and new */
1837
    int new_reuse = (par->nhs != nhs);
1838
    en->nhs = mpnh_merge(en->nhs, nhs, en->nhs_reuse, new_reuse, p->ecmp, p->nhpool);
1839
    en->nhs_reuse = 1;
1840
    return;
1841
  }
1842

    
1843
  DBG("     Adding candidate: rt: %R, id: %R, type: %u\n",
1844
      en->lsa.rt, en->lsa.id, en->lsa_type);
1845

    
1846
  if (en->color == CANDIDATE)
1847
  {                                /* We found a shorter path */
1848
    rem_node(&en->cn);
1849
  }
1850
  en->nhs = nhs;
1851
  en->dist = dist;
1852
  en->color = CANDIDATE;
1853
  en->nhs_reuse = (par->nhs != nhs);
1854

    
1855
  prev = NULL;
1856

    
1857
  if (EMPTY_LIST(*l))
1858
  {
1859
    add_head(l, &en->cn);
1860
  }
1861
  else
1862
  {
1863
    WALK_LIST(n, *l)
1864
    {
1865
      act = SKIP_BACK(struct top_hash_entry, cn, n);
1866
      if ((act->dist > dist) ||
1867
          ((act->dist == dist) && (act->lsa_type == LSA_T_RT)))
1868
      {
1869
        if (prev == NULL)
1870
          add_head(l, &en->cn);
1871
        else
1872
          insert_node(&en->cn, prev);
1873
        added = 1;
1874
        break;
1875
      }
1876
      prev = n;
1877
    }
1878

    
1879
    if (!added)
1880
    {
1881
      add_tail(l, &en->cn);
1882
    }
1883
  }
1884
}
1885

    
1886
static inline int
1887
ort_changed(ort *nf, rta *nr)
1888
{
1889
  rta *or = nf->old_rta;
1890
  return !or ||
1891
    (nf->n.metric1 != nf->old_metric1) || (nf->n.metric2 != nf->old_metric2) ||
1892
    (nf->n.tag != nf->old_tag) || (nf->n.rid != nf->old_rid) ||
1893
    (nr->source != or->source) || (nr->dest != or->dest) ||
1894
    (nr->iface != or->iface) || !ipa_equal(nr->gw, or->gw) ||
1895
    !mpnh_same(nr->nexthops, or->nexthops);
1896
}
1897

    
1898
static void
1899
rt_sync(struct ospf_proto *p)
1900
{
1901
  struct top_hash_entry *en;
1902
  struct fib_iterator fit;
1903
  struct fib *fib = &p->rtf;
1904
  ort *nf;
1905
  struct ospf_area *oa;
1906

    
1907
  /* This is used for forced reload of routes */
1908
  int reload = (p->calcrt == 2);
1909

    
1910
  OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation");
1911

    
1912
  DBG("Now syncing my rt table with nest's\n");
1913
  FIB_ITERATE_INIT(&fit, fib);
1914
again1:
1915
  FIB_ITERATE_START(fib, &fit, nftmp)
1916
  {
1917
    nf = (ort *) nftmp;
1918

    
1919
    /* Sanity check of next-hop addresses, failure should not happen */
1920
    if (nf->n.type)
1921
    {
1922
      struct mpnh *nh;
1923
      for (nh = nf->n.nhs; nh; nh = nh->next)
1924
        if (ipa_nonzero(nh->gw))
1925
        {
1926
          neighbor *ng = neigh_find2(&p->p, &nh->gw, nh->iface, 0);
1927
          if (!ng || (ng->scope == SCOPE_HOST))
1928
            { reset_ri(nf); break; }
1929
        }
1930
    }
1931

    
1932
    /* Remove configured stubnets */
1933
    if (!nf->n.nhs)
1934
      reset_ri(nf);
1935

    
1936
    if (nf->n.type) /* Add the route */
1937
    {
1938
      rta a0 = {
1939
        .src = p->p.main_source,
1940
        .source = nf->n.type,
1941
        .scope = SCOPE_UNIVERSE,
1942
        .cast = RTC_UNICAST
1943
      };
1944

    
1945
      if (nf->n.nhs->next)
1946
      {
1947
        a0.dest = RTD_MULTIPATH;
1948
        a0.nexthops = nf->n.nhs;
1949
      }
1950
      else if (ipa_nonzero(nf->n.nhs->gw))
1951
      {
1952
        a0.dest = RTD_ROUTER;
1953
        a0.iface = nf->n.nhs->iface;
1954
        a0.gw = nf->n.nhs->gw;
1955
      }
1956
      else
1957
      {
1958
        a0.dest = RTD_DEVICE;
1959
        a0.iface = nf->n.nhs->iface;
1960
      }
1961

    
1962
      if (reload || ort_changed(nf, &a0))
1963
      {
1964
        net *ne = net_get(p->p.table, nf->fn.prefix, nf->fn.pxlen);
1965
        rta *a = rta_lookup(&a0);
1966
        rte *e = rte_get_temp(a);
1967

    
1968
        rta_free(nf->old_rta);
1969
        nf->old_rta = rta_clone(a);
1970
        e->u.ospf.metric1 = nf->old_metric1 = nf->n.metric1;
1971
        e->u.ospf.metric2 = nf->old_metric2 = nf->n.metric2;
1972
        e->u.ospf.tag = nf->old_tag = nf->n.tag;
1973
        e->u.ospf.router_id = nf->old_rid = nf->n.rid;
1974
        e->pflags = 0;
1975
        e->net = ne;
1976
        e->pref = p->p.preference;
1977

    
1978
        DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n",
1979
            a0.source, nf->fn.prefix, nf->fn.pxlen, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
1980
        rte_update(&p->p, ne, e);
1981
      }
1982
    }
1983
    else if (nf->old_rta)
1984
    {
1985
      /* Remove the route */
1986
      rta_free(nf->old_rta);
1987
      nf->old_rta = NULL;
1988

    
1989
      net *ne = net_get(p->p.table, nf->fn.prefix, nf->fn.pxlen);
1990
      rte_update(&p->p, ne, NULL);
1991
    }
1992

    
1993
    /* Remove unused rt entry, some special entries are persistent */
1994
    if (!nf->n.type && !nf->external_rte && !nf->area_net)
1995
    {
1996
      FIB_ITERATE_PUT(&fit, nftmp);
1997
      fib_delete(fib, nftmp);
1998
      goto again1;
1999
    }
2000
  }
2001
  FIB_ITERATE_END(nftmp);
2002

    
2003

    
2004
  WALK_LIST(oa, p->area_list)
2005
  {
2006
    /* Cleanup ASBR hash tables */
2007
    FIB_ITERATE_INIT(&fit, &oa->rtr);
2008
again2:
2009
    FIB_ITERATE_START(&oa->rtr, &fit, nftmp)
2010
    {
2011
      nf = (ort *) nftmp;
2012

    
2013
      if (!nf->n.type)
2014
      {
2015
        FIB_ITERATE_PUT(&fit, nftmp);
2016
        fib_delete(&oa->rtr, nftmp);
2017
        goto again2;
2018
      }
2019
    }
2020
    FIB_ITERATE_END(nftmp);
2021
  }
2022

    
2023
  /* Cleanup stale LSAs */
2024
  WALK_SLIST(en, p->lsal)
2025
    if (en->mode == LSA_M_STALE)
2026
      ospf_flush_lsa(p, en);
2027
}