]> git.ipfire.org Git - thirdparty/bird.git/blame - nest/rt-attr.c
Merge branch 'master' into int-new
[thirdparty/bird.git] / nest / rt-attr.c
CommitLineData
2326b001
MM
1/*
2 * BIRD -- Route Attribute Cache
3 *
ee76a92a 4 * (c) 1998--2000 Martin Mares <mj@ucw.cz>
2326b001
MM
5 *
6 * Can be freely distributed and used under the terms of the GNU GPL.
7 */
8
3ce8c610
MM
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
2e9b2421 24 * in the &ea_list chain and in such case the first occurrence overrides
3ce8c610
MM
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 *
2e9b2421 36 * There exist two variants of &rta's -- cached and un-cached ones. Un-cached
3ce8c610
MM
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
2326b001
MM
47#include "nest/bird.h"
48#include "nest/route.h"
49#include "nest/protocol.h"
66e53309 50#include "nest/iface.h"
730f2e2c 51#include "nest/cli.h"
c6add07f 52#include "nest/attrs.h"
10af3676 53#include "lib/alloca.h"
e7d2ac44 54#include "lib/hash.h"
74c838a8 55#include "lib/idm.h"
2326b001 56#include "lib/resource.h"
221135d6 57#include "lib/string.h"
2326b001 58
9a74622c
JMM
59#include <stddef.h>
60
665be7f6
OZ
61const char * rta_dest_names[RTD_MAX] = {
62 [RTD_NONE] = "",
63 [RTD_UNICAST] = "unicast",
64 [RTD_BLACKHOLE] = "blackhole",
65 [RTD_UNREACHABLE] = "unreachable",
66 [RTD_PROHIBIT] = "prohibited",
67};
68
acb60628
OZ
69pool *rta_pool;
70
ec5e5d23
JMM
71static slab *rta_slab_[4];
72static slab *nexthop_slab_[4];
094d2bdb
OZ
73static slab *rte_src_slab;
74
74c838a8 75static struct idm src_ids;
e7d2ac44 76#define SRC_ID_INIT_SIZE 4
094d2bdb
OZ
77
78/* rte source hash */
e7d2ac44
OZ
79
80#define RSH_KEY(n) n->proto, n->private_id
81#define RSH_NEXT(n) n->next
82#define RSH_EQ(p1,n1,p2,n2) p1 == p2 && n1 == n2
83#define RSH_FN(p,n) p->hash_key ^ u32_hash(n)
84
85#define RSH_REHASH rte_src_rehash
86#define RSH_PARAMS /2, *2, 1, 1, 8, 20
87#define RSH_INIT_ORDER 6
88
89static HASH(struct rte_src) src_hash;
2326b001 90
3991d84e
MM
91struct protocol *attr_class_to_protocol[EAP_MAX];
92
094d2bdb
OZ
93
94static void
95rte_src_init(void)
96{
97 rte_src_slab = sl_new(rta_pool, sizeof(struct rte_src));
98
74c838a8 99 idm_init(&src_ids, rta_pool, SRC_ID_INIT_SIZE);
094d2bdb 100
e7d2ac44 101 HASH_INIT(src_hash, rta_pool, RSH_INIT_ORDER);
094d2bdb
OZ
102}
103
094d2bdb 104
e7d2ac44 105HASH_DEFINE_REHASH_FN(RSH, struct rte_src)
094d2bdb
OZ
106
107struct rte_src *
108rt_find_source(struct proto *p, u32 id)
109{
e7d2ac44 110 return HASH_FIND(src_hash, RSH, p, id);
094d2bdb
OZ
111}
112
113struct rte_src *
114rt_get_source(struct proto *p, u32 id)
115{
e7d2ac44 116 struct rte_src *src = rt_find_source(p, id);
094d2bdb 117
e7d2ac44
OZ
118 if (src)
119 return src;
094d2bdb
OZ
120
121 src = sl_alloc(rte_src_slab);
122 src->proto = p;
123 src->private_id = id;
74c838a8 124 src->global_id = idm_alloc(&src_ids);
094d2bdb 125 src->uc = 0;
d217ba51 126
e7d2ac44 127 HASH_INSERT2(src_hash, RSH, rta_pool, src);
094d2bdb
OZ
128
129 return src;
130}
131
094d2bdb
OZ
132void
133rt_prune_sources(void)
134{
e7d2ac44
OZ
135 HASH_WALK_FILTER(src_hash, next, src, sp)
136 {
137 if (src->uc == 0)
094d2bdb 138 {
e7d2ac44 139 HASH_DO_REMOVE(src_hash, RSH, sp);
74c838a8 140 idm_free(&src_ids, src->global_id);
e7d2ac44 141 sl_free(rte_src_slab, src);
094d2bdb 142 }
e7d2ac44
OZ
143 }
144 HASH_WALK_FILTER_END;
094d2bdb 145
e7d2ac44 146 HASH_MAY_RESIZE_DOWN(src_hash, RSH, rta_pool);
094d2bdb
OZ
147}
148
149
150/*
151 * Multipath Next Hop
152 */
153
04632fd7 154static inline u32
4e276a89 155nexthop_hash(struct nexthop *x)
7e95c05d 156{
04632fd7 157 u32 h = 0;
7e95c05d 158 for (; x; x = x->next)
ec5e5d23
JMM
159 {
160 h ^= ipa_hash(x->gw) ^ (h << 5) ^ (h >> 9);
62e64905
OZ
161
162 for (int i = 0; i < x->labels; i++)
ec5e5d23
JMM
163 h ^= x->label[i] ^ (h << 6) ^ (h >> 7);
164 }
7e95c05d
OZ
165
166 return h;
167}
168
169int
4e276a89 170nexthop__same(struct nexthop *x, struct nexthop *y)
7e95c05d
OZ
171{
172 for (; x && y; x = x->next, y = y->next)
ec5e5d23
JMM
173 {
174 if (!ipa_equal(x->gw, y->gw) || (x->iface != y->iface) || (x->weight != y->weight) || (x->labels != y->labels))
7e95c05d 175 return 0;
62e64905
OZ
176
177 for (int i = 0; i < x->labels; i++)
ec5e5d23
JMM
178 if (x->label[i] != y->label[i])
179 return 0;
180 }
7e95c05d 181
62e64905 182 return x == y;
7e95c05d
OZ
183}
184
d217ba51 185static int
4e276a89 186nexthop_compare_node(struct nexthop *x, struct nexthop *y)
d217ba51
OZ
187{
188 int r;
189
190 if (!x)
191 return 1;
192
193 if (!y)
194 return -1;
195
196 r = ((int) y->weight) - ((int) x->weight);
197 if (r)
198 return r;
199
200 r = ipa_compare(x->gw, y->gw);
201 if (r)
202 return r;
203
ec5e5d23
JMM
204 r = ((int) y->labels) - ((int) x->labels);
205 if (r)
206 return r;
207
62e64905 208 for (int i = 0; i < y->labels; i++)
ec5e5d23
JMM
209 {
210 r = ((int) y->label[i]) - ((int) x->label[i]);
211 if (r)
212 return r;
213 }
214
d217ba51
OZ
215 return ((int) x->iface->index) - ((int) y->iface->index);
216}
217
4e276a89
JMM
218static inline struct nexthop *
219nexthop_copy_node(const struct nexthop *src, linpool *lp)
d217ba51 220{
ec5e5d23
JMM
221 struct nexthop *n = lp_alloc(lp, nexthop_size(src));
222
223 memcpy(n, src, nexthop_size(src));
d217ba51 224 n->next = NULL;
ec5e5d23 225
d217ba51
OZ
226 return n;
227}
228
229/**
4e276a89 230 * nexthop_merge - merge nexthop lists
d217ba51
OZ
231 * @x: list 1
232 * @y: list 2
233 * @rx: reusability of list @x
234 * @ry: reusability of list @y
235 * @max: max number of nexthops
236 * @lp: linpool for allocating nexthops
237 *
4e276a89 238 * The nexthop_merge() function takes two nexthop lists @x and @y and merges them,
d217ba51
OZ
239 * eliminating possible duplicates. The input lists must be sorted and the
240 * result is sorted too. The number of nexthops in result is limited by @max.
241 * New nodes are allocated from linpool @lp.
242 *
243 * The arguments @rx and @ry specify whether corresponding input lists may be
244 * consumed by the function (i.e. their nodes reused in the resulting list), in
245 * that case the caller should not access these lists after that. To eliminate
246 * issues with deallocation of these lists, the caller should use some form of
247 * bulk deallocation (e.g. stack or linpool) to free these nodes when the
248 * resulting list is no longer needed. When reusability is not set, the
249 * corresponding lists are not modified nor linked from the resulting list.
250 */
4e276a89
JMM
251struct nexthop *
252nexthop_merge(struct nexthop *x, struct nexthop *y, int rx, int ry, int max, linpool *lp)
d217ba51 253{
4e276a89
JMM
254 struct nexthop *root = NULL;
255 struct nexthop **n = &root;
d217ba51
OZ
256
257 while ((x || y) && max--)
258 {
4e276a89 259 int cmp = nexthop_compare_node(x, y);
d217ba51
OZ
260 if (cmp < 0)
261 {
4e276a89 262 *n = rx ? x : nexthop_copy_node(x, lp);
d217ba51
OZ
263 x = x->next;
264 }
265 else if (cmp > 0)
266 {
4e276a89 267 *n = ry ? y : nexthop_copy_node(y, lp);
d217ba51
OZ
268 y = y->next;
269 }
270 else
271 {
4e276a89 272 *n = rx ? x : (ry ? y : nexthop_copy_node(x, lp));
d217ba51
OZ
273 x = x->next;
274 y = y->next;
275 }
276 n = &((*n)->next);
277 }
278 *n = NULL;
279
280 return root;
281}
282
84cac51a 283void
62e64905 284nexthop_insert(struct nexthop **n, struct nexthop *x)
84cac51a 285{
62e64905 286 for (; *n; n = &((*n)->next))
4e276a89 287 {
62e64905 288 int cmp = nexthop_compare_node(*n, x);
84cac51a
OZ
289
290 if (cmp < 0)
291 continue;
62e64905
OZ
292 else if (cmp > 0)
293 break;
294 else
295 return;
84cac51a
OZ
296 }
297
62e64905
OZ
298 x->next = *n;
299 *n = x;
84cac51a
OZ
300}
301
302int
4e276a89 303nexthop_is_sorted(struct nexthop *x)
84cac51a
OZ
304{
305 for (; x && x->next; x = x->next)
4e276a89 306 if (nexthop_compare_node(x, x->next) >= 0)
84cac51a
OZ
307 return 0;
308
309 return 1;
310}
d217ba51 311
ec5e5d23
JMM
312static inline slab *
313nexthop_slab(struct nexthop *nh)
314{
62e64905 315 return nexthop_slab_[MIN(nh->labels, 3)];
ec5e5d23
JMM
316}
317
4e276a89
JMM
318static struct nexthop *
319nexthop_copy(struct nexthop *o)
7e95c05d 320{
4e276a89
JMM
321 struct nexthop *first = NULL;
322 struct nexthop **last = &first;
7e95c05d
OZ
323
324 for (; o; o = o->next)
325 {
ec5e5d23 326 struct nexthop *n = sl_alloc(nexthop_slab(o));
7e95c05d
OZ
327 n->gw = o->gw;
328 n->iface = o->iface;
329 n->next = NULL;
330 n->weight = o->weight;
f2010f9c
JMM
331 n->labels = o->labels;
332 for (int i=0; i<o->labels; i++)
333 n->label[i] = o->label[i];
7e95c05d
OZ
334
335 *last = n;
336 last = &(n->next);
337 }
338
339 return first;
340}
341
342static void
4e276a89 343nexthop_free(struct nexthop *o)
7e95c05d 344{
4e276a89 345 struct nexthop *n;
7e95c05d
OZ
346
347 while (o)
348 {
349 n = o->next;
ec5e5d23 350 sl_free(nexthop_slab(o), o);
7e95c05d
OZ
351 o = n;
352 }
353}
354
355
b77ae37d
MM
356/*
357 * Extended Attributes
358 */
359
8d24b689
MM
360static inline eattr *
361ea__find(ea_list *e, unsigned id)
b77ae37d
MM
362{
363 eattr *a;
364 int l, r, m;
365
366 while (e)
367 {
368 if (e->flags & EALF_BISECT)
369 {
370 l = 0;
fee78355 371 r = e->count - 1;
b77ae37d
MM
372 while (l <= r)
373 {
374 m = (l+r) / 2;
375 a = &e->attrs[m];
376 if (a->id == id)
377 return a;
378 else if (a->id < id)
379 l = m+1;
380 else
381 r = m-1;
382 }
383 }
384 else
385 for(m=0; m<e->count; m++)
386 if (e->attrs[m].id == id)
387 return &e->attrs[m];
388 e = e->next;
389 }
390 return NULL;
391}
392
3ce8c610
MM
393/**
394 * ea_find - find an extended attribute
395 * @e: attribute list to search in
396 * @id: attribute ID to search for
397 *
398 * Given an extended attribute list, ea_find() searches for a first
2e9b2421 399 * occurrence of an attribute with specified ID, returning either a pointer
3ce8c610
MM
400 * to its &eattr structure or %NULL if no such attribute exists.
401 */
8d24b689
MM
402eattr *
403ea_find(ea_list *e, unsigned id)
404{
405 eattr *a = ea__find(e, id & EA_CODE_MASK);
406
407 if (a && (a->type & EAF_TYPE_MASK) == EAF_TYPE_UNDEF &&
408 !(id & EA_ALLOW_UNDEF))
409 return NULL;
410 return a;
411}
412
9fdf9d29
OZ
413/**
414 * ea_walk - walk through extended attributes
415 * @s: walk state structure
416 * @id: start of attribute ID interval
417 * @max: length of attribute ID interval
418 *
419 * Given an extended attribute list, ea_walk() walks through the list looking
420 * for first occurrences of attributes with ID in specified interval from @id to
421 * (@id + @max - 1), returning pointers to found &eattr structures, storing its
422 * walk state in @s for subsequent calls.
8e433d6a 423 *
9fdf9d29
OZ
424 * The function ea_walk() is supposed to be called in a loop, with initially
425 * zeroed walk state structure @s with filled the initial extended attribute
426 * list, returning one found attribute in each call or %NULL when no other
427 * attribute exists. The extended attribute list or the arguments should not be
428 * modified between calls. The maximum value of @max is 128.
429 */
430eattr *
431ea_walk(struct ea_walk_state *s, uint id, uint max)
432{
433 ea_list *e = s->eattrs;
434 eattr *a = s->ea;
435 eattr *a_max;
436
437 max = id + max;
438
439 if (a)
440 goto step;
441
442 for (; e; e = e->next)
443 {
444 if (e->flags & EALF_BISECT)
445 {
446 int l, r, m;
447
448 l = 0;
449 r = e->count - 1;
450 while (l < r)
451 {
452 m = (l+r) / 2;
453 if (e->attrs[m].id < id)
454 l = m + 1;
455 else
456 r = m;
457 }
458 a = e->attrs + l;
459 }
460 else
461 a = e->attrs;
462
463 step:
464 a_max = e->attrs + e->count;
465 for (; a < a_max; a++)
466 if ((a->id >= id) && (a->id < max))
467 {
468 int n = a->id - id;
469
470 if (BIT32_TEST(s->visited, n))
471 continue;
472
473 BIT32_SET(s->visited, n);
474
475 if ((a->type & EAF_TYPE_MASK) == EAF_TYPE_UNDEF)
476 continue;
477
478 s->eattrs = e;
479 s->ea = a;
480 return a;
481 }
482 else if (e->flags & EALF_BISECT)
483 break;
484 }
485
486 return NULL;
487}
488
3ce8c610
MM
489/**
490 * ea_get_int - fetch an integer attribute
491 * @e: attribute list
492 * @id: attribute ID
493 * @def: default value
494 *
495 * This function is a shortcut for retrieving a value of an integer attribute
496 * by calling ea_find() to find the attribute, extracting its value or returning
497 * a provided default if no such attribute is present.
498 */
c0100454
PM
499int
500ea_get_int(ea_list *e, unsigned id, int def)
501{
502 eattr *a = ea_find(e, id);
503 if (!a)
504 return def;
505 return a->u.data;
506}
507
b77ae37d
MM
508static inline void
509ea_do_sort(ea_list *e)
510{
511 unsigned n = e->count;
512 eattr *a = e->attrs;
513 eattr *b = alloca(n * sizeof(eattr));
514 unsigned s, ss;
515
516 /* We need to use a stable sorting algorithm, hence mergesort */
517 do
518 {
519 s = ss = 0;
520 while (s < n)
521 {
522 eattr *p, *q, *lo, *hi;
523 p = b;
524 ss = s;
525 *p++ = a[s++];
526 while (s < n && p[-1].id <= a[s].id)
527 *p++ = a[s++];
528 if (s < n)
529 {
530 q = p;
531 *p++ = a[s++];
532 while (s < n && p[-1].id <= a[s].id)
533 *p++ = a[s++];
534 lo = b;
535 hi = q;
536 s = ss;
537 while (lo < q && hi < p)
538 if (lo->id <= hi->id)
539 a[s++] = *lo++;
540 else
541 a[s++] = *hi++;
542 while (lo < q)
543 a[s++] = *lo++;
544 while (hi < p)
545 a[s++] = *hi++;
546 }
547 }
548 }
549 while (ss);
550}
551
552static inline void
553ea_do_prune(ea_list *e)
554{
51a183af 555 eattr *s, *d, *l, *s0;
8d24b689
MM
556 int i = 0;
557
558 /* Discard duplicates and undefs. Do you remember sorting was stable? */
559 s = d = e->attrs;
560 l = e->attrs + e->count;
561 while (s < l)
562 {
51a183af
MM
563 s0 = s++;
564 while (s < l && s->id == s[-1].id)
565 s++;
566 /* s0 is the most recent version, s[-1] the oldest one */
567 if ((s0->type & EAF_TYPE_MASK) != EAF_TYPE_UNDEF)
8d24b689 568 {
51a183af 569 *d = *s0;
d15b0b0a 570 d->type = (d->type & ~(EAF_ORIGINATED|EAF_FRESH)) | (s[-1].type & EAF_ORIGINATED);
51a183af 571 d++;
8d24b689
MM
572 i++;
573 }
8d24b689
MM
574 }
575 e->count = i;
b77ae37d
MM
576}
577
3ce8c610
MM
578/**
579 * ea_sort - sort an attribute list
580 * @e: list to be sorted
581 *
582 * This function takes a &ea_list chain and sorts the attributes
583 * within each of its entries.
584 *
585 * If an attribute occurs multiple times in a single &ea_list,
2e9b2421 586 * ea_sort() leaves only the first (the only significant) occurrence.
3ce8c610 587 */
b77ae37d
MM
588void
589ea_sort(ea_list *e)
590{
591 while (e)
592 {
593 if (!(e->flags & EALF_SORTED))
594 {
595 ea_do_sort(e);
596 ea_do_prune(e);
597 e->flags |= EALF_SORTED;
598 }
b77ae37d 599 if (e->count > 5)
b77ae37d
MM
600 e->flags |= EALF_BISECT;
601 e = e->next;
602 }
603}
604
3ce8c610
MM
605/**
606 * ea_scan - estimate attribute list size
607 * @e: attribute list
608 *
609 * This function calculates an upper bound of the size of
610 * a given &ea_list after merging with ea_merge().
611 */
b77ae37d
MM
612unsigned
613ea_scan(ea_list *e)
614{
615 unsigned cnt = 0;
616
617 while (e)
618 {
619 cnt += e->count;
620 e = e->next;
621 }
622 return sizeof(ea_list) + sizeof(eattr)*cnt;
623}
624
3ce8c610
MM
625/**
626 * ea_merge - merge segments of an attribute list
627 * @e: attribute list
628 * @t: buffer to store the result to
629 *
630 * This function takes a possibly multi-segment attribute list
631 * and merges all of its segments to one.
632 *
633 * The primary use of this function is for &ea_list normalization:
634 * first call ea_scan() to determine how much memory will the result
635 * take, then allocate a buffer (usually using alloca()), merge the
636 * segments with ea_merge() and finally sort and prune the result
637 * by calling ea_sort().
638 */
b77ae37d
MM
639void
640ea_merge(ea_list *e, ea_list *t)
641{
642 eattr *d = t->attrs;
643
644 t->flags = 0;
645 t->count = 0;
646 t->next = NULL;
647 while (e)
648 {
649 memcpy(d, e->attrs, sizeof(eattr)*e->count);
650 t->count += e->count;
651 d += e->count;
652 e = e->next;
653 }
654}
655
3ce8c610
MM
656/**
657 * ea_same - compare two &ea_list's
658 * @x: attribute list
659 * @y: attribute list
660 *
661 * ea_same() compares two normalized attribute lists @x and @y and returns
662 * 1 if they contain the same attributes, 0 otherwise.
663 */
6f57dcc0 664int
2326b001
MM
665ea_same(ea_list *x, ea_list *y)
666{
667 int c;
668
b77ae37d
MM
669 if (!x || !y)
670 return x == y;
671 ASSERT(!x->next && !y->next);
672 if (x->count != y->count)
673 return 0;
674 for(c=0; c<x->count; c++)
2326b001 675 {
b77ae37d
MM
676 eattr *a = &x->attrs[c];
677 eattr *b = &y->attrs[c];
678
679 if (a->id != b->id ||
680 a->flags != b->flags ||
681 a->type != b->type ||
28a10f84 682 ((a->type & EAF_EMBEDDED) ? a->u.data != b->u.data : !adata_same(a->u.ptr, b->u.ptr)))
2326b001 683 return 0;
b77ae37d
MM
684 }
685 return 1;
686}
687
688static inline ea_list *
689ea_list_copy(ea_list *o)
690{
691 ea_list *n;
692 unsigned i, len;
693
694 if (!o)
695 return NULL;
696 ASSERT(!o->next);
697 len = sizeof(ea_list) + sizeof(eattr) * o->count;
698 n = mb_alloc(rta_pool, len);
699 memcpy(n, o, len);
700 n->flags |= EALF_CACHED;
701 for(i=0; i<o->count; i++)
702 {
703 eattr *a = &n->attrs[i];
08732b71 704 if (!(a->type & EAF_EMBEDDED))
b77ae37d
MM
705 {
706 unsigned size = sizeof(struct adata) + a->u.ptr->length;
707 struct adata *d = mb_alloc(rta_pool, size);
708 memcpy(d, a->u.ptr, size);
709 a->u.ptr = d;
710 }
711 }
712 return n;
713}
714
5d86aefb
MM
715static inline void
716ea_free(ea_list *o)
717{
3ced9b34
MM
718 int i;
719
5d86aefb
MM
720 if (o)
721 {
722 ASSERT(!o->next);
3ced9b34
MM
723 for(i=0; i<o->count; i++)
724 {
725 eattr *a = &o->attrs[i];
726 if (!(a->type & EAF_EMBEDDED))
727 mb_free(a->u.ptr);
728 }
5d86aefb
MM
729 mb_free(o);
730 }
731}
732
ba5e5940
OZ
733static int
734get_generic_attr(eattr *a, byte **buf, int buflen UNUSED)
735{
736 if (a->id == EA_GEN_IGP_METRIC)
737 {
738 *buf += bsprintf(*buf, "igp_metric");
739 return GA_NAME;
740 }
d217ba51 741
ba5e5940
OZ
742 return GA_UNKNOWN;
743}
744
315f23a0
OZ
745void
746ea_format_bitfield(struct eattr *a, byte *buf, int bufsize, const char **names, int min, int max)
747{
748 byte *bound = buf + bufsize - 32;
749 u32 data = a->u.data;
750 int i;
751
752 for (i = min; i < max; i++)
753 if ((data & (1u << i)) && names[i])
754 {
755 if (buf > bound)
756 {
757 strcpy(buf, " ...");
758 return;
759 }
760
761 buf += bsprintf(buf, " %s", names[i]);
762 data &= ~(1u << i);
763 }
764
765 if (data)
766 bsprintf(buf, " %08x", data);
767
768 return;
769}
770
fdf16eb6 771static inline void
ae80a2de 772opaque_format(struct adata *ad, byte *buf, uint size)
fdf16eb6
OZ
773{
774 byte *bound = buf + size - 10;
3e236955 775 uint i;
fdf16eb6
OZ
776
777 for(i = 0; i < ad->length; i++)
778 {
779 if (buf > bound)
780 {
781 strcpy(buf, " ...");
782 return;
783 }
784 if (i)
785 *buf++ = ' ';
786
787 buf += bsprintf(buf, "%02x", ad->data[i]);
788 }
789
790 *buf = 0;
791 return;
792}
793
794static inline void
795ea_show_int_set(struct cli *c, struct adata *ad, int way, byte *pos, byte *buf, byte *end)
796{
797 int i = int_set_format(ad, way, 0, pos, end - pos);
a52d52fa 798 cli_printf(c, -1012, "\t%s", buf);
fdf16eb6
OZ
799 while (i)
800 {
801 i = int_set_format(ad, way, i, buf, end - buf - 1);
a52d52fa 802 cli_printf(c, -1012, "\t\t%s", buf);
fdf16eb6
OZ
803 }
804}
805
42a0c054
OZ
806static inline void
807ea_show_ec_set(struct cli *c, struct adata *ad, byte *pos, byte *buf, byte *end)
808{
809 int i = ec_set_format(ad, 0, pos, end - pos);
a52d52fa 810 cli_printf(c, -1012, "\t%s", buf);
42a0c054
OZ
811 while (i)
812 {
813 i = ec_set_format(ad, i, buf, end - buf - 1);
a52d52fa 814 cli_printf(c, -1012, "\t\t%s", buf);
42a0c054
OZ
815 }
816}
817
66dbdbd9
OZ
818static inline void
819ea_show_lc_set(struct cli *c, struct adata *ad, byte *pos, byte *buf, byte *end)
820{
821 int i = lc_set_format(ad, 0, pos, end - pos);
822 cli_printf(c, -1012, "\t%s", buf);
823 while (i)
824 {
825 i = lc_set_format(ad, i, buf, end - buf - 1);
826 cli_printf(c, -1012, "\t\t%s", buf);
827 }
828}
829
3ce8c610 830/**
fdf16eb6
OZ
831 * ea_show - print an &eattr to CLI
832 * @c: destination CLI
833 * @e: attribute to be printed
3ce8c610 834 *
fdf16eb6
OZ
835 * This function takes an extended attribute represented by its &eattr
836 * structure and prints it to the CLI according to the type information.
3ce8c610
MM
837 *
838 * If the protocol defining the attribute provides its own
839 * get_attr() hook, it's consulted first.
840 */
3991d84e 841void
fdf16eb6 842ea_show(struct cli *c, eattr *e)
3991d84e
MM
843{
844 struct protocol *p;
845 int status = GA_UNKNOWN;
3991d84e 846 struct adata *ad = (e->type & EAF_EMBEDDED) ? NULL : e->u.ptr;
fdf16eb6
OZ
847 byte buf[CLI_MSG_SIZE];
848 byte *pos = buf, *end = buf + sizeof(buf);
3991d84e
MM
849
850 if (p = attr_class_to_protocol[EA_PROTO(e->id)])
851 {
fdf16eb6 852 pos += bsprintf(pos, "%s.", p->name);
3991d84e 853 if (p->get_attr)
fdf16eb6
OZ
854 status = p->get_attr(e, pos, end - pos);
855 pos += strlen(pos);
3991d84e
MM
856 }
857 else if (EA_PROTO(e->id))
fdf16eb6 858 pos += bsprintf(pos, "%02x.", EA_PROTO(e->id));
d217ba51 859 else
fdf16eb6 860 status = get_generic_attr(e, &pos, end - pos);
ba5e5940 861
3991d84e 862 if (status < GA_NAME)
fdf16eb6 863 pos += bsprintf(pos, "%02x", EA_ID(e->id));
3991d84e
MM
864 if (status < GA_FULL)
865 {
fdf16eb6
OZ
866 *pos++ = ':';
867 *pos++ = ' ';
3991d84e
MM
868 switch (e->type & EAF_TYPE_MASK)
869 {
870 case EAF_TYPE_INT:
fdf16eb6 871 bsprintf(pos, "%u", e->u.data);
3991d84e
MM
872 break;
873 case EAF_TYPE_OPAQUE:
fdf16eb6 874 opaque_format(ad, pos, end - pos);
3991d84e
MM
875 break;
876 case EAF_TYPE_IP_ADDRESS:
fdf16eb6 877 bsprintf(pos, "%I", *(ip_addr *) ad->data);
3991d84e
MM
878 break;
879 case EAF_TYPE_ROUTER_ID:
fdf16eb6 880 bsprintf(pos, "%R", e->u.data);
3991d84e 881 break;
c6add07f 882 case EAF_TYPE_AS_PATH:
fdf16eb6 883 as_path_format(ad, pos, end - pos);
c6add07f 884 break;
315f23a0
OZ
885 case EAF_TYPE_BITFIELD:
886 bsprintf(pos, "%08x", e->u.data);
887 break;
c6add07f 888 case EAF_TYPE_INT_SET:
fdf16eb6
OZ
889 ea_show_int_set(c, ad, 1, pos, buf, end);
890 return;
42a0c054
OZ
891 case EAF_TYPE_EC_SET:
892 ea_show_ec_set(c, ad, pos, buf, end);
893 return;
66dbdbd9
OZ
894 case EAF_TYPE_LC_SET:
895 ea_show_lc_set(c, ad, pos, buf, end);
896 return;
3991d84e
MM
897 case EAF_TYPE_UNDEF:
898 default:
fdf16eb6 899 bsprintf(pos, "<type %02x>", e->type);
3991d84e
MM
900 }
901 }
a52d52fa 902 cli_printf(c, -1012, "\t%s", buf);
3991d84e
MM
903}
904
3ce8c610
MM
905/**
906 * ea_dump - dump an extended attribute
907 * @e: attribute to be dumped
908 *
909 * ea_dump() dumps contents of the extended attribute given to
910 * the debug output.
911 */
b77ae37d
MM
912void
913ea_dump(ea_list *e)
914{
915 int i;
916
917 if (!e)
918 {
919 debug("NONE");
920 return;
921 }
922 while (e)
923 {
924 debug("[%c%c%c]",
925 (e->flags & EALF_SORTED) ? 'S' : 's',
926 (e->flags & EALF_BISECT) ? 'B' : 'b',
927 (e->flags & EALF_CACHED) ? 'C' : 'c');
928 for(i=0; i<e->count; i++)
2326b001 929 {
b77ae37d
MM
930 eattr *a = &e->attrs[i];
931 debug(" %02x:%02x.%02x", EA_PROTO(a->id), EA_ID(a->id), a->flags);
9f4929e7
MM
932 if (a->type & EAF_TEMP)
933 debug("T");
b77ae37d 934 debug("=%c", "?iO?I?P???S?????" [a->type & EAF_TYPE_MASK]);
51a183af
MM
935 if (a->type & EAF_ORIGINATED)
936 debug("o");
b77ae37d
MM
937 if (a->type & EAF_EMBEDDED)
938 debug(":%08x", a->u.data);
939 else
940 {
941 int j, len = a->u.ptr->length;
942 debug("[%d]:", len);
943 for(j=0; j<len; j++)
944 debug("%02x", a->u.ptr->data[j]);
945 }
2326b001 946 }
b77ae37d
MM
947 if (e = e->next)
948 debug(" | ");
2326b001 949 }
2326b001
MM
950}
951
3ce8c610
MM
952/**
953 * ea_hash - calculate an &ea_list hash key
954 * @e: attribute list
955 *
956 * ea_hash() takes an extended attribute list and calculated a hopefully
957 * uniformly distributed hash value from its contents.
958 */
ae80a2de 959inline uint
ee76a92a
MM
960ea_hash(ea_list *e)
961{
9a74622c
JMM
962 const u64 mul = 0x68576150f3d6847;
963 u64 h = 0xafcef24eda8b29;
ee76a92a
MM
964 int i;
965
966 if (e) /* Assuming chain of length 1 */
967 {
968 for(i=0; i<e->count; i++)
969 {
970 struct eattr *a = &e->attrs[i];
9a74622c 971 h ^= a->id; h *= mul;
ee76a92a
MM
972 if (a->type & EAF_EMBEDDED)
973 h ^= a->u.data;
974 else
975 {
976 struct adata *d = a->u.ptr;
9a74622c 977 h ^= mem_hash(d->data, d->length);
ee76a92a 978 }
9a74622c 979 h *= mul;
ee76a92a 980 }
ee76a92a 981 }
9a74622c 982 return (h >> 32) ^ (h & 0xffffffff);
ee76a92a
MM
983}
984
3ce8c610
MM
985/**
986 * ea_append - concatenate &ea_list's
987 * @to: destination list (can be %NULL)
988 * @what: list to be appended (can be %NULL)
989 *
990 * This function appends the &ea_list @what at the end of
991 * &ea_list @to and returns a pointer to the resulting list.
992 */
ce1da96e
MM
993ea_list *
994ea_append(ea_list *to, ea_list *what)
995{
996 ea_list *res;
997
998 if (!to)
999 return what;
1000 res = to;
1001 while (to->next)
1002 to = to->next;
1003 to->next = what;
1004 return res;
1005}
1006
b77ae37d
MM
1007/*
1008 * rta's
1009 */
1010
ae80a2de
PT
1011static uint rta_cache_count;
1012static uint rta_cache_size = 32;
1013static uint rta_cache_limit;
1014static uint rta_cache_mask;
ee76a92a
MM
1015static rta **rta_hash_table;
1016
1017static void
1018rta_alloc_hash(void)
1019{
5d86aefb 1020 rta_hash_table = mb_allocz(rta_pool, sizeof(rta *) * rta_cache_size);
ee76a92a
MM
1021 if (rta_cache_size < 32768)
1022 rta_cache_limit = rta_cache_size * 2;
1023 else
1024 rta_cache_limit = ~0;
1025 rta_cache_mask = rta_cache_size - 1;
1026}
1027
ae80a2de 1028static inline uint
ee76a92a
MM
1029rta_hash(rta *a)
1030{
d39d41fb 1031 u64 h;
54ac0bec 1032 mem_hash_init(&h);
d39d41fb 1033#define MIX(f) mem_hash_mix(&h, &(a->f), sizeof(a->f));
54ac0bec
JMM
1034 MIX(src);
1035 MIX(hostentry);
54ac0bec
JMM
1036 MIX(from);
1037 MIX(igp_metric);
5b208e29
JMM
1038 MIX(source);
1039 MIX(scope);
1040 MIX(dest);
d39d41fb 1041#undef MIX
54ac0bec 1042
4e276a89 1043 return mem_hash_value(&h) ^ nexthop_hash(&(a->nh)) ^ ea_hash(a->eattrs);
ee76a92a
MM
1044}
1045
2326b001
MM
1046static inline int
1047rta_same(rta *x, rta *y)
1048{
094d2bdb 1049 return (x->src == y->src &&
2326b001
MM
1050 x->source == y->source &&
1051 x->scope == y->scope &&
2326b001 1052 x->dest == y->dest &&
d1e146f2 1053 x->igp_metric == y->igp_metric &&
2326b001 1054 ipa_equal(x->from, y->from) &&
d1e146f2 1055 x->hostentry == y->hostentry &&
4e276a89 1056 nexthop_same(&(x->nh), &(y->nh)) &&
2727bb7c 1057 ea_same(x->eattrs, y->eattrs));
2326b001
MM
1058}
1059
ec5e5d23
JMM
1060static inline slab *
1061rta_slab(rta *a)
1062{
1063 return rta_slab_[a->nh.labels > 2 ? 3 : a->nh.labels];
1064}
1065
2326b001
MM
1066static rta *
1067rta_copy(rta *o)
1068{
ec5e5d23 1069 rta *r = sl_alloc(rta_slab(o));
2326b001 1070
ec5e5d23 1071 memcpy(r, o, rta_size(o));
2326b001 1072 r->uc = 1;
4e276a89 1073 r->nh.next = nexthop_copy(o->nh.next);
2727bb7c 1074 r->eattrs = ea_list_copy(o->eattrs);
2326b001
MM
1075 return r;
1076}
1077
ee76a92a
MM
1078static inline void
1079rta_insert(rta *r)
1080{
ae80a2de 1081 uint h = r->hash_key & rta_cache_mask;
ee76a92a
MM
1082 r->next = rta_hash_table[h];
1083 if (r->next)
1084 r->next->pprev = &r->next;
1085 r->pprev = &rta_hash_table[h];
1086 rta_hash_table[h] = r;
1087}
1088
1089static void
1090rta_rehash(void)
1091{
ae80a2de
PT
1092 uint ohs = rta_cache_size;
1093 uint h;
ee76a92a
MM
1094 rta *r, *n;
1095 rta **oht = rta_hash_table;
1096
1097 rta_cache_size = 2*rta_cache_size;
1098 DBG("Rehashing rta cache from %d to %d entries.\n", ohs, rta_cache_size);
1099 rta_alloc_hash();
1100 for(h=0; h<ohs; h++)
1101 for(r=oht[h]; r; r=n)
1102 {
1103 n = r->next;
1104 rta_insert(r);
1105 }
1106 mb_free(oht);
1107}
1108
3ce8c610
MM
1109/**
1110 * rta_lookup - look up a &rta in attribute cache
2e9b2421 1111 * @o: a un-cached &rta
3ce8c610 1112 *
2e9b2421 1113 * rta_lookup() gets an un-cached &rta structure and returns its cached
3ce8c610
MM
1114 * counterpart. It starts with examining the attribute cache to see whether
1115 * there exists a matching entry. If such an entry exists, it's returned and
1116 * its use count is incremented, else a new entry is created with use count
1117 * set to 1.
1118 *
1119 * The extended attribute lists attached to the &rta are automatically
1120 * converted to the normalized form.
1121 */
2326b001
MM
1122rta *
1123rta_lookup(rta *o)
1124{
1125 rta *r;
ae80a2de 1126 uint h;
2326b001 1127
b77ae37d 1128 ASSERT(!(o->aflags & RTAF_CACHED));
2727bb7c 1129 if (o->eattrs)
b77ae37d 1130 {
2727bb7c 1131 if (o->eattrs->next) /* Multiple ea_list's, need to merge them */
b77ae37d 1132 {
2727bb7c
MM
1133 ea_list *ml = alloca(ea_scan(o->eattrs));
1134 ea_merge(o->eattrs, ml);
1135 o->eattrs = ml;
b77ae37d 1136 }
2727bb7c 1137 ea_sort(o->eattrs);
b77ae37d
MM
1138 }
1139
ee76a92a
MM
1140 h = rta_hash(o);
1141 for(r=rta_hash_table[h & rta_cache_mask]; r; r=r->next)
1142 if (r->hash_key == h && rta_same(r, o))
2326b001 1143 return rta_clone(r);
b77ae37d 1144
2326b001 1145 r = rta_copy(o);
ee76a92a 1146 r->hash_key = h;
04925e90 1147 r->aflags = RTAF_CACHED;
094d2bdb 1148 rt_lock_source(r->src);
cfe34a31 1149 rt_lock_hostentry(r->hostentry);
ee76a92a
MM
1150 rta_insert(r);
1151
1152 if (++rta_cache_count > rta_cache_limit)
1153 rta_rehash();
1154
2326b001
MM
1155 return r;
1156}
1157
1158void
b77ae37d 1159rta__free(rta *a)
2326b001 1160{
ee76a92a
MM
1161 ASSERT(rta_cache_count && (a->aflags & RTAF_CACHED));
1162 rta_cache_count--;
5d86aefb
MM
1163 *a->pprev = a->next;
1164 if (a->next)
1165 a->next->pprev = a->pprev;
cfe34a31 1166 rt_unlock_hostentry(a->hostentry);
094d2bdb 1167 rt_unlock_source(a->src);
4e276a89
JMM
1168 if (a->nh.next)
1169 nexthop_free(a->nh.next);
5d86aefb 1170 ea_free(a->eattrs);
039a65d0 1171 a->aflags = 0; /* Poison the entry */
ec5e5d23 1172 sl_free(rta_slab(a), a);
2326b001
MM
1173}
1174
8d9eef17
OZ
1175rta *
1176rta_do_cow(rta *o, linpool *lp)
1177{
ec5e5d23
JMM
1178 rta *r = lp_alloc(lp, rta_size(o));
1179 memcpy(r, o, rta_size(o));
f2010f9c
JMM
1180 for (struct nexthop **nhn = &(r->nh.next), *nho = o->nh.next; nho; nho = nho->next)
1181 {
1182 *nhn = lp_alloc(lp, nexthop_size(nho));
1183 memcpy(*nhn, nho, nexthop_size(nho));
1184 nhn = &((*nhn)->next);
1185 }
8d9eef17
OZ
1186 r->aflags = 0;
1187 r->uc = 0;
1188 return r;
1189}
1190
3ce8c610
MM
1191/**
1192 * rta_dump - dump route attributes
1193 * @a: attribute structure to dump
1194 *
1195 * This function takes a &rta and dumps its contents to the debug output.
1196 */
2326b001 1197void
66e53309 1198rta_dump(rta *a)
2326b001 1199{
618533af 1200 static char *rts[] = { "RTS_DUMMY", "RTS_STATIC", "RTS_INHERIT", "RTS_DEVICE",
beaf86e1 1201 "RTS_STAT_DEV", "RTS_REDIR", "RTS_RIP",
98ac6176 1202 "RTS_OSPF", "RTS_OSPF_IA", "RTS_OSPF_EXT1",
12640c14 1203 "RTS_OSPF_EXT2", "RTS_BGP", "RTS_PIPE", "RTS_BABEL" };
66e53309
MM
1204 static char *rtd[] = { "", " DEV", " HOLE", " UNREACH", " PROHIBIT" };
1205
5b208e29
JMM
1206 debug("p=%s uc=%d %s %s%s h=%04x",
1207 a->src->proto->name, a->uc, rts[a->source], ip_scope_text(a->scope),
ee76a92a 1208 rtd[a->dest], a->hash_key);
04925e90
MM
1209 if (!(a->aflags & RTAF_CACHED))
1210 debug(" !CACHED");
962ba482 1211 debug(" <-%I", a->from);
4e276a89
JMM
1212 if (a->dest == RTD_UNICAST)
1213 for (struct nexthop *nh = &(a->nh); nh; nh = nh->next)
1214 {
1215 if (ipa_nonzero(nh->gw)) debug(" ->%I", nh->gw);
ec5e5d23
JMM
1216 if (nh->labels) debug(" L %d", nh->label[0]);
1217 for (int i=1; i<nh->labels; i++)
1218 debug("/%d", nh->label[i]);
4e276a89
JMM
1219 debug(" [%s]", nh->iface ? nh->iface->name : "???");
1220 }
2727bb7c 1221 if (a->eattrs)
b77ae37d
MM
1222 {
1223 debug(" EA: ");
2727bb7c 1224 ea_dump(a->eattrs);
b77ae37d 1225 }
2326b001
MM
1226}
1227
3ce8c610
MM
1228/**
1229 * rta_dump_all - dump attribute cache
1230 *
1231 * This function dumps the whole contents of route attribute cache
1232 * to the debug output.
1233 */
2326b001
MM
1234void
1235rta_dump_all(void)
1236{
66e53309 1237 rta *a;
ae80a2de 1238 uint h;
ee76a92a
MM
1239
1240 debug("Route attribute cache (%d entries, rehash at %d):\n", rta_cache_count, rta_cache_limit);
1241 for(h=0; h<rta_cache_size; h++)
1242 for(a=rta_hash_table[h]; a; a=a->next)
1243 {
1244 debug("%p ", a);
1245 rta_dump(a);
1246 debug("\n");
1247 }
66e53309 1248 debug("\n");
2326b001
MM
1249}
1250
730f2e2c 1251void
ce1da96e 1252rta_show(struct cli *c, rta *a, ea_list *eal)
730f2e2c
MM
1253{
1254 static char *src_names[] = { "dummy", "static", "inherit", "device", "static-device", "redirect",
6370d6f6 1255 "RIP", "OSPF", "OSPF-IA", "OSPF-E1", "OSPF-E2", "BGP", "pipe" };
3991d84e 1256 int i;
730f2e2c 1257
5b208e29 1258 cli_printf(c, -1008, "\tType: %s %s", src_names[a->source], ip_scope_text(a->scope));
ce1da96e
MM
1259 if (!eal)
1260 eal = a->eattrs;
1261 for(; eal; eal=eal->next)
3991d84e 1262 for(i=0; i<eal->count; i++)
fdf16eb6 1263 ea_show(c, &eal->attrs[i]);
730f2e2c
MM
1264}
1265
3ce8c610
MM
1266/**
1267 * rta_init - initialize route attribute cache
1268 *
1269 * This function is called during initialization of the routing
1270 * table module to set up the internals of the attribute cache.
1271 */
2326b001
MM
1272void
1273rta_init(void)
1274{
ed68a5c6 1275 rta_pool = rp_new(&root_pool, "Attributes");
ec5e5d23
JMM
1276
1277 rta_slab_[0] = sl_new(rta_pool, sizeof(rta));
1278 rta_slab_[1] = sl_new(rta_pool, sizeof(rta) + sizeof(u32));
1279 rta_slab_[2] = sl_new(rta_pool, sizeof(rta) + sizeof(u32)*2);
d14f8c3c 1280 rta_slab_[3] = sl_new(rta_pool, sizeof(rta) + sizeof(u32)*MPLS_MAX_LABEL_STACK);
ec5e5d23
JMM
1281
1282 nexthop_slab_[0] = sl_new(rta_pool, sizeof(struct nexthop));
1283 nexthop_slab_[1] = sl_new(rta_pool, sizeof(struct nexthop) + sizeof(u32));
1284 nexthop_slab_[2] = sl_new(rta_pool, sizeof(struct nexthop) + sizeof(u32)*2);
d14f8c3c 1285 nexthop_slab_[3] = sl_new(rta_pool, sizeof(struct nexthop) + sizeof(u32)*MPLS_MAX_LABEL_STACK);
ec5e5d23 1286
ee76a92a 1287 rta_alloc_hash();
094d2bdb 1288 rte_src_init();
2326b001 1289}
3ce8c610
MM
1290
1291/*
1292 * Documentation for functions declared inline in route.h
1293 */
1294#if 0
1295
1296/**
1297 * rta_clone - clone route attributes
1298 * @r: a &rta to be cloned
1299 *
1300 * rta_clone() takes a cached &rta and returns its identical cached
1301 * copy. Currently it works by just returning the original &rta with
1302 * its use count incremented.
1303 */
1304static inline rta *rta_clone(rta *r)
1305{ DUMMY; }
1306
1307/**
1308 * rta_free - free route attributes
1309 * @r: a &rta to be freed
1310 *
1311 * If you stop using a &rta (for example when deleting a route which uses
1312 * it), you need to call rta_free() to notify the attribute cache the
1313 * attribute is no longer in use and can be freed if you were the last
1314 * user (which rta_free() tests by inspecting the use count).
1315 */
1316static inline void rta_free(rta *r)
1317{ DUMMY; }
1318
1319#endif