Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (48.1 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
unresolved_vlink(struct mpnh *nhs)
41
{
42
  return nhs && !nhs->iface;
43
}
44

    
45
static inline struct mpnh *
46
new_nexthop(struct proto_ospf *po, ip_addr gw, struct iface *iface, unsigned char weight)
47
{
48
  struct mpnh *nh = lp_alloc(po->nhpool, sizeof(struct mpnh));
49
  nh->gw = gw;
50
  nh->iface = iface;
51
  nh->next = NULL;
52
  nh->weight = weight;
53
  return nh;
54
}
55

    
56
static inline struct mpnh *
57
copy_nexthop(struct proto_ospf *po, struct mpnh *src)
58
{
59
  struct mpnh *nh = lp_alloc(po->nhpool, sizeof(struct mpnh));
60
  nh->gw = src->gw;
61
  nh->iface = src->iface;
62
  nh->next = NULL;
63
  nh->weight = src->weight;
64
  return nh;
65
}
66

    
67

    
68
/* If new is better return 1 */
69
static int
70
ri_better(struct proto_ospf *po, orta *new, orta *old)
71
{
72
  if (old->type == RTS_DUMMY)
73
    return 1;
74

    
75
  if (new->type < old->type)
76
    return 1;
77

    
78
  if (new->type > old->type)
79
    return 0;
80

    
81
  if (new->metric1 < old->metric1)
82
    return 1;
83

    
84
  if (new->metric1 > old->metric1)
85
    return 0;
86

    
87
  return 0;
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(orta *ep)
95
{
96
  return (ep->type == RTS_OSPF) && (ep->oa->areaid != 0);
97
}
98

    
99
/* 16.4. (3), return 1 if new is better */
100
static int
101
ri_better_asbr(struct proto_ospf *po, orta *new, orta *old)
102
{
103
  if (old->type == RTS_DUMMY)
104
    return 1;
105

    
106
  if (!po->rfc1583)
107
  {
108
    int new_pref = epath_preferred(new);
109
    int old_pref = epath_preferred(old);
110

    
111
    if (new_pref > old_pref)
112
      return 1;
113

    
114
    if (new_pref < old_pref)
115
      return 0;
116
  }
117

    
118
  if (new->metric1 < old->metric1)
119
    return 1;
120

    
121
  if (new->metric1 > old->metric1)
122
    return 0;
123

    
124
  /* Larger area ID is preferred */
125
  if (new->oa->areaid > old->oa->areaid)
126
    return 1;
127

    
128
  return 0;
129
}
130

    
131
static int
132
orta_prio(orta *nf)
133
{
134
  /* RFC 3103 2.5 (6e) priorities */
135
  u32 opts = nf->options & (ORTA_NSSA | ORTA_PROP);
136

    
137
  /* A Type-7 LSA with the P-bit set */
138
  if (opts == (ORTA_NSSA | ORTA_PROP))
139
    return 2;
140

    
141
  /* A Type-5 LSA */
142
  if (opts == 0)
143
    return 1;
144

    
145
  return 0;
146
}
147

    
148
/* 16.4. (6), return 1 if new is better */
149
static int
150
ri_better_ext(struct proto_ospf *po, orta *new, orta *old)
151
{
152
  if (old->type == RTS_DUMMY)
153
    return 1;
154

    
155
  /* 16.4. (6a) */
156
  if (new->type < old->type)
157
    return 1;
158

    
159
  if (new->type > old->type)
160
    return 0;
161

    
162
  /* 16.4. (6b), same type */
163
  if (new->type == RTS_OSPF_EXT2)
164
  {
165
    if (new->metric2 < old->metric2)
166
      return 1;
167

    
168
    if (new->metric2 > old->metric2)
169
      return 0;
170
  }
171

    
172
  /* 16.4. (6c) */
173
  if (!po->rfc1583)
174
  {
175
    u32 new_pref = new->options & ORTA_PREF;
176
    u32 old_pref = old->options & ORTA_PREF;
177

    
178
    if (new_pref > old_pref)
179
      return 1;
180

    
181
    if (new_pref < old_pref)
182
      return 0;
183
  }
184

    
185
  /* 16.4. (6d) */
186
  if (new->metric1 < old->metric1)
187
    return 1;
188

    
189
  if (new->metric1 > old->metric1)
190
    return 0;
191

    
192
  /* RFC 3103, 2.5. (6e) */
193
  int new_prio = orta_prio(new);
194
  int old_prio = orta_prio(old);
195

    
196
  if (new_prio > old_prio)
197
    return 1;
198

    
199
  if (old_prio > new_prio)
200
    return 0;
201

    
202
  /* make it more deterministic */
203
  if (new->rid > old->rid)
204
    return 1;
205

    
206
  return 0;
207
}
208

    
209
static inline void
210
ri_install_net(struct proto_ospf *po, ip_addr prefix, int pxlen, orta *new)
211
{
212
  ort *old = (ort *) fib_get(&po->rtf, &prefix, pxlen);
213
  if (ri_better(po, new, &old->n))
214
    memcpy(&old->n, new, sizeof(orta));
215
}
216

    
217
static inline void
218
ri_install_rt(struct ospf_area *oa, u32 rid, orta *new)
219
{
220
  ip_addr addr = ipa_from_rid(rid);
221
  ort *old = (ort *) fib_get(&oa->rtr, &addr, MAX_PREFIX_LENGTH);
222
  if (ri_better(oa->po, new, &old->n))
223
    memcpy(&old->n, new, sizeof(orta));
224
}
225

    
226
static inline void
227
ri_install_asbr(struct proto_ospf *po, ip_addr *addr, orta *new)
228
{
229
  ort *old = (ort *) fib_get(&po->backbone->rtr, addr, MAX_PREFIX_LENGTH);
230
  if (ri_better_asbr(po, new, &old->n))
231
    memcpy(&old->n, new, sizeof(orta));
232
}
233

    
234
static inline void
235
ri_install_ext(struct proto_ospf *po, ip_addr prefix, int pxlen, orta *new)
236
{
237
  ort *old = (ort *) fib_get(&po->rtf, &prefix, pxlen);
238
  if (ri_better_ext(po, new, &old->n))
239
    memcpy(&old->n, new, sizeof(orta));
240
}
241

    
242
static inline struct ospf_iface *
243
rt_pos_to_ifa(struct ospf_area *oa, int pos)
244
{
245
  struct ospf_iface *ifa;
246
  WALK_LIST(ifa, oa->po->iface_list)
247
    if (ifa->oa == oa && pos >= ifa->rt_pos_beg && pos < ifa->rt_pos_end)
248
      return ifa;
249
  return NULL;
250
}
251

    
252
#ifdef OSPFv3
253
static inline struct ospf_iface *
254
px_pos_to_ifa(struct ospf_area *oa, int pos)
255
{
256
  struct ospf_iface *ifa;
257
  WALK_LIST(ifa, oa->po->iface_list)
258
    if (ifa->oa == oa && pos >= ifa->px_pos_beg && pos < ifa->px_pos_end)
259
      return ifa;
260
  return NULL;
261
}
262
#endif
263

    
264

    
265
static void
266
add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en, int pos)
267
{
268
  orta nf = {
269
    .type = RTS_OSPF,
270
    .options = 0,
271
    .metric1 = metric,
272
    .metric2 = LSINFINITY,
273
    .tag = 0,
274
    .rid = en->lsa.rt,
275
    .oa = oa,
276
    .nhs = en->nhs
277
  };
278

    
279
  if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
280
  {
281
    log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
282
        oa->po->proto.name, en->lsa.type, en->lsa.id, en->lsa.rt);
283
    return;
284
  }
285

    
286
  if (en == oa->rt)
287
  {
288
    /* 
289
     * Local stub networks does not have proper iface in en->nhi
290
     * (because they all have common top_hash_entry en).
291
     * We have to find iface responsible for that stub network.
292
     * Configured stubnets does not have any iface. They will
293
     * be removed in rt_sync().
294
     */
295

    
296
    struct ospf_iface *ifa;
297
#ifdef OSPFv2
298
    ifa = rt_pos_to_ifa(oa, pos);
299
#else /* OSPFv3 */
300
    ifa = px_pos_to_ifa(oa, pos);
301
#endif
302

    
303
    nf.nhs = ifa ? new_nexthop(oa->po, IPA_NONE, ifa->iface, ifa->ecmp_weight) : NULL;
304
  }
305

    
306
  ri_install_net(oa->po, px, pxlen, &nf);
307
}
308

    
309
#ifdef OSPFv3
310
static void
311
process_prefixes(struct ospf_area *oa)
312
{
313
  struct proto_ospf *po = oa->po;
314
  // struct proto *p = &po->proto;
315
  struct top_hash_entry *en, *src;
316
  struct ospf_lsa_prefix *px;
317
  ip_addr pxa;
318
  int pxlen;
319
  u8 pxopts;
320
  u16 metric;
321
  u32 *buf;
322
  int i;
323

    
324
  WALK_SLIST(en, po->lsal)
325
  {
326
    if (en->lsa.type != LSA_T_PREFIX)
327
      continue;
328

    
329
    if (en->domain != oa->areaid)
330
      continue;
331

    
332
    if (en->lsa.age == LSA_MAXAGE)
333
      continue;
334

    
335
    px = en->lsa_body;
336

    
337
    /* For router prefix-LSA, we would like to find the first router-LSA */
338
    if (px->ref_type == LSA_T_RT)
339
      src = ospf_hash_find_rt(po->gr, oa->areaid, px->ref_rt);
340
    else
341
      src = ospf_hash_find(po->gr, oa->areaid, px->ref_id, px->ref_rt, px->ref_type);
342

    
343
    if (!src)
344
      continue;
345

    
346
    /* Reachable in SPF */
347
    if (src->color != INSPF)
348
      continue;
349

    
350
    if ((src->lsa.type != LSA_T_RT) && (src->lsa.type != LSA_T_NET))
351
      continue;
352

    
353
    buf = px->rest;
354
    for (i = 0; i < px->pxcount; i++)
355
      {
356
        buf = lsa_get_ipv6_prefix(buf, &pxa, &pxlen, &pxopts, &metric);
357

    
358
        if (pxopts & OPT_PX_NU)
359
          continue;
360

    
361
        /* Store the first global address to use it later as a vlink endpoint */
362
        if ((pxopts & OPT_PX_LA) && ipa_zero(src->lb))
363
          src->lb = pxa;
364

    
365
        add_network(oa, pxa, pxlen, src->dist + metric, src, i);
366
      }
367
  }
368
}
369
#endif
370

    
371

    
372
static void
373
ospf_rt_spfa_rtlinks(struct ospf_area *oa, struct top_hash_entry *act, struct top_hash_entry *en)
374
{
375
  // struct proto *p = &oa->po->proto;
376
  struct proto_ospf *po = oa->po;
377
  ip_addr prefix UNUSED;
378
  int pxlen UNUSED, i;
379

    
380
  struct ospf_lsa_rt *rt = en->lsa_body;
381
  struct ospf_lsa_rt_link *rr = (struct ospf_lsa_rt_link *) (rt + 1);
382

    
383
  for (i = 0; i < lsa_rt_count(&en->lsa); i++)
384
    {
385
      struct ospf_lsa_rt_link *rtl = rr + i;
386
      struct top_hash_entry *tmp = NULL;
387

    
388
      DBG("     Working on link: %R (type: %u)  ", rtl->id, rtl->type);
389
      switch (rtl->type)
390
        {
391
#ifdef OSPFv2
392
        case LSART_STUB:
393
          /*
394
           * RFC 2328 in 16.1. (2a) says to handle stub networks in an
395
           * second phase after the SPF for an area is calculated. We get
396
           * the same result by handing them here because add_network()
397
           * will keep the best (not the first) found route.
398
           */
399
          prefix = ipa_from_u32(rtl->id & rtl->data);
400
          pxlen = ipa_mklen(ipa_from_u32(rtl->data));
401
          add_network(oa, prefix, pxlen, act->dist + rtl->metric, act, i);
402
          break;
403
#endif
404

    
405
        case LSART_NET:
406
#ifdef OSPFv2
407
          /* In OSPFv2, rtl->id is IP addres of DR, Router ID is not known */
408
          tmp = ospf_hash_find_net(po->gr, oa->areaid, rtl->id);
409
#else /* OSPFv3 */
410
          tmp = ospf_hash_find(po->gr, oa->areaid, rtl->nif, rtl->id, LSA_T_NET);
411
#endif
412
          break;
413

    
414
        case LSART_VLNK:
415
        case LSART_PTP:
416
          tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id);
417
          break;
418

    
419
        default:
420
          log("Unknown link type in router lsa. (rid = %R)", act->lsa.id);
421
          break;
422
        }
423

    
424
      if (tmp)
425
        DBG("Going to add cand, Mydist: %u, Req: %u\n",
426
            tmp->dist, act->dist + rtl->metric);
427
      add_cand(&oa->cand, tmp, act, act->dist + rtl->metric, oa, i);
428
    }
429
}
430

    
431
/* RFC 2328 16.1. calculating shortest paths for an area */
432
static void
433
ospf_rt_spfa(struct ospf_area *oa)
434
{
435
  struct proto *p = &oa->po->proto;
436
  struct proto_ospf *po = oa->po;
437
  struct ospf_lsa_rt *rt;
438
  struct ospf_lsa_net *ln;
439
  struct top_hash_entry *act, *tmp;
440
  ip_addr prefix UNUSED;
441
  int pxlen UNUSED;
442
  u32 i, *rts;
443
  node *n;
444

    
445
  if (oa->rt == NULL)
446
    return;
447

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

    
450
  /* 16.1. (1) */
451
  init_list(&oa->cand);                /* Empty list of candidates */
452
  oa->trcap = 0;
453

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

    
456
  oa->rt->dist = 0;
457
  oa->rt->color = CANDIDATE;
458
  add_head(&oa->cand, &oa->rt->cn);
459
  DBG("RT LSA: rt: %R, id: %R, type: %u\n",
460
      oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa.type);
461

    
462
  while (!EMPTY_LIST(oa->cand))
463
  {
464
    n = HEAD(oa->cand);
465
    act = SKIP_BACK(struct top_hash_entry, cn, n);
466
    rem_node(n);
467

    
468
    DBG("Working on LSA: rt: %R, id: %R, type: %u\n",
469
        act->lsa.rt, act->lsa.id, act->lsa.type);
470

    
471
    act->color = INSPF;
472
    switch (act->lsa.type)
473
    {
474
    case LSA_T_RT:
475
      rt = (struct ospf_lsa_rt *) act->lsa_body;
476
      if (rt->options & OPT_RT_V)
477
        oa->trcap = 1;
478

    
479
      /*
480
       * In OSPFv3, all routers are added to per-area routing
481
       * tables. But we use it just for ASBRs and ABRs. For the
482
       * purpose of the last step in SPF - prefix-LSA processing in
483
       * process_prefixes(), we use information stored in LSA db.
484
       */
485
      if (((rt->options & OPT_RT_E) || (rt->options & OPT_RT_B))
486
          && (act->lsa.rt != po->router_id))
487
      {
488
        orta nf = {
489
          .type = RTS_OSPF,
490
          .options = rt->options,
491
          .metric1 = act->dist,
492
          .metric2 = LSINFINITY,
493
          .tag = 0,
494
          .rid = act->lsa.rt,
495
          .oa = oa,
496
          .nhs = act->nhs
497
        };
498
        ri_install_rt(oa, act->lsa.rt, &nf);
499
      }
500

    
501
#ifdef OSPFv2
502
      ospf_rt_spfa_rtlinks(oa, act, act);
503
#else /* OSPFv3 */
504
      /* Errata 2078 to RFC 5340 4.8.1 - skip links from non-routing nodes */
505
      if ((act != oa->rt) && !(rt->options & OPT_R))
506
        break;
507

    
508
      for (tmp = ospf_hash_find_rt_first(po->gr, act->domain, act->lsa.rt);
509
           tmp; tmp = ospf_hash_find_rt_next(tmp))
510
        ospf_rt_spfa_rtlinks(oa, act, tmp);
511
#endif
512

    
513
      break;
514
    case LSA_T_NET:
515
      ln = act->lsa_body;
516

    
517
#ifdef OSPFv2
518
      prefix = ipa_and(ipa_from_u32(act->lsa.id), ln->netmask);
519
      pxlen = ipa_mklen(ln->netmask);
520
      add_network(oa, prefix, pxlen, act->dist, act, -1);
521
#endif
522

    
523
      rts = (u32 *) (ln + 1);
524
      for (i = 0; i < lsa_net_count(&act->lsa); i++)
525
      {
526
        DBG("     Working on router %R ", rts[i]);
527
        tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]);
528
        if (tmp != NULL)
529
          DBG("Found :-)\n");
530
        else
531
          DBG("Not found!\n");
532
        add_cand(&oa->cand, tmp, act, act->dist, oa, -1);
533
      }
534
      break;
535
    }
536
  }
537

    
538
#ifdef OSPFv3
539
  process_prefixes(oa);
540
#endif
541
}
542

    
543
static int
544
link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par)
545
{
546
  u32 i, *rts;
547
  struct ospf_lsa_net *ln;
548
  struct ospf_lsa_rt *rt;
549
  struct ospf_lsa_rt_link *rtl, *rr;
550
  struct top_hash_entry *tmp;
551
  struct proto_ospf *po = oa->po;
552

    
553
  if (!en || !par) return 0;
554

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

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

    
565
  en->lb = IPA_NONE;
566
#ifdef OSPFv3
567
  en->lb_id = 0;
568
#endif
569
  switch (en->lsa.type)
570
  {
571
    case LSA_T_RT:
572
      rt = (struct ospf_lsa_rt *) en->lsa_body;
573
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
574
      for (i = 0; i < lsa_rt_count(&en->lsa); i++)
575
      {
576
        rtl = (rr + i);
577
        switch (rtl->type)
578
        {
579
        case LSART_STUB:
580
          break;
581
        case LSART_NET:
582
#ifdef OSPFv2
583
          /* In OSPFv2, rtl->id is IP addres of DR, Router ID is not known */
584
          tmp = ospf_hash_find_net(po->gr, oa->areaid, rtl->id);
585
#else /* OSPFv3 */
586
          tmp = ospf_hash_find(po->gr, oa->areaid, rtl->nif, rtl->id, LSA_T_NET);
587
#endif
588
          if (tmp == par)
589
          {
590
#ifdef OSPFv2
591
            en->lb = ipa_from_u32(rtl->data);
592
#else /* OSPFv3 */
593
            en->lb_id = rtl->lif;
594
#endif
595
            return 1;
596
          }
597

    
598
          break;
599
        case LSART_VLNK:
600
        case LSART_PTP:
601
          /* Not necessary the same link, see RFC 2328 [23] */
602
          tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id);
603
          if (tmp == par)
604
            return 1;
605

    
606
          break;
607
        default:
608
          log(L_WARN "Unknown link type in router lsa. (rid = %R)", en->lsa.rt);
609
          break;
610
        }
611
      }
612
      break;
613
    case LSA_T_NET:
614
      ln = en->lsa_body;
615
      rts = (u32 *) (ln + 1);
616
      for (i = 0; i < lsa_net_count(&en->lsa); i++)
617
      {
618
        tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]);
619
        if (tmp == par)
620
          return 1;
621
      }
622
      break;
623
    default:
624
      bug("Unknown lsa type %x.", en->lsa.type);
625
  }
626
  return 0;
627
}
628

    
629
  
630
/* RFC 2328 16.2. calculating inter-area routes */
631
static void
632
ospf_rt_sum(struct ospf_area *oa)
633
{
634
  struct proto_ospf *po = oa->po;
635
  struct proto *p = &po->proto;
636
  struct top_hash_entry *en;
637
  ip_addr ip = IPA_NONE;
638
  u32 dst_rid = 0;
639
  u32 metric, options;
640
  ort *abr;
641
  int pxlen = -1, type = -1;
642

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

    
645
  WALK_SLIST(en, po->lsal)
646
  {
647
    if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
648
      continue;
649

    
650
    if (en->domain != oa->areaid)
651
      continue;
652

    
653
    /* 16.2. (1a) */
654
    if (en->lsa.age == LSA_MAXAGE)
655
      continue;
656

    
657
    /* 16.2. (2) */
658
    if (en->lsa.rt == po->router_id)
659
      continue;
660

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

    
663
    if (en->lsa.type == LSA_T_SUM_NET)
664
    {
665
#ifdef OSPFv2
666
      struct ospf_lsa_sum *ls = en->lsa_body;
667
      ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask);
668
      pxlen = ipa_mklen(ls->netmask);
669
#else /* OSPFv3 */
670
      u8 pxopts;
671
      u16 rest;
672
      struct ospf_lsa_sum_net *ls = en->lsa_body;
673
      lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest);
674

    
675
      if (pxopts & OPT_PX_NU)
676
        continue;
677
#endif
678

    
679
      if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
680
      {
681
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
682
            p->name, en->lsa.type, en->lsa.id, en->lsa.rt);
683
        continue;
684
      }
685

    
686
      metric = ls->metric & METRIC_MASK;
687
      options = 0;
688
      type = ORT_NET;
689
    }
690
    else /* LSA_T_SUM_RT */
691
    {
692
#ifdef OSPFv2
693
      struct ospf_lsa_sum *ls = en->lsa_body;
694
      dst_rid = en->lsa.id;
695
      options = 0;
696
#else /* OSPFv3 */
697
      struct ospf_lsa_sum_rt *ls = en->lsa_body;
698
      dst_rid = ls->drid; 
699
      options = ls->options & OPTIONS_MASK;
700
#endif
701
      
702
      /* We don't want local router in ASBR routing table */
703
      if (dst_rid == po->router_id)
704
        continue;
705

    
706
      metric = ls->metric & METRIC_MASK;
707
      options |= ORTA_ASBR;
708
      type = ORT_ROUTER;
709
    }
710

    
711
    /* 16.2. (1b) */
712
    if (metric == LSINFINITY)
713
      continue;
714

    
715
    /* 16.2. (4) */
716
    ip_addr abrip = ipa_from_rid(en->lsa.rt);
717
    abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
718
    if (!abr || !abr->n.type)
719
      continue;
720

    
721
    if (!(abr->n.options & ORTA_ABR))
722
      continue;
723

    
724
    /* This check is not mentioned in RFC 2328 */
725
    if (abr->n.type != RTS_OSPF)
726
      continue;
727

    
728
    /* 16.2. (5) */
729
    orta nf = {
730
      .type = RTS_OSPF_IA,
731
      .options = options,
732
      .metric1 = abr->n.metric1 + metric,
733
      .metric2 = LSINFINITY,
734
      .tag = 0,
735
      .rid = en->lsa.rt, /* ABR ID */
736
      .oa = oa,
737
      .nhs = abr->n.nhs
738
    };
739

    
740
    if (type == ORT_NET)
741
      ri_install_net(po, ip, pxlen, &nf);
742
    else
743
      ri_install_rt(oa, dst_rid, &nf);
744
  }
745
}
746

    
747
/* RFC 2328 16.3. examining summary-LSAs in transit areas */
748
static void
749
ospf_rt_sum_tr(struct ospf_area *oa)
750
{
751
  struct proto *p = &oa->po->proto;
752
  struct proto_ospf *po = oa->po;
753
  struct ospf_area *bb = po->backbone;
754
  ip_addr abrip;
755
  struct top_hash_entry *en;
756
  u32 dst_rid, metric;
757
  ort *re = NULL, *abr;
758

    
759

    
760
  if (!bb) return;
761

    
762
  WALK_SLIST(en, po->lsal)
763
  {
764
    if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
765
      continue;
766

    
767
    if (en->domain != oa->areaid)
768
      continue;
769

    
770
    /* 16.3 (1a) */
771
    if (en->lsa.age == LSA_MAXAGE)
772
      continue;
773

    
774
    /* 16.3 (2) */
775
    if (en->lsa.rt == po->router_id)
776
      continue;
777

    
778
    if (en->lsa.type == LSA_T_SUM_NET)
779
    {
780
      ip_addr ip;
781
      int pxlen;
782
#ifdef OSPFv2
783
      struct ospf_lsa_sum *ls = en->lsa_body;
784
      ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask);
785
      pxlen = ipa_mklen(ls->netmask);
786
#else /* OSPFv3 */
787
      u8 pxopts;
788
      u16 rest;
789
      struct ospf_lsa_sum_net *ls = en->lsa_body;
790
      lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest);
791

    
792
      if (pxopts & OPT_PX_NU)
793
        continue;
794
#endif
795

    
796
      if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
797
      {
798
        log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
799
            p->name, en->lsa.type, en->lsa.id, en->lsa.rt);
800
        continue;
801
      }
802

    
803
      metric = ls->metric & METRIC_MASK;
804
      re = fib_find(&po->rtf, &ip, pxlen);
805
    }
806
    else // en->lsa.type == LSA_T_SUM_RT
807
    {
808
#ifdef OSPFv2
809
      struct ospf_lsa_sum *ls = en->lsa_body;
810
      dst_rid = en->lsa.id;
811
#else /* OSPFv3 */
812
      struct ospf_lsa_sum_rt *ls = en->lsa_body;
813
      dst_rid = ls->drid; 
814
#endif
815

    
816
      metric = ls->metric & METRIC_MASK;
817
      ip_addr ip = ipa_from_rid(dst_rid);
818
      re = fib_find(&bb->rtr, &ip, MAX_PREFIX_LENGTH);
819
    }
820

    
821
    /* 16.3 (1b) */ 
822
    if (metric == LSINFINITY) 
823
      continue; 
824

    
825
    /* 16.3 (3) */
826
    if (!re || !re->n.type)
827
      continue;
828

    
829
    if (re->n.oa->areaid != 0)
830
      continue;
831

    
832
    if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA))
833
      continue;
834

    
835
    /* 16.3. (4) */
836
    abrip = ipa_from_rid(en->lsa.rt);
837
    abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
838
    if (!abr || !abr->n.type)
839
      continue;
840

    
841
    metric = abr->n.metric1 + metric; /* IAC */
842

    
843
    /* 16.3. (5) */
844
    if ((metric < re->n.metric1) || 
845
        ((metric == re->n.metric1) && unresolved_vlink(re->n.nhs)))
846
    {
847
      /* We want to replace the next-hop even if the metric is equal
848
         to replace a virtual next-hop through vlink with a real one.
849
         Proper ECMP would merge nexthops here, but we do not do that.
850
         We restrict nexthops to fit one area to simplify check
851
         12.4.3 p4 in decide_sum_lsa() */
852

    
853
      re->n.metric1 = metric;
854
      re->n.voa = oa;
855
      re->n.nhs = abr->n.nhs;
856
    }
857
  }
858
}
859

    
860
/* Decide about originating or flushing summary LSAs for condended area networks */
861
static int
862
decide_anet_lsa(struct ospf_area *oa, struct area_net *anet, struct ospf_area *anet_oa)
863
{
864
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
865
  if (!oa_is_ext(oa) && !oa->ac->summary)
866
    return 0;
867

    
868
  if (oa == anet_oa)
869
    return 0;
870

    
871
  /* Do not condense routing info when exporting from backbone to the transit area */
872
  if ((anet_oa == oa->po->backbone) && oa->trcap)
873
    return 0;
874

    
875
  return (anet->active && !anet->hidden);
876
}
877

    
878
/* Decide about originating or flushing summary LSAs (12.4.3) */
879
static int
880
decide_sum_lsa(struct ospf_area *oa, ort *nf, int dest)
881
{
882
  /* 12.4.3.1. - for stub/NSSA areas, originating summary routes is configurable */
883
  if (!oa_is_ext(oa) && !oa->ac->summary)
884
    return 0;
885

    
886
  /* Invalid field - no route */
887
  if (!nf->n.type)
888
    return 0;
889

    
890
  /* 12.4.3 p2 */
891
  if (nf->n.type > RTS_OSPF_IA)
892
    return 0;
893

    
894
  /* 12.4.3 p3 */
895
  if ((nf->n.oa->areaid == oa->areaid))
896
    return 0;
897

    
898
  /* 12.4.3 p4 */
899
  if (nf->n.voa && (nf->n.voa->areaid == oa->areaid))
900
    return 0;
901

    
902
  /* 12.4.3 p5 */
903
  if (nf->n.metric1 >= LSINFINITY)
904
    return 0;
905

    
906
  /* 12.4.3 p6 - AS boundary router */
907
  if (dest == ORT_ROUTER)
908
  {
909
    /* We call decide_sum_lsa() on preferred ASBR entries, no need for 16.4. (3) */
910
    /* 12.4.3 p1 */
911
    return oa_is_ext(oa) && (nf->n.options & ORTA_ASBR);
912
  }
913

    
914
  /* 12.4.3 p7 - inter-area route */
915
  if (nf->n.type == RTS_OSPF_IA)
916
  {
917
    /* Inter-area routes are not repropagated into the backbone */
918
    return (oa != oa->po->backbone);
919
  }
920

    
921
  /* 12.4.3 p8 - intra-area route */
922

    
923
  /* Do not condense routing info when exporting from backbone to the transit area */
924
  if ((nf->n.oa == oa->po->backbone) && oa->trcap)
925
    return 1;
926

    
927
  struct area_net *anet = (struct area_net *)
928
    fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen);
929

    
930
  /* Condensed area network found */ 
931
  if (anet)
932
    return 0;
933

    
934
  return 1;
935
}
936

    
937
/* RFC 2328 16.7. p1 - originate or flush summary LSAs */
938
static inline void
939
check_sum_net_lsa(struct proto_ospf *po, ort *nf)
940
{
941
  struct area_net *anet = NULL;
942
  struct ospf_area *anet_oa = NULL;
943

    
944
  /* RT entry marked as area network */
945
  if (nf->fn.x0)
946
  {
947
    /* It is a default route for stub areas, handled entirely in ospf_rt_abr() */
948
    if (nf->fn.pxlen == 0)
949
      return;
950

    
951
    /* Find that area network */
952
    WALK_LIST(anet_oa, po->area_list)
953
    {
954
      anet = (struct area_net *) fib_find(&anet_oa->net_fib, &nf->fn.prefix, nf->fn.pxlen);
955
      if (anet)
956
        break;
957
    }
958
  }
959

    
960
  struct ospf_area *oa;
961
  WALK_LIST(oa, po->area_list)
962
  {
963
    if (anet && decide_anet_lsa(oa, anet, anet_oa))
964
      originate_sum_net_lsa(oa, &nf->fn, anet->metric);
965
    else if (decide_sum_lsa(oa, nf, ORT_NET))
966
      originate_sum_net_lsa(oa, &nf->fn, nf->n.metric1);
967
    else
968
      flush_sum_lsa(oa, &nf->fn, ORT_NET);
969
  }
970
}
971

    
972
static inline void
973
check_sum_rt_lsa(struct proto_ospf *po, ort *nf)
974
{
975
  struct ospf_area *oa;
976
  WALK_LIST(oa, po->area_list)
977
  {
978
    if (decide_sum_lsa(oa, nf, ORT_ROUTER))
979
      originate_sum_rt_lsa(oa, &nf->fn, nf->n.metric1, nf->n.options);
980
    else
981
      flush_sum_lsa(oa, &nf->fn, ORT_ROUTER);
982
  }
983
}
984

    
985
static inline int
986
decide_nssa_lsa(ort *nf, u32 *rt_metric, ip_addr *rt_fwaddr, u32 *rt_tag)
987
{
988
  struct ospf_area *oa = nf->n.oa;
989
  struct top_hash_entry *en = nf->n.en;
990
  int propagate;
991

    
992
  if (!rt_is_nssa(nf) || !oa->translate)
993
    return 0;
994

    
995
  /* Condensed area network found */ 
996
  if (fib_route(&oa->enet_fib, nf->fn.prefix, nf->fn.pxlen))
997
    return 0;
998

    
999
  if (!en || (en->lsa.type != LSA_T_NSSA))
1000
    return 0;
1001

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

    
1005
#ifdef OSPFv2
1006
  *rt_fwaddr = le->fwaddr;
1007
  *rt_tag = le->tag;
1008
  propagate = en->lsa.options & OPT_P;
1009
#else /* OSPFv3 */
1010
  u32 *buf = le->rest;
1011
  u8 pxlen = (*buf >> 24);
1012
  u8 pxopts = (*buf >> 16);
1013
  buf += IPV6_PREFIX_WORDS(pxlen);  /* Skip the IP prefix */
1014

    
1015
  if (pxopts & OPT_PX_NU)
1016
    return 0;
1017

    
1018
  if (le->metric & LSA_EXT_FBIT)
1019
    buf = lsa_get_ipv6_addr(buf, rt_fwaddr);
1020
  else
1021
    *rt_fwaddr = IPA_NONE;
1022

    
1023
  if (le->metric & LSA_EXT_TBIT)
1024
    *rt_tag = *buf++;
1025
  else
1026
    *rt_tag = 0;
1027

    
1028
  propagate = pxopts & OPT_PX_P;
1029
#endif
1030

    
1031
  if (!propagate || ipa_zero(*rt_fwaddr))
1032
    return 0;
1033

    
1034
  *rt_metric = le->metric & (METRIC_MASK | LSA_EXT_EBIT);
1035
  return 1;
1036
}
1037

    
1038
/* RFC 3103 3.2 - translating Type-7 LSAs into Type-5 LSAs */
1039
static inline void
1040
check_nssa_lsa(struct proto_ospf *po, ort *nf)
1041
{
1042
  struct fib_node *fn = &nf->fn;
1043
  struct area_net *anet = NULL;
1044
  struct ospf_area *oa = NULL;
1045
  u32 rt_metric, rt_tag;
1046
  ip_addr rt_fwaddr;
1047

    
1048
  /* Do not translate LSA if there is already the external LSA from route export */
1049
  if (fn->x1 == EXT_EXPORT)
1050
    return;
1051

    
1052
  /* RT entry marked as area network */
1053
  if (fn->x0)
1054
  {
1055
    /* Find that area network */
1056
    WALK_LIST(oa, po->area_list)
1057
    {
1058
      anet = (struct area_net *) fib_find(&oa->enet_fib, &fn->prefix, fn->pxlen);
1059
      if (anet)
1060
        break;
1061
    }
1062
  }
1063

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

    
1068
  /* RFC 3103 3.2 (2) - originate the same network */
1069
  else if (decide_nssa_lsa(nf, &rt_metric, &rt_fwaddr, &rt_tag))
1070
    originate_ext_lsa(po->backbone, fn, EXT_NSSA, rt_metric, rt_fwaddr, rt_tag, 0);
1071

    
1072
  else if (fn->x1 == EXT_NSSA)
1073
    flush_ext_lsa(po->backbone, fn, 0);
1074
}
1075

    
1076
/* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1077
static void
1078
ospf_check_vlinks(struct proto_ospf *po)
1079
{
1080
  struct proto *p = &po->proto;
1081

    
1082
  struct ospf_iface *iface;
1083
  WALK_LIST(iface, po->iface_list)
1084
  {
1085
    if (iface->type == OSPF_IT_VLINK)
1086
    {
1087
      struct top_hash_entry *tmp;
1088
      tmp = ospf_hash_find_rt(po->gr, iface->voa->areaid, iface->vid);
1089

    
1090
      if (tmp && (tmp->color == INSPF) && ipa_nonzero(tmp->lb) && tmp->nhs)
1091
      {
1092
        struct ospf_iface *nhi = ospf_iface_find(po, tmp->nhs->iface);
1093

    
1094
        if ((iface->state != OSPF_IS_PTP)
1095
            || (iface->vifa != nhi)
1096
            || !ipa_equal(iface->vip, tmp->lb))
1097
        {
1098
          OSPF_TRACE(D_EVENTS, "Vlink peer %R found", tmp->lsa.id);
1099
          ospf_iface_sm(iface, ISM_DOWN);
1100
          iface->vifa = nhi;
1101
          iface->iface = nhi->iface;
1102
          iface->addr = nhi->addr;
1103
          iface->sk = nhi->sk;
1104
          iface->cost = tmp->dist;
1105
          iface->vip = tmp->lb;
1106
          ospf_iface_sm(iface, ISM_UP);
1107
        }
1108
        else if ((iface->state == OSPF_IS_PTP) && (iface->cost != tmp->dist))
1109
        {
1110
          iface->cost = tmp->dist;
1111
          schedule_rt_lsa(po->backbone);
1112
        }
1113
      }
1114
      else
1115
      {
1116
        if (iface->state > OSPF_IS_DOWN)
1117
        {
1118
          OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", iface->vid);
1119
          ospf_iface_sm(iface, ISM_DOWN);
1120
        }
1121
      }
1122
    }
1123
  }
1124
}
1125

    
1126

    
1127
/* Miscellaneous route processing that needs to be done by ABRs */
1128
static void
1129
ospf_rt_abr1(struct proto_ospf *po)
1130
{
1131
  struct area_net *anet;
1132
  ort *nf, *default_nf;
1133

    
1134
  FIB_WALK(&po->rtf, nftmp)
1135
  {
1136
    nf = (ort *) nftmp;
1137

    
1138

    
1139
    /* RFC 2328 G.3 - incomplete resolution of virtual next hops */
1140
    if (nf->n.type && unresolved_vlink(nf->n.nhs))
1141
      reset_ri(nf);
1142

    
1143

    
1144
    /* Compute condensed area networks */
1145
    if (nf->n.type == RTS_OSPF)
1146
    {
1147
      anet = (struct area_net *) fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen);
1148
      if (anet)
1149
      {
1150
        if (!anet->active)
1151
        {
1152
          anet->active = 1;
1153

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

    
1158
          /* 16.2. (3) */
1159
          if (nfi->n.type == RTS_OSPF_IA)
1160
            reset_ri(nfi);
1161
        }
1162

    
1163
        if (anet->metric < nf->n.metric1)
1164
          anet->metric = nf->n.metric1;
1165
      }
1166
    }
1167
  }
1168
  FIB_WALK_END;
1169

    
1170
  ip_addr addr = IPA_NONE;
1171
  default_nf = (ort *) fib_get(&po->rtf, &addr, 0);
1172
  default_nf->fn.x0 = 1; /* keep persistent */
1173

    
1174
  struct ospf_area *oa;
1175
  WALK_LIST(oa, po->area_list)
1176
  {
1177

    
1178
    /* 12.4.3.1. - originate or flush default route for stub/NSSA areas */
1179
    if (oa_is_stub(oa) || (oa_is_nssa(oa) && !oa->ac->summary))
1180
      originate_sum_net_lsa(oa, &default_nf->fn, oa->ac->default_cost);
1181
    else
1182
      flush_sum_lsa(oa, &default_nf->fn, ORT_NET);
1183

    
1184
    /*
1185
     * Originate type-7 default route for NSSA areas
1186
     *
1187
     * Because type-7 default LSAs are originated by ABRs, they do not
1188
     * collide with other type-7 LSAs (as ABRs generate type-5 LSAs
1189
     * for both external route export or external-NSSA translation),
1190
     * so we use 0 for the src arg.
1191
     */
1192

    
1193
    if (oa_is_nssa(oa) && oa->ac->default_nssa)
1194
      originate_ext_lsa(oa, &default_nf->fn, 0, oa->ac->default_cost, IPA_NONE, 0, 0);
1195
    else
1196
      flush_ext_lsa(oa, &default_nf->fn, 1);
1197

    
1198

    
1199
    /* RFC 2328 16.4. (3) - precompute preferred ASBR entries */
1200
    if (oa_is_ext(oa))
1201
    {
1202
      FIB_WALK(&oa->rtr, nftmp)
1203
      {
1204
        nf = (ort *) nftmp;
1205
        if (nf->n.options & ORTA_ASBR)
1206
          ri_install_asbr(po, &nf->fn.prefix, &nf->n);
1207
      }
1208
      FIB_WALK_END;
1209
    }
1210
  }
1211

    
1212

    
1213
  /* Originate or flush ASBR summary LSAs */
1214
  FIB_WALK(&po->backbone->rtr, nftmp)
1215
  {
1216
    check_sum_rt_lsa(po, (ort *) nftmp);
1217
  }
1218
  FIB_WALK_END;
1219

    
1220

    
1221
  /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */
1222
  ospf_check_vlinks(po);
1223
}
1224

    
1225

    
1226
static void
1227
translator_timer_hook(timer *timer)
1228
{
1229
  struct ospf_area *oa = timer->data;
1230
  
1231
  if (oa->translate != TRANS_WAIT)
1232
    return;
1233

    
1234
  oa->translate = TRANS_OFF;
1235
  schedule_rtcalc(oa->po);
1236
}
1237

    
1238
static void
1239
ospf_rt_abr2(struct proto_ospf *po)
1240
{
1241
  struct ospf_area *oa;
1242
  struct top_hash_entry *en;
1243
  ort *nf, *nf2;
1244

    
1245

    
1246
  /* RFC 3103 3.1 - type-7 translator election */
1247
  struct ospf_area *bb = po->backbone;
1248
  WALK_LIST(oa, po->area_list)
1249
    if (oa_is_nssa(oa))
1250
    {
1251
      int translate = 1;
1252

    
1253
      if (oa->ac->translator)
1254
        goto decided;
1255

    
1256
      FIB_WALK(&oa->rtr, nftmp)
1257
      {
1258
        nf = (ort *) nftmp;
1259
        if (!nf->n.type || !(nf->n.options & ORTA_ABR))
1260
          continue;
1261

    
1262
        nf2 = fib_find(&bb->rtr, &nf->fn.prefix, MAX_PREFIX_LENGTH);
1263
        if (!nf2 || !nf2->n.type || !(nf2->n.options & ORTA_ABR))
1264
          continue;
1265

    
1266
        en = ospf_hash_find_rt(po->gr, oa->areaid, nf->n.rid);
1267
        if (!en || (en->color != INSPF))
1268
          continue;
1269

    
1270
        struct ospf_lsa_rt *rt = en->lsa_body;
1271
        /* There is better candidate - Nt-bit or higher Router ID */
1272
        if ((rt->options & OPT_RT_NT) || (po->router_id < nf->n.rid))
1273
        {
1274
          translate = 0;
1275
          goto decided;
1276
        }
1277
      }
1278
      FIB_WALK_END;
1279

    
1280
    decided:
1281
      if (translate && (oa->translate != TRANS_ON))
1282
      {
1283
        if (oa->translate == TRANS_WAIT)
1284
          tm_stop(oa->translator_timer);
1285

    
1286
        oa->translate = TRANS_ON;
1287
      }
1288

    
1289
      if (!translate && (oa->translate == TRANS_ON))
1290
      {
1291
        if (oa->translator_timer == NULL)
1292
          oa->translator_timer = tm_new_set(po->proto.pool, translator_timer_hook, oa, 0, 0);
1293

    
1294
        /* Schedule the end of translation */
1295
        tm_start(oa->translator_timer, oa->ac->transint);
1296
        oa->translate = TRANS_WAIT;
1297
      }
1298
    }
1299

    
1300

    
1301
  /* Compute condensed external networks */
1302
  FIB_WALK(&po->rtf, nftmp)
1303
  {
1304
    nf = (ort *) nftmp;
1305
    if (rt_is_nssa(nf) && (nf->n.options & ORTA_PROP))
1306
    {
1307
      struct area_net *anet = (struct area_net *)
1308
        fib_route(&nf->n.oa->enet_fib, nf->fn.prefix, nf->fn.pxlen);
1309

    
1310
      if (anet)
1311
      {
1312
        if (!anet->active)
1313
        {
1314
          anet->active = 1;
1315

    
1316
          /* Get a RT entry and mark it to know that it is an area network */
1317
          nf2 = (ort *) fib_get(&po->rtf, &anet->fn.prefix, anet->fn.pxlen);
1318
          nf2->fn.x0 = 1;
1319
        }
1320

    
1321
        u32 metric = (nf->n.type == RTS_OSPF_EXT1) ?
1322
          nf->n.metric1 : ((nf->n.metric2 + 1) | LSA_EXT_EBIT);
1323

    
1324
        if (anet->metric < metric)
1325
          anet->metric = metric;
1326
      }
1327
    }
1328
  }
1329
  FIB_WALK_END;
1330

    
1331

    
1332
  FIB_WALK(&po->rtf, nftmp)
1333
  {
1334
    nf = (ort *) nftmp;
1335

    
1336
    check_sum_net_lsa(po, nf);
1337
    check_nssa_lsa(po, nf);
1338
  }
1339
  FIB_WALK_END;
1340
}
1341

    
1342

    
1343
/* Like fib_route(), but ignores dummy rt entries */
1344
static void *
1345
ospf_fib_route(struct fib *f, ip_addr a, int len)
1346
{
1347
  ip_addr a0;
1348
  ort *nf;
1349

    
1350
  while (len >= 0)
1351
  {
1352
    a0 = ipa_and(a, ipa_mkmask(len));
1353
    nf = fib_find(f, &a0, len);
1354
    if (nf && nf->n.type)
1355
      return nf;
1356
    len--;
1357
  }
1358
  return NULL;
1359
}
1360

    
1361
/* RFC 2328 16.4. calculating external routes */
1362
static void
1363
ospf_ext_spf(struct proto_ospf *po)
1364
{
1365
  ort *nf1, *nf2;
1366
  orta nfa;
1367
  struct top_hash_entry *en;
1368
  struct proto *p = &po->proto;
1369
  struct ospf_lsa_ext *le;
1370
  int pxlen, ebit, rt_fwaddr_valid, rt_propagate;
1371
  ip_addr ip, rtid, rt_fwaddr;
1372
  u32 br_metric, rt_metric, rt_tag;
1373
  struct ospf_area *atmp;
1374
  struct mpnh* nhs = NULL;
1375

    
1376
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
1377

    
1378
  WALK_SLIST(en, po->lsal)
1379
  {
1380
    /* 16.4. (1) */
1381
    if ((en->lsa.type != LSA_T_EXT) && (en->lsa.type != LSA_T_NSSA))
1382
      continue;
1383

    
1384
    if (en->lsa.age == LSA_MAXAGE)
1385
      continue;
1386

    
1387
    /* 16.4. (2) */
1388
    if (en->lsa.rt == po->router_id)
1389
      continue;
1390

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

    
1394
    le = en->lsa_body;
1395

    
1396
    rt_metric = le->metric & METRIC_MASK;
1397
    ebit = le->metric & LSA_EXT_EBIT;
1398

    
1399
    if (rt_metric == LSINFINITY)
1400
      continue;
1401

    
1402
#ifdef OSPFv2
1403
    ip = ipa_and(ipa_from_u32(en->lsa.id), le->netmask);
1404
    pxlen = ipa_mklen(le->netmask);
1405
    rt_fwaddr = le->fwaddr;
1406
    rt_fwaddr_valid = !ipa_equal(rt_fwaddr, IPA_NONE);
1407
    rt_tag = le->tag;
1408
    rt_propagate = en->lsa.options & OPT_P;
1409
#else /* OSPFv3 */
1410
    u8 pxopts;
1411
    u16 rest;
1412
    u32 *buf = le->rest;
1413
    buf = lsa_get_ipv6_prefix(buf, &ip, &pxlen, &pxopts, &rest);
1414

    
1415
    if (pxopts & OPT_PX_NU)
1416
      continue;
1417

    
1418
    rt_fwaddr_valid = le->metric & LSA_EXT_FBIT;
1419
    if (rt_fwaddr_valid)
1420
      buf = lsa_get_ipv6_addr(buf, &rt_fwaddr);
1421
    else 
1422
      rt_fwaddr = IPA_NONE;
1423

    
1424
    if (le->metric & LSA_EXT_TBIT)
1425
      rt_tag = *buf++;
1426
    else
1427
      rt_tag = 0;
1428

    
1429
    rt_propagate = pxopts & OPT_PX_P;
1430
#endif
1431

    
1432
    if (pxlen < 0 || pxlen > MAX_PREFIX_LENGTH)
1433
    {
1434
      log(L_WARN "%s: Invalid prefix in LSA (Type: %04x, Id: %R, Rt: %R)",
1435
          p->name, en->lsa.type, en->lsa.id, en->lsa.rt);
1436
      continue;
1437
    }
1438

    
1439

    
1440
    /* 16.4. (3) */
1441
    /* If there are more areas, we already precomputed preferred ASBR
1442
       entries in ospf_rt_abr1() and stored them in the backbone
1443
       table. For NSSA, we examine the area to which the LSA is assigned */
1444
    if (en->lsa.type == LSA_T_EXT)
1445
      atmp = ospf_main_area(po);
1446
    else /* NSSA */
1447
      atmp = ospf_find_area(po, en->domain);
1448

    
1449
    if (!atmp)
1450
      continue;                        /* Should not happen */
1451

    
1452
    rtid = ipa_from_rid(en->lsa.rt);
1453
    nf1 = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH);
1454

    
1455
    if (!nf1 || !nf1->n.type)
1456
      continue;                        /* No AS boundary router found */
1457

    
1458
    if (!(nf1->n.options & ORTA_ASBR))
1459
      continue;                        /* It is not ASBR */
1460

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

    
1467
    if (!rt_fwaddr_valid)
1468
    {
1469
      nf2 = nf1;
1470
      nhs = nf1->n.nhs;
1471
      br_metric = nf1->n.metric1;
1472
    }
1473
    else
1474
    {
1475
      nf2 = ospf_fib_route(&po->rtf, rt_fwaddr, MAX_PREFIX_LENGTH);
1476
      if (!nf2)
1477
        continue;
1478

    
1479
      if (en->lsa.type == LSA_T_EXT)
1480
      {
1481
        /* For ext routes, we accept intra-area or inter-area routes */
1482
        if ((nf2->n.type != RTS_OSPF) && (nf2->n.type != RTS_OSPF_IA))
1483
          continue;
1484
      }
1485
      else /* NSSA */
1486
      {
1487
        /* For NSSA routes, we accept just intra-area in the same area */
1488
        if ((nf2->n.type != RTS_OSPF) || (nf2->n.oa != atmp))
1489
          continue;
1490
      }
1491

    
1492
      /* Next-hop is a part of a configured stubnet */
1493
      if (!nf2->n.nhs)
1494
        continue;
1495

    
1496
      nhs = nf2->n.nhs;
1497
      /* If gw is zero, it is a device route */
1498
      if (ipa_zero(nhs->gw))
1499
        nhs = new_nexthop(po, rt_fwaddr, nhs->iface, nhs->weight);
1500
      br_metric = nf2->n.metric1;
1501
    }
1502

    
1503
    if (ebit)
1504
    {
1505
      nfa.type = RTS_OSPF_EXT2;
1506
      nfa.metric1 = br_metric;
1507
      nfa.metric2 = rt_metric;
1508
    }
1509
    else
1510
    {
1511
      nfa.type = RTS_OSPF_EXT1;
1512
      nfa.metric1 = br_metric + rt_metric;
1513
      nfa.metric2 = LSINFINITY;
1514
    }
1515

    
1516
    /* Mark the LSA as reachable */
1517
    en->color = INSPF;
1518

    
1519
    /* Whether the route is preferred in route selection according to 16.4.1 */
1520
    nfa.options = epath_preferred(&nf2->n) ? ORTA_PREF : 0;
1521
    if (en->lsa.type == LSA_T_NSSA)
1522
    {
1523
      nfa.options |= ORTA_NSSA;
1524
      if (rt_propagate)
1525
        nfa.options |= ORTA_PROP;
1526
    }
1527

    
1528
    nfa.tag = rt_tag;
1529
    nfa.rid = en->lsa.rt;
1530
    nfa.oa = atmp; /* undefined in RFC 2328 */
1531
    nfa.voa = NULL;
1532
    nfa.nhs = nhs;
1533
    nfa.en = en; /* store LSA for later (NSSA processing) */
1534

    
1535
    ri_install_ext(po, ip, pxlen, &nfa);
1536
  }
1537
}
1538

    
1539
/* Cleanup of routing tables and data */
1540
void
1541
ospf_rt_reset(struct proto_ospf *po)
1542
{
1543
  struct ospf_area *oa;
1544
  struct top_hash_entry *en;
1545
  struct area_net *anet;
1546
  ort *ri;
1547

    
1548
  /* Reset old routing table */
1549
  FIB_WALK(&po->rtf, nftmp)
1550
  {
1551
    ri = (ort *) nftmp;
1552
    ri->fn.x0 = 0;
1553
    reset_ri(ri);
1554
  }
1555
  FIB_WALK_END;
1556

    
1557
  /* Reset SPF data in LSA db */
1558
  WALK_SLIST(en, po->lsal)
1559
  {
1560
    en->color = OUTSPF;
1561
    en->dist = LSINFINITY;
1562
    en->nhs = NULL;
1563
    en->lb = IPA_NONE;
1564
  }
1565

    
1566
  WALK_LIST(oa, po->area_list)
1567
  {
1568
    /* Reset ASBR routing tables */
1569
    FIB_WALK(&oa->rtr, nftmp)
1570
    {
1571
      ri = (ort *) nftmp;
1572
      reset_ri(ri);
1573
    }
1574
    FIB_WALK_END;
1575

    
1576
    /* Reset condensed area networks */
1577
    if (po->areano > 1)
1578
    {
1579
      FIB_WALK(&oa->net_fib, nftmp)
1580
      {
1581
        anet = (struct area_net *) nftmp;
1582
        anet->active = 0;
1583
        anet->metric = 0;
1584
      }
1585
      FIB_WALK_END;
1586

    
1587
      FIB_WALK(&oa->enet_fib, nftmp)
1588
      {
1589
        anet = (struct area_net *) nftmp;
1590
        anet->active = 0;
1591
        anet->metric = 0;
1592
      }
1593
      FIB_WALK_END;
1594
    }
1595
  }
1596
}
1597

    
1598
/**
1599
 * ospf_rt_spf - calculate internal routes
1600
 * @po: OSPF protocol
1601
 *
1602
 * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
1603
 * It's based on Dijkstra's shortest path tree algorithms.
1604
 * This function is invoked from ospf_disp().
1605
 */
1606
void
1607
ospf_rt_spf(struct proto_ospf *po)
1608
{
1609
  struct proto *p = &po->proto;
1610
  struct ospf_area *oa;
1611

    
1612
  if (po->areano == 0)
1613
    return;
1614

    
1615
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
1616

    
1617
  /* 16. (1) */
1618
  ospf_rt_reset(po);
1619

    
1620
  /* 16. (2) */
1621
  WALK_LIST(oa, po->area_list)
1622
    ospf_rt_spfa(oa);
1623

    
1624
  /* 16. (3) */
1625
  ospf_rt_sum(ospf_main_area(po));
1626

    
1627
  /* 16. (4) */
1628
  WALK_LIST(oa, po->area_list)
1629
    if (oa->trcap && (oa->areaid != 0))
1630
      ospf_rt_sum_tr(oa);
1631

    
1632
  if (po->areano > 1)
1633
    ospf_rt_abr1(po);
1634

    
1635
  /* 16. (5) */
1636
  ospf_ext_spf(po);
1637

    
1638
  if (po->areano > 1)
1639
    ospf_rt_abr2(po);
1640

    
1641
  rt_sync(po);
1642
  lp_flush(po->nhpool);
1643
  
1644
  po->calcrt = 0;
1645
}
1646

    
1647

    
1648
static inline int
1649
inherit_nexthops(struct mpnh *pn)
1650
{
1651
  /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */
1652
  return pn && (ipa_nonzero(pn->gw) || !pn->iface);
1653
}
1654

    
1655
static struct mpnh *
1656
calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
1657
              struct top_hash_entry *par, int pos)
1658
{
1659
  // struct proto *p = &oa->po->proto;
1660
  struct proto_ospf *po = oa->po;
1661
  struct mpnh *pn = par->nhs;
1662
  struct ospf_iface *ifa;
1663
  u32 rid = en->lsa.rt;
1664

    
1665
  /* 16.1.1. The next hop calculation */
1666
  DBG("     Next hop calculating for id: %R rt: %R type: %u\n",
1667
      en->lsa.id, en->lsa.rt, en->lsa.type);
1668

    
1669
  /* Usually, we inherit parent nexthops */
1670
  if (inherit_nexthops(pn))
1671
    return pn;
1672

    
1673
  /* 
1674
   * There are three cases:
1675
   * 1) en is a local network (and par is root)
1676
   * 2) en is a ptp or ptmp neighbor (and par is root)
1677
   * 3) en is a bcast or nbma neighbor (and par is local network)
1678
   */
1679

    
1680
  /* The first case - local network */
1681
  if ((en->lsa.type == LSA_T_NET) && (par == oa->rt))
1682
  {
1683
    ifa = rt_pos_to_ifa(oa, pos);
1684
    if (!ifa)
1685
      return NULL;
1686

    
1687
    return new_nexthop(po, IPA_NONE, ifa->iface, ifa->ecmp_weight);
1688
  }
1689

    
1690
  /* The second case - ptp or ptmp neighbor */
1691
  if ((en->lsa.type == LSA_T_RT) && (par == oa->rt))
1692
  {
1693
    ifa = rt_pos_to_ifa(oa, pos);
1694
    if (!ifa)
1695
      return NULL;
1696

    
1697
    if (ifa->type == OSPF_IT_VLINK)
1698
      return new_nexthop(po, IPA_NONE, NULL, 0);
1699

    
1700
    struct ospf_neighbor *m = find_neigh(ifa, rid);
1701
    if (!m || (m->state != NEIGHBOR_FULL))
1702
      return NULL;
1703

    
1704
    return new_nexthop(po, m->ip, ifa->iface, ifa->ecmp_weight);
1705
  }
1706

    
1707
  /* The third case - bcast or nbma neighbor */
1708
  if ((en->lsa.type == LSA_T_RT) && (par->lsa.type == LSA_T_NET))
1709
  {
1710
    /* par->nhi should be defined from parent's calc_next_hop() */
1711
    if (!pn)
1712
      goto bad;
1713

    
1714
#ifdef OSPFv2
1715
    /*
1716
     * In this case, next-hop is the same as link-back, which is
1717
     * already computed in link_back().
1718
     */
1719
    if (ipa_zero(en->lb))
1720
      goto bad;
1721

    
1722
    return new_nexthop(po, en->lb, pn->iface, pn->weight);
1723

    
1724
#else /* OSPFv3 */
1725
    /*
1726
     * Next-hop is taken from lladdr field of Link-LSA, en->lb_id
1727
     * is computed in link_back().
1728
     */
1729
    struct top_hash_entry *lhe;
1730
    lhe = ospf_hash_find(po->gr, pn->iface->index, en->lb_id, rid, LSA_T_LINK);
1731

    
1732
    if (!lhe)
1733
      return NULL;
1734

    
1735
    struct ospf_lsa_link *llsa = lhe->lsa_body;
1736
      
1737
    if (ipa_zero(llsa->lladdr))
1738
      return NULL;
1739

    
1740
    return new_nexthop(po, llsa->lladdr, pn->iface, pn->weight);
1741
#endif
1742
  }
1743

    
1744
 bad:
1745
  /* Probably bug or some race condition, we log it */
1746
  log(L_ERR "Unexpected case in next hop calculation");
1747
  return NULL;
1748
}
1749

    
1750
/* Compare nexthops during merge.
1751
   We need to maintain nhs sorted to eliminate duplicities */
1752
static int
1753
cmp_nhs(struct mpnh *s1, struct mpnh *s2)
1754
{
1755
  int r;
1756

    
1757
  if (!s1)
1758
    return 1;
1759

    
1760
  if (!s2)
1761
    return -1;
1762

    
1763
  r = ((int) s2->weight) - ((int) s1->weight);
1764
  if (r)
1765
    return r;
1766

    
1767
  r = ipa_compare(s1->gw, s2->gw);
1768
  if (r)
1769
    return r;
1770

    
1771
  return ((int) s1->iface->index) - ((int) s2->iface->index);
1772
}
1773

    
1774
static void
1775
merge_nexthops(struct proto_ospf *po, struct top_hash_entry *en,
1776
               struct top_hash_entry *par, struct mpnh *new)
1777
{
1778
  if (en->nhs == new)
1779
    return;
1780

    
1781
  int r1 = en->nhs_reuse;
1782
  int r2 = (par->nhs != new);
1783
  int count = po->ecmp;
1784
  struct mpnh *s1 = en->nhs;
1785
  struct mpnh *s2 = new;
1786
  struct mpnh **n = &(en->nhs);
1787

    
1788
  /*
1789
   * r1, r2 signalize whether we can reuse nexthops from s1, s2.
1790
   * New nexthops (s2, new) can be reused if they are not inherited
1791
   * from the parent (i.e. it is allocated in calc_next_hop()).
1792
   * Current nexthops (s1, en->nhs) can be reused if they weren't
1793
   * inherited in previous steps (that is stored in nhs_reuse,
1794
   * i.e. created by merging or allocalted in calc_next_hop()).
1795
   *
1796
   * Generally, a node first inherits shared nexthops from its
1797
   * parent and later possibly gets reusable copy during merging.
1798
   */
1799

    
1800
  while ((s1 || s2) && count--)
1801
  {
1802
    int cmp = cmp_nhs(s1, s2);
1803
    if (cmp < 0)
1804
    {
1805
      *n = r1 ? s1 : copy_nexthop(po, s1);
1806
      s1 = s1->next;
1807
    }
1808
    else if (cmp > 0)
1809
    {
1810
      *n = r2 ? s2 : copy_nexthop(po, s2);
1811
      s2 = s2->next;
1812
    }
1813
    else
1814
    {
1815
      *n = r1 ? s1 : (r2 ? s2 : copy_nexthop(po, s1));
1816
      s1 = s1->next;
1817
      s2 = s2->next;
1818
    }
1819
    n = &((*n)->next);
1820
  }
1821
  *n = NULL;
1822

    
1823
  en->nhs_reuse=1;
1824
}
1825

    
1826
/* Add LSA into list of candidates in Dijkstra's algorithm */
1827
static void
1828
add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
1829
         u32 dist, struct ospf_area *oa, int pos)
1830
{
1831
  struct proto_ospf *po = oa->po;
1832
  node *prev, *n;
1833
  int added = 0;
1834
  struct top_hash_entry *act;
1835

    
1836
  /* 16.1. (2b) */
1837
  if (en == NULL)
1838
    return;
1839
  if (en->lsa.age == LSA_MAXAGE)
1840
    return;
1841

    
1842
#ifdef OSPFv3
1843
  if (en->lsa.type == LSA_T_RT)
1844
    {
1845
      struct ospf_lsa_rt *rt = en->lsa_body;
1846
      if (!(rt->options & OPT_V6))
1847
        return;
1848
    }
1849
#endif
1850

    
1851
  /* 16.1. (2c) */
1852
  if (en->color == INSPF)
1853
    return;
1854

    
1855
  /* 16.1. (2d), also checks that dist < LSINFINITY */
1856
  if (dist > en->dist)
1857
    return;
1858

    
1859
  /* We should check whether there is a reverse link from en to par, */
1860
  if (!link_back(oa, en, par))
1861
    return;
1862

    
1863
  struct mpnh *nhs = calc_next_hop(oa, en, par, pos);
1864
  if (!nhs)
1865
  {
1866
    log(L_WARN "Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
1867
        en->lsa.type, en->lsa.id, en->lsa.rt);
1868
    return;
1869
  }
1870

    
1871
  if (dist == en->dist)
1872
  {
1873
    /*
1874
     * For multipath, we should merge nexthops. We do not mix dummy
1875
     * vlink nexthops, device nexthops and gateway nexthops. We merge
1876
     * gateway nexthops only. We prefer device nexthops over gateway
1877
     * nexthops and gateway nexthops over vlink nexthops. We either
1878
     * keep old nexthops, merge old and new, or replace old with new.
1879
     * 
1880
     * We know that en->color == CANDIDATE and en->nhs is defined.
1881
     */
1882
    struct mpnh *onhs = en->nhs;
1883

    
1884
    /* Keep old ones */
1885
    if (!po->ecmp || !nhs->iface || (onhs->iface && ipa_zero(onhs->gw)))
1886
      return;
1887

    
1888
    /* Merge old and new */
1889
    if (ipa_nonzero(nhs->gw) && ipa_nonzero(onhs->gw))
1890
    {
1891
      merge_nexthops(po, en, par, nhs);
1892
      return;
1893
    }
1894

    
1895
    /* Fallback to replace old ones */
1896
  }
1897

    
1898
  DBG("     Adding candidate: rt: %R, id: %R, type: %u\n",
1899
      en->lsa.rt, en->lsa.id, en->lsa.type);
1900

    
1901
  if (en->color == CANDIDATE)
1902
  {                                /* We found a shorter path */
1903
    rem_node(&en->cn);
1904
  }
1905
  en->nhs = nhs;
1906
  en->dist = dist;
1907
  en->color = CANDIDATE;
1908
  en->nhs_reuse = (par->nhs != nhs);
1909

    
1910
  prev = NULL;
1911

    
1912
  if (EMPTY_LIST(*l))
1913
  {
1914
    add_head(l, &en->cn);
1915
  }
1916
  else
1917
  {
1918
    WALK_LIST(n, *l)
1919
    {
1920
      act = SKIP_BACK(struct top_hash_entry, cn, n);
1921
      if ((act->dist > dist) ||
1922
          ((act->dist == dist) && (act->lsa.type == LSA_T_RT)))
1923
      {
1924
        if (prev == NULL)
1925
          add_head(l, &en->cn);
1926
        else
1927
          insert_node(&en->cn, prev);
1928
        added = 1;
1929
        break;
1930
      }
1931
      prev = n;
1932
    }
1933

    
1934
    if (!added)
1935
    {
1936
      add_tail(l, &en->cn);
1937
    }
1938
  }
1939
}
1940

    
1941
static inline int
1942
ort_changed(ort *nf, rta *nr)
1943
{
1944
  rta *or = nf->old_rta;
1945
  return !or ||
1946
    (nf->n.metric1 != nf->old_metric1) || (nf->n.metric2 != nf->old_metric2) ||
1947
    (nf->n.tag != nf->old_tag) || (nf->n.rid != nf->old_rid) ||
1948
    (nr->source != or->source) || (nr->dest != or->dest) ||
1949
    (nr->iface != or->iface) || !ipa_equal(nr->gw, or->gw) ||
1950
    !mpnh_same(nr->nexthops, or->nexthops);
1951
}
1952

    
1953
static void
1954
rt_sync(struct proto_ospf *po)
1955
{
1956
  struct proto *p = &po->proto;
1957
  struct fib_iterator fit;
1958
  struct fib *fib = &po->rtf;
1959
  ort *nf;
1960
  struct ospf_area *oa;
1961

    
1962
  /* This is used for forced reload of routes */
1963
  int reload = (po->calcrt == 2);
1964

    
1965
  OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation");
1966

    
1967
  DBG("Now syncing my rt table with nest's\n");
1968
  FIB_ITERATE_INIT(&fit, fib);
1969
again1:
1970
  FIB_ITERATE_START(fib, &fit, nftmp)
1971
  {
1972
    nf = (ort *) nftmp;
1973

    
1974
    /* Sanity check of next-hop addresses, failure should not happen */
1975
    if (nf->n.type)
1976
    {
1977
      struct mpnh *nh;
1978
      for (nh = nf->n.nhs; nh; nh = nh->next)
1979
        if (ipa_nonzero(nh->gw))
1980
        {
1981
          neighbor *ng = neigh_find2(p, &nh->gw, nh->iface, 0);
1982
          if (!ng || (ng->scope == SCOPE_HOST))
1983
            { reset_ri(nf); break; }
1984
        }
1985
    }
1986

    
1987
    /* Remove configured stubnets */
1988
    if (!nf->n.nhs)
1989
      reset_ri(nf);
1990

    
1991
    if (nf->n.type) /* Add the route */
1992
    {
1993
      rta a0 = {
1994
        .proto = p,
1995
        .source = nf->n.type,
1996
        .scope = SCOPE_UNIVERSE,
1997
        .cast = RTC_UNICAST,
1998
      };
1999

    
2000
      if (nf->n.nhs->next)
2001
      {
2002
        a0.dest = RTD_MULTIPATH;
2003
        a0.nexthops = nf->n.nhs;
2004
      }
2005
      else if (ipa_nonzero(nf->n.nhs->gw))
2006
      {
2007
        a0.dest = RTD_ROUTER;
2008
        a0.iface = nf->n.nhs->iface;
2009
        a0.gw = nf->n.nhs->gw;
2010
      }
2011
      else
2012
      {
2013
        a0.dest = RTD_DEVICE;
2014
        a0.iface = nf->n.nhs->iface;
2015
      }
2016

    
2017
      if (reload || ort_changed(nf, &a0))
2018
      {
2019
        net *ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
2020
        rta *a = rta_lookup(&a0);
2021
        rte *e = rte_get_temp(a);
2022

    
2023
        rta_free(nf->old_rta);
2024
        nf->old_rta = rta_clone(a);
2025
        e->u.ospf.metric1 = nf->old_metric1 = nf->n.metric1;
2026
        e->u.ospf.metric2 = nf->old_metric2 = nf->n.metric2;
2027
        e->u.ospf.tag = nf->old_tag = nf->n.tag;
2028
        e->u.ospf.router_id = nf->old_rid = nf->n.rid;
2029
        e->pflags = 0;
2030
        e->net = ne;
2031
        e->pref = p->preference;
2032

    
2033
        DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n",
2034
            a0.source, nf->fn.prefix, nf->fn.pxlen, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
2035
        rte_update(p->table, ne, p, p, e);
2036
      }
2037
    }
2038
    else if (nf->old_rta)
2039
    {
2040
      /* Remove the route */
2041
      rta_free(nf->old_rta);
2042
      nf->old_rta = NULL;
2043

    
2044
      net *ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
2045
      rte_update(p->table, ne, p, p, NULL);
2046
    }
2047

    
2048
    /* Remove unused rt entry. Entries with fn.x0 == 1 are persistent. */
2049
    if (!nf->n.type && !nf->fn.x0 && !nf->fn.x1)
2050
    {
2051
      FIB_ITERATE_PUT(&fit, nftmp);
2052
      fib_delete(fib, nftmp);
2053
      goto again1;
2054
    }
2055
  }
2056
  FIB_ITERATE_END(nftmp);
2057

    
2058

    
2059
  WALK_LIST(oa, po->area_list)
2060
  {
2061
    /* Cleanup ASBR hash tables */
2062
    FIB_ITERATE_INIT(&fit, &oa->rtr);
2063
again2:
2064
    FIB_ITERATE_START(&oa->rtr, &fit, nftmp)
2065
    {
2066
      nf = (ort *) nftmp;
2067

    
2068
      if (!nf->n.type)
2069
      {
2070
        FIB_ITERATE_PUT(&fit, nftmp);
2071
        fib_delete(&oa->rtr, nftmp);
2072
        goto again2;
2073
      }
2074
    }
2075
    FIB_ITERATE_END(nftmp);
2076
  }
2077
}