HomeFreeBSD

blist: Correct the node count computed in blist_create()

Description

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

Details

Provenance
markjAuthored on Jul 13 2021, 9:47 PM
Reviewer
dougm
Differential Revision
D31158: blist: Correct the node count used for allocation.
Parents
R10:45e2357113e6: malloc: Pass the allocation size to malloc_large() by value
Branches
Unknown
Tags
Unknown