page_alloc.c revision 72280ede316911fd5a82ef78d12a6705b1007d36
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#include <linux/sort.h> 41#include <linux/pfn.h> 42#include <linux/backing-dev.h> 43#include <linux/fault-inject.h> 44 45#include <asm/tlbflush.h> 46#include <asm/div64.h> 47#include "internal.h" 48 49/* 50 * MCD - HACK: Find somewhere to initialize this EARLY, or make this 51 * initializer cleaner 52 */ 53nodemask_t node_online_map __read_mostly = { { [0] = 1UL } }; 54EXPORT_SYMBOL(node_online_map); 55nodemask_t node_possible_map __read_mostly = NODE_MASK_ALL; 56EXPORT_SYMBOL(node_possible_map); 57unsigned long totalram_pages __read_mostly; 58unsigned long totalreserve_pages __read_mostly; 59long nr_swap_pages; 60int percpu_pagelist_fraction; 61 62static void __free_pages_ok(struct page *page, unsigned int order); 63 64/* 65 * results with 256, 32 in the lowmem_reserve sysctl: 66 * 1G machine -> (16M dma, 800M-16M normal, 1G-800M high) 67 * 1G machine -> (16M dma, 784M normal, 224M high) 68 * NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA 69 * HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL 70 * HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA 71 * 72 * TBD: should special case ZONE_DMA32 machines here - in those we normally 73 * don't need any ZONE_NORMAL reservation 74 */ 75int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = { 76#ifdef CONFIG_ZONE_DMA 77 256, 78#endif 79#ifdef CONFIG_ZONE_DMA32 80 256, 81#endif 82#ifdef CONFIG_HIGHMEM 83 32 84#endif 85}; 86 87EXPORT_SYMBOL(totalram_pages); 88 89static char * const zone_names[MAX_NR_ZONES] = { 90#ifdef CONFIG_ZONE_DMA 91 "DMA", 92#endif 93#ifdef CONFIG_ZONE_DMA32 94 "DMA32", 95#endif 96 "Normal", 97#ifdef CONFIG_HIGHMEM 98 "HighMem" 99#endif 100}; 101 102int min_free_kbytes = 1024; 103 104unsigned long __meminitdata nr_kernel_pages; 105unsigned long __meminitdata nr_all_pages; 106static unsigned long __meminitdata dma_reserve; 107 108#ifdef CONFIG_ARCH_POPULATES_NODE_MAP 109 /* 110 * MAX_ACTIVE_REGIONS determines the maxmimum number of distinct 111 * ranges of memory (RAM) that may be registered with add_active_range(). 112 * Ranges passed to add_active_range() will be merged if possible 113 * so the number of times add_active_range() can be called is 114 * related to the number of nodes and the number of holes 115 */ 116 #ifdef CONFIG_MAX_ACTIVE_REGIONS 117 /* Allow an architecture to set MAX_ACTIVE_REGIONS to save memory */ 118 #define MAX_ACTIVE_REGIONS CONFIG_MAX_ACTIVE_REGIONS 119 #else 120 #if MAX_NUMNODES >= 32 121 /* If there can be many nodes, allow up to 50 holes per node */ 122 #define MAX_ACTIVE_REGIONS (MAX_NUMNODES*50) 123 #else 124 /* By default, allow up to 256 distinct regions */ 125 #define MAX_ACTIVE_REGIONS 256 126 #endif 127 #endif 128 129 struct node_active_region __meminitdata early_node_map[MAX_ACTIVE_REGIONS]; 130 int __meminitdata nr_nodemap_entries; 131 unsigned long __meminitdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES]; 132 unsigned long __meminitdata arch_zone_highest_possible_pfn[MAX_NR_ZONES]; 133#ifdef CONFIG_MEMORY_HOTPLUG_RESERVE 134 unsigned long __initdata node_boundary_start_pfn[MAX_NUMNODES]; 135 unsigned long __initdata node_boundary_end_pfn[MAX_NUMNODES]; 136#endif /* CONFIG_MEMORY_HOTPLUG_RESERVE */ 137#endif /* CONFIG_ARCH_POPULATES_NODE_MAP */ 138 139#ifdef CONFIG_DEBUG_VM 140static int page_outside_zone_boundaries(struct zone *zone, struct page *page) 141{ 142 int ret = 0; 143 unsigned seq; 144 unsigned long pfn = page_to_pfn(page); 145 146 do { 147 seq = zone_span_seqbegin(zone); 148 if (pfn >= zone->zone_start_pfn + zone->spanned_pages) 149 ret = 1; 150 else if (pfn < zone->zone_start_pfn) 151 ret = 1; 152 } while (zone_span_seqretry(zone, seq)); 153 154 return ret; 155} 156 157static int page_is_consistent(struct zone *zone, struct page *page) 158{ 159 if (!pfn_valid_within(page_to_pfn(page))) 160 return 0; 161 if (zone != page_zone(page)) 162 return 0; 163 164 return 1; 165} 166/* 167 * Temporary debugging check for pages not lying within a given zone. 168 */ 169static int bad_range(struct zone *zone, struct page *page) 170{ 171 if (page_outside_zone_boundaries(zone, page)) 172 return 1; 173 if (!page_is_consistent(zone, page)) 174 return 1; 175 176 return 0; 177} 178#else 179static inline int bad_range(struct zone *zone, struct page *page) 180{ 181 return 0; 182} 183#endif 184 185static void bad_page(struct page *page) 186{ 187 printk(KERN_EMERG "Bad page state in process '%s'\n" 188 KERN_EMERG "page:%p flags:0x%0*lx mapping:%p mapcount:%d count:%d\n" 189 KERN_EMERG "Trying to fix it up, but a reboot is needed\n" 190 KERN_EMERG "Backtrace:\n", 191 current->comm, page, (int)(2*sizeof(unsigned long)), 192 (unsigned long)page->flags, page->mapping, 193 page_mapcount(page), page_count(page)); 194 dump_stack(); 195 page->flags &= ~(1 << PG_lru | 196 1 << PG_private | 197 1 << PG_locked | 198 1 << PG_active | 199 1 << PG_dirty | 200 1 << PG_reclaim | 201 1 << PG_slab | 202 1 << PG_swapcache | 203 1 << PG_writeback | 204 1 << PG_buddy ); 205 set_page_count(page, 0); 206 reset_page_mapcount(page); 207 page->mapping = NULL; 208 add_taint(TAINT_BAD_PAGE); 209} 210 211/* 212 * Higher-order pages are called "compound pages". They are structured thusly: 213 * 214 * The first PAGE_SIZE page is called the "head page". 215 * 216 * The remaining PAGE_SIZE pages are called "tail pages". 217 * 218 * All pages have PG_compound set. All pages have their ->private pointing at 219 * the head page (even the head page has this). 220 * 221 * The first tail page's ->lru.next holds the address of the compound page's 222 * put_page() function. Its ->lru.prev holds the order of allocation. 223 * This usage means that zero-order pages may not be compound. 224 */ 225 226static void free_compound_page(struct page *page) 227{ 228 __free_pages_ok(page, compound_order(page)); 229} 230 231static void prep_compound_page(struct page *page, unsigned long order) 232{ 233 int i; 234 int nr_pages = 1 << order; 235 236 set_compound_page_dtor(page, free_compound_page); 237 set_compound_order(page, order); 238 __SetPageHead(page); 239 for (i = 1; i < nr_pages; i++) { 240 struct page *p = page + i; 241 242 __SetPageTail(p); 243 p->first_page = page; 244 } 245} 246 247static void destroy_compound_page(struct page *page, unsigned long order) 248{ 249 int i; 250 int nr_pages = 1 << order; 251 252 if (unlikely(compound_order(page) != order)) 253 bad_page(page); 254 255 if (unlikely(!PageHead(page))) 256 bad_page(page); 257 __ClearPageHead(page); 258 for (i = 1; i < nr_pages; i++) { 259 struct page *p = page + i; 260 261 if (unlikely(!PageTail(p) | 262 (p->first_page != page))) 263 bad_page(page); 264 __ClearPageTail(p); 265 } 266} 267 268static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags) 269{ 270 int i; 271 272 VM_BUG_ON((gfp_flags & (__GFP_WAIT | __GFP_HIGHMEM)) == __GFP_HIGHMEM); 273 /* 274 * clear_highpage() will use KM_USER0, so it's a bug to use __GFP_ZERO 275 * and __GFP_HIGHMEM from hard or soft interrupt context. 276 */ 277 VM_BUG_ON((gfp_flags & __GFP_HIGHMEM) && in_interrupt()); 278 for (i = 0; i < (1 << order); i++) 279 clear_highpage(page + i); 280} 281 282/* 283 * function for dealing with page's order in buddy system. 284 * zone->lock is already acquired when we use these. 285 * So, we don't need atomic page->flags operations here. 286 */ 287static inline unsigned long page_order(struct page *page) 288{ 289 return page_private(page); 290} 291 292static inline void set_page_order(struct page *page, int order) 293{ 294 set_page_private(page, order); 295 __SetPageBuddy(page); 296} 297 298static inline void rmv_page_order(struct page *page) 299{ 300 __ClearPageBuddy(page); 301 set_page_private(page, 0); 302} 303 304/* 305 * Locate the struct page for both the matching buddy in our 306 * pair (buddy1) and the combined O(n+1) page they form (page). 307 * 308 * 1) Any buddy B1 will have an order O twin B2 which satisfies 309 * the following equation: 310 * B2 = B1 ^ (1 << O) 311 * For example, if the starting buddy (buddy2) is #8 its order 312 * 1 buddy is #10: 313 * B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10 314 * 315 * 2) Any buddy B will have an order O+1 parent P which 316 * satisfies the following equation: 317 * P = B & ~(1 << O) 318 * 319 * Assumption: *_mem_map is contiguous at least up to MAX_ORDER 320 */ 321static inline struct page * 322__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order) 323{ 324 unsigned long buddy_idx = page_idx ^ (1 << order); 325 326 return page + (buddy_idx - page_idx); 327} 328 329static inline unsigned long 330__find_combined_index(unsigned long page_idx, unsigned int order) 331{ 332 return (page_idx & ~(1 << order)); 333} 334 335/* 336 * This function checks whether a page is free && is the buddy 337 * we can do coalesce a page and its buddy if 338 * (a) the buddy is not in a hole && 339 * (b) the buddy is in the buddy system && 340 * (c) a page and its buddy have the same order && 341 * (d) a page and its buddy are in the same zone. 342 * 343 * For recording whether a page is in the buddy system, we use PG_buddy. 344 * Setting, clearing, and testing PG_buddy is serialized by zone->lock. 345 * 346 * For recording page's order, we use page_private(page). 347 */ 348static inline int page_is_buddy(struct page *page, struct page *buddy, 349 int order) 350{ 351 if (!pfn_valid_within(page_to_pfn(buddy))) 352 return 0; 353 354 if (page_zone_id(page) != page_zone_id(buddy)) 355 return 0; 356 357 if (PageBuddy(buddy) && page_order(buddy) == order) { 358 BUG_ON(page_count(buddy) != 0); 359 return 1; 360 } 361 return 0; 362} 363 364/* 365 * Freeing function for a buddy system allocator. 366 * 367 * The concept of a buddy system is to maintain direct-mapped table 368 * (containing bit values) for memory blocks of various "orders". 369 * The bottom level table contains the map for the smallest allocatable 370 * units of memory (here, pages), and each level above it describes 371 * pairs of units from the levels below, hence, "buddies". 372 * At a high level, all that happens here is marking the table entry 373 * at the bottom level available, and propagating the changes upward 374 * as necessary, plus some accounting needed to play nicely with other 375 * parts of the VM system. 376 * At each level, we keep a list of pages, which are heads of continuous 377 * free pages of length of (1 << order) and marked with PG_buddy. Page's 378 * order is recorded in page_private(page) field. 379 * So when we are allocating or freeing one, we can derive the state of the 380 * other. That is, if we allocate a small block, and both were 381 * free, the remainder of the region must be split into blocks. 382 * If a block is freed, and its buddy is also free, then this 383 * triggers coalescing into a block of larger size. 384 * 385 * -- wli 386 */ 387 388static inline void __free_one_page(struct page *page, 389 struct zone *zone, unsigned int order) 390{ 391 unsigned long page_idx; 392 int order_size = 1 << order; 393 394 if (unlikely(PageCompound(page))) 395 destroy_compound_page(page, order); 396 397 page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1); 398 399 VM_BUG_ON(page_idx & (order_size - 1)); 400 VM_BUG_ON(bad_range(zone, page)); 401 402 __mod_zone_page_state(zone, NR_FREE_PAGES, order_size); 403 while (order < MAX_ORDER-1) { 404 unsigned long combined_idx; 405 struct free_area *area; 406 struct page *buddy; 407 408 buddy = __page_find_buddy(page, page_idx, order); 409 if (!page_is_buddy(page, buddy, order)) 410 break; /* Move the buddy up one level. */ 411 412 list_del(&buddy->lru); 413 area = zone->free_area + order; 414 area->nr_free--; 415 rmv_page_order(buddy); 416 combined_idx = __find_combined_index(page_idx, order); 417 page = page + (combined_idx - page_idx); 418 page_idx = combined_idx; 419 order++; 420 } 421 set_page_order(page, order); 422 list_add(&page->lru, &zone->free_area[order].free_list); 423 zone->free_area[order].nr_free++; 424} 425 426static inline int free_pages_check(struct page *page) 427{ 428 if (unlikely(page_mapcount(page) | 429 (page->mapping != NULL) | 430 (page_count(page) != 0) | 431 (page->flags & ( 432 1 << PG_lru | 433 1 << PG_private | 434 1 << PG_locked | 435 1 << PG_active | 436 1 << PG_slab | 437 1 << PG_swapcache | 438 1 << PG_writeback | 439 1 << PG_reserved | 440 1 << PG_buddy )))) 441 bad_page(page); 442 /* 443 * PageReclaim == PageTail. It is only an error 444 * for PageReclaim to be set if PageCompound is clear. 445 */ 446 if (unlikely(!PageCompound(page) && PageReclaim(page))) 447 bad_page(page); 448 if (PageDirty(page)) 449 __ClearPageDirty(page); 450 /* 451 * For now, we report if PG_reserved was found set, but do not 452 * clear it, and do not free the page. But we shall soon need 453 * to do more, for when the ZERO_PAGE count wraps negative. 454 */ 455 return PageReserved(page); 456} 457 458/* 459 * Frees a list of pages. 460 * Assumes all pages on list are in same zone, and of same order. 461 * count is the number of pages to free. 462 * 463 * If the zone was previously in an "all pages pinned" state then look to 464 * see if this freeing clears that state. 465 * 466 * And clear the zone's pages_scanned counter, to hold off the "all pages are 467 * pinned" detection logic. 468 */ 469static void free_pages_bulk(struct zone *zone, int count, 470 struct list_head *list, int order) 471{ 472 spin_lock(&zone->lock); 473 zone->all_unreclaimable = 0; 474 zone->pages_scanned = 0; 475 while (count--) { 476 struct page *page; 477 478 VM_BUG_ON(list_empty(list)); 479 page = list_entry(list->prev, struct page, lru); 480 /* have to delete it as __free_one_page list manipulates */ 481 list_del(&page->lru); 482 __free_one_page(page, zone, order); 483 } 484 spin_unlock(&zone->lock); 485} 486 487static void free_one_page(struct zone *zone, struct page *page, int order) 488{ 489 spin_lock(&zone->lock); 490 zone->all_unreclaimable = 0; 491 zone->pages_scanned = 0; 492 __free_one_page(page, zone, order); 493 spin_unlock(&zone->lock); 494} 495 496static void __free_pages_ok(struct page *page, unsigned int order) 497{ 498 unsigned long flags; 499 int i; 500 int reserved = 0; 501 502 for (i = 0 ; i < (1 << order) ; ++i) 503 reserved += free_pages_check(page + i); 504 if (reserved) 505 return; 506 507 if (!PageHighMem(page)) 508 debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order); 509 arch_free_page(page, order); 510 kernel_map_pages(page, 1 << order, 0); 511 512 local_irq_save(flags); 513 __count_vm_events(PGFREE, 1 << order); 514 free_one_page(page_zone(page), page, order); 515 local_irq_restore(flags); 516} 517 518/* 519 * permit the bootmem allocator to evade page validation on high-order frees 520 */ 521void fastcall __init __free_pages_bootmem(struct page *page, unsigned int order) 522{ 523 if (order == 0) { 524 __ClearPageReserved(page); 525 set_page_count(page, 0); 526 set_page_refcounted(page); 527 __free_page(page); 528 } else { 529 int loop; 530 531 prefetchw(page); 532 for (loop = 0; loop < BITS_PER_LONG; loop++) { 533 struct page *p = &page[loop]; 534 535 if (loop + 1 < BITS_PER_LONG) 536 prefetchw(p + 1); 537 __ClearPageReserved(p); 538 set_page_count(p, 0); 539 } 540 541 set_page_refcounted(page); 542 __free_pages(page, order); 543 } 544} 545 546 547/* 548 * The order of subdivision here is critical for the IO subsystem. 549 * Please do not alter this order without good reasons and regression 550 * testing. Specifically, as large blocks of memory are subdivided, 551 * the order in which smaller blocks are delivered depends on the order 552 * they're subdivided in this function. This is the primary factor 553 * influencing the order in which pages are delivered to the IO 554 * subsystem according to empirical testing, and this is also justified 555 * by considering the behavior of a buddy system containing a single 556 * large block of memory acted on by a series of small allocations. 557 * This behavior is a critical factor in sglist merging's success. 558 * 559 * -- wli 560 */ 561static inline void expand(struct zone *zone, struct page *page, 562 int low, int high, struct free_area *area) 563{ 564 unsigned long size = 1 << high; 565 566 while (high > low) { 567 area--; 568 high--; 569 size >>= 1; 570 VM_BUG_ON(bad_range(zone, &page[size])); 571 list_add(&page[size].lru, &area->free_list); 572 area->nr_free++; 573 set_page_order(&page[size], high); 574 } 575} 576 577/* 578 * This page is about to be returned from the page allocator 579 */ 580static int prep_new_page(struct page *page, int order, gfp_t gfp_flags) 581{ 582 if (unlikely(page_mapcount(page) | 583 (page->mapping != NULL) | 584 (page_count(page) != 0) | 585 (page->flags & ( 586 1 << PG_lru | 587 1 << PG_private | 588 1 << PG_locked | 589 1 << PG_active | 590 1 << PG_dirty | 591 1 << PG_reclaim | 592 1 << PG_slab | 593 1 << PG_swapcache | 594 1 << PG_writeback | 595 1 << PG_reserved | 596 1 << PG_buddy )))) 597 bad_page(page); 598 599 /* 600 * For now, we report if PG_reserved was found set, but do not 601 * clear it, and do not allocate the page: as a safety net. 602 */ 603 if (PageReserved(page)) 604 return 1; 605 606 page->flags &= ~(1 << PG_uptodate | 1 << PG_error | 607 1 << PG_referenced | 1 << PG_arch_1 | 608 1 << PG_owner_priv_1 | 1 << PG_mappedtodisk); 609 set_page_private(page, 0); 610 set_page_refcounted(page); 611 612 arch_alloc_page(page, order); 613 kernel_map_pages(page, 1 << order, 1); 614 615 if (gfp_flags & __GFP_ZERO) 616 prep_zero_page(page, order, gfp_flags); 617 618 if (order && (gfp_flags & __GFP_COMP)) 619 prep_compound_page(page, order); 620 621 return 0; 622} 623 624/* 625 * Do the hard work of removing an element from the buddy allocator. 626 * Call me with the zone->lock already held. 627 */ 628static struct page *__rmqueue(struct zone *zone, unsigned int order) 629{ 630 struct free_area * area; 631 unsigned int current_order; 632 struct page *page; 633 634 for (current_order = order; current_order < MAX_ORDER; ++current_order) { 635 area = zone->free_area + current_order; 636 if (list_empty(&area->free_list)) 637 continue; 638 639 page = list_entry(area->free_list.next, struct page, lru); 640 list_del(&page->lru); 641 rmv_page_order(page); 642 area->nr_free--; 643 __mod_zone_page_state(zone, NR_FREE_PAGES, - (1UL << order)); 644 expand(zone, page, order, current_order, area); 645 return page; 646 } 647 648 return NULL; 649} 650 651/* 652 * Obtain a specified number of elements from the buddy allocator, all under 653 * a single hold of the lock, for efficiency. Add them to the supplied list. 654 * Returns the number of new pages which were placed at *list. 655 */ 656static int rmqueue_bulk(struct zone *zone, unsigned int order, 657 unsigned long count, struct list_head *list) 658{ 659 int i; 660 661 spin_lock(&zone->lock); 662 for (i = 0; i < count; ++i) { 663 struct page *page = __rmqueue(zone, order); 664 if (unlikely(page == NULL)) 665 break; 666 list_add_tail(&page->lru, list); 667 } 668 spin_unlock(&zone->lock); 669 return i; 670} 671 672#if MAX_NUMNODES > 1 673int nr_node_ids __read_mostly = MAX_NUMNODES; 674EXPORT_SYMBOL(nr_node_ids); 675 676/* 677 * Figure out the number of possible node ids. 678 */ 679static void __init setup_nr_node_ids(void) 680{ 681 unsigned int node; 682 unsigned int highest = 0; 683 684 for_each_node_mask(node, node_possible_map) 685 highest = node; 686 nr_node_ids = highest + 1; 687} 688#else 689static void __init setup_nr_node_ids(void) {} 690#endif 691 692#ifdef CONFIG_NUMA 693/* 694 * Called from the slab reaper to drain pagesets on a particular node that 695 * belongs to the currently executing processor. 696 * Note that this function must be called with the thread pinned to 697 * a single processor. 698 */ 699void drain_node_pages(int nodeid) 700{ 701 int i; 702 enum zone_type z; 703 unsigned long flags; 704 705 for (z = 0; z < MAX_NR_ZONES; z++) { 706 struct zone *zone = NODE_DATA(nodeid)->node_zones + z; 707 struct per_cpu_pageset *pset; 708 709 if (!populated_zone(zone)) 710 continue; 711 712 pset = zone_pcp(zone, smp_processor_id()); 713 for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) { 714 struct per_cpu_pages *pcp; 715 716 pcp = &pset->pcp[i]; 717 if (pcp->count) { 718 int to_drain; 719 720 local_irq_save(flags); 721 if (pcp->count >= pcp->batch) 722 to_drain = pcp->batch; 723 else 724 to_drain = pcp->count; 725 free_pages_bulk(zone, to_drain, &pcp->list, 0); 726 pcp->count -= to_drain; 727 local_irq_restore(flags); 728 } 729 } 730 } 731} 732#endif 733 734static void __drain_pages(unsigned int cpu) 735{ 736 unsigned long flags; 737 struct zone *zone; 738 int i; 739 740 for_each_zone(zone) { 741 struct per_cpu_pageset *pset; 742 743 if (!populated_zone(zone)) 744 continue; 745 746 pset = zone_pcp(zone, cpu); 747 for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) { 748 struct per_cpu_pages *pcp; 749 750 pcp = &pset->pcp[i]; 751 local_irq_save(flags); 752 free_pages_bulk(zone, pcp->count, &pcp->list, 0); 753 pcp->count = 0; 754 local_irq_restore(flags); 755 } 756 } 757} 758 759#ifdef CONFIG_PM 760 761void mark_free_pages(struct zone *zone) 762{ 763 unsigned long pfn, max_zone_pfn; 764 unsigned long flags; 765 int order; 766 struct list_head *curr; 767 768 if (!zone->spanned_pages) 769 return; 770 771 spin_lock_irqsave(&zone->lock, flags); 772 773 max_zone_pfn = zone->zone_start_pfn + zone->spanned_pages; 774 for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++) 775 if (pfn_valid(pfn)) { 776 struct page *page = pfn_to_page(pfn); 777 778 if (!swsusp_page_is_forbidden(page)) 779 swsusp_unset_page_free(page); 780 } 781 782 for (order = MAX_ORDER - 1; order >= 0; --order) 783 list_for_each(curr, &zone->free_area[order].free_list) { 784 unsigned long i; 785 786 pfn = page_to_pfn(list_entry(curr, struct page, lru)); 787 for (i = 0; i < (1UL << order); i++) 788 swsusp_set_page_free(pfn_to_page(pfn + i)); 789 } 790 791 spin_unlock_irqrestore(&zone->lock, flags); 792} 793 794/* 795 * Spill all of this CPU's per-cpu pages back into the buddy allocator. 796 */ 797void drain_local_pages(void) 798{ 799 unsigned long flags; 800 801 local_irq_save(flags); 802 __drain_pages(smp_processor_id()); 803 local_irq_restore(flags); 804} 805#endif /* CONFIG_PM */ 806 807/* 808 * Free a 0-order page 809 */ 810static void fastcall free_hot_cold_page(struct page *page, int cold) 811{ 812 struct zone *zone = page_zone(page); 813 struct per_cpu_pages *pcp; 814 unsigned long flags; 815 816 if (PageAnon(page)) 817 page->mapping = NULL; 818 if (free_pages_check(page)) 819 return; 820 821 if (!PageHighMem(page)) 822 debug_check_no_locks_freed(page_address(page), PAGE_SIZE); 823 arch_free_page(page, 0); 824 kernel_map_pages(page, 1, 0); 825 826 pcp = &zone_pcp(zone, get_cpu())->pcp[cold]; 827 local_irq_save(flags); 828 __count_vm_event(PGFREE); 829 list_add(&page->lru, &pcp->list); 830 pcp->count++; 831 if (pcp->count >= pcp->high) { 832 free_pages_bulk(zone, pcp->batch, &pcp->list, 0); 833 pcp->count -= pcp->batch; 834 } 835 local_irq_restore(flags); 836 put_cpu(); 837} 838 839void fastcall free_hot_page(struct page *page) 840{ 841 free_hot_cold_page(page, 0); 842} 843 844void fastcall free_cold_page(struct page *page) 845{ 846 free_hot_cold_page(page, 1); 847} 848 849/* 850 * split_page takes a non-compound higher-order page, and splits it into 851 * n (1<<order) sub-pages: page[0..n] 852 * Each sub-page must be freed individually. 853 * 854 * Note: this is probably too low level an operation for use in drivers. 855 * Please consult with lkml before using this in your driver. 856 */ 857void split_page(struct page *page, unsigned int order) 858{ 859 int i; 860 861 VM_BUG_ON(PageCompound(page)); 862 VM_BUG_ON(!page_count(page)); 863 for (i = 1; i < (1 << order); i++) 864 set_page_refcounted(page + i); 865} 866 867/* 868 * Really, prep_compound_page() should be called from __rmqueue_bulk(). But 869 * we cheat by calling it from here, in the order > 0 path. Saves a branch 870 * or two. 871 */ 872static struct page *buffered_rmqueue(struct zonelist *zonelist, 873 struct zone *zone, int order, gfp_t gfp_flags) 874{ 875 unsigned long flags; 876 struct page *page; 877 int cold = !!(gfp_flags & __GFP_COLD); 878 int cpu; 879 880again: 881 cpu = get_cpu(); 882 if (likely(order == 0)) { 883 struct per_cpu_pages *pcp; 884 885 pcp = &zone_pcp(zone, cpu)->pcp[cold]; 886 local_irq_save(flags); 887 if (!pcp->count) { 888 pcp->count = rmqueue_bulk(zone, 0, 889 pcp->batch, &pcp->list); 890 if (unlikely(!pcp->count)) 891 goto failed; 892 } 893 page = list_entry(pcp->list.next, struct page, lru); 894 list_del(&page->lru); 895 pcp->count--; 896 } else { 897 spin_lock_irqsave(&zone->lock, flags); 898 page = __rmqueue(zone, order); 899 spin_unlock(&zone->lock); 900 if (!page) 901 goto failed; 902 } 903 904 __count_zone_vm_events(PGALLOC, zone, 1 << order); 905 zone_statistics(zonelist, zone); 906 local_irq_restore(flags); 907 put_cpu(); 908 909 VM_BUG_ON(bad_range(zone, page)); 910 if (prep_new_page(page, order, gfp_flags)) 911 goto again; 912 return page; 913 914failed: 915 local_irq_restore(flags); 916 put_cpu(); 917 return NULL; 918} 919 920#define ALLOC_NO_WATERMARKS 0x01 /* don't check watermarks at all */ 921#define ALLOC_WMARK_MIN 0x02 /* use pages_min watermark */ 922#define ALLOC_WMARK_LOW 0x04 /* use pages_low watermark */ 923#define ALLOC_WMARK_HIGH 0x08 /* use pages_high watermark */ 924#define ALLOC_HARDER 0x10 /* try to alloc harder */ 925#define ALLOC_HIGH 0x20 /* __GFP_HIGH set */ 926#define ALLOC_CPUSET 0x40 /* check for correct cpuset */ 927 928#ifdef CONFIG_FAIL_PAGE_ALLOC 929 930static struct fail_page_alloc_attr { 931 struct fault_attr attr; 932 933 u32 ignore_gfp_highmem; 934 u32 ignore_gfp_wait; 935 936#ifdef CONFIG_FAULT_INJECTION_DEBUG_FS 937 938 struct dentry *ignore_gfp_highmem_file; 939 struct dentry *ignore_gfp_wait_file; 940 941#endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */ 942 943} fail_page_alloc = { 944 .attr = FAULT_ATTR_INITIALIZER, 945 .ignore_gfp_wait = 1, 946 .ignore_gfp_highmem = 1, 947}; 948 949static int __init setup_fail_page_alloc(char *str) 950{ 951 return setup_fault_attr(&fail_page_alloc.attr, str); 952} 953__setup("fail_page_alloc=", setup_fail_page_alloc); 954 955static int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order) 956{ 957 if (gfp_mask & __GFP_NOFAIL) 958 return 0; 959 if (fail_page_alloc.ignore_gfp_highmem && (gfp_mask & __GFP_HIGHMEM)) 960 return 0; 961 if (fail_page_alloc.ignore_gfp_wait && (gfp_mask & __GFP_WAIT)) 962 return 0; 963 964 return should_fail(&fail_page_alloc.attr, 1 << order); 965} 966 967#ifdef CONFIG_FAULT_INJECTION_DEBUG_FS 968 969static int __init fail_page_alloc_debugfs(void) 970{ 971 mode_t mode = S_IFREG | S_IRUSR | S_IWUSR; 972 struct dentry *dir; 973 int err; 974 975 err = init_fault_attr_dentries(&fail_page_alloc.attr, 976 "fail_page_alloc"); 977 if (err) 978 return err; 979 dir = fail_page_alloc.attr.dentries.dir; 980 981 fail_page_alloc.ignore_gfp_wait_file = 982 debugfs_create_bool("ignore-gfp-wait", mode, dir, 983 &fail_page_alloc.ignore_gfp_wait); 984 985 fail_page_alloc.ignore_gfp_highmem_file = 986 debugfs_create_bool("ignore-gfp-highmem", mode, dir, 987 &fail_page_alloc.ignore_gfp_highmem); 988 989 if (!fail_page_alloc.ignore_gfp_wait_file || 990 !fail_page_alloc.ignore_gfp_highmem_file) { 991 err = -ENOMEM; 992 debugfs_remove(fail_page_alloc.ignore_gfp_wait_file); 993 debugfs_remove(fail_page_alloc.ignore_gfp_highmem_file); 994 cleanup_fault_attr_dentries(&fail_page_alloc.attr); 995 } 996 997 return err; 998} 999 1000late_initcall(fail_page_alloc_debugfs); 1001 1002#endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */ 1003 1004#else /* CONFIG_FAIL_PAGE_ALLOC */ 1005 1006static inline int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order) 1007{ 1008 return 0; 1009} 1010 1011#endif /* CONFIG_FAIL_PAGE_ALLOC */ 1012 1013/* 1014 * Return 1 if free pages are above 'mark'. This takes into account the order 1015 * of the allocation. 1016 */ 1017int zone_watermark_ok(struct zone *z, int order, unsigned long mark, 1018 int classzone_idx, int alloc_flags) 1019{ 1020 /* free_pages my go negative - that's OK */ 1021 long min = mark; 1022 long free_pages = zone_page_state(z, NR_FREE_PAGES) - (1 << order) + 1; 1023 int o; 1024 1025 if (alloc_flags & ALLOC_HIGH) 1026 min -= min / 2; 1027 if (alloc_flags & ALLOC_HARDER) 1028 min -= min / 4; 1029 1030 if (free_pages <= min + z->lowmem_reserve[classzone_idx]) 1031 return 0; 1032 for (o = 0; o < order; o++) { 1033 /* At the next order, this order's pages become unavailable */ 1034 free_pages -= z->free_area[o].nr_free << o; 1035 1036 /* Require fewer higher order pages to be free */ 1037 min >>= 1; 1038 1039 if (free_pages <= min) 1040 return 0; 1041 } 1042 return 1; 1043} 1044 1045#ifdef CONFIG_NUMA 1046/* 1047 * zlc_setup - Setup for "zonelist cache". Uses cached zone data to 1048 * skip over zones that are not allowed by the cpuset, or that have 1049 * been recently (in last second) found to be nearly full. See further 1050 * comments in mmzone.h. Reduces cache footprint of zonelist scans 1051 * that have to skip over alot of full or unallowed zones. 1052 * 1053 * If the zonelist cache is present in the passed in zonelist, then 1054 * returns a pointer to the allowed node mask (either the current 1055 * tasks mems_allowed, or node_online_map.) 1056 * 1057 * If the zonelist cache is not available for this zonelist, does 1058 * nothing and returns NULL. 1059 * 1060 * If the fullzones BITMAP in the zonelist cache is stale (more than 1061 * a second since last zap'd) then we zap it out (clear its bits.) 1062 * 1063 * We hold off even calling zlc_setup, until after we've checked the 1064 * first zone in the zonelist, on the theory that most allocations will 1065 * be satisfied from that first zone, so best to examine that zone as 1066 * quickly as we can. 1067 */ 1068static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags) 1069{ 1070 struct zonelist_cache *zlc; /* cached zonelist speedup info */ 1071 nodemask_t *allowednodes; /* zonelist_cache approximation */ 1072 1073 zlc = zonelist->zlcache_ptr; 1074 if (!zlc) 1075 return NULL; 1076 1077 if (jiffies - zlc->last_full_zap > 1 * HZ) { 1078 bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST); 1079 zlc->last_full_zap = jiffies; 1080 } 1081 1082 allowednodes = !in_interrupt() && (alloc_flags & ALLOC_CPUSET) ? 1083 &cpuset_current_mems_allowed : 1084 &node_online_map; 1085 return allowednodes; 1086} 1087 1088/* 1089 * Given 'z' scanning a zonelist, run a couple of quick checks to see 1090 * if it is worth looking at further for free memory: 1091 * 1) Check that the zone isn't thought to be full (doesn't have its 1092 * bit set in the zonelist_cache fullzones BITMAP). 1093 * 2) Check that the zones node (obtained from the zonelist_cache 1094 * z_to_n[] mapping) is allowed in the passed in allowednodes mask. 1095 * Return true (non-zero) if zone is worth looking at further, or 1096 * else return false (zero) if it is not. 1097 * 1098 * This check -ignores- the distinction between various watermarks, 1099 * such as GFP_HIGH, GFP_ATOMIC, PF_MEMALLOC, ... If a zone is 1100 * found to be full for any variation of these watermarks, it will 1101 * be considered full for up to one second by all requests, unless 1102 * we are so low on memory on all allowed nodes that we are forced 1103 * into the second scan of the zonelist. 1104 * 1105 * In the second scan we ignore this zonelist cache and exactly 1106 * apply the watermarks to all zones, even it is slower to do so. 1107 * We are low on memory in the second scan, and should leave no stone 1108 * unturned looking for a free page. 1109 */ 1110static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zone **z, 1111 nodemask_t *allowednodes) 1112{ 1113 struct zonelist_cache *zlc; /* cached zonelist speedup info */ 1114 int i; /* index of *z in zonelist zones */ 1115 int n; /* node that zone *z is on */ 1116 1117 zlc = zonelist->zlcache_ptr; 1118 if (!zlc) 1119 return 1; 1120 1121 i = z - zonelist->zones; 1122 n = zlc->z_to_n[i]; 1123 1124 /* This zone is worth trying if it is allowed but not full */ 1125 return node_isset(n, *allowednodes) && !test_bit(i, zlc->fullzones); 1126} 1127 1128/* 1129 * Given 'z' scanning a zonelist, set the corresponding bit in 1130 * zlc->fullzones, so that subsequent attempts to allocate a page 1131 * from that zone don't waste time re-examining it. 1132 */ 1133static void zlc_mark_zone_full(struct zonelist *zonelist, struct zone **z) 1134{ 1135 struct zonelist_cache *zlc; /* cached zonelist speedup info */ 1136 int i; /* index of *z in zonelist zones */ 1137 1138 zlc = zonelist->zlcache_ptr; 1139 if (!zlc) 1140 return; 1141 1142 i = z - zonelist->zones; 1143 1144 set_bit(i, zlc->fullzones); 1145} 1146 1147#else /* CONFIG_NUMA */ 1148 1149static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags) 1150{ 1151 return NULL; 1152} 1153 1154static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zone **z, 1155 nodemask_t *allowednodes) 1156{ 1157 return 1; 1158} 1159 1160static void zlc_mark_zone_full(struct zonelist *zonelist, struct zone **z) 1161{ 1162} 1163#endif /* CONFIG_NUMA */ 1164 1165/* 1166 * get_page_from_freelist goes through the zonelist trying to allocate 1167 * a page. 1168 */ 1169static struct page * 1170get_page_from_freelist(gfp_t gfp_mask, unsigned int order, 1171 struct zonelist *zonelist, int alloc_flags) 1172{ 1173 struct zone **z; 1174 struct page *page = NULL; 1175 int classzone_idx = zone_idx(zonelist->zones[0]); 1176 struct zone *zone; 1177 nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */ 1178 int zlc_active = 0; /* set if using zonelist_cache */ 1179 int did_zlc_setup = 0; /* just call zlc_setup() one time */ 1180 1181zonelist_scan: 1182 /* 1183 * Scan zonelist, looking for a zone with enough free. 1184 * See also cpuset_zone_allowed() comment in kernel/cpuset.c. 1185 */ 1186 z = zonelist->zones; 1187 1188 do { 1189 if (NUMA_BUILD && zlc_active && 1190 !zlc_zone_worth_trying(zonelist, z, allowednodes)) 1191 continue; 1192 zone = *z; 1193 if (unlikely(NUMA_BUILD && (gfp_mask & __GFP_THISNODE) && 1194 zone->zone_pgdat != zonelist->zones[0]->zone_pgdat)) 1195 break; 1196 if ((alloc_flags & ALLOC_CPUSET) && 1197 !cpuset_zone_allowed_softwall(zone, gfp_mask)) 1198 goto try_next_zone; 1199 1200 if (!(alloc_flags & ALLOC_NO_WATERMARKS)) { 1201 unsigned long mark; 1202 if (alloc_flags & ALLOC_WMARK_MIN) 1203 mark = zone->pages_min; 1204 else if (alloc_flags & ALLOC_WMARK_LOW) 1205 mark = zone->pages_low; 1206 else 1207 mark = zone->pages_high; 1208 if (!zone_watermark_ok(zone, order, mark, 1209 classzone_idx, alloc_flags)) { 1210 if (!zone_reclaim_mode || 1211 !zone_reclaim(zone, gfp_mask, order)) 1212 goto this_zone_full; 1213 } 1214 } 1215 1216 page = buffered_rmqueue(zonelist, zone, order, gfp_mask); 1217 if (page) 1218 break; 1219this_zone_full: 1220 if (NUMA_BUILD) 1221 zlc_mark_zone_full(zonelist, z); 1222try_next_zone: 1223 if (NUMA_BUILD && !did_zlc_setup) { 1224 /* we do zlc_setup after the first zone is tried */ 1225 allowednodes = zlc_setup(zonelist, alloc_flags); 1226 zlc_active = 1; 1227 did_zlc_setup = 1; 1228 } 1229 } while (*(++z) != NULL); 1230 1231 if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) { 1232 /* Disable zlc cache for second zonelist scan */ 1233 zlc_active = 0; 1234 goto zonelist_scan; 1235 } 1236 return page; 1237} 1238 1239/* 1240 * This is the 'heart' of the zoned buddy allocator. 1241 */ 1242struct page * fastcall 1243__alloc_pages(gfp_t gfp_mask, unsigned int order, 1244 struct zonelist *zonelist) 1245{ 1246 const gfp_t wait = gfp_mask & __GFP_WAIT; 1247 struct zone **z; 1248 struct page *page; 1249 struct reclaim_state reclaim_state; 1250 struct task_struct *p = current; 1251 int do_retry; 1252 int alloc_flags; 1253 int did_some_progress; 1254 1255 might_sleep_if(wait); 1256 1257 if (should_fail_alloc_page(gfp_mask, order)) 1258 return NULL; 1259 1260restart: 1261 z = zonelist->zones; /* the list of zones suitable for gfp_mask */ 1262 1263 if (unlikely(*z == NULL)) { 1264 /* Should this ever happen?? */ 1265 return NULL; 1266 } 1267 1268 page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order, 1269 zonelist, ALLOC_WMARK_LOW|ALLOC_CPUSET); 1270 if (page) 1271 goto got_pg; 1272 1273 /* 1274 * GFP_THISNODE (meaning __GFP_THISNODE, __GFP_NORETRY and 1275 * __GFP_NOWARN set) should not cause reclaim since the subsystem 1276 * (f.e. slab) using GFP_THISNODE may choose to trigger reclaim 1277 * using a larger set of nodes after it has established that the 1278 * allowed per node queues are empty and that nodes are 1279 * over allocated. 1280 */ 1281 if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE) 1282 goto nopage; 1283 1284 for (z = zonelist->zones; *z; z++) 1285 wakeup_kswapd(*z, order); 1286 1287 /* 1288 * OK, we're below the kswapd watermark and have kicked background 1289 * reclaim. Now things get more complex, so set up alloc_flags according 1290 * to how we want to proceed. 1291 * 1292 * The caller may dip into page reserves a bit more if the caller 1293 * cannot run direct reclaim, or if the caller has realtime scheduling 1294 * policy or is asking for __GFP_HIGH memory. GFP_ATOMIC requests will 1295 * set both ALLOC_HARDER (!wait) and ALLOC_HIGH (__GFP_HIGH). 1296 */ 1297 alloc_flags = ALLOC_WMARK_MIN; 1298 if ((unlikely(rt_task(p)) && !in_interrupt()) || !wait) 1299 alloc_flags |= ALLOC_HARDER; 1300 if (gfp_mask & __GFP_HIGH) 1301 alloc_flags |= ALLOC_HIGH; 1302 if (wait) 1303 alloc_flags |= ALLOC_CPUSET; 1304 1305 /* 1306 * Go through the zonelist again. Let __GFP_HIGH and allocations 1307 * coming from realtime tasks go deeper into reserves. 1308 * 1309 * This is the last chance, in general, before the goto nopage. 1310 * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc. 1311 * See also cpuset_zone_allowed() comment in kernel/cpuset.c. 1312 */ 1313 page = get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags); 1314 if (page) 1315 goto got_pg; 1316 1317 /* This allocation should allow future memory freeing. */ 1318 1319rebalance: 1320 if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE))) 1321 && !in_interrupt()) { 1322 if (!(gfp_mask & __GFP_NOMEMALLOC)) { 1323nofail_alloc: 1324 /* go through the zonelist yet again, ignoring mins */ 1325 page = get_page_from_freelist(gfp_mask, order, 1326 zonelist, ALLOC_NO_WATERMARKS); 1327 if (page) 1328 goto got_pg; 1329 if (gfp_mask & __GFP_NOFAIL) { 1330 congestion_wait(WRITE, HZ/50); 1331 goto nofail_alloc; 1332 } 1333 } 1334 goto nopage; 1335 } 1336 1337 /* Atomic allocations - we can't balance anything */ 1338 if (!wait) 1339 goto nopage; 1340 1341 cond_resched(); 1342 1343 /* We now go into synchronous reclaim */ 1344 cpuset_memory_pressure_bump(); 1345 p->flags |= PF_MEMALLOC; 1346 reclaim_state.reclaimed_slab = 0; 1347 p->reclaim_state = &reclaim_state; 1348 1349 did_some_progress = try_to_free_pages(zonelist->zones, gfp_mask); 1350 1351 p->reclaim_state = NULL; 1352 p->flags &= ~PF_MEMALLOC; 1353 1354 cond_resched(); 1355 1356 if (likely(did_some_progress)) { 1357 page = get_page_from_freelist(gfp_mask, order, 1358 zonelist, alloc_flags); 1359 if (page) 1360 goto got_pg; 1361 } else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) { 1362 /* 1363 * Go through the zonelist yet one more time, keep 1364 * very high watermark here, this is only to catch 1365 * a parallel oom killing, we must fail if we're still 1366 * under heavy pressure. 1367 */ 1368 page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order, 1369 zonelist, ALLOC_WMARK_HIGH|ALLOC_CPUSET); 1370 if (page) 1371 goto got_pg; 1372 1373 out_of_memory(zonelist, gfp_mask, order); 1374 goto restart; 1375 } 1376 1377 /* 1378 * Don't let big-order allocations loop unless the caller explicitly 1379 * requests that. Wait for some write requests to complete then retry. 1380 * 1381 * In this implementation, __GFP_REPEAT means __GFP_NOFAIL for order 1382 * <= 3, but that may not be true in other implementations. 1383 */ 1384 do_retry = 0; 1385 if (!(gfp_mask & __GFP_NORETRY)) { 1386 if ((order <= 3) || (gfp_mask & __GFP_REPEAT)) 1387 do_retry = 1; 1388 if (gfp_mask & __GFP_NOFAIL) 1389 do_retry = 1; 1390 } 1391 if (do_retry) { 1392 congestion_wait(WRITE, HZ/50); 1393 goto rebalance; 1394 } 1395 1396nopage: 1397 if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) { 1398 printk(KERN_WARNING "%s: page allocation failure." 1399 " order:%d, mode:0x%x\n", 1400 p->comm, order, gfp_mask); 1401 dump_stack(); 1402 show_mem(); 1403 } 1404got_pg: 1405 return page; 1406} 1407 1408EXPORT_SYMBOL(__alloc_pages); 1409 1410/* 1411 * Common helper functions. 1412 */ 1413fastcall unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order) 1414{ 1415 struct page * page; 1416 page = alloc_pages(gfp_mask, order); 1417 if (!page) 1418 return 0; 1419 return (unsigned long) page_address(page); 1420} 1421 1422EXPORT_SYMBOL(__get_free_pages); 1423 1424fastcall unsigned long get_zeroed_page(gfp_t gfp_mask) 1425{ 1426 struct page * page; 1427 1428 /* 1429 * get_zeroed_page() returns a 32-bit address, which cannot represent 1430 * a highmem page 1431 */ 1432 VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0); 1433 1434 page = alloc_pages(gfp_mask | __GFP_ZERO, 0); 1435 if (page) 1436 return (unsigned long) page_address(page); 1437 return 0; 1438} 1439 1440EXPORT_SYMBOL(get_zeroed_page); 1441 1442void __pagevec_free(struct pagevec *pvec) 1443{ 1444 int i = pagevec_count(pvec); 1445 1446 while (--i >= 0) 1447 free_hot_cold_page(pvec->pages[i], pvec->cold); 1448} 1449 1450fastcall void __free_pages(struct page *page, unsigned int order) 1451{ 1452 if (put_page_testzero(page)) { 1453 if (order == 0) 1454 free_hot_page(page); 1455 else 1456 __free_pages_ok(page, order); 1457 } 1458} 1459 1460EXPORT_SYMBOL(__free_pages); 1461 1462fastcall void free_pages(unsigned long addr, unsigned int order) 1463{ 1464 if (addr != 0) { 1465 VM_BUG_ON(!virt_addr_valid((void *)addr)); 1466 __free_pages(virt_to_page((void *)addr), order); 1467 } 1468} 1469 1470EXPORT_SYMBOL(free_pages); 1471 1472static unsigned int nr_free_zone_pages(int offset) 1473{ 1474 /* Just pick one node, since fallback list is circular */ 1475 pg_data_t *pgdat = NODE_DATA(numa_node_id()); 1476 unsigned int sum = 0; 1477 1478 struct zonelist *zonelist = pgdat->node_zonelists + offset; 1479 struct zone **zonep = zonelist->zones; 1480 struct zone *zone; 1481 1482 for (zone = *zonep++; zone; zone = *zonep++) { 1483 unsigned long size = zone->present_pages; 1484 unsigned long high = zone->pages_high; 1485 if (size > high) 1486 sum += size - high; 1487 } 1488 1489 return sum; 1490} 1491 1492/* 1493 * Amount of free RAM allocatable within ZONE_DMA and ZONE_NORMAL 1494 */ 1495unsigned int nr_free_buffer_pages(void) 1496{ 1497 return nr_free_zone_pages(gfp_zone(GFP_USER)); 1498} 1499 1500/* 1501 * Amount of free RAM allocatable within all zones 1502 */ 1503unsigned int nr_free_pagecache_pages(void) 1504{ 1505 return nr_free_zone_pages(gfp_zone(GFP_HIGHUSER)); 1506} 1507 1508static inline void show_node(struct zone *zone) 1509{ 1510 if (NUMA_BUILD) 1511 printk("Node %d ", zone_to_nid(zone)); 1512} 1513 1514void si_meminfo(struct sysinfo *val) 1515{ 1516 val->totalram = totalram_pages; 1517 val->sharedram = 0; 1518 val->freeram = global_page_state(NR_FREE_PAGES); 1519 val->bufferram = nr_blockdev_pages(); 1520 val->totalhigh = totalhigh_pages; 1521 val->freehigh = nr_free_highpages(); 1522 val->mem_unit = PAGE_SIZE; 1523} 1524 1525EXPORT_SYMBOL(si_meminfo); 1526 1527#ifdef CONFIG_NUMA 1528void si_meminfo_node(struct sysinfo *val, int nid) 1529{ 1530 pg_data_t *pgdat = NODE_DATA(nid); 1531 1532 val->totalram = pgdat->node_present_pages; 1533 val->freeram = node_page_state(nid, NR_FREE_PAGES); 1534#ifdef CONFIG_HIGHMEM 1535 val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages; 1536 val->freehigh = zone_page_state(&pgdat->node_zones[ZONE_HIGHMEM], 1537 NR_FREE_PAGES); 1538#else 1539 val->totalhigh = 0; 1540 val->freehigh = 0; 1541#endif 1542 val->mem_unit = PAGE_SIZE; 1543} 1544#endif 1545 1546#define K(x) ((x) << (PAGE_SHIFT-10)) 1547 1548/* 1549 * Show free area list (used inside shift_scroll-lock stuff) 1550 * We also calculate the percentage fragmentation. We do this by counting the 1551 * memory on each free list with the exception of the first item on the list. 1552 */ 1553void show_free_areas(void) 1554{ 1555 int cpu; 1556 struct zone *zone; 1557 1558 for_each_zone(zone) { 1559 if (!populated_zone(zone)) 1560 continue; 1561 1562 show_node(zone); 1563 printk("%s per-cpu:\n", zone->name); 1564 1565 for_each_online_cpu(cpu) { 1566 struct per_cpu_pageset *pageset; 1567 1568 pageset = zone_pcp(zone, cpu); 1569 1570 printk("CPU %4d: Hot: hi:%5d, btch:%4d usd:%4d " 1571 "Cold: hi:%5d, btch:%4d usd:%4d\n", 1572 cpu, pageset->pcp[0].high, 1573 pageset->pcp[0].batch, pageset->pcp[0].count, 1574 pageset->pcp[1].high, pageset->pcp[1].batch, 1575 pageset->pcp[1].count); 1576 } 1577 } 1578 1579 printk("Active:%lu inactive:%lu dirty:%lu writeback:%lu unstable:%lu\n" 1580 " free:%lu slab:%lu mapped:%lu pagetables:%lu bounce:%lu\n", 1581 global_page_state(NR_ACTIVE), 1582 global_page_state(NR_INACTIVE), 1583 global_page_state(NR_FILE_DIRTY), 1584 global_page_state(NR_WRITEBACK), 1585 global_page_state(NR_UNSTABLE_NFS), 1586 global_page_state(NR_FREE_PAGES), 1587 global_page_state(NR_SLAB_RECLAIMABLE) + 1588 global_page_state(NR_SLAB_UNRECLAIMABLE), 1589 global_page_state(NR_FILE_MAPPED), 1590 global_page_state(NR_PAGETABLE), 1591 global_page_state(NR_BOUNCE)); 1592 1593 for_each_zone(zone) { 1594 int i; 1595 1596 if (!populated_zone(zone)) 1597 continue; 1598 1599 show_node(zone); 1600 printk("%s" 1601 " free:%lukB" 1602 " min:%lukB" 1603 " low:%lukB" 1604 " high:%lukB" 1605 " active:%lukB" 1606 " inactive:%lukB" 1607 " present:%lukB" 1608 " pages_scanned:%lu" 1609 " all_unreclaimable? %s" 1610 "\n", 1611 zone->name, 1612 K(zone_page_state(zone, NR_FREE_PAGES)), 1613 K(zone->pages_min), 1614 K(zone->pages_low), 1615 K(zone->pages_high), 1616 K(zone_page_state(zone, NR_ACTIVE)), 1617 K(zone_page_state(zone, NR_INACTIVE)), 1618 K(zone->present_pages), 1619 zone->pages_scanned, 1620 (zone->all_unreclaimable ? "yes" : "no") 1621 ); 1622 printk("lowmem_reserve[]:"); 1623 for (i = 0; i < MAX_NR_ZONES; i++) 1624 printk(" %lu", zone->lowmem_reserve[i]); 1625 printk("\n"); 1626 } 1627 1628 for_each_zone(zone) { 1629 unsigned long nr[MAX_ORDER], flags, order, total = 0; 1630 1631 if (!populated_zone(zone)) 1632 continue; 1633 1634 show_node(zone); 1635 printk("%s: ", zone->name); 1636 1637 spin_lock_irqsave(&zone->lock, flags); 1638 for (order = 0; order < MAX_ORDER; order++) { 1639 nr[order] = zone->free_area[order].nr_free; 1640 total += nr[order] << order; 1641 } 1642 spin_unlock_irqrestore(&zone->lock, flags); 1643 for (order = 0; order < MAX_ORDER; order++) 1644 printk("%lu*%lukB ", nr[order], K(1UL) << order); 1645 printk("= %lukB\n", K(total)); 1646 } 1647 1648 show_swap_cache_info(); 1649} 1650 1651/* 1652 * Builds allocation fallback zone lists. 1653 * 1654 * Add all populated zones of a node to the zonelist. 1655 */ 1656static int __meminit build_zonelists_node(pg_data_t *pgdat, 1657 struct zonelist *zonelist, int nr_zones, enum zone_type zone_type) 1658{ 1659 struct zone *zone; 1660 1661 BUG_ON(zone_type >= MAX_NR_ZONES); 1662 zone_type++; 1663 1664 do { 1665 zone_type--; 1666 zone = pgdat->node_zones + zone_type; 1667 if (populated_zone(zone)) { 1668 zonelist->zones[nr_zones++] = zone; 1669 check_highest_zone(zone_type); 1670 } 1671 1672 } while (zone_type); 1673 return nr_zones; 1674} 1675 1676#ifdef CONFIG_NUMA 1677#define MAX_NODE_LOAD (num_online_nodes()) 1678static int __meminitdata node_load[MAX_NUMNODES]; 1679/** 1680 * find_next_best_node - find the next node that should appear in a given node's fallback list 1681 * @node: node whose fallback list we're appending 1682 * @used_node_mask: nodemask_t of already used nodes 1683 * 1684 * We use a number of factors to determine which is the next node that should 1685 * appear on a given node's fallback list. The node should not have appeared 1686 * already in @node's fallback list, and it should be the next closest node 1687 * according to the distance array (which contains arbitrary distance values 1688 * from each node to each node in the system), and should also prefer nodes 1689 * with no CPUs, since presumably they'll have very little allocation pressure 1690 * on them otherwise. 1691 * It returns -1 if no node is found. 1692 */ 1693static int __meminit find_next_best_node(int node, nodemask_t *used_node_mask) 1694{ 1695 int n, val; 1696 int min_val = INT_MAX; 1697 int best_node = -1; 1698 1699 /* Use the local node if we haven't already */ 1700 if (!node_isset(node, *used_node_mask)) { 1701 node_set(node, *used_node_mask); 1702 return node; 1703 } 1704 1705 for_each_online_node(n) { 1706 cpumask_t tmp; 1707 1708 /* Don't want a node to appear more than once */ 1709 if (node_isset(n, *used_node_mask)) 1710 continue; 1711 1712 /* Use the distance array to find the distance */ 1713 val = node_distance(node, n); 1714 1715 /* Penalize nodes under us ("prefer the next node") */ 1716 val += (n < node); 1717 1718 /* Give preference to headless and unused nodes */ 1719 tmp = node_to_cpumask(n); 1720 if (!cpus_empty(tmp)) 1721 val += PENALTY_FOR_NODE_WITH_CPUS; 1722 1723 /* Slight preference for less loaded node */ 1724 val *= (MAX_NODE_LOAD*MAX_NUMNODES); 1725 val += node_load[n]; 1726 1727 if (val < min_val) { 1728 min_val = val; 1729 best_node = n; 1730 } 1731 } 1732 1733 if (best_node >= 0) 1734 node_set(best_node, *used_node_mask); 1735 1736 return best_node; 1737} 1738 1739static void __meminit build_zonelists(pg_data_t *pgdat) 1740{ 1741 int j, node, local_node; 1742 enum zone_type i; 1743 int prev_node, load; 1744 struct zonelist *zonelist; 1745 nodemask_t used_mask; 1746 1747 /* initialize zonelists */ 1748 for (i = 0; i < MAX_NR_ZONES; i++) { 1749 zonelist = pgdat->node_zonelists + i; 1750 zonelist->zones[0] = NULL; 1751 } 1752 1753 /* NUMA-aware ordering of nodes */ 1754 local_node = pgdat->node_id; 1755 load = num_online_nodes(); 1756 prev_node = local_node; 1757 nodes_clear(used_mask); 1758 while ((node = find_next_best_node(local_node, &used_mask)) >= 0) { 1759 int distance = node_distance(local_node, node); 1760 1761 /* 1762 * If another node is sufficiently far away then it is better 1763 * to reclaim pages in a zone before going off node. 1764 */ 1765 if (distance > RECLAIM_DISTANCE) 1766 zone_reclaim_mode = 1; 1767 1768 /* 1769 * We don't want to pressure a particular node. 1770 * So adding penalty to the first node in same 1771 * distance group to make it round-robin. 1772 */ 1773 1774 if (distance != node_distance(local_node, prev_node)) 1775 node_load[node] += load; 1776 prev_node = node; 1777 load--; 1778 for (i = 0; i < MAX_NR_ZONES; i++) { 1779 zonelist = pgdat->node_zonelists + i; 1780 for (j = 0; zonelist->zones[j] != NULL; j++); 1781 1782 j = build_zonelists_node(NODE_DATA(node), zonelist, j, i); 1783 zonelist->zones[j] = NULL; 1784 } 1785 } 1786} 1787 1788/* Construct the zonelist performance cache - see further mmzone.h */ 1789static void __meminit build_zonelist_cache(pg_data_t *pgdat) 1790{ 1791 int i; 1792 1793 for (i = 0; i < MAX_NR_ZONES; i++) { 1794 struct zonelist *zonelist; 1795 struct zonelist_cache *zlc; 1796 struct zone **z; 1797 1798 zonelist = pgdat->node_zonelists + i; 1799 zonelist->zlcache_ptr = zlc = &zonelist->zlcache; 1800 bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST); 1801 for (z = zonelist->zones; *z; z++) 1802 zlc->z_to_n[z - zonelist->zones] = zone_to_nid(*z); 1803 } 1804} 1805 1806#else /* CONFIG_NUMA */ 1807 1808static void __meminit build_zonelists(pg_data_t *pgdat) 1809{ 1810 int node, local_node; 1811 enum zone_type i,j; 1812 1813 local_node = pgdat->node_id; 1814 for (i = 0; i < MAX_NR_ZONES; i++) { 1815 struct zonelist *zonelist; 1816 1817 zonelist = pgdat->node_zonelists + i; 1818 1819 j = build_zonelists_node(pgdat, zonelist, 0, i); 1820 /* 1821 * Now we build the zonelist so that it contains the zones 1822 * of all the other nodes. 1823 * We don't want to pressure a particular node, so when 1824 * building the zones for node N, we make sure that the 1825 * zones coming right after the local ones are those from 1826 * node N+1 (modulo N) 1827 */ 1828 for (node = local_node + 1; node < MAX_NUMNODES; node++) { 1829 if (!node_online(node)) 1830 continue; 1831 j = build_zonelists_node(NODE_DATA(node), zonelist, j, i); 1832 } 1833 for (node = 0; node < local_node; node++) { 1834 if (!node_online(node)) 1835 continue; 1836 j = build_zonelists_node(NODE_DATA(node), zonelist, j, i); 1837 } 1838 1839 zonelist->zones[j] = NULL; 1840 } 1841} 1842 1843/* non-NUMA variant of zonelist performance cache - just NULL zlcache_ptr */ 1844static void __meminit build_zonelist_cache(pg_data_t *pgdat) 1845{ 1846 int i; 1847 1848 for (i = 0; i < MAX_NR_ZONES; i++) 1849 pgdat->node_zonelists[i].zlcache_ptr = NULL; 1850} 1851 1852#endif /* CONFIG_NUMA */ 1853 1854/* return values int ....just for stop_machine_run() */ 1855static int __meminit __build_all_zonelists(void *dummy) 1856{ 1857 int nid; 1858 1859 for_each_online_node(nid) { 1860 build_zonelists(NODE_DATA(nid)); 1861 build_zonelist_cache(NODE_DATA(nid)); 1862 } 1863 return 0; 1864} 1865 1866void __meminit build_all_zonelists(void) 1867{ 1868 if (system_state == SYSTEM_BOOTING) { 1869 __build_all_zonelists(NULL); 1870 cpuset_init_current_mems_allowed(); 1871 } else { 1872 /* we have to stop all cpus to guaranntee there is no user 1873 of zonelist */ 1874 stop_machine_run(__build_all_zonelists, NULL, NR_CPUS); 1875 /* cpuset refresh routine should be here */ 1876 } 1877 vm_total_pages = nr_free_pagecache_pages(); 1878 printk("Built %i zonelists. Total pages: %ld\n", 1879 num_online_nodes(), vm_total_pages); 1880} 1881 1882/* 1883 * Helper functions to size the waitqueue hash table. 1884 * Essentially these want to choose hash table sizes sufficiently 1885 * large so that collisions trying to wait on pages are rare. 1886 * But in fact, the number of active page waitqueues on typical 1887 * systems is ridiculously low, less than 200. So this is even 1888 * conservative, even though it seems large. 1889 * 1890 * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to 1891 * waitqueues, i.e. the size of the waitq table given the number of pages. 1892 */ 1893#define PAGES_PER_WAITQUEUE 256 1894 1895#ifndef CONFIG_MEMORY_HOTPLUG 1896static inline unsigned long wait_table_hash_nr_entries(unsigned long pages) 1897{ 1898 unsigned long size = 1; 1899 1900 pages /= PAGES_PER_WAITQUEUE; 1901 1902 while (size < pages) 1903 size <<= 1; 1904 1905 /* 1906 * Once we have dozens or even hundreds of threads sleeping 1907 * on IO we've got bigger problems than wait queue collision. 1908 * Limit the size of the wait table to a reasonable size. 1909 */ 1910 size = min(size, 4096UL); 1911 1912 return max(size, 4UL); 1913} 1914#else 1915/* 1916 * A zone's size might be changed by hot-add, so it is not possible to determine 1917 * a suitable size for its wait_table. So we use the maximum size now. 1918 * 1919 * The max wait table size = 4096 x sizeof(wait_queue_head_t). ie: 1920 * 1921 * i386 (preemption config) : 4096 x 16 = 64Kbyte. 1922 * ia64, x86-64 (no preemption): 4096 x 20 = 80Kbyte. 1923 * ia64, x86-64 (preemption) : 4096 x 24 = 96Kbyte. 1924 * 1925 * The maximum entries are prepared when a zone's memory is (512K + 256) pages 1926 * or more by the traditional way. (See above). It equals: 1927 * 1928 * i386, x86-64, powerpc(4K page size) : = ( 2G + 1M)byte. 1929 * ia64(16K page size) : = ( 8G + 4M)byte. 1930 * powerpc (64K page size) : = (32G +16M)byte. 1931 */ 1932static inline unsigned long wait_table_hash_nr_entries(unsigned long pages) 1933{ 1934 return 4096UL; 1935} 1936#endif 1937 1938/* 1939 * This is an integer logarithm so that shifts can be used later 1940 * to extract the more random high bits from the multiplicative 1941 * hash function before the remainder is taken. 1942 */ 1943static inline unsigned long wait_table_bits(unsigned long size) 1944{ 1945 return ffz(~size); 1946} 1947 1948#define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1)) 1949 1950/* 1951 * Initially all pages are reserved - free ones are freed 1952 * up by free_all_bootmem() once the early boot process is 1953 * done. Non-atomic initialization, single-pass. 1954 */ 1955void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone, 1956 unsigned long start_pfn, enum memmap_context context) 1957{ 1958 struct page *page; 1959 unsigned long end_pfn = start_pfn + size; 1960 unsigned long pfn; 1961 1962 for (pfn = start_pfn; pfn < end_pfn; pfn++) { 1963 /* 1964 * There can be holes in boot-time mem_map[]s 1965 * handed to this function. They do not 1966 * exist on hotplugged memory. 1967 */ 1968 if (context == MEMMAP_EARLY) { 1969 if (!early_pfn_valid(pfn)) 1970 continue; 1971 if (!early_pfn_in_nid(pfn, nid)) 1972 continue; 1973 } 1974 page = pfn_to_page(pfn); 1975 set_page_links(page, zone, nid, pfn); 1976 init_page_count(page); 1977 reset_page_mapcount(page); 1978 SetPageReserved(page); 1979 INIT_LIST_HEAD(&page->lru); 1980#ifdef WANT_PAGE_VIRTUAL 1981 /* The shift won't overflow because ZONE_NORMAL is below 4G. */ 1982 if (!is_highmem_idx(zone)) 1983 set_page_address(page, __va(pfn << PAGE_SHIFT)); 1984#endif 1985 } 1986} 1987 1988void zone_init_free_lists(struct pglist_data *pgdat, struct zone *zone, 1989 unsigned long size) 1990{ 1991 int order; 1992 for (order = 0; order < MAX_ORDER ; order++) { 1993 INIT_LIST_HEAD(&zone->free_area[order].free_list); 1994 zone->free_area[order].nr_free = 0; 1995 } 1996} 1997 1998#ifndef __HAVE_ARCH_MEMMAP_INIT 1999#define memmap_init(size, nid, zone, start_pfn) \ 2000 memmap_init_zone((size), (nid), (zone), (start_pfn), MEMMAP_EARLY) 2001#endif 2002 2003static int __cpuinit zone_batchsize(struct zone *zone) 2004{ 2005 int batch; 2006 2007 /* 2008 * The per-cpu-pages pools are set to around 1000th of the 2009 * size of the zone. But no more than 1/2 of a meg. 2010 * 2011 * OK, so we don't know how big the cache is. So guess. 2012 */ 2013 batch = zone->present_pages / 1024; 2014 if (batch * PAGE_SIZE > 512 * 1024) 2015 batch = (512 * 1024) / PAGE_SIZE; 2016 batch /= 4; /* We effectively *= 4 below */ 2017 if (batch < 1) 2018 batch = 1; 2019 2020 /* 2021 * Clamp the batch to a 2^n - 1 value. Having a power 2022 * of 2 value was found to be more likely to have 2023 * suboptimal cache aliasing properties in some cases. 2024 * 2025 * For example if 2 tasks are alternately allocating 2026 * batches of pages, one task can end up with a lot 2027 * of pages of one half of the possible page colors 2028 * and the other with pages of the other colors. 2029 */ 2030 batch = (1 << (fls(batch + batch/2)-1)) - 1; 2031 2032 return batch; 2033} 2034 2035inline void setup_pageset(struct per_cpu_pageset *p, unsigned long batch) 2036{ 2037 struct per_cpu_pages *pcp; 2038 2039 memset(p, 0, sizeof(*p)); 2040 2041 pcp = &p->pcp[0]; /* hot */ 2042 pcp->count = 0; 2043 pcp->high = 6 * batch; 2044 pcp->batch = max(1UL, 1 * batch); 2045 INIT_LIST_HEAD(&pcp->list); 2046 2047 pcp = &p->pcp[1]; /* cold*/ 2048 pcp->count = 0; 2049 pcp->high = 2 * batch; 2050 pcp->batch = max(1UL, batch/2); 2051 INIT_LIST_HEAD(&pcp->list); 2052} 2053 2054/* 2055 * setup_pagelist_highmark() sets the high water mark for hot per_cpu_pagelist 2056 * to the value high for the pageset p. 2057 */ 2058 2059static void setup_pagelist_highmark(struct per_cpu_pageset *p, 2060 unsigned long high) 2061{ 2062 struct per_cpu_pages *pcp; 2063 2064 pcp = &p->pcp[0]; /* hot list */ 2065 pcp->high = high; 2066 pcp->batch = max(1UL, high/4); 2067 if ((high/4) > (PAGE_SHIFT * 8)) 2068 pcp->batch = PAGE_SHIFT * 8; 2069} 2070 2071 2072#ifdef CONFIG_NUMA 2073/* 2074 * Boot pageset table. One per cpu which is going to be used for all 2075 * zones and all nodes. The parameters will be set in such a way 2076 * that an item put on a list will immediately be handed over to 2077 * the buddy list. This is safe since pageset manipulation is done 2078 * with interrupts disabled. 2079 * 2080 * Some NUMA counter updates may also be caught by the boot pagesets. 2081 * 2082 * The boot_pagesets must be kept even after bootup is complete for 2083 * unused processors and/or zones. They do play a role for bootstrapping 2084 * hotplugged processors. 2085 * 2086 * zoneinfo_show() and maybe other functions do 2087 * not check if the processor is online before following the pageset pointer. 2088 * Other parts of the kernel may not check if the zone is available. 2089 */ 2090static struct per_cpu_pageset boot_pageset[NR_CPUS]; 2091 2092/* 2093 * Dynamically allocate memory for the 2094 * per cpu pageset array in struct zone. 2095 */ 2096static int __cpuinit process_zones(int cpu) 2097{ 2098 struct zone *zone, *dzone; 2099 2100 for_each_zone(zone) { 2101 2102 if (!populated_zone(zone)) 2103 continue; 2104 2105 zone_pcp(zone, cpu) = kmalloc_node(sizeof(struct per_cpu_pageset), 2106 GFP_KERNEL, cpu_to_node(cpu)); 2107 if (!zone_pcp(zone, cpu)) 2108 goto bad; 2109 2110 setup_pageset(zone_pcp(zone, cpu), zone_batchsize(zone)); 2111 2112 if (percpu_pagelist_fraction) 2113 setup_pagelist_highmark(zone_pcp(zone, cpu), 2114 (zone->present_pages / percpu_pagelist_fraction)); 2115 } 2116 2117 return 0; 2118bad: 2119 for_each_zone(dzone) { 2120 if (dzone == zone) 2121 break; 2122 kfree(zone_pcp(dzone, cpu)); 2123 zone_pcp(dzone, cpu) = NULL; 2124 } 2125 return -ENOMEM; 2126} 2127 2128static inline void free_zone_pagesets(int cpu) 2129{ 2130 struct zone *zone; 2131 2132 for_each_zone(zone) { 2133 struct per_cpu_pageset *pset = zone_pcp(zone, cpu); 2134 2135 /* Free per_cpu_pageset if it is slab allocated */ 2136 if (pset != &boot_pageset[cpu]) 2137 kfree(pset); 2138 zone_pcp(zone, cpu) = NULL; 2139 } 2140} 2141 2142static int __cpuinit pageset_cpuup_callback(struct notifier_block *nfb, 2143 unsigned long action, 2144 void *hcpu) 2145{ 2146 int cpu = (long)hcpu; 2147 int ret = NOTIFY_OK; 2148 2149 switch (action) { 2150 case CPU_UP_PREPARE: 2151 if (process_zones(cpu)) 2152 ret = NOTIFY_BAD; 2153 break; 2154 case CPU_UP_CANCELED: 2155 case CPU_DEAD: 2156 free_zone_pagesets(cpu); 2157 break; 2158 default: 2159 break; 2160 } 2161 return ret; 2162} 2163 2164static struct notifier_block __cpuinitdata pageset_notifier = 2165 { &pageset_cpuup_callback, NULL, 0 }; 2166 2167void __init setup_per_cpu_pageset(void) 2168{ 2169 int err; 2170 2171 /* Initialize per_cpu_pageset for cpu 0. 2172 * A cpuup callback will do this for every cpu 2173 * as it comes online 2174 */ 2175 err = process_zones(smp_processor_id()); 2176 BUG_ON(err); 2177 register_cpu_notifier(&pageset_notifier); 2178} 2179 2180#endif 2181 2182static __meminit noinline 2183int zone_wait_table_init(struct zone *zone, unsigned long zone_size_pages) 2184{ 2185 int i; 2186 struct pglist_data *pgdat = zone->zone_pgdat; 2187 size_t alloc_size; 2188 2189 /* 2190 * The per-page waitqueue mechanism uses hashed waitqueues 2191 * per zone. 2192 */ 2193 zone->wait_table_hash_nr_entries = 2194 wait_table_hash_nr_entries(zone_size_pages); 2195 zone->wait_table_bits = 2196 wait_table_bits(zone->wait_table_hash_nr_entries); 2197 alloc_size = zone->wait_table_hash_nr_entries 2198 * sizeof(wait_queue_head_t); 2199 2200 if (system_state == SYSTEM_BOOTING) { 2201 zone->wait_table = (wait_queue_head_t *) 2202 alloc_bootmem_node(pgdat, alloc_size); 2203 } else { 2204 /* 2205 * This case means that a zone whose size was 0 gets new memory 2206 * via memory hot-add. 2207 * But it may be the case that a new node was hot-added. In 2208 * this case vmalloc() will not be able to use this new node's 2209 * memory - this wait_table must be initialized to use this new 2210 * node itself as well. 2211 * To use this new node's memory, further consideration will be 2212 * necessary. 2213 */ 2214 zone->wait_table = (wait_queue_head_t *)vmalloc(alloc_size); 2215 } 2216 if (!zone->wait_table) 2217 return -ENOMEM; 2218 2219 for(i = 0; i < zone->wait_table_hash_nr_entries; ++i) 2220 init_waitqueue_head(zone->wait_table + i); 2221 2222 return 0; 2223} 2224 2225static __meminit void zone_pcp_init(struct zone *zone) 2226{ 2227 int cpu; 2228 unsigned long batch = zone_batchsize(zone); 2229 2230 for (cpu = 0; cpu < NR_CPUS; cpu++) { 2231#ifdef CONFIG_NUMA 2232 /* Early boot. Slab allocator not functional yet */ 2233 zone_pcp(zone, cpu) = &boot_pageset[cpu]; 2234 setup_pageset(&boot_pageset[cpu],0); 2235#else 2236 setup_pageset(zone_pcp(zone,cpu), batch); 2237#endif 2238 } 2239 if (zone->present_pages) 2240 printk(KERN_DEBUG " %s zone: %lu pages, LIFO batch:%lu\n", 2241 zone->name, zone->present_pages, batch); 2242} 2243 2244__meminit int init_currently_empty_zone(struct zone *zone, 2245 unsigned long zone_start_pfn, 2246 unsigned long size, 2247 enum memmap_context context) 2248{ 2249 struct pglist_data *pgdat = zone->zone_pgdat; 2250 int ret; 2251 ret = zone_wait_table_init(zone, size); 2252 if (ret) 2253 return ret; 2254 pgdat->nr_zones = zone_idx(zone) + 1; 2255 2256 zone->zone_start_pfn = zone_start_pfn; 2257 2258 memmap_init(size, pgdat->node_id, zone_idx(zone), zone_start_pfn); 2259 2260 zone_init_free_lists(pgdat, zone, zone->spanned_pages); 2261 2262 return 0; 2263} 2264 2265#ifdef CONFIG_ARCH_POPULATES_NODE_MAP 2266/* 2267 * Basic iterator support. Return the first range of PFNs for a node 2268 * Note: nid == MAX_NUMNODES returns first region regardless of node 2269 */ 2270static int __meminit first_active_region_index_in_nid(int nid) 2271{ 2272 int i; 2273 2274 for (i = 0; i < nr_nodemap_entries; i++) 2275 if (nid == MAX_NUMNODES || early_node_map[i].nid == nid) 2276 return i; 2277 2278 return -1; 2279} 2280 2281/* 2282 * Basic iterator support. Return the next active range of PFNs for a node 2283 * Note: nid == MAX_NUMNODES returns next region regardles of node 2284 */ 2285static int __meminit next_active_region_index_in_nid(int index, int nid) 2286{ 2287 for (index = index + 1; index < nr_nodemap_entries; index++) 2288 if (nid == MAX_NUMNODES || early_node_map[index].nid == nid) 2289 return index; 2290 2291 return -1; 2292} 2293 2294#ifndef CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID 2295/* 2296 * Required by SPARSEMEM. Given a PFN, return what node the PFN is on. 2297 * Architectures may implement their own version but if add_active_range() 2298 * was used and there are no special requirements, this is a convenient 2299 * alternative 2300 */ 2301int __init early_pfn_to_nid(unsigned long pfn) 2302{ 2303 int i; 2304 2305 for (i = 0; i < nr_nodemap_entries; i++) { 2306 unsigned long start_pfn = early_node_map[i].start_pfn; 2307 unsigned long end_pfn = early_node_map[i].end_pfn; 2308 2309 if (start_pfn <= pfn && pfn < end_pfn) 2310 return early_node_map[i].nid; 2311 } 2312 2313 return 0; 2314} 2315#endif /* CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID */ 2316 2317/* Basic iterator support to walk early_node_map[] */ 2318#define for_each_active_range_index_in_nid(i, nid) \ 2319 for (i = first_active_region_index_in_nid(nid); i != -1; \ 2320 i = next_active_region_index_in_nid(i, nid)) 2321 2322/** 2323 * free_bootmem_with_active_regions - Call free_bootmem_node for each active range 2324 * @nid: The node to free memory on. If MAX_NUMNODES, all nodes are freed. 2325 * @max_low_pfn: The highest PFN that will be passed to free_bootmem_node 2326 * 2327 * If an architecture guarantees that all ranges registered with 2328 * add_active_ranges() contain no holes and may be freed, this 2329 * this function may be used instead of calling free_bootmem() manually. 2330 */ 2331void __init free_bootmem_with_active_regions(int nid, 2332 unsigned long max_low_pfn) 2333{ 2334 int i; 2335 2336 for_each_active_range_index_in_nid(i, nid) { 2337 unsigned long size_pages = 0; 2338 unsigned long end_pfn = early_node_map[i].end_pfn; 2339 2340 if (early_node_map[i].start_pfn >= max_low_pfn) 2341 continue; 2342 2343 if (end_pfn > max_low_pfn) 2344 end_pfn = max_low_pfn; 2345 2346 size_pages = end_pfn - early_node_map[i].start_pfn; 2347 free_bootmem_node(NODE_DATA(early_node_map[i].nid), 2348 PFN_PHYS(early_node_map[i].start_pfn), 2349 size_pages << PAGE_SHIFT); 2350 } 2351} 2352 2353/** 2354 * sparse_memory_present_with_active_regions - Call memory_present for each active range 2355 * @nid: The node to call memory_present for. If MAX_NUMNODES, all nodes will be used. 2356 * 2357 * If an architecture guarantees that all ranges registered with 2358 * add_active_ranges() contain no holes and may be freed, this 2359 * function may be used instead of calling memory_present() manually. 2360 */ 2361void __init sparse_memory_present_with_active_regions(int nid) 2362{ 2363 int i; 2364 2365 for_each_active_range_index_in_nid(i, nid) 2366 memory_present(early_node_map[i].nid, 2367 early_node_map[i].start_pfn, 2368 early_node_map[i].end_pfn); 2369} 2370 2371/** 2372 * push_node_boundaries - Push node boundaries to at least the requested boundary 2373 * @nid: The nid of the node to push the boundary for 2374 * @start_pfn: The start pfn of the node 2375 * @end_pfn: The end pfn of the node 2376 * 2377 * In reserve-based hot-add, mem_map is allocated that is unused until hotadd 2378 * time. Specifically, on x86_64, SRAT will report ranges that can potentially 2379 * be hotplugged even though no physical memory exists. This function allows 2380 * an arch to push out the node boundaries so mem_map is allocated that can 2381 * be used later. 2382 */ 2383#ifdef CONFIG_MEMORY_HOTPLUG_RESERVE 2384void __init push_node_boundaries(unsigned int nid, 2385 unsigned long start_pfn, unsigned long end_pfn) 2386{ 2387 printk(KERN_DEBUG "Entering push_node_boundaries(%u, %lu, %lu)\n", 2388 nid, start_pfn, end_pfn); 2389 2390 /* Initialise the boundary for this node if necessary */ 2391 if (node_boundary_end_pfn[nid] == 0) 2392 node_boundary_start_pfn[nid] = -1UL; 2393 2394 /* Update the boundaries */ 2395 if (node_boundary_start_pfn[nid] > start_pfn) 2396 node_boundary_start_pfn[nid] = start_pfn; 2397 if (node_boundary_end_pfn[nid] < end_pfn) 2398 node_boundary_end_pfn[nid] = end_pfn; 2399} 2400 2401/* If necessary, push the node boundary out for reserve hotadd */ 2402static void __init account_node_boundary(unsigned int nid, 2403 unsigned long *start_pfn, unsigned long *end_pfn) 2404{ 2405 printk(KERN_DEBUG "Entering account_node_boundary(%u, %lu, %lu)\n", 2406 nid, *start_pfn, *end_pfn); 2407 2408 /* Return if boundary information has not been provided */ 2409 if (node_boundary_end_pfn[nid] == 0) 2410 return; 2411 2412 /* Check the boundaries and update if necessary */ 2413 if (node_boundary_start_pfn[nid] < *start_pfn) 2414 *start_pfn = node_boundary_start_pfn[nid]; 2415 if (node_boundary_end_pfn[nid] > *end_pfn) 2416 *end_pfn = node_boundary_end_pfn[nid]; 2417} 2418#else 2419void __init push_node_boundaries(unsigned int nid, 2420 unsigned long start_pfn, unsigned long end_pfn) {} 2421 2422static void __init account_node_boundary(unsigned int nid, 2423 unsigned long *start_pfn, unsigned long *end_pfn) {} 2424#endif 2425 2426 2427/** 2428 * get_pfn_range_for_nid - Return the start and end page frames for a node 2429 * @nid: The nid to return the range for. If MAX_NUMNODES, the min and max PFN are returned. 2430 * @start_pfn: Passed by reference. On return, it will have the node start_pfn. 2431 * @end_pfn: Passed by reference. On return, it will have the node end_pfn. 2432 * 2433 * It returns the start and end page frame of a node based on information 2434 * provided by an arch calling add_active_range(). If called for a node 2435 * with no available memory, a warning is printed and the start and end 2436 * PFNs will be 0. 2437 */ 2438void __meminit get_pfn_range_for_nid(unsigned int nid, 2439 unsigned long *start_pfn, unsigned long *end_pfn) 2440{ 2441 int i; 2442 *start_pfn = -1UL; 2443 *end_pfn = 0; 2444 2445 for_each_active_range_index_in_nid(i, nid) { 2446 *start_pfn = min(*start_pfn, early_node_map[i].start_pfn); 2447 *end_pfn = max(*end_pfn, early_node_map[i].end_pfn); 2448 } 2449 2450 if (*start_pfn == -1UL) { 2451 printk(KERN_WARNING "Node %u active with no memory\n", nid); 2452 *start_pfn = 0; 2453 } 2454 2455 /* Push the node boundaries out if requested */ 2456 account_node_boundary(nid, start_pfn, end_pfn); 2457} 2458 2459/* 2460 * Return the number of pages a zone spans in a node, including holes 2461 * present_pages = zone_spanned_pages_in_node() - zone_absent_pages_in_node() 2462 */ 2463unsigned long __meminit zone_spanned_pages_in_node(int nid, 2464 unsigned long zone_type, 2465 unsigned long *ignored) 2466{ 2467 unsigned long node_start_pfn, node_end_pfn; 2468 unsigned long zone_start_pfn, zone_end_pfn; 2469 2470 /* Get the start and end of the node and zone */ 2471 get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn); 2472 zone_start_pfn = arch_zone_lowest_possible_pfn[zone_type]; 2473 zone_end_pfn = arch_zone_highest_possible_pfn[zone_type]; 2474 2475 /* Check that this node has pages within the zone's required range */ 2476 if (zone_end_pfn < node_start_pfn || zone_start_pfn > node_end_pfn) 2477 return 0; 2478 2479 /* Move the zone boundaries inside the node if necessary */ 2480 zone_end_pfn = min(zone_end_pfn, node_end_pfn); 2481 zone_start_pfn = max(zone_start_pfn, node_start_pfn); 2482 2483 /* Return the spanned pages */ 2484 return zone_end_pfn - zone_start_pfn; 2485} 2486 2487/* 2488 * Return the number of holes in a range on a node. If nid is MAX_NUMNODES, 2489 * then all holes in the requested range will be accounted for. 2490 */ 2491unsigned long __meminit __absent_pages_in_range(int nid, 2492 unsigned long range_start_pfn, 2493 unsigned long range_end_pfn) 2494{ 2495 int i = 0; 2496 unsigned long prev_end_pfn = 0, hole_pages = 0; 2497 unsigned long start_pfn; 2498 2499 /* Find the end_pfn of the first active range of pfns in the node */ 2500 i = first_active_region_index_in_nid(nid); 2501 if (i == -1) 2502 return 0; 2503 2504 /* Account for ranges before physical memory on this node */ 2505 if (early_node_map[i].start_pfn > range_start_pfn) 2506 hole_pages = early_node_map[i].start_pfn - range_start_pfn; 2507 2508 prev_end_pfn = early_node_map[i].start_pfn; 2509 2510 /* Find all holes for the zone within the node */ 2511 for (; i != -1; i = next_active_region_index_in_nid(i, nid)) { 2512 2513 /* No need to continue if prev_end_pfn is outside the zone */ 2514 if (prev_end_pfn >= range_end_pfn) 2515 break; 2516 2517 /* Make sure the end of the zone is not within the hole */ 2518 start_pfn = min(early_node_map[i].start_pfn, range_end_pfn); 2519 prev_end_pfn = max(prev_end_pfn, range_start_pfn); 2520 2521 /* Update the hole size cound and move on */ 2522 if (start_pfn > range_start_pfn) { 2523 BUG_ON(prev_end_pfn > start_pfn); 2524 hole_pages += start_pfn - prev_end_pfn; 2525 } 2526 prev_end_pfn = early_node_map[i].end_pfn; 2527 } 2528 2529 /* Account for ranges past physical memory on this node */ 2530 if (range_end_pfn > prev_end_pfn) 2531 hole_pages += range_end_pfn - 2532 max(range_start_pfn, prev_end_pfn); 2533 2534 return hole_pages; 2535} 2536 2537/** 2538 * absent_pages_in_range - Return number of page frames in holes within a range 2539 * @start_pfn: The start PFN to start searching for holes 2540 * @end_pfn: The end PFN to stop searching for holes 2541 * 2542 * It returns the number of pages frames in memory holes within a range. 2543 */ 2544unsigned long __init absent_pages_in_range(unsigned long start_pfn, 2545 unsigned long end_pfn) 2546{ 2547 return __absent_pages_in_range(MAX_NUMNODES, start_pfn, end_pfn); 2548} 2549 2550/* Return the number of page frames in holes in a zone on a node */ 2551unsigned long __meminit zone_absent_pages_in_node(int nid, 2552 unsigned long zone_type, 2553 unsigned long *ignored) 2554{ 2555 unsigned long node_start_pfn, node_end_pfn; 2556 unsigned long zone_start_pfn, zone_end_pfn; 2557 2558 get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn); 2559 zone_start_pfn = max(arch_zone_lowest_possible_pfn[zone_type], 2560 node_start_pfn); 2561 zone_end_pfn = min(arch_zone_highest_possible_pfn[zone_type], 2562 node_end_pfn); 2563 2564 return __absent_pages_in_range(nid, zone_start_pfn, zone_end_pfn); 2565} 2566 2567#else 2568static inline unsigned long zone_spanned_pages_in_node(int nid, 2569 unsigned long zone_type, 2570 unsigned long *zones_size) 2571{ 2572 return zones_size[zone_type]; 2573} 2574 2575static inline unsigned long zone_absent_pages_in_node(int nid, 2576 unsigned long zone_type, 2577 unsigned long *zholes_size) 2578{ 2579 if (!zholes_size) 2580 return 0; 2581 2582 return zholes_size[zone_type]; 2583} 2584 2585#endif 2586 2587static void __meminit calculate_node_totalpages(struct pglist_data *pgdat, 2588 unsigned long *zones_size, unsigned long *zholes_size) 2589{ 2590 unsigned long realtotalpages, totalpages = 0; 2591 enum zone_type i; 2592 2593 for (i = 0; i < MAX_NR_ZONES; i++) 2594 totalpages += zone_spanned_pages_in_node(pgdat->node_id, i, 2595 zones_size); 2596 pgdat->node_spanned_pages = totalpages; 2597 2598 realtotalpages = totalpages; 2599 for (i = 0; i < MAX_NR_ZONES; i++) 2600 realtotalpages -= 2601 zone_absent_pages_in_node(pgdat->node_id, i, 2602 zholes_size); 2603 pgdat->node_present_pages = realtotalpages; 2604 printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id, 2605 realtotalpages); 2606} 2607 2608/* 2609 * Set up the zone data structures: 2610 * - mark all pages reserved 2611 * - mark all memory queues empty 2612 * - clear the memory bitmaps 2613 */ 2614static void __meminit free_area_init_core(struct pglist_data *pgdat, 2615 unsigned long *zones_size, unsigned long *zholes_size) 2616{ 2617 enum zone_type j; 2618 int nid = pgdat->node_id; 2619 unsigned long zone_start_pfn = pgdat->node_start_pfn; 2620 int ret; 2621 2622 pgdat_resize_init(pgdat); 2623 pgdat->nr_zones = 0; 2624 init_waitqueue_head(&pgdat->kswapd_wait); 2625 pgdat->kswapd_max_order = 0; 2626 2627 for (j = 0; j < MAX_NR_ZONES; j++) { 2628 struct zone *zone = pgdat->node_zones + j; 2629 unsigned long size, realsize, memmap_pages; 2630 2631 size = zone_spanned_pages_in_node(nid, j, zones_size); 2632 realsize = size - zone_absent_pages_in_node(nid, j, 2633 zholes_size); 2634 2635 /* 2636 * Adjust realsize so that it accounts for how much memory 2637 * is used by this zone for memmap. This affects the watermark 2638 * and per-cpu initialisations 2639 */ 2640 memmap_pages = (size * sizeof(struct page)) >> PAGE_SHIFT; 2641 if (realsize >= memmap_pages) { 2642 realsize -= memmap_pages; 2643 printk(KERN_DEBUG 2644 " %s zone: %lu pages used for memmap\n", 2645 zone_names[j], memmap_pages); 2646 } else 2647 printk(KERN_WARNING 2648 " %s zone: %lu pages exceeds realsize %lu\n", 2649 zone_names[j], memmap_pages, realsize); 2650 2651 /* Account for reserved pages */ 2652 if (j == 0 && realsize > dma_reserve) { 2653 realsize -= dma_reserve; 2654 printk(KERN_DEBUG " %s zone: %lu pages reserved\n", 2655 zone_names[0], dma_reserve); 2656 } 2657 2658 if (!is_highmem_idx(j)) 2659 nr_kernel_pages += realsize; 2660 nr_all_pages += realsize; 2661 2662 zone->spanned_pages = size; 2663 zone->present_pages = realsize; 2664#ifdef CONFIG_NUMA 2665 zone->node = nid; 2666 zone->min_unmapped_pages = (realsize*sysctl_min_unmapped_ratio) 2667 / 100; 2668 zone->min_slab_pages = (realsize * sysctl_min_slab_ratio) / 100; 2669#endif 2670 zone->name = zone_names[j]; 2671 spin_lock_init(&zone->lock); 2672 spin_lock_init(&zone->lru_lock); 2673 zone_seqlock_init(zone); 2674 zone->zone_pgdat = pgdat; 2675 2676 zone->prev_priority = DEF_PRIORITY; 2677 2678 zone_pcp_init(zone); 2679 INIT_LIST_HEAD(&zone->active_list); 2680 INIT_LIST_HEAD(&zone->inactive_list); 2681 zone->nr_scan_active = 0; 2682 zone->nr_scan_inactive = 0; 2683 zap_zone_vm_stats(zone); 2684 atomic_set(&zone->reclaim_in_progress, 0); 2685 if (!size) 2686 continue; 2687 2688 ret = init_currently_empty_zone(zone, zone_start_pfn, 2689 size, MEMMAP_EARLY); 2690 BUG_ON(ret); 2691 zone_start_pfn += size; 2692 } 2693} 2694 2695static void __meminit alloc_node_mem_map(struct pglist_data *pgdat) 2696{ 2697 /* Skip empty nodes */ 2698 if (!pgdat->node_spanned_pages) 2699 return; 2700 2701#ifdef CONFIG_FLAT_NODE_MEM_MAP 2702 /* ia64 gets its own node_mem_map, before this, without bootmem */ 2703 if (!pgdat->node_mem_map) { 2704 unsigned long size, start, end; 2705 struct page *map; 2706 2707 /* 2708 * The zone's endpoints aren't required to be MAX_ORDER 2709 * aligned but the node_mem_map endpoints must be in order 2710 * for the buddy allocator to function correctly. 2711 */ 2712 start = pgdat->node_start_pfn & ~(MAX_ORDER_NR_PAGES - 1); 2713 end = pgdat->node_start_pfn + pgdat->node_spanned_pages; 2714 end = ALIGN(end, MAX_ORDER_NR_PAGES); 2715 size = (end - start) * sizeof(struct page); 2716 map = alloc_remap(pgdat->node_id, size); 2717 if (!map) 2718 map = alloc_bootmem_node(pgdat, size); 2719 pgdat->node_mem_map = map + (pgdat->node_start_pfn - start); 2720 } 2721#ifdef CONFIG_FLATMEM 2722 /* 2723 * With no DISCONTIG, the global mem_map is just set as node 0's 2724 */ 2725 if (pgdat == NODE_DATA(0)) { 2726 mem_map = NODE_DATA(0)->node_mem_map; 2727#ifdef CONFIG_ARCH_POPULATES_NODE_MAP 2728 if (page_to_pfn(mem_map) != pgdat->node_start_pfn) 2729 mem_map -= pgdat->node_start_pfn; 2730#endif /* CONFIG_ARCH_POPULATES_NODE_MAP */ 2731 } 2732#endif 2733#endif /* CONFIG_FLAT_NODE_MEM_MAP */ 2734} 2735 2736void __meminit free_area_init_node(int nid, struct pglist_data *pgdat, 2737 unsigned long *zones_size, unsigned long node_start_pfn, 2738 unsigned long *zholes_size) 2739{ 2740 pgdat->node_id = nid; 2741 pgdat->node_start_pfn = node_start_pfn; 2742 calculate_node_totalpages(pgdat, zones_size, zholes_size); 2743 2744 alloc_node_mem_map(pgdat); 2745 2746 free_area_init_core(pgdat, zones_size, zholes_size); 2747} 2748 2749#ifdef CONFIG_ARCH_POPULATES_NODE_MAP 2750/** 2751 * add_active_range - Register a range of PFNs backed by physical memory 2752 * @nid: The node ID the range resides on 2753 * @start_pfn: The start PFN of the available physical memory 2754 * @end_pfn: The end PFN of the available physical memory 2755 * 2756 * These ranges are stored in an early_node_map[] and later used by 2757 * free_area_init_nodes() to calculate zone sizes and holes. If the 2758 * range spans a memory hole, it is up to the architecture to ensure 2759 * the memory is not freed by the bootmem allocator. If possible 2760 * the range being registered will be merged with existing ranges. 2761 */ 2762void __init add_active_range(unsigned int nid, unsigned long start_pfn, 2763 unsigned long end_pfn) 2764{ 2765 int i; 2766 2767 printk(KERN_DEBUG "Entering add_active_range(%d, %lu, %lu) " 2768 "%d entries of %d used\n", 2769 nid, start_pfn, end_pfn, 2770 nr_nodemap_entries, MAX_ACTIVE_REGIONS); 2771 2772 /* Merge with existing active regions if possible */ 2773 for (i = 0; i < nr_nodemap_entries; i++) { 2774 if (early_node_map[i].nid != nid) 2775 continue; 2776 2777 /* Skip if an existing region covers this new one */ 2778 if (start_pfn >= early_node_map[i].start_pfn && 2779 end_pfn <= early_node_map[i].end_pfn) 2780 return; 2781 2782 /* Merge forward if suitable */ 2783 if (start_pfn <= early_node_map[i].end_pfn && 2784 end_pfn > early_node_map[i].end_pfn) { 2785 early_node_map[i].end_pfn = end_pfn; 2786 return; 2787 } 2788 2789 /* Merge backward if suitable */ 2790 if (start_pfn < early_node_map[i].end_pfn && 2791 end_pfn >= early_node_map[i].start_pfn) { 2792 early_node_map[i].start_pfn = start_pfn; 2793 return; 2794 } 2795 } 2796 2797 /* Check that early_node_map is large enough */ 2798 if (i >= MAX_ACTIVE_REGIONS) { 2799 printk(KERN_CRIT "More than %d memory regions, truncating\n", 2800 MAX_ACTIVE_REGIONS); 2801 return; 2802 } 2803 2804 early_node_map[i].nid = nid; 2805 early_node_map[i].start_pfn = start_pfn; 2806 early_node_map[i].end_pfn = end_pfn; 2807 nr_nodemap_entries = i + 1; 2808} 2809 2810/** 2811 * shrink_active_range - Shrink an existing registered range of PFNs 2812 * @nid: The node id the range is on that should be shrunk 2813 * @old_end_pfn: The old end PFN of the range 2814 * @new_end_pfn: The new PFN of the range 2815 * 2816 * i386 with NUMA use alloc_remap() to store a node_mem_map on a local node. 2817 * The map is kept at the end physical page range that has already been 2818 * registered with add_active_range(). This function allows an arch to shrink 2819 * an existing registered range. 2820 */ 2821void __init shrink_active_range(unsigned int nid, unsigned long old_end_pfn, 2822 unsigned long new_end_pfn) 2823{ 2824 int i; 2825 2826 /* Find the old active region end and shrink */ 2827 for_each_active_range_index_in_nid(i, nid) 2828 if (early_node_map[i].end_pfn == old_end_pfn) { 2829 early_node_map[i].end_pfn = new_end_pfn; 2830 break; 2831 } 2832} 2833 2834/** 2835 * remove_all_active_ranges - Remove all currently registered regions 2836 * 2837 * During discovery, it may be found that a table like SRAT is invalid 2838 * and an alternative discovery method must be used. This function removes 2839 * all currently registered regions. 2840 */ 2841void __init remove_all_active_ranges(void) 2842{ 2843 memset(early_node_map, 0, sizeof(early_node_map)); 2844 nr_nodemap_entries = 0; 2845#ifdef CONFIG_MEMORY_HOTPLUG_RESERVE 2846 memset(node_boundary_start_pfn, 0, sizeof(node_boundary_start_pfn)); 2847 memset(node_boundary_end_pfn, 0, sizeof(node_boundary_end_pfn)); 2848#endif /* CONFIG_MEMORY_HOTPLUG_RESERVE */ 2849} 2850 2851/* Compare two active node_active_regions */ 2852static int __init cmp_node_active_region(const void *a, const void *b) 2853{ 2854 struct node_active_region *arange = (struct node_active_region *)a; 2855 struct node_active_region *brange = (struct node_active_region *)b; 2856 2857 /* Done this way to avoid overflows */ 2858 if (arange->start_pfn > brange->start_pfn) 2859 return 1; 2860 if (arange->start_pfn < brange->start_pfn) 2861 return -1; 2862 2863 return 0; 2864} 2865 2866/* sort the node_map by start_pfn */ 2867static void __init sort_node_map(void) 2868{ 2869 sort(early_node_map, (size_t)nr_nodemap_entries, 2870 sizeof(struct node_active_region), 2871 cmp_node_active_region, NULL); 2872} 2873 2874/* Find the lowest pfn for a node */ 2875unsigned long __init find_min_pfn_for_node(unsigned long nid) 2876{ 2877 int i; 2878 unsigned long min_pfn = ULONG_MAX; 2879 2880 /* Assuming a sorted map, the first range found has the starting pfn */ 2881 for_each_active_range_index_in_nid(i, nid) 2882 min_pfn = min(min_pfn, early_node_map[i].start_pfn); 2883 2884 if (min_pfn == ULONG_MAX) { 2885 printk(KERN_WARNING 2886 "Could not find start_pfn for node %lu\n", nid); 2887 return 0; 2888 } 2889 2890 return min_pfn; 2891} 2892 2893/** 2894 * find_min_pfn_with_active_regions - Find the minimum PFN registered 2895 * 2896 * It returns the minimum PFN based on information provided via 2897 * add_active_range(). 2898 */ 2899unsigned long __init find_min_pfn_with_active_regions(void) 2900{ 2901 return find_min_pfn_for_node(MAX_NUMNODES); 2902} 2903 2904/** 2905 * find_max_pfn_with_active_regions - Find the maximum PFN registered 2906 * 2907 * It returns the maximum PFN based on information provided via 2908 * add_active_range(). 2909 */ 2910unsigned long __init find_max_pfn_with_active_regions(void) 2911{ 2912 int i; 2913 unsigned long max_pfn = 0; 2914 2915 for (i = 0; i < nr_nodemap_entries; i++) 2916 max_pfn = max(max_pfn, early_node_map[i].end_pfn); 2917 2918 return max_pfn; 2919} 2920 2921/** 2922 * free_area_init_nodes - Initialise all pg_data_t and zone data 2923 * @max_zone_pfn: an array of max PFNs for each zone 2924 * 2925 * This will call free_area_init_node() for each active node in the system. 2926 * Using the page ranges provided by add_active_range(), the size of each 2927 * zone in each node and their holes is calculated. If the maximum PFN 2928 * between two adjacent zones match, it is assumed that the zone is empty. 2929 * For example, if arch_max_dma_pfn == arch_max_dma32_pfn, it is assumed 2930 * that arch_max_dma32_pfn has no pages. It is also assumed that a zone 2931 * starts where the previous one ended. For example, ZONE_DMA32 starts 2932 * at arch_max_dma_pfn. 2933 */ 2934void __init free_area_init_nodes(unsigned long *max_zone_pfn) 2935{ 2936 unsigned long nid; 2937 enum zone_type i; 2938 2939 /* Sort early_node_map as initialisation assumes it is sorted */ 2940 sort_node_map(); 2941 2942 /* Record where the zone boundaries are */ 2943 memset(arch_zone_lowest_possible_pfn, 0, 2944 sizeof(arch_zone_lowest_possible_pfn)); 2945 memset(arch_zone_highest_possible_pfn, 0, 2946 sizeof(arch_zone_highest_possible_pfn)); 2947 arch_zone_lowest_possible_pfn[0] = find_min_pfn_with_active_regions(); 2948 arch_zone_highest_possible_pfn[0] = max_zone_pfn[0]; 2949 for (i = 1; i < MAX_NR_ZONES; i++) { 2950 arch_zone_lowest_possible_pfn[i] = 2951 arch_zone_highest_possible_pfn[i-1]; 2952 arch_zone_highest_possible_pfn[i] = 2953 max(max_zone_pfn[i], arch_zone_lowest_possible_pfn[i]); 2954 } 2955 2956 /* Print out the zone ranges */ 2957 printk("Zone PFN ranges:\n"); 2958 for (i = 0; i < MAX_NR_ZONES; i++) 2959 printk(" %-8s %8lu -> %8lu\n", 2960 zone_names[i], 2961 arch_zone_lowest_possible_pfn[i], 2962 arch_zone_highest_possible_pfn[i]); 2963 2964 /* Print out the early_node_map[] */ 2965 printk("early_node_map[%d] active PFN ranges\n", nr_nodemap_entries); 2966 for (i = 0; i < nr_nodemap_entries; i++) 2967 printk(" %3d: %8lu -> %8lu\n", early_node_map[i].nid, 2968 early_node_map[i].start_pfn, 2969 early_node_map[i].end_pfn); 2970 2971 /* Initialise every node */ 2972 setup_nr_node_ids(); 2973 for_each_online_node(nid) { 2974 pg_data_t *pgdat = NODE_DATA(nid); 2975 free_area_init_node(nid, pgdat, NULL, 2976 find_min_pfn_for_node(nid), NULL); 2977 } 2978} 2979#endif /* CONFIG_ARCH_POPULATES_NODE_MAP */ 2980 2981/** 2982 * set_dma_reserve - set the specified number of pages reserved in the first zone 2983 * @new_dma_reserve: The number of pages to mark reserved 2984 * 2985 * The per-cpu batchsize and zone watermarks are determined by present_pages. 2986 * In the DMA zone, a significant percentage may be consumed by kernel image 2987 * and other unfreeable allocations which can skew the watermarks badly. This 2988 * function may optionally be used to account for unfreeable pages in the 2989 * first zone (e.g., ZONE_DMA). The effect will be lower watermarks and 2990 * smaller per-cpu batchsize. 2991 */ 2992void __init set_dma_reserve(unsigned long new_dma_reserve) 2993{ 2994 dma_reserve = new_dma_reserve; 2995} 2996 2997#ifndef CONFIG_NEED_MULTIPLE_NODES 2998static bootmem_data_t contig_bootmem_data; 2999struct pglist_data contig_page_data = { .bdata = &contig_bootmem_data }; 3000 3001EXPORT_SYMBOL(contig_page_data); 3002#endif 3003 3004void __init free_area_init(unsigned long *zones_size) 3005{ 3006 free_area_init_node(0, NODE_DATA(0), zones_size, 3007 __pa(PAGE_OFFSET) >> PAGE_SHIFT, NULL); 3008} 3009 3010static int page_alloc_cpu_notify(struct notifier_block *self, 3011 unsigned long action, void *hcpu) 3012{ 3013 int cpu = (unsigned long)hcpu; 3014 3015 if (action == CPU_DEAD) { 3016 local_irq_disable(); 3017 __drain_pages(cpu); 3018 vm_events_fold_cpu(cpu); 3019 local_irq_enable(); 3020 refresh_cpu_vm_stats(cpu); 3021 } 3022 return NOTIFY_OK; 3023} 3024 3025void __init page_alloc_init(void) 3026{ 3027 hotcpu_notifier(page_alloc_cpu_notify, 0); 3028} 3029 3030/* 3031 * calculate_totalreserve_pages - called when sysctl_lower_zone_reserve_ratio 3032 * or min_free_kbytes changes. 3033 */ 3034static void calculate_totalreserve_pages(void) 3035{ 3036 struct pglist_data *pgdat; 3037 unsigned long reserve_pages = 0; 3038 enum zone_type i, j; 3039 3040 for_each_online_pgdat(pgdat) { 3041 for (i = 0; i < MAX_NR_ZONES; i++) { 3042 struct zone *zone = pgdat->node_zones + i; 3043 unsigned long max = 0; 3044 3045 /* Find valid and maximum lowmem_reserve in the zone */ 3046 for (j = i; j < MAX_NR_ZONES; j++) { 3047 if (zone->lowmem_reserve[j] > max) 3048 max = zone->lowmem_reserve[j]; 3049 } 3050 3051 /* we treat pages_high as reserved pages. */ 3052 max += zone->pages_high; 3053 3054 if (max > zone->present_pages) 3055 max = zone->present_pages; 3056 reserve_pages += max; 3057 } 3058 } 3059 totalreserve_pages = reserve_pages; 3060} 3061 3062/* 3063 * setup_per_zone_lowmem_reserve - called whenever 3064 * sysctl_lower_zone_reserve_ratio changes. Ensures that each zone 3065 * has a correct pages reserved value, so an adequate number of 3066 * pages are left in the zone after a successful __alloc_pages(). 3067 */ 3068static void setup_per_zone_lowmem_reserve(void) 3069{ 3070 struct pglist_data *pgdat; 3071 enum zone_type j, idx; 3072 3073 for_each_online_pgdat(pgdat) { 3074 for (j = 0; j < MAX_NR_ZONES; j++) { 3075 struct zone *zone = pgdat->node_zones + j; 3076 unsigned long present_pages = zone->present_pages; 3077 3078 zone->lowmem_reserve[j] = 0; 3079 3080 idx = j; 3081 while (idx) { 3082 struct zone *lower_zone; 3083 3084 idx--; 3085 3086 if (sysctl_lowmem_reserve_ratio[idx] < 1) 3087 sysctl_lowmem_reserve_ratio[idx] = 1; 3088 3089 lower_zone = pgdat->node_zones + idx; 3090 lower_zone->lowmem_reserve[j] = present_pages / 3091 sysctl_lowmem_reserve_ratio[idx]; 3092 present_pages += lower_zone->present_pages; 3093 } 3094 } 3095 } 3096 3097 /* update totalreserve_pages */ 3098 calculate_totalreserve_pages(); 3099} 3100 3101/** 3102 * setup_per_zone_pages_min - called when min_free_kbytes changes. 3103 * 3104 * Ensures that the pages_{min,low,high} values for each zone are set correctly 3105 * with respect to min_free_kbytes. 3106 */ 3107void setup_per_zone_pages_min(void) 3108{ 3109 unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10); 3110 unsigned long lowmem_pages = 0; 3111 struct zone *zone; 3112 unsigned long flags; 3113 3114 /* Calculate total number of !ZONE_HIGHMEM pages */ 3115 for_each_zone(zone) { 3116 if (!is_highmem(zone)) 3117 lowmem_pages += zone->present_pages; 3118 } 3119 3120 for_each_zone(zone) { 3121 u64 tmp; 3122 3123 spin_lock_irqsave(&zone->lru_lock, flags); 3124 tmp = (u64)pages_min * zone->present_pages; 3125 do_div(tmp, lowmem_pages); 3126 if (is_highmem(zone)) { 3127 /* 3128 * __GFP_HIGH and PF_MEMALLOC allocations usually don't 3129 * need highmem pages, so cap pages_min to a small 3130 * value here. 3131 * 3132 * The (pages_high-pages_low) and (pages_low-pages_min) 3133 * deltas controls asynch page reclaim, and so should 3134 * not be capped for highmem. 3135 */ 3136 int min_pages; 3137 3138 min_pages = zone->present_pages / 1024; 3139 if (min_pages < SWAP_CLUSTER_MAX) 3140 min_pages = SWAP_CLUSTER_MAX; 3141 if (min_pages > 128) 3142 min_pages = 128; 3143 zone->pages_min = min_pages; 3144 } else { 3145 /* 3146 * If it's a lowmem zone, reserve a number of pages 3147 * proportionate to the zone's size. 3148 */ 3149 zone->pages_min = tmp; 3150 } 3151 3152 zone->pages_low = zone->pages_min + (tmp >> 2); 3153 zone->pages_high = zone->pages_min + (tmp >> 1); 3154 spin_unlock_irqrestore(&zone->lru_lock, flags); 3155 } 3156 3157 /* update totalreserve_pages */ 3158 calculate_totalreserve_pages(); 3159} 3160 3161/* 3162 * Initialise min_free_kbytes. 3163 * 3164 * For small machines we want it small (128k min). For large machines 3165 * we want it large (64MB max). But it is not linear, because network 3166 * bandwidth does not increase linearly with machine size. We use 3167 * 3168 * min_free_kbytes = 4 * sqrt(lowmem_kbytes), for better accuracy: 3169 * min_free_kbytes = sqrt(lowmem_kbytes * 16) 3170 * 3171 * which yields 3172 * 3173 * 16MB: 512k 3174 * 32MB: 724k 3175 * 64MB: 1024k 3176 * 128MB: 1448k 3177 * 256MB: 2048k 3178 * 512MB: 2896k 3179 * 1024MB: 4096k 3180 * 2048MB: 5792k 3181 * 4096MB: 8192k 3182 * 8192MB: 11584k 3183 * 16384MB: 16384k 3184 */ 3185static int __init init_per_zone_pages_min(void) 3186{ 3187 unsigned long lowmem_kbytes; 3188 3189 lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10); 3190 3191 min_free_kbytes = int_sqrt(lowmem_kbytes * 16); 3192 if (min_free_kbytes < 128) 3193 min_free_kbytes = 128; 3194 if (min_free_kbytes > 65536) 3195 min_free_kbytes = 65536; 3196 setup_per_zone_pages_min(); 3197 setup_per_zone_lowmem_reserve(); 3198 return 0; 3199} 3200module_init(init_per_zone_pages_min) 3201 3202/* 3203 * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so 3204 * that we can call two helper functions whenever min_free_kbytes 3205 * changes. 3206 */ 3207int min_free_kbytes_sysctl_handler(ctl_table *table, int write, 3208 struct file *file, void __user *buffer, size_t *length, loff_t *ppos) 3209{ 3210 proc_dointvec(table, write, file, buffer, length, ppos); 3211 if (write) 3212 setup_per_zone_pages_min(); 3213 return 0; 3214} 3215 3216#ifdef CONFIG_NUMA 3217int sysctl_min_unmapped_ratio_sysctl_handler(ctl_table *table, int write, 3218 struct file *file, void __user *buffer, size_t *length, loff_t *ppos) 3219{ 3220 struct zone *zone; 3221 int rc; 3222 3223 rc = proc_dointvec_minmax(table, write, file, buffer, length, ppos); 3224 if (rc) 3225 return rc; 3226 3227 for_each_zone(zone) 3228 zone->min_unmapped_pages = (zone->present_pages * 3229 sysctl_min_unmapped_ratio) / 100; 3230 return 0; 3231} 3232 3233int sysctl_min_slab_ratio_sysctl_handler(ctl_table *table, int write, 3234 struct file *file, void __user *buffer, size_t *length, loff_t *ppos) 3235{ 3236 struct zone *zone; 3237 int rc; 3238 3239 rc = proc_dointvec_minmax(table, write, file, buffer, length, ppos); 3240 if (rc) 3241 return rc; 3242 3243 for_each_zone(zone) 3244 zone->min_slab_pages = (zone->present_pages * 3245 sysctl_min_slab_ratio) / 100; 3246 return 0; 3247} 3248#endif 3249 3250/* 3251 * lowmem_reserve_ratio_sysctl_handler - just a wrapper around 3252 * proc_dointvec() so that we can call setup_per_zone_lowmem_reserve() 3253 * whenever sysctl_lowmem_reserve_ratio changes. 3254 * 3255 * The reserve ratio obviously has absolutely no relation with the 3256 * pages_min watermarks. The lowmem reserve ratio can only make sense 3257 * if in function of the boot time zone sizes. 3258 */ 3259int lowmem_reserve_ratio_sysctl_handler(ctl_table *table, int write, 3260 struct file *file, void __user *buffer, size_t *length, loff_t *ppos) 3261{ 3262 proc_dointvec_minmax(table, write, file, buffer, length, ppos); 3263 setup_per_zone_lowmem_reserve(); 3264 return 0; 3265} 3266 3267/* 3268 * percpu_pagelist_fraction - changes the pcp->high for each zone on each 3269 * cpu. It is the fraction of total pages in each zone that a hot per cpu pagelist 3270 * can have before it gets flushed back to buddy allocator. 3271 */ 3272 3273int percpu_pagelist_fraction_sysctl_handler(ctl_table *table, int write, 3274 struct file *file, void __user *buffer, size_t *length, loff_t *ppos) 3275{ 3276 struct zone *zone; 3277 unsigned int cpu; 3278 int ret; 3279 3280 ret = proc_dointvec_minmax(table, write, file, buffer, length, ppos); 3281 if (!write || (ret == -EINVAL)) 3282 return ret; 3283 for_each_zone(zone) { 3284 for_each_online_cpu(cpu) { 3285 unsigned long high; 3286 high = zone->present_pages / percpu_pagelist_fraction; 3287 setup_pagelist_highmark(zone_pcp(zone, cpu), high); 3288 } 3289 } 3290 return 0; 3291} 3292 3293int hashdist = HASHDIST_DEFAULT; 3294 3295#ifdef CONFIG_NUMA 3296static int __init set_hashdist(char *str) 3297{ 3298 if (!str) 3299 return 0; 3300 hashdist = simple_strtoul(str, &str, 0); 3301 return 1; 3302} 3303__setup("hashdist=", set_hashdist); 3304#endif 3305 3306/* 3307 * allocate a large system hash table from bootmem 3308 * - it is assumed that the hash table must contain an exact power-of-2 3309 * quantity of entries 3310 * - limit is the number of hash buckets, not the total allocation size 3311 */ 3312void *__init alloc_large_system_hash(const char *tablename, 3313 unsigned long bucketsize, 3314 unsigned long numentries, 3315 int scale, 3316 int flags, 3317 unsigned int *_hash_shift, 3318 unsigned int *_hash_mask, 3319 unsigned long limit) 3320{ 3321 unsigned long long max = limit; 3322 unsigned long log2qty, size; 3323 void *table = NULL; 3324 3325 /* allow the kernel cmdline to have a say */ 3326 if (!numentries) { 3327 /* round applicable memory size up to nearest megabyte */ 3328 numentries = nr_kernel_pages; 3329 numentries += (1UL << (20 - PAGE_SHIFT)) - 1; 3330 numentries >>= 20 - PAGE_SHIFT; 3331 numentries <<= 20 - PAGE_SHIFT; 3332 3333 /* limit to 1 bucket per 2^scale bytes of low memory */ 3334 if (scale > PAGE_SHIFT) 3335 numentries >>= (scale - PAGE_SHIFT); 3336 else 3337 numentries <<= (PAGE_SHIFT - scale); 3338 3339 /* Make sure we've got at least a 0-order allocation.. */ 3340 if (unlikely((numentries * bucketsize) < PAGE_SIZE)) 3341 numentries = PAGE_SIZE / bucketsize; 3342 } 3343 numentries = roundup_pow_of_two(numentries); 3344 3345 /* limit allocation size to 1/16 total memory by default */ 3346 if (max == 0) { 3347 max = ((unsigned long long)nr_all_pages << PAGE_SHIFT) >> 4; 3348 do_div(max, bucketsize); 3349 } 3350 3351 if (numentries > max) 3352 numentries = max; 3353 3354 log2qty = ilog2(numentries); 3355 3356 do { 3357 size = bucketsize << log2qty; 3358 if (flags & HASH_EARLY) 3359 table = alloc_bootmem(size); 3360 else if (hashdist) 3361 table = __vmalloc(size, GFP_ATOMIC, PAGE_KERNEL); 3362 else { 3363 unsigned long order; 3364 for (order = 0; ((1UL << order) << PAGE_SHIFT) < size; order++) 3365 ; 3366 table = (void*) __get_free_pages(GFP_ATOMIC, order); 3367 } 3368 } while (!table && size > PAGE_SIZE && --log2qty); 3369 3370 if (!table) 3371 panic("Failed to allocate %s hash table\n", tablename); 3372 3373 printk("%s hash table entries: %d (order: %d, %lu bytes)\n", 3374 tablename, 3375 (1U << log2qty), 3376 ilog2(size) - PAGE_SHIFT, 3377 size); 3378 3379 if (_hash_shift) 3380 *_hash_shift = log2qty; 3381 if (_hash_mask) 3382 *_hash_mask = (1 << log2qty) - 1; 3383 3384 return table; 3385} 3386 3387#ifdef CONFIG_OUT_OF_LINE_PFN_TO_PAGE 3388struct page *pfn_to_page(unsigned long pfn) 3389{ 3390 return __pfn_to_page(pfn); 3391} 3392unsigned long page_to_pfn(struct page *page) 3393{ 3394 return __page_to_pfn(page); 3395} 3396EXPORT_SYMBOL(pfn_to_page); 3397EXPORT_SYMBOL(page_to_pfn); 3398#endif /* CONFIG_OUT_OF_LINE_PFN_TO_PAGE */ 3399 3400 3401