/*	$OpenBSD: uvm_amap.h,v 1.29 2016/05/26 13:37:26 stefan Exp $	*/
/*	$NetBSD: uvm_amap.h,v 1.14 2001/02/18 21:19:08 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.
 */

#ifndef _UVM_UVM_AMAP_H_
#define _UVM_UVM_AMAP_H_

/*
 * uvm_amap.h: general amap interface and amap implementation-specific info
 */

/*
 * an amap structure contains pointers to a set of anons that are
 * mapped together in virtual memory (an anon is a single page of
 * anonymous virtual memory -- see uvm_anon.h).  in uvm we hide the
 * details of the implementation of amaps behind a general amap
 * interface.  this allows us to change the amap implementation
 * without having to touch the rest of the code.  this file is divided
 * into two parts: the definition of the uvm amap interface and the
 * amap implementation-specific definitions.
 */

#ifdef _KERNEL

/*
 * part 1: amap interface
 */

/*
 * forward definition of vm_amap structure.  only amap
 * implementation-specific code should directly access the fields of
 * this structure.  
 */

struct vm_amap;

/*
 * prototypes for the amap interface 
 */

					/* ensure amap can store anon */
void		amap_populate(struct vm_aref *, vaddr_t);
					/* add an anon to an amap */
int		amap_add(struct vm_aref *, vaddr_t, struct vm_anon *,
		    boolean_t);
					/* allocate a new amap */
struct vm_amap	*amap_alloc(vaddr_t, int, int);
					/* clear amap needs-copy flag */
void		amap_copy(vm_map_t, vm_map_entry_t, int, boolean_t, vaddr_t,
		    vaddr_t);
					/* resolve all COW faults now */
void		amap_cow_now(vm_map_t, vm_map_entry_t);
					/* free amap */
void		amap_free(struct vm_amap *);
					/* init amap module (at boot time) */
void		amap_init(void);
					/* lookup an anon @ offset in amap */
struct vm_anon	*amap_lookup(struct vm_aref *, vaddr_t);
					/* lookup multiple anons */
void		amap_lookups(struct vm_aref *, vaddr_t, struct vm_anon **, int);
					/* add a reference to an amap */
void		amap_ref(struct vm_amap *, vaddr_t, vsize_t, int);
					/* split reference to amap into two */
void		amap_splitref(struct vm_aref *, struct vm_aref *, vaddr_t);
					/* remove an anon from an amap */
void		amap_unadd(struct vm_aref *, vaddr_t);
					/* drop reference to an amap */
void		amap_unref(struct vm_amap *, vaddr_t, vsize_t, int);
					/* remove all anons from amap */
void		amap_wipeout(struct vm_amap *);
boolean_t	amap_swap_off(int, int);

/*
 * amap flag values
 */

#define AMAP_SHARED	0x1	/* amap is shared */
#define AMAP_REFALL	0x2	/* amap_ref: reference entire amap */
#define AMAP_SWAPOFF	0x4	/* amap_swap_off() is in progress */

#endif /* _KERNEL */

/**********************************************************************/

/*
 * part 2: amap implementation-specific info
 */

/*
 * we currently provide an array-based amap implementation.  in this
 * implementation we provide the option of tracking split references
 * so that we don't lose track of references during partial unmaps
 * ... this is enabled with the "UVM_AMAP_PPREF" define.
 */

#define UVM_AMAP_PPREF		/* track partial references */

/*
 * here is the definition of the vm_amap structure and helper structures for
 * this implementation.
 */

struct vm_amap_chunk {
	TAILQ_ENTRY(vm_amap_chunk) ac_list;
	int ac_baseslot;
	uint16_t ac_usedmap;
	uint16_t ac_nslot;
	struct vm_anon *ac_anon[];
};

struct vm_amap {
	int am_ref;		/* reference count */
	int am_flags;		/* flags */
	int am_nslot;		/* # of slots currently in map */
	int am_nused;		/* # of slots currently in use */
#ifdef UVM_AMAP_PPREF
	int *am_ppref;		/* per page reference count (if !NULL) */
#endif
	LIST_ENTRY(vm_amap) am_list;

	union {
		struct {
			struct vm_amap_chunk **amn_buckets;
			TAILQ_HEAD(, vm_amap_chunk) amn_chunks;
			int amn_ncused;	/* # of chunkers currently in use */
			int amn_hashshift; /* shift count to hash slot to bucket */
		} ami_normal;

		/*
		 * MUST be last element in vm_amap because it contains a
		 * variably sized array element.
		 */
		struct vm_amap_chunk ami_small;
	} am_impl;

#define am_buckets	am_impl.ami_normal.amn_buckets
#define am_chunks	am_impl.ami_normal.amn_chunks
#define am_ncused	am_impl.ami_normal.amn_ncused
#define am_hashshift	am_impl.ami_normal.amn_hashshift

#define am_small	am_impl.ami_small
};

/*
 * The entries in an amap are called slots. For example an amap that
 * covers four pages is said to have four slots.
 *
 * The slots of an amap are clustered into chunks of UVM_AMAP_CHUNK
 * slots each. The data structure of a chunk is vm_amap_chunk.
 * Every chunk contains an array of pointers to vm_anon, and a bitmap
 * is used to represent which of the slots are in use.
 *
 * Small amaps of up to UVM_AMAP_CHUNK slots have the chunk directly
 * embedded in the amap structure.
 *
 * amaps with more slots are normal amaps and organize chunks in a hash
 * table. The hash table is organized as an array of buckets.
 * All chunks of the amap are additionally stored in a linked list.
 * Chunks that belong to the same hash bucket are stored in the list
 * consecutively. When all slots in a chunk are unused, the chunk is freed.
 *
 * For large amaps, the bucket array can grow large. See the description
 * below how large bucket arrays are avoided.
 */

/*
 * defines for handling of large sparce amaps:
 * 
 * one of the problems of array-based amaps is that if you allocate a
 * large sparcely-used area of virtual memory you end up allocating
 * large arrays that, for the most part, don't get used.  this is a
 * problem for BSD in that the kernel likes to make these types of
 * allocations to "reserve" memory for possible future use.
 *
 * for example, the kernel allocates (reserves) a large chunk of user
 * VM for possible stack growth.  most of the time only a page or two
 * of this VM is actually used.  since the stack is anonymous memory
 * it makes sense for it to live in an amap, but if we allocated an
 * amap for the entire stack range we could end up wasting a large
 * amount of malloc'd KVM.
 * 
 * for example, on the i386 at boot time we allocate two amaps for the stack 
 * of /sbin/init: 
 *  1. a 7680 slot amap at protection 0 (reserve space for stack)
 *  2. a 512 slot amap at protection 7 (top of stack)
 *
 * most of the array allocated for the amaps for this is never used.  
 * the amap interface provides a way for us to avoid this problem by
 * allowing amap_copy() to break larger amaps up into smaller sized 
 * chunks (controlled by the "canchunk" option).   we use this feature
 * to reduce our memory usage with the BSD stack management.  if we
 * are asked to create an amap with more than UVM_AMAP_LARGE slots in it,
 * we attempt to break it up into a UVM_AMAP_CHUNK sized amap if the
 * "canchunk" flag is set.
 *
 * so, in the i386 example, the 7680 slot area is never referenced so
 * nothing gets allocated (amap_copy is never called because the protection
 * is zero).   the 512 slot area for the top of the stack is referenced.
 * the chunking code breaks it up into 16 slot chunks (hopefully a single
 * 16 slot chunk is enough to handle the whole stack).
 */

#define UVM_AMAP_LARGE	256	/* # of slots in "large" amap */
#define UVM_AMAP_CHUNK	16	/* # of slots to chunk large amaps in */

#define UVM_AMAP_SMALL(amap)		((amap)->am_nslot <= UVM_AMAP_CHUNK)
#define UVM_AMAP_SLOTIDX(slot)		((slot) % UVM_AMAP_CHUNK)
#define UVM_AMAP_BUCKET(amap, slot)				\
	(((slot) / UVM_AMAP_CHUNK) >> (amap)->am_hashshift)

#ifdef _KERNEL

/*
 * macros
 */

/* AMAP_B2SLOT: convert byte offset to slot */
#define AMAP_B2SLOT(S,B) {						\
	KASSERT(((B) & (PAGE_SIZE - 1)) == 0);				\
	(S) = (B) >> PAGE_SHIFT;					\
}

#define AMAP_CHUNK_FOREACH(chunk, amap)					\
	for (chunk = (UVM_AMAP_SMALL(amap) ?				\
	    &(amap)->am_small : TAILQ_FIRST(&(amap)->am_chunks));	\
	    (chunk) != NULL; (chunk) = TAILQ_NEXT(chunk, ac_list))

#define AMAP_BASE_SLOT(slot)						\
	(((slot) / UVM_AMAP_CHUNK) * UVM_AMAP_CHUNK)

/*
 * flags macros
 */

#define amap_flags(AMAP)	((AMAP)->am_flags)
#define amap_refs(AMAP)		((AMAP)->am_ref)

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

					/* adjust references */
void		amap_pp_adjref(struct vm_amap *, int, vsize_t, int);
					/* establish ppref */
void		amap_pp_establish(struct vm_amap *);
					/* wipe part of an amap */
void		amap_wiperange(struct vm_amap *, int, int);
#endif	/* UVM_AMAP_PPREF */

#endif /* _KERNEL */

#endif /* _UVM_UVM_AMAP_H_ */