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