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