2 * Contains the garbage collector implementation.
4 * Copyright: D Language Foundation 2001 - 2021.
5 * License: $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
6 * Authors: Walter Bright, David Friedman, Sean Kelly
8 module core
.internal
.gc
.impl
.conservative
.gc
;
10 // D Programming Language Garbage Collector implementation
12 /************** Debugging ***************************/
14 //debug = PRINTF; // turn on printf's
15 //debug = PARALLEL_PRINTF; // turn on printf's
16 //debug = COLLECT_PRINTF; // turn on printf's
17 //debug = MARK_PRINTF; // turn on printf's
18 //debug = PRINTF_TO_FILE; // redirect printf's ouptut to file "gcx.log"
19 //debug = LOGGING; // log allocations / frees
20 //debug = MEMSTOMP; // stomp on memory
21 //debug = SENTINEL; // add underrun/overrrun protection
22 // NOTE: this needs to be enabled globally in the makefiles
23 // (-debug=SENTINEL) to pass druntime's unittests.
24 //debug = PTRCHECK; // more pointer checking
25 //debug = PTRCHECK2; // thorough but slow pointer checking
26 //debug = INVARIANT; // enable invariants
27 //debug = PROFILE_API; // profile API calls for config.profile > 1
28 //debug = GC_RECURSIVE_LOCK; // check for recursive locking on the same thread
29 //debug = VALGRIND; // Valgrind memcheck integration
31 /***************************************************/
32 version = COLLECT_PARALLEL
; // parallel scanning
34 version = COLLECT_FORK
;
36 import core
.internal
.gc
.bits
;
37 import core
.internal
.gc
.os
;
38 import core
.gc
.config
;
39 import core
.gc
.gcinterface
;
41 import core
.internal
.container
.treap
;
42 import core
.internal
.spinlock
;
43 import core
.internal
.gc
.pooltable
;
45 import cstdlib
= core
.stdc
.stdlib
: calloc
, free
, malloc
, realloc
;
46 import core
.stdc
.string
: memcpy
, memset
, memmove
;
49 static import core
.memory
;
51 version (GNU
) import gcc
.builtins
;
53 debug (PRINTF_TO_FILE
) import core
.stdc
.stdio
: sprintf
, fprintf
, fopen
, fflush
, FILE
;
54 else import core
.stdc
.stdio
: sprintf
, printf
; // needed to output profiling results
56 debug (VALGRIND
) import etc
.valgrind
.valgrind
;
59 alias currTime
= MonoTime
.currTime
;
61 // Track total time spent preparing for GC,
62 // marking, sweeping and recovering pages.
63 __gshared Duration prepTime
;
64 __gshared Duration markTime
;
65 __gshared Duration sweepTime
;
66 __gshared Duration pauseTime
;
67 __gshared Duration maxPauseTime
;
68 __gshared Duration maxCollectionTime
;
69 __gshared size_t numCollections
;
70 __gshared size_t maxPoolMemory
;
72 __gshared
long numMallocs
;
73 __gshared
long numFrees
;
74 __gshared
long numReallocs
;
75 __gshared
long numExtends
;
76 __gshared
long numOthers
;
77 __gshared
long mallocTime
; // using ticks instead of MonoTime for better performance
78 __gshared
long freeTime
;
79 __gshared
long reallocTime
;
80 __gshared
long extendTime
;
81 __gshared
long otherTime
;
82 __gshared
long lockTime
;
84 ulong bytesAllocated
; // thread local counter
90 // to allow compilation of this module without access to the rt package,
91 // make these functions available from rt.lifetime
92 void rt_finalizeFromGC(void* p
, size_t size
, uint attr
) nothrow;
93 int rt_hasFinalizerInSegment(void* p
, size_t size
, uint attr
, const scope void[] segment
) nothrow;
95 // Declared as an extern instead of importing core.exception
96 // to avoid inlining - see https://issues.dlang.org/show_bug.cgi?id=13725.
97 void onInvalidMemoryOperationError(void* pretend_sideffect
= null) @trusted pure nothrow @nogc;
98 void onOutOfMemoryErrorNoGC() @trusted nothrow @nogc;
100 version (COLLECT_FORK
)
102 pid_t
__fork() nothrow;
107 OPFAIL
= ~cast(size_t
)0
113 /* ============================ GC =============================== */
115 // register GC in C constructor (_STI_)
116 private pragma(crt_constructor
) void gc_conservative_ctor()
118 _d_register_conservative_gc();
121 extern(C
) void _d_register_conservative_gc()
123 import core
.gc
.registry
;
124 registerGCFactory("conservative", &initialize
);
127 private pragma(crt_constructor
) void gc_precise_ctor()
129 _d_register_precise_gc();
132 extern(C
) void _d_register_precise_gc()
134 import core
.gc
.registry
;
135 registerGCFactory("precise", &initialize_precise
);
138 private GC
initialize()
140 import core
.lifetime
: emplace
;
142 auto gc
= cast(ConservativeGC
) cstdlib
.malloc(__traits(classInstanceSize
, ConservativeGC
));
144 onOutOfMemoryErrorNoGC();
149 private GC
initialize_precise()
151 ConservativeGC
.isPrecise
= true;
155 class ConservativeGC
: GC
157 // For passing to debug code (not thread safe)
158 __gshared size_t line
;
159 __gshared
char* file
;
161 Gcx
*gcx
; // implementation
163 static gcLock
= shared(AlignedSpinLock
)(SpinLock
.Contention
.lengthy
);
164 static bool _inFinalizer
;
165 __gshared
bool isPrecise
= false;
170 * Throws: InvalidMemoryOperationError on recursive locking during finalization.
172 static void lockNR() @safe @nogc nothrow
175 onInvalidMemoryOperationError();
180 * Initialize the GC based on command line configuration.
183 * OutOfMemoryError if failed to initialize GC due to not enough memory.
187 //config is assumed to have already been initialized
189 gcx
= cast(Gcx
*)cstdlib
.calloc(1, Gcx
.sizeof
);
191 onOutOfMemoryErrorNoGC();
194 if (config
.initReserve
)
195 gcx
.reserve(config
.initReserve
);
205 //debug(PRINTF) printf("Thread %x ", pthread_self());
206 //debug(PRINTF) printf("GC.Dtor()\n");
215 // TODO: cannot free as memory is overwritten and
216 // the monitor is still read in rt_finalize (called by destroy)
217 // cstdlib.free(cast(void*) this);
222 * Enables the GC if disable() was previously called. Must be called
223 * for each time disable was called in order to enable the GC again.
227 static void go(Gcx
* gcx
) nothrow
229 assert(gcx
.disabled
> 0);
232 runLocked
!(go
, otherTime
, numOthers
)(gcx
);
237 * Disable the GC. The GC may still run if it deems necessary.
241 static void go(Gcx
* gcx
) nothrow
245 runLocked
!(go
, otherTime
, numOthers
)(gcx
);
248 debug (GC_RECURSIVE_LOCK
) static bool lockedOnThisThread
;
251 * Run a function inside a lock/unlock set.
254 * func = The function to run.
255 * args = The function arguments.
257 auto runLocked(alias func
, Args
...)(auto ref Args args
)
259 debug(PROFILE_API
) immutable tm
= (config
.profile
> 1 ? currTime
.ticks
: 0);
260 debug(GC_RECURSIVE_LOCK
)
262 if (lockedOnThisThread
)
263 onInvalidMemoryOperationError();
264 lockedOnThisThread
= true;
267 scope (failure
) gcLock
.unlock();
268 debug(PROFILE_API
) immutable tm2
= (config
.profile
> 1 ? currTime
.ticks
: 0);
270 static if (is(typeof(func(args
)) == void))
273 auto res
= func(args
);
275 debug(PROFILE_API
) if (config
.profile
> 1)
276 lockTime
+= tm2
- tm
;
278 debug(GC_RECURSIVE_LOCK
)
280 if (!lockedOnThisThread
)
281 onInvalidMemoryOperationError();
282 lockedOnThisThread
= false;
285 static if (!is(typeof(func(args
)) == void))
290 * Run a function in an lock/unlock set that keeps track of
291 * how much time was spend inside this function (in ticks)
292 * and how many times this fuction was called.
295 * func = The function to run.
296 * time = The variable keeping track of the time (in ticks).
297 * count = The variable keeping track of how many times this fuction was called.
298 * args = The function arguments.
300 auto runLocked(alias func
, alias time
, alias count
, Args
...)(auto ref Args args
)
302 debug(PROFILE_API
) immutable tm
= (config
.profile
> 1 ? currTime
.ticks
: 0);
303 debug(GC_RECURSIVE_LOCK
)
305 if (lockedOnThisThread
)
306 onInvalidMemoryOperationError();
307 lockedOnThisThread
= true;
310 scope (failure
) gcLock
.unlock();
311 debug(PROFILE_API
) immutable tm2
= (config
.profile
> 1 ? currTime
.ticks
: 0);
313 static if (is(typeof(func(args
)) == void))
316 auto res
= func(args
);
318 debug(PROFILE_API
) if (config
.profile
> 1)
321 immutable now
= currTime
.ticks
;
322 lockTime
+= tm2
- tm
;
326 debug(GC_RECURSIVE_LOCK
)
328 if (!lockedOnThisThread
)
329 onInvalidMemoryOperationError();
330 lockedOnThisThread
= false;
333 static if (!is(typeof(func(args
)) == void))
339 * Returns a bit field representing all block attributes set for the memory
343 * p = A pointer to the base of a valid memory block or to null.
346 * A bit field containing any bits set for the memory block referenced by
347 * p or zero on error.
349 uint getAttr(void* p
) nothrow
356 static uint go(Gcx
* gcx
, void* p
) nothrow
358 Pool
* pool
= gcx
.findPool(p
);
364 if (p
!= pool
.findBase(p
))
366 auto biti
= cast(size_t
)(p
- pool
.baseAddr
) >> pool
.shiftBy
;
368 oldb
= pool
.getBits(biti
);
373 return runLocked
!(go
, otherTime
, numOthers
)(gcx
, p
);
377 * Sets the specified bits for the memory references by p.
379 * If p was not allocated by the GC, points inside a block, or is null, no
380 * action will be taken.
383 * p = A pointer to the base of a valid memory block or to null.
384 * mask = A bit field containing any bits to set for this memory block.
387 * The result of a call to getAttr after the specified bits have been
390 uint setAttr(void* p
, uint mask
) nothrow
397 static uint go(Gcx
* gcx
, void* p
, uint mask
) nothrow
399 Pool
* pool
= gcx
.findPool(p
);
405 if (p
!= pool
.findBase(p
))
407 auto biti
= cast(size_t
)(p
- pool
.baseAddr
) >> pool
.shiftBy
;
409 oldb
= pool
.getBits(biti
);
410 pool
.setBits(biti
, mask
);
415 return runLocked
!(go
, otherTime
, numOthers
)(gcx
, p
, mask
);
420 * Clears the specified bits for the memory references by p.
422 * If p was not allocated by the GC, points inside a block, or is null, no
423 * action will be taken.
426 * p = A pointer to the base of a valid memory block or to null.
427 * mask = A bit field containing any bits to clear for this memory block.
430 * The result of a call to getAttr after the specified bits have been
433 uint clrAttr(void* p
, uint mask
) nothrow
440 static uint go(Gcx
* gcx
, void* p
, uint mask
) nothrow
442 Pool
* pool
= gcx
.findPool(p
);
448 if (p
!= pool
.findBase(p
))
450 auto biti
= cast(size_t
)(p
- pool
.baseAddr
) >> pool
.shiftBy
;
452 oldb
= pool
.getBits(biti
);
453 pool
.clrBits(biti
, mask
);
458 return runLocked
!(go
, otherTime
, numOthers
)(gcx
, p
, mask
);
462 * Requests an aligned block of managed memory from the garbage collector.
465 * size = The desired allocation size in bytes.
466 * bits = A bitmask of the attributes to set on this block.
467 * ti = TypeInfo to describe the memory.
470 * A reference to the allocated memory or null if no memory was requested.
473 * OutOfMemoryError on allocation failure
475 void *malloc(size_t size
, uint bits
= 0, const TypeInfo ti
= null) nothrow
482 size_t localAllocSize
= void;
484 auto p
= runLocked
!(mallocNoSync
, mallocTime
, numMallocs
)(size
, bits
, localAllocSize
, ti
);
486 invalidate(p
[0 .. localAllocSize
], 0xF0, true);
488 if (!(bits
& BlkAttr
.NO_SCAN
))
490 memset(p
+ size
, 0, localAllocSize
- size
);
498 // Implementation for malloc and calloc.
500 private void *mallocNoSync(size_t size
, uint bits
, ref size_t alloc_size
, const TypeInfo ti
= null) nothrow
505 printf("GC::malloc(gcx = %p, size = %d bits = %x, ti = %s)\n", gcx
, size
, bits
, debugTypeName(ti
).ptr
);
508 //debug(PRINTF) printf("gcx.self = %x, pthread_self() = %x\n", gcx.self, pthread_self());
510 auto p
= gcx
.alloc(size
+ SENTINEL_EXTRA
, alloc_size
, bits
, ti
);
512 onOutOfMemoryErrorNoGC();
517 sentinel_init(p
, size
);
520 gcx
.leakDetector
.log_malloc(p
, size
);
521 bytesAllocated
+= alloc_size
;
523 debug(PRINTF
) printf(" => p = %p\n", p
);
527 BlkInfo
qalloc( size_t size
, uint bits
, const scope TypeInfo ti
) nothrow
537 retval
.base
= runLocked
!(mallocNoSync
, mallocTime
, numMallocs
)(size
, bits
, retval
.size
, ti
);
539 if (!(bits
& BlkAttr
.NO_SCAN
))
541 memset(retval
.base
+ size
, 0, retval
.size
- size
);
550 * Requests an aligned block of managed memory from the garbage collector,
551 * which is initialized with all bits set to zero.
554 * size = The desired allocation size in bytes.
555 * bits = A bitmask of the attributes to set on this block.
556 * ti = TypeInfo to describe the memory.
559 * A reference to the allocated memory or null if no memory was requested.
562 * OutOfMemoryError on allocation failure.
564 void *calloc(size_t size
, uint bits
= 0, const TypeInfo ti
= null) nothrow
571 size_t localAllocSize
= void;
573 auto p
= runLocked
!(mallocNoSync
, mallocTime
, numMallocs
)(size
, bits
, localAllocSize
, ti
);
575 debug (VALGRIND
) makeMemUndefined(p
[0..size
]);
576 invalidate((p
+ size
)[0 .. localAllocSize
- size
], 0xF0, true);
579 if (!(bits
& BlkAttr
.NO_SCAN
))
581 memset(p
+ size
, 0, localAllocSize
- size
);
588 * Request that the GC reallocate a block of memory, attempting to adjust
589 * the size in place if possible. If size is 0, the memory will be freed.
591 * If p was not allocated by the GC, points inside a block, or is null, no
592 * action will be taken.
595 * p = A pointer to the root of a valid memory block or to null.
596 * size = The desired allocation size in bytes.
597 * bits = A bitmask of the attributes to set on this block.
598 * ti = TypeInfo to describe the memory.
601 * A reference to the allocated memory on success or null if size is
605 * OutOfMemoryError on allocation failure.
607 void *realloc(void *p
, size_t size
, uint bits
= 0, const TypeInfo ti
= null) nothrow
609 size_t localAllocSize
= void;
612 p
= runLocked
!(reallocNoSync
, mallocTime
, numMallocs
)(p
, size
, bits
, localAllocSize
, ti
);
614 if (p
&& !(bits
& BlkAttr
.NO_SCAN
))
616 memset(p
+ size
, 0, localAllocSize
- size
);
624 // The implementation of realloc.
626 // bits will be set to the resulting bits of the new block
628 private void *reallocNoSync(void *p
, size_t size
, ref uint bits
, ref size_t alloc_size
, const TypeInfo ti
= null) nothrow
638 return mallocNoSync(size
, bits
, alloc_size
, ti
);
640 debug(PRINTF
) printf("GC::realloc(p = %p, size = %llu)\n", p
, cast(ulong)size
);
642 Pool
*pool
= gcx
.findPool(p
);
653 bool alwaysMalloc
= true;
658 enum alwaysMalloc
= false;
664 bits
= pool
.getBits(biti
);
666 void* p2
= mallocNoSync(size
, bits
, alloc_size
, ti
);
668 psize
= sentinel_size(q
, psize
);
671 //debug(PRINTF) printf("\tcopying %d bytes\n",size);
677 if (pool
.isLargeObject
)
679 auto lpool
= cast(LargeObjectPool
*) pool
;
680 auto psz
= lpool
.getPages(p
); // get allocated size
682 return null; // interior pointer
683 psize
= psz
* PAGESIZE
;
685 alias pagenum
= biti
; // happens to be the same, but rename for clarity
686 pagenum
= lpool
.pagenumOf(p
);
688 if (size
<= PAGESIZE
/ 2 || alwaysMalloc
)
689 return doMalloc(); // switching from large object pool to small object pool
691 auto newsz
= lpool
.numPages(size
);
696 else if (newsz
< psz
)
699 invalidate((p
+ size
)[0 .. psize
- size
], 0xF2, false);
700 lpool
.freePages(pagenum
+ newsz
, psz
- newsz
);
701 lpool
.mergeFreePageOffsets
!(false, true)(pagenum
+ newsz
, psz
- newsz
);
702 lpool
.bPageOffsets
[pagenum
] = cast(uint) newsz
;
704 else if (pagenum
+ newsz
<= pool
.npages
)
706 // Attempt to expand in place (TODO: merge with extend)
707 if (lpool
.pagetable
[pagenum
+ psz
] != Bins
.B_FREE
)
710 auto newPages
= newsz
- psz
;
711 auto freesz
= lpool
.bPageOffsets
[pagenum
+ psz
];
712 if (freesz
< newPages
)
713 return doMalloc(); // free range too small
715 invalidate((p
+ psize
)[0 .. size
- psize
], 0xF0, true);
716 debug (PRINTF
) printFreeInfo(pool
);
717 memset(&lpool
.pagetable
[pagenum
+ psz
], Bins
.B_PAGEPLUS
, newPages
);
718 lpool
.bPageOffsets
[pagenum
] = cast(uint) newsz
;
719 for (auto offset
= psz
; offset
< newsz
; offset
++)
720 lpool
.bPageOffsets
[pagenum
+ offset
] = cast(uint) offset
;
721 if (freesz
> newPages
)
722 lpool
.setFreePageOffsets(pagenum
+ newsz
, freesz
- newPages
);
723 gcx
.usedLargePages
+= newPages
;
724 lpool
.freepages
-= newPages
;
725 debug (PRINTF
) printFreeInfo(pool
);
728 return doMalloc(); // does not fit into current pool
730 alloc_size
= newsz
* PAGESIZE
;
734 psize
= (cast(SmallObjectPool
*) pool
).getSize(p
); // get allocated bin size
736 return null; // interior pointer
737 biti
= cast(size_t
)(p
- pool
.baseAddr
) >> Pool
.ShiftBy
.Small
;
738 if (pool
.freebits
.test (biti
))
741 // allocate if new size is bigger or less than half
742 if (psize
< size || psize
> size
* 2 || alwaysMalloc
)
747 pool
.setPointerBitmapSmall(p
, size
, psize
, bits
, ti
);
752 pool
.clrBits(biti
, ~BlkAttr
.NONE
);
753 pool
.setBits(biti
, bits
);
759 size_t
extend(void* p
, size_t minsize
, size_t maxsize
, const TypeInfo ti
) nothrow
761 return runLocked
!(extendNoSync
, extendTime
, numExtends
)(p
, minsize
, maxsize
, ti
);
766 // Implementation of extend.
768 private size_t
extendNoSync(void* p
, size_t minsize
, size_t maxsize
, const TypeInfo ti
= null) nothrow
771 assert(minsize
<= maxsize
);
775 debug(PRINTF
) printf("GC::extend(p = %p, minsize = %zu, maxsize = %zu)\n", p
, minsize
, maxsize
);
782 auto pool
= gcx
.findPool(p
);
783 if (!pool ||
!pool
.isLargeObject
)
786 auto lpool
= cast(LargeObjectPool
*) pool
;
787 size_t pagenum
= lpool
.pagenumOf(p
);
788 if (lpool
.pagetable
[pagenum
] != Bins
.B_PAGE
)
791 size_t psz
= lpool
.bPageOffsets
[pagenum
];
794 auto minsz
= lpool
.numPages(minsize
);
795 auto maxsz
= lpool
.numPages(maxsize
);
797 if (pagenum
+ psz
>= lpool
.npages
)
799 if (lpool
.pagetable
[pagenum
+ psz
] != Bins
.B_FREE
)
802 size_t freesz
= lpool
.bPageOffsets
[pagenum
+ psz
];
805 size_t sz
= freesz
> maxsz ? maxsz
: freesz
;
806 invalidate((pool
.baseAddr
+ (pagenum
+ psz
) * PAGESIZE
)[0 .. sz
* PAGESIZE
], 0xF0, true);
807 memset(lpool
.pagetable
+ pagenum
+ psz
, Bins
.B_PAGEPLUS
, sz
);
808 lpool
.bPageOffsets
[pagenum
] = cast(uint) (psz
+ sz
);
809 for (auto offset
= psz
; offset
< psz
+ sz
; offset
++)
810 lpool
.bPageOffsets
[pagenum
+ offset
] = cast(uint) offset
;
812 lpool
.setFreePageOffsets(pagenum
+ psz
+ sz
, freesz
- sz
);
813 lpool
.freepages
-= sz
;
814 gcx
.usedLargePages
+= sz
;
815 return (psz
+ sz
) * PAGESIZE
;
821 * Requests that at least size bytes of memory be obtained from the operating
822 * system and marked as free.
825 * size = The desired size in bytes.
828 * The actual number of bytes reserved or zero on error.
830 size_t
reserve(size_t size
) nothrow
837 return runLocked
!(reserveNoSync
, otherTime
, numOthers
)(size
);
842 // Implementation of reserve
844 private size_t
reserveNoSync(size_t size
) nothrow
849 return gcx
.reserve(size
);
854 * Deallocates the memory referenced by p.
856 * If p was not allocated by the GC, points inside a block, is null, or
857 * if free is called from a finalizer, no action will be taken.
860 * p = A pointer to the root of a valid memory block or to null.
862 void free(void *p
) nothrow
864 if (!p || _inFinalizer
)
869 return runLocked
!(freeNoSync
, freeTime
, numFrees
)(p
);
874 // Implementation of free.
876 private void freeNoSync(void *p
) nothrow @nogc
878 debug(PRINTF
) printf("Freeing %p\n", cast(size_t
) p
);
886 // Find which page it is in
887 pool
= gcx
.findPool(p
);
888 if (!pool
) // if not one of ours
891 pagenum
= pool
.pagenumOf(p
);
893 debug(PRINTF
) printf("pool base = %p, PAGENUM = %d of %d, bin = %d\n", pool
.baseAddr
, pagenum
, pool
.npages
, pool
.pagetable
[pagenum
]);
894 debug(PRINTF
) if (pool
.isLargeObject
) printf("Block size = %d\n", pool
.bPageOffsets
[pagenum
]);
896 bin
= pool
.pagetable
[pagenum
];
898 // Verify that the pointer is at the beginning of a block,
899 // no action should be taken if p is an interior pointer
900 if (bin
> Bins
.B_PAGE
) // B_PAGEPLUS or B_FREE
902 size_t off
= (sentinel_sub(p
) - pool
.baseAddr
);
903 size_t base
= baseOffset(off
, bin
);
907 sentinel_Invariant(p
);
912 if (pool
.isLargeObject
) // if large alloc
914 biti
= cast(size_t
)(p
- pool
.baseAddr
) >> pool
.ShiftBy
.Large
;
915 assert(bin
== Bins
.B_PAGE
);
916 auto lpool
= cast(LargeObjectPool
*) pool
;
919 size_t npages
= lpool
.bPageOffsets
[pagenum
];
920 auto size
= npages
* PAGESIZE
;
921 ssize
= sentinel_size(q
, size
);
922 invalidate(p
[0 .. size
], 0xF2, false);
923 lpool
.freePages(pagenum
, npages
);
924 lpool
.mergeFreePageOffsets
!(true, true)(pagenum
, npages
);
928 biti
= cast(size_t
)(p
- pool
.baseAddr
) >> pool
.ShiftBy
.Small
;
929 if (pool
.freebits
.test (biti
))
932 List
*list
= cast(List
*)p
;
934 auto size
= binsize
[bin
];
935 ssize
= sentinel_size(q
, size
);
936 invalidate(p
[0 .. size
], 0xF2, false);
938 // in case the page hasn't been recovered yet, don't add the object to the free list
939 if (!gcx
.recoverPool
[bin
] || pool
.binPageChain
[pagenum
] == Pool
.PageRecovered
)
941 undefinedWrite(list
.next
, gcx
.bucket
[bin
]);
942 undefinedWrite(list
.pool
, pool
);
943 gcx
.bucket
[bin
] = list
;
945 pool
.freebits
.set(biti
);
947 pool
.clrBits(biti
, ~BlkAttr
.NONE
);
949 gcx
.leakDetector
.log_free(sentinel_add(p
), ssize
);
954 * Determine the base address of the block containing p. If p is not a gc
955 * allocated pointer, return null.
958 * p = A pointer to the root or the interior of a valid memory block or to
962 * The base address of the memory block referenced by p or null on error.
964 void* addrOf(void *p
) nothrow
971 return runLocked
!(addrOfNoSync
, otherTime
, numOthers
)(p
);
976 // Implementation of addrOf.
978 void* addrOfNoSync(void *p
) nothrow @nogc
985 auto q
= gcx
.findBase(p
);
993 * Determine the allocated size of pointer p. If p is an interior pointer
994 * or not a gc allocated pointer, return 0.
997 * p = A pointer to the root of a valid memory block or to null.
1000 * The size in bytes of the memory block referenced by p or zero on error.
1002 size_t
sizeOf(void *p
) nothrow
1009 return runLocked
!(sizeOfNoSync
, otherTime
, numOthers
)(p
);
1014 // Implementation of sizeOf.
1016 private size_t
sizeOfNoSync(void *p
) nothrow @nogc
1022 p
= sentinel_sub(p
);
1023 size_t size
= gcx
.findSize(p
);
1024 return size ? size
- SENTINEL_EXTRA
: 0;
1028 size_t size
= gcx
.findSize(p
);
1035 * Determine the base address of the block containing p. If p is not a gc
1036 * allocated pointer, return null.
1039 * p = A pointer to the root or the interior of a valid memory block or to
1043 * Information regarding the memory block referenced by p or BlkInfo.init
1046 BlkInfo
query(void *p
) nothrow
1054 return runLocked
!(queryNoSync
, otherTime
, numOthers
)(p
);
1058 // Implementation of query
1060 BlkInfo
queryNoSync(void *p
) nothrow
1064 BlkInfo info
= gcx
.getInfo(p
);
1069 info
.base
= sentinel_add(info
.base
);
1070 info
.size
= *sentinel_psize(info
.base
);
1078 * Performs certain checks on a pointer. These checks will cause asserts to
1079 * fail unless the following conditions are met:
1080 * 1) The poiinter belongs to this memory pool.
1081 * 2) The pointer points to the start of an allocated piece of memory.
1082 * 3) The pointer is not on a free list.
1085 * p = The pointer to be checked.
1087 void check(void *p
) nothrow
1094 return runLocked
!(checkNoSync
, otherTime
, numOthers
)(p
);
1099 // Implementation of check
1101 private void checkNoSync(void *p
) nothrow
1105 sentinel_Invariant(p
);
1112 p
= sentinel_sub(p
);
1113 pool
= gcx
.findPool(p
);
1115 pagenum
= pool
.pagenumOf(p
);
1116 bin
= pool
.pagetable
[pagenum
];
1117 assert(bin
<= Bins
.B_PAGE
);
1118 assert(p
== cast(void*)baseOffset(cast(size_t
)p
, bin
));
1122 if (bin
< Bins
.B_PAGE
)
1124 // Check that p is not on a free list
1127 for (list
= gcx
.bucket
[bin
]; list
; list
= list
.next
)
1129 assert(cast(void*)list
!= p
);
1138 * Add p to list of roots. If p is null, no operation is performed.
1141 * p = A pointer into a GC-managed memory block or null.
1143 void addRoot(void *p
) nothrow @nogc
1155 * Remove p from list of roots. If p is null or is not a value
1156 * previously passed to addRoot() then no operation is performed.
1159 * p = A pointer into a GC-managed memory block or null.
1161 void removeRoot(void *p
) nothrow @nogc
1172 * Returns an iterator allowing roots to be traversed via a foreach loop.
1174 @property RootIterator
rootIter() @nogc
1176 return &gcx
.rootsApply
;
1181 * Add range to scan for roots. If p is null or sz is 0, no operation is performed.
1184 * p = A pointer to a valid memory address or to null.
1185 * sz = The size in bytes of the block to add.
1186 * ti = TypeInfo to describe the memory.
1188 void addRange(void *p
, size_t sz
, const TypeInfo ti
= null) nothrow @nogc
1195 gcx
.addRange(p
, p
+ sz
, ti
);
1200 * Remove range from list of ranges. If p is null or does not represent
1201 * a value previously passed to addRange() then no operation is
1205 * p = A pointer to a valid memory address or to null.
1207 void removeRange(void *p
) nothrow @nogc
1219 * Returns an iterator allowing ranges to be traversed via a foreach loop.
1221 @property RangeIterator
rangeIter() @nogc
1223 return &gcx
.rangesApply
;
1228 * Run all finalizers in the code segment.
1231 * segment = address range of a code segment
1233 void runFinalizers(const scope void[] segment
) nothrow
1235 static void go(Gcx
* gcx
, const scope void[] segment
) nothrow
1237 gcx
.runFinalizers(segment
);
1239 return runLocked
!(go
, otherTime
, numOthers
)(gcx
, segment
);
1243 bool inFinalizer() nothrow @nogc
1245 return _inFinalizer
;
1249 void collect() nothrow
1255 void collectNoStack() nothrow
1257 fullCollectNoStack();
1262 * Begins a full collection, scanning all stack segments for roots.
1265 * The number of pages freed.
1267 size_t
fullCollect() nothrow
1269 debug(PRINTF
) printf("GC.fullCollect()\n");
1271 // Since a finalizer could launch a new thread, we always need to lock
1273 static size_t
go(Gcx
* gcx
) nothrow
1275 return gcx
.fullcollect(false, true); // standard stop the world
1277 immutable result
= runLocked
!go(gcx
);
1284 debug(PRINTF
) printf("heapSize = %zx, freeSize = %zx\n",
1285 stats
.heapSize
, stats
.freeSize
);
1288 gcx
.leakDetector
.log_collect();
1294 * Begins a full collection while ignoring all stack segments for roots.
1296 void fullCollectNoStack() nothrow
1298 // Since a finalizer could launch a new thread, we always need to lock
1300 static size_t
go(Gcx
* gcx
) nothrow
1302 return gcx
.fullcollect(true, true, true); // standard stop the world
1309 * Minimize free space usage.
1311 void minimize() nothrow
1313 static void go(Gcx
* gcx
) nothrow
1317 runLocked
!(go
, otherTime
, numOthers
)(gcx
);
1321 core
.memory
.GC
.Stats
stats() @safe nothrow @nogc
1325 runLocked
!(getStatsNoSync
, otherTime
, numOthers
)(ret);
1331 core
.memory
.GC
.ProfileStats
profileStats() nothrow @trusted
1335 ret.numCollections
= numCollections
;
1336 ret.totalCollectionTime
= prepTime
+ markTime
+ sweepTime
;
1337 ret.totalPauseTime
= pauseTime
;
1338 ret.maxCollectionTime
= maxCollectionTime
;
1339 ret.maxPauseTime
= maxPauseTime
;
1345 ulong allocatedInCurrentThread() nothrow
1347 return bytesAllocated
;
1352 // Implementation of getStats
1354 private void getStatsNoSync(out core
.memory
.GC
.Stats stats
) @trusted nothrow @nogc
1356 // This function is trusted for two reasons: `pool.pagetable` is a pointer,
1357 // which is being sliced in the below foreach, and so is `binPageChain`,
1358 // also sliced a bit later in this function.
1359 // However, both usages are safe as long as the assumption that `npools`
1360 // defines the limit for `pagetable`'s length holds true (see allocation).
1361 // The slicing happens at __LINE__ + 4 and __LINE__ + 24.
1362 // `@trusted` delegates are not used to prevent any performance issue.
1363 foreach (pool
; gcx
.pooltable
[])
1365 foreach (bin
; pool
.pagetable
[0 .. pool
.npages
])
1367 if (bin
== Bins
.B_FREE
)
1368 stats
.freeSize
+= PAGESIZE
;
1370 stats
.usedSize
+= PAGESIZE
;
1374 size_t freeListSize
;
1375 foreach (n
; 0 .. Bins
.B_PAGE
)
1377 immutable sz
= binsize
[n
];
1378 for (List
*list
= gcx
.bucket
[n
]; list
; list
= list
.next
)
1381 foreach (pool
; gcx
.pooltable
[])
1383 if (pool
.isLargeObject
)
1385 for (uint pn
= pool
.recoverPageFirst
[n
]; pn
< pool
.npages
; pn
= pool
.binPageChain
[pn
])
1387 const bitbase
= pn
* PAGESIZE
/ 16;
1388 const top
= PAGESIZE
- sz
+ 1; // ensure <size> bytes available even if unaligned
1389 for (size_t u
= 0; u
< top
; u
+= sz
)
1390 if (pool
.freebits
.test(bitbase
+ u
/ 16))
1396 stats
.usedSize
-= freeListSize
;
1397 stats
.freeSize
+= freeListSize
;
1398 stats
.allocatedInCurrentThread
= bytesAllocated
;
1403 /* ============================ Gcx =============================== */
1428 B_PAGE
= B_NUMSMALL
,// start of large alloc
1429 B_PAGEPLUS
, // continuation of large alloc
1430 B_FREE
, // free page
1440 // non power of two sizes optimized for small remainder within page (<= 64 bytes)
1441 immutable short[Bins
.B_NUMSMALL
+ 1] binsize
= [ 16, 32, 48, 64, 96, 128, 176, 256, 368, 512, 816, 1024, 1360, 2048, 4096 ];
1442 immutable short[PAGESIZE
/ 16][Bins
.B_NUMSMALL
+ 1] binbase
= calcBinBase();
1444 short[PAGESIZE
/ 16][Bins
.B_NUMSMALL
+ 1] calcBinBase()
1446 short[PAGESIZE
/ 16][Bins
.B_NUMSMALL
+ 1] bin
;
1448 foreach (i
, size
; binsize
)
1450 short end
= (PAGESIZE
/ size
) * size
;
1451 short bsz
= size
/ 16;
1452 foreach (off
; 0..PAGESIZE
/16)
1454 // add the remainder to the last bin, so no check during scanning
1455 // is needed if a false pointer targets that area
1456 const base
= (off
- off
% bsz
) * 16;
1457 bin
[i
][off
] = cast(short)(base
< end ? base
: end
- size
);
1463 size_t
baseOffset(size_t offset
, Bins bin
) @nogc nothrow
1465 assert(bin
<= Bins
.B_PAGE
);
1466 return (offset
& ~(PAGESIZE
- 1)) + binbase
[bin
][(offset
& (PAGESIZE
- 1)) >> 4];
1469 alias PageBits
= GCBits
.wordtype
[PAGESIZE
/ 16 / GCBits
.BITS_PER_WORD
];
1470 static assert(PAGESIZE
% (GCBits
.BITS_PER_WORD
* 16) == 0);
1472 // bitmask with bits set at base offsets of objects
1473 immutable PageBits
[Bins
.B_NUMSMALL
] baseOffsetBits
= (){
1474 PageBits
[Bins
.B_NUMSMALL
] bits
;
1475 foreach (bin
; 0 .. Bins
.B_NUMSMALL
)
1477 size_t size
= binsize
[bin
];
1478 const top
= PAGESIZE
- size
+ 1; // ensure <size> bytes available even if unaligned
1479 for (size_t u
= 0; u
< top
; u
+= size
)
1481 size_t biti
= u
/ 16;
1482 size_t off
= biti
/ GCBits
.BITS_PER_WORD
;
1483 size_t mod
= biti
% GCBits
.BITS_PER_WORD
;
1484 bits
[bin
][off
] |
= GCBits
.BITS_1
<< mod
;
1490 private void set(ref PageBits bits
, size_t i
) @nogc pure nothrow
1492 assert(i
< PageBits
.sizeof
* 8);
1496 /* ============================ Gcx =============================== */
1500 auto rootsLock
= shared(AlignedSpinLock
)(SpinLock
.Contention
.brief
);
1501 auto rangesLock
= shared(AlignedSpinLock
)(SpinLock
.Contention
.brief
);
1504 bool minimizeAfterNextCollection
= false;
1505 version (COLLECT_FORK
)
1507 private pid_t markProcPid
= 0;
1511 debug(INVARIANT
) bool initialized
;
1512 debug(INVARIANT
) bool inCollection
;
1513 uint disabled
; // turn off collections if >0
1515 PoolTable
!Pool pooltable
;
1517 List
*[Bins
.B_NUMSMALL
] bucket
; // free list for each small size
1519 // run a collection when reaching those thresholds (number of used pages)
1520 float smallCollectThreshold
= 0.0f, largeCollectThreshold
= 0.0f;
1521 uint usedSmallPages
, usedLargePages
;
1522 // total number of mapped pages
1526 LeakDetector leakDetector
;
1528 alias leakDetector
= LeakDetector
;
1530 SmallObjectPool
*[Bins
.B_NUMSMALL
] recoverPool
;
1531 version (Posix
) __gshared Gcx
* instance
;
1535 (cast(byte*)&this)[0 .. Gcx
.sizeof
] = 0;
1536 leakDetector
.initialize(&this);
1537 roots
.initialize(0x243F6A8885A308D3UL
);
1538 ranges
.initialize(0x13198A2E03707344UL
);
1539 smallCollectThreshold
= largeCollectThreshold
= 0.0f;
1540 usedSmallPages
= usedLargePages
= 0;
1542 //printf("gcx = %p, self = %x\n", &this, self);
1545 import core
.sys
.posix
.pthread
: pthread_atfork
;
1547 __gshared atforkHandlersInstalled
= false;
1548 if (!atforkHandlersInstalled
)
1551 &_d_gcx_atfork_prepare
,
1552 &_d_gcx_atfork_parent
,
1553 &_d_gcx_atfork_child
);
1554 atforkHandlersInstalled
= true;
1557 debug(INVARIANT
) initialized
= true;
1558 version (COLLECT_FORK
)
1559 shouldFork
= config
.fork
;
1567 printf("\tNumber of collections: %llu\n", cast(ulong)numCollections
);
1568 printf("\tTotal GC prep time: %lld milliseconds\n",
1569 prepTime
.total
!("msecs"));
1570 printf("\tTotal mark time: %lld milliseconds\n",
1571 markTime
.total
!("msecs"));
1572 printf("\tTotal sweep time: %lld milliseconds\n",
1573 sweepTime
.total
!("msecs"));
1574 long maxPause
= maxPauseTime
.total
!("msecs");
1575 printf("\tMax Pause Time: %lld milliseconds\n", maxPause
);
1576 long gcTime
= (sweepTime
+ markTime
+ prepTime
).total
!("msecs");
1577 printf("\tGrand total GC time: %lld milliseconds\n", gcTime
);
1578 long pauseTime
= (markTime
+ prepTime
).total
!("msecs");
1580 char[30] apitxt
= void;
1582 debug(PROFILE_API
) if (config
.profile
> 1)
1584 static Duration
toDuration(long dur
)
1586 return MonoTime(dur
) - MonoTime(0);
1590 printf("\tmalloc: %llu calls, %lld ms\n", cast(ulong)numMallocs
, toDuration(mallocTime
).total
!"msecs");
1591 printf("\trealloc: %llu calls, %lld ms\n", cast(ulong)numReallocs
, toDuration(reallocTime
).total
!"msecs");
1592 printf("\tfree: %llu calls, %lld ms\n", cast(ulong)numFrees
, toDuration(freeTime
).total
!"msecs");
1593 printf("\textend: %llu calls, %lld ms\n", cast(ulong)numExtends
, toDuration(extendTime
).total
!"msecs");
1594 printf("\tother: %llu calls, %lld ms\n", cast(ulong)numOthers
, toDuration(otherTime
).total
!"msecs");
1595 printf("\tlock time: %lld ms\n", toDuration(lockTime
).total
!"msecs");
1597 long apiTime
= mallocTime
+ reallocTime
+ freeTime
+ extendTime
+ otherTime
+ lockTime
;
1598 printf("\tGC API: %lld ms\n", toDuration(apiTime
).total
!"msecs");
1599 sprintf(apitxt
.ptr
, " API%5ld ms", toDuration(apiTime
).total
!"msecs");
1602 printf("GC summary:%5lld MB,%5lld GC%5lld ms, Pauses%5lld ms <%5lld ms%s\n",
1603 cast(long) maxPoolMemory
>> 20, cast(ulong)numCollections
, gcTime
,
1604 pauseTime
, maxPause
, apitxt
.ptr
);
1609 version (COLLECT_PARALLEL
)
1612 debug(INVARIANT
) initialized
= false;
1614 foreach (Pool
* pool
; this.pooltable
[])
1616 mappedPages
-= pool
.npages
;
1620 assert(!mappedPages
);
1625 toscanConservative
.reset();
1626 toscanPrecise
.reset();
1630 void Invariant() const { }
1637 //printf("Gcx.invariant(): this = %p\n", &this);
1638 pooltable
.Invariant();
1639 for (size_t p
= 0; p
< pooltable
.length
; p
++)
1640 if (pooltable
.pools
[p
].isLargeObject
)
1641 (cast(LargeObjectPool
*)(pooltable
.pools
[p
])).Invariant();
1643 (cast(SmallObjectPool
*)(pooltable
.pools
[p
])).Invariant();
1646 (cast()rangesLock
).lock();
1647 foreach (range
; ranges
)
1651 assert(range
.pbot
<= range
.ptop
);
1654 (cast()rangesLock
).unlock();
1656 for (size_t i
= 0; i
< Bins
.B_NUMSMALL
; i
++)
1659 List
* prev
, pprev
, ppprev
; // keep a short history to inspect in the debugger
1660 for (auto list
= cast(List
*)bucket
[i
]; list
; list
= list
.next
)
1662 auto pool
= list
.pool
;
1663 auto biti
= cast(size_t
)(cast(void*)list
- pool
.baseAddr
) >> Pool
.ShiftBy
.Small
;
1664 assert(pool
.freebits
.test(biti
));
1673 @property bool collectInProgress() const nothrow
1675 version (COLLECT_FORK
)
1676 return markProcPid
!= 0;
1685 void addRoot(void *p
) nothrow @nogc
1688 scope (failure
) rootsLock
.unlock();
1689 roots
.insert(Root(p
));
1697 void removeRoot(void *p
) nothrow @nogc
1700 scope (failure
) rootsLock
.unlock();
1701 roots
.remove(Root(p
));
1709 int rootsApply(scope int delegate(ref Root
) nothrow dg
) nothrow
1712 scope (failure
) rootsLock
.unlock();
1713 auto ret = roots
.opApply(dg
);
1722 void addRange(void *pbot
, void *ptop
, const TypeInfo ti
) nothrow @nogc
1724 //debug(PRINTF) printf("Thread %x ", pthread_self());
1725 debug(PRINTF
) printf("%p.Gcx::addRange(%p, %p)\n", &this, pbot
, ptop
);
1727 scope (failure
) rangesLock
.unlock();
1728 ranges
.insert(Range(pbot
, ptop
));
1729 rangesLock
.unlock();
1736 void removeRange(void *pbot
) nothrow @nogc
1738 //debug(PRINTF) printf("Thread %x ", pthread_self());
1739 debug(PRINTF
) printf("Gcx.removeRange(%p)\n", pbot
);
1741 scope (failure
) rangesLock
.unlock();
1742 ranges
.remove(Range(pbot
, pbot
)); // only pbot is used, see Range.opCmp
1743 rangesLock
.unlock();
1745 // debug(PRINTF) printf("Wrong thread\n");
1746 // This is a fatal error, but ignore it.
1747 // The problem is that we can get a Close() call on a thread
1748 // other than the one the range was allocated on.
1755 int rangesApply(scope int delegate(ref Range
) nothrow dg
) nothrow
1758 scope (failure
) rangesLock
.unlock();
1759 auto ret = ranges
.opApply(dg
);
1760 rangesLock
.unlock();
1768 void runFinalizers(const scope void[] segment
) nothrow
1770 ConservativeGC
._inFinalizer
= true;
1771 scope (failure
) ConservativeGC
._inFinalizer
= false;
1773 foreach (pool
; this.pooltable
[])
1775 if (!pool
.finals
.nbits
) continue;
1777 if (pool
.isLargeObject
)
1779 auto lpool
= cast(LargeObjectPool
*) pool
;
1780 lpool
.runFinalizers(segment
);
1784 auto spool
= cast(SmallObjectPool
*) pool
;
1785 spool
.runFinalizers(segment
);
1788 ConservativeGC
._inFinalizer
= false;
1791 Pool
* findPool(void* p
) pure nothrow @nogc
1793 return pooltable
.findPool(p
);
1797 * Find base address of block containing pointer p.
1798 * Returns null if not a gc'd pointer
1800 void* findBase(void *p
) nothrow @nogc
1806 return pool
.findBase(p
);
1812 * Find size of pointer p.
1813 * Returns 0 if not a gc'd pointer
1815 size_t
findSize(void *p
) nothrow @nogc
1817 Pool
* pool
= findPool(p
);
1819 return pool
.slGetSize(p
);
1826 BlkInfo
getInfo(void* p
) nothrow
1828 Pool
* pool
= findPool(p
);
1830 return pool
.slGetInfo(p
);
1835 * Computes the bin table using CTFE.
1837 static Bins
[2049] ctfeBins() nothrow
1841 for (Bins b
= Bins
.B_16
; b
<= Bins
.B_2048
; b
++)
1842 for ( ; p
<= binsize
[b
]; p
++)
1848 static immutable Bins
[2049] binTable
= ctfeBins();
1851 * Allocate a new pool of at least size bytes.
1852 * Sort it into pooltable[].
1853 * Mark all memory in the pool as B_FREE.
1854 * Return the actual number of bytes reserved or 0 on error.
1856 size_t
reserve(size_t size
) nothrow
1858 size_t npages
= (size
+ PAGESIZE
- 1) / PAGESIZE
;
1860 // Assume reserve() is for small objects.
1861 Pool
* pool
= newPool(npages
, false);
1865 return pool
.npages
* PAGESIZE
;
1869 * Update the thresholds for when to collect the next time
1871 void updateCollectThresholds() nothrow
1873 static float max(float a
, float b
) nothrow
1875 return a
>= b ? a
: b
;
1878 // instantly increases, slowly decreases
1879 static float smoothDecay(float oldVal
, float newVal
) nothrow
1881 // decay to 63.2% of newVal over 5 collections
1882 // http://en.wikipedia.org/wiki/Low-pass_filter#Simple_infinite_impulse_response_filter
1883 enum alpha
= 1.0 / (5 + 1);
1884 immutable decay
= (newVal
- oldVal
) * alpha
+ oldVal
;
1885 return max(newVal
, decay
);
1888 immutable smTarget
= usedSmallPages
* config
.heapSizeFactor
;
1889 smallCollectThreshold
= smoothDecay(smallCollectThreshold
, smTarget
);
1890 immutable lgTarget
= usedLargePages
* config
.heapSizeFactor
;
1891 largeCollectThreshold
= smoothDecay(largeCollectThreshold
, lgTarget
);
1895 * Minimizes physical memory usage by returning free pools to the OS.
1897 void minimize() nothrow
1899 debug(PRINTF
) printf("Minimizing.\n");
1901 foreach (pool
; pooltable
.minimize())
1903 debug(PRINTF
) printFreeInfo(pool
);
1904 mappedPages
-= pool
.npages
;
1909 debug(PRINTF
) printf("Done minimizing.\n");
1912 private @property bool lowMem() const nothrow
1914 return isLowOnMem(cast(size_t
)mappedPages
* PAGESIZE
);
1917 void* alloc(size_t size
, ref size_t alloc_size
, uint bits
, const TypeInfo ti
) nothrow
1919 return size
<= PAGESIZE
/2 ?
smallAlloc(size
, alloc_size
, bits
, ti
)
1920 : bigAlloc(size
, alloc_size
, bits
, ti
);
1923 void* smallAlloc(size_t size
, ref size_t alloc_size
, uint bits
, const TypeInfo ti
) nothrow
1925 immutable bin
= binTable
[size
];
1926 alloc_size
= binsize
[bin
];
1928 void* p
= bucket
[bin
];
1932 if (recoverPool
[bin
])
1933 recoverNextPage(bin
);
1935 bool tryAlloc() nothrow
1939 bucket
[bin
] = allocPage(bin
);
1949 if (!lowMem
&& (disabled || usedSmallPages
< smallCollectThreshold
))
1951 // disabled or threshold not reached => allocate a new pool instead of collecting
1952 if (!newPool(1, false))
1954 // out of memory => try to free some memory
1955 fullcollect(false, true); // stop the world
1958 recoverNextPage(bin
);
1961 else if (usedSmallPages
> 0)
1966 recoverNextPage(bin
);
1968 // tryAlloc will succeed if a new pool was allocated above, if it fails allocate a new pool now
1969 if (!tryAlloc() && (!newPool(1, false) ||
!tryAlloc()))
1970 // out of luck or memory
1971 onOutOfMemoryErrorNoGC();
1975 // Return next item from free list
1976 bucket
[bin
] = undefinedRead((cast(List
*)p
).next
);
1977 auto pool
= undefinedRead((cast(List
*)p
).pool
);
1979 auto biti
= (p
- pool
.baseAddr
) >> pool
.shiftBy
;
1980 assert(pool
.freebits
.test(biti
));
1981 if (collectInProgress
)
1982 pool
.mark
.setLocked(biti
); // be sure that the child is aware of the page being used
1983 pool
.freebits
.clear(biti
);
1985 pool
.setBits(biti
, bits
);
1986 //debug(PRINTF) printf("\tmalloc => %p\n", p);
1987 invalidate(p
[0 .. alloc_size
], 0xF0, true);
1989 if (ConservativeGC
.isPrecise
)
1992 pool
.setPointerBitmapSmall(sentinel_add(p
), size
- SENTINEL_EXTRA
, size
- SENTINEL_EXTRA
, bits
, ti
);
1994 pool
.setPointerBitmapSmall(p
, size
, alloc_size
, bits
, ti
);
2000 * Allocate a chunk of memory that is larger than a page.
2001 * Return null if out of memory.
2003 void* bigAlloc(size_t size
, ref size_t alloc_size
, uint bits
, const TypeInfo ti
= null) nothrow
2005 debug(PRINTF
) printf("In bigAlloc. Size: %d\n", size
);
2007 LargeObjectPool
* pool
;
2009 immutable npages
= LargeObjectPool
.numPages(size
);
2010 if (npages
== size_t
.max
)
2011 onOutOfMemoryErrorNoGC(); // size just below size_t.max requested
2013 bool tryAlloc() nothrow
2015 foreach (p
; this.pooltable
[])
2017 if (!p
.isLargeObject || p
.freepages
< npages
)
2019 auto lpool
= cast(LargeObjectPool
*) p
;
2020 if ((pn
= lpool
.allocPages(npages
)) == OPFAIL
)
2028 bool tryAllocNewPool() nothrow
2030 pool
= cast(LargeObjectPool
*) newPool(npages
, true);
2031 if (!pool
) return false;
2032 pn
= pool
.allocPages(npages
);
2033 assert(pn
!= OPFAIL
);
2039 if (!lowMem
&& (disabled || usedLargePages
< largeCollectThreshold
))
2041 // disabled or threshold not reached => allocate a new pool instead of collecting
2042 if (!tryAllocNewPool())
2044 // disabled but out of memory => try to free some memory
2045 minimizeAfterNextCollection
= true;
2046 fullcollect(false, true);
2049 else if (usedLargePages
> 0)
2051 minimizeAfterNextCollection
= true;
2054 // If alloc didn't yet succeed retry now that we collected/minimized
2055 if (!pool
&& !tryAlloc() && !tryAllocNewPool())
2056 // out of luck or memory
2061 debug(PRINTF
) printFreeInfo(&pool
.base
);
2062 if (collectInProgress
)
2063 pool
.mark
.setLocked(pn
);
2064 usedLargePages
+= npages
;
2066 debug(PRINTF
) printFreeInfo(&pool
.base
);
2068 auto p
= pool
.baseAddr
+ pn
* PAGESIZE
;
2069 debug(PRINTF
) printf("Got large alloc: %p, pt = %d, np = %d\n", p
, pool
.pagetable
[pn
], npages
);
2070 invalidate(p
[0 .. size
], 0xF1, true);
2071 alloc_size
= npages
* PAGESIZE
;
2072 //debug(PRINTF) printf("\tp = %p\n", p);
2075 pool
.setBits(pn
, bits
);
2077 if (ConservativeGC
.isPrecise
)
2079 // an array of classes is in fact an array of pointers
2080 immutable(void)* rtinfo
;
2082 rtinfo
= rtinfoHasPointers
;
2083 else if ((bits
& BlkAttr
.APPENDABLE
) && (typeid(ti
) is typeid(TypeInfo_Class
)))
2084 rtinfo
= rtinfoHasPointers
;
2086 rtinfo
= ti
.rtInfo();
2087 pool
.rtinfo
[pn
] = cast(immutable(size_t
)*)rtinfo
;
2095 * Allocate a new pool with at least npages in it.
2096 * Sort it into pooltable[].
2097 * Return null if failed.
2099 Pool
*newPool(size_t npages
, bool isLargeObject
) nothrow
2101 //debug(PRINTF) printf("************Gcx::newPool(npages = %d)****************\n", npages);
2103 // Minimum of POOLSIZE
2104 size_t minPages
= config
.minPoolSize
/ PAGESIZE
;
2105 if (npages
< minPages
)
2107 else if (npages
> minPages
)
2108 { // Give us 150% of requested size, so there's room to extend
2109 auto n
= npages
+ (npages
>> 1);
2110 if (n
< size_t
.max
/PAGESIZE
)
2114 // Allocate successively larger pools up to 8 megs
2115 if (this.pooltable
.length
)
2119 n
= config
.minPoolSize
+ config
.incPoolSize
* this.pooltable
.length
;
2120 if (n
> config
.maxPoolSize
)
2121 n
= config
.maxPoolSize
; // cap pool size
2122 n
/= PAGESIZE
; // convert bytes to pages
2127 //printf("npages = %d\n", npages);
2129 auto pool
= cast(Pool
*)cstdlib
.calloc(1, isLargeObject ? LargeObjectPool
.sizeof
: SmallObjectPool
.sizeof
);
2132 pool
.initialize(npages
, isLargeObject
);
2133 if (collectInProgress
)
2135 if (!pool
.baseAddr ||
!pooltable
.insert(pool
))
2143 mappedPages
+= npages
;
2147 if (cast(size_t
)mappedPages
* PAGESIZE
> maxPoolMemory
)
2148 maxPoolMemory
= cast(size_t
)mappedPages
* PAGESIZE
;
2154 * Allocate a page of bin's.
2156 * head of a single linked list of new entries
2158 List
* allocPage(Bins bin
) nothrow
2160 //debug(PRINTF) printf("Gcx::allocPage(bin = %d)\n", bin);
2161 foreach (Pool
* pool
; this.pooltable
[])
2163 if (pool
.isLargeObject
)
2165 if (List
* p
= (cast(SmallObjectPool
*)pool
).allocPage(bin
))
2174 static struct ScanRange(bool precise
)
2180 void** pbase
; // start of memory described by ptrbitmap
2181 size_t
* ptrbmp
; // bits from is_pointer or rtinfo
2182 size_t bmplength
; // number of valid bits
2186 static struct ToScanStack(RANGE
)
2189 @disable this(this);
2190 auto stackLock
= shared(AlignedSpinLock
)(SpinLock
.Contention
.brief
);
2197 os_mem_unmap(_p
, _cap
* RANGE
.sizeof
);
2207 void push(RANGE rng
)
2209 if (_length
== _cap
) grow();
2210 _p
[_length
++] = rng
;
2214 in { assert(!empty
); }
2217 return _p
[--_length
];
2220 bool popLocked(ref RANGE rng
)
2226 scope(exit
) stackLock
.unlock();
2229 rng
= _p
[--_length
];
2233 ref inout(RANGE
) opIndex(size_t idx
) inout
2234 in { assert(idx
< _length
); }
2240 @property size_t
length() const { return _length
; }
2241 @property bool empty() const { return !length
; }
2246 pragma(inline
, false);
2248 enum initSize
= 64 * 1024; // Windows VirtualAlloc granularity
2249 immutable ncap
= _cap ?
2 * _cap
: initSize
/ RANGE
.sizeof
;
2250 auto p
= cast(RANGE
*)os_mem_map(ncap
* RANGE
.sizeof
);
2251 if (p
is null) onOutOfMemoryErrorNoGC();
2252 debug (VALGRIND
) makeMemUndefined(p
[0..ncap
]);
2255 p
[0 .. _length
] = _p
[0 .. _length
];
2256 os_mem_unmap(_p
, _cap
* RANGE
.sizeof
);
2267 ToScanStack
!(ScanRange
!false) toscanConservative
;
2268 ToScanStack
!(ScanRange
!true) toscanPrecise
;
2270 template scanStack(bool precise
)
2273 alias scanStack
= toscanPrecise
;
2275 alias scanStack
= toscanConservative
;
2279 * Search a range of memory values and mark any pointers into the GC pool.
2281 private void mark(bool precise
, bool parallel
, bool shared_mem
)(ScanRange
!precise rng
) scope nothrow
2283 alias toscan
= scanStack
!precise
;
2286 printf("marking range: [%p..%p] (%#llx)\n", pbot
, ptop
, cast(long)(ptop
- pbot
));
2288 // limit the amount of ranges added to the toscan stack
2289 enum FANOUT_LIMIT
= 32;
2291 ScanRange
!precise
[FANOUT_LIMIT
] stack
= void;
2295 // let dmd allocate a register for this.pools
2296 auto pools
= pooltable
.pools
;
2297 const highpool
= pooltable
.length
- 1;
2298 const minAddr
= pooltable
.minAddr
;
2299 size_t memSize
= pooltable
.maxAddr
- minAddr
;
2302 // properties of allocation pointed to
2303 ScanRange
!precise tgt
= void;
2307 auto p
= undefinedRead(*cast(void**)(rng
.pbot
));
2308 debug (VALGRIND
) makeMemDefined((&p
)[0 .. 1]);
2310 debug(MARK_PRINTF
) printf("\tmark %p: %p\n", rng
.pbot
, p
);
2312 if (cast(size_t
)(p
- minAddr
) < memSize
&&
2313 (cast(size_t
)p
& ~cast(size_t
)(PAGESIZE
-1)) != pcache
)
2315 static if (precise
) if (rng
.pbase
)
2317 size_t bitpos
= cast(void**)rng
.pbot
- rng
.pbase
;
2318 while (bitpos
>= rng
.bmplength
)
2320 bitpos
-= rng
.bmplength
;
2321 rng
.pbase
+= rng
.bmplength
;
2323 if (!core
.bitop
.bt(rng
.ptrbmp
, bitpos
))
2325 debug(MARK_PRINTF
) printf("\t\tskipping non-pointer\n");
2330 if (!pool || p
< pool
.baseAddr || p
>= pool
.topAddr
)
2333 size_t high
= highpool
;
2336 size_t mid
= (low
+ high
) >> 1;
2338 if (p
< pool
.baseAddr
)
2340 else if (p
>= pool
.topAddr
)
2348 size_t offset
= cast(size_t
)(p
- pool
.baseAddr
);
2350 size_t pn
= offset
/ PAGESIZE
;
2351 size_t bin
= pool
.pagetable
[pn
]; // not Bins to avoid multiple size extension instructions
2354 printf("\t\tfound pool %p, base=%p, pn = %lld, bin = %d\n", pool
, pool
.baseAddr
, cast(long)pn
, bin
);
2356 // Adjust bit to be at start of allocated memory block
2357 if (bin
< Bins
.B_PAGE
)
2359 // We don't care abou setting pointsToBase correctly
2360 // because it's ignored for small object pools anyhow.
2361 auto offsetBase
= baseOffset(offset
, cast(Bins
)bin
);
2362 biti
= offsetBase
>> Pool
.ShiftBy
.Small
;
2363 //debug(PRINTF) printf("\t\tbiti = x%x\n", biti);
2365 if (!pool
.mark
.testAndSet
!shared_mem(biti
) && !pool
.noscan
.test(biti
))
2367 tgt
.pbot
= pool
.baseAddr
+ offsetBase
;
2368 tgt
.ptop
= tgt
.pbot
+ binsize
[bin
];
2371 tgt
.pbase
= cast(void**)pool
.baseAddr
;
2372 tgt
.ptrbmp
= pool
.is_pointer
.data
;
2373 tgt
.bmplength
= size_t
.max
; // no repetition
2378 else if (bin
== Bins
.B_PAGE
)
2380 biti
= offset
>> Pool
.ShiftBy
.Large
;
2381 //debug(PRINTF) printf("\t\tbiti = x%x\n", biti);
2383 pcache
= cast(size_t
)p
& ~cast(size_t
)(PAGESIZE
-1);
2384 tgt
.pbot
= cast(void*)pcache
;
2386 // For the NO_INTERIOR attribute. This tracks whether
2387 // the pointer is an interior pointer or points to the
2388 // base address of a block.
2389 if (tgt
.pbot
!= sentinel_sub(p
) && pool
.nointerior
.nbits
&& pool
.nointerior
.test(biti
))
2392 if (!pool
.mark
.testAndSet
!shared_mem(biti
) && !pool
.noscan
.test(biti
))
2394 tgt
.ptop
= tgt
.pbot
+ (cast(LargeObjectPool
*)pool
).getSize(pn
);
2395 goto LaddLargeRange
;
2398 else if (bin
== Bins
.B_PAGEPLUS
)
2400 pn
-= pool
.bPageOffsets
[pn
];
2401 biti
= pn
* (PAGESIZE
>> Pool
.ShiftBy
.Large
);
2403 pcache
= cast(size_t
)p
& ~cast(size_t
)(PAGESIZE
-1);
2404 if (pool
.nointerior
.nbits
&& pool
.nointerior
.test(biti
))
2407 if (!pool
.mark
.testAndSet
!shared_mem(biti
) && !pool
.noscan
.test(biti
))
2409 tgt
.pbot
= pool
.baseAddr
+ (pn
* PAGESIZE
);
2410 tgt
.ptop
= tgt
.pbot
+ (cast(LargeObjectPool
*)pool
).getSize(pn
);
2414 auto rtinfo
= pool
.rtinfo
[biti
];
2415 if (rtinfo
is rtinfoNoPointers
)
2416 goto LnextPtr
; // only if inconsistent with noscan
2417 if (rtinfo
is rtinfoHasPointers
)
2419 tgt
.pbase
= null; // conservative
2423 tgt
.ptrbmp
= cast(size_t
*)rtinfo
;
2424 size_t element_size
= *tgt
.ptrbmp
++;
2425 tgt
.bmplength
= (element_size
+ (void*).sizeof
- 1) / (void*).sizeof
;
2426 assert(tgt
.bmplength
);
2429 tgt
.pbot
= sentinel_add(tgt
.pbot
);
2430 if (pool
.appendable
.test(biti
))
2432 // take advantage of knowing array layout in rt.lifetime
2433 void* arrtop
= tgt
.pbot
+ 16 + *cast(size_t
*)tgt
.pbot
;
2434 assert (arrtop
> tgt
.pbot
&& arrtop
<= tgt
.ptop
);
2440 tgt
.ptop
= tgt
.pbot
+ element_size
;
2442 tgt
.pbase
= cast(void**)tgt
.pbot
;
2450 // Don't mark bits in B_FREE pages
2451 assert(bin
== Bins
.B_FREE
);
2455 rng
.pbot
+= (void*).sizeof
;
2456 if (rng
.pbot
< rng
.ptop
)
2462 // pop range from local stack and recurse
2463 rng
= stack
[--stackPos
];
2467 static if (parallel
)
2469 if (!toscan
.popLocked(rng
))
2470 break; // nothing more to do
2475 break; // nothing more to do
2477 // pop range from global stack and recurse
2481 // printf(" pop [%p..%p] (%#zx)\n", p1, p2, cast(size_t)p2 - cast(size_t)p1);
2485 rng
.pbot
+= (void*).sizeof
;
2486 if (rng
.pbot
< rng
.ptop
)
2488 if (stackPos
< stack
.length
)
2490 stack
[stackPos
] = tgt
;
2494 static if (parallel
)
2496 toscan
.stackLock
.lock();
2497 scope(exit
) toscan
.stackLock
.unlock();
2500 // reverse order for depth-first-order traversal
2501 foreach_reverse (ref range
; stack
)
2506 // continue with last found range
2514 void markConservative(bool shared_mem
)(void *pbot
, void *ptop
) scope nothrow
2517 mark
!(false, false, shared_mem
)(ScanRange
!false(pbot
, ptop
));
2520 void markPrecise(bool shared_mem
)(void *pbot
, void *ptop
) scope nothrow
2523 mark
!(true, false, shared_mem
)(ScanRange
!true(pbot
, ptop
, null));
2526 version (COLLECT_PARALLEL
)
2527 ToScanStack
!(void*) toscanRoots
;
2529 version (COLLECT_PARALLEL
)
2530 void collectRoots(void *pbot
, void *ptop
) scope nothrow
2532 const minAddr
= pooltable
.minAddr
;
2533 size_t memSize
= pooltable
.maxAddr
- minAddr
;
2535 for (auto p
= cast(void**)pbot
; cast(void*)p
< ptop
; p
++)
2538 debug (VALGRIND
) makeMemDefined((&ptr
)[0 .. 1]);
2539 if (cast(size_t
)(ptr
- minAddr
) < memSize
)
2540 toscanRoots
.push(ptr
);
2544 // collection step 1: prepare freebits and mark bits
2545 void prepare() nothrow
2547 debug(COLLECT_PRINTF
) printf("preparing mark.\n");
2549 foreach (Pool
* pool
; this.pooltable
[])
2551 if (pool
.isLargeObject
)
2554 pool
.mark
.copy(&pool
.freebits
);
2558 // collection step 2: mark roots and heap
2559 void markAll(alias markFn
)(bool nostack
) nothrow
2563 debug(COLLECT_PRINTF
) printf("\tscan stacks.\n");
2564 // Scan stacks and registers for each paused thread
2565 thread_scanAll(&markFn
);
2569 debug(COLLECT_PRINTF
) printf("\tscan roots[]\n");
2570 foreach (root
; roots
)
2572 markFn(cast(void*)&root
.proot
, cast(void*)(&root
.proot
+ 1));
2576 debug(COLLECT_PRINTF
) printf("\tscan ranges[]\n");
2578 foreach (range
; ranges
)
2580 debug(COLLECT_PRINTF
) printf("\t\t%p .. %p\n", range
.pbot
, range
.ptop
);
2581 markFn(range
.pbot
, range
.ptop
);
2586 version (COLLECT_PARALLEL
)
2587 void collectAllRoots(bool nostack
) nothrow
2591 debug(COLLECT_PRINTF
) printf("\tcollect stacks.\n");
2592 // Scan stacks and registers for each paused thread
2593 thread_scanAll(&collectRoots
);
2597 debug(COLLECT_PRINTF
) printf("\tcollect roots[]\n");
2598 foreach (root
; roots
)
2600 toscanRoots
.push(root
);
2604 debug(COLLECT_PRINTF
) printf("\tcollect ranges[]\n");
2605 foreach (range
; ranges
)
2607 debug(COLLECT_PRINTF
) printf("\t\t%p .. %p\n", range
.pbot
, range
.ptop
);
2608 collectRoots(range
.pbot
, range
.ptop
);
2612 // collection step 3: finalize unreferenced objects, recover full pages with no live objects
2613 size_t
sweep() nothrow
2615 // Free up everything not marked
2616 debug(COLLECT_PRINTF
) printf("\tfree'ing\n");
2617 size_t freedLargePages
;
2618 size_t freedSmallPages
;
2620 foreach (Pool
* pool
; this.pooltable
[])
2624 if (pool
.isLargeObject
)
2626 auto lpool
= cast(LargeObjectPool
*)pool
;
2629 for (pn
= 0; pn
< pool
.npages
; pn
+= npages
)
2631 npages
= pool
.bPageOffsets
[pn
];
2632 Bins bin
= cast(Bins
)pool
.pagetable
[pn
];
2633 if (bin
== Bins
.B_FREE
)
2638 assert(bin
== Bins
.B_PAGE
);
2641 if (!pool
.mark
.test(biti
))
2643 void *p
= pool
.baseAddr
+ pn
* PAGESIZE
;
2644 void* q
= sentinel_add(p
);
2645 sentinel_Invariant(q
);
2647 if (pool
.finals
.nbits
&& pool
.finals
.clear(biti
))
2649 size_t size
= npages
* PAGESIZE
- SENTINEL_EXTRA
;
2650 uint attr
= pool
.getBits(biti
);
2651 rt_finalizeFromGC(q
, sentinel_size(q
, size
), attr
);
2654 pool
.clrBits(biti
, ~BlkAttr
.NONE ^ BlkAttr
.FINALIZE
);
2656 debug(COLLECT_PRINTF
) printf("\tcollecting big %p\n", p
);
2657 leakDetector
.log_free(q
, sentinel_size(q
, npages
* PAGESIZE
- SENTINEL_EXTRA
));
2658 pool
.pagetable
[pn
..pn
+npages
] = Bins
.B_FREE
;
2659 if (pn
< pool
.searchStart
) pool
.searchStart
= pn
;
2660 freedLargePages
+= npages
;
2661 pool
.freepages
+= npages
;
2664 invalidate(p
[0 .. npages
* PAGESIZE
], 0xF3, false);
2665 // Don't need to update searchStart here because
2666 // pn is guaranteed to be greater than last time
2669 pool
.largestFree
= pool
.freepages
; // invalidate
2675 lpool
.setFreePageOffsets(pn
- numFree
, numFree
);
2681 lpool
.setFreePageOffsets(pn
- numFree
, numFree
);
2685 // reinit chain of pages to rebuild free list
2686 pool
.recoverPageFirst
[] = cast(uint)pool
.npages
;
2688 for (pn
= 0; pn
< pool
.npages
; pn
++)
2690 Bins bin
= cast(Bins
)pool
.pagetable
[pn
];
2692 if (bin
< Bins
.B_PAGE
)
2694 auto freebitsdata
= pool
.freebits
.data
+ pn
* PageBits
.length
;
2695 auto markdata
= pool
.mark
.data
+ pn
* PageBits
.length
;
2697 // the entries to free are allocated objects (freebits == false)
2698 // that are not marked (mark == false)
2700 static foreach (w
; 0 .. PageBits
.length
)
2701 toFree
[w
] = (~freebitsdata
[w
] & ~markdata
[w
]);
2703 // the page is unchanged if there is nothing to free
2704 bool unchanged
= true;
2705 static foreach (w
; 0 .. PageBits
.length
)
2706 unchanged
= unchanged
&& (toFree
[w
] == 0);
2709 bool hasDead
= false;
2710 static foreach (w
; 0 .. PageBits
.length
)
2711 hasDead
= hasDead ||
(~freebitsdata
[w
] != baseOffsetBits
[bin
][w
]);
2714 // add to recover chain
2715 pool
.binPageChain
[pn
] = pool
.recoverPageFirst
[bin
];
2716 pool
.recoverPageFirst
[bin
] = cast(uint)pn
;
2720 pool
.binPageChain
[pn
] = Pool
.PageRecovered
;
2725 // the page can be recovered if all of the allocated objects (freebits == false)
2727 bool recoverPage
= true;
2728 static foreach (w
; 0 .. PageBits
.length
)
2729 recoverPage
= recoverPage
&& (~freebitsdata
[w
] == toFree
[w
]);
2731 // We need to loop through each object if any have a finalizer,
2732 // or, if any of the debug hooks are enabled.
2733 bool doLoop
= false;
2736 else version (assert)
2738 else debug (COLLECT_PRINTF
) // need output for each object
2740 else debug (LOGGING
)
2742 else debug (MEMSTOMP
)
2744 else if (pool
.finals
.data
)
2746 // finalizers must be called on objects that are about to be freed
2747 auto finalsdata
= pool
.finals
.data
+ pn
* PageBits
.length
;
2748 static foreach (w
; 0 .. PageBits
.length
)
2749 doLoop
= doLoop ||
(toFree
[w
] & finalsdata
[w
]) != 0;
2754 immutable size
= binsize
[bin
];
2755 void *p
= pool
.baseAddr
+ pn
* PAGESIZE
;
2756 immutable base
= pn
* (PAGESIZE
/16);
2757 immutable bitstride
= size
/ 16;
2759 // ensure that there are at least <size> bytes for every address
2760 // below ptop even if unaligned
2761 void *ptop
= p
+ PAGESIZE
- size
+ 1;
2762 for (size_t i
; p
< ptop
; p
+= size
, i
+= bitstride
)
2764 immutable biti
= base
+ i
;
2766 if (!pool
.mark
.test(biti
))
2768 void* q
= sentinel_add(p
);
2769 sentinel_Invariant(q
);
2771 if (pool
.finals
.nbits
&& pool
.finals
.test(biti
))
2772 rt_finalizeFromGC(q
, sentinel_size(q
, size
), pool
.getBits(biti
));
2774 assert(core
.bitop
.bt(toFree
.ptr
, i
));
2776 debug(COLLECT_PRINTF
) printf("\tcollecting %p\n", p
);
2777 leakDetector
.log_free(q
, sentinel_size(q
, size
));
2779 invalidate(p
[0 .. size
], 0xF3, false);
2786 pool
.freeAllPageBits(pn
);
2788 pool
.pagetable
[pn
] = Bins
.B_FREE
;
2789 // add to free chain
2790 pool
.binPageChain
[pn
] = cast(uint) pool
.searchStart
;
2791 pool
.searchStart
= pn
;
2797 pool
.freePageBits(pn
, toFree
);
2799 // add to recover chain
2800 pool
.binPageChain
[pn
] = pool
.recoverPageFirst
[bin
];
2801 pool
.recoverPageFirst
[bin
] = cast(uint)pn
;
2808 assert(freedLargePages
<= usedLargePages
);
2809 usedLargePages
-= freedLargePages
;
2810 debug(COLLECT_PRINTF
) printf("\tfree'd %u bytes, %u pages from %u pools\n",
2811 freed
, freedLargePages
, this.pooltable
.length
);
2813 assert(freedSmallPages
<= usedSmallPages
);
2814 usedSmallPages
-= freedSmallPages
;
2815 debug(COLLECT_PRINTF
) printf("\trecovered small pages = %d\n", freedSmallPages
);
2817 return freedLargePages
+ freedSmallPages
;
2820 bool recoverPage(SmallObjectPool
* pool
, size_t pn
, Bins bin
) nothrow
2822 size_t size
= binsize
[bin
];
2823 size_t bitbase
= pn
* (PAGESIZE
/ 16);
2825 auto freebitsdata
= pool
.freebits
.data
+ pn
* PageBits
.length
;
2827 // the page had dead objects when collecting, these cannot have been resurrected
2828 bool hasDead
= false;
2829 static foreach (w
; 0 .. PageBits
.length
)
2830 hasDead
= hasDead ||
(freebitsdata
[w
] != 0);
2833 // prepend to buckets, but with forward addresses inside the page
2834 assert(bucket
[bin
] is null);
2835 List
** bucketTail
= &bucket
[bin
];
2837 void* p
= pool
.baseAddr
+ pn
* PAGESIZE
;
2838 const top
= PAGESIZE
- size
+ 1; // ensure <size> bytes available even if unaligned
2839 for (size_t u
= 0; u
< top
; u
+= size
)
2841 if (!core
.bitop
.bt(freebitsdata
, u
/ 16))
2843 auto elem
= cast(List
*)(p
+ u
);
2844 undefinedWrite(elem
.pool
, &pool
.base
);
2845 undefinedWrite(*bucketTail
, elem
);
2846 bucketTail
= &elem
.next
;
2848 undefinedWrite(*bucketTail
, null);
2849 assert(bucket
[bin
] !is null);
2853 bool recoverNextPage(Bins bin
) nothrow
2855 SmallObjectPool
* pool
= recoverPool
[bin
];
2858 auto pn
= pool
.recoverPageFirst
[bin
];
2859 while (pn
< pool
.npages
)
2861 auto next
= pool
.binPageChain
[pn
];
2862 pool
.binPageChain
[pn
] = Pool
.PageRecovered
;
2863 pool
.recoverPageFirst
[bin
] = next
;
2864 if (recoverPage(pool
, pn
, bin
))
2868 pool
= setNextRecoverPool(bin
, pool
.ptIndex
+ 1);
2873 private SmallObjectPool
* setNextRecoverPool(Bins bin
, size_t poolIndex
) nothrow
2876 while (poolIndex
< this.pooltable
.length
&&
2877 ((pool
= this.pooltable
[poolIndex
]).isLargeObject ||
2878 pool
.recoverPageFirst
[bin
] >= pool
.npages
))
2881 return recoverPool
[bin
] = poolIndex
< this.pooltable
.length ?
cast(SmallObjectPool
*)pool
: null;
2884 version (COLLECT_FORK
)
2885 void disableFork() nothrow
2891 version (COLLECT_FORK
)
2892 ChildStatus
collectFork(bool block
) nothrow
2894 typeof(return) rc
= wait_pid(markProcPid
, block
);
2897 case ChildStatus
.done
:
2898 debug(COLLECT_PRINTF
) printf("\t\tmark proc DONE (block=%d)\n",
2901 // process GC marks then sweep
2902 thread_suspendAll();
2903 thread_processGCMarks(&isMarked
);
2906 case ChildStatus
.running
:
2907 debug(COLLECT_PRINTF
) printf("\t\tmark proc RUNNING\n");
2910 // Something went wrong, if block is true, wait() should never
2912 goto case ChildStatus
.error
;
2913 case ChildStatus
.error
:
2914 debug(COLLECT_PRINTF
) printf("\t\tmark proc ERROR\n");
2915 // Try to keep going without forking
2916 // and do the marking in this thread
2922 version (COLLECT_FORK
)
2923 ChildStatus
markFork(bool nostack
, bool block
, bool doParallel
) nothrow
2925 // Forking is enabled, so we fork() and start a new concurrent mark phase
2926 // in the child. If the collection should not block, the parent process
2927 // tells the caller no memory could be recycled immediately (if this collection
2928 // was triggered by an allocation, the caller should allocate more memory
2929 // to fulfill the request).
2930 // If the collection should block, the parent will wait for the mark phase
2931 // to finish before returning control to the mutator,
2932 // but other threads are restarted and may run in parallel with the mark phase
2933 // (unless they allocate or use the GC themselves, in which case
2934 // the global GC lock will stop them).
2935 // fork now and sweep later
2936 int child_mark() scope
2939 markParallel(nostack
);
2940 else if (ConservativeGC
.isPrecise
)
2941 markAll
!(markPrecise
!true)(nostack
);
2943 markAll
!(markConservative
!true)(nostack
);
2947 import core
.stdc
.stdlib
: _Exit
;
2948 debug (PRINTF_TO_FILE
)
2950 fflush(null); // avoid duplicated FILE* output
2954 auto pid
= __fork(); // avoids calling handlers (from libc source code)
2956 else version (linux
)
2958 // clone() fits better as we don't want to do anything but scanning in the child process.
2959 // no fork-handlers are called, so we can avoid deadlocks due to malloc locks. Probably related:
2960 // https://sourceware.org/bugzilla/show_bug.cgi?id=4737
2961 import core
.sys
.linux
.sched
: clone
;
2962 import core
.sys
.posix
.signal
: SIGCHLD
;
2963 const flags
= SIGCHLD
; // exit signal
2964 scope int delegate() scope dg
= &child_mark
;
2965 extern(C
) static int wrap_delegate(void* arg
)
2967 auto dg
= cast(int delegate() scope*)arg
;
2970 ubyte[256] stackbuf
; // enough stack space for clone() to place some info for the child without stomping the parent stack
2971 auto stack
= stackbuf
.ptr
+ (isStackGrowingDown ? stackbuf
.length
: 0);
2972 auto pid
= clone(&wrap_delegate
, stack
, flags
, &dg
);
2976 fork_needs_lock
= false;
2978 fork_needs_lock
= true;
2982 case -1: // fork() failed, retry without forking
2983 return ChildStatus
.error
;
2984 case 0: // child process (not run with clone)
2987 default: // the parent
2992 return ChildStatus
.running
;
2994 ChildStatus r
= wait_pid(pid
); // block until marking is done
2995 if (r
== ChildStatus
.error
)
2997 thread_suspendAll();
2998 // there was an error
2999 // do the marking in this thread
3002 markParallel(nostack
);
3003 else if (ConservativeGC
.isPrecise
)
3004 markAll
!(markPrecise
!false)(nostack
);
3006 markAll
!(markConservative
!false)(nostack
);
3008 assert(r
== ChildStatus
.done
);
3009 assert(r
!= ChildStatus
.running
);
3012 return ChildStatus
.done
; // waited for the child
3016 * Return number of full pages free'd.
3017 * The collection is done concurrently only if block and isFinal are false.
3019 size_t
fullcollect(bool nostack
= false, bool block
= false, bool isFinal
= false) nothrow
3021 // It is possible that `fullcollect` will be called from a thread which
3022 // is not yet registered in runtime (because allocating `new Thread` is
3023 // part of `thread_attachThis` implementation). In that case it is
3024 // better not to try actually collecting anything
3026 if (Thread
.getThis() is null)
3029 MonoTime start
, stop
, begin
;
3030 begin
= start
= currTime
;
3032 debug(COLLECT_PRINTF
) printf("Gcx.fullcollect()\n");
3033 version (COLLECT_PARALLEL
)
3035 bool doParallel
= config
.parallel
> 0 && !config
.fork
;
3036 if (doParallel
&& !scanThreadData
)
3038 if (isFinal
) // avoid starting threads for parallel marking
3045 enum doParallel
= false;
3047 //printf("\tpool address range = %p .. %p\n", minAddr, maxAddr);
3049 version (COLLECT_FORK
)
3050 alias doFork
= shouldFork
;
3052 enum doFork
= false;
3054 if (doFork
&& collectInProgress
)
3056 version (COLLECT_FORK
)
3058 // If there is a mark process running, check if it already finished.
3059 // If that is the case, we move to the sweep phase.
3060 // If it's still running, either we block until the mark phase is
3061 // done (and then sweep to finish the collection), or in case of error
3062 // we redo the mark phase without forking.
3063 ChildStatus rc
= collectFork(block
);
3066 case ChildStatus
.done
:
3068 case ChildStatus
.running
:
3070 case ChildStatus
.error
:
3079 // lock roots and ranges around suspending threads b/c they're not reentrant safe
3082 debug(INVARIANT
) inCollection
= true;
3085 debug(INVARIANT
) inCollection
= false;
3086 rangesLock
.unlock();
3089 thread_suspendAll();
3094 prepTime
+= (stop
- start
);
3097 if (doFork
&& !isFinal
&& !block
) // don't start a new fork during termination
3099 version (COLLECT_FORK
)
3101 auto forkResult
= markFork(nostack
, block
, doParallel
);
3102 final switch (forkResult
)
3104 case ChildStatus
.error
:
3105 // fork() failed, retry without forking
3108 case ChildStatus
.running
:
3109 // update profiling informations
3111 markTime
+= (stop
- start
);
3112 Duration pause
= stop
- begin
;
3113 if (pause
> maxPauseTime
)
3114 maxPauseTime
= pause
;
3117 case ChildStatus
.done
:
3120 // if we get here, forking failed and a standard STW collection got issued
3121 // threads were suspended again, restart them
3122 thread_suspendAll();
3125 else if (doParallel
)
3127 version (COLLECT_PARALLEL
)
3128 markParallel(nostack
);
3132 if (ConservativeGC
.isPrecise
)
3133 markAll
!(markPrecise
!false)(nostack
);
3135 markAll
!(markConservative
!false)(nostack
);
3138 thread_processGCMarks(&isMarked
);
3143 // If we get here with the forking GC, the child process has finished the marking phase
3144 // or block == true and we are using standard stop the world collection.
3145 // It is time to sweep
3148 markTime
+= (stop
- start
);
3149 Duration pause
= stop
- begin
;
3150 if (pause
> maxPauseTime
)
3151 maxPauseTime
= pause
;
3155 ConservativeGC
._inFinalizer
= true;
3156 size_t freedPages
= void;
3158 scope (failure
) ConservativeGC
._inFinalizer
= false;
3159 freedPages
= sweep();
3160 ConservativeGC
._inFinalizer
= false;
3163 // minimize() should be called only after a call to fullcollect
3164 // terminates with a sweep
3165 if (minimizeAfterNextCollection || lowMem
)
3167 minimizeAfterNextCollection
= false;
3171 // init bucket lists
3173 foreach (Bins bin
; Bins
.B_16
.. Bins
.B_NUMSMALL
)
3174 setNextRecoverPool(bin
, 0);
3177 sweepTime
+= (stop
- start
);
3179 Duration collectionTime
= stop
- begin
;
3180 if (collectionTime
> maxCollectionTime
)
3181 maxCollectionTime
= collectionTime
;
3185 updateCollectThresholds();
3186 if (doFork
&& isFinal
)
3187 return fullcollect(true, true, false);
3192 * Returns true if the addr lies within a marked block.
3194 * Warning! This should only be called while the world is stopped inside
3195 * the fullcollect function after all live objects have been marked, but before sweeping.
3197 int isMarked(void *addr
) scope nothrow
3199 // first, we find the Pool this block is in, then check to see if the
3200 // mark bit is clear.
3201 auto pool
= findPool(addr
);
3204 auto offset
= cast(size_t
)(addr
- pool
.baseAddr
);
3205 auto pn
= offset
/ PAGESIZE
;
3206 auto bins
= cast(Bins
)pool
.pagetable
[pn
];
3208 if (bins
< Bins
.B_PAGE
)
3210 biti
= baseOffset(offset
, bins
) >> pool
.ShiftBy
.Small
;
3211 // doesn't need to check freebits because no pointer must exist
3212 // to a block that was free before starting the collection
3214 else if (bins
== Bins
.B_PAGE
)
3216 biti
= pn
* (PAGESIZE
>> pool
.ShiftBy
.Large
);
3218 else if (bins
== Bins
.B_PAGEPLUS
)
3220 pn
-= pool
.bPageOffsets
[pn
];
3221 biti
= pn
* (PAGESIZE
>> pool
.ShiftBy
.Large
);
3223 else // bins == Bins.B_FREE
3225 assert(bins
== Bins
.B_FREE
);
3228 return pool
.mark
.test(biti
) ? IsMarked
.yes
: IsMarked
.no
;
3230 return IsMarked
.unknown
;
3235 // A fork might happen while GC code is running in a different thread.
3236 // Because that would leave the GC in an inconsistent state,
3237 // make sure no GC code is running by acquiring the lock here,
3239 // This must not happen if fork is called from the GC with the lock already held
3241 __gshared
bool fork_needs_lock
= true; // racing condition with cocurrent calls of fork?
3244 extern(C
) static void _d_gcx_atfork_prepare()
3246 if (instance
&& fork_needs_lock
)
3247 ConservativeGC
.lockNR();
3250 extern(C
) static void _d_gcx_atfork_parent()
3252 if (instance
&& fork_needs_lock
)
3253 ConservativeGC
.gcLock
.unlock();
3256 extern(C
) static void _d_gcx_atfork_child()
3258 if (instance
&& fork_needs_lock
)
3260 ConservativeGC
.gcLock
.unlock();
3262 // make sure the threads and event handles are reinitialized in a fork
3263 version (COLLECT_PARALLEL
)
3265 if (Gcx
.instance
.scanThreadData
)
3267 cstdlib
.free(Gcx
.instance
.scanThreadData
);
3268 Gcx
.instance
.numScanThreads
= 0;
3269 Gcx
.instance
.scanThreadData
= null;
3270 Gcx
.instance
.busyThreads
= 0;
3272 memset(&Gcx
.instance
.evStart
, 0, Gcx
.instance
.evStart
.sizeof
);
3273 memset(&Gcx
.instance
.evDone
, 0, Gcx
.instance
.evDone
.sizeof
);
3280 /* ============================ Parallel scanning =============================== */
3281 version (COLLECT_PARALLEL
):
3285 import core
.sync
.event
;
3287 private: // disable invariants for background threads
3289 static struct ScanThreadData
3293 uint numScanThreads
;
3294 ScanThreadData
* scanThreadData
;
3299 shared uint busyThreads
;
3300 shared uint stoppedThreads
;
3303 void markParallel(bool nostack
) nothrow
3305 toscanRoots
.clear();
3306 collectAllRoots(nostack
);
3307 if (toscanRoots
.empty
)
3310 void** pbot
= toscanRoots
._p
;
3311 void** ptop
= toscanRoots
._p
+ toscanRoots
._length
;
3313 debug(PARALLEL_PRINTF
) printf("markParallel\n");
3315 size_t pointersPerThread
= toscanRoots
._length
/ (numScanThreads
+ 1);
3316 if (pointersPerThread
> 0)
3318 void pushRanges(bool precise
)()
3320 alias toscan
= scanStack
!precise
;
3321 toscan
.stackLock
.lock();
3323 for (int idx
= 0; idx
< numScanThreads
; idx
++)
3325 toscan
.push(ScanRange
!precise(pbot
, pbot
+ pointersPerThread
));
3326 pbot
+= pointersPerThread
;
3328 toscan
.stackLock
.unlock();
3330 if (ConservativeGC
.isPrecise
)
3335 assert(pbot
< ptop
);
3337 busyThreads
.atomicOp
!"+="(1); // main thread is busy
3339 evStart
.setIfInitialized();
3341 debug(PARALLEL_PRINTF
) printf("mark %lld roots\n", cast(ulong)(ptop
- pbot
));
3343 if (ConservativeGC
.isPrecise
)
3344 mark
!(true, true, true)(ScanRange
!true(pbot
, ptop
, null));
3346 mark
!(false, true, true)(ScanRange
!false(pbot
, ptop
));
3348 busyThreads
.atomicOp
!"-="(1);
3350 debug(PARALLEL_PRINTF
) printf("waitForScanDone\n");
3351 pullFromScanStack();
3352 debug(PARALLEL_PRINTF
) printf("waitForScanDone done\n");
3355 int maxParallelThreads() nothrow
3357 auto threads
= threadsPerCPU();
3361 // If the GC is called by module ctors no explicit
3362 // import dependency on the GC is generated. So the
3363 // GC module is not correctly inserted into the module
3364 // initialization chain. As it relies on core.cpuid being
3365 // initialized, force this here.
3368 foreach (m
; ModuleInfo
)
3369 if (m
.name
== "core.cpuid")
3370 if (auto ctor
= m
.ctor())
3373 threads
= threadsPerCPU();
3379 assert(false, "unexpected exception iterating ModuleInfo");
3386 void startScanThreads() nothrow
3388 auto threads
= maxParallelThreads();
3389 debug(PARALLEL_PRINTF
) printf("startScanThreads: %d threads per CPU\n", threads
);
3391 return; // either core.cpuid not initialized or single core
3393 numScanThreads
= threads
>= config
.parallel ? config
.parallel
: threads
- 1;
3395 scanThreadData
= cast(ScanThreadData
*) cstdlib
.calloc(numScanThreads
, ScanThreadData
.sizeof
);
3396 if (!scanThreadData
)
3397 onOutOfMemoryErrorNoGC();
3399 evStart
.initialize(false, false);
3400 evDone
.initialize(false, false);
3404 import core
.sys
.posix
.signal
;
3405 // block all signals, scanBackground inherits this mask.
3406 // see https://issues.dlang.org/show_bug.cgi?id=20256
3407 sigset_t new_mask
, old_mask
;
3408 sigfillset(&new_mask
);
3409 auto sigmask_rc
= pthread_sigmask(SIG_BLOCK
, &new_mask
, &old_mask
);
3410 assert(sigmask_rc
== 0, "failed to set up GC scan thread sigmask");
3413 for (int idx
= 0; idx
< numScanThreads
; idx
++)
3414 scanThreadData
[idx
].tid
= createLowLevelThread(&scanBackground
, 0x4000, &stopScanThreads
);
3418 sigmask_rc
= pthread_sigmask(SIG_SETMASK
, &old_mask
, null);
3419 assert(sigmask_rc
== 0, "failed to set up GC scan thread sigmask");
3423 void stopScanThreads() nothrow
3425 if (!numScanThreads
)
3428 debug(PARALLEL_PRINTF
) printf("stopScanThreads\n");
3429 int startedThreads
= 0;
3430 for (int idx
= 0; idx
< numScanThreads
; idx
++)
3431 if (scanThreadData
[idx
].tid
!= scanThreadData
[idx
].tid
.init
)
3435 alias allThreadsDead
= thread_DLLProcessDetaching
;
3437 enum allThreadsDead
= false;
3439 while (atomicLoad(stoppedThreads
) < startedThreads
&& !allThreadsDead
)
3441 evStart
.setIfInitialized();
3442 evDone
.wait(dur
!"msecs"(1));
3445 for (int idx
= 0; idx
< numScanThreads
; idx
++)
3447 if (scanThreadData
[idx
].tid
!= scanThreadData
[idx
].tid
.init
)
3449 joinLowLevelThread(scanThreadData
[idx
].tid
);
3450 scanThreadData
[idx
].tid
= scanThreadData
[idx
].tid
.init
;
3455 evStart
.terminate();
3457 cstdlib
.free(scanThreadData
);
3458 // scanThreadData = null; // keep non-null to not start again after shutdown
3461 debug(PARALLEL_PRINTF
) printf("stopScanThreads done\n");
3464 void scanBackground() nothrow
3469 pullFromScanStack();
3470 evDone
.setIfInitialized();
3472 stoppedThreads
.atomicOp
!"+="(1);
3475 void pullFromScanStack() nothrow
3477 if (ConservativeGC
.isPrecise
)
3478 pullFromScanStackImpl
!true();
3480 pullFromScanStackImpl
!false();
3483 void pullFromScanStackImpl(bool precise
)() nothrow
3485 if (atomicLoad(busyThreads
) == 0)
3488 debug(PARALLEL_PRINTF
)
3489 pthread_t threadId
= pthread_self();
3490 debug(PARALLEL_PRINTF
) printf("scanBackground thread %d start\n", threadId
);
3492 ScanRange
!precise rng
;
3493 alias toscan
= scanStack
!precise
;
3495 while (atomicLoad(busyThreads
) > 0)
3499 evDone
.wait(dur
!"msecs"(1));
3503 busyThreads
.atomicOp
!"+="(1);
3504 if (toscan
.popLocked(rng
))
3506 debug(PARALLEL_PRINTF
) printf("scanBackground thread %d scanning range [%p,%lld] from stack\n", threadId
,
3507 rng
.pbot
, cast(long) (rng
.ptop
- rng
.pbot
));
3508 mark
!(precise
, true, true)(rng
);
3510 busyThreads
.atomicOp
!"-="(1);
3512 debug(PARALLEL_PRINTF
) printf("scanBackground thread %d done\n", threadId
);
3516 /* ============================ Pool =============================== */
3522 size_t ptIndex
; // index in pool table
3523 GCBits mark
; // entries already scanned, or should not be scanned
3524 GCBits freebits
; // entries that are on the free list (all bits set but for allocated objects at their base offset)
3525 GCBits finals
; // entries that need finalizer run on them
3526 GCBits structFinals
;// struct entries that need a finalzier run on them
3527 GCBits noscan
; // entries that should not be scanned
3528 GCBits appendable
; // entries that are appendable
3529 GCBits nointerior
; // interior pointers should be ignored.
3530 // Only implemented for large object pools.
3531 GCBits is_pointer
; // precise GC only: per-word, not per-block like the rest of them (SmallObjectPool only)
3533 size_t freepages
; // The number of pages not in use.
3543 ShiftBy shiftBy
= void; // shift count for the divisor used for determining bit indices.
3545 // This tracks how far back we have to go to find the nearest B_PAGE at
3546 // a smaller address than a B_PAGEPLUS. To save space, we use a uint.
3547 // This limits individual allocations to 16 terabytes, assuming a 4k
3548 // pagesize. (LargeObjectPool only)
3549 // For B_PAGE and B_FREE, this specifies the number of pages in this block.
3550 // As an optimization, a contiguous range of free pages tracks this information
3551 // only for the first and the last page.
3554 // The small object pool uses the same array to keep a chain of
3555 // - pages with the same bin size that are still to be recovered
3556 // - free pages (searchStart is first free page)
3557 // other pages are marked by value PageRecovered
3558 alias binPageChain
= bPageOffsets
;
3560 enum PageRecovered
= uint.max
;
3562 // first of chain of pages to recover (SmallObjectPool only)
3563 uint[Bins
.B_NUMSMALL
] recoverPageFirst
;
3565 // precise GC: TypeInfo.rtInfo for allocation (LargeObjectPool only)
3566 immutable(size_t
)** rtinfo
;
3568 // This variable tracks a conservative estimate of where the first free
3569 // page in this pool is, so that if a lot of pages towards the beginning
3570 // are occupied, we can bypass them in O(1).
3572 size_t largestFree
; // upper limit for largest free chunk in large object pool
3574 void initialize(size_t npages
, bool isLargeObject
) nothrow
3576 assert(npages
>= 256);
3578 this.isLargeObject
= isLargeObject
;
3581 shiftBy
= isLargeObject ? ShiftBy
.Large
: ShiftBy
.Small
;
3583 //debug(PRINTF) printf("Pool::Pool(%u)\n", npages);
3584 poolsize
= npages
* PAGESIZE
;
3585 baseAddr
= cast(byte *)os_mem_map(poolsize
);
3586 version (VALGRIND
) makeMemNoAccess(baseAddr
[0..poolsize
]);
3588 // Some of the code depends on page alignment of memory pools
3589 assert((cast(size_t
)baseAddr
& (PAGESIZE
- 1)) == 0);
3593 //debug(PRINTF) printf("GC fail: poolsize = x%zx, errno = %d\n", poolsize, errno);
3594 //debug(PRINTF) printf("message = '%s'\n", sys_errlist[errno]);
3600 topAddr
= baseAddr
+ poolsize
;
3601 auto nbits
= cast(size_t
)poolsize
>> shiftBy
;
3603 version (COLLECT_FORK
)
3604 mark
.alloc(nbits
, config
.fork
);
3607 if (ConservativeGC
.isPrecise
)
3611 rtinfo
= cast(immutable(size_t
)**)cstdlib
.malloc(npages
* (size_t
*).sizeof
);
3613 onOutOfMemoryErrorNoGC();
3614 memset(rtinfo
, 0, npages
* (size_t
*).sizeof
);
3618 is_pointer
.alloc(cast(size_t
)poolsize
/(void*).sizeof
);
3619 is_pointer
.clrRange(0, is_pointer
.nbits
);
3623 // pagetable already keeps track of what's free for the large object
3627 freebits
.alloc(nbits
);
3628 freebits
.setRange(0, nbits
);
3631 noscan
.alloc(nbits
);
3632 appendable
.alloc(nbits
);
3634 pagetable
= cast(Bins
*)cstdlib
.malloc(npages
* Bins
.sizeof
);
3636 onOutOfMemoryErrorNoGC();
3640 bPageOffsets
= cast(uint*)cstdlib
.malloc(npages
* uint.sizeof
);
3642 onOutOfMemoryErrorNoGC();
3646 bPageOffsets
[0] = cast(uint)npages
;
3647 bPageOffsets
[npages
-1] = cast(uint)npages
;
3652 foreach (n
; 0..npages
)
3653 binPageChain
[n
] = cast(uint)(n
+ 1);
3654 recoverPageFirst
[] = cast(uint)npages
;
3658 memset(pagetable
, Bins
.B_FREE
, npages
);
3660 this.npages
= npages
;
3661 this.freepages
= npages
;
3662 this.searchStart
= 0;
3663 this.largestFree
= npages
;
3675 result
= os_mem_unmap(baseAddr
, npages
* PAGESIZE
);
3676 assert(result
== 0);
3685 cstdlib
.free(pagetable
);
3691 cstdlib
.free(bPageOffsets
);
3692 bPageOffsets
= null;
3695 mark
.Dtor(config
.fork
);
3696 if (ConservativeGC
.isPrecise
)
3699 cstdlib
.free(rtinfo
);
3712 structFinals
.Dtor();
3720 uint getBits(size_t biti
) nothrow
3724 if (finals
.nbits
&& finals
.test(biti
))
3725 bits |
= BlkAttr
.FINALIZE
;
3726 if (structFinals
.nbits
&& structFinals
.test(biti
))
3727 bits |
= BlkAttr
.STRUCTFINAL
;
3728 if (noscan
.test(biti
))
3729 bits |
= BlkAttr
.NO_SCAN
;
3730 if (nointerior
.nbits
&& nointerior
.test(biti
))
3731 bits |
= BlkAttr
.NO_INTERIOR
;
3732 if (appendable
.test(biti
))
3733 bits |
= BlkAttr
.APPENDABLE
;
3740 void clrBits(size_t biti
, uint mask
) nothrow @nogc
3742 immutable dataIndex
= biti
>> GCBits
.BITS_SHIFT
;
3743 immutable bitOffset
= biti
& GCBits
.BITS_MASK
;
3744 immutable keep
= ~(GCBits
.BITS_1
<< bitOffset
);
3746 if (mask
& BlkAttr
.FINALIZE
&& finals
.nbits
)
3747 finals
.data
[dataIndex
] &= keep
;
3749 if (structFinals
.nbits
&& (mask
& BlkAttr
.STRUCTFINAL
))
3750 structFinals
.data
[dataIndex
] &= keep
;
3752 if (mask
& BlkAttr
.NO_SCAN
)
3753 noscan
.data
[dataIndex
] &= keep
;
3754 if (mask
& BlkAttr
.APPENDABLE
)
3755 appendable
.data
[dataIndex
] &= keep
;
3756 if (nointerior
.nbits
&& (mask
& BlkAttr
.NO_INTERIOR
))
3757 nointerior
.data
[dataIndex
] &= keep
;
3763 void setBits(size_t biti
, uint mask
) nothrow
3765 // Calculate the mask and bit offset once and then use it to
3766 // set all of the bits we need to set.
3767 immutable dataIndex
= biti
>> GCBits
.BITS_SHIFT
;
3768 immutable bitOffset
= biti
& GCBits
.BITS_MASK
;
3769 immutable orWith
= GCBits
.BITS_1
<< bitOffset
;
3771 if (mask
& BlkAttr
.STRUCTFINAL
)
3773 if (!structFinals
.nbits
)
3774 structFinals
.alloc(mark
.nbits
);
3775 structFinals
.data
[dataIndex
] |
= orWith
;
3778 if (mask
& BlkAttr
.FINALIZE
)
3781 finals
.alloc(mark
.nbits
);
3782 finals
.data
[dataIndex
] |
= orWith
;
3785 if (mask
& BlkAttr
.NO_SCAN
)
3787 noscan
.data
[dataIndex
] |
= orWith
;
3789 // if (mask & BlkAttr.NO_MOVE)
3791 // if (!nomove.nbits)
3792 // nomove.alloc(mark.nbits);
3793 // nomove.data[dataIndex] |= orWith;
3795 if (mask
& BlkAttr
.APPENDABLE
)
3797 appendable
.data
[dataIndex
] |
= orWith
;
3800 if (isLargeObject
&& (mask
& BlkAttr
.NO_INTERIOR
))
3802 if (!nointerior
.nbits
)
3803 nointerior
.alloc(mark
.nbits
);
3804 nointerior
.data
[dataIndex
] |
= orWith
;
3808 void freePageBits(size_t pagenum
, const scope ref PageBits toFree
) nothrow
3810 assert(!isLargeObject
);
3811 assert(!nointerior
.nbits
); // only for large objects
3813 import core
.internal
.traits
: staticIota
;
3814 immutable beg
= pagenum
* (PAGESIZE
/ 16 / GCBits
.BITS_PER_WORD
);
3815 foreach (i
; staticIota
!(0, PageBits
.length
))
3817 immutable w
= toFree
[i
];
3820 immutable wi
= beg
+ i
;
3821 freebits
.data
[wi
] |
= w
;
3822 noscan
.data
[wi
] &= ~w
;
3823 appendable
.data
[wi
] &= ~w
;
3828 foreach (i
; staticIota
!(0, PageBits
.length
))
3830 finals
.data
[beg
+ i
] &= ~toFree
[i
];
3833 if (structFinals
.nbits
)
3835 foreach (i
; staticIota
!(0, PageBits
.length
))
3837 structFinals
.data
[beg
+ i
] &= ~toFree
[i
];
3841 void freeAllPageBits(size_t pagenum
) nothrow
3843 assert(!isLargeObject
);
3844 assert(!nointerior
.nbits
); // only for large objects
3846 immutable beg
= pagenum
* PageBits
.length
;
3847 static foreach (i
; 0 .. PageBits
.length
)
3849 immutable w
= beg
+ i
;
3850 freebits
.data
[w
] = ~0;
3852 appendable
.data
[w
] = 0;
3855 if (structFinals
.data
)
3856 structFinals
.data
[w
] = 0;
3861 * Given a pointer p in the p, return the pagenum.
3863 size_t
pagenumOf(void *p
) const nothrow @nogc
3866 assert(p
>= baseAddr
);
3867 assert(p
< topAddr
);
3871 return cast(size_t
)(p
- baseAddr
) / PAGESIZE
;
3875 @property bool isFree() const scope @safe pure nothrow @nogc
3877 return npages
== freepages
;
3881 * Return number of pages necessary for an allocation of the given size
3883 * returns size_t.max if more than uint.max pages are requested
3884 * (return type is still size_t to avoid truncation when being used
3885 * in calculations, e.g. npages * PAGESIZE)
3887 static size_t
numPages(size_t size
) nothrow @nogc
3891 if (size
> PAGESIZE
* cast(size_t
)uint.max
)
3896 if (size
> size_t
.max
- PAGESIZE
)
3899 return (size
+ PAGESIZE
- 1) / PAGESIZE
;
3902 void* findBase(void* p
) nothrow @nogc
3904 size_t offset
= cast(size_t
)(p
- baseAddr
);
3905 size_t pn
= offset
/ PAGESIZE
;
3906 Bins bin
= pagetable
[pn
];
3908 // Adjust bit to be at start of allocated memory block
3909 if (bin
< Bins
.B_NUMSMALL
)
3911 auto baseOff
= baseOffset(offset
, bin
);
3912 const biti
= baseOff
>> Pool
.ShiftBy
.Small
;
3913 if (freebits
.test (biti
))
3915 return baseAddr
+ baseOff
;
3917 if (bin
== Bins
.B_PAGE
)
3919 return baseAddr
+ (offset
& (offset
.max ^
(PAGESIZE
-1)));
3921 if (bin
== Bins
.B_PAGEPLUS
)
3923 size_t pageOffset
= bPageOffsets
[pn
];
3924 offset
-= pageOffset
* PAGESIZE
;
3927 return baseAddr
+ (offset
& (offset
.max ^
(PAGESIZE
-1)));
3929 // we are in a B_FREE page
3930 assert(bin
== Bins
.B_FREE
);
3934 size_t
slGetSize(void* p
) nothrow @nogc
3937 return (cast(LargeObjectPool
*)&this).getPages(p
) * PAGESIZE
;
3939 return (cast(SmallObjectPool
*)&this).getSize(p
);
3942 BlkInfo
slGetInfo(void* p
) nothrow
3945 return (cast(LargeObjectPool
*)&this).getInfo(p
);
3947 return (cast(SmallObjectPool
*)&this).getInfo(p
);
3951 void Invariant() const {}
3958 //if (baseAddr + npages * PAGESIZE != topAddr)
3959 //printf("baseAddr = %p, npages = %d, topAddr = %p\n", baseAddr, npages, topAddr);
3960 assert(baseAddr
+ npages
* PAGESIZE
== topAddr
);
3963 if (pagetable
!is null)
3965 for (size_t i
= 0; i
< npages
; i
++)
3967 Bins bin
= pagetable
[i
];
3968 assert(bin
< Bins
.B_MAX
);
3973 void setPointerBitmapSmall(void* p
, size_t s
, size_t allocSize
, uint attr
, const TypeInfo ti
) nothrow
3975 if (!(attr
& BlkAttr
.NO_SCAN
))
3976 setPointerBitmap(p
, s
, allocSize
, ti
, attr
);
3979 pragma(inline
,false)
3980 void setPointerBitmap(void* p
, size_t s
, size_t allocSize
, const TypeInfo ti
, uint attr
) nothrow
3982 size_t offset
= p
- baseAddr
;
3983 //debug(PRINTF) printGCBits(&pool.is_pointer);
3986 printf("Setting a pointer bitmap for %s at %p + %llu\n", debugTypeName(ti
).ptr
, p
, cast(ulong)s
);
3990 if (attr
& BlkAttr
.APPENDABLE
)
3992 // an array of classes is in fact an array of pointers
3993 if (typeid(ti
) is typeid(TypeInfo_Class
))
3994 goto L_conservative
;
3998 auto rtInfo
= cast(const(size_t
)*)ti
.rtInfo();
4000 if (rtInfo
is rtinfoNoPointers
)
4002 debug(PRINTF
) printf("\tCompiler generated rtInfo: no pointers\n");
4003 is_pointer
.clrRange(offset
/(void*).sizeof
, s
/(void*).sizeof
);
4005 else if (rtInfo
is rtinfoHasPointers
)
4007 debug(PRINTF
) printf("\tCompiler generated rtInfo: has pointers\n");
4008 is_pointer
.setRange(offset
/(void*).sizeof
, s
/(void*).sizeof
);
4012 const(size_t
)* bitmap
= cast (size_t
*) rtInfo
;
4013 //first element of rtInfo is the size of the object the bitmap encodes
4014 size_t element_size
= * bitmap
;
4017 if (attr
& BlkAttr
.APPENDABLE
)
4019 tocopy
= s
/(void*).sizeof
;
4020 is_pointer
.copyRangeRepeating(offset
/(void*).sizeof
, tocopy
, bitmap
, element_size
/(void*).sizeof
);
4024 tocopy
= (s
< element_size ? s
: element_size
)/(void*).sizeof
;
4025 is_pointer
.copyRange(offset
/(void*).sizeof
, tocopy
, bitmap
);
4028 debug(PRINTF
) printf("\tSetting bitmap for new object (%s)\n\t\tat %p\t\tcopying from %p + %llu: ",
4029 debugTypeName(ti
).ptr
, p
, bitmap
, cast(ulong)element_size
);
4031 for (size_t i
= 0; i
< element_size
/((void*).sizeof
); i
++)
4032 printf("%d", (bitmap
[i
/(8*size_t
.sizeof
)] >> (i
%(8*size_t
.sizeof
))) & 1);
4033 debug(PRINTF
) printf("\n");
4035 if (tocopy
* (void*).sizeof
< s
) // better safe than sorry: if allocated more, assume pointers inside
4037 debug(PRINTF
) printf(" Appending %d pointer bits\n", s
/(void*).sizeof
- tocopy
);
4038 is_pointer
.setRange(offset
/(void*).sizeof
+ tocopy
, s
/(void*).sizeof
- tocopy
);
4044 offset
= (offset
+ s
+ (void*).sizeof
- 1) & ~((void*).sizeof
- 1);
4045 is_pointer
.clrRange(offset
/(void*).sizeof
, (allocSize
- s
)/(void*).sizeof
);
4051 // limit pointers to actual size of allocation? might fail for arrays that append
4052 // without notifying the GC
4055 debug(PRINTF
) printf("Allocating a block without TypeInfo\n");
4056 is_pointer
.setRange(offset
/(void*).sizeof
, s
/(void*).sizeof
);
4058 //debug(PRINTF) printGCBits(&pool.is_pointer);
4062 struct LargeObjectPool
4071 for (size_t n
= 0; n
< npages
; )
4073 uint np
= bPageOffsets
[n
];
4074 assert(np
> 0 && np
<= npages
- n
);
4076 if (pagetable
[n
] == Bins
.B_PAGE
)
4078 for (uint p
= 1; p
< np
; p
++)
4080 assert(pagetable
[n
+ p
] == Bins
.B_PAGEPLUS
);
4081 assert(bPageOffsets
[n
+ p
] == p
);
4084 else if (pagetable
[n
] == Bins
.B_FREE
)
4086 for (uint p
= 1; p
< np
; p
++)
4088 assert(pagetable
[n
+ p
] == Bins
.B_FREE
);
4090 assert(bPageOffsets
[n
+ np
- 1] == np
);
4099 * Allocate n pages from Pool.
4100 * Returns OPFAIL on failure.
4102 size_t
allocPages(size_t n
) nothrow
4104 if (largestFree
< n || searchStart
+ n
> npages
)
4107 //debug(PRINTF) printf("Pool::allocPages(n = %d)\n", n);
4109 if (pagetable
[searchStart
] == Bins
.B_PAGEPLUS
)
4111 searchStart
-= bPageOffsets
[searchStart
]; // jump to B_PAGE
4112 searchStart
+= bPageOffsets
[searchStart
];
4114 while (searchStart
< npages
&& pagetable
[searchStart
] == Bins
.B_PAGE
)
4115 searchStart
+= bPageOffsets
[searchStart
];
4117 for (size_t i
= searchStart
; i
< npages
; )
4119 assert(pagetable
[i
] == Bins
.B_FREE
);
4121 auto p
= bPageOffsets
[i
];
4124 setFreePageOffsets(i
+ n
, p
- n
);
4130 pagetable
[i
] = Bins
.B_PAGE
;
4131 bPageOffsets
[i
] = cast(uint) n
;
4134 memset(&pagetable
[i
+ 1], Bins
.B_PAGEPLUS
, n
- 1);
4135 for (auto offset
= 1; offset
< n
; offset
++)
4136 bPageOffsets
[i
+ offset
] = cast(uint) offset
;
4145 while (i
< npages
&& pagetable
[i
] == Bins
.B_PAGE
)
4147 // we have the size information, so we skip a whole bunch of pages.
4148 i
+= bPageOffsets
[i
];
4152 // not enough free pages found, remember largest free chunk
4153 largestFree
= largest
;
4158 * Free npages pages starting with pagenum.
4160 void freePages(size_t pagenum
, size_t npages
) nothrow @nogc
4162 //memset(&pagetable[pagenum], B_FREE, npages);
4163 if (pagenum
< searchStart
)
4164 searchStart
= pagenum
;
4166 for (size_t i
= pagenum
; i
< npages
+ pagenum
; i
++)
4168 assert(pagetable
[i
] < Bins
.B_FREE
);
4169 pagetable
[i
] = Bins
.B_FREE
;
4171 freepages
+= npages
;
4172 largestFree
= freepages
; // invalidate
4176 * Set the first and the last entry of a B_FREE block to the size
4178 void setFreePageOffsets(size_t page
, size_t num
) nothrow @nogc
4180 assert(pagetable
[page
] == Bins
.B_FREE
);
4181 assert(pagetable
[page
+ num
- 1] == Bins
.B_FREE
);
4182 bPageOffsets
[page
] = cast(uint)num
;
4184 bPageOffsets
[page
+ num
- 1] = cast(uint)num
;
4187 void mergeFreePageOffsets(bool bwd
, bool fwd
)(size_t page
, size_t num
) nothrow @nogc
4191 if (page
> 0 && pagetable
[page
- 1] == Bins
.B_FREE
)
4193 auto sz
= bPageOffsets
[page
- 1];
4200 if (page
+ num
< npages
&& pagetable
[page
+ num
] == Bins
.B_FREE
)
4201 num
+= bPageOffsets
[page
+ num
];
4203 setFreePageOffsets(page
, num
);
4207 * Get pages of allocation at pointer p in pool.
4209 size_t
getPages(void *p
) const nothrow @nogc
4212 assert(p
>= baseAddr
);
4213 assert(p
< topAddr
);
4217 if (cast(size_t
)p
& (PAGESIZE
- 1)) // check for interior pointer
4219 size_t pagenum
= pagenumOf(p
);
4220 Bins bin
= pagetable
[pagenum
];
4221 if (bin
!= Bins
.B_PAGE
)
4223 return bPageOffsets
[pagenum
];
4227 * Get size of allocation at page pn in pool.
4229 size_t
getSize(size_t pn
) const nothrow @nogc
4231 assert(pagetable
[pn
] == Bins
.B_PAGE
);
4232 return cast(size_t
) bPageOffsets
[pn
] * PAGESIZE
;
4238 BlkInfo
getInfo(void* p
) nothrow
4242 size_t offset
= cast(size_t
)(p
- baseAddr
);
4243 size_t pn
= offset
/ PAGESIZE
;
4244 Bins bin
= pagetable
[pn
];
4246 if (bin
== Bins
.B_PAGEPLUS
)
4247 pn
-= bPageOffsets
[pn
];
4248 else if (bin
!= Bins
.B_PAGE
)
4249 return info
; // no info for free pages
4251 info
.base
= baseAddr
+ pn
* PAGESIZE
;
4252 info
.size
= getSize(pn
);
4253 info
.attr
= getBits(pn
);
4257 void runFinalizers(const scope void[] segment
) nothrow
4259 foreach (pn
; 0 .. npages
)
4261 Bins bin
= pagetable
[pn
];
4262 if (bin
> Bins
.B_PAGE
)
4266 if (!finals
.test(biti
))
4269 auto p
= sentinel_add(baseAddr
+ pn
* PAGESIZE
);
4270 size_t size
= sentinel_size(p
, getSize(pn
));
4271 uint attr
= getBits(biti
);
4273 if (!rt_hasFinalizerInSegment(p
, size
, attr
, segment
))
4276 rt_finalizeFromGC(p
, size
, attr
);
4278 clrBits(biti
, ~BlkAttr
.NONE
);
4280 if (pn
< searchStart
)
4283 debug(COLLECT_PRINTF
) printf("\tcollecting big %p\n", p
);
4284 //log_free(sentinel_add(p));
4287 for (; pn
+ n
< npages
; ++n
)
4288 if (pagetable
[pn
+ n
] != Bins
.B_PAGEPLUS
)
4290 invalidate((baseAddr
+ pn
* PAGESIZE
)[0 .. n
* PAGESIZE
], 0xF3, false);
4292 mergeFreePageOffsets
!(true, true)(pn
, n
);
4298 struct SmallObjectPool
4307 uint cntRecover
= 0;
4308 foreach (Bins bin
; Bins
.B_16
.. Bins
.B_NUMSMALL
)
4310 for (auto pn
= recoverPageFirst
[bin
]; pn
< npages
; pn
= binPageChain
[pn
])
4312 assert(pagetable
[pn
] == bin
);
4317 for (auto pn
= searchStart
; pn
< npages
; pn
= binPageChain
[pn
])
4319 assert(pagetable
[pn
] == Bins
.B_FREE
);
4322 assert(cntFree
== freepages
);
4323 assert(cntFree
+ cntRecover
<= npages
);
4327 * Get size of pointer p in pool.
4329 size_t
getSize(void *p
) const nothrow @nogc
4332 assert(p
>= baseAddr
);
4333 assert(p
< topAddr
);
4337 size_t pagenum
= pagenumOf(p
);
4338 Bins bin
= pagetable
[pagenum
];
4339 assert(bin
< Bins
.B_PAGE
);
4340 if (p
!= cast(void*)baseOffset(cast(size_t
)p
, bin
)) // check for interior pointer
4342 const biti
= cast(size_t
)(p
- baseAddr
) >> ShiftBy
.Small
;
4343 if (freebits
.test (biti
))
4345 return binsize
[bin
];
4348 BlkInfo
getInfo(void* p
) nothrow
4351 size_t offset
= cast(size_t
)(p
- baseAddr
);
4352 size_t pn
= offset
/ PAGESIZE
;
4353 Bins bin
= pagetable
[pn
];
4355 if (bin
>= Bins
.B_PAGE
)
4358 auto base
= cast(void*)baseOffset(cast(size_t
)p
, bin
);
4359 const biti
= cast(size_t
)(base
- baseAddr
) >> ShiftBy
.Small
;
4360 if (freebits
.test (biti
))
4364 info
.size
= binsize
[bin
];
4365 offset
= info
.base
- baseAddr
;
4366 info
.attr
= getBits(biti
);
4371 void runFinalizers(const scope void[] segment
) nothrow
4373 foreach (pn
; 0 .. npages
)
4375 Bins bin
= pagetable
[pn
];
4376 if (bin
>= Bins
.B_PAGE
)
4379 immutable size
= binsize
[bin
];
4380 auto p
= baseAddr
+ pn
* PAGESIZE
;
4381 const ptop
= p
+ PAGESIZE
- size
+ 1;
4382 immutable base
= pn
* (PAGESIZE
/16);
4383 immutable bitstride
= size
/ 16;
4388 for (size_t i
; p
< ptop
; p
+= size
, i
+= bitstride
)
4390 immutable biti
= base
+ i
;
4392 if (!finals
.test(biti
))
4395 auto q
= sentinel_add(p
);
4396 uint attr
= getBits(biti
);
4397 const ssize
= sentinel_size(q
, size
);
4398 if (!rt_hasFinalizerInSegment(q
, ssize
, attr
, segment
))
4401 rt_finalizeFromGC(q
, ssize
, attr
);
4406 debug(COLLECT_PRINTF
) printf("\tcollecting %p\n", p
);
4407 //log_free(sentinel_add(p));
4409 invalidate(p
[0 .. size
], 0xF3, false);
4413 freePageBits(pn
, toFree
);
4418 * Allocate a page of bin's.
4420 * head of a single linked list of new entries
4422 List
* allocPage(Bins bin
) nothrow
4424 if (searchStart
>= npages
)
4427 assert(pagetable
[searchStart
] == Bins
.B_FREE
);
4430 size_t pn
= searchStart
;
4431 searchStart
= binPageChain
[searchStart
];
4432 binPageChain
[pn
] = Pool
.PageRecovered
;
4433 pagetable
[pn
] = bin
;
4436 // Convert page to free list
4437 size_t size
= binsize
[bin
];
4438 void* p
= baseAddr
+ pn
* PAGESIZE
;
4439 auto first
= cast(List
*) p
;
4441 // ensure 2 <size> bytes blocks are available below ptop, one
4442 // being set in the loop, and one for the tail block
4443 void* ptop
= p
+ PAGESIZE
- 2 * size
+ 1;
4444 for (; p
< ptop
; p
+= size
)
4446 undefinedWrite((cast(List
*)p
).next
, cast(List
*)(p
+ size
));
4447 undefinedWrite((cast(List
*)p
).pool
, &base
);
4449 undefinedWrite((cast(List
*)p
).next
, null);
4450 undefinedWrite((cast(List
*)p
).pool
, &base
);
4455 debug(SENTINEL
) {} else // no additional capacity with SENTINEL
4456 unittest // https://issues.dlang.org/show_bug.cgi?id=14467
4458 int[] arr
= new int[10];
4459 assert(arr
.capacity
);
4461 assert(arr
.capacity
);
4464 unittest // https://issues.dlang.org/show_bug.cgi?id=15353
4466 import core
.memory
: GC
;
4472 GC
.free(buf
); // ignored in finalizer
4477 new Foo(GC
.malloc(10));
4481 unittest // https://issues.dlang.org/show_bug.cgi?id=15822
4483 import core
.memory
: GC
;
4485 __gshared
ubyte[16] buf
;
4490 GC
.removeRange(ptr
);
4496 GC
.addRoot(buf
.ptr
);
4497 GC
.addRange(buf
.ptr
, buf
.length
);
4502 unittest // https://issues.dlang.org/show_bug.cgi?id=1180
4504 import core
.exception
;
4507 size_t x
= size_t
.max
- 100;
4508 byte[] big_buf
= new byte[x
];
4510 catch (OutOfMemoryError
)
4515 /* ============================ PRINTF =============================== */
4517 debug(PRINTF_TO_FILE
)
4519 private __gshared MonoTime gcStartTick
;
4520 private __gshared FILE
* gcx_fh
;
4521 private __gshared
bool hadNewline
= false;
4522 import core
.internal
.spinlock
;
4523 static printLock
= shared(AlignedSpinLock
)(SpinLock
.Contention
.lengthy
);
4525 private int printf(ARGS
...)(const char* fmt
, ARGS args
) nothrow
4528 scope(exit
) printLock
.unlock();
4531 gcx_fh
= fopen("gcx.log", "w");
4536 if (MonoTime
.ticksPerSecond
== 0)
4538 len
= fprintf(gcx_fh
, "before init: ");
4540 else if (hadNewline
)
4542 if (gcStartTick
== MonoTime
.init
)
4543 gcStartTick
= MonoTime
.currTime
;
4544 immutable timeElapsed
= MonoTime
.currTime
- gcStartTick
;
4545 immutable secondsAsDouble
= timeElapsed
.total
!"hnsecs" / cast(double)convert
!("seconds", "hnsecs")(1);
4546 len
= fprintf(gcx_fh
, "%10.6f: ", secondsAsDouble
);
4548 len
+= fprintf(gcx_fh
, fmt
, args
);
4550 import core
.stdc
.string
;
4551 hadNewline
= fmt
&& fmt
[0] && fmt
[strlen(fmt
) - 1] == '\n';
4556 debug(PRINTF
) void printFreeInfo(Pool
* pool
) nothrow
4559 foreach (i
; 0..pool
.npages
) {
4560 if (pool
.pagetable
[i
] >= Bins
.B_FREE
) nReallyFree
++;
4563 printf("Pool %p: %d really free, %d supposedly free\n", pool
, nReallyFree
, pool
.freepages
);
4567 void printGCBits(GCBits
* bits
)
4569 for (size_t i
= 0; i
< bits
.nwords
; i
++)
4571 if (i
% 32 == 0) printf("\n\t");
4572 printf("%x ", bits
.data
[i
]);
4577 // we can assume the name is always from a literal, so it is zero terminated
4579 string
debugTypeName(const(TypeInfo
) ti
) nothrow
4584 else if (auto ci
= cast(TypeInfo_Class
)ti
)
4586 else if (auto si
= cast(TypeInfo_Struct
)ti
)
4587 name
= si
.mangledName
; // .name() might GC-allocate, avoid deadlock
4588 else if (auto ci
= cast(TypeInfo_Const
)ti
)
4589 static if (__traits(compiles
,ci
.base
)) // different whether compiled with object.di or object.d
4590 return debugTypeName(ci
.base
);
4592 return debugTypeName(ci
.next
);
4594 name
= typeid(ti
).name
;
4598 /* ======================= Leak Detector =========================== */
4610 void print() nothrow
4612 printf(" p = %p, size = %lld, parent = %p ", p
, cast(ulong)size
, parent
);
4615 printf("%s(%u)", file
, cast(uint)line
);
4628 void Dtor() nothrow @nogc
4635 void reserve(size_t nentries
) nothrow @nogc
4637 assert(dim
<= allocdim
);
4638 if (allocdim
- dim
< nentries
)
4640 allocdim
= (dim
+ nentries
) * 2;
4641 assert(dim
+ nentries
<= allocdim
);
4644 data
= cast(Log
*)cstdlib
.malloc(allocdim
* Log
.sizeof
);
4645 if (!data
&& allocdim
)
4646 onOutOfMemoryErrorNoGC();
4651 newdata
= cast(Log
*)cstdlib
.malloc(allocdim
* Log
.sizeof
);
4652 if (!newdata
&& allocdim
)
4653 onOutOfMemoryErrorNoGC();
4654 memcpy(newdata
, data
, dim
* Log
.sizeof
);
4662 void push(Log log
) nothrow @nogc
4668 void remove(size_t i
) nothrow @nogc
4670 memmove(data
+ i
, data
+ i
+ 1, (dim
- i
) * Log
.sizeof
);
4675 size_t
find(void *p
) nothrow @nogc
4677 for (size_t i
= 0; i
< dim
; i
++)
4682 return OPFAIL
; // not found
4686 void copy(LogArray
*from
) nothrow @nogc
4688 if (allocdim
< from
.dim
)
4689 reserve(from
.dim
- dim
);
4690 assert(from
.dim
<= allocdim
);
4691 memcpy(data
, from
.data
, from
.dim
* Log
.sizeof
);
4702 private void initialize(Gcx
* gc
)
4705 //debug(PRINTF) printf("+log_init()\n");
4706 current
.reserve(1000);
4708 //debug(PRINTF) printf("-log_init()\n");
4712 private void log_malloc(void *p
, size_t size
) nothrow
4714 //debug(PRINTF) printf("+log_malloc(p = %p, size = %zd)\n", p, size);
4719 log
.line
= ConservativeGC
.line
;
4720 log
.file
= ConservativeGC
.file
;
4723 ConservativeGC
.line
= 0;
4724 ConservativeGC
.file
= null;
4727 //debug(PRINTF) printf("-log_malloc()\n");
4731 private void log_free(void *p
, size_t size
) nothrow @nogc
4733 //debug(PRINTF) printf("+log_free(%p)\n", p);
4734 auto i
= current
.find(p
);
4737 debug(PRINTF
) printf("free'ing unallocated memory %p (size %zu)\n", p
, size
);
4741 //debug(PRINTF) printf("-log_free()\n");
4745 private void log_collect() nothrow
4747 //debug(PRINTF) printf("+log_collect()\n");
4748 // Print everything in current that is not in prev
4750 debug(PRINTF
) printf("New pointers this cycle: --------------------------------\n");
4752 for (size_t i
= 0; i
< current
.dim
; i
++)
4754 auto j
= prev
.find(current
.data
[i
].p
);
4756 current
.data
[i
].print();
4761 debug(PRINTF
) printf("All roots this cycle: --------------------------------\n");
4762 for (size_t i
= 0; i
< current
.dim
; i
++)
4764 void* p
= current
.data
[i
].p
;
4765 if (!gcx
.findPool(current
.data
[i
].parent
))
4767 auto j
= prev
.find(current
.data
[i
].p
);
4768 debug(PRINTF
) printf(j
== OPFAIL ?
"N" : " ");
4769 current
.data
[i
].print();
4773 debug(PRINTF
) printf("Used = %d-------------------------------------------------\n", used
);
4774 prev
.copy(¤t
);
4776 debug(PRINTF
) printf("-log_collect()\n");
4780 private void log_parent(void *p
, void *parent
) nothrow
4782 //debug(PRINTF) printf("+log_parent()\n");
4783 auto i
= current
.find(p
);
4786 debug(PRINTF
) printf("parent'ing unallocated memory %p, parent = %p\n", p
, parent
);
4788 pool
= gcx
.findPool(p
);
4790 size_t offset
= cast(size_t
)(p
- pool
.baseAddr
);
4792 size_t pn
= offset
/ PAGESIZE
;
4793 Bins bin
= pool
.pagetable
[pn
];
4794 biti
= (offset
& (PAGESIZE
- 1)) >> pool
.shiftBy
;
4795 debug(PRINTF
) printf("\tbin = %d, offset = x%x, biti = x%x\n", bin
, offset
, biti
);
4799 current
.data
[i
].parent
= parent
;
4801 //debug(PRINTF) printf("-log_parent()\n");
4809 static void initialize(Gcx
* gcx
) nothrow { }
4810 static void log_malloc(void *p
, size_t size
) nothrow { }
4811 static void log_free(void *p
, size_t size
) nothrow @nogc {}
4812 static void log_collect() nothrow { }
4813 static void log_parent(void *p
, void *parent
) nothrow { }
4817 /* ============================ SENTINEL =============================== */
4821 // pre-sentinel must be smaller than 16 bytes so that the same GC bits
4822 // are used for the allocated pointer and the user pointer
4823 // so use uint for both 32 and 64 bit platforms, limiting usage to < 4GB
4824 const uint SENTINEL_PRE
= 0xF4F4F4F4;
4825 const ubyte SENTINEL_POST
= 0xF5; // 8 bits
4826 const uint SENTINEL_EXTRA
= 2 * uint.sizeof
+ 1;
4829 inout(uint*) sentinel_psize(inout void *p
) nothrow @nogc { return &(cast(inout uint *)p
)[-2]; }
4830 inout(uint*) sentinel_pre(inout void *p
) nothrow @nogc { return &(cast(inout uint *)p
)[-1]; }
4831 inout(ubyte*) sentinel_post(inout void *p
) nothrow @nogc { return &(cast(inout ubyte *)p
)[*sentinel_psize(p
)]; }
4834 void sentinel_init(void *p
, size_t size
) nothrow @nogc
4836 assert(size
<= uint.max
);
4837 *sentinel_psize(p
) = cast(uint)size
;
4840 makeMemNoAccess(sentinel_pre(p
)[0..1]);
4841 makeMemNoAccess(sentinel_post(p
)[0..1]);
4845 *sentinel_pre(p
) = SENTINEL_PRE
;
4846 *sentinel_post(p
) = SENTINEL_POST
;
4851 void sentinel_Invariant(const void *p
) nothrow @nogc
4853 debug (VALGRIND
) {} else
4856 assert(*sentinel_pre(p
) == SENTINEL_PRE
);
4857 assert(*sentinel_post(p
) == SENTINEL_POST
);
4859 else if (*sentinel_pre(p
) != SENTINEL_PRE ||
*sentinel_post(p
) != SENTINEL_POST
)
4860 onInvalidMemoryOperationError(); // also trigger in release build
4863 size_t
sentinel_size(const void *p
, size_t alloc_size
) nothrow @nogc
4865 return *sentinel_psize(p
);
4868 void *sentinel_add(void *p
) nothrow @nogc
4870 return p
+ 2 * uint.sizeof
;
4874 void *sentinel_sub(void *p
) nothrow @nogc
4876 return p
- 2 * uint.sizeof
;
4881 const uint SENTINEL_EXTRA
= 0;
4884 void sentinel_init(void *p
, size_t size
) nothrow @nogc
4889 void sentinel_Invariant(const void *p
) nothrow @nogc
4893 size_t
sentinel_size(const void *p
, size_t alloc_size
) nothrow @nogc
4898 void *sentinel_add(void *p
) nothrow @nogc
4904 void *sentinel_sub(void *p
) nothrow @nogc
4914 auto p
= cast(size_t
*)GC
.malloc(size_t
.sizeof
*3);
4915 assert(*p
== cast(size_t
)0xF0F0F0F0F0F0F0F0);
4916 p
[2] = 0; // First two will be used for free list
4918 assert(p
[2] == cast(size_t
)0xF2F2F2F2F2F2F2F2);
4925 auto p
= cast(ubyte*)GC
.malloc(1);
4926 assert(p
[-1] == 0xF4);
4927 assert(p
[ 1] == 0xF5);
4929 // See also stand-alone tests in test/gc
4936 // https://issues.dlang.org/show_bug.cgi?id=9275
4937 GC
.removeRoot(null);
4938 GC
.removeRoot(cast(void*)13);
4941 // improve predictability of coverage of code that is eventually not hit by other tests
4942 debug (SENTINEL
) {} else // cannot extend with SENTINEL
4943 debug (MARK_PRINTF
) {} else // takes forever
4947 auto p
= GC
.malloc(260 << 20); // new pool has 390 MB
4948 auto q
= GC
.malloc(65 << 20); // next chunk (larger than 64MB to ensure the same pool is used)
4949 auto r
= GC
.malloc(65 << 20); // another chunk in same pool
4950 assert(p
+ (260 << 20) == q
);
4951 assert(q
+ (65 << 20) == r
);
4953 // should trigger "assert(bin == Bins.B_FREE);" in mark due to dangling pointer q:
4955 // should trigger "break;" in extendNoSync:
4956 size_t sz
= GC
.extend(p
, 64 << 20, 66 << 20); // trigger size after p large enough (but limited)
4957 assert(sz
== 325 << 20);
4960 r
= q
; // ensure q is not trashed before collection above
4962 p
= GC
.malloc(70 << 20); // from the same pool
4963 q
= GC
.malloc(70 << 20);
4964 r
= GC
.malloc(70 << 20);
4965 auto s
= GC
.malloc(70 << 20);
4966 auto t
= GC
.malloc(70 << 20); // 350 MB of 390 MB used
4967 assert(p
+ (70 << 20) == q
);
4968 assert(q
+ (70 << 20) == r
);
4969 assert(r
+ (70 << 20) == s
);
4970 assert(s
+ (70 << 20) == t
);
4971 GC
.free(r
); // ensure recalculation of largestFree in nxxt allocPages
4972 auto z
= GC
.malloc(75 << 20); // needs new pool
4979 GC
.minimize(); // release huge pool
4982 // https://issues.dlang.org/show_bug.cgi?id=19281
4983 debug (SENTINEL
) {} else // cannot allow >= 4 GB with SENTINEL
4984 debug (MEMSTOMP
) {} else // might take too long to actually touch the memory
4985 version (D_LP64
) unittest
4987 static if (__traits(compiles
, os_physical_mem
))
4989 // only run if the system has enough physical memory
4991 //import core.stdc.stdio;
4992 //printf("availphys = %lld", os_physical_mem());
4993 if (os_physical_mem() > sz
)
4998 auto stats
= GC
.stats();
4999 auto ptr
= GC
.malloc(sz
, BlkAttr
.NO_SCAN
);
5000 auto info
= GC
.query(ptr
);
5001 //printf("info.size = %lld", info.size);
5002 assert(info
.size
>= sz
);
5005 auto nstats
= GC
.stats();
5006 assert(nstats
.usedSize
== stats
.usedSize
);
5007 assert(nstats
.freeSize
== stats
.freeSize
);
5008 assert(nstats
.allocatedInCurrentThread
- sz
== stats
.allocatedInCurrentThread
);
5013 // https://issues.dlang.org/show_bug.cgi?id=19522
5020 assert(GC
.getAttr(p
) == BlkAttr
.NO_SCAN
);
5021 assert(GC
.setAttr(p
+ 4, BlkAttr
.NO_SCAN
) == 0); // interior pointer should fail
5022 assert(GC
.clrAttr(p
+ 4, BlkAttr
.NO_SCAN
) == 0); // interior pointer should fail
5024 assert(GC
.query(p
).base
== null);
5025 assert(GC
.query(p
).size
== 0);
5026 assert(GC
.addrOf(p
) == null);
5027 assert(GC
.sizeOf(p
) == 0); // fails
5028 assert(GC
.getAttr(p
) == 0);
5029 assert(GC
.setAttr(p
, BlkAttr
.NO_SCAN
) == 0);
5030 assert(GC
.clrAttr(p
, BlkAttr
.NO_SCAN
) == 0);
5032 void* large
= GC
.malloc(10000, BlkAttr
.NO_SCAN
);
5035 void* small
= GC
.malloc(100, BlkAttr
.NO_SCAN
);
5043 auto now
= currTime
;
5044 GC
.ProfileStats stats1
= GC
.profileStats();
5046 GC
.ProfileStats stats2
= GC
.profileStats();
5047 auto diff
= currTime
- now
;
5049 assert(stats2
.totalCollectionTime
- stats1
.totalCollectionTime
<= diff
);
5050 assert(stats2
.totalPauseTime
- stats1
.totalPauseTime
<= stats2
.totalCollectionTime
- stats1
.totalCollectionTime
);
5052 assert(stats2
.maxPauseTime
>= stats1
.maxPauseTime
);
5053 assert(stats2
.maxCollectionTime
>= stats1
.maxCollectionTime
);
5056 // https://issues.dlang.org/show_bug.cgi?id=20214
5060 import core
.stdc
.stdio
;
5062 // allocate from large pool
5063 auto o
= GC
.malloc(10);
5064 auto p
= (cast(void**)GC
.malloc(4096 * (void*).sizeof
))[0 .. 4096];
5065 auto q
= (cast(void**)GC
.malloc(4096 * (void*).sizeof
))[0 .. 4096];
5066 if (p
.ptr
+ p
.length
is q
.ptr
)
5068 q
[] = o
; // fill with pointers
5070 // shrink, unused area cleared?
5071 auto nq
= (cast(void**)GC
.realloc(q
.ptr
, 4000 * (void*).sizeof
))[0 .. 4000];
5072 assert(q
.ptr
is nq
.ptr
);
5073 assert(q
.ptr
[4095] !is o
);
5076 // expected to extend in place
5077 auto np
= (cast(void**)GC
.realloc(p
.ptr
, 4200 * (void*).sizeof
))[0 .. 4200];
5078 assert(p
.ptr
is np
.ptr
);
5079 assert(q
.ptr
[4200] !is o
);
5083 // adjacent allocations likely but not guaranteed
5084 printf("unexpected pointers %p and %p\n", p
.ptr
, q
.ptr
);
5088 /* ============================ MEMSTOMP =============================== */
5090 /// Mark the specified memory region as uninitialized -
5091 /// reading from this region is an error.
5092 /// If writable is false, writing to it is also an error.
5093 pragma(inline
, true)
5094 void invalidate(void[] mem
, ubyte pattern
, bool writable
) nothrow @nogc
5096 debug (MEMSTOMP
) memset(mem
.ptr
, pattern
, mem
.length
);
5100 makeMemUndefined(mem
);
5102 makeMemNoAccess(mem
);
5106 /// Read memory that should otherwise be marked as unreadable
5107 /// (e.g. free lists overlapped with unallocated heap objects).
5108 pragma(inline
, true)
5109 T
undefinedRead(T
)(ref T var
) nothrow
5113 auto varArr
= (&var
)[0..1];
5114 disableAddrReportingInRange(varArr
);
5116 enableAddrReportingInRange(varArr
);
5123 /// Write memory that should otherwise be marked as unwritable.
5124 pragma(inline
, true)
5125 void undefinedWrite(T
)(ref T var
, T value
) nothrow
5129 auto varArr
= (&var
)[0..1];
5130 disableAddrReportingInRange(varArr
);
5132 enableAddrReportingInRange(varArr
);