Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / rt.c @ 145368f5

History | View | Annotate | Download (52.8 KB)

1
/*
2
 * BIRD -- OSPF
3
 * 
4
 * (c) 2000--2004 Ondrej Filip <feela@network.cz>
5
 * 
6
 * Can be freely distributed and used under the terms of the GNU GPL.
7
 */
8

    
9
#include "ospf.h"
10

    
11
static void add_cand(list * l, struct top_hash_entry *en, 
12
                     struct top_hash_entry *par, u32 dist,
13
                     struct ospf_area *oa, int i);
14
static void rt_sync(struct proto_ospf *po);
15

    
16
/* In ospf_area->rtr we store paths to routers, but we use RID (and not IP address)
17
   as index, so we need to encapsulate RID to IP address */
18
#ifdef OSPFv2
19
#define ipa_from_rid(x) _MI(x)
20
#else /* OSPFv3 */
21
#define ipa_from_rid(x) _MI(0,0,0,x)
22
#endif
23

    
24

    
25
static inline void reset_ri(ort *ort)
26
{
27
  bzero(&ort->n, sizeof(orta));
28
}
29

    
30
void
31
ospf_rt_initort(struct fib_node *fn)
32
{
33
  ort *ri = (ort *) fn;
34
  reset_ri(ri);
35
  ri->old_rta = NULL;
36
  ri->fn.x0 = ri->fn.x1 = 0;
37
}
38

    
39
static inline int
40
nh_is_vlink(struct mpnh *nhs)
41
{
42
  return !nhs->iface;
43
}
44

    
45
static inline int
46
unresolved_vlink(ort *ort)
47
{
48
  return ort->n.nhs && nh_is_vlink(ort->n.nhs);
49
}
50

    
51
static inline struct mpnh *
52
new_nexthop(struct proto_ospf *po, ip_addr gw, struct iface *iface, unsigned char weight)
53
{
54
  struct mpnh *nh = lp_alloc(po->nhpool, sizeof(struct mpnh));
55
  nh->gw = gw;
56
  nh->iface = iface;
57
  nh->next = NULL;
58
  nh->weight = weight;
59
  return nh;
60
}
61

    
62
static inline struct mpnh *
63
copy_nexthop(struct proto_ospf *po, const struct mpnh *src)
64
{
65
  struct mpnh *nh = lp_alloc(po->nhpool, sizeof(struct mpnh));
66
  nh->gw = src->gw;
67
  nh->iface = src->iface;
68
  nh->next = NULL;
69
  nh->weight = src->weight;
70
  return nh;
71
}
72

    
73
/* Compare nexthops during merge.
74
   We need to maintain nhs sorted to eliminate duplicities */
75
static int
76
cmp_nhs(struct mpnh *s1, struct mpnh *s2)
77
{
78
  int r;
79

    
80
  if (!s1)
81
    return 1;
82

    
83
  if (!s2)
84
    return -1;
85

    
86
  r = ((int) s2->weight) - ((int) s1->weight);
87
  if (r)
88
    return r;
89

    
90
  r = ipa_compare(s1->gw, s2->gw);
91
  if (r)
92
    return r;
93

    
94
  return ((int) s1->iface->index) - ((int) s2->iface->index);
95
}
96

    
97
static struct mpnh *
98
merge_nexthops(struct proto_ospf *po, struct mpnh *s1, struct mpnh *s2, int r1, int r2)
99
{
100
  struct mpnh *root = NULL;
101
  struct mpnh **n = &root;
102
  int count = po->ecmp;
103

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

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

    
139
  return root;
140
}
141

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

    
150
  return 0;
151
}
152

    
153
/* Replace device nexthops with nexthops to gw */
154
static struct mpnh *
155
fix_device_nexthops(struct proto_ospf *po, const struct mpnh *n, ip_addr gw)
156
{
157
  struct mpnh *root1 = NULL;
158
  struct mpnh *root2 = NULL;
159
  struct mpnh **nn1 = &root1;
160
  struct mpnh **nn2 = &root2;
161

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

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

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

    
182
  return merge_nexthops(po, root1, root2, 1, 1);
183
}
184

    
185

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

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

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

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

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

    
217
  return 0;
218
}
219

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

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

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

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

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

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

    
253

    
254
  /* Rest is BIRD-specific */
255

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

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

    
272

    
273
  if (po->ecmp)
274
    return 0;
275

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

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

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

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

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

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

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

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

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

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

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

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

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

    
348

    
349
  if (po->ecmp && po->merge_external)
350
    return 0;
351

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

    
361
  return -1;
362
}
363

    
364

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

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

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

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

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

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

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

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

    
415

    
416

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

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

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

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

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

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

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

    
462
static inline struct ospf_iface *
463
rt_pos_to_ifa(struct ospf_area *oa, int pos)
464
{
465
  struct ospf_iface *ifa;
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
  return NULL;
470
}
471

    
472
#ifdef OSPFv3
473
static inline struct ospf_iface *
474
px_pos_to_ifa(struct ospf_area *oa, int pos)
475
{
476
  struct ospf_iface *ifa;
477
  WALK_LIST(ifa, oa->po->iface_list)
478
    if (ifa->oa == oa && pos >= ifa->px_pos_beg && pos < ifa->px_pos_end)
479
      return ifa;
480
  return NULL;
481
}
482
#endif
483

    
484

    
485
static void
486
add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en, int pos)
487
{
488
  orta nf = {
489
    .type = RTS_OSPF,
490
    .options = 0,
491
    .metric1 = metric,
492
    .metric2 = LSINFINITY,
493
    .tag = 0,
494
    .rid = en->lsa.rt,
495
    .oa = oa,
496
    .nhs = en->nhs
497
  };
498

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

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

    
516
    struct ospf_iface *ifa;
517
#ifdef OSPFv2
518
    ifa = rt_pos_to_ifa(oa, pos);
519
#else /* OSPFv3 */
520
    ifa = px_pos_to_ifa(oa, pos);
521
#endif
522

    
523
    nf.nhs = ifa ? new_nexthop(oa->po, IPA_NONE, ifa->iface, ifa->ecmp_weight) : NULL;
524
  }
525

    
526
  ri_install_net(oa->po, px, pxlen, &nf);
527
}
528

    
529
#ifdef OSPFv3
530
static void
531
process_prefixes(struct ospf_area *oa)
532
{
533
  struct proto_ospf *po = oa->po;
534
  // struct proto *p = &po->proto;
535
  struct top_hash_entry *en, *src;
536
  struct ospf_lsa_prefix *px;
537
  ip_addr pxa;
538
  int pxlen;
539
  u8 pxopts;
540
  u16 metric;
541
  u32 *buf;
542
  int i;
543

    
544
  WALK_SLIST(en, po->lsal)
545
  {
546
    if (en->lsa.type != LSA_T_PREFIX)
547
      continue;
548

    
549
    if (en->domain != oa->areaid)
550
      continue;
551

    
552
    if (en->lsa.age == LSA_MAXAGE)
553
      continue;
554

    
555
    px = en->lsa_body;
556

    
557
    /* For router prefix-LSA, we would like to find the first router-LSA */
558
    if (px->ref_type == LSA_T_RT)
559
      src = ospf_hash_find_rt(po->gr, oa->areaid, px->ref_rt);
560
    else
561
      src = ospf_hash_find(po->gr, oa->areaid, px->ref_id, px->ref_rt, px->ref_type);
562

    
563
    if (!src)
564
      continue;
565

    
566
    /* Reachable in SPF */
567
    if (src->color != INSPF)
568
      continue;
569

    
570
    if ((src->lsa.type != LSA_T_RT) && (src->lsa.type != LSA_T_NET))
571
      continue;
572

    
573
    buf = px->rest;
574
    for (i = 0; i < px->pxcount; i++)
575
      {
576
        buf = lsa_get_ipv6_prefix(buf, &pxa, &pxlen, &pxopts, &metric);
577

    
578
        if (pxopts & OPT_PX_NU)
579
          continue;
580

    
581
        /* Store the first global address to use it later as a vlink endpoint */
582
        if ((pxopts & OPT_PX_LA) && ipa_zero(src->lb))
583
          src->lb = pxa;
584

    
585
        add_network(oa, pxa, pxlen, src->dist + metric, src, i);
586
      }
587
  }
588
}
589
#endif
590

    
591

    
592
static void
593
ospf_rt_spfa_rtlinks(struct ospf_area *oa, struct top_hash_entry *act, struct top_hash_entry *en)
594
{
595
  // struct proto *p = &oa->po->proto;
596
  struct proto_ospf *po = oa->po;
597
  ip_addr prefix UNUSED;
598
  int pxlen UNUSED, i;
599

    
600
  struct ospf_lsa_rt *rt = en->lsa_body;
601
  struct ospf_lsa_rt_link *rr = (struct ospf_lsa_rt_link *) (rt + 1);
602

    
603
  for (i = 0; i < lsa_rt_count(&en->lsa); i++)
604
    {
605
      struct ospf_lsa_rt_link *rtl = rr + i;
606
      struct top_hash_entry *tmp = NULL;
607

    
608
      DBG("     Working on link: %R (type: %u)  ", rtl->id, rtl->type);
609
      switch (rtl->type)
610
        {
611
#ifdef OSPFv2
612
        case LSART_STUB:
613
          /*
614
           * RFC 2328 in 16.1. (2a) says to handle stub networks in an
615
           * second phase after the SPF for an area is calculated. We get
616
           * the same result by handing them here because add_network()
617
           * will keep the best (not the first) found route.
618
           */
619
          prefix = ipa_from_u32(rtl->id & rtl->data);
620
          pxlen = ipa_mklen(ipa_from_u32(rtl->data));
621
          add_network(oa, prefix, pxlen, act->dist + rtl->metric, act, i);
622
          break;
623
#endif
624

    
625
        case LSART_NET:
626
#ifdef OSPFv2
627
          /* In OSPFv2, rtl->id is IP addres of DR, Router ID is not known */
628
          tmp = ospf_hash_find_net(po->gr, oa->areaid, rtl->id);
629
#else /* OSPFv3 */
630
          tmp = ospf_hash_find(po->gr, oa->areaid, rtl->nif, rtl->id, LSA_T_NET);
631
#endif
632
          break;
633

    
634
        case LSART_VLNK:
635
        case LSART_PTP:
636
          tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id);
637
          break;
638

    
639
        default:
640
          log("Unknown link type in router lsa. (rid = %R)", act->lsa.id);
641
          break;
642
        }
643

    
644
      if (tmp)
645
        DBG("Going to add cand, Mydist: %u, Req: %u\n",
646
            tmp->dist, act->dist + rtl->metric);
647
      add_cand(&oa->cand, tmp, act, act->dist + rtl->metric, oa, i);
648
    }
649
}
650

    
651
/* RFC 2328 16.1. calculating shortest paths for an area */
652
static void
653
ospf_rt_spfa(struct ospf_area *oa)
654
{
655
  struct proto *p = &oa->po->proto;
656
  struct proto_ospf *po = oa->po;
657
  struct ospf_lsa_rt *rt;
658
  struct ospf_lsa_net *ln;
659
  struct top_hash_entry *act, *tmp;
660
  ip_addr prefix UNUSED;
661
  int pxlen UNUSED;
662
  u32 i, *rts;
663
  node *n;
664

    
665
  if (oa->rt == NULL)
666
    return;
667

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

    
670
  /* 16.1. (1) */
671
  init_list(&oa->cand);                /* Empty list of candidates */
672
  oa->trcap = 0;
673

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

    
676
  oa->rt->dist = 0;
677
  oa->rt->color = CANDIDATE;
678
  add_head(&oa->cand, &oa->rt->cn);
679
  DBG("RT LSA: rt: %R, id: %R, type: %u\n",
680
      oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa.type);
681

    
682
  while (!EMPTY_LIST(oa->cand))
683
  {
684
    n = HEAD(oa->cand);
685
    act = SKIP_BACK(struct top_hash_entry, cn, n);
686
    rem_node(n);
687

    
688
    DBG("Working on LSA: rt: %R, id: %R, type: %u\n",
689
        act->lsa.rt, act->lsa.id, act->lsa.type);
690

    
691
    act->color = INSPF;
692
    switch (act->lsa.type)
693
    {
694
    case LSA_T_RT:
695
      rt = (struct ospf_lsa_rt *) act->lsa_body;
696
      if (rt->options & OPT_RT_V)
697
        oa->trcap = 1;
698

    
699
      /*
700
       * In OSPFv3, all routers are added to per-area routing
701
       * tables. But we use it just for ASBRs and ABRs. For the
702
       * purpose of the last step in SPF - prefix-LSA processing in
703
       * process_prefixes(), we use information stored in LSA db.
704
       */
705
      if (((rt->options & OPT_RT_E) || (rt->options & OPT_RT_B))
706
          && (act->lsa.rt != po->router_id))
707
      {
708
        orta nf = {
709
          .type = RTS_OSPF,
710
          .options = rt->options,
711
          .metric1 = act->dist,
712
          .metric2 = LSINFINITY,
713
          .tag = 0,
714
          .rid = act->lsa.rt,
715
          .oa = oa,
716
          .nhs = act->nhs
717
        };
718
        ri_install_rt(oa, act->lsa.rt, &nf);
719
      }
720

    
721
#ifdef OSPFv2
722
      ospf_rt_spfa_rtlinks(oa, act, act);
723
#else /* OSPFv3 */
724
      /* Errata 2078 to RFC 5340 4.8.1 - skip links from non-routing nodes */
725
      if ((act != oa->rt) && !(rt->options & OPT_R))
726
        break;
727

    
728
      for (tmp = ospf_hash_find_rt_first(po->gr, act->domain, act->lsa.rt);
729
           tmp; tmp = ospf_hash_find_rt_next(tmp))
730
        ospf_rt_spfa_rtlinks(oa, act, tmp);
731
#endif
732

    
733
      break;
734
    case LSA_T_NET:
735
      ln = act->lsa_body;
736

    
737
#ifdef OSPFv2
738
      prefix = ipa_and(ipa_from_u32(act->lsa.id), ln->netmask);
739
      pxlen = ipa_mklen(ln->netmask);
740
      add_network(oa, prefix, pxlen, act->dist, act, -1);
741
#endif
742

    
743
      rts = (u32 *) (ln + 1);
744
      for (i = 0; i < lsa_net_count(&act->lsa); i++)
745
      {
746
        DBG("     Working on router %R ", rts[i]);
747
        tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]);
748
        if (tmp != NULL)
749
          DBG("Found :-)\n");
750
        else
751
          DBG("Not found!\n");
752
        add_cand(&oa->cand, tmp, act, act->dist, oa, -1);
753
      }
754
      break;
755
    }
756
  }
757

    
758
#ifdef OSPFv3
759
  process_prefixes(oa);
760
#endif
761
}
762

    
763
static int
764
link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par)
765
{
766
  u32 i, *rts;
767
  struct ospf_lsa_net *ln;
768
  struct ospf_lsa_rt *rt;
769
  struct ospf_lsa_rt_link *rtl, *rr;
770
  struct top_hash_entry *tmp;
771
  struct proto_ospf *po = oa->po;
772

    
773
  if (!en || !par) return 0;
774

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

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

    
785
  en->lb = IPA_NONE;
786
#ifdef OSPFv3
787
  en->lb_id = 0;
788
#endif
789
  switch (en->lsa.type)
790
  {
791
    case LSA_T_RT:
792
      rt = (struct ospf_lsa_rt *) en->lsa_body;
793
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
794
      for (i = 0; i < lsa_rt_count(&en->lsa); i++)
795
      {
796
        rtl = (rr + i);
797
        switch (rtl->type)
798
        {
799
        case LSART_STUB:
800
          break;
801
        case LSART_NET:
802
#ifdef OSPFv2
803
          /* In OSPFv2, rtl->id is IP addres of DR, Router ID is not known */
804
          tmp = ospf_hash_find_net(po->gr, oa->areaid, rtl->id);
805
#else /* OSPFv3 */
806
          tmp = ospf_hash_find(po->gr, oa->areaid, rtl->nif, rtl->id, LSA_T_NET);
807
#endif
808
          if (tmp == par)
809
          {
810
#ifdef OSPFv2
811
            en->lb = ipa_from_u32(rtl->data);
812
#else /* OSPFv3 */
813
            en->lb_id = rtl->lif;
814
#endif
815
            return 1;
816
          }
817

    
818
          break;
819
        case LSART_VLNK:
820
        case LSART_PTP:
821
          /* Not necessary the same link, see RFC 2328 [23] */
822
          tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id);
823
          if (tmp == par)
824
            return 1;
825

    
826
          break;
827
        default:
828
          log(L_WARN "Unknown link type in router lsa. (rid = %R)", en->lsa.rt);
829
          break;
830
        }
831
      }
832
      break;
833
    case LSA_T_NET:
834
      ln = en->lsa_body;
835
      rts = (u32 *) (ln + 1);
836
      for (i = 0; i < lsa_net_count(&en->lsa); i++)
837
      {
838
        tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]);
839
        if (tmp == par)
840
          return 1;
841
      }
842
      break;
843
    default:
844
      bug("Unknown lsa type %x.", en->lsa.type);
845
  }
846
  return 0;
847
}
848

    
849
  
850
/* RFC 2328 16.2. calculating inter-area routes */
851
static void
852
ospf_rt_sum(struct ospf_area *oa)
853
{
854
  struct proto_ospf *po = oa->po;
855
  struct proto *p = &po->proto;
856
  struct top_hash_entry *en;
857
  ip_addr ip = IPA_NONE;
858
  u32 dst_rid = 0;
859
  u32 metric, options;
860
  ort *abr;
861
  int pxlen = -1, type = -1;
862

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

    
865
  WALK_SLIST(en, po->lsal)
866
  {
867
    if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
868
      continue;
869

    
870
    if (en->domain != oa->areaid)
871
      continue;
872

    
873
    /* 16.2. (1a) */
874
    if (en->lsa.age == LSA_MAXAGE)
875
      continue;
876

    
877
    /* 16.2. (2) */
878
    if (en->lsa.rt == po->router_id)
879
      continue;
880

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

    
883
    if (en->lsa.type == LSA_T_SUM_NET)
884
    {
885
#ifdef OSPFv2
886
      struct ospf_lsa_sum *ls = en->lsa_body;
887
      ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask);
888
      pxlen = ipa_mklen(ls->netmask);
889
#else /* OSPFv3 */
890
      u8 pxopts;
891
      u16 rest;
892
      struct ospf_lsa_sum_net *ls = en->lsa_body;
893
      lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest);
894

    
895
      if (pxopts & OPT_PX_NU)
896
        continue;
897
#endif
898

    
899
      if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
900
      {
901
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
902
            p->name, en->lsa.type, en->lsa.id, en->lsa.rt);
903
        continue;
904
      }
905

    
906
      metric = ls->metric & METRIC_MASK;
907
      options = 0;
908
      type = ORT_NET;
909
    }
910
    else /* LSA_T_SUM_RT */
911
    {
912
#ifdef OSPFv2
913
      struct ospf_lsa_sum *ls = en->lsa_body;
914
      dst_rid = en->lsa.id;
915
      options = 0;
916
#else /* OSPFv3 */
917
      struct ospf_lsa_sum_rt *ls = en->lsa_body;
918
      dst_rid = ls->drid; 
919
      options = ls->options & OPTIONS_MASK;
920
#endif
921
      
922
      /* We don't want local router in ASBR routing table */
923
      if (dst_rid == po->router_id)
924
        continue;
925

    
926
      metric = ls->metric & METRIC_MASK;
927
      options |= ORTA_ASBR;
928
      type = ORT_ROUTER;
929
    }
930

    
931
    /* 16.2. (1b) */
932
    if (metric == LSINFINITY)
933
      continue;
934

    
935
    /* 16.2. (4) */
936
    ip_addr abrip = ipa_from_rid(en->lsa.rt);
937
    abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
938
    if (!abr || !abr->n.type)
939
      continue;
940

    
941
    if (!(abr->n.options & ORTA_ABR))
942
      continue;
943

    
944
    /* This check is not mentioned in RFC 2328 */
945
    if (abr->n.type != RTS_OSPF)
946
      continue;
947

    
948
    /* 16.2. (5) */
949
    orta nf = {
950
      .type = RTS_OSPF_IA,
951
      .options = options,
952
      .metric1 = abr->n.metric1 + metric,
953
      .metric2 = LSINFINITY,
954
      .tag = 0,
955
      .rid = en->lsa.rt, /* ABR ID */
956
      .oa = oa,
957
      .nhs = abr->n.nhs
958
    };
959

    
960
    if (type == ORT_NET)
961
      ri_install_net(po, ip, pxlen, &nf);
962
    else
963
      ri_install_rt(oa, dst_rid, &nf);
964
  }
965
}
966

    
967
/* RFC 2328 16.3. examining summary-LSAs in transit areas */
968
static void
969
ospf_rt_sum_tr(struct ospf_area *oa)
970
{
971
  struct proto *p = &oa->po->proto;
972
  struct proto_ospf *po = oa->po;
973
  struct ospf_area *bb = po->backbone;
974
  ip_addr abrip;
975
  struct top_hash_entry *en;
976
  u32 dst_rid, metric;
977
  ort *re = NULL, *abr;
978

    
979

    
980
  if (!bb) return;
981

    
982
  WALK_SLIST(en, po->lsal)
983
  {
984
    if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
985
      continue;
986

    
987
    if (en->domain != oa->areaid)
988
      continue;
989

    
990
    /* 16.3 (1a) */
991
    if (en->lsa.age == LSA_MAXAGE)
992
      continue;
993

    
994
    /* 16.3 (2) */
995
    if (en->lsa.rt == po->router_id)
996
      continue;
997

    
998
    if (en->lsa.type == LSA_T_SUM_NET)
999
    {
1000
      ip_addr ip;
1001
      int pxlen;
1002
#ifdef OSPFv2
1003
      struct ospf_lsa_sum *ls = en->lsa_body;
1004
      ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask);
1005
      pxlen = ipa_mklen(ls->netmask);
1006
#else /* OSPFv3 */
1007
      u8 pxopts;
1008
      u16 rest;
1009
      struct ospf_lsa_sum_net *ls = en->lsa_body;
1010
      lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest);
1011

    
1012
      if (pxopts & OPT_PX_NU)
1013
        continue;
1014
#endif
1015

    
1016
      if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
1017
      {
1018
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
1019
            p->name, en->lsa.type, en->lsa.id, en->lsa.rt);
1020
        continue;
1021
      }
1022

    
1023
      metric = ls->metric & METRIC_MASK;
1024
      re = fib_find(&po->rtf, &ip, pxlen);
1025
    }
1026
    else // en->lsa.type == LSA_T_SUM_RT
1027
    {
1028
#ifdef OSPFv2
1029
      struct ospf_lsa_sum *ls = en->lsa_body;
1030
      dst_rid = en->lsa.id;
1031
#else /* OSPFv3 */
1032
      struct ospf_lsa_sum_rt *ls = en->lsa_body;
1033
      dst_rid = ls->drid; 
1034
#endif
1035

    
1036
      metric = ls->metric & METRIC_MASK;
1037
      ip_addr ip = ipa_from_rid(dst_rid);
1038
      re = fib_find(&bb->rtr, &ip, MAX_PREFIX_LENGTH);
1039
    }
1040

    
1041
    /* 16.3 (1b) */ 
1042
    if (metric == LSINFINITY) 
1043
      continue; 
1044

    
1045
    /* 16.3 (3) */
1046
    if (!re || !re->n.type)
1047
      continue;
1048

    
1049
    if (re->n.oa->areaid != 0)
1050
      continue;
1051

    
1052
    if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA))
1053
      continue;
1054

    
1055
    /* 16.3. (4) */
1056
    abrip = ipa_from_rid(en->lsa.rt);
1057
    abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
1058
    if (!abr || !abr->n.type)
1059
      continue;
1060

    
1061
    metric = abr->n.metric1 + metric; /* IAC */
1062

    
1063
    /* 16.3. (5) */
1064
    if ((metric < re->n.metric1) || 
1065
        ((metric == re->n.metric1) && unresolved_vlink(re)))
1066
    {
1067
      /* We want to replace the next-hop even if the metric is equal
1068
         to replace a virtual next-hop through vlink with a real one.
1069
         Proper ECMP would merge nexthops here, but we do not do that.
1070
         We restrict nexthops to fit one area to simplify check
1071
         12.4.3 p4 in decide_sum_lsa() */
1072

    
1073
      re->n.metric1 = metric;
1074
      re->n.voa = oa;
1075
      re->n.nhs = abr->n.nhs;
1076
    }
1077
  }
1078
}
1079

    
1080
/* Decide about originating or flushing summary LSAs for condended area networks */
1081
static int
1082
decide_anet_lsa(struct ospf_area *oa, struct area_net *anet, struct ospf_area *anet_oa)
1083
{
1084
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
1085
  if (!oa_is_ext(oa) && !oa->ac->summary)
1086
    return 0;
1087

    
1088
  if (oa == anet_oa)
1089
    return 0;
1090

    
1091
  /* Do not condense routing info when exporting from backbone to the transit area */
1092
  if ((anet_oa == oa->po->backbone) && oa->trcap)
1093
    return 0;
1094

    
1095
  return (anet->active && !anet->hidden);
1096
}
1097

    
1098
/* Decide about originating or flushing summary LSAs (12.4.3) */
1099
static int
1100
decide_sum_lsa(struct ospf_area *oa, ort *nf, int dest)
1101
{
1102
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
1103
  if (!oa_is_ext(oa) && !oa->ac->summary)
1104
    return 0;
1105

    
1106
  /* Invalid field - no route */
1107
  if (!nf->n.type)
1108
    return 0;
1109

    
1110
  /* 12.4.3 p2 */
1111
  if (nf->n.type > RTS_OSPF_IA)
1112
    return 0;
1113

    
1114
  /* 12.4.3 p3 */
1115
  if ((nf->n.oa->areaid == oa->areaid))
1116
    return 0;
1117

    
1118
  /* 12.4.3 p4 */
1119
  if (nf->n.voa && (nf->n.voa->areaid == oa->areaid))
1120
    return 0;
1121

    
1122
  /* 12.4.3 p5 */
1123
  if (nf->n.metric1 >= LSINFINITY)
1124
    return 0;
1125

    
1126
  /* 12.4.3 p6 - AS boundary router */
1127
  if (dest == ORT_ROUTER)
1128
  {
1129
    /* We call decide_sum_lsa() on preferred ASBR entries, no need for 16.4. (3) */
1130
    /* 12.4.3 p1 */
1131
    return oa_is_ext(oa) && (nf->n.options & ORTA_ASBR);
1132
  }
1133

    
1134
  /* 12.4.3 p7 - inter-area route */
1135
  if (nf->n.type == RTS_OSPF_IA)
1136
  {
1137
    /* Inter-area routes are not repropagated into the backbone */
1138
    return (oa != oa->po->backbone);
1139
  }
1140

    
1141
  /* 12.4.3 p8 - intra-area route */
1142

    
1143
  /* Do not condense routing info when exporting from backbone to the transit area */
1144
  if ((nf->n.oa == oa->po->backbone) && oa->trcap)
1145
    return 1;
1146

    
1147
  struct area_net *anet = (struct area_net *)
1148
    fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen);
1149

    
1150
  /* Condensed area network found */ 
1151
  if (anet)
1152
    return 0;
1153

    
1154
  return 1;
1155
}
1156

    
1157
/* RFC 2328 16.7. p1 - originate or flush summary LSAs */
1158
static inline void
1159
check_sum_net_lsa(struct proto_ospf *po, ort *nf)
1160
{
1161
  struct area_net *anet = NULL;
1162
  struct ospf_area *anet_oa = NULL;
1163

    
1164
  /* RT entry marked as area network */
1165
  if (nf->fn.x0)
1166
  {
1167
    /* It is a default route for stub areas, handled entirely in ospf_rt_abr() */
1168
    if (nf->fn.pxlen == 0)
1169
      return;
1170

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

    
1180
  struct ospf_area *oa;
1181
  WALK_LIST(oa, po->area_list)
1182
  {
1183
    if (anet && decide_anet_lsa(oa, anet, anet_oa))
1184
      originate_sum_net_lsa(oa, &nf->fn, anet->metric);
1185
    else if (decide_sum_lsa(oa, nf, ORT_NET))
1186
      originate_sum_net_lsa(oa, &nf->fn, nf->n.metric1);
1187
    else
1188
      flush_sum_lsa(oa, &nf->fn, ORT_NET);
1189
  }
1190
}
1191

    
1192
static inline void
1193
check_sum_rt_lsa(struct proto_ospf *po, ort *nf)
1194
{
1195
  struct ospf_area *oa;
1196
  WALK_LIST(oa, po->area_list)
1197
  {
1198
    if (decide_sum_lsa(oa, nf, ORT_ROUTER))
1199
      originate_sum_rt_lsa(oa, &nf->fn, nf->n.metric1, nf->n.options);
1200
    else
1201
      flush_sum_lsa(oa, &nf->fn, ORT_ROUTER);
1202
  }
1203
}
1204

    
1205
static inline int
1206
decide_nssa_lsa(ort *nf, u32 *rt_metric, ip_addr *rt_fwaddr, u32 *rt_tag)
1207
{
1208
  struct ospf_area *oa = nf->n.oa;
1209
  struct top_hash_entry *en = nf->n.en;
1210
  int propagate;
1211

    
1212
  if (!rt_is_nssa(nf) || !oa->translate)
1213
    return 0;
1214

    
1215
  /* Condensed area network found */ 
1216
  if (fib_route(&oa->enet_fib, nf->fn.prefix, nf->fn.pxlen))
1217
    return 0;
1218

    
1219
  if (!en || (en->lsa.type != LSA_T_NSSA))
1220
    return 0;
1221

    
1222
  /* We do not store needed data in struct orta, we have to parse the LSA */
1223
  struct ospf_lsa_ext *le = en->lsa_body;
1224

    
1225
#ifdef OSPFv2
1226
  *rt_fwaddr = le->fwaddr;
1227
  *rt_tag = le->tag;
1228
  propagate = en->lsa.options & OPT_P;
1229
#else /* OSPFv3 */
1230
  u32 *buf = le->rest;
1231
  u8 pxlen = (*buf >> 24);
1232
  u8 pxopts = (*buf >> 16);
1233
  buf += IPV6_PREFIX_WORDS(pxlen);  /* Skip the IP prefix */
1234

    
1235
  if (pxopts & OPT_PX_NU)
1236
    return 0;
1237

    
1238
  if (le->metric & LSA_EXT_FBIT)
1239
    buf = lsa_get_ipv6_addr(buf, rt_fwaddr);
1240
  else
1241
    *rt_fwaddr = IPA_NONE;
1242

    
1243
  if (le->metric & LSA_EXT_TBIT)
1244
    *rt_tag = *buf++;
1245
  else
1246
    *rt_tag = 0;
1247

    
1248
  propagate = pxopts & OPT_PX_P;
1249
#endif
1250

    
1251
  if (!propagate || ipa_zero(*rt_fwaddr))
1252
    return 0;
1253

    
1254
  *rt_metric = le->metric & (METRIC_MASK | LSA_EXT_EBIT);
1255
  return 1;
1256
}
1257

    
1258
/* RFC 3103 3.2 - translating Type-7 LSAs into Type-5 LSAs */
1259
static inline void
1260
check_nssa_lsa(struct proto_ospf *po, ort *nf)
1261
{
1262
  struct fib_node *fn = &nf->fn;
1263
  struct area_net *anet = NULL;
1264
  struct ospf_area *oa = NULL;
1265
  u32 rt_metric, rt_tag;
1266
  ip_addr rt_fwaddr;
1267

    
1268
  /* Do not translate LSA if there is already the external LSA from route export */
1269
  if (fn->x1 == EXT_EXPORT)
1270
    return;
1271

    
1272
  /* RT entry marked as area network */
1273
  if (fn->x0)
1274
  {
1275
    /* Find that area network */
1276
    WALK_LIST(oa, po->area_list)
1277
    {
1278
      anet = (struct area_net *) fib_find(&oa->enet_fib, &fn->prefix, fn->pxlen);
1279
      if (anet)
1280
        break;
1281
    }
1282
  }
1283

    
1284
  /* RFC 3103 3.2 (3) - originate the aggregated address range */
1285
  if (anet && anet->active && !anet->hidden && oa->translate)
1286
    originate_ext_lsa(po->backbone, fn, EXT_NSSA, anet->metric, IPA_NONE, anet->tag, 0);
1287

    
1288
  /* RFC 3103 3.2 (2) - originate the same network */
1289
  else if (decide_nssa_lsa(nf, &rt_metric, &rt_fwaddr, &rt_tag))
1290
    originate_ext_lsa(po->backbone, fn, EXT_NSSA, rt_metric, rt_fwaddr, rt_tag, 0);
1291

    
1292
  else if (fn->x1 == EXT_NSSA)
1293
    flush_ext_lsa(po->backbone, fn, 0);
1294
}
1295

    
1296
/* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1297
static void
1298
ospf_check_vlinks(struct proto_ospf *po)
1299
{
1300
  struct proto *p = &po->proto;
1301

    
1302
  struct ospf_iface *ifa;
1303
  WALK_LIST(ifa, po->iface_list)
1304
  {
1305
    if (ifa->type == OSPF_IT_VLINK)
1306
    {
1307
      struct top_hash_entry *tmp;
1308
      tmp = ospf_hash_find_rt(po->gr, ifa->voa->areaid, ifa->vid);
1309

    
1310
      if (tmp && (tmp->color == INSPF) && ipa_nonzero(tmp->lb) && tmp->nhs)
1311
      {
1312
        struct ospf_iface *nhi = ospf_iface_find(po, tmp->nhs->iface);
1313

    
1314
        if ((ifa->state != OSPF_IS_PTP)
1315
            || (ifa->vifa != nhi)
1316
            || !ipa_equal(ifa->vip, tmp->lb))
1317
        {
1318
          OSPF_TRACE(D_EVENTS, "Vlink peer %R found", tmp->lsa.id);
1319
          ospf_iface_sm(ifa, ISM_DOWN);
1320
          ifa->vifa = nhi;
1321
          ifa->addr = nhi->addr;
1322
          ifa->cost = tmp->dist;
1323
          ifa->vip = tmp->lb;
1324
          ospf_iface_sm(ifa, ISM_UP);
1325
        }
1326
        else if ((ifa->state == OSPF_IS_PTP) && (ifa->cost != tmp->dist))
1327
        {
1328
          ifa->cost = tmp->dist;
1329
          schedule_rt_lsa(po->backbone);
1330
        }
1331
      }
1332
      else
1333
      {
1334
        if (ifa->state > OSPF_IS_DOWN)
1335
        {
1336
          OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", ifa->vid);
1337
          ospf_iface_sm(ifa, ISM_DOWN);
1338
        }
1339
      }
1340
    }
1341
  }
1342
}
1343

    
1344

    
1345
/* Miscellaneous route processing that needs to be done by ABRs */
1346
static void
1347
ospf_rt_abr1(struct proto_ospf *po)
1348
{
1349
  struct area_net *anet;
1350
  ort *nf, *default_nf;
1351

    
1352
  /* RFC 2328 G.3 - incomplete resolution of virtual next hops - routers */
1353
  FIB_WALK(&po->backbone->rtr, nftmp)
1354
  {
1355
    nf = (ort *) nftmp;
1356

    
1357
    if (nf->n.type && unresolved_vlink(nf))
1358
      reset_ri(nf);
1359
  }
1360
  FIB_WALK_END;
1361

    
1362

    
1363
  FIB_WALK(&po->rtf, nftmp)
1364
  {
1365
    nf = (ort *) nftmp;
1366

    
1367

    
1368
    /* RFC 2328 G.3 - incomplete resolution of virtual next hops - networks */
1369
    if (nf->n.type && unresolved_vlink(nf))
1370
      reset_ri(nf);
1371

    
1372

    
1373
    /* Compute condensed area networks */
1374
    if (nf->n.type == RTS_OSPF)
1375
    {
1376
      anet = (struct area_net *) fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen);
1377
      if (anet)
1378
      {
1379
        if (!anet->active)
1380
        {
1381
          anet->active = 1;
1382

    
1383
          /* Get a RT entry and mark it to know that it is an area network */
1384
          ort *nfi = (ort *) fib_get(&po->rtf, &anet->fn.prefix, anet->fn.pxlen);
1385
          nfi->fn.x0 = 1; /* mark and keep persistent, to have stable UID */
1386

    
1387
          /* 16.2. (3) */
1388
          if (nfi->n.type == RTS_OSPF_IA)
1389
            reset_ri(nfi);
1390
        }
1391

    
1392
        if (anet->metric < nf->n.metric1)
1393
          anet->metric = nf->n.metric1;
1394
      }
1395
    }
1396
  }
1397
  FIB_WALK_END;
1398

    
1399
  ip_addr addr = IPA_NONE;
1400
  default_nf = (ort *) fib_get(&po->rtf, &addr, 0);
1401
  default_nf->fn.x0 = 1; /* keep persistent */
1402

    
1403
  struct ospf_area *oa;
1404
  WALK_LIST(oa, po->area_list)
1405
  {
1406

    
1407
    /* 12.4.3.1. - originate or flush default route for stub/NSSA areas */
1408
    if (oa_is_stub(oa) || (oa_is_nssa(oa) && !oa->ac->summary))
1409
      originate_sum_net_lsa(oa, &default_nf->fn, oa->ac->default_cost);
1410
    else
1411
      flush_sum_lsa(oa, &default_nf->fn, ORT_NET);
1412

    
1413
    /*
1414
     * Originate type-7 default route for NSSA areas
1415
     *
1416
     * Because type-7 default LSAs are originated by ABRs, they do not
1417
     * collide with other type-7 LSAs (as ABRs generate type-5 LSAs
1418
     * for both external route export or external-NSSA translation),
1419
     * so we use 0 for the src arg.
1420
     */
1421

    
1422
    if (oa_is_nssa(oa) && oa->ac->default_nssa)
1423
      originate_ext_lsa(oa, &default_nf->fn, 0, oa->ac->default_cost, IPA_NONE, 0, 0);
1424
    else
1425
      flush_ext_lsa(oa, &default_nf->fn, 1);
1426

    
1427

    
1428
    /* RFC 2328 16.4. (3) - precompute preferred ASBR entries */
1429
    if (oa_is_ext(oa))
1430
    {
1431
      FIB_WALK(&oa->rtr, nftmp)
1432
      {
1433
        nf = (ort *) nftmp;
1434
        if (nf->n.options & ORTA_ASBR)
1435
          ri_install_asbr(po, &nf->fn.prefix, &nf->n);
1436
      }
1437
      FIB_WALK_END;
1438
    }
1439
  }
1440

    
1441

    
1442
  /* Originate or flush ASBR summary LSAs */
1443
  FIB_WALK(&po->backbone->rtr, nftmp)
1444
  {
1445
    check_sum_rt_lsa(po, (ort *) nftmp);
1446
  }
1447
  FIB_WALK_END;
1448

    
1449

    
1450
  /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1451
  ospf_check_vlinks(po);
1452
}
1453

    
1454

    
1455
static void
1456
translator_timer_hook(timer *timer)
1457
{
1458
  struct ospf_area *oa = timer->data;
1459
  
1460
  if (oa->translate != TRANS_WAIT)
1461
    return;
1462

    
1463
  oa->translate = TRANS_OFF;
1464
  schedule_rtcalc(oa->po);
1465
}
1466

    
1467
static void
1468
ospf_rt_abr2(struct proto_ospf *po)
1469
{
1470
  struct ospf_area *oa;
1471
  struct top_hash_entry *en;
1472
  ort *nf, *nf2;
1473

    
1474

    
1475
  /* RFC 3103 3.1 - type-7 translator election */
1476
  struct ospf_area *bb = po->backbone;
1477
  WALK_LIST(oa, po->area_list)
1478
    if (oa_is_nssa(oa))
1479
    {
1480
      int translate = 1;
1481

    
1482
      if (oa->ac->translator)
1483
        goto decided;
1484

    
1485
      FIB_WALK(&oa->rtr, nftmp)
1486
      {
1487
        nf = (ort *) nftmp;
1488
        if (!nf->n.type || !(nf->n.options & ORTA_ABR))
1489
          continue;
1490

    
1491
        nf2 = fib_find(&bb->rtr, &nf->fn.prefix, MAX_PREFIX_LENGTH);
1492
        if (!nf2 || !nf2->n.type || !(nf2->n.options & ORTA_ABR))
1493
          continue;
1494

    
1495
        en = ospf_hash_find_rt(po->gr, oa->areaid, nf->n.rid);
1496
        if (!en || (en->color != INSPF))
1497
          continue;
1498

    
1499
        struct ospf_lsa_rt *rt = en->lsa_body;
1500
        /* There is better candidate - Nt-bit or higher Router ID */
1501
        if ((rt->options & OPT_RT_NT) || (po->router_id < nf->n.rid))
1502
        {
1503
          translate = 0;
1504
          goto decided;
1505
        }
1506
      }
1507
      FIB_WALK_END;
1508

    
1509
    decided:
1510
      if (translate && (oa->translate != TRANS_ON))
1511
      {
1512
        if (oa->translate == TRANS_WAIT)
1513
          tm_stop(oa->translator_timer);
1514

    
1515
        oa->translate = TRANS_ON;
1516
      }
1517

    
1518
      if (!translate && (oa->translate == TRANS_ON))
1519
      {
1520
        if (oa->translator_timer == NULL)
1521
          oa->translator_timer = tm_new_set(po->proto.pool, translator_timer_hook, oa, 0, 0);
1522

    
1523
        /* Schedule the end of translation */
1524
        tm_start(oa->translator_timer, oa->ac->transint);
1525
        oa->translate = TRANS_WAIT;
1526
      }
1527
    }
1528

    
1529

    
1530
  /* Compute condensed external networks */
1531
  FIB_WALK(&po->rtf, nftmp)
1532
  {
1533
    nf = (ort *) nftmp;
1534
    if (rt_is_nssa(nf) && (nf->n.options & ORTA_PROP))
1535
    {
1536
      struct area_net *anet = (struct area_net *)
1537
        fib_route(&nf->n.oa->enet_fib, nf->fn.prefix, nf->fn.pxlen);
1538

    
1539
      if (anet)
1540
      {
1541
        if (!anet->active)
1542
        {
1543
          anet->active = 1;
1544

    
1545
          /* Get a RT entry and mark it to know that it is an area network */
1546
          nf2 = (ort *) fib_get(&po->rtf, &anet->fn.prefix, anet->fn.pxlen);
1547
          nf2->fn.x0 = 1;
1548
        }
1549

    
1550
        u32 metric = (nf->n.type == RTS_OSPF_EXT1) ?
1551
          nf->n.metric1 : ((nf->n.metric2 + 1) | LSA_EXT_EBIT);
1552

    
1553
        if (anet->metric < metric)
1554
          anet->metric = metric;
1555
      }
1556
    }
1557
  }
1558
  FIB_WALK_END;
1559

    
1560

    
1561
  FIB_WALK(&po->rtf, nftmp)
1562
  {
1563
    nf = (ort *) nftmp;
1564

    
1565
    check_sum_net_lsa(po, nf);
1566
    check_nssa_lsa(po, nf);
1567
  }
1568
  FIB_WALK_END;
1569
}
1570

    
1571

    
1572
/* Like fib_route(), but ignores dummy rt entries */
1573
static void *
1574
ospf_fib_route(struct fib *f, ip_addr a, int len)
1575
{
1576
  ip_addr a0;
1577
  ort *nf;
1578

    
1579
  while (len >= 0)
1580
  {
1581
    a0 = ipa_and(a, ipa_mkmask(len));
1582
    nf = fib_find(f, &a0, len);
1583
    if (nf && nf->n.type)
1584
      return nf;
1585
    len--;
1586
  }
1587
  return NULL;
1588
}
1589

    
1590
/* RFC 2328 16.4. calculating external routes */
1591
static void
1592
ospf_ext_spf(struct proto_ospf *po)
1593
{
1594
  ort *nf1, *nf2;
1595
  orta nfa = {};
1596
  struct top_hash_entry *en;
1597
  struct proto *p = &po->proto;
1598
  struct ospf_lsa_ext *le;
1599
  int pxlen, ebit, rt_fwaddr_valid, rt_propagate;
1600
  ip_addr ip, rtid, rt_fwaddr;
1601
  u32 br_metric, rt_metric, rt_tag;
1602
  struct ospf_area *atmp;
1603

    
1604
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
1605

    
1606
  WALK_SLIST(en, po->lsal)
1607
  {
1608
    /* 16.4. (1) */
1609
    if ((en->lsa.type != LSA_T_EXT) && (en->lsa.type != LSA_T_NSSA))
1610
      continue;
1611

    
1612
    if (en->lsa.age == LSA_MAXAGE)
1613
      continue;
1614

    
1615
    /* 16.4. (2) */
1616
    if (en->lsa.rt == po->router_id)
1617
      continue;
1618

    
1619
    DBG("%s: Working on LSA. ID: %R, RT: %R, Type: %u\n",
1620
        p->name, en->lsa.id, en->lsa.rt, en->lsa.type);
1621

    
1622
    le = en->lsa_body;
1623

    
1624
    rt_metric = le->metric & METRIC_MASK;
1625
    ebit = le->metric & LSA_EXT_EBIT;
1626

    
1627
    if (rt_metric == LSINFINITY)
1628
      continue;
1629

    
1630
#ifdef OSPFv2
1631
    ip = ipa_and(ipa_from_u32(en->lsa.id), le->netmask);
1632
    pxlen = ipa_mklen(le->netmask);
1633
    rt_fwaddr = le->fwaddr;
1634
    rt_fwaddr_valid = !ipa_equal(rt_fwaddr, IPA_NONE);
1635
    rt_tag = le->tag;
1636
    rt_propagate = en->lsa.options & OPT_P;
1637
#else /* OSPFv3 */
1638
    u8 pxopts;
1639
    u16 rest;
1640
    u32 *buf = le->rest;
1641
    buf = lsa_get_ipv6_prefix(buf, &ip, &pxlen, &pxopts, &rest);
1642

    
1643
    if (pxopts & OPT_PX_NU)
1644
      continue;
1645

    
1646
    rt_fwaddr_valid = le->metric & LSA_EXT_FBIT;
1647
    if (rt_fwaddr_valid)
1648
      buf = lsa_get_ipv6_addr(buf, &rt_fwaddr);
1649
    else 
1650
      rt_fwaddr = IPA_NONE;
1651

    
1652
    if (le->metric & LSA_EXT_TBIT)
1653
      rt_tag = *buf++;
1654
    else
1655
      rt_tag = 0;
1656

    
1657
    rt_propagate = pxopts & OPT_PX_P;
1658
#endif
1659

    
1660
    if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
1661
    {
1662
      log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
1663
          p->name, en->lsa.type, en->lsa.id, en->lsa.rt);
1664
      continue;
1665
    }
1666

    
1667

    
1668
    /* 16.4. (3) */
1669
    /* If there are more areas, we already precomputed preferred ASBR
1670
       entries in ospf_rt_abr1() and stored them in the backbone
1671
       table. For NSSA, we examine the area to which the LSA is assigned */
1672
    if (en->lsa.type == LSA_T_EXT)
1673
      atmp = ospf_main_area(po);
1674
    else /* NSSA */
1675
      atmp = ospf_find_area(po, en->domain);
1676

    
1677
    if (!atmp)
1678
      continue;                        /* Should not happen */
1679

    
1680
    rtid = ipa_from_rid(en->lsa.rt);
1681
    nf1 = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH);
1682

    
1683
    if (!nf1 || !nf1->n.type)
1684
      continue;                        /* No AS boundary router found */
1685

    
1686
    if (!(nf1->n.options & ORTA_ASBR))
1687
      continue;                        /* It is not ASBR */
1688

    
1689
    /* 16.4. (3) NSSA - special rule for default routes */
1690
    /* ABR should use default only if P-bit is set and summaries are active */
1691
    if ((en->lsa.type == LSA_T_NSSA) && ipa_zero(ip) && (pxlen == 0) &&
1692
        (po->areano > 1) && !(rt_propagate && atmp->ac->summary))
1693
      continue;
1694

    
1695
    if (!rt_fwaddr_valid)
1696
    {
1697
      nf2 = nf1;
1698
      nfa.nhs = nf1->n.nhs;
1699
      br_metric = nf1->n.metric1;
1700
    }
1701
    else
1702
    {
1703
      nf2 = ospf_fib_route(&po->rtf, rt_fwaddr, MAX_PREFIX_LENGTH);
1704
      if (!nf2)
1705
        continue;
1706

    
1707
      if (en->lsa.type == LSA_T_EXT)
1708
      {
1709
        /* For ext routes, we accept intra-area or inter-area routes */
1710
        if ((nf2->n.type != RTS_OSPF) && (nf2->n.type != RTS_OSPF_IA))
1711
          continue;
1712
      }
1713
      else /* NSSA */
1714
      {
1715
        /* For NSSA routes, we accept just intra-area in the same area */
1716
        if ((nf2->n.type != RTS_OSPF) || (nf2->n.oa != atmp))
1717
          continue;
1718
      }
1719

    
1720
      /* Next-hop is a part of a configured stubnet */
1721
      if (!nf2->n.nhs)
1722
        continue;
1723

    
1724
      nfa.nhs = nf2->n.nhs;
1725
      br_metric = nf2->n.metric1;
1726

    
1727
      /* Replace device nexthops with nexthops to forwarding address from LSA */
1728
      if (has_device_nexthops(nfa.nhs))
1729
      {
1730
        nfa.nhs = fix_device_nexthops(po, nfa.nhs, rt_fwaddr);
1731
        nfa.nhs_reuse = 1;
1732
      }
1733
    }
1734

    
1735
    if (ebit)
1736
    {
1737
      nfa.type = RTS_OSPF_EXT2;
1738
      nfa.metric1 = br_metric;
1739
      nfa.metric2 = rt_metric;
1740
    }
1741
    else
1742
    {
1743
      nfa.type = RTS_OSPF_EXT1;
1744
      nfa.metric1 = br_metric + rt_metric;
1745
      nfa.metric2 = LSINFINITY;
1746
    }
1747

    
1748
    /* Mark the LSA as reachable */
1749
    en->color = INSPF;
1750

    
1751
    /* Whether the route is preferred in route selection according to 16.4.1 */
1752
    nfa.options = epath_preferred(&nf2->n) ? ORTA_PREF : 0;
1753
    if (en->lsa.type == LSA_T_NSSA)
1754
    {
1755
      nfa.options |= ORTA_NSSA;
1756
      if (rt_propagate)
1757
        nfa.options |= ORTA_PROP;
1758
    }
1759

    
1760
    nfa.tag = rt_tag;
1761
    nfa.rid = en->lsa.rt;
1762
    nfa.oa = atmp; /* undefined in RFC 2328 */
1763
    nfa.en = en; /* store LSA for later (NSSA processing) */
1764

    
1765
    ri_install_ext(po, ip, pxlen, &nfa);
1766
  }
1767
}
1768

    
1769
/* Cleanup of routing tables and data */
1770
void
1771
ospf_rt_reset(struct proto_ospf *po)
1772
{
1773
  struct ospf_area *oa;
1774
  struct top_hash_entry *en;
1775
  struct area_net *anet;
1776
  ort *ri;
1777

    
1778
  /* Reset old routing table */
1779
  FIB_WALK(&po->rtf, nftmp)
1780
  {
1781
    ri = (ort *) nftmp;
1782
    ri->fn.x0 = 0;
1783
    reset_ri(ri);
1784
  }
1785
  FIB_WALK_END;
1786

    
1787
  /* Reset SPF data in LSA db */
1788
  WALK_SLIST(en, po->lsal)
1789
  {
1790
    en->color = OUTSPF;
1791
    en->dist = LSINFINITY;
1792
    en->nhs = NULL;
1793
    en->lb = IPA_NONE;
1794
  }
1795

    
1796
  WALK_LIST(oa, po->area_list)
1797
  {
1798
    /* Reset ASBR routing tables */
1799
    FIB_WALK(&oa->rtr, nftmp)
1800
    {
1801
      ri = (ort *) nftmp;
1802
      reset_ri(ri);
1803
    }
1804
    FIB_WALK_END;
1805

    
1806
    /* Reset condensed area networks */
1807
    if (po->areano > 1)
1808
    {
1809
      FIB_WALK(&oa->net_fib, nftmp)
1810
      {
1811
        anet = (struct area_net *) nftmp;
1812
        anet->active = 0;
1813
        anet->metric = 0;
1814
      }
1815
      FIB_WALK_END;
1816

    
1817
      FIB_WALK(&oa->enet_fib, nftmp)
1818
      {
1819
        anet = (struct area_net *) nftmp;
1820
        anet->active = 0;
1821
        anet->metric = 0;
1822
      }
1823
      FIB_WALK_END;
1824
    }
1825
  }
1826
}
1827

    
1828
/**
1829
 * ospf_rt_spf - calculate internal routes
1830
 * @po: OSPF protocol
1831
 *
1832
 * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
1833
 * It's based on Dijkstra's shortest path tree algorithms.
1834
 * This function is invoked from ospf_disp().
1835
 */
1836
void
1837
ospf_rt_spf(struct proto_ospf *po)
1838
{
1839
  struct proto *p = &po->proto;
1840
  struct ospf_area *oa;
1841

    
1842
  if (po->areano == 0)
1843
    return;
1844

    
1845
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
1846

    
1847
  /* 16. (1) */
1848
  ospf_rt_reset(po);
1849

    
1850
  /* 16. (2) */
1851
  WALK_LIST(oa, po->area_list)
1852
    ospf_rt_spfa(oa);
1853

    
1854
  /* 16. (3) */
1855
  ospf_rt_sum(ospf_main_area(po));
1856

    
1857
  /* 16. (4) */
1858
  WALK_LIST(oa, po->area_list)
1859
    if (oa->trcap && (oa->areaid != 0))
1860
      ospf_rt_sum_tr(oa);
1861

    
1862
  if (po->areano > 1)
1863
    ospf_rt_abr1(po);
1864

    
1865
  /* 16. (5) */
1866
  ospf_ext_spf(po);
1867

    
1868
  if (po->areano > 1)
1869
    ospf_rt_abr2(po);
1870

    
1871
  rt_sync(po);
1872
  lp_flush(po->nhpool);
1873
  
1874
  po->calcrt = 0;
1875
}
1876

    
1877

    
1878
static inline int
1879
inherit_nexthops(struct mpnh *pn)
1880
{
1881
  /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */
1882
  return pn && (ipa_nonzero(pn->gw) || !pn->iface);
1883
}
1884

    
1885
static struct mpnh *
1886
calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
1887
              struct top_hash_entry *par, int pos)
1888
{
1889
  // struct proto *p = &oa->po->proto;
1890
  struct proto_ospf *po = oa->po;
1891
  struct mpnh *pn = par->nhs;
1892
  struct ospf_iface *ifa;
1893
  u32 rid = en->lsa.rt;
1894

    
1895
  /* 16.1.1. The next hop calculation */
1896
  DBG("     Next hop calculating for id: %R rt: %R type: %u\n",
1897
      en->lsa.id, en->lsa.rt, en->lsa.type);
1898

    
1899
  /* Usually, we inherit parent nexthops */
1900
  if (inherit_nexthops(pn))
1901
    return pn;
1902

    
1903
  /* 
1904
   * There are three cases:
1905
   * 1) en is a local network (and par is root)
1906
   * 2) en is a ptp or ptmp neighbor (and par is root)
1907
   * 3) en is a bcast or nbma neighbor (and par is local network)
1908
   */
1909

    
1910
  /* The first case - local network */
1911
  if ((en->lsa.type == LSA_T_NET) && (par == oa->rt))
1912
  {
1913
    ifa = rt_pos_to_ifa(oa, pos);
1914
    if (!ifa)
1915
      return NULL;
1916

    
1917
    return new_nexthop(po, IPA_NONE, ifa->iface, ifa->ecmp_weight);
1918
  }
1919

    
1920
  /* The second case - ptp or ptmp neighbor */
1921
  if ((en->lsa.type == LSA_T_RT) && (par == oa->rt))
1922
  {
1923
    ifa = rt_pos_to_ifa(oa, pos);
1924
    if (!ifa)
1925
      return NULL;
1926

    
1927
    if (ifa->type == OSPF_IT_VLINK)
1928
      return new_nexthop(po, IPA_NONE, NULL, 0);
1929

    
1930
    struct ospf_neighbor *m = find_neigh(ifa, rid);
1931
    if (!m || (m->state != NEIGHBOR_FULL))
1932
      return NULL;
1933

    
1934
    return new_nexthop(po, m->ip, ifa->iface, ifa->ecmp_weight);
1935
  }
1936

    
1937
  /* The third case - bcast or nbma neighbor */
1938
  if ((en->lsa.type == LSA_T_RT) && (par->lsa.type == LSA_T_NET))
1939
  {
1940
    /* par->nhi should be defined from parent's calc_next_hop() */
1941
    if (!pn)
1942
      goto bad;
1943

    
1944
#ifdef OSPFv2
1945
    /*
1946
     * In this case, next-hop is the same as link-back, which is
1947
     * already computed in link_back().
1948
     */
1949
    if (ipa_zero(en->lb))
1950
      goto bad;
1951

    
1952
    return new_nexthop(po, en->lb, pn->iface, pn->weight);
1953

    
1954
#else /* OSPFv3 */
1955
    /*
1956
     * Next-hop is taken from lladdr field of Link-LSA, en->lb_id
1957
     * is computed in link_back().
1958
     */
1959
    struct top_hash_entry *lhe;
1960
    lhe = ospf_hash_find(po->gr, pn->iface->index, en->lb_id, rid, LSA_T_LINK);
1961

    
1962
    if (!lhe)
1963
      return NULL;
1964

    
1965
    struct ospf_lsa_link *llsa = lhe->lsa_body;
1966
      
1967
    if (ipa_zero(llsa->lladdr))
1968
      return NULL;
1969

    
1970
    return new_nexthop(po, llsa->lladdr, pn->iface, pn->weight);
1971
#endif
1972
  }
1973

    
1974
 bad:
1975
  /* Probably bug or some race condition, we log it */
1976
  log(L_ERR "Unexpected case in next hop calculation");
1977
  return NULL;
1978
}
1979

    
1980

    
1981
/* Add LSA into list of candidates in Dijkstra's algorithm */
1982
static void
1983
add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
1984
         u32 dist, struct ospf_area *oa, int pos)
1985
{
1986
  struct proto_ospf *po = oa->po;
1987
  node *prev, *n;
1988
  int added = 0;
1989
  struct top_hash_entry *act;
1990

    
1991
  /* 16.1. (2b) */
1992
  if (en == NULL)
1993
    return;
1994
  if (en->lsa.age == LSA_MAXAGE)
1995
    return;
1996

    
1997
#ifdef OSPFv3
1998
  if (en->lsa.type == LSA_T_RT)
1999
    {
2000
      struct ospf_lsa_rt *rt = en->lsa_body;
2001
      if (!(rt->options & OPT_V6))
2002
        return;
2003
    }
2004
#endif
2005

    
2006
  /* 16.1. (2c) */
2007
  if (en->color == INSPF)
2008
    return;
2009

    
2010
  /* 16.1. (2d), also checks that dist < LSINFINITY */
2011
  if (dist > en->dist)
2012
    return;
2013

    
2014
  /* We should check whether there is a reverse link from en to par, */
2015
  if (!link_back(oa, en, par))
2016
    return;
2017

    
2018
  struct mpnh *nhs = calc_next_hop(oa, en, par, pos);
2019
  if (!nhs)
2020
  {
2021
    log(L_WARN "Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
2022
        en->lsa.type, en->lsa.id, en->lsa.rt);
2023
    return;
2024
  }
2025

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

    
2028
  if ((dist == en->dist) && !nh_is_vlink(en->nhs))
2029
  {
2030
    /*
2031
     * For multipath, we should merge nexthops. We merge regular nexthops only.
2032
     * Dummy vlink nexthops are less preferred and handled as a special case.
2033
     *
2034
     * During merging, new nexthops (nhs) can be reused if they are not
2035
     * inherited from the parent (i.e. they are allocated in calc_next_hop()).
2036
     * Current nexthops (en->nhs) can be reused if they weren't inherited in
2037
     * previous steps (that is stored in nhs_reuse, i.e. created by merging or
2038
     * allocated in calc_next_hop()).
2039
     *
2040
     * Generally, a node first inherits shared nexthops from its parent and
2041
     * later possibly gets reusable copy during merging.
2042
     */
2043

    
2044
    /* Keep old ones */
2045
    if (!po->ecmp || nh_is_vlink(nhs) || (nhs == en->nhs))
2046
      return;
2047

    
2048
    /* Merge old and new */
2049
    int new_reuse = (par->nhs != nhs);
2050
    en->nhs = merge_nexthops(po, en->nhs, nhs, en->nhs_reuse, new_reuse);
2051
    en->nhs_reuse = 1;
2052
    return;
2053
  }
2054

    
2055
  DBG("     Adding candidate: rt: %R, id: %R, type: %u\n",
2056
      en->lsa.rt, en->lsa.id, en->lsa.type);
2057

    
2058
  if (en->color == CANDIDATE)
2059
  {                                /* We found a shorter path */
2060
    rem_node(&en->cn);
2061
  }
2062
  en->nhs = nhs;
2063
  en->dist = dist;
2064
  en->color = CANDIDATE;
2065
  en->nhs_reuse = (par->nhs != nhs);
2066

    
2067
  prev = NULL;
2068

    
2069
  if (EMPTY_LIST(*l))
2070
  {
2071
    add_head(l, &en->cn);
2072
  }
2073
  else
2074
  {
2075
    WALK_LIST(n, *l)
2076
    {
2077
      act = SKIP_BACK(struct top_hash_entry, cn, n);
2078
      if ((act->dist > dist) ||
2079
          ((act->dist == dist) && (act->lsa.type == LSA_T_RT)))
2080
      {
2081
        if (prev == NULL)
2082
          add_head(l, &en->cn);
2083
        else
2084
          insert_node(&en->cn, prev);
2085
        added = 1;
2086
        break;
2087
      }
2088
      prev = n;
2089
    }
2090

    
2091
    if (!added)
2092
    {
2093
      add_tail(l, &en->cn);
2094
    }
2095
  }
2096
}
2097

    
2098
static inline int
2099
ort_changed(ort *nf, rta *nr)
2100
{
2101
  rta *or = nf->old_rta;
2102
  return !or ||
2103
    (nf->n.metric1 != nf->old_metric1) || (nf->n.metric2 != nf->old_metric2) ||
2104
    (nf->n.tag != nf->old_tag) || (nf->n.rid != nf->old_rid) ||
2105
    (nr->source != or->source) || (nr->dest != or->dest) ||
2106
    (nr->iface != or->iface) || !ipa_equal(nr->gw, or->gw) ||
2107
    !mpnh_same(nr->nexthops, or->nexthops);
2108
}
2109

    
2110
static void
2111
rt_sync(struct proto_ospf *po)
2112
{
2113
  struct proto *p = &po->proto;
2114
  struct fib_iterator fit;
2115
  struct fib *fib = &po->rtf;
2116
  ort *nf;
2117
  struct ospf_area *oa;
2118

    
2119
  /* This is used for forced reload of routes */
2120
  int reload = (po->calcrt == 2);
2121

    
2122
  OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation");
2123

    
2124
  DBG("Now syncing my rt table with nest's\n");
2125
  FIB_ITERATE_INIT(&fit, fib);
2126
again1:
2127
  FIB_ITERATE_START(fib, &fit, nftmp)
2128
  {
2129
    nf = (ort *) nftmp;
2130

    
2131
    /* Sanity check of next-hop addresses, failure should not happen */
2132
    if (nf->n.type)
2133
    {
2134
      struct mpnh *nh;
2135
      for (nh = nf->n.nhs; nh; nh = nh->next)
2136
        if (ipa_nonzero(nh->gw))
2137
        {
2138
          neighbor *ng = neigh_find2(p, &nh->gw, nh->iface, 0);
2139
          if (!ng || (ng->scope == SCOPE_HOST))
2140
            { reset_ri(nf); break; }
2141
        }
2142
    }
2143

    
2144
    /* Remove configured stubnets */
2145
    if (!nf->n.nhs)
2146
      reset_ri(nf);
2147

    
2148
    if (nf->n.type) /* Add the route */
2149
    {
2150
      rta a0 = {
2151
        .src = p->main_source,
2152
        .source = nf->n.type,
2153
        .scope = SCOPE_UNIVERSE,
2154
        .cast = RTC_UNICAST
2155
      };
2156

    
2157
      if (nf->n.nhs->next)
2158
      {
2159
        a0.dest = RTD_MULTIPATH;
2160
        a0.nexthops = nf->n.nhs;
2161
      }
2162
      else if (ipa_nonzero(nf->n.nhs->gw))
2163
      {
2164
        a0.dest = RTD_ROUTER;
2165
        a0.iface = nf->n.nhs->iface;
2166
        a0.gw = nf->n.nhs->gw;
2167
      }
2168
      else
2169
      {
2170
        a0.dest = RTD_DEVICE;
2171
        a0.iface = nf->n.nhs->iface;
2172
      }
2173

    
2174
      if (reload || ort_changed(nf, &a0))
2175
      {
2176
        net *ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
2177
        rta *a = rta_lookup(&a0);
2178
        rte *e = rte_get_temp(a);
2179

    
2180
        rta_free(nf->old_rta);
2181
        nf->old_rta = rta_clone(a);
2182
        e->u.ospf.metric1 = nf->old_metric1 = nf->n.metric1;
2183
        e->u.ospf.metric2 = nf->old_metric2 = nf->n.metric2;
2184
        e->u.ospf.tag = nf->old_tag = nf->n.tag;
2185
        e->u.ospf.router_id = nf->old_rid = nf->n.rid;
2186
        e->pflags = 0;
2187
        e->net = ne;
2188
        e->pref = p->preference;
2189

    
2190
        DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n",
2191
            a0.source, nf->fn.prefix, nf->fn.pxlen, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
2192
        rte_update(p, ne, e);
2193
      }
2194
    }
2195
    else if (nf->old_rta)
2196
    {
2197
      /* Remove the route */
2198
      rta_free(nf->old_rta);
2199
      nf->old_rta = NULL;
2200

    
2201
      net *ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
2202
      rte_update(p, ne, NULL);
2203
    }
2204

    
2205
    /* Remove unused rt entry. Entries with fn.x0 == 1 are persistent. */
2206
    if (!nf->n.type && !nf->fn.x0 && !nf->fn.x1)
2207
    {
2208
      FIB_ITERATE_PUT(&fit, nftmp);
2209
      fib_delete(fib, nftmp);
2210
      goto again1;
2211
    }
2212
  }
2213
  FIB_ITERATE_END(nftmp);
2214

    
2215

    
2216
  WALK_LIST(oa, po->area_list)
2217
  {
2218
    /* Cleanup ASBR hash tables */
2219
    FIB_ITERATE_INIT(&fit, &oa->rtr);
2220
again2:
2221
    FIB_ITERATE_START(&oa->rtr, &fit, nftmp)
2222
    {
2223
      nf = (ort *) nftmp;
2224

    
2225
      if (!nf->n.type)
2226
      {
2227
        FIB_ITERATE_PUT(&fit, nftmp);
2228
        fib_delete(&oa->rtr, nftmp);
2229
        goto again2;
2230
      }
2231
    }
2232
    FIB_ITERATE_END(nftmp);
2233
  }
2234
}