diff options
Diffstat (limited to 'nest')
| -rw-r--r-- | nest/config.Y | 2 | ||||
| -rw-r--r-- | nest/route.h | 45 | ||||
| -rw-r--r-- | nest/rt-attr.c | 119 | ||||
| -rw-r--r-- | nest/rt-dev.c | 6 | ||||
| -rw-r--r-- | nest/rt-table.c | 73 |
5 files changed, 128 insertions, 117 deletions
diff --git a/nest/config.Y b/nest/config.Y index 23d6a452..95ce59cd 100644 --- a/nest/config.Y +++ b/nest/config.Y @@ -79,7 +79,7 @@ CF_ENUM(T_ENUM_RTS, RTS_, DUMMY, STATIC, INHERIT, DEVICE, STATIC_DEVICE, REDIREC RIP, OSPF, OSPF_IA, OSPF_EXT1, OSPF_EXT2, BGP, PIPE, BABEL) CF_ENUM(T_ENUM_SCOPE, SCOPE_, HOST, LINK, SITE, ORGANIZATION, UNIVERSE, UNDEFINED) CF_ENUM(T_ENUM_RTC, RTC_, UNICAST, BROADCAST, MULTICAST, ANYCAST) -CF_ENUM(T_ENUM_RTD, RTD_, ROUTER, DEVICE, BLACKHOLE, UNREACHABLE, PROHIBIT, MULTIPATH) +CF_ENUM(T_ENUM_RTD, RTD_, UNICAST, BLACKHOLE, UNREACHABLE, PROHIBIT) CF_ENUM(T_ENUM_ROA, ROA_, UNKNOWN, VALID, INVALID) %type <i32> idval diff --git a/nest/route.h b/nest/route.h index d652ca15..37c9abfb 100644 --- a/nest/route.h +++ b/nest/route.h @@ -195,7 +195,7 @@ struct hostentry { unsigned hash_key; /* Hash key */ unsigned uc; /* Use count */ struct rta *src; /* Source rta entry */ - ip_addr gw; /* Chosen next hop */ + struct nexthop *nh; /* Chosen next hop */ byte dest; /* Chosen route destination type (RTD_...) */ u32 igp_metric; /* Chosen route IGP metric */ }; @@ -332,11 +332,11 @@ void rt_show(struct rt_show_data *); * construction of BGP route attribute lists. */ -/* Multipath next-hop */ -struct mpnh { +/* Nexthop structure */ +struct nexthop { ip_addr gw; /* Next hop */ struct iface *iface; /* Outgoing interface */ - struct mpnh *next; + struct nexthop *next; byte weight; }; @@ -353,20 +353,19 @@ typedef struct rta { struct rta *next, **pprev; /* Hash chain */ u32 uc; /* Use count */ u32 hash_key; /* Hash over important fields */ - struct mpnh *nexthops; /* Next-hops for multipath routes */ struct ea_list *eattrs; /* Extended Attribute chain */ struct rte_src *src; /* Route source that created the route */ struct hostentry *hostentry; /* Hostentry for recursive next-hops */ - struct iface *iface; /* Outgoing interface */ - ip_addr gw; /* Next hop */ ip_addr from; /* Advertising router */ u32 igp_metric; /* IGP metric to next hop (for iBGP routes) */ - byte source; /* Route source (RTS_...) */ - byte scope; /* Route scope (SCOPE_... -- see ip.h) */ - byte cast; /* Casting type (RTC_...) */ - byte dest; /* Route destination type (RTD_...) */ - byte flags; /* Route flags (RTF_...), now unused */ - byte aflags; /* Attribute cache flags (RTAF_...) */ + u32 bf[0]; + u32 source:6; /* Route source (RTS_...) */ + u32 scope:6; /* Route scope (SCOPE_... -- see ip.h) */ + u32 cast:6; /* Casting type (RTC_...) */ + u32 dest:6; /* Route destination type (RTD_...) */ +// u32 eflags:8; /* Flags (RTAF_...) */ + u32 aflags:8; + struct nexthop nh; /* Next hop */ } rta; #define RTS_DUMMY 0 /* Dummy route to be removed soon */ @@ -391,12 +390,10 @@ typedef struct rta { #define RTC_MULTICAST 2 #define RTC_ANYCAST 3 /* IPv6 Anycast */ -#define RTD_ROUTER 0 /* Next hop is neighbor router */ -#define RTD_DEVICE 1 /* Points to device */ +#define RTD_UNICAST 0 /* Next hop is neighbor router */ #define RTD_BLACKHOLE 2 /* Silently drop packets */ #define RTD_UNREACHABLE 3 /* Reject as unreachable */ #define RTD_PROHIBIT 4 /* Administratively prohibited */ -#define RTD_MULTIPATH 5 /* Multipath route (nexthops != NULL) */ #define RTD_NONE 6 /* Invalid RTD */ /* Flags for net->n.flags, used by kernel syncer */ @@ -411,7 +408,7 @@ typedef struct rta { /* Route has regular, reachable nexthop (i.e. not RTD_UNREACHABLE and like) */ static inline int rte_is_reachable(rte *r) -{ uint d = r->attrs->dest; return (d == RTD_ROUTER) || (d == RTD_DEVICE) || (d == RTD_MULTIPATH); } +{ uint d = r->attrs->dest; return (d == RTD_UNICAST); } /* @@ -516,12 +513,14 @@ uint ea_hash(ea_list *e); /* Calculate 16-bit hash value */ ea_list *ea_append(ea_list *to, ea_list *what); void ea_format_bitfield(struct eattr *a, byte *buf, int bufsize, const char **names, int min, int max); -int mpnh__same(struct mpnh *x, struct mpnh *y); /* Compare multipath nexthops */ -static inline int mpnh_same(struct mpnh *x, struct mpnh *y) -{ return (x == y) || mpnh__same(x, y); } -struct mpnh *mpnh_merge(struct mpnh *x, struct mpnh *y, int rx, int ry, int max, linpool *lp); -void mpnh_insert(struct mpnh **n, struct mpnh *y); -int mpnh_is_sorted(struct mpnh *x); +int nexthop__same(struct nexthop *x, struct nexthop *y); /* Compare multipath nexthops */ +static inline int nexthop_same(struct nexthop *x, struct nexthop *y) +{ return (x == y) || nexthop__same(x, y); } +struct nexthop *nexthop_merge(struct nexthop *x, struct nexthop *y, int rx, int ry, int max, linpool *lp); +static inline void nexthop_link(struct rta *a, struct nexthop *from) +{ a->nh.gw = from->gw; a->nh.iface = from->iface; a->nh.weight = from->weight; a->nh.next = from->next; } +void nexthop_insert(struct nexthop *n, struct nexthop *y); +int nexthop_is_sorted(struct nexthop *x); void rta_init(void); rta *rta_lookup(rta *); /* Get rta equivalent to this one, uc++ */ diff --git a/nest/rt-attr.c b/nest/rt-attr.c index 94f25de8..0eacfe3f 100644 --- a/nest/rt-attr.c +++ b/nest/rt-attr.c @@ -61,7 +61,7 @@ pool *rta_pool; static slab *rta_slab; -static slab *mpnh_slab; +static slab *nexthop_slab; static slab *rte_src_slab; static struct idm src_ids; @@ -144,7 +144,7 @@ rt_prune_sources(void) */ static inline u32 -mpnh_hash(struct mpnh *x) +nexthop_hash(struct nexthop *x) { u32 h = 0; for (; x; x = x->next) @@ -154,7 +154,7 @@ mpnh_hash(struct mpnh *x) } int -mpnh__same(struct mpnh *x, struct mpnh *y) +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->weight != y->weight)) @@ -164,7 +164,7 @@ mpnh__same(struct mpnh *x, struct mpnh *y) } static int -mpnh_compare_node(struct mpnh *x, struct mpnh *y) +nexthop_compare_node(struct nexthop *x, struct nexthop *y) { int r; @@ -185,10 +185,10 @@ mpnh_compare_node(struct mpnh *x, struct mpnh *y) return ((int) x->iface->index) - ((int) y->iface->index); } -static inline struct mpnh * -mpnh_copy_node(const struct mpnh *src, linpool *lp) +static inline struct nexthop * +nexthop_copy_node(const struct nexthop *src, linpool *lp) { - struct mpnh *n = lp_alloc(lp, sizeof(struct mpnh)); + struct nexthop *n = lp_alloc(lp, sizeof(struct nexthop)); n->gw = src->gw; n->iface = src->iface; n->next = NULL; @@ -197,7 +197,7 @@ mpnh_copy_node(const struct mpnh *src, linpool *lp) } /** - * mpnh_merge - merge nexthop lists + * nexthop_merge - merge nexthop lists * @x: list 1 * @y: list 2 * @rx: reusability of list @x @@ -205,7 +205,7 @@ mpnh_copy_node(const struct mpnh *src, linpool *lp) * @max: max number of nexthops * @lp: linpool for allocating nexthops * - * The mpnh_merge() function takes two nexthop lists @x and @y and merges them, + * 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. @@ -218,28 +218,28 @@ mpnh_copy_node(const struct mpnh *src, linpool *lp) * 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 nexthop * +nexthop_merge(struct nexthop *x, struct nexthop *y, int rx, int ry, int max, linpool *lp) { - struct mpnh *root = NULL; - struct mpnh **n = &root; + struct nexthop *root = NULL; + struct nexthop **n = &root; while ((x || y) && max--) { - int cmp = mpnh_compare_node(x, y); + int cmp = nexthop_compare_node(x, y); if (cmp < 0) { - *n = rx ? x : mpnh_copy_node(x, lp); + *n = rx ? x : nexthop_copy_node(x, lp); x = x->next; } else if (cmp > 0) { - *n = ry ? y : mpnh_copy_node(y, lp); + *n = ry ? y : nexthop_copy_node(y, lp); y = y->next; } else { - *n = rx ? x : (ry ? y : mpnh_copy_node(x, lp)); + *n = rx ? x : (ry ? y : nexthop_copy_node(x, lp)); x = x->next; y = y->next; } @@ -251,43 +251,55 @@ mpnh_merge(struct mpnh *x, struct mpnh *y, int rx, int ry, int max, linpool *lp) } void -mpnh_insert(struct mpnh **n, struct mpnh *x) +nexthop_insert(struct nexthop *n, struct nexthop *x) { - for (; *n; n = &((*n)->next)) + struct nexthop tmp; + memcpy(&tmp, n, sizeof(struct nexthop)); + if (nexthop_compare_node(n, x) > 0) /* Insert to the included nexthop */ { - int cmp = mpnh_compare_node(*n, x); + memcpy(n, x, sizeof(struct nexthop)); + memcpy(x, &tmp, sizeof(struct nexthop)); + n->next = x; + return; + } + + for (struct nexthop **nn = &(n->next); *nn; nn = &((*nn)->next)) + { + int cmp = nexthop_compare_node(*nn, x); if (cmp < 0) continue; - else if (cmp > 0) - break; - else - return; + + if (cmp > 0) + { + x->next = *nn; + *nn = x; + } + + return; } - x->next = *n; - *n = x; } int -mpnh_is_sorted(struct mpnh *x) +nexthop_is_sorted(struct nexthop *x) { for (; x && x->next; x = x->next) - if (mpnh_compare_node(x, x->next) >= 0) + if (nexthop_compare_node(x, x->next) >= 0) return 0; return 1; } -static struct mpnh * -mpnh_copy(struct mpnh *o) +static struct nexthop * +nexthop_copy(struct nexthop *o) { - struct mpnh *first = NULL; - struct mpnh **last = &first; + struct nexthop *first = NULL; + struct nexthop **last = &first; for (; o; o = o->next) { - struct mpnh *n = sl_alloc(mpnh_slab); + struct nexthop *n = sl_alloc(nexthop_slab); n->gw = o->gw; n->iface = o->iface; n->next = NULL; @@ -301,14 +313,14 @@ mpnh_copy(struct mpnh *o) } static void -mpnh_free(struct mpnh *o) +nexthop_free(struct nexthop *o) { - struct mpnh *n; + struct nexthop *n; while (o) { n = o->next; - sl_free(mpnh_slab, o); + sl_free(nexthop_slab, o); o = n; } } @@ -994,19 +1006,12 @@ rta_hash(rta *a) #define MIX(f) mem_hash_mix(&h, &(a->f), sizeof(a->f)); MIX(src); MIX(hostentry); - MIX(iface); - MIX(gw); MIX(from); MIX(igp_metric); - MIX(source); - MIX(scope); - MIX(cast); - MIX(dest); - MIX(flags); - MIX(aflags); + mem_hash_mix(&h, a->bf, sizeof(u32)); #undef MIX - return mem_hash_value(&h) ^ mpnh_hash(a->nexthops) ^ ea_hash(a->eattrs); + return mem_hash_value(&h) ^ nexthop_hash(&(a->nh)) ^ ea_hash(a->eattrs); } static inline int @@ -1017,13 +1022,12 @@ rta_same(rta *x, rta *y) x->scope == y->scope && x->cast == y->cast && x->dest == y->dest && - x->flags == y->flags && x->igp_metric == y->igp_metric && - ipa_equal(x->gw, y->gw) && + ipa_equal(x->nh.gw, y->nh.gw) && ipa_equal(x->from, y->from) && - x->iface == y->iface && + x->nh.iface == y->nh.iface && x->hostentry == y->hostentry && - mpnh_same(x->nexthops, y->nexthops) && + nexthop_same(&(x->nh), &(y->nh)) && ea_same(x->eattrs, y->eattrs)); } @@ -1034,7 +1038,7 @@ rta_copy(rta *o) memcpy(r, o, sizeof(rta)); r->uc = 1; - r->nexthops = mpnh_copy(o->nexthops); + r->nh.next = nexthop_copy(o->nh.next); r->eattrs = ea_list_copy(o->eattrs); return r; } @@ -1130,7 +1134,8 @@ rta__free(rta *a) a->aflags = 0; /* Poison the entry */ rt_unlock_hostentry(a->hostentry); rt_unlock_source(a->src); - mpnh_free(a->nexthops); + if (a->nh.next) + nexthop_free(a->nh.next); ea_free(a->eattrs); sl_free(rta_slab, a); } @@ -1167,10 +1172,12 @@ rta_dump(rta *a) 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); + debug(" [%s]", nh->iface ? nh->iface->name : "???"); + } if (a->eattrs) { debug(" EA: "); @@ -1228,7 +1235,7 @@ rta_init(void) { rta_pool = rp_new(&root_pool, "Attributes"); rta_slab = sl_new(rta_pool, sizeof(rta)); - mpnh_slab = sl_new(rta_pool, sizeof(struct mpnh)); + nexthop_slab = sl_new(rta_pool, sizeof(struct nexthop)); rta_alloc_hash(); rte_src_init(); } diff --git a/nest/rt-dev.c b/nest/rt-dev.c index d98cd79f..43628af8 100644 --- a/nest/rt-dev.c +++ b/nest/rt-dev.c @@ -79,8 +79,10 @@ dev_ifa_notify(struct proto *P, uint flags, struct ifa *ad) .source = RTS_DEVICE, .scope = SCOPE_UNIVERSE, .cast = RTC_UNICAST, - .dest = RTD_DEVICE, - .iface = ad->iface + .dest = RTD_UNICAST, + .nh = { + .iface = ad->iface + } }; a = rta_lookup(&a0); diff --git a/nest/rt-table.c b/nest/rt-table.c index 8c429874..46857d0d 100644 --- a/nest/rt-table.c +++ b/nest/rt-table.c @@ -708,19 +708,17 @@ rt_notify_accepted(struct channel *c, net *net, rte *new_changed, rte *old_chang } -static struct mpnh * -mpnh_merge_rta(struct mpnh *nhs, rta *a, linpool *pool, int max) +static struct nexthop * +nexthop_merge_rta(struct nexthop *nhs, rta *a, linpool *pool, int max) { - struct mpnh nh = { .gw = a->gw, .iface = a->iface }; - struct mpnh *nh2 = (a->dest == RTD_MULTIPATH) ? a->nexthops : &nh; - return mpnh_merge(nhs, nh2, 1, 0, max, pool); + return nexthop_merge(nhs, &(a->nh), 1, 0, max, pool); } rte * rt_export_merged(struct channel *c, net *net, rte **rt_free, ea_list **tmpa, linpool *pool, int silent) { // struct proto *p = c->proto; - struct mpnh *nhs = NULL; + struct nexthop *nhs = NULL; rte *best0, *best, *rt0, *rt, *tmp; best0 = net->routes; @@ -745,7 +743,7 @@ rt_export_merged(struct channel *c, net *net, rte **rt_free, ea_list **tmpa, lin continue; if (rte_is_reachable(rt)) - nhs = mpnh_merge_rta(nhs, rt->attrs, pool, c->merge_limit); + nhs = nexthop_merge_rta(nhs, rt->attrs, pool, c->merge_limit); if (tmp) rte_free(tmp); @@ -753,13 +751,12 @@ rt_export_merged(struct channel *c, net *net, rte **rt_free, ea_list **tmpa, lin if (nhs) { - nhs = mpnh_merge_rta(nhs, best->attrs, pool, c->merge_limit); + nhs = nexthop_merge_rta(nhs, best->attrs, pool, c->merge_limit); if (nhs->next) { best = rte_cow_rta(best, pool); - best->attrs->dest = RTD_MULTIPATH; - best->attrs->nexthops = nhs; + nexthop_link(best->attrs, nhs); } } @@ -922,7 +919,7 @@ rte_validate(rte *e) return 0; } - if ((e->attrs->dest == RTD_MULTIPATH) && !mpnh_is_sorted(e->attrs->nexthops)) + if ((e->attrs->dest == RTD_UNICAST) && !nexthop_is_sorted(&(e->attrs->nh))) { log(L_WARN "Ignoring unsorted multipath route %N received via %s", n->n.addr, e->sender->proto->name); @@ -1763,20 +1760,22 @@ rta_next_hop_outdated(rta *a) if (!he->src) return a->dest != RTD_UNREACHABLE; - return (a->iface != he->src->iface) || !ipa_equal(a->gw, he->gw) || - (a->dest != he->dest) || (a->igp_metric != he->igp_metric) || - !mpnh_same(a->nexthops, he->src->nexthops); + return (a->dest != he->dest) || (a->igp_metric != he->igp_metric) || + !nexthop_same(&(a->nh), he->nh); } static inline void rta_apply_hostentry(rta *a, struct hostentry *he) { a->hostentry = he; - a->iface = he->src ? he->src->iface : NULL; - a->gw = he->gw; + + a->nh.gw = ipa_nonzero(he->nh->gw) ? he->nh->gw : he->link; + a->nh.iface = he->nh->iface; + a->nh.weight = he->nh->weight; + a->nh.next = he->nh->next; + a->dest = he->dest; a->igp_metric = he->igp_metric; - a->nexthops = he->src ? he->src->nexthops : NULL; } static inline rte * @@ -2310,8 +2309,7 @@ rt_get_igp_metric(rte *rt) return rt->u.rip.metric; #endif - /* Device routes */ - if ((a->dest != RTD_ROUTER) && (a->dest != RTD_MULTIPATH)) + if (a->source == RTS_DEVICE) return 0; return IGP_METRIC_UNKNOWN; @@ -2325,7 +2323,6 @@ rt_update_hostentry(rtable *tab, struct hostentry *he) /* Reset the hostentry */ he->src = NULL; - he->gw = IPA_NONE; he->dest = RTD_UNREACHABLE; he->igp_metric = 0; @@ -2346,24 +2343,24 @@ rt_update_hostentry(rtable *tab, struct hostentry *he) goto done; } - if (a->dest == RTD_DEVICE) - { - if (if_local_addr(he->addr, a->iface)) + if ((a->dest == RTD_UNICAST) && ipa_zero(a->nh.gw) && !a->next) + { /* We have singlepath device route */ + if (if_local_addr(he->addr, a->nh.iface)) { /* The host address is a local address, this is not valid */ log(L_WARN "Next hop address %I is a local address of iface %s", - he->addr, a->iface->name); + he->addr, a->nh.iface->name); goto done; } /* The host is directly reachable, use link as a gateway */ - he->gw = he->link; - he->dest = RTD_ROUTER; + he->nh = NULL; + he->dest = RTD_UNICAST; } else { /* The host is reachable through some route entry */ - he->gw = a->gw; + he->nh = (&a->nh); he->dest = a->dest; } @@ -2442,16 +2439,21 @@ rt_format_via(rte *e) rta *a = e->attrs; /* Max text length w/o IP addr and interface name is 16 */ - static byte via[IPA_MAX_TEXT_LENGTH+sizeof(a->iface->name)+16]; + static byte via[IPA_MAX_TEXT_LENGTH+sizeof(a->nh.iface->name)+16]; switch (a->dest) { - case RTD_ROUTER: bsprintf(via, "via %I on %s", a->gw, a->iface->name); break; - case RTD_DEVICE: bsprintf(via, "dev %s", a->iface->name); break; + case RTD_UNICAST: if (a->nh.next) + bsprintf(via, "multipath"); + else + { + if (ipa_nonzero(a->nh.gw)) bsprintf(via, "via %I ", a->nh.gw); + bsprintf(via, "dev %s", a->nh.iface->name); + } + break; case RTD_BLACKHOLE: bsprintf(via, "blackhole"); break; case RTD_UNREACHABLE: bsprintf(via, "unreachable"); break; case RTD_PROHIBIT: bsprintf(via, "prohibited"); break; - case RTD_MULTIPATH: bsprintf(via, "multipath"); break; default: bsprintf(via, "???"); } return via; @@ -2466,10 +2468,10 @@ rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tm int primary = (e->net->routes == e); int sync_error = (e->net->n.flags & KRF_SYNC_ERROR); void (*get_route_info)(struct rte *, byte *buf, struct ea_list *attrs); - struct mpnh *nh; + struct nexthop *nh; tm_format_datetime(tm, &config->tf_route, e->lastmod); - if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw)) + if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->nh.gw)) bsprintf(from, " from %I", a->from); else from[0] = 0; @@ -2490,8 +2492,9 @@ rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tm bsprintf(info, " (%d)", e->pref); cli_printf(c, -1007, "%-18s %s [%s %s%s]%s%s", ia, rt_format_via(e), a->src->proto->name, tm, from, primary ? (sync_error ? " !" : " *") : "", info); - for (nh = a->nexthops; nh; nh = nh->next) - cli_printf(c, -1007, "\tvia %I on %s weight %d", nh->gw, nh->iface->name, nh->weight + 1); + if (a->nh.next) + for (nh = &(a->nh); nh; nh = nh->next) + cli_printf(c, -1007, "\tvia %I on %s weight %d", nh->gw, nh->iface->name, nh->weight + 1); if (d->verbose) rta_show(c, a, tmpa); } |