/* * 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 #include /* struct reclaim_state */ #include #include #include #include #include #include "slab.h" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include "internal.h" /* * Lock order: * 1. slab_mutex (Global Mutex) * 2. node->list_lock * 3. slab_lock(page) (Only on some arches and for debugging) * * slab_mutex * * The role of the slab_mutex 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. */ 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 } static inline bool kmem_cache_has_cpu_partial(struct kmem_cache *s) { #ifdef CONFIG_SLUB_CPU_PARTIAL return !kmem_cache_debug(s); #else return false; #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 use. */ #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 */ #ifdef CONFIG_SMP static struct notifier_block slab_notifier; #endif /* * 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 *); static void memcg_propagate_slab_attrs(struct kmem_cache *s); #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) { } static inline void memcg_propagate_slab_attrs(struct kmem_cache *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 *******************************************************************/ 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 void prefetch_freepointer(const struct kmem_cache *s, void *object) { prefetch(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->object_size; #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); } static inline void set_page_slub_counters(struct page *page, unsigned long counters_new) { struct page tmp; tmp.counters = counters_new; /* * page->counters can cover frozen/inuse/objects as well * as page->_count. If we assign to ->counters directly * we run the risk of losing updates to page->_count, so * be careful and only assign to the fields we need. */ page->frozen = tmp.frozen; page->inuse = tmp.inuse; page->objects = tmp.objects; } /* 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()); #if defined(CONFIG_HAVE_CMPXCHG_DOUBLE) && \ defined(CONFIG_HAVE_ALIGNED_STRUCT_PAGE) if (s->flags & __CMPXCHG_DOUBLE) { if (cmpxchg_double(&page->freelist, &page->counters, 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; set_page_slub_counters(page, 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) { #if defined(CONFIG_HAVE_CMPXCHG_DOUBLE) && \ defined(CONFIG_HAVE_ALIGNED_STRUCT_PAGE) if (s->flags & __CMPXCHG_DOUBLE) { if (cmpxchg_double(&page->freelist, &page->counters, 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; set_page_slub_counters(page, 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) { print_hex_dump(KERN_ERR, text, DUMP_PREFIX_ADDRESS, 16, 1, addr, length, 1); } 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\n", 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\n", (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\n", 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 "========================================" "=====================================\n"); printk(KERN_ERR "BUG %s (%s): %s\n", s->name, print_tainted(), buf); printk(KERN_ERR "----------------------------------------" "-------------------------------------\n\n"); add_taint(TAINT_BAD_PAGE, LOCKDEP_NOW_UNRELIABLE); } 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\n", 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\n\n", 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->object_size, PAGE_SIZE)); if (s->flags & SLAB_RED_ZONE) print_section("Redzone ", p + s->object_size, s->inuse - s->object_size); 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, const 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->object_size - 1); p[s->object_size - 1] = POISON_END; } if (s->flags & SLAB_RED_ZONE) memset(p + s->object_size, val, s->inuse - s->object_size); } 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\n", 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 = memchr_inv(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\n", 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->object_size * Padding to reach word boundary. This is also used for Redzoning. * Padding is extended by another word if Redzoning is enabled and * object_size == 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 object_size 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 = memchr_inv(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->object_size; if (s->flags & SLAB_RED_ZONE) { if (!check_bytes_and_report(s, page, object, "Redzone", endobject, val, s->inuse - s->object_size)) return 0; } else { if ((s->flags & SLAB_POISON) && s->object_size < s->inuse) { check_bytes_and_report(s, page, p, "Alignment padding", endobject, POISON_INUSE, s->inuse - s->object_size); } } 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->object_size - 1) || !check_bytes_and_report(s, page, p, "Poison", p + s->object_size - 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); } 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\n", s->name, alloc ? "alloc" : "free", object, page->inuse, page->freelist); if (!alloc) print_section("Object ", (void *)object, s->object_size); 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 void kmalloc_large_node_hook(void *ptr, size_t size, gfp_t flags) { kmemleak_alloc(ptr, size, 1, flags); } static inline void kfree_hook(const void *x) { kmemleak_free(x); } 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->object_size, 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->object_size, 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 interrupts 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->object_size); debug_check_no_locks_freed(x, s->object_size); local_irq_restore(flags); } #endif if (!(s->flags & SLAB_DEBUG_OBJECTS)) debug_check_no_obj_freed(x, s->object_size); } /* * Tracking of fully allocated slabs for debugging purposes. */ static void add_full(struct kmem_cache *s, struct kmem_cache_node *n, struct page *page) { if (!(s->flags & SLAB_STORE_USER)) return; lockdep_assert_held(&n->list_lock); list_add(&page->lru, &n->full); } static void remove_full(struct kmem_cache *s, struct kmem_cache_node *n, struct page *page) { if (!(s->flags & SLAB_STORE_USER)) return; lockdep_assert_held(&n->list_lock); 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 (likely(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 struct kmem_cache_node *free_debug_processing( struct kmem_cache *s, struct page *page, void *object, unsigned long addr, unsigned long *flags) { struct kmem_cache_node *n = get_node(s, page_to_nid(page)); spin_lock_irqsave(&n->list_lock, *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_cache)) { if (!PageSlab(page)) { slab_err(s, page, "Attempt to free object(0x%p) " "outside of slab", object); } else if (!page->slab_cache) { printk(KERN_ERR "SLUB : no slab for object 0x%p.\n", 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); out: slab_unlock(page); /* * Keep node_lock to preserve integrity * until the object is actually freed */ return n; fail: slab_unlock(page); spin_unlock_irqrestore(&n->list_lock, *flags); slab_fix(s, "Object at 0x%p not freed", object); return NULL; } 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\n", *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 object_size, unsigned long flags, const char *name, void (*ctor)(void *)) { /* * Enable debugging if selected on the kernel commandline. */ if (slub_debug && (!slub_debug_slabs || (name && !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 struct kmem_cache_node *free_debug_processing( struct kmem_cache *s, struct page *page, void *object, unsigned long addr, unsigned long *flags) { return NULL; } 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 kmem_cache_node *n, struct page *page) {} static inline unsigned long kmem_cache_flags(unsigned long object_size, 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 void kmalloc_large_node_hook(void *ptr, size_t size, gfp_t flags) { kmemleak_alloc(ptr, size, 1, flags); } static inline void kfree_hook(const void *x) { kmemleak_free(x); } 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) { kmemleak_alloc_recursive(object, s->object_size, 1, s->flags, flags & gfp_allowed_mask); } static inline void slab_free_hook(struct kmem_cache *s, void *x) { kmemleak_free_recursive(x, s->flags); } #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 (kmemcheck_enabled && page && !(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); } if (flags & __GFP_WAIT) local_irq_disable(); if (!page) return NULL; 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; int order; BUG_ON(flags & GFP_SLAB_BUG_MASK); page = allocate_slab(s, flags & (GFP_RECLAIM_MASK | GFP_CONSTRAINT_MASK), node); if (!page) goto out; order = compound_order(page); inc_slabs_node(s, page_to_nid(page), page->objects); memcg_bind_pages(s, order); page->slab_cache = s; __SetPageSlab(page); if (page->pfmemalloc) SetPageSlabPfmemalloc(page); start = page_address(page); if (unlikely(s->flags & SLAB_POISON)) memset(start, POISON_INUSE, PAGE_SIZE << order); 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 = page->objects; 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); __ClearPageSlabPfmemalloc(page); __ClearPageSlab(page); memcg_release_pages(s, order); page_mapcount_reset(page); if (current->reclaim_state) current->reclaim_state->reclaimed_slab += pages; __free_memcg_kmem_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_cache, 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. */ static inline void __add_partial(struct kmem_cache_node *n, struct page *page, int tail) { n->nr_partial++; if (tail == DEACTIVATE_TO_TAIL) list_add_tail(&page->lru, &n->partial); else list_add(&page->lru, &n->partial); } static inline void add_partial(struct kmem_cache_node *n, struct page *page, int tail) { lockdep_assert_held(&n->list_lock); __add_partial(n, page, tail); } static inline void __remove_partial(struct kmem_cache_node *n, struct page *page) { list_del(&page->lru); n->nr_partial--; } static inline void remove_partial(struct kmem_cache_node *n, struct page *page) { lockdep_assert_held(&n->list_lock); __remove_partial(n, page); } /* * Remove slab from the partial list, freeze it and * return the pointer to the freelist. * * Returns a list of objects or NULL if it fails. */ static inline void *acquire_slab(struct kmem_cache *s, struct kmem_cache_node *n, struct page *page, int mode, int *objects) { void *freelist; unsigned long counters; struct page new; lockdep_assert_held(&n->list_lock); /* * Zap the freelist and set the frozen bit. * The old freelist is the list of objects for the * per cpu allocation list. */ freelist = page->freelist; counters = page->counters; new.counters = counters; *objects = new.objects - new.inuse; if (mode) { new.inuse = page->objects; new.freelist = NULL; } else { new.freelist = freelist; } VM_BUG_ON(new.frozen); new.frozen = 1; if (!__cmpxchg_double_slab(s, page, freelist, counters, new.freelist, new.counters, "acquire_slab")) return NULL; remove_partial(n, page); WARN_ON(!freelist); return freelist; } static void put_cpu_partial(struct kmem_cache *s, struct page *page, int drain); static inline bool pfmemalloc_match(struct page *page, gfp_t gfpflags); /* * Try to allocate a partial slab from a specific node. */ static void *get_partial_node(struct kmem_cache *s, struct kmem_cache_node *n, struct kmem_cache_cpu *c, gfp_t flags) { struct page *page, *page2; void *object = NULL; int available = 0; int objects; /* * 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_safe(page, page2, &n->partial, lru) { void *t; if (!pfmemalloc_match(page, flags)) continue; t = acquire_slab(s, n, page, object == NULL, &objects); if (!t) break; available += objects; if (!object) { c->page = page; stat(s, ALLOC_FROM_PARTIAL); object = t; } else { put_cpu_partial(s, page, 0); stat(s, CPU_PARTIAL_NODE); } if (!kmem_cache_has_cpu_partial(s) || available > s->cpu_partial / 2) break; } spin_unlock(&n->list_lock); return object; } /* * Get a page from somewhere. Search in increasing NUMA distances. */ static void *get_any_partial(struct kmem_cache *s, gfp_t flags, struct kmem_cache_cpu *c) { #ifdef CONFIG_NUMA struct zonelist *zonelist; struct zoneref *z; struct zone *zone; enum zone_type high_zoneidx = gfp_zone(flags); void *object; unsigned int cpuset_mems_cookie; /* * 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; do { cpuset_mems_cookie = get_mems_allowed(); zonelist = node_zonelist(slab_node(), 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) { object = get_partial_node(s, n, c, flags); if (object) { /* * Return the object even if * put_mems_allowed indicated that * the cpuset mems_allowed was * updated in parallel. It's a * harmless race between the alloc * and the cpuset update. */ put_mems_allowed(cpuset_mems_cookie); return object; } } } } while (!put_mems_allowed(cpuset_mems_cookie)); #endif return NULL; } /* * Get a partial page, lock it and return it. */ static void *get_partial(struct kmem_cache *s, gfp_t flags, int node, struct kmem_cache_cpu *c) { void *object; int searchnode = (node == NUMA_NO_NODE) ? numa_node_id() : node; object = get_partial_node(s, get_node(s, searchnode), c, flags); if (object || node != NUMA_NO_NODE) return object; return get_any_partial(s, flags, c); } #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\n", 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\n", tid_to_event(tid), tid_to_event(actual_tid)); else printk("for unknown reason: actual=%lx was=%lx target=%lx\n", actual_tid, tid, next_tid(tid)); #endif stat(s, CMPXCHG_DOUBLE_CPU_FAIL); } static 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 */ static void deactivate_slab(struct kmem_cache *s, struct page *page, void *freelist) { enum slab_modes { M_NONE, M_PARTIAL, M_FULL, M_FREE }; 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 *nextfree; int tail = DEACTIVATE_TO_HEAD; struct page new; struct page old; if (page->freelist) { stat(s, DEACTIVATE_REMOTE_FREES); tail = DEACTIVATE_TO_TAIL; } /* * 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, n, page); if (m == M_PARTIAL) { add_partial(n, page, tail); stat(s, tail); } 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); } } /* * Unfreeze all the cpu partial slabs. * * This function must be called with interrupts disabled * for the cpu using c (or some other guarantee must be there * to guarantee no concurrent accesses). */ static void unfreeze_partials(struct kmem_cache *s, struct kmem_cache_cpu *c) { #ifdef CONFIG_SLUB_CPU_PARTIAL struct kmem_cache_node *n = NULL, *n2 = NULL; struct page *page, *discard_page = NULL; while ((page = c->partial)) { struct page new; struct page old; c->partial = page->next; n2 = get_node(s, page_to_nid(page)); if (n != n2) { if (n) spin_unlock(&n->list_lock); n = n2; spin_lock(&n->list_lock); } do { old.freelist = page->freelist; old.counters = page->counters; VM_BUG_ON(!old.frozen); new.counters = old.counters; new.freelist = old.freelist; new.frozen = 0; } while (!__cmpxchg_double_slab(s, page, old.freelist, old.counters, new.freelist, new.counters, "unfreezing slab")); if (unlikely(!new.inuse && n->nr_partial > s->min_partial)) { page->next = discard_page; discard_page = page; } else { add_partial(n, page, DEACTIVATE_TO_TAIL); stat(s, FREE_ADD_PARTIAL); } } if (n) spin_unlock(&n->list_lock); while (discard_page) { page = discard_page; discard_page = discard_page->next; stat(s, DEACTIVATE_EMPTY); discard_slab(s, page); stat(s, FREE_SLAB); } #endif } /* * Put a page that was just frozen (in __slab_free) into a partial page * slot if available. This is done without interrupts disabled and without * preemption disabled. The cmpxchg is racy and may put the partial page * onto a random cpus partial slot. * * If we did not find a slot then simply move all the partials to the * per node partial list. */ static void put_cpu_partial(struct kmem_cache *s, struct page *page, int drain) { #ifdef CONFIG_SLUB_CPU_PARTIAL struct page *oldpage; int pages; int pobjects; do { pages = 0; pobjects = 0; oldpage = this_cpu_read(s->cpu_slab->partial); if (oldpage) { pobjects = oldpage->pobjects; pages = oldpage->pages; if (drain && pobjects > s->cpu_partial) { unsigned long flags; /* * partial array is full. Move the existing * set to the per node partial list. */ local_irq_save(flags); unfreeze_partials(s, this_cpu_ptr(s->cpu_slab)); local_irq_restore(flags); oldpage = NULL; pobjects = 0; pages = 0; stat(s, CPU_PARTIAL_DRAIN); } } pages++; pobjects += page->objects - page->inuse; page->pages = pages; page->pobjects = pobjects; page->next = oldpage; } while (this_cpu_cmpxchg(s->cpu_slab->partial, oldpage, page) != oldpage); #endif } static inline void flush_slab(struct kmem_cache *s, struct kmem_cache_cpu *c) { stat(s, CPUSLAB_FLUSH); deactivate_slab(s, c->page, c->freelist); c->tid = next_tid(c->tid); c->page = NULL; c->freelist = NULL; } /* * 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)) { if (c->page) flush_slab(s, c); unfreeze_partials(s, c); } } static void flush_cpu_slab(void *d) { struct kmem_cache *s = d; __flush_cpu_slab(s, smp_processor_id()); } static bool has_cpu_slab(int cpu, void *info) { struct kmem_cache *s = info; struct kmem_cache_cpu *c = per_cpu_ptr(s->cpu_slab, cpu); return c->page || c->partial; } static void flush_all(struct kmem_cache *s) { on_each_cpu_cond(has_cpu_slab, flush_cpu_slab, s, 1, GFP_ATOMIC); } /* * Check if the objects in a per cpu structure fit numa * locality expectations. */ static inline int node_match(struct page *page, int node) { #ifdef CONFIG_NUMA if (!page || (node != NUMA_NO_NODE && page_to_nid(page) != 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)\n", nid, gfpflags); printk(KERN_WARNING " cache: %s, object size: %d, buffer size: %d, " "default order: %d, min order: %d\n", s->name, s->object_size, s->size, oo_order(s->oo), oo_order(s->min)); if (oo_order(s->min) > get_order(s->object_size)) printk(KERN_WARNING " %s debugging increased min order, use " "slub_debug=O to disable.\n", 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\n", node, nr_slabs, nr_objs, nr_free); } } static inline void *new_slab_objects(struct kmem_cache *s, gfp_t flags, int node, struct kmem_cache_cpu **pc) { void *freelist; struct kmem_cache_cpu *c = *pc; struct page *page; freelist = get_partial(s, flags, node, c); if (freelist) return freelist; page = new_slab(s, flags, node); if (page) { c = __this_cpu_ptr(s->cpu_slab); if (c->page) flush_slab(s, c); /* * No other reference to the page yet so we can * muck around with it freely without cmpxchg */ freelist = page->freelist; page->freelist = NULL; stat(s, ALLOC_SLAB); c->page = page; *pc = c; } else freelist = NULL; return freelist; } static inline bool pfmemalloc_match(struct page *page, gfp_t gfpflags) { if (unlikely(PageSlabPfmemalloc(page))) return gfp_pfmemalloc_allowed(gfpflags); return true; } /* * Check the page->freelist of a page and either transfer the freelist to the * per cpu freelist or deactivate the page. * * The page is still frozen if the return value is not NULL. * * If this function returns NULL then the page has been unfrozen. * * This function must be called with interrupt disabled. */ static inline void *get_freelist(struct kmem_cache *s, struct page *page) { struct page new; unsigned long counters; void *freelist; do { freelist = page->freelist; counters = page->counters; new.counters = counters; VM_BUG_ON(!new.frozen); new.inuse = page->objects; new.frozen = freelist != NULL; } while (!__cmpxchg_double_slab(s, page, freelist, counters, NULL, new.counters, "get_freelist")); return freelist; } /* * Slow path. The lockless freelist is empty or we need to perform * debugging duties. * * 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 *freelist; struct page *page; unsigned long flags; local_irq_save(flags); #ifdef CONFIG_PREEMPT /* * We may have been preempted and rescheduled on a different * cpu before disabling interrupts. Need to reload cpu area * pointer. */ c = this_cpu_ptr(s->cpu_slab); #endif page = c->page; if (!page) goto new_slab; redo: if (unlikely(!node_match(page, node))) { stat(s, ALLOC_NODE_MISMATCH); deactivate_slab(s, page, c->freelist); c->page = NULL; c->freelist = NULL; goto new_slab; } /* * By rights, we should be searching for a slab page that was * PFMEMALLOC but right now, we are losing the pfmemalloc * information when the page leaves the per-cpu allocator */ if (unlikely(!pfmemalloc_match(page, gfpflags))) { deactivate_slab(s, page, c->freelist); c->page = NULL; c->freelist = NULL; goto new_slab; } /* must check again c->freelist in case of cpu migration or IRQ */ freelist = c->freelist; if (freelist) goto load_freelist; stat(s, ALLOC_SLOWPATH); freelist = get_freelist(s, page); if (!freelist) { c->page = NULL; stat(s, DEACTIVATE_BYPASS); goto new_slab; } stat(s, ALLOC_REFILL); load_freelist: /* * freelist is pointing to the list of objects to be used. * page is pointing to the page from which the objects are obtained. * That page must be frozen for per cpu allocations to work. */ VM_BUG_ON(!c->page->frozen); c->freelist = get_freepointer(s, freelist); c->tid = next_tid(c->tid); local_irq_restore(flags); return freelist; new_slab: if (c->partial) { page = c->page = c->partial; c->partial = page->next; stat(s, CPU_PARTIAL_ALLOC); c->freelist = NULL; goto redo; } freelist = new_slab_objects(s, gfpflags, node, &c); if (unlikely(!freelist)) { if (!(gfpflags & __GFP_NOWARN) && printk_ratelimit()) slab_out_of_memory(s, gfpflags, node); local_irq_restore(flags); return NULL; } page = c->page; if (likely(!kmem_cache_debug(s) && pfmemalloc_match(page, gfpflags))) goto load_freelist; /* Only entered in the debug case */ if (kmem_cache_debug(s) && !alloc_debug_processing(s, page, freelist, addr)) goto new_slab; /* Slab failed checks. Next slab needed */ deactivate_slab(s, page, get_freepointer(s, freelist)); c->page = NULL; c->freelist = NULL; local_irq_restore(flags); return freelist; } /* * 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_node(struct kmem_cache *s, gfp_t gfpflags, int node, unsigned long addr) { void **object; struct kmem_cache_cpu *c; struct page *page; unsigned long tid; if (slab_pre_alloc_hook(s, gfpflags)) return NULL; s = memcg_kmem_get_cache(s, gfpflags); redo: /* * Must read kmem_cache cpu data via this cpu ptr. Preemption is * enabled. We may switch back and forth between cpus while * reading from one cpu area. That does not matter as long * as we end up on the original cpu again when doing the cmpxchg. * * Preemption is disabled for the retrieval of the tid because that * must occur from the current processor. We cannot allow rescheduling * on a different processor between the determination of the pointer * and the retrieval of the tid. */ preempt_disable(); c = __this_cpu_ptr(s->cpu_slab); /* * The transaction ids are globally unique per cpu and per operation on * a per cpu queue. Thus they can be guarantee that the cmpxchg_double * occurs on the right processor and that there was no operation on the * linked list in between. */ tid = c->tid; preempt_enable(); object = c->freelist; page = c->page; if (unlikely(!object || !node_match(page, node))) object = __slab_alloc(s, gfpflags, node, addr, c); else { void *next_object = get_freepointer_safe(s, object); /* * The cmpxchg will only match if there was no additional * operation and if we are on the right processor. * * The cmpxchg does the following atomically (without lock * semantics!) * 1. Relocate first pointer to the current per cpu area. * 2. Verify that tid and freelist have not been changed * 3. If they were not changed replace tid and freelist * * Since this is without lock semantics the protection is only * against code executing on this cpu *not* from access by * other cpus. */ if (unlikely(!this_cpu_cmpxchg_double( s->cpu_slab->freelist, s->cpu_slab->tid, object, tid, next_object, next_tid(tid)))) { note_cmpxchg_failure("slab_alloc", s, tid); goto redo; } prefetch_freepointer(s, next_object); stat(s, ALLOC_FASTPATH); } if (unlikely(gfpflags & __GFP_ZERO) && object) memset(object, 0, s->object_size); slab_post_alloc_hook(s, gfpflags, object); return object; } static __always_inline void *slab_alloc(struct kmem_cache *s, gfp_t gfpflags, unsigned long addr) { return slab_alloc_node(s, gfpflags, NUMA_NO_NODE, addr); } void *kmem_cache_alloc(struct kmem_cache *s, gfp_t gfpflags) { void *ret = slab_alloc(s, gfpflags, _RET_IP_); trace_kmem_cache_alloc(_RET_IP_, ret, s->object_size, s->size, gfpflags); return ret; } EXPORT_SYMBOL(kmem_cache_alloc); #ifdef CONFIG_TRACING void *kmem_cache_alloc_trace(struct kmem_cache *s, gfp_t gfpflags, size_t size) { void *ret = slab_alloc(s, gfpflags, _RET_IP_); trace_kmalloc(_RET_IP_, ret, size, s->size, gfpflags); return ret; } EXPORT_SYMBOL(kmem_cache_alloc_trace); #endif #ifdef CONFIG_NUMA void *kmem_cache_alloc_node(struct kmem_cache *s, gfp_t gfpflags, int node) { void *ret = slab_alloc_node(s, gfpflags, node, _RET_IP_); trace_kmem_cache_alloc_node(_RET_IP_, ret, s->object_size, s->size, gfpflags, node); return ret; } EXPORT_SYMBOL(kmem_cache_alloc_node); #ifdef CONFIG_TRACING void *kmem_cache_alloc_node_trace(struct kmem_cache *s, gfp_t gfpflags, int node, size_t size) { void *ret = slab_alloc_node(s, gfpflags, node, _RET_IP_); trace_kmalloc_node(_RET_IP_, ret, size, s->size, gfpflags, node); return ret; } EXPORT_SYMBOL(kmem_cache_alloc_node_trace); #endif #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; int was_frozen; struct page new; unsigned long counters; struct kmem_cache_node *n = NULL; unsigned long uninitialized_var(flags); stat(s, FREE_SLOWPATH); if (kmem_cache_debug(s) && !(n = free_debug_processing(s, page, x, addr, &flags))) return; do { if (unlikely(n)) { spin_unlock_irqrestore(&n->list_lock, flags); n = NULL; } prior = page->freelist; counters = page->counters; set_freepointer(s, object, prior); new.counters = counters; was_frozen = new.frozen; new.inuse--; if ((!new.inuse || !prior) && !was_frozen) { if (kmem_cache_has_cpu_partial(s) && !prior) { /* * Slab was on no list before and will be * partially empty * We can defer the list move and instead * freeze it. */ new.frozen = 1; } else { /* Needs to be taken off a list */ n = get_node(s, page_to_nid(page)); /* * Speculatively acquire the list_lock. * If the cmpxchg does not succeed then we may * drop the list_lo