/*
   *  linux/mm/page_alloc.c
   *
   *  Manages the free list, the system allocates free pages here.
   *  Note that kmalloc() lives in slab.c
   *
   *  Copyright (C) 1991, 1992, 1993, 1994  Linus Torvalds
   *  Swap reorganised 29.12.95, Stephen Tweedie
   *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
   *  Reshaped it to be a zoned allocator, Ingo Molnar, Red Hat, 1999
   *  Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999
   *  Zone balancing, Kanoj Sarcar, SGI, Jan 2000
   *  Per cpu hot/cold page lists, bulk allocation, Martin J. Bligh, Sept 2002
   *          (lots of bits borrowed from Ingo Molnar & Andrew Morton)
   */

  #include <linux/stddef.h>
  #include <linux/mm.h>
  #include <linux/swap.h>
  #include <linux/interrupt.h>
  #include <linux/pagemap.h>

  #include <linux/jiffies.h>

  #include <linux/bootmem.h>
  #include <linux/compiler.h>

  #include <linux/kernel.h>

  #include <linux/kmemcheck.h>

  #include <linux/module.h>
  #include <linux/suspend.h>
  #include <linux/pagevec.h>
  #include <linux/blkdev.h>
  #include <linux/slab.h>

  #include <linux/oom.h>

  #include <linux/notifier.h>
  #include <linux/topology.h>
  #include <linux/sysctl.h>
  #include <linux/cpu.h>
  #include <linux/cpuset.h>

  #include <linux/memory_hotplug.h>

  #include <linux/nodemask.h>
  #include <linux/vmalloc.h>

  #include <linux/mempolicy.h>

  #include <linux/stop_machine.h>

  #include <linux/sort.h>
  #include <linux/pfn.h>

  #include <linux/backing-dev.h>

  #include <linux/fault-inject.h>

  #include <linux/page-isolation.h>

  #include <linux/page_cgroup.h>

  #include <linux/debugobjects.h>

  #include <linux/kmemleak.h>

  #include <linux/memory.h>

  #include <linux/compaction.h>

  #include <trace/events/kmem.h>

  #include <linux/ftrace_event.h>

  
  #include <asm/tlbflush.h>

  #include <asm/div64.h>

  #include "internal.h"

  #ifdef CONFIG_USE_PERCPU_NUMA_NODE_ID
  DEFINE_PER_CPU(int, numa_node);
  EXPORT_PER_CPU_SYMBOL(numa_node);
  #endif

  #ifdef CONFIG_HAVE_MEMORYLESS_NODES
  /*
   * N.B., Do NOT reference the '_numa_mem_' per cpu variable directly.
   * It will not be defined when CONFIG_HAVE_MEMORYLESS_NODES is not defined.
   * Use the accessor functions set_numa_mem(), numa_mem_id() and cpu_to_mem()
   * defined in <linux/topology.h>.
   */
  DEFINE_PER_CPU(int, _numa_mem_);		/* Kernel "local memory" node */
  EXPORT_PER_CPU_SYMBOL(_numa_mem_);
  #endif

  /*

   * Array of node states.

   */

  nodemask_t node_states[NR_NODE_STATES] __read_mostly = {
  	[N_POSSIBLE] = NODE_MASK_ALL,
  	[N_ONLINE] = { { [0] = 1UL } },
  #ifndef CONFIG_NUMA
  	[N_NORMAL_MEMORY] = { { [0] = 1UL } },
  #ifdef CONFIG_HIGHMEM
  	[N_HIGH_MEMORY] = { { [0] = 1UL } },
  #endif
  	[N_CPU] = { { [0] = 1UL } },
  #endif	/* NUMA */
  };
  EXPORT_SYMBOL(node_states);

  unsigned long totalram_pages __read_mostly;

  unsigned long totalreserve_pages __read_mostly;

  int percpu_pagelist_fraction;

  gfp_t gfp_allowed_mask __read_mostly = GFP_BOOT_MASK;

  #ifdef CONFIG_PM_SLEEP
  /*
   * The following functions are used by the suspend/hibernate code to temporarily
   * change gfp_allowed_mask in order to avoid using I/O during memory allocations
   * while devices are suspended.  To avoid races with the suspend/hibernate code,
   * they should always be called with pm_mutex held (gfp_allowed_mask also should
   * only be modified with pm_mutex held, unless the suspend/hibernate code is
   * guaranteed not to run in parallel with that modification).
   */
  void set_gfp_allowed_mask(gfp_t mask)
  {
  	WARN_ON(!mutex_is_locked(&pm_mutex));
  	gfp_allowed_mask = mask;
  }
  
  gfp_t clear_gfp_allowed_mask(gfp_t mask)
  {
  	gfp_t ret = gfp_allowed_mask;
  
  	WARN_ON(!mutex_is_locked(&pm_mutex));
  	gfp_allowed_mask &= ~mask;
  	return ret;
  }
  #endif /* CONFIG_PM_SLEEP */

  #ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
  int pageblock_order __read_mostly;
  #endif

  static void __free_pages_ok(struct page *page, unsigned int order);

  /*
   * results with 256, 32 in the lowmem_reserve sysctl:
   *	1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
   *	1G machine -> (16M dma, 784M normal, 224M high)
   *	NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
   *	HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
   *	HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA

   *
   * TBD: should special case ZONE_DMA32 machines here - in those we normally
   * don't need any ZONE_NORMAL reservation

   */

  int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = {

  #ifdef CONFIG_ZONE_DMA

  	 256,

  #endif

  #ifdef CONFIG_ZONE_DMA32

  	 256,

  #endif

  #ifdef CONFIG_HIGHMEM

  	 32,

  #endif

  	 32,

  };

  
  EXPORT_SYMBOL(totalram_pages);

  static char * const zone_names[MAX_NR_ZONES] = {

  #ifdef CONFIG_ZONE_DMA

  	 "DMA",

  #endif

  #ifdef CONFIG_ZONE_DMA32

  	 "DMA32",

  #endif

  	 "Normal",

  #ifdef CONFIG_HIGHMEM

  	 "HighMem",

  #endif

  	 "Movable",

  };

  int min_free_kbytes = 1024;

  static unsigned long __meminitdata nr_kernel_pages;
  static unsigned long __meminitdata nr_all_pages;

  static unsigned long __meminitdata dma_reserve;

  #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
    /*

     * MAX_ACTIVE_REGIONS determines the maximum number of distinct

     * ranges of memory (RAM) that may be registered with add_active_range().
     * Ranges passed to add_active_range() will be merged if possible
     * so the number of times add_active_range() can be called is
     * related to the number of nodes and the number of holes
     */
    #ifdef CONFIG_MAX_ACTIVE_REGIONS
      /* Allow an architecture to set MAX_ACTIVE_REGIONS to save memory */
      #define MAX_ACTIVE_REGIONS CONFIG_MAX_ACTIVE_REGIONS
    #else
      #if MAX_NUMNODES >= 32
        /* If there can be many nodes, allow up to 50 holes per node */
        #define MAX_ACTIVE_REGIONS (MAX_NUMNODES*50)
      #else
        /* By default, allow up to 256 distinct regions */
        #define MAX_ACTIVE_REGIONS 256
      #endif
    #endif

    static struct node_active_region __meminitdata early_node_map[MAX_ACTIVE_REGIONS];
    static int __meminitdata nr_nodemap_entries;
    static unsigned long __meminitdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES];
    static unsigned long __meminitdata arch_zone_highest_possible_pfn[MAX_NR_ZONES];

    static unsigned long __initdata required_kernelcore;

    static unsigned long __initdata required_movablecore;

    static unsigned long __meminitdata zone_movable_pfn[MAX_NUMNODES];

  
    /* movable_zone is the "real" zone pages in ZONE_MOVABLE are taken from */
    int movable_zone;
    EXPORT_SYMBOL(movable_zone);

  #endif /* CONFIG_ARCH_POPULATES_NODE_MAP */

  #if MAX_NUMNODES > 1
  int nr_node_ids __read_mostly = MAX_NUMNODES;

  int nr_online_nodes __read_mostly = 1;

  EXPORT_SYMBOL(nr_node_ids);

  EXPORT_SYMBOL(nr_online_nodes);

  #endif

  int page_group_by_mobility_disabled __read_mostly;

  static void set_pageblock_migratetype(struct page *page, int migratetype)
  {

  
  	if (unlikely(page_group_by_mobility_disabled))
  		migratetype = MIGRATE_UNMOVABLE;

  	set_pageblock_flags_group(page, (unsigned long)migratetype,
  					PB_migrate, PB_migrate_end);
  }

  bool oom_killer_disabled __read_mostly;

  #ifdef CONFIG_DEBUG_VM

  static int page_outside_zone_boundaries(struct zone *zone, struct page *page)

  {

  	int ret = 0;
  	unsigned seq;
  	unsigned long pfn = page_to_pfn(page);

  	do {
  		seq = zone_span_seqbegin(zone);
  		if (pfn >= zone->zone_start_pfn + zone->spanned_pages)
  			ret = 1;
  		else if (pfn < zone->zone_start_pfn)
  			ret = 1;
  	} while (zone_span_seqretry(zone, seq));
  
  	return ret;

  }
  
  static int page_is_consistent(struct zone *zone, struct page *page)
  {

  	if (!pfn_valid_within(page_to_pfn(page)))

  		return 0;

  	if (zone != page_zone(page))

  		return 0;
  
  	return 1;
  }
  /*
   * Temporary debugging check for pages not lying within a given zone.
   */
  static int bad_range(struct zone *zone, struct page *page)
  {
  	if (page_outside_zone_boundaries(zone, page))

  		return 1;

  	if (!page_is_consistent(zone, page))
  		return 1;

  	return 0;
  }

  #else
  static inline int bad_range(struct zone *zone, struct page *page)
  {
  	return 0;
  }
  #endif

  static void bad_page(struct page *page)

  {

  	static unsigned long resume;
  	static unsigned long nr_shown;
  	static unsigned long nr_unshown;

  	/* Don't complain about poisoned pages */
  	if (PageHWPoison(page)) {
  		__ClearPageBuddy(page);
  		return;
  	}

  	/*
  	 * Allow a burst of 60 reports, then keep quiet for that minute;
  	 * or allow a steady drip of one report per second.
  	 */
  	if (nr_shown == 60) {
  		if (time_before(jiffies, resume)) {
  			nr_unshown++;
  			goto out;
  		}
  		if (nr_unshown) {

  			printk(KERN_ALERT
  			      "BUG: Bad page state: %lu messages suppressed
  ",

  				nr_unshown);
  			nr_unshown = 0;
  		}
  		nr_shown = 0;
  	}
  	if (nr_shown++ == 0)
  		resume = jiffies + 60 * HZ;

  	printk(KERN_ALERT "BUG: Bad page state in process %s  pfn:%05lx
  ",

  		current->comm, page_to_pfn(page));

  	dump_page(page);

  	dump_stack();

  out:

  	/* Leave bad fields for debug, except PageBuddy could make trouble */
  	__ClearPageBuddy(page);

  	add_taint(TAINT_BAD_PAGE);

  }

  /*
   * Higher-order pages are called "compound pages".  They are structured thusly:
   *
   * The first PAGE_SIZE page is called the "head page".
   *
   * The remaining PAGE_SIZE pages are called "tail pages".
   *
   * All pages have PG_compound set.  All pages have their ->private pointing at
   * the head page (even the head page has this).
   *

   * The first tail page's ->lru.next holds the address of the compound page's
   * put_page() function.  Its ->lru.prev holds the order of allocation.
   * This usage means that zero-order pages may not be compound.

   */

  
  static void free_compound_page(struct page *page)
  {

  	__free_pages_ok(page, compound_order(page));

  }

  void prep_compound_page(struct page *page, unsigned long order)

  {
  	int i;
  	int nr_pages = 1 << order;

  
  	set_compound_page_dtor(page, free_compound_page);
  	set_compound_order(page, order);
  	__SetPageHead(page);
  	for (i = 1; i < nr_pages; i++) {
  		struct page *p = page + i;
  
  		__SetPageTail(p);
  		p->first_page = page;
  	}
  }

  static int destroy_compound_page(struct page *page, unsigned long order)

  {
  	int i;
  	int nr_pages = 1 << order;

  	int bad = 0;

  	if (unlikely(compound_order(page) != order) ||
  	    unlikely(!PageHead(page))) {

  		bad_page(page);

  		bad++;
  	}

  	__ClearPageHead(page);

  	for (i = 1; i < nr_pages; i++) {
  		struct page *p = page + i;

  		if (unlikely(!PageTail(p) || (p->first_page != page))) {

  			bad_page(page);

  			bad++;
  		}

  		__ClearPageTail(p);

  	}

  
  	return bad;

  }

  static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags)
  {
  	int i;

  	/*
  	 * clear_highpage() will use KM_USER0, so it's a bug to use __GFP_ZERO
  	 * and __GFP_HIGHMEM from hard or soft interrupt context.
  	 */

  	VM_BUG_ON((gfp_flags & __GFP_HIGHMEM) && in_interrupt());

  	for (i = 0; i < (1 << order); i++)
  		clear_highpage(page + i);
  }

  static inline void set_page_order(struct page *page, int order)
  {

  	set_page_private(page, order);

  	__SetPageBuddy(page);

  }
  
  static inline void rmv_page_order(struct page *page)
  {

  	__ClearPageBuddy(page);

  	set_page_private(page, 0);

  }
  
  /*
   * Locate the struct page for both the matching buddy in our
   * pair (buddy1) and the combined O(n+1) page they form (page).
   *
   * 1) Any buddy B1 will have an order O twin B2 which satisfies
   * the following equation:
   *     B2 = B1 ^ (1 << O)
   * For example, if the starting buddy (buddy2) is #8 its order
   * 1 buddy is #10:
   *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
   *
   * 2) Any buddy B will have an order O+1 parent P which
   * satisfies the following equation:
   *     P = B & ~(1 << O)
   *

   * Assumption: *_mem_map is contiguous at least up to MAX_ORDER

   */
  static inline struct page *
  __page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
  {
  	unsigned long buddy_idx = page_idx ^ (1 << order);
  
  	return page + (buddy_idx - page_idx);
  }
  
  static inline unsigned long
  __find_combined_index(unsigned long page_idx, unsigned int order)
  {
  	return (page_idx & ~(1 << order));
  }
  
  /*
   * This function checks whether a page is free && is the buddy
   * we can do coalesce a page and its buddy if

   * (a) the buddy is not in a hole &&

   * (b) the buddy is in the buddy system &&

   * (c) a page and its buddy have the same order &&
   * (d) a page and its buddy are in the same zone.

   *
   * For recording whether a page is in the buddy system, we use PG_buddy.
   * Setting, clearing, and testing PG_buddy is serialized by zone->lock.

   *

   * For recording page's order, we use page_private(page).

   */

  static inline int page_is_buddy(struct page *page, struct page *buddy,
  								int order)

  {

  	if (!pfn_valid_within(page_to_pfn(buddy)))

  		return 0;

  	if (page_zone_id(page) != page_zone_id(buddy))
  		return 0;
  
  	if (PageBuddy(buddy) && page_order(buddy) == order) {

  		VM_BUG_ON(page_count(buddy) != 0);

  		return 1;

  	}

  	return 0;

  }
  
  /*
   * Freeing function for a buddy system allocator.
   *
   * The concept of a buddy system is to maintain direct-mapped table
   * (containing bit values) for memory blocks of various "orders".
   * The bottom level table contains the map for the smallest allocatable
   * units of memory (here, pages), and each level above it describes
   * pairs of units from the levels below, hence, "buddies".
   * At a high level, all that happens here is marking the table entry
   * at the bottom level available, and propagating the changes upward
   * as necessary, plus some accounting needed to play nicely with other
   * parts of the VM system.
   * At each level, we keep a list of pages, which are heads of continuous

   * free pages of length of (1 << order) and marked with PG_buddy. Page's

   * order is recorded in page_private(page) field.

   * So when we are allocating or freeing one, we can derive the state of the
   * other.  That is, if we allocate a small block, and both were   
   * free, the remainder of the region must be split into blocks.   
   * If a block is freed, and its buddy is also free, then this
   * triggers coalescing into a block of larger size.            
   *
   * -- wli
   */

  static inline void __free_one_page(struct page *page,

  		struct zone *zone, unsigned int order,
  		int migratetype)

  {
  	unsigned long page_idx;

  	unsigned long combined_idx;
  	struct page *buddy;

  	if (unlikely(PageCompound(page)))

  		if (unlikely(destroy_compound_page(page, order)))
  			return;

  	VM_BUG_ON(migratetype == -1);

  	page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);

  	VM_BUG_ON(page_idx & ((1 << order) - 1));

  	VM_BUG_ON(bad_range(zone, page));

  	while (order < MAX_ORDER-1) {

  		buddy = __page_find_buddy(page, page_idx, order);

  		if (!page_is_buddy(page, buddy, order))

  			break;

  		/* Our buddy is free, merge with it and move up one order. */

  		list_del(&buddy->lru);

  		zone->free_area[order].nr_free--;

  		rmv_page_order(buddy);

  		combined_idx = __find_combined_index(page_idx, order);

  		page = page + (combined_idx - page_idx);
  		page_idx = combined_idx;
  		order++;
  	}
  	set_page_order(page, order);

  
  	/*
  	 * If this is not the largest possible page, check if the buddy
  	 * of the next-highest order is free. If it is, it's possible
  	 * that pages are being freed that will coalesce soon. In case,
  	 * that is happening, add the free page to the tail of the list
  	 * so it's less likely to be used soon and more likely to be merged
  	 * as a higher order page
  	 */
  	if ((order < MAX_ORDER-1) && pfn_valid_within(page_to_pfn(buddy))) {
  		struct page *higher_page, *higher_buddy;
  		combined_idx = __find_combined_index(page_idx, order);
  		higher_page = page + combined_idx - page_idx;
  		higher_buddy = __page_find_buddy(higher_page, combined_idx, order + 1);
  		if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
  			list_add_tail(&page->lru,
  				&zone->free_area[order].free_list[migratetype]);
  			goto out;
  		}
  	}
  
  	list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
  out:

  	zone->free_area[order].nr_free++;
  }

  /*
   * free_page_mlock() -- clean up attempts to free and mlocked() page.
   * Page should not be on lru, so no need to fix that up.
   * free_pages_check() will verify...
   */
  static inline void free_page_mlock(struct page *page)
  {

  	__dec_zone_page_state(page, NR_MLOCK);
  	__count_vm_event(UNEVICTABLE_MLOCKFREED);
  }

  static inline int free_pages_check(struct page *page)

  {

  	if (unlikely(page_mapcount(page) |
  		(page->mapping != NULL)  |

  		(atomic_read(&page->_count) != 0) |

  		(page->flags & PAGE_FLAGS_CHECK_AT_FREE))) {

  		bad_page(page);

  		return 1;

  	}

  	if (page->flags & PAGE_FLAGS_CHECK_AT_PREP)
  		page->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
  	return 0;

  }
  
  /*

   * Frees a number of pages from the PCP lists

   * Assumes all pages on list are in same zone, and of same order.

   * count is the number of pages to free.

   *
   * If the zone was previously in an "all pages pinned" state then look to
   * see if this freeing clears that state.
   *
   * And clear the zone's pages_scanned counter, to hold off the "all pages are
   * pinned" detection logic.
   */

  static void free_pcppages_bulk(struct zone *zone, int count,
  					struct per_cpu_pages *pcp)

  {

  	int migratetype = 0;

  	int batch_free = 0;

  	spin_lock(&zone->lock);

  	zone->all_unreclaimable = 0;

  	zone->pages_scanned = 0;

  	__mod_zone_page_state(zone, NR_FREE_PAGES, count);

  	while (count) {

  		struct page *page;

  		struct list_head *list;
  
  		/*

  		 * Remove pages from lists in a round-robin fashion. A
  		 * batch_free count is maintained that is incremented when an
  		 * empty list is encountered.  This is so more pages are freed
  		 * off fuller lists instead of spinning excessively around empty
  		 * lists

  		 */
  		do {

  			batch_free++;

  			if (++migratetype == MIGRATE_PCPTYPES)
  				migratetype = 0;
  			list = &pcp->lists[migratetype];
  		} while (list_empty(list));

  		do {
  			page = list_entry(list->prev, struct page, lru);
  			/* must delete as __free_one_page list manipulates */
  			list_del(&page->lru);

  			/* MIGRATE_MOVABLE list may include MIGRATE_RESERVEs */
  			__free_one_page(page, zone, 0, page_private(page));
  			trace_mm_page_pcpu_drain(page, 0, page_private(page));

  		} while (--count && --batch_free && !list_empty(list));

  	}

  	spin_unlock(&zone->lock);

  }

  static void free_one_page(struct zone *zone, struct page *page, int order,
  				int migratetype)

  {

  	spin_lock(&zone->lock);

  	zone->all_unreclaimable = 0;

  	zone->pages_scanned = 0;

  
  	__mod_zone_page_state(zone, NR_FREE_PAGES, 1 << order);

  	__free_one_page(page, zone, order, migratetype);

  	spin_unlock(&zone->lock);

  }

  static bool free_pages_prepare(struct page *page, unsigned int order)

  {

  	int i;

  	int bad = 0;

  	trace_mm_page_free_direct(page, order);

  	kmemcheck_free_shadow(page, order);

  	for (i = 0; i < (1 << order); i++) {
  		struct page *pg = page + i;
  
  		if (PageAnon(pg))
  			pg->mapping = NULL;
  		bad += free_pages_check(pg);
  	}

  	if (bad)

  		return false;

  	if (!PageHighMem(page)) {

  		debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);

  		debug_check_no_obj_freed(page_address(page),
  					   PAGE_SIZE << order);
  	}

  	arch_free_page(page, order);

  	kernel_map_pages(page, 1 << order, 0);

  	return true;
  }
  
  static void __free_pages_ok(struct page *page, unsigned int order)
  {
  	unsigned long flags;
  	int wasMlocked = __TestClearPageMlocked(page);
  
  	if (!free_pages_prepare(page, order))
  		return;

  	local_irq_save(flags);

  	if (unlikely(wasMlocked))

  		free_page_mlock(page);

  	__count_vm_events(PGFREE, 1 << order);

  	free_one_page(page_zone(page), page, order,
  					get_pageblock_migratetype(page));

  	local_irq_restore(flags);

  }

  /*
   * permit the bootmem allocator to evade page validation on high-order frees
   */

  void __meminit __free_pages_bootmem(struct page *page, unsigned int order)

  {
  	if (order == 0) {
  		__ClearPageReserved(page);
  		set_page_count(page, 0);

  		set_page_refcounted(page);

  		__free_page(page);

  	} else {

  		int loop;

  		prefetchw(page);

  		for (loop = 0; loop < BITS_PER_LONG; loop++) {
  			struct page *p = &page[loop];

  			if (loop + 1 < BITS_PER_LONG)
  				prefetchw(p + 1);

  			__ClearPageReserved(p);
  			set_page_count(p, 0);
  		}

  		set_page_refcounted(page);

  		__free_pages(page, order);

  	}
  }

  
  /*
   * The order of subdivision here is critical for the IO subsystem.
   * Please do not alter this order without good reasons and regression
   * testing. Specifically, as large blocks of memory are subdivided,
   * the order in which smaller blocks are delivered depends on the order
   * they're subdivided in this function. This is the primary factor
   * influencing the order in which pages are delivered to the IO
   * subsystem according to empirical testing, and this is also justified
   * by considering the behavior of a buddy system containing a single
   * large block of memory acted on by a series of small allocations.
   * This behavior is a critical factor in sglist merging's success.
   *
   * -- wli
   */

  static inline void expand(struct zone *zone, struct page *page,

  	int low, int high, struct free_area *area,
  	int migratetype)

  {
  	unsigned long size = 1 << high;
  
  	while (high > low) {
  		area--;
  		high--;
  		size >>= 1;

  		VM_BUG_ON(bad_range(zone, &page[size]));

  		list_add(&page[size].lru, &area->free_list[migratetype]);

  		area->nr_free++;
  		set_page_order(&page[size], high);
  	}

  }

  /*
   * This page is about to be returned from the page allocator
   */

  static inline int check_new_page(struct page *page)

  {

  	if (unlikely(page_mapcount(page) |
  		(page->mapping != NULL)  |

  		(atomic_read(&page->_count) != 0)  |

  		(page->flags & PAGE_FLAGS_CHECK_AT_PREP))) {

  		bad_page(page);

  		return 1;

  	}

  	return 0;
  }
  
  static int prep_new_page(struct page *page, int order, gfp_t gfp_flags)
  {
  	int i;
  
  	for (i = 0; i < (1 << order); i++) {
  		struct page *p = page + i;
  		if (unlikely(check_new_page(p)))
  			return 1;
  	}

  	set_page_private(page, 0);

  	set_page_refcounted(page);

  
  	arch_alloc_page(page, order);

  	kernel_map_pages(page, 1 << order, 1);

  
  	if (gfp_flags & __GFP_ZERO)
  		prep_zero_page(page, order, gfp_flags);
  
  	if (order && (gfp_flags & __GFP_COMP))
  		prep_compound_page(page, order);

  	return 0;

  }

  /*
   * Go through the free lists for the given migratetype and remove
   * the smallest available page from the freelists
   */

  static inline
  struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,

  						int migratetype)
  {
  	unsigned int current_order;
  	struct free_area * area;
  	struct page *page;
  
  	/* Find a page of the appropriate size in the preferred list */
  	for (current_order = order; current_order < MAX_ORDER; ++current_order) {
  		area = &(zone->free_area[current_order]);
  		if (list_empty(&area->free_list[migratetype]))
  			continue;
  
  		page = list_entry(area->free_list[migratetype].next,
  							struct page, lru);
  		list_del(&page->lru);
  		rmv_page_order(page);
  		area->nr_free--;

  		expand(zone, page, order, current_order, area, migratetype);
  		return page;
  	}
  
  	return NULL;
  }

  /*
   * This array describes the order lists are fallen back to when
   * the free lists for the desirable migrate type are depleted
   */
  static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {

  	[MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },
  	[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },
  	[MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
  	[MIGRATE_RESERVE]     = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, /* Never used */

  };

  /*
   * Move the free pages in a range to the free lists of the requested type.

   * Note that start_page and end_pages are not aligned on a pageblock

   * boundary. If alignment is required, use move_freepages_block()
   */

  static int move_freepages(struct zone *zone,
  			  struct page *start_page, struct page *end_page,
  			  int migratetype)

  {
  	struct page *page;
  	unsigned long order;

  	int pages_moved = 0;

  
  #ifndef CONFIG_HOLES_IN_ZONE
  	/*
  	 * page_zone is not safe to call in this context when
  	 * CONFIG_HOLES_IN_ZONE is set. This bug check is probably redundant
  	 * anyway as we check zone boundaries in move_freepages_block().
  	 * Remove at a later date when no bug reports exist related to

  	 * grouping pages by mobility

  	 */
  	BUG_ON(page_zone(start_page) != page_zone(end_page));
  #endif
  
  	for (page = start_page; page <= end_page;) {

  		/* Make sure we are not inadvertently changing nodes */
  		VM_BUG_ON(page_to_nid(page) != zone_to_nid(zone));

  		if (!pfn_valid_within(page_to_pfn(page))) {
  			page++;
  			continue;
  		}
  
  		if (!PageBuddy(page)) {
  			page++;
  			continue;
  		}
  
  		order = page_order(page);
  		list_del(&page->lru);
  		list_add(&page->lru,
  			&zone->free_area[order].free_list[migratetype]);
  		page += 1 << order;

  		pages_moved += 1 << order;

  	}

  	return pages_moved;

  }

  static int move_freepages_block(struct zone *zone, struct page *page,
  				int migratetype)

  {
  	unsigned long start_pfn, end_pfn;
  	struct page *start_page, *end_page;
  
  	start_pfn = page_to_pfn(page);

  	start_pfn = start_pfn & ~(pageblock_nr_pages-1);

  	start_page = pfn_to_page(start_pfn);

  	end_page = start_page + pageblock_nr_pages - 1;
  	end_pfn = start_pfn + pageblock_nr_pages - 1;

  
  	/* Do not cross zone boundaries */
  	if (start_pfn < zone->zone_start_pfn)
  		start_page = page;
  	if (end_pfn >= zone->zone_start_pfn + zone->spanned_pages)
  		return 0;
  
  	return move_freepages(zone, start_page, end_page, migratetype);
  }

  static void change_pageblock_range(struct page *pageblock_page,
  					int start_order, int migratetype)
  {
  	int nr_pageblocks = 1 << (start_order - pageblock_order);
  
  	while (nr_pageblocks--) {
  		set_pageblock_migratetype(pageblock_page, migratetype);
  		pageblock_page += pageblock_nr_pages;
  	}
  }

  /* Remove an element from the buddy allocator from the fallback list */

  static inline struct page *
  __rmqueue_fallback(struct zone *zone, int order, int start_migratetype)

  {
  	struct free_area * area;
  	int current_order;
  	struct page *page;
  	int migratetype, i;
  
  	/* Find the largest possible block of pages in the other list */
  	for (current_order = MAX_ORDER-1; current_order >= order;
  						--current_order) {
  		for (i = 0; i < MIGRATE_TYPES - 1; i++) {
  			migratetype = fallbacks[start_migratetype][i];

  			/* MIGRATE_RESERVE handled later if necessary */
  			if (migratetype == MIGRATE_RESERVE)
  				continue;

  			area = &(zone->free_area[current_order]);
  			if (list_empty(&area->free_list[migratetype]))
  				continue;
  
  			page = list_entry(area->free_list[migratetype].next,
  					struct page, lru);
  			area->nr_free--;
  
  			/*

  			 * If breaking a large block of pages, move all free

  			 * pages to the preferred allocation list. If falling
  			 * back for a reclaimable kernel allocation, be more
  			 * agressive about taking ownership of free pages

  			 */

  			if (unlikely(current_order >= (pageblock_order >> 1)) ||

  					start_migratetype == MIGRATE_RECLAIMABLE ||
  					page_group_by_mobility_disabled) {

  				unsigned long pages;
  				pages = move_freepages_block(zone, page,
  								start_migratetype);
  
  				/* Claim the whole block if over half of it is free */

  				if (pages >= (1 << (pageblock_order-1)) ||
  						page_group_by_mobility_disabled)

  					set_pageblock_migratetype(page,
  								start_migratetype);

  				migratetype = start_migratetype;

  			}

  
  			/* Remove the page from the freelists */
  			list_del(&page->lru);
  			rmv_page_order(page);

  			/* Take ownership for orders >= pageblock_order */
  			if (current_order >= pageblock_order)
  				change_pageblock_range(page, current_order,

  							start_migratetype);
  
  			expand(zone, page, order, current_order, area, migratetype);

  
  			trace_mm_page_alloc_extfrag(page, order, current_order,
  				start_migratetype, migratetype);

  			return page;
  		}
  	}

  	return NULL;

  }

  /*

   * Do the hard work of removing an element from the buddy allocator.
   * Call me with the zone->lock already held.
   */

  static struct page *__rmqueue(struct zone *zone, unsigned int order,
  						int migratetype)

  {

  	struct page *page;

  retry_reserve:

  	page = __rmqueue_smallest(zone, order, migratetype);

  	if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {

  		page = __rmqueue_fallback(zone, order, migratetype);

  		/*
  		 * Use MIGRATE_RESERVE rather than fail an allocation. goto
  		 * is used because __rmqueue_smallest is an inline function
  		 * and we want just one call site
  		 */
  		if (!page) {
  			migratetype = MIGRATE_RESERVE;
  			goto retry_reserve;
  		}
  	}

  	trace_mm_page_alloc_zone_locked(page, order, migratetype);

  	return page;

  }
  
  /* 
   * Obtain a specified number of elements from the buddy allocator, all under
   * a single hold of the lock, for efficiency.  Add them to the supplied list.
   * Returns the number of new pages which were placed at *list.
   */
  static int rmqueue_bulk(struct zone *zone, unsigned int order, 

  			unsigned long count, struct list_head *list,

  			int migratetype, int cold)

  {

  	int i;

  	spin_lock(&zone->lock);

  	for (i = 0; i < count; ++i) {

  		struct page *page = __rmqueue(zone, order, migratetype);

  		if (unlikely(page == NULL))

  			break;

  
  		/*
  		 * Split buddy pages returned by expand() are received here
  		 * in physical page order. The page is added to the callers and
  		 * list and the list head then moves forward. From the callers
  		 * perspective, the linked list is ordered by page number in
  		 * some conditions. This is useful for IO devices that can
  		 * merge IO requests if the physical pages are ordered
  		 * properly.
  		 */

  		if (likely(cold == 0))
  			list_add(&page->lru, list);
  		else
  			list_add_tail(&page->lru, list);

  		set_page_private(page, migratetype);

  		list = &page->lru;

  	}

  	__mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));

  	spin_unlock(&zone->lock);

  	return i;

  }

  #ifdef CONFIG_NUMA

  /*

   * Called from the vmstat counter updater to drain pagesets of this
   * currently executing processor on remote nodes after they have
   * expired.
   *

   * Note that this function must be called with the thread pinned to
   * a single processor.

   */

  void drain_zone_pages(struct zone *zone, struct per_cpu_pages *pcp)

  {

  	unsigned long flags;

  	int to_drain;

  	local_irq_save(flags);
  	if (pcp->count >= pcp->batch)
  		to_drain = pcp->batch;
  	else
  		to_drain = pcp->count;

  	free_pcppages_bulk(zone, to_drain, pcp);

  	pcp->count -= to_drain;
  	local_irq_restore(flags);

  }
  #endif

  /*
   * Drain pages of the indicated processor.
   *
   * The processor must either be the current processor and the
   * thread pinned to the current processor or a processor that
   * is not online.
   */
  static void drain_pages(unsigned int cpu)

  {

  	unsigned long flags;

  	struct zone *zone;

  	for_each_populated_zone(zone) {

  		struct per_cpu_pageset *pset;

  		struct per_cpu_pages *pcp;

  		local_irq_save(flags);
  		pset = per_cpu_ptr(zone->pageset, cpu);

  
  		pcp = &pset->pcp;

  		free_pcppages_bulk(zone, pcp->count, pcp);

  		pcp->count = 0;
  		local_irq_restore(flags);

  	}
  }

  /*
   * Spill all of this CPU's per-cpu pages back into the buddy allocator.
   */
  void drain_local_pages(void *arg)
  {
  	drain_pages(smp_processor_id());
  }
  
  /*
   * Spill all the per-cpu pages from all CPUs back into the buddy allocator
   */
  void drain_all_pages(void)
  {

  	on_each_cpu(drain_local_pages, NULL, 1);

  }

  #ifdef CONFIG_HIBERNATION

  
  void mark_free_pages(struct zone *zone)
  {

  	unsigned long pfn, max_zone_pfn;
  	unsigned long flags;

  	int order, t;

  	struct list_head *curr;
  
  	if (!zone->spanned_pages)
  		return;
  
  	spin_lock_irqsave(&zone->lock, flags);

  
  	max_zone_pfn = zone->zone_start_pfn + zone->spanned_pages;
  	for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
  		if (pfn_valid(pfn)) {
  			struct page *page = pfn_to_page(pfn);

  			if (!swsusp_page_is_forbidden(page))
  				swsusp_unset_page_free(page);

  		}

  	for_each_migratetype_order(order, t) {
  		list_for_each(curr, &zone->free_area[order].free_list[t]) {

  			unsigned long i;

  			pfn = page_to_pfn(list_entry(curr, struct page, lru));
  			for (i = 0; i < (1UL << order); i++)

  				swsusp_set_page_free(pfn_to_page(pfn + i));

  		}

  	}

  	spin_unlock_irqrestore(&zone->lock, flags);
  }

  #endif /* CONFIG_PM */

  
  /*

   * Free a 0-order page

   * cold == 1 ? free a cold page : free a hot page

   */

  void free_hot_cold_page(struct page *page, int cold)

  {
  	struct zone *zone = page_zone(page);
  	struct per_cpu_pages *pcp;
  	unsigned long flags;

  	int migratetype;

  	int wasMlocked = __TestClearPageMlocked(page);

  	if (!free_pages_prepare(page, 0))

  		return;

  	migratetype = get_pageblock_migratetype(page);
  	set_page_private(page, migratetype);

  	local_irq_save(flags);

  	if (unlikely(wasMlocked))

  		free_page_mlock(page);

  	__count_vm_event(PGFREE);

  	/*
  	 * We only track unmovable, reclaimable and movable on pcp lists.
  	 * Free ISOLATE pages back to the allocator because they are being
  	 * offlined but treat RESERVE as movable pages so we can get those
  	 * areas back if necessary. Otherwise, we may have to free
  	 * excessively into the page allocator
  	 */
  	if (migratetype >= MIGRATE_PCPTYPES) {
  		if (unlikely(migratetype == MIGRATE_ISOLATE)) {
  			free_one_page(zone, page, 0, migratetype);
  			goto out;
  		}
  		migratetype = MIGRATE_MOVABLE;
  	}

  	pcp = &this_cpu_ptr(zone->pageset)->pcp;

  	if (cold)

  		list_add_tail(&page->lru, &pcp->lists[migratetype]);

  	else

  		list_add(&page->lru, &pcp->lists[migratetype]);

  	pcp->count++;

  	if (pcp->count >= pcp->high) {

  		free_pcppages_bulk(zone, pcp->batch, pcp);

  		pcp->count -= pcp->batch;
  	}

  
  out:

  	local_irq_restore(flags);

  }

  /*
   * split_page takes a non-compound higher-order page, and splits it into
   * n (1<<order) sub-pages: page[0..n]
   * Each sub-page must be freed individually.
   *
   * Note: this is probably too low level an operation for use in drivers.
   * Please consult with lkml before using this in your driver.
   */
  void split_page(struct page *page, unsigned int order)
  {
  	int i;

  	VM_BUG_ON(PageCompound(page));
  	VM_BUG_ON(!page_count(page));

  
  #ifdef CONFIG_KMEMCHECK
  	/*
  	 * Split shadow pages too, because free(page[0]) would
  	 * otherwise free the whole shadow.
  	 */
  	if (kmemcheck_page_is_tracked(page))
  		split_page(virt_to_page(page[0].shadow), order);
  #endif

  	for (i = 1; i < (1 << order); i++)
  		set_page_refcounted(page + i);

  }

  /*

   * Similar to split_page except the page is already free. As this is only
   * being used for migration, the migratetype of the block also changes.
   * As this is called with interrupts disabled, the caller is responsible
   * for calling arch_alloc_page() and kernel_map_page() after interrupts
   * are enabled.
   *
   * Note: this is probably too low level an operation for use in drivers.
   * Please consult with lkml before using this in your driver.
   */
  int split_free_page(struct page *page)
  {
  	unsigned int order;
  	unsigned long watermark;
  	struct zone *zone;
  
  	BUG_ON(!PageBuddy(page));
  
  	zone = page_zone(page);
  	order = page_order(page);
  
  	/* Obey watermarks as if the page was being allocated */
  	watermark = low_wmark_pages(zone) + (1 << order);
  	if (!zone_watermark_ok(zone, 0, watermark, 0, 0))
  		return 0;
  
  	/* Remove page from free list */
  	list_del(&page->lru);
  	zone->free_area[order].nr_free--;
  	rmv_page_order(page);
  	__mod_zone_page_state(zone, NR_FREE_PAGES, -(1UL << order));
  
  	/* Split into individual pages */
  	set_page_refcounted(page);
  	split_page(page, order);
  
  	if (order >= pageblock_order - 1) {
  		struct page *endpage = page + (1 << order) - 1;
  		for (; page < endpage; page += pageblock_nr_pages)
  			set_pageblock_migratetype(page, MIGRATE_MOVABLE);
  	}
  
  	return 1 << order;
  }
  
  /*

   * Really, prep_compound_page() should be called from __rmqueue_bulk().  But
   * we cheat by calling it from here, in the order > 0 path.  Saves a branch
   * or two.
   */

  static inline
  struct page *buffered_rmqueue(struct zone *preferred_zone,

  			struct zone *zone, int order, gfp_t gfp_flags,
  			int migratetype)

  {
  	unsigned long flags;

  	struct page *page;

  	int cold = !!(gfp_flags & __GFP_COLD);

  again:

  	if (likely(order == 0)) {

  		struct per_cpu_pages *pcp;

  		struct list_head *list;

  		local_irq_save(flags);

  		pcp = &this_cpu_ptr(zone->pageset)->pcp;
  		list = &pcp->lists[migratetype];

  		if (list_empty(list)) {

  			pcp->count += rmqueue_bulk(zone, 0,

  					pcp->batch, list,

  					migratetype, cold);

  			if (unlikely(list_empty(list)))

  				goto failed;

  		}

  		if (cold)
  			page = list_entry(list->prev, struct page, lru);
  		else
  			page = list_entry(list->next, struct page, lru);

  		list_del(&page->lru);
  		pcp->count--;

  	} else {

  		if (unlikely(gfp_flags & __GFP_NOFAIL)) {
  			/*
  			 * __GFP_NOFAIL is not to be used in new code.
  			 *
  			 * All __GFP_NOFAIL callers should be fixed so that they
  			 * properly detect and handle allocation failures.
  			 *
  			 * We most definitely don't want callers attempting to

  			 * allocate greater than order-1 page units with

  			 * __GFP_NOFAIL.
  			 */

  			WARN_ON_ONCE(order > 1);

  		}

  		spin_lock_irqsave(&zone->lock, flags);

  		page = __rmqueue(zone, order, migratetype);

  		spin_unlock(&zone->lock);
  		if (!page)
  			goto failed;

  		__mod_zone_page_state(zone, NR_FREE_PAGES, -(1 << order));

  	}

  	__count_zone_vm_events(PGALLOC, zone, 1 << order);

  	zone_statistics(preferred_zone, zone);

  	local_irq_restore(flags);

  	VM_BUG_ON(bad_range(zone, page));

  	if (prep_new_page(page, order, gfp_flags))

  		goto again;

  	return page;

  
  failed:
  	local_irq_restore(flags);

  	return NULL;

  }

  /* The ALLOC_WMARK bits are used as an index to zone->watermark */
  #define ALLOC_WMARK_MIN		WMARK_MIN
  #define ALLOC_WMARK_LOW		WMARK_LOW
  #define ALLOC_WMARK_HIGH	WMARK_HIGH
  #define ALLOC_NO_WATERMARKS	0x04 /* don't check watermarks at all */
  
  /* Mask to get the watermark bits */
  #define ALLOC_WMARK_MASK	(ALLOC_NO_WATERMARKS-1)

  #define ALLOC_HARDER		0x10 /* try to alloc harder */
  #define ALLOC_HIGH		0x20 /* __GFP_HIGH set */
  #define ALLOC_CPUSET		0x40 /* check for correct cpuset */

  #ifdef CONFIG_FAIL_PAGE_ALLOC
  
  static struct fail_page_alloc_attr {
  	struct fault_attr attr;
  
  	u32 ignore_gfp_highmem;
  	u32 ignore_gfp_wait;

  	u32 min_order;

  
  #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
  
  	struct dentry *ignore_gfp_highmem_file;
  	struct dentry *ignore_gfp_wait_file;

  	struct dentry *min_order_file;

  
  #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
  
  } fail_page_alloc = {
  	.attr = FAULT_ATTR_INITIALIZER,

  	.ignore_gfp_wait = 1,
  	.ignore_gfp_highmem = 1,

  	.min_order = 1,

  };
  
  static int __init setup_fail_page_alloc(char *str)
  {
  	return setup_fault_attr(&fail_page_alloc.attr, str);
  }
  __setup("fail_page_alloc=", setup_fail_page_alloc);
  
  static int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
  {

  	if (order < fail_page_alloc.min_order)
  		return 0;

  	if (gfp_mask & __GFP_NOFAIL)
  		return 0;
  	if (fail_page_alloc.ignore_gfp_highmem && (gfp_mask & __GFP_HIGHMEM))
  		return 0;
  	if (fail_page_alloc.ignore_gfp_wait && (gfp_mask & __GFP_WAIT))
  		return 0;
  
  	return should_fail(&fail_page_alloc.attr, 1 << order);
  }
  
  #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
  
  static int __init fail_page_alloc_debugfs(void)
  {
  	mode_t mode = S_IFREG | S_IRUSR | S_IWUSR;
  	struct dentry *dir;
  	int err;
  
  	err = init_fault_attr_dentries(&fail_page_alloc.attr,
  				       "fail_page_alloc");
  	if (err)
  		return err;
  	dir = fail_page_alloc.attr.dentries.dir;
  
  	fail_page_alloc.ignore_gfp_wait_file =
  		debugfs_create_bool("ignore-gfp-wait", mode, dir,
  				      &fail_page_alloc.ignore_gfp_wait);
  
  	fail_page_alloc.ignore_gfp_highmem_file =
  		debugfs_create_bool("ignore-gfp-highmem", mode, dir,
  				      &fail_page_alloc.ignore_gfp_highmem);

  	fail_page_alloc.min_order_file =
  		debugfs_create_u32("min-order", mode, dir,
  				   &fail_page_alloc.min_order);

  
  	if (!fail_page_alloc.ignore_gfp_wait_file ||

              !fail_page_alloc.ignore_gfp_highmem_file ||
              !fail_page_alloc.min_order_file) {

  		err = -ENOMEM;
  		debugfs_remove(fail_page_alloc.ignore_gfp_wait_file);
  		debugfs_remove(fail_page_alloc.ignore_gfp_highmem_file);

  		debugfs_remove(fail_page_alloc.min_order_file);

  		cleanup_fault_attr_dentries(&fail_page_alloc.attr);
  	}
  
  	return err;
  }
  
  late_initcall(fail_page_alloc_debugfs);
  
  #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
  
  #else /* CONFIG_FAIL_PAGE_ALLOC */
  
  static inline int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
  {
  	return 0;
  }
  
  #endif /* CONFIG_FAIL_PAGE_ALLOC */

  /*
   * Return 1 if free pages are above 'mark'. This takes into account the order
   * of the allocation.
   */
  int zone_watermark_ok(struct zone *z, int order, unsigned long mark,

  		      int classzone_idx, int alloc_flags)

  {
  	/* free_pages my go negative - that's OK */

  	long min = mark;
  	long free_pages = zone_page_state(z, NR_FREE_PAGES) - (1 << order) + 1;

  	int o;

  	if (alloc_flags & ALLOC_HIGH)

  		min -= min / 2;

  	if (alloc_flags & ALLOC_HARDER)

  		min -= min / 4;
  
  	if (free_pages <= min + z->lowmem_reserve[classzone_idx])
  		return 0;
  	for (o = 0; o < order; o++) {
  		/* At the next order, this order's pages become unavailable */
  		free_pages -= z->free_area[o].nr_free << o;
  
  		/* Require fewer higher order pages to be free */
  		min >>= 1;
  
  		if (free_pages <= min)
  			return 0;
  	}
  	return 1;
  }

  #ifdef CONFIG_NUMA
  /*
   * zlc_setup - Setup for "zonelist cache".  Uses cached zone data to
   * skip over zones that are not allowed by the cpuset, or that have
   * been recently (in last second) found to be nearly full.  See further
   * comments in mmzone.h.  Reduces cache footprint of zonelist scans

   * that have to skip over a lot of full or unallowed zones.

   *
   * If the zonelist cache is present in the passed in zonelist, then
   * returns a pointer to the allowed node mask (either the current

   * tasks mems_allowed, or node_states[N_HIGH_MEMORY].)

   *
   * If the zonelist cache is not available for this zonelist, does
   * nothing and returns NULL.
   *
   * If the fullzones BITMAP in the zonelist cache is stale (more than
   * a second since last zap'd) then we zap it out (clear its bits.)
   *
   * We hold off even calling zlc_setup, until after we've checked the
   * first zone in the zonelist, on the theory that most allocations will
   * be satisfied from that first zone, so best to examine that zone as
   * quickly as we can.
   */
  static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
  {
  	struct zonelist_cache *zlc;	/* cached zonelist speedup info */
  	nodemask_t *allowednodes;	/* zonelist_cache approximation */
  
  	zlc = zonelist->zlcache_ptr;
  	if (!zlc)
  		return NULL;

  	if (time_after(jiffies, zlc->last_full_zap + HZ)) {

  		bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
  		zlc->last_full_zap = jiffies;
  	}
  
  	allowednodes = !in_interrupt() && (alloc_flags & ALLOC_CPUSET) ?
  					&cpuset_current_mems_allowed :

  					&node_states[N_HIGH_MEMORY];

  	return allowednodes;
  }
  
  /*
   * Given 'z' scanning a zonelist, run a couple of quick checks to see
   * if it is worth looking at further for free memory:
   *  1) Check that the zone isn't thought to be full (doesn't have its
   *     bit set in the zonelist_cache fullzones BITMAP).
   *  2) Check that the zones node (obtained from the zonelist_cache
   *     z_to_n[] mapping) is allowed in the passed in allowednodes mask.
   * Return true (non-zero) if zone is worth looking at further, or
   * else return false (zero) if it is not.
   *
   * This check -ignores- the distinction between various watermarks,
   * such as GFP_HIGH, GFP_ATOMIC, PF_MEMALLOC, ...  If a zone is
   * found to be full for any variation of these watermarks, it will
   * be considered full for up to one second by all requests, unless
   * we are so low on memory on all allowed nodes that we are forced
   * into the second scan of the zonelist.
   *
   * In the second scan we ignore this zonelist cache and exactly
   * apply the watermarks to all zones, even it is slower to do so.
   * We are low on memory in the second scan, and should leave no stone
   * unturned looking for a free page.
   */

  static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zoneref *z,

  						nodemask_t *allowednodes)
  {
  	struct zonelist_cache *zlc;	/* cached zonelist speedup info */
  	int i;				/* index of *z in zonelist zones */
  	int n;				/* node that zone *z is on */
  
  	zlc = zonelist->zlcache_ptr;
  	if (!zlc)
  		return 1;

  	i = z - zonelist->_zonerefs;

  	n = zlc->z_to_n[i];
  
  	/* This zone is worth trying if it is allowed but not full */
  	return node_isset(n, *allowednodes) && !test_bit(i, zlc->fullzones);
  }
  
  /*
   * Given 'z' scanning a zonelist, set the corresponding bit in
   * zlc->fullzones, so that subsequent attempts to allocate a page
   * from that zone don't waste time re-examining it.
   */

  static void zlc_mark_zone_full(struct zonelist *zonelist, struct zoneref *z)

  {
  	struct zonelist_cache *zlc;	/* cached zonelist speedup info */
  	int i;				/* index of *z in zonelist zones */
  
  	zlc = zonelist->zlcache_ptr;
  	if (!zlc)
  		return;

  	i = z - zonelist->_zonerefs;

  
  	set_bit(i, zlc->fullzones);
  }
  
  #else	/* CONFIG_NUMA */
  
  static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
  {
  	return NULL;
  }

  static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zoneref *z,

  				nodemask_t *allowednodes)
  {
  	return 1;
  }

  static void zlc_mark_zone_full(struct zonelist *zonelist, struct zoneref *z)

  {
  }
  #endif	/* CONFIG_NUMA */

  /*

   * get_page_from_freelist goes through the zonelist trying to allocate

   * a page.
   */
  static struct page *

  get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order,

  		struct zonelist *zonelist, int high_zoneidx, int alloc_flags,

  		struct zone *preferred_zone, int migratetype)

  {

  	struct zoneref *z;

  	struct page *page = NULL;

  	int classzone_idx;

  	struct zone *zone;

  	nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
  	int zlc_active = 0;		/* set if using zonelist_cache */
  	int did_zlc_setup = 0;		/* just call zlc_setup() one time */

  	classzone_idx = zone_idx(preferred_zone);

  zonelist_scan:

  	/*

  	 * Scan zonelist, looking for a zone with enough free.

  	 * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
  	 */

  	for_each_zone_zonelist_nodemask(zone, z, zonelist,
  						high_zoneidx, nodemask) {

  		if (NUMA_BUILD && zlc_active &&
  			!zlc_zone_worth_trying(zonelist, z, allowednodes))
  				continue;

  		if ((alloc_flags & ALLOC_CPUSET) &&

  			!cpuset_zone_allowed_softwall(zone, gfp_mask))

  				goto try_next_zone;

  		BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);

  		if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {

  			unsigned long mark;

  			int ret;

  			mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];

  			if (zone_watermark_ok(zone, order, mark,
  				    classzone_idx, alloc_flags))
  				goto try_this_zone;
  
  			if (zone_reclaim_mode == 0)
  				goto this_zone_full;
  
  			ret = zone_reclaim(zone, gfp_mask, order);
  			switch (ret) {
  			case ZONE_RECLAIM_NOSCAN:
  				/* did not scan */
  				goto try_next_zone;
  			case ZONE_RECLAIM_FULL:
  				/* scanned but unreclaimable */
  				goto this_zone_full;
  			default:
  				/* did we reclaim enough */
  				if (!zone_watermark_ok(zone, order, mark,
  						classzone_idx, alloc_flags))

  					goto this_zone_full;

  			}

  		}

  try_this_zone:

  		page = buffered_rmqueue(preferred_zone, zone, order,
  						gfp_mask, migratetype);

  		if (page)

  			break;

  this_zone_full:
  		if (NUMA_BUILD)
  			zlc_mark_zone_full(zonelist, z);
  try_next_zone:

  		if (NUMA_BUILD && !did_zlc_setup && nr_online_nodes > 1) {

  			/*
  			 * we do zlc_setup after the first zone is tried but only
  			 * if there are multiple nodes make it worthwhile
  			 */

  			allowednodes = zlc_setup(zonelist, alloc_flags);
  			zlc_active = 1;
  			did_zlc_setup = 1;
  		}

  	}

  
  	if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {
  		/* Disable zlc cache for second zonelist scan */
  		zlc_active = 0;
  		goto zonelist_scan;
  	}

  	return page;

  }

  static inline int
  should_alloc_retry(gfp_t gfp_mask, unsigned int order,
  				unsigned long pages_reclaimed)

  {

  	/* Do not loop if specifically requested */
  	if (gfp_mask & __GFP_NORETRY)
  		return 0;

  	/*
  	 * In this implementation, order <= PAGE_ALLOC_COSTLY_ORDER
  	 * means __GFP_NOFAIL, but that may not be true in other
  	 * implementations.
  	 */
  	if (order <= PAGE_ALLOC_COSTLY_ORDER)
  		return 1;
  
  	/*
  	 * For order > PAGE_ALLOC_COSTLY_ORDER, if __GFP_REPEAT is
  	 * specified, then we retry until we no longer reclaim any pages
  	 * (above), or we've reclaimed an order of pages at least as
  	 * large as the allocation's order. In both cases, if the
  	 * allocation still fails, we stop retrying.
  	 */
  	if (gfp_mask & __GFP_REPEAT && pages_reclaimed < (1 << order))
  		return 1;

  	/*
  	 * Don't let big-order allocations loop unless the caller
  	 * explicitly requests that.
  	 */
  	if (gfp_mask & __GFP_NOFAIL)
  		return 1;

  	return 0;
  }

  static inline struct page *
  __alloc_pages_may_oom(gfp_t gfp_mask, unsigned int order,
  	struct zonelist *zonelist, enum zone_type high_zoneidx,

  	nodemask_t *nodemask, struct zone *preferred_zone,
  	int migratetype)

  {
  	struct page *page;
  
  	/* Acquire the OOM killer lock for the zones in zonelist */
  	if (!try_set_zone_oom(zonelist, gfp_mask)) {
  		schedule_timeout_uninterruptible(1);

  		return NULL;
  	}

  	/*
  	 * Go through the zonelist yet one more time, keep very high watermark
  	 * here, this is only to catch a parallel oom killing, we must fail if
  	 * we're still under heavy pressure.
  	 */
  	page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask,
  		order, zonelist, high_zoneidx,

  		ALLOC_WMARK_HIGH|ALLOC_CPUSET,

  		preferred_zone, migratetype);

  	if (page)