1 /**
2 * Contains the garbage collector implementation.
3 *
4 * Copyright: Copyright Digital Mars 2001 - 2016.
5 * License: $(WEB www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
6 * Authors: Walter Bright, David Friedman, Sean Kelly
7 */
8
9 /* Copyright Digital Mars 2005 - 2016.
10 * Distributed under the Boost Software License, Version 1.0.
11 * (See accompanying file LICENSE or copy at
12 * http://www.boost.org/LICENSE_1_0.txt)
13 */
14 module gc.impl.conservative.gc;
15
16 // D Programming Language Garbage Collector implementation
17
18 /************** Debugging ***************************/
19
20 //debug = PRINTF; // turn on printf's
21 //debug = COLLECT_PRINTF; // turn on printf's
22 //debug = PRINTF_TO_FILE; // redirect printf's ouptut to file "gcx.log"
23 //debug = LOGGING; // log allocations / frees
24 //debug = MEMSTOMP; // stomp on memory
25 //debug = SENTINEL; // add underrun/overrrun protection
26 // NOTE: this needs to be enabled globally in the makefiles
27 // (-debug=SENTINEL) to pass druntime's unittests.
28 //debug = PTRCHECK; // more pointer checking
29 //debug = PTRCHECK2; // thorough but slow pointer checking
30 //debug = INVARIANT; // enable invariants
31 //debug = PROFILE_API; // profile API calls for config.profile > 1
32
33 /***************************************************/
34
35 import gc.bits;
36 import gc.os;
37 import gc.config;
38 import gc.gcinterface;
39
40 import rt.util.container.treap;
41
42 import cstdlib = core.stdc.stdlib : calloc, free, malloc, realloc;
43 import core.stdc.string : memcpy, memset, memmove;
44 import core.bitop;
45 import core.thread;
46 static import core.memory;
47
48 version (GNU) import gcc.builtins;
49
50 debug (PRINTF_TO_FILE) import core.stdc.stdio : sprintf, fprintf, fopen, fflush, FILE;
51 else import core.stdc.stdio : sprintf, printf; // needed to output profiling results
52
53 import core.time;
54 alias currTime = MonoTime.currTime;
55
debug(PRINTF_TO_FILE)56 debug(PRINTF_TO_FILE)
57 {
58 private __gshared MonoTime gcStartTick;
59 private __gshared FILE* gcx_fh;
60
61 private int printf(ARGS...)(const char* fmt, ARGS args) nothrow
62 {
63 if (!gcx_fh)
64 gcx_fh = fopen("gcx.log", "w");
65 if (!gcx_fh)
66 return 0;
67
68 int len;
69 if (MonoTime.ticksPerSecond == 0)
70 {
71 len = fprintf(gcx_fh, "before init: ");
72 }
73 else
74 {
75 if (gcStartTick == MonoTime.init)
76 gcStartTick = MonoTime.currTime;
77 immutable timeElapsed = MonoTime.currTime - gcStartTick;
78 immutable secondsAsDouble = timeElapsed.total!"hnsecs" / cast(double)convert!("seconds", "hnsecs")(1);
79 len = fprintf(gcx_fh, "%10.6lf: ", secondsAsDouble);
80 }
81 len += fprintf(gcx_fh, fmt, args);
82 fflush(gcx_fh);
83 return len;
84 }
85 }
86
debug(PRINTF)87 debug(PRINTF) void printFreeInfo(Pool* pool) nothrow
88 {
89 uint nReallyFree;
90 foreach (i; 0..pool.npages) {
91 if (pool.pagetable[i] >= B_FREE) nReallyFree++;
92 }
93
94 printf("Pool %p: %d really free, %d supposedly free\n", pool, nReallyFree, pool.freepages);
95 }
96
97 // Track total time spent preparing for GC,
98 // marking, sweeping and recovering pages.
99 __gshared Duration prepTime;
100 __gshared Duration markTime;
101 __gshared Duration sweepTime;
102 __gshared Duration recoverTime;
103 __gshared Duration maxPauseTime;
104 __gshared size_t numCollections;
105 __gshared size_t maxPoolMemory;
106
107 __gshared long numMallocs;
108 __gshared long numFrees;
109 __gshared long numReallocs;
110 __gshared long numExtends;
111 __gshared long numOthers;
112 __gshared long mallocTime; // using ticks instead of MonoTime for better performance
113 __gshared long freeTime;
114 __gshared long reallocTime;
115 __gshared long extendTime;
116 __gshared long otherTime;
117 __gshared long lockTime;
118
119 private
120 {
121 extern (C)
122 {
123 // to allow compilation of this module without access to the rt package,
124 // make these functions available from rt.lifetime
125 void rt_finalizeFromGC(void* p, size_t size, uint attr) nothrow;
126 int rt_hasFinalizerInSegment(void* p, size_t size, uint attr, in void[] segment) nothrow;
127
128 // Declared as an extern instead of importing core.exception
129 // to avoid inlining - see issue 13725.
130 void onInvalidMemoryOperationError() @nogc nothrow;
131 void onOutOfMemoryErrorNoGC() @nogc nothrow;
132 }
133
134 enum
135 {
136 OPFAIL = ~cast(size_t)0
137 }
138 }
139
140
141 alias GC gc_t;
142
143
144 /* ======================= Leak Detector =========================== */
145
146
147 debug (LOGGING)
148 {
149 struct Log
150 {
151 void* p;
152 size_t size;
153 size_t line;
154 char* file;
155 void* parent;
156
157 void print() nothrow
158 {
159 printf(" p = %p, size = %zd, parent = %p ", p, size, parent);
160 if (file)
161 {
162 printf("%s(%u)", file, line);
163 }
164 printf("\n");
165 }
166 }
167
168
169 struct LogArray
170 {
171 size_t dim;
172 size_t allocdim;
173 Log *data;
174
175 void Dtor() nothrow
176 {
177 if (data)
178 cstdlib.free(data);
179 data = null;
180 }
181
182 void reserve(size_t nentries) nothrow
183 {
184 assert(dim <= allocdim);
185 if (allocdim - dim < nentries)
186 {
187 allocdim = (dim + nentries) * 2;
188 assert(dim + nentries <= allocdim);
189 if (!data)
190 {
191 data = cast(Log*)cstdlib.malloc(allocdim * Log.sizeof);
192 if (!data && allocdim)
193 onOutOfMemoryErrorNoGC();
194 }
195 else
196 { Log *newdata;
197
198 newdata = cast(Log*)cstdlib.malloc(allocdim * Log.sizeof);
199 if (!newdata && allocdim)
200 onOutOfMemoryErrorNoGC();
201 memcpy(newdata, data, dim * Log.sizeof);
202 cstdlib.free(data);
203 data = newdata;
204 }
205 }
206 }
207
208
209 void push(Log log) nothrow
210 {
211 reserve(1);
212 data[dim++] = log;
213 }
214
215 void remove(size_t i) nothrow
216 {
217 memmove(data + i, data + i + 1, (dim - i) * Log.sizeof);
218 dim--;
219 }
220
221
222 size_t find(void *p) nothrow
223 {
224 for (size_t i = 0; i < dim; i++)
225 {
226 if (data[i].p == p)
227 return i;
228 }
229 return OPFAIL; // not found
230 }
231
232
233 void copy(LogArray *from) nothrow
234 {
235 reserve(from.dim - dim);
236 assert(from.dim <= allocdim);
237 memcpy(data, from.data, from.dim * Log.sizeof);
238 dim = from.dim;
239 }
240 }
241 }
242
243
244 /* ============================ GC =============================== */
245
246 class ConservativeGC : GC
247 {
248 // For passing to debug code (not thread safe)
249 __gshared size_t line;
250 __gshared char* file;
251
252 Gcx *gcx; // implementation
253
254 import core.internal.spinlock;
255 static gcLock = shared(AlignedSpinLock)(SpinLock.Contention.lengthy);
256 static bool _inFinalizer;
257
258 // lock GC, throw InvalidMemoryOperationError on recursive locking during finalization
259 static void lockNR() @nogc nothrow
260 {
261 if (_inFinalizer)
262 onInvalidMemoryOperationError();
263 gcLock.lock();
264 }
265
266
267 static void initialize(ref GC gc)
268 {
269 import core.stdc.string: memcpy;
270
271 if (config.gc != "conservative")
272 return;
273
274 auto p = cstdlib.malloc(__traits(classInstanceSize,ConservativeGC));
275
276 if (!p)
277 onOutOfMemoryErrorNoGC();
278
279 auto init = typeid(ConservativeGC).initializer();
280 assert(init.length == __traits(classInstanceSize, ConservativeGC));
281 auto instance = cast(ConservativeGC) memcpy(p, init.ptr, init.length);
282 instance.__ctor();
283
284 gc = instance;
285 }
286
287
288 static void finalize(ref GC gc)
289 {
290 if (config.gc != "conservative")
291 return;
292
293 auto instance = cast(ConservativeGC) gc;
294 instance.Dtor();
295 cstdlib.free(cast(void*)instance);
296 }
297
298
299 this()
300 {
301 //config is assumed to have already been initialized
302
303 gcx = cast(Gcx*)cstdlib.calloc(1, Gcx.sizeof);
304 if (!gcx)
305 onOutOfMemoryErrorNoGC();
306 gcx.initialize();
307
308 if (config.initReserve)
309 gcx.reserve(config.initReserve << 20);
310 if (config.disable)
311 gcx.disabled++;
312 }
313
314
315 void Dtor()
316 {
317 version (linux)
318 {
319 //debug(PRINTF) printf("Thread %x ", pthread_self());
320 //debug(PRINTF) printf("GC.Dtor()\n");
321 }
322
323 if (gcx)
324 {
325 gcx.Dtor();
326 cstdlib.free(gcx);
327 gcx = null;
328 }
329 }
330
331
332 void enable()
333 {
334 static void go(Gcx* gcx) nothrow
335 {
336 assert(gcx.disabled > 0);
337 gcx.disabled--;
338 }
339 runLocked!(go, otherTime, numOthers)(gcx);
340 }
341
342
343 void disable()
344 {
345 static void go(Gcx* gcx) nothrow
346 {
347 gcx.disabled++;
348 }
349 runLocked!(go, otherTime, numOthers)(gcx);
350 }
351
352
353 auto runLocked(alias func, Args...)(auto ref Args args)
354 {
355 debug(PROFILE_API) immutable tm = (config.profile > 1 ? currTime.ticks : 0);
356 lockNR();
357 scope (failure) gcLock.unlock();
358 debug(PROFILE_API) immutable tm2 = (config.profile > 1 ? currTime.ticks : 0);
359
360 static if (is(typeof(func(args)) == void))
361 func(args);
362 else
363 auto res = func(args);
364
365 debug(PROFILE_API) if (config.profile > 1)
366 lockTime += tm2 - tm;
367 gcLock.unlock();
368
369 static if (!is(typeof(func(args)) == void))
370 return res;
371 }
372
373
374 auto runLocked(alias func, alias time, alias count, Args...)(auto ref Args args)
375 {
376 debug(PROFILE_API) immutable tm = (config.profile > 1 ? currTime.ticks : 0);
377 lockNR();
378 scope (failure) gcLock.unlock();
379 debug(PROFILE_API) immutable tm2 = (config.profile > 1 ? currTime.ticks : 0);
380
381 static if (is(typeof(func(args)) == void))
382 func(args);
383 else
384 auto res = func(args);
385
386 debug(PROFILE_API) if (config.profile > 1)
387 {
388 count++;
389 immutable now = currTime.ticks;
390 lockTime += tm2 - tm;
391 time += now - tm2;
392 }
393 gcLock.unlock();
394
395 static if (!is(typeof(func(args)) == void))
396 return res;
397 }
398
399
400 uint getAttr(void* p) nothrow
401 {
402 if (!p)
403 {
404 return 0;
405 }
406
407 static uint go(Gcx* gcx, void* p) nothrow
408 {
409 Pool* pool = gcx.findPool(p);
410 uint oldb = 0;
411
412 if (pool)
413 {
414 p = sentinel_sub(p);
415 auto biti = cast(size_t)(p - pool.baseAddr) >> pool.shiftBy;
416
417 oldb = pool.getBits(biti);
418 }
419 return oldb;
420 }
421
422 return runLocked!(go, otherTime, numOthers)(gcx, p);
423 }
424
425
426 uint setAttr(void* p, uint mask) nothrow
427 {
428 if (!p)
429 {
430 return 0;
431 }
432
433 static uint go(Gcx* gcx, void* p, uint mask) nothrow
434 {
435 Pool* pool = gcx.findPool(p);
436 uint oldb = 0;
437
438 if (pool)
439 {
440 p = sentinel_sub(p);
441 auto biti = cast(size_t)(p - pool.baseAddr) >> pool.shiftBy;
442
443 oldb = pool.getBits(biti);
444 pool.setBits(biti, mask);
445 }
446 return oldb;
447 }
448
449 return runLocked!(go, otherTime, numOthers)(gcx, p, mask);
450 }
451
452
453 uint clrAttr(void* p, uint mask) nothrow
454 {
455 if (!p)
456 {
457 return 0;
458 }
459
460 static uint go(Gcx* gcx, void* p, uint mask) nothrow
461 {
462 Pool* pool = gcx.findPool(p);
463 uint oldb = 0;
464
465 if (pool)
466 {
467 p = sentinel_sub(p);
468 auto biti = cast(size_t)(p - pool.baseAddr) >> pool.shiftBy;
469
470 oldb = pool.getBits(biti);
471 pool.clrBits(biti, mask);
472 }
473 return oldb;
474 }
475
476 return runLocked!(go, otherTime, numOthers)(gcx, p, mask);
477 }
478
479
480 void *malloc(size_t size, uint bits, const TypeInfo ti) nothrow
481 {
482 if (!size)
483 {
484 return null;
485 }
486
487 size_t localAllocSize = void;
488
489 auto p = runLocked!(mallocNoSync, mallocTime, numMallocs)(size, bits, localAllocSize, ti);
490
491 if (!(bits & BlkAttr.NO_SCAN))
492 {
493 memset(p + size, 0, localAllocSize - size);
494 }
495
496 return p;
497 }
498
499
500 //
501 //
502 //
503 private void *mallocNoSync(size_t size, uint bits, ref size_t alloc_size, const TypeInfo ti = null) nothrow
504 {
505 assert(size != 0);
506
507 //debug(PRINTF) printf("GC::malloc(size = %d, gcx = %p)\n", size, gcx);
508 assert(gcx);
509 //debug(PRINTF) printf("gcx.self = %x, pthread_self() = %x\n", gcx.self, pthread_self());
510
511 auto p = gcx.alloc(size + SENTINEL_EXTRA, alloc_size, bits);
512 if (!p)
513 onOutOfMemoryErrorNoGC();
514
515 debug (SENTINEL)
516 {
517 p = sentinel_add(p);
518 sentinel_init(p, size);
519 alloc_size = size;
520 }
521 gcx.log_malloc(p, size);
522
523 return p;
524 }
525
526
527 BlkInfo qalloc( size_t size, uint bits, const TypeInfo ti) nothrow
528 {
529
530 if (!size)
531 {
532 return BlkInfo.init;
533 }
534
535 BlkInfo retval;
536
537 retval.base = runLocked!(mallocNoSync, mallocTime, numMallocs)(size, bits, retval.size, ti);
538
539 if (!(bits & BlkAttr.NO_SCAN))
540 {
541 memset(retval.base + size, 0, retval.size - size);
542 }
543
544 retval.attr = bits;
545 return retval;
546 }
547
548
549 void *calloc(size_t size, uint bits, const TypeInfo ti) nothrow
550 {
551 if (!size)
552 {
553 return null;
554 }
555
556 size_t localAllocSize = void;
557
558 auto p = runLocked!(mallocNoSync, mallocTime, numMallocs)(size, bits, localAllocSize, ti);
559
560 memset(p, 0, size);
561 if (!(bits & BlkAttr.NO_SCAN))
562 {
563 memset(p + size, 0, localAllocSize - size);
564 }
565
566 return p;
567 }
568
569
570 void *realloc(void *p, size_t size, uint bits, const TypeInfo ti) nothrow
571 {
572 size_t localAllocSize = void;
573 auto oldp = p;
574
575 p = runLocked!(reallocNoSync, mallocTime, numMallocs)(p, size, bits, localAllocSize, ti);
576
577 if (p !is oldp && !(bits & BlkAttr.NO_SCAN))
578 {
579 memset(p + size, 0, localAllocSize - size);
580 }
581
582 return p;
583 }
584
585
586 //
587 // bits will be set to the resulting bits of the new block
588 //
589 private void *reallocNoSync(void *p, size_t size, ref uint bits, ref size_t alloc_size, const TypeInfo ti = null) nothrow
590 {
591 if (!size)
592 { if (p)
593 { freeNoSync(p);
594 p = null;
595 }
596 alloc_size = 0;
597 }
598 else if (!p)
599 {
600 p = mallocNoSync(size, bits, alloc_size, ti);
601 }
602 else
603 { void *p2;
604 size_t psize;
605
606 //debug(PRINTF) printf("GC::realloc(p = %p, size = %zu)\n", p, size);
607 debug (SENTINEL)
608 {
609 sentinel_Invariant(p);
610 psize = *sentinel_size(p);
611 if (psize != size)
612 {
613 if (psize)
614 {
615 Pool *pool = gcx.findPool(p);
616
617 if (pool)
618 {
619 auto biti = cast(size_t)(sentinel_sub(p) - pool.baseAddr) >> pool.shiftBy;
620
621 if (bits)
622 {
623 pool.clrBits(biti, ~BlkAttr.NONE);
624 pool.setBits(biti, bits);
625 }
626 else
627 {
628 bits = pool.getBits(biti);
629 }
630 }
631 }
632 p2 = mallocNoSync(size, bits, alloc_size, ti);
633 if (psize < size)
634 size = psize;
635 //debug(PRINTF) printf("\tcopying %d bytes\n",size);
636 memcpy(p2, p, size);
637 p = p2;
638 }
639 }
640 else
641 {
642 auto pool = gcx.findPool(p);
643 if (pool.isLargeObject)
644 {
645 auto lpool = cast(LargeObjectPool*) pool;
646 psize = lpool.getSize(p); // get allocated size
647
648 if (size <= PAGESIZE / 2)
649 goto Lmalloc; // switching from large object pool to small object pool
650
651 auto psz = psize / PAGESIZE;
652 auto newsz = (size + PAGESIZE - 1) / PAGESIZE;
653 if (newsz == psz)
654 {
655 alloc_size = psize;
656 return p;
657 }
658
659 auto pagenum = lpool.pagenumOf(p);
660
661 if (newsz < psz)
662 { // Shrink in place
663 debug (MEMSTOMP) memset(p + size, 0xF2, psize - size);
664 lpool.freePages(pagenum + newsz, psz - newsz);
665 }
666 else if (pagenum + newsz <= pool.npages)
667 { // Attempt to expand in place
668 foreach (binsz; lpool.pagetable[pagenum + psz .. pagenum + newsz])
669 if (binsz != B_FREE)
670 goto Lmalloc;
671
672 debug (MEMSTOMP) memset(p + psize, 0xF0, size - psize);
673 debug(PRINTF) printFreeInfo(pool);
674 memset(&lpool.pagetable[pagenum + psz], B_PAGEPLUS, newsz - psz);
675 gcx.usedLargePages += newsz - psz;
676 lpool.freepages -= (newsz - psz);
677 debug(PRINTF) printFreeInfo(pool);
678 }
679 else
680 goto Lmalloc; // does not fit into current pool
681
682 lpool.updateOffsets(pagenum);
683 if (bits)
684 {
685 immutable biti = cast(size_t)(p - pool.baseAddr) >> pool.shiftBy;
686 pool.clrBits(biti, ~BlkAttr.NONE);
687 pool.setBits(biti, bits);
688 }
689 alloc_size = newsz * PAGESIZE;
690 return p;
691 }
692
693 psize = (cast(SmallObjectPool*) pool).getSize(p); // get allocated size
694 if (psize < size || // if new size is bigger
695 psize > size * 2) // or less than half
696 {
697 Lmalloc:
698 if (psize && pool)
699 {
700 auto biti = cast(size_t)(p - pool.baseAddr) >> pool.shiftBy;
701
702 if (bits)
703 {
704 pool.clrBits(biti, ~BlkAttr.NONE);
705 pool.setBits(biti, bits);
706 }
707 else
708 {
709 bits = pool.getBits(biti);
710 }
711 }
712 p2 = mallocNoSync(size, bits, alloc_size, ti);
713 if (psize < size)
714 size = psize;
715 //debug(PRINTF) printf("\tcopying %d bytes\n",size);
716 memcpy(p2, p, size);
717 p = p2;
718 }
719 else
720 alloc_size = psize;
721 }
722 }
723 return p;
724 }
725
726
727 size_t extend(void* p, size_t minsize, size_t maxsize, const TypeInfo ti) nothrow
728 {
729 return runLocked!(extendNoSync, extendTime, numExtends)(p, minsize, maxsize, ti);
730 }
731
732
733 //
734 //
735 //
736 private size_t extendNoSync(void* p, size_t minsize, size_t maxsize, const TypeInfo ti = null) nothrow
737 in
738 {
739 assert(minsize <= maxsize);
740 }
741 body
742 {
743 //debug(PRINTF) printf("GC::extend(p = %p, minsize = %zu, maxsize = %zu)\n", p, minsize, maxsize);
744 debug (SENTINEL)
745 {
746 return 0;
747 }
748 else
749 {
750 auto pool = gcx.findPool(p);
751 if (!pool || !pool.isLargeObject)
752 return 0;
753
754 auto lpool = cast(LargeObjectPool*) pool;
755 auto psize = lpool.getSize(p); // get allocated size
756 if (psize < PAGESIZE)
757 return 0; // cannot extend buckets
758
759 auto psz = psize / PAGESIZE;
760 auto minsz = (minsize + PAGESIZE - 1) / PAGESIZE;
761 auto maxsz = (maxsize + PAGESIZE - 1) / PAGESIZE;
762
763 auto pagenum = lpool.pagenumOf(p);
764
765 size_t sz;
766 for (sz = 0; sz < maxsz; sz++)
767 {
768 auto i = pagenum + psz + sz;
769 if (i == lpool.npages)
770 break;
771 if (lpool.pagetable[i] != B_FREE)
772 { if (sz < minsz)
773 return 0;
774 break;
775 }
776 }
777 if (sz < minsz)
778 return 0;
779 debug (MEMSTOMP) memset(pool.baseAddr + (pagenum + psz) * PAGESIZE, 0xF0, sz * PAGESIZE);
780 memset(lpool.pagetable + pagenum + psz, B_PAGEPLUS, sz);
781 lpool.updateOffsets(pagenum);
782 lpool.freepages -= sz;
783 gcx.usedLargePages += sz;
784 return (psz + sz) * PAGESIZE;
785 }
786 }
787
788
789 size_t reserve(size_t size) nothrow
790 {
791 if (!size)
792 {
793 return 0;
794 }
795
796 return runLocked!(reserveNoSync, otherTime, numOthers)(size);
797 }
798
799
800 //
801 //
802 //
803 private size_t reserveNoSync(size_t size) nothrow
804 {
805 assert(size != 0);
806 assert(gcx);
807
808 return gcx.reserve(size);
809 }
810
811
812 void free(void *p) nothrow
813 {
814 if (!p || _inFinalizer)
815 {
816 return;
817 }
818
819 return runLocked!(freeNoSync, freeTime, numFrees)(p);
820 }
821
822
823 //
824 //
825 //
826 private void freeNoSync(void *p) nothrow
827 {
828 debug(PRINTF) printf("Freeing %p\n", cast(size_t) p);
829 assert (p);
830
831 Pool* pool;
832 size_t pagenum;
833 Bins bin;
834 size_t biti;
835
836 // Find which page it is in
837 pool = gcx.findPool(p);
838 if (!pool) // if not one of ours
839 return; // ignore
840
841 pagenum = pool.pagenumOf(p);
842
843 debug(PRINTF) printf("pool base = %p, PAGENUM = %d of %d, bin = %d\n", pool.baseAddr, pagenum, pool.npages, pool.pagetable[pagenum]);
844 debug(PRINTF) if (pool.isLargeObject) printf("Block size = %d\n", pool.bPageOffsets[pagenum]);
845
846 bin = cast(Bins)pool.pagetable[pagenum];
847
848 // Verify that the pointer is at the beginning of a block,
849 // no action should be taken if p is an interior pointer
850 if (bin > B_PAGE) // B_PAGEPLUS or B_FREE
851 return;
852 if ((sentinel_sub(p) - pool.baseAddr) & (binsize[bin] - 1))
853 return;
854
855 sentinel_Invariant(p);
856 p = sentinel_sub(p);
857 biti = cast(size_t)(p - pool.baseAddr) >> pool.shiftBy;
858
859 pool.clrBits(biti, ~BlkAttr.NONE);
860
861 if (pool.isLargeObject) // if large alloc
862 {
863 assert(bin == B_PAGE);
864 auto lpool = cast(LargeObjectPool*) pool;
865
866 // Free pages
867 size_t npages = lpool.bPageOffsets[pagenum];
868 debug (MEMSTOMP) memset(p, 0xF2, npages * PAGESIZE);
869 lpool.freePages(pagenum, npages);
870 }
871 else
872 { // Add to free list
873 List *list = cast(List*)p;
874
875 debug (MEMSTOMP) memset(p, 0xF2, binsize[bin]);
876
877 list.next = gcx.bucket[bin];
878 list.pool = pool;
879 gcx.bucket[bin] = list;
880 }
881
882 gcx.log_free(sentinel_add(p));
883 }
884
885
886 void* addrOf(void *p) nothrow
887 {
888 if (!p)
889 {
890 return null;
891 }
892
893 return runLocked!(addrOfNoSync, otherTime, numOthers)(p);
894 }
895
896
897 //
898 //
899 //
900 void* addrOfNoSync(void *p) nothrow
901 {
902 if (!p)
903 {
904 return null;
905 }
906
907 auto q = gcx.findBase(p);
908 if (q)
909 q = sentinel_add(q);
910 return q;
911 }
912
913
914 size_t sizeOf(void *p) nothrow
915 {
916 if (!p)
917 {
918 return 0;
919 }
920
921 return runLocked!(sizeOfNoSync, otherTime, numOthers)(p);
922 }
923
924
925 //
926 //
927 //
928 private size_t sizeOfNoSync(void *p) nothrow
929 {
930 assert (p);
931
932 debug (SENTINEL)
933 {
934 p = sentinel_sub(p);
935 size_t size = gcx.findSize(p);
936
937 // Check for interior pointer
938 // This depends on:
939 // 1) size is a power of 2 for less than PAGESIZE values
940 // 2) base of memory pool is aligned on PAGESIZE boundary
941 if (cast(size_t)p & (size - 1) & (PAGESIZE - 1))
942 size = 0;
943 return size ? size - SENTINEL_EXTRA : 0;
944 }
945 else
946 {
947 size_t size = gcx.findSize(p);
948
949 // Check for interior pointer
950 // This depends on:
951 // 1) size is a power of 2 for less than PAGESIZE values
952 // 2) base of memory pool is aligned on PAGESIZE boundary
953 if (cast(size_t)p & (size - 1) & (PAGESIZE - 1))
954 return 0;
955 return size;
956 }
957 }
958
959
960 BlkInfo query(void *p) nothrow
961 {
962 if (!p)
963 {
964 BlkInfo i;
965 return i;
966 }
967
968 return runLocked!(queryNoSync, otherTime, numOthers)(p);
969 }
970
971 //
972 //
973 //
974 BlkInfo queryNoSync(void *p) nothrow
975 {
976 assert(p);
977
978 BlkInfo info = gcx.getInfo(p);
979 debug(SENTINEL)
980 {
981 if (info.base)
982 {
983 info.base = sentinel_add(info.base);
984 info.size = *sentinel_size(info.base);
985 }
986 }
987 return info;
988 }
989
990
991 /**
992 * Verify that pointer p:
993 * 1) belongs to this memory pool
994 * 2) points to the start of an allocated piece of memory
995 * 3) is not on a free list
996 */
997 void check(void *p) nothrow
998 {
999 if (!p)
1000 {
1001 return;
1002 }
1003
1004 return runLocked!(checkNoSync, otherTime, numOthers)(p);
1005 }
1006
1007
1008 //
1009 //
1010 //
1011 private void checkNoSync(void *p) nothrow
1012 {
1013 assert(p);
1014
1015 sentinel_Invariant(p);
1016 debug (PTRCHECK)
1017 {
1018 Pool* pool;
1019 size_t pagenum;
1020 Bins bin;
1021 size_t size;
1022
1023 p = sentinel_sub(p);
1024 pool = gcx.findPool(p);
1025 assert(pool);
1026 pagenum = pool.pagenumOf(p);
1027 bin = cast(Bins)pool.pagetable[pagenum];
1028 assert(bin <= B_PAGE);
1029 size = binsize[bin];
1030 assert((cast(size_t)p & (size - 1)) == 0);
1031
1032 debug (PTRCHECK2)
1033 {
1034 if (bin < B_PAGE)
1035 {
1036 // Check that p is not on a free list
1037 List *list;
1038
1039 for (list = gcx.bucket[bin]; list; list = list.next)
1040 {
1041 assert(cast(void*)list != p);
1042 }
1043 }
1044 }
1045 }
1046 }
1047
1048
1049 void addRoot(void *p) nothrow @nogc
1050 {
1051 if (!p)
1052 {
1053 return;
1054 }
1055
1056 gcx.addRoot(p);
1057 }
1058
1059
1060 void removeRoot(void *p) nothrow @nogc
1061 {
1062 if (!p)
1063 {
1064 return;
1065 }
1066
1067 gcx.removeRoot(p);
1068 }
1069
1070
1071 @property RootIterator rootIter() @nogc
1072 {
1073 return &gcx.rootsApply;
1074 }
1075
1076
1077 void addRange(void *p, size_t sz, const TypeInfo ti = null) nothrow @nogc
1078 {
1079 if (!p || !sz)
1080 {
1081 return;
1082 }
1083
1084 gcx.addRange(p, p + sz, ti);
1085 }
1086
1087
1088 void removeRange(void *p) nothrow @nogc
1089 {
1090 if (!p)
1091 {
1092 return;
1093 }
1094
1095 gcx.removeRange(p);
1096 }
1097
1098
1099 @property RangeIterator rangeIter() @nogc
1100 {
1101 return &gcx.rangesApply;
1102 }
1103
1104
1105 void runFinalizers(in void[] segment) nothrow
1106 {
1107 static void go(Gcx* gcx, in void[] segment) nothrow
1108 {
1109 gcx.runFinalizers(segment);
1110 }
1111 return runLocked!(go, otherTime, numOthers)(gcx, segment);
1112 }
1113
1114
1115 bool inFinalizer() nothrow
1116 {
1117 return _inFinalizer;
1118 }
1119
1120
1121 void collect() nothrow
1122 {
1123 fullCollect();
1124 }
1125
1126
1127 void collectNoStack() nothrow
1128 {
1129 fullCollectNoStack();
1130 }
1131
1132
1133 /**
1134 * Do full garbage collection.
1135 * Return number of pages free'd.
1136 */
1137 size_t fullCollect() nothrow
1138 {
1139 debug(PRINTF) printf("GC.fullCollect()\n");
1140
1141 // Since a finalizer could launch a new thread, we always need to lock
1142 // when collecting.
1143 static size_t go(Gcx* gcx) nothrow
1144 {
1145 return gcx.fullcollect();
1146 }
1147 immutable result = runLocked!go(gcx);
1148
1149 version (none)
1150 {
1151 GCStats stats;
1152
1153 getStats(stats);
1154 debug(PRINTF) printf("heapSize = %zx, freeSize = %zx\n",
1155 stats.heapSize, stats.freeSize);
1156 }
1157
1158 gcx.log_collect();
1159 return result;
1160 }
1161
1162
1163 /**
1164 * do full garbage collection ignoring roots
1165 */
1166 void fullCollectNoStack() nothrow
1167 {
1168 // Since a finalizer could launch a new thread, we always need to lock
1169 // when collecting.
1170 static size_t go(Gcx* gcx) nothrow
1171 {
1172 return gcx.fullcollect(true);
1173 }
1174 runLocked!go(gcx);
1175 }
1176
1177
1178 void minimize() nothrow
1179 {
1180 static void go(Gcx* gcx) nothrow
1181 {
1182 gcx.minimize();
1183 }
1184 runLocked!(go, otherTime, numOthers)(gcx);
1185 }
1186
1187
1188 core.memory.GC.Stats stats() nothrow
1189 {
1190 typeof(return) ret;
1191
1192 runLocked!(getStatsNoSync, otherTime, numOthers)(ret);
1193
1194 return ret;
1195 }
1196
1197
1198 //
1199 //
1200 //
1201 private void getStatsNoSync(out core.memory.GC.Stats stats) nothrow
1202 {
1203 foreach (pool; gcx.pooltable[0 .. gcx.npools])
1204 {
1205 foreach (bin; pool.pagetable[0 .. pool.npages])
1206 {
1207 if (bin == B_FREE)
1208 stats.freeSize += PAGESIZE;
1209 else
1210 stats.usedSize += PAGESIZE;
1211 }
1212 }
1213
1214 size_t freeListSize;
1215 foreach (n; 0 .. B_PAGE)
1216 {
1217 immutable sz = binsize[n];
1218 for (List *list = gcx.bucket[n]; list; list = list.next)
1219 freeListSize += sz;
1220 }
1221
1222 stats.usedSize -= freeListSize;
1223 stats.freeSize += freeListSize;
1224 }
1225 }
1226
1227
1228 /* ============================ Gcx =============================== */
1229
1230 enum
1231 { PAGESIZE = 4096,
1232 POOLSIZE = (4096*256),
1233 }
1234
1235
1236 enum
1237 {
1238 B_16,
1239 B_32,
1240 B_64,
1241 B_128,
1242 B_256,
1243 B_512,
1244 B_1024,
1245 B_2048,
1246 B_PAGE, // start of large alloc
1247 B_PAGEPLUS, // continuation of large alloc
1248 B_FREE, // free page
1249 B_MAX
1250 }
1251
1252
1253 alias ubyte Bins;
1254
1255
1256 struct List
1257 {
1258 List *next;
1259 Pool *pool;
1260 }
1261
1262
1263 immutable uint[B_MAX] binsize = [ 16,32,64,128,256,512,1024,2048,4096 ];
1264 immutable size_t[B_MAX] notbinsize = [ ~(16-1),~(32-1),~(64-1),~(128-1),~(256-1),
1265 ~(512-1),~(1024-1),~(2048-1),~(4096-1) ];
1266
1267 alias PageBits = GCBits.wordtype[PAGESIZE / 16 / GCBits.BITS_PER_WORD];
1268 static assert(PAGESIZE % (GCBits.BITS_PER_WORD * 16) == 0);
1269
1270 private void set(ref PageBits bits, size_t i) @nogc pure nothrow
1271 {
1272 assert(i < PageBits.sizeof * 8);
1273 bts(bits.ptr, i);
1274 }
1275
1276 /* ============================ Gcx =============================== */
1277
1278 struct Gcx
1279 {
1280 import core.internal.spinlock;
1281 auto rootsLock = shared(AlignedSpinLock)(SpinLock.Contention.brief);
1282 auto rangesLock = shared(AlignedSpinLock)(SpinLock.Contention.brief);
1283 Treap!Root roots;
1284 Treap!Range ranges;
1285
1286 bool log; // turn on logging
1287 debug(INVARIANT) bool initialized;
1288 uint disabled; // turn off collections if >0
1289
1290 import gc.pooltable;
1291 @property size_t npools() pure const nothrow { return pooltable.length; }
1292 PoolTable!Pool pooltable;
1293
1294 List*[B_PAGE] bucket; // free list for each small size
1295
1296 // run a collection when reaching those thresholds (number of used pages)
1297 float smallCollectThreshold, largeCollectThreshold;
1298 uint usedSmallPages, usedLargePages;
1299 // total number of mapped pages
1300 uint mappedPages;
1301
1302 void initialize()
1303 {
1304 (cast(byte*)&this)[0 .. Gcx.sizeof] = 0;
1305 log_init();
1306 roots.initialize();
1307 ranges.initialize();
1308 smallCollectThreshold = largeCollectThreshold = 0.0f;
1309 usedSmallPages = usedLargePages = 0;
1310 mappedPages = 0;
1311 //printf("gcx = %p, self = %x\n", &this, self);
1312 debug(INVARIANT) initialized = true;
1313 }
1314
1315
1316 void Dtor()
1317 {
1318 if (config.profile)
1319 {
1320 printf("\tNumber of collections: %llu\n", cast(ulong)numCollections);
1321 printf("\tTotal GC prep time: %lld milliseconds\n",
1322 prepTime.total!("msecs"));
1323 printf("\tTotal mark time: %lld milliseconds\n",
1324 markTime.total!("msecs"));
1325 printf("\tTotal sweep time: %lld milliseconds\n",
1326 sweepTime.total!("msecs"));
1327 printf("\tTotal page recovery time: %lld milliseconds\n",
1328 recoverTime.total!("msecs"));
1329 long maxPause = maxPauseTime.total!("msecs");
1330 printf("\tMax Pause Time: %lld milliseconds\n", maxPause);
1331 long gcTime = (recoverTime + sweepTime + markTime + prepTime).total!("msecs");
1332 printf("\tGrand total GC time: %lld milliseconds\n", gcTime);
1333 long pauseTime = (markTime + prepTime).total!("msecs");
1334
1335 char[30] apitxt;
1336 apitxt[0] = 0;
1337 debug(PROFILE_API) if (config.profile > 1)
1338 {
1339 static Duration toDuration(long dur)
1340 {
1341 return MonoTime(dur) - MonoTime(0);
1342 }
1343
1344 printf("\n");
1345 printf("\tmalloc: %llu calls, %lld ms\n", cast(ulong)numMallocs, toDuration(mallocTime).total!"msecs");
1346 printf("\trealloc: %llu calls, %lld ms\n", cast(ulong)numReallocs, toDuration(reallocTime).total!"msecs");
1347 printf("\tfree: %llu calls, %lld ms\n", cast(ulong)numFrees, toDuration(freeTime).total!"msecs");
1348 printf("\textend: %llu calls, %lld ms\n", cast(ulong)numExtends, toDuration(extendTime).total!"msecs");
1349 printf("\tother: %llu calls, %lld ms\n", cast(ulong)numOthers, toDuration(otherTime).total!"msecs");
1350 printf("\tlock time: %lld ms\n", toDuration(lockTime).total!"msecs");
1351
1352 long apiTime = mallocTime + reallocTime + freeTime + extendTime + otherTime + lockTime;
1353 printf("\tGC API: %lld ms\n", toDuration(apiTime).total!"msecs");
1354 sprintf(apitxt.ptr, " API%5ld ms", toDuration(apiTime).total!"msecs");
1355 }
1356
1357 printf("GC summary:%5lld MB,%5lld GC%5lld ms, Pauses%5lld ms <%5lld ms%s\n",
1358 cast(long) maxPoolMemory >> 20, cast(ulong)numCollections, gcTime,
1359 pauseTime, maxPause, apitxt.ptr);
1360 }
1361
1362 debug(INVARIANT) initialized = false;
1363
1364 for (size_t i = 0; i < npools; i++)
1365 {
1366 Pool *pool = pooltable[i];
1367 mappedPages -= pool.npages;
1368 pool.Dtor();
1369 cstdlib.free(pool);
1370 }
1371 assert(!mappedPages);
1372 pooltable.Dtor();
1373
1374 roots.removeAll();
1375 ranges.removeAll();
1376 toscan.reset();
1377 }
1378
1379
1380 void Invariant() const { }
1381
1382 debug(INVARIANT)
1383 invariant()
1384 {
1385 if (initialized)
1386 {
1387 //printf("Gcx.invariant(): this = %p\n", &this);
1388 pooltable.Invariant();
1389
1390 rangesLock.lock();
1391 foreach (range; ranges)
1392 {
1393 assert(range.pbot);
1394 assert(range.ptop);
1395 assert(range.pbot <= range.ptop);
1396 }
1397 rangesLock.unlock();
1398
1399 for (size_t i = 0; i < B_PAGE; i++)
1400 {
1401 for (auto list = cast(List*)bucket[i]; list; list = list.next)
1402 {
1403 }
1404 }
1405 }
1406 }
1407
1408
1409 /**
1410 *
1411 */
1412 void addRoot(void *p) nothrow @nogc
1413 {
1414 rootsLock.lock();
1415 scope (failure) rootsLock.unlock();
1416 roots.insert(Root(p));
1417 rootsLock.unlock();
1418 }
1419
1420
1421 /**
1422 *
1423 */
1424 void removeRoot(void *p) nothrow @nogc
1425 {
1426 rootsLock.lock();
1427 scope (failure) rootsLock.unlock();
1428 roots.remove(Root(p));
1429 rootsLock.unlock();
1430 }
1431
1432
1433 /**
1434 *
1435 */
1436 int rootsApply(scope int delegate(ref Root) nothrow dg) nothrow
1437 {
1438 rootsLock.lock();
1439 scope (failure) rootsLock.unlock();
1440 auto ret = roots.opApply(dg);
1441 rootsLock.unlock();
1442 return ret;
1443 }
1444
1445
1446 /**
1447 *
1448 */
1449 void addRange(void *pbot, void *ptop, const TypeInfo ti) nothrow @nogc
1450 {
1451 //debug(PRINTF) printf("Thread %x ", pthread_self());
1452 debug(PRINTF) printf("%p.Gcx::addRange(%p, %p)\n", &this, pbot, ptop);
1453 rangesLock.lock();
1454 scope (failure) rangesLock.unlock();
1455 ranges.insert(Range(pbot, ptop));
1456 rangesLock.unlock();
1457 }
1458
1459
1460 /**
1461 *
1462 */
1463 void removeRange(void *pbot) nothrow @nogc
1464 {
1465 //debug(PRINTF) printf("Thread %x ", pthread_self());
1466 debug(PRINTF) printf("Gcx.removeRange(%p)\n", pbot);
1467 rangesLock.lock();
1468 scope (failure) rangesLock.unlock();
1469 ranges.remove(Range(pbot, pbot)); // only pbot is used, see Range.opCmp
1470 rangesLock.unlock();
1471
1472 // debug(PRINTF) printf("Wrong thread\n");
1473 // This is a fatal error, but ignore it.
1474 // The problem is that we can get a Close() call on a thread
1475 // other than the one the range was allocated on.
1476 //assert(zero);
1477 }
1478
1479 /**
1480 *
1481 */
1482 int rangesApply(scope int delegate(ref Range) nothrow dg) nothrow
1483 {
1484 rangesLock.lock();
1485 scope (failure) rangesLock.unlock();
1486 auto ret = ranges.opApply(dg);
1487 rangesLock.unlock();
1488 return ret;
1489 }
1490
1491
1492 /**
1493 *
1494 */
1495 void runFinalizers(in void[] segment) nothrow
1496 {
1497 ConservativeGC._inFinalizer = true;
1498 scope (failure) ConservativeGC._inFinalizer = false;
1499
1500 foreach (pool; pooltable[0 .. npools])
1501 {
1502 if (!pool.finals.nbits) continue;
1503
1504 if (pool.isLargeObject)
1505 {
1506 auto lpool = cast(LargeObjectPool*) pool;
1507 lpool.runFinalizers(segment);
1508 }
1509 else
1510 {
1511 auto spool = cast(SmallObjectPool*) pool;
1512 spool.runFinalizers(segment);
1513 }
1514 }
1515 ConservativeGC._inFinalizer = false;
1516 }
1517
1518 Pool* findPool(void* p) pure nothrow
1519 {
1520 return pooltable.findPool(p);
1521 }
1522
1523 /**
1524 * Find base address of block containing pointer p.
1525 * Returns null if not a gc'd pointer
1526 */
1527 void* findBase(void *p) nothrow
1528 {
1529 Pool *pool;
1530
1531 pool = findPool(p);
1532 if (pool)
1533 {
1534 size_t offset = cast(size_t)(p - pool.baseAddr);
1535 size_t pn = offset / PAGESIZE;
1536 Bins bin = cast(Bins)pool.pagetable[pn];
1537
1538 // Adjust bit to be at start of allocated memory block
1539 if (bin <= B_PAGE)
1540 {
1541 return pool.baseAddr + (offset & notbinsize[bin]);
1542 }
1543 else if (bin == B_PAGEPLUS)
1544 {
1545 auto pageOffset = pool.bPageOffsets[pn];
1546 offset -= pageOffset * PAGESIZE;
1547 pn -= pageOffset;
1548
1549 return pool.baseAddr + (offset & (offset.max ^ (PAGESIZE-1)));
1550 }
1551 else
1552 {
1553 // we are in a B_FREE page
1554 assert(bin == B_FREE);
1555 return null;
1556 }
1557 }
1558 return null;
1559 }
1560
1561
1562 /**
1563 * Find size of pointer p.
1564 * Returns 0 if not a gc'd pointer
1565 */
1566 size_t findSize(void *p) nothrow
1567 {
1568 Pool* pool = findPool(p);
1569 if (pool)
1570 return pool.slGetSize(p);
1571 return 0;
1572 }
1573
1574 /**
1575 *
1576 */
1577 BlkInfo getInfo(void* p) nothrow
1578 {
1579 Pool* pool = findPool(p);
1580 if (pool)
1581 return pool.slGetInfo(p);
1582 return BlkInfo();
1583 }
1584
1585 /**
1586 * Computes the bin table using CTFE.
1587 */
1588 static byte[2049] ctfeBins() nothrow
1589 {
1590 byte[2049] ret;
1591 size_t p = 0;
1592 for (Bins b = B_16; b <= B_2048; b++)
1593 for ( ; p <= binsize[b]; p++)
1594 ret[p] = b;
1595
1596 return ret;
1597 }
1598
1599 static const byte[2049] binTable = ctfeBins();
1600
1601 /**
1602 * Allocate a new pool of at least size bytes.
1603 * Sort it into pooltable[].
1604 * Mark all memory in the pool as B_FREE.
1605 * Return the actual number of bytes reserved or 0 on error.
1606 */
1607 size_t reserve(size_t size) nothrow
1608 {
1609 size_t npages = (size + PAGESIZE - 1) / PAGESIZE;
1610
1611 // Assume reserve() is for small objects.
1612 Pool* pool = newPool(npages, false);
1613
1614 if (!pool)
1615 return 0;
1616 return pool.npages * PAGESIZE;
1617 }
1618
1619 /**
1620 * Update the thresholds for when to collect the next time
1621 */
1622 void updateCollectThresholds() nothrow
1623 {
1624 static float max(float a, float b) nothrow
1625 {
1626 return a >= b ? a : b;
1627 }
1628
1629 // instantly increases, slowly decreases
1630 static float smoothDecay(float oldVal, float newVal) nothrow
1631 {
1632 // decay to 63.2% of newVal over 5 collections
1633 // http://en.wikipedia.org/wiki/Low-pass_filter#Simple_infinite_impulse_response_filter
1634 enum alpha = 1.0 / (5 + 1);
1635 immutable decay = (newVal - oldVal) * alpha + oldVal;
1636 return max(newVal, decay);
1637 }
1638
1639 immutable smTarget = usedSmallPages * config.heapSizeFactor;
1640 smallCollectThreshold = smoothDecay(smallCollectThreshold, smTarget);
1641 immutable lgTarget = usedLargePages * config.heapSizeFactor;
1642 largeCollectThreshold = smoothDecay(largeCollectThreshold, lgTarget);
1643 }
1644
1645 /**
1646 * Minimizes physical memory usage by returning free pools to the OS.
1647 */
1648 void minimize() nothrow
1649 {
1650 debug(PRINTF) printf("Minimizing.\n");
1651
1652 foreach (pool; pooltable.minimize())
1653 {
1654 debug(PRINTF) printFreeInfo(pool);
1655 mappedPages -= pool.npages;
1656 pool.Dtor();
1657 cstdlib.free(pool);
1658 }
1659
1660 debug(PRINTF) printf("Done minimizing.\n");
1661 }
1662
1663 private @property bool lowMem() const nothrow
1664 {
1665 return isLowOnMem(mappedPages * PAGESIZE);
1666 }
1667
1668 void* alloc(size_t size, ref size_t alloc_size, uint bits) nothrow
1669 {
1670 return size <= 2048 ? smallAlloc(binTable[size], alloc_size, bits)
1671 : bigAlloc(size, alloc_size, bits);
1672 }
1673
1674 void* smallAlloc(Bins bin, ref size_t alloc_size, uint bits) nothrow
1675 {
1676 alloc_size = binsize[bin];
1677
1678 void* p;
1679 bool tryAlloc() nothrow
1680 {
1681 if (!bucket[bin])
1682 {
1683 bucket[bin] = allocPage(bin);
1684 if (!bucket[bin])
1685 return false;
1686 }
1687 p = bucket[bin];
1688 return true;
1689 }
1690
1691 if (!tryAlloc())
1692 {
1693 if (!lowMem && (disabled || usedSmallPages < smallCollectThreshold))
1694 {
1695 // disabled or threshold not reached => allocate a new pool instead of collecting
1696 if (!newPool(1, false))
1697 {
1698 // out of memory => try to free some memory
1699 fullcollect();
1700 if (lowMem) minimize();
1701 }
1702 }
1703 else
1704 {
1705 fullcollect();
1706 if (lowMem) minimize();
1707 }
1708 // tryAlloc will succeed if a new pool was allocated above, if it fails allocate a new pool now
1709 if (!tryAlloc() && (!newPool(1, false) || !tryAlloc()))
1710 // out of luck or memory
1711 onOutOfMemoryErrorNoGC();
1712 }
1713 assert(p !is null);
1714
1715 // Return next item from free list
1716 bucket[bin] = (cast(List*)p).next;
1717 auto pool = (cast(List*)p).pool;
1718 if (bits)
1719 pool.setBits((p - pool.baseAddr) >> pool.shiftBy, bits);
1720 //debug(PRINTF) printf("\tmalloc => %p\n", p);
1721 debug (MEMSTOMP) memset(p, 0xF0, alloc_size);
1722 return p;
1723 }
1724
1725 /**
1726 * Allocate a chunk of memory that is larger than a page.
1727 * Return null if out of memory.
1728 */
1729 void* bigAlloc(size_t size, ref size_t alloc_size, uint bits, const TypeInfo ti = null) nothrow
1730 {
1731 debug(PRINTF) printf("In bigAlloc. Size: %d\n", size);
1732
1733 LargeObjectPool* pool;
1734 size_t pn;
1735 immutable npages = (size + PAGESIZE - 1) / PAGESIZE;
1736 if (npages == 0)
1737 onOutOfMemoryErrorNoGC(); // size just below size_t.max requested
1738
1739 bool tryAlloc() nothrow
1740 {
1741 foreach (p; pooltable[0 .. npools])
1742 {
1743 if (!p.isLargeObject || p.freepages < npages)
1744 continue;
1745 auto lpool = cast(LargeObjectPool*) p;
1746 if ((pn = lpool.allocPages(npages)) == OPFAIL)
1747 continue;
1748 pool = lpool;
1749 return true;
1750 }
1751 return false;
1752 }
1753
1754 bool tryAllocNewPool() nothrow
1755 {
1756 pool = cast(LargeObjectPool*) newPool(npages, true);
1757 if (!pool) return false;
1758 pn = pool.allocPages(npages);
1759 assert(pn != OPFAIL);
1760 return true;
1761 }
1762
1763 if (!tryAlloc())
1764 {
1765 if (!lowMem && (disabled || usedLargePages < largeCollectThreshold))
1766 {
1767 // disabled or threshold not reached => allocate a new pool instead of collecting
1768 if (!tryAllocNewPool())
1769 {
1770 // disabled but out of memory => try to free some memory
1771 fullcollect();
1772 minimize();
1773 }
1774 }
1775 else
1776 {
1777 fullcollect();
1778 minimize();
1779 }
1780 // If alloc didn't yet succeed retry now that we collected/minimized
1781 if (!pool && !tryAlloc() && !tryAllocNewPool())
1782 // out of luck or memory
1783 return null;
1784 }
1785 assert(pool);
1786
1787 debug(PRINTF) printFreeInfo(&pool.base);
1788 pool.pagetable[pn] = B_PAGE;
1789 if (npages > 1)
1790 memset(&pool.pagetable[pn + 1], B_PAGEPLUS, npages - 1);
1791 pool.updateOffsets(pn);
1792 usedLargePages += npages;
1793 pool.freepages -= npages;
1794
1795 debug(PRINTF) printFreeInfo(&pool.base);
1796
1797 auto p = pool.baseAddr + pn * PAGESIZE;
1798 debug(PRINTF) printf("Got large alloc: %p, pt = %d, np = %d\n", p, pool.pagetable[pn], npages);
1799 debug (MEMSTOMP) memset(p, 0xF1, size);
1800 alloc_size = npages * PAGESIZE;
1801 //debug(PRINTF) printf("\tp = %p\n", p);
1802
1803 if (bits)
1804 pool.setBits(pn, bits);
1805 return p;
1806 }
1807
1808
1809 /**
1810 * Allocate a new pool with at least npages in it.
1811 * Sort it into pooltable[].
1812 * Return null if failed.
1813 */
1814 Pool *newPool(size_t npages, bool isLargeObject) nothrow
1815 {
1816 //debug(PRINTF) printf("************Gcx::newPool(npages = %d)****************\n", npages);
1817
1818 // Minimum of POOLSIZE
1819 size_t minPages = (config.minPoolSize << 20) / PAGESIZE;
1820 if (npages < minPages)
1821 npages = minPages;
1822 else if (npages > minPages)
1823 { // Give us 150% of requested size, so there's room to extend
1824 auto n = npages + (npages >> 1);
1825 if (n < size_t.max/PAGESIZE)
1826 npages = n;
1827 }
1828
1829 // Allocate successively larger pools up to 8 megs
1830 if (npools)
1831 { size_t n;
1832
1833 n = config.minPoolSize + config.incPoolSize * npools;
1834 if (n > config.maxPoolSize)
1835 n = config.maxPoolSize; // cap pool size
1836 n *= (1 << 20) / PAGESIZE; // convert MB to pages
1837 if (npages < n)
1838 npages = n;
1839 }
1840
1841 //printf("npages = %d\n", npages);
1842
1843 auto pool = cast(Pool *)cstdlib.calloc(1, isLargeObject ? LargeObjectPool.sizeof : SmallObjectPool.sizeof);
1844 if (pool)
1845 {
1846 pool.initialize(npages, isLargeObject);
1847 if (!pool.baseAddr || !pooltable.insert(pool))
1848 {
1849 pool.Dtor();
1850 cstdlib.free(pool);
1851 return null;
1852 }
1853 }
1854
1855 mappedPages += npages;
1856
1857 if (config.profile)
1858 {
1859 if (mappedPages * PAGESIZE > maxPoolMemory)
1860 maxPoolMemory = mappedPages * PAGESIZE;
1861 }
1862 return pool;
1863 }
1864
1865 /**
1866 * Allocate a page of bin's.
1867 * Returns:
1868 * head of a single linked list of new entries
1869 */
1870 List* allocPage(Bins bin) nothrow
1871 {
1872 //debug(PRINTF) printf("Gcx::allocPage(bin = %d)\n", bin);
1873 for (size_t n = 0; n < npools; n++)
1874 {
1875 Pool* pool = pooltable[n];
1876 if (pool.isLargeObject)
1877 continue;
1878 if (List* p = (cast(SmallObjectPool*)pool).allocPage(bin))
1879 {
1880 ++usedSmallPages;
1881 return p;
1882 }
1883 }
1884 return null;
1885 }
1886
1887 static struct ToScanStack
1888 {
1889 nothrow:
1890 @disable this(this);
1891
1892 void reset()
1893 {
1894 _length = 0;
1895 os_mem_unmap(_p, _cap * Range.sizeof);
1896 _p = null;
1897 _cap = 0;
1898 }
1899
1900 void push(Range rng)
1901 {
1902 if (_length == _cap) grow();
1903 _p[_length++] = rng;
1904 }
1905
1906 Range pop()
1907 in { assert(!empty); }
1908 body
1909 {
1910 return _p[--_length];
1911 }
1912
1913 ref inout(Range) opIndex(size_t idx) inout
1914 in { assert(idx < _length); }
1915 body
1916 {
1917 return _p[idx];
1918 }
1919
1920 @property size_t length() const { return _length; }
1921 @property bool empty() const { return !length; }
1922
1923 private:
1924 void grow()
1925 {
1926 enum initSize = 64 * 1024; // Windows VirtualAlloc granularity
1927 immutable ncap = _cap ? 2 * _cap : initSize / Range.sizeof;
1928 auto p = cast(Range*)os_mem_map(ncap * Range.sizeof);
1929 if (p is null) onOutOfMemoryErrorNoGC();
1930 if (_p !is null)
1931 {
1932 p[0 .. _length] = _p[0 .. _length];
1933 os_mem_unmap(_p, _cap * Range.sizeof);
1934 }
1935 _p = p;
1936 _cap = ncap;
1937 }
1938
1939 size_t _length;
1940 Range* _p;
1941 size_t _cap;
1942 }
1943
1944 ToScanStack toscan;
1945
1946 /**
1947 * Search a range of memory values and mark any pointers into the GC pool.
1948 */
1949 void mark(void *pbot, void *ptop) scope nothrow
1950 {
1951 void **p1 = cast(void **)pbot;
1952 void **p2 = cast(void **)ptop;
1953
1954 // limit the amount of ranges added to the toscan stack
1955 enum FANOUT_LIMIT = 32;
1956 size_t stackPos;
1957 Range[FANOUT_LIMIT] stack = void;
1958
1959 Lagain:
1960 size_t pcache = 0;
1961
1962 // let dmd allocate a register for this.pools
1963 auto pools = pooltable.pools;
1964 const highpool = pooltable.npools - 1;
1965 const minAddr = pooltable.minAddr;
1966 const maxAddr = pooltable.maxAddr;
1967
1968 //printf("marking range: [%p..%p] (%#zx)\n", p1, p2, cast(size_t)p2 - cast(size_t)p1);
1969 Lnext: for (; p1 < p2; p1++)
1970 {
1971 auto p = *p1;
1972
1973 //if (log) debug(PRINTF) printf("\tmark %p\n", p);
1974 if (p >= minAddr && p < maxAddr)
1975 {
1976 if ((cast(size_t)p & ~cast(size_t)(PAGESIZE-1)) == pcache)
1977 continue;
1978
1979 Pool* pool = void;
1980 size_t low = 0;
1981 size_t high = highpool;
1982 while (true)
1983 {
1984 size_t mid = (low + high) >> 1;
1985 pool = pools[mid];
1986 if (p < pool.baseAddr)
1987 high = mid - 1;
1988 else if (p >= pool.topAddr)
1989 low = mid + 1;
1990 else break;
1991
1992 if (low > high)
1993 continue Lnext;
1994 }
1995 size_t offset = cast(size_t)(p - pool.baseAddr);
1996 size_t biti = void;
1997 size_t pn = offset / PAGESIZE;
1998 Bins bin = cast(Bins)pool.pagetable[pn];
1999 void* base = void;
2000
2001 //debug(PRINTF) printf("\t\tfound pool %p, base=%p, pn = %zd, bin = %d, biti = x%x\n", pool, pool.baseAddr, pn, bin, biti);
2002
2003 // Adjust bit to be at start of allocated memory block
2004 if (bin < B_PAGE)
2005 {
2006 // We don't care abou setting pointsToBase correctly
2007 // because it's ignored for small object pools anyhow.
2008 auto offsetBase = offset & notbinsize[bin];
2009 biti = offsetBase >> pool.shiftBy;
2010 base = pool.baseAddr + offsetBase;
2011 //debug(PRINTF) printf("\t\tbiti = x%x\n", biti);
2012
2013 if (!pool.mark.set(biti) && !pool.noscan.test(biti)) {
2014 stack[stackPos++] = Range(base, base + binsize[bin]);
2015 if (stackPos == stack.length)
2016 break;
2017 }
2018 }
2019 else if (bin == B_PAGE)
2020 {
2021 auto offsetBase = offset & notbinsize[bin];
2022 base = pool.baseAddr + offsetBase;
2023 biti = offsetBase >> pool.shiftBy;
2024 //debug(PRINTF) printf("\t\tbiti = x%x\n", biti);
2025
2026 pcache = cast(size_t)p & ~cast(size_t)(PAGESIZE-1);
2027
2028 // For the NO_INTERIOR attribute. This tracks whether
2029 // the pointer is an interior pointer or points to the
2030 // base address of a block.
2031 bool pointsToBase = (base == sentinel_sub(p));
2032 if (!pointsToBase && pool.nointerior.nbits && pool.nointerior.test(biti))
2033 continue;
2034
2035 if (!pool.mark.set(biti) && !pool.noscan.test(biti)) {
2036 stack[stackPos++] = Range(base, base + pool.bPageOffsets[pn] * PAGESIZE);
2037 if (stackPos == stack.length)
2038 break;
2039 }
2040 }
2041 else if (bin == B_PAGEPLUS)
2042 {
2043 pn -= pool.bPageOffsets[pn];
2044 base = pool.baseAddr + (pn * PAGESIZE);
2045 biti = pn * (PAGESIZE >> pool.shiftBy);
2046
2047 pcache = cast(size_t)p & ~cast(size_t)(PAGESIZE-1);
2048 if (pool.nointerior.nbits && pool.nointerior.test(biti))
2049 continue;
2050
2051 if (!pool.mark.set(biti) && !pool.noscan.test(biti)) {
2052 stack[stackPos++] = Range(base, base + pool.bPageOffsets[pn] * PAGESIZE);
2053 if (stackPos == stack.length)
2054 break;
2055 }
2056 }
2057 else
2058 {
2059 // Don't mark bits in B_FREE pages
2060 assert(bin == B_FREE);
2061 continue;
2062 }
2063 }
2064 }
2065
2066 Range next=void;
2067 if (p1 < p2)
2068 {
2069 // local stack is full, push it to the global stack
2070 assert(stackPos == stack.length);
2071 toscan.push(Range(p1, p2));
2072 // reverse order for depth-first-order traversal
2073 foreach_reverse (ref rng; stack[0 .. $ - 1])
2074 toscan.push(rng);
2075 stackPos = 0;
2076 next = stack[$-1];
2077 }
2078 else if (stackPos)
2079 {
2080 // pop range from local stack and recurse
2081 next = stack[--stackPos];
2082 }
2083 else if (!toscan.empty)
2084 {
2085 // pop range from global stack and recurse
2086 next = toscan.pop();
2087 }
2088 else
2089 {
2090 // nothing more to do
2091 return;
2092 }
2093 p1 = cast(void**)next.pbot;
2094 p2 = cast(void**)next.ptop;
2095 // printf(" pop [%p..%p] (%#zx)\n", p1, p2, cast(size_t)p2 - cast(size_t)p1);
2096 goto Lagain;
2097 }
2098
2099 // collection step 1: prepare freebits and mark bits
2100 void prepare() nothrow
2101 {
2102 size_t n;
2103 Pool* pool;
2104
2105 for (n = 0; n < npools; n++)
2106 {
2107 pool = pooltable[n];
2108 pool.mark.zero();
2109 if (!pool.isLargeObject) pool.freebits.zero();
2110 }
2111
2112 debug(COLLECT_PRINTF) printf("Set bits\n");
2113
2114 // Mark each free entry, so it doesn't get scanned
2115 for (n = 0; n < B_PAGE; n++)
2116 {
2117 for (List *list = bucket[n]; list; list = list.next)
2118 {
2119 pool = list.pool;
2120 assert(pool);
2121 pool.freebits.set(cast(size_t)(cast(void*)list - pool.baseAddr) / 16);
2122 }
2123 }
2124
2125 debug(COLLECT_PRINTF) printf("Marked free entries.\n");
2126
2127 for (n = 0; n < npools; n++)
2128 {
2129 pool = pooltable[n];
2130 if (!pool.isLargeObject)
2131 {
2132 pool.mark.copy(&pool.freebits);
2133 }
2134 }
2135 }
2136
2137 // collection step 2: mark roots and heap
2138 void markAll(bool nostack) nothrow
2139 {
2140 if (!nostack)
2141 {
2142 debug(COLLECT_PRINTF) printf("\tscan stacks.\n");
2143 // Scan stacks and registers for each paused thread
2144 thread_scanAll(&mark);
2145 }
2146
2147 // Scan roots[]
2148 debug(COLLECT_PRINTF) printf("\tscan roots[]\n");
2149 foreach (root; roots)
2150 {
2151 mark(cast(void*)&root.proot, cast(void*)(&root.proot + 1));
2152 }
2153
2154 // Scan ranges[]
2155 debug(COLLECT_PRINTF) printf("\tscan ranges[]\n");
2156 //log++;
2157 foreach (range; ranges)
2158 {
2159 debug(COLLECT_PRINTF) printf("\t\t%p .. %p\n", range.pbot, range.ptop);
2160 mark(range.pbot, range.ptop);
2161 }
2162 //log--;
2163 }
2164
2165 // collection step 3: free all unreferenced objects
2166 size_t sweep() nothrow
2167 {
2168 // Free up everything not marked
2169 debug(COLLECT_PRINTF) printf("\tfree'ing\n");
2170 size_t freedLargePages;
2171 size_t freed;
2172 for (size_t n = 0; n < npools; n++)
2173 {
2174 size_t pn;
2175 Pool* pool = pooltable[n];
2176
2177 if (pool.isLargeObject)
2178 {
2179 for (pn = 0; pn < pool.npages; pn++)
2180 {
2181 Bins bin = cast(Bins)pool.pagetable[pn];
2182 if (bin > B_PAGE) continue;
2183 size_t biti = pn;
2184
2185 if (!pool.mark.test(biti))
2186 {
2187 void *p = pool.baseAddr + pn * PAGESIZE;
2188 void* q = sentinel_add(p);
2189 sentinel_Invariant(q);
2190
2191 if (pool.finals.nbits && pool.finals.clear(biti))
2192 {
2193 size_t size = pool.bPageOffsets[pn] * PAGESIZE - SENTINEL_EXTRA;
2194 uint attr = pool.getBits(biti);
2195 rt_finalizeFromGC(q, size, attr);
2196 }
2197
2198 pool.clrBits(biti, ~BlkAttr.NONE ^ BlkAttr.FINALIZE);
2199
2200 debug(COLLECT_PRINTF) printf("\tcollecting big %p\n", p);
2201 log_free(q);
2202 pool.pagetable[pn] = B_FREE;
2203 if (pn < pool.searchStart) pool.searchStart = pn;
2204 freedLargePages++;
2205 pool.freepages++;
2206
2207 debug (MEMSTOMP) memset(p, 0xF3, PAGESIZE);
2208 while (pn + 1 < pool.npages && pool.pagetable[pn + 1] == B_PAGEPLUS)
2209 {
2210 pn++;
2211 pool.pagetable[pn] = B_FREE;
2212
2213 // Don't need to update searchStart here because
2214 // pn is guaranteed to be greater than last time
2215 // we updated it.
2216
2217 pool.freepages++;
2218 freedLargePages++;
2219
2220 debug (MEMSTOMP)
2221 { p += PAGESIZE;
2222 memset(p, 0xF3, PAGESIZE);
2223 }
2224 }
2225 pool.largestFree = pool.freepages; // invalidate
2226 }
2227 }
2228 }
2229 else
2230 {
2231
2232 for (pn = 0; pn < pool.npages; pn++)
2233 {
2234 Bins bin = cast(Bins)pool.pagetable[pn];
2235
2236 if (bin < B_PAGE)
2237 {
2238 immutable size = binsize[bin];
2239 void *p = pool.baseAddr + pn * PAGESIZE;
2240 void *ptop = p + PAGESIZE;
2241 immutable base = pn * (PAGESIZE/16);
2242 immutable bitstride = size / 16;
2243
2244 bool freeBits;
2245 PageBits toFree;
2246
2247 for (size_t i; p < ptop; p += size, i += bitstride)
2248 {
2249 immutable biti = base + i;
2250
2251 if (!pool.mark.test(biti))
2252 {
2253 void* q = sentinel_add(p);
2254 sentinel_Invariant(q);
2255
2256 if (pool.finals.nbits && pool.finals.test(biti))
2257 rt_finalizeFromGC(q, size - SENTINEL_EXTRA, pool.getBits(biti));
2258
2259 freeBits = true;
2260 toFree.set(i);
2261
2262 debug(COLLECT_PRINTF) printf("\tcollecting %p\n", p);
2263 log_free(sentinel_add(p));
2264
2265 debug (MEMSTOMP) memset(p, 0xF3, size);
2266
2267 freed += size;
2268 }
2269 }
2270
2271 if (freeBits)
2272 pool.freePageBits(pn, toFree);
2273 }
2274 }
2275 }
2276 }
2277
2278 assert(freedLargePages <= usedLargePages);
2279 usedLargePages -= freedLargePages;
2280 debug(COLLECT_PRINTF) printf("\tfree'd %u bytes, %u pages from %u pools\n", freed, freedLargePages, npools);
2281 return freedLargePages;
2282 }
2283
2284 // collection step 4: recover pages with no live objects, rebuild free lists
2285 size_t recover() nothrow
2286 {
2287 // init tail list
2288 List**[B_PAGE] tail = void;
2289 foreach (i, ref next; tail)
2290 next = &bucket[i];
2291
2292 // Free complete pages, rebuild free list
2293 debug(COLLECT_PRINTF) printf("\tfree complete pages\n");
2294 size_t freedSmallPages;
2295 for (size_t n = 0; n < npools; n++)
2296 {
2297 size_t pn;
2298 Pool* pool = pooltable[n];
2299
2300 if (pool.isLargeObject)
2301 continue;
2302
2303 for (pn = 0; pn < pool.npages; pn++)
2304 {
2305 Bins bin = cast(Bins)pool.pagetable[pn];
2306 size_t biti;
2307 size_t u;
2308
2309 if (bin < B_PAGE)
2310 {
2311 size_t size = binsize[bin];
2312 size_t bitstride = size / 16;
2313 size_t bitbase = pn * (PAGESIZE / 16);
2314 size_t bittop = bitbase + (PAGESIZE / 16);
2315 void* p;
2316
2317 biti = bitbase;
2318 for (biti = bitbase; biti < bittop; biti += bitstride)
2319 {
2320 if (!pool.freebits.test(biti))
2321 goto Lnotfree;
2322 }
2323 pool.pagetable[pn] = B_FREE;
2324 if (pn < pool.searchStart) pool.searchStart = pn;
2325 pool.freepages++;
2326 freedSmallPages++;
2327 continue;
2328
2329 Lnotfree:
2330 p = pool.baseAddr + pn * PAGESIZE;
2331 for (u = 0; u < PAGESIZE; u += size)
2332 {
2333 biti = bitbase + u / 16;
2334 if (!pool.freebits.test(biti))
2335 continue;
2336 auto elem = cast(List *)(p + u);
2337 elem.pool = pool;
2338 *tail[bin] = elem;
2339 tail[bin] = &elem.next;
2340 }
2341 }
2342 }
2343 }
2344 // terminate tail list
2345 foreach (ref next; tail)
2346 *next = null;
2347
2348 assert(freedSmallPages <= usedSmallPages);
2349 usedSmallPages -= freedSmallPages;
2350 debug(COLLECT_PRINTF) printf("\trecovered pages = %d\n", freedSmallPages);
2351 return freedSmallPages;
2352 }
2353
2354 /**
2355 * Return number of full pages free'd.
2356 */
2357 size_t fullcollect(bool nostack = false) nothrow
2358 {
2359 MonoTime start, stop, begin;
2360
2361 if (config.profile)
2362 {
2363 begin = start = currTime;
2364 }
2365
2366 debug(COLLECT_PRINTF) printf("Gcx.fullcollect()\n");
2367 //printf("\tpool address range = %p .. %p\n", minAddr, maxAddr);
2368
2369 {
2370 // lock roots and ranges around suspending threads b/c they're not reentrant safe
2371 rangesLock.lock();
2372 rootsLock.lock();
2373 scope (exit)
2374 {
2375 rangesLock.unlock();
2376 rootsLock.unlock();
2377 }
2378 thread_suspendAll();
2379
2380 prepare();
2381
2382 if (config.profile)
2383 {
2384 stop = currTime;
2385 prepTime += (stop - start);
2386 start = stop;
2387 }
2388
2389 markAll(nostack);
2390
2391 thread_processGCMarks(&isMarked);
2392 thread_resumeAll();
2393 }
2394
2395 if (config.profile)
2396 {
2397 stop = currTime;
2398 markTime += (stop - start);
2399 Duration pause = stop - begin;
2400 if (pause > maxPauseTime)
2401 maxPauseTime = pause;
2402 start = stop;
2403 }
2404
2405 ConservativeGC._inFinalizer = true;
2406 size_t freedLargePages=void;
2407 {
2408 scope (failure) ConservativeGC._inFinalizer = false;
2409 freedLargePages = sweep();
2410 ConservativeGC._inFinalizer = false;
2411 }
2412
2413 if (config.profile)
2414 {
2415 stop = currTime;
2416 sweepTime += (stop - start);
2417 start = stop;
2418 }
2419
2420 immutable freedSmallPages = recover();
2421
2422 if (config.profile)
2423 {
2424 stop = currTime;
2425 recoverTime += (stop - start);
2426 ++numCollections;
2427 }
2428
2429 updateCollectThresholds();
2430
2431 return freedLargePages + freedSmallPages;
2432 }
2433
2434 /**
2435 * Returns true if the addr lies within a marked block.
2436 *
2437 * Warning! This should only be called while the world is stopped inside
2438 * the fullcollect function.
2439 */
2440 int isMarked(void *addr) scope nothrow
2441 {
2442 // first, we find the Pool this block is in, then check to see if the
2443 // mark bit is clear.
2444 auto pool = findPool(addr);
2445 if (pool)
2446 {
2447 auto offset = cast(size_t)(addr - pool.baseAddr);
2448 auto pn = offset / PAGESIZE;
2449 auto bins = cast(Bins)pool.pagetable[pn];
2450 size_t biti = void;
2451 if (bins <= B_PAGE)
2452 {
2453 biti = (offset & notbinsize[bins]) >> pool.shiftBy;
2454 }
2455 else if (bins == B_PAGEPLUS)
2456 {
2457 pn -= pool.bPageOffsets[pn];
2458 biti = pn * (PAGESIZE >> pool.shiftBy);
2459 }
2460 else // bins == B_FREE
2461 {
2462 assert(bins == B_FREE);
2463 return IsMarked.no;
2464 }
2465 return pool.mark.test(biti) ? IsMarked.yes : IsMarked.no;
2466 }
2467 return IsMarked.unknown;
2468 }
2469
2470
2471 /***** Leak Detector ******/
2472
2473
2474 debug (LOGGING)
2475 {
2476 LogArray current;
2477 LogArray prev;
2478
2479
2480 void log_init()
2481 {
2482 //debug(PRINTF) printf("+log_init()\n");
2483 current.reserve(1000);
2484 prev.reserve(1000);
2485 //debug(PRINTF) printf("-log_init()\n");
2486 }
2487
2488
2489 void log_malloc(void *p, size_t size) nothrow
2490 {
2491 //debug(PRINTF) printf("+log_malloc(p = %p, size = %zd)\n", p, size);
2492 Log log;
2493
2494 log.p = p;
2495 log.size = size;
2496 log.line = GC.line;
2497 log.file = GC.file;
2498 log.parent = null;
2499
2500 GC.line = 0;
2501 GC.file = null;
2502
2503 current.push(log);
2504 //debug(PRINTF) printf("-log_malloc()\n");
2505 }
2506
2507
2508 void log_free(void *p) nothrow
2509 {
2510 //debug(PRINTF) printf("+log_free(%p)\n", p);
2511 auto i = current.find(p);
2512 if (i == OPFAIL)
2513 {
2514 debug(PRINTF) printf("free'ing unallocated memory %p\n", p);
2515 }
2516 else
2517 current.remove(i);
2518 //debug(PRINTF) printf("-log_free()\n");
2519 }
2520
2521
2522 void log_collect() nothrow
2523 {
2524 //debug(PRINTF) printf("+log_collect()\n");
2525 // Print everything in current that is not in prev
2526
2527 debug(PRINTF) printf("New pointers this cycle: --------------------------------\n");
2528 size_t used = 0;
2529 for (size_t i = 0; i < current.dim; i++)
2530 {
2531 auto j = prev.find(current.data[i].p);
2532 if (j == OPFAIL)
2533 current.data[i].print();
2534 else
2535 used++;
2536 }
2537
2538 debug(PRINTF) printf("All roots this cycle: --------------------------------\n");
2539 for (size_t i = 0; i < current.dim; i++)
2540 {
2541 void* p = current.data[i].p;
2542 if (!findPool(current.data[i].parent))
2543 {
2544 auto j = prev.find(current.data[i].p);
2545 debug(PRINTF) printf(j == OPFAIL ? "N" : " ");
2546 current.data[i].print();
2547 }
2548 }
2549
2550 debug(PRINTF) printf("Used = %d-------------------------------------------------\n", used);
2551 prev.copy(¤t);
2552
2553 debug(PRINTF) printf("-log_collect()\n");
2554 }
2555
2556
2557 void log_parent(void *p, void *parent) nothrow
2558 {
2559 //debug(PRINTF) printf("+log_parent()\n");
2560 auto i = current.find(p);
2561 if (i == OPFAIL)
2562 {
2563 debug(PRINTF) printf("parent'ing unallocated memory %p, parent = %p\n", p, parent);
2564 Pool *pool;
2565 pool = findPool(p);
2566 assert(pool);
2567 size_t offset = cast(size_t)(p - pool.baseAddr);
2568 size_t biti;
2569 size_t pn = offset / PAGESIZE;
2570 Bins bin = cast(Bins)pool.pagetable[pn];
2571 biti = (offset & notbinsize[bin]);
2572 debug(PRINTF) printf("\tbin = %d, offset = x%x, biti = x%x\n", bin, offset, biti);
2573 }
2574 else
2575 {
2576 current.data[i].parent = parent;
2577 }
2578 //debug(PRINTF) printf("-log_parent()\n");
2579 }
2580
2581 }
2582 else
2583 {
2584 void log_init() nothrow { }
2585 void log_malloc(void *p, size_t size) nothrow { }
2586 void log_free(void *p) nothrow { }
2587 void log_collect() nothrow { }
2588 void log_parent(void *p, void *parent) nothrow { }
2589 }
2590 }
2591
2592 /* ============================ Pool =============================== */
2593
2594 struct Pool
2595 {
2596 void* baseAddr;
2597 void* topAddr;
2598 GCBits mark; // entries already scanned, or should not be scanned
2599 GCBits freebits; // entries that are on the free list
2600 GCBits finals; // entries that need finalizer run on them
2601 GCBits structFinals;// struct entries that need a finalzier run on them
2602 GCBits noscan; // entries that should not be scanned
2603 GCBits appendable; // entries that are appendable
2604 GCBits nointerior; // interior pointers should be ignored.
2605 // Only implemented for large object pools.
2606 size_t npages;
2607 size_t freepages; // The number of pages not in use.
2608 ubyte* pagetable;
2609
2610 bool isLargeObject;
2611
2612 uint shiftBy; // shift count for the divisor used for determining bit indices.
2613
2614 // This tracks how far back we have to go to find the nearest B_PAGE at
2615 // a smaller address than a B_PAGEPLUS. To save space, we use a uint.
2616 // This limits individual allocations to 16 terabytes, assuming a 4k
2617 // pagesize.
2618 uint* bPageOffsets;
2619
2620 // This variable tracks a conservative estimate of where the first free
2621 // page in this pool is, so that if a lot of pages towards the beginning
2622 // are occupied, we can bypass them in O(1).
2623 size_t searchStart;
2624 size_t largestFree; // upper limit for largest free chunk in large object pool
2625
2626 void initialize(size_t npages, bool isLargeObject) nothrow
2627 {
2628 this.isLargeObject = isLargeObject;
2629 size_t poolsize;
2630
2631 shiftBy = isLargeObject ? 12 : 4;
2632
2633 //debug(PRINTF) printf("Pool::Pool(%u)\n", npages);
2634 poolsize = npages * PAGESIZE;
2635 assert(poolsize >= POOLSIZE);
2636 baseAddr = cast(byte *)os_mem_map(poolsize);
2637
2638 // Some of the code depends on page alignment of memory pools
2639 assert((cast(size_t)baseAddr & (PAGESIZE - 1)) == 0);
2640
2641 if (!baseAddr)
2642 {
2643 //debug(PRINTF) printf("GC fail: poolsize = x%zx, errno = %d\n", poolsize, errno);
2644 //debug(PRINTF) printf("message = '%s'\n", sys_errlist[errno]);
2645
2646 npages = 0;
2647 poolsize = 0;
2648 }
2649 //assert(baseAddr);
2650 topAddr = baseAddr + poolsize;
2651 auto nbits = cast(size_t)poolsize >> shiftBy;
2652
2653 mark.alloc(nbits);
2654
2655 // pagetable already keeps track of what's free for the large object
2656 // pool.
2657 if (!isLargeObject)
2658 {
2659 freebits.alloc(nbits);
2660 }
2661
2662 noscan.alloc(nbits);
2663 appendable.alloc(nbits);
2664
2665 pagetable = cast(ubyte*)cstdlib.malloc(npages);
2666 if (!pagetable)
2667 onOutOfMemoryErrorNoGC();
2668
2669 if (isLargeObject)
2670 {
2671 bPageOffsets = cast(uint*)cstdlib.malloc(npages * uint.sizeof);
2672 if (!bPageOffsets)
2673 onOutOfMemoryErrorNoGC();
2674 }
2675
2676 memset(pagetable, B_FREE, npages);
2677
2678 this.npages = npages;
2679 this.freepages = npages;
2680 this.searchStart = 0;
2681 this.largestFree = npages;
2682 }
2683
2684
2685 void Dtor() nothrow
2686 {
2687 if (baseAddr)
2688 {
2689 int result;
2690
2691 if (npages)
2692 {
2693 result = os_mem_unmap(baseAddr, npages * PAGESIZE);
2694 assert(result == 0);
2695 npages = 0;
2696 }
2697
2698 baseAddr = null;
2699 topAddr = null;
2700 }
2701 if (pagetable)
2702 {
2703 cstdlib.free(pagetable);
2704 pagetable = null;
2705 }
2706
2707 if (bPageOffsets)
2708 cstdlib.free(bPageOffsets);
2709
2710 mark.Dtor();
2711 if (isLargeObject)
2712 {
2713 nointerior.Dtor();
2714 }
2715 else
2716 {
2717 freebits.Dtor();
2718 }
2719 finals.Dtor();
2720 structFinals.Dtor();
2721 noscan.Dtor();
2722 appendable.Dtor();
2723 }
2724
2725 /**
2726 *
2727 */
2728 uint getBits(size_t biti) nothrow
2729 {
2730 uint bits;
2731
2732 if (finals.nbits && finals.test(biti))
2733 bits |= BlkAttr.FINALIZE;
2734 if (structFinals.nbits && structFinals.test(biti))
2735 bits |= BlkAttr.STRUCTFINAL;
2736 if (noscan.test(biti))
2737 bits |= BlkAttr.NO_SCAN;
2738 if (nointerior.nbits && nointerior.test(biti))
2739 bits |= BlkAttr.NO_INTERIOR;
2740 if (appendable.test(biti))
2741 bits |= BlkAttr.APPENDABLE;
2742 return bits;
2743 }
2744
2745 /**
2746 *
2747 */
2748 void clrBits(size_t biti, uint mask) nothrow
2749 {
2750 immutable dataIndex = biti >> GCBits.BITS_SHIFT;
2751 immutable bitOffset = biti & GCBits.BITS_MASK;
2752 immutable keep = ~(GCBits.BITS_1 << bitOffset);
2753
2754 if (mask & BlkAttr.FINALIZE && finals.nbits)
2755 finals.data[dataIndex] &= keep;
2756
2757 if (structFinals.nbits && (mask & BlkAttr.STRUCTFINAL))
2758 structFinals.data[dataIndex] &= keep;
2759
2760 if (mask & BlkAttr.NO_SCAN)
2761 noscan.data[dataIndex] &= keep;
2762 if (mask & BlkAttr.APPENDABLE)
2763 appendable.data[dataIndex] &= keep;
2764 if (nointerior.nbits && (mask & BlkAttr.NO_INTERIOR))
2765 nointerior.data[dataIndex] &= keep;
2766 }
2767
2768 /**
2769 *
2770 */
2771 void setBits(size_t biti, uint mask) nothrow
2772 {
2773 // Calculate the mask and bit offset once and then use it to
2774 // set all of the bits we need to set.
2775 immutable dataIndex = biti >> GCBits.BITS_SHIFT;
2776 immutable bitOffset = biti & GCBits.BITS_MASK;
2777 immutable orWith = GCBits.BITS_1 << bitOffset;
2778
2779 if (mask & BlkAttr.STRUCTFINAL)
2780 {
2781 if (!structFinals.nbits)
2782 structFinals.alloc(mark.nbits);
2783 structFinals.data[dataIndex] |= orWith;
2784 }
2785
2786 if (mask & BlkAttr.FINALIZE)
2787 {
2788 if (!finals.nbits)
2789 finals.alloc(mark.nbits);
2790 finals.data[dataIndex] |= orWith;
2791 }
2792
2793 if (mask & BlkAttr.NO_SCAN)
2794 {
2795 noscan.data[dataIndex] |= orWith;
2796 }
2797 // if (mask & BlkAttr.NO_MOVE)
2798 // {
2799 // if (!nomove.nbits)
2800 // nomove.alloc(mark.nbits);
2801 // nomove.data[dataIndex] |= orWith;
2802 // }
2803 if (mask & BlkAttr.APPENDABLE)
2804 {
2805 appendable.data[dataIndex] |= orWith;
2806 }
2807
2808 if (isLargeObject && (mask & BlkAttr.NO_INTERIOR))
2809 {
2810 if (!nointerior.nbits)
2811 nointerior.alloc(mark.nbits);
2812 nointerior.data[dataIndex] |= orWith;
2813 }
2814 }
2815
2816 void freePageBits(size_t pagenum, in ref PageBits toFree) nothrow
2817 {
2818 assert(!isLargeObject);
2819 assert(!nointerior.nbits); // only for large objects
2820
2821 import core.internal.traits : staticIota;
2822 immutable beg = pagenum * (PAGESIZE / 16 / GCBits.BITS_PER_WORD);
2823 foreach (i; staticIota!(0, PageBits.length))
2824 {
2825 immutable w = toFree[i];
2826 if (!w) continue;
2827
2828 immutable wi = beg + i;
2829 freebits.data[wi] |= w;
2830 noscan.data[wi] &= ~w;
2831 appendable.data[wi] &= ~w;
2832 }
2833
2834 if (finals.nbits)
2835 {
2836 foreach (i; staticIota!(0, PageBits.length))
2837 if (toFree[i])
2838 finals.data[beg + i] &= ~toFree[i];
2839 }
2840
2841 if (structFinals.nbits)
2842 {
2843 foreach (i; staticIota!(0, PageBits.length))
2844 if (toFree[i])
2845 structFinals.data[beg + i] &= ~toFree[i];
2846 }
2847 }
2848
2849 /**
2850 * Given a pointer p in the p, return the pagenum.
2851 */
2852 size_t pagenumOf(void *p) const nothrow
2853 in
2854 {
2855 assert(p >= baseAddr);
2856 assert(p < topAddr);
2857 }
2858 body
2859 {
2860 return cast(size_t)(p - baseAddr) / PAGESIZE;
2861 }
2862
2863 @property bool isFree() const pure nothrow
2864 {
2865 return npages == freepages;
2866 }
2867
2868 size_t slGetSize(void* p) nothrow
2869 {
2870 if (isLargeObject)
2871 return (cast(LargeObjectPool*)&this).getSize(p);
2872 else
2873 return (cast(SmallObjectPool*)&this).getSize(p);
2874 }
2875
2876 BlkInfo slGetInfo(void* p) nothrow
2877 {
2878 if (isLargeObject)
2879 return (cast(LargeObjectPool*)&this).getInfo(p);
2880 else
2881 return (cast(SmallObjectPool*)&this).getInfo(p);
2882 }
2883
2884
2885 void Invariant() const {}
2886
2887 debug(INVARIANT)
2888 invariant()
2889 {
2890 //mark.Invariant();
2891 //scan.Invariant();
2892 //freebits.Invariant();
2893 //finals.Invariant();
2894 //structFinals.Invariant();
2895 //noscan.Invariant();
2896 //appendable.Invariant();
2897 //nointerior.Invariant();
2898
2899 if (baseAddr)
2900 {
2901 //if (baseAddr + npages * PAGESIZE != topAddr)
2902 //printf("baseAddr = %p, npages = %d, topAddr = %p\n", baseAddr, npages, topAddr);
2903 assert(baseAddr + npages * PAGESIZE == topAddr);
2904 }
2905
2906 if (pagetable !is null)
2907 {
2908 for (size_t i = 0; i < npages; i++)
2909 {
2910 Bins bin = cast(Bins)pagetable[i];
2911 assert(bin < B_MAX);
2912 }
2913 }
2914 }
2915 }
2916
2917 struct LargeObjectPool
2918 {
2919 Pool base;
2920 alias base this;
2921
2922 void updateOffsets(size_t fromWhere) nothrow
2923 {
2924 assert(pagetable[fromWhere] == B_PAGE);
2925 size_t pn = fromWhere + 1;
2926 for (uint offset = 1; pn < npages; pn++, offset++)
2927 {
2928 if (pagetable[pn] != B_PAGEPLUS) break;
2929 bPageOffsets[pn] = offset;
2930 }
2931
2932 // Store the size of the block in bPageOffsets[fromWhere].
2933 bPageOffsets[fromWhere] = cast(uint) (pn - fromWhere);
2934 }
2935
2936 /**
2937 * Allocate n pages from Pool.
2938 * Returns OPFAIL on failure.
2939 */
2940 size_t allocPages(size_t n) nothrow
2941 {
2942 if (largestFree < n || searchStart + n > npages)
2943 return OPFAIL;
2944
2945 //debug(PRINTF) printf("Pool::allocPages(n = %d)\n", n);
2946 size_t largest = 0;
2947 if (pagetable[searchStart] == B_PAGEPLUS)
2948 {
2949 searchStart -= bPageOffsets[searchStart]; // jump to B_PAGE
2950 searchStart += bPageOffsets[searchStart];
2951 }
2952 while (searchStart < npages && pagetable[searchStart] == B_PAGE)
2953 searchStart += bPageOffsets[searchStart];
2954
2955 for (size_t i = searchStart; i < npages; )
2956 {
2957 assert(pagetable[i] == B_FREE);
2958 size_t p = 1;
2959 while (p < n && i + p < npages && pagetable[i + p] == B_FREE)
2960 p++;
2961
2962 if (p == n)
2963 return i;
2964
2965 if (p > largest)
2966 largest = p;
2967
2968 i += p;
2969 while (i < npages && pagetable[i] == B_PAGE)
2970 {
2971 // we have the size information, so we skip a whole bunch of pages.
2972 i += bPageOffsets[i];
2973 }
2974 }
2975
2976 // not enough free pages found, remember largest free chunk
2977 largestFree = largest;
2978 return OPFAIL;
2979 }
2980
2981 /**
2982 * Free npages pages starting with pagenum.
2983 */
2984 void freePages(size_t pagenum, size_t npages) nothrow
2985 {
2986 //memset(&pagetable[pagenum], B_FREE, npages);
2987 if (pagenum < searchStart)
2988 searchStart = pagenum;
2989
2990 for (size_t i = pagenum; i < npages + pagenum; i++)
2991 {
2992 if (pagetable[i] < B_FREE)
2993 {
2994 freepages++;
2995 }
2996
2997 pagetable[i] = B_FREE;
2998 }
2999 largestFree = freepages; // invalidate
3000 }
3001
3002 /**
3003 * Get size of pointer p in pool.
3004 */
3005 size_t getSize(void *p) const nothrow
3006 in
3007 {
3008 assert(p >= baseAddr);
3009 assert(p < topAddr);
3010 }
3011 body
3012 {
3013 size_t pagenum = pagenumOf(p);
3014 Bins bin = cast(Bins)pagetable[pagenum];
3015 assert(bin == B_PAGE);
3016 return bPageOffsets[pagenum] * PAGESIZE;
3017 }
3018
3019 /**
3020 *
3021 */
3022 BlkInfo getInfo(void* p) nothrow
3023 {
3024 BlkInfo info;
3025
3026 size_t offset = cast(size_t)(p - baseAddr);
3027 size_t pn = offset / PAGESIZE;
3028 Bins bin = cast(Bins)pagetable[pn];
3029
3030 if (bin == B_PAGEPLUS)
3031 pn -= bPageOffsets[pn];
3032 else if (bin != B_PAGE)
3033 return info; // no info for free pages
3034
3035 info.base = baseAddr + pn * PAGESIZE;
3036 info.size = bPageOffsets[pn] * PAGESIZE;
3037
3038 info.attr = getBits(pn);
3039 return info;
3040 }
3041
3042 void runFinalizers(in void[] segment) nothrow
3043 {
3044 foreach (pn; 0 .. npages)
3045 {
3046 Bins bin = cast(Bins)pagetable[pn];
3047 if (bin > B_PAGE)
3048 continue;
3049 size_t biti = pn;
3050
3051 if (!finals.test(biti))
3052 continue;
3053
3054 auto p = sentinel_add(baseAddr + pn * PAGESIZE);
3055 size_t size = bPageOffsets[pn] * PAGESIZE - SENTINEL_EXTRA;
3056 uint attr = getBits(biti);
3057
3058 if (!rt_hasFinalizerInSegment(p, size, attr, segment))
3059 continue;
3060
3061 rt_finalizeFromGC(p, size, attr);
3062
3063 clrBits(biti, ~BlkAttr.NONE);
3064
3065 if (pn < searchStart)
3066 searchStart = pn;
3067
3068 debug(COLLECT_PRINTF) printf("\tcollecting big %p\n", p);
3069 //log_free(sentinel_add(p));
3070
3071 size_t n = 1;
3072 for (; pn + n < npages; ++n)
3073 if (pagetable[pn + n] != B_PAGEPLUS)
3074 break;
3075 debug (MEMSTOMP) memset(baseAddr + pn * PAGESIZE, 0xF3, n * PAGESIZE);
3076 freePages(pn, n);
3077 }
3078 }
3079 }
3080
3081
3082 struct SmallObjectPool
3083 {
3084 Pool base;
3085 alias base this;
3086
3087 /**
3088 * Get size of pointer p in pool.
3089 */
3090 size_t getSize(void *p) const nothrow
3091 in
3092 {
3093 assert(p >= baseAddr);
3094 assert(p < topAddr);
3095 }
3096 body
3097 {
3098 size_t pagenum = pagenumOf(p);
3099 Bins bin = cast(Bins)pagetable[pagenum];
3100 assert(bin < B_PAGE);
3101 return binsize[bin];
3102 }
3103
3104 BlkInfo getInfo(void* p) nothrow
3105 {
3106 BlkInfo info;
3107 size_t offset = cast(size_t)(p - baseAddr);
3108 size_t pn = offset / PAGESIZE;
3109 Bins bin = cast(Bins)pagetable[pn];
3110
3111 if (bin >= B_PAGE)
3112 return info;
3113
3114 info.base = cast(void*)((cast(size_t)p) & notbinsize[bin]);
3115 info.size = binsize[bin];
3116 offset = info.base - baseAddr;
3117 info.attr = getBits(cast(size_t)(offset >> shiftBy));
3118
3119 return info;
3120 }
3121
3122 void runFinalizers(in void[] segment) nothrow
3123 {
3124 foreach (pn; 0 .. npages)
3125 {
3126 Bins bin = cast(Bins)pagetable[pn];
3127 if (bin >= B_PAGE)
3128 continue;
3129
3130 immutable size = binsize[bin];
3131 auto p = baseAddr + pn * PAGESIZE;
3132 const ptop = p + PAGESIZE;
3133 immutable base = pn * (PAGESIZE/16);
3134 immutable bitstride = size / 16;
3135
3136 bool freeBits;
3137 PageBits toFree;
3138
3139 for (size_t i; p < ptop; p += size, i += bitstride)
3140 {
3141 immutable biti = base + i;
3142
3143 if (!finals.test(biti))
3144 continue;
3145
3146 auto q = sentinel_add(p);
3147 uint attr = getBits(biti);
3148
3149 if (!rt_hasFinalizerInSegment(q, size, attr, segment))
3150 continue;
3151
3152 rt_finalizeFromGC(q, size, attr);
3153
3154 freeBits = true;
3155 toFree.set(i);
3156
3157 debug(COLLECT_PRINTF) printf("\tcollecting %p\n", p);
3158 //log_free(sentinel_add(p));
3159
3160 debug (MEMSTOMP) memset(p, 0xF3, size);
3161 }
3162
3163 if (freeBits)
3164 freePageBits(pn, toFree);
3165 }
3166 }
3167
3168 /**
3169 * Allocate a page of bin's.
3170 * Returns:
3171 * head of a single linked list of new entries
3172 */
3173 List* allocPage(Bins bin) nothrow
3174 {
3175 size_t pn;
3176 for (pn = searchStart; pn < npages; pn++)
3177 if (pagetable[pn] == B_FREE)
3178 goto L1;
3179
3180 return null;
3181
3182 L1:
3183 searchStart = pn + 1;
3184 pagetable[pn] = cast(ubyte)bin;
3185 freepages--;
3186
3187 // Convert page to free list
3188 size_t size = binsize[bin];
3189 void* p = baseAddr + pn * PAGESIZE;
3190 void* ptop = p + PAGESIZE - size;
3191 auto first = cast(List*) p;
3192
3193 for (; p < ptop; p += size)
3194 {
3195 (cast(List *)p).next = cast(List *)(p + size);
3196 (cast(List *)p).pool = &base;
3197 }
3198 (cast(List *)p).next = null;
3199 (cast(List *)p).pool = &base;
3200 return first;
3201 }
3202 }
3203
3204 unittest // bugzilla 14467
3205 {
3206 int[] arr = new int[10];
3207 assert(arr.capacity);
3208 arr = arr[$..$];
3209 assert(arr.capacity);
3210 }
3211
3212 unittest // bugzilla 15353
3213 {
3214 import core.memory : GC;
3215
3216 static struct Foo
3217 {
3218 ~this()
3219 {
3220 GC.free(buf); // ignored in finalizer
3221 }
3222
3223 void* buf;
3224 }
3225 new Foo(GC.malloc(10));
3226 GC.collect();
3227 }
3228
3229 unittest // bugzilla 15822
3230 {
3231 import core.memory : GC;
3232
3233 ubyte[16] buf;
3234 static struct Foo
3235 {
3236 ~this()
3237 {
3238 GC.removeRange(ptr);
3239 GC.removeRoot(ptr);
3240 }
3241
3242 ubyte* ptr;
3243 }
3244 GC.addRoot(buf.ptr);
3245 GC.addRange(buf.ptr, buf.length);
3246 new Foo(buf.ptr);
3247 GC.collect();
3248 }
3249
3250 unittest // bugzilla 1180
3251 {
3252 import core.exception;
3253 try
3254 {
3255 size_t x = size_t.max - 100;
3256 byte[] big_buf = new byte[x];
3257 }
3258 catch (OutOfMemoryError)
3259 {
3260 }
3261 }
3262
3263 /* ============================ SENTINEL =============================== */
3264
3265
3266 debug (SENTINEL)
3267 {
3268 const size_t SENTINEL_PRE = cast(size_t) 0xF4F4F4F4F4F4F4F4UL; // 32 or 64 bits
3269 const ubyte SENTINEL_POST = 0xF5; // 8 bits
3270 const uint SENTINEL_EXTRA = 2 * size_t.sizeof + 1;
3271
3272
3273 inout(size_t*) sentinel_size(inout void *p) nothrow { return &(cast(inout size_t *)p)[-2]; }
3274 inout(size_t*) sentinel_pre(inout void *p) nothrow { return &(cast(inout size_t *)p)[-1]; }
3275 inout(ubyte*) sentinel_post(inout void *p) nothrow { return &(cast(inout ubyte *)p)[*sentinel_size(p)]; }
3276
3277
3278 void sentinel_init(void *p, size_t size) nothrow
3279 {
3280 *sentinel_size(p) = size;
3281 *sentinel_pre(p) = SENTINEL_PRE;
3282 *sentinel_post(p) = SENTINEL_POST;
3283 }
3284
3285
3286 void sentinel_Invariant(const void *p) nothrow
3287 {
3288 debug
3289 {
3290 assert(*sentinel_pre(p) == SENTINEL_PRE);
3291 assert(*sentinel_post(p) == SENTINEL_POST);
3292 }
3293 else if (*sentinel_pre(p) != SENTINEL_PRE || *sentinel_post(p) != SENTINEL_POST)
3294 onInvalidMemoryOperationError(); // also trigger in release build
3295 }
3296
3297
3298 void *sentinel_add(void *p) nothrow
3299 {
3300 return p + 2 * size_t.sizeof;
3301 }
3302
3303
3304 void *sentinel_sub(void *p) nothrow
3305 {
3306 return p - 2 * size_t.sizeof;
3307 }
3308 }
3309 else
3310 {
3311 const uint SENTINEL_EXTRA = 0;
3312
3313
3314 void sentinel_init(void *p, size_t size) nothrow
3315 {
3316 }
3317
3318
3319 void sentinel_Invariant(const void *p) nothrow
3320 {
3321 }
3322
3323
3324 void *sentinel_add(void *p) nothrow
3325 {
3326 return p;
3327 }
3328
3329
3330 void *sentinel_sub(void *p) nothrow
3331 {
3332 return p;
3333 }
3334 }
3335
3336 debug (MEMSTOMP)
3337 unittest
3338 {
3339 import core.memory;
3340 auto p = cast(uint*)GC.malloc(uint.sizeof*3);
3341 assert(*p == 0xF0F0F0F0);
3342 p[2] = 0; // First two will be used for free list
3343 GC.free(p);
3344 assert(p[2] == 0xF2F2F2F2);
3345 }
3346
3347 debug (SENTINEL)
3348 unittest
3349 {
3350 import core.memory;
3351 auto p = cast(ubyte*)GC.malloc(1);
3352 assert(p[-1] == 0xF4);
3353 assert(p[ 1] == 0xF5);
3354 /*
3355 p[1] = 0;
3356 bool thrown;
3357 try
3358 GC.free(p);
3359 catch (Error e)
3360 thrown = true;
3361 p[1] = 0xF5;
3362 assert(thrown);
3363 */
3364 }
3365
3366 unittest
3367 {
3368 import core.memory;
3369
3370 // https://issues.dlang.org/show_bug.cgi?id=9275
3371 GC.removeRoot(null);
3372 GC.removeRoot(cast(void*)13);
3373 }
3374
3375 // improve predictability of coverage of code that is eventually not hit by other tests
3376 unittest
3377 {
3378 import core.memory;
3379 auto p = GC.malloc(260 << 20); // new pool has 390 MB
3380 auto q = GC.malloc(65 << 20); // next chunk (larger than 64MB to ensure the same pool is used)
3381 auto r = GC.malloc(65 << 20); // another chunk in same pool
3382 assert(p + (260 << 20) == q);
3383 assert(q + (65 << 20) == r);
3384 GC.free(q);
3385 // should trigger "assert(bin == B_FREE);" in mark due to dangling pointer q:
3386 GC.collect();
3387 // should trigger "break;" in extendNoSync:
3388 size_t sz = GC.extend(p, 64 << 20, 66 << 20); // trigger size after p large enough (but limited)
3389 assert(sz == 325 << 20);
3390 GC.free(p);
3391 GC.free(r);
3392 r = q; // ensure q is not trashed before collection above
3393
3394 p = GC.malloc(70 << 20); // from the same pool
3395 q = GC.malloc(70 << 20);
3396 r = GC.malloc(70 << 20);
3397 auto s = GC.malloc(70 << 20);
3398 auto t = GC.malloc(70 << 20); // 350 MB of 390 MB used
3399 assert(p + (70 << 20) == q);
3400 assert(q + (70 << 20) == r);
3401 assert(r + (70 << 20) == s);
3402 assert(s + (70 << 20) == t);
3403 GC.free(r); // ensure recalculation of largestFree in nxxt allocPages
3404 auto z = GC.malloc(75 << 20); // needs new pool
3405
3406 GC.free(p);
3407 GC.free(q);
3408 GC.free(s);
3409 GC.free(t);
3410 GC.free(z);
3411 GC.minimize(); // release huge pool
3412 }
3413
3414