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_page.c 7.5 (Berkeley) 07/25/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 * Resident memory management module. 41 */ 42 43 #include "param.h" 44 45 #include "vm.h" 46 #include "vm_map.h" 47 #include "vm_page.h" 48 #include "vm_pageout.h" 49 50 /* 51 * Associated with page of user-allocatable memory is a 52 * page structure. 53 */ 54 55 queue_head_t *vm_page_buckets; /* Array of buckets */ 56 int vm_page_bucket_count = 0; /* How big is array? */ 57 int vm_page_hash_mask; /* Mask for hash function */ 58 simple_lock_data_t bucket_lock; /* lock for all buckets XXX */ 59 60 queue_head_t vm_page_queue_free; 61 queue_head_t vm_page_queue_active; 62 queue_head_t vm_page_queue_inactive; 63 simple_lock_data_t vm_page_queue_lock; 64 simple_lock_data_t vm_page_queue_free_lock; 65 66 vm_page_t vm_page_array; 67 long first_page; 68 long last_page; 69 vm_offset_t first_phys_addr; 70 vm_offset_t last_phys_addr; 71 vm_size_t page_mask; 72 int page_shift; 73 74 /* 75 * vm_set_page_size: 76 * 77 * Sets the page size, perhaps based upon the memory 78 * size. Must be called before any use of page-size 79 * dependent functions. 80 * 81 * Sets page_shift and page_mask from vm_stat.page_size. 82 */ 83 void vm_set_page_size() 84 { 85 86 if (vm_stat.page_size == 0) 87 vm_stat.page_size = DEFAULT_PAGE_SIZE; 88 page_mask = vm_stat.page_size - 1; 89 if ((page_mask & vm_stat.page_size) != 0) 90 panic("vm_set_page_size: page size not a power of two"); 91 for (page_shift = 0; ; page_shift++) 92 if ((1 << page_shift) == vm_stat.page_size) 93 break; 94 } 95 96 97 /* 98 * vm_page_startup: 99 * 100 * Initializes the resident memory module. 101 * 102 * Allocates memory for the page cells, and 103 * for the object/offset-to-page hash table headers. 104 * Each page cell is initialized and placed on the free list. 105 */ 106 vm_offset_t vm_page_startup(start, end, vaddr) 107 register vm_offset_t start; 108 vm_offset_t end; 109 register vm_offset_t vaddr; 110 { 111 register vm_offset_t mapped; 112 register vm_page_t m; 113 register queue_t bucket; 114 vm_size_t npages; 115 register vm_offset_t new_start; 116 int i; 117 vm_offset_t pa; 118 119 extern vm_offset_t kentry_data; 120 extern vm_size_t kentry_data_size; 121 122 123 /* 124 * Initialize the locks 125 */ 126 127 simple_lock_init(&vm_page_queue_free_lock); 128 simple_lock_init(&vm_page_queue_lock); 129 130 /* 131 * Initialize the queue headers for the free queue, 132 * the active queue and the inactive queue. 133 */ 134 135 queue_init(&vm_page_queue_free); 136 queue_init(&vm_page_queue_active); 137 queue_init(&vm_page_queue_inactive); 138 139 /* 140 * Allocate (and initialize) the hash table buckets. 141 * 142 * The number of buckets MUST BE a power of 2, and 143 * the actual value is the next power of 2 greater 144 * than the number of physical pages in the system. 145 * 146 * Note: 147 * This computation can be tweaked if desired. 148 */ 149 150 vm_page_buckets = (queue_t) vaddr; 151 bucket = vm_page_buckets; 152 if (vm_page_bucket_count == 0) { 153 vm_page_bucket_count = 1; 154 while (vm_page_bucket_count < atop(end - start)) 155 vm_page_bucket_count <<= 1; 156 } 157 158 vm_page_hash_mask = vm_page_bucket_count - 1; 159 160 /* 161 * Validate these addresses. 162 */ 163 164 new_start = round_page(((queue_t)start) + vm_page_bucket_count); 165 mapped = vaddr; 166 vaddr = pmap_map(mapped, start, new_start, 167 VM_PROT_READ|VM_PROT_WRITE); 168 start = new_start; 169 blkclr((caddr_t) mapped, vaddr - mapped); 170 mapped = vaddr; 171 172 for (i = vm_page_bucket_count; i--;) { 173 queue_init(bucket); 174 bucket++; 175 } 176 177 simple_lock_init(&bucket_lock); 178 179 /* 180 * round (or truncate) the addresses to our page size. 181 */ 182 183 end = trunc_page(end); 184 185 /* 186 * Pre-allocate maps and map entries that cannot be dynamically 187 * allocated via malloc(). The maps include the kernel_map and 188 * kmem_map which must be initialized before malloc() will 189 * work (obviously). Also could include pager maps which would 190 * be allocated before kmeminit. 191 * 192 * Allow some kernel map entries... this should be plenty 193 * since people shouldn't be cluttering up the kernel 194 * map (they should use their own maps). 195 */ 196 197 kentry_data_size = MAX_KMAP * sizeof(struct vm_map) + 198 MAX_KMAPENT * sizeof(struct vm_map_entry); 199 kentry_data_size = round_page(kentry_data_size); 200 kentry_data = (vm_offset_t) vaddr; 201 vaddr += kentry_data_size; 202 203 /* 204 * Validate these zone addresses. 205 */ 206 207 new_start = start + (vaddr - mapped); 208 pmap_map(mapped, start, new_start, VM_PROT_READ|VM_PROT_WRITE); 209 blkclr((caddr_t) mapped, (vaddr - mapped)); 210 mapped = vaddr; 211 start = new_start; 212 213 /* 214 * Compute the number of pages of memory that will be 215 * available for use (taking into account the overhead 216 * of a page structure per page). 217 */ 218 219 vm_stat.free_count = npages = 220 (end - start)/(PAGE_SIZE + sizeof(struct vm_page)); 221 222 /* 223 * Initialize the mem entry structures now, and 224 * put them in the free queue. 225 */ 226 227 m = vm_page_array = (vm_page_t) vaddr; 228 first_page = start; 229 first_page += npages*sizeof(struct vm_page); 230 first_page = atop(round_page(first_page)); 231 last_page = first_page + npages - 1; 232 233 first_phys_addr = ptoa(first_page); 234 last_phys_addr = ptoa(last_page) + PAGE_MASK; 235 236 /* 237 * Validate these addresses. 238 */ 239 240 new_start = start + (round_page(m + npages) - mapped); 241 mapped = pmap_map(mapped, start, new_start, 242 VM_PROT_READ|VM_PROT_WRITE); 243 start = new_start; 244 245 /* 246 * Clear all of the page structures 247 */ 248 blkclr((caddr_t)m, npages * sizeof(*m)); 249 250 pa = first_phys_addr; 251 while (npages--) { 252 m->copy_on_write = FALSE; 253 m->wanted = FALSE; 254 m->inactive = FALSE; 255 m->active = FALSE; 256 m->busy = FALSE; 257 m->object = NULL; 258 m->phys_addr = pa; 259 queue_enter(&vm_page_queue_free, m, vm_page_t, pageq); 260 m++; 261 pa += PAGE_SIZE; 262 } 263 264 /* 265 * Initialize vm_pages_needed lock here - don't wait for pageout 266 * daemon XXX 267 */ 268 simple_lock_init(&vm_pages_needed_lock); 269 270 return(mapped); 271 } 272 273 /* 274 * vm_page_hash: 275 * 276 * Distributes the object/offset key pair among hash buckets. 277 * 278 * NOTE: This macro depends on vm_page_bucket_count being a power of 2. 279 */ 280 #define vm_page_hash(object, offset) \ 281 (((unsigned)object+(unsigned)atop(offset))&vm_page_hash_mask) 282 283 /* 284 * vm_page_insert: [ internal use only ] 285 * 286 * Inserts the given mem entry into the object/object-page 287 * table and object list. 288 * 289 * The object and page must be locked. 290 */ 291 292 void vm_page_insert(mem, object, offset) 293 register vm_page_t mem; 294 register vm_object_t object; 295 register vm_offset_t offset; 296 { 297 register queue_t bucket; 298 int spl; 299 300 VM_PAGE_CHECK(mem); 301 302 if (mem->tabled) 303 panic("vm_page_insert: already inserted"); 304 305 /* 306 * Record the object/offset pair in this page 307 */ 308 309 mem->object = object; 310 mem->offset = offset; 311 312 /* 313 * Insert it into the object_object/offset hash table 314 */ 315 316 bucket = &vm_page_buckets[vm_page_hash(object, offset)]; 317 spl = splimp(); 318 simple_lock(&bucket_lock); 319 queue_enter(bucket, mem, vm_page_t, hashq); 320 simple_unlock(&bucket_lock); 321 (void) splx(spl); 322 323 /* 324 * Now link into the object's list of backed pages. 325 */ 326 327 queue_enter(&object->memq, mem, vm_page_t, listq); 328 mem->tabled = TRUE; 329 330 /* 331 * And show that the object has one more resident 332 * page. 333 */ 334 335 object->resident_page_count++; 336 } 337 338 /* 339 * vm_page_remove: [ internal use only ] 340 * 341 * Removes the given mem entry from the object/offset-page 342 * table and the object page list. 343 * 344 * The object and page must be locked. 345 */ 346 347 void vm_page_remove(mem) 348 register vm_page_t mem; 349 { 350 register queue_t bucket; 351 int spl; 352 353 VM_PAGE_CHECK(mem); 354 355 if (!mem->tabled) 356 return; 357 358 /* 359 * Remove from the object_object/offset hash table 360 */ 361 362 bucket = &vm_page_buckets[vm_page_hash(mem->object, mem->offset)]; 363 spl = splimp(); 364 simple_lock(&bucket_lock); 365 queue_remove(bucket, mem, vm_page_t, hashq); 366 simple_unlock(&bucket_lock); 367 (void) splx(spl); 368 369 /* 370 * Now remove from the object's list of backed pages. 371 */ 372 373 queue_remove(&mem->object->memq, mem, vm_page_t, listq); 374 375 /* 376 * And show that the object has one fewer resident 377 * page. 378 */ 379 380 mem->object->resident_page_count--; 381 382 mem->tabled = FALSE; 383 } 384 385 /* 386 * vm_page_lookup: 387 * 388 * Returns the page associated with the object/offset 389 * pair specified; if none is found, NULL is returned. 390 * 391 * The object must be locked. No side effects. 392 */ 393 394 vm_page_t vm_page_lookup(object, offset) 395 register vm_object_t object; 396 register vm_offset_t offset; 397 { 398 register vm_page_t mem; 399 register queue_t bucket; 400 int spl; 401 402 /* 403 * Search the hash table for this object/offset pair 404 */ 405 406 bucket = &vm_page_buckets[vm_page_hash(object, offset)]; 407 408 spl = splimp(); 409 simple_lock(&bucket_lock); 410 mem = (vm_page_t) queue_first(bucket); 411 while (!queue_end(bucket, (queue_entry_t) mem)) { 412 VM_PAGE_CHECK(mem); 413 if ((mem->object == object) && (mem->offset == offset)) { 414 simple_unlock(&bucket_lock); 415 splx(spl); 416 return(mem); 417 } 418 mem = (vm_page_t) queue_next(&mem->hashq); 419 } 420 421 simple_unlock(&bucket_lock); 422 splx(spl); 423 return(NULL); 424 } 425 426 /* 427 * vm_page_rename: 428 * 429 * Move the given memory entry from its 430 * current object to the specified target object/offset. 431 * 432 * The object must be locked. 433 */ 434 void vm_page_rename(mem, new_object, new_offset) 435 register vm_page_t mem; 436 register vm_object_t new_object; 437 vm_offset_t new_offset; 438 { 439 if (mem->object == new_object) 440 return; 441 442 vm_page_lock_queues(); /* keep page from moving out from 443 under pageout daemon */ 444 vm_page_remove(mem); 445 vm_page_insert(mem, new_object, new_offset); 446 vm_page_unlock_queues(); 447 } 448 449 void vm_page_init(mem, object, offset) 450 vm_page_t mem; 451 vm_object_t object; 452 vm_offset_t offset; 453 { 454 #ifdef DEBUG 455 #define vm_page_init(mem, object, offset) {\ 456 (mem)->busy = TRUE; \ 457 (mem)->tabled = FALSE; \ 458 vm_page_insert((mem), (object), (offset)); \ 459 (mem)->absent = FALSE; \ 460 (mem)->fictitious = FALSE; \ 461 (mem)->page_lock = VM_PROT_NONE; \ 462 (mem)->unlock_request = VM_PROT_NONE; \ 463 (mem)->laundry = FALSE; \ 464 (mem)->active = FALSE; \ 465 (mem)->inactive = FALSE; \ 466 (mem)->wire_count = 0; \ 467 (mem)->clean = TRUE; \ 468 (mem)->copy_on_write = FALSE; \ 469 (mem)->fake = TRUE; \ 470 (mem)->pagerowned = FALSE; \ 471 (mem)->ptpage = FALSE; \ 472 } 473 #else 474 #define vm_page_init(mem, object, offset) {\ 475 (mem)->busy = TRUE; \ 476 (mem)->tabled = FALSE; \ 477 vm_page_insert((mem), (object), (offset)); \ 478 (mem)->absent = FALSE; \ 479 (mem)->fictitious = FALSE; \ 480 (mem)->page_lock = VM_PROT_NONE; \ 481 (mem)->unlock_request = VM_PROT_NONE; \ 482 (mem)->laundry = FALSE; \ 483 (mem)->active = FALSE; \ 484 (mem)->inactive = FALSE; \ 485 (mem)->wire_count = 0; \ 486 (mem)->clean = TRUE; \ 487 (mem)->copy_on_write = FALSE; \ 488 (mem)->fake = TRUE; \ 489 } 490 #endif 491 492 vm_page_init(mem, object, offset); 493 } 494 495 /* 496 * vm_page_alloc: 497 * 498 * Allocate and return a memory cell associated 499 * with this VM object/offset pair. 500 * 501 * Object must be locked. 502 */ 503 vm_page_t vm_page_alloc(object, offset) 504 vm_object_t object; 505 vm_offset_t offset; 506 { 507 register vm_page_t mem; 508 int spl; 509 510 spl = splimp(); /* XXX */ 511 simple_lock(&vm_page_queue_free_lock); 512 if (queue_empty(&vm_page_queue_free)) { 513 simple_unlock(&vm_page_queue_free_lock); 514 splx(spl); 515 return(NULL); 516 } 517 518 queue_remove_first(&vm_page_queue_free, mem, vm_page_t, pageq); 519 520 vm_stat.free_count--; 521 simple_unlock(&vm_page_queue_free_lock); 522 splx(spl); 523 524 vm_page_init(mem, object, offset); 525 526 /* 527 * Decide if we should poke the pageout daemon. 528 * We do this if the free count is less than the low 529 * water mark, or if the free count is less than the high 530 * water mark (but above the low water mark) and the inactive 531 * count is less than its target. 532 * 533 * We don't have the counts locked ... if they change a little, 534 * it doesn't really matter. 535 */ 536 537 if ((vm_stat.free_count < vm_stat.free_min) || 538 ((vm_stat.free_count < vm_stat.free_target) && 539 (vm_stat.inactive_count < vm_stat.inactive_target))) 540 thread_wakeup(&vm_pages_needed); 541 return(mem); 542 } 543 544 /* 545 * vm_page_free: 546 * 547 * Returns the given page to the free list, 548 * disassociating it with any VM object. 549 * 550 * Object and page must be locked prior to entry. 551 */ 552 void vm_page_free(mem) 553 register vm_page_t mem; 554 { 555 vm_page_remove(mem); 556 if (mem->active) { 557 queue_remove(&vm_page_queue_active, mem, vm_page_t, pageq); 558 mem->active = FALSE; 559 vm_stat.active_count--; 560 } 561 562 if (mem->inactive) { 563 queue_remove(&vm_page_queue_inactive, mem, vm_page_t, pageq); 564 mem->inactive = FALSE; 565 vm_stat.inactive_count--; 566 } 567 568 if (!mem->fictitious) { 569 int spl; 570 571 spl = splimp(); 572 simple_lock(&vm_page_queue_free_lock); 573 queue_enter(&vm_page_queue_free, mem, vm_page_t, pageq); 574 575 vm_stat.free_count++; 576 simple_unlock(&vm_page_queue_free_lock); 577 splx(spl); 578 } 579 } 580 581 /* 582 * vm_page_wire: 583 * 584 * Mark this page as wired down by yet 585 * another map, removing it from paging queues 586 * as necessary. 587 * 588 * The page queues must be locked. 589 */ 590 void vm_page_wire(mem) 591 register vm_page_t mem; 592 { 593 VM_PAGE_CHECK(mem); 594 595 if (mem->wire_count == 0) { 596 if (mem->active) { 597 queue_remove(&vm_page_queue_active, mem, vm_page_t, 598 pageq); 599 vm_stat.active_count--; 600 mem->active = FALSE; 601 } 602 if (mem->inactive) { 603 queue_remove(&vm_page_queue_inactive, mem, vm_page_t, 604 pageq); 605 vm_stat.inactive_count--; 606 mem->inactive = FALSE; 607 } 608 vm_stat.wire_count++; 609 } 610 mem->wire_count++; 611 } 612 613 /* 614 * vm_page_unwire: 615 * 616 * Release one wiring of this page, potentially 617 * enabling it to be paged again. 618 * 619 * The page queues must be locked. 620 */ 621 void vm_page_unwire(mem) 622 register vm_page_t mem; 623 { 624 VM_PAGE_CHECK(mem); 625 626 mem->wire_count--; 627 if (mem->wire_count == 0) { 628 queue_enter(&vm_page_queue_active, mem, vm_page_t, pageq); 629 vm_stat.active_count++; 630 mem->active = TRUE; 631 vm_stat.wire_count--; 632 } 633 } 634 635 /* 636 * vm_page_deactivate: 637 * 638 * Returns the given page to the inactive list, 639 * indicating that no physical maps have access 640 * to this page. [Used by the physical mapping system.] 641 * 642 * The page queues must be locked. 643 */ 644 void vm_page_deactivate(m) 645 register vm_page_t m; 646 { 647 VM_PAGE_CHECK(m); 648 649 /* 650 * Only move active pages -- ignore locked or already 651 * inactive ones. 652 */ 653 654 if (m->active) { 655 pmap_clear_reference(VM_PAGE_TO_PHYS(m)); 656 queue_remove(&vm_page_queue_active, m, vm_page_t, pageq); 657 queue_enter(&vm_page_queue_inactive, m, vm_page_t, pageq); 658 m->active = FALSE; 659 m->inactive = TRUE; 660 vm_stat.active_count--; 661 vm_stat.inactive_count++; 662 if (pmap_is_modified(VM_PAGE_TO_PHYS(m))) 663 m->clean = FALSE; 664 m->laundry = !m->clean; 665 } 666 } 667 668 /* 669 * vm_page_activate: 670 * 671 * Put the specified page on the active list (if appropriate). 672 * 673 * The page queues must be locked. 674 */ 675 676 void vm_page_activate(m) 677 register vm_page_t m; 678 { 679 VM_PAGE_CHECK(m); 680 681 if (m->inactive) { 682 queue_remove(&vm_page_queue_inactive, m, vm_page_t, 683 pageq); 684 vm_stat.inactive_count--; 685 m->inactive = FALSE; 686 } 687 if (m->wire_count == 0) { 688 if (m->active) 689 panic("vm_page_activate: already active"); 690 691 queue_enter(&vm_page_queue_active, m, vm_page_t, pageq); 692 m->active = TRUE; 693 vm_stat.active_count++; 694 } 695 } 696 697 /* 698 * vm_page_zero_fill: 699 * 700 * Zero-fill the specified page. 701 * Written as a standard pagein routine, to 702 * be used by the zero-fill object. 703 */ 704 705 boolean_t vm_page_zero_fill(m) 706 vm_page_t m; 707 { 708 VM_PAGE_CHECK(m); 709 710 pmap_zero_page(VM_PAGE_TO_PHYS(m)); 711 return(TRUE); 712 } 713 714 /* 715 * vm_page_copy: 716 * 717 * Copy one page to another 718 */ 719 720 void vm_page_copy(src_m, dest_m) 721 vm_page_t src_m; 722 vm_page_t dest_m; 723 { 724 VM_PAGE_CHECK(src_m); 725 VM_PAGE_CHECK(dest_m); 726 727 pmap_copy_page(VM_PAGE_TO_PHYS(src_m), VM_PAGE_TO_PHYS(dest_m)); 728 } 729