Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (29.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);
14
static int calc_next_hop(struct ospf_area *oa,
15
                         struct top_hash_entry *en,
16
                         struct top_hash_entry *par);
17
static void ospf_ext_spf(struct proto_ospf *po);
18
static void rt_sync(struct proto_ospf *po);
19

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

    
28

    
29
static void
30
fill_ri(orta * orta)
31
{
32
  orta->type = RTS_DUMMY;
33
  orta->options = 0;
34
  orta->oa = NULL;
35
  orta->metric1 = LSINFINITY;
36
  orta->metric2 = LSINFINITY;
37
  orta->nh = IPA_NONE;
38
  orta->ifa = NULL;
39
  orta->ar = NULL;
40
  orta->tag = 0;
41
  orta->rid = 0;
42
}
43

    
44
void
45
ospf_rt_initort(struct fib_node *fn)
46
{
47
  ort *ri = (ort *) fn;
48
  fill_ri(&ri->n);
49
  memcpy(&ri->o, &ri->n, sizeof(orta));
50
  ri->efn = NULL;
51
}
52

    
53
/* If new is better return 1 */
54

    
55
/* 
56
 * This is hard to understand:
57
 * If rfc1583 is set to 1, it work likes normal route_better()
58
 * But if it is set to 0, it prunes number of AS boundary
59
 * routes before it starts the router decision
60
 */
61
static int
62
ri_better(struct proto_ospf *po, orta * new, ort *nefn, orta * old, ort *oefn, int rfc1583)
63
{
64
  int newtype = new->type;
65
  int oldtype = old->type;
66

    
67
  if (old->type == RTS_DUMMY)
68
    return 1;
69

    
70
  if (old->metric1 == LSINFINITY)
71
    return 1;
72

    
73
  if (!rfc1583)
74
  {
75
    if ((new->type < RTS_OSPF_EXT1) && (new->oa->areaid == 0)) newtype = RTS_OSPF_IA;
76
    if ((old->type < RTS_OSPF_EXT1) && (old->oa->areaid == 0)) oldtype = RTS_OSPF_IA;
77
  }
78

    
79
  if (newtype < oldtype)
80
    return 1;
81

    
82
  if (newtype > oldtype)
83
    return 0;
84

    
85
  /* Same type */
86
  if (new->type == RTS_OSPF_EXT2)
87
  {
88
    if (new->metric2 < old->metric2) return 1;
89
    if (new->metric2 > old->metric2) return 0;
90
  }
91

    
92
  if (((new->type == RTS_OSPF_EXT2) || (new->type == RTS_OSPF_EXT1)) && (!po->rfc1583))
93
  {
94
    newtype = nefn->n.type;
95
    oldtype = oefn->n.type;
96

    
97
    if (nefn->n.oa->areaid == 0) newtype = RTS_OSPF_IA;
98
    if (oefn->n.oa->areaid == 0) oldtype = RTS_OSPF_IA;
99

    
100
    if (newtype < oldtype) return 1;
101
    if (newtype > oldtype) return 0;
102
  }
103

    
104
  if (new->metric1 < old->metric1)
105
    return 1;
106

    
107
  if (new->metric1 > old->metric1)
108
    return 0;
109

    
110
  if (new->oa->areaid > old->oa->areaid) return 1;        /* Larger AREAID is preffered */
111

    
112
  return 0;                        /* Old is shorter or same */
113
}
114

    
115
static void
116
ri_install(struct proto_ospf *po, ip_addr prefix, int pxlen, int dest,
117
           orta * new, ort * ipath)
118
{
119
  struct ospf_area *oa = new->oa;
120
  ort *old;
121

    
122
  if (dest == ORT_NET)
123
  {
124
    struct area_net *anet;
125
    old = (ort *) fib_get(&po->rtf, &prefix, pxlen);
126
    if (ri_better(po, new, ipath, &old->n, old->efn, 1))
127
    {
128
      memcpy(&old->n, new, sizeof(orta));
129
      old->efn = ipath;
130
      if ((new->type == RTS_OSPF) && (anet = (struct area_net *)fib_route(&oa->net_fib, prefix, pxlen)))
131
      {
132
        anet->active = 1;
133
        if (new->metric1 > anet->metric) anet->metric = new->metric1;
134
      }
135
    }
136
  }
137
  else
138
  {
139
    old = (ort *) fib_get(&oa->rtr, &prefix, pxlen);
140

    
141
    if (ri_better(po, new, ipath, &old->n, old->efn, 1))
142
    {
143
      memcpy(&old->n, new, sizeof(orta));
144
      old->efn = ipath;
145
    }
146
  }
147
}
148

    
149
static void
150
add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en)
151
{
152
  orta nf;
153
  nf.type = RTS_OSPF;
154
  nf.options = 0;
155
  nf.metric1 = metric;
156
  nf.metric2 = LSINFINITY;
157
  nf.tag = 0;
158
  nf.oa = oa;
159
  nf.ar = en;
160
  nf.nh = en->nh;
161
  nf.ifa = en->nhi;
162
  nf.rid = en->lsa.rt;
163

    
164
  /* FIXME check nf.ifa on stubs */
165
  ri_install(oa->po, px, pxlen, ORT_NET, &nf, NULL);
166
}
167

    
168
#ifdef OSPFv3
169
static void
170
process_prefixes(struct ospf_area *oa)
171
{
172
  struct proto_ospf *po = oa->po;
173
  struct proto *p = &po->proto;
174
  struct top_hash_entry *en, *src;
175
  struct ospf_lsa_prefix *px;
176
  ip_addr pxa;
177
  int pxlen;
178
  u8 pxopts;
179
  u16 metric;
180
  u32 *buf;
181
  int i;
182

    
183
  WALK_SLIST(en, po->lsal)
184
  {
185
    if (en->lsa.type != LSA_T_PREFIX)
186
      continue;
187

    
188
    if (en->domain != oa->areaid)
189
      continue;
190

    
191
    if (en->lsa.age == LSA_MAXAGE)
192
      continue;
193

    
194
    px = en->lsa_body;
195

    
196
    /* For router prefix-LSA, we would like to find the first router-LSA */
197
    if (px->ref_type == LSA_T_RT)
198
      src = ospf_hash_find_rt(po->gr, oa->areaid, px->ref_rt);
199
    else
200
      src = ospf_hash_find(po->gr, oa->areaid, px->ref_id, px->ref_rt, px->ref_type);
201

    
202
    if (!src)
203
      continue;
204

    
205
    if (src->lsa.age == LSA_MAXAGE)
206
      continue;
207

    
208
    if ((src->lsa.type != LSA_T_RT) && (src->lsa.type != LSA_T_NET))
209
      continue;
210

    
211
    buf = px->rest;
212
    for (i = 0; i < px->pxcount; i++)
213
      {
214
        buf = lsa_get_ipv6_prefix(buf, &pxa, &pxlen, &pxopts, &metric);
215

    
216
        if (pxopts & OPT_PX_NU)
217
          continue;
218

    
219
        add_network(oa, pxa, pxlen, src->dist + metric, src);
220
      }
221
  }
222
}
223
#endif
224

    
225

    
226
static void
227
ospf_rt_spfa_rtlinks(struct ospf_area *oa, struct top_hash_entry *act, struct top_hash_entry *en)
228
{
229
  // struct proto *p = &oa->po->proto;
230
  struct proto_ospf *po = oa->po;
231
  orta nf;
232
  u32 i;
233

    
234
  struct ospf_lsa_rt *rt = en->lsa_body;
235
  struct ospf_lsa_rt_link *rr = (struct ospf_lsa_rt_link *) (rt + 1);
236

    
237
  for (i = 0; i < lsa_rt_count(&en->lsa); i++)
238
    {
239
      struct ospf_lsa_rt_link *rtl = rr + i;
240
      struct top_hash_entry *tmp = NULL;
241

    
242
      DBG("     Working on link: %R (type: %u)  ", rtl->id, rtl->type);
243
      switch (rtl->type)
244
        {
245
#ifdef OSPFv2
246
        case LSART_STUB:
247
          /*
248
           * This violates rfc2328! But it is mostly harmless.
249
           */
250
          DBG("\n");
251

    
252
          nf.type = RTS_OSPF;
253
          nf.options = 0;
254
          nf.metric1 = act->dist + rtl->metric;
255
          nf.metric2 = LSINFINITY;
256
          nf.tag = 0;
257
          nf.oa = oa;
258
          nf.ar = act;
259
          nf.nh = act->nh;
260
          nf.ifa = act->nhi;
261
          nf.rid = act->lsa.rt;
262

    
263
          if (act == oa->rt)
264
            {
265
              struct ospf_iface *iff;
266

    
267
              WALK_LIST(iff, po->iface_list)        /* Try to find corresponding interface */
268
                {
269
                  if (iff->iface && (iff->type != OSPF_IT_VLINK) &&
270
                      (rtl->id == (ipa_to_u32(ipa_mkmask(iff->iface->addr->pxlen))
271
                                   & ipa_to_u32(iff->iface->addr->prefix))))        /* No VLINK and IP must match */
272
                    {
273
                      nf.ifa = iff;
274
                      break;
275
                    }
276
                }
277
            }
278

    
279
          if (!nf.ifa)
280
            continue;
281

    
282
          ri_install(po, ipa_from_u32(rtl->id),
283
                     ipa_mklen(ipa_from_u32(rtl->data)), ORT_NET, &nf, NULL);
284
          break;
285
#endif
286

    
287
        case LSART_NET:
288
#ifdef OSPFv2
289
          /* In OSPFv2, rtl->id is IP addres of DR, Router ID is not known */
290
          tmp = ospf_hash_find_net(po->gr, oa->areaid, rtl->id);
291
#else /* OSPFv3 */
292
          tmp = ospf_hash_find(po->gr, oa->areaid, rtl->nif, rtl->id, LSA_T_NET);
293
#endif
294
          if (tmp == NULL)
295
            DBG("Not found!\n");
296
          else
297
            DBG("Found. :-)\n");
298
          break;
299

    
300
        case LSART_VLNK:
301
        case LSART_PTP:
302
          tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id);
303
          DBG("PTP found.\n");
304
          break;
305
        default:
306
          log("Unknown link type in router lsa. (rid = %R)", act->lsa.id);
307
          break;
308
        }
309
      if (tmp)
310
        DBG("Going to add cand, Mydist: %u, Req: %u\n",
311
            tmp->dist, act->dist + rtl->metric);
312
      add_cand(&oa->cand, tmp, act, act->dist + rtl->metric, oa);
313
    }
314
}
315

    
316
/* 16.1 calculating shortest paths for an area */
317
static void
318
ospf_rt_spfa(struct ospf_area *oa)
319
{
320
  struct proto *p = &oa->po->proto;
321
  struct proto_ospf *po = oa->po;
322
  struct ospf_lsa_rt *rt;
323
  struct ospf_lsa_net *ln;
324
  struct ospf_iface *iface;
325
  struct top_hash_entry *act, *tmp;
326
  u32 i, *rts;
327
  orta nf;
328
  node *n;
329

    
330
  if (oa->rt == NULL)
331
    return;
332

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

    
335
  if (oa->rt->dist != LSINFINITY)
336
    bug("Aging was not processed.");
337

    
338
  /* 16.1. (1) */
339
  init_list(&oa->cand);                /* Empty list of candidates */
340
  oa->trcap = 0;
341

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

    
344
  oa->rt->dist = 0;
345
  oa->rt->color = CANDIDATE;
346
  add_head(&oa->cand, &oa->rt->cn);
347
  DBG("RT LSA: rt: %R, id: %R, type: %u\n",
348
      oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa.type);
349

    
350
  while (!EMPTY_LIST(oa->cand))
351
  {
352
    n = HEAD(oa->cand);
353
    act = SKIP_BACK(struct top_hash_entry, cn, n);
354
    rem_node(n);
355

    
356
    DBG("Working on LSA: rt: %R, id: %R, type: %u\n",
357
        act->lsa.rt, act->lsa.id, act->lsa.type);
358

    
359
    act->color = INSPF;
360
    switch (act->lsa.type)
361
    {
362
    case LSA_T_RT:
363
      rt = (struct ospf_lsa_rt *) act->lsa_body;
364
      if (rt->options & OPT_RT_V)
365
        oa->trcap = 1;
366

    
367
      /* In OSPFv2, just ASBRs and ABRs are needed to add to oa->rtr table */
368
      // ((rt->options & OPT_RT_V) || (rt->options & OPT_RT_E))
369

    
370
      nf.type = RTS_OSPF;
371
      nf.options = rt->options;
372
      nf.metric1 = act->dist;
373
      nf.metric2 = LSINFINITY;
374
      nf.tag = 0;
375
      nf.oa = oa;
376
      nf.ar = act;
377
      nf.nh = act->nh;
378
      nf.ifa = act->nhi;
379
      nf.rid = act->lsa.rt;
380
      ri_install(po, ipa_from_rid(act->lsa.rt), MAX_PREFIX_LENGTH, ORT_ROUTER, &nf, NULL);
381

    
382
#ifdef OSPFv2
383
      ospf_rt_spfa_rtlinks(oa, act, act);
384
#else /* OSPFv3 */
385
      for (tmp = ospf_hash_find_rt_first(po->gr, act->domain, act->lsa.rt);
386
           tmp; tmp = ospf_hash_find_rt_next(tmp))
387
        ospf_rt_spfa_rtlinks(oa, act, tmp);
388
#endif
389

    
390
      break;
391
    case LSA_T_NET:
392
      ln = act->lsa_body;
393

    
394
#ifdef OSPFv2
395
      add_network(oa, ipa_and(ipa_from_u32(act->lsa.id), ln->netmask),
396
                  ipa_mklen(ln->netmask), act->dist, act);
397
#endif
398

    
399
      rts = (u32 *) (ln + 1);
400
      for (i = 0; i < lsa_net_count(&act->lsa); i++)
401
      {
402
        DBG("     Working on router %R ", rts[i]);
403
        tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]);
404
        if (tmp != NULL)
405
          DBG("Found :-)\n");
406
        else
407
          DBG("Not found!\n");
408
        add_cand(&oa->cand, tmp, act, act->dist, oa);
409
      }
410
      break;
411
    }
412
  }
413

    
414
#ifdef OSPFv3
415
  process_prefixes(oa);
416
#endif
417

    
418
  /* Find new/lost VLINK peers */
419
  WALK_LIST(iface, po->iface_list)
420
  {
421
    if ((iface->type == OSPF_IT_VLINK) && (iface->voa == oa))
422
    {
423
      if ((tmp = ospf_hash_find_rt(po->gr, oa->areaid, iface->vid)) &&
424
          (!ipa_equal(tmp->lb, IPA_NONE)))
425
      {
426
        if ((iface->state != OSPF_IS_PTP) || (iface->iface != tmp->nhi->iface) || (!ipa_equal(iface->vip, tmp->lb)))
427
        {
428
          OSPF_TRACE(D_EVENTS, "Vlink peer %R found", tmp->lsa.id);
429
          ospf_iface_sm(iface, ISM_DOWN);
430
          iface->iface = tmp->nhi->iface;
431
          iface->vip = tmp->lb;
432
          ospf_iface_sm(iface, ISM_UP);
433
        }
434
      }
435
      else
436
      {
437
        if (iface->state > OSPF_IS_DOWN)
438
        {
439
          OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", iface->vid);
440
          ospf_iface_sm(iface, ISM_DOWN);
441
        }
442
      }
443
    }
444
  }
445
}
446

    
447
static int
448
link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par)
449
{
450
  u32 i, *rts;
451
  struct ospf_lsa_net *ln;
452
  struct ospf_lsa_rt *rt;
453
  struct ospf_lsa_rt_link *rtl, *rr;
454
  struct top_hash_entry *tmp;
455
  struct proto_ospf *po = oa->po;
456

    
457
  if (!en || !par) return 0;
458

    
459
  // FIXME lb should be properly set for vlinks */
460
  en->lb = IPA_NONE;
461
  switch (en->lsa.type)
462
  {
463
    case LSA_T_RT:
464
      rt = (struct ospf_lsa_rt *) en->lsa_body;
465
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
466
      for (i = 0; i < lsa_rt_count(&en->lsa); i++)
467
      {
468
        rtl = (rr + i);
469
        switch (rtl->type)
470
        {
471
        case LSART_STUB:
472
          break;
473
        case LSART_NET:
474
#ifdef OSPFv2
475
          /* In OSPFv2, rtl->id is IP addres of DR, Router ID is not known */
476
          tmp = ospf_hash_find_net(po->gr, oa->areaid, rtl->id);
477
#else /* OSPFv3 */
478
          tmp = ospf_hash_find(po->gr, oa->areaid, rtl->nif, rtl->id, LSA_T_NET);
479
#endif
480
          if (tmp == par)
481
          {
482
#ifdef OSPFv2
483
            en->lb = ipa_from_u32(rtl->data);
484
#endif
485
            return 1;
486
          }
487

    
488
          break;
489
        case LSART_VLNK:
490
        case LSART_PTP:
491
          tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id);
492
          if (tmp == par)
493
            return 1;
494

    
495
          break;
496
        default:
497
          log(L_WARN "Unknown link type in router lsa. (rid = %R)", en->lsa.rt);
498
          break;
499
        }
500
      }
501
      break;
502
    case LSA_T_NET:
503
      ln = en->lsa_body;
504
      rts = (u32 *) (ln + 1);
505
      for (i = 0; i < lsa_net_count(&en->lsa); i++)
506
      {
507
        tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]);
508
        if (tmp == par)
509
          return 1;
510
      }
511
      break;
512
    default:
513
      bug("Unknown lsa type %x.", en->lsa.type);
514
  }
515
  return 0;
516
}
517

    
518
/* 16.3 examining summary-LSAs in transit areas */
519
static void
520
ospf_rt_sum_tr(struct ospf_area *oa)
521
{
522
  // struct proto *p = &oa->po->proto;
523
  struct proto_ospf *po = oa->po;
524
  struct ospf_area *bb = po->backbone;
525
  ip_addr ip, abrip;
526
  struct top_hash_entry *en;
527
  u32 dst_rid, metric, options;
528
  int pxlen = -1, type = -1;
529
  ort *re = NULL, *abr;
530
  orta nf;
531

    
532
  if (!bb) return;
533

    
534
  WALK_SLIST(en, po->lsal)
535
  {
536
    if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
537
      continue;
538

    
539
    if (en->domain != oa->areaid)
540
      continue;
541

    
542
    /* 16.3 (1a) */
543
    if (en->lsa.age == LSA_MAXAGE)
544
      continue;
545

    
546
    // if (en->dist == LSINFINITY)
547
    //   continue;
548

    
549
    /* 16.3 (2) */
550
    if (en->lsa.rt == po->router_id)
551
      continue;
552

    
553
    if (en->lsa.type == LSA_T_SUM_NET)
554
    {
555
#ifdef OSPFv2
556
      struct ospf_lsa_sum *ls = en->lsa_body;
557
      pxlen = ipa_mklen(ls->netmask);
558
      ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask);
559
#else /* OSPFv3 */
560
      u8 pxopts;
561
      u16 rest;
562
      struct ospf_lsa_sum_net *ls = en->lsa_body;
563
      lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest);
564

    
565
      if (pxopts & OPT_PX_NU)
566
        continue;
567
#endif
568

    
569
      metric = ls->metric & METRIC_MASK;
570
      options = 0;
571
      type = ORT_NET;
572
      re = (ort *) fib_find(&po->rtf, &ip, pxlen);
573
    }
574
    else if (en->lsa.type == LSA_T_SUM_RT)
575
    {
576
#ifdef OSPFv2
577
      struct ospf_lsa_sum *ls = en->lsa_body;
578
      dst_rid = en->lsa.id;
579
      options = 0;
580
#else /* OSPFv3 */
581
      struct ospf_lsa_sum_rt *ls = en->lsa_body;
582
      dst_rid = ls->drid; 
583
      options = ls->options & OPTIONS_MASK;
584
#endif
585

    
586
      ip = ipa_from_rid(dst_rid);
587
      pxlen = MAX_PREFIX_LENGTH;
588
      metric = ls->metric & METRIC_MASK;
589
      options |= ORTA_ASBR;
590
      type = ORT_ROUTER;
591
      re = (ort *) fib_find(&bb->rtr, &ip, pxlen);
592
    }
593

    
594
    /* 16.3 (1b) */ 
595
    if (metric == LSINFINITY) 
596
      continue; 
597

    
598
    /* 16.3 (3) */
599
    if (!re) continue;
600
    if (re->n.oa->areaid != 0) continue;
601
    if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA)) continue;
602

    
603
    /* 16.3. (4) */
604
    abrip = ipa_from_rid(en->lsa.rt);
605
    abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
606
    if (!abr) continue;
607

    
608
    nf.type = re->n.type;
609
    nf.options = options;
610
    nf.metric1 = abr->n.metric1 + metric;
611
    nf.metric2 = LSINFINITY;
612
    nf.tag = 0;
613
    nf.oa = oa;
614
    nf.ar = abr->n.ar;
615
    nf.nh = abr->n.nh;
616
    nf.ifa = abr->n.ifa;
617
    nf.rid = en->lsa.rt; /* ABR ID */
618
    ri_install(po, ip, pxlen, type, &nf, NULL);
619
  }
620
}
621
  
622
/* 16.2 calculating inter-area routes */
623
static void
624
ospf_rt_sum(struct ospf_area *oa)
625
{
626
  struct proto_ospf *po = oa->po;
627
  struct proto *p = &po->proto;
628
  struct top_hash_entry *en;
629
  ip_addr ip, abrip;        /* abrIP is actually ID */
630
  u32 dst_rid, metric, options;
631
  struct area_net *anet;
632
  orta nf;
633
  ort *abr;
634
  int pxlen = -1, type = -1;
635

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

    
638
  WALK_SLIST(en, po->lsal)
639
  {
640
    if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
641
      continue;
642

    
643
    if (en->domain != oa->areaid)
644
      continue;
645

    
646
    /* Page 169 (1) */
647
    if (en->lsa.age == LSA_MAXAGE)
648
      continue;
649

    
650
    /* Page 169 (2) */
651
    if (en->lsa.rt == po->router_id)
652
      continue;
653

    
654

    
655
    if (en->lsa.type == LSA_T_SUM_NET)
656
    {
657
      struct ospf_area *oaa;
658
      int skip = 0;
659

    
660
#ifdef OSPFv2
661
      struct ospf_lsa_sum *ls = en->lsa_body;
662
      pxlen = ipa_mklen(ls->netmask);
663
      ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask);
664
#else /* OSPFv3 */
665
      u8 pxopts;
666
      u16 rest;
667
      struct ospf_lsa_sum_net *ls = en->lsa_body;
668
      lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest);
669

    
670
      if (pxopts & OPT_PX_NU)
671
        continue;
672
#endif
673

    
674
      metric = ls->metric & METRIC_MASK;
675
      options = 0;
676
      type = ORT_NET;
677

    
678
      /* Page 169 (3) */
679
      WALK_LIST(oaa, po->area_list)
680
      {
681
        if ((anet = fib_find(&oaa->net_fib, &ip, pxlen)) && anet->active)
682
        {
683
          skip = 1;
684
          break;
685
        }
686
      }
687
      if (skip) continue;
688
    }
689
    else
690
    {
691
#ifdef OSPFv2
692
      struct ospf_lsa_sum *ls = en->lsa_body;
693
      dst_rid = en->lsa.id;
694
      options = 0;
695
#else /* OSPFv3 */
696
      struct ospf_lsa_sum_rt *ls = en->lsa_body;
697
      dst_rid = ls->drid; 
698
      options = ls->options & OPTIONS_MASK;
699
#endif
700

    
701
      ip = ipa_from_rid(dst_rid);
702
      pxlen = MAX_PREFIX_LENGTH;
703
      metric = ls->metric & METRIC_MASK;
704
      options |= ORTA_ASBR;
705
      type = ORT_ROUTER;
706
    }
707

    
708
    /* Page 169 (1) */
709
    if (metric == LSINFINITY)
710
      continue;
711

    
712
    /* Page 169 (4) */
713
    abrip = ipa_from_rid(en->lsa.rt);
714
    if (!(abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH))) continue;
715
    if (abr->n.metric1 == LSINFINITY) continue;
716
    if (!(abr->n.options & ORTA_ABR)) continue;
717

    
718
    nf.type = RTS_OSPF_IA;
719
    nf.options = options;
720
    nf.metric1 = abr->n.metric1 + metric;
721
    nf.metric2 = LSINFINITY;
722
    nf.tag = 0;
723
    nf.oa = oa;
724
    nf.ar = abr->n.ar;
725
    nf.nh = abr->n.nh;
726
    nf.ifa = abr->n.ifa;
727
    nf.rid = en->lsa.rt; /* ABR ID */
728
    ri_install(po, ip, pxlen, type, &nf, NULL);
729
  }
730
}
731

    
732
/**
733
 * ospf_rt_spf - calculate internal routes
734
 * @po: OSPF protocol
735
 *
736
 * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
737
 * It's based on Dijkstra's shortest path tree algorithms.
738
 * This function is invoked from ospf_disp().
739
 */
740
void
741
ospf_rt_spf(struct proto_ospf *po)
742
{
743
  struct proto *p = &po->proto;
744
  struct ospf_area *oa;
745
  ort *ri;
746
  struct area_net *anet;
747

    
748
  if (po->areano == 0) return;
749

    
750
  po->cleanup = 1;
751

    
752
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
753

    
754
  /* 16. (1) - Invalidate old routing table */
755
  FIB_WALK(&po->rtf, nftmp)
756
  {
757
    ri = (ort *) nftmp;
758
    memcpy(&ri->o, &ri->n, sizeof(orta));        /* Backup old data */
759
    fill_ri(&ri->n);
760
  }
761
  FIB_WALK_END;
762

    
763

    
764
  WALK_LIST(oa, po->area_list)
765
  {
766
    FIB_WALK(&oa->rtr, nftmp)
767
    {
768
      ri = (ort *) nftmp;
769
      memcpy(&ri->o, &ri->n, sizeof(orta));        /* Backup old data */
770
      fill_ri(&ri->n);
771
    }
772
    FIB_WALK_END;
773

    
774
    FIB_WALK(&oa->net_fib, nftmp)
775
    {
776
      anet = (struct area_net *) nftmp;
777
      anet->active = 0;
778
      anet->metric = 1;
779
    }
780
    FIB_WALK_END;
781

    
782
    /* 16. (2) */
783
    ospf_rt_spfa(oa);
784
  }
785

    
786
  /* 16. (3) */
787
  if ((po->areano == 1) || (!po->backbone))
788
  {
789
    ospf_rt_sum(HEAD(po->area_list));
790
  }
791
  else
792
  {
793
    ospf_rt_sum(po->backbone);
794
  }
795

    
796
  /* 16. (4) */
797
  WALK_LIST(oa, po->area_list)
798
  {
799
    if (oa->trcap && (oa->areaid != 0))
800
    {
801
      ospf_rt_sum_tr(oa);
802
      break;
803
    }
804
  }
805

    
806
  /* 16. (5) */
807
  ospf_ext_spf(po);
808

    
809
  rt_sync(po);
810

    
811
  po->calcrt = 0;
812
}
813

    
814
/**
815
 * ospf_ext_spf - calculate external paths
816
 * @po: protocol
817
 *
818
 * After routing table for any area is calculated, calculation of external
819
 * path is invoked. This process is described in 16.4 of RFC 2328.
820
 * Inter- and Intra-area paths are always prefered over externals.
821
 */
822
static void
823
ospf_ext_spf(struct proto_ospf *po)
824
{
825
  ort *nf1, *nf2, *nfh;
826
  orta nfa;
827
  struct top_hash_entry *en;
828
  struct proto *p = &po->proto;
829
  struct ospf_lsa_ext *le;
830
  int pxlen, ebit, rt_fwaddr_valid;
831
  ip_addr ip, nh, rtid, rt_fwaddr;
832
  struct ospf_iface *nhi = NULL;
833
  u32 br_metric, rt_metric, rt_tag;
834
  neighbor *nn;
835
  struct ospf_area *atmp;
836

    
837
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
838

    
839
  WALK_SLIST(en, po->lsal)
840
  {
841
    /* 16.4. (1) */
842
    if (en->lsa.type != LSA_T_EXT)
843
      continue;
844
    if (en->lsa.age == LSA_MAXAGE)
845
      continue;
846

    
847
    /* 16.4. (2) */
848
    if (en->lsa.rt == po->router_id)
849
      continue;
850

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

    
854
    le = en->lsa_body;
855

    
856
    rt_metric = le->metric & METRIC_MASK;
857
    ebit = le->metric & LSA_EXT_EBIT;
858

    
859
    if (rt_metric == LSINFINITY)
860
      continue;
861

    
862
#ifdef OSPFv2
863
    ip = ipa_and(ipa_from_u32(en->lsa.id), le->netmask);
864
    pxlen = ipa_mklen(le->netmask);
865
    rt_fwaddr = le->fwaddr;
866
    rt_fwaddr_valid = !ipa_equal(rt_fwaddr, IPA_NONE);
867
    rt_tag = le->tag;
868
#else /* OSPFv3 */
869
    u8 pxopts;
870
    u16 rest;
871
    u32 *buf = le->rest;
872
    buf = lsa_get_ipv6_prefix(buf, &ip, &pxlen, &pxopts, &rest);
873

    
874
    if (pxopts & OPT_PX_NU)
875
      continue;
876

    
877
    rt_fwaddr_valid = le->metric & LSA_EXT_FBIT;
878
    if (rt_fwaddr_valid)
879
      buf = lsa_get_ipv6_addr(buf, &rt_fwaddr);
880
    else 
881
      rt_fwaddr = IPA_NONE;
882

    
883
    if (le->metric & LSA_EXT_TBIT)
884
      rt_tag = *buf++;
885
    else
886
      rt_tag = 0;
887
#endif
888

    
889
    if (pxlen < 0)
890
    {
891
      log(L_WARN "%s: Invalid mask in LSA (Type: %04x, Id: %R, Rt: %R)",
892
          p->name, en->lsa.type, en->lsa.id, en->lsa.rt);
893
      continue;
894
    }
895
    nhi = NULL;
896
    nh = IPA_NONE;
897

    
898
    /* 16.4. (3) */
899
    rtid = ipa_from_rid(en->lsa.rt);
900
    nf1 = NULL;
901
    WALK_LIST(atmp, po->area_list)
902
    {
903
      nfh = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH);
904
      if (nfh == NULL) continue;
905
      if (nf1 == NULL) nf1 = nfh;
906
      else if (ri_better(po, &nfh->n, NULL, &nf1->n, NULL, po->rfc1583)) nf1 = nfh;
907
    }
908

    
909
    if (!nf1)
910
      continue;                        /* No AS boundary router found */
911

    
912
    if (nf1->n.metric1 == LSINFINITY)
913
      continue;                        /* distance is INF */
914

    
915
    if (!(nf1->n.options & ORTA_ASBR))
916
      continue;                        /* It is not ASBR */
917

    
918
    if (!rt_fwaddr_valid)
919
    {
920
      nh = nf1->n.nh;
921
      nhi = nf1->n.ifa;
922
      nfh = nf1;
923
      br_metric = nf1->n.metric1;
924
    }
925
    else
926
    {
927
      nf2 = fib_route(&po->rtf, rt_fwaddr, MAX_PREFIX_LENGTH);
928

    
929
      if (!nf2)
930
      {
931
        DBG("Cannot find network route (GW=%I)\n", rt_fwaddr);
932
        continue;
933
      }
934

    
935
      if ((nn = neigh_find(p, &rt_fwaddr, 0)) != NULL)
936
      {
937
        nh = rt_fwaddr;
938
        nhi = ospf_iface_find(po, nn->iface);
939
      }
940
      else
941
      {
942
        nh = nf2->n.nh;
943
        nhi = nf2->n.ifa;
944
      }
945

    
946
      br_metric = nf2->n.metric1;
947
      if (br_metric == LSINFINITY)
948
        continue;                        /* distance is INF */
949
    }
950

    
951
    if (ebit)
952
    {
953
      nfa.type = RTS_OSPF_EXT2;
954
      nfa.metric1 = br_metric;
955
      nfa.metric2 = rt_metric;
956
    }
957
    else
958
    {
959
      nfa.type = RTS_OSPF_EXT1;
960
      nfa.metric1 = br_metric + rt_metric;
961
      nfa.metric2 = LSINFINITY;
962
    }
963

    
964
    nfa.options = 0;
965
    nfa.tag = rt_tag;
966
    nfa.oa = (po->backbone == NULL) ? HEAD(po->area_list) : po->backbone;
967
    nfa.ar = nf1->n.ar;
968
    nfa.nh = nh;
969
    nfa.ifa = nhi;
970
    nfa.rid = en->lsa.rt;
971
    ri_install(po, ip, pxlen, ORT_NET, &nfa, nfh);
972
  }
973

    
974
}
975

    
976
/* Add LSA into list of candidates in Dijkstra's algorithm */
977
static void
978
add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
979
         u32 dist, struct ospf_area *oa)
980
{
981
  node *prev, *n;
982
  int added = 0;
983
  struct top_hash_entry *act;
984

    
985
  /* 16.1. (2b) */
986
  if (en == NULL)
987
    return;
988
  if (en->lsa.age == LSA_MAXAGE)
989
    return;
990

    
991
#ifdef OSPFv3
992
  if (en->lsa.type == LSA_T_RT)
993
    {
994
      struct ospf_lsa_rt *rt = en->lsa_body;
995
      if (!(rt->options & OPT_V6) || !(rt->options & OPT_R))
996
        return;
997
    }
998
#endif
999

    
1000
  /* 16.1. (2c) */
1001
  if (en->color == INSPF)
1002
    return;
1003

    
1004
  /* 16.1. (2d) */
1005
  if (dist >= en->dist)
1006
    return;
1007
  /*
1008
   * FIXME The line above (=) is not a bug, but we don't support multiple
1009
   * next hops. I'll start as soon as nest will
1010
   */
1011

    
1012
  /* We should check whether there is a reverse link from en to par, */
1013
  if (!link_back(oa, en, par))
1014
    return;
1015

    
1016
  if (!calc_next_hop(oa, en, par))
1017
  {
1018
    log(L_WARN "Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
1019
        en->lsa.type, en->lsa.id, en->lsa.rt);
1020
    return;
1021
  }
1022

    
1023
  DBG("     Adding candidate: rt: %R, id: %R, type: %u\n",
1024
      en->lsa.rt, en->lsa.id, en->lsa.type);
1025

    
1026
  if (en->color == CANDIDATE)
1027
  {                                /* We found a shorter path */
1028
    rem_node(&en->cn);
1029
  }
1030
  en->dist = dist;
1031
  en->color = CANDIDATE;
1032

    
1033
  prev = NULL;
1034

    
1035
  if (EMPTY_LIST(*l))
1036
  {
1037
    add_head(l, &en->cn);
1038
  }
1039
  else
1040
  {
1041
    WALK_LIST(n, *l)
1042
    {
1043
      act = SKIP_BACK(struct top_hash_entry, cn, n);
1044
      if ((act->dist > dist) ||
1045
          ((act->dist == dist) && (act->lsa.type == LSA_T_NET)))
1046
      /* FIXME - shouldn't be here LSA_T_RT ??? */
1047
      {
1048
        if (prev == NULL)
1049
          add_head(l, &en->cn);
1050
        else
1051
          insert_node(&en->cn, prev);
1052
        added = 1;
1053
        break;
1054
      }
1055
      prev = n;
1056
    }
1057

    
1058
    if (!added)
1059
    {
1060
      add_tail(l, &en->cn);
1061
    }
1062
  }
1063
}
1064

    
1065

    
1066
static inline int
1067
match_dr(struct ospf_iface *ifa, struct top_hash_entry *en)
1068
{
1069
#ifdef OSPFv2
1070
  return (ifa->drid == en->lsa.rt) && (ipa_to_u32(ifa->drip) == en->lsa.id);
1071
#else /* OSPFv3 */
1072
  return (ifa->drid == en->lsa.rt) && (ifa->dr_iface_id == en->lsa.id);
1073
#endif
1074
}
1075

    
1076
static int
1077
calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
1078
              struct top_hash_entry *par)
1079
{
1080
  // struct proto *p = &oa->po->proto;
1081
  struct ospf_neighbor *neigh;
1082
  struct proto_ospf *po = oa->po;
1083
  struct ospf_iface *ifa;
1084

    
1085
  /* 16.1.1. The next hop calculation */
1086
  DBG("     Next hop called.\n");
1087
  if (ipa_equal(par->nh, IPA_NONE))
1088
  {
1089
    DBG("     Next hop calculating for id: %R rt: %R type: %u\n",
1090
        en->lsa.id, en->lsa.rt, en->lsa.type);
1091

    
1092
    /* 
1093
     * There are three cases:
1094
     * 1) en is a local network (and par is root)
1095
     * 2) en is a ptp or ptmp neighbor (and par is root)
1096
     * 3) en is a bcast or nbma neighbor (and par is local network)
1097
     */
1098

    
1099
    /* The first case - local network */
1100
    if ((en->lsa.type == LSA_T_NET) && (par == oa->rt))
1101
    {
1102
      WALK_LIST(ifa, po->iface_list)
1103
        if (match_dr(ifa, en))
1104
          {
1105
            en->nh = IPA_NONE;
1106
            en->nhi = ifa;
1107
            return 1;
1108
          }
1109
      return 0;
1110
    }
1111

    
1112
    /* 
1113
     * Remaining cases - local neighbours.
1114
     * There are two problems with this code:
1115
     * 1) we use IP address from HELLO packet
1116
     *    and not the one from LSA (router or link).
1117
     *    This may break NBMA networks
1118
     * 2) we use find_neigh_noifa() and does not
1119
     *    take into account associated iface.
1120
     *    This breaks neighbors connected by more links.
1121
     */
1122

    
1123
    if ((en->lsa.type == LSA_T_RT) && 
1124
        ((par == oa->rt) || (par->lsa.type == LSA_T_NET)))
1125
    {
1126
      if ((neigh = find_neigh_noifa(po, en->lsa.rt)) != NULL)
1127
        {
1128
          en->nh = neigh->ip;
1129
          en->nhi = neigh->ifa;
1130
          return 1;
1131
        }
1132
      return 0;
1133
    }
1134

    
1135
    /* Probably bug or some race condition, we log it */
1136
    log(L_ERR "Unexpected case in next hop calculation");
1137

    
1138
    return 0;
1139
  }
1140

    
1141
  en->nh = par->nh;
1142
  en->nhi = par->nhi;
1143
  return 1;
1144
}
1145

    
1146
static void
1147
rt_sync(struct proto_ospf *po)
1148
{
1149
  struct proto *p = &po->proto;
1150
  struct fib_iterator fit;
1151
  struct fib *fib = &po->rtf;
1152
  ort *nf;
1153
  struct ospf_area *oa, *oaa;
1154
  struct area_net *anet;
1155
  int flush;
1156

    
1157
  /* This is used for forced reload of routes */
1158
  int reload = (po->calcrt == 2);
1159

    
1160
  OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation");
1161

    
1162
  DBG("Now syncing my rt table with nest's\n");
1163
  FIB_ITERATE_INIT(&fit, fib);
1164
again1:
1165
  FIB_ITERATE_START(fib, &fit, nftmp)
1166
  {
1167
    nf = (ort *) nftmp;
1168
    check_sum_lsa(po, nf, ORT_NET);
1169
    if (reload || memcmp(&nf->n, &nf->o, sizeof(orta)))
1170
    {                                /* Some difference */
1171
      net *ne;
1172
      rta a0;
1173
      rte *e;
1174

    
1175
      bzero(&a0, sizeof(a0));
1176

    
1177
      a0.proto = p;
1178
      a0.source = nf->n.type;
1179
      a0.scope = SCOPE_UNIVERSE;
1180
      a0.cast = RTC_UNICAST;
1181
      a0.dest = RTD_ROUTER;
1182
      a0.flags = 0;
1183
      a0.aflags = 0;
1184
      a0.iface = NULL;
1185
      if (nf->n.ifa) a0.iface = nf->n.ifa->iface;
1186
      a0.gw = nf->n.nh;
1187

    
1188
      if (ipa_nonzero(nf->n.nh) && (!neigh_find2(p, &nf->n.nh, nf->n.ifa->iface, 0)))
1189
      {
1190
        int found = 0;
1191
        struct ospf_iface *ifa;
1192
        struct top_hash_entry *en;
1193
        OSPF_TRACE(D_EVENTS, "Trying to find correct next hop %I/%d via %I", nf->fn.prefix, nf->fn.pxlen, nf->n.nh);
1194
        WALK_LIST(ifa, po->iface_list)
1195
        {
1196
          if ((ifa->type == OSPF_IT_VLINK) && ipa_equal(ifa->vip, nf->n.nh))
1197
          {
1198
            if ((en = ospf_hash_find_rt(po->gr, ifa->voa->areaid, ifa->vid))
1199
                && (!ipa_equal(en->nh, IPA_NONE)))
1200
            {
1201
              a0.gw = en->nh;
1202
              found = 1;
1203
            }
1204
            break;
1205
          }
1206
        }
1207
        if (!found) nf->n.metric1 = LSINFINITY; /* Delete it */
1208
      }
1209

    
1210
      if (ipa_equal(nf->n.nh, IPA_NONE)) a0.dest = RTD_DEVICE;
1211

    
1212
      if (!a0.iface)        /* Still no match? Can this really happen? */
1213
        nf->n.metric1 = LSINFINITY;
1214

    
1215
      ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
1216
      if (nf->n.metric1 < LSINFINITY)
1217
      {
1218
        e = rte_get_temp(&a0);
1219
        e->u.ospf.metric1 = nf->n.metric1;
1220
        e->u.ospf.metric2 = nf->n.metric2;
1221
        e->u.ospf.tag = nf->n.tag;
1222
        e->u.ospf.router_id = nf->n.rid;
1223
        e->pflags = 0;
1224
        e->net = ne;
1225
        e->pref = p->preference;
1226
        DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n",
1227
          a0.source, nf->fn.prefix, nf->fn.pxlen, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
1228
        rte_update(p->table, ne, p, p, e);
1229
      }
1230
      else
1231
      {
1232
        rte_update(p->table, ne, p, p, NULL);
1233
        FIB_ITERATE_PUT(&fit, nftmp);
1234
        fib_delete(fib, nftmp);
1235
        goto again1;
1236
      }
1237
    }
1238
  }
1239
  FIB_ITERATE_END(nftmp);
1240

    
1241
  WALK_LIST(oa, po->area_list)
1242
  {
1243
    FIB_ITERATE_INIT(&fit, &oa->rtr);
1244
again2:
1245
    FIB_ITERATE_START(&oa->rtr, &fit, nftmp)
1246
    {
1247
      nf = (ort *) nftmp;
1248
      if (memcmp(&nf->n, &nf->o, sizeof(orta)))
1249
      {                                /* Some difference */
1250
        check_sum_lsa(po, nf, ORT_ROUTER);
1251
        if (nf->n.metric1 >= LSINFINITY)
1252
        {
1253
          FIB_ITERATE_PUT(&fit, nftmp);
1254
          fib_delete(&oa->rtr, nftmp);
1255
          goto again2;
1256
        }
1257
      }
1258
    }
1259
    FIB_ITERATE_END(nftmp);
1260

    
1261
    /* Check condensed summary LSAs */
1262
    FIB_WALK(&oa->net_fib, nftmp)
1263
    {
1264
      flush = 1;
1265
      anet = (struct area_net *) nftmp;
1266
      if ((!anet->hidden) && anet->active)
1267
        flush = 0;
1268
          
1269
      WALK_LIST(oaa, po->area_list)
1270
      {
1271
        int fl = flush;
1272

    
1273
        if (oaa == oa) continue;
1274

    
1275
        if ((oa == po->backbone) && oaa->trcap) fl = 1;
1276

    
1277
        if (oaa->stub) fl = 1;
1278

    
1279
        if (fl) flush_sum_lsa(oaa, &anet->fn, ORT_NET);
1280
        else originate_sum_lsa(oaa, &anet->fn, ORT_NET, anet->metric, 0);
1281
      }
1282
    }
1283
    FIB_WALK_END;
1284

    
1285
    /* Check default summary LSA for stub areas
1286
     * just for router connected to backbone */
1287
    if (po->backbone)
1288
    {
1289
      struct fib_node fnn;
1290

    
1291
      fnn.prefix = IPA_NONE;
1292
      fnn.pxlen = 0;
1293
      if (oa->stub) originate_sum_lsa(oa, &fnn, ORT_NET, oa->stub, 0);
1294
      else flush_sum_lsa(oa, &fnn, ORT_NET);
1295
    }
1296
  }
1297
}