Date: Sun, 9 Dec 2018 17:55:10 +0000 (UTC) From: Alan Cox <alc@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r341766 - head/sys/kern Message-ID: <201812091755.wB9HtAOq011680@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: alc Date: Sun Dec 9 17:55:10 2018 New Revision: 341766 URL: https://svnweb.freebsd.org/changeset/base/341766 Log: blst_leaf_alloc updates bighint for a leaf when an allocation is successful and includes the last block represented by the leaf. The reasoning is that, if the last block is included, then there must be no solution before that one in the leaf, so the leaf cannot provide an allocation that big again; indeed, the leaf cannot provide a solution bigger than range1. Which is all correct, except that if the value of blk passed in did not represent the first block of the leaf, because the cursor was pointing to the middle of the leaf, then a possible solution before the cursor may have been ignored, and bighint cannot be updated. Consider the sequence allocate 63 (returning address 0), free 0,63 (freeing that same block, and allocate 1 (returning 63). The result is that one block is allocated from the first leaf, and the value of bighint is 0, so that nothing can be allocated from that leaf until the only block allocated from that leaf is freed. This change detects that skipped-over solution, and when there is one it makes sure that the value of bighint is not changed when the last block is allocated. Submitted by: Doug Moore <dougm@rice.edu> Tested by: pho X-MFC with: r340402 Differential Revision: https://reviews.freebsd.org/D18474 Modified: head/sys/kern/subr_blist.c Modified: head/sys/kern/subr_blist.c ============================================================================== --- head/sys/kern/subr_blist.c Sun Dec 9 15:34:20 2018 (r341765) +++ head/sys/kern/subr_blist.c Sun Dec 9 17:55:10 2018 (r341766) @@ -644,14 +644,14 @@ blst_next_leaf_alloc(blmeta_t *scan, daddr_t blk, int /* * BLST_LEAF_ALLOC() - allocate at a leaf in the radix tree (a bitmap). * - * This is the core of the allocator and is optimized for the - * BLIST_BMAP_RADIX block allocation case. Otherwise, execution - * time is proportional to log2(count) + bitpos time. + * This function is the core of the allocator. Its execution time is + * proportional to log(count), plus height of the tree if the allocation + * crosses a leaf boundary. */ static daddr_t blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count) { - u_daddr_t mask; + u_daddr_t cursor_mask, mask; int count1, hi, lo, num_shifts, range1, range_ext; range1 = 0; @@ -661,14 +661,14 @@ blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count while ((-mask & ~mask) != 0 && num_shifts > 0) { /* * If bit i is set in mask, then bits in [i, i+range1] are set - * in scan->bm_bitmap. The value of range1 is equal to - * count1 >> num_shifts. Grow range and reduce num_shifts to 0, - * while preserving these invariants. The updates to mask leave - * fewer bits set, but each bit that remains set represents a - * longer string of consecutive bits set in scan->bm_bitmap. - * If more updates to mask cannot clear more bits, because mask - * is partitioned with all 0 bits preceding all 1 bits, the loop - * terminates immediately. + * in scan->bm_bitmap. The value of range1 is equal to count1 + * >> num_shifts. Grow range1 and reduce num_shifts to 0, + * while preserving these invariants. The updates to mask + * leave fewer bits set, but each bit that remains set + * represents a longer string of consecutive bits set in + * scan->bm_bitmap. If more updates to mask cannot clear more + * bits, because mask is partitioned with all 0 bits preceding + * all 1 bits, the loop terminates immediately. */ num_shifts--; range_ext = range1 + ((count1 >> num_shifts) & 1); @@ -691,10 +691,23 @@ blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count } /* Discard any candidates that appear before blk. */ - mask &= (u_daddr_t)-1 << (blk & BLIST_BMAP_MASK); - if (mask == 0) - return (SWAPBLK_NONE); + if ((blk & BLIST_BMAP_MASK) != 0) { + cursor_mask = mask & bitrange(0, blk & BLIST_BMAP_MASK); + if (cursor_mask != 0) { + mask ^= cursor_mask; + if (mask == 0) + return (SWAPBLK_NONE); + /* + * Bighint change for last block allocation cannot + * assume that any other blocks are allocated, so the + * bighint cannot be reduced much. + */ + range1 = BLIST_MAX_ALLOC - 1; + } + blk &= ~BLIST_BMAP_MASK; + } + /* * The least significant set bit in mask marks the start of the first * available range of sufficient size. Clear all the bits but that one, @@ -734,7 +747,7 @@ blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count } /* Clear the allocated bits from this leaf. */ scan->bm_bitmap &= ~mask; - return ((blk & ~BLIST_BMAP_MASK) + lo); + return (blk + lo); } /*
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201812091755.wB9HtAOq011680>