diff mbox series

[ovs-dev,v2,1/2] northd: Make ECMP group and members independent of processing order.

Message ID 20261005184706.302185-1-lucas.vdias@magalu.cloud
State Changes Requested
Headers show
Series northd: Make ECMP ids independent of processing order. | expand

Commit Message

Lucas Vargas Dias Oct. 5, 2026, 6:47 p.m. UTC
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 <lucas.vdias@magalu.cloud>
---
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.

 lib/ovn-util.h               |  12 +++
 northd/en-group-ecmp-route.c | 168 +++++++++++++++++++++++++++++------
 tests/ovn-northd.at          |  66 ++++++++++++++
 3 files changed, 220 insertions(+), 26 deletions(-)

Comments

Jacob Tanenbaum Oct. 6, 2026, 6 p.m. UTC | #1
This patch looks good; I just have a few minor comments

On Mon, Oct 5, 2026 at 2:47 PM Lucas Vargas Dias via dev <
ovs-dev@openvswitch.org> 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 <lucas.vdias@magalu.cloud>
> ---
> 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.
>
>  lib/ovn-util.h               |  12 +++
>  northd/en-group-ecmp-route.c | 168 +++++++++++++++++++++++++++++------
>  tests/ovn-northd.at          |  66 ++++++++++++++
>  3 files changed, 220 insertions(+), 26 deletions(-)
>
> diff --git a/lib/ovn-util.h b/lib/ovn-util.h
> index 01d21d282..e618283a9 100644
> --- a/lib/ovn-util.h
> +++ b/lib/ovn-util.h
> @@ -684,6 +684,18 @@ strip_leading_zero(const char *s)
>      return s + strspn(s, "0");
>  }
>
> +/* Like strcmp(), but also accepts NULL arguments.  Two NULLs compare
> equal
> + * and NULL sorts before any non-NULL string, so !nullable_strcmp(a, b) is
> + * equivalent to nullable_string_is_equal(a, b). */
> +static inline int
> +nullable_strcmp(const char *a, const char *b)
> +{
> +    if (!a || !b) {
> +        return !!a - !!b;
> +    }
> +    return strcmp(a, b);
> +}
> +
>  static inline bool
>  is_uuid_with_prefix(const char *uuid)
>  {
> diff --git a/northd/en-group-ecmp-route.c b/northd/en-group-ecmp-route.c
> index aca197318..127bf7ce0 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,14 @@ 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);
> +    group->route_count = vector_len(&group->route_list);
>

I might be wrong but I think that group->route_count is now only written to
and never read. If that is the case could we get rid of the two assignments
and drop the field?


>  }
>
> -/* 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 +268,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;
> +    }
> +    cmp = nullable_strcmp(a->out_port ? a->out_port->key : NULL,
> +                          b->out_port ? b->out_port->key : NULL);
> +    if (cmp) {
> +        return cmp;
> +    }
> +    cmp = nullable_strcmp(a->lrp_addr_s, b->lrp_addr_s);
> +    if (cmp) {
> +        return cmp;
> +    }
> +    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 int
> +ecmp_group_source_class(enum route_source source)
>

Nit: This function returns an enum, could the return type be changed?


> +{
> +    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);
> +        }
> +    }
> +    group->route_count = id;
> +}
> +
> +/* 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 +417,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 +510,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 +590,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 +598,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 +650,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 +703,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 +760,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/tests/ovn-northd.at b/tests/ovn-northd.at
> index f8c144918..0ca70ca10 100644
> --- a/tests/ovn-northd.at
> +++ b/tests/ovn-northd.at
> @@ -23852,6 +23852,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
> --
> 2.43.0
>
>
> --
>
>
>
>
> _'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
> dev@openvswitch.org
> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
>
>
Thanks,
Jacob Tanenbaum
Lucas Vargas Dias Oct. 6, 2026, 6:10 p.m. UTC | #2
Hi Jacob,
Thanks for your review.

Em ter., 6 de out. de 2026 às 15:00, Jacob Tanenbaum <jtanenba@redhat.com>
escreveu:

> This patch looks good; I just have a few minor comments
>
> On Mon, Oct 5, 2026 at 2:47 PM Lucas Vargas Dias via dev <
> ovs-dev@openvswitch.org> 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 <lucas.vdias@magalu.cloud>
>> ---
>> 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.
>>
>>  lib/ovn-util.h               |  12 +++
>>  northd/en-group-ecmp-route.c | 168 +++++++++++++++++++++++++++++------
>>  tests/ovn-northd.at          |  66 ++++++++++++++
>>  3 files changed, 220 insertions(+), 26 deletions(-)
>>
>> diff --git a/lib/ovn-util.h b/lib/ovn-util.h
>> index 01d21d282..e618283a9 100644
>> --- a/lib/ovn-util.h
>> +++ b/lib/ovn-util.h
>> @@ -684,6 +684,18 @@ strip_leading_zero(const char *s)
>>      return s + strspn(s, "0");
>>  }
>>
>> +/* Like strcmp(), but also accepts NULL arguments.  Two NULLs compare
>> equal
>> + * and NULL sorts before any non-NULL string, so !nullable_strcmp(a, b)
>> is
>> + * equivalent to nullable_string_is_equal(a, b). */
>> +static inline int
>> +nullable_strcmp(const char *a, const char *b)
>> +{
>> +    if (!a || !b) {
>> +        return !!a - !!b;
>> +    }
>> +    return strcmp(a, b);
>> +}
>> +
>>  static inline bool
>>  is_uuid_with_prefix(const char *uuid)
>>  {
>> diff --git a/northd/en-group-ecmp-route.c b/northd/en-group-ecmp-route.c
>> index aca197318..127bf7ce0 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,14 @@ 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);
>> +    group->route_count = vector_len(&group->route_list);
>>
>
> I might be wrong but I think that group->route_count is now only written
> to and never read. If that is the case could we get rid of the two
> assignments and drop the field?
>
>

You're right.


>  }
>>
>> -/* 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 +268,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;
>> +    }
>> +    cmp = nullable_strcmp(a->out_port ? a->out_port->key : NULL,
>> +                          b->out_port ? b->out_port->key : NULL);
>> +    if (cmp) {
>> +        return cmp;
>> +    }
>> +    cmp = nullable_strcmp(a->lrp_addr_s, b->lrp_addr_s);
>> +    if (cmp) {
>> +        return cmp;
>> +    }
>> +    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 int
>> +ecmp_group_source_class(enum route_source source)
>>
>
> Nit: This function returns an enum, could the return type be changed?
>
>
Yes, it could.

Regards,
Lucas


> +{
>> +    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);
>> +        }
>> +    }
>> +    group->route_count = id;
>> +}
>> +
>> +/* 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 +417,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 +510,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 +590,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 +598,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 +650,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 +703,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 +760,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/tests/ovn-northd.at b/tests/ovn-northd.at
>> index f8c144918..0ca70ca10 100644
>> --- a/tests/ovn-northd.at
>> +++ b/tests/ovn-northd.at
>> @@ -23852,6 +23852,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
>> --
>> 2.43.0
>>
>>
>> --
>>
>>
>>
>>
>> _'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
>> dev@openvswitch.org
>> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
>>
>>
> Thanks,
> Jacob Tanenbaum
>
diff mbox series

Patch

diff --git a/lib/ovn-util.h b/lib/ovn-util.h
index 01d21d282..e618283a9 100644
--- a/lib/ovn-util.h
+++ b/lib/ovn-util.h
@@ -684,6 +684,18 @@  strip_leading_zero(const char *s)
     return s + strspn(s, "0");
 }
 
+/* Like strcmp(), but also accepts NULL arguments.  Two NULLs compare equal
+ * and NULL sorts before any non-NULL string, so !nullable_strcmp(a, b) is
+ * equivalent to nullable_string_is_equal(a, b). */
+static inline int
+nullable_strcmp(const char *a, const char *b)
+{
+    if (!a || !b) {
+        return !!a - !!b;
+    }
+    return strcmp(a, b);
+}
+
 static inline bool
 is_uuid_with_prefix(const char *uuid)
 {
diff --git a/northd/en-group-ecmp-route.c b/northd/en-group-ecmp-route.c
index aca197318..127bf7ce0 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,14 @@  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);
+    group->route_count = vector_len(&group->route_list);
 }
 
-/* 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 +268,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;
+    }
+    cmp = nullable_strcmp(a->out_port ? a->out_port->key : NULL,
+                          b->out_port ? b->out_port->key : NULL);
+    if (cmp) {
+        return cmp;
+    }
+    cmp = nullable_strcmp(a->lrp_addr_s, b->lrp_addr_s);
+    if (cmp) {
+        return cmp;
+    }
+    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 int
+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);
+        }
+    }
+    group->route_count = id;
+}
+
+/* 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 +417,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 +510,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 +590,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 +598,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 +650,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 +703,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 +760,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/tests/ovn-northd.at b/tests/ovn-northd.at
index f8c144918..0ca70ca10 100644
--- a/tests/ovn-northd.at
+++ b/tests/ovn-northd.at
@@ -23852,6 +23852,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