page_alloc.c revision 2f1b6248682f8b39ca3c7e549dfc216d26c4109b
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/stddef.h> 18#include <linux/mm.h> 19#include <linux/swap.h> 20#include <linux/interrupt.h> 21#include <linux/pagemap.h> 22#include <linux/bootmem.h> 23#include <linux/compiler.h> 24#include <linux/kernel.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#include <linux/cpuset.h> 35#include <linux/memory_hotplug.h> 36#include <linux/nodemask.h> 37#include <linux/vmalloc.h> 38#include <linux/mempolicy.h> 39#include <linux/stop_machine.h> 40 41#include <asm/tlbflush.h> 42#include <asm/div64.h> 43#include "internal.h" 44 45/* 46 * MCD - HACK: Find somewhere to initialize this EARLY, or make this 47 * initializer cleaner 48 */ 49nodemask_t node_online_map __read_mostly = { { [0] = 1UL } }; 50EXPORT_SYMBOL(node_online_map); 51nodemask_t node_possible_map __read_mostly = NODE_MASK_ALL; 52EXPORT_SYMBOL(node_possible_map); 53unsigned long totalram_pages __read_mostly; 54unsigned long totalreserve_pages __read_mostly; 55long nr_swap_pages; 56int percpu_pagelist_fraction; 57 58static void __free_pages_ok(struct page *page, unsigned int order); 59 60/* 61 * results with 256, 32 in the lowmem_reserve sysctl: 62 * 1G machine -> (16M dma, 800M-16M normal, 1G-800M high) 63 * 1G machine -> (16M dma, 784M normal, 224M high) 64 * NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA 65 * HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL 66 * HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA 67 * 68 * TBD: should special case ZONE_DMA32 machines here - in those we normally 69 * don't need any ZONE_NORMAL reservation 70 */ 71int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = { 72 256, 73 256, 74 32 75}; 76 77EXPORT_SYMBOL(totalram_pages); 78 79/* 80 * Used by page_zone() to look up the address of the struct zone whose 81 * id is encoded in the upper bits of page->flags 82 */ 83struct zone *zone_table[1 << ZONETABLE_SHIFT] __read_mostly; 84EXPORT_SYMBOL(zone_table); 85 86static char *zone_names[MAX_NR_ZONES] = { 87 "DMA", 88 "DMA32", 89 "Normal", 90 "HighMem" 91}; 92 93int min_free_kbytes = 1024; 94 95unsigned long __meminitdata nr_kernel_pages; 96unsigned long __meminitdata nr_all_pages; 97 98#ifdef CONFIG_DEBUG_VM 99static int page_outside_zone_boundaries(struct zone *zone, struct page *page) 100{ 101 int ret = 0; 102 unsigned seq; 103 unsigned long pfn = page_to_pfn(page); 104 105 do { 106 seq = zone_span_seqbegin(zone); 107 if (pfn >= zone->zone_start_pfn + zone->spanned_pages) 108 ret = 1; 109 else if (pfn < zone->zone_start_pfn) 110 ret = 1; 111 } while (zone_span_seqretry(zone, seq)); 112 113 return ret; 114} 115 116static int page_is_consistent(struct zone *zone, struct page *page) 117{ 118#ifdef CONFIG_HOLES_IN_ZONE 119 if (!pfn_valid(page_to_pfn(page))) 120 return 0; 121#endif 122 if (zone != page_zone(page)) 123 return 0; 124 125 return 1; 126} 127/* 128 * Temporary debugging check for pages not lying within a given zone. 129 */ 130static int bad_range(struct zone *zone, struct page *page) 131{ 132 if (page_outside_zone_boundaries(zone, page)) 133 return 1; 134 if (!page_is_consistent(zone, page)) 135 return 1; 136 137 return 0; 138} 139#else 140static inline int bad_range(struct zone *zone, struct page *page) 141{ 142 return 0; 143} 144#endif 145 146static void bad_page(struct page *page) 147{ 148 printk(KERN_EMERG "Bad page state in process '%s'\n" 149 KERN_EMERG "page:%p flags:0x%0*lx mapping:%p mapcount:%d count:%d\n" 150 KERN_EMERG "Trying to fix it up, but a reboot is needed\n" 151 KERN_EMERG "Backtrace:\n", 152 current->comm, page, (int)(2*sizeof(unsigned long)), 153 (unsigned long)page->flags, page->mapping, 154 page_mapcount(page), page_count(page)); 155 dump_stack(); 156 page->flags &= ~(1 << PG_lru | 157 1 << PG_private | 158 1 << PG_locked | 159 1 << PG_active | 160 1 << PG_dirty | 161 1 << PG_reclaim | 162 1 << PG_slab | 163 1 << PG_swapcache | 164 1 << PG_writeback | 165 1 << PG_buddy ); 166 set_page_count(page, 0); 167 reset_page_mapcount(page); 168 page->mapping = NULL; 169 add_taint(TAINT_BAD_PAGE); 170} 171 172/* 173 * Higher-order pages are called "compound pages". They are structured thusly: 174 * 175 * The first PAGE_SIZE page is called the "head page". 176 * 177 * The remaining PAGE_SIZE pages are called "tail pages". 178 * 179 * All pages have PG_compound set. All pages have their ->private pointing at 180 * the head page (even the head page has this). 181 * 182 * The first tail page's ->lru.next holds the address of the compound page's 183 * put_page() function. Its ->lru.prev holds the order of allocation. 184 * This usage means that zero-order pages may not be compound. 185 */ 186 187static void free_compound_page(struct page *page) 188{ 189 __free_pages_ok(page, (unsigned long)page[1].lru.prev); 190} 191 192static void prep_compound_page(struct page *page, unsigned long order) 193{ 194 int i; 195 int nr_pages = 1 << order; 196 197 page[1].lru.next = (void *)free_compound_page; /* set dtor */ 198 page[1].lru.prev = (void *)order; 199 for (i = 0; i < nr_pages; i++) { 200 struct page *p = page + i; 201 202 __SetPageCompound(p); 203 set_page_private(p, (unsigned long)page); 204 } 205} 206 207static void destroy_compound_page(struct page *page, unsigned long order) 208{ 209 int i; 210 int nr_pages = 1 << order; 211 212 if (unlikely((unsigned long)page[1].lru.prev != order)) 213 bad_page(page); 214 215 for (i = 0; i < nr_pages; i++) { 216 struct page *p = page + i; 217 218 if (unlikely(!PageCompound(p) | 219 (page_private(p) != (unsigned long)page))) 220 bad_page(page); 221 __ClearPageCompound(p); 222 } 223} 224 225static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags) 226{ 227 int i; 228 229 VM_BUG_ON((gfp_flags & (__GFP_WAIT | __GFP_HIGHMEM)) == __GFP_HIGHMEM); 230 /* 231 * clear_highpage() will use KM_USER0, so it's a bug to use __GFP_ZERO 232 * and __GFP_HIGHMEM from hard or soft interrupt context. 233 */ 234 VM_BUG_ON((gfp_flags & __GFP_HIGHMEM) && in_interrupt()); 235 for (i = 0; i < (1 << order); i++) 236 clear_highpage(page + i); 237} 238 239/* 240 * function for dealing with page's order in buddy system. 241 * zone->lock is already acquired when we use these. 242 * So, we don't need atomic page->flags operations here. 243 */ 244static inline unsigned long page_order(struct page *page) 245{ 246 return page_private(page); 247} 248 249static inline void set_page_order(struct page *page, int order) 250{ 251 set_page_private(page, order); 252 __SetPageBuddy(page); 253} 254 255static inline void rmv_page_order(struct page *page) 256{ 257 __ClearPageBuddy(page); 258 set_page_private(page, 0); 259} 260 261/* 262 * Locate the struct page for both the matching buddy in our 263 * pair (buddy1) and the combined O(n+1) page they form (page). 264 * 265 * 1) Any buddy B1 will have an order O twin B2 which satisfies 266 * the following equation: 267 * B2 = B1 ^ (1 << O) 268 * For example, if the starting buddy (buddy2) is #8 its order 269 * 1 buddy is #10: 270 * B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10 271 * 272 * 2) Any buddy B will have an order O+1 parent P which 273 * satisfies the following equation: 274 * P = B & ~(1 << O) 275 * 276 * Assumption: *_mem_map is contiguous at least up to MAX_ORDER 277 */ 278static inline struct page * 279__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order) 280{ 281 unsigned long buddy_idx = page_idx ^ (1 << order); 282 283 return page + (buddy_idx - page_idx); 284} 285 286static inline unsigned long 287__find_combined_index(unsigned long page_idx, unsigned int order) 288{ 289 return (page_idx & ~(1 << order)); 290} 291 292/* 293 * This function checks whether a page is free && is the buddy 294 * we can do coalesce a page and its buddy if 295 * (a) the buddy is not in a hole && 296 * (b) the buddy is in the buddy system && 297 * (c) a page and its buddy have the same order && 298 * (d) a page and its buddy are in the same zone. 299 * 300 * For recording whether a page is in the buddy system, we use PG_buddy. 301 * Setting, clearing, and testing PG_buddy is serialized by zone->lock. 302 * 303 * For recording page's order, we use page_private(page). 304 */ 305static inline int page_is_buddy(struct page *page, struct page *buddy, 306 int order) 307{ 308#ifdef CONFIG_HOLES_IN_ZONE 309 if (!pfn_valid(page_to_pfn(buddy))) 310 return 0; 311#endif 312 313 if (page_zone_id(page) != page_zone_id(buddy)) 314 return 0; 315 316 if (PageBuddy(buddy) && page_order(buddy) == order) { 317 BUG_ON(page_count(buddy) != 0); 318 return 1; 319 } 320 return 0; 321} 322 323/* 324 * Freeing function for a buddy system allocator. 325 * 326 * The concept of a buddy system is to maintain direct-mapped table 327 * (containing bit values) for memory blocks of various "orders". 328 * The bottom level table contains the map for the smallest allocatable 329 * units of memory (here, pages), and each level above it describes 330 * pairs of units from the levels below, hence, "buddies". 331 * At a high level, all that happens here is marking the table entry 332 * at the bottom level available, and propagating the changes upward 333 * as necessary, plus some accounting needed to play nicely with other 334 * parts of the VM system. 335 * At each level, we keep a list of pages, which are heads of continuous 336 * free pages of length of (1 << order) and marked with PG_buddy. Page's 337 * order is recorded in page_private(page) field. 338 * So when we are allocating or freeing one, we can derive the state of the 339 * other. That is, if we allocate a small block, and both were 340 * free, the remainder of the region must be split into blocks. 341 * If a block is freed, and its buddy is also free, then this 342 * triggers coalescing into a block of larger size. 343 * 344 * -- wli 345 */ 346 347static inline void __free_one_page(struct page *page, 348 struct zone *zone, unsigned int order) 349{ 350 unsigned long page_idx; 351 int order_size = 1 << order; 352 353 if (unlikely(PageCompound(page))) 354 destroy_compound_page(page, order); 355 356 page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1); 357 358 VM_BUG_ON(page_idx & (order_size - 1)); 359 VM_BUG_ON(bad_range(zone, page)); 360 361 zone->free_pages += order_size; 362 while (order < MAX_ORDER-1) { 363 unsigned long combined_idx; 364 struct free_area *area; 365 struct page *buddy; 366 367 buddy = __page_find_buddy(page, page_idx, order); 368 if (!page_is_buddy(page, buddy, order)) 369 break; /* Move the buddy up one level. */ 370 371 list_del(&buddy->lru); 372 area = zone->free_area + order; 373 area->nr_free--; 374 rmv_page_order(buddy); 375 combined_idx = __find_combined_index(page_idx, order); 376 page = page + (combined_idx - page_idx); 377 page_idx = combined_idx; 378 order++; 379 } 380 set_page_order(page, order); 381 list_add(&page->lru, &zone->free_area[order].free_list); 382 zone->free_area[order].nr_free++; 383} 384 385static inline int free_pages_check(struct page *page) 386{ 387 if (unlikely(page_mapcount(page) | 388 (page->mapping != NULL) | 389 (page_count(page) != 0) | 390 (page->flags & ( 391 1 << PG_lru | 392 1 << PG_private | 393 1 << PG_locked | 394 1 << PG_active | 395 1 << PG_reclaim | 396 1 << PG_slab | 397 1 << PG_swapcache | 398 1 << PG_writeback | 399 1 << PG_reserved | 400 1 << PG_buddy )))) 401 bad_page(page); 402 if (PageDirty(page)) 403 __ClearPageDirty(page); 404 /* 405 * For now, we report if PG_reserved was found set, but do not 406 * clear it, and do not free the page. But we shall soon need 407 * to do more, for when the ZERO_PAGE count wraps negative. 408 */ 409 return PageReserved(page); 410} 411 412/* 413 * Frees a list of pages. 414 * Assumes all pages on list are in same zone, and of same order. 415 * count is the number of pages to free. 416 * 417 * If the zone was previously in an "all pages pinned" state then look to 418 * see if this freeing clears that state. 419 * 420 * And clear the zone's pages_scanned counter, to hold off the "all pages are 421 * pinned" detection logic. 422 */ 423static void free_pages_bulk(struct zone *zone, int count, 424 struct list_head *list, int order) 425{ 426 spin_lock(&zone->lock); 427 zone->all_unreclaimable = 0; 428 zone->pages_scanned = 0; 429 while (count--) { 430 struct page *page; 431 432 VM_BUG_ON(list_empty(list)); 433 page = list_entry(list->prev, struct page, lru); 434 /* have to delete it as __free_one_page list manipulates */ 435 list_del(&page->lru); 436 __free_one_page(page, zone, order); 437 } 438 spin_unlock(&zone->lock); 439} 440 441static void free_one_page(struct zone *zone, struct page *page, int order) 442{ 443 LIST_HEAD(list); 444 list_add(&page->lru, &list); 445 free_pages_bulk(zone, 1, &list, order); 446} 447 448static void __free_pages_ok(struct page *page, unsigned int order) 449{ 450 unsigned long flags; 451 int i; 452 int reserved = 0; 453 454 arch_free_page(page, order); 455 if (!PageHighMem(page)) 456 debug_check_no_locks_freed(page_address(page), 457 PAGE_SIZE<<order); 458 459 for (i = 0 ; i < (1 << order) ; ++i) 460 reserved += free_pages_check(page + i); 461 if (reserved) 462 return; 463 464 kernel_map_pages(page, 1 << order, 0); 465 local_irq_save(flags); 466 __count_vm_events(PGFREE, 1 << order); 467 free_one_page(page_zone(page), page, order); 468 local_irq_restore(flags); 469} 470 471/* 472 * permit the bootmem allocator to evade page validation on high-order frees 473 */ 474void fastcall __init __free_pages_bootmem(struct page *page, unsigned int order) 475{ 476 if (order == 0) { 477 __ClearPageReserved(page); 478 set_page_count(page, 0); 479 set_page_refcounted(page); 480 __free_page(page); 481 } else { 482 int loop; 483 484 prefetchw(page); 485 for (loop = 0; loop < BITS_PER_LONG; loop++) { 486 struct page *p = &page[loop]; 487 488 if (loop + 1 < BITS_PER_LONG) 489 prefetchw(p + 1); 490 __ClearPageReserved(p); 491 set_page_count(p, 0); 492 } 493 494 set_page_refcounted(page); 495 __free_pages(page, order); 496 } 497} 498 499 500/* 501 * The order of subdivision here is critical for the IO subsystem. 502 * Please do not alter this order without good reasons and regression 503 * testing. Specifically, as large blocks of memory are subdivided, 504 * the order in which smaller blocks are delivered depends on the order 505 * they're subdivided in this function. This is the primary factor 506 * influencing the order in which pages are delivered to the IO 507 * subsystem according to empirical testing, and this is also justified 508 * by considering the behavior of a buddy system containing a single 509 * large block of memory acted on by a series of small allocations. 510 * This behavior is a critical factor in sglist merging's success. 511 * 512 * -- wli 513 */ 514static inline void expand(struct zone *zone, struct page *page, 515 int low, int high, struct free_area *area) 516{ 517 unsigned long size = 1 << high; 518 519 while (high > low) { 520 area--; 521 high--; 522 size >>= 1; 523 VM_BUG_ON(bad_range(zone, &page[size])); 524 list_add(&page[size].lru, &area->free_list); 525 area->nr_free++; 526 set_page_order(&page[size], high); 527 } 528} 529 530/* 531 * This page is about to be returned from the page allocator 532 */ 533static int prep_new_page(struct page *page, int order, gfp_t gfp_flags) 534{ 535 if (unlikely(page_mapcount(page) | 536 (page->mapping != NULL) | 537 (page_count(page) != 0) | 538 (page->flags & ( 539 1 << PG_lru | 540 1 << PG_private | 541 1 << PG_locked | 542 1 << PG_active | 543 1 << PG_dirty | 544 1 << PG_reclaim | 545 1 << PG_slab | 546 1 << PG_swapcache | 547 1 << PG_writeback | 548 1 << PG_reserved | 549 1 << PG_buddy )))) 550 bad_page(page); 551 552 /* 553 * For now, we report if PG_reserved was found set, but do not 554 * clear it, and do not allocate the page: as a safety net. 555 */ 556 if (PageReserved(page)) 557 return 1; 558 559 page->flags &= ~(1 << PG_uptodate | 1 << PG_error | 560 1 << PG_referenced | 1 << PG_arch_1 | 561 1 << PG_checked | 1 << PG_mappedtodisk); 562 set_page_private(page, 0); 563 set_page_refcounted(page); 564 kernel_map_pages(page, 1 << order, 1); 565 566 if (gfp_flags & __GFP_ZERO) 567 prep_zero_page(page, order, gfp_flags); 568 569 if (order && (gfp_flags & __GFP_COMP)) 570 prep_compound_page(page, order); 571 572 return 0; 573} 574 575/* 576 * Do the hard work of removing an element from the buddy allocator. 577 * Call me with the zone->lock already held. 578 */ 579static struct page *__rmqueue(struct zone *zone, unsigned int order) 580{ 581 struct free_area * area; 582 unsigned int current_order; 583 struct page *page; 584 585 for (current_order = order; current_order < MAX_ORDER; ++current_order) { 586 area = zone->free_area + current_order; 587 if (list_empty(&area->free_list)) 588 continue; 589 590 page = list_entry(area->free_list.next, struct page, lru); 591 list_del(&page->lru); 592 rmv_page_order(page); 593 area->nr_free--; 594 zone->free_pages -= 1UL << order; 595 expand(zone, page, order, current_order, area); 596 return page; 597 } 598 599 return NULL; 600} 601 602/* 603 * Obtain a specified number of elements from the buddy allocator, all under 604 * a single hold of the lock, for efficiency. Add them to the supplied list. 605 * Returns the number of new pages which were placed at *list. 606 */ 607static int rmqueue_bulk(struct zone *zone, unsigned int order, 608 unsigned long count, struct list_head *list) 609{ 610 int i; 611 612 spin_lock(&zone->lock); 613 for (i = 0; i < count; ++i) { 614 struct page *page = __rmqueue(zone, order); 615 if (unlikely(page == NULL)) 616 break; 617 list_add_tail(&page->lru, list); 618 } 619 spin_unlock(&zone->lock); 620 return i; 621} 622 623#ifdef CONFIG_NUMA 624/* 625 * Called from the slab reaper to drain pagesets on a particular node that 626 * belong to the currently executing processor. 627 * Note that this function must be called with the thread pinned to 628 * a single processor. 629 */ 630void drain_node_pages(int nodeid) 631{ 632 int i, z; 633 unsigned long flags; 634 635 for (z = 0; z < MAX_NR_ZONES; z++) { 636 struct zone *zone = NODE_DATA(nodeid)->node_zones + z; 637 struct per_cpu_pageset *pset; 638 639 pset = zone_pcp(zone, smp_processor_id()); 640 for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) { 641 struct per_cpu_pages *pcp; 642 643 pcp = &pset->pcp[i]; 644 if (pcp->count) { 645 local_irq_save(flags); 646 free_pages_bulk(zone, pcp->count, &pcp->list, 0); 647 pcp->count = 0; 648 local_irq_restore(flags); 649 } 650 } 651 } 652} 653#endif 654 655#if defined(CONFIG_PM) || defined(CONFIG_HOTPLUG_CPU) 656static void __drain_pages(unsigned int cpu) 657{ 658 unsigned long flags; 659 struct zone *zone; 660 int i; 661 662 for_each_zone(zone) { 663 struct per_cpu_pageset *pset; 664 665 pset = zone_pcp(zone, cpu); 666 for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) { 667 struct per_cpu_pages *pcp; 668 669 pcp = &pset->pcp[i]; 670 local_irq_save(flags); 671 free_pages_bulk(zone, pcp->count, &pcp->list, 0); 672 pcp->count = 0; 673 local_irq_restore(flags); 674 } 675 } 676} 677#endif /* CONFIG_PM || CONFIG_HOTPLUG_CPU */ 678 679#ifdef CONFIG_PM 680 681void mark_free_pages(struct zone *zone) 682{ 683 unsigned long zone_pfn, flags; 684 int order; 685 struct list_head *curr; 686 687 if (!zone->spanned_pages) 688 return; 689 690 spin_lock_irqsave(&zone->lock, flags); 691 for (zone_pfn = 0; zone_pfn < zone->spanned_pages; ++zone_pfn) 692 ClearPageNosaveFree(pfn_to_page(zone_pfn + zone->zone_start_pfn)); 693 694 for (order = MAX_ORDER - 1; order >= 0; --order) 695 list_for_each(curr, &zone->free_area[order].free_list) { 696 unsigned long start_pfn, i; 697 698 start_pfn = page_to_pfn(list_entry(curr, struct page, lru)); 699 700 for (i=0; i < (1<<order); i++) 701 SetPageNosaveFree(pfn_to_page(start_pfn+i)); 702 } 703 spin_unlock_irqrestore(&zone->lock, flags); 704} 705 706/* 707 * Spill all of this CPU's per-cpu pages back into the buddy allocator. 708 */ 709void drain_local_pages(void) 710{ 711 unsigned long flags; 712 713 local_irq_save(flags); 714 __drain_pages(smp_processor_id()); 715 local_irq_restore(flags); 716} 717#endif /* CONFIG_PM */ 718 719/* 720 * Free a 0-order page 721 */ 722static void fastcall free_hot_cold_page(struct page *page, int cold) 723{ 724 struct zone *zone = page_zone(page); 725 struct per_cpu_pages *pcp; 726 unsigned long flags; 727 728 arch_free_page(page, 0); 729 730 if (PageAnon(page)) 731 page->mapping = NULL; 732 if (free_pages_check(page)) 733 return; 734 735 kernel_map_pages(page, 1, 0); 736 737 pcp = &zone_pcp(zone, get_cpu())->pcp[cold]; 738 local_irq_save(flags); 739 __count_vm_event(PGFREE); 740 list_add(&page->lru, &pcp->list); 741 pcp->count++; 742 if (pcp->count >= pcp->high) { 743 free_pages_bulk(zone, pcp->batch, &pcp->list, 0); 744 pcp->count -= pcp->batch; 745 } 746 local_irq_restore(flags); 747 put_cpu(); 748} 749 750void fastcall free_hot_page(struct page *page) 751{ 752 free_hot_cold_page(page, 0); 753} 754 755void fastcall free_cold_page(struct page *page) 756{ 757 free_hot_cold_page(page, 1); 758} 759 760/* 761 * split_page takes a non-compound higher-order page, and splits it into 762 * n (1<<order) sub-pages: page[0..n] 763 * Each sub-page must be freed individually. 764 * 765 * Note: this is probably too low level an operation for use in drivers. 766 * Please consult with lkml before using this in your driver. 767 */ 768void split_page(struct page *page, unsigned int order) 769{ 770 int i; 771 772 VM_BUG_ON(PageCompound(page)); 773 VM_BUG_ON(!page_count(page)); 774 for (i = 1; i < (1 << order); i++) 775 set_page_refcounted(page + i); 776} 777 778/* 779 * Really, prep_compound_page() should be called from __rmqueue_bulk(). But 780 * we cheat by calling it from here, in the order > 0 path. Saves a branch 781 * or two. 782 */ 783static struct page *buffered_rmqueue(struct zonelist *zonelist, 784 struct zone *zone, int order, gfp_t gfp_flags) 785{ 786 unsigned long flags; 787 struct page *page; 788 int cold = !!(gfp_flags & __GFP_COLD); 789 int cpu; 790 791again: 792 cpu = get_cpu(); 793 if (likely(order == 0)) { 794 struct per_cpu_pages *pcp; 795 796 pcp = &zone_pcp(zone, cpu)->pcp[cold]; 797 local_irq_save(flags); 798 if (!pcp->count) { 799 pcp->count += rmqueue_bulk(zone, 0, 800 pcp->batch, &pcp->list); 801 if (unlikely(!pcp->count)) 802 goto failed; 803 } 804 page = list_entry(pcp->list.next, struct page, lru); 805 list_del(&page->lru); 806 pcp->count--; 807 } else { 808 spin_lock_irqsave(&zone->lock, flags); 809 page = __rmqueue(zone, order); 810 spin_unlock(&zone->lock); 811 if (!page) 812 goto failed; 813 } 814 815 __count_zone_vm_events(PGALLOC, zone, 1 << order); 816 zone_statistics(zonelist, zone); 817 local_irq_restore(flags); 818 put_cpu(); 819 820 VM_BUG_ON(bad_range(zone, page)); 821 if (prep_new_page(page, order, gfp_flags)) 822 goto again; 823 return page; 824 825failed: 826 local_irq_restore(flags); 827 put_cpu(); 828 return NULL; 829} 830 831#define ALLOC_NO_WATERMARKS 0x01 /* don't check watermarks at all */ 832#define ALLOC_WMARK_MIN 0x02 /* use pages_min watermark */ 833#define ALLOC_WMARK_LOW 0x04 /* use pages_low watermark */ 834#define ALLOC_WMARK_HIGH 0x08 /* use pages_high watermark */ 835#define ALLOC_HARDER 0x10 /* try to alloc harder */ 836#define ALLOC_HIGH 0x20 /* __GFP_HIGH set */ 837#define ALLOC_CPUSET 0x40 /* check for correct cpuset */ 838 839/* 840 * Return 1 if free pages are above 'mark'. This takes into account the order 841 * of the allocation. 842 */ 843int zone_watermark_ok(struct zone *z, int order, unsigned long mark, 844 int classzone_idx, int alloc_flags) 845{ 846 /* free_pages my go negative - that's OK */ 847 long min = mark, free_pages = z->free_pages - (1 << order) + 1; 848 int o; 849 850 if (alloc_flags & ALLOC_HIGH) 851 min -= min / 2; 852 if (alloc_flags & ALLOC_HARDER) 853 min -= min / 4; 854 855 if (free_pages <= min + z->lowmem_reserve[classzone_idx]) 856 return 0; 857 for (o = 0; o < order; o++) { 858 /* At the next order, this order's pages become unavailable */ 859 free_pages -= z->free_area[o].nr_free << o; 860 861 /* Require fewer higher order pages to be free */ 862 min >>= 1; 863 864 if (free_pages <= min) 865 return 0; 866 } 867 return 1; 868} 869 870/* 871 * get_page_from_freeliest goes through the zonelist trying to allocate 872 * a page. 873 */ 874static struct page * 875get_page_from_freelist(gfp_t gfp_mask, unsigned int order, 876 struct zonelist *zonelist, int alloc_flags) 877{ 878 struct zone **z = zonelist->zones; 879 struct page *page = NULL; 880 int classzone_idx = zone_idx(*z); 881 882 /* 883 * Go through the zonelist once, looking for a zone with enough free. 884 * See also cpuset_zone_allowed() comment in kernel/cpuset.c. 885 */ 886 do { 887 if ((alloc_flags & ALLOC_CPUSET) && 888 !cpuset_zone_allowed(*z, gfp_mask)) 889 continue; 890 891 if (!(alloc_flags & ALLOC_NO_WATERMARKS)) { 892 unsigned long mark; 893 if (alloc_flags & ALLOC_WMARK_MIN) 894 mark = (*z)->pages_min; 895 else if (alloc_flags & ALLOC_WMARK_LOW) 896 mark = (*z)->pages_low; 897 else 898 mark = (*z)->pages_high; 899 if (!zone_watermark_ok(*z, order, mark, 900 classzone_idx, alloc_flags)) 901 if (!zone_reclaim_mode || 902 !zone_reclaim(*z, gfp_mask, order)) 903 continue; 904 } 905 906 page = buffered_rmqueue(zonelist, *z, order, gfp_mask); 907 if (page) { 908 break; 909 } 910 } while (*(++z) != NULL); 911 return page; 912} 913 914/* 915 * This is the 'heart' of the zoned buddy allocator. 916 */ 917struct page * fastcall 918__alloc_pages(gfp_t gfp_mask, unsigned int order, 919 struct zonelist *zonelist) 920{ 921 const gfp_t wait = gfp_mask & __GFP_WAIT; 922 struct zone **z; 923 struct page *page; 924 struct reclaim_state reclaim_state; 925 struct task_struct *p = current; 926 int do_retry; 927 int alloc_flags; 928 int did_some_progress; 929 930 might_sleep_if(wait); 931 932restart: 933 z = zonelist->zones; /* the list of zones suitable for gfp_mask */ 934 935 if (unlikely(*z == NULL)) { 936 /* Should this ever happen?? */ 937 return NULL; 938 } 939 940 page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order, 941 zonelist, ALLOC_WMARK_LOW|ALLOC_CPUSET); 942 if (page) 943 goto got_pg; 944 945 do { 946 wakeup_kswapd(*z, order); 947 } while (*(++z)); 948 949 /* 950 * OK, we're below the kswapd watermark and have kicked background 951 * reclaim. Now things get more complex, so set up alloc_flags according 952 * to how we want to proceed. 953 * 954 * The caller may dip into page reserves a bit more if the caller 955 * cannot run direct reclaim, or if the caller has realtime scheduling 956 * policy or is asking for __GFP_HIGH memory. GFP_ATOMIC requests will 957 * set both ALLOC_HARDER (!wait) and ALLOC_HIGH (__GFP_HIGH). 958 */ 959 alloc_flags = ALLOC_WMARK_MIN; 960 if ((unlikely(rt_task(p)) && !in_interrupt()) || !wait) 961 alloc_flags |= ALLOC_HARDER; 962 if (gfp_mask & __GFP_HIGH) 963 alloc_flags |= ALLOC_HIGH; 964 if (wait) 965 alloc_flags |= ALLOC_CPUSET; 966 967 /* 968 * Go through the zonelist again. Let __GFP_HIGH and allocations 969 * coming from realtime tasks go deeper into reserves. 970 * 971 * This is the last chance, in general, before the goto nopage. 972 * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc. 973 * See also cpuset_zone_allowed() comment in kernel/cpuset.c. 974 */ 975 page = get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags); 976 if (page) 977 goto got_pg; 978 979 /* This allocation should allow future memory freeing. */ 980 981 if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE))) 982 && !in_interrupt()) { 983 if (!(gfp_mask & __GFP_NOMEMALLOC)) { 984nofail_alloc: 985 /* go through the zonelist yet again, ignoring mins */ 986 page = get_page_from_freelist(gfp_mask, order, 987 zonelist, ALLOC_NO_WATERMARKS); 988 if (page) 989 goto got_pg; 990 if (gfp_mask & __GFP_NOFAIL) { 991 blk_congestion_wait(WRITE, HZ/50); 992 goto nofail_alloc; 993 } 994 } 995 goto nopage; 996 } 997 998 /* Atomic allocations - we can't balance anything */ 999 if (!wait) 1000 goto nopage; 1001 1002rebalance: 1003 cond_resched(); 1004 1005 /* We now go into synchronous reclaim */ 1006 cpuset_memory_pressure_bump(); 1007 p->flags |= PF_MEMALLOC; 1008 reclaim_state.reclaimed_slab = 0; 1009 p->reclaim_state = &reclaim_state; 1010 1011 did_some_progress = try_to_free_pages(zonelist->zones, gfp_mask); 1012 1013 p->reclaim_state = NULL; 1014 p->flags &= ~PF_MEMALLOC; 1015 1016 cond_resched(); 1017 1018 if (likely(did_some_progress)) { 1019 page = get_page_from_freelist(gfp_mask, order, 1020 zonelist, alloc_flags); 1021 if (page) 1022 goto got_pg; 1023 } else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) { 1024 /* 1025 * Go through the zonelist yet one more time, keep 1026 * very high watermark here, this is only to catch 1027 * a parallel oom killing, we must fail if we're still 1028 * under heavy pressure. 1029 */ 1030 page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order, 1031 zonelist, ALLOC_WMARK_HIGH|ALLOC_CPUSET); 1032 if (page) 1033 goto got_pg; 1034 1035 out_of_memory(zonelist, gfp_mask, order); 1036 goto restart; 1037 } 1038 1039 /* 1040 * Don't let big-order allocations loop unless the caller explicitly 1041 * requests that. Wait for some write requests to complete then retry. 1042 * 1043 * In this implementation, __GFP_REPEAT means __GFP_NOFAIL for order 1044 * <= 3, but that may not be true in other implementations. 1045 */ 1046 do_retry = 0; 1047 if (!(gfp_mask & __GFP_NORETRY)) { 1048 if ((order <= 3) || (gfp_mask & __GFP_REPEAT)) 1049 do_retry = 1; 1050 if (gfp_mask & __GFP_NOFAIL) 1051 do_retry = 1; 1052 } 1053 if (do_retry) { 1054 blk_congestion_wait(WRITE, HZ/50); 1055 goto rebalance; 1056 } 1057 1058nopage: 1059 if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) { 1060 printk(KERN_WARNING "%s: page allocation failure." 1061 " order:%d, mode:0x%x\n", 1062 p->comm, order, gfp_mask); 1063 dump_stack(); 1064 show_mem(); 1065 } 1066got_pg: 1067 return page; 1068} 1069 1070EXPORT_SYMBOL(__alloc_pages); 1071 1072/* 1073 * Common helper functions. 1074 */ 1075fastcall unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order) 1076{ 1077 struct page * page; 1078 page = alloc_pages(gfp_mask, order); 1079 if (!page) 1080 return 0; 1081 return (unsigned long) page_address(page); 1082} 1083 1084EXPORT_SYMBOL(__get_free_pages); 1085 1086fastcall unsigned long get_zeroed_page(gfp_t gfp_mask) 1087{ 1088 struct page * page; 1089 1090 /* 1091 * get_zeroed_page() returns a 32-bit address, which cannot represent 1092 * a highmem page 1093 */ 1094 VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0); 1095 1096 page = alloc_pages(gfp_mask | __GFP_ZERO, 0); 1097 if (page) 1098 return (unsigned long) page_address(page); 1099 return 0; 1100} 1101 1102EXPORT_SYMBOL(get_zeroed_page); 1103 1104void __pagevec_free(struct pagevec *pvec) 1105{ 1106 int i = pagevec_count(pvec); 1107 1108 while (--i >= 0) 1109 free_hot_cold_page(pvec->pages[i], pvec->cold); 1110} 1111 1112fastcall void __free_pages(struct page *page, unsigned int order) 1113{ 1114 if (put_page_testzero(page)) { 1115 if (order == 0) 1116 free_hot_page(page); 1117 else 1118 __free_pages_ok(page, order); 1119 } 1120} 1121 1122EXPORT_SYMBOL(__free_pages); 1123 1124fastcall void free_pages(unsigned long addr, unsigned int order) 1125{ 1126 if (addr != 0) { 1127 VM_BUG_ON(!virt_addr_valid((void *)addr)); 1128 __free_pages(virt_to_page((void *)addr), order); 1129 } 1130} 1131 1132EXPORT_SYMBOL(free_pages); 1133 1134/* 1135 * Total amount of free (allocatable) RAM: 1136 */ 1137unsigned int nr_free_pages(void) 1138{ 1139 unsigned int sum = 0; 1140 struct zone *zone; 1141 1142 for_each_zone(zone) 1143 sum += zone->free_pages; 1144 1145 return sum; 1146} 1147 1148EXPORT_SYMBOL(nr_free_pages); 1149 1150#ifdef CONFIG_NUMA 1151unsigned int nr_free_pages_pgdat(pg_data_t *pgdat) 1152{ 1153 unsigned int i, sum = 0; 1154 1155 for (i = 0; i < MAX_NR_ZONES; i++) 1156 sum += pgdat->node_zones[i].free_pages; 1157 1158 return sum; 1159} 1160#endif 1161 1162static unsigned int nr_free_zone_pages(int offset) 1163{ 1164 /* Just pick one node, since fallback list is circular */ 1165 pg_data_t *pgdat = NODE_DATA(numa_node_id()); 1166 unsigned int sum = 0; 1167 1168 struct zonelist *zonelist = pgdat->node_zonelists + offset; 1169 struct zone **zonep = zonelist->zones; 1170 struct zone *zone; 1171 1172 for (zone = *zonep++; zone; zone = *zonep++) { 1173 unsigned long size = zone->present_pages; 1174 unsigned long high = zone->pages_high; 1175 if (size > high) 1176 sum += size - high; 1177 } 1178 1179 return sum; 1180} 1181 1182/* 1183 * Amount of free RAM allocatable within ZONE_DMA and ZONE_NORMAL 1184 */ 1185unsigned int nr_free_buffer_pages(void) 1186{ 1187 return nr_free_zone_pages(gfp_zone(GFP_USER)); 1188} 1189 1190/* 1191 * Amount of free RAM allocatable within all zones 1192 */ 1193unsigned int nr_free_pagecache_pages(void) 1194{ 1195 return nr_free_zone_pages(gfp_zone(GFP_HIGHUSER)); 1196} 1197#ifdef CONFIG_NUMA 1198static void show_node(struct zone *zone) 1199{ 1200 printk("Node %d ", zone->zone_pgdat->node_id); 1201} 1202#else 1203#define show_node(zone) do { } while (0) 1204#endif 1205 1206void si_meminfo(struct sysinfo *val) 1207{ 1208 val->totalram = totalram_pages; 1209 val->sharedram = 0; 1210 val->freeram = nr_free_pages(); 1211 val->bufferram = nr_blockdev_pages(); 1212 val->totalhigh = totalhigh_pages; 1213 val->freehigh = nr_free_highpages(); 1214 val->mem_unit = PAGE_SIZE; 1215} 1216 1217EXPORT_SYMBOL(si_meminfo); 1218 1219#ifdef CONFIG_NUMA 1220void si_meminfo_node(struct sysinfo *val, int nid) 1221{ 1222 pg_data_t *pgdat = NODE_DATA(nid); 1223 1224 val->totalram = pgdat->node_present_pages; 1225 val->freeram = nr_free_pages_pgdat(pgdat); 1226#ifdef CONFIG_HIGHMEM 1227 val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages; 1228 val->freehigh = pgdat->node_zones[ZONE_HIGHMEM].free_pages; 1229#else 1230 val->totalhigh = 0; 1231 val->freehigh = 0; 1232#endif 1233 val->mem_unit = PAGE_SIZE; 1234} 1235#endif 1236 1237#define K(x) ((x) << (PAGE_SHIFT-10)) 1238 1239/* 1240 * Show free area list (used inside shift_scroll-lock stuff) 1241 * We also calculate the percentage fragmentation. We do this by counting the 1242 * memory on each free list with the exception of the first item on the list. 1243 */ 1244void show_free_areas(void) 1245{ 1246 int cpu, temperature; 1247 unsigned long active; 1248 unsigned long inactive; 1249 unsigned long free; 1250 struct zone *zone; 1251 1252 for_each_zone(zone) { 1253 show_node(zone); 1254 printk("%s per-cpu:", zone->name); 1255 1256 if (!populated_zone(zone)) { 1257 printk(" empty\n"); 1258 continue; 1259 } else 1260 printk("\n"); 1261 1262 for_each_online_cpu(cpu) { 1263 struct per_cpu_pageset *pageset; 1264 1265 pageset = zone_pcp(zone, cpu); 1266 1267 for (temperature = 0; temperature < 2; temperature++) 1268 printk("cpu %d %s: high %d, batch %d used:%d\n", 1269 cpu, 1270 temperature ? "cold" : "hot", 1271 pageset->pcp[temperature].high, 1272 pageset->pcp[temperature].batch, 1273 pageset->pcp[temperature].count); 1274 } 1275 } 1276 1277 get_zone_counts(&active, &inactive, &free); 1278 1279 printk("Active:%lu inactive:%lu dirty:%lu writeback:%lu " 1280 "unstable:%lu free:%u slab:%lu mapped:%lu pagetables:%lu\n", 1281 active, 1282 inactive, 1283 global_page_state(NR_FILE_DIRTY), 1284 global_page_state(NR_WRITEBACK), 1285 global_page_state(NR_UNSTABLE_NFS), 1286 nr_free_pages(), 1287 global_page_state(NR_SLAB), 1288 global_page_state(NR_FILE_MAPPED), 1289 global_page_state(NR_PAGETABLE)); 1290 1291 for_each_zone(zone) { 1292 int i; 1293 1294 show_node(zone); 1295 printk("%s" 1296 " free:%lukB" 1297 " min:%lukB" 1298 " low:%lukB" 1299 " high:%lukB" 1300 " active:%lukB" 1301 " inactive:%lukB" 1302 " present:%lukB" 1303 " pages_scanned:%lu" 1304 " all_unreclaimable? %s" 1305 "\n", 1306 zone->name, 1307 K(zone->free_pages), 1308 K(zone->pages_min), 1309 K(zone->pages_low), 1310 K(zone->pages_high), 1311 K(zone->nr_active), 1312 K(zone->nr_inactive), 1313 K(zone->present_pages), 1314 zone->pages_scanned, 1315 (zone->all_unreclaimable ? "yes" : "no") 1316 ); 1317 printk("lowmem_reserve[]:"); 1318 for (i = 0; i < MAX_NR_ZONES; i++) 1319 printk(" %lu", zone->lowmem_reserve[i]); 1320 printk("\n"); 1321 } 1322 1323 for_each_zone(zone) { 1324 unsigned long nr[MAX_ORDER], flags, order, total = 0; 1325 1326 show_node(zone); 1327 printk("%s: ", zone->name); 1328 if (!populated_zone(zone)) { 1329 printk("empty\n"); 1330 continue; 1331 } 1332 1333 spin_lock_irqsave(&zone->lock, flags); 1334 for (order = 0; order < MAX_ORDER; order++) { 1335 nr[order] = zone->free_area[order].nr_free; 1336 total += nr[order] << order; 1337 } 1338 spin_unlock_irqrestore(&zone->lock, flags); 1339 for (order = 0; order < MAX_ORDER; order++) 1340 printk("%lu*%lukB ", nr[order], K(1UL) << order); 1341 printk("= %lukB\n", K(total)); 1342 } 1343 1344 show_swap_cache_info(); 1345} 1346 1347/* 1348 * Builds allocation fallback zone lists. 1349 * 1350 * Add all populated zones of a node to the zonelist. 1351 */ 1352static int __meminit build_zonelists_node(pg_data_t *pgdat, 1353 struct zonelist *zonelist, int nr_zones, int zone_type) 1354{ 1355 struct zone *zone; 1356 1357 BUG_ON(zone_type >= MAX_NR_ZONES); 1358 1359 do { 1360 zone = pgdat->node_zones + zone_type; 1361 if (populated_zone(zone)) { 1362 zonelist->zones[nr_zones++] = zone; 1363 check_highest_zone(zone_type); 1364 } 1365 zone_type--; 1366 1367 } while (zone_type >= 0); 1368 return nr_zones; 1369} 1370 1371static inline int highest_zone(int zone_bits) 1372{ 1373 int res = ZONE_NORMAL; 1374 if (zone_bits & (__force int)__GFP_HIGHMEM) 1375 res = ZONE_HIGHMEM; 1376 if (zone_bits & (__force int)__GFP_DMA32) 1377 res = ZONE_DMA32; 1378 if (zone_bits & (__force int)__GFP_DMA) 1379 res = ZONE_DMA; 1380 return res; 1381} 1382 1383#ifdef CONFIG_NUMA 1384#define MAX_NODE_LOAD (num_online_nodes()) 1385static int __meminitdata node_load[MAX_NUMNODES]; 1386/** 1387 * find_next_best_node - find the next node that should appear in a given node's fallback list 1388 * @node: node whose fallback list we're appending 1389 * @used_node_mask: nodemask_t of already used nodes 1390 * 1391 * We use a number of factors to determine which is the next node that should 1392 * appear on a given node's fallback list. The node should not have appeared 1393 * already in @node's fallback list, and it should be the next closest node 1394 * according to the distance array (which contains arbitrary distance values 1395 * from each node to each node in the system), and should also prefer nodes 1396 * with no CPUs, since presumably they'll have very little allocation pressure 1397 * on them otherwise. 1398 * It returns -1 if no node is found. 1399 */ 1400static int __meminit find_next_best_node(int node, nodemask_t *used_node_mask) 1401{ 1402 int n, val; 1403 int min_val = INT_MAX; 1404 int best_node = -1; 1405 1406 /* Use the local node if we haven't already */ 1407 if (!node_isset(node, *used_node_mask)) { 1408 node_set(node, *used_node_mask); 1409 return node; 1410 } 1411 1412 for_each_online_node(n) { 1413 cpumask_t tmp; 1414 1415 /* Don't want a node to appear more than once */ 1416 if (node_isset(n, *used_node_mask)) 1417 continue; 1418 1419 /* Use the distance array to find the distance */ 1420 val = node_distance(node, n); 1421 1422 /* Penalize nodes under us ("prefer the next node") */ 1423 val += (n < node); 1424 1425 /* Give preference to headless and unused nodes */ 1426 tmp = node_to_cpumask(n); 1427 if (!cpus_empty(tmp)) 1428 val += PENALTY_FOR_NODE_WITH_CPUS; 1429 1430 /* Slight preference for less loaded node */ 1431 val *= (MAX_NODE_LOAD*MAX_NUMNODES); 1432 val += node_load[n]; 1433 1434 if (val < min_val) { 1435 min_val = val; 1436 best_node = n; 1437 } 1438 } 1439 1440 if (best_node >= 0) 1441 node_set(best_node, *used_node_mask); 1442 1443 return best_node; 1444} 1445 1446static void __meminit build_zonelists(pg_data_t *pgdat) 1447{ 1448 int i, j, k, node, local_node; 1449 int prev_node, load; 1450 struct zonelist *zonelist; 1451 nodemask_t used_mask; 1452 1453 /* initialize zonelists */ 1454 for (i = 0; i < GFP_ZONETYPES; i++) { 1455 zonelist = pgdat->node_zonelists + i; 1456 zonelist->zones[0] = NULL; 1457 } 1458 1459 /* NUMA-aware ordering of nodes */ 1460 local_node = pgdat->node_id; 1461 load = num_online_nodes(); 1462 prev_node = local_node; 1463 nodes_clear(used_mask); 1464 while ((node = find_next_best_node(local_node, &used_mask)) >= 0) { 1465 int distance = node_distance(local_node, node); 1466 1467 /* 1468 * If another node is sufficiently far away then it is better 1469 * to reclaim pages in a zone before going off node. 1470 */ 1471 if (distance > RECLAIM_DISTANCE) 1472 zone_reclaim_mode = 1; 1473 1474 /* 1475 * We don't want to pressure a particular node. 1476 * So adding penalty to the first node in same 1477 * distance group to make it round-robin. 1478 */ 1479 1480 if (distance != node_distance(local_node, prev_node)) 1481 node_load[node] += load; 1482 prev_node = node; 1483 load--; 1484 for (i = 0; i < GFP_ZONETYPES; i++) { 1485 zonelist = pgdat->node_zonelists + i; 1486 for (j = 0; zonelist->zones[j] != NULL; j++); 1487 1488 k = highest_zone(i); 1489 1490 j = build_zonelists_node(NODE_DATA(node), zonelist, j, k); 1491 zonelist->zones[j] = NULL; 1492 } 1493 } 1494} 1495 1496#else /* CONFIG_NUMA */ 1497 1498static void __meminit build_zonelists(pg_data_t *pgdat) 1499{ 1500 int i, node, local_node; 1501 enum zone_type k; 1502 enum zone_type j; 1503 1504 local_node = pgdat->node_id; 1505 for (i = 0; i < GFP_ZONETYPES; i++) { 1506 struct zonelist *zonelist; 1507 1508 zonelist = pgdat->node_zonelists + i; 1509 1510 j = 0; 1511 k = highest_zone(i); 1512 j = build_zonelists_node(pgdat, zonelist, j, k); 1513 /* 1514 * Now we build the zonelist so that it contains the zones 1515 * of all the other nodes. 1516 * We don't want to pressure a particular node, so when 1517 * building the zones for node N, we make sure that the 1518 * zones coming right after the local ones are those from 1519 * node N+1 (modulo N) 1520 */ 1521 for (node = local_node + 1; node < MAX_NUMNODES; node++) { 1522 if (!node_online(node)) 1523 continue; 1524 j = build_zonelists_node(NODE_DATA(node), zonelist, j, k); 1525 } 1526 for (node = 0; node < local_node; node++) { 1527 if (!node_online(node)) 1528 continue; 1529 j = build_zonelists_node(NODE_DATA(node), zonelist, j, k); 1530 } 1531 1532 zonelist->zones[j] = NULL; 1533 } 1534} 1535 1536#endif /* CONFIG_NUMA */ 1537 1538/* return values int ....just for stop_machine_run() */ 1539static int __meminit __build_all_zonelists(void *dummy) 1540{ 1541 int nid; 1542 for_each_online_node(nid) 1543 build_zonelists(NODE_DATA(nid)); 1544 return 0; 1545} 1546 1547void __meminit build_all_zonelists(void) 1548{ 1549 if (system_state == SYSTEM_BOOTING) { 1550 __build_all_zonelists(0); 1551 cpuset_init_current_mems_allowed(); 1552 } else { 1553 /* we have to stop all cpus to guaranntee there is no user 1554 of zonelist */ 1555 stop_machine_run(__build_all_zonelists, NULL, NR_CPUS); 1556 /* cpuset refresh routine should be here */ 1557 } 1558 vm_total_pages = nr_free_pagecache_pages(); 1559 printk("Built %i zonelists. Total pages: %ld\n", 1560 num_online_nodes(), vm_total_pages); 1561} 1562 1563/* 1564 * Helper functions to size the waitqueue hash table. 1565 * Essentially these want to choose hash table sizes sufficiently 1566 * large so that collisions trying to wait on pages are rare. 1567 * But in fact, the number of active page waitqueues on typical 1568 * systems is ridiculously low, less than 200. So this is even 1569 * conservative, even though it seems large. 1570 * 1571 * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to 1572 * waitqueues, i.e. the size of the waitq table given the number of pages. 1573 */ 1574#define PAGES_PER_WAITQUEUE 256 1575 1576#ifndef CONFIG_MEMORY_HOTPLUG 1577static inline unsigned long wait_table_hash_nr_entries(unsigned long pages) 1578{ 1579 unsigned long size = 1; 1580 1581 pages /= PAGES_PER_WAITQUEUE; 1582 1583 while (size < pages) 1584 size <<= 1; 1585 1586 /* 1587 * Once we have dozens or even hundreds of threads sleeping 1588 * on IO we've got bigger problems than wait queue collision. 1589 * Limit the size of the wait table to a reasonable size. 1590 */ 1591 size = min(size, 4096UL); 1592 1593 return max(size, 4UL); 1594} 1595#else 1596/* 1597 * A zone's size might be changed by hot-add, so it is not possible to determine 1598 * a suitable size for its wait_table. So we use the maximum size now. 1599 * 1600 * The max wait table size = 4096 x sizeof(wait_queue_head_t). ie: 1601 * 1602 * i386 (preemption config) : 4096 x 16 = 64Kbyte. 1603 * ia64, x86-64 (no preemption): 4096 x 20 = 80Kbyte. 1604 * ia64, x86-64 (preemption) : 4096 x 24 = 96Kbyte. 1605 * 1606 * The maximum entries are prepared when a zone's memory is (512K + 256) pages 1607 * or more by the traditional way. (See above). It equals: 1608 * 1609 * i386, x86-64, powerpc(4K page size) : = ( 2G + 1M)byte. 1610 * ia64(16K page size) : = ( 8G + 4M)byte. 1611 * powerpc (64K page size) : = (32G +16M)byte. 1612 */ 1613static inline unsigned long wait_table_hash_nr_entries(unsigned long pages) 1614{ 1615 return 4096UL; 1616} 1617#endif 1618 1619/* 1620 * This is an integer logarithm so that shifts can be used later 1621 * to extract the more random high bits from the multiplicative 1622 * hash function before the remainder is taken. 1623 */ 1624static inline unsigned long wait_table_bits(unsigned long size) 1625{ 1626 return ffz(~size); 1627} 1628 1629#define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1)) 1630 1631static void __init calculate_zone_totalpages(struct pglist_data *pgdat, 1632 unsigned long *zones_size, unsigned long *zholes_size) 1633{ 1634 unsigned long realtotalpages, totalpages = 0; 1635 int i; 1636 1637 for (i = 0; i < MAX_NR_ZONES; i++) 1638 totalpages += zones_size[i]; 1639 pgdat->node_spanned_pages = totalpages; 1640 1641 realtotalpages = totalpages; 1642 if (zholes_size) 1643 for (i = 0; i < MAX_NR_ZONES; i++) 1644 realtotalpages -= zholes_size[i]; 1645 pgdat->node_present_pages = realtotalpages; 1646 printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id, realtotalpages); 1647} 1648 1649 1650/* 1651 * Initially all pages are reserved - free ones are freed 1652 * up by free_all_bootmem() once the early boot process is 1653 * done. Non-atomic initialization, single-pass. 1654 */ 1655void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone, 1656 unsigned long start_pfn) 1657{ 1658 struct page *page; 1659 unsigned long end_pfn = start_pfn + size; 1660 unsigned long pfn; 1661 1662 for (pfn = start_pfn; pfn < end_pfn; pfn++) { 1663 if (!early_pfn_valid(pfn)) 1664 continue; 1665 page = pfn_to_page(pfn); 1666 set_page_links(page, zone, nid, pfn); 1667 init_page_count(page); 1668 reset_page_mapcount(page); 1669 SetPageReserved(page); 1670 INIT_LIST_HEAD(&page->lru); 1671#ifdef WANT_PAGE_VIRTUAL 1672 /* The shift won't overflow because ZONE_NORMAL is below 4G. */ 1673 if (!is_highmem_idx(zone)) 1674 set_page_address(page, __va(pfn << PAGE_SHIFT)); 1675#endif 1676 } 1677} 1678 1679void zone_init_free_lists(struct pglist_data *pgdat, struct zone *zone, 1680 unsigned long size) 1681{ 1682 int order; 1683 for (order = 0; order < MAX_ORDER ; order++) { 1684 INIT_LIST_HEAD(&zone->free_area[order].free_list); 1685 zone->free_area[order].nr_free = 0; 1686 } 1687} 1688 1689#define ZONETABLE_INDEX(x, zone_nr) ((x << ZONES_SHIFT) | zone_nr) 1690void zonetable_add(struct zone *zone, int nid, enum zone_type zid, 1691 unsigned long pfn, unsigned long size) 1692{ 1693 unsigned long snum = pfn_to_section_nr(pfn); 1694 unsigned long end = pfn_to_section_nr(pfn + size); 1695 1696 if (FLAGS_HAS_NODE) 1697 zone_table[ZONETABLE_INDEX(nid, zid)] = zone; 1698 else 1699 for (; snum <= end; snum++) 1700 zone_table[ZONETABLE_INDEX(snum, zid)] = zone; 1701} 1702 1703#ifndef __HAVE_ARCH_MEMMAP_INIT 1704#define memmap_init(size, nid, zone, start_pfn) \ 1705 memmap_init_zone((size), (nid), (zone), (start_pfn)) 1706#endif 1707 1708static int __cpuinit zone_batchsize(struct zone *zone) 1709{ 1710 int batch; 1711 1712 /* 1713 * The per-cpu-pages pools are set to around 1000th of the 1714 * size of the zone. But no more than 1/2 of a meg. 1715 * 1716 * OK, so we don't know how big the cache is. So guess. 1717 */ 1718 batch = zone->present_pages / 1024; 1719 if (batch * PAGE_SIZE > 512 * 1024) 1720 batch = (512 * 1024) / PAGE_SIZE; 1721 batch /= 4; /* We effectively *= 4 below */ 1722 if (batch < 1) 1723 batch = 1; 1724 1725 /* 1726 * Clamp the batch to a 2^n - 1 value. Having a power 1727 * of 2 value was found to be more likely to have 1728 * suboptimal cache aliasing properties in some cases. 1729 * 1730 * For example if 2 tasks are alternately allocating 1731 * batches of pages, one task can end up with a lot 1732 * of pages of one half of the possible page colors 1733 * and the other with pages of the other colors. 1734 */ 1735 batch = (1 << (fls(batch + batch/2)-1)) - 1; 1736 1737 return batch; 1738} 1739 1740inline void setup_pageset(struct per_cpu_pageset *p, unsigned long batch) 1741{ 1742 struct per_cpu_pages *pcp; 1743 1744 memset(p, 0, sizeof(*p)); 1745 1746 pcp = &p->pcp[0]; /* hot */ 1747 pcp->count = 0; 1748 pcp->high = 6 * batch; 1749 pcp->batch = max(1UL, 1 * batch); 1750 INIT_LIST_HEAD(&pcp->list); 1751 1752 pcp = &p->pcp[1]; /* cold*/ 1753 pcp->count = 0; 1754 pcp->high = 2 * batch; 1755 pcp->batch = max(1UL, batch/2); 1756 INIT_LIST_HEAD(&pcp->list); 1757} 1758 1759/* 1760 * setup_pagelist_highmark() sets the high water mark for hot per_cpu_pagelist 1761 * to the value high for the pageset p. 1762 */ 1763 1764static void setup_pagelist_highmark(struct per_cpu_pageset *p, 1765 unsigned long high) 1766{ 1767 struct per_cpu_pages *pcp; 1768 1769 pcp = &p->pcp[0]; /* hot list */ 1770 pcp->high = high; 1771 pcp->batch = max(1UL, high/4); 1772 if ((high/4) > (PAGE_SHIFT * 8)) 1773 pcp->batch = PAGE_SHIFT * 8; 1774} 1775 1776 1777#ifdef CONFIG_NUMA 1778/* 1779 * Boot pageset table. One per cpu which is going to be used for all 1780 * zones and all nodes. The parameters will be set in such a way 1781 * that an item put on a list will immediately be handed over to 1782 * the buddy list. This is safe since pageset manipulation is done 1783 * with interrupts disabled. 1784 * 1785 * Some NUMA counter updates may also be caught by the boot pagesets. 1786 * 1787 * The boot_pagesets must be kept even after bootup is complete for 1788 * unused processors and/or zones. They do play a role for bootstrapping 1789 * hotplugged processors. 1790 * 1791 * zoneinfo_show() and maybe other functions do 1792 * not check if the processor is online before following the pageset pointer. 1793 * Other parts of the kernel may not check if the zone is available. 1794 */ 1795static struct per_cpu_pageset boot_pageset[NR_CPUS]; 1796 1797/* 1798 * Dynamically allocate memory for the 1799 * per cpu pageset array in struct zone. 1800 */ 1801static int __cpuinit process_zones(int cpu) 1802{ 1803 struct zone *zone, *dzone; 1804 1805 for_each_zone(zone) { 1806 1807 zone_pcp(zone, cpu) = kmalloc_node(sizeof(struct per_cpu_pageset), 1808 GFP_KERNEL, cpu_to_node(cpu)); 1809 if (!zone_pcp(zone, cpu)) 1810 goto bad; 1811 1812 setup_pageset(zone_pcp(zone, cpu), zone_batchsize(zone)); 1813 1814 if (percpu_pagelist_fraction) 1815 setup_pagelist_highmark(zone_pcp(zone, cpu), 1816 (zone->present_pages / percpu_pagelist_fraction)); 1817 } 1818 1819 return 0; 1820bad: 1821 for_each_zone(dzone) { 1822 if (dzone == zone) 1823 break; 1824 kfree(zone_pcp(dzone, cpu)); 1825 zone_pcp(dzone, cpu) = NULL; 1826 } 1827 return -ENOMEM; 1828} 1829 1830static inline void free_zone_pagesets(int cpu) 1831{ 1832 struct zone *zone; 1833 1834 for_each_zone(zone) { 1835 struct per_cpu_pageset *pset = zone_pcp(zone, cpu); 1836 1837 /* Free per_cpu_pageset if it is slab allocated */ 1838 if (pset != &boot_pageset[cpu]) 1839 kfree(pset); 1840 zone_pcp(zone, cpu) = NULL; 1841 } 1842} 1843 1844static int __cpuinit pageset_cpuup_callback(struct notifier_block *nfb, 1845 unsigned long action, 1846 void *hcpu) 1847{ 1848 int cpu = (long)hcpu; 1849 int ret = NOTIFY_OK; 1850 1851 switch (action) { 1852 case CPU_UP_PREPARE: 1853 if (process_zones(cpu)) 1854 ret = NOTIFY_BAD; 1855 break; 1856 case CPU_UP_CANCELED: 1857 case CPU_DEAD: 1858 free_zone_pagesets(cpu); 1859 break; 1860 default: 1861 break; 1862 } 1863 return ret; 1864} 1865 1866static struct notifier_block __cpuinitdata pageset_notifier = 1867 { &pageset_cpuup_callback, NULL, 0 }; 1868 1869void __init setup_per_cpu_pageset(void) 1870{ 1871 int err; 1872 1873 /* Initialize per_cpu_pageset for cpu 0. 1874 * A cpuup callback will do this for every cpu 1875 * as it comes online 1876 */ 1877 err = process_zones(smp_processor_id()); 1878 BUG_ON(err); 1879 register_cpu_notifier(&pageset_notifier); 1880} 1881 1882#endif 1883 1884static __meminit 1885int zone_wait_table_init(struct zone *zone, unsigned long zone_size_pages) 1886{ 1887 int i; 1888 struct pglist_data *pgdat = zone->zone_pgdat; 1889 size_t alloc_size; 1890 1891 /* 1892 * The per-page waitqueue mechanism uses hashed waitqueues 1893 * per zone. 1894 */ 1895 zone->wait_table_hash_nr_entries = 1896 wait_table_hash_nr_entries(zone_size_pages); 1897 zone->wait_table_bits = 1898 wait_table_bits(zone->wait_table_hash_nr_entries); 1899 alloc_size = zone->wait_table_hash_nr_entries 1900 * sizeof(wait_queue_head_t); 1901 1902 if (system_state == SYSTEM_BOOTING) { 1903 zone->wait_table = (wait_queue_head_t *) 1904 alloc_bootmem_node(pgdat, alloc_size); 1905 } else { 1906 /* 1907 * This case means that a zone whose size was 0 gets new memory 1908 * via memory hot-add. 1909 * But it may be the case that a new node was hot-added. In 1910 * this case vmalloc() will not be able to use this new node's 1911 * memory - this wait_table must be initialized to use this new 1912 * node itself as well. 1913 * To use this new node's memory, further consideration will be 1914 * necessary. 1915 */ 1916 zone->wait_table = (wait_queue_head_t *)vmalloc(alloc_size); 1917 } 1918 if (!zone->wait_table) 1919 return -ENOMEM; 1920 1921 for(i = 0; i < zone->wait_table_hash_nr_entries; ++i) 1922 init_waitqueue_head(zone->wait_table + i); 1923 1924 return 0; 1925} 1926 1927static __meminit void zone_pcp_init(struct zone *zone) 1928{ 1929 int cpu; 1930 unsigned long batch = zone_batchsize(zone); 1931 1932 for (cpu = 0; cpu < NR_CPUS; cpu++) { 1933#ifdef CONFIG_NUMA 1934 /* Early boot. Slab allocator not functional yet */ 1935 zone_pcp(zone, cpu) = &boot_pageset[cpu]; 1936 setup_pageset(&boot_pageset[cpu],0); 1937#else 1938 setup_pageset(zone_pcp(zone,cpu), batch); 1939#endif 1940 } 1941 if (zone->present_pages) 1942 printk(KERN_DEBUG " %s zone: %lu pages, LIFO batch:%lu\n", 1943 zone->name, zone->present_pages, batch); 1944} 1945 1946__meminit int init_currently_empty_zone(struct zone *zone, 1947 unsigned long zone_start_pfn, 1948 unsigned long size) 1949{ 1950 struct pglist_data *pgdat = zone->zone_pgdat; 1951 int ret; 1952 ret = zone_wait_table_init(zone, size); 1953 if (ret) 1954 return ret; 1955 pgdat->nr_zones = zone_idx(zone) + 1; 1956 1957 zone->zone_start_pfn = zone_start_pfn; 1958 1959 memmap_init(size, pgdat->node_id, zone_idx(zone), zone_start_pfn); 1960 1961 zone_init_free_lists(pgdat, zone, zone->spanned_pages); 1962 1963 return 0; 1964} 1965 1966/* 1967 * Set up the zone data structures: 1968 * - mark all pages reserved 1969 * - mark all memory queues empty 1970 * - clear the memory bitmaps 1971 */ 1972static void __meminit free_area_init_core(struct pglist_data *pgdat, 1973 unsigned long *zones_size, unsigned long *zholes_size) 1974{ 1975 enum zone_type j; 1976 int nid = pgdat->node_id; 1977 unsigned long zone_start_pfn = pgdat->node_start_pfn; 1978 int ret; 1979 1980 pgdat_resize_init(pgdat); 1981 pgdat->nr_zones = 0; 1982 init_waitqueue_head(&pgdat->kswapd_wait); 1983 pgdat->kswapd_max_order = 0; 1984 1985 for (j = 0; j < MAX_NR_ZONES; j++) { 1986 struct zone *zone = pgdat->node_zones + j; 1987 unsigned long size, realsize; 1988 1989 realsize = size = zones_size[j]; 1990 if (zholes_size) 1991 realsize -= zholes_size[j]; 1992 1993 if (!is_highmem_idx(j)) 1994 nr_kernel_pages += realsize; 1995 nr_all_pages += realsize; 1996 1997 zone->spanned_pages = size; 1998 zone->present_pages = realsize; 1999#ifdef CONFIG_NUMA 2000 zone->min_unmapped_ratio = (realsize*sysctl_min_unmapped_ratio) 2001 / 100; 2002#endif 2003 zone->name = zone_names[j]; 2004 spin_lock_init(&zone->lock); 2005 spin_lock_init(&zone->lru_lock); 2006 zone_seqlock_init(zone); 2007 zone->zone_pgdat = pgdat; 2008 zone->free_pages = 0; 2009 2010 zone->temp_priority = zone->prev_priority = DEF_PRIORITY; 2011 2012 zone_pcp_init(zone); 2013 INIT_LIST_HEAD(&zone->active_list); 2014 INIT_LIST_HEAD(&zone->inactive_list); 2015 zone->nr_scan_active = 0; 2016 zone->nr_scan_inactive = 0; 2017 zone->nr_active = 0; 2018 zone->nr_inactive = 0; 2019 zap_zone_vm_stats(zone); 2020 atomic_set(&zone->reclaim_in_progress, 0); 2021 if (!size) 2022 continue; 2023 2024 zonetable_add(zone, nid, j, zone_start_pfn, size); 2025 ret = init_currently_empty_zone(zone, zone_start_pfn, size); 2026 BUG_ON(ret); 2027 zone_start_pfn += size; 2028 } 2029} 2030 2031static void __init alloc_node_mem_map(struct pglist_data *pgdat) 2032{ 2033 /* Skip empty nodes */ 2034 if (!pgdat->node_spanned_pages) 2035 return; 2036 2037#ifdef CONFIG_FLAT_NODE_MEM_MAP 2038 /* ia64 gets its own node_mem_map, before this, without bootmem */ 2039 if (!pgdat->node_mem_map) { 2040 unsigned long size, start, end; 2041 struct page *map; 2042 2043 /* 2044 * The zone's endpoints aren't required to be MAX_ORDER 2045 * aligned but the node_mem_map endpoints must be in order 2046 * for the buddy allocator to function correctly. 2047 */ 2048 start = pgdat->node_start_pfn & ~(MAX_ORDER_NR_PAGES - 1); 2049 end = pgdat->node_start_pfn + pgdat->node_spanned_pages; 2050 end = ALIGN(end, MAX_ORDER_NR_PAGES); 2051 size = (end - start) * sizeof(struct page); 2052 map = alloc_remap(pgdat->node_id, size); 2053 if (!map) 2054 map = alloc_bootmem_node(pgdat, size); 2055 pgdat->node_mem_map = map + (pgdat->node_start_pfn - start); 2056 } 2057#ifdef CONFIG_FLATMEM 2058 /* 2059 * With no DISCONTIG, the global mem_map is just set as node 0's 2060 */ 2061 if (pgdat == NODE_DATA(0)) 2062 mem_map = NODE_DATA(0)->node_mem_map; 2063#endif 2064#endif /* CONFIG_FLAT_NODE_MEM_MAP */ 2065} 2066 2067void __meminit free_area_init_node(int nid, struct pglist_data *pgdat, 2068 unsigned long *zones_size, unsigned long node_start_pfn, 2069 unsigned long *zholes_size) 2070{ 2071 pgdat->node_id = nid; 2072 pgdat->node_start_pfn = node_start_pfn; 2073 calculate_zone_totalpages(pgdat, zones_size, zholes_size); 2074 2075 alloc_node_mem_map(pgdat); 2076 2077 free_area_init_core(pgdat, zones_size, zholes_size); 2078} 2079 2080#ifndef CONFIG_NEED_MULTIPLE_NODES 2081static bootmem_data_t contig_bootmem_data; 2082struct pglist_data contig_page_data = { .bdata = &contig_bootmem_data }; 2083 2084EXPORT_SYMBOL(contig_page_data); 2085#endif 2086 2087void __init free_area_init(unsigned long *zones_size) 2088{ 2089 free_area_init_node(0, NODE_DATA(0), zones_size, 2090 __pa(PAGE_OFFSET) >> PAGE_SHIFT, NULL); 2091} 2092 2093#ifdef CONFIG_HOTPLUG_CPU 2094static int page_alloc_cpu_notify(struct notifier_block *self, 2095 unsigned long action, void *hcpu) 2096{ 2097 int cpu = (unsigned long)hcpu; 2098 2099 if (action == CPU_DEAD) { 2100 local_irq_disable(); 2101 __drain_pages(cpu); 2102 vm_events_fold_cpu(cpu); 2103 local_irq_enable(); 2104 refresh_cpu_vm_stats(cpu); 2105 } 2106 return NOTIFY_OK; 2107} 2108#endif /* CONFIG_HOTPLUG_CPU */ 2109 2110void __init page_alloc_init(void) 2111{ 2112 hotcpu_notifier(page_alloc_cpu_notify, 0); 2113} 2114 2115/* 2116 * calculate_totalreserve_pages - called when sysctl_lower_zone_reserve_ratio 2117 * or min_free_kbytes changes. 2118 */ 2119static void calculate_totalreserve_pages(void) 2120{ 2121 struct pglist_data *pgdat; 2122 unsigned long reserve_pages = 0; 2123 int i, j; 2124 2125 for_each_online_pgdat(pgdat) { 2126 for (i = 0; i < MAX_NR_ZONES; i++) { 2127 struct zone *zone = pgdat->node_zones + i; 2128 unsigned long max = 0; 2129 2130 /* Find valid and maximum lowmem_reserve in the zone */ 2131 for (j = i; j < MAX_NR_ZONES; j++) { 2132 if (zone->lowmem_reserve[j] > max) 2133 max = zone->lowmem_reserve[j]; 2134 } 2135 2136 /* we treat pages_high as reserved pages. */ 2137 max += zone->pages_high; 2138 2139 if (max > zone->present_pages) 2140 max = zone->present_pages; 2141 reserve_pages += max; 2142 } 2143 } 2144 totalreserve_pages = reserve_pages; 2145} 2146 2147/* 2148 * setup_per_zone_lowmem_reserve - called whenever 2149 * sysctl_lower_zone_reserve_ratio changes. Ensures that each zone 2150 * has a correct pages reserved value, so an adequate number of 2151 * pages are left in the zone after a successful __alloc_pages(). 2152 */ 2153static void setup_per_zone_lowmem_reserve(void) 2154{ 2155 struct pglist_data *pgdat; 2156 int j, idx; 2157 2158 for_each_online_pgdat(pgdat) { 2159 for (j = 0; j < MAX_NR_ZONES; j++) { 2160 struct zone *zone = pgdat->node_zones + j; 2161 unsigned long present_pages = zone->present_pages; 2162 2163 zone->lowmem_reserve[j] = 0; 2164 2165 for (idx = j-1; idx >= 0; idx--) { 2166 struct zone *lower_zone; 2167 2168 if (sysctl_lowmem_reserve_ratio[idx] < 1) 2169 sysctl_lowmem_reserve_ratio[idx] = 1; 2170 2171 lower_zone = pgdat->node_zones + idx; 2172 lower_zone->lowmem_reserve[j] = present_pages / 2173 sysctl_lowmem_reserve_ratio[idx]; 2174 present_pages += lower_zone->present_pages; 2175 } 2176 } 2177 } 2178 2179 /* update totalreserve_pages */ 2180 calculate_totalreserve_pages(); 2181} 2182 2183/* 2184 * setup_per_zone_pages_min - called when min_free_kbytes changes. Ensures 2185 * that the pages_{min,low,high} values for each zone are set correctly 2186 * with respect to min_free_kbytes. 2187 */ 2188void setup_per_zone_pages_min(void) 2189{ 2190 unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10); 2191 unsigned long lowmem_pages = 0; 2192 struct zone *zone; 2193 unsigned long flags; 2194 2195 /* Calculate total number of !ZONE_HIGHMEM pages */ 2196 for_each_zone(zone) { 2197 if (!is_highmem(zone)) 2198 lowmem_pages += zone->present_pages; 2199 } 2200 2201 for_each_zone(zone) { 2202 u64 tmp; 2203 2204 spin_lock_irqsave(&zone->lru_lock, flags); 2205 tmp = (u64)pages_min * zone->present_pages; 2206 do_div(tmp, lowmem_pages); 2207 if (is_highmem(zone)) { 2208 /* 2209 * __GFP_HIGH and PF_MEMALLOC allocations usually don't 2210 * need highmem pages, so cap pages_min to a small 2211 * value here. 2212 * 2213 * The (pages_high-pages_low) and (pages_low-pages_min) 2214 * deltas controls asynch page reclaim, and so should 2215 * not be capped for highmem. 2216 */ 2217 int min_pages; 2218 2219 min_pages = zone->present_pages / 1024; 2220 if (min_pages < SWAP_CLUSTER_MAX) 2221 min_pages = SWAP_CLUSTER_MAX; 2222 if (min_pages > 128) 2223 min_pages = 128; 2224 zone->pages_min = min_pages; 2225 } else { 2226 /* 2227 * If it's a lowmem zone, reserve a number of pages 2228 * proportionate to the zone's size. 2229 */ 2230 zone->pages_min = tmp; 2231 } 2232 2233 zone->pages_low = zone->pages_min + (tmp >> 2); 2234 zone->pages_high = zone->pages_min + (tmp >> 1); 2235 spin_unlock_irqrestore(&zone->lru_lock, flags); 2236 } 2237 2238 /* update totalreserve_pages */ 2239 calculate_totalreserve_pages(); 2240} 2241 2242/* 2243 * Initialise min_free_kbytes. 2244 * 2245 * For small machines we want it small (128k min). For large machines 2246 * we want it large (64MB max). But it is not linear, because network 2247 * bandwidth does not increase linearly with machine size. We use 2248 * 2249 * min_free_kbytes = 4 * sqrt(lowmem_kbytes), for better accuracy: 2250 * min_free_kbytes = sqrt(lowmem_kbytes * 16) 2251 * 2252 * which yields 2253 * 2254 * 16MB: 512k 2255 * 32MB: 724k 2256 * 64MB: 1024k 2257 * 128MB: 1448k 2258 * 256MB: 2048k 2259 * 512MB: 2896k 2260 * 1024MB: 4096k 2261 * 2048MB: 5792k 2262 * 4096MB: 8192k 2263 * 8192MB: 11584k 2264 * 16384MB: 16384k 2265 */ 2266static int __init init_per_zone_pages_min(void) 2267{ 2268 unsigned long lowmem_kbytes; 2269 2270 lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10); 2271 2272 min_free_kbytes = int_sqrt(lowmem_kbytes * 16); 2273 if (min_free_kbytes < 128) 2274 min_free_kbytes = 128; 2275 if (min_free_kbytes > 65536) 2276 min_free_kbytes = 65536; 2277 setup_per_zone_pages_min(); 2278 setup_per_zone_lowmem_reserve(); 2279 return 0; 2280} 2281module_init(init_per_zone_pages_min) 2282 2283/* 2284 * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so 2285 * that we can call two helper functions whenever min_free_kbytes 2286 * changes. 2287 */ 2288int min_free_kbytes_sysctl_handler(ctl_table *table, int write, 2289 struct file *file, void __user *buffer, size_t *length, loff_t *ppos) 2290{ 2291 proc_dointvec(table, write, file, buffer, length, ppos); 2292 setup_per_zone_pages_min(); 2293 return 0; 2294} 2295 2296#ifdef CONFIG_NUMA 2297int sysctl_min_unmapped_ratio_sysctl_handler(ctl_table *table, int write, 2298 struct file *file, void __user *buffer, size_t *length, loff_t *ppos) 2299{ 2300 struct zone *zone; 2301 int rc; 2302 2303 rc = proc_dointvec_minmax(table, write, file, buffer, length, ppos); 2304 if (rc) 2305 return rc; 2306 2307 for_each_zone(zone) 2308 zone->min_unmapped_ratio = (zone->present_pages * 2309 sysctl_min_unmapped_ratio) / 100; 2310 return 0; 2311} 2312#endif 2313 2314/* 2315 * lowmem_reserve_ratio_sysctl_handler - just a wrapper around 2316 * proc_dointvec() so that we can call setup_per_zone_lowmem_reserve() 2317 * whenever sysctl_lowmem_reserve_ratio changes. 2318 * 2319 * The reserve ratio obviously has absolutely no relation with the 2320 * pages_min watermarks. The lowmem reserve ratio can only make sense 2321 * if in function of the boot time zone sizes. 2322 */ 2323int lowmem_reserve_ratio_sysctl_handler(ctl_table *table, int write, 2324 struct file *file, void __user *buffer, size_t *length, loff_t *ppos) 2325{ 2326 proc_dointvec_minmax(table, write, file, buffer, length, ppos); 2327 setup_per_zone_lowmem_reserve(); 2328 return 0; 2329} 2330 2331/* 2332 * percpu_pagelist_fraction - changes the pcp->high for each zone on each 2333 * cpu. It is the fraction of total pages in each zone that a hot per cpu pagelist 2334 * can have before it gets flushed back to buddy allocator. 2335 */ 2336 2337int percpu_pagelist_fraction_sysctl_handler(ctl_table *table, int write, 2338 struct file *file, void __user *buffer, size_t *length, loff_t *ppos) 2339{ 2340 struct zone *zone; 2341 unsigned int cpu; 2342 int ret; 2343 2344 ret = proc_dointvec_minmax(table, write, file, buffer, length, ppos); 2345 if (!write || (ret == -EINVAL)) 2346 return ret; 2347 for_each_zone(zone) { 2348 for_each_online_cpu(cpu) { 2349 unsigned long high; 2350 high = zone->present_pages / percpu_pagelist_fraction; 2351 setup_pagelist_highmark(zone_pcp(zone, cpu), high); 2352 } 2353 } 2354 return 0; 2355} 2356 2357int hashdist = HASHDIST_DEFAULT; 2358 2359#ifdef CONFIG_NUMA 2360static int __init set_hashdist(char *str) 2361{ 2362 if (!str) 2363 return 0; 2364 hashdist = simple_strtoul(str, &str, 0); 2365 return 1; 2366} 2367__setup("hashdist=", set_hashdist); 2368#endif 2369 2370/* 2371 * allocate a large system hash table from bootmem 2372 * - it is assumed that the hash table must contain an exact power-of-2 2373 * quantity of entries 2374 * - limit is the number of hash buckets, not the total allocation size 2375 */ 2376void *__init alloc_large_system_hash(const char *tablename, 2377 unsigned long bucketsize, 2378 unsigned long numentries, 2379 int scale, 2380 int flags, 2381 unsigned int *_hash_shift, 2382 unsigned int *_hash_mask, 2383 unsigned long limit) 2384{ 2385 unsigned long long max = limit; 2386 unsigned long log2qty, size; 2387 void *table = NULL; 2388 2389 /* allow the kernel cmdline to have a say */ 2390 if (!numentries) { 2391 /* round applicable memory size up to nearest megabyte */ 2392 numentries = (flags & HASH_HIGHMEM) ? nr_all_pages : nr_kernel_pages; 2393 numentries += (1UL << (20 - PAGE_SHIFT)) - 1; 2394 numentries >>= 20 - PAGE_SHIFT; 2395 numentries <<= 20 - PAGE_SHIFT; 2396 2397 /* limit to 1 bucket per 2^scale bytes of low memory */ 2398 if (scale > PAGE_SHIFT) 2399 numentries >>= (scale - PAGE_SHIFT); 2400 else 2401 numentries <<= (PAGE_SHIFT - scale); 2402 } 2403 numentries = roundup_pow_of_two(numentries); 2404 2405 /* limit allocation size to 1/16 total memory by default */ 2406 if (max == 0) { 2407 max = ((unsigned long long)nr_all_pages << PAGE_SHIFT) >> 4; 2408 do_div(max, bucketsize); 2409 } 2410 2411 if (numentries > max) 2412 numentries = max; 2413 2414 log2qty = long_log2(numentries); 2415 2416 do { 2417 size = bucketsize << log2qty; 2418 if (flags & HASH_EARLY) 2419 table = alloc_bootmem(size); 2420 else if (hashdist) 2421 table = __vmalloc(size, GFP_ATOMIC, PAGE_KERNEL); 2422 else { 2423 unsigned long order; 2424 for (order = 0; ((1UL << order) << PAGE_SHIFT) < size; order++) 2425 ; 2426 table = (void*) __get_free_pages(GFP_ATOMIC, order); 2427 } 2428 } while (!table && size > PAGE_SIZE && --log2qty); 2429 2430 if (!table) 2431 panic("Failed to allocate %s hash table\n", tablename); 2432 2433 printk("%s hash table entries: %d (order: %d, %lu bytes)\n", 2434 tablename, 2435 (1U << log2qty), 2436 long_log2(size) - PAGE_SHIFT, 2437 size); 2438 2439 if (_hash_shift) 2440 *_hash_shift = log2qty; 2441 if (_hash_mask) 2442 *_hash_mask = (1 << log2qty) - 1; 2443 2444 return table; 2445} 2446 2447#ifdef CONFIG_OUT_OF_LINE_PFN_TO_PAGE 2448struct page *pfn_to_page(unsigned long pfn) 2449{ 2450 return __pfn_to_page(pfn); 2451} 2452unsigned long page_to_pfn(struct page *page) 2453{ 2454 return __page_to_pfn(page); 2455} 2456EXPORT_SYMBOL(pfn_to_page); 2457EXPORT_SYMBOL(page_to_pfn); 2458#endif /* CONFIG_OUT_OF_LINE_PFN_TO_PAGE */ 2459