Replace random sbuf_printf() with cheaper cat/putc.

sys: Remove $FreeBSD$: one-line .c pattern

Remove /^[\s*]*__FBSDID\("\$FreeBSD\$"\);?\s*\n/

inline_ffs: remove backup binary implementation

There is no longer be any point to maintaining a binary search routine
for ffs; inlines will always do it as well or better.
Reviewed by: mhorne
Diffe

inline_ffs: remove backup binary implementation

There is no longer be any point to maintaining a binary search routine
for ffs; inlines will always do it as well or better.
Reviewed by: mhorne
Differential Revision: https://reviews.freebsd.org/D40703

show more ...

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

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

show more ...

kern: clean up empty lines in .c and .h files

Fix an overflow bug in the blist allocator that needlessly capped max
swap size by dividing a value, which was always a multiple of 64, by
64. Remove the code that reduced max swap size down to that

Fix an overflow bug in the blist allocator that needlessly capped max
swap size by dividing a value, which was always a multiple of 64, by
64. Remove the code that reduced max swap size down to that cap.

Eliminate the distinction between BLIST_BMAP_RADIX and
BLIST_META_RADIX. Call them both BLIST_RADIX.

Make improvments to the blist self-test code to silence compiler
warnings and to test larger blists.

Reported by: jmallett
Reviewed by: alc
Discussed with: kib
Tested by: pho
Differential Revision: https://reviews.freebsd.org/D25736

show more ...

Remove duplicated empty lines from kern/*.c

No functional changes.

Simplify the processing a leaf mask to find big-enough ranges of set
bits, by storing and modifying the complement of the original leaf
mask, and by avoiding some unnecessary intermediate variables i

Simplify the processing a leaf mask to find big-enough ranges of set
bits, by storing and modifying the complement of the original leaf
mask, and by avoiding some unnecessary intermediate variables in
computing the shift amounts. The logic is similar to what has recently
been committed to sys/sys/bitstring.h.

Compute better hint updates for the case when the cursor starts in
mid-leaf, and eliminates some otherwise viable solutions. Assume the
worst case, that all the eliminated offsets could have been solutions,
and you can still compute a better hint than we use now.

Eliminate some unnecessary conditional control flow.

Approved by: alc
Tested by: pho
Differential Revision: https://reviews.freebsd.org/D22666

show more ...

Address problems in blist_alloc introduced in r349777. The swap block allocator could become corrupted
if a retry to allocate swap space, after a larger allocation attempt failed, allocated a smalle

Address problems in blist_alloc introduced in r349777. The swap block allocator could become corrupted
if a retry to allocate swap space, after a larger allocation attempt failed, allocated a smaller set of free blocks
that ended on a 32- or 64-block boundary.

Add tests to detect this kind of failure-to-extend-at-boundary and prevent the associated accounting screwup.

Reported by: pho
Tested by: pho
Reviewed by: alc
Approved by: markj (mentor)
Discussed with: kib
Differential Revision: https://reviews.freebsd.org/D20893

show more ...

Change blist_next_leaf_alloc so that it can examine more than one leaf
after the one where the possible block allocation begins, and allocate
a larger number of blocks than the current limit. This do

Change blist_next_leaf_alloc so that it can examine more than one leaf
after the one where the possible block allocation begins, and allocate
a larger number of blocks than the current limit. This does not affect
the limit on minimum allocation size, which still cannot exceed
BLIST_MAX_ALLOC.

Use this change to modify swp_pager_getswapspace and its callers, so
that they can allocate more than BLIST_MAX_ALLOC blocks if they are
available.

Tested by: pho
Approved by: markj (mentor)
Differential Revision: https://reviews.freebsd.org/D20579

show more ...

A new parameter to blist_alloc specifies an upper bound on the size of
the allocation request, so that the blocks allocated are from the next
set of free blocks big enough to satisfy the minimum requ

A new parameter to blist_alloc specifies an upper bound on the size of
the allocation request, so that the blocks allocated are from the next
set of free blocks big enough to satisfy the minimum requirements of
the request, and the number of blocks allocated are as many as
possible, up to the specified maximum. The implementation of
swp_pager_getswapspace uses this parameter to ask for a number of
blocks between the new halved request size and the previous failed
request size. Thus a request for 32 blocks may fail, but instead of
getting only 16 blocks instead, the caller asks for 16 to 31 next, and
might get 19 or 27, which is closer to what they originally wanted.

I expect this to lead to bigger block allocations and less block
fragmentation, at least in some cases.

Approved by: kib (mentor)
Differential Revision: https://reviews.freebsd.org/D20001

show more ...

When bitpos can't be implemented with an inline ffs* instruction,
change the binary search so that it does not depend on a single bit
only being set in the bitmask. Use bitpos more generally, and avo

When bitpos can't be implemented with an inline ffs* instruction,
change the binary search so that it does not depend on a single bit
only being set in the bitmask. Use bitpos more generally, and avoid
some clearing of bits to accommodate its current behavior.

Approved by: kib (mentor)
Differential Revision: https://reviews.freebsd.org/D20237

show more ...

Revert r347469.

Approved by: kib (mentor)

Don't use _Generic, as many systems don't know about it. Go back to a lo-tech switch statement.

Approved by: kib (mentor)
Differential Revision: https://reviews.freebsd.org/D20235

When bitpos can't be implemented with an inline ffs* instruction,
change the binary search so that it does not depend on a single bit
only being set in the bitmask. Use bitpos more generally, and avo

When bitpos can't be implemented with an inline ffs* instruction,
change the binary search so that it does not depend on a single bit
only being set in the bitmask. Use bitpos more generally, and avoid
some clearing of bits to accommodate its current behavior.

Approved by: kib (mentor)
Differential Revision: https://reviews.freebsd.org/D20232

show more ...

Add a (q)uit option to the subr_blist test program.

Approved by: kib (mentor)
Differential Revision: https://reviews.freebsd.org/D20234

Replace the expression "-mask & ~mask" with a function call that does
the same thing, but is commented so that it might be better
understood.

Approved by: kib (mentor)
Differential Revision: https:/

Replace the expression "-mask & ~mask" with a function call that does
the same thing, but is commented so that it might be better
understood.

Approved by: kib (mentor)
Differential Revision: https://reviews.freebsd.org/D20231

show more ...

blist_next_leaf_alloc walks over all the meta-nodes between one leaf
and the next one, and if blocks are allocated from the next leaf, it
walks back toward where it started, as long as there are inte

blist_next_leaf_alloc walks over all the meta-nodes between one leaf
and the next one, and if blocks are allocated from the next leaf, it
walks back toward where it started, as long as there are interleaving
meta-nodes to be updated on account of the last free blocks under
those meta-nodes being allocated. Only if the walk goes all the way
back to the starting point must we calculate the position of the
meta-node that is the least-comment parent of one leaf and the next,
and update a bit in that meta-node to indicate the allocation of its
last free block.

There's no need to start calculating the position of that least-common
parent until the walk back reaches the original starting point, and
there's no need for a calculation that updates 'radius' to tell us
when we've walked back to the beginning, since comparing scan to next
suffices for that.

Approved by: kib (mentor)
Differential Revision: https://reviews.freebsd.org/D20229

show more ...

Replace panic() with KASSERT() and provide more useful information when failure happens.

Approved by: kib (mentor)
Differential Revision: https://reviews.freebsd.org/D20226

The intention of the blist cursor is for the search for free blocks to
resume where the last search left off. Suppose that there are no free
blocks of size 32, but plenty of size 16. If we repeatedly

The intention of the blist cursor is for the search for free blocks to
resume where the last search left off. Suppose that there are no free
blocks of size 32, but plenty of size 16. If we repeatedly request
size 32 blocks, fail, and retry with size 16 blocks, then the failures
all reset the cursor to the beginning of memory, making the 16 block
allocation use a first fit, rather than next fit, strategy.

This change has blist_alloc make a copy of the cursor for its own
decision making, and only updates the real blist cursor after a
successful allocation, making those 16 block searches behave like
next-fit searches.

Approved by: markj (mentor)
Differential Revision: https://reviews.freebsd.org/D20177

show more ...

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

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

show more ...

Terminate a blist_alloc search when a blst_meta_alloc call fails with
cursor == 0.

Every call to blst_meta_alloc but the one at the root is made only when the
meta-node is known to include a free bl

Terminate a blist_alloc search when a blst_meta_alloc call fails with
cursor == 0.

Every call to blst_meta_alloc but the one at the root is made only when the
meta-node is known to include a free block, so that either the allocation
will succeed, the node hint will be updated, or the last block of the meta-
node range is, and remains, free. But the call at the root is made without
checking that there is a free block, so in the case that every block is
allocated, there is no hint update to prevent the current code from looping
forever.

Submitted by: Doug Moore <dougm@rice.edu>
Reported by: pho
Reviewed by: pho
Tested by: pho
X-MFC with: r340402
Differential Revision: https://reviews.freebsd.org/D17999

show more ...

blist_meta_alloc assumes that mask=scan->bm_bitmap is nonzero. But if the
cursor lies in the middle of the space that the meta node represents, then
blanking the low bits of mask may make it zero, a

blist_meta_alloc assumes that mask=scan->bm_bitmap is nonzero. But if the
cursor lies in the middle of the space that the meta node represents, then
blanking the low bits of mask may make it zero, and break later code that
expects a nonzero value. Add a test that returns failure if the mask has
been cleared.

Submitted by: Doug Moore <dougm@rice.edu>
Reported by: pho
Tested by: pho
X-MFC with: r340402
Differential Revision: https://reviews.freebsd.org/D18058

show more ...

Allow allocations across meta boundaries.

Remove restrictions that prevent allocation requests to cross the
boundary between two meta nodes.

Replace the bmu_avail field in meta nodes with a bitmap

Allow allocations across meta boundaries.

Remove restrictions that prevent allocation requests to cross the
boundary between two meta nodes.

Replace the bmu_avail field in meta nodes with a bitmap that identifies
which subtrees have some free memory, and iterate over the nonempty
subtrees only in blst_meta_alloc. If free memory is scarce, this should
make searching for it faster.

Put the code for handling the next-leaf allocation in a separate
function. When taking blocks from the next leaf empties the leaf, be
sure to clear the appropriate bit in its parent, and so on, up to the
least-common ancestor of this leaf and the next.

Eliminate special terminator nodes, and rely instead on the fact that
there is a 0-bit at the end of the bitmask at the root of the tree that
will stop a meta_alloc search, or a next-leaf search, before the search
falls off the end of the tree. Make sure that the tree is big enough to
have space for that 0-bit.

Eliminate special all-free indicators. Lazy initialization of subtrees
stands in the way of having an allocation span a meta-node boundary, so
a subtree of all free blocks is not treated specially. Subtrees of
all-allocated blocks are still recognized by looking at the bitmask at
the root and finding 0.

Don't print all-allocated subtrees. Do print the bitmasks for meta
nodes, when tree-printing.

Submitted by: Doug Moore <dougm@rice.edu>
Reviewed by: alc
MFC after: 1 month
Differential Revision: https://reviews.freebsd.org/D12635

show more ...

Correct the condition under which we allocate a terminator node.

We will have last_block < blocks if the block count is divisible
by BLIST_BMAP_RADIX, but a terminator node is still needed if the
tr

Correct the condition under which we allocate a terminator node.

We will have last_block < blocks if the block count is divisible
by BLIST_BMAP_RADIX, but a terminator node is still needed if the
tree isn't balanced. In this case we were overruning the blist
array by 16 bytes during initialization.

While here, add a check for the invalid blocks == 0 case.

PR: 231116
Reviewed by: alc, kib (previous version), Doug Moore <dougm@rice.edu>
Approved by: re (gjb)
MFC after: 1 week
Sponsored by: The FreeBSD Foundation
Differential Revision: https://reviews.freebsd.org/D17020

show more ...