Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (12.1 KB)

1
/*
2
 *        BIRD -- OSPF
3
 *
4
 *        (c) 2000 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
#define LOCAL_DEBUG
12

    
13
void
14
init_infib(struct fib_node *fn)
15
{
16
  struct infib *f=(struct infib *)fn;
17

    
18
  f->metric=LSINFINITY;
19
  f->en=NULL;
20
}
21

    
22
void
23
init_efib(struct fib_node *fn)
24
{
25
  struct extfib *f=(struct extfib *)fn;
26

    
27
  f->metric=LSINFINITY;
28
  f->metric2=LSINFINITY;
29
  f->nh=ipa_from_u32(0);
30
  f->nhi=NULL;
31
}
32

    
33
void
34
ospf_rt_spfa(struct ospf_area *oa)
35
{
36
  struct top_hash_entry *en;
37
  u32 i,*rts;
38
  struct ospf_lsa_rt *rt;
39
  struct ospf_lsa_rt_link *rtl,*rr;
40
  struct fib *in=&oa->infib;
41
  struct infib *nf;
42
  struct fib_iterator fit;
43
  bird_clock_t delta;
44
  int age=0,flush=0;
45
  struct proto *p=&oa->po->proto;
46
  struct proto_ospf *po=oa->po;
47
  ip_addr ip;
48
  struct ospf_lsa_net *ln;
49

    
50
  debug("%s: Starting routing table calculation for area %I\n",p->name,
51
    oa->areaid);
52

    
53
  if(oa->rt==NULL) return;
54

    
55
  WALK_SLIST(SNODE en, oa->lsal)
56
  {
57
    en->color=OUTSPF;
58
    en->dist=LSINFINITY;
59
    en->nhi=NULL;
60
  }
61

    
62
  FIB_WALK(in,nftmp)
63
  {
64
    nf=(struct infib *)nftmp;
65
    nf->metric=LSINFINITY;
66
  }
67
  FIB_WALK_END;
68

    
69
  init_list(&oa->cand);                /* Empty list of candidates */
70
  oa->trcap=0;
71

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

    
74
  oa->rt->dist=0;
75
  oa->rt->color=CANDIDATE;
76
  add_head(&oa->cand, &oa->rt->cn);
77
  DBG("RT LSA: rt: %I, id: %I, type: %u\n",oa->rt->lsa.rt,oa->rt->lsa.id,oa->rt->lsa.type);
78

    
79
  while(!EMPTY_LIST(oa->cand))
80
  {
81
    struct top_hash_entry *act,*tmp;
82
    node *n;
83
    u16 met;
84

    
85
    n=HEAD(oa->cand);
86
    act=SKIP_BACK(struct top_hash_entry, cn, n);
87
    rem_node(n);
88

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

    
91
    act->color=INSPF;
92
    switch(act->lsa.type)
93
    {
94
      case LSA_T_RT:
95
        rt=(struct ospf_lsa_rt *)act->lsa_body;
96
        if((rt->VEB)&(1>>LSA_RT_V)) oa->trcap=1;
97
        rr=(struct ospf_lsa_rt_link *)(rt+1);
98
        DBG("  Number of links: %u\n",rt->links);
99
        for(i=0;i<rt->links;i++)
100
        {
101
          tmp=NULL;
102
          rtl=(rr+i);
103
          DBG("     Working on link: %I (type: %u)  ",rtl->id,rtl->type);
104
          switch(rtl->type)
105
          {
106
            case LSART_STUB:
107
             DBG("\n");
108
             ip=ipa_from_u32(rtl->id);
109
             nf=fib_get(in,&ip, ipa_mklen(ipa_from_u32(rtl->data)));
110
             if(nf->metric>(met=act->dist+rtl->metric))
111
             {
112
               nf->metric=met;
113
               nf->en=act;
114
             }
115
             break;
116
            case LSART_VLNK:
117
              DBG("Ignoring\n");
118
              continue;
119
              break;
120
            case LSART_NET:
121
              tmp=ospf_hash_find(oa->gr,rtl->id,rtl->id,LSA_T_NET);
122
              if(tmp==NULL) DBG("Fuck!\n");
123
              else DBG("Found. :-)\n");
124
              break;
125
            case LSART_PTP:
126
              tmp=ospf_hash_find(oa->gr,rtl->id,rtl->id,LSA_T_RT);
127
              DBG("PTP searched.\n");
128
              break;
129
            default:
130
              log("Unknown link type in router lsa.");
131
              break;
132
          }
133
          add_cand(&oa->cand,tmp,act,act->dist+rtl->metric,oa);
134
        }
135
        break;
136
      case LSA_T_NET:        /* FIXME Add to fib */
137
        ln=act->lsa_body;
138
        ip=ipa_and(ipa_from_u32(act->lsa.id),ln->netmask);
139
        nf=fib_get(in,&ip, ipa_mklen(ln->netmask));
140
        if(nf->metric>act->dist)
141
        {
142
          nf->metric=act->dist;
143
          nf->en=act;
144
        }
145

    
146
        rts=(u32 *)(ln+1);
147
        for(i=0;i<(act->lsa.length-sizeof(struct ospf_lsa_header)-
148
          sizeof(struct ospf_lsa_net))/sizeof(u32);i++)
149
        {
150
          DBG("     Working on router %I ",*(rts+i));
151
          tmp=ospf_hash_find(oa->gr, *(rts+i), *(rts+i), LSA_T_RT);
152
          if(tmp!=NULL) DBG("Found :-)\n");
153
          else DBG("Fuck!\n");
154
          add_cand(&oa->cand,tmp,act,act->dist,oa);
155
        }
156
        break;
157
    }
158
  }
159
  /* Now sync our fib with nest's */
160
  DBG("\nNow syncing my rt table with nest's\n\n");
161
  FIB_ITERATE_INIT(&fit,in);
162
again:
163
  FIB_ITERATE_START(in,&fit,nftmp)
164
  {
165
    nf=(struct infib *)nftmp;
166
    if(nf->metric==LSINFINITY) 
167
    {
168
      net *ne;
169
      struct top_hash_entry *en=nf->en;
170
      ln=en->lsa_body;
171
  
172
      ne=net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
173
      DBG("Deleting rt entry %I\n     (IP: %I, GW: %I, Iface: %s)\n",
174
        nf->fn.prefix,ip,en->nh,en->nhi->name);
175
      rte_update(p->table, ne, p, NULL);
176

    
177
      /* Now delete my fib */
178
      FIB_ITERATE_PUT(&fit, nftmp);
179
      fib_delete(in, nftmp);
180
      goto again;
181
    }
182
    else
183
    {
184
      /* Update routing table */
185
      if(nf->en->nhi==NULL)
186
      {
187
        struct top_hash_entry *en=nf->en;
188
        struct ospf_neighbor *neigh;
189
        neighbor *nn;
190

    
191
        if((neigh=find_neigh_noifa(po,en->lsa.rt))==NULL)
192
        {
193
          goto skip;
194
        }
195
        nn=neigh_find(p,&neigh->ip,0);
196
        DBG("     Next hop calculated: %I\n", nn->addr);
197
        en->nh=nn->addr;
198
        en->nhi=nn->iface;
199
      }
200

    
201
      {
202
        net *ne;
203
        rta a0;
204
        rte *e;
205
        struct top_hash_entry *en=nf->en;
206
        ln=en->lsa_body;
207
  
208
        bzero(&a0, sizeof(a0));
209
  
210
        a0.proto=p;
211
        a0.source=RTS_OSPF;
212
        a0.scope=SCOPE_UNIVERSE;        /* What's this good for? */
213
        a0.cast=RTC_UNICAST;
214
        a0.dest=RTD_ROUTER;
215
        a0.flags=0;
216
        a0.aflags=0;
217
        a0.iface=en->nhi;
218
        a0.gw=en->nh;
219
        a0.from=en->nh;                /* FIXME Just a test */
220
        ne=net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
221
        e=rte_get_temp(&a0);
222
        e->u.ospf.metric1=nf->metric;
223
        e->u.ospf.metric2=LSINFINITY;
224
        e->u.ospf.tag=0;                        /* FIXME Some config? */
225
        e->pflags = 0;
226
        e->net=ne;
227
        e->pref = p->preference;
228
        DBG("Modifying rt entry %I\n     (IP: %I, GW: %I, Iface: %s)\n",
229
          nf->fn.prefix,ip,en->nh,en->nhi->name);
230
        rte_update(p->table, ne, p, e);
231
      }
232
    }
233

    
234
  }
235
skip:
236
  FIB_ITERATE_END(nftmp);
237
  ospf_ext_spfa(po);
238
}
239

    
240
void
241
ospf_ext_spfa(struct proto_ospf *po)        /* FIXME looking into inter-area */
242
{
243
  struct top_hash_entry *en,*etmp,*absr;
244
  struct fib *ef=&po->efib;
245
  struct extfib *nf;
246
  struct fib_iterator fit;
247
  struct ospf_area *oa=NULL,*atmp,*absroa;
248
  struct proto *p=&po->proto;
249
  struct ospf_lsa_ext *le;
250
  struct ospf_lsa_ext_tos *lt;
251
  int mlen;
252
  ip_addr ip,nnh;
253
  struct iface *nnhi=NULL;
254
  u16 met,met2;
255
  u32 tag;
256
  neighbor *nn;
257

    
258
  debug("%s: Starting routing table calculation for external routes\n",
259
    p->name);
260

    
261
  FIB_WALK(ef,nftmp)
262
  {
263
    nf=(struct extfib *)nftmp;
264
    nf->metric=LSINFINITY;
265
    nf->metric2=LSINFINITY;
266
  }
267
  FIB_WALK_END;
268

    
269
  WALK_LIST(oa,po->area_list)
270
  {
271
    if(!oa->stub) break;
272
  }
273

    
274
  if(oa==NULL) return;
275

    
276
  WALK_SLIST(en,oa->lsal)
277
  {
278
    if(en->lsa.type!=LSA_T_EXT) continue;
279
    if(en->lsa.age==LSA_MAXAGE) continue;
280
    if(en->lsa.rt==p->cf->global->router_id) continue;
281

    
282
    le=en->lsa_body;
283
    lt=(struct ospf_lsa_ext_tos *)(le+1);
284

    
285
    if(lt->metric==LSINFINITY) continue;
286
    ip=ipa_and(ipa_from_u32(en->lsa.id),le->netmask);
287
    mlen=ipa_mklen(le->netmask);
288
    if((mlen<0)||(mlen>32))
289
    {
290
      log("%s: Invalid mask in LSA. ID: %I, RT: %I, Type: %u, Mask %I",
291
        p->name,en->lsa.id,en->lsa.rt,en->lsa.type,le->netmask);
292
      continue;
293
    }
294

    
295
    nf=NULL;
296

    
297
    WALK_LIST(atmp,po->area_list)
298
    {
299
      if((nf=fib_find(&atmp->infib,&ip, mlen))!=NULL) break;
300
    }
301

    
302
    if(nf!=NULL) continue;        /* Some intra area path exists */
303
    
304
    absr=NULL;
305
    absroa=NULL;
306
    nnhi=NULL;
307

    
308
    met=0;met2=0;tag=0;
309

    
310
    WALK_LIST(atmp,po->area_list)
311
    {
312
      if((etmp=ospf_hash_find(atmp->gr,en->lsa.rt,en->lsa.rt,LSA_T_RT))!=NULL)
313
      {
314
        if((absr==NULL) || (absr->dist>etmp->dist) ||
315
          ((etmp->dist==absr->dist) && (absroa->areaid<atmp->areaid)))
316
        {
317
          absr=etmp;
318
          absroa=atmp;
319
          break;
320
        }
321
      }
322
    }
323
    if((absr==NULL)||(absr->dist==LSINFINITY)) continue;
324

    
325
    if(ipa_compare(lt->fwaddr,ipa_from_u32(0))==0)
326
    {
327
      if(lt->etos>0)
328
      {
329
        met=absr->dist;
330
        met2=lt->metric;
331
      }
332
      else
333
      {
334
        met=absr->dist+lt->metric;
335
        met2=LSINFINITY;
336
      }
337
      tag=lt->tag;
338
    }
339
    else
340
    {
341
      nf=NULL;
342
      WALK_LIST(atmp,po->area_list)
343
      {
344
        if((nf=fib_route(&atmp->infib,lt->fwaddr,32))!=NULL)
345
        {
346
          break;
347
        }
348
      }
349
      if(nf==NULL) continue;
350
      if(lt->etos>0)
351
      {
352
        met=nf->metric;
353
        met2=lt->metric;
354
      }
355
      else
356
      {
357
        met=nf->metric+lt->metric;
358
        met2=LSINFINITY;
359
      }
360
      tag=lt->tag;
361

    
362
      if((nn=neigh_find(p,&lt->fwaddr,0))!=NULL)
363
      {
364
        nnh=nn->addr;
365
        nnhi=nn->iface;
366
      }
367
    }
368

    
369
    nf=fib_get(ef,&ip, mlen);
370
    if((nf->metric>met) || ((nf->metric==met)&&(nf->metric2>met2)))
371
    {
372
      nf->metric=met;
373
      nf->metric2=met2;
374
      nf->tag=tag;
375
      if(nnhi!=NULL)
376
      {
377
        nf->nh=nnh;
378
        nf->nhi=nnhi;
379
      }
380
      else
381
      {
382
        if(absr->nhi==NULL)
383
        {
384
          struct ospf_neighbor *neigh;
385

    
386
          if((neigh=find_neigh_noifa(po,absr->lsa.rt))==NULL)
387
          {
388
             continue;
389
          }
390
          nn=neigh_find(p,&neigh->ip,0);
391
          DBG("     Next hop calculated: %I\n", nn->addr);
392
          nf->nh=nn->addr;
393
          nf->nhi=nn->iface;
394
        }
395
        else
396
        {
397
          nf->nh=absr->nh;
398
          nf->nhi=absr->nhi;
399
        }
400
      }
401
    }
402
  }
403

    
404
  DBG("\nNow syncing my rt table with nest's\n\n");
405
  FIB_ITERATE_INIT(&fit,ef);
406
noch:
407
  FIB_ITERATE_START(ef,&fit,nftmp)
408
  {
409
    nf=(struct extfib *)nftmp;
410
    if(nf->metric==LSINFINITY) 
411
    {
412
      net *ne;
413
  
414
      ne=net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
415
      DBG("Deleting rt entry %I\n     (IP: %I, GW: %I)\n",
416
        nf->fn.prefix,ip,nf->nh);
417
      rte_update(p->table, ne, p, NULL);
418

    
419
      /* Now delete my fib */
420
      FIB_ITERATE_PUT(&fit, nftmp);
421
      fib_delete(ef, nftmp);
422
      goto noch;
423
    }
424
    else
425
    {
426
      net *ne;
427
      rta a0;
428
      rte *e;
429
  
430
      bzero(&a0, sizeof(a0));
431
  
432
      a0.proto=p;
433
      a0.source=RTS_OSPF_EXT;
434
      a0.scope=SCOPE_UNIVERSE;        /* What's this good for? */
435
      a0.cast=RTC_UNICAST;
436
      a0.dest=RTD_ROUTER;
437
      a0.flags=0;
438
      a0.aflags=0;
439
      a0.iface=nf->nhi;
440
      a0.gw=nf->nh;
441
      a0.from=nf->nh;                /* FIXME Just a test */
442
      ne=net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
443
      e=rte_get_temp(&a0);
444
      e->u.ospf.metric1=nf->metric;
445
      e->u.ospf.metric2=nf->metric2;
446
      e->u.ospf.tag=nf->tag;
447
      e->pflags = 0;
448
      e->net=ne;
449
      e->pref = p->preference;
450
      DBG("Modifying rt entry %I\n     (IP: %I, GW: %I)\n",
451
        nf->fn.prefix,ip,nf->nh);
452
      rte_update(p->table, ne, p, e);
453
    }
454
  }
455
let:
456
  FIB_ITERATE_END(nftmp);
457
}
458

    
459
void
460
add_cand(list *l, struct top_hash_entry *en, struct top_hash_entry *par, 
461
  u16 dist, struct ospf_area *oa)
462
{
463
  node *prev,*n;
464
  int flag=0,added=0;
465
  struct top_hash_entry *act;
466
  struct proto *p=&oa->po->proto;
467

    
468
  if(en==NULL) return;
469
  if(en->lsa.age==LSA_MAXAGE) return;
470
  /* FIXME Does it have link back? Test it! */
471
  if(en->color==INSPF) return;
472

    
473
  if(dist>=en->dist) return;
474
  /*
475
   * FIXME The line above is not a bug, but we don't support
476
   * multiple next hops. I'll start as soon as nest will
477
   */
478
  DBG("     Adding candidate: rt: %I, id: %I, type: %u\n",en->lsa.rt,en->lsa.id,en->lsa.type);
479

    
480
  en->nhi=NULL;
481
  
482
  calc_next_hop(par,en,oa);
483

    
484
  if(en->color==CANDIDATE)        /* We found a shorter path */
485
  {
486
    rem_node(&en->cn);
487
  }
488

    
489
  en->dist=dist;
490
  en->color=CANDIDATE;
491

    
492
  prev=NULL;
493

    
494
  if(EMPTY_LIST(*l))
495
  {
496
    add_head(l,&en->cn);
497
  }
498
  else
499
  {
500
    WALK_LIST(n,*l)
501
    {
502
      act=SKIP_BACK(struct top_hash_entry, cn, n);
503
      if((act->dist>dist)||
504
        ((act->dist==dist)&&(act->lsa.type==LSA_T_NET)))
505
      {
506
        if(prev==NULL) add_head(l,&en->cn);
507
        else insert_node(&en->cn,prev);
508
        added=1;
509
        break;
510
      }
511
      prev=n;
512
    }
513

    
514
    if(!added)
515
    {
516
      add_tail(l,&en->cn);
517
    }
518
  }
519
  /* FIXME Some VLINK staff should be here */
520
}
521

    
522
void
523
calc_next_hop(struct top_hash_entry *par, struct top_hash_entry *en,
524
  struct ospf_area *oa)
525
{
526
  struct ospf_neighbor *neigh;
527
  struct proto *p=&oa->po->proto;
528
  struct proto_ospf *po=oa->po;
529
  DBG("     Next hop called\n");
530
  if(par==oa->rt) return;
531
  if(par->nhi==NULL)
532
  {
533
    neighbor *nn;
534
    DBG("     Next hop calculating for id: %I rt: %I type: %u\n",en->lsa.id,en->lsa.rt,en->lsa.type);
535
    if(par->lsa.type!=LSA_T_RT) return;
536
    if((neigh=find_neigh_noifa(po,par->lsa.rt))==NULL) return;
537
    nn=neigh_find(p,&neigh->ip,0);
538
    DBG("     Next hop calculated: %I\n", nn->addr);
539
    en->nh=nn->addr;
540
    en->nhi=nn->iface;
541
    return;
542
  }
543
  en->nh=par->nh;
544
  en->nhi=par->nhi;
545
  DBG("     Next hop calculated: %I\n", en->nh);
546
}
547