From: Claudio Jeker <cjeker@diehard.n-r-g.com>
Subject: Re: bgpd: introduce bin_of from malloc to size various things
To: tech@openbsd.org
Date: Tue, 16 Dec 2025 15:53:13 +0100

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.
-- 
: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);
+}
+