271 lines
9.4 KiB
C
271 lines
9.4 KiB
C
/* $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_ */
|