diff options
| -rw-r--r-- | nest/route.h | 1 | ||||
| -rw-r--r-- | nest/rt-attr.c | 94 | ||||
| -rw-r--r-- | proto/ospf/rt.c | 104 | ||||
| -rw-r--r-- | proto/ospf/rt.h | 3 | ||||
| -rw-r--r-- | proto/ospf/topology.h | 2 |
5 files changed, 110 insertions, 94 deletions
diff --git a/nest/route.h b/nest/route.h index 8f3c7c9a..e22f950b 100644 --- a/nest/route.h +++ b/nest/route.h @@ -482,6 +482,7 @@ void ea_format_bitfield(struct eattr *a, byte *buf, int bufsize, const char **na 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 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 85a192c8..32090b52 100644 --- a/nest/rt-attr.c +++ b/nest/rt-attr.c @@ -167,7 +167,7 @@ rt_get_source(struct proto *p, u32 id) src->private_id = id; src->global_id = rte_src_alloc_id(); src->uc = 0; - + HASH_INSERT2(src_hash, RSH, rta_pool, src); return src; @@ -215,6 +215,94 @@ mpnh__same(struct mpnh *x, struct mpnh *y) 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; +} + + static struct mpnh * mpnh_copy(struct mpnh *o) { @@ -635,7 +723,7 @@ get_generic_attr(eattr *a, byte **buf, int buflen UNUSED) *buf += bsprintf(*buf, "igp_metric"); return GA_NAME; } - + return GA_UNKNOWN; } @@ -741,7 +829,7 @@ ea_show(struct cli *c, eattr *e) } 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) diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c index e74bcae6..cdf8012a 100644 --- a/proto/ospf/rt.c +++ b/proto/ospf/rt.c @@ -53,88 +53,6 @@ new_nexthop(struct ospf_proto *p, ip_addr gw, struct iface *iface, byte weight) return nh; } -static inline struct mpnh * -copy_nexthop(struct ospf_proto *p, const struct mpnh *src) -{ - struct mpnh *nh = lp_alloc(p->nhpool, sizeof(struct mpnh)); - nh->gw = src->gw; - nh->iface = src->iface; - nh->next = NULL; - nh->weight = src->weight; - return nh; -} - -/* Compare nexthops during merge. - We need to maintain nhs sorted to eliminate duplicities */ -static int -cmp_nhs(struct mpnh *s1, struct mpnh *s2) -{ - int r; - - if (!s1) - return 1; - - if (!s2) - return -1; - - r = ((int) s2->weight) - ((int) s1->weight); - if (r) - return r; - - r = ipa_compare(s1->gw, s2->gw); - if (r) - return r; - - return ((int) s1->iface->index) - ((int) s2->iface->index); -} - -static struct mpnh * -merge_nexthops(struct ospf_proto *p, struct mpnh *s1, struct mpnh *s2, int r1, int r2) -{ - struct mpnh *root = NULL; - struct mpnh **n = &root; - int count = p->ecmp; - - ASSERT(p->ecmp); - - /* - * r1, r2 signalize whether we can reuse nexthops from s1, s2. - * New nexthops (s2, new) can be reused if they are not inherited - * from the parent (i.e. it is allocated in calc_next_hop()). - * Current nexthops (s1, en->nhs) can be reused if they weren't - * inherited in previous steps (that is stored in nhs_reuse, - * i.e. created by merging or allocalted in calc_next_hop()). - * - * Generally, a node first inherits shared nexthops from its - * parent and later possibly gets reusable copy during merging. - */ - - while ((s1 || s2) && count--) - { - int cmp = cmp_nhs(s1, s2); - if (cmp < 0) - { - *n = r1 ? s1 : copy_nexthop(p, s1); - s1 = s1->next; - } - else if (cmp > 0) - { - *n = r2 ? s2 : copy_nexthop(p, s2); - s2 = s2->next; - } - else - { - *n = r1 ? s1 : (r2 ? s2 : copy_nexthop(p, s1)); - s1 = s1->next; - s2 = s2->next; - } - n = &((*n)->next); - } - *n = NULL; - - return root; -} - /* Returns true if there are device nexthops in n */ static inline int has_device_nexthops(const struct mpnh *n) @@ -178,7 +96,7 @@ fix_device_nexthops(struct ospf_proto *p, const struct mpnh *n, ip_addr gw) } } - return merge_nexthops(p, root1, root2, 1, 1); + return mpnh_merge(root1, root2, 1, 1, p->ecmp, p->nhpool); } @@ -374,7 +292,8 @@ ort_merge(struct ospf_proto *p, ort *o, const orta *new) if (old->nhs != new->nhs) { - old->nhs = merge_nexthops(p, old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse); + old->nhs = mpnh_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse, + p->ecmp, p->nhpool); old->nhs_reuse = 1; } @@ -389,7 +308,8 @@ ort_merge_ext(struct ospf_proto *p, ort *o, const orta *new) if (old->nhs != new->nhs) { - old->nhs = merge_nexthops(p, old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse); + old->nhs = mpnh_merge(old->nhs, new->nhs, old->nhs_reuse, new->nhs_reuse, + p->ecmp, p->nhpool); old->nhs_reuse = 1; } @@ -1885,8 +1805,7 @@ add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par, return; } - /* We know that en->color == CANDIDATE and en->nhs is defined. */ - + /* If en->dist > 0, we know that en->color == CANDIDATE and en->nhs is defined. */ if ((dist == en->dist) && !nh_is_vlink(en->nhs)) { /* @@ -1900,7 +1819,14 @@ add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par, * allocated in calc_next_hop()). * * Generally, a node first inherits shared nexthops from its parent and - * later possibly gets reusable copy during merging. + * later possibly gets reusable (private) copy during merging. This is more + * or less same for both top_hash_entry nodes and orta nodes. + * + * Note that when a child inherits a private nexthop from its parent, it + * should make the nexthop shared for both parent and child, while we only + * update nhs_reuse for the child node. This makes nhs_reuse field for the + * parent technically incorrect, but it is not a problem as parent's nhs + * will not be modified (and nhs_reuse examined) afterwards. */ /* Keep old ones */ @@ -1909,7 +1835,7 @@ add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par, /* Merge old and new */ int new_reuse = (par->nhs != nhs); - en->nhs = merge_nexthops(p, en->nhs, nhs, en->nhs_reuse, new_reuse); + en->nhs = mpnh_merge(en->nhs, nhs, en->nhs_reuse, new_reuse, p->ecmp, p->nhpool); en->nhs_reuse = 1; return; } diff --git a/proto/ospf/rt.h b/proto/ospf/rt.h index 61936f3c..30332f3b 100644 --- a/proto/ospf/rt.h +++ b/proto/ospf/rt.h @@ -18,7 +18,8 @@ typedef struct orta { u8 type; /* RTS_OSPF_* */ - u8 nhs_reuse; /* Whether nhs nodes can be reused during merging */ + u8 nhs_reuse; /* Whether nhs nodes can be reused during merging. + See a note in rt.c:add_cand() */ u32 options; /* * For ORT_ROUTER routes, options field are router-LSA style diff --git a/proto/ospf/topology.h b/proto/ospf/topology.h index e2d6c773..5652ced0 100644 --- a/proto/ospf/topology.h +++ b/proto/ospf/topology.h @@ -39,7 +39,7 @@ struct top_hash_entry #define INSPF 2 u8 mode; /* LSA generated during RT calculation (LSA_RTCALC or LSA_STALE)*/ u8 nhs_reuse; /* Whether nhs nodes can be reused during merging. - See a note in rt.c:merge_nexthops() */ + See a note in rt.c:add_cand() */ }; |