path: root/sys/uvm/uvm_amap.c

/*	$OpenBSD: uvm_amap.c,v 1.92 2023/04/11 00:45:09 jsg Exp $	*/
/*	$NetBSD: uvm_amap.c,v 1.27 2000/11/25 06:27:59 chs Exp $	*/

/*
 * Copyright (c) 1997 Charles D. Cranor and Washington University.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/*
 * uvm_amap.c: amap operations
 *
 * this file contains functions that perform operations on amaps.  see
 * uvm_amap.h for a brief explanation of the role of amaps in uvm.
 */

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/malloc.h>
#include <sys/kernel.h>
#include <sys/pool.h>
#include <sys/atomic.h>

#include <uvm/uvm.h>
#include <uvm/uvm_swap.h>

/*
 * pools for allocation of vm_amap structures.  note that in order to
 * avoid an endless loop, the amap pool's allocator cannot allocate
 * memory from an amap (it currently goes through the kernel uobj, so
 * we are ok).
 */

struct pool uvm_amap_pool;
struct pool uvm_small_amap_pool[UVM_AMAP_CHUNK];
struct pool uvm_amap_chunk_pool;

LIST_HEAD(, vm_amap) amap_list;
struct rwlock amap_list_lock = RWLOCK_INITIALIZER("amaplstlk");
#define amap_lock_list()	rw_enter_write(&amap_list_lock)
#define amap_unlock_list()	rw_exit_write(&amap_list_lock)

static char amap_small_pool_names[UVM_AMAP_CHUNK][9];

/*
 * local functions
 */

static struct vm_amap *amap_alloc1(int, int, int);
static inline void amap_list_insert(struct vm_amap *);
static inline void amap_list_remove(struct vm_amap *);   

struct vm_amap_chunk *amap_chunk_get(struct vm_amap *, int, int, int);
void amap_chunk_free(struct vm_amap *, struct vm_amap_chunk *);

/*
 * if we enable PPREF, then we have a couple of extra functions that
 * we need to prototype here...
 */

#ifdef UVM_AMAP_PPREF

#define PPREF_NONE ((int *) -1)	/* not using ppref */

void	amap_pp_adjref(struct vm_amap *, int, vsize_t, int);
void	amap_pp_establish(struct vm_amap *);
void	amap_wiperange_chunk(struct vm_amap *, struct vm_amap_chunk *, int,
	    int);
void	amap_wiperange(struct vm_amap *, int, int);

#endif	/* UVM_AMAP_PPREF */

static inline void
amap_list_insert(struct vm_amap *amap)
{
	amap_lock_list();
	LIST_INSERT_HEAD(&amap_list, amap, am_list);
	amap_unlock_list();
}

static inline void
amap_list_remove(struct vm_amap *amap)
{
	amap_lock_list();
	LIST_REMOVE(amap, am_list);
	amap_unlock_list();
}

/*
 * amap_chunk_get: lookup a chunk for slot. if create is non-zero,
 * the chunk is created if it does not yet exist.
 *
 * => returns the chunk on success or NULL on error
 */
struct vm_amap_chunk *
amap_chunk_get(struct vm_amap *amap, int slot, int create, int waitf)
{
	int bucket = UVM_AMAP_BUCKET(amap, slot);
	int baseslot = AMAP_BASE_SLOT(slot);
	int n;
	struct vm_amap_chunk *chunk, *newchunk, *pchunk = NULL;

	if (UVM_AMAP_SMALL(amap))
		return &amap->am_small;

	for (chunk = amap->am_buckets[bucket]; chunk != NULL;
	    chunk = TAILQ_NEXT(chunk, ac_list)) {
		if (UVM_AMAP_BUCKET(amap, chunk->ac_baseslot) != bucket)
			break;
		if (chunk->ac_baseslot == baseslot)
			return chunk;
		pchunk = chunk;
	}
	if (!create)
		return NULL;

	if (amap->am_nslot - baseslot >= UVM_AMAP_CHUNK)
		n = UVM_AMAP_CHUNK;
	else
		n = amap->am_nslot - baseslot;

	newchunk = pool_get(&uvm_amap_chunk_pool, waitf | PR_ZERO);
	if (newchunk == NULL)
		return NULL;

	if (pchunk == NULL) {
		TAILQ_INSERT_TAIL(&amap->am_chunks, newchunk, ac_list);
		KASSERT(amap->am_buckets[bucket] == NULL);
		amap->am_buckets[bucket] = newchunk;
	} else
		TAILQ_INSERT_AFTER(&amap->am_chunks, pchunk, newchunk,
		    ac_list);

	amap->am_ncused++;
	newchunk->ac_baseslot = baseslot;
	newchunk->ac_nslot = n;
	return newchunk;
}

void
amap_chunk_free(struct vm_amap *amap, struct vm_amap_chunk *chunk)
{
	int bucket = UVM_AMAP_BUCKET(amap, chunk->ac_baseslot);
	struct vm_amap_chunk *nchunk;

	if (UVM_AMAP_SMALL(amap))
		return;

	nchunk = TAILQ_NEXT(chunk, ac_list);
	TAILQ_REMOVE(&amap->am_chunks, chunk, ac_list);
	if (amap->am_buckets[bucket] == chunk) {
		if (nchunk != NULL &&
		    UVM_AMAP_BUCKET(amap, nchunk->ac_baseslot) == bucket)
			amap->am_buckets[bucket] = nchunk;
		else
			amap->am_buckets[bucket] = NULL;

	}
	pool_put(&uvm_amap_chunk_pool, chunk);
	amap->am_ncused--;
}

#ifdef UVM_AMAP_PPREF
/*
 * what is ppref?   ppref is an _optional_ amap feature which is used
 * to keep track of reference counts on a per-page basis.  it is enabled
 * when UVM_AMAP_PPREF is defined.
 *
 * when enabled, an array of ints is allocated for the pprefs.  this
 * array is allocated only when a partial reference is added to the
 * map (either by unmapping part of the amap, or gaining a reference
 * to only a part of an amap).  if the allocation of the array fails
 * (M_NOWAIT), then we set the array pointer to PPREF_NONE to indicate
 * that we tried to do ppref's but couldn't alloc the array so just
 * give up (after all, this is an optional feature!).
 *
 * the array is divided into page sized "chunks."   for chunks of length 1,
 * the chunk reference count plus one is stored in that chunk's slot.
 * for chunks of length > 1 the first slot contains (the reference count
 * plus one) * -1.    [the negative value indicates that the length is
 * greater than one.]   the second slot of the chunk contains the length
 * of the chunk.   here is an example:
 *
 * actual REFS:  2  2  2  2  3  1  1  0  0  0  4  4  0  1  1  1
 *       ppref: -3  4  x  x  4 -2  2 -1  3  x -5  2  1 -2  3  x
 *              <----------><-><----><-------><----><-><------->
 * (x = don't care)
 *
 * this allows us to allow one int to contain the ref count for the whole
 * chunk.    note that the "plus one" part is needed because a reference
 * count of zero is neither positive or negative (need a way to tell
 * if we've got one zero or a bunch of them).
 *
 * here are some in-line functions to help us.
 */

/*
 * pp_getreflen: get the reference and length for a specific offset
 *
 * => ppref's amap must be locked
 */
static inline void
pp_getreflen(int *ppref, int offset, int *refp, int *lenp)
{

	if (ppref[offset] > 0) {		/* chunk size must be 1 */
		*refp = ppref[offset] - 1;	/* don't forget to adjust */
		*lenp = 1;
	} else {
		*refp = (ppref[offset] * -1) - 1;
		*lenp = ppref[offset+1];
	}
}

/*
 * pp_setreflen: set the reference and length for a specific offset
 *
 * => ppref's amap must be locked
 */
static inline void
pp_setreflen(int *ppref, int offset, int ref, int len)
{
	if (len == 1) {
		ppref[offset] = ref + 1;
	} else {
		ppref[offset] = (ref + 1) * -1;
		ppref[offset+1] = len;
	}
}
#endif /* UVM_AMAP_PPREF */

/*
 * amap_init: called at boot time to init global amap data structures
 */

void
amap_init(void)
{
	int i;
	size_t size;

	/* Initialize the vm_amap pool. */
	pool_init(&uvm_amap_pool, sizeof(struct vm_amap),
	    0, IPL_MPFLOOR, PR_WAITOK, "amappl", NULL);
	pool_sethiwat(&uvm_amap_pool, 4096);

	/* initialize small amap pools */
	for (i = 0; i < nitems(uvm_small_amap_pool); i++) {
		snprintf(amap_small_pool_names[i],
		    sizeof(amap_small_pool_names[0]), "amappl%d", i + 1);
		size = offsetof(struct vm_amap, am_small.ac_anon) +
		    (i + 1) * sizeof(struct vm_anon *);
		pool_init(&uvm_small_amap_pool[i], size, 0, IPL_MPFLOOR,
		    PR_WAITOK, amap_small_pool_names[i], NULL);
	}

	pool_init(&uvm_amap_chunk_pool, sizeof(struct vm_amap_chunk) +
	    UVM_AMAP_CHUNK * sizeof(struct vm_anon *),
	    0, IPL_MPFLOOR, PR_WAITOK, "amapchunkpl", NULL);
	pool_sethiwat(&uvm_amap_chunk_pool, 4096);
}

/*
 * amap_alloc1: allocate an amap, but do not initialise the overlay.
 *
 * => Note: lock is not set.
 */
static inline struct vm_amap *
amap_alloc1(int slots, int waitf, int lazyalloc)
{
	struct vm_amap *amap;
	struct vm_amap_chunk *chunk, *tmp;
	int chunks, log_chunks, chunkperbucket = 1, hashshift = 0;
	int buckets, i, n;
	int pwaitf = (waitf & M_WAITOK) ? PR_WAITOK : PR_NOWAIT;

	KASSERT(slots > 0);

	/*
	 * Cast to unsigned so that rounding up cannot cause integer overflow
	 * if slots is large.
	 */
	chunks = roundup((unsigned int)slots, UVM_AMAP_CHUNK) / UVM_AMAP_CHUNK;

	if (lazyalloc) {
		/*
		 * Basically, the amap is a hash map where the number of
		 * buckets is fixed. We select the number of buckets using the
		 * following strategy:
		 *
		 * 1. The maximal number of entries to search in a bucket upon
		 * a collision should be less than or equal to
		 * log2(slots / UVM_AMAP_CHUNK). This is the worst-case number
		 * of lookups we would have if we could chunk the amap. The
		 * log2(n) comes from the fact that amaps are chunked by
		 * splitting up their vm_map_entries and organizing those
		 * in a binary search tree.
		 *
		 * 2. The maximal number of entries in a bucket must be a
		 * power of two.
		 *
		 * The maximal number of entries per bucket is used to hash
		 * a slot to a bucket.
		 *
		 * In the future, this strategy could be refined to make it
		 * even harder/impossible that the total amount of KVA needed
		 * for the hash buckets of all amaps to exceed the maximal
		 * amount of KVA memory reserved for amaps.
		 */
		for (log_chunks = 1; (chunks >> log_chunks) > 0; log_chunks++)
			continue;

		chunkperbucket = 1 << hashshift;
		while (chunkperbucket + 1 < log_chunks) {
			hashshift++;
			chunkperbucket = 1 << hashshift;
		}
	}

	if (slots > UVM_AMAP_CHUNK)
		amap = pool_get(&uvm_amap_pool, pwaitf);
	else
		amap = pool_get(&uvm_small_amap_pool[slots - 1],
		    pwaitf | PR_ZERO);
	if (amap == NULL)
		return NULL;

	amap->am_lock = NULL;
	amap->am_ref = 1;
	amap->am_flags = 0;
#ifdef UVM_AMAP_PPREF
	amap->am_ppref = NULL;
#endif
	amap->am_nslot = slots;
	amap->am_nused = 0;

	if (UVM_AMAP_SMALL(amap)) {
		amap->am_small.ac_nslot = slots;
		return amap;
	}

	amap->am_ncused = 0;
	TAILQ_INIT(&amap->am_chunks);
	amap->am_hashshift = hashshift;
	amap->am_buckets = NULL;

	buckets = howmany(chunks, chunkperbucket);
	amap->am_buckets = mallocarray(buckets, sizeof(*amap->am_buckets),
	    M_UVMAMAP, waitf | (lazyalloc ? M_ZERO : 0));
	if (amap->am_buckets == NULL)
		goto fail1;
	amap->am_nbuckets = buckets;

	if (!lazyalloc) {
		for (i = 0; i < buckets; i++) {
			if (i == buckets - 1) {
				n = slots % UVM_AMAP_CHUNK;
				if (n == 0)
					n = UVM_AMAP_CHUNK;
			} else
				n = UVM_AMAP_CHUNK;

			chunk = pool_get(&uvm_amap_chunk_pool,
			    PR_ZERO | pwaitf);
			if (chunk == NULL)
				goto fail1;

			amap->am_buckets[i] = chunk;
			amap->am_ncused++;
			chunk->ac_baseslot = i * UVM_AMAP_CHUNK;
			chunk->ac_nslot = n;
			TAILQ_INSERT_TAIL(&amap->am_chunks, chunk, ac_list);
		}
	}

	return amap;

fail1:
	free(amap->am_buckets, M_UVMAMAP, buckets * sizeof(*amap->am_buckets));
	TAILQ_FOREACH_SAFE(chunk, &amap->am_chunks, ac_list, tmp)
		pool_put(&uvm_amap_chunk_pool, chunk);
	pool_put(&uvm_amap_pool, amap);
	return NULL;
}

static void
amap_lock_alloc(struct vm_amap *amap)
{
	rw_obj_alloc(&amap->am_lock, "amaplk");
}

/*
 * amap_alloc: allocate an amap to manage "sz" bytes of anonymous VM
 *
 * => caller should ensure sz is a multiple of PAGE_SIZE
 * => reference count to new amap is set to one
 * => new amap is returned unlocked
 */
struct vm_amap *
amap_alloc(vaddr_t sz, int waitf, int lazyalloc)
{
	struct vm_amap *amap;
	size_t slots;

	AMAP_B2SLOT(slots, sz);		/* load slots */
	if (slots > INT_MAX)
		return NULL;

	amap = amap_alloc1(slots, waitf, lazyalloc);
	if (amap != NULL) {
		amap_lock_alloc(amap);
		amap_list_insert(amap);
	}

	return amap;
}


/*
 * amap_free: free an amap
 *
 * => the amap must be unlocked
 * => the amap should have a zero reference count and be empty
 */
void
amap_free(struct vm_amap *amap)
{
	struct vm_amap_chunk *chunk, *tmp;

	KASSERT(amap->am_ref == 0 && amap->am_nused == 0);
	KASSERT((amap->am_flags & AMAP_SWAPOFF) == 0);

	if (amap->am_lock != NULL) {
		KASSERT(amap->am_lock == NULL || !rw_write_held(amap->am_lock));
		rw_obj_free(amap->am_lock);
	}

#ifdef UVM_AMAP_PPREF
	if (amap->am_ppref && amap->am_ppref != PPREF_NONE)
		free(amap->am_ppref, M_UVMAMAP, amap->am_nslot * sizeof(int));
#endif

	if (UVM_AMAP_SMALL(amap))
		pool_put(&uvm_small_amap_pool[amap->am_nslot - 1], amap);
	else {
		TAILQ_FOREACH_SAFE(chunk, &amap->am_chunks, ac_list, tmp)
		    pool_put(&uvm_amap_chunk_pool, chunk);
		free(amap->am_buckets, M_UVMAMAP,
		    amap->am_nbuckets * sizeof(*amap->am_buckets));
		pool_put(&uvm_amap_pool, amap);
	}
}

/*
 * amap_wipeout: wipeout all anon's in an amap; then free the amap!
 *
 * => Called from amap_unref(), when reference count drops to zero.
 * => amap must be locked.
 */
void
amap_wipeout(struct vm_amap *amap)
{
	int slot;
	struct vm_anon *anon;
	struct vm_amap_chunk *chunk;
	struct pglist pgl;

	KASSERT(rw_write_held(amap->am_lock));
	KASSERT(amap->am_ref == 0);

	if (__predict_false((amap->am_flags & AMAP_SWAPOFF) != 0)) {
		/*
		 * Note: amap_swap_off() will call us again.
		 */
		amap_unlock(amap);
		return;
	}

	TAILQ_INIT(&pgl);
	amap_list_remove(amap);

	AMAP_CHUNK_FOREACH(chunk, amap) {
		int i, refs, map = chunk->ac_usedmap;

		for (i = ffs(map); i != 0; i = ffs(map)) {
			slot = i - 1;
			map ^= 1 << slot;
			anon = chunk->ac_anon[slot];

			if (anon == NULL || anon->an_ref == 0)
				panic("amap_wipeout: corrupt amap");
			KASSERT(anon->an_lock == amap->am_lock);

			/*
			 * Drop the reference.
			 */
			refs = --anon->an_ref;
			if (refs == 0) {
				uvm_anfree_list(anon, &pgl);
			}
		}
	}
	/* free the pages */
	uvm_pglistfree(&pgl);

	/*
	 * Finally, destroy the amap.
	 */
	amap->am_ref = 0;	/* ... was one */
	amap->am_nused = 0;
	amap_unlock(amap);
	amap_free(amap);
}

/*
 * amap_copy: ensure that a map entry's "needs_copy" flag is false
 *	by copying the amap if necessary.
 *
 * => an entry with a null amap pointer will get a new (blank) one.
 * => the map that the map entry belongs to must be locked by caller.
 * => the amap currently attached to "entry" (if any) must be unlocked.
 * => if canchunk is true, then we may clip the entry into a chunk
 * => "startva" and "endva" are used only if canchunk is true.  they are
 *     used to limit chunking (e.g. if you have a large space that you
 *     know you are going to need to allocate amaps for, there is no point
 *     in allowing that to be chunked)
 */

void
amap_copy(struct vm_map *map, struct vm_map_entry *entry, int waitf,
    boolean_t canchunk, vaddr_t startva, vaddr_t endva)
{
	struct vm_amap *amap, *srcamap;
	int slots, lcv, lazyalloc = 0;
	vaddr_t chunksize;
	int i, j, k, n, srcslot;
	struct vm_amap_chunk *chunk = NULL, *srcchunk = NULL;
	struct vm_anon *anon;

	KASSERT(map != kernel_map);		/* we use sleeping locks */

	/*
	 * Is there an amap to copy?  If not, create one.
	 */
	if (entry->aref.ar_amap == NULL) {
		/*
		 * Check to see if we have a large amap that we can
		 * chunk.  We align startva/endva to chunk-sized
		 * boundaries and then clip to them.
		 *
		 * If we cannot chunk the amap, allocate it in a way
		 * that makes it grow or shrink dynamically with
		 * the number of slots.
		 */
		if (atop(entry->end - entry->start) >= UVM_AMAP_LARGE) {
			if (canchunk) {
				/* convert slots to bytes */
				chunksize = UVM_AMAP_CHUNK << PAGE_SHIFT;
				startva = (startva / chunksize) * chunksize;
				endva = roundup(endva, chunksize);
				UVM_MAP_CLIP_START(map, entry, startva);
				/* watch out for endva wrap-around! */
				if (endva >= startva)
					UVM_MAP_CLIP_END(map, entry, endva);
			} else
				lazyalloc = 1;
		}

		entry->aref.ar_pageoff = 0;
		entry->aref.ar_amap = amap_alloc(entry->end - entry->start,
		    waitf, lazyalloc);
		if (entry->aref.ar_amap != NULL)
			entry->etype &= ~UVM_ET_NEEDSCOPY;
		return;
	}

	/*
	 * First check and see if we are the only map entry referencing
	 * he amap we currently have.  If so, then just take it over instead
	 * of copying it.  Note that we are reading am_ref without lock held
	 * as the value can only be one if we have the only reference
	 * to the amap (via our locked map).  If the value is greater than
	 * one, then allocate amap and re-check the value.
	 */
	if (entry->aref.ar_amap->am_ref == 1) {
		entry->etype &= ~UVM_ET_NEEDSCOPY;
		return;
	}

	/*
	 * Allocate a new amap (note: not initialised, etc).
	 */
	AMAP_B2SLOT(slots, entry->end - entry->start);
	if (!UVM_AMAP_SMALL(entry->aref.ar_amap) &&
	    entry->aref.ar_amap->am_hashshift != 0)
		lazyalloc = 1;
	amap = amap_alloc1(slots, waitf, lazyalloc);
	if (amap == NULL)
		return;
	srcamap = entry->aref.ar_amap;

	/*
	 * Make the new amap share the source amap's lock, and then lock
	 * both.
	 */
	amap->am_lock = srcamap->am_lock;
	rw_obj_hold(amap->am_lock);

	amap_lock(srcamap);

	/*
	 * Re-check the reference count with the lock held.  If it has
	 * dropped to one - we can take over the existing map.
	 */
	if (srcamap->am_ref == 1) {
		/* Just take over the existing amap. */
		entry->etype &= ~UVM_ET_NEEDSCOPY;
		amap_unlock(srcamap);
		/* Destroy the new (unused) amap. */
		amap->am_ref--;
		amap_free(amap);
		return;
	}

	/*
	 * Copy the slots.
	 */
	for (lcv = 0; lcv < slots; lcv += n) {
		srcslot = entry->aref.ar_pageoff + lcv;
		i = UVM_AMAP_SLOTIDX(lcv);
		j = UVM_AMAP_SLOTIDX(srcslot);
		n = UVM_AMAP_CHUNK;
		if (i > j)
			n -= i;
		else
			n -= j;
		if (lcv + n > slots)
			n = slots - lcv;

		srcchunk = amap_chunk_get(srcamap, srcslot, 0, PR_NOWAIT);
		if (srcchunk == NULL)
			continue;

		chunk = amap_chunk_get(amap, lcv, 1, PR_NOWAIT);
		if (chunk == NULL) {
			/* amap_wipeout() releases the lock. */
			amap->am_ref = 0;
			amap_wipeout(amap);
			return;
		}

		for (k = 0; k < n; i++, j++, k++) {
			chunk->ac_anon[i] = anon = srcchunk->ac_anon[j];
			if (anon == NULL)
				continue;

			KASSERT(anon->an_lock == srcamap->am_lock);
			KASSERT(anon->an_ref > 0);
			chunk->ac_usedmap |= (1 << i);
			anon->an_ref++;
			amap->am_nused++;
		}
	}

	/*
	 * Drop our reference to the old amap (srcamap) and unlock.
	 * Since the reference count on srcamap is greater than one,
	 * (we checked above), it cannot drop to zero while it is locked.
	 */
	srcamap->am_ref--;
	KASSERT(srcamap->am_ref > 0);

	if (srcamap->am_ref == 1 && (srcamap->am_flags & AMAP_SHARED) != 0)
		srcamap->am_flags &= ~AMAP_SHARED;   /* clear shared flag */
#ifdef UVM_AMAP_PPREF
	if (srcamap->am_ppref && srcamap->am_ppref != PPREF_NONE) {
		amap_pp_adjref(srcamap, entry->aref.ar_pageoff, 
		    (entry->end - entry->start) >> PAGE_SHIFT, -1);
	}
#endif

	/*
	 * If we referenced any anons, then share the source amap's lock.
	 * Otherwise, we have nothing in common, so allocate a new one.
	 */
	KASSERT(amap->am_lock == srcamap->am_lock);
	if (amap->am_nused == 0) {
		rw_obj_free(amap->am_lock);
		amap->am_lock = NULL;
	}
	amap_unlock(srcamap);

	if (amap->am_lock == NULL)
		amap_lock_alloc(amap);

	/*
	 * Install new amap.
	 */
	entry->aref.ar_pageoff = 0;
	entry->aref.ar_amap = amap;
	entry->etype &= ~UVM_ET_NEEDSCOPY;

	amap_list_insert(amap);
}

/*
 * amap_cow_now: resolve all copy-on-write faults in an amap now for fork(2)
 *
 *	called during fork(2) when the parent process has a wired map
 *	entry.   in that case we want to avoid write-protecting pages
 *	in the parent's map (e.g. like what you'd do for a COW page)
 *	so we resolve the COW here.
 *
 * => assume parent's entry was wired, thus all pages are resident.
 * => the parent and child vm_map must both be locked.
 * => caller passes child's map/entry in to us
 * => XXXCDC: out of memory should cause fork to fail, but there is
 *	currently no easy way to do this (needs fix)
 */

void
amap_cow_now(struct vm_map *map, struct vm_map_entry *entry)
{
	struct vm_amap *amap = entry->aref.ar_amap;
	int slot;
	struct vm_anon *anon, *nanon;
	struct vm_page *pg, *npg;
	struct vm_amap_chunk *chunk;

	/*
	 * note that if we unlock the amap then we must ReStart the "lcv" for
	 * loop because some other process could reorder the anon's in the
	 * am_anon[] array on us while the lock is dropped.
	 */
ReStart:
	amap_lock(amap);
	AMAP_CHUNK_FOREACH(chunk, amap) {
		int i, map = chunk->ac_usedmap;

		for (i = ffs(map); i != 0; i = ffs(map)) {
			slot = i - 1;
			map ^= 1 << slot;
			anon = chunk->ac_anon[slot];
			pg = anon->an_page;
			KASSERT(anon->an_lock == amap->am_lock);

			/*
			 * The old page must be resident since the parent is
			 * wired.
			 */
			KASSERT(pg != NULL);

			/*
			 * if the anon ref count is one, we are safe (the child
			 * has exclusive access to the page).
			 */
			if (anon->an_ref <= 1)
				continue;

			/*
			 * If the page is busy, then we have to unlock, wait for
			 * it and then restart.
			 */
			if (pg->pg_flags & PG_BUSY) {
				uvm_pagewait(pg, amap->am_lock, "cownow");
				goto ReStart;
			}

			/*
			 * Perform a copy-on-write.
			 * First - get a new anon and a page.
			 */
			nanon = uvm_analloc();
			if (nanon != NULL) {
				/* the new anon will share the amap's lock */
				nanon->an_lock = amap->am_lock;
				npg = uvm_pagealloc(NULL, 0, nanon, 0);
			} else
				npg = NULL;	/* XXX: quiet gcc warning */

			if (nanon == NULL || npg == NULL) {
				/* out of memory */
				amap_unlock(amap);
				if (nanon != NULL) {
					nanon->an_lock = NULL;
					nanon->an_ref--;
					KASSERT(nanon->an_ref == 0);
					uvm_anfree(nanon);
				}
				uvm_wait("cownowpage");
				goto ReStart;
			}

			/*
			 * Copy the data and replace anon with the new one.
			 * Also, setup its lock (share the with amap's lock).
			 */
			uvm_pagecopy(pg, npg);
			anon->an_ref--;
			KASSERT(anon->an_ref > 0);
			chunk->ac_anon[slot] = nanon;

			/*
			 * Drop PG_BUSY on new page.  Since its owner was write
			 * locked all this time - it cannot be PG_RELEASED or
			 * PG_WANTED.
			 */
			atomic_clearbits_int(&npg->pg_flags, PG_BUSY|PG_FAKE);
			UVM_PAGE_OWN(npg, NULL);
			uvm_lock_pageq();
			uvm_pageactivate(npg);
			uvm_unlock_pageq();
		}
	}
	amap_unlock(amap);
}

/*
 * amap_splitref: split a single reference into two separate references
 *
 * => called from uvm_map's clip routines
 * => origref's map should be locked
 * => origref->ar_amap should be unlocked (we will lock)
 */
void
amap_splitref(struct vm_aref *origref, struct vm_aref *splitref, vaddr_t offset)
{
	struct vm_amap *amap = origref->ar_amap;
	int leftslots;

	KASSERT(splitref->ar_amap == amap);
	AMAP_B2SLOT(leftslots, offset);
	if (leftslots == 0)
		panic("amap_splitref: split at zero offset");

	amap_lock(amap);

	if (amap->am_nslot - origref->ar_pageoff - leftslots <= 0)
		panic("amap_splitref: map size check failed");

#ifdef UVM_AMAP_PPREF
	/* Establish ppref before we add a duplicate reference to the amap. */
	if (amap->am_ppref == NULL)
		amap_pp_establish(amap);
#endif

	/* Note: not a share reference. */
	amap->am_ref++;
	splitref->ar_amap = amap;
	splitref->ar_pageoff = origref->ar_pageoff + leftslots;
	amap_unlock(amap);
}

#ifdef UVM_AMAP_PPREF

/*
 * amap_pp_establish: add a ppref array to an amap, if possible.
 *
 * => amap should be locked by caller* => amap should be locked by caller
 */
void
amap_pp_establish(struct vm_amap *amap)
{

	KASSERT(rw_write_held(amap->am_lock));
	amap->am_ppref = mallocarray(amap->am_nslot, sizeof(int),
	    M_UVMAMAP, M_NOWAIT|M_ZERO);

	if (amap->am_ppref == NULL) {
		/* Failure - just do not use ppref. */
		amap->am_ppref = PPREF_NONE;
		return;
	}

	pp_setreflen(amap->am_ppref, 0, amap->am_ref, amap->am_nslot);
}

/*
 * amap_pp_adjref: adjust reference count to a part of an amap using the
 * per-page reference count array.
 *
 * => caller must check that ppref != PPREF_NONE before calling.
 * => map and amap must be locked.
 */
void
amap_pp_adjref(struct vm_amap *amap, int curslot, vsize_t slotlen, int adjval)
{
 	int stopslot, *ppref, lcv, prevlcv;
 	int ref, len, prevref, prevlen;

	KASSERT(rw_write_held(amap->am_lock));

	stopslot = curslot + slotlen;
	ppref = amap->am_ppref;
 	prevlcv = 0;

	/*
	 * Advance to the correct place in the array, fragment if needed.
	 */
	for (lcv = 0 ; lcv < curslot ; lcv += len) {
		pp_getreflen(ppref, lcv, &ref, &len);
		if (lcv + len > curslot) {     /* goes past start? */
			pp_setreflen(ppref, lcv, ref, curslot - lcv);
			pp_setreflen(ppref, curslot, ref, len - (curslot -lcv));
			len = curslot - lcv;   /* new length of entry @ lcv */
		}
		prevlcv = lcv;
	}
	if (lcv != 0)
		pp_getreflen(ppref, prevlcv, &prevref, &prevlen);
	else {
		/*
		 * Ensure that the "prevref == ref" test below always
		 * fails, since we are starting from the beginning of
		 * the ppref array; that is, there is no previous chunk.
		 */
		prevref = -1;
		prevlen = 0;
	}

	/*
	 * Now adjust reference counts in range.  Merge the first
	 * changed entry with the last unchanged entry if possible.
	 */
	if (lcv != curslot)
		panic("amap_pp_adjref: overshot target");

	for (/* lcv already set */; lcv < stopslot ; lcv += len) {
		pp_getreflen(ppref, lcv, &ref, &len);
		if (lcv + len > stopslot) {     /* goes past end? */
			pp_setreflen(ppref, lcv, ref, stopslot - lcv);
			pp_setreflen(ppref, stopslot, ref,
			    len - (stopslot - lcv));
			len = stopslot - lcv;
		}
		ref += adjval;
		if (ref < 0)
			panic("amap_pp_adjref: negative reference count");
		if (lcv == prevlcv + prevlen && ref == prevref) {
			pp_setreflen(ppref, prevlcv, ref, prevlen + len);
		} else {
			pp_setreflen(ppref, lcv, ref, len);
		}
		if (ref == 0)
			amap_wiperange(amap, lcv, len);
	}

}

void
amap_wiperange_chunk(struct vm_amap *amap, struct vm_amap_chunk *chunk,
    int slotoff, int slots)
{
	int curslot, i, map;
	int startbase, endbase;
	struct vm_anon *anon;

	startbase = AMAP_BASE_SLOT(slotoff);
	endbase = AMAP_BASE_SLOT(slotoff + slots - 1);

	map = chunk->ac_usedmap;
	if (startbase == chunk->ac_baseslot)
		map &= ~((1 << (slotoff - startbase)) - 1);
	if (endbase == chunk->ac_baseslot)
		map &= (1 << (slotoff + slots - endbase)) - 1;

	for (i = ffs(map); i != 0; i = ffs(map)) {
		int refs;

		curslot = i - 1;
		map ^= 1 << curslot;
		chunk->ac_usedmap ^= 1 << curslot;
		anon = chunk->ac_anon[curslot];
		KASSERT(anon->an_lock == amap->am_lock);

		/* remove it from the amap */
		chunk->ac_anon[curslot] = NULL;

		amap->am_nused--;

		/* drop anon reference count */
		refs = --anon->an_ref;
		if (refs == 0) {
			uvm_anfree(anon);
		}

		/*
		 * done with this anon, next ...!
		 */

	}	/* end of 'for' loop */
}

/*
 * amap_wiperange: wipe out a range of an amap.
 * Note: different from amap_wipeout because the amap is kept intact.
 *
 * => Both map and amap must be locked by caller.
 */
void
amap_wiperange(struct vm_amap *amap, int slotoff, int slots)
{
	int bucket, startbucket, endbucket;
	struct vm_amap_chunk *chunk, *nchunk;

	KASSERT(rw_write_held(amap->am_lock));

	startbucket = UVM_AMAP_BUCKET(amap, slotoff);
	endbucket = UVM_AMAP_BUCKET(amap, slotoff + slots - 1);

	/*
	 * We can either traverse the amap by am_chunks or by am_buckets.
	 * Determine which way is less expensive.
	 */
	if (UVM_AMAP_SMALL(amap))
		amap_wiperange_chunk(amap, &amap->am_small, slotoff, slots);
	else if (endbucket + 1 - startbucket >= amap->am_ncused) {
		TAILQ_FOREACH_SAFE(chunk, &amap->am_chunks, ac_list, nchunk) {
			if (chunk->ac_baseslot + chunk->ac_nslot <= slotoff)
				continue;
			if (chunk->ac_baseslot >= slotoff + slots)
				continue;

			amap_wiperange_chunk(amap, chunk, slotoff, slots);
			if (chunk->ac_usedmap == 0)
				amap_chunk_free(amap, chunk);
		}
	} else {
		for (bucket = startbucket; bucket <= endbucket; bucket++) {
			for (chunk = amap->am_buckets[bucket]; chunk != NULL;
			    chunk = nchunk) {
				nchunk = TAILQ_NEXT(chunk, ac_list);

				if (UVM_AMAP_BUCKET(amap, chunk->ac_baseslot) !=
				    bucket)
					break;
				if (chunk->ac_baseslot + chunk->ac_nslot <=
				    slotoff)
					continue;
				if (chunk->ac_baseslot >= slotoff + slots)
					continue;

				amap_wiperange_chunk(amap, chunk, slotoff,
				    slots);
				if (chunk->ac_usedmap == 0)
					amap_chunk_free(amap, chunk);
			}
		}
	}
}

#endif

/*
 * amap_swap_off: pagein anonymous pages in amaps and drop swap slots.
 *
 * => note that we don't always traverse all anons.
 *    eg. amaps being wiped out, released anons.
 * => return TRUE if failed.
 */

boolean_t
amap_swap_off(int startslot, int endslot)
{
	struct vm_amap *am;
	struct vm_amap *am_next;
	struct vm_amap marker;
	boolean_t rv = FALSE;

	amap_lock_list();
	for (am = LIST_FIRST(&amap_list); am != NULL && !rv; am = am_next) {
		int i, map;
		struct vm_amap_chunk *chunk;

		amap_lock(am);
		if (am->am_nused == 0) {
			amap_unlock(am);
			am_next = LIST_NEXT(am, am_list);
			continue;
		}

		LIST_INSERT_AFTER(am, &marker, am_list);
		amap_unlock_list();

again:
		AMAP_CHUNK_FOREACH(chunk, am) {
			map = chunk->ac_usedmap;

			for (i = ffs(map); i != 0; i = ffs(map)) {
				int swslot;
				int slot = i - 1;
				struct vm_anon *anon;

				map ^= 1 << slot;
				anon = chunk->ac_anon[slot];

				swslot = anon->an_swslot;
				if (swslot < startslot || endslot <= swslot) {
					continue;
				}

				am->am_flags |= AMAP_SWAPOFF;

				rv = uvm_anon_pagein(am, anon);
				amap_lock(am);

				am->am_flags &= ~AMAP_SWAPOFF;
				if (amap_refs(am) == 0) {
					amap_wipeout(am);
					am = NULL;
					goto nextamap;
				}
				if (rv)
					goto nextamap;
				goto again;
			}
		}
nextamap:
		if (am != NULL)
			amap_unlock(am);
		amap_lock_list();
		am_next = LIST_NEXT(&marker, am_list);
		LIST_REMOVE(&marker, am_list);
	}
	amap_unlock_list();

	return rv;
}

/*
 * amap_lookup: look up a page in an amap.
 *
 * => amap should be locked by caller.
 */
struct vm_anon *
amap_lookup(struct vm_aref *aref, vaddr_t offset)
{
	int slot;
	struct vm_amap *amap = aref->ar_amap;
	struct vm_amap_chunk *chunk;

	AMAP_B2SLOT(slot, offset);
	slot += aref->ar_pageoff;
	KASSERT(slot < amap->am_nslot);

	chunk = amap_chunk_get(amap, slot, 0, PR_NOWAIT);
	if (chunk == NULL)
		return NULL;

	return chunk->ac_anon[UVM_AMAP_SLOTIDX(slot)];
}

/*
 * amap_lookups: look up a range of pages in an amap.
 *
 * => amap should be locked by caller.
 * => XXXCDC: this interface is biased toward array-based amaps.  fix.
 */
void
amap_lookups(struct vm_aref *aref, vaddr_t offset,
    struct vm_anon **anons, int npages)
{
	int i, lcv, n, slot;
	struct vm_amap *amap = aref->ar_amap;
	struct vm_amap_chunk *chunk = NULL;

	AMAP_B2SLOT(slot, offset);
	slot += aref->ar_pageoff;

	KASSERT((slot + (npages - 1)) < amap->am_nslot);

	for (i = 0, lcv = slot; lcv < slot + npages; i += n, lcv += n) {
		n = UVM_AMAP_CHUNK - UVM_AMAP_SLOTIDX(lcv);
		if (lcv + n > slot + npages)
			n = slot + npages - lcv;

		chunk = amap_chunk_get(amap, lcv, 0, PR_NOWAIT);
		if (chunk == NULL)
			memset(&anons[i], 0, n * sizeof(*anons));
		else
			memcpy(&anons[i],
			    &chunk->ac_anon[UVM_AMAP_SLOTIDX(lcv)],
			    n * sizeof(*anons));
	}
}

/*
 * amap_populate: ensure that the amap can store an anon for the page at
 * offset. This function can sleep until memory to store the anon is
 * available.
 */
void
amap_populate(struct vm_aref *aref, vaddr_t offset)
{
	int slot;
	struct vm_amap *amap = aref->ar_amap;
	struct vm_amap_chunk *chunk;

	AMAP_B2SLOT(slot, offset);
	slot += aref->ar_pageoff;
	KASSERT(slot < amap->am_nslot);

	chunk = amap_chunk_get(amap, slot, 1, PR_WAITOK);
	KASSERT(chunk != NULL);
}

/*
 * amap_add: add (or replace) a page to an amap.
 *
 * => amap should be locked by caller.
 * => anon must have the lock associated with this amap.
 */
int
amap_add(struct vm_aref *aref, vaddr_t offset, struct vm_anon *anon,
    boolean_t replace)
{
	int slot;
	struct vm_amap *amap = aref->ar_amap;
	struct vm_amap_chunk *chunk;

	AMAP_B2SLOT(slot, offset);
	slot += aref->ar_pageoff;
	KASSERT(slot < amap->am_nslot);

	chunk = amap_chunk_get(amap, slot, 1, PR_NOWAIT);
	if (chunk == NULL)
		return 1;

	slot = UVM_AMAP_SLOTIDX(slot);
	if (replace) {
		struct vm_anon *oanon  = chunk->ac_anon[slot];

		KASSERT(oanon != NULL);
		if (oanon->an_page && (amap->am_flags & AMAP_SHARED) != 0) {
			pmap_page_protect(oanon->an_page, PROT_NONE);
			/*
			 * XXX: suppose page is supposed to be wired somewhere?
			 */
		}
	} else {   /* !replace */
		if (chunk->ac_anon[slot] != NULL)
			panic("amap_add: slot in use");

		chunk->ac_usedmap |= 1 << slot;
		amap->am_nused++;
	}
	chunk->ac_anon[slot] = anon;

	return 0;
}

/*
 * amap_unadd: remove a page from an amap.
 *
 * => amap should be locked by caller.
 */
void
amap_unadd(struct vm_aref *aref, vaddr_t offset)
{
	struct vm_amap *amap = aref->ar_amap;
	struct vm_amap_chunk *chunk;
	int slot;

	KASSERT(rw_write_held(amap->am_lock));

	AMAP_B2SLOT(slot, offset);
	slot += aref->ar_pageoff;
	KASSERT(slot < amap->am_nslot);
	chunk = amap_chunk_get(amap, slot, 0, PR_NOWAIT);
	KASSERT(chunk != NULL);

	slot = UVM_AMAP_SLOTIDX(slot);
	KASSERT(chunk->ac_anon[slot] != NULL);

	chunk->ac_anon[slot] = NULL;
	chunk->ac_usedmap &= ~(1 << slot);
	amap->am_nused--;

	if (chunk->ac_usedmap == 0)
		amap_chunk_free(amap, chunk);
}

/*
 * amap_adjref_anons: adjust the reference count(s) on amap and its anons.
 */
static void
amap_adjref_anons(struct vm_amap *amap, vaddr_t offset, vsize_t len,
    int refv, boolean_t all)
{
#ifdef UVM_AMAP_PPREF
	KASSERT(rw_write_held(amap->am_lock));

	/*
	 * We must establish the ppref array before changing am_ref
	 * so that the ppref values match the current amap refcount.
	 */
	if (amap->am_ppref == NULL && !all && len != amap->am_nslot) {
		amap_pp_establish(amap);
	}
#endif

	amap->am_ref += refv;

#ifdef UVM_AMAP_PPREF
	if (amap->am_ppref && amap->am_ppref != PPREF_NONE) {
		if (all) {
			amap_pp_adjref(amap, 0, amap->am_nslot, refv);
		} else {
			amap_pp_adjref(amap, offset, len, refv);
		}
	}
#endif
	amap_unlock(amap);
}

/*
 * amap_ref: gain a reference to an amap.
 *
 * => amap must not be locked (we will lock).
 * => "offset" and "len" are in units of pages.
 * => Called at fork time to gain the child's reference.
 */
void
amap_ref(struct vm_amap *amap, vaddr_t offset, vsize_t len, int flags)
{
	amap_lock(amap);
	if (flags & AMAP_SHARED)
		amap->am_flags |= AMAP_SHARED;
	amap_adjref_anons(amap, offset, len, 1, (flags & AMAP_REFALL) != 0);
}

/*
 * amap_unref: remove a reference to an amap.
 *
 * => All pmap-level references to this amap must be already removed.
 * => Called from uvm_unmap_detach(); entry is already removed from the map.
 * => We will lock amap, so it must be unlocked.
 */
void
amap_unref(struct vm_amap *amap, vaddr_t offset, vsize_t len, boolean_t all)
{
	amap_lock(amap);

	KASSERT(amap->am_ref > 0);

	if (amap->am_ref == 1) {
		/*
		 * If the last reference - wipeout and destroy the amap.
		 */
		amap->am_ref--;
		amap_wipeout(amap);
		return;
	}

	/*
	 * Otherwise, drop the reference count(s) on anons.
	 */
	if (amap->am_ref == 2 && (amap->am_flags & AMAP_SHARED) != 0) {
		amap->am_flags &= ~AMAP_SHARED;
	}
	amap_adjref_anons(amap, offset, len, -1, all);
}