diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/nexthop.c | 62 | ||||
| -rw-r--r-- | lib/nexthop.h | 12 | ||||
| -rw-r--r-- | lib/nexthop_group.c | 130 | ||||
| -rw-r--r-- | lib/nexthop_group.h | 17 | ||||
| -rw-r--r-- | lib/route_types.txt | 2 |
5 files changed, 201 insertions, 22 deletions
diff --git a/lib/nexthop.c b/lib/nexthop.c index cf5bed3d62..73c2de0cd8 100644 --- a/lib/nexthop.c +++ b/lib/nexthop.c @@ -349,7 +349,7 @@ const char *nexthop2str(const struct nexthop *nexthop, char *str, int size) * left branch is 'resolved' and right branch is 'next': * https://en.wikipedia.org/wiki/Tree_traversal#/media/File:Sorted_binary_tree_preorder.svg */ -struct nexthop *nexthop_next(struct nexthop *nexthop) +struct nexthop *nexthop_next(const struct nexthop *nexthop) { if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE)) return nexthop->resolved; @@ -364,6 +364,19 @@ struct nexthop *nexthop_next(struct nexthop *nexthop) return NULL; } +/* Return the next nexthop in the tree that is resolved and active */ +struct nexthop *nexthop_next_active_resolved(const struct nexthop *nexthop) +{ + struct nexthop *next = nexthop_next(nexthop); + + while (next + && (CHECK_FLAG(next->flags, NEXTHOP_FLAG_RECURSIVE) + || !CHECK_FLAG(next->flags, NEXTHOP_FLAG_ACTIVE))) + next = nexthop_next(next); + + return next; +} + unsigned int nexthop_level(struct nexthop *nexthop) { unsigned int rv = 0; @@ -374,16 +387,13 @@ unsigned int nexthop_level(struct nexthop *nexthop) return rv; } -uint32_t nexthop_hash(const struct nexthop *nexthop) +/* Only hash word-sized things, let cmp do the rest. */ +uint32_t nexthop_hash_quick(const struct nexthop *nexthop) { uint32_t key = 0x45afe398; key = jhash_3words(nexthop->type, nexthop->vrf_id, nexthop->nh_label_type, key); - /* gate and blackhole are together in a union */ - key = jhash(&nexthop->gate, sizeof(nexthop->gate), key); - key = jhash(&nexthop->src, sizeof(nexthop->src), key); - key = jhash(&nexthop->rmap_src, sizeof(nexthop->rmap_src), key); if (nexthop->nh_label) { int labels = nexthop->nh_label->num_labels; @@ -410,17 +420,35 @@ uint32_t nexthop_hash(const struct nexthop *nexthop) key = jhash_1word(nexthop->nh_label->label[i], key); } - switch (nexthop->type) { - case NEXTHOP_TYPE_IPV4_IFINDEX: - case NEXTHOP_TYPE_IPV6_IFINDEX: - case NEXTHOP_TYPE_IFINDEX: - key = jhash_1word(nexthop->ifindex, key); - break; - case NEXTHOP_TYPE_BLACKHOLE: - case NEXTHOP_TYPE_IPV4: - case NEXTHOP_TYPE_IPV6: - break; - } + key = jhash_2words(nexthop->ifindex, + CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ONLINK), + key); + + return key; +} + + +#define GATE_SIZE 4 /* Number of uint32_t words in struct g_addr */ + +/* For a more granular hash */ +uint32_t nexthop_hash(const struct nexthop *nexthop) +{ + uint32_t gate_src_rmap_raw[GATE_SIZE * 3] = {}; + /* Get all the quick stuff */ + uint32_t key = nexthop_hash_quick(nexthop); + + assert(((sizeof(nexthop->gate) + sizeof(nexthop->src) + + sizeof(nexthop->rmap_src)) + / 3) + == (GATE_SIZE * sizeof(uint32_t))); + + memcpy(gate_src_rmap_raw, &nexthop->gate, GATE_SIZE); + memcpy(gate_src_rmap_raw + GATE_SIZE, &nexthop->src, GATE_SIZE); + memcpy(gate_src_rmap_raw + (2 * GATE_SIZE), &nexthop->rmap_src, + GATE_SIZE); + + key = jhash2(gate_src_rmap_raw, (GATE_SIZE * 3), key); + return key; } diff --git a/lib/nexthop.h b/lib/nexthop.h index 9dd5fc6fd3..fe029f1867 100644 --- a/lib/nexthop.h +++ b/lib/nexthop.h @@ -137,6 +137,14 @@ void nexthop_del_labels(struct nexthop *); * 32-bit hash of nexthop */ uint32_t nexthop_hash(const struct nexthop *nexthop); +/* + * Hash a nexthop only on word-sized attributes: + * - vrf_id + * - ifindex + * - type + * - (some) flags + */ +uint32_t nexthop_hash_quick(const struct nexthop *nexthop); extern bool nexthop_same(const struct nexthop *nh1, const struct nexthop *nh2); extern bool nexthop_same_no_labels(const struct nexthop *nh1, @@ -153,7 +161,9 @@ extern int nexthop_same_firsthop(struct nexthop *next1, struct nexthop *next2); extern const char *nexthop2str(const struct nexthop *nexthop, char *str, int size); -extern struct nexthop *nexthop_next(struct nexthop *nexthop); +extern struct nexthop *nexthop_next(const struct nexthop *nexthop); +extern struct nexthop * +nexthop_next_active_resolved(const struct nexthop *nexthop); extern unsigned int nexthop_level(struct nexthop *nexthop); /* Copies to an already allocated nexthop struct */ extern void nexthop_copy(struct nexthop *copy, const struct nexthop *nexthop, diff --git a/lib/nexthop_group.c b/lib/nexthop_group.c index 9564321d38..9552f89568 100644 --- a/lib/nexthop_group.c +++ b/lib/nexthop_group.c @@ -81,6 +81,17 @@ uint8_t nexthop_group_nexthop_num(const struct nexthop_group *nhg) return num; } +uint8_t nexthop_group_nexthop_num_no_recurse(const struct nexthop_group *nhg) +{ + struct nexthop *nhop; + uint8_t num = 0; + + for (nhop = nhg->nexthop; nhop; nhop = nhop->next) + num++; + + return num; +} + uint8_t nexthop_group_active_nexthop_num(const struct nexthop_group *nhg) { struct nexthop *nhop; @@ -94,7 +105,22 @@ uint8_t nexthop_group_active_nexthop_num(const struct nexthop_group *nhg) return num; } -struct nexthop *nexthop_exists(struct nexthop_group *nhg, struct nexthop *nh) +uint8_t +nexthop_group_active_nexthop_num_no_recurse(const struct nexthop_group *nhg) +{ + struct nexthop *nhop; + uint8_t num = 0; + + for (nhop = nhg->nexthop; nhop; nhop = nhop->next) { + if (CHECK_FLAG(nhop->flags, NEXTHOP_FLAG_ACTIVE)) + num++; + } + + return num; +} + +struct nexthop *nexthop_exists(const struct nexthop_group *nhg, + const struct nexthop *nh) { struct nexthop *nexthop; @@ -106,6 +132,74 @@ struct nexthop *nexthop_exists(struct nexthop_group *nhg, struct nexthop *nh) return NULL; } +static bool +nexthop_group_equal_common(const struct nexthop_group *nhg1, + const struct nexthop_group *nhg2, + uint8_t (*nexthop_group_nexthop_num_func)( + const struct nexthop_group *nhg)) +{ + if (nhg1 && !nhg2) + return false; + + if (!nhg1 && nhg2) + return false; + + if (nhg1 == nhg2) + return true; + + if (nexthop_group_nexthop_num_func(nhg1) + != nexthop_group_nexthop_num_func(nhg2)) + return false; + + return true; +} + +/* This assumes ordered */ +bool nexthop_group_equal_no_recurse(const struct nexthop_group *nhg1, + const struct nexthop_group *nhg2) +{ + struct nexthop *nh1 = NULL; + struct nexthop *nh2 = NULL; + + if (!nexthop_group_equal_common(nhg1, nhg2, + &nexthop_group_nexthop_num_no_recurse)) + return false; + + for (nh1 = nhg1->nexthop, nh2 = nhg2->nexthop; nh1 || nh2; + nh1 = nh1->next, nh2 = nh2->next) { + if (nh1 && !nh2) + return false; + if (!nh1 && nh2) + return false; + if (!nexthop_same(nh1, nh2)) + return false; + } + + return true; +} + +/* This assumes ordered */ +bool nexthop_group_equal(const struct nexthop_group *nhg1, + const struct nexthop_group *nhg2) +{ + struct nexthop *nh1 = NULL; + struct nexthop *nh2 = NULL; + + if (!nexthop_group_equal_common(nhg1, nhg2, &nexthop_group_nexthop_num)) + return false; + + for (nh1 = nhg1->nexthop, nh2 = nhg2->nexthop; nh1 || nh2; + nh1 = nexthop_next(nh1), nh2 = nexthop_next(nh2)) { + if (nh1 && !nh2) + return false; + if (!nh1 && nh2) + return false; + if (!nexthop_same(nh1, nh2)) + return false; + } + + return true; +} struct nexthop_group *nexthop_group_new(void) { return XCALLOC(MTYPE_NEXTHOP_GROUP, sizeof(struct nexthop_group)); @@ -119,6 +213,9 @@ void nexthop_group_copy(struct nexthop_group *to, struct nexthop_group *from) void nexthop_group_delete(struct nexthop_group **nhg) { + if ((*nhg)->nexthop) + nexthops_free((*nhg)->nexthop); + XFREE(MTYPE_NEXTHOP_GROUP, *nhg); } @@ -217,7 +314,7 @@ void copy_nexthops(struct nexthop **tnh, const struct nexthop *nh, } } -uint32_t nexthop_group_hash(const struct nexthop_group *nhg) +uint32_t nexthop_group_hash_no_recurse(const struct nexthop_group *nhg) { struct nexthop *nh; uint32_t key = 0; @@ -232,6 +329,35 @@ uint32_t nexthop_group_hash(const struct nexthop_group *nhg) return key; } +uint32_t nexthop_group_hash(const struct nexthop_group *nhg) +{ + struct nexthop *nh; + uint32_t key = 0; + + for (ALL_NEXTHOPS_PTR(nhg, nh)) + key = jhash_1word(nexthop_hash(nh), key); + + return key; +} + +void nexthop_group_mark_duplicates(struct nexthop_group *nhg) +{ + struct nexthop *nexthop, *prev; + + for (ALL_NEXTHOPS_PTR(nhg, nexthop)) { + UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_DUPLICATE); + for (ALL_NEXTHOPS_PTR(nhg, prev)) { + if (prev == nexthop) + break; + if (nexthop_same_firsthop(nexthop, prev)) { + SET_FLAG(nexthop->flags, + NEXTHOP_FLAG_DUPLICATE); + break; + } + } + } +} + static void nhgc_delete_nexthops(struct nexthop_group_cmd *nhgc) { struct nexthop *nexthop; diff --git a/lib/nexthop_group.h b/lib/nexthop_group.h index 4f4d40eb33..391775c69c 100644 --- a/lib/nexthop_group.h +++ b/lib/nexthop_group.h @@ -47,7 +47,9 @@ void nexthop_group_copy(struct nexthop_group *to, void copy_nexthops(struct nexthop **tnh, const struct nexthop *nh, struct nexthop *rparent); +uint32_t nexthop_group_hash_no_recurse(const struct nexthop_group *nhg); uint32_t nexthop_group_hash(const struct nexthop_group *nhg); +void nexthop_group_mark_duplicates(struct nexthop_group *nhg); /* The following for loop allows to iterate over the nexthop * structure of routes. @@ -110,8 +112,15 @@ void nexthop_group_disable_vrf(struct vrf *vrf); void nexthop_group_interface_state_change(struct interface *ifp, ifindex_t oldifindex); -extern struct nexthop *nexthop_exists(struct nexthop_group *nhg, - struct nexthop *nh); +extern struct nexthop *nexthop_exists(const struct nexthop_group *nhg, + const struct nexthop *nh); +/* This assumes ordered */ +extern bool nexthop_group_equal_no_recurse(const struct nexthop_group *nhg1, + const struct nexthop_group *nhg2); + +/* This assumes ordered */ +extern bool nexthop_group_equal(const struct nexthop_group *nhg1, + const struct nexthop_group *nhg2); extern struct nexthop_group_cmd *nhgc_find(const char *name); @@ -120,7 +129,11 @@ extern void nexthop_group_write_nexthop(struct vty *vty, struct nexthop *nh); /* Return the number of nexthops in this nhg */ extern uint8_t nexthop_group_nexthop_num(const struct nexthop_group *nhg); extern uint8_t +nexthop_group_nexthop_num_no_recurse(const struct nexthop_group *nhg); +extern uint8_t nexthop_group_active_nexthop_num(const struct nexthop_group *nhg); +extern uint8_t +nexthop_group_active_nexthop_num_no_recurse(const struct nexthop_group *nhg); #ifdef __cplusplus } diff --git a/lib/route_types.txt b/lib/route_types.txt index 59f3a91cf0..71d0a46449 100644 --- a/lib/route_types.txt +++ b/lib/route_types.txt @@ -84,6 +84,7 @@ ZEBRA_ROUTE_PBR, pbr, pbrd, 'F', 1, 1, 0, "PBR" ZEBRA_ROUTE_BFD, bfd, bfdd, '-', 0, 0, 0, "BFD" ZEBRA_ROUTE_OPENFABRIC, openfabric, fabricd, 'f', 1, 1, 1, "OpenFabric" ZEBRA_ROUTE_VRRP, vrrp, vrrpd, '-', 0, 0, 0, "VRRP" +ZEBRA_ROUTE_NHG, nhg, none, '-', 0, 0, 0, "Nexthop Group" ZEBRA_ROUTE_ALL, wildcard, none, '-', 0, 0, 0, "-" @@ -113,3 +114,4 @@ ZEBRA_ROUTE_PBR, "Policy Based Routing (PBR)" ZEBRA_ROUTE_BFD, "Bidirectional Fowarding Detection (BFD)" ZEBRA_ROUTE_VRRP, "Virtual Router Redundancy Protocol (VRRP)" ZEBRA_ROUTE_OPENFABRIC, "OpenFabric Routing Protocol" +ZEBRA_ROUTE_NHG, "Zebra Nexthop Groups (NHG)" |