diff --git a/sys/net/route/fib_algo.c b/sys/net/route/fib_algo.c
--- a/sys/net/route/fib_algo.c
+++ b/sys/net/route/fib_algo.c
@@ -525,6 +525,13 @@
 	}
 }
 
+static void
+sync_rib_gen(struct fib_data *fd)
+{
+	FD_PRINTF(LOG_DEBUG, fd, "Sync gen %u -> %u", fd->fd_rh->rnh_gen, fd->fd_rh->rnh_gen_rib);
+	fd->fd_rh->rnh_gen = fd->fd_rh->rnh_gen_rib;
+}
+
 static int64_t
 get_tv_diff_ms(const struct timeval *old_tv, const struct timeval *new_tv)
 {
@@ -680,6 +687,7 @@
 	result = fd->fd_flm->flm_change_rib_items_cb(fd->fd_rh, q, fd->fd_algo_data);
 
 	if (result == FLM_SUCCESS) {
+		sync_rib_gen(fd);
 		for (int i = 0; i < q->count; i++)
 			if (q->entries[i].nh_old)
 				fib_unref_nhop(fd, q->entries[i].nh_old);
@@ -811,6 +819,7 @@
 
 	switch (result) {
 	case FLM_SUCCESS:
+		sync_rib_gen(fd);
 		/* Unref old nexthop on success */
 		if (rc->rc_nh_old != NULL)
 			fib_unref_nhop(fd, rc->rc_nh_old);
@@ -1236,7 +1245,9 @@
 		result = try_setup_fd_instance(flm, rh, prev_fd, &new_fd);
 
 		if ((result == FLM_SUCCESS) && attach) {
-			if (!fib_set_datapath_ptr(new_fd, &new_fd->fd_dp))
+			if (fib_set_datapath_ptr(new_fd, &new_fd->fd_dp))
+				sync_rib_gen(new_fd);
+			else
 				result = FLM_REBUILD;
 		}
 
diff --git a/sys/net/route/route_ctl.c b/sys/net/route/route_ctl.c
--- a/sys/net/route/route_ctl.c
+++ b/sys/net/route/route_ctl.c
@@ -808,7 +808,7 @@
 	rt->rte_flags &= ~RTF_UP;
 
 	/* Finalize notification */
-	rnh->rnh_gen++;
+	rib_bump_gen(rnh);
 	rnh->rnh_prefixes--;
 
 	rc->rc_cmd = RTM_DELETE;
@@ -1060,7 +1060,7 @@
 			tmproutes_update(rnh, rt);
 
 		/* Finalize notification */
-		rnh->rnh_gen++;
+		rib_bump_gen(rnh);
 		rnh->rnh_prefixes++;
 
 		rc->rc_cmd = RTM_ADD;
@@ -1116,7 +1116,7 @@
 	}
 
 	/* Finalize notification */
-	rnh->rnh_gen++;
+	rib_bump_gen(rnh);
 	if (rnd->rnd_nhop == NULL)
 		rnh->rnh_prefixes--;
 
diff --git a/sys/net/route/route_var.h b/sys/net/route/route_var.h
--- a/sys/net/route/route_var.h
+++ b/sys/net/route/route_var.h
@@ -60,7 +60,7 @@
 	rn_walktree_t		*rnh_walktree;	/* traverse tree */
 	rn_walktree_from_t	*rnh_walktree_from; /* traverse tree below a */
 	rnh_preadd_entry_f_t	*rnh_preadd;	/* hook to alter record prior to insertion */
-	rt_gen_t		rnh_gen;	/* generation counter */
+	rt_gen_t		rnh_gen;	/* datapath generation counter */
 	int			rnh_multipath;	/* multipath capable ? */
 	struct radix_node	rnh_nodes[3];	/* empty tree for common case */
 	struct rmlock		rib_lock;	/* config/data path lock */
@@ -71,6 +71,9 @@
 	struct callout		expire_callout;	/* Callout for expiring dynamic routes */
 	time_t			next_expire;	/* Next expire run ts */
 	uint32_t		rnh_prefixes;	/* Number of prefixes */
+#ifdef FIB_ALGO
+	rt_gen_t		rnh_gen_rib;	/* rib generation counter */
+#endif
 	uint32_t		rib_dying:1;	/* rib is detaching */
 	uint32_t		rib_algo_fixed:1;/* fixed algorithm */
 	struct nh_control	*nh_control;	/* nexthop subsystem data */
@@ -116,6 +119,16 @@
 _Static_assert(__offsetof(struct route, ro_dst) == __offsetof(_ro_new, _dst_new),\
 		"ro_dst and " #_dst_new " are at different offset")
 
+static inline void
+rib_bump_gen(struct rib_head *rnh)
+{
+#ifdef FIB_ALGO
+	rnh->rnh_gen_rib++;
+#else
+	rnh->rnh_gen++;
+#endif
+}
+
 struct rib_head *rt_tables_get_rnh(uint32_t table, sa_family_t family);
 int rt_getifa_fib(struct rt_addrinfo *info, u_int fibnum);
 struct rib_cmd_info;