Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (47.9 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 (net->pxlen > MAX_PREFIX_LENGTH)
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 (pxopts & OPT_PX_NU)
769
        continue;
770

    
771
      if (net.pxlen > MAX_PREFIX_LENGTH)
772
      {
773
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
774
            p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
775
        continue;
776
      }
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 (pxopts & OPT_PX_NU)
866
        continue;
867

    
868
      if (net.pxlen > MAX_PREFIX_LENGTH)
869
      {
870
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
871
            p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
872
        continue;
873
      }
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 *nf, *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, nftmp)
1166
  {
1167
    nf = (ort *) nftmp;
1168

    
1169
    if (nf->n.type && unresolved_vlink(nf))
1170
      reset_ri(nf);
1171
  }
1172
  FIB_WALK_END;
1173

    
1174

    
1175
  FIB_WALK(&p->rtf, nftmp)
1176
  {
1177
    nf = (ort *) nftmp;
1178

    
1179

    
1180
    /* RFC 2328 G.3 - incomplete resolution of virtual next hops - networks */
1181
    if (nf->n.type && unresolved_vlink(nf))
1182
      reset_ri(nf);
1183

    
1184

    
1185
    /* Compute condensed area networks */
1186
    if (nf->n.type == RTS_OSPF)
1187
    {
1188
      anet = (struct area_net *) fib_route(&nf->n.oa->net_fib, nf->fn.addr);
1189
      if (anet)
1190
      {
1191
        if (!anet->active)
1192
        {
1193
          anet->active = 1;
1194

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

    
1199
          /* 16.2. (3) */
1200
          if (nfi->n.type == RTS_OSPF_IA)
1201
            reset_ri(nfi);
1202
        }
1203

    
1204
        if (anet->metric < nf->n.metric1)
1205
          anet->metric = nf->n.metric1;
1206
      }
1207
    }
1208
  }
1209
  FIB_WALK_END;
1210

    
1211

    
1212
  if (ospf_is_v2(p))
1213
    net_fill_ip4(&default_net, IP4_NONE, 0);
1214
  else
1215
    net_fill_ip6(&default_net, IP6_NONE, 0);
1216

    
1217
  default_nf = fib_get(&p->rtf, &default_net);
1218
  default_nf->area_net = 1;
1219

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

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

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

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

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

    
1254

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

    
1262

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

    
1267

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

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

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

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

    
1287

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

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

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

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

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

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

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

    
1328
        oa->translate = TRANS_ON;
1329
      }
1330

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

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

    
1342

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

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

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

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

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

    
1373

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

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

    
1384

    
1385
/* Like fib_route(), but ignores dummy rt entries */
1386
static void *
1387
ospf_fib_route_ip4(struct fib *f, ip4_addr a, int len)
1388
{
1389
  net_addr_ip4 net = NET_ADDR_IP4(a, len);
1390
  ort *nf;
1391

    
1392
loop:
1393
  nf = fib_find(f, (net_addr *) &net);
1394
  if (nf && nf->n.type)
1395
    return nf;
1396

    
1397
  if (net.pxlen > 0)
1398
  {
1399
    net.pxlen--;
1400
    ip4_clrbit(&net.prefix, net.pxlen);
1401
    goto loop;
1402
  }
1403

    
1404
  return NULL;
1405
}
1406

    
1407
static void *
1408
ospf_fib_route_ip6(struct fib *f, ip6_addr a, int len)
1409
{
1410
  net_addr_ip6 net = NET_ADDR_IP6(a, len);
1411
  ort *nf;
1412

    
1413
loop:
1414
  nf = fib_find(f, (net_addr *) &net);
1415
  if (nf && nf->n.type)
1416
    return nf;
1417

    
1418
  if (net.pxlen > 0)
1419
  {
1420
    net.pxlen--;
1421
    ip6_clrbit(&net.prefix, net.pxlen);
1422
    goto loop;
1423
  }
1424

    
1425
  return NULL;
1426
}
1427

    
1428
static void *
1429
ospf_fib_route(struct fib *f, ip_addr a)
1430
{
1431
  if (ospf_is_v2(p))
1432
    return ospf_fib_route_ip4(f, ipa_to_ip4(a), IP4_MAX_PREFIX_LENGTH);
1433
  else
1434
    return ospf_fib_route_ip6(f, ipa_to_ip6(a), IP6_MAX_PREFIX_LENGTH);
1435
}
1436

    
1437

    
1438
/* RFC 2328 16.4. calculating external routes */
1439
static void
1440
ospf_ext_spf(struct ospf_proto *p)
1441
{
1442
  struct top_hash_entry *en;
1443
  struct ospf_lsa_ext_local rt;
1444
  ort *nf1, *nf2;
1445
  orta nfa = {};
1446
  u32 br_metric;
1447
  struct ospf_area *atmp;
1448

    
1449
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
1450

    
1451
  WALK_SLIST(en, p->lsal)
1452
  {
1453
    /* 16.4. (1) */
1454
    if ((en->lsa_type != LSA_T_EXT) && (en->lsa_type != LSA_T_NSSA))
1455
      continue;
1456

    
1457
    if (en->lsa.age == LSA_MAXAGE)
1458
      continue;
1459

    
1460
    /* 16.4. (2) */
1461
    if (en->lsa.rt == p->router_id)
1462
      continue;
1463

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

    
1467
    lsa_parse_ext(en, ospf_is_v2(p), &rt);
1468

    
1469
    if (rt.metric == LSINFINITY)
1470
      continue;
1471

    
1472
    if (rt.pxopts & OPT_PX_NU)
1473
      continue;
1474

    
1475
    if (rt.net.pxlen > MAX_PREFIX_LENGTH)
1476
    {
1477
      log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
1478
          p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
1479
      continue;
1480
    }
1481

    
1482

    
1483
    /* 16.4. (3) */
1484
    /* If there are more areas, we already precomputed preferred ASBR
1485
       entries in ospf_rt_abr1() and stored them in the backbone
1486
       table. For NSSA, we examine the area to which the LSA is assigned */
1487
    if (en->lsa_type == LSA_T_EXT)
1488
      atmp = ospf_main_area(p);
1489
    else /* NSSA */
1490
      atmp = ospf_find_area(p, en->domain);
1491

    
1492
    if (!atmp)
1493
      continue;                        /* Should not happen */
1494

    
1495
    net_addr_ip4 nrid = net_from_rid(en->lsa.rt);
1496
    nf1 = fib_find(&atmp->rtr, (net_addr *) &nrid);
1497

    
1498
    if (!nf1 || !nf1->n.type)
1499
      continue;                        /* No AS boundary router found */
1500

    
1501
    if (!(nf1->n.options & ORTA_ASBR))
1502
      continue;                        /* It is not ASBR */
1503

    
1504
    /* 16.4. (3) NSSA - special rule for default routes */
1505
    /* ABR should use default only if P-bit is set and summaries are active */
1506
    if ((en->lsa_type == LSA_T_NSSA) && (rt.net.pxlen == 0) &&
1507
        (p->areano > 1) && !(rt.propagate && atmp->ac->summary))
1508
      continue;
1509

    
1510
    if (!rt.fbit)
1511
    {
1512
      nf2 = nf1;
1513
      nfa.nhs = nf1->n.nhs;
1514
      br_metric = nf1->n.metric1;
1515
    }
1516
    else
1517
    {
1518
      nf2 = ospf_fib_route(&p->rtf, rt.fwaddr);
1519
      if (!nf2)
1520
        continue;
1521

    
1522
      if (en->lsa_type == LSA_T_EXT)
1523
      {
1524
        /* For ext routes, we accept intra-area or inter-area routes */
1525
        if ((nf2->n.type != RTS_OSPF) && (nf2->n.type != RTS_OSPF_IA))
1526
          continue;
1527
      }
1528
      else /* NSSA */
1529
      {
1530
        /* For NSSA routes, we accept just intra-area in the same area */
1531
        if ((nf2->n.type != RTS_OSPF) || (nf2->n.oa != atmp))
1532
          continue;
1533
      }
1534

    
1535
      /* Next-hop is a part of a configured stubnet */
1536
      if (!nf2->n.nhs)
1537
        continue;
1538

    
1539
      nfa.nhs = nf2->n.nhs;
1540
      br_metric = nf2->n.metric1;
1541

    
1542
      /* Replace device nexthops with nexthops to forwarding address from LSA */
1543
      if (has_device_nexthops(nfa.nhs))
1544
      {
1545
        nfa.nhs = fix_device_nexthops(p, nfa.nhs, rt.fwaddr);
1546
        nfa.nhs_reuse = 1;
1547
      }
1548
    }
1549

    
1550
    if (rt.ebit)
1551
    {
1552
      nfa.type = RTS_OSPF_EXT2;
1553
      nfa.metric1 = br_metric;
1554
      nfa.metric2 = rt.metric;
1555
    }
1556
    else
1557
    {
1558
      nfa.type = RTS_OSPF_EXT1;
1559
      nfa.metric1 = br_metric + rt.metric;
1560
      nfa.metric2 = LSINFINITY;
1561
    }
1562

    
1563
    /* Mark the LSA as reachable */
1564
    en->color = INSPF;
1565

    
1566
    /* Whether the route is preferred in route selection according to 16.4.1 */
1567
    nfa.options = epath_preferred(&nf2->n) ? ORTA_PREF : 0;
1568
    if (en->lsa_type == LSA_T_NSSA)
1569
    {
1570
      nfa.options |= ORTA_NSSA;
1571
      if (rt.propagate)
1572
        nfa.options |= ORTA_PROP;
1573
    }
1574

    
1575
    nfa.tag = rt.tag;
1576
    nfa.rid = en->lsa.rt;
1577
    nfa.oa = atmp; /* undefined in RFC 2328 */
1578
    nfa.en = en; /* store LSA for later (NSSA processing) */
1579

    
1580
    ri_install_ext(p, &rt.net, &nfa);
1581
  }
1582
}
1583

    
1584
/* Cleanup of routing tables and data */
1585
void
1586
ospf_rt_reset(struct ospf_proto *p)
1587
{
1588
  struct ospf_area *oa;
1589
  struct top_hash_entry *en;
1590
  struct area_net *anet;
1591
  ort *ri;
1592

    
1593
  /* Reset old routing table */
1594
  FIB_WALK(&p->rtf, nftmp)
1595
  {
1596
    ri = (ort *) nftmp;
1597
    ri->area_net = 0;
1598
    reset_ri(ri);
1599
  }
1600
  FIB_WALK_END;
1601

    
1602
  /* Reset SPF data in LSA db */
1603
  WALK_SLIST(en, p->lsal)
1604
  {
1605
    en->color = OUTSPF;
1606
    en->dist = LSINFINITY;
1607
    en->nhs = NULL;
1608
    en->lb = IPA_NONE;
1609

    
1610
    if (en->mode == LSA_M_RTCALC)
1611
      en->mode = LSA_M_STALE;
1612
  }
1613

    
1614
  WALK_LIST(oa, p->area_list)
1615
  {
1616
    /* Reset ASBR routing tables */
1617
    FIB_WALK(&oa->rtr, nftmp)
1618
    {
1619
      ri = (ort *) nftmp;
1620
      reset_ri(ri);
1621
    }
1622
    FIB_WALK_END;
1623

    
1624
    /* Reset condensed area networks */
1625
    if (p->areano > 1)
1626
    {
1627
      FIB_WALK(&oa->net_fib, nftmp)
1628
      {
1629
        anet = (struct area_net *) nftmp;
1630
        anet->active = 0;
1631
        anet->metric = 0;
1632
      }
1633
      FIB_WALK_END;
1634

    
1635
      FIB_WALK(&oa->enet_fib, nftmp)
1636
      {
1637
        anet = (struct area_net *) nftmp;
1638
        anet->active = 0;
1639
        anet->metric = 0;
1640
      }
1641
      FIB_WALK_END;
1642
    }
1643
  }
1644
}
1645

    
1646
/**
1647
 * ospf_rt_spf - calculate internal routes
1648
 * @p: OSPF protocol instance
1649
 *
1650
 * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
1651
 * It's based on Dijkstra's shortest path tree algorithms.
1652
 * This function is invoked from ospf_disp().
1653
 */
1654
void
1655
ospf_rt_spf(struct ospf_proto *p)
1656
{
1657
  struct ospf_area *oa;
1658

    
1659
  if (p->areano == 0)
1660
    return;
1661

    
1662
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
1663

    
1664
  /* 16. (1) */
1665
  ospf_rt_reset(p);
1666

    
1667
  /* 16. (2) */
1668
  WALK_LIST(oa, p->area_list)
1669
    ospf_rt_spfa(oa);
1670

    
1671
  /* 16. (3) */
1672
  ospf_rt_sum(ospf_main_area(p));
1673

    
1674
  /* 16. (4) */
1675
  WALK_LIST(oa, p->area_list)
1676
    if (oa->trcap && (oa->areaid != 0))
1677
      ospf_rt_sum_tr(oa);
1678

    
1679
  if (p->areano > 1)
1680
    ospf_rt_abr1(p);
1681

    
1682
  /* 16. (5) */
1683
  ospf_ext_spf(p);
1684

    
1685
  if (p->areano > 1)
1686
    ospf_rt_abr2(p);
1687

    
1688
  rt_sync(p);
1689
  lp_flush(p->nhpool);
1690

    
1691
  p->calcrt = 0;
1692
}
1693

    
1694

    
1695
static inline int
1696
inherit_nexthops(struct mpnh *pn)
1697
{
1698
  /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */
1699
  return pn && (ipa_nonzero(pn->gw) || !pn->iface);
1700
}
1701

    
1702
static struct mpnh *
1703
calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
1704
              struct top_hash_entry *par, int pos)
1705
{
1706
  struct ospf_proto *p = oa->po;
1707
  struct mpnh *pn = par->nhs;
1708
  struct ospf_iface *ifa;
1709
  u32 rid = en->lsa.rt;
1710

    
1711
  /* 16.1.1. The next hop calculation */
1712
  DBG("     Next hop calculating for id: %R rt: %R type: %u\n",
1713
      en->lsa.id, en->lsa.rt, en->lsa_type);
1714

    
1715
  /* Usually, we inherit parent nexthops */
1716
  if (inherit_nexthops(pn))
1717
    return pn;
1718

    
1719
  /*
1720
   * There are three cases:
1721
   * 1) en is a local network (and par is root)
1722
   * 2) en is a ptp or ptmp neighbor (and par is root)
1723
   * 3) en is a bcast or nbma neighbor (and par is local network)
1724
   */
1725

    
1726
  /* The first case - local network */
1727
  if ((en->lsa_type == LSA_T_NET) && (par == oa->rt))
1728
  {
1729
    ifa = rt_pos_to_ifa(oa, pos);
1730
    if (!ifa)
1731
      return NULL;
1732

    
1733
    return new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight);
1734
  }
1735

    
1736
  /* The second case - ptp or ptmp neighbor */
1737
  if ((en->lsa_type == LSA_T_RT) && (par == oa->rt))
1738
  {
1739
    ifa = rt_pos_to_ifa(oa, pos);
1740
    if (!ifa)
1741
      return NULL;
1742

    
1743
    if (ifa->type == OSPF_IT_VLINK)
1744
      return new_nexthop(p, IPA_NONE, NULL, 0);
1745

    
1746
    struct ospf_neighbor *m = find_neigh(ifa, rid);
1747
    if (!m || (m->state != NEIGHBOR_FULL))
1748
      return NULL;
1749

    
1750
    return new_nexthop(p, m->ip, ifa->iface, ifa->ecmp_weight);
1751
  }
1752

    
1753
  /* The third case - bcast or nbma neighbor */
1754
  if ((en->lsa_type == LSA_T_RT) && (par->lsa_type == LSA_T_NET))
1755
  {
1756
    /* par->nhi should be defined from parent's calc_next_hop() */
1757
    if (!pn)
1758
      goto bad;
1759

    
1760
    if (ospf_is_v2(p))
1761
    {
1762
      /*
1763
       * In this case, next-hop is the same as link-back, which is
1764
       * already computed in link_back().
1765
       */
1766
      if (ipa_zero(en->lb))
1767
        goto bad;
1768

    
1769
      return new_nexthop(p, en->lb, pn->iface, pn->weight);
1770
    }
1771
    else /* OSPFv3 */
1772
    {
1773
      /*
1774
       * Next-hop is taken from lladdr field of Link-LSA, en->lb_id
1775
       * is computed in link_back().
1776
       */
1777
      struct top_hash_entry *lhe;
1778
      lhe = ospf_hash_find(p->gr, pn->iface->index, en->lb_id, rid, LSA_T_LINK);
1779

    
1780
      if (!lhe)
1781
        return NULL;
1782

    
1783
      struct ospf_lsa_link *llsa = lhe->lsa_body;
1784

    
1785
      if (ip6_zero(llsa->lladdr))
1786
        return NULL;
1787

    
1788
      return new_nexthop(p, ipa_from_ip6(llsa->lladdr), pn->iface, pn->weight);
1789
    }
1790
  }
1791

    
1792
 bad:
1793
  /* Probably bug or some race condition, we log it */
1794
  log(L_ERR "%s: Unexpected case in next hop calculation", p->p.name);
1795
  return NULL;
1796
}
1797

    
1798

    
1799
/* Add LSA into list of candidates in Dijkstra's algorithm */
1800
static void
1801
add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
1802
         u32 dist, struct ospf_area *oa, int pos)
1803
{
1804
  struct ospf_proto *p = oa->po;
1805
  node *prev, *n;
1806
  int added = 0;
1807
  struct top_hash_entry *act;
1808

    
1809
  /* 16.1. (2b) */
1810
  if (en == NULL)
1811
    return;
1812
  if (en->lsa.age == LSA_MAXAGE)
1813
    return;
1814

    
1815
  if (ospf_is_v3(p) && (en->lsa_type == LSA_T_RT))
1816
  {
1817
    /* In OSPFv3, check V6 flag */
1818
    struct ospf_lsa_rt *rt = en->lsa_body;
1819
    if (!(rt->options & OPT_V6))
1820
      return;
1821
  }
1822

    
1823
  /* 16.1. (2c) */
1824
  if (en->color == INSPF)
1825
    return;
1826

    
1827
  /* 16.1. (2d), also checks that dist < LSINFINITY */
1828
  if (dist > en->dist)
1829
    return;
1830

    
1831
  /* We should check whether there is a reverse link from en to par, */
1832
  if (!link_back(oa, en, par))
1833
    return;
1834

    
1835
  struct mpnh *nhs = calc_next_hop(oa, en, par, pos);
1836
  if (!nhs)
1837
  {
1838
    log(L_WARN "%s: Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
1839
        p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
1840
    return;
1841
  }
1842

    
1843
  /* If en->dist > 0, we know that en->color == CANDIDATE and en->nhs is defined. */
1844
  if ((dist == en->dist) && !nh_is_vlink(en->nhs))
1845
  {
1846
    /*
1847
     * For multipath, we should merge nexthops. We merge regular nexthops only.
1848
     * Dummy vlink nexthops are less preferred and handled as a special case.
1849
     *
1850
     * During merging, new nexthops (nhs) can be reused if they are not
1851
     * inherited from the parent (i.e. they are allocated in calc_next_hop()).
1852
     * Current nexthops (en->nhs) can be reused if they weren't inherited in
1853
     * previous steps (that is stored in nhs_reuse, i.e. created by merging or
1854
     * allocated in calc_next_hop()).
1855
     *
1856
     * Generally, a node first inherits shared nexthops from its parent and
1857
     * later possibly gets reusable (private) copy during merging. This is more
1858
     * or less same for both top_hash_entry nodes and orta nodes.
1859
     *
1860
     * Note that when a child inherits a private nexthop from its parent, it
1861
     * should make the nexthop shared for both parent and child, while we only
1862
     * update nhs_reuse for the child node. This makes nhs_reuse field for the
1863
     * parent technically incorrect, but it is not a problem as parent's nhs
1864
     * will not be modified (and nhs_reuse examined) afterwards.
1865
     */
1866

    
1867
    /* Keep old ones */
1868
    if (!p->ecmp || nh_is_vlink(nhs) || (nhs == en->nhs))
1869
      return;
1870

    
1871
    /* Merge old and new */
1872
    int new_reuse = (par->nhs != nhs);
1873
    en->nhs = mpnh_merge(en->nhs, nhs, en->nhs_reuse, new_reuse, p->ecmp, p->nhpool);
1874
    en->nhs_reuse = 1;
1875
    return;
1876
  }
1877

    
1878
  DBG("     Adding candidate: rt: %R, id: %R, type: %u\n",
1879
      en->lsa.rt, en->lsa.id, en->lsa_type);
1880

    
1881
  if (en->color == CANDIDATE)
1882
  {                                /* We found a shorter path */
1883
    rem_node(&en->cn);
1884
  }
1885
  en->nhs = nhs;
1886
  en->dist = dist;
1887
  en->color = CANDIDATE;
1888
  en->nhs_reuse = (par->nhs != nhs);
1889

    
1890
  prev = NULL;
1891

    
1892
  if (EMPTY_LIST(*l))
1893
  {
1894
    add_head(l, &en->cn);
1895
  }
1896
  else
1897
  {
1898
    WALK_LIST(n, *l)
1899
    {
1900
      act = SKIP_BACK(struct top_hash_entry, cn, n);
1901
      if ((act->dist > dist) ||
1902
          ((act->dist == dist) && (act->lsa_type == LSA_T_RT)))
1903
      {
1904
        if (prev == NULL)
1905
          add_head(l, &en->cn);
1906
        else
1907
          insert_node(&en->cn, prev);
1908
        added = 1;
1909
        break;
1910
      }
1911
      prev = n;
1912
    }
1913

    
1914
    if (!added)
1915
    {
1916
      add_tail(l, &en->cn);
1917
    }
1918
  }
1919
}
1920

    
1921
static inline int
1922
ort_changed(ort *nf, rta *nr)
1923
{
1924
  rta *or = nf->old_rta;
1925
  return !or ||
1926
    (nf->n.metric1 != nf->old_metric1) || (nf->n.metric2 != nf->old_metric2) ||
1927
    (nf->n.tag != nf->old_tag) || (nf->n.rid != nf->old_rid) ||
1928
    (nr->source != or->source) || (nr->dest != or->dest) ||
1929
    (nr->iface != or->iface) || !ipa_equal(nr->gw, or->gw) ||
1930
    !mpnh_same(nr->nexthops, or->nexthops);
1931
}
1932

    
1933
static void
1934
rt_sync(struct ospf_proto *p)
1935
{
1936
  struct top_hash_entry *en;
1937
  struct fib_iterator fit;
1938
  struct fib *fib = &p->rtf;
1939
  ort *nf;
1940
  struct ospf_area *oa;
1941

    
1942
  /* This is used for forced reload of routes */
1943
  int reload = (p->calcrt == 2);
1944

    
1945
  OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation");
1946

    
1947
  DBG("Now syncing my rt table with nest's\n");
1948
  FIB_ITERATE_INIT(&fit, fib);
1949
again1:
1950
  FIB_ITERATE_START(fib, &fit, nftmp)
1951
  {
1952
    nf = (ort *) nftmp;
1953

    
1954
    /* Sanity check of next-hop addresses, failure should not happen */
1955
    if (nf->n.type)
1956
    {
1957
      struct mpnh *nh;
1958
      for (nh = nf->n.nhs; nh; nh = nh->next)
1959
        if (ipa_nonzero(nh->gw))
1960
        {
1961
          neighbor *ng = neigh_find2(&p->p, &nh->gw, nh->iface, 0);
1962
          if (!ng || (ng->scope == SCOPE_HOST))
1963
            { reset_ri(nf); break; }
1964
        }
1965
    }
1966

    
1967
    /* Remove configured stubnets */
1968
    if (!nf->n.nhs)
1969
      reset_ri(nf);
1970

    
1971
    if (nf->n.type) /* Add the route */
1972
    {
1973
      rta a0 = {
1974
        .src = p->p.main_source,
1975
        .source = nf->n.type,
1976
        .scope = SCOPE_UNIVERSE,
1977
        .cast = RTC_UNICAST
1978
      };
1979

    
1980
      if (nf->n.nhs->next)
1981
      {
1982
        a0.dest = RTD_MULTIPATH;
1983
        a0.nexthops = nf->n.nhs;
1984
      }
1985
      else if (ipa_nonzero(nf->n.nhs->gw))
1986
      {
1987
        a0.dest = RTD_ROUTER;
1988
        a0.iface = nf->n.nhs->iface;
1989
        a0.gw = nf->n.nhs->gw;
1990
      }
1991
      else
1992
      {
1993
        a0.dest = RTD_DEVICE;
1994
        a0.iface = nf->n.nhs->iface;
1995
      }
1996

    
1997
      if (reload || ort_changed(nf, &a0))
1998
      {
1999
        net *ne = net_get(p->p.table, nf->fn.addr);
2000
        rta *a = rta_lookup(&a0);
2001
        rte *e = rte_get_temp(a);
2002

    
2003
        rta_free(nf->old_rta);
2004
        nf->old_rta = rta_clone(a);
2005
        e->u.ospf.metric1 = nf->old_metric1 = nf->n.metric1;
2006
        e->u.ospf.metric2 = nf->old_metric2 = nf->n.metric2;
2007
        e->u.ospf.tag = nf->old_tag = nf->n.tag;
2008
        e->u.ospf.router_id = nf->old_rid = nf->n.rid;
2009
        e->pflags = 0;
2010
        e->net = ne;
2011
        e->pref = p->p.preference;
2012

    
2013
        DBG("Mod rte type %d - %N via %I on iface %s, met %d\n",
2014
            a0.source, nf->fn.addr, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
2015
        rte_update(&p->p, ne, e);
2016
      }
2017
    }
2018
    else if (nf->old_rta)
2019
    {
2020
      /* Remove the route */
2021
      rta_free(nf->old_rta);
2022
      nf->old_rta = NULL;
2023

    
2024
      net *ne = net_get(p->p.table, nf->fn.addr);
2025
      rte_update(&p->p, ne, NULL);
2026
    }
2027

    
2028
    /* Remove unused rt entry, some special entries are persistent */
2029
    if (!nf->n.type && !nf->external_rte && !nf->area_net)
2030
    {
2031
      FIB_ITERATE_PUT(&fit, nftmp);
2032
      fib_delete(fib, nftmp);
2033
      goto again1;
2034
    }
2035
  }
2036
  FIB_ITERATE_END(nftmp);
2037

    
2038

    
2039
  WALK_LIST(oa, p->area_list)
2040
  {
2041
    /* Cleanup ASBR hash tables */
2042
    FIB_ITERATE_INIT(&fit, &oa->rtr);
2043
again2:
2044
    FIB_ITERATE_START(&oa->rtr, &fit, nftmp)
2045
    {
2046
      nf = (ort *) nftmp;
2047

    
2048
      if (!nf->n.type)
2049
      {
2050
        FIB_ITERATE_PUT(&fit, nftmp);
2051
        fib_delete(&oa->rtr, nftmp);
2052
        goto again2;
2053
      }
2054
    }
2055
    FIB_ITERATE_END(nftmp);
2056
  }
2057

    
2058
  /* Cleanup stale LSAs */
2059
  WALK_SLIST(en, p->lsal)
2060
    if (en->mode == LSA_M_STALE)
2061
      ospf_flush_lsa(p, en);
2062
}