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