1 /* $OpenBSD: uvm_amap.h,v 1.17 2007/06/18 21:51:15 pedro Exp $ */
2 /* $NetBSD: uvm_amap.h,v 1.14 2001/02/18 21:19:08 chs Exp $ */
3
4 /*
5 *
6 * Copyright (c) 1997 Charles D. Cranor and Washington University.
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 * 3. All advertising materials mentioning features or use of this software
18 * must display the following acknowledgement:
19 * This product includes software developed by Charles D. Cranor and
20 * Washington University.
21 * 4. The name of the author may not be used to endorse or promote products
22 * derived from this software without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
25 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
26 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
27 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
28 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
29 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
30 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
31 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
33 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 */
35
36 #ifndef _UVM_UVM_AMAP_H_
37 #define _UVM_UVM_AMAP_H_
38
39 /*
40 * uvm_amap.h: general amap interface and amap implementation-specific info
41 */
42
43 /*
44 * an amap structure contains pointers to a set of anons that are
45 * mapped together in virtual memory (an anon is a single page of
46 * anonymous virtual memory -- see uvm_anon.h). in uvm we hide the
47 * details of the implementation of amaps behind a general amap
48 * interface. this allows us to change the amap implementation
49 * without having to touch the rest of the code. this file is divided
50 * into two parts: the definition of the uvm amap interface and the
51 * amap implementation-specific definitions.
52 */
53
54 #ifdef _KERNEL
55
56 /*
57 * part 1: amap interface
58 */
59
60 /*
61 * forward definition of vm_amap structure. only amap
62 * implementation-specific code should directly access the fields of
63 * this structure.
64 */
65
66 struct vm_amap;
67
68 /*
69 * handle inline options... we allow amap ops to be inline, but we also
70 * provide a hook to turn this off. macros can also be used.
71 */
72
73 #ifdef UVM_AMAP_INLINE /* defined/undef'd in uvm_amap.c */
74 #define AMAP_INLINE static __inline /* inline enabled */
75 #else
76 #define AMAP_INLINE /* inline disabled */
77 #endif /* UVM_AMAP_INLINE */
78
79
80 /*
81 * prototypes for the amap interface
82 */
83
84 AMAP_INLINE /* add an anon to an amap */
85 void amap_add(struct vm_aref *, vaddr_t, struct vm_anon *, boolean_t);
86 /* allocate a new amap */
87 struct vm_amap *amap_alloc(vaddr_t, vaddr_t, int);
88 /* clear amap needs-copy flag */
89 void amap_copy(vm_map_t, vm_map_entry_t, int, boolean_t, vaddr_t,
90 vaddr_t);
91 /* resolve all COW faults now */
92 void amap_cow_now(vm_map_t, vm_map_entry_t);
93 /* make amap larger */
94 int amap_extend(vm_map_entry_t, vsize_t);
95 /* get amap's flags */
96 int amap_flags(struct vm_amap *);
97 /* free amap */
98 void amap_free(struct vm_amap *);
99 /* init amap module (at boot time) */
100 void amap_init(void);
101 AMAP_INLINE /* lookup an anon @ offset in amap */
102 struct vm_anon *amap_lookup(struct vm_aref *, vaddr_t);
103 AMAP_INLINE /* lookup multiple anons */
104 void amap_lookups(struct vm_aref *, vaddr_t, struct vm_anon **, int);
105 AMAP_INLINE /* add a reference to an amap */
106 void amap_ref(struct vm_amap *, vaddr_t, vsize_t, int);
107 /* get number of references of amap */
108 int amap_refs(struct vm_amap *);
109 /* protect pages in a shared amap */
110 void amap_share_protect(vm_map_entry_t, vm_prot_t);
111 /* split reference to amap into two */
112 void amap_splitref(struct vm_aref *, struct vm_aref *, vaddr_t);
113 AMAP_INLINE /* remove an anon from an amap */
114 void amap_unadd(struct vm_aref *, vaddr_t);
115 AMAP_INLINE /* drop reference to an amap */
116 void amap_unref(struct vm_amap *, vaddr_t, vsize_t, int);
117 /* remove all anons from amap */
118 void amap_wipeout(struct vm_amap *);
119 boolean_t amap_swap_off(int, int);
120
121 /*
122 * amap flag values
123 */
124
125 #define AMAP_SHARED 0x1 /* amap is shared */
126 #define AMAP_REFALL 0x2 /* amap_ref: reference entire amap */
127 #define AMAP_SWAPOFF 0x4 /* amap_swap_off() is in progress */
128
129 #endif /* _KERNEL */
130
131 /**********************************************************************/
132
133 /*
134 * part 2: amap implementation-specific info
135 */
136
137 /*
138 * we currently provide an array-based amap implementation. in this
139 * implementation we provide the option of tracking split references
140 * so that we don't lose track of references during partial unmaps
141 * ... this is enabled with the "UVM_AMAP_PPREF" define.
142 */
143
144 #define UVM_AMAP_PPREF /* track partial references */
145
146 /*
147 * here is the definition of the vm_amap structure for this implementation.
148 */
149
150 struct vm_amap {
151 int am_ref; /* reference count */
152 int am_flags; /* flags */
153 int am_maxslot; /* max # of slots allocated */
154 int am_nslot; /* # of slots currently in map ( <= maxslot) */
155 int am_nused; /* # of slots currently in use */
156 int *am_slots; /* contig array of active slots */
157 int *am_bckptr; /* back pointer array to am_slots */
158 struct vm_anon **am_anon; /* array of anonymous pages */
159 #ifdef UVM_AMAP_PPREF
160 int *am_ppref; /* per page reference count (if !NULL) */
161 #endif
162 LIST_ENTRY(vm_amap) am_list;
163 };
164
165 /*
166 * note that am_slots, am_bckptr, and am_anon are arrays. this allows
167 * fast lookup of pages based on their virual address at the expense of
168 * some extra memory. in the future we should be smarter about memory
169 * usage and fall back to a non-array based implementation on systems
170 * that are short of memory (XXXCDC).
171 *
172 * the entries in the array are called slots... for example an amap that
173 * covers four pages of virtual memory is said to have four slots. here
174 * is an example of the array usage for a four slot amap. note that only
175 * slots one and three have anons assigned to them. "D/C" means that we
176 * "don't care" about the value.
177 *
178 * 0 1 2 3
179 * am_anon: NULL, anon0, NULL, anon1 (actual pointers to anons)
180 * am_bckptr: D/C, 1, D/C, 0 (points to am_slots entry)
181 *
182 * am_slots: 3, 1, D/C, D/C (says slots 3 and 1 are in use)
183 *
184 * note that am_bckptr is D/C if the slot in am_anon is set to NULL.
185 * to find the entry in am_slots for an anon, look at am_bckptr[slot],
186 * thus the entry for slot 3 in am_slots[] is at am_slots[am_bckptr[3]].
187 * in general, if am_anon[X] is non-NULL, then the following must be
188 * true: am_slots[am_bckptr[X]] == X
189 *
190 * note that am_slots is always contig-packed.
191 */
192
193 /*
194 * defines for handling of large sparce amaps:
195 *
196 * one of the problems of array-based amaps is that if you allocate a
197 * large sparcely-used area of virtual memory you end up allocating
198 * large arrays that, for the most part, don't get used. this is a
199 * problem for BSD in that the kernel likes to make these types of
200 * allocations to "reserve" memory for possible future use.
201 *
202 * for example, the kernel allocates (reserves) a large chunk of user
203 * VM for possible stack growth. most of the time only a page or two
204 * of this VM is actually used. since the stack is anonymous memory
205 * it makes sense for it to live in an amap, but if we allocated an
206 * amap for the entire stack range we could end up wasting a large
207 * amount of malloc'd KVM.
208 *
209 * for example, on the i386 at boot time we allocate two amaps for the stack
210 * of /sbin/init:
211 * 1. a 7680 slot amap at protection 0 (reserve space for stack)
212 * 2. a 512 slot amap at protection 7 (top of stack)
213 *
214 * most of the array allocated for the amaps for this is never used.
215 * the amap interface provides a way for us to avoid this problem by
216 * allowing amap_copy() to break larger amaps up into smaller sized
217 * chunks (controlled by the "canchunk" option). we use this feature
218 * to reduce our memory usage with the BSD stack management. if we
219 * are asked to create an amap with more than UVM_AMAP_LARGE slots in it,
220 * we attempt to break it up into a UVM_AMAP_CHUNK sized amap if the
221 * "canchunk" flag is set.
222 *
223 * so, in the i386 example, the 7680 slot area is never referenced so
224 * nothing gets allocated (amap_copy is never called because the protection
225 * is zero). the 512 slot area for the top of the stack is referenced.
226 * the chunking code breaks it up into 16 slot chunks (hopefully a single
227 * 16 slot chunk is enough to handle the whole stack).
228 */
229
230 #define UVM_AMAP_LARGE 256 /* # of slots in "large" amap */
231 #define UVM_AMAP_CHUNK 16 /* # of slots to chunk large amaps in */
232
233 #ifdef _KERNEL
234
235 /*
236 * macros
237 */
238
239 /* AMAP_B2SLOT: convert byte offset to slot */
240 #define AMAP_B2SLOT(S,B) { \
241 KASSERT(((B) & (PAGE_SIZE - 1)) == 0); \
242 (S) = (B) >> PAGE_SHIFT; \
243 }
244
245 /*
246 * lock/unlock/refs/flags macros
247 */
248
249 #define amap_flags(AMAP) ((AMAP)->am_flags)
250 #define amap_refs(AMAP) ((AMAP)->am_ref)
251
252 /*
253 * if we enable PPREF, then we have a couple of extra functions that
254 * we need to prototype here...
255 */
256
257 #ifdef UVM_AMAP_PPREF
258
259 #define PPREF_NONE ((int *) -1) /* not using ppref */
260
261 /* adjust references */
262 void amap_pp_adjref(struct vm_amap *, int, vsize_t, int);
263 /* establish ppref */
264 void amap_pp_establish(struct vm_amap *);
265 /* wipe part of an amap */
266 void amap_wiperange(struct vm_amap *, int, int);
267 #endif /* UVM_AMAP_PPREF */
268
269 #endif /* _KERNEL */
270
271 #endif /* _UVM_UVM_AMAP_H_ */