Statistics
| Branch: | Revision:

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

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

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

    
133
  return root;
134
}
135

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

    
144
  return 0;
145
}
146

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

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

    
160
  for (; n; n = n->next)
161
  {
162
    struct mpnh *nn = new_nexthop(p, ipa_zero(n->gw) ? gw : n->gw, n->iface, n->weight);
163

    
164
    if (ipa_zero(n->gw))
165
    {
166
      *nn1 = nn;
167
      nn1 = &(nn->next);
168
    }
169
    else
170
    {
171
      *nn2 = nn;
172
      nn2 = &(nn->next);
173
    }
174
  }
175

    
176
  return merge_nexthops(p, root1, root2, 1, 1);
177
}
178

    
179

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

    
188
/* Whether the ext route has ASBR/next_hop marked as preferred. */
189
static inline int
190
orta_pref(const orta *nf)
191
{
192
  return !!(nf->options & ORTA_PREF);
193
}
194

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

    
203
  /* A Type-7 LSA with the P-bit set */
204
  if (opts == (ORTA_NSSA | ORTA_PROP))
205
    return 2;
206

    
207
  /* A Type-5 LSA */
208
  if (opts == 0)
209
    return 1;
210

    
211
  return 0;
212
}
213

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

    
222
  return (pn > po) || ((pn == po) && (new->en->lsa.rt > old->en->lsa.rt));
223
}
224

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

    
236
  if (old->type == RTS_DUMMY)
237
    return 1;
238

    
239
  /* Prefer intra-area to inter-area to externals */
240
  r = ((int) old->type) - ((int) new->type);
241
  if (r) return r;
242

    
243
  /* Prefer lowest type 1 metric */
244
  r = ((int) old->metric1) - ((int) new->metric1);
245
  if (r) return r;
246

    
247

    
248
  /* Rest is BIRD-specific */
249

    
250
  /* Area-wide routes should not mix next-hops from different areas.
251
     This generally should not happen unless there is some misconfiguration. */
252
  if (new->oa->areaid != old->oa->areaid)
253
    return (new->oa->areaid > old->oa->areaid) ? 1 : -1;
254

    
255
  /* Prefer routes for configured stubnets (!nhs) to regular routes to dummy
256
     vlink nexthops. We intentionally return -1 if both are stubnets or vlinks. */
257
  if (!old->nhs)
258
    return -1;
259
  if (!new->nhs)
260
    return 1;
261
  if (nh_is_vlink(new->nhs))
262
    return -1;
263
  if (nh_is_vlink(old->nhs))
264
    return 1;
265

    
266

    
267
  if (p->ecmp)
268
    return 0;
269

    
270
  /* Prefer routes with higher Router ID, just to be more deterministic */
271
  if (new->rid > old->rid)
272
    return 1;
273
  
274
  return -1;
275
}
276

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

    
287
  if (old->type == RTS_DUMMY)
288
    return 1;
289

    
290
  if (!p->rfc1583)
291
  {
292
    r = epath_preferred(new) - epath_preferred(old);
293
    if (r) return r;
294
  }
295

    
296
  r = ((int) old->metric1) - ((int) new->metric1);
297
  if (r) return r;
298

    
299
  /* Larger area ID is preferred */
300
  if (new->oa->areaid > old->oa->areaid)
301
    return 1;
302

    
303
  /* There is just one ASBR of that RID per area, so tie is not possible */
304
  return -1;
305
}
306

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

    
317
  if (old->type == RTS_DUMMY)
318
    return 1;
319

    
320
  /* 16.4 (6a) - prefer routes with lower type */
321
  r = ((int) old->type) - ((int) new->type);
322
  if (r) return r;
323

    
324
  /* 16.4 (6b) - prefer routes with lower type 2 metric */
325
  if (new->type == RTS_OSPF_EXT2)
326
  {
327
    r = ((int) old->metric2) - ((int) new->metric2);
328
    if (r) return r;
329
  }
330

    
331
  /* 16.4 (6c) - if not RFC1583, prefer routes with preferred ASBR/next_hop */
332
  if (!p->rfc1583)
333
  {
334
    r = orta_pref(new) - orta_pref(old);
335
    if (r) return r;
336
  }
337

    
338
  /* 16.4 (6d) - prefer routes with lower type 1 metric */
339
  r = ((int) old->metric1) - ((int) new->metric1);
340
  if (r) return r;
341

    
342

    
343
  if (p->ecmp && p->merge_external)
344
    return 0;
345

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

    
355
  return -1;
356
}
357

    
358

    
359
static inline void
360
ort_replace(ort *o, const orta *new)
361
{
362
  memcpy(&o->n, new, sizeof(orta));
363
}
364

    
365
static void
366
ort_merge(struct ospf_proto *p, ort *o, const orta *new)
367
{
368
  orta *old = &o->n;
369

    
370
  if (old->nhs != new->nhs)
371
  {
372
    old->nhs = merge_nexthops(p, old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse);
373
    old->nhs_reuse = 1;
374
  }
375

    
376
  if (old->rid < new->rid)
377
    old->rid = new->rid;
378
}
379

    
380
static void
381
ort_merge_ext(struct ospf_proto *p, ort *o, const orta *new)
382
{
383
  orta *old = &o->n;
384

    
385
  if (old->nhs != new->nhs)
386
  {
387
    old->nhs = merge_nexthops(p, old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse);
388
    old->nhs_reuse = 1;
389
  }
390

    
391
  if (old->tag != new->tag)
392
    old->tag = 0;
393

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

    
409

    
410

    
411
static inline void
412
ri_install_net(struct ospf_proto *p, ip_addr prefix, int pxlen, const orta *new)
413
{
414
  ort *old = (ort *) fib_get(&p->rtf, &prefix, pxlen);
415
  int cmp = orta_compare(p, new, &old->n);
416

    
417
  if (cmp > 0)
418
    ort_replace(old, new);
419
  else if (cmp == 0)
420
    ort_merge(p, old, new);
421
}
422

    
423
static inline void
424
ri_install_rt(struct ospf_area *oa, u32 rid, const orta *new)
425
{
426
  ip_addr addr = ipa_from_rid(rid);
427
  ort *old = (ort *) fib_get(&oa->rtr, &addr, MAX_PREFIX_LENGTH);
428
  int cmp = orta_compare(oa->po, new, &old->n);
429

    
430
  if (cmp > 0)
431
    ort_replace(old, new);
432
  else if (cmp == 0)
433
    ort_merge(oa->po, old, new);
434
}
435

    
436
static inline void
437
ri_install_asbr(struct ospf_proto *p, ip_addr *addr, const orta *new)
438
{
439
  ort *old = (ort *) fib_get(&p->backbone->rtr, addr, MAX_PREFIX_LENGTH);
440
  if (orta_compare_asbr(p, new, &old->n) > 0)
441
    ort_replace(old, new);
442
}
443

    
444
static inline void
445
ri_install_ext(struct ospf_proto *p, ip_addr prefix, int pxlen, const orta *new)
446
{
447
  ort *old = (ort *) fib_get(&p->rtf, &prefix, pxlen);
448
  int cmp = orta_compare_ext(p, new, &old->n);
449

    
450
  if (cmp > 0)
451
    ort_replace(old, new);
452
  else if (cmp == 0)
453
    ort_merge_ext(p, old, new);
454
}
455

    
456
static inline struct ospf_iface *
457
rt_pos_to_ifa(struct ospf_area *oa, int pos)
458
{
459
  struct ospf_iface *ifa;
460

    
461
  WALK_LIST(ifa, oa->po->iface_list)
462
    if (ifa->oa == oa && pos >= ifa->rt_pos_beg && pos < ifa->rt_pos_end)
463
      return ifa;
464

    
465
  return NULL;
466
}
467

    
468
static inline struct ospf_iface *
469
px_pos_to_ifa(struct ospf_area *oa, int pos)
470
{
471
  struct ospf_iface *ifa;
472

    
473
  WALK_LIST(ifa, oa->po->iface_list)
474
    if (ifa->oa == oa && pos >= ifa->px_pos_beg && pos < ifa->px_pos_end)
475
      return ifa;
476

    
477
  return NULL;
478
}
479

    
480

    
481
static void
482
add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en, int pos)
483
{
484
  struct ospf_proto *p = oa->po;
485

    
486
  orta nf = {
487
    .type = RTS_OSPF,
488
    .options = 0,
489
    .metric1 = metric,
490
    .metric2 = LSINFINITY,
491
    .tag = 0,
492
    .rid = en->lsa.rt,
493
    .oa = oa,
494
    .nhs = en->nhs
495
  };
496

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

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

    
514
    struct ospf_iface *ifa;
515
    ifa = ospf_is_v2(p) ? rt_pos_to_ifa(oa, pos) : px_pos_to_ifa(oa, pos);
516
    nf.nhs = ifa ? new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight) : NULL;
517
  }
518

    
519
  ri_install_net(p, px, pxlen, &nf);
520
}
521

    
522

    
523

    
524
static inline void
525
spfa_process_rt(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
526
{
527
  struct ospf_lsa_rt *rt = act->lsa_body;
528
  struct ospf_lsa_rt_walk rtl;
529
  struct top_hash_entry *tmp;
530
  ip_addr prefix;
531
  int pxlen, i;
532

    
533
  if (rt->options & OPT_RT_V)
534
    oa->trcap = 1;
535

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

    
558
  /* Errata 2078 to RFC 5340 4.8.1 - skip links from non-routing nodes */
559
  if (ospf_is_v3(p) && (act != oa->rt) && !(rt->options & OPT_R))
560
    return;
561

    
562
  /* Now process Rt links */
563
  for (lsa_walk_rt_init(p, act, &rtl), i = 0; lsa_walk_rt(&rtl); i++)
564
  {
565
    tmp = NULL;
566

    
567
    switch (rtl.type)
568
    {
569
    case LSART_STUB:
570

    
571
      /* Should not happen, LSART_STUB is not defined in OSPFv3 */
572
      if (ospf_is_v3(p))
573
        break;
574

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

    
586
    case LSART_NET:
587
      tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
588
      break;
589

    
590
    case LSART_VLNK:
591
    case LSART_PTP:
592
      tmp = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
593
      break;
594
    }
595

    
596
    add_cand(&oa->cand, tmp, act, act->dist + rtl.metric, oa, i);
597
  }
598
}
599

    
600
static inline void
601
spfa_process_net(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
602
{
603
  struct ospf_lsa_net *ln = act->lsa_body;
604
  struct top_hash_entry *tmp;
605
  ip_addr prefix;
606
  int pxlen, i, cnt;
607

    
608
  if (ospf_is_v2(p))
609
  {
610
    prefix = ipa_from_u32(act->lsa.id & ln->optx);
611
    pxlen = u32_masklen(ln->optx);
612
    add_network(oa, prefix, pxlen, act->dist, act, -1);
613
  }
614

    
615
  cnt = lsa_net_count(&act->lsa);
616
  for (i = 0; i < cnt; i++)
617
  {
618
    tmp = ospf_hash_find_rt(p->gr, oa->areaid, ln->routers[i]);
619
    add_cand(&oa->cand, tmp, act, act->dist, oa, -1);
620
  }
621
}
622

    
623
static inline void
624
spfa_process_prefixes(struct ospf_proto *p, struct ospf_area *oa)
625
{
626
  struct top_hash_entry *en, *src;
627
  struct ospf_lsa_prefix *px;
628
  ip_addr pxa;
629
  int pxlen;
630
  u8 pxopts;
631
  u16 metric;
632
  u32 *buf;
633
  int i;
634

    
635
  WALK_SLIST(en, p->lsal)
636
  {
637
    if (en->lsa_type != LSA_T_PREFIX)
638
      continue;
639

    
640
    if (en->domain != oa->areaid)
641
      continue;
642

    
643
    if (en->lsa.age == LSA_MAXAGE)
644
      continue;
645

    
646
    px = en->lsa_body;
647

    
648
    /* For router prefix-LSA, we would like to find the first router-LSA */
649
    if (px->ref_type == LSA_T_RT)
650
      src = ospf_hash_find_rt(p->gr, oa->areaid, px->ref_rt);
651
    else
652
      src = ospf_hash_find(p->gr, oa->areaid, px->ref_id, px->ref_rt, px->ref_type);
653

    
654
    if (!src)
655
      continue;
656

    
657
    /* Reachable in SPF */
658
    if (src->color != INSPF)
659
      continue;
660

    
661
    if ((src->lsa_type != LSA_T_RT) && (src->lsa_type != LSA_T_NET))
662
      continue;
663

    
664
    buf = px->rest;
665
    for (i = 0; i < px->pxcount; i++)
666
      {
667
        buf = lsa_get_ipv6_prefix(buf, &pxa, &pxlen, &pxopts, &metric);
668

    
669
        if (pxopts & OPT_PX_NU)
670
          continue;
671

    
672
        /* Store the first global address to use it later as a vlink endpoint */
673
        if ((pxopts & OPT_PX_LA) && ipa_zero(src->lb))
674
          src->lb = pxa;
675

    
676
        add_network(oa, pxa, pxlen, src->dist + metric, src, i);
677
      }
678
  }
679
}
680

    
681
/* RFC 2328 16.1. calculating shortest paths for an area */
682
static void
683
ospf_rt_spfa(struct ospf_area *oa)
684
{
685
  struct ospf_proto *p = oa->po;
686
  struct top_hash_entry *act;
687
  node *n;
688

    
689
  if (oa->rt == NULL)
690
    return;
691
  if (oa->rt->lsa.age == LSA_MAXAGE)
692
    return;
693

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

    
696
  /* 16.1. (1) */
697
  init_list(&oa->cand);                /* Empty list of candidates */
698
  oa->trcap = 0;
699

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

    
702
  oa->rt->dist = 0;
703
  oa->rt->color = CANDIDATE;
704
  add_head(&oa->cand, &oa->rt->cn);
705
  DBG("RT LSA: rt: %R, id: %R, type: %u\n",
706
      oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa_type);
707

    
708
  while (!EMPTY_LIST(oa->cand))
709
  {
710
    n = HEAD(oa->cand);
711
    act = SKIP_BACK(struct top_hash_entry, cn, n);
712
    rem_node(n);
713

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

    
717
    act->color = INSPF;
718
    switch (act->lsa_type)
719
    {
720
    case LSA_T_RT:
721
      spfa_process_rt(p, oa, act);
722
      break;
723

    
724
    case LSA_T_NET:
725
      spfa_process_net(p, oa, act);
726
      break;
727

    
728
    default:
729
      log(L_WARN "%s: Unknown LSA type in SPF: %d", p->p.name, act->lsa_type);
730
    }
731
  }
732

    
733
  if (ospf_is_v3(p))
734
    spfa_process_prefixes(p, oa);
735
}
736

    
737
static int
738
link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par)
739
{
740
  struct ospf_proto *p = oa->po;
741
  struct ospf_lsa_rt_walk rtl;
742
  struct top_hash_entry *tmp;
743
  struct ospf_lsa_net *ln;
744
  u32 i, cnt;
745

    
746
  if (!en || !par) return 0;
747

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

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

    
758
  en->lb = IPA_NONE;
759
  en->lb_id = 0;
760

    
761
  switch (en->lsa_type)
762
  {
763
  case LSA_T_RT:
764
    lsa_walk_rt_init(p, en, &rtl);
765
    while (lsa_walk_rt(&rtl))
766
    {
767
      switch (rtl.type)
768
      {
769
      case LSART_STUB:
770
        break;
771

    
772
      case LSART_NET:
773
        tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
774
        if (tmp == par)
775
        {
776
          if (ospf_is_v2(p))
777
            en->lb = ipa_from_u32(rtl.data);
778
          else
779
            en->lb_id = rtl.lif;
780

    
781
          return 1;
782
        }
783
        break;
784

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

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

    
807
  default:
808
    log(L_WARN "%s: Unknown LSA type in SPF: %d", p->p.name, en->lsa_type);
809
  }
810
  return 0;
811
}
812

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

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

    
829
  WALK_SLIST(en, p->lsal)
830
  {
831
    if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
832
      continue;
833

    
834
    if (en->domain != oa->areaid)
835
      continue;
836

    
837
    /* 16.2. (1a) */
838
    if (en->lsa.age == LSA_MAXAGE)
839
      continue;
840

    
841
    /* 16.2. (2) */
842
    if (en->lsa.rt == p->router_id)
843
      continue;
844

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

    
847
    if (en->lsa_type == LSA_T_SUM_NET)
848
    {
849
      lsa_parse_sum_net(en, ospf_is_v2(p), &ip, &pxlen, &pxopts, &metric);
850

    
851
      if (pxopts & OPT_PX_NU)
852
        continue;
853

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

    
861
      options = 0;
862
      type = ORT_NET;
863
    }
864
    else /* LSA_T_SUM_RT */
865
    {
866
      lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);
867
      
868
      /* We don't want local router in ASBR routing table */
869
      if (dst_rid == p->router_id)
870
        continue;
871

    
872
      options |= ORTA_ASBR;
873
      type = ORT_ROUTER;
874
    }
875

    
876
    /* 16.2. (1b) */
877
    if (metric == LSINFINITY)
878
      continue;
879

    
880
    /* 16.2. (4) */
881
    abrip = ipa_from_rid(en->lsa.rt);
882
    abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
883
    if (!abr || !abr->n.type)
884
      continue;
885

    
886
    if (!(abr->n.options & ORTA_ABR))
887
      continue;
888

    
889
    /* This check is not mentioned in RFC 2328 */
890
    if (abr->n.type != RTS_OSPF)
891
      continue;
892

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

    
905
    if (type == ORT_NET)
906
      ri_install_net(p, ip, pxlen, &nf);
907
    else
908
      ri_install_rt(oa, dst_rid, &nf);
909
  }
910
}
911

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

    
925

    
926
  if (!bb)
927
    return;
928

    
929
  WALK_SLIST(en, p->lsal)
930
  {
931
    if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
932
      continue;
933

    
934
    if (en->domain != oa->areaid)
935
      continue;
936

    
937
    /* 16.3 (1a) */
938
    if (en->lsa.age == LSA_MAXAGE)
939
      continue;
940

    
941
    /* 16.3 (2) */
942
    if (en->lsa.rt == p->router_id)
943
      continue;
944

    
945
    if (en->lsa_type == LSA_T_SUM_NET)
946
    {
947
      lsa_parse_sum_net(en, ospf_is_v2(p), &ip, &pxlen, &pxopts, &metric);
948

    
949
      if (pxopts & OPT_PX_NU)
950
        continue;
951

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

    
959
      re = fib_find(&p->rtf, &ip, pxlen);
960
    }
961
    else // en->lsa_type == LSA_T_SUM_RT
962
    {
963
      lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);
964

    
965
      ip = ipa_from_rid(dst_rid);
966
      re = fib_find(&bb->rtr, &ip, MAX_PREFIX_LENGTH);
967
    }
968

    
969
    /* 16.3 (1b) */ 
970
    if (metric == LSINFINITY) 
971
      continue; 
972

    
973
    /* 16.3 (3) */
974
    if (!re || !re->n.type)
975
      continue;
976

    
977
    if (re->n.oa->areaid != 0)
978
      continue;
979

    
980
    if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA))
981
      continue;
982

    
983
    /* 16.3. (4) */
984
    abrip = ipa_from_rid(en->lsa.rt);
985
    abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
986
    if (!abr || !abr->n.type)
987
      continue;
988

    
989
    metric = abr->n.metric1 + metric; /* IAC */
990

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

    
1001
      re->n.metric1 = metric;
1002
      re->n.voa = oa;
1003
      re->n.nhs = abr->n.nhs;
1004
    }
1005
  }
1006
}
1007

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

    
1016
  if (oa == anet_oa)
1017
    return 0;
1018

    
1019
  /* Do not condense routing info when exporting from backbone to the transit area */
1020
  if ((anet_oa == oa->po->backbone) && oa->trcap)
1021
    return 0;
1022

    
1023
  return (anet->active && !anet->hidden);
1024
}
1025

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

    
1034
  /* Invalid field - no route */
1035
  if (!nf->n.type)
1036
    return 0;
1037

    
1038
  /* 12.4.3 p2 */
1039
  if (nf->n.type > RTS_OSPF_IA)
1040
    return 0;
1041

    
1042
  /* 12.4.3 p3 */
1043
  if ((nf->n.oa->areaid == oa->areaid))
1044
    return 0;
1045

    
1046
  /* 12.4.3 p4 */
1047
  if (nf->n.voa && (nf->n.voa->areaid == oa->areaid))
1048
    return 0;
1049

    
1050
  /* 12.4.3 p5 */
1051
  if (nf->n.metric1 >= LSINFINITY)
1052
    return 0;
1053

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

    
1062
  /* 12.4.3 p7 - inter-area route */
1063
  if (nf->n.type == RTS_OSPF_IA)
1064
  {
1065
    /* Inter-area routes are not repropagated into the backbone */
1066
    return (oa != oa->po->backbone);
1067
  }
1068

    
1069
  /* 12.4.3 p8 - intra-area route */
1070

    
1071
  /* Do not condense routing info when exporting from backbone to the transit area */
1072
  if ((nf->n.oa == oa->po->backbone) && oa->trcap)
1073
    return 1;
1074

    
1075
  struct area_net *anet = (struct area_net *)
1076
    fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen);
1077

    
1078
  /* Condensed area network found */ 
1079
  if (anet)
1080
    return 0;
1081

    
1082
  return 1;
1083
}
1084

    
1085
/* RFC 2328 16.7. p1 - originate or flush summary LSAs */
1086
static inline void
1087
check_sum_net_lsa(struct ospf_proto *p, ort *nf)
1088
{
1089
  struct area_net *anet = NULL;
1090
  struct ospf_area *anet_oa = NULL;
1091

    
1092
  if (nf->area_net)
1093
  {
1094
    /* It is a default route for stub areas, handled entirely in ospf_rt_abr() */
1095
    if (nf->fn.pxlen == 0)
1096
      return;
1097

    
1098
    /* Find that area network */
1099
    WALK_LIST(anet_oa, p->area_list)
1100
    {
1101
      anet = (struct area_net *) fib_find(&anet_oa->net_fib, &nf->fn.prefix, nf->fn.pxlen);
1102
      if (anet)
1103
        break;
1104
    }
1105
  }
1106

    
1107
  struct ospf_area *oa;
1108
  WALK_LIST(oa, p->area_list)
1109
  {
1110
    if (anet && decide_anet_lsa(oa, anet, anet_oa))
1111
      ospf_originate_sum_net_lsa(p, oa, nf, anet->metric);
1112
    else if (decide_sum_lsa(oa, nf, ORT_NET))
1113
      ospf_originate_sum_net_lsa(p, oa, nf, nf->n.metric1);
1114
  }
1115
}
1116

    
1117
static inline void
1118
check_sum_rt_lsa(struct ospf_proto *p, ort *nf)
1119
{
1120
  struct ospf_area *oa;
1121
  WALK_LIST(oa, p->area_list)
1122
    if (decide_sum_lsa(oa, nf, ORT_ROUTER))
1123
      ospf_originate_sum_rt_lsa(p, oa, nf, nf->n.metric1, nf->n.options);
1124
}
1125

    
1126
static inline int
1127
decide_nssa_lsa(struct ospf_proto *p, ort *nf, struct ospf_lsa_ext_local *rt)
1128
{
1129
  struct ospf_area *oa = nf->n.oa;
1130
  struct top_hash_entry *en = nf->n.en;
1131

    
1132
  if (!rt_is_nssa(nf) || !oa->translate)
1133
    return 0;
1134

    
1135
  /* Condensed area network found */ 
1136
  if (fib_route(&oa->enet_fib, nf->fn.prefix, nf->fn.pxlen))
1137
    return 0;
1138

    
1139
  if (!en || (en->lsa_type != LSA_T_NSSA))
1140
    return 0;
1141

    
1142
  /* We do not store needed data in struct orta, we have to parse the LSA */
1143
  lsa_parse_ext(en, ospf_is_v2(p), rt);
1144
  
1145
  if (rt->pxopts & OPT_PX_NU)
1146
    return 0;
1147

    
1148
  if (!rt->propagate || ipa_zero(rt->fwaddr))
1149
    return 0;
1150

    
1151
  return 1;
1152
}
1153

    
1154
/* RFC 3103 3.2 - translating Type-7 LSAs into Type-5 LSAs */
1155
static inline void
1156
check_nssa_lsa(struct ospf_proto *p, ort *nf)
1157
{
1158
  struct area_net *anet = NULL;
1159
  struct ospf_area *oa = NULL;
1160
  struct ospf_lsa_ext_local rt;
1161

    
1162
  /* Do not translate LSA if there is already the external LSA from route export */
1163
  if (nf->external_rte)
1164
    return;
1165

    
1166
  if (nf->area_net)
1167
  {
1168
    /* Find that area network */
1169
    WALK_LIST(oa, p->area_list)
1170
    {
1171
      anet = (struct area_net *) fib_find(&oa->enet_fib, &nf->fn.prefix, nf->fn.pxlen);
1172
      if (anet)
1173
        break;
1174
    }
1175
  }
1176

    
1177
  /* RFC 3103 3.2 (3) - originate the aggregated address range */
1178
  if (anet && anet->active && !anet->hidden && oa->translate)
1179
    ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, anet->metric,
1180
                           (anet->metric & LSA_EXT3_EBIT), IPA_NONE, anet->tag, 0);
1181

    
1182
  /* RFC 3103 3.2 (2) - originate the same network */
1183
  else if (decide_nssa_lsa(p, nf, &rt))
1184
    ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, rt.metric, rt.ebit, rt.fwaddr, rt.tag, 0);
1185
}
1186

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

    
1199
      if (tmp && (tmp->color == INSPF) && ipa_nonzero(tmp->lb) && tmp->nhs)
1200
      {
1201
        struct ospf_iface *nhi = ospf_iface_find(p, tmp->nhs->iface);
1202

    
1203
        if ((ifa->state != OSPF_IS_PTP)
1204
            || (ifa->vifa != nhi)
1205
            || !ipa_equal(ifa->vip, tmp->lb))
1206
        {
1207
          OSPF_TRACE(D_EVENTS, "Vlink peer %R found", tmp->lsa.id);
1208
          ospf_iface_sm(ifa, ISM_DOWN);
1209
          ifa->vifa = nhi;
1210
          ifa->addr = nhi->addr;
1211
          ifa->cost = tmp->dist;
1212
          ifa->vip = tmp->lb;
1213
          ospf_iface_sm(ifa, ISM_UP);
1214
        }
1215
        else if ((ifa->state == OSPF_IS_PTP) && (ifa->cost != tmp->dist))
1216
        {
1217
          ifa->cost = tmp->dist;
1218

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

    
1235

    
1236
/* Miscellaneous route processing that needs to be done by ABRs */
1237
static void
1238
ospf_rt_abr1(struct ospf_proto *p)
1239
{
1240
  struct area_net *anet;
1241
  ort *nf, *default_nf;
1242

    
1243
  /* RFC 2328 G.3 - incomplete resolution of virtual next hops - routers */
1244
  FIB_WALK(&p->backbone->rtr, nftmp)
1245
  {
1246
    nf = (ort *) nftmp;
1247

    
1248
    if (nf->n.type && unresolved_vlink(nf))
1249
      reset_ri(nf);
1250
  }
1251
  FIB_WALK_END;
1252

    
1253

    
1254
  FIB_WALK(&p->rtf, nftmp)
1255
  {
1256
    nf = (ort *) nftmp;
1257

    
1258

    
1259
    /* RFC 2328 G.3 - incomplete resolution of virtual next hops - networks */
1260
    if (nf->n.type && unresolved_vlink(nf))
1261
      reset_ri(nf);
1262

    
1263

    
1264
    /* Compute condensed area networks */
1265
    if (nf->n.type == RTS_OSPF)
1266
    {
1267
      anet = (struct area_net *) fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen);
1268
      if (anet)
1269
      {
1270
        if (!anet->active)
1271
        {
1272
          anet->active = 1;
1273

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

    
1278
          /* 16.2. (3) */
1279
          if (nfi->n.type == RTS_OSPF_IA)
1280
            reset_ri(nfi);
1281
        }
1282

    
1283
        if (anet->metric < nf->n.metric1)
1284
          anet->metric = nf->n.metric1;
1285
      }
1286
    }
1287
  }
1288
  FIB_WALK_END;
1289

    
1290
  ip_addr addr = IPA_NONE;
1291
  default_nf = (ort *) fib_get(&p->rtf, &addr, 0);
1292
  default_nf->area_net = 1;
1293

    
1294
  struct ospf_area *oa;
1295
  WALK_LIST(oa, p->area_list)
1296
  {
1297

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

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

    
1311
    if (oa_is_nssa(oa) && oa->ac->default_nssa)
1312
      ospf_originate_ext_lsa(p, oa, default_nf, LSA_M_RTCALC, oa->ac->default_cost,
1313
                             (oa->ac->default_cost & LSA_EXT3_EBIT), IPA_NONE, 0, 0);
1314

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

    
1328

    
1329
  /* Originate or flush ASBR summary LSAs */
1330
  FIB_WALK(&p->backbone->rtr, nftmp)
1331
  {
1332
    check_sum_rt_lsa(p, (ort *) nftmp);
1333
  }
1334
  FIB_WALK_END;
1335

    
1336

    
1337
  /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1338
  ospf_check_vlinks(p);
1339
}
1340

    
1341

    
1342
static void
1343
translator_timer_hook(timer *timer)
1344
{
1345
  struct ospf_area *oa = timer->data;
1346
  
1347
  if (oa->translate != TRANS_WAIT)
1348
    return;
1349

    
1350
  oa->translate = TRANS_OFF;
1351
  ospf_schedule_rtcalc(oa->po);
1352
}
1353

    
1354
static void
1355
ospf_rt_abr2(struct ospf_proto *p)
1356
{
1357
  struct ospf_area *oa;
1358
  struct top_hash_entry *en;
1359
  ort *nf, *nf2;
1360

    
1361

    
1362
  /* RFC 3103 3.1 - type-7 translator election */
1363
  struct ospf_area *bb = p->backbone;
1364
  WALK_LIST(oa, p->area_list)
1365
    if (oa_is_nssa(oa))
1366
    {
1367
      int translate = 1;
1368

    
1369
      if (oa->ac->translator)
1370
        goto decided;
1371

    
1372
      FIB_WALK(&oa->rtr, nftmp)
1373
      {
1374
        nf = (ort *) nftmp;
1375
        if (!nf->n.type || !(nf->n.options & ORTA_ABR))
1376
          continue;
1377

    
1378
        nf2 = fib_find(&bb->rtr, &nf->fn.prefix, MAX_PREFIX_LENGTH);
1379
        if (!nf2 || !nf2->n.type || !(nf2->n.options & ORTA_ABR))
1380
          continue;
1381

    
1382
        en = ospf_hash_find_rt(p->gr, oa->areaid, nf->n.rid);
1383
        if (!en || (en->color != INSPF))
1384
          continue;
1385

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

    
1396
    decided:
1397
      if (translate && (oa->translate != TRANS_ON))
1398
      {
1399
        if (oa->translate == TRANS_WAIT)
1400
          tm_stop(oa->translator_timer);
1401

    
1402
        oa->translate = TRANS_ON;
1403
      }
1404

    
1405
      if (!translate && (oa->translate == TRANS_ON))
1406
      {
1407
        if (oa->translator_timer == NULL)
1408
          oa->translator_timer = tm_new_set(p->p.pool, translator_timer_hook, oa, 0, 0);
1409

    
1410
        /* Schedule the end of translation */
1411
        tm_start(oa->translator_timer, oa->ac->transint);
1412
        oa->translate = TRANS_WAIT;
1413
      }
1414
    }
1415

    
1416

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

    
1426
      if (anet)
1427
      {
1428
        if (!anet->active)
1429
        {
1430
          anet->active = 1;
1431

    
1432
          /* Get a RT entry and mark it to know that it is an area network */
1433
          nf2 = (ort *) fib_get(&p->rtf, &anet->fn.prefix, anet->fn.pxlen);
1434
          nf2->area_net = 1;
1435
        }
1436

    
1437
        u32 metric = (nf->n.type == RTS_OSPF_EXT1) ?
1438
          nf->n.metric1 : ((nf->n.metric2 + 1) | LSA_EXT3_EBIT);
1439

    
1440
        if (anet->metric < metric)
1441
          anet->metric = metric;
1442
      }
1443
    }
1444
  }
1445
  FIB_WALK_END;
1446

    
1447

    
1448
  FIB_WALK(&p->rtf, nftmp)
1449
  {
1450
    nf = (ort *) nftmp;
1451

    
1452
    check_sum_net_lsa(p, nf);
1453
    check_nssa_lsa(p, nf);
1454
  }
1455
  FIB_WALK_END;
1456
}
1457

    
1458

    
1459
/* Like fib_route(), but ignores dummy rt entries */
1460
static void *
1461
ospf_fib_route(struct fib *f, ip_addr a, int len)
1462
{
1463
  ip_addr a0;
1464
  ort *nf;
1465

    
1466
  while (len >= 0)
1467
  {
1468
    a0 = ipa_and(a, ipa_mkmask(len));
1469
    nf = fib_find(f, &a0, len);
1470
    if (nf && nf->n.type)
1471
      return nf;
1472
    len--;
1473
  }
1474
  return NULL;
1475
}
1476

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

    
1489
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
1490

    
1491
  WALK_SLIST(en, p->lsal)
1492
  {
1493
    /* 16.4. (1) */
1494
    if ((en->lsa_type != LSA_T_EXT) && (en->lsa_type != LSA_T_NSSA))
1495
      continue;
1496

    
1497
    if (en->lsa.age == LSA_MAXAGE)
1498
      continue;
1499

    
1500
    /* 16.4. (2) */
1501
    if (en->lsa.rt == p->router_id)
1502
      continue;
1503

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

    
1507
    lsa_parse_ext(en, ospf_is_v2(p), &rt);
1508

    
1509
    if (rt.metric == LSINFINITY)
1510
      continue;
1511

    
1512
    if (rt.pxopts & OPT_PX_NU)
1513
      continue;
1514

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

    
1522

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

    
1532
    if (!atmp)
1533
      continue;                        /* Should not happen */
1534

    
1535
    rtid = ipa_from_rid(en->lsa.rt);
1536
    nf1 = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH);
1537

    
1538
    if (!nf1 || !nf1->n.type)
1539
      continue;                        /* No AS boundary router found */
1540

    
1541
    if (!(nf1->n.options & ORTA_ASBR))
1542
      continue;                        /* It is not ASBR */
1543

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

    
1550
    if (!rt.fbit)
1551
    {
1552
      nf2 = nf1;
1553
      nfa.nhs = nf1->n.nhs;
1554
      br_metric = nf1->n.metric1;
1555
    }
1556
    else
1557
    {
1558
      nf2 = ospf_fib_route(&p->rtf, rt.fwaddr, MAX_PREFIX_LENGTH);
1559
      if (!nf2)
1560
        continue;
1561

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

    
1575
      /* Next-hop is a part of a configured stubnet */
1576
      if (!nf2->n.nhs)
1577
        continue;
1578

    
1579
      nfa.nhs = nf2->n.nhs;
1580
      br_metric = nf2->n.metric1;
1581

    
1582
      /* Replace device nexthops with nexthops to forwarding address from LSA */
1583
      if (has_device_nexthops(nfa.nhs))
1584
      {
1585
        nfa.nhs = fix_device_nexthops(p, nfa.nhs, rt.fwaddr);
1586
        nfa.nhs_reuse = 1;
1587
      }
1588
    }
1589

    
1590
    if (rt.ebit)
1591
    {
1592
      nfa.type = RTS_OSPF_EXT2;
1593
      nfa.metric1 = br_metric;
1594
      nfa.metric2 = rt.metric;
1595
    }
1596
    else
1597
    {
1598
      nfa.type = RTS_OSPF_EXT1;
1599
      nfa.metric1 = br_metric + rt.metric;
1600
      nfa.metric2 = LSINFINITY;
1601
    }
1602

    
1603
    /* Mark the LSA as reachable */
1604
    en->color = INSPF;
1605

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

    
1615
    nfa.tag = rt.tag;
1616
    nfa.rid = en->lsa.rt;
1617
    nfa.oa = atmp; /* undefined in RFC 2328 */
1618
    nfa.en = en; /* store LSA for later (NSSA processing) */
1619

    
1620
    ri_install_ext(p, rt.ip, rt.pxlen, &nfa);
1621
  }
1622
}
1623

    
1624
/* Cleanup of routing tables and data */
1625
void
1626
ospf_rt_reset(struct ospf_proto *p)
1627
{
1628
  struct ospf_area *oa;
1629
  struct top_hash_entry *en;
1630
  struct area_net *anet;
1631
  ort *ri;
1632

    
1633
  /* Reset old routing table */
1634
  FIB_WALK(&p->rtf, nftmp)
1635
  {
1636
    ri = (ort *) nftmp;
1637
    ri->area_net = 0;
1638
    reset_ri(ri);
1639
  }
1640
  FIB_WALK_END;
1641

    
1642
  /* Reset SPF data in LSA db */
1643
  WALK_SLIST(en, p->lsal)
1644
  {
1645
    en->color = OUTSPF;
1646
    en->dist = LSINFINITY;
1647
    en->nhs = NULL;
1648
    en->lb = IPA_NONE;
1649

    
1650
    if (en->mode == LSA_M_RTCALC)
1651
      en->mode = LSA_M_STALE;
1652
  }
1653

    
1654
  WALK_LIST(oa, p->area_list)
1655
  {
1656
    /* Reset ASBR routing tables */
1657
    FIB_WALK(&oa->rtr, nftmp)
1658
    {
1659
      ri = (ort *) nftmp;
1660
      reset_ri(ri);
1661
    }
1662
    FIB_WALK_END;
1663

    
1664
    /* Reset condensed area networks */
1665
    if (p->areano > 1)
1666
    {
1667
      FIB_WALK(&oa->net_fib, nftmp)
1668
      {
1669
        anet = (struct area_net *) nftmp;
1670
        anet->active = 0;
1671
        anet->metric = 0;
1672
      }
1673
      FIB_WALK_END;
1674

    
1675
      FIB_WALK(&oa->enet_fib, nftmp)
1676
      {
1677
        anet = (struct area_net *) nftmp;
1678
        anet->active = 0;
1679
        anet->metric = 0;
1680
      }
1681
      FIB_WALK_END;
1682
    }
1683
  }
1684
}
1685

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

    
1699
  if (p->areano == 0)
1700
    return;
1701

    
1702
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
1703

    
1704
  /* 16. (1) */
1705
  ospf_rt_reset(p);
1706

    
1707
  /* 16. (2) */
1708
  WALK_LIST(oa, p->area_list)
1709
    ospf_rt_spfa(oa);
1710

    
1711
  /* 16. (3) */
1712
  ospf_rt_sum(ospf_main_area(p));
1713

    
1714
  /* 16. (4) */
1715
  WALK_LIST(oa, p->area_list)
1716
    if (oa->trcap && (oa->areaid != 0))
1717
      ospf_rt_sum_tr(oa);
1718

    
1719
  if (p->areano > 1)
1720
    ospf_rt_abr1(p);
1721

    
1722
  /* 16. (5) */
1723
  ospf_ext_spf(p);
1724

    
1725
  if (p->areano > 1)
1726
    ospf_rt_abr2(p);
1727

    
1728
  rt_sync(p);
1729
  lp_flush(p->nhpool);
1730
  
1731
  p->calcrt = 0;
1732
}
1733

    
1734

    
1735
static inline int
1736
inherit_nexthops(struct mpnh *pn)
1737
{
1738
  /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */
1739
  return pn && (ipa_nonzero(pn->gw) || !pn->iface);
1740
}
1741

    
1742
static struct mpnh *
1743
calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
1744
              struct top_hash_entry *par, int pos)
1745
{
1746
  struct ospf_proto *p = oa->po;
1747
  struct mpnh *pn = par->nhs;
1748
  struct ospf_iface *ifa;
1749
  u32 rid = en->lsa.rt;
1750

    
1751
  /* 16.1.1. The next hop calculation */
1752
  DBG("     Next hop calculating for id: %R rt: %R type: %u\n",
1753
      en->lsa.id, en->lsa.rt, en->lsa_type);
1754

    
1755
  /* Usually, we inherit parent nexthops */
1756
  if (inherit_nexthops(pn))
1757
    return pn;
1758

    
1759
  /* 
1760
   * There are three cases:
1761
   * 1) en is a local network (and par is root)
1762
   * 2) en is a ptp or ptmp neighbor (and par is root)
1763
   * 3) en is a bcast or nbma neighbor (and par is local network)
1764
   */
1765

    
1766
  /* The first case - local network */
1767
  if ((en->lsa_type == LSA_T_NET) && (par == oa->rt))
1768
  {
1769
    ifa = rt_pos_to_ifa(oa, pos);
1770
    if (!ifa)
1771
      return NULL;
1772

    
1773
    return new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight);
1774
  }
1775

    
1776
  /* The second case - ptp or ptmp neighbor */
1777
  if ((en->lsa_type == LSA_T_RT) && (par == oa->rt))
1778
  {
1779
    ifa = rt_pos_to_ifa(oa, pos);
1780
    if (!ifa)
1781
      return NULL;
1782

    
1783
    if (ifa->type == OSPF_IT_VLINK)
1784
      return new_nexthop(p, IPA_NONE, NULL, 0);
1785

    
1786
    struct ospf_neighbor *m = find_neigh(ifa, rid);
1787
    if (!m || (m->state != NEIGHBOR_FULL))
1788
      return NULL;
1789

    
1790
    return new_nexthop(p, m->ip, ifa->iface, ifa->ecmp_weight);
1791
  }
1792

    
1793
  /* The third case - bcast or nbma neighbor */
1794
  if ((en->lsa_type == LSA_T_RT) && (par->lsa_type == LSA_T_NET))
1795
  {
1796
    /* par->nhi should be defined from parent's calc_next_hop() */
1797
    if (!pn)
1798
      goto bad;
1799

    
1800
    if (ospf_is_v2(p))
1801
    {
1802
      /*
1803
       * In this case, next-hop is the same as link-back, which is
1804
       * already computed in link_back().
1805
       */
1806
      if (ipa_zero(en->lb))
1807
        goto bad;
1808

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

    
1820
      if (!lhe)
1821
        return NULL;
1822

    
1823
      struct ospf_lsa_link *llsa = lhe->lsa_body;
1824
      
1825
      if (ipa_zero(llsa->lladdr))
1826
        return NULL;
1827

    
1828
      return new_nexthop(p, llsa->lladdr, pn->iface, pn->weight);
1829
    }
1830
  }
1831

    
1832
 bad:
1833
  /* Probably bug or some race condition, we log it */
1834
  log(L_ERR "Unexpected case in next hop calculation");
1835
  return NULL;
1836
}
1837

    
1838

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

    
1849
  /* 16.1. (2b) */
1850
  if (en == NULL)
1851
    return;
1852
  if (en->lsa.age == LSA_MAXAGE)
1853
    return;
1854

    
1855
  if (ospf_is_v3(p) && (en->lsa_type == LSA_T_RT))
1856
  {
1857
    /* In OSPFv3, check V6 flag */
1858
    struct ospf_lsa_rt *rt = en->lsa_body;
1859
    if (!(rt->options & OPT_V6))
1860
      return;
1861
  }
1862

    
1863
  /* 16.1. (2c) */
1864
  if (en->color == INSPF)
1865
    return;
1866

    
1867
  /* 16.1. (2d), also checks that dist < LSINFINITY */
1868
  if (dist > en->dist)
1869
    return;
1870

    
1871
  /* We should check whether there is a reverse link from en to par, */
1872
  if (!link_back(oa, en, par))
1873
    return;
1874

    
1875
  struct mpnh *nhs = calc_next_hop(oa, en, par, pos);
1876
  if (!nhs)
1877
  {
1878
    log(L_WARN "Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
1879
        en->lsa_type, en->lsa.id, en->lsa.rt);
1880
    return;
1881
  }
1882

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

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

    
1901
    /* Keep old ones */
1902
    if (!p->ecmp || nh_is_vlink(nhs) || (nhs == en->nhs))
1903
      return;
1904

    
1905
    /* Merge old and new */
1906
    int new_reuse = (par->nhs != nhs);
1907
    en->nhs = merge_nexthops(p, en->nhs, nhs, en->nhs_reuse, new_reuse);
1908
    en->nhs_reuse = 1;
1909
    return;
1910
  }
1911

    
1912
  DBG("     Adding candidate: rt: %R, id: %R, type: %u\n",
1913
      en->lsa.rt, en->lsa.id, en->lsa_type);
1914

    
1915
  if (en->color == CANDIDATE)
1916
  {                                /* We found a shorter path */
1917
    rem_node(&en->cn);
1918
  }
1919
  en->nhs = nhs;
1920
  en->dist = dist;
1921
  en->color = CANDIDATE;
1922
  en->nhs_reuse = (par->nhs != nhs);
1923

    
1924
  prev = NULL;
1925

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

    
1948
    if (!added)
1949
    {
1950
      add_tail(l, &en->cn);
1951
    }
1952
  }
1953
}
1954

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

    
1967
static void
1968
rt_sync(struct ospf_proto *p)
1969
{
1970
  struct top_hash_entry *en;
1971
  struct fib_iterator fit;
1972
  struct fib *fib = &p->rtf;
1973
  ort *nf;
1974
  struct ospf_area *oa;
1975

    
1976
  /* This is used for forced reload of routes */
1977
  int reload = (p->calcrt == 2);
1978

    
1979
  OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation");
1980

    
1981
  DBG("Now syncing my rt table with nest's\n");
1982
  FIB_ITERATE_INIT(&fit, fib);
1983
again1:
1984
  FIB_ITERATE_START(fib, &fit, nftmp)
1985
  {
1986
    nf = (ort *) nftmp;
1987

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

    
2001
    /* Remove configured stubnets */
2002
    if (!nf->n.nhs)
2003
      reset_ri(nf);
2004

    
2005
    if (nf->n.type) /* Add the route */
2006
    {
2007
      rta a0 = {
2008
        .src = p->p.main_source,
2009
        .source = nf->n.type,
2010
        .scope = SCOPE_UNIVERSE,
2011
        .cast = RTC_UNICAST
2012
      };
2013

    
2014
      if (nf->n.nhs->next)
2015
      {
2016
        a0.dest = RTD_MULTIPATH;
2017
        a0.nexthops = nf->n.nhs;
2018
      }
2019
      else if (ipa_nonzero(nf->n.nhs->gw))
2020
      {
2021
        a0.dest = RTD_ROUTER;
2022
        a0.iface = nf->n.nhs->iface;
2023
        a0.gw = nf->n.nhs->gw;
2024
      }
2025
      else
2026
      {
2027
        a0.dest = RTD_DEVICE;
2028
        a0.iface = nf->n.nhs->iface;
2029
      }
2030

    
2031
      if (reload || ort_changed(nf, &a0))
2032
      {
2033
        net *ne = net_get(p->p.table, nf->fn.prefix, nf->fn.pxlen);
2034
        rta *a = rta_lookup(&a0);
2035
        rte *e = rte_get_temp(a);
2036

    
2037
        rta_free(nf->old_rta);
2038
        nf->old_rta = rta_clone(a);
2039
        e->u.ospf.metric1 = nf->old_metric1 = nf->n.metric1;
2040
        e->u.ospf.metric2 = nf->old_metric2 = nf->n.metric2;
2041
        e->u.ospf.tag = nf->old_tag = nf->n.tag;
2042
        e->u.ospf.router_id = nf->old_rid = nf->n.rid;
2043
        e->pflags = 0;
2044
        e->net = ne;
2045
        e->pref = p->p.preference;
2046

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

    
2058
      net *ne = net_get(p->p.table, nf->fn.prefix, nf->fn.pxlen);
2059
      rte_update(&p->p, ne, NULL);
2060
    }
2061

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

    
2072

    
2073
  WALK_LIST(oa, p->area_list)
2074
  {
2075
    /* Cleanup ASBR hash tables */
2076
    FIB_ITERATE_INIT(&fit, &oa->rtr);
2077
again2:
2078
    FIB_ITERATE_START(&oa->rtr, &fit, nftmp)
2079
    {
2080
      nf = (ort *) nftmp;
2081

    
2082
      if (!nf->n.type)
2083
      {
2084
        FIB_ITERATE_PUT(&fit, nftmp);
2085
        fib_delete(&oa->rtr, nftmp);
2086
        goto again2;
2087
      }
2088
    }
2089
    FIB_ITERATE_END(nftmp);
2090
  }
2091

    
2092
  /* Cleanup stale LSAs */
2093
  WALK_SLIST(en, p->lsal)
2094
    if (en->mode == LSA_M_STALE)
2095
      ospf_flush_lsa(p, en);
2096
}