Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (29.4 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
}
42

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
186
    if (en->domain != oa->areaid)
187
      continue;
188

    
189
    if (en->lsa.age == LSA_MAXAGE)
190
      continue;
191

    
192
    px = en->lsa_body;
193

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

    
200
    if (!src)
201
      continue;
202

    
203
    if (src->lsa.age == LSA_MAXAGE)
204
      continue;
205

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

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

    
214
        if (pxopts & OPT_PX_NU)
215
          continue;
216

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

    
223

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

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

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

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

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

    
260
          if (act == oa->rt)
261
            {
262
              struct ospf_iface *iff;
263

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

    
276
          if (!nf.ifa)
277
            continue;
278

    
279
          ri_install(po, ipa_from_u32(rtl->id),
280
                     ipa_mklen(ipa_from_u32(rtl->data)), ORT_NET, &nf, NULL);
281
          break;
282
#endif
283

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

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

    
313
static void
314
ospf_rt_spfa(struct ospf_area *oa)
315
{
316
  struct proto *p = &oa->po->proto;
317
  struct proto_ospf *po = oa->po;
318
  struct ospf_lsa_rt *rt;
319
  struct ospf_lsa_net *ln;
320
  struct ospf_iface *iface;
321
  struct top_hash_entry *act, *tmp;
322
  u32 i, *rts;
323
  orta nf;
324
  node *n;
325

    
326
  if (oa->rt == NULL)
327
    return;
328

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

    
331
  if (oa->rt->dist != LSINFINITY)
332
    bug("Aging was not processed.");
333

    
334
  /* 16.1. (1) */
335
  init_list(&oa->cand);                /* Empty list of candidates */
336
  oa->trcap = 0;
337

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

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

    
346
  while (!EMPTY_LIST(oa->cand))
347
  {
348
    n = HEAD(oa->cand);
349
    act = SKIP_BACK(struct top_hash_entry, cn, n);
350
    rem_node(n);
351

    
352
    DBG("Working on LSA: rt: %R, id: %R, type: %u\n",
353
        act->lsa.rt, act->lsa.id, act->lsa.type);
354

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

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

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

    
377
#ifdef OSPFv2
378
      ospf_rt_spfa_rtlinks(oa, act, act);
379
#else /* OSPFv3 */
380
      for (tmp = ospf_hash_find_rt_first(po->gr, act->domain, act->lsa.rt);
381
           tmp; tmp = ospf_hash_find_rt_next(tmp))
382
        ospf_rt_spfa_rtlinks(oa, act, tmp);
383
#endif
384

    
385
      break;
386
    case LSA_T_NET:
387
      ln = act->lsa_body;
388

    
389
#ifdef OSPFv2
390
      add_network(oa, ipa_and(ipa_from_u32(act->lsa.id), ln->netmask),
391
                  ipa_mklen(ln->netmask), act->dist, act);
392
#endif
393

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

    
409
#ifdef OSPFv3
410
  process_prefixes(oa);
411
#endif
412

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

    
442
static int
443
link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par)
444
{
445
  u32 i, *rts;
446
  struct ospf_lsa_net *ln;
447
  struct ospf_lsa_rt *rt;
448
  struct ospf_lsa_rt_link *rtl, *rr;
449
  struct top_hash_entry *tmp;
450
  struct proto_ospf *po = oa->po;
451

    
452
  if (!en || !par) return 0;
453

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

    
483
          break;
484
        case LSART_VLNK:
485
        case LSART_PTP:
486
          tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id);
487
          if (tmp == par)
488
            return 1;
489

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

    
513
static void
514
ospf_rt_sum_tr(struct ospf_area *oa)
515
{
516
  struct proto *p = &oa->po->proto;
517
  struct proto_ospf *po = oa->po;
518
  struct ospf_area *bb = po->backbone;
519
  ip_addr ip, abrip;
520
  struct top_hash_entry *en;
521
  u32 dst_rid, metric, options;
522
  int pxlen = -1, type = -1;
523
  ort *re = NULL, *abr;
524
  orta nf;
525

    
526
  if (!bb) return;
527

    
528
  WALK_SLIST(en, po->lsal)
529
  {
530
    if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
531
      continue;
532

    
533
    if (en->domain != oa->areaid)
534
      continue;
535

    
536
    if (en->lsa.age == LSA_MAXAGE)
537
      continue;
538

    
539
    if (en->dist == LSINFINITY)
540
      continue;
541

    
542
    if (en->lsa.rt == po->router_id)
543
      continue;
544

    
545
    if (en->lsa.type == LSA_T_SUM_NET)
546
    {
547
#ifdef OSPFv2
548
      struct ospf_lsa_sum *ls = en->lsa_body;
549
      pxlen = ipa_mklen(ls->netmask);
550
      ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask);
551
#else /* OSPFv3 */
552
      u8 pxopts;
553
      u16 rest;
554
      struct ospf_lsa_sum_net *ls = en->lsa_body;
555
      lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest);
556

    
557
      if (pxopts & OPT_PX_NU)
558
        continue;
559
#endif
560

    
561
      metric = ls->metric & METRIC_MASK;
562
      options = 0;
563
      type = ORT_NET;
564
      re = (ort *) fib_find(&po->rtf, &ip, pxlen);
565
    }
566
    else if (en->lsa.type == LSA_T_SUM_RT)
567
    {
568
#ifdef OSPFv2
569
      struct ospf_lsa_sum *ls = en->lsa_body;
570
      dst_rid = en->lsa.id;
571
      options = 0;
572
#else /* OSPFv3 */
573
      struct ospf_lsa_sum_rt *ls = en->lsa_body;
574
      dst_rid = ls->drid; 
575
      options = ls->options & OPTIONS_MASK;
576
#endif
577

    
578
      ip = ipa_from_rid(dst_rid);
579
      pxlen = MAX_PREFIX_LENGTH;
580
      metric = ls->metric & METRIC_MASK;
581
      options |= ORTA_ASBR;
582
      type = ORT_ROUTER;
583
      re = (ort *) fib_find(&bb->rtr, &ip, pxlen);
584
    }
585

    
586
    if (!re) continue;
587
    if (re->n.oa->areaid != 0) continue;
588
    if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA)) continue;
589

    
590
    abrip = ipa_from_rid(en->lsa.rt);
591

    
592
    abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
593
    if (!abr) continue;
594

    
595
    nf.type = re->n.type;
596
    nf.options = options;
597
    nf.metric1 = abr->n.metric1 + metric;
598
    nf.metric2 = LSINFINITY;
599
    nf.tag = 0;
600
    nf.oa = oa;
601
    nf.ar = abr->n.ar;
602
    nf.nh = abr->n.nh;
603
    nf.ifa = abr->n.ifa;
604
    ri_install(po, ip, pxlen, type, &nf, NULL);
605
  }
606
}
607
  
608

    
609
static void
610
ospf_rt_sum(struct ospf_area *oa)
611
{
612
  struct proto_ospf *po = oa->po;
613
  struct proto *p = &po->proto;
614
  struct top_hash_entry *en;
615
  ip_addr ip, abrip;        /* abrIP is actually ID */
616
  u32 dst_rid, metric, options;
617
  struct area_net *anet;
618
  orta nf;
619
  ort *abr;
620
  int pxlen = -1, type = -1;
621

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

    
624
  WALK_SLIST(en, po->lsal)
625
  {
626
    if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
627
      continue;
628

    
629
    if (en->domain != oa->areaid)
630
      continue;
631

    
632
    /* Page 169 (1) */
633
    if (en->lsa.age == LSA_MAXAGE)
634
      continue;
635

    
636
    /* Page 169 (2) */
637
    if (en->lsa.rt == po->router_id)
638
      continue;
639

    
640

    
641
    if (en->lsa.type == LSA_T_SUM_NET)
642
    {
643
      struct ospf_area *oaa;
644
      int skip = 0;
645

    
646
#ifdef OSPFv2
647
      struct ospf_lsa_sum *ls = en->lsa_body;
648
      pxlen = ipa_mklen(ls->netmask);
649
      ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask);
650
#else /* OSPFv3 */
651
      u8 pxopts;
652
      u16 rest;
653
      struct ospf_lsa_sum_net *ls = en->lsa_body;
654
      lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest);
655

    
656
      if (pxopts & OPT_PX_NU)
657
        continue;
658
#endif
659

    
660
      metric = ls->metric & METRIC_MASK;
661
      options = 0;
662
      type = ORT_NET;
663

    
664
      /* Page 169 (3) */
665
      WALK_LIST(oaa, po->area_list)
666
      {
667
        if ((anet = fib_find(&oaa->net_fib, &ip, pxlen)) && anet->active)
668
        {
669
          skip = 1;
670
          break;
671
        }
672
      }
673
      if (skip) continue;
674
    }
675
    else
676
    {
677
#ifdef OSPFv2
678
      struct ospf_lsa_sum *ls = en->lsa_body;
679
      dst_rid = en->lsa.id;
680
      options = 0;
681
#else /* OSPFv3 */
682
      struct ospf_lsa_sum_rt *ls = en->lsa_body;
683
      dst_rid = ls->drid; 
684
      options = ls->options & OPTIONS_MASK;
685
#endif
686

    
687
      ip = ipa_from_rid(dst_rid);
688
      pxlen = MAX_PREFIX_LENGTH;
689
      metric = ls->metric & METRIC_MASK;
690
      options |= ORTA_ASBR;
691
      type = ORT_ROUTER;
692
    }
693

    
694
    /* Page 169 (1) */
695
    if (metric == LSINFINITY)
696
      continue;
697

    
698
    /* Page 169 (4) */
699
    abrip = ipa_from_rid(en->lsa.rt);
700
    if (!(abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH))) continue;
701
    if (abr->n.metric1 == LSINFINITY) continue;
702
    if (!(abr->n.options & ORTA_ABR)) continue;
703

    
704
    nf.type = RTS_OSPF_IA;
705
    nf.options = options;
706
    nf.metric1 = abr->n.metric1 + metric;
707
    nf.metric2 = LSINFINITY;
708
    nf.tag = 0;
709
    nf.oa = oa;
710
    nf.ar = abr->n.ar;
711
    nf.nh = abr->n.nh;
712
    nf.ifa = abr->n.ifa;
713
    ri_install(po, ip, pxlen, type, &nf, NULL);
714
  }
715
}
716

    
717
/**
718
 * ospf_rt_spf - calculate internal routes
719
 * @po: OSPF protocol
720
 *
721
 * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
722
 * It's based on Dijkstra's shortest path tree algorithms.
723
 * This function is invoked from ospf_disp().
724
 */
725
void
726
ospf_rt_spf(struct proto_ospf *po)
727
{
728
  struct proto *p = &po->proto;
729
  struct ospf_area *oa;
730
  ort *ri;
731
  struct area_net *anet;
732

    
733
  if (po->areano == 0) return;
734

    
735
  po->cleanup = 1;
736

    
737
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
738

    
739
  /* 16. (1) - Invalidate old routing table */
740
  FIB_WALK(&po->rtf, nftmp)
741
  {
742
    ri = (ort *) nftmp;
743
    memcpy(&ri->o, &ri->n, sizeof(orta));        /* Backup old data */
744
    fill_ri(&ri->n);
745
  }
746
  FIB_WALK_END;
747

    
748

    
749
  WALK_LIST(oa, po->area_list)
750
  {
751
    FIB_WALK(&oa->rtr, nftmp)
752
    {
753
      ri = (ort *) nftmp;
754
      memcpy(&ri->o, &ri->n, sizeof(orta));        /* Backup old data */
755
      fill_ri(&ri->n);
756
    }
757
    FIB_WALK_END;
758

    
759
    FIB_WALK(&oa->net_fib, nftmp)
760
    {
761
      anet = (struct area_net *) nftmp;
762
      anet->active = 0;
763
      anet->metric = 1;
764
    }
765
    FIB_WALK_END;
766

    
767
    /* 16. (2) */
768
    ospf_rt_spfa(oa);
769
  }
770

    
771
  /* 16. (3) */
772
  if ((po->areano == 1) || (!po->backbone))
773
  {
774
    ospf_rt_sum(HEAD(po->area_list));
775
  }
776
  else
777
  {
778
    ospf_rt_sum(po->backbone);
779
  }
780

    
781
  /* 16. (4) */
782
  WALK_LIST(oa, po->area_list)
783
  {
784
    if (oa->trcap && (oa->areaid != 0))
785
    {
786
      ospf_rt_sum_tr(oa);
787
      break;
788
    }
789
  }
790

    
791
  /* 16. (5) */
792
  ospf_ext_spf(po);
793

    
794
  rt_sync(po);
795

    
796
  po->calcrt = 0;
797
}
798

    
799
/**
800
 * ospf_ext_spf - calculate external paths
801
 * @po: protocol
802
 *
803
 * After routing table for any area is calculated, calculation of external
804
 * path is invoked. This process is described in 16.4 of RFC 2328.
805
 * Inter- and Intra-area paths are always prefered over externals.
806
 */
807
static void
808
ospf_ext_spf(struct proto_ospf *po)
809
{
810
  ort *nf1, *nf2, *nfh;
811
  orta nfa;
812
  struct top_hash_entry *en;
813
  struct proto *p = &po->proto;
814
  struct ospf_lsa_ext *le;
815
  int pxlen, ebit, rt_fwaddr_valid;
816
  ip_addr ip, nh, rtid, rt_fwaddr;
817
  struct ospf_iface *nhi = NULL;
818
  u32 br_metric, rt_metric, rt_tag;
819
  neighbor *nn;
820
  struct ospf_area *atmp;
821

    
822
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
823

    
824
  WALK_SLIST(en, po->lsal)
825
  {
826
    /* 16.4. (1) */
827
    if (en->lsa.type != LSA_T_EXT)
828
      continue;
829
    if (en->lsa.age == LSA_MAXAGE)
830
      continue;
831

    
832
    /* 16.4. (2) */
833
    if (en->lsa.rt == po->router_id)
834
      continue;
835

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

    
839
    le = en->lsa_body;
840

    
841
    rt_metric = le->metric & METRIC_MASK;
842
    ebit = le->metric & LSA_EXT_EBIT;
843

    
844
    if (rt_metric == LSINFINITY)
845
      continue;
846

    
847
#ifdef OSPFv2
848
    ip = ipa_and(ipa_from_u32(en->lsa.id), le->netmask);
849
    pxlen = ipa_mklen(le->netmask);
850
    rt_fwaddr = le->fwaddr;
851
    rt_fwaddr_valid = !ipa_equal(rt_fwaddr, IPA_NONE);
852
    rt_tag = le->tag;
853
#else /* OSPFv3 */
854
    u8 pxopts;
855
    u16 rest;
856
    u32 *buf = le->rest;
857
    buf = lsa_get_ipv6_prefix(buf, &ip, &pxlen, &pxopts, &rest);
858

    
859
    if (pxopts & OPT_PX_NU)
860
      continue;
861

    
862
    rt_fwaddr_valid = le->metric & LSA_EXT_FBIT;
863
    if (rt_fwaddr_valid)
864
      buf = lsa_get_ipv6_addr(buf, &rt_fwaddr);
865
    else 
866
      rt_fwaddr = IPA_NONE;
867

    
868
    if (le->metric & LSA_EXT_TBIT)
869
      rt_tag = *buf++;
870
    else
871
      rt_tag = 0;
872
#endif
873

    
874
    if (pxlen < 0)
875
    {
876
      log(L_WARN "%s: Invalid mask in LSA (Type: %04x, Id: %R, Rt: %R)",
877
          p->name, en->lsa.type, en->lsa.id, en->lsa.rt);
878
      continue;
879
    }
880
    nhi = NULL;
881
    nh = IPA_NONE;
882

    
883
    /* 16.4. (3) */
884
    rtid = ipa_from_rid(en->lsa.rt);
885
    nf1 = NULL;
886
    WALK_LIST(atmp, po->area_list)
887
    {
888
      nfh = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH);
889
      if (nfh == NULL) continue;
890
      if (nf1 == NULL) nf1 = nfh;
891
      else if (ri_better(po, &nfh->n, NULL, &nf1->n, NULL, po->rfc1583)) nf1 = nfh;
892
    }
893

    
894
    if (!nf1)
895
      continue;                        /* No AS boundary router found */
896

    
897
    if (nf1->n.metric1 == LSINFINITY)
898
      continue;                        /* distance is INF */
899

    
900
    if (!(nf1->n.options & ORTA_ASBR))
901
      continue;                        /* It is not ASBR */
902

    
903
    if (!rt_fwaddr_valid)
904
    {
905
      nh = nf1->n.nh;
906
      nhi = nf1->n.ifa;
907
      nfh = nf1;
908
      br_metric = nf1->n.metric1;
909
    }
910
    else
911
    {
912
      nf2 = fib_route(&po->rtf, rt_fwaddr, MAX_PREFIX_LENGTH);
913

    
914
      if (!nf2)
915
      {
916
        DBG("Cannot find network route (GW=%I)\n", rt_fwaddr);
917
        continue;
918
      }
919

    
920
      if ((nn = neigh_find(p, &rt_fwaddr, 0)) != NULL)
921
      {
922
        nh = rt_fwaddr;
923
        nhi = ospf_iface_find(po, nn->iface);
924
      }
925
      else
926
      {
927
        nh = nf2->n.nh;
928
        nhi = nf2->n.ifa;
929
      }
930

    
931
      br_metric = nf2->n.metric1;
932
      if (br_metric == LSINFINITY)
933
        continue;                        /* distance is INF */
934
    }
935

    
936
    if (ebit)
937
    {
938
      nfa.type = RTS_OSPF_EXT2;
939
      nfa.metric1 = br_metric;
940
      nfa.metric2 = rt_metric;
941
    }
942
    else
943
    {
944
      nfa.type = RTS_OSPF_EXT1;
945
      nfa.metric1 = br_metric + rt_metric;
946
      nfa.metric2 = LSINFINITY;
947
    }
948

    
949
    nfa.options = 0;
950
    nfa.tag = rt_tag;
951
    nfa.oa = (po->backbone == NULL) ? HEAD(po->area_list) : po->backbone;
952
    nfa.ar = nf1->n.ar;
953
    nfa.nh = nh;
954
    nfa.ifa = nhi;
955
    ri_install(po, ip, pxlen, ORT_NET, &nfa, nfh);
956
  }
957

    
958
}
959

    
960
/* Add LSA into list of candidates in Dijkstra's algorithm */
961
static void
962
add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
963
         u32 dist, struct ospf_area *oa)
964
{
965
  node *prev, *n;
966
  int added = 0;
967
  struct top_hash_entry *act;
968

    
969
  /* 16.1. (2b) */
970
  if (en == NULL)
971
    return;
972
  if (en->lsa.age == LSA_MAXAGE)
973
    return;
974

    
975
#ifdef OSPFv3
976
  if (en->lsa.type == LSA_T_RT)
977
    {
978
      struct ospf_lsa_rt *rt = en->lsa_body;
979
      if (!(rt->options & OPT_V6) || !(rt->options & OPT_R))
980
        return;
981
    }
982
#endif
983

    
984
  /* 16.1. (2c) */
985
  if (en->color == INSPF)
986
    return;
987

    
988
  /* 16.1. (2d) */
989
  if (dist >= en->dist)
990
    return;
991
  /*
992
   * FIXME The line above (=) is not a bug, but we don't support multiple
993
   * next hops. I'll start as soon as nest will
994
   */
995

    
996
  /* We should check whether there is a reverse link from en to par, */
997
  if (!link_back(oa, en, par))
998
    return;
999

    
1000
  if (!calc_next_hop(oa, en, par))
1001
  {
1002
    log(L_WARN "Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
1003
        en->lsa.type, en->lsa.id, en->lsa.rt);
1004
    return;
1005
  }
1006

    
1007
  DBG("     Adding candidate: rt: %R, id: %R, type: %u\n",
1008
      en->lsa.rt, en->lsa.id, en->lsa.type);
1009

    
1010
  if (en->color == CANDIDATE)
1011
  {                                /* We found a shorter path */
1012
    rem_node(&en->cn);
1013
  }
1014
  en->dist = dist;
1015
  en->color = CANDIDATE;
1016

    
1017
  prev = NULL;
1018

    
1019
  if (EMPTY_LIST(*l))
1020
  {
1021
    add_head(l, &en->cn);
1022
  }
1023
  else
1024
  {
1025
    WALK_LIST(n, *l)
1026
    {
1027
      act = SKIP_BACK(struct top_hash_entry, cn, n);
1028
      if ((act->dist > dist) ||
1029
          ((act->dist == dist) && (act->lsa.type == LSA_T_NET)))
1030
      /* FIXME - shouldn't be here LSA_T_RT ??? */
1031
      {
1032
        if (prev == NULL)
1033
          add_head(l, &en->cn);
1034
        else
1035
          insert_node(&en->cn, prev);
1036
        added = 1;
1037
        break;
1038
      }
1039
      prev = n;
1040
    }
1041

    
1042
    if (!added)
1043
    {
1044
      add_tail(l, &en->cn);
1045
    }
1046
  }
1047
}
1048

    
1049

    
1050
static inline int
1051
match_dr(struct ospf_iface *ifa, struct top_hash_entry *en)
1052
{
1053
#ifdef OSPFv2
1054
  return (ifa->drid == en->lsa.rt) && (ipa_to_u32(ifa->drip) == en->lsa.id);
1055
#else /* OSPFv3 */
1056
  return (ifa->drid == en->lsa.rt) && (ifa->dr_iface_id == en->lsa.id);
1057
#endif
1058
}
1059

    
1060
static int
1061
calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
1062
              struct top_hash_entry *par)
1063
{
1064
  struct ospf_neighbor *neigh;
1065
  struct proto *p = &oa->po->proto;
1066
  struct proto_ospf *po = oa->po;
1067
  struct ospf_iface *ifa;
1068

    
1069
  /* 16.1.1. The next hop calculation */
1070
  DBG("     Next hop called.\n");
1071
  if (ipa_equal(par->nh, IPA_NONE))
1072
  {
1073
    DBG("     Next hop calculating for id: %R rt: %R type: %u\n",
1074
        en->lsa.id, en->lsa.rt, en->lsa.type);
1075

    
1076
    /* 
1077
     * There are three cases:
1078
     * 1) en is a local network (and par is root)
1079
     * 2) en is a ptp or ptmp neighbor (and par is root)
1080
     * 3) en is a bcast or nbma neighbor (and par is local network)
1081
     */
1082

    
1083
    /* The first case - local network */
1084
    if ((en->lsa.type == LSA_T_NET) && (par == oa->rt))
1085
    {
1086
      WALK_LIST(ifa, po->iface_list)
1087
        if (match_dr(ifa, en))
1088
          {
1089
            en->nh = IPA_NONE;
1090
            en->nhi = ifa;
1091
            return 1;
1092
          }
1093
      return 0;
1094
    }
1095

    
1096
    /* 
1097
     * Remaining cases - local neighbours.
1098
     * There are two problems with this code:
1099
     * 1) we use IP address from HELLO packet
1100
     *    and not the one from LSA (router or link).
1101
     *    This may break NBMA networks
1102
     * 2) we use find_neigh_noifa() and does not
1103
     *    take into account associated iface.
1104
     *    This breaks neighbors connected by more links.
1105
     */
1106

    
1107
    if ((en->lsa.type == LSA_T_RT) && 
1108
        ((par == oa->rt) || (par->lsa.type == LSA_T_NET)))
1109
    {
1110
      if ((neigh = find_neigh_noifa(po, en->lsa.rt)) != NULL)
1111
        {
1112
          en->nh = neigh->ip;
1113
          en->nhi = neigh->ifa;
1114
          return 1;
1115
        }
1116
      return 0;
1117
    }
1118

    
1119
    /* Probably bug or some race condition, we log it */
1120
    log(L_ERR "Unexpected case in next hop calculation");
1121

    
1122
    return 0;
1123
  }
1124

    
1125
  en->nh = par->nh;
1126
  en->nhi = par->nhi;
1127
  return 1;
1128
}
1129

    
1130
static void
1131
rt_sync(struct proto_ospf *po)
1132
{
1133
  struct proto *p = &po->proto;
1134
  struct fib_iterator fit;
1135
  struct fib *fib = &po->rtf;
1136
  ort *nf;
1137
  struct ospf_area *oa, *oaa;
1138
  struct area_net *anet;
1139
  int flush;
1140

    
1141
  /* This is used for forced reload of routes */
1142
  int reload = (po->calcrt == 2);
1143

    
1144
  OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation");
1145

    
1146
  DBG("Now syncing my rt table with nest's\n");
1147
  FIB_ITERATE_INIT(&fit, fib);
1148
again1:
1149
  FIB_ITERATE_START(fib, &fit, nftmp)
1150
  {
1151
    nf = (ort *) nftmp;
1152
    check_sum_lsa(po, nf, ORT_NET);
1153
    if (reload || memcmp(&nf->n, &nf->o, sizeof(orta)))
1154
    {                                /* Some difference */
1155
      net *ne;
1156
      rta a0;
1157
      rte *e;
1158

    
1159
      bzero(&a0, sizeof(a0));
1160

    
1161
      a0.proto = p;
1162
      a0.source = nf->n.type;
1163
      a0.scope = SCOPE_UNIVERSE;
1164
      a0.cast = RTC_UNICAST;
1165
      a0.dest = RTD_ROUTER;
1166
      a0.flags = 0;
1167
      a0.aflags = 0;
1168
      a0.iface = NULL;
1169
      if (nf->n.ifa) a0.iface = nf->n.ifa->iface;
1170
      a0.gw = nf->n.nh;
1171

    
1172
      if (ipa_nonzero(nf->n.nh) && (!neigh_find2(p, &nf->n.nh, nf->n.ifa->iface, 0)))
1173
      {
1174
        int found = 0;
1175
        struct ospf_iface *ifa;
1176
        struct top_hash_entry *en;
1177
        OSPF_TRACE(D_EVENTS, "Trying to find correct next hop %I/%d via %I", nf->fn.prefix, nf->fn.pxlen, nf->n.nh);
1178
        WALK_LIST(ifa, po->iface_list)
1179
        {
1180
          if ((ifa->type == OSPF_IT_VLINK) && ipa_equal(ifa->vip, nf->n.nh))
1181
          {
1182
            if ((en = ospf_hash_find_rt(po->gr, ifa->voa->areaid, ifa->vid))
1183
                && (!ipa_equal(en->nh, IPA_NONE)))
1184
            {
1185
              a0.gw = en->nh;
1186
              found = 1;
1187
            }
1188
            break;
1189
          }
1190
        }
1191
        if (!found) nf->n.metric1 = LSINFINITY; /* Delete it */
1192
      }
1193

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

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

    
1199
      ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
1200
      if (nf->n.metric1 < LSINFINITY)
1201
      {
1202
        e = rte_get_temp(&a0);
1203
        e->u.ospf.metric1 = nf->n.metric1;
1204
        e->u.ospf.metric2 = nf->n.metric2;
1205
        e->u.ospf.tag = nf->n.tag;
1206
        e->pflags = 0;
1207
        e->net = ne;
1208
        e->pref = p->preference;
1209
        DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n",
1210
          a0.source, nf->fn.prefix, nf->fn.pxlen, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
1211
        rte_update(p->table, ne, p, p, e);
1212
      }
1213
      else
1214
      {
1215
        rte_update(p->table, ne, p, p, NULL);
1216
        FIB_ITERATE_PUT(&fit, nftmp);
1217
        fib_delete(fib, nftmp);
1218
        goto again1;
1219
      }
1220
    }
1221
  }
1222
  FIB_ITERATE_END(nftmp);
1223

    
1224
  WALK_LIST(oa, po->area_list)
1225
  {
1226
    FIB_ITERATE_INIT(&fit, &oa->rtr);
1227
again2:
1228
    FIB_ITERATE_START(&oa->rtr, &fit, nftmp)
1229
    {
1230
      nf = (ort *) nftmp;
1231
      if (memcmp(&nf->n, &nf->o, sizeof(orta)))
1232
      {                                /* Some difference */
1233
        check_sum_lsa(po, nf, ORT_ROUTER);
1234
        if (nf->n.metric1 >= LSINFINITY)
1235
        {
1236
          FIB_ITERATE_PUT(&fit, nftmp);
1237
          fib_delete(&oa->rtr, nftmp);
1238
          goto again2;
1239
        }
1240
      }
1241
    }
1242
    FIB_ITERATE_END(nftmp);
1243

    
1244
    /* Check condensed summary LSAs */
1245
    FIB_WALK(&oa->net_fib, nftmp)
1246
    {
1247
      flush = 1;
1248
      anet = (struct area_net *) nftmp;
1249
      if ((!anet->hidden) && anet->active)
1250
        flush = 0;
1251
          
1252
      WALK_LIST(oaa, po->area_list)
1253
      {
1254
        int fl = flush;
1255

    
1256
        if (oaa == oa) continue;
1257

    
1258
        if ((oa == po->backbone) && oaa->trcap) fl = 1;
1259

    
1260
        if (oaa->stub) fl = 1;
1261

    
1262
        if (fl) flush_sum_lsa(oaa, &anet->fn, ORT_NET);
1263
        else originate_sum_lsa(oaa, &anet->fn, ORT_NET, anet->metric, 0);
1264
      }
1265
    }
1266
    FIB_WALK_END;
1267

    
1268
    /* Check default summary LSA for stub areas
1269
     * just for router connected to backbone */
1270
    if (po->backbone)
1271
    {
1272
      struct fib_node fnn;
1273

    
1274
      fnn.prefix = IPA_NONE;
1275
      fnn.pxlen = 0;
1276
      if (oa->stub) originate_sum_lsa(oa, &fnn, ORT_NET, oa->stub, 0);
1277
      else flush_sum_lsa(oa, &fnn, ORT_NET);
1278
    }
1279
  }
1280
}