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

["Taylor R Campbell via gnats" <gnats-admin%NetBSD.org@localhost>]

The following reply was made to PR kern/60340; it has been noted by GNATS.

From: Taylor R Campbell <riastradh%NetBSD.org@localhost>
To: gnats-bugs%NetBSD.org@localhost, netbsd-bugs%NetBSD.org@localhost
Cc: 
Subject: Re: kern/60340: npf(4): quadratic-time state/config export
Date: Thu, 18 Jun 2026 20:44:05 +0000

 This is a multi-part message in MIME format.
 --=_jTTFFMu/al3E0ztP4Shf9axJ0hgFpHTk
 
 Candidate fix attached, untested -- need to construct a reproducer
 with a gigantic state table to verify that it doesn't provoke
 quadratic-time export.
 
 --=_jTTFFMu/al3E0ztP4Shf9axJ0hgFpHTk
 Content-Type: text/plain; charset="ISO-8859-1"; name="pr60340-nvlistquadtime"
 Content-Transfer-Encoding: quoted-printable
 Content-Disposition: attachment; filename="pr60340-nvlistquadtime.patch"
 
 # 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 =3D data;
  		nvp->nvp_datasize =3D datasize;
  		nvp->nvp_nitems =3D nitems;
 +		nvp->nvp_nalloc =3D nitems;
  		nvp->nvp_magic =3D NVPAIR_MAGIC;
  	}
 =20
 @@ -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 dat=
 asize)
  {
 -	void *olddata, *data, *valp;
 +	void *data, *valp;
  	size_t oldlen;
 =20
  	oldlen =3D nvp->nvp_nitems * valsize;
 -	olddata =3D (void *)(uintptr_t)nvp->nvp_data;
 -	data =3D nv_realloc(olddata, oldlen + valsize);
 -	if (data =3D=3D NULL) {
 -		ERRNO_SET(ENOMEM);
 -		return (-1);
 +	if (nvp->nvp_nitems < nvp->nvp_nalloc) {
 +		data =3D (void *)(uintptr_t)nvp->nvp_data;
 +	} else {
 +		void *const olddata =3D (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 =3D oldlen + valsize;
 +			newnalloc =3D nvp->nvp_nalloc + 1;
 +		} else {
 +			newlen =3D 2*oldlen + valsize;
 +			newnalloc =3D 2*nvp->nvp_nalloc + 1;
 +		}
 +		data =3D nv_realloc(olddata, newlen);
 +		if (data =3D=3D NULL) {
 +			ERRNO_SET(ENOMEM);
 +			return (-1);
 +		}
 +		nvp->nvp_nalloc =3D newnalloc;
 +		nvp->nvp_data =3D (uint64_t)(uintptr_t)data;
  	}
  	valp =3D (unsigned char *)data + oldlen;
  	memcpy(valp, value, valsize);
 =20
 -	nvp->nvp_data =3D (uint64_t)(uintptr_t)data;
  	nvp->nvp_datasize +=3D datasize;
  	nvp->nvp_nitems++;
  	return (0);
 
 --=_jTTFFMu/al3E0ztP4Shf9axJ0hgFpHTk--