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