]> git.llucax.com Git - software/dgc/cdgc.git/blob - rt/gc/cdgc/gc.d
f2d2f6ef3469f2bc75703fdd788bc7f3370064f4
[software/dgc/cdgc.git] / rt / gc / cdgc / gc.d
1 /**
2  * This module contains the garbage collector implementation.
3  *
4  * Copyright: Copyright (C) 2001-2007 Digital Mars, www.digitalmars.com.
5  *            All rights reserved.
6  * License:
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.
10  *
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
14  *  restrictions:
15  *
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
23  *     distribution.
24  * Authors:   Walter Bright, David Friedman, Sean Kelly
25  */
26
27 module rt.gc.cdgc.gc;
28
29 // D Programming Language Garbage Collector implementation
30
31 /************** Debugging ***************************/
32
33 //debug = COLLECT_PRINTF;       // turn on printf's
34 //debug = PTRCHECK;             // more pointer checking
35 //debug = PTRCHECK2;            // thorough but slow pointer checking
36
37 /*************** Configuration *********************/
38
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
42
43 /***************************************************/
44
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;
50
51 import cstdlib = tango.stdc.stdlib;
52 import cstring = tango.stdc.string;
53
54 /*
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.
58  */
59 void memset(void* dst, int c, size_t n)
60 {
61     // This number (32) has been determined empirically
62     if (n > 32) {
63         cstring.memset(dst, c, n);
64         return;
65     }
66     auto p = cast(ubyte*)(dst);
67     while (n-- > 0)
68         *p++ = c;
69 }
70
71 version (GNU)
72 {
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
76     //      be found.
77     static import gcc.builtins; // for __builtin_unwind_int
78 }
79
80 struct BlkInfo
81 {
82     void*  base;
83     size_t size;
84     uint   attr;
85 }
86
87 package enum BlkAttr : uint
88 {
89     FINALIZE = 0b0000_0001,
90     NO_SCAN  = 0b0000_0010,
91     NO_MOVE  = 0b0000_0100,
92     ALL_BITS = 0b1111_1111
93 }
94
95 package bool has_pointermap(uint attrs)
96 {
97     return !opts.options.conservative && !(attrs & BlkAttr.NO_SCAN);
98 }
99
100 private
101 {
102     alias void delegate(Object) DEvent;
103     alias void delegate( void*, void* ) scanFn;
104     enum { OPFAIL = ~cast(size_t)0 }
105
106     extern (C)
107     {
108         version (DigitalMars) version(OSX)
109             oid _d_osx_image_init();
110
111         void* rt_stackBottom();
112         void* rt_stackTop();
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 );
117
118         void thread_init();
119         bool thread_needLock();
120         void thread_suspendAll();
121         void thread_resumeAll();
122         void thread_scanAll( scanFn fn, void* curStackTop = null );
123
124         void onOutOfMemoryError();
125     }
126 }
127
128
129 enum
130 {
131     PAGESIZE =    4096,
132     POOLSIZE =   (4096*256),
133 }
134
135
136 enum
137 {
138     B_16,
139     B_32,
140     B_64,
141     B_128,
142     B_256,
143     B_512,
144     B_1024,
145     B_2048,
146     B_PAGE,             // start of large alloc
147     B_PAGEPLUS,         // continuation of large alloc
148     B_FREE,             // free page
149     B_MAX
150 }
151
152
153 alias ubyte Bins;
154
155
156 struct List
157 {
158     List *next;
159 }
160
161
162 struct Range
163 {
164     void *pbot;
165     void *ptop;
166     int opCmp(in Range other)
167     {
168         if (pbot < other.pbot)
169             return -1;
170         else
171         return cast(int)(pbot > other.pbot);
172     }
173 }
174
175
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) ];
179
180
181 /* ============================ GC =============================== */
182
183
184 class GCLock {} // just a dummy so we can get a global lock
185
186
187 struct GC
188 {
189     // global lock
190     ClassInfo lock;
191
192     void* p_cache;
193     size_t size_cache;
194
195     // !=0 means don't scan stack
196     uint no_stack;
197     bool any_changes;
198     void* stack_bottom;
199     uint inited;
200     /// Turn off collections if > 0
201     int disabled;
202
203     /// min(pool.baseAddr)
204     byte *min_addr;
205     /// max(pool.topAddr)
206     byte *max_addr;
207
208     /// Free list for each size
209     List*[B_MAX] free_list;
210
211     dynarray.DynArray!(void*) roots;
212     dynarray.DynArray!(Range) ranges;
213     dynarray.DynArray!(Pool) pools;
214
215     Stats stats;
216 }
217
218 // call locked if necessary
219 private T locked(T, alias Code)()
220 {
221     if (thread_needLock())
222         synchronized (gc.lock) return Code();
223     else
224        return Code();
225 }
226
227 private GC* gc;
228
229 bool Invariant()
230 {
231     assert (gc !is null);
232     if (gc.inited) {
233         for (size_t i = 0; i < gc.pools.length; i++) {
234             Pool* pool = gc.pools[i];
235             pool.Invariant();
236             if (i == 0)
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);
242         }
243
244         gc.roots.Invariant();
245         gc.ranges.Invariant();
246
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);
251         }
252
253         for (size_t i = 0; i < B_PAGE; i++)
254             for (List *list = gc.free_list[i]; list; list = list.next)
255             {
256             }
257     }
258     return true;
259 }
260
261
262 /**
263  * Find Pool that pointer is in.
264  * Return null if not in a Pool.
265  * Assume pools is sorted.
266  */
267 Pool *findPool(void *p)
268 {
269     if (p >= gc.min_addr && p < gc.max_addr)
270     {
271         if (gc.pools.length == 1)
272         {
273             return gc.pools[0];
274         }
275
276         for (size_t i = 0; i < gc.pools.length; i++)
277         {
278             Pool* pool = gc.pools[i];
279             if (p < pool.topAddr)
280             {
281                 if (pool.baseAddr <= p)
282                     return pool;
283                 break;
284             }
285         }
286     }
287     return null;
288 }
289
290
291 /**
292  * Determine the base address of the block containing p.  If p is not a gc
293  * allocated pointer, return null.
294  */
295 BlkInfo getInfo(void* p)
296 {
297     assert (p !is null);
298     Pool* pool = findPool(p);
299     if (pool is null)
300         return BlkInfo.init;
301     BlkInfo info;
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)) {
309             return BlkInfo.init;
310         }
311     }
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))
316             return BlkInfo.init;
317         info.size -= SENTINEL_EXTRA;
318     }
319     return info;
320 }
321
322
323 /**
324  * Compute bin for size.
325  */
326 static Bins findBin(size_t size)
327 {
328     Bins bin;
329     if (size <= 256)
330     {
331         if (size <= 64)
332         {
333             if (size <= 16)
334                 bin = B_16;
335             else if (size <= 32)
336                 bin = B_32;
337             else
338                 bin = B_64;
339         }
340         else
341         {
342             if (size <= 128)
343                 bin = B_128;
344             else
345                 bin = B_256;
346         }
347     }
348     else
349     {
350         if (size <= 1024)
351         {
352             if (size <= 512)
353                 bin = B_512;
354             else
355                 bin = B_1024;
356         }
357         else
358         {
359             if (size <= 2048)
360                 bin = B_2048;
361             else
362                 bin = B_PAGE;
363         }
364     }
365     return bin;
366 }
367
368
369 /**
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.
374  */
375 size_t reserve(size_t size)
376 {
377     assert(size != 0);
378     size_t npages = (size + PAGESIZE - 1) / PAGESIZE;
379     Pool*  pool = newPool(npages);
380
381     if (!pool)
382         return 0;
383     return pool.npages * PAGESIZE;
384 }
385
386
387 /**
388  * Minimizes physical memory usage by returning free pools to the OS.
389  */
390 void minimize()
391 {
392     size_t n;
393     size_t pn;
394     Pool*  pool;
395
396     for (n = 0; n < gc.pools.length; n++)
397     {
398         pool = gc.pools[n];
399         for (pn = 0; pn < pool.npages; pn++)
400         {
401             if (cast(Bins)pool.pagetable[pn] != B_FREE)
402                 break;
403         }
404         if (pn < pool.npages)
405             continue;
406         pool.Dtor();
407         gc.pools.remove_at(n);
408         n--;
409     }
410     gc.min_addr = gc.pools[0].baseAddr;
411     gc.max_addr = gc.pools[gc.pools.length - 1].topAddr;
412 }
413
414
415 /**
416  * Allocate a chunk of memory that is larger than a page.
417  * Return null if out of memory.
418  */
419 void *bigAlloc(size_t size)
420 {
421     Pool*  pool;
422     size_t npages;
423     size_t n;
424     size_t pn;
425     size_t freedpages;
426     void*  p;
427     int    state;
428
429     npages = (size + PAGESIZE - 1) / PAGESIZE;
430
431     for (state = 0; ; )
432     {
433         // This code could use some refinement when repeatedly
434         // allocating very large arrays.
435
436         for (n = 0; n < gc.pools.length; n++)
437         {
438             pool = gc.pools[n];
439             pn = pool.allocPages(npages);
440             if (pn != OPFAIL)
441                 goto L1;
442         }
443
444         // Failed
445         switch (state)
446         {
447         case 0:
448             if (gc.disabled)
449             {
450                 state = 1;
451                 continue;
452             }
453             // Try collecting
454             freedpages = fullcollectshell();
455             if (freedpages >= gc.pools.length * ((POOLSIZE / PAGESIZE) / 4))
456             {
457                 state = 1;
458                 continue;
459             }
460             // Release empty pools to prevent bloat
461             minimize();
462             // Allocate new pool
463             pool = newPool(npages);
464             if (!pool)
465             {
466                 state = 2;
467                 continue;
468             }
469             pn = pool.allocPages(npages);
470             assert(pn != OPFAIL);
471             goto L1;
472         case 1:
473             // Release empty pools to prevent bloat
474             minimize();
475             // Allocate new pool
476             pool = newPool(npages);
477             if (!pool)
478                 goto Lnomemory;
479             pn = pool.allocPages(npages);
480             assert(pn != OPFAIL);
481             goto L1;
482         case 2:
483             goto Lnomemory;
484         default:
485             assert(false);
486         }
487     }
488
489   L1:
490     pool.pagetable[pn] = B_PAGE;
491     if (npages > 1)
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);
497     return p;
498
499   Lnomemory:
500     return null; // let mallocNoSync handle the error
501 }
502
503
504 /**
505  * Allocate a new pool with at least npages in it.
506  * Sort it into pools.
507  * Return null if failed.
508  */
509 Pool *newPool(size_t npages)
510 {
511     // Minimum of POOLSIZE
512     if (npages < POOLSIZE/PAGESIZE)
513         npages = POOLSIZE/PAGESIZE;
514     else if (npages > POOLSIZE/PAGESIZE)
515     {
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)
519             npages = n;
520     }
521
522     // Allocate successively larger pools up to 8 megs
523     if (gc.pools.length)
524     {
525         size_t n = gc.pools.length;
526         if (n > 8)
527             n = 8;                  // cap pool size at 8 megs
528         n *= (POOLSIZE / PAGESIZE);
529         if (npages < n)
530             npages = n;
531     }
532
533     Pool p;
534     p.initialize(npages);
535     if (!p.baseAddr)
536     {
537         p.Dtor();
538         return null;
539     }
540
541     Pool* pool = gc.pools.insert_sorted(p);
542     if (pool)
543     {
544         gc.min_addr = gc.pools[0].baseAddr;
545         gc.max_addr = gc.pools[gc.pools.length - 1].topAddr;
546     }
547     return pool;
548 }
549
550
551 /**
552  * Allocate a page of bin's.
553  * Returns:
554  *  0       failed
555  */
556 int allocPage(Bins bin)
557 {
558     Pool*  pool;
559     size_t n;
560     size_t pn;
561     byte*  p;
562     byte*  ptop;
563
564     for (n = 0; n < gc.pools.length; n++)
565     {
566         pool = gc.pools[n];
567         pn = pool.allocPages(1);
568         if (pn != OPFAIL)
569             goto L1;
570     }
571     return 0;               // failed
572
573   L1:
574     pool.pagetable[pn] = cast(ubyte)bin;
575
576     // Convert page to free list
577     size_t size = binsize[bin];
578     List **b = &gc.free_list[bin];
579
580     p = pool.baseAddr + pn * PAGESIZE;
581     ptop = p + PAGESIZE;
582     for (; p < ptop; p += size)
583     {
584         (cast(List *)p).next = *b;
585         *b = cast(List *)p;
586     }
587     return 1;
588 }
589
590
591 /**
592  * Marks a range of memory using the conservative bit mask.  Used for
593  * the stack, for the data segment, and additional memory ranges.
594  */
595 void mark_conservative(void* pbot, void* ptop)
596 {
597     mark(pbot, ptop, PointerMap.init.bits.ptr);
598 }
599
600
601 /**
602  * Search a range of memory values and mark any pointers into the GC pool.
603  */
604 void mark(void *pbot, void *ptop, size_t* pm_bitmask)
605 {
606     // TODO: make our own assert because assert uses the GC
607     assert (pbot <= ptop);
608
609     const BITS_PER_WORD = size_t.sizeof * 8;
610
611     void **p1 = cast(void **)pbot;
612     void **p2 = cast(void **)ptop;
613     size_t pcache = 0;
614     uint changes = 0;
615
616     size_t type_size = pm_bitmask[0];
617     size_t* pm_bits = pm_bitmask + 1;
618
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))))
624                 continue;
625
626             void* p = *(p1 + n);
627
628             if (p < gc.min_addr || p >= gc.max_addr)
629                 continue;
630
631             if ((cast(size_t)p & ~(PAGESIZE-1)) == pcache)
632                 continue;
633
634             Pool* pool = findPool(p);
635             if (pool)
636             {
637                 size_t offset = cast(size_t)(p - pool.baseAddr);
638                 size_t bit_i;
639                 size_t pn = offset / PAGESIZE;
640                 Bins   bin = cast(Bins)pool.pagetable[pn];
641
642                 // Adjust bit to be at start of allocated memory block
643                 if (bin <= B_PAGE)
644                     bit_i = (offset & notbinsize[bin]) >> 4;
645                 else if (bin == B_PAGEPLUS)
646                 {
647                     do
648                     {
649                         --pn;
650                     }
651                     while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS);
652                     bit_i = pn * (PAGESIZE / 16);
653                 }
654                 else
655                 {
656                     // Don't mark bits in B_FREE pages
657                     continue;
658                 }
659
660                 if (bin >= B_PAGE) // Cache B_PAGE and B_PAGEPLUS lookups
661                     pcache = cast(size_t)p & ~(PAGESIZE-1);
662
663                 if (!pool.mark.test(bit_i))
664                 {
665                     pool.mark.set(bit_i);
666                     if (!pool.noscan.test(bit_i))
667                     {
668                         pool.scan.set(bit_i);
669                         changes = 1;
670                     }
671                 }
672             }
673         }
674     }
675     if (changes)
676         gc.any_changes = true;
677 }
678
679 /**
680  * Return number of full pages free'd.
681  */
682 size_t fullcollectshell()
683 {
684     gc.stats.collection_started();
685     scope (exit)
686         gc.stats.collection_finished();
687
688     // The purpose of the 'shell' is to ensure all the registers
689     // get put on the stack so they'll be scanned
690     void *sp;
691     size_t result;
692     version (GNU)
693     {
694         gcc.builtins.__builtin_unwind_init();
695         sp = & sp;
696     }
697     else version(LDC)
698     {
699         version(X86)
700         {
701             uint eax,ecx,edx,ebx,ebp,esi,edi;
702             asm
703             {
704                 mov eax[EBP], EAX      ;
705                 mov ecx[EBP], ECX      ;
706                 mov edx[EBP], EDX      ;
707                 mov ebx[EBP], EBX      ;
708                 mov ebp[EBP], EBP      ;
709                 mov esi[EBP], ESI      ;
710                 mov edi[EBP], EDI      ;
711                 mov  sp[EBP], ESP      ;
712             }
713         }
714         else version (X86_64)
715         {
716             ulong rax,rbx,rcx,rdx,rbp,rsi,rdi,r8,r9,r10,r11,r12,r13,r14,r15;
717             asm
718             {
719                 movq rax[RBP], RAX      ;
720                 movq rbx[RBP], RBX      ;
721                 movq rcx[RBP], RCX      ;
722                 movq rdx[RBP], RDX      ;
723                 movq rbp[RBP], RBP      ;
724                 movq rsi[RBP], RSI      ;
725                 movq rdi[RBP], RDI      ;
726                 movq r8 [RBP], R8       ;
727                 movq r9 [RBP], R9       ;
728                 movq r10[RBP], R10      ;
729                 movq r11[RBP], R11      ;
730                 movq r12[RBP], R12      ;
731                 movq r13[RBP], R13      ;
732                 movq r14[RBP], R14      ;
733                 movq r15[RBP], R15      ;
734                 movq  sp[RBP], RSP      ;
735             }
736         }
737         else
738         {
739             static assert( false, "Architecture not supported." );
740         }
741     }
742     else
743     {
744     asm
745     {
746         pushad              ;
747         mov sp[EBP],ESP     ;
748     }
749     }
750     result = fullcollect(sp);
751     version (GNU)
752     {
753         // nothing to do
754     }
755     else version(LDC)
756     {
757         // nothing to do
758     }
759     else
760     {
761     asm
762     {
763         popad               ;
764     }
765     }
766     return result;
767 }
768
769
770 /**
771  *
772  */
773 size_t fullcollect(void *stackTop)
774 {
775     size_t n;
776     Pool*  pool;
777
778     debug(COLLECT_PRINTF) printf("Gcx.fullcollect()\n");
779
780     thread_suspendAll();
781     gc.stats.world_stopped();
782
783     gc.p_cache = null;
784     gc.size_cache = 0;
785
786     gc.any_changes = false;
787     for (n = 0; n < gc.pools.length; n++)
788     {
789         pool = gc.pools[n];
790         pool.mark.zero();
791         pool.scan.zero();
792         pool.freebits.zero();
793     }
794
795     // Mark each free entry, so it doesn't get scanned
796     for (n = 0; n < B_PAGE; n++)
797     {
798         for (List *list = gc.free_list[n]; list; list = list.next)
799         {
800             pool = findPool(list);
801             assert(pool);
802             pool.freebits.set(cast(size_t)(cast(byte*)list - pool.baseAddr) / 16);
803         }
804     }
805
806     for (n = 0; n < gc.pools.length; n++)
807     {
808         pool = gc.pools[n];
809         pool.mark.copy(&pool.freebits);
810     }
811
812     void mark_conservative_dg(void* pbot, void* ptop)
813     {
814         mark_conservative(pbot, ptop);
815     }
816
817     rt_scanStaticData(&mark_conservative_dg);
818
819     if (!gc.no_stack)
820     {
821         // Scan stacks and registers for each paused thread
822         thread_scanAll(&mark_conservative_dg, stackTop);
823     }
824
825     // Scan roots
826     debug(COLLECT_PRINTF) printf("scan roots[]\n");
827     mark_conservative(gc.roots.ptr, gc.roots.ptr + gc.roots.length);
828
829     // Scan ranges
830     debug(COLLECT_PRINTF) printf("scan ranges[]\n");
831     for (n = 0; n < gc.ranges.length; n++)
832     {
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);
835     }
836
837     debug(COLLECT_PRINTF) printf("\tscan heap\n");
838     while (gc.any_changes)
839     {
840         gc.any_changes = false;
841         for (n = 0; n < gc.pools.length; n++)
842         {
843             uint *bbase;
844             uint *b;
845             uint *btop;
846
847             pool = gc.pools[n];
848
849             bbase = pool.scan.base();
850             btop = bbase + pool.scan.nwords;
851             for (b = bbase; b < btop;)
852             {
853                 Bins   bin;
854                 size_t pn;
855                 size_t u;
856                 size_t bitm;
857                 byte*  o;
858
859                 bitm = *b;
860                 if (!bitm)
861                 {
862                     b++;
863                     continue;
864                 }
865                 *b = 0;
866
867                 o = pool.baseAddr + (b - bbase) * 32 * 16;
868                 if (!(bitm & 0xFFFF))
869                 {
870                     bitm >>= 16;
871                     o += 16 * 16;
872                 }
873                 for (; bitm; o += 16, bitm >>= 1)
874                 {
875                     if (!(bitm & 1))
876                         continue;
877
878                     pn = cast(size_t)(o - pool.baseAddr) / PAGESIZE;
879                     bin = cast(Bins)pool.pagetable[pn];
880                     if (bin < B_PAGE) {
881                         if (opts.options.conservative)
882                             mark_conservative(o, o + binsize[bin]);
883                         else {
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);
888                         }
889                     }
890                     else if (bin == B_PAGE || bin == B_PAGEPLUS)
891                     {
892                         if (bin == B_PAGEPLUS)
893                         {
894                             while (pool.pagetable[pn - 1] != B_PAGE)
895                                 pn--;
896                         }
897                         u = 1;
898                         while (pn + u < pool.npages &&
899                                 pool.pagetable[pn + u] == B_PAGEPLUS)
900                             u++;
901
902                         size_t blk_size = u * PAGESIZE;
903                         if (opts.options.conservative)
904                             mark_conservative(o, o + blk_size);
905                         else {
906                             auto end_of_blk = cast(size_t**)(o + blk_size -
907                                     size_t.sizeof);
908                             size_t* pm_bitmask = *end_of_blk;
909                             mark(o, end_of_blk, pm_bitmask);
910                         }
911                     }
912                 }
913             }
914         }
915     }
916
917     thread_resumeAll();
918     gc.stats.world_started();
919
920     // Free up everything not marked
921     debug(COLLECT_PRINTF) printf("\tfree'ing\n");
922     size_t freedpages = 0;
923     size_t freed = 0;
924     for (n = 0; n < gc.pools.length; n++)
925     {
926         pool = gc.pools[n];
927         uint*  bbase = pool.mark.base();
928         size_t pn;
929         for (pn = 0; pn < pool.npages; pn++, bbase += PAGESIZE / (32 * 16))
930         {
931             Bins bin = cast(Bins)pool.pagetable[pn];
932
933             if (bin < B_PAGE)
934             {
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;
940
941 version(none) // BUG: doesn't work because freebits() must also be cleared
942 {
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)
947                 {
948                     for (; p < ptop; p += size, bit_i += bit_stride)
949                     {
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*/);
953                             else
954                                 rt_finalize(cast(List *)p, false/*gc.no_stack > 0*/);
955                         }
956                         clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
957
958                         List *list = cast(List *)p;
959
960                         if (opts.options.mem_stomp)
961                             memset(p, 0xF3, size);
962                     }
963                     pool.pagetable[pn] = B_FREE;
964                     freed += PAGESIZE;
965                     continue;
966                 }
967 }
968                 for (; p < ptop; p += size, bit_i += bit_stride)
969                 {
970                     if (!pool.mark.test(bit_i))
971                     {
972                         if (opts.options.sentinel)
973                             sentinel_Invariant(sentinel_add(p));
974
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*/);
979                             else
980                                 rt_finalize(cast(List *)p, false/*gc.no_stack > 0*/);
981                         }
982                         clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
983
984                         List *list = cast(List *)p;
985
986                         if (opts.options.mem_stomp)
987                             memset(p, 0xF3, size);
988
989                         freed += size;
990                     }
991                 }
992             }
993             else if (bin == B_PAGE)
994             {
995                 size_t bit_i = pn * (PAGESIZE / 16);
996                 if (!pool.mark.test(bit_i))
997                 {
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*/);
1004                         else
1005                             rt_finalize(p, false/*gc.no_stack > 0*/);
1006                     }
1007                     clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
1008
1009                     debug(COLLECT_PRINTF) printf("\tcollecting big %x\n", p);
1010                     pool.pagetable[pn] = B_FREE;
1011                     freedpages++;
1012                     if (opts.options.mem_stomp)
1013                         memset(p, 0xF3, PAGESIZE);
1014                     while (pn + 1 < pool.npages && pool.pagetable[pn + 1] == B_PAGEPLUS)
1015                     {
1016                         pn++;
1017                         pool.pagetable[pn] = B_FREE;
1018                         freedpages++;
1019
1020                         if (opts.options.mem_stomp)
1021                         {
1022                             p += PAGESIZE;
1023                             memset(p, 0xF3, PAGESIZE);
1024                         }
1025                     }
1026                 }
1027             }
1028         }
1029     }
1030
1031     // Zero buckets
1032     gc.free_list[] = null;
1033
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++)
1038     {
1039         pool = gc.pools[n];
1040         for (size_t pn = 0; pn < pool.npages; pn++)
1041         {
1042             Bins   bin = cast(Bins)pool.pagetable[pn];
1043             size_t bit_i;
1044             size_t u;
1045
1046             if (bin < B_PAGE)
1047             {
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);
1052                 byte*  p;
1053
1054                 bit_i = bit_base;
1055                 for (; bit_i < bit_top; bit_i += bit_stride)
1056                 {
1057                     if (!pool.freebits.test(bit_i))
1058                         goto Lnotfree;
1059                 }
1060                 pool.pagetable[pn] = B_FREE;
1061                 recoveredpages++;
1062                 continue;
1063
1064              Lnotfree:
1065                 p = pool.baseAddr + pn * PAGESIZE;
1066                 for (u = 0; u < PAGESIZE; u += size)
1067                 {
1068                     bit_i = bit_base + u / 16;
1069                     if (pool.freebits.test(bit_i))
1070                     {
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;
1076                     }
1077                 }
1078             }
1079         }
1080     }
1081
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);
1084
1085     return freedpages + recoveredpages;
1086 }
1087
1088
1089 /**
1090  *
1091  */
1092 uint getAttr(Pool* pool, size_t bit_i)
1093 in
1094 {
1095     assert( pool );
1096 }
1097 body
1098 {
1099     uint attrs;
1100
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;
1109     return attrs;
1110 }
1111
1112
1113 /**
1114  *
1115  */
1116 void setAttr(Pool* pool, size_t bit_i, uint mask)
1117 in
1118 {
1119     assert( pool );
1120 }
1121 body
1122 {
1123     if (mask & BlkAttr.FINALIZE)
1124     {
1125         if (!pool.finals.nbits)
1126             pool.finals.alloc(pool.mark.nbits);
1127         pool.finals.set(bit_i);
1128     }
1129     if (mask & BlkAttr.NO_SCAN)
1130     {
1131         pool.noscan.set(bit_i);
1132     }
1133 //        if (mask & BlkAttr.NO_MOVE)
1134 //        {
1135 //            if (!pool.nomove.nbits)
1136 //                pool.nomove.alloc(pool.mark.nbits);
1137 //            pool.nomove.set(bit_i);
1138 //        }
1139 }
1140
1141
1142 /**
1143  *
1144  */
1145 void clrAttr(Pool* pool, size_t bit_i, uint mask)
1146 in
1147 {
1148     assert( pool );
1149 }
1150 body
1151 {
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);
1158 }
1159
1160
1161
1162 void initialize()
1163 {
1164     int dummy;
1165     gc.stack_bottom = cast(char*)&dummy;
1166     opts.parse(cstdlib.getenv("D_GC_OPTS"));
1167     gc.lock = GCLock.classinfo;
1168     gc.inited = 1;
1169     setStackBottom(rt_stackBottom());
1170     gc.stats = Stats(gc);
1171 }
1172
1173
1174 //
1175 //
1176 //
1177 private void *malloc(size_t size, uint attrs, size_t* pm_bitmask)
1178 {
1179     assert(size != 0);
1180
1181     gc.stats.malloc_started(size, attrs, pm_bitmask);
1182     scope (exit)
1183         gc.stats.malloc_finished(p);
1184
1185     void *p = null;
1186     Bins bin;
1187
1188     if (opts.options.sentinel)
1189         size += SENTINEL_EXTRA;
1190
1191     bool has_pm = has_pointermap(attrs);
1192     if (has_pm)
1193         size += size_t.sizeof;
1194
1195     // Compute size bin
1196     // Cache previous binsize lookup - Dave Fladebo.
1197     static size_t lastsize = -1;
1198     static Bins lastbin;
1199     if (size == lastsize)
1200         bin = lastbin;
1201     else
1202     {
1203         bin = findBin(size);
1204         lastsize = size;
1205         lastbin = bin;
1206     }
1207
1208     size_t capacity; // to figure out where to store the bitmask
1209     if (bin < B_PAGE)
1210     {
1211         p = gc.free_list[bin];
1212         if (p is null)
1213         {
1214             if (!allocPage(bin) && !gc.disabled)   // try to find a new page
1215             {
1216                 if (!thread_needLock())
1217                 {
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.
1221                      */
1222                     synchronized (gc.lock)
1223                     {
1224                         fullcollectshell();
1225                     }
1226                 }
1227                 else if (!fullcollectshell())       // collect to find a new page
1228                 {
1229                     //newPool(1);
1230                 }
1231             }
1232             if (!gc.free_list[bin] && !allocPage(bin))
1233             {
1234                 newPool(1);         // allocate new pool to find a new page
1235                 int result = allocPage(bin);
1236                 if (!result)
1237                     onOutOfMemoryError();
1238             }
1239             p = gc.free_list[bin];
1240         }
1241         capacity = binsize[bin];
1242
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);
1249     }
1250     else
1251     {
1252         p = bigAlloc(size);
1253         if (!p)
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;
1258     }
1259
1260     // Store the bit mask AFTER SENTINEL_POST
1261     // TODO: store it BEFORE, so the bitmask is protected too
1262     if (has_pm) {
1263         auto end_of_blk = cast(size_t**)(p + capacity - size_t.sizeof);
1264         *end_of_blk = pm_bitmask;
1265         size -= size_t.sizeof;
1266     }
1267
1268     if (opts.options.sentinel) {
1269         size -= SENTINEL_EXTRA;
1270         p = sentinel_add(p);
1271         sentinel_init(p, size);
1272     }
1273
1274     if (attrs)
1275     {
1276         Pool *pool = findPool(p);
1277         assert(pool);
1278
1279         setAttr(pool, cast(size_t)(p - pool.baseAddr) / 16, attrs);
1280     }
1281     return p;
1282 }
1283
1284
1285 //
1286 //
1287 //
1288 private void *calloc(size_t size, uint attrs, size_t* pm_bitmask)
1289 {
1290     assert(size != 0);
1291
1292     void *p = malloc(size, attrs, pm_bitmask);
1293     memset(p, 0, size);
1294     return p;
1295 }
1296
1297
1298 //
1299 //
1300 //
1301 private void *realloc(void *p, size_t size, uint attrs,
1302         size_t* pm_bitmask)
1303 {
1304     if (!size)
1305     {
1306         if (p)
1307         {
1308             free(p);
1309             p = null;
1310         }
1311     }
1312     else if (!p)
1313     {
1314         p = malloc(size, attrs, pm_bitmask);
1315     }
1316     else
1317     {
1318         Pool* pool = findPool(p);
1319         if (pool is null)
1320             return null;
1321
1322         // Set or retrieve attributes as appropriate
1323         auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
1324         if (attrs) {
1325             clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
1326             setAttr(pool, bit_i, attrs);
1327         }
1328         else
1329             attrs = getAttr(pool, bit_i);
1330
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;
1335         if (has_pm) {
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;
1342             }
1343         }
1344
1345         if (opts.options.sentinel)
1346         {
1347             sentinel_Invariant(p);
1348             size_t sentinel_stored_size = *sentinel_size(p);
1349             if (sentinel_stored_size != size)
1350             {
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);
1355                 p = p2;
1356             }
1357         }
1358         else
1359         {
1360             size += pm_bitmask_size;
1361             if (blk_size >= PAGESIZE && size >= PAGESIZE)
1362             {
1363                 auto psz = blk_size / PAGESIZE;
1364                 auto newsz = (size + PAGESIZE - 1) / PAGESIZE;
1365                 if (newsz == psz)
1366                     return p;
1367
1368                 auto pagenum = (p - pool.baseAddr) / PAGESIZE;
1369
1370                 if (newsz < psz)
1371                 {
1372                     // Shrink in place
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);
1377                     if (has_pm) {
1378                         auto end_of_blk = cast(size_t**)(
1379                                 blk_base_addr + (PAGESIZE * newsz) -
1380                                 pm_bitmask_size);
1381                         *end_of_blk = pm_bitmask;
1382                     }
1383                     return p;
1384                 }
1385                 else if (pagenum + newsz <= pool.npages)
1386                 {
1387                     // Attempt to expand in place
1388                     for (size_t i = pagenum + psz; 1;)
1389                     {
1390                         if (i == pagenum + newsz)
1391                         {
1392                             if (opts.options.mem_stomp)
1393                                 memset(p + blk_size - pm_bitmask_size,
1394                                         0xF0, size - blk_size
1395                                         - pm_bitmask_size);
1396                             memset(pool.pagetable + pagenum +
1397                                     psz, B_PAGEPLUS, newsz - psz);
1398                             if (has_pm) {
1399                                 auto end_of_blk = cast(size_t**)(
1400                                         blk_base_addr +
1401                                         (PAGESIZE * newsz) -
1402                                         pm_bitmask_size);
1403                                 *end_of_blk = pm_bitmask;
1404                             }
1405                             return p;
1406                         }
1407                         if (i == pool.npages)
1408                         {
1409                             break;
1410                         }
1411                         if (pool.pagetable[i] != B_FREE)
1412                             break;
1413                         i++;
1414                     }
1415                 }
1416             }
1417             // if new size is bigger or less than half
1418             if (blk_size < size || blk_size > size * 2)
1419             {
1420                 size -= pm_bitmask_size;
1421                 blk_size -= pm_bitmask_size;
1422                 void* p2 = malloc(size, attrs, pm_bitmask);
1423                 if (blk_size < size)
1424                     size = blk_size;
1425                 cstring.memcpy(p2, p, size);
1426                 p = p2;
1427             }
1428         }
1429     }
1430     return p;
1431 }
1432
1433
1434 /**
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).
1438  *
1439  * Returns:
1440  *  0 if could not extend p,
1441  *  total size of entire memory block if successful.
1442  */
1443 private size_t extend(void* p, size_t minsize, size_t maxsize)
1444 in
1445 {
1446     assert( minsize <= maxsize );
1447 }
1448 body
1449 {
1450     if (opts.options.sentinel)
1451         return 0;
1452
1453     Pool* pool = findPool(p);
1454     if (pool is null)
1455         return 0;
1456
1457     // Retrieve attributes
1458     auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
1459     uint attrs = getAttr(pool, bit_i);
1460
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;
1466     if (has_pm) {
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;
1472
1473         minsize += size_t.sizeof;
1474         maxsize += size_t.sizeof;
1475     }
1476
1477     if (blk_size < PAGESIZE)
1478         return 0; // cannot extend buckets
1479
1480     auto psz = blk_size / PAGESIZE;
1481     auto minsz = (minsize + PAGESIZE - 1) / PAGESIZE;
1482     auto maxsz = (maxsize + PAGESIZE - 1) / PAGESIZE;
1483
1484     auto pagenum = (p - pool.baseAddr) / PAGESIZE;
1485
1486     size_t sz;
1487     for (sz = 0; sz < maxsz; sz++)
1488     {
1489         auto i = pagenum + psz + sz;
1490         if (i == pool.npages)
1491             break;
1492         if (pool.pagetable[i] != B_FREE)
1493         {
1494             if (sz < minsz)
1495                 return 0;
1496             break;
1497         }
1498     }
1499     if (sz < minsz)
1500         return 0;
1501
1502     size_t new_size = (psz + sz) * PAGESIZE;
1503
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);
1508     gc.p_cache = null;
1509     gc.size_cache = 0;
1510
1511     if (has_pm) {
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;
1515     }
1516     return new_size;
1517 }
1518
1519
1520 //
1521 //
1522 //
1523 private void free(void *p)
1524 {
1525     assert (p);
1526
1527     Pool*  pool;
1528     size_t pagenum;
1529     Bins   bin;
1530     size_t bit_i;
1531
1532     // Find which page it is in
1533     pool = findPool(p);
1534     if (!pool)                              // if not one of ours
1535         return;                             // ignore
1536     if (opts.options.sentinel) {
1537         sentinel_Invariant(p);
1538         p = sentinel_sub(p);
1539     }
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);
1543
1544     bin = cast(Bins)pool.pagetable[pagenum];
1545     if (bin == B_PAGE)              // if large alloc
1546     {
1547         // Free pages
1548         size_t npages = 1;
1549         size_t n = pagenum;
1550         while (++n < pool.npages && pool.pagetable[n] == B_PAGEPLUS)
1551             npages++;
1552         if (opts.options.mem_stomp)
1553             memset(p, 0xF2, npages * PAGESIZE);
1554         pool.freePages(pagenum, npages);
1555     }
1556     else
1557     {
1558         // Add to free list
1559         List *list = cast(List*)p;
1560
1561         if (opts.options.mem_stomp)
1562             memset(p, 0xF2, binsize[bin]);
1563
1564         list.next = gc.free_list[bin];
1565         gc.free_list[bin] = list;
1566     }
1567 }
1568
1569
1570 /**
1571  * Determine the allocated size of pointer p.  If p is an interior pointer
1572  * or not a gc allocated pointer, return 0.
1573  */
1574 private size_t sizeOf(void *p)
1575 {
1576     assert (p);
1577
1578     if (opts.options.sentinel)
1579         p = sentinel_sub(p);
1580
1581     Pool* pool = findPool(p);
1582     if (pool is null)
1583         return 0;
1584
1585     auto biti = cast(size_t)(p - pool.baseAddr) / 16;
1586     uint attrs = getAttr(pool, biti);
1587
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;
1592
1593     if (opts.options.sentinel) {
1594         // Check for interior pointer
1595         // This depends on:
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))
1599             return 0;
1600         return size - SENTINEL_EXTRA - pm_bitmask_size;
1601     }
1602     else {
1603         if (p == gc.p_cache)
1604             return gc.size_cache;
1605
1606         // Check for interior pointer
1607         // This depends on:
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))
1611             return 0;
1612
1613         gc.p_cache = p;
1614         gc.size_cache = size - pm_bitmask_size;
1615
1616         return gc.size_cache;
1617     }
1618 }
1619
1620
1621 /**
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
1626  */
1627 private void checkNoSync(void *p)
1628 {
1629     assert(p);
1630
1631     if (opts.options.sentinel)
1632         sentinel_Invariant(p);
1633     debug (PTRCHECK)
1634     {
1635         Pool*  pool;
1636         size_t pagenum;
1637         Bins   bin;
1638         size_t size;
1639
1640         if (opts.options.sentinel)
1641             p = sentinel_sub(p);
1642         pool = findPool(p);
1643         assert(pool);
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);
1649
1650         debug (PTRCHECK2)
1651         {
1652             if (bin < B_PAGE)
1653             {
1654                 // Check that p is not on a free list
1655                 List *list;
1656
1657                 for (list = gc.free_list[bin]; list; list = list.next)
1658                 {
1659                     assert(cast(void*)list != p);
1660                 }
1661             }
1662         }
1663     }
1664 }
1665
1666
1667 //
1668 //
1669 //
1670 private void setStackBottom(void *p)
1671 {
1672     version (STACKGROWSDOWN)
1673     {
1674         //p = (void *)((uint *)p + 4);
1675         if (p > gc.stack_bottom)
1676         {
1677             gc.stack_bottom = p;
1678         }
1679     }
1680     else
1681     {
1682         //p = (void *)((uint *)p - 4);
1683         if (p < gc.stack_bottom)
1684         {
1685             gc.stack_bottom = cast(char*)p;
1686         }
1687     }
1688 }
1689
1690
1691 /**
1692  * Retrieve statistics about garbage collection.
1693  * Useful for debugging and tuning.
1694  */
1695 private GCStats getStats()
1696 {
1697     GCStats stats;
1698     size_t psize = 0;
1699     size_t usize = 0;
1700     size_t flsize = 0;
1701
1702     size_t n;
1703     size_t bsize = 0;
1704
1705     for (n = 0; n < gc.pools.length; n++)
1706     {
1707         Pool* pool = gc.pools[n];
1708         psize += pool.npages * PAGESIZE;
1709         for (size_t j = 0; j < pool.npages; j++)
1710         {
1711             Bins bin = cast(Bins)pool.pagetable[j];
1712             if (bin == B_FREE)
1713                 stats.freeblocks++;
1714             else if (bin == B_PAGE)
1715                 stats.pageblocks++;
1716             else if (bin < B_PAGE)
1717                 bsize += PAGESIZE;
1718         }
1719     }
1720
1721     for (n = 0; n < B_PAGE; n++)
1722     {
1723         for (List *list = gc.free_list[n]; list; list = list.next)
1724             flsize += binsize[n];
1725     }
1726
1727     usize = bsize - flsize;
1728
1729     stats.poolsize = psize;
1730     stats.usedsize = bsize - flsize;
1731     stats.freelistsize = flsize;
1732     return stats;
1733 }
1734
1735 /******************* weak-reference support *********************/
1736
1737 private struct WeakPointer
1738 {
1739     Object reference;
1740
1741     void ondestroy(Object r)
1742     {
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, () {
1748             reference = null;
1749         })();
1750     }
1751 }
1752
1753 /**
1754  * Create a weak pointer to the given object.
1755  * Returns a pointer to an opaque struct allocated in C memory.
1756  */
1757 void* weakpointerCreate( Object r )
1758 {
1759     if (r)
1760     {
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
1764         //    for references
1765         auto wp = cast(WeakPointer*)(cstdlib.malloc(WeakPointer.sizeof));
1766         if (!wp)
1767             onOutOfMemoryError();
1768         wp.reference = r;
1769         rt_attachDisposeEvent(r, &wp.ondestroy);
1770         return wp;
1771     }
1772     return null;
1773 }
1774
1775 /**
1776  * Destroy a weak pointer returned by weakpointerCreate().
1777  * If null is passed, nothing happens.
1778  */
1779 void weakpointerDestroy( void* p )
1780 {
1781     if (p)
1782     {
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, () {
1787             if (wp.reference)
1788                 rt_detachDisposeEvent(wp.reference, &wp.ondestroy);
1789         })();
1790         cstdlib.free(wp);
1791     }
1792 }
1793
1794 /**
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.
1798  */
1799 Object weakpointerGet( void* p )
1800 {
1801     if (p)
1802     {
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;
1809         })();
1810         }
1811 }
1812
1813
1814 /* ============================ Pool  =============================== */
1815
1816
1817 struct Pool
1818 {
1819     byte* baseAddr;
1820     byte* topAddr;
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
1826
1827     size_t npages;
1828     ubyte* pagetable;
1829
1830
1831     void initialize(size_t npages)
1832     {
1833         size_t poolsize = npages * PAGESIZE;
1834         assert(poolsize >= POOLSIZE);
1835         baseAddr = cast(byte *) alloc.os_mem_map(poolsize);
1836
1837         // Some of the code depends on page alignment of memory pools
1838         assert((cast(size_t)baseAddr & (PAGESIZE - 1)) == 0);
1839
1840         if (!baseAddr)
1841         {
1842             npages = 0;
1843             poolsize = 0;
1844         }
1845         //assert(baseAddr);
1846         topAddr = baseAddr + poolsize;
1847
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);
1852
1853         pagetable = cast(ubyte*) cstdlib.malloc(npages);
1854         if (!pagetable)
1855             onOutOfMemoryError();
1856         memset(pagetable, B_FREE, npages);
1857
1858         this.npages = npages;
1859     }
1860
1861
1862     void Dtor()
1863     {
1864         if (baseAddr)
1865         {
1866             int result;
1867
1868             if (npages)
1869             {
1870                 result = alloc.os_mem_unmap(baseAddr, npages * PAGESIZE);
1871                 assert(result);
1872                 npages = 0;
1873             }
1874
1875             baseAddr = null;
1876             topAddr = null;
1877         }
1878         // See Gcx.Dtor() for the rationale of the null check.
1879         if (pagetable)
1880             cstdlib.free(pagetable);
1881
1882         mark.Dtor();
1883         scan.Dtor();
1884         freebits.Dtor();
1885         finals.Dtor();
1886         noscan.Dtor();
1887     }
1888
1889
1890     bool Invariant()
1891     {
1892         return true;
1893     }
1894
1895
1896     invariant
1897     {
1898         //mark.Invariant();
1899         //scan.Invariant();
1900         //freebits.Invariant();
1901         //finals.Invariant();
1902         //noscan.Invariant();
1903
1904         if (baseAddr)
1905         {
1906             //if (baseAddr + npages * PAGESIZE != topAddr)
1907                 //printf("baseAddr = %p, npages = %d, topAddr = %p\n", baseAddr, npages, topAddr);
1908             assert(baseAddr + npages * PAGESIZE == topAddr);
1909         }
1910
1911         for (size_t i = 0; i < npages; i++)
1912         {
1913             Bins bin = cast(Bins)pagetable[i];
1914             assert(bin < B_MAX);
1915         }
1916     }
1917
1918
1919     /**
1920      * Allocate n pages from Pool.
1921      * Returns OPFAIL on failure.
1922      */
1923     size_t allocPages(size_t n)
1924     {
1925         size_t i;
1926         size_t n2;
1927
1928         n2 = n;
1929         for (i = 0; i < npages; i++)
1930         {
1931             if (pagetable[i] == B_FREE)
1932             {
1933                 if (--n2 == 0)
1934                     return i - n + 1;
1935             }
1936             else
1937                 n2 = n;
1938         }
1939         return OPFAIL;
1940     }
1941
1942
1943     /**
1944      * Free npages pages starting with pagenum.
1945      */
1946     void freePages(size_t pagenum, size_t npages)
1947     {
1948         memset(&pagetable[pagenum], B_FREE, npages);
1949     }
1950
1951
1952     /**
1953      * Find base address of block containing pointer p.
1954      * Returns null if the pointer doesn't belong to this pool
1955      */
1956     void* findBase(void *p)
1957     {
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
1962         if (bin <= B_PAGE)
1963             return this.baseAddr + (offset & notbinsize[bin]);
1964         if (bin == B_PAGEPLUS) {
1965             do {
1966                 --pagenum, offset -= PAGESIZE;
1967             } while (cast(Bins)this.pagetable[pagenum] == B_PAGEPLUS);
1968             return this.baseAddr + (offset & (offset.max ^ (PAGESIZE-1)));
1969         }
1970         // we are in a B_FREE page
1971         return null;
1972     }
1973
1974
1975     /**
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
1978      * than a PAGE.
1979      */
1980     size_t findSize(void *p)
1981     {
1982         size_t pagenum = cast(size_t)(p - this.baseAddr) / PAGESIZE;
1983         Bins bin = cast(Bins)this.pagetable[pagenum];
1984         if (bin != B_PAGE)
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;
1990     }
1991
1992
1993     /**
1994      * Used for sorting pools
1995      */
1996     int opCmp(in Pool other)
1997     {
1998         if (baseAddr < other.baseAddr)
1999             return -1;
2000         else
2001         return cast(int)(baseAddr > other.baseAddr);
2002     }
2003 }
2004
2005
2006 /* ============================ SENTINEL =============================== */
2007
2008
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;
2012
2013
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)]; }
2017
2018
2019 void sentinel_init(void *p, size_t size)
2020 {
2021     *sentinel_size(p) = size;
2022     *sentinel_pre(p) = SENTINEL_PRE;
2023     *sentinel_post(p) = SENTINEL_POST;
2024 }
2025
2026
2027 void sentinel_Invariant(void *p)
2028 {
2029     assert(*sentinel_pre(p) == SENTINEL_PRE);
2030     assert(*sentinel_post(p) == SENTINEL_POST);
2031 }
2032
2033
2034 void *sentinel_add(void *p)
2035 {
2036     return p + 2 * size_t.sizeof;
2037 }
2038
2039
2040 void *sentinel_sub(void *p)
2041 {
2042     return p - 2 * size_t.sizeof;
2043 }
2044
2045
2046
2047 /* ============================ C Public Interface ======================== */
2048
2049
2050 private int _termCleanupLevel=1;
2051
2052 extern (C):
2053
2054 /// sets the cleanup level done by gc
2055 /// 0: none
2056 /// 1: fullCollect
2057 /// 2: fullCollect ignoring stack roots (might crash daemonThreads)
2058 /// result !=0 if the value was invalid
2059 int gc_setTermCleanupLevel(int cLevel)
2060 {
2061     if (cLevel<0 || cLevel>2) return cLevel;
2062     _termCleanupLevel=cLevel;
2063     return 0;
2064 }
2065
2066 /// returns the cleanup level done by gc
2067 int gc_getTermCleanupLevel()
2068 {
2069     return _termCleanupLevel;
2070 }
2071
2072 void gc_init()
2073 {
2074     scope (exit) assert (Invariant());
2075     gc = cast(GC*) cstdlib.calloc(1, GC.sizeof);
2076     *gc = GC.init;
2077     initialize();
2078     version (DigitalMars) version(OSX) {
2079         _d_osx_image_init();
2080     }
2081     // NOTE: The GC must initialize the thread library
2082     //       before its first collection.
2083     thread_init();
2084 }
2085
2086 void gc_term()
2087 {
2088     assert (Invariant());
2089     if (_termCleanupLevel<1) {
2090         // no cleanup
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
2101         //       more.
2102         //
2103         // not really a 'collect all' -- still scans static data area, roots,
2104         // and ranges.
2105         return locked!(void, () {
2106             gc.no_stack++;
2107             fullcollectshell();
2108             gc.no_stack--;
2109         })();
2110     } else {
2111         // default (safe) clenup
2112         return locked!(void, () {
2113             fullcollectshell();
2114         })();
2115     }
2116 }
2117
2118 void gc_enable()
2119 {
2120     return locked!(void, () {
2121         assert (Invariant()); scope (exit) assert (Invariant());
2122         assert (gc.disabled > 0);
2123         gc.disabled--;
2124     })();
2125 }
2126
2127 void gc_disable()
2128 {
2129     return locked!(void, () {
2130         assert (Invariant()); scope (exit) assert (Invariant());
2131         gc.disabled++;
2132     })();
2133 }
2134
2135 void gc_collect()
2136 {
2137     return locked!(void, () {
2138         assert (Invariant()); scope (exit) assert (Invariant());
2139         fullcollectshell();
2140     })();
2141 }
2142
2143
2144 void gc_minimize()
2145 {
2146     return locked!(void, () {
2147         assert (Invariant()); scope (exit) assert (Invariant());
2148         minimize();
2149     })();
2150 }
2151
2152 uint gc_getAttr(void* p)
2153 {
2154     if (p is null)
2155         return 0;
2156     return locked!(uint, () {
2157         assert (Invariant()); scope (exit) assert (Invariant());
2158         Pool* pool = findPool(p);
2159         if (pool is null)
2160             return 0u;
2161         auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
2162         return getAttr(pool, bit_i);
2163     })();
2164 }
2165
2166 uint gc_setAttr(void* p, uint attrs)
2167 {
2168     if (p is null)
2169         return 0;
2170     return locked!(uint, () {
2171         assert (Invariant()); scope (exit) assert (Invariant());
2172         Pool* pool = findPool(p);
2173         if (pool is null)
2174             return 0u;
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);
2178         return old_attrs;
2179     })();
2180 }
2181
2182 uint gc_clrAttr(void* p, uint attrs)
2183 {
2184     if (p is null)
2185         return 0;
2186     return locked!(uint, () {
2187         assert (Invariant()); scope (exit) assert (Invariant());
2188         Pool* pool = findPool(p);
2189         if (pool is null)
2190             return 0u;
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);
2194         return old_attrs;
2195     })();
2196 }
2197
2198 void* gc_malloc(size_t size, uint attrs = 0,
2199         PointerMap ptrmap = PointerMap.init)
2200 {
2201     if (size == 0)
2202         return null;
2203     return locked!(void*, () {
2204         assert (Invariant()); scope (exit) assert (Invariant());
2205         return malloc(size, attrs, ptrmap.bits.ptr);
2206     })();
2207 }
2208
2209 void* gc_calloc(size_t size, uint attrs = 0,
2210         PointerMap ptrmap = PointerMap.init)
2211 {
2212     if (size == 0)
2213         return null;
2214     return locked!(void*, () {
2215         assert (Invariant()); scope (exit) assert (Invariant());
2216         return calloc(size, attrs, ptrmap.bits.ptr);
2217     })();
2218 }
2219
2220 void* gc_realloc(void* p, size_t size, uint attrs = 0,
2221         PointerMap ptrmap = PointerMap.init)
2222 {
2223     return locked!(void*, () {
2224         assert (Invariant()); scope (exit) assert (Invariant());
2225         return realloc(p, size, attrs, ptrmap.bits.ptr);
2226     })();
2227 }
2228
2229 size_t gc_extend(void* p, size_t min_size, size_t max_size)
2230 {
2231     return locked!(size_t, () {
2232         assert (Invariant()); scope (exit) assert (Invariant());
2233         return extend(p, min_size, max_size);
2234     })();
2235 }
2236
2237 size_t gc_reserve(size_t size)
2238 {
2239     if (size == 0)
2240         return 0;
2241     return locked!(size_t, () {
2242         assert (Invariant()); scope (exit) assert (Invariant());
2243         return reserve(size);
2244     })();
2245 }
2246
2247 void gc_free(void* p)
2248 {
2249     if (p is null)
2250         return;
2251     return locked!(void, () {
2252         assert (Invariant()); scope (exit) assert (Invariant());
2253         free(p);
2254     })();
2255 }
2256
2257 void* gc_addrOf(void* p)
2258 {
2259     if (p is null)
2260         return null;
2261     return locked!(void*, () {
2262         assert (Invariant()); scope (exit) assert (Invariant());
2263         Pool* pool = findPool(p);
2264         if (pool is null)
2265             return null;
2266         return pool.findBase(p);
2267     })();
2268 }
2269
2270 size_t gc_sizeOf(void* p)
2271 {
2272     if (p is null)
2273         return 0;
2274     return locked!(size_t, () {
2275         assert (Invariant()); scope (exit) assert (Invariant());
2276         return sizeOf(p);
2277     })();
2278 }
2279
2280 BlkInfo gc_query(void* p)
2281 {
2282     if (p is null)
2283         return BlkInfo.init;
2284     return locked!(BlkInfo, () {
2285         assert (Invariant()); scope (exit) assert (Invariant());
2286         return getInfo(p);
2287     })();
2288 }
2289
2290 // NOTE: This routine is experimental.  The stats or function name may change
2291 //       before it is made officially available.
2292 GCStats gc_stats()
2293 {
2294     return locked!(GCStats, () {
2295         assert (Invariant()); scope (exit) assert (Invariant());
2296         return getStats();
2297     })();
2298 }
2299
2300 void gc_addRoot(void* p)
2301 {
2302     if (p is null)
2303         return;
2304     return locked!(void, () {
2305         assert (Invariant()); scope (exit) assert (Invariant());
2306         if (gc.roots.append(p) is null)
2307             onOutOfMemoryError();
2308     })();
2309 }
2310
2311 void gc_addRange(void* p, size_t size)
2312 {
2313     if (p is null || size == 0)
2314         return;
2315     return locked!(void, () {
2316         assert (Invariant()); scope (exit) assert (Invariant());
2317         if (gc.ranges.append(Range(p, p + size)) is null)
2318             onOutOfMemoryError();
2319     })();
2320 }
2321
2322 void gc_removeRoot(void* p)
2323 {
2324     if (p is null)
2325         return;
2326     return locked!(void, () {
2327         assert (Invariant()); scope (exit) assert (Invariant());
2328         bool r = gc.roots.remove(p);
2329         assert (r);
2330     })();
2331 }
2332
2333 void gc_removeRange(void* p)
2334 {
2335     if (p is null)
2336         return;
2337     return locked!(void, () {
2338         assert (Invariant()); scope (exit) assert (Invariant());
2339         bool r = gc.ranges.remove(Range(p, null));
2340         assert (r);
2341     })();
2342 }
2343
2344 void* gc_weakpointerCreate(Object r)
2345 {
2346     // weakpointers do their own locking
2347     return weakpointerCreate(r);
2348 }
2349
2350 void gc_weakpointerDestroy(void* wp)
2351 {
2352     // weakpointers do their own locking
2353     weakpointerDestroy(wp);
2354 }
2355
2356 Object gc_weakpointerGet(void* wp)
2357 {
2358     // weakpointers do their own locking
2359     return weakpointerGet(wp);
2360 }
2361
2362
2363 // vim: set et sw=4 sts=4 :