]>
git.ipfire.org Git - thirdparty/bird.git/blob - nest/rt-attr.c
2 * BIRD -- Route Attribute Cache
4 * (c) 1998--2000 Martin Mares <mj@ucw.cz>
6 * Can be freely distributed and used under the terms of the GNU GPL.
10 * DOC: Route attribute cache
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.
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
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
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.
44 * Routing tables always contain only cached &rta's.
47 #include "nest/bird.h"
48 #include "nest/route.h"
49 #include "nest/protocol.h"
50 #include "nest/iface.h"
52 #include "nest/attrs.h"
53 #include "lib/alloca.h"
54 #include "lib/resource.h"
55 #include "lib/string.h"
57 static slab
*rta_slab
;
58 static pool
*rta_pool
;
60 struct protocol
*attr_class_to_protocol
[EAP_MAX
];
67 ea__find(ea_list
*e
, unsigned id
)
74 if (e
->flags
& EALF_BISECT
)
91 for(m
=0; m
<e
->count
; m
++)
92 if (e
->attrs
[m
].id
== id
)
100 * ea_find - find an extended attribute
101 * @e: attribute list to search in
102 * @id: attribute ID to search for
104 * Given an extended attribute list, ea_find() searches for a first
105 * occurrence of an attribute with specified ID, returning either a pointer
106 * to its &eattr structure or %NULL if no such attribute exists.
109 ea_find(ea_list
*e
, unsigned id
)
111 eattr
*a
= ea__find(e
, id
& EA_CODE_MASK
);
113 if (a
&& (a
->type
& EAF_TYPE_MASK
) == EAF_TYPE_UNDEF
&&
114 !(id
& EA_ALLOW_UNDEF
))
120 * ea_get_int - fetch an integer attribute
123 * @def: default value
125 * This function is a shortcut for retrieving a value of an integer attribute
126 * by calling ea_find() to find the attribute, extracting its value or returning
127 * a provided default if no such attribute is present.
130 ea_get_int(ea_list
*e
, unsigned id
, int def
)
132 eattr
*a
= ea_find(e
, id
);
139 ea_do_sort(ea_list
*e
)
141 unsigned n
= e
->count
;
143 eattr
*b
= alloca(n
* sizeof(eattr
));
146 /* We need to use a stable sorting algorithm, hence mergesort */
152 eattr
*p
, *q
, *lo
, *hi
;
156 while (s
< n
&& p
[-1].id
<= a
[s
].id
)
162 while (s
< n
&& p
[-1].id
<= a
[s
].id
)
167 while (lo
< q
&& hi
< p
)
168 if (lo
->id
<= hi
->id
)
183 ea_do_prune(ea_list
*e
)
185 eattr
*s
, *d
, *l
, *s0
;
188 /* Discard duplicates and undefs. Do you remember sorting was stable? */
190 l
= e
->attrs
+ e
->count
;
194 while (s
< l
&& s
->id
== s
[-1].id
)
196 /* s0 is the most recent version, s[-1] the oldest one */
197 if ((s0
->type
& EAF_TYPE_MASK
) != EAF_TYPE_UNDEF
)
200 d
->type
= (d
->type
& ~EAF_ORIGINATED
) | (s
[-1].type
& EAF_ORIGINATED
);
209 * ea_sort - sort an attribute list
210 * @e: list to be sorted
212 * This function takes a &ea_list chain and sorts the attributes
213 * within each of its entries.
215 * If an attribute occurs multiple times in a single &ea_list,
216 * ea_sort() leaves only the first (the only significant) occurrence.
223 if (!(e
->flags
& EALF_SORTED
))
227 e
->flags
|= EALF_SORTED
;
230 e
->flags
|= EALF_BISECT
;
236 * ea_scan - estimate attribute list size
239 * This function calculates an upper bound of the size of
240 * a given &ea_list after merging with ea_merge().
252 return sizeof(ea_list
) + sizeof(eattr
)*cnt
;
256 * ea_merge - merge segments of an attribute list
258 * @t: buffer to store the result to
260 * This function takes a possibly multi-segment attribute list
261 * and merges all of its segments to one.
263 * The primary use of this function is for &ea_list normalization:
264 * first call ea_scan() to determine how much memory will the result
265 * take, then allocate a buffer (usually using alloca()), merge the
266 * segments with ea_merge() and finally sort and prune the result
267 * by calling ea_sort().
270 ea_merge(ea_list
*e
, ea_list
*t
)
279 memcpy(d
, e
->attrs
, sizeof(eattr
)*e
->count
);
280 t
->count
+= e
->count
;
287 * ea_same - compare two &ea_list's
291 * ea_same() compares two normalized attribute lists @x and @y and returns
292 * 1 if they contain the same attributes, 0 otherwise.
295 ea_same(ea_list
*x
, ea_list
*y
)
301 ASSERT(!x
->next
&& !y
->next
);
302 if (x
->count
!= y
->count
)
304 for(c
=0; c
<x
->count
; c
++)
306 eattr
*a
= &x
->attrs
[c
];
307 eattr
*b
= &y
->attrs
[c
];
309 if (a
->id
!= b
->id
||
310 a
->flags
!= b
->flags
||
311 a
->type
!= b
->type
||
312 ((a
->type
& EAF_EMBEDDED
) ? a
->u
.data
!= b
->u
.data
:
313 (a
->u
.ptr
->length
!= b
->u
.ptr
->length
|| memcmp(a
->u
.ptr
->data
, b
->u
.ptr
->data
, a
->u
.ptr
->length
))))
319 static inline ea_list
*
320 ea_list_copy(ea_list
*o
)
328 len
= sizeof(ea_list
) + sizeof(eattr
) * o
->count
;
329 n
= mb_alloc(rta_pool
, len
);
331 n
->flags
|= EALF_CACHED
;
332 for(i
=0; i
<o
->count
; i
++)
334 eattr
*a
= &n
->attrs
[i
];
335 if (!(a
->type
& EAF_EMBEDDED
))
337 unsigned size
= sizeof(struct adata
) + a
->u
.ptr
->length
;
338 struct adata
*d
= mb_alloc(rta_pool
, size
);
339 memcpy(d
, a
->u
.ptr
, size
);
354 for(i
=0; i
<o
->count
; i
++)
356 eattr
*a
= &o
->attrs
[i
];
357 if (!(a
->type
& EAF_EMBEDDED
))
365 * ea_format - format an &eattr for printing
366 * @e: attribute to be formatted
367 * @buf: destination buffer of size %EA_FORMAT_BUF_SIZE
369 * This function takes an extended attribute represented by its
370 * &eattr structure and formats it nicely for printing according
371 * to the type information.
373 * If the protocol defining the attribute provides its own
374 * get_attr() hook, it's consulted first.
377 ea_format(eattr
*e
, byte
*buf
)
380 int status
= GA_UNKNOWN
;
382 struct adata
*ad
= (e
->type
& EAF_EMBEDDED
) ? NULL
: e
->u
.ptr
;
383 byte
*end
= buf
+ EA_FORMAT_BUF_SIZE
- 1;
385 if (p
= attr_class_to_protocol
[EA_PROTO(e
->id
)])
387 buf
+= bsprintf(buf
, "%s.", p
->name
);
389 status
= p
->get_attr(e
, buf
, end
- buf
);
392 else if (EA_PROTO(e
->id
))
393 buf
+= bsprintf(buf
, "%02x.", EA_PROTO(e
->id
));
394 if (status
< GA_NAME
)
395 buf
+= bsprintf(buf
, "%02x", EA_ID(e
->id
));
396 if (status
< GA_FULL
)
400 switch (e
->type
& EAF_TYPE_MASK
)
403 bsprintf(buf
, "%u", e
->u
.data
);
405 case EAF_TYPE_OPAQUE
:
406 for(i
=0; i
<ad
->length
; i
++)
415 buf
+= bsprintf(buf
, "%02x", ad
->data
[i
]);
418 case EAF_TYPE_IP_ADDRESS
:
419 bsprintf(buf
, "%I", *(ip_addr
*) ad
->data
);
421 case EAF_TYPE_ROUTER_ID
:
422 bsprintf(buf
, "%R", e
->u
.data
);
424 case EAF_TYPE_AS_PATH
:
425 as_path_format(ad
, buf
, end
- buf
);
427 case EAF_TYPE_INT_SET
:
428 int_set_format(ad
, 1, buf
, end
- buf
);
432 bsprintf(buf
, "<type %02x>", e
->type
);
438 * ea_dump - dump an extended attribute
439 * @e: attribute to be dumped
441 * ea_dump() dumps contents of the extended attribute given to
457 (e
->flags
& EALF_SORTED
) ? 'S' : 's',
458 (e
->flags
& EALF_BISECT
) ? 'B' : 'b',
459 (e
->flags
& EALF_CACHED
) ? 'C' : 'c');
460 for(i
=0; i
<e
->count
; i
++)
462 eattr
*a
= &e
->attrs
[i
];
463 debug(" %02x:%02x.%02x", EA_PROTO(a
->id
), EA_ID(a
->id
), a
->flags
);
464 if (a
->type
& EAF_TEMP
)
466 debug("=%c", "?iO?I?P???S?????" [a
->type
& EAF_TYPE_MASK
]);
467 if (a
->type
& EAF_ORIGINATED
)
469 if (a
->type
& EAF_EMBEDDED
)
470 debug(":%08x", a
->u
.data
);
473 int j
, len
= a
->u
.ptr
->length
;
476 debug("%02x", a
->u
.ptr
->data
[j
]);
485 * ea_hash - calculate an &ea_list hash key
488 * ea_hash() takes an extended attribute list and calculated a hopefully
489 * uniformly distributed hash value from its contents.
497 if (e
) /* Assuming chain of length 1 */
499 for(i
=0; i
<e
->count
; i
++)
501 struct eattr
*a
= &e
->attrs
[i
];
503 if (a
->type
& EAF_EMBEDDED
)
507 struct adata
*d
= a
->u
.ptr
;
508 int size
= d
->length
;
517 h
= (h
>> 24) ^ (h
<< 8) ^ *z
++;
528 * ea_append - concatenate &ea_list's
529 * @to: destination list (can be %NULL)
530 * @what: list to be appended (can be %NULL)
532 * This function appends the &ea_list @what at the end of
533 * &ea_list @to and returns a pointer to the resulting list.
536 ea_append(ea_list
*to
, ea_list
*what
)
553 static unsigned int rta_cache_count
;
554 static unsigned int rta_cache_size
= 32;
555 static unsigned int rta_cache_limit
;
556 static unsigned int rta_cache_mask
;
557 static rta
**rta_hash_table
;
562 rta_hash_table
= mb_allocz(rta_pool
, sizeof(rta
*) * rta_cache_size
);
563 if (rta_cache_size
< 32768)
564 rta_cache_limit
= rta_cache_size
* 2;
566 rta_cache_limit
= ~0;
567 rta_cache_mask
= rta_cache_size
- 1;
570 static inline unsigned int
573 return (a
->proto
->hash_key
^ ipa_hash(a
->gw
) ^ ea_hash(a
->eattrs
)) & 0xffff;
577 rta_same(rta
*x
, rta
*y
)
579 return (x
->proto
== y
->proto
&&
580 x
->source
== y
->source
&&
581 x
->scope
== y
->scope
&&
582 x
->cast
== y
->cast
&&
583 x
->dest
== y
->dest
&&
584 x
->flags
== y
->flags
&&
585 ipa_equal(x
->gw
, y
->gw
) &&
586 ipa_equal(x
->from
, y
->from
) &&
587 x
->iface
== y
->iface
&&
588 ea_same(x
->eattrs
, y
->eattrs
));
594 rta
*r
= sl_alloc(rta_slab
);
596 memcpy(r
, o
, sizeof(rta
));
598 r
->eattrs
= ea_list_copy(o
->eattrs
);
605 unsigned int h
= r
->hash_key
& rta_cache_mask
;
606 r
->next
= rta_hash_table
[h
];
608 r
->next
->pprev
= &r
->next
;
609 r
->pprev
= &rta_hash_table
[h
];
610 rta_hash_table
[h
] = r
;
616 unsigned int ohs
= rta_cache_size
;
619 rta
**oht
= rta_hash_table
;
621 rta_cache_size
= 2*rta_cache_size
;
622 DBG("Rehashing rta cache from %d to %d entries.\n", ohs
, rta_cache_size
);
625 for(r
=oht
[h
]; r
; r
=n
)
634 * rta_lookup - look up a &rta in attribute cache
635 * @o: a un-cached &rta
637 * rta_lookup() gets an un-cached &rta structure and returns its cached
638 * counterpart. It starts with examining the attribute cache to see whether
639 * there exists a matching entry. If such an entry exists, it's returned and
640 * its use count is incremented, else a new entry is created with use count
643 * The extended attribute lists attached to the &rta are automatically
644 * converted to the normalized form.
652 ASSERT(!(o
->aflags
& RTAF_CACHED
));
655 if (o
->eattrs
->next
) /* Multiple ea_list's, need to merge them */
657 ea_list
*ml
= alloca(ea_scan(o
->eattrs
));
658 ea_merge(o
->eattrs
, ml
);
665 for(r
=rta_hash_table
[h
& rta_cache_mask
]; r
; r
=r
->next
)
666 if (r
->hash_key
== h
&& rta_same(r
, o
))
671 r
->aflags
= RTAF_CACHED
;
674 if (++rta_cache_count
> rta_cache_limit
)
683 ASSERT(rta_cache_count
&& (a
->aflags
& RTAF_CACHED
));
687 a
->next
->pprev
= a
->pprev
;
688 a
->aflags
= 0; /* Poison the entry */
690 sl_free(rta_slab
, a
);
694 * rta_dump - dump route attributes
695 * @a: attribute structure to dump
697 * This function takes a &rta and dumps its contents to the debug output.
702 static char *rts
[] = { "RTS_DUMMY", "RTS_STATIC", "RTS_INHERIT", "RTS_DEVICE",
703 "RTS_STAT_DEV", "RTS_REDIR", "RTS_RIP",
704 "RTS_OSPF", "RTS_OSPF_IA", "RTS_OSPF_EXT1",
705 "RTS_OSPF_EXT2", "RTS_BGP" };
706 static char *rtc
[] = { "", " BC", " MC", " AC" };
707 static char *rtd
[] = { "", " DEV", " HOLE", " UNREACH", " PROHIBIT" };
709 debug("p=%s uc=%d %s %s%s%s h=%04x",
710 a
->proto
->name
, a
->uc
, rts
[a
->source
], ip_scope_text(a
->scope
), rtc
[a
->cast
],
711 rtd
[a
->dest
], a
->hash_key
);
712 if (!(a
->aflags
& RTAF_CACHED
))
714 debug(" <-%I", a
->from
);
715 if (a
->dest
== RTD_ROUTER
)
716 debug(" ->%I", a
->gw
);
717 if (a
->dest
== RTD_DEVICE
|| a
->dest
== RTD_ROUTER
)
718 debug(" [%s]", a
->iface
? a
->iface
->name
: "???" );
727 * rta_dump_all - dump attribute cache
729 * This function dumps the whole contents of route attribute cache
730 * to the debug output.
738 debug("Route attribute cache (%d entries, rehash at %d):\n", rta_cache_count
, rta_cache_limit
);
739 for(h
=0; h
<rta_cache_size
; h
++)
740 for(a
=rta_hash_table
[h
]; a
; a
=a
->next
)
750 rta_show(struct cli
*c
, rta
*a
, ea_list
*eal
)
752 static char *src_names
[] = { "dummy", "static", "inherit", "device", "static-device", "redirect",
753 "RIP", "OSPF", "OSPF-ext", "OSPF-IA", "OSPF-boundary", "BGP" };
754 static char *cast_names
[] = { "unicast", "broadcast", "multicast", "anycast" };
756 byte buf
[EA_FORMAT_BUF_SIZE
];
758 cli_printf(c
, -1008, "\tType: %s %s %s", src_names
[a
->source
], cast_names
[a
->cast
], ip_scope_text(a
->scope
));
761 for(; eal
; eal
=eal
->next
)
762 for(i
=0; i
<eal
->count
; i
++)
764 ea_format(&eal
->attrs
[i
], buf
);
765 cli_printf(c
, -1012, "\t%s", buf
);
770 * rta_init - initialize route attribute cache
772 * This function is called during initialization of the routing
773 * table module to set up the internals of the attribute cache.
778 rta_pool
= rp_new(&root_pool
, "Attributes");
779 rta_slab
= sl_new(rta_pool
, sizeof(rta
));
784 * Documentation for functions declared inline in route.h
789 * rta_clone - clone route attributes
790 * @r: a &rta to be cloned
792 * rta_clone() takes a cached &rta and returns its identical cached
793 * copy. Currently it works by just returning the original &rta with
794 * its use count incremented.
796 static inline rta
*rta_clone(rta
*r
)
800 * rta_free - free route attributes
801 * @r: a &rta to be freed
803 * If you stop using a &rta (for example when deleting a route which uses
804 * it), you need to call rta_free() to notify the attribute cache the
805 * attribute is no longer in use and can be freed if you were the last
806 * user (which rta_free() tests by inspecting the use count).
808 static inline void rta_free(rta
*r
)