Adjust pathid_assign() to be much faster in the common case.

Use a per peer path_id_tx to assign to paths received from none add-path
enabled peers. This skips two extra walks of the RIB prefix list and is
a big speed-up when there are many regular sessions. If the session uses
add-path recv then the old way of assigning random path_ids needs to be
used.

With input and OK tb@

3 files changed, 44 insertions, 15 deletions

diff --git a/usr.sbin/bgpd/rde.c b/usr.sbin/bgpd/rde.c
index c3c6d05ee06..2941db9f941 100644
--- a/usr.sbin/bgpd/rde.c
+++ b/usr.sbin/bgpd/rde.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.c,v 1.576 2022/09/12 10:03:17 claudio Exp $ */
+/*	$OpenBSD: rde.c,v 1.577 2022/09/21 10:39:17 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -1607,28 +1607,38 @@ pathid_conflict(struct rib_entry *re, uint32_t pathid)
 	return 0;
 }
 
+/*
+ * Assign a send side path_id to all paths.
+ */
 static uint32_t
 pathid_assign(struct rde_peer *peer, uint32_t path_id,
     struct bgpd_addr *prefix, uint8_t prefixlen)
 {
 	struct rib_entry *re;
-	struct prefix *p = NULL;
 	uint32_t path_id_tx;
 
-	/*
-	 * Assign a send side path_id to all paths.
-	 */
+	/* If peer has no add-path use the per peer path_id */
+	if (!peer_has_add_path(peer, prefix->aid, CAPA_AP_RECV))
+		return peer->path_id_tx;
+
+	/* peer uses add-path, therefore new path_ids need to be assigned */
 	re = rib_get(rib_byid(RIB_ADJ_IN), prefix, prefixlen);
-	if (re != NULL)
+	if (re != NULL) {
+		struct prefix *p;
+
 		p = prefix_bypeer(re, peer, path_id);
-	if (p != NULL)
-		path_id_tx = p->path_id_tx;
-	else {
-		do {
-			/* assign new local path_id */
-			path_id_tx = arc4random();
-		} while (pathid_conflict(re, path_id_tx));
+		if (p != NULL)
+			return p->path_id_tx;
 	}
+
+	/*
+	 * Assign new local path_id, must be an odd number.
+	 * Even numbers are used by the per peer path_id_tx.
+	 */
+	do {
+		path_id_tx = arc4random() | 1;
+	} while (pathid_conflict(re, path_id_tx));
+
 	return path_id_tx;
 }
 
diff --git a/usr.sbin/bgpd/rde.h b/usr.sbin/bgpd/rde.h
index 3930b435ae0..231dac6c242 100644
--- a/usr.sbin/bgpd/rde.h
+++ b/usr.sbin/bgpd/rde.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde.h,v 1.271 2022/09/12 10:03:17 claudio Exp $ */
+/*	$OpenBSD: rde.h,v 1.272 2022/09/21 10:39:17 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org> and
@@ -99,6 +99,7 @@ struct rde_peer {
 	uint32_t			 remote_bgpid; /* host byte order! */
 	uint32_t			 up_nlricnt;
 	uint32_t			 up_wcnt;
+	uint32_t			 path_id_tx;
 	enum peer_state			 state;
 	enum export_type		 export_type;
 	uint16_t			 loc_rib_id;
diff --git a/usr.sbin/bgpd/rde_peer.c b/usr.sbin/bgpd/rde_peer.c
index 7964405495e..03659415c3d 100644
--- a/usr.sbin/bgpd/rde_peer.c
+++ b/usr.sbin/bgpd/rde_peer.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rde_peer.c,v 1.23 2022/09/01 13:23:24 claudio Exp $ */
+/*	$OpenBSD: rde_peer.c,v 1.24 2022/09/21 10:39:17 claudio Exp $ */
 
 /*
  * Copyright (c) 2019 Claudio Jeker <claudio@openbsd.org>
@@ -147,6 +147,7 @@ struct rde_peer *
 peer_add(uint32_t id, struct peer_config *p_conf)
 {
 	struct rde_peer		*peer;
+	int			 conflict;
 
 	if ((peer = peer_get(id))) {
 		memcpy(&peer->conf, p_conf, sizeof(struct peer_config));
@@ -168,6 +169,23 @@ peer_add(uint32_t id, struct peer_config *p_conf)
 	peer->flags = peer->conf.flags;
 	SIMPLEQ_INIT(&peer->imsg_queue);
 
+	/*
+	 * Assign an even random unique transmit path id.
+	 * Odd path_id_tx numbers are for peers using add-path recv.
+	 */
+	do {
+		struct rde_peer *p;
+
+		conflict = 0;
+		peer->path_id_tx = arc4random() << 1;
+		RB_FOREACH(p, peer_tree, &peertable) {
+			if (p->path_id_tx == peer->path_id_tx) {
+				conflict = 1;
+				break;
+			}
+		}
+	} while (conflict);
+
 	if (RB_INSERT(peer_tree, &peertable, peer) != NULL)
 		fatalx("rde peer table corrupted");