On Fri, Jun 12, 2026 at 4:52 PM Dumitru Ceara via dev <
[email protected]> wrote:
> When recomputing routes we can just mark everything that we already had
> as "potentially stale", build the new set of parsed routes and then
> remove what actually is stale in one go for all router datapaths.
>
> The old code was achieving the same thing but in a very inefficient way.
> It used to:
> - walk all routers, for each router R:
> - walk all parsed routes (for all routers) and mark as potentially stale
> the ones that correspond to R
> - reparse R's routes (making the ones that are still relevant "not
> stale")
> - remove all actually stale routes for R
>
> But that means O(N x M) iterations, where N is the number of routers and
> M is the number of routes in the NB database.
>
> It can be simplified to:
> - walk all parsed routes (for all routers) and mark them all as
> potentially stale
> - for each router R:
> - reparse R's routes (making the ones that are still relevant "not
> stale")
> - remove all actually stale routes (for all routers in one traversal).
>
> With a complexity of O(M).
>
> Some test numbers from a scaled setup, 1.6K routers with a total number
> of 28K routes.
>
> Before the change:
> node: routes, recompute (forced) took 5841ms
> After the change:
> node: routes, recompute (forced) took 2922ms
>
> Fixes: 15c9c9f42ad8 ("northd: Add bfd, static_routes, route_policies and
> bfd_sync nodes to I-P engine.")
> Signed-off-by: Dumitru Ceara <[email protected]>
> ---
> northd/en-northd.c | 14 ++++++++++++++
> northd/northd.c | 16 ----------------
> 2 files changed, 14 insertions(+), 16 deletions(-)
>
> diff --git a/northd/en-northd.c b/northd/en-northd.c
> index c34818dba9..430de028c7 100644
> --- a/northd/en-northd.c
> +++ b/northd/en-northd.c
> @@ -366,6 +366,11 @@ en_routes_run(struct engine_node *node, void *data)
> routes_destroy(data);
> routes_init(data);
>
> + struct parsed_route *pr;
> + HMAP_FOR_EACH (pr, key_node, &routes_data->parsed_routes) {
> + pr->stale = true;
> + }
> +
> struct ovn_datapath *od;
> HMAP_FOR_EACH (od, key_node, &northd_data->lr_datapaths.datapaths) {
> for (int i = 0; i < od->nbr->n_ports; i++) {
> @@ -382,6 +387,15 @@ en_routes_run(struct engine_node *node, void *data)
> &routes_data->bfd_active_connections);
> }
>
> + HMAP_FOR_EACH_SAFE (pr, key_node, &routes_data->parsed_routes) {
> + if (!pr->stale) {
> + continue;
> + }
> +
> + hmap_remove(&routes_data->parsed_routes, &pr->key_node);
> + parsed_route_free(pr);
> + }
> +
> return EN_UPDATED;
> }
>
> diff --git a/northd/northd.c b/northd/northd.c
> index 0dbf174269..d96fb371ef 100644
> --- a/northd/northd.c
> +++ b/northd/northd.c
> @@ -12502,13 +12502,6 @@ build_parsed_routes(const struct ovn_datapath
> *od, const struct hmap *lr_ports,
> struct simap *route_tables,
> struct hmap *bfd_active_connections)
> {
> - struct parsed_route *pr;
> - HMAP_FOR_EACH (pr, key_node, routes) {
> - if (pr->od == od) {
> - pr->stale = true;
> - }
> - }
> -
> for (size_t i = 0; i < od->nbr->n_static_routes; i++) {
> parsed_routes_add_static(od, lr_ports, od->nbr->static_routes[i],
> bfd_connections, routes, route_tables,
> @@ -12519,15 +12512,6 @@ build_parsed_routes(const struct ovn_datapath
> *od, const struct hmap *lr_ports,
> HMAP_FOR_EACH (op, dp_node, &od->ports) {
> parsed_routes_add_connected(od, op, routes);
> }
> -
> - HMAP_FOR_EACH_SAFE (pr, key_node, routes) {
> - if (!pr->stale) {
> - continue;
> - }
> -
> - hmap_remove(routes, &pr->key_node);
> - parsed_route_free(pr);
> - }
> }
>
> static char *
> --
> 2.54.0
>
> _______________________________________________
> dev mailing list
> [email protected]
> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
>
>
Looks good to me, thanks.
Acked-by: Ales Musil <[email protected]>
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
