git.ozlabs.org Git - ccan/blob - ccan/alloc/alloc.c

   1 #include <unistd.h>
   2 #include <stdint.h>
   3 #include <string.h>
   4 #include <limits.h>
   5 #include <assert.h>
   6 #include <stdlib.h>
   7 #include "alloc.h"
   8 #include <ccan/build_assert/build_assert.h>
   9 #include <ccan/likely/likely.h>
  10 #include <ccan/short_types/short_types.h>
  11 #include "config.h"
  12
  13 /*
  14    Inspired by (and parts taken from) Andrew Tridgell's alloc_mmap:
  15    http://samba.org/~tridge/junkcode/alloc_mmap/
  16
  17    Copyright (C) Andrew Tridgell 2007
  18
  19    This library is free software; you can redistribute it and/or
  20    modify it under the terms of the GNU Lesser General Public
  21    License as published by the Free Software Foundation; either
  22    version 2 of the License, or (at your option) any later version.
  23
  24    This library is distributed in the hope that it will be useful,
  25    but WITHOUT ANY WARRANTY; without even the implied warranty of
  26    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  27    Lesser General Public License for more details.
  28
  29    You should have received a copy of the GNU Lesser General Public
  30    License along with this library; if not, write to the Free Software
  31    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  32  */
  33
  34 #if 0 /* Until we have the tiny allocator working, go down to 1 MB */
  35
  36 /* We divide the pool into this many large pages (nearest power of 2) */
  37 #define MAX_PAGES (1024UL)
  38
  39 /* 32 small pages == 1 large page. */
  40 #define BITS_FROM_SMALL_TO_LARGE_PAGE 5
  41
  42 #else
  43
  44 #define MAX_PAGES (128UL)
  45 #define BITS_FROM_SMALL_TO_LARGE_PAGE 4
  46
  47 #endif
  48
  49 /* Smallest pool size for this scheme: 512-byte small pages.  That's
  50  * 4/8% overhead for 32/64 bit. */
  51 #define MIN_USEFUL_SIZE (MAX_PAGES << (9 + BITS_FROM_SMALL_TO_LARGE_PAGE))
  52
  53 /* Every 4 buckets, we jump up a power of 2. ...8 10 12 14 16 20 24 28 32... */
  54 #define INTER_BUCKET_SPACE 4
  55
  56 /* FIXME: Figure this out properly. */
  57 #define MAX_SIZE (1 << 30)
  58
  59 /* How few object to fit in a page before using a larger one? (8) */
  60 #define MAX_PAGE_OBJECT_ORDER   3
  61
  62 #define BITS_PER_LONG (sizeof(long) * CHAR_BIT)
  63
  64 struct bucket_state {
  65         unsigned long elements_per_page;
  66         unsigned long page_list;
  67         unsigned long full_list;
  68 };
  69
  70 struct header {
  71         /* 1024 bit bitmap of which pages are large. */
  72         unsigned long pagesize[MAX_PAGES / BITS_PER_LONG];
  73
  74         /* List of unused small/large pages. */
  75         unsigned long small_free_list;
  76         unsigned long large_free_list;
  77
  78         /* This is less defined: we have two buckets for each power of 2 */
  79         struct bucket_state bs[1];
  80 };
  81
  82 struct page_header {
  83         unsigned long next, prev;
  84         u32 elements_used;
  85         /* FIXME: Pack this in somewhere... */
  86         u8 bucket;
  87         unsigned long used[1]; /* One bit per element. */
  88 };
  89
  90 /* 2 bit for every byte to allocate. */
  91 static void tiny_alloc_init(void *pool, unsigned long poolsize)
  92 {
  93 /* FIXME */
  94 }
  95
  96 static void *tiny_alloc_get(void *pool, unsigned long poolsize,
  97                             unsigned long size, unsigned long align)
  98 {
  99 /* FIXME */
 100         return NULL;
 101 }
 102
 103 static void tiny_alloc_free(void *pool, unsigned long poolsize, void *free)
 104 {
 105 /* FIXME */
 106 }
 107
 108 static unsigned long tiny_alloc_size(void *pool, unsigned long poolsize,
 109                                       void *p)
 110 {
 111 /* FIXME */
 112         return 0;
 113 }
 114
 115 static bool tiny_alloc_check(void *pool, unsigned long poolsize)
 116 {
 117 /* FIXME */
 118         return true;
 119 }
 120
 121 static unsigned int fls(unsigned long val)
 122 {
 123 #if HAVE_BUILTIN_CLZL
 124         /* This is significantly faster! */
 125         return val ? sizeof(long) * CHAR_BIT - __builtin_clzl(val) : 0;
 126 #else
 127         unsigned int r = 32;
 128
 129         if (!val)
 130                 return 0;
 131         if (!(val & 0xffff0000u)) {
 132                 val <<= 16;
 133                 r -= 16;
 134         }
 135         if (!(val & 0xff000000u)) {
 136                 val <<= 8;
 137                 r -= 8;
 138         }
 139         if (!(val & 0xf0000000u)) {
 140                 val <<= 4;
 141                 r -= 4;
 142         }
 143         if (!(val & 0xc0000000u)) {
 144                 val <<= 2;
 145                 r -= 2;
 146         }
 147         if (!(val & 0x80000000u)) {
 148                 val <<= 1;
 149                 r -= 1;
 150         }
 151         return r;
 152 #endif
 153 }
 154
 155 /* FIXME: Move to bitops. */
 156 static unsigned int ffsl(unsigned long val)
 157 {
 158 #if HAVE_BUILTIN_FFSL
 159         /* This is significantly faster! */
 160         return __builtin_ffsl(val);
 161 #else
 162         unsigned int r = 1;
 163
 164         if (!val)
 165                 return 0;
 166         if (sizeof(long) == sizeof(u64)) {
 167                 if (!(val & 0xffffffff)) {
 168                         /* Workaround gcc warning on 32-bit:
 169                            error: right shift count >= width of type */
 170                         u64 tmp = val;
 171                         tmp >>= 32;
 172                         val = tmp;
 173                         r += 32;
 174                 }
 175         }
 176         if (!(val & 0xffff)) {
 177                 val >>= 16;
 178                 r += 16;
 179         }
 180         if (!(val & 0xff)) {
 181                 val >>= 8;
 182                 r += 8;
 183         }
 184         if (!(val & 0xf)) {
 185                 val >>= 4;
 186                 r += 4;
 187         }
 188         if (!(val & 3)) {
 189                 val >>= 2;
 190                 r += 2;
 191         }
 192         if (!(val & 1)) {
 193                 val >>= 1;
 194                 r += 1;
 195         }
 196         return r;
 197 #endif
 198 }
 199
 200 static unsigned int popcount(unsigned long val)
 201 {
 202 #if HAVE_BUILTIN_POPCOUNTL
 203         return __builtin_popcountl(val);
 204 #else
 205         if (sizeof(long) == sizeof(u64)) {
 206                 u64 v = val;
 207                 v = (v & 0x5555555555555555ULL)
 208                         + ((v >> 1) & 0x5555555555555555ULL);
 209                 v = (v & 0x3333333333333333ULL)
 210                         + ((v >> 1) & 0x3333333333333333ULL);
 211                 v = (v & 0x0F0F0F0F0F0F0F0FULL)
 212                         + ((v >> 1) & 0x0F0F0F0F0F0F0F0FULL);
 213                 v = (v & 0x00FF00FF00FF00FFULL)
 214                         + ((v >> 1) & 0x00FF00FF00FF00FFULL);
 215                 v = (v & 0x0000FFFF0000FFFFULL)
 216                         + ((v >> 1) & 0x0000FFFF0000FFFFULL);
 217                 v = (v & 0x00000000FFFFFFFFULL)
 218                         + ((v >> 1) & 0x00000000FFFFFFFFULL);
 219                 return v;
 220         }
 221         val = (val & 0x55555555ULL) + ((val >> 1) & 0x55555555ULL);
 222         val = (val & 0x33333333ULL) + ((val >> 1) & 0x33333333ULL);
 223         val = (val & 0x0F0F0F0FULL) + ((val >> 1) & 0x0F0F0F0FULL);
 224         val = (val & 0x00FF00FFULL) + ((val >> 1) & 0x00FF00FFULL);
 225         val = (val & 0x0000FFFFULL) + ((val >> 1) & 0x0000FFFFULL);
 226         return val;
 227 #endif
 228 }
 229
 230 /*
 231  * Every 4 buckets, the size doubles.
 232  * Between buckets, sizes increase linearly.
 233  *
 234  * eg. bucket 40 = 2^10                 = 1024
 235  *     bucket 41 = 2^10 + 2^10*4        = 1024 + 256
 236  *     bucket 42 = 2^10 + 2^10*4        = 1024 + 512
 237  *     bucket 43 = 2^10 + 2^10*4        = 1024 + 768
 238  *     bucket 45 = 2^11                 = 2048
 239  *
 240  * Care is taken to handle low numbered buckets, at cost of overflow.
 241  */
 242 static unsigned long bucket_to_size(unsigned int bucket)
 243 {
 244         unsigned long base = 1 << (bucket / INTER_BUCKET_SPACE);
 245         return base + ((bucket % INTER_BUCKET_SPACE)
 246                        << (bucket / INTER_BUCKET_SPACE))
 247                 / INTER_BUCKET_SPACE;
 248 }
 249
 250 /*
 251  * Say size is 10.
 252  *   fls(size/2) == 3.  1 << 3 == 8, so we're 2 too large, out of a possible
 253  * 8 too large.  That's 1/4 of the way to the next power of 2 == 1 bucket.
 254  *
 255  * We make sure we round up.  Note that this fails on 32 bit at size
 256  * 1879048193 (around bucket 120).
 257  */
 258 static unsigned int size_to_bucket(unsigned long size)
 259 {
 260         unsigned int base = fls(size/2);
 261         unsigned long overshoot;
 262
 263         overshoot = size - (1 << base);
 264         return base * INTER_BUCKET_SPACE
 265                 + ((overshoot * INTER_BUCKET_SPACE + (1 << base)-1) >> base);
 266 }
 267
 268 static unsigned int large_page_bits(unsigned long poolsize)
 269 {
 270         return fls(poolsize / MAX_PAGES / 2);
 271 }
 272
 273 static unsigned long align_up(unsigned long x, unsigned long align)
 274 {
 275         return (x + align - 1) & ~(align - 1);
 276 }
 277
 278 static void *from_off(struct header *head, unsigned long off)
 279 {
 280         return (char *)head + off;
 281 }
 282
 283 static unsigned long to_off(struct header *head, void *p)
 284 {
 285         return (char *)p - (char *)head;
 286 }
 287
 288 static size_t used_size(unsigned int num_elements)
 289 {
 290         return (num_elements + BITS_PER_LONG-1) / BITS_PER_LONG;
 291 }
 292
 293 /*
 294  * We always align the first entry to the lower power of 2.
 295  * eg. the 12-byte bucket gets 8-byte aligned.  The 4096-byte bucket
 296  * gets 4096-byte aligned.
 297  */
 298 static unsigned long page_header_size(unsigned int align_bits,
 299                                       unsigned long num_elements)
 300 {
 301         unsigned long size;
 302
 303         size = sizeof(struct page_header)
 304                 - sizeof(((struct page_header *)0)->used)
 305                 + used_size(num_elements);
 306         return align_up(size, 1 << align_bits);
 307 }
 308
 309 static void add_to_list(struct header *head,
 310                         unsigned long *list, struct page_header *ph)
 311 {
 312         unsigned long h = *list, offset = to_off(head, ph);
 313
 314         ph->next = h;
 315         if (h) {
 316                 struct page_header *prev = from_off(head, h);
 317                 assert(prev->prev == 0);
 318                 prev->prev = offset;
 319         }
 320         *list = offset;
 321         ph->prev = 0;
 322 }
 323
 324 static void del_from_list(struct header *head,
 325                           unsigned long *list, struct page_header *ph)
 326 {
 327         /* Front of list? */
 328         if (ph->prev == 0) {
 329                 *list = ph->next;
 330         } else {
 331                 struct page_header *prev = from_off(head, ph->prev);
 332                 prev->next = ph->next;
 333         }
 334         if (ph->next != 0) {
 335                 struct page_header *next = from_off(head, ph->next);
 336                 next->prev = ph->prev;
 337         }
 338 }
 339
 340 static unsigned long pop_from_list(struct header *head,
 341                                    unsigned long *list)
 342 {
 343         unsigned long h = *list;
 344         struct page_header *ph = from_off(head, h);
 345
 346         if (likely(h)) {
 347                 *list = ph->next;
 348                 if (*list) {
 349                         struct page_header *next = from_off(head, *list);
 350                         next->prev = 0;
 351                 }
 352         }
 353         return h;
 354 }
 355
 356 static void add_small_page_to_freelist(struct header *head,
 357                                        struct page_header *ph)
 358 {
 359         add_to_list(head, &head->small_free_list, ph);
 360 }
 361
 362 static void add_large_page_to_freelist(struct header *head,
 363                                        struct page_header *ph)
 364 {
 365         add_to_list(head, &head->large_free_list, ph);
 366 }
 367
 368 static void add_to_bucket_list(struct header *head,
 369                                struct bucket_state *bs,
 370                                struct page_header *ph)
 371 {
 372         add_to_list(head, &bs->page_list, ph);
 373 }
 374
 375 static void del_from_bucket_list(struct header *head,
 376                                  struct bucket_state *bs,
 377                                  struct page_header *ph)
 378 {
 379         del_from_list(head, &bs->page_list, ph);
 380 }
 381
 382 static void del_from_bucket_full_list(struct header *head,
 383                                       struct bucket_state *bs,
 384                                       struct page_header *ph)
 385 {
 386         del_from_list(head, &bs->full_list, ph);
 387 }
 388
 389 static void add_to_bucket_full_list(struct header *head,
 390                                     struct bucket_state *bs,
 391                                     struct page_header *ph)
 392 {
 393         add_to_list(head, &bs->full_list, ph);
 394 }
 395
 396 static void clear_bit(unsigned long bitmap[], unsigned int off)
 397 {
 398         bitmap[off / BITS_PER_LONG] &= ~(1 << (off % BITS_PER_LONG));
 399 }
 400
 401 static bool test_bit(const unsigned long bitmap[], unsigned int off)
 402 {
 403         return bitmap[off / BITS_PER_LONG] & (1 << (off % BITS_PER_LONG));
 404 }
 405
 406 static void set_bit(unsigned long bitmap[], unsigned int off)
 407 {
 408         bitmap[off / BITS_PER_LONG] |= (1 << (off % BITS_PER_LONG));
 409 }
 410
 411 /* There must be a bit to be found. */
 412 static unsigned int find_free_bit(const unsigned long bitmap[])
 413 {
 414         unsigned int i;
 415
 416         for (i = 0; bitmap[i] == -1UL; i++);
 417         return (i*BITS_PER_LONG) + ffsl(~bitmap[i]) - 1;
 418 }
 419
 420 /* How many elements can we fit in a page? */
 421 static unsigned long elements_per_page(unsigned long align_bits,
 422                                        unsigned long esize,
 423                                        unsigned long psize)
 424 {
 425         unsigned long num, overhead;
 426
 427         /* First approximation: no extra room for bitmap. */
 428         overhead = align_up(sizeof(struct page_header), 1 << align_bits);
 429         num = (psize - overhead) / esize;
 430
 431         while (page_header_size(align_bits, num) + esize * num > psize)
 432                 num--;
 433         return num;
 434 }
 435
 436 static bool large_page_bucket(unsigned int bucket, unsigned long poolsize)
 437 {
 438         unsigned int sp_bits;
 439         unsigned long max_smallsize;
 440
 441         sp_bits = large_page_bits(poolsize) - BITS_FROM_SMALL_TO_LARGE_PAGE;
 442         /* Note: this doesn't take into account page header. */
 443         max_smallsize = (1UL << sp_bits) >> MAX_PAGE_OBJECT_ORDER;
 444
 445         return bucket_to_size(bucket) > max_smallsize;
 446 }
 447
 448 static unsigned int max_bucket(unsigned int lp_bits)
 449 {
 450         return (lp_bits - MAX_PAGE_OBJECT_ORDER) * INTER_BUCKET_SPACE;
 451 }
 452
 453 void alloc_init(void *pool, unsigned long poolsize)
 454 {
 455         struct header *head = pool;
 456         struct page_header *ph;
 457         unsigned int lp_bits, sp_bits, num_buckets;
 458         unsigned long header_size, i;
 459
 460         if (poolsize < MIN_USEFUL_SIZE) {
 461                 tiny_alloc_init(pool, poolsize);
 462                 return;
 463         }
 464
 465         lp_bits = large_page_bits(poolsize);
 466         sp_bits = lp_bits - BITS_FROM_SMALL_TO_LARGE_PAGE;
 467
 468         num_buckets = max_bucket(lp_bits);
 469
 470         head = pool;
 471         header_size = sizeof(*head) + sizeof(head->bs) * (num_buckets-1);
 472
 473         memset(head, 0, header_size);
 474         for (i = 0; i < num_buckets; i++) {
 475                 unsigned long pagesize;
 476
 477                 if (large_page_bucket(i, poolsize))
 478                         pagesize = 1UL << lp_bits;
 479                 else
 480                         pagesize = 1UL << sp_bits;
 481
 482                 head->bs[i].elements_per_page
 483                         = elements_per_page(i / INTER_BUCKET_SPACE,
 484                                             bucket_to_size(i),
 485                                             pagesize);
 486         }
 487
 488         /* They start as all large pages. */
 489         memset(head->pagesize, 0xFF, sizeof(head->pagesize));
 490         /* FIXME: small pages for last bit? */
 491
 492         /* Split first page into small pages. */
 493         assert(header_size << (1UL << lp_bits));
 494         clear_bit(head->pagesize, 0);
 495
 496         /* Skip over page(s) used by header, add rest to free list */
 497         for (i = align_up(header_size, (1 << sp_bits)) >> sp_bits;
 498              i < (1 << BITS_FROM_SMALL_TO_LARGE_PAGE);
 499              i++) {
 500                 ph = from_off(head, i<<sp_bits);
 501                 ph->elements_used = 0;
 502                 add_small_page_to_freelist(head, ph);
 503         }
 504
 505         /* Add the rest of the pages as large pages. */
 506         i = (1 << lp_bits);
 507         while (i + (1 << lp_bits) <= poolsize) {
 508                 ph = from_off(head, i);
 509                 ph->elements_used = 0;
 510                 add_large_page_to_freelist(head, ph);
 511                 i += (1 << lp_bits);
 512         }
 513 }
 514
 515 /* A large page worth of small pages are free: delete them from free list. */
 516 static void del_large_from_small_free_list(struct header *head,
 517                                            struct page_header *ph,
 518                                            unsigned int sp_bits)
 519 {
 520         unsigned long i;
 521
 522         for (i = 0; i < (1 << BITS_FROM_SMALL_TO_LARGE_PAGE); i++) {
 523                 del_from_list(head, &head->small_free_list,
 524                               (void *)ph + (i << sp_bits));
 525         }
 526 }
 527
 528 static bool all_empty(struct header *head, unsigned long off, unsigned sp_bits)
 529 {
 530         unsigned long i;
 531
 532         for (i = 0; i < (1 << BITS_FROM_SMALL_TO_LARGE_PAGE); i++) {
 533                 struct page_header *ph = from_off(head, off + (i << sp_bits));
 534                 if (ph->elements_used)
 535                         return false;
 536         }
 537         return true;
 538 }
 539
 540 static unsigned long get_large_page(struct header *head,
 541                                     unsigned long poolsize)
 542 {
 543         unsigned long lp_bits, sp_bits, i, page;
 544
 545         page = pop_from_list(head, &head->large_free_list);
 546         if (likely(page))
 547                 return page;
 548
 549         /* Look for small pages to coalesce, after first large page. */
 550         lp_bits = large_page_bits(poolsize);
 551         sp_bits = lp_bits - BITS_FROM_SMALL_TO_LARGE_PAGE;
 552
 553         for (i = (1 << lp_bits); i < poolsize; i += (1 << lp_bits)) {
 554                 /* Already a large page? */
 555                 if (test_bit(head->pagesize, i >> lp_bits))
 556                         continue;
 557                 if (all_empty(head, i, sp_bits)) {
 558                         struct page_header *ph = from_off(head, i);
 559                         set_bit(head->pagesize, i >> lp_bits);
 560                         del_large_from_small_free_list(head, ph, sp_bits);
 561                         add_large_page_to_freelist(head, ph);
 562                 }
 563         }
 564
 565         return pop_from_list(head, &head->large_free_list);
 566 }
 567
 568 /* Returns small page. */
 569 static unsigned long break_up_large_page(struct header *head,
 570                                          unsigned long psize,
 571                                          unsigned long lpage)
 572 {
 573         unsigned long lp_bits, sp_bits, i;
 574
 575         lp_bits = large_page_bits(psize);
 576         sp_bits = lp_bits - BITS_FROM_SMALL_TO_LARGE_PAGE;
 577         clear_bit(head->pagesize, lpage >> lp_bits);
 578
 579         for (i = 1; i < (1 << BITS_FROM_SMALL_TO_LARGE_PAGE); i++)
 580                 add_small_page_to_freelist(head,
 581                                            from_off(head,
 582                                                     lpage + (i<<sp_bits)));
 583
 584         return lpage;
 585 }
 586
 587 static unsigned long get_small_page(struct header *head,
 588                                     unsigned long poolsize)
 589 {
 590         unsigned long ret;
 591
 592         ret = pop_from_list(head, &head->small_free_list);
 593         if (likely(ret))
 594                 return ret;
 595         ret = get_large_page(head, poolsize);
 596         if (likely(ret))
 597                 ret = break_up_large_page(head, poolsize, ret);
 598         return ret;
 599 }
 600
 601 void *alloc_get(void *pool, unsigned long poolsize,
 602                 unsigned long size, unsigned long align)
 603 {
 604         struct header *head = pool;
 605         unsigned int bucket;
 606         unsigned long i;
 607         struct bucket_state *bs;
 608         struct page_header *ph;
 609
 610         if (poolsize < MIN_USEFUL_SIZE) {
 611                 return tiny_alloc_get(pool, poolsize, size, align);
 612         }
 613
 614         size = align_up(size, align);
 615         if (unlikely(!size))
 616                 size = 1;
 617         bucket = size_to_bucket(size);
 618
 619         if (bucket >= max_bucket(large_page_bits(poolsize))) {
 620                 /* FIXME: huge alloc. */
 621                 return NULL;
 622         }
 623
 624         bs = &head->bs[bucket];
 625
 626         if (!bs->page_list) {
 627                 struct page_header *ph;
 628
 629                 if (large_page_bucket(bucket, poolsize))
 630                         bs->page_list = get_large_page(head, poolsize);
 631                 else
 632                         bs->page_list = get_small_page(head, poolsize);
 633                 /* FIXME: Try large-aligned alloc?  Header stuffing? */
 634                 if (unlikely(!bs->page_list))
 635                         return NULL;
 636                 ph = from_off(head, bs->page_list);
 637                 ph->bucket = bucket;
 638                 ph->elements_used = 0;
 639                 ph->next = 0;
 640                 memset(ph->used, 0, used_size(bs->elements_per_page));
 641         }
 642
 643         ph = from_off(head, bs->page_list);
 644
 645         i = find_free_bit(ph->used);
 646         set_bit(ph->used, i);
 647         ph->elements_used++;
 648
 649         /* check if this page is now full */
 650         if (unlikely(ph->elements_used == bs->elements_per_page)) {
 651                 del_from_bucket_list(head, bs, ph);
 652                 add_to_bucket_full_list(head, bs, ph);
 653         }
 654
 655         return (char *)ph + page_header_size(ph->bucket / INTER_BUCKET_SPACE,
 656                                              bs->elements_per_page)
 657                + i * bucket_to_size(bucket);
 658 }
 659
 660 void alloc_free(void *pool, unsigned long poolsize, void *free)
 661 {
 662         struct header *head = pool;
 663         struct bucket_state *bs;
 664         unsigned int pagebits;
 665         unsigned long i, pgoffset, offset = (char *)free - (char *)pool;
 666         bool smallpage;
 667         struct page_header *ph;
 668
 669         if (poolsize < MIN_USEFUL_SIZE) {
 670                 return tiny_alloc_free(pool, poolsize, free);
 671         }
 672
 673         /* Get page header. */
 674         pagebits = large_page_bits(poolsize);
 675         if (!test_bit(head->pagesize, offset >> pagebits)) {
 676                 smallpage = true;
 677                 pagebits -= BITS_FROM_SMALL_TO_LARGE_PAGE;
 678         } else
 679                 smallpage = false;
 680
 681         /* Step back to page header. */
 682         ph = from_off(head, offset & ~((1UL << pagebits) - 1));
 683         bs = &head->bs[ph->bucket];
 684         pgoffset = (offset & ((1UL << pagebits) - 1))
 685                 - page_header_size(ph->bucket / INTER_BUCKET_SPACE,
 686                                    bs->elements_per_page);
 687
 688         if (unlikely(ph->elements_used == bs->elements_per_page)) {
 689                 del_from_bucket_full_list(head, bs, ph);
 690                 add_to_bucket_list(head, bs, ph);
 691         }
 692
 693         /* Which element are we? */
 694         i = pgoffset / bucket_to_size(ph->bucket);
 695         clear_bit(ph->used, i);
 696         ph->elements_used--;
 697
 698         if (unlikely(ph->elements_used == 0)) {
 699                 bs = &head->bs[ph->bucket];
 700                 del_from_bucket_list(head, bs, ph);
 701                 if (smallpage)
 702                         add_small_page_to_freelist(head, ph);
 703                 else
 704                         add_large_page_to_freelist(head, ph);
 705         }
 706 }
 707
 708 unsigned long alloc_size(void *pool, unsigned long poolsize, void *p)
 709 {
 710         struct header *head = pool;
 711         unsigned int pagebits;
 712         unsigned long offset = (char *)p - (char *)pool;
 713         struct page_header *ph;
 714
 715         if (poolsize < MIN_USEFUL_SIZE)
 716                 return tiny_alloc_size(pool, poolsize, p);
 717
 718         /* Get page header. */
 719         pagebits = large_page_bits(poolsize);
 720         if (!test_bit(head->pagesize, offset >> pagebits))
 721                 pagebits -= BITS_FROM_SMALL_TO_LARGE_PAGE;
 722
 723         /* Step back to page header. */
 724         ph = from_off(head, offset & ~((1UL << pagebits) - 1));
 725         return bucket_to_size(ph->bucket);
 726 }
 727
 728 /* Useful for gdb breakpoints. */
 729 static bool check_fail(void)
 730 {
 731         return false;
 732 }
 733
 734 static unsigned long count_bits(const unsigned long bitmap[],
 735                                 unsigned long limit)
 736 {
 737         unsigned long i, count = 0;
 738
 739         while (limit >= BITS_PER_LONG) {
 740                 count += popcount(bitmap[0]);
 741                 bitmap++;
 742                 limit -= BITS_PER_LONG;
 743         }
 744
 745         for (i = 0; i < limit; i++)
 746                 if (test_bit(bitmap, i))
 747                         count++;
 748         return count;
 749 }
 750
 751 static bool out_of_bounds(unsigned long off,
 752                           unsigned long pagesize,
 753                           unsigned long poolsize)
 754 {
 755         return (off > poolsize || off + pagesize > poolsize);
 756 }
 757
 758 static bool check_bucket(struct header *head,
 759                          unsigned long poolsize,
 760                          unsigned long pages[],
 761                          struct bucket_state *bs,
 762                          unsigned int bindex)
 763 {
 764         bool lp_bucket = large_page_bucket(bindex, poolsize);
 765         struct page_header *ph;
 766         unsigned long taken, i, prev, pagesize, sp_bits, lp_bits;
 767
 768         lp_bits = large_page_bits(poolsize);
 769         sp_bits = lp_bits - BITS_FROM_SMALL_TO_LARGE_PAGE;
 770
 771         pagesize = 1UL << (lp_bucket ? lp_bits : sp_bits);
 772
 773         /* This many elements fit? */
 774         taken = page_header_size(bindex / INTER_BUCKET_SPACE,
 775                                  bs->elements_per_page);
 776         taken += bucket_to_size(bindex) * bs->elements_per_page;
 777         if (taken > pagesize)
 778                 return check_fail();
 779
 780         /* One more wouldn't fit? */
 781         taken = page_header_size(bindex / INTER_BUCKET_SPACE,
 782                                  bs->elements_per_page + 1);
 783         taken += bucket_to_size(bindex) * (bs->elements_per_page + 1);
 784         if (taken <= pagesize)
 785                 return check_fail();
 786
 787         /* Walk used list. */
 788         prev = 0;
 789         for (i = bs->page_list; i; i = ph->next) {
 790                 /* Bad pointer? */
 791                 if (out_of_bounds(i, pagesize, poolsize))
 792                         return check_fail();
 793                 /* Wrong size page? */
 794                 if (!!test_bit(head->pagesize, i >> lp_bits) != lp_bucket)
 795                         return check_fail();
 796                 /* Not page boundary? */
 797                 if (i % pagesize)
 798                         return check_fail();
 799                 ph = from_off(head, i);
 800                 /* Linked list corrupt? */
 801                 if (ph->prev != prev)
 802                         return check_fail();
 803                 /* Already seen this page? */
 804                 if (test_bit(pages, i >> sp_bits))
 805                         return check_fail();
 806                 set_bit(pages, i >> sp_bits);
 807                 /* Empty or full? */
 808                 if (ph->elements_used == 0)
 809                         return check_fail();
 810                 if (ph->elements_used >= bs->elements_per_page)
 811                         return check_fail();
 812                 /* Used bits don't agree? */
 813                 if (ph->elements_used != count_bits(ph->used,
 814                                                     bs->elements_per_page))
 815                         return check_fail();
 816                 /* Wrong bucket? */
 817                 if (ph->bucket != bindex)
 818                         return check_fail();
 819                 prev = i;
 820         }
 821
 822         /* Walk full list. */
 823         prev = 0;
 824         for (i = bs->full_list; i; i = ph->next) {
 825                 /* Bad pointer? */
 826                 if (out_of_bounds(i, pagesize, poolsize))
 827                         return check_fail();
 828                 /* Wrong size page? */
 829                 if (!!test_bit(head->pagesize, i >> lp_bits) != lp_bucket)
 830                         return check_fail();
 831                 /* Not page boundary? */
 832                 if (i % pagesize)
 833                         return check_fail();
 834                 ph = from_off(head, i);
 835                 /* Linked list corrupt? */
 836                 if (ph->prev != prev)
 837                         return check_fail();
 838                 /* Already seen this page? */
 839                 if (test_bit(pages, i >> sp_bits))
 840                         return check_fail();
 841                 set_bit(pages, i >> sp_bits);
 842                 /* Not full? */
 843                 if (ph->elements_used != bs->elements_per_page)
 844                         return check_fail();
 845                 /* Used bits don't agree? */
 846                 if (ph->elements_used != count_bits(ph->used,
 847                                                     bs->elements_per_page))
 848                         return check_fail();
 849                 /* Wrong bucket? */
 850                 if (ph->bucket != bindex)
 851                         return check_fail();
 852                 prev = i;
 853         }
 854         return true;
 855 }
 856
 857 bool alloc_check(void *pool, unsigned long poolsize)
 858 {
 859         struct header *head = pool;
 860         unsigned long prev, i, lp_bits, sp_bits, header_size, num_buckets;
 861         struct page_header *ph;
 862         unsigned long pages[(MAX_PAGES << BITS_FROM_SMALL_TO_LARGE_PAGE)
 863                             / BITS_PER_LONG] = { 0 };
 864
 865         if (poolsize < MIN_USEFUL_SIZE)
 866                 return tiny_alloc_check(pool, poolsize);
 867
 868         lp_bits = large_page_bits(poolsize);
 869         sp_bits = lp_bits - BITS_FROM_SMALL_TO_LARGE_PAGE;
 870
 871         num_buckets = max_bucket(lp_bits);
 872
 873         header_size = sizeof(*head) + sizeof(head->bs) * (num_buckets-1);
 874
 875         /* First, set all bits taken by header. */
 876         for (i = 0; i < header_size; i += (1UL << sp_bits))
 877                 set_bit(pages, i >> sp_bits);
 878
 879         /* Check small page free list. */
 880         prev = 0;
 881         for (i = head->small_free_list; i; i = ph->next) {
 882                 /* Bad pointer? */
 883                 if (out_of_bounds(i, 1 << sp_bits, poolsize))
 884                         return check_fail();
 885                 /* Large page? */
 886                 if (test_bit(head->pagesize, i >> lp_bits))
 887                         return check_fail();
 888                 /* Not page boundary? */
 889                 if (i % (1 << sp_bits))
 890                         return check_fail();
 891                 ph = from_off(head, i);
 892                 /* Linked list corrupt? */
 893                 if (ph->prev != prev)
 894                         return check_fail();
 895                 /* Already seen this page? */
 896                 if (test_bit(pages, i >> sp_bits))
 897                         return check_fail();
 898                 set_bit(pages, i >> sp_bits);
 899                 prev = i;
 900         }
 901
 902         /* Check large page free list. */
 903         prev = 0;
 904         for (i = head->large_free_list; i; i = ph->next) {
 905                 /* Bad pointer? */
 906                 if (out_of_bounds(i, 1 << lp_bits, poolsize))
 907                         return check_fail();
 908                 /* Not large page? */
 909                 if (!test_bit(head->pagesize, i >> lp_bits))
 910                         return check_fail();
 911                 /* Not page boundary? */
 912                 if (i % (1 << lp_bits))
 913                         return check_fail();
 914                 ph = from_off(head, i);
 915                 /* Linked list corrupt? */
 916                 if (ph->prev != prev)
 917                         return check_fail();
 918                 /* Already seen this page? */
 919                 if (test_bit(pages, i >> sp_bits))
 920                         return check_fail();
 921                 set_bit(pages, i >> sp_bits);
 922                 prev = i;
 923         }
 924
 925         /* Check the buckets. */
 926         for (i = 0; i < max_bucket(lp_bits); i++) {
 927                 struct bucket_state *bs = &head->bs[i];
 928
 929                 if (!check_bucket(head, poolsize, pages, bs, i))
 930                         return false;
 931         }
 932
 933         /* Make sure every page accounted for. */
 934         for (i = 0; i < poolsize >> sp_bits; i++) {
 935                 if (!test_bit(pages, i))
 936                         return check_fail();
 937                 if (test_bit(head->pagesize,
 938                              i >> BITS_FROM_SMALL_TO_LARGE_PAGE)) {
 939                         /* Large page, skip rest. */
 940                         i += (1 << BITS_FROM_SMALL_TO_LARGE_PAGE) - 1;
 941                 }
 942         }
 943
 944         return true;
 945 }