#
331722 |
|
29-Mar-2018 |
eadler |
Revert r330897:
This was intended to be a non-functional change. It wasn't. The commit message was thus wrong. In addition it broke arm, and merged crypto related code.
Revert with prejudice.
This revert skips files touched in r316370 since that commit was since MFCed. This revert also skips files that require $FreeBSD$ property changes.
Thank you to those who helped me get out of this mess including but not limited to gonzo, kevans, rgrimes.
Requested by: gjb (re)
|
#
330897 |
|
14-Mar-2018 |
eadler |
Partial merge of the SPDX changes
These changes are incomplete but are making it difficult to determine what other changes can/should be merged.
No objections from: pfg
|
#
324384 |
|
07-Oct-2017 |
alc |
MFC r323656 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.
|
#
324131 |
|
30-Sep-2017 |
alc |
MFC r323391 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.
|
#
324130 |
|
30-Sep-2017 |
alc |
MFC r322459,322897 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.)
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.
|
#
323681 |
|
17-Sep-2017 |
alc |
MFC r321840,322041 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.
In case readers are misled by expressions that combine multiplication and division, add parentheses to make the precedence explicit.
|
#
323665 |
|
17-Sep-2017 |
alc |
MFC r321423 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.
|
#
323664 |
|
17-Sep-2017 |
alc |
MFC r321102 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.
|
#
321453 |
|
25-Jul-2017 |
alc |
MFC r320077 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.
MFC r320417 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().
MFC r320527 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.
|
#
321374 |
|
22-Jul-2017 |
alc |
MFC r319905
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.
|
#
320621 |
|
03-Jul-2017 |
alc |
MFC r319699 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.)
MFC r319755 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.
MFC r319793 Remove an unnecessary field from struct blist. (The comment describing what this field represented was also inaccurate.)
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.
|
#
319981 |
|
15-Jun-2017 |
alc |
MFC r318995 In r118390, the swap pager's approach to striping swap allocation over multiple devices was changed. However, swapoff_one() was not fully and correctly converted. In particular, with r118390's introduction of a per- device blist, the maximum swap block size, "dmmax", became irrelevant to swapoff_one()'s operation. Moreover, swapoff_one() was performing out-of- range operations on the per-device blist that were silently ignored by blist_fill().
This change corrects both of these problems with swapoff_one(), which will allow us to potentially increase MAX_PAGEOUT_CLUSTER. Previously, swapoff_one() would panic inside of blist_fill() if you increased MAX_PAGEOUT_CLUSTER.
MFC r319001 After r118390, the variable "dmmax" was neither the correct strip size nor the correct maximum block size. Moreover, after r318995, it serves no purpose except to provide information to user space through a read- sysctl.
This change eliminates the variable "dmmax" but retains the sysctl. It also corrects the value returned by the sysctl.
MFC r319604 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.)
MFC r319612 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.
MFC r319627 Starting in r118390, swaponsomething() began to reserve the blocks at the beginning of a swap area for a disk label. However, neither r118390 nor r118544, which increased the reservation from one to two blocks, correctly accounted for these blocks when updating the variable "swap_pager_avail". This change corrects that error.
MFC r319655 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.
Approved by: re (kib)
|
#
302408 |
|
07-Jul-2016 |
gjb |
Copy head@r302406 to stable/11 as part of the 11.0-RELEASE cycle. Prune svn:mergeinfo from the new branch, as nothing has been merged here.
Additional commits post-branch will follow.
Approved by: re (implicit) Sponsored by: The FreeBSD Foundation |
#
298819 |
|
29-Apr-2016 |
pfg |
sys/kern: spelling fixes in comments.
No functional change.
|
#
246370 |
|
05-Feb-2013 |
pluknet |
Remove reference to the rlist code from comments, and fix a typo visible in the resulted change.
Reviewed by: kib MFC after: 1 week
|
#
228233 |
|
03-Dec-2011 |
eadler |
- Fix typos s/(more|less) then|\1 than/
Submitted by: Davide Italiano <davide.italiano@gmail.com> Approved by: brucec MFC after: 3 days
|
#
184205 |
|
23-Oct-2008 |
des |
Retire the MALLOC and FREE macros. They are an abomination unto style(9).
MFC after: 3 months
|
#
178792 |
|
05-May-2008 |
kmacy |
add malloc flag to blist so that it can be used in ithread context
Reviewed by: alc, bsdimp
|
#
130049 |
|
04-Jun-2004 |
alc |
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.)
|
#
118848 |
|
12-Aug-2003 |
imp |
Expand inline the relevant parts of src/COPYRIGHT for Matt Dillon's copyrighted files.
Approved by: Matt Dillon
|
#
116182 |
|
10-Jun-2003 |
obrien |
Use __FBSDID().
|
#
111119 |
|
19-Feb-2003 |
imp |
Back out M_* changes, per decision of the TRB.
Approved by: trb
|
#
109623 |
|
21-Jan-2003 |
alfred |
Remove M_TRYWAIT/M_WAITOK/M_WAIT. Callers should use 0. Merge M_NOWAIT/M_DONTWAIT into a single flag M_NOWAIT.
|
#
109086 |
|
10-Jan-2003 |
dillon |
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
|
#
107913 |
|
15-Dec-2002 |
dillon |
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
|
#
96882 |
|
18-May-2002 |
jhb |
Now that daddr_t has grown up, use %lld to printf it and cast it to long long.
|
#
79224 |
|
04-Jul-2001 |
dillon |
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.
|
#
76827 |
|
18-May-2001 |
alfred |
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
|
#
69781 |
|
08-Dec-2000 |
dwmalone |
Convert more malloc+bzero to malloc+M_ZERO.
Submitted by: josh@zipperup.org Submitted by: Robert Drehmel <robd@gmx.net>
|
#
58132 |
|
16-Mar-2000 |
phk |
Eliminate the undocumented, experimental, non-delivering and highly dangerous MAX_PERF option.
|
#
55206 |
|
29-Dec-1999 |
peter |
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.
|
#
52635 |
|
29-Oct-1999 |
phk |
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.
|
#
50477 |
|
27-Aug-1999 |
peter |
$Id$ -> $FreeBSD$
|
#
47989 |
|
17-Jun-1999 |
gpalmer |
Add Id strings
|
#
42956 |
|
21-Jan-1999 |
dillon |
Add new blist module - radix tree based bitmap allocator with size hinting. Will be used by the new swapper.
|