#
0a713948 |
|
22-Nov-2023 |
Alexander Motin <mav@FreeBSD.org> |
Replace random sbuf_printf() with cheaper cat/putc.
|
#
685dc743 |
|
16-Aug-2023 |
Warner Losh <imp@FreeBSD.org> |
sys: Remove $FreeBSD$: one-line .c pattern Remove /^[\s*]*__FBSDID\("\$FreeBSD\$"\);?\s*\n/
|
#
d4e236c7 |
|
06-Jul-2023 |
Doug Moore <dougm@FreeBSD.org> |
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
|
#
2783335c |
|
13-Jul-2021 |
Mark Johnston <markj@FreeBSD.org> |
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
|
#
6fed89b1 |
|
01-Sep-2020 |
Mateusz Guzik <mjg@FreeBSD.org> |
kern: clean up empty lines in .c and .h files
|
#
00fd73d2 |
|
25-Jul-2020 |
Doug Moore <dougm@FreeBSD.org> |
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
|
#
3ff65f71 |
|
30-Jan-2020 |
Mateusz Guzik <mjg@FreeBSD.org> |
Remove duplicated empty lines from kern/*.c No functional changes.
|
#
9f70442a |
|
14-Dec-2019 |
Doug Moore <dougm@FreeBSD.org> |
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
|
#
3f3f7c05 |
|
11-Jul-2019 |
Doug Moore <dougm@FreeBSD.org> |
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
|
#
31c82722 |
|
06-Jul-2019 |
Doug Moore <dougm@FreeBSD.org> |
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
|
#
87ae0686 |
|
11-May-2019 |
Doug Moore <dougm@FreeBSD.org> |
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
|
#
53519253 |
|
11-May-2019 |
Doug Moore <dougm@FreeBSD.org> |
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
|
#
0cb36fc9 |
|
10-May-2019 |
Doug Moore <dougm@FreeBSD.org> |
Revert r347469. Approved by: kib (mentor)
|
#
12cd7ded |
|
10-May-2019 |
Doug Moore <dougm@FreeBSD.org> |
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
|
#
4ab18ea2 |
|
10-May-2019 |
Doug Moore <dougm@FreeBSD.org> |
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
|
#
d4808c44 |
|
10-May-2019 |
Doug Moore <dougm@FreeBSD.org> |
Add a (q)uit option to the subr_blist test program. Approved by: kib (mentor) Differential Revision: https://reviews.freebsd.org/D20234
|
#
09b380a1 |
|
10-May-2019 |
Doug Moore <dougm@FreeBSD.org> |
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
|
#
d1c34a6b |
|
10-May-2019 |
Doug Moore <dougm@FreeBSD.org> |
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
|
#
b1f59c92 |
|
10-May-2019 |
Doug Moore <dougm@FreeBSD.org> |
Replace panic() with KASSERT() and provide more useful information when failure happens. Approved by: kib (mentor) Differential Revision: https://reviews.freebsd.org/D20226
|
#
27d172bb |
|
06-May-2019 |
Doug Moore <dougm@FreeBSD.org> |
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
|
#
2905d1ce |
|
09-Dec-2018 |
Alan Cox <alc@FreeBSD.org> |
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
|
#
749cdf6f |
|
05-Dec-2018 |
Alan Cox <alc@FreeBSD.org> |
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
|
#
ee73fef9 |
|
24-Nov-2018 |
Alan Cox <alc@FreeBSD.org> |
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
|
#
bb4a27f9 |
|
13-Nov-2018 |
Mark Johnston <markj@FreeBSD.org> |
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
|
#
ce9eea64 |
|
05-Sep-2018 |
Mark Johnston <markj@FreeBSD.org> |
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
|
#
51369649 |
|
20-Nov-2017 |
Pedro F. Giffuni <pfg@FreeBSD.org> |
sys: further adoption of SPDX licensing ID tags. Mainly focus on files that use BSD 3-Clause license. The Software Package Data Exchange (SPDX) group provides a specification to make it easier for automated tools to detect and summarize well known opensource licenses. We are gradually adopting the specification, noting that the tags are considered only advisory and do not, in any way, superceed or replace the license texts. Special thanks to Wind River for providing access to "The Duke of Highlander" tool: an older (2014) run over FreeBSD tree was useful as a starting point.
|
#
03ca2137 |
|
09-Oct-2017 |
Alan Cox <alc@FreeBSD.org> |
The recent change to initialization of blists (r324420) relied on '-1' appearing only where the code explicitly set it, but since much of the data was not initialized, '-1' appeared other places too, and led to panics. Clear the allocated data before initializing nonzero values by allocating with M_ZERO. Submitted by: Doug Moore <dougm@rice.edu> Reported by: Oleg V. Nauman <oleg@theweb.org.ua>, cy Tested by: Oleg V. Nauman <oleg@theweb.org.ua> MFC after: 1 week X-MFC with: r324420 Differential Revision: https://reviews.freebsd.org/D12627
|
#
8eefcd40 |
|
08-Oct-2017 |
Alan Cox <alc@FreeBSD.org> |
The blst_radix_init function has two purposes - to compute the number of nodes to allocate for the blist, and to initialize them. The computation can be done much more quickly by identifying the terminating node, if any, at every level of the tree and then summing the number of nodes at each level that precedes the topmost terminator. The initialization can also be done quickly, since settings at the root mark the tree as all-allocated, and only a few terminator nodes need to be marked in the rest of the tree. Eliminate blst_radix_init, and perform its two functions more simply in blist_create. The allocation of the blist takes places in two pieces, but there's no good reason to do so, when a single allocation is sufficient, and simpler. Allocate the blist struct, and the array of nodes associated with it, with a single allocation. Submitted by: Doug Moore <dougm@rice.edu> Reviewed by: markj (an earlier version) MFC after: 1 week Differential Revision: https://reviews.freebsd.org/D11968
|
#
ec371b57 |
|
16-Sep-2017 |
Alan Cox <alc@FreeBSD.org> |
Modify blst_leaf_alloc to take only the cursor argument. Modify blst_leaf_alloc to find allocations that cross the boundary between one leaf node and the next when those two leaves descend from the same meta node. Update the hint field for leaves so that it represents a bound on how large an allocation can begin in that leaf, where it currently represents a bound on how large an allocation can be found within the boundaries of the leaf. The first phase of blst_leaf_alloc currently shrinks sequences of consecutive 1-bits in mask until each has been shrunken by count-1 bits, so that any bits remaining show where an allocation can begin, or until all the bits have disappeared, in which case the allocation fails. This change amends that so that the high-order bit is copied, as if, when the last block was free, it was followed by an endless stream of free blocks. It also amends the early stopping condition, so that the shrinking of 1-sequences stops early when there are none, or there is only one unbounded one remaining. The search for the first set bit is unchanged, and the code path thereafter is mostly unchanged unless the first set bit is in a position that makes some of those copied sign bits matter. In that case, we look for a next leaf, and at what blocks it can provide, to see if a cross-boundary allocation is possible. The hint is updated on a successful allocation that clears the last bit, but it not updated on a failed allocation that leaves the last bit set. So, as long as the last block is free, the hint value for the leaf is large. As long as the last block is free, and there's a next leaf, a large allocation can begin here, perhaps. A stricter rule than this would mean that allocations and frees in one leaf could require hint updates to the preceding leaf, and this change seeks to leave the freeing code unmodified. Define BLIST_BMAP_MASK, and use it for bit masking in blst_leaf_free and blist_leaf_fill, as well as in blst_leaf_alloc. Correct a panic message in blst_leaf_free. Submitted by: Doug Moore <dougm@rice.edu> Reviewed by: markj (an earlier version) MFC after: 1 week Differential Revision: https://reviews.freebsd.org/D11819
|
#
d027ed2e |
|
10-Sep-2017 |
Alan Cox <alc@FreeBSD.org> |
To analyze the allocation of swap blocks by blist functions, add a method for analyzing the radix tree structures and reporting on the number, and sizes, of maximal intervals of free blocks. The report includes the number of maximal intervals, and also the number of them in each of several size ranges, from small (size 1, or 3 to 4) to large (28657 to 46367) with size boundaries defined by Fibonacci numbers. The report is written in the test tool with the 's' command, or in a running kernel by sysctl. The analysis of the radix tree frequently computes the position of the lone bit set in a u_daddr_t, a computation that also appears in leaf allocation. That computation has been moved into a function of its own, and optimized for cases where an inlined machine instruction can replace the usual binary search. Submitted by: Doug Moore <dougm@rice.edu> MFC after: 1 week Differential Revision: https://reviews.freebsd.org/D11906
|
#
a0ae476b |
|
25-Aug-2017 |
Alan Cox <alc@FreeBSD.org> |
Correct a regression in the previous change, r322459. Specifically, the removal of the "blk" parameter from blst_meta_alloc() had the unintended effect of generating an out-of-range allocation when the cursor reaches the end of the tree if the number of managed blocks in the tree equals the so-called "radix" (which in the blist code is not the standard notion of what a radix is but rather the maximum number of leaves in a tree of the current height.) In other words, only certain swap configurations were affected, which is why earlier testing did not reveal the problem. Submitted by: Doug Moore <dougm@rice.edu> Reported by: pho, kib Tested by: pho X-MFC with: r322459 Differential Revision: https://reviews.freebsd.org/D12106
|
#
bee93d3c |
|
13-Aug-2017 |
Alan Cox <alc@FreeBSD.org> |
The *_meta_* functions include a radix parameter, a blk parameter, and another parameter that identifies a starting point in the memory address block. Radix is a power of two, blk is a multiple of radix, and the starting point is in the range [blk, blk+radix), so that blk can always be computed from the other two. This change drops the blk parameter from the meta functions and computes it instead. (On amd64, for example, this change reduces subr_blist.o's text size by 7%.) It also makes the radix parameters unsigned to address concerns that the calculation of '-radix' might overflow without the -fwrapv option. (See https://reviews.freebsd.org/D11819.) Submitted by: Doug Moore <dougm@rice.edu> MFC after: 1 week Differential Revision: https://reviews.freebsd.org/D11964
|
#
ba98e6a2 |
|
03-Aug-2017 |
Alan Cox <alc@FreeBSD.org> |
In case readers are misled by expressions that combine multiplication and division, add parentheses to make the precedence explicit. Submitted by: Doug Moore <dougm@rice.edu> Requested by: imp Reviewed by: imp MFC after: 1 week X-MFC after: r321840 Differential Revision: https://reviews.freebsd.org/D11815
|
#
2ac0c7c3 |
|
31-Jul-2017 |
Alan Cox <alc@FreeBSD.org> |
The blist_meta_* routines that process a subtree take arguments 'radix' and 'skip', which denote, respectively, the largest number of blocks that can be managed by a subtree of that height, and one less than the number of nodes in a subtree of that height. This change removes the 'skip' argument from those functions because 'skip' can be trivially computed from 'radius'. This change also redefines 'skip' so that it denotes the number of nodes in the subtree, and so changes loop upper bound tests from '<= skip' to '< skip' to account for the change. The 'skip' field is also removed from the blist struct. The self-test program is changed so that the print command includes the cursor value in the output. Submitted by: Doug Moore <dougm@rice.edu> MFC after: 1 week
|
#
a396c83a |
|
24-Jul-2017 |
Alan Cox <alc@FreeBSD.org> |
Change the interactions of the interface functions with the "meta" and "leaf" functions for alloc, free, and fill. After the change, the interface functions call "meta" unconditionally, and the "meta" functions recur unconditionally in looping over their descendants. The "meta" functions start with a validity test, and then a test for the "leaf" case, before falling into the general recursive case. This simplifies and shrinks the code, and, for "free" and "fill" moves panic tests that check the same meta node repeatedly in a loop to a place that will have each node tested once. Remove irrelevant null checks from blist_free and blist_fill. Make the code that initializes a meta node the same in blist_meta_alloc and blist_meta_fill. Parenthesize return expressions in blst_meta_fill. Submitted by: Doug Moore <dougm@rice.edu> MFC after: 1 week
|
#
b411efa4 |
|
17-Jul-2017 |
Alan Cox <alc@FreeBSD.org> |
Tidy up before making another round of functional changes: Remove end- of-line whitespace, remove excessive whitespace and blank lines, remove dead code, follow our standard style for function definitions, and correct grammatical and factual errors in some of the comments. Submitted by: Doug Moore <dougm@rice.edu> MFC after: 1 week
|
#
54541421 |
|
30-Jun-2017 |
Alan Cox <alc@FreeBSD.org> |
Change blst_leaf_alloc() to handle a cursor argument, and to improve performance. To find in the leaf bitmap all ranges of sufficient length, use a doubling strategy with shift-and-and until each bit still set represents a bit sequence of length 'count', or until the bitmask is zero. In the latter case, update the hint based on the first bit sequence length not found to be available. For example, seeking an interval of length 12, the set bits of the bitmap would represent intervals of length 1, then 2, then 3, then 6, then 12. If no bits are set at the point when each bit represents an interval of length 6, then the hint can be updated to 5 and the search terminated. If long-enough intervals are found, discard those before the cursor. If any remain, use binary search to find the position of the first of them, and allocate that interval. Submitted by: Doug Moore <dougm@rice.edu> Reviewed by: kib, markj MFC after: 3 weeks Differential Revision: https://reviews.freebsd.org/D11426
|
#
d3783724 |
|
27-Jun-2017 |
Alan Cox <alc@FreeBSD.org> |
Address the remaining integer overflow issues with the "skip" parameters and "next_skip" variables. The "skip" value in struct blist has long been a 64-bit quantity but various functions have implicitly truncated this value to 32 bits. Now, all arithmetic involving the "skip" value is 64 bits wide. (This should allow us to relax the size limit on a swap device in the swap pager.) Maintain the ability to test this allocator as a user-space application by including <stdbool.h>. Remove an unused variable from blst_radix_print(). Reviewed by: kib, markj MFC after: 4 weeks Differential Revision: https://reviews.freebsd.org/D11358
|
#
d4e3484b |
|
18-Jun-2017 |
Alan Cox <alc@FreeBSD.org> |
Change blist_alloc()'s allocation policy from first-fit to next-fit so that disk writes are more likely to be sequential. This change is beneficial on both the solid state and mechanical disks that I've tested. (A similar change in allocation policy was made by DragonFly BSD in 2013 to speed up Poudriere with "stressful memory parameters".) Increase the width of blst_meta_alloc()'s parameter "skip" and the local variables whose values are derived from it to 64 bits. (This matches the width of the field "skip" that is stored in the structure "blist" and passed to blst_meta_alloc().) Eliminate a pointless check for a NULL blist_t. Simplify blst_meta_alloc()'s handling of the ALL-FREE case. Address nearby style errors. Reviewed by: kib, markj MFC after: 5 weeks Differential Revision: https://reviews.freebsd.org/D11247
|
#
4be4fd5d |
|
13-Jun-2017 |
Alan Cox <alc@FreeBSD.org> |
Reduce the frequency of hint updates on allocation without incurring additional allocation overhead. Previously, blst_meta_alloc() updated the hint after every successful allocation. However, these "eager" hint updates are of no actual benefit if, instead, the "lazy" hint update at the start of blst_meta_alloc() is generalized to handle all cases where the number of available blocks is less than the requested allocation. Previously, the lazy hint update at the start of blst_meta_alloc() only handled the ALL-FULL case. (I would also note that this change provides consistency between blist_alloc() and blist_fill() in that their hint maintenance is now entirely lazy.) Eliminate unnecessary checks for terminators in blst_meta_alloc() and blst_meta_fill() when handling ALL-FREE meta nodes. Eliminate the field "bl_free" from struct blist. It is redundant. Unless the entire radix tree is a single leaf, the count of free blocks is stored in the root node. Instead, provide a function blist_avail() for obtaining the number of free blocks. In blst_meta_alloc(), perform a sanity check on the allocation once rather than repeating it in a loop over the meta node's children. In blst_leaf_fill(), use the optimized bitcount*() function instead of a loop to count the blocks being allocated. Add or improve several comments. Address some nearby style errors. Reviewed by: kib MFC after: 6 weeks Differential Revision: https://reviews.freebsd.org/D11146
|
#
015d7db6 |
|
10-Jun-2017 |
Alan Cox <alc@FreeBSD.org> |
Remove an unnecessary field from struct blist. (The comment describing what this field represented was also inaccurate.) Suggested by: kib In r178792, blist_create() grew a malloc flag, allowing M_NOWAIT to be specified. However, blist_create() was not modified to handle the possibility that a malloc() call failed. Address this omission. Increase the width of the local variable "radix" to 64 bits. (This matches the width of the corresponding field in struct blist.) Reviewed by: kib MFC after: 6 weeks
|
#
a7249a6c |
|
09-Jun-2017 |
Alan Cox <alc@FreeBSD.org> |
blist_fill()'s return type is too narrow. blist_fill() accepts a 64-bit quantity as the size of the range to fill, but returns a 32-bit quantity as the number of blocks that were allocated to fill that range. This revision corrects that mismatch. Currently, swaponsomething() limits the size of a swap area to prevent arithmetic arithmetic overflow in other parts of the blist allocator. That limit has also prevented this type mismatch from causing problems. Reviewed by: kib, markj MFC after: 6 weeks Differential Revision: https://reviews.freebsd.org/D11096
|
#
86dd278f |
|
08-Jun-2017 |
Alan Cox <alc@FreeBSD.org> |
When allocating swap blocks, if the available number of free blocks in a subtree is already zero, then setting the "largest contiguous free block" hint for that subtree to anything other than zero makes no sense. To be clear, assigning a value to the hint that is too large is not a correctness problem, only a pessimization. Dragonfly BSD has applied the same change to blst_meta_alloc() but not blst_meta_fill(). MFC after: 6 weeks
|
#
d90bf7d8 |
|
07-Jun-2017 |
Alan Cox <alc@FreeBSD.org> |
Originally, this file could be compiled as a user-space application for testing purposes. However, over the years, various changes to the kernel have broken this feature. This revision applies some fixes to get user- space compilation working again. There are no changes in this revision to code that is used by the kernel. MFC after: 3 days
|
#
03bdd65f |
|
05-Jun-2017 |
Alan Cox <alc@FreeBSD.org> |
When the function blist_fill() was added to the kernel in r107913, the swap pager used a different scheme for striping the allocation of swap space across multiple devices. And, although blist_fill() was intended to support fill operations with large counts, the old striping scheme never performed a fill larger than the stripe size. Consequently, the misplacement of a sanity check in blst_meta_fill() went undetected. Now, moving forward in time to r118390, a new scheme for striping was introduced that maintained a blist allocator per device, but as noted in r318995, swapoff_one() was not fully and correctly converted to the new scheme. This change completes what was started in r318995 by fixing the underlying bug in blst_meta_fill() that stops swapoff_one() from simply performing a single blist_fill() operation. Reviewed by: kib MFC after: 5 days Differential Revision: https://reviews.freebsd.org/D11043
|
#
064650c1 |
|
05-Jun-2017 |
Alan Cox <alc@FreeBSD.org> |
Halve the memory being internally allocated by the blist allocator. In short, half of the memory that is allocated to implement the radix tree is wasted because we did not change "u_daddr_t" to be a 64-bit unsigned int when we changed "daddr_t" to be a 64-bit (signed) int. (See r96849 and r96851.) Reviewed by: kib, markj Tested by: pho MFC after: 5 days Differential Revision: https://reviews.freebsd.org/D11028
|
#
69a28758 |
|
15-Sep-2016 |
Ed Maste <emaste@FreeBSD.org> |
Renumber license clauses in sys/kern to avoid skipping #3
|
#
e3043798 |
|
29-Apr-2016 |
Pedro F. Giffuni <pfg@FreeBSD.org> |
sys/kern: spelling fixes in comments. No functional change.
|
#
51dc4fea |
|
05-Feb-2013 |
Sergey Kandaurov <pluknet@FreeBSD.org> |
Remove reference to the rlist code from comments, and fix a typo visible in the resulted change. Reviewed by: kib MFC after: 1 week
|
#
f565f395 |
|
03-Dec-2011 |
Eitan Adler <eadler@FreeBSD.org> |
- Fix typos s/(more|less) then|\1 than/ Submitted by: Davide Italiano <davide.italiano@gmail.com> Approved by: brucec MFC after: 3 days
|
#
a7d5f7eb |
|
19-Oct-2010 |
Jamie Gritton <jamie@FreeBSD.org> |
A new jail(8) with a configuration file, to replace the work currently done by /etc/rc.d/jail.
|
#
1ede983c |
|
23-Oct-2008 |
Dag-Erling Smørgrav <des@FreeBSD.org> |
Retire the MALLOC and FREE macros. They are an abomination unto style(9). MFC after: 3 months
|
#
d7f03759 |
|
19-Oct-2008 |
Ulf Lilleengen <lulf@FreeBSD.org> |
- Import the HEAD csup code which is the basis for the cvsmode work.
|
#
c8c7ad92 |
|
05-May-2008 |
Kip Macy <kmacy@FreeBSD.org> |
add malloc flag to blist so that it can be used in ithread context Reviewed by: alc, bsdimp
|
#
62326de7 |
|
03-Jun-2004 |
Alan Cox <alc@FreeBSD.org> |
Move the definitions of SWAPBLK_NONE and SWAPBLK_MASK from vm_page.h to blist.h, enabling the removal of numerous #includes from subr_blist.c. (subr_blist.c and swap_pager.c are the only users of these definitions.)
|
#
06b4bf3e |
|
12-Aug-2003 |
Warner Losh <imp@FreeBSD.org> |
Expand inline the relevant parts of src/COPYRIGHT for Matt Dillon's copyrighted files. Approved by: Matt Dillon
|
#
677b542e |
|
10-Jun-2003 |
David E. O'Brien <obrien@FreeBSD.org> |
Use __FBSDID().
|
#
a163d034 |
|
18-Feb-2003 |
Warner Losh <imp@FreeBSD.org> |
Back out M_* changes, per decision of the TRB. Approved by: trb
|
#
44956c98 |
|
21-Jan-2003 |
Alfred Perlstein <alfred@FreeBSD.org> |
Remove M_TRYWAIT/M_WAITOK/M_WAIT. Callers should use 0. Merge M_NOWAIT/M_DONTWAIT into a single flag M_NOWAIT.
|
#
57e6d29b |
|
10-Jan-2003 |
Matthew Dillon <dillon@FreeBSD.org> |
Remove all use of the LOG2() macro/inline, undoing some non-optimal cruft that crept in recently. GCC will optimize the divides and multiplies for us. Submitted by: David Schultz <dschultz@uclink.Berkeley.EDU> MFC after: 1 day
|
#
92da00bb |
|
15-Dec-2002 |
Matthew Dillon <dillon@FreeBSD.org> |
This is David Schultz's swapoff code which I am finally able to commit. This should be considered highly experimental for the moment. Submitted by: David Schultz <dschultz@uclink.Berkeley.EDU> MFC after: 3 weeks
|
#
bdc9a8d0 |
|
18-May-2002 |
John Baldwin <jhb@FreeBSD.org> |
Now that daddr_t has grown up, use %lld to printf it and cast it to long long.
|
#
0cddd8f0 |
|
04-Jul-2001 |
Matthew Dillon <dillon@FreeBSD.org> |
With Alfred's permission, remove vm_mtx in favor of a fine-grained approach (this commit is just the first stage). Also add various GIANT_ macros to formalize the removal of Giant, making it easy to test in a more piecemeal fashion. These macros will allow us to test fine-grained locks to a degree before removing Giant, and also after, and to remove Giant in a piecemeal fashion via sysctl's on those subsystems which the authors believe can operate without Giant.
|
#
23955314 |
|
18-May-2001 |
Alfred Perlstein <alfred@FreeBSD.org> |
Introduce a global lock for the vm subsystem (vm_mtx). vm_mtx does not recurse and is required for most low level vm operations. faults can not be taken without holding Giant. Memory subsystems can now call the base page allocators safely. Almost all atomic ops were removed as they are covered under the vm mutex. Alpha and ia64 now need to catch up to i386's trap handlers. FFS and NFS have been tested, other filesystems will need minor changes (grabbing the vm lock when twiddling page properties). Reviewed (partially) by: jake, jhb
|
#
7cc0979f |
|
08-Dec-2000 |
David Malone <dwmalone@FreeBSD.org> |
Convert more malloc+bzero to malloc+M_ZERO. Submitted by: josh@zipperup.org Submitted by: Robert Drehmel <robd@gmx.net>
|
#
db5f635a |
|
16-Mar-2000 |
Poul-Henning Kamp <phk@FreeBSD.org> |
Eliminate the undocumented, experimental, non-delivering and highly dangerous MAX_PERF option.
|
#
c4473420 |
|
28-Dec-1999 |
Peter Wemm <peter@FreeBSD.org> |
Change #ifdef KERNEL to #ifdef _KERNEL in the public headers. "KERNEL" is an application space macro and the applications are supposed to be free to use it as they please (but cannot). This is consistant with the other BSD's who made this change quite some time ago. More commits to come.
|
#
923502ff |
|
29-Oct-1999 |
Poul-Henning Kamp <phk@FreeBSD.org> |
useracc() the prequel: Merge the contents (less some trivial bordering the silly comments) of <vm/vm_prot.h> and <vm/vm_inherit.h> into <vm/vm.h>. This puts the #defines for the vm_inherit_t and vm_prot_t types next to their typedefs. This paves the road for the commit to follow shortly: change useracc() to use VM_PROT_{READ|WRITE} rather than B_{READ|WRITE} as argument.
|
#
c3aac50f |
|
27-Aug-1999 |
Peter Wemm <peter@FreeBSD.org> |
$Id$ -> $FreeBSD$
|
#
0625ba2f |
|
17-Jun-1999 |
Gary Palmer <gpalmer@FreeBSD.org> |
Add Id strings
|
#
7090df5a |
|
21-Jan-1999 |
Matthew Dillon <dillon@FreeBSD.org> |
Add new blist module - radix tree based bitmap allocator with size hinting. Will be used by the new swapper.
|