From: Theo Buehler <tb@theobuehler.org>
Subject: Re: bgpd: introduce bin_of from malloc to size various things
To: tech@openbsd.org
Date: Tue, 16 Dec 2025 16:22:06 +0100

On Tue, Dec 16, 2025 at 03:53:13PM +0100, Claudio Jeker wrote:
> On Tue, Dec 16, 2025 at 03:45:57PM +0100, Claudio Jeker wrote:
> > Another diff from my bigger adj-rib-out rewrite.
> > 
> > This introduces a new set of functions to size various dynamic arrays in
> > bgpd. For now attributes and communities. I looked at sets but that code
> > needs some rework to better fit into this.
> > 
> > Happy to repaint any bikesheds in this madness :)
> 
> Better version below that has the reallocarray fixed in the attr_optadd
> case.

Fine with this. Zap the trailing empty line in util.c perhaps and the
comment linking the blog could use some KNF.

ok tb

> -- 
> :wq Claudio
> 
> Index: bgpd.h
> ===================================================================
> RCS file: /cvs/src/usr.sbin/bgpd/bgpd.h,v
> diff -u -p -r1.526 bgpd.h
> --- bgpd.h	11 Dec 2025 12:18:27 -0000	1.526
> +++ bgpd.h	16 Dec 2025 14:33:41 -0000
> @@ -1674,6 +1674,9 @@ struct sockaddr	*addr2sa(const struct bg
>  void		 sa2addr(struct sockaddr *, struct bgpd_addr *, uint16_t *);
>  const char	*get_baudrate(unsigned long long, char *);
>  
> +unsigned int	 bin_of_attrs(unsigned int);
> +unsigned int	 bin_of_communities(unsigned int);
> +
>  /* flowspec.c */
>  int	flowspec_valid(const uint8_t *, int, int);
>  int	flowspec_cmp(const uint8_t *, int, const uint8_t *, int, int);
> Index: rde_attr.c
> ===================================================================
> RCS file: /cvs/src/usr.sbin/bgpd/rde_attr.c,v
> diff -u -p -r1.139 rde_attr.c
> --- rde_attr.c	4 Nov 2025 14:43:22 -0000	1.139
> +++ rde_attr.c	16 Dec 2025 14:48:42 -0000
> @@ -97,7 +97,7 @@ attr_optadd(struct rde_aspath *asp, uint
>  {
>  	uint8_t		 l;
>  	struct attr	*a, *t;
> -	void		*p;
> +	struct attr	**p;
>  	uint64_t	 h;
>  
>  	/* attribute allowed only once */
> @@ -136,14 +136,14 @@ attr_optadd(struct rde_aspath *asp, uint
>  	if (asp->others_len == UCHAR_MAX)
>  		fatalx("attr_optadd: attribute overflow");
>  
> -	asp->others_len++;
> -	if ((p = reallocarray(asp->others,
> -	    asp->others_len, sizeof(struct attr *))) == NULL)
> +	l = bin_of_attrs(asp->others_len + 1);
> +	if ((p = reallocarray(asp->others, l, sizeof(struct attr *))) == NULL)
>  		fatal("%s", __func__);
> +	memset(&p[asp->others_len], 0, (l - asp->others_len) * sizeof(*p));
>  	asp->others = p;
> +	asp->others[asp->others_len] = a;
> +	asp->others_len = l;
>  
> -	/* l stores the size of others before resize */
> -	asp->others[l] = a;
>  	return (0);
>  }
>  
> Index: rde_community.c
> ===================================================================
> RCS file: /cvs/src/usr.sbin/bgpd/rde_community.c,v
> diff -u -p -r1.20 rde_community.c
> --- rde_community.c	16 Dec 2025 12:08:11 -0000	1.20
> +++ rde_community.c	16 Dec 2025 13:27:59 -0000
> @@ -225,12 +225,13 @@ insert_community(struct rde_community *c
>  
>  	if (comm->nentries + 1 > comm->size) {
>  		struct community *new;
> -		int newsize = comm->size + 8;
> +		int newsize = bin_of_communities(comm->nentries + 1);
>  
>  		if ((new = reallocarray(comm->communities, newsize,
>  		    sizeof(*new))) == NULL)
>  			fatal(__func__);
> -		memset(&new[comm->size], 0, sizeof(*new) * 8);
> +		memset(&new[comm->size], 0,
> +		    sizeof(*new) * (newsize - comm->size));
>  		comm->communities = new;
>  		comm->size = newsize;
>  	}
> Index: util.c
> ===================================================================
> RCS file: /cvs/src/usr.sbin/bgpd/util.c,v
> diff -u -p -r1.96 util.c
> --- util.c	23 Oct 2025 18:55:30 -0000	1.96
> +++ util.c	16 Dec 2025 14:37:53 -0000
> @@ -22,6 +22,7 @@
>  #include <arpa/inet.h>
>  #include <endian.h>
>  #include <errno.h>
> +#include <limits.h>
>  #include <netdb.h>
>  #include <stdlib.h>
>  #include <stdio.h>
> @@ -1295,3 +1296,45 @@ get_baudrate(unsigned long long baudrate
>  
>  	return (bbuf);
>  }
> +
> +/* internal functions needed for bucket sizing, stolen from omalloc.c */
> +
> +/* using built-in function version */
> +__attribute__((const)) static inline unsigned int
> +lb(unsigned int x)
> +{
> +	/* I need an extension just for integer-length (: */
> +	return (sizeof(x) * CHAR_BIT - 1) - __builtin_clz(x);
> +}
> +
> +/* https://pvk.ca/Blog/2015/06/27/linear-log-bucketing-fast-versatile-simple/
> +   via Tony Finch */
> +static inline unsigned int
> +bin_of(unsigned int size, unsigned int linear, unsigned int subbin)
> +{
> +	unsigned int mask, rounded, rounded_size;
> +	unsigned int n_bits, shift;
> +
> +	n_bits = lb(size | (1U << linear));
> +	shift = n_bits - subbin;
> +	mask = (1U << shift) - 1;
> +	rounded = size + mask; /* XXX: overflow. */
> +
> +	rounded_size = rounded & ~mask;
> +	return rounded_size;
> +}
> +
> +unsigned int
> +bin_of_attrs(unsigned int count)
> +{
> +	/* 4, 8, 12, ... 60, 64, 72, 80, ... */
> +	return bin_of(count, 5, 3);
> +}
> +
> +unsigned int
> +bin_of_communities(unsigned int count)
> +{
> +	/* 8, 16, 24, ... 56, 64, 80, 96, ... */
> +	return bin_of(count, 5, 2);
> +}
> +
>