1 /* $NetBSD: uvm_map.c,v 1.161 2004/02/10 01:30:49 matt Exp $ */ 2 3 /* 4 * Copyright (c) 1997 Charles D. Cranor and Washington University. 5 * Copyright (c) 1991, 1993, The Regents of the University of California. 6 * 7 * All rights reserved. 8 * 9 * This code is derived from software contributed to Berkeley by 10 * The Mach Operating System project at Carnegie-Mellon University. 11 * 12 * Redistribution and use in source and binary forms, with or without 13 * modification, are permitted provided that the following conditions 14 * are met: 15 * 1. Redistributions of source code must retain the above copyright 16 * notice, this list of conditions and the following disclaimer. 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in the 19 * documentation and/or other materials provided with the distribution. 20 * 3. All advertising materials mentioning features or use of this software 21 * must display the following acknowledgement: 22 * This product includes software developed by Charles D. Cranor, 23 * Washington University, the University of California, Berkeley and 24 * its contributors. 25 * 4. Neither the name of the University nor the names of its contributors 26 * may be used to endorse or promote products derived from this software 27 * without specific prior written permission. 28 * 29 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 30 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 31 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 32 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 33 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 34 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 35 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 36 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 37 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 38 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 39 * SUCH DAMAGE. 40 * 41 * @(#)vm_map.c 8.3 (Berkeley) 1/12/94 42 * from: Id: uvm_map.c,v 1.1.2.27 1998/02/07 01:16:54 chs Exp 43 * 44 * 45 * Copyright (c) 1987, 1990 Carnegie-Mellon University. 46 * All rights reserved. 47 * 48 * Permission to use, copy, modify and distribute this software and 49 * its documentation is hereby granted, provided that both the copyright 50 * notice and this permission notice appear in all copies of the 51 * software, derivative works or modified versions, and any portions 52 * thereof, and that both notices appear in supporting documentation. 53 * 54 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" 55 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND 56 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. 57 * 58 * Carnegie Mellon requests users of this software to return to 59 * 60 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU 61 * School of Computer Science 62 * Carnegie Mellon University 63 * Pittsburgh PA 15213-3890 64 * 65 * any improvements or extensions that they make and grant Carnegie the 66 * rights to redistribute these changes. 67 */ 68 69 /* 70 * uvm_map.c: uvm map operations 71 */ 72 73 #include <sys/cdefs.h> 74 __KERNEL_RCSID(0, "$NetBSD: uvm_map.c,v 1.161 2004/02/10 01:30:49 matt Exp $"); 75 76 #include "opt_ddb.h" 77 #include "opt_uvmhist.h" 78 #include "opt_sysv.h" 79 80 #include <sys/param.h> 81 #include <sys/systm.h> 82 #include <sys/mman.h> 83 #include <sys/proc.h> 84 #include <sys/malloc.h> 85 #include <sys/pool.h> 86 #include <sys/kernel.h> 87 #include <sys/mount.h> 88 #include <sys/vnode.h> 89 90 #ifdef SYSVSHM 91 #include <sys/shm.h> 92 #endif 93 94 #define UVM_MAP 95 #include <uvm/uvm.h> 96 #undef RB_AUGMENT 97 #define RB_AUGMENT(x) uvm_rb_augment(x) 98 99 #ifdef DDB 100 #include <uvm/uvm_ddb.h> 101 #endif 102 103 extern struct vm_map *pager_map; 104 105 struct uvm_cnt map_ubackmerge, map_uforwmerge; 106 struct uvm_cnt map_ubimerge, map_unomerge; 107 struct uvm_cnt map_kbackmerge, map_kforwmerge; 108 struct uvm_cnt map_kbimerge, map_knomerge; 109 struct uvm_cnt uvm_map_call, uvm_mlk_call, uvm_mlk_hint; 110 const char vmmapbsy[] = "vmmapbsy"; 111 112 /* 113 * pool for vmspace structures. 114 */ 115 116 struct pool uvm_vmspace_pool; 117 118 /* 119 * pool for dynamically-allocated map entries. 120 */ 121 122 struct pool uvm_map_entry_pool; 123 struct pool uvm_map_entry_kmem_pool; 124 125 MALLOC_DEFINE(M_VMMAP, "VM map", "VM map structures"); 126 MALLOC_DEFINE(M_VMPMAP, "VM pmap", "VM pmap"); 127 128 #ifdef PMAP_GROWKERNEL 129 /* 130 * This global represents the end of the kernel virtual address 131 * space. If we want to exceed this, we must grow the kernel 132 * virtual address space dynamically. 133 * 134 * Note, this variable is locked by kernel_map's lock. 135 */ 136 vaddr_t uvm_maxkaddr; 137 #endif 138 139 /* 140 * macros 141 */ 142 143 /* 144 * uvm_map_entry_link: insert entry into a map 145 * 146 * => map must be locked 147 */ 148 #define uvm_map_entry_link(map, after_where, entry) do { \ 149 KASSERT(entry->start < entry->end); \ 150 (map)->nentries++; \ 151 (entry)->prev = (after_where); \ 152 (entry)->next = (after_where)->next; \ 153 (entry)->prev->next = (entry); \ 154 (entry)->next->prev = (entry); \ 155 uvm_rb_insert((map), (entry)); \ 156 } while (/*CONSTCOND*/ 0) 157 158 /* 159 * uvm_map_entry_unlink: remove entry from a map 160 * 161 * => map must be locked 162 */ 163 #define uvm_map_entry_unlink(map, entry) do { \ 164 (map)->nentries--; \ 165 (entry)->next->prev = (entry)->prev; \ 166 (entry)->prev->next = (entry)->next; \ 167 uvm_rb_remove((map), (entry)); \ 168 } while (/*CONSTCOND*/ 0) 169 170 /* 171 * SAVE_HINT: saves the specified entry as the hint for future lookups. 172 * 173 * => map need not be locked (protected by hint_lock). 174 */ 175 #define SAVE_HINT(map,check,value) do { \ 176 simple_lock(&(map)->hint_lock); \ 177 if ((map)->hint == (check)) \ 178 (map)->hint = (value); \ 179 simple_unlock(&(map)->hint_lock); \ 180 } while (/*CONSTCOND*/ 0) 181 182 /* 183 * VM_MAP_RANGE_CHECK: check and correct range 184 * 185 * => map must at least be read locked 186 */ 187 188 #define VM_MAP_RANGE_CHECK(map, start, end) do { \ 189 if (start < vm_map_min(map)) \ 190 start = vm_map_min(map); \ 191 if (end > vm_map_max(map)) \ 192 end = vm_map_max(map); \ 193 if (start > end) \ 194 start = end; \ 195 } while (/*CONSTCOND*/ 0) 196 197 /* 198 * local prototypes 199 */ 200 201 static struct vm_map_entry * 202 uvm_mapent_alloc(struct vm_map *, int); 203 static void uvm_mapent_copy(struct vm_map_entry *, struct vm_map_entry *); 204 static void uvm_mapent_free(struct vm_map_entry *); 205 static void uvm_map_entry_unwire(struct vm_map *, struct vm_map_entry *); 206 static void uvm_map_reference_amap(struct vm_map_entry *, int); 207 static int uvm_map_space_avail(vaddr_t *, vsize_t, voff_t, vsize_t, int, 208 struct vm_map_entry *); 209 static void uvm_map_unreference_amap(struct vm_map_entry *, int); 210 211 int _uvm_tree_sanity(struct vm_map *, const char *); 212 static vsize_t uvm_rb_subtree_space(const struct vm_map_entry *); 213 214 static __inline int 215 uvm_compare(const struct vm_map_entry *a, const struct vm_map_entry *b) 216 { 217 218 if (a->start < b->start) 219 return (-1); 220 else if (a->start > b->start) 221 return (1); 222 223 return (0); 224 } 225 226 static __inline void 227 uvm_rb_augment(struct vm_map_entry *entry) 228 { 229 230 entry->space = uvm_rb_subtree_space(entry); 231 } 232 233 RB_PROTOTYPE(uvm_tree, vm_map_entry, rb_entry, uvm_compare); 234 235 RB_GENERATE(uvm_tree, vm_map_entry, rb_entry, uvm_compare); 236 237 static __inline vsize_t 238 uvm_rb_space(const struct vm_map *map, const struct vm_map_entry *entry) 239 { 240 /* XXX map is not used */ 241 242 KASSERT(entry->next != NULL); 243 return entry->next->start - entry->end; 244 } 245 246 static vsize_t 247 uvm_rb_subtree_space(const struct vm_map_entry *entry) 248 { 249 vaddr_t space, tmp; 250 251 space = entry->ownspace; 252 if (RB_LEFT(entry, rb_entry)) { 253 tmp = RB_LEFT(entry, rb_entry)->space; 254 if (tmp > space) 255 space = tmp; 256 } 257 258 if (RB_RIGHT(entry, rb_entry)) { 259 tmp = RB_RIGHT(entry, rb_entry)->space; 260 if (tmp > space) 261 space = tmp; 262 } 263 264 return (space); 265 } 266 267 static __inline void 268 uvm_rb_fixup(struct vm_map *map, struct vm_map_entry *entry) 269 { 270 /* We need to traverse to the very top */ 271 do { 272 entry->ownspace = uvm_rb_space(map, entry); 273 entry->space = uvm_rb_subtree_space(entry); 274 } while ((entry = RB_PARENT(entry, rb_entry)) != NULL); 275 } 276 277 static __inline void 278 uvm_rb_insert(struct vm_map *map, struct vm_map_entry *entry) 279 { 280 vaddr_t space = uvm_rb_space(map, entry); 281 struct vm_map_entry *tmp; 282 283 entry->ownspace = entry->space = space; 284 tmp = RB_INSERT(uvm_tree, &(map)->rbhead, entry); 285 #ifdef DIAGNOSTIC 286 if (tmp != NULL) 287 panic("uvm_rb_insert: duplicate entry?"); 288 #endif 289 uvm_rb_fixup(map, entry); 290 if (entry->prev != &map->header) 291 uvm_rb_fixup(map, entry->prev); 292 } 293 294 static __inline void 295 uvm_rb_remove(struct vm_map *map, struct vm_map_entry *entry) 296 { 297 struct vm_map_entry *parent; 298 299 parent = RB_PARENT(entry, rb_entry); 300 RB_REMOVE(uvm_tree, &(map)->rbhead, entry); 301 if (entry->prev != &map->header) 302 uvm_rb_fixup(map, entry->prev); 303 if (parent) 304 uvm_rb_fixup(map, parent); 305 } 306 307 #ifdef DEBUG 308 int uvm_debug_check_rbtree = 0; 309 #define uvm_tree_sanity(x,y) \ 310 if (uvm_debug_check_rbtree) \ 311 _uvm_tree_sanity(x,y) 312 #else 313 #define uvm_tree_sanity(x,y) 314 #endif 315 316 int 317 _uvm_tree_sanity(struct vm_map *map, const char *name) 318 { 319 struct vm_map_entry *tmp, *trtmp; 320 int n = 0, i = 1; 321 322 RB_FOREACH(tmp, uvm_tree, &map->rbhead) { 323 if (tmp->ownspace != uvm_rb_space(map, tmp)) { 324 printf("%s: %d/%d ownspace %lx != %lx %s\n", 325 name, n + 1, map->nentries, 326 (ulong)tmp->ownspace, (ulong)uvm_rb_space(map, tmp), 327 tmp->next == &map->header ? "(last)" : ""); 328 goto error; 329 } 330 } 331 trtmp = NULL; 332 RB_FOREACH(tmp, uvm_tree, &map->rbhead) { 333 if (tmp->space != uvm_rb_subtree_space(tmp)) { 334 printf("%s: space %lx != %lx\n", 335 name, (ulong)tmp->space, 336 (ulong)uvm_rb_subtree_space(tmp)); 337 goto error; 338 } 339 if (trtmp != NULL && trtmp->start >= tmp->start) { 340 printf("%s: corrupt: 0x%lx >= 0x%lx\n", 341 name, trtmp->start, tmp->start); 342 goto error; 343 } 344 n++; 345 346 trtmp = tmp; 347 } 348 349 if (n != map->nentries) { 350 printf("%s: nentries: %d vs %d\n", 351 name, n, map->nentries); 352 goto error; 353 } 354 355 for (tmp = map->header.next; tmp && tmp != &map->header; 356 tmp = tmp->next, i++) { 357 trtmp = RB_FIND(uvm_tree, &map->rbhead, tmp); 358 if (trtmp != tmp) { 359 printf("%s: lookup: %d: %p - %p: %p\n", 360 name, i, tmp, trtmp, 361 RB_PARENT(tmp, rb_entry)); 362 goto error; 363 } 364 } 365 366 return (0); 367 error: 368 #ifdef DDB 369 /* handy breakpoint location for error case */ 370 __asm(".globl treesanity_label\ntreesanity_label:"); 371 #endif 372 return (-1); 373 } 374 375 /* 376 * local inlines 377 */ 378 379 /* 380 * uvm_mapent_alloc: allocate a map entry 381 */ 382 383 static __inline struct vm_map_entry * 384 uvm_mapent_alloc(struct vm_map *map, int flags) 385 { 386 struct vm_map_entry *me; 387 int s; 388 int pflags = (flags & UVM_FLAG_NOWAIT) ? PR_NOWAIT : PR_WAITOK; 389 UVMHIST_FUNC("uvm_mapent_alloc"); UVMHIST_CALLED(maphist); 390 391 if (map->flags & VM_MAP_INTRSAFE || cold) { 392 s = splvm(); 393 simple_lock(&uvm.kentry_lock); 394 me = uvm.kentry_free; 395 if (me) 396 uvm.kentry_free = me->next; 397 simple_unlock(&uvm.kentry_lock); 398 splx(s); 399 if (__predict_false(me == NULL)) { 400 panic("uvm_mapent_alloc: out of static map entries, " 401 "check MAX_KMAPENT (currently %d)", 402 MAX_KMAPENT); 403 } 404 me->flags = UVM_MAP_STATIC; 405 } else if (map == kernel_map) { 406 me = pool_get(&uvm_map_entry_kmem_pool, pflags); 407 if (__predict_false(me == NULL)) 408 return NULL; 409 me->flags = UVM_MAP_KMEM; 410 } else { 411 me = pool_get(&uvm_map_entry_pool, pflags); 412 if (__predict_false(me == NULL)) 413 return NULL; 414 me->flags = 0; 415 } 416 417 UVMHIST_LOG(maphist, "<- new entry=0x%x [kentry=%d]", me, 418 ((map->flags & VM_MAP_INTRSAFE) != 0 || map == kernel_map), 0, 0); 419 return (me); 420 } 421 422 /* 423 * uvm_mapent_free: free map entry 424 */ 425 426 static __inline void 427 uvm_mapent_free(struct vm_map_entry *me) 428 { 429 int s; 430 UVMHIST_FUNC("uvm_mapent_free"); UVMHIST_CALLED(maphist); 431 432 UVMHIST_LOG(maphist,"<- freeing map entry=0x%x [flags=%d]", 433 me, me->flags, 0, 0); 434 if (me->flags & UVM_MAP_STATIC) { 435 s = splvm(); 436 simple_lock(&uvm.kentry_lock); 437 me->next = uvm.kentry_free; 438 uvm.kentry_free = me; 439 simple_unlock(&uvm.kentry_lock); 440 splx(s); 441 } else if (me->flags & UVM_MAP_KMEM) { 442 pool_put(&uvm_map_entry_kmem_pool, me); 443 } else { 444 pool_put(&uvm_map_entry_pool, me); 445 } 446 } 447 448 /* 449 * uvm_mapent_copy: copy a map entry, preserving flags 450 */ 451 452 static __inline void 453 uvm_mapent_copy(struct vm_map_entry *src, struct vm_map_entry *dst) 454 { 455 456 memcpy(dst, src, ((char *)&src->uvm_map_entry_stop_copy) - 457 ((char *)src)); 458 } 459 460 /* 461 * uvm_map_entry_unwire: unwire a map entry 462 * 463 * => map should be locked by caller 464 */ 465 466 static __inline void 467 uvm_map_entry_unwire(struct vm_map *map, struct vm_map_entry *entry) 468 { 469 470 entry->wired_count = 0; 471 uvm_fault_unwire_locked(map, entry->start, entry->end); 472 } 473 474 475 /* 476 * wrapper for calling amap_ref() 477 */ 478 static __inline void 479 uvm_map_reference_amap(struct vm_map_entry *entry, int flags) 480 { 481 482 amap_ref(entry->aref.ar_amap, entry->aref.ar_pageoff, 483 (entry->end - entry->start) >> PAGE_SHIFT, flags); 484 } 485 486 487 /* 488 * wrapper for calling amap_unref() 489 */ 490 static __inline void 491 uvm_map_unreference_amap(struct vm_map_entry *entry, int flags) 492 { 493 494 amap_unref(entry->aref.ar_amap, entry->aref.ar_pageoff, 495 (entry->end - entry->start) >> PAGE_SHIFT, flags); 496 } 497 498 499 /* 500 * uvm_map_init: init mapping system at boot time. note that we allocate 501 * and init the static pool of struct vm_map_entry *'s for the kernel here. 502 */ 503 504 void 505 uvm_map_init(void) 506 { 507 static struct vm_map_entry kernel_map_entry[MAX_KMAPENT]; 508 #if defined(UVMHIST) 509 static struct uvm_history_ent maphistbuf[100]; 510 static struct uvm_history_ent pdhistbuf[100]; 511 #endif 512 int lcv; 513 514 /* 515 * first, init logging system. 516 */ 517 518 UVMHIST_FUNC("uvm_map_init"); 519 UVMHIST_INIT_STATIC(maphist, maphistbuf); 520 UVMHIST_INIT_STATIC(pdhist, pdhistbuf); 521 UVMHIST_CALLED(maphist); 522 UVMHIST_LOG(maphist,"<starting uvm map system>", 0, 0, 0, 0); 523 UVMCNT_INIT(uvm_map_call, UVMCNT_CNT, 0, 524 "# uvm_map() successful calls", 0); 525 526 UVMCNT_INIT(map_ubackmerge, UVMCNT_CNT, 0, 527 "# uvm_map() back umerges", 0); 528 UVMCNT_INIT(map_uforwmerge, UVMCNT_CNT, 0, 529 "# uvm_map() forward umerges", 0); 530 UVMCNT_INIT(map_ubimerge, UVMCNT_CNT, 0, 531 "# uvm_map() dual umerge", 0); 532 UVMCNT_INIT(map_unomerge, UVMCNT_CNT, 0, 533 "# uvm_map() no umerge", 0); 534 535 UVMCNT_INIT(map_kbackmerge, UVMCNT_CNT, 0, 536 "# uvm_map() back kmerges", 0); 537 UVMCNT_INIT(map_kforwmerge, UVMCNT_CNT, 0, 538 "# uvm_map() forward kmerges", 0); 539 UVMCNT_INIT(map_kbimerge, UVMCNT_CNT, 0, 540 "# uvm_map() dual kmerge", 0); 541 UVMCNT_INIT(map_knomerge, UVMCNT_CNT, 0, 542 "# uvm_map() no kmerge", 0); 543 544 UVMCNT_INIT(uvm_mlk_call, UVMCNT_CNT, 0, "# map lookup calls", 0); 545 UVMCNT_INIT(uvm_mlk_hint, UVMCNT_CNT, 0, "# map lookup hint hits", 0); 546 547 /* 548 * now set up static pool of kernel map entrys ... 549 */ 550 551 simple_lock_init(&uvm.kentry_lock); 552 uvm.kentry_free = NULL; 553 for (lcv = 0 ; lcv < MAX_KMAPENT ; lcv++) { 554 kernel_map_entry[lcv].next = uvm.kentry_free; 555 uvm.kentry_free = &kernel_map_entry[lcv]; 556 } 557 558 /* 559 * initialize the map-related pools. 560 */ 561 pool_init(&uvm_vmspace_pool, sizeof(struct vmspace), 562 0, 0, 0, "vmsppl", &pool_allocator_nointr); 563 pool_init(&uvm_map_entry_pool, sizeof(struct vm_map_entry), 564 0, 0, 0, "vmmpepl", &pool_allocator_nointr); 565 pool_init(&uvm_map_entry_kmem_pool, sizeof(struct vm_map_entry), 566 0, 0, 0, "vmmpekpl", NULL); 567 } 568 569 /* 570 * clippers 571 */ 572 573 /* 574 * uvm_map_clip_start: ensure that the entry begins at or after 575 * the starting address, if it doesn't we split the entry. 576 * 577 * => caller should use UVM_MAP_CLIP_START macro rather than calling 578 * this directly 579 * => map must be locked by caller 580 */ 581 582 void 583 uvm_map_clip_start(struct vm_map *map, struct vm_map_entry *entry, 584 vaddr_t start) 585 { 586 struct vm_map_entry *new_entry; 587 vaddr_t new_adj; 588 589 /* uvm_map_simplify_entry(map, entry); */ /* XXX */ 590 591 uvm_tree_sanity(map, "clip_start entry"); 592 593 /* 594 * Split off the front portion. note that we must insert the new 595 * entry BEFORE this one, so that this entry has the specified 596 * starting address. 597 */ 598 599 new_entry = uvm_mapent_alloc(map, 0); 600 uvm_mapent_copy(entry, new_entry); /* entry -> new_entry */ 601 602 new_entry->end = start; 603 new_adj = start - new_entry->start; 604 if (entry->object.uvm_obj) 605 entry->offset += new_adj; /* shift start over */ 606 607 /* Does not change order for the RB tree */ 608 entry->start = start; 609 610 if (new_entry->aref.ar_amap) { 611 amap_splitref(&new_entry->aref, &entry->aref, new_adj); 612 } 613 614 uvm_map_entry_link(map, entry->prev, new_entry); 615 616 if (UVM_ET_ISSUBMAP(entry)) { 617 /* ... unlikely to happen, but play it safe */ 618 uvm_map_reference(new_entry->object.sub_map); 619 } else { 620 if (UVM_ET_ISOBJ(entry) && 621 entry->object.uvm_obj->pgops && 622 entry->object.uvm_obj->pgops->pgo_reference) 623 entry->object.uvm_obj->pgops->pgo_reference( 624 entry->object.uvm_obj); 625 } 626 627 uvm_tree_sanity(map, "clip_start leave"); 628 } 629 630 /* 631 * uvm_map_clip_end: ensure that the entry ends at or before 632 * the ending address, if it does't we split the reference 633 * 634 * => caller should use UVM_MAP_CLIP_END macro rather than calling 635 * this directly 636 * => map must be locked by caller 637 */ 638 639 void 640 uvm_map_clip_end(struct vm_map *map, struct vm_map_entry *entry, vaddr_t end) 641 { 642 struct vm_map_entry * new_entry; 643 vaddr_t new_adj; /* #bytes we move start forward */ 644 645 uvm_tree_sanity(map, "clip_end entry"); 646 /* 647 * Create a new entry and insert it 648 * AFTER the specified entry 649 */ 650 651 new_entry = uvm_mapent_alloc(map, 0); 652 uvm_mapent_copy(entry, new_entry); /* entry -> new_entry */ 653 654 new_entry->start = entry->end = end; 655 new_adj = end - entry->start; 656 if (new_entry->object.uvm_obj) 657 new_entry->offset += new_adj; 658 659 if (entry->aref.ar_amap) 660 amap_splitref(&entry->aref, &new_entry->aref, new_adj); 661 662 uvm_rb_fixup(map, entry); 663 664 uvm_map_entry_link(map, entry, new_entry); 665 666 if (UVM_ET_ISSUBMAP(entry)) { 667 /* ... unlikely to happen, but play it safe */ 668 uvm_map_reference(new_entry->object.sub_map); 669 } else { 670 if (UVM_ET_ISOBJ(entry) && 671 entry->object.uvm_obj->pgops && 672 entry->object.uvm_obj->pgops->pgo_reference) 673 entry->object.uvm_obj->pgops->pgo_reference( 674 entry->object.uvm_obj); 675 } 676 677 uvm_tree_sanity(map, "clip_end leave"); 678 } 679 680 681 /* 682 * M A P - m a i n e n t r y p o i n t 683 */ 684 /* 685 * uvm_map: establish a valid mapping in a map 686 * 687 * => assume startp is page aligned. 688 * => assume size is a multiple of PAGE_SIZE. 689 * => assume sys_mmap provides enough of a "hint" to have us skip 690 * over text/data/bss area. 691 * => map must be unlocked (we will lock it) 692 * => <uobj,uoffset> value meanings (4 cases): 693 * [1] <NULL,uoffset> == uoffset is a hint for PMAP_PREFER 694 * [2] <NULL,UVM_UNKNOWN_OFFSET> == don't PMAP_PREFER 695 * [3] <uobj,uoffset> == normal mapping 696 * [4] <uobj,UVM_UNKNOWN_OFFSET> == uvm_map finds offset based on VA 697 * 698 * case [4] is for kernel mappings where we don't know the offset until 699 * we've found a virtual address. note that kernel object offsets are 700 * always relative to vm_map_min(kernel_map). 701 * 702 * => if `align' is non-zero, we try to align the virtual address to 703 * the specified alignment. this is only a hint; if we can't 704 * do it, the address will be unaligned. this is provided as 705 * a mechanism for large pages. 706 * 707 * => XXXCDC: need way to map in external amap? 708 */ 709 710 int 711 uvm_map(struct vm_map *map, vaddr_t *startp /* IN/OUT */, vsize_t size, 712 struct uvm_object *uobj, voff_t uoffset, vsize_t align, uvm_flag_t flags) 713 { 714 struct vm_map_entry *prev_entry, *new_entry; 715 const int amapwaitflag = (flags & UVM_FLAG_NOWAIT) ? 716 AMAP_EXTEND_NOWAIT : 0; 717 vm_prot_t prot = UVM_PROTECTION(flags), maxprot = 718 UVM_MAXPROTECTION(flags); 719 vm_inherit_t inherit = UVM_INHERIT(flags); 720 int advice = UVM_ADVICE(flags); 721 int error, merged = 0, kmap = (vm_map_pmap(map) == pmap_kernel()); 722 UVMHIST_FUNC("uvm_map"); 723 UVMHIST_CALLED(maphist); 724 725 UVMHIST_LOG(maphist, "(map=0x%x, *startp=0x%x, size=%d, flags=0x%x)", 726 map, *startp, size, flags); 727 UVMHIST_LOG(maphist, " uobj/offset 0x%x/%d", uobj, uoffset,0,0); 728 729 /* 730 * detect a popular device driver bug. 731 */ 732 733 KASSERT(doing_shutdown || curlwp != NULL || 734 (map->flags & VM_MAP_INTRSAFE)); 735 736 /* 737 * zero-sized mapping doesn't make any sense. 738 */ 739 KASSERT(size > 0); 740 741 uvm_tree_sanity(map, "map entry"); 742 743 /* 744 * check sanity of protection code 745 */ 746 747 if ((prot & maxprot) != prot) { 748 UVMHIST_LOG(maphist, "<- prot. failure: prot=0x%x, max=0x%x", 749 prot, maxprot,0,0); 750 return EACCES; 751 } 752 753 /* 754 * for pager_map, allocate the new entry first to avoid sleeping 755 * for memory while we have the map locked. 756 */ 757 758 new_entry = NULL; 759 if (map == pager_map) { 760 new_entry = uvm_mapent_alloc(map, (flags & UVM_FLAG_NOWAIT)); 761 if (__predict_false(new_entry == NULL)) 762 return ENOMEM; 763 } 764 765 /* 766 * figure out where to put new VM range 767 */ 768 769 if (vm_map_lock_try(map) == FALSE) { 770 if (flags & UVM_FLAG_TRYLOCK) { 771 if (new_entry) { 772 uvm_mapent_free(new_entry); 773 } 774 return EAGAIN; 775 } 776 vm_map_lock(map); /* could sleep here */ 777 } 778 if ((prev_entry = uvm_map_findspace(map, *startp, size, startp, 779 uobj, uoffset, align, flags)) == NULL) { 780 UVMHIST_LOG(maphist,"<- uvm_map_findspace failed!",0,0,0,0); 781 vm_map_unlock(map); 782 if (new_entry) { 783 uvm_mapent_free(new_entry); 784 } 785 return ENOMEM; 786 } 787 788 #ifdef PMAP_GROWKERNEL 789 /* 790 * If the kernel pmap can't map the requested space, 791 * then allocate more resources for it. 792 */ 793 if (map == kernel_map && uvm_maxkaddr < (*startp + size)) 794 uvm_maxkaddr = pmap_growkernel(*startp + size); 795 #endif 796 797 UVMCNT_INCR(uvm_map_call); 798 799 /* 800 * if uobj is null, then uoffset is either a VAC hint for PMAP_PREFER 801 * [typically from uvm_map_reserve] or it is UVM_UNKNOWN_OFFSET. in 802 * either case we want to zero it before storing it in the map entry 803 * (because it looks strange and confusing when debugging...) 804 * 805 * if uobj is not null 806 * if uoffset is not UVM_UNKNOWN_OFFSET then we have a normal mapping 807 * and we do not need to change uoffset. 808 * if uoffset is UVM_UNKNOWN_OFFSET then we need to find the offset 809 * now (based on the starting address of the map). this case is 810 * for kernel object mappings where we don't know the offset until 811 * the virtual address is found (with uvm_map_findspace). the 812 * offset is the distance we are from the start of the map. 813 */ 814 815 if (uobj == NULL) { 816 uoffset = 0; 817 } else { 818 if (uoffset == UVM_UNKNOWN_OFFSET) { 819 KASSERT(UVM_OBJ_IS_KERN_OBJECT(uobj)); 820 uoffset = *startp - vm_map_min(kernel_map); 821 } 822 } 823 824 /* 825 * try and insert in map by extending previous entry, if possible. 826 * XXX: we don't try and pull back the next entry. might be useful 827 * for a stack, but we are currently allocating our stack in advance. 828 */ 829 830 if (flags & UVM_FLAG_NOMERGE) 831 goto nomerge; 832 833 if (prev_entry->end == *startp && 834 prev_entry != &map->header && 835 prev_entry->object.uvm_obj == uobj) { 836 837 if (prev_entry->flags & UVM_MAP_NOMERGE) 838 goto forwardmerge; 839 840 if (uobj && prev_entry->offset + 841 (prev_entry->end - prev_entry->start) != uoffset) 842 goto forwardmerge; 843 844 if (UVM_ET_ISSUBMAP(prev_entry)) 845 goto forwardmerge; 846 847 if (prev_entry->protection != prot || 848 prev_entry->max_protection != maxprot) 849 goto forwardmerge; 850 851 if (prev_entry->inheritance != inherit || 852 prev_entry->advice != advice) 853 goto forwardmerge; 854 855 /* wiring status must match (new area is unwired) */ 856 if (VM_MAPENT_ISWIRED(prev_entry)) 857 goto forwardmerge; 858 859 /* 860 * can't extend a shared amap. note: no need to lock amap to 861 * look at refs since we don't care about its exact value. 862 * if it is one (i.e. we have only reference) it will stay there 863 */ 864 865 if (prev_entry->aref.ar_amap && 866 amap_refs(prev_entry->aref.ar_amap) != 1) { 867 goto forwardmerge; 868 } 869 870 if (prev_entry->aref.ar_amap) { 871 error = amap_extend(prev_entry, size, 872 amapwaitflag | AMAP_EXTEND_FORWARDS); 873 if (error) { 874 vm_map_unlock(map); 875 if (new_entry) { 876 uvm_mapent_free(new_entry); 877 } 878 return error; 879 } 880 } 881 882 if (kmap) 883 UVMCNT_INCR(map_kbackmerge); 884 else 885 UVMCNT_INCR(map_ubackmerge); 886 UVMHIST_LOG(maphist," starting back merge", 0, 0, 0, 0); 887 888 /* 889 * drop our reference to uobj since we are extending a reference 890 * that we already have (the ref count can not drop to zero). 891 */ 892 893 if (uobj && uobj->pgops->pgo_detach) 894 uobj->pgops->pgo_detach(uobj); 895 896 prev_entry->end += size; 897 uvm_rb_fixup(map, prev_entry); 898 899 uvm_tree_sanity(map, "map backmerged"); 900 901 UVMHIST_LOG(maphist,"<- done (via backmerge)!", 0, 0, 0, 0); 902 if (new_entry) { 903 uvm_mapent_free(new_entry); 904 new_entry = NULL; 905 } 906 merged++; 907 } 908 909 forwardmerge: 910 if (prev_entry->next->start == (*startp + size) && 911 prev_entry->next != &map->header && 912 prev_entry->next->object.uvm_obj == uobj) { 913 914 if (prev_entry->next->flags & UVM_MAP_NOMERGE) 915 goto nomerge; 916 917 if (uobj && prev_entry->next->offset != uoffset + size) 918 goto nomerge; 919 920 if (UVM_ET_ISSUBMAP(prev_entry->next)) 921 goto nomerge; 922 923 if (prev_entry->next->protection != prot || 924 prev_entry->next->max_protection != maxprot) 925 goto nomerge; 926 927 if (prev_entry->next->inheritance != inherit || 928 prev_entry->next->advice != advice) 929 goto nomerge; 930 931 /* wiring status must match (new area is unwired) */ 932 if (VM_MAPENT_ISWIRED(prev_entry->next)) 933 goto nomerge; 934 935 /* 936 * can't extend a shared amap. note: no need to lock amap to 937 * look at refs since we don't care about its exact value. 938 * if it is one (i.e. we have only reference) it will stay there. 939 * 940 * note that we also can't merge two amaps, so if we 941 * merged with the previous entry which has an amap, 942 * and the next entry also has an amap, we give up. 943 * 944 * Interesting cases: 945 * amap, new, amap -> give up second merge (single fwd extend) 946 * amap, new, none -> double forward extend (extend again here) 947 * none, new, amap -> double backward extend (done here) 948 * uobj, new, amap -> single backward extend (done here) 949 * 950 * XXX should we attempt to deal with someone refilling 951 * the deallocated region between two entries that are 952 * backed by the same amap (ie, arefs is 2, "prev" and 953 * "next" refer to it, and adding this allocation will 954 * close the hole, thus restoring arefs to 1 and 955 * deallocating the "next" vm_map_entry)? -- @@@ 956 */ 957 958 if (prev_entry->next->aref.ar_amap && 959 (amap_refs(prev_entry->next->aref.ar_amap) != 1 || 960 (merged && prev_entry->aref.ar_amap))) { 961 goto nomerge; 962 } 963 964 if (merged) { 965 /* 966 * Try to extend the amap of the previous entry to 967 * cover the next entry as well. If it doesn't work 968 * just skip on, don't actually give up, since we've 969 * already completed the back merge. 970 */ 971 if (prev_entry->aref.ar_amap) { 972 if (amap_extend(prev_entry, 973 prev_entry->next->end - 974 prev_entry->next->start, 975 amapwaitflag | AMAP_EXTEND_FORWARDS)) 976 goto nomerge; 977 } 978 979 /* 980 * Try to extend the amap of the *next* entry 981 * back to cover the new allocation *and* the 982 * previous entry as well (the previous merge 983 * didn't have an amap already otherwise we 984 * wouldn't be checking here for an amap). If 985 * it doesn't work just skip on, again, don't 986 * actually give up, since we've already 987 * completed the back merge. 988 */ 989 else if (prev_entry->next->aref.ar_amap) { 990 if (amap_extend(prev_entry->next, 991 prev_entry->end - 992 prev_entry->start, 993 amapwaitflag | AMAP_EXTEND_BACKWARDS)) 994 goto nomerge; 995 } 996 } else { 997 /* 998 * Pull the next entry's amap backwards to cover this 999 * new allocation. 1000 */ 1001 if (prev_entry->next->aref.ar_amap) { 1002 error = amap_extend(prev_entry->next, size, 1003 amapwaitflag | AMAP_EXTEND_BACKWARDS); 1004 if (error) { 1005 vm_map_unlock(map); 1006 if (new_entry) { 1007 uvm_mapent_free(new_entry); 1008 } 1009 return error; 1010 } 1011 } 1012 } 1013 1014 if (merged) { 1015 if (kmap) { 1016 UVMCNT_DECR(map_kbackmerge); 1017 UVMCNT_INCR(map_kbimerge); 1018 } else { 1019 UVMCNT_DECR(map_ubackmerge); 1020 UVMCNT_INCR(map_ubimerge); 1021 } 1022 } else { 1023 if (kmap) 1024 UVMCNT_INCR(map_kforwmerge); 1025 else 1026 UVMCNT_INCR(map_uforwmerge); 1027 } 1028 UVMHIST_LOG(maphist," starting forward merge", 0, 0, 0, 0); 1029 1030 /* 1031 * drop our reference to uobj since we are extending a reference 1032 * that we already have (the ref count can not drop to zero). 1033 * (if merged, we've already detached) 1034 */ 1035 if (uobj && uobj->pgops->pgo_detach && !merged) 1036 uobj->pgops->pgo_detach(uobj); 1037 1038 if (merged) { 1039 struct vm_map_entry *dead = prev_entry->next; 1040 prev_entry->end = dead->end; 1041 uvm_map_entry_unlink(map, dead); 1042 if (dead->aref.ar_amap != NULL) { 1043 prev_entry->aref = dead->aref; 1044 dead->aref.ar_amap = NULL; 1045 } 1046 uvm_mapent_free(dead); 1047 } else { 1048 prev_entry->next->start -= size; 1049 if (prev_entry != &map->header) 1050 uvm_rb_fixup(map, prev_entry); 1051 if (uobj) 1052 prev_entry->next->offset = uoffset; 1053 } 1054 1055 uvm_tree_sanity(map, "map forwardmerged"); 1056 1057 UVMHIST_LOG(maphist,"<- done forwardmerge", 0, 0, 0, 0); 1058 if (new_entry) { 1059 uvm_mapent_free(new_entry); 1060 new_entry = NULL; 1061 } 1062 merged++; 1063 } 1064 1065 nomerge: 1066 if (!merged) { 1067 UVMHIST_LOG(maphist," allocating new map entry", 0, 0, 0, 0); 1068 if (kmap) 1069 UVMCNT_INCR(map_knomerge); 1070 else 1071 UVMCNT_INCR(map_unomerge); 1072 1073 /* 1074 * allocate new entry and link it in. 1075 */ 1076 1077 if (new_entry == NULL) { 1078 new_entry = uvm_mapent_alloc(map, 1079 (flags & UVM_FLAG_NOWAIT)); 1080 if (__predict_false(new_entry == NULL)) { 1081 vm_map_unlock(map); 1082 return ENOMEM; 1083 } 1084 } 1085 new_entry->start = *startp; 1086 new_entry->end = new_entry->start + size; 1087 new_entry->object.uvm_obj = uobj; 1088 new_entry->offset = uoffset; 1089 1090 if (uobj) 1091 new_entry->etype = UVM_ET_OBJ; 1092 else 1093 new_entry->etype = 0; 1094 1095 if (flags & UVM_FLAG_COPYONW) { 1096 new_entry->etype |= UVM_ET_COPYONWRITE; 1097 if ((flags & UVM_FLAG_OVERLAY) == 0) 1098 new_entry->etype |= UVM_ET_NEEDSCOPY; 1099 } 1100 if (flags & UVM_FLAG_NOMERGE) { 1101 new_entry->flags |= UVM_MAP_NOMERGE; 1102 } 1103 1104 new_entry->protection = prot; 1105 new_entry->max_protection = maxprot; 1106 new_entry->inheritance = inherit; 1107 new_entry->wired_count = 0; 1108 new_entry->advice = advice; 1109 if (flags & UVM_FLAG_OVERLAY) { 1110 1111 /* 1112 * to_add: for BSS we overallocate a little since we 1113 * are likely to extend 1114 */ 1115 1116 vaddr_t to_add = (flags & UVM_FLAG_AMAPPAD) ? 1117 UVM_AMAP_CHUNK << PAGE_SHIFT : 0; 1118 struct vm_amap *amap = amap_alloc(size, to_add, 1119 (flags & UVM_FLAG_NOWAIT) ? M_NOWAIT : M_WAITOK); 1120 if (__predict_false(amap == NULL)) { 1121 vm_map_unlock(map); 1122 uvm_mapent_free(new_entry); 1123 return ENOMEM; 1124 } 1125 new_entry->aref.ar_pageoff = 0; 1126 new_entry->aref.ar_amap = amap; 1127 } else { 1128 new_entry->aref.ar_pageoff = 0; 1129 new_entry->aref.ar_amap = NULL; 1130 } 1131 uvm_map_entry_link(map, prev_entry, new_entry); 1132 1133 /* 1134 * Update the free space hint 1135 */ 1136 1137 if ((map->first_free == prev_entry) && 1138 (prev_entry->end >= new_entry->start)) 1139 map->first_free = new_entry; 1140 } 1141 1142 map->size += size; 1143 1144 UVMHIST_LOG(maphist,"<- done!", 0, 0, 0, 0); 1145 vm_map_unlock(map); 1146 return 0; 1147 } 1148 1149 /* 1150 * uvm_map_lookup_entry: find map entry at or before an address 1151 * 1152 * => map must at least be read-locked by caller 1153 * => entry is returned in "entry" 1154 * => return value is true if address is in the returned entry 1155 */ 1156 1157 boolean_t 1158 uvm_map_lookup_entry(struct vm_map *map, vaddr_t address, 1159 struct vm_map_entry **entry /* OUT */) 1160 { 1161 struct vm_map_entry *cur; 1162 boolean_t use_tree = FALSE; 1163 UVMHIST_FUNC("uvm_map_lookup_entry"); 1164 UVMHIST_CALLED(maphist); 1165 1166 UVMHIST_LOG(maphist,"(map=0x%x,addr=0x%x,ent=0x%x)", 1167 map, address, entry, 0); 1168 1169 /* 1170 * start looking either from the head of the 1171 * list, or from the hint. 1172 */ 1173 1174 simple_lock(&map->hint_lock); 1175 cur = map->hint; 1176 simple_unlock(&map->hint_lock); 1177 1178 if (cur == &map->header) 1179 cur = cur->next; 1180 1181 UVMCNT_INCR(uvm_mlk_call); 1182 if (address >= cur->start) { 1183 1184 /* 1185 * go from hint to end of list. 1186 * 1187 * but first, make a quick check to see if 1188 * we are already looking at the entry we 1189 * want (which is usually the case). 1190 * note also that we don't need to save the hint 1191 * here... it is the same hint (unless we are 1192 * at the header, in which case the hint didn't 1193 * buy us anything anyway). 1194 */ 1195 1196 if (cur != &map->header && cur->end > address) { 1197 UVMCNT_INCR(uvm_mlk_hint); 1198 *entry = cur; 1199 UVMHIST_LOG(maphist,"<- got it via hint (0x%x)", 1200 cur, 0, 0, 0); 1201 return (TRUE); 1202 } 1203 1204 if (map->nentries > 30) 1205 use_tree = TRUE; 1206 } else { 1207 1208 /* 1209 * invalid hint. use tree. 1210 */ 1211 use_tree = TRUE; 1212 } 1213 1214 uvm_tree_sanity(map, __func__); 1215 1216 if (use_tree) { 1217 struct vm_map_entry *prev = &map->header; 1218 cur = RB_ROOT(&map->rbhead); 1219 1220 /* 1221 * Simple lookup in the tree. Happens when the hint is 1222 * invalid, or nentries reach a threshold. 1223 */ 1224 while (cur) { 1225 if (address >= cur->start) { 1226 if (address < cur->end) { 1227 *entry = cur; 1228 goto got; 1229 } 1230 prev = cur; 1231 cur = RB_RIGHT(cur, rb_entry); 1232 } else 1233 cur = RB_LEFT(cur, rb_entry); 1234 } 1235 *entry = prev; 1236 goto failed; 1237 } 1238 1239 /* 1240 * search linearly 1241 */ 1242 1243 while (cur != &map->header) { 1244 if (cur->end > address) { 1245 if (address >= cur->start) { 1246 /* 1247 * save this lookup for future 1248 * hints, and return 1249 */ 1250 1251 *entry = cur; 1252 got: 1253 SAVE_HINT(map, map->hint, *entry); 1254 UVMHIST_LOG(maphist,"<- search got it (0x%x)", 1255 cur, 0, 0, 0); 1256 KDASSERT((*entry)->start <= address); 1257 KDASSERT(address < (*entry)->end); 1258 return (TRUE); 1259 } 1260 break; 1261 } 1262 cur = cur->next; 1263 } 1264 *entry = cur->prev; 1265 failed: 1266 SAVE_HINT(map, map->hint, *entry); 1267 UVMHIST_LOG(maphist,"<- failed!",0,0,0,0); 1268 KDASSERT((*entry) == &map->header || (*entry)->end <= address); 1269 KDASSERT((*entry)->next == &map->header || 1270 address < (*entry)->next->start); 1271 return (FALSE); 1272 } 1273 1274 /* 1275 * See if the range between start and start + length fits in the gap 1276 * entry->next->start and entry->end. Returns 1 if fits, 0 if doesn't 1277 * fit, and -1 address wraps around. 1278 */ 1279 static __inline int 1280 uvm_map_space_avail(vaddr_t *start, vsize_t length, voff_t uoffset, 1281 vsize_t align, int topdown, struct vm_map_entry *entry) 1282 { 1283 vaddr_t end; 1284 1285 #ifdef PMAP_PREFER 1286 /* 1287 * push start address forward as needed to avoid VAC alias problems. 1288 * we only do this if a valid offset is specified. 1289 */ 1290 1291 if (uoffset != UVM_UNKNOWN_OFFSET) 1292 PMAP_PREFER(uoffset, start); 1293 #endif 1294 if (align != 0) { 1295 if ((*start & (align - 1)) != 0) { 1296 if (topdown) 1297 *start &= ~(align - 1); 1298 else 1299 *start = roundup(*start, align); 1300 } 1301 /* 1302 * XXX Should we PMAP_PREFER() here again? 1303 */ 1304 } 1305 1306 /* 1307 * Find the end of the proposed new region. Be sure we didn't 1308 * wrap around the address; if so, we lose. Otherwise, if the 1309 * proposed new region fits before the next entry, we win. 1310 */ 1311 1312 end = *start + length; 1313 if (end < *start) 1314 return (-1); 1315 1316 if (entry->next->start >= end && *start >= entry->end) 1317 return (1); 1318 1319 return (0); 1320 } 1321 1322 /* 1323 * uvm_map_findspace: find "length" sized space in "map". 1324 * 1325 * => "hint" is a hint about where we want it, unless FINDSPACE_FIXED is 1326 * set (in which case we insist on using "hint"). 1327 * => "result" is VA returned 1328 * => uobj/uoffset are to be used to handle VAC alignment, if required 1329 * => if `align' is non-zero, we attempt to align to that value. 1330 * => caller must at least have read-locked map 1331 * => returns NULL on failure, or pointer to prev. map entry if success 1332 * => note this is a cross between the old vm_map_findspace and vm_map_find 1333 */ 1334 1335 struct vm_map_entry * 1336 uvm_map_findspace(struct vm_map *map, vaddr_t hint, vsize_t length, 1337 vaddr_t *result /* OUT */, struct uvm_object *uobj, voff_t uoffset, 1338 vsize_t align, int flags) 1339 { 1340 struct vm_map_entry *entry; 1341 struct vm_map_entry *child, *prev, *tmp; 1342 vaddr_t orig_hint; 1343 const int topdown = map->flags & VM_MAP_TOPDOWN; 1344 UVMHIST_FUNC("uvm_map_findspace"); 1345 UVMHIST_CALLED(maphist); 1346 1347 UVMHIST_LOG(maphist, "(map=0x%x, hint=0x%x, len=%d, flags=0x%x)", 1348 map, hint, length, flags); 1349 KASSERT((align & (align - 1)) == 0); 1350 KASSERT((flags & UVM_FLAG_FIXED) == 0 || align == 0); 1351 1352 uvm_tree_sanity(map, "map_findspace entry"); 1353 1354 /* 1355 * remember the original hint. if we are aligning, then we 1356 * may have to try again with no alignment constraint if 1357 * we fail the first time. 1358 */ 1359 1360 orig_hint = hint; 1361 if (hint < map->min_offset) { /* check ranges ... */ 1362 if (flags & UVM_FLAG_FIXED) { 1363 UVMHIST_LOG(maphist,"<- VA below map range",0,0,0,0); 1364 return (NULL); 1365 } 1366 hint = map->min_offset; 1367 } 1368 if (hint > map->max_offset) { 1369 UVMHIST_LOG(maphist,"<- VA 0x%x > range [0x%x->0x%x]", 1370 hint, map->min_offset, map->max_offset, 0); 1371 return (NULL); 1372 } 1373 1374 /* 1375 * Look for the first possible address; if there's already 1376 * something at this address, we have to start after it. 1377 */ 1378 1379 /* 1380 * @@@: there are four, no, eight cases to consider. 1381 * 1382 * 0: found, fixed, bottom up -> fail 1383 * 1: found, fixed, top down -> fail 1384 * 2: found, not fixed, bottom up -> start after entry->end, 1385 * loop up 1386 * 3: found, not fixed, top down -> start before entry->start, 1387 * loop down 1388 * 4: not found, fixed, bottom up -> check entry->next->start, fail 1389 * 5: not found, fixed, top down -> check entry->next->start, fail 1390 * 6: not found, not fixed, bottom up -> check entry->next->start, 1391 * loop up 1392 * 7: not found, not fixed, top down -> check entry->next->start, 1393 * loop down 1394 * 1395 * as you can see, it reduces to roughly five cases, and that 1396 * adding top down mapping only adds one unique case (without 1397 * it, there would be four cases). 1398 */ 1399 1400 if ((flags & UVM_FLAG_FIXED) == 0 && hint == map->min_offset) { 1401 entry = map->first_free; 1402 } else { 1403 if (uvm_map_lookup_entry(map, hint, &entry)) { 1404 /* "hint" address already in use ... */ 1405 if (flags & UVM_FLAG_FIXED) { 1406 UVMHIST_LOG(maphist, "<- fixed & VA in use", 1407 0, 0, 0, 0); 1408 return (NULL); 1409 } 1410 if (topdown) 1411 /* Start from lower gap. */ 1412 entry = entry->prev; 1413 } else if (flags & UVM_FLAG_FIXED) { 1414 if (entry->next->start >= hint + length && 1415 hint + length > hint) 1416 goto found; 1417 1418 /* "hint" address is gap but too small */ 1419 UVMHIST_LOG(maphist, "<- fixed mapping failed", 1420 0, 0, 0, 0); 1421 return (NULL); /* only one shot at it ... */ 1422 } else { 1423 /* 1424 * See if given hint fits in this gap. 1425 */ 1426 switch (uvm_map_space_avail(&hint, length, 1427 uoffset, align, topdown, entry)) { 1428 case 1: 1429 goto found; 1430 case -1: 1431 goto wraparound; 1432 } 1433 1434 if (topdown) { 1435 /* 1436 * Still there is a chance to fit 1437 * if hint > entry->end. 1438 */ 1439 } else { 1440 /* Start from higer gap. */ 1441 entry = entry->next; 1442 if (entry == &map->header) 1443 goto notfound; 1444 goto nextgap; 1445 } 1446 } 1447 } 1448 1449 /* 1450 * Note that all UVM_FLAGS_FIXED case is already handled. 1451 */ 1452 KDASSERT((flags & UVM_FLAG_FIXED) == 0); 1453 1454 /* Try to find the space in the red-black tree */ 1455 1456 /* Check slot before any entry */ 1457 hint = topdown ? entry->next->start - length : entry->end; 1458 switch (uvm_map_space_avail(&hint, length, uoffset, align, 1459 topdown, entry)) { 1460 case 1: 1461 goto found; 1462 case -1: 1463 goto wraparound; 1464 } 1465 1466 nextgap: 1467 KDASSERT((flags & UVM_FLAG_FIXED) == 0); 1468 /* If there is not enough space in the whole tree, we fail */ 1469 tmp = RB_ROOT(&map->rbhead); 1470 if (tmp == NULL || tmp->space < length) 1471 goto notfound; 1472 1473 prev = NULL; /* previous candidate */ 1474 1475 /* Find an entry close to hint that has enough space */ 1476 for (; tmp;) { 1477 KASSERT(tmp->next->start == tmp->end + tmp->ownspace); 1478 if (topdown) { 1479 if (tmp->next->start < hint + length && 1480 (prev == NULL || tmp->end > prev->end)) { 1481 if (tmp->ownspace >= length) 1482 prev = tmp; 1483 else if ((child = RB_LEFT(tmp, rb_entry)) 1484 != NULL && child->space >= length) 1485 prev = tmp; 1486 } 1487 } else { 1488 if (tmp->end >= hint && 1489 (prev == NULL || tmp->end < prev->end)) { 1490 if (tmp->ownspace >= length) 1491 prev = tmp; 1492 else if ((child = RB_RIGHT(tmp, rb_entry)) 1493 != NULL && child->space >= length) 1494 prev = tmp; 1495 } 1496 } 1497 if (tmp->next->start < hint + length) 1498 child = RB_RIGHT(tmp, rb_entry); 1499 else if (tmp->end > hint) 1500 child = RB_LEFT(tmp, rb_entry); 1501 else { 1502 if (tmp->ownspace >= length) 1503 break; 1504 if (topdown) 1505 child = RB_LEFT(tmp, rb_entry); 1506 else 1507 child = RB_RIGHT(tmp, rb_entry); 1508 } 1509 if (child == NULL || child->space < length) 1510 break; 1511 tmp = child; 1512 } 1513 1514 if (tmp != NULL && tmp->start < hint && hint < tmp->next->start) { 1515 /* 1516 * Check if the entry that we found satifies the 1517 * space requirement 1518 */ 1519 if (topdown) { 1520 if (hint > tmp->next->start - length) 1521 hint = tmp->next->start - length; 1522 } else { 1523 if (hint < tmp->end) 1524 hint = tmp->end; 1525 } 1526 switch (uvm_map_space_avail(&hint, length, uoffset, align, 1527 topdown, tmp)) { 1528 case 1: 1529 entry = tmp; 1530 goto found; 1531 case -1: 1532 goto wraparound; 1533 } 1534 if (tmp->ownspace >= length) 1535 goto listsearch; 1536 } 1537 if (prev == NULL) 1538 goto notfound; 1539 1540 if (topdown) { 1541 KASSERT(orig_hint >= prev->next->start - length || 1542 prev->next->start - length > prev->next->start); 1543 hint = prev->next->start - length; 1544 } else { 1545 KASSERT(orig_hint <= prev->end); 1546 hint = prev->end; 1547 } 1548 switch (uvm_map_space_avail(&hint, length, uoffset, align, 1549 topdown, prev)) { 1550 case 1: 1551 entry = prev; 1552 goto found; 1553 case -1: 1554 goto wraparound; 1555 } 1556 if (prev->ownspace >= length) 1557 goto listsearch; 1558 1559 if (topdown) 1560 tmp = RB_LEFT(prev, rb_entry); 1561 else 1562 tmp = RB_RIGHT(prev, rb_entry); 1563 for (;;) { 1564 KASSERT(tmp && tmp->space >= length); 1565 if (topdown) 1566 child = RB_RIGHT(tmp, rb_entry); 1567 else 1568 child = RB_LEFT(tmp, rb_entry); 1569 if (child && child->space >= length) { 1570 tmp = child; 1571 continue; 1572 } 1573 if (tmp->ownspace >= length) 1574 break; 1575 if (topdown) 1576 tmp = RB_LEFT(tmp, rb_entry); 1577 else 1578 tmp = RB_RIGHT(tmp, rb_entry); 1579 } 1580 1581 if (topdown) { 1582 KASSERT(orig_hint >= tmp->next->start - length || 1583 tmp->next->start - length > tmp->next->start); 1584 hint = tmp->next->start - length; 1585 } else { 1586 KASSERT(orig_hint <= tmp->end); 1587 hint = tmp->end; 1588 } 1589 switch (uvm_map_space_avail(&hint, length, uoffset, align, 1590 topdown, tmp)) { 1591 case 1: 1592 entry = tmp; 1593 goto found; 1594 case -1: 1595 goto wraparound; 1596 } 1597 1598 /* 1599 * The tree fails to find an entry because of offset or alignment 1600 * restrictions. Search the list instead. 1601 */ 1602 listsearch: 1603 /* 1604 * Look through the rest of the map, trying to fit a new region in 1605 * the gap between existing regions, or after the very last region. 1606 * note: entry->end = base VA of current gap, 1607 * entry->next->start = VA of end of current gap 1608 */ 1609 1610 for (;;) { 1611 /* Update hint for current gap. */ 1612 hint = topdown ? entry->next->start - length : entry->end; 1613 1614 /* See if it fits. */ 1615 switch (uvm_map_space_avail(&hint, length, uoffset, align, 1616 topdown, entry)) { 1617 case 1: 1618 goto found; 1619 case -1: 1620 goto wraparound; 1621 } 1622 1623 /* Advance to next/previous gap */ 1624 if (topdown) { 1625 if (entry == &map->header) { 1626 UVMHIST_LOG(maphist, "<- failed (off start)", 1627 0,0,0,0); 1628 goto notfound; 1629 } 1630 entry = entry->prev; 1631 } else { 1632 entry = entry->next; 1633 if (entry == &map->header) { 1634 UVMHIST_LOG(maphist, "<- failed (off end)", 1635 0,0,0,0); 1636 goto notfound; 1637 } 1638 } 1639 } 1640 1641 found: 1642 SAVE_HINT(map, map->hint, entry); 1643 *result = hint; 1644 UVMHIST_LOG(maphist,"<- got it! (result=0x%x)", hint, 0,0,0); 1645 KASSERT( topdown || hint >= orig_hint); 1646 KASSERT(!topdown || hint <= orig_hint); 1647 KASSERT(entry->end <= hint); 1648 KASSERT(hint + length <= entry->next->start); 1649 return (entry); 1650 1651 wraparound: 1652 UVMHIST_LOG(maphist, "<- failed (wrap around)", 0,0,0,0); 1653 1654 notfound: 1655 if (align != 0) { 1656 UVMHIST_LOG(maphist, "calling recursively, no align", 1657 0,0,0,0); 1658 return (uvm_map_findspace(map, orig_hint, 1659 length, result, uobj, uoffset, 0, flags)); 1660 } 1661 return (NULL); 1662 } 1663 1664 /* 1665 * U N M A P - m a i n h e l p e r f u n c t i o n s 1666 */ 1667 1668 /* 1669 * uvm_unmap_remove: remove mappings from a vm_map (from "start" up to "stop") 1670 * 1671 * => caller must check alignment and size 1672 * => map must be locked by caller 1673 * => we return a list of map entries that we've remove from the map 1674 * in "entry_list" 1675 */ 1676 1677 void 1678 uvm_unmap_remove(struct vm_map *map, vaddr_t start, vaddr_t end, 1679 struct vm_map_entry **entry_list /* OUT */) 1680 { 1681 struct vm_map_entry *entry, *first_entry, *next; 1682 vaddr_t len; 1683 UVMHIST_FUNC("uvm_unmap_remove"); UVMHIST_CALLED(maphist); 1684 1685 UVMHIST_LOG(maphist,"(map=0x%x, start=0x%x, end=0x%x)", 1686 map, start, end, 0); 1687 VM_MAP_RANGE_CHECK(map, start, end); 1688 1689 uvm_tree_sanity(map, "unmap_remove entry"); 1690 1691 /* 1692 * find first entry 1693 */ 1694 1695 if (uvm_map_lookup_entry(map, start, &first_entry) == TRUE) { 1696 /* clip and go... */ 1697 entry = first_entry; 1698 UVM_MAP_CLIP_START(map, entry, start); 1699 /* critical! prevents stale hint */ 1700 SAVE_HINT(map, entry, entry->prev); 1701 } else { 1702 entry = first_entry->next; 1703 } 1704 1705 /* 1706 * Save the free space hint 1707 */ 1708 1709 if (map->first_free->start >= start) 1710 map->first_free = entry->prev; 1711 1712 /* 1713 * note: we now re-use first_entry for a different task. we remove 1714 * a number of map entries from the map and save them in a linked 1715 * list headed by "first_entry". once we remove them from the map 1716 * the caller should unlock the map and drop the references to the 1717 * backing objects [c.f. uvm_unmap_detach]. the object is to 1718 * separate unmapping from reference dropping. why? 1719 * [1] the map has to be locked for unmapping 1720 * [2] the map need not be locked for reference dropping 1721 * [3] dropping references may trigger pager I/O, and if we hit 1722 * a pager that does synchronous I/O we may have to wait for it. 1723 * [4] we would like all waiting for I/O to occur with maps unlocked 1724 * so that we don't block other threads. 1725 */ 1726 1727 first_entry = NULL; 1728 *entry_list = NULL; 1729 1730 /* 1731 * break up the area into map entry sized regions and unmap. note 1732 * that all mappings have to be removed before we can even consider 1733 * dropping references to amaps or VM objects (otherwise we could end 1734 * up with a mapping to a page on the free list which would be very bad) 1735 */ 1736 1737 while ((entry != &map->header) && (entry->start < end)) { 1738 UVM_MAP_CLIP_END(map, entry, end); 1739 next = entry->next; 1740 len = entry->end - entry->start; 1741 1742 /* 1743 * unwire before removing addresses from the pmap; otherwise 1744 * unwiring will put the entries back into the pmap (XXX). 1745 */ 1746 1747 if (VM_MAPENT_ISWIRED(entry)) { 1748 uvm_map_entry_unwire(map, entry); 1749 } 1750 if ((map->flags & VM_MAP_PAGEABLE) == 0) { 1751 1752 /* 1753 * if the map is non-pageable, any pages mapped there 1754 * must be wired and entered with pmap_kenter_pa(), 1755 * and we should free any such pages immediately. 1756 * this is mostly used for kmem_map and mb_map. 1757 */ 1758 1759 uvm_km_pgremove_intrsafe(entry->start, entry->end); 1760 pmap_kremove(entry->start, len); 1761 } else if (UVM_ET_ISOBJ(entry) && 1762 UVM_OBJ_IS_KERN_OBJECT(entry->object.uvm_obj)) { 1763 KASSERT(vm_map_pmap(map) == pmap_kernel()); 1764 1765 /* 1766 * note: kernel object mappings are currently used in 1767 * two ways: 1768 * [1] "normal" mappings of pages in the kernel object 1769 * [2] uvm_km_valloc'd allocations in which we 1770 * pmap_enter in some non-kernel-object page 1771 * (e.g. vmapbuf). 1772 * 1773 * for case [1], we need to remove the mapping from 1774 * the pmap and then remove the page from the kernel 1775 * object (because, once pages in a kernel object are 1776 * unmapped they are no longer needed, unlike, say, 1777 * a vnode where you might want the data to persist 1778 * until flushed out of a queue). 1779 * 1780 * for case [2], we need to remove the mapping from 1781 * the pmap. there shouldn't be any pages at the 1782 * specified offset in the kernel object [but it 1783 * doesn't hurt to call uvm_km_pgremove just to be 1784 * safe?] 1785 * 1786 * uvm_km_pgremove currently does the following: 1787 * for pages in the kernel object in range: 1788 * - drops the swap slot 1789 * - uvm_pagefree the page 1790 */ 1791 1792 /* 1793 * remove mappings from pmap and drop the pages 1794 * from the object. offsets are always relative 1795 * to vm_map_min(kernel_map). 1796 */ 1797 1798 pmap_remove(pmap_kernel(), entry->start, 1799 entry->start + len); 1800 uvm_km_pgremove(entry->object.uvm_obj, 1801 entry->start - vm_map_min(kernel_map), 1802 entry->end - vm_map_min(kernel_map)); 1803 1804 /* 1805 * null out kernel_object reference, we've just 1806 * dropped it 1807 */ 1808 1809 entry->etype &= ~UVM_ET_OBJ; 1810 entry->object.uvm_obj = NULL; 1811 } else if (UVM_ET_ISOBJ(entry) || entry->aref.ar_amap) { 1812 1813 /* 1814 * remove mappings the standard way. 1815 */ 1816 1817 pmap_remove(map->pmap, entry->start, entry->end); 1818 } 1819 1820 /* 1821 * remove entry from map and put it on our list of entries 1822 * that we've nuked. then go to next entry. 1823 */ 1824 1825 UVMHIST_LOG(maphist, " removed map entry 0x%x", entry, 0, 0,0); 1826 1827 /* critical! prevents stale hint */ 1828 SAVE_HINT(map, entry, entry->prev); 1829 1830 uvm_map_entry_unlink(map, entry); 1831 KASSERT(map->size >= len); 1832 map->size -= len; 1833 entry->prev = NULL; 1834 entry->next = first_entry; 1835 first_entry = entry; 1836 entry = next; 1837 } 1838 if ((map->flags & VM_MAP_DYING) == 0) { 1839 pmap_update(vm_map_pmap(map)); 1840 } 1841 1842 uvm_tree_sanity(map, "unmap_remove leave"); 1843 1844 /* 1845 * now we've cleaned up the map and are ready for the caller to drop 1846 * references to the mapped objects. 1847 */ 1848 1849 *entry_list = first_entry; 1850 UVMHIST_LOG(maphist,"<- done!", 0, 0, 0, 0); 1851 } 1852 1853 /* 1854 * uvm_unmap_detach: drop references in a chain of map entries 1855 * 1856 * => we will free the map entries as we traverse the list. 1857 */ 1858 1859 void 1860 uvm_unmap_detach(struct vm_map_entry *first_entry, int flags) 1861 { 1862 struct vm_map_entry *next_entry; 1863 UVMHIST_FUNC("uvm_unmap_detach"); UVMHIST_CALLED(maphist); 1864 1865 while (first_entry) { 1866 KASSERT(!VM_MAPENT_ISWIRED(first_entry)); 1867 UVMHIST_LOG(maphist, 1868 " detach 0x%x: amap=0x%x, obj=0x%x, submap?=%d", 1869 first_entry, first_entry->aref.ar_amap, 1870 first_entry->object.uvm_obj, 1871 UVM_ET_ISSUBMAP(first_entry)); 1872 1873 /* 1874 * drop reference to amap, if we've got one 1875 */ 1876 1877 if (first_entry->aref.ar_amap) 1878 uvm_map_unreference_amap(first_entry, flags); 1879 1880 /* 1881 * drop reference to our backing object, if we've got one 1882 */ 1883 1884 KASSERT(!UVM_ET_ISSUBMAP(first_entry)); 1885 if (UVM_ET_ISOBJ(first_entry) && 1886 first_entry->object.uvm_obj->pgops->pgo_detach) { 1887 (*first_entry->object.uvm_obj->pgops->pgo_detach) 1888 (first_entry->object.uvm_obj); 1889 } 1890 next_entry = first_entry->next; 1891 uvm_mapent_free(first_entry); 1892 first_entry = next_entry; 1893 } 1894 UVMHIST_LOG(maphist, "<- done", 0,0,0,0); 1895 } 1896 1897 /* 1898 * E X T R A C T I O N F U N C T I O N S 1899 */ 1900 1901 /* 1902 * uvm_map_reserve: reserve space in a vm_map for future use. 1903 * 1904 * => we reserve space in a map by putting a dummy map entry in the 1905 * map (dummy means obj=NULL, amap=NULL, prot=VM_PROT_NONE) 1906 * => map should be unlocked (we will write lock it) 1907 * => we return true if we were able to reserve space 1908 * => XXXCDC: should be inline? 1909 */ 1910 1911 int 1912 uvm_map_reserve(struct vm_map *map, vsize_t size, 1913 vaddr_t offset /* hint for pmap_prefer */, 1914 vsize_t align /* alignment hint */, 1915 vaddr_t *raddr /* IN:hint, OUT: reserved VA */) 1916 { 1917 UVMHIST_FUNC("uvm_map_reserve"); UVMHIST_CALLED(maphist); 1918 1919 UVMHIST_LOG(maphist, "(map=0x%x, size=0x%x, offset=0x%x,addr=0x%x)", 1920 map,size,offset,raddr); 1921 1922 size = round_page(size); 1923 if (*raddr < vm_map_min(map)) 1924 *raddr = vm_map_min(map); /* hint */ 1925 1926 /* 1927 * reserve some virtual space. 1928 */ 1929 1930 if (uvm_map(map, raddr, size, NULL, offset, 0, 1931 UVM_MAPFLAG(UVM_PROT_NONE, UVM_PROT_NONE, UVM_INH_NONE, 1932 UVM_ADV_RANDOM, UVM_FLAG_NOMERGE)) != 0) { 1933 UVMHIST_LOG(maphist, "<- done (no VM)", 0,0,0,0); 1934 return (FALSE); 1935 } 1936 1937 UVMHIST_LOG(maphist, "<- done (*raddr=0x%x)", *raddr,0,0,0); 1938 return (TRUE); 1939 } 1940 1941 /* 1942 * uvm_map_replace: replace a reserved (blank) area of memory with 1943 * real mappings. 1944 * 1945 * => caller must WRITE-LOCK the map 1946 * => we return TRUE if replacement was a success 1947 * => we expect the newents chain to have nnewents entrys on it and 1948 * we expect newents->prev to point to the last entry on the list 1949 * => note newents is allowed to be NULL 1950 */ 1951 1952 int 1953 uvm_map_replace(struct vm_map *map, vaddr_t start, vaddr_t end, 1954 struct vm_map_entry *newents, int nnewents) 1955 { 1956 struct vm_map_entry *oldent, *last; 1957 1958 uvm_tree_sanity(map, "map_replace entry"); 1959 1960 /* 1961 * first find the blank map entry at the specified address 1962 */ 1963 1964 if (!uvm_map_lookup_entry(map, start, &oldent)) { 1965 return (FALSE); 1966 } 1967 1968 /* 1969 * check to make sure we have a proper blank entry 1970 */ 1971 1972 if (oldent->start != start || oldent->end != end || 1973 oldent->object.uvm_obj != NULL || oldent->aref.ar_amap != NULL) { 1974 return (FALSE); 1975 } 1976 1977 #ifdef DIAGNOSTIC 1978 1979 /* 1980 * sanity check the newents chain 1981 */ 1982 1983 { 1984 struct vm_map_entry *tmpent = newents; 1985 int nent = 0; 1986 vaddr_t cur = start; 1987 1988 while (tmpent) { 1989 nent++; 1990 if (tmpent->start < cur) 1991 panic("uvm_map_replace1"); 1992 if (tmpent->start > tmpent->end || tmpent->end > end) { 1993 printf("tmpent->start=0x%lx, tmpent->end=0x%lx, end=0x%lx\n", 1994 tmpent->start, tmpent->end, end); 1995 panic("uvm_map_replace2"); 1996 } 1997 cur = tmpent->end; 1998 if (tmpent->next) { 1999 if (tmpent->next->prev != tmpent) 2000 panic("uvm_map_replace3"); 2001 } else { 2002 if (newents->prev != tmpent) 2003 panic("uvm_map_replace4"); 2004 } 2005 tmpent = tmpent->next; 2006 } 2007 if (nent != nnewents) 2008 panic("uvm_map_replace5"); 2009 } 2010 #endif 2011 2012 /* 2013 * map entry is a valid blank! replace it. (this does all the 2014 * work of map entry link/unlink...). 2015 */ 2016 2017 if (newents) { 2018 last = newents->prev; 2019 2020 /* critical: flush stale hints out of map */ 2021 SAVE_HINT(map, map->hint, newents); 2022 if (map->first_free == oldent) 2023 map->first_free = last; 2024 2025 last->next = oldent->next; 2026 last->next->prev = last; 2027 2028 /* Fix RB tree */ 2029 uvm_rb_remove(map, oldent); 2030 2031 newents->prev = oldent->prev; 2032 newents->prev->next = newents; 2033 map->nentries = map->nentries + (nnewents - 1); 2034 2035 /* Fixup the RB tree */ 2036 { 2037 int i; 2038 struct vm_map_entry *tmp; 2039 2040 tmp = newents; 2041 for (i = 0; i < nnewents && tmp; i++) { 2042 uvm_rb_insert(map, tmp); 2043 tmp = tmp->next; 2044 } 2045 } 2046 } else { 2047 2048 /* critical: flush stale hints out of map */ 2049 SAVE_HINT(map, map->hint, oldent->prev); 2050 if (map->first_free == oldent) 2051 map->first_free = oldent->prev; 2052 2053 /* NULL list of new entries: just remove the old one */ 2054 uvm_map_entry_unlink(map, oldent); 2055 } 2056 2057 uvm_tree_sanity(map, "map_replace leave"); 2058 2059 /* 2060 * now we can free the old blank entry, unlock the map and return. 2061 */ 2062 2063 uvm_mapent_free(oldent); 2064 return (TRUE); 2065 } 2066 2067 /* 2068 * uvm_map_extract: extract a mapping from a map and put it somewhere 2069 * (maybe removing the old mapping) 2070 * 2071 * => maps should be unlocked (we will write lock them) 2072 * => returns 0 on success, error code otherwise 2073 * => start must be page aligned 2074 * => len must be page sized 2075 * => flags: 2076 * UVM_EXTRACT_REMOVE: remove mappings from srcmap 2077 * UVM_EXTRACT_CONTIG: abort if unmapped area (advisory only) 2078 * UVM_EXTRACT_QREF: for a temporary extraction do quick obj refs 2079 * UVM_EXTRACT_FIXPROT: set prot to maxprot as we go 2080 * >>>NOTE: if you set REMOVE, you are not allowed to use CONTIG or QREF!<<< 2081 * >>>NOTE: QREF's must be unmapped via the QREF path, thus should only 2082 * be used from within the kernel in a kernel level map <<< 2083 */ 2084 2085 int 2086 uvm_map_extract(struct vm_map *srcmap, vaddr_t start, vsize_t len, 2087 struct vm_map *dstmap, vaddr_t *dstaddrp, int flags) 2088 { 2089 vaddr_t dstaddr, end, newend, oldoffset, fudge, orig_fudge, 2090 oldstart; 2091 struct vm_map_entry *chain, *endchain, *entry, *orig_entry, *newentry, 2092 *deadentry, *oldentry; 2093 vsize_t elen; 2094 int nchain, error, copy_ok; 2095 UVMHIST_FUNC("uvm_map_extract"); UVMHIST_CALLED(maphist); 2096 2097 UVMHIST_LOG(maphist,"(srcmap=0x%x,start=0x%x, len=0x%x", srcmap, start, 2098 len,0); 2099 UVMHIST_LOG(maphist," ...,dstmap=0x%x, flags=0x%x)", dstmap,flags,0,0); 2100 2101 uvm_tree_sanity(srcmap, "map_extract src enter"); 2102 uvm_tree_sanity(dstmap, "map_extract dst enter"); 2103 2104 /* 2105 * step 0: sanity check: start must be on a page boundary, length 2106 * must be page sized. can't ask for CONTIG/QREF if you asked for 2107 * REMOVE. 2108 */ 2109 2110 KASSERT((start & PAGE_MASK) == 0 && (len & PAGE_MASK) == 0); 2111 KASSERT((flags & UVM_EXTRACT_REMOVE) == 0 || 2112 (flags & (UVM_EXTRACT_CONTIG|UVM_EXTRACT_QREF)) == 0); 2113 2114 /* 2115 * step 1: reserve space in the target map for the extracted area 2116 */ 2117 2118 dstaddr = vm_map_min(dstmap); 2119 if (uvm_map_reserve(dstmap, len, start, 0, &dstaddr) == FALSE) 2120 return (ENOMEM); 2121 *dstaddrp = dstaddr; /* pass address back to caller */ 2122 UVMHIST_LOG(maphist, " dstaddr=0x%x", dstaddr,0,0,0); 2123 2124 /* 2125 * step 2: setup for the extraction process loop by init'ing the 2126 * map entry chain, locking src map, and looking up the first useful 2127 * entry in the map. 2128 */ 2129 2130 end = start + len; 2131 newend = dstaddr + len; 2132 chain = endchain = NULL; 2133 nchain = 0; 2134 vm_map_lock(srcmap); 2135 2136 if (uvm_map_lookup_entry(srcmap, start, &entry)) { 2137 2138 /* "start" is within an entry */ 2139 if (flags & UVM_EXTRACT_QREF) { 2140 2141 /* 2142 * for quick references we don't clip the entry, so 2143 * the entry may map space "before" the starting 2144 * virtual address... this is the "fudge" factor 2145 * (which can be non-zero only the first time 2146 * through the "while" loop in step 3). 2147 */ 2148 2149 fudge = start - entry->start; 2150 } else { 2151 2152 /* 2153 * normal reference: we clip the map to fit (thus 2154 * fudge is zero) 2155 */ 2156 2157 UVM_MAP_CLIP_START(srcmap, entry, start); 2158 SAVE_HINT(srcmap, srcmap->hint, entry->prev); 2159 fudge = 0; 2160 } 2161 } else { 2162 2163 /* "start" is not within an entry ... skip to next entry */ 2164 if (flags & UVM_EXTRACT_CONTIG) { 2165 error = EINVAL; 2166 goto bad; /* definite hole here ... */ 2167 } 2168 2169 entry = entry->next; 2170 fudge = 0; 2171 } 2172 2173 /* save values from srcmap for step 6 */ 2174 orig_entry = entry; 2175 orig_fudge = fudge; 2176 2177 /* 2178 * step 3: now start looping through the map entries, extracting 2179 * as we go. 2180 */ 2181 2182 while (entry->start < end && entry != &srcmap->header) { 2183 2184 /* if we are not doing a quick reference, clip it */ 2185 if ((flags & UVM_EXTRACT_QREF) == 0) 2186 UVM_MAP_CLIP_END(srcmap, entry, end); 2187 2188 /* clear needs_copy (allow chunking) */ 2189 if (UVM_ET_ISNEEDSCOPY(entry)) { 2190 if (fudge) 2191 oldstart = entry->start; 2192 else 2193 oldstart = 0; /* XXX: gcc */ 2194 amap_copy(srcmap, entry, M_NOWAIT, TRUE, start, end); 2195 if (UVM_ET_ISNEEDSCOPY(entry)) { /* failed? */ 2196 error = ENOMEM; 2197 goto bad; 2198 } 2199 2200 /* amap_copy could clip (during chunk)! update fudge */ 2201 if (fudge) { 2202 fudge = fudge - (entry->start - oldstart); 2203 orig_fudge = fudge; 2204 } 2205 } 2206 2207 /* calculate the offset of this from "start" */ 2208 oldoffset = (entry->start + fudge) - start; 2209 2210 /* allocate a new map entry */ 2211 newentry = uvm_mapent_alloc(dstmap, 0); 2212 if (newentry == NULL) { 2213 error = ENOMEM; 2214 goto bad; 2215 } 2216 2217 /* set up new map entry */ 2218 newentry->next = NULL; 2219 newentry->prev = endchain; 2220 newentry->start = dstaddr + oldoffset; 2221 newentry->end = 2222 newentry->start + (entry->end - (entry->start + fudge)); 2223 if (newentry->end > newend || newentry->end < newentry->start) 2224 newentry->end = newend; 2225 newentry->object.uvm_obj = entry->object.uvm_obj; 2226 if (newentry->object.uvm_obj) { 2227 if (newentry->object.uvm_obj->pgops->pgo_reference) 2228 newentry->object.uvm_obj->pgops-> 2229 pgo_reference(newentry->object.uvm_obj); 2230 newentry->offset = entry->offset + fudge; 2231 } else { 2232 newentry->offset = 0; 2233 } 2234 newentry->etype = entry->etype; 2235 newentry->protection = (flags & UVM_EXTRACT_FIXPROT) ? 2236 entry->max_protection : entry->protection; 2237 newentry->max_protection = entry->max_protection; 2238 newentry->inheritance = entry->inheritance; 2239 newentry->wired_count = 0; 2240 newentry->aref.ar_amap = entry->aref.ar_amap; 2241 if (newentry->aref.ar_amap) { 2242 newentry->aref.ar_pageoff = 2243 entry->aref.ar_pageoff + (fudge >> PAGE_SHIFT); 2244 uvm_map_reference_amap(newentry, AMAP_SHARED | 2245 ((flags & UVM_EXTRACT_QREF) ? AMAP_REFALL : 0)); 2246 } else { 2247 newentry->aref.ar_pageoff = 0; 2248 } 2249 newentry->advice = entry->advice; 2250 2251 /* now link it on the chain */ 2252 nchain++; 2253 if (endchain == NULL) { 2254 chain = endchain = newentry; 2255 } else { 2256 endchain->next = newentry; 2257 endchain = newentry; 2258 } 2259 2260 /* end of 'while' loop! */ 2261 if ((flags & UVM_EXTRACT_CONTIG) && entry->end < end && 2262 (entry->next == &srcmap->header || 2263 entry->next->start != entry->end)) { 2264 error = EINVAL; 2265 goto bad; 2266 } 2267 entry = entry->next; 2268 fudge = 0; 2269 } 2270 2271 /* 2272 * step 4: close off chain (in format expected by uvm_map_replace) 2273 */ 2274 2275 if (chain) 2276 chain->prev = endchain; 2277 2278 /* 2279 * step 5: attempt to lock the dest map so we can pmap_copy. 2280 * note usage of copy_ok: 2281 * 1 => dstmap locked, pmap_copy ok, and we "replace" here (step 5) 2282 * 0 => dstmap unlocked, NO pmap_copy, and we will "replace" in step 7 2283 */ 2284 2285 if (srcmap == dstmap || vm_map_lock_try(dstmap) == TRUE) { 2286 copy_ok = 1; 2287 if (!uvm_map_replace(dstmap, dstaddr, dstaddr+len, chain, 2288 nchain)) { 2289 if (srcmap != dstmap) 2290 vm_map_unlock(dstmap); 2291 error = EIO; 2292 goto bad; 2293 } 2294 } else { 2295 copy_ok = 0; 2296 /* replace defered until step 7 */ 2297 } 2298 2299 /* 2300 * step 6: traverse the srcmap a second time to do the following: 2301 * - if we got a lock on the dstmap do pmap_copy 2302 * - if UVM_EXTRACT_REMOVE remove the entries 2303 * we make use of orig_entry and orig_fudge (saved in step 2) 2304 */ 2305 2306 if (copy_ok || (flags & UVM_EXTRACT_REMOVE)) { 2307 2308 /* purge possible stale hints from srcmap */ 2309 if (flags & UVM_EXTRACT_REMOVE) { 2310 SAVE_HINT(srcmap, srcmap->hint, orig_entry->prev); 2311 if (srcmap->first_free->start >= start) 2312 srcmap->first_free = orig_entry->prev; 2313 } 2314 2315 entry = orig_entry; 2316 fudge = orig_fudge; 2317 deadentry = NULL; /* for UVM_EXTRACT_REMOVE */ 2318 2319 while (entry->start < end && entry != &srcmap->header) { 2320 if (copy_ok) { 2321 oldoffset = (entry->start + fudge) - start; 2322 elen = MIN(end, entry->end) - 2323 (entry->start + fudge); 2324 pmap_copy(dstmap->pmap, srcmap->pmap, 2325 dstaddr + oldoffset, elen, 2326 entry->start + fudge); 2327 } 2328 2329 /* we advance "entry" in the following if statement */ 2330 if (flags & UVM_EXTRACT_REMOVE) { 2331 pmap_remove(srcmap->pmap, entry->start, 2332 entry->end); 2333 oldentry = entry; /* save entry */ 2334 entry = entry->next; /* advance */ 2335 uvm_map_entry_unlink(srcmap, oldentry); 2336 /* add to dead list */ 2337 oldentry->next = deadentry; 2338 deadentry = oldentry; 2339 } else { 2340 entry = entry->next; /* advance */ 2341 } 2342 2343 /* end of 'while' loop */ 2344 fudge = 0; 2345 } 2346 pmap_update(srcmap->pmap); 2347 2348 /* 2349 * unlock dstmap. we will dispose of deadentry in 2350 * step 7 if needed 2351 */ 2352 2353 if (copy_ok && srcmap != dstmap) 2354 vm_map_unlock(dstmap); 2355 2356 } else { 2357 deadentry = NULL; 2358 } 2359 2360 /* 2361 * step 7: we are done with the source map, unlock. if copy_ok 2362 * is 0 then we have not replaced the dummy mapping in dstmap yet 2363 * and we need to do so now. 2364 */ 2365 2366 vm_map_unlock(srcmap); 2367 if ((flags & UVM_EXTRACT_REMOVE) && deadentry) 2368 uvm_unmap_detach(deadentry, 0); /* dispose of old entries */ 2369 2370 /* now do the replacement if we didn't do it in step 5 */ 2371 if (copy_ok == 0) { 2372 vm_map_lock(dstmap); 2373 error = uvm_map_replace(dstmap, dstaddr, dstaddr+len, chain, 2374 nchain); 2375 vm_map_unlock(dstmap); 2376 2377 if (error == FALSE) { 2378 error = EIO; 2379 goto bad2; 2380 } 2381 } 2382 2383 uvm_tree_sanity(srcmap, "map_extract src leave"); 2384 uvm_tree_sanity(dstmap, "map_extract dst leave"); 2385 2386 return (0); 2387 2388 /* 2389 * bad: failure recovery 2390 */ 2391 bad: 2392 vm_map_unlock(srcmap); 2393 bad2: /* src already unlocked */ 2394 if (chain) 2395 uvm_unmap_detach(chain, 2396 (flags & UVM_EXTRACT_QREF) ? AMAP_REFALL : 0); 2397 2398 uvm_tree_sanity(srcmap, "map_extract src err leave"); 2399 uvm_tree_sanity(dstmap, "map_extract dst err leave"); 2400 2401 uvm_unmap(dstmap, dstaddr, dstaddr+len); /* ??? */ 2402 return (error); 2403 } 2404 2405 /* end of extraction functions */ 2406 2407 /* 2408 * uvm_map_submap: punch down part of a map into a submap 2409 * 2410 * => only the kernel_map is allowed to be submapped 2411 * => the purpose of submapping is to break up the locking granularity 2412 * of a larger map 2413 * => the range specified must have been mapped previously with a uvm_map() 2414 * call [with uobj==NULL] to create a blank map entry in the main map. 2415 * [And it had better still be blank!] 2416 * => maps which contain submaps should never be copied or forked. 2417 * => to remove a submap, use uvm_unmap() on the main map 2418 * and then uvm_map_deallocate() the submap. 2419 * => main map must be unlocked. 2420 * => submap must have been init'd and have a zero reference count. 2421 * [need not be locked as we don't actually reference it] 2422 */ 2423 2424 int 2425 uvm_map_submap(struct vm_map *map, vaddr_t start, vaddr_t end, 2426 struct vm_map *submap) 2427 { 2428 struct vm_map_entry *entry; 2429 int error; 2430 2431 vm_map_lock(map); 2432 VM_MAP_RANGE_CHECK(map, start, end); 2433 2434 if (uvm_map_lookup_entry(map, start, &entry)) { 2435 UVM_MAP_CLIP_START(map, entry, start); 2436 UVM_MAP_CLIP_END(map, entry, end); /* to be safe */ 2437 } else { 2438 entry = NULL; 2439 } 2440 2441 if (entry != NULL && 2442 entry->start == start && entry->end == end && 2443 entry->object.uvm_obj == NULL && entry->aref.ar_amap == NULL && 2444 !UVM_ET_ISCOPYONWRITE(entry) && !UVM_ET_ISNEEDSCOPY(entry)) { 2445 entry->etype |= UVM_ET_SUBMAP; 2446 entry->object.sub_map = submap; 2447 entry->offset = 0; 2448 uvm_map_reference(submap); 2449 error = 0; 2450 } else { 2451 error = EINVAL; 2452 } 2453 vm_map_unlock(map); 2454 return error; 2455 } 2456 2457 2458 /* 2459 * uvm_map_protect: change map protection 2460 * 2461 * => set_max means set max_protection. 2462 * => map must be unlocked. 2463 */ 2464 2465 #define MASK(entry) (UVM_ET_ISCOPYONWRITE(entry) ? \ 2466 ~VM_PROT_WRITE : VM_PROT_ALL) 2467 2468 int 2469 uvm_map_protect(struct vm_map *map, vaddr_t start, vaddr_t end, 2470 vm_prot_t new_prot, boolean_t set_max) 2471 { 2472 struct vm_map_entry *current, *entry; 2473 int error = 0; 2474 UVMHIST_FUNC("uvm_map_protect"); UVMHIST_CALLED(maphist); 2475 UVMHIST_LOG(maphist,"(map=0x%x,start=0x%x,end=0x%x,new_prot=0x%x)", 2476 map, start, end, new_prot); 2477 2478 vm_map_lock(map); 2479 VM_MAP_RANGE_CHECK(map, start, end); 2480 if (uvm_map_lookup_entry(map, start, &entry)) { 2481 UVM_MAP_CLIP_START(map, entry, start); 2482 } else { 2483 entry = entry->next; 2484 } 2485 2486 /* 2487 * make a first pass to check for protection violations. 2488 */ 2489 2490 current = entry; 2491 while ((current != &map->header) && (current->start < end)) { 2492 if (UVM_ET_ISSUBMAP(current)) { 2493 error = EINVAL; 2494 goto out; 2495 } 2496 if ((new_prot & current->max_protection) != new_prot) { 2497 error = EACCES; 2498 goto out; 2499 } 2500 /* 2501 * Don't allow VM_PROT_EXECUTE to be set on entries that 2502 * point to vnodes that are associated with a NOEXEC file 2503 * system. 2504 */ 2505 if (UVM_ET_ISOBJ(current) && 2506 UVM_OBJ_IS_VNODE(current->object.uvm_obj)) { 2507 struct vnode *vp = 2508 (struct vnode *) current->object.uvm_obj; 2509 2510 if ((new_prot & VM_PROT_EXECUTE) != 0 && 2511 (vp->v_mount->mnt_flag & MNT_NOEXEC) != 0) { 2512 error = EACCES; 2513 goto out; 2514 } 2515 } 2516 current = current->next; 2517 } 2518 2519 /* go back and fix up protections (no need to clip this time). */ 2520 2521 current = entry; 2522 while ((current != &map->header) && (current->start < end)) { 2523 vm_prot_t old_prot; 2524 2525 UVM_MAP_CLIP_END(map, current, end); 2526 old_prot = current->protection; 2527 if (set_max) 2528 current->protection = 2529 (current->max_protection = new_prot) & old_prot; 2530 else 2531 current->protection = new_prot; 2532 2533 /* 2534 * update physical map if necessary. worry about copy-on-write 2535 * here -- CHECK THIS XXX 2536 */ 2537 2538 if (current->protection != old_prot) { 2539 /* update pmap! */ 2540 pmap_protect(map->pmap, current->start, current->end, 2541 current->protection & MASK(entry)); 2542 2543 /* 2544 * If this entry points at a vnode, and the 2545 * protection includes VM_PROT_EXECUTE, mark 2546 * the vnode as VEXECMAP. 2547 */ 2548 if (UVM_ET_ISOBJ(current)) { 2549 struct uvm_object *uobj = 2550 current->object.uvm_obj; 2551 2552 if (UVM_OBJ_IS_VNODE(uobj) && 2553 (current->protection & VM_PROT_EXECUTE)) 2554 vn_markexec((struct vnode *) uobj); 2555 } 2556 } 2557 2558 /* 2559 * If the map is configured to lock any future mappings, 2560 * wire this entry now if the old protection was VM_PROT_NONE 2561 * and the new protection is not VM_PROT_NONE. 2562 */ 2563 2564 if ((map->flags & VM_MAP_WIREFUTURE) != 0 && 2565 VM_MAPENT_ISWIRED(entry) == 0 && 2566 old_prot == VM_PROT_NONE && 2567 new_prot != VM_PROT_NONE) { 2568 if (uvm_map_pageable(map, entry->start, 2569 entry->end, FALSE, 2570 UVM_LK_ENTER|UVM_LK_EXIT) != 0) { 2571 2572 /* 2573 * If locking the entry fails, remember the 2574 * error if it's the first one. Note we 2575 * still continue setting the protection in 2576 * the map, but will return the error 2577 * condition regardless. 2578 * 2579 * XXX Ignore what the actual error is, 2580 * XXX just call it a resource shortage 2581 * XXX so that it doesn't get confused 2582 * XXX what uvm_map_protect() itself would 2583 * XXX normally return. 2584 */ 2585 2586 error = ENOMEM; 2587 } 2588 } 2589 current = current->next; 2590 } 2591 pmap_update(map->pmap); 2592 2593 out: 2594 vm_map_unlock(map); 2595 UVMHIST_LOG(maphist, "<- done, error=%d",error,0,0,0); 2596 return error; 2597 } 2598 2599 #undef MASK 2600 2601 /* 2602 * uvm_map_inherit: set inheritance code for range of addrs in map. 2603 * 2604 * => map must be unlocked 2605 * => note that the inherit code is used during a "fork". see fork 2606 * code for details. 2607 */ 2608 2609 int 2610 uvm_map_inherit(struct vm_map *map, vaddr_t start, vaddr_t end, 2611 vm_inherit_t new_inheritance) 2612 { 2613 struct vm_map_entry *entry, *temp_entry; 2614 UVMHIST_FUNC("uvm_map_inherit"); UVMHIST_CALLED(maphist); 2615 UVMHIST_LOG(maphist,"(map=0x%x,start=0x%x,end=0x%x,new_inh=0x%x)", 2616 map, start, end, new_inheritance); 2617 2618 switch (new_inheritance) { 2619 case MAP_INHERIT_NONE: 2620 case MAP_INHERIT_COPY: 2621 case MAP_INHERIT_SHARE: 2622 break; 2623 default: 2624 UVMHIST_LOG(maphist,"<- done (INVALID ARG)",0,0,0,0); 2625 return EINVAL; 2626 } 2627 2628 vm_map_lock(map); 2629 VM_MAP_RANGE_CHECK(map, start, end); 2630 if (uvm_map_lookup_entry(map, start, &temp_entry)) { 2631 entry = temp_entry; 2632 UVM_MAP_CLIP_START(map, entry, start); 2633 } else { 2634 entry = temp_entry->next; 2635 } 2636 while ((entry != &map->header) && (entry->start < end)) { 2637 UVM_MAP_CLIP_END(map, entry, end); 2638 entry->inheritance = new_inheritance; 2639 entry = entry->next; 2640 } 2641 vm_map_unlock(map); 2642 UVMHIST_LOG(maphist,"<- done (OK)",0,0,0,0); 2643 return 0; 2644 } 2645 2646 /* 2647 * uvm_map_advice: set advice code for range of addrs in map. 2648 * 2649 * => map must be unlocked 2650 */ 2651 2652 int 2653 uvm_map_advice(struct vm_map *map, vaddr_t start, vaddr_t end, int new_advice) 2654 { 2655 struct vm_map_entry *entry, *temp_entry; 2656 UVMHIST_FUNC("uvm_map_advice"); UVMHIST_CALLED(maphist); 2657 UVMHIST_LOG(maphist,"(map=0x%x,start=0x%x,end=0x%x,new_adv=0x%x)", 2658 map, start, end, new_advice); 2659 2660 vm_map_lock(map); 2661 VM_MAP_RANGE_CHECK(map, start, end); 2662 if (uvm_map_lookup_entry(map, start, &temp_entry)) { 2663 entry = temp_entry; 2664 UVM_MAP_CLIP_START(map, entry, start); 2665 } else { 2666 entry = temp_entry->next; 2667 } 2668 2669 /* 2670 * XXXJRT: disallow holes? 2671 */ 2672 2673 while ((entry != &map->header) && (entry->start < end)) { 2674 UVM_MAP_CLIP_END(map, entry, end); 2675 2676 switch (new_advice) { 2677 case MADV_NORMAL: 2678 case MADV_RANDOM: 2679 case MADV_SEQUENTIAL: 2680 /* nothing special here */ 2681 break; 2682 2683 default: 2684 vm_map_unlock(map); 2685 UVMHIST_LOG(maphist,"<- done (INVALID ARG)",0,0,0,0); 2686 return EINVAL; 2687 } 2688 entry->advice = new_advice; 2689 entry = entry->next; 2690 } 2691 2692 vm_map_unlock(map); 2693 UVMHIST_LOG(maphist,"<- done (OK)",0,0,0,0); 2694 return 0; 2695 } 2696 2697 /* 2698 * uvm_map_pageable: sets the pageability of a range in a map. 2699 * 2700 * => wires map entries. should not be used for transient page locking. 2701 * for that, use uvm_fault_wire()/uvm_fault_unwire() (see uvm_vslock()). 2702 * => regions sepcified as not pageable require lock-down (wired) memory 2703 * and page tables. 2704 * => map must never be read-locked 2705 * => if islocked is TRUE, map is already write-locked 2706 * => we always unlock the map, since we must downgrade to a read-lock 2707 * to call uvm_fault_wire() 2708 * => XXXCDC: check this and try and clean it up. 2709 */ 2710 2711 int 2712 uvm_map_pageable(struct vm_map *map, vaddr_t start, vaddr_t end, 2713 boolean_t new_pageable, int lockflags) 2714 { 2715 struct vm_map_entry *entry, *start_entry, *failed_entry; 2716 int rv; 2717 #ifdef DIAGNOSTIC 2718 u_int timestamp_save; 2719 #endif 2720 UVMHIST_FUNC("uvm_map_pageable"); UVMHIST_CALLED(maphist); 2721 UVMHIST_LOG(maphist,"(map=0x%x,start=0x%x,end=0x%x,new_pageable=0x%x)", 2722 map, start, end, new_pageable); 2723 KASSERT(map->flags & VM_MAP_PAGEABLE); 2724 2725 if ((lockflags & UVM_LK_ENTER) == 0) 2726 vm_map_lock(map); 2727 VM_MAP_RANGE_CHECK(map, start, end); 2728 2729 /* 2730 * only one pageability change may take place at one time, since 2731 * uvm_fault_wire assumes it will be called only once for each 2732 * wiring/unwiring. therefore, we have to make sure we're actually 2733 * changing the pageability for the entire region. we do so before 2734 * making any changes. 2735 */ 2736 2737 if (uvm_map_lookup_entry(map, start, &start_entry) == FALSE) { 2738 if ((lockflags & UVM_LK_EXIT) == 0) 2739 vm_map_unlock(map); 2740 2741 UVMHIST_LOG(maphist,"<- done (fault)",0,0,0,0); 2742 return EFAULT; 2743 } 2744 entry = start_entry; 2745 2746 /* 2747 * handle wiring and unwiring separately. 2748 */ 2749 2750 if (new_pageable) { /* unwire */ 2751 UVM_MAP_CLIP_START(map, entry, start); 2752 2753 /* 2754 * unwiring. first ensure that the range to be unwired is 2755 * really wired down and that there are no holes. 2756 */ 2757 2758 while ((entry != &map->header) && (entry->start < end)) { 2759 if (entry->wired_count == 0 || 2760 (entry->end < end && 2761 (entry->next == &map->header || 2762 entry->next->start > entry->end))) { 2763 if ((lockflags & UVM_LK_EXIT) == 0) 2764 vm_map_unlock(map); 2765 UVMHIST_LOG(maphist, "<- done (INVAL)",0,0,0,0); 2766 return EINVAL; 2767 } 2768 entry = entry->next; 2769 } 2770 2771 /* 2772 * POSIX 1003.1b - a single munlock call unlocks a region, 2773 * regardless of the number of mlock calls made on that 2774 * region. 2775 */ 2776 2777 entry = start_entry; 2778 while ((entry != &map->header) && (entry->start < end)) { 2779 UVM_MAP_CLIP_END(map, entry, end); 2780 if (VM_MAPENT_ISWIRED(entry)) 2781 uvm_map_entry_unwire(map, entry); 2782 entry = entry->next; 2783 } 2784 if ((lockflags & UVM_LK_EXIT) == 0) 2785 vm_map_unlock(map); 2786 UVMHIST_LOG(maphist,"<- done (OK UNWIRE)",0,0,0,0); 2787 return 0; 2788 } 2789 2790 /* 2791 * wire case: in two passes [XXXCDC: ugly block of code here] 2792 * 2793 * 1: holding the write lock, we create any anonymous maps that need 2794 * to be created. then we clip each map entry to the region to 2795 * be wired and increment its wiring count. 2796 * 2797 * 2: we downgrade to a read lock, and call uvm_fault_wire to fault 2798 * in the pages for any newly wired area (wired_count == 1). 2799 * 2800 * downgrading to a read lock for uvm_fault_wire avoids a possible 2801 * deadlock with another thread that may have faulted on one of 2802 * the pages to be wired (it would mark the page busy, blocking 2803 * us, then in turn block on the map lock that we hold). because 2804 * of problems in the recursive lock package, we cannot upgrade 2805 * to a write lock in vm_map_lookup. thus, any actions that 2806 * require the write lock must be done beforehand. because we 2807 * keep the read lock on the map, the copy-on-write status of the 2808 * entries we modify here cannot change. 2809 */ 2810 2811 while ((entry != &map->header) && (entry->start < end)) { 2812 if (VM_MAPENT_ISWIRED(entry) == 0) { /* not already wired? */ 2813 2814 /* 2815 * perform actions of vm_map_lookup that need the 2816 * write lock on the map: create an anonymous map 2817 * for a copy-on-write region, or an anonymous map 2818 * for a zero-fill region. (XXXCDC: submap case 2819 * ok?) 2820 */ 2821 2822 if (!UVM_ET_ISSUBMAP(entry)) { /* not submap */ 2823 if (UVM_ET_ISNEEDSCOPY(entry) && 2824 ((entry->max_protection & VM_PROT_WRITE) || 2825 (entry->object.uvm_obj == NULL))) { 2826 amap_copy(map, entry, M_WAITOK, TRUE, 2827 start, end); 2828 /* XXXCDC: wait OK? */ 2829 } 2830 } 2831 } 2832 UVM_MAP_CLIP_START(map, entry, start); 2833 UVM_MAP_CLIP_END(map, entry, end); 2834 entry->wired_count++; 2835 2836 /* 2837 * Check for holes 2838 */ 2839 2840 if (entry->protection == VM_PROT_NONE || 2841 (entry->end < end && 2842 (entry->next == &map->header || 2843 entry->next->start > entry->end))) { 2844 2845 /* 2846 * found one. amap creation actions do not need to 2847 * be undone, but the wired counts need to be restored. 2848 */ 2849 2850 while (entry != &map->header && entry->end > start) { 2851 entry->wired_count--; 2852 entry = entry->prev; 2853 } 2854 if ((lockflags & UVM_LK_EXIT) == 0) 2855 vm_map_unlock(map); 2856 UVMHIST_LOG(maphist,"<- done (INVALID WIRE)",0,0,0,0); 2857 return EINVAL; 2858 } 2859 entry = entry->next; 2860 } 2861 2862 /* 2863 * Pass 2. 2864 */ 2865 2866 #ifdef DIAGNOSTIC 2867 timestamp_save = map->timestamp; 2868 #endif 2869 vm_map_busy(map); 2870 vm_map_downgrade(map); 2871 2872 rv = 0; 2873 entry = start_entry; 2874 while (entry != &map->header && entry->start < end) { 2875 if (entry->wired_count == 1) { 2876 rv = uvm_fault_wire(map, entry->start, entry->end, 2877 VM_FAULT_WIREMAX, entry->max_protection); 2878 if (rv) { 2879 2880 /* 2881 * wiring failed. break out of the loop. 2882 * we'll clean up the map below, once we 2883 * have a write lock again. 2884 */ 2885 2886 break; 2887 } 2888 } 2889 entry = entry->next; 2890 } 2891 2892 if (rv) { /* failed? */ 2893 2894 /* 2895 * Get back to an exclusive (write) lock. 2896 */ 2897 2898 vm_map_upgrade(map); 2899 vm_map_unbusy(map); 2900 2901 #ifdef DIAGNOSTIC 2902 if (timestamp_save != map->timestamp) 2903 panic("uvm_map_pageable: stale map"); 2904 #endif 2905 2906 /* 2907 * first drop the wiring count on all the entries 2908 * which haven't actually been wired yet. 2909 */ 2910 2911 failed_entry = entry; 2912 while (entry != &map->header && entry->start < end) { 2913 entry->wired_count--; 2914 entry = entry->next; 2915 } 2916 2917 /* 2918 * now, unwire all the entries that were successfully 2919 * wired above. 2920 */ 2921 2922 entry = start_entry; 2923 while (entry != failed_entry) { 2924 entry->wired_count--; 2925 if (VM_MAPENT_ISWIRED(entry) == 0) 2926 uvm_map_entry_unwire(map, entry); 2927 entry = entry->next; 2928 } 2929 if ((lockflags & UVM_LK_EXIT) == 0) 2930 vm_map_unlock(map); 2931 UVMHIST_LOG(maphist, "<- done (RV=%d)", rv,0,0,0); 2932 return (rv); 2933 } 2934 2935 /* We are holding a read lock here. */ 2936 if ((lockflags & UVM_LK_EXIT) == 0) { 2937 vm_map_unbusy(map); 2938 vm_map_unlock_read(map); 2939 } else { 2940 2941 /* 2942 * Get back to an exclusive (write) lock. 2943 */ 2944 2945 vm_map_upgrade(map); 2946 vm_map_unbusy(map); 2947 } 2948 2949 UVMHIST_LOG(maphist,"<- done (OK WIRE)",0,0,0,0); 2950 return 0; 2951 } 2952 2953 /* 2954 * uvm_map_pageable_all: special case of uvm_map_pageable - affects 2955 * all mapped regions. 2956 * 2957 * => map must not be locked. 2958 * => if no flags are specified, all regions are unwired. 2959 * => XXXJRT: has some of the same problems as uvm_map_pageable() above. 2960 */ 2961 2962 int 2963 uvm_map_pageable_all(struct vm_map *map, int flags, vsize_t limit) 2964 { 2965 struct vm_map_entry *entry, *failed_entry; 2966 vsize_t size; 2967 int rv; 2968 #ifdef DIAGNOSTIC 2969 u_int timestamp_save; 2970 #endif 2971 UVMHIST_FUNC("uvm_map_pageable_all"); UVMHIST_CALLED(maphist); 2972 UVMHIST_LOG(maphist,"(map=0x%x,flags=0x%x)", map, flags, 0, 0); 2973 2974 KASSERT(map->flags & VM_MAP_PAGEABLE); 2975 2976 vm_map_lock(map); 2977 2978 /* 2979 * handle wiring and unwiring separately. 2980 */ 2981 2982 if (flags == 0) { /* unwire */ 2983 2984 /* 2985 * POSIX 1003.1b -- munlockall unlocks all regions, 2986 * regardless of how many times mlockall has been called. 2987 */ 2988 2989 for (entry = map->header.next; entry != &map->header; 2990 entry = entry->next) { 2991 if (VM_MAPENT_ISWIRED(entry)) 2992 uvm_map_entry_unwire(map, entry); 2993 } 2994 vm_map_modflags(map, 0, VM_MAP_WIREFUTURE); 2995 vm_map_unlock(map); 2996 UVMHIST_LOG(maphist,"<- done (OK UNWIRE)",0,0,0,0); 2997 return 0; 2998 } 2999 3000 if (flags & MCL_FUTURE) { 3001 3002 /* 3003 * must wire all future mappings; remember this. 3004 */ 3005 3006 vm_map_modflags(map, VM_MAP_WIREFUTURE, 0); 3007 } 3008 3009 if ((flags & MCL_CURRENT) == 0) { 3010 3011 /* 3012 * no more work to do! 3013 */ 3014 3015 UVMHIST_LOG(maphist,"<- done (OK no wire)",0,0,0,0); 3016 vm_map_unlock(map); 3017 return 0; 3018 } 3019 3020 /* 3021 * wire case: in three passes [XXXCDC: ugly block of code here] 3022 * 3023 * 1: holding the write lock, count all pages mapped by non-wired 3024 * entries. if this would cause us to go over our limit, we fail. 3025 * 3026 * 2: still holding the write lock, we create any anonymous maps that 3027 * need to be created. then we increment its wiring count. 3028 * 3029 * 3: we downgrade to a read lock, and call uvm_fault_wire to fault 3030 * in the pages for any newly wired area (wired_count == 1). 3031 * 3032 * downgrading to a read lock for uvm_fault_wire avoids a possible 3033 * deadlock with another thread that may have faulted on one of 3034 * the pages to be wired (it would mark the page busy, blocking 3035 * us, then in turn block on the map lock that we hold). because 3036 * of problems in the recursive lock package, we cannot upgrade 3037 * to a write lock in vm_map_lookup. thus, any actions that 3038 * require the write lock must be done beforehand. because we 3039 * keep the read lock on the map, the copy-on-write status of the 3040 * entries we modify here cannot change. 3041 */ 3042 3043 for (size = 0, entry = map->header.next; entry != &map->header; 3044 entry = entry->next) { 3045 if (entry->protection != VM_PROT_NONE && 3046 VM_MAPENT_ISWIRED(entry) == 0) { /* not already wired? */ 3047 size += entry->end - entry->start; 3048 } 3049 } 3050 3051 if (atop(size) + uvmexp.wired > uvmexp.wiredmax) { 3052 vm_map_unlock(map); 3053 return ENOMEM; 3054 } 3055 3056 /* XXX non-pmap_wired_count case must be handled by caller */ 3057 #ifdef pmap_wired_count 3058 if (limit != 0 && 3059 (size + ptoa(pmap_wired_count(vm_map_pmap(map))) > limit)) { 3060 vm_map_unlock(map); 3061 return ENOMEM; 3062 } 3063 #endif 3064 3065 /* 3066 * Pass 2. 3067 */ 3068 3069 for (entry = map->header.next; entry != &map->header; 3070 entry = entry->next) { 3071 if (entry->protection == VM_PROT_NONE) 3072 continue; 3073 if (VM_MAPENT_ISWIRED(entry) == 0) { /* not already wired? */ 3074 3075 /* 3076 * perform actions of vm_map_lookup that need the 3077 * write lock on the map: create an anonymous map 3078 * for a copy-on-write region, or an anonymous map 3079 * for a zero-fill region. (XXXCDC: submap case 3080 * ok?) 3081 */ 3082 3083 if (!UVM_ET_ISSUBMAP(entry)) { /* not submap */ 3084 if (UVM_ET_ISNEEDSCOPY(entry) && 3085 ((entry->max_protection & VM_PROT_WRITE) || 3086 (entry->object.uvm_obj == NULL))) { 3087 amap_copy(map, entry, M_WAITOK, TRUE, 3088 entry->start, entry->end); 3089 /* XXXCDC: wait OK? */ 3090 } 3091 } 3092 } 3093 entry->wired_count++; 3094 } 3095 3096 /* 3097 * Pass 3. 3098 */ 3099 3100 #ifdef DIAGNOSTIC 3101 timestamp_save = map->timestamp; 3102 #endif 3103 vm_map_busy(map); 3104 vm_map_downgrade(map); 3105 3106 rv = 0; 3107 for (entry = map->header.next; entry != &map->header; 3108 entry = entry->next) { 3109 if (entry->wired_count == 1) { 3110 rv = uvm_fault_wire(map, entry->start, entry->end, 3111 VM_FAULT_WIREMAX, entry->max_protection); 3112 if (rv) { 3113 3114 /* 3115 * wiring failed. break out of the loop. 3116 * we'll clean up the map below, once we 3117 * have a write lock again. 3118 */ 3119 3120 break; 3121 } 3122 } 3123 } 3124 3125 if (rv) { 3126 3127 /* 3128 * Get back an exclusive (write) lock. 3129 */ 3130 3131 vm_map_upgrade(map); 3132 vm_map_unbusy(map); 3133 3134 #ifdef DIAGNOSTIC 3135 if (timestamp_save != map->timestamp) 3136 panic("uvm_map_pageable_all: stale map"); 3137 #endif 3138 3139 /* 3140 * first drop the wiring count on all the entries 3141 * which haven't actually been wired yet. 3142 * 3143 * Skip VM_PROT_NONE entries like we did above. 3144 */ 3145 3146 failed_entry = entry; 3147 for (/* nothing */; entry != &map->header; 3148 entry = entry->next) { 3149 if (entry->protection == VM_PROT_NONE) 3150 continue; 3151 entry->wired_count--; 3152 } 3153 3154 /* 3155 * now, unwire all the entries that were successfully 3156 * wired above. 3157 * 3158 * Skip VM_PROT_NONE entries like we did above. 3159 */ 3160 3161 for (entry = map->header.next; entry != failed_entry; 3162 entry = entry->next) { 3163 if (entry->protection == VM_PROT_NONE) 3164 continue; 3165 entry->wired_count--; 3166 if (VM_MAPENT_ISWIRED(entry)) 3167 uvm_map_entry_unwire(map, entry); 3168 } 3169 vm_map_unlock(map); 3170 UVMHIST_LOG(maphist,"<- done (RV=%d)", rv,0,0,0); 3171 return (rv); 3172 } 3173 3174 /* We are holding a read lock here. */ 3175 vm_map_unbusy(map); 3176 vm_map_unlock_read(map); 3177 3178 UVMHIST_LOG(maphist,"<- done (OK WIRE)",0,0,0,0); 3179 return 0; 3180 } 3181 3182 /* 3183 * uvm_map_clean: clean out a map range 3184 * 3185 * => valid flags: 3186 * if (flags & PGO_CLEANIT): dirty pages are cleaned first 3187 * if (flags & PGO_SYNCIO): dirty pages are written synchronously 3188 * if (flags & PGO_DEACTIVATE): any cached pages are deactivated after clean 3189 * if (flags & PGO_FREE): any cached pages are freed after clean 3190 * => returns an error if any part of the specified range isn't mapped 3191 * => never a need to flush amap layer since the anonymous memory has 3192 * no permanent home, but may deactivate pages there 3193 * => called from sys_msync() and sys_madvise() 3194 * => caller must not write-lock map (read OK). 3195 * => we may sleep while cleaning if SYNCIO [with map read-locked] 3196 */ 3197 3198 int 3199 uvm_map_clean(struct vm_map *map, vaddr_t start, vaddr_t end, int flags) 3200 { 3201 struct vm_map_entry *current, *entry; 3202 struct uvm_object *uobj; 3203 struct vm_amap *amap; 3204 struct vm_anon *anon; 3205 struct vm_page *pg; 3206 vaddr_t offset; 3207 vsize_t size; 3208 int error, refs; 3209 UVMHIST_FUNC("uvm_map_clean"); UVMHIST_CALLED(maphist); 3210 3211 UVMHIST_LOG(maphist,"(map=0x%x,start=0x%x,end=0x%x,flags=0x%x)", 3212 map, start, end, flags); 3213 KASSERT((flags & (PGO_FREE|PGO_DEACTIVATE)) != 3214 (PGO_FREE|PGO_DEACTIVATE)); 3215 3216 vm_map_lock_read(map); 3217 VM_MAP_RANGE_CHECK(map, start, end); 3218 if (uvm_map_lookup_entry(map, start, &entry) == FALSE) { 3219 vm_map_unlock_read(map); 3220 return EFAULT; 3221 } 3222 3223 /* 3224 * Make a first pass to check for holes. 3225 */ 3226 3227 for (current = entry; current->start < end; current = current->next) { 3228 if (UVM_ET_ISSUBMAP(current)) { 3229 vm_map_unlock_read(map); 3230 return EINVAL; 3231 } 3232 if (end <= current->end) { 3233 break; 3234 } 3235 if (current->end != current->next->start) { 3236 vm_map_unlock_read(map); 3237 return EFAULT; 3238 } 3239 } 3240 3241 error = 0; 3242 for (current = entry; start < end; current = current->next) { 3243 amap = current->aref.ar_amap; /* top layer */ 3244 uobj = current->object.uvm_obj; /* bottom layer */ 3245 KASSERT(start >= current->start); 3246 3247 /* 3248 * No amap cleaning necessary if: 3249 * 3250 * (1) There's no amap. 3251 * 3252 * (2) We're not deactivating or freeing pages. 3253 */ 3254 3255 if (amap == NULL || (flags & (PGO_DEACTIVATE|PGO_FREE)) == 0) 3256 goto flush_object; 3257 3258 amap_lock(amap); 3259 offset = start - current->start; 3260 size = MIN(end, current->end) - start; 3261 for ( ; size != 0; size -= PAGE_SIZE, offset += PAGE_SIZE) { 3262 anon = amap_lookup(¤t->aref, offset); 3263 if (anon == NULL) 3264 continue; 3265 3266 simple_lock(&anon->an_lock); 3267 pg = anon->u.an_page; 3268 if (pg == NULL) { 3269 simple_unlock(&anon->an_lock); 3270 continue; 3271 } 3272 3273 switch (flags & (PGO_CLEANIT|PGO_FREE|PGO_DEACTIVATE)) { 3274 3275 /* 3276 * In these first 3 cases, we just deactivate the page. 3277 */ 3278 3279 case PGO_CLEANIT|PGO_FREE: 3280 case PGO_CLEANIT|PGO_DEACTIVATE: 3281 case PGO_DEACTIVATE: 3282 deactivate_it: 3283 /* 3284 * skip the page if it's loaned or wired, 3285 * since it shouldn't be on a paging queue 3286 * at all in these cases. 3287 */ 3288 3289 uvm_lock_pageq(); 3290 if (pg->loan_count != 0 || 3291 pg->wire_count != 0) { 3292 uvm_unlock_pageq(); 3293 simple_unlock(&anon->an_lock); 3294 continue; 3295 } 3296 KASSERT(pg->uanon == anon); 3297 pmap_clear_reference(pg); 3298 uvm_pagedeactivate(pg); 3299 uvm_unlock_pageq(); 3300 simple_unlock(&anon->an_lock); 3301 continue; 3302 3303 case PGO_FREE: 3304 3305 /* 3306 * If there are multiple references to 3307 * the amap, just deactivate the page. 3308 */ 3309 3310 if (amap_refs(amap) > 1) 3311 goto deactivate_it; 3312 3313 /* skip the page if it's wired */ 3314 if (pg->wire_count != 0) { 3315 simple_unlock(&anon->an_lock); 3316 continue; 3317 } 3318 amap_unadd(¤t->aref, offset); 3319 refs = --anon->an_ref; 3320 simple_unlock(&anon->an_lock); 3321 if (refs == 0) 3322 uvm_anfree(anon); 3323 continue; 3324 } 3325 } 3326 amap_unlock(amap); 3327 3328 flush_object: 3329 /* 3330 * flush pages if we've got a valid backing object. 3331 * note that we must always clean object pages before 3332 * freeing them since otherwise we could reveal stale 3333 * data from files. 3334 */ 3335 3336 offset = current->offset + (start - current->start); 3337 size = MIN(end, current->end) - start; 3338 if (uobj != NULL) { 3339 simple_lock(&uobj->vmobjlock); 3340 if (uobj->pgops->pgo_put != NULL) 3341 error = (uobj->pgops->pgo_put)(uobj, offset, 3342 offset + size, flags | PGO_CLEANIT); 3343 else 3344 error = 0; 3345 } 3346 start += size; 3347 } 3348 vm_map_unlock_read(map); 3349 return (error); 3350 } 3351 3352 3353 /* 3354 * uvm_map_checkprot: check protection in map 3355 * 3356 * => must allow specified protection in a fully allocated region. 3357 * => map must be read or write locked by caller. 3358 */ 3359 3360 boolean_t 3361 uvm_map_checkprot(struct vm_map *map, vaddr_t start, vaddr_t end, 3362 vm_prot_t protection) 3363 { 3364 struct vm_map_entry *entry; 3365 struct vm_map_entry *tmp_entry; 3366 3367 if (!uvm_map_lookup_entry(map, start, &tmp_entry)) { 3368 return (FALSE); 3369 } 3370 entry = tmp_entry; 3371 while (start < end) { 3372 if (entry == &map->header) { 3373 return (FALSE); 3374 } 3375 3376 /* 3377 * no holes allowed 3378 */ 3379 3380 if (start < entry->start) { 3381 return (FALSE); 3382 } 3383 3384 /* 3385 * check protection associated with entry 3386 */ 3387 3388 if ((entry->protection & protection) != protection) { 3389 return (FALSE); 3390 } 3391 start = entry->end; 3392 entry = entry->next; 3393 } 3394 return (TRUE); 3395 } 3396 3397 /* 3398 * uvmspace_alloc: allocate a vmspace structure. 3399 * 3400 * - structure includes vm_map and pmap 3401 * - XXX: no locking on this structure 3402 * - refcnt set to 1, rest must be init'd by caller 3403 */ 3404 struct vmspace * 3405 uvmspace_alloc(vaddr_t min, vaddr_t max) 3406 { 3407 struct vmspace *vm; 3408 UVMHIST_FUNC("uvmspace_alloc"); UVMHIST_CALLED(maphist); 3409 3410 vm = pool_get(&uvm_vmspace_pool, PR_WAITOK); 3411 uvmspace_init(vm, NULL, min, max); 3412 UVMHIST_LOG(maphist,"<- done (vm=0x%x)", vm,0,0,0); 3413 return (vm); 3414 } 3415 3416 /* 3417 * uvmspace_init: initialize a vmspace structure. 3418 * 3419 * - XXX: no locking on this structure 3420 * - refcnt set to 1, rest must be init'd by caller 3421 */ 3422 void 3423 uvmspace_init(struct vmspace *vm, struct pmap *pmap, vaddr_t min, vaddr_t max) 3424 { 3425 UVMHIST_FUNC("uvmspace_init"); UVMHIST_CALLED(maphist); 3426 3427 memset(vm, 0, sizeof(*vm)); 3428 uvm_map_setup(&vm->vm_map, min, max, VM_MAP_PAGEABLE 3429 #ifdef __USING_TOPDOWN_VM 3430 | VM_MAP_TOPDOWN 3431 #endif 3432 ); 3433 if (pmap) 3434 pmap_reference(pmap); 3435 else 3436 pmap = pmap_create(); 3437 vm->vm_map.pmap = pmap; 3438 vm->vm_refcnt = 1; 3439 UVMHIST_LOG(maphist,"<- done",0,0,0,0); 3440 } 3441 3442 /* 3443 * uvmspace_share: share a vmspace between two proceses 3444 * 3445 * - XXX: no locking on vmspace 3446 * - used for vfork, threads(?) 3447 */ 3448 3449 void 3450 uvmspace_share(struct proc *p1, struct proc *p2) 3451 { 3452 3453 p2->p_vmspace = p1->p_vmspace; 3454 p1->p_vmspace->vm_refcnt++; 3455 } 3456 3457 /* 3458 * uvmspace_unshare: ensure that process "p" has its own, unshared, vmspace 3459 * 3460 * - XXX: no locking on vmspace 3461 */ 3462 3463 void 3464 uvmspace_unshare(struct lwp *l) 3465 { 3466 struct proc *p = l->l_proc; 3467 struct vmspace *nvm, *ovm = p->p_vmspace; 3468 3469 if (ovm->vm_refcnt == 1) 3470 /* nothing to do: vmspace isn't shared in the first place */ 3471 return; 3472 3473 /* make a new vmspace, still holding old one */ 3474 nvm = uvmspace_fork(ovm); 3475 3476 pmap_deactivate(l); /* unbind old vmspace */ 3477 p->p_vmspace = nvm; 3478 pmap_activate(l); /* switch to new vmspace */ 3479 3480 uvmspace_free(ovm); /* drop reference to old vmspace */ 3481 } 3482 3483 /* 3484 * uvmspace_exec: the process wants to exec a new program 3485 * 3486 * - XXX: no locking on vmspace 3487 */ 3488 3489 void 3490 uvmspace_exec(struct lwp *l, vaddr_t start, vaddr_t end) 3491 { 3492 struct proc *p = l->l_proc; 3493 struct vmspace *nvm, *ovm = p->p_vmspace; 3494 struct vm_map *map = &ovm->vm_map; 3495 3496 #ifdef __sparc__ 3497 /* XXX cgd 960926: the sparc #ifdef should be a MD hook */ 3498 kill_user_windows(l); /* before stack addresses go away */ 3499 #endif 3500 3501 /* 3502 * see if more than one process is using this vmspace... 3503 */ 3504 3505 if (ovm->vm_refcnt == 1) { 3506 3507 /* 3508 * if p is the only process using its vmspace then we can safely 3509 * recycle that vmspace for the program that is being exec'd. 3510 */ 3511 3512 #ifdef SYSVSHM 3513 /* 3514 * SYSV SHM semantics require us to kill all segments on an exec 3515 */ 3516 3517 if (ovm->vm_shm) 3518 shmexit(ovm); 3519 #endif 3520 3521 /* 3522 * POSIX 1003.1b -- "lock future mappings" is revoked 3523 * when a process execs another program image. 3524 */ 3525 3526 vm_map_modflags(map, 0, VM_MAP_WIREFUTURE); 3527 3528 /* 3529 * now unmap the old program 3530 */ 3531 3532 pmap_remove_all(map->pmap); 3533 uvm_unmap(map, map->min_offset, map->max_offset); 3534 KASSERT(map->header.prev == &map->header); 3535 KASSERT(map->nentries == 0); 3536 3537 /* 3538 * resize the map 3539 */ 3540 3541 map->min_offset = start; 3542 map->max_offset = end; 3543 } else { 3544 3545 /* 3546 * p's vmspace is being shared, so we can't reuse it for p since 3547 * it is still being used for others. allocate a new vmspace 3548 * for p 3549 */ 3550 3551 nvm = uvmspace_alloc(start, end); 3552 3553 /* 3554 * install new vmspace and drop our ref to the old one. 3555 */ 3556 3557 pmap_deactivate(l); 3558 p->p_vmspace = nvm; 3559 pmap_activate(l); 3560 3561 uvmspace_free(ovm); 3562 } 3563 } 3564 3565 /* 3566 * uvmspace_free: free a vmspace data structure 3567 * 3568 * - XXX: no locking on vmspace 3569 */ 3570 3571 void 3572 uvmspace_free(struct vmspace *vm) 3573 { 3574 struct vm_map_entry *dead_entries; 3575 struct vm_map *map; 3576 UVMHIST_FUNC("uvmspace_free"); UVMHIST_CALLED(maphist); 3577 3578 UVMHIST_LOG(maphist,"(vm=0x%x) ref=%d", vm, vm->vm_refcnt,0,0); 3579 if (--vm->vm_refcnt > 0) { 3580 return; 3581 } 3582 3583 /* 3584 * at this point, there should be no other references to the map. 3585 * delete all of the mappings, then destroy the pmap. 3586 */ 3587 3588 map = &vm->vm_map; 3589 map->flags |= VM_MAP_DYING; 3590 pmap_remove_all(map->pmap); 3591 #ifdef SYSVSHM 3592 /* Get rid of any SYSV shared memory segments. */ 3593 if (vm->vm_shm != NULL) 3594 shmexit(vm); 3595 #endif 3596 if (map->nentries) { 3597 uvm_unmap_remove(map, map->min_offset, map->max_offset, 3598 &dead_entries); 3599 if (dead_entries != NULL) 3600 uvm_unmap_detach(dead_entries, 0); 3601 } 3602 KASSERT(map->nentries == 0); 3603 KASSERT(map->size == 0); 3604 pmap_destroy(map->pmap); 3605 pool_put(&uvm_vmspace_pool, vm); 3606 } 3607 3608 /* 3609 * F O R K - m a i n e n t r y p o i n t 3610 */ 3611 /* 3612 * uvmspace_fork: fork a process' main map 3613 * 3614 * => create a new vmspace for child process from parent. 3615 * => parent's map must not be locked. 3616 */ 3617 3618 struct vmspace * 3619 uvmspace_fork(struct vmspace *vm1) 3620 { 3621 struct vmspace *vm2; 3622 struct vm_map *old_map = &vm1->vm_map; 3623 struct vm_map *new_map; 3624 struct vm_map_entry *old_entry; 3625 struct vm_map_entry *new_entry; 3626 UVMHIST_FUNC("uvmspace_fork"); UVMHIST_CALLED(maphist); 3627 3628 vm_map_lock(old_map); 3629 3630 vm2 = uvmspace_alloc(old_map->min_offset, old_map->max_offset); 3631 memcpy(&vm2->vm_startcopy, &vm1->vm_startcopy, 3632 (caddr_t) (vm1 + 1) - (caddr_t) &vm1->vm_startcopy); 3633 new_map = &vm2->vm_map; /* XXX */ 3634 3635 old_entry = old_map->header.next; 3636 3637 /* 3638 * go entry-by-entry 3639 */ 3640 3641 while (old_entry != &old_map->header) { 3642 3643 /* 3644 * first, some sanity checks on the old entry 3645 */ 3646 3647 KASSERT(!UVM_ET_ISSUBMAP(old_entry)); 3648 KASSERT(UVM_ET_ISCOPYONWRITE(old_entry) || 3649 !UVM_ET_ISNEEDSCOPY(old_entry)); 3650 3651 switch (old_entry->inheritance) { 3652 case MAP_INHERIT_NONE: 3653 3654 /* 3655 * drop the mapping 3656 */ 3657 3658 break; 3659 3660 case MAP_INHERIT_SHARE: 3661 3662 /* 3663 * share the mapping: this means we want the old and 3664 * new entries to share amaps and backing objects. 3665 */ 3666 /* 3667 * if the old_entry needs a new amap (due to prev fork) 3668 * then we need to allocate it now so that we have 3669 * something we own to share with the new_entry. [in 3670 * other words, we need to clear needs_copy] 3671 */ 3672 3673 if (UVM_ET_ISNEEDSCOPY(old_entry)) { 3674 /* get our own amap, clears needs_copy */ 3675 amap_copy(old_map, old_entry, M_WAITOK, FALSE, 3676 0, 0); 3677 /* XXXCDC: WAITOK??? */ 3678 } 3679 3680 new_entry = uvm_mapent_alloc(new_map, 0); 3681 /* old_entry -> new_entry */ 3682 uvm_mapent_copy(old_entry, new_entry); 3683 3684 /* new pmap has nothing wired in it */ 3685 new_entry->wired_count = 0; 3686 3687 /* 3688 * gain reference to object backing the map (can't 3689 * be a submap, already checked this case). 3690 */ 3691 3692 if (new_entry->aref.ar_amap) 3693 uvm_map_reference_amap(new_entry, AMAP_SHARED); 3694 3695 if (new_entry->object.uvm_obj && 3696 new_entry->object.uvm_obj->pgops->pgo_reference) 3697 new_entry->object.uvm_obj-> 3698 pgops->pgo_reference( 3699 new_entry->object.uvm_obj); 3700 3701 /* insert entry at end of new_map's entry list */ 3702 uvm_map_entry_link(new_map, new_map->header.prev, 3703 new_entry); 3704 3705 break; 3706 3707 case MAP_INHERIT_COPY: 3708 3709 /* 3710 * copy-on-write the mapping (using mmap's 3711 * MAP_PRIVATE semantics) 3712 * 3713 * allocate new_entry, adjust reference counts. 3714 * (note that new references are read-only). 3715 */ 3716 3717 new_entry = uvm_mapent_alloc(new_map, 0); 3718 /* old_entry -> new_entry */ 3719 uvm_mapent_copy(old_entry, new_entry); 3720 3721 if (new_entry->aref.ar_amap) 3722 uvm_map_reference_amap(new_entry, 0); 3723 3724 if (new_entry->object.uvm_obj && 3725 new_entry->object.uvm_obj->pgops->pgo_reference) 3726 new_entry->object.uvm_obj->pgops->pgo_reference 3727 (new_entry->object.uvm_obj); 3728 3729 /* new pmap has nothing wired in it */ 3730 new_entry->wired_count = 0; 3731 3732 new_entry->etype |= 3733 (UVM_ET_COPYONWRITE|UVM_ET_NEEDSCOPY); 3734 uvm_map_entry_link(new_map, new_map->header.prev, 3735 new_entry); 3736 3737 /* 3738 * the new entry will need an amap. it will either 3739 * need to be copied from the old entry or created 3740 * from scratch (if the old entry does not have an 3741 * amap). can we defer this process until later 3742 * (by setting "needs_copy") or do we need to copy 3743 * the amap now? 3744 * 3745 * we must copy the amap now if any of the following 3746 * conditions hold: 3747 * 1. the old entry has an amap and that amap is 3748 * being shared. this means that the old (parent) 3749 * process is sharing the amap with another 3750 * process. if we do not clear needs_copy here 3751 * we will end up in a situation where both the 3752 * parent and child process are refering to the 3753 * same amap with "needs_copy" set. if the 3754 * parent write-faults, the fault routine will 3755 * clear "needs_copy" in the parent by allocating 3756 * a new amap. this is wrong because the 3757 * parent is supposed to be sharing the old amap 3758 * and the new amap will break that. 3759 * 3760 * 2. if the old entry has an amap and a non-zero 3761 * wire count then we are going to have to call 3762 * amap_cow_now to avoid page faults in the 3763 * parent process. since amap_cow_now requires 3764 * "needs_copy" to be clear we might as well 3765 * clear it here as well. 3766 * 3767 */ 3768 3769 if (old_entry->aref.ar_amap != NULL) { 3770 if ((amap_flags(old_entry->aref.ar_amap) & 3771 AMAP_SHARED) != 0 || 3772 VM_MAPENT_ISWIRED(old_entry)) { 3773 3774 amap_copy(new_map, new_entry, M_WAITOK, 3775 FALSE, 0, 0); 3776 /* XXXCDC: M_WAITOK ... ok? */ 3777 } 3778 } 3779 3780 /* 3781 * if the parent's entry is wired down, then the 3782 * parent process does not want page faults on 3783 * access to that memory. this means that we 3784 * cannot do copy-on-write because we can't write 3785 * protect the old entry. in this case we 3786 * resolve all copy-on-write faults now, using 3787 * amap_cow_now. note that we have already 3788 * allocated any needed amap (above). 3789 */ 3790 3791 if (VM_MAPENT_ISWIRED(old_entry)) { 3792 3793 /* 3794 * resolve all copy-on-write faults now 3795 * (note that there is nothing to do if 3796 * the old mapping does not have an amap). 3797 */ 3798 if (old_entry->aref.ar_amap) 3799 amap_cow_now(new_map, new_entry); 3800 3801 } else { 3802 3803 /* 3804 * setup mappings to trigger copy-on-write faults 3805 * we must write-protect the parent if it has 3806 * an amap and it is not already "needs_copy"... 3807 * if it is already "needs_copy" then the parent 3808 * has already been write-protected by a previous 3809 * fork operation. 3810 */ 3811 3812 if (old_entry->aref.ar_amap && 3813 !UVM_ET_ISNEEDSCOPY(old_entry)) { 3814 if (old_entry->max_protection & VM_PROT_WRITE) { 3815 pmap_protect(old_map->pmap, 3816 old_entry->start, 3817 old_entry->end, 3818 old_entry->protection & 3819 ~VM_PROT_WRITE); 3820 pmap_update(old_map->pmap); 3821 } 3822 old_entry->etype |= UVM_ET_NEEDSCOPY; 3823 } 3824 } 3825 break; 3826 } /* end of switch statement */ 3827 old_entry = old_entry->next; 3828 } 3829 3830 new_map->size = old_map->size; 3831 vm_map_unlock(old_map); 3832 3833 #ifdef SYSVSHM 3834 if (vm1->vm_shm) 3835 shmfork(vm1, vm2); 3836 #endif 3837 3838 #ifdef PMAP_FORK 3839 pmap_fork(vm1->vm_map.pmap, vm2->vm_map.pmap); 3840 #endif 3841 3842 UVMHIST_LOG(maphist,"<- done",0,0,0,0); 3843 return (vm2); 3844 } 3845 3846 3847 #if defined(DDB) 3848 3849 /* 3850 * DDB hooks 3851 */ 3852 3853 /* 3854 * uvm_map_printit: actually prints the map 3855 */ 3856 3857 void 3858 uvm_map_printit(struct vm_map *map, boolean_t full, 3859 void (*pr)(const char *, ...)) 3860 { 3861 struct vm_map_entry *entry; 3862 3863 (*pr)("MAP %p: [0x%lx->0x%lx]\n", map, map->min_offset,map->max_offset); 3864 (*pr)("\t#ent=%d, sz=%d, ref=%d, version=%d, flags=0x%x\n", 3865 map->nentries, map->size, map->ref_count, map->timestamp, 3866 map->flags); 3867 (*pr)("\tpmap=%p(resident=%d)\n", map->pmap, 3868 pmap_resident_count(map->pmap)); 3869 if (!full) 3870 return; 3871 for (entry = map->header.next; entry != &map->header; 3872 entry = entry->next) { 3873 (*pr)(" - %p: 0x%lx->0x%lx: obj=%p/0x%llx, amap=%p/%d\n", 3874 entry, entry->start, entry->end, entry->object.uvm_obj, 3875 (long long)entry->offset, entry->aref.ar_amap, 3876 entry->aref.ar_pageoff); 3877 (*pr)( 3878 "\tsubmap=%c, cow=%c, nc=%c, prot(max)=%d/%d, inh=%d, " 3879 "wc=%d, adv=%d\n", 3880 (entry->etype & UVM_ET_SUBMAP) ? 'T' : 'F', 3881 (entry->etype & UVM_ET_COPYONWRITE) ? 'T' : 'F', 3882 (entry->etype & UVM_ET_NEEDSCOPY) ? 'T' : 'F', 3883 entry->protection, entry->max_protection, 3884 entry->inheritance, entry->wired_count, entry->advice); 3885 } 3886 } 3887 3888 /* 3889 * uvm_object_printit: actually prints the object 3890 */ 3891 3892 void 3893 uvm_object_printit(struct uvm_object *uobj, boolean_t full, 3894 void (*pr)(const char *, ...)) 3895 { 3896 struct vm_page *pg; 3897 int cnt = 0; 3898 3899 (*pr)("OBJECT %p: locked=%d, pgops=%p, npages=%d, ", 3900 uobj, uobj->vmobjlock.lock_data, uobj->pgops, uobj->uo_npages); 3901 if (UVM_OBJ_IS_KERN_OBJECT(uobj)) 3902 (*pr)("refs=<SYSTEM>\n"); 3903 else 3904 (*pr)("refs=%d\n", uobj->uo_refs); 3905 3906 if (!full) { 3907 return; 3908 } 3909 (*pr)(" PAGES <pg,offset>:\n "); 3910 TAILQ_FOREACH(pg, &uobj->memq, listq) { 3911 cnt++; 3912 (*pr)("<%p,0x%llx> ", pg, (long long)pg->offset); 3913 if ((cnt % 3) == 0) { 3914 (*pr)("\n "); 3915 } 3916 } 3917 if ((cnt % 3) != 0) { 3918 (*pr)("\n"); 3919 } 3920 } 3921 3922 /* 3923 * uvm_page_printit: actually print the page 3924 */ 3925 3926 static const char page_flagbits[] = 3927 "\20\1BUSY\2WANTED\3TABLED\4CLEAN\5PAGEOUT\6RELEASED\7FAKE\10RDONLY" 3928 "\11ZERO\15PAGER1"; 3929 static const char page_pqflagbits[] = 3930 "\20\1FREE\2INACTIVE\3ACTIVE\5ANON\6AOBJ"; 3931 3932 void 3933 uvm_page_printit(struct vm_page *pg, boolean_t full, 3934 void (*pr)(const char *, ...)) 3935 { 3936 struct vm_page *tpg; 3937 struct uvm_object *uobj; 3938 struct pglist *pgl; 3939 char pgbuf[128]; 3940 char pqbuf[128]; 3941 3942 (*pr)("PAGE %p:\n", pg); 3943 bitmask_snprintf(pg->flags, page_flagbits, pgbuf, sizeof(pgbuf)); 3944 bitmask_snprintf(pg->pqflags, page_pqflagbits, pqbuf, sizeof(pqbuf)); 3945 (*pr)(" flags=%s, pqflags=%s, wire_count=%d, pa=0x%lx\n", 3946 pgbuf, pqbuf, pg->wire_count, (long)VM_PAGE_TO_PHYS(pg)); 3947 (*pr)(" uobject=%p, uanon=%p, offset=0x%llx loan_count=%d\n", 3948 pg->uobject, pg->uanon, (long long)pg->offset, pg->loan_count); 3949 #if defined(UVM_PAGE_TRKOWN) 3950 if (pg->flags & PG_BUSY) 3951 (*pr)(" owning process = %d, tag=%s\n", 3952 pg->owner, pg->owner_tag); 3953 else 3954 (*pr)(" page not busy, no owner\n"); 3955 #else 3956 (*pr)(" [page ownership tracking disabled]\n"); 3957 #endif 3958 3959 if (!full) 3960 return; 3961 3962 /* cross-verify object/anon */ 3963 if ((pg->pqflags & PQ_FREE) == 0) { 3964 if (pg->pqflags & PQ_ANON) { 3965 if (pg->uanon == NULL || pg->uanon->u.an_page != pg) 3966 (*pr)(" >>> ANON DOES NOT POINT HERE <<< (%p)\n", 3967 (pg->uanon) ? pg->uanon->u.an_page : NULL); 3968 else 3969 (*pr)(" anon backpointer is OK\n"); 3970 } else { 3971 uobj = pg->uobject; 3972 if (uobj) { 3973 (*pr)(" checking object list\n"); 3974 TAILQ_FOREACH(tpg, &uobj->memq, listq) { 3975 if (tpg == pg) { 3976 break; 3977 } 3978 } 3979 if (tpg) 3980 (*pr)(" page found on object list\n"); 3981 else 3982 (*pr)(" >>> PAGE NOT FOUND ON OBJECT LIST! <<<\n"); 3983 } 3984 } 3985 } 3986 3987 /* cross-verify page queue */ 3988 if (pg->pqflags & PQ_FREE) { 3989 int fl = uvm_page_lookup_freelist(pg); 3990 int color = VM_PGCOLOR_BUCKET(pg); 3991 pgl = &uvm.page_free[fl].pgfl_buckets[color].pgfl_queues[ 3992 ((pg)->flags & PG_ZERO) ? PGFL_ZEROS : PGFL_UNKNOWN]; 3993 } else if (pg->pqflags & PQ_INACTIVE) { 3994 pgl = &uvm.page_inactive; 3995 } else if (pg->pqflags & PQ_ACTIVE) { 3996 pgl = &uvm.page_active; 3997 } else { 3998 pgl = NULL; 3999 } 4000 4001 if (pgl) { 4002 (*pr)(" checking pageq list\n"); 4003 TAILQ_FOREACH(tpg, pgl, pageq) { 4004 if (tpg == pg) { 4005 break; 4006 } 4007 } 4008 if (tpg) 4009 (*pr)(" page found on pageq list\n"); 4010 else 4011 (*pr)(" >>> PAGE NOT FOUND ON PAGEQ LIST! <<<\n"); 4012 } 4013 } 4014 #endif 4015