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