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