uvm_pglist.c revision 1.45.2.3
1 /* $NetBSD: uvm_pglist.c,v 1.45.2.3 2010/08/17 06:48:16 uebayasi Exp $ */ 2 3 /*- 4 * Copyright (c) 1997 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Jason R. Thorpe of the Numerical Aerospace Simulation Facility, 9 * NASA Ames Research Center. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in the 18 * documentation and/or other materials provided with the distribution. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 21 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 24 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 25 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 26 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 27 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 28 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 29 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 30 * POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33 /* 34 * uvm_pglist.c: pglist functions 35 */ 36 37 #include <sys/cdefs.h> 38 __KERNEL_RCSID(0, "$NetBSD: uvm_pglist.c,v 1.45.2.3 2010/08/17 06:48:16 uebayasi Exp $"); 39 40 #include <sys/param.h> 41 #include <sys/systm.h> 42 #include <sys/malloc.h> 43 #include <sys/proc.h> 44 45 #include <uvm/uvm.h> 46 #include <uvm/uvm_pdpolicy.h> 47 48 #ifdef VM_PAGE_ALLOC_MEMORY_STATS 49 #define STAT_INCR(v) (v)++ 50 #define STAT_DECR(v) do { \ 51 if ((v) == 0) \ 52 printf("%s:%d -- Already 0!\n", __FILE__, __LINE__); \ 53 else \ 54 (v)--; \ 55 } while (/*CONSTCOND*/ 0) 56 u_long uvm_pglistalloc_npages; 57 #else 58 #define STAT_INCR(v) 59 #define STAT_DECR(v) 60 #endif 61 62 /* 63 * uvm_pglistalloc: allocate a list of pages 64 * 65 * => allocated pages are placed onto an rlist. rlist is 66 * initialized by uvm_pglistalloc. 67 * => returns 0 on success or errno on failure 68 * => implementation allocates a single segment if any constraints are 69 * imposed by call arguments. 70 * => doesn't take into account clean non-busy pages on inactive list 71 * that could be used(?) 72 * => params: 73 * size the size of the allocation, rounded to page size. 74 * low the low address of the allowed allocation range. 75 * high the high address of the allowed allocation range. 76 * alignment memory must be aligned to this power-of-two boundary. 77 * boundary no segment in the allocation may cross this 78 * power-of-two boundary (relative to zero). 79 */ 80 81 static void 82 uvm_pglist_add(struct vm_page *pg, struct pglist *rlist) 83 { 84 int free_list, color, pgflidx; 85 #ifdef NOT_DEBUG 86 struct vm_page *tp; 87 #endif 88 89 KASSERT(mutex_owned(&uvm_fpageqlock)); 90 91 #if PGFL_NQUEUES != 2 92 #error uvm_pglistalloc needs to be updated 93 #endif 94 95 free_list = uvm_page_lookup_freelist(pg); 96 color = VM_PGCOLOR_BUCKET(pg); 97 pgflidx = (pg->flags & PG_ZERO) ? PGFL_ZEROS : PGFL_UNKNOWN; 98 #ifdef NOT_DEBUG 99 for (tp = LIST_FIRST(&uvm.page_free[ 100 free_list].pgfl_buckets[color].pgfl_queues[pgflidx]); 101 tp != NULL; 102 tp = LIST_NEXT(tp, pageq.list)) { 103 if (tp == pg) 104 break; 105 } 106 if (tp == NULL) 107 panic("uvm_pglistalloc: page not on freelist"); 108 #endif 109 LIST_REMOVE(pg, pageq.list); /* global */ 110 LIST_REMOVE(pg, listq.list); /* cpu */ 111 uvmexp.free--; 112 if (pg->flags & PG_ZERO) 113 uvmexp.zeropages--; 114 VM_FREE_PAGE_TO_CPU(pg)->pages[pgflidx]--; 115 pg->flags = PG_CLEAN; 116 pg->pqflags = 0; 117 pg->uobject = NULL; 118 pg->uanon = NULL; 119 TAILQ_INSERT_TAIL(rlist, pg, pageq.queue); 120 STAT_INCR(uvm_pglistalloc_npages); 121 } 122 123 static int 124 uvm_pglistalloc_c_ps(struct vm_physseg *ps, int num, paddr_t low, paddr_t high, 125 paddr_t alignment, paddr_t boundary, struct pglist *rlist) 126 { 127 int try, limit, tryidx, end, idx; 128 struct vm_page *pgs; 129 int pagemask; 130 #ifdef DEBUG 131 paddr_t idxpa, lastidxpa; 132 #if 0 133 int cidx = 0; /* XXX: GCC */ 134 #endif 135 #endif 136 #ifdef PGALLOC_VERBOSE 137 #if 0 138 printf("pgalloc: contig %d pgs from psi %ld\n", num, 139 (long)(ps - vm_physmem_store)); 140 #endif 141 #endif 142 143 KASSERT(mutex_owned(&uvm_fpageqlock)); 144 145 try = roundup(max(atop(low), ps->avail_start), atop(alignment)); 146 limit = min(atop(high), ps->avail_end); 147 pagemask = ~((boundary >> PAGE_SHIFT) - 1); 148 149 for (;;) { 150 if (try + num > limit) { 151 /* 152 * We've run past the allowable range. 153 */ 154 return (0); /* FAIL */ 155 } 156 if (boundary != 0 && 157 ((try ^ (try + num - 1)) & pagemask) != 0) { 158 /* 159 * Region crosses boundary. Jump to the boundary 160 * just crossed and ensure alignment. 161 */ 162 try = (try + num - 1) & pagemask; 163 try = roundup(try, atop(alignment)); 164 continue; 165 } 166 #ifdef DEBUG 167 /* 168 * Make sure this is a managed physical page. 169 */ 170 171 #if 0 172 if (vm_physseg_find(try, &cidx) != ps - vm_physmem_store) 173 panic("pgalloc contig: botch1"); 174 if (cidx != try - ps->start) 175 panic("pgalloc contig: botch2"); 176 #endif 177 #if 0 178 if (vm_physseg_find(try + num - 1, &cidx) != ps - vm_physmem_store) 179 panic("pgalloc contig: botch3"); 180 if (cidx != try - ps->start + num - 1) 181 panic("pgalloc contig: botch4"); 182 #endif 183 #endif 184 tryidx = try - ps->start; 185 end = tryidx + num; 186 pgs = ps->pgs; 187 188 /* 189 * Found a suitable starting page. See if the range is free. 190 */ 191 for (idx = tryidx; idx < end; idx++) { 192 if (VM_PAGE_IS_FREE(&pgs[idx]) == 0) 193 break; 194 195 #ifdef DEBUG 196 idxpa = VM_PAGE_TO_PHYS(&pgs[idx]); 197 if (idx > tryidx) { 198 lastidxpa = VM_PAGE_TO_PHYS(&pgs[idx - 1]); 199 if ((lastidxpa + PAGE_SIZE) != idxpa) { 200 /* 201 * Region not contiguous. 202 */ 203 panic("pgalloc contig: botch5"); 204 } 205 if (boundary != 0 && 206 ((lastidxpa ^ idxpa) & ~(boundary - 1)) 207 != 0) { 208 /* 209 * Region crosses boundary. 210 */ 211 panic("pgalloc contig: botch6"); 212 } 213 } 214 #endif 215 } 216 if (idx == end) 217 break; 218 219 try += atop(alignment); 220 } 221 222 /* 223 * we have a chunk of memory that conforms to the requested constraints. 224 */ 225 idx = tryidx; 226 while (idx < end) 227 uvm_pglist_add(&pgs[idx++], rlist); 228 229 #ifdef PGALLOC_VERBOSE 230 printf("got %d pgs\n", num); 231 #endif 232 return (num); /* number of pages allocated */ 233 } 234 235 static int 236 uvm_pglistalloc_contig(int num, paddr_t low, paddr_t high, paddr_t alignment, 237 paddr_t boundary, struct pglist *rlist) 238 { 239 int fl, psi; 240 struct vm_physseg *ps; 241 int error; 242 243 /* Default to "lose". */ 244 error = ENOMEM; 245 246 /* 247 * Block all memory allocation and lock the free list. 248 */ 249 mutex_spin_enter(&uvm_fpageqlock); 250 251 /* Are there even any free pages? */ 252 if (uvmexp.free <= (uvmexp.reserve_pagedaemon + uvmexp.reserve_kernel)) 253 goto out; 254 255 for (fl = 0; fl < VM_NFREELIST; fl++) { 256 #if (VM_PHYSSEG_STRAT == VM_PSTRAT_BIGFIRST) 257 for (psi = vm_nphysmem - 1 ; psi >= 0 ; psi--) 258 #else 259 for (psi = 0 ; psi < vm_nphysmem ; psi++) 260 #endif 261 { 262 ps = vm_physmem_ptrs[psi]; 263 264 if (ps->free_list != fl) 265 continue; 266 267 num -= uvm_pglistalloc_c_ps(ps, num, low, high, 268 alignment, boundary, rlist); 269 if (num == 0) { 270 #ifdef PGALLOC_VERBOSE 271 printf("pgalloc: %"PRIxMAX"-%"PRIxMAX"\n", 272 (uintmax_t) VM_PAGE_TO_PHYS(TAILQ_FIRST(rlist)), 273 (uintmax_t) VM_PAGE_TO_PHYS(TAILQ_LAST(rlist, pglist))); 274 #endif 275 error = 0; 276 goto out; 277 } 278 } 279 } 280 281 out: 282 /* 283 * check to see if we need to generate some free pages waking 284 * the pagedaemon. 285 */ 286 287 uvm_kick_pdaemon(); 288 mutex_spin_exit(&uvm_fpageqlock); 289 return (error); 290 } 291 292 static int 293 uvm_pglistalloc_s_ps(struct vm_physseg *ps, int num, paddr_t low, paddr_t high, 294 struct pglist *rlist) 295 { 296 int todo, limit, try; 297 struct vm_page *pg; 298 #ifdef DEBUG 299 #if 0 300 int cidx = 0; /* XXX: GCC */ 301 #endif 302 #endif 303 #ifdef PGALLOC_VERBOSE 304 #if 0 305 printf("pgalloc: simple %d pgs from psi %ld\n", num, 306 (long)(ps - vm_physmem_store)); 307 #endif 308 #endif 309 310 KASSERT(mutex_owned(&uvm_fpageqlock)); 311 312 todo = num; 313 limit = min(atop(high), ps->avail_end); 314 315 for (try = max(atop(low), ps->avail_start); 316 try < limit; try ++) { 317 #ifdef DEBUG 318 #if 0 319 if (vm_physseg_find(try, &cidx) != ps - vm_physmem_store) 320 panic("pgalloc simple: botch1"); 321 if (cidx != (try - ps->start)) 322 panic("pgalloc simple: botch2"); 323 #endif 324 #endif 325 pg = &ps->pgs[try - ps->start]; 326 if (VM_PAGE_IS_FREE(pg) == 0) 327 continue; 328 329 uvm_pglist_add(pg, rlist); 330 if (--todo == 0) 331 break; 332 } 333 334 #ifdef PGALLOC_VERBOSE 335 printf("got %d pgs\n", num - todo); 336 #endif 337 return (num - todo); /* number of pages allocated */ 338 } 339 340 static int 341 uvm_pglistalloc_simple(int num, paddr_t low, paddr_t high, 342 struct pglist *rlist, int waitok) 343 { 344 int fl, psi, error; 345 struct vm_physseg *ps; 346 347 /* Default to "lose". */ 348 error = ENOMEM; 349 350 again: 351 /* 352 * Block all memory allocation and lock the free list. 353 */ 354 mutex_spin_enter(&uvm_fpageqlock); 355 356 /* Are there even any free pages? */ 357 if (uvmexp.free <= (uvmexp.reserve_pagedaemon + uvmexp.reserve_kernel)) 358 goto out; 359 360 for (fl = 0; fl < VM_NFREELIST; fl++) { 361 #if (VM_PHYSSEG_STRAT == VM_PSTRAT_BIGFIRST) 362 for (psi = vm_nphysmem - 1 ; psi >= 0 ; psi--) 363 #else 364 for (psi = 0 ; psi < vm_nphysmem ; psi++) 365 #endif 366 { 367 ps = vm_physmem_ptrs[psi]; 368 369 if (ps->free_list != fl) 370 continue; 371 372 num -= uvm_pglistalloc_s_ps(ps, num, low, high, rlist); 373 if (num == 0) { 374 error = 0; 375 goto out; 376 } 377 } 378 379 } 380 381 out: 382 /* 383 * check to see if we need to generate some free pages waking 384 * the pagedaemon. 385 */ 386 387 uvm_kick_pdaemon(); 388 mutex_spin_exit(&uvm_fpageqlock); 389 390 if (error) { 391 if (waitok) { 392 /* XXX perhaps some time limitation? */ 393 #ifdef DEBUG 394 printf("pglistalloc waiting\n"); 395 #endif 396 uvm_wait("pglalloc"); 397 goto again; 398 } else 399 uvm_pglistfree(rlist); 400 } 401 #ifdef PGALLOC_VERBOSE 402 if (!error) 403 printf("pgalloc: %"PRIxMAX"..%"PRIxMAX"\n", 404 (uintmax_t) VM_PAGE_TO_PHYS(TAILQ_FIRST(rlist)), 405 (uintmax_t) VM_PAGE_TO_PHYS(TAILQ_LAST(rlist, pglist))); 406 #endif 407 return (error); 408 } 409 410 int 411 uvm_pglistalloc(psize_t size, paddr_t low, paddr_t high, paddr_t alignment, 412 paddr_t boundary, struct pglist *rlist, int nsegs, int waitok) 413 { 414 int num, res; 415 416 KASSERT((alignment & (alignment - 1)) == 0); 417 KASSERT((boundary & (boundary - 1)) == 0); 418 419 /* 420 * Our allocations are always page granularity, so our alignment 421 * must be, too. 422 */ 423 if (alignment < PAGE_SIZE) 424 alignment = PAGE_SIZE; 425 if (boundary != 0 && boundary < size) 426 return (EINVAL); 427 num = atop(round_page(size)); 428 low = roundup(low, alignment); 429 430 TAILQ_INIT(rlist); 431 432 if ((nsegs < size >> PAGE_SHIFT) || (alignment != PAGE_SIZE) || 433 (boundary != 0)) 434 res = uvm_pglistalloc_contig(num, low, high, alignment, 435 boundary, rlist); 436 else 437 res = uvm_pglistalloc_simple(num, low, high, rlist, waitok); 438 439 return (res); 440 } 441 442 /* 443 * uvm_pglistfree: free a list of pages 444 * 445 * => pages should already be unmapped 446 */ 447 448 void 449 uvm_pglistfree(struct pglist *list) 450 { 451 struct uvm_cpu *ucpu; 452 struct vm_page *pg; 453 int index, color, queue; 454 bool iszero; 455 456 /* 457 * Lock the free list and free each page. 458 */ 459 460 mutex_spin_enter(&uvm_fpageqlock); 461 ucpu = curcpu()->ci_data.cpu_uvm; 462 while ((pg = TAILQ_FIRST(list)) != NULL) { 463 KASSERT(!uvmpdpol_pageisqueued_p(pg)); 464 TAILQ_REMOVE(list, pg, pageq.queue); 465 iszero = (pg->flags & PG_ZERO); 466 pg->pqflags = PQ_FREE; 467 #ifdef DEBUG 468 pg->uobject = (void *)0xdeadbeef; 469 pg->uanon = (void *)0xdeadbeef; 470 #endif /* DEBUG */ 471 #ifdef DEBUG 472 if (iszero) 473 uvm_pagezerocheck(pg); 474 #endif /* DEBUG */ 475 index = uvm_page_lookup_freelist(pg); 476 color = VM_PGCOLOR_BUCKET(pg); 477 queue = iszero ? PGFL_ZEROS : PGFL_UNKNOWN; 478 pg->offset = (uintptr_t)ucpu; 479 LIST_INSERT_HEAD(&uvm.page_free[index].pgfl_buckets[color]. 480 pgfl_queues[queue], pg, pageq.list); 481 LIST_INSERT_HEAD(&ucpu->page_free[index].pgfl_buckets[color]. 482 pgfl_queues[queue], pg, listq.list); 483 uvmexp.free++; 484 if (iszero) 485 uvmexp.zeropages++; 486 ucpu->pages[queue]++; 487 STAT_DECR(uvm_pglistalloc_npages); 488 } 489 if (ucpu->pages[PGFL_ZEROS] < ucpu->pages[PGFL_UNKNOWN]) 490 ucpu->page_idle_zero = vm_page_zero_enable; 491 mutex_spin_exit(&uvm_fpageqlock); 492 } 493
Indexes created Wed Oct 22 00:09:40 GMT 2025