Hi Rosemarie, Thanks for your review.
Em qua., 14 de out. de 2026 às 09:15, Rosemarie O'Riorden < [email protected]> escreveu: > Hi Lucas, thanks for the new version! > > I had a lot of thoughts about your last version that took me too long to > organize. So I'm sorry for sending such a massive review too late to > catch you on v2. > > Basically, as soon as I saw ecmp_route_list_node_cmp() for the first > time, it felt off to me, but I couldn't exactly articulate why. After > much consideration, I believe the whole route ordering system is overly > complicated and could be much simpler and easier. Basically, we want > routes to be in *some* order, but it doesn't really matter which order. > Sure, the flow dumps might be more readable if routes are sorted by .10 > -> .20 -> .30, but the point of this patch is to make the routes ordered > deterministically between full recomute and icremental processing. > > For this reason, route ordering could be accomplished using only UUID. > It's the only characteristic of each route that is guaranteed to be > unique, so checking the others is ultimately unnecessary. This would > eliminate over 30 lines of repetitive code from just that one function. > I agree > > The same principle can be applied to groups. Groups don't themselves > have UUIDs so what unique characteristic can we use to order them? Well, > they contain the vector with the ordered routes, which have UUIDs. So we > could just use the first UUID of the first route of each group. > > I agree > Now, I want to talk about the IDs assigned to routes and route groups. > Say we have multiple routes ordered by UUID, and we remove one from the > middle, or add one whose UUID is lexicographically in the middle. This > means that all of the following routes are now assigned new IDs, which > means those flows have to be rewritten. Maybe we could try to keep IDs > unique per route/group and unrelated to order, so these flows don't have > to be completely rewritten when nothing about them even changed, besides > the number of routes before them... So now if we can't rely on > processing order, nor details of the routes beyond UUID, how do we > translate that into an index...? > > We could use a similar system as a hashmap, where elements are hashed > into different locations based on their contents. The only guaranteed > unique content of each route is its UUID. So we could "hash" this by > taking the UUID % (size of register) and making that value the ID. The > same concept could be applied to route groups, using their first route's > UUID as I mentioned above. This might look strange to have two routes > and for their IDs to be 4879 and 29387 rather than 1 and 2, but I think > it's ok for the efficiency benefit :) > > The only issue here is collisions, as we can't use buckets like in a > hashmap... And although they'd be very unlikely, we still need to > account for that. So maybe we could use a simpler way like if an index > is already in use, giving its collision the index (index + > num_of_collisions). But this means we need a way to track collisions, > and we need to make sure that indices we choose aren't already in use by > another route/group. I didn't fully think out the details of this so I'm > interested to hear your thoughts. > > Overall, the biggest con to this idea is that random indices may > complicate testing a bit, as would the UUID-based ordering, but I feel > it would be a minor inconvenience in exchange for the simplicity of the > code. > > Thanks for taking the time to hear out my thoughts! I'm excited to hear > what you think. > I agree with your points. I didn't think about using UUID and something like a hashmap. I have some points: - Members: the UUID alone isn't unique within a group. Redistributed NAT and LB routes use the NAT or Load_Balancer row as source_hint, and one row produces one route per path to the peer router, e.g. when the peer is reachable through two ports. I think the member hash could be the source_hint UUID, the nexthop and the output port. - Groups: instead of the first route's UUID I'll hash the group key (prefix, plen, route table, src/dst and source class, the same key ecmp_groups_find() uses). The first member changes when it's removed or when a member with a smaller UUID is added, and then the id of the whole group would change. The key is unique within a datapath and stays the same as members come and go. - Collisions: resolving them with "index + number of collisions" would make the ids depend on which element got the slot first, i.e. on processing order again, which is what this patch fixes. Instead, when two elements derive the same id, both retry in the next round with an id derived from their hash and the round number. The result only depends on the set of routes. Adding an element can occasionally move a colliding one, but that stays local and rare. - The members are listed in the select() action in id order, otherwise the action text would still depend on insertion order. Sorry for not CCing you before. I'll do it from now on. Regards, Lucas > BTW in the future please try to CC your reviewers so we can stay up to > date on the series :) > > Take care, > Rosemarie O'Riorden > > On 10/13/26 3:59 PM, Lucas Vargas Dias via dev wrote: > > The ECMP group id and the member ids are written into the > > lr_in_ip_routing and lr_in_ip_routing_ecmp logical flows, but they > > were assigned from the order in which routes reached > > en_group_ecmp_route: the group id was hmap_count() at creation time > > and the member id was the insertion position. On a full recompute > > the routes are walked in hmap order, while incremental processing > > appends them in event order, so the same set of routes could get a > > different numbering. Every forced or fallback recompute could then > > delete and re-insert Logical_Flow rows in the Southbound DB even > > though nothing had changed. > > > > Fixes: 6979a96138a2 ("northd: Support I+P for group_ecmp_route engine.") > > Fixes: 5395e12f247c ("northd: Drop traffic for ECMP group with "discard" > route.") > > Assisted-by: Claude Opus 5.5, Claude Code > > Signed-off-by: Lucas Vargas Dias <[email protected]> > > --- > > v3: > > - Dropped nullable_strcmp() and the patch converting its callers; use > > nullable_string_is_equal() in the member comparison instead. > > - Removed the unused 'route_count' field from struct ecmp_groups_node. > > v2: > > - Moved nullable_strcmp() to lib/ovn-util.h and documented its NULL > > handling. > > - Clarified in ecmp_groups_node_cmp() that it can't return 0 for two > > distinct groups. > > > > northd/en-group-ecmp-route.c | 167 +++++++++++++++++++++++++++++------ > > northd/en-group-ecmp-route.h | 1 - > > tests/ovn-northd.at | 66 ++++++++++++++ > > 3 files changed, 207 insertions(+), 27 deletions(-) > > > > diff --git a/northd/en-group-ecmp-route.c b/northd/en-group-ecmp-route.c > > index aca197318..f84155608 100644 > > --- a/northd/en-group-ecmp-route.c > > +++ b/northd/en-group-ecmp-route.c > > @@ -228,14 +228,12 @@ ecmp_groups_add_route(struct ecmp_groups_node > *group, > > const struct parsed_route *route) > > { > > static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1); > > - if (group->route_count == UINT16_MAX) { > > + if (vector_len(&group->route_list) == UINT16_MAX) { > > VLOG_WARN_RL(&rl, "too many routes in a single ecmp group."); > > return; > > } > > > > if (route->is_discard_route) { > > - group->has_discard_route = true; > > - > > char *prefix = normalize_v46_prefix(&route->prefix, > route->plen); > > VLOG_WARN_RL(&rl, "The ECMP route \"%s\" contains \"discard\" " > > "route, the whole group will drop traffic.", > prefix); > > @@ -244,22 +242,13 @@ ecmp_groups_add_route(struct ecmp_groups_node > *group, > > > > struct ecmp_route_list_node er = (struct ecmp_route_list_node) { > > .route = route, > > - .id = ++group->route_count, > > }; > > > > - if (group->route_count == 1) { > > - sset_clone(&group->selection_fields, > &route->ecmp_selection_fields); > > - } else { > > - sset_intersect(&group->selection_fields, > > - &route->ecmp_selection_fields); > > - } > > - > > vector_push(&group->route_list, &er); > > } > > > > -/* Removes a route from an ecmp group. If the ecmp group should persist > > - * afterwards you must call ecmp_groups_update_ids before any further > > - * insertions. */ > > +/* Removes a route from an ecmp group. The ids of the group and of its > > + * members are refreshed by group_ecmp_datapath_finalize(). */ > > static const struct parsed_route * > > ecmp_groups_remove_route(struct ecmp_groups_node *group, > > const struct parsed_route *pr) > > @@ -278,15 +267,140 @@ ecmp_groups_remove_route(struct ecmp_groups_node > *group, > > return NULL; > > } > > > > +/* Orders the members of an ecmp group by their content only, so that > the > > + * member ids do not depend on the order in which the routes were > added. */ > > +static int > > +ecmp_route_list_node_cmp(const void *a_, const void *b_) > > +{ > > + const struct parsed_route *a = > > + ((const struct ecmp_route_list_node *) a_)->route; > > + const struct parsed_route *b = > > + ((const struct ecmp_route_list_node *) b_)->route; > > + int cmp; > > + > > + if (a->source != b->source) { > > + return a->source < b->source ? -1 : 1; > > + } > > + if (a->is_discard_route != b->is_discard_route) { > > + return a->is_discard_route ? -1 : 1; > > + } > > + if (!a->nexthop || !b->nexthop) { > > + cmp = !!a->nexthop - !!b->nexthop; > > + } else { > > + cmp = memcmp(a->nexthop, b->nexthop, sizeof *a->nexthop); > > + } > > + if (cmp) { > > + return cmp; > > + } > > + const char *a_port = a->out_port ? a->out_port->key : NULL; > > + const char *b_port = b->out_port ? b->out_port->key : NULL; > > + if (!nullable_string_is_equal(a_port, b_port)) { > > + return !a_port ? -1 : !b_port ? 1 : strcmp(a_port, b_port); > > + } > > + if (!nullable_string_is_equal(a->lrp_addr_s, b->lrp_addr_s)) { > > + return !a->lrp_addr_s ? -1 > > + : !b->lrp_addr_s ? 1 > > + : strcmp(a->lrp_addr_s, b->lrp_addr_s); > > + } > > + if (a->ecmp_symmetric_reply != b->ecmp_symmetric_reply) { > > + return a->ecmp_symmetric_reply ? -1 : 1; > > + } > > + if (!a->source_hint || !b->source_hint) { > > + return !!a->source_hint - !!b->source_hint; > > + } > > + return uuid_compare_3way(&a->source_hint->uuid, > &b->source_hint->uuid); > > +} > > + > > +/* NAT and LB routes for the same prefix share a group, see > > + * route_sources_ecmp_compatible(). */ > > +static enum route_source > > +ecmp_group_source_class(enum route_source source) > > +{ > > + return source == ROUTE_SOURCE_LB ? ROUTE_SOURCE_NAT : source; > > +} > > + > > +/* Orders the ecmp groups of a datapath by their key only. The key is > unique > > + * within a datapath, see ecmp_groups_find(). */ > > +static int > > +ecmp_groups_node_cmp(const void *a_, const void *b_) > > +{ > > + const struct ecmp_groups_node *a = > > + *(const struct ecmp_groups_node *const *) a_; > > + const struct ecmp_groups_node *b = > > + *(const struct ecmp_groups_node *const *) b_; > > + > > + if (a->route_table_id != b->route_table_id) { > > + return a->route_table_id < b->route_table_id ? -1 : 1; > > + } > > + if (a->is_src_route != b->is_src_route) { > > + return a->is_src_route ? 1 : -1; > > + } > > + if (a->plen != b->plen) { > > + return a->plen < b->plen ? -1 : 1; > > + } > > + int cmp = memcmp(&a->prefix, &b->prefix, sizeof a->prefix); > > + if (cmp) { > > + return cmp; > > + } > > + /* Equal source classes mean the whole key is equal, i.e. 'a' and > 'b' are > > + * the same group, so this never returns 0 for two distinct groups. > */ > > + int a_class = ecmp_group_source_class(a->source); > > + int b_class = ecmp_group_source_class(b->source); > > + return a_class < b_class ? -1 : a_class > b_class; > > +} > > + > > +/* Recomputes everything in 'group' that is derived from its members, > so that > > + * the result only depends on the set of members. */ > > static void > > -ecmp_group_update_ids(struct ecmp_groups_node *group) > > +ecmp_group_finalize(struct ecmp_groups_node *group) > > { > > + vector_qsort(&group->route_list, ecmp_route_list_node_cmp); > > + > > struct ecmp_route_list_node *er; > > - size_t i = 0; > > + uint16_t id = 0; > > + group->has_discard_route = false; > > VECTOR_FOR_EACH_PTR (&group->route_list, er) { > > - er->id = i++; > > + er->id = ++id; > > + if (er->route->is_discard_route) { > > + group->has_discard_route = true; > > + } > > + if (id == 1) { > > + sset_destroy(&group->selection_fields); > > + sset_clone(&group->selection_fields, > > + &er->route->ecmp_selection_fields); > > + group->source = er->route->source; > > + } else { > > + sset_intersect(&group->selection_fields, > > + &er->route->ecmp_selection_fields); > > + } > > + } > > +} > > + > > +/* Assigns the group and member ids of all ecmp groups of 'gn'. Must be > > + * called after the ecmp groups of 'gn' changed, both on full recompute > and on > > + * incremental processing, so that both yield the same ids for the same > set > > + * of routes and the generated logical flows do not change on > recompute. */ > > +static void > > +group_ecmp_datapath_finalize(struct group_ecmp_datapath *gn) > > +{ > > + size_t n = hmap_count(&gn->ecmp_groups); > > + if (!n) { > > + return; > > + } > > + > > + struct ecmp_groups_node **groups = xmalloc(n * sizeof *groups); > > + struct ecmp_groups_node *eg; > > + size_t i = 0; > > + HMAP_FOR_EACH (eg, hmap_node, &gn->ecmp_groups) { > > + ecmp_group_finalize(eg); > > + groups[i++] = eg; > > + } > > + > > + qsort(groups, n, sizeof *groups, ecmp_groups_node_cmp); > > + for (i = 0; i < n; i++) { > > + groups[i]->id = i + 1; > > } > > - group->route_count = i; > > + free(groups); > > } > > > > static struct ecmp_groups_node * > > @@ -302,7 +416,6 @@ ecmp_groups_add(struct group_ecmp_datapath *gn, > > struct ecmp_groups_node *eg = xzalloc(sizeof *eg); > > hmap_insert(&gn->ecmp_groups, &eg->hmap_node, route->hash); > > > > - eg->id = hmap_count(&gn->ecmp_groups); > > eg->prefix = route->prefix; > > eg->plen = route->plen; > > eg->is_src_route = route->is_src_route; > > @@ -396,6 +509,10 @@ group_ecmp_route(struct group_ecmp_route_data *data, > > gn = group_ecmp_datapath_lookup_or_add(data, pr->od); > > add_route(gn, pr); > > } > > + > > + HMAP_FOR_EACH (gn, hmap_node, &data->datapaths) { > > + group_ecmp_datapath_finalize(gn); > > + } > > } > > > > enum engine_node_state > > @@ -472,9 +589,7 @@ handle_deleted_route(struct group_ecmp_route_data > *data, > > * unique route. Otherwise it stays an ecmp group with > just one > > * member. */ > > ecmp_groups_remove_route(eg, pr); > > - if (ecmp_group_has_symmetric_reply(eg)) { > > - ecmp_group_update_ids(eg); > > - } else { > > + if (!ecmp_group_has_symmetric_reply(eg)) { > > const struct ecmp_route_list_node *er = > > vector_get_ptr(&eg->route_list, 0); > > unique_routes_add(node, er->route); > > @@ -482,11 +597,8 @@ handle_deleted_route(struct group_ecmp_route_data > *data, > > ecmp_groups_node_free(eg); > > } > > } else { > > - /* We can just remove the member from the group. We need to > update > > - * the indices of all routes so that future insertions > directly > > - * have a new index. */ > > + /* We can just remove the member from the group. */ > > ecmp_groups_remove_route(eg, pr); > > - ecmp_group_update_ids(eg); > > } > > } > > > > @@ -537,6 +649,7 @@ group_ecmp_route_learned_route_change_handler(struct > engine_node *eng_node, > > hmapx_add(&data->trk_data.deleted_datapath_routes, node); > > hmap_remove(&data->datapaths, &node->hmap_node); > > } else { > > + group_ecmp_datapath_finalize(node); > > hmapx_add(&data->trk_data.crupdated_datapath_routes, node); > > } > > } > > @@ -589,6 +702,7 @@ group_ecmp_route_routes_change_handler(struct > engine_node *eng_node, > > hmapx_add(&data->trk_data.deleted_datapath_routes, node); > > hmap_remove(&data->datapaths, &node->hmap_node); > > } else { > > + group_ecmp_datapath_finalize(node); > > hmapx_add(&data->trk_data.crupdated_datapath_routes, node); > > } > > } > > @@ -645,6 +759,7 @@ > group_ecmp_route_dynamic_routes_change_handler(struct engine_node *eng_node, > > hmapx_add(&gdata->trk_data.deleted_datapath_routes, node); > > hmap_remove(&gdata->datapaths, &node->hmap_node); > > } else { > > + group_ecmp_datapath_finalize(node); > > hmapx_add(&gdata->trk_data.crupdated_datapath_routes, > node); > > } > > } > > diff --git a/northd/en-group-ecmp-route.h b/northd/en-group-ecmp-route.h > > index b40935be2..13f84a036 100644 > > --- a/northd/en-group-ecmp-route.h > > +++ b/northd/en-group-ecmp-route.h > > @@ -37,7 +37,6 @@ struct ecmp_groups_node { > > bool has_discard_route; > > enum route_source source; > > uint32_t route_table_id; > > - uint16_t route_count; > > struct vector route_list; /* Contains ecmp_route_list_node */ > > struct sset selection_fields; > > }; > > diff --git a/tests/ovn-northd.at b/tests/ovn-northd.at > > index 7a0a400c4..4c9fec29f 100644 > > --- a/tests/ovn-northd.at > > +++ b/tests/ovn-northd.at > > @@ -24092,6 +24092,72 @@ done > > OVN_CLEANUP_NORTHD > > AT_CLEANUP > > > > +OVN_FOR_EACH_NORTHD_NO_HV([ > > +AT_SETUP([Static routes - ECMP ids stable across recompute]) > > +AT_KEYWORDS([ecmp]) > > +ovn_start > > + > > +check ovn-nbctl lr-add lr0 > > +for i in 1 2 3 4; do > > + check ovn-nbctl lrp-add lr0 lr0-sw$i 00:00:00:00:0$i:01 10.0.$i.1/24 > > +done > > +check ovn-nbctl --wait=sb sync > > + > > +dnl Add the routes in "reverse" order, the ids must not depend on it. > > +for p in 192.168.30.0/24 192.168.20.0/24 192.168.10.0/24; do > > + for i in 3 2 1; do > > + check ovn-nbctl --wait=sb --ecmp lr-route-add lr0 $p 10.0.$i.10 > > + done > > +done > > +CHECK_NO_CHANGE_AFTER_RECOMPUTE > > + > > +AT_CHECK([ovn-sbctl dump-flows lr0 | grep -w lr_in_ip_routing | grep > select | ovn_strip_lflows], [0], [dnl > > + table=??(lr_in_ip_routing ), priority=1840 , match=(reg7 == 0 && > ip4.dst == 192.168.10.0/24), action=(ip.ttl--; flags.loopback = 1; > reg8[[0..15]] = 1; reg8[[16..31]] = select(1, 2, 3);) > > + table=??(lr_in_ip_routing ), priority=1840 , match=(reg7 == 0 && > ip4.dst == 192.168.20.0/24), action=(ip.ttl--; flags.loopback = 1; > reg8[[0..15]] = 2; reg8[[16..31]] = select(1, 2, 3);) > > + table=??(lr_in_ip_routing ), priority=1840 , match=(reg7 == 0 && > ip4.dst == 192.168.30.0/24), action=(ip.ttl--; flags.loopback = 1; > reg8[[0..15]] = 3; reg8[[16..31]] = select(1, 2, 3);) > > +]) > > +AT_CHECK([ovn-sbctl dump-flows lr0 | grep lr_in_ip_routing_ecmp | grep > -F "reg8[[0..15]] == 1 &&" | ovn_strip_lflows], [0], [dnl > > + table=??(lr_in_ip_routing_ecmp), priority=100 , match=(reg8[[0..15]] > == 1 && reg8[[16..31]] == 1), action=(reg0 = 10.0.1.10; reg5 = 10.0.1.1; > eth.src = 00:00:00:00:01:01; outport = "lr0-sw1"; reg9[[9]] = 1; next;) > > + table=??(lr_in_ip_routing_ecmp), priority=100 , match=(reg8[[0..15]] > == 1 && reg8[[16..31]] == 2), action=(reg0 = 10.0.2.10; reg5 = 10.0.2.1; > eth.src = 00:00:00:00:02:01; outport = "lr0-sw2"; reg9[[9]] = 1; next;) > > + table=??(lr_in_ip_routing_ecmp), priority=100 , match=(reg8[[0..15]] > == 1 && reg8[[16..31]] == 3), action=(reg0 = 10.0.3.10; reg5 = 10.0.3.1; > eth.src = 00:00:00:00:03:01; outport = "lr0-sw3"; reg9[[9]] = 1; next;) > > +]) > > + > > +dnl Remove a member from the middle of a group with more than 2 members. > > +check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats > > +check ovn-nbctl --wait=sb lr-route-del lr0 192.168.10.0/24 10.0.2.10 > > +check_engine_compute group_ecmp_route incremental > > +CHECK_NO_CHANGE_AFTER_RECOMPUTE > > + > > +dnl Remove a whole group and then add a new one, group ids must stay > unique. > > +check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats > > +check ovn-nbctl --wait=sb lr-route-del lr0 192.168.20.0/24 > > +check ovn-nbctl --wait=sb --ecmp lr-route-add lr0 192.168.40.0/24 > 10.0.1.10 > > +check ovn-nbctl --wait=sb --ecmp lr-route-add lr0 192.168.40.0/24 > 10.0.4.10 > > +check_engine_compute group_ecmp_route incremental > > +CHECK_NO_CHANGE_AFTER_RECOMPUTE > > +AT_CHECK([ovn-sbctl dump-flows lr0 | grep -w lr_in_ip_routing | grep > select | ovn_strip_lflows], [0], [dnl > > + table=??(lr_in_ip_routing ), priority=1840 , match=(reg7 == 0 && > ip4.dst == 192.168.10.0/24), action=(ip.ttl--; flags.loopback = 1; > reg8[[0..15]] = 1; reg8[[16..31]] = select(1, 2);) > > + table=??(lr_in_ip_routing ), priority=1840 , match=(reg7 == 0 && > ip4.dst == 192.168.30.0/24), action=(ip.ttl--; flags.loopback = 1; > reg8[[0..15]] = 2; reg8[[16..31]] = select(1, 2, 3);) > > + table=??(lr_in_ip_routing ), priority=1840 , match=(reg7 == 0 && > ip4.dst == 192.168.40.0/24), action=(ip.ttl--; flags.loopback = 1; > reg8[[0..15]] = 3; reg8[[16..31]] = select(1, 2);) > > +]) > > + > > +dnl Once no member is a discard route anymore the group must stop > dropping. > > +route=$(ovn-nbctl --bare --columns _uuid find > Logical_Router_Static_Route \ > > + ip_prefix="192.168.30.0/24" nexthop="10.0.3.10") > > +check ovn-nbctl --wait=sb set Logical_Router_Static_Route $route > nexthop=discard > > +AT_CHECK([ovn-sbctl dump-flows lr0 | grep lr_in_ip_routing_ecmp | grep > -c "drop;"], [0], [4 > > +]) > > +check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats > > +check ovn-nbctl --wait=sb set Logical_Router_Static_Route $route > nexthop=10.0.3.10 > > +check_engine_compute group_ecmp_route incremental > > +AT_CHECK([ovn-sbctl dump-flows lr0 | grep lr_in_ip_routing_ecmp | grep > -c "drop;"], [0], [1 > > +]) > > +CHECK_NO_CHANGE_AFTER_RECOMPUTE > > + > > +OVN_CLEANUP_NORTHD > > +AT_CLEANUP > > +]) > > + > > OVN_FOR_EACH_NORTHD_NO_HV([ > > AT_SETUP([Static routes - ECMP with discard]) > > ovn_start > > -- _‘Esta mensagem é direcionada apenas para os endereços constantes no cabeçalho inicial. Se você não está listado nos endereços constantes no cabeçalho, pedimos-lhe que desconsidere completamente o conteúdo dessa mensagem e cuja cópia, encaminhamento e/ou execução das ações citadas estão imediatamente anuladas e proibidas’._ * **‘Apesar do Magazine Luiza tomar todas as precauções razoáveis para assegurar que nenhum vírus esteja presente nesse e-mail, a empresa não poderá aceitar a responsabilidade por quaisquer perdas ou danos causados por esse e-mail ou por seus anexos’.* _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
