#include "nest/cli.h"
#include "nest/attrs.h"
#include "lib/alloca.h"
+#include "lib/hash.h"
+#include "lib/idm.h"
#include "lib/resource.h"
#include "lib/string.h"
-static slab *rta_slab;
-static pool *rta_pool;
+#include <stddef.h>
+
+const char * const rta_src_names[RTS_MAX] = {
+ [RTS_DUMMY] = "",
+ [RTS_STATIC] = "static",
+ [RTS_INHERIT] = "inherit",
+ [RTS_DEVICE] = "device",
+ [RTS_STATIC_DEVICE] = "static-device",
+ [RTS_REDIRECT] = "redirect",
+ [RTS_RIP] = "RIP",
+ [RTS_OSPF] = "OSPF",
+ [RTS_OSPF_IA] = "OSPF-IA",
+ [RTS_OSPF_EXT1] = "OSPF-E1",
+ [RTS_OSPF_EXT2] = "OSPF-E2",
+ [RTS_BGP] = "BGP",
+ [RTS_PIPE] = "pipe",
+ [RTS_BABEL] = "Babel",
+ [RTS_RPKI] = "RPKI",
+};
+
+const char * rta_dest_names[RTD_MAX] = {
+ [RTD_NONE] = "",
+ [RTD_UNICAST] = "unicast",
+ [RTD_BLACKHOLE] = "blackhole",
+ [RTD_UNREACHABLE] = "unreachable",
+ [RTD_PROHIBIT] = "prohibited",
+};
+
+pool *rta_pool;
+
+static slab *rta_slab_[4];
+static slab *nexthop_slab_[4];
+static slab *rte_src_slab;
+
+static struct idm src_ids;
+#define SRC_ID_INIT_SIZE 4
+
+/* rte source hash */
+
+#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;
+
+static void
+rte_src_init(void)
+{
+ rte_src_slab = sl_new(rta_pool, sizeof(struct rte_src));
+
+ idm_init(&src_ids, rta_pool, SRC_ID_INIT_SIZE);
+
+ HASH_INIT(src_hash, rta_pool, RSH_INIT_ORDER);
+}
+
+
+HASH_DEFINE_REHASH_FN(RSH, struct rte_src)
+
+struct rte_src *
+rt_find_source(struct proto *p, u32 id)
+{
+ return HASH_FIND(src_hash, RSH, p, id);
+}
+
+struct rte_src *
+rt_get_source(struct proto *p, u32 id)
+{
+ struct rte_src *src = rt_find_source(p, id);
+
+ if (src)
+ return src;
+
+ src = sl_alloc(rte_src_slab);
+ src->proto = p;
+ src->private_id = id;
+ src->global_id = idm_alloc(&src_ids);
+ src->uc = 0;
+
+ HASH_INSERT2(src_hash, RSH, rta_pool, src);
+
+ return src;
+}
+
+void
+rt_prune_sources(void)
+{
+ HASH_WALK_FILTER(src_hash, next, src, sp)
+ {
+ if (src->uc == 0)
+ {
+ HASH_DO_REMOVE(src_hash, RSH, sp);
+ idm_free(&src_ids, src->global_id);
+ sl_free(rte_src_slab, src);
+ }
+ }
+ HASH_WALK_FILTER_END;
+
+ HASH_MAY_RESIZE_DOWN(src_hash, RSH, rta_pool);
+}
+
+
+/*
+ * Multipath Next Hop
+ */
+
+static inline u32
+nexthop_hash(struct nexthop *x)
+{
+ u32 h = 0;
+ for (; x; x = x->next)
+ {
+ h ^= ipa_hash(x->gw) ^ (h << 5) ^ (h >> 9);
+
+ for (int i = 0; i < x->labels; i++)
+ h ^= x->label[i] ^ (h << 6) ^ (h >> 7);
+ }
+
+ return h;
+}
+
+int
+nexthop__same(struct nexthop *x, struct nexthop *y)
+{
+ for (; x && y; x = x->next, y = y->next)
+ {
+ if (!ipa_equal(x->gw, y->gw) || (x->iface != y->iface) ||
+ (x->flags != y->flags) || (x->weight != y->weight) ||
+ (x->labels != y->labels))
+ return 0;
+
+ for (int i = 0; i < x->labels; i++)
+ if (x->label[i] != y->label[i])
+ return 0;
+ }
+
+ return x == y;
+}
+
+static int
+nexthop_compare_node(struct nexthop *x, struct nexthop *y)
+{
+ int r;
+
+ if (!x)
+ return 1;
+
+ if (!y)
+ return -1;
+
+ /* Should we also compare flags ? */
+
+ r = ((int) y->weight) - ((int) x->weight);
+ if (r)
+ return r;
+
+ r = ipa_compare(x->gw, y->gw);
+ if (r)
+ return r;
+
+ r = ((int) y->labels) - ((int) x->labels);
+ if (r)
+ return r;
+
+ for (int i = 0; i < y->labels; i++)
+ {
+ r = ((int) y->label[i]) - ((int) x->label[i]);
+ if (r)
+ return r;
+ }
+
+ return ((int) x->iface->index) - ((int) y->iface->index);
+}
+
+static inline struct nexthop *
+nexthop_copy_node(const struct nexthop *src, linpool *lp)
+{
+ struct nexthop *n = lp_alloc(lp, nexthop_size(src));
+
+ memcpy(n, src, nexthop_size(src));
+ n->next = NULL;
+
+ return n;
+}
+
+/**
+ * nexthop_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 nexthop_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 nexthop *
+nexthop_merge(struct nexthop *x, struct nexthop *y, int rx, int ry, int max, linpool *lp)
+{
+ struct nexthop *root = NULL;
+ struct nexthop **n = &root;
+
+ while ((x || y) && max--)
+ {
+ int cmp = nexthop_compare_node(x, y);
+ if (cmp < 0)
+ {
+ *n = rx ? x : nexthop_copy_node(x, lp);
+ x = x->next;
+ }
+ else if (cmp > 0)
+ {
+ *n = ry ? y : nexthop_copy_node(y, lp);
+ y = y->next;
+ }
+ else
+ {
+ *n = rx ? x : (ry ? y : nexthop_copy_node(x, lp));
+ x = x->next;
+ y = y->next;
+ }
+ n = &((*n)->next);
+ }
+ *n = NULL;
+
+ return root;
+}
+
+void
+nexthop_insert(struct nexthop **n, struct nexthop *x)
+{
+ for (; *n; n = &((*n)->next))
+ {
+ int cmp = nexthop_compare_node(*n, x);
+
+ if (cmp < 0)
+ continue;
+ else if (cmp > 0)
+ break;
+ else
+ return;
+ }
+
+ x->next = *n;
+ *n = x;
+}
+
+int
+nexthop_is_sorted(struct nexthop *x)
+{
+ for (; x && x->next; x = x->next)
+ if (nexthop_compare_node(x, x->next) >= 0)
+ return 0;
+
+ return 1;
+}
+
+static inline slab *
+nexthop_slab(struct nexthop *nh)
+{
+ return nexthop_slab_[MIN(nh->labels, 3)];
+}
+
+static struct nexthop *
+nexthop_copy(struct nexthop *o)
+{
+ struct nexthop *first = NULL;
+ struct nexthop **last = &first;
+
+ for (; o; o = o->next)
+ {
+ struct nexthop *n = sl_alloc(nexthop_slab(o));
+ n->gw = o->gw;
+ n->iface = o->iface;
+ n->next = NULL;
+ n->flags = o->flags;
+ n->weight = o->weight;
+ n->labels = o->labels;
+ for (int i=0; i<o->labels; i++)
+ n->label[i] = o->label[i];
+
+ *last = n;
+ last = &(n->next);
+ }
+
+ return first;
+}
+
+static void
+nexthop_free(struct nexthop *o)
+{
+ struct nexthop *n;
+
+ while (o)
+ {
+ n = o->next;
+ sl_free(nexthop_slab(o), o);
+ o = n;
+ }
+}
-struct protocol *attr_class_to_protocol[EAP_MAX];
/*
* Extended Attributes
while (e)
{
- /*
if (e->flags & EALF_BISECT)
{
l = 0;
- r = e->count + 1;
+ r = e->count - 1;
while (l <= r)
{
m = (l+r) / 2;
}
}
else
- */
for(m=0; m<e->count; m++)
if (e->attrs[m].id == id)
return &e->attrs[m];
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
while (ss);
}
+/**
+ * In place discard duplicates, undefs and temporary attributes in sorted
+ * ea_list. We use stable sort for this reason.
+ **/
static inline void
ea_do_prune(ea_list *e)
{
eattr *s, *d, *l, *s0;
int i = 0;
- /* Discard duplicates and undefs. Do you remember sorting was stable? */
- s = d = e->attrs;
- l = e->attrs + e->count;
+ s = d = e->attrs; /* Beginning of the list. @s is source, @d is destination. */
+ l = e->attrs + e->count; /* End of the list */
+
+ /* Walk from begin to end. */
while (s < l)
{
s0 = s++;
+ /* Find a consecutive block of the same attribute */
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)
- {
- *d = *s0;
- d->type = (d->type & ~EAF_ORIGINATED) | (s[-1].type & EAF_ORIGINATED);
- d++;
- i++;
- }
+
+ /* Now s0 is the most recent version, s[-1] the oldest one */
+ /* Drop undefs */
+ if ((s0->type & EAF_TYPE_MASK) == EAF_TYPE_UNDEF)
+ continue;
+
+ /* Drop temporary attributes */
+ if (s0->type & EAF_TEMP)
+ continue;
+
+ /* Copy the newest version to destination */
+ *d = *s0;
+
+ /* Preserve info whether it originated locally */
+ d->type = (d->type & ~(EAF_ORIGINATED|EAF_FRESH)) | (s[-1].type & EAF_ORIGINATED);
+
+ /* Next destination */
+ d++;
+ i++;
}
+
e->count = i;
}
if (a->id != b->id ||
a->flags != b->flags ||
a->type != b->type ||
- ((a->type & EAF_EMBEDDED) ? a->u.data != b->u.data :
- (a->u.ptr->length != b->u.ptr->length || memcmp(a->u.ptr->data, b->u.ptr->data, a->u.ptr->length))))
+ ((a->type & EAF_EMBEDDED) ? a->u.data != b->u.data : !adata_same(a->u.ptr, b->u.ptr)))
return 0;
}
return 1;
}
}
+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;
+}
+
+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, uint size)
+{
+ byte *bound = buf + size - 10;
+ uint 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, "\t%s", buf);
+ while (i)
+ {
+ i = int_set_format(ad, way, i, buf, end - buf - 1);
+ cli_printf(c, -1012, "\t\t%s", buf);
+ }
+}
+
+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, "\t%s", buf);
+ while (i)
+ {
+ i = ec_set_format(ad, i, buf, end - buf - 1);
+ cli_printf(c, -1012, "\t\t%s", buf);
+ }
+}
+
+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_format - format an &eattr for printing
- * @e: attribute to be formatted
- * @buf: destination buffer of size %EA_FORMAT_BUF_SIZE
+ * ea_show - print an &eattr to CLI
+ * @c: destination CLI
+ * @e: attribute to be printed
*
- * This function takes an extended attribute represented by its
- * &eattr structure and formats it nicely for printing according
- * to the type information.
+ * This function takes an extended attribute represented by its &eattr
+ * structure and prints it to the CLI according to the type information.
*
* If the protocol defining the attribute provides its own
* get_attr() hook, it's consulted first.
*/
void
-ea_format(eattr *e, byte *buf)
+ea_show(struct cli *c, eattr *e)
{
struct protocol *p;
int status = GA_UNKNOWN;
- unsigned int i;
struct adata *ad = (e->type & EAF_EMBEDDED) ? NULL : e->u.ptr;
- byte *end = buf + EA_FORMAT_BUF_SIZE - 1;
+ byte buf[CLI_MSG_SIZE];
+ byte *pos = buf, *end = buf + sizeof(buf);
- if (p = attr_class_to_protocol[EA_PROTO(e->id)])
+ if (EA_IS_CUSTOM(e->id))
+ {
+ const char *name = ea_custom_name(e->id);
+ if (name)
+ {
+ pos += bsprintf(pos, "%s", name);
+ status = GA_NAME;
+ }
+ else
+ pos += bsprintf(pos, "%02x.", EA_PROTO(e->id));
+ }
+ else if (p = class_to_protocol[EA_PROTO(e->id)])
{
- buf += bsprintf(buf, "%s.", p->name);
+ pos += bsprintf(pos, "%s.", p->name);
if (p->get_attr)
- status = p->get_attr(e, buf, end - buf);
- buf += strlen(buf);
+ status = p->get_attr(e, pos, end - pos);
+ pos += strlen(pos);
}
else if (EA_PROTO(e->id))
- buf += bsprintf(buf, "%02x.", EA_PROTO(e->id));
+ pos += bsprintf(pos, "%02x.", EA_PROTO(e->id));
+ else
+ status = get_generic_attr(e, &pos, end - pos);
+
if (status < GA_NAME)
- buf += bsprintf(buf, "%02x", EA_ID(e->id));
+ pos += bsprintf(pos, "%02x", EA_ID(e->id));
if (status < GA_FULL)
{
- *buf++ = ':';
- *buf++ = ' ';
+ *pos++ = ':';
+ *pos++ = ' ';
switch (e->type & EAF_TYPE_MASK)
{
case EAF_TYPE_INT:
- bsprintf(buf, "%d", e->u.data);
+ bsprintf(pos, "%u", e->u.data);
break;
case EAF_TYPE_OPAQUE:
- for(i=0; i<ad->length; i++)
- {
- if (buf > end - 8)
- {
- strcpy(buf, " ...");
- break;
- }
- if (i)
- *buf++ = ' ';
- buf += bsprintf(buf, "%02x", ad->data[i]);
- }
+ opaque_format(ad, pos, end - pos);
break;
case EAF_TYPE_IP_ADDRESS:
- bsprintf(buf, "%I", *(ip_addr *) ad->data);
+ bsprintf(pos, "%I", *(ip_addr *) ad->data);
break;
case EAF_TYPE_ROUTER_ID:
- bsprintf(buf, "%R", e->u.data);
+ bsprintf(pos, "%R", e->u.data);
break;
case EAF_TYPE_AS_PATH:
- as_path_format(ad, buf, end - buf);
+ as_path_format(ad, pos, end - pos);
break;
- case EAF_TYPE_INT_SET:
- int_set_format(ad, 1, buf, end - buf);
+ 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(buf, "<type %02x>", e->type);
+ bsprintf(pos, "<type %02x>", e->type);
}
}
+ cli_printf(c, -1012, "\t%s", buf);
}
/**
* 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;
+ const u64 mul = 0x68576150f3d6847;
+ u64 h = 0xafcef24eda8b29;
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;
+ h ^= a->id; h *= mul;
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 ^= mem_hash(d->data, d->length);
}
+ h *= mul;
}
- h ^= h >> 16;
- h ^= h >> 6;
- h &= 0xffff;
}
- return h;
+ return (h >> 32) ^ (h & 0xffffffff);
}
/**
* 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 (a->proto->hash_key ^ ipa_hash(a->gw) ^ ea_hash(a->eattrs)) & 0xffff;
+ u64 h;
+ mem_hash_init(&h);
+#define MIX(f) mem_hash_mix(&h, &(a->f), sizeof(a->f));
+ MIX(src);
+ MIX(hostentry);
+ MIX(from);
+ MIX(igp_metric);
+ MIX(source);
+ MIX(scope);
+ MIX(dest);
+#undef MIX
+
+ return mem_hash_value(&h) ^ nexthop_hash(&(a->nh)) ^ ea_hash(a->eattrs);
}
static inline int
rta_same(rta *x, rta *y)
{
- return (x->proto == y->proto &&
+ return (x->src == y->src &&
x->source == y->source &&
x->scope == y->scope &&
- x->cast == y->cast &&
x->dest == y->dest &&
- x->flags == y->flags &&
- ipa_equal(x->gw, y->gw) &&
+ x->igp_metric == y->igp_metric &&
ipa_equal(x->from, y->from) &&
- x->iface == y->iface &&
+ x->hostentry == y->hostentry &&
+ nexthop_same(&(x->nh), &(y->nh)) &&
ea_same(x->eattrs, y->eattrs));
}
+static inline slab *
+rta_slab(rta *a)
+{
+ return rta_slab_[a->nh.labels > 2 ? 3 : a->nh.labels];
+}
+
static rta *
rta_copy(rta *o)
{
- rta *r = sl_alloc(rta_slab);
+ rta *r = sl_alloc(rta_slab(o));
- memcpy(r, o, sizeof(rta));
+ memcpy(r, o, rta_size(o));
r->uc = 1;
+ r->nh.next = nexthop_copy(o->nh.next);
r->eattrs = ea_list_copy(o->eattrs);
return r;
}
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)
- {
- if (o->eattrs->next) /* Multiple ea_list's, need to merge them */
- {
- ea_list *ml = alloca(ea_scan(o->eattrs));
- ea_merge(o->eattrs, ml);
- o->eattrs = ml;
- }
- ea_sort(o->eattrs);
- }
+ ea_normalize(o->eattrs);
h = rta_hash(o);
for(r=rta_hash_table[h & rta_cache_mask]; r; r=r->next)
r = rta_copy(o);
r->hash_key = h;
r->aflags = RTAF_CACHED;
+ rt_lock_source(r->src);
+ rt_lock_hostentry(r->hostentry);
rta_insert(r);
if (++rta_cache_count > rta_cache_limit)
*a->pprev = a->next;
if (a->next)
a->next->pprev = a->pprev;
- a->aflags = 0; /* Poison the entry */
+ rt_unlock_hostentry(a->hostentry);
+ rt_unlock_source(a->src);
+ if (a->nh.next)
+ nexthop_free(a->nh.next);
ea_free(a->eattrs);
- sl_free(rta_slab, a);
+ a->aflags = 0; /* Poison the entry */
+ sl_free(rta_slab(a), a);
+}
+
+rta *
+rta_do_cow(rta *o, linpool *lp)
+{
+ rta *r = lp_alloc(lp, rta_size(o));
+ memcpy(r, o, rta_size(o));
+ for (struct nexthop **nhn = &(r->nh.next), *nho = o->nh.next; nho; nho = nho->next)
+ {
+ *nhn = lp_alloc(lp, nexthop_size(nho));
+ memcpy(*nhn, nho, nexthop_size(nho));
+ nhn = &((*nhn)->next);
+ }
+ r->aflags = 0;
+ r->uc = 0;
+ return r;
}
/**
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" };
- static char *rtc[] = { "", " BC", " MC", " AC" };
+ "RTS_OSPF_EXT2", "RTS_BGP", "RTS_PIPE", "RTS_BABEL" };
static char *rtd[] = { "", " DEV", " HOLE", " UNREACH", " PROHIBIT" };
- debug("p=%s uc=%d %s %s%s%s h=%04x",
- a->proto->name, a->uc, rts[a->source], ip_scope_text(a->scope), rtc[a->cast],
+ debug("p=%s uc=%d %s %s%s h=%04x",
+ a->src->proto->name, a->uc, rts[a->source], ip_scope_text(a->scope),
rtd[a->dest], a->hash_key);
if (!(a->aflags & RTAF_CACHED))
debug(" !CACHED");
debug(" <-%I", a->from);
- if (a->dest == RTD_ROUTER)
- debug(" ->%I", a->gw);
- if (a->dest == RTD_DEVICE || a->dest == RTD_ROUTER)
- debug(" [%s]", a->iface ? a->iface->name : "???" );
+ if (a->dest == RTD_UNICAST)
+ for (struct nexthop *nh = &(a->nh); nh; nh = nh->next)
+ {
+ if (ipa_nonzero(nh->gw)) debug(" ->%I", nh->gw);
+ if (nh->labels) debug(" L %d", nh->label[0]);
+ for (int i=1; i<nh->labels; i++)
+ debug("/%d", nh->label[i]);
+ debug(" [%s]", nh->iface ? nh->iface->name : "???");
+ }
if (a->eattrs)
{
debug(" EA: ");
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++)
}
void
-rta_show(struct cli *c, rta *a, ea_list *eal)
+rta_show(struct cli *c, rta *a)
{
- static char *src_names[] = { "dummy", "static", "inherit", "device", "static-device", "redirect",
- "RIP", "OSPF", "OSPF-ext", "OSPF-IA", "OSPF-boundary", "BGP" };
- static char *cast_names[] = { "unicast", "broadcast", "multicast", "anycast" };
- int i;
- byte buf[EA_FORMAT_BUF_SIZE];
+ cli_printf(c, -1008, "\tType: %s %s", rta_src_names[a->source], ip_scope_text(a->scope));
- cli_printf(c, -1008, "\tType: %s %s %s", src_names[a->source], cast_names[a->cast], ip_scope_text(a->scope));
- if (!eal)
- eal = a->eattrs;
- for(; eal; eal=eal->next)
- for(i=0; i<eal->count; i++)
- {
- ea_format(&eal->attrs[i], buf);
- cli_printf(c, -1012, "\t%s", buf);
- }
+ for(ea_list *eal = a->eattrs; eal; eal=eal->next)
+ for(int i=0; i<eal->count; i++)
+ ea_show(c, &eal->attrs[i]);
}
/**
rta_init(void)
{
rta_pool = rp_new(&root_pool, "Attributes");
- rta_slab = sl_new(rta_pool, sizeof(rta));
+
+ rta_slab_[0] = sl_new(rta_pool, sizeof(rta));
+ rta_slab_[1] = sl_new(rta_pool, sizeof(rta) + sizeof(u32));
+ rta_slab_[2] = sl_new(rta_pool, sizeof(rta) + sizeof(u32)*2);
+ rta_slab_[3] = sl_new(rta_pool, sizeof(rta) + sizeof(u32)*MPLS_MAX_LABEL_STACK);
+
+ nexthop_slab_[0] = sl_new(rta_pool, sizeof(struct nexthop));
+ nexthop_slab_[1] = sl_new(rta_pool, sizeof(struct nexthop) + sizeof(u32));
+ nexthop_slab_[2] = sl_new(rta_pool, sizeof(struct nexthop) + sizeof(u32)*2);
+ nexthop_slab_[3] = sl_new(rta_pool, sizeof(struct nexthop) + sizeof(u32)*MPLS_MAX_LABEL_STACK);
+
rta_alloc_hash();
+ rte_src_init();
}
/*
projects / thirdparty / bird.git / blobdiff