On 2/18/25 3:02 PM, Felix Huettner via dev wrote:
> This adds initial incremental support for the new group_ecmp_route
> engine. It only supports incremental processing for learned routes for
> now as other route types miss the incremental handling up the chain.
>
> Signed-off-by: Felix Huettner <[email protected]>
> ---
Hi Felix,
> northd/en-group-ecmp-route.c | 271 ++++++++++++++++++++++++++++++++---
> northd/en-group-ecmp-route.h | 19 +++
> northd/inc-proc-northd.c | 3 +-
> tests/ovn-northd.at | 4 +-
> 4 files changed, 271 insertions(+), 26 deletions(-)
>
> diff --git a/northd/en-group-ecmp-route.c b/northd/en-group-ecmp-route.c
> index e8a882004..d930905a5 100644
> --- a/northd/en-group-ecmp-route.c
> +++ b/northd/en-group-ecmp-route.c
> @@ -17,6 +17,7 @@
> #include <config.h>
> #include <stdbool.h>
>
> +#include "openvswitch/list.h"
This doesn't seem to be needed.
> #include "openvswitch/vlog.h"
> #include "stopwatch.h"
> #include "northd.h"
> @@ -28,19 +29,29 @@
>
> VLOG_DEFINE_THIS_MODULE(en_group_ecmp_route);
>
> +static void
> +ecmp_groups_node_free(struct ecmp_groups_node *eg)
> +{
> + if (!eg) {
> + return;
Nit: indentation.
> + }
> +
> + struct ecmp_route_list_node *er;
> + LIST_FOR_EACH_SAFE (er, list_node, &eg->route_list) {
> + ovs_list_remove(&er->list_node);
> + free(er);
> + }
> + sset_destroy(&eg->selection_fields);
> + free(eg);
> +}
> +
> static void
> ecmp_groups_destroy(struct hmap *ecmp_groups)
> {
> struct ecmp_groups_node *eg;
> HMAP_FOR_EACH_SAFE (eg, hmap_node, ecmp_groups) {
> - struct ecmp_route_list_node *er;
> - LIST_FOR_EACH_SAFE (er, list_node, &eg->route_list) {
> - ovs_list_remove(&er->list_node);
> - free(er);
> - }
> hmap_remove(ecmp_groups, &eg->hmap_node);
> - sset_destroy(&eg->selection_fields);
> - free(eg);
> + ecmp_groups_node_free(eg);
> }
> hmap_destroy(ecmp_groups);
> }
> @@ -56,21 +67,47 @@ unique_routes_destroy(struct hmap *unique_routes)
> hmap_destroy(unique_routes);
> }
>
> +static void
> +group_node_free(struct group_ecmp_route_node *n)
> +{
> + if (!n) {
> + return;
> + }
> +
> + unique_routes_destroy(&n->unique_routes);
> + ecmp_groups_destroy(&n->ecmp_groups);
> + free(n);
> +}
> +
> +static void
> +group_ecmp_route_clear_tracked(struct group_ecmp_route_data *data)
> +{
> + data->tracked = false;
> + hmapx_clear(&data->trk_data.crupdated_routes);
> +
> + struct hmapx_node *hmapx_node;
> + HMAPX_FOR_EACH (hmapx_node, &data->trk_data.deleted_routes) {
> + group_node_free(hmapx_node->data);
> + }
> + hmapx_clear(&data->trk_data.deleted_routes);
> +}
> +
> static void
> group_ecmp_route_clear(struct group_ecmp_route_data *data)
> {
> struct group_ecmp_route_node *n;
> HMAP_FOR_EACH_POP (n, hmap_node, &data->routes) {
> - unique_routes_destroy(&n->unique_routes);
> - ecmp_groups_destroy(&n->ecmp_groups);
> - free(n);
> + group_node_free(n);
> }
> + group_ecmp_route_clear_tracked(data);
> }
>
> static void
> group_ecmp_route_init(struct group_ecmp_route_data *data)
> {
> hmap_init(&data->routes);
> + hmapx_init(&data->trk_data.crupdated_routes);
> + hmapx_init(&data->trk_data.deleted_routes);
> }
>
> void *en_group_ecmp_route_init(struct engine_node *node OVS_UNUSED,
> @@ -86,11 +123,14 @@ void en_group_ecmp_route_cleanup(void *_data)
> struct group_ecmp_route_data *data = _data;
> group_ecmp_route_clear(data);
> hmap_destroy(&data->routes);
> + hmapx_destroy(&data->trk_data.crupdated_routes);
> + hmapx_destroy(&data->trk_data.deleted_routes);
> }
>
> void
> en_group_ecmp_route_clear_tracked_data(void *data OVS_UNUSED)
> {
> + group_ecmp_route_clear_tracked(data);
> }
>
> struct group_ecmp_route_node *
> @@ -106,18 +146,12 @@ group_ecmp_route_lookup(const struct
> group_ecmp_route_data *data,
> }
> return NULL;
> }
> -
> static struct group_ecmp_route_node *
> group_ecmp_route_add(struct group_ecmp_route_data *data,
> const struct ovn_datapath *od)
> {
> - struct group_ecmp_route_node *n = group_ecmp_route_lookup(data, od);
> - if (n) {
> - return n;
> - }
> -
> size_t hash = uuid_hash(&od->key);
> - n = xmalloc(sizeof *n);
> + struct group_ecmp_route_node *n = xmalloc(sizeof *n);
> n->od = od;
> hmap_init(&n->ecmp_groups);
> hmap_init(&n->unique_routes);
> @@ -125,6 +159,18 @@ group_ecmp_route_add(struct group_ecmp_route_data *data,
> return n;
> }
>
> +static struct group_ecmp_route_node *
> +group_ecmp_route_lookup_or_add(struct group_ecmp_route_data *data,
> + const struct ovn_datapath *od)
> +{
> + struct group_ecmp_route_node *n = group_ecmp_route_lookup(data, od);
> + if (n) {
> + return n;
> + }
> +
> + return group_ecmp_route_add(data, od);
> +}
> +
> static void
> unique_routes_add(struct group_ecmp_route_node *gn,
> const struct parsed_route *route)
> @@ -180,6 +226,38 @@ ecmp_groups_add_route(struct ecmp_groups_node *group,
> ovs_list_insert(&group->route_list, &er->list_node);
> }
>
> +/* 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. */
> +static const struct parsed_route *
> +ecmp_groups_remove_route(struct ecmp_groups_node *group,
> + const struct parsed_route *pr)
> +{
> + struct ecmp_route_list_node *er;
> + LIST_FOR_EACH (er, list_node, &group->route_list) {
> + if (er->route == pr) {
> + const struct parsed_route *found_route = er->route;
> + ovs_list_remove(&er->list_node);
> + free(er);
> + return found_route;
> + }
> + }
> +
> + return NULL;
> +}
> +
> +static void
> +ecmp_group_update_ids(struct ecmp_groups_node *group)
> +{
> + struct ecmp_route_list_node *er;
> + size_t i = 0;
> + LIST_FOR_EACH (er, list_node, &group->route_list) {
> + er->id = i;
> + i++;
> + }
> + group->route_count = i;
> +}
> +
> static struct ecmp_groups_node *
> ecmp_groups_add(struct group_ecmp_route_node *gn,
> const struct parsed_route *route)
> @@ -223,11 +301,21 @@ ecmp_groups_find(struct group_ecmp_route_node *gn,
> return NULL;
> }
>
> -static void
> -add_route(struct group_ecmp_route_data *data, const struct parsed_route *pr)
> +static bool
> +ecmp_group_any_symmetric_reply(struct ecmp_groups_node *eg)
We never call this for any groups that have more than one entry. But
OK. I'd renable it to ecmp_group_has_symmetric_reply() though.
> {
> - struct group_ecmp_route_node *gn = group_ecmp_route_add(data, pr->od);
> + struct ecmp_route_list_node *er;
> + LIST_FOR_EACH (er, list_node, &eg->route_list) {
> + if (er->route->ecmp_symmetric_reply) {
> + return true;
> + }
> + }
> + return false;
> +}
>
> +static void
> +add_route(struct group_ecmp_route_node *gn, const struct parsed_route *pr)
> +{
> if (pr->source == ROUTE_SOURCE_CONNECTED) {
> unique_routes_add(gn, pr);
> return;
> @@ -260,17 +348,21 @@ group_ecmp_route(struct group_ecmp_route_data *data,
> const struct routes_data *routes_data,
> const struct learned_route_sync_data *learned_route_data)
> {
> + struct group_ecmp_route_node *gn;
> const struct parsed_route *pr;
> HMAP_FOR_EACH (pr, key_node, &routes_data->parsed_routes) {
> - add_route(data, pr);
> + gn = group_ecmp_route_lookup_or_add(data, pr->od);
> + add_route(gn, pr);
> }
>
> HMAP_FOR_EACH (pr, key_node, &learned_route_data->parsed_routes) {
> - add_route(data, pr);
> + gn = group_ecmp_route_lookup_or_add(data, pr->od);
> + add_route(gn, pr);
> }
> }
>
> -void en_group_ecmp_route_run(struct engine_node *node, void *_data)
> +void
> +en_group_ecmp_route_run(struct engine_node *node, void *_data)
> {
> struct group_ecmp_route_data *data = _data;
> group_ecmp_route_clear(data);
> @@ -287,3 +379,136 @@ void en_group_ecmp_route_run(struct engine_node *node,
> void *_data)
> stopwatch_stop(GROUP_ECMP_ROUTE_RUN_STOPWATCH_NAME, time_msec());
> engine_set_node_state(node, EN_UPDATED);
> }
> +
> +static void
> +handle_added_route(struct group_ecmp_route_data *data,
> + const struct parsed_route *pr,
> + struct hmapx *updated_routes)
> +{
> + struct group_ecmp_route_node *node = group_ecmp_route_lookup(data,
> pr->od);
> +
> + if (!node) {
> + node = group_ecmp_route_add(data, pr->od);
> + }
> +
> + add_route(node, pr);
> +
Nit: I'd remove this empty line, potentially I'd also swap these two
statements but that's not a must.
> + hmapx_add(updated_routes, node);
> +}
> +
> +static bool
> +handle_deleted_route(struct group_ecmp_route_data *data,
> + const struct parsed_route *pr,
> + struct hmapx *updated_routes)
> +{
> + struct group_ecmp_route_node *node = group_ecmp_route_lookup(data,
> pr->od);
> + if (!node) {
> + /* This should not happen since we should know the datapath. */
> + return false;
> + }
> +
> + const struct parsed_route *existing = unique_routes_remove(node, pr);
> + if (!existing) {
> + /* The route must be part of an ecmp group. */
> + if (pr->source == ROUTE_SOURCE_CONNECTED) {
> + /* Connected routes are never part of an ecmp group.
> + * We should recompute. */
> + return false;
> + }
> +
> + struct ecmp_groups_node *eg = ecmp_groups_find(node, pr);
> + if (!eg) {
> + /* We neither found the route as unique nor as ecmp group.
> + * We should recompute. */
> + return false;
> + }
> +
> + size_t ecmp_members = ovs_list_size(&eg->route_list);
> + if (ecmp_members == 1) {
> + /* The route is the only ecmp member, we remove the whole group.
> */
> + hmap_remove(&node->ecmp_groups, &eg->hmap_node);
> + ecmp_groups_node_free(eg);
> + } else if (ecmp_members == 2) {
> + /* There is only one other member. If it does not have
> + * ecmp_symmetric_reply configured, we convert it to a
> + * unique route. Otherwise it stays an ecmp group with just one
> + * member. */
> + ecmp_groups_remove_route(eg, pr);
> + if (ecmp_group_any_symmetric_reply(eg)) {
> + ecmp_group_update_ids(eg);
> + } else {
> + struct ecmp_route_list_node *er = CONTAINER_OF(
> + ovs_list_front(&eg->route_list),
> + struct ecmp_route_list_node, list_node);
> + unique_routes_add(node, er->route);
> + hmap_remove(&node->ecmp_groups, &eg->hmap_node);
> + 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. */
> + ecmp_groups_remove_route(eg, pr);
> + ecmp_group_update_ids(eg);
> + }
> +
> + }
> +
> + hmapx_add(updated_routes, node);
> + return true;
> +}
> +
> +bool
> +group_ecmp_route_learned_route_change_handler(struct engine_node *eng_node,
> + void *_data)
> +{
> + struct group_ecmp_route_data *data = _data;
> + struct learned_route_sync_data *learned_route_data
> + = engine_get_input_data("learned_route_sync", eng_node);
> +
> + if (learned_route_data->trk_data.type == LEARNED_ROUTES_TRACKED_NONE) {
> + data->tracked = false;
> + return false;
> + }
> +
> + data->tracked = true;
> +
> + struct hmapx updated_routes = HMAPX_INITIALIZER(&updated_routes);
> +
> + const struct hmapx_node *hmapx_node;
> + const struct parsed_route *pr;
> + HMAPX_FOR_EACH (hmapx_node,
> + &learned_route_data->trk_data.trk_created_parsed_route) {
> + pr = hmapx_node->data;
> + handle_added_route(data, pr, &updated_routes);
> + }
> +
> + HMAPX_FOR_EACH (hmapx_node,
> + &learned_route_data->trk_data.trk_deleted_parsed_route) {
> + pr = hmapx_node->data;
> + if (!handle_deleted_route(data, pr, &updated_routes)) {
> + return false;
> + }
> + }
Is there a reason to not handle deletions first? It might be safer to
do so, just in case.
> +
> + /* Now we need to group the route_nodes based on if there are any routes
> + * left. */
> + HMAPX_FOR_EACH (hmapx_node, &updated_routes) {
> + struct group_ecmp_route_node *node = hmapx_node->data;
> + if (hmap_is_empty(&node->unique_routes) &&
> + hmap_is_empty(&node->ecmp_groups)) {
> + hmapx_add(&data->trk_data.deleted_routes, node);
> + hmap_remove(&data->routes, &node->hmap_node);
> + } else {
> + hmapx_add(&data->trk_data.crupdated_routes, node);
> + }
> + }
> +
> + hmapx_destroy(&updated_routes);
> +
> + if (!(hmapx_is_empty(&data->trk_data.crupdated_routes) &&
> + hmapx_is_empty(&data->trk_data.deleted_routes))) {
> + engine_set_node_state(eng_node, EN_UPDATED);
> + }
> + return true;
> +}
> diff --git a/northd/en-group-ecmp-route.h b/northd/en-group-ecmp-route.h
> index c84bb11ee..0da8fa88c 100644
> --- a/northd/en-group-ecmp-route.h
> +++ b/northd/en-group-ecmp-route.h
> @@ -61,10 +61,26 @@ struct group_ecmp_route_node {
> struct hmap unique_routes;
> };
>
> +struct group_ecmp_route_tracked_data {
> + /* Contains references to group_ecmp_route_node. Each of the referenced
> + * datapath contains any route. */
Maybe "Each of the referenced datapaths contains at least one route." is
more clear?
> + struct hmapx crupdated_routes;
Same as on the previous patch, this actually stores pointers to per
datapath route maps. The 'crupdated' name is confusing IMO. Maybe
'crupdated_datapath_routes'?
> +
> + /* Contains references to group_ecmp_route_node. Each of the referenced
> + * datapath previously had some routes. The datapath now no longer
> + * contains any route.*/
> + struct hmapx deleted_routes;
Same comment about the name here. Maybe 'deleted_datapath_routes'?
> +};
> +
> struct group_ecmp_route_data {
> /* Contains struct group_ecmp_route_node.
> * Each entry represents the routes of a single datapath. */
> struct hmap routes;
> +
> + /* tracked is set to true if there is information available for
> incremental
Nit: because we're referring to an actual field name this should be:
/* 'tracked' is set to ..
> + * processing. If true then trk_data is valid. */
> + bool tracked;
> + struct group_ecmp_route_tracked_data trk_data;
> };
>
> void *en_group_ecmp_route_init(struct engine_node *, struct engine_arg *);
> @@ -72,6 +88,9 @@ void en_group_ecmp_route_cleanup(void *data);
> void en_group_ecmp_route_clear_tracked_data(void *data);
> void en_group_ecmp_route_run(struct engine_node *, void *data);
>
> +bool group_ecmp_route_learned_route_change_handler(struct engine_node *,
> + void *data);
> +
> struct group_ecmp_route_node * group_ecmp_route_lookup(
> const struct group_ecmp_route_data *data,
> const struct ovn_datapath *od);
> diff --git a/northd/inc-proc-northd.c b/northd/inc-proc-northd.c
> index 712aebaa1..147f54da0 100644
> --- a/northd/inc-proc-northd.c
> +++ b/northd/inc-proc-northd.c
> @@ -315,7 +315,8 @@ void inc_proc_northd_init(struct ovsdb_idl_loop *nb,
> learned_route_sync_northd_change_handler);
>
> engine_add_input(&en_group_ecmp_route, &en_routes, NULL);
> - engine_add_input(&en_group_ecmp_route, &en_learned_route_sync, NULL);
> + engine_add_input(&en_group_ecmp_route, &en_learned_route_sync,
> + group_ecmp_route_learned_route_change_handler);
>
> engine_add_input(&en_sync_meters, &en_nb_acl, NULL);
> engine_add_input(&en_sync_meters, &en_nb_meter, NULL);
> diff --git a/tests/ovn-northd.at b/tests/ovn-northd.at
> index 8d77b3534..b70deade3 100644
> --- a/tests/ovn-northd.at
> +++ b/tests/ovn-northd.at
> @@ -15642,7 +15642,7 @@ check_engine_compute northd unchanged
> check_engine_compute routes unchanged
> check_engine_compute advertised_route_sync unchanged
> check_engine_compute learned_route_sync incremental
> -check_engine_compute group_ecmp_route recompute
> +check_engine_compute group_ecmp_route incremental
> check_engine_compute lflow recompute
> CHECK_NO_CHANGE_AFTER_RECOMPUTE
>
> @@ -15653,7 +15653,7 @@ check_engine_compute northd unchanged
> check_engine_compute routes unchanged
> check_engine_compute advertised_route_sync unchanged
> check_engine_compute learned_route_sync incremental
> -check_engine_compute group_ecmp_route recompute
> +check_engine_compute group_ecmp_route incremental
> check_engine_compute lflow recompute
> CHECK_NO_CHANGE_AFTER_RECOMPUTE
>
Regards,
Dumitru
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
