/*

 * CDDL HEADER START

 *

 * The contents of this file are subject to the terms of the

 * Common Development and Distribution License, Version 1.0 only

 * (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

 * or http://www.opensolaris.org/os/licensing.

 * 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 2005 Sun Microsystems, Inc.  All rights reserved.

 * Use is subject to license terms.

 */

#pragma ident	"%Z%%M%	%I%	%E% SMI"

/*

 * Big Theory Statement for the virtual memory allocator.

 *

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

 *	Available as http://www.usenix.org/event/usenix01/bonwick.html

 *

 *

 * 1. General Concepts

 * -------------------

 *

 * 1.1 Overview

 * ------------

 * We divide the kernel address space into a number of logically distinct

 * pieces, or *arenas*: text, data, heap, stack, and so on.  Within these

 * arenas we often subdivide further; for example, we use heap addresses

 * not only for the kernel heap (kmem_alloc() space), but also for DVMA,

 * bp_mapin(), /dev/kmem, and even some device mappings like the TOD chip.

 * The kernel address space, therefore, is most accurately described as

 * a tree of arenas in which each node of the tree *imports* some subset

 * of its parent.  The virtual memory allocator manages these arenas and

 * supports their natural hierarchical structure.

 *

 * 1.2 Arenas

 * ----------

 * An arena is nothing more than a set of integers.  These integers most

 * commonly represent virtual addresses, but in fact they can represent

 * anything at all.  For example, we could use an arena containing the

 * integers minpid through maxpid to allocate process IDs.  vmem_create()

 * and vmem_destroy() create and destroy vmem arenas.  In order to

 * differentiate between arenas used for adresses and arenas used for

 * identifiers, the VMC_IDENTIFIER flag is passed to vmem_create().  This

 * prevents identifier exhaustion from being diagnosed as general memory

 * failure.

 *

 * 1.3 Spans

 * ---------

 * We represent the integers in an arena as a collection of *spans*, or

 * contiguous ranges of integers.  For example, the kernel heap consists

 * of just one span: [kernelheap, ekernelheap).  Spans can be added to an

 * arena in two ways: explicitly, by vmem_add(), or implicitly, by

 * importing, as described in Section 1.5 below.

 *

 * 1.4 Segments

 * ------------

 * Spans are subdivided into *segments*, each of which is either allocated

 * or free.  A segment, like a span, is a contiguous range of integers.

 * Each allocated segment [addr, addr + size) represents exactly one

 * vmem_alloc(size) that returned addr.  Free segments represent the space

 * between allocated segments.  If two free segments are adjacent, we

 * coalesce them into one larger segment; that is, if segments [a, b) and

 * [b, c) are both free, we merge them into a single segment [a, c).

 * The segments within a span are linked together in increasing-address order

 * so we can easily determine whether coalescing is possible.

 *

 * Segments never cross span boundaries.  When all segments within

 * an imported span become free, we return the span to its source.

 *

 * 1.5 Imported Memory

 * -------------------

 * As mentioned in the overview, some arenas are logical subsets of

 * other arenas.  For example, kmem_va_arena (a virtual address cache

 * that satisfies most kmem_slab_create() requests) is just a subset

 * of heap_arena (the kernel heap) that provides caching for the most

 * common slab sizes.  When kmem_va_arena runs out of virtual memory,

 * it *imports* more from the heap; we say that heap_arena is the

 * *vmem source* for kmem_va_arena.  vmem_create() allows you to

 * specify any existing vmem arena as the source for your new arena.

 * Topologically, since every arena is a child of at most one source,

 * the set of all arenas forms a collection of trees.

 *

 * 1.6 Constrained Allocations

 * ---------------------------

 * Some vmem clients are quite picky about the kind of address they want.

 * For example, the DVMA code may need an address that is at a particular

 * phase with respect to some alignment (to get good cache coloring), or

 * that lies within certain limits (the addressable range of a device),

 * or that doesn't cross some boundary (a DMA counter restriction) --

 * or all of the above.  vmem_xalloc() allows the client to specify any

 * or all of these constraints.

 *

 * 1.7 The Vmem Quantum

 * --------------------

 * Every arena has a notion of 'quantum', specified at vmem_create() time,

 * that defines the arena's minimum unit of currency.  Most commonly the

 * quantum is either 1 or PAGESIZE, but any power of 2 is legal.

 * All vmem allocations are guaranteed to be quantum-aligned.

 *

 * 1.8 Quantum Caching

 * -------------------

 * A vmem arena may be so hot (frequently used) that the scalability of vmem

 * allocation is a significant concern.  We address this by allowing the most

 * common allocation sizes to be serviced by the kernel memory allocator,

 * which provides low-latency per-cpu caching.  The qcache_max argument to

 * vmem_create() specifies the largest allocation size to cache.

 *

 * 1.9 Relationship to Kernel Memory Allocator

 * -------------------------------------------

 * Every kmem cache has a vmem arena as its slab supplier.  The kernel memory

 * allocator uses vmem_alloc() and vmem_free() to create and destroy slabs.

 *

 *

 * 2. Implementation

 * -----------------

 *

 * 2.1 Segment lists and markers

 * -----------------------------

 * The segment structure (vmem_seg_t) contains two doubly-linked lists.

 *

 * The arena list (vs_anext/vs_aprev) links all segments in the arena.

 * In addition to the allocated and free segments, the arena contains

 * special marker segments at span boundaries.  Span markers simplify

 * coalescing and importing logic by making it easy to tell both when

 * we're at a span boundary (so we don't coalesce across it), and when

 * a span is completely free (its neighbors will both be span markers).

 *

 * Imported spans will have vs_import set.

 *

 * The next-of-kin list (vs_knext/vs_kprev) links segments of the same type:

 * (1) for allocated segments, vs_knext is the hash chain linkage;

 * (2) for free segments, vs_knext is the freelist linkage;

 * (3) for span marker segments, vs_knext is the next span marker.

 *

 * 2.2 Allocation hashing

 * ----------------------

 * We maintain a hash table of all allocated segments, hashed by address.

 * This allows vmem_free() to discover the target segment in constant time.

 * vmem_update() periodically resizes hash tables to keep hash chains short.

 *

 * 2.3 Freelist management

 * -----------------------

 * We maintain power-of-2 freelists for free segments, i.e. free segments

 * of size >= 2^n reside in vmp->vm_freelist[n].  To ensure constant-time

 * allocation, vmem_xalloc() looks not in the first freelist that *might*

 * satisfy the allocation, but in the first freelist that *definitely*

 * satisfies the allocation (unless VM_BESTFIT is specified, or all larger

 * freelists are empty).  For example, a 1000-byte allocation will be

 * satisfied not from the 512..1023-byte freelist, whose members *might*

 * contains a 1000-byte segment, but from a 1024-byte or larger freelist,

 * the first member of which will *definitely* satisfy the allocation.

 * This ensures that vmem_xalloc() works in constant time.

 *

 * We maintain a bit map to determine quickly which freelists are non-empty.

 * vmp->vm_freemap & (1 << n) is non-zero iff vmp->vm_freelist[n] is non-empty.

 *

 * The different freelists are linked together into one large freelist,

 * with the freelist heads serving as markers.  Freelist markers simplify

 * the maintenance of vm_freemap by making it easy to tell when we're taking

 * the last member of a freelist (both of its neighbors will be markers).

 *

 * 2.4 Vmem Locking

 * ----------------

 * For simplicity, all arena state is protected by a per-arena lock.

 * For very hot arenas, use quantum caching for scalability.

 *

 * 2.5 Vmem Population

 * -------------------

 * Any internal vmem routine that might need to allocate new segment

 * structures must prepare in advance by calling vmem_populate(), which

 * will preallocate enough vmem_seg_t's to get is through the entire

 * operation without dropping the arena lock.

 *

 * 2.6 Auditing

 * ------------

 * If KMF_AUDIT is set in kmem_flags, we audit vmem allocations as well.

 * Since virtual addresses cannot be scribbled on, there is no equivalent

 * in vmem to redzone checking, deadbeef, or other kmem debugging features.

 * Moreover, we do not audit frees because segment coalescing destroys the

 * association between an address and its segment structure.  Auditing is

 * thus intended primarily to keep track of who's consuming the arena.

 * Debugging support could certainly be extended in the future if it proves

 * necessary, but we do so much live checking via the allocation hash table

 * that even non-DEBUG systems get quite a bit of sanity checking already.

 */

#include <sys/vmem_impl.h>

#include <sys/kmem.h>

#include <sys/kstat.h>

#include <sys/param.h>

#include <sys/systm.h>

#include <sys/atomic.h>

#include <sys/bitmap.h>

#include <sys/sysmacros.h>

#include <sys/cmn_err.h>

#include <sys/debug.h>

#include <sys/panic.h>

#define	VMEM_INITIAL		10	/* early vmem arenas */

#define	VMEM_SEG_INITIAL	200	/* early segments */

/*

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

 */

#define	VMEM_SEGS_PER_SPAN_CREATE	2

/*

 * 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

#define	VMEM_SEGS_PER_LEFT_ALLOC	1

#define	VMEM_SEGS_PER_RIGHT_ALLOC	1

#define	VMEM_SEGS_PER_MIDDLE_ALLOC	2

/*

 * 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		\

	(VMEM_SEGS_PER_SPAN_CREATE + VMEM_SEGS_PER_MIDDLE_ALLOC)

/*

 * 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):

 *

 * (In order to lower the fragmentation in the heap_arena, we specify a

 * minimum import size for the vmem_metadata_arena which is the same size

 * as the kmem_va quantum cache allocations.  This causes the worst-case

 * allocation from the vmem_metadata_arena to be 3 segments.)

 *

 * vmem_alloc(vmem_seg_arena)		-> 2 segs (span create + exact alloc)

 *  segkmem_alloc(vmem_metadata_arena)

 *   vmem_alloc(vmem_metadata_arena)	-> 3 segs (span create + left alloc)

 *    vmem_alloc(heap_arena)		-> 1 seg (left alloc)

 *   page_create()

 *   hat_memload()

 *    kmem_cache_alloc()

 *     kmem_slab_create()

 *	vmem_alloc(hat_memload_arena)	-> 2 segs (span create + exact alloc)

 *	 segkmem_alloc(heap_arena)

 *	  vmem_alloc(heap_arena)	-> 1 seg (left alloc)

 *	  page_create()

 *	  hat_memload()		-> (hat layer won't recurse further)

 *

 * The worst-case consumption for each arena is 3 segment structures.

 * Of course, a 3-seg reserve could easily be blown by multiple threads.

 * Therefore, we serialize all allocations from vmem_seg_arena (which is OK

 * because they're rare).  We cannot allow a non-blocking allocation to get

 * tied up behind a blocking allocation, however, so we use separate locks

 * for VM_SLEEP and VM_NOSLEEP allocations.  In addition, if the system is

 * panicking then we must keep enough resources for panic_thread to do its

 * work.  Thus we have at most three threads trying to allocate from

 * vmem_seg_arena, and each thread consumes at most three segment structures,

 * so we must maintain a 9-seg reserve.

 */

#define	VMEM_POPULATE_RESERVE	9

/*

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

 */

#define	VMEM_MINFREE	(VMEM_POPULATE_RESERVE + VMEM_SEGS_PER_ALLOC_MAX)

static vmem_t vmem0[VMEM_INITIAL];

static vmem_t *vmem_populator[VMEM_INITIAL];

static uint32_t vmem_id;

static uint32_t vmem_populators;

static vmem_seg_t vmem_seg0[VMEM_SEG_INITIAL];

static vmem_seg_t *vmem_segfree;

static kmutex_t vmem_list_lock;

static kmutex_t vmem_segfree_lock;

static kmutex_t vmem_sleep_lock;

static kmutex_t vmem_nosleep_lock;

static kmutex_t vmem_panic_lock;

static vmem_t *vmem_list;

static vmem_t *vmem_metadata_arena;

static vmem_t *vmem_seg_arena;

static vmem_t *vmem_hash_arena;

static vmem_t *vmem_vmem_arena;

static long vmem_update_interval = 15;	/* vmem_update() every 15 seconds */

uint32_t vmem_mtbf;		/* mean time between failures [default: off] */

size_t vmem_seg_size = sizeof (vmem_seg_t);

static vmem_kstat_t vmem_kstat_template = {

	{ "mem_inuse",		KSTAT_DATA_UINT64 },

	{ "mem_import",		KSTAT_DATA_UINT64 },

	{ "mem_total",		KSTAT_DATA_UINT64 },

	{ "vmem_source",	KSTAT_DATA_UINT32 },

	{ "alloc",		KSTAT_DATA_UINT64 },

	{ "free",		KSTAT_DATA_UINT64 },

	{ "wait",		KSTAT_DATA_UINT64 },

	{ "fail",		KSTAT_DATA_UINT64 },

	{ "lookup",		KSTAT_DATA_UINT64 },

	{ "search",		KSTAT_DATA_UINT64 },

	{ "populate_wait",	KSTAT_DATA_UINT64 },

	{ "populate_fail",	KSTAT_DATA_UINT64 },

	{ "contains",		KSTAT_DATA_UINT64 },

	{ "contains_search",	KSTAT_DATA_UINT64 },

};

/*

 * Insert/delete from arena list (type 'a') or next-of-kin list (type 'k').

 */

#define	VMEM_INSERT(vprev, vsp, type)					\

{									\

	vmem_seg_t *vnext = (vprev)->vs_##type##next;			\

	(vsp)->vs_##type##next = (vnext);				\

	(vsp)->vs_##type##prev = (vprev);				\

	(vprev)->vs_##type##next = (vsp);				\

	(vnext)->vs_##type##prev = (vsp);				\

}

#define	VMEM_DELETE(vsp, type)						\

{									\

	vmem_seg_t *vprev = (vsp)->vs_##type##prev;			\

	vmem_seg_t *vnext = (vsp)->vs_##type##next;			\

	(vprev)->vs_##type##next = (vnext);				\

	(vnext)->vs_##type##prev = (vprev);				\

}

/*

 * Get a vmem_seg_t from the global segfree list.

 */

static vmem_seg_t *

vmem_getseg_global(void)

{

	vmem_seg_t *vsp;

	mutex_enter(&vmem_segfree_lock);

	if ((vsp = vmem_segfree) != NULL)

		vmem_segfree = vsp->vs_knext;

	mutex_exit(&vmem_segfree_lock);

	return (vsp);

}

/*

 * Put a vmem_seg_t on the global segfree list.

 */

static void

vmem_putseg_global(vmem_seg_t *vsp)

{

	mutex_enter(&vmem_segfree_lock);

	vsp->vs_knext = vmem_segfree;

	vmem_segfree = vsp;

	mutex_exit(&vmem_segfree_lock);

}

/*

 * Get a vmem_seg_t from vmp's segfree list.

 */

static vmem_seg_t *

vmem_getseg(vmem_t *vmp)

{

	vmem_seg_t *vsp;

	ASSERT(vmp->vm_nsegfree > 0);

	vsp = vmp->vm_segfree;

	vmp->vm_segfree = vsp->vs_knext;

	vmp->vm_nsegfree--;

	return (vsp);

}

/*

 * Put a vmem_seg_t on vmp's segfree list.

 */

static void

vmem_putseg(vmem_t *vmp, vmem_seg_t *vsp)

{

	vsp->vs_knext = vmp->vm_segfree;

	vmp->vm_segfree = vsp;

	vmp->vm_nsegfree++;

}

/*

 * Add vsp to the appropriate freelist.

 */

static void

vmem_freelist_insert(vmem_t *vmp, vmem_seg_t *vsp)

{

	vmem_seg_t *vprev;

	ASSERT(*VMEM_HASH(vmp, vsp->vs_start) != vsp);

	vprev = (vmem_seg_t *)&vmp->vm_freelist[highbit(VS_SIZE(vsp)) - 1];

	vsp->vs_type = VMEM_FREE;

	vmp->vm_freemap |= VS_SIZE(vprev);

	VMEM_INSERT(vprev, vsp, k);

	cv_broadcast(&vmp->vm_cv);

}

/*

 * Take vsp from the freelist.

 */

static void

vmem_freelist_delete(vmem_t *vmp, vmem_seg_t *vsp)

{

	ASSERT(*VMEM_HASH(vmp, vsp->vs_start) != vsp);

	ASSERT(vsp->vs_type == VMEM_FREE);

	if (vsp->vs_knext->vs_start == 0 && vsp->vs_kprev->vs_start == 0) {

		/*

		 * The segments on both sides of 'vsp' are freelist heads,

		 * so taking vsp leaves the freelist at vsp->vs_kprev empty.

		 */

		ASSERT(vmp->vm_freemap & VS_SIZE(vsp->vs_kprev));

		vmp->vm_freemap ^= VS_SIZE(vsp->vs_kprev);

	}

	VMEM_DELETE(vsp, k);

}

/*

 * Add vsp to the allocated-segment hash table and update kstats.

 */

static void

vmem_hash_insert(vmem_t *vmp, vmem_seg_t *vsp)

{

	vmem_seg_t **bucket;

	vsp->vs_type = VMEM_ALLOC;

	bucket = VMEM_HASH(vmp, vsp->vs_start);

	vsp->vs_knext = *bucket;

	*bucket = vsp;

	if (vmem_seg_size == sizeof (vmem_seg_t)) {

		vsp->vs_depth = (uint8_t)getpcstack(vsp->vs_stack,

		    VMEM_STACK_DEPTH);

		vsp->vs_thread = curthread;

		vsp->vs_timestamp = gethrtime();

	} else {

		vsp->vs_depth = 0;

	}

	vmp->vm_kstat.vk_alloc.value.ui64++;

	vmp->vm_kstat.vk_mem_inuse.value.ui64 += VS_SIZE(vsp);

}

/*

 * Remove vsp from the allocated-segment hash table and update kstats.

 */

static vmem_seg_t *

vmem_hash_delete(vmem_t *vmp, uintptr_t addr, size_t size)

{

	vmem_seg_t *vsp, **prev_vspp;

	prev_vspp = VMEM_HASH(vmp, addr);

	while ((vsp = *prev_vspp) != NULL) {

		if (vsp->vs_start == addr) {

			*prev_vspp = vsp->vs_knext;

			break;

		}

		vmp->vm_kstat.vk_lookup.value.ui64++;

		prev_vspp = &vsp->vs_knext;

	}

	if (vsp == NULL)

		panic("vmem_hash_delete(%p, %lx, %lu): bad free",

		    vmp, addr, size);

	if (VS_SIZE(vsp) != size)

		panic("vmem_hash_delete(%p, %lx, %lu): wrong size (expect %lu)",

		    vmp, addr, size, VS_SIZE(vsp));

	vmp->vm_kstat.vk_free.value.ui64++;

	vmp->vm_kstat.vk_mem_inuse.value.ui64 -= size;

	return (vsp);

}

/*

 * Create a segment spanning the range [start, end) and add it to the arena.

 */

static vmem_seg_t *

vmem_seg_create(vmem_t *vmp, vmem_seg_t *vprev, uintptr_t start, uintptr_t end)

{

	vmem_seg_t *newseg = vmem_getseg(vmp);

	newseg->vs_start = start;

	newseg->vs_end = end;

	newseg->vs_type = 0;

	newseg->vs_import = 0;