Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / rt.c @ 48e5f32d

History | View | Annotate | Download (47.9 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 *ifa;
1083
  WALK_LIST(ifa, po->iface_list)
1084
  {
1085
    if (ifa->type == OSPF_IT_VLINK)
1086
    {
1087
      struct top_hash_entry *tmp;
1088
      tmp = ospf_hash_find_rt(po->gr, ifa->voa->areaid, ifa->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 ((ifa->state != OSPF_IS_PTP)
1095
            || (ifa->vifa != nhi)
1096
            || !ipa_equal(ifa->vip, tmp->lb))
1097
        {
1098
          OSPF_TRACE(D_EVENTS, "Vlink peer %R found", tmp->lsa.id);
1099
          ospf_iface_sm(ifa, ISM_DOWN);
1100
          ifa->vifa = nhi;
1101
          ifa->addr = nhi->addr;
1102
          ifa->cost = tmp->dist;
1103
          ifa->vip = tmp->lb;
1104
          ospf_iface_sm(ifa, ISM_UP);
1105
        }
1106
        else if ((ifa->state == OSPF_IS_PTP) && (ifa->cost != tmp->dist))
1107
        {
1108
          ifa->cost = tmp->dist;
1109
          schedule_rt_lsa(po->backbone);
1110
        }
1111
      }
1112
      else
1113
      {
1114
        if (ifa->state > OSPF_IS_DOWN)
1115
        {
1116
          OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", ifa->vid);
1117
          ospf_iface_sm(ifa, ISM_DOWN);
1118
        }
1119
      }
1120
    }
1121
  }
1122
}
1123

    
1124

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

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

    
1136

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

    
1141

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

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

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

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

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

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

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

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

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

    
1196

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

    
1210

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

    
1218

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

    
1223

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

    
1232
  oa->translate = TRANS_OFF;
1233
  schedule_rtcalc(oa->po);
1234
}
1235

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

    
1243

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

    
1251
      if (oa->ac->translator)
1252
        goto decided;
1253

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

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

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

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

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

    
1284
        oa->translate = TRANS_ON;
1285
      }
1286

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

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

    
1298

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

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

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

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

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

    
1329

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

    
1334
    check_sum_net_lsa(po, nf);
1335
    check_nssa_lsa(po, nf);
1336
  }
1337
  FIB_WALK_END;
1338
}
1339

    
1340

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

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

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

    
1374
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
1375

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

    
1382
    if (en->lsa.age == LSA_MAXAGE)
1383
      continue;
1384

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

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

    
1392
    le = en->lsa_body;
1393

    
1394
    rt_metric = le->metric & METRIC_MASK;
1395
    ebit = le->metric & LSA_EXT_EBIT;
1396

    
1397
    if (rt_metric == LSINFINITY)
1398
      continue;
1399

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

    
1413
    if (pxopts & OPT_PX_NU)
1414
      continue;
1415

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

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

    
1427
    rt_propagate = pxopts & OPT_PX_P;
1428
#endif
1429

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

    
1437

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

    
1447
    if (!atmp)
1448
      continue;                        /* Should not happen */
1449

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

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

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

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

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

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

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

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

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

    
1514
    /* Mark the LSA as reachable */
1515
    en->color = INSPF;
1516

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

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

    
1533
    ri_install_ext(po, ip, pxlen, &nfa);
1534
  }
1535
}
1536

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

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

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

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

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

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

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

    
1610
  if (po->areano == 0)
1611
    return;
1612

    
1613
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
1614

    
1615
  /* 16. (1) */
1616
  ospf_rt_reset(po);
1617

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

    
1622
  /* 16. (3) */
1623
  ospf_rt_sum(ospf_main_area(po));
1624

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

    
1630
  if (po->areano > 1)
1631
    ospf_rt_abr1(po);
1632

    
1633
  /* 16. (5) */
1634
  ospf_ext_spf(po);
1635

    
1636
  if (po->areano > 1)
1637
    ospf_rt_abr2(po);
1638

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

    
1645

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

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

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

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

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

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

    
1685
    return new_nexthop(po, IPA_NONE, ifa->iface, ifa->ecmp_weight);
1686
  }
1687

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

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

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

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

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

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

    
1720
    return new_nexthop(po, en->lb, pn->iface, pn->weight);
1721

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

    
1730
    if (!lhe)
1731
      return NULL;
1732

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

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

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

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

    
1755
  if (!s1)
1756
    return 1;
1757

    
1758
  if (!s2)
1759
    return -1;
1760

    
1761
  r = ((int) s2->weight) - ((int) s1->weight);
1762
  if (r)
1763
    return r;
1764

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

    
1769
  return ((int) s1->iface->index) - ((int) s2->iface->index);
1770
}
1771

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

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

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

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

    
1821
  en->nhs_reuse=1;
1822
}
1823

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

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

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

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

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

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

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

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

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

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

    
1893
    /* Fallback to replace old ones */
1894
  }
1895

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

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

    
1908
  prev = NULL;
1909

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

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

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

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

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

    
1963
  OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation");
1964

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

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

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

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

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

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

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

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

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

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

    
2056

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

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