Navigation

← Previous Changeset
Next Changeset →

Changeset 252

Timestamp:

02/22/10 16:34:04 (15 years ago)

Author:

schveiguy

Message:

Applying patch for eliminating array stomping from the runtime. See bugzilla issue 3637.

Files:

trunk/src/gc/gc.d (modified) (3 diffs)
trunk/src/gc/gcx.d (modified) (10 diffs)
trunk/src/rt/lifetime.d (modified) (14 diffs)

Legend:

: Unmodified
: Added
: Removed
: Modified
: Copied
: Moved

trunk/src/gc/gc.d

r214	r252
34	34	extern (C) void function() gc_enable;
35	35	extern (C) void function() gc_disable;
36	36	extern (C) void function() gc_collect;
37	37	extern (C) void function() gc_minimize;
38	38
39	39	extern (C) uint function(void*) gc_getAttr;
40	40	extern (C) uint function(void*, uint) gc_setAttr;
41	41	extern (C) uint function(void*, uint) gc_clrAttr;
42	42
43	43	extern (C) void* function(size_t, uint) gc_malloc;
	44	extern (C) BlkInfo function(size_t, uint) gc_malloc_bi;
44	45	extern (C) void* function(size_t, uint) gc_calloc;
45	46	extern (C) void* function(void*, size_t, uint ba) gc_realloc;
46	47	extern (C) size_t function(void*, size_t, size_t) gc_extend;
47	48	extern (C) size_t function(size_t) gc_reserve;
48	49	extern (C) void function(void*) gc_free;
49	50
50	51	extern (C) void* function(void*) gc_addrOf;
51	52	extern (C) size_t function(void*) gc_sizeOf;
52	53
53	54	extern (C) BlkInfo function(void*) gc_query;
…	…
67	68	pthis.gc_enable = &gc_enable;
68	69	pthis.gc_disable = &gc_disable;
69	70	pthis.gc_collect = &gc_collect;
70	71	pthis.gc_minimize = &gc_minimize;
71	72
72	73	pthis.gc_getAttr = &gc_getAttr;
73	74	pthis.gc_setAttr = &gc_setAttr;
74	75	pthis.gc_clrAttr = &gc_clrAttr;
75	76
76	77	pthis.gc_malloc = &gc_malloc;
	78	pthis.gc_malloc_bi = &gc_malloc_bi;
77	79	pthis.gc_calloc = &gc_calloc;
78	80	pthis.gc_realloc = &gc_realloc;
79	81	pthis.gc_extend = &gc_extend;
80	82	pthis.gc_reserve = &gc_reserve;
81	83	pthis.gc_free = &gc_free;
82	84
83	85	pthis.gc_addrOf = &gc_addrOf;
84	86	pthis.gc_sizeOf = &gc_sizeOf;
85	87
86	88	pthis.gc_query = &gc_query;
…	…
180	182	return proxy.gc_clrAttr( p, a );
181	183	}
182	184
183	185	extern (C) void* gc_malloc( size_t sz, uint ba = 0 )
184	186	{
185	187	if( proxy is null )
186	188	return _gc.malloc( sz, ba );
187	189	return proxy.gc_malloc( sz, ba );
188	190	}
189	191
	192	extern (C) BlkInfo gc_malloc_bi( size_t sz, uint ba = 0 )
	193	{
	194	if( proxy is null )
	195	{
	196	BlkInfo retval;
	197	retval.base = _gc.malloc( sz, ba, &retval.size );
	198	retval.attr = ba;
	199	return retval;
	200	}
	201	return proxy.gc_malloc_bi( sz, ba );
	202	}
	203
190	204	extern (C) void* gc_calloc( size_t sz, uint ba = 0 )
191	205	{
192	206	if( proxy is null )
193	207	return _gc.calloc( sz, ba );
194	208	return proxy.gc_calloc( sz, ba );
195	209	}
196	210
197	211	extern (C) void* gc_realloc( void* p, size_t sz, uint ba = 0 )
198	212	{
199	213	if( proxy is null )

trunk/src/gc/gcx.d

r220	r252
386	386	else synchronized (gcLock)
387	387	{
388	388	return go();
389	389	}
390	390	}
391	391
392	392
393	393	/**
394	394	*
395	395	*/
396		void *malloc(size_t size, uint bits = 0)
	396	void malloc(size_t size, uint bits = 0, size_t alloc_size = null)
397	397	{
398	398	if (!size)
399	399	{
	400	if(alloc_size)
	401	*alloc_size = 0;
400	402	return null;
401	403	}
402	404
403	405	// Since a finalizer could launch a new thread, we always need to lock
404	406	// when collecting. The safest way to do this is to simply always lock
405	407	// when allocating.
406	408	synchronized (gcLock)
407	409	{
408		return mallocNoSync(size, bits);
409		}
410		}
411
412
413		//
414		//
415		//
416		private void *mallocNoSync(size_t size, uint bits = 0)
	410	return mallocNoSync(size, bits, alloc_size);
	411	}
	412	}
	413
	414
	415	//
	416	//
	417	//
	418	private void mallocNoSync(size_t size, uint bits = 0, size_t alloc_size = null)
417	419	{
418	420	assert(size != 0);
419	421
420	422	void *p = null;
421	423	Bins bin;
422	424
423	425	//debug(PRINTF) printf("GC::malloc(size = %d, gcx = %p)\n", size, gcx);
424	426	assert(gcx);
425	427	//debug(PRINTF) printf("gcx.self = %x, pthread_self() = %x\n", gcx.self, pthread_self());
426	428
…	…
434	436	bin = lastbin;
435	437	else
436	438	{
437	439	bin = gcx.findBin(size);
438	440	lastsize = size;
439	441	lastbin = bin;
440	442	}
441	443
442	444	if (bin < B_PAGE)
443	445	{
	446	if(alloc_size)
	447	*alloc_size = binsize[bin];
444	448	int state = gcx.disabled ? 1 : 0;
445	449	bool collected = false;
446	450
447	451	while (!gcx.bucket[bin] && !gcx.allocPage(bin))
448	452	{
449	453	switch (state)
450	454	{
451	455	case 0:
452	456	gcx.fullcollectshell();
453	457	collected = true;
…	…
470	474
471	475	// Return next item from free list
472	476	gcx.bucket[bin] = (cast(List*)p).next;
473	477	if( !(bits & BlkAttr.NO_SCAN) )
474	478	memset(p + size, 0, binsize[bin] - size);
475	479	//debug(PRINTF) printf("\tmalloc => %x\n", p);
476	480	debug (MEMSTOMP) memset(p, 0xF0, size);
477	481	}
478	482	else
479	483	{
480		p = gcx.bigAlloc(size);
	484	p = gcx.bigAlloc(size, alloc_size);
481	485	if (!p)
482	486	onOutOfMemoryError();
483	487	}
484	488	size -= SENTINEL_EXTRA;
485	489	p = sentinel_add(p);
486	490	sentinel_init(p, size);
487	491	gcx.log_malloc(p, size);
488	492
489	493	if (bits)
490	494	{
…	…
493	497
494	498	gcx.setBits(pool, cast(size_t)(p - pool.baseAddr) / 16, bits);
495	499	}
496	500	return p;
497	501	}
498	502
499	503
500	504	/**
501	505	*
502	506	*/
503		void *calloc(size_t size, uint bits = 0)
	507	void calloc(size_t size, uint bits = 0, size_t alloc_size = null)
504	508	{
505	509	if (!size)
506	510	{
	511	if(alloc_size)
	512	*alloc_size = 0;
507	513	return null;
508	514	}
509	515
510	516	// Since a finalizer could launch a new thread, we always need to lock
511	517	// when collecting. The safest way to do this is to simply always lock
512	518	// when allocating.
513	519	synchronized (gcLock)
514	520	{
515		return callocNoSync(size, bits);
516		}
517		}
518
519
520		//
521		//
522		//
523		private void *callocNoSync(size_t size, uint bits = 0)
	521	return callocNoSync(size, bits, alloc_size);
	522	}
	523	}
	524
	525
	526	//
	527	//
	528	//
	529	private void callocNoSync(size_t size, uint bits = 0, size_t alloc_size = null)
524	530	{
525	531	assert(size != 0);
526	532
527	533	//debug(PRINTF) printf("calloc: %x len %d\n", p, len);
528		void *p = mallocNoSync(size, bits);
	534	void *p = mallocNoSync(size, bits, alloc_size);
529	535	memset(p, 0, size);
530	536	return p;
531	537	}
532	538
533	539
534	540	/**
535	541	*
536	542	*/
537		void realloc(void p, size_t size, uint bits = 0)
	543	void realloc(void p, size_t size, uint bits = 0, size_t *alloc_size = null)
538	544	{
539	545	// Since a finalizer could launch a new thread, we always need to lock
540	546	// when collecting. The safest way to do this is to simply always lock
541	547	// when allocating.
542	548	synchronized (gcLock)
543	549	{
544		return reallocNoSync(p, size, bits);
545		}
546		}
547
548
549		//
550		//
551		//
552		private void reallocNoSync(void p, size_t size, uint bits = 0)
	550	return reallocNoSync(p, size, bits, alloc_size);
	551	}
	552	}
	553
	554
	555	//
	556	//
	557	//
	558	private void reallocNoSync(void p, size_t size, uint bits = 0, size_t *alloc_size = null)
553	559	{
554	560	if (!size)
555	561	{ if (p)
556	562	{ freeNoSync(p);
557	563	p = null;
558	564	}
	565	if(alloc_size)
	566	*alloc_size = 0;
559	567	}
560	568	else if (!p)
561	569	{
562		p = mallocNoSync(size, bits);
	570	p = mallocNoSync(size, bits, alloc_size);
563	571	}
564	572	else
565	573	{ void *p2;
566	574	size_t psize;
567	575
568	576	//debug(PRINTF) printf("GC::realloc(p = %x, size = %u)\n", p, size);
569	577	version (SENTINEL)
570	578	{
571	579	sentinel_Invariant(p);
572	580	psize = *sentinel_size(p);
…	…
584	592	{
585	593	gcx.clrBits(pool, biti, BlkAttr.ALL_BITS);
586	594	gcx.setBits(pool, biti, bits);
587	595	}
588	596	else
589	597	{
590	598	bits = gcx.getBits(pool, biti);
591	599	}
592	600	}
593	601	}
594		p2 = mallocNoSync(size, bits);
	602	p2 = mallocNoSync(size, bits, alloc_size);
595	603	if (psize < size)
596	604	size = psize;
597	605	//debug(PRINTF) printf("\tcopying %d bytes\n",size);
598	606	memcpy(p2, p, size);
599	607	p = p2;
600	608	}
601	609	}
602	610	else
603	611	{
604	612	psize = gcx.findSize(p); // find allocated size
…	…
612	620	auto pool = gcx.findPool(p);
613	621	auto pagenum = (p - pool.baseAddr) / PAGESIZE;
614	622
615	623	if (newsz < psz)
616	624	{ // Shrink in place
617	625	synchronized (gcLock)
618	626	{
619	627	debug (MEMSTOMP) memset(p + size, 0xF2, psize - size);
620	628	pool.freePages(pagenum + newsz, psz - newsz);
621	629	}
	630	if(alloc_size)
	631	alloc_size = newsz PAGESIZE;
622	632	return p;
623	633	}
624	634	else if (pagenum + newsz <= pool.npages)
625	635	{
626	636	// Attempt to expand in place
627	637	synchronized (gcLock)
628	638	{
629	639	for (size_t i = pagenum + psz; 1;)
630	640	{
631	641	if (i == pagenum + newsz)
632	642	{
633	643	debug (MEMSTOMP) memset(p + psize, 0xF0, size - psize);
634	644	memset(&pool.pagetable[pagenum + psz], B_PAGEPLUS, newsz - psz);
	645	if(alloc_size)
	646	alloc_size = newsz PAGESIZE;
635	647	return p;
636	648	}
637	649	if (i == pool.ncommitted)
638	650	{
639	651	auto u = pool.extendPages(pagenum + newsz - pool.ncommitted);
640	652	if (u == OPFAIL)
641	653	break;
642	654	i = pagenum + newsz;
643	655	continue;
644	656	}
…	…
664	676	{
665	677	gcx.clrBits(pool, biti, BlkAttr.ALL_BITS);
666	678	gcx.setBits(pool, biti, bits);
667	679	}
668	680	else
669	681	{
670	682	bits = gcx.getBits(pool, biti);
671	683	}
672	684	}
673	685	}
674		p2 = mallocNoSync(size, bits);
	686	p2 = mallocNoSync(size, bits, alloc_size);
675	687	if (psize < size)
676	688	size = psize;
677	689	//debug(PRINTF) printf("\tcopying %d bytes\n",size);
678	690	memcpy(p2, p, size);
679	691	p = p2;
680	692	}
	693	else if(alloc_size)
	694	*alloc_size = psize;
681	695	}
682	696	}
683	697	return p;
684	698	}
685	699
686	700
687	701	/**
688	702	* Attempt to in-place enlarge the memory block pointed to by p by at least
689	703	* minbytes beyond its current capacity, up to a maximum of maxsize. This
690	704	* does not attempt to move the memory block (like realloc() does).
…	…
1774	1788	size_t offset = cast(size_t)(p - pool.baseAddr);
1775	1789	size_t pn = offset / PAGESIZE;
1776	1790	Bins bin = cast(Bins)pool.pagetable[pn];
1777	1791
1778	1792	////////////////////////////////////////////////////////////////////
1779	1793	// findAddr
1780	1794	////////////////////////////////////////////////////////////////////
1781	1795
1782	1796	if (bin <= B_PAGE)
1783	1797	{
1784		info.base = ~~pool.baseAddr + (offset~~ & notbinsize[bin]);
	1798	info.base = cast(void*)((cast(size_t)p) & notbinsize[bin]);
1785	1799	}
1786	1800	else if (bin == B_PAGEPLUS)
1787	1801	{
1788	1802	do
1789	1803	{ --pn, offset -= PAGESIZE;
1790	1804	} while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS);
1791	1805
1792	1806	info.base = pool.baseAddr + (offset & (offset.max ^ (PAGESIZE-1)));
1793	1807
1794	1808	// fix bin for use by size calc below
…	…
1922	1936	minAddr = pooltable[0].baseAddr;
1923	1937	maxAddr = pooltable[npools - 1].topAddr;
1924	1938	}
1925	1939	}
1926	1940
1927	1941
1928	1942	/**
1929	1943	* Allocate a chunk of memory that is larger than a page.
1930	1944	* Return null if out of memory.
1931	1945	*/
1932		void *bigAlloc(size_t size)
	1946	void bigAlloc(size_t size, size_t alloc_size = null)
1933	1947	{
1934	1948	Pool* pool;
1935	1949	size_t npages;
1936	1950	size_t n;
1937	1951	size_t pn;
1938	1952	size_t freedpages;
1939	1953	void* p;
1940	1954	int state;
1941	1955	bool collected = false;
1942	1956
…	…
1999	2013	}
2000	2014	}
2001	2015
2002	2016	L1:
2003	2017	pool.pagetable[pn] = B_PAGE;
2004	2018	if (npages > 1)
2005	2019	memset(&pool.pagetable[pn + 1], B_PAGEPLUS, npages - 1);
2006	2020	p = pool.baseAddr + pn * PAGESIZE;
2007	2021	memset(cast(char )p + size, 0, npages PAGESIZE - size);
2008	2022	debug (MEMSTOMP) memset(p, 0xF1, size);
	2023	if(alloc_size)
	2024	alloc_size = npages PAGESIZE;
2009	2025	//debug(PRINTF) printf("\tp = %x\n", p);
2010	2026	return p;
2011	2027
2012	2028	Lnomemory:
2013	2029	return null; // let caller handle the error
2014	2030	}
2015	2031
2016	2032
2017	2033	/**
2018	2034	* Allocate a new pool with at least npages in it.

trunk/src/rt/lifetime.d

r220	r252
40	40	void* base;
41	41	size_t size;
42	42	uint attr;
43	43	}
44	44
45	45	extern (C) uint gc_getAttr( in void* p );
46	46	extern (C) uint gc_setAttr( in void* p, uint a );
47	47	extern (C) uint gc_clrAttr( in void* p, uint a );
48	48
49	49	extern (C) void* gc_malloc( size_t sz, uint ba = 0 );
	50	extern (C) BlkInfo gc_malloc_bi( size_t sz, uint ba = 0 );
50	51	extern (C) void* gc_calloc( size_t sz, uint ba = 0 );
51	52	extern (C) size_t gc_extend( void* p, size_t mx, size_t sz );
52	53	extern (C) void gc_free( void* p );
53	54
54	55	extern (C) void* gc_addrOf( in void* p );
55	56	extern (C) size_t gc_sizeOf( in void* p );
56	57	extern (C) BlkInfo gc_query( in void* p );
57	58
58	59	extern (C) void onFinalizeError( ClassInfo c, Throwable e );
59	60	extern (C) void onOutOfMemoryError();
60	61
61	62	extern (C) void _d_monitordelete(Object h, bool det = true);
62	63
63	64	enum
64	65	{
65	66	PAGESIZE = 4096
66	67	}
67	68
68	69	alias bool function(Object) CollectHandler;
69	70	__gshared CollectHandler collectHandler = null;
	71
	72	enum : size_t
	73	{
	74	LENGTHMASK = ~(cast(size_t)0x0ff),
	75	BIGLENGTHMASK = ~(cast(size_t)PAGESIZE - 1),
	76	SMALLPAD = 1,
	77	MEDPAD = ushort.sizeof,
	78	LARGEPAD = size_t.sizeof * 2 + 1,
	79	}
70	80	}
71	81
72	82
73	83	/**
74	84	*
75	85	*/
76	86	extern (C) void* _d_allocmemory(size_t sz)
77	87	{
78	88	return gc_malloc(sz);
79	89	}
…	…
92	102	* using AddRef() and Release(). They get free'd by C's free()
93	103	* function called by Release() when Release()'s reference count goes
94	104	* to zero.
95	105	*/
96	106	p = malloc(ci.init.length);
97	107	if (!p)
98	108	onOutOfMemoryError();
99	109	}
100	110	else
101	111	{
102		~~p = gc_malloc(ci.init.length~~,
	112	auto info = gc_malloc_bi(ci.init.length + __arrayPad(ci.init.length),
103	113	BlkAttr.FINALIZE \| (ci.m_flags & 2 ? BlkAttr.NO_SCAN : 0));
	114	p = info.base;
	115	// only init ghost array length if noscan is set. Scanned blocks are
	116	// initialized to 0 by the gc.
	117	if(ci.flags & 2)
	118	{
	119	// initialize the ghost array length at the end of the block. This
	120	// prevents accidental stomping in the case where a class contains
	121	// a static array and someone tries to append to a slice of that
	122	// array.
	123	((cast(size_t )(p + info.size)) - 1) = 0;
	124	}
104	125	debug(PRINTF) printf(" p = %p\n", p);
105	126	}
106	127
107	128	debug(PRINTF)
108	129	{
109	130	printf("p = %p\n", p);
110	131	printf("ci = %p, ci.init = %p, len = %d\n", ci, ci.init, ci.init.length);
111	132	printf("vptr = %p\n", cast(void*) ci.init);
112	133	printf("vtbl[0] = %p\n", (cast(void**) ci.init)[0]);
113	134	printf("vtbl[1] = %p\n", (cast(void**) ci.init)[1]);
…	…
172	193	}
173	194	else
174	195	{
175	196	rt_finalize(cast(void) p);
176	197	}
177	198	gc_free(cast(void) p);
178	199	*p = null;
179	200	}
180	201	}
181	202
	203	/** dummy class used to lock for shared array appending */
	204	private class ArrayAllocLengthLock
	205	{}
	206
	207
	208	/**
	209	Set the allocated length of the array block. This is called
	210	any time an array is appended to or its length is set.
	211
	212	The allocated block looks like this for blocks < PAGESIZE:
	213
	214	\|elem0\|elem1\|elem2\|...\|elemN-1\|emptyspace\|N*elemsize\|
	215
	216
	217	The size of the allocated length at the end depends on the block size:
	218
	219	a block of 16 to 256 bytes has an 8-bit length.
	220
	221	a block with 512 to pagesize/2 bytes has a 16-bit length.
	222
	223	For blocks >= pagesize, the length is a size_t and is at the beginning of the
	224	block. The reason we have to do this is because the block can extend into
	225	more pages, so we cannot trust the block length if it sits at the end of the
	226	block, because it might have just been extended. If we can prove in the
	227	future that the block is unshared, we may be able to change this, but I'm not
	228	sure it's important.
	229
	230	In order to do put the length at the front, we have to provide 2*size_t bytes
	231	buffer space in case the block has to be aligned properly. For example, on a
	232	32-bit OS, doubles should be 8-byte aligned. In addition, we need the
	233	sentinel byte to prevent accidental pointers to the next block. Because of
	234	the extra overhead, we only do this for page size and above, where the
	235	overhead is minimal compared to the block size.
	236
	237	So for those blocks, it looks like:
	238
	239	\|N*elemsize\|padding\|elem0\|elem1\|...\|elemN-1\|emptyspace\|sentinelbyte\|
	240
	241	where elem0 starts 8 bytes after the first byte.
	242	*/
	243	bool __setArrayAllocLength(ref BlkInfo info, size_t newlength, bool isshared, size_t oldlength = ~0)
	244	{
	245	if(info.size <= 256)
	246	{
	247	if(newlength + SMALLPAD > info.size)
	248	// new size does not fit inside block
	249	return false;
	250	auto length = cast(ubyte *)(info.base + info.size - SMALLPAD);
	251	if(oldlength != ~0)
	252	{
	253	if(isshared)
	254	{
	255	synchronized(typeid(ArrayAllocLengthLock))
	256	{
	257	if(*length == cast(ubyte)oldlength)
	258	*length = cast(ubyte)newlength;
	259	else
	260	return false;
	261	}
	262	}
	263	else
	264	{
	265	if(*length == cast(ubyte)oldlength)
	266	*length = cast(ubyte)newlength;
	267	else
	268	return false;
	269	}
	270	}
	271	else
	272	{
	273	// setting the initial length, no lock needed
	274	*length = cast(ubyte)newlength;
	275	}
	276	}
	277	else if(info.size < PAGESIZE)
	278	{
	279	if(newlength + MEDPAD > info.size)
	280	// new size does not fit inside block
	281	return false;
	282	auto length = cast(ushort *)(info.base + info.size - MEDPAD);
	283	if(oldlength != ~0)
	284	{
	285	if(isshared)
	286	{
	287	synchronized(typeid(ArrayAllocLengthLock))
	288	{
	289	if(*length == oldlength)
	290	*length = cast(ushort)newlength;
	291	else
	292	return false;
	293	}
	294	}
	295	else
	296	{
	297	if(*length == oldlength)
	298	*length = cast(ushort)newlength;
	299	else
	300	return false;
	301	}
	302	}
	303	else
	304	{
	305	// setting the initial length, no lock needed
	306	*length = cast(ushort)newlength;
	307	}
	308	}
	309	else
	310	{
	311	if(newlength + LARGEPAD > info.size)
	312	// new size does not fit inside block
	313	return false;
	314	auto length = cast(size_t *)(info.base);
	315	if(oldlength != ~0)
	316	{
	317	if(isshared)
	318	{
	319	synchronized(typeid(ArrayAllocLengthLock))
	320	{
	321	if(*length == oldlength)
	322	*length = newlength;
	323	else
	324	return false;
	325	}
	326	}
	327	else
	328	{
	329	if(*length == oldlength)
	330	*length = newlength;
	331	else
	332	return false;
	333	}
	334	}
	335	else
	336	{
	337	// setting the initial length, no lock needed
	338	*length = newlength;
	339	}
	340	}
	341	return true; // resize succeeded
	342	}
	343
	344	/**
	345	get the start of the array for the given block
	346	*/
	347	void *__arrayStart(BlkInfo info)
	348	{
	349	return info.base + ((info.size & BIGLENGTHMASK) ? 2*size_t.sizeof : 0);
	350	}
	351
	352	size_t __arrayPad(size_t size)
	353	{
	354	return (size & BIGLENGTHMASK) ? LARGEPAD : (size & LENGTHMASK) ? MEDPAD : SMALLPAD;
	355	}
	356
	357	/**
	358	cache for the lookup of the block info
	359	*/
	360	enum N_CACHE_BLOCKS=8;
	361	static if(N_CACHE_BLOCKS==1)
	362	{
	363	version=single_cache;
	364	// note this is TLS, so no need to sync.
	365	BlkInfo __blkcache;
	366	}
	367	else
	368	{
	369	//version=simple_cache; // uncomment to test simple cache strategy
	370
	371	// ensure N_CACHE_BLOCKS is power of 2.
	372	static assert(!((N_CACHE_BLOCKS - 1) & N_CACHE_BLOCKS));
	373
	374	// note this is TLS, so no need to sync.
	375	BlkInfo __blkcache[N_CACHE_BLOCKS];
	376	int __nextBlkIdx;
	377	}
	378
	379
	380	/**
	381	Get the cached block info of an interior pointer. Returns null if the
	382	interior pointer's block is not cached.
	383	*/
	384	BlkInfo __getBlkInfo(void interior)
	385	{
	386	version(single_cache)
	387	{
	388	BlkInfo *ptr = &__blkcache;
	389	if(ptr.base <= interior && (interior - ptr.base) < ptr.size)
	390	return ptr;
	391	return null; // not in cache.
	392	}
	393	else
	394	{
	395	version(simple_cache)
	396	{
	397	BlkInfo *ptr = __blkcache.ptr;
	398	foreach(i; 0..N_CACHE_BLOCKS)
	399	{
	400	if(ptr.base <= interior && (interior - ptr.base) < ptr.size)
	401	return ptr;
	402	ptr++;
	403	}
	404	}
	405	else
	406	{
	407	// try to do a smart lookup, using __nextBlkIdx as the "head"
	408	BlkInfo *ptr = __blkcache.ptr;
	409	for(int i = __nextBlkIdx; i >= 0; --i)
	410	{
	411	if(ptr[i].base <= interior && (interior - ptr[i].base) < ptr.size)
	412	return ptr + i;
	413	}
	414
	415	for(int i = N_CACHE_BLOCKS - 1; i > __nextBlkIdx; --i)
	416	{
	417	if(ptr[i].base <= interior && (interior - ptr[i].base) < ptr.size)
	418	return ptr + i;
	419	}
	420	}
	421	return null; // not in cache.
	422	}
	423	}
	424
	425	void __insertBlkInfoCache(BlkInfo bi, BlkInfo *curpos)
	426	{
	427	version(single_cache)
	428	{
	429	__blkcache = bi;
	430	}
	431	else
	432	{
	433	version(simple_cache)
	434	{
	435	if(curpos)
	436	*curpos = bi;
	437	else
	438	{
	439	// note, this is a super-simple algorithm that does not care about
	440	// most recently used. It simply uses a round-robin technique to
	441	// cache block info. This means that the ordering of the cache
	442	// doesn't mean anything. Certain patterns of allocation may
	443	// render the cache near-useless.
	444	__blkcache.ptr[__nextBlkIdx] = bi;
	445	__nextBlkIdx = (__nextBlkIdx+1) & (N_CACHE_BLOCKS - 1);
	446	}
	447	}
	448	else
	449	{
	450	//
	451	// strategy: If the block currently is in the cache, swap it with
	452	// the head element. Otherwise, move the head element up by one,
	453	// and insert it there.
	454	//
	455	auto cache = __blkcache.ptr;
	456	if(!curpos)
	457	{
	458	__nextBlkIdx = (__nextBlkIdx+1) & (N_CACHE_BLOCKS - 1);
	459	curpos = cache + __nextBlkIdx;
	460	}
	461	else if(curpos !is cache + __nextBlkIdx)
	462	{
	463	*curpos = cache[__nextBlkIdx];
	464	curpos = cache + __nextBlkIdx;
	465	}
	466	*curpos = bi;
	467	}
	468	}
	469	}
182	470
183	471	/**
184	472	* Allocate a new array of length elements.
185	473	* ti is the type of the resulting array, or pointer to element.
186	474	* (For when the array is initialized to 0)
187	475	*/
188	476	extern (C) ulong _d_newarrayT(TypeInfo ti, size_t length)
189	477	{
190		~~void* p;~~
191	478	ulong result;
192	479	auto size = ti.next.tsize(); // array element size
193	480
194	481	debug(PRINTF) printf("_d_newarrayT(length = x%x, size = %d)\n", length, size);
195	482	if (length == 0 \|\| size == 0)
196	483	result = 0;
197	484	else
198	485	{
199	486	version (D_InlineAsm_X86)
200	487	{
201	488	asm
202	489	{
203	490	mov EAX,size ;
204	491	mul EAX,length ;
205	492	mov size,EAX ;
206	493	jc Loverflow ;
207	494	}
208	495	}
209	496	else
210	497	size *= length;
211		p = gc_malloc(size + 1, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
212		debug(PRINTF) printf(" p = %p\n", p);
213		memset(p, 0, size);
214		result = cast(ulong)length + (cast(ulong)cast(uint)p << 32);
	498	// increase the size by 1 if the actual requested size is < 256,
	499	// by size_t.sizeof if it's >= 256
	500
	501	auto info = gc_malloc_bi(size + __arrayPad(size), !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
	502	debug(PRINTF) printf(" p = %p\n", info.base);
	503	// update the length of the array
	504	memset(info.base, 0, size);
	505	auto isshared = ti.classinfo is TypeInfo_Shared.classinfo;
	506	__setArrayAllocLength(info, size, isshared);
	507	result = cast(ulong)length + (cast(ulong)cast(size_t)__arrayStart(info) << 32);
215	508	}
216	509	return result;
217	510
218	511	Loverflow:
219	512	onOutOfMemoryError();
220	513	}
221	514
222	515	/**
223	516	* For when the array has a non-zero initializer.
224	517	*/
…	…
241	534	asm
242	535	{
243	536	mov EAX,size ;
244	537	mul EAX,length ;
245	538	mov size,EAX ;
246	539	jc Loverflow ;
247	540	}
248	541	}
249	542	else
250	543	size *= length;
251		auto p = gc_malloc(size + 1, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
252		debug(PRINTF) printf(" p = %p\n", p);
	544
	545	auto info = gc_malloc_bi(size + __arrayPad(size), !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
	546	debug(PRINTF) printf(" p = %p\n", info.base);
253	547	if (isize == 1)
254		memset(p, cast(ubyte)q, size);
	548	memset(info.base, cast(ubyte)q, size);
255	549	else if (isize == int.sizeof)
256	550	{
257	551	int init = cast(int)q;
258	552	size /= int.sizeof;
259	553	for (size_t u = 0; u < size; u++)
260	554	{
261		(cast(int*)p)[u] = init;
	555	(cast(int*)info.base)[u] = init;
262	556	}
263	557	}
264	558	else
265	559	{
266	560	for (size_t u = 0; u < size; u += isize)
267	561	{
268		memcpy(p + u, q, isize);
	562	memcpy(info.base + u, q, isize);
269	563	}
270	564	}
271	565	va_end(q);
272		result = cast(ulong)length + (cast(ulong)cast(uint)p << 32);
	566	auto isshared = ti.classinfo is TypeInfo_Shared.classinfo;
	567	__setArrayAllocLength(info, size, isshared);
	568	result = cast(ulong)length + (cast(ulong)cast(uint)__arrayStart(info) << 32);
273	569	}
274	570	return result;
275	571
276	572	Loverflow:
277	573	onOutOfMemoryError();
278	574	}
279	575
280	576	/**
281	577	*
282	578	*/
…	…
297	593	void[] p;
298	594
299	595	debug(PRINTF) printf("foo(ti = %p, ti.next = %p, dim = %d, ndims = %d\n", ti, ti.next, dim, ndims);
300	596	if (ndims == 1)
301	597	{
302	598	auto r = _d_newarrayT(ti, dim);
303	599	p = cast(void[])(&r);
304	600	}
305	601	else
306	602	{
307		p = gc_malloc(dim * (void[]).sizeof + 1)[0 .. dim];
	603	auto allocsize = (void[]).sizeof * dim;
	604	auto info = gc_malloc_bi(allocsize + __arrayPad(allocsize));
	605	auto isshared = ti.classinfo is TypeInfo_Shared.classinfo;
	606	__setArrayAllocLength(info, allocsize, isshared);
	607	p = __arrayStart(info)[0 .. dim];
308	608	for (int i = 0; i < dim; i++)
309	609	{
310	610	(cast(void[]*)p.ptr)[i] = foo(ti.next, pdim + 1, ndims - 1);
311	611	}
312	612	}
313	613	return p;
314	614	}
315	615
316	616	size_t* pdim = cast(size_t *)q;
317	617	result = cast(ulong)foo(ti, pdim, ndims);
…	…
350	650	size_t dim = *pdim;
351	651	void[] p;
352	652
353	653	if (ndims == 1)
354	654	{
355	655	auto r = _d_newarrayiT(ti, dim);
356	656	p = cast(void[])(&r);
357	657	}
358	658	else
359	659	{
360		p = gc_malloc(dim * (void[]).sizeof + 1)[0 .. dim];
	660	auto allocsize = (void[]).sizeof * dim;
	661	auto info = gc_malloc_bi(allocsize + __arrayPad(allocsize));
	662	auto isshared = ti.classinfo is TypeInfo_Shared.classinfo;
	663	__setArrayAllocLength(info, allocsize, isshared);
	664	p = __arrayStart(info)[0 .. dim];
361	665	for (int i = 0; i < dim; i++)
362	666	{
363	667	(cast(void[]*)p.ptr)[i] = foo(ti.next, pdim + 1, ndims - 1);
364	668	}
365	669	}
366	670	return p;
367	671	}
368	672
369	673	size_t* pdim = cast(size_t *)q;
370	674	result = cast(ulong)foo(ti, pdim, ndims);
…	…
574	878	else
575	879	{
576	880	size_t newsize = sizeelem * newlength;
577	881
578	882	if (newsize / newlength != sizeelem)
579	883	goto Loverflow;
580	884	}
581	885
582	886	debug(PRINTF) printf("newsize = %x, newlength = %x\n", newsize, newlength);
583	887
	888	auto isshared = ti.classinfo is TypeInfo_Shared.classinfo;
	889
584	890	if (p.data)
585	891	{
586	892	newdata = p.data;
587	893	if (newlength > p.length)
588	894	{
589	895	size_t size = p.length * sizeelem;
590		auto info = gc_query(p.data);
591
592		if (info.size <= newsize \|\| info.base != p.data)
	896	auto bic = !isshared ? __getBlkInfo(p.data) : null;
	897	auto info = bic ? *bic : gc_query(p.data);
	898	// calculate the extent of the array given the base.
	899	size_t offset = p.data - __arrayStart(info);
	900	if(info.size >= PAGESIZE)
593	901	{
594		if (info.size >= PAGESIZE && info.base == p.data)
595		{ // Try to extend in-place
596		auto u = gc_extend(p.data, (newsize + 1) - info.size, (newsize + 1) - info.size);
597		if (u)
	902	// size of array is at the front of the block
	903	if(!__setArrayAllocLength(info, newsize + offset, isshared, size + offset))
	904	{
	905	// check to see if it failed because there is not
	906	// enough space
	907	if((cast(size_t)info.base) == size + offset)
598	908	{
599		goto L1;
	909	// not enough space, try extending
	910	auto extendsize = newsize + offset + LARGEPAD - info.size;
	911	auto u = gc_extend(p.data, extendsize, extendsize);
	912	if(u)
	913	{
	914	// extend worked, now try setting the length
	915	// again.
	916	info.size = u;
	917	if(__setArrayAllocLength(info, newsize + offset, isshared, size + offset))
	918	{
	919	if(!isshared)
	920	__insertBlkInfoCache(info, bic);
	921	goto L1;
	922	}
	923	}
600	924	}
	925
	926	// couldn't do it, reallocate
	927	info = gc_malloc_bi(newsize + LARGEPAD, info.attr);
	928	__setArrayAllocLength(info, newsize, isshared);
	929	if(!isshared)
	930	__insertBlkInfoCache(info, bic);
	931	newdata = cast(byte )(info.base + size_t.sizeof 2);
	932	newdata[0 .. size] = p.data[0 .. size];
601	933	}
602		newdata = cast(byte *)gc_malloc(newsize + 1, info.attr);
	934	}
	935	else if(!__setArrayAllocLength(info, newsize + offset, isshared, size + offset))
	936	{
	937	// could not resize in place
	938	info = gc_malloc_bi(newsize + __arrayPad(newsize), info.attr);
	939	__setArrayAllocLength(info, newsize, isshared);
	940	if(!isshared)
	941	__insertBlkInfoCache(info, bic);
	942	newdata = cast(byte *)__arrayStart(info);
603	943	newdata[0 .. size] = p.data[0 .. size];
	944	}
	945	else if(!isshared && !bic)
	946	{
	947	// add this to the cache, it wasn't present previously.
	948	__insertBlkInfoCache(info, null);
604	949	}
605	950	L1:
606	951	newdata[size .. newsize] = 0;
607	952	}
608	953	}
609	954	else
610	955	{
611		newdata = cast(byte *)gc_calloc(newsize + 1, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
	956	// pointer was null, need to allocate
	957	auto info = gc_malloc_bi(newsize + __arrayPad(newsize), !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
	958	__setArrayAllocLength(info, newsize, isshared);
	959	if(!isshared)
	960	__insertBlkInfoCache(info, null);
	961	newdata = cast(byte *)__arrayStart(info);
	962	newdata[0 .. newsize] = 0;
612	963	}
613	964	}
614	965	else
615	966	{
616	967	newdata = p.data;
617	968	}
618	969
619	970	p.data = newdata;
620	971	p.length = newlength;
621	972	return newdata[0 .. newlength];
…	…
674	1026	else
675	1027	{
676	1028	size_t newsize = sizeelem * newlength;
677	1029
678	1030	if (newsize / newlength != sizeelem)
679	1031	goto Loverflow;
680	1032	}
681	1033	debug(PRINTF) printf("newsize = %x, newlength = %x\n", newsize, newlength);
682	1034
683	1035	size_t size = p.length * sizeelem;
684
	1036	auto isshared = ti.classinfo is TypeInfo_Shared.classinfo;
685	1037	if (p.data)
686	1038	{
687	1039	newdata = p.data;
688	1040	if (newlength > p.length)
689	1041	{
690		auto info = gc_query(p.data);
691
692		if (info.size <= newsize \|\| info.base != p.data)
	1042	auto bic = !isshared ? __getBlkInfo(p.data) : null;
	1043	auto info = bic ? *bic : gc_query(p.data);
	1044
	1045	// calculate the extent of the array given the base.
	1046	size_t offset = p.data - __arrayStart(info);
	1047	if(info.size >= PAGESIZE)
693	1048	{
694		if (info.size >= PAGESIZE && info.base == p.data)
695		{ // Try to extend in-place
696		auto u = gc_extend(p.data, (newsize + 1) - info.size, (newsize + 1) - info.size);
697		if (u)
	1049	// size of array is at the front of the block
	1050	if(!__setArrayAllocLength(info, newsize + offset, isshared, size + offset))
	1051	{
	1052	// check to see if it failed because there is not
	1053	// enough space
	1054	if((cast(size_t)info.base) == size + offset)
698	1055	{
699		goto L1;
	1056	// not enough space, try extending
	1057	auto extendsize = newsize + offset + LARGEPAD - info.size;
	1058	auto u = gc_extend(p.data, extendsize, extendsize);
	1059	if(u)
	1060	{
	1061	// extend worked, now try setting the length
	1062	// again.
	1063	info.size = u;
	1064	if(__setArrayAllocLength(info, newsize + offset, isshared, size + offset))
	1065	{
	1066	if(!isshared)
	1067	__insertBlkInfoCache(info, bic);
	1068	goto L1;
	1069	}
	1070	}
700	1071	}
	1072
	1073	// couldn't do it, reallocate
	1074	info = gc_malloc_bi(newsize + LARGEPAD, info.attr);
	1075	__setArrayAllocLength(info, newsize, isshared);
	1076	if(!isshared)
	1077	__insertBlkInfoCache(info, bic);
	1078	newdata = cast(byte )(info.base + size_t.sizeof 2);
	1079	newdata[0 .. size] = p.data[0 .. size];
701	1080	}
702		newdata = cast(byte *)gc_malloc(newsize + 1, info.attr);
	1081	}
	1082	else if(!__setArrayAllocLength(info, newsize + offset, isshared, size + offset))
	1083	{
	1084	// could not resize in place
	1085	info = gc_malloc_bi(newsize + __arrayPad(newsize), info.attr);
	1086	__setArrayAllocLength(info, newsize, isshared);
	1087	if(!isshared)
	1088	__insertBlkInfoCache(info, bic);
	1089	newdata = cast(byte *)__arrayStart(info);
703	1090	newdata[0 .. size] = p.data[0 .. size];
	1091	}
	1092	else if(!isshared && !bic)
	1093	{
	1094	// add this to the cache, it wasn't present previously.
	1095	__insertBlkInfoCache(info, null);
	1096	}
704	1097	L1: ;
705		}
706	1098	}
707	1099	}
708	1100	else
709	1101	{
710		newdata = cast(byte *)gc_malloc(newsize + 1, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
	1102	// length was zero, need to allocate
	1103	auto info = gc_malloc_bi(newsize + __arrayPad(newsize), !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
	1104	__setArrayAllocLength(info, newsize, isshared);
	1105	if(!isshared)
	1106	__insertBlkInfoCache(info, null);
	1107	newdata = cast(byte *)__arrayStart(info);
711	1108	}
712	1109
713	1110	auto q = initializer.ptr; // pointer to initializer
714	1111
715	1112	if (newsize > size)
716	1113	{
717	1114	if (initsize == 1)
718	1115	{
719	1116	debug(PRINTF) printf("newdata = %p, size = %d, newsize = %d, q = %d\n", newdata, size, newsize, cast(byte*)q);
720	1117	newdata[size .. newsize] = (cast(byte)q);
…	…
741	1138	onOutOfMemoryError();
742	1139	}
743	1140
744	1141
745	1142	/**
746	1143	* Append y[] to array x[].
747	1144	* size is size of each array element.
748	1145	*/
749	1146	extern (C) long _d_arrayappendT(TypeInfo ti, Array *px, byte[] y)
750	1147	{
	1148	// only optimize array append where ti is not a shared type
751	1149	auto sizeelem = ti.next.tsize(); // array element size
752		auto info = gc_query(px.data);
	1150	auto isshared = ti.classinfo is TypeInfo_Shared.classinfo;
	1151	auto bic = !isshared ? __getBlkInfo(px.data) : null;
	1152	auto info = bic ? *bic : gc_query(px.data);
753	1153	auto length = px.length;
754	1154	auto newlength = length + y.length;
755	1155	auto newsize = newlength * sizeelem;
756
757		if (info.size < newsize \|\| info.base != px.data)
758		{ byte* newdata;
759
760		if (info.size >= PAGESIZE && info.base == px.data)
761		{ // Try to extend in-place
762		auto u = gc_extend(px.data, (newsize + 1) - info.size, (newsize + 1) - info.size);
763		if (u)
764		{
765		goto L1;
766		}
767		}
768		newdata = cast(byte *)gc_malloc(newCapacity(newlength, sizeelem) + 1, info.attr);
	1156	auto size = length * sizeelem;
	1157
	1158	// calculate the extent of the array given the base.
	1159	size_t offset = px.data - __arrayStart(info);
	1160	if(info.size >= PAGESIZE)
	1161	{
	1162	// size of array is at the front of the block
	1163	if(!__setArrayAllocLength(info, newsize + offset, isshared, size + offset))
	1164	{
	1165	// check to see if it failed because there is not
	1166	// enough space
	1167	if((cast(size_t)info.base) == size + offset)
	1168	{
	1169	// not enough space, try extending
	1170	auto extendsize = newsize + offset + LARGEPAD - info.size;
	1171	auto u = gc_extend(px.data, extendsize, extendsize);
	1172	if(u)
	1173	{
	1174	// extend worked, now try setting the length
	1175	// again.
	1176	info.size = u;
	1177	if(__setArrayAllocLength(info, newsize + offset, isshared, size + offset))
	1178	{
	1179	if(!isshared)
	1180	__insertBlkInfoCache(info, bic);
	1181	goto L1;
	1182	}
	1183	}
	1184	}
	1185
	1186	// couldn't do it, reallocate
	1187	info = gc_malloc_bi(newCapacity(newlength, sizeelem) + LARGEPAD, info.attr);
	1188	__setArrayAllocLength(info, newsize, isshared);
	1189	if(!isshared)
	1190	__insertBlkInfoCache(info, bic);
	1191	auto newdata = cast(byte )info.base + size_t.sizeof 2;
	1192	memcpy(newdata, px.data, length * sizeelem);
	1193	px.data = newdata;
	1194	}
	1195	}
	1196	else if(!__setArrayAllocLength(info, newsize + offset, isshared, size + offset))
	1197	{
	1198	// could not resize in place
	1199	auto allocsize = newCapacity(newlength, sizeelem);
	1200	info = gc_malloc_bi(allocsize + __arrayPad(allocsize), info.attr);
	1201	__setArrayAllocLength(info, newsize, isshared);
	1202	if(!isshared)
	1203	__insertBlkInfoCache(info, bic);
	1204	auto newdata = cast(byte *)__arrayStart(info);
769	1205	memcpy(newdata, px.data, length * sizeelem);
770	1206	px.data = newdata;
771	1207	}
	1208	else if(!isshared && !bic)
	1209	{
	1210	__insertBlkInfoCache(info, null);
	1211	}
	1212
	1213
772	1214	L1:
773	1215	px.length = newlength;
774	1216	memcpy(px.data + length * sizeelem, y.ptr, y.length * sizeelem);
775	1217	return cast(long)px;
776	1218	}
777	1219
778	1220
779	1221	/**
780	1222	*
781	1223	*/
…	…
844	1286	newcap = newext > newcap ? newext : newcap;
845	1287	debug(PRINTF) printf("newcap = %d, newlength = %d, size = %d\n", newcap, newlength, size);
846	1288	}
847	1289	return newcap;
848	1290	}
849	1291
850	1292
851	1293	/**
852	1294	*
853	1295	*/
854		extern (C) byte[] _d_arrayappendcT(TypeInfo ti, ref byte[] x, ...)
855		{
856		auto sizeelem = ti.next.tsize(); // array element size
857		auto info = gc_query(x.ptr);
858		auto length = x.length;
859		auto newlength = length + 1;
860		auto newsize = newlength * sizeelem;
861
862		assert(info.size == 0 \|\| length * sizeelem <= info.size);
863
864		debug(PRINTF) printf("_d_arrayappendcT(sizeelem = %d, ptr = %p, length = %d, cap = %d)\n", sizeelem, x.ptr, x.length, info.size);
865
866		if (info.size <= newsize \|\| info.base != x.ptr)
867		{ byte* newdata;
868
869		if (info.size >= PAGESIZE && info.base == x.ptr)
870		{ // Try to extend in-place
871		auto u = gc_extend(x.ptr, (newsize + 1) - info.size, (newsize + 1) - info.size);
872		if (u)
873		{
874		goto L1;
875		}
876		}
877		debug(PRINTF) printf("_d_arrayappendcT(length = %d, newlength = %d, cap = %d)\n", length, newlength, info.size);
878		auto newcap = newCapacity(newlength, sizeelem);
879		assert(newcap >= newlength * sizeelem);
880		newdata = cast(byte *)gc_malloc(newcap + 1, info.attr);
881		memcpy(newdata, x.ptr, length * sizeelem);
882		(cast(void**)(&x))[1] = newdata;
883		}
884		L1:
885		byte argp = cast(byte )(&ti + 2);
886
887		cast(size_t )&x = newlength;
888		x.ptr[length * sizeelem .. newsize] = argp[0 .. sizeelem];
889		assert((cast(size_t)x.ptr & 15) == 0);
890		assert(gc_sizeOf(x.ptr) > x.length * sizeelem);
891		return x;
	1296	version(none)
	1297	{
	1298	// no clue why this was special cased...
	1299	extern (C) byte[] _d_arrayappendcT(TypeInfo ti, ref byte[] x, ...)
	1300	{
	1301	auto sizeelem = ti.next.tsize(); // array element size
	1302	auto info = gc_query(x.ptr);
	1303	auto length = x.length;
	1304	auto newlength = length + 1;
	1305	auto newsize = newlength * sizeelem;
	1306
	1307	assert(info.size == 0 \|\| length * sizeelem <= info.size);
	1308
	1309	debug(PRINTF) printf("_d_arrayappendcT(sizeelem = %d, ptr = %p, length = %d, cap = %d)\n", sizeelem, x.ptr, x.length, info.size);
	1310
	1311	if (info.size <= newsize \|\| info.base != x.ptr)
	1312	{ byte* newdata;
	1313
	1314	if (info.size >= PAGESIZE && info.base == x.ptr)
	1315	{ // Try to extend in-place
	1316	auto u = gc_extend(x.ptr, (newsize + 1) - info.size, (newsize + 1) - info.size);
	1317	if (u)
	1318	{
	1319	goto L1;
	1320	}
	1321	}
	1322	debug(PRINTF) printf("_d_arrayappendcT(length = %d, newlength = %d, cap = %d)\n", length, newlength, info.size);
	1323	auto newcap = newCapacity(newlength, sizeelem);
	1324	assert(newcap >= newlength * sizeelem);
	1325	newdata = cast(byte *)gc_malloc(newcap + 1, info.attr);
	1326	memcpy(newdata, x.ptr, length * sizeelem);
	1327	(cast(void**)(&x))[1] = newdata;
	1328	}
	1329	L1:
	1330	byte argp = cast(byte )(&ti + 2);
	1331
	1332	cast(size_t )&x = newlength;
	1333	x.ptr[length * sizeelem .. newsize] = argp[0 .. sizeelem];
	1334	assert((cast(size_t)x.ptr & 15) == 0);
	1335	assert(gc_sizeOf(x.ptr) > x.length * sizeelem);
	1336	return x;
	1337	}
	1338	}
	1339	else
	1340	{
	1341	extern (C) long _d_arrayappendcT(TypeInfo ti, Array *x, ...)
	1342	{
	1343	byte argp = cast(byte)(&ti + 2);
	1344	return _d_arrayappendT(ti, x, argp[0..1]);
	1345	}
892	1346	}
893	1347
894	1348
895	1349	/**
896	1350	* Append dchar to char[]
897	1351	*/
898		extern (C) char[] _d_arrayappendcd(ref char[] x, dchar c)
899		{
900		const sizeelem = c.sizeof; // array element size
901		auto info = gc_query(x.ptr);
902		auto length = x.length;
903
	1352	extern (C) long _d_arrayappendcd(ref char[] x, dchar c)
	1353	{
904	1354	// c could encode into from 1 to 4 characters
905		int nchars;
	1355	char[4] buf = void;
	1356	byte[] appendthis; // passed to appendT
906	1357	if (c <= 0x7F)
907		nchars = 1;
	1358	{
	1359	buf.ptr[0] = cast(char)c;
	1360	appendthis = (cast(byte *)buf.ptr)[0..1];
	1361	}
908	1362	else if (c <= 0x7FF)
909		nchars = 2;
	1363	{
	1364	buf.ptr[0] = cast(char)(0xC0 \| (c >> 6));
	1365	buf.ptr[1] = cast(char)(0x80 \| (c & 0x3F));
	1366	appendthis = (cast(byte *)buf.ptr)[0..2];
	1367	}
910	1368	else if (c <= 0xFFFF)
911		nchars = 3;
	1369	{
	1370	buf.ptr[0] = cast(char)(0xE0 \| (c >> 12));
	1371	buf.ptr[1] = cast(char)(0x80 \| ((c >> 6) & 0x3F));
	1372	buf.ptr[2] = cast(char)(0x80 \| (c & 0x3F));
	1373	appendthis = (cast(byte *)buf.ptr)[0..3];
	1374	}
912	1375	else if (c <= 0x10FFFF)
913		nchars = 4;
	1376	{
	1377	buf.ptr[0] = cast(char)(0xF0 \| (c >> 18));
	1378	buf.ptr[1] = cast(char)(0x80 \| ((c >> 12) & 0x3F));
	1379	buf.ptr[2] = cast(char)(0x80 \| ((c >> 6) & 0x3F));
	1380	buf.ptr[3] = cast(char)(0x80 \| (c & 0x3F));
	1381	appendthis = (cast(byte *)buf.ptr)[0..4];
	1382	}
914	1383	else
915	1384	assert(0); // invalid utf character - should we throw an exception instead?
916	1385
917		auto newlength = length + nchars;
918		auto newsize = newlength * sizeelem;
919
920		assert(info.size == 0 \|\| length * sizeelem <= info.size);
921
922		debug(PRINTF) printf("_d_arrayappendcd(sizeelem = %d, ptr = %p, length = %d, cap = %d)\n", sizeelem, x.ptr, x.length, info.size);
923
924		if (info.size <= newsize \|\| info.base != x.ptr)
925		{ byte* newdata;
926
927		if (info.size >= PAGESIZE && info.base == x.ptr)
928		{ // Try to extend in-place
929		auto u = gc_extend(x.ptr, (newsize + 1) - info.size, (newsize + 1) - info.size);
930		if (u)
931		{
932		goto L1;
933		}
934		}
935		debug(PRINTF) printf("_d_arrayappendcd(length = %d, newlength = %d, cap = %d)\n", length, newlength, info.size);
936		auto newcap = newCapacity(newlength, sizeelem);
937		assert(newcap >= newlength * sizeelem);
938		newdata = cast(byte *)gc_malloc(newcap + 1, info.attr);
939		memcpy(newdata, x.ptr, length * sizeelem);
940		(cast(void**)(&x))[1] = newdata;
941		}
942		L1:
943		cast(size_t )&x = newlength;
944		char* ptr = &x.ptr[length];
945
946		if (c <= 0x7F)
947		{
948		ptr[0] = cast(char) c;
949		}
950		else if (c <= 0x7FF)
951		{
952		ptr[0] = cast(char)(0xC0 \| (c >> 6));
953		ptr[1] = cast(char)(0x80 \| (c & 0x3F));
954		}
955		else if (c <= 0xFFFF)
956		{
957		ptr[0] = cast(char)(0xE0 \| (c >> 12));
958		ptr[1] = cast(char)(0x80 \| ((c >> 6) & 0x3F));
959		ptr[2] = cast(char)(0x80 \| (c & 0x3F));
960		}
961		else if (c <= 0x10FFFF)
962		{
963		ptr[0] = cast(char)(0xF0 \| (c >> 18));
964		ptr[1] = cast(char)(0x80 \| ((c >> 12) & 0x3F));
965		ptr[2] = cast(char)(0x80 \| ((c >> 6) & 0x3F));
966		ptr[3] = cast(char)(0x80 \| (c & 0x3F));
	1386	//
	1387	// TODO: This always assumes the array type is shared, because we do not
	1388	// get a typeinfo from the compiler. Assuming shared is the safest option.
	1389	// Once the compiler is fixed, the proper typeinfo should be forwarded.
	1390	//
	1391	return _d_arrayappendT(typeid(shared char[]), cast(Array *)&x, appendthis);
	1392	}
	1393
	1394
	1395	/**
	1396	* Append dchar to wchar[]
	1397	*/
	1398	extern (C) long _d_arrayappendwd(ref wchar[] x, dchar c)
	1399	{
	1400	// c could encode into from 1 to 2 w characters
	1401	wchar[2] buf = void;
	1402	byte[] appendthis; // passed to appendT
	1403	if (c <= 0xFFFF)
	1404	{
	1405	buf.ptr[0] = cast(wchar) c;
	1406	// note that although we are passing only 1 byte here, appendT
	1407	// interprets this as being an array of wchar, making the necessary
	1408	// casts.
	1409	appendthis = (cast(byte *)buf.ptr)[0..1];
967	1410	}
968	1411	else
969		assert(0);
970
971		assert((cast(size_t)x.ptr & 15) == 0);
972		assert(gc_sizeOf(x.ptr) > x.length * sizeelem);
973		return x;
974		}
975
976
977		/**
978		* Append dchar to wchar[]
979		*/
980		extern (C) wchar[] _d_arrayappendwd(ref wchar[] x, dchar c)
981		{
982		const sizeelem = c.sizeof; // array element size
983		auto info = gc_query(x.ptr);
984		auto length = x.length;
985
986		// c could encode into from 1 to 2 w characters
987		int nchars;
988		if (c <= 0xFFFF)
989		nchars = 1;
990		else
991		nchars = 2;
992
993		auto newlength = length + nchars;
994		auto newsize = newlength * sizeelem;
995
996		assert(info.size == 0 \|\| length * sizeelem <= info.size);
997
998		debug(PRINTF) printf("_d_arrayappendwd(sizeelem = %d, ptr = %p, length = %d, cap = %d)\n", sizeelem, x.ptr, x.length, info.size);
999
1000		if (info.size <= newsize \|\| info.base != x.ptr)
1001		{ byte* newdata;
1002
1003		if (info.size >= PAGESIZE && info.base == x.ptr)
1004		{ // Try to extend in-place
1005		auto u = gc_extend(x.ptr, (newsize + 1) - info.size, (newsize + 1) - info.size);
1006		if (u)
1007		{
1008		goto L1;
1009		}
1010		}
1011		debug(PRINTF) printf("_d_arrayappendwd(length = %d, newlength = %d, cap = %d)\n", length, newlength, info.size);
1012		auto newcap = newCapacity(newlength, sizeelem);
1013		assert(newcap >= newlength * sizeelem);
1014		newdata = cast(byte *)gc_malloc(newcap + 1, info.attr);
1015		memcpy(newdata, x.ptr, length * sizeelem);
1016		(cast(void**)(&x))[1] = newdata;
1017		}
1018		L1:
1019		cast(size_t )&x = newlength;
1020		wchar* ptr = &x.ptr[length];
1021
1022		if (c <= 0xFFFF)
1023		{
1024		ptr[0] = cast(wchar) c;
1025		}
1026		else
1027		{
1028		ptr[0] = cast(wchar) ((((c - 0x10000) >> 10) & 0x3FF) + 0xD800);
1029		ptr[1] = cast(wchar) (((c - 0x10000) & 0x3FF) + 0xDC00);
1030		}
1031
1032		assert((cast(size_t)x.ptr & 15) == 0);
1033		assert(gc_sizeOf(x.ptr) > x.length * sizeelem);
1034		return x;
	1412	{
	1413	buf.ptr[0] = cast(wchar) ((((c - 0x10000) >> 10) & 0x3FF) + 0xD800);
	1414	buf.ptr[1] = cast(wchar) (((c - 0x10000) & 0x3FF) + 0xDC00);
	1415	// ditto from above.
	1416	appendthis = (cast(byte *)buf.ptr)[0..2];
	1417	}
	1418
	1419	//
	1420	// TODO: This always assumes the array type is shared, because we do not
	1421	// get a typeinfo from the compiler. Assuming shared is the safest option.
	1422	// Once the compiler is fixed, the proper typeinfo should be forwarded.
	1423	//
	1424	return _d_arrayappendT(typeid(shared wchar[]), cast(Array *)&x, appendthis);
1035	1425	}
1036	1426
1037	1427
1038	1428	/**
1039	1429	*
1040	1430	*/
1041	1431	extern (C) byte[] _d_arraycatT(TypeInfo ti, byte[] x, byte[] y)
1042	1432	out (result)
1043	1433	{
1044	1434	auto sizeelem = ti.next.tsize(); // array element size
…	…
1072	1462	debug(PRINTF) printf("_d_arraycatT(%d,%p ~ %d,%p)\n", x.length, x.ptr, y.length, y.ptr);
1073	1463	auto sizeelem = ti.next.tsize(); // array element size
1074	1464	debug(PRINTF) printf("_d_arraycatT(%d,%p ~ %d,%p sizeelem = %d)\n", x.length, x.ptr, y.length, y.ptr, sizeelem);
1075	1465	size_t xlen = x.length * sizeelem;
1076	1466	size_t ylen = y.length * sizeelem;
1077	1467	size_t len = xlen + ylen;
1078	1468
1079	1469	if (!len)
1080	1470	return null;
1081	1471
1082		byte* p = cast(byte*)gc_malloc(len + 1, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
	1472	auto info = gc_malloc_bi(len + __arrayPad(len), !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
	1473	byte* p = cast(byte*)__arrayStart(info);
	1474	p[len] = 0; // guessing this is to optimize for null-terminated arrays?
1083	1475	memcpy(p, x.ptr, xlen);
1084	1476	memcpy(p + xlen, y.ptr, ylen);
1085		p[len] = 0;
	1477	auto isshared = ti.classinfo is TypeInfo_Shared.classinfo;
	1478	__setArrayAllocLength(info, len, isshared);
1086	1479	return p[0 .. x.length + y.length];
1087	1480	}
1088	1481
1089	1482
1090	1483	/**
1091	1484	*
1092	1485	*/
1093	1486	extern (C) byte[] _d_arraycatnT(TypeInfo ti, uint n, ...)
1094	1487	{ void* a;
1095	1488	size_t length;
…	…
1101	1494	p = cast(byte[]*)(&n + 1);
1102	1495
1103	1496	for (i = 0; i < n; i++)
1104	1497	{
1105	1498	b = *p++;
1106	1499	length += b.length;
1107	1500	}
1108	1501	if (!length)
1109	1502	return null;
1110	1503
1111		a = gc_malloc(length * size, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
	1504	auto allocsize = length * size;
	1505	auto info = gc_malloc_bi(allocsize + __arrayPad(allocsize), !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
	1506	auto isshared = ti.classinfo is TypeInfo_Shared.classinfo;
	1507	__setArrayAllocLength(info, allocsize, isshared);
	1508	a = __arrayStart(info);
1112	1509	p = cast(byte[]*)(&n + 1);
1113	1510
1114	1511	uint j = 0;
1115	1512	for (i = 0; i < n; i++)
1116	1513	{
1117	1514	b = *p++;
1118	1515	if (b.length)
1119	1516	{
1120	1517	memcpy(a + j, b.ptr, b.length * size);
1121	1518	j += b.length * size;
…	…
1135	1532	extern (C) void* _d_arrayliteralT(TypeInfo ti, size_t length, ...)
1136	1533	{
1137	1534	auto sizeelem = ti.next.tsize(); // array element size
1138	1535	void* result;
1139	1536
1140	1537	debug(PRINTF) printf("_d_arrayliteralT(sizeelem = %d, length = %d)\n", sizeelem, length);
1141	1538	if (length == 0 \|\| sizeelem == 0)
1142	1539	result = null;
1143	1540	else
1144	1541	{
1145		result = gc_malloc(length * sizeelem, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
	1542	auto allocsize = length * sizeelem;
	1543	auto info = gc_malloc_bi(allocsize + __arrayPad(allocsize), !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
	1544	auto isshared = ti.classinfo is TypeInfo_Shared.classinfo;
	1545	__setArrayAllocLength(info, allocsize, isshared);
	1546	result = __arrayStart(info);
1146	1547
1147	1548	va_list q;
1148	1549	va_start!(size_t)(q, length);
1149	1550
1150	1551	size_t stacksize = (sizeelem + int.sizeof - 1) & ~(int.sizeof - 1);
1151	1552
1152	1553	if (stacksize == sizeelem)
1153	1554	{
1154	1555	memcpy(result, q, length * sizeelem);
1155	1556	}
…	…
1188	1589	assert(memcmp((cast(Array2)&result).ptr, a.ptr, a.length * sizeelem) == 0);
1189	1590	}
1190	1591	body
1191	1592	{
1192	1593	Array2 r;
1193	1594
1194	1595	if (a.length)
1195	1596	{
1196	1597	auto sizeelem = ti.next.tsize(); // array element size
1197	1598	auto size = a.length * sizeelem;
1198		r.ptr = gc_malloc(size, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
	1599	auto info = gc_malloc_bi(size + __arrayPad(size), !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
	1600	auto isshared = ti.classinfo is TypeInfo_Shared.classinfo;
	1601	__setArrayAllocLength(info, size, isshared);
	1602	r.ptr = __arrayStart(info);
1199	1603	r.length = a.length;
1200	1604	memcpy(r.ptr, a.ptr, size);
1201	1605	}
1202	1606	return cast(long)(&r);
1203	1607	}
1204	1608
1205	1609
1206	1610	unittest
1207	1611	{
1208	1612	int[] a;

druntime

Navigation

Changeset 252

Legend:

trunk/src/gc/gc.d

trunk/src/gc/gcx.d

trunk/src/rt/lifetime.d

Download in other formats: