From: Claudio Jeker <cjeker@diehard.n-r-g.com>
Subject: Re: bgpd: introduce pending attr and prefix queues
To: Theo Buehler <tb@theobuehler.org>
Cc: tech@openbsd.org
Date: Wed, 10 Dec 2025 11:44:19 +0100

On Wed, Dec 10, 2025 at 11:08:23AM +0100, Theo Buehler wrote:
> On Thu, Dec 04, 2025 at 05:14:15PM +0100, Claudio Jeker wrote:
> > Implement a per-peer pending prefix queue and lookup table and 
> > a pending attribute queue and lookup table. 
> > 
> > Withdraws just end up in the peer pending prefix queue while for updates
> > the prefix is queued on a pending attribute entry which itself is queued
> > on the peer. This allows to aggregate multiple prefixes into a single 
> > UPDATE message. When prefixes are added check the lookup table if there
> > is already an object. In such a case the prefix is first dequeued and then 
> > readded. pend_prefix_add() is therefor a bit fiddly.
> > 
> > If the attr pointer in struct pend_prefix is NULL then it is a withdraw.
> > The pend_attr needs to hold the aid so prefixes end up on the right queue.
> > If the attrs pointer is NULL the pend_attr is actually the End-of-RIB
> > marker.
> > 
> > This replaces the red-black tree contraption used right now. Which is a
> > big preformance bottleneck.
> 
> It's a tricky diff with all the decoupling deep in the guts of everything,
> but overall it looks like a clear win. Not only due to replacing expensive
> RB operations but also because largely independent logic becomes more
> isolated and therfore easier to follow. pend_prefix_add() is a bit of an
> exception there and indeed fiddly. Also, fewer magic flags is always good.
> 
> There are a ton of possible side effects that are hard to evaluate in full
> detail but I failed to spot issues.

I agree, this is a big change. I hope I thought of all the side effects in
the old code. My goal was to reduce side effects as much as possible in
this version.
 
> I've spent quite a bit of time on the various parts of this diff and what
> the changes do and I think I've crossed the point of diminishing returns.
> Let's get it in and see how it works out.
> 
> ok tb
> 
> A few very minor things inline.

See below.

> >  static void
> > @@ -3115,13 +3116,13 @@ rde_dump_adjout_upcall(struct adjout_pre
> >  {
> >  	struct rde_dump_ctx	*ctx = ptr;
> >  	struct rde_peer		*peer;
> > +	struct adjout_attr	*attrs;
> >  
> >  	if ((peer = peer_get(ctx->peerid)) == NULL)
> >  		return;
> > -	if (p->flags & PREFIX_ADJOUT_FLAG_WITHDRAW)
> > -		return;
> >  
> > -	rde_dump_adjout_filter(peer, p, &ctx->req);
> > +	attrs = p->attrs;
> > +	rde_dump_adjout_filter(peer, p, attrs, &ctx->req);
> 
> I'm not sure what the attrs variable buys us here, but maybe that's
> preparing an upcoming change. You do the same in peer_blast_upcall()
> and it looks a bit odd to me.

Yes, this interface will change a few more times that's why it is strange
like this. I hope by the end I cleaned up all of that again :)
 
> > Index: bgpd/rde.h
> > ===================================================================
> > RCS file: /cvs/src/usr.sbin/bgpd/rde.h,v
> > diff -u -p -r1.327 rde.h
> > --- bgpd/rde.h	2 Dec 2025 13:03:35 -0000	1.327
> > +++ bgpd/rde.h	4 Dec 2025 15:58:51 -0000
> > @@ -27,6 +27,7 @@
> >  
> >  #include "bgpd.h"
> >  #include "log.h"
> > +#include "chash.h"
> 
> I'd sort these alphabetically

Done.
 
> > @@ -84,8 +89,10 @@ struct rde_peer {
> >  	struct capabilities		 capa;
> >  	struct addpath_eval		 eval;
> >  	struct prefix_index		 adj_rib_out;
> > -	struct prefix_tree		 updates[AID_MAX];
> > -	struct prefix_tree		 withdraws[AID_MAX];
> > +	struct pend_prefix_hash		 pend_prefixes;
> > +	struct pend_attr_hash		 pend_attrs;
> > +	struct pend_attr_queue		 updates[AID_MAX];
> > +	struct pend_prefix_queue	 withdraws[AID_MAX];
> 
> The order is slightly strange but I understand why you did it this way.
 
It feels like the logical order to me (but I started with pend_prefixes
and so I'm biased).
I reshuffled them now like this:
        struct pend_attr_queue           updates[AID_MAX];
        struct pend_prefix_queue         withdraws[AID_MAX];
        struct pend_attr_hash            pend_attrs;
        struct pend_prefix_hash          pend_prefixes;

> > @@ -364,38 +554,28 @@ adjout_prefix_update(struct adjout_prefi
> >  			fatalx("%s: RB index invariant violated", __func__);
> >  	}
> >  
> > -	if ((p->flags & (PREFIX_ADJOUT_FLAG_WITHDRAW |
> > -	    PREFIX_ADJOUT_FLAG_DEAD)) == 0) {
> > +	if ((p->flags & (PREFIX_ADJOUT_FLAG_DEAD)) == 0) {
> 
> extra parens around PREFIX_ADJOUT_FLAG_DEAD
 
Fixed

-- 
:wq Claudio