Replace the swap extent(9) usage by a blist data structure.

It makes uvm_swap_free() faster: extents have a cost of O(n*n) which doesn't
really scale with gigabytes of swap.

Based on initial work from mpi@
The blist implementation comes from DragonFlyBSD.

The diff adds also a ddb(4) 'show swap' command to show the blist and help
debugging, and fix some off-by-one in size printed during hibernate.

ok mpi@

11 files changed, 159 insertions, 0 deletions

diff --git a/regress/sys/uvm/blist/Makefile b/regress/sys/uvm/blist/Makefile
new file mode 100644
index 00000000000..c46e70b6c27
--- /dev/null
+++ b/regress/sys/uvm/blist/Makefile
@@ -0,0 +1,37 @@
+# $OpenBSD: Makefile,v 1.1 2022/07/29 17:47:11 semarie Exp $
+
+SRCS +=		${.CURDIR}/../../../../sys/kern/subr_blist.c
+WARNINGS =	Yes
+
+TESTS +=	\
+	test-1	1024 \
+	test-2	1024 \
+	test-3	64 \
+	test-4	64 \
+	test-5	1024
+
+.for t s in ${TESTS}
+run-$t: blist
+	./blist $s <${.CURDIR}/$t.in >$t.run
+	diff -u ${.CURDIR}/$t.out $t.run
+
+show-$t: blist
+	./blist $s <${.CURDIR}/$t.in 2>&1
+
+regen-$t: blist
+	./blist $s <${.CURDIR}/$t.in >${.CURDIR}/$t.out
+
+REGRESS_TARGETS +=	run-$t
+REGEN_TARGETS +=	regen-$t
+CLEANFILES +=		$t.run
+.endfor
+
+blist: ${SRCS}
+	${CC} -o $@ ${CFLAGS} ${SRCS}
+CLEANFILES +=	blist blist.d
+
+regen: ${REGEN_TARGETS}
+
+.PHONY: regen ${REGEN_TARGETS}
+
+.include <bsd.regress.mk>
diff --git a/regress/sys/uvm/blist/test-1.in b/regress/sys/uvm/blist/test-1.in
new file mode 100644
index 00000000000..0c00549ccaf
--- /dev/null
+++ b/regress/sys/uvm/blist/test-1.in
@@ -0,0 +1,3 @@
+a 1
+p
+g
diff --git a/regress/sys/uvm/blist/test-1.out b/regress/sys/uvm/blist/test-1.out
new file mode 100644
index 00000000000..2184455b9ec
--- /dev/null
+++ b/regress/sys/uvm/blist/test-1.out
@@ -0,0 +1,28 @@
+BLIST representing 1024 blocks (4 MB of swap), requiring   0.00M of ram
+BLIST raw radix tree: 18 records, top-radix 2048
+1024/1024/2048> count 1
+blist_meta_alloc blkat 0 blk 0 count 1 radix 2048
+    R=0000
+1023/1024/2048> BLIST {
+    (0000,2048): subtree (1023/2048) big=1023 {
+        (0000,64): bitmap fffffffffffffffe big=64
+        (0040,64): bitmap ffffffffffffffff big=64
+        (0080,64): bitmap ffffffffffffffff big=64
+        (00c0,64): bitmap ffffffffffffffff big=64
+        (0100,64): bitmap ffffffffffffffff big=64
+        (0140,64): bitmap ffffffffffffffff big=64
+        (0180,64): bitmap ffffffffffffffff big=64
+        (01c0,64): bitmap ffffffffffffffff big=64
+        (0200,64): bitmap ffffffffffffffff big=64
+        (0240,64): bitmap ffffffffffffffff big=64
+        (0280,64): bitmap ffffffffffffffff big=64
+        (02c0,64): bitmap ffffffffffffffff big=64
+        (0300,64): bitmap ffffffffffffffff big=64
+        (0340,64): bitmap ffffffffffffffff big=64
+        (0380,64): bitmap ffffffffffffffff big=64
+        (03c0,64): bitmap ffffffffffffffff big=64
+        (0400,64): Terminator
+    }
+}
+1023/1024/2048> gapfind: begin=0040 end=0400 size=960
+1023/1024/2048> 
\ No newline at end of file
diff --git a/regress/sys/uvm/blist/test-2.in b/regress/sys/uvm/blist/test-2.in
new file mode 100644
index 00000000000..7d83c598c20
--- /dev/null
+++ b/regress/sys/uvm/blist/test-2.in
@@ -0,0 +1,6 @@
+a 64
+a 64
+a 64
+f 0x0040 64
+p
+g
diff --git a/regress/sys/uvm/blist/test-2.out b/regress/sys/uvm/blist/test-2.out
new file mode 100644
index 00000000000..6da19c7c66b
--- /dev/null
+++ b/regress/sys/uvm/blist/test-2.out
@@ -0,0 +1,34 @@
+BLIST representing 1024 blocks (4 MB of swap), requiring   0.00M of ram
+BLIST raw radix tree: 18 records, top-radix 2048
+1024/1024/2048> count 64
+blist_meta_alloc blkat 0 blk 0 count 64 radix 2048
+    R=0000
+960/1024/2048> count 64
+blist_meta_alloc blkat 0 blk 0 count 64 radix 2048
+    R=0040
+896/1024/2048> count 64
+blist_meta_alloc blkat 0 blk 0 count 64 radix 2048
+    R=0080
+832/1024/2048> 896/1024/2048> BLIST {
+    (0000,2048): subtree (896/2048) big=832 {
+        (0000,64): bitmap 0000000000000000 big=0
+        (0040,64): bitmap ffffffffffffffff big=64
+        (0080,64): bitmap 0000000000000000 big=64
+        (00c0,64): bitmap ffffffffffffffff big=64
+        (0100,64): bitmap ffffffffffffffff big=64
+        (0140,64): bitmap ffffffffffffffff big=64
+        (0180,64): bitmap ffffffffffffffff big=64
+        (01c0,64): bitmap ffffffffffffffff big=64
+        (0200,64): bitmap ffffffffffffffff big=64
+        (0240,64): bitmap ffffffffffffffff big=64
+        (0280,64): bitmap ffffffffffffffff big=64
+        (02c0,64): bitmap ffffffffffffffff big=64
+        (0300,64): bitmap ffffffffffffffff big=64
+        (0340,64): bitmap ffffffffffffffff big=64
+        (0380,64): bitmap ffffffffffffffff big=64
+        (03c0,64): bitmap ffffffffffffffff big=64
+        (0400,64): Terminator
+    }
+}
+896/1024/2048> gapfind: begin=00c0 end=0400 size=832
+896/1024/2048> 
\ No newline at end of file
diff --git a/regress/sys/uvm/blist/test-3.in b/regress/sys/uvm/blist/test-3.in
new file mode 100644
index 00000000000..960e7ef302a
--- /dev/null
+++ b/regress/sys/uvm/blist/test-3.in
@@ -0,0 +1,2 @@
+p
+g
diff --git a/regress/sys/uvm/blist/test-3.out b/regress/sys/uvm/blist/test-3.out
new file mode 100644
index 00000000000..b061c63d4d4
--- /dev/null
+++ b/regress/sys/uvm/blist/test-3.out
@@ -0,0 +1,7 @@
+BLIST representing 64 blocks (0 MB of swap), requiring   0.00M of ram
+BLIST raw radix tree: 1 records, top-radix 64
+64/64/64> BLIST {
+    (0000,64): bitmap ffffffffffffffff big=64
+}
+64/64/64> gapfind: begin=0000 end=0040 size=64
+64/64/64> 
\ No newline at end of file
diff --git a/regress/sys/uvm/blist/test-4.in b/regress/sys/uvm/blist/test-4.in
new file mode 100644
index 00000000000..fca2a03dc3b
--- /dev/null
+++ b/regress/sys/uvm/blist/test-4.in
@@ -0,0 +1,3 @@
+a 64
+p
+g
diff --git a/regress/sys/uvm/blist/test-4.out b/regress/sys/uvm/blist/test-4.out
new file mode 100644
index 00000000000..0a030935277
--- /dev/null
+++ b/regress/sys/uvm/blist/test-4.out
@@ -0,0 +1,9 @@
+BLIST representing 64 blocks (0 MB of swap), requiring   0.00M of ram
+BLIST raw radix tree: 1 records, top-radix 64
+64/64/64> count 64
+    R=0000
+0/64/64> BLIST {
+    (0000,64): bitmap 0000000000000000 big=64
+}
+0/64/64> gapfind: begin=0000 end=0000 size=0
+0/64/64> 
\ No newline at end of file
diff --git a/regress/sys/uvm/blist/test-5.in b/regress/sys/uvm/blist/test-5.in
new file mode 100644
index 00000000000..3c05f57c494
--- /dev/null
+++ b/regress/sys/uvm/blist/test-5.in
@@ -0,0 +1,3 @@
+a 64 0x300
+p
+g
diff --git a/regress/sys/uvm/blist/test-5.out b/regress/sys/uvm/blist/test-5.out
new file mode 100644
index 00000000000..0258ea1b75c
--- /dev/null
+++ b/regress/sys/uvm/blist/test-5.out
@@ -0,0 +1,27 @@
+BLIST representing 1024 blocks (4 MB of swap), requiring   0.00M of ram
+BLIST raw radix tree: 18 records, top-radix 2048
+1024/1024/2048> blist_meta_alloc blkat 768 blk 0 count 64 radix 2048
+    R=0300
+960/1024/2048> BLIST {
+    (0000,2048): subtree (960/2048) big=960 {
+        (0000,64): bitmap ffffffffffffffff big=64
+        (0040,64): bitmap ffffffffffffffff big=64
+        (0080,64): bitmap ffffffffffffffff big=64
+        (00c0,64): bitmap ffffffffffffffff big=64
+        (0100,64): bitmap ffffffffffffffff big=64
+        (0140,64): bitmap ffffffffffffffff big=64
+        (0180,64): bitmap ffffffffffffffff big=64
+        (01c0,64): bitmap ffffffffffffffff big=64
+        (0200,64): bitmap ffffffffffffffff big=64
+        (0240,64): bitmap ffffffffffffffff big=64
+        (0280,64): bitmap ffffffffffffffff big=64
+        (02c0,64): bitmap ffffffffffffffff big=64
+        (0300,64): bitmap 0000000000000000 big=64
+        (0340,64): bitmap ffffffffffffffff big=64
+        (0380,64): bitmap ffffffffffffffff big=64
+        (03c0,64): bitmap ffffffffffffffff big=64
+        (0400,64): Terminator
+    }
+}
+960/1024/2048> gapfind: begin=0000 end=0300 size=768
+960/1024/2048> 
\ No newline at end of file