D2 weak references

[Leandro Lucarella]

Leandro Lucarella, el 22 de abril a las 16:08 me escribiste:
> Jason House, el 22 de abril a las 13:31 me escribiste:
> > > > Unfortunately, that is not efficient. The state used by the GC is in
> > > > flux during the sweep phase, so there is no easy lockless way to access
> > > > that data. Having to acquire a lock on every weakref dereference
> > > > absolutely kills performance.
> > > 
> > > The sweep phase don't touch mark bits. I can't possible understand why
> > > you should synchronize access to a (temporarily) read-only variable.
> > 
> > I'm mostly regurgitating what Sean Kelly said. I know that if the sweep
> > deallocates at an object, the bits marking it become invalid. I don't
> > disagree that reading the bits without a lock should be possible, but
> > I also trust Sean's statement that it isn't easy. I'm trying to find
> > something that doesn't require reworking or rewriting large parts of
> > a garbage collector.
> 
> Sean's idea was, if I recall correctly, to move the sweep phase into the
> stop-the-world. My idea is different, and it doesn't need rewriting any
> large part of the collector. I think the change is pretty small (and can
> be easily applied to D1/Tango too).
> 
> I'm looking at the Tango code right now, and you know what? The unmarking
> is already done when all threads are paused, so all you need for this to
> work is a method to expose the mark bit. This can be really easily done by
> extending the BlkAttr defined values (or using a reserved value if this
> should not be a standard attribute) and ensuring that the mark bit is set
> when new pools/bins are allocated.
> 
> This patch (Tango) should do that (untested):
> ------>8------>8------>8------>8------>8------>8------>8------>8------>8------
> diff --git a/lib/gc/basic/gcx.d b/lib/gc/basic/gcx.d
> index a760465..fd21d44 100644
> --- a/lib/gc/basic/gcx.d
> +++ b/lib/gc/basic/gcx.d
> @@ -81,6 +81,7 @@ private
>          NO_SCAN  = 0b0000_0010,
>          NO_MOVE  = 0b0000_0100,
>          ALL_BITS = 0b1111_1111
> +        MARK_BIT = 0b1_0000_0000_0000_0000; // extension to query the mark bit
>      }
>  
>      extern (C) void* rt_stackBottom();
> @@ -519,7 +520,14 @@ class GC
>              Pool *pool = gcx.findPool(p);
>              assert(pool);
>  
> -            gcx.setBits(pool, cast(size_t)(p - pool.baseAddr) / 16, bits);
> +           uint biti = cast(size_t)(p - pool.baseAddr) / 16;
> +            gcx.setBits(pool, biti, bits);
> +           // Set the mark bit to maintain the invariant that live objects
> +           // always have the mark bit set, except when the collector is in
> +           // the mark phase (useful for weak reference implementations)
> +           // This is not done in setBits() to keep this bit read-only for
> +           // the user.
> +           pool.mark.set(biti)
>          }
>          return p;
>      }
> @@ -2576,6 +2584,8 @@ struct Gcx
>  //        if (pool.nomove.nbits &&
>  //            pool.nomove.test(biti))
>  //            bits |= BlkAttr.NO_MOVE;
> +        if (pool.mark.test(biti))
> +            bits |= BlkAttr.MARK_BIT;
>          return bits;
>      }
>  
> ------8<------8<------8<------8<------8<------8<------8<------8<------8<------

Woops! I already spotted a bug there =). The mark bit was only set if the
malloc was done passing bits. The solution has a performance penalty of a
"extra" pool lookup for malloc where attr == 0.

This is the fixed patch:

------>8------>8------>8------>8------>8------>8------>8------>8------>8------
diff --git a/lib/gc/basic/gcx.d b/lib/gc/basic/gcx.d
index a760465..940bc71 100644
--- a/lib/gc/basic/gcx.d
+++ b/lib/gc/basic/gcx.d
@@ -81,6 +81,7 @@ private
         NO_SCAN  = 0b0000_0010,
         NO_MOVE  = 0b0000_0100,
         ALL_BITS = 0b1111_1111
+        MARK_BIT = 0b1_0000_0000_0000_0000; // extension to query the mark bit
     }
 
     extern (C) void* rt_stackBottom();
@@ -514,13 +515,18 @@ class GC
         sentinel_init(p, size);
         gcx.log_malloc(p, size);
 
-        if (bits)
-        {
-            Pool *pool = gcx.findPool(p);
-            assert(pool);
+        Pool *pool = gcx.findPool(p);
+        assert(pool);
 
-            gcx.setBits(pool, cast(size_t)(p - pool.baseAddr) / 16, bits);
-        }
+        uint biti = cast(size_t)(p - pool.baseAddr) / 16;
+        if (bits)
+            gcx.setBits(pool, biti, bits);
+        // Set the mark bit to maintain the invariant that live objects
+        // always have the mark bit set, except when the collector is in
+        // the mark phase (useful for weak reference implementations)
+        // This is not done in setBits() to keep this bit read-only for
+        // the user.
+        pool.mark.set(biti)
         return p;
     }
 
@@ -2576,6 +2582,8 @@ struct Gcx
 //        if (pool.nomove.nbits &&
 //            pool.nomove.test(biti))
 //            bits |= BlkAttr.NO_MOVE;
+        if (pool.mark.test(biti))
+            bits |= BlkAttr.MARK_BIT;
         return bits;
     }
 
------8<------8<------8<------8<------8<------8<------8<------8<------8<------

-- 
Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/
----------------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------------
Bulletproof... I Wish I Was