Return to uvm_amap.h CVS log

Up to [local] / src / sys / uvm

(re)Introduce locking for amaps & anons.

A rwlock is attached to every amap and is shared with all its anon.  The
same lock will be used by multiple amaps if they have anons in common.

This should be enough to get the upper part of the fault handler out of the
KERNEL_LOCK() which seems to bring up to 20% improvements in builds.

This is based/copied/adapted from the most recent work done in NetBSD which
is an evolution of the precendent simple_lock scheme.

Tested by many, thanks!

ok kettenis@, mvs@

/*	$OpenBSD: uvm_amap.h,v 1.33 2021/01/19 13:21:36 mpi 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 {
	struct rwlock *am_lock;	/* lock for all vm_amap flags */
	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_nbuckets; /* # of buckets */
			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_nbuckets	am_impl.ami_normal.amn_nbuckets
#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 PROT_NONE (reserve space for stack)
 *  2. a 512 slot amap at protection PROT_READ|PROT_WRITE (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)

#define amap_lock(AMAP)		rw_enter_write((AMAP)->am_lock)
#define amap_unlock(AMAP)	rw_exit_write((AMAP)->am_lock)

#endif /* _KERNEL */

#endif /* _UVM_UVM_AMAP_H_ */