Index: sys/netpfil/pf/pf_ioctl.c
===================================================================
--- sys/netpfil/pf/pf_ioctl.c
+++ sys/netpfil/pf/pf_ioctl.c
@@ -5056,25 +5056,65 @@
 	nvlist_t	*nvl = NULL, *nvls;
 	void		*nvlpacked = NULL;
 	struct pf_state	*s = NULL;
-	int		 error = 0;
 	uint64_t	 count = 0;
+	uint64_t	 start_row, token;
+	int		 error = 0;
+	int		 i;
 
 #define ERROUT(x)	ERROUT_FUNCTION(errout, x)
 
+	start_row = 0;
+
+	/* Optional paging support. */
+	if (nv->len > 0) {
+		if (nv->len > pf_ioctl_maxcount)
+			ERROUT(ENOMEM);
+
+		nvlpacked = malloc(nv->len, M_NVLIST, M_WAITOK);
+		error = copyin(nv->data, nvlpacked, nv->len);
+		if (error)
+			ERROUT(error);
+
+		nvl = nvlist_unpack(nvlpacked, nv->len, 0);
+		if (nvl != NULL)
+			start_row = nvlist_get_number(nvl, "token");
+		nvlist_destroy(nvl);
+		nvl = NULL;
+
+		if (start_row > pf_hashmask)
+			ERROUT(EINVAL);
+	}
+
 	nvl = nvlist_create(0);
 	if (nvl == NULL)
 		ERROUT(ENOMEM);
 
-	nvlist_add_number(nvl, "count", uma_zone_get_cur(V_pf_state_z));
-
-	for (int i = 0; i < pf_hashmask; i++) {
+	token = start_row;
+	for (i = start_row; i < pf_hashmask; i++) {
 		struct pf_idhash *ih = &V_pf_idhash[i];
+		int elements = 0;
 
 		/* Avoid taking the lock if there are no states in the row. */
-		if (LIST_EMPTY(&ih->states))
+		if (LIST_EMPTY(&ih->states)) {
+			token = i + 1;
 			continue;
+		}
 
 		PF_HASHROW_LOCK(ih);
+
+		/* Count the states and estimate if we can fit this in the
+		 * remaining space. */
+		LIST_FOREACH(s, &ih->states, entry)
+			elements++;
+
+		/* If the next entire row wouldn't fit stop here. */
+		if ((nvlist_size(nvl) + (PFNV_STATE_SIZE_ESTIMATE * elements))
+		    > nv->size) {
+			PF_HASHROW_UNLOCK(ih);
+			count += elements;
+			break;
+		}
+
 		LIST_FOREACH(s, &ih->states, entry) {
 			if (s->timeout == PFTM_UNLINKED)
 				continue;
@@ -5089,27 +5129,24 @@
 				PF_HASHROW_UNLOCK(ih);
 				ERROUT(ENOMEM);
 			}
-			if ((nvlist_size(nvl) + nvlist_size(nvls)) > nv->size) {
-				/* We've run out of room for more states. */
-				nvlist_destroy(nvls);
-				PF_HASHROW_UNLOCK(ih);
-				goto DIOCGETSTATESNV_full;
-			}
+			MPASS(nvlist_size(nvls) < PFNV_STATE_SIZE_ESTIMATE);
+			MPASS(nv->size >= (nvlist_size(nvl) +
+			    nvlist_size(nvls)));
+
 			nvlist_append_nvlist_array(nvl, "states", nvls);
 			nvlist_destroy(nvls);
 			count++;
 		}
 		PF_HASHROW_UNLOCK(ih);
+
+		token = i + 1;
 	}
 
-	/* We've managed to put them all the available space. Let's make sure
-	 * 'count' matches our array (that's racy, because we don't hold a lock
-	 * over all states, only over each row individually. */
-	(void)nvlist_take_number(nvl, "count");
+	nvlist_add_bool(nvl, "done", token == pf_hashmask);
+	nvlist_add_number(nvl, "token", token);
 	nvlist_add_number(nvl, "count", count);
 
-DIOCGETSTATESNV_full:
-
+	free(nvlpacked, M_NVLIST);
 	nvlpacked = nvlist_pack(nvl, &nv->len);
 	if (nvlpacked == NULL)
 		ERROUT(ENOMEM);