Re: kern/60340: npf(4): quadratic-time state/config export

[Taylor R Campbell <riastradh%NetBSD.org@localhost>]

Candidate fix attached, untested -- need to construct a reproducer
with a gigantic state table to verify that it doesn't provoke
quadratic-time export.

# HG changeset patch
# User Taylor R Campbell <riastradh%NetBSD.org@localhost>
# Date 1781815285 0
#      Thu Jun 18 20:41:25 2026 +0000
# Branch trunk
# Node ID 7b5e16fb12943b9c83a6e1cec19c5dd3002dfc57
# Parent  babdf5c7e2cbe4d552248d2f38ead15e92b0b64f
# EXP-Topic riastradh-pr60340-nvlistquadtime
WIP: nvlist(9): Avoid quadratic-time array construction.

We could do this doubling in realloc(9) itself but that might have
nontrivial downstream consequences for other kernel users.

PR kern/60340: npf(4): quadratic-time state/config export

diff -r babdf5c7e2cb -r 7b5e16fb1294 sys/external/bsd/libnv/dist/nvpair.c
--- a/sys/external/bsd/libnv/dist/nvpair.c	Tue Jun 16 23:37:48 2026 +0000
+++ b/sys/external/bsd/libnv/dist/nvpair.c	Thu Jun 18 20:41:25 2026 +0000
@@ -113,6 +113,7 @@ struct nvpair {
 	uint64_t	 nvp_data;
 	size_t		 nvp_datasize;
 	size_t		 nvp_nitems;	/* Used only for array types. */
+	size_t		 nvp_nalloc;	/* Used only for array types. */
 	nvlist_t	*nvp_list;
 	TAILQ_ENTRY(nvpair) nvp_next;
 };
@@ -161,6 +162,7 @@ nvpair_allocv(const char *name, int type
 		nvp->nvp_data = data;
 		nvp->nvp_datasize = datasize;
 		nvp->nvp_nitems = nitems;
+		nvp->nvp_nalloc = nitems;
 		nvp->nvp_magic = NVPAIR_MAGIC;
 	}
 
@@ -170,20 +172,44 @@ nvpair_allocv(const char *name, int type
 static int
 nvpair_append(nvpair_t *nvp, const void *value, size_t valsize, size_t datasize)
 {
-	void *olddata, *data, *valp;
+	void *data, *valp;
 	size_t oldlen;
 
 	oldlen = nvp->nvp_nitems * valsize;
-	olddata = (void *)(uintptr_t)nvp->nvp_data;
-	data = nv_realloc(olddata, oldlen + valsize);
-	if (data == NULL) {
-		ERRNO_SET(ENOMEM);
-		return (-1);
+	if (nvp->nvp_nitems < nvp->nvp_nalloc) {
+		data = (void *)(uintptr_t)nvp->nvp_data;
+	} else {
+		void *const olddata = (void *)(uintptr_t)nvp->nvp_data;
+		size_t newlen, newnalloc;
+
+		if (valsize > SIZE_MAX - oldlen) {
+			ERRNO_SET(ENOMEM);
+			return (-1);
+		}
+		if (oldlen > SIZE_MAX/2 - 1) {
+			/*
+			 * Degrade to quadratic-time appending once
+			 * we're nearing SIZE_MAX -- only relevant on a
+			 * 32-bit platform, where we're likely to
+			 * exhaust memory before this point anyway.
+			 */
+			newlen = oldlen + valsize;
+			newnalloc = nvp->nvp_nalloc + 1;
+		} else {
+			newlen = 2*oldlen + valsize;
+			newnalloc = 2*nvp->nvp_nalloc + 1;
+		}
+		data = nv_realloc(olddata, newlen);
+		if (data == NULL) {
+			ERRNO_SET(ENOMEM);
+			return (-1);
+		}
+		nvp->nvp_nalloc = newnalloc;
+		nvp->nvp_data = (uint64_t)(uintptr_t)data;
 	}
 	valp = (unsigned char *)data + oldlen;
 	memcpy(valp, value, valsize);
 
-	nvp->nvp_data = (uint64_t)(uintptr_t)data;
 	nvp->nvp_datasize += datasize;
 	nvp->nvp_nitems++;
 	return (0);