583619dd1411b7c598c5fb69aee613eca1514651
[dragonfly.git] / sys / vm / vm_page.c
1 /*
2  * Copyright (c) 2003-2019 The DragonFly Project.  All rights reserved.
3  * Copyright (c) 1991 Regents of the University of California.
4  * All rights reserved.
5  *
6  * This code is derived from software contributed to Berkeley by
7  * The Mach Operating System project at Carnegie-Mellon University.
8  *
9  * This code is derived from software contributed to The DragonFly Project
10  * by Matthew Dillon <dillon@backplane.com>
11  *
12  * Redistribution and use in source and binary forms, with or without
13  * modification, are permitted provided that the following conditions
14  * are met:
15  * 1. Redistributions of source code must retain the above copyright
16  *    notice, this list of conditions and the following disclaimer.
17  * 2. Redistributions in binary form must reproduce the above copyright
18  *    notice, this list of conditions and the following disclaimer in the
19  *    documentation and/or other materials provided with the distribution.
20  * 3. Neither the name of the University nor the names of its contributors
21  *    may be used to endorse or promote products derived from this software
22  *    without specific prior written permission.
23  *
24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34  * SUCH DAMAGE.
35  *
36  *      from: @(#)vm_page.c     7.4 (Berkeley) 5/7/91
37  * $FreeBSD: src/sys/vm/vm_page.c,v 1.147.2.18 2002/03/10 05:03:19 alc Exp $
38  */
39
40 /*
41  * Copyright (c) 1987, 1990 Carnegie-Mellon University.
42  * All rights reserved.
43  *
44  * Authors: Avadis Tevanian, Jr., Michael Wayne Young
45  *
46  * Permission to use, copy, modify and distribute this software and
47  * its documentation is hereby granted, provided that both the copyright
48  * notice and this permission notice appear in all copies of the
49  * software, derivative works or modified versions, and any portions
50  * thereof, and that both notices appear in supporting documentation.
51  *
52  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
53  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
54  * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
55  *
56  * Carnegie Mellon requests users of this software to return to
57  *
58  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
59  *  School of Computer Science
60  *  Carnegie Mellon University
61  *  Pittsburgh PA 15213-3890
62  *
63  * any improvements or extensions that they make and grant Carnegie the
64  * rights to redistribute these changes.
65  */
66 /*
67  * Resident memory management module.  The module manipulates 'VM pages'.
68  * A VM page is the core building block for memory management.
69  */
70
71 #include <sys/param.h>
72 #include <sys/systm.h>
73 #include <sys/malloc.h>
74 #include <sys/proc.h>
75 #include <sys/vmmeter.h>
76 #include <sys/vnode.h>
77 #include <sys/kernel.h>
78 #include <sys/alist.h>
79 #include <sys/sysctl.h>
80 #include <sys/cpu_topology.h>
81
82 #include <vm/vm.h>
83 #include <vm/vm_param.h>
84 #include <sys/lock.h>
85 #include <vm/vm_kern.h>
86 #include <vm/pmap.h>
87 #include <vm/vm_map.h>
88 #include <vm/vm_object.h>
89 #include <vm/vm_page.h>
90 #include <vm/vm_pageout.h>
91 #include <vm/vm_pager.h>
92 #include <vm/vm_extern.h>
93 #include <vm/swap_pager.h>
94
95 #include <machine/inttypes.h>
96 #include <machine/md_var.h>
97 #include <machine/specialreg.h>
98 #include <machine/bus_dma.h>
99
100 #include <vm/vm_page2.h>
101 #include <sys/spinlock2.h>
102
103 struct vm_page_hash_elm {
104         vm_page_t       m;
105         int             ticks;
106         int             unused01;
107 };
108
109 /*
110  * SET - Minimum required set associative size, must be a power of 2.  We
111  *       want this to match or exceed the set-associativeness of the cpu,
112  *       up to a reasonable limit (we will use 16).
113  */
114 __read_mostly static int set_assoc_mask = 16 - 1;
115
116 static void vm_page_queue_init(void);
117 static void vm_page_free_wakeup(void);
118 static vm_page_t vm_page_select_cache(u_short pg_color);
119 static vm_page_t _vm_page_list_find2(int basequeue, int index, int *lastp);
120 static void _vm_page_deactivate_locked(vm_page_t m, int athead);
121 static void vm_numa_add_topology_mem(cpu_node_t *cpup, int physid, long bytes);
122
123 /*
124  * Array of tailq lists
125  */
126 struct vpgqueues vm_page_queues[PQ_COUNT];
127
128 static volatile int vm_pages_waiting;
129 static struct alist vm_contig_alist;
130 static struct almeta vm_contig_ameta[ALIST_RECORDS_65536];
131 static struct spinlock vm_contig_spin = SPINLOCK_INITIALIZER(&vm_contig_spin, "vm_contig_spin");
132
133 static struct vm_page_hash_elm *vm_page_hash;
134 __read_mostly static int vm_page_hash_size;
135
136 static u_long vm_dma_reserved = 0;
137 TUNABLE_ULONG("vm.dma_reserved", &vm_dma_reserved);
138 SYSCTL_ULONG(_vm, OID_AUTO, dma_reserved, CTLFLAG_RD, &vm_dma_reserved, 0,
139             "Memory reserved for DMA");
140 SYSCTL_UINT(_vm, OID_AUTO, dma_free_pages, CTLFLAG_RD,
141             &vm_contig_alist.bl_free, 0, "Memory reserved for DMA");
142
143 static int vm_contig_verbose = 0;
144 TUNABLE_INT("vm.contig_verbose", &vm_contig_verbose);
145
146 RB_GENERATE2(vm_page_rb_tree, vm_page, rb_entry, rb_vm_page_compare,
147              vm_pindex_t, pindex);
148
149 static void
150 vm_page_queue_init(void) 
151 {
152         int i;
153
154         for (i = 0; i < PQ_L2_SIZE; i++)
155                 vm_page_queues[PQ_FREE+i].cnt_offset =
156                         offsetof(struct vmstats, v_free_count);
157         for (i = 0; i < PQ_L2_SIZE; i++)
158                 vm_page_queues[PQ_CACHE+i].cnt_offset =
159                         offsetof(struct vmstats, v_cache_count);
160         for (i = 0; i < PQ_L2_SIZE; i++)
161                 vm_page_queues[PQ_INACTIVE+i].cnt_offset =
162                         offsetof(struct vmstats, v_inactive_count);
163         for (i = 0; i < PQ_L2_SIZE; i++)
164                 vm_page_queues[PQ_ACTIVE+i].cnt_offset =
165                         offsetof(struct vmstats, v_active_count);
166         for (i = 0; i < PQ_L2_SIZE; i++)
167                 vm_page_queues[PQ_HOLD+i].cnt_offset =
168                         offsetof(struct vmstats, v_active_count);
169         /* PQ_NONE has no queue */
170
171         for (i = 0; i < PQ_COUNT; i++) {
172                 vm_page_queues[i].lastq = -1;
173                 TAILQ_INIT(&vm_page_queues[i].pl);
174                 spin_init(&vm_page_queues[i].spin, "vm_page_queue_init");
175         }
176 }
177
178 /*
179  * note: place in initialized data section?  Is this necessary?
180  */
181 vm_pindex_t first_page = 0;
182 vm_pindex_t vm_page_array_size = 0;
183 vm_page_t vm_page_array = NULL;
184 vm_paddr_t vm_low_phys_reserved;
185
186 /*
187  * (low level boot)
188  *
189  * Sets the page size, perhaps based upon the memory size.
190  * Must be called before any use of page-size dependent functions.
191  */
192 void
193 vm_set_page_size(void)
194 {
195         if (vmstats.v_page_size == 0)
196                 vmstats.v_page_size = PAGE_SIZE;
197         if (((vmstats.v_page_size - 1) & vmstats.v_page_size) != 0)
198                 panic("vm_set_page_size: page size not a power of two");
199 }
200
201 /*
202  * (low level boot)
203  *
204  * Add a new page to the freelist for use by the system.  New pages
205  * are added to both the head and tail of the associated free page
206  * queue in a bottom-up fashion, so both zero'd and non-zero'd page
207  * requests pull 'recent' adds (higher physical addresses) first.
208  *
209  * Beware that the page zeroing daemon will also be running soon after
210  * boot, moving pages from the head to the tail of the PQ_FREE queues.
211  *
212  * Must be called in a critical section.
213  */
214 static void
215 vm_add_new_page(vm_paddr_t pa)
216 {
217         struct vpgqueues *vpq;
218         vm_page_t m;
219
220         m = PHYS_TO_VM_PAGE(pa);
221         m->phys_addr = pa;
222         m->flags = 0;
223         m->pat_mode = PAT_WRITE_BACK;
224         m->pc = (pa >> PAGE_SHIFT);
225
226         /*
227          * Twist for cpu localization in addition to page coloring, so
228          * different cpus selecting by m->queue get different page colors.
229          */
230         m->pc ^= ((pa >> PAGE_SHIFT) / PQ_L2_SIZE);
231         m->pc ^= ((pa >> PAGE_SHIFT) / (PQ_L2_SIZE * PQ_L2_SIZE));
232         m->pc &= PQ_L2_MASK;
233
234         /*
235          * Reserve a certain number of contiguous low memory pages for
236          * contigmalloc() to use.
237          */
238         if (pa < vm_low_phys_reserved) {
239                 atomic_add_long(&vmstats.v_page_count, 1);
240                 atomic_add_long(&vmstats.v_dma_pages, 1);
241                 m->queue = PQ_NONE;
242                 m->wire_count = 1;
243                 atomic_add_long(&vmstats.v_wire_count, 1);
244                 alist_free(&vm_contig_alist, pa >> PAGE_SHIFT, 1);
245                 return;
246         }
247
248         /*
249          * General page
250          */
251         m->queue = m->pc + PQ_FREE;
252         KKASSERT(m->dirty == 0);
253
254         atomic_add_long(&vmstats.v_page_count, 1);
255         atomic_add_long(&vmstats.v_free_count, 1);
256         vpq = &vm_page_queues[m->queue];
257         TAILQ_INSERT_HEAD(&vpq->pl, m, pageq);
258         ++vpq->lcnt;
259 }
260
261 /*
262  * (low level boot)
263  *
264  * Initializes the resident memory module.
265  *
266  * Preallocates memory for critical VM structures and arrays prior to
267  * kernel_map becoming available.
268  *
269  * Memory is allocated from (virtual2_start, virtual2_end) if available,
270  * otherwise memory is allocated from (virtual_start, virtual_end).
271  *
272  * On x86-64 (virtual_start, virtual_end) is only 2GB and may not be
273  * large enough to hold vm_page_array & other structures for machines with
274  * large amounts of ram, so we want to use virtual2* when available.
275  */
276 void
277 vm_page_startup(void)
278 {
279         vm_offset_t vaddr = virtual2_start ? virtual2_start : virtual_start;
280         vm_offset_t mapped;
281         vm_pindex_t npages;
282         vm_paddr_t page_range;
283         vm_paddr_t new_end;
284         int i;
285         vm_paddr_t pa;
286         vm_paddr_t last_pa;
287         vm_paddr_t end;
288         vm_paddr_t biggestone, biggestsize;
289         vm_paddr_t total;
290         vm_page_t m;
291
292         total = 0;
293         biggestsize = 0;
294         biggestone = 0;
295         vaddr = round_page(vaddr);
296
297         /*
298          * Make sure ranges are page-aligned.
299          */
300         for (i = 0; phys_avail[i].phys_end; ++i) {
301                 phys_avail[i].phys_beg = round_page64(phys_avail[i].phys_beg);
302                 phys_avail[i].phys_end = trunc_page64(phys_avail[i].phys_end);
303                 if (phys_avail[i].phys_end < phys_avail[i].phys_beg)
304                         phys_avail[i].phys_end = phys_avail[i].phys_beg;
305         }
306
307         /*
308          * Locate largest block
309          */
310         for (i = 0; phys_avail[i].phys_end; ++i) {
311                 vm_paddr_t size = phys_avail[i].phys_end -
312                                   phys_avail[i].phys_beg;
313
314                 if (size > biggestsize) {
315                         biggestone = i;
316                         biggestsize = size;
317                 }
318                 total += size;
319         }
320         --i;    /* adjust to last entry for use down below */
321
322         end = phys_avail[biggestone].phys_end;
323         end = trunc_page(end);
324
325         /*
326          * Initialize the queue headers for the free queue, the active queue
327          * and the inactive queue.
328          */
329         vm_page_queue_init();
330
331 #if !defined(_KERNEL_VIRTUAL)
332         /*
333          * VKERNELs don't support minidumps and as such don't need
334          * vm_page_dump
335          *
336          * Allocate a bitmap to indicate that a random physical page
337          * needs to be included in a minidump.
338          *
339          * The amd64 port needs this to indicate which direct map pages
340          * need to be dumped, via calls to dump_add_page()/dump_drop_page().
341          *
342          * However, x86 still needs this workspace internally within the
343          * minidump code.  In theory, they are not needed on x86, but are
344          * included should the sf_buf code decide to use them.
345          */
346         page_range = phys_avail[i].phys_end / PAGE_SIZE;
347         vm_page_dump_size = round_page(roundup2(page_range, NBBY) / NBBY);
348         end -= vm_page_dump_size;
349         vm_page_dump = (void *)pmap_map(&vaddr, end, end + vm_page_dump_size,
350                                         VM_PROT_READ | VM_PROT_WRITE);
351         bzero((void *)vm_page_dump, vm_page_dump_size);
352 #endif
353         /*
354          * Compute the number of pages of memory that will be available for
355          * use (taking into account the overhead of a page structure per
356          * page).
357          */
358         first_page = phys_avail[0].phys_beg / PAGE_SIZE;
359         page_range = phys_avail[i].phys_end / PAGE_SIZE - first_page;
360         npages = (total - (page_range * sizeof(struct vm_page))) / PAGE_SIZE;
361
362 #ifndef _KERNEL_VIRTUAL
363         /*
364          * (only applies to real kernels)
365          *
366          * Reserve a large amount of low memory for potential 32-bit DMA
367          * space allocations.  Once device initialization is complete we
368          * release most of it, but keep (vm_dma_reserved) memory reserved
369          * for later use.  Typically for X / graphics.  Through trial and
370          * error we find that GPUs usually requires ~60-100MB or so.
371          *
372          * By default, 128M is left in reserve on machines with 2G+ of ram.
373          */
374         vm_low_phys_reserved = (vm_paddr_t)65536 << PAGE_SHIFT;
375         if (vm_low_phys_reserved > total / 4)
376                 vm_low_phys_reserved = total / 4;
377         if (vm_dma_reserved == 0) {
378                 vm_dma_reserved = 128 * 1024 * 1024;    /* 128MB */
379                 if (vm_dma_reserved > total / 16)
380                         vm_dma_reserved = total / 16;
381         }
382 #endif
383         alist_init(&vm_contig_alist, 65536, vm_contig_ameta,
384                    ALIST_RECORDS_65536);
385
386         /*
387          * Initialize the mem entry structures now, and put them in the free
388          * queue.
389          */
390         if (bootverbose && ctob(physmem) >= 400LL*1024*1024*1024)
391                 kprintf("initializing vm_page_array ");
392         new_end = trunc_page(end - page_range * sizeof(struct vm_page));
393         mapped = pmap_map(&vaddr, new_end, end, VM_PROT_READ | VM_PROT_WRITE);
394         vm_page_array = (vm_page_t)mapped;
395
396 #if defined(__x86_64__) && !defined(_KERNEL_VIRTUAL)
397         /*
398          * since pmap_map on amd64 returns stuff out of a direct-map region,
399          * we have to manually add these pages to the minidump tracking so
400          * that they can be dumped, including the vm_page_array.
401          */
402         for (pa = new_end;
403              pa < phys_avail[biggestone].phys_end;
404              pa += PAGE_SIZE) {
405                 dump_add_page(pa);
406         }
407 #endif
408
409         /*
410          * Clear all of the page structures, run basic initialization so
411          * PHYS_TO_VM_PAGE() operates properly even on pages not in the
412          * map.
413          */
414         bzero((caddr_t) vm_page_array, page_range * sizeof(struct vm_page));
415         vm_page_array_size = page_range;
416         if (bootverbose && ctob(physmem) >= 400LL*1024*1024*1024)
417                 kprintf("size = 0x%zx\n", vm_page_array_size);
418
419         m = &vm_page_array[0];
420         pa = ptoa(first_page);
421         for (i = 0; i < page_range; ++i) {
422                 spin_init(&m->spin, "vm_page");
423                 m->phys_addr = pa;
424                 pa += PAGE_SIZE;
425                 ++m;
426         }
427
428         /*
429          * Construct the free queue(s) in ascending order (by physical
430          * address) so that the first 16MB of physical memory is allocated
431          * last rather than first.  On large-memory machines, this avoids
432          * the exhaustion of low physical memory before isa_dma_init has run.
433          */
434         vmstats.v_page_count = 0;
435         vmstats.v_free_count = 0;
436         for (i = 0; phys_avail[i].phys_end && npages > 0; ++i) {
437                 pa = phys_avail[i].phys_beg;
438                 if (i == biggestone)
439                         last_pa = new_end;
440                 else
441                         last_pa = phys_avail[i].phys_end;
442                 while (pa < last_pa && npages-- > 0) {
443                         vm_add_new_page(pa);
444                         pa += PAGE_SIZE;
445                 }
446         }
447         if (virtual2_start)
448                 virtual2_start = vaddr;
449         else
450                 virtual_start = vaddr;
451         mycpu->gd_vmstats = vmstats;
452 }
453
454 /*
455  * (called from early boot only)
456  *
457  * Reorganize VM pages based on numa data.  May be called as many times as
458  * necessary.  Will reorganize the vm_page_t page color and related queue(s)
459  * to allow vm_page_alloc() to choose pages based on socket affinity.
460  *
461  * NOTE: This function is only called while we are still in UP mode, so
462  *       we only need a critical section to protect the queues (which
463  *       saves a lot of time, there are likely a ton of pages).
464  */
465 void
466 vm_numa_organize(vm_paddr_t ran_beg, vm_paddr_t bytes, int physid)
467 {
468         vm_paddr_t scan_beg;
469         vm_paddr_t scan_end;
470         vm_paddr_t ran_end;
471         struct vpgqueues *vpq;
472         vm_page_t m;
473         vm_page_t mend;
474         int socket_mod;
475         int socket_value;
476         int i;
477
478         /*
479          * Check if no physical information, or there was only one socket
480          * (so don't waste time doing nothing!).
481          */
482         if (cpu_topology_phys_ids <= 1 ||
483             cpu_topology_core_ids == 0) {
484                 return;
485         }
486
487         /*
488          * Setup for our iteration.  Note that ACPI may iterate CPU
489          * sockets starting at 0 or 1 or some other number.  The
490          * cpu_topology code mod's it against the socket count.
491          */
492         ran_end = ran_beg + bytes;
493
494         socket_mod = PQ_L2_SIZE / cpu_topology_phys_ids;
495         socket_value = (physid % cpu_topology_phys_ids) * socket_mod;
496         mend = &vm_page_array[vm_page_array_size];
497
498         crit_enter();
499
500         /*
501          * Adjust cpu_topology's phys_mem parameter
502          */
503         if (root_cpu_node)
504                 vm_numa_add_topology_mem(root_cpu_node, physid, (long)bytes);
505
506         /*
507          * Adjust vm_page->pc and requeue all affected pages.  The
508          * allocator will then be able to localize memory allocations
509          * to some degree.
510          */
511         for (i = 0; phys_avail[i].phys_end; ++i) {
512                 scan_beg = phys_avail[i].phys_beg;
513                 scan_end = phys_avail[i].phys_end;
514                 if (scan_end <= ran_beg)
515                         continue;
516                 if (scan_beg >= ran_end)
517                         continue;
518                 if (scan_beg < ran_beg)
519                         scan_beg = ran_beg;
520                 if (scan_end > ran_end)
521                         scan_end = ran_end;
522                 if (atop(scan_end) > first_page + vm_page_array_size)
523                         scan_end = ptoa(first_page + vm_page_array_size);
524
525                 m = PHYS_TO_VM_PAGE(scan_beg);
526                 while (scan_beg < scan_end) {
527                         KKASSERT(m < mend);
528                         if (m->queue != PQ_NONE) {
529                                 vpq = &vm_page_queues[m->queue];
530                                 TAILQ_REMOVE(&vpq->pl, m, pageq);
531                                 --vpq->lcnt;
532                                 /* queue doesn't change, no need to adj cnt */
533                                 m->queue -= m->pc;
534                                 m->pc %= socket_mod;
535                                 m->pc += socket_value;
536                                 m->pc &= PQ_L2_MASK;
537                                 m->queue += m->pc;
538                                 vpq = &vm_page_queues[m->queue];
539                                 TAILQ_INSERT_HEAD(&vpq->pl, m, pageq);
540                                 ++vpq->lcnt;
541                                 /* queue doesn't change, no need to adj cnt */
542                         } else {
543                                 m->pc %= socket_mod;
544                                 m->pc += socket_value;
545                                 m->pc &= PQ_L2_MASK;
546                         }
547                         scan_beg += PAGE_SIZE;
548                         ++m;
549                 }
550         }
551
552         crit_exit();
553 }
554
555 /*
556  * (called from early boot only)
557  *
558  * Don't allow the NUMA organization to leave vm_page_queues[] nodes
559  * completely empty for a logical cpu.  Doing so would force allocations
560  * on that cpu to always borrow from a nearby cpu, create unnecessary
561  * contention, and cause vm_page_alloc() to iterate more queues and run more
562  * slowly.
563  *
564  * This situation can occur when memory sticks are not entirely populated,
565  * populated at different densities, or in naturally assymetric systems
566  * such as the 2990WX.  There could very well be many vm_page_queues[]
567  * entries with *NO* pages assigned to them.
568  *
569  * Fixing this up ensures that each logical CPU has roughly the same
570  * sized memory pool, and more importantly ensures that logical CPUs
571  * do not wind up with an empty memory pool.
572  *
573  * At them moment we just iterate the other queues and borrow pages,
574  * moving them into the queues for cpus with severe deficits even though
575  * the memory might not be local to those cpus.  I am not doing this in
576  * a 'smart' way, its effectively UMA style (sorta, since its page-by-page
577  * whereas real UMA typically exchanges address bits 8-10 with high address
578  * bits).  But it works extremely well and gives us fairly good deterministic
579  * results on the cpu cores associated with these secondary nodes.
580  */
581 void
582 vm_numa_organize_finalize(void)
583 {
584         struct vpgqueues *vpq;
585         vm_page_t m;
586         long lcnt_lo;
587         long lcnt_hi;
588         int iter;
589         int i;
590         int scale_lim;
591
592         crit_enter();
593
594         /*
595          * Machines might not use an exact power of 2 for phys_ids,
596          * core_ids, ht_ids, etc.  This can slightly reduce the actual
597          * range of indices in vm_page_queues[] that are nominally used.
598          */
599         if (cpu_topology_ht_ids) {
600                 scale_lim = PQ_L2_SIZE / cpu_topology_phys_ids;
601                 scale_lim = scale_lim / cpu_topology_core_ids;
602                 scale_lim = scale_lim / cpu_topology_ht_ids;
603                 scale_lim = scale_lim * cpu_topology_ht_ids;
604                 scale_lim = scale_lim * cpu_topology_core_ids;
605                 scale_lim = scale_lim * cpu_topology_phys_ids;
606         } else {
607                 scale_lim = PQ_L2_SIZE;
608         }
609
610         /*
611          * Calculate an average, set hysteresis for balancing from
612          * 10% below the average to the average.
613          */
614         lcnt_hi = 0;
615         for (i = 0; i < scale_lim; ++i) {
616                 lcnt_hi += vm_page_queues[i].lcnt;
617         }
618         lcnt_hi /= scale_lim;
619         lcnt_lo = lcnt_hi - lcnt_hi / 10;
620
621         kprintf("vm_page: avg %ld pages per queue, %d queues\n",
622                 lcnt_hi, scale_lim);
623
624         iter = 0;
625         for (i = 0; i < scale_lim; ++i) {
626                 vpq = &vm_page_queues[PQ_FREE + i];
627                 while (vpq->lcnt < lcnt_lo) {
628                         struct vpgqueues *vptmp;
629
630                         iter = (iter + 1) & PQ_L2_MASK;
631                         vptmp = &vm_page_queues[PQ_FREE + iter];
632                         if (vptmp->lcnt < lcnt_hi)
633                                 continue;
634                         m = TAILQ_FIRST(&vptmp->pl);
635                         KKASSERT(m->queue == PQ_FREE + iter);
636                         TAILQ_REMOVE(&vptmp->pl, m, pageq);
637                         --vptmp->lcnt;
638                         /* queue doesn't change, no need to adj cnt */
639                         m->queue -= m->pc;
640                         m->pc = i;
641                         m->queue += m->pc;
642                         TAILQ_INSERT_HEAD(&vpq->pl, m, pageq);
643                         ++vpq->lcnt;
644                 }
645         }
646         crit_exit();
647 }
648
649 static
650 void
651 vm_numa_add_topology_mem(cpu_node_t *cpup, int physid, long bytes)
652 {
653         int cpuid;
654         int i;
655
656         switch(cpup->type) {
657         case PACKAGE_LEVEL:
658                 cpup->phys_mem += bytes;
659                 break;
660         case CHIP_LEVEL:
661                 /*
662                  * All members should have the same chipid, so we only need
663                  * to pull out one member.
664                  */
665                 if (CPUMASK_TESTNZERO(cpup->members)) {
666                         cpuid = BSFCPUMASK(cpup->members);
667                         if (physid ==
668                             get_chip_ID_from_APICID(CPUID_TO_APICID(cpuid))) {
669                                 cpup->phys_mem += bytes;
670                         }
671                 }
672                 break;
673         case CORE_LEVEL:
674         case THREAD_LEVEL:
675                 /*
676                  * Just inherit from the parent node
677                  */
678                 cpup->phys_mem = cpup->parent_node->phys_mem;
679                 break;
680         }
681         for (i = 0; i < MAXCPU && cpup->child_node[i]; ++i)
682                 vm_numa_add_topology_mem(cpup->child_node[i], physid, bytes);
683 }
684
685 /*
686  * We tended to reserve a ton of memory for contigmalloc().  Now that most
687  * drivers have initialized we want to return most the remaining free
688  * reserve back to the VM page queues so they can be used for normal
689  * allocations.
690  *
691  * We leave vm_dma_reserved bytes worth of free pages in the reserve pool.
692  */
693 static void
694 vm_page_startup_finish(void *dummy __unused)
695 {
696         alist_blk_t blk;
697         alist_blk_t rblk;
698         alist_blk_t count;
699         alist_blk_t xcount;
700         alist_blk_t bfree;
701         vm_page_t m;
702         struct vm_page_hash_elm *mp;
703         int mask;
704
705         /*
706          * Set the set_assoc_mask based on the fitted number of CPUs.
707          * This is a mask, so we subject 1.
708          *
709          * w/PQ_L2_SIZE = 1024:
710          *
711          *      Don't let the associativity drop below 8.  So if we have
712          *      256 CPUs, two hyper-threads will wind up sharing.  The
713          *      maximum is PQ_L2_SIZE.
714          */
715         mask = PQ_L2_SIZE / ncpus_fit - 1;
716         if (mask < 7)           /* minimum is 8-way w/256 CPU threads */
717                 mask = 7;
718         cpu_ccfence();
719         set_assoc_mask = mask;
720
721         /*
722          * Return part of the initial reserve back to the system
723          */
724         spin_lock(&vm_contig_spin);
725         for (;;) {
726                 bfree = alist_free_info(&vm_contig_alist, &blk, &count);
727                 if (bfree <= vm_dma_reserved / PAGE_SIZE)
728                         break;
729                 if (count == 0)
730                         break;
731
732                 /*
733                  * Figure out how much of the initial reserve we have to
734                  * free in order to reach our target.
735                  */
736                 bfree -= vm_dma_reserved / PAGE_SIZE;
737                 if (count > bfree) {
738                         blk += count - bfree;
739                         count = bfree;
740                 }
741
742                 /*
743                  * Calculate the nearest power of 2 <= count.
744                  */
745                 for (xcount = 1; xcount <= count; xcount <<= 1)
746                         ;
747                 xcount >>= 1;
748                 blk += count - xcount;
749                 count = xcount;
750
751                 /*
752                  * Allocate the pages from the alist, then free them to
753                  * the normal VM page queues.
754                  *
755                  * Pages allocated from the alist are wired.  We have to
756                  * busy, unwire, and free them.  We must also adjust
757                  * vm_low_phys_reserved before freeing any pages to prevent
758                  * confusion.
759                  */
760                 rblk = alist_alloc(&vm_contig_alist, blk, count);
761                 if (rblk != blk) {
762                         kprintf("vm_page_startup_finish: Unable to return "
763                                 "dma space @0x%08x/%d -> 0x%08x\n",
764                                 blk, count, rblk);
765                         break;
766                 }
767                 atomic_add_long(&vmstats.v_dma_pages, -(long)count);
768                 spin_unlock(&vm_contig_spin);
769
770                 m = PHYS_TO_VM_PAGE((vm_paddr_t)blk << PAGE_SHIFT);
771                 vm_low_phys_reserved = VM_PAGE_TO_PHYS(m);
772                 while (count) {
773                         vm_page_busy_wait(m, FALSE, "cpgfr");
774                         vm_page_unwire(m, 0);
775                         vm_page_free(m);
776                         --count;
777                         ++m;
778                 }
779                 spin_lock(&vm_contig_spin);
780         }
781         spin_unlock(&vm_contig_spin);
782
783         /*
784          * Print out how much DMA space drivers have already allocated and
785          * how much is left over.
786          */
787         kprintf("DMA space used: %jdk, remaining available: %jdk\n",
788                 (intmax_t)(vmstats.v_dma_pages - vm_contig_alist.bl_free) *
789                 (PAGE_SIZE / 1024),
790                 (intmax_t)vm_contig_alist.bl_free * (PAGE_SIZE / 1024));
791
792         /*
793          * Power of 2
794          */
795         vm_page_hash_size = 4096;
796         while (vm_page_hash_size < (vm_page_array_size / 16))
797                 vm_page_hash_size <<= 1;
798         if (vm_page_hash_size > 1024*1024)
799                 vm_page_hash_size = 1024*1024;
800
801         /*
802          * hash table for vm_page_lookup_quick()
803          */
804         mp = (void *)kmem_alloc3(&kernel_map,
805                                  vm_page_hash_size * sizeof(*vm_page_hash),
806                                  VM_SUBSYS_VMPGHASH, KM_CPU(0));
807         bzero(mp, vm_page_hash_size * sizeof(*mp));
808         cpu_sfence();
809         vm_page_hash = mp;
810 }
811 SYSINIT(vm_pgend, SI_SUB_PROC0_POST, SI_ORDER_ANY,
812         vm_page_startup_finish, NULL);
813
814
815 /*
816  * Scan comparison function for Red-Black tree scans.  An inclusive
817  * (start,end) is expected.  Other fields are not used.
818  */
819 int
820 rb_vm_page_scancmp(struct vm_page *p, void *data)
821 {
822         struct rb_vm_page_scan_info *info = data;
823
824         if (p->pindex < info->start_pindex)
825                 return(-1);
826         if (p->pindex > info->end_pindex)
827                 return(1);
828         return(0);
829 }
830
831 int
832 rb_vm_page_compare(struct vm_page *p1, struct vm_page *p2)
833 {
834         if (p1->pindex < p2->pindex)
835                 return(-1);
836         if (p1->pindex > p2->pindex)
837                 return(1);
838         return(0);
839 }
840
841 void
842 vm_page_init(vm_page_t m)
843 {
844         /* do nothing for now.  Called from pmap_page_init() */
845 }
846
847 /*
848  * Each page queue has its own spin lock, which is fairly optimal for
849  * allocating and freeing pages at least.
850  *
851  * The caller must hold the vm_page_spin_lock() before locking a vm_page's
852  * queue spinlock via this function.  Also note that m->queue cannot change
853  * unless both the page and queue are locked.
854  */
855 static __inline
856 void
857 _vm_page_queue_spin_lock(vm_page_t m)
858 {
859         u_short queue;
860
861         queue = m->queue;
862         if (queue != PQ_NONE) {
863                 spin_lock(&vm_page_queues[queue].spin);
864                 KKASSERT(queue == m->queue);
865         }
866 }
867
868 static __inline
869 void
870 _vm_page_queue_spin_unlock(vm_page_t m)
871 {
872         u_short queue;
873
874         queue = m->queue;
875         cpu_ccfence();
876         if (queue != PQ_NONE)
877                 spin_unlock(&vm_page_queues[queue].spin);
878 }
879
880 static __inline
881 void
882 _vm_page_queues_spin_lock(u_short queue)
883 {
884         cpu_ccfence();
885         if (queue != PQ_NONE)
886                 spin_lock(&vm_page_queues[queue].spin);
887 }
888
889
890 static __inline
891 void
892 _vm_page_queues_spin_unlock(u_short queue)
893 {
894         cpu_ccfence();
895         if (queue != PQ_NONE)
896                 spin_unlock(&vm_page_queues[queue].spin);
897 }
898
899 void
900 vm_page_queue_spin_lock(vm_page_t m)
901 {
902         _vm_page_queue_spin_lock(m);
903 }
904
905 void
906 vm_page_queues_spin_lock(u_short queue)
907 {
908         _vm_page_queues_spin_lock(queue);
909 }
910
911 void
912 vm_page_queue_spin_unlock(vm_page_t m)
913 {
914         _vm_page_queue_spin_unlock(m);
915 }
916
917 void
918 vm_page_queues_spin_unlock(u_short queue)
919 {
920         _vm_page_queues_spin_unlock(queue);
921 }
922
923 /*
924  * This locks the specified vm_page and its queue in the proper order
925  * (page first, then queue).  The queue may change so the caller must
926  * recheck on return.
927  */
928 static __inline
929 void
930 _vm_page_and_queue_spin_lock(vm_page_t m)
931 {
932         vm_page_spin_lock(m);
933         _vm_page_queue_spin_lock(m);
934 }
935
936 static __inline
937 void
938 _vm_page_and_queue_spin_unlock(vm_page_t m)
939 {
940         _vm_page_queues_spin_unlock(m->queue);
941         vm_page_spin_unlock(m);
942 }
943
944 void
945 vm_page_and_queue_spin_unlock(vm_page_t m)
946 {
947         _vm_page_and_queue_spin_unlock(m);
948 }
949
950 void
951 vm_page_and_queue_spin_lock(vm_page_t m)
952 {
953         _vm_page_and_queue_spin_lock(m);
954 }
955
956 /*
957  * Helper function removes vm_page from its current queue.
958  * Returns the base queue the page used to be on.
959  *
960  * The vm_page and the queue must be spinlocked.
961  * This function will unlock the queue but leave the page spinlocked.
962  */
963 static __inline u_short
964 _vm_page_rem_queue_spinlocked(vm_page_t m)
965 {
966         struct vpgqueues *pq;
967         u_short queue;
968         u_short oqueue;
969         long *cnt;
970
971         queue = m->queue;
972         if (queue != PQ_NONE) {
973                 pq = &vm_page_queues[queue];
974                 TAILQ_REMOVE(&pq->pl, m, pageq);
975
976                 /*
977                  * Adjust our pcpu stats.  In order for the nominal low-memory
978                  * algorithms to work properly we don't let any pcpu stat get
979                  * too negative before we force it to be rolled-up into the
980                  * global stats.  Otherwise our pageout and vm_wait tests
981                  * will fail badly.
982                  *
983                  * The idea here is to reduce unnecessary SMP cache
984                  * mastership changes in the global vmstats, which can be
985                  * particularly bad in multi-socket systems.
986                  */
987                 cnt = (long *)((char *)&mycpu->gd_vmstats_adj + pq->cnt_offset);
988                 atomic_add_long(cnt, -1);
989                 if (*cnt < -VMMETER_SLOP_COUNT) {
990                         u_long copy = atomic_swap_long(cnt, 0);
991                         cnt = (long *)((char *)&vmstats + pq->cnt_offset);
992                         atomic_add_long(cnt, copy);
993                         cnt = (long *)((char *)&mycpu->gd_vmstats +
994                                       pq->cnt_offset);
995                         atomic_add_long(cnt, copy);
996                 }
997                 pq->lcnt--;
998                 m->queue = PQ_NONE;
999                 oqueue = queue;
1000                 queue -= m->pc;
1001                 vm_page_queues_spin_unlock(oqueue);     /* intended */
1002         }
1003         return queue;
1004 }
1005
1006 /*
1007  * Helper function places the vm_page on the specified queue.  Generally
1008  * speaking only PQ_FREE pages are placed at the head, to allow them to
1009  * be allocated sooner rather than later on the assumption that they
1010  * are cache-hot.
1011  *
1012  * The vm_page must be spinlocked.
1013  * The vm_page must NOT be FICTITIOUS (that would be a disaster)
1014  * This function will return with both the page and the queue locked.
1015  */
1016 static __inline void
1017 _vm_page_add_queue_spinlocked(vm_page_t m, u_short queue, int athead)
1018 {
1019         struct vpgqueues *pq;
1020         u_long *cnt;
1021
1022         KKASSERT(m->queue == PQ_NONE && (m->flags & PG_FICTITIOUS) == 0);
1023
1024         if (queue != PQ_NONE) {
1025                 vm_page_queues_spin_lock(queue);
1026                 pq = &vm_page_queues[queue];
1027                 ++pq->lcnt;
1028
1029                 /*
1030                  * Adjust our pcpu stats.  If a system entity really needs
1031                  * to incorporate the count it will call vmstats_rollup()
1032                  * to roll it all up into the global vmstats strufture.
1033                  */
1034                 cnt = (long *)((char *)&mycpu->gd_vmstats_adj + pq->cnt_offset);
1035                 atomic_add_long(cnt, 1);
1036
1037                 /*
1038                  * PQ_FREE is always handled LIFO style to try to provide
1039                  * cache-hot pages to programs.
1040                  */
1041                 m->queue = queue;
1042                 if (queue - m->pc == PQ_FREE) {
1043                         TAILQ_INSERT_HEAD(&pq->pl, m, pageq);
1044                 } else if (athead) {
1045                         TAILQ_INSERT_HEAD(&pq->pl, m, pageq);
1046                 } else {
1047                         TAILQ_INSERT_TAIL(&pq->pl, m, pageq);
1048                 }
1049                 /* leave the queue spinlocked */
1050         }
1051 }
1052
1053 /*
1054  * Wait until page is no longer BUSY.  If also_m_busy is TRUE we wait
1055  * until the page is no longer BUSY or SBUSY (busy_count field is 0).
1056  *
1057  * Returns TRUE if it had to sleep, FALSE if we did not.  Only one sleep
1058  * call will be made before returning.
1059  *
1060  * This function does NOT busy the page and on return the page is not
1061  * guaranteed to be available.
1062  */
1063 void
1064 vm_page_sleep_busy(vm_page_t m, int also_m_busy, const char *msg)
1065 {
1066         u_int32_t busy_count;
1067
1068         for (;;) {
1069                 busy_count = m->busy_count;
1070                 cpu_ccfence();
1071
1072                 if ((busy_count & PBUSY_LOCKED) == 0 &&
1073                     (also_m_busy == 0 || (busy_count & PBUSY_MASK) == 0)) {
1074                         break;
1075                 }
1076                 tsleep_interlock(m, 0);
1077                 if (atomic_cmpset_int(&m->busy_count, busy_count,
1078                                       busy_count | PBUSY_WANTED)) {
1079                         atomic_set_int(&m->flags, PG_REFERENCED);
1080                         tsleep(m, PINTERLOCKED, msg, 0);
1081                         break;
1082                 }
1083         }
1084 }
1085
1086 /*
1087  * This calculates and returns a page color given an optional VM object and
1088  * either a pindex or an iterator.  We attempt to return a cpu-localized
1089  * pg_color that is still roughly 16-way set-associative.  The CPU topology
1090  * is used if it was probed.
1091  *
1092  * The caller may use the returned value to index into e.g. PQ_FREE when
1093  * allocating a page in order to nominally obtain pages that are hopefully
1094  * already localized to the requesting cpu.  This function is not able to
1095  * provide any sort of guarantee of this, but does its best to improve
1096  * hardware cache management performance.
1097  *
1098  * WARNING! The caller must mask the returned value with PQ_L2_MASK.
1099  */
1100 u_short
1101 vm_get_pg_color(int cpuid, vm_object_t object, vm_pindex_t pindex)
1102 {
1103         u_short pg_color;
1104         int object_pg_color;
1105
1106         /*
1107          * WARNING! cpu_topology_core_ids might not be a power of two.
1108          *          We also shouldn't make assumptions about
1109          *          cpu_topology_phys_ids either.
1110          *
1111          * WARNING! ncpus might not be known at this time (during early
1112          *          boot), and might be set to 1.
1113          *
1114          * General format: [phys_id][core_id][cpuid][set-associativity]
1115          * (but uses modulo, so not necessarily precise bit masks)
1116          */
1117         object_pg_color = object ? object->pg_color : 0;
1118
1119         if (cpu_topology_ht_ids) {
1120                 int phys_id;
1121                 int core_id;
1122                 int ht_id;
1123                 int physcale;
1124                 int grpscale;
1125                 int cpuscale;
1126
1127                 /*
1128                  * Translate cpuid to socket, core, and hyperthread id.
1129                  */
1130                 phys_id = get_cpu_phys_id(cpuid);
1131                 core_id = get_cpu_core_id(cpuid);
1132                 ht_id = get_cpu_ht_id(cpuid);
1133
1134                 /*
1135                  * Calculate pg_color for our array index.
1136                  *
1137                  * physcale - socket multiplier.
1138                  * grpscale - core multiplier (cores per socket)
1139                  * cpu*     - cpus per core
1140                  *
1141                  * WARNING! In early boot, ncpus has not yet been
1142                  *          initialized and may be set to (1).
1143                  *
1144                  * WARNING! physcale must match the organization that
1145                  *          vm_numa_organize() creates to ensure that
1146                  *          we properly localize allocations to the
1147                  *          requested cpuid.
1148                  */
1149                 physcale = PQ_L2_SIZE / cpu_topology_phys_ids;
1150                 grpscale = physcale / cpu_topology_core_ids;
1151                 cpuscale = grpscale / cpu_topology_ht_ids;
1152
1153                 pg_color = phys_id * physcale;
1154                 pg_color += core_id * grpscale;
1155                 pg_color += ht_id * cpuscale;
1156                 pg_color += (pindex + object_pg_color) % cpuscale;
1157
1158 #if 0
1159                 if (grpsize >= 8) {
1160                         pg_color += (pindex + object_pg_color) % grpsize;
1161                 } else {
1162                         if (grpsize <= 2) {
1163                                 grpsize = 8;
1164                         } else {
1165                                 /* 3->9, 4->8, 5->10, 6->12, 7->14 */
1166                                 grpsize += grpsize;
1167                                 if (grpsize < 8)
1168                                         grpsize += grpsize;
1169                         }
1170                         pg_color += (pindex + object_pg_color) % grpsize;
1171                 }
1172 #endif
1173         } else {
1174                 /*
1175                  * Unknown topology, distribute things evenly.
1176                  *
1177                  * WARNING! In early boot, ncpus has not yet been
1178                  *          initialized and may be set to (1).
1179                  */
1180                 int cpuscale;
1181
1182                 cpuscale = PQ_L2_SIZE / ncpus;
1183
1184                 pg_color = cpuid * cpuscale;
1185                 pg_color += (pindex + object_pg_color) % cpuscale;
1186         }
1187         return (pg_color & PQ_L2_MASK);
1188 }
1189
1190 /*
1191  * Wait until BUSY can be set, then set it.  If also_m_busy is TRUE we
1192  * also wait for m->busy_count to become 0 before setting PBUSY_LOCKED.
1193  */
1194 void
1195 VM_PAGE_DEBUG_EXT(vm_page_busy_wait)(vm_page_t m,
1196                                      int also_m_busy, const char *msg
1197                                      VM_PAGE_DEBUG_ARGS)
1198 {
1199         u_int32_t busy_count;
1200
1201         for (;;) {
1202                 busy_count = m->busy_count;
1203                 cpu_ccfence();
1204                 if (busy_count & PBUSY_LOCKED) {
1205                         tsleep_interlock(m, 0);
1206                         if (atomic_cmpset_int(&m->busy_count, busy_count,
1207                                           busy_count | PBUSY_WANTED)) {
1208                                 atomic_set_int(&m->flags, PG_REFERENCED);
1209                                 tsleep(m, PINTERLOCKED, msg, 0);
1210                         }
1211                 } else if (also_m_busy && busy_count) {
1212                         tsleep_interlock(m, 0);
1213                         if (atomic_cmpset_int(&m->busy_count, busy_count,
1214                                           busy_count | PBUSY_WANTED)) {
1215                                 atomic_set_int(&m->flags, PG_REFERENCED);
1216                                 tsleep(m, PINTERLOCKED, msg, 0);
1217                         }
1218                 } else {
1219                         if (atomic_cmpset_int(&m->busy_count, busy_count,
1220                                               busy_count | PBUSY_LOCKED)) {
1221 #ifdef VM_PAGE_DEBUG
1222                                 m->busy_func = func;
1223                                 m->busy_line = lineno;
1224 #endif
1225                                 break;
1226                         }
1227                 }
1228         }
1229 }
1230
1231 /*
1232  * Attempt to set BUSY.  If also_m_busy is TRUE we only succeed if
1233  * m->busy_count is also 0.
1234  *
1235  * Returns non-zero on failure.
1236  */
1237 int
1238 VM_PAGE_DEBUG_EXT(vm_page_busy_try)(vm_page_t m, int also_m_busy
1239                                     VM_PAGE_DEBUG_ARGS)
1240 {
1241         u_int32_t busy_count;
1242
1243         for (;;) {
1244                 busy_count = m->busy_count;
1245                 cpu_ccfence();
1246                 if (busy_count & PBUSY_LOCKED)
1247                         return TRUE;
1248                 if (also_m_busy && (busy_count & PBUSY_MASK) != 0)
1249                         return TRUE;
1250                 if (atomic_cmpset_int(&m->busy_count, busy_count,
1251                                       busy_count | PBUSY_LOCKED)) {
1252 #ifdef VM_PAGE_DEBUG
1253                                 m->busy_func = func;
1254                                 m->busy_line = lineno;
1255 #endif
1256                         return FALSE;
1257                 }
1258         }
1259 }
1260
1261 /*
1262  * Clear the BUSY flag and return non-zero to indicate to the caller
1263  * that a wakeup() should be performed.
1264  *
1265  * (inline version)
1266  */
1267 static __inline
1268 int
1269 _vm_page_wakeup(vm_page_t m)
1270 {
1271         u_int32_t busy_count;
1272
1273         busy_count = m->busy_count;
1274         cpu_ccfence();
1275         for (;;) {
1276                 if (atomic_fcmpset_int(&m->busy_count, &busy_count,
1277                                       busy_count &
1278                                       ~(PBUSY_LOCKED | PBUSY_WANTED))) {
1279                         return((int)(busy_count & PBUSY_WANTED));
1280                 }
1281         }
1282         /* not reached */
1283 }
1284
1285 /*
1286  * Clear the BUSY flag and wakeup anyone waiting for the page.  This
1287  * is typically the last call you make on a page before moving onto
1288  * other things.
1289  */
1290 void
1291 vm_page_wakeup(vm_page_t m)
1292 {
1293         KASSERT(m->busy_count & PBUSY_LOCKED,
1294                 ("vm_page_wakeup: page not busy!!!"));
1295         if (_vm_page_wakeup(m))
1296                 wakeup(m);
1297 }
1298
1299 /*
1300  * Hold a page, preventing reuse.  This is typically only called on pages
1301  * in a known state (either held busy, special, or interlocked in some
1302  * manner).  Holding a page does not ensure that it remains valid, it only
1303  * prevents reuse.  The page must not already be on the FREE queue or in
1304  * any danger of being moved to the FREE queue concurrent with this call.
1305  *
1306  * Other parts of the system can still disassociate the page from its object
1307  * and attempt to free it, or perform read or write I/O on it and/or otherwise
1308  * manipulate the page, but if the page is held the VM system will leave the
1309  * page and its data intact and not cycle it through the FREE queue until
1310  * the last hold has been released.
1311  *
1312  * (see vm_page_wire() if you want to prevent the page from being
1313  *  disassociated from its object too).
1314  */
1315 void
1316 vm_page_hold(vm_page_t m)
1317 {
1318         atomic_add_int(&m->hold_count, 1);
1319         KKASSERT(m->queue - m->pc != PQ_FREE);
1320 }
1321
1322 /*
1323  * The opposite of vm_page_hold().  If the page is on the HOLD queue
1324  * it was freed while held and must be moved back to the FREE queue.
1325  *
1326  * To avoid racing against vm_page_free*() we must re-test conditions
1327  * after obtaining the spin-lock.  The initial test can also race a
1328  * vm_page_free*() that is in the middle of moving a page to PQ_HOLD,
1329  * leaving the page on PQ_HOLD with hold_count == 0.  Rather than
1330  * throw a spin-lock in the critical path, we rely on the pageout
1331  * daemon to clean-up these loose ends.
1332  *
1333  * More critically, the 'easy movement' between queues without busying
1334  * a vm_page is only allowed for PQ_FREE<->PQ_HOLD.
1335  */
1336 void
1337 vm_page_unhold(vm_page_t m)
1338 {
1339         KASSERT(m->hold_count > 0 && m->queue - m->pc != PQ_FREE,
1340                 ("vm_page_unhold: pg %p illegal hold_count (%d) or "
1341                  "on FREE queue (%d)",
1342                  m, m->hold_count, m->queue - m->pc));
1343
1344         if (atomic_fetchadd_int(&m->hold_count, -1) == 1 &&
1345             m->queue - m->pc == PQ_HOLD) {
1346                 vm_page_spin_lock(m);
1347                 if (m->hold_count == 0 && m->queue - m->pc == PQ_HOLD) {
1348                         _vm_page_queue_spin_lock(m);
1349                         _vm_page_rem_queue_spinlocked(m);
1350                         _vm_page_add_queue_spinlocked(m, PQ_FREE + m->pc, 1);
1351                         _vm_page_queue_spin_unlock(m);
1352                 }
1353                 vm_page_spin_unlock(m);
1354         }
1355 }
1356
1357 /*
1358  * Create a fictitious page with the specified physical address and
1359  * memory attribute.  The memory attribute is the only the machine-
1360  * dependent aspect of a fictitious page that must be initialized.
1361  */
1362 void
1363 vm_page_initfake(vm_page_t m, vm_paddr_t paddr, vm_memattr_t memattr)
1364 {
1365         if ((m->flags & PG_FICTITIOUS) != 0) {
1366                 /*
1367                  * The page's memattr might have changed since the
1368                  * previous initialization.  Update the pmap to the
1369                  * new memattr.
1370                  */
1371                 goto memattr;
1372         }
1373         m->phys_addr = paddr;
1374         m->queue = PQ_NONE;
1375         /* Fictitious pages don't use "segind". */
1376         /* Fictitious pages don't use "order" or "pool". */
1377         m->flags = PG_FICTITIOUS | PG_UNMANAGED;
1378         m->busy_count = PBUSY_LOCKED;
1379         m->wire_count = 1;
1380         spin_init(&m->spin, "fake_page");
1381         pmap_page_init(m);
1382 memattr:
1383         pmap_page_set_memattr(m, memattr);
1384 }
1385
1386 /*
1387  * Inserts the given vm_page into the object and object list.
1388  *
1389  * The pagetables are not updated but will presumably fault the page
1390  * in if necessary, or if a kernel page the caller will at some point
1391  * enter the page into the kernel's pmap.  We are not allowed to block
1392  * here so we *can't* do this anyway.
1393  *
1394  * This routine may not block.
1395  * This routine must be called with the vm_object held.
1396  * This routine must be called with a critical section held.
1397  *
1398  * This routine returns TRUE if the page was inserted into the object
1399  * successfully, and FALSE if the page already exists in the object.
1400  */
1401 int
1402 vm_page_insert(vm_page_t m, vm_object_t object, vm_pindex_t pindex)
1403 {
1404         ASSERT_LWKT_TOKEN_HELD_EXCL(vm_object_token(object));
1405         if (m->object != NULL)
1406                 panic("vm_page_insert: already inserted");
1407
1408         atomic_add_int(&object->generation, 1);
1409
1410         /*
1411          * Associate the VM page with an (object, offset).
1412          *
1413          * The vm_page spin lock is required for interactions with the pmap.
1414          */
1415         vm_page_spin_lock(m);
1416         m->object = object;
1417         m->pindex = pindex;
1418         if (vm_page_rb_tree_RB_INSERT(&object->rb_memq, m)) {
1419                 m->object = NULL;
1420                 m->pindex = 0;
1421                 vm_page_spin_unlock(m);
1422                 return FALSE;
1423         }
1424         ++object->resident_page_count;
1425         ++mycpu->gd_vmtotal.t_rm;
1426         vm_page_spin_unlock(m);
1427
1428         /*
1429          * Since we are inserting a new and possibly dirty page,
1430          * update the object's OBJ_WRITEABLE and OBJ_MIGHTBEDIRTY flags.
1431          */
1432         if ((m->valid & m->dirty) ||
1433             (m->flags & (PG_WRITEABLE | PG_NEED_COMMIT)))
1434                 vm_object_set_writeable_dirty(object);
1435
1436         /*
1437          * Checks for a swap assignment and sets PG_SWAPPED if appropriate.
1438          */
1439         swap_pager_page_inserted(m);
1440         return TRUE;
1441 }
1442
1443 /*
1444  * Removes the given vm_page_t from the (object,index) table
1445  *
1446  * The page must be BUSY and will remain BUSY on return.
1447  * No other requirements.
1448  *
1449  * NOTE: FreeBSD side effect was to unbusy the page on return.  We leave
1450  *       it busy.
1451  *
1452  * NOTE: Caller is responsible for any pmap disposition prior to the
1453  *       rename (as the pmap code will not be able to find the entries
1454  *       once the object has been disassociated).  The caller may choose
1455  *       to leave the pmap association intact if this routine is being
1456  *       called as part of a rename between shadowed objects.
1457  *
1458  * This routine may not block.
1459  */
1460 void
1461 vm_page_remove(vm_page_t m)
1462 {
1463         vm_object_t object;
1464
1465         if (m->object == NULL) {
1466                 return;
1467         }
1468
1469         if ((m->busy_count & PBUSY_LOCKED) == 0)
1470                 panic("vm_page_remove: page not busy");
1471
1472         object = m->object;
1473
1474         vm_object_hold(object);
1475
1476         /*
1477          * Remove the page from the object and update the object.
1478          *
1479          * The vm_page spin lock is required for interactions with the pmap.
1480          */
1481         vm_page_spin_lock(m);
1482         vm_page_rb_tree_RB_REMOVE(&object->rb_memq, m);
1483         --object->resident_page_count;
1484         --mycpu->gd_vmtotal.t_rm;
1485         m->object = NULL;
1486         atomic_add_int(&object->generation, 1);
1487         vm_page_spin_unlock(m);
1488
1489         vm_object_drop(object);
1490 }
1491
1492 /*
1493  * Calculate the hash position for the vm_page hash heuristic.
1494  *
1495  * Mask by ~3 to offer 4-way set-assoc
1496  */
1497 static __inline
1498 struct vm_page_hash_elm *
1499 vm_page_hash_hash(vm_object_t object, vm_pindex_t pindex)
1500 {
1501         size_t hi;
1502
1503         hi = ((object->pg_color << 8) ^ (uintptr_t)object) + (pindex << 2);
1504         hi &= vm_page_hash_size - 1;
1505         hi &= ~3;
1506         return (&vm_page_hash[hi]);
1507 }
1508
1509 /*
1510  * Heuristical page lookup that does not require any locks.  Returns
1511  * a soft-busied page on success, NULL on failure.
1512  *
1513  * Caller must lookup the page the slow way if NULL is returned.
1514  */
1515 vm_page_t
1516 vm_page_hash_get(vm_object_t object, vm_pindex_t pindex)
1517 {
1518         struct vm_page_hash_elm *mp;
1519         vm_page_t m;
1520         int i;
1521
1522         if (vm_page_hash == NULL)
1523                 return NULL;
1524         mp = vm_page_hash_hash(object, pindex);
1525         for (i = 0; i < 4; ++i) {
1526                 m = mp[i].m;
1527                 cpu_ccfence();
1528                 if (m == NULL)
1529                         continue;
1530                 if (m->object != object || m->pindex != pindex)
1531                         continue;
1532                 if (vm_page_sbusy_try(m))
1533                         continue;
1534                 if (m->object == object && m->pindex == pindex) {
1535                         mp[i].ticks = ticks;
1536                         return m;
1537                 }
1538                 vm_page_sbusy_drop(m);
1539         }
1540         return NULL;
1541 }
1542
1543 /*
1544  * Enter page onto vm_page_hash[].  This is a heuristic, SMP collisions
1545  * are allowed.
1546  */
1547 static __inline
1548 void
1549 vm_page_hash_enter(vm_page_t m)
1550 {
1551         struct vm_page_hash_elm *mp;
1552         struct vm_page_hash_elm *best;
1553         int i;
1554
1555         if (vm_page_hash &&
1556             m > &vm_page_array[0] &&
1557             m < &vm_page_array[vm_page_array_size]) {
1558                 mp = vm_page_hash_hash(m->object, m->pindex);
1559                 best = mp;
1560                 for (i = 0; i < 4; ++i) {
1561                         if (mp[i].m == m) {
1562                                 mp[i].ticks = ticks;
1563                                 return;
1564                         }
1565
1566                         /*
1567                          * The best choice is the oldest entry
1568                          */
1569                         if ((ticks - best->ticks) < (ticks - mp[i].ticks) ||
1570                             (int)(ticks - mp[i].ticks) < 0) {
1571                                 best = &mp[i];
1572                         }
1573                 }
1574                 best->m = m;
1575                 best->ticks = ticks;
1576         }
1577 }
1578
1579 /*
1580  * Locate and return the page at (object, pindex), or NULL if the
1581  * page could not be found.
1582  *
1583  * The caller must hold the vm_object token.
1584  */
1585 vm_page_t
1586 vm_page_lookup(vm_object_t object, vm_pindex_t pindex)
1587 {
1588         vm_page_t m;
1589
1590         /*
1591          * Search the hash table for this object/offset pair
1592          */
1593         ASSERT_LWKT_TOKEN_HELD(vm_object_token(object));
1594         m = vm_page_rb_tree_RB_LOOKUP(&object->rb_memq, pindex);
1595         if (m) {
1596                 KKASSERT(m->object == object && m->pindex == pindex);
1597                 vm_page_hash_enter(m);
1598         }
1599         return(m);
1600 }
1601
1602 vm_page_t
1603 VM_PAGE_DEBUG_EXT(vm_page_lookup_busy_wait)(struct vm_object *object,
1604                                             vm_pindex_t pindex,
1605                                             int also_m_busy, const char *msg
1606                                             VM_PAGE_DEBUG_ARGS)
1607 {
1608         u_int32_t busy_count;
1609         vm_page_t m;
1610
1611         ASSERT_LWKT_TOKEN_HELD(vm_object_token(object));
1612         m = vm_page_rb_tree_RB_LOOKUP(&object->rb_memq, pindex);
1613         while (m) {
1614                 KKASSERT(m->object == object && m->pindex == pindex);
1615                 busy_count = m->busy_count;
1616                 cpu_ccfence();
1617                 if (busy_count & PBUSY_LOCKED) {
1618                         tsleep_interlock(m, 0);
1619                         if (atomic_cmpset_int(&m->busy_count, busy_count,
1620                                           busy_count | PBUSY_WANTED)) {
1621                                 atomic_set_int(&m->flags, PG_REFERENCED);
1622                                 tsleep(m, PINTERLOCKED, msg, 0);
1623                                 m = vm_page_rb_tree_RB_LOOKUP(&object->rb_memq,
1624                                                               pindex);
1625                         }
1626                 } else if (also_m_busy && busy_count) {
1627                         tsleep_interlock(m, 0);
1628                         if (atomic_cmpset_int(&m->busy_count, busy_count,
1629                                           busy_count | PBUSY_WANTED)) {
1630                                 atomic_set_int(&m->flags, PG_REFERENCED);
1631                                 tsleep(m, PINTERLOCKED, msg, 0);
1632                                 m = vm_page_rb_tree_RB_LOOKUP(&object->rb_memq,
1633                                                               pindex);
1634                         }
1635                 } else if (atomic_cmpset_int(&m->busy_count, busy_count,
1636                                              busy_count | PBUSY_LOCKED)) {
1637 #ifdef VM_PAGE_DEBUG
1638                         m->busy_func = func;
1639                         m->busy_line = lineno;
1640 #endif
1641                         vm_page_hash_enter(m);
1642                         break;
1643                 }
1644         }
1645         return m;
1646 }
1647
1648 /*
1649  * Attempt to lookup and busy a page.
1650  *
1651  * Returns NULL if the page could not be found
1652  *
1653  * Returns a vm_page and error == TRUE if the page exists but could not
1654  * be busied.
1655  *
1656  * Returns a vm_page and error == FALSE on success.
1657  */
1658 vm_page_t
1659 VM_PAGE_DEBUG_EXT(vm_page_lookup_busy_try)(struct vm_object *object,
1660                                            vm_pindex_t pindex,
1661                                            int also_m_busy, int *errorp
1662                                            VM_PAGE_DEBUG_ARGS)
1663 {
1664         u_int32_t busy_count;
1665         vm_page_t m;
1666
1667         ASSERT_LWKT_TOKEN_HELD(vm_object_token(object));
1668         m = vm_page_rb_tree_RB_LOOKUP(&object->rb_memq, pindex);
1669         *errorp = FALSE;
1670         while (m) {
1671                 KKASSERT(m->object == object && m->pindex == pindex);
1672                 busy_count = m->busy_count;
1673                 cpu_ccfence();
1674                 if (busy_count & PBUSY_LOCKED) {
1675                         *errorp = TRUE;
1676                         break;
1677                 }
1678                 if (also_m_busy && busy_count) {
1679                         *errorp = TRUE;
1680                         break;
1681                 }
1682                 if (atomic_cmpset_int(&m->busy_count, busy_count,
1683                                       busy_count | PBUSY_LOCKED)) {
1684 #ifdef VM_PAGE_DEBUG
1685                         m->busy_func = func;
1686                         m->busy_line = lineno;
1687 #endif
1688                         vm_page_hash_enter(m);
1689                         break;
1690                 }
1691         }
1692         return m;
1693 }
1694
1695 /*
1696  * Returns a page that is only soft-busied for use by the caller in
1697  * a read-only fashion.  Returns NULL if the page could not be found,
1698  * the soft busy could not be obtained, or the page data is invalid.
1699  */
1700 vm_page_t
1701 vm_page_lookup_sbusy_try(struct vm_object *object, vm_pindex_t pindex,
1702                          int pgoff, int pgbytes)
1703 {
1704         vm_page_t m;
1705
1706         ASSERT_LWKT_TOKEN_HELD(vm_object_token(object));
1707         m = vm_page_rb_tree_RB_LOOKUP(&object->rb_memq, pindex);
1708         if (m) {
1709                 if ((m->valid != VM_PAGE_BITS_ALL &&
1710                      !vm_page_is_valid(m, pgoff, pgbytes)) ||
1711                     (m->flags & PG_FICTITIOUS)) {
1712                         m = NULL;
1713                 } else if (vm_page_sbusy_try(m)) {
1714                         m = NULL;
1715                 } else if ((m->valid != VM_PAGE_BITS_ALL &&
1716                             !vm_page_is_valid(m, pgoff, pgbytes)) ||
1717                            (m->flags & PG_FICTITIOUS)) {
1718                         vm_page_sbusy_drop(m);
1719                         m = NULL;
1720                 } else {
1721                         vm_page_hash_enter(m);
1722                 }
1723         }
1724         return m;
1725 }
1726
1727 /*
1728  * Caller must hold the related vm_object
1729  */
1730 vm_page_t
1731 vm_page_next(vm_page_t m)
1732 {
1733         vm_page_t next;
1734
1735         next = vm_page_rb_tree_RB_NEXT(m);
1736         if (next && next->pindex != m->pindex + 1)
1737                 next = NULL;
1738         return (next);
1739 }
1740
1741 /*
1742  * vm_page_rename()
1743  *
1744  * Move the given vm_page from its current object to the specified
1745  * target object/offset.  The page must be busy and will remain so
1746  * on return.
1747  *
1748  * new_object must be held.
1749  * This routine might block. XXX ?
1750  *
1751  * NOTE: Swap associated with the page must be invalidated by the move.  We
1752  *       have to do this for several reasons:  (1) we aren't freeing the
1753  *       page, (2) we are dirtying the page, (3) the VM system is probably
1754  *       moving the page from object A to B, and will then later move
1755  *       the backing store from A to B and we can't have a conflict.
1756  *
1757  * NOTE: We *always* dirty the page.  It is necessary both for the
1758  *       fact that we moved it, and because we may be invalidating
1759  *       swap.  If the page is on the cache, we have to deactivate it
1760  *       or vm_page_dirty() will panic.  Dirty pages are not allowed
1761  *       on the cache.
1762  *
1763  * NOTE: Caller is responsible for any pmap disposition prior to the
1764  *       rename (as the pmap code will not be able to find the entries
1765  *       once the object has been disassociated or changed).  Nominally
1766  *       the caller is moving a page between shadowed objects and so the
1767  *       pmap association is retained without having to remove the page
1768  *       from it.
1769  */
1770 void
1771 vm_page_rename(vm_page_t m, vm_object_t new_object, vm_pindex_t new_pindex)
1772 {
1773         KKASSERT(m->busy_count & PBUSY_LOCKED);
1774         ASSERT_LWKT_TOKEN_HELD_EXCL(vm_object_token(new_object));
1775         if (m->object) {
1776                 ASSERT_LWKT_TOKEN_HELD_EXCL(vm_object_token(m->object));
1777                 vm_page_remove(m);
1778         }
1779         if (vm_page_insert(m, new_object, new_pindex) == FALSE) {
1780                 panic("vm_page_rename: target exists (%p,%"PRIu64")",
1781                       new_object, new_pindex);
1782         }
1783         if (m->queue - m->pc == PQ_CACHE)
1784                 vm_page_deactivate(m);
1785         vm_page_dirty(m);
1786 }
1787
1788 /*
1789  * vm_page_unqueue() without any wakeup.  This routine is used when a page
1790  * is to remain BUSYied by the caller.
1791  *
1792  * This routine may not block.
1793  */
1794 void
1795 vm_page_unqueue_nowakeup(vm_page_t m)
1796 {
1797         vm_page_and_queue_spin_lock(m);
1798         (void)_vm_page_rem_queue_spinlocked(m);
1799         vm_page_spin_unlock(m);
1800 }
1801
1802 /*
1803  * vm_page_unqueue() - Remove a page from its queue, wakeup the pagedemon
1804  * if necessary.
1805  *
1806  * This routine may not block.
1807  */
1808 void
1809 vm_page_unqueue(vm_page_t m)
1810 {
1811         u_short queue;
1812
1813         vm_page_and_queue_spin_lock(m);
1814         queue = _vm_page_rem_queue_spinlocked(m);
1815         if (queue == PQ_FREE || queue == PQ_CACHE) {
1816                 vm_page_spin_unlock(m);
1817                 pagedaemon_wakeup();
1818         } else {
1819                 vm_page_spin_unlock(m);
1820         }
1821 }
1822
1823 /*
1824  * vm_page_list_find()
1825  *
1826  * Find a page on the specified queue with color optimization.
1827  *
1828  * The page coloring optimization attempts to locate a page that does
1829  * not overload other nearby pages in the object in the cpu's L1 or L2
1830  * caches.  We need this optimization because cpu caches tend to be
1831  * physical caches, while object spaces tend to be virtual.
1832  *
1833  * The page coloring optimization also, very importantly, tries to localize
1834  * memory to cpus and physical sockets.
1835  *
1836  * Each PQ_FREE and PQ_CACHE color queue has its own spinlock and the
1837  * algorithm is adjusted to localize allocations on a per-core basis.
1838  * This is done by 'twisting' the colors.
1839  *
1840  * The page is returned spinlocked and removed from its queue (it will
1841  * be on PQ_NONE), or NULL. The page is not BUSY'd.  The caller
1842  * is responsible for dealing with the busy-page case (usually by
1843  * deactivating the page and looping).
1844  *
1845  * NOTE:  This routine is carefully inlined.  A non-inlined version
1846  *        is available for outside callers but the only critical path is
1847  *        from within this source file.
1848  *
1849  * NOTE:  This routine assumes that the vm_pages found in PQ_CACHE and PQ_FREE
1850  *        represent stable storage, allowing us to order our locks vm_page
1851  *        first, then queue.
1852  */
1853 static __inline
1854 vm_page_t
1855 _vm_page_list_find(int basequeue, int index)
1856 {
1857         struct vpgqueues *pq;
1858         vm_page_t m;
1859
1860         index &= PQ_L2_MASK;
1861         pq = &vm_page_queues[basequeue + index];
1862
1863         /*
1864          * Try this cpu's colored queue first.  Test for a page unlocked,
1865          * then lock the queue and locate a page.  Note that the lock order
1866          * is reversed, but we do not want to dwadle on the page spinlock
1867          * anyway as it is held significantly longer than the queue spinlock.
1868          */
1869         if (TAILQ_FIRST(&pq->pl)) {
1870                 spin_lock(&pq->spin);
1871                 TAILQ_FOREACH(m, &pq->pl, pageq) {
1872                         if (spin_trylock(&m->spin) == 0)
1873                                 continue;
1874                         KKASSERT(m->queue == basequeue + index);
1875                         _vm_page_rem_queue_spinlocked(m);
1876                         pq->lastq = -1;
1877                         return(m);
1878                 }
1879                 spin_unlock(&pq->spin);
1880         }
1881
1882         /*
1883          * If we are unable to get a page, do a more involved NUMA-aware
1884          * search.  However, to avoid re-searching empty queues over and
1885          * over again skip to pq->last if appropriate.
1886          */
1887         if (pq->lastq >= 0)
1888                 index = pq->lastq;
1889
1890         m = _vm_page_list_find2(basequeue, index, &pq->lastq);
1891
1892         return(m);
1893 }
1894
1895 /*
1896  * If we could not find the page in the desired queue try to find it in
1897  * a nearby (NUMA-aware) queue.
1898  */
1899 static vm_page_t
1900 _vm_page_list_find2(int basequeue, int index, int *lastp)
1901 {
1902         struct vpgqueues *pq;
1903         vm_page_t m = NULL;
1904         int pqmask = set_assoc_mask >> 1;
1905         int pqstart = 0;
1906         int pqi;
1907         int i;
1908
1909         index &= PQ_L2_MASK;
1910         pq = &vm_page_queues[basequeue];
1911
1912         /*
1913          * Run local sets of 16, 32, 64, 128, up to the entire queue if all
1914          * else fails (PQ_L2_MASK).
1915          *
1916          * pqmask is a mask, 15, 31, 63, etc.
1917          *
1918          * Test each queue unlocked first, then lock the queue and locate
1919          * a page.  Note that the lock order is reversed, but we do not want
1920          * to dwadle on the page spinlock anyway as it is held significantly
1921          * longer than the queue spinlock.
1922          */
1923         do {
1924                 pqmask = (pqmask << 1) | 1;
1925                 for (i = pqstart; i <= pqmask; ++i) {
1926                         pqi = (index & ~pqmask) | ((index + i) & pqmask);
1927                         if (TAILQ_FIRST(&pq[pqi].pl)) {
1928                                 spin_lock(&pq[pqi].spin);
1929                                 TAILQ_FOREACH(m, &pq[pqi].pl, pageq) {
1930                                         if (spin_trylock(&m->spin) == 0)
1931                                                 continue;
1932                                         KKASSERT(m->queue == basequeue + pqi);
1933                                         _vm_page_rem_queue_spinlocked(m);
1934
1935                                         /*
1936                                          * If we had to wander too far, set
1937                                          * *lastp to skip past empty queues.
1938                                          */
1939                                         if (i >= 8)
1940                                                 *lastp = pqi & PQ_L2_MASK;
1941                                         return(m);
1942                                 }
1943                                 spin_unlock(&pq[pqi].spin);
1944                         }
1945                 }
1946                 pqstart = i;
1947         } while (pqmask != PQ_L2_MASK);
1948
1949         return(m);
1950 }
1951
1952 /*
1953  * Returns a vm_page candidate for allocation.  The page is not busied so
1954  * it can move around.  The caller must busy the page (and typically
1955  * deactivate it if it cannot be busied!)
1956  *
1957  * Returns a spinlocked vm_page that has been removed from its queue.
1958  */
1959 vm_page_t
1960 vm_page_list_find(int basequeue, int index)
1961 {
1962         return(_vm_page_list_find(basequeue, index));
1963 }
1964
1965 /*
1966  * Find a page on the cache queue with color optimization, remove it
1967  * from the queue, and busy it.  The returned page will not be spinlocked.
1968  *
1969  * A candidate failure will be deactivated.  Candidates can fail due to
1970  * being busied by someone else, in which case they will be deactivated.
1971  *
1972  * This routine may not block.
1973  *
1974  */
1975 static vm_page_t
1976 vm_page_select_cache(u_short pg_color)
1977 {
1978         vm_page_t m;
1979
1980         for (;;) {
1981                 m = _vm_page_list_find(PQ_CACHE, pg_color);
1982                 if (m == NULL)
1983                         break;
1984                 /*
1985                  * (m) has been removed from its queue and spinlocked
1986                  */
1987                 if (vm_page_busy_try(m, TRUE)) {
1988                         _vm_page_deactivate_locked(m, 0);
1989                         vm_page_spin_unlock(m);
1990                 } else {
1991                         /*
1992                          * We successfully busied the page
1993                          */
1994                         if ((m->flags & (PG_UNMANAGED | PG_NEED_COMMIT)) == 0 &&
1995                             m->hold_count == 0 &&
1996                             m->wire_count == 0 &&
1997                             (m->dirty & m->valid) == 0) {
1998                                 vm_page_spin_unlock(m);
1999                                 pagedaemon_wakeup();
2000                                 return(m);
2001                         }
2002
2003                         /*
2004                          * The page cannot be recycled, deactivate it.
2005                          */
2006                         _vm_page_deactivate_locked(m, 0);
2007                         if (_vm_page_wakeup(m)) {
2008                                 vm_page_spin_unlock(m);
2009                                 wakeup(m);
2010                         } else {
2011                                 vm_page_spin_unlock(m);
2012                         }
2013                 }
2014         }
2015         return (m);
2016 }
2017
2018 /*
2019  * Find a free page.  We attempt to inline the nominal case and fall back
2020  * to _vm_page_select_free() otherwise.  A busied page is removed from
2021  * the queue and returned.
2022  *
2023  * This routine may not block.
2024  */
2025 static __inline vm_page_t
2026 vm_page_select_free(u_short pg_color)
2027 {
2028         vm_page_t m;
2029
2030         for (;;) {
2031                 m = _vm_page_list_find(PQ_FREE, pg_color);
2032                 if (m == NULL)
2033                         break;
2034                 if (vm_page_busy_try(m, TRUE)) {
2035                         /*
2036                          * Various mechanisms such as a pmap_collect can
2037                          * result in a busy page on the free queue.  We
2038                          * have to move the page out of the way so we can
2039                          * retry the allocation.  If the other thread is not
2040                          * allocating the page then m->valid will remain 0 and
2041                          * the pageout daemon will free the page later on.
2042                          *
2043                          * Since we could not busy the page, however, we
2044                          * cannot make assumptions as to whether the page
2045                          * will be allocated by the other thread or not,
2046                          * so all we can do is deactivate it to move it out
2047                          * of the way.  In particular, if the other thread
2048                          * wires the page it may wind up on the inactive
2049                          * queue and the pageout daemon will have to deal
2050                          * with that case too.
2051                          */
2052                         _vm_page_deactivate_locked(m, 0);
2053                         vm_page_spin_unlock(m);
2054                 } else {
2055                         /*
2056                          * Theoretically if we are able to busy the page
2057                          * atomic with the queue removal (using the vm_page
2058                          * lock) nobody else should have been able to mess
2059                          * with the page before us.
2060                          *
2061                          * Assert the page state.  Note that even though
2062                          * wiring doesn't adjust queues, a page on the free
2063                          * queue should never be wired at this point.
2064                          */
2065                         KKASSERT((m->flags & (PG_UNMANAGED |
2066                                               PG_NEED_COMMIT)) == 0);
2067                         KASSERT(m->hold_count == 0,
2068                                 ("m->hold_count is not zero "
2069                                  "pg %p q=%d flags=%08x hold=%d wire=%d",
2070                                  m, m->queue, m->flags,
2071                                  m->hold_count, m->wire_count));
2072                         KKASSERT(m->wire_count == 0);
2073                         vm_page_spin_unlock(m);
2074                         pagedaemon_wakeup();
2075
2076                         /* return busied and removed page */
2077                         return(m);
2078                 }
2079         }
2080         return(m);
2081 }
2082
2083 /*
2084  * vm_page_alloc()
2085  *
2086  * Allocate and return a memory cell associated with this VM object/offset
2087  * pair.  If object is NULL an unassociated page will be allocated.
2088  *
2089  * The returned page will be busied and removed from its queues.  This
2090  * routine can block and may return NULL if a race occurs and the page
2091  * is found to already exist at the specified (object, pindex).
2092  *
2093  *      VM_ALLOC_NORMAL         allow use of cache pages, nominal free drain
2094  *      VM_ALLOC_QUICK          like normal but cannot use cache
2095  *      VM_ALLOC_SYSTEM         greater free drain
2096  *      VM_ALLOC_INTERRUPT      allow free list to be completely drained
2097  *      VM_ALLOC_ZERO           advisory request for pre-zero'd page only
2098  *      VM_ALLOC_FORCE_ZERO     advisory request for pre-zero'd page only
2099  *      VM_ALLOC_NULL_OK        ok to return NULL on insertion collision
2100  *                              (see vm_page_grab())
2101  *      VM_ALLOC_USE_GD         ok to use per-gd cache
2102  *
2103  *      VM_ALLOC_CPU(n)         allocate using specified cpu localization
2104  *
2105  * The object must be held if not NULL
2106  * This routine may not block
2107  *
2108  * Additional special handling is required when called from an interrupt
2109  * (VM_ALLOC_INTERRUPT).  We are not allowed to mess with the page cache
2110  * in this case.
2111  */
2112 vm_page_t
2113 vm_page_alloc(vm_object_t object, vm_pindex_t pindex, int page_req)
2114 {
2115         globaldata_t gd;
2116         vm_object_t obj;
2117         vm_page_t m;
2118         u_short pg_color;
2119         int cpuid_local;
2120
2121 #if 0
2122         /*
2123          * Special per-cpu free VM page cache.  The pages are pre-busied
2124          * and pre-zerod for us.
2125          */
2126         if (gd->gd_vmpg_count && (page_req & VM_ALLOC_USE_GD)) {
2127                 crit_enter_gd(gd);
2128                 if (gd->gd_vmpg_count) {
2129                         m = gd->gd_vmpg_array[--gd->gd_vmpg_count];
2130                         crit_exit_gd(gd);
2131                         goto done;
2132                 }
2133                 crit_exit_gd(gd);
2134         }
2135 #endif
2136         m = NULL;
2137
2138         /*
2139          * CPU LOCALIZATION
2140          *
2141          * CPU localization algorithm.  Break the page queues up by physical
2142          * id and core id (note that two cpu threads will have the same core
2143          * id, and core_id != gd_cpuid).
2144          *
2145          * This is nowhere near perfect, for example the last pindex in a
2146          * subgroup will overflow into the next cpu or package.  But this
2147          * should get us good page reuse locality in heavy mixed loads.
2148          *
2149          * (may be executed before the APs are started, so other GDs might
2150          *  not exist!)
2151          */
2152         if (page_req & VM_ALLOC_CPU_SPEC)
2153                 cpuid_local = VM_ALLOC_GETCPU(page_req);
2154         else
2155                 cpuid_local = mycpu->gd_cpuid;
2156
2157         pg_color = vm_get_pg_color(cpuid_local, object, pindex);
2158
2159         KKASSERT(page_req & 
2160                 (VM_ALLOC_NORMAL|VM_ALLOC_QUICK|
2161                  VM_ALLOC_INTERRUPT|VM_ALLOC_SYSTEM));
2162
2163         /*
2164          * Certain system threads (pageout daemon, buf_daemon's) are
2165          * allowed to eat deeper into the free page list.
2166          */
2167         if (curthread->td_flags & TDF_SYSTHREAD)
2168                 page_req |= VM_ALLOC_SYSTEM;
2169
2170         /*
2171          * Impose various limitations.  Note that the v_free_reserved test
2172          * must match the opposite of vm_page_count_target() to avoid
2173          * livelocks, be careful.
2174          */
2175 loop:
2176         gd = mycpu;
2177         if (gd->gd_vmstats.v_free_count >= gd->gd_vmstats.v_free_reserved ||
2178             ((page_req & VM_ALLOC_INTERRUPT) &&
2179              gd->gd_vmstats.v_free_count > 0) ||
2180             ((page_req & VM_ALLOC_SYSTEM) &&
2181              gd->gd_vmstats.v_cache_count == 0 &&
2182                 gd->gd_vmstats.v_free_count >
2183                 gd->gd_vmstats.v_interrupt_free_min)
2184         ) {
2185                 /*
2186                  * The free queue has sufficient free pages to take one out.
2187                  */
2188                 m = vm_page_select_free(pg_color);
2189         } else if (page_req & VM_ALLOC_NORMAL) {
2190                 /*
2191                  * Allocatable from the cache (non-interrupt only).  On
2192                  * success, we must free the page and try again, thus
2193                  * ensuring that vmstats.v_*_free_min counters are replenished.
2194                  */
2195 #ifdef INVARIANTS
2196                 if (curthread->td_preempted) {
2197                         kprintf("vm_page_alloc(): warning, attempt to allocate"
2198                                 " cache page from preempting interrupt\n");
2199                         m = NULL;
2200                 } else {
2201                         m = vm_page_select_cache(pg_color);
2202                 }
2203 #else
2204                 m = vm_page_select_cache(pg_color);
2205 #endif
2206                 /*
2207                  * On success move the page into the free queue and loop.
2208                  *
2209                  * Only do this if we can safely acquire the vm_object lock,
2210                  * because this is effectively a random page and the caller
2211                  * might be holding the lock shared, we don't want to
2212                  * deadlock.
2213                  */
2214                 if (m != NULL) {
2215                         KASSERT(m->dirty == 0,
2216                                 ("Found dirty cache page %p", m));
2217                         if ((obj = m->object) != NULL) {
2218                                 if (vm_object_hold_try(obj)) {
2219                                         vm_page_protect(m, VM_PROT_NONE);
2220                                         vm_page_free(m);
2221                                         /* m->object NULL here */
2222                                         vm_object_drop(obj);
2223                                 } else {
2224                                         vm_page_deactivate(m);
2225                                         vm_page_wakeup(m);
2226                                 }
2227                         } else {
2228                                 vm_page_protect(m, VM_PROT_NONE);
2229                                 vm_page_free(m);
2230                         }
2231                         goto loop;
2232                 }
2233
2234                 /*
2235                  * On failure return NULL
2236                  */
2237                 atomic_add_int(&vm_pageout_deficit, 1);
2238                 pagedaemon_wakeup();
2239                 return (NULL);
2240         } else {
2241                 /*
2242                  * No pages available, wakeup the pageout daemon and give up.
2243                  */
2244                 atomic_add_int(&vm_pageout_deficit, 1);
2245                 pagedaemon_wakeup();
2246                 return (NULL);
2247         }
2248
2249         /*
2250          * v_free_count can race so loop if we don't find the expected
2251          * page.
2252          */
2253         if (m == NULL) {
2254                 vmstats_rollup();
2255                 goto loop;
2256         }
2257
2258         /*
2259          * Good page found.  The page has already been busied for us and
2260          * removed from its queues.
2261          */
2262         KASSERT(m->dirty == 0,
2263                 ("vm_page_alloc: free/cache page %p was dirty", m));
2264         KKASSERT(m->queue == PQ_NONE);
2265
2266 #if 0
2267 done:
2268 #endif
2269         /*
2270          * Initialize the structure, inheriting some flags but clearing
2271          * all the rest.  The page has already been busied for us.
2272          */
2273         vm_page_flag_clear(m, ~PG_KEEP_NEWPAGE_MASK);
2274
2275         KKASSERT(m->wire_count == 0);
2276         KKASSERT((m->busy_count & PBUSY_MASK) == 0);
2277         m->act_count = 0;
2278         m->valid = 0;
2279
2280         /*
2281          * Caller must be holding the object lock (asserted by
2282          * vm_page_insert()).
2283          *
2284          * NOTE: Inserting a page here does not insert it into any pmaps
2285          *       (which could cause us to block allocating memory).
2286          *
2287          * NOTE: If no object an unassociated page is allocated, m->pindex
2288          *       can be used by the caller for any purpose.
2289          */
2290         if (object) {
2291                 if (vm_page_insert(m, object, pindex) == FALSE) {
2292                         vm_page_free(m);
2293                         if ((page_req & VM_ALLOC_NULL_OK) == 0)
2294                                 panic("PAGE RACE %p[%ld]/%p",
2295                                       object, (long)pindex, m);
2296                         m = NULL;
2297                 }
2298         } else {
2299                 m->pindex = pindex;
2300         }
2301
2302         /*
2303          * Don't wakeup too often - wakeup the pageout daemon when
2304          * we would be nearly out of memory.
2305          */
2306         pagedaemon_wakeup();
2307
2308         /*
2309          * A BUSY page is returned.
2310          */
2311         return (m);
2312 }
2313
2314 /*
2315  * Returns number of pages available in our DMA memory reserve
2316  * (adjusted with vm.dma_reserved=<value>m in /boot/loader.conf)
2317  */
2318 vm_size_t
2319 vm_contig_avail_pages(void)
2320 {
2321         alist_blk_t blk;
2322         alist_blk_t count;
2323         alist_blk_t bfree;
2324         spin_lock(&vm_contig_spin);
2325         bfree = alist_free_info(&vm_contig_alist, &blk, &count);
2326         spin_unlock(&vm_contig_spin);
2327
2328         return bfree;
2329 }
2330
2331 /*
2332  * Attempt to allocate contiguous physical memory with the specified
2333  * requirements.
2334  */
2335 vm_page_t
2336 vm_page_alloc_contig(vm_paddr_t low, vm_paddr_t high,
2337                      unsigned long alignment, unsigned long boundary,
2338                      unsigned long size, vm_memattr_t memattr)
2339 {
2340         alist_blk_t blk;
2341         vm_page_t m;
2342         vm_pindex_t i;
2343 #if 0
2344         static vm_pindex_t contig_rover;
2345 #endif
2346
2347         alignment >>= PAGE_SHIFT;
2348         if (alignment == 0)
2349                 alignment = 1;
2350         boundary >>= PAGE_SHIFT;
2351         if (boundary == 0)
2352                 boundary = 1;
2353         size = (size + PAGE_MASK) >> PAGE_SHIFT;
2354
2355 #if 0
2356         /*
2357          * Disabled temporarily until we find a solution for DRM (a flag
2358          * to always use the free space reserve, for performance).
2359          */
2360         if (high == BUS_SPACE_MAXADDR && alignment <= PAGE_SIZE &&
2361             boundary <= PAGE_SIZE && size == 1 &&
2362             memattr == VM_MEMATTR_DEFAULT) {
2363                 /*
2364                  * Any page will work, use vm_page_alloc()
2365                  * (e.g. when used from kmem_alloc_attr())
2366                  */
2367                 m = vm_page_alloc(NULL, (contig_rover++) & 0x7FFFFFFF,
2368                                   VM_ALLOC_NORMAL | VM_ALLOC_SYSTEM |
2369                                   VM_ALLOC_INTERRUPT);
2370                 m->valid = VM_PAGE_BITS_ALL;
2371                 vm_page_wire(m);
2372                 vm_page_wakeup(m);
2373         } else
2374 #endif
2375         {
2376                 /*
2377                  * Use the low-memory dma reserve
2378                  */
2379                 spin_lock(&vm_contig_spin);
2380                 blk = alist_alloc(&vm_contig_alist, 0, size);
2381                 if (blk == ALIST_BLOCK_NONE) {
2382                         spin_unlock(&vm_contig_spin);
2383                         if (bootverbose) {
2384                                 kprintf("vm_page_alloc_contig: %ldk nospace\n",
2385                                         (size << PAGE_SHIFT) / 1024);
2386                                 print_backtrace(5);
2387                         }
2388                         return(NULL);
2389                 }
2390                 if (high && ((vm_paddr_t)(blk + size) << PAGE_SHIFT) > high) {
2391                         alist_free(&vm_contig_alist, blk, size);
2392                         spin_unlock(&vm_contig_spin);
2393                         if (bootverbose) {
2394                                 kprintf("vm_page_alloc_contig: %ldk high "
2395                                         "%016jx failed\n",
2396                                         (size << PAGE_SHIFT) / 1024,
2397                                         (intmax_t)high);
2398                         }
2399                         return(NULL);
2400                 }
2401                 spin_unlock(&vm_contig_spin);
2402                 m = PHYS_TO_VM_PAGE((vm_paddr_t)blk << PAGE_SHIFT);
2403         }
2404         if (vm_contig_verbose) {
2405                 kprintf("vm_page_alloc_contig: %016jx/%ldk "
2406                         "(%016jx-%016jx al=%lu bo=%lu pgs=%lu attr=%d\n",
2407                         (intmax_t)m->phys_addr,
2408                         (size << PAGE_SHIFT) / 1024,
2409                         low, high, alignment, boundary, size, memattr);
2410         }
2411         if (memattr != VM_MEMATTR_DEFAULT) {
2412                 for (i = 0;i < size; i++)
2413                         pmap_page_set_memattr(&m[i], memattr);
2414         }
2415         return m;
2416 }
2417
2418 /*
2419  * Free contiguously allocated pages.  The pages will be wired but not busy.
2420  * When freeing to the alist we leave them wired and not busy.
2421  */
2422 void
2423 vm_page_free_contig(vm_page_t m, unsigned long size)
2424 {
2425         vm_paddr_t pa = VM_PAGE_TO_PHYS(m);
2426         vm_pindex_t start = pa >> PAGE_SHIFT;
2427         vm_pindex_t pages = (size + PAGE_MASK) >> PAGE_SHIFT;
2428
2429         if (vm_contig_verbose) {
2430                 kprintf("vm_page_free_contig:  %016jx/%ldk\n",
2431                         (intmax_t)pa, size / 1024);
2432         }
2433         if (pa < vm_low_phys_reserved) {
2434                 KKASSERT(pa + size <= vm_low_phys_reserved);
2435                 spin_lock(&vm_contig_spin);
2436                 alist_free(&vm_contig_alist, start, pages);
2437                 spin_unlock(&vm_contig_spin);
2438         } else {
2439                 while (pages) {
2440                         vm_page_busy_wait(m, FALSE, "cpgfr");
2441                         vm_page_unwire(m, 0);
2442                         vm_page_free(m);
2443                         --pages;
2444                         ++m;
2445                 }
2446
2447         }
2448 }
2449
2450
2451 /*
2452  * Wait for sufficient free memory for nominal heavy memory use kernel
2453  * operations.
2454  *
2455  * WARNING!  Be sure never to call this in any vm_pageout code path, which
2456  *           will trivially deadlock the system.
2457  */
2458 void
2459 vm_wait_nominal(void)
2460 {
2461         while (vm_page_count_min(0))
2462                 vm_wait(0);
2463 }
2464
2465 /*
2466  * Test if vm_wait_nominal() would block.
2467  */
2468 int
2469 vm_test_nominal(void)
2470 {
2471         if (vm_page_count_min(0))
2472                 return(1);
2473         return(0);
2474 }
2475
2476 /*
2477  * Block until free pages are available for allocation, called in various
2478  * places before memory allocations.
2479  *
2480  * The caller may loop if vm_page_count_min() == FALSE so we cannot be
2481  * more generous then that.
2482  */
2483 void
2484 vm_wait(int timo)
2485 {
2486         /*
2487          * never wait forever
2488          */
2489         if (timo == 0)
2490                 timo = hz;
2491         lwkt_gettoken(&vm_token);
2492
2493         if (curthread == pagethread ||
2494             curthread == emergpager) {
2495                 /*
2496                  * The pageout daemon itself needs pages, this is bad.
2497                  */
2498                 if (vm_page_count_min(0)) {
2499                         vm_pageout_pages_needed = 1;
2500                         tsleep(&vm_pageout_pages_needed, 0, "VMWait", timo);
2501                 }
2502         } else {
2503                 /*
2504                  * Wakeup the pageout daemon if necessary and wait.
2505                  *
2506                  * Do not wait indefinitely for the target to be reached,
2507                  * as load might prevent it from being reached any time soon.
2508                  * But wait a little to try to slow down page allocations
2509                  * and to give more important threads (the pagedaemon)
2510                  * allocation priority.
2511                  */
2512                 if (vm_page_count_target()) {
2513                         if (vm_pages_needed == 0) {
2514                                 vm_pages_needed = 1;
2515                                 wakeup(&vm_pages_needed);
2516                         }
2517                         ++vm_pages_waiting;     /* SMP race ok */
2518                         tsleep(&vmstats.v_free_count, 0, "vmwait", timo);
2519                 }
2520         }
2521         lwkt_reltoken(&vm_token);
2522 }
2523
2524 /*
2525  * Block until free pages are available for allocation
2526  *
2527  * Called only from vm_fault so that processes page faulting can be
2528  * easily tracked.
2529  */
2530 void
2531 vm_wait_pfault(void)
2532 {
2533         /*
2534          * Wakeup the pageout daemon if necessary and wait.
2535          *
2536          * Do not wait indefinitely for the target to be reached,
2537          * as load might prevent it from being reached any time soon.
2538          * But wait a little to try to slow down page allocations
2539          * and to give more important threads (the pagedaemon)
2540          * allocation priority.
2541          */
2542         if (vm_page_count_min(0)) {
2543                 lwkt_gettoken(&vm_token);
2544                 while (vm_page_count_severe()) {
2545                         if (vm_page_count_target()) {
2546                                 thread_t td;
2547
2548                                 if (vm_pages_needed == 0) {
2549                                         vm_pages_needed = 1;
2550                                         wakeup(&vm_pages_needed);
2551                                 }
2552                                 ++vm_pages_waiting;     /* SMP race ok */
2553                                 tsleep(&vmstats.v_free_count, 0, "pfault", hz);
2554
2555                                 /*
2556                                  * Do not stay stuck in the loop if the system is trying
2557                                  * to kill the process.
2558                                  */
2559                                 td = curthread;
2560                                 if (td->td_proc && (td->td_proc->p_flags & P_LOWMEMKILL))
2561                                         break;
2562                         }
2563                 }
2564                 lwkt_reltoken(&vm_token);
2565         }
2566 }
2567
2568 /*
2569  * Put the specified page on the active list (if appropriate).  Ensure
2570  * that act_count is at least ACT_INIT but do not otherwise mess with it.
2571  *
2572  * The caller should be holding the page busied ? XXX
2573  * This routine may not block.
2574  */
2575 void
2576 vm_page_activate(vm_page_t m)
2577 {
2578         u_short oqueue;
2579
2580         vm_page_spin_lock(m);
2581         if (m->queue - m->pc != PQ_ACTIVE && !(m->flags & PG_FICTITIOUS)) {
2582                 _vm_page_queue_spin_lock(m);
2583                 oqueue = _vm_page_rem_queue_spinlocked(m);
2584                 /* page is left spinlocked, queue is unlocked */
2585
2586                 if (oqueue == PQ_CACHE)
2587                         mycpu->gd_cnt.v_reactivated++;
2588                 if ((m->flags & PG_UNMANAGED) == 0) {
2589                         if (m->act_count < ACT_INIT)
2590                                 m->act_count = ACT_INIT;
2591                         _vm_page_add_queue_spinlocked(m, PQ_ACTIVE + m->pc, 0);
2592                 }
2593                 _vm_page_and_queue_spin_unlock(m);
2594                 if (oqueue == PQ_CACHE || oqueue == PQ_FREE)
2595                         pagedaemon_wakeup();
2596         } else {
2597                 if (m->act_count < ACT_INIT)
2598                         m->act_count = ACT_INIT;
2599                 vm_page_spin_unlock(m);
2600         }
2601 }
2602
2603 void
2604 vm_page_soft_activate(vm_page_t m)
2605 {
2606         if (m->queue - m->pc == PQ_ACTIVE || (m->flags & PG_FICTITIOUS)) {
2607                 if (m->act_count < ACT_INIT)
2608                         m->act_count = ACT_INIT;
2609         } else {
2610                 vm_page_activate(m);
2611         }
2612 }
2613
2614 /*
2615  * Helper routine for vm_page_free_toq() and vm_page_cache().  This
2616  * routine is called when a page has been added to the cache or free
2617  * queues.
2618  *
2619  * This routine may not block.
2620  */
2621 static __inline void
2622 vm_page_free_wakeup(void)
2623 {
2624         globaldata_t gd = mycpu;
2625
2626         /*
2627          * If the pageout daemon itself needs pages, then tell it that
2628          * there are some free.
2629          */
2630         if (vm_pageout_pages_needed &&
2631             gd->gd_vmstats.v_cache_count + gd->gd_vmstats.v_free_count >=
2632             gd->gd_vmstats.v_pageout_free_min
2633         ) {
2634                 vm_pageout_pages_needed = 0;
2635                 wakeup(&vm_pageout_pages_needed);
2636         }
2637
2638         /*
2639          * Wakeup processes that are waiting on memory.
2640          *
2641          * Generally speaking we want to wakeup stuck processes as soon as
2642          * possible.  !vm_page_count_min(0) is the absolute minimum point
2643          * where we can do this.  Wait a bit longer to reduce degenerate
2644          * re-blocking (vm_page_free_hysteresis).  The target check is just
2645          * to make sure the min-check w/hysteresis does not exceed the
2646          * normal target.
2647          */
2648         if (vm_pages_waiting) {
2649                 if (!vm_page_count_min(vm_page_free_hysteresis) ||
2650                     !vm_page_count_target()) {
2651                         vm_pages_waiting = 0;
2652                         wakeup(&vmstats.v_free_count);
2653                         ++mycpu->gd_cnt.v_ppwakeups;
2654                 }
2655 #if 0
2656                 if (!vm_page_count_target()) {
2657                         /*
2658                          * Plenty of pages are free, wakeup everyone.
2659                          */
2660                         vm_pages_waiting = 0;
2661                         wakeup(&vmstats.v_free_count);
2662                         ++mycpu->gd_cnt.v_ppwakeups;
2663                 } else if (!vm_page_count_min(0)) {
2664                         /*
2665                          * Some pages are free, wakeup someone.
2666                          */
2667                         int wcount = vm_pages_waiting;
2668                         if (wcount > 0)
2669                                 --wcount;
2670                         vm_pages_waiting = wcount;
2671                         wakeup_one(&vmstats.v_free_count);
2672                         ++mycpu->gd_cnt.v_ppwakeups;
2673                 }
2674 #endif
2675         }
2676 }
2677
2678 /*
2679  * Returns the given page to the PQ_FREE or PQ_HOLD list and disassociates
2680  * it from its VM object.
2681  *
2682  * The vm_page must be BUSY on entry.  BUSY will be released on
2683  * return (the page will have been freed).
2684  */
2685 void
2686 vm_page_free_toq(vm_page_t m)
2687 {
2688         mycpu->gd_cnt.v_tfree++;
2689         if (m->flags & (PG_MAPPED | PG_WRITEABLE))
2690                 pmap_mapped_sync(m);
2691         KKASSERT((m->flags & PG_MAPPED) == 0);
2692         KKASSERT(m->busy_count & PBUSY_LOCKED);
2693
2694         if ((m->busy_count & PBUSY_MASK) || ((m->queue - m->pc) == PQ_FREE)) {
2695                 kprintf("vm_page_free: pindex(%lu), busy %08x, "
2696                         "hold(%d)\n",
2697                         (u_long)m->pindex, m->busy_count, m->hold_count);
2698                 if ((m->queue - m->pc) == PQ_FREE)
2699                         panic("vm_page_free: freeing free page");
2700                 else
2701                         panic("vm_page_free: freeing busy page");
2702         }
2703
2704         /*
2705          * Remove from object, spinlock the page and its queues and
2706          * remove from any queue.  No queue spinlock will be held
2707          * after this section (because the page was removed from any
2708          * queue).
2709          */
2710         vm_page_remove(m);
2711
2712         /*
2713          * No further management of fictitious pages occurs beyond object
2714          * and queue removal.
2715          */
2716         if ((m->flags & PG_FICTITIOUS) != 0) {
2717                 KKASSERT(m->queue == PQ_NONE);
2718                 vm_page_wakeup(m);
2719                 return;
2720         }
2721         vm_page_and_queue_spin_lock(m);
2722         _vm_page_rem_queue_spinlocked(m);
2723
2724         m->valid = 0;
2725         vm_page_undirty(m);
2726
2727         if (m->wire_count != 0) {
2728                 if (m->wire_count > 1) {
2729                     panic(
2730                         "vm_page_free: invalid wire count (%d), pindex: 0x%lx",
2731                         m->wire_count, (long)m->pindex);
2732                 }
2733                 panic("vm_page_free: freeing wired page");
2734         }
2735
2736         /*
2737          * Clear the UNMANAGED flag when freeing an unmanaged page.
2738          * Clear the NEED_COMMIT flag
2739          */
2740         if (m->flags & PG_UNMANAGED)
2741                 vm_page_flag_clear(m, PG_UNMANAGED);
2742         if (m->flags & PG_NEED_COMMIT)
2743                 vm_page_flag_clear(m, PG_NEED_COMMIT);
2744
2745         if (m->hold_count != 0) {
2746                 _vm_page_add_queue_spinlocked(m, PQ_HOLD + m->pc, 0);
2747         } else {
2748                 _vm_page_add_queue_spinlocked(m, PQ_FREE + m->pc, 1);
2749         }
2750
2751         /*
2752          * This sequence allows us to clear BUSY while still holding
2753          * its spin lock, which reduces contention vs allocators.  We
2754          * must not leave the queue locked or _vm_page_wakeup() may
2755          * deadlock.
2756          */
2757         _vm_page_queue_spin_unlock(m);
2758         if (_vm_page_wakeup(m)) {
2759                 vm_page_spin_unlock(m);
2760                 wakeup(m);
2761         } else {
2762                 vm_page_spin_unlock(m);
2763         }
2764         vm_page_free_wakeup();
2765 }
2766
2767 /*
2768  * vm_page_unmanage()
2769  *
2770  * Prevent PV management from being done on the page.  The page is
2771  * also removed from the paging queues, and as a consequence of no longer
2772  * being managed the pageout daemon will not touch it (since there is no
2773  * way to locate the pte mappings for the page).  madvise() calls that
2774  * mess with the pmap will also no longer operate on the page.
2775  *
2776  * Beyond that the page is still reasonably 'normal'.  Freeing the page
2777  * will clear the flag.
2778  *
2779  * This routine is used by OBJT_PHYS objects - objects using unswappable
2780  * physical memory as backing store rather then swap-backed memory and
2781  * will eventually be extended to support 4MB unmanaged physical 
2782  * mappings.
2783  *
2784  * Caller must be holding the page busy.
2785  */
2786 void
2787 vm_page_unmanage(vm_page_t m)
2788 {
2789         KKASSERT(m->busy_count & PBUSY_LOCKED);
2790         if ((m->flags & PG_UNMANAGED) == 0) {
2791                 vm_page_unqueue(m);
2792         }
2793         vm_page_flag_set(m, PG_UNMANAGED);
2794 }
2795
2796 /*
2797  * Mark this page as wired down by yet another map.  We do not adjust the
2798  * queue the page is on, it will be checked for wiring as-needed.
2799  *
2800  * Caller must be holding the page busy.
2801  */
2802 void
2803 vm_page_wire(vm_page_t m)
2804 {
2805         /*
2806          * Only bump the wire statistics if the page is not already wired,
2807          * and only unqueue the page if it is on some queue (if it is unmanaged
2808          * it is already off the queues).  Don't do anything with fictitious
2809          * pages because they are always wired.
2810          */
2811         KKASSERT(m->busy_count & PBUSY_LOCKED);
2812         if ((m->flags & PG_FICTITIOUS) == 0) {
2813                 if (atomic_fetchadd_int(&m->wire_count, 1) == 0) {
2814                         atomic_add_long(&mycpu->gd_vmstats_adj.v_wire_count, 1);
2815                 }
2816                 KASSERT(m->wire_count != 0,
2817                         ("vm_page_wire: wire_count overflow m=%p", m));
2818         }
2819 }
2820
2821 /*
2822  * Release one wiring of this page, potentially enabling it to be paged again.
2823  *
2824  * Note that wired pages are no longer unconditionally removed from the
2825  * paging queues, so the page may already be on a queue.  Move the page
2826  * to the desired queue if necessary.
2827  *
2828  * Many pages placed on the inactive queue should actually go
2829  * into the cache, but it is difficult to figure out which.  What
2830  * we do instead, if the inactive target is well met, is to put
2831  * clean pages at the head of the inactive queue instead of the tail.
2832  * This will cause them to be moved to the cache more quickly and
2833  * if not actively re-referenced, freed more quickly.  If we just
2834  * stick these pages at the end of the inactive queue, heavy filesystem
2835  * meta-data accesses can cause an unnecessary paging load on memory bound 
2836  * processes.  This optimization causes one-time-use metadata to be
2837  * reused more quickly.
2838  *
2839  * Pages marked PG_NEED_COMMIT are always activated and never placed on
2840  * the inactive queue.  This helps the pageout daemon determine memory
2841  * pressure and act on out-of-memory situations more quickly.
2842  *
2843  * BUT, if we are in a low-memory situation we have no choice but to
2844  * put clean pages on the cache queue.
2845  *
2846  * A number of routines use vm_page_unwire() to guarantee that the page
2847  * will go into either the inactive or active queues, and will NEVER
2848  * be placed in the cache - for example, just after dirtying a page.
2849  * dirty pages in the cache are not allowed.
2850  *
2851  * This routine may not block.
2852  */
2853 void
2854 vm_page_unwire(vm_page_t m, int activate)
2855 {
2856         KKASSERT(m->busy_count & PBUSY_LOCKED);
2857         if (m->flags & PG_FICTITIOUS) {
2858                 /* do nothing */
2859         } else if ((int)m->wire_count <= 0) {
2860                 panic("vm_page_unwire: invalid wire count: %d", m->wire_count);
2861         } else {
2862                 if (atomic_fetchadd_int(&m->wire_count, -1) == 1) {
2863                         atomic_add_long(&mycpu->gd_vmstats_adj.v_wire_count,-1);
2864                         if (m->flags & PG_UNMANAGED) {
2865                                 ;
2866                         } else if (activate || (m->flags & PG_NEED_COMMIT)) {
2867                                 vm_page_activate(m);
2868                         } else {
2869                                 vm_page_deactivate(m);
2870                         }
2871                 }
2872         }
2873 }
2874
2875 /*
2876  * Move the specified page to the inactive queue.
2877  *
2878  * Normally athead is 0 resulting in LRU operation.  athead is set
2879  * to 1 if we want this page to be 'as if it were placed in the cache',
2880  * except without unmapping it from the process address space.
2881  *
2882  * vm_page's spinlock must be held on entry and will remain held on return.
2883  * This routine may not block.  The caller does not have to hold the page
2884  * busied but should have some sort of interlock on its validity.
2885  */
2886 static void
2887 _vm_page_deactivate_locked(vm_page_t m, int athead)
2888 {
2889         u_short oqueue;
2890
2891         /*
2892          * Ignore if already inactive.
2893          */
2894         if (m->queue - m->pc == PQ_INACTIVE || (m->flags & PG_FICTITIOUS))
2895                 return;
2896         _vm_page_queue_spin_lock(m);
2897         oqueue = _vm_page_rem_queue_spinlocked(m);
2898
2899         if ((m->flags & PG_UNMANAGED) == 0) {
2900                 if (oqueue == PQ_CACHE)
2901                         mycpu->gd_cnt.v_reactivated++;
2902                 vm_page_flag_clear(m, PG_WINATCFLS);
2903                 _vm_page_add_queue_spinlocked(m, PQ_INACTIVE + m->pc, athead);
2904                 if (athead == 0) {
2905                         atomic_add_long(
2906                                 &vm_page_queues[PQ_INACTIVE + m->pc].adds, 1);
2907                 }
2908         }
2909         /* NOTE: PQ_NONE if condition not taken */
2910         _vm_page_queue_spin_unlock(m);
2911         /* leaves vm_page spinlocked */
2912 }
2913
2914 /*
2915  * Attempt to deactivate a page.
2916  *
2917  * No requirements.
2918  */
2919 void
2920 vm_page_deactivate(vm_page_t m)
2921 {
2922         vm_page_spin_lock(m);
2923         _vm_page_deactivate_locked(m, 0);
2924         vm_page_spin_unlock(m);
2925 }
2926
2927 void
2928 vm_page_deactivate_locked(vm_page_t m)
2929 {
2930         _vm_page_deactivate_locked(m, 0);
2931 }
2932
2933 /*
2934  * Attempt to move a busied page to PQ_CACHE, then unconditionally unbusy it.
2935  *
2936  * This function returns non-zero if it successfully moved the page to
2937  * PQ_CACHE.
2938  *
2939  * This function unconditionally unbusies the page on return.
2940  */
2941 int
2942 vm_page_try_to_cache(vm_page_t m)
2943 {
2944         /*
2945          * Shortcut if we obviously cannot move the page, or if the
2946          * page is already on the cache queue, or it is ficitious.
2947          */
2948         if (m->dirty || m->hold_count || m->wire_count ||
2949             m->queue - m->pc == PQ_CACHE ||
2950             (m->flags & (PG_UNMANAGED | PG_NEED_COMMIT | PG_FICTITIOUS))) {
2951                 vm_page_wakeup(m);
2952                 return(0);
2953         }
2954
2955         /*
2956          * Page busied by us and no longer spinlocked.  Dirty pages cannot
2957          * be moved to the cache.
2958          */
2959         vm_page_test_dirty(m);
2960         if (m->dirty || (m->flags & PG_NEED_COMMIT)) {
2961                 vm_page_wakeup(m);
2962                 return(0);
2963         }
2964         vm_page_cache(m);
2965         return(1);
2966 }
2967
2968 /*
2969  * Attempt to free the page.  If we cannot free it, we do nothing.
2970  * 1 is returned on success, 0 on failure.
2971  *
2972  * Caller provides an unlocked/non-busied page.
2973  * No requirements.
2974  */
2975 int
2976 vm_page_try_to_free(vm_page_t m)
2977 {
2978         if (vm_page_busy_try(m, TRUE))
2979                 return(0);
2980
2981         /*
2982          * The page can be in any state, including already being on the free
2983          * queue.  Check to see if it really can be freed.
2984          */
2985         if (m->dirty ||                         /* can't free if it is dirty */
2986             m->hold_count ||                    /* or held (XXX may be wrong) */
2987             m->wire_count ||                    /* or wired */
2988             (m->flags & (PG_UNMANAGED |         /* or unmanaged */
2989                          PG_NEED_COMMIT |       /* or needs a commit */
2990                          PG_FICTITIOUS)) ||     /* or is fictitious */
2991             m->queue - m->pc == PQ_FREE ||      /* already on PQ_FREE */
2992             m->queue - m->pc == PQ_HOLD) {      /* already on PQ_HOLD */
2993                 vm_page_wakeup(m);
2994                 return(0);
2995         }
2996
2997         /*
2998          * We can probably free the page.
2999          *
3000          * Page busied by us and no longer spinlocked.  Dirty pages will
3001          * not be freed by this function.    We have to re-test the
3002          * dirty bit after cleaning out the pmaps.
3003          */
3004         vm_page_test_dirty(m);
3005         if (m->dirty || (m->flags & PG_NEED_COMMIT)) {
3006                 vm_page_wakeup(m);
3007                 return(0);
3008         }
3009         vm_page_protect(m, VM_PROT_NONE);
3010         if (m->dirty || (m->flags & PG_NEED_COMMIT)) {
3011                 vm_page_wakeup(m);
3012                 return(0);
3013         }
3014         vm_page_free(m);
3015         return(1);
3016 }
3017
3018 /*
3019  * vm_page_cache
3020  *
3021  * Put the specified page onto the page cache queue (if appropriate).
3022  *
3023  * The page must be busy, and this routine will release the busy and
3024  * possibly even free the page.
3025  */
3026 void
3027 vm_page_cache(vm_page_t m)
3028 {
3029         /*
3030          * Not suitable for the cache
3031          */
3032         if ((m->flags & (PG_UNMANAGED | PG_NEED_COMMIT | PG_FICTITIOUS)) ||
3033             (m->busy_count & PBUSY_MASK) ||
3034             m->wire_count || m->hold_count) {
3035                 vm_page_wakeup(m);
3036                 return;
3037         }
3038
3039         /*
3040          * Already in the cache (and thus not mapped)
3041          */
3042         if ((m->queue - m->pc) == PQ_CACHE) {
3043                 if (m->flags & (PG_MAPPED | PG_WRITEABLE))
3044                         pmap_mapped_sync(m);
3045                 KKASSERT((m->flags & PG_MAPPED) == 0);
3046                 vm_page_wakeup(m);
3047                 return;
3048         }
3049
3050 #if 0
3051         /*
3052          * REMOVED - it is possible for dirty to get set at any time as
3053          *           long as the page is still mapped and writeable.
3054          *
3055          * Caller is required to test m->dirty, but note that the act of
3056          * removing the page from its maps can cause it to become dirty
3057          * on an SMP system due to another cpu running in usermode.
3058          */
3059         if (m->dirty) {
3060                 panic("vm_page_cache: caching a dirty page, pindex: %ld",
3061                         (long)m->pindex);
3062         }
3063 #endif
3064
3065         /*
3066          * Remove all pmaps and indicate that the page is not
3067          * writeable or mapped.  Our vm_page_protect() call may
3068          * have blocked (especially w/ VM_PROT_NONE), so recheck
3069          * everything.
3070          */
3071         vm_page_protect(m, VM_PROT_NONE);
3072         pmap_mapped_sync(m);
3073         if ((m->flags & (PG_UNMANAGED | PG_MAPPED)) ||
3074             (m->busy_count & PBUSY_MASK) ||
3075             m->wire_count || m->hold_count) {
3076                 vm_page_wakeup(m);
3077         } else if (m->dirty || (m->flags & PG_NEED_COMMIT)) {
3078                 vm_page_deactivate(m);
3079                 vm_page_wakeup(m);
3080         } else {
3081                 _vm_page_and_queue_spin_lock(m);
3082                 _vm_page_rem_queue_spinlocked(m);
3083                 _vm_page_add_queue_spinlocked(m, PQ_CACHE + m->pc, 0);
3084                 _vm_page_and_queue_spin_unlock(m);
3085                 vm_page_wakeup(m);
3086                 vm_page_free_wakeup();
3087         }
3088 }
3089
3090 /*
3091  * vm_page_dontneed()
3092  *
3093  * Cache, deactivate, or do nothing as appropriate.  This routine
3094  * is typically used by madvise() MADV_DONTNEED.
3095  *
3096  * Generally speaking we want to move the page into the cache so
3097  * it gets reused quickly.  However, this can result in a silly syndrome
3098  * due to the page recycling too quickly.  Small objects will not be
3099  * fully cached.  On the otherhand, if we move the page to the inactive
3100  * queue we wind up with a problem whereby very large objects 
3101  * unnecessarily blow away our inactive and cache queues.
3102  *
3103  * The solution is to move the pages based on a fixed weighting.  We
3104  * either leave them alone, deactivate them, or move them to the cache,
3105  * where moving them to the cache has the highest weighting.
3106  * By forcing some pages into other queues we eventually force the
3107  * system to balance the queues, potentially recovering other unrelated
3108  * space from active.  The idea is to not force this to happen too
3109  * often.
3110  *
3111  * The page must be busied.
3112  */
3113 void
3114 vm_page_dontneed(vm_page_t m)
3115 {
3116         static int dnweight;
3117         int dnw;
3118         int head;
3119
3120         dnw = ++dnweight;
3121
3122         /*
3123          * occassionally leave the page alone
3124          */
3125         if ((dnw & 0x01F0) == 0 ||
3126             m->queue - m->pc == PQ_INACTIVE ||
3127             m->queue - m->pc == PQ_CACHE
3128         ) {
3129                 if (m->act_count >= ACT_INIT)
3130                         --m->act_count;
3131                 return;
3132         }
3133
3134         /*
3135          * If vm_page_dontneed() is inactivating a page, it must clear
3136          * the referenced flag; otherwise the pagedaemon will see references
3137          * on the page in the inactive queue and reactivate it. Until the 
3138          * page can move to the cache queue, madvise's job is not done.
3139          */
3140         vm_page_flag_clear(m, PG_REFERENCED);
3141         pmap_clear_reference(m);
3142
3143         if (m->dirty == 0)
3144                 vm_page_test_dirty(m);
3145
3146         if (m->dirty || (dnw & 0x0070) == 0) {
3147                 /*
3148                  * Deactivate the page 3 times out of 32.
3149                  */
3150                 head = 0;
3151         } else {
3152                 /*
3153                  * Cache the page 28 times out of every 32.  Note that
3154                  * the page is deactivated instead of cached, but placed
3155                  * at the head of the queue instead of the tail.
3156                  */
3157                 head = 1;
3158         }
3159         vm_page_spin_lock(m);
3160         _vm_page_deactivate_locked(m, head);
3161         vm_page_spin_unlock(m);
3162 }
3163
3164 /*
3165  * These routines manipulate the 'soft busy' count for a page.  A soft busy
3166  * is almost like a hard BUSY except that it allows certain compatible
3167  * operations to occur on the page while it is busy.  For example, a page
3168  * undergoing a write can still be mapped read-only.
3169  *
3170  * We also use soft-busy to quickly pmap_enter shared read-only pages
3171  * without having to hold the page locked.
3172  *
3173  * The soft-busy count can be > 1 in situations where multiple threads
3174  * are pmap_enter()ing the same page simultaneously, or when two buffer
3175  * cache buffers overlap the same page.
3176  *
3177  * The caller must hold the page BUSY when making these two calls.
3178  */
3179 void
3180 vm_page_io_start(vm_page_t m)
3181 {
3182         uint32_t ocount;
3183
3184         ocount = atomic_fetchadd_int(&m->busy_count, 1);
3185         KKASSERT(ocount & PBUSY_LOCKED);
3186 }
3187
3188 void
3189 vm_page_io_finish(vm_page_t m)
3190 {
3191         uint32_t ocount;
3192
3193         ocount = atomic_fetchadd_int(&m->busy_count, -1);
3194         KKASSERT(ocount & PBUSY_MASK);
3195 #if 0
3196         if (((ocount - 1) & (PBUSY_LOCKED | PBUSY_MASK)) == 0)
3197                 wakeup(m);
3198 #endif
3199 }
3200
3201 /*
3202  * Attempt to soft-busy a page.  The page must not be PBUSY_LOCKED.
3203  *
3204  * We can't use fetchadd here because we might race a hard-busy and the
3205  * page freeing code asserts on a non-zero soft-busy count (even if only
3206  * temporary).
3207  *
3208  * Returns 0 on success, non-zero on failure.
3209  */
3210 int
3211 vm_page_sbusy_try(vm_page_t m)
3212 {
3213         uint32_t ocount;
3214
3215         for (;;) {
3216                 ocount = m->busy_count;
3217                 cpu_ccfence();
3218                 if (ocount & PBUSY_LOCKED)
3219                         return 1;
3220                 if (atomic_cmpset_int(&m->busy_count, ocount, ocount + 1))
3221                         break;
3222         }
3223         return 0;
3224 #if 0
3225         if (m->busy_count & PBUSY_LOCKED)
3226                 return 1;
3227         ocount = atomic_fetchadd_int(&m->busy_count, 1);
3228         if (ocount & PBUSY_LOCKED) {
3229                 vm_page_sbusy_drop(m);
3230                 return 1;
3231         }
3232         return 0;
3233 #endif
3234 }
3235
3236 /*
3237  * Indicate that a clean VM page requires a filesystem commit and cannot
3238  * be reused.  Used by tmpfs.
3239  */
3240 void
3241 vm_page_need_commit(vm_page_t m)
3242 {
3243         vm_page_flag_set(m, PG_NEED_COMMIT);
3244         vm_object_set_writeable_dirty(m->object);
3245 }
3246
3247 void
3248 vm_page_clear_commit(vm_page_t m)
3249 {
3250         vm_page_flag_clear(m, PG_NEED_COMMIT);
3251 }
3252
3253 /*
3254  * Grab a page, blocking if it is busy and allocating a page if necessary.
3255  * A busy page is returned or NULL.  The page may or may not be valid and
3256  * might not be on a queue (the caller is responsible for the disposition of
3257  * the page).
3258  *
3259  * If VM_ALLOC_ZERO is specified and the grab must allocate a new page, the
3260  * page will be zero'd and marked valid.
3261  *
3262  * If VM_ALLOC_FORCE_ZERO is specified the page will be zero'd and marked
3263  * valid even if it already exists.
3264  *
3265  * If VM_ALLOC_RETRY is specified this routine will never return NULL.  Also
3266  * note that VM_ALLOC_NORMAL must be specified if VM_ALLOC_RETRY is specified.
3267  * VM_ALLOC_NULL_OK is implied when VM_ALLOC_RETRY is specified.
3268  *
3269  * This routine may block, but if VM_ALLOC_RETRY is not set then NULL is
3270  * always returned if we had blocked.  
3271  *
3272  * This routine may not be called from an interrupt.
3273  *
3274  * No other requirements.
3275  */
3276 vm_page_t
3277 vm_page_grab(vm_object_t object, vm_pindex_t pindex, int allocflags)
3278 {
3279         vm_page_t m;
3280         int error;
3281         int shared = 1;
3282
3283         KKASSERT(allocflags &
3284                 (VM_ALLOC_NORMAL|VM_ALLOC_INTERRUPT|VM_ALLOC_SYSTEM));
3285         vm_object_hold_shared(object);
3286         for (;;) {
3287                 m = vm_page_lookup_busy_try(object, pindex, TRUE, &error);
3288                 if (error) {
3289                         vm_page_sleep_busy(m, TRUE, "pgrbwt");
3290                         if ((allocflags & VM_ALLOC_RETRY) == 0) {
3291                                 m = NULL;
3292                                 break;
3293                         }
3294                         /* retry */
3295                 } else if (m == NULL) {
3296                         if (shared) {
3297                                 vm_object_upgrade(object);
3298                                 shared = 0;
3299                         }
3300                         if (allocflags & VM_ALLOC_RETRY)
3301                                 allocflags |= VM_ALLOC_NULL_OK;
3302                         m = vm_page_alloc(object, pindex,
3303                                           allocflags & ~VM_ALLOC_RETRY);
3304                         if (m)
3305                                 break;
3306                         vm_wait(0);
3307                         if ((allocflags & VM_ALLOC_RETRY) == 0)
3308                                 goto failed;
3309                 } else {
3310                         /* m found */
3311                         break;
3312                 }
3313         }
3314
3315         /*
3316          * If VM_ALLOC_ZERO an invalid page will be zero'd and set valid.
3317          *
3318          * If VM_ALLOC_FORCE_ZERO the page is unconditionally zero'd and set
3319          * valid even if already valid.
3320          *
3321          * NOTE!  We have removed all of the PG_ZERO optimizations and also
3322          *        removed the idle zeroing code.  These optimizations actually
3323          *        slow things down on modern cpus because the zerod area is
3324          *        likely uncached, placing a memory-access burden on the
3325          *        accesors taking the fault.
3326          *
3327          *        By always zeroing the page in-line with the fault, no
3328          *        dynamic ram reads are needed and the caches are hot, ready
3329          *        for userland to access the memory.
3330          */
3331         if (m->valid == 0) {
3332                 if (allocflags & (VM_ALLOC_ZERO | VM_ALLOC_FORCE_ZERO)) {
3333                         pmap_zero_page(VM_PAGE_TO_PHYS(m));
3334                         m->valid = VM_PAGE_BITS_ALL;
3335                 }
3336         } else if (allocflags & VM_ALLOC_FORCE_ZERO) {
3337                 pmap_zero_page(VM_PAGE_TO_PHYS(m));
3338                 m->valid = VM_PAGE_BITS_ALL;
3339         }
3340 failed:
3341         vm_object_drop(object);
3342         return(m);
3343 }
3344
3345 /*
3346  * Mapping function for valid bits or for dirty bits in
3347  * a page.  May not block.
3348  *
3349  * Inputs are required to range within a page.
3350  *
3351  * No requirements.
3352  * Non blocking.
3353  */
3354 int
3355 vm_page_bits(int base, int size)
3356 {
3357         int first_bit;
3358         int last_bit;
3359
3360         KASSERT(
3361             base + size <= PAGE_SIZE,
3362             ("vm_page_bits: illegal base/size %d/%d", base, size)
3363         );
3364
3365         if (size == 0)          /* handle degenerate case */
3366                 return(0);
3367
3368         first_bit = base >> DEV_BSHIFT;
3369         last_bit = (base + size - 1) >> DEV_BSHIFT;
3370
3371         return ((2 << last_bit) - (1 << first_bit));
3372 }
3373
3374 /*
3375  * Sets portions of a page valid and clean.  The arguments are expected
3376  * to be DEV_BSIZE aligned but if they aren't the bitmap is inclusive
3377  * of any partial chunks touched by the range.  The invalid portion of
3378  * such chunks will be zero'd.
3379  *
3380  * NOTE: When truncating a buffer vnode_pager_setsize() will automatically
3381  *       align base to DEV_BSIZE so as not to mark clean a partially
3382  *       truncated device block.  Otherwise the dirty page status might be
3383  *       lost.
3384  *
3385  * This routine may not block.
3386  *
3387  * (base + size) must be less then or equal to PAGE_SIZE.
3388  */
3389 static void
3390 _vm_page_zero_valid(vm_page_t m, int base, int size)
3391 {
3392         int frag;
3393         int endoff;
3394
3395         if (size == 0)  /* handle degenerate case */
3396                 return;
3397
3398         /*
3399          * If the base is not DEV_BSIZE aligned and the valid
3400          * bit is clear, we have to zero out a portion of the
3401          * first block.
3402          */
3403
3404         if ((frag = base & ~(DEV_BSIZE - 1)) != base &&
3405             (m->valid & (1 << (base >> DEV_BSHIFT))) == 0
3406         ) {
3407                 pmap_zero_page_area(
3408                     VM_PAGE_TO_PHYS(m),
3409                     frag,
3410                     base - frag
3411                 );
3412         }
3413
3414         /*
3415          * If the ending offset is not DEV_BSIZE aligned and the 
3416          * valid bit is clear, we have to zero out a portion of
3417          * the last block.
3418          */
3419
3420         endoff = base + size;
3421
3422         if ((frag = endoff & ~(DEV_BSIZE - 1)) != endoff &&
3423             (m->valid & (1 << (endoff >> DEV_BSHIFT))) == 0
3424         ) {
3425                 pmap_zero_page_area(
3426                     VM_PAGE_TO_PHYS(m),
3427                     endoff,
3428                     DEV_BSIZE - (endoff & (DEV_BSIZE - 1))
3429                 );
3430         }
3431 }
3432
3433 /*
3434  * Set valid, clear dirty bits.  If validating the entire
3435  * page we can safely clear the pmap modify bit.  We also
3436  * use this opportunity to clear the PG_NOSYNC flag.  If a process
3437  * takes a write fault on a MAP_NOSYNC memory area the flag will
3438  * be set again.
3439  *
3440  * We set valid bits inclusive of any overlap, but we can only
3441  * clear dirty bits for DEV_BSIZE chunks that are fully within
3442  * the range.
3443  *
3444  * Page must be busied?
3445  * No other requirements.
3446  */
3447 void
3448 vm_page_set_valid(vm_page_t m, int base, int size)
3449 {
3450         _vm_page_zero_valid(m, base, size);
3451         m->valid |= vm_page_bits(base, size);
3452 }
3453
3454
3455 /*
3456  * Set valid bits and clear dirty bits.
3457  *
3458  * Page must be busied by caller.
3459  *
3460  * NOTE: This function does not clear the pmap modified bit.
3461  *       Also note that e.g. NFS may use a byte-granular base
3462  *       and size.
3463  *
3464  * No other requirements.
3465  */
3466 void
3467 vm_page_set_validclean(vm_page_t m, int base, int size)
3468 {
3469         int pagebits;
3470
3471         _vm_page_zero_valid(m, base, size);
3472         pagebits = vm_page_bits(base, size);
3473         m->valid |= pagebits;
3474         m->dirty &= ~pagebits;
3475         if (base == 0 && size == PAGE_SIZE) {
3476                 /*pmap_clear_modify(m);*/
3477                 vm_page_flag_clear(m, PG_NOSYNC);
3478         }
3479 }
3480
3481 /*
3482  * Set valid & dirty.  Used by buwrite()
3483  *
3484  * Page must be busied by caller.
3485  */
3486 void
3487 vm_page_set_validdirty(vm_page_t m, int base, int size)
3488 {
3489         int pagebits;
3490
3491         pagebits = vm_page_bits(base, size);
3492         m->valid |= pagebits;
3493         m->dirty |= pagebits;
3494         if (m->object)
3495                vm_object_set_writeable_dirty(m->object);
3496 }
3497
3498 /*
3499  * Clear dirty bits.
3500  *
3501  * NOTE: This function does not clear the pmap modified bit.
3502  *       Also note that e.g. NFS may use a byte-granular base
3503  *       and size.
3504  *
3505  * Page must be busied?
3506  * No other requirements.
3507  */
3508 void
3509 vm_page_clear_dirty(vm_page_t m, int base, int size)
3510 {
3511         m->dirty &= ~vm_page_bits(base, size);
3512         if (base == 0 && size == PAGE_SIZE) {
3513                 /*pmap_clear_modify(m);*/
3514                 vm_page_flag_clear(m, PG_NOSYNC);
3515         }
3516 }
3517
3518 /*
3519  * Make the page all-dirty.
3520  *
3521  * Also make sure the related object and vnode reflect the fact that the
3522  * object may now contain a dirty page.
3523  *
3524  * Page must be busied?
3525  * No other requirements.
3526  */
3527 void
3528 vm_page_dirty(vm_page_t m)
3529 {
3530 #ifdef INVARIANTS
3531         int pqtype = m->queue - m->pc;
3532 #endif
3533         KASSERT(pqtype != PQ_CACHE && pqtype != PQ_FREE,
3534                 ("vm_page_dirty: page in free/cache queue!"));
3535         if (m->dirty != VM_PAGE_BITS_ALL) {
3536                 m->dirty = VM_PAGE_BITS_ALL;
3537                 if (m->object)
3538                         vm_object_set_writeable_dirty(m->object);
3539         }
3540 }
3541
3542 /*
3543  * Invalidates DEV_BSIZE'd chunks within a page.  Both the
3544  * valid and dirty bits for the effected areas are cleared.
3545  *
3546  * Page must be busied?
3547  * Does not block.
3548  * No other requirements.
3549  */
3550 void
3551 vm_page_set_invalid(vm_page_t m, int base, int size)
3552 {
3553         int bits;
3554
3555         bits = vm_page_bits(base, size);
3556         m->valid &= ~bits;
3557         m->dirty &= ~bits;
3558         atomic_add_int(&m->object->generation, 1);
3559 }
3560
3561 /*
3562  * The kernel assumes that the invalid portions of a page contain 
3563  * garbage, but such pages can be mapped into memory by user code.
3564  * When this occurs, we must zero out the non-valid portions of the
3565  * page so user code sees what it expects.
3566  *
3567  * Pages are most often semi-valid when the end of a file is mapped 
3568  * into memory and the file's size is not page aligned.
3569  *
3570  * Page must be busied?
3571  * No other requirements.
3572  */
3573 void
3574 vm_page_zero_invalid(vm_page_t m, boolean_t setvalid)
3575 {
3576         int b;
3577         int i;
3578
3579         /*
3580          * Scan the valid bits looking for invalid sections that
3581          * must be zerod.  Invalid sub-DEV_BSIZE'd areas ( where the
3582          * valid bit may be set ) have already been zerod by
3583          * vm_page_set_validclean().
3584          */
3585         for (b = i = 0; i <= PAGE_SIZE / DEV_BSIZE; ++i) {
3586                 if (i == (PAGE_SIZE / DEV_BSIZE) || 
3587                     (m->valid & (1 << i))
3588                 ) {
3589                         if (i > b) {
3590                                 pmap_zero_page_area(
3591                                     VM_PAGE_TO_PHYS(m), 
3592                                     b << DEV_BSHIFT,
3593                                     (i - b) << DEV_BSHIFT
3594                                 );
3595                         }
3596                         b = i + 1;
3597                 }
3598         }
3599
3600         /*
3601          * setvalid is TRUE when we can safely set the zero'd areas
3602          * as being valid.  We can do this if there are no cache consistency
3603          * issues.  e.g. it is ok to do with UFS, but not ok to do with NFS.
3604          */
3605         if (setvalid)
3606                 m->valid = VM_PAGE_BITS_ALL;
3607 }
3608
3609 /*
3610  * Is a (partial) page valid?  Note that the case where size == 0
3611  * will return FALSE in the degenerate case where the page is entirely
3612  * invalid, and TRUE otherwise.
3613  *
3614  * Does not block.
3615  * No other requirements.
3616  */
3617 int
3618 vm_page_is_valid(vm_page_t m, int base, int size)
3619 {
3620         int bits = vm_page_bits(base, size);
3621
3622         if (m->valid && ((m->valid & bits) == bits))
3623                 return 1;
3624         else
3625                 return 0;
3626 }
3627
3628 /*
3629  * Update dirty bits from pmap/mmu.  May not block.
3630  *
3631  * Caller must hold the page busy
3632  *
3633  * WARNING! Unless the page has been unmapped, this function only
3634  *          provides a likely dirty status.
3635  */
3636 void
3637 vm_page_test_dirty(vm_page_t m)
3638 {
3639         if (m->dirty != VM_PAGE_BITS_ALL && pmap_is_modified(m)) {
3640                 vm_page_dirty(m);
3641         }
3642 }
3643
3644 #include "opt_ddb.h"
3645 #ifdef DDB
3646 #include <ddb/ddb.h>
3647
3648 DB_SHOW_COMMAND(page, vm_page_print_page_info)
3649 {
3650         db_printf("vmstats.v_free_count: %ld\n", vmstats.v_free_count);
3651         db_printf("vmstats.v_cache_count: %ld\n", vmstats.v_cache_count);
3652         db_printf("vmstats.v_inactive_count: %ld\n", vmstats.v_inactive_count);
3653         db_printf("vmstats.v_active_count: %ld\n", vmstats.v_active_count);
3654         db_printf("vmstats.v_wire_count: %ld\n", vmstats.v_wire_count);
3655         db_printf("vmstats.v_free_reserved: %ld\n", vmstats.v_free_reserved);
3656         db_printf("vmstats.v_free_min: %ld\n", vmstats.v_free_min);
3657         db_printf("vmstats.v_free_target: %ld\n", vmstats.v_free_target);
3658         db_printf("vmstats.v_cache_min: %ld\n", vmstats.v_cache_min);
3659         db_printf("vmstats.v_inactive_target: %ld\n",
3660                   vmstats.v_inactive_target);
3661 }
3662
3663 DB_SHOW_COMMAND(pageq, vm_page_print_pageq_info)
3664 {
3665         int i;
3666         db_printf("PQ_FREE:");
3667         for (i = 0; i < PQ_L2_SIZE; i++) {
3668                 db_printf(" %ld", vm_page_queues[PQ_FREE + i].lcnt);
3669         }
3670         db_printf("\n");
3671                 
3672         db_printf("PQ_CACHE:");
3673         for(i = 0; i < PQ_L2_SIZE; i++) {
3674                 db_printf(" %ld", vm_page_queues[PQ_CACHE + i].lcnt);
3675         }
3676         db_printf("\n");
3677
3678         db_printf("PQ_ACTIVE:");
3679         for(i = 0; i < PQ_L2_SIZE; i++) {
3680                 db_printf(" %ld", vm_page_queues[PQ_ACTIVE + i].lcnt);
3681         }
3682         db_printf("\n");
3683
3684         db_printf("PQ_INACTIVE:");
3685         for(i = 0; i < PQ_L2_SIZE; i++) {
3686                 db_printf(" %ld", vm_page_queues[PQ_INACTIVE + i].lcnt);
3687         }
3688         db_printf("\n");
3689 }
3690 #endif /* DDB */