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

["campbell+netbsd%mumble.net@localhost via gnats" <gnats-admin%NetBSD.org@localhost>]

>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
>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.