Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / topology.c @ e43ae633

History | View | Annotate | Download (16.2 KB)

1 6ba36f06 Martin Mares
/*
2
 *        BIRD -- OSPF Topological Database
3
 *
4 de30342f Ondrej Filip
 *        (c) 1999        Martin Mares <mj@ucw.cz>
5
 *        (c) 1999 - 2000 Ondrej Filip <feela@network.cz>
6 6ba36f06 Martin Mares
 *
7
 *        Can be freely distributed and used under the terms of the GNU GPL.
8
 */
9
10
#include "nest/bird.h"
11 221135d6 Martin Mares
#include "lib/string.h"
12 6ba36f06 Martin Mares
13
#include "ospf.h"
14
15 8d56febe Ondrej Filip
#define HASH_DEF_ORDER 6
16 6ba36f06 Martin Mares
#define HASH_HI_MARK *4
17
#define HASH_HI_STEP 2
18
#define HASH_HI_MAX 16
19
#define HASH_LO_MARK /5
20
#define HASH_LO_STEP 2
21
#define HASH_LO_MIN 8
22
23 d8852b36 Ondrej Filip
void *
24
originate_rt_lsa_body(struct ospf_area *oa, u16 *length, struct proto_ospf *p)
25 ce17d4c1 Ondrej Filip
{
26
  struct ospf_iface *ifa;
27 fdb19982 Ondrej Filip
  int j=0,k=0,v=0;
28 9f940976 Ondrej Filip
  u16 i=0;
29 ce17d4c1 Ondrej Filip
  struct ospf_lsa_rt *rt;
30
  struct ospf_lsa_rt_link *ln;
31
  struct ospf_neighbor *neigh;
32
  struct top_hash_entry *old;
33 d8852b36 Ondrej Filip
  struct proto_ospf *po=(struct proto_ospf *)p;
34 ce17d4c1 Ondrej Filip
35 9669362f Ondrej Filip
  DBG("%s: Originating RT_lsa body for area \"%I\".\n", po->proto.name,
36
    oa->areaid);
37 ce17d4c1 Ondrej Filip
38 9669362f Ondrej Filip
  WALK_LIST (ifa, p->iface_list)
39 ce17d4c1 Ondrej Filip
  {
40
    if((ifa->an==oa->areaid) && (ifa->state!=OSPF_IS_DOWN))
41
    {
42
      i++;
43
      if(ifa->type==OSPF_IT_VLINK) v=1;
44
    }
45
  }
46
  rt=mb_allocz(p->proto.pool, sizeof(struct ospf_lsa_rt)+
47
    i*sizeof(struct ospf_lsa_rt_link));
48 85062e8a Ondrej Filip
  if(p->areano>1) rt->veb.bit.b=1;
49 fdb19982 Ondrej Filip
  if((p->ebit)&&(!oa->stub)) rt->veb.bit.e=1;
50
  rt->veb.bit.v=v;
51 ce17d4c1 Ondrej Filip
  ln=(struct ospf_lsa_rt_link *)(rt+1);
52
53
  WALK_LIST (ifa, p->iface_list)
54
  {
55 3b580a23 Ondrej Filip
    if((ifa->an!=oa->areaid) || (ifa->state==OSPF_IS_DOWN)) continue;
56
57
    if(ifa->state==OSPF_IS_LOOP)
58 ce17d4c1 Ondrej Filip
    {
59 3b580a23 Ondrej Filip
      ln->type=3;
60
      ln->id=ipa_to_u32(ifa->iface->addr->ip);
61
      ln->data=0xffffffff;
62
      ln->metric=0;
63
      ln->notos=0;
64
    }
65
    else
66
    {
67
      switch(ifa->type)
68 ce17d4c1 Ondrej Filip
      {
69 3b580a23 Ondrej Filip
        case OSPF_IT_PTP:                /* rfc2328 - pg126 */
70
          neigh=(struct ospf_neighbor *)HEAD(ifa->neigh_list);
71
          if((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state==NEIGHBOR_FULL))
72
          {
73
             ln->type=LSART_PTP;
74
             ln->id=neigh->rid;
75
             ln->metric=ifa->cost;
76
             ln->notos=0;
77
             if(ifa->iface->flags && IA_UNNUMBERED)
78
             {
79
               ln->data=ifa->iface->index;
80
             }
81
             else
82
             {
83
               ln->id=ipa_to_u32(ifa->iface->addr->ip);
84
             }
85
          }
86
          else
87
          {
88
            if(ifa->state==OSPF_IS_PTP)
89 ce17d4c1 Ondrej Filip
            {
90
              ln->type=LSART_STUB;
91 3b580a23 Ondrej Filip
              ln->id=ln->id=ipa_to_u32(ifa->iface->addr->opposite);
92
              ln->metric=ifa->cost;
93
              ln->notos=0;
94
              ln->data=0xffffffff;
95
            }
96
            else
97
            {
98
              i--; /* No link added */
99
            }
100
          }
101
          break;
102
        case OSPF_IT_BCAST:
103
        case OSPF_IT_NBMA:
104
          if(ifa->state==OSPF_IS_WAITING)
105
          {
106
            ln->type=LSART_STUB;
107
            ln->id=ipa_to_u32(ifa->iface->addr->prefix);
108
            ln->data=ipa_to_u32(ipa_mkmask(ifa->iface->addr->pxlen));
109
            ln->metric=ifa->cost;
110
            ln->notos=0;
111
          }
112
          else
113
          {
114
            j=0,k=0;
115
            WALK_LIST(neigh, ifa->neigh_list)
116
            {
117
              if((neigh->rid==ifa->drid) &&
118
                (neigh->state==NEIGHBOR_FULL)) k=1;
119
              if(neigh->state==NEIGHBOR_FULL) j=1;
120
            }
121
            if(((ifa->state==OSPF_IS_DR) && (j==1)) || (k==1))
122
            {
123
              ln->type=LSART_NET;
124
              ln->id=ipa_to_u32(ifa->drip);
125
              ln->data=ipa_to_u32(ifa->iface->addr->ip);
126 ce17d4c1 Ondrej Filip
              ln->metric=ifa->cost;
127
              ln->notos=0;
128
            }
129 3b580a23 Ondrej Filip
            else
130 ce17d4c1 Ondrej Filip
            {
131 3b580a23 Ondrej Filip
              ln->type=LSART_STUB;
132
              ln->id=ipa_to_u32(ifa->iface->addr->prefix);
133
              ln->data=ipa_to_u32(ipa_mkmask(ifa->iface->addr->pxlen));
134
              ln->metric=ifa->cost;
135
              ln->notos=0;
136 ce17d4c1 Ondrej Filip
            }
137 3b580a23 Ondrej Filip
          }
138
          break;
139
        case OSPF_IT_VLINK:        /* FIXME Add virtual links! */
140
          i--;
141
          break;
142 ce17d4c1 Ondrej Filip
      }
143
    }
144 3b580a23 Ondrej Filip
    if(ifa->type==OSPF_IT_VLINK) v=1;
145 ce17d4c1 Ondrej Filip
    ln=(ln+1);
146
  }
147
  rt->links=i;
148 d8852b36 Ondrej Filip
  *length=i*sizeof(struct ospf_lsa_rt_link)+sizeof(struct ospf_lsa_rt)+
149
    sizeof(struct ospf_lsa_header);
150
  return rt;
151 ce17d4c1 Ondrej Filip
}
152 c45f48fb Ondrej Filip
153
void
154 ab56f6b1 Ondrej Filip
addifa_rtlsa(struct ospf_iface *ifa)
155
{
156
  struct ospf_area *oa;
157 c45f48fb Ondrej Filip
  struct proto_ospf *po=ifa->proto;
158 3b580a23 Ondrej Filip
  struct proto *p=&po->proto;
159 ab56f6b1 Ondrej Filip
160 8496b2e4 Ondrej Filip
161
  WALK_LIST(NODE oa,po->area_list)
162 ab56f6b1 Ondrej Filip
  {
163 30147b89 Ondrej Filip
    if(oa->areaid==ifa->an) break;
164 ab56f6b1 Ondrej Filip
  }
165 30147b89 Ondrej Filip
166 8496b2e4 Ondrej Filip
  if(EMPTY_LIST(po->area_list) || (oa->areaid!=ifa->an))        /* New area */
167 ab56f6b1 Ondrej Filip
  {
168 51cff78b Ondrej Filip
    bug("Cannot add any area to accepted Interface");
169 de30342f Ondrej Filip
  }
170 67cc9135 Ondrej Filip
  else ifa->oa=oa;
171 d8852b36 Ondrej Filip
}
172
173 7ab3ff6a Ondrej Filip
/**
174
 * originate_rt_lsa - build new instance of router LSA
175
 * @oa: ospf_area which is LSA built to
176
 *
177
 * It builds router LSA walking through all OSPF interfaces in
178
 * specified OSPF area. This function is mostly called from
179
 * area_disp(). Builds new LSA, increases sequence number (if old
180
 * instance exists) and sets age of LSA to zero.
181
 */
182 9bc1808a Ondrej Filip
void
183 70a38319 Ondrej Filip
originate_rt_lsa(struct ospf_area *oa)
184 d8852b36 Ondrej Filip
{
185
  struct ospf_lsa_header lsa;
186 70a38319 Ondrej Filip
  struct proto_ospf *po=oa->po;
187 992705f6 Ondrej Filip
  struct proto *p=&po->proto;
188 d8852b36 Ondrej Filip
  u32 rtid=po->proto.cf->global->router_id;
189
  struct top_hash_entry *en;
190
  void *body;
191
192 78e2c6cc Ondrej Filip
  if((oa->rt)&&((oa->rt->inst_t+MINLSINTERVAL))>now) return;
193
        /*
194
         * Tick is probably set to very low value. We cannot
195
         * originate new LSA before MINLSINTERVAL. We will
196
         * try to do it next tick.
197
         */
198
199 992705f6 Ondrej Filip
  OSPF_TRACE(D_EVENTS, "Originating RT_lsa for area \"%I\".",oa->areaid);
200 d8852b36 Ondrej Filip
201
  lsa.age=0;
202
  lsa.id=rtid;
203
  lsa.type=LSA_T_RT;
204
  lsa.rt=rtid;
205 3dd8f983 Ondrej Filip
  lsa.options=0;
206 d8852b36 Ondrej Filip
  if(oa->rt==NULL)
207
  {
208
    lsa.sn=LSA_INITSEQNO;
209
  }
210
  else
211
  {
212
    lsa.sn=oa->rt->lsa.sn+1;
213
  }
214
  body=originate_rt_lsa_body(oa, &lsa.length, po);
215
  lsasum_calculate(&lsa,body,po);
216 e9ab0b42 Ondrej Filip
  en=lsa_install_new(&lsa, body, oa);
217 9bc1808a Ondrej Filip
  oa->rt=en;
218 3dd8f983 Ondrej Filip
  flood_lsa(NULL,NULL,&oa->rt->lsa,po,NULL,oa,1);
219 273fd2c1 Ondrej Filip
  schedule_rtcalc(oa);
220 78e2c6cc Ondrej Filip
  oa->origrt=0;
221 ab56f6b1 Ondrej Filip
}
222
223 0bf2f203 Ondrej Filip
void *
224
originate_net_lsa_body(struct ospf_iface *ifa, u16 *length,
225
  struct proto_ospf *po)
226
{
227
  u16 i=1;
228
  struct ospf_neighbor *n;
229
  u32 *body;
230 d345cda5 Ondrej Filip
  struct ospf_lsa_net *net;
231 0bf2f203 Ondrej Filip
232 d345cda5 Ondrej Filip
  net=mb_alloc(po->proto.pool,sizeof(u32)*(ifa->fadj+1)+
233
    sizeof(struct ospf_lsa_net));
234
  net->netmask=ipa_mkmask(ifa->iface->addr->pxlen);
235
236
  body=(u32 *)(net+1);
237 0bf2f203 Ondrej Filip
  i=1;
238
  *body=po->proto.cf->global->router_id;
239
  WALK_LIST(n,ifa->neigh_list)
240
  {
241
    if(n->state==NEIGHBOR_FULL)
242
    {
243
      *(body+i)=n->rid;
244
      i++;
245
    }
246
  }
247 d345cda5 Ondrej Filip
  *length=i*sizeof(u32)+sizeof(struct ospf_lsa_header)+
248
    sizeof(struct ospf_lsa_net);
249
  return net;
250 0bf2f203 Ondrej Filip
}
251
252 7ab3ff6a Ondrej Filip
/**
253
 * originate_net_lsa - originates of deletes network LSA
254
 * @ifa: interface which is LSA originated for
255
 *
256
 * Interface counts number of adjacent neighbor. If this number is
257
 * lower then one or interface is not in state %OSPF_IS_DR it deletes
258
 * and premature ages instance of network LSA for specified interface.
259
 * In other case, new instance of network LSA is originated.
260
 */
261 9bc1808a Ondrej Filip
void
262 7ab3ff6a Ondrej Filip
originate_net_lsa(struct ospf_iface *ifa)
263 0bf2f203 Ondrej Filip
{
264 7ab3ff6a Ondrej Filip
  struct proto_ospf *po=ifa->proto;
265 0bf2f203 Ondrej Filip
  struct ospf_lsa_header lsa;
266
  u32 rtid=po->proto.cf->global->router_id;
267
  struct top_hash_entry *en;
268 992705f6 Ondrej Filip
  struct proto *p=&po->proto;
269 0bf2f203 Ondrej Filip
  void *body;
270
271 78e2c6cc Ondrej Filip
  if(ifa->nlsa&&((ifa->nlsa->inst_t+MINLSINTERVAL)>now)) return;
272
  /*
273
   * It's too early to originate new network LSA. We will
274
   * try to do it next tick
275
   */
276
277 992705f6 Ondrej Filip
  OSPF_TRACE(D_EVENTS, "Originating Net lsa for iface \"%s\".",
278 9669362f Ondrej Filip
    ifa->iface->name);
279 b29c620f Ondrej Filip
280 3dd8f983 Ondrej Filip
  if((ifa->state!=OSPF_IS_DR)||(ifa->fadj==0))
281 9bc1808a Ondrej Filip
  {
282
    if(ifa->nlsa==NULL) return;
283
284 7ab3ff6a Ondrej Filip
    OSPF_TRACE(D_EVENTS, "Deleting Net lsa for iface \"%s\".",
285
      ifa->iface->name);
286 3dd8f983 Ondrej Filip
    ifa->nlsa->lsa.sn+=1;
287
    ifa->nlsa->lsa.age=LSA_MAXAGE;
288
    flood_lsa(NULL,NULL,&ifa->nlsa->lsa,po,NULL,ifa->oa,0);
289 52893236 Ondrej Filip
    s_rem_node(SNODE ifa->nlsa);
290 3dd8f983 Ondrej Filip
    ospf_hash_delete(ifa->oa->gr, ifa->nlsa);
291 52893236 Ondrej Filip
    schedule_rtcalc(ifa->oa);
292 9bc1808a Ondrej Filip
    ifa->nlsa=NULL;
293
    return ;
294
  }
295
296 7ab3ff6a Ondrej Filip
  OSPF_TRACE(D_EVENTS, "Originating Net lsa for iface \"%s\".",
297
    ifa->iface->name);
298
299 0bf2f203 Ondrej Filip
  lsa.age=0;
300 3dd8f983 Ondrej Filip
  lsa.id=ipa_to_u32(ifa->iface->addr->ip);
301 0bf2f203 Ondrej Filip
  lsa.type=LSA_T_NET;
302
  lsa.rt=rtid;
303 3dd8f983 Ondrej Filip
  lsa.options=0;
304 0bf2f203 Ondrej Filip
  if(ifa->nlsa==NULL)
305
  {
306
    lsa.sn=LSA_INITSEQNO;
307
  }
308
  else
309
  {
310 3dd8f983 Ondrej Filip
    lsa.sn=ifa->nlsa->lsa.sn+1;
311 0bf2f203 Ondrej Filip
  }
312 3dd8f983 Ondrej Filip
313 0bf2f203 Ondrej Filip
  body=originate_net_lsa_body(ifa, &lsa.length, po);
314
  lsasum_calculate(&lsa,body,po);
315 e9ab0b42 Ondrej Filip
  ifa->nlsa=lsa_install_new(&lsa, body, ifa->oa);
316 3dd8f983 Ondrej Filip
  flood_lsa(NULL,NULL,&ifa->nlsa->lsa,po,NULL,ifa->oa,1);
317 78e2c6cc Ondrej Filip
  ifa->orignet=0;
318 0bf2f203 Ondrej Filip
}
319
320 5919c66e Martin Mares
static void *
321
originate_ext_lsa_body(net *n, rte *e, struct proto_ospf *po, struct ea_list *attrs)
322 e8085aba Ondrej Filip
{
323
  struct proto *p=&po->proto;
324
  struct ospf_lsa_ext *ext;
325
  struct ospf_lsa_ext_tos *et;
326
  neighbor *nn;
327 8441f179 Martin Mares
  u32 m1 = ea_get_int(attrs, EA_OSPF_METRIC1, LSINFINITY);
328
  u32 m2 = ea_get_int(attrs, EA_OSPF_METRIC2, 10000);
329 5919c66e Martin Mares
  u32 tag = ea_get_int(attrs, EA_OSPF_TAG, 0);
330 fc741dab Ondrej Filip
  int inas=0;
331 e8085aba Ondrej Filip
332
  ext=mb_alloc(p->pool,sizeof(struct ospf_lsa_ext)+
333
    sizeof(struct ospf_lsa_ext_tos));
334
  ext->netmask=ipa_mkmask(n->n.pxlen);
335
336
  et=(struct ospf_lsa_ext_tos *)(ext+1);
337 5919c66e Martin Mares
338 5a063efe Ondrej Filip
  if(m1!=LSINFINITY)
339
  {
340
    et->etos=0;
341
    et->metric=m1;
342
  }
343 e8085aba Ondrej Filip
  else
344 5a063efe Ondrej Filip
  {
345
    et->etos=0x80;
346
    et->metric=m2;
347
  }
348 e8085aba Ondrej Filip
  et->padding=0;
349 5919c66e Martin Mares
  et->tag=tag;
350 fc741dab Ondrej Filip
  if(ipa_compare(e->attrs->gw,ipa_from_u32(0))!=0)
351
  {
352 5a063efe Ondrej Filip
    if(find_iface((struct proto_ospf *)p, e->attrs->iface)!=NULL) inas=1;
353 fc741dab Ondrej Filip
  }
354
    
355
  if(!inas) et->fwaddr= ipa_from_u32(0);
356 e8085aba Ondrej Filip
  else et->fwaddr=e->attrs->gw;
357
  return ext;
358
}
359
360 7ab3ff6a Ondrej Filip
/**
361
 * originate_ext_lsa - new route recived from nest and filters
362
 * @n: network prefix and mask
363
 * @e: rte
364
 * @po: current instance of OSPF
365
 * @attrs: list of extended attributes
366
 *
367
 * If I receive message that new route is installed, I try to originate an
368
 * external LSA. LSA header of such LSA does not contain information about
369
 * prefix lenght, so if I have to originate multiple LSAs for route with
370
 * different prefixes I try to increment prefix id to find a "free" one.
371 fdb19982 Ondrej Filip
 *
372
 * The function also set flag ebit. If it's first time, the new router lsa
373
 * origination is necessary.
374 7ab3ff6a Ondrej Filip
 */
375 e8085aba Ondrej Filip
void
376 5919c66e Martin Mares
originate_ext_lsa(net *n, rte *e, struct proto_ospf *po, struct ea_list *attrs)
377 e8085aba Ondrej Filip
{
378
  struct ospf_lsa_header lsa;
379
  u32 rtid=po->proto.cf->global->router_id;
380
  struct top_hash_entry *en=NULL;
381
  void *body=NULL;
382 273fd2c1 Ondrej Filip
  struct proto *p=&po->proto;
383 67cc9135 Ondrej Filip
  struct ospf_area *oa;
384 273fd2c1 Ondrej Filip
  struct ospf_lsa_ext *ext1,*ext2;
385
  int i;
386 e8085aba Ondrej Filip
387 992705f6 Ondrej Filip
  OSPF_TRACE(D_EVENTS, "Originating Ext lsa for %I/%d.", n->n.prefix,
388 e8085aba Ondrej Filip
    n->n.pxlen);
389
390
  lsa.age=0;
391
  lsa.id=ipa_to_u32(n->n.prefix);
392
  lsa.type=LSA_T_EXT;
393
  lsa.rt=rtid;
394
  lsa.sn=LSA_INITSEQNO;
395 5919c66e Martin Mares
  body=originate_ext_lsa_body(n, e, po, attrs);
396 e8085aba Ondrej Filip
  lsa.length=sizeof(struct ospf_lsa_ext)+sizeof(struct ospf_lsa_ext_tos)+
397
    sizeof(struct ospf_lsa_header);
398 273fd2c1 Ondrej Filip
  ext1=body;
399
400
  oa=HEAD(po->area_list);
401
402
  for(i=0;i<MAXNETS;i++)
403
  {
404
    if((en=ospf_hash_find_header(oa->gr, &lsa))!=NULL)
405
    {
406
      ext2=en->lsa_body;
407
      if(ipa_compare(ext1->netmask,ext2->netmask)!=0) lsa.id++;
408
      else break;
409
    }
410
    else break;
411
  }
412
413
  if(i==MAXNETS)
414
  {
415
    log("%s: got more routes for one network then %d, ignoring",p->name,
416
      MAXNETS);
417
    mb_free(body);
418
    return;
419
  }
420 e8085aba Ondrej Filip
  lsasum_calculate(&lsa,body,po);
421 67cc9135 Ondrej Filip
  WALK_LIST(oa, po->area_list)
422 e8085aba Ondrej Filip
  {
423 e9ab0b42 Ondrej Filip
    en=lsa_install_new(&lsa, body, oa);
424 67cc9135 Ondrej Filip
    flood_lsa(NULL,NULL,&en->lsa,po,NULL,oa,1);
425
    body=originate_ext_lsa_body(n, e, po, attrs);
426 e8085aba Ondrej Filip
  }
427 67cc9135 Ondrej Filip
  mb_free(body);
428 fdb19982 Ondrej Filip
429
  if(po->ebit==0)
430
  {
431
    po->ebit=1;
432
    WALK_LIST(oa, po->area_list)
433
    {
434
      schedule_rt_lsa(oa);
435
    }
436
  }
437 e8085aba Ondrej Filip
}
438
439
440 6ba36f06 Martin Mares
static void
441
ospf_top_ht_alloc(struct top_graph *f)
442
{
443
  f->hash_size = 1 << f->hash_order;
444
  f->hash_mask = f->hash_size - 1;
445
  if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
446
    f->hash_entries_max = ~0;
447
  else
448
    f->hash_entries_max = f->hash_size HASH_HI_MARK;
449
  if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
450
    f->hash_entries_min = 0;
451
  else
452
    f->hash_entries_min = f->hash_size HASH_LO_MARK;
453
  DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
454
      f->hash_order, f->hash_size, f->hash_entries_min, f->hash_entries_max);
455
  f->hash_table = mb_alloc(f->pool, f->hash_size * sizeof(struct top_hash_entry *));
456
  bzero(f->hash_table, f->hash_size * sizeof(struct top_hash_entry *));
457
}
458
459
static inline void
460
ospf_top_ht_free(struct top_hash_entry **h)
461
{
462
  mb_free(h);
463
}
464
465
static inline u32
466
ospf_top_hash_u32(u32 a)
467
{
468
  /* Shamelessly stolen from IP address hashing in ipv4.h */
469
  a ^= a >> 16;
470
  a ^= a << 10;
471
  return a;
472
}
473
474
static inline unsigned
475
ospf_top_hash(struct top_graph *f, u32 lsaid, u32 rtrid, u32 type)
476
{
477 88048fb3 Ondrej Filip
#if 1        /* Dirty patch to make rt table calculation work. */
478
return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32((type==LSA_T_NET) ? lsaid : rtrid) + type) & f->hash_mask;
479
#else
480 6ba36f06 Martin Mares
  return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) + type) & f->hash_mask;
481 88048fb3 Ondrej Filip
#endif
482 6ba36f06 Martin Mares
}
483
484 7ab3ff6a Ondrej Filip
/**
485
 * ospf_top_new - allocated new topology database
486
 * @p: current instance of OSPF
487
 *
488
 * This dynamically hashed structure is often used for keeping LSAs. Mainly
489
 * its used in @ospf_area structute.
490
 */
491 6ba36f06 Martin Mares
struct top_graph *
492
ospf_top_new(struct proto_ospf *p)
493
{
494
  struct top_graph *f;
495
496
  f = mb_allocz(p->proto.pool, sizeof(struct top_graph));
497
  f->pool = p->proto.pool;
498
  f->hash_slab = sl_new(f->pool, sizeof(struct top_hash_entry));
499
  f->hash_order = HASH_DEF_ORDER;
500
  ospf_top_ht_alloc(f);
501
  f->hash_entries = 0;
502
  f->hash_entries_min = 0;
503
  return f;
504
}
505
506
void
507
ospf_top_free(struct top_graph *f)
508
{
509
  rfree(f->hash_slab);
510
  ospf_top_ht_free(f->hash_table);
511
  mb_free(f);
512
}
513
514
static void
515
ospf_top_rehash(struct top_graph *f, int step)
516
{
517
  unsigned int oldn, oldh;
518
  struct top_hash_entry **n, **oldt, **newt, *e, *x;
519
520
  oldn = f->hash_size;
521
  oldt = f->hash_table;
522
  DBG("Re-hashing topology hash from order %d to %d\n", f->hash_order, f->hash_order+step);
523
  f->hash_order += step;
524
  ospf_top_ht_alloc(f);
525
  newt = f->hash_table;
526
527
  for(oldh=0; oldh < oldn; oldh++)
528
    {
529
      e = oldt[oldh];
530
      while (e)
531
        {
532
          x = e->next;
533 ce17d4c1 Ondrej Filip
          n = newt + ospf_top_hash(f, e->lsa.id, e->lsa.rt, e->lsa.type);
534 6ba36f06 Martin Mares
          e->next = *n;
535
          *n = e;
536
          e = x;
537
        }
538
    }
539
  ospf_top_ht_free(oldt);
540
}
541
542
struct top_hash_entry *
543 921a93f2 Ondrej Filip
ospf_hash_find_header(struct top_graph *f, struct ospf_lsa_header *h)
544
{
545
  return ospf_hash_find(f,h->id,h->rt,h->type);
546
}
547 d8852b36 Ondrej Filip
548
struct top_hash_entry *
549
ospf_hash_get_header(struct top_graph *f, struct ospf_lsa_header *h)
550
{
551
  return ospf_hash_get(f,h->id,h->rt,h->type);
552
}
553
554 921a93f2 Ondrej Filip
struct top_hash_entry *
555 6ba36f06 Martin Mares
ospf_hash_find(struct top_graph *f, u32 lsa, u32 rtr, u32 type)
556
{
557
  struct top_hash_entry *e = f->hash_table[ospf_top_hash(f, lsa, rtr, type)];
558
559 88048fb3 Ondrej Filip
#if 1        /* Dirty patch to make rt table calculation work. */
560
  if(type==LSA_T_NET)
561
  {
562
    while (e && (e->lsa.id != lsa || e->lsa.type != LSA_T_NET ))
563
       e = e->next;
564
  }
565
  else
566
  {
567
     while (e && (e->lsa.id != lsa || e->lsa.type != type || e->lsa.rt != rtr))
568
       e = e->next;
569
  }
570
#else
571 ce17d4c1 Ondrej Filip
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type))
572 6ba36f06 Martin Mares
    e = e->next;
573 88048fb3 Ondrej Filip
#endif
574 6ba36f06 Martin Mares
  return e;
575
}
576
577
struct top_hash_entry *
578
ospf_hash_get(struct top_graph *f, u32 lsa, u32 rtr, u32 type)
579
{
580
  struct top_hash_entry **ee = f->hash_table + ospf_top_hash(f, lsa, rtr, type);
581
  struct top_hash_entry *e = *ee;
582
583 ce17d4c1 Ondrej Filip
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type))
584 6ba36f06 Martin Mares
    e = e->next;
585
  if (e)
586
    return e;
587
  e = sl_alloc(f->hash_slab);
588 ce17d4c1 Ondrej Filip
  e->lsa.id = lsa;
589
  e->lsa.rt = rtr;
590
  e->lsa.type = type;
591
  e->lsa_body = NULL;
592 c6c56264 Ondrej Filip
  e->nhi=NULL;
593 de30342f Ondrej Filip
  e->next=*ee;                /* MJ you forgot this :-) */
594
  *ee=e;
595 6ba36f06 Martin Mares
  if (f->hash_entries++ > f->hash_entries_max)
596
    ospf_top_rehash(f, HASH_HI_STEP);
597
  return e;
598
}
599
600
void
601
ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
602
{
603 ce17d4c1 Ondrej Filip
  unsigned int h = ospf_top_hash(f, e->lsa.id, e->lsa.rt, e->lsa.type);
604 6ba36f06 Martin Mares
  struct top_hash_entry **ee = f->hash_table + h;
605
606
  while (*ee)
607
    {
608
      if (*ee == e)
609
        {
610
          *ee = e->next;
611
          sl_free(f->hash_slab, e);
612
          if (f->hash_entries-- < f->hash_entries_min)
613
            ospf_top_rehash(f, -HASH_LO_STEP);
614
          return;
615
        }
616
      ee = &((*ee)->next);
617
    }
618
  bug("ospf_hash_delete() called for invalid node");
619
}
620
621
void
622 992705f6 Ondrej Filip
ospf_top_dump(struct top_graph *f, struct proto *p)
623 6ba36f06 Martin Mares
{
624
  unsigned int i;
625 992705f6 Ondrej Filip
  OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
626 6ba36f06 Martin Mares
627
  for(i=0; i<f->hash_size; i++)
628
    {
629
      struct top_hash_entry *e = f->hash_table[i];
630
      while (e)
631
        {
632 e43ae633 Martin Mares
          OSPF_TRACE(D_EVENTS, "\t%1x %-1I %-1I %4u 0x%08x",
633 992705f6 Ondrej Filip
            e->lsa.type, e->lsa.id,
634 3b8b1bd0 Ondrej Filip
            e->lsa.rt, e->lsa.age, e->lsa.sn);
635 6ba36f06 Martin Mares
          e = e->next;
636
        }
637
    }
638
}
639 de30342f Ondrej Filip
640 ad5453b5 Ondrej Filip
/* This is very uneficient, please don't call it often */
641
642
/* I should also test for every LSA if it's in some link state
643
 * retransmision list for every neighbor. I will not test it.
644
 * It can happen that I'll receive some strange ls ack's.
645
 */
646
647
int
648
can_flush_lsa(struct ospf_area *oa)
649
{
650
  struct ospf_iface *ifa;
651
  struct ospf_neighbor *n;
652
  struct proto_ospf *po=oa->po;
653
654
  WALK_LIST(ifa, iface_list)
655
  {
656
    if(ifa->oa==oa)
657
    {
658
      WALK_LIST(n, ifa->neigh_list)
659
      {
660 9e48d717 Ondrej Filip
        if((n->state==NEIGHBOR_EXCHANGE)||(n->state==NEIGHBOR_LOADING))
661 ad5453b5 Ondrej Filip
        {
662 9e48d717 Ondrej Filip
          return 0;
663 ad5453b5 Ondrej Filip
        }
664
      }
665
    }
666
  }
667
668 9e48d717 Ondrej Filip
  return 1;
669 ad5453b5 Ondrej Filip
}