Compare pointers explicitly against null using is and !is

[software/dgc/naive.git] / gc / gc.d

diff --git a/gc/gc.d b/gc/gc.d
index 5f341f0de4751d0adc5c2370278f91cb9a2335ab..a10143a410164fde698846627494c6df5a06deb6 100644 (file)
--- a/gc/gc.d
+++ b/gc/gc.d
@@ -3,23 +3,22 @@
  *
  * This module implements a Naive Garbage Collector. The idea behind this
  * implementation is to document all the bookkeeping and considerations that
  *
  * This module implements a Naive Garbage Collector. The idea behind this
  * implementation is to document all the bookkeeping and considerations that

- * has to be taken in order to implement a garbage collector for D.
+ * have to be taken in order to implement a garbage collector for D.

  *
  *

- * The garbage collector algorithm itself is extremely simple so focus can be
- * held in the specifics of D, and not the algorithm. A completely naive mark
- * and sweep algorithm is used, with a recursive mark phase. The code is
- * extremely inefficient in order to keep the code clean and easy to read and
- * understand.
+ * The garbage collector algorithm itself is extremely simple to make it
+ * easier to focus on the specifics of D. A completely naive mark and sweep
+ * algorithm is used, with a recursive mark phase. The code is extremely
+ * inefficient in order to keep it clean, and easy to read and understand.

  *
  *

- * The implementation is split in several modules to ease even more the
- * lecture. All architecture/compiler specific code is done in the arch module,
- * in order to avoid confusing version statements all over the places. The cell
- * module has all the code related to the memory cells header. dynarray is
- * another support module which holds the implementation of a simple dynamic
- * array used to store root pointers and ranges. The list module holds a simple
- * singly linked list (of cells) implementation to store the live and free
- * lists. Finally, the iface module is the one with the C interface to comply
- * with the Tango/Druntime GC specification.
+ * The implementation is split in several modules to ease the reading even
+ * more. All architecture/compiler specific code is done in the arch module,
+ * in order to avoid confusing version statements all over the places. The
+ * cell module has all the code related to the memory cells header. dynarray
+ * is another support module which holds the implementation of a simple
+ * dynamic array used to store root pointers and ranges. The list module holds
+ * a simple singly linked list (of cells) implementation to store the live and
+ * free lists. Finally, the iface module is the one with the C interface to
+ * comply with the Tango/Druntime GC specification.

  *
  * Copyright: Public Domain
  * License:   Public Domain
  *
  * Copyright: Public Domain
  * License:   Public Domain


@@ -37,7 +36,6 @@ import gc.dynarray: DynArray;
 import gc.arch: push_registers, pop_registers;
 
 // Standard imports
 import gc.arch: push_registers, pop_registers;
 
 // Standard imports

-import cstdlib = tango.stdc.stdlib;

 import cstring = tango.stdc.string;
 
 // Debug imports
 import cstring = tango.stdc.string;
 
 // Debug imports


@@ -65,7 +63,7 @@ extern (C) void thread_scanAll(mark_function mark, void* stack_top=null);
 struct RootRange
 {
 
 struct RootRange
 {
 

-    /// Start of the memory range
+    /// Beginning of the memory range

     void* from;
 
     /// End of the memory range
     void* from;
 
     /// End of the memory range


@@ -152,8 +150,6 @@ struct BlkInfo
 struct GC
 {
 
 struct GC
 {
 

-// TODO: GC Lock
-

 private:
 
     /// List of free cells.
 private:
 
     /// List of free cells.


@@ -165,7 +161,7 @@ private:
     /// Single root pointers.
     DynArray!(void*) root_pointers;
 
     /// Single root pointers.
     DynArray!(void*) root_pointers;
 

-    /// Single root pointers.
+    /// Root ranges.

     DynArray!(RootRange) root_ranges;
 
     /**
     DynArray!(RootRange) root_ranges;
 
     /**


@@ -197,7 +193,7 @@ private:
     }
 
     /**
     }
 
     /**

-     * Marks all live data (pausing all threads)
+     * Mark all live data (pausing all threads)

      *
      * This methods start marking following all the known roots:
      *
      *
      * This methods start marking following all the known roots:
      *


@@ -253,8 +249,7 @@ private:
      * Wrapper for mark() over a range, needed by some runtime functions.
      *
      * This function is used as a delegate to be passed to rt_scanStaticData()
      * Wrapper for mark() over a range, needed by some runtime functions.
      *
      * This function is used as a delegate to be passed to rt_scanStaticData()

-     * and thread_scanAll(), because they expects a function taking
-     * 2 pointers.
+     * and thread_scanAll(), because they expect a function taking 2 pointers.

      *
      * This extremely inefficient on purpose. The goal of this implementation
      * is simplicity, nor performance.
      *
      * This extremely inefficient on purpose. The goal of this implementation
      * is simplicity, nor performance.


@@ -271,7 +266,7 @@ private:
     }
 
     /**
     }
 
     /**

-     * Marks all cells accessible from a pointer.
+     * Mark all cells accessible from a pointer.

      *
      * This is the mark algorithm itself. It's recursive and dumb as a log. No
      * care is taken in regards to stack overflows. This is the first example
      *
      * This is the mark algorithm itself. It's recursive and dumb as a log. No
      * care is taken in regards to stack overflows. This is the first example


@@ -400,7 +395,7 @@ public:
      * Run a GC collection in order to find unreferenced objects.
      *
      * This is the simplest stop-the-world mark-sweep algorithm ever. It first
      * Run a GC collection in order to find unreferenced objects.
      *
      * This is the simplest stop-the-world mark-sweep algorithm ever. It first

-     * removes the mark bit from all the live cells, then it mark the cells
+     * removes the mark bit from all the live cells, then it marks the cells

      * that are reachable through the root set (static data, stack, registers
      * and custom root), and finally sweeps the live list looking for unmarked
      * cells to free.
      * that are reachable through the root set (static data, stack, registers
      * and custom root), and finally sweeps the live list looking for unmarked
      * cells to free.


@@ -439,17 +434,17 @@ public:
     {
         foreach (cell; this.free_list) {
             this.free_list.unlink(cell);
     {
         foreach (cell; this.free_list) {
             this.free_list.unlink(cell);

-            cstdlib.free(cell);
+            Cell.free(cell);

         }
     }
 
     /**
      * Get attributes associated to the cell pointed by ptr.
      *
         }
     }
 
     /**
      * Get attributes associated to the cell pointed by ptr.
      *

-     * Attributes is a bitmap that can have theses values:
+     * Attributes is a bitmap that can have these values:

      *
      *  $(UL
      *
      *  $(UL

-     *      $(LI 1: The object stored in the cell have to be finalized)
+     *      $(LI 1: The object stored in the cell has to be finalized)

      *      $(LI 2: The cell should not be scanned for pointers)
      *      $(LI 4: The cell should not be moved during a collection
      *           (unimplemented))
      *      $(LI 2: The cell should not be scanned for pointers)
      *      $(LI 4: The cell should not be moved during a collection
      *           (unimplemented))


@@ -460,7 +455,7 @@ public:
     uint getAttr(void* ptr)
     {
         auto cell = this.live_list.find(ptr);
     uint getAttr(void* ptr)
     {
         auto cell = this.live_list.find(ptr);

-        if (cell)
+        if (cell !is null)

             return cell.attr;
         return 0;
     }
             return cell.attr;
         return 0;
     }


@@ -476,7 +471,7 @@ public:
     uint setAttr(void* ptr, uint attr)
     {
         auto cell = this.live_list.find(ptr);
     uint setAttr(void* ptr, uint attr)
     {
         auto cell = this.live_list.find(ptr);

-        if (cell) {
+        if (cell !is null) {

             auto old = cell.attr;
             cell.attr |= attr;
             return cell.attr;
             auto old = cell.attr;
             cell.attr |= attr;
             return cell.attr;


@@ -495,7 +490,7 @@ public:
     uint clrAttr(void* ptr, uint attr)
     {
         auto cell = this.live_list.find(ptr);
     uint clrAttr(void* ptr, uint attr)
     {
         auto cell = this.live_list.find(ptr);

-        if (cell) {
+        if (cell !is null) {

             auto old = cell.attr;
             cell.attr &= ~attr;
             return cell.attr;
             auto old = cell.attr;
             cell.attr &= ~attr;
             return cell.attr;


@@ -523,33 +518,33 @@ public:
 
         // Find a free cell in the free list with enough space
         auto cell = this.free_list.pop(size);
 
         // Find a free cell in the free list with enough space
         auto cell = this.free_list.pop(size);

-        if (cell)
-            goto success;
+        if (cell !is null)
+            goto reuse;

 
         // No room in the free list found, if the GC is enabled, trigger
         // a collection and try again
         if (!this.disabled) {
             this.collect();
             cell = this.free_list.pop(size);
 
         // No room in the free list found, if the GC is enabled, trigger
         // a collection and try again
         if (!this.disabled) {
             this.collect();
             cell = this.free_list.pop(size);

-            if (cell)
-                goto success;
+            if (cell !is null)
+                goto reuse;

         }
 
         }
 

-        // No luck still, allocate new memory
-        cell = cast(Cell*) cstdlib.malloc(size + Cell.sizeof);
-        if (cell)
-            goto success;
+        // No luck still, allocate a new cell
+        cell = Cell.alloc(size, attr);
+        if (cell !is null)
+            goto link;

 
         // No memory
         onOutOfMemoryError();
 
         return null;
 
 
         // No memory
         onOutOfMemoryError();
 
         return null;
 

-    success:
+    reuse:

         cell.size = size;
         cell.size = size;

-        if (cell.capacity == 0) // fresh cell
-            cell.capacity = size;

         cell.attr = cast(BlkAttr) attr;
         cell.attr = cast(BlkAttr) attr;

+
+    link:

         this.live_list.link(cell);
 
         return cell.ptr;
         this.live_list.link(cell);
 
         return cell.ptr;


@@ -562,11 +557,12 @@ public:
      */
     void* calloc(size_t size, uint attr=0)
     {
      */
     void* calloc(size_t size, uint attr=0)
     {

+        if (size == 0)
+            return null;
+

         void* ptr = this.malloc(size, attr);
 
         void* ptr = this.malloc(size, attr);
 

-        if (ptr is null)
-            onOutOfMemoryError();
-        else
+        if (ptr !is null) // in case onOutOfMemoryError didn't throw

             cstring.memset(ptr, 0, size);
 
         return ptr;
             cstring.memset(ptr, 0, size);
 
         return ptr;


@@ -580,7 +576,7 @@ public:
      * returned. Otherwise a new cell is allocated using malloc() (this can
      * trigger a collection), the contents are moved and the old cell is freed.
      *
      * returned. Otherwise a new cell is allocated using malloc() (this can
      * trigger a collection), the contents are moved and the old cell is freed.
      *

-     * attr are the same as malloc().
+     * attr has the same meaning as in malloc().

      */
     void* realloc(void* ptr, size_t size, uint attr=0)
     {
      */
     void* realloc(void* ptr, size_t size, uint attr=0)
     {


@@ -596,7 +592,7 @@ public:
         }
 
         auto cell = this.live_list.find(ptr);
         }
 
         auto cell = this.live_list.find(ptr);

-        assert (cell);
+        assert (cell !is null);

 
         // We have enough capacity already, just change the size
         if (cell.capacity >= size) {
 
         // We have enough capacity already, just change the size
         if (cell.capacity >= size) {


@@ -606,8 +602,11 @@ public:
 
         // We need to move the cell because of the lack of capacity, find
         // a free cell with the requested capacity (at least)
 
         // We need to move the cell because of the lack of capacity, find
         // a free cell with the requested capacity (at least)

-        Cell* new_cell = Cell.from_ptr(this.malloc(size));
-        assert (!(new_cell is null)); // out of memory is handled by malloc()
+        ptr = this.malloc(size, attr);
+        if (ptr is null) // in case onOutOfMemoryError didn't throw
+            return null;
+        Cell* new_cell = Cell.from_ptr(ptr);
+        assert (new_cell !is null);

 
         // Move cell attributes and contents
         new_cell.attr = cell.attr;
 
         // Move cell attributes and contents
         new_cell.attr = cell.attr;


@@ -642,29 +641,27 @@ public:
      * Reserve memory to anticipate memory allocations.
      *
      * This implementation is really dumb, a single cell is allocated with
      * Reserve memory to anticipate memory allocations.
      *
      * This implementation is really dumb, a single cell is allocated with

-     * size bytes. If 2 mallocs() follows a call to reserve(size), requesting
-     * size/2 bytes each, one allocation will be done still (and  half the
-     * memory of the first malloc will be wasted =) Since this is a trivial
+     * size bytes. If 2 malloc()s follow a call to reserve(size), requesting
+     * size/2 bytes each, one allocation will still be done (and half the
+     * memory of the first malloc will be wasted =). Since this is a trivial

      * implementation, we don't care about this.
      *
      * implementation, we don't care about this.
      *

-     * The actual number of bytes reserver are returned, or 0 on error.
+     * The actual number of bytes reserved are returned, or 0 on error.

      */
     size_t reserve(size_t size)
     {
         assert (size > 0);
      */
     size_t reserve(size_t size)
     {
         assert (size > 0);

-        auto cell = cast(Cell*) cstdlib.malloc(size + Cell.sizeof);
-        if (!cell)
+        auto cell = Cell.alloc(size);
+        if (cell is null)

             return 0;
             return 0;

-        cell.size = size;
-        cell.capacity = size;

         this.free_list.link(cell);
         this.free_list.link(cell);

-        return size;
+        return cell.capacity;

     }
 
     /**
      * Free unused memory.
      *
     }
 
     /**
      * Free unused memory.
      *

-     * This method tells the GC that a cell is not longer used. The GC don't
+     * This method tells the GC that a cell is not longer used. The GC doesn't

      * perform any connectivity check, if the cell was referenced by others,
      * nasty things will happen (much like C/C++).
      *
      * perform any connectivity check, if the cell was referenced by others,
      * nasty things will happen (much like C/C++).
      *


@@ -678,7 +675,7 @@ public:
             return;
 
         auto cell = this.live_list.pop(ptr);
             return;
 
         auto cell = this.live_list.pop(ptr);

-        assert (cell);
+        assert (cell !is null);

 
         this.free_list.link(cell);
     }
 
         this.free_list.link(cell);
     }


@@ -699,14 +696,14 @@ public:
         }
 
         auto cell = this.live_list.find(&in_range);
         }
 
         auto cell = this.live_list.find(&in_range);

-        if (cell)
+        if (cell !is null)

             return cell.ptr;
 
         return null;
     }
 
     /**
             return cell.ptr;
 
         return null;
     }
 
     /**

-     * Return the real size (capacity) for the cell pointed by ptr.
+     * Return the real size (capacity) for the cell pointed to by ptr.

      *
      * ptr should be the base address of a heap allocated object, interior
      * pointers are not supported (use addrOf() if you have an interior
      *
      * ptr should be the base address of a heap allocated object, interior
      * pointers are not supported (use addrOf() if you have an interior


@@ -718,13 +715,13 @@ public:
     size_t sizeOf(void* ptr)
     {
         auto cell = this.live_list.find(ptr);
     size_t sizeOf(void* ptr)
     {
         auto cell = this.live_list.find(ptr);

-        if (cell)
+        if (cell !is null)

             return cell.capacity;
         return 0;
     }
 
     /**
             return cell.capacity;
         return 0;
     }
 
     /**

-     * Get information about the cell pointed by ptr.
+     * Get information about the cell pointed to by ptr.

      *
      * ptr should be the base address of a heap allocated object, interior
      * pointers are not supported (use addrOf() if you have an interior
      *
      * ptr should be the base address of a heap allocated object, interior
      * pointers are not supported (use addrOf() if you have an interior


@@ -737,7 +734,7 @@ public:
         BlkInfo blk_info;
 
         auto cell = this.live_list.find(ptr);
         BlkInfo blk_info;
 
         auto cell = this.live_list.find(ptr);

-        if (cell) {
+        if (cell !is null) {

             blk_info.base = cell.ptr;
             blk_info.size = cell.capacity;
             blk_info.attr = cell.attr;
             blk_info.base = cell.ptr;
             blk_info.size = cell.capacity;
             blk_info.attr = cell.attr;


@@ -782,8 +779,8 @@ public:
     /**
      * Remove a root pointer from the root set.
      *
     /**
      * Remove a root pointer from the root set.
      *

-     * ptr has to be previously registered using addRoot(), in other case the
-     * results of this method is undefined.
+     * ptr has to be previously registered using addRoot(), otherwise the
+     * results are undefined.

      *
      * See_Also: addRoot(), addRange(), removeRange()
      */
      *
      * See_Also: addRoot(), addRange(), removeRange()
      */


@@ -795,8 +792,8 @@ public:
     /**
      * Remove a root range from the root set.
      *
     /**
      * Remove a root range from the root set.
      *

-     * ptr has to be previously registered using addRange(), in other case the
-     * results of this method is undefined.
+     * ptr has to be previously registered using addRange(), otherwise the
+     * results are undefined.

      *
      * See_Also: addRange(), addRoot(), removeRoot()
      */
      *
      * See_Also: addRange(), addRoot(), removeRoot()
      */