From 0c7f982a383ff4a8baede943ed3095b8813de977 Mon Sep 17 00:00:00 2001 From: Pat Ruddy Date: Wed, 19 May 2021 12:11:03 +0100 Subject: [PATCH] ospf6d: break early on route prefix mismatch The route linked list in ospf6d is ordered in prefix batches which are associated with a the route node denoting the prefix. So if you look up the prefix in the tree and start walking the list, if you find a prefix which differs from the one you are interested in then you have gone beyond the batch of routes for that prefix. In some cases the route database linked list is used on a per-prefix basis. The existing code simply does a continue when the prefix does not match and continues to walk. This works with small numbers of routes because the walk continues through unrelated prefix batches and never finds anything to operate on. However if we have many thousands of routes these walks become expensive and can cause the SPF thread (amongst others) to run very long, causing issues with adjacencies where the dead timer is short. Add a break to these prefix-based loops to exit early if we get a prefix mismatch to avoid continuing down the route list if we have overshot. Signed-off-by: Pat Ruddy --- ospf6d/ospf6_abr.c | 13 ++++++++++--- ospf6d/ospf6_asbr.c | 21 +++++++++++++++------ ospf6d/ospf6_intra.c | 20 ++++++++++++++++---- 3 files changed, 41 insertions(+), 13 deletions(-) diff --git a/ospf6d/ospf6_abr.c b/ospf6d/ospf6_abr.c index f289bf26b9..08d2ef0702 100644 --- a/ospf6d/ospf6_abr.c +++ b/ospf6d/ospf6_abr.c @@ -1194,9 +1194,16 @@ void ospf6_abr_examin_summary(struct ospf6_lsa *lsa, struct ospf6_area *oa) __func__, &prefix, listcount(old->paths)); } for (old_route = old; old_route; old_route = old_route->next) { - if (!ospf6_route_is_same(old_route, route) || - (old_route->type != route->type) || - (old_route->path.type != route->path.type)) + + /* The route linked-list is grouped in batches of prefix. + * If the new prefix is not the same as the one of interest + * then we have walked over the end of the batch and so we + * should break rather than continuing unnecessarily. + */ + if (!ospf6_route_is_same(old_route, route)) + break; + if ((old_route->type != route->type) + || (old_route->path.type != route->path.type)) continue; if ((ospf6_route_cmp(route, old_route) != 0)) { diff --git a/ospf6d/ospf6_asbr.c b/ospf6d/ospf6_asbr.c index 3e911a743a..2b1c344ba8 100644 --- a/ospf6d/ospf6_asbr.c +++ b/ospf6d/ospf6_asbr.c @@ -240,8 +240,14 @@ void ospf6_asbr_update_route_ecmp_path(struct ospf6_route *old, next_route = old_route->next; - if (!ospf6_route_is_same(old_route, route) - || (old_route->path.type != route->path.type)) + /* The route linked-list is grouped in batches of prefix. + * If the new prefix is not the same as the one of interest + * then we have walked over the end of the batch and so we + * should break rather than continuing unnecessarily. + */ + if (!ospf6_route_is_same(old_route, route)) + break; + if (old_route->path.type != route->path.type) continue; /* Current and New route has same origin, @@ -345,11 +351,14 @@ void ospf6_asbr_update_route_ecmp_path(struct ospf6_route *old, /* Add new route */ for (old_route = old; old_route; old_route = old_route->next) { - /* Current and New Route prefix or route type - * is not same skip this current node. + /* The route linked-list is grouped in batches of prefix. + * If the new prefix is not the same as the one of interest + * then we have walked over the end of the batch and so we + * should break rather than continuing unnecessarily. */ - if (!ospf6_route_is_same(old_route, route) - || (old_route->path.type != route->path.type)) + if (!ospf6_route_is_same(old_route, route)) + break; + if (old_route->path.type != route->path.type) continue; /* Old Route and New Route have Equal Cost, Merge NHs */ diff --git a/ospf6d/ospf6_intra.c b/ospf6d/ospf6_intra.c index c971c6180e..69ebc112a7 100644 --- a/ospf6d/ospf6_intra.c +++ b/ospf6d/ospf6_intra.c @@ -1490,8 +1490,14 @@ void ospf6_intra_prefix_route_ecmp_path(struct ospf6_area *oa, for (old_route = old; old_route; old_route = old_route->next) { bool route_updated = false; - if (!ospf6_route_is_same(old_route, route) || - (old_route->path.type != route->path.type)) + /* The route linked-list is grouped in batches of prefix. + * If the new prefix is not the same as the one of interest + * then we have walked over the end of the batch and so we + * should break rather than continuing unnecessarily. + */ + if (!ospf6_route_is_same(old_route, route)) + break; + if (old_route->path.type != route->path.type) continue; /* Current and New route has same origin, @@ -1589,8 +1595,14 @@ void ospf6_intra_prefix_route_ecmp_path(struct ospf6_area *oa, for (old_route = old; old_route; old_route = old_route->next) { - if (!ospf6_route_is_same(old_route, route) || - (old_route->path.type != route->path.type)) + /* The route linked-list is grouped in batches of prefix. + * If the new prefix is not the same as the one of interest + * then we have walked over the end of the batch and so we + * should break rather than continuing unnecessarily. + */ + if (!ospf6_route_is_same(old_route, route)) + break; + if (old_route->path.type != route->path.type) continue; /* Old Route and New Route have Equal Cost, Merge NHs */ -- 2.39.5