2 * This module contains the garbage collector implementation.
4 * Copyright: Copyright (C) 2001-2007 Digital Mars, www.digitalmars.com.
7 * This software is provided 'as-is', without any express or implied
8 * warranty. In no event will the authors be held liable for any damages
9 * arising from the use of this software.
11 * Permission is granted to anyone to use this software for any purpose,
12 * including commercial applications, and to alter it and redistribute it
13 * freely, in both source and binary form, subject to the following
16 * o The origin of this software must not be misrepresented; you must not
17 * claim that you wrote the original software. If you use this software
18 * in a product, an acknowledgment in the product documentation would be
19 * appreciated but is not required.
20 * o Altered source versions must be plainly marked as such, and must not
21 * be misrepresented as being the original software.
22 * o This notice may not be removed or altered from any source
24 * Authors: Walter Bright, David Friedman, Sean Kelly
29 // D Programming Language Garbage Collector implementation
31 /************** Debugging ***************************/
33 //debug = COLLECT_PRINTF; // turn on printf's
34 //debug = PTRCHECK; // more pointer checking
35 //debug = PTRCHECK2; // thorough but slow pointer checking
37 /*************** Configuration *********************/
39 version = STACKGROWSDOWN; // growing the stack means subtracting from the stack pointer
40 // (use for Intel X86 CPUs)
41 // else growing the stack means adding to the stack pointer
43 /***************************************************/
45 import rt.gc.cdgc.bits: GCBits;
46 import rt.gc.cdgc.stats: GCStats, Stats;
47 import dynarray = rt.gc.cdgc.dynarray;
48 import alloc = rt.gc.cdgc.alloc;
49 import opts = rt.gc.cdgc.opts;
51 import cstdlib = tango.stdc.stdlib;
52 import cstring = tango.stdc.string;
55 * This is a small optimization that proved it's usefulness. For small chunks
56 * or memory memset() seems to be slower (probably because of the call) that
57 * simply doing a simple loop to set the memory.
59 void memset(void* dst, int c, size_t n)
61 // This number (32) has been determined empirically
63 cstring.memset(dst, c, n);
66 auto p = cast(ubyte*)(dst);
73 // BUG: The following import will likely not work, since the gcc
74 // subdirectory is elsewhere. Instead, perhaps the functions
75 // could be declared directly or some other resolution could
77 static import gcc.builtins; // for __builtin_unwind_int
87 package enum BlkAttr : uint
89 FINALIZE = 0b0000_0001,
90 NO_SCAN = 0b0000_0010,
91 NO_MOVE = 0b0000_0100,
92 ALL_BITS = 0b1111_1111
95 package bool has_pointermap(uint attrs)
97 return !opts.options.conservative && !(attrs & BlkAttr.NO_SCAN);
102 alias void delegate(Object) DEvent;
103 alias void delegate( void*, void* ) scanFn;
104 enum { OPFAIL = ~cast(size_t)0 }
108 version (DigitalMars) version(OSX)
109 oid _d_osx_image_init();
111 void* rt_stackBottom();
113 void rt_finalize( void* p, bool det = true );
114 void rt_attachDisposeEvent(Object h, DEvent e);
115 bool rt_detachDisposeEvent(Object h, DEvent e);
116 void rt_scanStaticData( scanFn scan );
119 bool thread_needLock();
120 void thread_suspendAll();
121 void thread_resumeAll();
122 void thread_scanAll( scanFn fn, void* curStackTop = null );
124 void onOutOfMemoryError();
132 POOLSIZE = (4096*256),
146 B_PAGE, // start of large alloc
147 B_PAGEPLUS, // continuation of large alloc
166 int opCmp(in Range other)
168 if (pbot < other.pbot)
171 return cast(int)(pbot > other.pbot);
176 const uint binsize[B_MAX] = [ 16,32,64,128,256,512,1024,2048,4096 ];
177 const uint notbinsize[B_MAX] = [ ~(16u-1),~(32u-1),~(64u-1),~(128u-1),~(256u-1),
178 ~(512u-1),~(1024u-1),~(2048u-1),~(4096u-1) ];
181 /* ============================ GC =============================== */
184 class GCLock {} // just a dummy so we can get a global lock
195 // !=0 means don't scan stack
200 /// Turn off collections if > 0
203 /// min(pool.baseAddr)
205 /// max(pool.topAddr)
208 /// Free list for each size
209 List*[B_MAX] free_list;
211 dynarray.DynArray!(void*) roots;
212 dynarray.DynArray!(Range) ranges;
213 dynarray.DynArray!(Pool) pools;
218 // call locked if necessary
219 private T locked(T, alias Code)()
221 if (thread_needLock())
222 synchronized (gc.lock) return Code();
231 assert (gc !is null);
233 for (size_t i = 0; i < gc.pools.length; i++) {
234 Pool* pool = gc.pools[i];
237 assert(gc.min_addr == pool.baseAddr);
238 if (i + 1 < gc.pools.length)
239 assert(*pool < gc.pools[i + 1]);
240 else if (i + 1 == gc.pools.length)
241 assert(gc.max_addr == pool.topAddr);
244 gc.roots.Invariant();
245 gc.ranges.Invariant();
247 for (size_t i = 0; i < gc.ranges.length; i++) {
248 assert(gc.ranges[i].pbot);
249 assert(gc.ranges[i].ptop);
250 assert(gc.ranges[i].pbot <= gc.ranges[i].ptop);
253 for (size_t i = 0; i < B_PAGE; i++)
254 for (List *list = gc.free_list[i]; list; list = list.next)
263 * Find Pool that pointer is in.
264 * Return null if not in a Pool.
265 * Assume pools is sorted.
267 Pool *findPool(void *p)
269 if (p >= gc.min_addr && p < gc.max_addr)
271 if (gc.pools.length == 1)
276 for (size_t i = 0; i < gc.pools.length; i++)
278 Pool* pool = gc.pools[i];
279 if (p < pool.topAddr)
281 if (pool.baseAddr <= p)
292 * Determine the base address of the block containing p. If p is not a gc
293 * allocated pointer, return null.
295 BlkInfo getInfo(void* p)
298 Pool* pool = findPool(p);
302 info.base = pool.findBase(p);
303 info.size = pool.findSize(info.base);
304 info.attr = getAttr(pool, cast(size_t)(info.base - pool.baseAddr) / 16u);
305 if (has_pointermap(info.attr)) {
306 info.size -= size_t.sizeof; // PointerMap bitmask
307 // Points to the PointerMap bitmask pointer, not user data
308 if (p >= (info.base + info.size)) {
312 if (opts.options.sentinel) {
313 info.base = sentinel_add(info.base);
314 // points to sentinel data, not user data
315 if (p < info.base || p >= sentinel_post(info.base))
317 info.size -= SENTINEL_EXTRA;
324 * Compute bin for size.
326 static Bins findBin(size_t size)
370 * Allocate a new pool of at least size bytes.
371 * Sort it into pools.
372 * Mark all memory in the pool as B_FREE.
373 * Return the actual number of bytes reserved or 0 on error.
375 size_t reserve(size_t size)
378 size_t npages = (size + PAGESIZE - 1) / PAGESIZE;
379 Pool* pool = newPool(npages);
383 return pool.npages * PAGESIZE;
388 * Minimizes physical memory usage by returning free pools to the OS.
396 for (n = 0; n < gc.pools.length; n++)
399 for (pn = 0; pn < pool.npages; pn++)
401 if (cast(Bins)pool.pagetable[pn] != B_FREE)
404 if (pn < pool.npages)
407 gc.pools.remove_at(n);
410 gc.min_addr = gc.pools[0].baseAddr;
411 gc.max_addr = gc.pools[gc.pools.length - 1].topAddr;
416 * Allocate a chunk of memory that is larger than a page.
417 * Return null if out of memory.
419 void *bigAlloc(size_t size)
429 npages = (size + PAGESIZE - 1) / PAGESIZE;
433 // This code could use some refinement when repeatedly
434 // allocating very large arrays.
436 for (n = 0; n < gc.pools.length; n++)
439 pn = pool.allocPages(npages);
454 freedpages = fullcollectshell();
455 if (freedpages >= gc.pools.length * ((POOLSIZE / PAGESIZE) / 4))
460 // Release empty pools to prevent bloat
463 pool = newPool(npages);
469 pn = pool.allocPages(npages);
470 assert(pn != OPFAIL);
473 // Release empty pools to prevent bloat
476 pool = newPool(npages);
479 pn = pool.allocPages(npages);
480 assert(pn != OPFAIL);
490 pool.pagetable[pn] = B_PAGE;
492 memset(&pool.pagetable[pn + 1], B_PAGEPLUS, npages - 1);
493 p = pool.baseAddr + pn * PAGESIZE;
494 memset(cast(char *)p + size, 0, npages * PAGESIZE - size);
495 if (opts.options.mem_stomp)
496 memset(p, 0xF1, size);
500 return null; // let mallocNoSync handle the error
505 * Allocate a new pool with at least npages in it.
506 * Sort it into pools.
507 * Return null if failed.
509 Pool *newPool(size_t npages)
511 // Minimum of POOLSIZE
512 if (npages < POOLSIZE/PAGESIZE)
513 npages = POOLSIZE/PAGESIZE;
514 else if (npages > POOLSIZE/PAGESIZE)
516 // Give us 150% of requested size, so there's room to extend
517 auto n = npages + (npages >> 1);
518 if (n < size_t.max/PAGESIZE)
522 // Allocate successively larger pools up to 8 megs
525 size_t n = gc.pools.length;
527 n = 8; // cap pool size at 8 megs
528 n *= (POOLSIZE / PAGESIZE);
534 p.initialize(npages);
541 Pool* pool = gc.pools.insert_sorted(p);
544 gc.min_addr = gc.pools[0].baseAddr;
545 gc.max_addr = gc.pools[gc.pools.length - 1].topAddr;
552 * Allocate a page of bin's.
556 int allocPage(Bins bin)
564 for (n = 0; n < gc.pools.length; n++)
567 pn = pool.allocPages(1);
574 pool.pagetable[pn] = cast(ubyte)bin;
576 // Convert page to free list
577 size_t size = binsize[bin];
578 List **b = &gc.free_list[bin];
580 p = pool.baseAddr + pn * PAGESIZE;
582 for (; p < ptop; p += size)
584 (cast(List *)p).next = *b;
592 * Marks a range of memory using the conservative bit mask. Used for
593 * the stack, for the data segment, and additional memory ranges.
595 void mark_conservative(void* pbot, void* ptop)
597 mark(pbot, ptop, PointerMap.init.bits.ptr);
602 * Search a range of memory values and mark any pointers into the GC pool.
604 void mark(void *pbot, void *ptop, size_t* pm_bitmask)
606 // TODO: make our own assert because assert uses the GC
607 assert (pbot <= ptop);
609 const BITS_PER_WORD = size_t.sizeof * 8;
611 void **p1 = cast(void **)pbot;
612 void **p2 = cast(void **)ptop;
616 size_t type_size = pm_bitmask[0];
617 size_t* pm_bits = pm_bitmask + 1;
619 //printf("marking range: %p -> %p\n", pbot, ptop);
620 for (; p1 + type_size <= p2; p1 += type_size) {
621 for (size_t n = 0; n < type_size; n++) {
622 // scan bit set for this word
623 if (!(pm_bits[n / BITS_PER_WORD] & (1 << (n % BITS_PER_WORD))))
628 if (p < gc.min_addr || p >= gc.max_addr)
631 if ((cast(size_t)p & ~(PAGESIZE-1)) == pcache)
634 Pool* pool = findPool(p);
637 size_t offset = cast(size_t)(p - pool.baseAddr);
639 size_t pn = offset / PAGESIZE;
640 Bins bin = cast(Bins)pool.pagetable[pn];
642 // Adjust bit to be at start of allocated memory block
644 bit_i = (offset & notbinsize[bin]) >> 4;
645 else if (bin == B_PAGEPLUS)
651 while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS);
652 bit_i = pn * (PAGESIZE / 16);
656 // Don't mark bits in B_FREE pages
660 if (bin >= B_PAGE) // Cache B_PAGE and B_PAGEPLUS lookups
661 pcache = cast(size_t)p & ~(PAGESIZE-1);
663 if (!pool.mark.test(bit_i))
665 pool.mark.set(bit_i);
666 if (!pool.noscan.test(bit_i))
668 pool.scan.set(bit_i);
676 gc.any_changes = true;
680 * Return number of full pages free'd.
682 size_t fullcollectshell()
684 gc.stats.collection_started();
686 gc.stats.collection_finished();
688 // The purpose of the 'shell' is to ensure all the registers
689 // get put on the stack so they'll be scanned
694 gcc.builtins.__builtin_unwind_init();
701 uint eax,ecx,edx,ebx,ebp,esi,edi;
714 else version (X86_64)
716 ulong rax,rbx,rcx,rdx,rbp,rsi,rdi,r8,r9,r10,r11,r12,r13,r14,r15;
739 static assert( false, "Architecture not supported." );
750 result = fullcollect(sp);
773 size_t fullcollect(void *stackTop)
778 debug(COLLECT_PRINTF) printf("Gcx.fullcollect()\n");
781 gc.stats.world_stopped();
786 gc.any_changes = false;
787 for (n = 0; n < gc.pools.length; n++)
792 pool.freebits.zero();
795 // Mark each free entry, so it doesn't get scanned
796 for (n = 0; n < B_PAGE; n++)
798 for (List *list = gc.free_list[n]; list; list = list.next)
800 pool = findPool(list);
802 pool.freebits.set(cast(size_t)(cast(byte*)list - pool.baseAddr) / 16);
806 for (n = 0; n < gc.pools.length; n++)
809 pool.mark.copy(&pool.freebits);
812 void mark_conservative_dg(void* pbot, void* ptop)
814 mark_conservative(pbot, ptop);
817 rt_scanStaticData(&mark_conservative_dg);
821 // Scan stacks and registers for each paused thread
822 thread_scanAll(&mark_conservative_dg, stackTop);
826 debug(COLLECT_PRINTF) printf("scan roots[]\n");
827 mark_conservative(gc.roots.ptr, gc.roots.ptr + gc.roots.length);
830 debug(COLLECT_PRINTF) printf("scan ranges[]\n");
831 for (n = 0; n < gc.ranges.length; n++)
833 debug(COLLECT_PRINTF) printf("\t%x .. %x\n", gc.ranges[n].pbot, gc.ranges[n].ptop);
834 mark_conservative(gc.ranges[n].pbot, gc.ranges[n].ptop);
837 debug(COLLECT_PRINTF) printf("\tscan heap\n");
838 while (gc.any_changes)
840 gc.any_changes = false;
841 for (n = 0; n < gc.pools.length; n++)
849 bbase = pool.scan.base();
850 btop = bbase + pool.scan.nwords;
851 for (b = bbase; b < btop;)
867 o = pool.baseAddr + (b - bbase) * 32 * 16;
868 if (!(bitm & 0xFFFF))
873 for (; bitm; o += 16, bitm >>= 1)
878 pn = cast(size_t)(o - pool.baseAddr) / PAGESIZE;
879 bin = cast(Bins)pool.pagetable[pn];
881 if (opts.options.conservative)
882 mark_conservative(o, o + binsize[bin]);
884 auto end_of_blk = cast(size_t**)(o +
885 binsize[bin] - size_t.sizeof);
886 size_t* pm_bitmask = *end_of_blk;
887 mark(o, end_of_blk, pm_bitmask);
890 else if (bin == B_PAGE || bin == B_PAGEPLUS)
892 if (bin == B_PAGEPLUS)
894 while (pool.pagetable[pn - 1] != B_PAGE)
898 while (pn + u < pool.npages &&
899 pool.pagetable[pn + u] == B_PAGEPLUS)
902 size_t blk_size = u * PAGESIZE;
903 if (opts.options.conservative)
904 mark_conservative(o, o + blk_size);
906 auto end_of_blk = cast(size_t**)(o + blk_size -
908 size_t* pm_bitmask = *end_of_blk;
909 mark(o, end_of_blk, pm_bitmask);
918 gc.stats.world_started();
920 // Free up everything not marked
921 debug(COLLECT_PRINTF) printf("\tfree'ing\n");
922 size_t freedpages = 0;
924 for (n = 0; n < gc.pools.length; n++)
927 uint* bbase = pool.mark.base();
929 for (pn = 0; pn < pool.npages; pn++, bbase += PAGESIZE / (32 * 16))
931 Bins bin = cast(Bins)pool.pagetable[pn];
935 auto size = binsize[bin];
936 byte* p = pool.baseAddr + pn * PAGESIZE;
937 byte* ptop = p + PAGESIZE;
938 size_t bit_i = pn * (PAGESIZE/16);
939 size_t bit_stride = size / 16;
941 version(none) // BUG: doesn't work because freebits() must also be cleared
943 // If free'd entire page
944 if (bbase[0] == 0 && bbase[1] == 0 && bbase[2] == 0 &&
945 bbase[3] == 0 && bbase[4] == 0 && bbase[5] == 0 &&
946 bbase[6] == 0 && bbase[7] == 0)
948 for (; p < ptop; p += size, bit_i += bit_stride)
950 if (pool.finals.nbits && pool.finals.testClear(bit_i)) {
951 if (opts.options.sentinel)
952 rt_finalize(cast(List *)sentinel_add(p), false/*gc.no_stack > 0*/);
954 rt_finalize(cast(List *)p, false/*gc.no_stack > 0*/);
956 clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
958 List *list = cast(List *)p;
960 if (opts.options.mem_stomp)
961 memset(p, 0xF3, size);
963 pool.pagetable[pn] = B_FREE;
968 for (; p < ptop; p += size, bit_i += bit_stride)
970 if (!pool.mark.test(bit_i))
972 if (opts.options.sentinel)
973 sentinel_Invariant(sentinel_add(p));
975 pool.freebits.set(bit_i);
976 if (pool.finals.nbits && pool.finals.testClear(bit_i)) {
977 if (opts.options.sentinel)
978 rt_finalize(cast(List *)sentinel_add(p), false/*gc.no_stack > 0*/);
980 rt_finalize(cast(List *)p, false/*gc.no_stack > 0*/);
982 clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
984 List *list = cast(List *)p;
986 if (opts.options.mem_stomp)
987 memset(p, 0xF3, size);
993 else if (bin == B_PAGE)
995 size_t bit_i = pn * (PAGESIZE / 16);
996 if (!pool.mark.test(bit_i))
998 byte *p = pool.baseAddr + pn * PAGESIZE;
999 if (opts.options.sentinel)
1000 sentinel_Invariant(sentinel_add(p));
1001 if (pool.finals.nbits && pool.finals.testClear(bit_i)) {
1002 if (opts.options.sentinel)
1003 rt_finalize(sentinel_add(p), false/*gc.no_stack > 0*/);
1005 rt_finalize(p, false/*gc.no_stack > 0*/);
1007 clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
1009 debug(COLLECT_PRINTF) printf("\tcollecting big %x\n", p);
1010 pool.pagetable[pn] = B_FREE;
1012 if (opts.options.mem_stomp)
1013 memset(p, 0xF3, PAGESIZE);
1014 while (pn + 1 < pool.npages && pool.pagetable[pn + 1] == B_PAGEPLUS)
1017 pool.pagetable[pn] = B_FREE;
1020 if (opts.options.mem_stomp)
1023 memset(p, 0xF3, PAGESIZE);
1032 gc.free_list[] = null;
1034 // Free complete pages, rebuild free list
1035 debug(COLLECT_PRINTF) printf("\tfree complete pages\n");
1036 size_t recoveredpages = 0;
1037 for (n = 0; n < gc.pools.length; n++)
1040 for (size_t pn = 0; pn < pool.npages; pn++)
1042 Bins bin = cast(Bins)pool.pagetable[pn];
1048 size_t size = binsize[bin];
1049 size_t bit_stride = size / 16;
1050 size_t bit_base = pn * (PAGESIZE / 16);
1051 size_t bit_top = bit_base + (PAGESIZE / 16);
1055 for (; bit_i < bit_top; bit_i += bit_stride)
1057 if (!pool.freebits.test(bit_i))
1060 pool.pagetable[pn] = B_FREE;
1065 p = pool.baseAddr + pn * PAGESIZE;
1066 for (u = 0; u < PAGESIZE; u += size)
1068 bit_i = bit_base + u / 16;
1069 if (pool.freebits.test(bit_i))
1071 List *list = cast(List *)(p + u);
1072 // avoid unnecessary writes
1073 if (list.next != gc.free_list[bin])
1074 list.next = gc.free_list[bin];
1075 gc.free_list[bin] = list;
1082 debug(COLLECT_PRINTF) printf("recovered pages = %d\n", recoveredpages);
1083 debug(COLLECT_PRINTF) printf("\tfree'd %u bytes, %u pages from %u pools\n", freed, freedpages, gc.pools.length);
1085 return freedpages + recoveredpages;
1092 uint getAttr(Pool* pool, size_t bit_i)
1101 if (pool.finals.nbits &&
1102 pool.finals.test(bit_i))
1103 attrs |= BlkAttr.FINALIZE;
1104 if (pool.noscan.test(bit_i))
1105 attrs |= BlkAttr.NO_SCAN;
1106 // if (pool.nomove.nbits &&
1107 // pool.nomove.test(bit_i))
1108 // attrs |= BlkAttr.NO_MOVE;
1116 void setAttr(Pool* pool, size_t bit_i, uint mask)
1123 if (mask & BlkAttr.FINALIZE)
1125 if (!pool.finals.nbits)
1126 pool.finals.alloc(pool.mark.nbits);
1127 pool.finals.set(bit_i);
1129 if (mask & BlkAttr.NO_SCAN)
1131 pool.noscan.set(bit_i);
1133 // if (mask & BlkAttr.NO_MOVE)
1135 // if (!pool.nomove.nbits)
1136 // pool.nomove.alloc(pool.mark.nbits);
1137 // pool.nomove.set(bit_i);
1145 void clrAttr(Pool* pool, size_t bit_i, uint mask)
1152 if (mask & BlkAttr.FINALIZE && pool.finals.nbits)
1153 pool.finals.clear(bit_i);
1154 if (mask & BlkAttr.NO_SCAN)
1155 pool.noscan.clear(bit_i);
1156 // if (mask & BlkAttr.NO_MOVE && pool.nomove.nbits)
1157 // pool.nomove.clear(bit_i);
1165 gc.stack_bottom = cast(char*)&dummy;
1166 opts.parse(cstdlib.getenv("D_GC_OPTS"));
1167 gc.lock = GCLock.classinfo;
1169 setStackBottom(rt_stackBottom());
1170 gc.stats = Stats(gc);
1177 private void *malloc(size_t size, uint attrs, size_t* pm_bitmask)
1181 gc.stats.malloc_started(size, attrs, pm_bitmask);
1183 gc.stats.malloc_finished(p);
1188 if (opts.options.sentinel)
1189 size += SENTINEL_EXTRA;
1191 bool has_pm = has_pointermap(attrs);
1193 size += size_t.sizeof;
1196 // Cache previous binsize lookup - Dave Fladebo.
1197 static size_t lastsize = -1;
1198 static Bins lastbin;
1199 if (size == lastsize)
1203 bin = findBin(size);
1208 size_t capacity; // to figure out where to store the bitmask
1211 p = gc.free_list[bin];
1214 if (!allocPage(bin) && !gc.disabled) // try to find a new page
1216 if (!thread_needLock())
1218 /* Then we haven't locked it yet. Be sure
1219 * and gc.lock for a collection, since a finalizer
1220 * may start a new thread.
1222 synchronized (gc.lock)
1227 else if (!fullcollectshell()) // collect to find a new page
1232 if (!gc.free_list[bin] && !allocPage(bin))
1234 newPool(1); // allocate new pool to find a new page
1235 int result = allocPage(bin);
1237 onOutOfMemoryError();
1239 p = gc.free_list[bin];
1241 capacity = binsize[bin];
1243 // Return next item from free list
1244 gc.free_list[bin] = (cast(List*)p).next;
1245 if (!(attrs & BlkAttr.NO_SCAN))
1246 memset(p + size, 0, capacity - size);
1247 if (opts.options.mem_stomp)
1248 memset(p, 0xF0, size);
1254 onOutOfMemoryError();
1255 // Round the size up to the number of pages needed to store it
1256 size_t npages = (size + PAGESIZE - 1) / PAGESIZE;
1257 capacity = npages * PAGESIZE;
1260 // Store the bit mask AFTER SENTINEL_POST
1261 // TODO: store it BEFORE, so the bitmask is protected too
1263 auto end_of_blk = cast(size_t**)(p + capacity - size_t.sizeof);
1264 *end_of_blk = pm_bitmask;
1265 size -= size_t.sizeof;
1268 if (opts.options.sentinel) {
1269 size -= SENTINEL_EXTRA;
1270 p = sentinel_add(p);
1271 sentinel_init(p, size);
1276 Pool *pool = findPool(p);
1279 setAttr(pool, cast(size_t)(p - pool.baseAddr) / 16, attrs);
1288 private void *calloc(size_t size, uint attrs, size_t* pm_bitmask)
1292 void *p = malloc(size, attrs, pm_bitmask);
1301 private void *realloc(void *p, size_t size, uint attrs,
1314 p = malloc(size, attrs, pm_bitmask);
1318 Pool* pool = findPool(p);
1322 // Set or retrieve attributes as appropriate
1323 auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
1325 clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
1326 setAttr(pool, bit_i, attrs);
1329 attrs = getAttr(pool, bit_i);
1331 void* blk_base_addr = pool.findBase(p);
1332 size_t blk_size = pool.findSize(p);
1333 bool has_pm = has_pointermap(attrs);
1334 size_t pm_bitmask_size = 0;
1336 pm_bitmask_size = size_t.sizeof;
1337 // Retrieve pointer map bit mask if appropriate
1338 if (pm_bitmask is null) {
1339 auto end_of_blk = cast(size_t**)(blk_base_addr +
1340 blk_size - size_t.sizeof);
1341 pm_bitmask = *end_of_blk;
1345 if (opts.options.sentinel)
1347 sentinel_Invariant(p);
1348 size_t sentinel_stored_size = *sentinel_size(p);
1349 if (sentinel_stored_size != size)
1351 void* p2 = malloc(size, attrs, pm_bitmask);
1352 if (sentinel_stored_size < size)
1353 size = sentinel_stored_size;
1354 cstring.memcpy(p2, p, size);
1360 size += pm_bitmask_size;
1361 if (blk_size >= PAGESIZE && size >= PAGESIZE)
1363 auto psz = blk_size / PAGESIZE;
1364 auto newsz = (size + PAGESIZE - 1) / PAGESIZE;
1368 auto pagenum = (p - pool.baseAddr) / PAGESIZE;
1373 if (opts.options.mem_stomp)
1374 memset(p + size - pm_bitmask_size, 0xF2,
1375 blk_size - size - pm_bitmask_size);
1376 pool.freePages(pagenum + newsz, psz - newsz);
1378 auto end_of_blk = cast(size_t**)(
1379 blk_base_addr + (PAGESIZE * newsz) -
1381 *end_of_blk = pm_bitmask;
1385 else if (pagenum + newsz <= pool.npages)
1387 // Attempt to expand in place
1388 for (size_t i = pagenum + psz; 1;)
1390 if (i == pagenum + newsz)
1392 if (opts.options.mem_stomp)
1393 memset(p + blk_size - pm_bitmask_size,
1394 0xF0, size - blk_size
1396 memset(pool.pagetable + pagenum +
1397 psz, B_PAGEPLUS, newsz - psz);
1399 auto end_of_blk = cast(size_t**)(
1401 (PAGESIZE * newsz) -
1403 *end_of_blk = pm_bitmask;
1407 if (i == pool.npages)
1411 if (pool.pagetable[i] != B_FREE)
1417 // if new size is bigger or less than half
1418 if (blk_size < size || blk_size > size * 2)
1420 size -= pm_bitmask_size;
1421 blk_size -= pm_bitmask_size;
1422 void* p2 = malloc(size, attrs, pm_bitmask);
1423 if (blk_size < size)
1425 cstring.memcpy(p2, p, size);
1435 * Attempt to in-place enlarge the memory block pointed to by p by at least
1436 * min_size beyond its current capacity, up to a maximum of max_size. This
1437 * does not attempt to move the memory block (like realloc() does).
1440 * 0 if could not extend p,
1441 * total size of entire memory block if successful.
1443 private size_t extend(void* p, size_t minsize, size_t maxsize)
1446 assert( minsize <= maxsize );
1450 if (opts.options.sentinel)
1453 Pool* pool = findPool(p);
1457 // Retrieve attributes
1458 auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
1459 uint attrs = getAttr(pool, bit_i);
1461 void* blk_base_addr = pool.findBase(p);
1462 size_t blk_size = pool.findSize(p);
1463 bool has_pm = has_pointermap(attrs);
1464 size_t* pm_bitmask = null;
1465 size_t pm_bitmask_size = 0;
1467 pm_bitmask_size = size_t.sizeof;
1468 // Retrieve pointer map bit mask
1469 auto end_of_blk = cast(size_t**)(blk_base_addr +
1470 blk_size - size_t.sizeof);
1471 pm_bitmask = *end_of_blk;
1473 minsize += size_t.sizeof;
1474 maxsize += size_t.sizeof;
1477 if (blk_size < PAGESIZE)
1478 return 0; // cannot extend buckets
1480 auto psz = blk_size / PAGESIZE;
1481 auto minsz = (minsize + PAGESIZE - 1) / PAGESIZE;
1482 auto maxsz = (maxsize + PAGESIZE - 1) / PAGESIZE;
1484 auto pagenum = (p - pool.baseAddr) / PAGESIZE;
1487 for (sz = 0; sz < maxsz; sz++)
1489 auto i = pagenum + psz + sz;
1490 if (i == pool.npages)
1492 if (pool.pagetable[i] != B_FREE)
1502 size_t new_size = (psz + sz) * PAGESIZE;
1504 if (opts.options.mem_stomp)
1505 memset(p + blk_size - pm_bitmask_size, 0xF0,
1506 new_size - blk_size - pm_bitmask_size);
1507 memset(pool.pagetable + pagenum + psz, B_PAGEPLUS, sz);
1512 new_size -= size_t.sizeof;
1513 auto end_of_blk = cast(size_t**)(blk_base_addr + new_size);
1514 *end_of_blk = pm_bitmask;
1523 private void free(void *p)
1532 // Find which page it is in
1534 if (!pool) // if not one of ours
1536 if (opts.options.sentinel) {
1537 sentinel_Invariant(p);
1538 p = sentinel_sub(p);
1540 pagenum = cast(size_t)(p - pool.baseAddr) / PAGESIZE;
1541 bit_i = cast(size_t)(p - pool.baseAddr) / 16;
1542 clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
1544 bin = cast(Bins)pool.pagetable[pagenum];
1545 if (bin == B_PAGE) // if large alloc
1550 while (++n < pool.npages && pool.pagetable[n] == B_PAGEPLUS)
1552 if (opts.options.mem_stomp)
1553 memset(p, 0xF2, npages * PAGESIZE);
1554 pool.freePages(pagenum, npages);
1559 List *list = cast(List*)p;
1561 if (opts.options.mem_stomp)
1562 memset(p, 0xF2, binsize[bin]);
1564 list.next = gc.free_list[bin];
1565 gc.free_list[bin] = list;
1571 * Determine the allocated size of pointer p. If p is an interior pointer
1572 * or not a gc allocated pointer, return 0.
1574 private size_t sizeOf(void *p)
1578 if (opts.options.sentinel)
1579 p = sentinel_sub(p);
1581 Pool* pool = findPool(p);
1585 auto biti = cast(size_t)(p - pool.baseAddr) / 16;
1586 uint attrs = getAttr(pool, biti);
1588 size_t size = pool.findSize(p);
1589 size_t pm_bitmask_size = 0;
1590 if (has_pointermap(attrs))
1591 pm_bitmask_size = size_t.sizeof;
1593 if (opts.options.sentinel) {
1594 // Check for interior pointer
1596 // 1) size is a power of 2 for less than PAGESIZE values
1597 // 2) base of memory pool is aligned on PAGESIZE boundary
1598 if (cast(size_t)p & (size - 1) & (PAGESIZE - 1))
1600 return size - SENTINEL_EXTRA - pm_bitmask_size;
1603 if (p == gc.p_cache)
1604 return gc.size_cache;
1606 // Check for interior pointer
1608 // 1) size is a power of 2 for less than PAGESIZE values
1609 // 2) base of memory pool is aligned on PAGESIZE boundary
1610 if (cast(size_t)p & (size - 1) & (PAGESIZE - 1))
1614 gc.size_cache = size - pm_bitmask_size;
1616 return gc.size_cache;
1622 * Verify that pointer p:
1623 * 1) belongs to this memory pool
1624 * 2) points to the start of an allocated piece of memory
1625 * 3) is not on a free list
1627 private void checkNoSync(void *p)
1631 if (opts.options.sentinel)
1632 sentinel_Invariant(p);
1640 if (opts.options.sentinel)
1641 p = sentinel_sub(p);
1644 pagenum = cast(size_t)(p - pool.baseAddr) / PAGESIZE;
1645 bin = cast(Bins)pool.pagetable[pagenum];
1646 assert(bin <= B_PAGE);
1647 size = binsize[bin];
1648 assert((cast(size_t)p & (size - 1)) == 0);
1654 // Check that p is not on a free list
1657 for (list = gc.free_list[bin]; list; list = list.next)
1659 assert(cast(void*)list != p);
1670 private void setStackBottom(void *p)
1672 version (STACKGROWSDOWN)
1674 //p = (void *)((uint *)p + 4);
1675 if (p > gc.stack_bottom)
1677 gc.stack_bottom = p;
1682 //p = (void *)((uint *)p - 4);
1683 if (p < gc.stack_bottom)
1685 gc.stack_bottom = cast(char*)p;
1692 * Retrieve statistics about garbage collection.
1693 * Useful for debugging and tuning.
1695 private GCStats getStats()
1705 for (n = 0; n < gc.pools.length; n++)
1707 Pool* pool = gc.pools[n];
1708 psize += pool.npages * PAGESIZE;
1709 for (size_t j = 0; j < pool.npages; j++)
1711 Bins bin = cast(Bins)pool.pagetable[j];
1714 else if (bin == B_PAGE)
1716 else if (bin < B_PAGE)
1721 for (n = 0; n < B_PAGE; n++)
1723 for (List *list = gc.free_list[n]; list; list = list.next)
1724 flsize += binsize[n];
1727 usize = bsize - flsize;
1729 stats.poolsize = psize;
1730 stats.usedsize = bsize - flsize;
1731 stats.freelistsize = flsize;
1735 /******************* weak-reference support *********************/
1737 private struct WeakPointer
1741 void ondestroy(Object r)
1743 assert(r is reference);
1744 // lock for memory consistency (parallel readers)
1745 // also ensures that weakpointerDestroy can be called while another
1746 // thread is freeing the reference with "delete"
1747 return locked!(void, () {
1754 * Create a weak pointer to the given object.
1755 * Returns a pointer to an opaque struct allocated in C memory.
1757 void* weakpointerCreate( Object r )
1761 // must be allocated in C memory
1762 // 1. to hide the reference from the GC
1763 // 2. the GC doesn't scan delegates added by rt_attachDisposeEvent
1765 auto wp = cast(WeakPointer*)(cstdlib.malloc(WeakPointer.sizeof));
1767 onOutOfMemoryError();
1769 rt_attachDisposeEvent(r, &wp.ondestroy);
1776 * Destroy a weak pointer returned by weakpointerCreate().
1777 * If null is passed, nothing happens.
1779 void weakpointerDestroy( void* p )
1783 auto wp = cast(WeakPointer*)p;
1784 // must be extra careful about the GC or parallel threads
1785 // finalizing the reference at the same time
1786 return locked!(void, () {
1788 rt_detachDisposeEvent(wp.reference, &wp.ondestroy);
1795 * Query a weak pointer and return either the object passed to
1796 * weakpointerCreate, or null if it was free'd in the meantime.
1797 * If null is passed, null is returned.
1799 Object weakpointerGet( void* p )
1803 // NOTE: could avoid the lock by using Fawzi style GC counters but
1804 // that'd require core.sync.Atomic and lots of care about memory
1805 // consistency it's an optional optimization see
1806 // http://dsource.org/projects/tango/browser/trunk/user/tango/core/Lifetime.d?rev=5100#L158
1807 return locked!(Object, () {
1808 return (cast(WeakPointer*)p).reference;
1814 /* ============================ Pool =============================== */
1821 GCBits mark; // entries already scanned, or should not be scanned
1822 GCBits scan; // entries that need to be scanned
1823 GCBits freebits; // entries that are on the free list
1824 GCBits finals; // entries that need finalizer run on them
1825 GCBits noscan; // entries that should not be scanned
1831 void initialize(size_t npages)
1833 size_t poolsize = npages * PAGESIZE;
1834 assert(poolsize >= POOLSIZE);
1835 baseAddr = cast(byte *) alloc.os_mem_map(poolsize);
1837 // Some of the code depends on page alignment of memory pools
1838 assert((cast(size_t)baseAddr & (PAGESIZE - 1)) == 0);
1846 topAddr = baseAddr + poolsize;
1848 mark.alloc(cast(size_t)poolsize / 16);
1849 scan.alloc(cast(size_t)poolsize / 16);
1850 freebits.alloc(cast(size_t)poolsize / 16);
1851 noscan.alloc(cast(size_t)poolsize / 16);
1853 pagetable = cast(ubyte*) cstdlib.malloc(npages);
1855 onOutOfMemoryError();
1856 memset(pagetable, B_FREE, npages);
1858 this.npages = npages;
1870 result = alloc.os_mem_unmap(baseAddr, npages * PAGESIZE);
1878 // See Gcx.Dtor() for the rationale of the null check.
1880 cstdlib.free(pagetable);
1900 //freebits.Invariant();
1901 //finals.Invariant();
1902 //noscan.Invariant();
1906 //if (baseAddr + npages * PAGESIZE != topAddr)
1907 //printf("baseAddr = %p, npages = %d, topAddr = %p\n", baseAddr, npages, topAddr);
1908 assert(baseAddr + npages * PAGESIZE == topAddr);
1911 for (size_t i = 0; i < npages; i++)
1913 Bins bin = cast(Bins)pagetable[i];
1914 assert(bin < B_MAX);
1920 * Allocate n pages from Pool.
1921 * Returns OPFAIL on failure.
1923 size_t allocPages(size_t n)
1929 for (i = 0; i < npages; i++)
1931 if (pagetable[i] == B_FREE)
1944 * Free npages pages starting with pagenum.
1946 void freePages(size_t pagenum, size_t npages)
1948 memset(&pagetable[pagenum], B_FREE, npages);
1953 * Find base address of block containing pointer p.
1954 * Returns null if the pointer doesn't belong to this pool
1956 void* findBase(void *p)
1958 size_t offset = cast(size_t)(p - this.baseAddr);
1959 size_t pagenum = offset / PAGESIZE;
1960 Bins bin = cast(Bins)this.pagetable[pagenum];
1961 // Adjust bit to be at start of allocated memory block
1963 return this.baseAddr + (offset & notbinsize[bin]);
1964 if (bin == B_PAGEPLUS) {
1966 --pagenum, offset -= PAGESIZE;
1967 } while (cast(Bins)this.pagetable[pagenum] == B_PAGEPLUS);
1968 return this.baseAddr + (offset & (offset.max ^ (PAGESIZE-1)));
1970 // we are in a B_FREE page
1976 * Find size of pointer p.
1977 * Returns 0 if p doesn't belong to this pool if if it's block size is less
1980 size_t findSize(void *p)
1982 size_t pagenum = cast(size_t)(p - this.baseAddr) / PAGESIZE;
1983 Bins bin = cast(Bins)this.pagetable[pagenum];
1985 return binsize[bin];
1986 for (size_t i = pagenum + 1; i < this.npages; i++)
1987 if (this.pagetable[i] != B_PAGEPLUS)
1988 return (i - pagenum) * PAGESIZE;
1989 return (this.npages - pagenum) * PAGESIZE;
1994 * Used for sorting pools
1996 int opCmp(in Pool other)
1998 if (baseAddr < other.baseAddr)
2001 return cast(int)(baseAddr > other.baseAddr);
2006 /* ============================ SENTINEL =============================== */
2009 const size_t SENTINEL_PRE = cast(size_t) 0xF4F4F4F4F4F4F4F4UL; // 32 or 64 bits
2010 const ubyte SENTINEL_POST = 0xF5; // 8 bits
2011 const uint SENTINEL_EXTRA = 2 * size_t.sizeof + 1;
2014 size_t* sentinel_size(void *p) { return &(cast(size_t *)p)[-2]; }
2015 size_t* sentinel_pre(void *p) { return &(cast(size_t *)p)[-1]; }
2016 ubyte* sentinel_post(void *p) { return &(cast(ubyte *)p)[*sentinel_size(p)]; }
2019 void sentinel_init(void *p, size_t size)
2021 *sentinel_size(p) = size;
2022 *sentinel_pre(p) = SENTINEL_PRE;
2023 *sentinel_post(p) = SENTINEL_POST;
2027 void sentinel_Invariant(void *p)
2029 assert(*sentinel_pre(p) == SENTINEL_PRE);
2030 assert(*sentinel_post(p) == SENTINEL_POST);
2034 void *sentinel_add(void *p)
2036 return p + 2 * size_t.sizeof;
2040 void *sentinel_sub(void *p)
2042 return p - 2 * size_t.sizeof;
2047 /* ============================ C Public Interface ======================== */
2050 private int _termCleanupLevel=1;
2054 /// sets the cleanup level done by gc
2057 /// 2: fullCollect ignoring stack roots (might crash daemonThreads)
2058 /// result !=0 if the value was invalid
2059 int gc_setTermCleanupLevel(int cLevel)
2061 if (cLevel<0 || cLevel>2) return cLevel;
2062 _termCleanupLevel=cLevel;
2066 /// returns the cleanup level done by gc
2067 int gc_getTermCleanupLevel()
2069 return _termCleanupLevel;
2074 scope (exit) assert (Invariant());
2075 gc = cast(GC*) cstdlib.calloc(1, GC.sizeof);
2078 version (DigitalMars) version(OSX) {
2079 _d_osx_image_init();
2081 // NOTE: The GC must initialize the thread library
2082 // before its first collection.
2088 assert (Invariant());
2089 if (_termCleanupLevel<1) {
2091 } else if (_termCleanupLevel==2){
2092 // a more complete cleanup
2093 // NOTE: There may be daemons threads still running when this routine is
2094 // called. If so, cleaning memory out from under then is a good
2095 // way to make them crash horribly.
2096 // Often this probably doesn't matter much since the app is
2097 // supposed to be shutting down anyway, but for example tests might
2098 // crash (and be considerd failed even if the test was ok).
2099 // thus this is not the default and should be enabled by
2100 // I'm disabling cleanup for now until I can think about it some
2103 // not really a 'collect all' -- still scans static data area, roots,
2105 return locked!(void, () {
2111 // default (safe) clenup
2112 return locked!(void, () {
2120 return locked!(void, () {
2121 assert (Invariant()); scope (exit) assert (Invariant());
2122 assert (gc.disabled > 0);
2129 return locked!(void, () {
2130 assert (Invariant()); scope (exit) assert (Invariant());
2137 return locked!(void, () {
2138 assert (Invariant()); scope (exit) assert (Invariant());
2146 return locked!(void, () {
2147 assert (Invariant()); scope (exit) assert (Invariant());
2152 uint gc_getAttr(void* p)
2156 return locked!(uint, () {
2157 assert (Invariant()); scope (exit) assert (Invariant());
2158 Pool* pool = findPool(p);
2161 auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
2162 return getAttr(pool, bit_i);
2166 uint gc_setAttr(void* p, uint attrs)
2170 return locked!(uint, () {
2171 assert (Invariant()); scope (exit) assert (Invariant());
2172 Pool* pool = findPool(p);
2175 auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
2176 uint old_attrs = getAttr(pool, bit_i);
2177 setAttr(pool, bit_i, attrs);
2182 uint gc_clrAttr(void* p, uint attrs)
2186 return locked!(uint, () {
2187 assert (Invariant()); scope (exit) assert (Invariant());
2188 Pool* pool = findPool(p);
2191 auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
2192 uint old_attrs = getAttr(pool, bit_i);
2193 clrAttr(pool, bit_i, attrs);
2198 void* gc_malloc(size_t size, uint attrs = 0,
2199 PointerMap ptrmap = PointerMap.init)
2203 return locked!(void*, () {
2204 assert (Invariant()); scope (exit) assert (Invariant());
2205 return malloc(size, attrs, ptrmap.bits.ptr);
2209 void* gc_calloc(size_t size, uint attrs = 0,
2210 PointerMap ptrmap = PointerMap.init)
2214 return locked!(void*, () {
2215 assert (Invariant()); scope (exit) assert (Invariant());
2216 return calloc(size, attrs, ptrmap.bits.ptr);
2220 void* gc_realloc(void* p, size_t size, uint attrs = 0,
2221 PointerMap ptrmap = PointerMap.init)
2223 return locked!(void*, () {
2224 assert (Invariant()); scope (exit) assert (Invariant());
2225 return realloc(p, size, attrs, ptrmap.bits.ptr);
2229 size_t gc_extend(void* p, size_t min_size, size_t max_size)
2231 return locked!(size_t, () {
2232 assert (Invariant()); scope (exit) assert (Invariant());
2233 return extend(p, min_size, max_size);
2237 size_t gc_reserve(size_t size)
2241 return locked!(size_t, () {
2242 assert (Invariant()); scope (exit) assert (Invariant());
2243 return reserve(size);
2247 void gc_free(void* p)
2251 return locked!(void, () {
2252 assert (Invariant()); scope (exit) assert (Invariant());
2257 void* gc_addrOf(void* p)
2261 return locked!(void*, () {
2262 assert (Invariant()); scope (exit) assert (Invariant());
2263 Pool* pool = findPool(p);
2266 return pool.findBase(p);
2270 size_t gc_sizeOf(void* p)
2274 return locked!(size_t, () {
2275 assert (Invariant()); scope (exit) assert (Invariant());
2280 BlkInfo gc_query(void* p)
2283 return BlkInfo.init;
2284 return locked!(BlkInfo, () {
2285 assert (Invariant()); scope (exit) assert (Invariant());
2290 // NOTE: This routine is experimental. The stats or function name may change
2291 // before it is made officially available.
2294 return locked!(GCStats, () {
2295 assert (Invariant()); scope (exit) assert (Invariant());
2300 void gc_addRoot(void* p)
2304 return locked!(void, () {
2305 assert (Invariant()); scope (exit) assert (Invariant());
2306 if (gc.roots.append(p) is null)
2307 onOutOfMemoryError();
2311 void gc_addRange(void* p, size_t size)
2313 if (p is null || size == 0)
2315 return locked!(void, () {
2316 assert (Invariant()); scope (exit) assert (Invariant());
2317 if (gc.ranges.append(Range(p, p + size)) is null)
2318 onOutOfMemoryError();
2322 void gc_removeRoot(void* p)
2326 return locked!(void, () {
2327 assert (Invariant()); scope (exit) assert (Invariant());
2328 bool r = gc.roots.remove(p);
2333 void gc_removeRange(void* p)
2337 return locked!(void, () {
2338 assert (Invariant()); scope (exit) assert (Invariant());
2339 bool r = gc.ranges.remove(Range(p, null));
2344 void* gc_weakpointerCreate(Object r)
2346 // weakpointers do their own locking
2347 return weakpointerCreate(r);
2350 void gc_weakpointerDestroy(void* wp)
2352 // weakpointers do their own locking
2353 weakpointerDestroy(wp);
2356 Object gc_weakpointerGet(void* wp)
2358 // weakpointers do their own locking
2359 return weakpointerGet(wp);
2363 // vim: set et sw=4 sts=4 :