From: Claudio Jeker <cjeker@diehard.n-r-g.com>
Subject: bgpd: bring back up_generate_addpath_all using the rib entry queue
To: tech@openbsd.org
Date: Wed, 15 Jul 2026 23:04:36 +0200

add-path send all can take a fair amount of shortcuts compared to the
other add-path send modes. The rib entry queue (struct pq_entry) holds
all the information to update the adj-rib-out.

For general updates just walk the pq list and insert / withdraw all
paths. A path can only be once on the list so the code just needs to
walk it and call up_process_prefix for updates. If up_process_prefix()
returns UP_FILTERED or UP_EXCLUDED then try to withdraw the prefix. This
uses the same codepath as for any withdraw in the queue.

A version of this is running on the NLNOG ring looking glass with good
success.
-- 
:wq Claudio

Index: rde.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde.h,v
diff -u -p -r1.358 rde.h
--- rde.h	15 Jul 2026 11:59:27 -0000	1.358
+++ rde.h	15 Jul 2026 20:43:45 -0000
@@ -321,6 +321,12 @@ struct prefix {
 #define	NEXTHOP_MASK		0x0f
 #define	NEXTHOP_VALID		0x80
 
+struct pq_entry {
+	TAILQ_ENTRY(pq_entry)	 entry;
+	struct prefix		*p;	/* NULL for withdraws */
+	uint32_t		 path_id_tx;
+};
+
 struct adjout_attr {
 	uint64_t		 hash;
 	struct rde_aspath	*aspath;
Index: rde_rib.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_rib.c,v
diff -u -p -r1.302 rde_rib.c
--- rde_rib.c	2 Jul 2026 07:40:12 -0000	1.302
+++ rde_rib.c	15 Jul 2026 20:43:45 -0000
@@ -41,12 +41,6 @@ uint16_t rib_size;
 struct rib **ribs;
 struct rib flowrib = { .id = 1, .tree = RB_INITIALIZER(&flowrib.tree) };
 
-struct pq_entry {
-	TAILQ_ENTRY(pq_entry)	 entry;
-	struct prefix		*p;	/* NULL for withdraws */
-	uint32_t		 path_id_tx;
-};
-
 struct rib_entry *rib_add(struct rib *, struct pt_entry *);
 static inline int rib_compare(const struct rib_entry *,
 			const struct rib_entry *);
Index: rde_update.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_update.c,v
diff -u -p -r1.201 rde_update.c
--- rde_update.c	15 Jul 2026 11:59:27 -0000	1.201
+++ rde_update.c	15 Jul 2026 20:43:45 -0000
@@ -367,51 +367,44 @@ void
 up_generate_addpath_all(struct rde_peer *peer, struct rib_entry *re,
     enum eval_mode mode)
 {
-#if 0
-	/* XXX needs to be rewritten */
 	struct adjout_prefix	*p;
+	struct pt_entry		*pte;
+	struct pq_entry		*pq;
 
 	/*
-	 * If old and new are NULL then re-insert all prefixes from re,
-	 * use up_generate_addpath() for that.
+	 * If this is a sync or reeval of all prefixes from re,
+	 * then use up_generate_addpath().
 	 */
-	if (old_pathid_tx == 0 && new == NULL) {
+	if (mode == EVAL_SYNC || mode == EVAL_REEVAL) {
 		up_generate_addpath(peer, re, mode);
 		return;
 	}
 
-	if (new != NULL && !prefix_eligible(new)) {
-		/* only allow valid prefixes */
-		new = NULL;
-	}
-
-	if (new != NULL) {
-		/* add new path */
-		switch (up_process_prefix(peer, new, (void *)-1, mode)) {
-		case UP_OK:
-			/* don't remove old if an existing prefix was updated */
-			if (old_pathid_tx == new->path_id_tx)
-				old_pathid_tx = 0;
-			break;
-		case UP_FILTERED:
-		case UP_EXCLUDED:
-			break;
-		case UP_ERR_LIMIT:
-			/* just give up */
-			return;
+	pte = re->prefix;
+	TAILQ_FOREACH(pq, &re->pq_head, entry) {
+		if (pq->p != NULL && prefix_eligible(pq->p)) {
+			/* add new path */
+			switch (up_process_prefix(peer, pq->p, (void *)-1,
+			    mode)) {
+			case UP_OK:
+				/* update processed, go to next */
+				continue;
+			case UP_FILTERED:
+			case UP_EXCLUDED:
+				/* update needs to be withdrawn */
+				break;
+			case UP_ERR_LIMIT:
+				/* just give up */
+				return;
+			}
 		}
-	}
 
-	if (old_pathid_tx != 0) {
-		/* withdraw old path */
-		p = adjout_prefix_get(peer, old_pathid_tx, re->prefix);
+		/* prefix was withdrawn or got filtered, withdraw from adjout */
+		p = adjout_prefix_get(peer, pq->path_id_tx, pte);
 		if (p != NULL)
 			adjout_prefix_withdraw(peer, re->prefix, p,
 			    mode == EVAL_SYNC);
 	}
-#else
-	up_generate_addpath(peer, re, mode);
-#endif
 }
 
 /* send a default route to the specified peer, always force the update out */