Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (48.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
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
static inline struct mpnh *
57
copy_nexthop(struct ospf_proto *p, const struct mpnh *src)
58
{
59
  struct mpnh *nh = lp_alloc(p->nhpool, sizeof(struct mpnh));
60
  nh->gw = src->gw;
61
  nh->iface = src->iface;
62
  nh->next = NULL;
63
  nh->weight = src->weight;
64
  return nh;
65
}
66

    
67
/* Compare nexthops during merge.
68
   We need to maintain nhs sorted to eliminate duplicities */
69
static int
70
cmp_nhs(struct mpnh *s1, struct mpnh *s2)
71
{
72
  int r;
73

    
74
  if (!s1)
75
    return 1;
76

    
77
  if (!s2)
78
    return -1;
79

    
80
  r = ((int) s2->weight) - ((int) s1->weight);
81
  if (r)
82
    return r;
83

    
84
  r = ipa_compare(s1->gw, s2->gw);
85
  if (r)
86
    return r;
87

    
88
  return ((int) s1->iface->index) - ((int) s2->iface->index);
89
}
90

    
91
static struct mpnh *
92
merge_nexthops(struct ospf_proto *p, struct mpnh *s1, struct mpnh *s2, int r1, int r2)
93
{
94
  struct mpnh *root = NULL;
95
  struct mpnh **n = &root;
96
  int count = p->ecmp;
97

    
98
  ASSERT(p->ecmp);
99

    
100
  /*
101
   * r1, r2 signalize whether we can reuse nexthops from s1, s2.
102
   * New nexthops (s2, new) can be reused if they are not inherited
103
   * from the parent (i.e. it is allocated in calc_next_hop()).
104
   * Current nexthops (s1, en->nhs) can be reused if they weren't
105
   * inherited in previous steps (that is stored in nhs_reuse,
106
   * i.e. created by merging or allocalted in calc_next_hop()).
107
   *
108
   * Generally, a node first inherits shared nexthops from its
109
   * parent and later possibly gets reusable copy during merging.
110
   */
111

    
112
  while ((s1 || s2) && count--)
113
  {
114
    int cmp = cmp_nhs(s1, s2);
115
    if (cmp < 0)
116
    {
117
      *n = r1 ? s1 : copy_nexthop(p, s1);
118
      s1 = s1->next;
119
    }
120
    else if (cmp > 0)
121
    {
122
      *n = r2 ? s2 : copy_nexthop(p, s2);
123
      s2 = s2->next;
124
    }
125
    else
126
    {
127
      *n = r1 ? s1 : (r2 ? s2 : copy_nexthop(p, s1));
128
      s1 = s1->next;
129
      s2 = s2->next;
130
    }
131
    n = &((*n)->next);
132
  }
133
  *n = NULL;
134

    
135
  return root;
136
}
137

    
138
/* Returns true if there are device nexthops in n */
139
static inline int
140
has_device_nexthops(const struct mpnh *n)
141
{
142
  for (; n; n = n->next)
143
    if (ipa_zero(n->gw))
144
      return 1;
145

    
146
  return 0;
147
}
148

    
149
/* Replace device nexthops with nexthops to gw */
150
static struct mpnh *
151
fix_device_nexthops(struct ospf_proto *p, const struct mpnh *n, ip_addr gw)
152
{
153
  struct mpnh *root1 = NULL;
154
  struct mpnh *root2 = NULL;
155
  struct mpnh **nn1 = &root1;
156
  struct mpnh **nn2 = &root2;
157

    
158
  if (!p->ecmp)
159
    return new_nexthop(p, gw, n->iface, n->weight);
160

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

    
165
  for (; n; n = n->next)
166
  {
167
    struct mpnh *nn = new_nexthop(p, ipa_zero(n->gw) ? gw : n->gw, n->iface, n->weight);
168

    
169
    if (ipa_zero(n->gw))
170
    {
171
      *nn1 = nn;
172
      nn1 = &(nn->next);
173
    }
174
    else
175
    {
176
      *nn2 = nn;
177
      nn2 = &(nn->next);
178
    }
179
  }
180

    
181
  return merge_nexthops(p, root1, root2, 1, 1);
182
}
183

    
184

    
185
/* Whether the ASBR or the forward address destination is preferred
186
   in AS external route selection according to 16.4.1. */
187
static inline int
188
epath_preferred(const orta *ep)
189
{
190
  return (ep->type == RTS_OSPF) && (ep->oa->areaid != 0);
191
}
192

    
193
/* Whether the ext route has ASBR/next_hop marked as preferred. */
194
static inline int
195
orta_pref(const orta *nf)
196
{
197
  return !!(nf->options & ORTA_PREF);
198
}
199

    
200
/* Classify orta entries according to RFC 3101 2.5 (6e) priorities:
201
   Type-7 LSA with P-bit, Type-5 LSA, Type-7 LSA without P-bit */
202
static int
203
orta_prio(const orta *nf)
204
{
205
  /* RFC 3103 2.5 (6e) priorities */
206
  u32 opts = nf->options & (ORTA_NSSA | ORTA_PROP);
207

    
208
  /* A Type-7 LSA with the P-bit set */
209
  if (opts == (ORTA_NSSA | ORTA_PROP))
210
    return 2;
211

    
212
  /* A Type-5 LSA */
213
  if (opts == 0)
214
    return 1;
215

    
216
  return 0;
217
}
218

    
219
/* Whether the route is better according to RFC 3101 2.5 (6e):
220
   Prioritize Type-7 LSA with P-bit, then Type-5 LSA, then higher router ID */
221
static int
222
orta_prefer_lsa(const orta *new, const orta *old)
223
{
224
  int pn = orta_prio(new);
225
  int po = orta_prio(old);
226

    
227
  return (pn > po) || ((pn == po) && (new->en->lsa.rt > old->en->lsa.rt));
228
}
229

    
230
/*
231
 * Compare an existing routing table entry with a new one. Applicable for
232
 * intra-area routes, inter-area routes and router entries. Returns integer
233
 * <, = or > than 0 if the new orta is less, equal or more preferred than
234
 * the old orta.
235
 */
236
static int
237
orta_compare(const struct ospf_proto *p, const orta *new, const orta *old)
238
{
239
  int r;
240

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

    
244
  /* Prefer intra-area to inter-area to externals */
245
  r = ((int) old->type) - ((int) new->type);
246
  if (r) return r;
247

    
248
  /* Prefer lowest type 1 metric */
249
  r = ((int) old->metric1) - ((int) new->metric1);
250
  if (r) return r;
251

    
252

    
253
  /* Rest is BIRD-specific */
254

    
255
  /* Area-wide routes should not mix next-hops from different areas.
256
     This generally should not happen unless there is some misconfiguration. */
257
  if (new->oa->areaid != old->oa->areaid)
258
    return (new->oa->areaid > old->oa->areaid) ? 1 : -1;
259

    
260
  /* Prefer routes for configured stubnets (!nhs) to regular routes to dummy
261
     vlink nexthops. We intentionally return -1 if both are stubnets or vlinks. */
262
  if (!old->nhs)
263
    return -1;
264
  if (!new->nhs)
265
    return 1;
266
  if (nh_is_vlink(new->nhs))
267
    return -1;
268
  if (nh_is_vlink(old->nhs))
269
    return 1;
270

    
271

    
272
  if (p->ecmp)
273
    return 0;
274

    
275
  /* Prefer routes with higher Router ID, just to be more deterministic */
276
  if (new->rid > old->rid)
277
    return 1;
278

    
279
  return -1;
280
}
281

    
282
/*
283
 * Compare ASBR routing table entry with a new one, used for precompute ASBRs
284
 * for AS external route selection (RFC 2328 16.4 (3)), Returns integer < or >
285
 * than 0 if the new ASBR is less or more preferred than the old ASBR.
286
 */
287
static int
288
orta_compare_asbr(const struct ospf_proto *p, const orta *new, const orta *old)
289
{
290
  int r;
291

    
292
  if (old->type == RTS_DUMMY)
293
    return 1;
294

    
295
  if (!p->rfc1583)
296
  {
297
    r = epath_preferred(new) - epath_preferred(old);
298
    if (r) return r;
299
  }
300

    
301
  r = ((int) old->metric1) - ((int) new->metric1);
302
  if (r) return r;
303

    
304
  /* Larger area ID is preferred */
305
  if (new->oa->areaid > old->oa->areaid)
306
    return 1;
307

    
308
  /* There is just one ASBR of that RID per area, so tie is not possible */
309
  return -1;
310
}
311

    
312
/*
313
 * Compare a routing table entry with a new one, for AS external routes
314
 * (RFC 2328 16.4) and NSSA routes (RFC 3103 2.5), Returns integer <, = or >
315
 * than 0 if the new orta is less, equal or more preferred than the old orta.
316
 */
317
static int
318
orta_compare_ext(const struct ospf_proto *p, const orta *new, const orta *old)
319
{
320
  int r;
321

    
322
  if (old->type == RTS_DUMMY)
323
    return 1;
324

    
325
  /* 16.4 (6a) - prefer routes with lower type */
326
  r = ((int) old->type) - ((int) new->type);
327
  if (r) return r;
328

    
329
  /* 16.4 (6b) - prefer routes with lower type 2 metric */
330
  if (new->type == RTS_OSPF_EXT2)
331
  {
332
    r = ((int) old->metric2) - ((int) new->metric2);
333
    if (r) return r;
334
  }
335

    
336
  /* 16.4 (6c) - if not RFC1583, prefer routes with preferred ASBR/next_hop */
337
  if (!p->rfc1583)
338
  {
339
    r = orta_pref(new) - orta_pref(old);
340
    if (r) return r;
341
  }
342

    
343
  /* 16.4 (6d) - prefer routes with lower type 1 metric */
344
  r = ((int) old->metric1) - ((int) new->metric1);
345
  if (r) return r;
346

    
347

    
348
  if (p->ecmp && p->merge_external)
349
    return 0;
350

    
351
  /*
352
   * RFC 3101 2.5 (6e) - prioritize Type-7 LSA with P-bit, then Type-5 LSA, then
353
   * LSA with higher router ID. Although this should apply just to functionally
354
   * equivalent LSAs (i.e. ones with the same non-zero forwarding address), we
355
   * use it also to disambiguate otherwise equally preferred nexthops.
356
   */
357
  if (orta_prefer_lsa(new, old))
358
    return 1;
359

    
360
  return -1;
361
}
362

    
363

    
364
static inline void
365
ort_replace(ort *o, const orta *new)
366
{
367
  memcpy(&o->n, new, sizeof(orta));
368
}
369

    
370
static void
371
ort_merge(struct ospf_proto *p, ort *o, const orta *new)
372
{
373
  orta *old = &o->n;
374

    
375
  if (old->nhs != new->nhs)
376
  {
377
    old->nhs = merge_nexthops(p, old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse);
378
    old->nhs_reuse = 1;
379
  }
380

    
381
  if (old->rid < new->rid)
382
    old->rid = new->rid;
383
}
384

    
385
static void
386
ort_merge_ext(struct ospf_proto *p, ort *o, const orta *new)
387
{
388
  orta *old = &o->n;
389

    
390
  if (old->nhs != new->nhs)
391
  {
392
    old->nhs = merge_nexthops(p, old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse);
393
    old->nhs_reuse = 1;
394
  }
395

    
396
  if (old->tag != new->tag)
397
    old->tag = 0;
398

    
399
  /*
400
   * Even with multipath, we store only one LSA in orta.en for the purpose of
401
   * NSSA/ext translation. Therefore, we apply procedures from RFC 3101 2.5 (6e)
402
   * to all chosen LSAs for given network, not just to functionally equivalent
403
   * ones (i.e. ones with the same non-zero forwarding address).
404
   */
405
  if (orta_prefer_lsa(new, old))
406
  {
407
    old->options = new->options;
408
    old->rid = new->rid;
409
    old->oa = new->oa;
410
    old->en = new->en;
411
  }
412
}
413

    
414

    
415

    
416
static inline void
417
ri_install_net(struct ospf_proto *p, ip_addr prefix, int pxlen, const orta *new)
418
{
419
  ort *old = (ort *) fib_get(&p->rtf, &prefix, pxlen);
420
  int cmp = orta_compare(p, new, &old->n);
421

    
422
  if (cmp > 0)
423
    ort_replace(old, new);
424
  else if (cmp == 0)
425
    ort_merge(p, old, new);
426
}
427

    
428
static inline void
429
ri_install_rt(struct ospf_area *oa, u32 rid, const orta *new)
430
{
431
  ip_addr addr = ipa_from_rid(rid);
432
  ort *old = (ort *) fib_get(&oa->rtr, &addr, MAX_PREFIX_LENGTH);
433
  int cmp = orta_compare(oa->po, new, &old->n);
434

    
435
  if (cmp > 0)
436
    ort_replace(old, new);
437
  else if (cmp == 0)
438
    ort_merge(oa->po, old, new);
439
}
440

    
441
static inline void
442
ri_install_asbr(struct ospf_proto *p, ip_addr *addr, const orta *new)
443
{
444
  ort *old = (ort *) fib_get(&p->backbone->rtr, addr, MAX_PREFIX_LENGTH);
445
  if (orta_compare_asbr(p, new, &old->n) > 0)
446
    ort_replace(old, new);
447
}
448

    
449
static inline void
450
ri_install_ext(struct ospf_proto *p, ip_addr prefix, int pxlen, const orta *new)
451
{
452
  ort *old = (ort *) fib_get(&p->rtf, &prefix, pxlen);
453
  int cmp = orta_compare_ext(p, new, &old->n);
454

    
455
  if (cmp > 0)
456
    ort_replace(old, new);
457
  else if (cmp == 0)
458
    ort_merge_ext(p, old, new);
459
}
460

    
461
static inline struct ospf_iface *
462
rt_pos_to_ifa(struct ospf_area *oa, int pos)
463
{
464
  struct ospf_iface *ifa;
465

    
466
  WALK_LIST(ifa, oa->po->iface_list)
467
    if (ifa->oa == oa && pos >= ifa->rt_pos_beg && pos < ifa->rt_pos_end)
468
      return ifa;
469

    
470
  return NULL;
471
}
472

    
473
static inline struct ospf_iface *
474
px_pos_to_ifa(struct ospf_area *oa, int pos)
475
{
476
  struct ospf_iface *ifa;
477

    
478
  WALK_LIST(ifa, oa->po->iface_list)
479
    if (ifa->oa == oa && pos >= ifa->px_pos_beg && pos < ifa->px_pos_end)
480
      return ifa;
481

    
482
  return NULL;
483
}
484

    
485

    
486
static void
487
add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en, int pos)
488
{
489
  struct ospf_proto *p = oa->po;
490

    
491
  orta nf = {
492
    .type = RTS_OSPF,
493
    .options = 0,
494
    .metric1 = metric,
495
    .metric2 = LSINFINITY,
496
    .tag = 0,
497
    .rid = en->lsa.rt,
498
    .oa = oa,
499
    .nhs = en->nhs
500
  };
501

    
502
  if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
503
  {
504
    log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
505
        p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
506
    return;
507
  }
508

    
509
  if (en == oa->rt)
510
  {
511
    /*
512
     * Local stub networks does not have proper iface in en->nhi
513
     * (because they all have common top_hash_entry en).
514
     * We have to find iface responsible for that stub network.
515
     * Configured stubnets does not have any iface. They will
516
     * be removed in rt_sync().
517
     */
518

    
519
    struct ospf_iface *ifa;
520
    ifa = ospf_is_v2(p) ? rt_pos_to_ifa(oa, pos) : px_pos_to_ifa(oa, pos);
521
    nf.nhs = ifa ? new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight) : NULL;
522
  }
523

    
524
  ri_install_net(p, px, pxlen, &nf);
525
}
526

    
527

    
528

    
529
static inline void
530
spfa_process_rt(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
531
{
532
  struct ospf_lsa_rt *rt = act->lsa_body;
533
  struct ospf_lsa_rt_walk rtl;
534
  struct top_hash_entry *tmp;
535
  ip_addr prefix;
536
  int pxlen, i;
537

    
538
  if (rt->options & OPT_RT_V)
539
    oa->trcap = 1;
540

    
541
  /*
542
   * In OSPFv3, all routers are added to per-area routing
543
   * tables. But we use it just for ASBRs and ABRs. For the
544
   * purpose of the last step in SPF - prefix-LSA processing in
545
   * spfa_process_prefixes(), we use information stored in LSA db.
546
   */
547
  if (((rt->options & OPT_RT_E) || (rt->options & OPT_RT_B))
548
      && (act->lsa.rt != p->router_id))
549
  {
550
    orta nf = {
551
      .type = RTS_OSPF,
552
      .options = rt->options,
553
      .metric1 = act->dist,
554
      .metric2 = LSINFINITY,
555
      .tag = 0,
556
      .rid = act->lsa.rt,
557
      .oa = oa,
558
      .nhs = act->nhs
559
    };
560
    ri_install_rt(oa, act->lsa.rt, &nf);
561
  }
562

    
563
  /* Errata 2078 to RFC 5340 4.8.1 - skip links from non-routing nodes */
564
  if (ospf_is_v3(p) && (act != oa->rt) && !(rt->options & OPT_R))
565
    return;
566

    
567
  /* Now process Rt links */
568
  for (lsa_walk_rt_init(p, act, &rtl), i = 0; lsa_walk_rt(&rtl); i++)
569
  {
570
    tmp = NULL;
571

    
572
    switch (rtl.type)
573
    {
574
    case LSART_STUB:
575

    
576
      /* Should not happen, LSART_STUB is not defined in OSPFv3 */
577
      if (ospf_is_v3(p))
578
        break;
579

    
580
      /*
581
       * RFC 2328 in 16.1. (2a) says to handle stub networks in an
582
       * second phase after the SPF for an area is calculated. We get
583
       * the same result by handing them here because add_network()
584
       * will keep the best (not the first) found route.
585
       */
586
      prefix = ipa_from_u32(rtl.id & rtl.data);
587
      pxlen = u32_masklen(rtl.data);
588
      add_network(oa, prefix, pxlen, act->dist + rtl.metric, act, i);
589
      break;
590

    
591
    case LSART_NET:
592
      tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
593
      break;
594

    
595
    case LSART_VLNK:
596
    case LSART_PTP:
597
      tmp = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
598
      break;
599
    }
600

    
601
    add_cand(&oa->cand, tmp, act, act->dist + rtl.metric, oa, i);
602
  }
603
}
604

    
605
static inline void
606
spfa_process_net(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
607
{
608
  struct ospf_lsa_net *ln = act->lsa_body;
609
  struct top_hash_entry *tmp;
610
  ip_addr prefix;
611
  int pxlen, i, cnt;
612

    
613
  if (ospf_is_v2(p))
614
  {
615
    prefix = ipa_from_u32(act->lsa.id & ln->optx);
616
    pxlen = u32_masklen(ln->optx);
617
    add_network(oa, prefix, pxlen, act->dist, act, -1);
618
  }
619

    
620
  cnt = lsa_net_count(&act->lsa);
621
  for (i = 0; i < cnt; i++)
622
  {
623
    tmp = ospf_hash_find_rt(p->gr, oa->areaid, ln->routers[i]);
624
    add_cand(&oa->cand, tmp, act, act->dist, oa, -1);
625
  }
626
}
627

    
628
static inline void
629
spfa_process_prefixes(struct ospf_proto *p, struct ospf_area *oa)
630
{
631
  struct top_hash_entry *en, *src;
632
  struct ospf_lsa_prefix *px;
633
  ip_addr pxa;
634
  int pxlen;
635
  u8 pxopts;
636
  u16 metric;
637
  u32 *buf;
638
  int i;
639

    
640
  WALK_SLIST(en, p->lsal)
641
  {
642
    if (en->lsa_type != LSA_T_PREFIX)
643
      continue;
644

    
645
    if (en->domain != oa->areaid)
646
      continue;
647

    
648
    if (en->lsa.age == LSA_MAXAGE)
649
      continue;
650

    
651
    px = en->lsa_body;
652

    
653
    /* For router prefix-LSA, we would like to find the first router-LSA */
654
    if (px->ref_type == LSA_T_RT)
655
      src = ospf_hash_find_rt(p->gr, oa->areaid, px->ref_rt);
656
    else
657
      src = ospf_hash_find(p->gr, oa->areaid, px->ref_id, px->ref_rt, px->ref_type);
658

    
659
    if (!src)
660
      continue;
661

    
662
    /* Reachable in SPF */
663
    if (src->color != INSPF)
664
      continue;
665

    
666
    if ((src->lsa_type != LSA_T_RT) && (src->lsa_type != LSA_T_NET))
667
      continue;
668

    
669
    buf = px->rest;
670
    for (i = 0; i < px->pxcount; i++)
671
      {
672
        buf = lsa_get_ipv6_prefix(buf, &pxa, &pxlen, &pxopts, &metric);
673

    
674
        if (pxopts & OPT_PX_NU)
675
          continue;
676

    
677
        /* Store the first global address to use it later as a vlink endpoint */
678
        if ((pxopts & OPT_PX_LA) && ipa_zero(src->lb))
679
          src->lb = pxa;
680

    
681
        add_network(oa, pxa, pxlen, src->dist + metric, src, i);
682
      }
683
  }
684
}
685

    
686
/* RFC 2328 16.1. calculating shortest paths for an area */
687
static void
688
ospf_rt_spfa(struct ospf_area *oa)
689
{
690
  struct ospf_proto *p = oa->po;
691
  struct top_hash_entry *act;
692
  node *n;
693

    
694
  if (oa->rt == NULL)
695
    return;
696
  if (oa->rt->lsa.age == LSA_MAXAGE)
697
    return;
698

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

    
701
  /* 16.1. (1) */
702
  init_list(&oa->cand);                /* Empty list of candidates */
703
  oa->trcap = 0;
704

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

    
707
  oa->rt->dist = 0;
708
  oa->rt->color = CANDIDATE;
709
  add_head(&oa->cand, &oa->rt->cn);
710
  DBG("RT LSA: rt: %R, id: %R, type: %u\n",
711
      oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa_type);
712

    
713
  while (!EMPTY_LIST(oa->cand))
714
  {
715
    n = HEAD(oa->cand);
716
    act = SKIP_BACK(struct top_hash_entry, cn, n);
717
    rem_node(n);
718

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

    
722
    act->color = INSPF;
723
    switch (act->lsa_type)
724
    {
725
    case LSA_T_RT:
726
      spfa_process_rt(p, oa, act);
727
      break;
728

    
729
    case LSA_T_NET:
730
      spfa_process_net(p, oa, act);
731
      break;
732

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

    
738
  if (ospf_is_v3(p))
739
    spfa_process_prefixes(p, oa);
740
}
741

    
742
static int
743
link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par)
744
{
745
  struct ospf_proto *p = oa->po;
746
  struct ospf_lsa_rt_walk rtl;
747
  struct top_hash_entry *tmp;
748
  struct ospf_lsa_net *ln;
749
  u32 i, cnt;
750

    
751
  if (!en || !par) return 0;
752

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

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

    
763
  en->lb = IPA_NONE;
764
  en->lb_id = 0;
765

    
766
  switch (en->lsa_type)
767
  {
768
  case LSA_T_RT:
769
    lsa_walk_rt_init(p, en, &rtl);
770
    while (lsa_walk_rt(&rtl))
771
    {
772
      switch (rtl.type)
773
      {
774
      case LSART_STUB:
775
        break;
776

    
777
      case LSART_NET:
778
        tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
779
        if (tmp == par)
780
        {
781
          if (ospf_is_v2(p))
782
            en->lb = ipa_from_u32(rtl.data);
783
          else
784
            en->lb_id = rtl.lif;
785

    
786
          return 1;
787
        }
788
        break;
789

    
790
      case LSART_VLNK:
791
      case LSART_PTP:
792
        /* Not necessary the same link, see RFC 2328 [23] */
793
        tmp = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
794
        if (tmp == par)
795
          return 1;
796
        break;
797
      }
798
    }
799
    break;
800

    
801
  case LSA_T_NET:
802
    ln = en->lsa_body;
803
    cnt = lsa_net_count(&en->lsa);
804
    for (i = 0; i < cnt; i++)
805
    {
806
      tmp = ospf_hash_find_rt(p->gr, oa->areaid, ln->routers[i]);
807
      if (tmp == par)
808
        return 1;
809
    }
810
    break;
811

    
812
  default:
813
    log(L_WARN "%s: Unknown LSA type in SPF: %d", p->p.name, en->lsa_type);
814
  }
815
  return 0;
816
}
817

    
818

    
819
/* RFC 2328 16.2. calculating inter-area routes */
820
static void
821
ospf_rt_sum(struct ospf_area *oa)
822
{
823
  struct ospf_proto *p = oa->po;
824
  struct top_hash_entry *en;
825
  ip_addr ip, abrip;
826
  u32 dst_rid, metric, options;
827
  ort *abr;
828
  int pxlen = -1, type = -1;
829
  u8 pxopts;
830

    
831

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

    
834
  WALK_SLIST(en, p->lsal)
835
  {
836
    if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
837
      continue;
838

    
839
    if (en->domain != oa->areaid)
840
      continue;
841

    
842
    /* 16.2. (1a) */
843
    if (en->lsa.age == LSA_MAXAGE)
844
      continue;
845

    
846
    /* 16.2. (2) */
847
    if (en->lsa.rt == p->router_id)
848
      continue;
849

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

    
852
    if (en->lsa_type == LSA_T_SUM_NET)
853
    {
854
      lsa_parse_sum_net(en, ospf_is_v2(p), &ip, &pxlen, &pxopts, &metric);
855

    
856
      if (pxopts & OPT_PX_NU)
857
        continue;
858

    
859
      if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
860
      {
861
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
862
            p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
863
        continue;
864
      }
865

    
866
      options = 0;
867
      type = ORT_NET;
868
    }
869
    else /* LSA_T_SUM_RT */
870
    {
871
      lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);
872

    
873
      /* We don't want local router in ASBR routing table */
874
      if (dst_rid == p->router_id)
875
        continue;
876

    
877
      options |= ORTA_ASBR;
878
      type = ORT_ROUTER;
879
    }
880

    
881
    /* 16.2. (1b) */
882
    if (metric == LSINFINITY)
883
      continue;
884

    
885
    /* 16.2. (4) */
886
    abrip = ipa_from_rid(en->lsa.rt);
887
    abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
888
    if (!abr || !abr->n.type)
889
      continue;
890

    
891
    if (!(abr->n.options & ORTA_ABR))
892
      continue;
893

    
894
    /* This check is not mentioned in RFC 2328 */
895
    if (abr->n.type != RTS_OSPF)
896
      continue;
897

    
898
    /* 16.2. (5) */
899
    orta nf = {
900
      .type = RTS_OSPF_IA,
901
      .options = options,
902
      .metric1 = abr->n.metric1 + metric,
903
      .metric2 = LSINFINITY,
904
      .tag = 0,
905
      .rid = en->lsa.rt, /* ABR ID */
906
      .oa = oa,
907
      .nhs = abr->n.nhs
908
    };
909

    
910
    if (type == ORT_NET)
911
      ri_install_net(p, ip, pxlen, &nf);
912
    else
913
      ri_install_rt(oa, dst_rid, &nf);
914
  }
915
}
916

    
917
/* RFC 2328 16.3. examining summary-LSAs in transit areas */
918
static void
919
ospf_rt_sum_tr(struct ospf_area *oa)
920
{
921
  struct ospf_proto *p = oa->po;
922
  struct ospf_area *bb = p->backbone;
923
  struct top_hash_entry *en;
924
  ort *re, *abr;
925
  ip_addr ip, abrip;
926
  u32 dst_rid, metric, options;
927
  int pxlen;
928
  u8 pxopts;
929

    
930

    
931
  if (!bb)
932
    return;
933

    
934
  WALK_SLIST(en, p->lsal)
935
  {
936
    if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
937
      continue;
938

    
939
    if (en->domain != oa->areaid)
940
      continue;
941

    
942
    /* 16.3 (1a) */
943
    if (en->lsa.age == LSA_MAXAGE)
944
      continue;
945

    
946
    /* 16.3 (2) */
947
    if (en->lsa.rt == p->router_id)
948
      continue;
949

    
950
    if (en->lsa_type == LSA_T_SUM_NET)
951
    {
952
      lsa_parse_sum_net(en, ospf_is_v2(p), &ip, &pxlen, &pxopts, &metric);
953

    
954
      if (pxopts & OPT_PX_NU)
955
        continue;
956

    
957
      if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
958
      {
959
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
960
            p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
961
        continue;
962
      }
963

    
964
      re = fib_find(&p->rtf, &ip, pxlen);
965
    }
966
    else // en->lsa_type == LSA_T_SUM_RT
967
    {
968
      lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);
969

    
970
      ip = ipa_from_rid(dst_rid);
971
      re = fib_find(&bb->rtr, &ip, MAX_PREFIX_LENGTH);
972
    }
973

    
974
    /* 16.3 (1b) */
975
    if (metric == LSINFINITY)
976
      continue;
977

    
978
    /* 16.3 (3) */
979
    if (!re || !re->n.type)
980
      continue;
981

    
982
    if (re->n.oa->areaid != 0)
983
      continue;
984

    
985
    if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA))
986
      continue;
987

    
988
    /* 16.3. (4) */
989
    abrip = ipa_from_rid(en->lsa.rt);
990
    abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
991
    if (!abr || !abr->n.type)
992
      continue;
993

    
994
    metric = abr->n.metric1 + metric; /* IAC */
995

    
996
    /* 16.3. (5) */
997
    if ((metric < re->n.metric1) ||
998
        ((metric == re->n.metric1) && unresolved_vlink(re)))
999
    {
1000
      /* We want to replace the next-hop even if the metric is equal
1001
         to replace a virtual next-hop through vlink with a real one.
1002
         Proper ECMP would merge nexthops here, but we do not do that.
1003
         We restrict nexthops to fit one area to simplify check
1004
         12.4.3 p4 in decide_sum_lsa() */
1005

    
1006
      re->n.metric1 = metric;
1007
      re->n.voa = oa;
1008
      re->n.nhs = abr->n.nhs;
1009
    }
1010
  }
1011
}
1012

    
1013
/* Decide about originating or flushing summary LSAs for condended area networks */
1014
static int
1015
decide_anet_lsa(struct ospf_area *oa, struct area_net *anet, struct ospf_area *anet_oa)
1016
{
1017
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
1018
  if (!oa_is_ext(oa) && !oa->ac->summary)
1019
    return 0;
1020

    
1021
  if (oa == anet_oa)
1022
    return 0;
1023

    
1024
  /* Do not condense routing info when exporting from backbone to the transit area */
1025
  if ((anet_oa == oa->po->backbone) && oa->trcap)
1026
    return 0;
1027

    
1028
  return (anet->active && !anet->hidden);
1029
}
1030

    
1031
/* Decide about originating or flushing summary LSAs (12.4.3) */
1032
static int
1033
decide_sum_lsa(struct ospf_area *oa, ort *nf, int dest)
1034
{
1035
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
1036
  if (!oa_is_ext(oa) && !oa->ac->summary)
1037
    return 0;
1038

    
1039
  /* Invalid field - no route */
1040
  if (!nf->n.type)
1041
    return 0;
1042

    
1043
  /* 12.4.3 p2 */
1044
  if (nf->n.type > RTS_OSPF_IA)
1045
    return 0;
1046

    
1047
  /* 12.4.3 p3 */
1048
  if ((nf->n.oa->areaid == oa->areaid))
1049
    return 0;
1050

    
1051
  /* 12.4.3 p4 */
1052
  if (nf->n.voa && (nf->n.voa->areaid == oa->areaid))
1053
    return 0;
1054

    
1055
  /* 12.4.3 p5 */
1056
  if (nf->n.metric1 >= LSINFINITY)
1057
    return 0;
1058

    
1059
  /* 12.4.3 p6 - AS boundary router */
1060
  if (dest == ORT_ROUTER)
1061
  {
1062
    /* We call decide_sum_lsa() on preferred ASBR entries, no need for 16.4. (3) */
1063
    /* 12.4.3 p1 */
1064
    return oa_is_ext(oa) && (nf->n.options & ORTA_ASBR);
1065
  }
1066

    
1067
  /* 12.4.3 p7 - inter-area route */
1068
  if (nf->n.type == RTS_OSPF_IA)
1069
  {
1070
    /* Inter-area routes are not repropagated into the backbone */
1071
    return (oa != oa->po->backbone);
1072
  }
1073

    
1074
  /* 12.4.3 p8 - intra-area route */
1075

    
1076
  /* Do not condense routing info when exporting from backbone to the transit area */
1077
  if ((nf->n.oa == oa->po->backbone) && oa->trcap)
1078
    return 1;
1079

    
1080
  struct area_net *anet = (struct area_net *)
1081
    fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen);
1082

    
1083
  /* Condensed area network found */
1084
  if (anet)
1085
    return 0;
1086

    
1087
  return 1;
1088
}
1089

    
1090
/* RFC 2328 16.7. p1 - originate or flush summary LSAs */
1091
static inline void
1092
check_sum_net_lsa(struct ospf_proto *p, ort *nf)
1093
{
1094
  struct area_net *anet = NULL;
1095
  struct ospf_area *anet_oa = NULL;
1096

    
1097
  if (nf->area_net)
1098
  {
1099
    /* It is a default route for stub areas, handled entirely in ospf_rt_abr() */
1100
    if (nf->fn.pxlen == 0)
1101
      return;
1102

    
1103
    /* Find that area network */
1104
    WALK_LIST(anet_oa, p->area_list)
1105
    {
1106
      anet = (struct area_net *) fib_find(&anet_oa->net_fib, &nf->fn.prefix, nf->fn.pxlen);
1107
      if (anet)
1108
        break;
1109
    }
1110
  }
1111

    
1112
  struct ospf_area *oa;
1113
  WALK_LIST(oa, p->area_list)
1114
  {
1115
    if (anet && decide_anet_lsa(oa, anet, anet_oa))
1116
      ospf_originate_sum_net_lsa(p, oa, nf, anet->metric);
1117
    else if (decide_sum_lsa(oa, nf, ORT_NET))
1118
      ospf_originate_sum_net_lsa(p, oa, nf, nf->n.metric1);
1119
  }
1120
}
1121

    
1122
static inline void
1123
check_sum_rt_lsa(struct ospf_proto *p, ort *nf)
1124
{
1125
  struct ospf_area *oa;
1126
  WALK_LIST(oa, p->area_list)
1127
    if (decide_sum_lsa(oa, nf, ORT_ROUTER))
1128
      ospf_originate_sum_rt_lsa(p, oa, nf, nf->n.metric1, nf->n.options);
1129
}
1130

    
1131
static inline int
1132
decide_nssa_lsa(struct ospf_proto *p, ort *nf, struct ospf_lsa_ext_local *rt)
1133
{
1134
  struct ospf_area *oa = nf->n.oa;
1135
  struct top_hash_entry *en = nf->n.en;
1136

    
1137
  if (!rt_is_nssa(nf) || !oa->translate)
1138
    return 0;
1139

    
1140
  /* Condensed area network found */
1141
  if (fib_route(&oa->enet_fib, nf->fn.prefix, nf->fn.pxlen))
1142
    return 0;
1143

    
1144
  if (!en || (en->lsa_type != LSA_T_NSSA))
1145
    return 0;
1146

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

    
1150
  if (rt->pxopts & OPT_PX_NU)
1151
    return 0;
1152

    
1153
  if (!rt->propagate || ipa_zero(rt->fwaddr))
1154
    return 0;
1155

    
1156
  return 1;
1157
}
1158

    
1159
/* RFC 3103 3.2 - translating Type-7 LSAs into Type-5 LSAs */
1160
static inline void
1161
check_nssa_lsa(struct ospf_proto *p, ort *nf)
1162
{
1163
  struct area_net *anet = NULL;
1164
  struct ospf_area *oa = NULL;
1165
  struct ospf_lsa_ext_local rt;
1166

    
1167
  /* Do not translate LSA if there is already the external LSA from route export */
1168
  if (nf->external_rte)
1169
    return;
1170

    
1171
  if (nf->area_net)
1172
  {
1173
    /* Find that area network */
1174
    WALK_LIST(oa, p->area_list)
1175
    {
1176
      anet = (struct area_net *) fib_find(&oa->enet_fib, &nf->fn.prefix, nf->fn.pxlen);
1177
      if (anet)
1178
        break;
1179
    }
1180
  }
1181

    
1182
  /* RFC 3103 3.2 (3) - originate the aggregated address range */
1183
  if (anet && anet->active && !anet->hidden && oa->translate)
1184
    ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, anet->metric,
1185
                           (anet->metric & LSA_EXT3_EBIT), IPA_NONE, anet->tag, 0);
1186

    
1187
  /* RFC 3103 3.2 (2) - originate the same network */
1188
  else if (decide_nssa_lsa(p, nf, &rt))
1189
    ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, rt.metric, rt.ebit, rt.fwaddr, rt.tag, 0);
1190
}
1191

    
1192
/* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1193
static void
1194
ospf_check_vlinks(struct ospf_proto *p)
1195
{
1196
  struct ospf_iface *ifa;
1197
  WALK_LIST(ifa, p->iface_list)
1198
  {
1199
    if (ifa->type == OSPF_IT_VLINK)
1200
    {
1201
      struct top_hash_entry *tmp;
1202
      tmp = ospf_hash_find_rt(p->gr, ifa->voa->areaid, ifa->vid);
1203

    
1204
      if (tmp && (tmp->color == INSPF) && ipa_nonzero(tmp->lb) && tmp->nhs)
1205
      {
1206
        struct ospf_iface *nhi = ospf_iface_find(p, tmp->nhs->iface);
1207

    
1208
        if ((ifa->state != OSPF_IS_PTP)
1209
            || (ifa->vifa != nhi)
1210
            || !ipa_equal(ifa->vip, tmp->lb))
1211
        {
1212
          OSPF_TRACE(D_EVENTS, "Vlink peer %R found", ifa->vid);
1213
          ospf_iface_sm(ifa, ISM_DOWN);
1214
          ifa->vifa = nhi;
1215
          ifa->addr = nhi->addr;
1216
          ifa->cost = tmp->dist;
1217
          ifa->vip = tmp->lb;
1218
          ospf_iface_sm(ifa, ISM_UP);
1219
        }
1220
        else if ((ifa->state == OSPF_IS_PTP) && (ifa->cost != tmp->dist))
1221
        {
1222
          ifa->cost = tmp->dist;
1223

    
1224
          /* RFC 2328 12.4 Event 8 - vlink state change */
1225
          ospf_notify_rt_lsa(ifa->oa);
1226
        }
1227
      }
1228
      else
1229
      {
1230
        if (ifa->state > OSPF_IS_DOWN)
1231
        {
1232
          OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", ifa->vid);
1233
          ospf_iface_sm(ifa, ISM_DOWN);
1234
        }
1235
      }
1236
    }
1237
  }
1238
}
1239

    
1240

    
1241
/* Miscellaneous route processing that needs to be done by ABRs */
1242
static void
1243
ospf_rt_abr1(struct ospf_proto *p)
1244
{
1245
  struct area_net *anet;
1246
  ort *nf, *default_nf;
1247

    
1248
  /* RFC 2328 G.3 - incomplete resolution of virtual next hops - routers */
1249
  FIB_WALK(&p->backbone->rtr, nftmp)
1250
  {
1251
    nf = (ort *) nftmp;
1252

    
1253
    if (nf->n.type && unresolved_vlink(nf))
1254
      reset_ri(nf);
1255
  }
1256
  FIB_WALK_END;
1257

    
1258

    
1259
  FIB_WALK(&p->rtf, nftmp)
1260
  {
1261
    nf = (ort *) nftmp;
1262

    
1263

    
1264
    /* RFC 2328 G.3 - incomplete resolution of virtual next hops - networks */
1265
    if (nf->n.type && unresolved_vlink(nf))
1266
      reset_ri(nf);
1267

    
1268

    
1269
    /* Compute condensed area networks */
1270
    if (nf->n.type == RTS_OSPF)
1271
    {
1272
      anet = (struct area_net *) fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen);
1273
      if (anet)
1274
      {
1275
        if (!anet->active)
1276
        {
1277
          anet->active = 1;
1278

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

    
1283
          /* 16.2. (3) */
1284
          if (nfi->n.type == RTS_OSPF_IA)
1285
            reset_ri(nfi);
1286
        }
1287

    
1288
        if (anet->metric < nf->n.metric1)
1289
          anet->metric = nf->n.metric1;
1290
      }
1291
    }
1292
  }
1293
  FIB_WALK_END;
1294

    
1295
  ip_addr addr = IPA_NONE;
1296
  default_nf = (ort *) fib_get(&p->rtf, &addr, 0);
1297
  default_nf->area_net = 1;
1298

    
1299
  struct ospf_area *oa;
1300
  WALK_LIST(oa, p->area_list)
1301
  {
1302

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

    
1307
    /*
1308
     * Originate type-7 default route for NSSA areas
1309
     *
1310
     * Because type-7 default LSAs are originated by ABRs, they do not
1311
     * collide with other type-7 LSAs (as ABRs generate type-5 LSAs
1312
     * for both external route export or external-NSSA translation),
1313
     * so we use 0 for the src arg.
1314
     */
1315

    
1316
    if (oa_is_nssa(oa) && oa->ac->default_nssa)
1317
      ospf_originate_ext_lsa(p, oa, default_nf, LSA_M_RTCALC, oa->ac->default_cost,
1318
                             (oa->ac->default_cost & LSA_EXT3_EBIT), IPA_NONE, 0, 0);
1319

    
1320
    /* RFC 2328 16.4. (3) - precompute preferred ASBR entries */
1321
    if (oa_is_ext(oa))
1322
    {
1323
      FIB_WALK(&oa->rtr, nftmp)
1324
      {
1325
        nf = (ort *) nftmp;
1326
        if (nf->n.options & ORTA_ASBR)
1327
          ri_install_asbr(p, &nf->fn.prefix, &nf->n);
1328
      }
1329
      FIB_WALK_END;
1330
    }
1331
  }
1332

    
1333

    
1334
  /* Originate or flush ASBR summary LSAs */
1335
  FIB_WALK(&p->backbone->rtr, nftmp)
1336
  {
1337
    check_sum_rt_lsa(p, (ort *) nftmp);
1338
  }
1339
  FIB_WALK_END;
1340

    
1341

    
1342
  /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1343
  ospf_check_vlinks(p);
1344
}
1345

    
1346

    
1347
static void
1348
translator_timer_hook(timer *timer)
1349
{
1350
  struct ospf_area *oa = timer->data;
1351

    
1352
  if (oa->translate != TRANS_WAIT)
1353
    return;
1354

    
1355
  oa->translate = TRANS_OFF;
1356
  ospf_schedule_rtcalc(oa->po);
1357
}
1358

    
1359
static void
1360
ospf_rt_abr2(struct ospf_proto *p)
1361
{
1362
  struct ospf_area *oa;
1363
  struct top_hash_entry *en;
1364
  ort *nf, *nf2;
1365

    
1366

    
1367
  /* RFC 3103 3.1 - type-7 translator election */
1368
  struct ospf_area *bb = p->backbone;
1369
  WALK_LIST(oa, p->area_list)
1370
    if (oa_is_nssa(oa))
1371
    {
1372
      int translate = 1;
1373

    
1374
      if (oa->ac->translator)
1375
        goto decided;
1376

    
1377
      FIB_WALK(&oa->rtr, nftmp)
1378
      {
1379
        nf = (ort *) nftmp;
1380
        if (!nf->n.type || !(nf->n.options & ORTA_ABR))
1381
          continue;
1382

    
1383
        nf2 = fib_find(&bb->rtr, &nf->fn.prefix, MAX_PREFIX_LENGTH);
1384
        if (!nf2 || !nf2->n.type || !(nf2->n.options & ORTA_ABR))
1385
          continue;
1386

    
1387
        en = ospf_hash_find_rt(p->gr, oa->areaid, nf->n.rid);
1388
        if (!en || (en->color != INSPF))
1389
          continue;
1390

    
1391
        struct ospf_lsa_rt *rt = en->lsa_body;
1392
        /* There is better candidate - Nt-bit or higher Router ID */
1393
        if ((rt->options & OPT_RT_NT) || (p->router_id < nf->n.rid))
1394
        {
1395
          translate = 0;
1396
          goto decided;
1397
        }
1398
      }
1399
      FIB_WALK_END;
1400

    
1401
    decided:
1402
      if (translate && (oa->translate != TRANS_ON))
1403
      {
1404
        if (oa->translate == TRANS_WAIT)
1405
          tm_stop(oa->translator_timer);
1406

    
1407
        oa->translate = TRANS_ON;
1408
      }
1409

    
1410
      if (!translate && (oa->translate == TRANS_ON))
1411
      {
1412
        if (oa->translator_timer == NULL)
1413
          oa->translator_timer = tm_new_set(p->p.pool, translator_timer_hook, oa, 0, 0);
1414

    
1415
        /* Schedule the end of translation */
1416
        tm_start(oa->translator_timer, oa->ac->transint);
1417
        oa->translate = TRANS_WAIT;
1418
      }
1419
    }
1420

    
1421

    
1422
  /* Compute condensed external networks */
1423
  FIB_WALK(&p->rtf, nftmp)
1424
  {
1425
    nf = (ort *) nftmp;
1426
    if (rt_is_nssa(nf) && (nf->n.options & ORTA_PROP))
1427
    {
1428
      struct area_net *anet = (struct area_net *)
1429
        fib_route(&nf->n.oa->enet_fib, nf->fn.prefix, nf->fn.pxlen);
1430

    
1431
      if (anet)
1432
      {
1433
        if (!anet->active)
1434
        {
1435
          anet->active = 1;
1436

    
1437
          /* Get a RT entry and mark it to know that it is an area network */
1438
          nf2 = (ort *) fib_get(&p->rtf, &anet->fn.prefix, anet->fn.pxlen);
1439
          nf2->area_net = 1;
1440
        }
1441

    
1442
        u32 metric = (nf->n.type == RTS_OSPF_EXT1) ?
1443
          nf->n.metric1 : ((nf->n.metric2 + 1) | LSA_EXT3_EBIT);
1444

    
1445
        if (anet->metric < metric)
1446
          anet->metric = metric;
1447
      }
1448
    }
1449
  }
1450
  FIB_WALK_END;
1451

    
1452

    
1453
  FIB_WALK(&p->rtf, nftmp)
1454
  {
1455
    nf = (ort *) nftmp;
1456

    
1457
    check_sum_net_lsa(p, nf);
1458
    check_nssa_lsa(p, nf);
1459
  }
1460
  FIB_WALK_END;
1461
}
1462

    
1463

    
1464
/* Like fib_route(), but ignores dummy rt entries */
1465
static void *
1466
ospf_fib_route(struct fib *f, ip_addr a, int len)
1467
{
1468
  ip_addr a0;
1469
  ort *nf;
1470

    
1471
  while (len >= 0)
1472
  {
1473
    a0 = ipa_and(a, ipa_mkmask(len));
1474
    nf = fib_find(f, &a0, len);
1475
    if (nf && nf->n.type)
1476
      return nf;
1477
    len--;
1478
  }
1479
  return NULL;
1480
}
1481

    
1482
/* RFC 2328 16.4. calculating external routes */
1483
static void
1484
ospf_ext_spf(struct ospf_proto *p)
1485
{
1486
  struct top_hash_entry *en;
1487
  struct ospf_lsa_ext_local rt;
1488
  ort *nf1, *nf2;
1489
  orta nfa = {};
1490
  ip_addr rtid;
1491
  u32 br_metric;
1492
  struct ospf_area *atmp;
1493

    
1494
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
1495

    
1496
  WALK_SLIST(en, p->lsal)
1497
  {
1498
    /* 16.4. (1) */
1499
    if ((en->lsa_type != LSA_T_EXT) && (en->lsa_type != LSA_T_NSSA))
1500
      continue;
1501

    
1502
    if (en->lsa.age == LSA_MAXAGE)
1503
      continue;
1504

    
1505
    /* 16.4. (2) */
1506
    if (en->lsa.rt == p->router_id)
1507
      continue;
1508

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

    
1512
    lsa_parse_ext(en, ospf_is_v2(p), &rt);
1513

    
1514
    if (rt.metric == LSINFINITY)
1515
      continue;
1516

    
1517
    if (rt.pxopts & OPT_PX_NU)
1518
      continue;
1519

    
1520
    if (rt.pxlen < 0 || rt.pxlen > MAX_PREFIX_LENGTH)
1521
    {
1522
      log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
1523
          p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
1524
      continue;
1525
    }
1526

    
1527

    
1528
    /* 16.4. (3) */
1529
    /* If there are more areas, we already precomputed preferred ASBR
1530
       entries in ospf_rt_abr1() and stored them in the backbone
1531
       table. For NSSA, we examine the area to which the LSA is assigned */
1532
    if (en->lsa_type == LSA_T_EXT)
1533
      atmp = ospf_main_area(p);
1534
    else /* NSSA */
1535
      atmp = ospf_find_area(p, en->domain);
1536

    
1537
    if (!atmp)
1538
      continue;                        /* Should not happen */
1539

    
1540
    rtid = ipa_from_rid(en->lsa.rt);
1541
    nf1 = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH);
1542

    
1543
    if (!nf1 || !nf1->n.type)
1544
      continue;                        /* No AS boundary router found */
1545

    
1546
    if (!(nf1->n.options & ORTA_ASBR))
1547
      continue;                        /* It is not ASBR */
1548

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

    
1555
    if (!rt.fbit)
1556
    {
1557
      nf2 = nf1;
1558
      nfa.nhs = nf1->n.nhs;
1559
      br_metric = nf1->n.metric1;
1560
    }
1561
    else
1562
    {
1563
      nf2 = ospf_fib_route(&p->rtf, rt.fwaddr, MAX_PREFIX_LENGTH);
1564
      if (!nf2)
1565
        continue;
1566

    
1567
      if (en->lsa_type == LSA_T_EXT)
1568
      {
1569
        /* For ext routes, we accept intra-area or inter-area routes */
1570
        if ((nf2->n.type != RTS_OSPF) && (nf2->n.type != RTS_OSPF_IA))
1571
          continue;
1572
      }
1573
      else /* NSSA */
1574
      {
1575
        /* For NSSA routes, we accept just intra-area in the same area */
1576
        if ((nf2->n.type != RTS_OSPF) || (nf2->n.oa != atmp))
1577
          continue;
1578
      }
1579

    
1580
      /* Next-hop is a part of a configured stubnet */
1581
      if (!nf2->n.nhs)
1582
        continue;
1583

    
1584
      nfa.nhs = nf2->n.nhs;
1585
      br_metric = nf2->n.metric1;
1586

    
1587
      /* Replace device nexthops with nexthops to forwarding address from LSA */
1588
      if (has_device_nexthops(nfa.nhs))
1589
      {
1590
        nfa.nhs = fix_device_nexthops(p, nfa.nhs, rt.fwaddr);
1591
        nfa.nhs_reuse = 1;
1592
      }
1593
    }
1594

    
1595
    if (rt.ebit)
1596
    {
1597
      nfa.type = RTS_OSPF_EXT2;
1598
      nfa.metric1 = br_metric;
1599
      nfa.metric2 = rt.metric;
1600
    }
1601
    else
1602
    {
1603
      nfa.type = RTS_OSPF_EXT1;
1604
      nfa.metric1 = br_metric + rt.metric;
1605
      nfa.metric2 = LSINFINITY;
1606
    }
1607

    
1608
    /* Mark the LSA as reachable */
1609
    en->color = INSPF;
1610

    
1611
    /* Whether the route is preferred in route selection according to 16.4.1 */
1612
    nfa.options = epath_preferred(&nf2->n) ? ORTA_PREF : 0;
1613
    if (en->lsa_type == LSA_T_NSSA)
1614
    {
1615
      nfa.options |= ORTA_NSSA;
1616
      if (rt.propagate)
1617
        nfa.options |= ORTA_PROP;
1618
    }
1619

    
1620
    nfa.tag = rt.tag;
1621
    nfa.rid = en->lsa.rt;
1622
    nfa.oa = atmp; /* undefined in RFC 2328 */
1623
    nfa.en = en; /* store LSA for later (NSSA processing) */
1624

    
1625
    ri_install_ext(p, rt.ip, rt.pxlen, &nfa);
1626
  }
1627
}
1628

    
1629
/* Cleanup of routing tables and data */
1630
void
1631
ospf_rt_reset(struct ospf_proto *p)
1632
{
1633
  struct ospf_area *oa;
1634
  struct top_hash_entry *en;
1635
  struct area_net *anet;
1636
  ort *ri;
1637

    
1638
  /* Reset old routing table */
1639
  FIB_WALK(&p->rtf, nftmp)
1640
  {
1641
    ri = (ort *) nftmp;
1642
    ri->area_net = 0;
1643
    reset_ri(ri);
1644
  }
1645
  FIB_WALK_END;
1646

    
1647
  /* Reset SPF data in LSA db */
1648
  WALK_SLIST(en, p->lsal)
1649
  {
1650
    en->color = OUTSPF;
1651
    en->dist = LSINFINITY;
1652
    en->nhs = NULL;
1653
    en->lb = IPA_NONE;
1654

    
1655
    if (en->mode == LSA_M_RTCALC)
1656
      en->mode = LSA_M_STALE;
1657
  }
1658

    
1659
  WALK_LIST(oa, p->area_list)
1660
  {
1661
    /* Reset ASBR routing tables */
1662
    FIB_WALK(&oa->rtr, nftmp)
1663
    {
1664
      ri = (ort *) nftmp;
1665
      reset_ri(ri);
1666
    }
1667
    FIB_WALK_END;
1668

    
1669
    /* Reset condensed area networks */
1670
    if (p->areano > 1)
1671
    {
1672
      FIB_WALK(&oa->net_fib, nftmp)
1673
      {
1674
        anet = (struct area_net *) nftmp;
1675
        anet->active = 0;
1676
        anet->metric = 0;
1677
      }
1678
      FIB_WALK_END;
1679

    
1680
      FIB_WALK(&oa->enet_fib, nftmp)
1681
      {
1682
        anet = (struct area_net *) nftmp;
1683
        anet->active = 0;
1684
        anet->metric = 0;
1685
      }
1686
      FIB_WALK_END;
1687
    }
1688
  }
1689
}
1690

    
1691
/**
1692
 * ospf_rt_spf - calculate internal routes
1693
 * @p: OSPF protocol instance
1694
 *
1695
 * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
1696
 * It's based on Dijkstra's shortest path tree algorithms.
1697
 * This function is invoked from ospf_disp().
1698
 */
1699
void
1700
ospf_rt_spf(struct ospf_proto *p)
1701
{
1702
  struct ospf_area *oa;
1703

    
1704
  if (p->areano == 0)
1705
    return;
1706

    
1707
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
1708

    
1709
  /* 16. (1) */
1710
  ospf_rt_reset(p);
1711

    
1712
  /* 16. (2) */
1713
  WALK_LIST(oa, p->area_list)
1714
    ospf_rt_spfa(oa);
1715

    
1716
  /* 16. (3) */
1717
  ospf_rt_sum(ospf_main_area(p));
1718

    
1719
  /* 16. (4) */
1720
  WALK_LIST(oa, p->area_list)
1721
    if (oa->trcap && (oa->areaid != 0))
1722
      ospf_rt_sum_tr(oa);
1723

    
1724
  if (p->areano > 1)
1725
    ospf_rt_abr1(p);
1726

    
1727
  /* 16. (5) */
1728
  ospf_ext_spf(p);
1729

    
1730
  if (p->areano > 1)
1731
    ospf_rt_abr2(p);
1732

    
1733
  rt_sync(p);
1734
  lp_flush(p->nhpool);
1735

    
1736
  p->calcrt = 0;
1737
}
1738

    
1739

    
1740
static inline int
1741
inherit_nexthops(struct mpnh *pn)
1742
{
1743
  /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */
1744
  return pn && (ipa_nonzero(pn->gw) || !pn->iface);
1745
}
1746

    
1747
static struct mpnh *
1748
calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
1749
              struct top_hash_entry *par, int pos)
1750
{
1751
  struct ospf_proto *p = oa->po;
1752
  struct mpnh *pn = par->nhs;
1753
  struct ospf_iface *ifa;
1754
  u32 rid = en->lsa.rt;
1755

    
1756
  /* 16.1.1. The next hop calculation */
1757
  DBG("     Next hop calculating for id: %R rt: %R type: %u\n",
1758
      en->lsa.id, en->lsa.rt, en->lsa_type);
1759

    
1760
  /* Usually, we inherit parent nexthops */
1761
  if (inherit_nexthops(pn))
1762
    return pn;
1763

    
1764
  /*
1765
   * There are three cases:
1766
   * 1) en is a local network (and par is root)
1767
   * 2) en is a ptp or ptmp neighbor (and par is root)
1768
   * 3) en is a bcast or nbma neighbor (and par is local network)
1769
   */
1770

    
1771
  /* The first case - local network */
1772
  if ((en->lsa_type == LSA_T_NET) && (par == oa->rt))
1773
  {
1774
    ifa = rt_pos_to_ifa(oa, pos);
1775
    if (!ifa)
1776
      return NULL;
1777

    
1778
    return new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight);
1779
  }
1780

    
1781
  /* The second case - ptp or ptmp neighbor */
1782
  if ((en->lsa_type == LSA_T_RT) && (par == oa->rt))
1783
  {
1784
    ifa = rt_pos_to_ifa(oa, pos);
1785
    if (!ifa)
1786
      return NULL;
1787

    
1788
    if (ifa->type == OSPF_IT_VLINK)
1789
      return new_nexthop(p, IPA_NONE, NULL, 0);
1790

    
1791
    struct ospf_neighbor *m = find_neigh(ifa, rid);
1792
    if (!m || (m->state != NEIGHBOR_FULL))
1793
      return NULL;
1794

    
1795
    return new_nexthop(p, m->ip, ifa->iface, ifa->ecmp_weight);
1796
  }
1797

    
1798
  /* The third case - bcast or nbma neighbor */
1799
  if ((en->lsa_type == LSA_T_RT) && (par->lsa_type == LSA_T_NET))
1800
  {
1801
    /* par->nhi should be defined from parent's calc_next_hop() */
1802
    if (!pn)
1803
      goto bad;
1804

    
1805
    if (ospf_is_v2(p))
1806
    {
1807
      /*
1808
       * In this case, next-hop is the same as link-back, which is
1809
       * already computed in link_back().
1810
       */
1811
      if (ipa_zero(en->lb))
1812
        goto bad;
1813

    
1814
      return new_nexthop(p, en->lb, pn->iface, pn->weight);
1815
    }
1816
    else /* OSPFv3 */
1817
    {
1818
      /*
1819
       * Next-hop is taken from lladdr field of Link-LSA, en->lb_id
1820
       * is computed in link_back().
1821
       */
1822
      struct top_hash_entry *lhe;
1823
      lhe = ospf_hash_find(p->gr, pn->iface->index, en->lb_id, rid, LSA_T_LINK);
1824

    
1825
      if (!lhe)
1826
        return NULL;
1827

    
1828
      struct ospf_lsa_link *llsa = lhe->lsa_body;
1829

    
1830
      if (ip6_zero(llsa->lladdr))
1831
        return NULL;
1832

    
1833
      return new_nexthop(p, ipa_from_ip6(llsa->lladdr), pn->iface, pn->weight);
1834
    }
1835
  }
1836

    
1837
 bad:
1838
  /* Probably bug or some race condition, we log it */
1839
  log(L_ERR "%s: Unexpected case in next hop calculation", p->p.name);
1840
  return NULL;
1841
}
1842

    
1843

    
1844
/* Add LSA into list of candidates in Dijkstra's algorithm */
1845
static void
1846
add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
1847
         u32 dist, struct ospf_area *oa, int pos)
1848
{
1849
  struct ospf_proto *p = oa->po;
1850
  node *prev, *n;
1851
  int added = 0;
1852
  struct top_hash_entry *act;
1853

    
1854
  /* 16.1. (2b) */
1855
  if (en == NULL)
1856
    return;
1857
  if (en->lsa.age == LSA_MAXAGE)
1858
    return;
1859

    
1860
  if (ospf_is_v3(p) && (en->lsa_type == LSA_T_RT))
1861
  {
1862
    /* In OSPFv3, check V6 flag */
1863
    struct ospf_lsa_rt *rt = en->lsa_body;
1864
    if (!(rt->options & OPT_V6))
1865
      return;
1866
  }
1867

    
1868
  /* 16.1. (2c) */
1869
  if (en->color == INSPF)
1870
    return;
1871

    
1872
  /* 16.1. (2d), also checks that dist < LSINFINITY */
1873
  if (dist > en->dist)
1874
    return;
1875

    
1876
  /* We should check whether there is a reverse link from en to par, */
1877
  if (!link_back(oa, en, par))
1878
    return;
1879

    
1880
  struct mpnh *nhs = calc_next_hop(oa, en, par, pos);
1881
  if (!nhs)
1882
  {
1883
    log(L_WARN "%s: Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
1884
        p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
1885
    return;
1886
  }
1887

    
1888
  /* We know that en->color == CANDIDATE and en->nhs is defined. */
1889

    
1890
  if ((dist == en->dist) && !nh_is_vlink(en->nhs))
1891
  {
1892
    /*
1893
     * For multipath, we should merge nexthops. We merge regular nexthops only.
1894
     * Dummy vlink nexthops are less preferred and handled as a special case.
1895
     *
1896
     * During merging, new nexthops (nhs) can be reused if they are not
1897
     * inherited from the parent (i.e. they are allocated in calc_next_hop()).
1898
     * Current nexthops (en->nhs) can be reused if they weren't inherited in
1899
     * previous steps (that is stored in nhs_reuse, i.e. created by merging or
1900
     * allocated in calc_next_hop()).
1901
     *
1902
     * Generally, a node first inherits shared nexthops from its parent and
1903
     * later possibly gets reusable copy during merging.
1904
     */
1905

    
1906
    /* Keep old ones */
1907
    if (!p->ecmp || nh_is_vlink(nhs) || (nhs == en->nhs))
1908
      return;
1909

    
1910
    /* Merge old and new */
1911
    int new_reuse = (par->nhs != nhs);
1912
    en->nhs = merge_nexthops(p, en->nhs, nhs, en->nhs_reuse, new_reuse);
1913
    en->nhs_reuse = 1;
1914
    return;
1915
  }
1916

    
1917
  DBG("     Adding candidate: rt: %R, id: %R, type: %u\n",
1918
      en->lsa.rt, en->lsa.id, en->lsa_type);
1919

    
1920
  if (en->color == CANDIDATE)
1921
  {                                /* We found a shorter path */
1922
    rem_node(&en->cn);
1923
  }
1924
  en->nhs = nhs;
1925
  en->dist = dist;
1926
  en->color = CANDIDATE;
1927
  en->nhs_reuse = (par->nhs != nhs);
1928

    
1929
  prev = NULL;
1930

    
1931
  if (EMPTY_LIST(*l))
1932
  {
1933
    add_head(l, &en->cn);
1934
  }
1935
  else
1936
  {
1937
    WALK_LIST(n, *l)
1938
    {
1939
      act = SKIP_BACK(struct top_hash_entry, cn, n);
1940
      if ((act->dist > dist) ||
1941
          ((act->dist == dist) && (act->lsa_type == LSA_T_RT)))
1942
      {
1943
        if (prev == NULL)
1944
          add_head(l, &en->cn);
1945
        else
1946
          insert_node(&en->cn, prev);
1947
        added = 1;
1948
        break;
1949
      }
1950
      prev = n;
1951
    }
1952

    
1953
    if (!added)
1954
    {
1955
      add_tail(l, &en->cn);
1956
    }
1957
  }
1958
}
1959

    
1960
static inline int
1961
ort_changed(ort *nf, rta *nr)
1962
{
1963
  rta *or = nf->old_rta;
1964
  return !or ||
1965
    (nf->n.metric1 != nf->old_metric1) || (nf->n.metric2 != nf->old_metric2) ||
1966
    (nf->n.tag != nf->old_tag) || (nf->n.rid != nf->old_rid) ||
1967
    (nr->source != or->source) || (nr->dest != or->dest) ||
1968
    (nr->iface != or->iface) || !ipa_equal(nr->gw, or->gw) ||
1969
    !mpnh_same(nr->nexthops, or->nexthops);
1970
}
1971

    
1972
static void
1973
rt_sync(struct ospf_proto *p)
1974
{
1975
  struct top_hash_entry *en;
1976
  struct fib_iterator fit;
1977
  struct fib *fib = &p->rtf;
1978
  ort *nf;
1979
  struct ospf_area *oa;
1980

    
1981
  /* This is used for forced reload of routes */
1982
  int reload = (p->calcrt == 2);
1983

    
1984
  OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation");
1985

    
1986
  DBG("Now syncing my rt table with nest's\n");
1987
  FIB_ITERATE_INIT(&fit, fib);
1988
again1:
1989
  FIB_ITERATE_START(fib, &fit, nftmp)
1990
  {
1991
    nf = (ort *) nftmp;
1992

    
1993
    /* Sanity check of next-hop addresses, failure should not happen */
1994
    if (nf->n.type)
1995
    {
1996
      struct mpnh *nh;
1997
      for (nh = nf->n.nhs; nh; nh = nh->next)
1998
        if (ipa_nonzero(nh->gw))
1999
        {
2000
          neighbor *ng = neigh_find2(&p->p, &nh->gw, nh->iface, 0);
2001
          if (!ng || (ng->scope == SCOPE_HOST))
2002
            { reset_ri(nf); break; }
2003
        }
2004
    }
2005

    
2006
    /* Remove configured stubnets */
2007
    if (!nf->n.nhs)
2008
      reset_ri(nf);
2009

    
2010
    if (nf->n.type) /* Add the route */
2011
    {
2012
      rta a0 = {
2013
        .src = p->p.main_source,
2014
        .source = nf->n.type,
2015
        .scope = SCOPE_UNIVERSE,
2016
        .cast = RTC_UNICAST
2017
      };
2018

    
2019
      if (nf->n.nhs->next)
2020
      {
2021
        a0.dest = RTD_MULTIPATH;
2022
        a0.nexthops = nf->n.nhs;
2023
      }
2024
      else if (ipa_nonzero(nf->n.nhs->gw))
2025
      {
2026
        a0.dest = RTD_ROUTER;
2027
        a0.iface = nf->n.nhs->iface;
2028
        a0.gw = nf->n.nhs->gw;
2029
      }
2030
      else
2031
      {
2032
        a0.dest = RTD_DEVICE;
2033
        a0.iface = nf->n.nhs->iface;
2034
      }
2035

    
2036
      if (reload || ort_changed(nf, &a0))
2037
      {
2038
        net *ne = net_get(p->p.table, nf->fn.prefix, nf->fn.pxlen);
2039
        rta *a = rta_lookup(&a0);
2040
        rte *e = rte_get_temp(a);
2041

    
2042
        rta_free(nf->old_rta);
2043
        nf->old_rta = rta_clone(a);
2044
        e->u.ospf.metric1 = nf->old_metric1 = nf->n.metric1;
2045
        e->u.ospf.metric2 = nf->old_metric2 = nf->n.metric2;
2046
        e->u.ospf.tag = nf->old_tag = nf->n.tag;
2047
        e->u.ospf.router_id = nf->old_rid = nf->n.rid;
2048
        e->pflags = 0;
2049
        e->net = ne;
2050
        e->pref = p->p.preference;
2051

    
2052
        DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n",
2053
            a0.source, nf->fn.prefix, nf->fn.pxlen, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
2054
        rte_update(&p->p, ne, e);
2055
      }
2056
    }
2057
    else if (nf->old_rta)
2058
    {
2059
      /* Remove the route */
2060
      rta_free(nf->old_rta);
2061
      nf->old_rta = NULL;
2062

    
2063
      net *ne = net_get(p->p.table, nf->fn.prefix, nf->fn.pxlen);
2064
      rte_update(&p->p, ne, NULL);
2065
    }
2066

    
2067
    /* Remove unused rt entry, some special entries are persistent */
2068
    if (!nf->n.type && !nf->external_rte && !nf->area_net)
2069
    {
2070
      FIB_ITERATE_PUT(&fit, nftmp);
2071
      fib_delete(fib, nftmp);
2072
      goto again1;
2073
    }
2074
  }
2075
  FIB_ITERATE_END(nftmp);
2076

    
2077

    
2078
  WALK_LIST(oa, p->area_list)
2079
  {
2080
    /* Cleanup ASBR hash tables */
2081
    FIB_ITERATE_INIT(&fit, &oa->rtr);
2082
again2:
2083
    FIB_ITERATE_START(&oa->rtr, &fit, nftmp)
2084
    {
2085
      nf = (ort *) nftmp;
2086

    
2087
      if (!nf->n.type)
2088
      {
2089
        FIB_ITERATE_PUT(&fit, nftmp);
2090
        fib_delete(&oa->rtr, nftmp);
2091
        goto again2;
2092
      }
2093
    }
2094
    FIB_ITERATE_END(nftmp);
2095
  }
2096

    
2097
  /* Cleanup stale LSAs */
2098
  WALK_SLIST(en, p->lsal)
2099
    if (en->mode == LSA_M_STALE)
2100
      ospf_flush_lsa(p, en);
2101
}