Merge branch 'js/maint-add-path-stat-pwd' into maint
[git] / 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() THROWSPEC                                      { nedpmalloc_stats(0); }
163 size_t nedmalloc_footprint() 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         if(p->caches)
327         {
328                 threadcache *tc;
329                 int n;
330                 for(n=0; n<THREADCACHEMAXCACHES; n++)
331                 {
332                         if((tc=p->caches[n]))
333                         {
334                                 tc->frees++;
335                                 RemoveCacheEntries(p, tc, 0);
336                                 assert(!tc->freeInCache);
337                                 tc->mymspace=-1;
338                                 tc->threadid=0;
339                                 mspace_free(0, tc);
340                                 p->caches[n]=0;
341                         }
342                 }
343         }
344 }
345
346 static NOINLINE threadcache *AllocCache(nedpool *p) THROWSPEC
347 {
348         threadcache *tc=0;
349         int n, end;
350         ACQUIRE_LOCK(&p->mutex);
351         for(n=0; n<THREADCACHEMAXCACHES && p->caches[n]; n++);
352         if(THREADCACHEMAXCACHES==n)
353         {       /* List exhausted, so disable for this thread */
354                 RELEASE_LOCK(&p->mutex);
355                 return 0;
356         }
357         tc=p->caches[n]=(threadcache *) mspace_calloc(p->m[0], 1, sizeof(threadcache));
358         if(!tc)
359         {
360                 RELEASE_LOCK(&p->mutex);
361                 return 0;
362         }
363 #ifdef FULLSANITYCHECKS
364         tc->magic1=*(unsigned int *)"NEDMALC1";
365         tc->magic2=*(unsigned int *)"NEDMALC2";
366 #endif
367         tc->threadid=(long)(size_t)CURRENT_THREAD;
368         for(end=0; p->m[end]; end++);
369         tc->mymspace=tc->threadid % end;
370         RELEASE_LOCK(&p->mutex);
371         if(TLSSET(p->mycache, (void *)(size_t)(n+1))) abort();
372         return tc;
373 }
374
375 static void *threadcache_malloc(nedpool *p, threadcache *tc, size_t *size) THROWSPEC
376 {
377         void *ret=0;
378         unsigned int bestsize;
379         unsigned int idx=size2binidx(*size);
380         size_t blksize=0;
381         threadcacheblk *blk, **binsptr;
382 #ifdef FULLSANITYCHECKS
383         tcfullsanitycheck(tc);
384 #endif
385         /* Calculate best fit bin size */
386         bestsize=1<<(idx+4);
387 #if 0
388         /* Finer grained bin fit */
389         idx<<=1;
390         if(*size>bestsize)
391         {
392                 idx++;
393                 bestsize+=bestsize>>1;
394         }
395         if(*size>bestsize)
396         {
397                 idx++;
398                 bestsize=1<<(4+(idx>>1));
399         }
400 #else
401         if(*size>bestsize)
402         {
403                 idx++;
404                 bestsize<<=1;
405         }
406 #endif
407         assert(bestsize>=*size);
408         if(*size<bestsize) *size=bestsize;
409         assert(*size<=THREADCACHEMAX);
410         assert(idx<=THREADCACHEMAXBINS);
411         binsptr=&tc->bins[idx*2];
412         /* Try to match close, but move up a bin if necessary */
413         blk=*binsptr;
414         if(!blk || blk->size<*size)
415         {       /* Bump it up a bin */
416                 if(idx<THREADCACHEMAXBINS)
417                 {
418                         idx++;
419                         binsptr+=2;
420                         blk=*binsptr;
421                 }
422         }
423         if(blk)
424         {
425                 blksize=blk->size; /*nedblksize(blk);*/
426                 assert(nedblksize(blk)>=blksize);
427                 assert(blksize>=*size);
428                 if(blk->next)
429                         blk->next->prev=0;
430                 *binsptr=blk->next;
431                 if(!*binsptr)
432                         binsptr[1]=0;
433 #ifdef FULLSANITYCHECKS
434                 blk->magic=0;
435 #endif
436                 assert(binsptr[0]!=blk && binsptr[1]!=blk);
437                 assert(nedblksize(blk)>=sizeof(threadcacheblk) && nedblksize(blk)<=THREADCACHEMAX+CHUNK_OVERHEAD);
438                 /*printf("malloc: %p, %p, %p, %lu\n", p, tc, blk, (long) size);*/
439                 ret=(void *) blk;
440         }
441         ++tc->mallocs;
442         if(ret)
443         {
444                 assert(blksize>=*size);
445                 ++tc->successes;
446                 tc->freeInCache-=blksize;
447                 assert((long) tc->freeInCache>=0);
448         }
449 #if defined(DEBUG) && 0
450         if(!(tc->mallocs & 0xfff))
451         {
452                 printf("*** threadcache=%u, mallocs=%u (%f), free=%u (%f), freeInCache=%u\n", (unsigned int) tc->threadid, tc->mallocs,
453                         (float) tc->successes/tc->mallocs, tc->frees, (float) tc->successes/tc->frees, (unsigned int) tc->freeInCache);
454         }
455 #endif
456 #ifdef FULLSANITYCHECKS
457         tcfullsanitycheck(tc);
458 #endif
459         return ret;
460 }
461 static NOINLINE void ReleaseFreeInCache(nedpool *p, threadcache *tc, int mymspace) THROWSPEC
462 {
463         unsigned int age=THREADCACHEMAXFREESPACE/8192;
464         /*ACQUIRE_LOCK(&p->m[mymspace]->mutex);*/
465         while(age && tc->freeInCache>=THREADCACHEMAXFREESPACE)
466         {
467                 RemoveCacheEntries(p, tc, age);
468                 /*printf("*** Removing cache entries older than %u (%u)\n", age, (unsigned int) tc->freeInCache);*/
469                 age>>=1;
470         }
471         /*RELEASE_LOCK(&p->m[mymspace]->mutex);*/
472 }
473 static void threadcache_free(nedpool *p, threadcache *tc, int mymspace, void *mem, size_t size) THROWSPEC
474 {
475         unsigned int bestsize;
476         unsigned int idx=size2binidx(size);
477         threadcacheblk **binsptr, *tck=(threadcacheblk *) mem;
478         assert(size>=sizeof(threadcacheblk) && size<=THREADCACHEMAX+CHUNK_OVERHEAD);
479 #ifdef DEBUG
480         {       /* Make sure this is a valid memory block */
481             mchunkptr p  = mem2chunk(mem);
482             mstate fm = get_mstate_for(p);
483             if (!ok_magic(fm)) {
484               USAGE_ERROR_ACTION(fm, p);
485               return;
486             }
487         }
488 #endif
489 #ifdef FULLSANITYCHECKS
490         tcfullsanitycheck(tc);
491 #endif
492         /* Calculate best fit bin size */
493         bestsize=1<<(idx+4);
494 #if 0
495         /* Finer grained bin fit */
496         idx<<=1;
497         if(size>bestsize)
498         {
499                 unsigned int biggerbestsize=bestsize+bestsize<<1;
500                 if(size>=biggerbestsize)
501                 {
502                         idx++;
503                         bestsize=biggerbestsize;
504                 }
505         }
506 #endif
507         if(bestsize!=size)      /* dlmalloc can round up, so we round down to preserve indexing */
508                 size=bestsize;
509         binsptr=&tc->bins[idx*2];
510         assert(idx<=THREADCACHEMAXBINS);
511         if(tck==*binsptr)
512         {
513                 fprintf(stderr, "Attempt to free already freed memory block %p - aborting!\n", tck);
514                 abort();
515         }
516 #ifdef FULLSANITYCHECKS
517         tck->magic=*(unsigned int *) "NEDN";
518 #endif
519         tck->lastUsed=++tc->frees;
520         tck->size=(unsigned int) size;
521         tck->next=*binsptr;
522         tck->prev=0;
523         if(tck->next)
524                 tck->next->prev=tck;
525         else
526                 binsptr[1]=tck;
527         assert(!*binsptr || (*binsptr)->size==tck->size);
528         *binsptr=tck;
529         assert(tck==tc->bins[idx*2]);
530         assert(tc->bins[idx*2+1]==tck || binsptr[0]->next->prev==tck);
531         /*printf("free: %p, %p, %p, %lu\n", p, tc, mem, (long) size);*/
532         tc->freeInCache+=size;
533 #ifdef FULLSANITYCHECKS
534         tcfullsanitycheck(tc);
535 #endif
536 #if 1
537         if(tc->freeInCache>=THREADCACHEMAXFREESPACE)
538                 ReleaseFreeInCache(p, tc, mymspace);
539 #endif
540 }
541
542
543
544
545 static NOINLINE int InitPool(nedpool *p, size_t capacity, int threads) THROWSPEC
546 {       /* threads is -1 for system pool */
547         ensure_initialization();
548         ACQUIRE_MALLOC_GLOBAL_LOCK();
549         if(p->threads) goto done;
550         if(INITIAL_LOCK(&p->mutex)) goto err;
551         if(TLSALLOC(&p->mycache)) goto err;
552         if(!(p->m[0]=(mstate) create_mspace(capacity, 1))) goto err;
553         p->m[0]->extp=p;
554         p->threads=(threads<1 || threads>MAXTHREADSINPOOL) ? MAXTHREADSINPOOL : threads;
555 done:
556         RELEASE_MALLOC_GLOBAL_LOCK();
557         return 1;
558 err:
559         if(threads<0)
560                 abort();                        /* If you can't allocate for system pool, we're screwed */
561         DestroyCaches(p);
562         if(p->m[0])
563         {
564                 destroy_mspace(p->m[0]);
565                 p->m[0]=0;
566         }
567         if(p->mycache)
568         {
569                 if(TLSFREE(p->mycache)) abort();
570                 p->mycache=0;
571         }
572         RELEASE_MALLOC_GLOBAL_LOCK();
573         return 0;
574 }
575 static NOINLINE mstate FindMSpace(nedpool *p, threadcache *tc, int *lastUsed, size_t size) THROWSPEC
576 {       /* Gets called when thread's last used mspace is in use. The strategy
577         is to run through the list of all available mspaces looking for an
578         unlocked one and if we fail, we create a new one so long as we don't
579         exceed p->threads */
580         int n, end;
581         for(n=end=*lastUsed+1; p->m[n]; end=++n)
582         {
583                 if(TRY_LOCK(&p->m[n]->mutex)) goto found;
584         }
585         for(n=0; n<*lastUsed && p->m[n]; n++)
586         {
587                 if(TRY_LOCK(&p->m[n]->mutex)) goto found;
588         }
589         if(end<p->threads)
590         {
591                 mstate temp;
592                 if(!(temp=(mstate) create_mspace(size, 1)))
593                         goto badexit;
594                 /* Now we're ready to modify the lists, we lock */
595                 ACQUIRE_LOCK(&p->mutex);
596                 while(p->m[end] && end<p->threads)
597                         end++;
598                 if(end>=p->threads)
599                 {       /* Drat, must destroy it now */
600                         RELEASE_LOCK(&p->mutex);
601                         destroy_mspace((mspace) temp);
602                         goto badexit;
603                 }
604                 /* We really want to make sure this goes into memory now but we
605                 have to be careful of breaking aliasing rules, so write it twice */
606                 *((volatile struct malloc_state **) &p->m[end])=p->m[end]=temp;
607                 ACQUIRE_LOCK(&p->m[end]->mutex);
608                 /*printf("Created mspace idx %d\n", end);*/
609                 RELEASE_LOCK(&p->mutex);
610                 n=end;
611                 goto found;
612         }
613         /* Let it lock on the last one it used */
614 badexit:
615         ACQUIRE_LOCK(&p->m[*lastUsed]->mutex);
616         return p->m[*lastUsed];
617 found:
618         *lastUsed=n;
619         if(tc)
620                 tc->mymspace=n;
621         else
622         {
623                 if(TLSSET(p->mycache, (void *)(size_t)(-(n+1)))) abort();
624         }
625         return p->m[n];
626 }
627
628 nedpool *nedcreatepool(size_t capacity, int threads) THROWSPEC
629 {
630         nedpool *ret;
631         if(!(ret=(nedpool *) nedpcalloc(0, 1, sizeof(nedpool)))) return 0;
632         if(!InitPool(ret, capacity, threads))
633         {
634                 nedpfree(0, ret);
635                 return 0;
636         }
637         return ret;
638 }
639 void neddestroypool(nedpool *p) THROWSPEC
640 {
641         int n;
642         ACQUIRE_LOCK(&p->mutex);
643         DestroyCaches(p);
644         for(n=0; p->m[n]; n++)
645         {
646                 destroy_mspace(p->m[n]);
647                 p->m[n]=0;
648         }
649         RELEASE_LOCK(&p->mutex);
650         if(TLSFREE(p->mycache)) abort();
651         nedpfree(0, p);
652 }
653
654 void nedpsetvalue(nedpool *p, void *v) THROWSPEC
655 {
656         if(!p) { p=&syspool; if(!syspool.threads) InitPool(&syspool, 0, -1); }
657         p->uservalue=v;
658 }
659 void *nedgetvalue(nedpool **p, void *mem) THROWSPEC
660 {
661         nedpool *np=0;
662         mchunkptr mcp=mem2chunk(mem);
663         mstate fm;
664         if(!(is_aligned(chunk2mem(mcp))) && mcp->head != FENCEPOST_HEAD) return 0;
665         if(!cinuse(mcp)) return 0;
666         if(!next_pinuse(mcp)) return 0;
667         if(!is_mmapped(mcp) && !pinuse(mcp))
668         {
669                 if(next_chunk(prev_chunk(mcp))!=mcp) return 0;
670         }
671         fm=get_mstate_for(mcp);
672         if(!ok_magic(fm)) return 0;
673         if(!ok_address(fm, mcp)) return 0;
674         if(!fm->extp) return 0;
675         np=(nedpool *) fm->extp;
676         if(p) *p=np;
677         return np->uservalue;
678 }
679
680 void neddisablethreadcache(nedpool *p) THROWSPEC
681 {
682         int mycache;
683         if(!p)
684         {
685                 p=&syspool;
686                 if(!syspool.threads) InitPool(&syspool, 0, -1);
687         }
688         mycache=(int)(size_t) TLSGET(p->mycache);
689         if(!mycache)
690         {       /* Set to mspace 0 */
691                 if(TLSSET(p->mycache, (void *)-1)) abort();
692         }
693         else if(mycache>0)
694         {       /* Set to last used mspace */
695                 threadcache *tc=p->caches[mycache-1];
696 #if defined(DEBUG)
697                 printf("Threadcache utilisation: %lf%% in cache with %lf%% lost to other threads\n",
698                         100.0*tc->successes/tc->mallocs, 100.0*((double) tc->mallocs-tc->frees)/tc->mallocs);
699 #endif
700                 if(TLSSET(p->mycache, (void *)(size_t)(-tc->mymspace))) abort();
701                 tc->frees++;
702                 RemoveCacheEntries(p, tc, 0);
703                 assert(!tc->freeInCache);
704                 tc->mymspace=-1;
705                 tc->threadid=0;
706                 mspace_free(0, p->caches[mycache-1]);
707                 p->caches[mycache-1]=0;
708         }
709 }
710
711 #define GETMSPACE(m,p,tc,ms,s,action)           \
712   do                                            \
713   {                                             \
714     mstate m = GetMSpace((p),(tc),(ms),(s));    \
715     action;                                     \
716     RELEASE_LOCK(&m->mutex);                    \
717   } while (0)
718
719 static FORCEINLINE mstate GetMSpace(nedpool *p, threadcache *tc, int mymspace, size_t size) THROWSPEC
720 {       /* Returns a locked and ready for use mspace */
721         mstate m=p->m[mymspace];
722         assert(m);
723         if(!TRY_LOCK(&p->m[mymspace]->mutex)) m=FindMSpace(p, tc, &mymspace, size);\
724         /*assert(IS_LOCKED(&p->m[mymspace]->mutex));*/
725         return m;
726 }
727 static FORCEINLINE void GetThreadCache(nedpool **p, threadcache **tc, int *mymspace, size_t *size) THROWSPEC
728 {
729         int mycache;
730         if(size && *size<sizeof(threadcacheblk)) *size=sizeof(threadcacheblk);
731         if(!*p)
732         {
733                 *p=&syspool;
734                 if(!syspool.threads) InitPool(&syspool, 0, -1);
735         }
736         mycache=(int)(size_t) TLSGET((*p)->mycache);
737         if(mycache>0)
738         {
739                 *tc=(*p)->caches[mycache-1];
740                 *mymspace=(*tc)->mymspace;
741         }
742         else if(!mycache)
743         {
744                 *tc=AllocCache(*p);
745                 if(!*tc)
746                 {       /* Disable */
747                         if(TLSSET((*p)->mycache, (void *)-1)) abort();
748                         *mymspace=0;
749                 }
750                 else
751                         *mymspace=(*tc)->mymspace;
752         }
753         else
754         {
755                 *tc=0;
756                 *mymspace=-mycache-1;
757         }
758         assert(*mymspace>=0);
759         assert((long)(size_t)CURRENT_THREAD==(*tc)->threadid);
760 #ifdef FULLSANITYCHECKS
761         if(*tc)
762         {
763                 if(*(unsigned int *)"NEDMALC1"!=(*tc)->magic1 || *(unsigned int *)"NEDMALC2"!=(*tc)->magic2)
764                 {
765                         abort();
766                 }
767         }
768 #endif
769 }
770
771 void * nedpmalloc(nedpool *p, size_t size) THROWSPEC
772 {
773         void *ret=0;
774         threadcache *tc;
775         int mymspace;
776         GetThreadCache(&p, &tc, &mymspace, &size);
777 #if THREADCACHEMAX
778         if(tc && size<=THREADCACHEMAX)
779         {       /* Use the thread cache */
780                 ret=threadcache_malloc(p, tc, &size);
781         }
782 #endif
783         if(!ret)
784         {       /* Use this thread's mspace */
785         GETMSPACE(m, p, tc, mymspace, size,
786                   ret=mspace_malloc(m, size));
787         }
788         return ret;
789 }
790 void * nedpcalloc(nedpool *p, size_t no, size_t size) THROWSPEC
791 {
792         size_t rsize=size*no;
793         void *ret=0;
794         threadcache *tc;
795         int mymspace;
796         GetThreadCache(&p, &tc, &mymspace, &rsize);
797 #if THREADCACHEMAX
798         if(tc && rsize<=THREADCACHEMAX)
799         {       /* Use the thread cache */
800                 if((ret=threadcache_malloc(p, tc, &rsize)))
801                         memset(ret, 0, rsize);
802         }
803 #endif
804         if(!ret)
805         {       /* Use this thread's mspace */
806         GETMSPACE(m, p, tc, mymspace, rsize,
807                   ret=mspace_calloc(m, 1, rsize));
808         }
809         return ret;
810 }
811 void * nedprealloc(nedpool *p, void *mem, size_t size) THROWSPEC
812 {
813         void *ret=0;
814         threadcache *tc;
815         int mymspace;
816         if(!mem) return nedpmalloc(p, size);
817         GetThreadCache(&p, &tc, &mymspace, &size);
818 #if THREADCACHEMAX
819         if(tc && size && size<=THREADCACHEMAX)
820         {       /* Use the thread cache */
821                 size_t memsize=nedblksize(mem);
822                 assert(memsize);
823                 if((ret=threadcache_malloc(p, tc, &size)))
824                 {
825                         memcpy(ret, mem, memsize<size ? memsize : size);
826                         if(memsize<=THREADCACHEMAX)
827                                 threadcache_free(p, tc, mymspace, mem, memsize);
828                         else
829                                 mspace_free(0, mem);
830                 }
831         }
832 #endif
833         if(!ret)
834         {       /* Reallocs always happen in the mspace they happened in, so skip
835                 locking the preferred mspace for this thread */
836                 ret=mspace_realloc(0, mem, size);
837         }
838         return ret;
839 }
840 void   nedpfree(nedpool *p, void *mem) THROWSPEC
841 {       /* Frees always happen in the mspace they happened in, so skip
842         locking the preferred mspace for this thread */
843         threadcache *tc;
844         int mymspace;
845         size_t memsize;
846         assert(mem);
847         GetThreadCache(&p, &tc, &mymspace, 0);
848 #if THREADCACHEMAX
849         memsize=nedblksize(mem);
850         assert(memsize);
851         if(mem && tc && memsize<=(THREADCACHEMAX+CHUNK_OVERHEAD))
852                 threadcache_free(p, tc, mymspace, mem, memsize);
853         else
854 #endif
855                 mspace_free(0, mem);
856 }
857 void * nedpmemalign(nedpool *p, size_t alignment, size_t bytes) THROWSPEC
858 {
859         void *ret;
860         threadcache *tc;
861         int mymspace;
862         GetThreadCache(&p, &tc, &mymspace, &bytes);
863         {       /* Use this thread's mspace */
864         GETMSPACE(m, p, tc, mymspace, bytes,
865                   ret=mspace_memalign(m, alignment, bytes));
866         }
867         return ret;
868 }
869 #if !NO_MALLINFO
870 struct mallinfo nedpmallinfo(nedpool *p) THROWSPEC
871 {
872         int n;
873         struct mallinfo ret={0};
874         if(!p) { p=&syspool; if(!syspool.threads) InitPool(&syspool, 0, -1); }
875         for(n=0; p->m[n]; n++)
876         {
877                 struct mallinfo t=mspace_mallinfo(p->m[n]);
878                 ret.arena+=t.arena;
879                 ret.ordblks+=t.ordblks;
880                 ret.hblkhd+=t.hblkhd;
881                 ret.usmblks+=t.usmblks;
882                 ret.uordblks+=t.uordblks;
883                 ret.fordblks+=t.fordblks;
884                 ret.keepcost+=t.keepcost;
885         }
886         return ret;
887 }
888 #endif
889 int    nedpmallopt(nedpool *p, int parno, int value) THROWSPEC
890 {
891         return mspace_mallopt(parno, value);
892 }
893 int    nedpmalloc_trim(nedpool *p, size_t pad) THROWSPEC
894 {
895         int n, ret=0;
896         if(!p) { p=&syspool; if(!syspool.threads) InitPool(&syspool, 0, -1); }
897         for(n=0; p->m[n]; n++)
898         {
899                 ret+=mspace_trim(p->m[n], pad);
900         }
901         return ret;
902 }
903 void   nedpmalloc_stats(nedpool *p) THROWSPEC
904 {
905         int n;
906         if(!p) { p=&syspool; if(!syspool.threads) InitPool(&syspool, 0, -1); }
907         for(n=0; p->m[n]; n++)
908         {
909                 mspace_malloc_stats(p->m[n]);
910         }
911 }
912 size_t nedpmalloc_footprint(nedpool *p) THROWSPEC
913 {
914         size_t ret=0;
915         int n;
916         if(!p) { p=&syspool; if(!syspool.threads) InitPool(&syspool, 0, -1); }
917         for(n=0; p->m[n]; n++)
918         {
919                 ret+=mspace_footprint(p->m[n]);
920         }
921         return ret;
922 }
923 void **nedpindependent_calloc(nedpool *p, size_t elemsno, size_t elemsize, void **chunks) THROWSPEC
924 {
925         void **ret;
926         threadcache *tc;
927         int mymspace;
928         GetThreadCache(&p, &tc, &mymspace, &elemsize);
929     GETMSPACE(m, p, tc, mymspace, elemsno*elemsize,
930               ret=mspace_independent_calloc(m, elemsno, elemsize, chunks));
931         return ret;
932 }
933 void **nedpindependent_comalloc(nedpool *p, size_t elems, size_t *sizes, void **chunks) THROWSPEC
934 {
935         void **ret;
936         threadcache *tc;
937         int mymspace;
938     size_t i, *adjustedsizes=(size_t *) alloca(elems*sizeof(size_t));
939     if(!adjustedsizes) return 0;
940     for(i=0; i<elems; i++)
941         adjustedsizes[i]=sizes[i]<sizeof(threadcacheblk) ? sizeof(threadcacheblk) : sizes[i];
942         GetThreadCache(&p, &tc, &mymspace, 0);
943         GETMSPACE(m, p, tc, mymspace, 0,
944               ret=mspace_independent_comalloc(m, elems, adjustedsizes, chunks));
945         return ret;
946 }
947
948 #ifdef OVERRIDE_STRDUP
949 /*
950  * This implementation is purely there to override the libc version, to
951  * avoid a crash due to allocation and free on different 'heaps'.
952  */
953 char *strdup(const char *s1)
954 {
955         char *s2 = 0;
956         if (s1) {
957                 s2 = malloc(strlen(s1) + 1);
958                 strcpy(s2, s1);
959         }
960         return s2;
961 }
962 #endif
963
964 #if defined(__cplusplus)
965 }
966 #endif