1 /* 2 * Copyright (c) 1991 Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * The Mach Operating System project at Carnegie-Mellon University. 7 * 8 * %sccs.include.redist.c% 9 * 10 * @(#)vm_map.c 7.3 (Berkeley) 04/21/91 11 * 12 * 13 * Copyright (c) 1987, 1990 Carnegie-Mellon University. 14 * All rights reserved. 15 * 16 * Authors: Avadis Tevanian, Jr., Michael Wayne Young 17 * 18 * Permission to use, copy, modify and distribute this software and 19 * its documentation is hereby granted, provided that both the copyright 20 * notice and this permission notice appear in all copies of the 21 * software, derivative works or modified versions, and any portions 22 * thereof, and that both notices appear in supporting documentation. 23 * 24 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" 25 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND 26 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. 27 * 28 * Carnegie Mellon requests users of this software to return to 29 * 30 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU 31 * School of Computer Science 32 * Carnegie Mellon University 33 * Pittsburgh PA 15213-3890 34 * 35 * any improvements or extensions that they make and grant Carnegie the 36 * rights to redistribute these changes. 37 */ 38 39 /* 40 * Virtual memory mapping module. 41 */ 42 43 #include "param.h" 44 #include "malloc.h" 45 #include "vm.h" 46 #include "vm_page.h" 47 #include "vm_object.h" 48 49 /* 50 * Virtual memory maps provide for the mapping, protection, 51 * and sharing of virtual memory objects. In addition, 52 * this module provides for an efficient virtual copy of 53 * memory from one map to another. 54 * 55 * Synchronization is required prior to most operations. 56 * 57 * Maps consist of an ordered doubly-linked list of simple 58 * entries; a single hint is used to speed up lookups. 59 * 60 * In order to properly represent the sharing of virtual 61 * memory regions among maps, the map structure is bi-level. 62 * Top-level ("address") maps refer to regions of sharable 63 * virtual memory. These regions are implemented as 64 * ("sharing") maps, which then refer to the actual virtual 65 * memory objects. When two address maps "share" memory, 66 * their top-level maps both have references to the same 67 * sharing map. When memory is virtual-copied from one 68 * address map to another, the references in the sharing 69 * maps are actually copied -- no copying occurs at the 70 * virtual memory object level. 71 * 72 * Since portions of maps are specified by start/end addreses, 73 * which may not align with existing map entries, all 74 * routines merely "clip" entries to these start/end values. 75 * [That is, an entry is split into two, bordering at a 76 * start or end value.] Note that these clippings may not 77 * always be necessary (as the two resulting entries are then 78 * not changed); however, the clipping is done for convenience. 79 * No attempt is currently made to "glue back together" two 80 * abutting entries. 81 * 82 * As mentioned above, virtual copy operations are performed 83 * by copying VM object references from one sharing map to 84 * another, and then marking both regions as copy-on-write. 85 * It is important to note that only one writeable reference 86 * to a VM object region exists in any map -- this means that 87 * shadow object creation can be delayed until a write operation 88 * occurs. 89 */ 90 91 /* 92 * vm_map_startup: 93 * 94 * Initialize the vm_map module. Must be called before 95 * any other vm_map routines. 96 * 97 * Map and entry structures are allocated from the general 98 * purpose memory pool with some exceptions: 99 * 100 * - The kernel map and kmem submap are allocated statically. 101 * - Kernel map entries are allocated out of a static pool. 102 * 103 * These restrictions are necessary since malloc() uses the 104 * maps and requires map entries. 105 */ 106 107 vm_offset_t kentry_data; 108 vm_size_t kentry_data_size; 109 vm_map_entry_t kentry_free; 110 vm_map_t kmap_free; 111 112 void vm_map_startup() 113 { 114 register int i; 115 register vm_map_entry_t mep; 116 vm_map_t mp; 117 118 /* 119 * Static map structures for allocation before initialization of 120 * kernel map or kmem map. vm_map_create knows how to deal with them. 121 */ 122 kmap_free = mp = (vm_map_t) kentry_data; 123 i = MAX_KMAP; 124 while (--i > 0) { 125 mp->header.next = (vm_map_entry_t) (mp + 1); 126 mp++; 127 } 128 mp++->header.next = NULL; 129 130 /* 131 * Form a free list of statically allocated kernel map entries 132 * with the rest. 133 */ 134 kentry_free = mep = (vm_map_entry_t) mp; 135 i = (kentry_data_size - MAX_KMAP * sizeof *mp) / sizeof *mep; 136 while (--i > 0) { 137 mep->next = mep + 1; 138 mep++; 139 } 140 mep->next = NULL; 141 } 142 143 /* 144 * Allocate a vmspace structure, including a vm_map and pmap, 145 * and initialize those structures. The refcnt is set to 1. 146 * The remaining fields must be initialized by the caller. 147 */ 148 struct vmspace * 149 vmspace_alloc(min, max, pageable) 150 vm_offset_t min, max; 151 int pageable; 152 { 153 register struct vmspace *vm; 154 155 MALLOC(vm, struct vmspace *, sizeof(struct vmspace), M_VMMAP, M_WAITOK); 156 bzero(vm, (caddr_t) &vm->vm_startcopy - (caddr_t) vm); 157 vm_map_init(&vm->vm_map, min, max, pageable); 158 pmap_pinit(&vm->vm_pmap); 159 vm->vm_map.pmap = &vm->vm_pmap; /* XXX */ 160 vm->vm_refcnt = 1; 161 return (vm); 162 } 163 164 void 165 vmspace_free(vm) 166 register struct vmspace *vm; 167 { 168 169 if (--vm->vm_refcnt == 0) { 170 /* 171 * Lock the map, to wait out all other references to it. 172 * Delete all of the mappings and pages they hold, 173 * then call the pmap module to reclaim anything left. 174 */ 175 vm_map_lock(&vm->vm_map); 176 (void) vm_map_delete(&vm->vm_map, vm->vm_map.min_offset, 177 vm->vm_map.max_offset); 178 pmap_release(&vm->vm_pmap); 179 FREE(vm, M_VMMAP); 180 } 181 } 182 183 /* 184 * vm_map_create: 185 * 186 * Creates and returns a new empty VM map with 187 * the given physical map structure, and having 188 * the given lower and upper address bounds. 189 */ 190 vm_map_t vm_map_create(pmap, min, max, pageable) 191 pmap_t pmap; 192 vm_offset_t min, max; 193 boolean_t pageable; 194 { 195 register vm_map_t result; 196 extern vm_map_t kernel_map, kmem_map; 197 198 if (kmem_map == NULL) { 199 result = kmap_free; 200 kmap_free = (vm_map_t) result->header.next; 201 if (result == NULL) 202 panic("vm_map_create: out of maps"); 203 } else 204 MALLOC(result, vm_map_t, sizeof(struct vm_map), 205 M_VMMAP, M_WAITOK); 206 207 vm_map_init(result, min, max, pageable); 208 result->pmap = pmap; 209 return(result); 210 } 211 212 /* 213 * Initialize an existing vm_map structure 214 * such as that in the vmspace structure. 215 * The pmap is set elsewhere. 216 */ 217 void 218 vm_map_init(map, min, max, pageable) 219 register struct vm_map *map; 220 vm_offset_t min, max; 221 boolean_t pageable; 222 { 223 map->header.next = map->header.prev = &map->header; 224 map->nentries = 0; 225 map->size = 0; 226 map->ref_count = 1; 227 map->is_main_map = TRUE; 228 map->min_offset = min; 229 map->max_offset = max; 230 map->entries_pageable = pageable; 231 map->first_free = &map->header; 232 map->hint = &map->header; 233 map->timestamp = 0; 234 lock_init(&map->lock, TRUE); 235 simple_lock_init(&map->ref_lock); 236 simple_lock_init(&map->hint_lock); 237 } 238 239 /* 240 * vm_map_entry_create: [ internal use only ] 241 * 242 * Allocates a VM map entry for insertion. 243 * No entry fields are filled in. This routine is 244 */ 245 vm_map_entry_t vm_map_entry_create(map) 246 vm_map_t map; 247 { 248 vm_map_entry_t entry; 249 extern vm_map_t kernel_map, kmem_map, mb_map; 250 251 if (map == kernel_map || map == kmem_map || map == mb_map) { 252 if (entry = kentry_free) 253 kentry_free = kentry_free->next; 254 } else 255 MALLOC(entry, vm_map_entry_t, sizeof(struct vm_map_entry), 256 M_VMMAPENT, M_WAITOK); 257 if (entry == NULL) 258 panic("vm_map_entry_create: out of map entries"); 259 260 return(entry); 261 } 262 263 /* 264 * vm_map_entry_dispose: [ internal use only ] 265 * 266 * Inverse of vm_map_entry_create. 267 */ 268 void vm_map_entry_dispose(map, entry) 269 vm_map_t map; 270 vm_map_entry_t entry; 271 { 272 extern vm_map_t kernel_map, kmem_map, mb_map; 273 274 if (map == kernel_map || map == kmem_map || map == mb_map) { 275 entry->next = kentry_free; 276 kentry_free = entry; 277 } else 278 FREE(entry, M_VMMAPENT); 279 } 280 281 /* 282 * vm_map_entry_{un,}link: 283 * 284 * Insert/remove entries from maps. 285 */ 286 #define vm_map_entry_link(map, after_where, entry) \ 287 { \ 288 (map)->nentries++; \ 289 (entry)->prev = (after_where); \ 290 (entry)->next = (after_where)->next; \ 291 (entry)->prev->next = (entry); \ 292 (entry)->next->prev = (entry); \ 293 } 294 #define vm_map_entry_unlink(map, entry) \ 295 { \ 296 (map)->nentries--; \ 297 (entry)->next->prev = (entry)->prev; \ 298 (entry)->prev->next = (entry)->next; \ 299 } 300 301 /* 302 * vm_map_reference: 303 * 304 * Creates another valid reference to the given map. 305 * 306 */ 307 void vm_map_reference(map) 308 register vm_map_t map; 309 { 310 if (map == NULL) 311 return; 312 313 simple_lock(&map->ref_lock); 314 map->ref_count++; 315 simple_unlock(&map->ref_lock); 316 } 317 318 /* 319 * vm_map_deallocate: 320 * 321 * Removes a reference from the specified map, 322 * destroying it if no references remain. 323 * The map should not be locked. 324 */ 325 void vm_map_deallocate(map) 326 register vm_map_t map; 327 { 328 register int c; 329 330 if (map == NULL) 331 return; 332 333 simple_lock(&map->ref_lock); 334 c = --map->ref_count; 335 simple_unlock(&map->ref_lock); 336 337 if (c > 0) { 338 return; 339 } 340 341 /* 342 * Lock the map, to wait out all other references 343 * to it. 344 */ 345 346 vm_map_lock(map); 347 348 (void) vm_map_delete(map, map->min_offset, map->max_offset); 349 350 pmap_destroy(map->pmap); 351 352 FREE(map, M_VMMAP); 353 } 354 355 /* 356 * vm_map_insert: [ internal use only ] 357 * 358 * Inserts the given whole VM object into the target 359 * map at the specified address range. The object's 360 * size should match that of the address range. 361 * 362 * Requires that the map be locked, and leaves it so. 363 */ 364 vm_map_insert(map, object, offset, start, end) 365 vm_map_t map; 366 vm_object_t object; 367 vm_offset_t offset; 368 vm_offset_t start; 369 vm_offset_t end; 370 { 371 register vm_map_entry_t new_entry; 372 register vm_map_entry_t prev_entry; 373 vm_map_entry_t temp_entry; 374 375 /* 376 * Check that the start and end points are not bogus. 377 */ 378 379 if ((start < map->min_offset) || (end > map->max_offset) || 380 (start >= end)) 381 return(KERN_INVALID_ADDRESS); 382 383 /* 384 * Find the entry prior to the proposed 385 * starting address; if it's part of an 386 * existing entry, this range is bogus. 387 */ 388 389 if (vm_map_lookup_entry(map, start, &temp_entry)) 390 return(KERN_NO_SPACE); 391 392 prev_entry = temp_entry; 393 394 /* 395 * Assert that the next entry doesn't overlap the 396 * end point. 397 */ 398 399 if ((prev_entry->next != &map->header) && 400 (prev_entry->next->start < end)) 401 return(KERN_NO_SPACE); 402 403 /* 404 * See if we can avoid creating a new entry by 405 * extending one of our neighbors. 406 */ 407 408 if (object == NULL) { 409 if ((prev_entry != &map->header) && 410 (prev_entry->end == start) && 411 (map->is_main_map) && 412 (prev_entry->is_a_map == FALSE) && 413 (prev_entry->is_sub_map == FALSE) && 414 (prev_entry->inheritance == VM_INHERIT_DEFAULT) && 415 (prev_entry->protection == VM_PROT_DEFAULT) && 416 (prev_entry->max_protection == VM_PROT_DEFAULT) && 417 (prev_entry->wired_count == 0)) { 418 419 if (vm_object_coalesce(prev_entry->object.vm_object, 420 NULL, 421 prev_entry->offset, 422 (vm_offset_t) 0, 423 (vm_size_t)(prev_entry->end 424 - prev_entry->start), 425 (vm_size_t)(end - prev_entry->end))) { 426 /* 427 * Coalesced the two objects - can extend 428 * the previous map entry to include the 429 * new range. 430 */ 431 map->size += (end - prev_entry->end); 432 prev_entry->end = end; 433 return(KERN_SUCCESS); 434 } 435 } 436 } 437 438 /* 439 * Create a new entry 440 */ 441 442 new_entry = vm_map_entry_create(map); 443 new_entry->start = start; 444 new_entry->end = end; 445 446 new_entry->is_a_map = FALSE; 447 new_entry->is_sub_map = FALSE; 448 new_entry->object.vm_object = object; 449 new_entry->offset = offset; 450 451 new_entry->copy_on_write = FALSE; 452 new_entry->needs_copy = FALSE; 453 454 if (map->is_main_map) { 455 new_entry->inheritance = VM_INHERIT_DEFAULT; 456 new_entry->protection = VM_PROT_DEFAULT; 457 new_entry->max_protection = VM_PROT_DEFAULT; 458 new_entry->wired_count = 0; 459 } 460 461 /* 462 * Insert the new entry into the list 463 */ 464 465 vm_map_entry_link(map, prev_entry, new_entry); 466 map->size += new_entry->end - new_entry->start; 467 468 /* 469 * Update the free space hint 470 */ 471 472 if ((map->first_free == prev_entry) && (prev_entry->end >= new_entry->start)) 473 map->first_free = new_entry; 474 475 return(KERN_SUCCESS); 476 } 477 478 /* 479 * SAVE_HINT: 480 * 481 * Saves the specified entry as the hint for 482 * future lookups. Performs necessary interlocks. 483 */ 484 #define SAVE_HINT(map,value) \ 485 simple_lock(&(map)->hint_lock); \ 486 (map)->hint = (value); \ 487 simple_unlock(&(map)->hint_lock); 488 489 /* 490 * vm_map_lookup_entry: [ internal use only ] 491 * 492 * Finds the map entry containing (or 493 * immediately preceding) the specified address 494 * in the given map; the entry is returned 495 * in the "entry" parameter. The boolean 496 * result indicates whether the address is 497 * actually contained in the map. 498 */ 499 boolean_t vm_map_lookup_entry(map, address, entry) 500 register vm_map_t map; 501 register vm_offset_t address; 502 vm_map_entry_t *entry; /* OUT */ 503 { 504 register vm_map_entry_t cur; 505 register vm_map_entry_t last; 506 507 /* 508 * Start looking either from the head of the 509 * list, or from the hint. 510 */ 511 512 simple_lock(&map->hint_lock); 513 cur = map->hint; 514 simple_unlock(&map->hint_lock); 515 516 if (cur == &map->header) 517 cur = cur->next; 518 519 if (address >= cur->start) { 520 /* 521 * Go from hint to end of list. 522 * 523 * But first, make a quick check to see if 524 * we are already looking at the entry we 525 * want (which is usually the case). 526 * Note also that we don't need to save the hint 527 * here... it is the same hint (unless we are 528 * at the header, in which case the hint didn't 529 * buy us anything anyway). 530 */ 531 last = &map->header; 532 if ((cur != last) && (cur->end > address)) { 533 *entry = cur; 534 return(TRUE); 535 } 536 } 537 else { 538 /* 539 * Go from start to hint, *inclusively* 540 */ 541 last = cur->next; 542 cur = map->header.next; 543 } 544 545 /* 546 * Search linearly 547 */ 548 549 while (cur != last) { 550 if (cur->end > address) { 551 if (address >= cur->start) { 552 /* 553 * Save this lookup for future 554 * hints, and return 555 */ 556 557 *entry = cur; 558 SAVE_HINT(map, cur); 559 return(TRUE); 560 } 561 break; 562 } 563 cur = cur->next; 564 } 565 *entry = cur->prev; 566 SAVE_HINT(map, *entry); 567 return(FALSE); 568 } 569 570 /* 571 * vm_map_find finds an unallocated region in the target address 572 * map with the given length. The search is defined to be 573 * first-fit from the specified address; the region found is 574 * returned in the same parameter. 575 * 576 */ 577 vm_map_find(map, object, offset, addr, length, find_space) 578 vm_map_t map; 579 vm_object_t object; 580 vm_offset_t offset; 581 vm_offset_t *addr; /* IN/OUT */ 582 vm_size_t length; 583 boolean_t find_space; 584 { 585 register vm_map_entry_t entry; 586 register vm_offset_t start; 587 register vm_offset_t end; 588 int result; 589 590 start = *addr; 591 592 vm_map_lock(map); 593 594 if (find_space) { 595 /* 596 * Calculate the first possible address. 597 */ 598 599 if (start < map->min_offset) 600 start = map->min_offset; 601 if (start > map->max_offset) { 602 vm_map_unlock(map); 603 return (KERN_NO_SPACE); 604 } 605 606 /* 607 * Look for the first possible address; 608 * if there's already something at this 609 * address, we have to start after it. 610 */ 611 612 if (start == map->min_offset) { 613 if ((entry = map->first_free) != &map->header) 614 start = entry->end; 615 } else { 616 vm_map_entry_t tmp_entry; 617 if (vm_map_lookup_entry(map, start, &tmp_entry)) 618 start = tmp_entry->end; 619 entry = tmp_entry; 620 } 621 622 /* 623 * In any case, the "entry" always precedes 624 * the proposed new region throughout the 625 * loop: 626 */ 627 628 while (TRUE) { 629 register vm_map_entry_t next; 630 631 /* 632 * Find the end of the proposed new region. 633 * Be sure we didn't go beyond the end, or 634 * wrap around the address. 635 */ 636 637 end = start + length; 638 639 if ((end > map->max_offset) || (end < start)) { 640 vm_map_unlock(map); 641 return (KERN_NO_SPACE); 642 } 643 644 /* 645 * If there are no more entries, we must win. 646 */ 647 648 next = entry->next; 649 if (next == &map->header) 650 break; 651 652 /* 653 * If there is another entry, it must be 654 * after the end of the potential new region. 655 */ 656 657 if (next->start >= end) 658 break; 659 660 /* 661 * Didn't fit -- move to the next entry. 662 */ 663 664 entry = next; 665 start = entry->end; 666 } 667 *addr = start; 668 669 SAVE_HINT(map, entry); 670 } 671 672 result = vm_map_insert(map, object, offset, start, start + length); 673 674 vm_map_unlock(map); 675 return(result); 676 } 677 678 /* 679 * vm_map_simplify_entry: [ internal use only ] 680 * 681 * Simplify the given map entry by: 682 * removing extra sharing maps 683 * [XXX maybe later] merging with a neighbor 684 */ 685 void vm_map_simplify_entry(map, entry) 686 vm_map_t map; 687 vm_map_entry_t entry; 688 { 689 #ifdef lint 690 map++; 691 #endif lint 692 693 /* 694 * If this entry corresponds to a sharing map, then 695 * see if we can remove the level of indirection. 696 * If it's not a sharing map, then it points to 697 * a VM object, so see if we can merge with either 698 * of our neighbors. 699 */ 700 701 if (entry->is_sub_map) 702 return; 703 if (entry->is_a_map) { 704 #if 0 705 vm_map_t my_share_map; 706 int count; 707 708 my_share_map = entry->object.share_map; 709 simple_lock(&my_share_map->ref_lock); 710 count = my_share_map->ref_count; 711 simple_unlock(&my_share_map->ref_lock); 712 713 if (count == 1) { 714 /* Can move the region from 715 * entry->start to entry->end (+ entry->offset) 716 * in my_share_map into place of entry. 717 * Later. 718 */ 719 } 720 #endif 0 721 } 722 else { 723 /* 724 * Try to merge with our neighbors. 725 * 726 * Conditions for merge are: 727 * 728 * 1. entries are adjacent. 729 * 2. both entries point to objects 730 * with null pagers. 731 * 732 * If a merge is possible, we replace the two 733 * entries with a single entry, then merge 734 * the two objects into a single object. 735 * 736 * Now, all that is left to do is write the 737 * code! 738 */ 739 } 740 } 741 742 /* 743 * vm_map_clip_start: [ internal use only ] 744 * 745 * Asserts that the given entry begins at or after 746 * the specified address; if necessary, 747 * it splits the entry into two. 748 */ 749 #define vm_map_clip_start(map, entry, startaddr) \ 750 { \ 751 if (startaddr > entry->start) \ 752 _vm_map_clip_start(map, entry, startaddr); \ 753 } 754 755 /* 756 * This routine is called only when it is known that 757 * the entry must be split. 758 */ 759 void _vm_map_clip_start(map, entry, start) 760 register vm_map_t map; 761 register vm_map_entry_t entry; 762 register vm_offset_t start; 763 { 764 register vm_map_entry_t new_entry; 765 766 /* 767 * See if we can simplify this entry first 768 */ 769 770 vm_map_simplify_entry(map, entry); 771 772 /* 773 * Split off the front portion -- 774 * note that we must insert the new 775 * entry BEFORE this one, so that 776 * this entry has the specified starting 777 * address. 778 */ 779 780 new_entry = vm_map_entry_create(map); 781 *new_entry = *entry; 782 783 new_entry->end = start; 784 entry->offset += (start - entry->start); 785 entry->start = start; 786 787 vm_map_entry_link(map, entry->prev, new_entry); 788 789 if (entry->is_a_map || entry->is_sub_map) 790 vm_map_reference(new_entry->object.share_map); 791 else 792 vm_object_reference(new_entry->object.vm_object); 793 } 794 795 /* 796 * vm_map_clip_end: [ internal use only ] 797 * 798 * Asserts that the given entry ends at or before 799 * the specified address; if necessary, 800 * it splits the entry into two. 801 */ 802 803 void _vm_map_clip_end(); 804 #define vm_map_clip_end(map, entry, endaddr) \ 805 { \ 806 if (endaddr < entry->end) \ 807 _vm_map_clip_end(map, entry, endaddr); \ 808 } 809 810 /* 811 * This routine is called only when it is known that 812 * the entry must be split. 813 */ 814 void _vm_map_clip_end(map, entry, end) 815 register vm_map_t map; 816 register vm_map_entry_t entry; 817 register vm_offset_t end; 818 { 819 register vm_map_entry_t new_entry; 820 821 /* 822 * Create a new entry and insert it 823 * AFTER the specified entry 824 */ 825 826 new_entry = vm_map_entry_create(map); 827 *new_entry = *entry; 828 829 new_entry->start = entry->end = end; 830 new_entry->offset += (end - entry->start); 831 832 vm_map_entry_link(map, entry, new_entry); 833 834 if (entry->is_a_map || entry->is_sub_map) 835 vm_map_reference(new_entry->object.share_map); 836 else 837 vm_object_reference(new_entry->object.vm_object); 838 } 839 840 /* 841 * VM_MAP_RANGE_CHECK: [ internal use only ] 842 * 843 * Asserts that the starting and ending region 844 * addresses fall within the valid range of the map. 845 */ 846 #define VM_MAP_RANGE_CHECK(map, start, end) \ 847 { \ 848 if (start < vm_map_min(map)) \ 849 start = vm_map_min(map); \ 850 if (end > vm_map_max(map)) \ 851 end = vm_map_max(map); \ 852 if (start > end) \ 853 start = end; \ 854 } 855 856 /* 857 * vm_map_submap: [ kernel use only ] 858 * 859 * Mark the given range as handled by a subordinate map. 860 * 861 * This range must have been created with vm_map_find, 862 * and no other operations may have been performed on this 863 * range prior to calling vm_map_submap. 864 * 865 * Only a limited number of operations can be performed 866 * within this rage after calling vm_map_submap: 867 * vm_fault 868 * [Don't try vm_map_copy!] 869 * 870 * To remove a submapping, one must first remove the 871 * range from the superior map, and then destroy the 872 * submap (if desired). [Better yet, don't try it.] 873 */ 874 vm_map_submap(map, start, end, submap) 875 register vm_map_t map; 876 register vm_offset_t start; 877 register vm_offset_t end; 878 vm_map_t submap; 879 { 880 vm_map_entry_t entry; 881 register int result = KERN_INVALID_ARGUMENT; 882 883 vm_map_lock(map); 884 885 VM_MAP_RANGE_CHECK(map, start, end); 886 887 if (vm_map_lookup_entry(map, start, &entry)) { 888 vm_map_clip_start(map, entry, start); 889 } 890 else 891 entry = entry->next; 892 893 vm_map_clip_end(map, entry, end); 894 895 if ((entry->start == start) && (entry->end == end) && 896 (!entry->is_a_map) && 897 (entry->object.vm_object == NULL) && 898 (!entry->copy_on_write)) { 899 entry->is_a_map = FALSE; 900 entry->is_sub_map = TRUE; 901 vm_map_reference(entry->object.sub_map = submap); 902 result = KERN_SUCCESS; 903 } 904 vm_map_unlock(map); 905 906 return(result); 907 } 908 909 /* 910 * vm_map_protect: 911 * 912 * Sets the protection of the specified address 913 * region in the target map. If "set_max" is 914 * specified, the maximum protection is to be set; 915 * otherwise, only the current protection is affected. 916 */ 917 vm_map_protect(map, start, end, new_prot, set_max) 918 register vm_map_t map; 919 register vm_offset_t start; 920 register vm_offset_t end; 921 register vm_prot_t new_prot; 922 register boolean_t set_max; 923 { 924 register vm_map_entry_t current; 925 vm_map_entry_t entry; 926 927 vm_map_lock(map); 928 929 VM_MAP_RANGE_CHECK(map, start, end); 930 931 if (vm_map_lookup_entry(map, start, &entry)) { 932 vm_map_clip_start(map, entry, start); 933 } 934 else 935 entry = entry->next; 936 937 /* 938 * Make a first pass to check for protection 939 * violations. 940 */ 941 942 current = entry; 943 while ((current != &map->header) && (current->start < end)) { 944 if (current->is_sub_map) 945 return(KERN_INVALID_ARGUMENT); 946 if ((new_prot & current->max_protection) != new_prot) { 947 vm_map_unlock(map); 948 return(KERN_PROTECTION_FAILURE); 949 } 950 951 current = current->next; 952 } 953 954 /* 955 * Go back and fix up protections. 956 * [Note that clipping is not necessary the second time.] 957 */ 958 959 current = entry; 960 961 while ((current != &map->header) && (current->start < end)) { 962 vm_prot_t old_prot; 963 964 vm_map_clip_end(map, current, end); 965 966 old_prot = current->protection; 967 if (set_max) 968 current->protection = 969 (current->max_protection = new_prot) & 970 old_prot; 971 else 972 current->protection = new_prot; 973 974 /* 975 * Update physical map if necessary. 976 * Worry about copy-on-write here -- CHECK THIS XXX 977 */ 978 979 if (current->protection != old_prot) { 980 981 #define MASK(entry) ((entry)->copy_on_write ? ~VM_PROT_WRITE : \ 982 VM_PROT_ALL) 983 #define max(a,b) ((a) > (b) ? (a) : (b)) 984 985 if (current->is_a_map) { 986 vm_map_entry_t share_entry; 987 vm_offset_t share_end; 988 989 vm_map_lock(current->object.share_map); 990 (void) vm_map_lookup_entry( 991 current->object.share_map, 992 current->offset, 993 &share_entry); 994 share_end = current->offset + 995 (current->end - current->start); 996 while ((share_entry != 997 ¤t->object.share_map->header) && 998 (share_entry->start < share_end)) { 999 1000 pmap_protect(map->pmap, 1001 (max(share_entry->start, 1002 current->offset) - 1003 current->offset + 1004 current->start), 1005 min(share_entry->end, 1006 share_end) - 1007 current->offset + 1008 current->start, 1009 current->protection & 1010 MASK(share_entry)); 1011 1012 share_entry = share_entry->next; 1013 } 1014 vm_map_unlock(current->object.share_map); 1015 } 1016 else 1017 pmap_protect(map->pmap, current->start, 1018 current->end, 1019 current->protection & MASK(entry)); 1020 #undef max 1021 #undef MASK 1022 } 1023 current = current->next; 1024 } 1025 1026 vm_map_unlock(map); 1027 return(KERN_SUCCESS); 1028 } 1029 1030 /* 1031 * vm_map_inherit: 1032 * 1033 * Sets the inheritance of the specified address 1034 * range in the target map. Inheritance 1035 * affects how the map will be shared with 1036 * child maps at the time of vm_map_fork. 1037 */ 1038 vm_map_inherit(map, start, end, new_inheritance) 1039 register vm_map_t map; 1040 register vm_offset_t start; 1041 register vm_offset_t end; 1042 register vm_inherit_t new_inheritance; 1043 { 1044 register vm_map_entry_t entry; 1045 vm_map_entry_t temp_entry; 1046 1047 switch (new_inheritance) { 1048 case VM_INHERIT_NONE: 1049 case VM_INHERIT_COPY: 1050 case VM_INHERIT_SHARE: 1051 break; 1052 default: 1053 return(KERN_INVALID_ARGUMENT); 1054 } 1055 1056 vm_map_lock(map); 1057 1058 VM_MAP_RANGE_CHECK(map, start, end); 1059 1060 if (vm_map_lookup_entry(map, start, &temp_entry)) { 1061 entry = temp_entry; 1062 vm_map_clip_start(map, entry, start); 1063 } 1064 else 1065 entry = temp_entry->next; 1066 1067 while ((entry != &map->header) && (entry->start < end)) { 1068 vm_map_clip_end(map, entry, end); 1069 1070 entry->inheritance = new_inheritance; 1071 1072 entry = entry->next; 1073 } 1074 1075 vm_map_unlock(map); 1076 return(KERN_SUCCESS); 1077 } 1078 1079 /* 1080 * vm_map_pageable: 1081 * 1082 * Sets the pageability of the specified address 1083 * range in the target map. Regions specified 1084 * as not pageable require locked-down physical 1085 * memory and physical page maps. 1086 * 1087 * The map must not be locked, but a reference 1088 * must remain to the map throughout the call. 1089 */ 1090 vm_map_pageable(map, start, end, new_pageable) 1091 register vm_map_t map; 1092 register vm_offset_t start; 1093 register vm_offset_t end; 1094 register boolean_t new_pageable; 1095 { 1096 register vm_map_entry_t entry; 1097 vm_map_entry_t temp_entry; 1098 1099 vm_map_lock(map); 1100 1101 VM_MAP_RANGE_CHECK(map, start, end); 1102 1103 /* 1104 * Only one pageability change may take place at one 1105 * time, since vm_fault assumes it will be called 1106 * only once for each wiring/unwiring. Therefore, we 1107 * have to make sure we're actually changing the pageability 1108 * for the entire region. We do so before making any changes. 1109 */ 1110 1111 if (vm_map_lookup_entry(map, start, &temp_entry)) { 1112 entry = temp_entry; 1113 vm_map_clip_start(map, entry, start); 1114 } 1115 else 1116 entry = temp_entry->next; 1117 temp_entry = entry; 1118 1119 /* 1120 * Actions are rather different for wiring and unwiring, 1121 * so we have two separate cases. 1122 */ 1123 1124 if (new_pageable) { 1125 1126 /* 1127 * Unwiring. First ensure that the range to be 1128 * unwired is really wired down. 1129 */ 1130 while ((entry != &map->header) && (entry->start < end)) { 1131 1132 if (entry->wired_count == 0) { 1133 vm_map_unlock(map); 1134 return(KERN_INVALID_ARGUMENT); 1135 } 1136 entry = entry->next; 1137 } 1138 1139 /* 1140 * Now decrement the wiring count for each region. 1141 * If a region becomes completely unwired, 1142 * unwire its physical pages and mappings. 1143 */ 1144 lock_set_recursive(&map->lock); 1145 1146 entry = temp_entry; 1147 while ((entry != &map->header) && (entry->start < end)) { 1148 vm_map_clip_end(map, entry, end); 1149 1150 entry->wired_count--; 1151 if (entry->wired_count == 0) 1152 vm_fault_unwire(map, entry->start, entry->end); 1153 1154 entry = entry->next; 1155 } 1156 lock_clear_recursive(&map->lock); 1157 } 1158 1159 else { 1160 /* 1161 * Wiring. We must do this in two passes: 1162 * 1163 * 1. Holding the write lock, we increment the 1164 * wiring count. For any area that is not already 1165 * wired, we create any shadow objects that need 1166 * to be created. 1167 * 1168 * 2. We downgrade to a read lock, and call 1169 * vm_fault_wire to fault in the pages for any 1170 * newly wired area (wired_count is 1). 1171 * 1172 * Downgrading to a read lock for vm_fault_wire avoids 1173 * a possible deadlock with another thread that may have 1174 * faulted on one of the pages to be wired (it would mark 1175 * the page busy, blocking us, then in turn block on the 1176 * map lock that we hold). Because of problems in the 1177 * recursive lock package, we cannot upgrade to a write 1178 * lock in vm_map_lookup. Thus, any actions that require 1179 * the write lock must be done beforehand. Because we 1180 * keep the read lock on the map, the copy-on-write status 1181 * of the entries we modify here cannot change. 1182 */ 1183 1184 /* 1185 * Pass 1. 1186 */ 1187 entry = temp_entry; 1188 while ((entry != &map->header) && (entry->start < end)) { 1189 vm_map_clip_end(map, entry, end); 1190 1191 entry->wired_count++; 1192 if (entry->wired_count == 1) { 1193 1194 /* 1195 * Perform actions of vm_map_lookup that need 1196 * the write lock on the map: create a shadow 1197 * object for a copy-on-write region, or an 1198 * object for a zero-fill region. 1199 * 1200 * We don't have to do this for entries that 1201 * point to sharing maps, because we won't hold 1202 * the lock on the sharing map. 1203 */ 1204 if (!entry->is_a_map) { 1205 if (entry->needs_copy && 1206 ((entry->protection & VM_PROT_WRITE) != 0)) { 1207 1208 vm_object_shadow(&entry->object.vm_object, 1209 &entry->offset, 1210 (vm_size_t)(entry->end 1211 - entry->start)); 1212 entry->needs_copy = FALSE; 1213 } 1214 else if (entry->object.vm_object == NULL) { 1215 entry->object.vm_object = 1216 vm_object_allocate((vm_size_t)(entry->end 1217 - entry->start)); 1218 entry->offset = (vm_offset_t)0; 1219 } 1220 } 1221 } 1222 1223 entry = entry->next; 1224 } 1225 1226 /* 1227 * Pass 2. 1228 */ 1229 1230 /* 1231 * HACK HACK HACK HACK 1232 * 1233 * If we are wiring in the kernel map or a submap of it, 1234 * unlock the map to avoid deadlocks. We trust that the 1235 * kernel threads are well-behaved, and therefore will 1236 * not do anything destructive to this region of the map 1237 * while we have it unlocked. We cannot trust user threads 1238 * to do the same. 1239 * 1240 * HACK HACK HACK HACK 1241 */ 1242 if (vm_map_pmap(map) == kernel_pmap) { 1243 vm_map_unlock(map); /* trust me ... */ 1244 } 1245 else { 1246 lock_set_recursive(&map->lock); 1247 lock_write_to_read(&map->lock); 1248 } 1249 1250 entry = temp_entry; 1251 while (entry != &map->header && entry->start < end) { 1252 if (entry->wired_count == 1) { 1253 vm_fault_wire(map, entry->start, entry->end); 1254 } 1255 entry = entry->next; 1256 } 1257 1258 if (vm_map_pmap(map) == kernel_pmap) { 1259 vm_map_lock(map); 1260 } 1261 else { 1262 lock_clear_recursive(&map->lock); 1263 } 1264 } 1265 1266 vm_map_unlock(map); 1267 1268 return(KERN_SUCCESS); 1269 } 1270 1271 /* 1272 * vm_map_entry_unwire: [ internal use only ] 1273 * 1274 * Make the region specified by this entry pageable. 1275 * 1276 * The map in question should be locked. 1277 * [This is the reason for this routine's existence.] 1278 */ 1279 void vm_map_entry_unwire(map, entry) 1280 vm_map_t map; 1281 register vm_map_entry_t entry; 1282 { 1283 vm_fault_unwire(map, entry->start, entry->end); 1284 entry->wired_count = 0; 1285 } 1286 1287 /* 1288 * vm_map_entry_delete: [ internal use only ] 1289 * 1290 * Deallocate the given entry from the target map. 1291 */ 1292 void vm_map_entry_delete(map, entry) 1293 register vm_map_t map; 1294 register vm_map_entry_t entry; 1295 { 1296 if (entry->wired_count != 0) 1297 vm_map_entry_unwire(map, entry); 1298 1299 vm_map_entry_unlink(map, entry); 1300 map->size -= entry->end - entry->start; 1301 1302 if (entry->is_a_map || entry->is_sub_map) 1303 vm_map_deallocate(entry->object.share_map); 1304 else 1305 vm_object_deallocate(entry->object.vm_object); 1306 1307 vm_map_entry_dispose(map, entry); 1308 } 1309 1310 /* 1311 * vm_map_delete: [ internal use only ] 1312 * 1313 * Deallocates the given address range from the target 1314 * map. 1315 * 1316 * When called with a sharing map, removes pages from 1317 * that region from all physical maps. 1318 */ 1319 vm_map_delete(map, start, end) 1320 register vm_map_t map; 1321 vm_offset_t start; 1322 register vm_offset_t end; 1323 { 1324 register vm_map_entry_t entry; 1325 vm_map_entry_t first_entry; 1326 1327 /* 1328 * Find the start of the region, and clip it 1329 */ 1330 1331 if (!vm_map_lookup_entry(map, start, &first_entry)) 1332 entry = first_entry->next; 1333 else { 1334 entry = first_entry; 1335 vm_map_clip_start(map, entry, start); 1336 1337 /* 1338 * Fix the lookup hint now, rather than each 1339 * time though the loop. 1340 */ 1341 1342 SAVE_HINT(map, entry->prev); 1343 } 1344 1345 /* 1346 * Save the free space hint 1347 */ 1348 1349 if (map->first_free->start >= start) 1350 map->first_free = entry->prev; 1351 1352 /* 1353 * Step through all entries in this region 1354 */ 1355 1356 while ((entry != &map->header) && (entry->start < end)) { 1357 vm_map_entry_t next; 1358 register vm_offset_t s, e; 1359 register vm_object_t object; 1360 1361 vm_map_clip_end(map, entry, end); 1362 1363 next = entry->next; 1364 s = entry->start; 1365 e = entry->end; 1366 1367 /* 1368 * Unwire before removing addresses from the pmap; 1369 * otherwise, unwiring will put the entries back in 1370 * the pmap. 1371 */ 1372 1373 object = entry->object.vm_object; 1374 if (entry->wired_count != 0) 1375 vm_map_entry_unwire(map, entry); 1376 1377 /* 1378 * If this is a sharing map, we must remove 1379 * *all* references to this data, since we can't 1380 * find all of the physical maps which are sharing 1381 * it. 1382 */ 1383 1384 if (object == kernel_object || object == kmem_object) 1385 vm_object_page_remove(object, entry->offset, 1386 entry->offset + (e - s)); 1387 else if (!map->is_main_map) 1388 vm_object_pmap_remove(object, 1389 entry->offset, 1390 entry->offset + (e - s)); 1391 else 1392 pmap_remove(map->pmap, s, e); 1393 1394 /* 1395 * Delete the entry (which may delete the object) 1396 * only after removing all pmap entries pointing 1397 * to its pages. (Otherwise, its page frames may 1398 * be reallocated, and any modify bits will be 1399 * set in the wrong object!) 1400 */ 1401 1402 vm_map_entry_delete(map, entry); 1403 entry = next; 1404 } 1405 return(KERN_SUCCESS); 1406 } 1407 1408 /* 1409 * vm_map_remove: 1410 * 1411 * Remove the given address range from the target map. 1412 * This is the exported form of vm_map_delete. 1413 */ 1414 vm_map_remove(map, start, end) 1415 register vm_map_t map; 1416 register vm_offset_t start; 1417 register vm_offset_t end; 1418 { 1419 register int result; 1420 1421 vm_map_lock(map); 1422 VM_MAP_RANGE_CHECK(map, start, end); 1423 result = vm_map_delete(map, start, end); 1424 vm_map_unlock(map); 1425 1426 return(result); 1427 } 1428 1429 /* 1430 * vm_map_check_protection: 1431 * 1432 * Assert that the target map allows the specified 1433 * privilege on the entire address region given. 1434 * The entire region must be allocated. 1435 */ 1436 boolean_t vm_map_check_protection(map, start, end, protection) 1437 register vm_map_t map; 1438 register vm_offset_t start; 1439 register vm_offset_t end; 1440 register vm_prot_t protection; 1441 { 1442 register vm_map_entry_t entry; 1443 vm_map_entry_t tmp_entry; 1444 1445 if (!vm_map_lookup_entry(map, start, &tmp_entry)) { 1446 return(FALSE); 1447 } 1448 1449 entry = tmp_entry; 1450 1451 while (start < end) { 1452 if (entry == &map->header) { 1453 return(FALSE); 1454 } 1455 1456 /* 1457 * No holes allowed! 1458 */ 1459 1460 if (start < entry->start) { 1461 return(FALSE); 1462 } 1463 1464 /* 1465 * Check protection associated with entry. 1466 */ 1467 1468 if ((entry->protection & protection) != protection) { 1469 return(FALSE); 1470 } 1471 1472 /* go to next entry */ 1473 1474 start = entry->end; 1475 entry = entry->next; 1476 } 1477 return(TRUE); 1478 } 1479 1480 /* 1481 * vm_map_copy_entry: 1482 * 1483 * Copies the contents of the source entry to the destination 1484 * entry. The entries *must* be aligned properly. 1485 */ 1486 void vm_map_copy_entry(src_map, dst_map, src_entry, dst_entry) 1487 vm_map_t src_map, dst_map; 1488 register vm_map_entry_t src_entry, dst_entry; 1489 { 1490 vm_object_t temp_object; 1491 1492 if (src_entry->is_sub_map || dst_entry->is_sub_map) 1493 return; 1494 1495 if (dst_entry->object.vm_object != NULL && 1496 !dst_entry->object.vm_object->internal) 1497 printf("vm_map_copy_entry: copying over permanent data!\n"); 1498 1499 /* 1500 * If our destination map was wired down, 1501 * unwire it now. 1502 */ 1503 1504 if (dst_entry->wired_count != 0) 1505 vm_map_entry_unwire(dst_map, dst_entry); 1506 1507 /* 1508 * If we're dealing with a sharing map, we 1509 * must remove the destination pages from 1510 * all maps (since we cannot know which maps 1511 * this sharing map belongs in). 1512 */ 1513 1514 if (dst_map->is_main_map) 1515 pmap_remove(dst_map->pmap, dst_entry->start, dst_entry->end); 1516 else 1517 vm_object_pmap_remove(dst_entry->object.vm_object, 1518 dst_entry->offset, 1519 dst_entry->offset + 1520 (dst_entry->end - dst_entry->start)); 1521 1522 if (src_entry->wired_count == 0) { 1523 1524 boolean_t src_needs_copy; 1525 1526 /* 1527 * If the source entry is marked needs_copy, 1528 * it is already write-protected. 1529 */ 1530 if (!src_entry->needs_copy) { 1531 1532 boolean_t su; 1533 1534 /* 1535 * If the source entry has only one mapping, 1536 * we can just protect the virtual address 1537 * range. 1538 */ 1539 if (!(su = src_map->is_main_map)) { 1540 simple_lock(&src_map->ref_lock); 1541 su = (src_map->ref_count == 1); 1542 simple_unlock(&src_map->ref_lock); 1543 } 1544 1545 if (su) { 1546 pmap_protect(src_map->pmap, 1547 src_entry->start, 1548 src_entry->end, 1549 src_entry->protection & ~VM_PROT_WRITE); 1550 } 1551 else { 1552 vm_object_pmap_copy(src_entry->object.vm_object, 1553 src_entry->offset, 1554 src_entry->offset + (src_entry->end 1555 -src_entry->start)); 1556 } 1557 } 1558 1559 /* 1560 * Make a copy of the object. 1561 */ 1562 temp_object = dst_entry->object.vm_object; 1563 vm_object_copy(src_entry->object.vm_object, 1564 src_entry->offset, 1565 (vm_size_t)(src_entry->end - 1566 src_entry->start), 1567 &dst_entry->object.vm_object, 1568 &dst_entry->offset, 1569 &src_needs_copy); 1570 /* 1571 * If we didn't get a copy-object now, mark the 1572 * source map entry so that a shadow will be created 1573 * to hold its changed pages. 1574 */ 1575 if (src_needs_copy) 1576 src_entry->needs_copy = TRUE; 1577 1578 /* 1579 * The destination always needs to have a shadow 1580 * created. 1581 */ 1582 dst_entry->needs_copy = TRUE; 1583 1584 /* 1585 * Mark the entries copy-on-write, so that write-enabling 1586 * the entry won't make copy-on-write pages writable. 1587 */ 1588 src_entry->copy_on_write = TRUE; 1589 dst_entry->copy_on_write = TRUE; 1590 /* 1591 * Get rid of the old object. 1592 */ 1593 vm_object_deallocate(temp_object); 1594 1595 pmap_copy(dst_map->pmap, src_map->pmap, dst_entry->start, 1596 dst_entry->end - dst_entry->start, src_entry->start); 1597 } 1598 else { 1599 /* 1600 * Of course, wired down pages can't be set copy-on-write. 1601 * Cause wired pages to be copied into the new 1602 * map by simulating faults (the new pages are 1603 * pageable) 1604 */ 1605 vm_fault_copy_entry(dst_map, src_map, dst_entry, src_entry); 1606 } 1607 } 1608 1609 /* 1610 * vm_map_copy: 1611 * 1612 * Perform a virtual memory copy from the source 1613 * address map/range to the destination map/range. 1614 * 1615 * If src_destroy or dst_alloc is requested, 1616 * the source and destination regions should be 1617 * disjoint, not only in the top-level map, but 1618 * in the sharing maps as well. [The best way 1619 * to guarantee this is to use a new intermediate 1620 * map to make copies. This also reduces map 1621 * fragmentation.] 1622 */ 1623 vm_map_copy(dst_map, src_map, 1624 dst_addr, len, src_addr, 1625 dst_alloc, src_destroy) 1626 vm_map_t dst_map; 1627 vm_map_t src_map; 1628 vm_offset_t dst_addr; 1629 vm_size_t len; 1630 vm_offset_t src_addr; 1631 boolean_t dst_alloc; 1632 boolean_t src_destroy; 1633 { 1634 register 1635 vm_map_entry_t src_entry; 1636 register 1637 vm_map_entry_t dst_entry; 1638 vm_map_entry_t tmp_entry; 1639 vm_offset_t src_start; 1640 vm_offset_t src_end; 1641 vm_offset_t dst_start; 1642 vm_offset_t dst_end; 1643 vm_offset_t src_clip; 1644 vm_offset_t dst_clip; 1645 int result; 1646 boolean_t old_src_destroy; 1647 1648 /* 1649 * XXX While we figure out why src_destroy screws up, 1650 * we'll do it by explicitly vm_map_delete'ing at the end. 1651 */ 1652 1653 old_src_destroy = src_destroy; 1654 src_destroy = FALSE; 1655 1656 /* 1657 * Compute start and end of region in both maps 1658 */ 1659 1660 src_start = src_addr; 1661 src_end = src_start + len; 1662 dst_start = dst_addr; 1663 dst_end = dst_start + len; 1664 1665 /* 1666 * Check that the region can exist in both source 1667 * and destination. 1668 */ 1669 1670 if ((dst_end < dst_start) || (src_end < src_start)) 1671 return(KERN_NO_SPACE); 1672 1673 /* 1674 * Lock the maps in question -- we avoid deadlock 1675 * by ordering lock acquisition by map value 1676 */ 1677 1678 if (src_map == dst_map) { 1679 vm_map_lock(src_map); 1680 } 1681 else if ((int) src_map < (int) dst_map) { 1682 vm_map_lock(src_map); 1683 vm_map_lock(dst_map); 1684 } else { 1685 vm_map_lock(dst_map); 1686 vm_map_lock(src_map); 1687 } 1688 1689 result = KERN_SUCCESS; 1690 1691 /* 1692 * Check protections... source must be completely readable and 1693 * destination must be completely writable. [Note that if we're 1694 * allocating the destination region, we don't have to worry 1695 * about protection, but instead about whether the region 1696 * exists.] 1697 */ 1698 1699 if (src_map->is_main_map && dst_map->is_main_map) { 1700 if (!vm_map_check_protection(src_map, src_start, src_end, 1701 VM_PROT_READ)) { 1702 result = KERN_PROTECTION_FAILURE; 1703 goto Return; 1704 } 1705 1706 if (dst_alloc) { 1707 /* XXX Consider making this a vm_map_find instead */ 1708 if ((result = vm_map_insert(dst_map, NULL, 1709 (vm_offset_t) 0, dst_start, dst_end)) != KERN_SUCCESS) 1710 goto Return; 1711 } 1712 else if (!vm_map_check_protection(dst_map, dst_start, dst_end, 1713 VM_PROT_WRITE)) { 1714 result = KERN_PROTECTION_FAILURE; 1715 goto Return; 1716 } 1717 } 1718 1719 /* 1720 * Find the start entries and clip. 1721 * 1722 * Note that checking protection asserts that the 1723 * lookup cannot fail. 1724 * 1725 * Also note that we wait to do the second lookup 1726 * until we have done the first clip, as the clip 1727 * may affect which entry we get! 1728 */ 1729 1730 (void) vm_map_lookup_entry(src_map, src_addr, &tmp_entry); 1731 src_entry = tmp_entry; 1732 vm_map_clip_start(src_map, src_entry, src_start); 1733 1734 (void) vm_map_lookup_entry(dst_map, dst_addr, &tmp_entry); 1735 dst_entry = tmp_entry; 1736 vm_map_clip_start(dst_map, dst_entry, dst_start); 1737 1738 /* 1739 * If both source and destination entries are the same, 1740 * retry the first lookup, as it may have changed. 1741 */ 1742 1743 if (src_entry == dst_entry) { 1744 (void) vm_map_lookup_entry(src_map, src_addr, &tmp_entry); 1745 src_entry = tmp_entry; 1746 } 1747 1748 /* 1749 * If source and destination entries are still the same, 1750 * a null copy is being performed. 1751 */ 1752 1753 if (src_entry == dst_entry) 1754 goto Return; 1755 1756 /* 1757 * Go through entries until we get to the end of the 1758 * region. 1759 */ 1760 1761 while (src_start < src_end) { 1762 /* 1763 * Clip the entries to the endpoint of the entire region. 1764 */ 1765 1766 vm_map_clip_end(src_map, src_entry, src_end); 1767 vm_map_clip_end(dst_map, dst_entry, dst_end); 1768 1769 /* 1770 * Clip each entry to the endpoint of the other entry. 1771 */ 1772 1773 src_clip = src_entry->start + (dst_entry->end - dst_entry->start); 1774 vm_map_clip_end(src_map, src_entry, src_clip); 1775 1776 dst_clip = dst_entry->start + (src_entry->end - src_entry->start); 1777 vm_map_clip_end(dst_map, dst_entry, dst_clip); 1778 1779 /* 1780 * Both entries now match in size and relative endpoints. 1781 * 1782 * If both entries refer to a VM object, we can 1783 * deal with them now. 1784 */ 1785 1786 if (!src_entry->is_a_map && !dst_entry->is_a_map) { 1787 vm_map_copy_entry(src_map, dst_map, src_entry, 1788 dst_entry); 1789 } 1790 else { 1791 register vm_map_t new_dst_map; 1792 vm_offset_t new_dst_start; 1793 vm_size_t new_size; 1794 vm_map_t new_src_map; 1795 vm_offset_t new_src_start; 1796 1797 /* 1798 * We have to follow at least one sharing map. 1799 */ 1800 1801 new_size = (dst_entry->end - dst_entry->start); 1802 1803 if (src_entry->is_a_map) { 1804 new_src_map = src_entry->object.share_map; 1805 new_src_start = src_entry->offset; 1806 } 1807 else { 1808 new_src_map = src_map; 1809 new_src_start = src_entry->start; 1810 lock_set_recursive(&src_map->lock); 1811 } 1812 1813 if (dst_entry->is_a_map) { 1814 vm_offset_t new_dst_end; 1815 1816 new_dst_map = dst_entry->object.share_map; 1817 new_dst_start = dst_entry->offset; 1818 1819 /* 1820 * Since the destination sharing entries 1821 * will be merely deallocated, we can 1822 * do that now, and replace the region 1823 * with a null object. [This prevents 1824 * splitting the source map to match 1825 * the form of the destination map.] 1826 * Note that we can only do so if the 1827 * source and destination do not overlap. 1828 */ 1829 1830 new_dst_end = new_dst_start + new_size; 1831 1832 if (new_dst_map != new_src_map) { 1833 vm_map_lock(new_dst_map); 1834 (void) vm_map_delete(new_dst_map, 1835 new_dst_start, 1836 new_dst_end); 1837 (void) vm_map_insert(new_dst_map, 1838 NULL, 1839 (vm_offset_t) 0, 1840 new_dst_start, 1841 new_dst_end); 1842 vm_map_unlock(new_dst_map); 1843 } 1844 } 1845 else { 1846 new_dst_map = dst_map; 1847 new_dst_start = dst_entry->start; 1848 lock_set_recursive(&dst_map->lock); 1849 } 1850 1851 /* 1852 * Recursively copy the sharing map. 1853 */ 1854 1855 (void) vm_map_copy(new_dst_map, new_src_map, 1856 new_dst_start, new_size, new_src_start, 1857 FALSE, FALSE); 1858 1859 if (dst_map == new_dst_map) 1860 lock_clear_recursive(&dst_map->lock); 1861 if (src_map == new_src_map) 1862 lock_clear_recursive(&src_map->lock); 1863 } 1864 1865 /* 1866 * Update variables for next pass through the loop. 1867 */ 1868 1869 src_start = src_entry->end; 1870 src_entry = src_entry->next; 1871 dst_start = dst_entry->end; 1872 dst_entry = dst_entry->next; 1873 1874 /* 1875 * If the source is to be destroyed, here is the 1876 * place to do it. 1877 */ 1878 1879 if (src_destroy && src_map->is_main_map && 1880 dst_map->is_main_map) 1881 vm_map_entry_delete(src_map, src_entry->prev); 1882 } 1883 1884 /* 1885 * Update the physical maps as appropriate 1886 */ 1887 1888 if (src_map->is_main_map && dst_map->is_main_map) { 1889 if (src_destroy) 1890 pmap_remove(src_map->pmap, src_addr, src_addr + len); 1891 } 1892 1893 /* 1894 * Unlock the maps 1895 */ 1896 1897 Return: ; 1898 1899 if (old_src_destroy) 1900 vm_map_delete(src_map, src_addr, src_addr + len); 1901 1902 vm_map_unlock(src_map); 1903 if (src_map != dst_map) 1904 vm_map_unlock(dst_map); 1905 1906 return(result); 1907 } 1908 1909 /* 1910 * vmspace_fork: 1911 * Create a new process vmspace structure and vm_map 1912 * based on those of an existing process. The new map 1913 * is based on the old map, according to the inheritance 1914 * values on the regions in that map. 1915 * 1916 * The source map must not be locked. 1917 */ 1918 struct vmspace * 1919 vmspace_fork(vm1) 1920 register struct vmspace *vm1; 1921 { 1922 register struct vmspace *vm2; 1923 vm_map_t old_map = &vm1->vm_map; 1924 vm_map_t new_map; 1925 vm_map_entry_t old_entry; 1926 vm_map_entry_t new_entry; 1927 pmap_t new_pmap; 1928 1929 vm_map_lock(old_map); 1930 1931 vm2 = vmspace_alloc(old_map->min_offset, old_map->max_offset, 1932 old_map->entries_pageable); 1933 bcopy(&vm1->vm_startcopy, &vm2->vm_startcopy, 1934 (caddr_t) (vm1 + 1) - (caddr_t) &vm1->vm_startcopy); 1935 new_pmap = &vm2->vm_pmap; /* XXX */ 1936 new_map = &vm2->vm_map; /* XXX */ 1937 1938 old_entry = old_map->header.next; 1939 1940 while (old_entry != &old_map->header) { 1941 if (old_entry->is_sub_map) 1942 panic("vm_map_fork: encountered a submap"); 1943 1944 switch (old_entry->inheritance) { 1945 case VM_INHERIT_NONE: 1946 break; 1947 1948 case VM_INHERIT_SHARE: 1949 /* 1950 * If we don't already have a sharing map: 1951 */ 1952 1953 if (!old_entry->is_a_map) { 1954 vm_map_t new_share_map; 1955 vm_map_entry_t new_share_entry; 1956 1957 /* 1958 * Create a new sharing map 1959 */ 1960 1961 new_share_map = vm_map_create(NULL, 1962 old_entry->start, 1963 old_entry->end, 1964 TRUE); 1965 new_share_map->is_main_map = FALSE; 1966 1967 /* 1968 * Create the only sharing entry from the 1969 * old task map entry. 1970 */ 1971 1972 new_share_entry = 1973 vm_map_entry_create(new_share_map); 1974 *new_share_entry = *old_entry; 1975 1976 /* 1977 * Insert the entry into the new sharing 1978 * map 1979 */ 1980 1981 vm_map_entry_link(new_share_map, 1982 new_share_map->header.prev, 1983 new_share_entry); 1984 1985 /* 1986 * Fix up the task map entry to refer 1987 * to the sharing map now. 1988 */ 1989 1990 old_entry->is_a_map = TRUE; 1991 old_entry->object.share_map = new_share_map; 1992 old_entry->offset = old_entry->start; 1993 } 1994 1995 /* 1996 * Clone the entry, referencing the sharing map. 1997 */ 1998 1999 new_entry = vm_map_entry_create(new_map); 2000 *new_entry = *old_entry; 2001 vm_map_reference(new_entry->object.share_map); 2002 2003 /* 2004 * Insert the entry into the new map -- we 2005 * know we're inserting at the end of the new 2006 * map. 2007 */ 2008 2009 vm_map_entry_link(new_map, new_map->header.prev, 2010 new_entry); 2011 2012 /* 2013 * Update the physical map 2014 */ 2015 2016 pmap_copy(new_map->pmap, old_map->pmap, 2017 new_entry->start, 2018 (old_entry->end - old_entry->start), 2019 old_entry->start); 2020 break; 2021 2022 case VM_INHERIT_COPY: 2023 /* 2024 * Clone the entry and link into the map. 2025 */ 2026 2027 new_entry = vm_map_entry_create(new_map); 2028 *new_entry = *old_entry; 2029 new_entry->wired_count = 0; 2030 new_entry->object.vm_object = NULL; 2031 new_entry->is_a_map = FALSE; 2032 vm_map_entry_link(new_map, new_map->header.prev, 2033 new_entry); 2034 if (old_entry->is_a_map) { 2035 int check; 2036 2037 check = vm_map_copy(new_map, 2038 old_entry->object.share_map, 2039 new_entry->start, 2040 (vm_size_t)(new_entry->end - 2041 new_entry->start), 2042 old_entry->offset, 2043 FALSE, FALSE); 2044 if (check != KERN_SUCCESS) 2045 printf("vm_map_fork: copy in share_map region failed\n"); 2046 } 2047 else { 2048 vm_map_copy_entry(old_map, new_map, old_entry, 2049 new_entry); 2050 } 2051 break; 2052 } 2053 old_entry = old_entry->next; 2054 } 2055 2056 new_map->size = old_map->size; 2057 vm_map_unlock(old_map); 2058 2059 return(vm2); 2060 } 2061 2062 /* 2063 * vm_map_lookup: 2064 * 2065 * Finds the VM object, offset, and 2066 * protection for a given virtual address in the 2067 * specified map, assuming a page fault of the 2068 * type specified. 2069 * 2070 * Leaves the map in question locked for read; return 2071 * values are guaranteed until a vm_map_lookup_done 2072 * call is performed. Note that the map argument 2073 * is in/out; the returned map must be used in 2074 * the call to vm_map_lookup_done. 2075 * 2076 * A handle (out_entry) is returned for use in 2077 * vm_map_lookup_done, to make that fast. 2078 * 2079 * If a lookup is requested with "write protection" 2080 * specified, the map may be changed to perform virtual 2081 * copying operations, although the data referenced will 2082 * remain the same. 2083 */ 2084 vm_map_lookup(var_map, vaddr, fault_type, out_entry, 2085 object, offset, out_prot, wired, single_use) 2086 vm_map_t *var_map; /* IN/OUT */ 2087 register vm_offset_t vaddr; 2088 register vm_prot_t fault_type; 2089 2090 vm_map_entry_t *out_entry; /* OUT */ 2091 vm_object_t *object; /* OUT */ 2092 vm_offset_t *offset; /* OUT */ 2093 vm_prot_t *out_prot; /* OUT */ 2094 boolean_t *wired; /* OUT */ 2095 boolean_t *single_use; /* OUT */ 2096 { 2097 vm_map_t share_map; 2098 vm_offset_t share_offset; 2099 register vm_map_entry_t entry; 2100 register vm_map_t map = *var_map; 2101 register vm_prot_t prot; 2102 register boolean_t su; 2103 2104 RetryLookup: ; 2105 2106 /* 2107 * Lookup the faulting address. 2108 */ 2109 2110 vm_map_lock_read(map); 2111 2112 #define RETURN(why) \ 2113 { \ 2114 vm_map_unlock_read(map); \ 2115 return(why); \ 2116 } 2117 2118 /* 2119 * If the map has an interesting hint, try it before calling 2120 * full blown lookup routine. 2121 */ 2122 2123 simple_lock(&map->hint_lock); 2124 entry = map->hint; 2125 simple_unlock(&map->hint_lock); 2126 2127 *out_entry = entry; 2128 2129 if ((entry == &map->header) || 2130 (vaddr < entry->start) || (vaddr >= entry->end)) { 2131 vm_map_entry_t tmp_entry; 2132 2133 /* 2134 * Entry was either not a valid hint, or the vaddr 2135 * was not contained in the entry, so do a full lookup. 2136 */ 2137 if (!vm_map_lookup_entry(map, vaddr, &tmp_entry)) 2138 RETURN(KERN_INVALID_ADDRESS); 2139 2140 entry = tmp_entry; 2141 *out_entry = entry; 2142 } 2143 2144 /* 2145 * Handle submaps. 2146 */ 2147 2148 if (entry->is_sub_map) { 2149 vm_map_t old_map = map; 2150 2151 *var_map = map = entry->object.sub_map; 2152 vm_map_unlock_read(old_map); 2153 goto RetryLookup; 2154 } 2155 2156 /* 2157 * Check whether this task is allowed to have 2158 * this page. 2159 */ 2160 2161 prot = entry->protection; 2162 if ((fault_type & (prot)) != fault_type) 2163 RETURN(KERN_PROTECTION_FAILURE); 2164 2165 /* 2166 * If this page is not pageable, we have to get 2167 * it for all possible accesses. 2168 */ 2169 2170 if (*wired = (entry->wired_count != 0)) 2171 prot = fault_type = entry->protection; 2172 2173 /* 2174 * If we don't already have a VM object, track 2175 * it down. 2176 */ 2177 2178 if (su = !entry->is_a_map) { 2179 share_map = map; 2180 share_offset = vaddr; 2181 } 2182 else { 2183 vm_map_entry_t share_entry; 2184 2185 /* 2186 * Compute the sharing map, and offset into it. 2187 */ 2188 2189 share_map = entry->object.share_map; 2190 share_offset = (vaddr - entry->start) + entry->offset; 2191 2192 /* 2193 * Look for the backing store object and offset 2194 */ 2195 2196 vm_map_lock_read(share_map); 2197 2198 if (!vm_map_lookup_entry(share_map, share_offset, 2199 &share_entry)) { 2200 vm_map_unlock_read(share_map); 2201 RETURN(KERN_INVALID_ADDRESS); 2202 } 2203 entry = share_entry; 2204 } 2205 2206 /* 2207 * If the entry was copy-on-write, we either ... 2208 */ 2209 2210 if (entry->needs_copy) { 2211 /* 2212 * If we want to write the page, we may as well 2213 * handle that now since we've got the sharing 2214 * map locked. 2215 * 2216 * If we don't need to write the page, we just 2217 * demote the permissions allowed. 2218 */ 2219 2220 if (fault_type & VM_PROT_WRITE) { 2221 /* 2222 * Make a new object, and place it in the 2223 * object chain. Note that no new references 2224 * have appeared -- one just moved from the 2225 * share map to the new object. 2226 */ 2227 2228 if (lock_read_to_write(&share_map->lock)) { 2229 if (share_map != map) 2230 vm_map_unlock_read(map); 2231 goto RetryLookup; 2232 } 2233 2234 vm_object_shadow( 2235 &entry->object.vm_object, 2236 &entry->offset, 2237 (vm_size_t) (entry->end - entry->start)); 2238 2239 entry->needs_copy = FALSE; 2240 2241 lock_write_to_read(&share_map->lock); 2242 } 2243 else { 2244 /* 2245 * We're attempting to read a copy-on-write 2246 * page -- don't allow writes. 2247 */ 2248 2249 prot &= (~VM_PROT_WRITE); 2250 } 2251 } 2252 2253 /* 2254 * Create an object if necessary. 2255 */ 2256 if (entry->object.vm_object == NULL) { 2257 2258 if (lock_read_to_write(&share_map->lock)) { 2259 if (share_map != map) 2260 vm_map_unlock_read(map); 2261 goto RetryLookup; 2262 } 2263 2264 entry->object.vm_object = vm_object_allocate( 2265 (vm_size_t)(entry->end - entry->start)); 2266 entry->offset = 0; 2267 lock_write_to_read(&share_map->lock); 2268 } 2269 2270 /* 2271 * Return the object/offset from this entry. If the entry 2272 * was copy-on-write or empty, it has been fixed up. 2273 */ 2274 2275 *offset = (share_offset - entry->start) + entry->offset; 2276 *object = entry->object.vm_object; 2277 2278 /* 2279 * Return whether this is the only map sharing this data. 2280 */ 2281 2282 if (!su) { 2283 simple_lock(&share_map->ref_lock); 2284 su = (share_map->ref_count == 1); 2285 simple_unlock(&share_map->ref_lock); 2286 } 2287 2288 *out_prot = prot; 2289 *single_use = su; 2290 2291 return(KERN_SUCCESS); 2292 2293 #undef RETURN 2294 } 2295 2296 /* 2297 * vm_map_lookup_done: 2298 * 2299 * Releases locks acquired by a vm_map_lookup 2300 * (according to the handle returned by that lookup). 2301 */ 2302 2303 void vm_map_lookup_done(map, entry) 2304 register vm_map_t map; 2305 vm_map_entry_t entry; 2306 { 2307 /* 2308 * If this entry references a map, unlock it first. 2309 */ 2310 2311 if (entry->is_a_map) 2312 vm_map_unlock_read(entry->object.share_map); 2313 2314 /* 2315 * Unlock the main-level map 2316 */ 2317 2318 vm_map_unlock_read(map); 2319 } 2320 2321 /* 2322 * Routine: vm_map_simplify 2323 * Purpose: 2324 * Attempt to simplify the map representation in 2325 * the vicinity of the given starting address. 2326 * Note: 2327 * This routine is intended primarily to keep the 2328 * kernel maps more compact -- they generally don't 2329 * benefit from the "expand a map entry" technology 2330 * at allocation time because the adjacent entry 2331 * is often wired down. 2332 */ 2333 void vm_map_simplify(map, start) 2334 vm_map_t map; 2335 vm_offset_t start; 2336 { 2337 vm_map_entry_t this_entry; 2338 vm_map_entry_t prev_entry; 2339 2340 vm_map_lock(map); 2341 if ( 2342 (vm_map_lookup_entry(map, start, &this_entry)) && 2343 ((prev_entry = this_entry->prev) != &map->header) && 2344 2345 (prev_entry->end == start) && 2346 (map->is_main_map) && 2347 2348 (prev_entry->is_a_map == FALSE) && 2349 (prev_entry->is_sub_map == FALSE) && 2350 2351 (this_entry->is_a_map == FALSE) && 2352 (this_entry->is_sub_map == FALSE) && 2353 2354 (prev_entry->inheritance == this_entry->inheritance) && 2355 (prev_entry->protection == this_entry->protection) && 2356 (prev_entry->max_protection == this_entry->max_protection) && 2357 (prev_entry->wired_count == this_entry->wired_count) && 2358 2359 (prev_entry->copy_on_write == this_entry->copy_on_write) && 2360 (prev_entry->needs_copy == this_entry->needs_copy) && 2361 2362 (prev_entry->object.vm_object == this_entry->object.vm_object) && 2363 ((prev_entry->offset + (prev_entry->end - prev_entry->start)) 2364 == this_entry->offset) 2365 ) { 2366 if (map->first_free == this_entry) 2367 map->first_free = prev_entry; 2368 2369 SAVE_HINT(map, prev_entry); 2370 vm_map_entry_unlink(map, this_entry); 2371 prev_entry->end = this_entry->end; 2372 vm_object_deallocate(this_entry->object.vm_object); 2373 vm_map_entry_dispose(map, this_entry); 2374 } 2375 vm_map_unlock(map); 2376 } 2377 2378 /* 2379 * vm_map_print: [ debug ] 2380 */ 2381 void vm_map_print(map, full) 2382 register vm_map_t map; 2383 boolean_t full; 2384 { 2385 register vm_map_entry_t entry; 2386 extern int indent; 2387 2388 iprintf("%s map 0x%x: pmap=0x%x,ref=%d,nentries=%d,version=%d\n", 2389 (map->is_main_map ? "Task" : "Share"), 2390 (int) map, (int) (map->pmap), map->ref_count, map->nentries, 2391 map->timestamp); 2392 2393 if (!full && indent) 2394 return; 2395 2396 indent += 2; 2397 for (entry = map->header.next; entry != &map->header; 2398 entry = entry->next) { 2399 iprintf("map entry 0x%x: start=0x%x, end=0x%x, ", 2400 (int) entry, (int) entry->start, (int) entry->end); 2401 if (map->is_main_map) { 2402 static char *inheritance_name[4] = 2403 { "share", "copy", "none", "donate_copy"}; 2404 printf("prot=%x/%x/%s, ", 2405 entry->protection, 2406 entry->max_protection, 2407 inheritance_name[entry->inheritance]); 2408 if (entry->wired_count != 0) 2409 printf("wired, "); 2410 } 2411 2412 if (entry->is_a_map || entry->is_sub_map) { 2413 printf("share=0x%x, offset=0x%x\n", 2414 (int) entry->object.share_map, 2415 (int) entry->offset); 2416 if ((entry->prev == &map->header) || 2417 (!entry->prev->is_a_map) || 2418 (entry->prev->object.share_map != 2419 entry->object.share_map)) { 2420 indent += 2; 2421 vm_map_print(entry->object.share_map, full); 2422 indent -= 2; 2423 } 2424 2425 } 2426 else { 2427 printf("object=0x%x, offset=0x%x", 2428 (int) entry->object.vm_object, 2429 (int) entry->offset); 2430 if (entry->copy_on_write) 2431 printf(", copy (%s)", 2432 entry->needs_copy ? "needed" : "done"); 2433 printf("\n"); 2434 2435 if ((entry->prev == &map->header) || 2436 (entry->prev->is_a_map) || 2437 (entry->prev->object.vm_object != 2438 entry->object.vm_object)) { 2439 indent += 2; 2440 vm_object_print(entry->object.vm_object, full); 2441 indent -= 2; 2442 } 2443 } 2444 } 2445 indent -= 2; 2446 } 2447