blist: Correct the node count used for allocation.

[markj]

Summary

Commit bb4a27f927a1 added the ability to allocate a span of blocks
crossing a meta node boundary. To ensure that blst_next_leaf_alloc()
does not walk past the end of the tree, an extra all-zero meta node
exists at the end of the allocation, and blst_next_leaf_alloc() is
implemented such that the presence of this node terminates the search.

blist_create() computes the number of nodes required. It has two
problems:

1. When the size of the blist is a power of BLIST_RADIX, we would
allocate an extra level in the tree for no reason that I can see.
2. When the size of the blist is a multiple of BLIST_RADIX, we would
fail to allocate a terminator node. In this case,
blst_next_leaf_alloc() could scan beyond the bounds of the
allocation.

Fix both problems by rewriting the loop which counts the number of
required nodes.

Problem 2 was found using KASAN.

Reported by: pho

Test Plan

To reproduce this using a user-mode build of subr_blist.c:

$ clang -fsanitize=address subr_blist.c -lsbuf
$ ./a.out 64
BLIST representing 64 blocks (0 MB of swap), requiring 1K of ram
BLIST raw radix tree contains 2 records
64/64/4096> a 63 63
    R=00000000, c=00000063
1/64/4096> a 1 2
=================================================================
==20873==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x606000000060 at pc 0x0000002b979d bp 0x7fffffffdc00 sp 0x7fffffffdbf8
READ of size 8 at 0x606000000060 thread T0
    #0 0x2b979c in blst_next_leaf_alloc (/usr/home/markj/src/freebsd/sys/kern/a.out+0x2b979c)
    #1 0x2b95a9 in blst_leaf_alloc (/usr/home/markj/src/freebsd/sys/kern/a.out+0x2b95a9)
    #2 0x2b5a2c in blst_meta_alloc (/usr/home/markj/src/freebsd/sys/kern/a.out+0x2b5a2c)
    #3 0x2b5c2f in blst_meta_alloc (/usr/home/markj/src/freebsd/sys/kern/a.out+0x2b5c2f)
    #4 0x2b573b in blist_alloc (/usr/home/markj/src/freebsd/sys/kern/a.out+0x2b573b)
    #5 0x2b8ad6 in main (/usr/home/markj/src/freebsd/sys/kern/a.out+0x2b8ad6)

0x606000000060 is located 0 bytes to the right of 64-byte region [0x606000000020,0x606000000060)
allocated by thread T0 here:
    #0 0x28c272 in calloc /usr/home/markj/src/freebsd/contrib/llvm-project/compiler-rt/lib/asan/asan_malloc_linux.cpp:154:3
    #1 0x2b53ca in blist_create (/usr/home/markj/src/freebsd/sys/kern/a.out+0x2b53ca)
    #2 0x2b845a in main (/usr/home/markj/src/freebsd/sys/kern/a.out+0x2b845a)
    #3 0x2359df in _start /usr/home/markj/src/freebsd/lib/csu/amd64/crt1_c.c:75:7
    #4 0x8002df007  (<unknown module>)

   SUMMARY: AddressSanitizer: heap-buffer-overflow (/usr/home/markj/src/freebsd/sys/kern/a.out+0x2b979c) in blst_next_leaf_alloc
Shadow bytes around the buggy address:
  0x4c0bffffffb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x4c0bffffffc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x4c0bffffffd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x4c0bffffffe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x4c0bfffffff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x4c0c00000000: fa fa fa fa 00 00 00 00 00 00 00 00[fa]fa fa fa
  0x4c0c00000010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x4c0c00000020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x4c0c00000030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x4c0c00000040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x4c0c00000050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==20873==ABORTING

This report is basically just saying that blst_next_leaf_alloc() triggered
an out-of-bounds access. Note also that in that example we allocated
two meta nodes even though only one is required.

[dougm]

sys/kern/subr_blist.c

247–256

I suggest that this loop rewriting only addresses problem 1, and that the problem of radix growing too large can be addressed with less rewriting as:

nodes = 1;
for (radix = 1; (blocks - 1) / BLIST_RADIX / radix > 0; radix *= BLIST_RADIX) {

nodes += 1 + (blocks - 1) / BLIST_RADIX / radix;

}

I accept that the two problems exist and that the proposed changes address them.

[markj]

Apply Doug's suggestion.

[markj]

sys/kern/subr_blist.c

247–256

Thanks. The review description is indeed misleading, sorry. I will fix it before committing.

[dougm]

Looks okay to me.