Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / rt.c @ 60e04f04

History | View | Annotate | Download (24.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
12
add_cand(list * l, struct top_hash_entry *en,
13
         struct top_hash_entry *par, u16 dist, struct ospf_area *oa);
14
static void
15
calc_next_hop(struct top_hash_entry *en,
16
              struct top_hash_entry *par, struct ospf_area *oa);
17
static void ospf_ext_spf(struct proto_ospf *po);
18
static void rt_sync(struct proto_ospf *po);
19

    
20
static void
21
fill_ri(orta * orta)
22
{
23
  orta->type = RTS_DUMMY;
24
  orta->capa = 0;
25
  orta->oa = NULL;
26
  orta->metric1 = LSINFINITY;
27
  orta->metric2 = LSINFINITY;
28
  orta->nh = IPA_NONE;
29
  orta->ifa = NULL;
30
  orta->ar = NULL;
31
  orta->tag = 0;
32
}
33

    
34
void
35
ospf_rt_initort(struct fib_node *fn)
36
{
37
  ort *ri = (ort *) fn;
38
  fill_ri(&ri->n);
39
  memcpy(&ri->o, &ri->n, sizeof(orta));
40
  ri->efn = NULL;
41
}
42

    
43
/* If new is better return 1 */
44

    
45
/* 
46
 * This is hard to understand:
47
 * If rfc1583 is set to 1, it work likes normal route_better()
48
 * But if it is set to 0, it prunes number of AS bondary
49
 * routes before it starts the router decision
50
 */
51
static int
52
ri_better(struct proto_ospf *po, orta * new, ort *nefn, orta * old, ort *oefn, int rfc1583)
53
{
54
  int newtype = new->type;
55
  int oldtype = old->type;
56

    
57
  if (old->type == RTS_DUMMY)
58
    return 1;
59

    
60
  if (old->metric1 == LSINFINITY)
61
    return 1;
62

    
63
  if(!rfc1583)
64
  {
65
    if(new->oa->areaid == 0) newtype = RTS_OSPF_IA;
66
    if(old->oa->areaid == 0) oldtype = RTS_OSPF_IA;
67
  }
68

    
69
  if (new->type < old->type)
70
    return 1;
71

    
72
  if (new->type > old->type)
73
    return 0;
74

    
75
  /* Same type */
76
  if(new->type == RTS_OSPF_EXT2)
77
  {
78
    if (new->metric2 < old->metric2) return 1;
79
    if (new->metric2 > old->metric2) return 0;
80
  }
81

    
82
  if(((new->type == RTS_OSPF_EXT2) || (new->type == RTS_OSPF_EXT1)) && (!po->rfc1583))
83
  {
84
    int newtype = nefn->n.type;
85
    int oldtype = oefn->n.type;
86

    
87
    if(nefn->n.oa->areaid == 0) newtype = RTS_OSPF_IA;
88
    if(oefn->n.oa->areaid == 0) oldtype = RTS_OSPF_IA;
89

    
90
    if(newtype < oldtype) return 1;
91
    if(newtype > oldtype) return 0;
92
  }
93

    
94
  if (new->metric1 < old->metric1)
95
    return 1;
96

    
97
  if (new->metric1 > old->metric1)
98
    return 0;
99

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

    
102
  return 0;                        /* Old is shorter or same */
103
}
104

    
105
static void
106
ri_install(struct proto_ospf *po, ip_addr prefix, int pxlen, int dest,
107
           orta * new, ort * ipath)
108
{
109
  struct ospf_area *oa = new->oa;
110
  ort *old;
111

    
112
  if (dest == ORT_NET)
113
  {
114
    struct area_net *anet;
115
    old = (ort *) fib_get(&po->rtf, &prefix, pxlen);
116
    if (ri_better(po, new, ipath, &old->n, old->efn, 1))
117
    {
118
      memcpy(&old->n, new, sizeof(orta));
119
      old->efn = ipath;
120
    }
121
    if ((new->type == RTS_OSPF) && (anet = (struct area_net *)fib_route(&oa->net_fib, prefix, pxlen)))
122
    {
123
       anet->active = 1;
124
       if (new->metric1 < anet->metric) anet->metric = new->metric1;
125
    }
126
  }
127
  else
128
  {
129
    old = (ort *) fib_get(&oa->rtr, &prefix, pxlen);
130

    
131
    if (ri_better(po, new, ipath, &old->n, old->efn, 1))
132
    {
133
      memcpy(&old->n, new, sizeof(orta));
134
      old->efn = ipath;
135
    }
136
  }
137
}
138

    
139
static void
140
ospf_rt_spfa(struct ospf_area *oa)
141
{
142
  u32 i, *rts;
143
  struct ospf_lsa_rt *rt;
144
  struct ospf_lsa_rt_link *rtl, *rr;
145
  struct proto *p = &oa->po->proto;
146
  struct proto_ospf *po = oa->po;
147
  struct ospf_lsa_net *ln;
148
  orta nf;
149
  struct ospf_iface *iface;
150
  struct top_hash_entry *act, *tmp;
151
  node *n;
152

    
153

    
154
  if (oa->rt == NULL)
155
    return;
156

    
157
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for area %I",
158
             oa->areaid);
159

    
160
  if (oa->rt->dist != LSINFINITY)
161
    bug("Aging was not processed.");
162

    
163
  init_list(&oa->cand);                /* Empty list of candidates */
164
  oa->trcap = 0;
165

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

    
168
  oa->rt->dist = 0;
169
  oa->rt->color = CANDIDATE;
170
  add_head(&oa->cand, &oa->rt->cn);
171
  DBG("RT LSA: rt: %I, id: %I, type: %u\n", oa->rt->lsa.rt,
172
      oa->rt->lsa.id, oa->rt->lsa.type);
173

    
174
  while (!EMPTY_LIST(oa->cand))
175
  {
176
    n = HEAD(oa->cand);
177
    act = SKIP_BACK(struct top_hash_entry, cn, n);
178
    rem_node(n);
179

    
180
    DBG("Working on LSA: rt: %I, id: %I, type: %u\n", act->lsa.rt,
181
        act->lsa.id, act->lsa.type);
182

    
183
    act->color = INSPF;
184
    switch (act->lsa.type)
185
    {
186
    case LSA_T_RT:
187
      rt = (struct ospf_lsa_rt *) act->lsa_body;
188
      if (rt->veb.bit.v)
189
        oa->trcap = 1;
190
      if (rt->veb.bit.b || rt->veb.bit.e)
191
      {
192
        nf.type = RTS_OSPF;
193
        nf.capa = 0;
194
        if (rt->veb.bit.b) nf.capa |= ORTA_ABR;
195
        if (rt->veb.bit.e) nf.capa |= ORTA_ASBR;
196
        nf.metric1 = act->dist;
197
        nf.metric2 = LSINFINITY;
198
        nf.oa = oa;
199
        nf.ar = act;
200
        nf.nh = act->nh;
201
        nf.ifa = act->nhi;
202
        ri_install(po, ipa_from_u32(act->lsa.id), 32, ORT_ROUTER, &nf, NULL);
203
      }
204
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
205
      DBG("  Number of links: %u\n", rt->links);
206
      for (i = 0; i < rt->links; i++)
207
      {
208
        tmp = NULL;
209
        rtl = (rr + i);
210
        DBG("     Working on link: %I (type: %u)  ", rtl->id, rtl->type);
211
        switch (rtl->type)
212
        {
213
        case LSART_STUB:
214
          /*
215
           * This violates rfc2328! but I hope
216
           * it's also correct.
217
           */
218
          DBG("\n");
219

    
220
          nf.type = RTS_OSPF;
221
          nf.capa = 0;
222
          nf.metric1 = act->dist + rtl->metric;
223
          nf.metric2 = LSINFINITY;
224
          nf.oa = oa;
225
          nf.ar = act;
226
          nf.nh = act->nh;
227
          nf.ifa = act->nhi;
228

    
229
          if (act == oa->rt)
230
          {
231
            struct ospf_iface *iff;
232

    
233
            WALK_LIST(iff, po->iface_list)        /* Try to find corresponding interface */
234
            {
235
               if (iff->iface && (iff->type != OSPF_IT_VLINK) &&
236
                 (rtl->id == (ipa_to_u32(ipa_mkmask(iff->iface->addr->pxlen))
237
                 & ipa_to_u32(iff->iface->addr->prefix))))        /* No VLINK and IP must match */
238
               {
239
                 nf.ifa = iff;
240
                 break;
241
               }
242
            }
243
          }
244

    
245
          if (!nf.ifa)
246
            continue;
247

    
248
          ri_install(po, ipa_from_u32(rtl->id),
249
                     ipa_mklen(ipa_from_u32(rtl->data)), ORT_NET, &nf, NULL);
250
          break;
251

    
252
        case LSART_NET:
253
          tmp = ospf_hash_find(po->gr, oa->areaid, rtl->id, rtl->id, LSA_T_NET);
254
          if (tmp == NULL)
255
            DBG("Not found!\n");
256
          else
257
            DBG("Found. :-)\n");
258
          break;
259

    
260
        case LSART_VLNK:
261
        case LSART_PTP:
262
          tmp = ospf_hash_find(po->gr, oa->areaid, rtl->id, rtl->id, LSA_T_RT);
263
          DBG("PTP found.\n");
264
          break;
265
        default:
266
          log("Unknown link type in router lsa. (rid = %I)", act->lsa.id);
267
          break;
268
        }
269
        if (tmp)
270
          DBG("Going to add cand, Mydist: %u, Req: %u\n",
271
              tmp->dist, act->dist + rtl->metric);
272
        add_cand(&oa->cand, tmp, act, act->dist + rtl->metric, oa);
273
      }
274
      break;
275
    case LSA_T_NET:
276
      ln = act->lsa_body;
277
      nf.type = RTS_OSPF;
278
      nf.capa = 0;
279
      nf.metric1 = act->dist;
280
      nf.metric2 = LSINFINITY;
281
      nf.oa = oa;
282
      nf.ar = act;
283
      nf.nh = act->nh;
284
      nf.ifa = act->nhi;
285
      ri_install(po, ipa_and(ipa_from_u32(act->lsa.id), ln->netmask),
286
                 ipa_mklen(ln->netmask), ORT_NET, &nf, NULL);
287

    
288
      rts = (u32 *) (ln + 1);
289
      for (i = 0; i < (act->lsa.length - sizeof(struct ospf_lsa_header) -
290
                       sizeof(struct ospf_lsa_net)) / sizeof(u32); i++)
291
      {
292
        DBG("     Working on router %I ", *(rts + i));
293
        tmp = ospf_hash_find(po->gr, oa->areaid, *(rts + i), *(rts + i), LSA_T_RT);
294
        if (tmp != NULL)
295
          DBG("Found :-)\n");
296
        else
297
          DBG("Not found!\n");
298
        add_cand(&oa->cand, tmp, act, act->dist, oa);
299
      }
300
      break;
301
    }
302
  }
303

    
304
  /* Find new/lost VLINK peers */
305
  WALK_LIST(iface, po->iface_list)
306
  {
307
    if ((iface->type == OSPF_IT_VLINK) && (iface->voa == oa))
308
    {
309
      if ((tmp = ospf_hash_find(po->gr, oa->areaid, iface->vid, iface->vid, LSA_T_RT)) &&
310
        (!ipa_equal(tmp->lb, IPA_NONE)))
311
      {
312
        if ((iface->state != OSPF_IS_PTP) || (iface->iface != tmp->nhi->iface) || (!ipa_equal(iface->vip, tmp->lb)))
313
        {
314
          OSPF_TRACE(D_EVENTS, "Vlink peer %I found", tmp->lsa.id);
315
          ospf_iface_sm(iface, ISM_DOWN);
316
          iface->iface = tmp->nhi->iface;
317
          iface->vip = tmp->lb;
318
          ospf_iface_sm(iface, ISM_UP);
319
        }
320
      }
321
      else
322
      {
323
        if (iface->state > OSPF_IS_DOWN)
324
        {
325
          OSPF_TRACE(D_EVENTS, "Vlink peer %I lost", iface->vid);
326
          ospf_iface_sm(iface, ISM_DOWN);
327
        }
328
      }
329
    }
330
  }
331
}
332

    
333
static int
334
link_back(struct ospf_area *oa, struct top_hash_entry *fol, struct top_hash_entry *pre)
335
{
336
  u32 i, *rts;
337
  struct ospf_lsa_net *ln;
338
  struct ospf_lsa_rt *rt;
339
  struct ospf_lsa_rt_link *rtl, *rr;
340
  struct proto_ospf *po = oa->po;
341

    
342
  if(!pre) return 0;
343
  if(!fol) return 0;
344
  switch (fol->lsa.type)
345
  {
346
    case LSA_T_RT:
347
      rt = (struct ospf_lsa_rt *) fol->lsa_body;
348
      rr = (struct ospf_lsa_rt_link *) (rt + 1);
349
      for (i = 0; i < rt->links; i++)
350
      {
351
        rtl = (rr + i);
352
        switch (rtl->type)
353
        {
354
        case LSART_STUB:
355
          break;
356
        case LSART_NET:
357
          if (ospf_hash_find(po->gr, oa->areaid, rtl->id, rtl->id, LSA_T_NET) == pre)
358
          {
359
            fol->lb = ipa_from_u32(rtl->data);
360
            return 1;
361
          }
362
          break;
363
        case LSART_VLNK:
364
        case LSART_PTP:
365
          if (ospf_hash_find(po->gr, oa->areaid, rtl->id, rtl->id, LSA_T_RT) == pre)
366
          {
367
            fol->lb = ipa_from_u32(rtl->data);
368
            return 1;
369
          }
370
          break;
371
        default:
372
          log("Unknown link type in router lsa. (rid = %I)", fol->lsa.id);
373
          break;
374
        }
375
      }
376
      break;
377
    case LSA_T_NET:
378
      ln = fol->lsa_body;
379
      rts = (u32 *) (ln + 1);
380
      for (i = 0; i < (fol->lsa.length - sizeof(struct ospf_lsa_header) -
381
                       sizeof(struct ospf_lsa_net)) / sizeof(u32); i++)
382
      {
383
        if (ospf_hash_find(po->gr, oa->areaid, *(rts + i), *(rts + i), LSA_T_RT) == pre)
384
        {
385
          return 1;
386
        }
387
      }
388
      break;
389
    default:
390
      bug("Unknown lsa type. (id = %I)", fol->lsa.id);
391
  }
392
  return 0;
393
}
394

    
395
static void
396
ospf_rt_sum_tr(struct ospf_area *oa)
397
{
398
  struct proto *p = &oa->po->proto;
399
  struct proto_ospf *po = oa->po;
400
  struct ospf_area *bb = po->backbone;
401
  ip_addr *mask, ip, abrip;
402
  struct top_hash_entry *en;
403
  int mlen = -1, type = -1;
404
  union ospf_lsa_sum_tm *tm;
405
  ort *re = NULL, *abr;
406
  orta nf;
407

    
408
  if(!bb) return;
409

    
410
  WALK_SLIST(en, po->lsal)
411
  {
412
    if (en->oa != oa)
413
      continue;
414
    if (en->lsa.age == LSA_MAXAGE)
415
      continue;
416
    if (en->dist == LSINFINITY)
417
      continue;
418

    
419
    if (en->lsa.rt == p->cf->global->router_id)
420
      continue;
421

    
422
    if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
423
      continue;
424

    
425
    mask = (ip_addr *)en->lsa_body;
426

    
427
    if (en->lsa.type == LSA_T_SUM_NET)
428
    {
429
      mlen = ipa_mklen(*mask);
430
      ip = ipa_and(ipa_from_u32(en->lsa.id), *mask);
431
      type = ORT_NET;
432
      re = (ort *) fib_find(&po->rtf, &ip, 32);
433
    }
434

    
435
    if (en->lsa.type == LSA_T_SUM_RT)
436
    {
437
      ip = ipa_from_u32(en->lsa.id);
438
      mlen = 32;
439
      type = ORT_ROUTER;
440
      re = (ort *) fib_find(&bb->rtr, &ip, 32);
441
    }
442
    if(!re) continue;
443
    if(re->n.oa->areaid != 0) continue;
444
    if((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA)) continue;
445

    
446
    abrip = ipa_from_u32(en->lsa.rt);
447

    
448
    abr = fib_find(&oa->rtr, &abrip, 32);
449
    if(!abr) continue;
450

    
451
    tm = (union ospf_lsa_sum_tm *)(mask + 1);
452

    
453
    nf.type = re->n.type;
454
    nf.capa = ORTA_ASBR;
455
    nf.metric1 = abr->n.metric1 + (tm->metric & METRIC_MASK);
456
    nf.metric2 = LSINFINITY;
457
    nf.oa = oa;
458
    nf.ar = abr->n.ar;
459
    nf.nh = abr->n.nh;
460
    nf.ifa = abr->n.ifa;
461
    ri_install(po, ip, mlen, type, &nf, NULL);
462
  }
463
}
464
  
465

    
466
static void
467
ospf_rt_sum(struct ospf_area *oa)
468
{
469
  struct proto_ospf *po = oa->po;
470
  struct proto *p = &po->proto;
471
  struct top_hash_entry *en;
472
  ip_addr *mask, ip, abrip;        /* abrIP is actually ID */
473
  struct area_net *anet;
474
  orta nf;
475
  ort *re, *abr;
476
  int mlen = -1, type = -1;
477
  union ospf_lsa_sum_tm *tm;
478

    
479
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for inter-area (area %I)", oa->areaid);
480

    
481
  WALK_SLIST(en, po->lsal)
482
  {
483
    if (en->oa != oa)
484
      continue;
485
    /* Page 169 (1) */
486
    if (en->lsa.age == LSA_MAXAGE)
487
      continue;
488
    /* Page 169 (2) */
489
    if (en->lsa.rt == p->cf->global->router_id)
490
      continue;
491

    
492
    if((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET))
493
      continue;
494

    
495
    mask = (ip_addr *)en->lsa_body;
496
    tm = (union ospf_lsa_sum_tm *)(mask + 1);
497

    
498
    if((tm->metric & METRIC_MASK) == LSINFINITY)
499
      continue;
500

    
501
    if (en->lsa.type == LSA_T_SUM_NET)
502
    {
503
      struct ospf_area *oaa;
504
      int skip = 0;
505
      mlen = ipa_mklen(*mask);
506
      ip = ipa_and(ipa_from_u32(en->lsa.id), *mask);
507
      /* Page 169 (3) */
508
      WALK_LIST(oaa, po->area_list)
509
      {
510
        if ((anet = fib_find(&oaa->net_fib, &ip, mlen)) && anet->active)
511
        {
512
          skip = 1;
513
          break;
514
        }
515
      }
516
      if (skip) continue;
517

    
518
      type = ORT_NET;
519
    }
520
    else
521
    {
522
      ip = ipa_from_u32(en->lsa.id);
523
      mlen = 32;
524
      type = ORT_ROUTER;
525
    }
526
    abrip = ipa_from_u32(en->lsa.rt);
527

    
528
    if (!(abr = (ort *) fib_find(&oa->rtr, &abrip, 32))) continue;
529
    if (abr->n.metric1 == LSINFINITY) continue;
530
    if (!(abr->n.capa & ORTA_ABR)) continue;
531

    
532
    nf.type = RTS_OSPF_IA;
533
    nf.capa = ORTA_ASBR;
534
    nf.metric1 = abr->n.metric1 + (tm->metric & METRIC_MASK);
535
    nf.metric2 = LSINFINITY;
536
    nf.oa = oa;
537
    nf.ar = abr->n.ar;
538
    nf.nh = abr->n.nh;
539
    nf.ifa = abr->n.ifa;
540
    ri_install(po, ip, mlen, type, &nf, NULL);
541
  }
542
}
543

    
544
/**
545
 * ospf_rt_spf - calculate internal routes
546
 * @po: OSPF protocol
547
 *
548
 * Calculation of internal paths in an area is described in 16.1 of RFC 2328.
549
 * It's based on Dijkstra's shortest path tree algorithms.
550
 * This function is invoked from ospf_disp().
551
 */
552
void
553
ospf_rt_spf(struct proto_ospf *po)
554
{
555
  struct proto *p = &po->proto;
556
  struct ospf_area *oa;
557
  int i;
558
  ort *ri;
559
  struct area_net *anet;
560

    
561
  if (po->areano == 0) return;
562

    
563
  po->cleanup = 1;
564

    
565
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation");
566

    
567
  /* Invalidate old routing table */
568
  FIB_WALK(&po->rtf, nftmp)
569
  {
570
    ri = (ort *) nftmp;
571
    memcpy(&ri->o, &ri->n, sizeof(orta));        /* Backup old data */
572
    fill_ri(&ri->n);
573
  }
574
  FIB_WALK_END;
575

    
576

    
577
  WALK_LIST(oa, po->area_list)
578
  {
579
    FIB_WALK(&oa->rtr, nftmp)
580
    {
581
      ri = (ort *) nftmp;
582
      memcpy(&ri->o, &ri->n, sizeof(orta));        /* Backup old data */
583
      fill_ri(&ri->n);
584
    }
585
    FIB_WALK_END;
586

    
587
    FIB_WALK(&oa->net_fib, nftmp)
588
    {
589
      anet = (struct area_net *) nftmp;
590
      anet->active = 0;
591
      anet->metric = LSINFINITY;
592
    }
593
    FIB_WALK_END;
594
    ospf_rt_spfa(oa);
595
  }
596

    
597
  if ((po->areano == 1) || (!po->backbone))
598
  {
599
    ospf_rt_sum(HEAD(po->area_list));
600
  }
601
  else
602
  {
603
    ospf_rt_sum(po->backbone);
604
  }
605

    
606
  WALK_LIST(oa, po->area_list)
607
  {
608
    if (oa->trcap && (oa->areaid != 0))
609
    {
610
      ospf_rt_sum_tr(oa);
611
      break;
612
    }
613
  }
614

    
615
  ospf_ext_spf(po);
616

    
617
  rt_sync(po);
618

    
619
  po->calcrt = 0;
620
}
621

    
622

    
623
/**
624
 * ospf_ext_spf - calculate external paths
625
 * @po: protocol
626
 *
627
 * After routing table for any area is calculated, calculation of external
628
 * path is invoked. This process is described in 16.6 of RFC 2328.
629
 * Inter- and Intra-area paths are always prefered over externals.
630
 */
631
static void
632
ospf_ext_spf(struct proto_ospf *po)
633
{
634
  ort *nf1, *nf2, *nfh;
635
  orta nfa;
636
  struct top_hash_entry *en;
637
  struct proto *p = &po->proto;
638
  struct ospf_lsa_ext *le;
639
  struct ospf_lsa_ext_tos *lt;
640
  int mlen;
641
  ip_addr ip, nh, rtid;
642
  struct ospf_iface *nhi = NULL;
643
  int met1, met2;
644
  neighbor *nn;
645
  struct ospf_lsa_rt *rt;
646
  struct ospf_area *atmp;
647

    
648

    
649
  OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes");
650

    
651
  WALK_SLIST(en, po->lsal)
652
  {
653
    if (en->lsa.type != LSA_T_EXT)
654
      continue;
655
    if (en->lsa.age == LSA_MAXAGE)
656
      continue;
657
    if (en->lsa.rt == p->cf->global->router_id)
658
      continue;
659

    
660
    le = en->lsa_body;
661
    lt = (struct ospf_lsa_ext_tos *) (le + 1);
662

    
663
    DBG("%s: Working on LSA. ID: %I, RT: %I, Type: %u, Mask %I\n",
664
        p->name, en->lsa.id, en->lsa.rt, en->lsa.type, le->netmask);
665

    
666
    if ((lt->etm.metric & METRIC_MASK) == LSINFINITY)
667
      continue;
668
    ip = ipa_and(ipa_from_u32(en->lsa.id), le->netmask);
669
    mlen = ipa_mklen(le->netmask);
670
    if ((mlen < 0) || (mlen > 32))
671
    {
672
      log("%s: Invalid mask in LSA. ID: %I, RT: %I, Type: %u, Mask %I",
673
          p->name, en->lsa.id, en->lsa.rt, en->lsa.type, le->netmask);
674
      continue;
675
    }
676
    nhi = NULL;
677
    nh = IPA_NONE;
678

    
679
    met1 = LSINFINITY;
680
    met2 = LSINFINITY;
681

    
682
    rtid = ipa_from_u32(en->lsa.rt);
683

    
684
    nf1 = NULL;
685
    WALK_LIST(atmp, po->area_list)
686
    {
687
      nfh = fib_find(&atmp->rtr, &rtid, 32);
688
      if(nfh == NULL) continue;
689
      if(nf1 == NULL) nf1 = nfh;
690
      else if(ri_better(po, &nfh->n, NULL, &nf1->n, NULL, po->rfc1583)) nf1 = nfh;
691
    }
692

    
693
    if (!nf1)
694
      continue;                        /* No AS boundary router found */
695

    
696
    if (nf1->n.metric1 == LSINFINITY)
697
      continue;                        /* distance is INF */
698

    
699
    if (!(nf1->n.capa & ORTA_ASBR))
700
      continue;                        /* It is not ASBR */
701

    
702
    if (ipa_equal(lt->fwaddr, IPA_NONE))
703
    {
704
      if (lt->etm.etos.ebit)
705
      {                                /* FW address == 0 */
706
        met1 = nf1->n.metric1;
707
        met2 = (lt->etm.metric & METRIC_MASK);
708
      }
709
      else
710
      {
711
        met1 = nf1->n.metric1 + (lt->etm.metric & METRIC_MASK);
712
        met2 = LSINFINITY;
713
      }
714

    
715
      nh = nf1->n.nh;
716
      nhi = nf1->n.ifa;
717
      nfh = nf1;
718
    }
719
    else
720
    {                                /* FW address !=0 */
721
      nf2 = fib_route(&po->rtf, lt->fwaddr, 32);
722

    
723
      if (!nf2)
724
      {
725
        DBG("Cannot find network route (GW=%I)\n", lt->fwaddr);
726
        continue;
727
      }
728

    
729
      if (lt->etm.etos.ebit)
730
      {
731
        met1 = nf2->n.metric1;
732
        met2 = (lt->etm.metric & METRIC_MASK);
733
      }
734
      else
735
      {
736
        met1 = nf2->n.metric1 + (lt->etm.metric & METRIC_MASK);
737
        met2 = LSINFINITY;
738
      }
739

    
740
      if ((nn = neigh_find(p, &lt->fwaddr, 0)) != NULL)
741
      {
742
        nh = lt->fwaddr;
743
        nhi = ospf_iface_find(po, nn->iface);
744
      }
745
      else
746
      {
747
        nh = nf2->n.nh;
748
        nhi = nf2->n.ifa;
749
      }
750

    
751
      nfh = nf2;
752
    }
753

    
754
    nfa.type = RTS_OSPF_EXT2;
755
    if(met2 == LSINFINITY) nfa.type = RTS_OSPF_EXT1;
756
    nfa.capa = 0;
757
    nfa.metric1 = met1;
758
    nfa.metric2 = met2;
759
    nfa.oa = po->backbone;
760
    nfa.ar = nf1->n.ar;
761
    nfa.nh = nh;
762
    nfa.ifa = nhi;
763
    nfa.tag = lt->tag;
764
    ri_install(po, ip, mlen, ORT_NET, &nfa, nfh);
765
  }
766

    
767
}
768

    
769
/* Add LSA into list of candidates in Dijkstra's algorithm */
770
static void
771
add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
772
         u16 dist, struct ospf_area *oa)
773
{
774
  node *prev, *n;
775
  int added = 0;
776
  struct top_hash_entry *act;
777

    
778
  if (en == NULL)
779
    return;
780
  if (en->lsa.age == LSA_MAXAGE)
781
    return;
782

    
783
  if (en->color == INSPF)
784
    return;
785

    
786
  if (dist >= en->dist)
787
    return;
788
  /*
789
   * FIXME The line above (=) is not a bug, but we don't support multiple
790
   * next hops. I'll start as soon as nest will
791
   */
792

    
793
  if (!link_back(oa, en, par))
794
    return;
795

    
796
  DBG("     Adding candidate: rt: %I, id: %I, type: %u\n", en->lsa.rt,
797
      en->lsa.id, en->lsa.type);
798

    
799
  en->nhi = NULL;
800
  en->nh = IPA_NONE;
801

    
802
  calc_next_hop(en, par, oa);
803

    
804
  if (!en->nhi)
805
    return;                        /* We cannot find next hop, ignore it */
806

    
807
  if (en->color == CANDIDATE)
808
  {                                /* We found a shorter path */
809
    rem_node(&en->cn);
810
  }
811
  en->dist = dist;
812
  en->color = CANDIDATE;
813

    
814
  prev = NULL;
815

    
816
  if (EMPTY_LIST(*l))
817
  {
818
    add_head(l, &en->cn);
819
  }
820
  else
821
  {
822
    WALK_LIST(n, *l)
823
    {
824
      act = SKIP_BACK(struct top_hash_entry, cn, n);
825
      if ((act->dist > dist) ||
826
          ((act->dist == dist) && (act->lsa.type == LSA_T_NET)))
827
      {
828
        if (prev == NULL)
829
          add_head(l, &en->cn);
830
        else
831
          insert_node(&en->cn, prev);
832
        added = 1;
833
        break;
834
      }
835
      prev = n;
836
    }
837

    
838
    if (!added)
839
    {
840
      add_tail(l, &en->cn);
841
    }
842
  }
843
}
844

    
845
static void
846
calc_next_hop(struct top_hash_entry *en, struct top_hash_entry *par,
847
              struct ospf_area *oa)
848
{
849
  struct ospf_neighbor *neigh;
850
  struct proto *p = &oa->po->proto;
851
  struct proto_ospf *po = oa->po;
852
  struct ospf_iface *ifa;
853
  u32 myrid = p->cf->global->router_id;
854

    
855
  DBG("     Next hop called.\n");
856
  if (ipa_equal(par->nh, IPA_NONE))
857
  {
858
    neighbor *nn;
859
    DBG("     Next hop calculating for id: %I rt: %I type: %u\n",
860
        en->lsa.id, en->lsa.rt, en->lsa.type);
861

    
862
    if (par == oa->rt)
863
    {
864
      if (en->lsa.type == LSA_T_NET)
865
      {
866
        if (en->lsa.rt == myrid)
867
        {
868
          WALK_LIST(ifa, po->iface_list)
869
            if (ifa->iface && (ipa_compare
870
                (ifa->iface->addr->ip, ipa_from_u32(en->lsa.id)) == 0))
871
          {
872
            en->nhi = ifa;
873
            return;
874
          }
875
          log(L_ERR "I didn't find interface for my self originated LSA!\n");
876
          /* This could sometimes happen */
877
          return;
878
        }
879
        else
880
        {
881
          ip_addr ip = ipa_from_u32(en->lsa.id);
882
          nn = neigh_find(p, &ip, 0);
883
          if (nn)
884
            en->nhi = ospf_iface_find(po, nn->iface);
885
          return;
886
        }
887
      }
888
      else
889
      {
890
        if ((neigh = find_neigh_noifa(po, en->lsa.rt)) == NULL)
891
          return;
892
        en->nhi = neigh->ifa;
893
        if (neigh->ifa->type == OSPF_IT_VLINK) 
894
        en->nh = neigh->ip;        /* Yes, neighbor is it's
895
                                 * own next hop */
896
        return;
897
      }
898
    }
899
    if (par->lsa.type == LSA_T_NET)
900
    {
901
      if (en->lsa.type == LSA_T_NET)
902
        bug("Parent for net is net?");
903
      if ((en->nhi = par->nhi) == NULL)
904
        bug("Did not find next hop interface for INSPF lsa!");
905
      if ((neigh = find_neigh_noifa(po, en->lsa.rt)) == NULL)
906
        return;
907
      en->nhi = neigh->ifa;
908
      en->nh = neigh->ip;        /* Yes, neighbor is it's own
909
                                 * next hop */
910
      return;
911
    }
912
    else
913
    {                                /* Parent is some RT neighbor */
914
      log(L_ERR "Router's parent has no next hop. (EN=%I, PAR=%I)",
915
          en->lsa.id, par->lsa.id);
916
      /* I hoped this would never happen */
917
      return;
918
    }
919
  }
920
  en->nh = par->nh;
921
  en->nhi = par->nhi;
922
  DBG("     Next hop calculated: %I.\n", en->nh);
923
}
924

    
925
static void
926
rt_sync(struct proto_ospf *po)
927
{
928
  struct proto *p = &po->proto;
929
  struct fib_iterator fit;
930
  struct fib *fib = &po->rtf;
931
  ort *nf;
932
  struct ospf_area *oa, *oaa;
933
  struct area_net *anet;
934
  int flush;
935

    
936
  OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation");
937

    
938
  DBG("Now syncing my rt table with nest's\n");
939
  FIB_ITERATE_INIT(&fit, fib);
940
again1:
941
  FIB_ITERATE_START(fib, &fit, nftmp)
942
  {
943
    nf = (ort *) nftmp;
944
    check_sum_lsa(po, nf, ORT_NET);
945
    if (memcmp(&nf->n, &nf->o, sizeof(orta)))
946
    {                                /* Some difference */
947
      net *ne;
948
      rta a0;
949
      rte *e;
950

    
951
      bzero(&a0, sizeof(a0));
952

    
953
      a0.proto = p;
954
      a0.source = nf->n.type;
955
      a0.scope = SCOPE_UNIVERSE;
956
      a0.cast = RTC_UNICAST;
957
      a0.dest = RTD_ROUTER;
958
      a0.flags = 0;
959
      a0.aflags = 0;
960
      a0.iface = NULL;
961
      if (nf->n.ifa) a0.iface = nf->n.ifa->iface;
962
      a0.gw = nf->n.nh;
963

    
964
      if (ipa_equal(nf->n.nh, IPA_NONE)) a0.dest = RTD_DEVICE;
965
      
966
      if ((!ipa_equal(nf->n.nh, IPA_NONE)) && (!neigh_find(p, &nf->n.nh, 0)))
967
      {
968
        int found = 0;
969
        struct ospf_iface *ifa;
970
        struct top_hash_entry *en;
971
        DBG("Trying to find correct next hop");
972
        WALK_LIST(ifa, po->iface_list)
973
        {
974
          if ((ifa->type == OSPF_IT_VLINK) && ipa_equal(ifa->vip, nf->n.nh))
975
          {
976
            if ((en = ospf_hash_find(po->gr, ifa->voa->areaid, ifa->vid, ifa->vid, LSA_T_RT)) &&
977
              (!ipa_equal(en->nh, IPA_NONE)))
978
            {
979
              a0.gw = en->nh;
980
              found = 1;
981
            }
982
            break;
983
          }
984
        }
985
        if (!found) nf->n.metric1 = LSINFINITY; /* Delete it */
986
      }
987

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

    
991
      ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
992
      if (nf->n.metric1 < LSINFINITY)
993
      {
994
        e = rte_get_temp(&a0);
995
        e->u.ospf.metric1 = nf->n.metric1;
996
        e->u.ospf.metric2 = nf->n.metric2;
997
        e->u.ospf.tag = nf->n.tag;
998
        e->pflags = 0;
999
        e->net = ne;
1000
        e->pref = p->preference;
1001
        DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n",
1002
          a0.source, nf->fn.prefix, nf->fn.pxlen, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1);
1003
        rte_update(p->table, ne, p, e);
1004
      }
1005
      else
1006
      {
1007
        rte_update(p->table, ne, p, NULL);
1008
        FIB_ITERATE_PUT(&fit, nftmp);
1009
        fib_delete(fib, nftmp);
1010
        goto again1;
1011
      }
1012
    }
1013
  }
1014
  FIB_ITERATE_END(nftmp);
1015

    
1016
  WALK_LIST(oa, po->area_list)
1017
  {
1018
    FIB_ITERATE_INIT(&fit, &oa->rtr);
1019
again2:
1020
    FIB_ITERATE_START(&oa->rtr, &fit, nftmp)
1021
    {
1022
      nf = (ort *) nftmp;
1023
      if (memcmp(&nf->n, &nf->o, sizeof(orta)))
1024
      {                                /* Some difference */
1025
        check_sum_lsa(po, nf, ORT_ROUTER);
1026
        if(nf->n.metric1 >= LSINFINITY)
1027
        {
1028
          FIB_ITERATE_PUT(&fit, nftmp);
1029
          fib_delete(&oa->rtr, nftmp);
1030
          goto again2;
1031
        }
1032
      }
1033
    }
1034
    FIB_ITERATE_END(nftmp);
1035

    
1036
    /* Check condensed summary LSAs */
1037
    FIB_WALK(&oa->net_fib, nftmp)
1038
    {
1039
      flush = 1;
1040
      anet = (struct area_net *) nftmp;
1041
      if((!anet->hidden) && anet->active)
1042
        flush = 0;
1043
          
1044
      WALK_LIST(oaa, po->area_list)
1045
      {
1046
        int fl = flush;
1047

    
1048
        if (oaa == oa) continue;
1049

    
1050
        if ((oa == po->backbone) && oaa->trcap) fl = 1;
1051

    
1052
        if(fl) flush_sum_lsa(oaa, &anet->fn, ORT_NET);
1053
        else originate_sum_lsa(oaa, &anet->fn, ORT_NET, anet->metric);
1054
      }
1055
    }
1056
    FIB_WALK_END;
1057
  }
1058
}