alloc_mmap/alloc_mmap.c

   1 /*
   2   a mmap based memory allocator
   3
   4    Copyright (C) Andrew Tridgell 2007
   5
   6    This library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2 of the License, or (at your option) any later version.
  10
  11    This library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with this library; if not, write to the Free Software
  18    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  */
  20 /*
  21
  22   The basic aims of this allocator are:
  23
  24      - fast for small allocations
  25      - all memory comes from anonymous mmap
  26      - releases memory back to the OS as much as possible
  27      - no per-block prefix (so extremely low overhead)
  28      - very little paranoid checking in the code
  29      - thread safety optional at compile time
  30
  31   Design:
  32
  33       allocations are either 'small' or 'large' or 'memalign'
  34
  35       'large' allocations do a plain mmap, one per allocation. When
  36       you free you munmap. The 'large' allocations have a struct
  37       large_header prefix, so the returned pointer is not in fact on a
  38       page boundary.
  39
  40       'small' allocations come from a bucket allocator. There are
  41       a set of buckets, each larger than the previous by a constant
  42       factor. 'small' allocations do not have any prefix header before
  43       the allocation.
  44
  45       The meta-data for the small allocations comes at the start of
  46       the page. This meta-data contains a bitmap of what pieces of the
  47       page are currently used.
  48
  49       'memalign' allocations are for handling memlign()
  50       requests. These are horribly inefficient, using a singly linked
  51       list. Best to avoid this function.
  52
  53  */
  54 #include <stdio.h>
  55 #include <stdint.h>
  56 #include <unistd.h>
  57 #include <string.h>
  58 #include <strings.h>
  59 #include <stddef.h>
  60 #include <stdlib.h>
  61 #include <stdbool.h>
  62 #include <errno.h>
  63 #include <sys/mman.h>
  64 #ifdef THREAD_SAFE
  65 #include <pthread.h>
  66 #endif
  67
  68 #if (__GNUC__ >= 3)
  69 #define likely(x)   __builtin_expect(!!(x), 1)
  70 #define unlikely(x) __builtin_expect(!!(x), 0)
  71 #else
  72 #define likely(x) x
  73 #define unlikely(x) x
  74 #endif
  75
  76 #define MAX_BUCKETS     15
  77 #define BASE_BUCKET     16
  78 #define FREE_PAGE_LIMIT  2
  79 #define ALLOC_ALIGNMENT 16
  80 #define BUCKET_NEXT_SIZE(prev) ((3*(prev))/2)
  81 #define PID_CHECK        0
  82 #define BUCKET_LOOKUP_SIZE 128
  83 #define ALLOC_PARANOIA   0
  84
  85 /* you can hard code the page size in the Makefile for more speed */
  86 #ifndef PAGE_SIZE
  87 #define PAGE_SIZE state.page_size
  88 #endif
  89
  90 #ifndef MIN
  91 #define MIN(a,b) ((a)<(b)?(a):(b))
  92 #endif
  93
  94 #define ALIGN_SIZE(size) (((size)+(ALLOC_ALIGNMENT-1))&~(ALLOC_ALIGNMENT-1))
  95
  96 /* work out how many bytes aligning to ALLOC_ALIGNMENT plus at least sizeof(type)
  97    will cost */
  98 #define ALIGN_COST(type) ALIGN_SIZE(sizeof(type))
  99
 100 /* take a pointer, and move it up by at least one sizeof(type), aligned
 101    to the ALLOC_ALIGNMENT */
 102 #define ALIGN_UP(ptr, type) ((ALIGN_COST(type)+(intptr_t)(ptr)))
 103
 104 /* align to the start of the page, and return a type* */
 105 #define ALIGN_DOWN_PAGE(ptr, type) (type *)((~(intptr_t)(PAGE_SIZE-1)) & (intptr_t)(ptr))
 106
 107 /* work out the aligned size of a page header, given the size of the used[] array */
 108 #define PAGE_HEADER_SIZE(n) ALIGN_SIZE(offsetof(struct page_header, used) + 4*(((n)+31)/32))
 109
 110 /* see if a pointer is page aligned. This detects large memalign() pointers */
 111 #define IS_PAGE_ALIGNED(ptr) (((PAGE_SIZE-1) & (intptr_t)ptr) == 0)
 112
 113 /* move an element from the front of list1 to the front of list2 */
 114 #define MOVE_LIST_FRONT(list1, list2, p) \
 115         do { \
 116                 list1 = p->next;               \
 117                 if (list1) list1->prev = NULL; \
 118                 p->next = list2;                \
 119                 if (p->next) p->next->prev = p; \
 120                 list2 = p;                      \
 121         } while (0)
 122
 123 /* move an element from the anywhere in list1 to the front of list2 */
 124 #define MOVE_LIST(list1, list2, p) \
 125         do { \
 126                 if (p == list1) { \
 127                         MOVE_LIST_FRONT(list1, list2, p); \
 128                 } else { \
 129                         p->prev->next = p->next; \
 130                         if (p->next) p->next->prev = p->prev; \
 131                         (p)->next = list2; \
 132                         if (p->next) (p)->next->prev = (p);     \
 133                         p->prev = NULL; \
 134                         list2 = (p);    \
 135                 } \
 136         } while (0)
 137
 138 struct page_header {
 139         uint32_t num_pages; /* maps to num_pages in struct large_header */
 140         uint16_t elements_used;
 141         uint16_t num_elements;
 142 #if PID_CHECK
 143         pid_t pid;
 144 #endif
 145         struct page_header *next, *prev;
 146         struct bucket_state *bucket;
 147         uint32_t used[1];
 148 };
 149
 150 struct large_header {
 151         uint32_t num_pages;
 152 };
 153
 154 struct memalign_header {
 155         struct memalign_header *next;
 156         void *p;
 157         uint32_t num_pages;
 158 };
 159
 160 struct bucket_state {
 161         uint32_t alloc_limit;
 162         uint16_t elements_per_page;
 163 #ifdef THREAD_SAFE
 164         pthread_mutex_t mutex;
 165 #endif
 166         struct page_header *page_list;
 167         struct page_header *full_list;
 168 };
 169
 170 struct alloc_state {
 171         bool initialised;
 172         uint32_t page_size;
 173         uint32_t largest_bucket;
 174         uint32_t max_bucket;
 175 #if PID_CHECK
 176         pid_t pid;
 177 #endif
 178         /* this is a lookup table that maps size/ALLOC_ALIGNMENT to the right bucket */
 179         uint8_t bucket_lookup[BUCKET_LOOKUP_SIZE];
 180
 181         /* the rest of the structure may be written to after initialisation,
 182            so all accesses need to hold the mutex */
 183 #ifdef THREAD_SAFE
 184         pthread_mutex_t mutex;
 185 #endif
 186         uint32_t num_empty_pages;
 187         struct page_header *empty_list;
 188         struct memalign_header *memalign_list;
 189         struct bucket_state buckets[MAX_BUCKETS];
 190
 191 };
 192
 193 /* static state of the allocator */
 194 #ifndef THREAD_SAFE
 195 static struct alloc_state state;
 196 #else
 197 static struct alloc_state state = {
 198         .mutex = PTHREAD_MUTEX_INITIALIZER
 199 };
 200 #endif
 201
 202 #ifdef THREAD_SAFE
 203 #define THREAD_LOCK(mutexp) do { if (pthread_mutex_lock(mutexp) != 0) abort(); } while (0);
 204 #define THREAD_UNLOCK(mutexp) do { if (pthread_mutex_unlock(mutexp) != 0) abort(); } while (0);
 205 #else
 206 #define THREAD_LOCK(mutexp)
 207 #define THREAD_UNLOCK(mutexp)
 208 #endif
 209
 210 /*
 211   initialise the allocator
 212  */
 213 static void alloc_initialise(void)
 214 {
 215         int i, b=0, n;
 216         THREAD_LOCK(&state.mutex);
 217         state.page_size = getpagesize();
 218         if (PAGE_SIZE != state.page_size) {
 219                 abort();
 220         }
 221         for (i=0;i<MAX_BUCKETS;i++) {
 222                 struct bucket_state *bs = &state.buckets[i];
 223
 224 #ifdef THREAD_SAFE
 225                 pthread_mutex_init(&bs->mutex, NULL);
 226 #endif
 227
 228                 if (i == 0) {
 229                         int n;
 230                         bs->alloc_limit = BASE_BUCKET;
 231                         n = bs->alloc_limit/ALLOC_ALIGNMENT;
 232                         if (n > BUCKET_LOOKUP_SIZE) {
 233                                 n = BUCKET_LOOKUP_SIZE;
 234                         }
 235                         memset(&state.bucket_lookup[0], i, n);
 236                         b = n;
 237                 } else {
 238                         struct bucket_state *bs0 = &state.buckets[i-1];
 239                         bs->alloc_limit = ALIGN_SIZE(BUCKET_NEXT_SIZE(bs0->alloc_limit));
 240
 241                         /* squeeze in one more bucket if possible */
 242                         if (bs->alloc_limit > PAGE_SIZE - PAGE_HEADER_SIZE(1)) {
 243                                 bs->alloc_limit = PAGE_SIZE - PAGE_HEADER_SIZE(1);
 244                                 if (bs->alloc_limit == bs0->alloc_limit) break;
 245                         }
 246
 247                         n = (bs->alloc_limit - bs0->alloc_limit)/ALLOC_ALIGNMENT;
 248                         if (n + b > BUCKET_LOOKUP_SIZE) {
 249                                 n = BUCKET_LOOKUP_SIZE - b;
 250                         }
 251                         memset(&state.bucket_lookup[b], i, n);
 252                         b += n;
 253                 }
 254
 255                 /* work out how many elements can be put on each page */
 256                 bs->elements_per_page = (PAGE_SIZE-PAGE_HEADER_SIZE(1))/bs->alloc_limit;
 257                 while (bs->elements_per_page*bs->alloc_limit + PAGE_HEADER_SIZE(bs->elements_per_page) >
 258                        PAGE_SIZE) {
 259                         bs->elements_per_page--;
 260                 }
 261                 if (unlikely(bs->elements_per_page < 1)) {
 262                         break;
 263                 }
 264         }
 265         state.max_bucket = i-1;
 266         state.largest_bucket = state.buckets[state.max_bucket].alloc_limit;
 267         state.initialised = true;
 268 #if PID_CHECK
 269         state.pid = getpid();
 270 #endif
 271         THREAD_UNLOCK(&state.mutex);
 272 }
 273
 274 #if PID_CHECK
 275 static void alloc_pid_handler(void)
 276 {
 277         state.pid = getpid();
 278 }
 279 #endif
 280
 281 /*
 282   large allocation function - use mmap per allocation
 283  */
 284 static void *alloc_large(size_t size)
 285 {
 286         uint32_t num_pages;
 287         struct large_header *lh;
 288
 289         num_pages = (size+ALIGN_COST(struct large_header)+(PAGE_SIZE-1))/PAGE_SIZE;
 290
 291         /* check for wrap */
 292         if (unlikely(num_pages < size/PAGE_SIZE)) {
 293                 return NULL;
 294         }
 295
 296         lh = (struct large_header *)mmap(0, num_pages*PAGE_SIZE, PROT_READ | PROT_WRITE,
 297                                          MAP_ANON | MAP_PRIVATE, -1, 0);
 298         if (unlikely(lh == (struct large_header *)-1)) {
 299                 return NULL;
 300         }
 301
 302         lh->num_pages = num_pages;
 303
 304         return (void *)ALIGN_UP(lh, struct large_header);
 305 }
 306
 307
 308 /*
 309   large free function
 310  */
 311 static void alloc_large_free(void *ptr)
 312 {
 313         struct large_header *lh = ALIGN_DOWN_PAGE(ptr, struct large_header);
 314         munmap((void *)lh, lh->num_pages*PAGE_SIZE);
 315 }
 316
 317 /*
 318   refill a bucket
 319   called with the bucket lock held
 320  */
 321 static void alloc_refill_bucket(struct bucket_state *bs)
 322 {
 323         struct page_header *ph;
 324
 325         /* see if we can get a page from the global empty list */
 326         THREAD_LOCK(&state.mutex);
 327         ph = state.empty_list;
 328         if (ph != NULL) {
 329                 MOVE_LIST_FRONT(state.empty_list, bs->page_list, ph);
 330                 ph->num_elements = bs->elements_per_page;
 331                 ph->bucket = bs;
 332 #if PID_CHECK
 333                 ph->pid = getpid();
 334 #endif
 335                 memset(ph->used, 0, (ph->num_elements+7)/8);
 336                 state.num_empty_pages--;
 337                 THREAD_UNLOCK(&state.mutex);
 338                 return;
 339         }
 340
 341         /* we need to allocate a new page */
 342         ph = (struct page_header *)mmap(0, PAGE_SIZE, PROT_READ | PROT_WRITE,
 343                                         MAP_ANON | MAP_PRIVATE, -1, 0);
 344         if (unlikely(ph == (struct page_header *)-1)) {
 345                 THREAD_UNLOCK(&state.mutex);
 346                 return;
 347         }
 348
 349         /* we rely on mmap() giving us initially zero memory */
 350         ph->bucket = bs;
 351         ph->num_elements = bs->elements_per_page;
 352 #if PID_CHECK
 353         ph->pid = getpid();
 354 #endif
 355
 356         /* link it into the page_list */
 357         ph->next = bs->page_list;
 358         if (ph->next) ph->next->prev = ph;
 359         bs->page_list = ph;
 360         THREAD_UNLOCK(&state.mutex);
 361 }
 362
 363
 364 /*
 365   find the first free element in a bitmap. This assumes there is a bit
 366   to be found! Any return >= num_bits means an error (no free bit found)
 367  */
 368 static inline unsigned alloc_find_free_bit(const uint32_t *bitmap, uint32_t num_bits)
 369 {
 370         uint32_t i;
 371         const uint32_t n = (num_bits+31)/32;
 372         for (i=0;i<n;i++) {
 373                 if (bitmap[i] != 0xFFFFFFFF) {
 374                         return (i*32) + ffs(~bitmap[i]) - 1;
 375                 }
 376         }
 377         return num_bits;
 378 }
 379
 380
 381 /*
 382   allocate some memory
 383  */
 384 static void *alloc_malloc(size_t size)
 385 {
 386         uint32_t i;
 387         struct bucket_state *bs;
 388         struct page_header *ph;
 389
 390         if (unlikely(state.initialised == false)) {
 391                 alloc_initialise();
 392         }
 393
 394 #if PID_CHECK
 395         if (unlikely(state.pid != getpid())) {
 396                 alloc_pid_handler();
 397         }
 398 #endif
 399
 400         /* is it a large allocation? */
 401         if (unlikely(size > state.largest_bucket)) {
 402                 return alloc_large(size);
 403         }
 404
 405         /* find the right bucket */
 406         if (likely(size / ALLOC_ALIGNMENT < BUCKET_LOOKUP_SIZE)) {
 407                 if (size == 0) {
 408                         i = 0;
 409                 } else {
 410                         i = state.bucket_lookup[(size-1) / ALLOC_ALIGNMENT];
 411                 }
 412         } else {
 413                 for (i=state.bucket_lookup[BUCKET_LOOKUP_SIZE-1];i<=state.max_bucket;i++) {
 414                         if (state.buckets[i].alloc_limit >= size) {
 415                                 break;
 416                         }
 417                 }
 418         }
 419
 420         bs = &state.buckets[i];
 421
 422         THREAD_LOCK(&bs->mutex);
 423
 424 #if ALLOC_PARANOIA
 425         if (size > bs->alloc_limit) {
 426                 abort();
 427         }
 428 #endif
 429
 430         /* it might be empty. If so, refill it */
 431         if (unlikely(bs->page_list == NULL)) {
 432                 alloc_refill_bucket(bs);
 433                 if (unlikely(bs->page_list == NULL)) {
 434                         THREAD_UNLOCK(&bs->mutex);
 435                         return NULL;
 436                 }
 437         }
 438
 439 #if PID_CHECK
 440         if (unlikely(bs->page_list->pid != getpid() &&
 441                      bs->page_list->elements_used >= bs->page_list->num_elements/2)) {
 442                 alloc_refill_bucket(bs);
 443         }
 444 #endif
 445
 446         /* take the first one */
 447         ph = bs->page_list;
 448         i = alloc_find_free_bit(ph->used, ph->num_elements);
 449 #if ALLOC_PARANOIA
 450         if (unlikely(i >= ph->num_elements)) {
 451                 abort();
 452         }
 453 #endif
 454         ph->elements_used++;
 455
 456         /* mark this element as used */
 457         ph->used[i/32] |= 1<<(i%32);
 458
 459         /* check if this page is now full */
 460         if (unlikely(ph->elements_used == ph->num_elements)) {
 461                 MOVE_LIST_FRONT(bs->page_list, bs->full_list, ph);
 462         }
 463
 464         THREAD_UNLOCK(&bs->mutex);
 465
 466         /* return the element within the page */
 467         return (void *)((i*bs->alloc_limit)+PAGE_HEADER_SIZE(ph->num_elements)+(intptr_t)ph);
 468 }
 469
 470
 471 /*
 472   release all completely free pages
 473   called with state.mutex held
 474  */
 475 static void alloc_release(void)
 476 {
 477         struct page_header *ph, *next;
 478
 479         /* release all the empty pages */
 480         for (ph=state.empty_list;ph;ph=next) {
 481                 next = ph->next;
 482                 munmap((void *)ph, PAGE_SIZE);
 483         }
 484         state.empty_list = NULL;
 485         state.num_empty_pages = 0;
 486 }
 487
 488 /*
 489   free some memory from a alloc_memalign
 490  */
 491 static void alloc_memalign_free(void *ptr)
 492 {
 493         struct memalign_header *mh;
 494
 495         THREAD_LOCK(&state.mutex);
 496
 497 #if ALLOC_PARANOIA
 498         if (state.memalign_list == NULL) {
 499                 abort();
 500         }
 501 #endif
 502
 503         /* see if its the top one */
 504         mh = state.memalign_list;
 505         if (mh->p == ptr) {
 506                 state.memalign_list = mh->next;
 507                 munmap(ptr, mh->num_pages*PAGE_SIZE);
 508                 THREAD_UNLOCK(&state.mutex);
 509                 free(mh);
 510                 return;
 511         }
 512
 513         /* otherwise walk it */
 514         while (mh->next) {
 515                 struct memalign_header *mh2 = mh->next;
 516                 if (mh2->p == ptr) {
 517                         mh->next = mh2->next;
 518                         munmap(ptr, mh2->num_pages);
 519                         THREAD_UNLOCK(&state.mutex);
 520                         free(mh2);
 521                         return;
 522                 }
 523                 mh = mh->next;
 524         }
 525
 526         THREAD_UNLOCK(&state.mutex);
 527
 528 #if ALLOC_PARANOIA
 529         /* it wasn't there ... */
 530         abort();
 531 #endif
 532 }
 533
 534
 535 /*
 536   realloc for memalign blocks
 537  */
 538 static void *alloc_memalign_realloc(void *ptr, size_t size)
 539 {
 540         struct memalign_header *mh;
 541         void *ptr2;
 542
 543         THREAD_LOCK(&state.mutex);
 544         for (mh=state.memalign_list;mh;mh=mh->next) {
 545                 if (mh->p == ptr) break;
 546         }
 547 #if ALLOC_PARANOIA
 548         if (mh == NULL) {
 549                 abort();
 550         }
 551 #endif
 552         THREAD_UNLOCK(&state.mutex);
 553
 554         ptr2 = malloc(size);
 555         if (ptr2 == NULL) {
 556                 return NULL;
 557         }
 558
 559         memcpy(ptr2, ptr, MIN(size, mh->num_pages*PAGE_SIZE));
 560         free(ptr);
 561         return ptr2;
 562 }
 563
 564 /*
 565   free some memory
 566  */
 567 static void alloc_free(void *ptr)
 568 {
 569         struct page_header *ph = ALIGN_DOWN_PAGE(ptr, struct page_header);
 570         struct bucket_state *bs;
 571         int i;
 572
 573         if (unlikely(ptr == NULL)) {
 574                 return;
 575         }
 576
 577         if (unlikely(IS_PAGE_ALIGNED(ptr))) {
 578                 alloc_memalign_free(ptr);
 579                 return;
 580         }
 581
 582         if (ph->num_pages != 0) {
 583                 alloc_large_free(ptr);
 584                 return;
 585         }
 586
 587         bs = ph->bucket;
 588         THREAD_LOCK(&bs->mutex);
 589
 590         /* mark the block as being free in the page bitmap */
 591         i = ((((intptr_t)ptr) - (intptr_t)ph) - PAGE_HEADER_SIZE(ph->num_elements)) /
 592                 bs->alloc_limit;
 593 #if ALLOC_PARANOIA
 594         if ((ph->used[i/32] & (1<<(i%32))) == 0) {
 595                 abort();
 596         }
 597 #endif
 598         ph->used[i/32] &= ~(1<<(i%32));
 599
 600         /* if all blocks in this page were previously used, then move
 601            the page from the full list to the page list */
 602         if (unlikely(ph->elements_used == ph->num_elements)) {
 603                 MOVE_LIST(bs->full_list, bs->page_list, ph);
 604         }
 605
 606         ph->elements_used--;
 607
 608         /* if all blocks in the page are now free, then its an empty
 609            page, and can be added to the global pool of empty
 610            pages. When that gets too large, release them completely */
 611         if (unlikely(ph->elements_used == 0)) {
 612                 THREAD_LOCK(&state.mutex);
 613                 MOVE_LIST(bs->page_list, state.empty_list, ph);
 614                 state.num_empty_pages++;
 615                 if (state.num_empty_pages == FREE_PAGE_LIMIT) {
 616                         alloc_release();
 617                 }
 618                 THREAD_UNLOCK(&state.mutex);
 619         }
 620         THREAD_UNLOCK(&bs->mutex);
 621 }
 622
 623
 624 /*
 625   realloc for large blocks
 626  */
 627 static void *alloc_realloc_large(void *ptr, size_t size)
 628 {
 629         void *ptr2;
 630         struct large_header *lh = ALIGN_DOWN_PAGE(ptr, struct large_header);
 631
 632         /* check for wrap around */
 633         if (size + ALIGN_COST(struct large_header) < size) {
 634                 return NULL;
 635         }
 636
 637         /* if it fits in the current pointer, keep it there */
 638         if (lh->num_pages*PAGE_SIZE >= (size + ALIGN_COST(struct large_header))) {
 639                 return ptr;
 640         }
 641
 642         ptr2 = alloc_malloc(size);
 643         if (ptr2 == NULL) {
 644                 return NULL;
 645         }
 646
 647         memcpy(ptr2, ptr,
 648                MIN(size, (lh->num_pages*PAGE_SIZE)-ALIGN_COST(struct large_header)));
 649         alloc_large_free(ptr);
 650         return ptr2;
 651 }
 652
 653
 654
 655 /*
 656   realloc
 657  */
 658 static void *alloc_realloc(void *ptr, size_t size)
 659 {
 660         struct page_header *ph = ALIGN_DOWN_PAGE(ptr, struct page_header);
 661         struct bucket_state *bs;
 662         void *ptr2;
 663
 664         /* modern realloc() semantics */
 665         if (unlikely(size == 0)) {
 666                 alloc_free(ptr);
 667                 return NULL;
 668         }
 669         if (unlikely(ptr == NULL)) {
 670                 return alloc_malloc(size);
 671         }
 672
 673         if (unlikely(IS_PAGE_ALIGNED(ptr))) {
 674                 return alloc_memalign_realloc(ptr, size);
 675         }
 676
 677         /* if it was a large allocation, it needs special handling */
 678         if (ph->num_pages != 0) {
 679                 return alloc_realloc_large(ptr, size);
 680         }
 681
 682         bs = ph->bucket;
 683         if (bs->alloc_limit >= size) {
 684                 return ptr;
 685         }
 686
 687         ptr2 = alloc_malloc(size);
 688         if (unlikely(ptr2 == NULL)) {
 689                 return NULL;
 690         }
 691
 692         memcpy(ptr2, ptr, MIN(bs->alloc_limit, size));
 693         alloc_free(ptr);
 694         return ptr2;
 695 }
 696
 697
 698 /*
 699   calloc
 700  */
 701 static void *alloc_calloc(size_t nmemb, size_t size)
 702 {
 703         void *ptr;
 704         uint32_t total_size = nmemb*size;
 705         if (unlikely(size != 0 && total_size / size != nmemb)) {
 706                 return NULL;
 707         }
 708 #if PID_CHECK
 709         if (unlikely(state.pid != getpid())) {
 710                 alloc_pid_handler();
 711         }
 712 #endif
 713         if (unlikely(total_size > state.largest_bucket)) {
 714                 if (unlikely(state.initialised == false)) {
 715                         alloc_initialise();
 716                 }
 717                 return alloc_large(total_size);
 718         }
 719         ptr = alloc_malloc(total_size);
 720         if (likely(ptr != NULL)) {
 721                 memset(ptr, 0, total_size);
 722         }
 723         return ptr;
 724 }
 725
 726
 727 /*
 728   memalign - the most difficult of the lot with these data structures
 729
 730   this is O(n) in the number of aligned allocations. Don't use
 731   memalign() unless you _really_ need it
 732  */
 733 static void *alloc_memalign(size_t boundary, size_t size)
 734 {
 735         struct memalign_header *mh;
 736         uint32_t extra_pages=0;
 737
 738 #if PID_CHECK
 739         if (unlikely(state.pid != getpid())) {
 740                 alloc_pid_handler();
 741         }
 742 #endif
 743
 744         if (unlikely(state.initialised == false)) {
 745                 alloc_initialise();
 746         }
 747
 748         /* must be power of 2, and no overflow on page alignment */
 749         if (boundary & (boundary-1)) {
 750                 return NULL;
 751         }
 752         if (boundary == 0 || (size+PAGE_SIZE-1 < size)) {
 753                 return NULL;
 754         }
 755
 756         /* try and get lucky */
 757         if (boundary < state.largest_bucket) {
 758                 void *ptr = malloc(size);
 759                 if (((intptr_t)ptr) % boundary == 0) {
 760                         return ptr;
 761                 }
 762
 763                 /* nope, do it the slow way */
 764                 free(ptr);
 765         }
 766
 767         mh = malloc(sizeof(struct memalign_header));
 768         if (mh == NULL) {
 769                 return NULL;
 770         }
 771
 772         /* need to overallocate to guarantee alignment of larger than
 773            a page */
 774         if (boundary > PAGE_SIZE) {
 775                 extra_pages = boundary / PAGE_SIZE;
 776         }
 777
 778         /* give them a page aligned allocation */
 779         mh->num_pages = (size + PAGE_SIZE-1) / PAGE_SIZE;
 780
 781         if (mh->num_pages == 0) {
 782                 mh->num_pages = 1;
 783         }
 784
 785         /* check for overflow due to large boundary */
 786         if (mh->num_pages + extra_pages < mh->num_pages) {
 787                 free(mh);
 788                 return NULL;
 789         }
 790
 791         mh->p = mmap(0, (extra_pages+mh->num_pages)*PAGE_SIZE, PROT_READ | PROT_WRITE,
 792                      MAP_ANON | MAP_PRIVATE, -1, 0);
 793         if (mh->p == (void *)-1) {
 794                 free(mh);
 795                 return NULL;
 796         }
 797         if (extra_pages) {
 798                 while (((intptr_t)mh->p) % boundary) {
 799                         munmap(mh->p, PAGE_SIZE);
 800                         mh->p = (void *)(PAGE_SIZE + (intptr_t)mh->p);
 801                         extra_pages--;
 802                 }
 803                 if (extra_pages) {
 804                         munmap((void *)(mh->num_pages*PAGE_SIZE + (intptr_t)mh->p),
 805                                extra_pages*PAGE_SIZE);
 806                 }
 807         }
 808
 809         THREAD_LOCK(&state.mutex);
 810         mh->next = state.memalign_list;
 811         state.memalign_list = mh;
 812         THREAD_UNLOCK(&state.mutex);
 813
 814         return mh->p;
 815 }
 816
 817 #if 1
 818 void *malloc(size_t size)
 819 {
 820         return alloc_malloc(size);
 821 }
 822
 823 void *calloc(size_t nmemb, size_t size)
 824 {
 825         return alloc_calloc(nmemb, size);
 826 }
 827
 828 void free(void *ptr)
 829 {
 830         alloc_free(ptr);
 831 }
 832
 833 void cfree(void *ptr)
 834 {
 835         alloc_free(ptr);
 836 }
 837
 838 void *realloc(void *ptr, size_t size)
 839 {
 840         return alloc_realloc(ptr, size);
 841 }
 842
 843 void *memalign(size_t boundary, size_t size)
 844 {
 845         return alloc_memalign(boundary, size);
 846 }
 847
 848 void *valloc(size_t size)
 849 {
 850         return alloc_memalign(getpagesize(), size);
 851 }
 852
 853 void *pvalloc(size_t size)
 854 {
 855         return alloc_memalign(getpagesize(), size);
 856 }
 857
 858 int posix_memalign(void **memptr, size_t alignment, size_t size)
 859 {
 860         *memptr = alloc_memalign(alignment, size);
 861         if (*memptr == NULL) {
 862                 errno = ENOMEM;
 863                 return -1;
 864         }
 865         return 0;
 866 }
 867
 868 /* try to catch the internal entry points too */
 869 #if (__GNUC__ >= 3)
 870 void *__libc_malloc(size_t size)                                     __attribute__((weak, alias("malloc")));
 871 void *__libc_calloc(size_t nmemb, size_t size)                       __attribute__((weak, alias("calloc")));
 872 void __libc_free(void *ptr)                                          __attribute__((weak, alias("free")));
 873 void __libc_cfree(void *ptr)                                         __attribute__((weak, alias("cfree")));
 874 void *__libc_realloc(void *ptr, size_t size)                         __attribute__((weak, alias("realloc")));
 875 void *__libc_memalign(size_t boundary, size_t size)                  __attribute__((weak, alias("memalign")));
 876 void *__libc_valloc(size_t size)                                     __attribute__((weak, alias("valloc")));
 877 void *__libc_pvalloc(size_t size)                                    __attribute__((weak, alias("pvalloc")));
 878 int __posix_memalign(void **memptr, size_t alignment, size_t size)   __attribute__((weak, alias("posix_memalign")));
 879 #endif
 880
 881 #endif