Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / topology.c @ 7a42e6ce

History | View | Annotate | Download (12.7 KB)

1
/*
2
 *        BIRD -- OSPF Topological Database
3
 *
4
 *        (c) 1999        Martin Mares <mj@ucw.cz>
5
 *        (c) 1999 - 2000 Ondrej Filip <feela@network.cz>
6
 *
7
 *        Can be freely distributed and used under the terms of the GNU GPL.
8
 */
9

    
10
#include "nest/bird.h"
11
#include "lib/string.h"
12

    
13
#include "ospf.h"
14

    
15
#define HASH_DEF_ORDER 6                /* FIXME: Increase */
16
#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
void *
24
originate_rt_lsa_body(struct ospf_area *oa, u16 *length, struct proto_ospf *p)
25
{
26
  struct ospf_iface *ifa;
27
  int j=0,k=0,v=0,e=0,b=0;
28
  u16 i=0;
29
  struct ospf_lsa_rt *rt;
30
  struct ospf_lsa_rt_link *ln;
31
  struct ospf_neighbor *neigh;
32
  struct top_hash_entry *old;
33
  struct proto_ospf *po=(struct proto_ospf *)p;
34

    
35
  DBG("%s: Originating RT_lsa body for area \"%I\".\n", po->proto.name,
36
    oa->areaid);
37

    
38
  WALK_LIST (ifa, p->iface_list)
39
  {
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
  if((p->areano>1) && (!oa->stub)) e=1;
49
  rt->VEB=(v>>LSA_RT_V)+(e>>LSA_RT_E)+(b>>LSA_RT_B);
50
  ln=(struct ospf_lsa_rt_link *)(rt+1);
51

    
52
  WALK_LIST (ifa, p->iface_list)
53
  {
54
    if((ifa->an==oa->areaid) && (ifa->state!=OSPF_IS_DOWN))
55
    {
56
      if(ifa->state==OSPF_IS_LOOP)
57
      {
58
        ln->type=3;
59
        ln->id=ipa_to_u32(ifa->iface->addr->ip);
60
        ln->data=0xffffffff;
61
        ln->metric=0;
62
        ln->notos=0;
63
      }
64
      else
65
      {
66
        switch(ifa->type)
67
        {
68
          case OSPF_IT_PTP:                /* rfc2328 - pg126 */
69
            neigh=(struct ospf_neighbor *)HEAD(ifa->neigh_list);
70
            if((neigh!=NULL) || (neigh->state==NEIGHBOR_FULL))
71
            {
72
               ln->type=LSART_PTP;
73
               ln->id=neigh->rid;
74
               ln->metric=ifa->cost;
75
               ln->notos=0;
76
               if(ifa->iface->flags && IA_UNNUMBERED)
77
               {
78
                 ln->data=ifa->iface->index;
79
               }
80
               else
81
               {
82
                 ln->id=ipa_to_u32(ifa->iface->addr->ip);
83
               }
84
            }
85
            else
86
            {
87
              if(ifa->state==OSPF_IS_PTP)
88
              {
89
                ln->type=LSART_STUB;
90
                ln->id=ln->id=ipa_to_u32(ifa->iface->addr->opposite);
91
                ln->metric=ifa->cost;
92
                ln->notos=0;
93
                ln->data=0xffffffff;
94
              }
95
              else
96
              {
97
                i--; /* No link added */
98
              }
99
            }
100
            break;
101
          case OSPF_IT_BCAST: /*FIXME Go on */
102
          case OSPF_IT_NBMA:
103
            if(ifa->state==OSPF_IS_WAITING)
104
            {
105
              ln->type=LSART_STUB;
106
              ln->id=ipa_to_u32(ifa->iface->addr->prefix);
107
              ln->data=ipa_to_u32(ipa_mkmask(ifa->iface->addr->pxlen));
108
              ln->metric=ifa->cost;
109
              ln->notos=0;
110
            }
111
            else
112
            {
113
              j=0,k=0;
114
              WALK_LIST(neigh, ifa->neigh_list)
115
              {
116
                if((neigh->rid==ifa->drid) &&
117
                  (neigh->state==NEIGHBOR_FULL)) k=1;
118
                if(neigh->state==NEIGHBOR_FULL) j=1;
119
              }
120
              if(((ifa->state==OSPF_IS_DR) && (j==1)) || (k==1))
121
              {
122
                ln->type=LSART_NET;
123
                ln->id=ipa_to_u32(ifa->drip);
124
                ln->data=ipa_to_u32(ifa->iface->addr->ip);
125
                ln->metric=ifa->cost;
126
                ln->notos=0;
127
              }
128
              else
129
              {
130
                ln->type=LSART_STUB;
131
                  ln->id=ipa_to_u32(ifa->iface->addr->prefix);
132
                ln->data=ipa_to_u32(ipa_mkmask(ifa->iface->addr->pxlen));
133
                ln->metric=ifa->cost;
134
                ln->notos=0;
135
              }
136
            }
137
            break;
138
          case OSPF_IT_VLINK:        /* FIXME Add virtual links! */
139
            i--;
140
            break;
141
        }
142
      }
143
      if(ifa->type==OSPF_IT_VLINK) v=1;
144
    }
145
    ln=(ln+1);
146
  }
147
  rt->links=i;
148
  *length=i*sizeof(struct ospf_lsa_rt_link)+sizeof(struct ospf_lsa_rt)+
149
    sizeof(struct ospf_lsa_header);
150
  return rt;
151
}
152

    
153
void
154
age_timer_hook(timer *timer)
155
{
156
  struct ospf_area *oa=timer->data;
157
  bird_clock_t delta;
158
  struct top_hash_entry *en,*nxt;
159
  int flush=0;
160

    
161
  flush=can_flush_lsa(oa);
162

    
163
  if((delta=now-oa->lage)>=AGINGDELTA)
164
  {
165
    WALK_SLIST_DELSAFE(en,nxt,oa->lsal) ospf_age(en,delta,flush,oa);
166
    oa->lage=now;
167
  }
168
}
169
        
170

    
171
void
172
addifa_rtlsa(struct ospf_iface *ifa)
173
{
174
  struct ospf_area *oa;
175
  struct proto_ospf *po=ifa->proto;
176
  u32 rtid;
177
  struct top_graph_rtlsa_link *li, *lih;
178

    
179
  rtid=po->proto.cf->global->router_id;
180
  DBG("%s: New OSPF area \"%d\" adding.\n", po->proto.name, ifa->an);
181
  oa=NULL;
182

    
183

    
184
  WALK_LIST(NODE oa,po->area_list)
185
  {
186
    if(oa->areaid==ifa->an) break;
187
  }
188

    
189
  if(EMPTY_LIST(po->area_list) || (oa->areaid!=ifa->an))        /* New area */
190
  {
191
    struct ospf_lsa_header *lsa;
192

    
193
    oa=mb_allocz(po->proto.pool, sizeof(struct ospf_area));
194
    add_tail(&po->area_list,NODE oa);
195
    oa->areaid=ifa->an;
196
    oa->gr=ospf_top_new(po);
197
    s_init_list(&(oa->lsal));
198
    oa->rt=NULL;
199
    oa->lage=now;
200
    oa->po=po;
201
    oa->age_timer=tm_new(po->proto.pool);
202
    oa->age_timer->data=oa;
203
    oa->age_timer->randomize=0;
204
    oa->age_timer->hook=age_timer_hook;
205
    oa->age_timer->recurrent=AGINGDELTA;
206
    tm_start(oa->age_timer,AGINGDELTA);
207
    fib_init(&oa->infib,po->proto.pool,sizeof(struct infib),16,init_infib);
208
            /* FIXME 16?? (Oh, sweet 16.... :-) */
209
    po->areano++;
210
    DBG("%s: New OSPF area \"%d\" added.\n", po->proto.name, ifa->an);
211
  }
212

    
213
  ifa->oa=oa;
214

    
215
  originate_rt_lsa(oa,po);
216
  DBG("RT LSA: rt: %I, id: %I, type: %u\n",oa->rt->lsa.rt,oa->rt->lsa.id,oa->rt->lsa.type);
217
  flood_lsa(NULL,NULL,&oa->rt->lsa,po,NULL,oa);
218
}
219

    
220
void
221
originate_rt_lsa(struct ospf_area *oa, struct proto_ospf *po)
222
{
223
  struct ospf_lsa_header lsa;
224
  u32 rtid=po->proto.cf->global->router_id;
225
  struct top_hash_entry *en;
226
  void *body;
227

    
228
  debug("%s: Originating RT_lsa for area \"%I\".\n",po->proto.name,oa->areaid);
229

    
230
  lsa.age=0;
231
  lsa.id=rtid;
232
  lsa.type=LSA_T_RT;
233
  lsa.rt=rtid;
234
  if(oa->rt==NULL)
235
  {
236
    lsa.sn=LSA_INITSEQNO;
237
  }
238
  else
239
  {
240
    lsa.sn=oa->rt->lsa.sn+1;
241
  }
242
  body=originate_rt_lsa_body(oa, &lsa.length, po);
243
  lsasum_calculate(&lsa,body,po);
244
  en=lsa_install_new(&lsa, body, oa, &po->proto);
245
  oa->rt=en;
246
  flood_lsa(NULL,NULL,&oa->rt->lsa,po,NULL,oa);
247
  {
248
    struct ospf_lsa_rt *rt=body;
249
    debug("Originated, size=%u, link=%u\n",lsa.length,rt->links);
250
  }
251
}
252

    
253
void *
254
originate_net_lsa_body(struct ospf_iface *ifa, u16 *length,
255
  struct proto_ospf *po)
256
{
257
  u16 i=1;
258
  struct ospf_neighbor *n;
259
  u32 *body;
260
  struct ospf_lsa_net *net;
261

    
262
  net=mb_alloc(po->proto.pool,sizeof(u32)*(ifa->fadj+1)+
263
    sizeof(struct ospf_lsa_net));
264
  net->netmask=ipa_mkmask(ifa->iface->addr->pxlen);
265

    
266
  body=(u32 *)(net+1);
267
  i=1;
268
  *body=po->proto.cf->global->router_id;
269
  WALK_LIST(n,ifa->neigh_list)
270
  {
271
    if(n->state==NEIGHBOR_FULL)
272
    {
273
      *(body+i)=n->rid;
274
      i++;
275
    }
276
  }
277
  *length=i*sizeof(u32)+sizeof(struct ospf_lsa_header)+
278
    sizeof(struct ospf_lsa_net);
279
  return net;
280
}
281

    
282
void
283
originate_net_lsa(struct ospf_iface *ifa, struct proto_ospf *po)
284
{
285
  struct ospf_lsa_header lsa;
286
  u32 rtid=po->proto.cf->global->router_id;
287
  struct top_hash_entry *en;
288
  void *body;
289

    
290

    
291
  if(ifa->state!=OSPF_IS_DR) return;
292

    
293
  debug("%s: Originating Net lsa for iface \"%s\".\n", po->proto.name,
294
    ifa->iface->name);
295

    
296
  if(ifa->fadj==0)
297
  {
298
    if(ifa->nlsa==NULL) return;
299

    
300
    lsa.sn+=1;
301
    lsa.age=LSA_MAXAGE;
302
    flood_lsa(NULL,NULL,&ifa->nlsa->lsa,po,NULL,ifa->oa);
303
    /* FIXME delete LSA */
304
    ifa->nlsa=NULL;
305
    return ;
306
  }
307

    
308
  lsa.age=0;
309
  lsa.id=rtid;
310
  lsa.type=LSA_T_NET;
311
  lsa.rt=rtid;
312
  if(ifa->nlsa==NULL)
313
  {
314
    lsa.sn=LSA_INITSEQNO;
315
  }
316
  else
317
  {
318
    lsa.sn+=1;
319
  }
320
  body=originate_net_lsa_body(ifa, &lsa.length, po);
321
  lsasum_calculate(&lsa,body,po);
322
  ifa->nlsa=lsa_install_new(&lsa, body, ifa->oa, &po->proto);
323
  flood_lsa(NULL,NULL,&ifa->nlsa->lsa,po,NULL,ifa->oa);
324
}
325

    
326
static void
327
ospf_top_ht_alloc(struct top_graph *f)
328
{
329
  f->hash_size = 1 << f->hash_order;
330
  f->hash_mask = f->hash_size - 1;
331
  if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
332
    f->hash_entries_max = ~0;
333
  else
334
    f->hash_entries_max = f->hash_size HASH_HI_MARK;
335
  if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
336
    f->hash_entries_min = 0;
337
  else
338
    f->hash_entries_min = f->hash_size HASH_LO_MARK;
339
  DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
340
      f->hash_order, f->hash_size, f->hash_entries_min, f->hash_entries_max);
341
  f->hash_table = mb_alloc(f->pool, f->hash_size * sizeof(struct top_hash_entry *));
342
  bzero(f->hash_table, f->hash_size * sizeof(struct top_hash_entry *));
343
}
344

    
345
static inline void
346
ospf_top_ht_free(struct top_hash_entry **h)
347
{
348
  mb_free(h);
349
}
350

    
351
static inline u32
352
ospf_top_hash_u32(u32 a)
353
{
354
  /* Shamelessly stolen from IP address hashing in ipv4.h */
355
  a ^= a >> 16;
356
  a ^= a << 10;
357
  return a;
358
}
359

    
360
static inline unsigned
361
ospf_top_hash(struct top_graph *f, u32 lsaid, u32 rtrid, u32 type)
362
{
363
#if 1        /* Dirty patch to make rt table calculation work. */
364
  return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32((type==2) ? lsaid : rtrid) + type) & f->hash_mask;
365
#else
366
  return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) + type) & f->hash_mask;
367
#endif
368
}
369

    
370
struct top_graph *
371
ospf_top_new(struct proto_ospf *p)
372
{
373
  struct top_graph *f;
374

    
375
  f = mb_allocz(p->proto.pool, sizeof(struct top_graph));
376
  f->pool = p->proto.pool;
377
  f->hash_slab = sl_new(f->pool, sizeof(struct top_hash_entry));
378
  f->hash_order = HASH_DEF_ORDER;
379
  ospf_top_ht_alloc(f);
380
  f->hash_entries = 0;
381
  f->hash_entries_min = 0;
382
  return f;
383
}
384

    
385
void
386
ospf_top_free(struct top_graph *f)
387
{
388
  rfree(f->hash_slab);
389
  ospf_top_ht_free(f->hash_table);
390
  mb_free(f);
391
}
392

    
393
static void
394
ospf_top_rehash(struct top_graph *f, int step)
395
{
396
  unsigned int oldn, oldh;
397
  struct top_hash_entry **n, **oldt, **newt, *e, *x;
398

    
399
  oldn = f->hash_size;
400
  oldt = f->hash_table;
401
  DBG("Re-hashing topology hash from order %d to %d\n", f->hash_order, f->hash_order+step);
402
  f->hash_order += step;
403
  ospf_top_ht_alloc(f);
404
  newt = f->hash_table;
405

    
406
  for(oldh=0; oldh < oldn; oldh++)
407
    {
408
      e = oldt[oldh];
409
      while (e)
410
        {
411
          x = e->next;
412
          n = newt + ospf_top_hash(f, e->lsa.id, e->lsa.rt, e->lsa.type);
413
          e->next = *n;
414
          *n = e;
415
          e = x;
416
        }
417
    }
418
  ospf_top_ht_free(oldt);
419
}
420

    
421
struct top_hash_entry *
422
ospf_hash_find_header(struct top_graph *f, struct ospf_lsa_header *h)
423
{
424
  return ospf_hash_find(f,h->id,h->rt,h->type);
425
}
426

    
427
struct top_hash_entry *
428
ospf_hash_get_header(struct top_graph *f, struct ospf_lsa_header *h)
429
{
430
  return ospf_hash_get(f,h->id,h->rt,h->type);
431
}
432

    
433
struct top_hash_entry *
434
ospf_hash_find(struct top_graph *f, u32 lsa, u32 rtr, u32 type)
435
{
436
  struct top_hash_entry *e = f->hash_table[ospf_top_hash(f, lsa, rtr, type)];
437

    
438
#if 1
439
  if(type==2 && lsa==rtr)
440
  {
441
    while (e && (e->lsa.id != lsa || e->lsa.type != 2 ))
442
      e = e->next;
443
  }
444
  else
445
  {
446
    while (e && (e->lsa.id != lsa || e->lsa.type != type || e->lsa.rt != rtr))
447
      e = e->next;
448
  }
449
#else
450
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type))
451
    e = e->next;
452
#endif
453
  return e;
454
}
455

    
456
struct top_hash_entry *
457
ospf_hash_get(struct top_graph *f, u32 lsa, u32 rtr, u32 type)
458
{
459
  struct top_hash_entry **ee = f->hash_table + ospf_top_hash(f, lsa, rtr, type);
460
  struct top_hash_entry *e = *ee;
461

    
462
  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type))
463
    e = e->next;
464
  if (e)
465
    return e;
466
  e = sl_alloc(f->hash_slab);
467
  e->lsa.id = lsa;
468
  e->lsa.rt = rtr;
469
  e->lsa.type = type;
470
  e->lsa_body = NULL;
471
  e->nhi=NULL;
472
  e->next=*ee;                /* MJ you forgot this :-) */
473
  *ee=e;
474
  if (f->hash_entries++ > f->hash_entries_max)
475
    ospf_top_rehash(f, HASH_HI_STEP);
476
  return e;
477
}
478

    
479
void
480
ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
481
{
482
  unsigned int h = ospf_top_hash(f, e->lsa.id, e->lsa.rt, e->lsa.type);
483
  struct top_hash_entry **ee = f->hash_table + h;
484

    
485
  while (*ee)
486
    {
487
      if (*ee == e)
488
        {
489
          *ee = e->next;
490
          sl_free(f->hash_slab, e);
491
          if (f->hash_entries-- < f->hash_entries_min)
492
            ospf_top_rehash(f, -HASH_LO_STEP);
493
          return;
494
        }
495
      ee = &((*ee)->next);
496
    }
497
  bug("ospf_hash_delete() called for invalid node");
498
}
499

    
500
void
501
ospf_top_dump(struct top_graph *f)
502
{
503
  unsigned int i;
504
  debug("Hash entries: %d\n", f->hash_entries);
505

    
506
  for(i=0; i<f->hash_size; i++)
507
    {
508
      struct top_hash_entry *e = f->hash_table[i];
509
      while (e)
510
        {
511
          debug("\t%1x %8I %8I %4u 0x%08x\n", e->lsa.type, e->lsa.id,
512
            e->lsa.rt, e->lsa.age, e->lsa.sn);
513
          e = e->next;
514
        }
515
    }
516
}
517

    
518
/* This is very uneficient, please don't call it often */
519

    
520
/* I should also test for every LSA if it's in some link state
521
 * retransmision list for every neighbor. I will not test it.
522
 * It can happen that I'll receive some strange ls ack's.
523
 */
524

    
525
int
526
can_flush_lsa(struct ospf_area *oa)
527
{
528
  struct ospf_iface *ifa;
529
  struct ospf_neighbor *n;
530
  struct proto_ospf *po=oa->po;
531

    
532
  WALK_LIST(ifa, iface_list)
533
  {
534
    if(ifa->oa==oa)
535
    {
536
      WALK_LIST(n, ifa->neigh_list)
537
      {
538
        if((n->state==NEIGHBOR_EXCHANGE)||(n->state==NEIGHBOR_LOADING))
539
        {
540
          return 0;
541
        }
542
      }
543
    }
544
  }
545

    
546
  return 1;
547
}