1 /* $OpenBSD: uvm_map.h,v 1.10 2001/08/12 22:41:15 mickey Exp $ */ 2 /* $NetBSD: uvm_map.h,v 1.17 2000/03/29 04:05:47 simonb 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 125 * another map (called a "sharing map") which denotes read-write 126 * sharing with other maps. 127 * 128 * XXXCDC: private pager data goes here now 129 */ 130 131 union vm_map_object { 132 struct uvm_object *uvm_obj; /* UVM OBJECT */ 133 struct vm_map *sub_map; /* belongs to another map */ 134 }; 135 136 /* 137 * Address map entries consist of start and end addresses, 138 * a VM object (or sharing map) and offset into that object, 139 * and user-exported inheritance and protection information. 140 * Also included is control information for virtual copy operations. 141 */ 142 struct vm_map_entry { 143 struct vm_map_entry *prev; /* previous entry */ 144 struct vm_map_entry *next; /* next entry */ 145 vaddr_t start; /* start address */ 146 vaddr_t end; /* end address */ 147 union vm_map_object object; /* object I point to */ 148 voff_t offset; /* offset into object */ 149 /* etype is a bitmap that replaces the following 4 items */ 150 int etype; /* entry type */ 151 /* Only in task maps: */ 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 }; 163 164 #define VM_MAPENT_ISWIRED(entry) ((entry)->wired_count != 0) 165 166 /* 167 * Maps are doubly-linked lists of map entries, kept sorted 168 * by address. A single hint is provided to start 169 * searches again from the last successful search, 170 * insertion, or removal. 171 * 172 * LOCKING PROTOCOL NOTES: 173 * ----------------------- 174 * 175 * VM map locking is a little complicated. There are both shared 176 * and exclusive locks on maps. However, it is sometimes required 177 * to downgrade an exclusive lock to a shared lock, and upgrade to 178 * an exclusive lock again (to perform error recovery). However, 179 * another thread *must not* queue itself to receive an exclusive 180 * lock while before we upgrade back to exclusive, otherwise the 181 * error recovery becomes extremely difficult, if not impossible. 182 * 183 * In order to prevent this scenario, we introduce the notion of 184 * a `busy' map. A `busy' map is read-locked, but other threads 185 * attempting to write-lock wait for this flag to clear before 186 * entering the lock manager. A map may only be marked busy 187 * when the map is write-locked (and then the map must be downgraded 188 * to read-locked), and may only be marked unbusy by the thread 189 * which marked it busy (holding *either* a read-lock or a 190 * write-lock, the latter being gained by an upgrade). 191 * 192 * Access to the map `flags' member is controlled by the `flags_lock' 193 * simple lock. Note that some flags are static (set once at map 194 * creation time, and never changed), and thus require no locking 195 * to check those flags. All flags which are r/w must be set or 196 * cleared while the `flags_lock' is asserted. Additional locking 197 * requirements are: 198 * 199 * VM_MAP_PAGEABLE r/o static flag; no locking required 200 * 201 * VM_MAP_INTRSAFE r/o static flag; no locking required 202 * 203 * VM_MAP_WIREFUTURE r/w; may only be set or cleared when 204 * map is write-locked. may be tested 205 * without asserting `flags_lock'. 206 * 207 * VM_MAP_BUSY r/w; may only be set when map is 208 * write-locked, may only be cleared by 209 * thread which set it, map read-locked 210 * or write-locked. must be tested 211 * while `flags_lock' is asserted. 212 * 213 * VM_MAP_WANTLOCK r/w; may only be set when the map 214 * is busy, and thread is attempting 215 * to write-lock. must be tested 216 * while `flags_lock' is asserted. 217 */ 218 struct vm_map { 219 struct pmap * pmap; /* Physical map */ 220 lock_data_t lock; /* Lock for map data */ 221 struct vm_map_entry header; /* List of entries */ 222 int nentries; /* Number of entries */ 223 vsize_t size; /* virtual size */ 224 int ref_count; /* Reference count */ 225 simple_lock_data_t ref_lock; /* Lock for ref_count field */ 226 vm_map_entry_t hint; /* hint for quick lookups */ 227 simple_lock_data_t hint_lock; /* lock for hint storage */ 228 vm_map_entry_t first_free; /* First free space hint */ 229 int flags; /* flags */ 230 simple_lock_data_t flags_lock; /* Lock for flags field */ 231 unsigned int timestamp; /* Version number */ 232 #define min_offset header.start 233 #define max_offset header.end 234 }; 235 236 /* vm_map flags */ 237 #define VM_MAP_PAGEABLE 0x01 /* ro: entries are pageable*/ 238 #define VM_MAP_INTRSAFE 0x02 /* ro: interrupt safe map */ 239 #define VM_MAP_WIREFUTURE 0x04 /* rw: wire future mappings */ 240 #define VM_MAP_BUSY 0x08 /* rw: map is busy */ 241 #define VM_MAP_WANTLOCK 0x10 /* rw: want to write-lock */ 242 243 #ifdef _KERNEL 244 #define vm_map_modflags(map, set, clear) \ 245 do { \ 246 simple_lock(&(map)->flags_lock); \ 247 (map)->flags = ((map)->flags | (set)) & ~(clear); \ 248 simple_unlock(&(map)->flags_lock); \ 249 } while (0) 250 #endif /* _KERNEL */ 251 252 /* 253 * Interrupt-safe maps must also be kept on a special list, 254 * to assist uvm_fault() in avoiding locking problems. 255 */ 256 struct vm_map_intrsafe { 257 struct vm_map vmi_map; 258 LIST_ENTRY(vm_map_intrsafe) vmi_list; 259 }; 260 261 LIST_HEAD(vmi_list, vm_map_intrsafe); 262 #ifdef _KERNEL 263 extern simple_lock_data_t vmi_list_slock; 264 extern struct vmi_list vmi_list; 265 266 static __inline int vmi_list_lock __P((void)); 267 static __inline void vmi_list_unlock __P((int)); 268 269 static __inline int 270 vmi_list_lock() 271 { 272 int s; 273 274 s = splhigh(); 275 simple_lock(&vmi_list_slock); 276 return (s); 277 } 278 279 static __inline void 280 vmi_list_unlock(s) 281 int s; 282 { 283 284 simple_unlock(&vmi_list_slock); 285 splx(s); 286 } 287 #endif /* _KERNEL */ 288 289 /* 290 * VM map locking operations: 291 * 292 * These operations perform locking on the data portion of the 293 * map. 294 * 295 * vm_map_lock_try: try to lock a map, failing if it is already locked. 296 * 297 * vm_map_lock: acquire an exclusive (write) lock on a map. 298 * 299 * vm_map_lock_read: acquire a shared (read) lock on a map. 300 * 301 * vm_map_unlock: release an exclusive lock on a map. 302 * 303 * vm_map_unlock_read: release a shared lock on a map. 304 * 305 * vm_map_downgrade: downgrade an exclusive lock to a shared lock. 306 * 307 * vm_map_upgrade: upgrade a shared lock to an exclusive lock. 308 * 309 * vm_map_busy: mark a map as busy. 310 * 311 * vm_map_unbusy: clear busy status on a map. 312 * 313 * Note that "intrsafe" maps use only exclusive, spin locks. We simply 314 * use the sleep lock's interlock for this. 315 */ 316 317 #ifdef _KERNEL 318 /* XXX: clean up later */ 319 #include <sys/time.h> 320 #include <sys/proc.h> /* for tsleep(), wakeup() */ 321 #include <sys/systm.h> /* for panic() */ 322 323 static __inline boolean_t vm_map_lock_try __P((vm_map_t)); 324 static __inline void vm_map_lock __P((vm_map_t)); 325 326 static __inline boolean_t 327 vm_map_lock_try(map) 328 vm_map_t map; 329 { 330 boolean_t rv; 331 332 if (map->flags & VM_MAP_INTRSAFE) 333 rv = simple_lock_try(&map->lock.lk_interlock); 334 else { 335 simple_lock(&map->flags_lock); 336 if (map->flags & VM_MAP_BUSY) { 337 simple_unlock(&map->flags_lock); 338 return (FALSE); 339 } 340 rv = (lockmgr(&map->lock, LK_EXCLUSIVE|LK_NOWAIT|LK_INTERLOCK, 341 &map->flags_lock, curproc) == 0); 342 } 343 344 if (rv) 345 map->timestamp++; 346 347 return (rv); 348 } 349 350 static __inline void 351 vm_map_lock(map) 352 vm_map_t map; 353 { 354 int error; 355 356 if (map->flags & VM_MAP_INTRSAFE) { 357 simple_lock(&map->lock.lk_interlock); 358 return; 359 } 360 361 try_again: 362 simple_lock(&map->flags_lock); 363 if (map->flags & VM_MAP_BUSY) { 364 map->flags |= VM_MAP_WANTLOCK; 365 simple_unlock(&map->flags_lock); 366 (void) tsleep(&map->flags, PVM, "vmmapbsy", 0); 367 goto try_again; 368 } 369 370 error = lockmgr(&map->lock, LK_EXCLUSIVE|LK_SLEEPFAIL|LK_INTERLOCK, 371 &map->flags_lock, curproc); 372 373 if (error) { 374 #ifdef DIAGNOSTIC 375 if (error != ENOLCK) 376 panic("vm_map_lock: failed to get lock"); 377 #endif 378 goto try_again; 379 } 380 381 (map)->timestamp++; 382 } 383 384 #ifdef DIAGNOSTIC 385 #define vm_map_lock_read(map) \ 386 do { \ 387 if (map->flags & VM_MAP_INTRSAFE) \ 388 panic("vm_map_lock_read: intrsafe map"); \ 389 (void) lockmgr(&(map)->lock, LK_SHARED, NULL, curproc); \ 390 } while (0) 391 #else 392 #define vm_map_lock_read(map) \ 393 (void) lockmgr(&(map)->lock, LK_SHARED, NULL, curproc) 394 #endif 395 396 #define vm_map_unlock(map) \ 397 do { \ 398 if ((map)->flags & VM_MAP_INTRSAFE) \ 399 simple_unlock(&(map)->lock.lk_interlock); \ 400 else \ 401 (void) lockmgr(&(map)->lock, LK_RELEASE, NULL, curproc);\ 402 } while (0) 403 404 #define vm_map_unlock_read(map) \ 405 (void) lockmgr(&(map)->lock, LK_RELEASE, NULL, curproc) 406 407 #define vm_map_downgrade(map) \ 408 (void) lockmgr(&(map)->lock, LK_DOWNGRADE, NULL, curproc) 409 410 #ifdef DIAGNOSTIC 411 #define vm_map_upgrade(map) \ 412 do { \ 413 if (lockmgr(&(map)->lock, LK_UPGRADE, NULL, curproc) != 0) \ 414 panic("vm_map_upgrade: failed to upgrade lock"); \ 415 } while (0) 416 #else 417 #define vm_map_upgrade(map) \ 418 (void) lockmgr(&(map)->lock, LK_UPGRADE, NULL, curproc) 419 #endif 420 421 #define vm_map_busy(map) \ 422 do { \ 423 simple_lock(&(map)->flags_lock); \ 424 (map)->flags |= VM_MAP_BUSY; \ 425 simple_unlock(&(map)->flags_lock); \ 426 } while (0) 427 428 #define vm_map_unbusy(map) \ 429 do { \ 430 int oflags; \ 431 \ 432 simple_lock(&(map)->flags_lock); \ 433 oflags = (map)->flags; \ 434 (map)->flags &= ~(VM_MAP_BUSY|VM_MAP_WANTLOCK); \ 435 simple_unlock(&(map)->flags_lock); \ 436 if (oflags & VM_MAP_WANTLOCK) \ 437 wakeup(&(map)->flags); \ 438 } while (0) 439 #endif /* _KERNEL */ 440 441 /* 442 * Functions implemented as macros 443 */ 444 #define vm_map_min(map) ((map)->min_offset) 445 #define vm_map_max(map) ((map)->max_offset) 446 #define vm_map_pmap(map) ((map)->pmap) 447 448 /* XXX: number of kernel maps and entries to statically allocate */ 449 #ifndef MAX_KMAP 450 #define MAX_KMAP 20 451 #endif 452 #ifndef MAX_KMAPENT 453 #if (50 + (2 * NPROC) > 1000) 454 #define MAX_KMAPENT (50 + (2 * NPROC)) 455 #else 456 #define MAX_KMAPENT 1000 /* XXXCDC: no crash */ 457 #endif 458 #endif 459 460 /* 461 * handle inline options 462 */ 463 464 #ifdef UVM_MAP_INLINE 465 #define MAP_INLINE static __inline 466 #else 467 #define MAP_INLINE /* nothing */ 468 #endif /* UVM_MAP_INLINE */ 469 470 /* 471 * globals: 472 */ 473 474 #ifdef _KERNEL 475 476 #ifdef PMAP_GROWKERNEL 477 extern vaddr_t uvm_maxkaddr; 478 #endif 479 480 /* 481 * protos: the following prototypes define the interface to vm_map 482 */ 483 484 MAP_INLINE 485 void uvm_map_deallocate __P((vm_map_t)); 486 487 int uvm_map_clean __P((vm_map_t, vaddr_t, vaddr_t, int)); 488 void uvm_map_clip_start __P((vm_map_t, vm_map_entry_t, vaddr_t)); 489 void uvm_map_clip_end __P((vm_map_t, vm_map_entry_t, vaddr_t)); 490 MAP_INLINE 491 vm_map_t uvm_map_create __P((pmap_t, vaddr_t, vaddr_t, int)); 492 int uvm_map_extract __P((vm_map_t, vaddr_t, vsize_t, 493 vm_map_t, vaddr_t *, int)); 494 vm_map_entry_t uvm_map_findspace __P((vm_map_t, vaddr_t, vsize_t, vaddr_t *, 495 struct uvm_object *, voff_t, boolean_t)); 496 int uvm_map_inherit __P((vm_map_t, vaddr_t, vaddr_t, vm_inherit_t)); 497 int uvm_map_advice __P((vm_map_t, vaddr_t, vaddr_t, int)); 498 void uvm_map_init __P((void)); 499 boolean_t uvm_map_lookup_entry __P((vm_map_t, vaddr_t, vm_map_entry_t *)); 500 MAP_INLINE 501 void uvm_map_reference __P((vm_map_t)); 502 int uvm_map_replace __P((vm_map_t, vaddr_t, vaddr_t, 503 vm_map_entry_t, int)); 504 int uvm_map_reserve __P((vm_map_t, vsize_t, vaddr_t, vaddr_t *)); 505 void uvm_map_setup __P((vm_map_t, vaddr_t, vaddr_t, int)); 506 int uvm_map_submap __P((vm_map_t, vaddr_t, vaddr_t, vm_map_t)); 507 MAP_INLINE 508 int uvm_unmap __P((vm_map_t, vaddr_t, vaddr_t)); 509 void uvm_unmap_detach __P((vm_map_entry_t,int)); 510 int uvm_unmap_remove __P((vm_map_t, vaddr_t, vaddr_t, 511 vm_map_entry_t *)); 512 513 #endif /* _KERNEL */ 514 515 #endif /* _UVM_UVM_MAP_H_ */ 516