Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (7.78 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
void
12
init_infib(struct fib_node *fn)
13
{
14
  struct infib *f=(struct infib *)fn;
15

    
16
  f->metric=LSINFINITY;
17
  f->en=NULL;
18
}
19

    
20
void
21
ospf_rt_spfa(struct ospf_area *oa)
22
{
23
  struct top_hash_entry *en, *nx;
24
  u32 i,*rts;
25
  struct ospf_lsa_rt *rt;
26
  struct ospf_lsa_rt_link *rtl,*rr;
27
  struct fib *in=&oa->infib;
28
  struct infib *nf;
29
  bird_clock_t delta;
30
  int age=0,flush=0;
31
  struct proto *p=&oa->po->proto;
32
  struct proto_ospf *po=oa->po;
33
  ip_addr ip;
34
  struct fib_iterator fit;
35
  struct ospf_lsa_net *ln;
36

    
37
  flush=can_flush_lsa(oa);
38

    
39
  if((delta=now-oa->lage)>=AGINGDELTA)
40
  {
41
     oa->lage=now;
42
     age=1;
43
  }
44

    
45
  WALK_SLIST_DELSAFE(SNODE en, nx, oa->lsal)
46
  {
47
    en->color=OUTSPF;
48
    en->dist=LSINFINITY;
49
    en->nhi=NULL;
50
    if(age) ospf_age(en,delta,flush,oa);
51
  }
52

    
53
  FIB_WALK(in,nftmp)
54
  {
55
    nf=(struct infib *)nftmp;
56
    nf->metric=LSINFINITY;
57
  }
58
  FIB_WALK_END;
59

    
60
  init_list(&oa->cand);                /* Empty list of candidates */
61
  oa->trcap=0;
62

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

    
65
  oa->rt->dist=0;
66
  oa->rt->color=CANDIDATE;
67
  add_head(&oa->cand, &oa->rt->cn);
68
  DBG("RT LSA: rt: %I, id: %I, type: %u\n",oa->rt->lsa.rt,oa->rt->lsa.id,oa->rt->lsa.type);
69

    
70
  while(!EMPTY_LIST(oa->cand))
71
  {
72
    struct top_hash_entry *act,*tmp;
73
    node *n;
74
    u16 met;
75

    
76
    n=HEAD(oa->cand);
77
    act=SKIP_BACK(struct top_hash_entry, cn, n);
78
    rem_node(n);
79

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

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

    
137
        rts=(u32 *)(ln+1);
138
        for(i=0;i<(act->lsa.length-sizeof(struct ospf_lsa_header)-
139
          sizeof(struct ospf_lsa_net))/sizeof(u32);i++)
140
        {
141
          DBG("     Working on router %I ",*(rts+i));
142
          tmp=ospf_hash_find(oa->gr, *(rts+i), *(rts+i), LSA_T_RT);
143
          if(tmp!=NULL) DBG("Found :-)\n");
144
          else DBG("Fuck!\n");
145
          add_cand(&oa->cand,tmp,act,act->dist,oa);
146
        }
147
        break;
148
    }
149
  }
150
  /* Now sync our fib with nest's */
151
  DBG("\nNow syncing my rt table with nest's\n\n");
152
  FIB_ITERATE_INIT(&fit,in);
153
again:
154
  FIB_ITERATE_START(in,&fit,nftmp)
155
  {
156
    nf=(struct infib *)nftmp;
157
    if(nf->metric==LSINFINITY) 
158
    {
159
      net *ne;
160
      rta a0;
161
      struct top_hash_entry *en=nf->en;
162
      ln=en->lsa_body;
163
  
164
      bzero(&a0, sizeof(a0));
165
  
166
      a0.proto=p;
167
      a0.source=RTS_OSPF;
168
      a0.scope=SCOPE_UNIVERSE;        /* What's this good for? */
169
      a0.cast=RTC_UNICAST;
170
      a0.dest=RTD_ROUTER;
171
      a0.flags=0;
172
      a0.aflags=0;
173
      a0.iface=en->nhi;
174
      a0.gw=en->nh;
175
      a0.from=en->nh;                /* FIXME Just a test */
176
      ne=net_get(p->table, nf->fn.prefix, nf->fn.pxlen);
177
      DBG("Deleting rt entry %I\n     (IP: %I, GW: %I, Iface: %s)\n",
178
        nf->fn.prefix,ip,en->nh,en->nhi->name);
179
      rte_update(p->table, ne, p, NULL);
180

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

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

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

    
238
  }
239
skip:
240
  FIB_ITERATE_END(nftmp);
241
}
242

    
243
void
244
ospf_ext_spfa(struct proto_ospf *po)
245
{
246
  struct top_hash_entry *en;
247

    
248
  /* FIXME Go on */
249
}
250

    
251
void
252
add_cand(list *l, struct top_hash_entry *en, struct top_hash_entry *par, 
253
  u16 dist, struct ospf_area *oa)
254
{
255
  node *prev,*n;
256
  int flag=0,added=0;
257
  struct top_hash_entry *act;
258
  struct proto *p=&oa->po->proto;
259

    
260
  if(en==NULL) return;
261
  if(en->lsa.age==LSA_MAXAGE) return;
262
  /* FIXME Does it have link back? Test it! */
263
  if(en->color==INSPF) return;
264

    
265
  if(dist>=en->dist) return;
266
  /*
267
   * FIXME The line above is not a bug, but we don't support
268
   * multiple next hops. I'll start as soon as nest will
269
   */
270
  DBG("     Adding candidate: rt: %I, id: %I, type: %u\n",en->lsa.rt,en->lsa.id,en->lsa.type);
271

    
272
  en->nhi=NULL;
273
  
274
  calc_next_hop(par,en,oa);
275

    
276
  if(en->color==CANDIDATE)        /* We found a shorter path */
277
  {
278
    rem_node(&en->cn);
279
  }
280

    
281
  en->dist=dist;
282
  en->color=CANDIDATE;
283

    
284
  prev=NULL;
285

    
286
  if(EMPTY_LIST(*l))
287
  {
288
    add_head(l,&en->cn);
289
  }
290
  else
291
  {
292
    WALK_LIST(n,*l)
293
    {
294
      act=SKIP_BACK(struct top_hash_entry, cn, n);
295
      if((act->dist>dist)||
296
        ((act->dist==dist)&&(act->lsa.type==LSA_T_NET)))
297
      {
298
        if(prev==NULL) add_head(l,&en->cn);
299
        else insert_node(&en->cn,prev);
300
        added=1;
301
        break;
302
      }
303
      prev=n;
304
    }
305

    
306
    if(!added)
307
    {
308
      add_tail(l,&en->cn);
309
    }
310
  }
311
  /* FIXME Some VLINK staff should be here */
312
}
313

    
314
void
315
calc_next_hop(struct top_hash_entry *par, struct top_hash_entry *en,
316
  struct ospf_area *oa)
317
{
318
  struct ospf_neighbor *neigh;
319
  struct proto *p=&oa->po->proto;
320
  struct proto_ospf *po=oa->po;
321
  DBG("     Next hop called\n");
322
  if(par==oa->rt) return;
323
  if(par->nhi==NULL)
324
  {
325
    neighbor *nn;
326
    DBG("     Next hop calculating for id: %I rt: %I type: %u\n",en->lsa.id,en->lsa.rt,en->lsa.type);
327
    if(par->lsa.type!=LSA_T_RT) return;
328
    if((neigh=find_neigh_noifa(po,par->lsa.rt))==NULL) return;
329
    nn=neigh_find(p,&neigh->ip,0);
330
    DBG("     Next hop calculated: %I\n", nn->addr);
331
    en->nh=nn->addr;
332
    en->nhi=nn->iface;
333
    return;
334
  }
335
  en->nh=par->nh;
336
  en->nhi=par->nhi;
337
  DBG("     Next hop calculated: %I\n", en->nh);
338
}
339