/*
   * SLUB: A slab allocator that limits cache line use instead of queuing
   * objects in per cpu and per node lists.
   *

   * The allocator synchronizes using per slab locks or atomic operatios
   * and only uses a centralized lock to manage a pool of partial slabs.

   *

   * (C) 2007 SGI, Christoph Lameter

   * (C) 2011 Linux Foundation, Christoph Lameter

   */
  
  #include <linux/mm.h>

  #include <linux/swap.h> /* struct reclaim_state */

  #include <linux/module.h>
  #include <linux/bit_spinlock.h>
  #include <linux/interrupt.h>
  #include <linux/bitops.h>
  #include <linux/slab.h>

  #include <linux/proc_fs.h>

  #include <linux/seq_file.h>

  #include <linux/kmemcheck.h>

  #include <linux/cpu.h>
  #include <linux/cpuset.h>
  #include <linux/mempolicy.h>
  #include <linux/ctype.h>

  #include <linux/debugobjects.h>

  #include <linux/kallsyms.h>

  #include <linux/memory.h>

  #include <linux/math64.h>

  #include <linux/fault-inject.h>

  #include <linux/stacktrace.h>

  #include <trace/events/kmem.h>

  /*
   * Lock order:

   *   1. slub_lock (Global Semaphore)
   *   2. node->list_lock
   *   3. slab_lock(page) (Only on some arches and for debugging)

   *

   *   slub_lock
   *
   *   The role of the slub_lock is to protect the list of all the slabs
   *   and to synchronize major metadata changes to slab cache structures.
   *
   *   The slab_lock is only used for debugging and on arches that do not
   *   have the ability to do a cmpxchg_double. It only protects the second
   *   double word in the page struct. Meaning
   *	A. page->freelist	-> List of object free in a page
   *	B. page->counters	-> Counters of objects
   *	C. page->frozen		-> frozen state
   *
   *   If a slab is frozen then it is exempt from list management. It is not
   *   on any list. The processor that froze the slab is the one who can
   *   perform list operations on the page. Other processors may put objects
   *   onto the freelist but the processor that froze the slab is the only
   *   one that can retrieve the objects from the page's freelist.

   *
   *   The list_lock protects the partial and full list on each node and
   *   the partial slab counter. If taken then no new slabs may be added or
   *   removed from the lists nor make the number of partial slabs be modified.
   *   (Note that the total number of slabs is an atomic value that may be
   *   modified without taking the list lock).
   *
   *   The list_lock is a centralized lock and thus we avoid taking it as
   *   much as possible. As long as SLUB does not have to handle partial
   *   slabs, operations can continue without any centralized lock. F.e.
   *   allocating a long series of objects that fill up slabs does not require
   *   the list lock.

   *   Interrupts are disabled during allocation and deallocation in order to
   *   make the slab allocator safe to use in the context of an irq. In addition
   *   interrupts are disabled to ensure that the processor does not change
   *   while handling per_cpu slabs, due to kernel preemption.
   *
   * SLUB assigns one slab for allocation to each processor.
   * Allocations only occur from these slabs called cpu slabs.
   *

   * Slabs with free elements are kept on a partial list and during regular
   * operations no list for full slabs is used. If an object in a full slab is

   * freed then the slab will show up again on the partial lists.

   * We track full slabs for debugging purposes though because otherwise we
   * cannot scan all objects.

   *
   * Slabs are freed when they become empty. Teardown and setup is
   * minimal so we rely on the page allocators per cpu caches for
   * fast frees and allocs.
   *
   * Overloading of page flags that are otherwise used for LRU management.
   *

   * PageActive 		The slab is frozen and exempt from list processing.
   * 			This means that the slab is dedicated to a purpose
   * 			such as satisfying allocations for a specific
   * 			processor. Objects may be freed in the slab while
   * 			it is frozen but slab_free will then skip the usual
   * 			list operations. It is up to the processor holding
   * 			the slab to integrate the slab into the slab lists
   * 			when the slab is no longer needed.
   *
   * 			One use of this flag is to mark slabs that are
   * 			used for allocations. Then such a slab becomes a cpu
   * 			slab. The cpu slab may be equipped with an additional

   * 			freelist that allows lockless access to

   * 			free objects in addition to the regular freelist
   * 			that requires the slab lock.

   *
   * PageError		Slab requires special handling due to debug
   * 			options set. This moves	slab handling out of

   * 			the fast path and disables lockless freelists.

   */

  #define SLAB_DEBUG_FLAGS (SLAB_RED_ZONE | SLAB_POISON | SLAB_STORE_USER | \
  		SLAB_TRACE | SLAB_DEBUG_FREE)
  
  static inline int kmem_cache_debug(struct kmem_cache *s)
  {

  #ifdef CONFIG_SLUB_DEBUG

  	return unlikely(s->flags & SLAB_DEBUG_FLAGS);

  #else

  	return 0;

  #endif

  }

  /*
   * Issues still to be resolved:
   *

   * - Support PAGE_ALLOC_DEBUG. Should be easy to do.
   *

   * - Variable sizing of the per node arrays
   */
  
  /* Enable to test recovery from slab corruption on boot */
  #undef SLUB_RESILIENCY_TEST

  /* Enable to log cmpxchg failures */
  #undef SLUB_DEBUG_CMPXCHG

  /*

   * Mininum number of partial slabs. These will be left on the partial
   * lists even if they are empty. kmem_cache_shrink may reclaim them.
   */

  #define MIN_PARTIAL 5

  /*
   * Maximum number of desirable partial slabs.
   * The existence of more partial slabs makes kmem_cache_shrink
   * sort the partial list by the number of objects in the.
   */
  #define MAX_PARTIAL 10

  #define DEBUG_DEFAULT_FLAGS (SLAB_DEBUG_FREE | SLAB_RED_ZONE | \
  				SLAB_POISON | SLAB_STORE_USER)

  /*

   * Debugging flags that require metadata to be stored in the slab.  These get
   * disabled when slub_debug=O is used and a cache's min order increases with
   * metadata.

   */

  #define DEBUG_METADATA_FLAGS (SLAB_RED_ZONE | SLAB_POISON | SLAB_STORE_USER)

  
  /*

   * Set of flags that will prevent slab merging
   */
  #define SLUB_NEVER_MERGE (SLAB_RED_ZONE | SLAB_POISON | SLAB_STORE_USER | \

  		SLAB_TRACE | SLAB_DESTROY_BY_RCU | SLAB_NOLEAKTRACE | \
  		SLAB_FAILSLAB)

  
  #define SLUB_MERGE_SAME (SLAB_DEBUG_FREE | SLAB_RECLAIM_ACCOUNT | \

  		SLAB_CACHE_DMA | SLAB_NOTRACK)

  #define OO_SHIFT	16
  #define OO_MASK		((1 << OO_SHIFT) - 1)

  #define MAX_OBJS_PER_PAGE	32767 /* since page.objects is u15 */

  /* Internal SLUB flags */

  #define __OBJECT_POISON		0x80000000UL /* Poison object */

  #define __CMPXCHG_DOUBLE	0x40000000UL /* Use cmpxchg_double */

  
  static int kmem_size = sizeof(struct kmem_cache);
  
  #ifdef CONFIG_SMP
  static struct notifier_block slab_notifier;
  #endif
  
  static enum {
  	DOWN,		/* No slab functionality available */

  	PARTIAL,	/* Kmem_cache_node works */

  	UP,		/* Everything works but does not show up in sysfs */

  	SYSFS		/* Sysfs up */
  } slab_state = DOWN;
  
  /* A list of all slab caches on the system */
  static DECLARE_RWSEM(slub_lock);

  static LIST_HEAD(slab_caches);

  /*
   * Tracking user of a slab.
   */

  #define TRACK_ADDRS_COUNT 16

  struct track {

  	unsigned long addr;	/* Called from address */

  #ifdef CONFIG_STACKTRACE
  	unsigned long addrs[TRACK_ADDRS_COUNT];	/* Called from address */
  #endif

  	int cpu;		/* Was running on cpu */
  	int pid;		/* Pid context */
  	unsigned long when;	/* When did the operation occur */
  };
  
  enum track_item { TRACK_ALLOC, TRACK_FREE };

  #ifdef CONFIG_SYSFS

  static int sysfs_slab_add(struct kmem_cache *);
  static int sysfs_slab_alias(struct kmem_cache *, const char *);
  static void sysfs_slab_remove(struct kmem_cache *);

  #else

  static inline int sysfs_slab_add(struct kmem_cache *s) { return 0; }
  static inline int sysfs_slab_alias(struct kmem_cache *s, const char *p)
  							{ return 0; }

  static inline void sysfs_slab_remove(struct kmem_cache *s)
  {

  	kfree(s->name);

  	kfree(s);
  }

  #endif

  static inline void stat(const struct kmem_cache *s, enum stat_item si)

  {
  #ifdef CONFIG_SLUB_STATS

  	__this_cpu_inc(s->cpu_slab->stat[si]);

  #endif
  }

  /********************************************************************
   * 			Core slab cache functions
   *******************************************************************/
  
  int slab_is_available(void)
  {
  	return slab_state >= UP;
  }
  
  static inline struct kmem_cache_node *get_node(struct kmem_cache *s, int node)
  {

  	return s->node[node];

  }

  /* Verify that a pointer has an address that is valid within a slab page */

  static inline int check_valid_pointer(struct kmem_cache *s,
  				struct page *page, const void *object)
  {
  	void *base;

  	if (!object)

  		return 1;

  	base = page_address(page);

  	if (object < base || object >= base + page->objects * s->size ||

  		(object - base) % s->size) {
  		return 0;
  	}
  
  	return 1;
  }

  static inline void *get_freepointer(struct kmem_cache *s, void *object)
  {
  	return *(void **)(object + s->offset);
  }

  static inline void *get_freepointer_safe(struct kmem_cache *s, void *object)
  {
  	void *p;
  
  #ifdef CONFIG_DEBUG_PAGEALLOC
  	probe_kernel_read(&p, (void **)(object + s->offset), sizeof(p));
  #else
  	p = get_freepointer(s, object);
  #endif
  	return p;
  }

  static inline void set_freepointer(struct kmem_cache *s, void *object, void *fp)
  {
  	*(void **)(object + s->offset) = fp;
  }
  
  /* Loop over all objects in a slab */

  #define for_each_object(__p, __s, __addr, __objects) \
  	for (__p = (__addr); __p < (__addr) + (__objects) * (__s)->size;\

  			__p += (__s)->size)

  /* Determine object index from a given position */
  static inline int slab_index(void *p, struct kmem_cache *s, void *addr)
  {
  	return (p - addr) / s->size;
  }

  static inline size_t slab_ksize(const struct kmem_cache *s)
  {
  #ifdef CONFIG_SLUB_DEBUG
  	/*
  	 * Debugging requires use of the padding between object
  	 * and whatever may come after it.
  	 */
  	if (s->flags & (SLAB_RED_ZONE | SLAB_POISON))
  		return s->objsize;
  
  #endif
  	/*
  	 * If we have the need to store the freelist pointer
  	 * back there or track user information then we can
  	 * only use the space before that information.
  	 */
  	if (s->flags & (SLAB_DESTROY_BY_RCU | SLAB_STORE_USER))
  		return s->inuse;
  	/*
  	 * Else we can use all the padding etc for the allocation
  	 */
  	return s->size;
  }

  static inline int order_objects(int order, unsigned long size, int reserved)
  {
  	return ((PAGE_SIZE << order) - reserved) / size;
  }

  static inline struct kmem_cache_order_objects oo_make(int order,

  		unsigned long size, int reserved)

  {
  	struct kmem_cache_order_objects x = {

  		(order << OO_SHIFT) + order_objects(order, size, reserved)

  	};
  
  	return x;
  }
  
  static inline int oo_order(struct kmem_cache_order_objects x)
  {

  	return x.x >> OO_SHIFT;

  }
  
  static inline int oo_objects(struct kmem_cache_order_objects x)
  {

  	return x.x & OO_MASK;

  }

  /*
   * Per slab locking using the pagelock
   */
  static __always_inline void slab_lock(struct page *page)
  {
  	bit_spin_lock(PG_locked, &page->flags);
  }
  
  static __always_inline void slab_unlock(struct page *page)
  {
  	__bit_spin_unlock(PG_locked, &page->flags);
  }

  /* Interrupts must be disabled (for the fallback code to work right) */
  static inline bool __cmpxchg_double_slab(struct kmem_cache *s, struct page *page,
  		void *freelist_old, unsigned long counters_old,
  		void *freelist_new, unsigned long counters_new,
  		const char *n)
  {
  	VM_BUG_ON(!irqs_disabled());
  #ifdef CONFIG_CMPXCHG_DOUBLE
  	if (s->flags & __CMPXCHG_DOUBLE) {
  		if (cmpxchg_double(&page->freelist,
  			freelist_old, counters_old,
  			freelist_new, counters_new))
  		return 1;
  	} else
  #endif
  	{
  		slab_lock(page);
  		if (page->freelist == freelist_old && page->counters == counters_old) {
  			page->freelist = freelist_new;
  			page->counters = counters_new;
  			slab_unlock(page);
  			return 1;
  		}
  		slab_unlock(page);
  	}
  
  	cpu_relax();
  	stat(s, CMPXCHG_DOUBLE_FAIL);
  
  #ifdef SLUB_DEBUG_CMPXCHG
  	printk(KERN_INFO "%s %s: cmpxchg double redo ", n, s->name);
  #endif
  
  	return 0;
  }

  static inline bool cmpxchg_double_slab(struct kmem_cache *s, struct page *page,
  		void *freelist_old, unsigned long counters_old,
  		void *freelist_new, unsigned long counters_new,
  		const char *n)
  {
  #ifdef CONFIG_CMPXCHG_DOUBLE
  	if (s->flags & __CMPXCHG_DOUBLE) {
  		if (cmpxchg_double(&page->freelist,
  			freelist_old, counters_old,
  			freelist_new, counters_new))
  		return 1;
  	} else
  #endif
  	{

  		unsigned long flags;
  
  		local_irq_save(flags);

  		slab_lock(page);

  		if (page->freelist == freelist_old && page->counters == counters_old) {
  			page->freelist = freelist_new;
  			page->counters = counters_new;

  			slab_unlock(page);

  			local_irq_restore(flags);

  			return 1;
  		}

  		slab_unlock(page);

  		local_irq_restore(flags);

  	}
  
  	cpu_relax();
  	stat(s, CMPXCHG_DOUBLE_FAIL);
  
  #ifdef SLUB_DEBUG_CMPXCHG
  	printk(KERN_INFO "%s %s: cmpxchg double redo ", n, s->name);
  #endif
  
  	return 0;
  }

  #ifdef CONFIG_SLUB_DEBUG
  /*

   * Determine a map of object in use on a page.
   *

   * Node listlock must be held to guarantee that the page does

   * not vanish from under us.
   */
  static void get_map(struct kmem_cache *s, struct page *page, unsigned long *map)
  {
  	void *p;
  	void *addr = page_address(page);
  
  	for (p = page->freelist; p; p = get_freepointer(s, p))
  		set_bit(slab_index(p, s, addr), map);
  }

  /*
   * Debug settings:
   */

  #ifdef CONFIG_SLUB_DEBUG_ON
  static int slub_debug = DEBUG_DEFAULT_FLAGS;
  #else

  static int slub_debug;

  #endif

  
  static char *slub_debug_slabs;

  static int disable_higher_order_debug;

  /*

   * Object debugging
   */
  static void print_section(char *text, u8 *addr, unsigned int length)
  {
  	int i, offset;
  	int newline = 1;
  	char ascii[17];
  
  	ascii[16] = 0;
  
  	for (i = 0; i < length; i++) {
  		if (newline) {

  			printk(KERN_ERR "%8s 0x%p: ", text, addr + i);

  			newline = 0;
  		}

  		printk(KERN_CONT " %02x", addr[i]);

  		offset = i % 16;
  		ascii[offset] = isgraph(addr[i]) ? addr[i] : '.';
  		if (offset == 15) {

  			printk(KERN_CONT " %s
  ", ascii);

  			newline = 1;
  		}
  	}
  	if (!newline) {
  		i %= 16;
  		while (i < 16) {

  			printk(KERN_CONT "   ");

  			ascii[i] = ' ';
  			i++;
  		}

  		printk(KERN_CONT " %s
  ", ascii);

  	}
  }

  static struct track *get_track(struct kmem_cache *s, void *object,
  	enum track_item alloc)
  {
  	struct track *p;
  
  	if (s->offset)
  		p = object + s->offset + sizeof(void *);
  	else
  		p = object + s->inuse;
  
  	return p + alloc;
  }
  
  static void set_track(struct kmem_cache *s, void *object,

  			enum track_item alloc, unsigned long addr)

  {

  	struct track *p = get_track(s, object, alloc);

  	if (addr) {

  #ifdef CONFIG_STACKTRACE
  		struct stack_trace trace;
  		int i;
  
  		trace.nr_entries = 0;
  		trace.max_entries = TRACK_ADDRS_COUNT;
  		trace.entries = p->addrs;
  		trace.skip = 3;
  		save_stack_trace(&trace);
  
  		/* See rant in lockdep.c */
  		if (trace.nr_entries != 0 &&
  		    trace.entries[trace.nr_entries - 1] == ULONG_MAX)
  			trace.nr_entries--;
  
  		for (i = trace.nr_entries; i < TRACK_ADDRS_COUNT; i++)
  			p->addrs[i] = 0;
  #endif

  		p->addr = addr;
  		p->cpu = smp_processor_id();

  		p->pid = current->pid;

  		p->when = jiffies;
  	} else
  		memset(p, 0, sizeof(struct track));
  }

  static void init_tracking(struct kmem_cache *s, void *object)
  {

  	if (!(s->flags & SLAB_STORE_USER))
  		return;

  	set_track(s, object, TRACK_FREE, 0UL);
  	set_track(s, object, TRACK_ALLOC, 0UL);

  }
  
  static void print_track(const char *s, struct track *t)
  {
  	if (!t->addr)
  		return;

  	printk(KERN_ERR "INFO: %s in %pS age=%lu cpu=%u pid=%d
  ",

  		s, (void *)t->addr, jiffies - t->when, t->cpu, t->pid);

  #ifdef CONFIG_STACKTRACE
  	{
  		int i;
  		for (i = 0; i < TRACK_ADDRS_COUNT; i++)
  			if (t->addrs[i])
  				printk(KERN_ERR "\t%pS
  ", (void *)t->addrs[i]);
  			else
  				break;
  	}
  #endif

  }
  
  static void print_tracking(struct kmem_cache *s, void *object)
  {
  	if (!(s->flags & SLAB_STORE_USER))
  		return;
  
  	print_track("Allocated", get_track(s, object, TRACK_ALLOC));
  	print_track("Freed", get_track(s, object, TRACK_FREE));
  }
  
  static void print_page_info(struct page *page)
  {

  	printk(KERN_ERR "INFO: Slab 0x%p objects=%u used=%u fp=0x%p flags=0x%04lx
  ",
  		page, page->objects, page->inuse, page->freelist, page->flags);

  
  }
  
  static void slab_bug(struct kmem_cache *s, char *fmt, ...)
  {
  	va_list args;
  	char buf[100];
  
  	va_start(args, fmt);
  	vsnprintf(buf, sizeof(buf), fmt, args);
  	va_end(args);
  	printk(KERN_ERR "========================================"
  			"=====================================
  ");
  	printk(KERN_ERR "BUG %s: %s
  ", s->name, buf);
  	printk(KERN_ERR "----------------------------------------"
  			"-------------------------------------
  
  ");

  }

  static void slab_fix(struct kmem_cache *s, char *fmt, ...)
  {
  	va_list args;
  	char buf[100];
  
  	va_start(args, fmt);
  	vsnprintf(buf, sizeof(buf), fmt, args);
  	va_end(args);
  	printk(KERN_ERR "FIX %s: %s
  ", s->name, buf);
  }
  
  static void print_trailer(struct kmem_cache *s, struct page *page, u8 *p)

  {
  	unsigned int off;	/* Offset of last byte */

  	u8 *addr = page_address(page);

  
  	print_tracking(s, p);
  
  	print_page_info(page);
  
  	printk(KERN_ERR "INFO: Object 0x%p @offset=%tu fp=0x%p
  
  ",
  			p, p - addr, get_freepointer(s, p));
  
  	if (p > addr + 16)
  		print_section("Bytes b4", p - 16, 16);

  	print_section("Object", p, min_t(unsigned long, s->objsize, PAGE_SIZE));

  
  	if (s->flags & SLAB_RED_ZONE)
  		print_section("Redzone", p + s->objsize,
  			s->inuse - s->objsize);

  	if (s->offset)
  		off = s->offset + sizeof(void *);
  	else
  		off = s->inuse;

  	if (s->flags & SLAB_STORE_USER)

  		off += 2 * sizeof(struct track);

  
  	if (off != s->size)
  		/* Beginning of the filler is the free pointer */

  		print_section("Padding", p + off, s->size - off);
  
  	dump_stack();

  }
  
  static void object_err(struct kmem_cache *s, struct page *page,
  			u8 *object, char *reason)
  {

  	slab_bug(s, "%s", reason);

  	print_trailer(s, page, object);

  }

  static void slab_err(struct kmem_cache *s, struct page *page, char *fmt, ...)

  {
  	va_list args;
  	char buf[100];

  	va_start(args, fmt);
  	vsnprintf(buf, sizeof(buf), fmt, args);

  	va_end(args);

  	slab_bug(s, "%s", buf);

  	print_page_info(page);

  	dump_stack();
  }

  static void init_object(struct kmem_cache *s, void *object, u8 val)

  {
  	u8 *p = object;
  
  	if (s->flags & __OBJECT_POISON) {
  		memset(p, POISON_FREE, s->objsize - 1);

  		p[s->objsize - 1] = POISON_END;

  	}
  
  	if (s->flags & SLAB_RED_ZONE)

  		memset(p + s->objsize, val, s->inuse - s->objsize);

  }

  static u8 *check_bytes8(u8 *start, u8 value, unsigned int bytes)

  {
  	while (bytes) {

  		if (*start != value)

  			return start;

  		start++;
  		bytes--;
  	}

  	return NULL;
  }

  static u8 *check_bytes(u8 *start, u8 value, unsigned int bytes)
  {
  	u64 value64;
  	unsigned int words, prefix;
  
  	if (bytes <= 16)
  		return check_bytes8(start, value, bytes);
  
  	value64 = value | value << 8 | value << 16 | value << 24;

  	value64 = (value64 & 0xffffffff) | value64 << 32;

  	prefix = 8 - ((unsigned long)start) % 8;
  
  	if (prefix) {
  		u8 *r = check_bytes8(start, value, prefix);
  		if (r)
  			return r;
  		start += prefix;
  		bytes -= prefix;
  	}
  
  	words = bytes / 8;
  
  	while (words) {
  		if (*(u64 *)start != value64)
  			return check_bytes8(start, value, 8);
  		start += 8;
  		words--;
  	}
  
  	return check_bytes8(start, value, bytes % 8);
  }

  static void restore_bytes(struct kmem_cache *s, char *message, u8 data,
  						void *from, void *to)
  {
  	slab_fix(s, "Restoring 0x%p-0x%p=0x%x
  ", from, to - 1, data);
  	memset(from, data, to - from);
  }
  
  static int check_bytes_and_report(struct kmem_cache *s, struct page *page,
  			u8 *object, char *what,

  			u8 *start, unsigned int value, unsigned int bytes)

  {
  	u8 *fault;
  	u8 *end;
  
  	fault = check_bytes(start, value, bytes);
  	if (!fault)
  		return 1;
  
  	end = start + bytes;
  	while (end > fault && end[-1] == value)
  		end--;
  
  	slab_bug(s, "%s overwritten", what);
  	printk(KERN_ERR "INFO: 0x%p-0x%p. First byte 0x%x instead of 0x%x
  ",
  					fault, end - 1, fault[0], value);
  	print_trailer(s, page, object);
  
  	restore_bytes(s, what, value, fault, end);
  	return 0;

  }

  /*
   * Object layout:
   *
   * object address
   * 	Bytes of the object to be managed.
   * 	If the freepointer may overlay the object then the free
   * 	pointer is the first word of the object.

   *

   * 	Poisoning uses 0x6b (POISON_FREE) and the last byte is
   * 	0xa5 (POISON_END)
   *
   * object + s->objsize
   * 	Padding to reach word boundary. This is also used for Redzoning.

   * 	Padding is extended by another word if Redzoning is enabled and
   * 	objsize == inuse.
   *

   * 	We fill with 0xbb (RED_INACTIVE) for inactive objects and with
   * 	0xcc (RED_ACTIVE) for objects in use.
   *
   * object + s->inuse

   * 	Meta data starts here.
   *

   * 	A. Free pointer (if we cannot overwrite object on free)
   * 	B. Tracking data for SLAB_STORE_USER

   * 	C. Padding to reach required alignment boundary or at mininum

   * 		one word if debugging is on to be able to detect writes

   * 		before the word boundary.
   *
   *	Padding is done using 0x5a (POISON_INUSE)

   *
   * object + s->size

   * 	Nothing is used beyond s->size.

   *

   * If slabcaches are merged then the objsize and inuse boundaries are mostly
   * ignored. And therefore no slab options that rely on these boundaries

   * may be used with merged slabcaches.
   */

  static int check_pad_bytes(struct kmem_cache *s, struct page *page, u8 *p)
  {
  	unsigned long off = s->inuse;	/* The end of info */
  
  	if (s->offset)
  		/* Freepointer is placed after the object. */
  		off += sizeof(void *);
  
  	if (s->flags & SLAB_STORE_USER)
  		/* We also have user information there */
  		off += 2 * sizeof(struct track);
  
  	if (s->size == off)
  		return 1;

  	return check_bytes_and_report(s, page, p, "Object padding",
  				p + off, POISON_INUSE, s->size - off);

  }

  /* Check the pad bytes at the end of a slab page */

  static int slab_pad_check(struct kmem_cache *s, struct page *page)
  {

  	u8 *start;
  	u8 *fault;
  	u8 *end;
  	int length;
  	int remainder;

  
  	if (!(s->flags & SLAB_POISON))
  		return 1;

  	start = page_address(page);

  	length = (PAGE_SIZE << compound_order(page)) - s->reserved;

  	end = start + length;
  	remainder = length % s->size;

  	if (!remainder)
  		return 1;

  	fault = check_bytes(end - remainder, POISON_INUSE, remainder);

  	if (!fault)
  		return 1;
  	while (end > fault && end[-1] == POISON_INUSE)
  		end--;
  
  	slab_err(s, page, "Padding overwritten. 0x%p-0x%p", fault, end - 1);

  	print_section("Padding", end - remainder, remainder);

  	restore_bytes(s, "slab padding", POISON_INUSE, end - remainder, end);

  	return 0;

  }
  
  static int check_object(struct kmem_cache *s, struct page *page,

  					void *object, u8 val)

  {
  	u8 *p = object;
  	u8 *endobject = object + s->objsize;
  
  	if (s->flags & SLAB_RED_ZONE) {

  		if (!check_bytes_and_report(s, page, object, "Redzone",

  			endobject, val, s->inuse - s->objsize))

  			return 0;

  	} else {

  		if ((s->flags & SLAB_POISON) && s->objsize < s->inuse) {
  			check_bytes_and_report(s, page, p, "Alignment padding",
  				endobject, POISON_INUSE, s->inuse - s->objsize);
  		}

  	}
  
  	if (s->flags & SLAB_POISON) {

  		if (val != SLUB_RED_ACTIVE && (s->flags & __OBJECT_POISON) &&

  			(!check_bytes_and_report(s, page, p, "Poison", p,
  					POISON_FREE, s->objsize - 1) ||
  			 !check_bytes_and_report(s, page, p, "Poison",

  				p + s->objsize - 1, POISON_END, 1)))

  			return 0;

  		/*
  		 * check_pad_bytes cleans up on its own.
  		 */
  		check_pad_bytes(s, page, p);
  	}

  	if (!s->offset && val == SLUB_RED_ACTIVE)

  		/*
  		 * Object and freepointer overlap. Cannot check
  		 * freepointer while object is allocated.
  		 */
  		return 1;
  
  	/* Check free pointer validity */
  	if (!check_valid_pointer(s, page, get_freepointer(s, p))) {
  		object_err(s, page, p, "Freepointer corrupt");
  		/*

  		 * No choice but to zap it and thus lose the remainder

  		 * of the free objects in this slab. May cause

  		 * another error because the object count is now wrong.

  		 */

  		set_freepointer(s, p, NULL);

  		return 0;
  	}
  	return 1;
  }
  
  static int check_slab(struct kmem_cache *s, struct page *page)
  {

  	int maxobj;

  	VM_BUG_ON(!irqs_disabled());
  
  	if (!PageSlab(page)) {

  		slab_err(s, page, "Not a valid slab page");

  		return 0;
  	}

  	maxobj = order_objects(compound_order(page), s->size, s->reserved);

  	if (page->objects > maxobj) {
  		slab_err(s, page, "objects %u > max %u",
  			s->name, page->objects, maxobj);
  		return 0;
  	}
  	if (page->inuse > page->objects) {

  		slab_err(s, page, "inuse %u > max %u",

  			s->name, page->inuse, page->objects);

  		return 0;
  	}
  	/* Slab_pad_check fixes things up after itself */
  	slab_pad_check(s, page);
  	return 1;
  }
  
  /*

   * Determine if a certain object on a page is on the freelist. Must hold the
   * slab lock to guarantee that the chains are in a consistent state.

   */
  static int on_freelist(struct kmem_cache *s, struct page *page, void *search)
  {
  	int nr = 0;

  	void *fp;

  	void *object = NULL;

  	unsigned long max_objects;

  	fp = page->freelist;

  	while (fp && nr <= page->objects) {

  		if (fp == search)
  			return 1;
  		if (!check_valid_pointer(s, page, fp)) {
  			if (object) {
  				object_err(s, page, object,
  					"Freechain corrupt");

  				set_freepointer(s, object, NULL);

  				break;
  			} else {

  				slab_err(s, page, "Freepointer corrupt");

  				page->freelist = NULL;

  				page->inuse = page->objects;

  				slab_fix(s, "Freelist cleared");

  				return 0;
  			}
  			break;
  		}
  		object = fp;
  		fp = get_freepointer(s, object);
  		nr++;
  	}

  	max_objects = order_objects(compound_order(page), s->size, s->reserved);

  	if (max_objects > MAX_OBJS_PER_PAGE)
  		max_objects = MAX_OBJS_PER_PAGE;

  
  	if (page->objects != max_objects) {
  		slab_err(s, page, "Wrong number of objects. Found %d but "
  			"should be %d", page->objects, max_objects);
  		page->objects = max_objects;
  		slab_fix(s, "Number of objects adjusted.");
  	}

  	if (page->inuse != page->objects - nr) {

  		slab_err(s, page, "Wrong object count. Counter is %d but "

  			"counted were %d", page->inuse, page->objects - nr);
  		page->inuse = page->objects - nr;

  		slab_fix(s, "Object count adjusted.");

  	}
  	return search == NULL;
  }

  static void trace(struct kmem_cache *s, struct page *page, void *object,
  								int alloc)

  {
  	if (s->flags & SLAB_TRACE) {
  		printk(KERN_INFO "TRACE %s %s 0x%p inuse=%d fp=0x%p
  ",
  			s->name,
  			alloc ? "alloc" : "free",
  			object, page->inuse,
  			page->freelist);
  
  		if (!alloc)
  			print_section("Object", (void *)object, s->objsize);
  
  		dump_stack();
  	}
  }

  /*

   * Hooks for other subsystems that check memory allocations. In a typical
   * production configuration these hooks all should produce no code at all.
   */
  static inline int slab_pre_alloc_hook(struct kmem_cache *s, gfp_t flags)
  {

  	flags &= gfp_allowed_mask;

  	lockdep_trace_alloc(flags);
  	might_sleep_if(flags & __GFP_WAIT);
  
  	return should_failslab(s->objsize, flags, s->flags);
  }
  
  static inline void slab_post_alloc_hook(struct kmem_cache *s, gfp_t flags, void *object)
  {

  	flags &= gfp_allowed_mask;

  	kmemcheck_slab_alloc(s, flags, object, slab_ksize(s));

  	kmemleak_alloc_recursive(object, s->objsize, 1, s->flags, flags);
  }
  
  static inline void slab_free_hook(struct kmem_cache *s, void *x)
  {
  	kmemleak_free_recursive(x, s->flags);

  	/*
  	 * Trouble is that we may no longer disable interupts in the fast path
  	 * So in order to make the debug calls that expect irqs to be
  	 * disabled we need to disable interrupts temporarily.
  	 */
  #if defined(CONFIG_KMEMCHECK) || defined(CONFIG_LOCKDEP)
  	{
  		unsigned long flags;
  
  		local_irq_save(flags);
  		kmemcheck_slab_free(s, x, s->objsize);
  		debug_check_no_locks_freed(x, s->objsize);

  		local_irq_restore(flags);
  	}
  #endif

  	if (!(s->flags & SLAB_DEBUG_OBJECTS))
  		debug_check_no_obj_freed(x, s->objsize);

  }
  
  /*

   * Tracking of fully allocated slabs for debugging purposes.

   *
   * list_lock must be held.

   */

  static void add_full(struct kmem_cache *s,
  	struct kmem_cache_node *n, struct page *page)

  {

  	if (!(s->flags & SLAB_STORE_USER))
  		return;

  	list_add(&page->lru, &n->full);

  }

  /*
   * list_lock must be held.
   */

  static void remove_full(struct kmem_cache *s, struct page *page)
  {

  	if (!(s->flags & SLAB_STORE_USER))
  		return;

  	list_del(&page->lru);

  }

  /* Tracking of the number of slabs for debugging purposes */
  static inline unsigned long slabs_node(struct kmem_cache *s, int node)
  {
  	struct kmem_cache_node *n = get_node(s, node);
  
  	return atomic_long_read(&n->nr_slabs);
  }

  static inline unsigned long node_nr_slabs(struct kmem_cache_node *n)
  {
  	return atomic_long_read(&n->nr_slabs);
  }

  static inline void inc_slabs_node(struct kmem_cache *s, int node, int objects)

  {
  	struct kmem_cache_node *n = get_node(s, node);
  
  	/*
  	 * May be called early in order to allocate a slab for the
  	 * kmem_cache_node structure. Solve the chicken-egg
  	 * dilemma by deferring the increment of the count during
  	 * bootstrap (see early_kmem_cache_node_alloc).
  	 */

  	if (n) {

  		atomic_long_inc(&n->nr_slabs);

  		atomic_long_add(objects, &n->total_objects);
  	}

  }

  static inline void dec_slabs_node(struct kmem_cache *s, int node, int objects)

  {
  	struct kmem_cache_node *n = get_node(s, node);
  
  	atomic_long_dec(&n->nr_slabs);

  	atomic_long_sub(objects, &n->total_objects);

  }
  
  /* Object debug checks for alloc/free paths */

  static void setup_object_debug(struct kmem_cache *s, struct page *page,
  								void *object)
  {
  	if (!(s->flags & (SLAB_STORE_USER|SLAB_RED_ZONE|__OBJECT_POISON)))
  		return;

  	init_object(s, object, SLUB_RED_INACTIVE);

  	init_tracking(s, object);
  }

  static noinline int alloc_debug_processing(struct kmem_cache *s, struct page *page,

  					void *object, unsigned long addr)

  {
  	if (!check_slab(s, page))
  		goto bad;

  	if (!check_valid_pointer(s, page, object)) {
  		object_err(s, page, object, "Freelist Pointer check fails");

  		goto bad;

  	}

  	if (!check_object(s, page, object, SLUB_RED_INACTIVE))

  		goto bad;

  	/* Success perform special debug activities for allocs */
  	if (s->flags & SLAB_STORE_USER)
  		set_track(s, object, TRACK_ALLOC, addr);
  	trace(s, page, object, 1);

  	init_object(s, object, SLUB_RED_ACTIVE);

  	return 1;

  bad:
  	if (PageSlab(page)) {
  		/*
  		 * If this is a slab page then lets do the best we can
  		 * to avoid issues in the future. Marking all objects

  		 * as used avoids touching the remaining objects.

  		 */

  		slab_fix(s, "Marking all objects used");

  		page->inuse = page->objects;

  		page->freelist = NULL;

  	}
  	return 0;
  }

  static noinline int free_debug_processing(struct kmem_cache *s,
  		 struct page *page, void *object, unsigned long addr)

  {

  	unsigned long flags;
  	int rc = 0;
  
  	local_irq_save(flags);

  	slab_lock(page);

  	if (!check_slab(s, page))
  		goto fail;
  
  	if (!check_valid_pointer(s, page, object)) {

  		slab_err(s, page, "Invalid object pointer 0x%p", object);

  		goto fail;
  	}
  
  	if (on_freelist(s, page, object)) {

  		object_err(s, page, object, "Object already free");

  		goto fail;
  	}

  	if (!check_object(s, page, object, SLUB_RED_ACTIVE))

  		goto out;

  
  	if (unlikely(s != page->slab)) {

  		if (!PageSlab(page)) {

  			slab_err(s, page, "Attempt to free object(0x%p) "
  				"outside of slab", object);

  		} else if (!page->slab) {

  			printk(KERN_ERR

  				"SLUB <none>: no slab for object 0x%p.
  ",

  						object);

  			dump_stack();

  		} else

  			object_err(s, page, object,
  					"page slab pointer corrupt.");

  		goto fail;
  	}

  	if (s->flags & SLAB_STORE_USER)
  		set_track(s, object, TRACK_FREE, addr);
  	trace(s, page, object, 0);

  	init_object(s, object, SLUB_RED_INACTIVE);

  	rc = 1;
  out:

  	slab_unlock(page);

  	local_irq_restore(flags);
  	return rc;

  fail:

  	slab_fix(s, "Object at 0x%p not freed", object);

  	goto out;

  }

  static int __init setup_slub_debug(char *str)
  {

  	slub_debug = DEBUG_DEFAULT_FLAGS;
  	if (*str++ != '=' || !*str)
  		/*
  		 * No options specified. Switch on full debugging.
  		 */
  		goto out;
  
  	if (*str == ',')
  		/*
  		 * No options but restriction on slabs. This means full
  		 * debugging for slabs matching a pattern.
  		 */
  		goto check_slabs;

  	if (tolower(*str) == 'o') {
  		/*
  		 * Avoid enabling debugging on caches if its minimum order
  		 * would increase as a result.
  		 */
  		disable_higher_order_debug = 1;
  		goto out;
  	}

  	slub_debug = 0;
  	if (*str == '-')
  		/*
  		 * Switch off all debugging measures.
  		 */
  		goto out;
  
  	/*
  	 * Determine which debug features should be switched on
  	 */

  	for (; *str && *str != ','; str++) {

  		switch (tolower(*str)) {
  		case 'f':
  			slub_debug |= SLAB_DEBUG_FREE;
  			break;
  		case 'z':
  			slub_debug |= SLAB_RED_ZONE;
  			break;
  		case 'p':
  			slub_debug |= SLAB_POISON;
  			break;
  		case 'u':
  			slub_debug |= SLAB_STORE_USER;
  			break;
  		case 't':
  			slub_debug |= SLAB_TRACE;
  			break;

  		case 'a':
  			slub_debug |= SLAB_FAILSLAB;
  			break;

  		default:
  			printk(KERN_ERR "slub_debug option '%c' "

  				"unknown. skipped
  ", *str);

  		}

  	}

  check_slabs:

  	if (*str == ',')
  		slub_debug_slabs = str + 1;

  out:

  	return 1;
  }
  
  __setup("slub_debug", setup_slub_debug);

  static unsigned long kmem_cache_flags(unsigned long objsize,
  	unsigned long flags, const char *name,

  	void (*ctor)(void *))

  {
  	/*

  	 * Enable debugging if selected on the kernel commandline.

  	 */

  	if (slub_debug && (!slub_debug_slabs ||

  		!strncmp(slub_debug_slabs, name, strlen(slub_debug_slabs))))
  		flags |= slub_debug;

  
  	return flags;

  }
  #else

  static inline void setup_object_debug(struct kmem_cache *s,
  			struct page *page, void *object) {}

  static inline int alloc_debug_processing(struct kmem_cache *s,

  	struct page *page, void *object, unsigned long addr) { return 0; }

  static inline int free_debug_processing(struct kmem_cache *s,

  	struct page *page, void *object, unsigned long addr) { return 0; }

  static inline int slab_pad_check(struct kmem_cache *s, struct page *page)
  			{ return 1; }
  static inline int check_object(struct kmem_cache *s, struct page *page,

  			void *object, u8 val) { return 1; }

  static inline void add_full(struct kmem_cache *s, struct kmem_cache_node *n,
  					struct page *page) {}

  static inline void remove_full(struct kmem_cache *s, struct page *page) {}

  static inline unsigned long kmem_cache_flags(unsigned long objsize,
  	unsigned long flags, const char *name,

  	void (*ctor)(void *))

  {
  	return flags;
  }

  #define slub_debug 0

  #define disable_higher_order_debug 0

  static inline unsigned long slabs_node(struct kmem_cache *s, int node)
  							{ return 0; }

  static inline unsigned long node_nr_slabs(struct kmem_cache_node *n)
  							{ return 0; }

  static inline void inc_slabs_node(struct kmem_cache *s, int node,
  							int objects) {}
  static inline void dec_slabs_node(struct kmem_cache *s, int node,
  							int objects) {}

  
  static inline int slab_pre_alloc_hook(struct kmem_cache *s, gfp_t flags)
  							{ return 0; }
  
  static inline void slab_post_alloc_hook(struct kmem_cache *s, gfp_t flags,
  		void *object) {}
  
  static inline void slab_free_hook(struct kmem_cache *s, void *x) {}

  #endif /* CONFIG_SLUB_DEBUG */

  /*
   * Slab allocation and freeing
   */

  static inline struct page *alloc_slab_page(gfp_t flags, int node,
  					struct kmem_cache_order_objects oo)
  {
  	int order = oo_order(oo);

  	flags |= __GFP_NOTRACK;

  	if (node == NUMA_NO_NODE)

  		return alloc_pages(flags, order);
  	else

  		return alloc_pages_exact_node(node, flags, order);

  }

  static struct page *allocate_slab(struct kmem_cache *s, gfp_t flags, int node)
  {

  	struct page *page;

  	struct kmem_cache_order_objects oo = s->oo;

  	gfp_t alloc_gfp;

  	flags &= gfp_allowed_mask;
  
  	if (flags & __GFP_WAIT)
  		local_irq_enable();

  	flags |= s->allocflags;

  	/*
  	 * Let the initial higher-order allocation fail under memory pressure
  	 * so we fall-back to the minimum order allocation.
  	 */
  	alloc_gfp = (flags | __GFP_NOWARN | __GFP_NORETRY) & ~__GFP_NOFAIL;
  
  	page = alloc_slab_page(alloc_gfp, node, oo);

  	if (unlikely(!page)) {
  		oo = s->min;
  		/*
  		 * Allocation may have failed due to fragmentation.
  		 * Try a lower order alloc if possible
  		 */
  		page = alloc_slab_page(flags, node, oo);

  		if (page)
  			stat(s, ORDER_FALLBACK);

  	}

  	if (flags & __GFP_WAIT)
  		local_irq_disable();
  
  	if (!page)
  		return NULL;

  	if (kmemcheck_enabled

  		&& !(s->flags & (SLAB_NOTRACK | DEBUG_DEFAULT_FLAGS))) {

  		int pages = 1 << oo_order(oo);
  
  		kmemcheck_alloc_shadow(page, oo_order(oo), flags, node);
  
  		/*
  		 * Objects from caches that have a constructor don't get
  		 * cleared when they're allocated, so we need to do it here.
  		 */
  		if (s->ctor)
  			kmemcheck_mark_uninitialized_pages(page, pages);
  		else
  			kmemcheck_mark_unallocated_pages(page, pages);

  	}

  	page->objects = oo_objects(oo);

  	mod_zone_page_state(page_zone(page),
  		(s->flags & SLAB_RECLAIM_ACCOUNT) ?
  		NR_SLAB_RECLAIMABLE : NR_SLAB_UNRECLAIMABLE,

  		1 << oo_order(oo));

  
  	return page;
  }
  
  static void setup_object(struct kmem_cache *s, struct page *page,
  				void *object)
  {

  	setup_object_debug(s, page, object);

  	if (unlikely(s->ctor))

  		s->ctor(object);

  }
  
  static struct page *new_slab(struct kmem_cache *s, gfp_t flags, int node)
  {
  	struct page *page;

  	void *start;

  	void *last;
  	void *p;

  	BUG_ON(flags & GFP_SLAB_BUG_MASK);

  	page = allocate_slab(s,
  		flags & (GFP_RECLAIM_MASK | GFP_CONSTRAINT_MASK), node);

  	if (!page)
  		goto out;

  	inc_slabs_node(s, page_to_nid(page), page->objects);

  	page->slab = s;
  	page->flags |= 1 << PG_slab;

  
  	start = page_address(page);

  
  	if (unlikely(s->flags & SLAB_POISON))

  		memset(start, POISON_INUSE, PAGE_SIZE << compound_order(page));

  
  	last = start;

  	for_each_object(p, s, start, page->objects) {

  		setup_object(s, page, last);
  		set_freepointer(s, last, p);
  		last = p;
  	}
  	setup_object(s, page, last);

  	set_freepointer(s, last, NULL);

  
  	page->freelist = start;
  	page->inuse = 0;

  	page->frozen = 1;

  out:

  	return page;
  }
  
  static void __free_slab(struct kmem_cache *s, struct page *page)
  {

  	int order = compound_order(page);
  	int pages = 1 << order;

  	if (kmem_cache_debug(s)) {

  		void *p;
  
  		slab_pad_check(s, page);

  		for_each_object(p, s, page_address(page),
  						page->objects)

  			check_object(s, page, p, SLUB_RED_INACTIVE);

  	}

  	kmemcheck_free_shadow(page, compound_order(page));

  	mod_zone_page_state(page_zone(page),
  		(s->flags & SLAB_RECLAIM_ACCOUNT) ?
  		NR_SLAB_RECLAIMABLE : NR_SLAB_UNRECLAIMABLE,

  		-pages);

  	__ClearPageSlab(page);
  	reset_page_mapcount(page);

  	if (current->reclaim_state)
  		current->reclaim_state->reclaimed_slab += pages;

  	__free_pages(page, order);

  }

  #define need_reserve_slab_rcu						\
  	(sizeof(((struct page *)NULL)->lru) < sizeof(struct rcu_head))

  static void rcu_free_slab(struct rcu_head *h)
  {
  	struct page *page;

  	if (need_reserve_slab_rcu)
  		page = virt_to_head_page(h);
  	else
  		page = container_of((struct list_head *)h, struct page, lru);

  	__free_slab(page->slab, page);
  }
  
  static void free_slab(struct kmem_cache *s, struct page *page)
  {
  	if (unlikely(s->flags & SLAB_DESTROY_BY_RCU)) {

  		struct rcu_head *head;
  
  		if (need_reserve_slab_rcu) {
  			int order = compound_order(page);
  			int offset = (PAGE_SIZE << order) - s->reserved;
  
  			VM_BUG_ON(s->reserved != sizeof(*head));
  			head = page_address(page) + offset;
  		} else {
  			/*
  			 * RCU free overloads the RCU head over the LRU
  			 */
  			head = (void *)&page->lru;
  		}

  
  		call_rcu(head, rcu_free_slab);
  	} else
  		__free_slab(s, page);
  }
  
  static void discard_slab(struct kmem_cache *s, struct page *page)
  {

  	dec_slabs_node(s, page_to_nid(page), page->objects);

  	free_slab(s, page);
  }
  
  /*

   * Management of partially allocated slabs.
   *
   * list_lock must be held.

   */

  static inline void add_partial(struct kmem_cache_node *n,

  				struct page *page, int tail)

  {

  	n->nr_partial++;

  	if (tail)
  		list_add_tail(&page->lru, &n->partial);
  	else
  		list_add(&page->lru, &n->partial);

  }

  /*
   * list_lock must be held.
   */
  static inline void remove_partial(struct kmem_cache_node *n,

  					struct page *page)
  {
  	list_del(&page->lru);
  	n->nr_partial--;
  }

  /*

   * Lock slab, remove from the partial list and put the object into the
   * per cpu freelist.

   *

   * Must hold list_lock.

   */

  static inline int acquire_slab(struct kmem_cache *s,

  		struct kmem_cache_node *n, struct page *page)

  {

  	void *freelist;
  	unsigned long counters;
  	struct page new;

  	/*
  	 * Zap the freelist and set the frozen bit.
  	 * The old freelist is the list of objects for the
  	 * per cpu allocation list.
  	 */
  	do {
  		freelist = page->freelist;
  		counters = page->counters;
  		new.counters = counters;
  		new.inuse = page->objects;
  
  		VM_BUG_ON(new.frozen);
  		new.frozen = 1;

  	} while (!__cmpxchg_double_slab(s, page,

  			freelist, counters,
  			NULL, new.counters,
  			"lock and freeze"));
  
  	remove_partial(n, page);
  
  	if (freelist) {
  		/* Populate the per cpu freelist */
  		this_cpu_write(s->cpu_slab->freelist, freelist);
  		this_cpu_write(s->cpu_slab->page, page);
  		this_cpu_write(s->cpu_slab->node, page_to_nid(page));

  		return 1;

  	} else {
  		/*
  		 * Slab page came from the wrong list. No object to allocate
  		 * from. Put it onto the correct list and continue partial
  		 * scan.
  		 */
  		printk(KERN_ERR "SLUB: %s : Page without available objects on"
  			" partial list
  ", s->name);

  		return 0;

  	}

  }
  
  /*

   * Try to allocate a partial slab from a specific node.

   */

  static struct page *get_partial_node(struct kmem_cache *s,
  					struct kmem_cache_node *n)

  {
  	struct page *page;
  
  	/*
  	 * Racy check. If we mistakenly see no partial slabs then we
  	 * just allocate an empty slab. If we mistakenly try to get a

  	 * partial slab and there is none available then get_partials()
  	 * will return NULL.

  	 */
  	if (!n || !n->nr_partial)
  		return NULL;
  
  	spin_lock(&n->list_lock);
  	list_for_each_entry(page, &n->partial, lru)

  		if (acquire_slab(s, n, page))

  			goto out;
  	page = NULL;
  out:
  	spin_unlock(&n->list_lock);
  	return page;
  }
  
  /*

   * Get a page from somewhere. Search in increasing NUMA distances.

   */
  static struct page *get_any_partial(struct kmem_cache *s, gfp_t flags)
  {
  #ifdef CONFIG_NUMA
  	struct zonelist *zonelist;

  	struct zoneref *z;

  	struct zone *zone;
  	enum zone_type high_zoneidx = gfp_zone(flags);

  	struct page *page;
  
  	/*

  	 * The defrag ratio allows a configuration of the tradeoffs between
  	 * inter node defragmentation and node local allocations. A lower
  	 * defrag_ratio increases the tendency to do local allocations
  	 * instead of attempting to obtain partial slabs from other nodes.

  	 *

  	 * If the defrag_ratio is set to 0 then kmalloc() always
  	 * returns node local objects. If the ratio is higher then kmalloc()
  	 * may return off node objects because partial slabs are obtained
  	 * from other nodes and filled up.

  	 *

  	 * If /sys/kernel/slab/xx/defrag_ratio is set to 100 (which makes

  	 * defrag_ratio = 1000) then every (well almost) allocation will
  	 * first attempt to defrag slab caches on other nodes. This means
  	 * scanning over all nodes to look for partial slabs which may be
  	 * expensive if we do it every time we are trying to find a slab
  	 * with available objects.

  	 */

  	if (!s->remote_node_defrag_ratio ||
  			get_cycles() % 1024 > s->remote_node_defrag_ratio)

  		return NULL;

  	get_mems_allowed();

  	zonelist = node_zonelist(slab_node(current->mempolicy), flags);

  	for_each_zone_zonelist(zone, z, zonelist, high_zoneidx) {

  		struct kmem_cache_node *n;

  		n = get_node(s, zone_to_nid(zone));

  		if (n && cpuset_zone_allowed_hardwall(zone, flags) &&

  				n->nr_partial > s->min_partial) {

  			page = get_partial_node(s, n);

  			if (page) {
  				put_mems_allowed();

  				return page;

  			}

  		}
  	}

  	put_mems_allowed();

  #endif
  	return NULL;
  }
  
  /*
   * Get a partial page, lock it and return it.
   */
  static struct page *get_partial(struct kmem_cache *s, gfp_t flags, int node)
  {
  	struct page *page;

  	int searchnode = (node == NUMA_NO_NODE) ? numa_node_id() : node;

  	page = get_partial_node(s, get_node(s, searchnode));

  	if (page || node != NUMA_NO_NODE)

  		return page;
  
  	return get_any_partial(s, flags);
  }

  #ifdef CONFIG_PREEMPT
  /*
   * Calculate the next globally unique transaction for disambiguiation
   * during cmpxchg. The transactions start with the cpu number and are then
   * incremented by CONFIG_NR_CPUS.
   */
  #define TID_STEP  roundup_pow_of_two(CONFIG_NR_CPUS)
  #else
  /*
   * No preemption supported therefore also no need to check for
   * different cpus.
   */
  #define TID_STEP 1
  #endif
  
  static inline unsigned long next_tid(unsigned long tid)
  {
  	return tid + TID_STEP;
  }
  
  static inline unsigned int tid_to_cpu(unsigned long tid)
  {
  	return tid % TID_STEP;
  }
  
  static inline unsigned long tid_to_event(unsigned long tid)
  {
  	return tid / TID_STEP;
  }
  
  static inline unsigned int init_tid(int cpu)
  {
  	return cpu;
  }
  
  static inline void note_cmpxchg_failure(const char *n,
  		const struct kmem_cache *s, unsigned long tid)
  {
  #ifdef SLUB_DEBUG_CMPXCHG
  	unsigned long actual_tid = __this_cpu_read(s->cpu_slab->tid);
  
  	printk(KERN_INFO "%s %s: cmpxchg redo ", n, s->name);
  
  #ifdef CONFIG_PREEMPT
  	if (tid_to_cpu(tid) != tid_to_cpu(actual_tid))
  		printk("due to cpu change %d -> %d
  ",
  			tid_to_cpu(tid), tid_to_cpu(actual_tid));
  	else
  #endif
  	if (tid_to_event(tid) != tid_to_event(actual_tid))
  		printk("due to cpu running other code. Event %ld->%ld
  ",
  			tid_to_event(tid), tid_to_event(actual_tid));
  	else
  		printk("for unknown reason: actual=%lx was=%lx target=%lx
  ",
  			actual_tid, tid, next_tid(tid));
  #endif

  	stat(s, CMPXCHG_DOUBLE_CPU_FAIL);

  }

  void init_kmem_cache_cpus(struct kmem_cache *s)
  {

  	int cpu;
  
  	for_each_possible_cpu(cpu)
  		per_cpu_ptr(s->cpu_slab, cpu)->tid = init_tid(cpu);

  }

  /*
   * Remove the cpu slab
   */

  
  /*
   * Remove the cpu slab
   */

  static void deactivate_slab(struct kmem_cache *s, struct kmem_cache_cpu *c)

  {

  	enum slab_modes { M_NONE, M_PARTIAL, M_FULL, M_FREE };

  	struct page *page = c->page;

  	struct kmem_cache_node *n = get_node(s, page_to_nid(page));
  	int lock = 0;
  	enum slab_modes l = M_NONE, m = M_NONE;
  	void *freelist;
  	void *nextfree;
  	int tail = 0;
  	struct page new;
  	struct page old;
  
  	if (page->freelist) {

  		stat(s, DEACTIVATE_REMOTE_FREES);

  		tail = 1;
  	}
  
  	c->tid = next_tid(c->tid);
  	c->page = NULL;
  	freelist = c->freelist;
  	c->freelist = NULL;

  	/*

  	 * Stage one: Free all available per cpu objects back
  	 * to the page freelist while it is still frozen. Leave the
  	 * last one.
  	 *
  	 * There is no need to take the list->lock because the page
  	 * is still frozen.
  	 */
  	while (freelist && (nextfree = get_freepointer(s, freelist))) {
  		void *prior;
  		unsigned long counters;
  
  		do {
  			prior = page->freelist;
  			counters = page->counters;
  			set_freepointer(s, freelist, prior);
  			new.counters = counters;
  			new.inuse--;
  			VM_BUG_ON(!new.frozen);

  		} while (!__cmpxchg_double_slab(s, page,

  			prior, counters,
  			freelist, new.counters,
  			"drain percpu freelist"));
  
  		freelist = nextfree;
  	}

  	/*

  	 * Stage two: Ensure that the page is unfrozen while the
  	 * list presence reflects the actual number of objects
  	 * during unfreeze.
  	 *
  	 * We setup the list membership and then perform a cmpxchg
  	 * with the count. If there is a mismatch then the page
  	 * is not unfrozen but the page is on the wrong list.
  	 *
  	 * Then we restart the process which may have to remove
  	 * the page from the list that we just put it on again
  	 * because the number of objects in the slab may have
  	 * changed.

  	 */

  redo:

  	old.freelist = page->freelist;
  	old.counters = page->counters;
  	VM_BUG_ON(!old.frozen);

  	/* Determine target state of the slab */
  	new.counters = old.counters;
  	if (freelist) {
  		new.inuse--;
  		set_freepointer(s, freelist, old.freelist);
  		new.freelist = freelist;
  	} else
  		new.freelist = old.freelist;
  
  	new.frozen = 0;

  	if (!new.inuse && n->nr_partial > s->min_partial)

  		m = M_FREE;
  	else if (new.freelist) {
  		m = M_PARTIAL;
  		if (!lock) {
  			lock = 1;
  			/*
  			 * Taking the spinlock removes the possiblity
  			 * that acquire_slab() will see a slab page that
  			 * is frozen
  			 */
  			spin_lock(&n->list_lock);
  		}
  	} else {
  		m = M_FULL;
  		if (kmem_cache_debug(s) && !lock) {
  			lock = 1;
  			/*
  			 * This also ensures that the scanning of full
  			 * slabs from diagnostic functions will not see
  			 * any frozen slabs.
  			 */
  			spin_lock(&n->list_lock);
  		}
  	}
  
  	if (l != m) {
  
  		if (l == M_PARTIAL)
  
  			remove_partial(n, page);
  
  		else if (l == M_FULL)

  			remove_full(s, page);
  
  		if (m == M_PARTIAL) {
  
  			add_partial(n, page, tail);
  			stat(s, tail ? DEACTIVATE_TO_TAIL : DEACTIVATE_TO_HEAD);
  
  		} else if (m == M_FULL) {

  			stat(s, DEACTIVATE_FULL);
  			add_full(s, n, page);
  
  		}
  	}
  
  	l = m;

  	if (!__cmpxchg_double_slab(s, page,

  				old.freelist, old.counters,
  				new.freelist, new.counters,
  				"unfreezing slab"))
  		goto redo;

  	if (lock)
  		spin_unlock(&n->list_lock);
  
  	if (m == M_FREE) {
  		stat(s, DEACTIVATE_EMPTY);
  		discard_slab(s, page);
  		stat(s, FREE_SLAB);

  	}

  }

  static inline void flush_slab(struct kmem_cache *s, struct kmem_cache_cpu *c)

  {

  	stat(s, CPUSLAB_FLUSH);

  	deactivate_slab(s, c);

  }
  
  /*
   * Flush cpu slab.

   *

   * Called from IPI handler with interrupts disabled.
   */

  static inline void __flush_cpu_slab(struct kmem_cache *s, int cpu)

  {

  	struct kmem_cache_cpu *c = per_cpu_ptr(s->cpu_slab, cpu);

  	if (likely(c && c->page))
  		flush_slab(s, c);

  }
  
  static void flush_cpu_slab(void *d)
  {
  	struct kmem_cache *s = d;

  	__flush_cpu_slab(s, smp_processor_id());

  }
  
  static void flush_all(struct kmem_cache *s)
  {

  	on_each_cpu(flush_cpu_slab, s, 1);

  }
  
  /*

   * Check if the objects in a per cpu structure fit numa
   * locality expectations.
   */
  static inline int node_match(struct kmem_cache_cpu *c, int node)
  {
  #ifdef CONFIG_NUMA

  	if (node != NUMA_NO_NODE && c->node != node)

  		return 0;
  #endif
  	return 1;
  }

  static int count_free(struct page *page)
  {
  	return page->objects - page->inuse;
  }
  
  static unsigned long count_partial(struct kmem_cache_node *n,
  					int (*get_count)(struct page *))
  {
  	unsigned long flags;
  	unsigned long x = 0;
  	struct page *page;
  
  	spin_lock_irqsave(&n->list_lock, flags);
  	list_for_each_entry(page, &n->partial, lru)
  		x += get_count(page);
  	spin_unlock_irqrestore(&n->list_lock, flags);
  	return x;
  }

  static inline unsigned long node_nr_objs(struct kmem_cache_node *n)
  {
  #ifdef CONFIG_SLUB_DEBUG
  	return atomic_long_read(&n->total_objects);
  #else
  	return 0;
  #endif
  }

  static noinline void
  slab_out_of_memory(struct kmem_cache *s, gfp_t gfpflags, int nid)
  {
  	int node;
  
  	printk(KERN_WARNING
  		"SLUB: Unable to allocate memory on node %d (gfp=0x%x)
  ",
  		nid, gfpflags);
  	printk(KERN_WARNING "  cache: %s, object size: %d, buffer size: %d, "
  		"default order: %d, min order: %d
  ", s->name, s->objsize,
  		s->size, oo_order(s->oo), oo_order(s->min));

  	if (oo_order(s->min) > get_order(s->objsize))
  		printk(KERN_WARNING "  %s debugging increased min order, use "
  		       "slub_debug=O to disable.
  ", s->name);

  	for_each_online_node(node) {
  		struct kmem_cache_node *n = get_node(s, node);
  		unsigned long nr_slabs;
  		unsigned long nr_objs;
  		unsigned long nr_free;
  
  		if (!n)
  			continue;

  		nr_free  = count_partial(n, count_free);
  		nr_slabs = node_nr_slabs(n);
  		nr_objs  = node_nr_objs(n);