compat/nedmalloc/nedmalloc.c

   1 /* Alternative malloc implementation for multiple threads without
   2 lock contention based on dlmalloc. (C) 2005-2006 Niall Douglas
   3
   4 Boost Software License - Version 1.0 - August 17th, 2003
   5
   6 Permission is hereby granted, free of charge, to any person or organization
   7 obtaining a copy of the software and accompanying documentation covered by
   8 this license (the "Software") to use, reproduce, display, distribute,
   9 execute, and transmit the Software, and to prepare derivative works of the
  10 Software, and to permit third-parties to whom the Software is furnished to
  11 do so, all subject to the following:
  12
  13 The copyright notices in the Software and this entire statement, including
  14 the above license grant, this restriction and the following disclaimer,
  15 must be included in all copies of the Software, in whole or in part, and
  16 all derivative works of the Software, unless such copies or derivative
  17 works are solely in the form of machine-executable object code generated by
  18 a source language processor.
  19
  20 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  21 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  22 FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
  23 SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
  24 FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
  25 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  26 DEALINGS IN THE SOFTWARE.
  27 */
  28
  29 #ifdef _MSC_VER
  30 /* Enable full aliasing on MSVC */
  31 /*#pragma optimize("a", on)*/
  32 #endif
  33
  34 /*#define FULLSANITYCHECKS*/
  35
  36 #include "nedmalloc.h"
  37 #if defined(WIN32)
  38  #include <malloc.h>
  39 #endif
  40 #define MSPACES 1
  41 #define ONLY_MSPACES 1
  42 #ifndef USE_LOCKS
  43  #define USE_LOCKS 1
  44 #endif
  45 #define FOOTERS 1           /* Need to enable footers so frees lock the right mspace */
  46 #undef DEBUG                            /* dlmalloc wants DEBUG either 0 or 1 */
  47 #ifdef _DEBUG
  48  #define DEBUG 1
  49 #else
  50  #define DEBUG 0
  51 #endif
  52 #ifdef NDEBUG               /* Disable assert checking on release builds */
  53  #undef DEBUG
  54 #endif
  55 /* The default of 64Kb means we spend too much time kernel-side */
  56 #ifndef DEFAULT_GRANULARITY
  57 #define DEFAULT_GRANULARITY (1*1024*1024)
  58 #endif
  59 /*#define USE_SPIN_LOCKS 0*/
  60
  61
  62 /*#define FORCEINLINE*/
  63 #include "malloc.c.h"
  64 #ifdef NDEBUG               /* Disable assert checking on release builds */
  65  #undef DEBUG
  66 #endif
  67
  68 /* The maximum concurrent threads in a pool possible */
  69 #ifndef MAXTHREADSINPOOL
  70 #define MAXTHREADSINPOOL 16
  71 #endif
  72 /* The maximum number of threadcaches which can be allocated */
  73 #ifndef THREADCACHEMAXCACHES
  74 #define THREADCACHEMAXCACHES 256
  75 #endif
  76 /* The maximum size to be allocated from the thread cache */
  77 #ifndef THREADCACHEMAX
  78 #define THREADCACHEMAX 8192
  79 #endif
  80 #if 0
  81 /* The number of cache entries for finer grained bins. This is (topbitpos(THREADCACHEMAX)-4)*2 */
  82 #define THREADCACHEMAXBINS ((13-4)*2)
  83 #else
  84 /* The number of cache entries. This is (topbitpos(THREADCACHEMAX)-4) */
  85 #define THREADCACHEMAXBINS (13-4)
  86 #endif
  87 /* Point at which the free space in a thread cache is garbage collected */
  88 #ifndef THREADCACHEMAXFREESPACE
  89 #define THREADCACHEMAXFREESPACE (512*1024)
  90 #endif
  91
  92
  93 #ifdef WIN32
  94  #define TLSVAR                 DWORD
  95  #define TLSALLOC(k)    (*(k)=TlsAlloc(), TLS_OUT_OF_INDEXES==*(k))
  96  #define TLSFREE(k)             (!TlsFree(k))
  97  #define TLSGET(k)              TlsGetValue(k)
  98  #define TLSSET(k, a)   (!TlsSetValue(k, a))
  99  #ifdef DEBUG
 100 static LPVOID ChkedTlsGetValue(DWORD idx)
 101 {
 102         LPVOID ret=TlsGetValue(idx);
 103         assert(S_OK==GetLastError());
 104         return ret;
 105 }
 106   #undef TLSGET
 107   #define TLSGET(k) ChkedTlsGetValue(k)
 108  #endif
 109 #else
 110  #define TLSVAR                 pthread_key_t
 111  #define TLSALLOC(k)    pthread_key_create(k, 0)
 112  #define TLSFREE(k)             pthread_key_delete(k)
 113  #define TLSGET(k)              pthread_getspecific(k)
 114  #define TLSSET(k, a)   pthread_setspecific(k, a)
 115 #endif
 116
 117 #if 0
 118 /* Only enable if testing with valgrind. Causes misoperation */
 119 #define mspace_malloc(p, s) malloc(s)
 120 #define mspace_realloc(p, m, s) realloc(m, s)
 121 #define mspace_calloc(p, n, s) calloc(n, s)
 122 #define mspace_free(p, m) free(m)
 123 #endif
 124
 125
 126 #if defined(__cplusplus)
 127 #if !defined(NO_NED_NAMESPACE)
 128 namespace nedalloc {
 129 #else
 130 extern "C" {
 131 #endif
 132 #endif
 133
 134 size_t nedblksize(void *mem) THROWSPEC
 135 {
 136 #if 0
 137         /* Only enable if testing with valgrind. Causes misoperation */
 138         return THREADCACHEMAX;
 139 #else
 140         if(mem)
 141         {
 142                 mchunkptr p=mem2chunk(mem);
 143                 assert(cinuse(p));      /* If this fails, someone tried to free a block twice */
 144                 if(cinuse(p))
 145                         return chunksize(p)-overhead_for(p);
 146         }
 147         return 0;
 148 #endif
 149 }
 150
 151 void nedsetvalue(void *v) THROWSPEC                                     { nedpsetvalue(0, v); }
 152 void * nedmalloc(size_t size) THROWSPEC                         { return nedpmalloc(0, size); }
 153 void * nedcalloc(size_t no, size_t size) THROWSPEC      { return nedpcalloc(0, no, size); }
 154 void * nedrealloc(void *mem, size_t size) THROWSPEC     { return nedprealloc(0, mem, size); }
 155 void   nedfree(void *mem) THROWSPEC                                     { nedpfree(0, mem); }
 156 void * nedmemalign(size_t alignment, size_t bytes) THROWSPEC { return nedpmemalign(0, alignment, bytes); }
 157 #if !NO_MALLINFO
 158 struct mallinfo nedmallinfo(void) THROWSPEC                     { return nedpmallinfo(0); }
 159 #endif
 160 int    nedmallopt(int parno, int value) THROWSPEC       { return nedpmallopt(0, parno, value); }
 161 int    nedmalloc_trim(size_t pad) THROWSPEC                     { return nedpmalloc_trim(0, pad); }
 162 void   nedmalloc_stats(void) THROWSPEC                                  { nedpmalloc_stats(0); }
 163 size_t nedmalloc_footprint(void) THROWSPEC                              { return nedpmalloc_footprint(0); }
 164 void **nedindependent_calloc(size_t elemsno, size_t elemsize, void **chunks) THROWSPEC  { return nedpindependent_calloc(0, elemsno, elemsize, chunks); }
 165 void **nedindependent_comalloc(size_t elems, size_t *sizes, void **chunks) THROWSPEC    { return nedpindependent_comalloc(0, elems, sizes, chunks); }
 166
 167 struct threadcacheblk_t;
 168 typedef struct threadcacheblk_t threadcacheblk;
 169 struct threadcacheblk_t
 170 {       /* Keep less than 16 bytes on 32 bit systems and 32 bytes on 64 bit systems */
 171 #ifdef FULLSANITYCHECKS
 172         unsigned int magic;
 173 #endif
 174         unsigned int lastUsed, size;
 175         threadcacheblk *next, *prev;
 176 };
 177 typedef struct threadcache_t
 178 {
 179 #ifdef FULLSANITYCHECKS
 180         unsigned int magic1;
 181 #endif
 182         int mymspace;                                           /* Last mspace entry this thread used */
 183         long threadid;
 184         unsigned int mallocs, frees, successes;
 185         size_t freeInCache;                                     /* How much free space is stored in this cache */
 186         threadcacheblk *bins[(THREADCACHEMAXBINS+1)*2];
 187 #ifdef FULLSANITYCHECKS
 188         unsigned int magic2;
 189 #endif
 190 } threadcache;
 191 struct nedpool_t
 192 {
 193         MLOCK_T mutex;
 194         void *uservalue;
 195         int threads;                                            /* Max entries in m to use */
 196         threadcache *caches[THREADCACHEMAXCACHES];
 197         TLSVAR mycache;                                         /* Thread cache for this thread. 0 for unset, negative for use mspace-1 directly, otherwise is cache-1 */
 198         mstate m[MAXTHREADSINPOOL+1];           /* mspace entries for this pool */
 199 };
 200 static nedpool syspool;
 201
 202 static FORCEINLINE unsigned int size2binidx(size_t _size) THROWSPEC
 203 {       /* 8=1000       16=10000        20=10100        24=11000        32=100000       48=110000       4096=1000000000000 */
 204         unsigned int topbit, size=(unsigned int)(_size>>4);
 205         /* 16=1         20=1    24=1    32=10   48=11   64=100  96=110  128=1000        4096=100000000 */
 206
 207 #if defined(__GNUC__)
 208         topbit = sizeof(size)*__CHAR_BIT__ - 1 - __builtin_clz(size);
 209 #elif defined(_MSC_VER) && _MSC_VER>=1300
 210         {
 211             unsigned long bsrTopBit;
 212
 213             _BitScanReverse(&bsrTopBit, size);
 214
 215             topbit = bsrTopBit;
 216         }
 217 #else
 218 #if 0
 219         union {
 220                 unsigned asInt[2];
 221                 double asDouble;
 222         };
 223         int n;
 224
 225         asDouble = (double)size + 0.5;
 226         topbit = (asInt[!FOX_BIGENDIAN] >> 20) - 1023;
 227 #else
 228         {
 229                 unsigned int x=size;
 230                 x = x | (x >> 1);
 231                 x = x | (x >> 2);
 232                 x = x | (x >> 4);
 233                 x = x | (x >> 8);
 234                 x = x | (x >>16);
 235                 x = ~x;
 236                 x = x - ((x >> 1) & 0x55555555);
 237                 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 238                 x = (x + (x >> 4)) & 0x0F0F0F0F;
 239                 x = x + (x << 8);
 240                 x = x + (x << 16);
 241                 topbit=31 - (x >> 24);
 242         }
 243 #endif
 244 #endif
 245         return topbit;
 246 }
 247
 248
 249 #ifdef FULLSANITYCHECKS
 250 static void tcsanitycheck(threadcacheblk **ptr) THROWSPEC
 251 {
 252         assert((ptr[0] && ptr[1]) || (!ptr[0] && !ptr[1]));
 253         if(ptr[0] && ptr[1])
 254         {
 255                 assert(nedblksize(ptr[0])>=sizeof(threadcacheblk));
 256                 assert(nedblksize(ptr[1])>=sizeof(threadcacheblk));
 257                 assert(*(unsigned int *) "NEDN"==ptr[0]->magic);
 258                 assert(*(unsigned int *) "NEDN"==ptr[1]->magic);
 259                 assert(!ptr[0]->prev);
 260                 assert(!ptr[1]->next);
 261                 if(ptr[0]==ptr[1])
 262                 {
 263                         assert(!ptr[0]->next);
 264                         assert(!ptr[1]->prev);
 265                 }
 266         }
 267 }
 268 static void tcfullsanitycheck(threadcache *tc) THROWSPEC
 269 {
 270         threadcacheblk **tcbptr=tc->bins;
 271         int n;
 272         for(n=0; n<=THREADCACHEMAXBINS; n++, tcbptr+=2)
 273         {
 274                 threadcacheblk *b, *ob=0;
 275                 tcsanitycheck(tcbptr);
 276                 for(b=tcbptr[0]; b; ob=b, b=b->next)
 277                 {
 278                         assert(*(unsigned int *) "NEDN"==b->magic);
 279                         assert(!ob || ob->next==b);
 280                         assert(!ob || b->prev==ob);
 281                 }
 282         }
 283 }
 284 #endif
 285
 286 static NOINLINE void RemoveCacheEntries(nedpool *p, threadcache *tc, unsigned int age) THROWSPEC
 287 {
 288 #ifdef FULLSANITYCHECKS
 289         tcfullsanitycheck(tc);
 290 #endif
 291         if(tc->freeInCache)
 292         {
 293                 threadcacheblk **tcbptr=tc->bins;
 294                 int n;
 295                 for(n=0; n<=THREADCACHEMAXBINS; n++, tcbptr+=2)
 296                 {
 297                         threadcacheblk **tcb=tcbptr+1;          /* come from oldest end of list */
 298                         /*tcsanitycheck(tcbptr);*/
 299                         for(; *tcb && tc->frees-(*tcb)->lastUsed>=age; )
 300                         {
 301                                 threadcacheblk *f=*tcb;
 302                                 size_t blksize=f->size; /*nedblksize(f);*/
 303                                 assert(blksize<=nedblksize(f));
 304                                 assert(blksize);
 305 #ifdef FULLSANITYCHECKS
 306                                 assert(*(unsigned int *) "NEDN"==(*tcb)->magic);
 307 #endif
 308                                 *tcb=(*tcb)->prev;
 309                                 if(*tcb)
 310                                         (*tcb)->next=0;
 311                                 else
 312                                         *tcbptr=0;
 313                                 tc->freeInCache-=blksize;
 314                                 assert((long) tc->freeInCache>=0);
 315                                 mspace_free(0, f);
 316                                 /*tcsanitycheck(tcbptr);*/
 317                         }
 318                 }
 319         }
 320 #ifdef FULLSANITYCHECKS
 321         tcfullsanitycheck(tc);
 322 #endif
 323 }
 324 static void DestroyCaches(nedpool *p) THROWSPEC
 325 {
 326         {
 327                 threadcache *tc;
 328                 int n;
 329                 for(n=0; n<THREADCACHEMAXCACHES; n++)
 330                 {
 331                         if((tc=p->caches[n]))
 332                         {
 333                                 tc->frees++;
 334                                 RemoveCacheEntries(p, tc, 0);
 335                                 assert(!tc->freeInCache);
 336                                 tc->mymspace=-1;
 337                                 tc->threadid=0;
 338                                 mspace_free(0, tc);
 339                                 p->caches[n]=0;
 340                         }
 341                 }
 342         }
 343 }
 344
 345 static NOINLINE threadcache *AllocCache(nedpool *p) THROWSPEC
 346 {
 347         threadcache *tc=0;
 348         int n, end;
 349         ACQUIRE_LOCK(&p->mutex);
 350         for(n=0; n<THREADCACHEMAXCACHES && p->caches[n]; n++);
 351         if(THREADCACHEMAXCACHES==n)
 352         {       /* List exhausted, so disable for this thread */
 353                 RELEASE_LOCK(&p->mutex);
 354                 return 0;
 355         }
 356         tc=p->caches[n]=(threadcache *) mspace_calloc(p->m[0], 1, sizeof(threadcache));
 357         if(!tc)
 358         {
 359                 RELEASE_LOCK(&p->mutex);
 360                 return 0;
 361         }
 362 #ifdef FULLSANITYCHECKS
 363         tc->magic1=*(unsigned int *)"NEDMALC1";
 364         tc->magic2=*(unsigned int *)"NEDMALC2";
 365 #endif
 366         tc->threadid=(long)(size_t)CURRENT_THREAD;
 367         for(end=0; p->m[end]; end++);
 368         tc->mymspace=tc->threadid % end;
 369         RELEASE_LOCK(&p->mutex);
 370         if(TLSSET(p->mycache, (void *)(size_t)(n+1))) abort();
 371         return tc;
 372 }
 373
 374 static void *threadcache_malloc(nedpool *p, threadcache *tc, size_t *size) THROWSPEC
 375 {
 376         void *ret=0;
 377         unsigned int bestsize;
 378         unsigned int idx=size2binidx(*size);
 379         size_t blksize=0;
 380         threadcacheblk *blk, **binsptr;
 381 #ifdef FULLSANITYCHECKS
 382         tcfullsanitycheck(tc);
 383 #endif
 384         /* Calculate best fit bin size */
 385         bestsize=1<<(idx+4);
 386 #if 0
 387         /* Finer grained bin fit */
 388         idx<<=1;
 389         if(*size>bestsize)
 390         {
 391                 idx++;
 392                 bestsize+=bestsize>>1;
 393         }
 394         if(*size>bestsize)
 395         {
 396                 idx++;
 397                 bestsize=1<<(4+(idx>>1));
 398         }
 399 #else
 400         if(*size>bestsize)
 401         {
 402                 idx++;
 403                 bestsize<<=1;
 404         }
 405 #endif
 406         assert(bestsize>=*size);
 407         if(*size<bestsize) *size=bestsize;
 408         assert(*size<=THREADCACHEMAX);
 409         assert(idx<=THREADCACHEMAXBINS);
 410         binsptr=&tc->bins[idx*2];
 411         /* Try to match close, but move up a bin if necessary */
 412         blk=*binsptr;
 413         if(!blk || blk->size<*size)
 414         {       /* Bump it up a bin */
 415                 if(idx<THREADCACHEMAXBINS)
 416                 {
 417                         idx++;
 418                         binsptr+=2;
 419                         blk=*binsptr;
 420                 }
 421         }
 422         if(blk)
 423         {
 424                 blksize=blk->size; /*nedblksize(blk);*/
 425                 assert(nedblksize(blk)>=blksize);
 426                 assert(blksize>=*size);
 427                 if(blk->next)
 428                         blk->next->prev=0;
 429                 *binsptr=blk->next;
 430                 if(!*binsptr)
 431                         binsptr[1]=0;
 432 #ifdef FULLSANITYCHECKS
 433                 blk->magic=0;
 434 #endif
 435                 assert(binsptr[0]!=blk && binsptr[1]!=blk);
 436                 assert(nedblksize(blk)>=sizeof(threadcacheblk) && nedblksize(blk)<=THREADCACHEMAX+CHUNK_OVERHEAD);
 437                 /*printf("malloc: %p, %p, %p, %lu\n", p, tc, blk, (long) size);*/
 438                 ret=(void *) blk;
 439         }
 440         ++tc->mallocs;
 441         if(ret)
 442         {
 443                 assert(blksize>=*size);
 444                 ++tc->successes;
 445                 tc->freeInCache-=blksize;
 446                 assert((long) tc->freeInCache>=0);
 447         }
 448 #if defined(DEBUG) && 0
 449         if(!(tc->mallocs & 0xfff))
 450         {
 451                 printf("*** threadcache=%u, mallocs=%u (%f), free=%u (%f), freeInCache=%u\n", (unsigned int) tc->threadid, tc->mallocs,
 452                         (float) tc->successes/tc->mallocs, tc->frees, (float) tc->successes/tc->frees, (unsigned int) tc->freeInCache);
 453         }
 454 #endif
 455 #ifdef FULLSANITYCHECKS
 456         tcfullsanitycheck(tc);
 457 #endif
 458         return ret;
 459 }
 460 static NOINLINE void ReleaseFreeInCache(nedpool *p, threadcache *tc, int mymspace) THROWSPEC
 461 {
 462         unsigned int age=THREADCACHEMAXFREESPACE/8192;
 463         /*ACQUIRE_LOCK(&p->m[mymspace]->mutex);*/
 464         while(age && tc->freeInCache>=THREADCACHEMAXFREESPACE)
 465         {
 466                 RemoveCacheEntries(p, tc, age);
 467                 /*printf("*** Removing cache entries older than %u (%u)\n", age, (unsigned int) tc->freeInCache);*/
 468                 age>>=1;
 469         }
 470         /*RELEASE_LOCK(&p->m[mymspace]->mutex);*/
 471 }
 472 static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *mem, size_t size) THROWSPEC
 473 {
 474         unsigned int bestsize;
 475         unsigned int idx=size2binidx(size);
 476         threadcacheblk **binsptr, *tck=(threadcacheblk *) mem;
 477         assert(size>=sizeof(threadcacheblk) && size<=THREADCACHEMAX+CHUNK_OVERHEAD);
 478 #ifdef DEBUG
 479         {       /* Make sure this is a valid memory block */
 480             mchunkptr p  = mem2chunk(mem);
 481             mstate fm = get_mstate_for(p);
 482             if (!ok_magic(fm)) {
 483               USAGE_ERROR_ACTION(fm, p);
 484               return;
 485             }
 486         }
 487 #endif
 488 #ifdef FULLSANITYCHECKS
 489         tcfullsanitycheck(tc);
 490 #endif
 491         /* Calculate best fit bin size */
 492         bestsize=1<<(idx+4);
 493 #if 0
 494         /* Finer grained bin fit */
 495         idx<<=1;
 496         if(size>bestsize)
 497         {
 498                 unsigned int biggerbestsize=bestsize+bestsize<<1;
 499                 if(size>=biggerbestsize)
 500                 {
 501                         idx++;
 502                         bestsize=biggerbestsize;
 503                 }
 504         }
 505 #endif
 506         if(bestsize!=size)      /* dlmalloc can round up, so we round down to preserve indexing */
 507                 size=bestsize;
 508         binsptr=&tc->bins[idx*2];
 509         assert(idx<=THREADCACHEMAXBINS);
 510         if(tck==*binsptr)
 511         {
 512                 fprintf(stderr, "Attempt to free already freed memory block %p - aborting!\n", (void *)tck);
 513                 abort();
 514         }
 515 #ifdef FULLSANITYCHECKS
 516         tck->magic=*(unsigned int *) "NEDN";
 517 #endif
 518         tck->lastUsed=++tc->frees;
 519         tck->size=(unsigned int) size;
 520         tck->next=*binsptr;
 521         tck->prev=0;
 522         if(tck->next)
 523                 tck->next->prev=tck;
 524         else
 525                 binsptr[1]=tck;
 526         assert(!*binsptr || (*binsptr)->size==tck->size);
 527         *binsptr=tck;
 528         assert(tck==tc->bins[idx*2]);
 529         assert(tc->bins[idx*2+1]==tck || binsptr[0]->next->prev==tck);
 530         /*printf("free: %p, %p, %p, %lu\n", p, tc, mem, (long) size);*/
 531         tc->freeInCache+=size;
 532 #ifdef FULLSANITYCHECKS
 533         tcfullsanitycheck(tc);
 534 #endif
 535 #if 1
 536         if(tc->freeInCache>=THREADCACHEMAXFREESPACE)
 537                 ReleaseFreeInCache(p, tc, mymspace);
 538 #endif
 539 }
 540
 541
 542
 543
 544 static NOINLINE int InitPool(nedpool *p, size_t capacity, int threads) THROWSPEC
 545 {       /* threads is -1 for system pool */
 546         ensure_initialization();
 547         ACQUIRE_MALLOC_GLOBAL_LOCK();
 548         if(p->threads) goto done;
 549         if(INITIAL_LOCK(&p->mutex)) goto err;
 550         if(TLSALLOC(&p->mycache)) goto err;
 551         if(!(p->m[0]=(mstate) create_mspace(capacity, 1))) goto err;
 552         p->m[0]->extp=p;
 553         p->threads=(threads<1 || threads>MAXTHREADSINPOOL) ? MAXTHREADSINPOOL : threads;
 554 done:
 555         RELEASE_MALLOC_GLOBAL_LOCK();
 556         return 1;
 557 err:
 558         if(threads<0)
 559                 abort();                        /* If you can't allocate for system pool, we're screwed */
 560         DestroyCaches(p);
 561         if(p->m[0])
 562         {
 563                 destroy_mspace(p->m[0]);
 564                 p->m[0]=0;
 565         }
 566         if(p->mycache)
 567         {
 568                 if(TLSFREE(p->mycache)) abort();
 569                 p->mycache=0;
 570         }
 571         RELEASE_MALLOC_GLOBAL_LOCK();
 572         return 0;
 573 }
 574 static NOINLINE mstate FindMSpace(nedpool *p, threadcache *tc, int *lastUsed, size_t size) THROWSPEC
 575 {       /* Gets called when thread's last used mspace is in use. The strategy
 576         is to run through the list of all available mspaces looking for an
 577         unlocked one and if we fail, we create a new one so long as we don't
 578         exceed p->threads */
 579         int n, end;
 580         for(n=end=*lastUsed+1; p->m[n]; end=++n)
 581         {
 582                 if(TRY_LOCK(&p->m[n]->mutex)) goto found;
 583         }
 584         for(n=0; n<*lastUsed && p->m[n]; n++)
 585         {
 586                 if(TRY_LOCK(&p->m[n]->mutex)) goto found;
 587         }
 588         if(end<p->threads)
 589         {
 590                 mstate temp;
 591                 if(!(temp=(mstate) create_mspace(size, 1)))
 592                         goto badexit;
 593                 /* Now we're ready to modify the lists, we lock */
 594                 ACQUIRE_LOCK(&p->mutex);
 595                 while(p->m[end] && end<p->threads)
 596                         end++;
 597                 if(end>=p->threads)
 598                 {       /* Drat, must destroy it now */
 599                         RELEASE_LOCK(&p->mutex);
 600                         destroy_mspace((mspace) temp);
 601                         goto badexit;
 602                 }
 603                 /* We really want to make sure this goes into memory now but we
 604                 have to be careful of breaking aliasing rules, so write it twice */
 605                 {
 606                         volatile struct malloc_state **_m=(volatile struct malloc_state **) &p->m[end];
 607                         *_m=(p->m[end]=temp);
 608                 }
 609                 ACQUIRE_LOCK(&p->m[end]->mutex);
 610                 /*printf("Created mspace idx %d\n", end);*/
 611                 RELEASE_LOCK(&p->mutex);
 612                 n=end;
 613                 goto found;
 614         }
 615         /* Let it lock on the last one it used */
 616 badexit:
 617         ACQUIRE_LOCK(&p->m[*lastUsed]->mutex);
 618         return p->m[*lastUsed];
 619 found:
 620         *lastUsed=n;
 621         if(tc)
 622                 tc->mymspace=n;
 623         else
 624         {
 625                 if(TLSSET(p->mycache, (void *)(size_t)(-(n+1)))) abort();
 626         }
 627         return p->m[n];
 628 }
 629
 630 nedpool *nedcreatepool(size_t capacity, int threads) THROWSPEC
 631 {
 632         nedpool *ret;
 633         if(!(ret=(nedpool *) nedpcalloc(0, 1, sizeof(nedpool)))) return 0;
 634         if(!InitPool(ret, capacity, threads))
 635         {
 636                 nedpfree(0, ret);
 637                 return 0;
 638         }
 639         return ret;
 640 }
 641 void neddestroypool(nedpool *p) THROWSPEC
 642 {
 643         int n;
 644         ACQUIRE_LOCK(&p->mutex);
 645         DestroyCaches(p);
 646         for(n=0; p->m[n]; n++)
 647         {
 648                 destroy_mspace(p->m[n]);
 649                 p->m[n]=0;
 650         }
 651         RELEASE_LOCK(&p->mutex);
 652         if(TLSFREE(p->mycache)) abort();
 653         nedpfree(0, p);
 654 }
 655
 656 void nedpsetvalue(nedpool *p, void *v) THROWSPEC
 657 {
 658         if(!p) { p=&syspool; if(!syspool.threads) InitPool(&syspool, 0, -1); }
 659         p->uservalue=v;
 660 }
 661 void *nedgetvalue(nedpool **p, void *mem) THROWSPEC
 662 {
 663         nedpool *np=0;
 664         mchunkptr mcp=mem2chunk(mem);
 665         mstate fm;
 666         if(!(is_aligned(chunk2mem(mcp))) && mcp->head != FENCEPOST_HEAD) return 0;
 667         if(!cinuse(mcp)) return 0;
 668         if(!next_pinuse(mcp)) return 0;
 669         if(!is_mmapped(mcp) && !pinuse(mcp))
 670         {
 671                 if(next_chunk(prev_chunk(mcp))!=mcp) return 0;
 672         }
 673         fm=get_mstate_for(mcp);
 674         if(!ok_magic(fm)) return 0;
 675         if(!ok_address(fm, mcp)) return 0;
 676         if(!fm->extp) return 0;
 677         np=(nedpool *) fm->extp;
 678         if(p) *p=np;
 679         return np->uservalue;
 680 }
 681
 682 void neddisablethreadcache(nedpool *p) THROWSPEC
 683 {
 684         int mycache;
 685         if(!p)
 686         {
 687                 p=&syspool;
 688                 if(!syspool.threads) InitPool(&syspool, 0, -1);
 689         }
 690         mycache=(int)(size_t) TLSGET(p->mycache);
 691         if(!mycache)
 692         {       /* Set to mspace 0 */
 693                 if(TLSSET(p->mycache, (void *)-1)) abort();
 694         }
 695         else if(mycache>0)
 696         {       /* Set to last used mspace */
 697                 threadcache *tc=p->caches[mycache-1];
 698 #if defined(DEBUG)
 699                 printf("Threadcache utilisation: %lf%% in cache with %lf%% lost to other threads\n",
 700                         100.0*tc->successes/tc->mallocs, 100.0*((double) tc->mallocs-tc->frees)/tc->mallocs);
 701 #endif
 702                 if(TLSSET(p->mycache, (void *)(size_t)(-tc->mymspace))) abort();
 703                 tc->frees++;
 704                 RemoveCacheEntries(p, tc, 0);
 705                 assert(!tc->freeInCache);
 706                 tc->mymspace=-1;
 707                 tc->threadid=0;
 708                 mspace_free(0, p->caches[mycache-1]);
 709                 p->caches[mycache-1]=0;
 710         }
 711 }
 712
 713 #define GETMSPACE(m,p,tc,ms,s,action)           \
 714   do                                            \
 715   {                                             \
 716     mstate m = GetMSpace((p),(tc),(ms),(s));    \
 717     action;                                     \
 718     RELEASE_LOCK(&m->mutex);                    \
 719   } while (0)
 720
 721 static FORCEINLINE mstate GetMSpace(nedpool *p, threadcache *tc, int mymspace, size_t size) THROWSPEC
 722 {       /* Returns a locked and ready for use mspace */
 723         mstate m=p->m[mymspace];
 724         assert(m);
 725         if(!TRY_LOCK(&p->m[mymspace]->mutex)) m=FindMSpace(p, tc, &mymspace, size);\
 726         /*assert(IS_LOCKED(&p->m[mymspace]->mutex));*/
 727         return m;
 728 }
 729 static FORCEINLINE void GetThreadCache(nedpool **p, threadcache **tc, int *mymspace, size_t *size) THROWSPEC
 730 {
 731         int mycache;
 732         if(size && *size<sizeof(threadcacheblk)) *size=sizeof(threadcacheblk);
 733         if(!*p)
 734         {
 735                 *p=&syspool;
 736                 if(!syspool.threads) InitPool(&syspool, 0, -1);
 737         }
 738         mycache=(int)(size_t) TLSGET((*p)->mycache);
 739         if(mycache>0)
 740         {
 741                 *tc=(*p)->caches[mycache-1];
 742                 *mymspace=(*tc)->mymspace;
 743         }
 744         else if(!mycache)
 745         {
 746                 *tc=AllocCache(*p);
 747                 if(!*tc)
 748                 {       /* Disable */
 749                         if(TLSSET((*p)->mycache, (void *)-1)) abort();
 750                         *mymspace=0;
 751                 }
 752                 else
 753                         *mymspace=(*tc)->mymspace;
 754         }
 755         else
 756         {
 757                 *tc=0;
 758                 *mymspace=-mycache-1;
 759         }
 760         assert(*mymspace>=0);
 761         assert((long)(size_t)CURRENT_THREAD==(*tc)->threadid);
 762 #ifdef FULLSANITYCHECKS
 763         if(*tc)
 764         {
 765                 if(*(unsigned int *)"NEDMALC1"!=(*tc)->magic1 || *(unsigned int *)"NEDMALC2"!=(*tc)->magic2)
 766                 {
 767                         abort();
 768                 }
 769         }
 770 #endif
 771 }
 772
 773 void * nedpmalloc(nedpool *p, size_t size) THROWSPEC
 774 {
 775         void *ret=0;
 776         threadcache *tc;
 777         int mymspace;
 778         GetThreadCache(&p, &tc, &mymspace, &size);
 779 #if THREADCACHEMAX
 780         if(tc && size<=THREADCACHEMAX)
 781         {       /* Use the thread cache */
 782                 ret=threadcache_malloc(p, tc, &size);
 783         }
 784 #endif
 785         if(!ret)
 786         {       /* Use this thread's mspace */
 787         GETMSPACE(m, p, tc, mymspace, size,
 788                   ret=mspace_malloc(m, size));
 789         }
 790         return ret;
 791 }
 792 void * nedpcalloc(nedpool *p, size_t no, size_t size) THROWSPEC
 793 {
 794         size_t rsize=size*no;
 795         void *ret=0;
 796         threadcache *tc;
 797         int mymspace;
 798         GetThreadCache(&p, &tc, &mymspace, &rsize);
 799 #if THREADCACHEMAX
 800         if(tc && rsize<=THREADCACHEMAX)
 801         {       /* Use the thread cache */
 802                 if((ret=threadcache_malloc(p, tc, &rsize)))
 803                         memset(ret, 0, rsize);
 804         }
 805 #endif
 806         if(!ret)
 807         {       /* Use this thread's mspace */
 808         GETMSPACE(m, p, tc, mymspace, rsize,
 809                   ret=mspace_calloc(m, 1, rsize));
 810         }
 811         return ret;
 812 }
 813 void * nedprealloc(nedpool *p, void *mem, size_t size) THROWSPEC
 814 {
 815         void *ret=0;
 816         threadcache *tc;
 817         int mymspace;
 818         if(!mem) return nedpmalloc(p, size);
 819         GetThreadCache(&p, &tc, &mymspace, &size);
 820 #if THREADCACHEMAX
 821         if(tc && size && size<=THREADCACHEMAX)
 822         {       /* Use the thread cache */
 823                 size_t memsize=nedblksize(mem);
 824                 assert(memsize);
 825                 if((ret=threadcache_malloc(p, tc, &size)))
 826                 {
 827                         memcpy(ret, mem, memsize<size ? memsize : size);
 828                         if(memsize<=THREADCACHEMAX)
 829                                 threadcache_free(p, tc, mymspace, mem, memsize);
 830                         else
 831                                 mspace_free(0, mem);
 832                 }
 833         }
 834 #endif
 835         if(!ret)
 836         {       /* Reallocs always happen in the mspace they happened in, so skip
 837                 locking the preferred mspace for this thread */
 838                 ret=mspace_realloc(0, mem, size);
 839         }
 840         return ret;
 841 }
 842 void   nedpfree(nedpool *p, void *mem) THROWSPEC
 843 {       /* Frees always happen in the mspace they happened in, so skip
 844         locking the preferred mspace for this thread */
 845         threadcache *tc;
 846         int mymspace;
 847         size_t memsize;
 848         assert(mem);
 849         GetThreadCache(&p, &tc, &mymspace, 0);
 850 #if THREADCACHEMAX
 851         memsize=nedblksize(mem);
 852         assert(memsize);
 853         if(mem && tc && memsize<=(THREADCACHEMAX+CHUNK_OVERHEAD))
 854                 threadcache_free(p, tc, mymspace, mem, memsize);
 855         else
 856 #endif
 857                 mspace_free(0, mem);
 858 }
 859 void * nedpmemalign(nedpool *p, size_t alignment, size_t bytes) THROWSPEC
 860 {
 861         void *ret;
 862         threadcache *tc;
 863         int mymspace;
 864         GetThreadCache(&p, &tc, &mymspace, &bytes);
 865         {       /* Use this thread's mspace */
 866         GETMSPACE(m, p, tc, mymspace, bytes,
 867                   ret=mspace_memalign(m, alignment, bytes));
 868         }
 869         return ret;
 870 }
 871 #if !NO_MALLINFO
 872 struct mallinfo nedpmallinfo(nedpool *p) THROWSPEC
 873 {
 874         int n;
 875         struct mallinfo ret={0};
 876         if(!p) { p=&syspool; if(!syspool.threads) InitPool(&syspool, 0, -1); }
 877         for(n=0; p->m[n]; n++)
 878         {
 879                 struct mallinfo t=mspace_mallinfo(p->m[n]);
 880                 ret.arena+=t.arena;
 881                 ret.ordblks+=t.ordblks;
 882                 ret.hblkhd+=t.hblkhd;
 883                 ret.usmblks+=t.usmblks;
 884                 ret.uordblks+=t.uordblks;
 885                 ret.fordblks+=t.fordblks;
 886                 ret.keepcost+=t.keepcost;
 887         }
 888         return ret;
 889 }
 890 #endif
 891 int    nedpmallopt(nedpool *p, int parno, int value) THROWSPEC
 892 {
 893         return mspace_mallopt(parno, value);
 894 }
 895 int    nedpmalloc_trim(nedpool *p, size_t pad) THROWSPEC
 896 {
 897         int n, ret=0;
 898         if(!p) { p=&syspool; if(!syspool.threads) InitPool(&syspool, 0, -1); }
 899         for(n=0; p->m[n]; n++)
 900         {
 901                 ret+=mspace_trim(p->m[n], pad);
 902         }
 903         return ret;
 904 }
 905 void   nedpmalloc_stats(nedpool *p) THROWSPEC
 906 {
 907         int n;
 908         if(!p) { p=&syspool; if(!syspool.threads) InitPool(&syspool, 0, -1); }
 909         for(n=0; p->m[n]; n++)
 910         {
 911                 mspace_malloc_stats(p->m[n]);
 912         }
 913 }
 914 size_t nedpmalloc_footprint(nedpool *p) THROWSPEC
 915 {
 916         size_t ret=0;
 917         int n;
 918         if(!p) { p=&syspool; if(!syspool.threads) InitPool(&syspool, 0, -1); }
 919         for(n=0; p->m[n]; n++)
 920         {
 921                 ret+=mspace_footprint(p->m[n]);
 922         }
 923         return ret;
 924 }
 925 void **nedpindependent_calloc(nedpool *p, size_t elemsno, size_t elemsize, void **chunks) THROWSPEC
 926 {
 927         void **ret;
 928         threadcache *tc;
 929         int mymspace;
 930         GetThreadCache(&p, &tc, &mymspace, &elemsize);
 931     GETMSPACE(m, p, tc, mymspace, elemsno*elemsize,
 932               ret=mspace_independent_calloc(m, elemsno, elemsize, chunks));
 933         return ret;
 934 }
 935 void **nedpindependent_comalloc(nedpool *p, size_t elems, size_t *sizes, void **chunks) THROWSPEC
 936 {
 937         void **ret;
 938         threadcache *tc;
 939         int mymspace;
 940         size_t i, *adjustedsizes=(size_t *) alloca(elems*sizeof(size_t));
 941         if(!adjustedsizes) return 0;
 942         for(i=0; i<elems; i++)
 943                 adjustedsizes[i]=sizes[i]<sizeof(threadcacheblk) ? sizeof(threadcacheblk) : sizes[i];
 944         GetThreadCache(&p, &tc, &mymspace, 0);
 945         GETMSPACE(m, p, tc, mymspace, 0,
 946               ret=mspace_independent_comalloc(m, elems, adjustedsizes, chunks));
 947         return ret;
 948 }
 949
 950 #if defined(__cplusplus)
 951 }
 952 #endif