gc.d

   1 /**
   2  * This module contains a minimal garbage collector implementation according to
   3  * Tango requirements.  This library is mostly intended to serve as an example,
   4  * but it is usable in applications which do not rely on a garbage collector
   5  * to clean up memory (ie. when dynamic array resizing is not used, and all
   6  * memory allocated with 'new' is freed deterministically with 'delete').
   7  *
   8  * Please note that block attribute data must be tracked, or at a minimum, the
   9  * FINALIZE bit must be tracked for any allocated memory block because calling
  10  * rt_finalize on a non-object block can result in an access violation.  In the
  11  * allocator below, this tracking is done via a leading uint bitmask.  A real
  12  * allocator may do better to store this data separately, similar to the basic
  13  * GC normally used by Tango.
  14  *
  15  * Copyright: Public Domain
  16  * License:   BOLA
  17  * Authors:   Leandro Lucarella
  18  */
  19
  20 module gc;
  21
  22 private {
  23
  24     import cell: Cell, BlkAttr;
  25     import list: List;
  26     import dynarray: DynArray;
  27     import arch: stack_smaller, push_registers, pop_registers;
  28     import alloc: mem_alloc, mem_free;
  29
  30     import stdc = tango.stdc.stdlib;
  31     import tango.stdc.string: memset, memcpy;
  32     debug import tango.stdc.stdio: printf;
  33
  34     alias void delegate(void*, void*) mark_function;
  35     extern (C) void onOutOfMemoryError();
  36     extern (C) void rt_finalize(void* p, bool det=true);
  37     extern (C) void rt_scanStaticData(mark_function mark);
  38     extern (C) void thread_init();
  39     extern (C) bool thread_needLock();
  40     extern (C) void thread_suspendAll();
  41     extern (C) void thread_resumeAll();
  42     extern (C) void thread_scanAll(mark_function mark, void* stack_top=null);
  43
  44     struct RootRange
  45     {
  46
  47         void* from;
  48
  49         void* to;
  50
  51         int opApply(int delegate(ref void*) dg)
  52         {
  53             int result = 0;
  54             auto from = cast(void**) this.from;
  55             auto to = cast(void**) this.to;
  56             // TODO: alignment. The range should be aligned and the size
  57             //       should be a multiple of the word size. If the later does
  58             //       not hold, the last bytes that are not enough to build
  59             //       a complete word should be ignored. Right now we are
  60             //       doing invalid reads in that cases.
  61             for (void** current = from; current < to; current++) {
  62                 result = dg(*current);
  63                 if (result)
  64                     break;
  65             }
  66             return result;
  67         }
  68
  69     }
  70
  71 }
  72
  73 struct BlkInfo
  74 {
  75     void*  base;
  76     size_t size;
  77     uint   attr;
  78 }
  79
  80 // TODO: ver bien donde desmarkcar/marcar celdas (probablemente en malloc)
  81
  82 struct NaiveGC
  83 {
  84
  85 private:
  86
  87     List free_list;
  88
  89     List live_list;
  90
  91     DynArray!(void*) root_pointers;
  92
  93     DynArray!(RootRange) root_ranges;
  94
  95     uint enabled;
  96
  97     void unmark()
  98     {
  99         debug (gc_naive_gc_collect)
 100             printf("gc.unmark()\n");
 101         foreach (cell; this.live_list)
 102             cell.marked = false;
 103     }
 104
 105     void mark_all()
 106     {
 107         debug (gc_naive_gc_collect)
 108             printf("gc.mark_all()\n");
 109         void* stack_top;
 110         mixin (push_registers("stack_top"));
 111         thread_suspendAll();
 112         debug (gc_naive_gc_collect)
 113             printf("gc.mark_all() - scanning static data\n");
 114         rt_scanStaticData(&mark_range);
 115         debug (gc_naive_gc_collect)
 116             printf("gc.mark_all() - scanning threads stack\n");
 117         thread_scanAll(&mark_range, stack_top);
 118         debug (gc_naive_gc_collect)
 119             printf("gc.mark_all() - scanning root pointers:");
 120         foreach (ptr; this.root_pointers) {
 121             debug (gc_naive_gc_collect)
 122                 printf(" %p", ptr);
 123             this.mark(ptr);
 124         }
 125         debug (gc_naive_gc_collect)
 126             printf("\ngc.mark_all() - scanning root ranges:");
 127         foreach (range; this.root_ranges) {
 128             debug (gc_naive_gc_collect)
 129                 printf(" %p-%p", range.from, range.to);
 130             this.mark_range(range.from, range.to);
 131         }
 132         debug (gc_naive_gc_collect)
 133             printf("\n");
 134         thread_resumeAll();
 135         mixin (pop_registers("stack_top"));
 136     }
 137
 138     void mark_range(void* from, void* to)
 139     {
 140         debug (gc_naive_gc_collect)
 141             printf("gc.mark_range(%p, %p)\n", from, to);
 142         foreach (ptr; RootRange(from, to))
 143             mark(ptr);
 144     }
 145
 146     void mark(void* ptr)
 147     {
 148         debug (gc_naive_gc_collect_extra)
 149             printf("gc.mark(%p)\n", ptr);
 150         Cell* cell = Cell.from_ptr(this.addrOf(ptr));
 151         if (cell is null)
 152             return;
 153         debug (gc_naive_gc_collect)
 154             printf("gc.mark() - %p cell=%p\n", cell.ptr, cell);
 155         if (!cell.marked) {
 156             cell.marked = true;
 157             debug (gc_naive_gc_collect)
 158                 printf("gc.mark() - cell=%p marked\n", cell);
 159             if (cell.has_pointers) {
 160                 foreach (ptr; *cell)
 161                     mark(ptr);
 162             }
 163         }
 164     }
 165
 166     void sweep()
 167     {
 168         debug (gc_naive_gc_collect) {
 169             printf("gc.sweep()\n\tfree:");
 170             foreach (cell; this.free_list)
 171                 printf(" %p", cell);
 172             printf("\n\tlive:");
 173             foreach (cell; this.live_list)
 174                 printf(" %s%p", cell.marked ? "*\0".ptr : "\0".ptr, cell);
 175             printf("\n\tfreed:");
 176         }
 177         foreach (cell; this.live_list) {
 178             if (!cell.marked) {
 179                 debug (gc_naive_gc_collect)
 180                     printf(" %p", cell);
 181                 this.live_list.unlink(cell);
 182                 if (cell.finalize())
 183                     rt_finalize(cell.ptr, false);
 184                 this.free_list.link(cell);
 185             }
 186         }
 187         debug (gc_naive_gc_collect) {
 188             printf("\n\tfree:");
 189             foreach (cell; this.free_list)
 190                 printf(" %p", cell);
 191             printf("\n\tlive:");
 192             foreach (cell; this.live_list)
 193                 printf(" %p", cell);
 194             printf("\n");
 195         }
 196     }
 197
 198 public:
 199
 200     void init()
 201     {
 202         // NOTE: The GC must initialize the thread library before its first
 203         //       collection, and always before returning from gc_init().
 204         this.enabled = true;
 205         thread_init();
 206     }
 207
 208     void term()
 209     {
 210         // Finalization of unreferenced cells is not mandatory by the specs.
 211         // This implementation guarantees that all live data gets finalized,
 212         // referenced or unreferenced, at the end of the program.
 213         //foreach (cell; this.live_list)
 214         //    if (cell.finalize)
 215         //         rt_finalize(cell.ptr, false);
 216     }
 217
 218     void enable()
 219     {
 220         this.enabled++;
 221         assert (this.enabled > 0);
 222     }
 223
 224     void disable()
 225     {
 226         assert (this.enabled > 0);
 227         this.enabled--;
 228     }
 229
 230     void collect()
 231     {
 232         this.unmark();
 233         this.mark_all();
 234         this.sweep();
 235     }
 236
 237     void minimize()
 238     {
 239         foreach (cell; this.free_list) {
 240             this.free_list.unlink(cell);
 241             mem_free(cell, cell.capacity + Cell.sizeof);
 242         }
 243     }
 244
 245     uint getAttr(void* ptr)
 246     {
 247         auto cell = this.live_list.find(ptr);
 248         if (cell)
 249             return cell.attr;
 250         return 0;
 251     }
 252
 253     // return the old value
 254     uint setAttr(void* ptr, uint attr)
 255     {
 256         auto cell = this.live_list.find(ptr);
 257         if (cell) {
 258             auto old = cell.attr;
 259             cell.attr |= attr;
 260             return cell.attr;
 261         }
 262         return 0;
 263     }
 264
 265     uint clrAttr(void* ptr, uint attr)
 266     {
 267         auto cell = this.live_list.find(ptr);
 268         if (cell) {
 269             auto old = cell.attr;
 270             cell.attr &= ~attr;
 271             return cell.attr;
 272         }
 273         return 0;
 274     }
 275
 276     void* malloc(size_t size, uint attr=0)
 277     {
 278         debug (gc_naive_gc_malloc)
 279             printf("gc.malloc(%u, %u)\n", size, attr);
 280         if (size == 0)
 281             return null;
 282
 283         // Find a free cell in the free list with enough space
 284         auto cell = this.free_list.pop(size);
 285         if (cell)
 286             goto success;
 287         debug (gc_naive_gc_malloc)
 288             printf("gc.malloc() - no cell available in the free list\n");
 289
 290         // No room in the free list found, trigger a collection
 291         this.collect();
 292
 293         // Try again in the free list
 294         cell = this.free_list.pop(size);
 295         if (cell)
 296             goto success;
 297         debug (gc_naive_gc_malloc)
 298             printf("gc.malloc() - after collection, still no free cell\n");
 299
 300         // No luck still, allocate new memory
 301         cell = cast(Cell*) mem_alloc(size + Cell.sizeof);
 302         if (cell)
 303             goto success;
 304         debug (gc_naive_gc_malloc)
 305             printf("gc.malloc() - can't malloc() from the OS\n");
 306
 307         // No memory
 308         onOutOfMemoryError();
 309
 310         return null;
 311
 312     success:
 313         cell.size = size;
 314         if (cell.capacity == 0) // fresh cell
 315             cell.capacity = size;
 316         cell.attr = cast(BlkAttr) attr;
 317         cell.marked = false;
 318         this.live_list.link(cell);
 319
 320         debug (gc_naive_gc_collect) {
 321             printf("gc.malloc() -> %p (cell=%p)\n\tfree:", cell.ptr, cell);
 322             foreach (cell; this.free_list)
 323                 printf(" %p", cell);
 324             printf(" | live:");
 325             foreach (cell; this.live_list)
 326                 printf(" %p", cell);
 327             printf("\n");
 328         }
 329
 330         return cell.ptr;
 331     }
 332
 333     void* calloc(size_t size, uint attr=0)
 334     {
 335         void* ptr = this.malloc(size, attr);
 336
 337         if (ptr is null)
 338             onOutOfMemoryError();
 339         else
 340             memset(ptr, 0, size);
 341
 342         return ptr;
 343     }
 344
 345     void* realloc(void* ptr, size_t size, uint attr=0)
 346     {
 347         if (ptr is null)
 348             return this.malloc(size, attr);
 349
 350         if (size == 0) {
 351             this.free(ptr);
 352             return null;
 353         }
 354
 355         auto cell = this.live_list.find(ptr);
 356         assert (cell);
 357
 358         if (cell.capacity >= size) {
 359             cell.size = size;
 360             return cell;
 361         }
 362
 363         Cell* new_cell = cast(Cell*) mem_alloc(size + Cell.sizeof);
 364         if (new_cell is null)
 365             onOutOfMemoryError();
 366
 367         memcpy(new_cell, cell, size + Cell.sizeof);
 368         new_cell.size = size;
 369         new_cell.capacity = size;
 370
 371         this.live_list.link(new_cell);
 372
 373         this.free(cell);
 374
 375         return new_cell.ptr;
 376     }
 377
 378     size_t extend(void* ptr, size_t min_size, size_t max_size)
 379     {
 380         assert (min_size <= max_size);
 381         // There is no possible extension of the capacity for this
 382         // implementation.
 383         return 0;
 384     }
 385
 386     size_t reserve(size_t size)
 387     {
 388         assert (size > 0);
 389         auto cell = cast(Cell*) mem_alloc(size + Cell.sizeof);
 390         if (!cell)
 391             return 0;
 392         cell.size = size;
 393         cell.capacity = size;
 394         this.free_list.link(cell);
 395         return size;
 396     }
 397
 398     void free(void* ptr)
 399     {
 400         if (ptr is null)
 401             return;
 402
 403         auto cell = this.live_list.pop(ptr);
 404         assert (cell);
 405
 406         this.free_list.link(cell);
 407     }
 408
 409     void* addrOf(void* ptr)
 410     {
 411         if (ptr is null)
 412             return null;
 413
 414         bool in_range(Cell* cell)
 415         {
 416             return ptr >= cell.ptr && ptr < (cell.ptr + cell.size);
 417         }
 418
 419         auto cell = this.live_list.find(&in_range);
 420         if (cell)
 421             return cell.ptr;
 422
 423         return null;
 424     }
 425
 426     // TODO: acepta un address que no sea el base?
 427     //       es valido aceptar un ptr que no pertenezca al heap?
 428     //       (contestado en basic/gcx.d, pero es estandar?)
 429     size_t sizeOf(void* ptr)
 430     {
 431         auto cell = this.live_list.find(ptr);
 432         if (cell)
 433             return cell.capacity;
 434         return 0;
 435     }
 436
 437     // TODO: acepta un address que no sea el base?
 438     //       es valido aceptar un ptr que no pertenezca al heap?
 439     BlkInfo query(void* ptr)
 440     {
 441         BlkInfo blk_info;
 442
 443         auto cell = this.live_list.find(ptr);
 444         if (cell) {
 445             blk_info.base = cell.ptr;
 446             blk_info.size = cell.capacity;
 447             blk_info.attr = cell.attr;
 448         }
 449
 450         return blk_info;
 451     }
 452
 453     void addRoot(void* ptr)
 454     {
 455         this.root_pointers.append(ptr);
 456     }
 457
 458     void addRange(void* ptr, size_t size)
 459     {
 460         this.root_ranges.append(RootRange(ptr, ptr + size));
 461     }
 462
 463     void removeRoot(void* ptr)
 464     {
 465         this.root_pointers.remove(ptr);
 466     }
 467
 468     void removeRange(void* ptr)
 469     {
 470         foreach (range; this.root_ranges) {
 471             if (range.from is ptr) {
 472                 this.root_ranges.remove(range);
 473                 break;
 474             }
 475         }
 476     }
 477
 478 }
 479
 480 // vim: set et sw=4 sts=4 :