#include "nest/cli.h"
#include "nest/attrs.h"
#include "lib/alloca.h"
+#include "lib/hash.h"
#include "lib/resource.h"
#include "lib/string.h"
/* rte source ID bitmap */
static u32 *src_ids;
static u32 src_id_size, src_id_used, src_id_pos;
-#define SRC_ID_SIZE_DEF 4
+#define SRC_ID_INIT_SIZE 4
/* rte source hash */
-static struct rte_src **src_table;
-static u32 src_hash_order, src_hash_size, src_hash_count;
-#define SRC_HASH_ORDER_DEF 6
-#define SRC_HASH_ORDER_MAX 18
-#define SRC_HASH_ORDER_MIN 10
+
+#define RSH_KEY(n) n->proto, n->private_id
+#define RSH_NEXT(n) n->next
+#define RSH_EQ(p1,n1,p2,n2) p1 == p2 && n1 == n2
+#define RSH_FN(p,n) p->hash_key ^ u32_hash(n)
+
+#define RSH_REHASH rte_src_rehash
+#define RSH_PARAMS /2, *2, 1, 1, 8, 20
+#define RSH_INIT_ORDER 6
+
+static HASH(struct rte_src) src_hash;
struct protocol *attr_class_to_protocol[EAP_MAX];
rte_src_slab = sl_new(rta_pool, sizeof(struct rte_src));
src_id_pos = 0;
- src_id_size = SRC_ID_SIZE_DEF;
+ src_id_size = SRC_ID_INIT_SIZE;
src_ids = mb_allocz(rta_pool, src_id_size * sizeof(u32));
/* ID 0 is reserved */
src_ids[0] = 1;
src_id_used = 1;
- src_hash_count = 0;
- src_hash_order = SRC_HASH_ORDER_DEF;
- src_hash_size = 1 << src_hash_order;
- src_table = mb_allocz(rta_pool, src_hash_size * sizeof(struct rte_src *));
+ HASH_INIT(src_hash, rta_pool, RSH_INIT_ORDER);
}
-static inline int u32_cto(unsigned int x) { return ffs(~x) - 1; }
+static inline int u32_cto(uint x) { return ffs(~x) - 1; }
static inline u32
rte_src_alloc_id(void)
{
- int i, j;
+ uint i, j;
for (i = src_id_pos; i < src_id_size; i++)
if (src_ids[i] != 0xffffffff)
goto found;
src_id_used--;
}
-static inline u32 rte_src_hash(struct proto *p, u32 x, u32 order)
-{ return (x * 2902958171u) >> (32 - order); }
-
-static void
-rte_src_rehash(int step)
-{
- struct rte_src **old_tab, *src, *src_next;
- u32 old_size, hash, i;
-
- old_tab = src_table;
- old_size = src_hash_size;
-
- src_hash_order += step;
- src_hash_size = 1 << src_hash_order;
- src_table = mb_allocz(rta_pool, src_hash_size * sizeof(struct rte_src *));
-
- for (i = 0; i < old_size; i++)
- for (src = old_tab[i]; src; src = src_next)
- {
- src_next = src->next;
- hash = rte_src_hash(src->proto, src->private_id, src_hash_order);
- src->next = src_table[hash];
- src_table[hash] = src;
- }
- mb_free(old_tab);
-}
+HASH_DEFINE_REHASH_FN(RSH, struct rte_src)
struct rte_src *
rt_find_source(struct proto *p, u32 id)
{
- struct rte_src *src;
- u32 hash = rte_src_hash(p, id, src_hash_order);
-
- for (src = src_table[hash]; src; src = src->next)
- if ((src->proto == p) && (src->private_id == id))
- return src;
-
- return NULL;
+ return HASH_FIND(src_hash, RSH, p, id);
}
struct rte_src *
rt_get_source(struct proto *p, u32 id)
{
- struct rte_src *src;
- u32 hash = rte_src_hash(p, id, src_hash_order);
+ struct rte_src *src = rt_find_source(p, id);
- for (src = src_table[hash]; src; src = src->next)
- if ((src->proto == p) && (src->private_id == id))
- return src;
+ if (src)
+ return src;
src = sl_alloc(rte_src_slab);
src->proto = p;
src->global_id = rte_src_alloc_id();
src->uc = 0;
- src->next = src_table[hash];
- src_table[hash] = src;
-
- src_hash_count++;
- if ((src_hash_count > src_hash_size) && (src_hash_order < SRC_HASH_ORDER_MAX))
- rte_src_rehash(1);
+ HASH_INSERT2(src_hash, RSH, rta_pool, src);
return src;
}
-static inline void
-rt_remove_source(struct rte_src **sp)
-{
- struct rte_src *src = *sp;
-
- *sp = src->next;
- rte_src_free_id(src->global_id);
- sl_free(rte_src_slab, src);
- src_hash_count--;
-}
-
void
rt_prune_sources(void)
{
- struct rte_src **sp;
- int i;
-
- for (i = 0; i < src_hash_size; i++)
+ HASH_WALK_FILTER(src_hash, next, src, sp)
+ {
+ if (src->uc == 0)
{
- sp = &src_table[i];
- while (*sp)
- {
- if ((*sp)->uc == 0)
- rt_remove_source(sp);
- else
- sp = &(*sp)->next;
- }
+ HASH_DO_REMOVE(src_hash, RSH, sp);
+ rte_src_free_id(src->global_id);
+ sl_free(rte_src_slab, src);
}
+ }
+ HASH_WALK_FILTER_END;
- while ((src_hash_count < (src_hash_size / 4)) && (src_hash_order > SRC_HASH_ORDER_MIN))
- rte_src_rehash(-1);
+ HASH_MAY_RESIZE_DOWN(src_hash, RSH, rta_pool);
}
* Multipath Next Hop
*/
-static inline unsigned int
+static inline uint
mpnh_hash(struct mpnh *x)
{
- unsigned int h = 0;
+ uint h = 0;
for (; x; x = x->next)
h ^= ipa_hash(x->gw);
return x == y;
}
+static int
+mpnh_compare_node(struct mpnh *x, struct mpnh *y)
+{
+ int r;
+
+ if (!x)
+ return 1;
+
+ if (!y)
+ return -1;
+
+ r = ((int) y->weight) - ((int) x->weight);
+ if (r)
+ return r;
+
+ r = ipa_compare(x->gw, y->gw);
+ if (r)
+ return r;
+
+ return ((int) x->iface->index) - ((int) y->iface->index);
+}
+
+static inline struct mpnh *
+mpnh_copy_node(const struct mpnh *src, linpool *lp)
+{
+ struct mpnh *n = lp_alloc(lp, sizeof(struct mpnh));
+ n->gw = src->gw;
+ n->iface = src->iface;
+ n->next = NULL;
+ n->weight = src->weight;
+ return n;
+}
+
+/**
+ * mpnh_merge - merge nexthop lists
+ * @x: list 1
+ * @y: list 2
+ * @rx: reusability of list @x
+ * @ry: reusability of list @y
+ * @max: max number of nexthops
+ * @lp: linpool for allocating nexthops
+ *
+ * The mpnh_merge() function takes two nexthop lists @x and @y and merges them,
+ * eliminating possible duplicates. The input lists must be sorted and the
+ * result is sorted too. The number of nexthops in result is limited by @max.
+ * New nodes are allocated from linpool @lp.
+ *
+ * The arguments @rx and @ry specify whether corresponding input lists may be
+ * consumed by the function (i.e. their nodes reused in the resulting list), in
+ * that case the caller should not access these lists after that. To eliminate
+ * issues with deallocation of these lists, the caller should use some form of
+ * bulk deallocation (e.g. stack or linpool) to free these nodes when the
+ * resulting list is no longer needed. When reusability is not set, the
+ * corresponding lists are not modified nor linked from the resulting list.
+ */
+struct mpnh *
+mpnh_merge(struct mpnh *x, struct mpnh *y, int rx, int ry, int max, linpool *lp)
+{
+ struct mpnh *root = NULL;
+ struct mpnh **n = &root;
+
+ while ((x || y) && max--)
+ {
+ int cmp = mpnh_compare_node(x, y);
+ if (cmp < 0)
+ {
+ *n = rx ? x : mpnh_copy_node(x, lp);
+ x = x->next;
+ }
+ else if (cmp > 0)
+ {
+ *n = ry ? y : mpnh_copy_node(y, lp);
+ y = y->next;
+ }
+ else
+ {
+ *n = rx ? x : (ry ? y : mpnh_copy_node(x, lp));
+ x = x->next;
+ y = y->next;
+ }
+ n = &((*n)->next);
+ }
+ *n = NULL;
+
+ return root;
+}
+
+void
+mpnh_insert(struct mpnh **n, struct mpnh *x)
+{
+ for (; *n; n = &((*n)->next))
+ {
+ int cmp = mpnh_compare_node(*n, x);
+
+ if (cmp < 0)
+ continue;
+ else if (cmp > 0)
+ break;
+ else
+ return;
+ }
+
+ x->next = *n;
+ *n = x;
+}
+
+int
+mpnh_is_sorted(struct mpnh *x)
+{
+ for (; x && x->next; x = x->next)
+ if (mpnh_compare_node(x, x->next) >= 0)
+ return 0;
+
+ return 1;
+}
+
static struct mpnh *
mpnh_copy(struct mpnh *o)
{
return a;
}
+/**
+ * ea_walk - walk through extended attributes
+ * @s: walk state structure
+ * @id: start of attribute ID interval
+ * @max: length of attribute ID interval
+ *
+ * Given an extended attribute list, ea_walk() walks through the list looking
+ * for first occurrences of attributes with ID in specified interval from @id to
+ * (@id + @max - 1), returning pointers to found &eattr structures, storing its
+ * walk state in @s for subsequent calls.
+ *
+ * The function ea_walk() is supposed to be called in a loop, with initially
+ * zeroed walk state structure @s with filled the initial extended attribute
+ * list, returning one found attribute in each call or %NULL when no other
+ * attribute exists. The extended attribute list or the arguments should not be
+ * modified between calls. The maximum value of @max is 128.
+ */
+eattr *
+ea_walk(struct ea_walk_state *s, uint id, uint max)
+{
+ ea_list *e = s->eattrs;
+ eattr *a = s->ea;
+ eattr *a_max;
+
+ max = id + max;
+
+ if (a)
+ goto step;
+
+ for (; e; e = e->next)
+ {
+ if (e->flags & EALF_BISECT)
+ {
+ int l, r, m;
+
+ l = 0;
+ r = e->count - 1;
+ while (l < r)
+ {
+ m = (l+r) / 2;
+ if (e->attrs[m].id < id)
+ l = m + 1;
+ else
+ r = m;
+ }
+ a = e->attrs + l;
+ }
+ else
+ a = e->attrs;
+
+ step:
+ a_max = e->attrs + e->count;
+ for (; a < a_max; a++)
+ if ((a->id >= id) && (a->id < max))
+ {
+ int n = a->id - id;
+
+ if (BIT32_TEST(s->visited, n))
+ continue;
+
+ BIT32_SET(s->visited, n);
+
+ if ((a->type & EAF_TYPE_MASK) == EAF_TYPE_UNDEF)
+ continue;
+
+ s->eattrs = e;
+ s->ea = a;
+ return a;
+ }
+ else if (e->flags & EALF_BISECT)
+ break;
+ }
+
+ return NULL;
+}
+
/**
* ea_get_int - fetch an integer attribute
* @e: attribute list
*buf += bsprintf(*buf, "igp_metric");
return GA_NAME;
}
-
+
return GA_UNKNOWN;
}
+void
+ea_format_bitfield(struct eattr *a, byte *buf, int bufsize, const char **names, int min, int max)
+{
+ byte *bound = buf + bufsize - 32;
+ u32 data = a->u.data;
+ int i;
+
+ for (i = min; i < max; i++)
+ if ((data & (1u << i)) && names[i])
+ {
+ if (buf > bound)
+ {
+ strcpy(buf, " ...");
+ return;
+ }
+
+ buf += bsprintf(buf, " %s", names[i]);
+ data &= ~(1u << i);
+ }
+
+ if (data)
+ bsprintf(buf, " %08x", data);
+
+ return;
+}
+
static inline void
-opaque_format(struct adata *ad, byte *buf, unsigned int size)
+opaque_format(struct adata *ad, byte *buf, uint size)
{
byte *bound = buf + size - 10;
- int i;
+ uint i;
for(i = 0; i < ad->length; i++)
{
}
}
+static inline void
+ea_show_lc_set(struct cli *c, struct adata *ad, byte *pos, byte *buf, byte *end)
+{
+ int i = lc_set_format(ad, 0, pos, end - pos);
+ cli_printf(c, -1012, "\t%s", buf);
+ while (i)
+ {
+ i = lc_set_format(ad, i, buf, end - buf - 1);
+ cli_printf(c, -1012, "\t\t%s", buf);
+ }
+}
+
/**
* ea_show - print an &eattr to CLI
* @c: destination CLI
}
else if (EA_PROTO(e->id))
pos += bsprintf(pos, "%02x.", EA_PROTO(e->id));
- else
+ else
status = get_generic_attr(e, &pos, end - pos);
if (status < GA_NAME)
case EAF_TYPE_AS_PATH:
as_path_format(ad, pos, end - pos);
break;
+ case EAF_TYPE_BITFIELD:
+ bsprintf(pos, "%08x", e->u.data);
+ break;
case EAF_TYPE_INT_SET:
ea_show_int_set(c, ad, 1, pos, buf, end);
return;
case EAF_TYPE_EC_SET:
ea_show_ec_set(c, ad, pos, buf, end);
return;
+ case EAF_TYPE_LC_SET:
+ ea_show_lc_set(c, ad, pos, buf, end);
+ return;
case EAF_TYPE_UNDEF:
default:
bsprintf(pos, "<type %02x>", e->type);
* ea_hash() takes an extended attribute list and calculated a hopefully
* uniformly distributed hash value from its contents.
*/
-inline unsigned int
+inline uint
ea_hash(ea_list *e)
{
u32 h = 0;
* rta's
*/
-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 uint rta_cache_count;
+static uint rta_cache_size = 32;
+static uint rta_cache_limit;
+static uint rta_cache_mask;
static rta **rta_hash_table;
static void
rta_cache_mask = rta_cache_size - 1;
}
-static inline unsigned int
+static inline uint
rta_hash(rta *a)
{
- return (((unsigned) a->src) ^ ipa_hash(a->gw) ^
+ return (((uint) (uintptr_t) a->src) ^ ipa_hash(a->gw) ^
mpnh_hash(a->nexthops) ^ ea_hash(a->eattrs)) & 0xffff;
}
static inline void
rta_insert(rta *r)
{
- unsigned int h = r->hash_key & rta_cache_mask;
+ uint h = r->hash_key & rta_cache_mask;
r->next = rta_hash_table[h];
if (r->next)
r->next->pprev = &r->next;
static void
rta_rehash(void)
{
- unsigned int ohs = rta_cache_size;
- unsigned int h;
+ uint ohs = rta_cache_size;
+ uint h;
rta *r, *n;
rta **oht = rta_hash_table;
rta_lookup(rta *o)
{
rta *r;
- unsigned int h;
+ uint h;
ASSERT(!(o->aflags & RTAF_CACHED));
if (o->eattrs)
sl_free(rta_slab, a);
}
+rta *
+rta_do_cow(rta *o, linpool *lp)
+{
+ rta *r = lp_alloc(lp, sizeof(rta));
+ memcpy(r, o, sizeof(rta));
+ r->aflags = 0;
+ r->uc = 0;
+ return r;
+}
+
/**
* rta_dump - dump route attributes
* @a: attribute structure to dump
static char *rts[] = { "RTS_DUMMY", "RTS_STATIC", "RTS_INHERIT", "RTS_DEVICE",
"RTS_STAT_DEV", "RTS_REDIR", "RTS_RIP",
"RTS_OSPF", "RTS_OSPF_IA", "RTS_OSPF_EXT1",
- "RTS_OSPF_EXT2", "RTS_BGP" };
+ "RTS_OSPF_EXT2", "RTS_BGP", "RTS_PIPE", "RTS_BABEL" };
static char *rtc[] = { "", " BC", " MC", " AC" };
static char *rtd[] = { "", " DEV", " HOLE", " UNREACH", " PROHIBIT" };
rta_dump_all(void)
{
rta *a;
- unsigned int h;
+ uint 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++)
projects / thirdparty / bird.git / blobdiff