NetBSD Problem Report #60340

From www@netbsd.org  Thu Jun 18 20:18:25 2026
Return-Path: <www@netbsd.org>
Received: from mail.netbsd.org (mail.netbsd.org [199.233.217.200])
	(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)
	 key-exchange X25519 server-signature RSA-PSS (2048 bits)
	 client-signature RSA-PSS (2048 bits))
	(Client CN "mail.netbsd.org", Issuer "R13" (not verified))
	by mollari.NetBSD.org (Postfix) with ESMTPS id C57FA1A923A
	for <gnats-bugs@gnats.NetBSD.org>; Thu, 18 Jun 2026 20:18:25 +0000 (UTC)
Message-Id: <20260618201824.691AA1A923B@mollari.NetBSD.org>
Date: Thu, 18 Jun 2026 20:18:24 +0000 (UTC)
From: campbell+netbsd@mumble.net
Reply-To: campbell+netbsd@mumble.net
To: gnats-bugs@NetBSD.org
Subject: npf(4): quadratic-time state/config export
X-Send-Pr-Version: www-1.0
X-From4GNATS: "campbell+netbsd@mumble.net via gnats" <gnats-admin@NetBSD.org>

>Number:         60340
>Category:       kern
>Synopsis:       npf(4): quadratic-time state/config export
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    kern-bug-people
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Thu Jun 18 20:20:01 +0000 2026
>Last-Modified:  Thu Jun 18 20:45:01 +0000 2026
>Originator:     Taylor R Campbell
>Release:        current, 11, 10, 9, ...
>Organization:
The NetBSD Packet Foundation, Esquared
>Environment:
>Description:

	The ioctl to export the npf state, IOC_NPF_SAVE runs in
	quadratic time because it uses realloc in a loop with a fixed
	increment, and the kernel realloc(9) only allocates exactly as
	much as the caller requested, no more.  So the kth increment
	costs k time to memcpy all the data so far, and hence the whole
	process for n items takes O(n^2) time.

    870 	case IOC_NPF_SAVE:
    871 		error = npfctl_save(npf, req, resp);
https://nxr.netbsd.org/xref/src/sys/net/npf/npf_ctl.c?r=1.62#870

    625 static int
    626 npfctl_save(npf_t *npf, const nvlist_t *req, nvlist_t *resp)
    627 {
...
    640 	error = npf_conndb_export(npf, resp);
https://nxr.netbsd.org/xref/src/sys/net/npf/npf_ctl.c?r=1.62#620

    789 	con = head;
    790 	while (con) {
    791 		nvlist_t *con_nvl;
    792 
    793 		con_nvl = nvlist_create(0);
    794 		if (npf_conn_export(npf, con, con_nvl) == 0) {
    795 			nvlist_append_nvlist_array(nvl, "conn-list", con_nvl);
    796 		}
    797 		nvlist_destroy(con_nvl);
    798 
    799 		if ((con = npf_conndb_getnext(conn_db, con)) == head) {
https://nxr.netbsd.org/xref/src/sys/net/npf/npf_conn.c?r=1.35#768

   1647 #define	NVLIST_APPEND_ARRAY(vtype, type, TYPE)				\
   1648 void									\
   1649 nvlist_append_##type##_array(nvlist_t *nvl, const char *name, vtype value)\
   1650 {									\
...
   1662 	if (nvpair_append_##type##_array(nvp, value) == -1) {		\
https://nxr.netbsd.org/xref/src/sys/external/bsd/libnv/dist/nvlist.c?r=1.11#1647

    170 static int
    171 nvpair_append(nvpair_t *nvp, const void *value, size_t valsize, size_t datasize)
    172 {
    173 	void *olddata, *data, *valp;
    174 	size_t oldlen;
    175 
    176 	oldlen = nvp->nvp_nitems * valsize;
    177 	olddata = (void *)(uintptr_t)nvp->nvp_data;
    178 	data = nv_realloc(olddata, oldlen + valsize);
https://nxr.netbsd.org/xref/src/sys/external/bsd/libnv/dist/nvpair.c?r=1.14#170

     66 # define nv_realloc(buf, size)		realloc((buf), (size), M_NVLIST, \
     67 					    M_WAITOK)
https://nxr.netbsd.org/xref/src/sys/external/bsd/libnv/dist/nv_impl.h?r=1.7#66

     72 #define	realloc(ptr, size, type, flags)	kern_realloc(ptr, size, flags)
https://nxr.netbsd.org/xref/src/sys/sys/malloc.h?r=1.117#72

    174 void *
    175 kern_realloc(void *curaddr, unsigned long newsize, int flags)
    176 {
...
    208 	/*
    209 	 * If we already actually have as much as they want, we're done.
    210 	 */
    211 	if (newsize <= cursize)
    212 		return curaddr;
    213 
    214 	/*
    215 	 * Can't satisfy the allocation with the existing block.
    216 	 * Allocate a new one and copy the data.
    217 	 */
    218 	newaddr = malloc(newsize, ksp, flags);
https://nxr.netbsd.org/xref/src/sys/kern/kern_malloc.c?r=1.158#174

>How-To-Repeat:

	1. set up a stateful firewall with tens of thousands of connections
	2. npfctl list

>Fix:

	Increase the size geometrically, not linearly: double, don't
	add an increment, each time there's no space for a new item, so
	this takes amortized linear time instead of quadratic time.

>Audit-Trail:
From: Taylor R Campbell <riastradh@NetBSD.org>
To: gnats-bugs@NetBSD.org, netbsd-bugs@NetBSD.org
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>
 # 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--

Home	PR Database Search