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