From e1f3a8eb193267da195088cc515b598ae5a92a12 Mon Sep 17 00:00:00 2001 From: Mark Stapp Date: Mon, 9 Dec 2019 16:02:57 -0500 Subject: [PATCH] lib,zebra: add api to enforce nexthop sort order when copying Add an api that creates a copy of a list of nexthops and enforces the canonical sort ordering; consolidate some nhg code to avoid copy-and-paste. The zebra dplane uses that api when a plugin sets up a list of nexthops, ensuring that the plugin's list is ordered when it's processed in zebra. Signed-off-by: Mark Stapp --- lib/nexthop_group.c | 81 ++++++++++++++++++++++++++++++++++---------- lib/nexthop_group.h | 7 ++++ zebra/zebra_dplane.c | 7 +++- 3 files changed, 76 insertions(+), 19 deletions(-) diff --git a/lib/nexthop_group.c b/lib/nexthop_group.c index b810d13a5a..e1c1b1ca84 100644 --- a/lib/nexthop_group.c +++ b/lib/nexthop_group.c @@ -243,25 +243,16 @@ void _nexthop_add(struct nexthop **target, struct nexthop *nexthop) nexthop->prev = last; } -void nexthop_group_add_sorted(struct nexthop_group *nhg, - struct nexthop *nexthop) +/* Add nexthop to sorted list of nexthops */ +static void _nexthop_add_sorted(struct nexthop **head, + struct nexthop *nexthop) { - struct nexthop *position, *prev, *tail; - - /* Try to just append to the end first - * This trust it is already sorted - */ - - tail = nexthop_group_tail(nhg); + struct nexthop *position, *prev; - if (tail && (nexthop_cmp(tail, nexthop) < 0)) { - tail->next = nexthop; - nexthop->prev = tail; - - return; - } + /* Ensure this gets set */ + nexthop->next = NULL; - for (position = nhg->nexthop, prev = NULL; position; + for (position = *head, prev = NULL; position; prev = position, position = position->next) { if (nexthop_cmp(position, nexthop) > 0) { nexthop->next = position; @@ -270,7 +261,7 @@ void nexthop_group_add_sorted(struct nexthop_group *nhg, if (nexthop->prev) nexthop->prev->next = nexthop; else - nhg->nexthop = nexthop; + *head = nexthop; position->prev = nexthop; return; @@ -281,7 +272,27 @@ void nexthop_group_add_sorted(struct nexthop_group *nhg, if (prev) prev->next = nexthop; else - nhg->nexthop = nexthop; + *head = nexthop; +} + +void nexthop_group_add_sorted(struct nexthop_group *nhg, + struct nexthop *nexthop) +{ + struct nexthop *tail; + + /* Try to just append to the end first; + * trust the list is already sorted + */ + tail = nexthop_group_tail(nhg); + + if (tail && (nexthop_cmp(tail, nexthop) < 0)) { + tail->next = nexthop; + nexthop->prev = tail; + + return; + } + + _nexthop_add_sorted(&nhg->nexthop, nexthop); } /* Delete nexthop from a nexthop list. */ @@ -308,6 +319,40 @@ void _nexthop_del(struct nexthop_group *nhg, struct nexthop *nh) nh->next = NULL; } +/* + * Copy a list of nexthops in 'nh' to an nhg, enforcing canonical sort order + */ +void nexthop_group_copy_nh_sorted(struct nexthop_group *nhg, + const struct nexthop *nh) +{ + struct nexthop *nexthop, *tail; + const struct nexthop *nh1; + + /* We'll try to append to the end of the new list; + * if the original list in nh is already sorted, this eliminates + * lots of comparison operations. + */ + tail = nexthop_group_tail(nhg); + + for (nh1 = nh; nh1; nh1 = nh1->next) { + nexthop = nexthop_dup(nh1, NULL); + + if (tail && (nexthop_cmp(tail, nexthop) < 0)) { + tail->next = nexthop; + nexthop->prev = tail; + + tail = nexthop; + continue; + } + + _nexthop_add_sorted(&nhg->nexthop, nexthop); + + if (tail == NULL) + tail = nexthop; + } +} + +/* Copy a list of nexthops, no effort made to sort or order them. */ void copy_nexthops(struct nexthop **tnh, const struct nexthop *nh, struct nexthop *rparent) { diff --git a/lib/nexthop_group.h b/lib/nexthop_group.h index c90b21737a..73b020283a 100644 --- a/lib/nexthop_group.h +++ b/lib/nexthop_group.h @@ -44,6 +44,13 @@ void nexthop_group_delete(struct nexthop_group **nhg); void nexthop_group_copy(struct nexthop_group *to, struct nexthop_group *from); + +/* + * Copy a list of nexthops in 'nh' to an nhg, enforcing canonical sort order + */ +void nexthop_group_copy_nh_sorted(struct nexthop_group *nhg, + const struct nexthop *nh); + void copy_nexthops(struct nexthop **tnh, const struct nexthop *nh, struct nexthop *rparent); diff --git a/zebra/zebra_dplane.c b/zebra/zebra_dplane.c index ca72ea5227..ef942151b0 100644 --- a/zebra/zebra_dplane.c +++ b/zebra/zebra_dplane.c @@ -1023,6 +1023,11 @@ uint8_t dplane_ctx_get_old_distance(const struct zebra_dplane_ctx *ctx) return ctx->u.rinfo.zd_old_distance; } +/* + * Set the nexthops associated with a context: note that processing code + * may well expect that nexthops are in canonical (sorted) order, so we + * will enforce that here. + */ void dplane_ctx_set_nexthops(struct zebra_dplane_ctx *ctx, struct nexthop *nh) { DPLANE_CTX_VALID(ctx); @@ -1031,7 +1036,7 @@ void dplane_ctx_set_nexthops(struct zebra_dplane_ctx *ctx, struct nexthop *nh) nexthops_free(ctx->u.rinfo.zd_ng.nexthop); ctx->u.rinfo.zd_ng.nexthop = NULL; } - copy_nexthops(&(ctx->u.rinfo.zd_ng.nexthop), nh, NULL); + nexthop_group_copy_nh_sorted(&(ctx->u.rinfo.zd_ng), nh); } const struct nexthop_group *dplane_ctx_get_ng( -- 2.39.5