/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2008 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
* Copyright 2012 Joyent, Inc. All rights reserved.
*/
/*
* For a more complete description of the main ideas, see:
*
* Jeff Bonwick and Jonathan Adams,
*
* Magazines and vmem: Extending the Slab Allocator to Many CPUs and
* Arbitrary Resources.
*
* Proceedings of the 2001 Usenix Conference.
*
*
* 1. Overview of changes
* ------------------------------
* There have been a few changes to vmem in order to support umem. The
* main areas are:
*
* * VM_SLEEP unsupported
*
* * Reaping changes
*
* * initialization changes
*
* * _vmem_extend_alloc
*
*
* 2. VM_SLEEP Removed
* -------------------
* Since VM_SLEEP allocations can hold locks (in vmem_populate()) for
* possibly infinite amounts of time, they are not supported in this
* version of vmem. Sleep-like behavior can be achieved through
* UMEM_NOFAIL umem allocations.
*
*
* 3. Reaping changes
* ------------------
* Unlike kmem_reap(), which just asynchronously schedules work, umem_reap()
* can do allocations and frees synchronously. This is a problem if it
* occurs during a vmem_populate() allocation.
*
* Instead, we delay reaps while populates are active.
*
*
* 4. Initialization changes
* -------------------------
* In the kernel, vmem_init() allows you to create a single, top-level arena,
* which has vmem_internal_arena as a child. For umem, we want to be able
* to extend arenas dynamically. It is much easier to support this if we
* allow a two-level "heap" arena:
*
* +----------+
* | "fake" |
* +----------+
* |
* +----------+
* | "heap" |
* +----------+
* | \ \
* | +-+-- ... <other children>
* |
* +---------------+
* | vmem_internal |
* +---------------+
* | | | |
* <children>
*
* The new vmem_init() allows you to specify a "parent" of the heap, along
* with allocation functions.
*
*
* 5. _vmem_extend_alloc
* ---------------------
* The other part of extending is _vmem_extend_alloc. This function allows
* you to extend (expand current spans, if possible) an arena and allocate
* a chunk of the newly extened span atomically. This is needed to support
* extending the heap while vmem_populate()ing it.
*
* In order to increase the usefulness of extending, non-imported spans are
* sorted in address order.
*/
#include <sys/vmem_impl_user.h>
#include <alloca.h>
#include <sys/sysmacros.h>
#include <stdio.h>
#include <strings.h>
#include <atomic.h>
#include "vmem_base.h"
#include "umem_base.h"
/*
* Adding a new span to an arena requires two segment structures: one to
* represent the span, and one to represent the free segment it contains.
*/
/*
* Allocating a piece of an existing segment requires 0-2 segment structures
* depending on how much of the segment we're allocating.
*
* To allocate the entire segment, no new segment structures are needed; we
* simply move the existing segment structure from the freelist to the
* allocation hash table.
*
* To allocate a piece from the left or right end of the segment, we must
* split the segment into two pieces (allocated part and remainder), so we
* need one new segment structure to represent the remainder.
*
* To allocate from the middle of a segment, we need two new segment strucures
* to represent the remainders on either side of the allocated part.
*/
#define VMEM_SEGS_PER_EXACT_ALLOC 0
/*
* vmem_populate() preallocates segment structures for vmem to do its work.
* It must preallocate enough for the worst case, which is when we must import
* a new span and then allocate from the middle of it.
*/
#define VMEM_SEGS_PER_ALLOC_MAX \
/*
* The segment structures themselves are allocated from vmem_seg_arena, so
* we have a recursion problem when vmem_seg_arena needs to populate itself.
* We address this by working out the maximum number of segment structures
* this act will require, and multiplying by the maximum number of threads
* that we'll allow to do it simultaneously.
*
* The worst-case segment consumption to populate vmem_seg_arena is as
* follows (depicted as a stack trace to indicate why events are occurring):
*
* vmem_alloc(vmem_seg_arena) -> 2 segs (span create + exact alloc)
* vmem_alloc(vmem_internal_arena) -> 2 segs (span create + exact alloc)
* heap_alloc(heap_arena)
* vmem_alloc(heap_arena) -> 4 seg (span create + alloc)
* parent_alloc(parent_arena)
* _vmem_extend_alloc(parent_arena) -> 3 seg (span create + left alloc)
*
* Note: The reservation for heap_arena must be 4, since vmem_xalloc()
* is overly pessimistic on allocations where parent_arena has a stricter
* alignment than heap_arena.
*
* The worst-case consumption for any arena is 4 segment structures.
* For now, we only support VM_NOSLEEP allocations, so as long as we
* serialize all vmem_populates, a 4-seg reserve is sufficient.
*/
#define VMEM_POPULATE_RESERVE \
/*
* vmem_populate() ensures that each arena has VMEM_MINFREE seg structures
* so that it can satisfy the worst-case allocation *and* participate in
* worst-case allocation from vmem_seg_arena.
*/
/* Don't assume new statics are zeroed - see vmem_startup() */
/*
*/
{ \
}
{ \
}
/*
* Get a vmem_seg_t from the global segfree list.
*/
static vmem_seg_t *
vmem_getseg_global(void)
{
(void) mutex_lock(&vmem_segfree_lock);
(void) mutex_unlock(&vmem_segfree_lock);
return (vsp);
}
/*
* Put a vmem_seg_t on the global segfree list.
*/
static void
{
(void) mutex_lock(&vmem_segfree_lock);
vmem_segfree = vsp;
(void) mutex_unlock(&vmem_segfree_lock);
}
/*
* Get a vmem_seg_t from vmp's segfree list.
*/
static vmem_seg_t *
{
vmp->vm_nsegfree--;
return (vsp);
}
/*
* Put a vmem_seg_t on vmp's segfree list.
*/
static void
{
vmp->vm_nsegfree++;
}
/*
* Add vsp to the appropriate freelist.
*/
static void
{
}
/*
* Take vsp from the freelist.
*/
static void
{
/*
* The segments on both sides of 'vsp' are freelist heads,
* so taking vsp leaves the freelist at vsp->vs_kprev empty.
*/
}
VMEM_DELETE(vsp, k);
}
/*
* Add vsp to the allocated-segment hash table and update kstats.
*/
static void
{
if (vmem_seg_size == sizeof (vmem_seg_t)) {
VMEM_STACK_DEPTH, 0);
} else {
}
}
/*
* Remove vsp from the allocated-segment hash table and update kstats.
*/
static vmem_seg_t *
{
break;
}
}
umem_panic("vmem_hash_delete(%p, %lx, %lu): bad free",
}
umem_panic("vmem_hash_delete(%p, %lx, %lu): wrong size "
}
return (vsp);
}
/*
* Create a segment spanning the range [start, end) and add it to the arena.
*/
static vmem_seg_t *
{
return (newseg);
}
/*
* Remove segment vsp from the arena.
*/
static void
{
VMEM_DELETE(vsp, a);
}
/*
* Add the span [vaddr, vaddr + size) to vmp and update kstats.
*/
static vmem_seg_t *
{
/*
* non-imported spans are sorted in address order. This
* makes vmem_extend_unlocked() much more effective.
*
* We search in reverse order, since new spans are
* generally at higher addresses.
*/
break;
}
}
umem_panic("vmem_span_create(%p, %p, %lu): misaligned",
}
if (import)
return (newseg);
}
/*
* Remove span vsp from vmp and update kstats.
*/
static void
{
VMEM_DELETE(span, k);
}
/*
* Allocate the subrange [addr, addr + size) from segment vsp.
* If there are leftovers on either side, place them on the freelist.
* Returns a pointer to the segment representing [addr, addr + size).
*/
static vmem_seg_t *
{
/*
* If we're allocating from the start of the segment, and the
* remainder will be on the same freelist, we can save quite
* a bit of work.
*/
return (vsp);
}
return (vsp);
}
/*
* We cannot reap if we are in the middle of a vmem_populate().
*/
void
vmem_reap(void)
{
if (!IN_POPULATE())
umem_reap();
}
/*
* Populate vmp's segfree list with VMEM_MINFREE vmem_seg_t structures.
*/
static int
{
char *p;
int i;
return (1);
/*
* If we're already populating, tap the reserve.
*/
return (1);
}
lp = &vmem_nosleep_lock;
/*
* Cannot be just a mutex_lock(), since that has no effect if
* libthread is not linked.
*/
/*
* The following vmem_alloc() may need to populate vmem_seg_arena
* and all the things it imports from. When doing so, it will tap
* each arena's reserve to prevent recursion (see the block comment
* above the definition of VMEM_POPULATE_RESERVE).
*
* During this allocation, vmem_reap() is a no-op. If the allocation
* fails, we call vmem_reap() after dropping the population lock.
*/
if (p == NULL) {
vmem_reap();
return (0);
}
/*
* Restock the arenas that may have been depleted during population.
*/
for (i = 0; i < vmem_populators; i++) {
}
/*
* Now take our own segments.
*/
/*
* Give the remainder to charity.
*/
while (nseg > 0)
return (1);
}
/*
* Advance a walker from its previous position to 'afterme'.
* Note: may drop and reacquire vmp->vm_lock.
*/
static void
{
VMEM_DELETE(walker, a);
/*
* The walker segment's presence may have prevented its neighbors
* from coalescing. If so, coalesce them now.
*/
}
}
/*
* vsp could represent a complete imported span,
* in which case we must return it to the source.
*/
}
}
/*
* VM_NEXTFIT allocations deliberately cycle through all virtual addresses
* in an arena, so that we avoid reusing addresses for as long as possible.
* This helps to catch used-after-freed bugs. It's also the perfect policy
* for allocating things like process IDs, where we want to cycle through
* all values in order.
*/
static void *
{
return (NULL);
}
/*
* The common case is that the segment right after the rotor is free,
* and large enough that extracting 'size' bytes won't change which
* freelist it's on. In this case we can avoid a *lot* of work.
* Instead of the normal vmem_seg_alloc(), we just advance the start
* address of the victim segment. Instead of moving the rotor, we
* create the new segment structure *behind the rotor*, which has
* the same effect. And finally, we know we don't have to coalesce
* the rotor's neighbors because the new segment lies between them.
*/
return ((void *)addr);
}
/*
* Starting at the rotor, look for a segment large enough to
* satisfy the allocation.
*/
for (;;) {
break;
int cancel_state;
/*
* We've come full circle. One possibility is that the
* there's actually enough space, but the rotor itself
* is preventing the allocation from succeeding because
* it's sitting between two free segments. Therefore,
* we advance the rotor and see if that liberates a
* suitable segment.
*/
break;
/*
* If there's a lower arena we can import from, or it's
* a VM_NOSLEEP allocation, let vmem_xalloc() handle it.
* Otherwise, wait until another thread frees something.
*/
(vmflag & VM_NOSLEEP)) {
}
&cancel_state);
}
}
/*
* We found a segment. Extract enough space to satisfy the allocation.
*/
/*
* Advance the rotor to right after the newly-allocated segment.
* That's where the next VM_NEXTFIT allocation will begin searching.
*/
return ((void *)addr);
}
/*
* Allocate size bytes at offset phase from an align boundary such that the
* resulting segment [addr, addr + size) is a subset of [minaddr, maxaddr)
* that does not straddle a nocross-aligned boundary.
*/
void *
{
void *vaddr;
umem_panic("vmem_xalloc(%p, %lu, %lu, %lu, %lu, %p, %p, %x): "
"invalid phase",
if (align == 0)
umem_panic("vmem_xalloc(%p, %lu, %lu, %lu, %lu, %p, %p, %x): "
"parameters not vm_quantum aligned",
}
if (nocross != 0 &&
umem_panic("vmem_xalloc(%p, %lu, %lu, %lu, %lu, %p, %p, %x): "
"overconstrained allocation",
}
return (NULL);
for (;;) {
int cancel_state;
break;
/*
* highbit() returns the highest bit + 1, which is exactly
* what we want: we want to search the first freelist whose
* members are *definitely* large enough to satisfy our
* allocation. However, there are certain cases in which we
* want to look at the next-smallest freelist (which *might*
* be able to satisfy the allocation):
*
* (1) The size is exactly a power of 2, in which case
* the smaller freelist is always big enough;
*
* (2) All other freelists are empty;
*
* (3) We're in the highest possible freelist, which is
* always empty (e.g. the 4GB freelist on 32-bit systems);
*
* (4) We're doing a best-fit or first-fit allocation.
*/
} else {
hb == VMEM_FREELISTS ||
hb--;
}
/*
* We're moving up to a larger freelist,
* so if we've already found a candidate,
* the fit can't possibly get any better.
*/
break;
/*
* Find the next non-empty freelist.
*/
if (flist-- == 0)
break;
continue;
}
continue;
continue;
taddr +=
continue;
break;
}
break;
if (size == 0)
umem_panic("vmem_xalloc(): size == 0");
if (vmflag & VM_NOSLEEP)
return (NULL);
umem_panic("vmem_xalloc(): "
"overflow on VM_SLEEP allocation");
}
/*
* Determine how many segment structures we'll consume.
* The calculation must be presise because if we're
* here on behalf of vmem_populate(), we are taking
* segments from a very limited reserve.
*/
vmflag & VM_UMFLAGS);
break;
}
}
vmem_reap();
if (vmflag & VM_NOSLEEP)
break;
&cancel_state);
}
return ((void *)addr);
}
umem_panic("vmem_xalloc(%p, %lu, %lu, %lu, %lu, %p, %p, %x): "
"cannot satisfy mandatory allocation",
return (NULL);
}
/*
* Free the segment [vaddr, vaddr + size), where vaddr was a constrained
* allocation. vmem_xalloc() and vmem_xfree() must always be paired because
* both routines bypass the quantum caches.
*/
void
{
/*
* Attempt to coalesce with the next segment.
*/
}
/*
* Attempt to coalesce with the previous segment.
*/
}
/*
* If the entire span is free, return it to the source.
*/
} else {
}
}
/*
* Allocate size bytes from arena vmp. Returns the allocated address
* on success, NULL on failure. vmflag specifies VM_SLEEP or VM_NOSLEEP,
* and may also specify best-fit, first-fit, or next-fit allocation policy
* instead of the default instant-fit policy. VM_SLEEP allocations are
* guaranteed to succeed.
*/
void *
{
int hb;
int flist = 0;
vmflag |= vmem_allocator;
}
return (NULL);
if (vmflag & VM_NEXTFIT)
/*
* Unconstrained instant-fit allocation from the segment list.
*/
}
if (flist-- == 0) {
}
return ((void *)addr);
}
/*
* Free the segment [vaddr, vaddr + size).
*/
void
{
vaddr);
else
}
/*
* Determine whether arena vmp contains the segment [vaddr, vaddr + size).
*/
int
{
break;
}
}
/*
* Add the span [vaddr, vaddr + size) to arena vmp.
*/
void *
{
umem_panic("vmem_add(%p, %p, %lu): bad arguments",
}
else
return (vaddr);
}
/*
* Adds the address range [addr, endaddr) to arena vmp, by either:
* 1. joining two existing spans, [x, addr), and [endaddr, y) (which
* are in that order) into a single [x, y) span,
* 2. expanding an existing [x, addr) span to [x, endaddr),
* 3. expanding an existing [endaddr, x) span to [addr, x), or
* 4. creating a new [addr, endaddr) span.
*
* Called with vmp->vm_lock held, and a successful vmem_populate() completed.
* Cannot fail. Returns the new segment.
*
* NOTE: this algorithm is linear-time in the number of spans, but is
* constant-time when you are extending the last (highest-addressed)
* span.
*/
static vmem_seg_t *
{
/*
* the second "if" clause below relies on the direction of this search
*/
break;
}
/*
* prevspan becomes the span marker for the full range
*/
/*
* Notionally, span becomes a free segment representing
* [addr, endaddr).
*
* However, if either of its neighbors are free, we coalesce
* by destroying span and changing the free segment.
*/
/*
* coalesce both ways
*/
VMEM_DELETE(span, k);
/*
* coalesce left
*/
VMEM_DELETE(span, k);
/*
* coalesce right
*/
VMEM_DELETE(span, k);
} else {
/*
* cannnot coalesce
*/
VMEM_DELETE(span, k);
}
} else
} else {
} else
}
return (vsp);
}
/*
* Does some error checking, calls vmem_extend_unlocked to add
* [vaddr, vaddr+size) to vmp, then allocates alloc bytes from the
* newly merged segment.
*/
void *
int vmflag)
{
return (NULL);
}
/*
* if there is a source, we can't mess with the spans
*/
else
return (vaddr);
}
/*
* Walk the vmp arena, applying func to each segment matching typemask.
* If VMEM_REENTRANT is specified, the arena lock is dropped across each
* call to func(); otherwise, it is held for the duration of vmem_walk()
* to ensure a consistent snapshot. Note that VMEM_REENTRANT callbacks
* are *not* necessarily consistent, so they may only be used when a hint
* is adequate.
*/
void
{
if (typemask & VMEM_WALKER)
return;
if (typemask & VMEM_REENTRANT) {
} else {
}
}
}
}
/*
* Return the total amount of memory whose type matches typemask. Thus:
*
* typemask VMEM_ALLOC yields total memory allocated (in use).
* typemask VMEM_FREE yields total memory free (available).
* typemask (VMEM_ALLOC | VMEM_FREE) yields total arena size.
*/
{
if (typemask & VMEM_ALLOC)
}
/*
* Create an arena called name whose initial span is [base, base + size).
* The arena's natural unit of currency is quantum, so vmem_alloc()
* guarantees quantum-aligned results. The arena may import new spans
* by invoking afunc() on source, and may return those spans by invoking
* ffunc() on source. To make small allocations fast and scalable,
* the arena offers high-performance caching for each integer multiple
* of quantum up to qcache_max.
*/
vmem_t *
{
int i;
if (vmem_vmem_arena != NULL) {
vmflag & VM_UMFLAGS);
} else {
}
return (NULL);
vmflag &= VM_UMFLAGS;
for (i = 0; i <= VMEM_FREELISTS; i++) {
}
if (nqcache != 0) {
for (i = 0; i < nqcache; i++) {
break;
}
}
}
(void) mutex_lock(&vmem_list_lock);
(void) mutex_unlock(&vmem_list_lock);
}
return (NULL);
}
return (vmp);
}
/*
* Destroy arena vmp.
*/
void
{
int i;
(void) mutex_lock(&vmem_list_lock);
(void) mutex_unlock(&vmem_list_lock);
for (i = 0; i < VMEM_NQCACHE_MAX; i++)
if (leaked != 0)
umem_printf("vmem_destroy('%s'): leaked %lu bytes",
/*
* Give back the segment structures for anything that's left in the
* arena, e.g. the primary spans and their free segments.
*/
while (vmp->vm_nsegfree > 0)
}
/*
* Resize vmp's hash table to keep the average lookup depth near 1.0.
*/
static void
{
return;
return;
for (h = 0; h < old_size; h++) {
*hash_bucket = vsp;
}
}
old_size * sizeof (void *));
}
/*
* Perform periodic maintenance on all vmem arenas.
*/
/*ARGSUSED*/
void
{
(void) mutex_lock(&vmem_list_lock);
/*
* If threads are waiting for resources, wake them up
* periodically so they can issue another vmem_reap()
* to reclaim resources cached by the slab allocator.
*/
/*
* Rescale the hash table to keep the hash chains short.
*/
}
(void) mutex_unlock(&vmem_list_lock);
}
/*
* If vmem_init is called again, we need to be able to reset the world.
* That includes resetting the statics back to their original values.
*/
void
vmem_startup(void)
{
#ifdef UMEM_STANDALONE
vmem_id = 0;
vmem_populators = 0;
vmem_segfree = NULL;
#endif
}
/*
* Prepare vmem for use.
*/
vmem_t *
{
while (--nseg >= 0)
if (parent_name != NULL) {
heap_start = NULL;
heap_size = 0;
} else {
}
NULL, 0, heap_quantum,
NULL, 0, heap_quantum,
NULL, 0, 8,
VM_SLEEP);
VM_SLEEP);
return (heap);
}
void
vmem_no_debug(void)
{
/*
* This size must be a multiple of the minimum required alignment,
* since vmem_populate allocates them compactly.
*/
sizeof (hrtime_t));
}
/*
* Lockup and release, for fork1(2) handling.
*/
void
vmem_lockup(void)
{
(void) mutex_lock(&vmem_list_lock);
/*
* Lock up and broadcast all arenas.
*/
}
(void) mutex_lock(&vmem_segfree_lock);
}
void
vmem_release(void)
{
(void) mutex_unlock(&vmem_segfree_lock);
(void) mutex_unlock(&vmem_list_lock);
}