2 * This module contains all functions related to an object's lifetime:
3 * allocation, resizing, deallocation, and finalization.
5 * Copyright: Copyright Digital Mars 2000 - 2012.
6 * License: Distributed under the
7 * $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0).
8 * (See accompanying file LICENSE)
9 * Authors: Walter Bright, Sean Kelly, Steven Schveighoffer
10 * Source: $(DRUNTIMESRC rt/_lifetime.d)
15 import core
.attribute
: weak
;
16 import core
.internal
.array
.utils
: __arrayStart
, __arrayClearPad
;
18 debug(PRINTF
) import core
.stdc
.stdio
;
19 static import rt
.tlsgc
;
21 alias BlkInfo
= GC
.BlkInfo
;
22 alias BlkAttr
= GC
.BlkAttr
;
26 alias bool function(Object
) CollectHandler
;
27 __gshared CollectHandler collectHandler
= null;
29 extern (C
) void _d_monitordelete(Object h
, bool det
);
34 BIGLENGTHMASK
= ~(PAGESIZE
- 1),
36 MEDPAD
= ushort.sizeof
,
37 LARGEPREFIX
= 16, // 16 bytes padding at the front of the array
38 LARGEPAD
= LARGEPREFIX
+ 1,
39 MAXSMALLSIZE
= 256-SMALLPAD
,
40 MAXMEDSIZE
= (PAGESIZE
/ 2) - MEDPAD
44 // Now-removed symbol, kept around for ABI
45 // Some programs are dynamically linked, so best to err on the side of keeping symbols around for a while (especially extern(C) ones)
46 // https://github.com/dlang/druntime/pull/3361
47 deprecated extern (C
) void lifetime_init()
52 Allocate memory using the garbage collector
54 DMD uses this to allocate closures:
58 return () => x; // `x` is on stack, must be moved to heap to keep it alive
63 sz = number of bytes to allocate
65 Returns: pointer to `sz` bytes of free, uninitialized memory, managed by the GC.
67 extern (C
) void* _d_allocmemory(size_t sz
) @weak
73 Create a new class instance.
75 Allocates memory and sets fields to their initial value, but does not call a constructor.
78 new Object() // _d_newclass(typeid(Object))
81 ci = `TypeInfo_Class` object, to provide instance size and initial bytes to copy
83 Returns: newly created object
85 extern (C
) Object
_d_newclass(const ClassInfo ci
) @weak
87 import core
.stdc
.stdlib
;
88 import core
.exception
: onOutOfMemoryError
;
90 auto init
= ci
.initializer
;
92 debug(PRINTF
) printf("_d_newclass(ci = %p, %s)\n", ci
, cast(char *)ci
.name
);
93 if (ci
.m_flags
& TypeInfo_Class
.ClassFlags
.isCOMclass
)
94 { /* COM objects are not garbage collected, they are reference counted
95 * using AddRef() and Release(). They get free'd by C's free()
96 * function called by Release() when Release()'s reference count goes
99 p
= malloc(init
.length
);
101 onOutOfMemoryError();
105 // TODO: should this be + 1 to avoid having pointers to the next block?
106 BlkAttr attr
= BlkAttr
.NONE
;
107 // extern(C++) classes don't have a classinfo pointer in their vtable so the GC can't finalize them
108 if (ci
.m_flags
& TypeInfo_Class
.ClassFlags
.hasDtor
109 && !(ci
.m_flags
& TypeInfo_Class
.ClassFlags
.isCPPclass
))
110 attr |
= BlkAttr
.FINALIZE
;
111 if (ci
.m_flags
& TypeInfo_Class
.ClassFlags
.noPointers
)
112 attr |
= BlkAttr
.NO_SCAN
;
113 p
= GC
.malloc(init
.length
, attr
, ci
);
114 debug(PRINTF
) printf(" p = %p\n", p
);
119 printf("p = %p\n", p
);
120 printf("ci = %p, ci.init.ptr = %p, len = %llu\n", ci
, init
.ptr
, cast(ulong)init
.length
);
121 printf("vptr = %p\n", *cast(void**) init
);
122 printf("vtbl[0] = %p\n", (*cast(void***) init
)[0]);
123 printf("vtbl[1] = %p\n", (*cast(void***) init
)[1]);
124 printf("init[0] = %x\n", (cast(uint*) init
)[0]);
125 printf("init[1] = %x\n", (cast(uint*) init
)[1]);
126 printf("init[2] = %x\n", (cast(uint*) init
)[2]);
127 printf("init[3] = %x\n", (cast(uint*) init
)[3]);
128 printf("init[4] = %x\n", (cast(uint*) init
)[4]);
132 p
[0 .. init
.length
] = init
[];
134 debug(PRINTF
) printf("initialization done\n");
135 return cast(Object
) p
;
142 extern (C
) void _d_delinterface(void** p
)
146 Interface
* pi
= **cast(Interface
***)*p
;
147 Object o
= cast(Object
)(*p
- pi
.offset
);
156 private extern (D
) alias void function (Object
) fp_t
;
162 extern (C
) void _d_delclass(Object
* p
) @weak
166 debug(PRINTF
) printf("_d_delclass(%p)\n", *p
);
168 ClassInfo
**pc
= cast(ClassInfo
**)*p
;
173 rt_finalize(cast(void*) *p
);
177 fp_t fp
= cast(fp_t
)c
.deallocator
;
178 (*fp
)(*p
); // call deallocator
185 rt_finalize(cast(void*) *p
);
187 GC
.free(cast(void*) *p
);
192 // strip const/immutable/shared/inout from type info
193 inout(TypeInfo
) unqualify(return scope inout(TypeInfo
) cti
) pure nothrow @nogc
195 TypeInfo ti
= cast() cti
;
198 // avoid dynamic type casts
199 auto tti
= typeid(ti
);
200 if (tti
is typeid(TypeInfo_Const
))
201 ti
= (cast(TypeInfo_Const
)cast(void*)ti
).base
;
202 else if (tti
is typeid(TypeInfo_Invariant
))
203 ti
= (cast(TypeInfo_Invariant
)cast(void*)ti
).base
;
204 else if (tti
is typeid(TypeInfo_Shared
))
205 ti
= (cast(TypeInfo_Shared
)cast(void*)ti
).base
;
206 else if (tti
is typeid(TypeInfo_Inout
))
207 ti
= (cast(TypeInfo_Inout
)cast(void*)ti
).base
;
214 // size used to store the TypeInfo at the end of an allocation for structs that have a destructor
215 size_t
structTypeInfoSize(const TypeInfo ti
) pure nothrow @nogc
217 if (ti
&& typeid(ti
) is typeid(TypeInfo_Struct
)) // avoid a complete dynamic type cast
219 auto sti = cast(TypeInfo_Struct
)cast(void*)ti
;
221 return size_t
.sizeof
;
226 /** dummy class used to lock for shared array appending */
227 private class ArrayAllocLengthLock
231 Set the allocated length of the array block. This is called
232 any time an array is appended to or its length is set.
234 The allocated block looks like this for blocks < PAGESIZE:
236 |elem0|elem1|elem2|...|elemN-1|emptyspace|N*elemsize|
239 The size of the allocated length at the end depends on the block size:
241 a block of 16 to 256 bytes has an 8-bit length.
243 a block with 512 to pagesize/2 bytes has a 16-bit length.
245 For blocks >= pagesize, the length is a size_t and is at the beginning of the
246 block. The reason we have to do this is because the block can extend into
247 more pages, so we cannot trust the block length if it sits at the end of the
248 block, because it might have just been extended. If we can prove in the
249 future that the block is unshared, we may be able to change this, but I'm not
252 In order to do put the length at the front, we have to provide 16 bytes
253 buffer space in case the block has to be aligned properly. In x86, certain
254 SSE instructions will only work if the data is 16-byte aligned. In addition,
255 we need the sentinel byte to prevent accidental pointers to the next block.
256 Because of the extra overhead, we only do this for page size and above, where
257 the overhead is minimal compared to the block size.
259 So for those blocks, it looks like:
261 |N*elemsize|padding|elem0|elem1|...|elemN-1|emptyspace|sentinelbyte|
263 where elem0 starts 16 bytes after the first byte.
265 bool __setArrayAllocLength(ref BlkInfo info
, size_t newlength
, bool isshared
, const TypeInfo tinext
, size_t oldlength
= ~0) pure nothrow
269 size_t typeInfoSize
= structTypeInfoSize(tinext
);
271 if (info
.size
<= 256)
273 import core
.checkedint
;
276 auto newlength_padded
= addu(newlength
,
277 addu(SMALLPAD
, typeInfoSize
, overflow
),
280 if (newlength_padded
> info
.size || overflow
)
281 // new size does not fit inside block
284 auto length
= cast(ubyte *)(info
.base
+ info
.size
- typeInfoSize
- SMALLPAD
);
289 return cas(cast(shared)length
, cast(ubyte)oldlength
, cast(ubyte)newlength
);
293 if (*length
== cast(ubyte)oldlength
)
294 *length
= cast(ubyte)newlength
;
301 // setting the initial length, no cas needed
302 *length
= cast(ubyte)newlength
;
306 auto typeInfo
= cast(TypeInfo
*)(info
.base
+ info
.size
- size_t
.sizeof
);
307 *typeInfo
= cast() tinext
;
310 else if (info
.size
< PAGESIZE
)
312 if (newlength
+ MEDPAD
+ typeInfoSize
> info
.size
)
313 // new size does not fit inside block
315 auto length
= cast(ushort *)(info
.base
+ info
.size
- typeInfoSize
- MEDPAD
);
320 return cas(cast(shared)length
, cast(ushort)oldlength
, cast(ushort)newlength
);
324 if (*length
== oldlength
)
325 *length
= cast(ushort)newlength
;
332 // setting the initial length, no cas needed
333 *length
= cast(ushort)newlength
;
337 auto typeInfo
= cast(TypeInfo
*)(info
.base
+ info
.size
- size_t
.sizeof
);
338 *typeInfo
= cast() tinext
;
343 if (newlength
+ LARGEPAD
> info
.size
)
344 // new size does not fit inside block
346 auto length
= cast(size_t
*)(info
.base
);
351 return cas(cast(shared)length
, cast(size_t
)oldlength
, cast(size_t
)newlength
);
355 if (*length
== oldlength
)
363 // setting the initial length, no cas needed
368 auto typeInfo
= cast(TypeInfo
*)(info
.base
+ size_t
.sizeof
);
369 *typeInfo
= cast()tinext
;
372 return true; // resize succeeded
376 get the allocation size of the array for the given block (without padding or type info)
378 private size_t
__arrayAllocLength(ref BlkInfo info
, const TypeInfo tinext
) pure nothrow
380 if (info
.size
<= 256)
381 return *cast(ubyte *)(info
.base
+ info
.size
- structTypeInfoSize(tinext
) - SMALLPAD
);
383 if (info
.size
< PAGESIZE
)
384 return *cast(ushort *)(info
.base
+ info
.size
- structTypeInfoSize(tinext
) - MEDPAD
);
386 return *cast(size_t
*)(info
.base
);
390 get the padding required to allocate size bytes. Note that the padding is
391 NOT included in the passed in size. Therefore, do NOT call this function
392 with the size of an allocated block.
394 private size_t
__arrayPad(size_t size
, const TypeInfo tinext
) nothrow pure @trusted
396 return size
> MAXMEDSIZE ? LARGEPAD
: ((size
> MAXSMALLSIZE ? MEDPAD
: SMALLPAD
) + structTypeInfoSize(tinext
));
400 allocate an array memory block by applying the proper padding and
401 assigning block attributes if not inherited from the existing block
403 private BlkInfo
__arrayAlloc(size_t arrsize
, const scope TypeInfo ti
, const TypeInfo tinext
) nothrow pure
405 import core
.checkedint
;
407 size_t typeInfoSize
= structTypeInfoSize(tinext
);
408 size_t padsize
= arrsize
> MAXMEDSIZE ? LARGEPAD
: ((arrsize
> MAXSMALLSIZE ? MEDPAD
: SMALLPAD
) + typeInfoSize
);
411 auto padded_size
= addu(arrsize
, padsize
, overflow
);
416 uint attr
= (!(tinext
.flags
& 1) ? BlkAttr
.NO_SCAN
: 0) | BlkAttr
.APPENDABLE
;
418 attr |
= BlkAttr
.STRUCTFINAL | BlkAttr
.FINALIZE
;
420 auto bi
= GC
.qalloc(padded_size
, attr
, tinext
);
421 __arrayClearPad(bi
, arrsize
, padsize
);
425 private BlkInfo
__arrayAlloc(size_t arrsize
, ref BlkInfo info
, const scope TypeInfo ti
, const TypeInfo tinext
)
427 import core
.checkedint
;
430 return __arrayAlloc(arrsize
, ti
, tinext
);
432 immutable padsize
= __arrayPad(arrsize
, tinext
);
434 auto padded_size
= addu(arrsize
, padsize
, overflow
);
440 auto bi
= GC
.qalloc(padded_size
, info
.attr
, tinext
);
441 __arrayClearPad(bi
, arrsize
, padsize
);
446 cache for the lookup of the block info
448 private enum N_CACHE_BLOCKS
=8;
450 // note this is TLS, so no need to sync.
451 BlkInfo
*__blkcache_storage
;
453 static if (N_CACHE_BLOCKS
==1)
455 version=single_cache
;
459 //version=simple_cache; // uncomment to test simple cache strategy
460 //version=random_cache; // uncomment to test random cache strategy
462 // ensure N_CACHE_BLOCKS is power of 2.
463 static assert(!((N_CACHE_BLOCKS
- 1) & N_CACHE_BLOCKS
));
465 version (random_cache
)
467 int __nextRndNum
= 0;
472 @property BlkInfo
*__blkcache() nothrow
474 if (!__blkcache_storage
)
476 import core
.stdc
.stdlib
;
477 import core
.stdc
.string
;
478 // allocate the block cache for the first time
479 immutable size
= BlkInfo
.sizeof
* N_CACHE_BLOCKS
;
480 __blkcache_storage
= cast(BlkInfo
*)malloc(size
);
481 memset(__blkcache_storage
, 0, size
);
483 return __blkcache_storage
;
486 // called when thread is exiting.
490 if (__blkcache_storage
)
492 import core
.stdc
.stdlib
;
493 free(__blkcache_storage
);
494 __blkcache_storage
= null;
499 // we expect this to be called with the lock in place
500 void processGCMarks(BlkInfo
* cache
, scope rt
.tlsgc
.IsMarkedDg isMarked
) nothrow
502 // called after the mark routine to eliminate block cache data when it
503 // might be ready to sweep
505 debug(PRINTF
) printf("processing GC Marks, %x\n", cache
);
508 debug(PRINTF
) foreach (i
; 0 .. N_CACHE_BLOCKS
)
510 printf("cache entry %d has base ptr %x\tsize %d\tflags %x\n", i
, cache
[i
].base
, cache
[i
].size
, cache
[i
].attr
);
512 auto cache_end
= cache
+ N_CACHE_BLOCKS
;
513 for (;cache
< cache_end
; ++cache
)
515 if (cache
.base
!= null && !isMarked(cache
.base
))
517 debug(PRINTF
) printf("clearing cache entry at %x\n", cache
.base
);
518 cache
.base
= null; // clear that data.
526 // Bugzilla 10701 - segfault in GC
527 ubyte[] result
; result
.length
= 4096;
533 Get the cached block info of an interior pointer. Returns null if the
534 interior pointer's block is not cached.
536 NOTE: The base ptr in this struct can be cleared asynchronously by the GC,
537 so any use of the returned BlkInfo should copy it and then check the
538 base ptr of the copy before actually using it.
540 TODO: Change this function so the caller doesn't have to be aware of this
541 issue. Either return by value and expect the caller to always check
542 the base ptr as an indication of whether the struct is valid, or set
543 the BlkInfo as a side-effect and return a bool to indicate success.
545 BlkInfo
*__getBlkInfo(void *interior
) nothrow
547 BlkInfo
*ptr
= __blkcache
;
548 version (single_cache
)
550 if (ptr
.base
&& ptr
.base
<= interior
&& (interior
- ptr
.base
) < ptr
.size
)
552 return null; // not in cache.
554 else version (simple_cache
)
556 foreach (i
; 0..N_CACHE_BLOCKS
)
558 if (ptr
.base
&& ptr
.base
<= interior
&& (interior
- ptr
.base
) < ptr
.size
)
565 // try to do a smart lookup, using __nextBlkIdx as the "head"
566 auto curi
= ptr
+ __nextBlkIdx
;
567 for (auto i
= curi
; i
>= ptr
; --i
)
569 if (i
.base
&& i
.base
<= interior
&& cast(size_t
)(interior
- i
.base
) < i
.size
)
573 for (auto i
= ptr
+ N_CACHE_BLOCKS
- 1; i
> curi
; --i
)
575 if (i
.base
&& i
.base
<= interior
&& cast(size_t
)(interior
- i
.base
) < i
.size
)
579 return null; // not in cache.
582 void __insertBlkInfoCache(BlkInfo bi
, BlkInfo
*curpos
) nothrow
584 version (single_cache
)
590 version (simple_cache
)
596 // note, this is a super-simple algorithm that does not care about
597 // most recently used. It simply uses a round-robin technique to
598 // cache block info. This means that the ordering of the cache
599 // doesn't mean anything. Certain patterns of allocation may
600 // render the cache near-useless.
601 __blkcache
[__nextBlkIdx
] = bi
;
602 __nextBlkIdx
= (__nextBlkIdx
+1) & (N_CACHE_BLOCKS
- 1);
605 else version (random_cache
)
607 // strategy: if the block currently is in the cache, move the
608 // current block index to the a random element and evict that
610 auto cache
= __blkcache
;
613 __nextBlkIdx
= (__nextRndNum
= 1664525 * __nextRndNum
+ 1013904223) & (N_CACHE_BLOCKS
- 1);
614 curpos
= cache
+ __nextBlkIdx
;
618 __nextBlkIdx
= curpos
- cache
;
625 // strategy: If the block currently is in the cache, swap it with
626 // the head element. Otherwise, move the head element up by one,
627 // and insert it there.
629 auto cache
= __blkcache
;
632 __nextBlkIdx
= (__nextBlkIdx
+1) & (N_CACHE_BLOCKS
- 1);
633 curpos
= cache
+ __nextBlkIdx
;
635 else if (curpos
!is cache
+ __nextBlkIdx
)
637 *curpos
= cache
[__nextBlkIdx
];
638 curpos
= cache
+ __nextBlkIdx
;
646 Shrink the "allocated" length of an array to be the exact size of the array.
648 It doesn't matter what the current allocated length of the array is, the
649 user is telling the runtime that he knows what he is doing.
652 ti = `TypeInfo` of array type
653 arr = array to shrink. Its `.length` is element length, not byte length, despite `void` type
655 extern(C
) void _d_arrayshrinkfit(const TypeInfo ti
, void[] arr
) nothrow
657 // note, we do not care about shared. We are setting the length no matter
658 // what, so no lock is required.
659 debug(PRINTF
) printf("_d_arrayshrinkfit, elemsize = %d, arr.ptr = x%x arr.length = %d\n", ti
.next
.tsize
, arr
.ptr
, arr
.length
);
660 auto tinext
= unqualify(ti
.next
);
661 auto size
= tinext
.tsize
; // array element size
662 auto cursize
= arr
.length
* size
;
663 auto isshared
= typeid(ti
) is typeid(TypeInfo_Shared
);
664 auto bic
= isshared ?
null : __getBlkInfo(arr
.ptr
);
665 auto info
= bic ?
*bic
: GC
.query(arr
.ptr
);
666 if (info
.base
&& (info
.attr
& BlkAttr
.APPENDABLE
))
668 auto newsize
= (arr
.ptr
- __arrayStart(info
)) + cursize
;
670 debug(PRINTF
) printf("setting allocated size to %d\n", (arr
.ptr
- info
.base
) + cursize
);
672 // destroy structs that become unused memory when array size is shrinked
673 if (typeid(tinext
) is typeid(TypeInfo_Struct
)) // avoid a complete dynamic type cast
675 auto sti = cast(TypeInfo_Struct
)cast(void*)tinext
;
678 auto oldsize
= __arrayAllocLength(info
, tinext
);
679 if (oldsize
> cursize
)
683 finalize_array(arr
.ptr
+ cursize
, oldsize
- cursize
, sti);
687 import core
.exception
: onFinalizeError
;
688 onFinalizeError(sti, e
);
693 // Note: Since we "assume" the append is safe, it means it is not shared.
694 // Since it is not shared, we also know it won't throw (no lock).
695 if (!__setArrayAllocLength(info
, newsize
, false, tinext
))
697 import core
.exception
: onInvalidMemoryOperationError
;
698 onInvalidMemoryOperationError();
701 // cache the block if not already done.
702 if (!isshared
&& !bic
)
703 __insertBlkInfoCache(info
, null);
707 package bool hasPostblit(in TypeInfo ti
) nothrow pure
709 return (&ti
.postblit
).funcptr
!is &TypeInfo
.postblit
;
712 void __doPostblit(void *ptr
, size_t len
, const TypeInfo ti
)
714 if (!hasPostblit(ti
))
717 if (auto tis
= cast(TypeInfo_Struct
)ti
)
719 // this is a struct, check the xpostblit member
720 auto pblit
= tis
.xpostblit
;
722 // postblit not specified, no point in looping.
725 // optimized for struct, call xpostblit directly for each element
726 immutable size
= ti
.tsize
;
727 const eptr
= ptr
+ len
;
728 for (;ptr
< eptr
;ptr
+= size
)
733 // generic case, call the typeinfo's postblit function
734 immutable size
= ti
.tsize
;
735 const eptr
= ptr
+ len
;
736 for (;ptr
< eptr
;ptr
+= size
)
743 Set the array capacity.
745 If the array capacity isn't currently large enough
746 to hold the requested capacity (in number of elements), then the array is
747 resized/reallocated to the appropriate size.
749 Pass in a requested capacity of 0 to get the current capacity.
752 ti = type info of element type
753 newcapacity = requested new capacity
754 p = pointer to array to set. Its `length` is left unchanged.
756 Returns: the number of elements that can actually be stored once the resizing is done
758 extern(C
) size_t
_d_arraysetcapacity(const TypeInfo ti
, size_t newcapacity
, void[]* p
) @weak
762 assert(!(*p
).length ||
(*p
).ptr
);
766 import core
.stdc
.string
;
767 import core
.exception
: onOutOfMemoryError
;
769 // step 1, get the block
770 auto isshared
= typeid(ti
) is typeid(TypeInfo_Shared
);
771 auto bic
= isshared ?
null : __getBlkInfo((*p
).ptr
);
772 auto info
= bic ?
*bic
: GC
.query((*p
).ptr
);
773 auto tinext
= unqualify(ti
.next
);
774 auto size
= tinext
.tsize
;
775 version (D_InlineAsm_X86
)
777 size_t reqsize
= void;
781 mov EAX
, newcapacity
;
787 else version (D_InlineAsm_X86_64
)
789 size_t reqsize
= void;
793 mov RAX
, newcapacity
;
801 import core
.checkedint
: mulu
;
803 bool overflow
= false;
804 size_t reqsize
= mulu(size
, newcapacity
, overflow
);
809 onOutOfMemoryError();
813 // step 2, get the actual "allocated" size. If the allocated size does not
814 // match what we expect, then we will need to reallocate anyways.
816 // TODO: this probably isn't correct for shared arrays
817 size_t curallocsize
= void;
818 size_t curcapacity
= void;
819 size_t offset
= void;
820 size_t arraypad
= void;
821 if (info
.base
&& (info
.attr
& BlkAttr
.APPENDABLE
))
823 if (info
.size
<= 256)
825 arraypad
= SMALLPAD
+ structTypeInfoSize(tinext
);
826 curallocsize
= *(cast(ubyte *)(info
.base
+ info
.size
- arraypad
));
828 else if (info
.size
< PAGESIZE
)
830 arraypad
= MEDPAD
+ structTypeInfoSize(tinext
);
831 curallocsize
= *(cast(ushort *)(info
.base
+ info
.size
- arraypad
));
835 curallocsize
= *(cast(size_t
*)(info
.base
));
840 offset
= (*p
).ptr
- __arrayStart(info
);
841 if (offset
+ (*p
).length
* size
!= curallocsize
)
847 // figure out the current capacity of the block from the point
848 // of view of the array.
849 curcapacity
= info
.size
- offset
- arraypad
;
854 curallocsize
= curcapacity
= offset
= 0;
856 debug(PRINTF
) printf("_d_arraysetcapacity, p = x%d,%d, newcapacity=%d, info.size=%d, reqsize=%d, curallocsize=%d, curcapacity=%d, offset=%d\n", (*p
).ptr
, (*p
).length
, newcapacity
, info
.size
, reqsize
, curallocsize
, curcapacity
, offset
);
858 if (curcapacity
>= reqsize
)
860 // no problems, the current allocated size is large enough.
861 return curcapacity
/ size
;
864 // step 3, try to extend the array in place.
865 if (info
.size
>= PAGESIZE
&& curcapacity
!= 0)
867 auto extendsize
= reqsize
+ offset
+ LARGEPAD
- info
.size
;
868 auto u
= GC
.extend(info
.base
, extendsize
, extendsize
);
871 // extend worked, save the new current allocated size
873 bic
.size
= u
; // update cache
874 curcapacity
= u
- offset
- LARGEPAD
;
875 return curcapacity
/ size
;
879 // step 4, if extending doesn't work, allocate a new array with at least the requested allocated size.
880 auto datasize
= (*p
).length
* size
;
881 // copy attributes from original block, or from the typeinfo if the
882 // original block doesn't exist.
883 info
= __arrayAlloc(reqsize
, info
, ti
, tinext
);
884 if (info
.base
is null)
886 // copy the data over.
887 // note that malloc will have initialized the data we did not request to 0.
888 auto tgt
= __arrayStart(info
);
889 memcpy(tgt
, (*p
).ptr
, datasize
);
892 __doPostblit(tgt
, datasize
, tinext
);
894 if (!(info
.attr
& BlkAttr
.NO_SCAN
))
896 // need to memset the newly requested data, except for the data that
897 // malloc returned that we didn't request.
898 void *endptr
= tgt
+ reqsize
;
899 void *begptr
= tgt
+ datasize
;
902 assert(endptr
>= begptr
);
903 memset(begptr
, 0, endptr
- begptr
);
906 // set up the correct length
907 __setArrayAllocLength(info
, datasize
, isshared
, tinext
);
909 __insertBlkInfoCache(info
, bic
);
911 *p
= (cast(void*)tgt
)[0 .. (*p
).length
];
913 // determine the padding. This has to be done manually because __arrayPad
914 // assumes you are not counting the pad size, and info.size does include
916 if (info
.size
<= 256)
917 arraypad
= SMALLPAD
+ structTypeInfoSize(tinext
);
918 else if (info
.size
< PAGESIZE
)
919 arraypad
= MEDPAD
+ structTypeInfoSize(tinext
);
923 curcapacity
= info
.size
- arraypad
;
924 return curcapacity
/ size
;
928 Allocate an array with the garbage collector.
931 - `_d_newarrayU` leave elements uninitialized
932 - `_d_newarrayT` initializes to 0 (e.g `new int[]`)
933 - `_d_newarrayiT` initializes based on initializer retrieved from TypeInfo (e.g `new float[]`)
936 ti = the type of the resulting array, (may also be the corresponding `array.ptr` type)
937 length = `.length` of resulting array
938 Returns: newly allocated array
940 extern (C
) void[] _d_newarrayU(const scope TypeInfo ti
, size_t length
) pure nothrow @weak
942 import core
.exception
: onOutOfMemoryError
;
944 auto tinext
= unqualify(ti
.next
);
945 auto size
= tinext
.tsize
;
947 debug(PRINTF
) printf("_d_newarrayU(length = x%x, size = %d)\n", length
, size
);
948 if (length
== 0 || size
== 0)
951 version (D_InlineAsm_X86
)
953 asm pure nothrow @nogc
961 else version (D_InlineAsm_X86_64
)
963 asm pure nothrow @nogc
973 import core
.checkedint
: mulu
;
975 bool overflow
= false;
976 size
= mulu(size
, length
, overflow
);
981 onOutOfMemoryError();
985 auto info
= __arrayAlloc(size
, ti
, tinext
);
988 debug(PRINTF
) printf(" p = %p\n", info
.base
);
989 // update the length of the array
990 auto arrstart
= __arrayStart(info
);
991 auto isshared
= typeid(ti
) is typeid(TypeInfo_Shared
);
992 __setArrayAllocLength(info
, size
, isshared
, tinext
);
993 return arrstart
[0..length
];
997 extern (C
) void[] _d_newarrayT(const TypeInfo ti
, size_t length
) pure nothrow @weak
999 import core
.stdc
.string
;
1001 void[] result
= _d_newarrayU(ti
, length
);
1002 auto tinext
= unqualify(ti
.next
);
1003 auto size
= tinext
.tsize
;
1005 memset(result
.ptr
, 0, size
* length
);
1010 extern (C
) void[] _d_newarrayiT(const TypeInfo ti
, size_t length
) pure nothrow @weak
1012 import core
.internal
.traits
: AliasSeq
;
1014 void[] result
= _d_newarrayU(ti
, length
);
1015 auto tinext
= unqualify(ti
.next
);
1016 auto size
= tinext
.tsize
;
1018 auto init
= tinext
.initializer();
1020 switch (init
.length
)
1022 foreach (T
; AliasSeq
!(ubyte, ushort, uint, ulong))
1025 if (tinext
.talign
% T
.alignof
== 0)
1027 (cast(T
*)result
.ptr
)[0 .. size
* length
/ T
.sizeof
] = *cast(T
*)init
.ptr
;
1035 import core
.stdc
.string
;
1036 immutable sz
= init
.length
;
1037 for (size_t u
= 0; u
< size
* length
; u
+= sz
)
1038 memcpy(result
.ptr
+ u
, init
.ptr
, sz
);
1045 Non-template version of $(REF _d_newitemT, core,lifetime) that does not perform
1046 initialization. Needed for $(REF allocEntry, rt,aaA).
1049 _ti = `TypeInfo` of item to allocate
1051 newly allocated item
1053 extern (C
) void* _d_newitemU(scope const TypeInfo _ti
) pure nothrow @weak
1055 auto ti
= unqualify(_ti
);
1056 auto flags
= !(ti
.flags
& 1) ? BlkAttr
.NO_SCAN
: 0;
1057 immutable tiSize
= structTypeInfoSize(ti
);
1058 immutable itemSize
= ti
.tsize
;
1059 immutable size
= itemSize
+ tiSize
;
1061 flags |
= BlkAttr
.STRUCTFINAL | BlkAttr
.FINALIZE
;
1063 auto blkInf
= GC
.qalloc(size
, flags
, ti
);
1064 auto p
= blkInf
.base
;
1068 // the GC might not have cleared the padding area in the block
1069 *cast(TypeInfo
*)(p
+ (itemSize
& ~(size_t
.sizeof
- 1))) = null;
1070 *cast(TypeInfo
*)(p
+ blkInf
.size
- tiSize
) = cast() ti
;
1078 extern(C
) void printArrayCache()
1080 auto ptr
= __blkcache
;
1081 printf("CACHE: \n");
1082 foreach (i
; 0 .. N_CACHE_BLOCKS
)
1084 printf(" %d\taddr:% .8x\tsize:% .10d\tflags:% .8x\n", i
, ptr
[i
].base
, ptr
[i
].size
, ptr
[i
].attr
);
1092 extern (C
) void _d_delmemory(void* *p
) @weak
1105 extern (C
) void _d_callinterfacefinalizer(void *p
) @weak
1109 Interface
*pi
= **cast(Interface
***)p
;
1110 Object o
= cast(Object
)(p
- pi
.offset
);
1111 rt_finalize(cast(void*)o
);
1119 extern (C
) void _d_callfinalizer(void* p
) @weak
1128 extern (C
) void rt_setCollectHandler(CollectHandler h
)
1137 extern (C
) CollectHandler
rt_getCollectHandler()
1139 return collectHandler
;
1146 extern (C
) int rt_hasFinalizerInSegment(void* p
, size_t size
, uint attr
, scope const(void)[] segment
) nothrow
1148 if (attr
& BlkAttr
.STRUCTFINAL
)
1150 if (attr
& BlkAttr
.APPENDABLE
)
1151 return hasArrayFinalizerInSegment(p
, size
, segment
);
1152 return hasStructFinalizerInSegment(p
, size
, segment
);
1156 auto ppv
= cast(void**) p
;
1160 auto c
= *cast(ClassInfo
*)*ppv
;
1163 auto pf
= c
.destructor
;
1164 if (cast(size_t
)(pf
- segment
.ptr
) < segment
.length
) return true;
1166 while ((c
= c
.base
) !is null);
1171 int hasStructFinalizerInSegment(void* p
, size_t size
, in void[] segment
) nothrow
1176 auto ti
= *cast(TypeInfo_Struct
*)(p
+ size
- size_t
.sizeof
);
1177 return cast(size_t
)(cast(void*)ti
.xdtor
- segment
.ptr
) < segment
.length
;
1180 int hasArrayFinalizerInSegment(void* p
, size_t size
, in void[] segment
) nothrow
1185 TypeInfo_Struct si
= void;
1186 if (size
< PAGESIZE
)
1187 si
= *cast(TypeInfo_Struct
*)(p
+ size
- size_t
.sizeof
);
1189 si
= *cast(TypeInfo_Struct
*)(p
+ size_t
.sizeof
);
1191 return cast(size_t
)(cast(void*)si
.xdtor
- segment
.ptr
) < segment
.length
;
1194 debug (VALGRIND
) import etc
.valgrind
.valgrind
;
1197 void finalize_array2(void* p
, size_t size
) nothrow
1199 debug(PRINTF
) printf("rt_finalize_array2(p = %p)\n", p
);
1201 TypeInfo_Struct si
= void;
1204 auto block
= p
[0..size
];
1205 disableAddrReportingInRange(block
);
1209 si
= *cast(TypeInfo_Struct
*)(p
+ size
- size_t
.sizeof
);
1210 size
= *cast(ubyte*)(p
+ size
- size_t
.sizeof
- SMALLPAD
);
1212 else if (size
< PAGESIZE
)
1214 si
= *cast(TypeInfo_Struct
*)(p
+ size
- size_t
.sizeof
);
1215 size
= *cast(ushort*)(p
+ size
- size_t
.sizeof
- MEDPAD
);
1219 si
= *cast(TypeInfo_Struct
*)(p
+ size_t
.sizeof
);
1220 size
= *cast(size_t
*)p
;
1223 debug (VALGRIND
) enableAddrReportingInRange(block
);
1227 finalize_array(p
, size
, si
);
1231 import core
.exception
: onFinalizeError
;
1232 onFinalizeError(si
, e
);
1236 void finalize_array(void* p
, size_t size
, const TypeInfo_Struct si
)
1238 // Due to the fact that the delete operator calls destructors
1239 // for arrays from the last element to the first, we maintain
1240 // compatibility here by doing the same.
1241 auto tsize
= si
.tsize
;
1242 for (auto curP
= p
+ size
- tsize
; curP
>= p
; curP
-= tsize
)
1250 void finalize_struct(void* p
, size_t size
) nothrow
1252 debug(PRINTF
) printf("finalize_struct(p = %p)\n", p
);
1254 auto ti
= *cast(TypeInfo_Struct
*)(p
+ size
- size_t
.sizeof
);
1257 ti
.destroy(p
); // call destructor
1261 import core
.exception
: onFinalizeError
;
1262 onFinalizeError(ti
, e
);
1269 extern (C
) void rt_finalize2(void* p
, bool det
= true, bool resetMemory
= true) nothrow
1271 debug(PRINTF
) printf("rt_finalize2(p = %p)\n", p
);
1273 auto ppv
= cast(void**) p
;
1277 auto pc
= cast(ClassInfo
*) *ppv
;
1280 if (det || collectHandler
is null ||
collectHandler(cast(Object
) p
))
1286 (cast(fp_t
) c
.destructor
)(cast(Object
) p
); // call destructor
1288 while ((c
= c
.base
) !is null);
1291 if (ppv
[1]) // if monitor is not null
1292 _d_monitordelete(cast(Object
) p
, det
);
1296 auto w
= (*pc
).initializer
;
1297 p
[0 .. w
.length
] = w
[];
1302 import core
.exception
: onFinalizeError
;
1303 onFinalizeError(*pc
, e
);
1307 *ppv
= null; // zero vptr even if `resetMemory` is false
1311 /// Backwards compatibility
1312 extern (C
) void rt_finalize(void* p
, bool det
= true) nothrow
1314 rt_finalize2(p
, det
, true);
1317 extern (C
) void rt_finalizeFromGC(void* p
, size_t size
, uint attr
) nothrow
1319 // to verify: reset memory necessary?
1320 if (!(attr
& BlkAttr
.STRUCTFINAL
))
1321 rt_finalize2(p
, false, false); // class
1322 else if (attr
& BlkAttr
.APPENDABLE
)
1323 finalize_array2(p
, size
); // array of structs
1325 finalize_struct(p
, size
); // struct
1330 Resize a dynamic array by setting the `.length` property
1332 Newly created elements are initialized to their default value.
1335 - `_d_arraysetlengthT` for arrays with elements that initialize to 0
1336 - `_d_arraysetlengthiT` for non-zero initializers retrieved from `TypeInfo`
1342 a.length = 3; // gets lowered to `_d_arraysetlengthT(typeid(int[]), 3, &a)`
1347 ti = `TypeInfo` of array
1348 newlength = new value for the array's `.length`
1349 p = pointer to array to update the `.length` of.
1350 While it's cast to `void[]`, its `.length` is still treated as element length.
1351 Returns: `*p` after being updated
1353 extern (C
) void[] _d_arraysetlengthT(const TypeInfo ti
, size_t newlength
, void[]* p
) @weak
1357 assert(!(*p
).length ||
(*p
).ptr
);
1361 import core
.stdc
.string
;
1362 import core
.exception
: onOutOfMemoryError
;
1366 //printf("_d_arraysetlengthT(p = %p, sizeelem = %d, newlength = %d)\n", p, sizeelem, newlength);
1368 printf("\tp.ptr = %p, p.length = %d\n", (*p
).ptr
, (*p
).length
);
1371 if (newlength
<= (*p
).length
)
1373 *p
= (*p
)[0 .. newlength
];
1374 void* newdata
= (*p
).ptr
;
1375 return newdata
[0 .. newlength
];
1377 auto tinext
= unqualify(ti
.next
);
1378 size_t sizeelem
= tinext
.tsize
;
1380 /* Calculate: newsize = newlength * sizeelem
1382 bool overflow
= false;
1383 version (D_InlineAsm_X86
)
1385 size_t newsize
= void;
1387 asm pure nothrow @nogc
1395 else version (D_InlineAsm_X86_64
)
1397 size_t newsize
= void;
1399 asm pure nothrow @nogc
1409 import core
.checkedint
: mulu
;
1410 const size_t newsize
= mulu(sizeelem
, newlength
, overflow
);
1414 onOutOfMemoryError();
1418 debug(PRINTF
) printf("newsize = %x, newlength = %x\n", newsize
, newlength
);
1420 const isshared
= typeid(ti
) is typeid(TypeInfo_Shared
);
1424 // pointer was null, need to allocate
1425 auto info
= __arrayAlloc(newsize
, ti
, tinext
);
1426 if (info
.base
is null)
1428 onOutOfMemoryError();
1431 __setArrayAllocLength(info
, newsize
, isshared
, tinext
);
1433 __insertBlkInfoCache(info
, null);
1434 void* newdata
= cast(byte *)__arrayStart(info
);
1435 memset(newdata
, 0, newsize
);
1436 *p
= newdata
[0 .. newlength
];
1440 const size_t size
= (*p
).length
* sizeelem
;
1441 auto bic
= isshared ?
null : __getBlkInfo((*p
).ptr
);
1442 auto info
= bic ?
*bic
: GC
.query((*p
).ptr
);
1444 /* Attempt to extend past the end of the existing array.
1445 * If not possible, allocate new space for entire array and copy.
1447 bool allocateAndCopy
= false;
1448 void* newdata
= (*p
).ptr
;
1449 if (info
.base
&& (info
.attr
& BlkAttr
.APPENDABLE
))
1451 // calculate the extent of the array given the base.
1452 const size_t offset
= (*p
).ptr
- __arrayStart(info
);
1453 if (info
.size
>= PAGESIZE
)
1455 // size of array is at the front of the block
1456 if (!__setArrayAllocLength(info
, newsize
+ offset
, isshared
, tinext
, size
+ offset
))
1458 // check to see if it failed because there is not
1460 if (*(cast(size_t
*)info
.base
) == size
+ offset
)
1462 // not enough space, try extending
1463 auto extendsize
= newsize
+ offset
+ LARGEPAD
- info
.size
;
1464 auto u
= GC
.extend(info
.base
, extendsize
, extendsize
);
1467 // extend worked, now try setting the length
1470 if (__setArrayAllocLength(info
, newsize
+ offset
, isshared
, tinext
, size
+ offset
))
1473 __insertBlkInfoCache(info
, bic
);
1474 memset(newdata
+ size
, 0, newsize
- size
);
1475 *p
= newdata
[0 .. newlength
];
1481 // couldn't do it, reallocate
1482 allocateAndCopy
= true;
1484 else if (!isshared
&& !bic
)
1486 // add this to the cache, it wasn't present previously.
1487 __insertBlkInfoCache(info
, null);
1490 else if (!__setArrayAllocLength(info
, newsize
+ offset
, isshared
, tinext
, size
+ offset
))
1492 // could not resize in place
1493 allocateAndCopy
= true;
1495 else if (!isshared
&& !bic
)
1497 // add this to the cache, it wasn't present previously.
1498 __insertBlkInfoCache(info
, null);
1502 allocateAndCopy
= true;
1504 if (allocateAndCopy
)
1510 // a chance that flags have changed since this was cached, we should fetch the most recent flags
1511 info
.attr
= GC
.getAttr(info
.base
) | BlkAttr
.APPENDABLE
;
1513 info
= __arrayAlloc(newsize
, info
, ti
, tinext
);
1517 info
= __arrayAlloc(newsize
, ti
, tinext
);
1520 if (info
.base
is null)
1522 onOutOfMemoryError();
1526 __setArrayAllocLength(info
, newsize
, isshared
, tinext
);
1528 __insertBlkInfoCache(info
, bic
);
1529 newdata
= cast(byte *)__arrayStart(info
);
1530 newdata
[0 .. size
] = (*p
).ptr
[0 .. size
];
1532 /* Do postblit processing, as we are making a copy and the
1533 * original array may have references.
1534 * Note that this may throw.
1536 __doPostblit(newdata
, size
, tinext
);
1539 // Zero the unused portion of the newly allocated space
1540 memset(newdata
+ size
, 0, newsize
- size
);
1542 *p
= newdata
[0 .. newlength
];
1547 extern (C
) void[] _d_arraysetlengthiT(const TypeInfo ti
, size_t newlength
, void[]* p
) @weak
1550 assert(!(*p
).length ||
(*p
).ptr
);
1554 import core
.stdc
.string
;
1555 import core
.exception
: onOutOfMemoryError
;
1559 //printf("_d_arraysetlengthiT(p = %p, sizeelem = %d, newlength = %d)\n", p, sizeelem, newlength);
1561 printf("\tp.ptr = %p, p.length = %d\n", (*p
).ptr
, (*p
).length
);
1564 if (newlength
<= (*p
).length
)
1566 *p
= (*p
)[0 .. newlength
];
1567 void* newdata
= (*p
).ptr
;
1568 return newdata
[0 .. newlength
];
1570 auto tinext
= unqualify(ti
.next
);
1571 size_t sizeelem
= tinext
.tsize
;
1573 /* Calculate: newsize = newlength * sizeelem
1575 bool overflow
= false;
1576 version (D_InlineAsm_X86
)
1578 size_t newsize
= void;
1580 asm pure nothrow @nogc
1588 else version (D_InlineAsm_X86_64
)
1590 size_t newsize
= void;
1592 asm pure nothrow @nogc
1602 import core
.checkedint
: mulu
;
1603 const size_t newsize
= mulu(sizeelem
, newlength
, overflow
);
1607 onOutOfMemoryError();
1611 debug(PRINTF
) printf("newsize = %x, newlength = %x\n", newsize
, newlength
);
1613 const isshared
= typeid(ti
) is typeid(TypeInfo_Shared
);
1615 static void doInitialize(void *start
, void *end
, const void[] initializer
)
1617 if (initializer
.length
== 1)
1619 memset(start
, *(cast(ubyte*)initializer
.ptr
), end
- start
);
1623 auto q
= initializer
.ptr
;
1624 immutable initsize
= initializer
.length
;
1625 for (; start
< end
; start
+= initsize
)
1627 memcpy(start
, q
, initsize
);
1634 // pointer was null, need to allocate
1635 auto info
= __arrayAlloc(newsize
, ti
, tinext
);
1636 if (info
.base
is null)
1638 onOutOfMemoryError();
1641 __setArrayAllocLength(info
, newsize
, isshared
, tinext
);
1643 __insertBlkInfoCache(info
, null);
1644 void* newdata
= cast(byte *)__arrayStart(info
);
1645 doInitialize(newdata
, newdata
+ newsize
, tinext
.initializer
);
1646 *p
= newdata
[0 .. newlength
];
1650 const size_t size
= (*p
).length
* sizeelem
;
1651 auto bic
= isshared ?
null : __getBlkInfo((*p
).ptr
);
1652 auto info
= bic ?
*bic
: GC
.query((*p
).ptr
);
1654 /* Attempt to extend past the end of the existing array.
1655 * If not possible, allocate new space for entire array and copy.
1657 bool allocateAndCopy
= false;
1658 void* newdata
= (*p
).ptr
;
1660 if (info
.base
&& (info
.attr
& BlkAttr
.APPENDABLE
))
1662 // calculate the extent of the array given the base.
1663 const size_t offset
= (*p
).ptr
- __arrayStart(info
);
1664 if (info
.size
>= PAGESIZE
)
1666 // size of array is at the front of the block
1667 if (!__setArrayAllocLength(info
, newsize
+ offset
, isshared
, tinext
, size
+ offset
))
1669 // check to see if it failed because there is not
1671 if (*(cast(size_t
*)info
.base
) == size
+ offset
)
1673 // not enough space, try extending
1674 auto extendsize
= newsize
+ offset
+ LARGEPAD
- info
.size
;
1675 auto u
= GC
.extend(info
.base
, extendsize
, extendsize
);
1678 // extend worked, now try setting the length
1681 if (__setArrayAllocLength(info
, newsize
+ offset
, isshared
, tinext
, size
+ offset
))
1684 __insertBlkInfoCache(info
, bic
);
1685 doInitialize(newdata
+ size
, newdata
+ newsize
, tinext
.initializer
);
1686 *p
= newdata
[0 .. newlength
];
1692 // couldn't do it, reallocate
1693 allocateAndCopy
= true;
1695 else if (!isshared
&& !bic
)
1697 // add this to the cache, it wasn't present previously.
1698 __insertBlkInfoCache(info
, null);
1701 else if (!__setArrayAllocLength(info
, newsize
+ offset
, isshared
, tinext
, size
+ offset
))
1703 // could not resize in place
1704 allocateAndCopy
= true;
1706 else if (!isshared
&& !bic
)
1708 // add this to the cache, it wasn't present previously.
1709 __insertBlkInfoCache(info
, null);
1713 allocateAndCopy
= true;
1715 if (allocateAndCopy
)
1721 // a chance that flags have changed since this was cached, we should fetch the most recent flags
1722 info
.attr
= GC
.getAttr(info
.base
) | BlkAttr
.APPENDABLE
;
1724 info
= __arrayAlloc(newsize
, info
, ti
, tinext
);
1728 info
= __arrayAlloc(newsize
, ti
, tinext
);
1731 if (info
.base
is null)
1733 onOutOfMemoryError();
1737 __setArrayAllocLength(info
, newsize
, isshared
, tinext
);
1739 __insertBlkInfoCache(info
, bic
);
1740 newdata
= cast(byte *)__arrayStart(info
);
1741 newdata
[0 .. size
] = (*p
).ptr
[0 .. size
];
1743 /* Do postblit processing, as we are making a copy and the
1744 * original array may have references.
1745 * Note that this may throw.
1747 __doPostblit(newdata
, size
, tinext
);
1750 // Initialize the unused portion of the newly allocated space
1751 doInitialize(newdata
+ size
, newdata
+ newsize
, tinext
.initializer
);
1752 *p
= newdata
[0 .. newlength
];
1758 Given an array of length `size` that needs to be expanded to `newlength`,
1759 compute a new capacity.
1761 Better version by Dave Fladebo:
1762 This uses an inverse logorithmic algorithm to pre-allocate a bit more
1763 space for larger arrays.
1764 - Arrays smaller than PAGESIZE bytes are left as-is, so for the most
1765 common cases, memory allocation is 1 to 1. The small overhead added
1766 doesn't affect small array perf. (it's virtually the same as
1768 - Larger arrays have some space pre-allocated.
1769 - As the arrays grow, the relative pre-allocated space shrinks.
1770 - The logorithmic algorithm allocates relatively more space for
1771 mid-size arrays, making it very fast for medium arrays (for
1772 mid-to-large arrays, this turns out to be quite a bit faster than the
1773 equivalent realloc() code in C, on Linux at least. Small arrays are
1774 just as fast as GCC).
1775 - Perhaps most importantly, overall memory usage and stress on the GC
1776 is decreased significantly for demanding environments.
1779 newlength = new `.length`
1780 size = old `.length`
1781 Returns: new capacity for array
1783 size_t
newCapacity(size_t newlength
, size_t size
)
1787 size_t newcap
= newlength
* size
;
1791 size_t newcap
= newlength
* size
;
1794 if (newcap
> PAGESIZE
)
1796 //double mult2 = 1.0 + (size / log10(pow(newcap * 2.0,2.0)));
1798 // redo above line using only integer math
1800 /*static int log2plus1(size_t c)
1806 for (i = 1; c >>= 1; i++)
1812 /* The following setting for mult sets how much bigger
1813 * the new size will be over what is actually needed.
1814 * 100 means the same size, more means proportionally more.
1815 * More means faster but more memory consumption.
1817 //long mult = 100 + (1000L * size) / (6 * log2plus1(newcap));
1818 //long mult = 100 + (1000L * size) / log2plus1(newcap);
1820 long mult
= 100 + (1000L) / (bsr(newcap
) + 1);
1822 // testing shows 1.02 for large arrays is about the point of diminishing return
1824 // Commented out because the multipler will never be < 102. In order for it to be < 2,
1825 // then 1000L / (bsr(x) + 1) must be > 2. The highest bsr(x) + 1
1826 // could be is 65 (64th bit set), and 1000L / 64 is much larger
1827 // than 2. We need 500 bit integers for 101 to be achieved :)
1830 /*newext = cast(size_t)((newcap * mult) / 100);
1831 newext -= newext % size;*/
1832 // This version rounds up to the next element, and avoids using
1834 newext
= cast(size_t
)((newlength
* mult
+ 99) / 100) * size
;
1835 debug(PRINTF
) printf("mult: %2.2f, alloc: %2.2f\n",mult
/100.0,newext
/ cast(double)size
);
1837 newcap
= newext
> newcap ? newext
: newcap
;
1838 debug(PRINTF
) printf("newcap = %d, newlength = %d, size = %d\n", newcap
, newlength
, size
);
1845 Extend an array by n elements.
1847 Caller must initialize those elements.
1850 ti = type info of array type (not element type)
1851 px = array to append to, cast to `byte[]` while keeping the same `.length`. Will be updated.
1852 n = number of elements to append
1853 Returns: `px` after being appended to
1856 byte[] _d_arrayappendcTX(const TypeInfo ti
, return scope ref byte[] px
, size_t n
) @weak
1858 import core
.stdc
.string
;
1859 // This is a cut&paste job from _d_arrayappendT(). Should be refactored.
1861 // only optimize array append where ti is not a shared type
1862 auto tinext
= unqualify(ti
.next
);
1863 auto sizeelem
= tinext
.tsize
; // array element size
1864 auto isshared
= typeid(ti
) is typeid(TypeInfo_Shared
);
1865 auto bic
= isshared ?
null : __getBlkInfo(px
.ptr
);
1866 auto info
= bic ?
*bic
: GC
.query(px
.ptr
);
1867 auto length
= px
.length
;
1868 auto newlength
= length
+ n
;
1869 auto newsize
= newlength
* sizeelem
;
1870 auto size
= length
* sizeelem
;
1871 size_t newcap
= void; // for scratch space
1873 // calculate the extent of the array given the base.
1874 size_t offset
= cast(void*)px
.ptr
- __arrayStart(info
);
1875 if (info
.base
&& (info
.attr
& BlkAttr
.APPENDABLE
))
1877 if (info
.size
>= PAGESIZE
)
1879 // size of array is at the front of the block
1880 if (!__setArrayAllocLength(info
, newsize
+ offset
, isshared
, tinext
, size
+ offset
))
1882 // check to see if it failed because there is not
1884 newcap
= newCapacity(newlength
, sizeelem
);
1885 if (*(cast(size_t
*)info
.base
) == size
+ offset
)
1887 // not enough space, try extending
1888 auto extendoffset
= offset
+ LARGEPAD
- info
.size
;
1889 auto u
= GC
.extend(info
.base
, newsize
+ extendoffset
, newcap
+ extendoffset
);
1892 // extend worked, now try setting the length
1895 if (__setArrayAllocLength(info
, newsize
+ offset
, isshared
, tinext
, size
+ offset
))
1898 __insertBlkInfoCache(info
, bic
);
1904 // couldn't do it, reallocate
1907 else if (!isshared
&& !bic
)
1909 __insertBlkInfoCache(info
, null);
1912 else if (!__setArrayAllocLength(info
, newsize
+ offset
, isshared
, tinext
, size
+ offset
))
1914 // could not resize in place
1915 newcap
= newCapacity(newlength
, sizeelem
);
1918 else if (!isshared
&& !bic
)
1920 __insertBlkInfoCache(info
, null);
1925 // not appendable or is null
1926 newcap
= newCapacity(newlength
, sizeelem
);
1932 // a chance that flags have changed since this was cached, we should fetch the most recent flags
1933 info
.attr
= GC
.getAttr(info
.base
) | BlkAttr
.APPENDABLE
;
1935 info
= __arrayAlloc(newcap
, info
, ti
, tinext
);
1939 info
= __arrayAlloc(newcap
, ti
, tinext
);
1941 __setArrayAllocLength(info
, newsize
, isshared
, tinext
);
1943 __insertBlkInfoCache(info
, bic
);
1944 auto newdata
= cast(byte *)__arrayStart(info
);
1945 memcpy(newdata
, px
.ptr
, length
* sizeelem
);
1946 // do postblit processing
1947 __doPostblit(newdata
, length
* sizeelem
, tinext
);
1948 (cast(void **)(&px
))[1] = newdata
;
1952 *cast(size_t
*)&px
= newlength
;
1958 Append `dchar` to `char[]`, converting UTF-32 to UTF-8
1969 x = array to append to cast to `byte[]`. Will be modified.
1970 c = `dchar` to append
1971 Returns: updated `x` cast to `void[]`
1973 extern (C
) void[] _d_arrayappendcd(ref byte[] x
, dchar c
) @weak
1975 // c could encode into from 1 to 4 characters
1977 char[] appendthis
; // passed to appendT
1980 buf
.ptr
[0] = cast(char)c
;
1981 appendthis
= buf
[0..1];
1983 else if (c
<= 0x7FF)
1985 buf
.ptr
[0] = cast(char)(0xC0 |
(c
>> 6));
1986 buf
.ptr
[1] = cast(char)(0x80 |
(c
& 0x3F));
1987 appendthis
= buf
[0..2];
1989 else if (c
<= 0xFFFF)
1991 buf
.ptr
[0] = cast(char)(0xE0 |
(c
>> 12));
1992 buf
.ptr
[1] = cast(char)(0x80 |
((c
>> 6) & 0x3F));
1993 buf
.ptr
[2] = cast(char)(0x80 |
(c
& 0x3F));
1994 appendthis
= buf
[0..3];
1996 else if (c
<= 0x10FFFF)
1998 buf
.ptr
[0] = cast(char)(0xF0 |
(c
>> 18));
1999 buf
.ptr
[1] = cast(char)(0x80 |
((c
>> 12) & 0x3F));
2000 buf
.ptr
[2] = cast(char)(0x80 |
((c
>> 6) & 0x3F));
2001 buf
.ptr
[3] = cast(char)(0x80 |
(c
& 0x3F));
2002 appendthis
= buf
[0..4];
2006 import core
.exception
: onUnicodeError
;
2007 onUnicodeError("Invalid UTF-8 sequence", 0); // invalid utf character
2011 // TODO: This always assumes the array type is shared, because we do not
2012 // get a typeinfo from the compiler. Assuming shared is the safest option.
2013 // Once the compiler is fixed, the proper typeinfo should be forwarded.
2016 // Hack because _d_arrayappendT takes `x` as a reference
2017 auto xx
= cast(shared(char)[])x
;
2018 object
._d_arrayappendT(xx
, cast(shared(char)[])appendthis
);
2025 import core
.exception
: UnicodeException
;
2027 /* Using inline try {} catch {} blocks fails to catch the UnicodeException
2029 * https://issues.dlang.org/show_bug.cgi?id=16799
2031 static void assertThrown(T
: Throwable
= Exception
, E
)(lazy E expr
, string msg
)
2036 assert(e
.msg
== msg
);
2048 assertThrown
!UnicodeException(f(), "Invalid UTF-8 sequence");
2053 Append `dchar` to `wchar[]`, converting UTF-32 to UTF-16
2065 x = array to append to cast to `byte[]`. Will be modified.
2066 c = `dchar` to append
2068 Returns: updated `x` cast to `void[]`
2070 extern (C
) void[] _d_arrayappendwd(ref byte[] x
, dchar c
) @weak
2072 // c could encode into from 1 to 2 w characters
2073 wchar[2] buf
= void;
2074 wchar[] appendthis
; // passed to appendT
2077 buf
.ptr
[0] = cast(wchar) c
;
2078 appendthis
= buf
[0..1];
2082 buf
.ptr
[0] = cast(wchar) ((((c
- 0x10000) >> 10) & 0x3FF) + 0xD800);
2083 buf
.ptr
[1] = cast(wchar) (((c
- 0x10000) & 0x3FF) + 0xDC00);
2084 appendthis
= buf
[0..2];
2088 // TODO: This always assumes the array type is shared, because we do not
2089 // get a typeinfo from the compiler. Assuming shared is the safest option.
2090 // Once the compiler is fixed, the proper typeinfo should be forwarded.
2093 auto xx
= (cast(shared(wchar)*)x
.ptr
)[0 .. x
.length
];
2094 object
._d_arrayappendT(xx
, cast(shared(wchar)[])appendthis
);
2095 x
= (cast(byte*)xx
.ptr
)[0 .. xx
.length
];
2100 Allocate an array literal
2102 Rely on the caller to do the initialization of the array.
2108 // auto res = cast(int*) _d_arrayliteralTX(typeid(int[]), 2);
2111 // return res[0..2];
2116 ti = `TypeInfo` of resulting array type
2117 length = `.length` of array literal
2119 Returns: pointer to allocated array
2122 void* _d_arrayliteralTX(const TypeInfo ti
, size_t length
) @weak
2124 auto tinext
= unqualify(ti
.next
);
2125 auto sizeelem
= tinext
.tsize
; // array element size
2128 debug(PRINTF
) printf("_d_arrayliteralTX(sizeelem = %d, length = %d)\n", sizeelem
, length
);
2129 if (length
== 0 || sizeelem
== 0)
2133 auto allocsize
= length
* sizeelem
;
2134 auto info
= __arrayAlloc(allocsize
, ti
, tinext
);
2135 auto isshared
= typeid(ti
) is typeid(TypeInfo_Shared
);
2136 __setArrayAllocLength(info
, allocsize
, isshared
, tinext
);
2137 result
= __arrayStart(info
);
2150 a
[0] = 1; a
[1] = 2; a
[2] = 3;
2152 assert(b
.length
== 3);
2153 for (i
= 0; i
< 3; i
++)
2154 assert(b
[i
] == i
+ 1);
2156 // test slice appending
2159 for (i
= 0; i
< 3; i
++)
2160 assert(a
[i
] == i
+ 1);
2163 char[] arr
= new char[4093];
2164 for (i
= 0; i
< arr
.length
; i
++)
2165 arr
[i
] = cast(char)(i
% 256);
2167 // note that these two commands used to cause corruption, which may not be
2170 auto arr2
= arr
~ "123";
2171 assert(arr2
[0..arr
.length
] == arr
);
2172 assert(arr2
[arr
.length
..$] == "123");
2174 // test postblit on array concat, append, length, etc.
2184 void testPostBlit(T
)()
2186 auto sarr
= new T
[1];
2187 debug(SENTINEL
) {} else
2188 assert(sarr
.capacity
== 1);
2192 assert(sarr
[0].x
== 0);
2194 assert(sarr2
[0].x
== 1);
2195 assert(sarr
[0].x
== 0);
2201 assert(sarr2
[0].x
== 1);
2202 assert(sarr2
[1].x
== 1);
2203 assert(sarr
[0].x
== 0);
2207 sarr2
= sarr
~ sarr
;
2208 assert(sarr2
[0].x
== 1);
2209 assert(sarr2
[1].x
== 1);
2210 assert(sarr
[0].x
== 0);
2212 // concat multiple (calls different method)
2213 sarr2
= sarr
~ sarr
~ sarr
;
2214 assert(sarr2
[0].x
== 1);
2215 assert(sarr2
[1].x
== 1);
2216 assert(sarr2
[2].x
== 1);
2217 assert(sarr
[0].x
== 0);
2222 assert(sarr2
[0].x
== 1);
2223 assert(sarr
[0].x
== 0);
2226 testPostBlit
!(const(S
))();
2231 // Bugzilla 3454 - Inconsistent flag setting in GC.realloc()
2232 static void test(size_t multiplier
)
2234 auto p
= GC
.malloc(8 * multiplier
, 0);
2235 assert(GC
.getAttr(p
) == 0);
2237 // no move, set attr
2238 p
= GC
.realloc(p
, 8 * multiplier
+ 5, BlkAttr
.NO_SCAN
);
2239 assert(GC
.getAttr(p
) == BlkAttr
.NO_SCAN
);
2241 // shrink, copy attr
2242 p
= GC
.realloc(p
, 2 * multiplier
, 0);
2243 assert(GC
.getAttr(p
) == BlkAttr
.NO_SCAN
);
2245 // extend, copy attr
2246 p
= GC
.realloc(p
, 8 * multiplier
, 0);
2247 assert(GC
.getAttr(p
) == BlkAttr
.NO_SCAN
);
2255 import core
.exception
;
2258 size_t x
= size_t
.max
;
2259 byte[] big_buf
= new byte[x
];
2261 catch (OutOfMemoryError
)
2268 // https://issues.dlang.org/show_bug.cgi?id=13854
2269 auto arr
= new ubyte[PAGESIZE
]; // ensure page size
2270 auto info1
= GC
.query(arr
.ptr
);
2271 assert(info1
.base
!is arr
.ptr
); // offset is required for page size or larger
2273 auto arr2
= arr
[0..1];
2274 assert(arr2
.capacity
== 0); // cannot append
2275 arr2
~= 0; // add a byte
2276 assert(arr2
.ptr
!is arr
.ptr
); // reallocated
2277 auto info2
= GC
.query(arr2
.ptr
);
2278 assert(info2
.base
is arr2
.ptr
); // no offset, the capacity is small.
2280 // do the same via setting length
2282 assert(arr2
.capacity
== 0);
2284 assert(arr2
.ptr
!is arr
.ptr
); // reallocated
2285 info2
= GC
.query(arr2
.ptr
);
2286 assert(info2
.base
is arr2
.ptr
); // no offset, the capacity is small.
2288 // do the same for char[] since we need a type with an initializer to test certain runtime functions
2289 auto carr
= new char[PAGESIZE
];
2290 info1
= GC
.query(carr
.ptr
);
2291 assert(info1
.base
!is carr
.ptr
); // offset is required for page size or larger
2293 auto carr2
= carr
[0..1];
2294 assert(carr2
.capacity
== 0); // cannot append
2295 carr2
~= 0; // add a byte
2296 assert(carr2
.ptr
!is carr
.ptr
); // reallocated
2297 info2
= GC
.query(carr2
.ptr
);
2298 assert(info2
.base
is carr2
.ptr
); // no offset, the capacity is small.
2300 // do the same via setting length
2302 assert(carr2
.capacity
== 0);
2304 assert(carr2
.ptr
!is carr
.ptr
); // reallocated
2305 info2
= GC
.query(carr2
.ptr
);
2306 assert(info2
.base
is carr2
.ptr
); // no offset, the capacity is small.
2311 // https://issues.dlang.org/show_bug.cgi?id=13878
2312 auto arr
= new ubyte[1];
2313 auto info
= GC
.query(arr
.ptr
);
2314 assert(info
.attr
& BlkAttr
.NO_SCAN
); // should be NO_SCAN
2315 arr
~= 0; // ensure array is inserted into cache
2316 debug(SENTINEL
) {} else
2317 assert(arr
.ptr
is info
.base
);
2318 GC
.clrAttr(arr
.ptr
, BlkAttr
.NO_SCAN
); // remove the attribute
2319 auto arr2
= arr
[0..1];
2320 assert(arr2
.capacity
== 0); // cannot append
2322 assert(arr2
.ptr
!is arr
.ptr
);
2323 info
= GC
.query(arr2
.ptr
);
2324 assert(!(info
.attr
& BlkAttr
.NO_SCAN
)); // ensure attribute sticks
2326 // do the same via setting length
2328 arr
~= 0; // ensure array is inserted into cache
2329 GC
.clrAttr(arr
.ptr
, BlkAttr
.NO_SCAN
); // remove the attribute
2331 assert(arr2
.capacity
== 0);
2333 assert(arr2
.ptr
!is arr
.ptr
); // reallocated
2334 info
= GC
.query(arr2
.ptr
);
2335 assert(!(info
.attr
& BlkAttr
.NO_SCAN
)); // ensure attribute sticks
2337 // do the same for char[] since we need a type with an initializer to test certain runtime functions
2338 auto carr
= new char[1];
2339 info
= GC
.query(carr
.ptr
);
2340 assert(info
.attr
& BlkAttr
.NO_SCAN
); // should be NO_SCAN
2341 carr
~= 0; // ensure array is inserted into cache
2342 debug(SENTINEL
) {} else
2343 assert(carr
.ptr
is info
.base
);
2344 GC
.clrAttr(carr
.ptr
, BlkAttr
.NO_SCAN
); // remove the attribute
2345 auto carr2
= carr
[0..1];
2346 assert(carr2
.capacity
== 0); // cannot append
2348 assert(carr2
.ptr
!is carr
.ptr
);
2349 info
= GC
.query(carr2
.ptr
);
2350 assert(!(info
.attr
& BlkAttr
.NO_SCAN
)); // ensure attribute sticks
2352 // do the same via setting length
2354 carr
~= 0; // ensure array is inserted into cache
2355 GC
.clrAttr(carr
.ptr
, BlkAttr
.NO_SCAN
); // remove the attribute
2357 assert(carr2
.capacity
== 0);
2359 assert(carr2
.ptr
!is carr
.ptr
); // reallocated
2360 info
= GC
.query(carr2
.ptr
);
2361 assert(!(info
.attr
& BlkAttr
.NO_SCAN
)); // ensure attribute sticks
2364 // test struct finalizers
2365 debug(SENTINEL
) {} else
2368 __gshared
int dtorCount
;
2381 GC
.runFinalizers((cast(char*)(typeid(S1
).xdtor
))[0..1]);
2382 assert(dtorCount
== 1);
2386 const(S1
)* s3
= new const(S1
);
2387 GC
.runFinalizers((cast(char*)(typeid(S1
).xdtor
))[0..1]);
2388 assert(dtorCount
== 1);
2389 GC
.free(cast(void*)s3
);
2392 shared(S1
)* s4
= new shared(S1
);
2393 GC
.runFinalizers((cast(char*)(typeid(S1
).xdtor
))[0..1]);
2394 assert(dtorCount
== 1);
2395 GC
.free(cast(void*)s4
);
2398 const(S1
)[] carr1
= new const(S1
)[5];
2399 BlkInfo blkinf1
= GC
.query(carr1
.ptr
);
2400 GC
.runFinalizers((cast(char*)(typeid(S1
).xdtor
))[0..1]);
2401 assert(dtorCount
== 5);
2402 GC
.free(blkinf1
.base
);
2405 S1
[] arr2
= new S1
[10];
2407 arr2
.assumeSafeAppend
;
2408 assert(dtorCount
== 4); // destructors run explicitely?
2411 BlkInfo blkinf
= GC
.query(arr2
.ptr
);
2412 GC
.runFinalizers((cast(char*)(typeid(S1
).xdtor
))[0..1]);
2413 assert(dtorCount
== 6);
2414 GC
.free(blkinf
.base
);
2416 // associative arrays
2417 import rt
.aaA
: entryDtor
;
2418 // throw away all existing AA entries with dtor
2419 GC
.runFinalizers((cast(char*)(&entryDtor
))[0..1]);
2426 GC
.runFinalizers((cast(char*)(&entryDtor
))[0..1]);
2427 assert(dtorCount
== 2);
2435 GC
.runFinalizers((cast(char*)(&entryDtor
))[0..1]);
2436 assert(dtorCount
== 3);
2439 aa3
[0] = [S1(0),S1(2)];
2440 aa3
[1] = [S1(1),S1(3)];
2443 GC
.runFinalizers((cast(char*)(&entryDtor
))[0..1]);
2444 assert(dtorCount
== 4);
2447 // test struct dtor handling not causing false pointers
2450 // for 64-bit, allocate a struct of size 40
2460 // a struct with a dtor with size 32, but the dtor will cause
2461 // allocation to be larger by a pointer
2471 auto a
= new A
; // reuse same memory
2472 if (cast(void*)a
is cast(void*)p2
) // reusage not guaranteed
2474 auto ptr
= cast(S
**)(a
+ 1);
2475 assert(*ptr
!= p1
); // still same data as p2.ptr4?
2483 auto arr1
= new SArr
;
2487 // allocates 2*A.sizeof + (void*).sizeof (TypeInfo) + 1 (array length)
2488 auto arr2
= new A
[2];
2489 if (cast(void*)arr1
is cast(void*)arr2
.ptr
) // reusage not guaranteed
2491 auto ptr
= cast(S
**)(arr2
.ptr
+ 2);
2492 assert(*ptr
!= p1
); // still same data as p2.ptr4?
2500 auto larr1
= new LArr
;
2504 auto larr2
= new S
[255];
2505 if (cast(void*)larr1
is cast(void*)larr2
.ptr
- LARGEPREFIX
) // reusage not guaranteed
2507 auto ptr
= cast(S
**)larr1
;
2508 assert(ptr
[0] != p1
); // 16 bytes array header
2509 assert(ptr
[1] != p1
);
2510 version (D_LP64
) {} else
2512 assert(ptr
[2] != p1
);
2513 assert(ptr
[3] != p1
);
2518 // test class finalizers exception handling
2523 import core
.exception
;
2527 this(E exc
) { this.exc
= exc
; }
2528 ~this() { throw exc
; }
2531 bool caught
= false;
2532 C1 c
= new C1(new E("test onFinalizeError"));
2535 GC
.runFinalizers((cast(uint*)&C1
.__dtor
)[0..1]);
2537 catch (FinalizeError err
)
2544 GC
.free(cast(void*)c
);
2548 assert( test!Exception
);
2549 import core
.exception
: InvalidMemoryOperationError
;
2550 assert(!test!InvalidMemoryOperationError
);
2559 ~this() { assert(&this == thisptr
); thisptr
= null;}
2562 S
[] test14126
= new S
[2048]; // make sure we allocate at least a PAGE
2563 foreach (ref s
; test14126
)