platform: use NMDedupMultiIndex for routes in NMPCacheth/dedup-multi

Rework platform object cache to use NMDedupMultiIndex.

Already previously, NMPCache used NMMultiIndex and had thus
O(1) for most operations. What is new is:

- NMDedupMultiIndex preserves the order of the cached items.
  This is important to handle routes properly as kernel will
  replace the first matching route based on network/plen/metric
  properties. See related bug rh#1337855.
  Without tracking the order of routes as they are exposed
  by kernel, we cannot properly maintain the route cache.

- All NMPObject instances are now treated immutable, refcounted
  and get de-duplicated via NMDedupMultiIndex. This allows
  to have a global NMDedupMultiIndex that can be shared with
  NMIP4Config and NMRouteManager. It also allows to share the
  objects themselves.
  Immutable objects are so much nicer. We can get rid of the
  update pre-hook callback, which was required previously because
  we would mutate the object inplace. Now, we can just update
  the cache, and compare obj_old and obj_new after the fact.

- NMMultiIndex was treated as an internal of NMPCache. On the other
  hand, NMDedupMultiIndex exposes NMDedupMultiHeadEntry, which is
  basically an object that allows to iterate over all related
  objects. That means, we can now lookup objects in the cache
  and give the NMDedupMultiHeadEntry instance to the caller,
  which then can iterate the list on it's own -- without need
  for copying anything.
  Currently, at various places we still create copies of lookup
  results. That can be improved later.

The ability to share NMPObject instances should enable us to
significantly improve performance and scale with large number
of routes.

1 files changed, 1089 insertions, 752 deletions

diff --git a/src/platform/nmp-object.c b/src/platform/nmp-object.c
index 234647dd4e..4b6b6c0495 100644
--- a/src/platform/nmp-object.c
+++ b/src/platform/nmp-object.c
@@ -51,6 +51,11 @@
 
 /*****************************************************************************/
 
+typedef struct {
+	NMDedupMultiIdxType parent;
+	NMPCacheIdType cache_id_type;
+} DedupMultiIdxType;
+
 struct _NMPCache {
 	/* the cache contains only one hash table for all object types, and similarly
 	 * it contains only one NMMultiIndex.
@@ -66,14 +71,319 @@ struct _NMPCache {
 	 * This effectively merges the udev-device cache into the NMPCache.
 	 */
 
-	GHashTable *idx_main;
-	NMMultiIndex *idx_multi;
+	NMDedupMultiIndex *multi_idx;
+
+	/* an idx_type entry for each NMP_CACHE_ID_TYPE. Note that NONE (zero)
+	 * is skipped, so the index is shifted by one: idx_type[cache_id_type - 1].
+	 *
+	 * Don't bother, use _idx_type_get() instead! */
+	DedupMultiIdxType idx_types[NMP_CACHE_ID_TYPE_MAX];
 
 	gboolean use_udev;
 };
 
 /*****************************************************************************/
 
+static const NMDedupMultiIdxTypeClass _dedup_multi_idx_type_class;
+
+static guint
+_idx_obj_id_hash (const NMDedupMultiIdxType *idx_type,
+                  const NMDedupMultiObj *obj)
+{
+	const NMPObject *o = (NMPObject *) obj;
+
+	nm_assert (idx_type && idx_type->klass == &_dedup_multi_idx_type_class);
+	nm_assert (NMP_OBJECT_GET_TYPE (o) != NMP_OBJECT_TYPE_UNKNOWN);
+
+	return nmp_object_id_hash (o);
+}
+
+static gboolean
+_idx_obj_id_equal (const NMDedupMultiIdxType *idx_type,
+                   const NMDedupMultiObj *obj_a,
+                   const NMDedupMultiObj *obj_b)
+{
+	const NMPObject *o_a = (NMPObject *) obj_a;
+	const NMPObject *o_b = (NMPObject *) obj_b;
+
+	nm_assert (idx_type && idx_type->klass == &_dedup_multi_idx_type_class);
+	nm_assert (NMP_OBJECT_GET_TYPE (o_a) != NMP_OBJECT_TYPE_UNKNOWN);
+	nm_assert (NMP_OBJECT_GET_TYPE (o_b) != NMP_OBJECT_TYPE_UNKNOWN);
+
+	return nmp_object_id_equal (o_a, o_b);
+}
+
+/* the return value of _idx_obj_part() encodes 3 things:
+ * 1) for idx_obj_partitionable(), it returns 0 or non-zero.
+ * 2) for idx_obj_partition_hash(), it returns the hash value (which
+ *   must never be zero not to clash with idx_obj_partitionable().
+ * 3) for idx_obj_partition_equal(), returns 0 or 1 depending
+ *   on whether the objects are equal.
+ *
+ * _HASH_NON_ZERO() is used to for case 2), to avoid that the a zero hash value
+ * is returned. */
+#define _HASH_NON_ZERO(h) \
+	((h) ?: (1998098407 + __LINE__)) \
+
+static guint
+_idx_obj_part (const DedupMultiIdxType *idx_type,
+               gboolean request_hash,
+               const NMPObject *obj_a,
+               const NMPObject *obj_b)
+{
+	guint h;
+
+	/* the hash/equals functions are strongly related. So, keep them
+	 * side-by-side and do it all in _idx_obj_part(). */
+
+	nm_assert (idx_type);
+	nm_assert (idx_type->parent.klass == &_dedup_multi_idx_type_class);
+	nm_assert (obj_a);
+	nm_assert (NMP_OBJECT_GET_TYPE (obj_a) != NMP_OBJECT_TYPE_UNKNOWN);
+	nm_assert (!obj_b || (NMP_OBJECT_GET_TYPE (obj_b) != NMP_OBJECT_TYPE_UNKNOWN));
+	nm_assert (!request_hash || !obj_b);
+
+	switch (idx_type->cache_id_type) {
+
+	case NMP_CACHE_ID_TYPE_OBJECT_TYPE:
+		if (obj_b)
+			return NMP_OBJECT_GET_TYPE (obj_a) == NMP_OBJECT_GET_TYPE (obj_b);
+		if (request_hash) {
+			h = (guint) idx_type->cache_id_type;
+			h = NM_HASH_COMBINE (h, NMP_OBJECT_GET_TYPE (obj_a));
+			return _HASH_NON_ZERO (h);
+		}
+		return 1;
+
+	case NMP_CACHE_ID_TYPE_LINK_BY_IFNAME:
+		if (NMP_OBJECT_GET_TYPE (obj_a) != NMP_OBJECT_TYPE_LINK) {
+			/* first check, whether obj_a is suitable for this idx_type.
+			 * If not, return 0 (which is correct for partitionable(), hash() and equal()
+			 * functions. */
+			return 0;
+		}
+		if (obj_b) {
+			/* we are in equal() mode. Compare obj_b with obj_a. */
+			return    NMP_OBJECT_GET_TYPE (obj_b) == NMP_OBJECT_TYPE_LINK
+			       && nm_streq (obj_a->link.name, obj_b->link.name);
+		}
+		if (request_hash) {
+			/* we request a hash from obj_a. Hash the relevant parts. */
+			h = (guint) idx_type->cache_id_type;
+			h = NM_HASH_COMBINE (h, g_str_hash (obj_a->link.name));
+			return _HASH_NON_ZERO (h);
+		}
+		/* just return 1, to indicate that obj_a is partitionable by this idx_type. */
+		return 1;
+
+	case NMP_CACHE_ID_TYPE_OBJECT_TYPE_VISIBLE_ONLY:
+		if (!nmp_object_is_visible (obj_a))
+			return 0;
+		if (obj_b) {
+			return    NMP_OBJECT_GET_TYPE (obj_a) == NMP_OBJECT_GET_TYPE (obj_b)
+			       && 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));
+			return _HASH_NON_ZERO (h);
+		}
+		return 1;
+
+	case NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_NO_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_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));
+			return _HASH_NON_ZERO (h);
+		}
+		return 1;
+
+	case NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_ONLY_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_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));
+			return _HASH_NON_ZERO (h);
+		}
+		return 1;
+
+	case NMP_CACHE_ID_TYPE_ADDRROUTE_VISIBLE_BY_IFINDEX:
+		if (   !NM_IN_SET (NMP_OBJECT_GET_TYPE (obj_a), NMP_OBJECT_TYPE_IP4_ADDRESS,
+		                                                NMP_OBJECT_TYPE_IP6_ADDRESS,
+		                                                NMP_OBJECT_TYPE_IP4_ROUTE,
+		                                                NMP_OBJECT_TYPE_IP6_ROUTE)
+		    || !nmp_object_is_visible (obj_a))
+			return 0;
+		nm_assert (obj_a->object.ifindex > 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
+			       && 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, obj_a->object.ifindex);
+			return _HASH_NON_ZERO (h);
+		}
+		return 1;
+
+	case NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_NO_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)
+		    || 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)
+			       && !NM_PLATFORM_IP_ROUTE_IS_DEFAULT (&obj_b->ip_route)
+			       && obj_a->object.ifindex == obj_b->object.ifindex
+			       && 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, obj_a->object.ifindex);
+			return _HASH_NON_ZERO (h);
+		}
+		return 1;
+
+	case NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_ONLY_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)
+		    || 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)
+			       && NM_PLATFORM_IP_ROUTE_IS_DEFAULT (&obj_b->ip_route)
+			       && obj_a->object.ifindex == obj_b->object.ifindex
+			       && 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, obj_a->object.ifindex);
+			return _HASH_NON_ZERO (h);
+		}
+		return 1;
+
+	case NMP_CACHE_ID_TYPE_ROUTES_BY_DESTINATION_IP4:
+		if (   !NM_IN_SET (NMP_OBJECT_GET_TYPE (obj_a), NMP_OBJECT_TYPE_IP4_ROUTE)
+		    || obj_a->object.ifindex <= 0)
+			return 0;
+		if (obj_b) {
+			return    NMP_OBJECT_GET_TYPE (obj_a) == NMP_OBJECT_GET_TYPE (obj_b)
+			       && obj_b->object.ifindex > 0
+			       && obj_a->ip_route.plen == obj_b->ip_route.plen
+			       && obj_a->ip_route.metric == obj_b->ip_route.metric
+			       && obj_a->ip4_route.network == obj_b->ip4_route.network;
+		}
+		if (request_hash) {
+			h = (guint) idx_type->cache_id_type;
+			h = NM_HASH_COMBINE (h, obj_a->ip_route.plen);
+			h = NM_HASH_COMBINE (h, obj_a->ip_route.metric);
+			h = NM_HASH_COMBINE (h, obj_a->ip4_route.network);
+			return _HASH_NON_ZERO (h);
+		}
+		return 1;
+
+	case NMP_CACHE_ID_TYPE_ROUTES_BY_DESTINATION_IP6:
+		if (   !NM_IN_SET (NMP_OBJECT_GET_TYPE (obj_a), NMP_OBJECT_TYPE_IP6_ROUTE)
+		    || obj_a->object.ifindex <= 0)
+			return 0;
+		if (obj_b) {
+			return    NMP_OBJECT_GET_TYPE (obj_a) == NMP_OBJECT_GET_TYPE (obj_b)
+			       && obj_b->object.ifindex > 0
+			       && obj_a->ip_route.plen == obj_b->ip_route.plen
+			       && obj_a->ip_route.metric == obj_b->ip_route.metric
+			       && IN6_ARE_ADDR_EQUAL (&obj_a->ip6_route.network, &obj_b->ip6_route.network);
+		}
+		if (request_hash) {
+			h = (guint) idx_type->cache_id_type;
+			h = NM_HASH_COMBINE (h, obj_a->ip_route.plen);
+			h = NM_HASH_COMBINE (h, obj_a->ip_route.metric);
+			h = NM_HASH_COMBINE (h, nm_utils_in6_addr_hash (&obj_a->ip6_route.network));
+			return _HASH_NON_ZERO (h);
+		}
+		return 1;
+
+	case NMP_CACHE_ID_TYPE_NONE:
+	case __NMP_CACHE_ID_TYPE_MAX:
+		break;
+	}
+	nm_assert_not_reached ();
+	return 0;
+}
+
+static gboolean
+_idx_obj_partitionable (const NMDedupMultiIdxType *idx_type,
+                        const NMDedupMultiObj *obj)
+{
+	return _idx_obj_part ((DedupMultiIdxType *) idx_type,
+	                      FALSE,
+	                      (NMPObject *) obj,
+	                      NULL) != 0;
+}
+
+static guint
+_idx_obj_partition_hash (const NMDedupMultiIdxType *idx_type,
+                         const NMDedupMultiObj *obj)
+{
+	return _idx_obj_part ((DedupMultiIdxType *) idx_type,
+	                      TRUE,
+	                      (NMPObject *) obj,
+	                      NULL);
+}
+
+static gboolean
+_idx_obj_partition_equal (const NMDedupMultiIdxType *idx_type,
+                          const NMDedupMultiObj *obj_a,
+                          const NMDedupMultiObj *obj_b)
+{
+	return _idx_obj_part ((DedupMultiIdxType *) idx_type,
+	                      FALSE,
+	                      (NMPObject *) obj_a,
+	                      (NMPObject *) obj_b);
+}
+
+static const NMDedupMultiIdxTypeClass _dedup_multi_idx_type_class = {
+	.idx_obj_id_hash = _idx_obj_id_hash,
+	.idx_obj_id_equal = _idx_obj_id_equal,
+	.idx_obj_partitionable = _idx_obj_partitionable,
+	.idx_obj_partition_hash = _idx_obj_partition_hash,
+	.idx_obj_partition_equal = _idx_obj_partition_equal,
+};
+
+static void
+_dedup_multi_idx_type_init (DedupMultiIdxType *idx_type, NMPCacheIdType cache_id_type)
+{
+	nm_dedup_multi_idx_type_init ((NMDedupMultiIdxType *) idx_type,
+	                              &_dedup_multi_idx_type_class);
+	idx_type->cache_id_type = cache_id_type;
+}
+
+/*****************************************************************************/
+
 static int
 _vlan_xgress_qos_mappings_cmp (guint n_map,
                                const NMVlanQosMapping *map1,
@@ -139,12 +449,18 @@ _link_get_driver (struct udev_device *udevice, const char *kind, int ifindex)
 }
 
 void
-_nmp_object_fixup_link_udev_fields (NMPObject *obj, gboolean use_udev)
+_nmp_object_fixup_link_udev_fields (NMPObject **obj_new, NMPObject *obj_orig, gboolean use_udev)
 {
 	const char *driver = NULL;
 	gboolean initialized = FALSE;
+	NMPObject *obj;
 
-	nm_assert (NMP_OBJECT_GET_TYPE (obj) == NMP_OBJECT_TYPE_LINK);
+	nm_assert (obj_orig || *obj_new);
+	nm_assert (obj_new);
+	nm_assert (!obj_orig || NMP_OBJECT_GET_TYPE (obj_orig) == NMP_OBJECT_TYPE_LINK);
+	nm_assert (!*obj_new || NMP_OBJECT_GET_TYPE (*obj_new) == NMP_OBJECT_TYPE_LINK);
+
+	obj = *obj_new ?: obj_orig;
 
 	/* The link contains internal fields that are combined by
 	 * properties from netlink and udev. Update those properties */
@@ -168,17 +484,34 @@ _nmp_object_fixup_link_udev_fields (NMPObject *obj, gboolean use_udev)
 		}
 	}
 
+	if (   nm_streq0 (obj->link.driver, driver)
+	    && obj->link.initialized == initialized)
+		return;
+
+	if (!*obj_new)
+		obj = *obj_new = nmp_object_clone (obj, FALSE);
+
 	obj->link.driver = driver;
 	obj->link.initialized = initialized;
 }
 
 static void
-_nmp_object_fixup_link_master_connected (NMPObject *obj, const NMPCache *cache)
+_nmp_object_fixup_link_master_connected (NMPObject **obj_new, NMPObject *obj_orig, const NMPCache *cache)
 {
-	nm_assert (NMP_OBJECT_GET_TYPE (obj) == NMP_OBJECT_TYPE_LINK);
+	NMPObject *obj;
+
+	nm_assert (obj_orig || *obj_new);
+	nm_assert (obj_new);
+	nm_assert (!obj_orig || NMP_OBJECT_GET_TYPE (obj_orig) == NMP_OBJECT_TYPE_LINK);
+	nm_assert (!*obj_new || NMP_OBJECT_GET_TYPE (*obj_new) == NMP_OBJECT_TYPE_LINK);
 
-	if (nmp_cache_link_connected_needs_toggle (cache, obj, NULL, NULL))
+	obj = *obj_new ?: obj_orig;
+
+	if (nmp_cache_link_connected_needs_toggle (cache, obj, NULL, NULL)) {
+		if (!*obj_new)
+			obj = *obj_new = nmp_object_clone (obj, FALSE);
 		obj->link.connected = !obj->link.connected;
+	}
 }
 
 /*****************************************************************************/
@@ -193,29 +526,34 @@ nmp_class_from_type (NMPObjectType obj_type)
 
 /*****************************************************************************/
 
-NMPObject *
-nmp_object_ref (NMPObject *obj)
+const NMPObject *
+nmp_object_ref (const NMPObject *obj)
 {
+	/* ref and unref accept const pointers. NMPObject is supposed to be shared
+	 * and kept immutable. Disallowing to take/retrun a reference to a const
+	 * NMPObject is cumbersome, because callers are precisely expected to
+	 * keep a ref on the otherwise immutable object. */
 	g_return_val_if_fail (NMP_OBJECT_IS_VALID (obj), NULL);
 	g_return_val_if_fail (obj->_ref_count != NM_OBJ_REF_COUNT_STACKINIT, NULL);
-	obj->_ref_count++;
+	((NMPObject *) obj)->_ref_count++;
 
 	return obj;
 }
 
 void
-nmp_object_unref (NMPObject *obj)
+nmp_object_unref (const NMPObject *obj)
 {
 	if (obj) {
-		g_return_if_fail (obj->_ref_count > 0);
-		g_return_if_fail (obj->_ref_count != NM_OBJ_REF_COUNT_STACKINIT);
-		if (--obj->_ref_count <= 0) {
-			const NMPClass *klass = obj->_class;
+		NMPObject *o = (NMPObject *) obj;
+
+		g_return_if_fail (o->_ref_count > 0);
+		g_return_if_fail (o->_ref_count != NM_OBJ_REF_COUNT_STACKINIT);
+		if (--o->_ref_count <= 0) {
+			const NMPClass *klass = o->_class;
 
-			nm_assert (!obj->is_cached);
 			if (klass->cmd_obj_dispose)
-				klass->cmd_obj_dispose (obj);
-			g_slice_free1 (klass->sizeof_data + G_STRUCT_OFFSET (NMPObject, object), obj);
+				klass->cmd_obj_dispose (o);
+			g_slice_free1 (klass->sizeof_data + G_STRUCT_OFFSET (NMPObject, object), o);
 		}
 	}
 }
@@ -276,9 +614,24 @@ nmp_object_new_link (int ifindex)
 
 /*****************************************************************************/
 
-static const NMPObject *
+static void
 _nmp_object_stackinit_from_class (NMPObject *obj, const NMPClass *klass)
 {
+	nm_assert (obj);
+	nm_assert (klass);
+
+	memset (obj, 0, sizeof (NMPObject));
+	obj->_class = klass;
+	obj->_ref_count = NM_OBJ_REF_COUNT_STACKINIT;
+}
+
+static NMPObject *
+_nmp_object_stackinit_from_type (NMPObject *obj, NMPObjectType obj_type)
+{
+	const NMPClass *klass;
+
+	nm_assert (obj);
+	klass = nmp_class_from_type (obj_type);
 	nm_assert (klass);
 
 	memset (obj, 0, sizeof (NMPObject));
@@ -308,7 +661,7 @@ nmp_object_stackinit_id  (NMPObject *obj, const NMPObject *src)
 
 	klass = NMP_OBJECT_GET_CLASS (src);
 	if (!klass->cmd_obj_stackinit_id)
-		nmp_object_stackinit (obj, klass->obj_type, NULL);
+		_nmp_object_stackinit_from_class (obj, klass);
 	else
 		klass->cmd_obj_stackinit_id (obj, src);
 	return obj;
@@ -317,7 +670,7 @@ nmp_object_stackinit_id  (NMPObject *obj, const NMPObject *src)
 const NMPObject *
 nmp_object_stackinit_id_link (NMPObject *obj, int ifindex)
 {
-	nmp_object_stackinit (obj, NMP_OBJECT_TYPE_LINK, NULL);
+	_nmp_object_stackinit_from_type (obj, NMP_OBJECT_TYPE_LINK);
 	obj->link.ifindex = ifindex;
 	return obj;
 }
@@ -331,7 +684,7 @@ _vt_cmd_obj_stackinit_id_link (NMPObject *obj, const NMPObject *src)
 const NMPObject *
 nmp_object_stackinit_id_ip4_address (NMPObject *obj, int ifindex, guint32 address, guint8 plen, guint32 peer_address)
 {
-	nmp_object_stackinit (obj, NMP_OBJECT_TYPE_IP4_ADDRESS, NULL);
+	_nmp_object_stackinit_from_type (obj, NMP_OBJECT_TYPE_IP4_ADDRESS);
 	obj->ip4_address.ifindex = ifindex;
 	obj->ip4_address.address = address;
 	obj->ip4_address.plen = plen;
@@ -348,7 +701,7 @@ _vt_cmd_obj_stackinit_id_ip4_address (NMPObject *obj, const NMPObject *src)
 const NMPObject *
 nmp_object_stackinit_id_ip6_address (NMPObject *obj, int ifindex, const struct in6_addr *address)
 {
-	nmp_object_stackinit (obj, NMP_OBJECT_TYPE_IP6_ADDRESS, NULL);
+	_nmp_object_stackinit_from_type (obj, NMP_OBJECT_TYPE_IP6_ADDRESS);
 	obj->ip4_address.ifindex = ifindex;
 	if (address)
 		obj->ip6_address.address = *address;
@@ -364,7 +717,7 @@ _vt_cmd_obj_stackinit_id_ip6_address (NMPObject *obj, const NMPObject *src)
 const NMPObject *
 nmp_object_stackinit_id_ip4_route (NMPObject *obj, int ifindex, guint32 network, guint8 plen, guint32 metric)
 {
-	nmp_object_stackinit (obj, NMP_OBJECT_TYPE_IP4_ROUTE, NULL);
+	_nmp_object_stackinit_from_type (obj, NMP_OBJECT_TYPE_IP4_ROUTE);
 	obj->ip4_route.ifindex = ifindex;
 	obj->ip4_route.network = network;
 	obj->ip4_route.plen = plen;
@@ -381,7 +734,7 @@ _vt_cmd_obj_stackinit_id_ip4_route (NMPObject *obj, const NMPObject *src)
 const NMPObject *
 nmp_object_stackinit_id_ip6_route (NMPObject *obj, int ifindex, const struct in6_addr *network, guint8 plen, guint32 metric)
 {
-	nmp_object_stackinit (obj, NMP_OBJECT_TYPE_IP6_ROUTE, NULL);
+	_nmp_object_stackinit_from_type (obj, NMP_OBJECT_TYPE_IP6_ROUTE);
 	obj->ip6_route.ifindex = ifindex;
 	if (network)
 		obj->ip6_route.network = *network;
@@ -423,9 +776,8 @@ nmp_object_to_string (const NMPObject *obj, NMPObjectToStringMode to_string_mode
 		return klass->cmd_plobj_to_string_id (&obj->object, buf, buf_size);
 	case NMP_OBJECT_TO_STRING_ALL:
 		g_snprintf (buf, buf_size,
-		            "[%s,%p,%u,%ccache,%calive,%cvisible; %s]",
+		            "[%s,%p,%u,%calive,%cvisible; %s]",
 		            klass->obj_type_name, obj, obj->_ref_count,
-		            obj->is_cached ? '+' : '-',
 		            nmp_object_is_alive (obj) ? '+' : '-',
 		            nmp_object_is_visible (obj) ? '+' : '-',
 		            NMP_OBJECT_GET_CLASS (obj)->cmd_plobj_to_string (&obj->object, buf2, sizeof (buf2)));
@@ -450,9 +802,8 @@ _vt_cmd_obj_to_string_link (const NMPObject *obj, NMPObjectToStringMode to_strin
 		return klass->cmd_plobj_to_string_id (&obj->object, buf, buf_size);
 	case NMP_OBJECT_TO_STRING_ALL:
 		g_snprintf (buf, buf_size,
-		            "[%s,%p,%u,%ccache,%calive,%cvisible,%cin-nl,%p; %s]",
+		            "[%s,%p,%u,%calive,%cvisible,%cin-nl,%p; %s]",
 		            klass->obj_type_name, obj, obj->_ref_count,
-		            obj->is_cached ? '+' : '-',
 		            nmp_object_is_alive (obj) ? '+' : '-',
 		            nmp_object_is_visible (obj) ? '+' : '-',
 		            obj->_link.netlink.is_in_netlink ? '+' : '-',
@@ -491,9 +842,8 @@ _vt_cmd_obj_to_string_lnk_vlan (const NMPObject *obj, NMPObjectToStringMode to_s
 	case NMP_OBJECT_TO_STRING_ALL:
 
 		g_snprintf (buf, buf_size,
-		            "[%s,%p,%u,%ccache,%calive,%cvisible; %s]",
+		            "[%s,%p,%u,%calive,%cvisible; %s]",
 		            klass->obj_type_name, obj, obj->_ref_count,
-		            obj->is_cached ? '+' : '-',
 		            nmp_object_is_alive (obj) ? '+' : '-',
 		            nmp_object_is_visible (obj) ? '+' : '-',
 		            nmp_object_to_string (obj, NMP_OBJECT_TO_STRING_PUBLIC, buf2, sizeof (buf2)));
@@ -581,6 +931,21 @@ _vt_cmd_obj_hash_not_implemented (const NMPObject *obj)
 }
 
 static guint
+_vt_cmd_obj_hash_link (const NMPObject *obj)
+{
+	guint h = 1228913327;
+
+	nm_assert (NMP_OBJECT_GET_TYPE (obj) == NMP_OBJECT_TYPE_LINK);
+
+	h = NM_HASH_COMBINE (h, nm_platform_link_hash (&obj->link));
+	h = NM_HASH_COMBINE (h, obj->_link.netlink.is_in_netlink);
+	/* TODO: properly hash lnk objects. */
+	h = NM_HASH_COMBINE (h, !!obj->_link.netlink.lnk);
+	h = NM_HASH_COMBINE (h, GPOINTER_TO_UINT (obj->_link.udev.device));
+	return h;
+}
+
+static guint
 _vt_cmd_plobj_hash_not_implemented (const NMPlatformObject *obj)
 {
 	g_return_val_if_reached (0);
@@ -977,218 +1342,6 @@ _vt_cmd_obj_is_visible_link (const NMPObject *obj)
 
 /*****************************************************************************/
 
-_NM_UTILS_LOOKUP_DEFINE (static, _nmp_cache_id_size_by_type, NMPCacheIdType, guint,
-	NM_UTILS_LOOKUP_DEFAULT (({ nm_assert_not_reached (); (guint) 0; })),
-	NM_UTILS_LOOKUP_ITEM (NMP_CACHE_ID_TYPE_OBJECT_TYPE,                            nm_offsetofend (NMPCacheId, object_type)),
-	NM_UTILS_LOOKUP_ITEM (NMP_CACHE_ID_TYPE_OBJECT_TYPE_VISIBLE_ONLY,               nm_offsetofend (NMPCacheId, object_type)),
-	NM_UTILS_LOOKUP_ITEM (NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_NO_DEFAULT,              nm_offsetofend (NMPCacheId, object_type)),
-	NM_UTILS_LOOKUP_ITEM (NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_ONLY_DEFAULT,            nm_offsetofend (NMPCacheId, object_type)),
-	NM_UTILS_LOOKUP_ITEM (NMP_CACHE_ID_TYPE_ADDRROUTE_VISIBLE_BY_IFINDEX,           nm_offsetofend (NMPCacheId, object_type_by_ifindex)),
-	NM_UTILS_LOOKUP_ITEM (NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_NO_DEFAULT,   nm_offsetofend (NMPCacheId, object_type_by_ifindex)),
-	NM_UTILS_LOOKUP_ITEM (NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_ONLY_DEFAULT, nm_offsetofend (NMPCacheId, object_type_by_ifindex)),
-	NM_UTILS_LOOKUP_ITEM (NMP_CACHE_ID_TYPE_LINK_BY_IFNAME,                         nm_offsetofend (NMPCacheId, link_by_ifname)),
-	NM_UTILS_LOOKUP_ITEM (NMP_CACHE_ID_TYPE_ROUTES_BY_DESTINATION_IP4,              nm_offsetofend (NMPCacheId, routes_by_destination_ip4)),
-	NM_UTILS_LOOKUP_ITEM (NMP_CACHE_ID_TYPE_ROUTES_BY_DESTINATION_IP6,              nm_offsetofend (NMPCacheId, routes_by_destination_ip6)),
-	NM_UTILS_LOOKUP_ITEM_IGNORE (NMP_CACHE_ID_TYPE_NONE),
-	NM_UTILS_LOOKUP_ITEM_IGNORE (__NMP_CACHE_ID_TYPE_MAX),
-);
-
-gboolean
-nmp_cache_id_equal (const NMPCacheId *a, const NMPCacheId *b)
-{
-	if (a->_id_type != b->_id_type)
-		return FALSE;
-	return memcmp (a, b, _nmp_cache_id_size_by_type (a->_id_type)) == 0;
-}
-
-guint
-nmp_cache_id_hash (const NMPCacheId *id)
-{
-	guint hash = 5381;
-	guint i, n;
-
-	n = _nmp_cache_id_size_by_type (id->_id_type);
-	for (i = 0; i < n; i++)
-		hash = NM_HASH_COMBINE (hash, ((char *) id)[i]);
-	return hash;
-}
-
-NMPCacheId *
-nmp_cache_id_clone (const NMPCacheId *id)
-{
-	NMPCacheId *id2;
-	guint n;
-
-	n = _nmp_cache_id_size_by_type (id->_id_type);
-	id2 = g_slice_alloc (n);
-	memcpy (id2, id, n);
-	return id2;
-}
-
-void
-nmp_cache_id_destroy (NMPCacheId *id)
-{
-	guint n;
-
-	n = _nmp_cache_id_size_by_type (id->_id_type);
-	g_slice_free1 (n, id);
-}
-
-/*****************************************************************************/
-
-static void
-_nmp_cache_id_init (NMPCacheId *id, NMPCacheIdType id_type)
-{
-	/* there is no need to set the entire @id to zero when
-	 * initializing the ID.
-	 *
-	 * First, depending on the @id_type only part of the
-	 * @id is actually used (_nmp_cache_id_size_by_type).
-	 *
-	 * Second, the nmp_cache_id_init_*() *MUST* anyway make sure
-	 * that all relevant fields are set. Since it happens that
-	 * all structs have the packed attribute, there are no holes
-	 * due to alignment, and it becomes simple for nmp_cache_id_init_*()
-	 * to ensure that all fields are set. */
-
-#if NM_MORE_ASSERTS
-	nm_assert (id);
-	{
-		guint i;
-
-		/* initialized with some bogus canary to hopefully detect when we miss
-		 * to initialize a field of the cache-id. */
-		for (i = 0; i < sizeof (*id); i++) {
-			((char *) id)[i] = GPOINTER_TO_UINT (id) ^ i;
-		}
-	}
-#endif
-
-	id->_id_type = id_type;
-}
-
-NMPCacheId *
-nmp_cache_id_init_object_type (NMPCacheId *id, NMPObjectType obj_type, gboolean visible_only)
-{
-	_nmp_cache_id_init (id, visible_only
-	                        ? NMP_CACHE_ID_TYPE_OBJECT_TYPE_VISIBLE_ONLY
-	                        : NMP_CACHE_ID_TYPE_OBJECT_TYPE);
-	id->object_type.obj_type = obj_type;
-	return id;
-}
-
-NMPCacheId *
-nmp_cache_id_init_addrroute_visible_by_ifindex (NMPCacheId *id,
-                                                NMPObjectType obj_type,
-                                                int ifindex)
-{
-	g_return_val_if_fail (NM_IN_SET (obj_type,
-	                                 NMP_OBJECT_TYPE_IP4_ADDRESS, NMP_OBJECT_TYPE_IP4_ROUTE,
-	                                 NMP_OBJECT_TYPE_IP6_ADDRESS, NMP_OBJECT_TYPE_IP6_ROUTE), NULL);
-
-	if (ifindex <= 0)
-		return nmp_cache_id_init_object_type (id, obj_type, TRUE);
-
-	_nmp_cache_id_init (id, NMP_CACHE_ID_TYPE_ADDRROUTE_VISIBLE_BY_IFINDEX);
-	id->object_type_by_ifindex.obj_type = obj_type;
-	memcpy (&id->object_type_by_ifindex._misaligned_ifindex, &ifindex, sizeof (int));
-	return id;
-}
-
-NMPCacheId *
-nmp_cache_id_init_routes_visible (NMPCacheId *id,
-                                  NMPObjectType obj_type,
-                                  gboolean with_default,
-                                  gboolean with_non_default,
-                                  int ifindex)
-{
-	g_return_val_if_fail (NM_IN_SET (obj_type, NMP_OBJECT_TYPE_IP4_ROUTE, NMP_OBJECT_TYPE_IP6_ROUTE), NULL);
-
-	if (with_default) {
-		if (with_non_default) {
-			if (ifindex <= 0)
-				return nmp_cache_id_init_object_type (id, obj_type, TRUE);
-			return nmp_cache_id_init_addrroute_visible_by_ifindex (id, obj_type, ifindex);
-		}
-		_nmp_cache_id_init (id, NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_ONLY_DEFAULT);
-	} else if (with_non_default)
-		_nmp_cache_id_init (id, NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_NO_DEFAULT);
-	else
-		g_return_val_if_reached (NULL);
-
-	id->object_type_by_ifindex.obj_type = obj_type;
-	memcpy (&id->object_type_by_ifindex._misaligned_ifindex, &ifindex, sizeof (int));
-	return id;
-}
-
-NMPCacheId *
-nmp_cache_id_init_link_by_ifname (NMPCacheId *id,
-                                  const char *ifname)
-{
-	gsize l;
-
-	if (   !ifname
-	    || (l = strlen (ifname)) > sizeof (id->link_by_ifname.ifname_short))
-		g_return_val_if_reached (id);
-
-	_nmp_cache_id_init (id, NMP_CACHE_ID_TYPE_LINK_BY_IFNAME);
-
-	memset (id->link_by_ifname.ifname_short, 0, sizeof (id->link_by_ifname.ifname_short));
-	/* the trailing NUL is dropped!! */
-	memcpy (id->link_by_ifname.ifname_short, ifname, l);
-
-	return id;
-}
-
-NMPCacheId *
-nmp_cache_id_init_routes_by_destination_ip4 (NMPCacheId *id,
-                                             guint32 network,
-                                             guint8 plen,
-                                             guint32 metric)
-{
-	_nmp_cache_id_init (id, NMP_CACHE_ID_TYPE_ROUTES_BY_DESTINATION_IP4);
-	id->routes_by_destination_ip4.plen = plen;
-	memcpy (&id->routes_by_destination_ip4._misaligned_metric,  &metric, sizeof (guint32));
-	memcpy (&id->routes_by_destination_ip4._misaligned_network, &network, sizeof (guint32));
-	return id;
-}
-
-NMPCacheId *
-nmp_cache_id_init_routes_by_destination_ip6 (NMPCacheId *id,
-                                             const struct in6_addr *network,
-                                             guint8 plen,
-                                             guint32 metric)
-{
-	_nmp_cache_id_init (id, NMP_CACHE_ID_TYPE_ROUTES_BY_DESTINATION_IP6);
-	id->routes_by_destination_ip4.plen = plen;
-	memcpy (&id->routes_by_destination_ip6._misaligned_metric,  &metric, sizeof (guint32));
-	memcpy (&id->routes_by_destination_ip6._misaligned_network, network ?: &nm_ip_addr_zero.addr6, sizeof (struct in6_addr));
-	return id;
-}
-
-/*****************************************************************************/
-
-static gboolean
-_nmp_object_init_cache_id (const NMPObject *obj, NMPCacheIdType id_type, NMPCacheId *id, const NMPCacheId **out_id)
-{
-	const NMPClass *klass = NMP_OBJECT_GET_CLASS (obj);
-
-	switch (id_type) {
-	case NMP_CACHE_ID_TYPE_OBJECT_TYPE:
-		*out_id = nmp_cache_id_init_object_type (id, klass->obj_type, FALSE);
-		return TRUE;
-	case NMP_CACHE_ID_TYPE_OBJECT_TYPE_VISIBLE_ONLY:
-		if (nmp_object_is_visible (obj))
-			*out_id = nmp_cache_id_init_object_type (id, klass->obj_type, TRUE);
-		else
-			*out_id = NULL;
-		return TRUE;
-	default:
-		return    klass->cmd_obj_init_cache_id
-		       && klass->cmd_obj_init_cache_id (obj, id_type, id, out_id);
-	}
-}
-
 static const guint8 _supported_cache_ids_link[] = {
 	NMP_CACHE_ID_TYPE_OBJECT_TYPE,
 	NMP_CACHE_ID_TYPE_OBJECT_TYPE_VISIBLE_ONLY,
@@ -1196,23 +1349,6 @@ static const guint8 _supported_cache_ids_link[] = {
 	0,
 };
 
-static gboolean
-_vt_cmd_obj_init_cache_id_link (const NMPObject *obj, NMPCacheIdType id_type, NMPCacheId *id, const NMPCacheId **out_id)
-{
-	switch (id_type) {
-	case NMP_CACHE_ID_TYPE_LINK_BY_IFNAME:
-		if (obj->link.name[0]) {
-			*out_id = nmp_cache_id_init_link_by_ifname (id, obj->link.name);
-			return TRUE;
-		}
-		break;
-	default:
-		return FALSE;
-	}
-	*out_id = NULL;
-	return TRUE;
-}
-
 static const guint8 _supported_cache_ids_ipx_address[] = {
 	NMP_CACHE_ID_TYPE_OBJECT_TYPE,
 	NMP_CACHE_ID_TYPE_OBJECT_TYPE_VISIBLE_ONLY,
@@ -1220,24 +1356,6 @@ static const guint8 _supported_cache_ids_ipx_address[] = {
 	0,
 };
 
-static gboolean
-_vt_cmd_obj_init_cache_id_ipx_address (const NMPObject *obj, NMPCacheIdType id_type, NMPCacheId *id, const NMPCacheId **out_id)
-{
-	switch (id_type) {
-	case NMP_CACHE_ID_TYPE_ADDRROUTE_VISIBLE_BY_IFINDEX:
-		if (nmp_object_is_visible (obj)) {
-			nm_assert (obj->object.ifindex > 0);
-			*out_id = nmp_cache_id_init_addrroute_visible_by_ifindex (id, NMP_OBJECT_GET_TYPE (obj), obj->object.ifindex);
-			return TRUE;
-		}
-		break;
-	default:
-		return FALSE;
-	}
-	*out_id = NULL;
-	return TRUE;
-}
-
 static const guint8 _supported_cache_ids_ip4_route[] = {
 	NMP_CACHE_ID_TYPE_OBJECT_TYPE,
 	NMP_CACHE_ID_TYPE_OBJECT_TYPE_VISIBLE_ONLY,
@@ -1262,68 +1380,6 @@ static const guint8 _supported_cache_ids_ip6_route[] = {
 	0,
 };
 
-static gboolean
-_vt_cmd_obj_init_cache_id_ipx_route (const NMPObject *obj, NMPCacheIdType id_type, NMPCacheId *id, const NMPCacheId **out_id)
-{
-	switch (id_type) {
-	case NMP_CACHE_ID_TYPE_ADDRROUTE_VISIBLE_BY_IFINDEX:
-		if (nmp_object_is_visible (obj)) {
-			nm_assert (obj->object.ifindex > 0);
-			*out_id = nmp_cache_id_init_addrroute_visible_by_ifindex (id, NMP_OBJECT_GET_TYPE (obj), obj->object.ifindex);
-			return TRUE;
-		}
-		break;
-	case NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_NO_DEFAULT:
-		if (   nmp_object_is_visible  (obj)
-		    && !NM_PLATFORM_IP_ROUTE_IS_DEFAULT (&obj->ip_route)) {
-			nm_assert (obj->object.ifindex > 0);
-			*out_id = nmp_cache_id_init_routes_visible (id, NMP_OBJECT_GET_TYPE (obj), FALSE, TRUE, 0);
-			return TRUE;
-		}
-		break;
-	case NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_ONLY_DEFAULT:
-		if (   nmp_object_is_visible  (obj)
-		    && NM_PLATFORM_IP_ROUTE_IS_DEFAULT (&obj->ip_route)) {
-			nm_assert (obj->object.ifindex > 0);
-			*out_id = nmp_cache_id_init_routes_visible (id, NMP_OBJECT_GET_TYPE (obj), TRUE, FALSE, 0);
-			return TRUE;
-		}
-		break;
-	case NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_NO_DEFAULT:
-		if (   nmp_object_is_visible (obj)
-		    && !NM_PLATFORM_IP_ROUTE_IS_DEFAULT (&obj->ip_route)) {
-			nm_assert (obj->object.ifindex > 0);
-			*out_id = nmp_cache_id_init_routes_visible (id, NMP_OBJECT_GET_TYPE (obj), FALSE, TRUE, obj->object.ifindex);
-			return TRUE;
-		}
-		break;
-	case NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_ONLY_DEFAULT:
-		if (   nmp_object_is_visible (obj)
-		    && NM_PLATFORM_IP_ROUTE_IS_DEFAULT (&obj->ip_route)) {
-			nm_assert (obj->object.ifindex > 0);
-			*out_id = nmp_cache_id_init_routes_visible (id, NMP_OBJECT_GET_TYPE (obj), TRUE, FALSE, obj->object.ifindex);
-			return TRUE;
-		}
-		break;
-	case NMP_CACHE_ID_TYPE_ROUTES_BY_DESTINATION_IP4:
-		if (NMP_OBJECT_GET_CLASS (obj)->obj_type == NMP_OBJECT_TYPE_IP4_ROUTE) {
-			*out_id = nmp_cache_id_init_routes_by_destination_ip4 (id, obj->ip4_route.network, obj->ip_route.plen, obj->ip_route.metric);
-			return TRUE;
-		}
-		return FALSE;
-	case NMP_CACHE_ID_TYPE_ROUTES_BY_DESTINATION_IP6:
-		if (NMP_OBJECT_GET_CLASS (obj)->obj_type == NMP_OBJECT_TYPE_IP6_ROUTE) {
-			*out_id = nmp_cache_id_init_routes_by_destination_ip6 (id, &obj->ip6_route.network, obj->ip_route.plen, obj->ip_route.metric);
-			return TRUE;
-		}
-		return FALSE;
-	default:
-		return FALSE;
-	}
-	*out_id = NULL;
-	return TRUE;
-}
-
 /*****************************************************************************/
 
 static NMDedupMultiObj *
@@ -1368,6 +1424,18 @@ _vt_dedup_obj_full_equal (const NMDedupMultiObj *obj_a,
 
 /*****************************************************************************/
 
+static NMDedupMultiIdxType *
+_idx_type_get (const NMPCache *cache, NMPCacheIdType cache_id_type)
+{
+	nm_assert (cache);
+	nm_assert (cache_id_type > NMP_CACHE_ID_TYPE_NONE);
+	nm_assert (cache_id_type <= NMP_CACHE_ID_TYPE_MAX);
+	nm_assert ((int) cache_id_type - 1 >= 0);
+	nm_assert ((int) cache_id_type - 1 < G_N_ELEMENTS (cache->idx_types));
+
+	return (NMDedupMultiIdxType *) &cache->idx_types[cache_id_type - 1];
+}
+
 gboolean
 nmp_cache_use_udev_get (const NMPCache *cache)
 {
@@ -1402,9 +1470,7 @@ nmp_cache_use_udev_get (const NMPCache *cache)
 gboolean
 nmp_cache_link_connected_needs_toggle (const NMPCache *cache, const NMPObject *master, const NMPObject *potential_slave, const NMPObject *ignore_slave)
 {
-	const NMPlatformLink *const *links;
 	gboolean is_lower_up = FALSE;
-	guint len, i;
 
 	if (   !master
 	    || NMP_OBJECT_GET_TYPE (master) != NMP_OBJECT_TYPE_LINK
@@ -1428,15 +1494,16 @@ nmp_cache_link_connected_needs_toggle (const NMPCache *cache, const NMPObject *m
 	    && potential_slave->link.connected) {
 		is_lower_up = TRUE;
 	} else {
-		NMPCacheId cache_id;
-
-		links = (const NMPlatformLink *const *) nmp_cache_lookup_multi (cache, nmp_cache_id_init_object_type (&cache_id, NMP_OBJECT_TYPE_LINK, FALSE), &len);
-		for (i = 0; i < len; i++) {
-			const NMPlatformLink *link = links[i];
+		NMPLookup lookup;
+		NMDedupMultiIter iter;
+		const NMPlatformLink *link = NULL;
+
+		nmp_cache_iter_for_each_link (&iter,
+		                              nmp_cache_lookup (cache,
+		                                                nmp_lookup_init_link (&lookup, FALSE)),
+		                              &link) {
 			const NMPObject *obj = NMP_OBJECT_UP_CAST ((NMPlatformObject *) link);
 
-			nm_assert (NMP_OBJECT_GET_TYPE (NMP_OBJECT_UP_CAST ((NMPlatformObject *) link)) == NMP_OBJECT_TYPE_LINK);
-
 			if (   (!potential_slave || potential_slave->link.ifindex != link->ifindex)
 			    && ignore_slave != obj
 			    && link->ifindex > 0
@@ -1485,40 +1552,40 @@ nmp_cache_link_connected_needs_toggle_by_ifindex (const NMPCache *cache, int mas
 
 /*****************************************************************************/
 
-const NMPlatformObject *const *
-nmp_cache_lookup_multi (const NMPCache *cache, const NMPCacheId *cache_id, guint *out_len)
+static const NMDedupMultiEntry *
+_lookup_obj (const NMPCache *cache, const NMPObject *obj)
 {
-	return (const NMPlatformObject *const *) nm_multi_index_lookup (cache->idx_multi,
-	                                                                (const NMMultiIndexId *) cache_id,
-	                                                                out_len);
+	nm_assert (cache);
+	nm_assert (NMP_OBJECT_IS_VALID (obj));
+
+	return nm_dedup_multi_index_lookup_obj (cache->multi_idx,
+	                                        _idx_type_get (cache, NMP_CACHE_ID_TYPE_OBJECT_TYPE),
+	                                        obj);
 }
 
-GArray *
-nmp_cache_lookup_multi_to_array (const NMPCache *cache, NMPObjectType obj_type, const NMPCacheId *cache_id)
+const NMPObject *
+nmp_cache_lookup_obj (const NMPCache *cache, const NMPObject *obj)
 {
-	const NMPClass *klass = nmp_class_from_type (obj_type);
-	guint len, i;
-	const NMPlatformObject *const *objects;
-	GArray *array;
-
-	g_return_val_if_fail (klass, NULL);
+	const NMDedupMultiEntry *entry;
 
-	objects = nmp_cache_lookup_multi (cache, cache_id, &len);
-	array = g_array_sized_new (FALSE, FALSE, klass->sizeof_public, len);
+	g_return_val_if_fail (cache, NULL);
+	g_return_val_if_fail (obj, NULL);
 
-	for (i = 0; i < len; i++) {
-		nm_assert (NMP_OBJECT_GET_CLASS (NMP_OBJECT_UP_CAST (objects[i])) == klass);
-		g_array_append_vals (array, objects[i], 1);
-	}
-	return array;
+	entry = _lookup_obj (cache, obj);
+	return entry ? entry->box->obj : NULL;
 }
 
-const NMPObject *
-nmp_cache_lookup_obj (const NMPCache *cache, const NMPObject *obj)
+const NMDedupMultiEntry *
+nmp_cache_lookup_entry_link (const NMPCache *cache, int ifindex)
 {
-	g_return_val_if_fail (obj, NULL);
+	NMPObject obj_needle;
 
-	return g_hash_table_lookup (cache->idx_main, obj);
+	nm_assert (cache);
+
+	nmp_object_stackinit_id_link (&obj_needle, ifindex);
+	return nm_dedup_multi_index_lookup_obj (cache->multi_idx,
+	                                        _idx_type_get (cache, NMP_CACHE_ID_TYPE_OBJECT_TYPE),
+	                                        &obj_needle);
 }
 
 const NMPObject *
@@ -1529,6 +1596,228 @@ nmp_cache_lookup_link (const NMPCache *cache, int ifindex)
 	return nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&obj_needle, ifindex));
 }
 
+/*****************************************************************************/
+
+const NMDedupMultiHeadEntry *
+nmp_cache_lookup_all (const NMPCache *cache,
+                      NMPCacheIdType cache_id_type,
+                      const NMPObject *select_obj)
+{
+	nm_assert (cache);
+	nm_assert (NMP_OBJECT_IS_VALID (select_obj));
+
+	return nm_dedup_multi_index_lookup_head (cache->multi_idx,
+	                                         _idx_type_get (cache, cache_id_type),
+	                                         select_obj);
+}
+
+static const NMPLookup *
+_L (const NMPLookup *lookup)
+{
+#if NM_MORE_ASSERTS
+	DedupMultiIdxType idx_type;
+
+	nm_assert (lookup);
+	_dedup_multi_idx_type_init (&idx_type, lookup->cache_id_type);
+	nm_assert (idx_type.parent.klass->idx_obj_partitionable  ((NMDedupMultiIdxType *) &idx_type, (NMDedupMultiObj *) &lookup->selector_obj));
+	nm_assert (idx_type.parent.klass->idx_obj_partition_hash ((NMDedupMultiIdxType *) &idx_type, (NMDedupMultiObj *) &lookup->selector_obj) > 0);
+#endif
+	return lookup;
+}
+
+const NMPLookup *
+nmp_lookup_init_obj_type (NMPLookup *lookup,
+                          NMPObjectType obj_type,
+                          gboolean visible_only)
+{
+	NMPObject *o;
+
+	nm_assert (lookup);
+
+	switch (obj_type) {
+	case NMP_OBJECT_TYPE_LINK:
+	case NMP_OBJECT_TYPE_IP4_ADDRESS:
+	case NMP_OBJECT_TYPE_IP6_ADDRESS:
+	case NMP_OBJECT_TYPE_IP4_ROUTE:
+	case NMP_OBJECT_TYPE_IP6_ROUTE:
+		o = _nmp_object_stackinit_from_type (&lookup->selector_obj, obj_type);
+		if (visible_only) {
+			lookup->cache_id_type = NMP_CACHE_ID_TYPE_OBJECT_TYPE_VISIBLE_ONLY;
+			o->object.ifindex = 1;
+			if (obj_type == NMP_OBJECT_TYPE_LINK) {
+				o->_link.netlink.is_in_netlink = TRUE;
+				o->link.name[0] = 'x';
+			}
+		} else {
+			lookup->cache_id_type = NMP_CACHE_ID_TYPE_OBJECT_TYPE;
+		}
+		return _L (lookup);
+	default:
+		nm_assert_not_reached ();
+		return NULL;
+	}
+}
+
+const NMPLookup *
+nmp_lookup_init_link (NMPLookup *lookup,
+                      gboolean visible_only)
+{
+	return nmp_lookup_init_obj_type (lookup,
+	                                 NMP_OBJECT_TYPE_LINK,
+	                                 visible_only);
+}
+
+const NMPLookup *
+nmp_lookup_init_link_by_ifname (NMPLookup *lookup,
+                                const char *ifname)
+{
+	NMPObject *o;
+
+	nm_assert (lookup);
+	nm_assert (ifname);
+	nm_assert (strlen (ifname) < IFNAMSIZ);
+
+	o = _nmp_object_stackinit_from_type (&lookup->selector_obj, NMP_OBJECT_TYPE_LINK);
+	if (g_strlcpy (o->link.name, ifname, sizeof (o->link.name)) >= sizeof (o->link.name))
+		g_return_val_if_reached (NULL);
+	lookup->cache_id_type = NMP_CACHE_ID_TYPE_LINK_BY_IFNAME;
+	return _L (lookup);
+}
+
+const NMPLookup *
+nmp_lookup_init_addrroute (NMPLookup *lookup,
+                           NMPObjectType obj_type,
+                           int ifindex,
+                           gboolean visible_only)
+{
+	NMPObject *o;
+
+	nm_assert (lookup);
+	nm_assert (NM_IN_SET (obj_type, NMP_OBJECT_TYPE_IP4_ADDRESS,
+	                                NMP_OBJECT_TYPE_IP6_ADDRESS,
+	                                NMP_OBJECT_TYPE_IP4_ROUTE,
+	                                NMP_OBJECT_TYPE_IP6_ROUTE));
+
+	if (ifindex <= 0) {
+		return nmp_lookup_init_obj_type (lookup,
+		                                 obj_type,
+		                                 visible_only);
+	}
+
+	if (!visible_only) {
+		/* some match combinations are not implemented, as they would require
+		 * an additional index which is expensive to maintain. */
+		g_return_val_if_reached (NULL);
+	}
+
+	o = _nmp_object_stackinit_from_type (&lookup->selector_obj, obj_type);
+	o->object.ifindex = ifindex;
+	lookup->cache_id_type = NMP_CACHE_ID_TYPE_ADDRROUTE_VISIBLE_BY_IFINDEX;
+	return _L (lookup);
+}
+
+const NMPLookup *
+nmp_lookup_init_route_visible (NMPLookup *lookup,
+                               NMPObjectType obj_type,
+                               int ifindex,
+                               gboolean with_default,
+                               gboolean with_non_default)
+{
+	NMPObject *o;
+
+	nm_assert (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);
+		}
+		if (ifindex <= 0)
+			g_return_val_if_reached (NULL);
+		o = _nmp_object_stackinit_from_type (&lookup->selector_obj, obj_type);
+		o->object.ifindex = ifindex;
+		lookup->cache_id_type = NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_ONLY_DEFAULT;
+		return _L (lookup);
+	} else if (with_non_default) {
+		if (ifindex <= 0)
+			g_return_val_if_reached (NULL);
+		o = _nmp_object_stackinit_from_type (&lookup->selector_obj, obj_type);
+		o->object.ifindex = ifindex;
+		o->ip_route.plen = 1;
+		lookup->cache_id_type = NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_NO_DEFAULT;
+		return _L (lookup);
+	} else
+		g_return_val_if_reached (NULL);
+}
+
+const NMPLookup *
+nmp_lookup_init_route_by_dest (NMPLookup *lookup,
+                               int addr_family,
+                               gconstpointer network,
+                               guint plen,
+                               guint32 metric)
+{
+	NMPObject *o;
+
+	nm_assert (lookup);
+
+	switch (addr_family) {
+	case AF_INET:
+		o = _nmp_object_stackinit_from_type (&lookup->selector_obj, NMP_OBJECT_TYPE_IP4_ROUTE);
+		o->object.ifindex = 1;
+		o->ip_route.plen = plen;
+		o->ip_route.metric = metric;
+		if (network)
+			o->ip4_route.network = *((in_addr_t *) network);
+		lookup->cache_id_type = NMP_CACHE_ID_TYPE_ROUTES_BY_DESTINATION_IP4;
+		break;
+	case AF_INET6:
+		o = _nmp_object_stackinit_from_type (&lookup->selector_obj, NMP_OBJECT_TYPE_IP6_ROUTE);
+		o->object.ifindex = 1;
+		o->ip_route.plen = plen;
+		o->ip_route.metric = metric;
+		if (network)
+			o->ip6_route.network = *((struct in6_addr *) network);
+		lookup->cache_id_type = NMP_CACHE_ID_TYPE_ROUTES_BY_DESTINATION_IP6;
+		break;
+	default:
+		nm_assert_not_reached ();
+		return NULL;
+	}
+	return _L (lookup);
+}
+
+/*****************************************************************************/
+
+GArray *
+nmp_cache_lookup_to_array (const NMDedupMultiHeadEntry *head_entry,
+                           NMPObjectType obj_type)
+{
+	const NMPClass *klass = nmp_class_from_type (obj_type);
+	NMDedupMultiIter iter;
+	const NMPObject *o;
+	GArray *array;
+
+	g_return_val_if_fail (klass, NULL);
+
+	array = g_array_sized_new (FALSE, FALSE,
+	                           klass->sizeof_public,
+	                           head_entry ? head_entry->len : 0);
+	nmp_cache_iter_for_each (&iter,
+	                         head_entry,
+	                         &o) {
+		nm_assert (NMP_OBJECT_GET_CLASS (o) == klass);
+		g_array_append_vals (array, &o->object, 1);
+	}
+	return array;
+}
+
+/*****************************************************************************/
+
 /**
  * nmp_cache_find_other_route_for_same_destination:
  * @cache:
@@ -1544,32 +1833,36 @@ nmp_cache_lookup_link (const NMPCache *cache, int ifindex)
 const NMPObject *
 nmp_cache_find_other_route_for_same_destination (const NMPCache *cache, const NMPObject *route)
 {
-	NMPCacheId cache_id;
-	const NMPlatformObject *const *list;
+	NMPLookup lookup;
+	NMDedupMultiIter iter;
+	const NMPObject *o = NULL;
 
 	nm_assert (cache);
 
 	switch (NMP_OBJECT_GET_TYPE (route)) {
 	case NMP_OBJECT_TYPE_IP4_ROUTE:
-		nmp_cache_id_init_routes_by_destination_ip4 (&cache_id, route->ip4_route.network, route->ip_route.plen, route->ip_route.metric);
+		nmp_lookup_init_route_by_dest (&lookup,
+		                               AF_INET,
+		                               &route->ip4_route.network,
+		                               route->ip_route.plen,
+		                               route->ip_route.metric);
 		break;
 	case NMP_OBJECT_TYPE_IP6_ROUTE:
-		nmp_cache_id_init_routes_by_destination_ip6 (&cache_id, &route->ip6_route.network, route->ip_route.plen, route->ip_route.metric);
+		nmp_lookup_init_route_by_dest (&lookup,
+		                               AF_INET6,
+		                               &route->ip6_route.network,
+		                               route->ip_route.plen,
+		                               route->ip_route.metric);
 		break;
 	default:
 		g_return_val_if_reached (NULL);
 	}
 
-	list = nmp_cache_lookup_multi (cache, &cache_id, NULL);
-	if (list) {
-		for (; *list; list++) {
-			const NMPObject *candidate = NMP_OBJECT_UP_CAST (*list);
+	nmp_cache_iter_for_each (&iter, nmp_cache_lookup (cache, &lookup), &o) {
+		nm_assert (NMP_OBJECT_GET_CLASS (route) == NMP_OBJECT_GET_CLASS (o));
 
-			nm_assert (NMP_OBJECT_GET_CLASS (route) == NMP_OBJECT_GET_CLASS (candidate));
-
-			if (!nmp_object_id_equal (route, candidate))
-				return candidate;
-		}
+		if (!nmp_object_id_equal (route, o))
+			return o;
 	}
 	return NULL;
 }
@@ -1585,9 +1878,10 @@ nmp_cache_lookup_link_full (const NMPCache *cache,
 {
 	NMPObject obj_needle;
 	const NMPObject *obj;
-	const NMPlatformObject *const *list;
-	guint i, len;
-	NMPCacheId cache_id, *p_cache_id;
+	NMDedupMultiIter iter;
+	const NMDedupMultiHeadEntry *head_entry;
+	const NMPlatformLink *link = NULL;
+	NMPLookup lookup;
 
 	if (ifindex > 0) {
 		obj = nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&obj_needle, ifindex));
@@ -1602,18 +1896,19 @@ nmp_cache_lookup_link_full (const NMPCache *cache,
 	} else if (!ifname && !match_fn)
 		return NULL;
 	else {
-		if (   ifname
-		    && strlen (ifname) <= sizeof (cache_id.link_by_ifname.ifname_short)) {
-			p_cache_id = nmp_cache_id_init_link_by_ifname (&cache_id, ifname);
+		if (ifname) {
+			if (strlen (ifname) >= IFNAMSIZ || !ifname[0])
+				g_return_val_if_reached (NULL);
+			nmp_lookup_init_link_by_ifname (&lookup, ifname);
 			ifname = NULL;
 		} else {
-			p_cache_id = nmp_cache_id_init_object_type (&cache_id, NMP_OBJECT_TYPE_LINK, visible_only);
+			nmp_lookup_init_link (&lookup, visible_only);
 			visible_only = FALSE;
 		}
 
-		list = nmp_cache_lookup_multi (cache, p_cache_id, &len);
-		for (i = 0; i < len; i++) {
-			obj = NMP_OBJECT_UP_CAST (list[i]);
+		head_entry = nmp_cache_lookup (cache, &lookup);
+		nmp_cache_iter_for_each_link (&iter, head_entry, &link) {
+			obj = NMP_OBJECT_UP_CAST (link);
 
 			if (visible_only && !nmp_object_is_visible (obj))
 				continue;
@@ -1631,22 +1926,19 @@ nmp_cache_lookup_link_full (const NMPCache *cache,
 }
 
 GHashTable *
-nmp_cache_lookup_all_to_hash (const NMPCache *cache,
-                              NMPCacheId *cache_id,
-                              GHashTable *hash)
+nmp_cache_lookup_to_hash (const NMDedupMultiHeadEntry *head_entry,
+                          GHashTable *hash)
 {
-	NMMultiIndexIdIter iter;
-	gpointer plobj;
-
-	nm_multi_index_id_iter_init (&iter, cache->idx_multi, (const NMMultiIndexId *) cache_id);
+	NMDedupMultiIter iter;
+	const NMPObject *o = NULL;
 
-	if (nm_multi_index_id_iter_next (&iter, &plobj)) {
+	nm_dedup_multi_iter_init (&iter, head_entry);
+	if (nmp_cache_iter_next (&iter, &o)) {
 		if (!hash)
 			hash = g_hash_table_new_full (NULL, NULL, (GDestroyNotify) nmp_object_unref, NULL);
-
 		do {
-			g_hash_table_add (hash, nmp_object_ref (NMP_OBJECT_UP_CAST (plobj)));
-		} while (nm_multi_index_id_iter_next (&iter, &plobj));
+			g_hash_table_add (hash, (NMPObject *) nmp_object_ref (o));
+		} while (nmp_cache_iter_next (&iter, &o));
 	}
 
 	return hash;
@@ -1655,165 +1947,261 @@ nmp_cache_lookup_all_to_hash (const NMPCache *cache,
 /*****************************************************************************/
 
 static void
-_nmp_cache_update_cache (NMPCache *cache, NMPObject *obj, gboolean remove)
-{
-	const guint8 *id_type;
-
-	for (id_type = NMP_OBJECT_GET_CLASS (obj)->supported_cache_ids; *id_type; id_type++) {
-		NMPCacheId cache_id_storage;
-		const NMPCacheId *cache_id;
-
-		if (!_nmp_object_init_cache_id (obj, *id_type, &cache_id_storage, &cache_id))
-			continue;
-		if (!cache_id)
-			continue;
-
-		/* We don't put @obj itself into the multi index, but &obj->object. As of now, all
-		 * users expect a pointer to NMPlatformObject, not NMPObject.
-		 * You can use NMP_OBJECT_UP_CAST() to retrieve the original @obj pointer.
-		 *
-		 * If need be, we could determine based on @id_type which pointer we want to store. */
-
-		if (remove) {
-			if (!nm_multi_index_remove (cache->idx_multi, &cache_id->base, &obj->object))
-				g_assert_not_reached ();
+_idxcache_update_box_move (NMPCache *cache,
+                           NMPCacheIdType cache_id_type,
+                           const NMDedupMultiBox *box_old,
+                           const NMDedupMultiBox *box_new)
+{
+	const NMDedupMultiEntry *entry_new;
+	const NMDedupMultiEntry *entry_old;
+	const NMDedupMultiEntry *entry_order;
+	NMDedupMultiIdxType *idx_type;
+	const NMPObject *new, *old;
+
+	new = box_new ? box_new->obj : NULL;
+	old = box_old ? box_old->obj : NULL;
+
+	nm_assert (new || old);
+	nm_assert (!new || NMP_OBJECT_GET_TYPE (new) != NMP_OBJECT_TYPE_UNKNOWN);
+	nm_assert (!old || NMP_OBJECT_GET_TYPE (old) != NMP_OBJECT_TYPE_UNKNOWN);
+	nm_assert (!old || !new || NMP_OBJECT_GET_CLASS (new) == NMP_OBJECT_GET_CLASS (old));
+	nm_assert (!old || !new || !nmp_object_equal (new, old));
+	nm_assert (!box_new || box_new == nm_dedup_multi_box_find (cache->multi_idx, new));
+	nm_assert (!box_old || box_old == nm_dedup_multi_box_find (cache->multi_idx, old));
+
+	idx_type = _idx_type_get (cache, cache_id_type);
+
+	if (old) {
+		entry_old = nm_dedup_multi_index_lookup_obj (cache->multi_idx,
+		                                             idx_type,
+		                                             old);
+		if (!new) {
+			if (entry_old)
+				nm_dedup_multi_index_remove_entry (cache->multi_idx, entry_old);
+			return;
+		}
+	} else
+		entry_old = NULL;
+
+	if (new) {
+		if (   old
+		    && nm_dedup_multi_idx_type_id_equal (idx_type, old, new)
+		    && nm_dedup_multi_idx_type_partition_equal (idx_type, old, new)) {
+			/* optimize. We just looked up the @old entry and @new compares equal
+			 * according to idx_obj_id_equal(). entry_new is the same as entry_old. */
+			entry_new = entry_old;
 		} else {
-			if (!nm_multi_index_add (cache->idx_multi, &cache_id->base, &obj->object))
-				g_assert_not_reached ();
+			entry_new = nm_dedup_multi_index_lookup_obj (cache->multi_idx,
+			                                             idx_type,
+			                                             new);
 		}
-	}
-}
 
-static void
-_nmp_cache_update_add (NMPCache *cache, NMPObject *obj)
-{
-	nm_assert (!obj->is_cached);
-	nmp_object_ref (obj);
-	nm_assert (!nm_multi_index_lookup_first_by_value (cache->idx_multi, &obj->object));
-	if (!nm_g_hash_table_add (cache->idx_main, obj))
-		g_assert_not_reached ();
-	obj->is_cached = TRUE;
-	_nmp_cache_update_cache (cache, obj, FALSE);
-}
+		if (entry_new)
+			entry_order = entry_new;
+		else if (   entry_old
+		         && nm_dedup_multi_idx_type_partition_equal (idx_type, entry_old->box->obj, new))
+			entry_order = entry_old;
+		else
+			entry_order = NULL;
+		nm_dedup_multi_index_add_full (cache->multi_idx,
+		                               idx_type,
+		                               new,
+		                               NM_DEDUP_MULTI_IDX_MODE_APPEND,
+		                               entry_order,
+		                               entry_new ?: NM_DEDUP_MULTI_ENTRY_MISSING,
+		                               entry_new ? entry_new->head : (entry_order ? entry_order->head : NULL),
+		                               box_new,
+		                               &entry_new,
+		                               NULL);
 
-static void
-_nmp_cache_update_remove (NMPCache *cache, NMPObject *obj)
-{
-	nm_assert (obj->is_cached);
-	_nmp_cache_update_cache (cache, obj, TRUE);
-	obj->is_cached = FALSE;
-	if (!g_hash_table_remove (cache->idx_main, obj))
-		g_assert_not_reached ();
+#if NM_MORE_ASSERTS
+		if (entry_new) {
+			nm_assert (idx_type->klass->idx_obj_partitionable);
+			nm_assert (idx_type->klass->idx_obj_partition_equal);
+			nm_assert (idx_type->klass->idx_obj_partitionable (idx_type, entry_new->box->obj));
+			nm_assert (idx_type->klass->idx_obj_partition_equal (idx_type, (gpointer) new, entry_new->box->obj));
+		}
+#endif
+	} else
+		entry_new = NULL;
 
-	/* @obj is possibly a dangling pointer at this point. No problem, multi-index doesn't dereference. */
-	nm_assert (!nm_multi_index_lookup_first_by_value (cache->idx_multi, &obj->object));
+	if (   entry_old
+	    && entry_old != entry_new)
+		nm_dedup_multi_index_remove_entry (cache->multi_idx, entry_old);
 }
 
 static void
-_nmp_cache_update_update (NMPCache *cache, NMPObject *obj, const NMPObject *new)
+_idxcache_update (NMPCache *cache,
+                  const NMDedupMultiEntry *entry_old,
+                  NMPObject *obj_new,
+                  const NMDedupMultiEntry **out_entry_new)
 {
-	const guint8 *id_type;
+	const NMPClass *klass;
+	const guint8 *i_idx_type;
+	NMDedupMultiIdxType *idx_type_o = _idx_type_get (cache, NMP_CACHE_ID_TYPE_OBJECT_TYPE);
+	const NMDedupMultiEntry *entry_new = NULL;
+	const NMDedupMultiBox *box_old;
+	const NMDedupMultiBox *box_old2 = NULL;
 
-	nm_assert (NMP_OBJECT_GET_CLASS (obj) == NMP_OBJECT_GET_CLASS (new));
-	nm_assert (obj->is_cached);
-	nm_assert (!new->is_cached);
+	/* we update an object in the cache.
+	 *
+	 * Note that @entry_old MUST be what is currently tracked in multi_idx, and it must
+	 * have the same ID as @obj_new. */
 
-	for (id_type = NMP_OBJECT_GET_CLASS (obj)->supported_cache_ids; *id_type; id_type++) {
-		NMPCacheId cache_id_storage_obj, cache_id_storage_new;
-		const NMPCacheId *cache_id_obj, *cache_id_new;
+	nm_assert (cache);
+	nm_assert (entry_old || obj_new);
+	nm_assert (!obj_new || nmp_object_is_alive (obj_new));
+	nm_assert (!entry_old || entry_old == nm_dedup_multi_index_lookup_obj (cache->multi_idx, idx_type_o, entry_old->box->obj));
+	nm_assert (!obj_new || entry_old == nm_dedup_multi_index_lookup_obj (cache->multi_idx, idx_type_o, obj_new));
+	nm_assert (!entry_old || entry_old->head->idx_type == idx_type_o);
+	nm_assert (   !entry_old
+	           || !obj_new
+	           || nm_dedup_multi_idx_type_partition_equal (idx_type_o, entry_old->box->obj, obj_new));
+	nm_assert (   !entry_old
+	           || !obj_new
+	           || nm_dedup_multi_idx_type_id_equal (idx_type_o, entry_old->box->obj, obj_new));
+	nm_assert (   !entry_old
+	           || !obj_new
+	           || (   obj_new->parent.klass == ((const NMPObject *) entry_old->box->obj)->parent.klass
+	               && !obj_new->parent.klass->obj_full_equal ((NMDedupMultiObj *) obj_new, entry_old->box->obj)));
+
+	/* keep a boxed reference to the pre-existing entry */
+	box_old = entry_old ? nm_dedup_multi_box_ref (entry_old->box) : NULL;
+
+	/* first update the main index NMP_CACHE_ID_TYPE_OBJECT_TYPE.
+	 * We already know the pre-existing @entry old, so all that
+	 * nm_dedup_multi_index_add_full() effectively does, is update the
+	 * obj reference.
+	 *
+	 * We also get the new boxed object, which we need below. */
+	if (obj_new) {
+		nm_dedup_multi_index_add_full (cache->multi_idx,
+		                               idx_type_o,
+		                               obj_new,
+		                               NM_DEDUP_MULTI_IDX_MODE_APPEND,
+		                               NULL,
+		                               entry_old ?: NM_DEDUP_MULTI_ENTRY_MISSING,
+		                               NULL,
+		                               NULL,
+		                               &entry_new,
+		                               &box_old2);
+		nm_assert (entry_new);
+		nm_assert (box_old == box_old2);
+		nm_assert (!entry_old || entry_old == entry_new);
+		if (box_old2)
+			nm_dedup_multi_box_unref (cache->multi_idx, box_old2);
+	} else
+		nm_dedup_multi_index_remove_entry (cache->multi_idx, entry_old);
 
-		if (!_nmp_object_init_cache_id (obj, *id_type, &cache_id_storage_obj, &cache_id_obj))
+	/* now update all other indexes. We know the previously boxed entry, and the
+	 * newly boxed one. */
+	klass = NMP_OBJECT_GET_CLASS (entry_new ? entry_new->box->obj : box_old->obj);
+	for (i_idx_type = klass->supported_cache_ids; *i_idx_type; i_idx_type++) {
+		NMPCacheIdType id_type = *i_idx_type;
+
+		if (id_type == NMP_CACHE_ID_TYPE_OBJECT_TYPE)
 			continue;
-		if (!_nmp_object_init_cache_id (new, *id_type, &cache_id_storage_new, &cache_id_new))
-			g_assert_not_reached ();
-		if (!nm_multi_index_move (cache->idx_multi, (NMMultiIndexId *) cache_id_obj, (NMMultiIndexId *) cache_id_new, &obj->object))
-			g_assert_not_reached ();
+		_idxcache_update_box_move (cache, id_type,
+		                           box_old,
+		                           entry_new ? entry_new->box : NULL);
 	}
-	nmp_object_copy (obj, new, FALSE);
+
+	NM_SET_OUT (out_entry_new, entry_new);
+
+	if (box_old)
+		nm_dedup_multi_box_unref (cache->multi_idx, box_old);
 }
 
 NMPCacheOpsType
-nmp_cache_remove (NMPCache *cache, const NMPObject *obj, gboolean equals_by_ptr, NMPObject **out_obj, gboolean *out_was_visible, NMPCachePreHook pre_hook, gpointer user_data)
+nmp_cache_remove (NMPCache *cache,
+                  const NMPObject *obj_needle,
+                  gboolean equals_by_ptr,
+                  const NMPObject **out_obj_old)
 {
-	NMPObject *old;
+	const NMDedupMultiEntry *entry_old;
+	const NMPObject *obj_old;
 
-	nm_assert (NMP_OBJECT_IS_VALID (obj));
+	entry_old = _lookup_obj (cache, obj_needle);
 
-	old = g_hash_table_lookup (cache->idx_main, obj);
-	if (!old) {
-		if (out_obj)
-			*out_obj = NULL;
-		if (out_was_visible)
-			*out_was_visible = FALSE;
+	if (!entry_old) {
+		NM_SET_OUT (out_obj_old, NULL);
 		return NMP_CACHE_OPS_UNCHANGED;
 	}
 
-	if (out_obj)
-		*out_obj = nmp_object_ref (old);
-	if (out_was_visible)
-		*out_was_visible = nmp_object_is_visible (old);
-	if (equals_by_ptr && old != obj) {
+	obj_old = entry_old->box->obj;
+
+	NM_SET_OUT (out_obj_old, nmp_object_ref (obj_old));
+
+	if (   equals_by_ptr
+	    && obj_old != obj_needle) {
 		/* We found an identical object, but we only delete it if it's the same pointer as
-		 * @obj. */
+		 * @obj_needle. */
 		return NMP_CACHE_OPS_UNCHANGED;
 	}
-	if (pre_hook)
-		pre_hook (cache, old, NULL, NMP_CACHE_OPS_REMOVED, user_data);
-	_nmp_cache_update_remove (cache, old);
+	_idxcache_update (cache, entry_old, NULL, NULL);
 	return NMP_CACHE_OPS_REMOVED;
 }
 
 NMPCacheOpsType
-nmp_cache_remove_netlink (NMPCache *cache, const NMPObject *obj_needle, NMPObject **out_obj, gboolean *out_was_visible, NMPCachePreHook pre_hook, gpointer user_data)
+nmp_cache_remove_netlink (NMPCache *cache,
+                          const NMPObject *obj_needle,
+                          const NMPObject **out_obj_old,
+                          const NMPObject **out_obj_new)
 {
-	if (NMP_OBJECT_GET_TYPE (obj_needle) == NMP_OBJECT_TYPE_LINK) {
-		NMPObject *old;
-		nm_auto_nmpobj NMPObject *obj = NULL;
+	const NMDedupMultiEntry *entry_old;
+	const NMDedupMultiEntry *entry_new = NULL;
+	const NMPObject *obj_old;
+	NMPObject *obj_new;
+
+	entry_old = _lookup_obj (cache, obj_needle);
+
+	if (!entry_old) {
+		NM_SET_OUT (out_obj_old, NULL);
+		NM_SET_OUT (out_obj_new, NULL);
+		return NMP_CACHE_OPS_UNCHANGED;
+	}
 
+	obj_old = entry_old->box->obj;
+
+	if (NMP_OBJECT_GET_TYPE (obj_needle) == NMP_OBJECT_TYPE_LINK) {
 		/* For nmp_cache_remove_netlink() we have an incomplete @obj_needle instance to be
 		 * removed from netlink. Link objects are alive without being in netlink when they
 		 * have a udev-device. All we want to do in this case is clear the netlink.is_in_netlink
 		 * flag. */
 
-		old = (NMPObject *) nmp_cache_lookup_link (cache, obj_needle->link.ifindex);
-		if (!old) {
-			if (out_obj)
-				*out_obj = NULL;
-			if (out_was_visible)
-				*out_was_visible = FALSE;
-			return NMP_CACHE_OPS_UNCHANGED;
-		}
-
-		if (out_obj)
-			*out_obj = nmp_object_ref (old);
-		if (out_was_visible)
-			*out_was_visible = nmp_object_is_visible (old);
+		NM_SET_OUT (out_obj_old, nmp_object_ref (obj_old));
 
-		if (!old->_link.netlink.is_in_netlink) {
-			nm_assert (old->_link.udev.device);
+		if (!obj_old->_link.netlink.is_in_netlink) {
+			nm_assert (obj_old->_link.udev.device);
+			NM_SET_OUT (out_obj_new, nmp_object_ref (obj_old));
 			return NMP_CACHE_OPS_UNCHANGED;
 		}
 
-		if (!old->_link.udev.device) {
-			/* the update would make @old invalid. Remove it. */
-			if (pre_hook)
-				pre_hook (cache, old, NULL, NMP_CACHE_OPS_REMOVED, user_data);
-			_nmp_cache_update_remove (cache, old);
+		if (!obj_old->_link.udev.device) {
+			/* the update would make @obj_old invalid. Remove it. */
+			_idxcache_update (cache, entry_old, NULL, NULL);
+			NM_SET_OUT (out_obj_new, NULL);
 			return NMP_CACHE_OPS_REMOVED;
 		}
 
-		obj = nmp_object_clone (old, FALSE);
-		obj->_link.netlink.is_in_netlink = FALSE;
+		obj_new = nmp_object_clone (obj_old, FALSE);
+		obj_new->_link.netlink.is_in_netlink = FALSE;
 
-		_nmp_object_fixup_link_master_connected (obj, cache);
-		_nmp_object_fixup_link_udev_fields (obj, cache->use_udev);
+		_nmp_object_fixup_link_master_connected (&obj_new, NULL, cache);
+		_nmp_object_fixup_link_udev_fields (&obj_new, NULL, cache->use_udev);
 
-		if (pre_hook)
-			pre_hook (cache, old, obj, NMP_CACHE_OPS_UPDATED, user_data);
-		_nmp_cache_update_update (cache, old, obj);
+		_idxcache_update (cache,
+		                  entry_old,
+		                  obj_new,
+		                  &entry_new);
+		NM_SET_OUT (out_obj_new, nmp_object_ref (entry_new->box->obj));
 		return NMP_CACHE_OPS_UPDATED;
-	} else
-		return nmp_cache_remove (cache, obj_needle, FALSE, out_obj, out_was_visible, pre_hook, user_data);
+	}
+
+	NM_SET_OUT (out_obj_old, nmp_object_ref (obj_old));
+	NM_SET_OUT (out_obj_new, NULL);
+	_idxcache_update (cache, entry_old, NULL, NULL);
+	return NMP_CACHE_OPS_REMOVED;
 }
 
 /**
@@ -1841,233 +2229,246 @@ nmp_cache_remove_netlink (NMPCache *cache, const NMPObject *obj_needle, NMPObjec
  * Returns: how the cache changed.
  **/
 NMPCacheOpsType
-nmp_cache_update_netlink (NMPCache *cache, NMPObject *obj, NMPObject **out_obj, gboolean *out_was_visible, NMPCachePreHook pre_hook, gpointer user_data)
+nmp_cache_update_netlink (NMPCache *cache,
+                          NMPObject *obj_hand_over,
+                          const NMPObject **out_obj_old,
+                          const NMPObject **out_obj_new)
 {
-	NMPObject *old;
-
-	nm_assert (NMP_OBJECT_IS_VALID (obj));
-	nm_assert (!NMP_OBJECT_IS_STACKINIT (obj));
-	nm_assert (!obj->is_cached);
+	const NMDedupMultiEntry *entry_old;
+	const NMDedupMultiEntry *entry_new;
+	const NMPObject *obj_old;
+	nm_auto_nmpobj NMPObject *obj_new = NULL;
+	gboolean is_alive;
 
+	nm_assert (cache);
+	nm_assert (NMP_OBJECT_IS_VALID (obj_hand_over));
+	nm_assert (!NMP_OBJECT_IS_STACKINIT (obj_hand_over));
 	/* A link object from netlink must have the udev related fields unset.
 	 * We could implement to handle that, but there is no need to support such
 	 * a use-case */
-	nm_assert (NMP_OBJECT_GET_TYPE (obj) != NMP_OBJECT_TYPE_LINK ||
-	           (   !obj->_link.udev.device
-	            && !obj->link.driver));
+	nm_assert (NMP_OBJECT_GET_TYPE (obj_hand_over) != NMP_OBJECT_TYPE_LINK ||
+	           (   !obj_hand_over->_link.udev.device
+	            && !obj_hand_over->link.driver));
+	nm_assert (({
+	                const NMDedupMultiBox *_b = nm_dedup_multi_box_find (cache->multi_idx, obj_hand_over);
+	                !_b || obj_hand_over != _b->obj;
+	            }));
 
-	old = g_hash_table_lookup (cache->idx_main, obj);
+	entry_old = _lookup_obj (cache, obj_hand_over);
 
-	NM_SET_OUT (out_obj, NULL);
-	NM_SET_OUT (out_was_visible, FALSE);
+	if (!entry_old) {
 
-	if (!old) {
-		if (!nmp_object_is_alive (obj))
-			return NMP_CACHE_OPS_UNCHANGED;
+		NM_SET_OUT (out_obj_old, NULL);
 
-		if (NMP_OBJECT_GET_TYPE (obj) == NMP_OBJECT_TYPE_LINK) {
-			_nmp_object_fixup_link_master_connected (obj, cache);
-			_nmp_object_fixup_link_udev_fields (obj, cache->use_udev);
+		if (!nmp_object_is_alive (obj_hand_over)) {
+			NM_SET_OUT (out_obj_new, NULL);
+			return NMP_CACHE_OPS_UNCHANGED;
 		}
 
-		NM_SET_OUT (out_obj, nmp_object_ref (obj));
+		if (NMP_OBJECT_GET_TYPE (obj_hand_over) == NMP_OBJECT_TYPE_LINK) {
+			_nmp_object_fixup_link_master_connected (&obj_hand_over, NULL, cache);
+			_nmp_object_fixup_link_udev_fields (&obj_hand_over, NULL, cache->use_udev);
+		}
 
-		if (pre_hook)
-			pre_hook (cache, NULL, obj, NMP_CACHE_OPS_ADDED, user_data);
-		_nmp_cache_update_add (cache, obj);
+		_idxcache_update (cache,
+		                  entry_old,
+		                  obj_hand_over,
+		                  &entry_new);
+		NM_SET_OUT (out_obj_new, nmp_object_ref (entry_new->box->obj));
 		return NMP_CACHE_OPS_ADDED;
-	} else if (old == obj) {
-		/* updating a cached object inplace is not supported because the object contributes to hash-key
-		 * for NMMultiIndex. Modifying an object that is inside NMMultiIndex means that these
-		 * keys change.
-		 * The problem is, that for a given object NMMultiIndex does not support (efficient)
-		 * reverse lookup to get all the NMPCacheIds to which it belongs. If that would be implemented,
-		 * it would be possible to implement inplace-update.
-		 *
-		 * There is an un-optimized reverse lookup via nm_multi_index_iter_init(), but we don't want
-		 * that because we might have a large number of indexes to search.
-		 *
-		 * We could add efficient reverse lookup by adding a reverse index to NMMultiIndex. But that
-		 * also adds some cost to support an (uncommon?) usage pattern.
-		 *
-		 * Instead we just don't support it, instead we expect the user to
-		 * create a new instance from netlink.
-		 *
-		 * TL;DR: a cached object must never be modified.
-		 */
-		g_assert_not_reached ();
-	} else {
-		gboolean is_alive = FALSE;
-
-		nm_assert (old->is_cached);
-
-		if (NMP_OBJECT_GET_TYPE (obj) == NMP_OBJECT_TYPE_LINK) {
-			if (!obj->_link.netlink.is_in_netlink) {
-				if (!old->_link.netlink.is_in_netlink) {
-					nm_assert (old->_link.udev.device);
-					NM_SET_OUT (out_obj, nmp_object_ref (old));
-					NM_SET_OUT (out_was_visible, nmp_object_is_visible (old));
-					return NMP_CACHE_OPS_UNCHANGED;
-				}
-				if (old->_link.udev.device) {
-					/* @obj is not in netlink.
-					 *
-					 * This is similar to nmp_cache_remove_netlink(), but there we preserve the
-					 * preexisting netlink properties. The use case of that is when kernel_get_object()
-					 * cannot load an object (based on the id of a needle).
-					 *
-					 * Here we keep the data provided from @obj. The usecase is when receiving
-					 * a valid @obj instance from netlink with RTM_DELROUTE.
-					 */
-					is_alive = TRUE;
-				}
-			} else
-				is_alive = TRUE;
+	}
 
-			if (is_alive) {
-				_nmp_object_fixup_link_master_connected (obj, cache);
+	obj_old = entry_old->box->obj;
 
-				/* Merge the netlink parts with what we have from udev. */
-				udev_device_unref (obj->_link.udev.device);
-				obj->_link.udev.device = old->_link.udev.device ? udev_device_ref (old->_link.udev.device) : NULL;
-				_nmp_object_fixup_link_udev_fields (obj, cache->use_udev);
+	if (NMP_OBJECT_GET_TYPE (obj_hand_over) == NMP_OBJECT_TYPE_LINK) {
+		if (!obj_hand_over->_link.netlink.is_in_netlink) {
+			if (!obj_old->_link.netlink.is_in_netlink) {
+				nm_assert (obj_old->_link.udev.device);
+				NM_SET_OUT (out_obj_old, nmp_object_ref (obj_old));
+				NM_SET_OUT (out_obj_new, nmp_object_ref (obj_old));
+				return NMP_CACHE_OPS_UNCHANGED;
 			}
+			if (obj_old->_link.udev.device) {
+				/* @obj_hand_over is not in netlink.
+				 *
+				 * This is similar to nmp_cache_remove_netlink(), but there we preserve the
+				 * preexisting netlink properties. The use case of that is when kernel_get_object()
+				 * cannot load an object (based on the id of a needle).
+				 *
+				 * Here we keep the data provided from @obj_hand_over. The usecase is when receiving
+				 * a valid @obj_hand_over instance from netlink with RTM_DELROUTE.
+				 */
+				is_alive = TRUE;
+			} else
+				is_alive = FALSE;
 		} else
-			is_alive = nmp_object_is_alive (obj);
+			is_alive = TRUE;
 
-		NM_SET_OUT (out_obj, nmp_object_ref (old));
-		NM_SET_OUT (out_was_visible, nmp_object_is_visible (old));
+		if (is_alive) {
+			_nmp_object_fixup_link_master_connected (&obj_hand_over, NULL, cache);
 
-		if (!is_alive) {
-			/* the update would make @old invalid. Remove it. */
-			if (pre_hook)
-				pre_hook (cache, old, NULL, NMP_CACHE_OPS_REMOVED, user_data);
-			_nmp_cache_update_remove (cache, old);
-			return NMP_CACHE_OPS_REMOVED;
+			/* Merge the netlink parts with what we have from udev. */
+			udev_device_unref (obj_hand_over->_link.udev.device);
+			obj_hand_over->_link.udev.device = obj_old->_link.udev.device ? udev_device_ref (obj_old->_link.udev.device) : NULL;
+			_nmp_object_fixup_link_udev_fields (&obj_hand_over, NULL, cache->use_udev);
 		}
+	} else
+		is_alive = nmp_object_is_alive (obj_hand_over);
 
-		if (nmp_object_equal (old, obj))
-			return NMP_CACHE_OPS_UNCHANGED;
+	NM_SET_OUT (out_obj_old, nmp_object_ref (obj_old));
 
-		if (pre_hook)
-			pre_hook (cache, old, obj, NMP_CACHE_OPS_UPDATED, user_data);
-		_nmp_cache_update_update (cache, old, obj);
-		return NMP_CACHE_OPS_UPDATED;
+	if (!is_alive) {
+		/* the update would make @obj_old invalid. Remove it. */
+		_idxcache_update (cache, entry_old, NULL, NULL);
+		NM_SET_OUT (out_obj_new, NULL);
+		return NMP_CACHE_OPS_REMOVED;
+	}
+
+	if (nmp_object_equal (obj_old, obj_hand_over)) {
+		NM_SET_OUT (out_obj_new, nmp_object_ref (obj_old));
+		return NMP_CACHE_OPS_UNCHANGED;
 	}
+
+	_idxcache_update (cache,
+	                  entry_old,
+	                  obj_hand_over,
+	                  &entry_new);
+	NM_SET_OUT (out_obj_new, nmp_object_ref (entry_new->box->obj));
+	return NMP_CACHE_OPS_UPDATED;
 }
 
 NMPCacheOpsType
-nmp_cache_update_link_udev (NMPCache *cache, int ifindex, struct udev_device *udevice, NMPObject **out_obj, gboolean *out_was_visible, NMPCachePreHook pre_hook, gpointer user_data)
+nmp_cache_update_link_udev (NMPCache *cache,
+                            int ifindex,
+                            struct udev_device *udevice,
+                            const NMPObject **out_obj_old,
+                            const NMPObject **out_obj_new)
 {
-	NMPObject *old;
-	nm_auto_nmpobj NMPObject *obj = NULL;
+	const NMPObject *obj_old;
+	nm_auto_nmpobj NMPObject *obj_new = NULL;
+	const NMDedupMultiEntry *entry_old;
+	const NMDedupMultiEntry *entry_new;
 
-	old = (NMPObject *) nmp_cache_lookup_link (cache, ifindex);
+	entry_old = nmp_cache_lookup_entry_link (cache, ifindex);
 
-	NM_SET_OUT (out_obj, NULL);
-	NM_SET_OUT (out_was_visible, FALSE);
-
-	if (!old) {
-		if (!udevice)
+	if (!entry_old) {
+		if (!udevice) {
+			NM_SET_OUT (out_obj_old, NULL);
+			NM_SET_OUT (out_obj_new, NULL);
 			return NMP_CACHE_OPS_UNCHANGED;
+		}
 
-		obj = nmp_object_new (NMP_OBJECT_TYPE_LINK, NULL);
-		obj->link.ifindex = ifindex;
-		obj->_link.udev.device = udev_device_ref (udevice);
-
-		_nmp_object_fixup_link_udev_fields (obj, cache->use_udev);
-
-		nm_assert (nmp_object_is_alive (obj));
+		obj_new = nmp_object_new (NMP_OBJECT_TYPE_LINK, NULL);
+		obj_new->link.ifindex = ifindex;
+		obj_new->_link.udev.device = udev_device_ref (udevice);
 
-		if (out_obj)
-			*out_obj = nmp_object_ref (obj);
+		_nmp_object_fixup_link_udev_fields (&obj_new, NULL, cache->use_udev);
 
-		if (pre_hook)
-			pre_hook (cache, NULL, obj, NMP_CACHE_OPS_ADDED, user_data);
-		_nmp_cache_update_add (cache, obj);
+		_idxcache_update (cache,
+		                  NULL,
+		                  obj_new,
+		                  &entry_new);
+		NM_SET_OUT (out_obj_old, NULL);
+		NM_SET_OUT (out_obj_new, nmp_object_ref (entry_new->box->obj));
 		return NMP_CACHE_OPS_ADDED;
 	} else {
-		nm_assert (old->is_cached);
+		obj_old = entry_old->box->obj;
+		NM_SET_OUT (out_obj_old, nmp_object_ref (obj_old));
 
-		NM_SET_OUT (out_obj, nmp_object_ref (old));
-		NM_SET_OUT (out_was_visible, nmp_object_is_visible (old));
-
-		if (old->_link.udev.device == udevice)
+		if (obj_old->_link.udev.device == udevice) {
+			NM_SET_OUT (out_obj_new, nmp_object_ref (obj_old));
 			return NMP_CACHE_OPS_UNCHANGED;
+		}
 
-		if (!udevice && !old->_link.netlink.is_in_netlink) {
-			/* the update would make @old invalid. Remove it. */
-			if (pre_hook)
-				pre_hook (cache, old, NULL, NMP_CACHE_OPS_REMOVED, user_data);
-			_nmp_cache_update_remove (cache, old);
+		if (!udevice && !obj_old->_link.netlink.is_in_netlink) {
+			/* the update would make @obj_old invalid. Remove it. */
+			_idxcache_update (cache, entry_old, NULL, NULL);
+			NM_SET_OUT (out_obj_new, NULL);
 			return NMP_CACHE_OPS_REMOVED;
 		}
 
-		obj = nmp_object_clone (old, FALSE);
-
-		udev_device_unref (obj->_link.udev.device);
-		obj->_link.udev.device = udevice ? udev_device_ref (udevice) : NULL;
+		obj_new = nmp_object_clone (obj_old, FALSE);
 
-		_nmp_object_fixup_link_udev_fields (obj, cache->use_udev);
+		udev_device_unref (obj_new->_link.udev.device);
+		obj_new->_link.udev.device = udevice ? udev_device_ref (udevice) : NULL;
 
-		nm_assert (nmp_object_is_alive (obj));
+		_nmp_object_fixup_link_udev_fields (&obj_new, NULL, cache->use_udev);
 
-		if (pre_hook)
-			pre_hook (cache, old, obj, NMP_CACHE_OPS_UPDATED, user_data);
-		_nmp_cache_update_update (cache, old, obj);
+		_idxcache_update (cache,
+		                  entry_old,
+		                  obj_new,
+		                  &entry_new);
+		NM_SET_OUT (out_obj_new, nmp_object_ref (entry_new->box->obj));
 		return NMP_CACHE_OPS_UPDATED;
 	}
 }
 
 NMPCacheOpsType
-nmp_cache_update_link_master_connected (NMPCache *cache, int ifindex, NMPObject **out_obj, gboolean *out_was_visible, NMPCachePreHook pre_hook, gpointer user_data)
+nmp_cache_update_link_master_connected (NMPCache *cache,
+                                        int ifindex,
+                                        const NMPObject **out_obj_old,
+                                        const NMPObject **out_obj_new)
 {
-	NMPObject *old;
-	nm_auto_nmpobj NMPObject *obj = NULL;
+	const NMDedupMultiEntry *entry_old;
+	const NMDedupMultiEntry *entry_new = NULL;
+	const NMPObject *obj_old;
+	nm_auto_nmpobj NMPObject *obj_new = NULL;
 
-	old = (NMPObject *) nmp_cache_lookup_link (cache, ifindex);
+	entry_old = nmp_cache_lookup_entry_link (cache, ifindex);
 
-	if (!old) {
-		NM_SET_OUT (out_obj, NULL);
-		NM_SET_OUT (out_was_visible, FALSE);
+	if (!entry_old) {
+		NM_SET_OUT (out_obj_old, NULL);
+		NM_SET_OUT (out_obj_new, NULL);
+		return NMP_CACHE_OPS_UNCHANGED;
+	}
 
+	obj_old = entry_old->box->obj;
+
+	if (!nmp_cache_link_connected_needs_toggle (cache, obj_old, NULL, NULL)) {
+		NM_SET_OUT (out_obj_old, nmp_object_ref (obj_old));
+		NM_SET_OUT (out_obj_new, nmp_object_ref (obj_old));
 		return NMP_CACHE_OPS_UNCHANGED;
 	}
 
-	nm_assert (old->is_cached);
+	obj_new = nmp_object_clone (obj_old, FALSE);
+	obj_new->link.connected = !obj_old->link.connected;
 
-	NM_SET_OUT (out_obj, nmp_object_ref (old));
-	NM_SET_OUT (out_was_visible, nmp_object_is_visible (old));
+	NM_SET_OUT (out_obj_old, nmp_object_ref (obj_old));
+	_idxcache_update (cache,
+	                  entry_old,
+	                  obj_new,
+	                  &entry_new);
+	NM_SET_OUT (out_obj_new, nmp_object_ref (entry_new->box->obj));
+	return NMP_CACHE_OPS_UPDATED;
+}
 
-	if (!nmp_cache_link_connected_needs_toggle (cache, old, NULL, NULL))
-		return NMP_CACHE_OPS_UNCHANGED;
+/*****************************************************************************/
 
-	obj = nmp_object_clone (old, FALSE);
-	obj->link.connected = !old->link.connected;
+void
+nmp_cache_dirty_set_all (NMPCache *cache, NMPObjectType obj_type)
+{
+	NMPObject obj_needle;
 
-	nm_assert (nmp_object_is_alive (obj));
+	nm_assert (cache);
 
-	if (pre_hook)
-		pre_hook (cache, old, obj, NMP_CACHE_OPS_UPDATED, user_data);
-	_nmp_cache_update_update (cache, old, obj);
-	return NMP_CACHE_OPS_UPDATED;
+	nm_dedup_multi_index_dirty_set_head (cache->multi_idx,
+	                                     _idx_type_get (cache, NMP_CACHE_ID_TYPE_OBJECT_TYPE),
+	                                     _nmp_object_stackinit_from_type (&obj_needle, obj_type));
 }
 
 /*****************************************************************************/
 
 NMPCache *
-nmp_cache_new (gboolean use_udev)
-{
-	NMPCache *cache = g_new (NMPCache, 1);
-
-	cache->idx_main = g_hash_table_new_full ((GHashFunc) nmp_object_id_hash,
-	                                         (GEqualFunc) nmp_object_id_equal,
-	                                         (GDestroyNotify) nmp_object_unref,
-	                                         NULL);
-	cache->idx_multi = nm_multi_index_new ((NMMultiIndexFuncHash) nmp_cache_id_hash,
-	                                       (NMMultiIndexFuncEqual) nmp_cache_id_equal,
-	                                       (NMMultiIndexFuncClone) nmp_cache_id_clone,
-	                                       (NMMultiIndexFuncDestroy) nmp_cache_id_destroy);
+nmp_cache_new (NMDedupMultiIndex *multi_idx, gboolean use_udev)
+{
+	NMPCache *cache = g_slice_new0 (NMPCache);
+	guint i;
+
+	for (i = NMP_CACHE_ID_TYPE_NONE + 1; i <= NMP_CACHE_ID_TYPE_MAX; i++)
+		_dedup_multi_idx_type_init ((DedupMultiIdxType *) _idx_type_get (cache, i), i);
+
+	cache->multi_idx = nm_dedup_multi_index_ref (multi_idx);
+
 	cache->use_udev = !!use_udev;
 	return cache;
 }
@@ -2075,23 +2476,14 @@ nmp_cache_new (gboolean use_udev)
 void
 nmp_cache_free (NMPCache *cache)
 {
-	GHashTableIter iter;
-	NMPObject *obj;
+	guint i;
 
-	/* No need to cumbersomely remove the objects properly. They are not hooked up
-	 * in a complicated way, we can just unref them together with cache->idx_main.
-	 *
-	 * But we must clear the @is_cached flag. */
-	g_hash_table_iter_init (&iter, cache->idx_main);
-	while (g_hash_table_iter_next (&iter, (gpointer *) &obj, NULL)) {
-		nm_assert (obj->is_cached);
-		obj->is_cached = FALSE;
-	}
+	for (i = NMP_CACHE_ID_TYPE_NONE + 1; i <= NMP_CACHE_ID_TYPE_MAX; i++)
+		nm_dedup_multi_index_remove_idx (cache->multi_idx, _idx_type_get (cache, i));
 
-	nm_multi_index_free (cache->idx_multi);
-	g_hash_table_unref (cache->idx_main);
+	nm_dedup_multi_index_unref (cache->multi_idx);
 
-	g_free (cache);
+	g_slice_free (NMPCache, cache);
 }
 
 /*****************************************************************************/
@@ -2099,63 +2491,13 @@ nmp_cache_free (NMPCache *cache)
 void
 ASSERT_nmp_cache_is_consistent (const NMPCache *cache)
 {
-#if NM_MORE_ASSERTS
-	NMMultiIndexIter iter_multi;
-	GHashTableIter iter_hash;
-	guint i, len;
-	NMPCacheId cache_id_storage;
-	const NMPCacheId *cache_id, *cache_id2;
-	const NMPlatformObject *const *objects;
-	const NMPObject *obj;
-
-	g_assert (cache);
-
-	g_hash_table_iter_init (&iter_hash, cache->idx_main);
-	while (g_hash_table_iter_next (&iter_hash, (gpointer *) &obj, NULL)) {
-		const guint8 *id_type;
-
-		g_assert (NMP_OBJECT_IS_VALID (obj));
-		g_assert (nmp_object_is_alive (obj));
-
-		for (id_type = NMP_OBJECT_GET_CLASS (obj)->supported_cache_ids; *id_type; id_type++) {
-			if (!_nmp_object_init_cache_id (obj, *id_type, &cache_id_storage, &cache_id))
-				continue;
-			if (!cache_id)
-				continue;
-			g_assert (nm_multi_index_contains (cache->idx_multi, &cache_id->base, &obj->object));
-		}
-	}
-
-	nm_multi_index_iter_init (&iter_multi, cache->idx_multi, NULL);
-	while (nm_multi_index_iter_next (&iter_multi,
-	                                 (const NMMultiIndexId **) &cache_id,
-	                                 (void *const**) &objects,
-	                                 &len)) {
-		g_assert (len > 0 && objects && objects[len] == NULL);
-
-		for (i = 0; i < len; i++) {
-			g_assert (objects[i]);
-			obj = NMP_OBJECT_UP_CAST (objects[i]);
-			g_assert (NMP_OBJECT_IS_VALID (obj));
-
-			/* for now, enforce that all objects for a certain index are of the same type. */
-			g_assert (NMP_OBJECT_GET_CLASS (obj) == NMP_OBJECT_GET_CLASS (NMP_OBJECT_UP_CAST (objects[0])));
-
-			if (!_nmp_object_init_cache_id (obj, cache_id->_id_type, &cache_id_storage, &cache_id2))
-				g_assert_not_reached ();
-			g_assert (cache_id2);
-			g_assert (nmp_cache_id_equal (cache_id, cache_id2));
-			g_assert_cmpint (nmp_cache_id_hash (cache_id), ==, nmp_cache_id_hash (cache_id2));
-
-			g_assert (obj == g_hash_table_lookup (cache->idx_main, obj));
-		}
-	}
-#endif
 }
+
 /*****************************************************************************/
 
 const NMPClass _nmp_classes[NMP_OBJECT_TYPE_MAX] = {
 	[NMP_OBJECT_TYPE_LINK - 1] = {
+		.parent                             = DEDUP_MULTI_OBJ_CLASS_INIT(),
 		.obj_type                           = NMP_OBJECT_TYPE_LINK,
 		.sizeof_data                        = sizeof (NMPObjectLink),
 		.sizeof_public                      = sizeof (NMPlatformLink),
@@ -2165,8 +2507,7 @@ const NMPClass _nmp_classes[NMP_OBJECT_TYPE_MAX] = {
 		.signal_type_id                     = NM_PLATFORM_SIGNAL_ID_LINK,
 		.signal_type                        = NM_PLATFORM_SIGNAL_LINK_CHANGED,
 		.supported_cache_ids                = _supported_cache_ids_link,
-		.cmd_obj_init_cache_id              = _vt_cmd_obj_init_cache_id_link,
-		.cmd_obj_hash                       = _vt_cmd_obj_hash_not_implemented,
+		.cmd_obj_hash                       = _vt_cmd_obj_hash_link,
 		.cmd_obj_cmp                        = _vt_cmd_obj_cmp_link,
 		.cmd_obj_copy                       = _vt_cmd_obj_copy_link,
 		.cmd_obj_stackinit_id               = _vt_cmd_obj_stackinit_id_link,
@@ -2193,7 +2534,6 @@ const NMPClass _nmp_classes[NMP_OBJECT_TYPE_MAX] = {
 		.signal_type_id                     = NM_PLATFORM_SIGNAL_ID_IP4_ADDRESS,
 		.signal_type                        = NM_PLATFORM_SIGNAL_IP4_ADDRESS_CHANGED,
 		.supported_cache_ids                = _supported_cache_ids_ipx_address,
-		.cmd_obj_init_cache_id              = _vt_cmd_obj_init_cache_id_ipx_address,
 		.cmd_obj_stackinit_id               = _vt_cmd_obj_stackinit_id_ip4_address,
 		.cmd_obj_is_alive                   = _vt_cmd_obj_is_alive_ipx_address,
 		.cmd_plobj_id_copy                  = _vt_cmd_plobj_id_copy_ip4_address,
@@ -2215,7 +2555,6 @@ const NMPClass _nmp_classes[NMP_OBJECT_TYPE_MAX] = {
 		.signal_type_id                     = NM_PLATFORM_SIGNAL_ID_IP6_ADDRESS,
 		.signal_type                        = NM_PLATFORM_SIGNAL_IP6_ADDRESS_CHANGED,
 		.supported_cache_ids                = _supported_cache_ids_ipx_address,
-		.cmd_obj_init_cache_id              = _vt_cmd_obj_init_cache_id_ipx_address,
 		.cmd_obj_stackinit_id               = _vt_cmd_obj_stackinit_id_ip6_address,
 		.cmd_obj_is_alive                   = _vt_cmd_obj_is_alive_ipx_address,
 		.cmd_plobj_id_copy                  = _vt_cmd_plobj_id_copy_ip6_address,
@@ -2237,7 +2576,6 @@ const NMPClass _nmp_classes[NMP_OBJECT_TYPE_MAX] = {
 		.signal_type_id                     = NM_PLATFORM_SIGNAL_ID_IP4_ROUTE,
 		.signal_type                        = NM_PLATFORM_SIGNAL_IP4_ROUTE_CHANGED,
 		.supported_cache_ids                = _supported_cache_ids_ip4_route,
-		.cmd_obj_init_cache_id              = _vt_cmd_obj_init_cache_id_ipx_route,
 		.cmd_obj_stackinit_id               = _vt_cmd_obj_stackinit_id_ip4_route,
 		.cmd_obj_is_alive                   = _vt_cmd_obj_is_alive_ipx_route,
 		.cmd_plobj_id_copy                  = _vt_cmd_plobj_id_copy_ip4_route,
@@ -2259,7 +2597,6 @@ const NMPClass _nmp_classes[NMP_OBJECT_TYPE_MAX] = {
 		.signal_type_id                     = NM_PLATFORM_SIGNAL_ID_IP6_ROUTE,
 		.signal_type                        = NM_PLATFORM_SIGNAL_IP6_ROUTE_CHANGED,
 		.supported_cache_ids                = _supported_cache_ids_ip6_route,
-		.cmd_obj_init_cache_id              = _vt_cmd_obj_init_cache_id_ipx_route,
 		.cmd_obj_stackinit_id               = _vt_cmd_obj_stackinit_id_ip6_route,
 		.cmd_obj_is_alive                   = _vt_cmd_obj_is_alive_ipx_route,
 		.cmd_plobj_id_copy                  = _vt_cmd_plobj_id_copy_ip6_route,