kernel - Major vm_page, lwkt thread, and other changes
[dragonfly.git] / sys / vm / vm_page.c
1 /*
2  * (MPSAFE)
3  *
4  * Copyright (c) 1991 Regents of the University of California.
5  * All rights reserved.
6  *
7  * This code is derived from software contributed to Berkeley by
8  * The Mach Operating System project at Carnegie-Mellon University.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  * 1. Redistributions of source code must retain the above copyright
14  *    notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  * 4. Neither the name of the University nor the names of its contributors
19  *    may be used to endorse or promote products derived from this software
20  *    without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  *
34  *      from: @(#)vm_page.c     7.4 (Berkeley) 5/7/91
35  * $FreeBSD: src/sys/vm/vm_page.c,v 1.147.2.18 2002/03/10 05:03:19 alc Exp $
36  */
37
38 /*
39  * Copyright (c) 1987, 1990 Carnegie-Mellon University.
40  * All rights reserved.
41  *
42  * Authors: Avadis Tevanian, Jr., Michael Wayne Young
43  *
44  * Permission to use, copy, modify and distribute this software and
45  * its documentation is hereby granted, provided that both the copyright
46  * notice and this permission notice appear in all copies of the
47  * software, derivative works or modified versions, and any portions
48  * thereof, and that both notices appear in supporting documentation.
49  *
50  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
51  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
52  * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
53  *
54  * Carnegie Mellon requests users of this software to return to
55  *
56  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
57  *  School of Computer Science
58  *  Carnegie Mellon University
59  *  Pittsburgh PA 15213-3890
60  *
61  * any improvements or extensions that they make and grant Carnegie the
62  * rights to redistribute these changes.
63  */
64 /*
65  * Resident memory management module.  The module manipulates 'VM pages'.
66  * A VM page is the core building block for memory management.
67  */
68
69 #include <sys/param.h>
70 #include <sys/systm.h>
71 #include <sys/malloc.h>
72 #include <sys/proc.h>
73 #include <sys/vmmeter.h>
74 #include <sys/vnode.h>
75 #include <sys/kernel.h>
76
77 #include <vm/vm.h>
78 #include <vm/vm_param.h>
79 #include <sys/lock.h>
80 #include <vm/vm_kern.h>
81 #include <vm/pmap.h>
82 #include <vm/vm_map.h>
83 #include <vm/vm_object.h>
84 #include <vm/vm_page.h>
85 #include <vm/vm_pageout.h>
86 #include <vm/vm_pager.h>
87 #include <vm/vm_extern.h>
88 #include <vm/swap_pager.h>
89
90 #include <machine/md_var.h>
91
92 #include <vm/vm_page2.h>
93 #include <sys/spinlock2.h>
94
95 #define VMACTION_HSIZE  256
96 #define VMACTION_HMASK  (VMACTION_HSIZE - 1)
97
98 static void vm_page_queue_init(void);
99 static void vm_page_free_wakeup(void);
100 static vm_page_t vm_page_select_cache(u_short pg_color);
101 static vm_page_t _vm_page_list_find2(int basequeue, int index);
102 static void _vm_page_deactivate_locked(vm_page_t m, int athead);
103
104 /*
105  * Array of tailq lists
106  */
107 __cachealign struct vpgqueues vm_page_queues[PQ_COUNT];
108
109 LIST_HEAD(vm_page_action_list, vm_page_action);
110 struct vm_page_action_list      action_list[VMACTION_HSIZE];
111 static volatile int vm_pages_waiting;
112
113
114 RB_GENERATE2(vm_page_rb_tree, vm_page, rb_entry, rb_vm_page_compare,
115              vm_pindex_t, pindex);
116
117 static void
118 vm_page_queue_init(void) 
119 {
120         int i;
121
122         for (i = 0; i < PQ_L2_SIZE; i++)
123                 vm_page_queues[PQ_FREE+i].cnt = &vmstats.v_free_count;
124         for (i = 0; i < PQ_L2_SIZE; i++)
125                 vm_page_queues[PQ_CACHE+i].cnt = &vmstats.v_cache_count;
126
127         vm_page_queues[PQ_INACTIVE].cnt = &vmstats.v_inactive_count;
128         vm_page_queues[PQ_ACTIVE].cnt = &vmstats.v_active_count;
129         vm_page_queues[PQ_HOLD].cnt = &vmstats.v_active_count;
130         /* PQ_NONE has no queue */
131
132         for (i = 0; i < PQ_COUNT; i++) {
133                 TAILQ_INIT(&vm_page_queues[i].pl);
134                 spin_init(&vm_page_queues[i].spin);
135         }
136
137         for (i = 0; i < VMACTION_HSIZE; i++)
138                 LIST_INIT(&action_list[i]);
139 }
140
141 /*
142  * note: place in initialized data section?  Is this necessary?
143  */
144 long first_page = 0;
145 int vm_page_array_size = 0;
146 int vm_page_zero_count = 0;
147 vm_page_t vm_page_array = 0;
148
149 /*
150  * (low level boot)
151  *
152  * Sets the page size, perhaps based upon the memory size.
153  * Must be called before any use of page-size dependent functions.
154  */
155 void
156 vm_set_page_size(void)
157 {
158         if (vmstats.v_page_size == 0)
159                 vmstats.v_page_size = PAGE_SIZE;
160         if (((vmstats.v_page_size - 1) & vmstats.v_page_size) != 0)
161                 panic("vm_set_page_size: page size not a power of two");
162 }
163
164 /*
165  * (low level boot)
166  *
167  * Add a new page to the freelist for use by the system.  New pages
168  * are added to both the head and tail of the associated free page
169  * queue in a bottom-up fashion, so both zero'd and non-zero'd page
170  * requests pull 'recent' adds (higher physical addresses) first.
171  *
172  * Must be called in a critical section.
173  */
174 static vm_page_t
175 vm_add_new_page(vm_paddr_t pa)
176 {
177         struct vpgqueues *vpq;
178         vm_page_t m;
179
180         m = PHYS_TO_VM_PAGE(pa);
181         m->phys_addr = pa;
182         m->flags = 0;
183         m->pc = (pa >> PAGE_SHIFT) & PQ_L2_MASK;
184 #ifdef SMP
185         /*
186          * Twist for cpu localization instead of page coloring.
187          */
188         m->pc ^= ((pa >> PAGE_SHIFT) / PQ_L2_SIZE) & PQ_L2_MASK;
189         m->pc ^= ((pa >> PAGE_SHIFT) / (PQ_L2_SIZE * PQ_L2_SIZE)) & PQ_L2_MASK;
190 #endif
191         m->queue = m->pc + PQ_FREE;
192         KKASSERT(m->dirty == 0);
193
194         atomic_add_int(&vmstats.v_page_count, 1);
195         atomic_add_int(&vmstats.v_free_count, 1);
196         vpq = &vm_page_queues[m->queue];
197         if (vpq->flipflop)
198                 TAILQ_INSERT_TAIL(&vpq->pl, m, pageq);
199         else
200                 TAILQ_INSERT_HEAD(&vpq->pl, m, pageq);
201         vpq->flipflop = 1 - vpq->flipflop;
202         ++vpq->lcnt;
203
204         return (m);
205 }
206
207 /*
208  * (low level boot)
209  *
210  * Initializes the resident memory module.
211  *
212  * Preallocates memory for critical VM structures and arrays prior to
213  * kernel_map becoming available.
214  *
215  * Memory is allocated from (virtual2_start, virtual2_end) if available,
216  * otherwise memory is allocated from (virtual_start, virtual_end).
217  *
218  * On x86-64 (virtual_start, virtual_end) is only 2GB and may not be
219  * large enough to hold vm_page_array & other structures for machines with
220  * large amounts of ram, so we want to use virtual2* when available.
221  */
222 void
223 vm_page_startup(void)
224 {
225         vm_offset_t vaddr = virtual2_start ? virtual2_start : virtual_start;
226         vm_offset_t mapped;
227         vm_size_t npages;
228         vm_paddr_t page_range;
229         vm_paddr_t new_end;
230         int i;
231         vm_paddr_t pa;
232         int nblocks;
233         vm_paddr_t last_pa;
234         vm_paddr_t end;
235         vm_paddr_t biggestone, biggestsize;
236         vm_paddr_t total;
237
238         total = 0;
239         biggestsize = 0;
240         biggestone = 0;
241         nblocks = 0;
242         vaddr = round_page(vaddr);
243
244         for (i = 0; phys_avail[i + 1]; i += 2) {
245                 phys_avail[i] = round_page64(phys_avail[i]);
246                 phys_avail[i + 1] = trunc_page64(phys_avail[i + 1]);
247         }
248
249         for (i = 0; phys_avail[i + 1]; i += 2) {
250                 vm_paddr_t size = phys_avail[i + 1] - phys_avail[i];
251
252                 if (size > biggestsize) {
253                         biggestone = i;
254                         biggestsize = size;
255                 }
256                 ++nblocks;
257                 total += size;
258         }
259
260         end = phys_avail[biggestone+1];
261         end = trunc_page(end);
262
263         /*
264          * Initialize the queue headers for the free queue, the active queue
265          * and the inactive queue.
266          */
267
268         vm_page_queue_init();
269
270 #if !defined(_KERNEL_VIRTUAL)
271         /*
272          * VKERNELs don't support minidumps and as such don't need
273          * vm_page_dump
274          *
275          * Allocate a bitmap to indicate that a random physical page
276          * needs to be included in a minidump.
277          *
278          * The amd64 port needs this to indicate which direct map pages
279          * need to be dumped, via calls to dump_add_page()/dump_drop_page().
280          *
281          * However, i386 still needs this workspace internally within the
282          * minidump code.  In theory, they are not needed on i386, but are
283          * included should the sf_buf code decide to use them.
284          */
285         page_range = phys_avail[(nblocks - 1) * 2 + 1] / PAGE_SIZE;
286         vm_page_dump_size = round_page(roundup2(page_range, NBBY) / NBBY);
287         end -= vm_page_dump_size;
288         vm_page_dump = (void *)pmap_map(&vaddr, end, end + vm_page_dump_size,
289             VM_PROT_READ | VM_PROT_WRITE);
290         bzero((void *)vm_page_dump, vm_page_dump_size);
291 #endif
292
293         /*
294          * Compute the number of pages of memory that will be available for
295          * use (taking into account the overhead of a page structure per
296          * page).
297          */
298         first_page = phys_avail[0] / PAGE_SIZE;
299         page_range = phys_avail[(nblocks - 1) * 2 + 1] / PAGE_SIZE - first_page;
300         npages = (total - (page_range * sizeof(struct vm_page))) / PAGE_SIZE;
301
302         /*
303          * Initialize the mem entry structures now, and put them in the free
304          * queue.
305          */
306         new_end = trunc_page(end - page_range * sizeof(struct vm_page));
307         mapped = pmap_map(&vaddr, new_end, end,
308             VM_PROT_READ | VM_PROT_WRITE);
309         vm_page_array = (vm_page_t)mapped;
310
311 #if defined(__x86_64__) && !defined(_KERNEL_VIRTUAL)
312         /*
313          * since pmap_map on amd64 returns stuff out of a direct-map region,
314          * we have to manually add these pages to the minidump tracking so
315          * that they can be dumped, including the vm_page_array.
316          */
317         for (pa = new_end; pa < phys_avail[biggestone + 1]; pa += PAGE_SIZE)
318                 dump_add_page(pa);
319 #endif
320
321         /*
322          * Clear all of the page structures
323          */
324         bzero((caddr_t) vm_page_array, page_range * sizeof(struct vm_page));
325         vm_page_array_size = page_range;
326
327         /*
328          * Construct the free queue(s) in ascending order (by physical
329          * address) so that the first 16MB of physical memory is allocated
330          * last rather than first.  On large-memory machines, this avoids
331          * the exhaustion of low physical memory before isa_dmainit has run.
332          */
333         vmstats.v_page_count = 0;
334         vmstats.v_free_count = 0;
335         for (i = 0; phys_avail[i + 1] && npages > 0; i += 2) {
336                 pa = phys_avail[i];
337                 if (i == biggestone)
338                         last_pa = new_end;
339                 else
340                         last_pa = phys_avail[i + 1];
341                 while (pa < last_pa && npages-- > 0) {
342                         vm_add_new_page(pa);
343                         pa += PAGE_SIZE;
344                 }
345         }
346         if (virtual2_start)
347                 virtual2_start = vaddr;
348         else
349                 virtual_start = vaddr;
350 }
351
352 /*
353  * Scan comparison function for Red-Black tree scans.  An inclusive
354  * (start,end) is expected.  Other fields are not used.
355  */
356 int
357 rb_vm_page_scancmp(struct vm_page *p, void *data)
358 {
359         struct rb_vm_page_scan_info *info = data;
360
361         if (p->pindex < info->start_pindex)
362                 return(-1);
363         if (p->pindex > info->end_pindex)
364                 return(1);
365         return(0);
366 }
367
368 int
369 rb_vm_page_compare(struct vm_page *p1, struct vm_page *p2)
370 {
371         if (p1->pindex < p2->pindex)
372                 return(-1);
373         if (p1->pindex > p2->pindex)
374                 return(1);
375         return(0);
376 }
377
378 /*
379  * Each page queue has its own spin lock, which is fairly optimal for
380  * allocating and freeing pages at least.
381  *
382  * The caller must hold the vm_page_spin_lock() before locking a vm_page's
383  * queue spinlock via this function.  Also note that m->queue cannot change
384  * unless both the page and queue are locked.
385  */
386 static __inline
387 void
388 _vm_page_queue_spin_lock(vm_page_t m)
389 {
390         u_short queue;
391
392         queue = m->queue;
393         if (queue != PQ_NONE) {
394                 spin_lock(&vm_page_queues[queue].spin);
395                 KKASSERT(queue == m->queue);
396         }
397 }
398
399 static __inline
400 void
401 _vm_page_queue_spin_unlock(vm_page_t m)
402 {
403         u_short queue;
404
405         queue = m->queue;
406         cpu_ccfence();
407         if (queue != PQ_NONE)
408                 spin_unlock(&vm_page_queues[queue].spin);
409 }
410
411 static __inline
412 void
413 _vm_page_queues_spin_lock(u_short queue)
414 {
415         cpu_ccfence();
416         if (queue != PQ_NONE)
417                 spin_lock(&vm_page_queues[queue].spin);
418 }
419
420
421 static __inline
422 void
423 _vm_page_queues_spin_unlock(u_short queue)
424 {
425         cpu_ccfence();
426         if (queue != PQ_NONE)
427                 spin_unlock(&vm_page_queues[queue].spin);
428 }
429
430 void
431 vm_page_queue_spin_lock(vm_page_t m)
432 {
433         _vm_page_queue_spin_lock(m);
434 }
435
436 void
437 vm_page_queues_spin_lock(u_short queue)
438 {
439         _vm_page_queues_spin_lock(queue);
440 }
441
442 void
443 vm_page_queue_spin_unlock(vm_page_t m)
444 {
445         _vm_page_queue_spin_unlock(m);
446 }
447
448 void
449 vm_page_queues_spin_unlock(u_short queue)
450 {
451         _vm_page_queues_spin_unlock(queue);
452 }
453
454 /*
455  * This locks the specified vm_page and its queue in the proper order
456  * (page first, then queue).  The queue may change so the caller must
457  * recheck on return.
458  */
459 static __inline
460 void
461 _vm_page_and_queue_spin_lock(vm_page_t m)
462 {
463         vm_page_spin_lock(m);
464         _vm_page_queue_spin_lock(m);
465 }
466
467 static __inline
468 void
469 _vm_page_and_queue_spin_unlock(vm_page_t m)
470 {
471         _vm_page_queues_spin_unlock(m->queue);
472         vm_page_spin_unlock(m);
473 }
474
475 void
476 vm_page_and_queue_spin_unlock(vm_page_t m)
477 {
478         _vm_page_and_queue_spin_unlock(m);
479 }
480
481 void
482 vm_page_and_queue_spin_lock(vm_page_t m)
483 {
484         _vm_page_and_queue_spin_lock(m);
485 }
486
487 /*
488  * Helper function removes vm_page from its current queue.
489  * Returns the base queue the page used to be on.
490  *
491  * The vm_page and the queue must be spinlocked.
492  * This function will unlock the queue but leave the page spinlocked.
493  */
494 static __inline u_short
495 _vm_page_rem_queue_spinlocked(vm_page_t m)
496 {
497         struct vpgqueues *pq;
498         u_short queue;
499
500         queue = m->queue;
501         if (queue != PQ_NONE) {
502                 pq = &vm_page_queues[queue];
503                 TAILQ_REMOVE(&pq->pl, m, pageq);
504                 atomic_add_int(pq->cnt, -1);
505                 pq->lcnt--;
506                 m->queue = PQ_NONE;
507                 vm_page_queues_spin_unlock(queue);
508                 if ((queue - m->pc) == PQ_FREE && (m->flags & PG_ZERO))
509                         atomic_subtract_int(&vm_page_zero_count, 1);
510                 if ((queue - m->pc) == PQ_CACHE || (queue - m->pc) == PQ_FREE)
511                         return (queue - m->pc);
512         }
513         return queue;
514 }
515
516 /*
517  * Helper function places the vm_page on the specified queue.
518  *
519  * The vm_page must be spinlocked.
520  * This function will return with both the page and the queue locked.
521  */
522 static __inline void
523 _vm_page_add_queue_spinlocked(vm_page_t m, u_short queue, int athead)
524 {
525         struct vpgqueues *pq;
526
527         KKASSERT(m->queue == PQ_NONE);
528
529         if (queue != PQ_NONE) {
530                 vm_page_queues_spin_lock(queue);
531                 pq = &vm_page_queues[queue];
532                 ++pq->lcnt;
533                 atomic_add_int(pq->cnt, 1);
534                 m->queue = queue;
535
536                 /*
537                  * Put zero'd pages on the end ( where we look for zero'd pages
538                  * first ) and non-zerod pages at the head.
539                  */
540                 if (queue - m->pc == PQ_FREE) {
541                         if (m->flags & PG_ZERO) {
542                                 TAILQ_INSERT_TAIL(&pq->pl, m, pageq);
543                                 atomic_add_int(&vm_page_zero_count, 1);
544                         } else {
545                                 TAILQ_INSERT_HEAD(&pq->pl, m, pageq);
546                         }
547                 } else if (athead) {
548                         TAILQ_INSERT_HEAD(&pq->pl, m, pageq);
549                 } else {
550                         TAILQ_INSERT_TAIL(&pq->pl, m, pageq);
551                 }
552                 /* leave the queue spinlocked */
553         }
554 }
555
556 /*
557  * Wait until page is no longer PG_BUSY or (if also_m_busy is TRUE)
558  * m->busy is zero.  Returns TRUE if it had to sleep, FALSE if we
559  * did not.  Only one sleep call will be made before returning.
560  *
561  * This function does NOT busy the page and on return the page is not
562  * guaranteed to be available.
563  */
564 void
565 vm_page_sleep_busy(vm_page_t m, int also_m_busy, const char *msg)
566 {
567         u_int32_t flags;
568
569         for (;;) {
570                 flags = m->flags;
571                 cpu_ccfence();
572
573                 if ((flags & PG_BUSY) == 0 &&
574                     (also_m_busy == 0 || (flags & PG_SBUSY) == 0)) {
575                         break;
576                 }
577                 tsleep_interlock(m, 0);
578                 if (atomic_cmpset_int(&m->flags, flags,
579                                       flags | PG_WANTED | PG_REFERENCED)) {
580                         tsleep(m, PINTERLOCKED, msg, 0);
581                         break;
582                 }
583         }
584 }
585
586 /*
587  * Wait until PG_BUSY can be set, then set it.  If also_m_busy is TRUE we
588  * also wait for m->busy to become 0 before setting PG_BUSY.
589  */
590 void
591 VM_PAGE_DEBUG_EXT(vm_page_busy_wait)(vm_page_t m,
592                                      int also_m_busy, const char *msg
593                                      VM_PAGE_DEBUG_ARGS)
594 {
595         u_int32_t flags;
596
597         for (;;) {
598                 flags = m->flags;
599                 cpu_ccfence();
600                 if (flags & PG_BUSY) {
601                         tsleep_interlock(m, 0);
602                         if (atomic_cmpset_int(&m->flags, flags,
603                                           flags | PG_WANTED | PG_REFERENCED)) {
604                                 tsleep(m, PINTERLOCKED, msg, 0);
605                         }
606                 } else if (also_m_busy && (flags & PG_SBUSY)) {
607                         tsleep_interlock(m, 0);
608                         if (atomic_cmpset_int(&m->flags, flags,
609                                           flags | PG_WANTED | PG_REFERENCED)) {
610                                 tsleep(m, PINTERLOCKED, msg, 0);
611                         }
612                 } else {
613                         if (atomic_cmpset_int(&m->flags, flags,
614                                               flags | PG_BUSY)) {
615 #ifdef VM_PAGE_DEBUG
616                                 m->busy_func = func;
617                                 m->busy_line = lineno;
618 #endif
619                                 break;
620                         }
621                 }
622         }
623 }
624
625 /*
626  * Attempt to set PG_BUSY.  If also_m_busy is TRUE we only succeed if m->busy
627  * is also 0.
628  *
629  * Returns non-zero on failure.
630  */
631 int
632 VM_PAGE_DEBUG_EXT(vm_page_busy_try)(vm_page_t m, int also_m_busy
633                                     VM_PAGE_DEBUG_ARGS)
634 {
635         u_int32_t flags;
636
637         for (;;) {
638                 flags = m->flags;
639                 cpu_ccfence();
640                 if (flags & PG_BUSY)
641                         return TRUE;
642                 if (also_m_busy && (flags & PG_SBUSY))
643                         return TRUE;
644                 if (atomic_cmpset_int(&m->flags, flags, flags | PG_BUSY)) {
645 #ifdef VM_PAGE_DEBUG
646                                 m->busy_func = func;
647                                 m->busy_line = lineno;
648 #endif
649                         return FALSE;
650                 }
651         }
652 }
653
654 /*
655  * Clear the PG_BUSY flag and return non-zero to indicate to the caller
656  * that a wakeup() should be performed.
657  *
658  * The vm_page must be spinlocked and will remain spinlocked on return.
659  * The related queue must NOT be spinlocked (which could deadlock us).
660  *
661  * (inline version)
662  */
663 static __inline
664 int
665 _vm_page_wakeup(vm_page_t m)
666 {
667         u_int32_t flags;
668
669         for (;;) {
670                 flags = m->flags;
671                 cpu_ccfence();
672                 if (atomic_cmpset_int(&m->flags, flags,
673                                       flags & ~(PG_BUSY | PG_WANTED))) {
674                         break;
675                 }
676         }
677         return(flags & PG_WANTED);
678 }
679
680 /*
681  * Clear the PG_BUSY flag and wakeup anyone waiting for the page.  This
682  * is typically the last call you make on a page before moving onto
683  * other things.
684  */
685 void
686 vm_page_wakeup(vm_page_t m)
687 {
688         KASSERT(m->flags & PG_BUSY, ("vm_page_wakeup: page not busy!!!"));
689         vm_page_spin_lock(m);
690         if (_vm_page_wakeup(m)) {
691                 vm_page_spin_unlock(m);
692                 wakeup(m);
693         } else {
694                 vm_page_spin_unlock(m);
695         }
696 }
697
698 /*
699  * Holding a page keeps it from being reused.  Other parts of the system
700  * can still disassociate the page from its current object and free it, or
701  * perform read or write I/O on it and/or otherwise manipulate the page,
702  * but if the page is held the VM system will leave the page and its data
703  * intact and not reuse the page for other purposes until the last hold
704  * reference is released.  (see vm_page_wire() if you want to prevent the
705  * page from being disassociated from its object too).
706  *
707  * The caller must still validate the contents of the page and, if necessary,
708  * wait for any pending I/O (e.g. vm_page_sleep_busy() loop) to complete
709  * before manipulating the page.
710  *
711  * XXX get vm_page_spin_lock() here and move FREE->HOLD if necessary
712  */
713 void
714 vm_page_hold(vm_page_t m)
715 {
716         vm_page_spin_lock(m);
717         atomic_add_int(&m->hold_count, 1);
718         if (m->queue - m->pc == PQ_FREE) {
719                 _vm_page_queue_spin_lock(m);
720                 _vm_page_rem_queue_spinlocked(m);
721                 _vm_page_add_queue_spinlocked(m, PQ_HOLD, 0);
722                 _vm_page_queue_spin_unlock(m);
723         }
724         vm_page_spin_unlock(m);
725 }
726
727 /*
728  * The opposite of vm_page_hold().  A page can be freed while being held,
729  * which places it on the PQ_HOLD queue.  If we are able to busy the page
730  * after the hold count drops to zero we will move the page to the
731  * appropriate PQ_FREE queue by calling vm_page_free_toq().
732  */
733 void
734 vm_page_unhold(vm_page_t m)
735 {
736         vm_page_spin_lock(m);
737         atomic_add_int(&m->hold_count, -1);
738         if (m->hold_count == 0 && m->queue == PQ_HOLD) {
739                 _vm_page_queue_spin_lock(m);
740                 _vm_page_rem_queue_spinlocked(m);
741                 _vm_page_add_queue_spinlocked(m, PQ_FREE + m->pc, 0);
742                 _vm_page_queue_spin_unlock(m);
743         }
744         vm_page_spin_unlock(m);
745 }
746
747 /*
748  * Inserts the given vm_page into the object and object list.
749  *
750  * The pagetables are not updated but will presumably fault the page
751  * in if necessary, or if a kernel page the caller will at some point
752  * enter the page into the kernel's pmap.  We are not allowed to block
753  * here so we *can't* do this anyway.
754  *
755  * This routine may not block.
756  * This routine must be called with the vm_object held.
757  * This routine must be called with a critical section held.
758  */
759 void
760 vm_page_insert(vm_page_t m, vm_object_t object, vm_pindex_t pindex)
761 {
762         ASSERT_LWKT_TOKEN_HELD(vm_object_token(object));
763         if (m->object != NULL)
764                 panic("vm_page_insert: already inserted");
765
766         object->generation++;
767         object->resident_page_count++;
768
769         /*
770          * Record the object/offset pair in this page and add the
771          * pv_list_count of the page to the object.
772          *
773          * The vm_page spin lock is required for interactions with the pmap.
774          */
775         vm_page_spin_lock(m);
776         m->object = object;
777         m->pindex = pindex;
778         vm_page_rb_tree_RB_INSERT(&object->rb_memq, m);
779         /* atomic_add_int(&object->agg_pv_list_count, m->md.pv_list_count); */
780         vm_page_spin_unlock(m);
781
782         /*
783          * Since we are inserting a new and possibly dirty page,
784          * update the object's OBJ_WRITEABLE and OBJ_MIGHTBEDIRTY flags.
785          */
786         if ((m->valid & m->dirty) || (m->flags & PG_WRITEABLE))
787                 vm_object_set_writeable_dirty(object);
788
789         /*
790          * Checks for a swap assignment and sets PG_SWAPPED if appropriate.
791          */
792         swap_pager_page_inserted(m);
793 }
794
795 /*
796  * Removes the given vm_page_t from the (object,index) table
797  *
798  * The underlying pmap entry (if any) is NOT removed here.
799  * This routine may not block.
800  *
801  * The page must be BUSY and will remain BUSY on return.
802  * No other requirements.
803  *
804  * NOTE: FreeBSD side effect was to unbusy the page on return.  We leave
805  *       it busy.
806  */
807 void
808 vm_page_remove(vm_page_t m)
809 {
810         vm_object_t object;
811
812         if (m->object == NULL) {
813                 return;
814         }
815
816         if ((m->flags & PG_BUSY) == 0)
817                 panic("vm_page_remove: page not busy");
818
819         object = m->object;
820
821         vm_object_hold(object);
822
823         /*
824          * Remove the page from the object and update the object.
825          *
826          * The vm_page spin lock is required for interactions with the pmap.
827          */
828         vm_page_spin_lock(m);
829         vm_page_rb_tree_RB_REMOVE(&object->rb_memq, m);
830         object->resident_page_count--;
831         /* atomic_add_int(&object->agg_pv_list_count, -m->md.pv_list_count); */
832         m->object = NULL;
833         vm_page_spin_unlock(m);
834
835         object->generation++;
836
837         vm_object_drop(object);
838 }
839
840 /*
841  * Locate and return the page at (object, pindex), or NULL if the
842  * page could not be found.
843  *
844  * The caller must hold the vm_object token.
845  */
846 vm_page_t
847 vm_page_lookup(vm_object_t object, vm_pindex_t pindex)
848 {
849         vm_page_t m;
850
851         /*
852          * Search the hash table for this object/offset pair
853          */
854         ASSERT_LWKT_TOKEN_HELD(vm_object_token(object));
855         m = vm_page_rb_tree_RB_LOOKUP(&object->rb_memq, pindex);
856         KKASSERT(m == NULL || (m->object == object && m->pindex == pindex));
857         return(m);
858 }
859
860 vm_page_t
861 VM_PAGE_DEBUG_EXT(vm_page_lookup_busy_wait)(struct vm_object *object,
862                                             vm_pindex_t pindex,
863                                             int also_m_busy, const char *msg
864                                             VM_PAGE_DEBUG_ARGS)
865 {
866         u_int32_t flags;
867         vm_page_t m;
868
869         ASSERT_LWKT_TOKEN_HELD(vm_object_token(object));
870         m = vm_page_rb_tree_RB_LOOKUP(&object->rb_memq, pindex);
871         while (m) {
872                 KKASSERT(m->object == object && m->pindex == pindex);
873                 flags = m->flags;
874                 cpu_ccfence();
875                 if (flags & PG_BUSY) {
876                         tsleep_interlock(m, 0);
877                         if (atomic_cmpset_int(&m->flags, flags,
878                                           flags | PG_WANTED | PG_REFERENCED)) {
879                                 tsleep(m, PINTERLOCKED, msg, 0);
880                                 m = vm_page_rb_tree_RB_LOOKUP(&object->rb_memq,
881                                                               pindex);
882                         }
883                 } else if (also_m_busy && (flags & PG_SBUSY)) {
884                         tsleep_interlock(m, 0);
885                         if (atomic_cmpset_int(&m->flags, flags,
886                                           flags | PG_WANTED | PG_REFERENCED)) {
887                                 tsleep(m, PINTERLOCKED, msg, 0);
888                                 m = vm_page_rb_tree_RB_LOOKUP(&object->rb_memq,
889                                                               pindex);
890                         }
891                 } else if (atomic_cmpset_int(&m->flags, flags,
892                                              flags | PG_BUSY)) {
893 #ifdef VM_PAGE_DEBUG
894                         m->busy_func = func;
895                         m->busy_line = lineno;
896 #endif
897                         break;
898                 }
899         }
900         return m;
901 }
902
903 /*
904  * Attempt to lookup and busy a page.
905  *
906  * Returns NULL if the page could not be found
907  *
908  * Returns a vm_page and error == TRUE if the page exists but could not
909  * be busied.
910  *
911  * Returns a vm_page and error == FALSE on success.
912  */
913 vm_page_t
914 VM_PAGE_DEBUG_EXT(vm_page_lookup_busy_try)(struct vm_object *object,
915                                            vm_pindex_t pindex,
916                                            int also_m_busy, int *errorp
917                                            VM_PAGE_DEBUG_ARGS)
918 {
919         u_int32_t flags;
920         vm_page_t m;
921
922         ASSERT_LWKT_TOKEN_HELD(vm_object_token(object));
923         m = vm_page_rb_tree_RB_LOOKUP(&object->rb_memq, pindex);
924         *errorp = FALSE;
925         while (m) {
926                 KKASSERT(m->object == object && m->pindex == pindex);
927                 flags = m->flags;
928                 cpu_ccfence();
929                 if (flags & PG_BUSY) {
930                         *errorp = TRUE;
931                         break;
932                 }
933                 if (also_m_busy && (flags & PG_SBUSY)) {
934                         *errorp = TRUE;
935                         break;
936                 }
937                 if (atomic_cmpset_int(&m->flags, flags, flags | PG_BUSY)) {
938 #ifdef VM_PAGE_DEBUG
939                         m->busy_func = func;
940                         m->busy_line = lineno;
941 #endif
942                         break;
943                 }
944         }
945         return m;
946 }
947
948 /*
949  * Caller must hold the related vm_object
950  */
951 vm_page_t
952 vm_page_next(vm_page_t m)
953 {
954         vm_page_t next;
955
956         next = vm_page_rb_tree_RB_NEXT(m);
957         if (next && next->pindex != m->pindex + 1)
958                 next = NULL;
959         return (next);
960 }
961
962 /*
963  * vm_page_rename()
964  *
965  * Move the given vm_page from its current object to the specified
966  * target object/offset.  The page must be busy and will remain so
967  * on return.
968  *
969  * new_object must be held.
970  * This routine might block. XXX ?
971  *
972  * NOTE: Swap associated with the page must be invalidated by the move.  We
973  *       have to do this for several reasons:  (1) we aren't freeing the
974  *       page, (2) we are dirtying the page, (3) the VM system is probably
975  *       moving the page from object A to B, and will then later move
976  *       the backing store from A to B and we can't have a conflict.
977  *
978  * NOTE: We *always* dirty the page.  It is necessary both for the
979  *       fact that we moved it, and because we may be invalidating
980  *       swap.  If the page is on the cache, we have to deactivate it
981  *       or vm_page_dirty() will panic.  Dirty pages are not allowed
982  *       on the cache.
983  */
984 void
985 vm_page_rename(vm_page_t m, vm_object_t new_object, vm_pindex_t new_pindex)
986 {
987         KKASSERT(m->flags & PG_BUSY);
988         ASSERT_LWKT_TOKEN_HELD(vm_object_token(new_object));
989         if (m->object) {
990                 ASSERT_LWKT_TOKEN_HELD(vm_object_token(m->object));
991                 vm_page_remove(m);
992         }
993         vm_page_insert(m, new_object, new_pindex);
994         if (m->queue - m->pc == PQ_CACHE)
995                 vm_page_deactivate(m);
996         vm_page_dirty(m);
997 }
998
999 /*
1000  * vm_page_unqueue() without any wakeup.  This routine is used when a page
1001  * is being moved between queues or otherwise is to remain BUSYied by the
1002  * caller.
1003  *
1004  * This routine may not block.
1005  */
1006 void
1007 vm_page_unqueue_nowakeup(vm_page_t m)
1008 {
1009         vm_page_and_queue_spin_lock(m);
1010         (void)_vm_page_rem_queue_spinlocked(m);
1011         vm_page_spin_unlock(m);
1012 }
1013
1014 /*
1015  * vm_page_unqueue() - Remove a page from its queue, wakeup the pagedemon
1016  * if necessary.
1017  *
1018  * This routine may not block.
1019  */
1020 void
1021 vm_page_unqueue(vm_page_t m)
1022 {
1023         u_short queue;
1024
1025         vm_page_and_queue_spin_lock(m);
1026         queue = _vm_page_rem_queue_spinlocked(m);
1027         if (queue == PQ_FREE || queue == PQ_CACHE) {
1028                 vm_page_spin_unlock(m);
1029                 pagedaemon_wakeup();
1030         } else {
1031                 vm_page_spin_unlock(m);
1032         }
1033 }
1034
1035 /*
1036  * vm_page_list_find()
1037  *
1038  * Find a page on the specified queue with color optimization.
1039  *
1040  * The page coloring optimization attempts to locate a page that does
1041  * not overload other nearby pages in the object in the cpu's L1 or L2
1042  * caches.  We need this optimization because cpu caches tend to be
1043  * physical caches, while object spaces tend to be virtual.
1044  *
1045  * On MP systems each PQ_FREE and PQ_CACHE color queue has its own spinlock
1046  * and the algorithm is adjusted to localize allocations on a per-core basis.
1047  * This is done by 'twisting' the colors.
1048  *
1049  * The page is returned spinlocked and removed from its queue (it will
1050  * be on PQ_NONE), or NULL. The page is not PG_BUSY'd.  The caller
1051  * is responsible for dealing with the busy-page case (usually by
1052  * deactivating the page and looping).
1053  *
1054  * NOTE:  This routine is carefully inlined.  A non-inlined version
1055  *        is available for outside callers but the only critical path is
1056  *        from within this source file.
1057  *
1058  * NOTE:  This routine assumes that the vm_pages found in PQ_CACHE and PQ_FREE
1059  *        represent stable storage, allowing us to order our locks vm_page
1060  *        first, then queue.
1061  */
1062 static __inline
1063 vm_page_t
1064 _vm_page_list_find(int basequeue, int index, boolean_t prefer_zero)
1065 {
1066         vm_page_t m;
1067
1068         for (;;) {
1069                 if (prefer_zero)
1070                         m = TAILQ_LAST(&vm_page_queues[basequeue+index].pl, pglist);
1071                 else
1072                         m = TAILQ_FIRST(&vm_page_queues[basequeue+index].pl);
1073                 if (m == NULL) {
1074                         m = _vm_page_list_find2(basequeue, index);
1075                         return(m);
1076                 }
1077                 vm_page_and_queue_spin_lock(m);
1078                 if (m->queue == basequeue + index) {
1079                         _vm_page_rem_queue_spinlocked(m);
1080                         /* vm_page_t spin held, no queue spin */
1081                         break;
1082                 }
1083                 vm_page_and_queue_spin_unlock(m);
1084         }
1085         return(m);
1086 }
1087
1088 static vm_page_t
1089 _vm_page_list_find2(int basequeue, int index)
1090 {
1091         int i;
1092         vm_page_t m = NULL;
1093         struct vpgqueues *pq;
1094
1095         pq = &vm_page_queues[basequeue];
1096
1097         /*
1098          * Note that for the first loop, index+i and index-i wind up at the
1099          * same place.  Even though this is not totally optimal, we've already
1100          * blown it by missing the cache case so we do not care.
1101          */
1102         for (i = PQ_L2_SIZE / 2; i > 0; --i) {
1103                 for (;;) {
1104                         m = TAILQ_FIRST(&pq[(index + i) & PQ_L2_MASK].pl);
1105                         if (m) {
1106                                 _vm_page_and_queue_spin_lock(m);
1107                                 if (m->queue ==
1108                                     basequeue + ((index + i) & PQ_L2_MASK)) {
1109                                         _vm_page_rem_queue_spinlocked(m);
1110                                         return(m);
1111                                 }
1112                                 _vm_page_and_queue_spin_unlock(m);
1113                                 continue;
1114                         }
1115                         m = TAILQ_FIRST(&pq[(index - i) & PQ_L2_MASK].pl);
1116                         if (m) {
1117                                 _vm_page_and_queue_spin_lock(m);
1118                                 if (m->queue ==
1119                                     basequeue + ((index - i) & PQ_L2_MASK)) {
1120                                         _vm_page_rem_queue_spinlocked(m);
1121                                         return(m);
1122                                 }
1123                                 _vm_page_and_queue_spin_unlock(m);
1124                                 continue;
1125                         }
1126                         break;  /* next i */
1127                 }
1128         }
1129         return(m);
1130 }
1131
1132 /*
1133  * Returns a vm_page candidate for allocation.  The page is not busied so
1134  * it can move around.  The caller must busy the page (and typically
1135  * deactivate it if it cannot be busied!)
1136  *
1137  * Returns a spinlocked vm_page that has been removed from its queue.
1138  */
1139 vm_page_t
1140 vm_page_list_find(int basequeue, int index, boolean_t prefer_zero)
1141 {
1142         return(_vm_page_list_find(basequeue, index, prefer_zero));
1143 }
1144
1145 /*
1146  * Find a page on the cache queue with color optimization, remove it
1147  * from the queue, and busy it.  The returned page will not be spinlocked.
1148  *
1149  * A candidate failure will be deactivated.  Candidates can fail due to
1150  * being busied by someone else, in which case they will be deactivated.
1151  *
1152  * This routine may not block.
1153  *
1154  */
1155 static vm_page_t
1156 vm_page_select_cache(u_short pg_color)
1157 {
1158         vm_page_t m;
1159
1160         for (;;) {
1161                 m = _vm_page_list_find(PQ_CACHE, pg_color & PQ_L2_MASK, FALSE);
1162                 if (m == NULL)
1163                         break;
1164                 /*
1165                  * (m) has been removed from its queue and spinlocked
1166                  */
1167                 if (vm_page_busy_try(m, TRUE)) {
1168                         _vm_page_deactivate_locked(m, 0);
1169                         vm_page_spin_unlock(m);
1170 #ifdef INVARIANTS
1171                         kprintf("Warning: busy page %p found in cache\n", m);
1172 #endif
1173                 } else {
1174                         /*
1175                          * We successfully busied the page
1176                          */
1177                         if ((m->flags & PG_UNMANAGED) == 0 &&
1178                             m->hold_count == 0 &&
1179                             m->wire_count == 0) {
1180                                 vm_page_spin_unlock(m);
1181                                 pagedaemon_wakeup();
1182                                 return(m);
1183                         }
1184                         _vm_page_deactivate_locked(m, 0);
1185                         if (_vm_page_wakeup(m)) {
1186                                 vm_page_spin_unlock(m);
1187                                 wakeup(m);
1188                         } else {
1189                                 vm_page_spin_unlock(m);
1190                         }
1191                 }
1192         }
1193         return (m);
1194 }
1195
1196 /*
1197  * Find a free or zero page, with specified preference.  We attempt to
1198  * inline the nominal case and fall back to _vm_page_select_free() 
1199  * otherwise.  A busied page is removed from the queue and returned.
1200  *
1201  * This routine may not block.
1202  */
1203 static __inline vm_page_t
1204 vm_page_select_free(u_short pg_color, boolean_t prefer_zero)
1205 {
1206         vm_page_t m;
1207
1208         for (;;) {
1209                 m = _vm_page_list_find(PQ_FREE, pg_color & PQ_L2_MASK,
1210                                        prefer_zero);
1211                 if (m == NULL)
1212                         break;
1213                 if (vm_page_busy_try(m, TRUE)) {
1214                         _vm_page_deactivate_locked(m, 0);
1215                         vm_page_spin_unlock(m);
1216 #ifdef INVARIANTS
1217                         kprintf("Warning: busy page %p found in cache\n", m);
1218 #endif
1219                 } else {
1220                         KKASSERT((m->flags & PG_UNMANAGED) == 0);
1221                         KKASSERT(m->hold_count == 0);
1222                         KKASSERT(m->wire_count == 0);
1223                         vm_page_spin_unlock(m);
1224                         pagedaemon_wakeup();
1225
1226                         /* return busied and removed page */
1227                         return(m);
1228                 }
1229         }
1230         return(m);
1231 }
1232
1233 /*
1234  * vm_page_alloc()
1235  *
1236  * Allocate and return a memory cell associated with this VM object/offset
1237  * pair.  If object is NULL an unassociated page will be allocated.
1238  *
1239  *      page_req classes:
1240  *
1241  *      VM_ALLOC_NORMAL         allow use of cache pages, nominal free drain
1242  *      VM_ALLOC_QUICK          like normal but cannot use cache
1243  *      VM_ALLOC_SYSTEM         greater free drain
1244  *      VM_ALLOC_INTERRUPT      allow free list to be completely drained
1245  *      VM_ALLOC_ZERO           advisory request for pre-zero'd page
1246  *
1247  * The object must be locked if not NULL
1248  * This routine may not block
1249  * The returned page will be marked PG_BUSY
1250  *
1251  * Additional special handling is required when called from an interrupt
1252  * (VM_ALLOC_INTERRUPT).  We are not allowed to mess with the page cache
1253  * in this case.
1254  */
1255 vm_page_t
1256 vm_page_alloc(vm_object_t object, vm_pindex_t pindex, int page_req)
1257 {
1258         vm_page_t m = NULL;
1259         u_short pg_color;
1260
1261 #ifdef SMP
1262         /*
1263          * Cpu twist - cpu localization algorithm
1264          */
1265         if (object) {
1266                 pg_color = mycpu->gd_cpuid + (pindex & ~ncpus_fit_mask) +
1267                            (object->pg_color & ~ncpus_fit_mask);
1268                 KASSERT(vm_page_lookup(object, pindex) == NULL,
1269                         ("vm_page_alloc: page already allocated"));
1270         } else {
1271                 pg_color = mycpu->gd_cpuid + (pindex & ~ncpus_fit_mask);
1272         }
1273 #else
1274         /*
1275          * Normal page coloring algorithm
1276          */
1277         if (object) {
1278                 pg_color = object->pg_color + pindex;
1279                 KASSERT(vm_page_lookup(object, pindex) == NULL,
1280                         ("vm_page_alloc: page already allocated"));
1281         } else {
1282                 pg_color = pindex;
1283         }
1284 #endif
1285         KKASSERT(page_req & 
1286                 (VM_ALLOC_NORMAL|VM_ALLOC_QUICK|
1287                  VM_ALLOC_INTERRUPT|VM_ALLOC_SYSTEM));
1288
1289         /*
1290          * Certain system threads (pageout daemon, buf_daemon's) are
1291          * allowed to eat deeper into the free page list.
1292          */
1293         if (curthread->td_flags & TDF_SYSTHREAD)
1294                 page_req |= VM_ALLOC_SYSTEM;
1295
1296 loop:
1297         if (vmstats.v_free_count > vmstats.v_free_reserved ||
1298             ((page_req & VM_ALLOC_INTERRUPT) && vmstats.v_free_count > 0) ||
1299             ((page_req & VM_ALLOC_SYSTEM) && vmstats.v_cache_count == 0 &&
1300                 vmstats.v_free_count > vmstats.v_interrupt_free_min)
1301         ) {
1302                 /*
1303                  * The free queue has sufficient free pages to take one out.
1304                  */
1305                 if (page_req & VM_ALLOC_ZERO)
1306                         m = vm_page_select_free(pg_color, TRUE);
1307                 else
1308                         m = vm_page_select_free(pg_color, FALSE);
1309         } else if (page_req & VM_ALLOC_NORMAL) {
1310                 /*
1311                  * Allocatable from the cache (non-interrupt only).  On
1312                  * success, we must free the page and try again, thus
1313                  * ensuring that vmstats.v_*_free_min counters are replenished.
1314                  */
1315 #ifdef INVARIANTS
1316                 if (curthread->td_preempted) {
1317                         kprintf("vm_page_alloc(): warning, attempt to allocate"
1318                                 " cache page from preempting interrupt\n");
1319                         m = NULL;
1320                 } else {
1321                         m = vm_page_select_cache(pg_color);
1322                 }
1323 #else
1324                 m = vm_page_select_cache(pg_color);
1325 #endif
1326                 /*
1327                  * On success move the page into the free queue and loop.
1328                  */
1329                 if (m != NULL) {
1330                         KASSERT(m->dirty == 0,
1331                             ("Found dirty cache page %p", m));
1332                         vm_page_protect(m, VM_PROT_NONE);
1333                         vm_page_free(m);
1334                         goto loop;
1335                 }
1336
1337                 /*
1338                  * On failure return NULL
1339                  */
1340 #if defined(DIAGNOSTIC)
1341                 if (vmstats.v_cache_count > 0)
1342                         kprintf("vm_page_alloc(NORMAL): missing pages on cache queue: %d\n", vmstats.v_cache_count);
1343 #endif
1344                 vm_pageout_deficit++;
1345                 pagedaemon_wakeup();
1346                 return (NULL);
1347         } else {
1348                 /*
1349                  * No pages available, wakeup the pageout daemon and give up.
1350                  */
1351                 vm_pageout_deficit++;
1352                 pagedaemon_wakeup();
1353                 return (NULL);
1354         }
1355
1356         /*
1357          * Good page found.  The page has already been busied for us.
1358          *
1359          * v_free_count can race so loop if we don't find the expected
1360          * page.
1361          */
1362         if (m == NULL)
1363                 goto loop;
1364         KASSERT(m->dirty == 0, 
1365                 ("vm_page_alloc: free/cache page %p was dirty", m));
1366
1367         /*
1368          * NOTE: page has already been removed from its queue and busied.
1369          */
1370         KKASSERT(m->queue == PQ_NONE);
1371
1372         /*
1373          * Initialize structure.  Only the PG_ZERO flag is inherited.  Set
1374          * the page PG_BUSY
1375          */
1376         vm_page_flag_clear(m, ~(PG_ZERO | PG_BUSY));
1377         KKASSERT(m->wire_count == 0);
1378         KKASSERT(m->busy == 0);
1379         m->act_count = 0;
1380         m->valid = 0;
1381
1382         /*
1383          * Caller must be holding the object lock (asserted by
1384          * vm_page_insert()).
1385          *
1386          * NOTE: Inserting a page here does not insert it into any pmaps
1387          *       (which could cause us to block allocating memory).
1388          *
1389          * NOTE: If no object an unassociated page is allocated, m->pindex
1390          *       can be used by the caller for any purpose.
1391          */
1392         if (object)
1393                 vm_page_insert(m, object, pindex);
1394         else
1395                 m->pindex = pindex;
1396
1397         /*
1398          * Don't wakeup too often - wakeup the pageout daemon when
1399          * we would be nearly out of memory.
1400          */
1401         pagedaemon_wakeup();
1402
1403         /*
1404          * A PG_BUSY page is returned.
1405          */
1406         return (m);
1407 }
1408
1409 /*
1410  * Wait for sufficient free memory for nominal heavy memory use kernel
1411  * operations.
1412  */
1413 void
1414 vm_wait_nominal(void)
1415 {
1416         while (vm_page_count_min(0))
1417                 vm_wait(0);
1418 }
1419
1420 /*
1421  * Test if vm_wait_nominal() would block.
1422  */
1423 int
1424 vm_test_nominal(void)
1425 {
1426         if (vm_page_count_min(0))
1427                 return(1);
1428         return(0);
1429 }
1430
1431 /*
1432  * Block until free pages are available for allocation, called in various
1433  * places before memory allocations.
1434  *
1435  * The caller may loop if vm_page_count_min() == FALSE so we cannot be
1436  * more generous then that.
1437  */
1438 void
1439 vm_wait(int timo)
1440 {
1441         /*
1442          * never wait forever
1443          */
1444         if (timo == 0)
1445                 timo = hz;
1446         lwkt_gettoken(&vm_token);
1447
1448         if (curthread == pagethread) {
1449                 /*
1450                  * The pageout daemon itself needs pages, this is bad.
1451                  */
1452                 if (vm_page_count_min(0)) {
1453                         vm_pageout_pages_needed = 1;
1454                         tsleep(&vm_pageout_pages_needed, 0, "VMWait", timo);
1455                 }
1456         } else {
1457                 /*
1458                  * Wakeup the pageout daemon if necessary and wait.
1459                  */
1460                 if (vm_page_count_target()) {
1461                         if (vm_pages_needed == 0) {
1462                                 vm_pages_needed = 1;
1463                                 wakeup(&vm_pages_needed);
1464                         }
1465                         ++vm_pages_waiting;     /* SMP race ok */
1466                         tsleep(&vmstats.v_free_count, 0, "vmwait", timo);
1467                 }
1468         }
1469         lwkt_reltoken(&vm_token);
1470 }
1471
1472 /*
1473  * Block until free pages are available for allocation
1474  *
1475  * Called only from vm_fault so that processes page faulting can be
1476  * easily tracked.
1477  */
1478 void
1479 vm_waitpfault(void)
1480 {
1481         /*
1482          * Wakeup the pageout daemon if necessary and wait.
1483          */
1484         if (vm_page_count_target()) {
1485                 lwkt_gettoken(&vm_token);
1486                 if (vm_page_count_target()) {
1487                         if (vm_pages_needed == 0) {
1488                                 vm_pages_needed = 1;
1489                                 wakeup(&vm_pages_needed);
1490                         }
1491                         ++vm_pages_waiting;     /* SMP race ok */
1492                         tsleep(&vmstats.v_free_count, 0, "pfault", hz);
1493                 }
1494                 lwkt_reltoken(&vm_token);
1495         }
1496 }
1497
1498 /*
1499  * Put the specified page on the active list (if appropriate).  Ensure
1500  * that act_count is at least ACT_INIT but do not otherwise mess with it.
1501  *
1502  * The caller should be holding the page busied ? XXX
1503  * This routine may not block.
1504  */
1505 void
1506 vm_page_activate(vm_page_t m)
1507 {
1508         u_short oqueue;
1509
1510         vm_page_spin_lock(m);
1511         if (m->queue != PQ_ACTIVE) {
1512                 _vm_page_queue_spin_lock(m);
1513                 oqueue = _vm_page_rem_queue_spinlocked(m);
1514                 /* page is left spinlocked, queue is unlocked */
1515
1516                 if (oqueue == PQ_CACHE)
1517                         mycpu->gd_cnt.v_reactivated++;
1518                 if (m->wire_count == 0 && (m->flags & PG_UNMANAGED) == 0) {
1519                         if (m->act_count < ACT_INIT)
1520                                 m->act_count = ACT_INIT;
1521                         _vm_page_add_queue_spinlocked(m, PQ_ACTIVE, 0);
1522                 }
1523                 _vm_page_and_queue_spin_unlock(m);
1524                 if (oqueue == PQ_CACHE || oqueue == PQ_FREE)
1525                         pagedaemon_wakeup();
1526         } else {
1527                 if (m->act_count < ACT_INIT)
1528                         m->act_count = ACT_INIT;
1529                 vm_page_spin_unlock(m);
1530         }
1531 }
1532
1533 /*
1534  * Helper routine for vm_page_free_toq() and vm_page_cache().  This
1535  * routine is called when a page has been added to the cache or free
1536  * queues.
1537  *
1538  * This routine may not block.
1539  */
1540 static __inline void
1541 vm_page_free_wakeup(void)
1542 {
1543         /*
1544          * If the pageout daemon itself needs pages, then tell it that
1545          * there are some free.
1546          */
1547         if (vm_pageout_pages_needed &&
1548             vmstats.v_cache_count + vmstats.v_free_count >= 
1549             vmstats.v_pageout_free_min
1550         ) {
1551                 wakeup(&vm_pageout_pages_needed);
1552                 vm_pageout_pages_needed = 0;
1553         }
1554
1555         /*
1556          * Wakeup processes that are waiting on memory.
1557          *
1558          * NOTE: vm_paging_target() is the pageout daemon's target, while
1559          *       vm_page_count_target() is somewhere inbetween.  We want
1560          *       to wake processes up prior to the pageout daemon reaching
1561          *       its target to provide some hysteresis.
1562          */
1563         if (vm_pages_waiting) {
1564                 if (!vm_page_count_target()) {
1565                         /*
1566                          * Plenty of pages are free, wakeup everyone.
1567                          */
1568                         vm_pages_waiting = 0;
1569                         wakeup(&vmstats.v_free_count);
1570                         ++mycpu->gd_cnt.v_ppwakeups;
1571                 } else if (!vm_page_count_min(0)) {
1572                         /*
1573                          * Some pages are free, wakeup someone.
1574                          */
1575                         int wcount = vm_pages_waiting;
1576                         if (wcount > 0)
1577                                 --wcount;
1578                         vm_pages_waiting = wcount;
1579                         wakeup_one(&vmstats.v_free_count);
1580                         ++mycpu->gd_cnt.v_ppwakeups;
1581                 }
1582         }
1583 }
1584
1585 /*
1586  * Returns the given page to the PQ_FREE or PQ_HOLD list and disassociates
1587  * it from its VM object.
1588  *
1589  * The vm_page must be PG_BUSY on entry.  PG_BUSY will be released on
1590  * return (the page will have been freed).
1591  */
1592 void
1593 vm_page_free_toq(vm_page_t m)
1594 {
1595         mycpu->gd_cnt.v_tfree++;
1596         KKASSERT((m->flags & PG_MAPPED) == 0);
1597         KKASSERT(m->flags & PG_BUSY);
1598
1599         if (m->busy || ((m->queue - m->pc) == PQ_FREE)) {
1600                 kprintf(
1601                 "vm_page_free: pindex(%lu), busy(%d), PG_BUSY(%d), hold(%d)\n",
1602                     (u_long)m->pindex, m->busy, (m->flags & PG_BUSY) ? 1 : 0,
1603                     m->hold_count);
1604                 if ((m->queue - m->pc) == PQ_FREE)
1605                         panic("vm_page_free: freeing free page");
1606                 else
1607                         panic("vm_page_free: freeing busy page");
1608         }
1609
1610         /*
1611          * Remove from object, spinlock the page and its queues and
1612          * remove from any queue.  No queue spinlock will be held
1613          * after this section (because the page was removed from any
1614          * queue).
1615          */
1616         vm_page_remove(m);
1617         vm_page_and_queue_spin_lock(m);
1618         _vm_page_rem_queue_spinlocked(m);
1619
1620         /*
1621          * No further management of fictitious pages occurs beyond object
1622          * and queue removal.
1623          */
1624         if ((m->flags & PG_FICTITIOUS) != 0) {
1625                 vm_page_spin_unlock(m);
1626                 vm_page_wakeup(m);
1627                 return;
1628         }
1629
1630         m->valid = 0;
1631         vm_page_undirty(m);
1632
1633         if (m->wire_count != 0) {
1634                 if (m->wire_count > 1) {
1635                     panic(
1636                         "vm_page_free: invalid wire count (%d), pindex: 0x%lx",
1637                         m->wire_count, (long)m->pindex);
1638                 }
1639                 panic("vm_page_free: freeing wired page");
1640         }
1641
1642         /*
1643          * Clear the UNMANAGED flag when freeing an unmanaged page.
1644          */
1645         if (m->flags & PG_UNMANAGED) {
1646                 vm_page_flag_clear(m, PG_UNMANAGED);
1647         }
1648
1649         if (m->hold_count != 0) {
1650                 vm_page_flag_clear(m, PG_ZERO);
1651                 _vm_page_add_queue_spinlocked(m, PQ_HOLD, 0);
1652         } else {
1653                 _vm_page_add_queue_spinlocked(m, PQ_FREE + m->pc, 0);
1654         }
1655
1656         /*
1657          * This sequence allows us to clear PG_BUSY while still holding
1658          * its spin lock, which reduces contention vs allocators.  We
1659          * must not leave the queue locked or _vm_page_wakeup() may
1660          * deadlock.
1661          */
1662         _vm_page_queue_spin_unlock(m);
1663         if (_vm_page_wakeup(m)) {
1664                 vm_page_spin_unlock(m);
1665                 wakeup(m);
1666         } else {
1667                 vm_page_spin_unlock(m);
1668         }
1669         vm_page_free_wakeup();
1670 }
1671
1672 /*
1673  * vm_page_free_fromq_fast()
1674  *
1675  * Remove a non-zero page from one of the free queues; the page is removed for
1676  * zeroing, so do not issue a wakeup.
1677  */
1678 vm_page_t
1679 vm_page_free_fromq_fast(void)
1680 {
1681         static int qi;
1682         vm_page_t m;
1683         int i;
1684
1685         for (i = 0; i < PQ_L2_SIZE; ++i) {
1686                 m = vm_page_list_find(PQ_FREE, qi, FALSE);
1687                 /* page is returned spinlocked and removed from its queue */
1688                 if (m) {
1689                         if (vm_page_busy_try(m, TRUE)) {
1690                                 /*
1691                                  * We were unable to busy the page, deactivate
1692                                  * it and loop.
1693                                  */
1694                                 _vm_page_deactivate_locked(m, 0);
1695                                 vm_page_spin_unlock(m);
1696                         } else if ((m->flags & PG_ZERO) == 0) {
1697                                 /*
1698                                  * The page is not PG_ZERO'd so return it.
1699                                  */
1700                                 vm_page_spin_unlock(m);
1701                                 break;
1702                         } else {
1703                                 /*
1704                                  * The page is PG_ZERO, requeue it and loop
1705                                  */
1706                                 _vm_page_add_queue_spinlocked(m,
1707                                                               PQ_FREE + m->pc,
1708                                                               0);
1709                                 vm_page_queue_spin_unlock(m);
1710                                 if (_vm_page_wakeup(m)) {
1711                                         vm_page_spin_unlock(m);
1712                                         wakeup(m);
1713                                 } else {
1714                                         vm_page_spin_unlock(m);
1715                                 }
1716                         }
1717                         m = NULL;
1718                 }
1719                 qi = (qi + PQ_PRIME2) & PQ_L2_MASK;
1720         }
1721         return (m);
1722 }
1723
1724 /*
1725  * vm_page_unmanage()
1726  *
1727  * Prevent PV management from being done on the page.  The page is
1728  * removed from the paging queues as if it were wired, and as a 
1729  * consequence of no longer being managed the pageout daemon will not
1730  * touch it (since there is no way to locate the pte mappings for the
1731  * page).  madvise() calls that mess with the pmap will also no longer
1732  * operate on the page.
1733  *
1734  * Beyond that the page is still reasonably 'normal'.  Freeing the page
1735  * will clear the flag.
1736  *
1737  * This routine is used by OBJT_PHYS objects - objects using unswappable
1738  * physical memory as backing store rather then swap-backed memory and
1739  * will eventually be extended to support 4MB unmanaged physical 
1740  * mappings.
1741  *
1742  * Caller must be holding the page busy.
1743  */
1744 void
1745 vm_page_unmanage(vm_page_t m)
1746 {
1747         KKASSERT(m->flags & PG_BUSY);
1748         if ((m->flags & PG_UNMANAGED) == 0) {
1749                 if (m->wire_count == 0)
1750                         vm_page_unqueue(m);
1751         }
1752         vm_page_flag_set(m, PG_UNMANAGED);
1753 }
1754
1755 /*
1756  * Mark this page as wired down by yet another map, removing it from
1757  * paging queues as necessary.
1758  *
1759  * Caller must be holding the page busy.
1760  */
1761 void
1762 vm_page_wire(vm_page_t m)
1763 {
1764         /*
1765          * Only bump the wire statistics if the page is not already wired,
1766          * and only unqueue the page if it is on some queue (if it is unmanaged
1767          * it is already off the queues).  Don't do anything with fictitious
1768          * pages because they are always wired.
1769          */
1770         KKASSERT(m->flags & PG_BUSY);
1771         if ((m->flags & PG_FICTITIOUS) == 0) {
1772                 if (atomic_fetchadd_int(&m->wire_count, 1) == 0) {
1773                         if ((m->flags & PG_UNMANAGED) == 0)
1774                                 vm_page_unqueue(m);
1775                         atomic_add_int(&vmstats.v_wire_count, 1);
1776                 }
1777                 KASSERT(m->wire_count != 0,
1778                         ("vm_page_wire: wire_count overflow m=%p", m));
1779         }
1780 }
1781
1782 /*
1783  * Release one wiring of this page, potentially enabling it to be paged again.
1784  *
1785  * Many pages placed on the inactive queue should actually go
1786  * into the cache, but it is difficult to figure out which.  What
1787  * we do instead, if the inactive target is well met, is to put
1788  * clean pages at the head of the inactive queue instead of the tail.
1789  * This will cause them to be moved to the cache more quickly and
1790  * if not actively re-referenced, freed more quickly.  If we just
1791  * stick these pages at the end of the inactive queue, heavy filesystem
1792  * meta-data accesses can cause an unnecessary paging load on memory bound 
1793  * processes.  This optimization causes one-time-use metadata to be
1794  * reused more quickly.
1795  *
1796  * BUT, if we are in a low-memory situation we have no choice but to
1797  * put clean pages on the cache queue.
1798  *
1799  * A number of routines use vm_page_unwire() to guarantee that the page
1800  * will go into either the inactive or active queues, and will NEVER
1801  * be placed in the cache - for example, just after dirtying a page.
1802  * dirty pages in the cache are not allowed.
1803  *
1804  * The page queues must be locked.
1805  * This routine may not block.
1806  */
1807 void
1808 vm_page_unwire(vm_page_t m, int activate)
1809 {
1810         KKASSERT(m->flags & PG_BUSY);
1811         if (m->flags & PG_FICTITIOUS) {
1812                 /* do nothing */
1813         } else if (m->wire_count <= 0) {
1814                 panic("vm_page_unwire: invalid wire count: %d", m->wire_count);
1815         } else {
1816                 if (atomic_fetchadd_int(&m->wire_count, -1) == 1) {
1817                         atomic_add_int(&vmstats.v_wire_count, -1);
1818                         if (m->flags & PG_UNMANAGED) {
1819                                 ;
1820                         } else if (activate) {
1821                                 vm_page_spin_lock(m);
1822                                 _vm_page_add_queue_spinlocked(m, PQ_ACTIVE, 0);
1823                                 _vm_page_and_queue_spin_unlock(m);
1824                         } else {
1825                                 vm_page_spin_lock(m);
1826                                 vm_page_flag_clear(m, PG_WINATCFLS);
1827                                 _vm_page_add_queue_spinlocked(m, PQ_INACTIVE,
1828                                                               0);
1829                                 ++vm_swapcache_inactive_heuristic;
1830                                 _vm_page_and_queue_spin_unlock(m);
1831                         }
1832                 }
1833         }
1834 }
1835
1836 /*
1837  * Move the specified page to the inactive queue.  If the page has
1838  * any associated swap, the swap is deallocated.
1839  *
1840  * Normally athead is 0 resulting in LRU operation.  athead is set
1841  * to 1 if we want this page to be 'as if it were placed in the cache',
1842  * except without unmapping it from the process address space.
1843  *
1844  * vm_page's spinlock must be held on entry and will remain held on return.
1845  * This routine may not block.
1846  */
1847 static void
1848 _vm_page_deactivate_locked(vm_page_t m, int athead)
1849 {
1850         u_short oqueue;
1851
1852         /*
1853          * Ignore if already inactive.
1854          */
1855         if (m->queue == PQ_INACTIVE)
1856                 return;
1857         _vm_page_queue_spin_lock(m);
1858         oqueue = _vm_page_rem_queue_spinlocked(m);
1859
1860         if (m->wire_count == 0 && (m->flags & PG_UNMANAGED) == 0) {
1861                 if (oqueue == PQ_CACHE)
1862                         mycpu->gd_cnt.v_reactivated++;
1863                 vm_page_flag_clear(m, PG_WINATCFLS);
1864                 _vm_page_add_queue_spinlocked(m, PQ_INACTIVE, athead);
1865                 if (athead == 0)
1866                         ++vm_swapcache_inactive_heuristic;
1867         }
1868         _vm_page_queue_spin_unlock(m);
1869         /* leaves vm_page spinlocked */
1870 }
1871
1872 /*
1873  * Attempt to deactivate a page.
1874  *
1875  * No requirements.
1876  */
1877 void
1878 vm_page_deactivate(vm_page_t m)
1879 {
1880         vm_page_spin_lock(m);
1881         _vm_page_deactivate_locked(m, 0);
1882         vm_page_spin_unlock(m);
1883 }
1884
1885 void
1886 vm_page_deactivate_locked(vm_page_t m)
1887 {
1888         _vm_page_deactivate_locked(m, 0);
1889 }
1890
1891 /*
1892  * Attempt to move a page to PQ_CACHE.
1893  *
1894  * Returns 0 on failure, 1 on success
1895  *
1896  * The page should NOT be busied by the caller.  This function will validate
1897  * whether the page can be safely moved to the cache.
1898  */
1899 int
1900 vm_page_try_to_cache(vm_page_t m)
1901 {
1902         vm_page_spin_lock(m);
1903         if (vm_page_busy_try(m, TRUE)) {
1904                 vm_page_spin_unlock(m);
1905                 return(0);
1906         }
1907         if (m->dirty || m->hold_count || m->wire_count ||
1908             (m->flags & PG_UNMANAGED)) {
1909                 if (_vm_page_wakeup(m)) {
1910                         vm_page_spin_unlock(m);
1911                         wakeup(m);
1912                 } else {
1913                         vm_page_spin_unlock(m);
1914                 }
1915                 return(0);
1916         }
1917         vm_page_spin_unlock(m);
1918
1919         /*
1920          * Page busied by us and no longer spinlocked.  Dirty pages cannot
1921          * be moved to the cache.
1922          */
1923         vm_page_test_dirty(m);
1924         if (m->dirty) {
1925                 vm_page_wakeup(m);
1926                 return(0);
1927         }
1928         vm_page_cache(m);
1929         return(1);
1930 }
1931
1932 /*
1933  * Attempt to free the page.  If we cannot free it, we do nothing.
1934  * 1 is returned on success, 0 on failure.
1935  *
1936  * No requirements.
1937  */
1938 int
1939 vm_page_try_to_free(vm_page_t m)
1940 {
1941         vm_page_spin_lock(m);
1942         if (vm_page_busy_try(m, TRUE)) {
1943                 vm_page_spin_unlock(m);
1944                 return(0);
1945         }
1946         if (m->dirty || m->hold_count || m->wire_count ||
1947             (m->flags & PG_UNMANAGED)) {
1948                 if (_vm_page_wakeup(m)) {
1949                         vm_page_spin_unlock(m);
1950                         wakeup(m);
1951                 } else {
1952                         vm_page_spin_unlock(m);
1953                 }
1954                 return(0);
1955         }
1956         vm_page_spin_unlock(m);
1957
1958         /*
1959          * Page busied by us and no longer spinlocked.  Dirty pages will
1960          * not be freed by this function.    We have to re-test the
1961          * dirty bit after cleaning out the pmaps.
1962          */
1963         vm_page_test_dirty(m);
1964         if (m->dirty) {
1965                 vm_page_wakeup(m);
1966                 return(0);
1967         }
1968         vm_page_protect(m, VM_PROT_NONE);
1969         if (m->dirty) {
1970                 vm_page_wakeup(m);
1971                 return(0);
1972         }
1973         vm_page_free(m);
1974         return(1);
1975 }
1976
1977 /*
1978  * vm_page_cache
1979  *
1980  * Put the specified page onto the page cache queue (if appropriate).
1981  *
1982  * The page must be busy, and this routine will release the busy and
1983  * possibly even free the page.
1984  */
1985 void
1986 vm_page_cache(vm_page_t m)
1987 {
1988         if ((m->flags & PG_UNMANAGED) || m->busy ||
1989             m->wire_count || m->hold_count) {
1990                 kprintf("vm_page_cache: attempting to cache busy/held page\n");
1991                 vm_page_wakeup(m);
1992                 return;
1993         }
1994
1995         /*
1996          * Already in the cache (and thus not mapped)
1997          */
1998         if ((m->queue - m->pc) == PQ_CACHE) {
1999                 KKASSERT((m->flags & PG_MAPPED) == 0);
2000                 vm_page_wakeup(m);
2001                 return;
2002         }
2003
2004         /*
2005          * Caller is required to test m->dirty, but note that the act of
2006          * removing the page from its maps can cause it to become dirty
2007          * on an SMP system due to another cpu running in usermode.
2008          */
2009         if (m->dirty) {
2010                 panic("vm_page_cache: caching a dirty page, pindex: %ld",
2011                         (long)m->pindex);
2012         }
2013
2014         /*
2015          * Remove all pmaps and indicate that the page is not
2016          * writeable or mapped.  Our vm_page_protect() call may
2017          * have blocked (especially w/ VM_PROT_NONE), so recheck
2018          * everything.
2019          */
2020         vm_page_protect(m, VM_PROT_NONE);
2021         if ((m->flags & (PG_UNMANAGED|PG_MAPPED)) || m->busy ||
2022                         m->wire_count || m->hold_count) {
2023                 vm_page_wakeup(m);
2024         } else if (m->dirty) {
2025                 vm_page_deactivate(m);
2026                 vm_page_wakeup(m);
2027         } else {
2028                 _vm_page_and_queue_spin_lock(m);
2029                 _vm_page_rem_queue_spinlocked(m);
2030                 _vm_page_add_queue_spinlocked(m, PQ_CACHE + m->pc, 0);
2031                 _vm_page_queue_spin_unlock(m);
2032                 if (_vm_page_wakeup(m)) {
2033                         vm_page_spin_unlock(m);
2034                         wakeup(m);
2035                 } else {
2036                         vm_page_spin_unlock(m);
2037                 }
2038                 vm_page_free_wakeup();
2039         }
2040 }
2041
2042 /*
2043  * vm_page_dontneed()
2044  *
2045  * Cache, deactivate, or do nothing as appropriate.  This routine
2046  * is typically used by madvise() MADV_DONTNEED.
2047  *
2048  * Generally speaking we want to move the page into the cache so
2049  * it gets reused quickly.  However, this can result in a silly syndrome
2050  * due to the page recycling too quickly.  Small objects will not be
2051  * fully cached.  On the otherhand, if we move the page to the inactive
2052  * queue we wind up with a problem whereby very large objects 
2053  * unnecessarily blow away our inactive and cache queues.
2054  *
2055  * The solution is to move the pages based on a fixed weighting.  We
2056  * either leave them alone, deactivate them, or move them to the cache,
2057  * where moving them to the cache has the highest weighting.
2058  * By forcing some pages into other queues we eventually force the
2059  * system to balance the queues, potentially recovering other unrelated
2060  * space from active.  The idea is to not force this to happen too
2061  * often.
2062  *
2063  * The page must be busied.
2064  */
2065 void
2066 vm_page_dontneed(vm_page_t m)
2067 {
2068         static int dnweight;
2069         int dnw;
2070         int head;
2071
2072         dnw = ++dnweight;
2073
2074         /*
2075          * occassionally leave the page alone
2076          */
2077         if ((dnw & 0x01F0) == 0 ||
2078             m->queue == PQ_INACTIVE || 
2079             m->queue - m->pc == PQ_CACHE
2080         ) {
2081                 if (m->act_count >= ACT_INIT)
2082                         --m->act_count;
2083                 return;
2084         }
2085
2086         /*
2087          * If vm_page_dontneed() is inactivating a page, it must clear
2088          * the referenced flag; otherwise the pagedaemon will see references
2089          * on the page in the inactive queue and reactivate it. Until the 
2090          * page can move to the cache queue, madvise's job is not done.
2091          */
2092         vm_page_flag_clear(m, PG_REFERENCED);
2093         pmap_clear_reference(m);
2094
2095         if (m->dirty == 0)
2096                 vm_page_test_dirty(m);
2097
2098         if (m->dirty || (dnw & 0x0070) == 0) {
2099                 /*
2100                  * Deactivate the page 3 times out of 32.
2101                  */
2102                 head = 0;
2103         } else {
2104                 /*
2105                  * Cache the page 28 times out of every 32.  Note that
2106                  * the page is deactivated instead of cached, but placed
2107                  * at the head of the queue instead of the tail.
2108                  */
2109                 head = 1;
2110         }
2111         vm_page_spin_lock(m);
2112         _vm_page_deactivate_locked(m, head);
2113         vm_page_spin_unlock(m);
2114 }
2115
2116 /*
2117  * These routines manipulate the 'soft busy' count for a page.  A soft busy
2118  * is almost like PG_BUSY except that it allows certain compatible operations
2119  * to occur on the page while it is busy.  For example, a page undergoing a
2120  * write can still be mapped read-only.
2121  *
2122  * Because vm_pages can overlap buffers m->busy can be > 1.  m->busy is only
2123  * adjusted while the vm_page is PG_BUSY so the flash will occur when the
2124  * busy bit is cleared.
2125  */
2126 void
2127 vm_page_io_start(vm_page_t m)
2128 {
2129         KASSERT(m->flags & PG_BUSY, ("vm_page_io_start: page not busy!!!"));
2130         atomic_add_char(&m->busy, 1);
2131         vm_page_flag_set(m, PG_SBUSY);
2132 }
2133
2134 void
2135 vm_page_io_finish(vm_page_t m)
2136 {
2137         KASSERT(m->flags & PG_BUSY, ("vm_page_io_finish: page not busy!!!"));
2138         atomic_subtract_char(&m->busy, 1);
2139         if (m->busy == 0)
2140                 vm_page_flag_clear(m, PG_SBUSY);
2141 }
2142
2143 /*
2144  * Grab a page, blocking if it is busy and allocating a page if necessary.
2145  * A busy page is returned or NULL.
2146  *
2147  * The page is not removed from its queues. XXX?
2148  *
2149  * If VM_ALLOC_RETRY is specified VM_ALLOC_NORMAL must also be specified.
2150  * If VM_ALLOC_RETRY is not specified
2151  *
2152  * This routine may block, but if VM_ALLOC_RETRY is not set then NULL is
2153  * always returned if we had blocked.  
2154  * This routine will never return NULL if VM_ALLOC_RETRY is set.
2155  * This routine may not be called from an interrupt.
2156  * The returned page may not be entirely valid.
2157  *
2158  * This routine may be called from mainline code without spl protection and
2159  * be guarenteed a busied page associated with the object at the specified
2160  * index.
2161  *
2162  * No requirements.
2163  */
2164 vm_page_t
2165 vm_page_grab(vm_object_t object, vm_pindex_t pindex, int allocflags)
2166 {
2167         vm_page_t m;
2168         int error;
2169
2170         KKASSERT(allocflags &
2171                 (VM_ALLOC_NORMAL|VM_ALLOC_INTERRUPT|VM_ALLOC_SYSTEM));
2172         vm_object_hold(object);
2173         for (;;) {
2174                 m = vm_page_lookup_busy_try(object, pindex, TRUE, &error);
2175                 if (error) {
2176                         vm_page_sleep_busy(m, TRUE, "pgrbwt");
2177                         if ((allocflags & VM_ALLOC_RETRY) == 0) {
2178                                 m = NULL;
2179                                 break;
2180                         }
2181                 } else if (m == NULL) {
2182                         m = vm_page_alloc(object, pindex,
2183                                           allocflags & ~VM_ALLOC_RETRY);
2184                         if (m)
2185                                 break;
2186                         vm_wait(0);
2187                         if ((allocflags & VM_ALLOC_RETRY) == 0)
2188                                 break;
2189                 } else {
2190                         /* m found */
2191                         break;
2192                 }
2193         }
2194         vm_object_drop(object);
2195         return(m);
2196 }
2197
2198 /*
2199  * Mapping function for valid bits or for dirty bits in
2200  * a page.  May not block.
2201  *
2202  * Inputs are required to range within a page.
2203  *
2204  * No requirements.
2205  * Non blocking.
2206  */
2207 int
2208 vm_page_bits(int base, int size)
2209 {
2210         int first_bit;
2211         int last_bit;
2212
2213         KASSERT(
2214             base + size <= PAGE_SIZE,
2215             ("vm_page_bits: illegal base/size %d/%d", base, size)
2216         );
2217
2218         if (size == 0)          /* handle degenerate case */
2219                 return(0);
2220
2221         first_bit = base >> DEV_BSHIFT;
2222         last_bit = (base + size - 1) >> DEV_BSHIFT;
2223
2224         return ((2 << last_bit) - (1 << first_bit));
2225 }
2226
2227 /*
2228  * Sets portions of a page valid and clean.  The arguments are expected
2229  * to be DEV_BSIZE aligned but if they aren't the bitmap is inclusive
2230  * of any partial chunks touched by the range.  The invalid portion of
2231  * such chunks will be zero'd.
2232  *
2233  * NOTE: When truncating a buffer vnode_pager_setsize() will automatically
2234  *       align base to DEV_BSIZE so as not to mark clean a partially
2235  *       truncated device block.  Otherwise the dirty page status might be
2236  *       lost.
2237  *
2238  * This routine may not block.
2239  *
2240  * (base + size) must be less then or equal to PAGE_SIZE.
2241  */
2242 static void
2243 _vm_page_zero_valid(vm_page_t m, int base, int size)
2244 {
2245         int frag;
2246         int endoff;
2247
2248         if (size == 0)  /* handle degenerate case */
2249                 return;
2250
2251         /*
2252          * If the base is not DEV_BSIZE aligned and the valid
2253          * bit is clear, we have to zero out a portion of the
2254          * first block.
2255          */
2256
2257         if ((frag = base & ~(DEV_BSIZE - 1)) != base &&
2258             (m->valid & (1 << (base >> DEV_BSHIFT))) == 0
2259         ) {
2260                 pmap_zero_page_area(
2261                     VM_PAGE_TO_PHYS(m),
2262                     frag,
2263                     base - frag
2264                 );
2265         }
2266
2267         /*
2268          * If the ending offset is not DEV_BSIZE aligned and the 
2269          * valid bit is clear, we have to zero out a portion of
2270          * the last block.
2271          */
2272
2273         endoff = base + size;
2274
2275         if ((frag = endoff & ~(DEV_BSIZE - 1)) != endoff &&
2276             (m->valid & (1 << (endoff >> DEV_BSHIFT))) == 0
2277         ) {
2278                 pmap_zero_page_area(
2279                     VM_PAGE_TO_PHYS(m),
2280                     endoff,
2281                     DEV_BSIZE - (endoff & (DEV_BSIZE - 1))
2282                 );
2283         }
2284 }
2285
2286 /*
2287  * Set valid, clear dirty bits.  If validating the entire
2288  * page we can safely clear the pmap modify bit.  We also
2289  * use this opportunity to clear the PG_NOSYNC flag.  If a process
2290  * takes a write fault on a MAP_NOSYNC memory area the flag will
2291  * be set again.
2292  *
2293  * We set valid bits inclusive of any overlap, but we can only
2294  * clear dirty bits for DEV_BSIZE chunks that are fully within
2295  * the range.
2296  *
2297  * Page must be busied?
2298  * No other requirements.
2299  */
2300 void
2301 vm_page_set_valid(vm_page_t m, int base, int size)
2302 {
2303         _vm_page_zero_valid(m, base, size);
2304         m->valid |= vm_page_bits(base, size);
2305 }
2306
2307
2308 /*
2309  * Set valid bits and clear dirty bits.
2310  *
2311  * NOTE: This function does not clear the pmap modified bit.
2312  *       Also note that e.g. NFS may use a byte-granular base
2313  *       and size.
2314  *
2315  * WARNING: Page must be busied?  But vfs_clean_one_page() will call
2316  *          this without necessarily busying the page (via bdwrite()).
2317  *          So for now vm_token must also be held.
2318  *
2319  * No other requirements.
2320  */
2321 void
2322 vm_page_set_validclean(vm_page_t m, int base, int size)
2323 {
2324         int pagebits;
2325
2326         _vm_page_zero_valid(m, base, size);
2327         pagebits = vm_page_bits(base, size);
2328         m->valid |= pagebits;
2329         m->dirty &= ~pagebits;
2330         if (base == 0 && size == PAGE_SIZE) {
2331                 /*pmap_clear_modify(m);*/
2332                 vm_page_flag_clear(m, PG_NOSYNC);
2333         }
2334 }
2335
2336 /*
2337  * Set valid & dirty.  Used by buwrite()
2338  *
2339  * WARNING: Page must be busied?  But vfs_dirty_one_page() will
2340  *          call this function in buwrite() so for now vm_token must
2341  *          be held.
2342  *
2343  * No other requirements.
2344  */
2345 void
2346 vm_page_set_validdirty(vm_page_t m, int base, int size)
2347 {
2348         int pagebits;
2349
2350         pagebits = vm_page_bits(base, size);
2351         m->valid |= pagebits;
2352         m->dirty |= pagebits;
2353         if (m->object)
2354                 vm_object_set_writeable_dirty(m->object);
2355 }
2356
2357 /*
2358  * Clear dirty bits.
2359  *
2360  * NOTE: This function does not clear the pmap modified bit.
2361  *       Also note that e.g. NFS may use a byte-granular base
2362  *       and size.
2363  *
2364  * Page must be busied?
2365  * No other requirements.
2366  */
2367 void
2368 vm_page_clear_dirty(vm_page_t m, int base, int size)
2369 {
2370         m->dirty &= ~vm_page_bits(base, size);
2371         if (base == 0 && size == PAGE_SIZE) {
2372                 /*pmap_clear_modify(m);*/
2373                 vm_page_flag_clear(m, PG_NOSYNC);
2374         }
2375 }
2376
2377 /*
2378  * Make the page all-dirty.
2379  *
2380  * Also make sure the related object and vnode reflect the fact that the
2381  * object may now contain a dirty page.
2382  *
2383  * Page must be busied?
2384  * No other requirements.
2385  */
2386 void
2387 vm_page_dirty(vm_page_t m)
2388 {
2389 #ifdef INVARIANTS
2390         int pqtype = m->queue - m->pc;
2391 #endif
2392         KASSERT(pqtype != PQ_CACHE && pqtype != PQ_FREE,
2393                 ("vm_page_dirty: page in free/cache queue!"));
2394         if (m->dirty != VM_PAGE_BITS_ALL) {
2395                 m->dirty = VM_PAGE_BITS_ALL;
2396                 if (m->object)
2397                         vm_object_set_writeable_dirty(m->object);
2398         }
2399 }
2400
2401 /*
2402  * Invalidates DEV_BSIZE'd chunks within a page.  Both the
2403  * valid and dirty bits for the effected areas are cleared.
2404  *
2405  * Page must be busied?
2406  * Does not block.
2407  * No other requirements.
2408  */
2409 void
2410 vm_page_set_invalid(vm_page_t m, int base, int size)
2411 {
2412         int bits;
2413
2414         bits = vm_page_bits(base, size);
2415         m->valid &= ~bits;
2416         m->dirty &= ~bits;
2417         m->object->generation++;
2418 }
2419
2420 /*
2421  * The kernel assumes that the invalid portions of a page contain 
2422  * garbage, but such pages can be mapped into memory by user code.
2423  * When this occurs, we must zero out the non-valid portions of the
2424  * page so user code sees what it expects.
2425  *
2426  * Pages are most often semi-valid when the end of a file is mapped 
2427  * into memory and the file's size is not page aligned.
2428  *
2429  * Page must be busied?
2430  * No other requirements.
2431  */
2432 void
2433 vm_page_zero_invalid(vm_page_t m, boolean_t setvalid)
2434 {
2435         int b;
2436         int i;
2437
2438         /*
2439          * Scan the valid bits looking for invalid sections that
2440          * must be zerod.  Invalid sub-DEV_BSIZE'd areas ( where the
2441          * valid bit may be set ) have already been zerod by
2442          * vm_page_set_validclean().
2443          */
2444         for (b = i = 0; i <= PAGE_SIZE / DEV_BSIZE; ++i) {
2445                 if (i == (PAGE_SIZE / DEV_BSIZE) || 
2446                     (m->valid & (1 << i))
2447                 ) {
2448                         if (i > b) {
2449                                 pmap_zero_page_area(
2450                                     VM_PAGE_TO_PHYS(m), 
2451                                     b << DEV_BSHIFT,
2452                                     (i - b) << DEV_BSHIFT
2453                                 );
2454                         }
2455                         b = i + 1;
2456                 }
2457         }
2458
2459         /*
2460          * setvalid is TRUE when we can safely set the zero'd areas
2461          * as being valid.  We can do this if there are no cache consistency
2462          * issues.  e.g. it is ok to do with UFS, but not ok to do with NFS.
2463          */
2464         if (setvalid)
2465                 m->valid = VM_PAGE_BITS_ALL;
2466 }
2467
2468 /*
2469  * Is a (partial) page valid?  Note that the case where size == 0
2470  * will return FALSE in the degenerate case where the page is entirely
2471  * invalid, and TRUE otherwise.
2472  *
2473  * Does not block.
2474  * No other requirements.
2475  */
2476 int
2477 vm_page_is_valid(vm_page_t m, int base, int size)
2478 {
2479         int bits = vm_page_bits(base, size);
2480
2481         if (m->valid && ((m->valid & bits) == bits))
2482                 return 1;
2483         else
2484                 return 0;
2485 }
2486
2487 /*
2488  * update dirty bits from pmap/mmu.  May not block.
2489  *
2490  * Caller must hold the page busy
2491  */
2492 void
2493 vm_page_test_dirty(vm_page_t m)
2494 {
2495         if ((m->dirty != VM_PAGE_BITS_ALL) && pmap_is_modified(m)) {
2496                 vm_page_dirty(m);
2497         }
2498 }
2499
2500 /*
2501  * Register an action, associating it with its vm_page
2502  */
2503 void
2504 vm_page_register_action(vm_page_action_t action, vm_page_event_t event)
2505 {
2506         struct vm_page_action_list *list;
2507         int hv;
2508
2509         hv = (int)((intptr_t)action->m >> 8) & VMACTION_HMASK;
2510         list = &action_list[hv];
2511
2512         lwkt_gettoken(&vm_token);
2513         vm_page_flag_set(action->m, PG_ACTIONLIST);
2514         action->event = event;
2515         LIST_INSERT_HEAD(list, action, entry);
2516         lwkt_reltoken(&vm_token);
2517 }
2518
2519 /*
2520  * Unregister an action, disassociating it from its related vm_page
2521  */
2522 void
2523 vm_page_unregister_action(vm_page_action_t action)
2524 {
2525         struct vm_page_action_list *list;
2526         int hv;
2527
2528         lwkt_gettoken(&vm_token);
2529         if (action->event != VMEVENT_NONE) {
2530                 action->event = VMEVENT_NONE;
2531                 LIST_REMOVE(action, entry);
2532
2533                 hv = (int)((intptr_t)action->m >> 8) & VMACTION_HMASK;
2534                 list = &action_list[hv];
2535                 if (LIST_EMPTY(list))
2536                         vm_page_flag_clear(action->m, PG_ACTIONLIST);
2537         }
2538         lwkt_reltoken(&vm_token);
2539 }
2540
2541 /*
2542  * Issue an event on a VM page.  Corresponding action structures are
2543  * removed from the page's list and called.
2544  *
2545  * If the vm_page has no more pending action events we clear its
2546  * PG_ACTIONLIST flag.
2547  */
2548 void
2549 vm_page_event_internal(vm_page_t m, vm_page_event_t event)
2550 {
2551         struct vm_page_action_list *list;
2552         struct vm_page_action *scan;
2553         struct vm_page_action *next;
2554         int hv;
2555         int all;
2556
2557         hv = (int)((intptr_t)m >> 8) & VMACTION_HMASK;
2558         list = &action_list[hv];
2559         all = 1;
2560
2561         lwkt_gettoken(&vm_token);
2562         LIST_FOREACH_MUTABLE(scan, list, entry, next) {
2563                 if (scan->m == m) {
2564                         if (scan->event == event) {
2565                                 scan->event = VMEVENT_NONE;
2566                                 LIST_REMOVE(scan, entry);
2567                                 scan->func(m, scan);
2568                                 /* XXX */
2569                         } else {
2570                                 all = 0;
2571                         }
2572                 }
2573         }
2574         if (all)
2575                 vm_page_flag_clear(m, PG_ACTIONLIST);
2576         lwkt_reltoken(&vm_token);
2577 }
2578
2579 #include "opt_ddb.h"
2580 #ifdef DDB
2581 #include <sys/kernel.h>
2582
2583 #include <ddb/ddb.h>
2584
2585 DB_SHOW_COMMAND(page, vm_page_print_page_info)
2586 {
2587         db_printf("vmstats.v_free_count: %d\n", vmstats.v_free_count);
2588         db_printf("vmstats.v_cache_count: %d\n", vmstats.v_cache_count);
2589         db_printf("vmstats.v_inactive_count: %d\n", vmstats.v_inactive_count);
2590         db_printf("vmstats.v_active_count: %d\n", vmstats.v_active_count);
2591         db_printf("vmstats.v_wire_count: %d\n", vmstats.v_wire_count);
2592         db_printf("vmstats.v_free_reserved: %d\n", vmstats.v_free_reserved);
2593         db_printf("vmstats.v_free_min: %d\n", vmstats.v_free_min);
2594         db_printf("vmstats.v_free_target: %d\n", vmstats.v_free_target);
2595         db_printf("vmstats.v_cache_min: %d\n", vmstats.v_cache_min);
2596         db_printf("vmstats.v_inactive_target: %d\n", vmstats.v_inactive_target);
2597 }
2598
2599 DB_SHOW_COMMAND(pageq, vm_page_print_pageq_info)
2600 {
2601         int i;
2602         db_printf("PQ_FREE:");
2603         for(i=0;i<PQ_L2_SIZE;i++) {
2604                 db_printf(" %d", vm_page_queues[PQ_FREE + i].lcnt);
2605         }
2606         db_printf("\n");
2607                 
2608         db_printf("PQ_CACHE:");
2609         for(i=0;i<PQ_L2_SIZE;i++) {
2610                 db_printf(" %d", vm_page_queues[PQ_CACHE + i].lcnt);
2611         }
2612         db_printf("\n");
2613
2614         db_printf("PQ_ACTIVE: %d, PQ_INACTIVE: %d\n",
2615                 vm_page_queues[PQ_ACTIVE].lcnt,
2616                 vm_page_queues[PQ_INACTIVE].lcnt);
2617 }
2618 #endif /* DDB */