61290ea721c8b778adb89c2e1af24a1f1a7154d3
[linux-2.6.git] / mm / page_alloc.c
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/jiffies.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/oom.h>
32 #include <linux/notifier.h>
33 #include <linux/topology.h>
34 #include <linux/sysctl.h>
35 #include <linux/cpu.h>
36 #include <linux/cpuset.h>
37 #include <linux/memory_hotplug.h>
38 #include <linux/nodemask.h>
39 #include <linux/vmalloc.h>
40 #include <linux/mempolicy.h>
41 #include <linux/stop_machine.h>
42 #include <linux/sort.h>
43 #include <linux/pfn.h>
44 #include <linux/backing-dev.h>
45 #include <linux/fault-inject.h>
46 #include <linux/page-isolation.h>
47 #include <linux/page_cgroup.h>
48 #include <linux/debugobjects.h>
49 #include <linux/kmemleak.h>
50
51 #include <asm/tlbflush.h>
52 #include <asm/div64.h>
53 #include "internal.h"
54
55 /*
56  * Array of node states.
57  */
58 nodemask_t node_states[NR_NODE_STATES] __read_mostly = {
59         [N_POSSIBLE] = NODE_MASK_ALL,
60         [N_ONLINE] = { { [0] = 1UL } },
61 #ifndef CONFIG_NUMA
62         [N_NORMAL_MEMORY] = { { [0] = 1UL } },
63 #ifdef CONFIG_HIGHMEM
64         [N_HIGH_MEMORY] = { { [0] = 1UL } },
65 #endif
66         [N_CPU] = { { [0] = 1UL } },
67 #endif  /* NUMA */
68 };
69 EXPORT_SYMBOL(node_states);
70
71 unsigned long totalram_pages __read_mostly;
72 unsigned long totalreserve_pages __read_mostly;
73 unsigned long highest_memmap_pfn __read_mostly;
74 int percpu_pagelist_fraction;
75
76 #ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
77 int pageblock_order __read_mostly;
78 #endif
79
80 static void __free_pages_ok(struct page *page, unsigned int order);
81
82 /*
83  * results with 256, 32 in the lowmem_reserve sysctl:
84  *      1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
85  *      1G machine -> (16M dma, 784M normal, 224M high)
86  *      NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
87  *      HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
88  *      HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA
89  *
90  * TBD: should special case ZONE_DMA32 machines here - in those we normally
91  * don't need any ZONE_NORMAL reservation
92  */
93 int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = {
94 #ifdef CONFIG_ZONE_DMA
95          256,
96 #endif
97 #ifdef CONFIG_ZONE_DMA32
98          256,
99 #endif
100 #ifdef CONFIG_HIGHMEM
101          32,
102 #endif
103          32,
104 };
105
106 EXPORT_SYMBOL(totalram_pages);
107
108 static char * const zone_names[MAX_NR_ZONES] = {
109 #ifdef CONFIG_ZONE_DMA
110          "DMA",
111 #endif
112 #ifdef CONFIG_ZONE_DMA32
113          "DMA32",
114 #endif
115          "Normal",
116 #ifdef CONFIG_HIGHMEM
117          "HighMem",
118 #endif
119          "Movable",
120 };
121
122 int min_free_kbytes = 1024;
123
124 unsigned long __meminitdata nr_kernel_pages;
125 unsigned long __meminitdata nr_all_pages;
126 static unsigned long __meminitdata dma_reserve;
127
128 #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
129   /*
130    * MAX_ACTIVE_REGIONS determines the maximum number of distinct
131    * ranges of memory (RAM) that may be registered with add_active_range().
132    * Ranges passed to add_active_range() will be merged if possible
133    * so the number of times add_active_range() can be called is
134    * related to the number of nodes and the number of holes
135    */
136   #ifdef CONFIG_MAX_ACTIVE_REGIONS
137     /* Allow an architecture to set MAX_ACTIVE_REGIONS to save memory */
138     #define MAX_ACTIVE_REGIONS CONFIG_MAX_ACTIVE_REGIONS
139   #else
140     #if MAX_NUMNODES >= 32
141       /* If there can be many nodes, allow up to 50 holes per node */
142       #define MAX_ACTIVE_REGIONS (MAX_NUMNODES*50)
143     #else
144       /* By default, allow up to 256 distinct regions */
145       #define MAX_ACTIVE_REGIONS 256
146     #endif
147   #endif
148
149   static struct node_active_region __meminitdata early_node_map[MAX_ACTIVE_REGIONS];
150   static int __meminitdata nr_nodemap_entries;
151   static unsigned long __meminitdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES];
152   static unsigned long __meminitdata arch_zone_highest_possible_pfn[MAX_NR_ZONES];
153   static unsigned long __initdata required_kernelcore;
154   static unsigned long __initdata required_movablecore;
155   static unsigned long __meminitdata zone_movable_pfn[MAX_NUMNODES];
156
157   /* movable_zone is the "real" zone pages in ZONE_MOVABLE are taken from */
158   int movable_zone;
159   EXPORT_SYMBOL(movable_zone);
160 #endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
161
162 #if MAX_NUMNODES > 1
163 int nr_node_ids __read_mostly = MAX_NUMNODES;
164 int nr_online_nodes __read_mostly = 1;
165 EXPORT_SYMBOL(nr_node_ids);
166 EXPORT_SYMBOL(nr_online_nodes);
167 #endif
168
169 int page_group_by_mobility_disabled __read_mostly;
170
171 static void set_pageblock_migratetype(struct page *page, int migratetype)
172 {
173
174         if (unlikely(page_group_by_mobility_disabled))
175                 migratetype = MIGRATE_UNMOVABLE;
176
177         set_pageblock_flags_group(page, (unsigned long)migratetype,
178                                         PB_migrate, PB_migrate_end);
179 }
180
181 #ifdef CONFIG_DEBUG_VM
182 static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
183 {
184         int ret = 0;
185         unsigned seq;
186         unsigned long pfn = page_to_pfn(page);
187
188         do {
189                 seq = zone_span_seqbegin(zone);
190                 if (pfn >= zone->zone_start_pfn + zone->spanned_pages)
191                         ret = 1;
192                 else if (pfn < zone->zone_start_pfn)
193                         ret = 1;
194         } while (zone_span_seqretry(zone, seq));
195
196         return ret;
197 }
198
199 static int page_is_consistent(struct zone *zone, struct page *page)
200 {
201         if (!pfn_valid_within(page_to_pfn(page)))
202                 return 0;
203         if (zone != page_zone(page))
204                 return 0;
205
206         return 1;
207 }
208 /*
209  * Temporary debugging check for pages not lying within a given zone.
210  */
211 static int bad_range(struct zone *zone, struct page *page)
212 {
213         if (page_outside_zone_boundaries(zone, page))
214                 return 1;
215         if (!page_is_consistent(zone, page))
216                 return 1;
217
218         return 0;
219 }
220 #else
221 static inline int bad_range(struct zone *zone, struct page *page)
222 {
223         return 0;
224 }
225 #endif
226
227 static void bad_page(struct page *page)
228 {
229         static unsigned long resume;
230         static unsigned long nr_shown;
231         static unsigned long nr_unshown;
232
233         /*
234          * Allow a burst of 60 reports, then keep quiet for that minute;
235          * or allow a steady drip of one report per second.
236          */
237         if (nr_shown == 60) {
238                 if (time_before(jiffies, resume)) {
239                         nr_unshown++;
240                         goto out;
241                 }
242                 if (nr_unshown) {
243                         printk(KERN_ALERT
244                               "BUG: Bad page state: %lu messages suppressed\n",
245                                 nr_unshown);
246                         nr_unshown = 0;
247                 }
248                 nr_shown = 0;
249         }
250         if (nr_shown++ == 0)
251                 resume = jiffies + 60 * HZ;
252
253         printk(KERN_ALERT "BUG: Bad page state in process %s  pfn:%05lx\n",
254                 current->comm, page_to_pfn(page));
255         printk(KERN_ALERT
256                 "page:%p flags:%p count:%d mapcount:%d mapping:%p index:%lx\n",
257                 page, (void *)page->flags, page_count(page),
258                 page_mapcount(page), page->mapping, page->index);
259
260         dump_stack();
261 out:
262         /* Leave bad fields for debug, except PageBuddy could make trouble */
263         __ClearPageBuddy(page);
264         add_taint(TAINT_BAD_PAGE);
265 }
266
267 /*
268  * Higher-order pages are called "compound pages".  They are structured thusly:
269  *
270  * The first PAGE_SIZE page is called the "head page".
271  *
272  * The remaining PAGE_SIZE pages are called "tail pages".
273  *
274  * All pages have PG_compound set.  All pages have their ->private pointing at
275  * the head page (even the head page has this).
276  *
277  * The first tail page's ->lru.next holds the address of the compound page's
278  * put_page() function.  Its ->lru.prev holds the order of allocation.
279  * This usage means that zero-order pages may not be compound.
280  */
281
282 static void free_compound_page(struct page *page)
283 {
284         __free_pages_ok(page, compound_order(page));
285 }
286
287 void prep_compound_page(struct page *page, unsigned long order)
288 {
289         int i;
290         int nr_pages = 1 << order;
291
292         set_compound_page_dtor(page, free_compound_page);
293         set_compound_order(page, order);
294         __SetPageHead(page);
295         for (i = 1; i < nr_pages; i++) {
296                 struct page *p = page + i;
297
298                 __SetPageTail(p);
299                 p->first_page = page;
300         }
301 }
302
303 static int destroy_compound_page(struct page *page, unsigned long order)
304 {
305         int i;
306         int nr_pages = 1 << order;
307         int bad = 0;
308
309         if (unlikely(compound_order(page) != order) ||
310             unlikely(!PageHead(page))) {
311                 bad_page(page);
312                 bad++;
313         }
314
315         __ClearPageHead(page);
316
317         for (i = 1; i < nr_pages; i++) {
318                 struct page *p = page + i;
319
320                 if (unlikely(!PageTail(p) || (p->first_page != page))) {
321                         bad_page(page);
322                         bad++;
323                 }
324                 __ClearPageTail(p);
325         }
326
327         return bad;
328 }
329
330 static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags)
331 {
332         int i;
333
334         /*
335          * clear_highpage() will use KM_USER0, so it's a bug to use __GFP_ZERO
336          * and __GFP_HIGHMEM from hard or soft interrupt context.
337          */
338         VM_BUG_ON((gfp_flags & __GFP_HIGHMEM) && in_interrupt());
339         for (i = 0; i < (1 << order); i++)
340                 clear_highpage(page + i);
341 }
342
343 static inline void set_page_order(struct page *page, int order)
344 {
345         set_page_private(page, order);
346         __SetPageBuddy(page);
347 }
348
349 static inline void rmv_page_order(struct page *page)
350 {
351         __ClearPageBuddy(page);
352         set_page_private(page, 0);
353 }
354
355 /*
356  * Locate the struct page for both the matching buddy in our
357  * pair (buddy1) and the combined O(n+1) page they form (page).
358  *
359  * 1) Any buddy B1 will have an order O twin B2 which satisfies
360  * the following equation:
361  *     B2 = B1 ^ (1 << O)
362  * For example, if the starting buddy (buddy2) is #8 its order
363  * 1 buddy is #10:
364  *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
365  *
366  * 2) Any buddy B will have an order O+1 parent P which
367  * satisfies the following equation:
368  *     P = B & ~(1 << O)
369  *
370  * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
371  */
372 static inline struct page *
373 __page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
374 {
375         unsigned long buddy_idx = page_idx ^ (1 << order);
376
377         return page + (buddy_idx - page_idx);
378 }
379
380 static inline unsigned long
381 __find_combined_index(unsigned long page_idx, unsigned int order)
382 {
383         return (page_idx & ~(1 << order));
384 }
385
386 /*
387  * This function checks whether a page is free && is the buddy
388  * we can do coalesce a page and its buddy if
389  * (a) the buddy is not in a hole &&
390  * (b) the buddy is in the buddy system &&
391  * (c) a page and its buddy have the same order &&
392  * (d) a page and its buddy are in the same zone.
393  *
394  * For recording whether a page is in the buddy system, we use PG_buddy.
395  * Setting, clearing, and testing PG_buddy is serialized by zone->lock.
396  *
397  * For recording page's order, we use page_private(page).
398  */
399 static inline int page_is_buddy(struct page *page, struct page *buddy,
400                                                                 int order)
401 {
402         if (!pfn_valid_within(page_to_pfn(buddy)))
403                 return 0;
404
405         if (page_zone_id(page) != page_zone_id(buddy))
406                 return 0;
407
408         if (PageBuddy(buddy) && page_order(buddy) == order) {
409                 VM_BUG_ON(page_count(buddy) != 0);
410                 return 1;
411         }
412         return 0;
413 }
414
415 /*
416  * Freeing function for a buddy system allocator.
417  *
418  * The concept of a buddy system is to maintain direct-mapped table
419  * (containing bit values) for memory blocks of various "orders".
420  * The bottom level table contains the map for the smallest allocatable
421  * units of memory (here, pages), and each level above it describes
422  * pairs of units from the levels below, hence, "buddies".
423  * At a high level, all that happens here is marking the table entry
424  * at the bottom level available, and propagating the changes upward
425  * as necessary, plus some accounting needed to play nicely with other
426  * parts of the VM system.
427  * At each level, we keep a list of pages, which are heads of continuous
428  * free pages of length of (1 << order) and marked with PG_buddy. Page's
429  * order is recorded in page_private(page) field.
430  * So when we are allocating or freeing one, we can derive the state of the
431  * other.  That is, if we allocate a small block, and both were   
432  * free, the remainder of the region must be split into blocks.   
433  * If a block is freed, and its buddy is also free, then this
434  * triggers coalescing into a block of larger size.            
435  *
436  * -- wli
437  */
438
439 static inline void __free_one_page(struct page *page,
440                 struct zone *zone, unsigned int order,
441                 int migratetype)
442 {
443         unsigned long page_idx;
444
445         if (unlikely(PageCompound(page)))
446                 if (unlikely(destroy_compound_page(page, order)))
447                         return;
448
449         VM_BUG_ON(migratetype == -1);
450
451         page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
452
453         VM_BUG_ON(page_idx & ((1 << order) - 1));
454         VM_BUG_ON(bad_range(zone, page));
455
456         while (order < MAX_ORDER-1) {
457                 unsigned long combined_idx;
458                 struct page *buddy;
459
460                 buddy = __page_find_buddy(page, page_idx, order);
461                 if (!page_is_buddy(page, buddy, order))
462                         break;
463
464                 /* Our buddy is free, merge with it and move up one order. */
465                 list_del(&buddy->lru);
466                 zone->free_area[order].nr_free--;
467                 rmv_page_order(buddy);
468                 combined_idx = __find_combined_index(page_idx, order);
469                 page = page + (combined_idx - page_idx);
470                 page_idx = combined_idx;
471                 order++;
472         }
473         set_page_order(page, order);
474         list_add(&page->lru,
475                 &zone->free_area[order].free_list[migratetype]);
476         zone->free_area[order].nr_free++;
477 }
478
479 #ifdef CONFIG_HAVE_MLOCKED_PAGE_BIT
480 /*
481  * free_page_mlock() -- clean up attempts to free and mlocked() page.
482  * Page should not be on lru, so no need to fix that up.
483  * free_pages_check() will verify...
484  */
485 static inline void free_page_mlock(struct page *page)
486 {
487         __ClearPageMlocked(page);
488         __dec_zone_page_state(page, NR_MLOCK);
489         __count_vm_event(UNEVICTABLE_MLOCKFREED);
490 }
491 #else
492 static void free_page_mlock(struct page *page) { }
493 #endif
494
495 static inline int free_pages_check(struct page *page)
496 {
497         if (unlikely(page_mapcount(page) |
498                 (page->mapping != NULL)  |
499                 (atomic_read(&page->_count) != 0) |
500                 (page->flags & PAGE_FLAGS_CHECK_AT_FREE))) {
501                 bad_page(page);
502                 return 1;
503         }
504         if (page->flags & PAGE_FLAGS_CHECK_AT_PREP)
505                 page->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
506         return 0;
507 }
508
509 /*
510  * Frees a list of pages. 
511  * Assumes all pages on list are in same zone, and of same order.
512  * count is the number of pages to free.
513  *
514  * If the zone was previously in an "all pages pinned" state then look to
515  * see if this freeing clears that state.
516  *
517  * And clear the zone's pages_scanned counter, to hold off the "all pages are
518  * pinned" detection logic.
519  */
520 static void free_pages_bulk(struct zone *zone, int count,
521                                         struct list_head *list, int order)
522 {
523         spin_lock(&zone->lock);
524         zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);
525         zone->pages_scanned = 0;
526
527         __mod_zone_page_state(zone, NR_FREE_PAGES, count << order);
528         while (count--) {
529                 struct page *page;
530
531                 VM_BUG_ON(list_empty(list));
532                 page = list_entry(list->prev, struct page, lru);
533                 /* have to delete it as __free_one_page list manipulates */
534                 list_del(&page->lru);
535                 __free_one_page(page, zone, order, page_private(page));
536         }
537         spin_unlock(&zone->lock);
538 }
539
540 static void free_one_page(struct zone *zone, struct page *page, int order,
541                                 int migratetype)
542 {
543         spin_lock(&zone->lock);
544         zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);
545         zone->pages_scanned = 0;
546
547         __mod_zone_page_state(zone, NR_FREE_PAGES, 1 << order);
548         __free_one_page(page, zone, order, migratetype);
549         spin_unlock(&zone->lock);
550 }
551
552 static void __free_pages_ok(struct page *page, unsigned int order)
553 {
554         unsigned long flags;
555         int i;
556         int bad = 0;
557         int clearMlocked = PageMlocked(page);
558
559         for (i = 0 ; i < (1 << order) ; ++i)
560                 bad += free_pages_check(page + i);
561         if (bad)
562                 return;
563
564         if (!PageHighMem(page)) {
565                 debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);
566                 debug_check_no_obj_freed(page_address(page),
567                                            PAGE_SIZE << order);
568         }
569         arch_free_page(page, order);
570         kernel_map_pages(page, 1 << order, 0);
571
572         local_irq_save(flags);
573         if (unlikely(clearMlocked))
574                 free_page_mlock(page);
575         __count_vm_events(PGFREE, 1 << order);
576         free_one_page(page_zone(page), page, order,
577                                         get_pageblock_migratetype(page));
578         local_irq_restore(flags);
579 }
580
581 /*
582  * permit the bootmem allocator to evade page validation on high-order frees
583  */
584 void __meminit __free_pages_bootmem(struct page *page, unsigned int order)
585 {
586         if (order == 0) {
587                 __ClearPageReserved(page);
588                 set_page_count(page, 0);
589                 set_page_refcounted(page);
590                 __free_page(page);
591         } else {
592                 int loop;
593
594                 prefetchw(page);
595                 for (loop = 0; loop < BITS_PER_LONG; loop++) {
596                         struct page *p = &page[loop];
597
598                         if (loop + 1 < BITS_PER_LONG)
599                                 prefetchw(p + 1);
600                         __ClearPageReserved(p);
601                         set_page_count(p, 0);
602                 }
603
604                 set_page_refcounted(page);
605                 __free_pages(page, order);
606         }
607 }
608
609
610 /*
611  * The order of subdivision here is critical for the IO subsystem.
612  * Please do not alter this order without good reasons and regression
613  * testing. Specifically, as large blocks of memory are subdivided,
614  * the order in which smaller blocks are delivered depends on the order
615  * they're subdivided in this function. This is the primary factor
616  * influencing the order in which pages are delivered to the IO
617  * subsystem according to empirical testing, and this is also justified
618  * by considering the behavior of a buddy system containing a single
619  * large block of memory acted on by a series of small allocations.
620  * This behavior is a critical factor in sglist merging's success.
621  *
622  * -- wli
623  */
624 static inline void expand(struct zone *zone, struct page *page,
625         int low, int high, struct free_area *area,
626         int migratetype)
627 {
628         unsigned long size = 1 << high;
629
630         while (high > low) {
631                 area--;
632                 high--;
633                 size >>= 1;
634                 VM_BUG_ON(bad_range(zone, &page[size]));
635                 list_add(&page[size].lru, &area->free_list[migratetype]);
636                 area->nr_free++;
637                 set_page_order(&page[size], high);
638         }
639 }
640
641 /*
642  * This page is about to be returned from the page allocator
643  */
644 static int prep_new_page(struct page *page, int order, gfp_t gfp_flags)
645 {
646         if (unlikely(page_mapcount(page) |
647                 (page->mapping != NULL)  |
648                 (atomic_read(&page->_count) != 0)  |
649                 (page->flags & PAGE_FLAGS_CHECK_AT_PREP))) {
650                 bad_page(page);
651                 return 1;
652         }
653
654         set_page_private(page, 0);
655         set_page_refcounted(page);
656
657         arch_alloc_page(page, order);
658         kernel_map_pages(page, 1 << order, 1);
659
660         if (gfp_flags & __GFP_ZERO)
661                 prep_zero_page(page, order, gfp_flags);
662
663         if (order && (gfp_flags & __GFP_COMP))
664                 prep_compound_page(page, order);
665
666         return 0;
667 }
668
669 /*
670  * Go through the free lists for the given migratetype and remove
671  * the smallest available page from the freelists
672  */
673 static inline
674 struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
675                                                 int migratetype)
676 {
677         unsigned int current_order;
678         struct free_area * area;
679         struct page *page;
680
681         /* Find a page of the appropriate size in the preferred list */
682         for (current_order = order; current_order < MAX_ORDER; ++current_order) {
683                 area = &(zone->free_area[current_order]);
684                 if (list_empty(&area->free_list[migratetype]))
685                         continue;
686
687                 page = list_entry(area->free_list[migratetype].next,
688                                                         struct page, lru);
689                 list_del(&page->lru);
690                 rmv_page_order(page);
691                 area->nr_free--;
692                 expand(zone, page, order, current_order, area, migratetype);
693                 return page;
694         }
695
696         return NULL;
697 }
698
699
700 /*
701  * This array describes the order lists are fallen back to when
702  * the free lists for the desirable migrate type are depleted
703  */
704 static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {
705         [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },
706         [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },
707         [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
708         [MIGRATE_RESERVE]     = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, /* Never used */
709 };
710
711 /*
712  * Move the free pages in a range to the free lists of the requested type.
713  * Note that start_page and end_pages are not aligned on a pageblock
714  * boundary. If alignment is required, use move_freepages_block()
715  */
716 static int move_freepages(struct zone *zone,
717                           struct page *start_page, struct page *end_page,
718                           int migratetype)
719 {
720         struct page *page;
721         unsigned long order;
722         int pages_moved = 0;
723
724 #ifndef CONFIG_HOLES_IN_ZONE
725         /*
726          * page_zone is not safe to call in this context when
727          * CONFIG_HOLES_IN_ZONE is set. This bug check is probably redundant
728          * anyway as we check zone boundaries in move_freepages_block().
729          * Remove at a later date when no bug reports exist related to
730          * grouping pages by mobility
731          */
732         BUG_ON(page_zone(start_page) != page_zone(end_page));
733 #endif
734
735         for (page = start_page; page <= end_page;) {
736                 /* Make sure we are not inadvertently changing nodes */
737                 VM_BUG_ON(page_to_nid(page) != zone_to_nid(zone));
738
739                 if (!pfn_valid_within(page_to_pfn(page))) {
740                         page++;
741                         continue;
742                 }
743
744                 if (!PageBuddy(page)) {
745                         page++;
746                         continue;
747                 }
748
749                 order = page_order(page);
750                 list_del(&page->lru);
751                 list_add(&page->lru,
752                         &zone->free_area[order].free_list[migratetype]);
753                 page += 1 << order;
754                 pages_moved += 1 << order;
755         }
756
757         return pages_moved;
758 }
759
760 static int move_freepages_block(struct zone *zone, struct page *page,
761                                 int migratetype)
762 {
763         unsigned long start_pfn, end_pfn;
764         struct page *start_page, *end_page;
765
766         start_pfn = page_to_pfn(page);
767         start_pfn = start_pfn & ~(pageblock_nr_pages-1);
768         start_page = pfn_to_page(start_pfn);
769         end_page = start_page + pageblock_nr_pages - 1;
770         end_pfn = start_pfn + pageblock_nr_pages - 1;
771
772         /* Do not cross zone boundaries */
773         if (start_pfn < zone->zone_start_pfn)
774                 start_page = page;
775         if (end_pfn >= zone->zone_start_pfn + zone->spanned_pages)
776                 return 0;
777
778         return move_freepages(zone, start_page, end_page, migratetype);
779 }
780
781 /* Remove an element from the buddy allocator from the fallback list */
782 static inline struct page *
783 __rmqueue_fallback(struct zone *zone, int order, int start_migratetype)
784 {
785         struct free_area * area;
786         int current_order;
787         struct page *page;
788         int migratetype, i;
789
790         /* Find the largest possible block of pages in the other list */
791         for (current_order = MAX_ORDER-1; current_order >= order;
792                                                 --current_order) {
793                 for (i = 0; i < MIGRATE_TYPES - 1; i++) {
794                         migratetype = fallbacks[start_migratetype][i];
795
796                         /* MIGRATE_RESERVE handled later if necessary */
797                         if (migratetype == MIGRATE_RESERVE)
798                                 continue;
799
800                         area = &(zone->free_area[current_order]);
801                         if (list_empty(&area->free_list[migratetype]))
802                                 continue;
803
804                         page = list_entry(area->free_list[migratetype].next,
805                                         struct page, lru);
806                         area->nr_free--;
807
808                         /*
809                          * If breaking a large block of pages, move all free
810                          * pages to the preferred allocation list. If falling
811                          * back for a reclaimable kernel allocation, be more
812                          * agressive about taking ownership of free pages
813                          */
814                         if (unlikely(current_order >= (pageblock_order >> 1)) ||
815                                         start_migratetype == MIGRATE_RECLAIMABLE) {
816                                 unsigned long pages;
817                                 pages = move_freepages_block(zone, page,
818                                                                 start_migratetype);
819
820                                 /* Claim the whole block if over half of it is free */
821                                 if (pages >= (1 << (pageblock_order-1)))
822                                         set_pageblock_migratetype(page,
823                                                                 start_migratetype);
824
825                                 migratetype = start_migratetype;
826                         }
827
828                         /* Remove the page from the freelists */
829                         list_del(&page->lru);
830                         rmv_page_order(page);
831
832                         if (current_order == pageblock_order)
833                                 set_pageblock_migratetype(page,
834                                                         start_migratetype);
835
836                         expand(zone, page, order, current_order, area, migratetype);
837                         return page;
838                 }
839         }
840
841         return NULL;
842 }
843
844 /*
845  * Do the hard work of removing an element from the buddy allocator.
846  * Call me with the zone->lock already held.
847  */
848 static struct page *__rmqueue(struct zone *zone, unsigned int order,
849                                                 int migratetype)
850 {
851         struct page *page;
852
853 retry_reserve:
854         page = __rmqueue_smallest(zone, order, migratetype);
855
856         if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
857                 page = __rmqueue_fallback(zone, order, migratetype);
858
859                 /*
860                  * Use MIGRATE_RESERVE rather than fail an allocation. goto
861                  * is used because __rmqueue_smallest is an inline function
862                  * and we want just one call site
863                  */
864                 if (!page) {
865                         migratetype = MIGRATE_RESERVE;
866                         goto retry_reserve;
867                 }
868         }
869
870         return page;
871 }
872
873 /* 
874  * Obtain a specified number of elements from the buddy allocator, all under
875  * a single hold of the lock, for efficiency.  Add them to the supplied list.
876  * Returns the number of new pages which were placed at *list.
877  */
878 static int rmqueue_bulk(struct zone *zone, unsigned int order, 
879                         unsigned long count, struct list_head *list,
880                         int migratetype)
881 {
882         int i;
883         
884         spin_lock(&zone->lock);
885         for (i = 0; i < count; ++i) {
886                 struct page *page = __rmqueue(zone, order, migratetype);
887                 if (unlikely(page == NULL))
888                         break;
889
890                 /*
891                  * Split buddy pages returned by expand() are received here
892                  * in physical page order. The page is added to the callers and
893                  * list and the list head then moves forward. From the callers
894                  * perspective, the linked list is ordered by page number in
895                  * some conditions. This is useful for IO devices that can
896                  * merge IO requests if the physical pages are ordered
897                  * properly.
898                  */
899                 list_add(&page->lru, list);
900                 set_page_private(page, migratetype);
901                 list = &page->lru;
902         }
903         __mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
904         spin_unlock(&zone->lock);
905         return i;
906 }
907
908 #ifdef CONFIG_NUMA
909 /*
910  * Called from the vmstat counter updater to drain pagesets of this
911  * currently executing processor on remote nodes after they have
912  * expired.
913  *
914  * Note that this function must be called with the thread pinned to
915  * a single processor.
916  */
917 void drain_zone_pages(struct zone *zone, struct per_cpu_pages *pcp)
918 {
919         unsigned long flags;
920         int to_drain;
921
922         local_irq_save(flags);
923         if (pcp->count >= pcp->batch)
924                 to_drain = pcp->batch;
925         else
926                 to_drain = pcp->count;
927         free_pages_bulk(zone, to_drain, &pcp->list, 0);
928         pcp->count -= to_drain;
929         local_irq_restore(flags);
930 }
931 #endif
932
933 /*
934  * Drain pages of the indicated processor.
935  *
936  * The processor must either be the current processor and the
937  * thread pinned to the current processor or a processor that
938  * is not online.
939  */
940 static void drain_pages(unsigned int cpu)
941 {
942         unsigned long flags;
943         struct zone *zone;
944
945         for_each_populated_zone(zone) {
946                 struct per_cpu_pageset *pset;
947                 struct per_cpu_pages *pcp;
948
949                 pset = zone_pcp(zone, cpu);
950
951                 pcp = &pset->pcp;
952                 local_irq_save(flags);
953                 free_pages_bulk(zone, pcp->count, &pcp->list, 0);
954                 pcp->count = 0;
955                 local_irq_restore(flags);
956         }
957 }
958
959 /*
960  * Spill all of this CPU's per-cpu pages back into the buddy allocator.
961  */
962 void drain_local_pages(void *arg)
963 {
964         drain_pages(smp_processor_id());
965 }
966
967 /*
968  * Spill all the per-cpu pages from all CPUs back into the buddy allocator
969  */
970 void drain_all_pages(void)
971 {
972         on_each_cpu(drain_local_pages, NULL, 1);
973 }
974
975 #ifdef CONFIG_HIBERNATION
976
977 void mark_free_pages(struct zone *zone)
978 {
979         unsigned long pfn, max_zone_pfn;
980         unsigned long flags;
981         int order, t;
982         struct list_head *curr;
983
984         if (!zone->spanned_pages)
985                 return;
986
987         spin_lock_irqsave(&zone->lock, flags);
988
989         max_zone_pfn = zone->zone_start_pfn + zone->spanned_pages;
990         for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
991                 if (pfn_valid(pfn)) {
992                         struct page *page = pfn_to_page(pfn);
993
994                         if (!swsusp_page_is_forbidden(page))
995                                 swsusp_unset_page_free(page);
996                 }
997
998         for_each_migratetype_order(order, t) {
999                 list_for_each(curr, &zone->free_area[order].free_list[t]) {
1000                         unsigned long i;
1001
1002                         pfn = page_to_pfn(list_entry(curr, struct page, lru));
1003                         for (i = 0; i < (1UL << order); i++)
1004                                 swsusp_set_page_free(pfn_to_page(pfn + i));
1005                 }
1006         }
1007         spin_unlock_irqrestore(&zone->lock, flags);
1008 }
1009 #endif /* CONFIG_PM */
1010
1011 /*
1012  * Free a 0-order page
1013  */
1014 static void free_hot_cold_page(struct page *page, int cold)
1015 {
1016         struct zone *zone = page_zone(page);
1017         struct per_cpu_pages *pcp;
1018         unsigned long flags;
1019         int clearMlocked = PageMlocked(page);
1020
1021         if (PageAnon(page))
1022                 page->mapping = NULL;
1023         if (free_pages_check(page))
1024                 return;
1025
1026         if (!PageHighMem(page)) {
1027                 debug_check_no_locks_freed(page_address(page), PAGE_SIZE);
1028                 debug_check_no_obj_freed(page_address(page), PAGE_SIZE);
1029         }
1030         arch_free_page(page, 0);
1031         kernel_map_pages(page, 1, 0);
1032
1033         pcp = &zone_pcp(zone, get_cpu())->pcp;
1034         set_page_private(page, get_pageblock_migratetype(page));
1035         local_irq_save(flags);
1036         if (unlikely(clearMlocked))
1037                 free_page_mlock(page);
1038         __count_vm_event(PGFREE);
1039
1040         if (cold)
1041                 list_add_tail(&page->lru, &pcp->list);
1042         else
1043                 list_add(&page->lru, &pcp->list);
1044         pcp->count++;
1045         if (pcp->count >= pcp->high) {
1046                 free_pages_bulk(zone, pcp->batch, &pcp->list, 0);
1047                 pcp->count -= pcp->batch;
1048         }
1049         local_irq_restore(flags);
1050         put_cpu();
1051 }
1052
1053 void free_hot_page(struct page *page)
1054 {
1055         free_hot_cold_page(page, 0);
1056 }
1057         
1058 void free_cold_page(struct page *page)
1059 {
1060         free_hot_cold_page(page, 1);
1061 }
1062
1063 /*
1064  * split_page takes a non-compound higher-order page, and splits it into
1065  * n (1<<order) sub-pages: page[0..n]
1066  * Each sub-page must be freed individually.
1067  *
1068  * Note: this is probably too low level an operation for use in drivers.
1069  * Please consult with lkml before using this in your driver.
1070  */
1071 void split_page(struct page *page, unsigned int order)
1072 {
1073         int i;
1074
1075         VM_BUG_ON(PageCompound(page));
1076         VM_BUG_ON(!page_count(page));
1077         for (i = 1; i < (1 << order); i++)
1078                 set_page_refcounted(page + i);
1079 }
1080
1081 /*
1082  * Really, prep_compound_page() should be called from __rmqueue_bulk().  But
1083  * we cheat by calling it from here, in the order > 0 path.  Saves a branch
1084  * or two.
1085  */
1086 static inline
1087 struct page *buffered_rmqueue(struct zone *preferred_zone,
1088                         struct zone *zone, int order, gfp_t gfp_flags,
1089                         int migratetype)
1090 {
1091         unsigned long flags;
1092         struct page *page;
1093         int cold = !!(gfp_flags & __GFP_COLD);
1094         int cpu;
1095
1096 again:
1097         cpu  = get_cpu();
1098         if (likely(order == 0)) {
1099                 struct per_cpu_pages *pcp;
1100
1101                 pcp = &zone_pcp(zone, cpu)->pcp;
1102                 local_irq_save(flags);
1103                 if (!pcp->count) {
1104                         pcp->count = rmqueue_bulk(zone, 0,
1105                                         pcp->batch, &pcp->list, migratetype);
1106                         if (unlikely(!pcp->count))
1107                                 goto failed;
1108                 }
1109
1110                 /* Find a page of the appropriate migrate type */
1111                 if (cold) {
1112                         list_for_each_entry_reverse(page, &pcp->list, lru)
1113                                 if (page_private(page) == migratetype)
1114                                         break;
1115                 } else {
1116                         list_for_each_entry(page, &pcp->list, lru)
1117                                 if (page_private(page) == migratetype)
1118                                         break;
1119                 }
1120
1121                 /* Allocate more to the pcp list if necessary */
1122                 if (unlikely(&page->lru == &pcp->list)) {
1123                         pcp->count += rmqueue_bulk(zone, 0,
1124                                         pcp->batch, &pcp->list, migratetype);
1125                         page = list_entry(pcp->list.next, struct page, lru);
1126                 }
1127
1128                 list_del(&page->lru);
1129                 pcp->count--;
1130         } else {
1131                 if (unlikely(gfp_flags & __GFP_NOFAIL)) {
1132                         /*
1133                          * __GFP_NOFAIL is not to be used in new code.
1134                          *
1135                          * All __GFP_NOFAIL callers should be fixed so that they
1136                          * properly detect and handle allocation failures.
1137                          *
1138                          * We most definitely don't want callers attempting to
1139                          * allocate greater than single-page units with
1140                          * __GFP_NOFAIL.
1141                          */
1142                         WARN_ON_ONCE(order > 0);
1143                 }
1144                 spin_lock_irqsave(&zone->lock, flags);
1145                 page = __rmqueue(zone, order, migratetype);
1146                 __mod_zone_page_state(zone, NR_FREE_PAGES, -(1 << order));
1147                 spin_unlock(&zone->lock);
1148                 if (!page)
1149                         goto failed;
1150         }
1151
1152         __count_zone_vm_events(PGALLOC, zone, 1 << order);
1153         zone_statistics(preferred_zone, zone);
1154         local_irq_restore(flags);
1155         put_cpu();
1156
1157         VM_BUG_ON(bad_range(zone, page));
1158         if (prep_new_page(page, order, gfp_flags))
1159                 goto again;
1160         return page;
1161
1162 failed:
1163         local_irq_restore(flags);
1164         put_cpu();
1165         return NULL;
1166 }
1167
1168 /* The ALLOC_WMARK bits are used as an index to zone->watermark */
1169 #define ALLOC_WMARK_MIN         WMARK_MIN
1170 #define ALLOC_WMARK_LOW         WMARK_LOW
1171 #define ALLOC_WMARK_HIGH        WMARK_HIGH
1172 #define ALLOC_NO_WATERMARKS     0x04 /* don't check watermarks at all */
1173
1174 /* Mask to get the watermark bits */
1175 #define ALLOC_WMARK_MASK        (ALLOC_NO_WATERMARKS-1)
1176
1177 #define ALLOC_HARDER            0x10 /* try to alloc harder */
1178 #define ALLOC_HIGH              0x20 /* __GFP_HIGH set */
1179 #define ALLOC_CPUSET            0x40 /* check for correct cpuset */
1180
1181 #ifdef CONFIG_FAIL_PAGE_ALLOC
1182
1183 static struct fail_page_alloc_attr {
1184         struct fault_attr attr;
1185
1186         u32 ignore_gfp_highmem;
1187         u32 ignore_gfp_wait;
1188         u32 min_order;
1189
1190 #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
1191
1192         struct dentry *ignore_gfp_highmem_file;
1193         struct dentry *ignore_gfp_wait_file;
1194         struct dentry *min_order_file;
1195
1196 #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
1197
1198 } fail_page_alloc = {
1199         .attr = FAULT_ATTR_INITIALIZER,
1200         .ignore_gfp_wait = 1,
1201         .ignore_gfp_highmem = 1,
1202         .min_order = 1,
1203 };
1204
1205 static int __init setup_fail_page_alloc(char *str)
1206 {
1207         return setup_fault_attr(&fail_page_alloc.attr, str);
1208 }
1209 __setup("fail_page_alloc=", setup_fail_page_alloc);
1210
1211 static int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
1212 {
1213         if (order < fail_page_alloc.min_order)
1214                 return 0;
1215         if (gfp_mask & __GFP_NOFAIL)
1216                 return 0;
1217         if (fail_page_alloc.ignore_gfp_highmem && (gfp_mask & __GFP_HIGHMEM))
1218                 return 0;
1219         if (fail_page_alloc.ignore_gfp_wait && (gfp_mask & __GFP_WAIT))
1220                 return 0;
1221
1222         return should_fail(&fail_page_alloc.attr, 1 << order);
1223 }
1224
1225 #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
1226
1227 static int __init fail_page_alloc_debugfs(void)
1228 {
1229         mode_t mode = S_IFREG | S_IRUSR | S_IWUSR;
1230         struct dentry *dir;
1231         int err;
1232
1233         err = init_fault_attr_dentries(&fail_page_alloc.attr,
1234                                        "fail_page_alloc");
1235         if (err)
1236                 return err;
1237         dir = fail_page_alloc.attr.dentries.dir;
1238
1239         fail_page_alloc.ignore_gfp_wait_file =
1240                 debugfs_create_bool("ignore-gfp-wait", mode, dir,
1241                                       &fail_page_alloc.ignore_gfp_wait);
1242
1243         fail_page_alloc.ignore_gfp_highmem_file =
1244                 debugfs_create_bool("ignore-gfp-highmem", mode, dir,
1245                                       &fail_page_alloc.ignore_gfp_highmem);
1246         fail_page_alloc.min_order_file =
1247                 debugfs_create_u32("min-order", mode, dir,
1248                                    &fail_page_alloc.min_order);
1249
1250         if (!fail_page_alloc.ignore_gfp_wait_file ||
1251             !fail_page_alloc.ignore_gfp_highmem_file ||
1252             !fail_page_alloc.min_order_file) {
1253                 err = -ENOMEM;
1254                 debugfs_remove(fail_page_alloc.ignore_gfp_wait_file);
1255                 debugfs_remove(fail_page_alloc.ignore_gfp_highmem_file);
1256                 debugfs_remove(fail_page_alloc.min_order_file);
1257                 cleanup_fault_attr_dentries(&fail_page_alloc.attr);
1258         }
1259
1260         return err;
1261 }
1262
1263 late_initcall(fail_page_alloc_debugfs);
1264
1265 #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
1266
1267 #else /* CONFIG_FAIL_PAGE_ALLOC */
1268
1269 static inline int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
1270 {
1271         return 0;
1272 }
1273
1274 #endif /* CONFIG_FAIL_PAGE_ALLOC */
1275
1276 /*
1277  * Return 1 if free pages are above 'mark'. This takes into account the order
1278  * of the allocation.
1279  */
1280 int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
1281                       int classzone_idx, int alloc_flags)
1282 {
1283         /* free_pages my go negative - that's OK */
1284         long min = mark;
1285         long free_pages = zone_page_state(z, NR_FREE_PAGES) - (1 << order) + 1;
1286         int o;
1287
1288         if (alloc_flags & ALLOC_HIGH)
1289                 min -= min / 2;
1290         if (alloc_flags & ALLOC_HARDER)
1291                 min -= min / 4;
1292
1293         if (free_pages <= min + z->lowmem_reserve[classzone_idx])
1294                 return 0;
1295         for (o = 0; o < order; o++) {
1296                 /* At the next order, this order's pages become unavailable */
1297                 free_pages -= z->free_area[o].nr_free << o;
1298
1299                 /* Require fewer higher order pages to be free */
1300                 min >>= 1;
1301
1302                 if (free_pages <= min)
1303                         return 0;
1304         }
1305         return 1;
1306 }
1307
1308 #ifdef CONFIG_NUMA
1309 /*
1310  * zlc_setup - Setup for "zonelist cache".  Uses cached zone data to
1311  * skip over zones that are not allowed by the cpuset, or that have
1312  * been recently (in last second) found to be nearly full.  See further
1313  * comments in mmzone.h.  Reduces cache footprint of zonelist scans
1314  * that have to skip over a lot of full or unallowed zones.
1315  *
1316  * If the zonelist cache is present in the passed in zonelist, then
1317  * returns a pointer to the allowed node mask (either the current
1318  * tasks mems_allowed, or node_states[N_HIGH_MEMORY].)
1319  *
1320  * If the zonelist cache is not available for this zonelist, does
1321  * nothing and returns NULL.
1322  *
1323  * If the fullzones BITMAP in the zonelist cache is stale (more than
1324  * a second since last zap'd) then we zap it out (clear its bits.)
1325  *
1326  * We hold off even calling zlc_setup, until after we've checked the
1327  * first zone in the zonelist, on the theory that most allocations will
1328  * be satisfied from that first zone, so best to examine that zone as
1329  * quickly as we can.
1330  */
1331 static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
1332 {
1333         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1334         nodemask_t *allowednodes;       /* zonelist_cache approximation */
1335
1336         zlc = zonelist->zlcache_ptr;
1337         if (!zlc)
1338                 return NULL;
1339
1340         if (time_after(jiffies, zlc->last_full_zap + HZ)) {
1341                 bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
1342                 zlc->last_full_zap = jiffies;
1343         }
1344
1345         allowednodes = !in_interrupt() && (alloc_flags & ALLOC_CPUSET) ?
1346                                         &cpuset_current_mems_allowed :
1347                                         &node_states[N_HIGH_MEMORY];
1348         return allowednodes;
1349 }
1350
1351 /*
1352  * Given 'z' scanning a zonelist, run a couple of quick checks to see
1353  * if it is worth looking at further for free memory:
1354  *  1) Check that the zone isn't thought to be full (doesn't have its
1355  *     bit set in the zonelist_cache fullzones BITMAP).
1356  *  2) Check that the zones node (obtained from the zonelist_cache
1357  *     z_to_n[] mapping) is allowed in the passed in allowednodes mask.
1358  * Return true (non-zero) if zone is worth looking at further, or
1359  * else return false (zero) if it is not.
1360  *
1361  * This check -ignores- the distinction between various watermarks,
1362  * such as GFP_HIGH, GFP_ATOMIC, PF_MEMALLOC, ...  If a zone is
1363  * found to be full for any variation of these watermarks, it will
1364  * be considered full for up to one second by all requests, unless
1365  * we are so low on memory on all allowed nodes that we are forced
1366  * into the second scan of the zonelist.
1367  *
1368  * In the second scan we ignore this zonelist cache and exactly
1369  * apply the watermarks to all zones, even it is slower to do so.
1370  * We are low on memory in the second scan, and should leave no stone
1371  * unturned looking for a free page.
1372  */
1373 static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zoneref *z,
1374                                                 nodemask_t *allowednodes)
1375 {
1376         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1377         int i;                          /* index of *z in zonelist zones */
1378         int n;                          /* node that zone *z is on */
1379
1380         zlc = zonelist->zlcache_ptr;
1381         if (!zlc)
1382                 return 1;
1383
1384         i = z - zonelist->_zonerefs;
1385         n = zlc->z_to_n[i];
1386
1387         /* This zone is worth trying if it is allowed but not full */
1388         return node_isset(n, *allowednodes) && !test_bit(i, zlc->fullzones);
1389 }
1390
1391 /*
1392  * Given 'z' scanning a zonelist, set the corresponding bit in
1393  * zlc->fullzones, so that subsequent attempts to allocate a page
1394  * from that zone don't waste time re-examining it.
1395  */
1396 static void zlc_mark_zone_full(struct zonelist *zonelist, struct zoneref *z)
1397 {
1398         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1399         int i;                          /* index of *z in zonelist zones */
1400
1401         zlc = zonelist->zlcache_ptr;
1402         if (!zlc)
1403                 return;
1404
1405         i = z - zonelist->_zonerefs;
1406
1407         set_bit(i, zlc->fullzones);
1408 }
1409
1410 #else   /* CONFIG_NUMA */
1411
1412 static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
1413 {
1414         return NULL;
1415 }
1416
1417 static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zoneref *z,
1418                                 nodemask_t *allowednodes)
1419 {
1420         return 1;
1421 }
1422
1423 static void zlc_mark_zone_full(struct zonelist *zonelist, struct zoneref *z)
1424 {
1425 }
1426 #endif  /* CONFIG_NUMA */
1427
1428 /*
1429  * get_page_from_freelist goes through the zonelist trying to allocate
1430  * a page.
1431  */
1432 static struct page *
1433 get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order,
1434                 struct zonelist *zonelist, int high_zoneidx, int alloc_flags,
1435                 struct zone *preferred_zone, int migratetype)
1436 {
1437         struct zoneref *z;
1438         struct page *page = NULL;
1439         int classzone_idx;
1440         struct zone *zone;
1441         nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
1442         int zlc_active = 0;             /* set if using zonelist_cache */
1443         int did_zlc_setup = 0;          /* just call zlc_setup() one time */
1444
1445         classzone_idx = zone_idx(preferred_zone);
1446 zonelist_scan:
1447         /*
1448          * Scan zonelist, looking for a zone with enough free.
1449          * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
1450          */
1451         for_each_zone_zonelist_nodemask(zone, z, zonelist,
1452                                                 high_zoneidx, nodemask) {
1453                 if (NUMA_BUILD && zlc_active &&
1454                         !zlc_zone_worth_trying(zonelist, z, allowednodes))
1455                                 continue;
1456                 if ((alloc_flags & ALLOC_CPUSET) &&
1457                         !cpuset_zone_allowed_softwall(zone, gfp_mask))
1458                                 goto try_next_zone;
1459
1460                 BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
1461                 if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {
1462                         unsigned long mark;
1463                         mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];
1464                         if (!zone_watermark_ok(zone, order, mark,
1465                                     classzone_idx, alloc_flags)) {
1466                                 if (!zone_reclaim_mode ||
1467                                     !zone_reclaim(zone, gfp_mask, order))
1468                                         goto this_zone_full;
1469                         }
1470                 }
1471
1472                 page = buffered_rmqueue(preferred_zone, zone, order,
1473                                                 gfp_mask, migratetype);
1474                 if (page)
1475                         break;
1476 this_zone_full:
1477                 if (NUMA_BUILD)
1478                         zlc_mark_zone_full(zonelist, z);
1479 try_next_zone:
1480                 if (NUMA_BUILD && !did_zlc_setup && nr_online_nodes > 1) {
1481                         /*
1482                          * we do zlc_setup after the first zone is tried but only
1483                          * if there are multiple nodes make it worthwhile
1484                          */
1485                         allowednodes = zlc_setup(zonelist, alloc_flags);
1486                         zlc_active = 1;
1487                         did_zlc_setup = 1;
1488                 }
1489         }
1490
1491         if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {
1492                 /* Disable zlc cache for second zonelist scan */
1493                 zlc_active = 0;
1494                 goto zonelist_scan;
1495         }
1496         return page;
1497 }
1498
1499 static inline int
1500 should_alloc_retry(gfp_t gfp_mask, unsigned int order,
1501                                 unsigned long pages_reclaimed)
1502 {
1503         /* Do not loop if specifically requested */
1504         if (gfp_mask & __GFP_NORETRY)
1505                 return 0;
1506
1507         /*
1508          * In this implementation, order <= PAGE_ALLOC_COSTLY_ORDER
1509          * means __GFP_NOFAIL, but that may not be true in other
1510          * implementations.
1511          */
1512         if (order <= PAGE_ALLOC_COSTLY_ORDER)
1513                 return 1;
1514
1515         /*
1516          * For order > PAGE_ALLOC_COSTLY_ORDER, if __GFP_REPEAT is
1517          * specified, then we retry until we no longer reclaim any pages
1518          * (above), or we've reclaimed an order of pages at least as
1519          * large as the allocation's order. In both cases, if the
1520          * allocation still fails, we stop retrying.
1521          */
1522         if (gfp_mask & __GFP_REPEAT && pages_reclaimed < (1 << order))
1523                 return 1;
1524
1525         /*
1526          * Don't let big-order allocations loop unless the caller
1527          * explicitly requests that.
1528          */
1529         if (gfp_mask & __GFP_NOFAIL)
1530                 return 1;
1531
1532         return 0;
1533 }
1534
1535 static inline struct page *
1536 __alloc_pages_may_oom(gfp_t gfp_mask, unsigned int order,
1537         struct zonelist *zonelist, enum zone_type high_zoneidx,
1538         nodemask_t *nodemask, struct zone *preferred_zone,
1539         int migratetype)
1540 {
1541         struct page *page;
1542
1543         /* Acquire the OOM killer lock for the zones in zonelist */
1544         if (!try_set_zone_oom(zonelist, gfp_mask)) {
1545                 schedule_timeout_uninterruptible(1);
1546                 return NULL;
1547         }
1548
1549         /*
1550          * Go through the zonelist yet one more time, keep very high watermark
1551          * here, this is only to catch a parallel oom killing, we must fail if
1552          * we're still under heavy pressure.
1553          */
1554         page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask,
1555                 order, zonelist, high_zoneidx,
1556                 ALLOC_WMARK_HIGH|ALLOC_CPUSET,
1557                 preferred_zone, migratetype);
1558         if (page)
1559                 goto out;
1560
1561         /* The OOM killer will not help higher order allocs */
1562         if (order > PAGE_ALLOC_COSTLY_ORDER)
1563                 goto out;
1564
1565         /* Exhausted what can be done so it's blamo time */
1566         out_of_memory(zonelist, gfp_mask, order);
1567
1568 out:
1569         clear_zonelist_oom(zonelist, gfp_mask);
1570         return page;
1571 }
1572
1573 /* The really slow allocator path where we enter direct reclaim */
1574 static inline struct page *
1575 __alloc_pages_direct_reclaim(gfp_t gfp_mask, unsigned int order,
1576         struct zonelist *zonelist, enum zone_type high_zoneidx,
1577         nodemask_t *nodemask, int alloc_flags, struct zone *preferred_zone,
1578         int migratetype, unsigned long *did_some_progress)
1579 {
1580         struct page *page = NULL;
1581         struct reclaim_state reclaim_state;
1582         struct task_struct *p = current;
1583
1584         cond_resched();
1585
1586         /* We now go into synchronous reclaim */
1587         cpuset_memory_pressure_bump();
1588
1589         /*
1590          * The task's cpuset might have expanded its set of allowable nodes
1591          */
1592         p->flags |= PF_MEMALLOC;
1593         lockdep_set_current_reclaim_state(gfp_mask);
1594         reclaim_state.reclaimed_slab = 0;
1595         p->reclaim_state = &reclaim_state;
1596
1597         *did_some_progress = try_to_free_pages(zonelist, order, gfp_mask, nodemask);
1598
1599         p->reclaim_state = NULL;
1600         lockdep_clear_current_reclaim_state();
1601         p->flags &= ~PF_MEMALLOC;
1602
1603         cond_resched();
1604
1605         if (order != 0)
1606                 drain_all_pages();
1607
1608         if (likely(*did_some_progress))
1609                 page = get_page_from_freelist(gfp_mask, nodemask, order,
1610                                         zonelist, high_zoneidx,
1611                                         alloc_flags, preferred_zone,
1612                                         migratetype);
1613         return page;
1614 }
1615
1616 /*
1617  * This is called in the allocator slow-path if the allocation request is of
1618  * sufficient urgency to ignore watermarks and take other desperate measures
1619  */
1620 static inline struct page *
1621 __alloc_pages_high_priority(gfp_t gfp_mask, unsigned int order,
1622         struct zonelist *zonelist, enum zone_type high_zoneidx,
1623         nodemask_t *nodemask, struct zone *preferred_zone,
1624         int migratetype)
1625 {
1626         struct page *page;
1627
1628         do {
1629                 page = get_page_from_freelist(gfp_mask, nodemask, order,
1630                         zonelist, high_zoneidx, ALLOC_NO_WATERMARKS,
1631                         preferred_zone, migratetype);
1632
1633                 if (!page && gfp_mask & __GFP_NOFAIL)
1634                         congestion_wait(WRITE, HZ/50);
1635         } while (!page && (gfp_mask & __GFP_NOFAIL));
1636
1637         return page;
1638 }
1639
1640 static inline
1641 void wake_all_kswapd(unsigned int order, struct zonelist *zonelist,
1642                                                 enum zone_type high_zoneidx)
1643 {
1644         struct zoneref *z;
1645         struct zone *zone;
1646
1647         for_each_zone_zonelist(zone, z, zonelist, high_zoneidx)
1648                 wakeup_kswapd(zone, order);
1649 }
1650
1651 static inline int
1652 gfp_to_alloc_flags(gfp_t gfp_mask)
1653 {
1654         struct task_struct *p = current;
1655         int alloc_flags = ALLOC_WMARK_MIN | ALLOC_CPUSET;
1656         const gfp_t wait = gfp_mask & __GFP_WAIT;
1657
1658         /* __GFP_HIGH is assumed to be the same as ALLOC_HIGH to save a branch. */
1659         BUILD_BUG_ON(__GFP_HIGH != ALLOC_HIGH);
1660
1661         /*
1662          * The caller may dip into page reserves a bit more if the caller
1663          * cannot run direct reclaim, or if the caller has realtime scheduling
1664          * policy or is asking for __GFP_HIGH memory.  GFP_ATOMIC requests will
1665          * set both ALLOC_HARDER (!wait) and ALLOC_HIGH (__GFP_HIGH).
1666          */
1667         alloc_flags |= (gfp_mask & __GFP_HIGH);
1668
1669         if (!wait) {
1670                 alloc_flags |= ALLOC_HARDER;
1671                 /*
1672                  * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc.
1673                  * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
1674                  */
1675                 alloc_flags &= ~ALLOC_CPUSET;
1676         } else if (unlikely(rt_task(p)))
1677                 alloc_flags |= ALLOC_HARDER;
1678
1679         if (likely(!(gfp_mask & __GFP_NOMEMALLOC))) {
1680                 if (!in_interrupt() &&
1681                     ((p->flags & PF_MEMALLOC) ||
1682                      unlikely(test_thread_flag(TIF_MEMDIE))))
1683                         alloc_flags |= ALLOC_NO_WATERMARKS;
1684         }
1685
1686         return alloc_flags;
1687 }
1688
1689 static inline struct page *
1690 __alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
1691         struct zonelist *zonelist, enum zone_type high_zoneidx,
1692         nodemask_t *nodemask, struct zone *preferred_zone,
1693         int migratetype)
1694 {
1695         const gfp_t wait = gfp_mask & __GFP_WAIT;
1696         struct page *page = NULL;
1697         int alloc_flags;
1698         unsigned long pages_reclaimed = 0;
1699         unsigned long did_some_progress;
1700         struct task_struct *p = current;
1701
1702         /*
1703          * In the slowpath, we sanity check order to avoid ever trying to
1704          * reclaim >= MAX_ORDER areas which will never succeed. Callers may
1705          * be using allocators in order of preference for an area that is
1706          * too large.
1707          */
1708         if (WARN_ON_ONCE(order >= MAX_ORDER))
1709                 return NULL;
1710
1711         /*
1712          * GFP_THISNODE (meaning __GFP_THISNODE, __GFP_NORETRY and
1713          * __GFP_NOWARN set) should not cause reclaim since the subsystem
1714          * (f.e. slab) using GFP_THISNODE may choose to trigger reclaim
1715          * using a larger set of nodes after it has established that the
1716          * allowed per node queues are empty and that nodes are
1717          * over allocated.
1718          */
1719         if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)
1720                 goto nopage;
1721
1722         wake_all_kswapd(order, zonelist, high_zoneidx);
1723
1724         /*
1725          * OK, we're below the kswapd watermark and have kicked background
1726          * reclaim. Now things get more complex, so set up alloc_flags according
1727          * to how we want to proceed.
1728          */
1729         alloc_flags = gfp_to_alloc_flags(gfp_mask);
1730
1731 restart:
1732         /* This is the last chance, in general, before the goto nopage. */
1733         page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist,
1734                         high_zoneidx, alloc_flags & ~ALLOC_NO_WATERMARKS,
1735                         preferred_zone, migratetype);
1736         if (page)
1737                 goto got_pg;
1738
1739 rebalance:
1740         /* Allocate without watermarks if the context allows */
1741         if (alloc_flags & ALLOC_NO_WATERMARKS) {
1742                 page = __alloc_pages_high_priority(gfp_mask, order,
1743                                 zonelist, high_zoneidx, nodemask,
1744                                 preferred_zone, migratetype);
1745                 if (page)
1746                         goto got_pg;
1747         }
1748
1749         /* Atomic allocations - we can't balance anything */
1750         if (!wait)
1751                 goto nopage;
1752
1753         /* Avoid recursion of direct reclaim */
1754         if (p->flags & PF_MEMALLOC)
1755                 goto nopage;
1756
1757         /* Try direct reclaim and then allocating */
1758         page = __alloc_pages_direct_reclaim(gfp_mask, order,
1759                                         zonelist, high_zoneidx,
1760                                         nodemask,
1761                                         alloc_flags, preferred_zone,
1762                                         migratetype, &did_some_progress);
1763         if (page)
1764                 goto got_pg;
1765
1766         /*
1767          * If we failed to make any progress reclaiming, then we are
1768          * running out of options and have to consider going OOM
1769          */
1770         if (!did_some_progress) {
1771                 if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
1772                         page = __alloc_pages_may_oom(gfp_mask, order,
1773                                         zonelist, high_zoneidx,
1774                                         nodemask, preferred_zone,
1775                                         migratetype);
1776                         if (page)
1777                                 goto got_pg;
1778
1779                         /*
1780                          * The OOM killer does not trigger for high-order allocations
1781                          * but if no progress is being made, there are no other
1782                          * options and retrying is unlikely to help
1783                          */
1784                         if (order > PAGE_ALLOC_COSTLY_ORDER)
1785                                 goto nopage;
1786
1787                         goto restart;
1788                 }
1789         }
1790
1791         /* Check if we should retry the allocation */
1792         pages_reclaimed += did_some_progress;
1793         if (should_alloc_retry(gfp_mask, order, pages_reclaimed)) {
1794                 /* Wait for some write requests to complete then retry */
1795                 congestion_wait(WRITE, HZ/50);
1796                 goto rebalance;
1797         }
1798
1799 nopage:
1800         if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
1801                 printk(KERN_WARNING "%s: page allocation failure."
1802                         " order:%d, mode:0x%x\n",
1803                         p->comm, order, gfp_mask);
1804                 dump_stack();
1805                 show_mem();
1806         }
1807 got_pg:
1808         return page;
1809
1810 }
1811
1812 /*
1813  * This is the 'heart' of the zoned buddy allocator.
1814  */
1815 struct page *
1816 __alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
1817                         struct zonelist *zonelist, nodemask_t *nodemask)
1818 {
1819         enum zone_type high_zoneidx = gfp_zone(gfp_mask);
1820         struct zone *preferred_zone;
1821         struct page *page;
1822         int migratetype = allocflags_to_migratetype(gfp_mask);
1823
1824         lockdep_trace_alloc(gfp_mask);
1825
1826         might_sleep_if(gfp_mask & __GFP_WAIT);
1827
1828         if (should_fail_alloc_page(gfp_mask, order))
1829                 return NULL;
1830
1831         /*
1832          * Check the zones suitable for the gfp_mask contain at least one
1833          * valid zone. It's possible to have an empty zonelist as a result
1834          * of GFP_THISNODE and a memoryless node
1835          */
1836         if (unlikely(!zonelist->_zonerefs->zone))
1837                 return NULL;
1838
1839         /* The preferred zone is used for statistics later */
1840         first_zones_zonelist(zonelist, high_zoneidx, nodemask, &preferred_zone);
1841         if (!preferred_zone)
1842                 return NULL;
1843
1844         /* First allocation attempt */
1845         page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order,
1846                         zonelist, high_zoneidx, ALLOC_WMARK_LOW|ALLOC_CPUSET,
1847                         preferred_zone, migratetype);
1848         if (unlikely(!page))
1849                 page = __alloc_pages_slowpath(gfp_mask, order,
1850                                 zonelist, high_zoneidx, nodemask,
1851                                 preferred_zone, migratetype);
1852
1853         return page;
1854 }
1855 EXPORT_SYMBOL(__alloc_pages_nodemask);
1856
1857 /*
1858  * Common helper functions.
1859  */
1860 unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
1861 {
1862         struct page * page;
1863         page = alloc_pages(gfp_mask, order);
1864         if (!page)
1865                 return 0;
1866         return (unsigned long) page_address(page);
1867 }
1868
1869 EXPORT_SYMBOL(__get_free_pages);
1870
1871 unsigned long get_zeroed_page(gfp_t gfp_mask)
1872 {
1873         struct page * page;
1874
1875         /*
1876          * get_zeroed_page() returns a 32-bit address, which cannot represent
1877          * a highmem page
1878          */
1879         VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0);
1880
1881         page = alloc_pages(gfp_mask | __GFP_ZERO, 0);
1882         if (page)
1883                 return (unsigned long) page_address(page);
1884         return 0;
1885 }
1886
1887 EXPORT_SYMBOL(get_zeroed_page);
1888
1889 void __pagevec_free(struct pagevec *pvec)
1890 {
1891         int i = pagevec_count(pvec);
1892
1893         while (--i >= 0)
1894                 free_hot_cold_page(pvec->pages[i], pvec->cold);
1895 }
1896
1897 void __free_pages(struct page *page, unsigned int order)
1898 {
1899         if (put_page_testzero(page)) {
1900                 if (order == 0)
1901                         free_hot_page(page);
1902                 else
1903                         __free_pages_ok(page, order);
1904         }
1905 }
1906
1907 EXPORT_SYMBOL(__free_pages);
1908
1909 void free_pages(unsigned long addr, unsigned int order)
1910 {
1911         if (addr != 0) {
1912                 VM_BUG_ON(!virt_addr_valid((void *)addr));
1913                 __free_pages(virt_to_page((void *)addr), order);
1914         }
1915 }
1916
1917 EXPORT_SYMBOL(free_pages);
1918
1919 /**
1920  * alloc_pages_exact - allocate an exact number physically-contiguous pages.
1921  * @size: the number of bytes to allocate
1922  * @gfp_mask: GFP flags for the allocation
1923  *
1924  * This function is similar to alloc_pages(), except that it allocates the
1925  * minimum number of pages to satisfy the request.  alloc_pages() can only
1926  * allocate memory in power-of-two pages.
1927  *
1928  * This function is also limited by MAX_ORDER.
1929  *
1930  * Memory allocated by this function must be released by free_pages_exact().
1931  */
1932 void *alloc_pages_exact(size_t size, gfp_t gfp_mask)
1933 {
1934         unsigned int order = get_order(size);
1935         unsigned long addr;
1936
1937         addr = __get_free_pages(gfp_mask, order);
1938         if (addr) {
1939                 unsigned long alloc_end = addr + (PAGE_SIZE << order);
1940                 unsigned long used = addr + PAGE_ALIGN(size);
1941
1942                 split_page(virt_to_page(addr), order);
1943                 while (used < alloc_end) {
1944                         free_page(used);
1945                         used += PAGE_SIZE;
1946                 }
1947         }
1948
1949         return (void *)addr;
1950 }
1951 EXPORT_SYMBOL(alloc_pages_exact);
1952
1953 /**
1954  * free_pages_exact - release memory allocated via alloc_pages_exact()
1955  * @virt: the value returned by alloc_pages_exact.
1956  * @size: size of allocation, same value as passed to alloc_pages_exact().
1957  *
1958  * Release the memory allocated by a previous call to alloc_pages_exact.
1959  */
1960 void free_pages_exact(void *virt, size_t size)
1961 {
1962         unsigned long addr = (unsigned long)virt;
1963         unsigned long end = addr + PAGE_ALIGN(size);
1964
1965         while (addr < end) {
1966                 free_page(addr);
1967                 addr += PAGE_SIZE;
1968         }
1969 }
1970 EXPORT_SYMBOL(free_pages_exact);
1971
1972 static unsigned int nr_free_zone_pages(int offset)
1973 {
1974         struct zoneref *z;
1975         struct zone *zone;
1976
1977         /* Just pick one node, since fallback list is circular */
1978         unsigned int sum = 0;
1979
1980         struct zonelist *zonelist = node_zonelist(numa_node_id(), GFP_KERNEL);
1981
1982         for_each_zone_zonelist(zone, z, zonelist, offset) {
1983                 unsigned long size = zone->present_pages;
1984                 unsigned long high = high_wmark_pages(zone);
1985                 if (size > high)
1986                         sum += size - high;
1987         }
1988
1989         return sum;
1990 }
1991
1992 /*
1993  * Amount of free RAM allocatable within ZONE_DMA and ZONE_NORMAL
1994  */
1995 unsigned int nr_free_buffer_pages(void)
1996 {
1997         return nr_free_zone_pages(gfp_zone(GFP_USER));
1998 }
1999 EXPORT_SYMBOL_GPL(nr_free_buffer_pages);
2000
2001 /*
2002  * Amount of free RAM allocatable within all zones
2003  */
2004 unsigned int nr_free_pagecache_pages(void)
2005 {
2006         return nr_free_zone_pages(gfp_zone(GFP_HIGHUSER_MOVABLE));
2007 }
2008
2009 static inline void show_node(struct zone *zone)
2010 {
2011         if (NUMA_BUILD)
2012                 printk("Node %d ", zone_to_nid(zone));
2013 }
2014
2015 void si_meminfo(struct sysinfo *val)
2016 {
2017         val->totalram = totalram_pages;
2018         val->sharedram = 0;
2019         val->freeram = global_page_state(NR_FREE_PAGES);
2020         val->bufferram = nr_blockdev_pages();
2021         val->totalhigh = totalhigh_pages;
2022         val->freehigh = nr_free_highpages();
2023         val->mem_unit = PAGE_SIZE;
2024 }
2025
2026 EXPORT_SYMBOL(si_meminfo);
2027
2028 #ifdef CONFIG_NUMA
2029 void si_meminfo_node(struct sysinfo *val, int nid)
2030 {
2031         pg_data_t *pgdat = NODE_DATA(nid);
2032
2033         val->totalram = pgdat->node_present_pages;
2034         val->freeram = node_page_state(nid, NR_FREE_PAGES);
2035 #ifdef CONFIG_HIGHMEM
2036         val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages;
2037         val->freehigh = zone_page_state(&pgdat->node_zones[ZONE_HIGHMEM],
2038                         NR_FREE_PAGES);
2039 #else
2040         val->totalhigh = 0;
2041         val->freehigh = 0;
2042 #endif
2043         val->mem_unit = PAGE_SIZE;
2044 }
2045 #endif
2046
2047 #define K(x) ((x) << (PAGE_SHIFT-10))
2048
2049 /*
2050  * Show free area list (used inside shift_scroll-lock stuff)
2051  * We also calculate the percentage fragmentation. We do this by counting the
2052  * memory on each free list with the exception of the first item on the list.
2053  */
2054 void show_free_areas(void)
2055 {
2056         int cpu;
2057         struct zone *zone;
2058
2059         for_each_populated_zone(zone) {
2060                 show_node(zone);
2061                 printk("%s per-cpu:\n", zone->name);
2062
2063                 for_each_online_cpu(cpu) {
2064                         struct per_cpu_pageset *pageset;
2065
2066                         pageset = zone_pcp(zone, cpu);
2067
2068                         printk("CPU %4d: hi:%5d, btch:%4d usd:%4d\n",
2069                                cpu, pageset->pcp.high,
2070                                pageset->pcp.batch, pageset->pcp.count);
2071                 }
2072         }
2073
2074         printk("Active_anon:%lu active_file:%lu inactive_anon:%lu\n"
2075                 " inactive_file:%lu"
2076 //TODO:  check/adjust line lengths
2077 #ifdef CONFIG_UNEVICTABLE_LRU
2078                 " unevictable:%lu"
2079 #endif
2080                 " dirty:%lu writeback:%lu unstable:%lu\n"
2081                 " free:%lu slab:%lu mapped:%lu pagetables:%lu bounce:%lu\n",
2082                 global_page_state(NR_ACTIVE_ANON),
2083                 global_page_state(NR_ACTIVE_FILE),
2084                 global_page_state(NR_INACTIVE_ANON),
2085                 global_page_state(NR_INACTIVE_FILE),
2086 #ifdef CONFIG_UNEVICTABLE_LRU
2087                 global_page_state(NR_UNEVICTABLE),
2088 #endif
2089                 global_page_state(NR_FILE_DIRTY),
2090                 global_page_state(NR_WRITEBACK),
2091                 global_page_state(NR_UNSTABLE_NFS),
2092                 global_page_state(NR_FREE_PAGES),
2093                 global_page_state(NR_SLAB_RECLAIMABLE) +
2094                         global_page_state(NR_SLAB_UNRECLAIMABLE),
2095                 global_page_state(NR_FILE_MAPPED),
2096                 global_page_state(NR_PAGETABLE),
2097                 global_page_state(NR_BOUNCE));
2098
2099         for_each_populated_zone(zone) {
2100                 int i;
2101
2102                 show_node(zone);
2103                 printk("%s"
2104                         " free:%lukB"
2105                         " min:%lukB"
2106                         " low:%lukB"
2107                         " high:%lukB"
2108                         " active_anon:%lukB"
2109                         " inactive_anon:%lukB"
2110                         " active_file:%lukB"
2111                         " inactive_file:%lukB"
2112 #ifdef CONFIG_UNEVICTABLE_LRU
2113                         " unevictable:%lukB"
2114 #endif
2115                         " present:%lukB"
2116                         " pages_scanned:%lu"
2117                         " all_unreclaimable? %s"
2118                         "\n",
2119                         zone->name,
2120                         K(zone_page_state(zone, NR_FREE_PAGES)),
2121                         K(min_wmark_pages(zone)),
2122                         K(low_wmark_pages(zone)),
2123                         K(high_wmark_pages(zone)),
2124                         K(zone_page_state(zone, NR_ACTIVE_ANON)),
2125                         K(zone_page_state(zone, NR_INACTIVE_ANON)),
2126                         K(zone_page_state(zone, NR_ACTIVE_FILE)),
2127                         K(zone_page_state(zone, NR_INACTIVE_FILE)),
2128 #ifdef CONFIG_UNEVICTABLE_LRU
2129                         K(zone_page_state(zone, NR_UNEVICTABLE)),
2130 #endif
2131                         K(zone->present_pages),
2132                         zone->pages_scanned,
2133                         (zone_is_all_unreclaimable(zone) ? "yes" : "no")
2134                         );
2135                 printk("lowmem_reserve[]:");
2136                 for (i = 0; i < MAX_NR_ZONES; i++)
2137                         printk(" %lu", zone->lowmem_reserve[i]);
2138                 printk("\n");
2139         }
2140
2141         for_each_populated_zone(zone) {
2142                 unsigned long nr[MAX_ORDER], flags, order, total = 0;
2143
2144                 show_node(zone);
2145                 printk("%s: ", zone->name);
2146
2147                 spin_lock_irqsave(&zone->lock, flags);
2148                 for (order = 0; order < MAX_ORDER; order++) {
2149                         nr[order] = zone->free_area[order].nr_free;
2150                         total += nr[order] << order;
2151                 }
2152                 spin_unlock_irqrestore(&zone->lock, flags);
2153                 for (order = 0; order < MAX_ORDER; order++)
2154                         printk("%lu*%lukB ", nr[order], K(1UL) << order);
2155                 printk("= %lukB\n", K(total));
2156         }
2157
2158         printk("%ld total pagecache pages\n", global_page_state(NR_FILE_PAGES));
2159
2160         show_swap_cache_info();
2161 }
2162
2163 static void zoneref_set_zone(struct zone *zone, struct zoneref *zoneref)
2164 {
2165         zoneref->zone = zone;
2166         zoneref->zone_idx = zone_idx(zone);
2167 }
2168
2169 /*
2170  * Builds allocation fallback zone lists.
2171  *
2172  * Add all populated zones of a node to the zonelist.
2173  */
2174 static int build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist,
2175                                 int nr_zones, enum zone_type zone_type)
2176 {
2177         struct zone *zone;
2178
2179         BUG_ON(zone_type >= MAX_NR_ZONES);
2180         zone_type++;
2181
2182         do {
2183                 zone_type--;
2184                 zone = pgdat->node_zones + zone_type;
2185                 if (populated_zone(zone)) {
2186                         zoneref_set_zone(zone,
2187                                 &zonelist->_zonerefs[nr_zones++]);
2188                         check_highest_zone(zone_type);
2189                 }
2190
2191         } while (zone_type);
2192         return nr_zones;
2193 }
2194
2195
2196 /*
2197  *  zonelist_order:
2198  *  0 = automatic detection of better ordering.
2199  *  1 = order by ([node] distance, -zonetype)
2200  *  2 = order by (-zonetype, [node] distance)
2201  *
2202  *  If not NUMA, ZONELIST_ORDER_ZONE and ZONELIST_ORDER_NODE will create
2203  *  the same zonelist. So only NUMA can configure this param.
2204  */
2205 #define ZONELIST_ORDER_DEFAULT  0
2206 #define ZONELIST_ORDER_NODE     1
2207 #define ZONELIST_ORDER_ZONE     2
2208
2209 /* zonelist order in the kernel.
2210  * set_zonelist_order() will set this to NODE or ZONE.
2211  */
2212 static int current_zonelist_order = ZONELIST_ORDER_DEFAULT;
2213 static char zonelist_order_name[3][8] = {"Default", "Node", "Zone"};
2214
2215
2216 #ifdef CONFIG_NUMA
2217 /* The value user specified ....changed by config */
2218 static int user_zonelist_order = ZONELIST_ORDER_DEFAULT;
2219 /* string for sysctl */
2220 #define NUMA_ZONELIST_ORDER_LEN 16
2221 char numa_zonelist_order[16] = "default";
2222
2223 /*
2224  * interface for configure zonelist ordering.
2225  * command line option "numa_zonelist_order"
2226  *      = "[dD]efault   - default, automatic configuration.
2227  *      = "[nN]ode      - order by node locality, then by zone within node
2228  *      = "[zZ]one      - order by zone, then by locality within zone
2229  */
2230
2231 static int __parse_numa_zonelist_order(char *s)
2232 {
2233         if (*s == 'd' || *s == 'D') {
2234                 user_zonelist_order = ZONELIST_ORDER_DEFAULT;
2235         } else if (*s == 'n' || *s == 'N') {
2236                 user_zonelist_order = ZONELIST_ORDER_NODE;
2237         } else if (*s == 'z' || *s == 'Z') {
2238                 user_zonelist_order = ZONELIST_ORDER_ZONE;
2239         } else {
2240                 printk(KERN_WARNING
2241                         "Ignoring invalid numa_zonelist_order value:  "
2242                         "%s\n", s);
2243                 return -EINVAL;
2244         }
2245         return 0;
2246 }
2247
2248 static __init int setup_numa_zonelist_order(char *s)
2249 {
2250         if (s)
2251                 return __parse_numa_zonelist_order(s);
2252         return 0;
2253 }
2254 early_param("numa_zonelist_order", setup_numa_zonelist_order);
2255
2256 /*
2257  * sysctl handler for numa_zonelist_order
2258  */
2259 int numa_zonelist_order_handler(ctl_table *table, int write,
2260                 struct file *file, void __user *buffer, size_t *length,
2261                 loff_t *ppos)
2262 {
2263         char saved_string[NUMA_ZONELIST_ORDER_LEN];
2264         int ret;
2265
2266         if (write)
2267                 strncpy(saved_string, (char*)table->data,
2268                         NUMA_ZONELIST_ORDER_LEN);
2269         ret = proc_dostring(table, write, file, buffer, length, ppos);
2270         if (ret)
2271                 return ret;
2272         if (write) {
2273                 int oldval = user_zonelist_order;
2274                 if (__parse_numa_zonelist_order((char*)table->data)) {
2275                         /*
2276                          * bogus value.  restore saved string
2277                          */
2278                         strncpy((char*)table->data, saved_string,
2279                                 NUMA_ZONELIST_ORDER_LEN);
2280                         user_zonelist_order = oldval;
2281                 } else if (oldval != user_zonelist_order)
2282                         build_all_zonelists();
2283         }
2284         return 0;
2285 }
2286
2287
2288 #define MAX_NODE_LOAD (nr_online_nodes)
2289 static int node_load[MAX_NUMNODES];
2290
2291 /**
2292  * find_next_best_node - find the next node that should appear in a given node's fallback list
2293  * @node: node whose fallback list we're appending
2294  * @used_node_mask: nodemask_t of already used nodes
2295  *
2296  * We use a number of factors to determine which is the next node that should
2297  * appear on a given node's fallback list.  The node should not have appeared
2298  * already in @node's fallback list, and it should be the next closest node
2299  * according to the distance array (which contains arbitrary distance values
2300  * from each node to each node in the system), and should also prefer nodes
2301  * with no CPUs, since presumably they'll have very little allocation pressure
2302  * on them otherwise.
2303  * It returns -1 if no node is found.
2304  */
2305 static int find_next_best_node(int node, nodemask_t *used_node_mask)
2306 {
2307         int n, val;
2308         int min_val = INT_MAX;
2309         int best_node = -1;
2310         const struct cpumask *tmp = cpumask_of_node(0);
2311
2312         /* Use the local node if we haven't already */
2313         if (!node_isset(node, *used_node_mask)) {
2314                 node_set(node, *used_node_mask);
2315                 return node;
2316         }
2317
2318         for_each_node_state(n, N_HIGH_MEMORY) {
2319
2320                 /* Don't want a node to appear more than once */
2321                 if (node_isset(n, *used_node_mask))
2322                         continue;
2323
2324                 /* Use the distance array to find the distance */
2325                 val = node_distance(node, n);
2326
2327                 /* Penalize nodes under us ("prefer the next node") */
2328                 val += (n < node);
2329
2330                 /* Give preference to headless and unused nodes */
2331                 tmp = cpumask_of_node(n);
2332                 if (!cpumask_empty(tmp))
2333                         val += PENALTY_FOR_NODE_WITH_CPUS;
2334
2335                 /* Slight preference for less loaded node */
2336                 val *= (MAX_NODE_LOAD*MAX_NUMNODES);
2337                 val += node_load[n];
2338
2339                 if (val < min_val) {
2340                         min_val = val;
2341                         best_node = n;
2342                 }
2343         }
2344
2345         if (best_node >= 0)
2346                 node_set(best_node, *used_node_mask);
2347
2348         return best_node;
2349 }
2350
2351
2352 /*
2353  * Build zonelists ordered by node and zones within node.
2354  * This results in maximum locality--normal zone overflows into local
2355  * DMA zone, if any--but risks exhausting DMA zone.
2356  */
2357 static void build_zonelists_in_node_order(pg_data_t *pgdat, int node)
2358 {
2359         int j;
2360         struct zonelist *zonelist;
2361
2362         zonelist = &pgdat->node_zonelists[0];
2363         for (j = 0; zonelist->_zonerefs[j].zone != NULL; j++)
2364                 ;
2365         j = build_zonelists_node(NODE_DATA(node), zonelist, j,
2366                                                         MAX_NR_ZONES - 1);
2367         zonelist->_zonerefs[j].zone = NULL;
2368         zonelist->_zonerefs[j].zone_idx = 0;
2369 }
2370
2371 /*
2372  * Build gfp_thisnode zonelists
2373  */
2374 static void build_thisnode_zonelists(pg_data_t *pgdat)
2375 {
2376         int j;
2377         struct zonelist *zonelist;
2378
2379         zonelist = &pgdat->node_zonelists[1];
2380         j = build_zonelists_node(pgdat, zonelist, 0, MAX_NR_ZONES - 1);
2381         zonelist->_zonerefs[j].zone = NULL;
2382         zonelist->_zonerefs[j].zone_idx = 0;
2383 }
2384
2385 /*
2386  * Build zonelists ordered by zone and nodes within zones.
2387  * This results in conserving DMA zone[s] until all Normal memory is
2388  * exhausted, but results in overflowing to remote node while memory
2389  * may still exist in local DMA zone.
2390  */
2391 static int node_order[MAX_NUMNODES];
2392
2393 static void build_zonelists_in_zone_order(pg_data_t *pgdat, int nr_nodes)
2394 {
2395         int pos, j, node;
2396         int zone_type;          /* needs to be signed */
2397         struct zone *z;
2398         struct zonelist *zonelist;
2399
2400         zonelist = &pgdat->node_zonelists[0];
2401         pos = 0;
2402         for (zone_type = MAX_NR_ZONES - 1; zone_type >= 0; zone_type--) {
2403                 for (j = 0; j < nr_nodes; j++) {
2404                         node = node_order[j];
2405                         z = &NODE_DATA(node)->node_zones[zone_type];
2406                         if (populated_zone(z)) {
2407                                 zoneref_set_zone(z,
2408                                         &zonelist->_zonerefs[pos++]);
2409                                 check_highest_zone(zone_type);
2410                         }
2411                 }
2412         }
2413         zonelist->_zonerefs[pos].zone = NULL;
2414         zonelist->_zonerefs[pos].zone_idx = 0;
2415 }
2416
2417 static int default_zonelist_order(void)
2418 {
2419         int nid, zone_type;
2420         unsigned long low_kmem_size,total_size;
2421         struct zone *z;
2422         int average_size;
2423         /*
2424          * ZONE_DMA and ZONE_DMA32 can be very small area in the sytem.
2425          * If they are really small and used heavily, the system can fall
2426          * into OOM very easily.
2427          * This function detect ZONE_DMA/DMA32 size and confgigures zone order.
2428          */
2429         /* Is there ZONE_NORMAL ? (ex. ppc has only DMA zone..) */
2430         low_kmem_size = 0;
2431         total_size = 0;
2432         for_each_online_node(nid) {
2433                 for (zone_type = 0; zone_type < MAX_NR_ZONES; zone_type++) {
2434                         z = &NODE_DATA(nid)->node_zones[zone_type];
2435                         if (populated_zone(z)) {
2436                                 if (zone_type < ZONE_NORMAL)
2437                                         low_kmem_size += z->present_pages;
2438                                 total_size += z->present_pages;
2439                         }
2440                 }
2441         }
2442         if (!low_kmem_size ||  /* there are no DMA area. */
2443             low_kmem_size > total_size/2) /* DMA/DMA32 is big. */
2444                 return ZONELIST_ORDER_NODE;
2445         /*
2446          * look into each node's config.
2447          * If there is a node whose DMA/DMA32 memory is very big area on
2448          * local memory, NODE_ORDER may be suitable.
2449          */
2450         average_size = total_size /
2451                                 (nodes_weight(node_states[N_HIGH_MEMORY]) + 1);
2452         for_each_online_node(nid) {
2453                 low_kmem_size = 0;
2454                 total_size = 0;
2455                 for (zone_type = 0; zone_type < MAX_NR_ZONES; zone_type++) {
2456                         z = &NODE_DATA(nid)->node_zones[zone_type];
2457                         if (populated_zone(z)) {
2458                                 if (zone_type < ZONE_NORMAL)
2459                                         low_kmem_size += z->present_pages;
2460                                 total_size += z->present_pages;
2461                         }
2462                 }
2463                 if (low_kmem_size &&
2464                     total_size > average_size && /* ignore small node */
2465                     low_kmem_size > total_size * 70/100)
2466                         return ZONELIST_ORDER_NODE;
2467         }
2468         return ZONELIST_ORDER_ZONE;
2469 }
2470
2471 static void set_zonelist_order(void)
2472 {
2473         if (user_zonelist_order == ZONELIST_ORDER_DEFAULT)
2474                 current_zonelist_order = default_zonelist_order();
2475         else
2476                 current_zonelist_order = user_zonelist_order;
2477 }
2478
2479 static void build_zonelists(pg_data_t *pgdat)
2480 {
2481         int j, node, load;
2482         enum zone_type i;
2483         nodemask_t used_mask;
2484         int local_node, prev_node;
2485         struct zonelist *zonelist;
2486         int order = current_zonelist_order;
2487
2488         /* initialize zonelists */
2489         for (i = 0; i < MAX_ZONELISTS; i++) {
2490                 zonelist = pgdat->node_zonelists + i;
2491                 zonelist->_zonerefs[0].zone = NULL;
2492                 zonelist->_zonerefs[0].zone_idx = 0;
2493         }
2494
2495         /* NUMA-aware ordering of nodes */
2496         local_node = pgdat->node_id;
2497         load = nr_online_nodes;
2498         prev_node = local_node;
2499         nodes_clear(used_mask);
2500
2501         memset(node_load, 0, sizeof(node_load));
2502         memset(node_order, 0, sizeof(node_order));
2503         j = 0;
2504
2505         while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
2506                 int distance = node_distance(local_node, node);
2507
2508                 /*
2509                  * If another node is sufficiently far away then it is better
2510                  * to reclaim pages in a zone before going off node.
2511                  */
2512                 if (distance > RECLAIM_DISTANCE)
2513                         zone_reclaim_mode = 1;
2514
2515                 /*
2516                  * We don't want to pressure a particular node.
2517                  * So adding penalty to the first node in same
2518                  * distance group to make it round-robin.
2519                  */
2520                 if (distance != node_distance(local_node, prev_node))
2521                         node_load[node] = load;
2522
2523                 prev_node = node;
2524                 load--;
2525                 if (order == ZONELIST_ORDER_NODE)
2526                         build_zonelists_in_node_order(pgdat, node);
2527                 else
2528                         node_order[j++] = node; /* remember order */
2529         }
2530
2531         if (order == ZONELIST_ORDER_ZONE) {
2532                 /* calculate node order -- i.e., DMA last! */
2533                 build_zonelists_in_zone_order(pgdat, j);
2534         }
2535
2536         build_thisnode_zonelists(pgdat);
2537 }
2538
2539 /* Construct the zonelist performance cache - see further mmzone.h */
2540 static void build_zonelist_cache(pg_data_t *pgdat)
2541 {
2542         struct zonelist *zonelist;
2543         struct zonelist_cache *zlc;
2544         struct zoneref *z;
2545
2546         zonelist = &pgdat->node_zonelists[0];
2547         zonelist->zlcache_ptr = zlc = &zonelist->zlcache;
2548         bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
2549         for (z = zonelist->_zonerefs; z->zone; z++)
2550                 zlc->z_to_n[z - zonelist->_zonerefs] = zonelist_node_idx(z);
2551 }
2552
2553
2554 #else   /* CONFIG_NUMA */
2555
2556 static void set_zonelist_order(void)
2557 {
2558         current_zonelist_order = ZONELIST_ORDER_ZONE;
2559 }
2560
2561 static void build_zonelists(pg_data_t *pgdat)
2562 {
2563         int node, local_node;
2564         enum zone_type j;
2565         struct zonelist *zonelist;
2566
2567         local_node = pgdat->node_id;
2568
2569         zonelist = &pgdat->node_zonelists[0];
2570         j = build_zonelists_node(pgdat, zonelist, 0, MAX_NR_ZONES - 1);
2571
2572         /*
2573          * Now we build the zonelist so that it contains the zones
2574          * of all the other nodes.
2575          * We don't want to pressure a particular node, so when
2576          * building the zones for node N, we make sure that the
2577          * zones coming right after the local ones are those from
2578          * node N+1 (modulo N)
2579          */
2580         for (node = local_node + 1; node < MAX_NUMNODES; node++) {
2581                 if (!node_online(node))
2582                         continue;
2583                 j = build_zonelists_node(NODE_DATA(node), zonelist, j,
2584                                                         MAX_NR_ZONES - 1);
2585         }
2586         for (node = 0; node < local_node; node++) {
2587                 if (!node_online(node))
2588                         continue;
2589                 j = build_zonelists_node(NODE_DATA(node), zonelist, j,
2590                                                         MAX_NR_ZONES - 1);
2591         }
2592
2593         zonelist->_zonerefs[j].zone = NULL;
2594         zonelist->_zonerefs[j].zone_idx = 0;
2595 }
2596
2597 /* non-NUMA variant of zonelist performance cache - just NULL zlcache_ptr */
2598 static void build_zonelist_cache(pg_data_t *pgdat)
2599 {
2600         pgdat->node_zonelists[0].zlcache_ptr = NULL;
2601 }
2602
2603 #endif  /* CONFIG_NUMA */
2604
2605 /* return values int ....just for stop_machine() */
2606 static int __build_all_zonelists(void *dummy)
2607 {
2608         int nid;
2609
2610         for_each_online_node(nid) {
2611                 pg_data_t *pgdat = NODE_DATA(nid);
2612
2613                 build_zonelists(pgdat);
2614                 build_zonelist_cache(pgdat);
2615         }
2616         return 0;
2617 }
2618
2619 void build_all_zonelists(void)
2620 {
2621         set_zonelist_order();
2622
2623         if (system_state == SYSTEM_BOOTING) {
2624                 __build_all_zonelists(NULL);
2625                 mminit_verify_zonelist();
2626                 cpuset_init_current_mems_allowed();
2627         } else {
2628                 /* we have to stop all cpus to guarantee there is no user
2629                    of zonelist */
2630                 stop_machine(__build_all_zonelists, NULL, NULL);
2631                 /* cpuset refresh routine should be here */
2632         }
2633         vm_total_pages = nr_free_pagecache_pages();
2634         /*
2635          * Disable grouping by mobility if the number of pages in the
2636          * system is too low to allow the mechanism to work. It would be
2637          * more accurate, but expensive to check per-zone. This check is
2638          * made on memory-hotadd so a system can start with mobility
2639          * disabled and enable it later
2640          */
2641         if (vm_total_pages < (pageblock_nr_pages * MIGRATE_TYPES))
2642                 page_group_by_mobility_disabled = 1;
2643         else
2644                 page_group_by_mobility_disabled = 0;
2645
2646         printk("Built %i zonelists in %s order, mobility grouping %s.  "
2647                 "Total pages: %ld\n",
2648                         nr_online_nodes,
2649                         zonelist_order_name[current_zonelist_order],
2650                         page_group_by_mobility_disabled ? "off" : "on",
2651                         vm_total_pages);
2652 #ifdef CONFIG_NUMA
2653         printk("Policy zone: %s\n", zone_names[policy_zone]);
2654 #endif
2655 }
2656
2657 /*
2658  * Helper functions to size the waitqueue hash table.
2659  * Essentially these want to choose hash table sizes sufficiently
2660  * large so that collisions trying to wait on pages are rare.
2661  * But in fact, the number of active page waitqueues on typical
2662  * systems is ridiculously low, less than 200. So this is even
2663  * conservative, even though it seems large.
2664  *
2665  * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to
2666  * waitqueues, i.e. the size of the waitq table given the number of pages.
2667  */
2668 #define PAGES_PER_WAITQUEUE     256
2669
2670 #ifndef CONFIG_MEMORY_HOTPLUG
2671 static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
2672 {
2673         unsigned long size = 1;
2674
2675         pages /= PAGES_PER_WAITQUEUE;
2676
2677         while (size < pages)
2678                 size <<= 1;
2679
2680         /*
2681          * Once we have dozens or even hundreds of threads sleeping
2682          * on IO we've got bigger problems than wait queue collision.
2683          * Limit the size of the wait table to a reasonable size.
2684          */
2685         size = min(size, 4096UL);
2686
2687         return max(size, 4UL);
2688 }
2689 #else
2690 /*
2691  * A zone's size might be changed by hot-add, so it is not possible to determine
2692  * a suitable size for its wait_table.  So we use the maximum size now.
2693  *
2694  * The max wait table size = 4096 x sizeof(wait_queue_head_t).   ie:
2695  *
2696  *    i386 (preemption config)    : 4096 x 16 = 64Kbyte.
2697  *    ia64, x86-64 (no preemption): 4096 x 20 = 80Kbyte.
2698  *    ia64, x86-64 (preemption)   : 4096 x 24 = 96Kbyte.
2699  *
2700  * The maximum entries are prepared when a zone's memory is (512K + 256) pages
2701  * or more by the traditional way. (See above).  It equals:
2702  *
2703  *    i386, x86-64, powerpc(4K page size) : =  ( 2G + 1M)byte.
2704  *    ia64(16K page size)                 : =  ( 8G + 4M)byte.
2705  *    powerpc (64K page size)             : =  (32G +16M)byte.
2706  */
2707 static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
2708 {
2709         return 4096UL;
2710 }
2711 #endif
2712
2713 /*
2714  * This is an integer logarithm so that shifts can be used later
2715  * to extract the more random high bits from the multiplicative
2716  * hash function before the remainder is taken.
2717  */
2718 static inline unsigned long wait_table_bits(unsigned long size)
2719 {
2720         return ffz(~size);
2721 }
2722
2723 #define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))
2724
2725 /*
2726  * Mark a number of pageblocks as MIGRATE_RESERVE. The number
2727  * of blocks reserved is based on min_wmark_pages(zone). The memory within
2728  * the reserve will tend to store contiguous free pages. Setting min_free_kbytes
2729  * higher will lead to a bigger reserve which will get freed as contiguous
2730  * blocks as reclaim kicks in
2731  */
2732 static void setup_zone_migrate_reserve(struct zone *zone)
2733 {
2734         unsigned long start_pfn, pfn, end_pfn;
2735         struct page *page;
2736         unsigned long reserve, block_migratetype;
2737
2738         /* Get the start pfn, end pfn and the number of blocks to reserve */
2739         start_pfn = zone->zone_start_pfn;
2740         end_pfn = start_pfn + zone->spanned_pages;
2741         reserve = roundup(min_wmark_pages(zone), pageblock_nr_pages) >>
2742                                                         pageblock_order;
2743
2744         for (pfn = start_pfn; pfn < end_pfn; pfn += pageblock_nr_pages) {
2745                 if (!pfn_valid(pfn))
2746                         continue;
2747                 page = pfn_to_page(pfn);
2748
2749                 /* Watch out for overlapping nodes */
2750                 if (page_to_nid(page) != zone_to_nid(zone))
2751                         continue;
2752
2753                 /* Blocks with reserved pages will never free, skip them. */
2754                 if (PageReserved(page))
2755                         continue;
2756
2757                 block_migratetype = get_pageblock_migratetype(page);
2758
2759                 /* If this block is reserved, account for it */
2760                 if (reserve > 0 && block_migratetype == MIGRATE_RESERVE) {
2761                         reserve--;
2762                         continue;
2763                 }
2764
2765                 /* Suitable for reserving if this block is movable */
2766                 if (reserve > 0 && block_migratetype == MIGRATE_MOVABLE) {
2767                         set_pageblock_migratetype(page, MIGRATE_RESERVE);
2768                         move_freepages_block(zone, page, MIGRATE_RESERVE);
2769                         reserve--;
2770                         continue;
2771                 }
2772
2773                 /*
2774                  * If the reserve is met and this is a previous reserved block,
2775                  * take it back
2776                  */
2777                 if (block_migratetype == MIGRATE_RESERVE) {
2778                         set_pageblock_migratetype(page, MIGRATE_MOVABLE);
2779                         move_freepages_block(zone, page, MIGRATE_MOVABLE);
2780                 }
2781         }
2782 }
2783
2784 /*
2785  * Initially all pages are reserved - free ones are freed
2786  * up by free_all_bootmem() once the early boot process is
2787  * done. Non-atomic initialization, single-pass.
2788  */
2789 void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
2790                 unsigned long start_pfn, enum memmap_context context)
2791 {
2792         struct page *page;
2793         unsigned long end_pfn = start_pfn + size;
2794         unsigned long pfn;
2795         struct zone *z;
2796
2797         if (highest_memmap_pfn < end_pfn - 1)
2798                 highest_memmap_pfn = end_pfn - 1;
2799
2800         z = &NODE_DATA(nid)->node_zones[zone];
2801         for (pfn = start_pfn; pfn < end_pfn; pfn++) {
2802                 /*
2803                  * There can be holes in boot-time mem_map[]s
2804                  * handed to this function.  They do not
2805                  * exist on hotplugged memory.
2806                  */
2807                 if (context == MEMMAP_EARLY) {
2808                         if (!early_pfn_valid(pfn))
2809                                 continue;
2810                         if (!early_pfn_in_nid(pfn, nid))
2811                                 continue;
2812                 }
2813                 page = pfn_to_page(pfn);
2814                 set_page_links(page, zone, nid, pfn);
2815                 mminit_verify_page_links(page, zone, nid, pfn);
2816                 init_page_count(page);
2817                 reset_page_mapcount(page);
2818                 SetPageReserved(page);
2819                 /*
2820                  * Mark the block movable so that blocks are reserved for
2821                  * movable at startup. This will force kernel allocations
2822                  * to reserve their blocks rather than leaking throughout
2823                  * the address space during boot when many long-lived
2824                  * kernel allocations are made. Later some blocks near
2825                  * the start are marked MIGRATE_RESERVE by
2826                  * setup_zone_migrate_reserve()
2827                  *
2828                  * bitmap is created for zone's valid pfn range. but memmap
2829                  * can be created for invalid pages (for alignment)
2830                  * check here not to call set_pageblock_migratetype() against
2831                  * pfn out of zone.
2832                  */
2833                 if ((z->zone_start_pfn <= pfn)
2834                     && (pfn < z->zone_start_pfn + z->spanned_pages)
2835                     && !(pfn & (pageblock_nr_pages - 1)))
2836                         set_pageblock_migratetype(page, MIGRATE_MOVABLE);
2837
2838                 INIT_LIST_HEAD(&page->lru);
2839 #ifdef WANT_PAGE_VIRTUAL
2840                 /* The shift won't overflow because ZONE_NORMAL is below 4G. */
2841                 if (!is_highmem_idx(zone))
2842                         set_page_address(page, __va(pfn << PAGE_SHIFT));
2843 #endif
2844         }
2845 }
2846
2847 static void __meminit zone_init_free_lists(struct zone *zone)
2848 {
2849         int order, t;
2850         for_each_migratetype_order(order, t) {
2851                 INIT_LIST_HEAD(&zone->free_area[order].free_list[t]);
2852                 zone->free_area[order].nr_free = 0;
2853         }
2854 }
2855
2856 #ifndef __HAVE_ARCH_MEMMAP_INIT
2857 #define memmap_init(size, nid, zone, start_pfn) \
2858         memmap_init_zone((size), (nid), (zone), (start_pfn), MEMMAP_EARLY)
2859 #endif
2860
2861 static int zone_batchsize(struct zone *zone)
2862 {
2863 #ifdef CONFIG_MMU
2864         int batch;
2865
2866         /*
2867          * The per-cpu-pages pools are set to around 1000th of the
2868          * size of the zone.  But no more than 1/2 of a meg.
2869          *
2870          * OK, so we don't know how big the cache is.  So guess.
2871          */
2872         batch = zone->present_pages / 1024;
2873         if (batch * PAGE_SIZE > 512 * 1024)
2874                 batch = (512 * 1024) / PAGE_SIZE;
2875         batch /= 4;             /* We effectively *= 4 below */
2876         if (batch < 1)
2877                 batch = 1;
2878
2879         /*
2880          * Clamp the batch to a 2^n - 1 value. Having a power
2881          * of 2 value was found to be more likely to have
2882          * suboptimal cache aliasing properties in some cases.
2883          *
2884          * For example if 2 tasks are alternately allocating
2885          * batches of pages, one task can end up with a lot
2886          * of pages of one half of the possible page colors
2887          * and the other with pages of the other colors.
2888          */
2889         batch = rounddown_pow_of_two(batch + batch/2) - 1;
2890
2891         return batch;
2892
2893 #else
2894         /* The deferral and batching of frees should be suppressed under NOMMU
2895          * conditions.
2896          *
2897          * The problem is that NOMMU needs to be able to allocate large chunks
2898          * of contiguous memory as there's no hardware page translation to
2899          * assemble apparent contiguous memory from discontiguous pages.
2900          *
2901          * Queueing large contiguous runs of pages for batching, however,
2902          * causes the pages to actually be freed in smaller chunks.  As there
2903          * can be a significant delay between the individual batches being
2904          * recycled, this leads to the once large chunks of space being
2905          * fragmented and becoming unavailable for high-order allocations.
2906          */
2907         return 0;
2908 #endif
2909 }
2910
2911 static void setup_pageset(struct per_cpu_pageset *p, unsigned long batch)
2912 {
2913         struct per_cpu_pages *pcp;
2914
2915         memset(p, 0, sizeof(*p));
2916
2917         pcp = &p->pcp;
2918         pcp->count = 0;
2919         pcp->high = 6 * batch;
2920         pcp->batch = max(1UL, 1 * batch);
2921         INIT_LIST_HEAD(&pcp->list);
2922 }
2923
2924 /*
2925  * setup_pagelist_highmark() sets the high water mark for hot per_cpu_pagelist
2926  * to the value high for the pageset p.
2927  */
2928
2929 static void setup_pagelist_highmark(struct per_cpu_pageset *p,
2930                                 unsigned long high)
2931 {
2932         struct per_cpu_pages *pcp;
2933
2934         pcp = &p->pcp;
2935         pcp->high = high;
2936         pcp->batch = max(1UL, high/4);
2937         if ((high/4) > (PAGE_SHIFT * 8))
2938                 pcp->batch = PAGE_SHIFT * 8;
2939 }
2940
2941
2942 #ifdef CONFIG_NUMA
2943 /*
2944  * Boot pageset table. One per cpu which is going to be used for all
2945  * zones and all nodes. The parameters will be set in such a way
2946  * that an item put on a list will immediately be handed over to
2947  * the buddy list. This is safe since pageset manipulation is done
2948  * with interrupts disabled.
2949  *
2950  * Some NUMA counter updates may also be caught by the boot pagesets.
2951  *
2952  * The boot_pagesets must be kept even after bootup is complete for
2953  * unused processors and/or zones. They do play a role for bootstrapping
2954  * hotplugged processors.
2955  *
2956  * zoneinfo_show() and maybe other functions do
2957  * not check if the processor is online before following the pageset pointer.
2958  * Other parts of the kernel may not check if the zone is available.
2959  */
2960 static struct per_cpu_pageset boot_pageset[NR_CPUS];
2961
2962 /*
2963  * Dynamically allocate memory for the
2964  * per cpu pageset array in struct zone.
2965  */
2966 static int __cpuinit process_zones(int cpu)
2967 {
2968         struct zone *zone, *dzone;
2969         int node = cpu_to_node(cpu);
2970
2971         node_set_state(node, N_CPU);    /* this node has a cpu */
2972
2973         for_each_populated_zone(zone) {
2974                 zone_pcp(zone, cpu) = kmalloc_node(sizeof(struct per_cpu_pageset),
2975                                          GFP_KERNEL, node);
2976                 if (!zone_pcp(zone, cpu))
2977                         goto bad;
2978
2979                 setup_pageset(zone_pcp(zone, cpu), zone_batchsize(zone));
2980
2981                 if (percpu_pagelist_fraction)
2982                         setup_pagelist_highmark(zone_pcp(zone, cpu),
2983                                 (zone->present_pages / percpu_pagelist_fraction));
2984         }
2985
2986         return 0;
2987 bad:
2988         for_each_zone(dzone) {
2989                 if (!populated_zone(dzone))
2990                         continue;
2991                 if (dzone == zone)
2992                         break;
2993                 kfree(zone_pcp(dzone, cpu));
2994                 zone_pcp(dzone, cpu) = NULL;
2995         }
2996         return -ENOMEM;
2997 }
2998
2999 static inline void free_zone_pagesets(int cpu)
3000 {
3001         struct zone *zone;
3002
3003         for_each_zone(zone) {
3004                 struct per_cpu_pageset *pset = zone_pcp(zone, cpu);
3005
3006                 /* Free per_cpu_pageset if it is slab allocated */
3007                 if (pset != &boot_pageset[cpu])
3008                         kfree(pset);
3009                 zone_pcp(zone, cpu) = NULL;
3010         }
3011 }
3012
3013 static int __cpuinit pageset_cpuup_callback(struct notifier_block *nfb,
3014                 unsigned long action,
3015                 void *hcpu)
3016 {
3017         int cpu = (long)hcpu;
3018         int ret = NOTIFY_OK;
3019
3020         switch (action) {
3021         case CPU_UP_PREPARE:
3022         case CPU_UP_PREPARE_FROZEN:
3023                 if (process_zones(cpu))
3024                         ret = NOTIFY_BAD;
3025                 break;
3026         case CPU_UP_CANCELED:
3027         case CPU_UP_CANCELED_FROZEN:
3028         case CPU_DEAD:
3029         case CPU_DEAD_FROZEN:
3030                 free_zone_pagesets(cpu);
3031                 break;
3032         default:
3033                 break;
3034         }
3035         return ret;
3036 }
3037
3038 static struct notifier_block __cpuinitdata pageset_notifier =
3039         { &pageset_cpuup_callback, NULL, 0 };
3040
3041 void __init setup_per_cpu_pageset(void)
3042 {
3043         int err;
3044
3045         /* Initialize per_cpu_pageset for cpu 0.
3046          * A cpuup callback will do this for every cpu
3047          * as it comes online
3048          */
3049         err = process_zones(smp_processor_id());
3050         BUG_ON(err);
3051         register_cpu_notifier(&pageset_notifier);
3052 }
3053
3054 #endif
3055
3056 static noinline __init_refok
3057 int zone_wait_table_init(struct zone *zone, unsigned long zone_size_pages)
3058 {
3059         int i;
3060         struct pglist_data *pgdat = zone->zone_pgdat;
3061         size_t alloc_size;
3062
3063         /*
3064          * The per-page waitqueue mechanism uses hashed waitqueues
3065          * per zone.
3066          */
3067         zone->wait_table_hash_nr_entries =
3068                  wait_table_hash_nr_entries(zone_size_pages);
3069         zone->wait_table_bits =
3070                 wait_table_bits(zone->wait_table_hash_nr_entries);
3071         alloc_size = zone->wait_table_hash_nr_entries
3072                                         * sizeof(wait_queue_head_t);
3073
3074         if (!slab_is_available()) {
3075                 zone->wait_table = (wait_queue_head_t *)
3076                         alloc_bootmem_node(pgdat, alloc_size);
3077         } else {
3078                 /*
3079                  * This case means that a zone whose size was 0 gets new memory
3080                  * via memory hot-add.
3081                  * But it may be the case that a new node was hot-added.  In
3082                  * this case vmalloc() will not be able to use this new node's
3083                  * memory - this wait_table must be initialized to use this new
3084                  * node itself as well.
3085                  * To use this new node's memory, further consideration will be
3086                  * necessary.
3087                  */
3088                 zone->wait_table = vmalloc(alloc_size);
3089         }
3090         if (!zone->wait_table)
3091                 return -ENOMEM;
3092
3093         for(i = 0; i < zone->wait_table_hash_nr_entries; ++i)
3094                 init_waitqueue_head(zone->wait_table + i);
3095
3096         return 0;
3097 }
3098
3099 static __meminit void zone_pcp_init(struct zone *zone)
3100 {
3101         int cpu;
3102         unsigned long batch = zone_batchsize(zone);
3103
3104         for (cpu = 0; cpu < NR_CPUS; cpu++) {
3105 #ifdef CONFIG_NUMA
3106                 /* Early boot. Slab allocator not functional yet */
3107                 zone_pcp(zone, cpu) = &boot_pageset[cpu];
3108                 setup_pageset(&boot_pageset[cpu],0);
3109 #else
3110                 setup_pageset(zone_pcp(zone,cpu), batch);
3111 #endif
3112         }
3113         if (zone->present_pages)
3114                 printk(KERN_DEBUG "  %s zone: %lu pages, LIFO batch:%lu\n",
3115                         zone->name, zone->present_pages, batch);
3116 }
3117
3118 __meminit int init_currently_empty_zone(struct zone *zone,
3119                                         unsigned long zone_start_pfn,
3120                                         unsigned long size,
3121                                         enum memmap_context context)
3122 {
3123         struct pglist_data *pgdat = zone->zone_pgdat;
3124         int ret;
3125         ret = zone_wait_table_init(zone, size);
3126         if (ret)
3127                 return ret;
3128         pgdat->nr_zones = zone_idx(zone) + 1;
3129
3130         zone->zone_start_pfn = zone_start_pfn;
3131
3132         mminit_dprintk(MMINIT_TRACE, "memmap_init",
3133                         "Initialising map node %d zone %lu pfns %lu -> %lu\n",
3134                         pgdat->node_id,
3135                         (unsigned long)zone_idx(zone),
3136                         zone_start_pfn, (zone_start_pfn + size));
3137
3138         zone_init_free_lists(zone);
3139
3140         return 0;
3141 }
3142
3143 #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
3144 /*
3145  * Basic iterator support. Return the first range of PFNs for a node
3146  * Note: nid == MAX_NUMNODES returns first region regardless of node
3147  */
3148 static int __meminit first_active_region_index_in_nid(int nid)
3149 {
3150         int i;
3151
3152         for (i = 0; i < nr_nodemap_entries; i++)
3153                 if (nid == MAX_NUMNODES || early_node_map[i].nid == nid)
3154                         return i;
3155
3156         return -1;
3157 }
3158
3159 /*
3160  * Basic iterator support. Return the next active range of PFNs for a node
3161  * Note: nid == MAX_NUMNODES returns next region regardless of node
3162  */
3163 static int __meminit next_active_region_index_in_nid(int index, int nid)
3164 {
3165         for (index = index + 1; index < nr_nodemap_entries; index++)
3166                 if (nid == MAX_NUMNODES || early_node_map[index].nid == nid)
3167                         return index;
3168
3169         return -1;
3170 }
3171
3172 #ifndef CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID
3173 /*
3174  * Required by SPARSEMEM. Given a PFN, return what node the PFN is on.
3175  * Architectures may implement their own version but if add_active_range()
3176  * was used and there are no special requirements, this is a convenient
3177  * alternative
3178  */
3179 int __meminit __early_pfn_to_nid(unsigned long pfn)
3180 {
3181         int i;
3182
3183         for (i = 0; i < nr_nodemap_entries; i++) {
3184                 unsigned long start_pfn = early_node_map[i].start_pfn;
3185                 unsigned long end_pfn = early_node_map[i].end_pfn;
3186
3187                 if (start_pfn <= pfn && pfn < end_pfn)
3188                         return early_node_map[i].nid;
3189         }
3190         /* This is a memory hole */
3191         return -1;
3192 }
3193 #endif /* CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID */
3194
3195 int __meminit early_pfn_to_nid(unsigned long pfn)
3196 {
3197         int nid;
3198
3199         nid = __early_pfn_to_nid(pfn);
3200         if (nid >= 0)
3201                 return nid;
3202         /* just returns 0 */
3203         return 0;
3204 }
3205
3206 #ifdef CONFIG_NODES_SPAN_OTHER_NODES
3207 bool __meminit early_pfn_in_nid(unsigned long pfn, int node)
3208 {
3209         int nid;
3210
3211         nid = __early_pfn_to_nid(pfn);
3212         if (nid >= 0 && nid != node)
3213                 return false;
3214         return true;
3215 }
3216 #endif
3217
3218 /* Basic iterator support to walk early_node_map[] */
3219 #define for_each_active_range_index_in_nid(i, nid) \
3220         for (i = first_active_region_index_in_nid(nid); i != -1; \
3221                                 i = next_active_region_index_in_nid(i, nid))
3222
3223 /**
3224  * free_bootmem_with_active_regions - Call free_bootmem_node for each active range
3225  * @nid: The node to free memory on. If MAX_NUMNODES, all nodes are freed.
3226  * @max_low_pfn: The highest PFN that will be passed to free_bootmem_node
3227  *
3228  * If an architecture guarantees that all ranges registered with
3229  * add_active_ranges() contain no holes and may be freed, this
3230  * this function may be used instead of calling free_bootmem() manually.
3231  */
3232 void __init free_bootmem_with_active_regions(int nid,
3233                                                 unsigned long max_low_pfn)
3234 {
3235         int i;
3236
3237         for_each_active_range_index_in_nid(i, nid) {
3238                 unsigned long size_pages = 0;
3239                 unsigned long end_pfn = early_node_map[i].end_pfn;
3240
3241                 if (early_node_map[i].start_pfn >= max_low_pfn)
3242                         continue;
3243
3244                 if (end_pfn > max_low_pfn)
3245                         end_pfn = max_low_pfn;
3246
3247                 size_pages = end_pfn - early_node_map[i].start_pfn;
3248                 free_bootmem_node(NODE_DATA(early_node_map[i].nid),
3249                                 PFN_PHYS(early_node_map[i].start_pfn),
3250                                 size_pages << PAGE_SHIFT);
3251         }
3252 }
3253
3254 void __init work_with_active_regions(int nid, work_fn_t work_fn, void *data)
3255 {
3256         int i;
3257         int ret;
3258
3259         for_each_active_range_index_in_nid(i, nid) {
3260                 ret = work_fn(early_node_map[i].start_pfn,
3261                               early_node_map[i].end_pfn, data);
3262                 if (ret)
3263                         break;
3264         }
3265 }
3266 /**
3267  * sparse_memory_present_with_active_regions - Call memory_present for each active range
3268  * @nid: The node to call memory_present for. If MAX_NUMNODES, all nodes will be used.
3269  *
3270  * If an architecture guarantees that all ranges registered with
3271  * add_active_ranges() contain no holes and may be freed, this
3272  * function may be used instead of calling memory_present() manually.
3273  */
3274 void __init sparse_memory_present_with_active_regions(int nid)
3275 {
3276         int i;
3277
3278         for_each_active_range_index_in_nid(i, nid)
3279                 memory_present(early_node_map[i].nid,
3280                                 early_node_map[i].start_pfn,
3281                                 early_node_map[i].end_pfn);
3282 }
3283
3284 /**
3285  * get_pfn_range_for_nid - Return the start and end page frames for a node
3286  * @nid: The nid to return the range for. If MAX_NUMNODES, the min and max PFN are returned.
3287  * @start_pfn: Passed by reference. On return, it will have the node start_pfn.
3288  * @end_pfn: Passed by reference. On return, it will have the node end_pfn.
3289  *
3290  * It returns the start and end page frame of a node based on information
3291  * provided by an arch calling add_active_range(). If called for a node
3292  * with no available memory, a warning is printed and the start and end
3293  * PFNs will be 0.
3294  */
3295 void __meminit get_pfn_range_for_nid(unsigned int nid,
3296                         unsigned long *start_pfn, unsigned long *end_pfn)
3297 {
3298         int i;
3299         *start_pfn = -1UL;
3300         *end_pfn = 0;
3301
3302         for_each_active_range_index_in_nid(i, nid) {
3303                 *start_pfn = min(*start_pfn, early_node_map[i].start_pfn);
3304                 *end_pfn = max(*end_pfn, early_node_map[i].end_pfn);
3305         }
3306
3307         if (*start_pfn == -1UL)
3308                 *start_pfn = 0;
3309 }
3310
3311 /*
3312  * This finds a zone that can be used for ZONE_MOVABLE pages. The
3313  * assumption is made that zones within a node are ordered in monotonic
3314  * increasing memory addresses so that the "highest" populated zone is used
3315  */
3316 static void __init find_usable_zone_for_movable(void)
3317 {
3318         int zone_index;
3319         for (zone_index = MAX_NR_ZONES - 1; zone_index >= 0; zone_index--) {
3320                 if (zone_index == ZONE_MOVABLE)
3321                         continue;
3322
3323                 if (arch_zone_highest_possible_pfn[zone_index] >
3324                                 arch_zone_lowest_possible_pfn[zone_index])
3325                         break;
3326         }
3327
3328         VM_BUG_ON(zone_index == -1);
3329         movable_zone = zone_index;
3330 }
3331
3332 /*
3333  * The zone ranges provided by the architecture do not include ZONE_MOVABLE
3334  * because it is sized independant of architecture. Unlike the other zones,
3335  * the starting point for ZONE_MOVABLE is not fixed. It may be different
3336  * in each node depending on the size of each node and how evenly kernelcore
3337  * is distributed. This helper function adjusts the zone ranges
3338  * provided by the architecture for a given node by using the end of the
3339  * highest usable zone for ZONE_MOVABLE. This preserves the assumption that
3340  * zones within a node are in order of monotonic increases memory addresses
3341  */
3342 static void __meminit adjust_zone_range_for_zone_movable(int nid,
3343                                         unsigned long zone_type,
3344                                         unsigned long node_start_pfn,
3345                                         unsigned long node_end_pfn,
3346                                         unsigned long *zone_start_pfn,
3347                                         unsigned long *zone_end_pfn)
3348 {
3349         /* Only adjust if ZONE_MOVABLE is on this node */
3350         if (zone_movable_pfn[nid]) {
3351                 /* Size ZONE_MOVABLE */
3352                 if (zone_type == ZONE_MOVABLE) {
3353                         *zone_start_pfn = zone_movable_pfn[nid];
3354                         *zone_end_pfn = min(node_end_pfn,
3355                                 arch_zone_highest_possible_pfn[movable_zone]);
3356
3357                 /* Adjust for ZONE_MOVABLE starting within this range */
3358                 } else if (*zone_start_pfn < zone_movable_pfn[nid] &&
3359                                 *zone_end_pfn > zone_movable_pfn[nid]) {
3360                         *zone_end_pfn = zone_movable_pfn[nid];
3361
3362                 /* Check if this whole range is within ZONE_MOVABLE */
3363                 } else if (*zone_start_pfn >= zone_movable_pfn[nid])
3364                         *zone_start_pfn = *zone_end_pfn;
3365         }
3366 }
3367
3368 /*
3369  * Return the number of pages a zone spans in a node, including holes
3370  * present_pages = zone_spanned_pages_in_node() - zone_absent_pages_in_node()
3371  */
3372 static unsigned long __meminit zone_spanned_pages_in_node(int nid,
3373                                         unsigned long zone_type,
3374                                         unsigned long *ignored)
3375 {
3376         unsigned long node_start_pfn, node_end_pfn;
3377         unsigned long zone_start_pfn, zone_end_pfn;
3378
3379         /* Get the start and end of the node and zone */
3380         get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
3381         zone_start_pfn = arch_zone_lowest_possible_pfn[zone_type];
3382         zone_end_pfn = arch_zone_highest_possible_pfn[zone_type];
3383         adjust_zone_range_for_zone_movable(nid, zone_type,
3384                                 node_start_pfn, node_end_pfn,
3385                                 &zone_start_pfn, &zone_end_pfn);
3386
3387         /* Check that this node has pages within the zone's required range */
3388         if (zone_end_pfn < node_start_pfn || zone_start_pfn > node_end_pfn)
3389                 return 0;
3390
3391         /* Move the zone boundaries inside the node if necessary */
3392         zone_end_pfn = min(zone_end_pfn, node_end_pfn);
3393         zone_start_pfn = max(zone_start_pfn, node_start_pfn);
3394
3395         /* Return the spanned pages */
3396         return zone_end_pfn - zone_start_pfn;
3397 }
3398
3399 /*
3400  * Return the number of holes in a range on a node. If nid is MAX_NUMNODES,
3401  * then all holes in the requested range will be accounted for.
3402  */
3403 static unsigned long __meminit __absent_pages_in_range(int nid,
3404                                 unsigned long range_start_pfn,
3405                                 unsigned long range_end_pfn)
3406 {
3407         int i = 0;
3408         unsigned long prev_end_pfn = 0, hole_pages = 0;
3409         unsigned long start_pfn;
3410
3411         /* Find the end_pfn of the first active range of pfns in the node */
3412         i = first_active_region_index_in_nid(nid);
3413         if (i == -1)
3414                 return 0;
3415
3416         prev_end_pfn = min(early_node_map[i].start_pfn, range_end_pfn);
3417
3418         /* Account for ranges before physical memory on this node */
3419         if (early_node_map[i].start_pfn > range_start_pfn)
3420                 hole_pages = prev_end_pfn - range_start_pfn;
3421
3422         /* Find all holes for the zone within the node */
3423         for (; i != -1; i = next_active_region_index_in_nid(i, nid)) {
3424
3425                 /* No need to continue if prev_end_pfn is outside the zone */
3426                 if (prev_end_pfn >= range_end_pfn)
3427                         break;
3428
3429                 /* Make sure the end of the zone is not within the hole */
3430                 start_pfn = min(early_node_map[i].start_pfn, range_end_pfn);
3431                 prev_end_pfn = max(prev_end_pfn, range_start_pfn);
3432
3433                 /* Update the hole size cound and move on */
3434                 if (start_pfn > range_start_pfn) {
3435                         BUG_ON(prev_end_pfn > start_pfn);
3436                         hole_pages += start_pfn - prev_end_pfn;
3437                 }
3438                 prev_end_pfn = early_node_map[i].end_pfn;
3439         }
3440
3441         /* Account for ranges past physical memory on this node */
3442         if (range_end_pfn > prev_end_pfn)
3443                 hole_pages += range_end_pfn -
3444                                 max(range_start_pfn, prev_end_pfn);
3445
3446         return hole_pages;
3447 }
3448
3449 /**
3450  * absent_pages_in_range - Return number of page frames in holes within a range
3451  * @start_pfn: The start PFN to start searching for holes
3452  * @end_pfn: The end PFN to stop searching for holes
3453  *
3454  * It returns the number of pages frames in memory holes within a range.
3455  */
3456 unsigned long __init absent_pages_in_range(unsigned long start_pfn,
3457                                                         unsigned long end_pfn)
3458 {
3459         return __absent_pages_in_range(MAX_NUMNODES, start_pfn, end_pfn);
3460 }
3461
3462 /* Return the number of page frames in holes in a zone on a node */
3463 static unsigned long __meminit zone_absent_pages_in_node(int nid,
3464                                         unsigned long zone_type,
3465                                         unsigned long *ignored)
3466 {
3467         unsigned long node_start_pfn, node_end_pfn;
3468         unsigned long zone_start_pfn, zone_end_pfn;
3469
3470         get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
3471         zone_start_pfn = max(arch_zone_lowest_possible_pfn[zone_type],
3472                                                         node_start_pfn);
3473         zone_end_pfn = min(arch_zone_highest_possible_pfn[zone_type],
3474                                                         node_end_pfn);
3475
3476         adjust_zone_range_for_zone_movable(nid, zone_type,
3477                         node_start_pfn, node_end_pfn,
3478                         &zone_start_pfn, &zone_end_pfn);
3479         return __absent_pages_in_range(nid, zone_start_pfn, zone_end_pfn);
3480 }
3481
3482 #else
3483 static inline unsigned long __meminit zone_spanned_pages_in_node(int nid,
3484                                         unsigned long zone_type,
3485                                         unsigned long *zones_size)
3486 {
3487         return zones_size[zone_type];
3488 }
3489
3490 static inline unsigned long __meminit zone_absent_pages_in_node(int nid,
3491                                                 unsigned long zone_type,
3492                                                 unsigned long *zholes_size)
3493 {
3494         if (!zholes_size)
3495                 return 0;
3496
3497         return zholes_size[zone_type];
3498 }
3499
3500 #endif
3501
3502 static void __meminit calculate_node_totalpages(struct pglist_data *pgdat,
3503                 unsigned long *zones_size, unsigned long *zholes_size)
3504 {
3505         unsigned long realtotalpages, totalpages = 0;
3506         enum zone_type i;
3507
3508         for (i = 0; i < MAX_NR_ZONES; i++)
3509                 totalpages += zone_spanned_pages_in_node(pgdat->node_id, i,
3510                                                                 zones_size);
3511         pgdat->node_spanned_pages = totalpages;
3512
3513         realtotalpages = totalpages;
3514         for (i = 0; i < MAX_NR_ZONES; i++)
3515                 realtotalpages -=
3516                         zone_absent_pages_in_node(pgdat->node_id, i,
3517                                                                 zholes_size);
3518         pgdat->node_present_pages = realtotalpages;
3519         printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id,
3520                                                         realtotalpages);
3521 }
3522
3523 #ifndef CONFIG_SPARSEMEM
3524 /*
3525  * Calculate the size of the zone->blockflags rounded to an unsigned long
3526  * Start by making sure zonesize is a multiple of pageblock_order by rounding
3527  * up. Then use 1 NR_PAGEBLOCK_BITS worth of bits per pageblock, finally
3528  * round what is now in bits to nearest long in bits, then return it in
3529  * bytes.
3530  */
3531 static unsigned long __init usemap_size(unsigned long zonesize)
3532 {
3533         unsigned long usemapsize;
3534
3535         usemapsize = roundup(zonesize, pageblock_nr_pages);
3536         usemapsize = usemapsize >> pageblock_order;
3537         usemapsize *= NR_PAGEBLOCK_BITS;
3538         usemapsize = roundup(usemapsize, 8 * sizeof(unsigned long));
3539
3540         return usemapsize / 8;
3541 }
3542
3543 static void __init setup_usemap(struct pglist_data *pgdat,
3544                                 struct zone *zone, unsigned long zonesize)
3545 {
3546         unsigned long usemapsize = usemap_size(zonesize);
3547         zone->pageblock_flags = NULL;
3548         if (usemapsize)
3549                 zone->pageblock_flags = alloc_bootmem_node(pgdat, usemapsize);
3550 }
3551 #else
3552 static void inline setup_usemap(struct pglist_data *pgdat,
3553                                 struct zone *zone, unsigned long zonesize) {}
3554 #endif /* CONFIG_SPARSEMEM */
3555
3556 #ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
3557
3558 /* Return a sensible default order for the pageblock size. */
3559 static inline int pageblock_default_order(void)
3560 {
3561         if (HPAGE_SHIFT > PAGE_SHIFT)
3562                 return HUGETLB_PAGE_ORDER;
3563
3564         return MAX_ORDER-1;
3565 }
3566
3567 /* Initialise the number of pages represented by NR_PAGEBLOCK_BITS */
3568 static inline void __init set_pageblock_order(unsigned int order)
3569 {
3570         /* Check that pageblock_nr_pages has not already been setup */
3571         if (pageblock_order)
3572                 return;
3573
3574         /*
3575          * Assume the largest contiguous order of interest is a huge page.
3576          * This value may be variable depending on boot parameters on IA64
3577          */
3578         pageblock_order = order;
3579 }
3580 #else /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */
3581
3582 /*
3583  * When CONFIG_HUGETLB_PAGE_SIZE_VARIABLE is not set, set_pageblock_order()
3584  * and pageblock_default_order() are unused as pageblock_order is set
3585  * at compile-time. See include/linux/pageblock-flags.h for the values of
3586  * pageblock_order based on the kernel config
3587  */
3588 static inline int pageblock_default_order(unsigned int order)
3589 {
3590         return MAX_ORDER-1;
3591 }
3592 #define set_pageblock_order(x)  do {} while (0)
3593
3594 #endif /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */
3595
3596 /*
3597  * Set up the zone data structures:
3598  *   - mark all pages reserved
3599  *   - mark all memory queues empty
3600  *   - clear the memory bitmaps
3601  */
3602 static void __paginginit free_area_init_core(struct pglist_data *pgdat,
3603                 unsigned long *zones_size, unsigned long *zholes_size)
3604 {
3605         enum zone_type j;
3606         int nid = pgdat->node_id;
3607         unsigned long zone_start_pfn = pgdat->node_start_pfn;
3608         int ret;
3609
3610         pgdat_resize_init(pgdat);
3611         pgdat->nr_zones = 0;
3612         init_waitqueue_head(&pgdat->kswapd_wait);
3613         pgdat->kswapd_max_order = 0;
3614         pgdat_page_cgroup_init(pgdat);
3615         
3616         for (j = 0; j < MAX_NR_ZONES; j++) {
3617                 struct zone *zone = pgdat->node_zones + j;
3618                 unsigned long size, realsize, memmap_pages;
3619                 enum lru_list l;
3620
3621                 size = zone_spanned_pages_in_node(nid, j, zones_size);
3622                 realsize = size - zone_absent_pages_in_node(nid, j,
3623                                                                 zholes_size);
3624
3625                 /*
3626                  * Adjust realsize so that it accounts for how much memory
3627                  * is used by this zone for memmap. This affects the watermark
3628                  * and per-cpu initialisations
3629                  */
3630                 memmap_pages =
3631                         PAGE_ALIGN(size * sizeof(struct page)) >> PAGE_SHIFT;
3632                 if (realsize >= memmap_pages) {
3633                         realsize -= memmap_pages;
3634                         if (memmap_pages)
3635                                 printk(KERN_DEBUG
3636                                        "  %s zone: %lu pages used for memmap\n",
3637                                        zone_names[j], memmap_pages);
3638                 } else
3639                         printk(KERN_WARNING
3640                                 "  %s zone: %lu pages exceeds realsize %lu\n",
3641                                 zone_names[j], memmap_pages, realsize);
3642
3643                 /* Account for reserved pages */
3644                 if (j == 0 && realsize > dma_reserve) {
3645                         realsize -= dma_reserve;
3646                         printk(KERN_DEBUG "  %s zone: %lu pages reserved\n",
3647                                         zone_names[0], dma_reserve);
3648                 }
3649
3650                 if (!is_highmem_idx(j))
3651                         nr_kernel_pages += realsize;
3652                 nr_all_pages += realsize;
3653
3654                 zone->spanned_pages = size;
3655                 zone->present_pages = realsize;
3656 #ifdef CONFIG_NUMA
3657                 zone->node = nid;
3658                 zone->min_unmapped_pages = (realsize*sysctl_min_unmapped_ratio)
3659                                                 / 100;
3660                 zone->min_slab_pages = (realsize * sysctl_min_slab_ratio) / 100;
3661 #endif
3662                 zone->name = zone_names[j];
3663                 spin_lock_init(&zone->lock);
3664                 spin_lock_init(&zone->lru_lock);
3665                 zone_seqlock_init(zone);
3666                 zone->zone_pgdat = pgdat;
3667
3668                 zone->prev_priority = DEF_PRIORITY;
3669
3670                 zone_pcp_init(zone);
3671                 for_each_lru(l) {
3672                         INIT_LIST_HEAD(&zone->lru[l].list);
3673                         zone->lru[l].nr_saved_scan = 0;
3674                 }
3675                 zone->reclaim_stat.recent_rotated[0] = 0;
3676                 zone->reclaim_stat.recent_rotated[1] = 0;
3677                 zone->reclaim_stat.recent_scanned[0] = 0;
3678                 zone->reclaim_stat.recent_scanned[1] = 0;
3679                 zap_zone_vm_stats(zone);
3680                 zone->flags = 0;
3681                 if (!size)
3682                         continue;
3683
3684                 set_pageblock_order(pageblock_default_order());
3685                 setup_usemap(pgdat, zone, size);
3686                 ret = init_currently_empty_zone(zone, zone_start_pfn,
3687                                                 size, MEMMAP_EARLY);
3688                 BUG_ON(ret);
3689                 memmap_init(size, nid, j, zone_start_pfn);
3690                 zone_start_pfn += size;
3691         }
3692 }
3693
3694 static void __init_refok alloc_node_mem_map(struct pglist_data *pgdat)
3695 {
3696         /* Skip empty nodes */
3697         if (!pgdat->node_spanned_pages)
3698                 return;
3699
3700 #ifdef CONFIG_FLAT_NODE_MEM_MAP
3701         /* ia64 gets its own node_mem_map, before this, without bootmem */
3702         if (!pgdat->node_mem_map) {
3703                 unsigned long size, start, end;
3704                 struct page *map;
3705
3706                 /*
3707                  * The zone's endpoints aren't required to be MAX_ORDER
3708                  * aligned but the node_mem_map endpoints must be in order
3709                  * for the buddy allocator to function correctly.
3710                  */
3711                 start = pgdat->node_start_pfn & ~(MAX_ORDER_NR_PAGES - 1);
3712                 end = pgdat->node_start_pfn + pgdat->node_spanned_pages;
3713                 end = ALIGN(end, MAX_ORDER_NR_PAGES);
3714                 size =  (end - start) * sizeof(struct page);
3715                 map = alloc_remap(pgdat->node_id, size);
3716                 if (!map)
3717                         map = alloc_bootmem_node(pgdat, size);
3718                 pgdat->node_mem_map = map + (pgdat->node_start_pfn - start);
3719         }
3720 #ifndef CONFIG_NEED_MULTIPLE_NODES
3721         /*
3722          * With no DISCONTIG, the global mem_map is just set as node 0's
3723          */
3724         if (pgdat == NODE_DATA(0)) {
3725                 mem_map = NODE_DATA(0)->node_mem_map;
3726 #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
3727                 if (page_to_pfn(mem_map) != pgdat->node_start_pfn)
3728                         mem_map -= (pgdat->node_start_pfn - ARCH_PFN_OFFSET);
3729 #endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
3730         }
3731 #endif
3732 #endif /* CONFIG_FLAT_NODE_MEM_MAP */
3733 }
3734
3735 void __paginginit free_area_init_node(int nid, unsigned long *zones_size,
3736                 unsigned long node_start_pfn, unsigned long *zholes_size)
3737 {
3738         pg_data_t *pgdat = NODE_DATA(nid);
3739
3740         pgdat->node_id = nid;
3741         pgdat->node_start_pfn = node_start_pfn;
3742         calculate_node_totalpages(pgdat, zones_size, zholes_size);
3743
3744         alloc_node_mem_map(pgdat);
3745 #ifdef CONFIG_FLAT_NODE_MEM_MAP
3746         printk(KERN_DEBUG "free_area_init_node: node %d, pgdat %08lx, node_mem_map %08lx\n",
3747                 nid, (unsigned long)pgdat,
3748                 (unsigned long)pgdat->node_mem_map);
3749 #endif
3750
3751         free_area_init_core(pgdat, zones_size, zholes_size);
3752 }
3753
3754 #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
3755
3756 #if MAX_NUMNODES > 1
3757 /*
3758  * Figure out the number of possible node ids.
3759  */
3760 static void __init setup_nr_node_ids(void)
3761 {
3762         unsigned int node;
3763         unsigned int highest = 0;
3764
3765         for_each_node_mask(node, node_possible_map)
3766                 highest = node;
3767         nr_node_ids = highest + 1;
3768 }
3769 #else
3770 static inline void setup_nr_node_ids(void)
3771 {
3772 }
3773 #endif
3774
3775 /**
3776  * add_active_range - Register a range of PFNs backed by physical memory
3777  * @nid: The node ID the range resides on
3778  * @start_pfn: The start PFN of the available physical memory
3779  * @end_pfn: The end PFN of the available physical memory
3780  *
3781  * These ranges are stored in an early_node_map[] and later used by
3782  * free_area_init_nodes() to calculate zone sizes and holes. If the
3783  * range spans a memory hole, it is up to the architecture to ensure
3784  * the memory is not freed by the bootmem allocator. If possible
3785  * the range being registered will be merged with existing ranges.
3786  */
3787 void __init add_active_range(unsigned int nid, unsigned long start_pfn,
3788                                                 unsigned long end_pfn)
3789 {
3790         int i;
3791
3792         mminit_dprintk(MMINIT_TRACE, "memory_register",
3793                         "Entering add_active_range(%d, %#lx, %#lx) "
3794                         "%d entries of %d used\n",
3795                         nid, start_pfn, end_pfn,
3796                         nr_nodemap_entries, MAX_ACTIVE_REGIONS);
3797
3798         mminit_validate_memmodel_limits(&start_pfn, &end_pfn);
3799
3800         /* Merge with existing active regions if possible */
3801         for (i = 0; i < nr_nodemap_entries; i++) {
3802                 if (early_node_map[i].nid != nid)
3803                         continue;
3804
3805                 /* Skip if an existing region covers this new one */
3806                 if (start_pfn >= early_node_map[i].start_pfn &&
3807                                 end_pfn <= early_node_map[i].end_pfn)
3808                         return;
3809
3810                 /* Merge forward if suitable */
3811                 if (start_pfn <= early_node_map[i].end_pfn &&
3812                                 end_pfn > early_node_map[i].end_pfn) {
3813                         early_node_map[i].end_pfn = end_pfn;
3814                         return;
3815                 }
3816
3817                 /* Merge backward if suitable */
3818                 if (start_pfn < early_node_map[i].end_pfn &&
3819                                 end_pfn >= early_node_map[i].start_pfn) {
3820                         early_node_map[i].start_pfn = start_pfn;
3821                         return;
3822                 }
3823         }
3824
3825         /* Check that early_node_map is large enough */
3826         if (i >= MAX_ACTIVE_REGIONS) {
3827                 printk(KERN_CRIT "More than %d memory regions, truncating\n",
3828                                                         MAX_ACTIVE_REGIONS);
3829                 return;
3830         }
3831
3832         early_node_map[i].nid = nid;
3833         early_node_map[i].start_pfn = start_pfn;
3834         early_node_map[i].end_pfn = end_pfn;
3835         nr_nodemap_entries = i + 1;
3836 }
3837
3838 /**
3839  * remove_active_range - Shrink an existing registered range of PFNs
3840  * @nid: The node id the range is on that should be shrunk
3841  * @start_pfn: The new PFN of the range
3842  * @end_pfn: The new PFN of the range
3843  *
3844  * i386 with NUMA use alloc_remap() to store a node_mem_map on a local node.
3845  * The map is kept near the end physical page range that has already been
3846  * registered. This function allows an arch to shrink an existing registered
3847  * range.
3848  */
3849 void __init remove_active_range(unsigned int nid, unsigned long start_pfn,
3850                                 unsigned long end_pfn)
3851 {
3852         int i, j;
3853         int removed = 0;
3854
3855         printk(KERN_DEBUG "remove_active_range (%d, %lu, %lu)\n",
3856                           nid, start_pfn, end_pfn);
3857
3858         /* Find the old active region end and shrink */
3859         for_each_active_range_index_in_nid(i, nid) {
3860                 if (early_node_map[i].start_pfn >= start_pfn &&
3861                     early_node_map[i].end_pfn <= end_pfn) {
3862                         /* clear it */
3863                         early_node_map[i].start_pfn = 0;
3864                         early_node_map[i].end_pfn = 0;
3865                         removed = 1;
3866                         continue;
3867                 }
3868                 if (early_node_map[i].start_pfn < start_pfn &&
3869                     early_node_map[i].end_pfn > start_pfn) {
3870                         unsigned long temp_end_pfn = early_node_map[i].end_pfn;
3871                         early_node_map[i].end_pfn = start_pfn;
3872                         if (temp_end_pfn > end_pfn)
3873                                 add_active_range(nid, end_pfn, temp_end_pfn);
3874                         continue;
3875                 }
3876                 if (early_node_map[i].start_pfn >= start_pfn &&
3877                     early_node_map[i].end_pfn > end_pfn &&
3878                     early_node_map[i].start_pfn < end_pfn) {
3879                         early_node_map[i].start_pfn = end_pfn;
3880                         continue;
3881                 }
3882         }
3883
3884         if (!removed)
3885                 return;
3886
3887         /* remove the blank ones */
3888         for (i = nr_nodemap_entries - 1; i > 0; i--) {
3889                 if (early_node_map[i].nid != nid)
3890                         continue;
3891                 if (early_node_map[i].end_pfn)
3892                         continue;
3893                 /* we found it, get rid of it */
3894                 for (j = i; j < nr_nodemap_entries - 1; j++)
3895                         memcpy(&early_node_map[j], &early_node_map[j+1],
3896                                 sizeof(early_node_map[j]));
3897                 j = nr_nodemap_entries - 1;
3898                 memset(&early_node_map[j], 0, sizeof(early_node_map[j]));
3899                 nr_nodemap_entries--;
3900         }
3901 }
3902
3903 /**
3904  * remove_all_active_ranges - Remove all currently registered regions
3905  *
3906  * During discovery, it may be found that a table like SRAT is invalid
3907  * and an alternative discovery method must be used. This function removes
3908  * all currently registered regions.
3909  */
3910 void __init remove_all_active_ranges(void)
3911 {
3912         memset(early_node_map, 0, sizeof(early_node_map));
3913         nr_nodemap_entries = 0;
3914 }
3915
3916 /* Compare two active node_active_regions */
3917 static int __init cmp_node_active_region(const void *a, const void *b)
3918 {
3919         struct node_active_region *arange = (struct node_active_region *)a;
3920         struct node_active_region *brange = (struct node_active_region *)b;
3921
3922         /* Done this way to avoid overflows */
3923         if (arange->start_pfn > brange->start_pfn)
3924                 return 1;
3925         if (arange->start_pfn < brange->start_pfn)
3926                 return -1;
3927
3928         return 0;
3929 }
3930
3931 /* sort the node_map by start_pfn */
3932 static void __init sort_node_map(void)
3933 {
3934         sort(early_node_map, (size_t)nr_nodemap_entries,
3935                         sizeof(struct node_active_region),
3936                         cmp_node_active_region, NULL);
3937 }
3938
3939 /* Find the lowest pfn for a node */
3940 static unsigned long __init find_min_pfn_for_node(int nid)
3941 {
3942         int i;
3943         unsigned long min_pfn = ULONG_MAX;
3944
3945         /* Assuming a sorted map, the first range found has the starting pfn */
3946         for_each_active_range_index_in_nid(i, nid)
3947                 min_pfn = min(min_pfn, early_node_map[i].start_pfn);
3948
3949         if (min_pfn == ULONG_MAX) {
3950                 printk(KERN_WARNING
3951                         "Could not find start_pfn for node %d\n", nid);
3952                 return 0;
3953         }
3954
3955         return min_pfn;
3956 }
3957
3958 /**
3959  * find_min_pfn_with_active_regions - Find the minimum PFN registered
3960  *
3961  * It returns the minimum PFN based on information provided via
3962  * add_active_range().
3963  */
3964 unsigned long __init find_min_pfn_with_active_regions(void)
3965 {
3966         return find_min_pfn_for_node(MAX_NUMNODES);
3967 }
3968
3969 /*
3970  * early_calculate_totalpages()
3971  * Sum pages in active regions for movable zone.
3972  * Populate N_HIGH_MEMORY for calculating usable_nodes.
3973  */
3974 static unsigned long __init early_calculate_totalpages(void)
3975 {
3976         int i;
3977         unsigned long totalpages = 0;
3978
3979         for (i = 0; i < nr_nodemap_entries; i++) {
3980                 unsigned long pages = early_node_map[i].end_pfn -
3981                                                 early_node_map[i].start_pfn;
3982                 totalpages += pages;
3983                 if (pages)
3984                         node_set_state(early_node_map[i].nid, N_HIGH_MEMORY);
3985         }
3986         return totalpages;
3987 }
3988
3989 /*
3990  * Find the PFN the Movable zone begins in each node. Kernel memory
3991  * is spread evenly between nodes as long as the nodes have enough
3992  * memory. When they don't, some nodes will have more kernelcore than
3993  * others
3994  */
3995 static void __init find_zone_movable_pfns_for_nodes(unsigned long *movable_pfn)
3996 {
3997         int i, nid;
3998         unsigned long usable_startpfn;
3999         unsigned long kernelcore_node, kernelcore_remaining;
4000         unsigned long totalpages = early_calculate_totalpages();
4001         int usable_nodes = nodes_weight(node_states[N_HIGH_MEMORY]);
4002
4003         /*
4004          * If movablecore was specified, calculate what size of
4005          * kernelcore that corresponds so that memory usable for
4006          * any allocation type is evenly spread. If both kernelcore
4007          * and movablecore are specified, then the value of kernelcore
4008          * will be used for required_kernelcore if it's greater than
4009          * what movablecore would have allowed.
4010          */
4011         if (required_movablecore) {
4012                 unsigned long corepages;
4013
4014                 /*
4015                  * Round-up so that ZONE_MOVABLE is at least as large as what
4016                  * was requested by the user
4017                  */
4018                 required_movablecore =
4019                         roundup(required_movablecore, MAX_ORDER_NR_PAGES);
4020                 corepages = totalpages - required_movablecore;
4021
4022                 required_kernelcore = max(required_kernelcore, corepages);
4023         }
4024
4025         /* If kernelcore was not specified, there is no ZONE_MOVABLE */
4026         if (!required_kernelcore)
4027                 return;
4028
4029         /* usable_startpfn is the lowest possible pfn ZONE_MOVABLE can be at */
4030         find_usable_zone_for_movable();
4031         usable_startpfn = arch_zone_lowest_possible_pfn[movable_zone];
4032
4033 restart:
4034         /* Spread kernelcore memory as evenly as possible throughout nodes */
4035         kernelcore_node = required_kernelcore / usable_nodes;
4036         for_each_node_state(nid, N_HIGH_MEMORY) {
4037                 /*
4038                  * Recalculate kernelcore_node if the division per node
4039                  * now exceeds what is necessary to satisfy the requested
4040                  * amount of memory for the kernel
4041                  */
4042                 if (required_kernelcore < kernelcore_node)
4043                         kernelcore_node = required_kernelcore / usable_nodes;
4044
4045                 /*
4046                  * As the map is walked, we track how much memory is usable
4047                  * by the kernel using kernelcore_remaining. When it is
4048                  * 0, the rest of the node is usable by ZONE_MOVABLE
4049                  */
4050                 kernelcore_remaining = kernelcore_node;
4051
4052                 /* Go through each range of PFNs within this node */
4053                 for_each_active_range_index_in_nid(i, nid) {
4054                         unsigned long start_pfn, end_pfn;
4055                         unsigned long size_pages;
4056
4057                         start_pfn = max(early_node_map[i].start_pfn,
4058                                                 zone_movable_pfn[nid]);
4059                         end_pfn = early_node_map[i].end_pfn;
4060                         if (start_pfn >= end_pfn)
4061                                 continue;
4062
4063                         /* Account for what is only usable for kernelcore */
4064                         if (start_pfn < usable_startpfn) {
4065                                 unsigned long kernel_pages;
4066                                 kernel_pages = min(end_pfn, usable_startpfn)
4067                                                                 - start_pfn;
4068
4069                                 kernelcore_remaining -= min(kernel_pages,
4070                                                         kernelcore_remaining);
4071                                 required_kernelcore -= min(kernel_pages,
4072                                                         required_kernelcore);
4073
4074                                 /* Continue if range is now fully accounted */
4075                                 if (end_pfn <= usable_startpfn) {
4076
4077                                         /*
4078                                          * Push zone_movable_pfn to the end so
4079                                          * that if we have to rebalance
4080                                          * kernelcore across nodes, we will
4081                                          * not double account here
4082                                          */
4083                                         zone_movable_pfn[nid] = end_pfn;
4084                                         continue;
4085                                 }
4086                                 start_pfn = usable_startpfn;
4087                         }
4088
4089                         /*
4090                          * The usable PFN range for ZONE_MOVABLE is from
4091                          * start_pfn->end_pfn. Calculate size_pages as the
4092                          * number of pages used as kernelcore
4093                          */
4094                         size_pages = end_pfn - start_pfn;
4095                         if (size_pages > kernelcore_remaining)
4096                                 size_pages = kernelcore_remaining;
4097                         zone_movable_pfn[nid] = start_pfn + size_pages;
4098
4099                         /*
4100                          * Some kernelcore has been met, update counts and
4101                          * break if the kernelcore for this node has been
4102                          * satisified
4103                          */
4104                         required_kernelcore -= min(required_kernelcore,
4105                                                                 size_pages);
4106                         kernelcore_remaining -= size_pages;
4107                         if (!kernelcore_remaining)
4108                                 break;
4109                 }
4110         }
4111
4112         /*
4113          * If there is still required_kernelcore, we do another pass with one
4114          * less node in the count. This will push zone_movable_pfn[nid] further
4115          * along on the nodes that still have memory until kernelcore is
4116          * satisified
4117          */
4118         usable_nodes--;
4119         if (usable_nodes && required_kernelcore > usable_nodes)
4120                 goto restart;
4121
4122         /* Align start of ZONE_MOVABLE on all nids to MAX_ORDER_NR_PAGES */
4123         for (nid = 0; nid < MAX_NUMNODES; nid++)
4124                 zone_movable_pfn[nid] =
4125                         roundup(zone_movable_pfn[nid], MAX_ORDER_NR_PAGES);
4126 }
4127
4128 /* Any regular memory on that node ? */
4129 static void check_for_regular_memory(pg_data_t *pgdat)
4130 {
4131 #ifdef CONFIG_HIGHMEM
4132         enum zone_type zone_type;
4133
4134         for (zone_type = 0; zone_type <= ZONE_NORMAL; zone_type++) {
4135                 struct zone *zone = &pgdat->node_zones[zone_type];
4136                 if (zone->present_pages)
4137                         node_set_state(zone_to_nid(zone), N_NORMAL_MEMORY);
4138         }
4139 #endif
4140 }
4141
4142 /**
4143  * free_area_init_nodes - Initialise all pg_data_t and zone data
4144  * @max_zone_pfn: an array of max PFNs for each zone
4145  *
4146  * This will call free_area_init_node() for each active node in the system.
4147  * Using the page ranges provided by add_active_range(), the size of each
4148  * zone in each node and their holes is calculated. If the maximum PFN
4149  * between two adjacent zones match, it is assumed that the zone is empty.
4150  * For example, if arch_max_dma_pfn == arch_max_dma32_pfn, it is assumed
4151  * that arch_max_dma32_pfn has no pages. It is also assumed that a zone
4152  * starts where the previous one ended. For example, ZONE_DMA32 starts
4153  * at arch_max_dma_pfn.
4154  */
4155 void __init free_area_init_nodes(unsigned long *max_zone_pfn)
4156 {
4157         unsigned long nid;
4158         int i;
4159
4160         /* Sort early_node_map as initialisation assumes it is sorted */
4161         sort_node_map();
4162
4163         /* Record where the zone boundaries are */
4164         memset(arch_zone_lowest_possible_pfn, 0,
4165                                 sizeof(arch_zone_lowest_possible_pfn));
4166         memset(arch_zone_highest_possible_pfn, 0,
4167                                 sizeof(arch_zone_highest_possible_pfn));
4168         arch_zone_lowest_possible_pfn[0] = find_min_pfn_with_active_regions();
4169         arch_zone_highest_possible_pfn[0] = max_zone_pfn[0];
4170         for (i = 1; i < MAX_NR_ZONES; i++) {
4171                 if (i == ZONE_MOVABLE)
4172                         continue;
4173                 arch_zone_lowest_possible_pfn[i] =
4174                         arch_zone_highest_possible_pfn[i-1];
4175                 arch_zone_highest_possible_pfn[i] =
4176                         max(max_zone_pfn[i], arch_zone_lowest_possible_pfn[i]);
4177         }
4178         arch_zone_lowest_possible_pfn[ZONE_MOVABLE] = 0;
4179         arch_zone_highest_possible_pfn[ZONE_MOVABLE] = 0;
4180
4181         /* Find the PFNs that ZONE_MOVABLE begins at in each node */
4182         memset(zone_movable_pfn, 0, sizeof(zone_movable_pfn));
4183         find_zone_movable_pfns_for_nodes(zone_movable_pfn);
4184
4185         /* Print out the zone ranges */
4186         printk("Zone PFN ranges:\n");
4187         for (i = 0; i < MAX_NR_ZONES; i++) {
4188                 if (i == ZONE_MOVABLE)
4189                         continue;
4190                 printk("  %-8s %0#10lx -> %0#10lx\n",
4191                                 zone_names[i],
4192                                 arch_zone_lowest_possible_pfn[i],
4193                                 arch_zone_highest_possible_pfn[i]);
4194         }
4195
4196         /* Print out the PFNs ZONE_MOVABLE begins at in each node */
4197         printk("Movable zone start PFN for each node\n");
4198         for (i = 0; i < MAX_NUMNODES; i++) {
4199                 if (zone_movable_pfn[i])
4200                         printk("  Node %d: %lu\n", i, zone_movable_pfn[i]);
4201         }
4202
4203         /* Print out the early_node_map[] */
4204         printk("early_node_map[%d] active PFN ranges\n", nr_nodemap_entries);
4205         for (i = 0; i < nr_nodemap_entries; i++)
4206                 printk("  %3d: %0#10lx -> %0#10lx\n", early_node_map[i].nid,
4207                                                 early_node_map[i].start_pfn,
4208                                                 early_node_map[i].end_pfn);
4209
4210         /* Initialise every node */
4211         mminit_verify_pageflags_layout();
4212         setup_nr_node_ids();
4213         for_each_online_node(nid) {
4214                 pg_data_t *pgdat = NODE_DATA(nid);
4215                 free_area_init_node(nid, NULL,
4216                                 find_min_pfn_for_node(nid), NULL);
4217
4218                 /* Any memory on that node */
4219                 if (pgdat->node_present_pages)
4220                         node_set_state(nid, N_HIGH_MEMORY);
4221                 check_for_regular_memory(pgdat);
4222         }
4223 }
4224
4225 static int __init cmdline_parse_core(char *p, unsigned long *core)
4226 {
4227         unsigned long long coremem;
4228         if (!p)
4229                 return -EINVAL;
4230
4231         coremem = memparse(p, &p);
4232         *core = coremem >> PAGE_SHIFT;
4233
4234         /* Paranoid check that UL is enough for the coremem value */
4235         WARN_ON((coremem >> PAGE_SHIFT) > ULONG_MAX);
4236
4237         return 0;
4238 }
4239
4240 /*
4241  * kernelcore=size sets the amount of memory for use for allocations that
4242  * cannot be reclaimed or migrated.
4243  */
4244 static int __init cmdline_parse_kernelcore(char *p)
4245 {
4246         return cmdline_parse_core(p, &required_kernelcore);
4247 }
4248
4249 /*
4250  * movablecore=size sets the amount of memory for use for allocations that
4251  * can be reclaimed or migrated.
4252  */
4253 static int __init cmdline_parse_movablecore(char *p)
4254 {
4255         return cmdline_parse_core(p, &required_movablecore);
4256 }
4257
4258 early_param("kernelcore", cmdline_parse_kernelcore);
4259 early_param("movablecore", cmdline_parse_movablecore);
4260
4261 #endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
4262
4263 /**
4264  * set_dma_reserve - set the specified number of pages reserved in the first zone
4265  * @new_dma_reserve: The number of pages to mark reserved
4266  *
4267  * The per-cpu batchsize and zone watermarks are determined by present_pages.
4268  * In the DMA zone, a significant percentage may be consumed by kernel image
4269  * and other unfreeable allocations which can skew the watermarks badly. This
4270  * function may optionally be used to account for unfreeable pages in the
4271  * first zone (e.g., ZONE_DMA). The effect will be lower watermarks and
4272  * smaller per-cpu batchsize.
4273  */
4274 void __init set_dma_reserve(unsigned long new_dma_reserve)
4275 {
4276         dma_reserve = new_dma_reserve;
4277 }
4278
4279 #ifndef CONFIG_NEED_MULTIPLE_NODES
4280 struct pglist_data __refdata contig_page_data = { .bdata = &bootmem_node_data[0] };
4281 EXPORT_SYMBOL(contig_page_data);
4282 #endif
4283
4284 void __init free_area_init(unsigned long *zones_size)
4285 {
4286         free_area_init_node(0, zones_size,
4287                         __pa(PAGE_OFFSET) >> PAGE_SHIFT, NULL);
4288 }
4289
4290 static int page_alloc_cpu_notify(struct notifier_block *self,
4291                                  unsigned long action, void *hcpu)
4292 {
4293         int cpu = (unsigned long)hcpu;
4294
4295         if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) {
4296                 drain_pages(cpu);
4297
4298                 /*
4299                  * Spill the event counters of the dead processor
4300                  * into the current processors event counters.
4301                  * This artificially elevates the count of the current
4302                  * processor.
4303                  */
4304                 vm_events_fold_cpu(cpu);
4305
4306                 /*
4307                  * Zero the differential counters of the dead processor
4308                  * so that the vm statistics are consistent.
4309                  *
4310                  * This is only okay since the processor is dead and cannot
4311                  * race with what we are doing.
4312                  */
4313                 refresh_cpu_vm_stats(cpu);
4314         }
4315         return NOTIFY_OK;
4316 }
4317
4318 void __init page_alloc_init(void)
4319 {
4320         hotcpu_notifier(page_alloc_cpu_notify, 0);
4321 }
4322
4323 /*
4324  * calculate_totalreserve_pages - called when sysctl_lower_zone_reserve_ratio
4325  *      or min_free_kbytes changes.
4326  */
4327 static void calculate_totalreserve_pages(void)
4328 {
4329         struct pglist_data *pgdat;
4330         unsigned long reserve_pages = 0;
4331         enum zone_type i, j;
4332
4333         for_each_online_pgdat(pgdat) {
4334                 for (i = 0; i < MAX_NR_ZONES; i++) {
4335                         struct zone *zone = pgdat->node_zones + i;
4336                         unsigned long max = 0;
4337
4338                         /* Find valid and maximum lowmem_reserve in the zone */
4339                         for (j = i; j < MAX_NR_ZONES; j++) {
4340                                 if (zone->lowmem_reserve[j] > max)
4341                                         max = zone->lowmem_reserve[j];
4342                         }
4343
4344                         /* we treat the high watermark as reserved pages. */
4345                         max += high_wmark_pages(zone);
4346
4347                         if (max > zone->present_pages)
4348                                 max = zone->present_pages;
4349                         reserve_pages += max;
4350                 }
4351         }
4352         totalreserve_pages = reserve_pages;
4353 }
4354
4355 /*
4356  * setup_per_zone_lowmem_reserve - called whenever
4357  *      sysctl_lower_zone_reserve_ratio changes.  Ensures that each zone
4358  *      has a correct pages reserved value, so an adequate number of
4359  *      pages are left in the zone after a successful __alloc_pages().
4360  */
4361 static void setup_per_zone_lowmem_reserve(void)
4362 {
4363         struct pglist_data *pgdat;
4364         enum zone_type j, idx;
4365
4366         for_each_online_pgdat(pgdat) {
4367                 for (j = 0; j < MAX_NR_ZONES; j++) {
4368                         struct zone *zone = pgdat->node_zones + j;
4369                         unsigned long present_pages = zone->present_pages;
4370
4371                         zone->lowmem_reserve[j] = 0;
4372
4373                         idx = j;
4374                         while (idx) {
4375                                 struct zone *lower_zone;
4376
4377                                 idx--;
4378
4379                                 if (sysctl_lowmem_reserve_ratio[idx] < 1)
4380                                         sysctl_lowmem_reserve_ratio[idx] = 1;
4381
4382                                 lower_zone = pgdat->node_zones + idx;
4383                                 lower_zone->lowmem_reserve[j] = present_pages /
4384                                         sysctl_lowmem_reserve_ratio[idx];
4385                                 present_pages += lower_zone->present_pages;
4386                         }
4387                 }
4388         }
4389
4390         /* update totalreserve_pages */
4391         calculate_totalreserve_pages();
4392 }
4393
4394 /**
4395  * setup_per_zone_pages_min - called when min_free_kbytes changes.
4396  *
4397  * Ensures that the pages_{min,low,high} values for each zone are set correctly
4398  * with respect to min_free_kbytes.
4399  */
4400 void setup_per_zone_pages_min(void)
4401 {
4402         unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
4403         unsigned long lowmem_pages = 0;
4404         struct zone *zone;
4405         unsigned long flags;
4406
4407         /* Calculate total number of !ZONE_HIGHMEM pages */
4408         for_each_zone(zone) {
4409                 if (!is_highmem(zone))
4410                         lowmem_pages += zone->present_pages;
4411         }
4412
4413         for_each_zone(zone) {
4414                 u64 tmp;
4415
4416                 spin_lock_irqsave(&zone->lock, flags);
4417                 tmp = (u64)pages_min * zone->present_pages;
4418                 do_div(tmp, lowmem_pages);
4419                 if (is_highmem(zone)) {
4420                         /*
4421                          * __GFP_HIGH and PF_MEMALLOC allocations usually don't
4422                          * need highmem pages, so cap pages_min to a small
4423                          * value here.
4424                          *
4425                          * The WMARK_HIGH-WMARK_LOW and (WMARK_LOW-WMARK_MIN)
4426                          * deltas controls asynch page reclaim, and so should
4427                          * not be capped for highmem.
4428                          */
4429                         int min_pages;
4430
4431                         min_pages = zone->present_pages / 1024;
4432                         if (min_pages < SWAP_CLUSTER_MAX)
4433                                 min_pages = SWAP_CLUSTER_MAX;
4434                         if (min_pages > 128)
4435                                 min_pages = 128;
4436                         zone->watermark[WMARK_MIN] = min_pages;
4437                 } else {
4438                         /*
4439                          * If it's a lowmem zone, reserve a number of pages
4440                          * proportionate to the zone's size.
4441                          */
4442                         zone->watermark[WMARK_MIN] = tmp;
4443                 }
4444
4445                 zone->watermark[WMARK_LOW]  = min_wmark_pages(zone) + (tmp >> 2);
4446                 zone->watermark[WMARK_HIGH] = min_wmark_pages(zone) + (tmp >> 1);
4447                 setup_zone_migrate_reserve(zone);
4448                 spin_unlock_irqrestore(&zone->lock, flags);
4449         }
4450
4451         /* update totalreserve_pages */
4452         calculate_totalreserve_pages();
4453 }
4454
4455 /**
4456  * The inactive anon list should be small enough that the VM never has to
4457  * do too much work, but large enough that each inactive page has a chance
4458  * to be referenced again before it is swapped out.
4459  *
4460  * The inactive_anon ratio is the target ratio of ACTIVE_ANON to
4461  * INACTIVE_ANON pages on this zone's LRU, maintained by the
4462  * pageout code. A zone->inactive_ratio of 3 means 3:1 or 25% of
4463  * the anonymous pages are kept on the inactive list.
4464  *
4465  * total     target    max
4466  * memory    ratio     inactive anon
4467  * -------------------------------------
4468  *   10MB       1         5MB
4469  *  100MB       1        50MB
4470  *    1GB       3       250MB
4471  *   10GB      10       0.9GB
4472  *  100GB      31         3GB
4473  *    1TB     101        10GB
4474  *   10TB     320        32GB
4475  */
4476 static void __init setup_per_zone_inactive_ratio(void)
4477 {
4478         struct zone *zone;
4479
4480         for_each_zone(zone) {
4481                 unsigned int gb, ratio;
4482
4483                 /* Zone size in gigabytes */
4484                 gb = zone->present_pages >> (30 - PAGE_SHIFT);
4485                 if (gb)
4486                         ratio = int_sqrt(10 * gb);
4487                 else
4488                         ratio = 1;
4489
4490                 zone->inactive_ratio = ratio;
4491         }
4492 }
4493
4494 /*
4495  * Initialise min_free_kbytes.
4496  *
4497  * For small machines we want it small (128k min).  For large machines
4498  * we want it large (64MB max).  But it is not linear, because network
4499  * bandwidth does not increase linearly with machine size.  We use
4500  *
4501  *      min_free_kbytes = 4 * sqrt(lowmem_kbytes), for better accuracy:
4502  *      min_free_kbytes = sqrt(lowmem_kbytes * 16)
4503  *
4504  * which yields
4505  *
4506  * 16MB:        512k
4507  * 32MB:        724k
4508  * 64MB:        1024k
4509  * 128MB:       1448k
4510  * 256MB:       2048k
4511  * 512MB:       2896k
4512  * 1024MB:      4096k
4513  * 2048MB:      5792k
4514  * 4096MB:      8192k
4515  * 8192MB:      11584k
4516  * 16384MB:     16384k
4517  */
4518 static int __init init_per_zone_pages_min(void)
4519 {
4520         unsigned long lowmem_kbytes;
4521
4522         lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10);
4523
4524         min_free_kbytes = int_sqrt(lowmem_kbytes * 16);
4525         if (min_free_kbytes < 128)
4526                 min_free_kbytes = 128;
4527         if (min_free_kbytes > 65536)
4528                 min_free_kbytes = 65536;
4529         setup_per_zone_pages_min();
4530         setup_per_zone_lowmem_reserve();
4531         setup_per_zone_inactive_ratio();
4532         return 0;
4533 }
4534 module_init(init_per_zone_pages_min)
4535
4536 /*
4537  * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so 
4538  *      that we can call two helper functions whenever min_free_kbytes
4539  *      changes.
4540  */
4541 int min_free_kbytes_sysctl_handler(ctl_table *table, int write, 
4542         struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
4543 {
4544         proc_dointvec(table, write, file, buffer, length, ppos);
4545         if (write)
4546                 setup_per_zone_pages_min();
4547         return 0;
4548 }
4549
4550 #ifdef CONFIG_NUMA
4551 int sysctl_min_unmapped_ratio_sysctl_handler(ctl_table *table, int write,
4552         struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
4553 {
4554         struct zone *zone;
4555         int rc;
4556
4557         rc = proc_dointvec_minmax(table, write, file, buffer, length, ppos);
4558         if (rc)
4559                 return rc;
4560
4561         for_each_zone(zone)
4562                 zone->min_unmapped_pages = (zone->present_pages *
4563                                 sysctl_min_unmapped_ratio) / 100;
4564         return 0;
4565 }
4566
4567 int sysctl_min_slab_ratio_sysctl_handler(ctl_table *table, int write,
4568         struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
4569 {
4570         struct zone *zone;
4571         int rc;
4572
4573         rc = proc_dointvec_minmax(table, write, file, buffer, length, ppos);
4574         if (rc)
4575                 return rc;
4576
4577         for_each_zone(zone)
4578                 zone->min_slab_pages = (zone->present_pages *
4579                                 sysctl_min_slab_ratio) / 100;
4580         return 0;
4581 }
4582 #endif
4583
4584 /*
4585  * lowmem_reserve_ratio_sysctl_handler - just a wrapper around
4586  *      proc_dointvec() so that we can call setup_per_zone_lowmem_reserve()
4587  *      whenever sysctl_lowmem_reserve_ratio changes.
4588  *
4589  * The reserve ratio obviously has absolutely no relation with the
4590  * minimum watermarks. The lowmem reserve ratio can only make sense
4591  * if in function of the boot time zone sizes.
4592  */
4593 int lowmem_reserve_ratio_sysctl_handler(ctl_table *table, int write,
4594         struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
4595 {
4596         proc_dointvec_minmax(table, write, file, buffer, length, ppos);
4597         setup_per_zone_lowmem_reserve();
4598         return 0;
4599 }
4600
4601 /*
4602  * percpu_pagelist_fraction - changes the pcp->high for each zone on each
4603  * cpu.  It is the fraction of total pages in each zone that a hot per cpu pagelist
4604  * can have before it gets flushed back to buddy allocator.
4605  */
4606
4607 int percpu_pagelist_fraction_sysctl_handler(ctl_table *table, int write,
4608         struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
4609 {
4610         struct zone *zone;
4611         unsigned int cpu;
4612         int ret;
4613
4614         ret = proc_dointvec_minmax(table, write, file, buffer, length, ppos);
4615         if (!write || (ret == -EINVAL))
4616                 return ret;
4617         for_each_zone(zone) {
4618                 for_each_online_cpu(cpu) {
4619                         unsigned long  high;
4620                         high = zone->present_pages / percpu_pagelist_fraction;
4621                         setup_pagelist_highmark(zone_pcp(zone, cpu), high);
4622                 }
4623         }
4624         return 0;
4625 }
4626
4627 int hashdist = HASHDIST_DEFAULT;
4628
4629 #ifdef CONFIG_NUMA
4630 static int __init set_hashdist(char *str)
4631 {
4632         if (!str)
4633                 return 0;
4634         hashdist = simple_strtoul(str, &str, 0);
4635         return 1;
4636 }
4637 __setup("hashdist=", set_hashdist);
4638 #endif
4639
4640 /*
4641  * allocate a large system hash table from bootmem
4642  * - it is assumed that the hash table must contain an exact power-of-2
4643  *   quantity of entries
4644  * - limit is the number of hash buckets, not the total allocation size
4645  */
4646 void *__init alloc_large_system_hash(const char *tablename,
4647                                      unsigned long bucketsize,
4648                                      unsigned long numentries,
4649                                      int scale,
4650                                      int flags,
4651                                      unsigned int *_hash_shift,
4652                                      unsigned int *_hash_mask,
4653                                      unsigned long limit)
4654 {
4655         unsigned long long max = limit;
4656         unsigned long log2qty, size;
4657         void *table = NULL;
4658
4659         /* allow the kernel cmdline to have a say */
4660         if (!numentries) {
4661                 /* round applicable memory size up to nearest megabyte */
4662                 numentries = nr_kernel_pages;
4663                 numentries += (1UL << (20 - PAGE_SHIFT)) - 1;
4664                 numentries >>= 20 - PAGE_SHIFT;
4665                 numentries <<= 20 - PAGE_SHIFT;
4666
4667                 /* limit to 1 bucket per 2^scale bytes of low memory */
4668                 if (scale > PAGE_SHIFT)
4669                         numentries >>= (scale - PAGE_SHIFT);
4670                 else
4671                         numentries <<= (PAGE_SHIFT - scale);
4672
4673                 /* Make sure we've got at least a 0-order allocation.. */
4674                 if (unlikely((numentries * bucketsize) < PAGE_SIZE))
4675                         numentries = PAGE_SIZE / bucketsize;
4676         }
4677         numentries = roundup_pow_of_two(numentries);
4678
4679         /* limit allocation size to 1/16 total memory by default */
4680         if (max == 0) {
4681                 max = ((unsigned long long)nr_all_pages << PAGE_SHIFT) >> 4;
4682                 do_div(max, bucketsize);
4683         }
4684
4685         if (numentries > max)
4686                 numentries = max;
4687
4688         log2qty = ilog2(numentries);
4689
4690         do {
4691                 size = bucketsize << log2qty;
4692                 if (flags & HASH_EARLY)
4693                         table = alloc_bootmem_nopanic(size);
4694                 else if (hashdist)
4695                         table = __vmalloc(size, GFP_ATOMIC, PAGE_KERNEL);
4696                 else {
4697                         /*
4698                          * If bucketsize is not a power-of-two, we may free
4699                          * some pages at the end of hash table which
4700                          * alloc_pages_exact() automatically does
4701                          */
4702                         if (get_order(size) < MAX_ORDER)
4703                                 table = alloc_pages_exact(size, GFP_ATOMIC);
4704                 }
4705         } while (!table && size > PAGE_SIZE && --log2qty);
4706
4707         if (!table)
4708                 panic("Failed to allocate %s hash table\n", tablename);
4709
4710         printk(KERN_INFO "%s hash table entries: %d (order: %d, %lu bytes)\n",
4711                tablename,
4712                (1U << log2qty),
4713                ilog2(size) - PAGE_SHIFT,
4714                size);
4715
4716         if (_hash_shift)
4717                 *_hash_shift = log2qty;
4718         if (_hash_mask)
4719                 *_hash_mask = (1 << log2qty) - 1;
4720
4721         /*
4722          * If hashdist is set, the table allocation is done with __vmalloc()
4723          * which invokes the kmemleak_alloc() callback. This function may also
4724          * be called before the slab and kmemleak are initialised when
4725          * kmemleak simply buffers the request to be executed later
4726          * (GFP_ATOMIC flag ignored in this case).
4727          */
4728         if (!hashdist)
4729                 kmemleak_alloc(table, size, 1, GFP_ATOMIC);
4730
4731         return table;
4732 }
4733
4734 /* Return a pointer to the bitmap storing bits affecting a block of pages */
4735 static inline unsigned long *get_pageblock_bitmap(struct zone *zone,
4736                                                         unsigned long pfn)
4737 {
4738 #ifdef CONFIG_SPARSEMEM
4739         return __pfn_to_section(pfn)->pageblock_flags;
4740 #else
4741         return zone->pageblock_flags;
4742 #endif /* CONFIG_SPARSEMEM */
4743 }
4744
4745 static inline int pfn_to_bitidx(struct zone *zone, unsigned long pfn)
4746 {
4747 #ifdef CONFIG_SPARSEMEM
4748         pfn &= (PAGES_PER_SECTION-1);
4749         return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
4750 #else
4751         pfn = pfn - zone->zone_start_pfn;
4752         return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
4753 #endif /* CONFIG_SPARSEMEM */
4754 }
4755
4756 /**
4757  * get_pageblock_flags_group - Return the requested group of flags for the pageblock_nr_pages block of pages
4758  * @page: The page within the block of interest
4759  * @start_bitidx: The first bit of interest to retrieve
4760  * @end_bitidx: The last bit of interest
4761  * returns pageblock_bits flags
4762  */
4763 unsigned long get_pageblock_flags_group(struct page *page,
4764                                         int start_bitidx, int end_bitidx)
4765 {
4766         struct zone *zone;
4767         unsigned long *bitmap;
4768         unsigned long pfn, bitidx;
4769         unsigned long flags = 0;
4770         unsigned long value = 1;
4771
4772         zone = page_zone(page);
4773         pfn = page_to_pfn(page);
4774         bitmap = get_pageblock_bitmap(zone, pfn);
4775         bitidx = pfn_to_bitidx(zone, pfn);
4776
4777         for (; start_bitidx <= end_bitidx; start_bitidx++, value <<= 1)
4778                 if (test_bit(bitidx + start_bitidx, bitmap))
4779                         flags |= value;
4780
4781         return flags;
4782 }
4783
4784 /**
4785  * set_pageblock_flags_group - Set the requested group of flags for a pageblock_nr_pages block of pages
4786  * @page: The page within the block of interest
4787  * @start_bitidx: The first bit of interest
4788  * @end_bitidx: The last bit of interest
4789  * @flags: The flags to set
4790  */
4791 void set_pageblock_flags_group(struct page *page, unsigned long flags,
4792                                         int start_bitidx, int end_bitidx)
4793 {
4794         struct zone *zone;
4795         unsigned long *bitmap;
4796         unsigned long pfn, bitidx;
4797         unsigned long value = 1;
4798
4799         zone = page_zone(page);
4800         pfn = page_to_pfn(page);
4801         bitmap = get_pageblock_bitmap(zone, pfn);
4802         bitidx = pfn_to_bitidx(zone, pfn);
4803         VM_BUG_ON(pfn < zone->zone_start_pfn);
4804         VM_BUG_ON(pfn >= zone->zone_start_pfn + zone->spanned_pages);
4805
4806         for (; start_bitidx <= end_bitidx; start_bitidx++, value <<= 1)
4807                 if (flags & value)
4808                         __set_bit(bitidx + start_bitidx, bitmap);
4809                 else
4810                         __clear_bit(bitidx + start_bitidx, bitmap);
4811 }
4812
4813 /*
4814  * This is designed as sub function...plz see page_isolation.c also.
4815  * set/clear page block's type to be ISOLATE.
4816  * page allocater never alloc memory from ISOLATE block.
4817  */
4818
4819 int set_migratetype_isolate(struct page *page)
4820 {
4821         struct zone *zone;
4822         unsigned long flags;
4823         int ret = -EBUSY;
4824
4825         zone = page_zone(page);
4826         spin_lock_irqsave(&zone->lock, flags);
4827         /*
4828          * In future, more migrate types will be able to be isolation target.
4829          */
4830         if (get_pageblock_migratetype(page) != MIGRATE_MOVABLE)
4831                 goto out;
4832         set_pageblock_migratetype(page, MIGRATE_ISOLATE);
4833         move_freepages_block(zone, page, MIGRATE_ISOLATE);
4834         ret = 0;
4835 out:
4836         spin_unlock_irqrestore(&zone->lock, flags);
4837         if (!ret)
4838                 drain_all_pages();
4839         return ret;
4840 }
4841
4842 void unset_migratetype_isolate(struct page *page)
4843 {
4844         struct zone *zone;
4845         unsigned long flags;
4846         zone = page_zone(page);
4847         spin_lock_irqsave(&zone->lock, flags);
4848         if (get_pageblock_migratetype(page) != MIGRATE_ISOLATE)
4849                 goto out;
4850         set_pageblock_migratetype(page, MIGRATE_MOVABLE);
4851         move_freepages_block(zone, page, MIGRATE_MOVABLE);
4852 out:
4853         spin_unlock_irqrestore(&zone->lock, flags);
4854 }
4855
4856 #ifdef CONFIG_MEMORY_HOTREMOVE
4857 /*
4858  * All pages in the range must be isolated before calling this.
4859  */
4860 void
4861 __offline_isolated_pages(unsigned long start_pfn, unsigned long end_pfn)
4862 {
4863         struct page *page;
4864         struct zone *zone;
4865         int order, i;
4866         unsigned long pfn;
4867         unsigned long flags;
4868         /* find the first valid pfn */
4869         for (pfn = start_pfn; pfn < end_pfn; pfn++)
4870                 if (pfn_valid(pfn))
4871                         break;
4872         if (pfn == end_pfn)
4873                 return;
4874         zone = page_zone(pfn_to_page(pfn));
4875         spin_lock_irqsave(&zone->lock, flags);
4876         pfn = start_pfn;
4877         while (pfn < end_pfn) {
4878                 if (!pfn_valid(pfn)) {
4879                         pfn++;
4880                         continue;
4881                 }
4882                 page = pfn_to_page(pfn);
4883                 BUG_ON(page_count(page));
4884                 BUG_ON(!PageBuddy(page));
4885                 order = page_order(page);
4886 #ifdef CONFIG_DEBUG_VM
4887                 printk(KERN_INFO "remove from free list %lx %d %lx\n",
4888                        pfn, 1 << order, end_pfn);
4889 #endif
4890                 list_del(&page->lru);
4891                 rmv_page_order(page);
4892                 zone->free_area[order].nr_free--;
4893                 __mod_zone_page_state(zone, NR_FREE_PAGES,
4894                                       - (1UL << order));
4895                 for (i = 0; i < (1 << order); i++)
4896                         SetPageReserved((page+i));
4897                 pfn += (1 << order);
4898         }
4899         spin_unlock_irqrestore(&zone->lock, flags);
4900 }
4901 #endif