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