Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / proto / ospf / rt.c @ 6b3f1a54

History | View | Annotate | Download (49.1 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(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par, u32 dist, int i, uint lif, uint nif);
14
static void rt_sync(struct ospf_proto *p);
15

    
16

    
17
static inline void reset_ri(ort *ort)
18
{
19
  bzero(&ort->n, sizeof(orta));
20
}
21

    
22
static inline int
23
nh_is_vlink(struct nexthop *nhs)
24
{
25
  return !nhs->iface;
26
}
27

    
28
static inline int
29
unresolved_vlink(ort *ort)
30
{
31
  return ort->n.nhs && nh_is_vlink(ort->n.nhs);
32
}
33

    
34
static inline struct nexthop *
35
new_nexthop(struct ospf_proto *p, ip_addr gw, struct iface *iface, byte weight)
36
{
37
  struct nexthop *nh = lp_allocz(p->nhpool, sizeof(struct nexthop));
38
  nh->gw = gw;
39
  nh->iface = iface;
40
  nh->weight = weight;
41
  return nh;
42
}
43

    
44
/* Returns true if there are device nexthops in n */
45
static inline int
46
has_device_nexthops(const struct nexthop *n)
47
{
48
  for (; n; n = n->next)
49
    if (ipa_zero(n->gw))
50
      return 1;
51

    
52
  return 0;
53
}
54

    
55
/* Replace device nexthops with nexthops to gw */
56
static struct nexthop *
57
fix_device_nexthops(struct ospf_proto *p, const struct nexthop *n, ip_addr gw)
58
{
59
  struct nexthop *root1 = NULL;
60
  struct nexthop *root2 = NULL;
61
  struct nexthop **nn1 = &root1;
62
  struct nexthop **nn2 = &root2;
63

    
64
  if (!p->ecmp)
65
    return new_nexthop(p, gw, n->iface, n->weight);
66

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

    
71
  for (; n; n = n->next)
72
  {
73
    struct nexthop *nn = new_nexthop(p, ipa_zero(n->gw) ? gw : n->gw, n->iface, n->weight);
74

    
75
    if (ipa_zero(n->gw))
76
    {
77
      *nn1 = nn;
78
      nn1 = &(nn->next);
79
    }
80
    else
81
    {
82
      *nn2 = nn;
83
      nn2 = &(nn->next);
84
    }
85
  }
86

    
87
  return nexthop_merge(root1, root2, 1, 1, p->ecmp, p->nhpool);
88
}
89

    
90

    
91
/* Whether the ASBR or the forward address destination is preferred
92
   in AS external route selection according to 16.4.1. */
93
static inline int
94
epath_preferred(const orta *ep)
95
{
96
  return (ep->type == RTS_OSPF) && (ep->oa->areaid != 0);
97
}
98

    
99
/* Whether the ext route has ASBR/next_hop marked as preferred. */
100
static inline int
101
orta_pref(const orta *nf)
102
{
103
  return !!(nf->options & ORTA_PREF);
104
}
105

    
106
/* Classify orta entries according to RFC 3101 2.5 (6e) priorities:
107
   Type-7 LSA with P-bit, Type-5 LSA, Type-7 LSA without P-bit */
108
static int
109
orta_prio(const orta *nf)
110
{
111
  /* RFC 3103 2.5 (6e) priorities */
112
  u32 opts = nf->options & (ORTA_NSSA | ORTA_PROP);
113

    
114
  /* A Type-7 LSA with the P-bit set */
115
  if (opts == (ORTA_NSSA | ORTA_PROP))
116
    return 2;
117

    
118
  /* A Type-5 LSA */
119
  if (opts == 0)
120
    return 1;
121

    
122
  return 0;
123
}
124

    
125
/* Whether the route is better according to RFC 3101 2.5 (6e):
126
   Prioritize Type-7 LSA with P-bit, then Type-5 LSA, then higher router ID */
127
static int
128
orta_prefer_lsa(const orta *new, const orta *old)
129
{
130
  int pn = orta_prio(new);
131
  int po = orta_prio(old);
132

    
133
  return (pn > po) || ((pn == po) && (new->en->lsa.rt > old->en->lsa.rt));
134
}
135

    
136
/*
137
 * Compare an existing routing table entry with a new one. Applicable for
138
 * intra-area routes, inter-area routes and router entries. Returns integer
139
 * <, = or > than 0 if the new orta is less, equal or more preferred than
140
 * the old orta.
141
 */
142
static int
143
orta_compare(const struct ospf_proto *p, const orta *new, const orta *old)
144
{
145
  int r;
146

    
147
  if (old->type == RTS_DUMMY)
148
    return 1;
149

    
150
  /* Prefer intra-area to inter-area to externals */
151
  r = ((int) old->type) - ((int) new->type);
152
  if (r) return r;
153

    
154
  /* Prefer lowest type 1 metric */
155
  r = ((int) old->metric1) - ((int) new->metric1);
156
  if (r) return r;
157

    
158

    
159
  /* Rest is BIRD-specific */
160

    
161
  /* Area-wide routes should not mix next-hops from different areas.
162
     This generally should not happen unless there is some misconfiguration. */
163
  if (new->oa->areaid != old->oa->areaid)
164
    return (new->oa->areaid > old->oa->areaid) ? 1 : -1;
165

    
166
  /* Prefer routes for configured stubnets (!nhs) to regular routes to dummy
167
     vlink nexthops. We intentionally return -1 if both are stubnets or vlinks. */
168
  if (!old->nhs)
169
    return -1;
170
  if (!new->nhs)
171
    return 1;
172
  if (nh_is_vlink(new->nhs))
173
    return -1;
174
  if (nh_is_vlink(old->nhs))
175
    return 1;
176

    
177

    
178
  if (p->ecmp)
179
    return 0;
180

    
181
  /* Prefer routes with higher Router ID, just to be more deterministic */
182
  if (new->rid > old->rid)
183
    return 1;
184

    
185
  return -1;
186
}
187

    
188
/*
189
 * Compare ASBR routing table entry with a new one, used for precompute ASBRs
190
 * for AS external route selection (RFC 2328 16.4 (3)), Returns integer < or >
191
 * than 0 if the new ASBR is less or more preferred than the old ASBR.
192
 */
193
static int
194
orta_compare_asbr(const struct ospf_proto *p, const orta *new, const orta *old)
195
{
196
  int r;
197

    
198
  if (old->type == RTS_DUMMY)
199
    return 1;
200

    
201
  if (!p->rfc1583)
202
  {
203
    r = epath_preferred(new) - epath_preferred(old);
204
    if (r) return r;
205
  }
206

    
207
  r = ((int) old->metric1) - ((int) new->metric1);
208
  if (r) return r;
209

    
210
  /* Larger area ID is preferred */
211
  if (new->oa->areaid > old->oa->areaid)
212
    return 1;
213

    
214
  /* There is just one ASBR of that RID per area, so tie is not possible */
215
  return -1;
216
}
217

    
218
/*
219
 * Compare a routing table entry with a new one, for AS external routes
220
 * (RFC 2328 16.4) and NSSA routes (RFC 3103 2.5), Returns integer <, = or >
221
 * than 0 if the new orta is less, equal or more preferred than the old orta.
222
 */
223
static int
224
orta_compare_ext(const struct ospf_proto *p, const orta *new, const orta *old)
225
{
226
  int r;
227

    
228
  if (old->type == RTS_DUMMY)
229
    return 1;
230

    
231
  /* 16.4 (6a) - prefer routes with lower type */
232
  r = ((int) old->type) - ((int) new->type);
233
  if (r) return r;
234

    
235
  /* 16.4 (6b) - prefer routes with lower type 2 metric */
236
  if (new->type == RTS_OSPF_EXT2)
237
  {
238
    r = ((int) old->metric2) - ((int) new->metric2);
239
    if (r) return r;
240
  }
241

    
242
  /* 16.4 (6c) - if not RFC1583, prefer routes with preferred ASBR/next_hop */
243
  if (!p->rfc1583)
244
  {
245
    r = orta_pref(new) - orta_pref(old);
246
    if (r) return r;
247
  }
248

    
249
  /* 16.4 (6d) - prefer routes with lower type 1 metric */
250
  r = ((int) old->metric1) - ((int) new->metric1);
251
  if (r) return r;
252

    
253

    
254
  if (p->ecmp && p->merge_external)
255
    return 0;
256

    
257
  /*
258
   * RFC 3101 2.5 (6e) - prioritize Type-7 LSA with P-bit, then Type-5 LSA, then
259
   * LSA with higher router ID. Although this should apply just to functionally
260
   * equivalent LSAs (i.e. ones with the same non-zero forwarding address), we
261
   * use it also to disambiguate otherwise equally preferred nexthops.
262
   */
263
  if (orta_prefer_lsa(new, old))
264
    return 1;
265

    
266
  return -1;
267
}
268

    
269

    
270
static inline void
271
ort_replace(ort *o, const orta *new)
272
{
273
  memcpy(&o->n, new, sizeof(orta));
274
}
275

    
276
static void
277
ort_merge(struct ospf_proto *p, ort *o, const orta *new)
278
{
279
  orta *old = &o->n;
280

    
281
  if (old->nhs != new->nhs)
282
  {
283
    old->nhs = nexthop_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
284
                          p->ecmp, p->nhpool);
285
    old->nhs_reuse = 1;
286
  }
287

    
288
  if (old->rid < new->rid)
289
    old->rid = new->rid;
290
}
291

    
292
static void
293
ort_merge_ext(struct ospf_proto *p, ort *o, const orta *new)
294
{
295
  orta *old = &o->n;
296

    
297
  if (old->nhs != new->nhs)
298
  {
299
    old->nhs = nexthop_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse,
300
                          p->ecmp, p->nhpool);
301
    old->nhs_reuse = 1;
302
  }
303

    
304
  if (old->tag != new->tag)
305
    old->tag = 0;
306

    
307
  /*
308
   * Even with multipath, we store only one LSA in orta.en for the purpose of
309
   * NSSA/ext translation. Therefore, we apply procedures from RFC 3101 2.5 (6e)
310
   * to all chosen LSAs for given network, not just to functionally equivalent
311
   * ones (i.e. ones with the same non-zero forwarding address).
312
   */
313
  if (orta_prefer_lsa(new, old))
314
  {
315
    old->options = new->options;
316
    old->rid = new->rid;
317
    old->oa = new->oa;
318
    old->en = new->en;
319
  }
320
}
321

    
322

    
323

    
324
static inline void
325
ri_install_net(struct ospf_proto *p, net_addr *net, const orta *new)
326
{
327
  ort *old = fib_get(&p->rtf, net);
328
  int cmp = orta_compare(p, new, &old->n);
329

    
330
  if (cmp > 0)
331
    ort_replace(old, new);
332
  else if (cmp == 0)
333
    ort_merge(p, old, new);
334
}
335

    
336
static inline void
337
ri_install_rt(struct ospf_area *oa, u32 rid, const orta *new)
338
{
339
  net_addr_ip4 nrid = net_from_rid(rid);
340
  ort *old = fib_get(&oa->rtr, (net_addr *) &nrid);
341
  int cmp = orta_compare(oa->po, new, &old->n);
342

    
343
  if (cmp > 0)
344
    ort_replace(old, new);
345
  else if (cmp == 0)
346
    ort_merge(oa->po, old, new);
347
}
348

    
349
static inline void
350
ri_install_asbr(struct ospf_proto *p, u32 rid, const orta *new)
351
{
352
  net_addr_ip4 nrid = net_from_rid(rid);
353
  ort *old = fib_get(&p->backbone->rtr, (net_addr *) &nrid);
354

    
355
  if (orta_compare_asbr(p, new, &old->n) > 0)
356
    ort_replace(old, new);
357
}
358

    
359
static inline void
360
ri_install_ext(struct ospf_proto *p, net_addr *net, const orta *new)
361
{
362
  ort *old = fib_get(&p->rtf, net);
363
  int cmp = orta_compare_ext(p, new, &old->n);
364

    
365
  if (cmp > 0)
366
    ort_replace(old, new);
367
  else if (cmp == 0)
368
    ort_merge_ext(p, old, new);
369
}
370

    
371
static inline struct ospf_iface *
372
rt_pos_to_ifa(struct ospf_area *oa, int pos)
373
{
374
  struct ospf_iface *ifa;
375

    
376
  WALK_LIST(ifa, oa->po->iface_list)
377
    if (ifa->oa == oa && pos >= ifa->rt_pos_beg && pos < ifa->rt_pos_end)
378
      return ifa;
379

    
380
  return NULL;
381
}
382

    
383
static inline struct ospf_iface *
384
px_pos_to_ifa(struct ospf_area *oa, int pos)
385
{
386
  struct ospf_iface *ifa;
387

    
388
  WALK_LIST(ifa, oa->po->iface_list)
389
    if (ifa->oa == oa && pos >= ifa->px_pos_beg && pos < ifa->px_pos_end)
390
      return ifa;
391

    
392
  return NULL;
393
}
394

    
395

    
396
static void
397
add_network(struct ospf_area *oa, net_addr *net, int metric, struct top_hash_entry *en, int pos)
398
{
399
  struct ospf_proto *p = oa->po;
400

    
401
  orta nf = {
402
    .type = RTS_OSPF,
403
    .options = 0,
404
    .metric1 = metric,
405
    .metric2 = LSINFINITY,
406
    .tag = 0,
407
    .rid = en->lsa.rt,
408
    .oa = oa,
409
    .nhs = en->nhs
410
  };
411

    
412
  if (!ospf_valid_prefix(net))
413
  {
414
    log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
415
        p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
416
    return;
417
  }
418

    
419
  if (en == oa->rt)
420
  {
421
    /*
422
     * Local stub networks do not have proper iface in en->nhi (because they all
423
     * have common top_hash_entry en). We have to find iface responsible for
424
     * that stub network. Configured stubnets do not have any iface. They will
425
     * be removed in rt_sync().
426
     */
427

    
428
    struct ospf_iface *ifa;
429
    ifa = ospf_is_v2(p) ? rt_pos_to_ifa(oa, pos) : px_pos_to_ifa(oa, pos);
430
    nf.nhs = ifa ? new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight) : NULL;
431
  }
432

    
433
  ri_install_net(p, net, &nf);
434
}
435

    
436

    
437

    
438
static inline void
439
spfa_process_rt(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
440
{
441
  struct ospf_lsa_rt *rt = act->lsa_body;
442
  struct ospf_lsa_rt_walk rtl;
443
  struct top_hash_entry *tmp;
444
  int i;
445

    
446
  if (rt->options & OPT_RT_V)
447
    oa->trcap = 1;
448

    
449
  /*
450
   * In OSPFv3, all routers are added to per-area routing
451
   * tables. But we use it just for ASBRs and ABRs. For the
452
   * purpose of the last step in SPF - prefix-LSA processing in
453
   * spfa_process_prefixes(), we use information stored in LSA db.
454
   */
455
  if (((rt->options & OPT_RT_E) || (rt->options & OPT_RT_B))
456
      && (act->lsa.rt != p->router_id))
457
  {
458
    orta nf = {
459
      .type = RTS_OSPF,
460
      .options = rt->options,
461
      .metric1 = act->dist,
462
      .metric2 = LSINFINITY,
463
      .tag = 0,
464
      .rid = act->lsa.rt,
465
      .oa = oa,
466
      .nhs = act->nhs
467
    };
468
    ri_install_rt(oa, act->lsa.rt, &nf);
469
  }
470

    
471
  /* Errata 2078 to RFC 5340 4.8.1 - skip links from non-routing nodes */
472
  if (ospf_is_v3(p) && (act != oa->rt) && !(rt->options & OPT_R))
473
    return;
474

    
475
  /* Now process Rt links */
476
  for (lsa_walk_rt_init(p, act, &rtl), i = 0; lsa_walk_rt(&rtl); i++)
477
  {
478
    tmp = NULL;
479

    
480
    switch (rtl.type)
481
    {
482
    case LSART_STUB:
483

    
484
      /* Should not happen, LSART_STUB is not defined in OSPFv3 */
485
      if (ospf_is_v3(p))
486
        break;
487

    
488
      /*
489
       * RFC 2328 in 16.1. (2a) says to handle stub networks in an
490
       * second phase after the SPF for an area is calculated. We get
491
       * the same result by handing them here because add_network()
492
       * will keep the best (not the first) found route.
493
       */
494
      net_addr_ip4 net =
495
        NET_ADDR_IP4(ip4_from_u32(rtl.id & rtl.data), u32_masklen(rtl.data));
496

    
497
      add_network(oa, (net_addr *) &net, act->dist + rtl.metric, act, i);
498
      break;
499

    
500
    case LSART_NET:
501
      tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
502
      break;
503

    
504
    case LSART_VLNK:
505
    case LSART_PTP:
506
      tmp = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
507
      break;
508
    }
509

    
510
    add_cand(oa, tmp, act, act->dist + rtl.metric, i, rtl.lif, rtl.nif);
511
  }
512
}
513

    
514
static inline void
515
spfa_process_net(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entry *act)
516
{
517
  struct ospf_lsa_net *ln = act->lsa_body;
518
  struct top_hash_entry *tmp;
519
  int i, cnt;
520

    
521
  if (ospf_is_v2(p))
522
  {
523
    net_addr_ip4 net =
524
      NET_ADDR_IP4(ip4_from_u32(act->lsa.id & ln->optx), u32_masklen(ln->optx));
525

    
526
    add_network(oa, (net_addr *) &net, act->dist, act, -1);
527
  }
528

    
529
  cnt = lsa_net_count(&act->lsa);
530
  for (i = 0; i < cnt; i++)
531
  {
532
    tmp = ospf_hash_find_rt(p->gr, oa->areaid, ln->routers[i]);
533
    add_cand(oa, tmp, act, act->dist, -1, 0, 0);
534
  }
535
}
536

    
537
static inline void
538
spfa_process_prefixes(struct ospf_proto *p, struct ospf_area *oa)
539
{
540
  struct top_hash_entry *en, *src;
541
  struct ospf_lsa_prefix *px;
542
  u32 *buf;
543
  int i;
544

    
545
  WALK_SLIST(en, p->lsal)
546
  {
547
    if (en->lsa_type != LSA_T_PREFIX)
548
      continue;
549

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

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

    
556
    px = en->lsa_body;
557

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

    
564
    if (!src)
565
      continue;
566

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

    
571
    if ((src->lsa_type != LSA_T_RT) && (src->lsa_type != LSA_T_NET))
572
      continue;
573

    
574
    buf = px->rest;
575
    for (i = 0; i < px->pxcount; i++)
576
    {
577
      net_addr net;
578
      u8 pxopts;
579
      u16 metric;
580

    
581
      buf = ospf3_get_prefix(buf, ospf_get_af(p), &net, &pxopts, &metric);
582

    
583
      if (pxopts & OPT_PX_NU)
584
        continue;
585

    
586
      /* Store the first global address to use it later as a vlink endpoint */
587
      if ((pxopts & OPT_PX_LA) && (net.type == NET_IP6) && ipa_zero(src->lb))
588
        src->lb = ipa_from_ip6(net6_prefix(&net));
589

    
590
      add_network(oa, &net, src->dist + metric, src, i);
591
    }
592
  }
593
}
594

    
595
/* RFC 2328 16.1. calculating shortest paths for an area */
596
static void
597
ospf_rt_spfa(struct ospf_area *oa)
598
{
599
  struct ospf_proto *p = oa->po;
600
  struct top_hash_entry *act;
601
  node *n;
602

    
603
  if (oa->rt == NULL)
604
    return;
605
  if (oa->rt->lsa.age == LSA_MAXAGE)
606
    return;
607

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

    
610
  /* 16.1. (1) */
611
  init_list(&oa->cand);                /* Empty list of candidates */
612
  oa->trcap = 0;
613

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

    
616
  oa->rt->dist = 0;
617
  oa->rt->color = CANDIDATE;
618
  add_head(&oa->cand, &oa->rt->cn);
619
  DBG("RT LSA: rt: %R, id: %R, type: %u\n",
620
      oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa_type);
621

    
622
  while (!EMPTY_LIST(oa->cand))
623
  {
624
    n = HEAD(oa->cand);
625
    act = SKIP_BACK(struct top_hash_entry, cn, n);
626
    rem_node(n);
627

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

    
631
    act->color = INSPF;
632
    switch (act->lsa_type)
633
    {
634
    case LSA_T_RT:
635
      spfa_process_rt(p, oa, act);
636
      break;
637

    
638
    case LSA_T_NET:
639
      spfa_process_net(p, oa, act);
640
      break;
641

    
642
    default:
643
      log(L_WARN "%s: Unknown LSA type in SPF: %d", p->p.name, act->lsa_type);
644
    }
645
  }
646

    
647
  if (ospf_is_v3(p))
648
    spfa_process_prefixes(p, oa);
649
}
650

    
651
static int
652
link_back(struct ospf_area *oa, struct top_hash_entry *en,
653
          struct top_hash_entry *par, uint lif, uint nif)
654
{
655
  struct ospf_proto *p = oa->po;
656
  struct ospf_lsa_rt_walk rtl;
657
  struct top_hash_entry *tmp;
658
  struct ospf_lsa_net *ln;
659
  u32 i, cnt;
660

    
661
  if (!en || !par) return 0;
662

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

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

    
673
  en->lb = IPA_NONE;
674
  en->lb_id = 0;
675

    
676
  switch (en->lsa_type)
677
  {
678
  case LSA_T_RT:
679
    lsa_walk_rt_init(p, en, &rtl);
680
    while (lsa_walk_rt(&rtl))
681
    {
682
      switch (rtl.type)
683
      {
684
      case LSART_STUB:
685
        break;
686

    
687
      case LSART_NET:
688
        tmp = ospf_hash_find_net(p->gr, oa->areaid, rtl.id, rtl.nif);
689
        if (tmp == par)
690
        {
691
          /*
692
           * Note that there may be multiple matching Rt-fields if router 'en'
693
           * have multiple interfaces to net 'par'. Perhaps we should do ECMP.
694
           */
695
          if (ospf_is_v2(p))
696
            en->lb = ipa_from_u32(rtl.data);
697
          else
698
            en->lb_id = rtl.lif;
699

    
700
          return 1;
701
        }
702
        break;
703

    
704
      case LSART_VLNK:
705
      case LSART_PTP:
706
        /*
707
         * For OSPFv2, not necessary the same link, see RFC 2328 [23].
708
         * For OSPFv3, we verify that by comparing nif and lif fields.
709
         */
710
        if (ospf_is_v3(p) && ((rtl.lif != nif) || (rtl.nif != lif)))
711
          break;
712

    
713
        tmp = ospf_hash_find_rt(p->gr, oa->areaid, rtl.id);
714
        if (tmp == par)
715
          return 1;
716
        break;
717
      }
718
    }
719
    break;
720

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

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

    
738

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

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

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

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

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

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

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

    
771
    if (en->lsa_type == LSA_T_SUM_NET)
772
    {
773
      lsa_parse_sum_net(en, ospf_is_v2(p), ospf_get_af(p), &net, &pxopts, &metric);
774

    
775
      if (!ospf_valid_prefix(&net))
776
      {
777
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
778
            p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
779
        continue;
780
      }
781

    
782
      if (pxopts & OPT_PX_NU)
783
        continue;
784

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

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

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

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

    
804
    /* 16.2. (4) */
805
    net_addr_ip4 nrid = net_from_rid(en->lsa.rt);
806
    abr = fib_find(&oa->rtr, (net_addr *) &nrid);
807
    if (!abr || !abr->n.type)
808
      continue;
809

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

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

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

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

    
836
/* RFC 2328 16.3. examining summary-LSAs in transit areas */
837
static void
838
ospf_rt_sum_tr(struct ospf_area *oa)
839
{
840
  struct ospf_proto *p = oa->po;
841
  struct ospf_area *bb = p->backbone;
842
  struct top_hash_entry *en;
843
  ort *re, *abr;
844
  u32 metric;
845

    
846
  if (!bb)
847
    return;
848

    
849
  WALK_SLIST(en, p->lsal)
850
  {
851
    if ((en->lsa_type != LSA_T_SUM_RT) && (en->lsa_type != LSA_T_SUM_NET))
852
      continue;
853

    
854
    if (en->domain != oa->areaid)
855
      continue;
856

    
857
    /* 16.3 (1a) */
858
    if (en->lsa.age == LSA_MAXAGE)
859
      continue;
860

    
861
    /* 16.3 (2) */
862
    if (en->lsa.rt == p->router_id)
863
      continue;
864

    
865
    if (en->lsa_type == LSA_T_SUM_NET)
866
    {
867
      net_addr net;
868
      u8 pxopts;
869

    
870
      lsa_parse_sum_net(en, ospf_is_v2(p), ospf_get_af(p), &net, &pxopts, &metric);
871

    
872
      if (!ospf_valid_prefix(&net))
873
      {
874
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
875
            p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
876
        continue;
877
      }
878

    
879
      if (pxopts & OPT_PX_NU)
880
        continue;
881

    
882
      re = fib_find(&p->rtf, &net);
883
    }
884
    else // en->lsa_type == LSA_T_SUM_RT
885
    {
886
      u32 dst_rid, options;
887

    
888
      lsa_parse_sum_rt(en, ospf_is_v2(p), &dst_rid, &metric, &options);
889

    
890
      net_addr_ip4 nrid = net_from_rid(dst_rid);
891
      re = fib_find(&bb->rtr, (net_addr *) &nrid);
892
    }
893

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
1007
  return 1;
1008
}
1009

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

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

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

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

    
1042
static inline void
1043
check_sum_rt_lsa(struct ospf_proto *p, ort *nf)
1044
{
1045
  u32 rid = rid_from_net(nf->fn.addr);
1046

    
1047
  struct ospf_area *oa;
1048
  WALK_LIST(oa, p->area_list)
1049
    if (decide_sum_lsa(oa, nf, ORT_ROUTER))
1050
      ospf_originate_sum_rt_lsa(p, oa, rid, nf->n.metric1, nf->n.options);
1051
}
1052

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

    
1059
  if (!rt_is_nssa(nf) || !oa->translate)
1060
    return 0;
1061

    
1062
  /* Condensed area network found */
1063
  if (fib_route(&oa->enet_fib, nf->fn.addr))
1064
    return 0;
1065

    
1066
  if (!en || (en->lsa_type != LSA_T_NSSA))
1067
    return 0;
1068

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

    
1072
  if (rt->pxopts & OPT_PX_NU)
1073
    return 0;
1074

    
1075
  if (!rt->propagate || ipa_zero(rt->fwaddr))
1076
    return 0;
1077

    
1078
  return 1;
1079
}
1080

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

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

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

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

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

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

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

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

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

    
1162

    
1163
/* Miscellaneous route processing that needs to be done by ABRs */
1164
static void
1165
ospf_rt_abr1(struct ospf_proto *p)
1166
{
1167
  struct area_net *anet;
1168
  ort *default_nf;
1169
  net_addr default_net;
1170

    
1171
  /* RFC 2328 G.3 - incomplete resolution of virtual next hops - routers */
1172
  FIB_WALK(&p->backbone->rtr, ort, nf)
1173
  {
1174
    if (nf->n.type && unresolved_vlink(nf))
1175
      reset_ri(nf);
1176
  }
1177
  FIB_WALK_END;
1178

    
1179

    
1180
  FIB_WALK(&p->rtf, ort, nf)
1181
  {
1182
    /* RFC 2328 G.3 - incomplete resolution of virtual next hops - networks */
1183
    if (nf->n.type && unresolved_vlink(nf))
1184
      reset_ri(nf);
1185

    
1186

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

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

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

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

    
1213

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

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

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

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

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

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

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

    
1255

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

    
1263

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

    
1268

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

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

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

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

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

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

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

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

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

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

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

    
1326
        oa->translate = TRANS_ON;
1327
      }
1328

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

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

    
1340

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

    
1348
      if (anet)
1349
      {
1350
        if (!anet->active)
1351
        {
1352
          anet->active = 1;
1353

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

    
1359
        u32 metric = (nf->n.type == RTS_OSPF_EXT1) ?
1360
          nf->n.metric1 : ((nf->n.metric2 + 1) | LSA_EXT3_EBIT);
1361

    
1362
        if (anet->metric < metric)
1363
          anet->metric = metric;
1364
      }
1365
    }
1366
  }
1367
  FIB_WALK_END;
1368

    
1369

    
1370
  FIB_WALK(&p->rtf, ort, nf)
1371
  {
1372
    check_sum_net_lsa(p, nf);
1373
    check_nssa_lsa(p, nf);
1374
  }
1375
  FIB_WALK_END;
1376
}
1377

    
1378

    
1379
/* Like fib_route(), but ignores dummy rt entries */
1380
static void *
1381
ospf_fib_route_ip4(struct fib *f, ip4_addr a, int len)
1382
{
1383
  net_addr_ip4 net = NET_ADDR_IP4(a, len);
1384
  ort *nf;
1385

    
1386
loop:
1387
  nf = fib_find(f, (net_addr *) &net);
1388
  if (nf && nf->n.type)
1389
    return nf;
1390

    
1391
  if (net.pxlen > 0)
1392
  {
1393
    net.pxlen--;
1394
    ip4_clrbit(&net.prefix, net.pxlen);
1395
    goto loop;
1396
  }
1397

    
1398
  return NULL;
1399
}
1400

    
1401
static void *
1402
ospf_fib_route_ip6(struct fib *f, ip6_addr a, int len)
1403
{
1404
  net_addr_ip6 net = NET_ADDR_IP6(a, len);
1405
  ort *nf;
1406

    
1407
loop:
1408
  nf = fib_find(f, (net_addr *) &net);
1409
  if (nf && nf->n.type)
1410
    return nf;
1411

    
1412
  if (net.pxlen > 0)
1413
  {
1414
    net.pxlen--;
1415
    ip6_clrbit(&net.prefix, net.pxlen);
1416
    goto loop;
1417
  }
1418

    
1419
  return NULL;
1420
}
1421

    
1422
static void *
1423
ospf_fib_route(struct fib *f, ip_addr a)
1424
{
1425
  if (f->addr_type == NET_IP4)
1426
    return ospf_fib_route_ip4(f, ipa_to_ip4(a), IP4_MAX_PREFIX_LENGTH);
1427
  else
1428
    return ospf_fib_route_ip6(f, ipa_to_ip6(a), IP6_MAX_PREFIX_LENGTH);
1429
}
1430

    
1431

    
1432
/* RFC 2328 16.4. calculating external routes */
1433
static void
1434
ospf_ext_spf(struct ospf_proto *p)
1435
{
1436
  struct top_hash_entry *en;
1437
  struct ospf_lsa_ext_local rt;
1438
  ort *nf1, *nf2;
1439
  u32 br_metric;
1440
  struct ospf_area *atmp;
1441

    
1442
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
1443

    
1444
  WALK_SLIST(en, p->lsal)
1445
  {
1446
    orta nfa = {};
1447

    
1448
    /* 16.4. (1) */
1449
    if ((en->lsa_type != LSA_T_EXT) && (en->lsa_type != LSA_T_NSSA))
1450
      continue;
1451

    
1452
    if (en->lsa.age == LSA_MAXAGE)
1453
      continue;
1454

    
1455
    /* 16.4. (2) */
1456
    if (en->lsa.rt == p->router_id)
1457
      continue;
1458

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

    
1462
    lsa_parse_ext(en, ospf_is_v2(p), ospf_get_af(p), &rt);
1463

    
1464
    if (!ospf_valid_prefix(&rt.net))
1465
    {
1466
      log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
1467
          p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
1468
      continue;
1469
    }
1470

    
1471
    if (rt.metric == LSINFINITY)
1472
      continue;
1473

    
1474
    if (rt.pxopts & OPT_PX_NU)
1475
      continue;
1476

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

    
1486
    if (!atmp)
1487
      continue;                        /* Should not happen */
1488

    
1489
    net_addr_ip4 nrid = net_from_rid(en->lsa.rt);
1490
    nf1 = fib_find(&atmp->rtr, (net_addr *) &nrid);
1491

    
1492
    if (!nf1 || !nf1->n.type)
1493
      continue;                        /* No AS boundary router found */
1494

    
1495
    if (!(nf1->n.options & ORTA_ASBR))
1496
      continue;                        /* It is not ASBR */
1497

    
1498
    /* 16.4. (3) NSSA - special rule for default routes */
1499
    /* ABR should use default only if P-bit is set and summaries are active */
1500
    if ((en->lsa_type == LSA_T_NSSA) && (rt.net.pxlen == 0) &&
1501
        (p->areano > 1) && !(rt.propagate && atmp->ac->summary))
1502
      continue;
1503

    
1504
    if (!rt.fbit)
1505
    {
1506
      nf2 = nf1;
1507
      nfa.nhs = nf1->n.nhs;
1508
      br_metric = nf1->n.metric1;
1509
    }
1510
    else
1511
    {
1512
      nf2 = ospf_fib_route(&p->rtf, rt.fwaddr);
1513
      if (!nf2)
1514
        continue;
1515

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

    
1529
      /* Next-hop is a part of a configured stubnet */
1530
      if (!nf2->n.nhs)
1531
        continue;
1532

    
1533
      nfa.nhs = nf2->n.nhs;
1534
      br_metric = nf2->n.metric1;
1535

    
1536
      /* Replace device nexthops with nexthops to forwarding address from LSA */
1537
      if (has_device_nexthops(nfa.nhs))
1538
      {
1539
        nfa.nhs = fix_device_nexthops(p, nfa.nhs, rt.fwaddr);
1540
        nfa.nhs_reuse = 1;
1541
      }
1542
    }
1543

    
1544
    if (rt.ebit)
1545
    {
1546
      nfa.type = RTS_OSPF_EXT2;
1547
      nfa.metric1 = br_metric;
1548
      nfa.metric2 = rt.metric;
1549
    }
1550
    else
1551
    {
1552
      nfa.type = RTS_OSPF_EXT1;
1553
      nfa.metric1 = br_metric + rt.metric;
1554
      nfa.metric2 = LSINFINITY;
1555
    }
1556

    
1557
    /* Mark the LSA as reachable */
1558
    en->color = INSPF;
1559

    
1560
    /* Whether the route is preferred in route selection according to 16.4.1 */
1561
    nfa.options = epath_preferred(&nf2->n) ? ORTA_PREF : 0;
1562
    if (en->lsa_type == LSA_T_NSSA)
1563
    {
1564
      nfa.options |= ORTA_NSSA;
1565
      if (rt.propagate)
1566
        nfa.options |= ORTA_PROP;
1567
    }
1568

    
1569
    nfa.tag = rt.tag;
1570
    nfa.rid = en->lsa.rt;
1571
    nfa.oa = atmp; /* undefined in RFC 2328 */
1572
    nfa.en = en; /* store LSA for later (NSSA processing) */
1573

    
1574
    ri_install_ext(p, &rt.net, &nfa);
1575
  }
1576
}
1577

    
1578
/* Cleanup of routing tables and data */
1579
void
1580
ospf_rt_reset(struct ospf_proto *p)
1581
{
1582
  struct ospf_area *oa;
1583
  struct top_hash_entry *en;
1584

    
1585
  /* Reset old routing table */
1586
  FIB_WALK(&p->rtf, ort, ri)
1587
  {
1588
    ri->area_net = 0;
1589
    ri->keep = 0;
1590
    reset_ri(ri);
1591
  }
1592
  FIB_WALK_END;
1593

    
1594
  /* Reset SPF data in LSA db */
1595
  WALK_SLIST(en, p->lsal)
1596
  {
1597
    en->color = OUTSPF;
1598
    en->dist = LSINFINITY;
1599
    en->nhs = NULL;
1600
    en->lb = IPA_NONE;
1601

    
1602
    if (en->mode == LSA_M_RTCALC)
1603
      en->mode = LSA_M_STALE;
1604
  }
1605

    
1606
  WALK_LIST(oa, p->area_list)
1607
  {
1608
    /* Reset ASBR routing tables */
1609
    FIB_WALK(&oa->rtr, ort, ri)
1610
    {
1611
      reset_ri(ri);
1612
    }
1613
    FIB_WALK_END;
1614

    
1615
    /* Reset condensed area networks */
1616
    if (p->areano > 1)
1617
    {
1618
      FIB_WALK(&oa->net_fib, struct area_net, anet)
1619
      {
1620
        anet->active = 0;
1621
        anet->metric = 0;
1622
      }
1623
      FIB_WALK_END;
1624

    
1625
      FIB_WALK(&oa->enet_fib, struct area_net, anet)
1626
      {
1627
        anet->active = 0;
1628
        anet->metric = 0;
1629
      }
1630
      FIB_WALK_END;
1631
    }
1632
  }
1633
}
1634

    
1635
/**
1636
 * ospf_rt_spf - calculate internal routes
1637
 * @p: OSPF protocol instance
1638
 *
1639
 * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
1640
 * It's based on Dijkstra's shortest path tree algorithms.
1641
 * This function is invoked from ospf_disp().
1642
 */
1643
void
1644
ospf_rt_spf(struct ospf_proto *p)
1645
{
1646
  struct ospf_area *oa;
1647

    
1648
  if (p->areano == 0)
1649
    return;
1650

    
1651
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
1652

    
1653
  /* 16. (1) */
1654
  ospf_rt_reset(p);
1655

    
1656
  /* 16. (2) */
1657
  WALK_LIST(oa, p->area_list)
1658
    ospf_rt_spfa(oa);
1659

    
1660
  /* 16. (3) */
1661
  ospf_rt_sum(ospf_main_area(p));
1662

    
1663
  /* 16. (4) */
1664
  WALK_LIST(oa, p->area_list)
1665
    if (oa->trcap && (oa->areaid != 0))
1666
      ospf_rt_sum_tr(oa);
1667

    
1668
  if (p->areano > 1)
1669
    ospf_rt_abr1(p);
1670

    
1671
  /* 16. (5) */
1672
  ospf_ext_spf(p);
1673

    
1674
  if (p->areano > 1)
1675
    ospf_rt_abr2(p);
1676

    
1677
  rt_sync(p);
1678
  lp_flush(p->nhpool);
1679

    
1680
  p->calcrt = 0;
1681
}
1682

    
1683

    
1684
static inline int
1685
inherit_nexthops(struct nexthop *pn)
1686
{
1687
  /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */
1688
  return pn && (ipa_nonzero(pn->gw) || !pn->iface);
1689
}
1690

    
1691
static inline ip_addr
1692
link_lsa_lladdr(struct ospf_proto *p, struct top_hash_entry *en)
1693
{
1694
  struct ospf_lsa_link *link_lsa = en->lsa_body;
1695
  ip6_addr ll = link_lsa->lladdr;
1696

    
1697
  if (ip6_zero(ll))
1698
    return IPA_NONE;
1699

    
1700
  return ospf_is_ip4(p) ? ipa_from_ip4(ospf3_6to4(ll)) : ipa_from_ip6(ll);
1701
}
1702

    
1703
static struct nexthop *
1704
calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
1705
              struct top_hash_entry *par, int pos, uint lif, uint nif)
1706
{
1707
  struct ospf_proto *p = oa->po;
1708
  struct nexthop *pn = par->nhs;
1709
  struct top_hash_entry *link = NULL;
1710
  struct ospf_iface *ifa = NULL;
1711
  ip_addr nh = IPA_NONE;
1712
  u32 rid = en->lsa.rt;
1713

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

    
1718
  /* Usually, we inherit parent nexthops */
1719
  if (inherit_nexthops(pn))
1720
    return pn;
1721

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

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

    
1736
    if (ospf_is_v3(p) && (ifa->iface_id != lif))
1737
      log(L_WARN "%s: Inconsistent interface ID %u/%u", p->p.name, ifa->iface_id, lif);
1738

    
1739
    return new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight);
1740
  }
1741

    
1742
  /* The second case - ptp or ptmp neighbor */
1743
  if ((en->lsa_type == LSA_T_RT) && (par == oa->rt))
1744
  {
1745
    ifa = rt_pos_to_ifa(oa, pos);
1746
    if (!ifa)
1747
      return NULL;
1748

    
1749
    if (ospf_is_v3(p) && (ifa->iface_id != lif))
1750
      log(L_WARN "%s: Inconsistent interface ID %u/%u", p->p.name, ifa->iface_id, lif);
1751

    
1752
    if (ifa->type == OSPF_IT_VLINK)
1753
      return new_nexthop(p, IPA_NONE, NULL, 0);
1754

    
1755
    /* FIXME: On physical PtP links we may skip next-hop altogether */
1756

    
1757
    if (ospf_is_v2(p) || ospf_is_ip6(p))
1758
    {
1759
      /*
1760
       * In this case, next-hop is a source address from neighbor's packets.
1761
       * That is necessary for OSPFv2 and practical for OSPFv3 (as it works even
1762
       * if neighbor uses LinkLSASuppression), but does not work with OSPFv3-AF
1763
       * on IPv4 topology, where src is IPv6 but next-hop should be IPv4.
1764
       */
1765
      struct ospf_neighbor *m = find_neigh(ifa, rid);
1766
      if (!m || (m->state != NEIGHBOR_FULL))
1767
        return NULL;
1768

    
1769
      nh = m->ip;
1770
    }
1771
    else
1772
    {
1773
      /*
1774
       * Next-hop is taken from lladdr field of Link-LSA, based on Neighbor
1775
       * Iface ID (nif) field in our Router-LSA, which is just nbr->iface_id.
1776
       */
1777
      link = ospf_hash_find(p->gr, ifa->iface_id, nif, rid, LSA_T_LINK);
1778
      if (!link)
1779
        return NULL;
1780

    
1781
      nh = link_lsa_lladdr(p, link);
1782
      if (ipa_zero(nh))
1783
        return NULL;
1784
    }
1785

    
1786
    return new_nexthop(p, nh, ifa->iface, ifa->ecmp_weight);
1787
  }
1788

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

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

    
1805
      return new_nexthop(p, en->lb, pn->iface, pn->weight);
1806
    }
1807
    else /* OSPFv3 */
1808
    {
1809
      /*
1810
       * Next-hop is taken from lladdr field of Link-LSA, en->lb_id
1811
       * is computed in link_back().
1812
       */
1813
      link = ospf_hash_find(p->gr, pn->iface->index, en->lb_id, rid, LSA_T_LINK);
1814
      if (!link)
1815
        return NULL;
1816

    
1817
      nh = link_lsa_lladdr(p, link);
1818
      if (ipa_zero(nh))
1819
        return NULL;
1820

    
1821
      return new_nexthop(p, nh, pn->iface, pn->weight);
1822
    }
1823
  }
1824

    
1825
 bad:
1826
  /* Probably bug or some race condition, we log it */
1827
  log(L_ERR "%s: Unexpected case in next hop calculation", p->p.name);
1828
  return NULL;
1829
}
1830

    
1831

    
1832
/* Add LSA into list of candidates in Dijkstra's algorithm */
1833
static void
1834
add_cand(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par,
1835
         u32 dist, int pos, uint lif, uint nif)
1836
{
1837
  struct ospf_proto *p = oa->po;
1838
  node *prev, *n;
1839
  int added = 0;
1840
  struct top_hash_entry *act;
1841

    
1842
  /* 16.1. (2b) */
1843
  if (en == NULL)
1844
    return;
1845
  if (en->lsa.age == LSA_MAXAGE)
1846
    return;
1847

    
1848
  if (ospf_is_v3(p) && (oa->options & OPT_V6) && (en->lsa_type == LSA_T_RT))
1849
  {
1850
    /* In OSPFv3 IPv6 unicast, check V6 flag */
1851
    struct ospf_lsa_rt *rt = en->lsa_body;
1852
    if (!(rt->options & OPT_V6))
1853
      return;
1854
  }
1855

    
1856
  /* 16.1. (2c) */
1857
  if (en->color == INSPF)
1858
    return;
1859

    
1860
  /* 16.1. (2d), also checks that dist < LSINFINITY */
1861
  if (dist > en->dist)
1862
    return;
1863

    
1864
  /* We should check whether there is a reverse link from en to par, */
1865
  if (!link_back(oa, en, par, lif, nif))
1866
    return;
1867

    
1868
  struct nexthop *nhs = calc_next_hop(oa, en, par, pos, lif, nif);
1869
  if (!nhs)
1870
  {
1871
    log(L_WARN "%s: Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
1872
        p->p.name, en->lsa_type, en->lsa.id, en->lsa.rt);
1873
    return;
1874
  }
1875

    
1876
  /* If en->dist > 0, we know that en->color == CANDIDATE and en->nhs is defined. */
1877
  if ((dist == en->dist) && !nh_is_vlink(en->nhs))
1878
  {
1879
    /*
1880
     * For multipath, we should merge nexthops. We merge regular nexthops only.
1881
     * Dummy vlink nexthops are less preferred and handled as a special case.
1882
     *
1883
     * During merging, new nexthops (nhs) can be reused if they are not
1884
     * inherited from the parent (i.e. they are allocated in calc_next_hop()).
1885
     * Current nexthops (en->nhs) can be reused if they weren't inherited in
1886
     * previous steps (that is stored in nhs_reuse, i.e. created by merging or
1887
     * allocated in calc_next_hop()).
1888
     *
1889
     * Generally, a node first inherits shared nexthops from its parent and
1890
     * later possibly gets reusable (private) copy during merging. This is more
1891
     * or less same for both top_hash_entry nodes and orta nodes.
1892
     *
1893
     * Note that when a child inherits a private nexthop from its parent, it
1894
     * should make the nexthop shared for both parent and child, while we only
1895
     * update nhs_reuse for the child node. This makes nhs_reuse field for the
1896
     * parent technically incorrect, but it is not a problem as parent's nhs
1897
     * will not be modified (and nhs_reuse examined) afterwards.
1898
     */
1899

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

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

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

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

    
1923
  prev = NULL;
1924

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

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

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

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

    
1973
  /* This is used for forced reload of routes */
1974
  int reload = (p->calcrt == 2);
1975

    
1976
  OSPF_TRACE(D_EVENTS, "Starting routing table synchronization");
1977

    
1978
  DBG("Now syncing my rt table with nest's\n");
1979
  FIB_ITERATE_INIT(&fit, fib);
1980
again1:
1981
  FIB_ITERATE_START(fib, &fit, ort, nf)
1982
  {
1983
    /* Sanity check of next-hop addresses, failure should not happen */
1984
    if (nf->n.type)
1985
    {
1986
      struct nexthop *nh;
1987
      for (nh = nf->n.nhs; nh; nh = nh->next)
1988
        if (ipa_nonzero(nh->gw))
1989
        {
1990
          neighbor *ng = neigh_find2(&p->p, &nh->gw, nh->iface, 0);
1991
          if (!ng || (ng->scope == SCOPE_HOST))
1992
            { reset_ri(nf); break; }
1993
        }
1994
    }
1995

    
1996
    /* Remove configured stubnets but keep the entries */
1997
    if (nf->n.type && !nf->n.nhs)
1998
    {
1999
      reset_ri(nf);
2000
      nf->keep = 1;
2001
    }
2002

    
2003
    if (nf->n.type) /* Add the route */
2004
    {
2005
      rta a0 = {
2006
        .src = p->p.main_source,
2007
        .source = nf->n.type,
2008
        .scope = SCOPE_UNIVERSE,
2009
        .dest = RTD_UNICAST,
2010
        .nh = *(nf->n.nhs),
2011
      };
2012

    
2013
      if (reload || ort_changed(nf, &a0))
2014
      {
2015
        rta *a = rta_lookup(&a0);
2016
        rte *e = rte_get_temp(a);
2017

    
2018
        rta_free(nf->old_rta);
2019
        nf->old_rta = rta_clone(a);
2020
        e->u.ospf.metric1 = nf->old_metric1 = nf->n.metric1;
2021
        e->u.ospf.metric2 = nf->old_metric2 = nf->n.metric2;
2022
        e->u.ospf.tag = nf->old_tag = nf->n.tag;
2023
        e->u.ospf.router_id = nf->old_rid = nf->n.rid;
2024
        e->pflags = 0;
2025

    
2026
        DBG("Mod rte type %d - %N via %I on iface %s, met %d\n",
2027
            a0.source, nf->fn.addr, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
2028
        rte_update(&p->p, nf->fn.addr, e);
2029
      }
2030
    }
2031
    else if (nf->old_rta)
2032
    {
2033
      /* Remove the route */
2034
      rta_free(nf->old_rta);
2035
      nf->old_rta = NULL;
2036

    
2037
      rte_update(&p->p, nf->fn.addr, NULL);
2038
    }
2039

    
2040
    /* Remove unused rt entry, some special entries are persistent */
2041
    if (!nf->n.type && !nf->external_rte && !nf->area_net && !nf->keep)
2042
    {
2043
      if (nf->lsa_id)
2044
        idm_free(&p->idm, nf->lsa_id);
2045

    
2046
      FIB_ITERATE_PUT(&fit);
2047
      fib_delete(fib, nf);
2048
      goto again1;
2049
    }
2050
  }
2051
  FIB_ITERATE_END;
2052

    
2053

    
2054
  WALK_LIST(oa, p->area_list)
2055
  {
2056
    /* Cleanup ASBR hash tables */
2057
    FIB_ITERATE_INIT(&fit, &oa->rtr);
2058
again2:
2059
    FIB_ITERATE_START(&oa->rtr, &fit, ort, nf)
2060
    {
2061
      if (!nf->n.type)
2062
      {
2063
        FIB_ITERATE_PUT(&fit);
2064
        fib_delete(&oa->rtr, nf);
2065
        goto again2;
2066
      }
2067
    }
2068
    FIB_ITERATE_END;
2069
  }
2070

    
2071
  /* Cleanup stale LSAs */
2072
  WALK_SLIST(en, p->lsal)
2073
    if (en->mode == LSA_M_STALE)
2074
      ospf_flush_lsa(p, en);
2075
}