SAFE public projects git trees. - safe/jmp/linux-2.6/blob - mm/slob.c

   1 /*
   2  * SLOB Allocator: Simple List Of Blocks
   3  *
   4  * Matt Mackall <mpm@selenic.com> 12/30/03
   5  *
   6  * How SLOB works:
   7  *
   8  * The core of SLOB is a traditional K&R style heap allocator, with
   9  * support for returning aligned objects. The granularity of this
  10  * allocator is 4 bytes on 32-bit and 8 bytes on 64-bit, though it
  11  * could be as low as 2 if the compiler alignment requirements allow.
  12  *
  13  * The slob heap is a linked list of pages from __get_free_page, and
  14  * within each page, there is a singly-linked list of free blocks (slob_t).
  15  * The heap is grown on demand and allocation from the heap is currently
  16  * first-fit.
  17  *
  18  * Above this is an implementation of kmalloc/kfree. Blocks returned
  19  * from kmalloc are 4-byte aligned and prepended with a 4-byte header.
  20  * If kmalloc is asked for objects of PAGE_SIZE or larger, it calls
  21  * __get_free_pages directly so that it can return page-aligned blocks
  22  * and keeps a linked list of such pages and their orders. These
  23  * objects are detected in kfree() by their page alignment.
  24  *
  25  * SLAB is emulated on top of SLOB by simply calling constructors and
  26  * destructors for every SLAB allocation. Objects are returned with the
  27  * 4-byte alignment unless the SLAB_HWCACHE_ALIGN flag is set, in which
  28  * case the low-level allocator will fragment blocks to create the proper
  29  * alignment. Again, objects of page-size or greater are allocated by
  30  * calling __get_free_pages. As SLAB objects know their size, no separate
  31  * size bookkeeping is necessary and there is essentially no allocation
  32  * space overhead.
  33  */
  34
  35 #include <linux/kernel.h>
  36 #include <linux/slab.h>
  37 #include <linux/mm.h>
  38 #include <linux/cache.h>
  39 #include <linux/init.h>
  40 #include <linux/module.h>
  41 #include <linux/rcupdate.h>
  42 #include <linux/list.h>
  43 #include <asm/atomic.h>
  44
  45 /* SLOB_MIN_ALIGN == sizeof(long) */
  46 #if BITS_PER_BYTE == 32
  47 #define SLOB_MIN_ALIGN  4
  48 #else
  49 #define SLOB_MIN_ALIGN  8
  50 #endif
  51
  52 /*
  53  * slob_block has a field 'units', which indicates size of block if +ve,
  54  * or offset of next block if -ve (in SLOB_UNITs).
  55  *
  56  * Free blocks of size 1 unit simply contain the offset of the next block.
  57  * Those with larger size contain their size in the first SLOB_UNIT of
  58  * memory, and the offset of the next free block in the second SLOB_UNIT.
  59  */
  60 #if PAGE_SIZE <= (32767 * SLOB_MIN_ALIGN)
  61 typedef s16 slobidx_t;
  62 #else
  63 typedef s32 slobidx_t;
  64 #endif
  65
  66 /*
  67  * Align struct slob_block to long for now, but can some embedded
  68  * architectures get away with less?
  69  */
  70 struct slob_block {
  71         slobidx_t units;
  72 } __attribute__((aligned(SLOB_MIN_ALIGN)));
  73 typedef struct slob_block slob_t;
  74
  75 /*
  76  * We use struct page fields to manage some slob allocation aspects,
  77  * however to avoid the horrible mess in include/linux/mm_types.h, we'll
  78  * just define our own struct page type variant here.
  79  */
  80 struct slob_page {
  81         union {
  82                 struct {
  83                         unsigned long flags;    /* mandatory */
  84                         atomic_t _count;        /* mandatory */
  85                         slobidx_t units;        /* free units left in page */
  86                         unsigned long pad[2];
  87                         slob_t *free;           /* first free slob_t in page */
  88                         struct list_head list;  /* linked list of free pages */
  89                 };
  90                 struct page page;
  91         };
  92 };
  93 static inline void struct_slob_page_wrong_size(void)
  94 { BUILD_BUG_ON(sizeof(struct slob_page) != sizeof(struct page)); }
  95
  96 /*
  97  * free_slob_page: call before a slob_page is returned to the page allocator.
  98  */
  99 static inline void free_slob_page(struct slob_page *sp)
 100 {
 101         reset_page_mapcount(&sp->page);
 102         sp->page.mapping = NULL;
 103 }
 104
 105 /*
 106  * All (partially) free slob pages go on this list.
 107  */
 108 static LIST_HEAD(free_slob_pages);
 109
 110 /*
 111  * slob_page: True for all slob pages (false for bigblock pages)
 112  */
 113 static inline int slob_page(struct slob_page *sp)
 114 {
 115         return test_bit(PG_active, &sp->flags);
 116 }
 117
 118 static inline void set_slob_page(struct slob_page *sp)
 119 {
 120         __set_bit(PG_active, &sp->flags);
 121 }
 122
 123 static inline void clear_slob_page(struct slob_page *sp)
 124 {
 125         __clear_bit(PG_active, &sp->flags);
 126 }
 127
 128 /*
 129  * slob_page_free: true for pages on free_slob_pages list.
 130  */
 131 static inline int slob_page_free(struct slob_page *sp)
 132 {
 133         return test_bit(PG_private, &sp->flags);
 134 }
 135
 136 static inline void set_slob_page_free(struct slob_page *sp)
 137 {
 138         list_add(&sp->list, &free_slob_pages);
 139         __set_bit(PG_private, &sp->flags);
 140 }
 141
 142 static inline void clear_slob_page_free(struct slob_page *sp)
 143 {
 144         list_del(&sp->list);
 145         __clear_bit(PG_private, &sp->flags);
 146 }
 147
 148 #define SLOB_UNIT sizeof(slob_t)
 149 #define SLOB_UNITS(size) (((size) + SLOB_UNIT - 1)/SLOB_UNIT)
 150 #define SLOB_ALIGN L1_CACHE_BYTES
 151
 152 /*
 153  * struct slob_rcu is inserted at the tail of allocated slob blocks, which
 154  * were created with a SLAB_DESTROY_BY_RCU slab. slob_rcu is used to free
 155  * the block using call_rcu.
 156  */
 157 struct slob_rcu {
 158         struct rcu_head head;
 159         int size;
 160 };
 161
 162 /*
 163  * slob_lock protects all slob allocator structures.
 164  */
 165 static DEFINE_SPINLOCK(slob_lock);
 166
 167 /*
 168  * Encode the given size and next info into a free slob block s.
 169  */
 170 static void set_slob(slob_t *s, slobidx_t size, slob_t *next)
 171 {
 172         slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);
 173         slobidx_t offset = next - base;
 174
 175         if (size > 1) {
 176                 s[0].units = size;
 177                 s[1].units = offset;
 178         } else
 179                 s[0].units = -offset;
 180 }
 181
 182 /*
 183  * Return the size of a slob block.
 184  */
 185 static slobidx_t slob_units(slob_t *s)
 186 {
 187         if (s->units > 0)
 188                 return s->units;
 189         return 1;
 190 }
 191
 192 /*
 193  * Return the next free slob block pointer after this one.
 194  */
 195 static slob_t *slob_next(slob_t *s)
 196 {
 197         slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);
 198         slobidx_t next;
 199
 200         if (s[0].units < 0)
 201                 next = -s[0].units;
 202         else
 203                 next = s[1].units;
 204         return base+next;
 205 }
 206
 207 /*
 208  * Returns true if s is the last free block in its page.
 209  */
 210 static int slob_last(slob_t *s)
 211 {
 212         return !((unsigned long)slob_next(s) & ~PAGE_MASK);
 213 }
 214
 215 /*
 216  * Allocate a slob block within a given slob_page sp.
 217  */
 218 static void *slob_page_alloc(struct slob_page *sp, size_t size, int align)
 219 {
 220         slob_t *prev, *cur, *aligned = 0;
 221         int delta = 0, units = SLOB_UNITS(size);
 222
 223         for (prev = NULL, cur = sp->free; ; prev = cur, cur = slob_next(cur)) {
 224                 slobidx_t avail = slob_units(cur);
 225
 226                 if (align) {
 227                         aligned = (slob_t *)ALIGN((unsigned long)cur, align);
 228                         delta = aligned - cur;
 229                 }
 230                 if (avail >= units + delta) { /* room enough? */
 231                         slob_t *next;
 232
 233                         if (delta) { /* need to fragment head to align? */
 234                                 next = slob_next(cur);
 235                                 set_slob(aligned, avail - delta, next);
 236                                 set_slob(cur, delta, aligned);
 237                                 prev = cur;
 238                                 cur = aligned;
 239                                 avail = slob_units(cur);
 240                         }
 241
 242                         next = slob_next(cur);
 243                         if (avail == units) { /* exact fit? unlink. */
 244                                 if (prev)
 245                                         set_slob(prev, slob_units(prev), next);
 246                                 else
 247                                         sp->free = next;
 248                         } else { /* fragment */
 249                                 if (prev)
 250                                         set_slob(prev, slob_units(prev), cur + units);
 251                                 else
 252                                         sp->free = cur + units;
 253                                 set_slob(cur + units, avail - units, next);
 254                         }
 255
 256                         sp->units -= units;
 257                         if (!sp->units)
 258                                 clear_slob_page_free(sp);
 259                         return cur;
 260                 }
 261                 if (slob_last(cur))
 262                         return NULL;
 263         }
 264 }
 265
 266 /*
 267  * slob_alloc: entry point into the slob allocator.
 268  */
 269 static void *slob_alloc(size_t size, gfp_t gfp, int align)
 270 {
 271         struct slob_page *sp;
 272         slob_t *b = NULL;
 273         unsigned long flags;
 274
 275         spin_lock_irqsave(&slob_lock, flags);
 276         /* Iterate through each partially free page, try to find room */
 277         list_for_each_entry(sp, &free_slob_pages, list) {
 278                 if (sp->units >= SLOB_UNITS(size)) {
 279                         b = slob_page_alloc(sp, size, align);
 280                         if (b)
 281                                 break;
 282                 }
 283         }
 284         spin_unlock_irqrestore(&slob_lock, flags);
 285
 286         /* Not enough space: must allocate a new page */
 287         if (!b) {
 288                 b = (slob_t *)__get_free_page(gfp);
 289                 if (!b)
 290                         return 0;
 291                 sp = (struct slob_page *)virt_to_page(b);
 292                 set_slob_page(sp);
 293
 294                 spin_lock_irqsave(&slob_lock, flags);
 295                 sp->units = SLOB_UNITS(PAGE_SIZE);
 296                 sp->free = b;
 297                 INIT_LIST_HEAD(&sp->list);
 298                 set_slob(b, SLOB_UNITS(PAGE_SIZE), b + SLOB_UNITS(PAGE_SIZE));
 299                 set_slob_page_free(sp);
 300                 b = slob_page_alloc(sp, size, align);
 301                 BUG_ON(!b);
 302                 spin_unlock_irqrestore(&slob_lock, flags);
 303         }
 304         return b;
 305 }
 306
 307 /*
 308  * slob_free: entry point into the slob allocator.
 309  */
 310 static void slob_free(void *block, int size)
 311 {
 312         struct slob_page *sp;
 313         slob_t *prev, *next, *b = (slob_t *)block;
 314         slobidx_t units;
 315         unsigned long flags;
 316
 317         if (!block)
 318                 return;
 319         BUG_ON(!size);
 320
 321         sp = (struct slob_page *)virt_to_page(block);
 322         units = SLOB_UNITS(size);
 323
 324         spin_lock_irqsave(&slob_lock, flags);
 325
 326         if (sp->units + units == SLOB_UNITS(PAGE_SIZE)) {
 327                 /* Go directly to page allocator. Do not pass slob allocator */
 328                 if (slob_page_free(sp))
 329                         clear_slob_page_free(sp);
 330                 clear_slob_page(sp);
 331                 free_slob_page(sp);
 332                 free_page((unsigned long)b);
 333                 goto out;
 334         }
 335
 336         if (!slob_page_free(sp)) {
 337                 /* This slob page is about to become partially free. Easy! */
 338                 sp->units = units;
 339                 sp->free = b;
 340                 set_slob(b, units,
 341                         (void *)((unsigned long)(b +
 342                                         SLOB_UNITS(PAGE_SIZE)) & PAGE_MASK));
 343                 set_slob_page_free(sp);
 344                 goto out;
 345         }
 346
 347         /*
 348          * Otherwise the page is already partially free, so find reinsertion
 349          * point.
 350          */
 351         sp->units += units;
 352
 353         if (b < sp->free) {
 354                 set_slob(b, units, sp->free);
 355                 sp->free = b;
 356         } else {
 357                 prev = sp->free;
 358                 next = slob_next(prev);
 359                 while (b > next) {
 360                         prev = next;
 361                         next = slob_next(prev);
 362                 }
 363
 364                 if (!slob_last(prev) && b + units == next) {
 365                         units += slob_units(next);
 366                         set_slob(b, units, slob_next(next));
 367                 } else
 368                         set_slob(b, units, next);
 369
 370                 if (prev + slob_units(prev) == b) {
 371                         units = slob_units(b) + slob_units(prev);
 372                         set_slob(prev, units, slob_next(b));
 373                 } else
 374                         set_slob(prev, slob_units(prev), b);
 375         }
 376 out:
 377         spin_unlock_irqrestore(&slob_lock, flags);
 378 }
 379
 380 /*
 381  * End of slob allocator proper. Begin kmem_cache_alloc and kmalloc frontend.
 382  */
 383
 384 struct bigblock {
 385         int order;
 386         void *pages;
 387         struct bigblock *next;
 388 };
 389 typedef struct bigblock bigblock_t;
 390
 391 static bigblock_t *bigblocks;
 392
 393 static DEFINE_SPINLOCK(block_lock);
 394
 395
 396 void *__kmalloc(size_t size, gfp_t gfp)
 397 {
 398         slob_t *m;
 399         bigblock_t *bb;
 400         unsigned long flags;
 401
 402         if (size < PAGE_SIZE - SLOB_UNIT) {
 403                 m = slob_alloc(size + SLOB_UNIT, gfp, 0);
 404                 if (m)
 405                         m->units = size;
 406                 return m+1;
 407         }
 408
 409         bb = slob_alloc(sizeof(bigblock_t), gfp, 0);
 410         if (!bb)
 411                 return 0;
 412
 413         bb->order = get_order(size);
 414         bb->pages = (void *)__get_free_pages(gfp, bb->order);
 415
 416         if (bb->pages) {
 417                 spin_lock_irqsave(&block_lock, flags);
 418                 bb->next = bigblocks;
 419                 bigblocks = bb;
 420                 spin_unlock_irqrestore(&block_lock, flags);
 421                 return bb->pages;
 422         }
 423
 424         slob_free(bb, sizeof(bigblock_t));
 425         return 0;
 426 }
 427 EXPORT_SYMBOL(__kmalloc);
 428
 429 /**
 430  * krealloc - reallocate memory. The contents will remain unchanged.
 431  *
 432  * @p: object to reallocate memory for.
 433  * @new_size: how many bytes of memory are required.
 434  * @flags: the type of memory to allocate.
 435  *
 436  * The contents of the object pointed to are preserved up to the
 437  * lesser of the new and old sizes.  If @p is %NULL, krealloc()
 438  * behaves exactly like kmalloc().  If @size is 0 and @p is not a
 439  * %NULL pointer, the object pointed to is freed.
 440  */
 441 void *krealloc(const void *p, size_t new_size, gfp_t flags)
 442 {
 443         void *ret;
 444
 445         if (unlikely(!p))
 446                 return kmalloc_track_caller(new_size, flags);
 447
 448         if (unlikely(!new_size)) {
 449                 kfree(p);
 450                 return NULL;
 451         }
 452
 453         ret = kmalloc_track_caller(new_size, flags);
 454         if (ret) {
 455                 memcpy(ret, p, min(new_size, ksize(p)));
 456                 kfree(p);
 457         }
 458         return ret;
 459 }
 460 EXPORT_SYMBOL(krealloc);
 461
 462 void kfree(const void *block)
 463 {
 464         struct slob_page *sp;
 465         slob_t *m;
 466         bigblock_t *bb, **last = &bigblocks;
 467         unsigned long flags;
 468
 469         if (!block)
 470                 return;
 471
 472         sp = (struct slob_page *)virt_to_page(block);
 473         if (!slob_page(sp)) {
 474                 /* on the big block list */
 475                 spin_lock_irqsave(&block_lock, flags);
 476                 for (bb = bigblocks; bb; last = &bb->next, bb = bb->next) {
 477                         if (bb->pages == block) {
 478                                 *last = bb->next;
 479                                 spin_unlock_irqrestore(&block_lock, flags);
 480                                 free_pages((unsigned long)block, bb->order);
 481                                 slob_free(bb, sizeof(bigblock_t));
 482                                 return;
 483                         }
 484                 }
 485                 spin_unlock_irqrestore(&block_lock, flags);
 486                 WARN_ON(1);
 487                 return;
 488         }
 489
 490         m = (slob_t *)block - 1;
 491         slob_free(m, m->units + SLOB_UNIT);
 492         return;
 493 }
 494
 495 EXPORT_SYMBOL(kfree);
 496
 497 size_t ksize(const void *block)
 498 {
 499         struct slob_page *sp;
 500         bigblock_t *bb;
 501         unsigned long flags;
 502
 503         if (!block)
 504                 return 0;
 505
 506         sp = (struct slob_page *)virt_to_page(block);
 507         if (!slob_page(sp)) {
 508                 spin_lock_irqsave(&block_lock, flags);
 509                 for (bb = bigblocks; bb; bb = bb->next)
 510                         if (bb->pages == block) {
 511                                 spin_unlock_irqrestore(&slob_lock, flags);
 512                                 return PAGE_SIZE << bb->order;
 513                         }
 514                 spin_unlock_irqrestore(&block_lock, flags);
 515         }
 516
 517         return ((slob_t *)block - 1)->units + SLOB_UNIT;
 518 }
 519
 520 struct kmem_cache {
 521         unsigned int size, align;
 522         unsigned long flags;
 523         const char *name;
 524         void (*ctor)(void *, struct kmem_cache *, unsigned long);
 525 };
 526
 527 struct kmem_cache *kmem_cache_create(const char *name, size_t size,
 528         size_t align, unsigned long flags,
 529         void (*ctor)(void*, struct kmem_cache *, unsigned long),
 530         void (*dtor)(void*, struct kmem_cache *, unsigned long))
 531 {
 532         struct kmem_cache *c;
 533
 534         c = slob_alloc(sizeof(struct kmem_cache), flags, 0);
 535
 536         if (c) {
 537                 c->name = name;
 538                 c->size = size;
 539                 if (flags & SLAB_DESTROY_BY_RCU) {
 540                         /* leave room for rcu footer at the end of object */
 541                         c->size += sizeof(struct slob_rcu);
 542                 }
 543                 c->flags = flags;
 544                 c->ctor = ctor;
 545                 /* ignore alignment unless it's forced */
 546                 c->align = (flags & SLAB_HWCACHE_ALIGN) ? SLOB_ALIGN : 0;
 547                 if (c->align < align)
 548                         c->align = align;
 549         } else if (flags & SLAB_PANIC)
 550                 panic("Cannot create slab cache %s\n", name);
 551
 552         return c;
 553 }
 554 EXPORT_SYMBOL(kmem_cache_create);
 555
 556 void kmem_cache_destroy(struct kmem_cache *c)
 557 {
 558         slob_free(c, sizeof(struct kmem_cache));
 559 }
 560 EXPORT_SYMBOL(kmem_cache_destroy);
 561
 562 void *kmem_cache_alloc(struct kmem_cache *c, gfp_t flags)
 563 {
 564         void *b;
 565
 566         if (c->size < PAGE_SIZE)
 567                 b = slob_alloc(c->size, flags, c->align);
 568         else
 569                 b = (void *)__get_free_pages(flags, get_order(c->size));
 570
 571         if (c->ctor)
 572                 c->ctor(b, c, 0);
 573
 574         return b;
 575 }
 576 EXPORT_SYMBOL(kmem_cache_alloc);
 577
 578 void *kmem_cache_zalloc(struct kmem_cache *c, gfp_t flags)
 579 {
 580         void *ret = kmem_cache_alloc(c, flags);
 581         if (ret)
 582                 memset(ret, 0, c->size);
 583
 584         return ret;
 585 }
 586 EXPORT_SYMBOL(kmem_cache_zalloc);
 587
 588 static void __kmem_cache_free(void *b, int size)
 589 {
 590         if (size < PAGE_SIZE)
 591                 slob_free(b, size);
 592         else
 593                 free_pages((unsigned long)b, get_order(size));
 594 }
 595
 596 static void kmem_rcu_free(struct rcu_head *head)
 597 {
 598         struct slob_rcu *slob_rcu = (struct slob_rcu *)head;
 599         void *b = (void *)slob_rcu - (slob_rcu->size - sizeof(struct slob_rcu));
 600
 601         __kmem_cache_free(b, slob_rcu->size);
 602 }
 603
 604 void kmem_cache_free(struct kmem_cache *c, void *b)
 605 {
 606         if (unlikely(c->flags & SLAB_DESTROY_BY_RCU)) {
 607                 struct slob_rcu *slob_rcu;
 608                 slob_rcu = b + (c->size - sizeof(struct slob_rcu));
 609                 INIT_RCU_HEAD(&slob_rcu->head);
 610                 slob_rcu->size = c->size;
 611                 call_rcu(&slob_rcu->head, kmem_rcu_free);
 612         } else {
 613                 __kmem_cache_free(b, c->size);
 614         }
 615 }
 616 EXPORT_SYMBOL(kmem_cache_free);
 617
 618 unsigned int kmem_cache_size(struct kmem_cache *c)
 619 {
 620         return c->size;
 621 }
 622 EXPORT_SYMBOL(kmem_cache_size);
 623
 624 const char *kmem_cache_name(struct kmem_cache *c)
 625 {
 626         return c->name;
 627 }
 628 EXPORT_SYMBOL(kmem_cache_name);
 629
 630 int kmem_cache_shrink(struct kmem_cache *d)
 631 {
 632         return 0;
 633 }
 634 EXPORT_SYMBOL(kmem_cache_shrink);
 635
 636 int kmem_ptr_validate(struct kmem_cache *a, const void *b)
 637 {
 638         return 0;
 639 }
 640
 641 void __init kmem_cache_init(void)
 642 {
 643 }