platform: reduce number of route indexes

Maintaining an index is expensive.Not so much in term of runtime, but
in term of memory.

Drop some indexes, and require the caller to use a more broad index (and
filter out unwanted elements).

Dropped:

 - can no longer lookup visible default-routes by ifindex.
   If you care about default-routes, lookup all and search for the
   desired ifindex. The overall number of default-routes is expected
   to be small.
   We drop NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_WITH_DEFAULT
   entirely.

 - no longer have a separate index for non-default routes. We
   expect that the most routes are non-default routes. So, don't
   have an index without default-routes, instead let the caller
   just lookup all routes, and reject default-routes themself.
   We keep NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_DEFAULT, but it
   now no longer tracks non-default routes.

This drops 1 out of 6 route indexes, and modifes another one, so
that we expect that there are almost no entires tracked by it.

9 files changed, 47 insertions, 77 deletions

diff --git a/src/devices/nm-device.c b/src/devices/nm-device.c
index db59171b02..4bf34cd5b2 100644
--- a/src/devices/nm-device.c
+++ b/src/devices/nm-device.c
@@ -5417,13 +5417,14 @@ _device_get_default_route_from_platform (NMDevice *self, int addr_family, NMPlat
 	                                                  addr_family == AF_INET
 	                                                    ? NMP_OBJECT_TYPE_IP4_ROUTE
 	                                                    : NMP_OBJECT_TYPE_IP6_ROUTE,
-	                                                  ifindex,
-	                                                  TRUE,
-	                                                  FALSE);
+	                                                  0,
+	                                                  TRUE);
 	nmp_cache_iter_for_each (&iter, pl_head_entry, &plobj) {
 		guint32 m;
 		const NMPlatformIPRoute *r = NMP_OBJECT_CAST_IP_ROUTE (plobj);
 
+		if (r->ifindex != ifindex)
+			continue;
 		if (r->rt_source == NM_IP_CONFIG_SOURCE_RTPROT_KERNEL)
 			continue;
 
diff --git a/src/nm-default-route-manager.c b/src/nm-default-route-manager.c
index fb61ef751c..f0dc75cfd1 100644
--- a/src/nm-default-route-manager.c
+++ b/src/nm-default-route-manager.c
@@ -336,7 +336,6 @@ _platform_route_sync_flush (const VTableIP *vtable, NMDefaultRouteManager *self,
 	                                                 vtable->vt->obj_type,
 	                                                 0,
 	                                                 TRUE,
-	                                                 FALSE,
 	                                                 nm_platform_lookup_predicate_routes_skip_rtprot_kernel,
 	                                                 NULL);
 	if (!routes)
@@ -520,7 +519,6 @@ _resync_all (const VTableIP *vtable, NMDefaultRouteManager *self, const Entry *c
 	                                                 vtable->vt->obj_type,
 	                                                 0,
 	                                                 TRUE,
-	                                                 FALSE,
 	                                                 nm_platform_lookup_predicate_routes_skip_rtprot_kernel,
 	                                                 NULL);
 
diff --git a/src/nm-ip4-config.c b/src/nm-ip4-config.c
index d5df277b14..1ec3115d4e 100644
--- a/src/nm-ip4-config.c
+++ b/src/nm-ip4-config.c
@@ -419,8 +419,7 @@ nm_ip4_config_capture (NMDedupMultiIndex *multi_idx, NMPlatform *platform, int i
 	pl_head_entry = nm_platform_lookup_route_visible (platform,
 	                                                  NMP_OBJECT_TYPE_IP4_ROUTE,
 	                                                  ifindex,
-	                                                  TRUE,
-	                                                  TRUE);
+	                                                  FALSE);
 
 	/* Extract gateway from default route */
 	old_gateway = priv->gateway;
diff --git a/src/nm-ip6-config.c b/src/nm-ip6-config.c
index 0dc7adcad2..dde62e9501 100644
--- a/src/nm-ip6-config.c
+++ b/src/nm-ip6-config.c
@@ -377,8 +377,7 @@ nm_ip6_config_capture (NMDedupMultiIndex *multi_idx, NMPlatform *platform, int i
 	pl_head_entry = nm_platform_lookup_route_visible (platform,
 	                                                  NMP_OBJECT_TYPE_IP6_ROUTE,
 	                                                  ifindex,
-	                                                  TRUE,
-	                                                  TRUE);
+	                                                  FALSE);
 
 	/* Extract gateway from default route */
 	old_gateway = priv->gateway;
diff --git a/src/nm-route-manager.c b/src/nm-route-manager.c
index 574493d990..8372d65234 100644
--- a/src/nm-route-manager.c
+++ b/src/nm-route-manager.c
@@ -314,7 +314,7 @@ _route_index_create_from_platform (const VTableIP *vtable,
                                    GPtrArray **out_storage)
 {
 	RouteIndex *index;
-	guint i, len;
+	guint i, j, len;
 	GPtrArray *storage;
 
 	nm_assert (out_storage && !*out_storage);
@@ -323,7 +323,6 @@ _route_index_create_from_platform (const VTableIP *vtable,
 	                                                  vtable->vt->obj_type,
 	                                                  ifindex,
 	                                                  FALSE,
-	                                                  TRUE,
 	                                                  NULL,
 	                                                  NULL);
 	if (!storage)
@@ -332,17 +331,23 @@ _route_index_create_from_platform (const VTableIP *vtable,
 	len = storage->len;
 	index = g_malloc (sizeof (RouteIndex) + len * sizeof (NMPlatformIPXRoute *));
 
-	index->len = len;
+	j = 0;
 	for (i = 0; i < len; i++) {
+		const NMPlatformIPXRoute *ipx_route = NMP_OBJECT_CAST_IPX_ROUTE ((NMPObject *) storage->pdata[i]);
+
+		if (NM_PLATFORM_IP_ROUTE_IS_DEFAULT (ipx_route))
+			continue;
+
 		/* we cast away the const-ness of the NMPObjects. The caller must
 		 * ensure not to modify the object via index->entries. */
-		index->entries[i] = NMP_OBJECT_CAST_IPX_ROUTE ((NMPObject *) storage->pdata[i]);
+		index->entries[j++] = (NMPlatformIPXRoute *) ipx_route;
 	}
-	index->entries[i] = NULL;
+	index->entries[j] = NULL;
+	index->len = j;
 
 	/* this is a stable sort, which is very important at this point. */
 	g_qsort_with_data (index->entries,
-	                   len,
+	                   index->len,
 	                   sizeof (NMPlatformIPXRoute *),
 	                   (GCompareDataFunc) _route_index_create_sort,
 	                   (gpointer) vtable);
diff --git a/src/platform/nmp-object.c b/src/platform/nmp-object.c
index dd3445e2f8..ac5ee20e1d 100644
--- a/src/platform/nmp-object.c
+++ b/src/platform/nmp-object.c
@@ -194,17 +194,17 @@ _idx_obj_part (const DedupMultiIdxType *idx_type,
 	case NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_DEFAULT:
 		if (   !NM_IN_SET (NMP_OBJECT_GET_TYPE (obj_a), NMP_OBJECT_TYPE_IP4_ROUTE,
 		                                                NMP_OBJECT_TYPE_IP6_ROUTE)
+		    || !NM_PLATFORM_IP_ROUTE_IS_DEFAULT (&obj_a->ip_route)
 		    || !nmp_object_is_visible (obj_a))
 			return 0;
 		if (obj_b) {
 			return    NMP_OBJECT_GET_TYPE (obj_a) == NMP_OBJECT_GET_TYPE (obj_b)
-			       && NM_PLATFORM_IP_ROUTE_IS_DEFAULT (&obj_a->ip_route) == NM_PLATFORM_IP_ROUTE_IS_DEFAULT (&obj_b->ip_route)
+			       && NM_PLATFORM_IP_ROUTE_IS_DEFAULT (&obj_b->ip_route)
 			       && nmp_object_is_visible (obj_b);
 		}
 		if (request_hash) {
 			h = (guint) idx_type->cache_id_type;
 			h = NM_HASH_COMBINE (h, NMP_OBJECT_GET_TYPE (obj_a));
-			h = NM_HASH_COMBINE (h, NM_PLATFORM_IP_ROUTE_IS_DEFAULT (&obj_a->ip_route));
 			return _HASH_NON_ZERO (h);
 		}
 		return 1;
@@ -230,26 +230,6 @@ _idx_obj_part (const DedupMultiIdxType *idx_type,
 		}
 		return 1;
 
-	case NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_WITH_DEFAULT:
-		if (   !NM_IN_SET (NMP_OBJECT_GET_TYPE (obj_a), NMP_OBJECT_TYPE_IP4_ROUTE, NMP_OBJECT_TYPE_IP6_ROUTE)
-		    || obj_a->object.ifindex <= 0
-		    || !nmp_object_is_visible (obj_a))
-			return 0;
-		if (obj_b) {
-			return    NMP_OBJECT_GET_TYPE (obj_a) == NMP_OBJECT_GET_TYPE (obj_b)
-			       && obj_a->object.ifindex == obj_b->object.ifindex
-			       && NM_PLATFORM_IP_ROUTE_IS_DEFAULT (&obj_a->ip_route) == NM_PLATFORM_IP_ROUTE_IS_DEFAULT (&obj_b->ip_route)
-			       && nmp_object_is_visible (obj_b);
-		}
-		if (request_hash) {
-			h = (guint) idx_type->cache_id_type;
-			h = NM_HASH_COMBINE (h, NMP_OBJECT_GET_TYPE (obj_a));
-			h = NM_HASH_COMBINE (h, NM_PLATFORM_IP_ROUTE_IS_DEFAULT (&obj_a->ip_route));
-			h = NM_HASH_COMBINE (h, obj_a->object.ifindex);
-			return _HASH_NON_ZERO (h);
-		}
-		return 1;
-
 	case NMP_CACHE_ID_TYPE_ROUTES_BY_DESTINATION:
 		obj_type = NMP_OBJECT_GET_TYPE (obj_a);
 		if (   !NM_IN_SET (obj_type, NMP_OBJECT_TYPE_IP4_ROUTE,
@@ -1300,7 +1280,6 @@ static const guint8 _supported_cache_ids_ipx_route[] = {
 	NMP_CACHE_ID_TYPE_OBJECT_TYPE_VISIBLE_ONLY,
 	NMP_CACHE_ID_TYPE_ADDRROUTE_VISIBLE_BY_IFINDEX,
 	NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_DEFAULT,
-	NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_WITH_DEFAULT,
 	NMP_CACHE_ID_TYPE_ROUTES_BY_DESTINATION,
 	0,
 };
@@ -1654,8 +1633,7 @@ const NMPLookup *
 nmp_lookup_init_route_visible (NMPLookup *lookup,
                                NMPObjectType obj_type,
                                int ifindex,
-                               gboolean with_default,
-                               gboolean with_non_default)
+                               gboolean only_default)
 {
 	NMPObject *o;
 
@@ -1663,24 +1641,22 @@ nmp_lookup_init_route_visible (NMPLookup *lookup,
 	nm_assert (NM_IN_SET (obj_type, NMP_OBJECT_TYPE_IP4_ROUTE,
 	                                NMP_OBJECT_TYPE_IP6_ROUTE));
 
-	if (with_default) {
-		if (with_non_default) {
-			return nmp_lookup_init_addrroute (lookup,
-			                                  obj_type,
-			                                  ifindex,
-			                                  TRUE);
-		}
-	} else if (!with_non_default)
+	if (!only_default) {
+		return nmp_lookup_init_addrroute (lookup,
+		                                  obj_type,
+		                                  ifindex,
+		                                  TRUE);
+	}
+
+	if (ifindex > 0) {
+		/* there is no index to lookup a default-route by ifindex.
+		 * You have to lookup all default-routes, and filter yourself */
 		g_return_val_if_reached (NULL);
-	o = _nmp_object_stackinit_from_type (&lookup->selector_obj, obj_type);
-	o->ip_route.plen = with_default ? 0 : 1;
-	if (ifindex <= 0) {
-		o->object.ifindex = 1;
-		lookup->cache_id_type = NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_DEFAULT;
-	} else {
-		o->object.ifindex = ifindex;
-		lookup->cache_id_type = NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_WITH_DEFAULT;
 	}
+
+	o = _nmp_object_stackinit_from_type (&lookup->selector_obj, obj_type);
+	o->object.ifindex = 1;
+	lookup->cache_id_type = NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_DEFAULT;
 	return _L (lookup);
 }
 
diff --git a/src/platform/nmp-object.h b/src/platform/nmp-object.h
index 5574e0b3b6..1cff049555 100644
--- a/src/platform/nmp-object.h
+++ b/src/platform/nmp-object.h
@@ -75,17 +75,14 @@ typedef enum { /*< skip >*/
 	/* all the visible objects of a certain type */
 	NMP_CACHE_ID_TYPE_OBJECT_TYPE_VISIBLE_ONLY,
 
-	/* indeces for the visible routes, ignoring ifindex.
-	 * The index separates default routes from non-default routes. */
+	/* indeces for the visible default-routes, ignoring ifindex.
+	 * This index only contains two partitions: all visible default-routes,
+	 * separate for IPv4 and IPv6. */
 	NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_DEFAULT,
 
 	/* all the visible addresses/routes (by object-type) for an ifindex. */
 	NMP_CACHE_ID_TYPE_ADDRROUTE_VISIBLE_BY_IFINDEX,
 
-	/* indeces for the visible routes, per ifindex.
-	 * The index separates default routes from non-default routes. */
-	NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_WITH_DEFAULT,
-
 	/* Consider all the destination fields of a route, that is, the ID without the ifindex
 	 * and gateway (meaning: network/plen,metric).
 	 * The reason for this is that `ip route change` can replace an existing route
@@ -469,8 +466,7 @@ const NMPLookup *nmp_lookup_init_addrroute (NMPLookup *lookup,
 const NMPLookup *nmp_lookup_init_route_visible (NMPLookup *lookup,
                                                 NMPObjectType obj_type,
                                                 int ifindex,
-                                                gboolean with_default,
-                                                gboolean with_non_default);
+                                                gboolean only_default);
 const NMPLookup *nmp_lookup_init_route_by_dest (NMPLookup *lookup,
                                                 int addr_family,
                                                 gconstpointer network,
@@ -649,12 +645,11 @@ static inline const NMDedupMultiHeadEntry *
 nm_platform_lookup_route_visible (NMPlatform *platform,
                                   NMPObjectType obj_type,
                                   int ifindex,
-                                  gboolean with_default,
-                                  gboolean with_non_default)
+                                  gboolean only_default)
 {
 	NMPLookup lookup;
 
-	nmp_lookup_init_route_visible (&lookup, obj_type, ifindex, with_default, with_non_default);
+	nmp_lookup_init_route_visible (&lookup, obj_type, ifindex, only_default);
 	return nm_platform_lookup (platform, &lookup);
 }
 
@@ -662,14 +657,13 @@ static inline GPtrArray *
 nm_platform_lookup_route_visible_clone (NMPlatform *platform,
                                         NMPObjectType obj_type,
                                         int ifindex,
-                                        gboolean with_default,
-                                        gboolean with_non_default,
+                                        gboolean only_default,
                                         gboolean (*predicate) (const NMPObject *obj, gpointer user_data),
                                         gpointer user_data)
 {
 	NMPLookup lookup;
 
-	nmp_lookup_init_route_visible (&lookup, obj_type, ifindex, with_default, with_non_default);
+	nmp_lookup_init_route_visible (&lookup, obj_type, ifindex, only_default);
 	return nm_platform_lookup_clone (platform, &lookup, predicate, user_data);
 }
 
diff --git a/src/platform/tests/test-common.h b/src/platform/tests/test-common.h
index e047705fd3..b9e879ff62 100644
--- a/src/platform/tests/test-common.h
+++ b/src/platform/tests/test-common.h
@@ -195,8 +195,7 @@ nmtstp_ip4_route_get_all (NMPlatform *platform,
 	return nm_platform_lookup_route_visible_clone (platform,
 	                                               NMP_OBJECT_TYPE_IP4_ROUTE,
 	                                               ifindex,
-	                                               TRUE,
-	                                               TRUE,
+	                                               FALSE,
 	                                               nm_platform_lookup_predicate_routes_skip_rtprot_kernel,
 	                                               NULL);
 }
@@ -208,8 +207,7 @@ nmtstp_ip6_route_get_all (NMPlatform *platform,
 	return nm_platform_lookup_route_visible_clone (platform,
 	                                               NMP_OBJECT_TYPE_IP6_ROUTE,
 	                                               ifindex,
-	                                               TRUE,
-	                                               TRUE,
+	                                               FALSE,
 	                                               nm_platform_lookup_predicate_routes_skip_rtprot_kernel,
 	                                               NULL);
 }
diff --git a/src/tests/test-route-manager.c b/src/tests/test-route-manager.c
index 275d898641..cf771f80ea 100644
--- a/src/tests/test-route-manager.c
+++ b/src/tests/test-route-manager.c
@@ -169,14 +169,14 @@ ip_routes (test_fixture *fixture, NMPObjectType obj_type)
 		pl_head_entry = nm_platform_lookup_route_visible (NM_PLATFORM_GET,
 		                                                  obj_type,
 		                                                  ifindex,
-		                                                  FALSE,
-		                                                  TRUE);
+		                                                  FALSE);
 		nmp_cache_iter_for_each (&iter, pl_head_entry, &plobj) {
 			const NMPlatformIPRoute *r = NMP_OBJECT_CAST_IP_ROUTE (plobj);
 
+			if (NM_PLATFORM_IP_ROUTE_IS_DEFAULT (r))
+				continue;
 			if (r->rt_source == NM_IP_CONFIG_SOURCE_RTPROT_KERNEL)
 				continue;
-			g_assert (!NM_PLATFORM_IP_ROUTE_IS_DEFAULT (r));
 			g_assert (r->ifindex == ifindex);
 			g_assert (nmp_object_is_visible (plobj));
 			g_array_append_vals (routes, r, 1);