Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-attr.c @ ce1da96e

History | View | Annotate | Download (11.4 KB)

1
/*
2
 *        BIRD -- Route Attribute Cache
3
 *
4
 *        (c) 1998--2000 Martin Mares <mj@ucw.cz>
5
 *
6
 *        Can be freely distributed and used under the terms of the GNU GPL.
7
 */
8

    
9
#include <alloca.h>
10

    
11
#include "nest/bird.h"
12
#include "nest/route.h"
13
#include "nest/protocol.h"
14
#include "nest/iface.h"
15
#include "nest/cli.h"
16
#include "nest/attrs.h"
17
#include "lib/resource.h"
18
#include "lib/string.h"
19

    
20
static slab *rta_slab;
21
static pool *rta_pool;
22

    
23
struct protocol *attr_class_to_protocol[EAP_MAX];
24

    
25
/*
26
 *        Extended Attributes
27
 */
28

    
29
static inline eattr *
30
ea__find(ea_list *e, unsigned id)
31
{
32
  eattr *a;
33
  int l, r, m;
34

    
35
  while (e)
36
    {
37
      if (e->flags & EALF_BISECT)
38
        {
39
          l = 0;
40
          r = e->count + 1;
41
          while (l <= r)
42
            {
43
              m = (l+r) / 2;
44
              a = &e->attrs[m];
45
              if (a->id == id)
46
                return a;
47
              else if (a->id < id)
48
                l = m+1;
49
              else
50
                r = m-1;
51
            }
52
        }
53
      else
54
        for(m=0; m<e->count; m++)
55
          if (e->attrs[m].id == id)
56
            return &e->attrs[m];
57
      e = e->next;
58
    }
59
  return NULL;
60
}
61

    
62
eattr *
63
ea_find(ea_list *e, unsigned id)
64
{
65
  eattr *a = ea__find(e, id & EA_CODE_MASK);
66

    
67
  if (a && (a->type & EAF_TYPE_MASK) == EAF_TYPE_UNDEF &&
68
      !(id & EA_ALLOW_UNDEF))
69
    return NULL;
70
  return a;
71
}
72

    
73
static inline void
74
ea_do_sort(ea_list *e)
75
{
76
  unsigned n = e->count;
77
  eattr *a = e->attrs;
78
  eattr *b = alloca(n * sizeof(eattr));
79
  unsigned s, ss;
80

    
81
  /* We need to use a stable sorting algorithm, hence mergesort */
82
  do
83
    {
84
      s = ss = 0;
85
      while (s < n)
86
        {
87
          eattr *p, *q, *lo, *hi;
88
          p = b;
89
          ss = s;
90
          *p++ = a[s++];
91
          while (s < n && p[-1].id <= a[s].id)
92
            *p++ = a[s++];
93
          if (s < n)
94
            {
95
              q = p;
96
              *p++ = a[s++];
97
              while (s < n && p[-1].id <= a[s].id)
98
                *p++ = a[s++];
99
              lo = b;
100
              hi = q;
101
              s = ss;
102
              while (lo < q && hi < p)
103
                if (lo->id <= hi->id)
104
                  a[s++] = *lo++;
105
                else
106
                  a[s++] = *hi++;
107
              while (lo < q)
108
                a[s++] = *lo++;
109
              while (hi < p)
110
                a[s++] = *hi++;
111
            }
112
        }
113
    }
114
  while (ss);
115
}
116

    
117
static inline void
118
ea_do_prune(ea_list *e)
119
{
120
  eattr *s, *d, *l, *s0;
121
  int i = 0;
122

    
123
  /* Discard duplicates and undefs. Do you remember sorting was stable? */
124
  s = d = e->attrs;
125
  l = e->attrs + e->count;
126
  while (s < l)
127
    {
128
      s0 = s++;
129
      while (s < l && s->id == s[-1].id)
130
        s++;
131
      /* s0 is the most recent version, s[-1] the oldest one */
132
      if ((s0->type & EAF_TYPE_MASK) != EAF_TYPE_UNDEF)
133
        {
134
          *d = *s0;
135
          d->type = (d->type & ~EAF_ORIGINATED) | (s[-1].type & EAF_ORIGINATED);
136
          d++;
137
          i++;
138
        }
139
    }
140
  e->count = i;
141
}
142

    
143
void
144
ea_sort(ea_list *e)
145
{
146
  while (e)
147
    {
148
      if (!(e->flags & EALF_SORTED))
149
        {
150
          ea_do_sort(e);
151
          ea_do_prune(e);
152
          e->flags |= EALF_SORTED;
153
        }
154
      if (e->count > 5)
155
        e->flags |= EALF_BISECT;
156
      e = e->next;
157
    }
158
}
159

    
160
unsigned
161
ea_scan(ea_list *e)
162
{
163
  unsigned cnt = 0;
164

    
165
  while (e)
166
    {
167
      cnt += e->count;
168
      e = e->next;
169
    }
170
  return sizeof(ea_list) + sizeof(eattr)*cnt;
171
}
172

    
173
void
174
ea_merge(ea_list *e, ea_list *t)
175
{
176
  eattr *d = t->attrs;
177

    
178
  t->flags = 0;
179
  t->count = 0;
180
  t->next = NULL;
181
  while (e)
182
    {
183
      memcpy(d, e->attrs, sizeof(eattr)*e->count);
184
      t->count += e->count;
185
      d += e->count;
186
      e = e->next;
187
    }
188
}
189

    
190
int
191
ea_same(ea_list *x, ea_list *y)
192
{
193
  int c;
194

    
195
  if (!x || !y)
196
    return x == y;
197
  ASSERT(!x->next && !y->next);
198
  if (x->count != y->count)
199
    return 0;
200
  for(c=0; c<x->count; c++)
201
    {
202
      eattr *a = &x->attrs[c];
203
      eattr *b = &y->attrs[c];
204

    
205
      if (a->id != b->id ||
206
          a->flags != b->flags ||
207
          a->type != b->type ||
208
          ((a->type & EAF_EMBEDDED) ? a->u.data != b->u.data :
209
           (a->u.ptr->length != b->u.ptr->length || memcmp(a->u.ptr, b->u.ptr, a->u.ptr->length))))
210
        return 0;
211
    }
212
  return 1;
213
}
214

    
215
static inline ea_list *
216
ea_list_copy(ea_list *o)
217
{
218
  ea_list *n;
219
  unsigned i, len;
220

    
221
  if (!o)
222
    return NULL;
223
  ASSERT(!o->next);
224
  len = sizeof(ea_list) + sizeof(eattr) * o->count;
225
  n = mb_alloc(rta_pool, len);
226
  memcpy(n, o, len);
227
  n->flags |= EALF_CACHED;
228
  for(i=0; i<o->count; i++)
229
    {
230
      eattr *a = &n->attrs[i];
231
      if (!(a->type & EAF_EMBEDDED))
232
        {
233
          unsigned size = sizeof(struct adata) + a->u.ptr->length;
234
          struct adata *d = mb_alloc(rta_pool, size);
235
          memcpy(d, a->u.ptr, size);
236
          a->u.ptr = d;
237
        }
238
    }
239
  return n;
240
}
241

    
242
void
243
ea_format(eattr *e, byte *buf)
244
{
245
  struct protocol *p;
246
  int status = GA_UNKNOWN;
247
  unsigned int i;
248
  struct adata *ad = (e->type & EAF_EMBEDDED) ? NULL : e->u.ptr;
249
  byte *end = buf + EA_FORMAT_BUF_SIZE - 1;
250

    
251
  if (p = attr_class_to_protocol[EA_PROTO(e->id)])
252
    {
253
      buf += bsprintf(buf, "%s.", p->name);
254
      if (p->get_attr)
255
        status = p->get_attr(e, buf);
256
      buf += strlen(buf);
257
    }
258
  else if (EA_PROTO(e->id))
259
    buf += bsprintf(buf, "%02x.", EA_PROTO(e->id));
260
  if (status < GA_NAME)
261
    buf += bsprintf(buf, "%02x", EA_ID(e->id));
262
  if (status < GA_FULL)
263
    {
264
      *buf++ = ':';
265
      *buf++ = ' ';
266
      switch (e->type & EAF_TYPE_MASK)
267
        {
268
        case EAF_TYPE_INT:
269
          bsprintf(buf, "%d", e->u.data);
270
          break;
271
        case EAF_TYPE_OPAQUE:
272
          for(i=0; i<ad->length; i++)
273
            {
274
              if (buf > end - 8)
275
                {
276
                  strcpy(buf, " ...");
277
                  break;
278
                }
279
              if (i)
280
                *buf++ = ' ';
281
              buf += bsprintf(buf, "%02x", ad->data[i]);
282
            }
283
          break;
284
        case EAF_TYPE_IP_ADDRESS:
285
          bsprintf(buf, "%I", *(ip_addr *) ad->data);
286
          break;
287
        case EAF_TYPE_ROUTER_ID:
288
          bsprintf(buf, "%d.%d.%d.%d",
289
                   (e->u.data >> 24) & 0xff,
290
                   (e->u.data >> 16) & 0xff,
291
                   (e->u.data >> 8) & 0xff,
292
                   e->u.data & 0xff);
293
          break;
294
        case EAF_TYPE_AS_PATH:
295
          as_path_format(ad, buf, end - buf);
296
          break;
297
        case EAF_TYPE_INT_SET:
298
          int_set_format(ad, buf, end - buf);
299
          break;
300
        case EAF_TYPE_UNDEF:
301
        default:
302
          bsprintf(buf, "<type %02x>", e->type);
303
        }
304
    }
305
}
306

    
307
void
308
ea_dump(ea_list *e)
309
{
310
  int i;
311

    
312
  if (!e)
313
    {
314
      debug("NONE");
315
      return;
316
    }
317
  while (e)
318
    {
319
      debug("[%c%c%c]",
320
            (e->flags & EALF_SORTED) ? 'S' : 's',
321
            (e->flags & EALF_BISECT) ? 'B' : 'b',
322
            (e->flags & EALF_CACHED) ? 'C' : 'c');
323
      for(i=0; i<e->count; i++)
324
        {
325
          eattr *a = &e->attrs[i];
326
          debug(" %02x:%02x.%02x", EA_PROTO(a->id), EA_ID(a->id), a->flags);
327
          if (a->type & EAF_TEMP)
328
            debug("T");
329
          debug("=%c", "?iO?I?P???S?????" [a->type & EAF_TYPE_MASK]);
330
          if (a->type & EAF_ORIGINATED)
331
            debug("o");
332
          if (a->type & EAF_EMBEDDED)
333
            debug(":%08x", a->u.data);
334
          else
335
            {
336
              int j, len = a->u.ptr->length;
337
              debug("[%d]:", len);
338
              for(j=0; j<len; j++)
339
                debug("%02x", a->u.ptr->data[j]);
340
            }
341
        }
342
      if (e = e->next)
343
        debug(" | ");
344
    }
345
}
346

    
347
inline unsigned int
348
ea_hash(ea_list *e)
349
{
350
  u32 h = 0;
351
  int i;
352

    
353
  if (e)                        /* Assuming chain of length 1 */
354
    {
355
      for(i=0; i<e->count; i++)
356
        {
357
          struct eattr *a = &e->attrs[i];
358
          h ^= a->id;
359
          if (a->type & EAF_EMBEDDED)
360
            h ^= a->u.data;
361
          else
362
            {
363
              struct adata *d = a->u.ptr;
364
              int size = d->length;
365
              byte *z = d->data;
366
              while (size >= 4)
367
                {
368
                  h ^= *(u32 *)z;
369
                  z += 4;
370
                  size -= 4;
371
                }
372
              while (size--)
373
                h = (h >> 24) ^ (h << 8) ^ *z++;
374
            }
375
        }
376
      h ^= h >> 16;
377
      h ^= h >> 6;
378
      h &= 0xffff;
379
    }
380
  return h;
381
}
382

    
383
ea_list *
384
ea_append(ea_list *to, ea_list *what)
385
{
386
  ea_list *res;
387

    
388
  if (!to)
389
    return what;
390
  res = to;
391
  while (to->next)
392
    to = to->next;
393
  to->next = what;
394
  return res;
395
}
396

    
397
/*
398
 *        rta's
399
 */
400

    
401
static unsigned int rta_cache_count;
402
static unsigned int rta_cache_size = 32;
403
static unsigned int rta_cache_limit;
404
static unsigned int rta_cache_mask;
405
static rta **rta_hash_table;
406

    
407
static void
408
rta_alloc_hash(void)
409
{
410
  rta_hash_table = mb_alloc(rta_pool, sizeof(rta *) * rta_cache_size);
411
  bzero(rta_hash_table, sizeof(rta *) * rta_cache_size);
412
  if (rta_cache_size < 32768)
413
    rta_cache_limit = rta_cache_size * 2;
414
  else
415
    rta_cache_limit = ~0;
416
  rta_cache_mask = rta_cache_size - 1;
417
}
418

    
419
static inline unsigned int
420
rta_hash(rta *a)
421
{
422
  return a->proto->hash_key ^ ipa_hash(a->gw) ^ ea_hash(a->eattrs);
423
}
424

    
425
static inline int
426
rta_same(rta *x, rta *y)
427
{
428
  return (x->proto == y->proto &&
429
          x->source == y->source &&
430
          x->scope == y->scope &&
431
          x->cast == y->cast &&
432
          x->dest == y->dest &&
433
          x->flags == y->flags &&
434
          ipa_equal(x->gw, y->gw) &&
435
          ipa_equal(x->from, y->from) &&
436
          x->iface == y->iface &&
437
          ea_same(x->eattrs, y->eattrs));
438
}
439

    
440
static rta *
441
rta_copy(rta *o)
442
{
443
  rta *r = sl_alloc(rta_slab);
444

    
445
  memcpy(r, o, sizeof(rta));
446
  r->uc = 1;
447
  r->eattrs = ea_list_copy(o->eattrs);
448
  return r;
449
}
450

    
451
static inline void
452
rta_insert(rta *r)
453
{
454
  unsigned int h = r->hash_key & rta_cache_mask;
455
  r->next = rta_hash_table[h];
456
  if (r->next)
457
    r->next->pprev = &r->next;
458
  r->pprev = &rta_hash_table[h];
459
  rta_hash_table[h] = r;
460
}
461

    
462
static void
463
rta_rehash(void)
464
{
465
  unsigned int ohs = rta_cache_size;
466
  unsigned int h;
467
  rta *r, *n;
468
  rta **oht = rta_hash_table;
469

    
470
  rta_cache_size = 2*rta_cache_size;
471
  DBG("Rehashing rta cache from %d to %d entries.\n", ohs, rta_cache_size);
472
  rta_alloc_hash();
473
  for(h=0; h<ohs; h++)
474
    for(r=oht[h]; r; r=n)
475
      {
476
        n = r->next;
477
        rta_insert(r);
478
      }
479
  mb_free(oht);
480
}
481

    
482
rta *
483
rta_lookup(rta *o)
484
{
485
  rta *r;
486
  unsigned int h;
487

    
488
  ASSERT(!(o->aflags & RTAF_CACHED));
489
  if (o->eattrs)
490
    {
491
      if (o->eattrs->next)        /* Multiple ea_list's, need to merge them */
492
        {
493
          ea_list *ml = alloca(ea_scan(o->eattrs));
494
          ea_merge(o->eattrs, ml);
495
          o->eattrs = ml;
496
        }
497
      ea_sort(o->eattrs);
498
    }
499

    
500
  h = rta_hash(o);
501
  for(r=rta_hash_table[h & rta_cache_mask]; r; r=r->next)
502
    if (r->hash_key == h && rta_same(r, o))
503
      return rta_clone(r);
504

    
505
  r = rta_copy(o);
506
  r->hash_key = h;
507
  r->aflags = RTAF_CACHED;
508
  rta_insert(r);
509

    
510
  if (++rta_cache_count > rta_cache_limit)
511
    rta_rehash();
512

    
513
  return r;
514
}
515

    
516
void
517
rta__free(rta *a)
518
{
519
  ASSERT(rta_cache_count && (a->aflags & RTAF_CACHED));
520
  rta_cache_count--;
521
}
522

    
523
void
524
rta_dump(rta *a)
525
{
526
  static char *rts[] = { "RTS_DUMMY", "RTS_STATIC", "RTS_INHERIT", "RTS_DEVICE",
527
                         "RTS_STAT_DEV", "RTS_REDIR", "RTS_RIP",
528
                         "RTS_OSPF", "RTS_OSPF_EXT", "RTS_OSPF_IA",
529
                         "RTS_OSPF_BOUNDARY", "RTS_BGP" };
530
  static char *rtc[] = { "", " BC", " MC", " AC" };
531
  static char *rtd[] = { "", " DEV", " HOLE", " UNREACH", " PROHIBIT" };
532

    
533
  debug("p=%s uc=%d %s %s%s%s h=%04x",
534
        a->proto->name, a->uc, rts[a->source], ip_scope_text(a->scope), rtc[a->cast],
535
        rtd[a->dest], a->hash_key);
536
  if (!(a->aflags & RTAF_CACHED))
537
    debug(" !CACHED");
538
  debug(" <-%I", a->from);
539
  if (a->dest == RTD_ROUTER)
540
    debug(" ->%I", a->gw);
541
  if (a->dest == RTD_DEVICE || a->dest == RTD_ROUTER)
542
    debug(" [%s]", a->iface ? a->iface->name : "???" );
543
  if (a->eattrs)
544
    {
545
      debug(" EA: ");
546
      ea_dump(a->eattrs);
547
    }
548
}
549

    
550
void
551
rta_dump_all(void)
552
{
553
  rta *a;
554
  unsigned int h;
555

    
556
  debug("Route attribute cache (%d entries, rehash at %d):\n", rta_cache_count, rta_cache_limit);
557
  for(h=0; h<rta_cache_size; h++)
558
    for(a=rta_hash_table[h]; a; a=a->next)
559
      {
560
        debug("%p ", a);
561
        rta_dump(a);
562
        debug("\n");
563
      }
564
  debug("\n");
565
}
566

    
567
void
568
rta_show(struct cli *c, rta *a, ea_list *eal)
569
{
570
  static char *src_names[] = { "dummy", "static", "inherit", "device", "static-device", "redirect",
571
                               "RIP", "RIP-ext", "OSPF", "OSPF-ext", "OSPF-IA", "OSPF-boundary",
572
                               "BGP" };
573
  static char *cast_names[] = { "unicast", "broadcast", "multicast", "anycast" };
574
  int i;
575
  byte buf[EA_FORMAT_BUF_SIZE];
576

    
577
  cli_printf(c, -1008, "\tType: %s %s %s", src_names[a->source], cast_names[a->cast], ip_scope_text(a->scope));
578
  if (!eal)
579
    eal = a->eattrs;
580
  for(; eal; eal=eal->next)
581
    for(i=0; i<eal->count; i++)
582
      {
583
        ea_format(&eal->attrs[i], buf);
584
        cli_printf(c, -1012, "\t%s", buf);
585
      }
586
}
587

    
588
void
589
rta_init(void)
590
{
591
  rta_pool = rp_new(&root_pool, "Attributes");
592
  rta_slab = sl_new(rta_pool, sizeof(rta));
593
  rta_alloc_hash();
594
}