On 6/12/26 5:48 PM, Ales Musil wrote: > 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]> >
Thanks for the review! But, on a closer look, it's even worse than I originally thought, the "stale" marking is useless because we cleared all of them in the beginning of the function, in routes_destroy(). The original code would never find any stale routes anyway. I'll post a v2 removing the two useless loops all toghether. Regards, Dumitru _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
