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

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

47
48
49
#include "nest/bird.h"
#include "nest/route.h"
#include "nest/protocol.h"
50
#include "nest/iface.h"
51
#include "nest/cli.h"
52
#include "nest/attrs.h"
Ondřej Filip's avatar
Ondřej Filip committed
53
#include "lib/alloca.h"
54
#include "lib/resource.h"
55
#include "lib/string.h"
56

57
58
pool *rta_pool;

59
static slab *rta_slab;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
60
static slab *mpnh_slab;
61

62
63
struct protocol *attr_class_to_protocol[EAP_MAX];

Ondřej Zajíček's avatar
Ondřej Zajíček committed
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
static inline unsigned int
mpnh_hash(struct mpnh *x)
{
  unsigned int h = 0;
  for (; x; x = x->next)
    h ^= ipa_hash(x->gw);

  return h;
}

int
mpnh__same(struct mpnh *x, struct mpnh *y)
{
  for (; x && y; x = x->next, y = y->next)
    if (!ipa_equal(x->gw, y->gw) || (x->iface != y->iface) || (x->weight != y->weight))
      return 0;

  return x == y;
}

static struct mpnh *
mpnh_copy(struct mpnh *o)
{
  struct mpnh *first = NULL;
  struct mpnh **last = &first;

  for (; o; o = o->next)
    {
      struct mpnh *n = sl_alloc(mpnh_slab);
      n->gw = o->gw;
      n->iface = o->iface;
      n->next = NULL;
      n->weight = o->weight;

      *last = n;
      last = &(n->next);
    }

  return first;
}

static void
mpnh_free(struct mpnh *o)
{
  struct mpnh *n;

  while (o)
    {
      n = o->next;
      sl_free(mpnh_slab, o);
      o = n;
    }
}


119
120
121
122
/*
 *	Extended Attributes
 */

123
124
static inline eattr *
ea__find(ea_list *e, unsigned id)
125
126
127
128
129
130
131
132
133
{
  eattr *a;
  int l, r, m;

  while (e)
    {
      if (e->flags & EALF_BISECT)
	{
	  l = 0;
134
	  r = e->count - 1;
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
	  while (l <= r)
	    {
	      m = (l+r) / 2;
	      a = &e->attrs[m];
	      if (a->id == id)
		return a;
	      else if (a->id < id)
		l = m+1;
	      else
		r = m-1;
	    }
	}
      else
	for(m=0; m<e->count; m++)
	  if (e->attrs[m].id == id)
	    return &e->attrs[m];
      e = e->next;
    }
  return NULL;
}

156
157
158
159
160
161
/**
 * ea_find - find an extended attribute
 * @e: attribute list to search in
 * @id: attribute ID to search for
 *
 * Given an extended attribute list, ea_find() searches for a first
Martin Mareš's avatar
Martin Mareš committed
162
 * occurrence of an attribute with specified ID, returning either a pointer
163
164
 * to its &eattr structure or %NULL if no such attribute exists.
 */
165
166
167
168
169
170
171
172
173
174
175
eattr *
ea_find(ea_list *e, unsigned id)
{
  eattr *a = ea__find(e, id & EA_CODE_MASK);

  if (a && (a->type & EAF_TYPE_MASK) == EAF_TYPE_UNDEF &&
      !(id & EA_ALLOW_UNDEF))
    return NULL;
  return a;
}

176
177
178
179
180
181
182
183
184
185
/**
 * ea_get_int - fetch an integer attribute
 * @e: attribute list
 * @id: attribute ID
 * @def: default value
 *
 * This function is a shortcut for retrieving a value of an integer attribute
 * by calling ea_find() to find the attribute, extracting its value or returning
 * a provided default if no such attribute is present.
 */
186
187
188
189
190
191
192
193
194
int
ea_get_int(ea_list *e, unsigned id, int def)
{
  eattr *a = ea_find(e, id);
  if (!a)
    return def;
  return a->u.data;
}

195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
static inline void
ea_do_sort(ea_list *e)
{
  unsigned n = e->count;
  eattr *a = e->attrs;
  eattr *b = alloca(n * sizeof(eattr));
  unsigned s, ss;

  /* We need to use a stable sorting algorithm, hence mergesort */
  do
    {
      s = ss = 0;
      while (s < n)
	{
	  eattr *p, *q, *lo, *hi;
	  p = b;
	  ss = s;
	  *p++ = a[s++];
	  while (s < n && p[-1].id <= a[s].id)
	    *p++ = a[s++];
	  if (s < n)
	    {
	      q = p;
	      *p++ = a[s++];
	      while (s < n && p[-1].id <= a[s].id)
		*p++ = a[s++];
	      lo = b;
	      hi = q;
	      s = ss;
	      while (lo < q && hi < p)
		if (lo->id <= hi->id)
		  a[s++] = *lo++;
		else
		  a[s++] = *hi++;
	      while (lo < q)
		a[s++] = *lo++;
	      while (hi < p)
		a[s++] = *hi++;
	    }
	}
    }
  while (ss);
}

static inline void
ea_do_prune(ea_list *e)
{
242
  eattr *s, *d, *l, *s0;
243
244
245
246
247
248
249
  int i = 0;

  /* Discard duplicates and undefs. Do you remember sorting was stable? */
  s = d = e->attrs;
  l = e->attrs + e->count;
  while (s < l)
    {
250
251
252
253
254
      s0 = s++;
      while (s < l && s->id == s[-1].id)
	s++;
      /* s0 is the most recent version, s[-1] the oldest one */
      if ((s0->type & EAF_TYPE_MASK) != EAF_TYPE_UNDEF)
255
	{
256
257
258
	  *d = *s0;
	  d->type = (d->type & ~EAF_ORIGINATED) | (s[-1].type & EAF_ORIGINATED);
	  d++;
259
260
261
262
	  i++;
	}
    }
  e->count = i;
263
264
}

265
266
267
268
269
270
271
272
/**
 * ea_sort - sort an attribute list
 * @e: list to be sorted
 *
 * This function takes a &ea_list chain and sorts the attributes
 * within each of its entries.
 *
 * If an attribute occurs multiple times in a single &ea_list,
Martin Mareš's avatar
Martin Mareš committed
273
 * ea_sort() leaves only the first (the only significant) occurrence.
274
 */
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
void
ea_sort(ea_list *e)
{
  while (e)
    {
      if (!(e->flags & EALF_SORTED))
	{
	  ea_do_sort(e);
	  ea_do_prune(e);
	  e->flags |= EALF_SORTED;
	}
      if (e->count > 5)
	e->flags |= EALF_BISECT;
      e = e->next;
    }
}

292
293
294
295
296
297
298
/**
 * ea_scan - estimate attribute list size
 * @e: attribute list
 *
 * This function calculates an upper bound of the size of
 * a given &ea_list after merging with ea_merge().
 */
299
300
301
302
303
304
305
306
307
308
309
310
311
unsigned
ea_scan(ea_list *e)
{
  unsigned cnt = 0;

  while (e)
    {
      cnt += e->count;
      e = e->next;
    }
  return sizeof(ea_list) + sizeof(eattr)*cnt;
}

312
313
314
315
316
317
318
319
320
321
322
323
324
325
/**
 * ea_merge - merge segments of an attribute list
 * @e: attribute list
 * @t: buffer to store the result to
 *
 * This function takes a possibly multi-segment attribute list
 * and merges all of its segments to one.
 *
 * The primary use of this function is for &ea_list normalization:
 * first call ea_scan() to determine how much memory will the result
 * take, then allocate a buffer (usually using alloca()), merge the
 * segments with ea_merge() and finally sort and prune the result
 * by calling ea_sort().
 */
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
void
ea_merge(ea_list *e, ea_list *t)
{
  eattr *d = t->attrs;

  t->flags = 0;
  t->count = 0;
  t->next = NULL;
  while (e)
    {
      memcpy(d, e->attrs, sizeof(eattr)*e->count);
      t->count += e->count;
      d += e->count;
      e = e->next;
    }
}

343
344
345
346
347
348
349
350
/**
 * ea_same - compare two &ea_list's
 * @x: attribute list
 * @y: attribute list
 *
 * ea_same() compares two normalized attribute lists @x and @y and returns
 * 1 if they contain the same attributes, 0 otherwise.
 */
351
int
352
353
354
355
ea_same(ea_list *x, ea_list *y)
{
  int c;

356
357
358
359
360
361
  if (!x || !y)
    return x == y;
  ASSERT(!x->next && !y->next);
  if (x->count != y->count)
    return 0;
  for(c=0; c<x->count; c++)
362
    {
363
364
365
366
367
368
369
      eattr *a = &x->attrs[c];
      eattr *b = &y->attrs[c];

      if (a->id != b->id ||
	  a->flags != b->flags ||
	  a->type != b->type ||
	  ((a->type & EAF_EMBEDDED) ? a->u.data != b->u.data :
370
	   (a->u.ptr->length != b->u.ptr->length || memcmp(a->u.ptr->data, b->u.ptr->data, a->u.ptr->length))))
371
	return 0;
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
    }
  return 1;
}

static inline ea_list *
ea_list_copy(ea_list *o)
{
  ea_list *n;
  unsigned i, len;

  if (!o)
    return NULL;
  ASSERT(!o->next);
  len = sizeof(ea_list) + sizeof(eattr) * o->count;
  n = mb_alloc(rta_pool, len);
  memcpy(n, o, len);
  n->flags |= EALF_CACHED;
  for(i=0; i<o->count; i++)
    {
      eattr *a = &n->attrs[i];
392
      if (!(a->type & EAF_EMBEDDED))
393
394
395
396
397
398
399
400
401
402
	{
	  unsigned size = sizeof(struct adata) + a->u.ptr->length;
	  struct adata *d = mb_alloc(rta_pool, size);
	  memcpy(d, a->u.ptr, size);
	  a->u.ptr = d;
	}
    }
  return n;
}

Martin Mareš's avatar
Martin Mareš committed
403
404
405
static inline void
ea_free(ea_list *o)
{
406
407
  int i;

Martin Mareš's avatar
Martin Mareš committed
408
409
410
  if (o)
    {
      ASSERT(!o->next);
411
412
413
414
415
416
      for(i=0; i<o->count; i++)
	{
	  eattr *a = &o->attrs[i];
	  if (!(a->type & EAF_EMBEDDED))
	    mb_free(a->u.ptr);
	}
Martin Mareš's avatar
Martin Mareš committed
417
418
419
420
      mb_free(o);
    }
}

Ondřej Zajíček's avatar
Ondřej Zajíček committed
421
422
423
424
425
426
427
428
429
430
431
432
static int
get_generic_attr(eattr *a, byte **buf, int buflen UNUSED)
{
  if (a->id == EA_GEN_IGP_METRIC)
    {
      *buf += bsprintf(*buf, "igp_metric");
      return GA_NAME;
    }
 
  return GA_UNKNOWN;
}

433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
static inline void
opaque_format(struct adata *ad, byte *buf, unsigned int size)
{
  byte *bound = buf + size - 10;
  int i;

  for(i = 0; i < ad->length; i++)
    {
      if (buf > bound)
	{
	  strcpy(buf, " ...");
	  return;
	}
      if (i)
	*buf++ = ' ';

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

  *buf = 0;
  return;
}

static inline void
ea_show_int_set(struct cli *c, struct adata *ad, int way, byte *pos, byte *buf, byte *end)
{
  int i = int_set_format(ad, way, 0, pos, end - pos);
  cli_printf(c, -1012, "%s", buf);
  while (i)
    {
      i = int_set_format(ad, way, i, buf, end - buf - 1);
      cli_printf(c, -1012, "\t%s", buf);
    }
}

Ondřej Zajíček's avatar
Ondřej Zajíček committed
468
469
470
471
472
473
474
475
476
477
478
479
static inline void
ea_show_ec_set(struct cli *c, struct adata *ad, byte *pos, byte *buf, byte *end)
{
  int i = ec_set_format(ad, 0, pos, end - pos);
  cli_printf(c, -1012, "%s", buf);
  while (i)
    {
      i = ec_set_format(ad, i, buf, end - buf - 1);
      cli_printf(c, -1012, "\t%s", buf);
    }
}

480
/**
481
482
483
 * ea_show - print an &eattr to CLI
 * @c: destination CLI
 * @e: attribute to be printed
484
 *
485
486
 * This function takes an extended attribute represented by its &eattr
 * structure and prints it to the CLI according to the type information.
487
488
489
490
 *
 * If the protocol defining the attribute provides its own
 * get_attr() hook, it's consulted first.
 */
491
void
492
ea_show(struct cli *c, eattr *e)
493
494
495
496
{
  struct protocol *p;
  int status = GA_UNKNOWN;
  struct adata *ad = (e->type & EAF_EMBEDDED) ? NULL : e->u.ptr;
497
498
  byte buf[CLI_MSG_SIZE];
  byte *pos = buf, *end = buf + sizeof(buf);
499
500
501

  if (p = attr_class_to_protocol[EA_PROTO(e->id)])
    {
502
      pos += bsprintf(pos, "%s.", p->name);
503
      if (p->get_attr)
504
505
	status = p->get_attr(e, pos, end - pos);
      pos += strlen(pos);
506
507
    }
  else if (EA_PROTO(e->id))
508
    pos += bsprintf(pos, "%02x.", EA_PROTO(e->id));
Ondřej Zajíček's avatar
Ondřej Zajíček committed
509
  else 
510
    status = get_generic_attr(e, &pos, end - pos);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
511

512
  if (status < GA_NAME)
513
    pos += bsprintf(pos, "%02x", EA_ID(e->id));
514
515
  if (status < GA_FULL)
    {
516
517
      *pos++ = ':';
      *pos++ = ' ';
518
519
520
      switch (e->type & EAF_TYPE_MASK)
	{
	case EAF_TYPE_INT:
521
	  bsprintf(pos, "%u", e->u.data);
522
523
	  break;
	case EAF_TYPE_OPAQUE:
524
	  opaque_format(ad, pos, end - pos);
525
526
	  break;
	case EAF_TYPE_IP_ADDRESS:
527
	  bsprintf(pos, "%I", *(ip_addr *) ad->data);
528
529
	  break;
	case EAF_TYPE_ROUTER_ID:
530
	  bsprintf(pos, "%R", e->u.data);
531
	  break;
532
	case EAF_TYPE_AS_PATH:
533
	  as_path_format(ad, pos, end - pos);
534
535
	  break;
	case EAF_TYPE_INT_SET:
536
537
	  ea_show_int_set(c, ad, 1, pos, buf, end);
	  return;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
538
539
540
	case EAF_TYPE_EC_SET:
	  ea_show_ec_set(c, ad, pos, buf, end);
	  return;
541
542
	case EAF_TYPE_UNDEF:
	default:
543
	  bsprintf(pos, "<type %02x>", e->type);
544
545
	}
    }
546
  cli_printf(c, -1012, "%s", buf);
547
548
}

549
550
551
552
553
554
555
/**
 * ea_dump - dump an extended attribute
 * @e: attribute to be dumped
 *
 * ea_dump() dumps contents of the extended attribute given to
 * the debug output.
 */
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
void
ea_dump(ea_list *e)
{
  int i;

  if (!e)
    {
      debug("NONE");
      return;
    }
  while (e)
    {
      debug("[%c%c%c]",
	    (e->flags & EALF_SORTED) ? 'S' : 's',
	    (e->flags & EALF_BISECT) ? 'B' : 'b',
	    (e->flags & EALF_CACHED) ? 'C' : 'c');
      for(i=0; i<e->count; i++)
573
	{
574
575
	  eattr *a = &e->attrs[i];
	  debug(" %02x:%02x.%02x", EA_PROTO(a->id), EA_ID(a->id), a->flags);
576
577
	  if (a->type & EAF_TEMP)
	    debug("T");
578
	  debug("=%c", "?iO?I?P???S?????" [a->type & EAF_TYPE_MASK]);
579
580
	  if (a->type & EAF_ORIGINATED)
	    debug("o");
581
582
583
584
585
586
587
588
589
	  if (a->type & EAF_EMBEDDED)
	    debug(":%08x", a->u.data);
	  else
	    {
	      int j, len = a->u.ptr->length;
	      debug("[%d]:", len);
	      for(j=0; j<len; j++)
		debug("%02x", a->u.ptr->data[j]);
	    }
590
	}
591
592
      if (e = e->next)
	debug(" | ");
593
594
595
    }
}

596
597
598
599
600
601
602
/**
 * ea_hash - calculate an &ea_list hash key
 * @e: attribute list
 *
 * ea_hash() takes an extended attribute list and calculated a hopefully
 * uniformly distributed hash value from its contents.
 */
603
inline unsigned int
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
ea_hash(ea_list *e)
{
  u32 h = 0;
  int i;

  if (e)			/* Assuming chain of length 1 */
    {
      for(i=0; i<e->count; i++)
	{
	  struct eattr *a = &e->attrs[i];
	  h ^= a->id;
	  if (a->type & EAF_EMBEDDED)
	    h ^= a->u.data;
	  else
	    {
	      struct adata *d = a->u.ptr;
	      int size = d->length;
	      byte *z = d->data;
	      while (size >= 4)
		{
		  h ^= *(u32 *)z;
		  z += 4;
		  size -= 4;
		}
	      while (size--)
		h = (h >> 24) ^ (h << 8) ^ *z++;
	    }
	}
      h ^= h >> 16;
      h ^= h >> 6;
      h &= 0xffff;
    }
  return h;
}

639
640
641
642
643
644
645
646
/**
 * ea_append - concatenate &ea_list's
 * @to: destination list (can be %NULL)
 * @what: list to be appended (can be %NULL)
 *
 * This function appends the &ea_list @what at the end of
 * &ea_list @to and returns a pointer to the resulting list.
 */
647
648
649
650
651
652
653
654
655
656
657
658
659
660
ea_list *
ea_append(ea_list *to, ea_list *what)
{
  ea_list *res;

  if (!to)
    return what;
  res = to;
  while (to->next)
    to = to->next;
  to->next = what;
  return res;
}

661
662
663
664
/*
 *	rta's
 */

665
666
667
668
669
670
671
672
673
static unsigned int rta_cache_count;
static unsigned int rta_cache_size = 32;
static unsigned int rta_cache_limit;
static unsigned int rta_cache_mask;
static rta **rta_hash_table;

static void
rta_alloc_hash(void)
{
Martin Mareš's avatar
Martin Mareš committed
674
  rta_hash_table = mb_allocz(rta_pool, sizeof(rta *) * rta_cache_size);
675
676
677
678
679
680
681
682
683
684
  if (rta_cache_size < 32768)
    rta_cache_limit = rta_cache_size * 2;
  else
    rta_cache_limit = ~0;
  rta_cache_mask = rta_cache_size - 1;
}

static inline unsigned int
rta_hash(rta *a)
{
Ondřej Zajíček's avatar
Ondřej Zajíček committed
685
686
  return (a->proto->hash_key ^ ipa_hash(a->gw) ^
	  mpnh_hash(a->nexthops) ^ ea_hash(a->eattrs)) & 0xffff;
687
688
}

689
690
691
692
693
694
695
696
697
static inline int
rta_same(rta *x, rta *y)
{
  return (x->proto == y->proto &&
	  x->source == y->source &&
	  x->scope == y->scope &&
	  x->cast == y->cast &&
	  x->dest == y->dest &&
	  x->flags == y->flags &&
698
	  x->igp_metric == y->igp_metric &&
699
700
701
	  ipa_equal(x->gw, y->gw) &&
	  ipa_equal(x->from, y->from) &&
	  x->iface == y->iface &&
702
	  x->hostentry == y->hostentry &&
Ondřej Zajíček's avatar
Ondřej Zajíček committed
703
	  mpnh_same(x->nexthops, y->nexthops) &&
704
	  ea_same(x->eattrs, y->eattrs));
705
706
707
708
709
710
711
712
713
}

static rta *
rta_copy(rta *o)
{
  rta *r = sl_alloc(rta_slab);

  memcpy(r, o, sizeof(rta));
  r->uc = 1;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
714
  r->nexthops = mpnh_copy(o->nexthops);
715
  r->eattrs = ea_list_copy(o->eattrs);
716
717
718
  return r;
}

719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
static inline void
rta_insert(rta *r)
{
  unsigned int h = r->hash_key & rta_cache_mask;
  r->next = rta_hash_table[h];
  if (r->next)
    r->next->pprev = &r->next;
  r->pprev = &rta_hash_table[h];
  rta_hash_table[h] = r;
}

static void
rta_rehash(void)
{
  unsigned int ohs = rta_cache_size;
  unsigned int h;
  rta *r, *n;
  rta **oht = rta_hash_table;

  rta_cache_size = 2*rta_cache_size;
  DBG("Rehashing rta cache from %d to %d entries.\n", ohs, rta_cache_size);
  rta_alloc_hash();
  for(h=0; h<ohs; h++)
    for(r=oht[h]; r; r=n)
      {
	n = r->next;
	rta_insert(r);
      }
  mb_free(oht);
}

750
751
/**
 * rta_lookup - look up a &rta in attribute cache
Martin Mareš's avatar
Martin Mareš committed
752
 * @o: a un-cached &rta
753
 *
Martin Mareš's avatar
Martin Mareš committed
754
 * rta_lookup() gets an un-cached &rta structure and returns its cached
755
756
757
758
759
760
761
762
 * counterpart. It starts with examining the attribute cache to see whether
 * there exists a matching entry. If such an entry exists, it's returned and
 * its use count is incremented, else a new entry is created with use count
 * set to 1.
 *
 * The extended attribute lists attached to the &rta are automatically
 * converted to the normalized form.
 */
763
764
765
766
rta *
rta_lookup(rta *o)
{
  rta *r;
767
  unsigned int h;
768

769
  ASSERT(!(o->aflags & RTAF_CACHED));
770
  if (o->eattrs)
771
    {
772
      if (o->eattrs->next)	/* Multiple ea_list's, need to merge them */
773
	{
774
775
776
	  ea_list *ml = alloca(ea_scan(o->eattrs));
	  ea_merge(o->eattrs, ml);
	  o->eattrs = ml;
777
	}
778
      ea_sort(o->eattrs);
779
780
    }

781
782
783
  h = rta_hash(o);
  for(r=rta_hash_table[h & rta_cache_mask]; r; r=r->next)
    if (r->hash_key == h && rta_same(r, o))
784
      return rta_clone(r);
785

786
  r = rta_copy(o);
787
  r->hash_key = h;
788
  r->aflags = RTAF_CACHED;
789
  rt_lock_hostentry(r->hostentry);
790
791
792
793
794
  rta_insert(r);

  if (++rta_cache_count > rta_cache_limit)
    rta_rehash();

795
796
797
798
  return r;
}

void
799
rta__free(rta *a)
800
{
801
802
  ASSERT(rta_cache_count && (a->aflags & RTAF_CACHED));
  rta_cache_count--;
Martin Mareš's avatar
Martin Mareš committed
803
804
805
806
  *a->pprev = a->next;
  if (a->next)
    a->next->pprev = a->pprev;
  a->aflags = 0;		/* Poison the entry */
807
  rt_unlock_hostentry(a->hostentry);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
808
  mpnh_free(a->nexthops);
Martin Mareš's avatar
Martin Mareš committed
809
810
  ea_free(a->eattrs);
  sl_free(rta_slab, a);
811
812
}

813
814
815
816
817
818
/**
 * rta_dump - dump route attributes
 * @a: attribute structure to dump
 *
 * This function takes a &rta and dumps its contents to the debug output.
 */
819
void
820
rta_dump(rta *a)
821
{
822
  static char *rts[] = { "RTS_DUMMY", "RTS_STATIC", "RTS_INHERIT", "RTS_DEVICE",
Martin Mareš's avatar
Martin Mareš committed
823
			 "RTS_STAT_DEV", "RTS_REDIR", "RTS_RIP",
Ondřej Filip's avatar
Ondřej Filip committed
824
825
			 "RTS_OSPF", "RTS_OSPF_IA", "RTS_OSPF_EXT1",
                         "RTS_OSPF_EXT2", "RTS_BGP" };
826
827
828
  static char *rtc[] = { "", " BC", " MC", " AC" };
  static char *rtd[] = { "", " DEV", " HOLE", " UNREACH", " PROHIBIT" };

829
  debug("p=%s uc=%d %s %s%s%s h=%04x",
830
	a->proto->name, a->uc, rts[a->source], ip_scope_text(a->scope), rtc[a->cast],
831
	rtd[a->dest], a->hash_key);
832
833
  if (!(a->aflags & RTAF_CACHED))
    debug(" !CACHED");
834
  debug(" <-%I", a->from);
835
  if (a->dest == RTD_ROUTER)
836
    debug(" ->%I", a->gw);
837
  if (a->dest == RTD_DEVICE || a->dest == RTD_ROUTER)
838
    debug(" [%s]", a->iface ? a->iface->name : "???" );
839
  if (a->eattrs)
840
841
    {
      debug(" EA: ");
842
      ea_dump(a->eattrs);
843
    }
844
845
}

846
847
848
849
850
851
/**
 * rta_dump_all - dump attribute cache
 *
 * This function dumps the whole contents of route attribute cache
 * to the debug output.
 */
852
853
854
void
rta_dump_all(void)
{
855
  rta *a;
856
857
858
859
860
861
862
863
864
865
  unsigned int h;

  debug("Route attribute cache (%d entries, rehash at %d):\n", rta_cache_count, rta_cache_limit);
  for(h=0; h<rta_cache_size; h++)
    for(a=rta_hash_table[h]; a; a=a->next)
      {
	debug("%p ", a);
	rta_dump(a);
	debug("\n");
      }
866
  debug("\n");
867
868
}

869
void
870
rta_show(struct cli *c, rta *a, ea_list *eal)
871
872
{
  static char *src_names[] = { "dummy", "static", "inherit", "device", "static-device", "redirect",
873
			       "RIP", "OSPF", "OSPF-IA", "OSPF-E1", "OSPF-E2", "BGP", "pipe" };
874
  static char *cast_names[] = { "unicast", "broadcast", "multicast", "anycast" };
875
  int i;
876
877

  cli_printf(c, -1008, "\tType: %s %s %s", src_names[a->source], cast_names[a->cast], ip_scope_text(a->scope));
878
879
880
  if (!eal)
    eal = a->eattrs;
  for(; eal; eal=eal->next)
881
    for(i=0; i<eal->count; i++)
882
      ea_show(c, &eal->attrs[i]);
883
884
}

885
886
887
888
889
890
/**
 * rta_init - initialize route attribute cache
 *
 * This function is called during initialization of the routing
 * table module to set up the internals of the attribute cache.
 */
891
892
893
void
rta_init(void)
{
Martin Mareš's avatar
Martin Mareš committed
894
  rta_pool = rp_new(&root_pool, "Attributes");
895
  rta_slab = sl_new(rta_pool, sizeof(rta));
Ondřej Zajíček's avatar
Ondřej Zajíček committed
896
  mpnh_slab = sl_new(rta_pool, sizeof(struct mpnh));
897
  rta_alloc_hash();
898
}
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928

/*
 *  Documentation for functions declared inline in route.h
 */
#if 0

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

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

#endif