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