Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-attr.c @ 094d2bdb

History | View | Annotate | Download (24.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
/**
10
 * DOC: Route attribute cache
11
 *
12
 * Each route entry carries a set of route attributes. Several of them
13
 * vary from route to route, but most attributes are usually common
14
 * for a large number of routes. To conserve memory, we've decided to
15
 * store only the varying ones directly in the &rte and hold the rest
16
 * in a special structure called &rta which is shared among all the
17
 * &rte's with these attributes.
18
 *
19
 * Each &rta contains all the static attributes of the route (i.e.,
20
 * those which are always present) as structure members and a list of
21
 * dynamic attributes represented by a linked list of &ea_list
22
 * structures, each of them consisting of an array of &eattr's containing
23
 * the individual attributes. An attribute can be specified more than once
24
 * in the &ea_list chain and in such case the first occurrence overrides
25
 * the others. This semantics is used especially when someone (for example
26
 * a filter) wishes to alter values of several dynamic attributes, but
27
 * it wants to preserve the original attribute lists maintained by
28
 * another module.
29
 *
30
 * Each &eattr contains an attribute identifier (split to protocol ID and
31
 * per-protocol attribute ID), protocol dependent flags, a type code (consisting
32
 * of several bit fields describing attribute characteristics) and either an
33
 * embedded 32-bit value or a pointer to a &adata structure holding attribute
34
 * contents.
35
 *
36
 * There exist two variants of &rta's -- cached and un-cached ones. Un-cached
37
 * &rta's can have arbitrarily complex structure of &ea_list's and they
38
 * can be modified by any module in the route processing chain. Cached
39
 * &rta's have their attribute lists normalized (that means at most one
40
 * &ea_list is present and its values are sorted in order to speed up
41
 * searching), they are stored in a hash table to make fast lookup possible
42
 * and they are provided with a use count to allow sharing.
43
 *
44
 * Routing tables always contain only cached &rta's.
45
 */
46

    
47
#include "nest/bird.h"
48
#include "nest/route.h"
49
#include "nest/protocol.h"
50
#include "nest/iface.h"
51
#include "nest/cli.h"
52
#include "nest/attrs.h"
53
#include "lib/alloca.h"
54
#include "lib/resource.h"
55
#include "lib/string.h"
56

    
57
pool *rta_pool;
58

    
59
static slab *rta_slab;
60
static slab *mpnh_slab;
61
static slab *rte_src_slab;
62

    
63
/* rte source ID bitmap */
64
static u32 *src_ids;
65
static u32 src_id_size, src_id_used, src_id_pos;
66
#define SRC_ID_SIZE_DEF 4
67

    
68
/* rte source hash */
69
static struct rte_src **src_table;
70
static u32 src_hash_order, src_hash_size, src_hash_count;
71
#define SRC_HASH_ORDER_DEF 6
72
#define SRC_HASH_ORDER_MAX 18
73
#define SRC_HASH_ORDER_MIN 10
74

    
75
struct protocol *attr_class_to_protocol[EAP_MAX];
76

    
77

    
78
static void
79
rte_src_init(void)
80
{
81
  rte_src_slab = sl_new(rta_pool, sizeof(struct rte_src));
82

    
83
  src_id_pos = 0;
84
  src_id_size = SRC_ID_SIZE_DEF;
85
  src_ids = mb_allocz(rta_pool, src_id_size * sizeof(u32));
86

    
87
 /* ID 0 is reserved */
88
  src_ids[0] = 1;
89
  src_id_used = 1;
90

    
91
  src_hash_count = 0;
92
  src_hash_order = SRC_HASH_ORDER_DEF;
93
  src_hash_size = 1 << src_hash_order;
94
  src_table = mb_allocz(rta_pool, src_hash_size * sizeof(struct rte_src *));
95
}
96

    
97
static inline int u32_cto(unsigned int x) { return ffs(~x) - 1; }
98

    
99
static inline u32
100
rte_src_alloc_id(void)
101
{
102
  int i, j;
103
  for (i = src_id_pos; i < src_id_size; i++)
104
    if (src_ids[i] != 0xffffffff)
105
      goto found;
106

    
107
  /* If we are at least 7/8 full, expand */
108
  if (src_id_used > (src_id_size * 28))
109
    {
110
      src_id_size *= 2;
111
      src_ids = mb_realloc(rta_pool, src_ids, src_id_size * sizeof(u32));
112
      bzero(src_ids + i, (src_id_size - i) * sizeof(u32));
113
      goto found;
114
    }
115

    
116
  for (i = 0; i < src_id_pos; i++)
117
    if (src_ids[i] != 0xffffffff)
118
      goto found;
119

    
120
  ASSERT(0);
121

    
122
 found:
123
  ASSERT(i < 0x8000000);
124

    
125
  src_id_pos = i;
126
  j = u32_cto(src_ids[i]);
127

    
128
  src_ids[i] |= (1 << j);
129
  src_id_used++;
130
  return 32 * i + j;
131
}
132

    
133
static inline void
134
rte_src_free_id(u32 id)
135
{
136
  int i = id / 32;
137
  int j = id % 32;
138

    
139
  ASSERT((i < src_id_size) && (src_ids[i] & (1 << j)));
140
  src_ids[i] &= ~(1 << j);
141
  src_id_used--;
142
}
143

    
144
static inline u32 rte_src_hash(struct proto *p, u32 x, u32 order)
145
{ return (x * 2902958171u) >> (32 - order); }
146

    
147
static void
148
rte_src_rehash(int step)
149
{
150
  struct rte_src **old_tab, *src, *src_next;
151
  u32 old_size, hash, i;
152

    
153
  old_tab = src_table;
154
  old_size = src_hash_size;
155

    
156
  src_hash_order += step;
157
  src_hash_size = 1 << src_hash_order;
158
  src_table = mb_allocz(rta_pool, src_hash_size * sizeof(struct rte_src *));
159
  
160
  for (i = 0; i < old_size; i++)
161
    for (src = old_tab[i]; src; src = src_next)
162
      {
163
        src_next = src->next;
164
        hash = rte_src_hash(src->proto, src->private_id, src_hash_order);
165
        src->next = src_table[hash];
166
        src_table[hash] = src;
167
      }
168

    
169
  mb_free(old_tab);
170
}
171

    
172
struct rte_src *
173
rt_find_source(struct proto *p, u32 id)
174
{
175
  struct rte_src *src;
176
  u32 hash = rte_src_hash(p, id, src_hash_order);
177

    
178
  for (src = src_table[hash]; src; src = src->next)
179
    if ((src->proto == p) && (src->private_id == id))
180
      return src;
181

    
182
  return NULL;
183
}
184

    
185
struct rte_src *
186
rt_get_source(struct proto *p, u32 id)
187
{
188
  struct rte_src *src;
189
  u32 hash = rte_src_hash(p, id, src_hash_order);
190

    
191
  for (src = src_table[hash]; src; src = src->next)
192
    if ((src->proto == p) && (src->private_id == id))
193
      return src;
194

    
195
  src = sl_alloc(rte_src_slab);
196
  src->proto = p;
197
  src->private_id = id;
198
  src->global_id = rte_src_alloc_id();
199
  src->uc = 0;
200

    
201
  src->next = src_table[hash];
202
  src_table[hash] = src;
203

    
204
  src_hash_count++;
205
  if ((src_hash_count > src_hash_size) && (src_hash_order < SRC_HASH_ORDER_MAX))
206
    rte_src_rehash(1);
207

    
208
  return src;
209
}
210

    
211
static inline void
212
rt_remove_source(struct rte_src **sp)
213
{
214
  struct rte_src *src = *sp;
215

    
216
  *sp = src->next;
217
  rte_src_free_id(src->global_id);
218
  sl_free(rte_src_slab, src);
219
  src_hash_count--;
220
}
221

    
222
void
223
rt_prune_sources(void)
224
{
225
  struct rte_src **sp;
226
  int i;
227
  
228
  for (i = 0; i < src_hash_size; i++)
229
    {
230
      sp = &src_table[i];
231
      while (*sp)
232
        {
233
          if ((*sp)->uc == 0)
234
            rt_remove_source(sp);
235
          else
236
            sp = &(*sp)->next;
237
        }
238
    }
239

    
240
  while ((src_hash_count < (src_hash_size / 4)) && (src_hash_order > SRC_HASH_ORDER_MIN))
241
    rte_src_rehash(-1);
242
}
243

    
244

    
245
/*
246
 *        Multipath Next Hop
247
 */
248

    
249
static inline unsigned int
250
mpnh_hash(struct mpnh *x)
251
{
252
  unsigned int h = 0;
253
  for (; x; x = x->next)
254
    h ^= ipa_hash(x->gw);
255

    
256
  return h;
257
}
258

    
259
int
260
mpnh__same(struct mpnh *x, struct mpnh *y)
261
{
262
  for (; x && y; x = x->next, y = y->next)
263
    if (!ipa_equal(x->gw, y->gw) || (x->iface != y->iface) || (x->weight != y->weight))
264
      return 0;
265

    
266
  return x == y;
267
}
268

    
269
static struct mpnh *
270
mpnh_copy(struct mpnh *o)
271
{
272
  struct mpnh *first = NULL;
273
  struct mpnh **last = &first;
274

    
275
  for (; o; o = o->next)
276
    {
277
      struct mpnh *n = sl_alloc(mpnh_slab);
278
      n->gw = o->gw;
279
      n->iface = o->iface;
280
      n->next = NULL;
281
      n->weight = o->weight;
282

    
283
      *last = n;
284
      last = &(n->next);
285
    }
286

    
287
  return first;
288
}
289

    
290
static void
291
mpnh_free(struct mpnh *o)
292
{
293
  struct mpnh *n;
294

    
295
  while (o)
296
    {
297
      n = o->next;
298
      sl_free(mpnh_slab, o);
299
      o = n;
300
    }
301
}
302

    
303

    
304
/*
305
 *        Extended Attributes
306
 */
307

    
308
static inline eattr *
309
ea__find(ea_list *e, unsigned id)
310
{
311
  eattr *a;
312
  int l, r, m;
313

    
314
  while (e)
315
    {
316
      if (e->flags & EALF_BISECT)
317
        {
318
          l = 0;
319
          r = e->count - 1;
320
          while (l <= r)
321
            {
322
              m = (l+r) / 2;
323
              a = &e->attrs[m];
324
              if (a->id == id)
325
                return a;
326
              else if (a->id < id)
327
                l = m+1;
328
              else
329
                r = m-1;
330
            }
331
        }
332
      else
333
        for(m=0; m<e->count; m++)
334
          if (e->attrs[m].id == id)
335
            return &e->attrs[m];
336
      e = e->next;
337
    }
338
  return NULL;
339
}
340

    
341
/**
342
 * ea_find - find an extended attribute
343
 * @e: attribute list to search in
344
 * @id: attribute ID to search for
345
 *
346
 * Given an extended attribute list, ea_find() searches for a first
347
 * occurrence of an attribute with specified ID, returning either a pointer
348
 * to its &eattr structure or %NULL if no such attribute exists.
349
 */
350
eattr *
351
ea_find(ea_list *e, unsigned id)
352
{
353
  eattr *a = ea__find(e, id & EA_CODE_MASK);
354

    
355
  if (a && (a->type & EAF_TYPE_MASK) == EAF_TYPE_UNDEF &&
356
      !(id & EA_ALLOW_UNDEF))
357
    return NULL;
358
  return a;
359
}
360

    
361
/**
362
 * ea_get_int - fetch an integer attribute
363
 * @e: attribute list
364
 * @id: attribute ID
365
 * @def: default value
366
 *
367
 * This function is a shortcut for retrieving a value of an integer attribute
368
 * by calling ea_find() to find the attribute, extracting its value or returning
369
 * a provided default if no such attribute is present.
370
 */
371
int
372
ea_get_int(ea_list *e, unsigned id, int def)
373
{
374
  eattr *a = ea_find(e, id);
375
  if (!a)
376
    return def;
377
  return a->u.data;
378
}
379

    
380
static inline void
381
ea_do_sort(ea_list *e)
382
{
383
  unsigned n = e->count;
384
  eattr *a = e->attrs;
385
  eattr *b = alloca(n * sizeof(eattr));
386
  unsigned s, ss;
387

    
388
  /* We need to use a stable sorting algorithm, hence mergesort */
389
  do
390
    {
391
      s = ss = 0;
392
      while (s < n)
393
        {
394
          eattr *p, *q, *lo, *hi;
395
          p = b;
396
          ss = s;
397
          *p++ = a[s++];
398
          while (s < n && p[-1].id <= a[s].id)
399
            *p++ = a[s++];
400
          if (s < n)
401
            {
402
              q = p;
403
              *p++ = a[s++];
404
              while (s < n && p[-1].id <= a[s].id)
405
                *p++ = a[s++];
406
              lo = b;
407
              hi = q;
408
              s = ss;
409
              while (lo < q && hi < p)
410
                if (lo->id <= hi->id)
411
                  a[s++] = *lo++;
412
                else
413
                  a[s++] = *hi++;
414
              while (lo < q)
415
                a[s++] = *lo++;
416
              while (hi < p)
417
                a[s++] = *hi++;
418
            }
419
        }
420
    }
421
  while (ss);
422
}
423

    
424
static inline void
425
ea_do_prune(ea_list *e)
426
{
427
  eattr *s, *d, *l, *s0;
428
  int i = 0;
429

    
430
  /* Discard duplicates and undefs. Do you remember sorting was stable? */
431
  s = d = e->attrs;
432
  l = e->attrs + e->count;
433
  while (s < l)
434
    {
435
      s0 = s++;
436
      while (s < l && s->id == s[-1].id)
437
        s++;
438
      /* s0 is the most recent version, s[-1] the oldest one */
439
      if ((s0->type & EAF_TYPE_MASK) != EAF_TYPE_UNDEF)
440
        {
441
          *d = *s0;
442
          d->type = (d->type & ~EAF_ORIGINATED) | (s[-1].type & EAF_ORIGINATED);
443
          d++;
444
          i++;
445
        }
446
    }
447
  e->count = i;
448
}
449

    
450
/**
451
 * ea_sort - sort an attribute list
452
 * @e: list to be sorted
453
 *
454
 * This function takes a &ea_list chain and sorts the attributes
455
 * within each of its entries.
456
 *
457
 * If an attribute occurs multiple times in a single &ea_list,
458
 * ea_sort() leaves only the first (the only significant) occurrence.
459
 */
460
void
461
ea_sort(ea_list *e)
462
{
463
  while (e)
464
    {
465
      if (!(e->flags & EALF_SORTED))
466
        {
467
          ea_do_sort(e);
468
          ea_do_prune(e);
469
          e->flags |= EALF_SORTED;
470
        }
471
      if (e->count > 5)
472
        e->flags |= EALF_BISECT;
473
      e = e->next;
474
    }
475
}
476

    
477
/**
478
 * ea_scan - estimate attribute list size
479
 * @e: attribute list
480
 *
481
 * This function calculates an upper bound of the size of
482
 * a given &ea_list after merging with ea_merge().
483
 */
484
unsigned
485
ea_scan(ea_list *e)
486
{
487
  unsigned cnt = 0;
488

    
489
  while (e)
490
    {
491
      cnt += e->count;
492
      e = e->next;
493
    }
494
  return sizeof(ea_list) + sizeof(eattr)*cnt;
495
}
496

    
497
/**
498
 * ea_merge - merge segments of an attribute list
499
 * @e: attribute list
500
 * @t: buffer to store the result to
501
 *
502
 * This function takes a possibly multi-segment attribute list
503
 * and merges all of its segments to one.
504
 *
505
 * The primary use of this function is for &ea_list normalization:
506
 * first call ea_scan() to determine how much memory will the result
507
 * take, then allocate a buffer (usually using alloca()), merge the
508
 * segments with ea_merge() and finally sort and prune the result
509
 * by calling ea_sort().
510
 */
511
void
512
ea_merge(ea_list *e, ea_list *t)
513
{
514
  eattr *d = t->attrs;
515

    
516
  t->flags = 0;
517
  t->count = 0;
518
  t->next = NULL;
519
  while (e)
520
    {
521
      memcpy(d, e->attrs, sizeof(eattr)*e->count);
522
      t->count += e->count;
523
      d += e->count;
524
      e = e->next;
525
    }
526
}
527

    
528
/**
529
 * ea_same - compare two &ea_list's
530
 * @x: attribute list
531
 * @y: attribute list
532
 *
533
 * ea_same() compares two normalized attribute lists @x and @y and returns
534
 * 1 if they contain the same attributes, 0 otherwise.
535
 */
536
int
537
ea_same(ea_list *x, ea_list *y)
538
{
539
  int c;
540

    
541
  if (!x || !y)
542
    return x == y;
543
  ASSERT(!x->next && !y->next);
544
  if (x->count != y->count)
545
    return 0;
546
  for(c=0; c<x->count; c++)
547
    {
548
      eattr *a = &x->attrs[c];
549
      eattr *b = &y->attrs[c];
550

    
551
      if (a->id != b->id ||
552
          a->flags != b->flags ||
553
          a->type != b->type ||
554
          ((a->type & EAF_EMBEDDED) ? a->u.data != b->u.data :
555
           (a->u.ptr->length != b->u.ptr->length || memcmp(a->u.ptr->data, b->u.ptr->data, a->u.ptr->length))))
556
        return 0;
557
    }
558
  return 1;
559
}
560

    
561
static inline ea_list *
562
ea_list_copy(ea_list *o)
563
{
564
  ea_list *n;
565
  unsigned i, len;
566

    
567
  if (!o)
568
    return NULL;
569
  ASSERT(!o->next);
570
  len = sizeof(ea_list) + sizeof(eattr) * o->count;
571
  n = mb_alloc(rta_pool, len);
572
  memcpy(n, o, len);
573
  n->flags |= EALF_CACHED;
574
  for(i=0; i<o->count; i++)
575
    {
576
      eattr *a = &n->attrs[i];
577
      if (!(a->type & EAF_EMBEDDED))
578
        {
579
          unsigned size = sizeof(struct adata) + a->u.ptr->length;
580
          struct adata *d = mb_alloc(rta_pool, size);
581
          memcpy(d, a->u.ptr, size);
582
          a->u.ptr = d;
583
        }
584
    }
585
  return n;
586
}
587

    
588
static inline void
589
ea_free(ea_list *o)
590
{
591
  int i;
592

    
593
  if (o)
594
    {
595
      ASSERT(!o->next);
596
      for(i=0; i<o->count; i++)
597
        {
598
          eattr *a = &o->attrs[i];
599
          if (!(a->type & EAF_EMBEDDED))
600
            mb_free(a->u.ptr);
601
        }
602
      mb_free(o);
603
    }
604
}
605

    
606
static int
607
get_generic_attr(eattr *a, byte **buf, int buflen UNUSED)
608
{
609
  if (a->id == EA_GEN_IGP_METRIC)
610
    {
611
      *buf += bsprintf(*buf, "igp_metric");
612
      return GA_NAME;
613
    }
614
 
615
  return GA_UNKNOWN;
616
}
617

    
618
static inline void
619
opaque_format(struct adata *ad, byte *buf, unsigned int size)
620
{
621
  byte *bound = buf + size - 10;
622
  int i;
623

    
624
  for(i = 0; i < ad->length; i++)
625
    {
626
      if (buf > bound)
627
        {
628
          strcpy(buf, " ...");
629
          return;
630
        }
631
      if (i)
632
        *buf++ = ' ';
633

    
634
      buf += bsprintf(buf, "%02x", ad->data[i]);
635
    }
636

    
637
  *buf = 0;
638
  return;
639
}
640

    
641
static inline void
642
ea_show_int_set(struct cli *c, struct adata *ad, int way, byte *pos, byte *buf, byte *end)
643
{
644
  int i = int_set_format(ad, way, 0, pos, end - pos);
645
  cli_printf(c, -1012, "\t%s", buf);
646
  while (i)
647
    {
648
      i = int_set_format(ad, way, i, buf, end - buf - 1);
649
      cli_printf(c, -1012, "\t\t%s", buf);
650
    }
651
}
652

    
653
static inline void
654
ea_show_ec_set(struct cli *c, struct adata *ad, byte *pos, byte *buf, byte *end)
655
{
656
  int i = ec_set_format(ad, 0, pos, end - pos);
657
  cli_printf(c, -1012, "\t%s", buf);
658
  while (i)
659
    {
660
      i = ec_set_format(ad, i, buf, end - buf - 1);
661
      cli_printf(c, -1012, "\t\t%s", buf);
662
    }
663
}
664

    
665
/**
666
 * ea_show - print an &eattr to CLI
667
 * @c: destination CLI
668
 * @e: attribute to be printed
669
 *
670
 * This function takes an extended attribute represented by its &eattr
671
 * structure and prints it to the CLI according to the type information.
672
 *
673
 * If the protocol defining the attribute provides its own
674
 * get_attr() hook, it's consulted first.
675
 */
676
void
677
ea_show(struct cli *c, eattr *e)
678
{
679
  struct protocol *p;
680
  int status = GA_UNKNOWN;
681
  struct adata *ad = (e->type & EAF_EMBEDDED) ? NULL : e->u.ptr;
682
  byte buf[CLI_MSG_SIZE];
683
  byte *pos = buf, *end = buf + sizeof(buf);
684

    
685
  if (p = attr_class_to_protocol[EA_PROTO(e->id)])
686
    {
687
      pos += bsprintf(pos, "%s.", p->name);
688
      if (p->get_attr)
689
        status = p->get_attr(e, pos, end - pos);
690
      pos += strlen(pos);
691
    }
692
  else if (EA_PROTO(e->id))
693
    pos += bsprintf(pos, "%02x.", EA_PROTO(e->id));
694
  else 
695
    status = get_generic_attr(e, &pos, end - pos);
696

    
697
  if (status < GA_NAME)
698
    pos += bsprintf(pos, "%02x", EA_ID(e->id));
699
  if (status < GA_FULL)
700
    {
701
      *pos++ = ':';
702
      *pos++ = ' ';
703
      switch (e->type & EAF_TYPE_MASK)
704
        {
705
        case EAF_TYPE_INT:
706
          bsprintf(pos, "%u", e->u.data);
707
          break;
708
        case EAF_TYPE_OPAQUE:
709
          opaque_format(ad, pos, end - pos);
710
          break;
711
        case EAF_TYPE_IP_ADDRESS:
712
          bsprintf(pos, "%I", *(ip_addr *) ad->data);
713
          break;
714
        case EAF_TYPE_ROUTER_ID:
715
          bsprintf(pos, "%R", e->u.data);
716
          break;
717
        case EAF_TYPE_AS_PATH:
718
          as_path_format(ad, pos, end - pos);
719
          break;
720
        case EAF_TYPE_INT_SET:
721
          ea_show_int_set(c, ad, 1, pos, buf, end);
722
          return;
723
        case EAF_TYPE_EC_SET:
724
          ea_show_ec_set(c, ad, pos, buf, end);
725
          return;
726
        case EAF_TYPE_UNDEF:
727
        default:
728
          bsprintf(pos, "<type %02x>", e->type);
729
        }
730
    }
731
  cli_printf(c, -1012, "\t%s", buf);
732
}
733

    
734
/**
735
 * ea_dump - dump an extended attribute
736
 * @e: attribute to be dumped
737
 *
738
 * ea_dump() dumps contents of the extended attribute given to
739
 * the debug output.
740
 */
741
void
742
ea_dump(ea_list *e)
743
{
744
  int i;
745

    
746
  if (!e)
747
    {
748
      debug("NONE");
749
      return;
750
    }
751
  while (e)
752
    {
753
      debug("[%c%c%c]",
754
            (e->flags & EALF_SORTED) ? 'S' : 's',
755
            (e->flags & EALF_BISECT) ? 'B' : 'b',
756
            (e->flags & EALF_CACHED) ? 'C' : 'c');
757
      for(i=0; i<e->count; i++)
758
        {
759
          eattr *a = &e->attrs[i];
760
          debug(" %02x:%02x.%02x", EA_PROTO(a->id), EA_ID(a->id), a->flags);
761
          if (a->type & EAF_TEMP)
762
            debug("T");
763
          debug("=%c", "?iO?I?P???S?????" [a->type & EAF_TYPE_MASK]);
764
          if (a->type & EAF_ORIGINATED)
765
            debug("o");
766
          if (a->type & EAF_EMBEDDED)
767
            debug(":%08x", a->u.data);
768
          else
769
            {
770
              int j, len = a->u.ptr->length;
771
              debug("[%d]:", len);
772
              for(j=0; j<len; j++)
773
                debug("%02x", a->u.ptr->data[j]);
774
            }
775
        }
776
      if (e = e->next)
777
        debug(" | ");
778
    }
779
}
780

    
781
/**
782
 * ea_hash - calculate an &ea_list hash key
783
 * @e: attribute list
784
 *
785
 * ea_hash() takes an extended attribute list and calculated a hopefully
786
 * uniformly distributed hash value from its contents.
787
 */
788
inline unsigned int
789
ea_hash(ea_list *e)
790
{
791
  u32 h = 0;
792
  int i;
793

    
794
  if (e)                        /* Assuming chain of length 1 */
795
    {
796
      for(i=0; i<e->count; i++)
797
        {
798
          struct eattr *a = &e->attrs[i];
799
          h ^= a->id;
800
          if (a->type & EAF_EMBEDDED)
801
            h ^= a->u.data;
802
          else
803
            {
804
              struct adata *d = a->u.ptr;
805
              int size = d->length;
806
              byte *z = d->data;
807
              while (size >= 4)
808
                {
809
                  h ^= *(u32 *)z;
810
                  z += 4;
811
                  size -= 4;
812
                }
813
              while (size--)
814
                h = (h >> 24) ^ (h << 8) ^ *z++;
815
            }
816
        }
817
      h ^= h >> 16;
818
      h ^= h >> 6;
819
      h &= 0xffff;
820
    }
821
  return h;
822
}
823

    
824
/**
825
 * ea_append - concatenate &ea_list's
826
 * @to: destination list (can be %NULL)
827
 * @what: list to be appended (can be %NULL)
828
 *
829
 * This function appends the &ea_list @what at the end of
830
 * &ea_list @to and returns a pointer to the resulting list.
831
 */
832
ea_list *
833
ea_append(ea_list *to, ea_list *what)
834
{
835
  ea_list *res;
836

    
837
  if (!to)
838
    return what;
839
  res = to;
840
  while (to->next)
841
    to = to->next;
842
  to->next = what;
843
  return res;
844
}
845

    
846
/*
847
 *        rta's
848
 */
849

    
850
static unsigned int rta_cache_count;
851
static unsigned int rta_cache_size = 32;
852
static unsigned int rta_cache_limit;
853
static unsigned int rta_cache_mask;
854
static rta **rta_hash_table;
855

    
856
static void
857
rta_alloc_hash(void)
858
{
859
  rta_hash_table = mb_allocz(rta_pool, sizeof(rta *) * rta_cache_size);
860
  if (rta_cache_size < 32768)
861
    rta_cache_limit = rta_cache_size * 2;
862
  else
863
    rta_cache_limit = ~0;
864
  rta_cache_mask = rta_cache_size - 1;
865
}
866

    
867
static inline unsigned int
868
rta_hash(rta *a)
869
{
870
  return (((unsigned) a->src) ^ ipa_hash(a->gw) ^
871
          mpnh_hash(a->nexthops) ^ ea_hash(a->eattrs)) & 0xffff;
872
}
873

    
874
static inline int
875
rta_same(rta *x, rta *y)
876
{
877
  return (x->src == y->src &&
878
          x->source == y->source &&
879
          x->scope == y->scope &&
880
          x->cast == y->cast &&
881
          x->dest == y->dest &&
882
          x->flags == y->flags &&
883
          x->igp_metric == y->igp_metric &&
884
          ipa_equal(x->gw, y->gw) &&
885
          ipa_equal(x->from, y->from) &&
886
          x->iface == y->iface &&
887
          x->hostentry == y->hostentry &&
888
          mpnh_same(x->nexthops, y->nexthops) &&
889
          ea_same(x->eattrs, y->eattrs));
890
}
891

    
892
static rta *
893
rta_copy(rta *o)
894
{
895
  rta *r = sl_alloc(rta_slab);
896

    
897
  memcpy(r, o, sizeof(rta));
898
  r->uc = 1;
899
  r->nexthops = mpnh_copy(o->nexthops);
900
  r->eattrs = ea_list_copy(o->eattrs);
901
  return r;
902
}
903

    
904
static inline void
905
rta_insert(rta *r)
906
{
907
  unsigned int h = r->hash_key & rta_cache_mask;
908
  r->next = rta_hash_table[h];
909
  if (r->next)
910
    r->next->pprev = &r->next;
911
  r->pprev = &rta_hash_table[h];
912
  rta_hash_table[h] = r;
913
}
914

    
915
static void
916
rta_rehash(void)
917
{
918
  unsigned int ohs = rta_cache_size;
919
  unsigned int h;
920
  rta *r, *n;
921
  rta **oht = rta_hash_table;
922

    
923
  rta_cache_size = 2*rta_cache_size;
924
  DBG("Rehashing rta cache from %d to %d entries.\n", ohs, rta_cache_size);
925
  rta_alloc_hash();
926
  for(h=0; h<ohs; h++)
927
    for(r=oht[h]; r; r=n)
928
      {
929
        n = r->next;
930
        rta_insert(r);
931
      }
932
  mb_free(oht);
933
}
934

    
935
/**
936
 * rta_lookup - look up a &rta in attribute cache
937
 * @o: a un-cached &rta
938
 *
939
 * rta_lookup() gets an un-cached &rta structure and returns its cached
940
 * counterpart. It starts with examining the attribute cache to see whether
941
 * there exists a matching entry. If such an entry exists, it's returned and
942
 * its use count is incremented, else a new entry is created with use count
943
 * set to 1.
944
 *
945
 * The extended attribute lists attached to the &rta are automatically
946
 * converted to the normalized form.
947
 */
948
rta *
949
rta_lookup(rta *o)
950
{
951
  rta *r;
952
  unsigned int h;
953

    
954
  ASSERT(!(o->aflags & RTAF_CACHED));
955
  if (o->eattrs)
956
    {
957
      if (o->eattrs->next)        /* Multiple ea_list's, need to merge them */
958
        {
959
          ea_list *ml = alloca(ea_scan(o->eattrs));
960
          ea_merge(o->eattrs, ml);
961
          o->eattrs = ml;
962
        }
963
      ea_sort(o->eattrs);
964
    }
965

    
966
  h = rta_hash(o);
967
  for(r=rta_hash_table[h & rta_cache_mask]; r; r=r->next)
968
    if (r->hash_key == h && rta_same(r, o))
969
      return rta_clone(r);
970

    
971
  r = rta_copy(o);
972
  r->hash_key = h;
973
  r->aflags = RTAF_CACHED;
974
  rt_lock_source(r->src);
975
  rt_lock_hostentry(r->hostentry);
976
  rta_insert(r);
977

    
978
  if (++rta_cache_count > rta_cache_limit)
979
    rta_rehash();
980

    
981
  return r;
982
}
983

    
984
void
985
rta__free(rta *a)
986
{
987
  ASSERT(rta_cache_count && (a->aflags & RTAF_CACHED));
988
  rta_cache_count--;
989
  *a->pprev = a->next;
990
  if (a->next)
991
    a->next->pprev = a->pprev;
992
  a->aflags = 0;                /* Poison the entry */
993
  rt_unlock_hostentry(a->hostentry);
994
  rt_unlock_source(a->src);
995
  mpnh_free(a->nexthops);
996
  ea_free(a->eattrs);
997
  sl_free(rta_slab, a);
998
}
999

    
1000
/**
1001
 * rta_dump - dump route attributes
1002
 * @a: attribute structure to dump
1003
 *
1004
 * This function takes a &rta and dumps its contents to the debug output.
1005
 */
1006
void
1007
rta_dump(rta *a)
1008
{
1009
  static char *rts[] = { "RTS_DUMMY", "RTS_STATIC", "RTS_INHERIT", "RTS_DEVICE",
1010
                         "RTS_STAT_DEV", "RTS_REDIR", "RTS_RIP",
1011
                         "RTS_OSPF", "RTS_OSPF_IA", "RTS_OSPF_EXT1",
1012
                         "RTS_OSPF_EXT2", "RTS_BGP" };
1013
  static char *rtc[] = { "", " BC", " MC", " AC" };
1014
  static char *rtd[] = { "", " DEV", " HOLE", " UNREACH", " PROHIBIT" };
1015

    
1016
  debug("p=%s uc=%d %s %s%s%s h=%04x",
1017
        a->src->proto->name, a->uc, rts[a->source], ip_scope_text(a->scope), rtc[a->cast],
1018
        rtd[a->dest], a->hash_key);
1019
  if (!(a->aflags & RTAF_CACHED))
1020
    debug(" !CACHED");
1021
  debug(" <-%I", a->from);
1022
  if (a->dest == RTD_ROUTER)
1023
    debug(" ->%I", a->gw);
1024
  if (a->dest == RTD_DEVICE || a->dest == RTD_ROUTER)
1025
    debug(" [%s]", a->iface ? a->iface->name : "???" );
1026
  if (a->eattrs)
1027
    {
1028
      debug(" EA: ");
1029
      ea_dump(a->eattrs);
1030
    }
1031
}
1032

    
1033
/**
1034
 * rta_dump_all - dump attribute cache
1035
 *
1036
 * This function dumps the whole contents of route attribute cache
1037
 * to the debug output.
1038
 */
1039
void
1040
rta_dump_all(void)
1041
{
1042
  rta *a;
1043
  unsigned int h;
1044

    
1045
  debug("Route attribute cache (%d entries, rehash at %d):\n", rta_cache_count, rta_cache_limit);
1046
  for(h=0; h<rta_cache_size; h++)
1047
    for(a=rta_hash_table[h]; a; a=a->next)
1048
      {
1049
        debug("%p ", a);
1050
        rta_dump(a);
1051
        debug("\n");
1052
      }
1053
  debug("\n");
1054
}
1055

    
1056
void
1057
rta_show(struct cli *c, rta *a, ea_list *eal)
1058
{
1059
  static char *src_names[] = { "dummy", "static", "inherit", "device", "static-device", "redirect",
1060
                               "RIP", "OSPF", "OSPF-IA", "OSPF-E1", "OSPF-E2", "BGP", "pipe" };
1061
  static char *cast_names[] = { "unicast", "broadcast", "multicast", "anycast" };
1062
  int i;
1063

    
1064
  cli_printf(c, -1008, "\tType: %s %s %s", src_names[a->source], cast_names[a->cast], ip_scope_text(a->scope));
1065
  if (!eal)
1066
    eal = a->eattrs;
1067
  for(; eal; eal=eal->next)
1068
    for(i=0; i<eal->count; i++)
1069
      ea_show(c, &eal->attrs[i]);
1070
}
1071

    
1072
/**
1073
 * rta_init - initialize route attribute cache
1074
 *
1075
 * This function is called during initialization of the routing
1076
 * table module to set up the internals of the attribute cache.
1077
 */
1078
void
1079
rta_init(void)
1080
{
1081
  rta_pool = rp_new(&root_pool, "Attributes");
1082
  rta_slab = sl_new(rta_pool, sizeof(rta));
1083
  mpnh_slab = sl_new(rta_pool, sizeof(struct mpnh));
1084
  rta_alloc_hash();
1085
  rte_src_init();
1086
}
1087

    
1088
/*
1089
 *  Documentation for functions declared inline in route.h
1090
 */
1091
#if 0
1092

1093
/**
1094
 * rta_clone - clone route attributes
1095
 * @r: a &rta to be cloned
1096
 *
1097
 * rta_clone() takes a cached &rta and returns its identical cached
1098
 * copy. Currently it works by just returning the original &rta with
1099
 * its use count incremented.
1100
 */
1101
static inline rta *rta_clone(rta *r)
1102
{ DUMMY; }
1103

1104
/**
1105
 * rta_free - free route attributes
1106
 * @r: a &rta to be freed
1107
 *
1108
 * If you stop using a &rta (for example when deleting a route which uses
1109
 * it), you need to call rta_free() to notify the attribute cache the
1110
 * attribute is no longer in use and can be freed if you were the last
1111
 * user (which rta_free() tests by inspecting the use count).
1112
 */
1113
static inline void rta_free(rta *r)
1114
{ DUMMY; }
1115

1116
#endif