Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / rt.c @ 3034b384

History | View | Annotate | Download (29.3 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
            return 1;
477

    
478
          break;
479
        case LSART_VLNK:
480
        case LSART_PTP:
481
          tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id);
482
          if (tmp == par)
483
            return 1;
484

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

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

    
521
  if (!bb) return;
522

    
523
  WALK_SLIST(en, po->lsal)
524
  {
525
    if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
526
      continue;
527

    
528
    if (en->domain != oa->areaid)
529
      continue;
530

    
531
    if (en->lsa.age == LSA_MAXAGE)
532
      continue;
533

    
534
    if (en->dist == LSINFINITY)
535
      continue;
536

    
537
    if (en->lsa.rt == po->router_id)
538
      continue;
539

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

    
552
      if (pxopts & OPT_PX_NU)
553
        continue;
554
#endif
555

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

    
573
      ip = ipa_from_rid(dst_rid);
574
      pxlen = MAX_PREFIX_LENGTH;
575
      metric = ls->metric & METRIC_MASK;
576
      options |= ORTA_ASBR;
577
      type = ORT_ROUTER;
578
      re = (ort *) fib_find(&bb->rtr, &ip, pxlen);
579
    }
580

    
581
    if (!re) continue;
582
    if (re->n.oa->areaid != 0) continue;
583
    if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA)) continue;
584

    
585
    abrip = ipa_from_rid(en->lsa.rt);
586

    
587
    abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH);
588
    if (!abr) continue;
589

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

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

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

    
619
  WALK_SLIST(en, po->lsal)
620
  {
621
    if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
622
      continue;
623

    
624
    if (en->domain != oa->areaid)
625
      continue;
626

    
627
    /* Page 169 (1) */
628
    if (en->lsa.age == LSA_MAXAGE)
629
      continue;
630

    
631
    /* Page 169 (2) */
632
    if (en->lsa.rt == po->router_id)
633
      continue;
634

    
635

    
636
    if (en->lsa.type == LSA_T_SUM_NET)
637
    {
638
      struct ospf_area *oaa;
639
      int skip = 0;
640

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

    
651
      if (pxopts & OPT_PX_NU)
652
        continue;
653
#endif
654

    
655
      metric = ls->metric & METRIC_MASK;
656
      options = 0;
657
      type = ORT_NET;
658

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

    
682
      ip = ipa_from_rid(dst_rid);
683
      pxlen = MAX_PREFIX_LENGTH;
684
      metric = ls->metric & METRIC_MASK;
685
      options |= ORTA_ASBR;
686
      type = ORT_ROUTER;
687
    }
688

    
689
    /* Page 169 (1) */
690
    if (metric == LSINFINITY)
691
      continue;
692

    
693
    /* Page 169 (4) */
694
    abrip = ipa_from_rid(en->lsa.rt);
695
    if (!(abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH))) continue;
696
    if (abr->n.metric1 == LSINFINITY) continue;
697
    if (!(abr->n.options & ORTA_ABR)) continue;
698

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

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

    
728
  if (po->areano == 0) return;
729

    
730
  po->cleanup = 1;
731

    
732
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
733

    
734
  /* 16. (1) - Invalidate old routing table */
735
  FIB_WALK(&po->rtf, nftmp)
736
  {
737
    ri = (ort *) nftmp;
738
    memcpy(&ri->o, &ri->n, sizeof(orta));        /* Backup old data */
739
    fill_ri(&ri->n);
740
  }
741
  FIB_WALK_END;
742

    
743

    
744
  WALK_LIST(oa, po->area_list)
745
  {
746
    FIB_WALK(&oa->rtr, nftmp)
747
    {
748
      ri = (ort *) nftmp;
749
      memcpy(&ri->o, &ri->n, sizeof(orta));        /* Backup old data */
750
      fill_ri(&ri->n);
751
    }
752
    FIB_WALK_END;
753

    
754
    FIB_WALK(&oa->net_fib, nftmp)
755
    {
756
      anet = (struct area_net *) nftmp;
757
      anet->active = 0;
758
      anet->metric = 1;
759
    }
760
    FIB_WALK_END;
761

    
762
    /* 16. (2) */
763
    ospf_rt_spfa(oa);
764
  }
765

    
766
  /* 16. (3) */
767
  if ((po->areano == 1) || (!po->backbone))
768
  {
769
    ospf_rt_sum(HEAD(po->area_list));
770
  }
771
  else
772
  {
773
    ospf_rt_sum(po->backbone);
774
  }
775

    
776
  /* 16. (4) */
777
  WALK_LIST(oa, po->area_list)
778
  {
779
    if (oa->trcap && (oa->areaid != 0))
780
    {
781
      ospf_rt_sum_tr(oa);
782
      break;
783
    }
784
  }
785

    
786
  /* 16. (5) */
787
  ospf_ext_spf(po);
788

    
789
  rt_sync(po);
790

    
791
  po->calcrt = 0;
792
}
793

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

    
817
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
818

    
819
  WALK_SLIST(en, po->lsal)
820
  {
821
    /* 16.4. (1) */
822
    if (en->lsa.type != LSA_T_EXT)
823
      continue;
824
    if (en->lsa.age == LSA_MAXAGE)
825
      continue;
826

    
827
    /* 16.4. (2) */
828
    if (en->lsa.rt == po->router_id)
829
      continue;
830

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

    
834
    le = en->lsa_body;
835

    
836
    rt_metric = le->metric & METRIC_MASK;
837
    ebit = le->metric & LSA_EXT_EBIT;
838

    
839
    if (rt_metric == LSINFINITY)
840
      continue;
841

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

    
854
    if (pxopts & OPT_PX_NU)
855
      continue;
856

    
857
    rt_fwaddr_valid = le->metric & LSA_EXT_FBIT;
858
    if (rt_fwaddr_valid)
859
      buf = lsa_get_ipv6_addr(buf, &rt_fwaddr);
860
    else 
861
      rt_fwaddr = IPA_NONE;
862

    
863
    if (le->metric & LSA_EXT_TBIT)
864
      rt_tag = *buf++;
865
    else
866
      rt_tag = 0;
867
#endif
868

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

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

    
889
    if (!nf1)
890
      continue;                        /* No AS boundary router found */
891

    
892
    if (nf1->n.metric1 == LSINFINITY)
893
      continue;                        /* distance is INF */
894

    
895
    if (!(nf1->n.options & ORTA_ASBR))
896
      continue;                        /* It is not ASBR */
897

    
898
    if (!rt_fwaddr_valid)
899
    {
900
      nh = nf1->n.nh;
901
      nhi = nf1->n.ifa;
902
      nfh = nf1;
903
      br_metric = nf1->n.metric1;
904
    }
905
    else
906
    {
907
      nf2 = fib_route(&po->rtf, rt_fwaddr, MAX_PREFIX_LENGTH);
908

    
909
      if (!nf2)
910
      {
911
        DBG("Cannot find network route (GW=%I)\n", rt_fwaddr);
912
        continue;
913
      }
914

    
915
      if ((nn = neigh_find(p, &rt_fwaddr, 0)) != NULL)
916
      {
917
        nh = rt_fwaddr;
918
        nhi = ospf_iface_find(po, nn->iface);
919
      }
920
      else
921
      {
922
        nh = nf2->n.nh;
923
        nhi = nf2->n.ifa;
924
      }
925

    
926
      br_metric = nf2->n.metric1;
927
      if (br_metric == LSINFINITY)
928
        continue;                        /* distance is INF */
929
    }
930

    
931
    if (ebit)
932
    {
933
      nfa.type = RTS_OSPF_EXT2;
934
      nfa.metric1 = br_metric;
935
      nfa.metric2 = rt_metric;
936
    }
937
    else
938
    {
939
      nfa.type = RTS_OSPF_EXT1;
940
      nfa.metric1 = br_metric + rt_metric;
941
      nfa.metric2 = LSINFINITY;
942
    }
943

    
944
    nfa.options = 0;
945
    nfa.tag = rt_tag;
946
    nfa.oa = (po->backbone == NULL) ? HEAD(po->area_list) : po->backbone;
947
    nfa.ar = nf1->n.ar;
948
    nfa.nh = nh;
949
    nfa.ifa = nhi;
950
    ri_install(po, ip, pxlen, ORT_NET, &nfa, nfh);
951
  }
952

    
953
}
954

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

    
964
  /* 16.1. (2b) */
965
  if (en == NULL)
966
    return;
967
  if (en->lsa.age == LSA_MAXAGE)
968
    return;
969

    
970
#ifdef OSPFv3
971
  if (en->lsa.type == LSA_T_RT)
972
    {
973
      struct ospf_lsa_rt *rt = en->lsa_body;
974
      if (!(rt->options & OPT_V6) || !(rt->options & OPT_R))
975
        return;
976
    }
977
#endif
978

    
979
  /* 16.1. (2c) */
980
  if (en->color == INSPF)
981
    return;
982

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

    
991
  /* We should check whether there is a reverse link from en to par, */
992
  if (!link_back(oa, en, par))
993
    return;
994

    
995
  if (!calc_next_hop(oa, en, par))
996
  {
997
    log(L_WARN "Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
998
        en->lsa.type, en->lsa.id, en->lsa.rt);
999
    return;
1000
  }
1001

    
1002
  DBG("     Adding candidate: rt: %R, id: %R, type: %u\n",
1003
      en->lsa.rt, en->lsa.id, en->lsa.type);
1004

    
1005
  if (en->color == CANDIDATE)
1006
  {                                /* We found a shorter path */
1007
    rem_node(&en->cn);
1008
  }
1009
  en->dist = dist;
1010
  en->color = CANDIDATE;
1011

    
1012
  prev = NULL;
1013

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

    
1037
    if (!added)
1038
    {
1039
      add_tail(l, &en->cn);
1040
    }
1041
  }
1042
}
1043

    
1044

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

    
1055
static int
1056
calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
1057
              struct top_hash_entry *par)
1058
{
1059
  struct ospf_neighbor *neigh;
1060
  struct proto *p = &oa->po->proto;
1061
  struct proto_ospf *po = oa->po;
1062
  struct ospf_iface *ifa;
1063

    
1064
  /* 16.1.1. The next hop calculation */
1065
  DBG("     Next hop called.\n");
1066
  if (ipa_equal(par->nh, IPA_NONE))
1067
  {
1068
    DBG("     Next hop calculating for id: %R rt: %R type: %u\n",
1069
        en->lsa.id, en->lsa.rt, en->lsa.type);
1070

    
1071
    /* 
1072
     * There are three cases:
1073
     * 1) en is a local network (and par is root)
1074
     * 2) en is a ptp or ptmp neighbor (and par is root)
1075
     * 3) en is a bcast or nbma neighbor (and par is local network)
1076
     */
1077

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

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

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

    
1114
    /* Probably bug or some race condition, we log it */
1115
    log(L_ERR "Unexpected case in next hop calculation");
1116

    
1117
    return 0;
1118
  }
1119

    
1120
  en->nh = par->nh;
1121
  en->nhi = par->nhi;
1122
  return 1;
1123
}
1124

    
1125
static void
1126
rt_sync(struct proto_ospf *po)
1127
{
1128
  struct proto *p = &po->proto;
1129
  struct fib_iterator fit;
1130
  struct fib *fib = &po->rtf;
1131
  ort *nf;
1132
  struct ospf_area *oa, *oaa;
1133
  struct area_net *anet;
1134
  int flush;
1135

    
1136
  /* This is used for forced reload of routes */
1137
  int reload = (po->calcrt == 2);
1138

    
1139
  OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation");
1140

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

    
1154
      bzero(&a0, sizeof(a0));
1155

    
1156
      a0.proto = p;
1157
      a0.source = nf->n.type;
1158
      a0.scope = SCOPE_UNIVERSE;
1159
      a0.cast = RTC_UNICAST;
1160
      a0.dest = RTD_ROUTER;
1161
      a0.flags = 0;
1162
      a0.aflags = 0;
1163
      a0.iface = NULL;
1164
      if (nf->n.ifa) a0.iface = nf->n.ifa->iface;
1165
      a0.gw = nf->n.nh;
1166

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

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

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

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

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

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

    
1251
        if (oaa == oa) continue;
1252

    
1253
        if ((oa == po->backbone) && oaa->trcap) fl = 1;
1254

    
1255
        if (oaa->stub) fl = 1;
1256

    
1257
        if (fl) flush_sum_lsa(oaa, &anet->fn, ORT_NET);
1258
        else originate_sum_lsa(oaa, &anet->fn, ORT_NET, anet->metric, 0);
1259
      }
1260
    }
1261
    FIB_WALK_END;
1262

    
1263
    /* Check default summary LSA for stub areas
1264
     * just for router connected to backbone */
1265
    if (po->backbone)
1266
    {
1267
      struct fib_node fnn;
1268

    
1269
      fnn.prefix = IPA_NONE;
1270
      fnn.pxlen = 0;
1271
      if (oa->stub) originate_sum_lsa(oa, &fnn, ORT_NET, oa->stub, 0);
1272
      else flush_sum_lsa(oa, &fnn, ORT_NET);
1273
    }
1274
  }
1275
}