| Message ID | 20260612145144.471883-1-dceara@redhat.com |
|---|---|
| State | Changes Requested |
| Headers | show |
| Series | [ovs-dev] northd: Avoid useless iterations when recomputing routes. | expand |
| Context | Check | Description |
|---|---|---|
| ovsrobot/apply-robot | success | apply and check: success |
| ovsrobot/github-robot-_Build_and_Test | success | github build: passed |
| ovsrobot/github-robot-_ovn-kubernetes | success | github build: passed |
On Fri, Jun 12, 2026 at 4:52 PM Dumitru Ceara via dev < ovs-dev@openvswitch.org> 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 <dceara@redhat.com> > --- > 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 > dev@openvswitch.org > https://mail.openvswitch.org/mailman/listinfo/ovs-dev > > Looks good to me, thanks. Acked-by: Ales Musil <amusil@redhat.com>
On 6/12/26 5:48 PM, Ales Musil wrote: > On Fri, Jun 12, 2026 at 4:52 PM Dumitru Ceara via dev < > ovs-dev@openvswitch.org> 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 <dceara@redhat.com> >> --- >> 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 >> dev@openvswitch.org >> https://mail.openvswitch.org/mailman/listinfo/ovs-dev >> >> > Looks good to me, thanks. > > Acked-by: Ales Musil <amusil@redhat.com> > 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
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 *
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 <dceara@redhat.com> --- northd/en-northd.c | 14 ++++++++++++++ northd/northd.c | 16 ---------------- 2 files changed, 14 insertions(+), 16 deletions(-)