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.

8 files changed, 1696 insertions, 1274 deletions

diff --git a/src/nm-route-manager.c b/src/nm-route-manager.c
index b58cdeb069..6c1f78ac96 100644
--- a/src/nm-route-manager.c
+++ b/src/nm-route-manager.c
@@ -1173,7 +1173,7 @@ nm_route_manager_ip4_route_register_device_route_purge_list (NMRouteManager *sel
 		                                      ? "update" : "new",
 		                                  nmp_object_to_string (entry->obj, NMP_OBJECT_TO_STRING_PUBLIC, NULL, 0));
 		g_hash_table_replace (priv->ip4_device_routes.entries,
-		                      nmp_object_ref (entry->obj),
+		                      (NMPObject *) nmp_object_ref (entry->obj),
 		                      entry);
 	}
 	if (priv->ip4_device_routes.gc_id == 0) {
diff --git a/src/platform/nm-linux-platform.c b/src/platform/nm-linux-platform.c
index 18bb159243..e7af50fa4b 100644
--- a/src/platform/nm-linux-platform.c
+++ b/src/platform/nm-linux-platform.c
@@ -255,8 +255,11 @@ static void delayed_action_schedule (NMPlatform *platform, DelayedActionType act
 static gboolean delayed_action_handle_all (NMPlatform *platform, gboolean read_netlink);
 static void do_request_link_no_delayed_actions (NMPlatform *platform, int ifindex, const char *name);
 static void do_request_all_no_delayed_actions (NMPlatform *platform, DelayedActionType action_type);
-static void cache_pre_hook (NMPCache *cache, const NMPObject *old, const NMPObject *new, NMPCacheOpsType cache_op, gpointer user_data);
-static void cache_prune_candidates_prune (NMPlatform *platform);
+static void cache_on_change (NMPlatform *platform,
+                             NMPCacheOpsType cache_op,
+                             const NMPObject *obj_old,
+                             const NMPObject *obj_new);
+static void cache_prune_all (NMPlatform *platform);
 static gboolean event_handler_read_netlink (NMPlatform *platform, gboolean wait_for_acks);
 static void ASSERT_NETNS_CURRENT (NMPlatform *platform);
 
@@ -1680,7 +1683,7 @@ _new_from_nl_link (NMPlatform *platform, const NMPCache *cache, struct nlmsghdr
 				 * Also, sometimes the info-data is missing for updates. In this case
 				 * we want to keep the previously received lnk_data. */
 				nmp_object_unref (lnk_data);
-				lnk_data = nmp_object_ref (link_cached->_link.netlink.lnk);
+				lnk_data = (NMPObject *) nmp_object_ref (link_cached->_link.netlink.lnk);
 			}
 			if (address_complete_from_cache)
 				obj->link.addr = link_cached->link.addr;
@@ -2574,7 +2577,9 @@ typedef struct {
 	GIOChannel *event_channel;
 	guint event_id;
 
-	gboolean sysctl_get_warned;
+	bool pruning[_DELAYED_ACTION_IDX_REFRESH_ALL_NUM];
+
+	bool sysctl_get_warned;
 	GHashTable *sysctl_get_prev_values;
 
 	NMUdevClient *udev_client;
@@ -2595,8 +2600,6 @@ typedef struct {
 		gint is_handling;
 	} delayed_action;
 
-	GHashTable *prune_candidates;
-
 	GHashTable *wifi_data;
 } NMLinuxPlatformPrivate;
 
@@ -2913,29 +2916,20 @@ process_events (NMPlatform *platform)
 
 /*****************************************************************************/
 
-#define cache_lookup_all_objects(type, platform, obj_type, visible_only) \
-	({ \
-		NMPCacheId _cache_id; \
-		\
-		((const type *const*) nmp_cache_lookup_multi (NM_LINUX_PLATFORM_GET_PRIVATE ((platform))->cache, \
-		                                              nmp_cache_id_init_object_type (&_cache_id, (obj_type), (visible_only)), \
-		                                              NULL)); \
-	})
-
-/*****************************************************************************/
-
 static void
-do_emit_signal (NMPlatform *platform, const NMPObject *obj_new, NMPCacheOpsType cache_op, gboolean was_visible)
-{
-	gboolean is_visible;
-	NMPObject obj_clone;
+do_emit_signal (NMPlatform *platform,
+                NMPCacheOpsType cache_op,
+                const NMPObject *obj_old,
+                const NMPObject *obj_new)
+{
+	gboolean visible_new;
+	gboolean visible_old;
+	const NMPObject *o;
 	const NMPClass *klass;
 
 	nm_assert (NM_IN_SET ((NMPlatformSignalChangeType) cache_op, (NMPlatformSignalChangeType) NMP_CACHE_OPS_UNCHANGED, NM_PLATFORM_SIGNAL_ADDED, NM_PLATFORM_SIGNAL_CHANGED, NM_PLATFORM_SIGNAL_REMOVED));
 
-	nm_assert (obj_new || cache_op == NMP_CACHE_OPS_UNCHANGED);
-	nm_assert (!obj_new || cache_op == NMP_CACHE_OPS_REMOVED || obj_new == nmp_cache_lookup_obj (NM_LINUX_PLATFORM_GET_PRIVATE (platform)->cache, obj_new));
-	nm_assert (!obj_new || cache_op != NMP_CACHE_OPS_REMOVED || obj_new != nmp_cache_lookup_obj (NM_LINUX_PLATFORM_GET_PRIVATE (platform)->cache, obj_new));
+	ASSERT_nmp_cache_ops (NM_LINUX_PLATFORM_GET_PRIVATE (platform)->cache, cache_op, obj_old, obj_new);
 
 	ASSERT_NETNS_CURRENT (platform);
 
@@ -2943,52 +2937,49 @@ do_emit_signal (NMPlatform *platform, const NMPObject *obj_new, NMPCacheOpsType
 	case NMP_CACHE_OPS_ADDED:
 		if (!nmp_object_is_visible (obj_new))
 			return;
+		o = obj_new;
 		break;
 	case NMP_CACHE_OPS_UPDATED:
-		is_visible = nmp_object_is_visible (obj_new);
-		if (!was_visible && is_visible)
+		visible_old = nmp_object_is_visible (obj_old);
+		visible_new = nmp_object_is_visible (obj_new);
+		if (!visible_old && visible_new) {
+			o = obj_new;
 			cache_op = NMP_CACHE_OPS_ADDED;
-		else if (was_visible && !is_visible) {
-			/* This is a bit ugly. The object was visible and changed in a way that it became invisible.
-			 * We raise a removed signal, but contrary to a real 'remove', @obj_new is already changed to be
-			 * different from what it was when the user saw it the last time.
-			 *
-			 * The more correct solution would be to have cache_pre_hook() create a clone of the original
-			 * value before it was changed to become invisible.
-			 *
-			 * But, don't bother. Probably nobody depends on the original values and only cares about the
-			 * id properties (which are still correct).
-			 */
+		} else if (visible_old && !visible_new) {
+			o = obj_old;
 			cache_op = NMP_CACHE_OPS_REMOVED;
-		} else if (!is_visible)
+		} else if (!visible_new) {
+			/* it was invisible and stayed invisible. Nothing to do. */
 			return;
+		} else
+			o = obj_new;
 		break;
 	case NMP_CACHE_OPS_REMOVED:
-		if (!was_visible)
+		if (!nmp_object_is_visible (obj_old))
 			return;
+		o = obj_old;
 		break;
 	default:
-		g_assert (cache_op == NMP_CACHE_OPS_UNCHANGED);
+		nm_assert (cache_op == NMP_CACHE_OPS_UNCHANGED);
 		return;
 	}
 
-	klass = NMP_OBJECT_GET_CLASS (obj_new);
+	klass = NMP_OBJECT_GET_CLASS (o);
 
 	_LOGt ("emit signal %s %s: %s",
 	       klass->signal_type,
 	       nm_platform_signal_change_type_to_string ((NMPlatformSignalChangeType) cache_op),
-	       nmp_object_to_string (obj_new, NMP_OBJECT_TO_STRING_PUBLIC, NULL, 0));
+	       nmp_object_to_string (o, NMP_OBJECT_TO_STRING_PUBLIC, NULL, 0));
 
-	/* don't expose @obj_new directly, but clone the public fields. A signal handler might
-	 * call back into NMPlatform which could invalidate (or modify) @obj_new. */
-	memcpy (&obj_clone.object, &obj_new->object, klass->sizeof_public);
+	nmp_object_ref (o);
 	g_signal_emit (platform,
 	               _nm_platform_signal_id_get (klass->signal_type_id),
 	               0,
 	               (int) klass->obj_type,
-	               obj_clone.object.ifindex,
-	               &obj_clone.object,
+	               o->object.ifindex,
+	               &o->object,
 	               (int) cache_op);
+	nmp_object_unref (o);
 }
 
 /*****************************************************************************/
@@ -3164,12 +3155,15 @@ static void
 delayed_action_handle_MASTER_CONNECTED (NMPlatform *platform, int master_ifindex)
 {
 	NMLinuxPlatformPrivate *priv = NM_LINUX_PLATFORM_GET_PRIVATE (platform);
-	nm_auto_nmpobj NMPObject *obj_cache = NULL;
-	gboolean was_visible;
+	nm_auto_nmpobj const NMPObject *obj_old = NULL;
+	nm_auto_nmpobj const NMPObject *obj_new = NULL;
 	NMPCacheOpsType cache_op;
 
-	cache_op = nmp_cache_update_link_master_connected (priv->cache, master_ifindex, &obj_cache, &was_visible, cache_pre_hook, platform);
-	do_emit_signal (platform, obj_cache, cache_op, was_visible);
+	cache_op = nmp_cache_update_link_master_connected (priv->cache, master_ifindex, &obj_old, &obj_new);
+	if (cache_op == NMP_CACHE_OPS_UNCHANGED)
+		return;
+	cache_on_change (platform, cache_op, obj_old, obj_new);
+	do_emit_signal (platform, cache_op, obj_old, obj_new);
 }
 
 static void
@@ -3290,7 +3284,7 @@ delayed_action_handle_all (NMPlatform *platform, gboolean read_netlink)
 		any = TRUE;
 	priv->delayed_action.is_handling--;
 
-	cache_prune_candidates_prune (platform);
+	cache_prune_all (platform);
 
 	return any;
 }
@@ -3353,100 +3347,68 @@ delayed_action_schedule_WAIT_FOR_NL_RESPONSE (NMPlatform *platform,
 /*****************************************************************************/
 
 static void
-cache_prune_candidates_record_all (NMPlatform *platform, NMPObjectType obj_type)
+cache_prune_one_type (NMPlatform *platform, NMPObjectType obj_type)
 {
 	NMLinuxPlatformPrivate *priv = NM_LINUX_PLATFORM_GET_PRIVATE (platform);
-	NMPCacheId cache_id;
-
-	priv->prune_candidates = nmp_cache_lookup_all_to_hash (priv->cache,
-	                                                       nmp_cache_id_init_object_type (&cache_id, obj_type, FALSE),
-	                                                       priv->prune_candidates);
-	_LOGt ("cache-prune: record %s (now %u candidates)", nmp_class_from_type (obj_type)->obj_type_name,
-	       priv->prune_candidates ? g_hash_table_size (priv->prune_candidates) : 0);
-}
-
-static void
-cache_prune_candidates_record_one (NMPlatform *platform, NMPObject *obj)
-{
-	NMLinuxPlatformPrivate *priv;
-
-	if (!obj)
-		return;
-
-	priv = NM_LINUX_PLATFORM_GET_PRIVATE (platform);
-
-	if (!priv->prune_candidates)
-		priv->prune_candidates = g_hash_table_new_full (NULL, NULL, (GDestroyNotify) nmp_object_unref, NULL);
-
-	if (_LOGt_ENABLED () && !g_hash_table_contains (priv->prune_candidates, obj))
-		_LOGt ("cache-prune: record-one: %s", nmp_object_to_string (obj, NMP_OBJECT_TO_STRING_ALL, NULL, 0));
-	g_hash_table_add (priv->prune_candidates, nmp_object_ref (obj));
-}
-
-static void
-cache_prune_candidates_drop (NMPlatform *platform, const NMPObject *obj)
-{
-	NMLinuxPlatformPrivate *priv;
-
-	if (!obj)
-		return;
-
-	priv = NM_LINUX_PLATFORM_GET_PRIVATE (platform);
-	if (priv->prune_candidates) {
-		if (_LOGt_ENABLED () && g_hash_table_contains (priv->prune_candidates, obj))
-			_LOGt ("cache-prune: drop-one: %s", nmp_object_to_string (obj, NMP_OBJECT_TO_STRING_ALL, NULL, 0));
-		g_hash_table_remove (priv->prune_candidates, obj);
+	NMDedupMultiIter iter;
+	const NMPObject *obj;
+	NMPCacheOpsType cache_op;
+	NMPLookup lookup;
+
+	nmp_lookup_init_obj_type (&lookup,
+	                          NMP_CACHE_ID_TYPE_OBJECT_TYPE,
+	                          FALSE);
+	nm_dedup_multi_iter_init (&iter,
+	                          nmp_cache_lookup (priv->cache,
+	                                            &lookup));
+	while (nm_dedup_multi_iter_next (&iter)) {
+		if (iter.current->dirty) {
+			nm_auto_nlmsg const NMPObject *obj_old = NULL;
+
+			obj = iter.current->box->obj;
+			_LOGt ("cache-prune: prune %s", nmp_object_to_string (obj, NMP_OBJECT_TO_STRING_ALL, NULL, 0));
+			cache_op = nmp_cache_remove (priv->cache, obj, TRUE, &obj_old);
+			nm_assert (cache_op == NMP_CACHE_OPS_REMOVED);
+			cache_on_change (platform, cache_op, obj_old, NULL);
+			do_emit_signal (platform, cache_op, obj_old, NULL);
+		}
 	}
 }
 
 static void
-cache_prune_candidates_prune (NMPlatform *platform)
+cache_prune_all (NMPlatform *platform)
 {
 	NMLinuxPlatformPrivate *priv = NM_LINUX_PLATFORM_GET_PRIVATE (platform);
-	GHashTable *prune_candidates;
-	GHashTableIter iter;
-	const NMPObject *obj;
-	gboolean was_visible;
-	NMPCacheOpsType cache_op;
-
-	if (!priv->prune_candidates)
-		return;
+	DelayedActionType iflags, action_type;
 
-	prune_candidates = priv->prune_candidates;
-	priv->prune_candidates = NULL;
-
-	g_hash_table_iter_init (&iter, prune_candidates);
-	while (g_hash_table_iter_next (&iter, (gpointer *)&obj, NULL)) {
-		nm_auto_nmpobj NMPObject *obj_cache = NULL;
+	action_type = DELAYED_ACTION_TYPE_REFRESH_ALL;
+	FOR_EACH_DELAYED_ACTION (iflags, action_type) {
+		bool *p = &priv->pruning[delayed_action_refresh_all_to_idx (iflags)];
 
-		_LOGt ("cache-prune: prune %s", nmp_object_to_string (obj, NMP_OBJECT_TO_STRING_ALL, NULL, 0));
-		cache_op = nmp_cache_remove (priv->cache, obj, TRUE, &obj_cache, &was_visible, cache_pre_hook, platform);
-		do_emit_signal (platform, obj_cache, cache_op, was_visible);
+		if (*p) {
+			*p = TRUE;
+			cache_prune_one_type (platform, delayed_action_refresh_to_object_type (iflags));
+		}
 	}
-
-	g_hash_table_unref (prune_candidates);
 }
 
 static void
-cache_pre_hook (NMPCache *cache, const NMPObject *obj_old, const NMPObject *obj_new, NMPCacheOpsType cache_op, gpointer user_data)
+cache_on_change (NMPlatform *platform,
+                 NMPCacheOpsType cache_op,
+                 const NMPObject *obj_old,
+                 const NMPObject *obj_new)
 {
-	NMPlatform *platform = user_data;
 	NMLinuxPlatformPrivate *priv = NM_LINUX_PLATFORM_GET_PRIVATE (platform);
 	const NMPClass *klass;
 	char str_buf[sizeof (_nm_utils_to_string_buffer)];
 	char str_buf2[sizeof (_nm_utils_to_string_buffer)];
 
-	nm_assert (obj_old || obj_new);
-	nm_assert (NM_IN_SET (cache_op, NMP_CACHE_OPS_ADDED, NMP_CACHE_OPS_REMOVED, NMP_CACHE_OPS_UPDATED));
-	nm_assert (cache_op != NMP_CACHE_OPS_ADDED   || (obj_old == NULL && NMP_OBJECT_IS_VALID (obj_new) && nmp_object_is_alive (obj_new)));
-	nm_assert (cache_op != NMP_CACHE_OPS_REMOVED || (obj_new == NULL && NMP_OBJECT_IS_VALID (obj_old) && nmp_object_is_alive (obj_old)));
-	nm_assert (cache_op != NMP_CACHE_OPS_UPDATED || (NMP_OBJECT_IS_VALID (obj_old) && nmp_object_is_alive (obj_old) && NMP_OBJECT_IS_VALID (obj_new) && nmp_object_is_alive (obj_new)));
-	nm_assert (obj_new == NULL || obj_old == NULL || nmp_object_id_equal (obj_new, obj_old));
-	nm_assert (!obj_old || !obj_new || NMP_OBJECT_GET_CLASS (obj_old) == NMP_OBJECT_GET_CLASS (obj_new));
+	ASSERT_nmp_cache_ops (priv->cache, cache_op, obj_old, obj_new);
 
-	klass = obj_old ? NMP_OBJECT_GET_CLASS (obj_old) : NMP_OBJECT_GET_CLASS (obj_new);
+	if (cache_op == NMP_CACHE_OPS_UNCHANGED)
+		return;
 
-	nm_assert (klass == (obj_new ? NMP_OBJECT_GET_CLASS (obj_new) : NMP_OBJECT_GET_CLASS (obj_old)));
+	klass = obj_old ? NMP_OBJECT_GET_CLASS (obj_old) : NMP_OBJECT_GET_CLASS (obj_new);
 
 	_LOGt ("update-cache-%s: %s: %s%s%s",
 	       klass->obj_type_name,
@@ -3478,7 +3440,7 @@ cache_pre_hook (NMPCache *cache, const NMPObject *obj_old, const NMPObject *obj_
 		{
 			/* check whether we are about to change a master link that needs toggling connected state. */
 			if (   obj_new /* <-- nonsensical, make coverity happy */
-			    && nmp_cache_link_connected_needs_toggle (cache, obj_new, obj_new, obj_old))
+			    && nmp_cache_link_connected_needs_toggle (priv->cache, obj_new, obj_new, obj_old))
 				delayed_action_schedule (platform, DELAYED_ACTION_TYPE_MASTER_CONNECTED, GINT_TO_POINTER (obj_new->link.ifindex));
 		}
 		{
@@ -3522,16 +3484,16 @@ cache_pre_hook (NMPCache *cache, const NMPObject *obj_old, const NMPObject *obj_
 				ifindex = obj_new->link.ifindex;
 
 			if (ifindex > 0) {
-				const NMPlatformLink *const *links;
-
-				links = cache_lookup_all_objects (NMPlatformLink, platform, NMP_OBJECT_TYPE_LINK, FALSE);
-				if (links) {
-					for (; *links; links++) {
-						const NMPlatformLink *l = (*links);
-
-						if (l->parent == ifindex)
-							delayed_action_schedule (platform, DELAYED_ACTION_TYPE_REFRESH_LINK, GINT_TO_POINTER (l->ifindex));
-					}
+				NMPLookup lookup;
+				NMDedupMultiIter iter;
+				const NMPlatformLink *l;
+
+				nmp_lookup_init_link (&lookup, FALSE);
+				nmp_cache_iter_for_each_link (&iter,
+				                              nmp_cache_lookup (priv->cache, &lookup),
+				                              &l) {
+					if (l->parent == ifindex)
+						delayed_action_schedule (platform, DELAYED_ACTION_TYPE_REFRESH_LINK, GINT_TO_POINTER (l->ifindex));
 				}
 			}
 		}
@@ -3739,8 +3701,13 @@ do_request_link_no_delayed_actions (NMPlatform *platform, int ifindex, const cha
 	_LOGD ("do-request-link: %d %s", ifindex, name ? name : "");
 
 	if (ifindex > 0) {
-		cache_prune_candidates_record_one (platform,
-		                                   (NMPObject *) nmp_cache_lookup_link (priv->cache, ifindex));
+		const NMDedupMultiEntry *entry;
+
+		entry = nmp_cache_lookup_entry_link (priv->cache, ifindex);
+		if (entry) {
+			priv->pruning[DELAYED_ACTION_IDX_REFRESH_ALL_LINKS] = TRUE;
+			nm_dedup_multi_entry_set_dirty (entry, TRUE);
+		}
 	}
 
 	event_handler_read_netlink (platform, FALSE);
@@ -3772,7 +3739,9 @@ do_request_all_no_delayed_actions (NMPlatform *platform, DelayedActionType actio
 	action_type &= DELAYED_ACTION_TYPE_REFRESH_ALL;
 
 	FOR_EACH_DELAYED_ACTION (iflags, action_type) {
-		cache_prune_candidates_record_all (platform, delayed_action_refresh_to_object_type (iflags));
+		priv->pruning[delayed_action_refresh_all_to_idx (iflags)] = TRUE;
+		nmp_cache_dirty_set_all (priv->cache,
+		                         delayed_action_refresh_to_object_type (iflags));
 	}
 
 	FOR_EACH_DELAYED_ACTION (iflags, action_type) {
@@ -3903,7 +3872,6 @@ event_valid_msg (NMPlatform *platform, struct nl_msg *msg, gboolean handle_event
 	struct nlmsghdr *msghdr;
 	char buf_nlmsg_type[16];
 	gboolean id_only = FALSE;
-	gboolean was_visible;
 
 	msghdr = nlmsg_hdr (msg);
 
@@ -3932,31 +3900,36 @@ event_valid_msg (NMPlatform *platform, struct nl_msg *msg, gboolean handle_event
 	       msghdr->nlmsg_seq, nmp_object_to_string (obj,
 	           id_only ? NMP_OBJECT_TO_STRING_ID : NMP_OBJECT_TO_STRING_PUBLIC, NULL, 0));
 
-	switch (msghdr->nlmsg_type) {
-
-	case RTM_NEWLINK:
-	case RTM_NEWADDR:
-	case RTM_NEWROUTE:
-	case RTM_GETLINK:
-		cache_op = nmp_cache_update_netlink (priv->cache, obj, &obj_cache, &was_visible, cache_pre_hook, platform);
-
-		cache_post (platform, msghdr, cache_op, obj, obj_cache);
-
-		do_emit_signal (platform, obj_cache, cache_op, was_visible);
-		break;
+	{
+		nm_auto_nmpobj const NMPObject *obj_old = NULL;
+		nm_auto_nmpobj const NMPObject *obj_new = NULL;
+
+		switch (msghdr->nlmsg_type) {
+
+		case RTM_NEWLINK:
+		case RTM_NEWADDR:
+		case RTM_NEWROUTE:
+		case RTM_GETLINK:
+			cache_op = nmp_cache_update_netlink (priv->cache, obj, &obj_old, &obj_new);
+			cache_on_change (platform, cache_op, obj_old, obj_new);
+			cache_post (platform, msghdr, cache_op, obj, obj_cache);
+			do_emit_signal (platform, cache_op, obj_old, obj_new);
+			break;
 
-	case RTM_DELLINK:
-	case RTM_DELADDR:
-	case RTM_DELROUTE:
-		cache_op = nmp_cache_remove_netlink (priv->cache, obj, &obj_cache, &was_visible, cache_pre_hook, platform);
-		do_emit_signal (platform, obj_cache, cache_op, was_visible);
-		break;
+		case RTM_DELLINK:
+		case RTM_DELADDR:
+		case RTM_DELROUTE:
+			cache_op = nmp_cache_remove_netlink (priv->cache, obj, &obj_old, &obj_new);
+			if (cache_op != NMP_CACHE_OPS_UNCHANGED) {
+				cache_on_change (platform, cache_op, obj_old, obj_new);
+				do_emit_signal (platform, cache_op, obj_old, obj_new);
+			}
+			break;
 
-	default:
-		break;
+		default:
+			break;
+		}
 	}
-
-	cache_prune_candidates_drop (platform, obj_cache);
 }
 
 /*****************************************************************************/
@@ -3973,25 +3946,15 @@ cache_lookup_link (NMPlatform *platform, int ifindex)
 	return obj_cache;
 }
 
-const NMPlatformObject *const*
-nm_linux_platform_lookup (NMPlatform *platform, const NMPCacheId *cache_id, guint *out_len)
-{
-	g_return_val_if_fail (NM_IS_LINUX_PLATFORM (platform), NULL);
-	g_return_val_if_fail (cache_id, NULL);
-
-	return nmp_cache_lookup_multi (NM_LINUX_PLATFORM_GET_PRIVATE (platform)->cache,
-	                               cache_id, out_len);
-}
-
 static GArray *
 link_get_all (NMPlatform *platform)
 {
 	NMLinuxPlatformPrivate *priv = NM_LINUX_PLATFORM_GET_PRIVATE (platform);
-	NMPCacheId cache_id;
+	NMPLookup lookup;
 
-	return nmp_cache_lookup_multi_to_array (priv->cache,
-	                                        NMP_OBJECT_TYPE_LINK,
-	                                        nmp_cache_id_init_object_type (&cache_id, NMP_OBJECT_TYPE_LINK, TRUE));
+	nmp_lookup_init_link (&lookup, TRUE);
+	return nmp_cache_lookup_to_array (nmp_cache_lookup (priv->cache, &lookup),
+	                                  NMP_OBJECT_TYPE_LINK);
 }
 
 static const NMPlatformLink *
@@ -5733,10 +5696,9 @@ static gboolean
 link_can_assume (NMPlatform *platform, int ifindex)
 {
 	NMLinuxPlatformPrivate *priv = NM_LINUX_PLATFORM_GET_PRIVATE (platform);
-	NMPCacheId cache_id;
-	const NMPlatformObject *const *objs;
-	guint i, len;
-	const NMPObject *link;
+	NMPLookup lookup;
+	const NMPObject *link, *o;
+	NMDedupMultiIter iter;
 
 	if (ifindex <= 0)
 		return FALSE;
@@ -5751,21 +5713,23 @@ link_can_assume (NMPlatform *platform, int ifindex)
 	if (link->link.master > 0)
 		return TRUE;
 
-	if (nmp_cache_lookup_multi (priv->cache,
-	                            nmp_cache_id_init_addrroute_visible_by_ifindex (&cache_id, NMP_OBJECT_TYPE_IP4_ADDRESS, ifindex),
-	                            NULL))
+	nmp_lookup_init_addrroute (&lookup,
+	                           NMP_OBJECT_TYPE_IP4_ADDRESS,
+	                           ifindex,
+	                           TRUE);
+	if (nmp_cache_lookup (priv->cache, &lookup))
 		return TRUE;
 
-	objs = nmp_cache_lookup_multi (priv->cache,
-	                               nmp_cache_id_init_addrroute_visible_by_ifindex (&cache_id, NMP_OBJECT_TYPE_IP6_ADDRESS, ifindex),
-	                               &len);
-	if (objs) {
-		for (i = 0; i < len; i++) {
-			const NMPlatformIP6Address *a = (NMPlatformIP6Address *) objs[i];
-
-			if (!IN6_IS_ADDR_LINKLOCAL (&a->address))
+	nmp_lookup_init_addrroute (&lookup,
+	                           NMP_OBJECT_TYPE_IP6_ADDRESS,
+	                           ifindex,
+	                           TRUE);
+	nmp_cache_iter_for_each (&iter,
+	                         nmp_cache_lookup (priv->cache, &lookup),
+	                         &o) {
+		nm_assert (NMP_OBJECT_GET_TYPE (o) == NMP_OBJECT_TYPE_IP6_ADDRESS);
+		if (!IN6_IS_ADDR_LINKLOCAL (&o->ip6_address.address))
 				return TRUE;
-		}
 	}
 	return FALSE;
 }
@@ -5844,15 +5808,15 @@ static GArray *
 ipx_address_get_all (NMPlatform *platform, int ifindex, NMPObjectType obj_type)
 {
 	NMLinuxPlatformPrivate *priv = NM_LINUX_PLATFORM_GET_PRIVATE (platform);
-	NMPCacheId cache_id;
+	NMPLookup lookup;
 
 	nm_assert (NM_IN_SET (obj_type, NMP_OBJECT_TYPE_IP4_ADDRESS, NMP_OBJECT_TYPE_IP6_ADDRESS));
-
-	return nmp_cache_lookup_multi_to_array (priv->cache,
-	                                        obj_type,
-	                                        nmp_cache_id_init_addrroute_visible_by_ifindex (&cache_id,
-	                                                                                        obj_type,
-	                                                                                        ifindex));
+	nmp_lookup_init_addrroute (&lookup,
+	                           obj_type,
+	                           ifindex,
+	                           TRUE);
+	return nmp_cache_lookup_to_array (nmp_cache_lookup (priv->cache, &lookup),
+	                                  obj_type);
 }
 
 static GArray *
@@ -6010,12 +5974,13 @@ static GArray *
 ipx_route_get_all (NMPlatform *platform, int ifindex, NMPObjectType obj_type, NMPlatformGetRouteFlags flags)
 {
 	NMLinuxPlatformPrivate *priv = NM_LINUX_PLATFORM_GET_PRIVATE (platform);
-	NMPCacheId cache_id;
-	const NMPlatformIPRoute *const* routes;
+	NMDedupMultiIter iter;
+	NMPLookup lookup;
+	const NMDedupMultiHeadEntry *head_entry;
 	GArray *array;
 	const NMPClass *klass;
+	const NMPObject *o;
 	gboolean with_rtprot_kernel;
-	guint i, len;
 
 	nm_assert (NM_IN_SET (obj_type, NMP_OBJECT_TYPE_IP4_ROUTE, NMP_OBJECT_TYPE_IP6_ROUTE));
 
@@ -6024,23 +5989,24 @@ ipx_route_get_all (NMPlatform *platform, int ifindex, NMPObjectType obj_type, NM
 
 	klass = nmp_class_from_type (obj_type);
 
-	nmp_cache_id_init_routes_visible (&cache_id,
-	                                  obj_type,
-	                                  NM_FLAGS_HAS (flags, NM_PLATFORM_GET_ROUTE_FLAGS_WITH_DEFAULT),
-	                                  NM_FLAGS_HAS (flags, NM_PLATFORM_GET_ROUTE_FLAGS_WITH_NON_DEFAULT),
-	                                  ifindex);
+	head_entry = nmp_cache_lookup (priv->cache,
+	                               nmp_lookup_init_route_visible (&lookup,
+	                                                              obj_type,
+	                                                              ifindex,
+	                                                              NM_FLAGS_HAS (flags, NM_PLATFORM_GET_ROUTE_FLAGS_WITH_DEFAULT),
+	                                                              NM_FLAGS_HAS (flags, NM_PLATFORM_GET_ROUTE_FLAGS_WITH_NON_DEFAULT)));
 
-	routes = (const NMPlatformIPRoute *const*) nmp_cache_lookup_multi (priv->cache, &cache_id, &len);
-
-	array = g_array_sized_new (FALSE, FALSE, klass->sizeof_public, len);
+	array = g_array_sized_new (FALSE, FALSE, klass->sizeof_public, head_entry ? head_entry->len : 0);
 
 	with_rtprot_kernel = NM_FLAGS_HAS (flags, NM_PLATFORM_GET_ROUTE_FLAGS_WITH_RTPROT_KERNEL);
-	for (i = 0; i < len; i++) {
-		nm_assert (NMP_OBJECT_GET_CLASS (NMP_OBJECT_UP_CAST (routes[i])) == klass);
 
+	nmp_cache_iter_for_each (&iter,
+	                         head_entry,
+	                         &o) {
+		nm_assert (NMP_OBJECT_GET_CLASS (o) == klass);
 		if (   with_rtprot_kernel
-		    || routes[i]->rt_source != NM_IP_CONFIG_SOURCE_RTPROT_KERNEL)
-			g_array_append_vals (array, routes[i], 1);
+		    || o->ip_route.rt_source != NM_IP_CONFIG_SOURCE_RTPROT_KERNEL)
+			g_array_append_vals (array, &o->ip_route, 1);
 	}
 	return array;
 }
@@ -6634,18 +6600,19 @@ cache_update_link_udev (NMPlatform *platform,
                         struct udev_device *udevice)
 {
 	NMLinuxPlatformPrivate *priv = NM_LINUX_PLATFORM_GET_PRIVATE (platform);
-	nm_auto_nmpobj NMPObject *obj_cache = NULL;
-	gboolean was_visible;
+	nm_auto_nmpobj const NMPObject *obj_old = NULL;
+	nm_auto_nmpobj const NMPObject *obj_new = NULL;
 	NMPCacheOpsType cache_op;
 
-	cache_op = nmp_cache_update_link_udev (priv->cache, ifindex, udevice, &obj_cache, &was_visible, cache_pre_hook, platform);
+	cache_op = nmp_cache_update_link_udev (priv->cache, ifindex, udevice, &obj_old, &obj_new);
 
 	if (cache_op != NMP_CACHE_OPS_UNCHANGED) {
 		nm_auto_pop_netns NMPNetns *netns = NULL;
 
+		cache_on_change (platform, cache_op, obj_old, obj_new);
 		if (!nm_platform_netns_push (platform, &netns))
 			return;
-		do_emit_signal (platform, obj_cache, cache_op, was_visible);
+		do_emit_signal (platform, cache_op, obj_old, obj_new);
 	}
 }
 
@@ -6753,19 +6720,15 @@ static void
 nm_linux_platform_init (NMLinuxPlatform *self)
 {
 	NMLinuxPlatformPrivate *priv = NM_LINUX_PLATFORM_GET_PRIVATE (self);
-	gboolean use_udev;
-
-	use_udev =    nmp_netns_is_initial ()
-	           && access ("/sys", W_OK) == 0;
 
 	priv->nlh_seq_next = 1;
-	priv->cache = nmp_cache_new (use_udev);
 	priv->delayed_action.list_master_connected = g_ptr_array_new ();
 	priv->delayed_action.list_refresh_link = g_ptr_array_new ();
 	priv->delayed_action.list_wait_for_nl_response = g_array_new (FALSE, TRUE, sizeof (DelayedActionWaitForNlResponseData));
 	priv->wifi_data = g_hash_table_new_full (NULL, NULL, NULL, (GDestroyNotify) wifi_utils_deinit);
 
-	if (use_udev) {
+	if (   nmp_netns_is_initial ()
+	    && access ("/sys", W_OK) == 0) {
 		priv->udev_client = nm_udev_client_new ((const char *[]) { "net", NULL },
 		                                        handle_udev_event, self);
 	}
@@ -6793,6 +6756,9 @@ constructed (GObject *_object)
 	                                   nmp_netns_get_current () == nmp_netns_get_initial () ? "/main" : "")),
 	       nmp_cache_use_udev_get (priv->cache) ? "use" : "no");
 
+	priv->cache = nmp_cache_new (nm_platform_get_multi_idx (platform),
+	                             priv->udev_client != NULL);
+
 	priv->nlh = nl_socket_alloc ();
 	g_assert (priv->nlh);
 
@@ -6892,8 +6858,6 @@ dispose (GObject *object)
 	g_ptr_array_set_size (priv->delayed_action.list_master_connected, 0);
 	g_ptr_array_set_size (priv->delayed_action.list_refresh_link, 0);
 
-	g_clear_pointer (&priv->prune_candidates, g_hash_table_unref);
-
 	G_OBJECT_CLASS (nm_linux_platform_parent_class)->dispose (object);
 }
 
diff --git a/src/platform/nm-linux-platform.h b/src/platform/nm-linux-platform.h
index 6b66ea699c..bff6c00cc7 100644
--- a/src/platform/nm-linux-platform.h
+++ b/src/platform/nm-linux-platform.h
@@ -39,10 +39,4 @@ NMPlatform *nm_linux_platform_new (gboolean log_with_ptr, gboolean netns_support
 
 void nm_linux_platform_setup (void);
 
-struct _NMPCacheId;
-
-const NMPlatformObject *const *nm_linux_platform_lookup (NMPlatform *platform,
-                                                         const struct _NMPCacheId *cache_id,
-                                                         guint *out_len);
-
 #endif /* __NETWORKMANAGER_LINUX_PLATFORM_H__ */
diff --git a/src/platform/nm-platform.c b/src/platform/nm-platform.c
index b1f5904fe3..2dfe50d472 100644
--- a/src/platform/nm-platform.c
+++ b/src/platform/nm-platform.c
@@ -4149,6 +4149,39 @@ nm_platform_ip6_route_to_string (const NMPlatformIP6Route *route, char *buf, gsi
             return c < 0 ? -1 : 1;                          \
     } G_STMT_END
 
+guint
+nm_platform_link_hash (const NMPlatformLink *obj)
+{
+	guint h = 99413953;
+	guint8 i8;
+
+	h = NM_HASH_COMBINE (h, obj->ifindex);
+	h = NM_HASH_COMBINE (h, obj->type);
+	h = NM_HASH_COMBINE (h, g_str_hash (obj->name));
+	h = NM_HASH_COMBINE (h, obj->master);
+	h = NM_HASH_COMBINE (h, obj->parent);
+	h = NM_HASH_COMBINE (h, obj->n_ifi_flags);
+	h = NM_HASH_COMBINE (h, obj->connected);
+	h = NM_HASH_COMBINE (h, obj->mtu);
+	h = NM_HASH_COMBINE (h, !!obj->initialized);
+	h = NM_HASH_COMBINE (h, obj->arptype);
+	h = NM_HASH_COMBINE (h, obj->addr.len);
+	h = NM_HASH_COMBINE (h, obj->inet6_addr_gen_mode_inv);
+	if (obj->kind)
+		h = NM_HASH_COMBINE (h, g_str_hash (obj->kind));
+	if (obj->driver)
+		h = NM_HASH_COMBINE (h, g_str_hash (obj->driver));
+	for (i8 = 0; i8 < obj->addr.len; i8++)
+		h = NM_HASH_COMBINE (h, obj->addr.data[i8]);
+	for (i8 = 0; i8 < sizeof (obj->inet6_token); i8++)
+		h = NM_HASH_COMBINE (h, obj->inet6_token.id_u8[i8]);
+	h = NM_HASH_COMBINE (h, obj->rx_packets);
+	h = NM_HASH_COMBINE (h, obj->rx_bytes);
+	h = NM_HASH_COMBINE (h, obj->tx_packets);
+	h = NM_HASH_COMBINE (h, obj->tx_bytes);
+	return h;
+}
+
 int
 nm_platform_link_cmp (const NMPlatformLink *a, const NMPlatformLink *b)
 {
diff --git a/src/platform/nm-platform.h b/src/platform/nm-platform.h
index 71dd7f9ff6..aaa549aeb2 100644
--- a/src/platform/nm-platform.h
+++ b/src/platform/nm-platform.h
@@ -1024,6 +1024,7 @@ nm_platform_ip6_route_cmp (const NMPlatformIP6Route *a, const NMPlatformIP6Route
 	return nm_platform_ip6_route_cmp_full (a, b, TRUE);
 }
 
+guint nm_platform_link_hash (const NMPlatformLink *obj);
 guint nm_platform_ip4_address_hash (const NMPlatformIP4Address *obj);
 guint nm_platform_ip6_address_hash (const NMPlatformIP6Address *obj);
 guint nm_platform_ip4_route_hash (const NMPlatformIP4Route *obj);
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,
diff --git a/src/platform/nmp-object.h b/src/platform/nmp-object.h
index 7664a43817..bf3671d355 100644
--- a/src/platform/nmp-object.h
+++ b/src/platform/nmp-object.h
@@ -24,7 +24,6 @@
 #include "nm-utils/nm-obj.h"
 #include "nm-utils/nm-dedup-multi.h"
 #include "nm-platform.h"
-#include "nm-multi-index.h"
 
 struct udev_device;
 
@@ -60,7 +59,14 @@ typedef enum { /*< skip >*/
 typedef enum { /*< skip >*/
 	NMP_CACHE_ID_TYPE_NONE,
 
-	/* all the objects of a certain type */
+	/* all the objects of a certain type.
+	 *
+	 * This index is special. It is the only one that contains *all* object.
+	 * Other indexes may consider some object as non "partitionable", hence
+	 * they don't track all objects.
+	 *
+	 * Hence, this index type is used when looking at all objects (still
+	 * partitioned by type). */
 	NMP_CACHE_ID_TYPE_OBJECT_TYPE,
 
 	/* index for the link objects by ifname. */
@@ -76,7 +82,7 @@ typedef enum { /*< skip >*/
 	/* all the visible addresses/routes (by object-type) for an ifindex. */
 	NMP_CACHE_ID_TYPE_ADDRROUTE_VISIBLE_BY_IFINDEX,
 
-	/* three indeces for the visible routes, per ifindex. */
+	/* indeces for the visible routes, per ifindex. */
 	NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_NO_DEFAULT,
 	NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_ONLY_DEFAULT,
 
@@ -95,50 +101,6 @@ typedef enum { /*< skip >*/
 	NMP_CACHE_ID_TYPE_MAX = __NMP_CACHE_ID_TYPE_MAX - 1,
 } NMPCacheIdType;
 
-typedef struct _NMPCacheId NMPCacheId;
-
-struct _NMPCacheId {
-	union {
-		NMMultiIndexId base;
-		guint8 _id_type; /* NMPCacheIdType as guint8 */
-		struct _nm_packed {
-			/* NMP_CACHE_ID_TYPE_OBJECT_TYPE */
-			/* NMP_CACHE_ID_TYPE_OBJECT_TYPE_VISIBLE_ONLY */
-			/* NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_NO_DEFAULT */
-			/* NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_ONLY_DEFAULT */
-			guint8 _id_type;
-			guint8 obj_type; /* NMPObjectType as guint8 */
-		} object_type;
-		struct _nm_packed {
-			/* NMP_CACHE_ID_TYPE_ADDRROUTE_VISIBLE_BY_IFINDEX */
-			/* NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_NO_DEFAULT */
-			/* NMP_CACHE_ID_TYPE_ROUTES_VISIBLE_BY_IFINDEX_ONLY_DEFAULT */
-			guint8 _id_type;
-			guint8 obj_type; /* NMPObjectType as guint8 */
-			int _misaligned_ifindex;
-		} object_type_by_ifindex;
-		struct _nm_packed {
-			/* NMP_CACHE_ID_TYPE_LINK_BY_IFNAME */
-			guint8 _id_type;
-			char ifname_short[IFNAMSIZ - 1]; /* don't include the trailing NUL so the struct fits in 4 bytes. */
-		} link_by_ifname;
-		struct _nm_packed {
-			/* NMP_CACHE_ID_TYPE_ROUTES_BY_DESTINATION_IP4 */
-			guint8 _id_type;
-			guint8 plen;
-			guint32 _misaligned_metric;
-			guint32 _misaligned_network;
-		} routes_by_destination_ip4;
-		struct _nm_packed {
-			/* NMP_CACHE_ID_TYPE_ROUTES_BY_DESTINATION_IP6 */
-			guint8 _id_type;
-			guint8 plen;
-			guint32 _misaligned_metric;
-			struct in6_addr _misaligned_network;
-		} routes_by_destination_ip6;
-	};
-};
-
 typedef struct {
 	NMDedupMultiObjClass parent;
 	const char *obj_type_name;
@@ -155,10 +117,6 @@ typedef struct {
 	/* Only for NMPObjectLnk* types. */
 	NMLinkType lnk_link_type;
 
-	/* returns %FALSE, if the obj type would never have an entry for index type @id_type. If @obj has an index,
-	 * initialize @id and set @out_id to it. Otherwise, @out_id is NULL. */
-	gboolean (*cmd_obj_init_cache_id) (const NMPObject *obj, NMPCacheIdType id_type, NMPCacheId *id, const NMPCacheId **out_id);
-
 	guint (*cmd_obj_hash) (const NMPObject *obj);
 	int (*cmd_obj_cmp) (const NMPObject *obj1, const NMPObject *obj2);
 	void (*cmd_obj_copy) (NMPObject *dst, const NMPObject *src);
@@ -276,7 +234,6 @@ struct _NMPObject {
 		const NMPClass *_class;
 	};
 	guint _ref_count;
-	bool is_cached;
 	union {
 		NMPlatformObject        object;
 
@@ -387,8 +344,8 @@ NMP_OBJECT_GET_TYPE (const NMPObject *obj)
 
 const NMPClass *nmp_class_from_type (NMPObjectType obj_type);
 
-NMPObject *nmp_object_ref (NMPObject *object);
-void nmp_object_unref (NMPObject *object);
+const NMPObject *nmp_object_ref (const NMPObject *object);
+void nmp_object_unref (const NMPObject *object);
 NMPObject *nmp_object_new (NMPObjectType obj_type, const NMPlatformObject *plob);
 NMPObject *nmp_object_new_link (int ifindex);
 
@@ -411,13 +368,13 @@ guint nmp_object_id_hash (const NMPObject *obj);
 gboolean nmp_object_is_alive (const NMPObject *obj);
 gboolean nmp_object_is_visible (const NMPObject *obj);
 
-void _nmp_object_fixup_link_udev_fields (NMPObject *obj, gboolean use_udev);
+void _nmp_object_fixup_link_udev_fields (NMPObject **obj_new, NMPObject *obj_orig, gboolean use_udev);
 
 #define nm_auto_nmpobj __attribute__((cleanup(_nm_auto_nmpobj_cleanup)))
 static inline void
-_nm_auto_nmpobj_cleanup (NMPObject **pobj)
+_nm_auto_nmpobj_cleanup (gpointer p)
 {
-	nmp_object_unref (*pobj);
+	nmp_object_unref (*((const NMPObject **) p));
 }
 
 typedef struct _NMPCache NMPCache;
@@ -425,23 +382,92 @@ typedef struct _NMPCache NMPCache;
 typedef void (*NMPCachePreHook) (NMPCache *cache, const NMPObject *old, const NMPObject *new, NMPCacheOpsType ops_type, gpointer user_data);
 typedef gboolean (*NMPObjectMatchFn) (const NMPObject *obj, gpointer user_data);
 
-gboolean nmp_cache_id_equal (const NMPCacheId *a, const NMPCacheId *b);
-guint nmp_cache_id_hash (const NMPCacheId *id);
-NMPCacheId *nmp_cache_id_clone (const NMPCacheId *id);
-void nmp_cache_id_destroy (NMPCacheId *id);
+const NMDedupMultiEntry *nmp_cache_lookup_entry_link (const NMPCache *cache, int ifindex);
 
-NMPCacheId *nmp_cache_id_init_object_type (NMPCacheId *id, NMPObjectType obj_type, gboolean visible_only);
-NMPCacheId *nmp_cache_id_init_addrroute_visible_by_ifindex (NMPCacheId *id, NMPObjectType obj_type, int ifindex);
-NMPCacheId *nmp_cache_id_init_routes_visible (NMPCacheId *id, NMPObjectType obj_type, gboolean with_default, gboolean with_non_default, int ifindex);
-NMPCacheId *nmp_cache_id_init_link_by_ifname (NMPCacheId *id, const char *ifname);
-NMPCacheId *nmp_cache_id_init_routes_by_destination_ip4 (NMPCacheId *id, guint32 network, guint8 plen, guint32 metric);
-NMPCacheId *nmp_cache_id_init_routes_by_destination_ip6 (NMPCacheId *id, const struct in6_addr *network, guint8 plen, guint32 metric);
-
-const NMPlatformObject *const *nmp_cache_lookup_multi (const NMPCache *cache, const NMPCacheId *cache_id, guint *out_len);
-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 NMPObject *nmp_cache_lookup_link (const NMPCache *cache, int ifindex);
 
+typedef struct {
+	NMPCacheIdType cache_id_type;
+	NMPObject selector_obj;
+} NMPLookup;
+
+const NMDedupMultiHeadEntry *nmp_cache_lookup_all (const NMPCache *cache,
+                                                   NMPCacheIdType cache_id_type,
+                                                   const NMPObject *select_obj);
+
+static inline const NMDedupMultiHeadEntry *
+nmp_cache_lookup (const NMPCache *cache,
+                  const NMPLookup *lookup)
+{
+	return nmp_cache_lookup_all (cache, lookup->cache_id_type, &lookup->selector_obj);
+}
+
+const NMPLookup *nmp_lookup_init_obj_type (NMPLookup *lookup,
+                                           NMPObjectType obj_type,
+                                           gboolean visible_only);
+const NMPLookup *nmp_lookup_init_link (NMPLookup *lookup,
+                                       gboolean visible_only);
+const NMPLookup *nmp_lookup_init_link_by_ifname (NMPLookup *lookup,
+                                                 const char *ifname);
+const NMPLookup *nmp_lookup_init_addrroute (NMPLookup *lookup,
+                                            NMPObjectType obj_type,
+                                            int ifindex,
+                                            gboolean visible_only);
+const NMPLookup *nmp_lookup_init_route_visible (NMPLookup *lookup,
+                                                NMPObjectType obj_type,
+                                                int ifindex,
+                                                gboolean with_default,
+                                                gboolean with_non_default);
+const NMPLookup *nmp_lookup_init_route_by_dest (NMPLookup *lookup,
+                                                int addr_family,
+                                                gconstpointer network,
+                                                guint plen,
+                                                guint32 metric);
+
+GArray *nmp_cache_lookup_to_array (const NMDedupMultiHeadEntry *head_entry,
+                                   NMPObjectType obj_type);
+GHashTable *nmp_cache_lookup_to_hash (const NMDedupMultiHeadEntry *head_entry,
+                                      GHashTable *hash);
+
+static inline gboolean
+nmp_cache_iter_next (NMDedupMultiIter *iter, const NMPObject **out_obj)
+{
+	gboolean has_next;
+
+	has_next = nm_dedup_multi_iter_next (iter);
+	if (has_next) {
+		nm_assert (NMP_OBJECT_IS_VALID (iter->current->box->obj));
+		NM_SET_OUT (out_obj, iter->current->box->obj);
+	}
+	return has_next;
+}
+
+static inline gboolean
+nmp_cache_iter_next_link (NMDedupMultiIter *iter, const NMPlatformLink **out_obj)
+{
+	gboolean has_next;
+
+	has_next = nm_dedup_multi_iter_next (iter);
+	if (has_next) {
+		nm_assert (NMP_OBJECT_GET_TYPE (iter->current->box->obj) == NMP_OBJECT_TYPE_LINK);
+		NM_SET_OUT (out_obj, &(((const NMPObject *) iter->current->box->obj)->link));
+	}
+	return has_next;
+}
+
+#define nmp_cache_iter_for_each(iter, head, obj) \
+	for (nm_dedup_multi_iter_init ((iter), \
+	                               (head)); \
+	     nmp_cache_iter_next ((iter), (obj)); \
+	     )
+
+#define nmp_cache_iter_for_each_link(iter, head, obj) \
+	for (nm_dedup_multi_iter_init ((iter), \
+	                               (head)); \
+	     nmp_cache_iter_next_link ((iter), (obj)); \
+	     )
+
 const NMPObject *nmp_cache_find_other_route_for_same_destination (const NMPCache *cache, const NMPObject *route);
 
 const NMPObject *nmp_cache_lookup_link_full (const NMPCache *cache,
@@ -451,9 +477,6 @@ const NMPObject *nmp_cache_lookup_link_full (const NMPCache *cache,
                                              NMLinkType link_type,
                                              NMPObjectMatchFn match_fn,
                                              gpointer user_data);
-GHashTable *nmp_cache_lookup_all_to_hash (const NMPCache *cache,
-                                          NMPCacheId *cache_id,
-                                          GHashTable *hash);
 
 gboolean nmp_cache_link_connected_needs_toggle (const NMPCache *cache, const NMPObject *master, const NMPObject *potential_slave, const NMPObject *ignore_slave);
 const NMPObject *nmp_cache_link_connected_needs_toggle_by_ifindex (const NMPCache *cache, int master_ifindex, const NMPObject *potential_slave, const NMPObject *ignore_slave);
@@ -462,13 +485,71 @@ gboolean nmp_cache_use_udev_get (const NMPCache *cache);
 
 void ASSERT_nmp_cache_is_consistent (const NMPCache *cache);
 
-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);
-NMPCacheOpsType nmp_cache_remove_netlink (NMPCache *cache, const NMPObject *obj, NMPObject **out_obj, gboolean *out_was_visible, NMPCachePreHook pre_hook, gpointer user_data);
-NMPCacheOpsType nmp_cache_update_netlink (NMPCache *cache, NMPObject *obj, NMPObject **out_obj, gboolean *out_was_visible, NMPCachePreHook pre_hook, gpointer user_data);
-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);
-NMPCacheOpsType nmp_cache_update_link_master_connected (NMPCache *cache, int ifindex, NMPObject **out_obj, gboolean *out_was_visible, NMPCachePreHook pre_hook, gpointer user_data);
-
-NMPCache *nmp_cache_new (gboolean use_udev);
+NMPCacheOpsType nmp_cache_remove (NMPCache *cache,
+                                  const NMPObject *obj_needle,
+                                  gboolean equals_by_ptr,
+                                  const NMPObject **out_obj_old);
+NMPCacheOpsType nmp_cache_remove_netlink (NMPCache *cache,
+                                          const NMPObject *obj_needle,
+                                          const NMPObject **out_obj_old,
+                                          const NMPObject **out_obj_new);
+NMPCacheOpsType nmp_cache_update_netlink (NMPCache *cache,
+                                          NMPObject *obj,
+                                          const NMPObject **out_obj_old,
+                                          const NMPObject **out_obj_new);
+NMPCacheOpsType nmp_cache_update_link_udev (NMPCache *cache,
+                                            int ifindex,
+                                            struct udev_device *udevice,
+                                            const NMPObject **out_obj_old,
+                                            const NMPObject **out_obj_new);
+NMPCacheOpsType nmp_cache_update_link_master_connected (NMPCache *cache,
+                                                        int ifindex,
+                                                        const NMPObject **out_obj_old,
+                                                        const NMPObject **out_obj_new);
+
+void nmp_cache_dirty_set_all (NMPCache *cache, NMPObjectType obj_type);
+
+NMPCache *nmp_cache_new (NMDedupMultiIndex *multi_idx, gboolean use_udev);
 void nmp_cache_free (NMPCache *cache);
 
+static inline void
+ASSERT_nmp_cache_ops (const NMPCache *cache,
+                      NMPCacheOpsType ops_type,
+                      const NMPObject *obj_old,
+                      const NMPObject *obj_new)
+{
+#if NM_MORE_ASSERTS
+	nm_assert (cache);
+	nm_assert (obj_old || obj_new);
+	nm_assert (!obj_old || (   NMP_OBJECT_IS_VALID (obj_old)
+	                        && !NMP_OBJECT_IS_STACKINIT (obj_old)
+	                        && nmp_object_is_alive (obj_old)));
+	nm_assert (!obj_new || (   NMP_OBJECT_IS_VALID (obj_new)
+	                        && !NMP_OBJECT_IS_STACKINIT (obj_new)
+	                        && nmp_object_is_alive (obj_new)));
+
+	switch (ops_type) {
+	case NMP_CACHE_OPS_UNCHANGED:
+		nm_assert (obj_old == obj_new);
+		break;
+	case NMP_CACHE_OPS_ADDED:
+		nm_assert (!obj_old && obj_new);
+		break;
+	case NMP_CACHE_OPS_UPDATED:
+		nm_assert (obj_old &&  obj_new && obj_old != obj_new);
+		break;
+	case NMP_CACHE_OPS_REMOVED:
+		nm_assert (obj_old && !obj_new);
+		break;
+	default:
+		nm_assert_not_reached ();
+	}
+
+	nm_assert (obj_new == NULL || obj_old == NULL || nmp_object_id_equal (obj_new, obj_old));
+	nm_assert (!obj_old || !obj_new || NMP_OBJECT_GET_CLASS (obj_old) == NMP_OBJECT_GET_CLASS (obj_new));
+
+	nm_assert (obj_new == nmp_cache_lookup_obj (cache, obj_new ?: obj_old));
+#endif
+}
+
 #endif /* __NMP_OBJECT_H__ */
diff --git a/src/platform/tests/test-nmp-object.c b/src/platform/tests/test-nmp-object.c
index 300a0cb464..24e790c32c 100644
--- a/src/platform/tests/test-nmp-object.c
+++ b/src/platform/tests/test-nmp-object.c
@@ -103,150 +103,141 @@ _nmp_object_equal (const NMPObject *a, const NMPObject *b)
 /*****************************************************************************/
 
 static void
-_assert_cache_multi_lookup_contains (const NMPCache *cache, const NMPCacheId *cache_id, const NMPObject *obj, gboolean contains)
+_assert_cache_multi_lookup_contains (const NMPCache *cache, const NMDedupMultiHeadEntry *head_entry, const NMPObject *obj, gboolean contains)
 {
-	const NMPlatformObject *const *objects;
-	guint i, len;
+	NMDedupMultiIter iter;
 	gboolean found;
+	guint i, len;
+	const NMPObject *o;
 
-	g_assert (cache_id);
 	g_assert (NMP_OBJECT_IS_VALID (obj));
 
 	g_assert (nmp_cache_lookup_obj (cache, obj) == obj);
+	g_assert (!head_entry || (head_entry->len > 0 && c_list_length (&head_entry->lst_entries_head) == head_entry->len));
 
-	objects = nmp_cache_lookup_multi (cache, cache_id, &len);
-
-	g_assert ((len == 0 && !objects) || (len > 0 && objects && !objects[len]));
+	len = head_entry ? head_entry->len : 0;
 
 	found = FALSE;
-	for (i = 0; i < len; i++) {
-		NMPObject *o;
-
-		g_assert (objects[i]);
-		o = NMP_OBJECT_UP_CAST (objects[i]);
+	i = 0;
+	nmp_cache_iter_for_each (&iter,
+	                         head_entry,
+	                         &o) {
 		g_assert (NMP_OBJECT_IS_VALID (o));
-
 		if (obj == o) {
 			g_assert (!found);
 			found = TRUE;
 		}
+		i++;
 	}
 
+	g_assert (len == i);
 	g_assert (!!contains == found);
 }
 
-/*****************************************************************************/
+static void
+_assert_cache_multi_lookup_contains_link (const NMPCache *cache,
+                                          gboolean visible_only,
+                                          const NMPObject *obj,
+                                          gboolean contains)
+{
+	const NMDedupMultiHeadEntry *head_entry;
+	NMPLookup lookup;
 
-typedef struct {
-	NMPCache *cache;
-	NMPCacheOpsType expected_ops_type;
-	const NMPObject *obj_clone;
-	NMPObject *new_clone;
-	gboolean was_visible;
-	gboolean called;
-} _NMPCacheUpdateData;
+	g_assert (cache);
+
+	nmp_lookup_init_link (&lookup, visible_only);
+	head_entry = nmp_cache_lookup (cache, &lookup);
+	_assert_cache_multi_lookup_contains (cache, head_entry, obj, contains);
+}
+
+/*****************************************************************************/
 
 static void
-_nmp_cache_update_hook (NMPCache *cache, const NMPObject *old, const NMPObject *new, NMPCacheOpsType ops_type, gpointer user_data)
+ops_post_check (NMPCache *cache,
+                NMPCacheOpsType ops_type,
+                const NMPObject *obj_old,
+                const NMPObject *obj_new,
+                const NMPObject *obj_new_expected,
+                NMPCacheOpsType expected_ops_type)
 {
-	_NMPCacheUpdateData *data = user_data;
-
-	g_assert (data);
-	g_assert (!data->called);
-	g_assert (data->cache == cache);
+	g_assert (cache);
 
-	g_assert_cmpint (data->expected_ops_type, ==, ops_type);
+	g_assert_cmpint (expected_ops_type, ==, ops_type);
 
 	switch (ops_type) {
 	case NMP_CACHE_OPS_ADDED:
-		g_assert (!old);
-		g_assert (NMP_OBJECT_IS_VALID (new));
-		g_assert (nmp_object_is_alive (new));
-		g_assert (nmp_object_id_equal (data->obj_clone, new));
-		g_assert (nmp_object_equal (data->obj_clone, new));
+		g_assert (!obj_old);
+		g_assert (NMP_OBJECT_IS_VALID (obj_new));
+		g_assert (nmp_object_is_alive (obj_new));
+		g_assert (nmp_object_id_equal (obj_new_expected, obj_new));
+		g_assert (nmp_object_equal (obj_new_expected, obj_new));
 		break;
 	case NMP_CACHE_OPS_UPDATED:
-		g_assert (NMP_OBJECT_IS_VALID (old));
-		g_assert (NMP_OBJECT_IS_VALID (new));
-		g_assert (nmp_object_is_alive (old));
-		g_assert (nmp_object_is_alive (new));
-		g_assert (nmp_object_id_equal (data->obj_clone, new));
-		g_assert (nmp_object_id_equal (data->obj_clone, old));
-		g_assert (nmp_object_id_equal (old, new));
-		g_assert (nmp_object_equal (data->obj_clone, new));
-		g_assert (!nmp_object_equal (data->obj_clone, old));
-		g_assert (!nmp_object_equal (old, new));
+		g_assert (obj_old != obj_new);
+		g_assert (NMP_OBJECT_IS_VALID (obj_old));
+		g_assert (NMP_OBJECT_IS_VALID (obj_new));
+		g_assert (nmp_object_is_alive (obj_old));
+		g_assert (nmp_object_is_alive (obj_new));
+		g_assert (nmp_object_id_equal (obj_new_expected, obj_new));
+		g_assert (nmp_object_id_equal (obj_new_expected, obj_old));
+		g_assert (nmp_object_id_equal (obj_old, obj_new));
+		g_assert (nmp_object_equal (obj_new_expected, obj_new));
+		g_assert (!nmp_object_equal (obj_new_expected, obj_old));
+		g_assert (!nmp_object_equal (obj_old, obj_new));
 		break;
 	case NMP_CACHE_OPS_REMOVED:
-		g_assert (!new);
-		g_assert (NMP_OBJECT_IS_VALID (old));
-		g_assert (nmp_object_is_alive (old));
-		g_assert (nmp_object_id_equal (data->obj_clone, old));
+		g_assert (!obj_new);
+		g_assert (NMP_OBJECT_IS_VALID (obj_old));
+		g_assert (nmp_object_is_alive (obj_old));
+		if (obj_new_expected)
+			g_assert (nmp_object_id_equal (obj_new_expected, obj_old));
+		break;
+	case NMP_CACHE_OPS_UNCHANGED:
+		g_assert (obj_old == obj_new);
+		if (obj_old) {
+			g_assert (NMP_OBJECT_IS_VALID (obj_old));
+			g_assert (nmp_object_is_alive (obj_old));
+			g_assert (nmp_object_equal (obj_old, obj_new));
+			g_assert (nmp_object_id_equal (obj_new_expected, obj_new));
+		} else
+			g_assert (!obj_new_expected);
 		break;
 	default:
 		g_assert_not_reached ();
 	}
-
-	data->was_visible = old ? nmp_object_is_visible (old) : FALSE;
-	data->new_clone = new ? nmp_object_clone (new, FALSE) : NULL;
-	data->called = TRUE;
 }
 
 static void
-_nmp_cache_update_netlink (NMPCache *cache, NMPObject *obj, NMPObject **out_obj, gboolean *out_was_visible, NMPCacheOpsType expected_ops_type)
+_nmp_cache_update_netlink (NMPCache *cache, NMPObject *obj, const NMPObject **out_obj_old, const NMPObject **out_obj_new, NMPCacheOpsType expected_ops_type)
 {
 	NMPCacheOpsType ops_type;
-	NMPObject *obj2;
-	gboolean was_visible;
-	nm_auto_nmpobj NMPObject *obj_clone = nmp_object_clone (obj, FALSE);
-	nm_auto_nmpobj NMPObject *new_clone = NULL;
+	const NMPObject *obj_prev;
 	const NMPObject *obj_old;
-	_NMPCacheUpdateData data = {
-		.cache = cache,
-		.expected_ops_type = expected_ops_type,
-		.obj_clone = obj_clone,
-	};
-
-	obj_old = nmp_cache_lookup_link (cache, obj->object.ifindex);
-	if (obj_old && obj_old->_link.udev.device)
-		obj_clone->_link.udev.device = udev_device_ref (obj_old->_link.udev.device);
-	_nmp_object_fixup_link_udev_fields (obj_clone, nmp_cache_use_udev_get (cache));
+	const NMPObject *obj_new;
+	nm_auto_nmpobj NMPObject *obj_new_expected = NULL;
 
 	g_assert (cache);
 	g_assert (NMP_OBJECT_IS_VALID (obj));
 
-	ops_type = nmp_cache_update_netlink (cache, obj, &obj2, &was_visible, _nmp_cache_update_hook, &data);
+	obj_prev = nmp_cache_lookup_link (cache, obj->object.ifindex);
+	obj_new_expected = nmp_object_clone (obj, FALSE);
+	if (obj_prev && obj_prev->_link.udev.device)
+		obj_new_expected->_link.udev.device = udev_device_ref (obj_prev->_link.udev.device);
+	_nmp_object_fixup_link_udev_fields (&obj_new_expected, NULL, nmp_cache_use_udev_get (cache));
 
-	new_clone = data.new_clone;
+	ops_type = nmp_cache_update_netlink (cache, obj, &obj_old, &obj_new);
+	ops_post_check (cache, ops_type, obj_old, obj_new,
+	                nmp_object_is_alive (obj_new_expected) ? obj_new_expected : NULL,
+	                expected_ops_type);
 
-	g_assert_cmpint (ops_type, ==, expected_ops_type);
-
-	if (ops_type != NMP_CACHE_OPS_UNCHANGED) {
-		g_assert (NMP_OBJECT_IS_VALID (obj2));
-		g_assert (data.called);
-		g_assert_cmpint (data.was_visible, ==, was_visible);
-
-		if (ops_type == NMP_CACHE_OPS_REMOVED)
-			g_assert (!data.new_clone);
-		else {
-			g_assert (data.new_clone);
-			g_assert (nmp_object_equal (obj2, data.new_clone));
-		}
-	} else {
-		g_assert (!data.called);
-		g_assert (!obj2 || was_visible == nmp_object_is_visible (obj2));
-	}
-
-	g_assert (!obj2 || nmp_object_id_equal (obj, obj2));
-	if (ops_type != NMP_CACHE_OPS_REMOVED && obj2)
-		g_assert (nmp_object_equal (obj, obj2));
-
-	if (out_obj)
-		*out_obj = obj2;
+	if (out_obj_new)
+		*out_obj_new = obj_new;
+	else
+		nmp_object_unref (obj_new);
+	if (out_obj_old)
+		*out_obj_old = obj_old;
 	else
-		nmp_object_unref (obj2);
-	if (out_was_visible)
-		*out_was_visible = was_visible;
+		nmp_object_unref (obj_old);
 }
 
 static const NMPlatformLink pl_link_2 = {
@@ -265,168 +256,189 @@ static void
 test_cache_link (void)
 {
 	NMPCache *cache;
-	NMPObject *obj1, *obj2;
+	NMPObject *objm1;
+	const NMPObject *obj_old, *obj_new;
 	NMPObject objs1;
-	gboolean was_visible;
-	NMPCacheId cache_id_storage;
 	struct udev_device *udev_device_2 = g_list_nth_data (global.udev_devices, 0);
 	struct udev_device *udev_device_3 = g_list_nth_data (global.udev_devices, 0);
 	NMPCacheOpsType ops_type;
+	nm_auto_unref_dedup_multi_index NMDedupMultiIndex *multi_idx = NULL;
 
-	cache = nmp_cache_new (nmtst_get_rand_int () % 2);
+	multi_idx = nm_dedup_multi_index_new ();
+
+	cache = nmp_cache_new (multi_idx, nmtst_get_rand_int () % 2);
 
 	/* if we have a link, and don't set is_in_netlink, adding it has no effect. */
-	obj1 = nmp_object_new (NMP_OBJECT_TYPE_LINK, (NMPlatformObject *) &pl_link_2);
-	g_assert (NMP_OBJECT_UP_CAST (&obj1->object) == obj1);
-	g_assert (!nmp_object_is_alive (obj1));
-	_nmp_cache_update_netlink (cache, obj1, &obj2, &was_visible, NMP_CACHE_OPS_UNCHANGED);
+	objm1 = nmp_object_new (NMP_OBJECT_TYPE_LINK, (NMPlatformObject *) &pl_link_2);
+	g_assert (NMP_OBJECT_UP_CAST (&objm1->object) == objm1);
+	g_assert (!nmp_object_is_alive (objm1));
+	_nmp_cache_update_netlink (cache, objm1, &obj_old, &obj_new, NMP_CACHE_OPS_UNCHANGED);
 	ASSERT_nmp_cache_is_consistent (cache);
-	g_assert (!obj2);
-	g_assert (!was_visible);
-	g_assert (!nmp_cache_lookup_obj (cache, obj1));
+	g_assert (!obj_old);
+	g_assert (!obj_new);
+	g_assert (!nmp_cache_lookup_obj (cache, objm1));
 	g_assert (!nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_2.ifindex)));
-	nmp_object_unref (obj1);
+	nmp_object_unref (objm1);
 
 	/* Only when setting @is_in_netlink the link is added. */
-	obj1 = nmp_object_new (NMP_OBJECT_TYPE_LINK, (NMPlatformObject *) &pl_link_2);
-	obj1->_link.netlink.is_in_netlink = TRUE;
-	g_assert (nmp_object_is_alive (obj1));
-	_nmp_cache_update_netlink (cache, obj1, &obj2, &was_visible, NMP_CACHE_OPS_ADDED);
+	objm1 = nmp_object_new (NMP_OBJECT_TYPE_LINK, (NMPlatformObject *) &pl_link_2);
+	objm1->_link.netlink.is_in_netlink = TRUE;
+	g_assert (nmp_object_is_alive (objm1));
+	_nmp_cache_update_netlink (cache, objm1, &obj_old, &obj_new, NMP_CACHE_OPS_ADDED);
 	ASSERT_nmp_cache_is_consistent (cache);
-	g_assert (nmp_object_equal (obj1, obj2));
-	g_assert (!was_visible);
-	g_assert (nmp_cache_lookup_obj (cache, obj1) == obj2);
-	g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_2.ifindex)) == obj2);
-	g_assert (nmp_object_is_visible (obj2));
-	_assert_cache_multi_lookup_contains (cache, nmp_cache_id_init_object_type (&cache_id_storage, NMP_OBJECT_TYPE_LINK, TRUE), obj2, TRUE);
-	_assert_cache_multi_lookup_contains (cache, nmp_cache_id_init_object_type (&cache_id_storage, NMP_OBJECT_TYPE_LINK, FALSE), obj2, TRUE);
-	nmp_object_unref (obj1);
-	nmp_object_unref (obj2);
+	g_assert (!obj_old);
+	g_assert (obj_new);
+	g_assert (objm1 == obj_new);
+	g_assert (nmp_object_equal (objm1, obj_new));
+	g_assert (nmp_cache_lookup_obj (cache, objm1) == obj_new);
+	g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_2.ifindex)) == obj_new);
+	g_assert (nmp_object_is_visible (obj_new));
+	_assert_cache_multi_lookup_contains_link (cache, FALSE, obj_new, TRUE);
+	_assert_cache_multi_lookup_contains_link (cache, TRUE, obj_new, TRUE);
+	nmp_object_unref (objm1);
+	nmp_object_unref (obj_new);
 
 	/* updating the same link with identical value, has no effect. */
-	obj1 = nmp_object_new (NMP_OBJECT_TYPE_LINK, (NMPlatformObject *) &pl_link_2);
-	obj1->_link.netlink.is_in_netlink = TRUE;
-	g_assert (nmp_object_is_alive (obj1));
-	_nmp_cache_update_netlink (cache, obj1, &obj2, &was_visible, NMP_CACHE_OPS_UNCHANGED);
+	objm1 = nmp_object_new (NMP_OBJECT_TYPE_LINK, (NMPlatformObject *) &pl_link_2);
+	objm1->_link.netlink.is_in_netlink = TRUE;
+	g_assert (nmp_object_is_alive (objm1));
+	_nmp_cache_update_netlink (cache, objm1, &obj_old, &obj_new, NMP_CACHE_OPS_UNCHANGED);
 	ASSERT_nmp_cache_is_consistent (cache);
-	g_assert (obj2 != obj1);
-	g_assert (nmp_object_equal (obj1, obj2));
-	g_assert (was_visible);
-	g_assert (nmp_cache_lookup_obj (cache, obj1) == obj2);
-	g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_2.ifindex)) == obj2);
-	nmp_object_unref (obj1);
-	nmp_object_unref (obj2);
+	g_assert (obj_old);
+	g_assert (obj_new);
+	g_assert (obj_new != objm1);
+	g_assert (nmp_object_equal (objm1, obj_new));
+	g_assert (nmp_cache_lookup_obj (cache, objm1) == obj_new);
+	g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_2.ifindex)) == obj_new);
+	nmp_object_unref (objm1);
+	nmp_object_unref (obj_new);
+	nmp_object_unref (obj_new);
 
 	/* remove the link from netlink */
-	obj1 = nmp_object_new (NMP_OBJECT_TYPE_LINK, (NMPlatformObject *) &pl_link_2);
-	g_assert (!nmp_object_is_alive (obj1));
-	_nmp_cache_update_netlink (cache, obj1, &obj2, &was_visible, NMP_CACHE_OPS_REMOVED);
+	objm1 = nmp_object_new (NMP_OBJECT_TYPE_LINK, (NMPlatformObject *) &pl_link_2);
+	g_assert (!nmp_object_is_alive (objm1));
+	_nmp_cache_update_netlink (cache, objm1, &obj_old, &obj_new, NMP_CACHE_OPS_REMOVED);
 	ASSERT_nmp_cache_is_consistent (cache);
-	g_assert (obj2 != obj1);
-	g_assert (was_visible);
-	g_assert (!nmp_cache_lookup_obj (cache, obj1));
+	g_assert (obj_old);
+	g_assert (!obj_new);
+	g_assert (!nmp_cache_lookup_obj (cache, objm1));
 	g_assert (!nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_2.ifindex)));
-	nmp_object_unref (obj1);
-	nmp_object_unref (obj2);
+	nmp_object_unref (objm1);
+	nmp_object_unref (obj_old);
+	nmp_object_unref (obj_new);
 
 	if (udev_device_2) {
 		/* now add the link only with aspect UDEV. */
-		ops_type = nmp_cache_update_link_udev (cache, pl_link_2.ifindex, udev_device_2, &obj2, &was_visible, NULL, NULL);
+		ops_type = nmp_cache_update_link_udev (cache, pl_link_2.ifindex, udev_device_2, &obj_old, &obj_new);
 		ASSERT_nmp_cache_is_consistent (cache);
 		g_assert_cmpint (ops_type, ==, NMP_CACHE_OPS_ADDED);
-		g_assert (!was_visible);
-		g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_2.ifindex)) == obj2);
-		g_assert (!nmp_object_is_visible (obj2));
-		_assert_cache_multi_lookup_contains (cache, nmp_cache_id_init_object_type (&cache_id_storage, NMP_OBJECT_TYPE_LINK, TRUE), obj2, FALSE);
-		_assert_cache_multi_lookup_contains (cache, nmp_cache_id_init_object_type (&cache_id_storage, NMP_OBJECT_TYPE_LINK, FALSE), obj2, TRUE);
-		nmp_object_unref (obj2);
+		g_assert (!obj_old);
+		g_assert (obj_new);
+		g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_2.ifindex)) == obj_new);
+		g_assert (!nmp_object_is_visible (obj_new));
+		_assert_cache_multi_lookup_contains_link (cache, TRUE, obj_new, FALSE);
+		_assert_cache_multi_lookup_contains_link (cache, FALSE, obj_new, TRUE);
+		nmp_object_unref (obj_new);
 	}
 
 	/* add it in netlink too. */
-	obj1 = nmp_object_new (NMP_OBJECT_TYPE_LINK, (NMPlatformObject *) &pl_link_2);
-	obj1->_link.netlink.is_in_netlink = TRUE;
-	g_assert (nmp_object_is_alive (obj1));
-	_nmp_cache_update_netlink (cache, obj1, &obj2, &was_visible, udev_device_2 ? NMP_CACHE_OPS_UPDATED : NMP_CACHE_OPS_ADDED);
+	objm1 = nmp_object_new (NMP_OBJECT_TYPE_LINK, (NMPlatformObject *) &pl_link_2);
+	objm1->_link.netlink.is_in_netlink = TRUE;
+	g_assert (nmp_object_is_alive (objm1));
+	_nmp_cache_update_netlink (cache, objm1, &obj_old, &obj_new, udev_device_2 ? NMP_CACHE_OPS_UPDATED : NMP_CACHE_OPS_ADDED);
 	ASSERT_nmp_cache_is_consistent (cache);
-	g_assert (nmp_object_equal (obj1, obj2));
-	g_assert (!was_visible);
-	g_assert (nmp_cache_lookup_obj (cache, obj1) == obj2);
-	g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_2.ifindex)) == obj2);
-	g_assert (nmp_object_is_visible (obj2));
-	_assert_cache_multi_lookup_contains (cache, nmp_cache_id_init_object_type (&cache_id_storage, NMP_OBJECT_TYPE_LINK, TRUE), obj2, TRUE);
-	_assert_cache_multi_lookup_contains (cache, nmp_cache_id_init_object_type (&cache_id_storage, NMP_OBJECT_TYPE_LINK, FALSE), obj2, TRUE);
-	nmp_object_unref (obj1);
-	nmp_object_unref (obj2);
+	if (udev_device_2) {
+		g_assert (obj_old);
+		g_assert (!nmp_object_is_visible (obj_old));
+	} else
+		g_assert (!obj_old);
+	g_assert (nmp_object_equal (objm1, obj_new));
+	g_assert (nmp_cache_lookup_obj (cache, objm1) == obj_new);
+	g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_2.ifindex)) == obj_new);
+	g_assert (nmp_object_is_visible (obj_new));
+	_assert_cache_multi_lookup_contains_link (cache, TRUE, obj_new, TRUE);
+	_assert_cache_multi_lookup_contains_link (cache, FALSE, obj_new, TRUE);
+	nmp_object_unref (objm1);
+	nmp_object_unref (obj_old);
+	nmp_object_unref (obj_new);
 
 	/* remove again from netlink. */
-	obj1 = nmp_object_new (NMP_OBJECT_TYPE_LINK, (NMPlatformObject *) &pl_link_2);
-	obj1->_link.netlink.is_in_netlink = FALSE;
-	g_assert (!nmp_object_is_alive (obj1));
-	_nmp_cache_update_netlink (cache, obj1, &obj2, &was_visible, udev_device_2 ? NMP_CACHE_OPS_UPDATED : NMP_CACHE_OPS_REMOVED);
+	objm1 = nmp_object_new (NMP_OBJECT_TYPE_LINK, (NMPlatformObject *) &pl_link_2);
+	objm1->_link.netlink.is_in_netlink = FALSE;
+	g_assert (!nmp_object_is_alive (objm1));
+	_nmp_cache_update_netlink (cache, objm1, &obj_old, &obj_new, udev_device_2 ? NMP_CACHE_OPS_UPDATED : NMP_CACHE_OPS_REMOVED);
 	ASSERT_nmp_cache_is_consistent (cache);
-	g_assert (obj2 != obj1);
-	g_assert (was_visible);
+	if (udev_device_2)
+		g_assert (obj_new == objm1);
+	else
+		g_assert (!obj_new);
+	g_assert (obj_old);
+	g_assert (nmp_object_is_alive (obj_old));
 	if (udev_device_2) {
-		g_assert (nmp_cache_lookup_obj (cache, obj1) == obj2);
-		g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_2.ifindex)) == obj2);
-		g_assert (!nmp_object_is_visible (obj2));
-		_assert_cache_multi_lookup_contains (cache, nmp_cache_id_init_object_type (&cache_id_storage, NMP_OBJECT_TYPE_LINK, TRUE), obj2, FALSE);
-		_assert_cache_multi_lookup_contains (cache, nmp_cache_id_init_object_type (&cache_id_storage, NMP_OBJECT_TYPE_LINK, FALSE), obj2, TRUE);
+		g_assert (nmp_cache_lookup_obj (cache, objm1) == obj_new);
+		g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_2.ifindex)) == obj_new);
+		g_assert (!nmp_object_is_visible (obj_new));
+		_assert_cache_multi_lookup_contains_link (cache, TRUE, obj_new, FALSE);
+		_assert_cache_multi_lookup_contains_link (cache, FALSE, obj_new, TRUE);
 	} else {
-		g_assert (nmp_cache_lookup_obj (cache, obj1) == NULL);
+		g_assert (nmp_cache_lookup_obj (cache, objm1) == NULL);
 		g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_2.ifindex)) == NULL);
-		g_assert (nmp_object_is_visible (obj2));
+		g_assert (nmp_object_is_visible (obj_new));
 	}
-	nmp_object_unref (obj1);
-	nmp_object_unref (obj2);
+	nmp_object_unref (objm1);
+	nmp_object_unref (obj_old);
+	nmp_object_unref (obj_new);
 
 	/* now another link only with aspect UDEV. */
 	if (udev_device_3) {
 		/* now add the link only with aspect UDEV. */
-		ops_type = nmp_cache_update_link_udev (cache, pl_link_3.ifindex, udev_device_3, &obj2, &was_visible, NULL, NULL);
+		ops_type = nmp_cache_update_link_udev (cache, pl_link_3.ifindex, udev_device_3, &obj_old, &obj_new);
 		g_assert_cmpint (ops_type, ==, NMP_CACHE_OPS_ADDED);
 		ASSERT_nmp_cache_is_consistent (cache);
-		g_assert (NMP_OBJECT_IS_VALID (obj2));
-		g_assert (!was_visible);
-		g_assert (!nmp_object_is_visible (obj2));
-		g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_3.ifindex)) == obj2);
-		_assert_cache_multi_lookup_contains (cache, nmp_cache_id_init_object_type (&cache_id_storage, NMP_OBJECT_TYPE_LINK, TRUE), obj2, FALSE);
-		_assert_cache_multi_lookup_contains (cache, nmp_cache_id_init_object_type (&cache_id_storage, NMP_OBJECT_TYPE_LINK, FALSE), obj2, TRUE);
-		g_assert_cmpint (obj2->_link.netlink.is_in_netlink, ==, FALSE);
-		g_assert_cmpint (obj2->link.initialized, ==, FALSE);
-		nmp_object_unref (obj2);
+		g_assert (NMP_OBJECT_IS_VALID (obj_new));
+		g_assert (!obj_old);
+		g_assert (!nmp_object_is_visible (obj_new));
+		g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_3.ifindex)) == obj_new);
+		_assert_cache_multi_lookup_contains_link (cache, TRUE, obj_new, FALSE);
+		_assert_cache_multi_lookup_contains_link (cache, FALSE, obj_new, TRUE);
+		g_assert_cmpint (obj_new->_link.netlink.is_in_netlink, ==, FALSE);
+		g_assert_cmpint (obj_new->link.initialized, ==, FALSE);
+		nmp_object_unref (obj_new);
 
 		/* add it in netlink too. */
-		obj1 = nmp_object_new (NMP_OBJECT_TYPE_LINK, (NMPlatformObject *) &pl_link_3);
-		obj1->_link.netlink.is_in_netlink = TRUE;
-		g_assert (nmp_object_is_alive (obj1));
-		_nmp_cache_update_netlink (cache, obj1, &obj2, &was_visible, NMP_CACHE_OPS_UPDATED);
+		objm1 = nmp_object_new (NMP_OBJECT_TYPE_LINK, (NMPlatformObject *) &pl_link_3);
+		objm1->_link.netlink.is_in_netlink = TRUE;
+		g_assert (nmp_object_is_alive (objm1));
+		_nmp_cache_update_netlink (cache, objm1, &obj_old, &obj_new, NMP_CACHE_OPS_UPDATED);
 		ASSERT_nmp_cache_is_consistent (cache);
-		g_assert (obj2 != obj1);
-		g_assert (nmp_object_equal (obj1, obj2));
-		g_assert (!was_visible);
-		g_assert (nmp_cache_lookup_obj (cache, obj1) == obj2);
-		g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_3.ifindex)) == obj2);
-		g_assert (nmp_object_is_visible (obj2));
-		_assert_cache_multi_lookup_contains (cache, nmp_cache_id_init_object_type (&cache_id_storage, NMP_OBJECT_TYPE_LINK, TRUE), obj2, TRUE);
-		_assert_cache_multi_lookup_contains (cache, nmp_cache_id_init_object_type (&cache_id_storage, NMP_OBJECT_TYPE_LINK, FALSE), obj2, TRUE);
-		g_assert_cmpint (obj2->_link.netlink.is_in_netlink, ==, TRUE);
-		g_assert_cmpint (obj2->link.initialized, ==, TRUE);
-		nmp_object_unref (obj1);
-		nmp_object_unref (obj2);
+		g_assert (obj_old);
+		g_assert (obj_new == objm1);
+		g_assert (nmp_object_equal (objm1, obj_new));
+		g_assert (!obj_old || !nmp_object_is_visible (obj_old));
+		g_assert (nmp_cache_lookup_obj (cache, objm1) == obj_new);
+		g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_3.ifindex)) == obj_new);
+		g_assert (nmp_object_is_visible (obj_new));
+		_assert_cache_multi_lookup_contains_link (cache, TRUE, obj_new, TRUE);
+		_assert_cache_multi_lookup_contains_link (cache, FALSE, obj_new, TRUE);
+		g_assert_cmpint (obj_new->_link.netlink.is_in_netlink, ==, TRUE);
+		g_assert_cmpint (obj_new->link.initialized, ==, TRUE);
+		nmp_object_unref (objm1);
+		nmp_object_unref (obj_old);
+		nmp_object_unref (obj_new);
 
 		/* remove UDEV. */
-		ops_type = nmp_cache_update_link_udev (cache, pl_link_3.ifindex, NULL, &obj2, &was_visible, NULL, NULL);
+		ops_type = nmp_cache_update_link_udev (cache, pl_link_3.ifindex, NULL, &obj_old, &obj_new);
 		g_assert_cmpint (ops_type, ==, NMP_CACHE_OPS_UPDATED);
 		ASSERT_nmp_cache_is_consistent (cache);
-		g_assert (was_visible);
-		g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_3.ifindex)) == obj2);
-		g_assert (nmp_object_is_visible (obj2));
-		_assert_cache_multi_lookup_contains (cache, nmp_cache_id_init_object_type (&cache_id_storage, NMP_OBJECT_TYPE_LINK, TRUE), obj2, TRUE);
-		_assert_cache_multi_lookup_contains (cache, nmp_cache_id_init_object_type (&cache_id_storage, NMP_OBJECT_TYPE_LINK, FALSE), obj2, TRUE);
-		g_assert_cmpint (obj2->_link.netlink.is_in_netlink, ==, TRUE);
-		g_assert_cmpint (obj2->link.initialized, ==, !nmp_cache_use_udev_get (cache));
-		nmp_object_unref (obj2);
+		g_assert (obj_old && nmp_object_is_visible (obj_old));
+		g_assert (nmp_cache_lookup_obj (cache, nmp_object_stackinit_id_link (&objs1, pl_link_3.ifindex)) == obj_new);
+		g_assert (nmp_object_is_visible (obj_new));
+		_assert_cache_multi_lookup_contains_link (cache, TRUE, obj_new, TRUE);
+		_assert_cache_multi_lookup_contains_link (cache, FALSE, obj_new, TRUE);
+		g_assert_cmpint (obj_new->_link.netlink.is_in_netlink, ==, TRUE);
+		g_assert_cmpint (obj_new->link.initialized, ==, !nmp_cache_use_udev_get (cache));
+		nmp_object_unref (obj_new);
+		nmp_object_unref (obj_old);
 	}
 
 	nmp_cache_free (cache);