Fix an edge case in the node count computation in blist_create().
ClosedPublic
Actions

Authored by markj on Sep 4 2018, 6:02 PM.

Details

Reviewers

dougm
alc
kib

Commits

rS338472: Correct the condition under which we allocate a terminator node.

Summary

There are some cases where we need to allocate an extra terminator node
even when last_block == blocks - 1. This occurs when each leaf is
completely filled out (i.e., blocks is a sum of powers of 2 greater than
or equal to BLIST_BMAP_RADIX) but "blocks" is smaller than "radix".

While here, add an explicit check for the blocks == 0 case, which
is otherwise invalid and not handled properly.

Test Plan

Compiled subr_blist.c for userland and verified that we allocate the
correct number of nodes and place terminators at the correct offsets
for various inputs to blist_create().

Diff Detail

Lint

Lint Passed

Unit

No Test Coverage

Build Status

Buildable 19399
Build 18999: arc lint + arc unit

Event Timeline

markj created this revision.Sep 4 2018, 6:02 PM

Harbormaster completed remote builds in B19386: Diff 47648.Sep 4 2018, 6:02 PM

markj edited the test plan for this revision. (Show Details)Sep 4 2018, 6:05 PM

markj added reviewers: dougm, alc, kib.

markj added inline comments.Sep 4 2018, 6:14 PM

sys/kern/subr_blist.c
251	Oops, the last condition is redundant. It's sufficient to check radix - blocks > BLIST_BMAP_RADIX.

markj added inline comments.Sep 4 2018, 6:17 PM

sys/kern/subr_blist.c
250	The comparison should also be >=, not >.

Address comments.

Harbormaster completed remote builds in B19387: Diff 47650.Sep 4 2018, 6:19 PM

kib accepted this revision.Sep 4 2018, 7:43 PM

This revision is now accepted and ready to land.Sep 4 2018, 7:43 PM

dougm added inline comments.Sep 4 2018, 9:09 PM

sys/kern/subr_blist.c
250	I read this as "If there are missing leaf (bmap) nodes that keep this from being a complete balanced tree, then we need a terminator somewhere. I agree. But then does the "last_block >= blocks" test still serve any purpose? Perhaps even the iterative calculation of last_block should be dropped?

Simplify the test for the presence of a terminator node.
Update comments to reflect the fact that last_block is not used in the above-mentioned test.

This revision now requires review to proceed.Sep 5 2018, 12:13 AM

Harbormaster completed remote builds in B19399: Diff 47672.Sep 5 2018, 12:13 AM

markj added inline comments.Sep 5 2018, 12:13 AM

sys/kern/subr_blist.c
250	I believe you're right that the last_block >= blocks tests is not needed anymore, but we still need the iterative computation of last_block in order for the node count computation below to be correct. I don't really see a way to compute both "nodes" and "radix" with a single loop - do you?