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