From: Theo Buehler <tb@theobuehler.org>
Subject: Re: bgpd: bring back up_generate_addpath_all using the rib entry queue
To: tech@openbsd.org
Date: Thu, 16 Jul 2026 07:09:24 +0200

On Wed, Jul 15, 2026 at 11:04:36PM +0200, Claudio Jeker wrote:
> 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.

ok tb

> -- 
> :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 */
>