aboutsummaryrefslogtreecommitdiff
path: root/sys/sys/blist.h
Commit message (Collapse)AuthorAgeFilesLines
* sys: clean up empty lines in .c and .h filesMateusz Guzik2020-09-011-1/+0
| | | | Notes: svn path=/head/; revision=365223
* Fix an overflow bug in the blist allocator that needlessly capped maxDoug Moore2020-07-251-3/+2
| | | | | | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=363532
* A new parameter to blist_alloc specifies an upper bound on the size ofDoug Moore2019-05-111-2/+2
| | | | | | | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=347493
* A major change to subr_blist.c failed to update all the comments aboutDoug Moore2019-05-101-3/+3
| | | | | | | | | | changes to struct fields. Update those now. Approved by: markj (mentor) Differential Revision: https://reviews.freebsd.org/D20227 Notes: svn path=/head/; revision=347433
* Allow allocations across meta boundaries.Mark Johnston2018-11-131-5/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=340402
* sys: further adoption of SPDX licensing ID tags.Pedro F. Giffuni2017-11-201-0/+2
| | | | | | | | | | | | | | | | | 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. Notes: svn path=/head/; revision=326023
* The blst_radix_init function has two purposes - to compute the number ofAlan Cox2017-10-081-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=324420
* To analyze the allocation of swap blocks by blist functions, add a methodAlan Cox2017-09-101-0/+3
| | | | | | | | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=323391
* The *_meta_* functions include a radix parameter, a blk parameter, andAlan Cox2017-08-131-1/+1
| | | | | | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=322459
* The blist_meta_* routines that process a subtree take arguments 'radix' andAlan Cox2017-08-011-1/+0
| | | | | | | | | | | | | | | | | | | | | '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 Notes: svn path=/head/; revision=321840
* Change blist_alloc()'s allocation policy from first-fit to next-fit soAlan Cox2017-06-181-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=320077
* Reduce the frequency of hint updates on allocation without incurringAlan Cox2017-06-131-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=319905
* Remove an unnecessary field from struct blist. (The comment describingAlan Cox2017-06-101-1/+0
| | | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=319793
* Style and comment fixes only.Alan Cox2017-06-091-8/+8
| | | | | | | | Reviewed by: kib MFC after: 6 weeks Notes: svn path=/head/; revision=319756
* blist_fill()'s return type is too narrow. blist_fill() accepts a 64-bitAlan Cox2017-06-091-1/+1
| | | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=319755
* Halve the memory being internally allocated by the blist allocator. InAlan Cox2017-06-051-2/+2
| | | | | | | | | | | | | | | 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 Notes: svn path=/head/; revision=319604
* Renumber copyright clause 4Warner Losh2017-02-281-1/+1
| | | | | | | | | | | | Renumber cluase 4 to 3, per what everybody else did when BSD granted them permission to remove clause 3. My insistance on keeping the same numbering for legal reasons is too pedantic, so give up on that point. Submitted by: Jan Schaumann <jschauma@stevens.edu> Pull Request: https://github.com/freebsd/freebsd/pull/96 Notes: svn path=/head/; revision=314436
* add malloc flag to blist so that it can be used in ithread contextKip Macy2008-05-051-4/+5
| | | | | | | Reviewed by: alc, bsdimp Notes: svn path=/head/; revision=178792
* /* -> /*- for license, minor formatting changesWarner Losh2005-01-071-1/+3
| | | | Notes: svn path=/head/; revision=139825
* Move the definitions of SWAPBLK_NONE and SWAPBLK_MASK from vm_page.h toAlan Cox2004-06-041-0/+8
| | | | | | | | 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.) Notes: svn path=/head/; revision=130049
* Expand inline the relevant parts of src/COPYRIGHT for Matt Dillon'sWarner Losh2003-08-121-3/+25
| | | | | | | | | copyrighted files. Approved by: Matt Dillon Notes: svn path=/head/; revision=118848
* Remove all use of the LOG2() macro/inline, undoing some non-optimal cruftMatthew Dillon2003-01-111-16/+0
| | | | | | | | | | 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 Notes: svn path=/head/; revision=109086
* This is David Schultz's swapoff code which I am finally able to commit.Matthew Dillon2002-12-151-0/+2
| | | | | | | | | | This should be considered highly experimental for the moment. Submitted by: David Schultz <dschultz@uclink.Berkeley.EDU> MFC after: 3 weeks Notes: svn path=/head/; revision=107913
* Move the hideously misnamed type "u_daddr_t" to <sys/blist.h> where itPoul-Henning Kamp2002-05-181-0/+2
| | | | | | | | | belongs. Sponsored by: DARPA & NAI Labs. Notes: svn path=/head/; revision=96849
* Roll the LOG2 macro up again, I don't belive unrolling this for 64bitsPoul-Henning Kamp2002-05-141-31/+13
| | | | | | | | | make sense. Sponsored by: DARPA & NAI Labs. Notes: svn path=/head/; revision=96567
* $Id$ -> $FreeBSD$Peter Wemm1999-08-281-1/+1
| | | | Notes: svn path=/head/; revision=50477
* Add new blist module - radix tree based bitmap allocator withMatthew Dillon1999-01-211-0/+101
size hinting. Will be used by the new swapper. Notes: svn path=/head/; revision=42956
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-27 22:50:06 +0000