sys/vm/vm_phys.c

   1 /*-
   2  * Copyright (c) 2002-2006 Rice University
   3  * Copyright (c) 2007 Alan L. Cox <alc@cs.rice.edu>
   4  * All rights reserved.
   5  *
   6  * This software was developed for the FreeBSD Project by Alan L. Cox,
   7  * Olivier Crameri, Peter Druschel, Sitaram Iyer, and Juan Navarro.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT
  22  * HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  24  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
  25  * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  26  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
  28  * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29  * POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 /*
  33  *      Physical memory system implementation
  34  *
  35  * Any external functions defined by this module are only to be used by the
  36  * virtual memory system.
  37  */
  38
  39 #include <sys/cdefs.h>
  40 __FBSDID("$FreeBSD$");
  41
  42 #include "opt_ddb.h"
  43 #include "opt_vm.h"
  44
  45 #include <sys/param.h>
  46 #include <sys/systm.h>
  47 #include <sys/lock.h>
  48 #include <sys/kernel.h>
  49 #include <sys/malloc.h>
  50 #include <sys/mutex.h>
  51 #if MAXMEMDOM > 1
  52 #include <sys/proc.h>
  53 #endif
  54 #include <sys/queue.h>
  55 #include <sys/rwlock.h>
  56 #include <sys/sbuf.h>
  57 #include <sys/sysctl.h>
  58 #include <sys/tree.h>
  59 #include <sys/vmmeter.h>
  60
  61 #include <ddb/ddb.h>
  62
  63 #include <vm/vm.h>
  64 #include <vm/vm_param.h>
  65 #include <vm/vm_kern.h>
  66 #include <vm/vm_object.h>
  67 #include <vm/vm_page.h>
  68 #include <vm/vm_phys.h>
  69
  70 _Static_assert(sizeof(long) * NBBY >= VM_PHYSSEG_MAX,
  71     "Too many physsegs.");
  72
  73 struct mem_affinity *mem_affinity;
  74
  75 int vm_ndomains = 1;
  76
  77 struct vm_phys_seg vm_phys_segs[VM_PHYSSEG_MAX];
  78 int vm_phys_nsegs;
  79
  80 struct vm_phys_fictitious_seg;
  81 static int vm_phys_fictitious_cmp(struct vm_phys_fictitious_seg *,
  82     struct vm_phys_fictitious_seg *);
  83
  84 RB_HEAD(fict_tree, vm_phys_fictitious_seg) vm_phys_fictitious_tree =
  85     RB_INITIALIZER(_vm_phys_fictitious_tree);
  86
  87 struct vm_phys_fictitious_seg {
  88         RB_ENTRY(vm_phys_fictitious_seg) node;
  89         /* Memory region data */
  90         vm_paddr_t      start;
  91         vm_paddr_t      end;
  92         vm_page_t       first_page;
  93 };
  94
  95 RB_GENERATE_STATIC(fict_tree, vm_phys_fictitious_seg, node,
  96     vm_phys_fictitious_cmp);
  97
  98 static struct rwlock vm_phys_fictitious_reg_lock;
  99 MALLOC_DEFINE(M_FICT_PAGES, "vm_fictitious", "Fictitious VM pages");
 100
 101 static struct vm_freelist
 102     vm_phys_free_queues[MAXMEMDOM][VM_NFREELIST][VM_NFREEPOOL][VM_NFREEORDER];
 103
 104 static int vm_nfreelists = VM_FREELIST_DEFAULT + 1;
 105
 106 static int cnt_prezero;
 107 SYSCTL_INT(_vm_stats_misc, OID_AUTO, cnt_prezero, CTLFLAG_RD,
 108     &cnt_prezero, 0, "The number of physical pages prezeroed at idle time");
 109
 110 static int sysctl_vm_phys_free(SYSCTL_HANDLER_ARGS);
 111 SYSCTL_OID(_vm, OID_AUTO, phys_free, CTLTYPE_STRING | CTLFLAG_RD,
 112     NULL, 0, sysctl_vm_phys_free, "A", "Phys Free Info");
 113
 114 static int sysctl_vm_phys_segs(SYSCTL_HANDLER_ARGS);
 115 SYSCTL_OID(_vm, OID_AUTO, phys_segs, CTLTYPE_STRING | CTLFLAG_RD,
 116     NULL, 0, sysctl_vm_phys_segs, "A", "Phys Seg Info");
 117
 118 SYSCTL_INT(_vm, OID_AUTO, ndomains, CTLFLAG_RD,
 119     &vm_ndomains, 0, "Number of physical memory domains available.");
 120
 121 static vm_page_t vm_phys_alloc_domain_pages(int domain, int flind, int pool,
 122     int order);
 123 static void _vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int flind,
 124     int domain);
 125 static void vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int flind);
 126 static int vm_phys_paddr_to_segind(vm_paddr_t pa);
 127 static void vm_phys_split_pages(vm_page_t m, int oind, struct vm_freelist *fl,
 128     int order);
 129
 130 /*
 131  * Red-black tree helpers for vm fictitious range management.
 132  */
 133 static inline int
 134 vm_phys_fictitious_in_range(struct vm_phys_fictitious_seg *p,
 135     struct vm_phys_fictitious_seg *range)
 136 {
 137
 138         KASSERT(range->start != 0 && range->end != 0,
 139             ("Invalid range passed on search for vm_fictitious page"));
 140         if (p->start >= range->end)
 141                 return (1);
 142         if (p->start < range->start)
 143                 return (-1);
 144
 145         return (0);
 146 }
 147
 148 static int
 149 vm_phys_fictitious_cmp(struct vm_phys_fictitious_seg *p1,
 150     struct vm_phys_fictitious_seg *p2)
 151 {
 152
 153         /* Check if this is a search for a page */
 154         if (p1->end == 0)
 155                 return (vm_phys_fictitious_in_range(p1, p2));
 156
 157         KASSERT(p2->end != 0,
 158     ("Invalid range passed as second parameter to vm fictitious comparison"));
 159
 160         /* Searching to add a new range */
 161         if (p1->end <= p2->start)
 162                 return (-1);
 163         if (p1->start >= p2->end)
 164                 return (1);
 165
 166         panic("Trying to add overlapping vm fictitious ranges:\n"
 167             "[%#jx:%#jx] and [%#jx:%#jx]", (uintmax_t)p1->start,
 168             (uintmax_t)p1->end, (uintmax_t)p2->start, (uintmax_t)p2->end);
 169 }
 170
 171 static __inline int
 172 vm_rr_selectdomain(void)
 173 {
 174 #if MAXMEMDOM > 1
 175         struct thread *td;
 176
 177         td = curthread;
 178
 179         td->td_dom_rr_idx++;
 180         td->td_dom_rr_idx %= vm_ndomains;
 181         return (td->td_dom_rr_idx);
 182 #else
 183         return (0);
 184 #endif
 185 }
 186
 187 boolean_t
 188 vm_phys_domain_intersects(long mask, vm_paddr_t low, vm_paddr_t high)
 189 {
 190         struct vm_phys_seg *s;
 191         int idx;
 192
 193         while ((idx = ffsl(mask)) != 0) {
 194                 idx--;  /* ffsl counts from 1 */
 195                 mask &= ~(1UL << idx);
 196                 s = &vm_phys_segs[idx];
 197                 if (low < s->end && high > s->start)
 198                         return (TRUE);
 199         }
 200         return (FALSE);
 201 }
 202
 203 /*
 204  * Outputs the state of the physical memory allocator, specifically,
 205  * the amount of physical memory in each free list.
 206  */
 207 static int
 208 sysctl_vm_phys_free(SYSCTL_HANDLER_ARGS)
 209 {
 210         struct sbuf sbuf;
 211         struct vm_freelist *fl;
 212         int dom, error, flind, oind, pind;
 213
 214         error = sysctl_wire_old_buffer(req, 0);
 215         if (error != 0)
 216                 return (error);
 217         sbuf_new_for_sysctl(&sbuf, NULL, 128 * vm_ndomains, req);
 218         for (dom = 0; dom < vm_ndomains; dom++) {
 219                 sbuf_printf(&sbuf,"\nDOMAIN %d:\n", dom);
 220                 for (flind = 0; flind < vm_nfreelists; flind++) {
 221                         sbuf_printf(&sbuf, "\nFREE LIST %d:\n"
 222                             "\n  ORDER (SIZE)  |  NUMBER"
 223                             "\n              ", flind);
 224                         for (pind = 0; pind < VM_NFREEPOOL; pind++)
 225                                 sbuf_printf(&sbuf, "  |  POOL %d", pind);
 226                         sbuf_printf(&sbuf, "\n--            ");
 227                         for (pind = 0; pind < VM_NFREEPOOL; pind++)
 228                                 sbuf_printf(&sbuf, "-- --      ");
 229                         sbuf_printf(&sbuf, "--\n");
 230                         for (oind = VM_NFREEORDER - 1; oind >= 0; oind--) {
 231                                 sbuf_printf(&sbuf, "  %2d (%6dK)", oind,
 232                                     1 << (PAGE_SHIFT - 10 + oind));
 233                                 for (pind = 0; pind < VM_NFREEPOOL; pind++) {
 234                                 fl = vm_phys_free_queues[dom][flind][pind];
 235                                         sbuf_printf(&sbuf, "  |  %6d",
 236                                             fl[oind].lcnt);
 237                                 }
 238                                 sbuf_printf(&sbuf, "\n");
 239                         }
 240                 }
 241         }
 242         error = sbuf_finish(&sbuf);
 243         sbuf_delete(&sbuf);
 244         return (error);
 245 }
 246
 247 /*
 248  * Outputs the set of physical memory segments.
 249  */
 250 static int
 251 sysctl_vm_phys_segs(SYSCTL_HANDLER_ARGS)
 252 {
 253         struct sbuf sbuf;
 254         struct vm_phys_seg *seg;
 255         int error, segind;
 256
 257         error = sysctl_wire_old_buffer(req, 0);
 258         if (error != 0)
 259                 return (error);
 260         sbuf_new_for_sysctl(&sbuf, NULL, 128, req);
 261         for (segind = 0; segind < vm_phys_nsegs; segind++) {
 262                 sbuf_printf(&sbuf, "\nSEGMENT %d:\n\n", segind);
 263                 seg = &vm_phys_segs[segind];
 264                 sbuf_printf(&sbuf, "start:     %#jx\n",
 265                     (uintmax_t)seg->start);
 266                 sbuf_printf(&sbuf, "end:       %#jx\n",
 267                     (uintmax_t)seg->end);
 268                 sbuf_printf(&sbuf, "domain:    %d\n", seg->domain);
 269                 sbuf_printf(&sbuf, "free list: %p\n", seg->free_queues);
 270         }
 271         error = sbuf_finish(&sbuf);
 272         sbuf_delete(&sbuf);
 273         return (error);
 274 }
 275
 276 static void
 277 vm_freelist_add(struct vm_freelist *fl, vm_page_t m, int order, int tail)
 278 {
 279
 280         m->order = order;
 281         if (tail)
 282                 TAILQ_INSERT_TAIL(&fl[order].pl, m, plinks.q);
 283         else
 284                 TAILQ_INSERT_HEAD(&fl[order].pl, m, plinks.q);
 285         fl[order].lcnt++;
 286 }
 287
 288 static void
 289 vm_freelist_rem(struct vm_freelist *fl, vm_page_t m, int order)
 290 {
 291
 292         TAILQ_REMOVE(&fl[order].pl, m, plinks.q);
 293         fl[order].lcnt--;
 294         m->order = VM_NFREEORDER;
 295 }
 296
 297 /*
 298  * Create a physical memory segment.
 299  */
 300 static void
 301 _vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int flind, int domain)
 302 {
 303         struct vm_phys_seg *seg;
 304 #ifdef VM_PHYSSEG_SPARSE
 305         long pages;
 306         int segind;
 307
 308         pages = 0;
 309         for (segind = 0; segind < vm_phys_nsegs; segind++) {
 310                 seg = &vm_phys_segs[segind];
 311                 pages += atop(seg->end - seg->start);
 312         }
 313 #endif
 314         KASSERT(vm_phys_nsegs < VM_PHYSSEG_MAX,
 315             ("vm_phys_create_seg: increase VM_PHYSSEG_MAX"));
 316         KASSERT(domain < vm_ndomains,
 317             ("vm_phys_create_seg: invalid domain provided"));
 318         seg = &vm_phys_segs[vm_phys_nsegs++];
 319         seg->start = start;
 320         seg->end = end;
 321         seg->domain = domain;
 322 #ifdef VM_PHYSSEG_SPARSE
 323         seg->first_page = &vm_page_array[pages];
 324 #else
 325         seg->first_page = PHYS_TO_VM_PAGE(start);
 326 #endif
 327         seg->free_queues = &vm_phys_free_queues[domain][flind];
 328 }
 329
 330 static void
 331 vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int flind)
 332 {
 333         int i;
 334
 335         if (mem_affinity == NULL) {
 336                 _vm_phys_create_seg(start, end, flind, 0);
 337                 return;
 338         }
 339
 340         for (i = 0;; i++) {
 341                 if (mem_affinity[i].end == 0)
 342                         panic("Reached end of affinity info");
 343                 if (mem_affinity[i].end <= start)
 344                         continue;
 345                 if (mem_affinity[i].start > start)
 346                         panic("No affinity info for start %jx",
 347                             (uintmax_t)start);
 348                 if (mem_affinity[i].end >= end) {
 349                         _vm_phys_create_seg(start, end, flind,
 350                             mem_affinity[i].domain);
 351                         break;
 352                 }
 353                 _vm_phys_create_seg(start, mem_affinity[i].end, flind,
 354                     mem_affinity[i].domain);
 355                 start = mem_affinity[i].end;
 356         }
 357 }
 358
 359 /*
 360  * Initialize the physical memory allocator.
 361  */
 362 void
 363 vm_phys_init(void)
 364 {
 365         struct vm_freelist *fl;
 366         int dom, flind, i, oind, pind;
 367
 368         for (i = 0; phys_avail[i + 1] != 0; i += 2) {
 369 #ifdef  VM_FREELIST_ISADMA
 370                 if (phys_avail[i] < 16777216) {
 371                         if (phys_avail[i + 1] > 16777216) {
 372                                 vm_phys_create_seg(phys_avail[i], 16777216,
 373                                     VM_FREELIST_ISADMA);
 374                                 vm_phys_create_seg(16777216, phys_avail[i + 1],
 375                                     VM_FREELIST_DEFAULT);
 376                         } else {
 377                                 vm_phys_create_seg(phys_avail[i],
 378                                     phys_avail[i + 1], VM_FREELIST_ISADMA);
 379                         }
 380                         if (VM_FREELIST_ISADMA >= vm_nfreelists)
 381                                 vm_nfreelists = VM_FREELIST_ISADMA + 1;
 382                 } else
 383 #endif
 384 #ifdef  VM_FREELIST_HIGHMEM
 385                 if (phys_avail[i + 1] > VM_HIGHMEM_ADDRESS) {
 386                         if (phys_avail[i] < VM_HIGHMEM_ADDRESS) {
 387                                 vm_phys_create_seg(phys_avail[i],
 388                                     VM_HIGHMEM_ADDRESS, VM_FREELIST_DEFAULT);
 389                                 vm_phys_create_seg(VM_HIGHMEM_ADDRESS,
 390                                     phys_avail[i + 1], VM_FREELIST_HIGHMEM);
 391                         } else {
 392                                 vm_phys_create_seg(phys_avail[i],
 393                                     phys_avail[i + 1], VM_FREELIST_HIGHMEM);
 394                         }
 395                         if (VM_FREELIST_HIGHMEM >= vm_nfreelists)
 396                                 vm_nfreelists = VM_FREELIST_HIGHMEM + 1;
 397                 } else
 398 #endif
 399                 vm_phys_create_seg(phys_avail[i], phys_avail[i + 1],
 400                     VM_FREELIST_DEFAULT);
 401         }
 402         for (dom = 0; dom < vm_ndomains; dom++) {
 403                 for (flind = 0; flind < vm_nfreelists; flind++) {
 404                         for (pind = 0; pind < VM_NFREEPOOL; pind++) {
 405                                 fl = vm_phys_free_queues[dom][flind][pind];
 406                                 for (oind = 0; oind < VM_NFREEORDER; oind++)
 407                                         TAILQ_INIT(&fl[oind].pl);
 408                         }
 409                 }
 410         }
 411         rw_init(&vm_phys_fictitious_reg_lock, "vmfctr");
 412 }
 413
 414 /*
 415  * Split a contiguous, power of two-sized set of physical pages.
 416  */
 417 static __inline void
 418 vm_phys_split_pages(vm_page_t m, int oind, struct vm_freelist *fl, int order)
 419 {
 420         vm_page_t m_buddy;
 421
 422         while (oind > order) {
 423                 oind--;
 424                 m_buddy = &m[1 << oind];
 425                 KASSERT(m_buddy->order == VM_NFREEORDER,
 426                     ("vm_phys_split_pages: page %p has unexpected order %d",
 427                     m_buddy, m_buddy->order));
 428                 vm_freelist_add(fl, m_buddy, oind, 0);
 429         }
 430 }
 431
 432 /*
 433  * Initialize a physical page and add it to the free lists.
 434  */
 435 void
 436 vm_phys_add_page(vm_paddr_t pa)
 437 {
 438         vm_page_t m;
 439         struct vm_domain *vmd;
 440
 441         vm_cnt.v_page_count++;
 442         m = vm_phys_paddr_to_vm_page(pa);
 443         m->phys_addr = pa;
 444         m->queue = PQ_NONE;
 445         m->segind = vm_phys_paddr_to_segind(pa);
 446         vmd = vm_phys_domain(m);
 447         vmd->vmd_page_count++;
 448         vmd->vmd_segs |= 1UL << m->segind;
 449         KASSERT(m->order == VM_NFREEORDER,
 450             ("vm_phys_add_page: page %p has unexpected order %d",
 451             m, m->order));
 452         m->pool = VM_FREEPOOL_DEFAULT;
 453         pmap_page_init(m);
 454         mtx_lock(&vm_page_queue_free_mtx);
 455         vm_phys_freecnt_adj(m, 1);
 456         vm_phys_free_pages(m, 0);
 457         mtx_unlock(&vm_page_queue_free_mtx);
 458 }
 459
 460 /*
 461  * Allocate a contiguous, power of two-sized set of physical pages
 462  * from the free lists.
 463  *
 464  * The free page queues must be locked.
 465  */
 466 vm_page_t
 467 vm_phys_alloc_pages(int pool, int order)
 468 {
 469         vm_page_t m;
 470         int dom, domain, flind;
 471
 472         KASSERT(pool < VM_NFREEPOOL,
 473             ("vm_phys_alloc_pages: pool %d is out of range", pool));
 474         KASSERT(order < VM_NFREEORDER,
 475             ("vm_phys_alloc_pages: order %d is out of range", order));
 476
 477         for (dom = 0; dom < vm_ndomains; dom++) {
 478                 domain = vm_rr_selectdomain();
 479                 for (flind = 0; flind < vm_nfreelists; flind++) {
 480                         m = vm_phys_alloc_domain_pages(domain, flind, pool,
 481                             order);
 482                         if (m != NULL)
 483                                 return (m);
 484                 }
 485         }
 486         return (NULL);
 487 }
 488
 489 /*
 490  * Find and dequeue a free page on the given free list, with the
 491  * specified pool and order
 492  */
 493 vm_page_t
 494 vm_phys_alloc_freelist_pages(int flind, int pool, int order)
 495 {
 496         vm_page_t m;
 497         int dom, domain;
 498
 499         KASSERT(flind < VM_NFREELIST,
 500             ("vm_phys_alloc_freelist_pages: freelist %d is out of range", flind));
 501         KASSERT(pool < VM_NFREEPOOL,
 502             ("vm_phys_alloc_freelist_pages: pool %d is out of range", pool));
 503         KASSERT(order < VM_NFREEORDER,
 504             ("vm_phys_alloc_freelist_pages: order %d is out of range", order));
 505
 506         for (dom = 0; dom < vm_ndomains; dom++) {
 507                 domain = vm_rr_selectdomain();
 508                 m = vm_phys_alloc_domain_pages(domain, flind, pool, order);
 509                 if (m != NULL)
 510                         return (m);
 511         }
 512         return (NULL);
 513 }
 514
 515 static vm_page_t
 516 vm_phys_alloc_domain_pages(int domain, int flind, int pool, int order)
 517 {
 518         struct vm_freelist *fl;
 519         struct vm_freelist *alt;
 520         int oind, pind;
 521         vm_page_t m;
 522
 523         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
 524         fl = &vm_phys_free_queues[domain][flind][pool][0];
 525         for (oind = order; oind < VM_NFREEORDER; oind++) {
 526                 m = TAILQ_FIRST(&fl[oind].pl);
 527                 if (m != NULL) {
 528                         vm_freelist_rem(fl, m, oind);
 529                         vm_phys_split_pages(m, oind, fl, order);
 530                         return (m);
 531                 }
 532         }
 533
 534         /*
 535          * The given pool was empty.  Find the largest
 536          * contiguous, power-of-two-sized set of pages in any
 537          * pool.  Transfer these pages to the given pool, and
 538          * use them to satisfy the allocation.
 539          */
 540         for (oind = VM_NFREEORDER - 1; oind >= order; oind--) {
 541                 for (pind = 0; pind < VM_NFREEPOOL; pind++) {
 542                         alt = &vm_phys_free_queues[domain][flind][pind][0];
 543                         m = TAILQ_FIRST(&alt[oind].pl);
 544                         if (m != NULL) {
 545                                 vm_freelist_rem(alt, m, oind);
 546                                 vm_phys_set_pool(pool, m, oind);
 547                                 vm_phys_split_pages(m, oind, fl, order);
 548                                 return (m);
 549                         }
 550                 }
 551         }
 552         return (NULL);
 553 }
 554
 555 /*
 556  * Find the vm_page corresponding to the given physical address.
 557  */
 558 vm_page_t
 559 vm_phys_paddr_to_vm_page(vm_paddr_t pa)
 560 {
 561         struct vm_phys_seg *seg;
 562         int segind;
 563
 564         for (segind = 0; segind < vm_phys_nsegs; segind++) {
 565                 seg = &vm_phys_segs[segind];
 566                 if (pa >= seg->start && pa < seg->end)
 567                         return (&seg->first_page[atop(pa - seg->start)]);
 568         }
 569         return (NULL);
 570 }
 571
 572 vm_page_t
 573 vm_phys_fictitious_to_vm_page(vm_paddr_t pa)
 574 {
 575         struct vm_phys_fictitious_seg tmp, *seg;
 576         vm_page_t m;
 577
 578         m = NULL;
 579         tmp.start = pa;
 580         tmp.end = 0;
 581
 582         rw_rlock(&vm_phys_fictitious_reg_lock);
 583         seg = RB_FIND(fict_tree, &vm_phys_fictitious_tree, &tmp);
 584         rw_runlock(&vm_phys_fictitious_reg_lock);
 585         if (seg == NULL)
 586                 return (NULL);
 587
 588         m = &seg->first_page[atop(pa - seg->start)];
 589         KASSERT((m->flags & PG_FICTITIOUS) != 0, ("%p not fictitious", m));
 590
 591         return (m);
 592 }
 593
 594 int
 595 vm_phys_fictitious_reg_range(vm_paddr_t start, vm_paddr_t end,
 596     vm_memattr_t memattr)
 597 {
 598         struct vm_phys_fictitious_seg *seg;
 599         vm_page_t fp;
 600         long i, page_count;
 601 #ifdef VM_PHYSSEG_DENSE
 602         long pi;
 603 #endif
 604
 605         page_count = (end - start) / PAGE_SIZE;
 606
 607 #ifdef VM_PHYSSEG_DENSE
 608         pi = atop(start);
 609         if (pi >= first_page && pi < vm_page_array_size + first_page) {
 610                 if (atop(end) >= vm_page_array_size + first_page)
 611                         return (EINVAL);
 612                 fp = &vm_page_array[pi - first_page];
 613         } else
 614 #endif
 615         {
 616                 fp = malloc(page_count * sizeof(struct vm_page), M_FICT_PAGES,
 617                     M_WAITOK | M_ZERO);
 618         }
 619         for (i = 0; i < page_count; i++) {
 620                 vm_page_initfake(&fp[i], start + PAGE_SIZE * i, memattr);
 621                 fp[i].oflags &= ~VPO_UNMANAGED;
 622                 fp[i].busy_lock = VPB_UNBUSIED;
 623         }
 624
 625         seg = malloc(sizeof(*seg), M_FICT_PAGES, M_WAITOK | M_ZERO);
 626         seg->start = start;
 627         seg->end = end;
 628         seg->first_page = fp;
 629
 630         rw_wlock(&vm_phys_fictitious_reg_lock);
 631         RB_INSERT(fict_tree, &vm_phys_fictitious_tree, seg);
 632         rw_wunlock(&vm_phys_fictitious_reg_lock);
 633
 634         return (0);
 635 }
 636
 637 void
 638 vm_phys_fictitious_unreg_range(vm_paddr_t start, vm_paddr_t end)
 639 {
 640         struct vm_phys_fictitious_seg *seg, tmp;
 641 #ifdef VM_PHYSSEG_DENSE
 642         long pi;
 643 #endif
 644
 645 #ifdef VM_PHYSSEG_DENSE
 646         pi = atop(start);
 647 #endif
 648         tmp.start = start;
 649         tmp.end = 0;
 650
 651         rw_wlock(&vm_phys_fictitious_reg_lock);
 652         seg = RB_FIND(fict_tree, &vm_phys_fictitious_tree, &tmp);
 653         if (seg->start != start || seg->end != end) {
 654                 rw_wunlock(&vm_phys_fictitious_reg_lock);
 655                 panic(
 656                     "Unregistering not registered fictitious range [%#jx:%#jx]",
 657                     (uintmax_t)start, (uintmax_t)end);
 658         }
 659         RB_REMOVE(fict_tree, &vm_phys_fictitious_tree, seg);
 660         rw_wunlock(&vm_phys_fictitious_reg_lock);
 661 #ifdef VM_PHYSSEG_DENSE
 662         if (pi < first_page || atop(end) >= vm_page_array_size)
 663 #endif
 664                 free(seg->first_page, M_FICT_PAGES);
 665         free(seg, M_FICT_PAGES);
 666 }
 667
 668 /*
 669  * Find the segment containing the given physical address.
 670  */
 671 static int
 672 vm_phys_paddr_to_segind(vm_paddr_t pa)
 673 {
 674         struct vm_phys_seg *seg;
 675         int segind;
 676
 677         for (segind = 0; segind < vm_phys_nsegs; segind++) {
 678                 seg = &vm_phys_segs[segind];
 679                 if (pa >= seg->start && pa < seg->end)
 680                         return (segind);
 681         }
 682         panic("vm_phys_paddr_to_segind: paddr %#jx is not in any segment" ,
 683             (uintmax_t)pa);
 684 }
 685
 686 /*
 687  * Free a contiguous, power of two-sized set of physical pages.
 688  *
 689  * The free page queues must be locked.
 690  */
 691 void
 692 vm_phys_free_pages(vm_page_t m, int order)
 693 {
 694         struct vm_freelist *fl;
 695         struct vm_phys_seg *seg;
 696         vm_paddr_t pa;
 697         vm_page_t m_buddy;
 698
 699         KASSERT(m->order == VM_NFREEORDER,
 700             ("vm_phys_free_pages: page %p has unexpected order %d",
 701             m, m->order));
 702         KASSERT(m->pool < VM_NFREEPOOL,
 703             ("vm_phys_free_pages: page %p has unexpected pool %d",
 704             m, m->pool));
 705         KASSERT(order < VM_NFREEORDER,
 706             ("vm_phys_free_pages: order %d is out of range", order));
 707         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
 708         seg = &vm_phys_segs[m->segind];
 709         if (order < VM_NFREEORDER - 1) {
 710                 pa = VM_PAGE_TO_PHYS(m);
 711                 do {
 712                         pa ^= ((vm_paddr_t)1 << (PAGE_SHIFT + order));
 713                         if (pa < seg->start || pa >= seg->end)
 714                                 break;
 715                         m_buddy = &seg->first_page[atop(pa - seg->start)];
 716                         if (m_buddy->order != order)
 717                                 break;
 718                         fl = (*seg->free_queues)[m_buddy->pool];
 719                         vm_freelist_rem(fl, m_buddy, order);
 720                         if (m_buddy->pool != m->pool)
 721                                 vm_phys_set_pool(m->pool, m_buddy, order);
 722                         order++;
 723                         pa &= ~(((vm_paddr_t)1 << (PAGE_SHIFT + order)) - 1);
 724                         m = &seg->first_page[atop(pa - seg->start)];
 725                 } while (order < VM_NFREEORDER - 1);
 726         }
 727         fl = (*seg->free_queues)[m->pool];
 728         vm_freelist_add(fl, m, order, 1);
 729 }
 730
 731 /*
 732  * Free a contiguous, arbitrarily sized set of physical pages.
 733  *
 734  * The free page queues must be locked.
 735  */
 736 void
 737 vm_phys_free_contig(vm_page_t m, u_long npages)
 738 {
 739         u_int n;
 740         int order;
 741
 742         /*
 743          * Avoid unnecessary coalescing by freeing the pages in the largest
 744          * possible power-of-two-sized subsets.
 745          */
 746         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
 747         for (;; npages -= n) {
 748                 /*
 749                  * Unsigned "min" is used here so that "order" is assigned
 750                  * "VM_NFREEORDER - 1" when "m"'s physical address is zero
 751                  * or the low-order bits of its physical address are zero
 752                  * because the size of a physical address exceeds the size of
 753                  * a long.
 754                  */
 755                 order = min(ffsl(VM_PAGE_TO_PHYS(m) >> PAGE_SHIFT) - 1,
 756                     VM_NFREEORDER - 1);
 757                 n = 1 << order;
 758                 if (npages < n)
 759                         break;
 760                 vm_phys_free_pages(m, order);
 761                 m += n;
 762         }
 763         /* The residual "npages" is less than "1 << (VM_NFREEORDER - 1)". */
 764         for (; npages > 0; npages -= n) {
 765                 order = flsl(npages) - 1;
 766                 n = 1 << order;
 767                 vm_phys_free_pages(m, order);
 768                 m += n;
 769         }
 770 }
 771
 772 /*
 773  * Set the pool for a contiguous, power of two-sized set of physical pages.
 774  */
 775 void
 776 vm_phys_set_pool(int pool, vm_page_t m, int order)
 777 {
 778         vm_page_t m_tmp;
 779
 780         for (m_tmp = m; m_tmp < &m[1 << order]; m_tmp++)
 781                 m_tmp->pool = pool;
 782 }
 783
 784 /*
 785  * Search for the given physical page "m" in the free lists.  If the search
 786  * succeeds, remove "m" from the free lists and return TRUE.  Otherwise, return
 787  * FALSE, indicating that "m" is not in the free lists.
 788  *
 789  * The free page queues must be locked.
 790  */
 791 boolean_t
 792 vm_phys_unfree_page(vm_page_t m)
 793 {
 794         struct vm_freelist *fl;
 795         struct vm_phys_seg *seg;
 796         vm_paddr_t pa, pa_half;
 797         vm_page_t m_set, m_tmp;
 798         int order;
 799
 800         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
 801
 802         /*
 803          * First, find the contiguous, power of two-sized set of free
 804          * physical pages containing the given physical page "m" and
 805          * assign it to "m_set".
 806          */
 807         seg = &vm_phys_segs[m->segind];
 808         for (m_set = m, order = 0; m_set->order == VM_NFREEORDER &&
 809             order < VM_NFREEORDER - 1; ) {
 810                 order++;
 811                 pa = m->phys_addr & (~(vm_paddr_t)0 << (PAGE_SHIFT + order));
 812                 if (pa >= seg->start)
 813                         m_set = &seg->first_page[atop(pa - seg->start)];
 814                 else
 815                         return (FALSE);
 816         }
 817         if (m_set->order < order)
 818                 return (FALSE);
 819         if (m_set->order == VM_NFREEORDER)
 820                 return (FALSE);
 821         KASSERT(m_set->order < VM_NFREEORDER,
 822             ("vm_phys_unfree_page: page %p has unexpected order %d",
 823             m_set, m_set->order));
 824
 825         /*
 826          * Next, remove "m_set" from the free lists.  Finally, extract
 827          * "m" from "m_set" using an iterative algorithm: While "m_set"
 828          * is larger than a page, shrink "m_set" by returning the half
 829          * of "m_set" that does not contain "m" to the free lists.
 830          */
 831         fl = (*seg->free_queues)[m_set->pool];
 832         order = m_set->order;
 833         vm_freelist_rem(fl, m_set, order);
 834         while (order > 0) {
 835                 order--;
 836                 pa_half = m_set->phys_addr ^ (1 << (PAGE_SHIFT + order));
 837                 if (m->phys_addr < pa_half)
 838                         m_tmp = &seg->first_page[atop(pa_half - seg->start)];
 839                 else {
 840                         m_tmp = m_set;
 841                         m_set = &seg->first_page[atop(pa_half - seg->start)];
 842                 }
 843                 vm_freelist_add(fl, m_tmp, order, 0);
 844         }
 845         KASSERT(m_set == m, ("vm_phys_unfree_page: fatal inconsistency"));
 846         return (TRUE);
 847 }
 848
 849 /*
 850  * Try to zero one physical page.  Used by an idle priority thread.
 851  */
 852 boolean_t
 853 vm_phys_zero_pages_idle(void)
 854 {
 855         static struct vm_freelist *fl;
 856         static int flind, oind, pind;
 857         vm_page_t m, m_tmp;
 858         int domain;
 859
 860         domain = vm_rr_selectdomain();
 861         fl = vm_phys_free_queues[domain][0][0];
 862         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
 863         for (;;) {
 864                 TAILQ_FOREACH_REVERSE(m, &fl[oind].pl, pglist, plinks.q) {
 865                         for (m_tmp = m; m_tmp < &m[1 << oind]; m_tmp++) {
 866                                 if ((m_tmp->flags & (PG_CACHED | PG_ZERO)) == 0) {
 867                                         vm_phys_unfree_page(m_tmp);
 868                                         vm_phys_freecnt_adj(m, -1);
 869                                         mtx_unlock(&vm_page_queue_free_mtx);
 870                                         pmap_zero_page_idle(m_tmp);
 871                                         m_tmp->flags |= PG_ZERO;
 872                                         mtx_lock(&vm_page_queue_free_mtx);
 873                                         vm_phys_freecnt_adj(m, 1);
 874                                         vm_phys_free_pages(m_tmp, 0);
 875                                         vm_page_zero_count++;
 876                                         cnt_prezero++;
 877                                         return (TRUE);
 878                                 }
 879                         }
 880                 }
 881                 oind++;
 882                 if (oind == VM_NFREEORDER) {
 883                         oind = 0;
 884                         pind++;
 885                         if (pind == VM_NFREEPOOL) {
 886                                 pind = 0;
 887                                 flind++;
 888                                 if (flind == vm_nfreelists)
 889                                         flind = 0;
 890                         }
 891                         fl = vm_phys_free_queues[domain][flind][pind];
 892                 }
 893         }
 894 }
 895
 896 /*
 897  * Allocate a contiguous set of physical pages of the given size
 898  * "npages" from the free lists.  All of the physical pages must be at
 899  * or above the given physical address "low" and below the given
 900  * physical address "high".  The given value "alignment" determines the
 901  * alignment of the first physical page in the set.  If the given value
 902  * "boundary" is non-zero, then the set of physical pages cannot cross
 903  * any physical address boundary that is a multiple of that value.  Both
 904  * "alignment" and "boundary" must be a power of two.
 905  */
 906 vm_page_t
 907 vm_phys_alloc_contig(u_long npages, vm_paddr_t low, vm_paddr_t high,
 908     u_long alignment, vm_paddr_t boundary)
 909 {
 910         struct vm_freelist *fl;
 911         struct vm_phys_seg *seg;
 912         vm_paddr_t pa, pa_last, size;
 913         vm_page_t m, m_ret;
 914         u_long npages_end;
 915         int dom, domain, flind, oind, order, pind;
 916
 917         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
 918         size = npages << PAGE_SHIFT;
 919         KASSERT(size != 0,
 920             ("vm_phys_alloc_contig: size must not be 0"));
 921         KASSERT((alignment & (alignment - 1)) == 0,
 922             ("vm_phys_alloc_contig: alignment must be a power of 2"));
 923         KASSERT((boundary & (boundary - 1)) == 0,
 924             ("vm_phys_alloc_contig: boundary must be a power of 2"));
 925         /* Compute the queue that is the best fit for npages. */
 926         for (order = 0; (1 << order) < npages; order++);
 927         dom = 0;
 928 restartdom:
 929         domain = vm_rr_selectdomain();
 930         for (flind = 0; flind < vm_nfreelists; flind++) {
 931                 for (oind = min(order, VM_NFREEORDER - 1); oind < VM_NFREEORDER; oind++) {
 932                         for (pind = 0; pind < VM_NFREEPOOL; pind++) {
 933                                 fl = &vm_phys_free_queues[domain][flind][pind][0];
 934                                 TAILQ_FOREACH(m_ret, &fl[oind].pl, plinks.q) {
 935                                         /*
 936                                          * A free list may contain physical pages
 937                                          * from one or more segments.
 938                                          */
 939                                         seg = &vm_phys_segs[m_ret->segind];
 940                                         if (seg->start > high ||
 941                                             low >= seg->end)
 942                                                 continue;
 943
 944                                         /*
 945                                          * Is the size of this allocation request
 946                                          * larger than the largest block size?
 947                                          */
 948                                         if (order >= VM_NFREEORDER) {
 949                                                 /*
 950                                                  * Determine if a sufficient number
 951                                                  * of subsequent blocks to satisfy
 952                                                  * the allocation request are free.
 953                                                  */
 954                                                 pa = VM_PAGE_TO_PHYS(m_ret);
 955                                                 pa_last = pa + size;
 956                                                 for (;;) {
 957                                                         pa += 1 << (PAGE_SHIFT + VM_NFREEORDER - 1);
 958                                                         if (pa >= pa_last)
 959                                                                 break;
 960                                                         if (pa < seg->start ||
 961                                                             pa >= seg->end)
 962                                                                 break;
 963                                                         m = &seg->first_page[atop(pa - seg->start)];
 964                                                         if (m->order != VM_NFREEORDER - 1)
 965                                                                 break;
 966                                                 }
 967                                                 /* If not, continue to the next block. */
 968                                                 if (pa < pa_last)
 969                                                         continue;
 970                                         }
 971
 972                                         /*
 973                                          * Determine if the blocks are within the given range,
 974                                          * satisfy the given alignment, and do not cross the
 975                                          * given boundary.
 976                                          */
 977                                         pa = VM_PAGE_TO_PHYS(m_ret);
 978                                         if (pa >= low &&
 979                                             pa + size <= high &&
 980                                             (pa & (alignment - 1)) == 0 &&
 981                                             ((pa ^ (pa + size - 1)) & ~(boundary - 1)) == 0)
 982                                                 goto done;
 983                                 }
 984                         }
 985                 }
 986         }
 987         if (++dom < vm_ndomains)
 988                 goto restartdom;
 989         return (NULL);
 990 done:
 991         for (m = m_ret; m < &m_ret[npages]; m = &m[1 << oind]) {
 992                 fl = (*seg->free_queues)[m->pool];
 993                 vm_freelist_rem(fl, m, m->order);
 994         }
 995         if (m_ret->pool != VM_FREEPOOL_DEFAULT)
 996                 vm_phys_set_pool(VM_FREEPOOL_DEFAULT, m_ret, oind);
 997         fl = (*seg->free_queues)[m_ret->pool];
 998         vm_phys_split_pages(m_ret, oind, fl, order);
 999         /* Return excess pages to the free lists. */
1000         npages_end = roundup2(npages, 1 << imin(oind, order));
1001         if (npages < npages_end)
1002                 vm_phys_free_contig(&m_ret[npages], npages_end - npages);
1003         return (m_ret);
1004 }
1005
1006 #ifdef DDB
1007 /*
1008  * Show the number of physical pages in each of the free lists.
1009  */
1010 DB_SHOW_COMMAND(freepages, db_show_freepages)
1011 {
1012         struct vm_freelist *fl;
1013         int flind, oind, pind, dom;
1014
1015         for (dom = 0; dom < vm_ndomains; dom++) {
1016                 db_printf("DOMAIN: %d\n", dom);
1017                 for (flind = 0; flind < vm_nfreelists; flind++) {
1018                         db_printf("FREE LIST %d:\n"
1019                             "\n  ORDER (SIZE)  |  NUMBER"
1020                             "\n              ", flind);
1021                         for (pind = 0; pind < VM_NFREEPOOL; pind++)
1022                                 db_printf("  |  POOL %d", pind);
1023                         db_printf("\n--            ");
1024                         for (pind = 0; pind < VM_NFREEPOOL; pind++)
1025                                 db_printf("-- --      ");
1026                         db_printf("--\n");
1027                         for (oind = VM_NFREEORDER - 1; oind >= 0; oind--) {
1028                                 db_printf("  %2.2d (%6.6dK)", oind,
1029                                     1 << (PAGE_SHIFT - 10 + oind));
1030                                 for (pind = 0; pind < VM_NFREEPOOL; pind++) {
1031                                 fl = vm_phys_free_queues[dom][flind][pind];
1032                                         db_printf("  |  %6.6d", fl[oind].lcnt);
1033                                 }
1034                                 db_printf("\n");
1035                         }
1036                         db_printf("\n");
1037                 }
1038                 db_printf("\n");
1039         }
1040 }
1041 #endif