up_generate_addpath() is the only user of PREFIX_ADJOUT_FLAG_STALE.

Instead of marking prefixes with PREFIX_ADJOUT_FLAG_STALE
up_generate_addpath() can use a local array of path ids to track which
paths were present at the start of the call, clear the path id during
updates and then add then end remove all paths that are still present in
the list. 

While this does a lot of linear walks I doubt this matters. The number of
paths is normally very small and so this linear search is all cached.
It is possible to further optimize this by also tracking the adjout_prefix
pointer to drop the adjout_prefix_get() call at the end.

This also uses a fixed maximum of 2000 paths which is more than a
magnitude more than the amount the nlnog looking glass needs. Which is
AFAIK the biggest system using addpath. Normally people will limit the
amounts of selected paths to a handful.

-- 
:wq Claudio

Index: rde.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde.h,v
diff -u -p -r1.332 rde.h
--- rde.h	13 Dec 2025 19:26:17 -0000	1.332
+++ rde.h	14 Dec 2025 06:30:22 -0000
@@ -324,8 +324,7 @@ struct adjout_prefix {
 	uint32_t			 path_id_tx;
 	uint8_t			 	 flags;
 };
-#define	PREFIX_ADJOUT_FLAG_STALE	0x01	/* stale entry (for addpath) */
-#define	PREFIX_ADJOUT_FLAG_LOCKED	0x20	/* locked by rib walker */
+#define	PREFIX_ADJOUT_FLAG_LOCKED	0x01	/* locked by rib walker */
 
 struct pend_attr {
 	TAILQ_ENTRY(pend_attr)		 entry;
Index: rde_adjout.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_adjout.c,v
diff -u -p -r1.12 rde_adjout.c
--- rde_adjout.c	13 Dec 2025 19:26:17 -0000	1.12
+++ rde_adjout.c	14 Dec 2025 06:30:22 -0000
@@ -522,7 +522,6 @@ adjout_prefix_update(struct adjout_prefi
 		    attrs->communities) &&
 		    path_equal(&state->aspath, attrs->aspath)) {
 			/* nothing changed */
-			p->flags &= ~PREFIX_ADJOUT_FLAG_STALE;
 			return;
 		}
 
@@ -531,9 +530,6 @@ adjout_prefix_update(struct adjout_prefi
 		peer->stats.prefix_out_cnt--;
 	}
 
-	/* clear PREFIX_ADJOUT_FLAG_STALE for up_generate_addpath() */
-	p->flags &= ~PREFIX_ADJOUT_FLAG_STALE;
-
 	/* update path_id_tx now that the prefix is unlinked */
 	if (p->path_id_tx != path_id_tx) {
 		/* path_id_tx is part of the index so remove and re-insert p */
@@ -573,9 +569,6 @@ adjout_prefix_destroy(struct rde_peer *p
 		adjout_prefix_unlink(p, peer);
 		peer->stats.prefix_out_cnt--;
 	}
-
-	/* clear PREFIX_ADJOUT_FLAG_STALE just in case */
-	p->flags &= ~PREFIX_ADJOUT_FLAG_STALE;
 
 	if (!prefix_is_locked(p)) {
 		RB_REMOVE(prefix_index, &peer->adj_rib_out, p);
Index: rde_update.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_update.c,v
diff -u -p -r1.189 rde_update.c
--- rde_update.c	12 Dec 2025 21:42:58 -0000	1.189
+++ rde_update.c	14 Dec 2025 07:38:50 -0000
@@ -258,15 +258,19 @@ void
 up_generate_addpath(struct rde_peer *peer, struct rib_entry *re)
 {
 	struct prefix		*new;
-	struct adjout_prefix	*head, *p, *np;
+	struct adjout_prefix	*head, *p;
+	uint32_t		addpath_prefix_list[2000];	/* XXX */
 	int			maxpaths = 0, extrapaths = 0, extra;
 	int			checkmode = 1;
+	unsigned int		pidx = 0, i;
 
+	/* collect all current paths */
 	head = adjout_prefix_first(peer, re->prefix);
-
-	/* mark all paths as stale */
-	for (p = head; p != NULL; p = adjout_prefix_next(peer, p))
-		p->flags |= PREFIX_ADJOUT_FLAG_STALE;
+	for (p = head; p != NULL; p = adjout_prefix_next(peer, p)) {
+		addpath_prefix_list[pidx++] = p->path_id_tx;
+		if (pidx >= nitems(addpath_prefix_list))
+			fatalx("too many addpath paths to select from");
+	}
 
 	/* update paths */
 	new = prefix_best(re);
@@ -316,6 +320,12 @@ up_generate_addpath(struct rde_peer *pee
 		case UP_OK:
 			maxpaths++;
 			extrapaths += extra;
+			for (i = 0; i < pidx; i++) {
+				if (addpath_prefix_list[i] == new->path_id_tx) {
+					addpath_prefix_list[i] = 0;
+					break;
+				}
+			}
 			break;
 		case UP_FILTERED:
 		case UP_EXCLUDED:
@@ -332,10 +342,13 @@ up_generate_addpath(struct rde_peer *pee
 	}
 
 	/* withdraw stale paths */
-	for (p = head; p != NULL; p = np) {
-		np = adjout_prefix_next(peer, p);
-		if (p->flags & PREFIX_ADJOUT_FLAG_STALE)
-			adjout_prefix_withdraw(peer, p);
+	for (i = 0; i < pidx; i++) {
+		if (addpath_prefix_list[i] != 0) {
+			p = adjout_prefix_get(peer, addpath_prefix_list[i],
+			    re->prefix);
+			if (p != NULL)
+				adjout_prefix_withdraw(peer, p);
+		}
 	}
 }