On Thu, Feb 20, 2025 at 02:46:53PM +0100, Dumitru Ceara wrote:
> 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,
Hi Dumitru,
thanks for the review.
>
> > 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.
This might point to also an issue in the incremental logic of the
en_learned_route_sync.
I am thinking now of two scenarios that we need to handle in a single
incremental run.
In Scenario 1 we have no preexisting learned route. First a learned_route is
added and is then removed again.
In Scenario 2 we have a preexisting learned route. First this route is
removed. Then a new one is added with basically the same value.
The final result of Scenario 1 should be that we do not learn this
route, the final result of Scenario 2 contains the route.
We could handle Scenario 1 (on the en_learned_route_sync side) by
checking if a route is both created and deleted. If yes it could be
removed from both hmapx. That means that this engine node never needs to
care about that issue.
Alternatively the IDL already handles this and does not even present
this Learned_Route. I just don't know if that is the case.
I think Scenario 2 should already be fine, but it is probably more
efficient if we first handle the deletions.
I would be interested in your opinion.
>
> > +
> > + /* 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?
A lot better.
>
> > + 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'?
I'll change both
>
> > +};
> > +
> > 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
> >
I'll address all the things in the next version.
I am really interested in your view on the incremental add-delete thing
above.
Thanks a lot,
Felix
>
> Regards,
> Dumitru
>
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
