mm/slab.c

   1 /*
   2  * linux/mm/slab.c
   3  * Written by Mark Hemment, 1996/97.
   4  * (markhe@nextd.demon.co.uk)
   5  *
   6  * kmem_cache_destroy() + some cleanup - 1999 Andrea Arcangeli
   7  *
   8  * Major cleanup, different bufctl logic, per-cpu arrays
   9  *      (c) 2000 Manfred Spraul
  10  *
  11  * Cleanup, make the head arrays unconditional, preparation for NUMA
  12  *      (c) 2002 Manfred Spraul
  13  *
  14  * An implementation of the Slab Allocator as described in outline in;
  15  *      UNIX Internals: The New Frontiers by Uresh Vahalia
  16  *      Pub: Prentice Hall      ISBN 0-13-101908-2
  17  * or with a little more detail in;
  18  *      The Slab Allocator: An Object-Caching Kernel Memory Allocator
  19  *      Jeff Bonwick (Sun Microsystems).
  20  *      Presented at: USENIX Summer 1994 Technical Conference
  21  *
  22  * The memory is organized in caches, one cache for each object type.
  23  * (e.g. inode_cache, dentry_cache, buffer_head, vm_area_struct)
  24  * Each cache consists out of many slabs (they are small (usually one
  25  * page long) and always contiguous), and each slab contains multiple
  26  * initialized objects.
  27  *
  28  * This means, that your constructor is used only for newly allocated
  29  * slabs and you must pass objects with the same intializations to
  30  * kmem_cache_free.
  31  *
  32  * Each cache can only support one memory type (GFP_DMA, GFP_HIGHMEM,
  33  * normal). If you need a special memory type, then must create a new
  34  * cache for that memory type.
  35  *
  36  * In order to reduce fragmentation, the slabs are sorted in 3 groups:
  37  *   full slabs with 0 free objects
  38  *   partial slabs
  39  *   empty slabs with no allocated objects
  40  *
  41  * If partial slabs exist, then new allocations come from these slabs,
  42  * otherwise from empty slabs or new slabs are allocated.
  43  *
  44  * kmem_cache_destroy() CAN CRASH if you try to allocate from the cache
  45  * during kmem_cache_destroy(). The caller must prevent concurrent allocs.
  46  *
  47  * Each cache has a short per-cpu head array, most allocs
  48  * and frees go into that array, and if that array overflows, then 1/2
  49  * of the entries in the array are given back into the global cache.
  50  * The head array is strictly LIFO and should improve the cache hit rates.
  51  * On SMP, it additionally reduces the spinlock operations.
  52  *
  53  * The c_cpuarray may not be read with enabled local interrupts -
  54  * it's changed with a smp_call_function().
  55  *
  56  * SMP synchronization:
  57  *  constructors and destructors are called without any locking.
  58  *  Several members in kmem_cache_t and struct slab never change, they
  59  *      are accessed without any locking.
  60  *  The per-cpu arrays are never accessed from the wrong cpu, no locking,
  61  *      and local interrupts are disabled so slab code is preempt-safe.
  62  *  The non-constant members are protected with a per-cache irq spinlock.
  63  *
  64  * Many thanks to Mark Hemment, who wrote another per-cpu slab patch
  65  * in 2000 - many ideas in the current implementation are derived from
  66  * his patch.
  67  *
  68  * Further notes from the original documentation:
  69  *
  70  * 11 April '97.  Started multi-threading - markhe
  71  *      The global cache-chain is protected by the semaphore 'cache_chain_sem'.
  72  *      The sem is only needed when accessing/extending the cache-chain, which
  73  *      can never happen inside an interrupt (kmem_cache_create(),
  74  *      kmem_cache_shrink() and kmem_cache_reap()).
  75  *
  76  *      At present, each engine can be growing a cache.  This should be blocked.
  77  *
  78  */
  79
  80 #include        <linux/config.h>
  81 #include        <linux/slab.h>
  82 #include        <linux/mm.h>
  83 #include        <linux/swap.h>
  84 #include        <linux/cache.h>
  85 #include        <linux/interrupt.h>
  86 #include        <linux/init.h>
  87 #include        <linux/compiler.h>
  88 #include        <linux/seq_file.h>
  89 #include        <linux/notifier.h>
  90 #include        <linux/kallsyms.h>
  91 #include        <linux/cpu.h>
  92 #include        <linux/sysctl.h>
  93 #include        <linux/module.h>
  94
  95 #include        <asm/uaccess.h>
  96 #include        <asm/cacheflush.h>
  97 #include        <asm/tlbflush.h>
  98
  99 /*
 100  * DEBUG        - 1 for kmem_cache_create() to honour; SLAB_DEBUG_INITIAL,
 101  *                SLAB_RED_ZONE & SLAB_POISON.
 102  *                0 for faster, smaller code (especially in the critical paths).
 103  *
 104  * STATS        - 1 to collect stats for /proc/slabinfo.
 105  *                0 for faster, smaller code (especially in the critical paths).
 106  *
 107  * FORCED_DEBUG - 1 enables SLAB_RED_ZONE and SLAB_POISON (if possible)
 108  */
 109
 110 #ifdef CONFIG_DEBUG_SLAB
 111 #define DEBUG           1
 112 #define STATS           1
 113 #define FORCED_DEBUG    1
 114 #else
 115 #define DEBUG           0
 116 #define STATS           0
 117 #define FORCED_DEBUG    0
 118 #endif
 119
 120
 121 /* Shouldn't this be in a header file somewhere? */
 122 #define BYTES_PER_WORD          sizeof(void *)
 123
 124 #ifndef cache_line_size
 125 #define cache_line_size()       L1_CACHE_BYTES
 126 #endif
 127
 128 #ifndef ARCH_KMALLOC_MINALIGN
 129 #define ARCH_KMALLOC_MINALIGN 0
 130 #endif
 131
 132 #ifndef ARCH_KMALLOC_FLAGS
 133 #define ARCH_KMALLOC_FLAGS SLAB_HWCACHE_ALIGN
 134 #endif
 135
 136 /* Legal flag mask for kmem_cache_create(). */
 137 #if DEBUG
 138 # define CREATE_MASK    (SLAB_DEBUG_INITIAL | SLAB_RED_ZONE | \
 139                          SLAB_POISON | SLAB_HWCACHE_ALIGN | \
 140                          SLAB_NO_REAP | SLAB_CACHE_DMA | \
 141                          SLAB_MUST_HWCACHE_ALIGN | SLAB_STORE_USER | \
 142                          SLAB_RECLAIM_ACCOUNT | SLAB_PANIC)
 143 #else
 144 # define CREATE_MASK    (SLAB_HWCACHE_ALIGN | SLAB_NO_REAP | \
 145                          SLAB_CACHE_DMA | SLAB_MUST_HWCACHE_ALIGN | \
 146                          SLAB_RECLAIM_ACCOUNT | SLAB_PANIC)
 147 #endif
 148
 149 /*
 150  * kmem_bufctl_t:
 151  *
 152  * Bufctl's are used for linking objs within a slab
 153  * linked offsets.
 154  *
 155  * This implementation relies on "struct page" for locating the cache &
 156  * slab an object belongs to.
 157  * This allows the bufctl structure to be small (one int), but limits
 158  * the number of objects a slab (not a cache) can contain when off-slab
 159  * bufctls are used. The limit is the size of the largest general cache
 160  * that does not use off-slab slabs.
 161  * For 32bit archs with 4 kB pages, is this 56.
 162  * This is not serious, as it is only for large objects, when it is unwise
 163  * to have too many per slab.
 164  * Note: This limit can be raised by introducing a general cache whose size
 165  * is less than 512 (PAGE_SIZE<<3), but greater than 256.
 166  */
 167
 168 #define BUFCTL_END      (((kmem_bufctl_t)(~0U))-0)
 169 #define BUFCTL_FREE     (((kmem_bufctl_t)(~0U))-1)
 170 #define SLAB_LIMIT      (((kmem_bufctl_t)(~0U))-2)
 171
 172 /* Max number of objs-per-slab for caches which use off-slab slabs.
 173  * Needed to avoid a possible looping condition in cache_grow().
 174  */
 175 static unsigned long offslab_limit;
 176
 177 /*
 178  * struct slab
 179  *
 180  * Manages the objs in a slab. Placed either at the beginning of mem allocated
 181  * for a slab, or allocated from an general cache.
 182  * Slabs are chained into three list: fully used, partial, fully free slabs.
 183  */
 184 struct slab {
 185         struct list_head        list;
 186         unsigned long           colouroff;
 187         void                    *s_mem;         /* including colour offset */
 188         unsigned int            inuse;          /* num of objs active in slab */
 189         kmem_bufctl_t           free;
 190 };
 191
 192 /*
 193  * struct array_cache
 194  *
 195  * Per cpu structures
 196  * Purpose:
 197  * - LIFO ordering, to hand out cache-warm objects from _alloc
 198  * - reduce the number of linked list operations
 199  * - reduce spinlock operations
 200  *
 201  * The limit is stored in the per-cpu structure to reduce the data cache
 202  * footprint.
 203  *
 204  */
 205 struct array_cache {
 206         unsigned int avail;
 207         unsigned int limit;
 208         unsigned int batchcount;
 209         unsigned int touched;
 210 };
 211
 212 /* bootstrap: The caches do not work without cpuarrays anymore,
 213  * but the cpuarrays are allocated from the generic caches...
 214  */
 215 #define BOOT_CPUCACHE_ENTRIES   1
 216 struct arraycache_init {
 217         struct array_cache cache;
 218         void * entries[BOOT_CPUCACHE_ENTRIES];
 219 };
 220
 221 /*
 222  * The slab lists of all objects.
 223  * Hopefully reduce the internal fragmentation
 224  * NUMA: The spinlock could be moved from the kmem_cache_t
 225  * into this structure, too. Figure out what causes
 226  * fewer cross-node spinlock operations.
 227  */
 228 struct kmem_list3 {
 229         struct list_head        slabs_partial;  /* partial list first, better asm code */
 230         struct list_head        slabs_full;
 231         struct list_head        slabs_free;
 232         unsigned long   free_objects;
 233         int             free_touched;
 234         unsigned long   next_reap;
 235         struct array_cache      *shared;
 236 };
 237
 238 #define LIST3_INIT(parent) \
 239         { \
 240                 .slabs_full     = LIST_HEAD_INIT(parent.slabs_full), \
 241                 .slabs_partial  = LIST_HEAD_INIT(parent.slabs_partial), \
 242                 .slabs_free     = LIST_HEAD_INIT(parent.slabs_free) \
 243         }
 244 #define list3_data(cachep) \
 245         (&(cachep)->lists)
 246
 247 /* NUMA: per-node */
 248 #define list3_data_ptr(cachep, ptr) \
 249                 list3_data(cachep)
 250
 251 /*
 252  * kmem_cache_t
 253  *
 254  * manages a cache.
 255  */
 256
 257 struct kmem_cache_s {
 258 /* 1) per-cpu data, touched during every alloc/free */
 259         struct array_cache      *array[NR_CPUS];
 260         unsigned int            batchcount;
 261         unsigned int            limit;
 262 /* 2) touched by every alloc & free from the backend */
 263         struct kmem_list3       lists;
 264         /* NUMA: kmem_3list_t   *nodelists[MAX_NUMNODES] */
 265         unsigned int            objsize;
 266         unsigned int            flags;  /* constant flags */
 267         unsigned int            num;    /* # of objs per slab */
 268         unsigned int            free_limit; /* upper limit of objects in the lists */
 269         spinlock_t              spinlock;
 270
 271 /* 3) cache_grow/shrink */
 272         /* order of pgs per slab (2^n) */
 273         unsigned int            gfporder;
 274
 275         /* force GFP flags, e.g. GFP_DMA */
 276         unsigned int            gfpflags;
 277
 278         size_t                  colour;         /* cache colouring range */
 279         unsigned int            colour_off;     /* colour offset */
 280         unsigned int            colour_next;    /* cache colouring */
 281         kmem_cache_t            *slabp_cache;
 282         unsigned int            slab_size;
 283         unsigned int            dflags;         /* dynamic flags */
 284
 285         /* constructor func */
 286         void (*ctor)(void *, kmem_cache_t *, unsigned long);
 287
 288         /* de-constructor func */
 289         void (*dtor)(void *, kmem_cache_t *, unsigned long);
 290
 291 /* 4) cache creation/removal */
 292         const char              *name;
 293         struct list_head        next;
 294
 295 /* 5) statistics */
 296 #if STATS
 297         unsigned long           num_active;
 298         unsigned long           num_allocations;
 299         unsigned long           high_mark;
 300         unsigned long           grown;
 301         unsigned long           reaped;
 302         unsigned long           errors;
 303         unsigned long           max_freeable;
 304         atomic_t                allochit;
 305         atomic_t                allocmiss;
 306         atomic_t                freehit;
 307         atomic_t                freemiss;
 308 #endif
 309 #if DEBUG
 310         int                     dbghead;
 311         int                     reallen;
 312 #endif
 313 };
 314
 315 #define CFLGS_OFF_SLAB          (0x80000000UL)
 316 #define OFF_SLAB(x)     ((x)->flags & CFLGS_OFF_SLAB)
 317
 318 #define BATCHREFILL_LIMIT       16
 319 /* Optimization question: fewer reaps means less
 320  * probability for unnessary cpucache drain/refill cycles.
 321  *
 322  * OTHO the cpuarrays can contain lots of objects,
 323  * which could lock up otherwise freeable slabs.
 324  */
 325 #define REAPTIMEOUT_CPUC        (2*HZ)
 326 #define REAPTIMEOUT_LIST3       (4*HZ)
 327
 328 #if STATS
 329 #define STATS_INC_ACTIVE(x)     ((x)->num_active++)
 330 #define STATS_DEC_ACTIVE(x)     ((x)->num_active--)
 331 #define STATS_INC_ALLOCED(x)    ((x)->num_allocations++)
 332 #define STATS_INC_GROWN(x)      ((x)->grown++)
 333 #define STATS_INC_REAPED(x)     ((x)->reaped++)
 334 #define STATS_SET_HIGH(x)       do { if ((x)->num_active > (x)->high_mark) \
 335                                         (x)->high_mark = (x)->num_active; \
 336                                 } while (0)
 337 #define STATS_INC_ERR(x)        ((x)->errors++)
 338 #define STATS_SET_FREEABLE(x, i) \
 339                                 do { if ((x)->max_freeable < i) \
 340                                         (x)->max_freeable = i; \
 341                                 } while (0)
 342
 343 #define STATS_INC_ALLOCHIT(x)   atomic_inc(&(x)->allochit)
 344 #define STATS_INC_ALLOCMISS(x)  atomic_inc(&(x)->allocmiss)
 345 #define STATS_INC_FREEHIT(x)    atomic_inc(&(x)->freehit)
 346 #define STATS_INC_FREEMISS(x)   atomic_inc(&(x)->freemiss)
 347 #else
 348 #define STATS_INC_ACTIVE(x)     do { } while (0)
 349 #define STATS_DEC_ACTIVE(x)     do { } while (0)
 350 #define STATS_INC_ALLOCED(x)    do { } while (0)
 351 #define STATS_INC_GROWN(x)      do { } while (0)
 352 #define STATS_INC_REAPED(x)     do { } while (0)
 353 #define STATS_SET_HIGH(x)       do { } while (0)
 354 #define STATS_INC_ERR(x)        do { } while (0)
 355 #define STATS_SET_FREEABLE(x, i) \
 356                                 do { } while (0)
 357
 358 #define STATS_INC_ALLOCHIT(x)   do { } while (0)
 359 #define STATS_INC_ALLOCMISS(x)  do { } while (0)
 360 #define STATS_INC_FREEHIT(x)    do { } while (0)
 361 #define STATS_INC_FREEMISS(x)   do { } while (0)
 362 #endif
 363
 364 #if DEBUG
 365 /* Magic nums for obj red zoning.
 366  * Placed in the first word before and the first word after an obj.
 367  */
 368 #define RED_INACTIVE    0x5A2CF071UL    /* when obj is inactive */
 369 #define RED_ACTIVE      0x170FC2A5UL    /* when obj is active */
 370
 371 /* ...and for poisoning */
 372 #define POISON_INUSE    0x5a    /* for use-uninitialised poisoning */
 373 #define POISON_FREE     0x6b    /* for use-after-free poisoning */
 374 #define POISON_END      0xa5    /* end-byte of poisoning */
 375
 376 /* memory layout of objects:
 377  * 0            : objp
 378  * 0 .. cachep->dbghead - BYTES_PER_WORD - 1: padding. This ensures that
 379  *              the end of an object is aligned with the end of the real
 380  *              allocation. Catches writes behind the end of the allocation.
 381  * cachep->dbghead - BYTES_PER_WORD .. cachep->dbghead - 1:
 382  *              redzone word.
 383  * cachep->dbghead: The real object.
 384  * cachep->objsize - 2* BYTES_PER_WORD: redzone word [BYTES_PER_WORD long]
 385  * cachep->objsize - 1* BYTES_PER_WORD: last caller address [BYTES_PER_WORD long]
 386  */
 387 static int obj_dbghead(kmem_cache_t *cachep)
 388 {
 389         return cachep->dbghead;
 390 }
 391
 392 static int obj_reallen(kmem_cache_t *cachep)
 393 {
 394         return cachep->reallen;
 395 }
 396
 397 static unsigned long *dbg_redzone1(kmem_cache_t *cachep, void *objp)
 398 {
 399         BUG_ON(!(cachep->flags & SLAB_RED_ZONE));
 400         return (unsigned long*) (objp+obj_dbghead(cachep)-BYTES_PER_WORD);
 401 }
 402
 403 static unsigned long *dbg_redzone2(kmem_cache_t *cachep, void *objp)
 404 {
 405         BUG_ON(!(cachep->flags & SLAB_RED_ZONE));
 406         if (cachep->flags & SLAB_STORE_USER)
 407                 return (unsigned long*) (objp+cachep->objsize-2*BYTES_PER_WORD);
 408         return (unsigned long*) (objp+cachep->objsize-BYTES_PER_WORD);
 409 }
 410
 411 static void **dbg_userword(kmem_cache_t *cachep, void *objp)
 412 {
 413         BUG_ON(!(cachep->flags & SLAB_STORE_USER));
 414         return (void**)(objp+cachep->objsize-BYTES_PER_WORD);
 415 }
 416
 417 #else
 418
 419 #define obj_dbghead(x)                  0
 420 #define obj_reallen(cachep)             (cachep->objsize)
 421 #define dbg_redzone1(cachep, objp)      ({BUG(); (unsigned long *)NULL;})
 422 #define dbg_redzone2(cachep, objp)      ({BUG(); (unsigned long *)NULL;})
 423 #define dbg_userword(cachep, objp)      ({BUG(); (void **)NULL;})
 424
 425 #endif
 426
 427 /*
 428  * Maximum size of an obj (in 2^order pages)
 429  * and absolute limit for the gfp order.
 430  */
 431 #if defined(CONFIG_LARGE_ALLOCS)
 432 #define MAX_OBJ_ORDER   13      /* up to 32Mb */
 433 #define MAX_GFP_ORDER   13      /* up to 32Mb */
 434 #elif defined(CONFIG_MMU)
 435 #define MAX_OBJ_ORDER   5       /* 32 pages */
 436 #define MAX_GFP_ORDER   5       /* 32 pages */
 437 #else
 438 #define MAX_OBJ_ORDER   8       /* up to 1Mb */
 439 #define MAX_GFP_ORDER   8       /* up to 1Mb */
 440 #endif
 441
 442 /*
 443  * Do not go above this order unless 0 objects fit into the slab.
 444  */
 445 #define BREAK_GFP_ORDER_HI      1
 446 #define BREAK_GFP_ORDER_LO      0
 447 static int slab_break_gfp_order = BREAK_GFP_ORDER_LO;
 448
 449 /* Macros for storing/retrieving the cachep and or slab from the
 450  * global 'mem_map'. These are used to find the slab an obj belongs to.
 451  * With kfree(), these are used to find the cache which an obj belongs to.
 452  */
 453 #define SET_PAGE_CACHE(pg,x)  ((pg)->lru.next = (struct list_head *)(x))
 454 #define GET_PAGE_CACHE(pg)    ((kmem_cache_t *)(pg)->lru.next)
 455 #define SET_PAGE_SLAB(pg,x)   ((pg)->lru.prev = (struct list_head *)(x))
 456 #define GET_PAGE_SLAB(pg)     ((struct slab *)(pg)->lru.prev)
 457
 458 /* These are the default caches for kmalloc. Custom caches can have other sizes. */
 459 struct cache_sizes malloc_sizes[] = {
 460 #define CACHE(x) { .cs_size = (x) },
 461 #include <linux/kmalloc_sizes.h>
 462         { 0, }
 463 #undef CACHE
 464 };
 465
 466 EXPORT_SYMBOL(malloc_sizes);
 467
 468 /* Must match cache_sizes above. Out of line to keep cache footprint low. */
 469 struct cache_names {
 470         char *name;
 471         char *name_dma;
 472 };
 473
 474 static struct cache_names __initdata cache_names[] = {
 475 #define CACHE(x) { .name = "size-" #x, .name_dma = "size-" #x "(DMA)" },
 476 #include <linux/kmalloc_sizes.h>
 477         { NULL, }
 478 #undef CACHE
 479 };
 480
 481 struct arraycache_init initarray_cache __initdata = { { 0, BOOT_CPUCACHE_ENTRIES, 1, 0} };
 482 struct arraycache_init initarray_generic __initdata = { { 0, BOOT_CPUCACHE_ENTRIES, 1, 0} };
 483
 484 /* internal cache of cache description objs */
 485 static kmem_cache_t cache_cache = {
 486         .lists          = LIST3_INIT(cache_cache.lists),
 487         .batchcount     = 1,
 488         .limit          = BOOT_CPUCACHE_ENTRIES,
 489         .objsize        = sizeof(kmem_cache_t),
 490         .flags          = SLAB_NO_REAP,
 491         .spinlock       = SPIN_LOCK_UNLOCKED,
 492         .name           = "kmem_cache",
 493 #if DEBUG
 494         .reallen        = sizeof(kmem_cache_t),
 495 #endif
 496 };
 497
 498 /* Guard access to the cache-chain. */
 499 static struct semaphore cache_chain_sem;
 500
 501 struct list_head cache_chain;
 502
 503 /*
 504  * vm_enough_memory() looks at this to determine how many
 505  * slab-allocated pages are possibly freeable under pressure
 506  *
 507  * SLAB_RECLAIM_ACCOUNT turns this on per-slab
 508  */
 509 atomic_t slab_reclaim_pages;
 510 EXPORT_SYMBOL(slab_reclaim_pages);
 511
 512 /*
 513  * chicken and egg problem: delay the per-cpu array allocation
 514  * until the general caches are up.
 515  */
 516 enum {
 517         NONE,
 518         PARTIAL,
 519         FULL
 520 } g_cpucache_up;
 521
 522 static DEFINE_PER_CPU(struct timer_list, reap_timers);
 523
 524 static void reap_timer_fnc(unsigned long data);
 525 static void free_block(kmem_cache_t* cachep, void** objpp, int len);
 526 static void enable_cpucache (kmem_cache_t *cachep);
 527
 528 static inline void ** ac_entry(struct array_cache *ac)
 529 {
 530         return (void**)(ac+1);
 531 }
 532
 533 static inline struct array_cache *ac_data(kmem_cache_t *cachep)
 534 {
 535         return cachep->array[smp_processor_id()];
 536 }
 537
 538 /* Cal the num objs, wastage, and bytes left over for a given slab size. */
 539 static void cache_estimate (unsigned long gfporder, size_t size, size_t align,
 540                  int flags, size_t *left_over, unsigned int *num)
 541 {
 542         int i;
 543         size_t wastage = PAGE_SIZE<<gfporder;
 544         size_t extra = 0;
 545         size_t base = 0;
 546
 547         if (!(flags & CFLGS_OFF_SLAB)) {
 548                 base = sizeof(struct slab);
 549                 extra = sizeof(kmem_bufctl_t);
 550         }
 551         i = 0;
 552         while (i*size + ALIGN(base+i*extra, align) <= wastage)
 553                 i++;
 554         if (i > 0)
 555                 i--;
 556
 557         if (i > SLAB_LIMIT)
 558                 i = SLAB_LIMIT;
 559
 560         *num = i;
 561         wastage -= i*size;
 562         wastage -= ALIGN(base+i*extra, align);
 563         *left_over = wastage;
 564 }
 565
 566 #define slab_error(cachep, msg) __slab_error(__FUNCTION__, cachep, msg)
 567
 568 static void __slab_error(const char *function, kmem_cache_t *cachep, char *msg)
 569 {
 570         printk(KERN_ERR "slab error in %s(): cache `%s': %s\n",
 571                 function, cachep->name, msg);
 572         dump_stack();
 573 }
 574
 575 /*
 576  * Start the reap timer running on the target CPU.  We run at around 1 to 2Hz.
 577  * Add the CPU number into the expiry time to minimize the possibility of the
 578  * CPUs getting into lockstep and contending for the global cache chain lock.
 579  */
 580 static void __devinit start_cpu_timer(int cpu)
 581 {
 582         struct timer_list *rt = &per_cpu(reap_timers, cpu);
 583
 584         if (rt->function == NULL) {
 585                 init_timer(rt);
 586                 rt->expires = jiffies + HZ + 3*cpu;
 587                 rt->data = cpu;
 588                 rt->function = reap_timer_fnc;
 589                 add_timer_on(rt, cpu);
 590         }
 591 }
 592
 593 #ifdef CONFIG_HOTPLUG_CPU
 594 static void stop_cpu_timer(int cpu)
 595 {
 596         struct timer_list *rt = &per_cpu(reap_timers, cpu);
 597
 598         if (rt->function) {
 599                 del_timer_sync(rt);
 600                 WARN_ON(timer_pending(rt));
 601                 rt->function = NULL;
 602         }
 603 }
 604 #endif
 605
 606 static struct array_cache *alloc_arraycache(int cpu, int entries, int batchcount)
 607 {
 608         int memsize = sizeof(void*)*entries+sizeof(struct array_cache);
 609         struct array_cache *nc = NULL;
 610
 611         if (cpu != -1) {
 612                 nc = kmem_cache_alloc_node(kmem_find_general_cachep(memsize,
 613                                         GFP_KERNEL), cpu_to_node(cpu));
 614         }
 615         if (!nc)
 616                 nc = kmalloc(memsize, GFP_KERNEL);
 617         if (nc) {
 618                 nc->avail = 0;
 619                 nc->limit = entries;
 620                 nc->batchcount = batchcount;
 621                 nc->touched = 0;
 622         }
 623         return nc;
 624 }
 625
 626 static int __devinit cpuup_callback(struct notifier_block *nfb,
 627                                   unsigned long action,
 628                                   void *hcpu)
 629 {
 630         long cpu = (long)hcpu;
 631         kmem_cache_t* cachep;
 632
 633         switch (action) {
 634         case CPU_UP_PREPARE:
 635                 down(&cache_chain_sem);
 636                 list_for_each_entry(cachep, &cache_chain, next) {
 637                         struct array_cache *nc;
 638
 639                         nc = alloc_arraycache(cpu, cachep->limit, cachep->batchcount);
 640                         if (!nc)
 641                                 goto bad;
 642
 643                         spin_lock_irq(&cachep->spinlock);
 644                         cachep->array[cpu] = nc;
 645                         cachep->free_limit = (1+num_online_cpus())*cachep->batchcount
 646                                                 + cachep->num;
 647                         spin_unlock_irq(&cachep->spinlock);
 648
 649                 }
 650                 up(&cache_chain_sem);
 651                 break;
 652         case CPU_ONLINE:
 653                 start_cpu_timer(cpu);
 654                 break;
 655 #ifdef CONFIG_HOTPLUG_CPU
 656         case CPU_DEAD:
 657                 stop_cpu_timer(cpu);
 658                 /* fall thru */
 659         case CPU_UP_CANCELED:
 660                 down(&cache_chain_sem);
 661
 662                 list_for_each_entry(cachep, &cache_chain, next) {
 663                         struct array_cache *nc;
 664
 665                         spin_lock_irq(&cachep->spinlock);
 666                         /* cpu is dead; no one can alloc from it. */
 667                         nc = cachep->array[cpu];
 668                         cachep->array[cpu] = NULL;
 669                         cachep->free_limit -= cachep->batchcount;
 670                         free_block(cachep, ac_entry(nc), nc->avail);
 671                         spin_unlock_irq(&cachep->spinlock);
 672                         kfree(nc);
 673                 }
 674                 up(&cache_chain_sem);
 675                 break;
 676 #endif
 677         }
 678         return NOTIFY_OK;
 679 bad:
 680         up(&cache_chain_sem);
 681         return NOTIFY_BAD;
 682 }
 683
 684 static struct notifier_block cpucache_notifier = { &cpuup_callback, NULL, 0 };
 685
 686 /* Initialisation.
 687  * Called after the gfp() functions have been enabled, and before smp_init().
 688  */
 689 void __init kmem_cache_init(void)
 690 {
 691         size_t left_over;
 692         struct cache_sizes *sizes;
 693         struct cache_names *names;
 694
 695         /*
 696          * Fragmentation resistance on low memory - only use bigger
 697          * page orders on machines with more than 32MB of memory.
 698          */
 699         if (num_physpages > (32 << 20) >> PAGE_SHIFT)
 700                 slab_break_gfp_order = BREAK_GFP_ORDER_HI;
 701
 702
 703         /* Bootstrap is tricky, because several objects are allocated
 704          * from caches that do not exist yet:
 705          * 1) initialize the cache_cache cache: it contains the kmem_cache_t
 706          *    structures of all caches, except cache_cache itself: cache_cache
 707          *    is statically allocated.
 708          *    Initially an __init data area is used for the head array, it's
 709          *    replaced with a kmalloc allocated array at the end of the bootstrap.
 710          * 2) Create the first kmalloc cache.
 711          *    The kmem_cache_t for the new cache is allocated normally. An __init
 712          *    data area is used for the head array.
 713          * 3) Create the remaining kmalloc caches, with minimally sized head arrays.
 714          * 4) Replace the __init data head arrays for cache_cache and the first
 715          *    kmalloc cache with kmalloc allocated arrays.
 716          * 5) Resize the head arrays of the kmalloc caches to their final sizes.
 717          */
 718
 719         /* 1) create the cache_cache */
 720         init_MUTEX(&cache_chain_sem);
 721         INIT_LIST_HEAD(&cache_chain);
 722         list_add(&cache_cache.next, &cache_chain);
 723         cache_cache.colour_off = cache_line_size();
 724         cache_cache.array[smp_processor_id()] = &initarray_cache.cache;
 725
 726         cache_cache.objsize = ALIGN(cache_cache.objsize, cache_line_size());
 727
 728         cache_estimate(0, cache_cache.objsize, cache_line_size(), 0,
 729                                 &left_over, &cache_cache.num);
 730         if (!cache_cache.num)
 731                 BUG();
 732
 733         cache_cache.colour = left_over/cache_cache.colour_off;
 734         cache_cache.colour_next = 0;
 735         cache_cache.slab_size = ALIGN(cache_cache.num*sizeof(kmem_bufctl_t) +
 736                                 sizeof(struct slab), cache_line_size());
 737
 738         /* 2+3) create the kmalloc caches */
 739         sizes = malloc_sizes;
 740         names = cache_names;
 741
 742         while (sizes->cs_size) {
 743                 /* For performance, all the general caches are L1 aligned.
 744                  * This should be particularly beneficial on SMP boxes, as it
 745                  * eliminates "false sharing".
 746                  * Note for systems short on memory removing the alignment will
 747                  * allow tighter packing of the smaller caches. */
 748                 sizes->cs_cachep = kmem_cache_create(names->name,
 749                         sizes->cs_size, ARCH_KMALLOC_MINALIGN,
 750                         (ARCH_KMALLOC_FLAGS | SLAB_PANIC), NULL, NULL);
 751
 752                 /* Inc off-slab bufctl limit until the ceiling is hit. */
 753                 if (!(OFF_SLAB(sizes->cs_cachep))) {
 754                         offslab_limit = sizes->cs_size-sizeof(struct slab);
 755                         offslab_limit /= sizeof(kmem_bufctl_t);
 756                 }
 757
 758                 sizes->cs_dmacachep = kmem_cache_create(names->name_dma,
 759                         sizes->cs_size, ARCH_KMALLOC_MINALIGN,
 760                         (ARCH_KMALLOC_FLAGS | SLAB_CACHE_DMA | SLAB_PANIC),
 761                         NULL, NULL);
 762
 763                 sizes++;
 764                 names++;
 765         }
 766         /* 4) Replace the bootstrap head arrays */
 767         {
 768                 void * ptr;
 769
 770                 ptr = kmalloc(sizeof(struct arraycache_init), GFP_KERNEL);
 771                 local_irq_disable();
 772                 BUG_ON(ac_data(&cache_cache) != &initarray_cache.cache);
 773                 memcpy(ptr, ac_data(&cache_cache), sizeof(struct arraycache_init));
 774                 cache_cache.array[smp_processor_id()] = ptr;
 775                 local_irq_enable();
 776
 777                 ptr = kmalloc(sizeof(struct arraycache_init), GFP_KERNEL);
 778                 local_irq_disable();
 779                 BUG_ON(ac_data(malloc_sizes[0].cs_cachep) != &initarray_generic.cache);
 780                 memcpy(ptr, ac_data(malloc_sizes[0].cs_cachep),
 781                                 sizeof(struct arraycache_init));
 782                 malloc_sizes[0].cs_cachep->array[smp_processor_id()] = ptr;
 783                 local_irq_enable();
 784         }
 785
 786         /* 5) resize the head arrays to their final sizes */
 787         {
 788                 kmem_cache_t *cachep;
 789                 down(&cache_chain_sem);
 790                 list_for_each_entry(cachep, &cache_chain, next)
 791                         enable_cpucache(cachep);
 792                 up(&cache_chain_sem);
 793         }
 794
 795         /* Done! */
 796         g_cpucache_up = FULL;
 797
 798         /* Register a cpu startup notifier callback
 799          * that initializes ac_data for all new cpus
 800          */
 801         register_cpu_notifier(&cpucache_notifier);
 802
 803
 804         /* The reap timers are started later, with a module init call:
 805          * That part of the kernel is not yet operational.
 806          */
 807 }
 808
 809 int __init cpucache_init(void)
 810 {
 811         int cpu;
 812
 813         /*
 814          * Register the timers that return unneeded
 815          * pages to gfp.
 816          */
 817         for (cpu = 0; cpu < NR_CPUS; cpu++) {
 818                 if (cpu_online(cpu))
 819                         start_cpu_timer(cpu);
 820         }
 821
 822         return 0;
 823 }
 824
 825 __initcall(cpucache_init);
 826
 827 /*
 828  * Interface to system's page allocator. No need to hold the cache-lock.
 829  *
 830  * If we requested dmaable memory, we will get it. Even if we
 831  * did not request dmaable memory, we might get it, but that
 832  * would be relatively rare and ignorable.
 833  */
 834 static void *kmem_getpages(kmem_cache_t *cachep, int flags, int nodeid)
 835 {
 836         struct page *page;
 837         void *addr;
 838         int i;
 839
 840         flags |= cachep->gfpflags;
 841         if (likely(nodeid == -1)) {
 842                 addr = (void*)__get_free_pages(flags, cachep->gfporder);
 843                 if (!addr)
 844                         return NULL;
 845                 page = virt_to_page(addr);
 846         } else {
 847                 page = alloc_pages_node(nodeid, flags, cachep->gfporder);
 848                 if (!page)
 849                         return NULL;
 850                 addr = page_address(page);
 851         }
 852
 853         i = (1 << cachep->gfporder);
 854         if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
 855                 atomic_add(i, &slab_reclaim_pages);
 856         add_page_state(nr_slab, i);
 857         while (i--) {
 858                 SetPageSlab(page);
 859                 page++;
 860         }
 861         return addr;
 862 }
 863
 864 /*
 865  * Interface to system's page release.
 866  */
 867 static void kmem_freepages(kmem_cache_t *cachep, void *addr)
 868 {
 869         unsigned long i = (1<<cachep->gfporder);
 870         struct page *page = virt_to_page(addr);
 871         const unsigned long nr_freed = i;
 872
 873         while (i--) {
 874                 if (!TestClearPageSlab(page))
 875                         BUG();
 876                 page++;
 877         }
 878         sub_page_state(nr_slab, nr_freed);
 879         if (current->reclaim_state)
 880                 current->reclaim_state->reclaimed_slab += nr_freed;
 881         free_pages((unsigned long)addr, cachep->gfporder);
 882         if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
 883                 atomic_sub(1<<cachep->gfporder, &slab_reclaim_pages);
 884 }
 885
 886 #if DEBUG
 887
 888 #ifdef CONFIG_DEBUG_PAGEALLOC
 889 static void store_stackinfo(kmem_cache_t *cachep, unsigned long *addr, unsigned long caller)
 890 {
 891         int size = obj_reallen(cachep);
 892
 893         addr = (unsigned long *)&((char*)addr)[obj_dbghead(cachep)];
 894
 895         if (size < 5*sizeof(unsigned long))
 896                 return;
 897
 898         *addr++=0x12345678;
 899         *addr++=caller;
 900         *addr++=smp_processor_id();
 901         size -= 3*sizeof(unsigned long);
 902         {
 903                 unsigned long *sptr = &caller;
 904                 unsigned long svalue;
 905
 906                 while (!kstack_end(sptr)) {
 907                         svalue = *sptr++;
 908                         if (kernel_text_address(svalue)) {
 909                                 *addr++=svalue;
 910                                 size -= sizeof(unsigned long);
 911                                 if (size <= sizeof(unsigned long))
 912                                         break;
 913                         }
 914                 }
 915
 916         }
 917         *addr++=0x87654321;
 918 }
 919 #endif
 920
 921 static void poison_obj(kmem_cache_t *cachep, void *addr, unsigned char val)
 922 {
 923         int size = obj_reallen(cachep);
 924         addr = &((char*)addr)[obj_dbghead(cachep)];
 925
 926         memset(addr, val, size);
 927         *(unsigned char *)(addr+size-1) = POISON_END;
 928 }
 929
 930 static void dump_line(char *data, int offset, int limit)
 931 {
 932         int i;
 933         printk(KERN_ERR "%03x:", offset);
 934         for (i=0;i<limit;i++) {
 935                 printk(" %02x", (unsigned char)data[offset+i]);
 936         }
 937         printk("\n");
 938 }
 939 #endif
 940
 941 static void print_objinfo(kmem_cache_t *cachep, void *objp, int lines)
 942 {
 943 #if DEBUG
 944         int i, size;
 945         char *realobj;
 946
 947         if (cachep->flags & SLAB_RED_ZONE) {
 948                 printk(KERN_ERR "Redzone: 0x%lx/0x%lx.\n",
 949                         *dbg_redzone1(cachep, objp),
 950                         *dbg_redzone2(cachep, objp));
 951         }
 952
 953         if (cachep->flags & SLAB_STORE_USER) {
 954                 printk(KERN_ERR "Last user: [<%p>]", *dbg_userword(cachep, objp));
 955                 print_symbol("(%s)", (unsigned long)*dbg_userword(cachep, objp));
 956                 printk("\n");
 957         }
 958         realobj = (char*)objp+obj_dbghead(cachep);
 959         size = obj_reallen(cachep);
 960         for (i=0; i<size && lines;i+=16, lines--) {
 961                 int limit;
 962                 limit = 16;
 963                 if (i+limit > size)
 964                         limit = size-i;
 965                 dump_line(realobj, i, limit);
 966         }
 967 #endif
 968 }
 969
 970 #if DEBUG
 971
 972 static void check_poison_obj(kmem_cache_t *cachep, void *objp)
 973 {
 974         char *realobj;
 975         int size, i;
 976         int lines = 0;
 977
 978         realobj = (char*)objp+obj_dbghead(cachep);
 979         size = obj_reallen(cachep);
 980
 981         for (i=0;i<size;i++) {
 982                 char exp = POISON_FREE;
 983                 if (i == size-1)
 984                         exp = POISON_END;
 985                 if (realobj[i] != exp) {
 986                         int limit;
 987                         /* Mismatch ! */
 988                         /* Print header */
 989                         if (lines == 0) {
 990                                 printk(KERN_ERR "Slab corruption: start=%p, len=%d\n",
 991                                                 realobj, size);
 992                                 print_objinfo(cachep, objp, 0);
 993                         }
 994                         /* Hexdump the affected line */
 995                         i = (i/16)*16;
 996                         limit = 16;
 997                         if (i+limit > size)
 998                                 limit = size-i;
 999                         dump_line(realobj, i, limit);
1000                         i += 16;
1001                         lines++;
1002                         /* Limit to 5 lines */
1003                         if (lines > 5)
1004                                 break;
1005                 }
1006         }
1007         if (lines != 0) {
1008                 /* Print some data about the neighboring objects, if they
1009                  * exist:
1010                  */
1011                 struct slab *slabp = GET_PAGE_SLAB(virt_to_page(objp));
1012                 int objnr;
1013
1014                 objnr = (objp-slabp->s_mem)/cachep->objsize;
1015                 if (objnr) {
1016                         objp = slabp->s_mem+(objnr-1)*cachep->objsize;
1017                         realobj = (char*)objp+obj_dbghead(cachep);
1018                         printk(KERN_ERR "Prev obj: start=%p, len=%d\n",
1019                                                 realobj, size);
1020                         print_objinfo(cachep, objp, 2);
1021                 }
1022                 if (objnr+1 < cachep->num) {
1023                         objp = slabp->s_mem+(objnr+1)*cachep->objsize;
1024                         realobj = (char*)objp+obj_dbghead(cachep);
1025                         printk(KERN_ERR "Next obj: start=%p, len=%d\n",
1026                                                 realobj, size);
1027                         print_objinfo(cachep, objp, 2);
1028                 }
1029         }
1030 }
1031 #endif
1032
1033 /* Destroy all the objs in a slab, and release the mem back to the system.
1034  * Before calling the slab must have been unlinked from the cache.
1035  * The cache-lock is not held/needed.
1036  */
1037 static void slab_destroy (kmem_cache_t *cachep, struct slab *slabp)
1038 {
1039 #if DEBUG
1040         int i;
1041         for (i = 0; i < cachep->num; i++) {
1042                 void *objp = slabp->s_mem + cachep->objsize * i;
1043
1044                 if (cachep->flags & SLAB_POISON) {
1045 #ifdef CONFIG_DEBUG_PAGEALLOC
1046                         if ((cachep->objsize%PAGE_SIZE)==0 && OFF_SLAB(cachep))
1047                                 kernel_map_pages(virt_to_page(objp), cachep->objsize/PAGE_SIZE,1);
1048                         else
1049                                 check_poison_obj(cachep, objp);
1050 #else
1051                         check_poison_obj(cachep, objp);
1052 #endif
1053                 }
1054                 if (cachep->flags & SLAB_RED_ZONE) {
1055                         if (*dbg_redzone1(cachep, objp) != RED_INACTIVE)
1056                                 slab_error(cachep, "start of a freed object "
1057                                                         "was overwritten");
1058                         if (*dbg_redzone2(cachep, objp) != RED_INACTIVE)
1059                                 slab_error(cachep, "end of a freed object "
1060                                                         "was overwritten");
1061                 }
1062                 if (cachep->dtor && !(cachep->flags & SLAB_POISON))
1063                         (cachep->dtor)(objp+obj_dbghead(cachep), cachep, 0);
1064         }
1065 #else
1066         if (cachep->dtor) {
1067                 int i;
1068                 for (i = 0; i < cachep->num; i++) {
1069                         void* objp = slabp->s_mem+cachep->objsize*i;
1070                         (cachep->dtor)(objp, cachep, 0);
1071                 }
1072         }
1073 #endif
1074
1075         kmem_freepages(cachep, slabp->s_mem-slabp->colouroff);
1076         if (OFF_SLAB(cachep))
1077                 kmem_cache_free(cachep->slabp_cache, slabp);
1078 }
1079
1080 /**
1081  * kmem_cache_create - Create a cache.
1082  * @name: A string which is used in /proc/slabinfo to identify this cache.
1083  * @size: The size of objects to be created in this cache.
1084  * @align: The required alignment for the objects.
1085  * @flags: SLAB flags
1086  * @ctor: A constructor for the objects.
1087  * @dtor: A destructor for the objects.
1088  *
1089  * Returns a ptr to the cache on success, NULL on failure.
1090  * Cannot be called within a int, but can be interrupted.
1091  * The @ctor is run when new pages are allocated by the cache
1092  * and the @dtor is run before the pages are handed back.
1093  *
1094  * @name must be valid until the cache is destroyed. This implies that
1095  * the module calling this has to destroy the cache before getting
1096  * unloaded.
1097  *
1098  * The flags are
1099  *
1100  * %SLAB_POISON - Poison the slab with a known test pattern (a5a5a5a5)
1101  * to catch references to uninitialised memory.
1102  *
1103  * %SLAB_RED_ZONE - Insert `Red' zones around the allocated memory to check
1104  * for buffer overruns.
1105  *
1106  * %SLAB_NO_REAP - Don't automatically reap this cache when we're under
1107  * memory pressure.
1108  *
1109  * %SLAB_HWCACHE_ALIGN - Align the objects in this cache to a hardware
1110  * cacheline.  This can be beneficial if you're counting cycles as closely
1111  * as davem.
1112  */
1113 kmem_cache_t *
1114 kmem_cache_create (const char *name, size_t size, size_t align,
1115         unsigned long flags, void (*ctor)(void*, kmem_cache_t *, unsigned long),
1116         void (*dtor)(void*, kmem_cache_t *, unsigned long))
1117 {
1118         size_t left_over, slab_size;
1119         kmem_cache_t *cachep = NULL;
1120
1121         /*
1122          * Sanity checks... these are all serious usage bugs.
1123          */
1124         if ((!name) ||
1125                 in_interrupt() ||
1126                 (size < BYTES_PER_WORD) ||
1127                 (size > (1<<MAX_OBJ_ORDER)*PAGE_SIZE) ||
1128                 (dtor && !ctor)) {
1129                         printk(KERN_ERR "%s: Early error in slab %s\n",
1130                                         __FUNCTION__, name);
1131                         BUG();
1132                 }
1133
1134 #if DEBUG
1135         WARN_ON(strchr(name, ' '));     /* It confuses parsers */
1136         if ((flags & SLAB_DEBUG_INITIAL) && !ctor) {
1137                 /* No constructor, but inital state check requested */
1138                 printk(KERN_ERR "%s: No con, but init state check "
1139                                 "requested - %s\n", __FUNCTION__, name);
1140                 flags &= ~SLAB_DEBUG_INITIAL;
1141         }
1142
1143 #if FORCED_DEBUG
1144         /*
1145          * Enable redzoning and last user accounting, except for caches with
1146          * large objects, if the increased size would increase the object size
1147          * above the next power of two: caches with object sizes just above a
1148          * power of two have a significant amount of internal fragmentation.
1149          */
1150         if ((size < 4096 || fls(size-1) == fls(size-1+3*BYTES_PER_WORD)))
1151                 flags |= SLAB_RED_ZONE|SLAB_STORE_USER;
1152         flags |= SLAB_POISON;
1153 #endif
1154 #endif
1155         /*
1156          * Always checks flags, a caller might be expecting debug
1157          * support which isn't available.
1158          */
1159         if (flags & ~CREATE_MASK)
1160                 BUG();
1161
1162         if (align) {
1163                 /* combinations of forced alignment and advanced debugging is
1164                  * not yet implemented.
1165                  */
1166                 flags &= ~(SLAB_RED_ZONE|SLAB_STORE_USER);
1167         } else {
1168                 if (flags & SLAB_HWCACHE_ALIGN) {
1169                         /* Default alignment: as specified by the arch code.
1170                          * Except if an object is really small, then squeeze multiple
1171                          * into one cacheline.
1172                          */
1173                         align = cache_line_size();
1174                         while (size <= align/2)
1175                                 align /= 2;
1176                 } else {
1177                         align = BYTES_PER_WORD;
1178                 }
1179         }
1180
1181         /* Get cache's description obj. */
1182         cachep = (kmem_cache_t *) kmem_cache_alloc(&cache_cache, SLAB_KERNEL);
1183         if (!cachep)
1184                 goto opps;
1185         memset(cachep, 0, sizeof(kmem_cache_t));
1186
1187         /* Check that size is in terms of words.  This is needed to avoid
1188          * unaligned accesses for some archs when redzoning is used, and makes
1189          * sure any on-slab bufctl's are also correctly aligned.
1190          */
1191         if (size & (BYTES_PER_WORD-1)) {
1192                 size += (BYTES_PER_WORD-1);
1193                 size &= ~(BYTES_PER_WORD-1);
1194         }
1195
1196 #if DEBUG
1197         cachep->reallen = size;
1198
1199         if (flags & SLAB_RED_ZONE) {
1200                 /* redzoning only works with word aligned caches */
1201                 align = BYTES_PER_WORD;
1202
1203                 /* add space for red zone words */
1204                 cachep->dbghead += BYTES_PER_WORD;
1205                 size += 2*BYTES_PER_WORD;
1206         }
1207         if (flags & SLAB_STORE_USER) {
1208                 /* user store requires word alignment and
1209                  * one word storage behind the end of the real
1210                  * object.
1211                  */
1212                 align = BYTES_PER_WORD;
1213                 size += BYTES_PER_WORD;
1214         }
1215 #if FORCED_DEBUG && defined(CONFIG_DEBUG_PAGEALLOC)
1216         if (size > 128 && cachep->reallen > cache_line_size() && size < PAGE_SIZE) {
1217                 cachep->dbghead += PAGE_SIZE - size;
1218                 size = PAGE_SIZE;
1219         }
1220 #endif
1221 #endif
1222
1223         /* Determine if the slab management is 'on' or 'off' slab. */
1224         if (size >= (PAGE_SIZE>>3))
1225                 /*
1226                  * Size is large, assume best to place the slab management obj
1227                  * off-slab (should allow better packing of objs).
1228                  */
1229                 flags |= CFLGS_OFF_SLAB;
1230
1231         size = ALIGN(size, align);
1232
1233         if ((flags & SLAB_RECLAIM_ACCOUNT) && size <= PAGE_SIZE) {
1234                 /*
1235                  * A VFS-reclaimable slab tends to have most allocations
1236                  * as GFP_NOFS and we really don't want to have to be allocating
1237                  * higher-order pages when we are unable to shrink dcache.
1238                  */
1239                 cachep->gfporder = 0;
1240                 cache_estimate(cachep->gfporder, size, align, flags,
1241                                         &left_over, &cachep->num);
1242         } else {
1243                 /*
1244                  * Calculate size (in pages) of slabs, and the num of objs per
1245                  * slab.  This could be made much more intelligent.  For now,
1246                  * try to avoid using high page-orders for slabs.  When the
1247                  * gfp() funcs are more friendly towards high-order requests,
1248                  * this should be changed.
1249                  */
1250                 do {
1251                         unsigned int break_flag = 0;
1252 cal_wastage:
1253                         cache_estimate(cachep->gfporder, size, align, flags,
1254                                                 &left_over, &cachep->num);
1255                         if (break_flag)
1256                                 break;
1257                         if (cachep->gfporder >= MAX_GFP_ORDER)
1258                                 break;
1259                         if (!cachep->num)
1260                                 goto next;
1261                         if (flags & CFLGS_OFF_SLAB &&
1262                                         cachep->num > offslab_limit) {
1263                                 /* This num of objs will cause problems. */
1264                                 cachep->gfporder--;
1265                                 break_flag++;
1266                                 goto cal_wastage;
1267                         }
1268
1269                         /*
1270                          * Large num of objs is good, but v. large slabs are
1271                          * currently bad for the gfp()s.
1272                          */
1273                         if (cachep->gfporder >= slab_break_gfp_order)
1274                                 break;
1275
1276                         if ((left_over*8) <= (PAGE_SIZE<<cachep->gfporder))
1277                                 break;  /* Acceptable internal fragmentation. */
1278 next:
1279                         cachep->gfporder++;
1280                 } while (1);
1281         }
1282
1283         if (!cachep->num) {
1284                 printk("kmem_cache_create: couldn't create cache %s.\n", name);
1285                 kmem_cache_free(&cache_cache, cachep);
1286                 cachep = NULL;
1287                 goto opps;
1288         }
1289         slab_size = ALIGN(cachep->num*sizeof(kmem_bufctl_t)
1290                                 + sizeof(struct slab), align);
1291
1292         /*
1293          * If the slab has been placed off-slab, and we have enough space then
1294          * move it on-slab. This is at the expense of any extra colouring.
1295          */
1296         if (flags & CFLGS_OFF_SLAB && left_over >= slab_size) {
1297                 flags &= ~CFLGS_OFF_SLAB;
1298                 left_over -= slab_size;
1299         }
1300
1301         if (flags & CFLGS_OFF_SLAB) {
1302                 /* really off slab. No need for manual alignment */
1303                 slab_size = cachep->num*sizeof(kmem_bufctl_t)+sizeof(struct slab);
1304         }
1305
1306         cachep->colour_off = cache_line_size();
1307         /* Offset must be a multiple of the alignment. */
1308         if (cachep->colour_off < align)
1309                 cachep->colour_off = align;
1310         cachep->colour = left_over/cachep->colour_off;
1311         cachep->slab_size = slab_size;
1312         cachep->flags = flags;
1313         cachep->gfpflags = 0;
1314         if (flags & SLAB_CACHE_DMA)
1315                 cachep->gfpflags |= GFP_DMA;
1316         spin_lock_init(&cachep->spinlock);
1317         cachep->objsize = size;
1318         /* NUMA */
1319         INIT_LIST_HEAD(&cachep->lists.slabs_full);
1320         INIT_LIST_HEAD(&cachep->lists.slabs_partial);
1321         INIT_LIST_HEAD(&cachep->lists.slabs_free);
1322
1323         if (flags & CFLGS_OFF_SLAB)
1324                 cachep->slabp_cache = kmem_find_general_cachep(slab_size,0);
1325         cachep->ctor = ctor;
1326         cachep->dtor = dtor;
1327         cachep->name = name;
1328
1329         /* Don't let CPUs to come and go */
1330         lock_cpu_hotplug();
1331
1332         if (g_cpucache_up == FULL) {
1333                 enable_cpucache(cachep);
1334         } else {
1335                 if (g_cpucache_up == NONE) {
1336                         /* Note: the first kmem_cache_create must create
1337                          * the cache that's used by kmalloc(24), otherwise
1338                          * the creation of further caches will BUG().
1339                          */
1340                         cachep->array[smp_processor_id()] =
1341                                         &initarray_generic.cache;
1342                         g_cpucache_up = PARTIAL;
1343                 } else {
1344                         cachep->array[smp_processor_id()] =
1345                                 kmalloc(sizeof(struct arraycache_init),
1346                                         GFP_KERNEL);
1347                 }
1348                 BUG_ON(!ac_data(cachep));
1349                 ac_data(cachep)->avail = 0;
1350                 ac_data(cachep)->limit = BOOT_CPUCACHE_ENTRIES;
1351                 ac_data(cachep)->batchcount = 1;
1352                 ac_data(cachep)->touched = 0;
1353                 cachep->batchcount = 1;
1354                 cachep->limit = BOOT_CPUCACHE_ENTRIES;
1355                 cachep->free_limit = (1+num_online_cpus())*cachep->batchcount
1356                                         + cachep->num;
1357         }
1358
1359         cachep->lists.next_reap = jiffies + REAPTIMEOUT_LIST3 +
1360                                 ((unsigned long)cachep)%REAPTIMEOUT_LIST3;
1361
1362         /* Need the semaphore to access the chain. */
1363         down(&cache_chain_sem);
1364         {
1365                 struct list_head *p;
1366                 mm_segment_t old_fs;
1367
1368                 old_fs = get_fs();
1369                 set_fs(KERNEL_DS);
1370                 list_for_each(p, &cache_chain) {
1371                         kmem_cache_t *pc = list_entry(p, kmem_cache_t, next);
1372                         char tmp;
1373
1374                         /*
1375                          * This happens when the module gets unloaded and
1376                          * doesn't destroy its slab cache and noone else reuses
1377                          * the vmalloc area of the module. Print a warning.
1378                          */
1379 #ifdef CONFIG_X86_UACCESS_INDIRECT
1380                         if (__direct_get_user(tmp,pc->name)) {
1381 #else
1382                         if (__get_user(tmp,pc->name)) {
1383 #endif
1384                                 printk("SLAB: cache with size %d has lost its "
1385                                                 "name\n", pc->objsize);
1386                                 continue;
1387                         }
1388                         if (!strcmp(pc->name,name)) {
1389                                 printk("kmem_cache_create: duplicate "
1390                                                 "cache %s\n",name);
1391                                 up(&cache_chain_sem);
1392                                 unlock_cpu_hotplug();
1393                                 BUG();
1394                         }
1395                 }
1396                 set_fs(old_fs);
1397         }
1398
1399         /* cache setup completed, link it into the list */
1400         list_add(&cachep->next, &cache_chain);
1401         up(&cache_chain_sem);
1402         unlock_cpu_hotplug();
1403 opps:
1404         if (!cachep && (flags & SLAB_PANIC))
1405                 panic("kmem_cache_create(): failed to create slab `%s'\n",
1406                         name);
1407         return cachep;
1408 }
1409 EXPORT_SYMBOL(kmem_cache_create);
1410
1411 #if DEBUG
1412 static void check_irq_off(void)
1413 {
1414         BUG_ON(!irqs_disabled());
1415 }
1416
1417 static void check_irq_on(void)
1418 {
1419         BUG_ON(irqs_disabled());
1420 }
1421
1422 static void check_spinlock_acquired(kmem_cache_t *cachep)
1423 {
1424 #ifdef CONFIG_SMP
1425         check_irq_off();
1426         BUG_ON(spin_trylock(&cachep->spinlock));
1427 #endif
1428 }
1429 #else
1430 #define check_irq_off() do { } while(0)
1431 #define check_irq_on()  do { } while(0)
1432 #define check_spinlock_acquired(x) do { } while(0)
1433 #endif
1434
1435 /*
1436  * Waits for all CPUs to execute func().
1437  */
1438 static void smp_call_function_all_cpus(void (*func) (void *arg), void *arg)
1439 {
1440         check_irq_on();
1441         preempt_disable();
1442
1443         local_irq_disable();
1444         func(arg);
1445         local_irq_enable();
1446
1447         if (smp_call_function(func, arg, 1, 1))
1448                 BUG();
1449
1450         preempt_enable();
1451 }
1452
1453 static void drain_array_locked(kmem_cache_t* cachep,
1454                                 struct array_cache *ac, int force);
1455
1456 static void do_drain(void *arg)
1457 {
1458         kmem_cache_t *cachep = (kmem_cache_t*)arg;
1459         struct array_cache *ac;
1460
1461         check_irq_off();
1462         ac = ac_data(cachep);
1463         spin_lock(&cachep->spinlock);
1464         free_block(cachep, &ac_entry(ac)[0], ac->avail);
1465         spin_unlock(&cachep->spinlock);
1466         ac->avail = 0;
1467 }
1468
1469 static void drain_cpu_caches(kmem_cache_t *cachep)
1470 {
1471         smp_call_function_all_cpus(do_drain, cachep);
1472         check_irq_on();
1473         spin_lock_irq(&cachep->spinlock);
1474         if (cachep->lists.shared)
1475                 drain_array_locked(cachep, cachep->lists.shared, 1);
1476         spin_unlock_irq(&cachep->spinlock);
1477 }
1478
1479
1480 /* NUMA shrink all list3s */
1481 static int __cache_shrink(kmem_cache_t *cachep)
1482 {
1483         struct slab *slabp;
1484         int ret;
1485
1486         drain_cpu_caches(cachep);
1487
1488         check_irq_on();
1489         spin_lock_irq(&cachep->spinlock);
1490
1491         for(;;) {
1492                 struct list_head *p;
1493
1494                 p = cachep->lists.slabs_free.prev;
1495                 if (p == &cachep->lists.slabs_free)
1496                         break;
1497
1498                 slabp = list_entry(cachep->lists.slabs_free.prev, struct slab, list);
1499 #if DEBUG
1500                 if (slabp->inuse)
1501                         BUG();
1502 #endif
1503                 list_del(&slabp->list);
1504
1505                 cachep->lists.free_objects -= cachep->num;
1506                 spin_unlock_irq(&cachep->spinlock);
1507                 slab_destroy(cachep, slabp);
1508                 spin_lock_irq(&cachep->spinlock);
1509         }
1510         ret = !list_empty(&cachep->lists.slabs_full) ||
1511                 !list_empty(&cachep->lists.slabs_partial);
1512         spin_unlock_irq(&cachep->spinlock);
1513         return ret;
1514 }
1515
1516 /**
1517  * kmem_cache_shrink - Shrink a cache.
1518  * @cachep: The cache to shrink.
1519  *
1520  * Releases as many slabs as possible for a cache.
1521  * To help debugging, a zero exit status indicates all slabs were released.
1522  */
1523 int kmem_cache_shrink(kmem_cache_t *cachep)
1524 {
1525         if (!cachep || in_interrupt())
1526                 BUG();
1527
1528         return __cache_shrink(cachep);
1529 }
1530
1531 EXPORT_SYMBOL(kmem_cache_shrink);
1532
1533 /**
1534  * kmem_cache_destroy - delete a cache
1535  * @cachep: the cache to destroy
1536  *
1537  * Remove a kmem_cache_t object from the slab cache.
1538  * Returns 0 on success.
1539  *
1540  * It is expected this function will be called by a module when it is
1541  * unloaded.  This will remove the cache completely, and avoid a duplicate
1542  * cache being allocated each time a module is loaded and unloaded, if the
1543  * module doesn't have persistent in-kernel storage across loads and unloads.
1544  *
1545  * The cache must be empty before calling this function.
1546  *
1547  * The caller must guarantee that noone will allocate memory from the cache
1548  * during the kmem_cache_destroy().
1549  */
1550 int kmem_cache_destroy (kmem_cache_t * cachep)
1551 {
1552         int i;
1553
1554         if (!cachep || in_interrupt())
1555                 BUG();
1556
1557         /* Don't let CPUs to come and go */
1558         lock_cpu_hotplug();
1559
1560         /* Find the cache in the chain of caches. */
1561         down(&cache_chain_sem);
1562         /*
1563          * the chain is never empty, cache_cache is never destroyed
1564          */
1565         list_del(&cachep->next);
1566         up(&cache_chain_sem);
1567
1568         if (__cache_shrink(cachep)) {
1569                 slab_error(cachep, "Can't free all objects");
1570                 down(&cache_chain_sem);
1571                 list_add(&cachep->next,&cache_chain);
1572                 up(&cache_chain_sem);
1573                 unlock_cpu_hotplug();
1574                 return 1;
1575         }
1576
1577         /* no cpu_online check required here since we clear the percpu
1578          * array on cpu offline and set this to NULL.
1579          */
1580         for (i = 0; i < NR_CPUS; i++)
1581                 kfree(cachep->array[i]);
1582
1583         /* NUMA: free the list3 structures */
1584         kfree(cachep->lists.shared);
1585         cachep->lists.shared = NULL;
1586         kmem_cache_free(&cache_cache, cachep);
1587
1588         unlock_cpu_hotplug();
1589
1590         return 0;
1591 }
1592
1593 EXPORT_SYMBOL(kmem_cache_destroy);
1594
1595 /* Get the memory for a slab management obj. */
1596 static struct slab* alloc_slabmgmt (kmem_cache_t *cachep,
1597                         void *objp, int colour_off, int local_flags)
1598 {
1599         struct slab *slabp;
1600
1601         if (OFF_SLAB(cachep)) {
1602                 /* Slab management obj is off-slab. */
1603                 slabp = kmem_cache_alloc(cachep->slabp_cache, local_flags);
1604                 if (!slabp)
1605                         return NULL;
1606         } else {
1607                 slabp = objp+colour_off;
1608                 colour_off += cachep->slab_size;
1609         }
1610         slabp->inuse = 0;
1611         slabp->colouroff = colour_off;
1612         slabp->s_mem = objp+colour_off;
1613
1614         return slabp;
1615 }
1616
1617 static inline kmem_bufctl_t *slab_bufctl(struct slab *slabp)
1618 {
1619         return (kmem_bufctl_t *)(slabp+1);
1620 }
1621
1622 static void cache_init_objs (kmem_cache_t * cachep,
1623                         struct slab * slabp, unsigned long ctor_flags)
1624 {
1625         int i;
1626
1627         for (i = 0; i < cachep->num; i++) {
1628                 void* objp = slabp->s_mem+cachep->objsize*i;
1629 #if DEBUG
1630                 /* need to poison the objs? */
1631                 if (cachep->flags & SLAB_POISON)
1632                         poison_obj(cachep, objp, POISON_FREE);
1633                 if (cachep->flags & SLAB_STORE_USER)
1634                         *dbg_userword(cachep, objp) = NULL;
1635
1636                 if (cachep->flags & SLAB_RED_ZONE) {
1637                         *dbg_redzone1(cachep, objp) = RED_INACTIVE;
1638                         *dbg_redzone2(cachep, objp) = RED_INACTIVE;
1639                 }
1640                 /*
1641                  * Constructors are not allowed to allocate memory from
1642                  * the same cache which they are a constructor for.
1643                  * Otherwise, deadlock. They must also be threaded.
1644                  */
1645                 if (cachep->ctor && !(cachep->flags & SLAB_POISON))
1646                         cachep->ctor(objp+obj_dbghead(cachep), cachep, ctor_flags);
1647
1648                 if (cachep->flags & SLAB_RED_ZONE) {
1649                         if (*dbg_redzone2(cachep, objp) != RED_INACTIVE)
1650                                 slab_error(cachep, "constructor overwrote the"
1651                                                         " end of an object");
1652                         if (*dbg_redzone1(cachep, objp) != RED_INACTIVE)
1653                                 slab_error(cachep, "constructor overwrote the"
1654                                                         " start of an object");
1655                 }
1656                 if ((cachep->objsize % PAGE_SIZE) == 0 && OFF_SLAB(cachep) && cachep->flags & SLAB_POISON)
1657                         kernel_map_pages(virt_to_page(objp), cachep->objsize/PAGE_SIZE, 0);
1658 #else
1659                 if (cachep->ctor)
1660                         cachep->ctor(objp, cachep, ctor_flags);
1661 #endif
1662                 slab_bufctl(slabp)[i] = i+1;
1663         }
1664         slab_bufctl(slabp)[i-1] = BUFCTL_END;
1665         slabp->free = 0;
1666 }
1667
1668 static void kmem_flagcheck(kmem_cache_t *cachep, int flags)
1669 {
1670         if (flags & SLAB_DMA) {
1671                 if (!(cachep->gfpflags & GFP_DMA))
1672                         BUG();
1673         } else {
1674                 if (cachep->gfpflags & GFP_DMA)
1675                         BUG();
1676         }
1677 }
1678
1679 static void set_slab_attr(kmem_cache_t *cachep, struct slab *slabp, void *objp)
1680 {
1681         int i;
1682         struct page *page;
1683
1684         /* Nasty!!!!!! I hope this is OK. */
1685         i = 1 << cachep->gfporder;
1686         page = virt_to_page(objp);
1687         do {
1688                 SET_PAGE_CACHE(page, cachep);
1689                 SET_PAGE_SLAB(page, slabp);
1690                 page++;
1691         } while (--i);
1692 }
1693
1694 /*
1695  * Grow (by 1) the number of slabs within a cache.  This is called by
1696  * kmem_cache_alloc() when there are no active objs left in a cache.
1697  */
1698 static int cache_grow (kmem_cache_t * cachep, int flags)
1699 {
1700         struct slab     *slabp;
1701         void            *objp;
1702         size_t           offset;
1703         int              local_flags;
1704         unsigned long    ctor_flags;
1705
1706         /* Be lazy and only check for valid flags here,
1707          * keeping it out of the critical path in kmem_cache_alloc().
1708          */
1709         if (flags & ~(SLAB_DMA|SLAB_LEVEL_MASK|SLAB_NO_GROW))
1710                 BUG();
1711         if (flags & SLAB_NO_GROW)
1712                 return 0;
1713
1714         ctor_flags = SLAB_CTOR_CONSTRUCTOR;
1715         local_flags = (flags & SLAB_LEVEL_MASK);
1716         if (!(local_flags & __GFP_WAIT))
1717                 /*
1718                  * Not allowed to sleep.  Need to tell a constructor about
1719                  * this - it might need to know...
1720                  */
1721                 ctor_flags |= SLAB_CTOR_ATOMIC;
1722
1723         /* About to mess with non-constant members - lock. */
1724         check_irq_off();
1725         spin_lock(&cachep->spinlock);
1726
1727         /* Get colour for the slab, and cal the next value. */
1728         offset = cachep->colour_next;
1729         cachep->colour_next++;
1730         if (cachep->colour_next >= cachep->colour)
1731                 cachep->colour_next = 0;
1732         offset *= cachep->colour_off;
1733
1734         spin_unlock(&cachep->spinlock);
1735
1736         if (local_flags & __GFP_WAIT)
1737                 local_irq_enable();
1738
1739         /*
1740          * The test for missing atomic flag is performed here, rather than
1741          * the more obvious place, simply to reduce the critical path length
1742          * in kmem_cache_alloc(). If a caller is seriously mis-behaving they
1743          * will eventually be caught here (where it matters).
1744          */
1745         kmem_flagcheck(cachep, flags);
1746
1747
1748         /* Get mem for the objs. */
1749         if (!(objp = kmem_getpages(cachep, flags, -1)))
1750                 goto failed;
1751
1752         /* Get slab management. */
1753         if (!(slabp = alloc_slabmgmt(cachep, objp, offset, local_flags)))
1754                 goto opps1;
1755
1756         set_slab_attr(cachep, slabp, objp);
1757
1758         cache_init_objs(cachep, slabp, ctor_flags);
1759
1760         if (local_flags & __GFP_WAIT)
1761                 local_irq_disable();
1762         check_irq_off();
1763         spin_lock(&cachep->spinlock);
1764
1765         /* Make slab active. */
1766         list_add_tail(&slabp->list, &(list3_data(cachep)->slabs_free));
1767         STATS_INC_GROWN(cachep);
1768         list3_data(cachep)->free_objects += cachep->num;
1769         spin_unlock(&cachep->spinlock);
1770         return 1;
1771 opps1:
1772         kmem_freepages(cachep, objp);
1773 failed:
1774         if (local_flags & __GFP_WAIT)
1775                 local_irq_disable();
1776         return 0;
1777 }
1778
1779 #if DEBUG
1780
1781 /*
1782  * Perform extra freeing checks:
1783  * - detect bad pointers.
1784  * - POISON/RED_ZONE checking
1785  * - destructor calls, for caches with POISON+dtor
1786  */
1787 static void kfree_debugcheck(const void *objp)
1788 {
1789         struct page *page;
1790
1791         if (!virt_addr_valid(objp)) {
1792                 printk(KERN_ERR "kfree_debugcheck: out of range ptr %lxh.\n",
1793                         (unsigned long)objp);
1794                 BUG();
1795         }
1796         page = virt_to_page(objp);
1797         if (!PageSlab(page)) {
1798                 printk(KERN_ERR "kfree_debugcheck: bad ptr %lxh.\n", (unsigned long)objp);
1799                 BUG();
1800         }
1801 }
1802
1803 static void *cache_free_debugcheck (kmem_cache_t * cachep, void * objp, void *caller)
1804 {
1805         struct page *page;
1806         unsigned int objnr;
1807         struct slab *slabp;
1808
1809         objp -= obj_dbghead(cachep);
1810         kfree_debugcheck(objp);
1811         page = virt_to_page(objp);
1812
1813         if (GET_PAGE_CACHE(page) != cachep) {
1814                 printk(KERN_ERR "mismatch in kmem_cache_free: expected cache %p, got %p\n",
1815                                 GET_PAGE_CACHE(page),cachep);
1816                 printk(KERN_ERR "%p is %s.\n", cachep, cachep->name);
1817                 printk(KERN_ERR "%p is %s.\n", GET_PAGE_CACHE(page), GET_PAGE_CACHE(page)->name);
1818                 WARN_ON(1);
1819         }
1820         slabp = GET_PAGE_SLAB(page);
1821
1822         if (cachep->flags & SLAB_RED_ZONE) {
1823                 if (*dbg_redzone1(cachep, objp) != RED_ACTIVE || *dbg_redzone2(cachep, objp) != RED_ACTIVE) {
1824                         slab_error(cachep, "double free, or memory outside"
1825                                                 " object was overwritten");
1826                         printk(KERN_ERR "%p: redzone 1: 0x%lx, redzone 2: 0x%lx.\n",
1827                                         objp, *dbg_redzone1(cachep, objp), *dbg_redzone2(cachep, objp));
1828                 }
1829                 *dbg_redzone1(cachep, objp) = RED_INACTIVE;
1830                 *dbg_redzone2(cachep, objp) = RED_INACTIVE;
1831         }
1832         if (cachep->flags & SLAB_STORE_USER)
1833                 *dbg_userword(cachep, objp) = caller;
1834
1835         objnr = (objp-slabp->s_mem)/cachep->objsize;
1836
1837         BUG_ON(objnr >= cachep->num);
1838         BUG_ON(objp != slabp->s_mem + objnr*cachep->objsize);
1839
1840         if (cachep->flags & SLAB_DEBUG_INITIAL) {
1841                 /* Need to call the slab's constructor so the
1842                  * caller can perform a verify of its state (debugging).
1843                  * Called without the cache-lock held.
1844                  */
1845                 cachep->ctor(objp+obj_dbghead(cachep),
1846                                         cachep, SLAB_CTOR_CONSTRUCTOR|SLAB_CTOR_VERIFY);
1847         }
1848         if (cachep->flags & SLAB_POISON && cachep->dtor) {
1849                 /* we want to cache poison the object,
1850                  * call the destruction callback
1851                  */
1852                 cachep->dtor(objp+obj_dbghead(cachep), cachep, 0);
1853         }
1854         if (cachep->flags & SLAB_POISON) {
1855 #ifdef CONFIG_DEBUG_PAGEALLOC
1856                 if ((cachep->objsize % PAGE_SIZE) == 0 && OFF_SLAB(cachep)) {
1857                         store_stackinfo(cachep, objp, (unsigned long)caller);
1858                         kernel_map_pages(virt_to_page(objp), cachep->objsize/PAGE_SIZE, 0);
1859                 } else {
1860                         poison_obj(cachep, objp, POISON_FREE);
1861                 }
1862 #else
1863                 poison_obj(cachep, objp, POISON_FREE);
1864 #endif
1865         }
1866         return objp;
1867 }
1868
1869 static void check_slabp(kmem_cache_t *cachep, struct slab *slabp)
1870 {
1871         int i;
1872         int entries = 0;
1873
1874         check_spinlock_acquired(cachep);
1875         /* Check slab's freelist to see if this obj is there. */
1876         for (i = slabp->free; i != BUFCTL_END; i = slab_bufctl(slabp)[i]) {
1877                 entries++;
1878                 if (entries > cachep->num || i < 0 || i >= cachep->num)
1879                         goto bad;
1880         }
1881         if (entries != cachep->num - slabp->inuse) {
1882                 int i;
1883 bad:
1884                 printk(KERN_ERR "slab: Internal list corruption detected in cache '%s'(%d), slabp %p(%d). Hexdump:\n",
1885                                 cachep->name, cachep->num, slabp, slabp->inuse);
1886                 for (i=0;i<sizeof(slabp)+cachep->num*sizeof(kmem_bufctl_t);i++) {
1887                         if ((i%16)==0)
1888                                 printk("\n%03x:", i);
1889                         printk(" %02x", ((unsigned char*)slabp)[i]);
1890                 }
1891                 printk("\n");
1892                 BUG();
1893         }
1894 }
1895 #else
1896 #define kfree_debugcheck(x) do { } while(0)
1897 #define cache_free_debugcheck(x,objp,z) (objp)
1898 #define check_slabp(x,y) do { } while(0)
1899 #endif
1900
1901 static void* cache_alloc_refill(kmem_cache_t* cachep, int flags)
1902 {
1903         int batchcount;
1904         struct kmem_list3 *l3;
1905         struct array_cache *ac;
1906
1907         check_irq_off();
1908         ac = ac_data(cachep);
1909 retry:
1910         batchcount = ac->batchcount;
1911         if (!ac->touched && batchcount > BATCHREFILL_LIMIT) {
1912                 /* if there was little recent activity on this
1913                  * cache, then perform only a partial refill.
1914                  * Otherwise we could generate refill bouncing.
1915                  */
1916                 batchcount = BATCHREFILL_LIMIT;
1917         }
1918         l3 = list3_data(cachep);
1919
1920         BUG_ON(ac->avail > 0);
1921         spin_lock(&cachep->spinlock);
1922         if (l3->shared) {
1923                 struct array_cache *shared_array = l3->shared;
1924                 if (shared_array->avail) {
1925                         if (batchcount > shared_array->avail)
1926                                 batchcount = shared_array->avail;
1927                         shared_array->avail -= batchcount;
1928                         ac->avail = batchcount;
1929                         memcpy(ac_entry(ac), &ac_entry(shared_array)[shared_array->avail],
1930                                         sizeof(void*)*batchcount);
1931                         shared_array->touched = 1;
1932                         goto alloc_done;
1933                 }
1934         }
1935         while (batchcount > 0) {
1936                 struct list_head *entry;
1937                 struct slab *slabp;
1938                 /* Get slab alloc is to come from. */
1939                 entry = l3->slabs_partial.next;
1940                 if (entry == &l3->slabs_partial) {
1941                         l3->free_touched = 1;
1942                         entry = l3->slabs_free.next;
1943                         if (entry == &l3->slabs_free)
1944                                 goto must_grow;
1945                 }
1946
1947                 slabp = list_entry(entry, struct slab, list);
1948                 check_slabp(cachep, slabp);
1949                 check_spinlock_acquired(cachep);
1950                 while (slabp->inuse < cachep->num && batchcount--) {
1951                         kmem_bufctl_t next;
1952                         STATS_INC_ALLOCED(cachep);
1953                         STATS_INC_ACTIVE(cachep);
1954                         STATS_SET_HIGH(cachep);
1955
1956                         /* get obj pointer */
1957                         ac_entry(ac)[ac->avail++] = slabp->s_mem + slabp->free*cachep->objsize;
1958
1959                         slabp->inuse++;
1960                         next = slab_bufctl(slabp)[slabp->free];
1961 #if DEBUG
1962                         slab_bufctl(slabp)[slabp->free] = BUFCTL_FREE;
1963 #endif
1964                         slabp->free = next;
1965                 }
1966                 check_slabp(cachep, slabp);
1967
1968                 /* move slabp to correct slabp list: */
1969                 list_del(&slabp->list);
1970                 if (slabp->free == BUFCTL_END)
1971                         list_add(&slabp->list, &l3->slabs_full);
1972                 else
1973                         list_add(&slabp->list, &l3->slabs_partial);
1974         }
1975
1976 must_grow:
1977         l3->free_objects -= ac->avail;
1978 alloc_done:
1979         spin_unlock(&cachep->spinlock);
1980
1981         if (unlikely(!ac->avail)) {
1982                 int x;
1983                 x = cache_grow(cachep, flags);
1984
1985                 // cache_grow can reenable interrupts, then ac could change.
1986                 ac = ac_data(cachep);
1987                 if (!x && ac->avail == 0)       // no objects in sight? abort
1988                         return NULL;
1989
1990                 if (!ac->avail)         // objects refilled by interrupt?
1991                         goto retry;
1992         }
1993         ac->touched = 1;
1994         return ac_entry(ac)[--ac->avail];
1995 }
1996
1997 static inline void
1998 cache_alloc_debugcheck_before(kmem_cache_t *cachep, int flags)
1999 {
2000         might_sleep_if(flags & __GFP_WAIT);
2001 #if DEBUG
2002         kmem_flagcheck(cachep, flags);
2003 #endif
2004 }
2005
2006 #if DEBUG
2007 static void *
2008 cache_alloc_debugcheck_after(kmem_cache_t *cachep,
2009                         unsigned long flags, void *objp, void *caller)
2010 {
2011         if (!objp)
2012                 return objp;
2013         if (cachep->flags & SLAB_POISON) {
2014 #ifdef CONFIG_DEBUG_PAGEALLOC
2015                 if ((cachep->objsize % PAGE_SIZE) == 0 && OFF_SLAB(cachep))
2016                         kernel_map_pages(virt_to_page(objp), cachep->objsize/PAGE_SIZE, 1);
2017                 else
2018                         check_poison_obj(cachep, objp);
2019 #else
2020                 check_poison_obj(cachep, objp);
2021 #endif
2022                 poison_obj(cachep, objp, POISON_INUSE);
2023         }
2024         if (cachep->flags & SLAB_STORE_USER)
2025                 *dbg_userword(cachep, objp) = caller;
2026
2027         if (cachep->flags & SLAB_RED_ZONE) {
2028                 if (*dbg_redzone1(cachep, objp) != RED_INACTIVE || *dbg_redzone2(cachep, objp) != RED_INACTIVE) {
2029                         slab_error(cachep, "double free, or memory outside"
2030                                                 " object was overwritten");
2031                         printk(KERN_ERR "%p: redzone 1: 0x%lx, redzone 2: 0x%lx.\n",
2032                                         objp, *dbg_redzone1(cachep, objp), *dbg_redzone2(cachep, objp));
2033                 }
2034                 *dbg_redzone1(cachep, objp) = RED_ACTIVE;
2035                 *dbg_redzone2(cachep, objp) = RED_ACTIVE;
2036         }
2037         objp += obj_dbghead(cachep);
2038         if (cachep->ctor && cachep->flags & SLAB_POISON) {
2039                 unsigned long   ctor_flags = SLAB_CTOR_CONSTRUCTOR;
2040
2041                 if (!(flags & __GFP_WAIT))
2042                         ctor_flags |= SLAB_CTOR_ATOMIC;
2043
2044                 cachep->ctor(objp, cachep, ctor_flags);
2045         }
2046         return objp;
2047 }
2048 #else
2049 #define cache_alloc_debugcheck_after(a,b,objp,d) (objp)
2050 #endif
2051
2052
2053 static inline void * __cache_alloc (kmem_cache_t *cachep, int flags)
2054 {
2055         unsigned long save_flags;
2056         void* objp;
2057         struct array_cache *ac;
2058
2059         cache_alloc_debugcheck_before(cachep, flags);
2060
2061         local_irq_save(save_flags);
2062         ac = ac_data(cachep);
2063         if (likely(ac->avail)) {
2064                 STATS_INC_ALLOCHIT(cachep);
2065                 ac->touched = 1;
2066                 objp = ac_entry(ac)[--ac->avail];
2067         } else {
2068                 STATS_INC_ALLOCMISS(cachep);
2069                 objp = cache_alloc_refill(cachep, flags);
2070         }
2071         local_irq_restore(save_flags);
2072         objp = cache_alloc_debugcheck_after(cachep, flags, objp, __builtin_return_address(0));
2073         return objp;
2074 }
2075
2076 /*
2077  * NUMA: different approach needed if the spinlock is moved into
2078  * the l3 structure
2079  */
2080
2081 static void free_block(kmem_cache_t *cachep, void **objpp, int nr_objects)
2082 {
2083         int i;
2084
2085         check_spinlock_acquired(cachep);
2086
2087         /* NUMA: move add into loop */
2088         cachep->lists.free_objects += nr_objects;
2089
2090         for (i = 0; i < nr_objects; i++) {
2091                 void *objp = objpp[i];
2092                 struct slab *slabp;
2093                 unsigned int objnr;
2094
2095                 slabp = GET_PAGE_SLAB(virt_to_page(objp));
2096                 list_del(&slabp->list);
2097                 objnr = (objp - slabp->s_mem) / cachep->objsize;
2098                 check_slabp(cachep, slabp);
2099 #if DEBUG
2100                 if (slab_bufctl(slabp)[objnr] != BUFCTL_FREE) {
2101                         printk(KERN_ERR "slab: double free detected in cache '%s', objp %p.\n",
2102                                                 cachep->name, objp);
2103                         BUG();
2104                 }
2105 #endif
2106                 slab_bufctl(slabp)[objnr] = slabp->free;
2107                 slabp->free = objnr;
2108                 STATS_DEC_ACTIVE(cachep);
2109                 slabp->inuse--;
2110                 check_slabp(cachep, slabp);
2111
2112                 /* fixup slab chains */
2113                 if (slabp->inuse == 0) {
2114                         if (cachep->lists.free_objects > cachep->free_limit) {
2115                                 cachep->lists.free_objects -= cachep->num;
2116                                 slab_destroy(cachep, slabp);
2117                         } else {
2118                                 list_add(&slabp->list,
2119                                 &list3_data_ptr(cachep, objp)->slabs_free);
2120                         }
2121                 } else {
2122                         /* Unconditionally move a slab to the end of the
2123                          * partial list on free - maximum time for the
2124                          * other objects to be freed, too.
2125                          */
2126                         list_add_tail(&slabp->list,
2127                                 &list3_data_ptr(cachep, objp)->slabs_partial);
2128                 }
2129         }
2130 }
2131
2132 static void cache_flusharray (kmem_cache_t* cachep, struct array_cache *ac)
2133 {
2134         int batchcount;
2135
2136         batchcount = ac->batchcount;
2137 #if DEBUG
2138         BUG_ON(!batchcount || batchcount > ac->avail);
2139 #endif
2140         check_irq_off();
2141         spin_lock(&cachep->spinlock);
2142         if (cachep->lists.shared) {
2143                 struct array_cache *shared_array = cachep->lists.shared;
2144                 int max = shared_array->limit-shared_array->avail;
2145                 if (max) {
2146                         if (batchcount > max)
2147                                 batchcount = max;
2148                         memcpy(&ac_entry(shared_array)[shared_array->avail],
2149                                         &ac_entry(ac)[0],
2150                                         sizeof(void*)*batchcount);
2151                         shared_array->avail += batchcount;
2152                         goto free_done;
2153                 }
2154         }
2155
2156         free_block(cachep, &ac_entry(ac)[0], batchcount);
2157 free_done:
2158 #if STATS
2159         {
2160                 int i = 0;
2161                 struct list_head *p;
2162
2163                 p = list3_data(cachep)->slabs_free.next;
2164                 while (p != &(list3_data(cachep)->slabs_free)) {
2165                         struct slab *slabp;
2166
2167                         slabp = list_entry(p, struct slab, list);
2168                         BUG_ON(slabp->inuse);
2169
2170                         i++;
2171                         p = p->next;
2172                 }
2173                 STATS_SET_FREEABLE(cachep, i);
2174         }
2175 #endif
2176         spin_unlock(&cachep->spinlock);
2177         ac->avail -= batchcount;
2178         memmove(&ac_entry(ac)[0], &ac_entry(ac)[batchcount],
2179                         sizeof(void*)*ac->avail);
2180 }
2181
2182 /*
2183  * __cache_free
2184  * Release an obj back to its cache. If the obj has a constructed
2185  * state, it must be in this state _before_ it is released.
2186  *
2187  * Called with disabled ints.
2188  */
2189 static inline void __cache_free (kmem_cache_t *cachep, void* objp)
2190 {
2191         struct array_cache *ac = ac_data(cachep);
2192
2193         check_irq_off();
2194         objp = cache_free_debugcheck(cachep, objp, __builtin_return_address(0));
2195
2196         if (likely(ac->avail < ac->limit)) {
2197                 STATS_INC_FREEHIT(cachep);
2198                 ac_entry(ac)[ac->avail++] = objp;
2199                 return;
2200         } else {
2201                 STATS_INC_FREEMISS(cachep);
2202                 cache_flusharray(cachep, ac);
2203                 ac_entry(ac)[ac->avail++] = objp;
2204         }
2205 }
2206
2207 /**
2208  * kmem_cache_alloc - Allocate an object
2209  * @cachep: The cache to allocate from.
2210  * @flags: See kmalloc().
2211  *
2212  * Allocate an object from this cache.  The flags are only relevant
2213  * if the cache has no available objects.
2214  */
2215 void * kmem_cache_alloc (kmem_cache_t *cachep, int flags)
2216 {
2217         return __cache_alloc(cachep, flags);
2218 }
2219
2220 EXPORT_SYMBOL(kmem_cache_alloc);
2221
2222 /**
2223  * kmem_ptr_validate - check if an untrusted pointer might
2224  *      be a slab entry.
2225  * @cachep: the cache we're checking against
2226  * @ptr: pointer to validate
2227  *
2228  * This verifies that the untrusted pointer looks sane:
2229  * it is _not_ a guarantee that the pointer is actually
2230  * part of the slab cache in question, but it at least
2231  * validates that the pointer can be dereferenced and
2232  * looks half-way sane.
2233  *
2234  * Currently only used for dentry validation.
2235  */
2236 int fastcall kmem_ptr_validate(kmem_cache_t *cachep, void *ptr)
2237 {
2238         unsigned long addr = (unsigned long) ptr;
2239         unsigned long min_addr = PAGE_OFFSET;
2240         unsigned long align_mask = BYTES_PER_WORD-1;
2241         unsigned long size = cachep->objsize;
2242         struct page *page;
2243
2244         if (unlikely(addr < min_addr))
2245                 goto out;
2246         if (unlikely(addr > (unsigned long)high_memory - size))
2247                 goto out;
2248         if (unlikely(addr & align_mask))
2249                 goto out;
2250         if (unlikely(!kern_addr_valid(addr)))
2251                 goto out;
2252         if (unlikely(!kern_addr_valid(addr + size - 1)))
2253                 goto out;
2254         page = virt_to_page(ptr);
2255         if (unlikely(!PageSlab(page)))
2256                 goto out;
2257         if (unlikely(GET_PAGE_CACHE(page) != cachep))
2258                 goto out;
2259         return 1;
2260 out:
2261         return 0;
2262 }
2263
2264 /**
2265  * kmem_cache_alloc_node - Allocate an object on the specified node
2266  * @cachep: The cache to allocate from.
2267  * @flags: See kmalloc().
2268  * @nodeid: node number of the target node.
2269  *
2270  * Identical to kmem_cache_alloc, except that this function is slow
2271  * and can sleep. And it will allocate memory on the given node, which
2272  * can improve the performance for cpu bound structures.
2273  */
2274 void *kmem_cache_alloc_node(kmem_cache_t *cachep, int nodeid)
2275 {
2276         size_t offset;
2277         void *objp;
2278         struct slab *slabp;
2279         kmem_bufctl_t next;
2280
2281         /* The main algorithms are not node aware, thus we have to cheat:
2282          * We bypass all caches and allocate a new slab.
2283          * The following code is a streamlined copy of cache_grow().
2284          */
2285
2286         /* Get colour for the slab, and update the next value. */
2287         spin_lock_irq(&cachep->spinlock);
2288         offset = cachep->colour_next;
2289         cachep->colour_next++;
2290         if (cachep->colour_next >= cachep->colour)
2291                 cachep->colour_next = 0;
2292         offset *= cachep->colour_off;
2293         spin_unlock_irq(&cachep->spinlock);
2294
2295         /* Get mem for the objs. */
2296         if (!(objp = kmem_getpages(cachep, GFP_KERNEL, nodeid)))
2297                 goto failed;
2298
2299         /* Get slab management. */
2300         if (!(slabp = alloc_slabmgmt(cachep, objp, offset, GFP_KERNEL)))
2301                 goto opps1;
2302
2303         set_slab_attr(cachep, slabp, objp);
2304         cache_init_objs(cachep, slabp, SLAB_CTOR_CONSTRUCTOR);
2305
2306         /* The first object is ours: */
2307         objp = slabp->s_mem + slabp->free*cachep->objsize;
2308         slabp->inuse++;
2309         next = slab_bufctl(slabp)[slabp->free];
2310 #if DEBUG
2311         slab_bufctl(slabp)[slabp->free] = BUFCTL_FREE;
2312 #endif
2313         slabp->free = next;
2314
2315         /* add the remaining objects into the cache */
2316         spin_lock_irq(&cachep->spinlock);
2317         check_slabp(cachep, slabp);
2318         STATS_INC_GROWN(cachep);
2319         /* Make slab active. */
2320         if (slabp->free == BUFCTL_END) {
2321                 list_add_tail(&slabp->list, &(list3_data(cachep)->slabs_full));
2322         } else {
2323                 list_add_tail(&slabp->list,
2324                                 &(list3_data(cachep)->slabs_partial));
2325                 list3_data(cachep)->free_objects += cachep->num-1;
2326         }
2327         spin_unlock_irq(&cachep->spinlock);
2328         objp = cache_alloc_debugcheck_after(cachep, GFP_KERNEL, objp,
2329                                         __builtin_return_address(0));
2330         return objp;
2331 opps1:
2332         kmem_freepages(cachep, objp);
2333 failed:
2334         return NULL;
2335
2336 }
2337 EXPORT_SYMBOL(kmem_cache_alloc_node);
2338
2339 /**
2340  * kmalloc - allocate memory
2341  * @size: how many bytes of memory are required.
2342  * @flags: the type of memory to allocate.
2343  *
2344  * kmalloc is the normal method of allocating memory
2345  * in the kernel.
2346  *
2347  * The @flags argument may be one of:
2348  *
2349  * %GFP_USER - Allocate memory on behalf of user.  May sleep.
2350  *
2351  * %GFP_KERNEL - Allocate normal kernel ram.  May sleep.
2352  *
2353  * %GFP_ATOMIC - Allocation will not sleep.  Use inside interrupt handlers.
2354  *
2355  * Additionally, the %GFP_DMA flag may be set to indicate the memory
2356  * must be suitable for DMA.  This can mean different things on different
2357  * platforms.  For example, on i386, it means that the memory must come
2358  * from the first 16MB.
2359  */
2360 void * __kmalloc (size_t size, int flags)
2361 {
2362         struct cache_sizes *csizep = malloc_sizes;
2363
2364         for (; csizep->cs_size; csizep++) {
2365                 if (size > csizep->cs_size)
2366                         continue;
2367 #if DEBUG
2368                 /* This happens if someone tries to call
2369                  * kmem_cache_create(), or kmalloc(), before
2370                  * the generic caches are initialized.
2371                  */
2372                 BUG_ON(csizep->cs_cachep == NULL);
2373 #endif
2374                 return __cache_alloc(flags & GFP_DMA ?
2375                          csizep->cs_dmacachep : csizep->cs_cachep, flags);
2376         }
2377         return NULL;
2378 }
2379
2380 EXPORT_SYMBOL(__kmalloc);
2381
2382 #ifdef CONFIG_SMP
2383 /**
2384  * __alloc_percpu - allocate one copy of the object for every present
2385  * cpu in the system, zeroing them.
2386  * Objects should be dereferenced using per_cpu_ptr/get_cpu_ptr
2387  * macros only.
2388  *
2389  * @size: how many bytes of memory are required.
2390  * @align: the alignment, which can't be greater than SMP_CACHE_BYTES.
2391  */
2392 void *__alloc_percpu(size_t size, size_t align)
2393 {
2394         int i;
2395         struct percpu_data *pdata = kmalloc(sizeof (*pdata), GFP_KERNEL);
2396
2397         if (!pdata)
2398                 return NULL;
2399
2400         for (i = 0; i < NR_CPUS; i++) {
2401                 if (!cpu_possible(i))
2402                         continue;
2403                 pdata->ptrs[i] = kmem_cache_alloc_node(
2404                                 kmem_find_general_cachep(size, GFP_KERNEL),
2405                                 cpu_to_node(i));
2406
2407                 if (!pdata->ptrs[i])
2408                         goto unwind_oom;
2409                 memset(pdata->ptrs[i], 0, size);
2410         }
2411
2412         /* Catch derefs w/o wrappers */
2413         return (void *) (~(unsigned long) pdata);
2414
2415 unwind_oom:
2416         while (--i >= 0) {
2417                 if (!cpu_possible(i))
2418                         continue;
2419                 kfree(pdata->ptrs[i]);
2420         }
2421         kfree(pdata);
2422         return NULL;
2423 }
2424
2425 EXPORT_SYMBOL(__alloc_percpu);
2426 #endif
2427
2428 /**
2429  * kmem_cache_free - Deallocate an object
2430  * @cachep: The cache the allocation was from.
2431  * @objp: The previously allocated object.
2432  *
2433  * Free an object which was previously allocated from this
2434  * cache.
2435  */
2436 void kmem_cache_free (kmem_cache_t *cachep, void *objp)
2437 {
2438         unsigned long flags;
2439
2440         local_irq_save(flags);
2441         __cache_free(cachep, objp);
2442         local_irq_restore(flags);
2443 }
2444
2445 EXPORT_SYMBOL(kmem_cache_free);
2446
2447 /**
2448  * kfree - free previously allocated memory
2449  * @objp: pointer returned by kmalloc.
2450  *
2451  * Don't free memory not originally allocated by kmalloc()
2452  * or you will run into trouble.
2453  */
2454 void kfree (const void *objp)
2455 {
2456         kmem_cache_t *c;
2457         unsigned long flags;
2458
2459         if (!objp)
2460                 return;
2461         local_irq_save(flags);
2462         kfree_debugcheck(objp);
2463         c = GET_PAGE_CACHE(virt_to_page(objp));
2464         __cache_free(c, (void*)objp);
2465         local_irq_restore(flags);
2466 }
2467
2468 EXPORT_SYMBOL(kfree);
2469
2470 #ifdef CONFIG_SMP
2471 /**
2472  * free_percpu - free previously allocated percpu memory
2473  * @objp: pointer returned by alloc_percpu.
2474  *
2475  * Don't free memory not originally allocated by alloc_percpu()
2476  * The complemented objp is to check for that.
2477  */
2478 void
2479 free_percpu(const void *objp)
2480 {
2481         int i;
2482         struct percpu_data *p = (struct percpu_data *) (~(unsigned long) objp);
2483
2484         for (i = 0; i < NR_CPUS; i++) {
2485                 if (!cpu_possible(i))
2486                         continue;
2487                 kfree(p->ptrs[i]);
2488         }
2489 }
2490
2491 EXPORT_SYMBOL(free_percpu);
2492 #endif
2493
2494 unsigned int kmem_cache_size(kmem_cache_t *cachep)
2495 {
2496         return obj_reallen(cachep);
2497 }
2498
2499 EXPORT_SYMBOL(kmem_cache_size);
2500
2501 kmem_cache_t * kmem_find_general_cachep (size_t size, int gfpflags)
2502 {
2503         struct cache_sizes *csizep = malloc_sizes;
2504
2505         /* This function could be moved to the header file, and
2506          * made inline so consumers can quickly determine what
2507          * cache pointer they require.
2508          */
2509         for ( ; csizep->cs_size; csizep++) {
2510                 if (size > csizep->cs_size)
2511                         continue;
2512                 break;
2513         }
2514         return (gfpflags & GFP_DMA) ? csizep->cs_dmacachep : csizep->cs_cachep;
2515 }
2516
2517 EXPORT_SYMBOL(kmem_find_general_cachep);
2518
2519 struct ccupdate_struct {
2520         kmem_cache_t *cachep;
2521         struct array_cache *new[NR_CPUS];
2522 };
2523
2524 static void do_ccupdate_local(void *info)
2525 {
2526         struct ccupdate_struct *new = (struct ccupdate_struct *)info;
2527         struct array_cache *old;
2528
2529         check_irq_off();
2530         old = ac_data(new->cachep);
2531
2532         new->cachep->array[smp_processor_id()] = new->new[smp_processor_id()];
2533         new->new[smp_processor_id()] = old;
2534 }
2535
2536
2537 static int do_tune_cpucache (kmem_cache_t* cachep, int limit, int batchcount, int shared)
2538 {
2539         struct ccupdate_struct new;
2540         struct array_cache *new_shared;
2541         int i;
2542
2543         memset(&new.new,0,sizeof(new.new));
2544         for (i = 0; i < NR_CPUS; i++) {
2545                 if (cpu_online(i)) {
2546                         new.new[i] = alloc_arraycache(i, limit, batchcount);
2547                         if (!new.new[i]) {
2548                                 for (i--; i >= 0; i--) kfree(new.new[i]);
2549                                 return -ENOMEM;
2550                         }
2551                 } else {
2552                         new.new[i] = NULL;
2553                 }
2554         }
2555         new.cachep = cachep;
2556
2557         smp_call_function_all_cpus(do_ccupdate_local, (void *)&new);
2558
2559         check_irq_on();
2560         spin_lock_irq(&cachep->spinlock);
2561         cachep->batchcount = batchcount;
2562         cachep->limit = limit;
2563         cachep->free_limit = (1+num_online_cpus())*cachep->batchcount + cachep->num;
2564         spin_unlock_irq(&cachep->spinlock);
2565
2566         for (i = 0; i < NR_CPUS; i++) {
2567                 struct array_cache *ccold = new.new[i];
2568                 if (!ccold)
2569                         continue;
2570                 spin_lock_irq(&cachep->spinlock);
2571                 free_block(cachep, ac_entry(ccold), ccold->avail);
2572                 spin_unlock_irq(&cachep->spinlock);
2573                 kfree(ccold);
2574         }
2575         new_shared = alloc_arraycache(-1, batchcount*shared, 0xbaadf00d);
2576         if (new_shared) {
2577                 struct array_cache *old;
2578
2579                 spin_lock_irq(&cachep->spinlock);
2580                 old = cachep->lists.shared;
2581                 cachep->lists.shared = new_shared;
2582                 if (old)
2583                         free_block(cachep, ac_entry(old), old->avail);
2584                 spin_unlock_irq(&cachep->spinlock);
2585                 kfree(old);
2586         }
2587
2588         return 0;
2589 }
2590
2591
2592 static void enable_cpucache (kmem_cache_t *cachep)
2593 {
2594         int err;
2595         int limit, shared;
2596
2597         /* The head array serves three purposes:
2598          * - create a LIFO ordering, i.e. return objects that are cache-warm
2599          * - reduce the number of spinlock operations.
2600          * - reduce the number of linked list operations on the slab and
2601          *   bufctl chains: array operations are cheaper.
2602          * The numbers are guessed, we should auto-tune as described by
2603          * Bonwick.
2604          */
2605         if (cachep->objsize > 131072)
2606                 limit = 1;
2607         else if (cachep->objsize > PAGE_SIZE)
2608                 limit = 8;
2609         else if (cachep->objsize > 1024)
2610                 limit = 24;
2611         else if (cachep->objsize > 256)
2612                 limit = 54;
2613         else
2614                 limit = 120;
2615
2616         /* Cpu bound tasks (e.g. network routing) can exhibit cpu bound
2617          * allocation behaviour: Most allocs on one cpu, most free operations
2618          * on another cpu. For these cases, an efficient object passing between
2619          * cpus is necessary. This is provided by a shared array. The array
2620          * replaces Bonwick's magazine layer.
2621          * On uniprocessor, it's functionally equivalent (but less efficient)
2622          * to a larger limit. Thus disabled by default.
2623          */
2624         shared = 0;
2625 #ifdef CONFIG_SMP
2626         if (cachep->objsize <= PAGE_SIZE)
2627                 shared = 8;
2628 #endif
2629
2630 #if DEBUG
2631         /* With debugging enabled, large batchcount lead to excessively
2632          * long periods with disabled local interrupts. Limit the
2633          * batchcount
2634          */
2635         if (limit > 32)
2636                 limit = 32;
2637 #endif
2638         err = do_tune_cpucache(cachep, limit, (limit+1)/2, shared);
2639         if (err)
2640                 printk(KERN_ERR "enable_cpucache failed for %s, error %d.\n",
2641                                         cachep->name, -err);
2642 }
2643
2644 static void drain_array(kmem_cache_t *cachep, struct array_cache *ac)
2645 {
2646         int tofree;
2647
2648         check_irq_off();
2649         if (ac->touched) {
2650                 ac->touched = 0;
2651         } else if (ac->avail) {
2652                 tofree = (ac->limit+4)/5;
2653                 if (tofree > ac->avail) {
2654                         tofree = (ac->avail+1)/2;
2655                 }
2656                 spin_lock(&cachep->spinlock);
2657                 free_block(cachep, ac_entry(ac), tofree);
2658                 spin_unlock(&cachep->spinlock);
2659                 ac->avail -= tofree;
2660                 memmove(&ac_entry(ac)[0], &ac_entry(ac)[tofree],
2661                                         sizeof(void*)*ac->avail);
2662         }
2663 }
2664
2665 static void drain_array_locked(kmem_cache_t *cachep,
2666                                 struct array_cache *ac, int force)
2667 {
2668         int tofree;
2669
2670         check_spinlock_acquired(cachep);
2671         if (ac->touched && !force) {
2672                 ac->touched = 0;
2673         } else if (ac->avail) {
2674                 tofree = force ? ac->avail : (ac->limit+4)/5;
2675                 if (tofree > ac->avail) {
2676                         tofree = (ac->avail+1)/2;
2677                 }
2678                 free_block(cachep, ac_entry(ac), tofree);
2679                 ac->avail -= tofree;
2680                 memmove(&ac_entry(ac)[0], &ac_entry(ac)[tofree],
2681                                         sizeof(void*)*ac->avail);
2682         }
2683 }
2684
2685 /**
2686  * cache_reap - Reclaim memory from caches.
2687  *
2688  * Called from a timer, every few seconds
2689  * Purpose:
2690  * - clear the per-cpu caches for this CPU.
2691  * - return freeable pages to the main free memory pool.
2692  *
2693  * If we cannot acquire the cache chain semaphore then just give up - we'll
2694  * try again next timer interrupt.
2695  */
2696 static void cache_reap (void)
2697 {
2698         struct list_head *walk;
2699
2700 #if DEBUG
2701         BUG_ON(!in_interrupt());
2702         BUG_ON(in_irq());
2703 #endif
2704         if (down_trylock(&cache_chain_sem))
2705                 return;
2706
2707         list_for_each(walk, &cache_chain) {
2708                 kmem_cache_t *searchp;
2709                 struct list_head* p;
2710                 int tofree;
2711                 struct slab *slabp;
2712
2713                 searchp = list_entry(walk, kmem_cache_t, next);
2714
2715                 if (searchp->flags & SLAB_NO_REAP)
2716                         goto next;
2717
2718                 check_irq_on();
2719                 local_irq_disable();
2720                 drain_array(searchp, ac_data(searchp));
2721
2722                 if(time_after(searchp->lists.next_reap, jiffies))
2723                         goto next_irqon;
2724
2725                 spin_lock(&searchp->spinlock);
2726                 if(time_after(searchp->lists.next_reap, jiffies)) {
2727                         goto next_unlock;
2728                 }
2729                 searchp->lists.next_reap = jiffies + REAPTIMEOUT_LIST3;
2730
2731                 if (searchp->lists.shared)
2732                         drain_array_locked(searchp, searchp->lists.shared, 0);
2733
2734                 if (searchp->lists.free_touched) {
2735                         searchp->lists.free_touched = 0;
2736                         goto next_unlock;
2737                 }
2738
2739                 tofree = (searchp->free_limit+5*searchp->num-1)/(5*searchp->num);
2740                 do {
2741                         p = list3_data(searchp)->slabs_free.next;
2742                         if (p == &(list3_data(searchp)->slabs_free))
2743                                 break;
2744
2745                         slabp = list_entry(p, struct slab, list);
2746                         BUG_ON(slabp->inuse);
2747                         list_del(&slabp->list);
2748                         STATS_INC_REAPED(searchp);
2749
2750                         /* Safe to drop the lock. The slab is no longer
2751                          * linked to the cache.
2752                          * searchp cannot disappear, we hold
2753                          * cache_chain_lock
2754                          */
2755                         searchp->lists.free_objects -= searchp->num;
2756                         spin_unlock_irq(&searchp->spinlock);
2757                         slab_destroy(searchp, slabp);
2758                         spin_lock_irq(&searchp->spinlock);
2759                 } while(--tofree > 0);
2760 next_unlock:
2761                 spin_unlock(&searchp->spinlock);
2762 next_irqon:
2763                 local_irq_enable();
2764 next:
2765                 ;
2766         }
2767         check_irq_on();
2768         up(&cache_chain_sem);
2769 }
2770
2771 /*
2772  * This is a timer handler.  There is one per CPU.  It is called periodially
2773  * to shrink this CPU's caches.  Otherwise there could be memory tied up
2774  * for long periods (or for ever) due to load changes.
2775  */
2776 static void reap_timer_fnc(unsigned long cpu)
2777 {
2778         struct timer_list *rt = &__get_cpu_var(reap_timers);
2779
2780         /* CPU hotplug can drag us off cpu: don't run on wrong CPU */
2781         if (!cpu_is_offline(cpu)) {
2782                 cache_reap();
2783                 mod_timer(rt, jiffies + REAPTIMEOUT_CPUC + cpu);
2784         }
2785 }
2786
2787 #ifdef CONFIG_PROC_FS
2788
2789 static void *s_start(struct seq_file *m, loff_t *pos)
2790 {
2791         loff_t n = *pos;
2792         struct list_head *p;
2793
2794         down(&cache_chain_sem);
2795         if (!n) {
2796                 /*
2797                  * Output format version, so at least we can change it
2798                  * without _too_ many complaints.
2799                  */
2800 #if STATS
2801                 seq_puts(m, "slabinfo - version: 2.0 (statistics)\n");
2802 #else
2803                 seq_puts(m, "slabinfo - version: 2.0\n");
2804 #endif
2805                 seq_puts(m, "# name            <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab>");
2806                 seq_puts(m, " : tunables <batchcount> <limit> <sharedfactor>");
2807                 seq_puts(m, " : slabdata <active_slabs> <num_slabs> <sharedavail>");
2808 #if STATS
2809                 seq_puts(m, " : globalstat <listallocs> <maxobjs> <grown> <reaped> <error> <maxfreeable> <freelimit>");
2810                 seq_puts(m, " : cpustat <allochit> <allocmiss> <freehit> <freemiss>");
2811 #endif
2812                 seq_putc(m, '\n');
2813         }
2814         p = cache_chain.next;
2815         while (n--) {
2816                 p = p->next;
2817                 if (p == &cache_chain)
2818                         return NULL;
2819         }
2820         return list_entry(p, kmem_cache_t, next);
2821 }
2822
2823 static void *s_next(struct seq_file *m, void *p, loff_t *pos)
2824 {
2825         kmem_cache_t *cachep = p;
2826         ++*pos;
2827         return cachep->next.next == &cache_chain ? NULL
2828                 : list_entry(cachep->next.next, kmem_cache_t, next);
2829 }
2830
2831 static void s_stop(struct seq_file *m, void *p)
2832 {
2833         up(&cache_chain_sem);
2834 }
2835
2836 static int s_show(struct seq_file *m, void *p)
2837 {
2838         kmem_cache_t *cachep = p;
2839         struct list_head *q;
2840         struct slab     *slabp;
2841         unsigned long   active_objs;
2842         unsigned long   num_objs;
2843         unsigned long   active_slabs = 0;
2844         unsigned long   num_slabs;
2845         const char *name;
2846         char *error = NULL;
2847
2848         check_irq_on();
2849         spin_lock_irq(&cachep->spinlock);
2850         active_objs = 0;
2851         num_slabs = 0;
2852         list_for_each(q,&cachep->lists.slabs_full) {
2853                 slabp = list_entry(q, struct slab, list);
2854                 if (slabp->inuse != cachep->num && !error)
2855                         error = "slabs_full accounting error";
2856                 active_objs += cachep->num;
2857                 active_slabs++;
2858         }
2859         list_for_each(q,&cachep->lists.slabs_partial) {
2860                 slabp = list_entry(q, struct slab, list);
2861                 if (slabp->inuse == cachep->num && !error)
2862                         error = "slabs_partial inuse accounting error";
2863                 if (!slabp->inuse && !error)
2864                         error = "slabs_partial/inuse accounting error";
2865                 active_objs += slabp->inuse;
2866                 active_slabs++;
2867         }
2868         list_for_each(q,&cachep->lists.slabs_free) {
2869                 slabp = list_entry(q, struct slab, list);
2870                 if (slabp->inuse && !error)
2871                         error = "slabs_free/inuse accounting error";
2872                 num_slabs++;
2873         }
2874         num_slabs+=active_slabs;
2875         num_objs = num_slabs*cachep->num;
2876         if (num_objs - active_objs != cachep->lists.free_objects && !error)
2877                 error = "free_objects accounting error";
2878
2879         name = cachep->name;
2880         if (error)
2881                 printk(KERN_ERR "slab: cache %s error: %s\n", name, error);
2882
2883         seq_printf(m, "%-17s %6lu %6lu %6u %4u %4d",
2884                 name, active_objs, num_objs, cachep->objsize,
2885                 cachep->num, (1<<cachep->gfporder));
2886         seq_printf(m, " : tunables %4u %4u %4u",
2887                         cachep->limit, cachep->batchcount,
2888                         cachep->lists.shared->limit/cachep->batchcount);
2889         seq_printf(m, " : slabdata %6lu %6lu %6u",
2890                         active_slabs, num_slabs, cachep->lists.shared->avail);
2891 #if STATS
2892         {       /* list3 stats */
2893                 unsigned long high = cachep->high_mark;
2894                 unsigned long allocs = cachep->num_allocations;
2895                 unsigned long grown = cachep->grown;
2896                 unsigned long reaped = cachep->reaped;
2897                 unsigned long errors = cachep->errors;
2898                 unsigned long max_freeable = cachep->max_freeable;
2899                 unsigned long free_limit = cachep->free_limit;
2900
2901                 seq_printf(m, " : globalstat %7lu %6lu %5lu %4lu %4lu %4lu %4lu",
2902                                 allocs, high, grown, reaped, errors,
2903                                 max_freeable, free_limit);
2904         }
2905         /* cpu stats */
2906         {
2907                 unsigned long allochit = atomic_read(&cachep->allochit);
2908                 unsigned long allocmiss = atomic_read(&cachep->allocmiss);
2909                 unsigned long freehit = atomic_read(&cachep->freehit);
2910                 unsigned long freemiss = atomic_read(&cachep->freemiss);
2911
2912                 seq_printf(m, " : cpustat %6lu %6lu %6lu %6lu",
2913                         allochit, allocmiss, freehit, freemiss);
2914         }
2915 #endif
2916         seq_putc(m, '\n');
2917         spin_unlock_irq(&cachep->spinlock);
2918         return 0;
2919 }
2920
2921 /*
2922  * slabinfo_op - iterator that generates /proc/slabinfo
2923  *
2924  * Output layout:
2925  * cache-name
2926  * num-active-objs
2927  * total-objs
2928  * object size
2929  * num-active-slabs
2930  * total-slabs
2931  * num-pages-per-slab
2932  * + further values on SMP and with statistics enabled
2933  */
2934
2935 struct seq_operations slabinfo_op = {
2936         .start  = s_start,
2937         .next   = s_next,
2938         .stop   = s_stop,
2939         .show   = s_show,
2940 };
2941
2942 #define MAX_SLABINFO_WRITE 128
2943 /**
2944  * slabinfo_write - Tuning for the slab allocator
2945  * @file: unused
2946  * @buffer: user buffer
2947  * @count: data length
2948  * @ppos: unused
2949  */
2950 ssize_t slabinfo_write(struct file *file, const char __user *buffer,
2951                                 size_t count, loff_t *ppos)
2952 {
2953         char kbuf[MAX_SLABINFO_WRITE+1], *tmp;
2954         int limit, batchcount, shared, res;
2955         struct list_head *p;
2956
2957         if (count > MAX_SLABINFO_WRITE)
2958                 return -EINVAL;
2959         if (copy_from_user(&kbuf, buffer, count))
2960                 return -EFAULT;
2961         kbuf[MAX_SLABINFO_WRITE] = '\0';
2962
2963         tmp = strchr(kbuf, ' ');
2964         if (!tmp)
2965                 return -EINVAL;
2966         *tmp = '\0';
2967         tmp++;
2968         if (sscanf(tmp, " %d %d %d", &limit, &batchcount, &shared) != 3)
2969                 return -EINVAL;
2970
2971         /* Find the cache in the chain of caches. */
2972         down(&cache_chain_sem);
2973         res = -EINVAL;
2974         list_for_each(p,&cache_chain) {
2975                 kmem_cache_t *cachep = list_entry(p, kmem_cache_t, next);
2976
2977                 if (!strcmp(cachep->name, kbuf)) {
2978                         if (limit < 1 ||
2979                             batchcount < 1 ||
2980                             batchcount > limit ||
2981                             shared < 0) {
2982                                 res = -EINVAL;
2983                         } else {
2984                                 res = do_tune_cpucache(cachep, limit, batchcount, shared);
2985                         }
2986                         break;
2987                 }
2988         }
2989         up(&cache_chain_sem);
2990         if (res >= 0)
2991                 res = count;
2992         return res;
2993 }
2994 #endif
2995
2996 unsigned int ksize(const void *objp)
2997 {
2998         kmem_cache_t *c;
2999         unsigned long flags;
3000         unsigned int size = 0;
3001
3002         if (likely(objp != NULL)) {
3003                 local_irq_save(flags);
3004                 c = GET_PAGE_CACHE(virt_to_page(objp));
3005                 size = kmem_cache_size(c);
3006                 local_irq_restore(flags);
3007         }
3008
3009         return size;
3010 }
3011
3012 void ptrinfo(unsigned long addr)
3013 {
3014         struct page *page;
3015
3016         printk("Dumping data about address %p.\n", (void*)addr);
3017         if (!virt_addr_valid((void*)addr)) {
3018                 printk("virt addr invalid.\n");
3019                 return;
3020         }
3021 #ifdef CONFIG_MMU
3022         do {
3023                 pgd_t *pgd = pgd_offset_k(addr);
3024                 pmd_t *pmd;
3025                 if (pgd_none(*pgd)) {
3026                         printk("No pgd.\n");
3027                         break;
3028                 }
3029                 pmd = pmd_offset(pgd, addr);
3030                 if (pmd_none(*pmd)) {
3031                         printk("No pmd.\n");
3032                         break;
3033                 }
3034 #ifdef CONFIG_X86
3035                 if (pmd_large(*pmd)) {
3036                         printk("Large page.\n");
3037                         break;
3038                 }
3039 #endif
3040                 printk("normal page, pte_val 0x%llx\n",
3041                   (unsigned long long)pte_val(*pte_offset_kernel(pmd, addr)));
3042         } while(0);
3043 #endif
3044
3045         page = virt_to_page((void*)addr);
3046         printk("struct page at %p, flags %08lx\n",
3047                         page, (unsigned long)page->flags);
3048         if (PageSlab(page)) {
3049                 kmem_cache_t *c;
3050                 struct slab *s;
3051                 unsigned long flags;
3052                 int objnr;
3053                 void *objp;
3054
3055                 c = GET_PAGE_CACHE(page);
3056                 printk("belongs to cache %s.\n",c->name);
3057
3058                 spin_lock_irqsave(&c->spinlock, flags);
3059                 s = GET_PAGE_SLAB(page);
3060                 printk("slabp %p with %d inuse objects (from %d).\n",
3061                         s, s->inuse, c->num);
3062                 check_slabp(c,s);
3063
3064                 objnr = (addr-(unsigned long)s->s_mem)/c->objsize;
3065                 objp = s->s_mem+c->objsize*objnr;
3066                 printk("points into object no %d, starting at %p, len %d.\n",
3067                         objnr, objp, c->objsize);
3068                 if (objnr >= c->num) {
3069                         printk("Bad obj number.\n");
3070                 } else {
3071                         kernel_map_pages(virt_to_page(objp),
3072                                         c->objsize/PAGE_SIZE, 1);
3073
3074                         print_objinfo(c, objp, 2);
3075                 }
3076                 spin_unlock_irqrestore(&c->spinlock, flags);
3077
3078         }
3079 }