/*
   * 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 and only
   * uses a centralized lock to manage a pool of partial slabs.
   *

   * (C) 2007 SGI, 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/kmemtrace.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>

  
  /*
   * Lock order:
   *   1. slab_lock(page)
   *   2. slab->list_lock
   *
   *   The slab_lock protects operations on the object of a particular
   *   slab and its metadata in the page struct. If the slab lock
   *   has been taken then no allocations nor frees can be performed
   *   on the objects in the slab nor can the slab be added or removed
   *   from the partial or full lists since this would mean modifying
   *   the page_struct of the slab.
   *
   *   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.
   *
   *   The lock order is sometimes inverted when we are trying to get a slab
   *   off a list. We take the list_lock and then look for a page on the list
   *   to use. While we do that objects in the slabs may be freed. We can
   *   only operate on the slab if we have also taken the slab_lock. So we use
   *   a slab_trylock() on the slab. If trylock was successful then no frees
   *   can occur anymore and we can use the slab for allocations etc. If the
   *   slab_trylock() does not succeed then frees are in progress in the slab and
   *   we must stay away from it for a while since we may cause a bouncing
   *   cacheline if we try to acquire the lock. So go onto the next slab.
   *   If all pages are busy then we may allocate a new slab instead of reusing
   *   a partial slab. A new slab has noone operating on it and thus there is
   *   no danger of cacheline contention.
   *
   *   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.

   */

  #ifdef CONFIG_SLUB_DEBUG

  #define SLABDEBUG 1

  #else
  #define SLABDEBUG 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

  /*

   * 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	65535 /* since page.objects is u16 */

  /* Internal SLUB flags */

  #define __OBJECT_POISON		0x80000000 /* Poison object */
  #define __SYSFS_ADD_DEFERRED	0x40000000 /* Not yet visible via sysfs */

  
  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_open() works but kmalloc does not */

  	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.
   */
  struct track {

  	unsigned long addr;	/* Called from address */

  	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_SLUB_DEBUG

  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);
  }

  #endif

  static inline void stat(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)
  {
  #ifdef CONFIG_NUMA
  	return s->node[node];
  #else
  	return &s->local_node;
  #endif
  }

  /* 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 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)
  
  /* Scan freelist */
  #define for_each_free_object(__p, __s, __free) \

  	for (__p = (__free); __p; __p = get_freepointer((__s), __p))

  
  /* 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 struct kmem_cache_order_objects oo_make(int order,
  						unsigned long size)
  {
  	struct kmem_cache_order_objects x = {

  		(order << OO_SHIFT) + (PAGE_SIZE << order) / size

  	};
  
  	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;

  }

  #ifdef CONFIG_SLUB_DEBUG
  /*
   * 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) {
  		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);

  }
  
  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, int active)
  {
  	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,
  			active ? SLUB_RED_ACTIVE : SLUB_RED_INACTIVE,
  			s->inuse - s->objsize);
  }

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

  {
  	while (bytes) {
  		if (*start != (u8)value)

  			return start;

  		start++;
  		bytes--;
  	}

  	return NULL;
  }
  
  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));

  	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, int active)
  {
  	u8 *p = object;
  	u8 *endobject = object + s->objsize;
  
  	if (s->flags & SLAB_RED_ZONE) {
  		unsigned int red =
  			active ? SLUB_RED_ACTIVE : SLUB_RED_INACTIVE;

  		if (!check_bytes_and_report(s, page, object, "Redzone",
  			endobject, red, 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 (!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 && 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 = (PAGE_SIZE << compound_order(page)) / s->size;
  	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 = page->freelist;
  	void *object = NULL;

  	unsigned long max_objects;

  	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 = (PAGE_SIZE << compound_order(page)) / s->size;

  	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();
  	}
  }

  /*

   * Tracking of fully allocated slabs for debugging purposes.

   */

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

  {

  	spin_lock(&n->list_lock);
  	list_add(&page->lru, &n->full);
  	spin_unlock(&n->list_lock);
  }
  
  static void remove_full(struct kmem_cache *s, struct page *page)
  {
  	struct kmem_cache_node *n;
  
  	if (!(s->flags & SLAB_STORE_USER))
  		return;
  
  	n = get_node(s, page_to_nid(page));
  
  	spin_lock(&n->list_lock);
  	list_del(&page->lru);
  	spin_unlock(&n->list_lock);
  }

  /* 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 (!NUMA_BUILD || 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, 0);
  	init_tracking(s, object);
  }
  
  static int alloc_debug_processing(struct kmem_cache *s, struct page *page,

  					void *object, unsigned long addr)

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

  	if (!on_freelist(s, page, object)) {

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

  		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, 0))

  		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, 1);

  	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 int free_debug_processing(struct kmem_cache *s, struct page *page,

  					void *object, unsigned long addr)

  {
  	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, 1))
  		return 0;
  
  	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;
  	}

  
  	/* Special debug activities for freeing objects */

  	if (!PageSlubFrozen(page) && !page->freelist)

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

  	return 1;

  fail:

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

  	return 0;
  }

  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, int active) { return 1; }

  static inline void add_full(struct kmem_cache_node *n, 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) {}

  #endif

  /*
   * 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 == -1)
  		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 |= 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)
  			return NULL;

  		stat(s, ORDER_FALLBACK);

  	}

  
  	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;
  	if (s->flags & (SLAB_DEBUG_FREE | SLAB_RED_ZONE | SLAB_POISON |
  			SLAB_STORE_USER | SLAB_TRACE))

  		__SetPageSlubDebug(page);

  
  	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;
  out:

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

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

  	if (unlikely(SLABDEBUG && PageSlubDebug(page))) {

  		void *p;
  
  		slab_pad_check(s, page);

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

  			check_object(s, page, p, 0);

  		__ClearPageSlubDebug(page);

  	}

  	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);

  }
  
  static void rcu_free_slab(struct rcu_head *h)
  {
  	struct page *page;
  
  	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)) {
  		/*
  		 * RCU free overloads the RCU head over the LRU
  		 */
  		struct rcu_head *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);
  }
  
  /*
   * 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);

  }
  
  static __always_inline int slab_trylock(struct page *page)
  {
  	int rc = 1;
  
  	rc = bit_spin_trylock(PG_locked, &page->flags);
  	return rc;
  }
  
  /*
   * Management of partially allocated slabs
   */

  static void add_partial(struct kmem_cache_node *n,
  				struct page *page, int tail)

  {

  	spin_lock(&n->list_lock);
  	n->nr_partial++;

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

  	spin_unlock(&n->list_lock);
  }

  static void remove_partial(struct kmem_cache *s, struct page *page)

  {
  	struct kmem_cache_node *n = get_node(s, page_to_nid(page));
  
  	spin_lock(&n->list_lock);
  	list_del(&page->lru);
  	n->nr_partial--;
  	spin_unlock(&n->list_lock);
  }
  
  /*

   * Lock slab and remove from the partial list.

   *

   * Must hold list_lock.

   */

  static inline int lock_and_freeze_slab(struct kmem_cache_node *n,
  							struct page *page)

  {
  	if (slab_trylock(page)) {
  		list_del(&page->lru);
  		n->nr_partial--;

  		__SetPageSlubFrozen(page);

  		return 1;
  	}
  	return 0;
  }
  
  /*

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

   */
  static struct page *get_partial_node(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 (lock_and_freeze_slab(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(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 == -1) ? numa_node_id() : node;
  
  	page = get_partial_node(get_node(s, searchnode));
  	if (page || (flags & __GFP_THISNODE))
  		return page;
  
  	return get_any_partial(s, flags);
  }
  
  /*
   * Move a page back to the lists.
   *
   * Must be called with the slab lock held.
   *
   * On exit the slab lock will have been dropped.
   */

  static void unfreeze_slab(struct kmem_cache *s, struct page *page, int tail)

  {

  	struct kmem_cache_node *n = get_node(s, page_to_nid(page));

  	__ClearPageSlubFrozen(page);

  	if (page->inuse) {

  		if (page->freelist) {

  			add_partial(n, page, tail);

  			stat(s, tail ? DEACTIVATE_TO_TAIL : DEACTIVATE_TO_HEAD);

  		} else {

  			stat(s, DEACTIVATE_FULL);

  			if (SLABDEBUG && PageSlubDebug(page) &&
  						(s->flags & SLAB_STORE_USER))

  				add_full(n, page);
  		}

  		slab_unlock(page);
  	} else {

  		stat(s, DEACTIVATE_EMPTY);

  		if (n->nr_partial < s->min_partial) {

  			/*

  			 * Adding an empty slab to the partial slabs in order
  			 * to avoid page allocator overhead. This slab needs
  			 * to come after the other slabs with objects in

  			 * so that the others get filled first. That way the
  			 * size of the partial list stays small.
  			 *

  			 * kmem_cache_shrink can reclaim any empty slabs from
  			 * the partial list.

  			 */

  			add_partial(n, page, 1);

  			slab_unlock(page);
  		} else {
  			slab_unlock(page);

  			stat(s, FREE_SLAB);

  			discard_slab(s, page);
  		}

  	}
  }
  
  /*
   * Remove the cpu slab
   */

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

  {

  	struct page *page = c->page;

  	int tail = 1;

  	if (page->freelist)

  		stat(s, DEACTIVATE_REMOTE_FREES);

  	/*

  	 * Merge cpu freelist into slab freelist. Typically we get here

  	 * because both freelists are empty. So this is unlikely
  	 * to occur.
  	 */

  	while (unlikely(c->freelist)) {

  		void **object;

  		tail = 0;	/* Hot objects. Put the slab first */

  		/* Retrieve object from cpu_freelist */

  		object = c->freelist;

  		c->freelist = get_freepointer(s, c->freelist);

  
  		/* And put onto the regular freelist */

  		set_freepointer(s, object, page->freelist);

  		page->freelist = object;
  		page->inuse--;
  	}

  	c->page = NULL;

  	unfreeze_slab(s, page, tail);

  }

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

  {

  	stat(s, CPUSLAB_FLUSH);

  	slab_lock(c->page);
  	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 != -1 && 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);

  
  		printk(KERN_WARNING
  			"  node %d: slabs: %ld, objs: %ld, free: %ld
  ",
  			node, nr_slabs, nr_objs, nr_free);
  	}
  }

  /*

   * Slow path. The lockless freelist is empty or we need to perform
   * debugging duties.
   *
   * Interrupts are disabled.

   *

   * Processing is still very fast if new objects have been freed to the
   * regular freelist. In that case we simply take over the regular freelist
   * as the lockless freelist and zap the regular freelist.

   *

   * If that is not working then we fall back to the partial lists. We take the
   * first element of the freelist as the object to allocate now and move the
   * rest of the freelist to the lockless freelist.

   *

   * And if we were unable to get a new slab from the partial slab lists then

   * we need to allocate a new slab. This is the slowest path since it involves
   * a call to the page allocator and the setup of a new slab.

   */

  static void *__slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
  			  unsigned long addr, struct kmem_cache_cpu *c)

  {

  	void **object;

  	struct page *new;

  	/* We handle __GFP_ZERO in the caller */
  	gfpflags &= ~__GFP_ZERO;

  	if (!c->page)

  		goto new_slab;

  	slab_lock(c->page);
  	if (unlikely(!node_match(c, node)))

  		goto another_slab;

  	stat(s, ALLOC_REFILL);

  load_freelist:

  	object = c->page->freelist;

  	if (unlikely(!object))

  		goto another_slab;

  	if (unlikely(SLABDEBUG && PageSlubDebug(c->page)))

  		goto debug;

  	c->freelist = get_freepointer(s, object);

  	c->page->inuse = c->page->objects;

  	c->page->freelist = NULL;

  	c->node = page_to_nid(c->page);

  unlock_out:

  	slab_unlock(c->page);

  	stat(s, ALLOC_SLOWPATH);

  	return object;
  
  another_slab:

  	deactivate_slab(s, c);

  
  new_slab:

  	new = get_partial(s, gfpflags, node);
  	if (new) {
  		c->page = new;

  		stat(s, ALLOC_FROM_PARTIAL);

  		goto load_freelist;

  	}

  	if (gfpflags & __GFP_WAIT)
  		local_irq_enable();

  	new = new_slab(s, gfpflags, node);

  
  	if (gfpflags & __GFP_WAIT)
  		local_irq_disable();

  	if (new) {

  		c = __this_cpu_ptr(s->cpu_slab);

  		stat(s, ALLOC_SLAB);

  		if (c->page)

  			flush_slab(s, c);

  		slab_lock(new);

  		__SetPageSlubFrozen(new);

  		c->page = new;

  		goto load_freelist;

  	}

  	if (!(gfpflags & __GFP_NOWARN) && printk_ratelimit())
  		slab_out_of_memory(s, gfpflags, node);

  	return NULL;

  debug:

  	if (!alloc_debug_processing(s, c->page, object, addr))

  		goto another_slab;

  	c->page->inuse++;

  	c->page->freelist = get_freepointer(s, object);

  	c->node = -1;

  	goto unlock_out;

  }
  
  /*
   * Inlined fastpath so that allocation functions (kmalloc, kmem_cache_alloc)
   * have the fastpath folded into their functions. So no function call
   * overhead for requests that can be satisfied on the fastpath.
   *
   * The fastpath works by first checking if the lockless freelist can be used.
   * If not then __slab_alloc is called for slow processing.
   *
   * Otherwise we can simply pick the next object from the lockless free list.
   */

  static __always_inline void *slab_alloc(struct kmem_cache *s,

  		gfp_t gfpflags, int node, unsigned long addr)

  {

  	void **object;

  	struct kmem_cache_cpu *c;

  	unsigned long flags;

  	gfpflags &= gfp_allowed_mask;

  	lockdep_trace_alloc(gfpflags);

  	might_sleep_if(gfpflags & __GFP_WAIT);

  	if (should_failslab(s->objsize, gfpflags, s->flags))

  		return NULL;

  	local_irq_save(flags);

  	c = __this_cpu_ptr(s->cpu_slab);
  	object = c->freelist;

  	if (unlikely(!object || !node_match(c, node)))

  		object = __slab_alloc(s, gfpflags, node, addr, c);

  
  	else {

  		c->freelist = get_freepointer(s, object);

  		stat(s, ALLOC_FASTPATH);

  	}
  	local_irq_restore(flags);

  	if (unlikely(gfpflags & __GFP_ZERO) && object)

  		memset(object, 0, s->objsize);

  	kmemcheck_slab_alloc(s, gfpflags, object, s->objsize);
  	kmemleak_alloc_recursive(object, s->objsize, 1, s->flags, gfpflags);

  	return object;

  }
  
  void *kmem_cache_alloc(struct kmem_cache *s, gfp_t gfpflags)
  {

  	void *ret = slab_alloc(s, gfpflags, -1, _RET_IP_);

  	trace_kmem_cache_alloc(_RET_IP_, ret, s->objsize, s->size, gfpflags);

  
  	return ret;

  }
  EXPORT_SYMBOL(kmem_cache_alloc);

  #ifdef CONFIG_TRACING

  void *kmem_cache_alloc_notrace(struct kmem_cache *s, gfp_t gfpflags)
  {
  	return slab_alloc(s, gfpflags, -1, _RET_IP_);
  }
  EXPORT_SYMBOL(kmem_cache_alloc_notrace);
  #endif

  #ifdef CONFIG_NUMA
  void *kmem_cache_alloc_node(struct kmem_cache *s, gfp_t gfpflags, int node)
  {

  	void *ret = slab_alloc(s, gfpflags, node, _RET_IP_);

  	trace_kmem_cache_alloc_node(_RET_IP_, ret,
  				    s->objsize, s->size, gfpflags, node);

  
  	return ret;

  }
  EXPORT_SYMBOL(kmem_cache_alloc_node);
  #endif

  #ifdef CONFIG_TRACING

  void *kmem_cache_alloc_node_notrace(struct kmem_cache *s,
  				    gfp_t gfpflags,
  				    int node)
  {
  	return slab_alloc(s, gfpflags, node, _RET_IP_);
  }
  EXPORT_SYMBOL(kmem_cache_alloc_node_notrace);
  #endif

  /*

   * Slow patch handling. This may still be called frequently since objects
   * have a longer lifetime than the cpu slabs in most processing loads.

   *

   * So we still attempt to reduce cache line usage. Just take the slab
   * lock and free the item. If there is no additional partial page
   * handling required then we can return immediately.

   */

  static void __slab_free(struct kmem_cache *s, struct page *page,

  			void *x, unsigned long addr)

  {
  	void *prior;
  	void **object = (void *)x;