/*
   * linux/mm/slab.c
   * Written by Mark Hemment, 1996/97.
   * (markhe@nextd.demon.co.uk)
   *
   * kmem_cache_destroy() + some cleanup - 1999 Andrea Arcangeli
   *
   * Major cleanup, different bufctl logic, per-cpu arrays
   *	(c) 2000 Manfred Spraul
   *
   * Cleanup, make the head arrays unconditional, preparation for NUMA
   * 	(c) 2002 Manfred Spraul
   *
   * An implementation of the Slab Allocator as described in outline in;
   *	UNIX Internals: The New Frontiers by Uresh Vahalia
   *	Pub: Prentice Hall	ISBN 0-13-101908-2
   * or with a little more detail in;
   *	The Slab Allocator: An Object-Caching Kernel Memory Allocator
   *	Jeff Bonwick (Sun Microsystems).
   *	Presented at: USENIX Summer 1994 Technical Conference
   *
   * The memory is organized in caches, one cache for each object type.
   * (e.g. inode_cache, dentry_cache, buffer_head, vm_area_struct)
   * Each cache consists out of many slabs (they are small (usually one
   * page long) and always contiguous), and each slab contains multiple
   * initialized objects.
   *
   * This means, that your constructor is used only for newly allocated

   * slabs and you must pass objects with the same initializations to

   * kmem_cache_free.
   *
   * Each cache can only support one memory type (GFP_DMA, GFP_HIGHMEM,
   * normal). If you need a special memory type, then must create a new
   * cache for that memory type.
   *
   * In order to reduce fragmentation, the slabs are sorted in 3 groups:
   *   full slabs with 0 free objects
   *   partial slabs
   *   empty slabs with no allocated objects
   *
   * If partial slabs exist, then new allocations come from these slabs,
   * otherwise from empty slabs or new slabs are allocated.
   *
   * kmem_cache_destroy() CAN CRASH if you try to allocate from the cache
   * during kmem_cache_destroy(). The caller must prevent concurrent allocs.
   *
   * Each cache has a short per-cpu head array, most allocs
   * and frees go into that array, and if that array overflows, then 1/2
   * of the entries in the array are given back into the global cache.
   * The head array is strictly LIFO and should improve the cache hit rates.
   * On SMP, it additionally reduces the spinlock operations.
   *

   * The c_cpuarray may not be read with enabled local interrupts -

   * it's changed with a smp_call_function().
   *
   * SMP synchronization:
   *  constructors and destructors are called without any locking.

   *  Several members in struct kmem_cache and struct slab never change, they

   *	are accessed without any locking.
   *  The per-cpu arrays are never accessed from the wrong cpu, no locking,
   *  	and local interrupts are disabled so slab code is preempt-safe.
   *  The non-constant members are protected with a per-cache irq spinlock.
   *
   * Many thanks to Mark Hemment, who wrote another per-cpu slab patch
   * in 2000 - many ideas in the current implementation are derived from
   * his patch.
   *
   * Further notes from the original documentation:
   *
   * 11 April '97.  Started multi-threading - markhe

   *	The global cache-chain is protected by the mutex 'cache_chain_mutex'.

   *	The sem is only needed when accessing/extending the cache-chain, which
   *	can never happen inside an interrupt (kmem_cache_create(),
   *	kmem_cache_shrink() and kmem_cache_reap()).
   *
   *	At present, each engine can be growing a cache.  This should be blocked.
   *

   * 15 March 2005. NUMA slab allocator.
   *	Shai Fultheim <shai@scalex86.org>.
   *	Shobhit Dayal <shobhit@calsoftinc.com>
   *	Alok N Kataria <alokk@calsoftinc.com>
   *	Christoph Lameter <christoph@lameter.com>
   *
   *	Modified the slab allocator to be node aware on NUMA systems.
   *	Each node has its own list of partial, free and full slabs.
   *	All object allocations for a node occur from node specific slab lists.

   */

  #include	<linux/slab.h>
  #include	<linux/mm.h>

  #include	<linux/poison.h>

  #include	<linux/swap.h>
  #include	<linux/cache.h>
  #include	<linux/interrupt.h>
  #include	<linux/init.h>
  #include	<linux/compiler.h>

  #include	<linux/cpuset.h>

  #include	<linux/proc_fs.h>

  #include	<linux/seq_file.h>
  #include	<linux/notifier.h>
  #include	<linux/kallsyms.h>
  #include	<linux/cpu.h>
  #include	<linux/sysctl.h>
  #include	<linux/module.h>
  #include	<linux/rcupdate.h>

  #include	<linux/string.h>

  #include	<linux/uaccess.h>

  #include	<linux/nodemask.h>

  #include	<linux/mempolicy.h>

  #include	<linux/mutex.h>

  #include	<linux/fault-inject.h>

  #include	<linux/rtmutex.h>

  #include	<linux/reciprocal_div.h>

  #include	<linux/debugobjects.h>

  #include	<asm/cacheflush.h>
  #include	<asm/tlbflush.h>
  #include	<asm/page.h>
  
  /*

   * DEBUG	- 1 for kmem_cache_create() to honour; SLAB_RED_ZONE & SLAB_POISON.

   *		  0 for faster, smaller code (especially in the critical paths).
   *
   * STATS	- 1 to collect stats for /proc/slabinfo.
   *		  0 for faster, smaller code (especially in the critical paths).
   *
   * FORCED_DEBUG	- 1 enables SLAB_RED_ZONE and SLAB_POISON (if possible)
   */
  
  #ifdef CONFIG_DEBUG_SLAB
  #define	DEBUG		1
  #define	STATS		1
  #define	FORCED_DEBUG	1
  #else
  #define	DEBUG		0
  #define	STATS		0
  #define	FORCED_DEBUG	0
  #endif

  /* Shouldn't this be in a header file somewhere? */
  #define	BYTES_PER_WORD		sizeof(void *)

  #define	REDZONE_ALIGN		max(BYTES_PER_WORD, __alignof__(unsigned long long))

  #ifndef ARCH_KMALLOC_MINALIGN
  /*
   * Enforce a minimum alignment for the kmalloc caches.
   * Usually, the kmalloc caches are cache_line_size() aligned, except when
   * DEBUG and FORCED_DEBUG are enabled, then they are BYTES_PER_WORD aligned.
   * Some archs want to perform DMA into kmalloc caches and need a guaranteed

   * alignment larger than the alignment of a 64-bit integer.
   * ARCH_KMALLOC_MINALIGN allows that.
   * Note that increasing this value may disable some debug features.

   */

  #define ARCH_KMALLOC_MINALIGN __alignof__(unsigned long long)

  #endif
  
  #ifndef ARCH_SLAB_MINALIGN
  /*
   * Enforce a minimum alignment for all caches.
   * Intended for archs that get misalignment faults even for BYTES_PER_WORD
   * aligned buffers. Includes ARCH_KMALLOC_MINALIGN.
   * If possible: Do not enable this flag for CONFIG_DEBUG_SLAB, it disables
   * some debug features.
   */
  #define ARCH_SLAB_MINALIGN 0
  #endif
  
  #ifndef ARCH_KMALLOC_FLAGS
  #define ARCH_KMALLOC_FLAGS SLAB_HWCACHE_ALIGN
  #endif
  
  /* Legal flag mask for kmem_cache_create(). */
  #if DEBUG

  # define CREATE_MASK	(SLAB_RED_ZONE | \

  			 SLAB_POISON | SLAB_HWCACHE_ALIGN | \

  			 SLAB_CACHE_DMA | \

  			 SLAB_STORE_USER | \

  			 SLAB_RECLAIM_ACCOUNT | SLAB_PANIC | \

  			 SLAB_DESTROY_BY_RCU | SLAB_MEM_SPREAD | \
  			 SLAB_DEBUG_OBJECTS)

  #else

  # define CREATE_MASK	(SLAB_HWCACHE_ALIGN | \

  			 SLAB_CACHE_DMA | \

  			 SLAB_RECLAIM_ACCOUNT | SLAB_PANIC | \

  			 SLAB_DESTROY_BY_RCU | SLAB_MEM_SPREAD | \
  			 SLAB_DEBUG_OBJECTS)

  #endif
  
  /*
   * kmem_bufctl_t:
   *
   * Bufctl's are used for linking objs within a slab
   * linked offsets.
   *
   * This implementation relies on "struct page" for locating the cache &
   * slab an object belongs to.
   * This allows the bufctl structure to be small (one int), but limits
   * the number of objects a slab (not a cache) can contain when off-slab
   * bufctls are used. The limit is the size of the largest general cache
   * that does not use off-slab slabs.
   * For 32bit archs with 4 kB pages, is this 56.
   * This is not serious, as it is only for large objects, when it is unwise
   * to have too many per slab.
   * Note: This limit can be raised by introducing a general cache whose size
   * is less than 512 (PAGE_SIZE<<3), but greater than 256.
   */

  typedef unsigned int kmem_bufctl_t;

  #define BUFCTL_END	(((kmem_bufctl_t)(~0U))-0)
  #define BUFCTL_FREE	(((kmem_bufctl_t)(~0U))-1)

  #define	BUFCTL_ACTIVE	(((kmem_bufctl_t)(~0U))-2)
  #define	SLAB_LIMIT	(((kmem_bufctl_t)(~0U))-3)

  /*
   * struct slab
   *
   * Manages the objs in a slab. Placed either at the beginning of mem allocated
   * for a slab, or allocated from an general cache.
   * Slabs are chained into three list: fully used, partial, fully free slabs.
   */
  struct slab {

  	struct list_head list;
  	unsigned long colouroff;
  	void *s_mem;		/* including colour offset */
  	unsigned int inuse;	/* num of objs active in slab */
  	kmem_bufctl_t free;
  	unsigned short nodeid;

  };
  
  /*
   * struct slab_rcu
   *
   * slab_destroy on a SLAB_DESTROY_BY_RCU cache uses this structure to
   * arrange for kmem_freepages to be called via RCU.  This is useful if
   * we need to approach a kernel structure obliquely, from its address
   * obtained without the usual locking.  We can lock the structure to
   * stabilize it and check it's still at the given address, only if we
   * can be sure that the memory has not been meanwhile reused for some
   * other kind of object (which our subsystem's lock might corrupt).
   *
   * rcu_read_lock before reading the address, then rcu_read_unlock after
   * taking the spinlock within the structure expected at that address.
   *
   * We assume struct slab_rcu can overlay struct slab when destroying.
   */
  struct slab_rcu {

  	struct rcu_head head;

  	struct kmem_cache *cachep;

  	void *addr;

  };
  
  /*
   * struct array_cache
   *

   * Purpose:
   * - LIFO ordering, to hand out cache-warm objects from _alloc
   * - reduce the number of linked list operations
   * - reduce spinlock operations
   *
   * The limit is stored in the per-cpu structure to reduce the data cache
   * footprint.
   *
   */
  struct array_cache {
  	unsigned int avail;
  	unsigned int limit;
  	unsigned int batchcount;
  	unsigned int touched;

  	spinlock_t lock;

  	void *entry[];	/*

  			 * Must have this definition in here for the proper
  			 * alignment of array_cache. Also simplifies accessing
  			 * the entries.

  			 */

  };

  /*
   * bootstrap: The caches do not work without cpuarrays anymore, but the
   * cpuarrays are allocated from the generic caches...

   */
  #define BOOT_CPUCACHE_ENTRIES	1
  struct arraycache_init {
  	struct array_cache cache;

  	void *entries[BOOT_CPUCACHE_ENTRIES];

  };
  
  /*

   * The slab lists for all objects.

   */
  struct kmem_list3 {

  	struct list_head slabs_partial;	/* partial list first, better asm code */
  	struct list_head slabs_full;
  	struct list_head slabs_free;
  	unsigned long free_objects;

  	unsigned int free_limit;

  	unsigned int colour_next;	/* Per-node cache coloring */

  	spinlock_t list_lock;
  	struct array_cache *shared;	/* shared per node */
  	struct array_cache **alien;	/* on other nodes */

  	unsigned long next_reap;	/* updated without locking */
  	int free_touched;		/* updated without locking */

  };

  /*
   * Need this for bootstrapping a per node allocator.
   */

  #define NUM_INIT_LISTS (3 * MAX_NUMNODES)

  struct kmem_list3 __initdata initkmem_list3[NUM_INIT_LISTS];
  #define	CACHE_CACHE 0

  #define	SIZE_AC MAX_NUMNODES
  #define	SIZE_L3 (2 * MAX_NUMNODES)

  static int drain_freelist(struct kmem_cache *cache,
  			struct kmem_list3 *l3, int tofree);
  static void free_block(struct kmem_cache *cachep, void **objpp, int len,
  			int node);

  static int enable_cpucache(struct kmem_cache *cachep);

  static void cache_reap(struct work_struct *unused);

  /*

   * This function must be completely optimized away if a constant is passed to
   * it.  Mostly the same as what is in linux/slab.h except it returns an index.

   */

  static __always_inline int index_of(const size_t size)

  {

  	extern void __bad_size(void);

  	if (__builtin_constant_p(size)) {
  		int i = 0;
  
  #define CACHE(x) \
  	if (size <=x) \
  		return i; \
  	else \
  		i++;

  #include <linux/kmalloc_sizes.h>

  #undef CACHE

  		__bad_size();

  	} else

  		__bad_size();

  	return 0;
  }

  static int slab_early_init = 1;

  #define INDEX_AC index_of(sizeof(struct arraycache_init))
  #define INDEX_L3 index_of(sizeof(struct kmem_list3))

  static void kmem_list3_init(struct kmem_list3 *parent)

  {
  	INIT_LIST_HEAD(&parent->slabs_full);
  	INIT_LIST_HEAD(&parent->slabs_partial);
  	INIT_LIST_HEAD(&parent->slabs_free);
  	parent->shared = NULL;
  	parent->alien = NULL;

  	parent->colour_next = 0;

  	spin_lock_init(&parent->list_lock);
  	parent->free_objects = 0;
  	parent->free_touched = 0;
  }

  #define MAKE_LIST(cachep, listp, slab, nodeid)				\
  	do {								\
  		INIT_LIST_HEAD(listp);					\
  		list_splice(&(cachep->nodelists[nodeid]->slab), listp);	\

  	} while (0)

  #define	MAKE_ALL_LISTS(cachep, ptr, nodeid)				\
  	do {								\

  	MAKE_LIST((cachep), (&(ptr)->slabs_full), slabs_full, nodeid);	\
  	MAKE_LIST((cachep), (&(ptr)->slabs_partial), slabs_partial, nodeid); \
  	MAKE_LIST((cachep), (&(ptr)->slabs_free), slabs_free, nodeid);	\
  	} while (0)

  
  /*

   * struct kmem_cache

   *
   * manages a cache.
   */

  struct kmem_cache {

  /* 1) per-cpu data, touched during every alloc/free */

  	struct array_cache *array[NR_CPUS];

  /* 2) Cache tunables. Protected by cache_chain_mutex */

  	unsigned int batchcount;
  	unsigned int limit;
  	unsigned int shared;

  	unsigned int buffer_size;

  	u32 reciprocal_buffer_size;

  /* 3) touched by every alloc & free from the backend */

  	unsigned int flags;		/* constant flags */
  	unsigned int num;		/* # of objs per slab */

  /* 4) cache_grow/shrink */

  	/* order of pgs per slab (2^n) */

  	unsigned int gfporder;

  
  	/* force GFP flags, e.g. GFP_DMA */

  	gfp_t gfpflags;

  	size_t colour;			/* cache colouring range */

  	unsigned int colour_off;	/* colour offset */

  	struct kmem_cache *slabp_cache;

  	unsigned int slab_size;

  	unsigned int dflags;		/* dynamic flags */

  
  	/* constructor func */

  	void (*ctor)(void *obj);

  /* 5) cache creation/removal */

  	const char *name;
  	struct list_head next;

  /* 6) statistics */

  #if STATS

  	unsigned long num_active;
  	unsigned long num_allocations;
  	unsigned long high_mark;
  	unsigned long grown;
  	unsigned long reaped;
  	unsigned long errors;
  	unsigned long max_freeable;
  	unsigned long node_allocs;
  	unsigned long node_frees;

  	unsigned long node_overflow;

  	atomic_t allochit;
  	atomic_t allocmiss;
  	atomic_t freehit;
  	atomic_t freemiss;

  #endif
  #if DEBUG

  	/*
  	 * If debugging is enabled, then the allocator can add additional
  	 * fields and/or padding to every object. buffer_size contains the total
  	 * object size including these internal fields, the following two
  	 * variables contain the offset to the user object and its size.
  	 */
  	int obj_offset;
  	int obj_size;

  #endif

  	/*
  	 * We put nodelists[] at the end of kmem_cache, because we want to size
  	 * this array to nr_node_ids slots instead of MAX_NUMNODES
  	 * (see kmem_cache_init())
  	 * We still use [MAX_NUMNODES] and not [1] or [0] because cache_cache
  	 * is statically defined, so we reserve the max number of nodes.
  	 */
  	struct kmem_list3 *nodelists[MAX_NUMNODES];
  	/*
  	 * Do not add fields after nodelists[]
  	 */

  };
  
  #define CFLGS_OFF_SLAB		(0x80000000UL)
  #define	OFF_SLAB(x)	((x)->flags & CFLGS_OFF_SLAB)
  
  #define BATCHREFILL_LIMIT	16

  /*
   * Optimization question: fewer reaps means less probability for unnessary
   * cpucache drain/refill cycles.

   *

   * OTOH the cpuarrays can contain lots of objects,

   * which could lock up otherwise freeable slabs.
   */
  #define REAPTIMEOUT_CPUC	(2*HZ)
  #define REAPTIMEOUT_LIST3	(4*HZ)
  
  #if STATS
  #define	STATS_INC_ACTIVE(x)	((x)->num_active++)
  #define	STATS_DEC_ACTIVE(x)	((x)->num_active--)
  #define	STATS_INC_ALLOCED(x)	((x)->num_allocations++)
  #define	STATS_INC_GROWN(x)	((x)->grown++)

  #define	STATS_ADD_REAPED(x,y)	((x)->reaped += (y))

  #define	STATS_SET_HIGH(x)						\
  	do {								\
  		if ((x)->num_active > (x)->high_mark)			\
  			(x)->high_mark = (x)->num_active;		\
  	} while (0)

  #define	STATS_INC_ERR(x)	((x)->errors++)
  #define	STATS_INC_NODEALLOCS(x)	((x)->node_allocs++)

  #define	STATS_INC_NODEFREES(x)	((x)->node_frees++)

  #define STATS_INC_ACOVERFLOW(x)   ((x)->node_overflow++)

  #define	STATS_SET_FREEABLE(x, i)					\
  	do {								\
  		if ((x)->max_freeable < i)				\
  			(x)->max_freeable = i;				\
  	} while (0)

  #define STATS_INC_ALLOCHIT(x)	atomic_inc(&(x)->allochit)
  #define STATS_INC_ALLOCMISS(x)	atomic_inc(&(x)->allocmiss)
  #define STATS_INC_FREEHIT(x)	atomic_inc(&(x)->freehit)
  #define STATS_INC_FREEMISS(x)	atomic_inc(&(x)->freemiss)
  #else
  #define	STATS_INC_ACTIVE(x)	do { } while (0)
  #define	STATS_DEC_ACTIVE(x)	do { } while (0)
  #define	STATS_INC_ALLOCED(x)	do { } while (0)
  #define	STATS_INC_GROWN(x)	do { } while (0)

  #define	STATS_ADD_REAPED(x,y)	do { } while (0)

  #define	STATS_SET_HIGH(x)	do { } while (0)
  #define	STATS_INC_ERR(x)	do { } while (0)
  #define	STATS_INC_NODEALLOCS(x)	do { } while (0)

  #define	STATS_INC_NODEFREES(x)	do { } while (0)

  #define STATS_INC_ACOVERFLOW(x)   do { } while (0)

  #define	STATS_SET_FREEABLE(x, i) do { } while (0)

  #define STATS_INC_ALLOCHIT(x)	do { } while (0)
  #define STATS_INC_ALLOCMISS(x)	do { } while (0)
  #define STATS_INC_FREEHIT(x)	do { } while (0)
  #define STATS_INC_FREEMISS(x)	do { } while (0)
  #endif
  
  #if DEBUG

  /*
   * memory layout of objects:

   * 0		: objp

   * 0 .. cachep->obj_offset - BYTES_PER_WORD - 1: padding. This ensures that

   * 		the end of an object is aligned with the end of the real
   * 		allocation. Catches writes behind the end of the allocation.

   * cachep->obj_offset - BYTES_PER_WORD .. cachep->obj_offset - 1:

   * 		redzone word.

   * cachep->obj_offset: The real object.
   * cachep->buffer_size - 2* BYTES_PER_WORD: redzone word [BYTES_PER_WORD long]

   * cachep->buffer_size - 1* BYTES_PER_WORD: last caller address
   *					[BYTES_PER_WORD long]

   */

  static int obj_offset(struct kmem_cache *cachep)

  {

  	return cachep->obj_offset;

  }

  static int obj_size(struct kmem_cache *cachep)

  {

  	return cachep->obj_size;

  }

  static unsigned long long *dbg_redzone1(struct kmem_cache *cachep, void *objp)

  {
  	BUG_ON(!(cachep->flags & SLAB_RED_ZONE));

  	return (unsigned long long*) (objp + obj_offset(cachep) -
  				      sizeof(unsigned long long));

  }

  static unsigned long long *dbg_redzone2(struct kmem_cache *cachep, void *objp)

  {
  	BUG_ON(!(cachep->flags & SLAB_RED_ZONE));
  	if (cachep->flags & SLAB_STORE_USER)

  		return (unsigned long long *)(objp + cachep->buffer_size -
  					      sizeof(unsigned long long) -

  					      REDZONE_ALIGN);

  	return (unsigned long long *) (objp + cachep->buffer_size -
  				       sizeof(unsigned long long));

  }

  static void **dbg_userword(struct kmem_cache *cachep, void *objp)

  {
  	BUG_ON(!(cachep->flags & SLAB_STORE_USER));

  	return (void **)(objp + cachep->buffer_size - BYTES_PER_WORD);

  }
  
  #else

  #define obj_offset(x)			0
  #define obj_size(cachep)		(cachep->buffer_size)

  #define dbg_redzone1(cachep, objp)	({BUG(); (unsigned long long *)NULL;})
  #define dbg_redzone2(cachep, objp)	({BUG(); (unsigned long long *)NULL;})

  #define dbg_userword(cachep, objp)	({BUG(); (void **)NULL;})
  
  #endif
  
  /*

   * Do not go above this order unless 0 objects fit into the slab.
   */
  #define	BREAK_GFP_ORDER_HI	1
  #define	BREAK_GFP_ORDER_LO	0
  static int slab_break_gfp_order = BREAK_GFP_ORDER_LO;

  /*
   * Functions for storing/retrieving the cachep and or slab from the page
   * allocator.  These are used to find the slab an obj belongs to.  With kfree(),
   * these are used to find the cache which an obj belongs to.

   */

  static inline void page_set_cache(struct page *page, struct kmem_cache *cache)
  {
  	page->lru.next = (struct list_head *)cache;
  }
  
  static inline struct kmem_cache *page_get_cache(struct page *page)
  {

  	page = compound_head(page);

  	BUG_ON(!PageSlab(page));

  	return (struct kmem_cache *)page->lru.next;
  }
  
  static inline void page_set_slab(struct page *page, struct slab *slab)
  {
  	page->lru.prev = (struct list_head *)slab;
  }
  
  static inline struct slab *page_get_slab(struct page *page)
  {

  	BUG_ON(!PageSlab(page));

  	return (struct slab *)page->lru.prev;
  }

  static inline struct kmem_cache *virt_to_cache(const void *obj)
  {

  	struct page *page = virt_to_head_page(obj);

  	return page_get_cache(page);
  }
  
  static inline struct slab *virt_to_slab(const void *obj)
  {

  	struct page *page = virt_to_head_page(obj);

  	return page_get_slab(page);
  }

  static inline void *index_to_obj(struct kmem_cache *cache, struct slab *slab,
  				 unsigned int idx)
  {
  	return slab->s_mem + cache->buffer_size * idx;
  }

  /*
   * We want to avoid an expensive divide : (offset / cache->buffer_size)
   *   Using the fact that buffer_size is a constant for a particular cache,
   *   we can replace (offset / cache->buffer_size) by
   *   reciprocal_divide(offset, cache->reciprocal_buffer_size)
   */
  static inline unsigned int obj_to_index(const struct kmem_cache *cache,
  					const struct slab *slab, void *obj)

  {

  	u32 offset = (obj - slab->s_mem);
  	return reciprocal_divide(offset, cache->reciprocal_buffer_size);

  }

  /*
   * These are the default caches for kmalloc. Custom caches can have other sizes.
   */

  struct cache_sizes malloc_sizes[] = {
  #define CACHE(x) { .cs_size = (x) },
  #include <linux/kmalloc_sizes.h>
  	CACHE(ULONG_MAX)
  #undef CACHE
  };
  EXPORT_SYMBOL(malloc_sizes);
  
  /* Must match cache_sizes above. Out of line to keep cache footprint low. */
  struct cache_names {
  	char *name;
  	char *name_dma;
  };
  
  static struct cache_names __initdata cache_names[] = {
  #define CACHE(x) { .name = "size-" #x, .name_dma = "size-" #x "(DMA)" },
  #include <linux/kmalloc_sizes.h>

  	{NULL,}

  #undef CACHE
  };
  
  static struct arraycache_init initarray_cache __initdata =

      { {0, BOOT_CPUCACHE_ENTRIES, 1, 0} };

  static struct arraycache_init initarray_generic =

      { {0, BOOT_CPUCACHE_ENTRIES, 1, 0} };

  
  /* internal cache of cache description objs */

  static struct kmem_cache cache_cache = {

  	.batchcount = 1,
  	.limit = BOOT_CPUCACHE_ENTRIES,
  	.shared = 1,

  	.buffer_size = sizeof(struct kmem_cache),

  	.name = "kmem_cache",

  };

  #define BAD_ALIEN_MAGIC 0x01020304ul

  #ifdef CONFIG_LOCKDEP
  
  /*
   * Slab sometimes uses the kmalloc slabs to store the slab headers
   * for other slabs "off slab".
   * The locking for this is tricky in that it nests within the locks
   * of all other slabs in a few places; to deal with this special
   * locking we put on-slab caches into a separate lock-class.

   *
   * We set lock class for alien array caches which are up during init.
   * The lock annotation will be lost if all cpus of a node goes down and
   * then comes back up during hotplug

   */

  static struct lock_class_key on_slab_l3_key;
  static struct lock_class_key on_slab_alc_key;
  
  static inline void init_lock_keys(void)

  {
  	int q;

  	struct cache_sizes *s = malloc_sizes;
  
  	while (s->cs_size != ULONG_MAX) {
  		for_each_node(q) {
  			struct array_cache **alc;
  			int r;
  			struct kmem_list3 *l3 = s->cs_cachep->nodelists[q];
  			if (!l3 || OFF_SLAB(s->cs_cachep))
  				continue;
  			lockdep_set_class(&l3->list_lock, &on_slab_l3_key);
  			alc = l3->alien;
  			/*
  			 * FIXME: This check for BAD_ALIEN_MAGIC
  			 * should go away when common slab code is taught to
  			 * work even without alien caches.
  			 * Currently, non NUMA code returns BAD_ALIEN_MAGIC
  			 * for alloc_alien_cache,
  			 */
  			if (!alc || (unsigned long)alc == BAD_ALIEN_MAGIC)
  				continue;
  			for_each_node(r) {
  				if (alc[r])
  					lockdep_set_class(&alc[r]->lock,
  					     &on_slab_alc_key);
  			}
  		}
  		s++;

  	}
  }

  #else

  static inline void init_lock_keys(void)

  {
  }
  #endif

  /*

   * Guard access to the cache-chain.

   */

  static DEFINE_MUTEX(cache_chain_mutex);

  static struct list_head cache_chain;
  
  /*

   * chicken and egg problem: delay the per-cpu array allocation
   * until the general caches are up.
   */
  static enum {
  	NONE,

  	PARTIAL_AC,
  	PARTIAL_L3,

  	FULL
  } g_cpucache_up;

  /*
   * used by boot code to determine if it can use slab based allocator
   */
  int slab_is_available(void)
  {
  	return g_cpucache_up == FULL;
  }

  static DEFINE_PER_CPU(struct delayed_work, reap_work);

  static inline struct array_cache *cpu_cache_get(struct kmem_cache *cachep)

  {
  	return cachep->array[smp_processor_id()];
  }

  static inline struct kmem_cache *__find_general_cachep(size_t size,
  							gfp_t gfpflags)

  {
  	struct cache_sizes *csizep = malloc_sizes;
  
  #if DEBUG
  	/* This happens if someone tries to call

  	 * kmem_cache_create(), or __kmalloc(), before
  	 * the generic caches are initialized.
  	 */

  	BUG_ON(malloc_sizes[INDEX_AC].cs_cachep == NULL);

  #endif

  	if (!size)
  		return ZERO_SIZE_PTR;

  	while (size > csizep->cs_size)
  		csizep++;
  
  	/*

  	 * Really subtle: The last entry with cs->cs_size==ULONG_MAX

  	 * has cs_{dma,}cachep==NULL. Thus no special case
  	 * for large kmalloc calls required.
  	 */

  #ifdef CONFIG_ZONE_DMA

  	if (unlikely(gfpflags & GFP_DMA))
  		return csizep->cs_dmacachep;

  #endif

  	return csizep->cs_cachep;
  }

  static struct kmem_cache *kmem_find_general_cachep(size_t size, gfp_t gfpflags)

  {
  	return __find_general_cachep(size, gfpflags);
  }

  static size_t slab_mgmt_size(size_t nr_objs, size_t align)

  {

  	return ALIGN(sizeof(struct slab)+nr_objs*sizeof(kmem_bufctl_t), align);
  }

  /*
   * Calculate the number of objects and left-over bytes for a given buffer size.
   */

  static void cache_estimate(unsigned long gfporder, size_t buffer_size,
  			   size_t align, int flags, size_t *left_over,
  			   unsigned int *num)
  {
  	int nr_objs;
  	size_t mgmt_size;
  	size_t slab_size = PAGE_SIZE << gfporder;

  	/*
  	 * The slab management structure can be either off the slab or
  	 * on it. For the latter case, the memory allocated for a
  	 * slab is used for:
  	 *
  	 * - The struct slab
  	 * - One kmem_bufctl_t for each object
  	 * - Padding to respect alignment of @align
  	 * - @buffer_size bytes for each object
  	 *
  	 * If the slab management structure is off the slab, then the
  	 * alignment will already be calculated into the size. Because
  	 * the slabs are all pages aligned, the objects will be at the
  	 * correct alignment when allocated.
  	 */
  	if (flags & CFLGS_OFF_SLAB) {
  		mgmt_size = 0;
  		nr_objs = slab_size / buffer_size;
  
  		if (nr_objs > SLAB_LIMIT)
  			nr_objs = SLAB_LIMIT;
  	} else {
  		/*
  		 * Ignore padding for the initial guess. The padding
  		 * is at most @align-1 bytes, and @buffer_size is at
  		 * least @align. In the worst case, this result will
  		 * be one greater than the number of objects that fit
  		 * into the memory allocation when taking the padding
  		 * into account.
  		 */
  		nr_objs = (slab_size - sizeof(struct slab)) /
  			  (buffer_size + sizeof(kmem_bufctl_t));
  
  		/*
  		 * This calculated number will be either the right
  		 * amount, or one greater than what we want.
  		 */
  		if (slab_mgmt_size(nr_objs, align) + nr_objs*buffer_size
  		       > slab_size)
  			nr_objs--;
  
  		if (nr_objs > SLAB_LIMIT)
  			nr_objs = SLAB_LIMIT;
  
  		mgmt_size = slab_mgmt_size(nr_objs, align);
  	}
  	*num = nr_objs;
  	*left_over = slab_size - nr_objs*buffer_size - mgmt_size;

  }

  #define slab_error(cachep, msg) __slab_error(__func__, cachep, msg)

  static void __slab_error(const char *function, struct kmem_cache *cachep,
  			char *msg)

  {
  	printk(KERN_ERR "slab error in %s(): cache `%s': %s
  ",

  	       function, cachep->name, msg);

  	dump_stack();
  }

  /*
   * By default on NUMA we use alien caches to stage the freeing of
   * objects allocated from other nodes. This causes massive memory
   * inefficiencies when using fake NUMA setup to split memory into a
   * large number of small nodes, so it can be disabled on the command
   * line
    */
  
  static int use_alien_caches __read_mostly = 1;

  static int numa_platform __read_mostly = 1;

  static int __init noaliencache_setup(char *s)
  {
  	use_alien_caches = 0;
  	return 1;
  }
  __setup("noaliencache", noaliencache_setup);

  #ifdef CONFIG_NUMA
  /*
   * Special reaping functions for NUMA systems called from cache_reap().
   * These take care of doing round robin flushing of alien caches (containing
   * objects freed on different nodes from which they were allocated) and the
   * flushing of remote pcps by calling drain_node_pages.
   */
  static DEFINE_PER_CPU(unsigned long, reap_node);
  
  static void init_reap_node(int cpu)
  {
  	int node;
  
  	node = next_node(cpu_to_node(cpu), node_online_map);
  	if (node == MAX_NUMNODES)

  		node = first_node(node_online_map);

  	per_cpu(reap_node, cpu) = node;

  }
  
  static void next_reap_node(void)
  {
  	int node = __get_cpu_var(reap_node);

  	node = next_node(node, node_online_map);
  	if (unlikely(node >= MAX_NUMNODES))
  		node = first_node(node_online_map);
  	__get_cpu_var(reap_node) = node;
  }
  
  #else
  #define init_reap_node(cpu) do { } while (0)
  #define next_reap_node(void) do { } while (0)
  #endif

  /*
   * Initiate the reap timer running on the target CPU.  We run at around 1 to 2Hz
   * via the workqueue/eventd.
   * Add the CPU number into the expiration time to minimize the possibility of
   * the CPUs getting into lockstep and contending for the global cache chain
   * lock.
   */

  static void __cpuinit start_cpu_timer(int cpu)

  {

  	struct delayed_work *reap_work = &per_cpu(reap_work, cpu);

  
  	/*
  	 * When this gets called from do_initcalls via cpucache_init(),
  	 * init_workqueues() has already run, so keventd will be setup
  	 * at that time.
  	 */

  	if (keventd_up() && reap_work->work.func == NULL) {

  		init_reap_node(cpu);

  		INIT_DELAYED_WORK(reap_work, cache_reap);

  		schedule_delayed_work_on(cpu, reap_work,
  					__round_jiffies_relative(HZ, cpu));

  	}
  }

  static struct array_cache *alloc_arraycache(int node, int entries,

  					    int batchcount)

  {

  	int memsize = sizeof(void *) * entries + sizeof(struct array_cache);

  	struct array_cache *nc = NULL;

  	nc = kmalloc_node(memsize, GFP_KERNEL, node);

  	if (nc) {
  		nc->avail = 0;
  		nc->limit = entries;
  		nc->batchcount = batchcount;
  		nc->touched = 0;

  		spin_lock_init(&nc->lock);

  	}
  	return nc;
  }

  /*
   * Transfer objects in one arraycache to another.
   * Locking must be handled by the caller.
   *
   * Return the number of entries transferred.
   */
  static int transfer_objects(struct array_cache *to,
  		struct array_cache *from, unsigned int max)
  {
  	/* Figure out how many entries to transfer */
  	int nr = min(min(from->avail, max), to->limit - to->avail);
  
  	if (!nr)
  		return 0;
  
  	memcpy(to->entry + to->avail, from->entry + from->avail -nr,
  			sizeof(void *) *nr);
  
  	from->avail -= nr;
  	to->avail += nr;
  	to->touched = 1;
  	return nr;
  }

  #ifndef CONFIG_NUMA
  
  #define drain_alien_cache(cachep, alien) do { } while (0)
  #define reap_alien(cachep, l3) do { } while (0)
  
  static inline struct array_cache **alloc_alien_cache(int node, int limit)
  {
  	return (struct array_cache **)BAD_ALIEN_MAGIC;
  }
  
  static inline void free_alien_cache(struct array_cache **ac_ptr)
  {
  }
  
  static inline int cache_free_alien(struct kmem_cache *cachep, void *objp)
  {
  	return 0;
  }
  
  static inline void *alternate_node_alloc(struct kmem_cache *cachep,
  		gfp_t flags)
  {
  	return NULL;
  }

  static inline void *____cache_alloc_node(struct kmem_cache *cachep,

  		 gfp_t flags, int nodeid)
  {
  	return NULL;
  }
  
  #else	/* CONFIG_NUMA */

  static void *____cache_alloc_node(struct kmem_cache *, gfp_t, int);

  static void *alternate_node_alloc(struct kmem_cache *, gfp_t);

  static struct array_cache **alloc_alien_cache(int node, int limit)

  {
  	struct array_cache **ac_ptr;

  	int memsize = sizeof(void *) * nr_node_ids;

  	int i;
  
  	if (limit > 1)
  		limit = 12;
  	ac_ptr = kmalloc_node(memsize, GFP_KERNEL, node);
  	if (ac_ptr) {
  		for_each_node(i) {
  			if (i == node || !node_online(i)) {
  				ac_ptr[i] = NULL;
  				continue;
  			}
  			ac_ptr[i] = alloc_arraycache(node, limit, 0xbaadf00d);
  			if (!ac_ptr[i]) {

  				for (i--; i >= 0; i--)

  					kfree(ac_ptr[i]);
  				kfree(ac_ptr);
  				return NULL;
  			}
  		}
  	}
  	return ac_ptr;
  }

  static void free_alien_cache(struct array_cache **ac_ptr)

  {
  	int i;
  
  	if (!ac_ptr)
  		return;

  	for_each_node(i)

  	    kfree(ac_ptr[i]);

  	kfree(ac_ptr);
  }

  static void __drain_alien_cache(struct kmem_cache *cachep,

  				struct array_cache *ac, int node)

  {
  	struct kmem_list3 *rl3 = cachep->nodelists[node];
  
  	if (ac->avail) {
  		spin_lock(&rl3->list_lock);

  		/*
  		 * Stuff objects into the remote nodes shared array first.
  		 * That way we could avoid the overhead of putting the objects
  		 * into the free lists and getting them back later.
  		 */

  		if (rl3->shared)
  			transfer_objects(rl3->shared, ac, ac->limit);

  		free_block(cachep, ac->entry, ac->avail, node);

  		ac->avail = 0;
  		spin_unlock(&rl3->list_lock);
  	}
  }

  /*
   * Called from cache_reap() to regularly drain alien caches round robin.
   */
  static void reap_alien(struct kmem_cache *cachep, struct kmem_list3 *l3)
  {
  	int node = __get_cpu_var(reap_node);
  
  	if (l3->alien) {
  		struct array_cache *ac = l3->alien[node];

  
  		if (ac && ac->avail && spin_trylock_irq(&ac->lock)) {

  			__drain_alien_cache(cachep, ac, node);
  			spin_unlock_irq(&ac->lock);
  		}
  	}
  }

  static void drain_alien_cache(struct kmem_cache *cachep,
  				struct array_cache **alien)

  {

  	int i = 0;

  	struct array_cache *ac;
  	unsigned long flags;
  
  	for_each_online_node(i) {

  		ac = alien[i];

  		if (ac) {
  			spin_lock_irqsave(&ac->lock, flags);
  			__drain_alien_cache(cachep, ac, i);
  			spin_unlock_irqrestore(&ac->lock, flags);
  		}
  	}
  }

  static inline int cache_free_alien(struct kmem_cache *cachep, void *objp)

  {
  	struct slab *slabp = virt_to_slab(objp);
  	int nodeid = slabp->nodeid;
  	struct kmem_list3 *l3;
  	struct array_cache *alien = NULL;

  	int node;
  
  	node = numa_node_id();

  
  	/*
  	 * Make sure we are not freeing a object from another node to the array
  	 * cache on this cpu.
  	 */

  	if (likely(slabp->nodeid == node))

  		return 0;

  	l3 = cachep->nodelists[node];

  	STATS_INC_NODEFREES(cachep);
  	if (l3->alien && l3->alien[nodeid]) {
  		alien = l3->alien[nodeid];

  		spin_lock(&alien->lock);

  		if (unlikely(alien->avail == alien->limit)) {
  			STATS_INC_ACOVERFLOW(cachep);
  			__drain_alien_cache(cachep, alien, nodeid);
  		}
  		alien->entry[alien->avail++] = objp;
  		spin_unlock(&alien->lock);
  	} else {
  		spin_lock(&(cachep->nodelists[nodeid])->list_lock);
  		free_block(cachep, &objp, 1, nodeid);
  		spin_unlock(&(cachep->nodelists[nodeid])->list_lock);
  	}
  	return 1;
  }

  #endif

  static void __cpuinit cpuup_canceled(long cpu)
  {
  	struct kmem_cache *cachep;
  	struct kmem_list3 *l3 = NULL;
  	int node = cpu_to_node(cpu);

  	node_to_cpumask_ptr(mask, node);

  
  	list_for_each_entry(cachep, &cache_chain, next) {
  		struct array_cache *nc;
  		struct array_cache *shared;
  		struct array_cache **alien;

  		/* cpu is dead; no one can alloc from it. */
  		nc = cachep->array[cpu];
  		cachep->array[cpu] = NULL;
  		l3 = cachep->nodelists[node];
  
  		if (!l3)
  			goto free_array_cache;
  
  		spin_lock_irq(&l3->list_lock);
  
  		/* Free limit for this kmem_list3 */
  		l3->free_limit -= cachep->batchcount;
  		if (nc)
  			free_block(cachep, nc->entry, nc->avail, node);

  		if (!cpus_empty(*mask)) {

  			spin_unlock_irq(&l3->list_lock);
  			goto free_array_cache;
  		}
  
  		shared = l3->shared;
  		if (shared) {
  			free_block(cachep, shared->entry,
  				   shared->avail, node);
  			l3->shared = NULL;
  		}
  
  		alien = l3->alien;
  		l3->alien = NULL;
  
  		spin_unlock_irq(&l3->list_lock);
  
  		kfree(shared);
  		if (alien) {
  			drain_alien_cache(cachep, alien);
  			free_alien_cache(alien);
  		}
  free_array_cache:
  		kfree(nc);
  	}
  	/*
  	 * In the previous loop, all the objects were freed to
  	 * the respective cache's slabs,  now we can go ahead and
  	 * shrink each nodelist to its limit.
  	 */
  	list_for_each_entry(cachep, &cache_chain, next) {
  		l3 = cachep->nodelists[node];
  		if (!l3)
  			continue;
  		drain_freelist(cachep, l3, l3->free_objects);
  	}
  }
  
  static int __cpuinit cpuup_prepare(long cpu)

  {

  	struct kmem_cache *cachep;

  	struct kmem_list3 *l3 = NULL;
  	int node = cpu_to_node(cpu);

  	const int memsize = sizeof(struct kmem_list3);

  	/*
  	 * We need to do this right in the beginning since
  	 * alloc_arraycache's are going to use this list.
  	 * kmalloc_node allows us to add the slab to the right
  	 * kmem_list3 and not this cpu's kmem_list3
  	 */
  
  	list_for_each_entry(cachep, &cache_chain, next) {

  		/*

  		 * Set up the size64 kmemlist for cpu before we can
  		 * begin anything. Make sure some other cpu on this
  		 * node has not already allocated this

  		 */

  		if (!cachep->nodelists[node]) {
  			l3 = kmalloc_node(memsize, GFP_KERNEL, node);
  			if (!l3)
  				goto bad;
  			kmem_list3_init(l3);
  			l3->next_reap = jiffies + REAPTIMEOUT_LIST3 +
  			    ((unsigned long)cachep) % REAPTIMEOUT_LIST3;

  			/*

  			 * The l3s don't come and go as CPUs come and
  			 * go.  cache_chain_mutex is sufficient
  			 * protection here.

  			 */

  			cachep->nodelists[node] = l3;

  		}

  		spin_lock_irq(&cachep->nodelists[node]->list_lock);
  		cachep->nodelists[node]->free_limit =
  			(1 + nr_cpus_node(node)) *
  			cachep->batchcount + cachep->num;
  		spin_unlock_irq(&cachep->nodelists[node]->list_lock);
  	}
  
  	/*
  	 * Now we can go ahead with allocating the shared arrays and
  	 * array caches
  	 */
  	list_for_each_entry(cachep, &cache_chain, next) {
  		struct array_cache *nc;
  		struct array_cache *shared = NULL;
  		struct array_cache **alien = NULL;
  
  		nc = alloc_arraycache(node, cachep->limit,
  					cachep->batchcount);
  		if (!nc)
  			goto bad;
  		if (cachep->shared) {
  			shared = alloc_arraycache(node,
  				cachep->shared * cachep->batchcount,
  				0xbaadf00d);

  			if (!shared) {
  				kfree(nc);

  				goto bad;

  			}

  		}
  		if (use_alien_caches) {
  			alien = alloc_alien_cache(node, cachep->limit);

  			if (!alien) {
  				kfree(shared);
  				kfree(nc);

  				goto bad;

  			}

  		}
  		cachep->array[cpu] = nc;
  		l3 = cachep->nodelists[node];
  		BUG_ON(!l3);
  
  		spin_lock_irq(&l3->list_lock);
  		if (!l3->shared) {
  			/*
  			 * We are serialised from CPU_DEAD or
  			 * CPU_UP_CANCELLED by the cpucontrol lock
  			 */
  			l3->shared = shared;
  			shared = NULL;
  		}

  #ifdef CONFIG_NUMA

  		if (!l3->alien) {
  			l3->alien = alien;
  			alien = NULL;

  		}

  #endif
  		spin_unlock_irq(&l3->list_lock);
  		kfree(shared);
  		free_alien_cache(alien);
  	}
  	return 0;
  bad:

  	cpuup_canceled(cpu);

  	return -ENOMEM;
  }
  
  static int __cpuinit cpuup_callback(struct notifier_block *nfb,
  				    unsigned long action, void *hcpu)
  {
  	long cpu = (long)hcpu;
  	int err = 0;
  
  	switch (action) {

  	case CPU_UP_PREPARE:
  	case CPU_UP_PREPARE_FROZEN:

  		mutex_lock(&cache_chain_mutex);

  		err = cpuup_prepare(cpu);

  		mutex_unlock(&cache_chain_mutex);

  		break;
  	case CPU_ONLINE:

  	case CPU_ONLINE_FROZEN:

  		start_cpu_timer(cpu);
  		break;
  #ifdef CONFIG_HOTPLUG_CPU

    	case CPU_DOWN_PREPARE:

    	case CPU_DOWN_PREPARE_FROZEN:

  		/*
  		 * Shutdown cache reaper. Note that the cache_chain_mutex is
  		 * held so that if cache_reap() is invoked it cannot do
  		 * anything expensive but will only modify reap_work
  		 * and reschedule the timer.
  		*/
  		cancel_rearming_delayed_work(&per_cpu(reap_work, cpu));
  		/* Now the cache_reaper is guaranteed to be not running. */
  		per_cpu(reap_work, cpu).work.func = NULL;
    		break;
    	case CPU_DOWN_FAILED:

    	case CPU_DOWN_FAILED_FROZEN:

  		start_cpu_timer(cpu);
    		break;

  	case CPU_DEAD:

  	case CPU_DEAD_FROZEN:

  		/*
  		 * Even if all the cpus of a node are down, we don't free the
  		 * kmem_list3 of any cache. This to avoid a race between
  		 * cpu_down, and a kmalloc allocation from another cpu for
  		 * memory from the node of the cpu going down.  The list3
  		 * structure is usually allocated from kmem_cache_create() and
  		 * gets destroyed at kmem_cache_destroy().
  		 */

  		/* fall through */

  #endif

  	case CPU_UP_CANCELED:

  	case CPU_UP_CANCELED_FROZEN:

  		mutex_lock(&cache_chain_mutex);

  		cpuup_canceled(cpu);

  		mutex_unlock(&cache_chain_mutex);

  		break;

  	}

  	return err ? NOTIFY_BAD : NOTIFY_OK;

  }

  static struct notifier_block __cpuinitdata cpucache_notifier = {
  	&cpuup_callback, NULL, 0
  };

  /*
   * swap the static kmem_list3 with kmalloced memory
   */

  static void init_list(struct kmem_cache *cachep, struct kmem_list3 *list,
  			int nodeid)

  {
  	struct kmem_list3 *ptr;

  	ptr = kmalloc_node(sizeof(struct kmem_list3), GFP_KERNEL, nodeid);
  	BUG_ON(!ptr);
  
  	local_irq_disable();
  	memcpy(ptr, list, sizeof(struct kmem_list3));

  	/*
  	 * Do not assume that spinlocks can be initialized via memcpy:
  	 */
  	spin_lock_init(&ptr->list_lock);

  	MAKE_ALL_LISTS(cachep, ptr, nodeid);
  	cachep->nodelists[nodeid] = ptr;
  	local_irq_enable();
  }

  /*

   * For setting up all the kmem_list3s for cache whose buffer_size is same as
   * size of kmem_list3.
   */
  static void __init set_up_list3s(struct kmem_cache *cachep, int index)
  {
  	int node;
  
  	for_each_online_node(node) {
  		cachep->nodelists[node] = &initkmem_list3[index + node];
  		cachep->nodelists[node]->next_reap = jiffies +
  		    REAPTIMEOUT_LIST3 +
  		    ((unsigned long)cachep) % REAPTIMEOUT_LIST3;
  	}
  }
  
  /*

   * Initialisation.  Called after the page allocator have been initialised and
   * before smp_init().

   */
  void __init kmem_cache_init(void)
  {
  	size_t left_over;
  	struct cache_sizes *sizes;
  	struct cache_names *names;

  	int i;

  	int order;

  	int node;

  	if (num_possible_nodes() == 1) {

  		use_alien_caches = 0;

  		numa_platform = 0;
  	}

  	for (i = 0; i < NUM_INIT_LISTS; i++) {
  		kmem_list3_init(&initkmem_list3[i]);
  		if (i < MAX_NUMNODES)
  			cache_cache.nodelists[i] = NULL;
  	}

  	set_up_list3s(&cache_cache, CACHE_CACHE);

  
  	/*
  	 * Fragmentation resistance on low memory - only use bigger
  	 * page orders on machines with more than 32MB of memory.
  	 */
  	if (num_physpages > (32 << 20) >> PAGE_SHIFT)
  		slab_break_gfp_order = BREAK_GFP_ORDER_HI;

  	/* Bootstrap is tricky, because several objects are allocated
  	 * from caches that do not exist yet:

  	 * 1) initialize the cache_cache cache: it contains the struct
  	 *    kmem_cache structures of all caches, except cache_cache itself:
  	 *    cache_cache is statically allocated.

  	 *    Initially an __init data area is used for the head array and the
  	 *    kmem_list3 structures, it's replaced with a kmalloc allocated
  	 *    array at the end of the bootstrap.

  	 * 2) Create the first kmalloc cache.

  	 *    The struct kmem_cache for the new cache is allocated normally.

  	 *    An __init data area is used for the head array.
  	 * 3) Create the remaining kmalloc caches, with minimally sized
  	 *    head arrays.

  	 * 4) Replace the __init data head arrays for cache_cache and the first
  	 *    kmalloc cache with kmalloc allocated arrays.

  	 * 5) Replace the __init data for kmem_list3 for cache_cache and
  	 *    the other cache's with kmalloc allocated memory.
  	 * 6) Resize the head arrays of the kmalloc caches to their final sizes.

  	 */

  	node = numa_node_id();

  	/* 1) create the cache_cache */

  	INIT_LIST_HEAD(&cache_chain);
  	list_add(&cache_cache.next, &cache_chain);
  	cache_cache.colour_off = cache_line_size();
  	cache_cache.array[smp_processor_id()] = &initarray_cache.cache;

  	cache_cache.nodelists[node] = &initkmem_list3[CACHE_CACHE + node];

  	/*
  	 * struct kmem_cache size depends on nr_node_ids, which
  	 * can be less than MAX_NUMNODES.
  	 */
  	cache_cache.buffer_size = offsetof(struct kmem_cache, nodelists) +
  				 nr_node_ids * sizeof(struct kmem_list3 *);
  #if DEBUG
  	cache_cache.obj_size = cache_cache.buffer_size;
  #endif

  	cache_cache.buffer_size = ALIGN(cache_cache.buffer_size,
  					cache_line_size());

  	cache_cache.reciprocal_buffer_size =
  		reciprocal_value(cache_cache.buffer_size);

  	for (order = 0; order < MAX_ORDER; order++) {
  		cache_estimate(order, cache_cache.buffer_size,
  			cache_line_size(), 0, &left_over, &cache_cache.num);
  		if (cache_cache.num)
  			break;
  	}

  	BUG_ON(!cache_cache.num);

  	cache_cache.gfporder = order;

  	cache_cache.colour = left_over / cache_cache.colour_off;

  	cache_cache.slab_size = ALIGN(cache_cache.num * sizeof(kmem_bufctl_t) +
  				      sizeof(struct slab), cache_line_size());

  
  	/* 2+3) create the kmalloc caches */
  	sizes = malloc_sizes;
  	names = cache_names;

  	/*
  	 * Initialize the caches that provide memory for the array cache and the
  	 * kmem_list3 structures first.  Without this, further allocations will
  	 * bug.

  	 */
  
  	sizes[INDEX_AC].cs_cachep = kmem_cache_create(names[INDEX_AC].name,

  					sizes[INDEX_AC].cs_size,
  					ARCH_KMALLOC_MINALIGN,
  					ARCH_KMALLOC_FLAGS|SLAB_PANIC,

  					NULL);

  	if (INDEX_AC != INDEX_L3) {

  		sizes[INDEX_L3].cs_cachep =

  			kmem_cache_create(names[INDEX_L3].name,
  				sizes[INDEX_L3].cs_size,
  				ARCH_KMALLOC_MINALIGN,
  				ARCH_KMALLOC_FLAGS|SLAB_PANIC,

  				NULL);

  	}

  	slab_early_init = 0;

  	while (sizes->cs_size != ULONG_MAX) {

  		/*
  		 * For performance, all the general caches are L1 aligned.

  		 * This should be particularly beneficial on SMP boxes, as it
  		 * eliminates "false sharing".
  		 * Note for systems short on memory removing the alignment will

  		 * allow tighter packing of the smaller caches.
  		 */

  		if (!sizes->cs_cachep) {

  			sizes->cs_cachep = kmem_cache_create(names->name,

  					sizes->cs_size,
  					ARCH_KMALLOC_MINALIGN,
  					ARCH_KMALLOC_FLAGS|SLAB_PANIC,

  					NULL);

  		}

  #ifdef CONFIG_ZONE_DMA
  		sizes->cs_dmacachep = kmem_cache_create(
  					names->name_dma,

  					sizes->cs_size,
  					ARCH_KMALLOC_MINALIGN,
  					ARCH_KMALLOC_FLAGS|SLAB_CACHE_DMA|
  						SLAB_PANIC,

  					NULL);

  #endif

  		sizes++;
  		names++;
  	}
  	/* 4) Replace the bootstrap head arrays */
  	{

  		struct array_cache *ptr;

  		ptr = kmalloc(sizeof(struct arraycache_init), GFP_KERNEL);

  		local_irq_disable();

  		BUG_ON(cpu_cache_get(&cache_cache) != &initarray_cache.cache);
  		memcpy(ptr, cpu_cache_get(&cache_cache),

  		       sizeof(struct arraycache_init));

  		/*
  		 * Do not assume that spinlocks can be initialized via memcpy:
  		 */
  		spin_lock_init(&ptr->lock);

  		cache_cache.array[smp_processor_id()] = ptr;
  		local_irq_enable();

  		ptr = kmalloc(sizeof(struct arraycache_init), GFP_KERNEL);

  		local_irq_disable();

  		BUG_ON(cpu_cache_get(malloc_sizes[INDEX_AC].cs_cachep)

  		       != &initarray_generic.cache);

  		memcpy(ptr, cpu_cache_get(malloc_sizes[INDEX_AC].cs_cachep),

  		       sizeof(struct arraycache_init));

  		/*
  		 * Do not assume that spinlocks can be initialized via memcpy:
  		 */
  		spin_lock_init(&ptr->lock);

  		malloc_sizes[INDEX_AC].cs_cachep->array[smp_processor_id()] =

  		    ptr;

  		local_irq_enable();
  	}

  	/* 5) Replace the bootstrap kmem_list3's */
  	{

  		int nid;

  		for_each_online_node(nid) {

  			init_list(&cache_cache, &initkmem_list3[CACHE_CACHE + nid], nid);

  			init_list(malloc_sizes[INDEX_AC].cs_cachep,

  				  &initkmem_list3[SIZE_AC + nid], nid);

  
  			if (INDEX_AC != INDEX_L3) {
  				init_list(malloc_sizes[INDEX_L3].cs_cachep,

  					  &initkmem_list3[SIZE_L3 + nid], nid);

  			}
  		}
  	}

  	/* 6) resize the head arrays to their final sizes */

  	{

  		struct kmem_cache *cachep;

  		mutex_lock(&cache_chain_mutex);

  		list_for_each_entry(cachep, &cache_chain, next)

  			if (enable_cpucache(cachep))
  				BUG();

  		mutex_unlock(&cache_chain_mutex);

  	}

  	/* Annotate slab for lockdep -- annotate the malloc caches */
  	init_lock_keys();

  	/* Done! */
  	g_cpucache_up = FULL;

  	/*
  	 * Register a cpu startup notifier callback that initializes
  	 * cpu_cache_get for all new cpus

  	 */
  	register_cpu_notifier(&cpucache_notifier);

  	/*
  	 * The reap timers are started later, with a module init call: That part
  	 * of the kernel is not yet operational.

  	 */
  }
  
  static int __init cpucache_init(void)
  {
  	int cpu;

  	/*
  	 * Register the timers that return unneeded pages to the page allocator

  	 */

  	for_each_online_cpu(cpu)

  		start_cpu_timer(cpu);

  	return 0;
  }

  __initcall(cpucache_init);
  
  /*
   * Interface to system's page allocator. No need to hold the cache-lock.
   *
   * If we requested dmaable memory, we will get it. Even if we
   * did not request dmaable memory, we might get it, but that
   * would be relatively rare and ignorable.
   */

  static void *kmem_getpages(struct kmem_cache *cachep, gfp_t flags, int nodeid)

  {
  	struct page *page;

  	int nr_pages;

  	int i;

  #ifndef CONFIG_MMU

  	/*
  	 * Nommu uses slab's for process anonymous memory allocations, and thus
  	 * requires __GFP_COMP to properly refcount higher order allocations

  	 */

  	flags |= __GFP_COMP;

  #endif

  	flags |= cachep->gfpflags;

  	if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
  		flags |= __GFP_RECLAIMABLE;

  
  	page = alloc_pages_node(nodeid, flags, cachep->gfporder);

  	if (!page)
  		return NULL;

  	nr_pages = (1 << cachep->gfporder);

  	if (cachep->flags & SLAB_RECLAIM_ACCOUNT)

  		add_zone_page_state(page_zone(page),
  			NR_SLAB_RECLAIMABLE, nr_pages);
  	else
  		add_zone_page_state(page_zone(page),
  			NR_SLAB_UNRECLAIMABLE, nr_pages);

  	for (i = 0; i < nr_pages; i++)
  		__SetPageSlab(page + i);
  	return page_address(page);

  }
  
  /*
   * Interface to system's page release.
   */

  static void kmem_freepages(struct kmem_cache *cachep, void *addr)

  {

  	unsigned long i = (1 << cachep->gfporder);

  	struct page *page = virt_to_page(addr);
  	const unsigned long nr_freed = i;

  	if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
  		sub_zone_page_state(page_zone(page),
  				NR_SLAB_RECLAIMABLE, nr_freed);
  	else
  		sub_zone_page_state(page_zone(page),
  				NR_SLAB_UNRECLAIMABLE, nr_freed);

  	while (i--) {

  		BUG_ON(!PageSlab(page));
  		__ClearPageSlab(page);

  		page++;
  	}

  	if (current->reclaim_state)
  		current->reclaim_state->reclaimed_slab += nr_freed;
  	free_pages((unsigned long)addr, cachep->gfporder);

  }
  
  static void kmem_rcu_free(struct rcu_head *head)
  {

  	struct slab_rcu *slab_rcu = (struct slab_rcu *)head;

  	struct kmem_cache *cachep = slab_rcu->cachep;

  
  	kmem_freepages(cachep, slab_rcu->addr);
  	if (OFF_SLAB(cachep))
  		kmem_cache_free(cachep->slabp_cache, slab_rcu);
  }
  
  #if DEBUG
  
  #ifdef CONFIG_DEBUG_PAGEALLOC

  static void store_stackinfo(struct kmem_cache *cachep, unsigned long *addr,

  			    unsigned long caller)

  {

  	int size = obj_size(cachep);

  	addr = (unsigned long *)&((char *)addr)[obj_offset(cachep)];

  	if (size < 5 * sizeof(unsigned long))

  		return;

  	*addr++ = 0x12345678;
  	*addr++ = caller;
  	*addr++ = smp_processor_id();
  	size -= 3 * sizeof(unsigned long);

  	{
  		unsigned long *sptr = &caller;
  		unsigned long svalue;
  
  		while (!kstack_end(sptr)) {
  			svalue = *sptr++;
  			if (kernel_text_address(svalue)) {

  				*addr++ = svalue;

  				size -= sizeof(unsigned long);
  				if (size <= sizeof(unsigned long))
  					break;
  			}
  		}
  
  	}

  	*addr++ = 0x87654321;

  }
  #endif

  static void poison_obj(struct kmem_cache *cachep, void *addr, unsigned char val)

  {

  	int size = obj_size(cachep);
  	addr = &((char *)addr)[obj_offset(cachep)];

  
  	memset(addr, val, size);

  	*(unsigned char *)(addr + size - 1) = POISON_END;

  }
  
  static void dump_line(char *data, int offset, int limit)
  {
  	int i;

  	unsigned char error = 0;
  	int bad_count = 0;

  	printk(KERN_ERR "%03x:", offset);

  	for (i = 0; i < limit; i++) {
  		if (data[offset + i] != POISON_FREE) {
  			error = data[offset + i];
  			bad_count++;
  		}

  		printk(" %02x", (unsigned char)data[offset + i]);

  	}

  	printk("
  ");

  
  	if (bad_count == 1) {
  		error ^= POISON_FREE;
  		if (!(error & (error - 1))) {
  			printk(KERN_ERR "Single bit error detected. Probably "
  					"bad RAM.
  ");
  #ifdef CONFIG_X86
  			printk(KERN_ERR "Run memtest86+ or a similar memory "
  					"test tool.
  ");
  #else
  			printk(KERN_ERR "Run a memory test tool.
  ");
  #endif
  		}
  	}

  }
  #endif
  
  #if DEBUG

  static void print_objinfo(struct kmem_cache *cachep, void *objp, int lines)

  {
  	int i, size;
  	char *realobj;
  
  	if (cachep->flags & SLAB_RED_ZONE) {

  		printk(KERN_ERR "Redzone: 0x%llx/0x%llx.
  ",

  			*dbg_redzone1(cachep, objp),
  			*dbg_redzone2(cachep, objp));

  	}
  
  	if (cachep->flags & SLAB_STORE_USER) {
  		printk(KERN_ERR "Last user: [<%p>]",

  			*dbg_userword(cachep, objp));

  		print_symbol("(%s)",

  				(unsigned long)*dbg_userword(cachep, objp));

  		printk("
  ");
  	}

  	realobj = (char *)objp + obj_offset(cachep);
  	size = obj_size(cachep);

  	for (i = 0; i < size && lines; i += 16, lines--) {

  		int limit;
  		limit = 16;

  		if (i + limit > size)
  			limit = size - i;

  		dump_line(realobj, i, limit);
  	}
  }

  static void check_poison_obj(struct kmem_cache *cachep, void *objp)

  {
  	char *realobj;
  	int size, i;
  	int lines = 0;

  	realobj = (char *)objp + obj_offset(cachep);
  	size = obj_size(cachep);

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

  		char exp = POISON_FREE;

  		if (i == size - 1)

  			exp = POISON_END;
  		if (realobj[i] != exp) {
  			int limit;
  			/* Mismatch ! */
  			/* Print header */
  			if (lines == 0) {

  				printk(KERN_ERR

  					"Slab corruption: %s start=%p, len=%d
  ",
  					cachep->name, realobj, size);

  				print_objinfo(cachep, objp, 0);
  			}
  			/* Hexdump the affected line */

  			i = (i / 16) * 16;

  			limit = 16;

  			if (i + limit > size)
  				limit = size - i;

  			dump_line(realobj, i, limit);
  			i += 16;
  			lines++;
  			/* Limit to 5 lines */
  			if (lines > 5)
  				break;
  		}
  	}
  	if (lines != 0) {
  		/* Print some data about the neighboring objects, if they
  		 * exist:
  		 */

  		struct slab *slabp = virt_to_slab(objp);

  		unsigned int objnr;

  		objnr = obj_to_index(cachep, slabp, objp);

  		if (objnr) {

  			objp = index_to_obj(cachep, slabp, objnr - 1);

  			realobj = (char *)objp + obj_offset(cachep);

  			printk(KERN_ERR "Prev obj: start=%p, len=%d
  ",

  			       realobj, size);

  			print_objinfo(cachep, objp, 2);
  		}

  		if (objnr + 1 < cachep->num) {