git: 2783335caeae - main - blist: Correct the node count computed in blist_create()

[Mark Johnston]

The branch main has been updated by markj:

URL: https://cgit.FreeBSD.org/src/commit/?id=2783335caeae964bd8a1aa15726b523876613e45

commit 2783335caeae964bd8a1aa15726b523876613e45
Author:     Mark Johnston <markj at FreeBSD.org>
AuthorDate: 2021-07-13 21:47:27 +0000
Commit:     Mark Johnston <markj at FreeBSD.org>
CommitDate: 2021-07-13 21:47:27 +0000

    blist: Correct the node count computed in blist_create()
    
    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
    needs to be present 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 had two
    problems:
    1. When the size of the blist is a power of BLIST_RADIX, we would
       unnecessarily allocate an extra level in the tree.
    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.  This was found using KASAN.
    
    Modify blist_create() to handle these cases correctly.
    
    Reported by:    pho
    Reviewed by:    dougm
    MFC after:      2 weeks
    Differential Revision:  https://reviews.freebsd.org/D31158
---
 sys/kern/subr_blist.c | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

diff --git a/sys/kern/subr_blist.c b/sys/kern/subr_blist.c
index 27b226fd8a18..ba13fb4efd80 100644
--- a/sys/kern/subr_blist.c
+++ b/sys/kern/subr_blist.c
@@ -244,8 +244,16 @@ blist_create(daddr_t blocks, int flags)
 	 * Calculate the radix and node count used for scanning.
 	 */
 	nodes = 1;
-	for (radix = 1; radix <= blocks / BLIST_RADIX; radix *= BLIST_RADIX)
-		nodes += 1 + (blocks - 1) / radix / BLIST_RADIX;
+	for (radix = 1; (blocks - 1) / BLIST_RADIX / radix > 0;
+	    radix *= BLIST_RADIX)
+		nodes += 1 + (blocks - 1) / BLIST_RADIX / radix;
+
+	/*
+	 * Include a sentinel node to ensure that cross-leaf scans stay within
+	 * the bounds of the allocation.
+	 */
+	if (blocks % BLIST_RADIX == 0)
+		nodes++;
 
 	bl = malloc(offsetof(struct blist, bl_root[nodes]), M_SWAP, flags |
 	    M_ZERO);