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
