git

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
953