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.

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.

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.

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.

MFC r298819:

sys/kern: spelling fixes in comments.

Copy head (r256279) to stable/10 as part of the 10.0-RELEASE cycle.

Approved by: re (implicit)
Sponsored by: The FreeBSD Foundation

Remove reference to the rlist code from comments, and fix a typo visible
in the resulted change.

Reviewed by: kib
MFC after: 1 week

- Fix typos s/(more|less) then|\1 than/

Submitted by: Davide Italiano <davide.italiano@gmail.com>
Approved by: brucec
MFC after: 3 days

Retire the MALLOC and FREE macros. They are an abomination unto style(9).

MFC after: 3 months

add malloc flag to blist so that it can be used in ithread context

Reviewed by: alc, bsdimp

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.)

Expand inline the relevant parts of src/COPYRIGHT for Matt Dillon's
copyrighted files.

Approved by: Matt Dillon

Use __FBSDID().

Back out M_* changes, per decision of the TRB.

Approved by: trb

Remove M_TRYWAIT/M_WAITOK/M_WAIT. Callers should use 0.
Merge M_NOWAIT/M_DONTWAIT into a single flag M_NOWAIT.

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

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

Now that daddr_t has grown up, use %lld to printf it and cast it to long
long.

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.

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

Convert more malloc+bzero to malloc+M_ZERO.

Submitted by: josh@zipperup.org
Submitted by: Robert Drehmel <robd@gmx.net>

Eliminate the undocumented, experimental, non-delivering and highly
dangerous MAX_PERF option.

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.

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.

$Id$ -> $FreeBSD$

Add Id strings

Add new blist module - radix tree based bitmap allocator with
size hinting. Will be used by the new swapper.