1 /* 2 * linux/mm/page_alloc.c 3 * 4 * Manages the free list, the system allocates free pages here. 5 * Note that kmalloc() lives in slab.c 6 * 7 * Copyright (C) 1991, 1992, 1993, 1994 Linus Torvalds 8 * Swap reorganised 29.12.95, Stephen Tweedie 9 * Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999 10 * Reshaped it to be a zoned allocator, Ingo Molnar, Red Hat, 1999 11 * Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999 12 * Zone balancing, Kanoj Sarcar, SGI, Jan 2000 13 * Per cpu hot/cold page lists, bulk allocation, Martin J. Bligh, Sept 2002 14 * (lots of bits borrowed from Ingo Molnar & Andrew Morton) 15 */ 16 17 #include <linux/config.h> 18 #include <linux/stddef.h> 19 #include <linux/mm.h> 20 #include <linux/swap.h> 21 #include <linux/interrupt.h> 22 #include <linux/pagemap.h> 23 #include <linux/bootmem.h> 24 #include <linux/compiler.h> 25 #include <linux/module.h> 26 #include <linux/suspend.h> 27 #include <linux/pagevec.h> 28 #include <linux/blkdev.h> 29 #include <linux/slab.h> 30 #include <linux/notifier.h> 31 #include <linux/topology.h> 32 #include <linux/sysctl.h> 33 #include <linux/cpu.h> 34 35 #include <asm/tlbflush.h> 36 37 DECLARE_BITMAP(node_online_map, MAX_NUMNODES); 38 struct pglist_data *pgdat_list; 39 unsigned long totalram_pages; 40 unsigned long totalhigh_pages; 41 long nr_swap_pages; 42 int numnodes = 1; 43 int sysctl_lower_zone_protection = 0; 44 45 EXPORT_SYMBOL(totalram_pages); 46 EXPORT_SYMBOL(nr_swap_pages); 47 48 /* 49 * Used by page_zone() to look up the address of the struct zone whose 50 * id is encoded in the upper bits of page->flags 51 */ 52 struct zone *zone_table[1 << (ZONES_SHIFT + NODES_SHIFT)]; 53 EXPORT_SYMBOL(zone_table); 54 55 static char *zone_names[MAX_NR_ZONES] = { "DMA", "Normal", "HighMem" }; 56 int min_free_kbytes = 1024; 57 58 static unsigned long __initdata nr_kernel_pages; 59 static unsigned long __initdata nr_all_pages; 60 61 /* 62 * Temporary debugging check for pages not lying within a given zone. 63 */ 64 static int bad_range(struct zone *zone, struct page *page) 65 { 66 if (page_to_pfn(page) >= zone->zone_start_pfn + zone->spanned_pages) 67 return 1; 68 if (page_to_pfn(page) < zone->zone_start_pfn) 69 return 1; 70 if (zone != page_zone(page)) 71 return 1; 72 return 0; 73 } 74 75 static void bad_page(const char *function, struct page *page) 76 { 77 printk(KERN_EMERG "Bad page state at %s (in process '%s', page %p)\n", 78 function, current->comm, page); 79 printk(KERN_EMERG "flags:0x%08lx mapping:%p mapcount:%d count:%d\n", 80 (unsigned long)page->flags, page->mapping, 81 (int)page->mapcount, page_count(page)); 82 printk(KERN_EMERG "Backtrace:\n"); 83 dump_stack(); 84 printk(KERN_EMERG "Trying to fix it up, but a reboot is needed\n"); 85 page->flags &= ~(1 << PG_private | 86 1 << PG_locked | 87 1 << PG_lru | 88 1 << PG_active | 89 1 << PG_dirty | 90 1 << PG_maplock | 91 1 << PG_anon | 92 1 << PG_swapcache | 93 1 << PG_writeback); 94 set_page_count(page, 0); 95 page->mapping = NULL; 96 page->mapcount = 0; 97 } 98 99 #ifndef CONFIG_HUGETLB_PAGE 100 #define prep_compound_page(page, order) do { } while (0) 101 #define destroy_compound_page(page, order) do { } while (0) 102 #else 103 /* 104 * Higher-order pages are called "compound pages". They are structured thusly: 105 * 106 * The first PAGE_SIZE page is called the "head page". 107 * 108 * The remaining PAGE_SIZE pages are called "tail pages". 109 * 110 * All pages have PG_compound set. All pages have their ->private pointing at 111 * the head page (even the head page has this). 112 * 113 * The first tail page's ->mapping, if non-zero, holds the address of the 114 * compound page's put_page() function. 115 * 116 * The order of the allocation is stored in the first tail page's ->index 117 * This is only for debug at present. This usage means that zero-order pages 118 * may not be compound. 119 */ 120 static void prep_compound_page(struct page *page, unsigned long order) 121 { 122 int i; 123 int nr_pages = 1 << order; 124 125 page[1].mapping = NULL; 126 page[1].index = order; 127 for (i = 0; i < nr_pages; i++) { 128 struct page *p = page + i; 129 130 SetPageCompound(p); 131 p->private = (unsigned long)page; 132 } 133 } 134 135 static void destroy_compound_page(struct page *page, unsigned long order) 136 { 137 int i; 138 int nr_pages = 1 << order; 139 140 if (!PageCompound(page)) 141 return; 142 143 if (page[1].index != order) 144 bad_page(__FUNCTION__, page); 145 146 for (i = 0; i < nr_pages; i++) { 147 struct page *p = page + i; 148 149 if (!PageCompound(p)) 150 bad_page(__FUNCTION__, page); 151 if (p->private != (unsigned long)page) 152 bad_page(__FUNCTION__, page); 153 ClearPageCompound(p); 154 } 155 } 156 #endif /* CONFIG_HUGETLB_PAGE */ 157 158 /* 159 * Freeing function for a buddy system allocator. 160 * 161 * The concept of a buddy system is to maintain direct-mapped table 162 * (containing bit values) for memory blocks of various "orders". 163 * The bottom level table contains the map for the smallest allocatable 164 * units of memory (here, pages), and each level above it describes 165 * pairs of units from the levels below, hence, "buddies". 166 * At a high level, all that happens here is marking the table entry 167 * at the bottom level available, and propagating the changes upward 168 * as necessary, plus some accounting needed to play nicely with other 169 * parts of the VM system. 170 * At each level, we keep one bit for each pair of blocks, which 171 * is set to 1 iff only one of the pair is allocated. So when we 172 * are allocating or freeing one, we can derive the state of the 173 * other. That is, if we allocate a small block, and both were 174 * free, the remainder of the region must be split into blocks. 175 * If a block is freed, and its buddy is also free, then this 176 * triggers coalescing into a block of larger size. 177 * 178 * -- wli 179 */ 180 181 static inline void __free_pages_bulk (struct page *page, struct page *base, 182 struct zone *zone, struct free_area *area, unsigned int order) 183 { 184 unsigned long page_idx, index, mask; 185 186 if (order) 187 destroy_compound_page(page, order); 188 mask = (~0UL) << order; 189 page_idx = page - base; 190 if (page_idx & ~mask) 191 BUG(); 192 index = page_idx >> (1 + order); 193 194 zone->free_pages += 1 << order; 195 while (order < MAX_ORDER-1) { 196 struct page *buddy1, *buddy2; 197 198 BUG_ON(area >= zone->free_area + MAX_ORDER); 199 if (!__test_and_change_bit(index, area->map)) 200 /* 201 * the buddy page is still allocated. 202 */ 203 break; 204 205 /* Move the buddy up one level. */ 206 buddy1 = base + (page_idx ^ (1 << order)); 207 buddy2 = base + page_idx; 208 BUG_ON(bad_range(zone, buddy1)); 209 BUG_ON(bad_range(zone, buddy2)); 210 list_del(&buddy1->lru); 211 mask <<= 1; 212 order++; 213 area++; 214 index >>= 1; 215 page_idx &= mask; 216 } 217 list_add(&(base + page_idx)->lru, &area->free_list); 218 } 219 220 static inline void free_pages_check(const char *function, struct page *page) 221 { 222 if ( page_mapped(page) || 223 page->mapping != NULL || 224 page_count(page) != 0 || 225 (page->flags & ( 226 1 << PG_lru | 227 1 << PG_private | 228 1 << PG_locked | 229 1 << PG_active | 230 1 << PG_reclaim | 231 1 << PG_slab | 232 1 << PG_maplock | 233 1 << PG_anon | 234 1 << PG_swapcache | 235 1 << PG_writeback ))) 236 bad_page(function, page); 237 if (PageDirty(page)) 238 ClearPageDirty(page); 239 } 240 241 /* 242 * Frees a list of pages. 243 * Assumes all pages on list are in same zone, and of same order. 244 * count is the number of pages to free, or 0 for all on the list. 245 * 246 * If the zone was previously in an "all pages pinned" state then look to 247 * see if this freeing clears that state. 248 * 249 * And clear the zone's pages_scanned counter, to hold off the "all pages are 250 * pinned" detection logic. 251 */ 252 static int 253 free_pages_bulk(struct zone *zone, int count, 254 struct list_head *list, unsigned int order) 255 { 256 unsigned long flags; 257 struct free_area *area; 258 struct page *base, *page = NULL; 259 int ret = 0; 260 261 base = zone->zone_mem_map; 262 area = zone->free_area + order; 263 spin_lock_irqsave(&zone->lock, flags); 264 zone->all_unreclaimable = 0; 265 zone->pages_scanned = 0; 266 while (!list_empty(list) && count--) { 267 page = list_entry(list->prev, struct page, lru); 268 /* have to delete it as __free_pages_bulk list manipulates */ 269 list_del(&page->lru); 270 __free_pages_bulk(page, base, zone, area, order); 271 ret++; 272 } 273 spin_unlock_irqrestore(&zone->lock, flags); 274 return ret; 275 } 276 277 void __free_pages_ok(struct page *page, unsigned int order) 278 { 279 LIST_HEAD(list); 280 int i; 281 282 mod_page_state(pgfree, 1 << order); 283 for (i = 0 ; i < (1 << order) ; ++i) 284 free_pages_check(__FUNCTION__, page + i); 285 list_add(&page->lru, &list); 286 kernel_map_pages(page, 1<<order, 0); 287 free_pages_bulk(page_zone(page), 1, &list, order); 288 } 289 290 #define MARK_USED(index, order, area) \ 291 __change_bit((index) >> (1+(order)), (area)->map) 292 293 /* 294 * The order of subdivision here is critical for the IO subsystem. 295 * Please do not alter this order without good reasons and regression 296 * testing. Specifically, as large blocks of memory are subdivided, 297 * the order in which smaller blocks are delivered depends on the order 298 * they're subdivided in this function. This is the primary factor 299 * influencing the order in which pages are delivered to the IO 300 * subsystem according to empirical testing, and this is also justified 301 * by considering the behavior of a buddy system containing a single 302 * large block of memory acted on by a series of small allocations. 303 * This behavior is a critical factor in sglist merging's success. 304 * 305 * -- wli 306 */ 307 static inline struct page * 308 expand(struct zone *zone, struct page *page, 309 unsigned long index, int low, int high, struct free_area *area) 310 { 311 unsigned long size = 1 << high; 312 313 while (high > low) { 314 area--; 315 high--; 316 size >>= 1; 317 BUG_ON(bad_range(zone, &page[size])); 318 list_add(&page[size].lru, &area->free_list); 319 MARK_USED(index + size, high, area); 320 } 321 return page; 322 } 323 324 static inline void set_page_refs(struct page *page, int order) 325 { 326 #ifdef CONFIG_MMU 327 set_page_count(page, 1); 328 #else 329 int i; 330 331 /* 332 * We need to reference all the pages for this order, otherwise if 333 * anyone accesses one of the pages with (get/put) it will be freed. 334 */ 335 for (i = 0; i < (1 << order); i++) 336 set_page_count(page+i, 1); 337 #endif /* CONFIG_MMU */ 338 } 339 340 /* 341 * This page is about to be returned from the page allocator 342 */ 343 static void prep_new_page(struct page *page, int order) 344 { 345 if (page->mapping || page_mapped(page) || 346 (page->flags & ( 347 1 << PG_private | 348 1 << PG_locked | 349 1 << PG_lru | 350 1 << PG_active | 351 1 << PG_dirty | 352 1 << PG_reclaim | 353 1 << PG_maplock | 354 1 << PG_anon | 355 1 << PG_swapcache | 356 1 << PG_writeback ))) 357 bad_page(__FUNCTION__, page); 358 359 page->flags &= ~(1 << PG_uptodate | 1 << PG_error | 360 1 << PG_referenced | 1 << PG_arch_1 | 361 1 << PG_checked | 1 << PG_mappedtodisk); 362 page->private = 0; 363 set_page_refs(page, order); 364 } 365 366 /* 367 * Do the hard work of removing an element from the buddy allocator. 368 * Call me with the zone->lock already held. 369 */ 370 static struct page *__rmqueue(struct zone *zone, unsigned int order) 371 { 372 struct free_area * area; 373 unsigned int current_order; 374 struct page *page; 375 unsigned int index; 376 377 for (current_order = order; current_order < MAX_ORDER; ++current_order) { 378 area = zone->free_area + current_order; 379 if (list_empty(&area->free_list)) 380 continue; 381 382 page = list_entry(area->free_list.next, struct page, lru); 383 list_del(&page->lru); 384 index = page - zone->zone_mem_map; 385 if (current_order != MAX_ORDER-1) 386 MARK_USED(index, current_order, area); 387 zone->free_pages -= 1UL << order; 388 return expand(zone, page, index, order, current_order, area); 389 } 390 391 return NULL; 392 } 393 394 /* 395 * Obtain a specified number of elements from the buddy allocator, all under 396 * a single hold of the lock, for efficiency. Add them to the supplied list. 397 * Returns the number of new pages which were placed at *list. 398 */ 399 static int rmqueue_bulk(struct zone *zone, unsigned int order, 400 unsigned long count, struct list_head *list) 401 { 402 unsigned long flags; 403 int i; 404 int allocated = 0; 405 struct page *page; 406 407 spin_lock_irqsave(&zone->lock, flags); 408 for (i = 0; i < count; ++i) { 409 page = __rmqueue(zone, order); 410 if (page == NULL) 411 break; 412 allocated++; 413 list_add_tail(&page->lru, list); 414 } 415 spin_unlock_irqrestore(&zone->lock, flags); 416 return allocated; 417 } 418 419 #if defined(CONFIG_PM) || defined(CONFIG_HOTPLUG_CPU) 420 static void __drain_pages(unsigned int cpu) 421 { 422 struct zone *zone; 423 int i; 424 425 for_each_zone(zone) { 426 struct per_cpu_pageset *pset; 427 428 pset = &zone->pageset[cpu]; 429 for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) { 430 struct per_cpu_pages *pcp; 431 432 pcp = &pset->pcp[i]; 433 pcp->count -= free_pages_bulk(zone, pcp->count, 434 &pcp->list, 0); 435 } 436 } 437 } 438 #endif /* CONFIG_PM || CONFIG_HOTPLUG_CPU */ 439 440 #ifdef CONFIG_PM 441 int is_head_of_free_region(struct page *page) 442 { 443 struct zone *zone = page_zone(page); 444 unsigned long flags; 445 int order; 446 struct list_head *curr; 447 448 /* 449 * Should not matter as we need quiescent system for 450 * suspend anyway, but... 451 */ 452 spin_lock_irqsave(&zone->lock, flags); 453 for (order = MAX_ORDER - 1; order >= 0; --order) 454 list_for_each(curr, &zone->free_area[order].free_list) 455 if (page == list_entry(curr, struct page, lru)) { 456 spin_unlock_irqrestore(&zone->lock, flags); 457 return 1 << order; 458 } 459 spin_unlock_irqrestore(&zone->lock, flags); 460 return 0; 461 } 462 463 /* 464 * Spill all of this CPU's per-cpu pages back into the buddy allocator. 465 */ 466 void drain_local_pages(void) 467 { 468 unsigned long flags; 469 470 local_irq_save(flags); 471 __drain_pages(smp_processor_id()); 472 local_irq_restore(flags); 473 } 474 #endif /* CONFIG_PM */ 475 476 static void zone_statistics(struct zonelist *zonelist, struct zone *z) 477 { 478 #ifdef CONFIG_NUMA 479 unsigned long flags; 480 int cpu; 481 pg_data_t *pg = z->zone_pgdat; 482 pg_data_t *orig = zonelist->zones[0]->zone_pgdat; 483 struct per_cpu_pageset *p; 484 485 local_irq_save(flags); 486 cpu = smp_processor_id(); 487 p = &z->pageset[cpu]; 488 if (pg == orig) { 489 z->pageset[cpu].numa_hit++; 490 } else { 491 p->numa_miss++; 492 zonelist->zones[0]->pageset[cpu].numa_foreign++; 493 } 494 if (pg == NODE_DATA(numa_node_id())) 495 p->local_node++; 496 else 497 p->other_node++; 498 local_irq_restore(flags); 499 #endif 500 } 501 502 /* 503 * Free a 0-order page 504 */ 505 static void FASTCALL(free_hot_cold_page(struct page *page, int cold)); 506 static void fastcall free_hot_cold_page(struct page *page, int cold) 507 { 508 struct zone *zone = page_zone(page); 509 struct per_cpu_pages *pcp; 510 unsigned long flags; 511 512 kernel_map_pages(page, 1, 0); 513 inc_page_state(pgfree); 514 free_pages_check(__FUNCTION__, page); 515 pcp = &zone->pageset[get_cpu()].pcp[cold]; 516 local_irq_save(flags); 517 if (pcp->count >= pcp->high) 518 pcp->count -= free_pages_bulk(zone, pcp->batch, &pcp->list, 0); 519 list_add(&page->lru, &pcp->list); 520 pcp->count++; 521 local_irq_restore(flags); 522 put_cpu(); 523 } 524 525 void fastcall free_hot_page(struct page *page) 526 { 527 free_hot_cold_page(page, 0); 528 } 529 530 void fastcall free_cold_page(struct page *page) 531 { 532 free_hot_cold_page(page, 1); 533 } 534 535 /* 536 * Really, prep_compound_page() should be called from __rmqueue_bulk(). But 537 * we cheat by calling it from here, in the order > 0 path. Saves a branch 538 * or two. 539 */ 540 541 static struct page * 542 buffered_rmqueue(struct zone *zone, int order, int gfp_flags) 543 { 544 unsigned long flags; 545 struct page *page = NULL; 546 int cold = !!(gfp_flags & __GFP_COLD); 547 548 if (order == 0) { 549 struct per_cpu_pages *pcp; 550 551 pcp = &zone->pageset[get_cpu()].pcp[cold]; 552 local_irq_save(flags); 553 if (pcp->count <= pcp->low) 554 pcp->count += rmqueue_bulk(zone, 0, 555 pcp->batch, &pcp->list); 556 if (pcp->count) { 557 page = list_entry(pcp->list.next, struct page, lru); 558 list_del(&page->lru); 559 pcp->count--; 560 } 561 local_irq_restore(flags); 562 put_cpu(); 563 } 564 565 if (page == NULL) { 566 spin_lock_irqsave(&zone->lock, flags); 567 page = __rmqueue(zone, order); 568 spin_unlock_irqrestore(&zone->lock, flags); 569 } 570 571 if (page != NULL) { 572 BUG_ON(bad_range(zone, page)); 573 mod_page_state_zone(zone, pgalloc, 1 << order); 574 prep_new_page(page, order); 575 if (order && (gfp_flags & __GFP_COMP)) 576 prep_compound_page(page, order); 577 } 578 return page; 579 } 580 581 /* 582 * This is the 'heart' of the zoned buddy allocator. 583 * 584 * Herein lies the mysterious "incremental min". That's the 585 * 586 * local_low = z->pages_low; 587 * min += local_low; 588 * 589 * thing. The intent here is to provide additional protection to low zones for 590 * allocation requests which _could_ use higher zones. So a GFP_HIGHMEM 591 * request is not allowed to dip as deeply into the normal zone as a GFP_KERNEL 592 * request. This preserves additional space in those lower zones for requests 593 * which really do need memory from those zones. It means that on a decent 594 * sized machine, GFP_HIGHMEM and GFP_KERNEL requests basically leave the DMA 595 * zone untouched. 596 */ 597 struct page * fastcall 598 __alloc_pages(unsigned int gfp_mask, unsigned int order, 599 struct zonelist *zonelist) 600 { 601 const int wait = gfp_mask & __GFP_WAIT; 602 unsigned long min; 603 struct zone **zones; 604 struct page *page; 605 struct reclaim_state reclaim_state; 606 struct task_struct *p = current; 607 int i; 608 int alloc_type; 609 int do_retry; 610 611 might_sleep_if(wait); 612 613 zones = zonelist->zones; /* the list of zones suitable for gfp_mask */ 614 if (zones[0] == NULL) /* no zones in the zonelist */ 615 return NULL; 616 617 alloc_type = zone_idx(zones[0]); 618 619 /* Go through the zonelist once, looking for a zone with enough free */ 620 for (i = 0; zones[i] != NULL; i++) { 621 struct zone *z = zones[i]; 622 623 min = (1<<order) + z->protection[alloc_type]; 624 625 /* 626 * We let real-time tasks dip their real-time paws a little 627 * deeper into reserves. 628 */ 629 if (rt_task(p)) 630 min -= z->pages_low >> 1; 631 632 if (z->free_pages >= min || 633 (!wait && z->free_pages >= z->pages_high)) { 634 page = buffered_rmqueue(z, order, gfp_mask); 635 if (page) { 636 zone_statistics(zonelist, z); 637 goto got_pg; 638 } 639 } 640 } 641 642 /* we're somewhat low on memory, failed to find what we needed */ 643 for (i = 0; zones[i] != NULL; i++) 644 wakeup_kswapd(zones[i]); 645 646 /* Go through the zonelist again, taking __GFP_HIGH into account */ 647 for (i = 0; zones[i] != NULL; i++) { 648 struct zone *z = zones[i]; 649 650 min = (1<<order) + z->protection[alloc_type]; 651 652 if (gfp_mask & __GFP_HIGH) 653 min -= z->pages_low >> 2; 654 if (rt_task(p)) 655 min -= z->pages_low >> 1; 656 657 if (z->free_pages >= min || 658 (!wait && z->free_pages >= z->pages_high)) { 659 page = buffered_rmqueue(z, order, gfp_mask); 660 if (page) { 661 zone_statistics(zonelist, z); 662 goto got_pg; 663 } 664 } 665 } 666 667 /* here we're in the low on memory slow path */ 668 669 rebalance: 670 if ((p->flags & (PF_MEMALLOC | PF_MEMDIE)) && !in_interrupt()) { 671 /* go through the zonelist yet again, ignoring mins */ 672 for (i = 0; zones[i] != NULL; i++) { 673 struct zone *z = zones[i]; 674 675 page = buffered_rmqueue(z, order, gfp_mask); 676 if (page) { 677 zone_statistics(zonelist, z); 678 goto got_pg; 679 } 680 } 681 goto nopage; 682 } 683 684 /* Atomic allocations - we can't balance anything */ 685 if (!wait) 686 goto nopage; 687 688 p->flags |= PF_MEMALLOC; 689 reclaim_state.reclaimed_slab = 0; 690 p->reclaim_state = &reclaim_state; 691 692 try_to_free_pages(zones, gfp_mask, order); 693 694 p->reclaim_state = NULL; 695 p->flags &= ~PF_MEMALLOC; 696 697 /* go through the zonelist yet one more time */ 698 for (i = 0; zones[i] != NULL; i++) { 699 struct zone *z = zones[i]; 700 701 min = (1UL << order) + z->protection[alloc_type]; 702 703 if (z->free_pages >= min || 704 (!wait && z->free_pages >= z->pages_high)) { 705 page = buffered_rmqueue(z, order, gfp_mask); 706 if (page) { 707 zone_statistics(zonelist, z); 708 goto got_pg; 709 } 710 } 711 } 712 713 /* 714 * Don't let big-order allocations loop unless the caller explicitly 715 * requests that. Wait for some write requests to complete then retry. 716 * 717 * In this implementation, __GFP_REPEAT means __GFP_NOFAIL, but that 718 * may not be true in other implementations. 719 */ 720 do_retry = 0; 721 if (!(gfp_mask & __GFP_NORETRY)) { 722 if ((order <= 3) || (gfp_mask & __GFP_REPEAT)) 723 do_retry = 1; 724 if (gfp_mask & __GFP_NOFAIL) 725 do_retry = 1; 726 } 727 if (do_retry) { 728 blk_congestion_wait(WRITE, HZ/50); 729 goto rebalance; 730 } 731 732 nopage: 733 if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) { 734 printk(KERN_WARNING "%s: page allocation failure." 735 " order:%d, mode:0x%x\n", 736 p->comm, order, gfp_mask); 737 dump_stack(); 738 } 739 return NULL; 740 got_pg: 741 kernel_map_pages(page, 1 << order, 1); 742 return page; 743 } 744 745 EXPORT_SYMBOL(__alloc_pages); 746 747 /* 748 * Common helper functions. 749 */ 750 fastcall unsigned long __get_free_pages(unsigned int gfp_mask, unsigned int order) 751 { 752 struct page * page; 753 page = alloc_pages(gfp_mask, order); 754 if (!page) 755 return 0; 756 return (unsigned long) page_address(page); 757 } 758 759 EXPORT_SYMBOL(__get_free_pages); 760 761 fastcall unsigned long get_zeroed_page(unsigned int gfp_mask) 762 { 763 struct page * page; 764 765 /* 766 * get_zeroed_page() returns a 32-bit address, which cannot represent 767 * a highmem page 768 */ 769 BUG_ON(gfp_mask & __GFP_HIGHMEM); 770 771 page = alloc_pages(gfp_mask, 0); 772 if (page) { 773 void *address = page_address(page); 774 clear_page(address); 775 return (unsigned long) address; 776 } 777 return 0; 778 } 779 780 EXPORT_SYMBOL(get_zeroed_page); 781 782 void __pagevec_free(struct pagevec *pvec) 783 { 784 int i = pagevec_count(pvec); 785 786 while (--i >= 0) 787 free_hot_cold_page(pvec->pages[i], pvec->cold); 788 } 789 790 fastcall void __free_pages(struct page *page, unsigned int order) 791 { 792 if (!PageReserved(page) && put_page_testzero(page)) { 793 if (order == 0) 794 free_hot_page(page); 795 else 796 __free_pages_ok(page, order); 797 } 798 } 799 800 EXPORT_SYMBOL(__free_pages); 801 802 fastcall void free_pages(unsigned long addr, unsigned int order) 803 { 804 if (addr != 0) { 805 BUG_ON(!virt_addr_valid(addr)); 806 __free_pages(virt_to_page(addr), order); 807 } 808 } 809 810 EXPORT_SYMBOL(free_pages); 811 812 /* 813 * Total amount of free (allocatable) RAM: 814 */ 815 unsigned int nr_free_pages(void) 816 { 817 unsigned int sum = 0; 818 struct zone *zone; 819 820 for_each_zone(zone) 821 sum += zone->free_pages; 822 823 return sum; 824 } 825 826 EXPORT_SYMBOL(nr_free_pages); 827 828 #ifdef CONFIG_NUMA 829 unsigned int nr_free_pages_pgdat(pg_data_t *pgdat) 830 { 831 unsigned int i, sum = 0; 832 833 for (i = 0; i < MAX_NR_ZONES; i++) 834 sum += pgdat->node_zones[i].free_pages; 835 836 return sum; 837 } 838 #endif 839 840 static unsigned int nr_free_zone_pages(int offset) 841 { 842 pg_data_t *pgdat; 843 unsigned int sum = 0; 844 845 for_each_pgdat(pgdat) { 846 struct zonelist *zonelist = pgdat->node_zonelists + offset; 847 struct zone **zonep = zonelist->zones; 848 struct zone *zone; 849 850 for (zone = *zonep++; zone; zone = *zonep++) { 851 unsigned long size = zone->present_pages; 852 unsigned long high = zone->pages_high; 853 if (size > high) 854 sum += size - high; 855 } 856 } 857 858 return sum; 859 } 860 861 /* 862 * Amount of free RAM allocatable within ZONE_DMA and ZONE_NORMAL 863 */ 864 unsigned int nr_free_buffer_pages(void) 865 { 866 return nr_free_zone_pages(GFP_USER & GFP_ZONEMASK); 867 } 868 869 /* 870 * Amount of free RAM allocatable within all zones 871 */ 872 unsigned int nr_free_pagecache_pages(void) 873 { 874 return nr_free_zone_pages(GFP_HIGHUSER & GFP_ZONEMASK); 875 } 876 877 #ifdef CONFIG_HIGHMEM 878 unsigned int nr_free_highpages (void) 879 { 880 pg_data_t *pgdat; 881 unsigned int pages = 0; 882 883 for_each_pgdat(pgdat) 884 pages += pgdat->node_zones[ZONE_HIGHMEM].free_pages; 885 886 return pages; 887 } 888 #endif 889 890 #ifdef CONFIG_NUMA 891 static void show_node(struct zone *zone) 892 { 893 printk("Node %d ", zone->zone_pgdat->node_id); 894 } 895 #else 896 #define show_node(zone) do { } while (0) 897 #endif 898 899 /* 900 * Accumulate the page_state information across all CPUs. 901 * The result is unavoidably approximate - it can change 902 * during and after execution of this function. 903 */ 904 DEFINE_PER_CPU(struct page_state, page_states) = {0}; 905 EXPORT_PER_CPU_SYMBOL(page_states); 906 907 atomic_t nr_pagecache = ATOMIC_INIT(0); 908 EXPORT_SYMBOL(nr_pagecache); 909 #ifdef CONFIG_SMP 910 DEFINE_PER_CPU(long, nr_pagecache_local) = 0; 911 #endif 912 913 void __get_page_state(struct page_state *ret, int nr) 914 { 915 int cpu = 0; 916 917 memset(ret, 0, sizeof(*ret)); 918 while (cpu < NR_CPUS) { 919 unsigned long *in, *out, off; 920 921 if (!cpu_possible(cpu)) { 922 cpu++; 923 continue; 924 } 925 926 in = (unsigned long *)&per_cpu(page_states, cpu); 927 cpu++; 928 if (cpu < NR_CPUS && cpu_possible(cpu)) 929 prefetch(&per_cpu(page_states, cpu)); 930 out = (unsigned long *)ret; 931 for (off = 0; off < nr; off++) 932 *out++ += *in++; 933 } 934 } 935 936 void get_page_state(struct page_state *ret) 937 { 938 int nr; 939 940 nr = offsetof(struct page_state, GET_PAGE_STATE_LAST); 941 nr /= sizeof(unsigned long); 942 943 __get_page_state(ret, nr + 1); 944 } 945 946 void get_full_page_state(struct page_state *ret) 947 { 948 __get_page_state(ret, sizeof(*ret) / sizeof(unsigned long)); 949 } 950 951 unsigned long __read_page_state(unsigned offset) 952 { 953 unsigned long ret = 0; 954 int cpu; 955 956 for (cpu = 0; cpu < NR_CPUS; cpu++) { 957 unsigned long in; 958 959 if (!cpu_possible(cpu)) 960 continue; 961 962 in = (unsigned long)&per_cpu(page_states, cpu) + offset; 963 ret += *((unsigned long *)in); 964 } 965 return ret; 966 } 967 968 void get_zone_counts(unsigned long *active, 969 unsigned long *inactive, unsigned long *free) 970 { 971 struct zone *zone; 972 973 *active = 0; 974 *inactive = 0; 975 *free = 0; 976 for_each_zone(zone) { 977 *active += zone->nr_active; 978 *inactive += zone->nr_inactive; 979 *free += zone->free_pages; 980 } 981 } 982 983 void si_meminfo(struct sysinfo *val) 984 { 985 val->totalram = totalram_pages; 986 val->sharedram = 0; 987 val->freeram = nr_free_pages(); 988 val->bufferram = nr_blockdev_pages(); 989 #ifdef CONFIG_HIGHMEM 990 val->totalhigh = totalhigh_pages; 991 val->freehigh = nr_free_highpages(); 992 #else 993 val->totalhigh = 0; 994 val->freehigh = 0; 995 #endif 996 val->mem_unit = PAGE_SIZE; 997 } 998 999 EXPORT_SYMBOL(si_meminfo); 1000 1001 #ifdef CONFIG_NUMA 1002 void si_meminfo_node(struct sysinfo *val, int nid) 1003 { 1004 pg_data_t *pgdat = NODE_DATA(nid); 1005 1006 val->totalram = pgdat->node_present_pages; 1007 val->freeram = nr_free_pages_pgdat(pgdat); 1008 val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages; 1009 val->freehigh = pgdat->node_zones[ZONE_HIGHMEM].free_pages; 1010 val->mem_unit = PAGE_SIZE; 1011 } 1012 #endif 1013 1014 #define K(x) ((x) << (PAGE_SHIFT-10)) 1015 1016 /* 1017 * Show free area list (used inside shift_scroll-lock stuff) 1018 * We also calculate the percentage fragmentation. We do this by counting the 1019 * memory on each free list with the exception of the first item on the list. 1020 */ 1021 void show_free_areas(void) 1022 { 1023 struct page_state ps; 1024 int cpu, temperature; 1025 unsigned long active; 1026 unsigned long inactive; 1027 unsigned long free; 1028 struct zone *zone; 1029 1030 for_each_zone(zone) { 1031 show_node(zone); 1032 printk("%s per-cpu:", zone->name); 1033 1034 if (!zone->present_pages) { 1035 printk(" empty\n"); 1036 continue; 1037 } else 1038 printk("\n"); 1039 1040 for (cpu = 0; cpu < NR_CPUS; ++cpu) { 1041 struct per_cpu_pageset *pageset; 1042 1043 if (!cpu_possible(cpu)) 1044 continue; 1045 1046 pageset = zone->pageset + cpu; 1047 1048 for (temperature = 0; temperature < 2; temperature++) 1049 printk("cpu %d %s: low %d, high %d, batch %d\n", 1050 cpu, 1051 temperature ? "cold" : "hot", 1052 pageset->pcp[temperature].low, 1053 pageset->pcp[temperature].high, 1054 pageset->pcp[temperature].batch); 1055 } 1056 } 1057 1058 get_page_state(&ps); 1059 get_zone_counts(&active, &inactive, &free); 1060 1061 printk("\nFree pages: %11ukB (%ukB HighMem)\n", 1062 K(nr_free_pages()), 1063 K(nr_free_highpages())); 1064 1065 printk("Active:%lu inactive:%lu dirty:%lu writeback:%lu " 1066 "unstable:%lu free:%u slab:%lu mapped:%lu pagetables:%lu\n", 1067 active, 1068 inactive, 1069 ps.nr_dirty, 1070 ps.nr_writeback, 1071 ps.nr_unstable, 1072 nr_free_pages(), 1073 ps.nr_slab, 1074 ps.nr_mapped, 1075 ps.nr_page_table_pages); 1076 1077 for_each_zone(zone) { 1078 int i; 1079 1080 show_node(zone); 1081 printk("%s" 1082 " free:%lukB" 1083 " min:%lukB" 1084 " low:%lukB" 1085 " high:%lukB" 1086 " active:%lukB" 1087 " inactive:%lukB" 1088 " present:%lukB" 1089 "\n", 1090 zone->name, 1091 K(zone->free_pages), 1092 K(zone->pages_min), 1093 K(zone->pages_low), 1094 K(zone->pages_high), 1095 K(zone->nr_active), 1096 K(zone->nr_inactive), 1097 K(zone->present_pages) 1098 ); 1099 printk("protections[]:"); 1100 for (i = 0; i < MAX_NR_ZONES; i++) 1101 printk(" %lu", zone->protection[i]); 1102 printk("\n"); 1103 } 1104 1105 for_each_zone(zone) { 1106 struct list_head *elem; 1107 unsigned long nr, flags, order, total = 0; 1108 1109 show_node(zone); 1110 printk("%s: ", zone->name); 1111 if (!zone->present_pages) { 1112 printk("empty\n"); 1113 continue; 1114 } 1115 1116 spin_lock_irqsave(&zone->lock, flags); 1117 for (order = 0; order < MAX_ORDER; order++) { 1118 nr = 0; 1119 list_for_each(elem, &zone->free_area[order].free_list) 1120 ++nr; 1121 total += nr << order; 1122 printk("%lu*%lukB ", nr, K(1UL) << order); 1123 } 1124 spin_unlock_irqrestore(&zone->lock, flags); 1125 printk("= %lukB\n", K(total)); 1126 } 1127 1128 show_swap_cache_info(); 1129 } 1130 1131 /* 1132 * Builds allocation fallback zone lists. 1133 */ 1134 static int __init build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist, int j, int k) 1135 { 1136 switch (k) { 1137 struct zone *zone; 1138 default: 1139 BUG(); 1140 case ZONE_HIGHMEM: 1141 zone = pgdat->node_zones + ZONE_HIGHMEM; 1142 if (zone->present_pages) { 1143 #ifndef CONFIG_HIGHMEM 1144 BUG(); 1145 #endif 1146 zonelist->zones[j++] = zone; 1147 } 1148 case ZONE_NORMAL: 1149 zone = pgdat->node_zones + ZONE_NORMAL; 1150 if (zone->present_pages) 1151 zonelist->zones[j++] = zone; 1152 case ZONE_DMA: 1153 zone = pgdat->node_zones + ZONE_DMA; 1154 if (zone->present_pages) 1155 zonelist->zones[j++] = zone; 1156 } 1157 1158 return j; 1159 } 1160 1161 #ifdef CONFIG_NUMA 1162 #define MAX_NODE_LOAD (numnodes) 1163 static int __initdata node_load[MAX_NUMNODES]; 1164 /** 1165 * find_next_best_node - find the next node that should appear in a given 1166 * node's fallback list 1167 * @node: node whose fallback list we're appending 1168 * @used_node_mask: pointer to the bitmap of already used nodes 1169 * 1170 * We use a number of factors to determine which is the next node that should 1171 * appear on a given node's fallback list. The node should not have appeared 1172 * already in @node's fallback list, and it should be the next closest node 1173 * according to the distance array (which contains arbitrary distance values 1174 * from each node to each node in the system), and should also prefer nodes 1175 * with no CPUs, since presumably they'll have very little allocation pressure 1176 * on them otherwise. 1177 * It returns -1 if no node is found. 1178 */ 1179 static int __init find_next_best_node(int node, void *used_node_mask) 1180 { 1181 int i, n, val; 1182 int min_val = INT_MAX; 1183 int best_node = -1; 1184 1185 for (i = 0; i < numnodes; i++) { 1186 cpumask_t tmp; 1187 1188 /* Start from local node */ 1189 n = (node+i)%numnodes; 1190 1191 /* Don't want a node to appear more than once */ 1192 if (test_bit(n, used_node_mask)) 1193 continue; 1194 1195 /* Use the distance array to find the distance */ 1196 val = node_distance(node, n); 1197 1198 /* Give preference to headless and unused nodes */ 1199 tmp = node_to_cpumask(n); 1200 if (!cpus_empty(tmp)) 1201 val += PENALTY_FOR_NODE_WITH_CPUS; 1202 1203 /* Slight preference for less loaded node */ 1204 val *= (MAX_NODE_LOAD*MAX_NUMNODES); 1205 val += node_load[n]; 1206 1207 if (val < min_val) { 1208 min_val = val; 1209 best_node = n; 1210 } 1211 } 1212 1213 if (best_node >= 0) 1214 set_bit(best_node, used_node_mask); 1215 1216 return best_node; 1217 } 1218 1219 static void __init build_zonelists(pg_data_t *pgdat) 1220 { 1221 int i, j, k, node, local_node; 1222 int prev_node, load; 1223 struct zonelist *zonelist; 1224 DECLARE_BITMAP(used_mask, MAX_NUMNODES); 1225 1226 /* initialize zonelists */ 1227 for (i = 0; i < GFP_ZONETYPES; i++) { 1228 zonelist = pgdat->node_zonelists + i; 1229 memset(zonelist, 0, sizeof(*zonelist)); 1230 zonelist->zones[0] = NULL; 1231 } 1232 1233 /* NUMA-aware ordering of nodes */ 1234 local_node = pgdat->node_id; 1235 load = numnodes; 1236 prev_node = local_node; 1237 bitmap_zero(used_mask, MAX_NUMNODES); 1238 while ((node = find_next_best_node(local_node, used_mask)) >= 0) { 1239 /* 1240 * We don't want to pressure a particular node. 1241 * So adding penalty to the first node in same 1242 * distance group to make it round-robin. 1243 */ 1244 if (node_distance(local_node, node) != 1245 node_distance(local_node, prev_node)) 1246 node_load[node] += load; 1247 prev_node = node; 1248 load--; 1249 for (i = 0; i < GFP_ZONETYPES; i++) { 1250 zonelist = pgdat->node_zonelists + i; 1251 for (j = 0; zonelist->zones[j] != NULL; j++); 1252 1253 k = ZONE_NORMAL; 1254 if (i & __GFP_HIGHMEM) 1255 k = ZONE_HIGHMEM; 1256 if (i & __GFP_DMA) 1257 k = ZONE_DMA; 1258 1259 j = build_zonelists_node(NODE_DATA(node), zonelist, j, k); 1260 zonelist->zones[j] = NULL; 1261 } 1262 } 1263 } 1264 1265 #else /* CONFIG_NUMA */ 1266 1267 static void __init build_zonelists(pg_data_t *pgdat) 1268 { 1269 int i, j, k, node, local_node; 1270 1271 local_node = pgdat->node_id; 1272 for (i = 0; i < GFP_ZONETYPES; i++) { 1273 struct zonelist *zonelist; 1274 1275 zonelist = pgdat->node_zonelists + i; 1276 memset(zonelist, 0, sizeof(*zonelist)); 1277 1278 j = 0; 1279 k = ZONE_NORMAL; 1280 if (i & __GFP_HIGHMEM) 1281 k = ZONE_HIGHMEM; 1282 if (i & __GFP_DMA) 1283 k = ZONE_DMA; 1284 1285 j = build_zonelists_node(pgdat, zonelist, j, k); 1286 /* 1287 * Now we build the zonelist so that it contains the zones 1288 * of all the other nodes. 1289 * We don't want to pressure a particular node, so when 1290 * building the zones for node N, we make sure that the 1291 * zones coming right after the local ones are those from 1292 * node N+1 (modulo N) 1293 */ 1294 for (node = local_node + 1; node < numnodes; node++) 1295 j = build_zonelists_node(NODE_DATA(node), zonelist, j, k); 1296 for (node = 0; node < local_node; node++) 1297 j = build_zonelists_node(NODE_DATA(node), zonelist, j, k); 1298 1299 zonelist->zones[j] = NULL; 1300 } 1301 } 1302 1303 #endif /* CONFIG_NUMA */ 1304 1305 void __init build_all_zonelists(void) 1306 { 1307 int i; 1308 1309 for(i = 0 ; i < numnodes ; i++) 1310 build_zonelists(NODE_DATA(i)); 1311 printk("Built %i zonelists\n", numnodes); 1312 } 1313 1314 /* 1315 * Helper functions to size the waitqueue hash table. 1316 * Essentially these want to choose hash table sizes sufficiently 1317 * large so that collisions trying to wait on pages are rare. 1318 * But in fact, the number of active page waitqueues on typical 1319 * systems is ridiculously low, less than 200. So this is even 1320 * conservative, even though it seems large. 1321 * 1322 * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to 1323 * waitqueues, i.e. the size of the waitq table given the number of pages. 1324 */ 1325 #define PAGES_PER_WAITQUEUE 256 1326 1327 static inline unsigned long wait_table_size(unsigned long pages) 1328 { 1329 unsigned long size = 1; 1330 1331 pages /= PAGES_PER_WAITQUEUE; 1332 1333 while (size < pages) 1334 size <<= 1; 1335 1336 /* 1337 * Once we have dozens or even hundreds of threads sleeping 1338 * on IO we've got bigger problems than wait queue collision. 1339 * Limit the size of the wait table to a reasonable size. 1340 */ 1341 size = min(size, 4096UL); 1342 1343 return max(size, 4UL); 1344 } 1345 1346 /* 1347 * This is an integer logarithm so that shifts can be used later 1348 * to extract the more random high bits from the multiplicative 1349 * hash function before the remainder is taken. 1350 */ 1351 static inline unsigned long wait_table_bits(unsigned long size) 1352 { 1353 return ffz(~size); 1354 } 1355 1356 #define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1)) 1357 1358 static void __init calculate_zone_totalpages(struct pglist_data *pgdat, 1359 unsigned long *zones_size, unsigned long *zholes_size) 1360 { 1361 unsigned long realtotalpages, totalpages = 0; 1362 int i; 1363 1364 for (i = 0; i < MAX_NR_ZONES; i++) 1365 totalpages += zones_size[i]; 1366 pgdat->node_spanned_pages = totalpages; 1367 1368 realtotalpages = totalpages; 1369 if (zholes_size) 1370 for (i = 0; i < MAX_NR_ZONES; i++) 1371 realtotalpages -= zholes_size[i]; 1372 pgdat->node_present_pages = realtotalpages; 1373 printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id, realtotalpages); 1374 } 1375 1376 1377 /* 1378 * Initially all pages are reserved - free ones are freed 1379 * up by free_all_bootmem() once the early boot process is 1380 * done. Non-atomic initialization, single-pass. 1381 */ 1382 void __init memmap_init_zone(struct page *start, unsigned long size, int nid, 1383 unsigned long zone, unsigned long start_pfn) 1384 { 1385 struct page *page; 1386 1387 for (page = start; page < (start + size); page++) { 1388 set_page_zone(page, NODEZONE(nid, zone)); 1389 set_page_count(page, 0); 1390 SetPageReserved(page); 1391 INIT_LIST_HEAD(&page->lru); 1392 #ifdef WANT_PAGE_VIRTUAL 1393 /* The shift won't overflow because ZONE_NORMAL is below 4G. */ 1394 if (!is_highmem_idx(zone)) 1395 set_page_address(page, __va(start_pfn << PAGE_SHIFT)); 1396 #endif 1397 start_pfn++; 1398 } 1399 } 1400 1401 #ifndef __HAVE_ARCH_MEMMAP_INIT 1402 #define memmap_init(start, size, nid, zone, start_pfn) \ 1403 memmap_init_zone((start), (size), (nid), (zone), (start_pfn)) 1404 #endif 1405 1406 /* 1407 * Set up the zone data structures: 1408 * - mark all pages reserved 1409 * - mark all memory queues empty 1410 * - clear the memory bitmaps 1411 */ 1412 static void __init free_area_init_core(struct pglist_data *pgdat, 1413 unsigned long *zones_size, unsigned long *zholes_size) 1414 { 1415 unsigned long i, j; 1416 const unsigned long zone_required_alignment = 1UL << (MAX_ORDER-1); 1417 int cpu, nid = pgdat->node_id; 1418 struct page *lmem_map = pgdat->node_mem_map; 1419 unsigned long zone_start_pfn = pgdat->node_start_pfn; 1420 1421 pgdat->nr_zones = 0; 1422 init_waitqueue_head(&pgdat->kswapd_wait); 1423 1424 for (j = 0; j < MAX_NR_ZONES; j++) { 1425 struct zone *zone = pgdat->node_zones + j; 1426 unsigned long size, realsize; 1427 unsigned long batch; 1428 1429 zone_table[NODEZONE(nid, j)] = zone; 1430 realsize = size = zones_size[j]; 1431 if (zholes_size) 1432 realsize -= zholes_size[j]; 1433 1434 if (j == ZONE_DMA || j == ZONE_NORMAL) 1435 nr_kernel_pages += realsize; 1436 nr_all_pages += realsize; 1437 1438 zone->spanned_pages = size; 1439 zone->present_pages = realsize; 1440 zone->name = zone_names[j]; 1441 spin_lock_init(&zone->lock); 1442 spin_lock_init(&zone->lru_lock); 1443 zone->zone_pgdat = pgdat; 1444 zone->free_pages = 0; 1445 1446 zone->temp_priority = zone->prev_priority = DEF_PRIORITY; 1447 1448 /* 1449 * The per-cpu-pages pools are set to around 1000th of the 1450 * size of the zone. But no more than 1/4 of a meg - there's 1451 * no point in going beyond the size of L2 cache. 1452 * 1453 * OK, so we don't know how big the cache is. So guess. 1454 */ 1455 batch = zone->present_pages / 1024; 1456 if (batch * PAGE_SIZE > 256 * 1024) 1457 batch = (256 * 1024) / PAGE_SIZE; 1458 batch /= 4; /* We effectively *= 4 below */ 1459 if (batch < 1) 1460 batch = 1; 1461 1462 for (cpu = 0; cpu < NR_CPUS; cpu++) { 1463 struct per_cpu_pages *pcp; 1464 1465 pcp = &zone->pageset[cpu].pcp[0]; /* hot */ 1466 pcp->count = 0; 1467 pcp->low = 2 * batch; 1468 pcp->high = 6 * batch; 1469 pcp->batch = 1 * batch; 1470 INIT_LIST_HEAD(&pcp->list); 1471 1472 pcp = &zone->pageset[cpu].pcp[1]; /* cold */ 1473 pcp->count = 0; 1474 pcp->low = 0; 1475 pcp->high = 2 * batch; 1476 pcp->batch = 1 * batch; 1477 INIT_LIST_HEAD(&pcp->list); 1478 } 1479 printk(KERN_DEBUG " %s zone: %lu pages, LIFO batch:%lu\n", 1480 zone_names[j], realsize, batch); 1481 INIT_LIST_HEAD(&zone->active_list); 1482 INIT_LIST_HEAD(&zone->inactive_list); 1483 zone->nr_scan_active = 0; 1484 zone->nr_scan_inactive = 0; 1485 zone->nr_active = 0; 1486 zone->nr_inactive = 0; 1487 if (!size) 1488 continue; 1489 1490 /* 1491 * The per-page waitqueue mechanism uses hashed waitqueues 1492 * per zone. 1493 */ 1494 zone->wait_table_size = wait_table_size(size); 1495 zone->wait_table_bits = 1496 wait_table_bits(zone->wait_table_size); 1497 zone->wait_table = (wait_queue_head_t *) 1498 alloc_bootmem_node(pgdat, zone->wait_table_size 1499 * sizeof(wait_queue_head_t)); 1500 1501 for(i = 0; i < zone->wait_table_size; ++i) 1502 init_waitqueue_head(zone->wait_table + i); 1503 1504 pgdat->nr_zones = j+1; 1505 1506 zone->zone_mem_map = lmem_map; 1507 zone->zone_start_pfn = zone_start_pfn; 1508 1509 if ((zone_start_pfn) & (zone_required_alignment-1)) 1510 printk("BUG: wrong zone alignment, it will crash\n"); 1511 1512 memmap_init(lmem_map, size, nid, j, zone_start_pfn); 1513 1514 zone_start_pfn += size; 1515 lmem_map += size; 1516 1517 for (i = 0; ; i++) { 1518 unsigned long bitmap_size; 1519 1520 INIT_LIST_HEAD(&zone->free_area[i].free_list); 1521 if (i == MAX_ORDER-1) { 1522 zone->free_area[i].map = NULL; 1523 break; 1524 } 1525 1526 /* 1527 * Page buddy system uses "index >> (i+1)", 1528 * where "index" is at most "size-1". 1529 * 1530 * The extra "+3" is to round down to byte 1531 * size (8 bits per byte assumption). Thus 1532 * we get "(size-1) >> (i+4)" as the last byte 1533 * we can access. 1534 * 1535 * The "+1" is because we want to round the 1536 * byte allocation up rather than down. So 1537 * we should have had a "+7" before we shifted 1538 * down by three. Also, we have to add one as 1539 * we actually _use_ the last bit (it's [0,n] 1540 * inclusive, not [0,n[). 1541 * 1542 * So we actually had +7+1 before we shift 1543 * down by 3. But (n+8) >> 3 == (n >> 3) + 1 1544 * (modulo overflows, which we do not have). 1545 * 1546 * Finally, we LONG_ALIGN because all bitmap 1547 * operations are on longs. 1548 */ 1549 bitmap_size = (size-1) >> (i+4); 1550 bitmap_size = LONG_ALIGN(bitmap_size+1); 1551 zone->free_area[i].map = 1552 (unsigned long *) alloc_bootmem_node(pgdat, bitmap_size); 1553 } 1554 } 1555 } 1556 1557 void __init free_area_init_node(int nid, struct pglist_data *pgdat, 1558 struct page *node_mem_map, unsigned long *zones_size, 1559 unsigned long node_start_pfn, unsigned long *zholes_size) 1560 { 1561 unsigned long size; 1562 1563 pgdat->node_id = nid; 1564 pgdat->node_start_pfn = node_start_pfn; 1565 calculate_zone_totalpages(pgdat, zones_size, zholes_size); 1566 if (!node_mem_map) { 1567 size = (pgdat->node_spanned_pages + 1) * sizeof(struct page); 1568 node_mem_map = alloc_bootmem_node(pgdat, size); 1569 } 1570 pgdat->node_mem_map = node_mem_map; 1571 1572 free_area_init_core(pgdat, zones_size, zholes_size); 1573 } 1574 1575 #ifndef CONFIG_DISCONTIGMEM 1576 static bootmem_data_t contig_bootmem_data; 1577 struct pglist_data contig_page_data = { .bdata = &contig_bootmem_data }; 1578 1579 EXPORT_SYMBOL(contig_page_data); 1580 1581 void __init free_area_init(unsigned long *zones_size) 1582 { 1583 free_area_init_node(0, &contig_page_data, NULL, zones_size, 1584 __pa(PAGE_OFFSET) >> PAGE_SHIFT, NULL); 1585 mem_map = contig_page_data.node_mem_map; 1586 } 1587 #endif 1588 1589 #ifdef CONFIG_PROC_FS 1590 1591 #include <linux/seq_file.h> 1592 1593 static void *frag_start(struct seq_file *m, loff_t *pos) 1594 { 1595 pg_data_t *pgdat; 1596 loff_t node = *pos; 1597 1598 for (pgdat = pgdat_list; pgdat && node; pgdat = pgdat->pgdat_next) 1599 --node; 1600 1601 return pgdat; 1602 } 1603 1604 static void *frag_next(struct seq_file *m, void *arg, loff_t *pos) 1605 { 1606 pg_data_t *pgdat = (pg_data_t *)arg; 1607 1608 (*pos)++; 1609 return pgdat->pgdat_next; 1610 } 1611 1612 static void frag_stop(struct seq_file *m, void *arg) 1613 { 1614 } 1615 1616 /* 1617 * This walks the freelist for each zone. Whilst this is slow, I'd rather 1618 * be slow here than slow down the fast path by keeping stats - mjbligh 1619 */ 1620 static int frag_show(struct seq_file *m, void *arg) 1621 { 1622 pg_data_t *pgdat = (pg_data_t *)arg; 1623 struct zone *zone; 1624 struct zone *node_zones = pgdat->node_zones; 1625 unsigned long flags; 1626 int order; 1627 1628 for (zone = node_zones; zone - node_zones < MAX_NR_ZONES; ++zone) { 1629 if (!zone->present_pages) 1630 continue; 1631 1632 spin_lock_irqsave(&zone->lock, flags); 1633 seq_printf(m, "Node %d, zone %8s ", pgdat->node_id, zone->name); 1634 for (order = 0; order < MAX_ORDER; ++order) { 1635 unsigned long nr_bufs = 0; 1636 struct list_head *elem; 1637 1638 list_for_each(elem, &(zone->free_area[order].free_list)) 1639 ++nr_bufs; 1640 seq_printf(m, "%6lu ", nr_bufs); 1641 } 1642 spin_unlock_irqrestore(&zone->lock, flags); 1643 seq_putc(m, '\n'); 1644 } 1645 return 0; 1646 } 1647 1648 struct seq_operations fragmentation_op = { 1649 .start = frag_start, 1650 .next = frag_next, 1651 .stop = frag_stop, 1652 .show = frag_show, 1653 }; 1654 1655 static char *vmstat_text[] = { 1656 "nr_dirty", 1657 "nr_writeback", 1658 "nr_unstable", 1659 "nr_page_table_pages", 1660 "nr_mapped", 1661 "nr_slab", 1662 1663 "pgpgin", 1664 "pgpgout", 1665 "pswpin", 1666 "pswpout", 1667 "pgalloc_high", 1668 1669 "pgalloc_normal", 1670 "pgalloc_dma", 1671 "pgfree", 1672 "pgactivate", 1673 "pgdeactivate", 1674 1675 "pgfault", 1676 "pgmajfault", 1677 "pgrefill_high", 1678 "pgrefill_normal", 1679 "pgrefill_dma", 1680 1681 "pgsteal_high", 1682 "pgsteal_normal", 1683 "pgsteal_dma", 1684 "pgscan_kswapd_high", 1685 "pgscan_kswapd_normal", 1686 1687 "pgscan_kswapd_dma", 1688 "pgscan_direct_high", 1689 "pgscan_direct_normal", 1690 "pgscan_direct_dma", 1691 "pginodesteal", 1692 1693 "slabs_scanned", 1694 "kswapd_steal", 1695 "kswapd_inodesteal", 1696 "pageoutrun", 1697 "allocstall", 1698 1699 "pgrotated", 1700 }; 1701 1702 static void *vmstat_start(struct seq_file *m, loff_t *pos) 1703 { 1704 struct page_state *ps; 1705 1706 if (*pos >= ARRAY_SIZE(vmstat_text)) 1707 return NULL; 1708 1709 ps = kmalloc(sizeof(*ps), GFP_KERNEL); 1710 m->private = ps; 1711 if (!ps) 1712 return ERR_PTR(-ENOMEM); 1713 get_full_page_state(ps); 1714 ps->pgpgin /= 2; /* sectors -> kbytes */ 1715 ps->pgpgout /= 2; 1716 return (unsigned long *)ps + *pos; 1717 } 1718 1719 static void *vmstat_next(struct seq_file *m, void *arg, loff_t *pos) 1720 { 1721 (*pos)++; 1722 if (*pos >= ARRAY_SIZE(vmstat_text)) 1723 return NULL; 1724 return (unsigned long *)m->private + *pos; 1725 } 1726 1727 static int vmstat_show(struct seq_file *m, void *arg) 1728 { 1729 unsigned long *l = arg; 1730 unsigned long off = l - (unsigned long *)m->private; 1731 1732 seq_printf(m, "%s %lu\n", vmstat_text[off], *l); 1733 return 0; 1734 } 1735 1736 static void vmstat_stop(struct seq_file *m, void *arg) 1737 { 1738 kfree(m->private); 1739 m->private = NULL; 1740 } 1741 1742 struct seq_operations vmstat_op = { 1743 .start = vmstat_start, 1744 .next = vmstat_next, 1745 .stop = vmstat_stop, 1746 .show = vmstat_show, 1747 }; 1748 1749 #endif /* CONFIG_PROC_FS */ 1750 1751 #ifdef CONFIG_HOTPLUG_CPU 1752 static int page_alloc_cpu_notify(struct notifier_block *self, 1753 unsigned long action, void *hcpu) 1754 { 1755 int cpu = (unsigned long)hcpu; 1756 long *count; 1757 1758 if (action == CPU_DEAD) { 1759 /* Drain local pagecache count. */ 1760 count = &per_cpu(nr_pagecache_local, cpu); 1761 atomic_add(*count, &nr_pagecache); 1762 *count = 0; 1763 local_irq_disable(); 1764 __drain_pages(cpu); 1765 local_irq_enable(); 1766 } 1767 return NOTIFY_OK; 1768 } 1769 #endif /* CONFIG_HOTPLUG_CPU */ 1770 1771 void __init page_alloc_init(void) 1772 { 1773 hotcpu_notifier(page_alloc_cpu_notify, 0); 1774 } 1775 1776 static unsigned long higherzone_val(struct zone *z, int max_zone, 1777 int alloc_type) 1778 { 1779 int z_idx = zone_idx(z); 1780 struct zone *higherzone; 1781 unsigned long pages; 1782 1783 /* there is no higher zone to get a contribution from */ 1784 if (z_idx == MAX_NR_ZONES-1) 1785 return 0; 1786 1787 higherzone = &z->zone_pgdat->node_zones[z_idx+1]; 1788 1789 /* We always start with the higher zone's protection value */ 1790 pages = higherzone->protection[alloc_type]; 1791 1792 /* 1793 * We get a lower-zone-protection contribution only if there are 1794 * pages in the higher zone and if we're not the highest zone 1795 * in the current zonelist. e.g., never happens for GFP_DMA. Happens 1796 * only for ZONE_DMA in a GFP_KERNEL allocation and happens for ZONE_DMA 1797 * and ZONE_NORMAL for a GFP_HIGHMEM allocation. 1798 */ 1799 if (higherzone->present_pages && z_idx < alloc_type) 1800 pages += higherzone->pages_low * sysctl_lower_zone_protection; 1801 1802 return pages; 1803 } 1804 1805 /* 1806 * setup_per_zone_protection - called whenver min_free_kbytes or 1807 * sysctl_lower_zone_protection changes. Ensures that each zone 1808 * has a correct pages_protected value, so an adequate number of 1809 * pages are left in the zone after a successful __alloc_pages(). 1810 * 1811 * This algorithm is way confusing. I tries to keep the same behavior 1812 * as we had with the incremental min iterative algorithm. 1813 */ 1814 static void setup_per_zone_protection(void) 1815 { 1816 struct pglist_data *pgdat; 1817 struct zone *zones, *zone; 1818 int max_zone; 1819 int i, j; 1820 1821 for_each_pgdat(pgdat) { 1822 zones = pgdat->node_zones; 1823 1824 for (i = 0, max_zone = 0; i < MAX_NR_ZONES; i++) 1825 if (zones[i].present_pages) 1826 max_zone = i; 1827 1828 /* 1829 * For each of the different allocation types: 1830 * GFP_DMA -> GFP_KERNEL -> GFP_HIGHMEM 1831 */ 1832 for (i = 0; i < GFP_ZONETYPES; i++) { 1833 /* 1834 * For each of the zones: 1835 * ZONE_HIGHMEM -> ZONE_NORMAL -> ZONE_DMA 1836 */ 1837 for (j = MAX_NR_ZONES-1; j >= 0; j--) { 1838 zone = &zones[j]; 1839 1840 /* 1841 * We never protect zones that don't have memory 1842 * in them (j>max_zone) or zones that aren't in 1843 * the zonelists for a certain type of 1844 * allocation (j>i). We have to assign these to 1845 * zero because the lower zones take 1846 * contributions from the higher zones. 1847 */ 1848 if (j > max_zone || j > i) { 1849 zone->protection[i] = 0; 1850 continue; 1851 } 1852 /* 1853 * The contribution of the next higher zone 1854 */ 1855 zone->protection[i] = higherzone_val(zone, 1856 max_zone, i); 1857 zone->protection[i] += zone->pages_low; 1858 } 1859 } 1860 } 1861 } 1862 1863 /* 1864 * setup_per_zone_pages_min - called when min_free_kbytes changes. Ensures 1865 * that the pages_{min,low,high} values for each zone are set correctly 1866 * with respect to min_free_kbytes. 1867 */ 1868 static void setup_per_zone_pages_min(void) 1869 { 1870 unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10); 1871 unsigned long lowmem_pages = 0; 1872 struct zone *zone; 1873 unsigned long flags; 1874 1875 /* Calculate total number of !ZONE_HIGHMEM pages */ 1876 for_each_zone(zone) { 1877 if (!is_highmem(zone)) 1878 lowmem_pages += zone->present_pages; 1879 } 1880 1881 for_each_zone(zone) { 1882 spin_lock_irqsave(&zone->lru_lock, flags); 1883 if (is_highmem(zone)) { 1884 /* 1885 * Often, highmem doesn't need to reserve any pages. 1886 * But the pages_min/low/high values are also used for 1887 * batching up page reclaim activity so we need a 1888 * decent value here. 1889 */ 1890 int min_pages; 1891 1892 min_pages = zone->present_pages / 1024; 1893 if (min_pages < SWAP_CLUSTER_MAX) 1894 min_pages = SWAP_CLUSTER_MAX; 1895 if (min_pages > 128) 1896 min_pages = 128; 1897 zone->pages_min = min_pages; 1898 } else { 1899 /* if it's a lowmem zone, reserve a number of pages 1900 * proportionate to the zone's size. 1901 */ 1902 zone->pages_min = (pages_min * zone->present_pages) / 1903 lowmem_pages; 1904 } 1905 1906 zone->pages_low = zone->pages_min * 2; 1907 zone->pages_high = zone->pages_min * 3; 1908 spin_unlock_irqrestore(&zone->lru_lock, flags); 1909 } 1910 } 1911 1912 /* 1913 * Initialise min_free_kbytes. 1914 * 1915 * For small machines we want it small (128k min). For large machines 1916 * we want it large (16MB max). But it is not linear, because network 1917 * bandwidth does not increase linearly with machine size. We use 1918 * 1919 * min_free_kbytes = sqrt(lowmem_kbytes) 1920 * 1921 * which yields 1922 * 1923 * 16MB: 128k 1924 * 32MB: 181k 1925 * 64MB: 256k 1926 * 128MB: 362k 1927 * 256MB: 512k 1928 * 512MB: 724k 1929 * 1024MB: 1024k 1930 * 2048MB: 1448k 1931 * 4096MB: 2048k 1932 * 8192MB: 2896k 1933 * 16384MB: 4096k 1934 */ 1935 static int __init init_per_zone_pages_min(void) 1936 { 1937 unsigned long lowmem_kbytes; 1938 1939 lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10); 1940 1941 min_free_kbytes = int_sqrt(lowmem_kbytes); 1942 if (min_free_kbytes < 128) 1943 min_free_kbytes = 128; 1944 if (min_free_kbytes > 16384) 1945 min_free_kbytes = 16384; 1946 setup_per_zone_pages_min(); 1947 setup_per_zone_protection(); 1948 return 0; 1949 } 1950 module_init(init_per_zone_pages_min) 1951 1952 /* 1953 * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so 1954 * that we can call two helper functions whenever min_free_kbytes 1955 * changes. 1956 */ 1957 int min_free_kbytes_sysctl_handler(ctl_table *table, int write, 1958 struct file *file, void __user *buffer, size_t *length, loff_t *ppos) 1959 { 1960 proc_dointvec(table, write, file, buffer, length, ppos); 1961 setup_per_zone_pages_min(); 1962 setup_per_zone_protection(); 1963 return 0; 1964 } 1965 1966 /* 1967 * lower_zone_protection_sysctl_handler - just a wrapper around 1968 * proc_dointvec() so that we can call setup_per_zone_protection() 1969 * whenever sysctl_lower_zone_protection changes. 1970 */ 1971 int lower_zone_protection_sysctl_handler(ctl_table *table, int write, 1972 struct file *file, void __user *buffer, size_t *length, loff_t *ppos) 1973 { 1974 proc_dointvec_minmax(table, write, file, buffer, length, ppos); 1975 setup_per_zone_protection(); 1976 return 0; 1977 } 1978 1979 /* 1980 * allocate a large system hash table from bootmem 1981 * - it is assumed that the hash table must contain an exact power-of-2 1982 * quantity of entries 1983 */ 1984 void *__init alloc_large_system_hash(const char *tablename, 1985 unsigned long bucketsize, 1986 unsigned long numentries, 1987 int scale, 1988 int consider_highmem, 1989 unsigned int *_hash_shift, 1990 unsigned int *_hash_mask) 1991 { 1992 unsigned long mem, max, log2qty, size; 1993 void *table; 1994 1995 /* round applicable memory size up to nearest megabyte */ 1996 mem = consider_highmem ? nr_all_pages : nr_kernel_pages; 1997 mem += (1UL << (20 - PAGE_SHIFT)) - 1; 1998 mem >>= 20 - PAGE_SHIFT; 1999 mem <<= 20 - PAGE_SHIFT; 2000 2001 /* limit to 1 bucket per 2^scale bytes of low memory (rounded up to 2002 * nearest power of 2 in size) */ 2003 if (scale > PAGE_SHIFT) 2004 mem >>= (scale - PAGE_SHIFT); 2005 else 2006 mem <<= (PAGE_SHIFT - scale); 2007 2008 mem = 1UL << (long_log2(mem) + 1); 2009 2010 /* limit allocation size */ 2011 max = (1UL << (PAGE_SHIFT + MAX_SYS_HASH_TABLE_ORDER)) / bucketsize; 2012 if (max > mem) 2013 max = mem; 2014 2015 /* allow the kernel cmdline to have a say */ 2016 if (!numentries || numentries > max) 2017 numentries = max; 2018 2019 log2qty = long_log2(numentries); 2020 2021 do { 2022 size = bucketsize << log2qty; 2023 2024 table = (void *) alloc_bootmem(size); 2025 2026 } while (!table && size > PAGE_SIZE); 2027 2028 if (!table) 2029 panic("Failed to allocate %s hash table\n", tablename); 2030 2031 printk("%s hash table entries: %d (order: %d, %lu bytes)\n", 2032 tablename, 2033 (1U << log2qty), 2034 long_log2(size) - PAGE_SHIFT, 2035 size); 2036 2037 if (_hash_shift) 2038 *_hash_shift = log2qty; 2039 if (_hash_mask) 2040 *_hash_mask = (1 << log2qty) - 1; 2041 2042 return table; 2043 } 2044
This page was automatically generated by LXR 0.3.1. • Linux is a registered trademark of Linus Torvalds