Hi Rosemarie,
Thanks for your review.
Em qua., 14 de out. de 2026 às 09:15, Rosemarie O'Riorden
<[email protected] <mailto:[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.
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 <http://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 <http://ovn-northd.at> b/tests/
ovn-northd.at <http://ovn-northd.at>
> index 7a0a400c4..4c9fec29f 100644
> --- a/tests/ovn-northd.at <http://ovn-northd.at>
> +++ b/tests/ovn-northd.at <http://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 <http://192.168.30.0/24>
192.168.20.0/24 <http://192.168.20.0/24> 192.168.10.0/24
<http://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 <http://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 <http://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 <http://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
<http://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
<http://192.168.20.0/24>
> +check ovn-nbctl --wait=sb --ecmp lr-route-add lr0
192.168.40.0/24 <http://192.168.40.0/24> 10.0.1.10
> +check ovn-nbctl --wait=sb --ecmp lr-route-add lr0
192.168.40.0/24 <http://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 <http://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 <http://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 <http://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 <http://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’./
