1 /* $OpenBSD: uvm_map.h,v 1.29 2003/04/14 04:53:51 art Exp $ */
2 /* $NetBSD: uvm_map.h,v 1.24 2001/02/18 21:19:08 chs Exp $ */
3
4 /*
5 * Copyright (c) 1997 Charles D. Cranor and Washington University.
6 * Copyright (c) 1991, 1993, The Regents of the University of California.
7 *
8 * All rights reserved.
9 *
10 * This code is derived from software contributed to Berkeley by
11 * The Mach Operating System project at Carnegie-Mellon University.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
15 * are met:
16 * 1. Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 * 2. Redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution.
21 * 3. All advertising materials mentioning features or use of this software
22 * must display the following acknowledgement:
23 * This product includes software developed by Charles D. Cranor,
24 * Washington University, the University of California, Berkeley and
25 * its contributors.
26 * 4. Neither the name of the University nor the names of its contributors
27 * may be used to endorse or promote products derived from this software
28 * without specific prior written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
31 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
32 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
34 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
35 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
36 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
37 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
38 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
39 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
40 * SUCH DAMAGE.
41 *
42 * @(#)vm_map.h 8.3 (Berkeley) 3/15/94
43 * from: Id: uvm_map.h,v 1.1.2.3 1998/02/07 01:16:55 chs Exp
44 *
45 *
46 * Copyright (c) 1987, 1990 Carnegie-Mellon University.
47 * All rights reserved.
48 *
49 * Permission to use, copy, modify and distribute this software and
50 * its documentation is hereby granted, provided that both the copyright
51 * notice and this permission notice appear in all copies of the
52 * software, derivative works or modified versions, and any portions
53 * thereof, and that both notices appear in supporting documentation.
54 *
55 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
56 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
57 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
58 *
59 * Carnegie Mellon requests users of this software to return to
60 *
61 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
62 * School of Computer Science
63 * Carnegie Mellon University
64 * Pittsburgh PA 15213-3890
65 *
66 * any improvements or extensions that they make and grant Carnegie the
67 * rights to redistribute these changes.
68 */
69
70 #ifndef _UVM_UVM_MAP_H_
71 #define _UVM_UVM_MAP_H_
72
73 /*
74 * uvm_map.h
75 */
76
77 #ifdef _KERNEL
78
79 /*
80 * macros
81 */
82
83 /*
84 * UVM_MAP_CLIP_START: ensure that the entry begins at or after
85 * the starting address, if it doesn't we split the entry.
86 *
87 * => map must be locked by caller
88 */
89
90 #define UVM_MAP_CLIP_START(MAP,ENTRY,VA) { \
91 if ((VA) > (ENTRY)->start) uvm_map_clip_start(MAP,ENTRY,VA); }
92
93 /*
94 * UVM_MAP_CLIP_END: ensure that the entry ends at or before
95 * the ending address, if it does't we split the entry.
96 *
97 * => map must be locked by caller
98 */
99
100 #define UVM_MAP_CLIP_END(MAP,ENTRY,VA) { \
101 if ((VA) < (ENTRY)->end) uvm_map_clip_end(MAP,ENTRY,VA); }
102
103 /*
104 * extract flags
105 */
106 #define UVM_EXTRACT_REMOVE 0x1 /* remove mapping from old map */
107 #define UVM_EXTRACT_CONTIG 0x2 /* try to keep it contig */
108 #define UVM_EXTRACT_QREF 0x4 /* use quick refs */
109 #define UVM_EXTRACT_FIXPROT 0x8 /* set prot to maxprot as we go */
110
111 #endif /* _KERNEL */
112
113 #include <uvm/uvm_anon.h>
114
115 /*
116 * types defined:
117 *
118 * vm_map_t the high-level address map data structure.
119 * vm_map_entry_t an entry in an address map.
120 * vm_map_version_t a timestamp of a map, for use with vm_map_lookup
121 */
122
123 /*
124 * Objects which live in maps may be either VM objects, or another map
125 * (called a "sharing map") which denotes read-write sharing with other maps.
126 *
127 * XXXCDC: private pager data goes here now
128 */
129
130 union vm_map_object {
131 struct uvm_object *uvm_obj; /* UVM OBJECT */
132 struct vm_map *sub_map; /* belongs to another map */
133 };
134
135 /*
136 * Address map entries consist of start and end addresses,
137 * a VM object (or sharing map) and offset into that object,
138 * and user-exported inheritance and protection information.
139 * Also included is control information for virtual copy operations.
140 */
141 struct vm_map_entry {
142 RB_ENTRY(vm_map_entry) rb_entry; /* tree information */
143 vaddr_t ownspace; /* free space after */
144 vaddr_t space; /* space in subtree */
145 struct vm_map_entry *prev; /* previous entry */
146 struct vm_map_entry *next; /* next entry */
147 vaddr_t start; /* start address */
148 vaddr_t end; /* end address */
149 union vm_map_object object; /* object I point to */
150 voff_t offset; /* offset into object */
151 int etype; /* entry type */
152 vm_prot_t protection; /* protection code */
153 vm_prot_t max_protection; /* maximum protection */
154 vm_inherit_t inheritance; /* inheritance */
155 int wired_count; /* can be paged if == 0 */
156 struct vm_aref aref; /* anonymous overlay */
157 int advice; /* madvise advice */
158 #define uvm_map_entry_stop_copy flags
159 u_int8_t flags; /* flags */
160
161 #define UVM_MAP_STATIC 0x01 /* static map entry */
162 #define UVM_MAP_KMEM 0x02 /* from kmem entry pool */
163
164 };
165
166 #define VM_MAPENT_ISWIRED(entry) ((entry)->wired_count != 0)
167
168 /*
169 * Maps are doubly-linked lists of map entries, kept sorted
170 * by address. A single hint is provided to start
171 * searches again from the last successful search,
172 * insertion, or removal.
173 *
174 * LOCKING PROTOCOL NOTES:
175 * -----------------------
176 *
177 * VM map locking is a little complicated. There are both shared
178 * and exclusive locks on maps. However, it is sometimes required
179 * to downgrade an exclusive lock to a shared lock, and upgrade to
180 * an exclusive lock again (to perform error recovery). However,
181 * another thread *must not* queue itself to receive an exclusive
182 * lock while before we upgrade back to exclusive, otherwise the
183 * error recovery becomes extremely difficult, if not impossible.
184 *
185 * In order to prevent this scenario, we introduce the notion of
186 * a `busy' map. A `busy' map is read-locked, but other threads
187 * attempting to write-lock wait for this flag to clear before
188 * entering the lock manager. A map may only be marked busy
189 * when the map is write-locked (and then the map must be downgraded
190 * to read-locked), and may only be marked unbusy by the thread
191 * which marked it busy (holding *either* a read-lock or a
192 * write-lock, the latter being gained by an upgrade).
193 *
194 * Access to the map `flags' member is controlled by the `flags_lock'
195 * simple lock. Note that some flags are static (set once at map
196 * creation time, and never changed), and thus require no locking
197 * to check those flags. All flags which are r/w must be set or
198 * cleared while the `flags_lock' is asserted. Additional locking
199 * requirements are:
200 *
201 * VM_MAP_PAGEABLE r/o static flag; no locking required
202 *
203 * VM_MAP_INTRSAFE r/o static flag; no locking required
204 *
205 * VM_MAP_WIREFUTURE r/w; may only be set or cleared when
206 * map is write-locked. may be tested
207 * without asserting `flags_lock'.
208 *
209 * VM_MAP_BUSY r/w; may only be set when map is
210 * write-locked, may only be cleared by
211 * thread which set it, map read-locked
212 * or write-locked. must be tested
213 * while `flags_lock' is asserted.
214 *
215 * VM_MAP_WANTLOCK r/w; may only be set when the map
216 * is busy, and thread is attempting
217 * to write-lock. must be tested
218 * while `flags_lock' is asserted.
219 */
220 struct vm_map {
221 struct pmap * pmap; /* Physical map */
222 lock_data_t lock; /* Lock for map data */
223 RB_HEAD(uvm_tree, vm_map_entry) rbhead; /* Tree for entries */
224 struct vm_map_entry header; /* List of entries */
225 int nentries; /* Number of entries */
226 vsize_t size; /* virtual size */
227 int ref_count; /* Reference count */
228 simple_lock_data_t ref_lock; /* Lock for ref_count field */
229 vm_map_entry_t hint; /* hint for quick lookups */
230 simple_lock_data_t hint_lock; /* lock for hint storage */
231 vm_map_entry_t first_free; /* First free space hint */
232 int flags; /* flags */
233 simple_lock_data_t flags_lock; /* Lock for flags field */
234 unsigned int timestamp; /* Version number */
235 #define min_offset header.start
236 #define max_offset header.end
237 };
238
239 /* vm_map flags */
240 #define VM_MAP_PAGEABLE 0x01 /* ro: entries are pageable */
241 #define VM_MAP_INTRSAFE 0x02 /* ro: interrupt safe map */
242 #define VM_MAP_WIREFUTURE 0x04 /* rw: wire future mappings */
243 #define VM_MAP_BUSY 0x08 /* rw: map is busy */
244 #define VM_MAP_WANTLOCK 0x10 /* rw: want to write-lock */
245
246 /* XXX: number of kernel maps and entries to statically allocate */
247
248 #if !defined(MAX_KMAPENT)
249 #if (50 + (2 * NPROC) > 1000)
250 #define MAX_KMAPENT (50 + (2 * NPROC))
251 #else
252 #define MAX_KMAPENT 1000 /* XXXCDC: no crash */
253 #endif
254 #endif /* !defined MAX_KMAPENT */
255
256 #ifdef _KERNEL
257 #define vm_map_modflags(map, set, clear) \
258 do { \
259 simple_lock(&(map)->flags_lock); \
260 (map)->flags = ((map)->flags | (set)) & ~(clear); \
261 simple_unlock(&(map)->flags_lock); \
262 } while (0)
263 #endif /* _KERNEL */
264
265 /*
266 * Interrupt-safe maps must also be kept on a special list,
267 * to assist uvm_fault() in avoiding locking problems.
268 */
269 struct vm_map_intrsafe {
270 struct vm_map vmi_map;
271 LIST_ENTRY(vm_map_intrsafe) vmi_list;
272 };
273
274 LIST_HEAD(vmi_list, vm_map_intrsafe);
275 #ifdef _KERNEL
276 extern simple_lock_data_t vmi_list_slock;
277 extern struct vmi_list vmi_list;
278
279 static __inline int vmi_list_lock(void);
280 static __inline void vmi_list_unlock(int);
281
282 static __inline int
vmi_list_lock()283 vmi_list_lock()
284 {
285 int s;
286
287 s = splhigh();
288 simple_lock(&vmi_list_slock);
289 return (s);
290 }
291
292 static __inline void
vmi_list_unlock(s)293 vmi_list_unlock(s)
294 int s;
295 {
296
297 simple_unlock(&vmi_list_slock);
298 splx(s);
299 }
300 #endif /* _KERNEL */
301
302 /*
303 * handle inline options
304 */
305
306 #ifdef UVM_MAP_INLINE
307 #define MAP_INLINE static __inline
308 #else
309 #define MAP_INLINE /* nothing */
310 #endif /* UVM_MAP_INLINE */
311
312 /*
313 * globals:
314 */
315
316 #ifdef _KERNEL
317
318 #ifdef PMAP_GROWKERNEL
319 extern vaddr_t uvm_maxkaddr;
320 #endif
321
322 /*
323 * protos: the following prototypes define the interface to vm_map
324 */
325
326 MAP_INLINE
327 void uvm_map_deallocate(vm_map_t);
328
329 int uvm_map_clean(vm_map_t, vaddr_t, vaddr_t, int);
330 void uvm_map_clip_start(vm_map_t, vm_map_entry_t, vaddr_t);
331 void uvm_map_clip_end(vm_map_t, vm_map_entry_t, vaddr_t);
332 MAP_INLINE
333 vm_map_t uvm_map_create(pmap_t, vaddr_t, vaddr_t, int);
334 int uvm_map_extract(vm_map_t, vaddr_t, vsize_t,
335 vm_map_t, vaddr_t *, int);
336 vm_map_entry_t uvm_map_findspace(vm_map_t, vaddr_t, vsize_t, vaddr_t *,
337 struct uvm_object *, voff_t, vsize_t, int);
338 vaddr_t uvm_map_hint(struct proc *, vm_prot_t);
339 int uvm_map_inherit(vm_map_t, vaddr_t, vaddr_t, vm_inherit_t);
340 int uvm_map_advice(vm_map_t, vaddr_t, vaddr_t, int);
341 void uvm_map_init(void);
342 boolean_t uvm_map_lookup_entry(vm_map_t, vaddr_t, vm_map_entry_t *);
343 MAP_INLINE
344 void uvm_map_reference(vm_map_t);
345 int uvm_map_replace(vm_map_t, vaddr_t, vaddr_t,
346 vm_map_entry_t, int);
347 int uvm_map_reserve(vm_map_t, vsize_t, vaddr_t, vsize_t,
348 vaddr_t *);
349 void uvm_map_setup(vm_map_t, vaddr_t, vaddr_t, int);
350 int uvm_map_submap(vm_map_t, vaddr_t, vaddr_t, vm_map_t);
351 MAP_INLINE
352 void uvm_unmap(vm_map_t, vaddr_t, vaddr_t);
353 void uvm_unmap_detach(vm_map_entry_t,int);
354 void uvm_unmap_remove(vm_map_t, vaddr_t, vaddr_t,
355 vm_map_entry_t *);
356
357 #endif /* _KERNEL */
358
359 /*
360 * VM map locking operations:
361 *
362 * These operations perform locking on the data portion of the
363 * map.
364 *
365 * vm_map_lock_try: try to lock a map, failing if it is already locked.
366 *
367 * vm_map_lock: acquire an exclusive (write) lock on a map.
368 *
369 * vm_map_lock_read: acquire a shared (read) lock on a map.
370 *
371 * vm_map_unlock: release an exclusive lock on a map.
372 *
373 * vm_map_unlock_read: release a shared lock on a map.
374 *
375 * vm_map_downgrade: downgrade an exclusive lock to a shared lock.
376 *
377 * vm_map_upgrade: upgrade a shared lock to an exclusive lock.
378 *
379 * vm_map_busy: mark a map as busy.
380 *
381 * vm_map_unbusy: clear busy status on a map.
382 *
383 * Note that "intrsafe" maps use only exclusive, spin locks. We simply
384 * use the sleep lock's interlock for this.
385 */
386
387 #ifdef _KERNEL
388 /* XXX: clean up later */
389 #include <sys/time.h>
390 #include <sys/proc.h> /* for tsleep(), wakeup() */
391 #include <sys/systm.h> /* for panic() */
392
393 static __inline boolean_t vm_map_lock_try(vm_map_t);
394 static __inline void vm_map_lock(vm_map_t);
395 extern const char vmmapbsy[];
396
397 static __inline boolean_t
vm_map_lock_try(map)398 vm_map_lock_try(map)
399 vm_map_t map;
400 {
401 boolean_t rv;
402
403 if (map->flags & VM_MAP_INTRSAFE)
404 rv = simple_lock_try(&map->lock.lk_interlock);
405 else {
406 simple_lock(&map->flags_lock);
407 if (map->flags & VM_MAP_BUSY) {
408 simple_unlock(&map->flags_lock);
409 return (FALSE);
410 }
411 rv = (lockmgr(&map->lock, LK_EXCLUSIVE|LK_NOWAIT|LK_INTERLOCK,
412 &map->flags_lock, curproc) == 0);
413 }
414
415 if (rv)
416 map->timestamp++;
417
418 return (rv);
419 }
420
421 static __inline void
vm_map_lock(map)422 vm_map_lock(map)
423 vm_map_t map;
424 {
425 int error;
426
427 if (map->flags & VM_MAP_INTRSAFE) {
428 simple_lock(&map->lock.lk_interlock);
429 return;
430 }
431
432 try_again:
433 simple_lock(&map->flags_lock);
434 while (map->flags & VM_MAP_BUSY) {
435 map->flags |= VM_MAP_WANTLOCK;
436 ltsleep(&map->flags, PVM, (char *)vmmapbsy, 0, &map->flags_lock);
437 }
438
439 error = lockmgr(&map->lock, LK_EXCLUSIVE|LK_SLEEPFAIL|LK_INTERLOCK,
440 &map->flags_lock, curproc);
441
442 if (error) {
443 goto try_again;
444 }
445
446 (map)->timestamp++;
447 }
448
449 #ifdef DIAGNOSTIC
450 #define vm_map_lock_read(map) \
451 do { \
452 if (map->flags & VM_MAP_INTRSAFE) \
453 panic("vm_map_lock_read: intrsafe map"); \
454 (void) lockmgr(&(map)->lock, LK_SHARED, NULL, curproc); \
455 } while (0)
456 #else
457 #define vm_map_lock_read(map) \
458 (void) lockmgr(&(map)->lock, LK_SHARED, NULL, curproc)
459 #endif
460
461 #define vm_map_unlock(map) \
462 do { \
463 if ((map)->flags & VM_MAP_INTRSAFE) \
464 simple_unlock(&(map)->lock.lk_interlock); \
465 else \
466 (void) lockmgr(&(map)->lock, LK_RELEASE, NULL, curproc);\
467 } while (0)
468
469 #define vm_map_unlock_read(map) \
470 (void) lockmgr(&(map)->lock, LK_RELEASE, NULL, curproc)
471
472 #define vm_map_downgrade(map) \
473 (void) lockmgr(&(map)->lock, LK_DOWNGRADE, NULL, curproc)
474
475 #ifdef DIAGNOSTIC
476 #define vm_map_upgrade(map) \
477 do { \
478 if (lockmgr(&(map)->lock, LK_UPGRADE, NULL, curproc) != 0) \
479 panic("vm_map_upgrade: failed to upgrade lock"); \
480 } while (0)
481 #else
482 #define vm_map_upgrade(map) \
483 (void) lockmgr(&(map)->lock, LK_UPGRADE, NULL, curproc)
484 #endif
485
486 #define vm_map_busy(map) \
487 do { \
488 simple_lock(&(map)->flags_lock); \
489 (map)->flags |= VM_MAP_BUSY; \
490 simple_unlock(&(map)->flags_lock); \
491 } while (0)
492
493 #define vm_map_unbusy(map) \
494 do { \
495 int oflags; \
496 \
497 simple_lock(&(map)->flags_lock); \
498 oflags = (map)->flags; \
499 (map)->flags &= ~(VM_MAP_BUSY|VM_MAP_WANTLOCK); \
500 simple_unlock(&(map)->flags_lock); \
501 if (oflags & VM_MAP_WANTLOCK) \
502 wakeup(&(map)->flags); \
503 } while (0)
504 #endif /* _KERNEL */
505
506 /*
507 * Functions implemented as macros
508 */
509 #define vm_map_min(map) ((map)->min_offset)
510 #define vm_map_max(map) ((map)->max_offset)
511 #define vm_map_pmap(map) ((map)->pmap)
512
513 #endif /* _UVM_UVM_MAP_H_ */
514