April 23, 2009
Leandro Lucarella Wrote:

> Jason House, el 22 de abril a las 21:26 me escribiste:
> > I'm finally looking at the gc source code.  From what I can tell, memory is allocated in large chunks (pools), and divided into 16 byte chunks.
> > 
> > Attributes are not all packed together like the BlkInfo of the spec implies, so some so access to that stuff is safer than I would have thought.
> 
> I'm sorry you had to go through that, I think this could have save you
> a lot of time =)
> http://proj.llucax.com.ar/blog/dgc/blog/tag/understanding%20the%20current%20gc

It really wasn't that bad of a way to familiarize myself. I had enough of an idea about how it coulf work already. It is helpful to compare what I expect in a gc verses what's actually in the gc. I appreciate the link and will make sure to read it.



> > Here's a weak ref implementation that I just whipped together under the assumption it goes into druntime/src/gc/basic/gcx.d.  I think it is sane.  I haven't scoured the gc's code to ensure everything is legit.  I declared it as a class mostly because value semantics don't make much sense and I'm too lazy/tired to do the sample code as a 100% correct struct definition.
> > 
> > My two biggest concerns:
> > 
> > 1. Is the gc lock held while running a constructor? If not and it's needed to do what it needs, where can the hook be added to make the construction of a weak reference special?
> 
> I don't think it's held, I just can't see how it can be held because construction is not done in the GC.
> 
> If you need to acquire the GC lock I think you can just do:
> synchronized (GC.gcLock) {
> 	// protected stuff
> }
> The GC lock is a static member of the GC struct in gcx.d.

Efficiency is a big concern of mine with this because I'm going to use it heavily. Locking twice is undesirable, but I may do it in an initial implementation. A lock on deref is unacceptable though.



> > 2. Will the assignment to noscan get overwritten / hit a race condition?
> 
> I don't think that should happen except if someone calls
> gc_setAttr/gc_getAttr().
> 
> > It is possible to hide the pointer inside a size_t instead, but given the intimate tying to the GC such tricks just make the code tougher to read.
> 
> Agree. Maybe you can overload the operator new and pass the flags directly at allocation time, but I don't know very well how this is plugged in the runtime/GC, but since it's a regular gc_malloc() call it should be thread-safe.

Interesting idea. I'll look into that.



> Something like:
> 
> class weakRef(T) if (is(T==class))
> {
> 	new(size_t size)
> 	{
> 		return gc_malloc(size, FINALIZE | NO_SCAN);
> 	}
> 	this(T _t)
> 	{
> 		// set up tracking for the weakly referenced object
> 		t = _t;
> 		pool = findPool(t);
> 		rt_attachDisposeEvent(&t, &sweep);
> 	}
> 	// ...
> }
> 
> 
> > class weakRef(T) if (is(T==class))
> > {
> >     this(T _t){
> >         // set up tracking for the weakly referenced object
> >         t = _t;
> >         pool = findPool(t);
> >         rt_attachDisposeEvent(&t, &sweep);
> > 
> >         // tell the gc to not scan the weak reference
> >         weakRefPool = findPool(&this);
> >         weakRefPool.noscan[index(weakRefPool,&this)] = true;
> 
> You can do this by calling setAttr(&this, NO_SCAN).

True.


> >     }
> > 
> >     T opCall(){
> >         T tmp = t; // force future conservative GC scan to find the pointer
> >         if ( (tmp is null) || (pool.mark[index] == false) ){
> 
> pool.mark.test(index) is used in the GC code, I don't know if the array syntax works. And to use the mark bit trick, I think something in the lines of my patch is needed to ensure the mark bit is set for all live objects.
> 
> >             t = null;
> >             return null;
> >         }
> >         tmp = t; // avoid race where t was replaced with new data
> 
> I don't understand exactly what kind of race are you trying to avoid with this (and how this assignation can avoid any race if there is one).

Consider this sequence:
1. GC runs mark phase and leaves object unmarked.
2. Weakref starts dereferencing and reads its hidden pointer.
3. Sweep calls finalizer and deallocates
4. A new object is allocated in the old location
5. Query for GC mark says we're ok
6. Weakref returns its old copy of the pointer
7. Pointer is used
8. Random behavior



> >         return tmp;
> >     }
> > 
> > private:
> >     T t;
> >     Pool* pool;
> > 
> >     size_t index(Pool *p, byte *element){ return (element-p)/16; }
> >     size_t index(){ return index(pool,&t); }
> > 
> >     void sweep( Object o ){
> >         t = null;
> >         pool = null;
> >     }
> > }
> 
> 
> 
> -- 
> Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/
> ----------------------------------------------------------------------------
> GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
> ----------------------------------------------------------------------------
> Lo último que hay que pensar es que se desalinea la memoria
> Hay que priorizar como causa la idiotez propia
> Ya lo tengo asumido
> 	-- Pablete, filósofo contemporáneo desconocido

April 23, 2009
Jason House, el 23 de abril a las 12:51 me escribiste:
> > >     T opCall(){
> > >         T tmp = t; // force future conservative GC scan to find the pointer
> > >         if ( (tmp is null) || (pool.mark[index] == false) ){
> > 
> > pool.mark.test(index) is used in the GC code, I don't know if the array syntax works. And to use the mark bit trick, I think something in the lines of my patch is needed to ensure the mark bit is set for all live objects.
> > 
> > >             t = null;
> > >             return null;
> > >         }
> > >         tmp = t; // avoid race where t was replaced with new data
> > 
> > I don't understand exactly what kind of race are you trying to avoid with this (and how this assignation can avoid any race if there is one).
> 
> Consider this sequence:
> 1. GC runs mark phase and leaves object unmarked.
> 2. Weakref starts dereferencing and reads its hidden pointer.

Ok, I see now that this can happen because you first store the reference into the stack so it can be seen in future collections.

What I'm not sure is if it's really necessary to do that step. What can go wrong with this simple approach?

     T opCall() {
         if (!pool.mark.test(index))
             t = null;
         return t;
     }

Weakref only reads the reference *if* the mark bit is set, in which case is safe to assume that the object is live.

If the object is garbage, the mark bit is unset and in that case the reference is only *written* (the only race it could happen is the sweep() can be called but in that case the reference is written to null too, so there should be no problem with that, I guess...

As long as the test are successful (t is not overwritten to null), the GC should be able to find the reference in the stack when the function returns.

I'm probably missing something else...

> 3. Sweep calls finalizer and deallocates
> 4. A new object is allocated in the old location
> 5. Query for GC mark says we're ok
> 6. Weakref returns its old copy of the pointer
> 7. Pointer is used
> 8. Random behavior

-- 
Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/
----------------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------------
April 23, 2009
Leandro Lucarella Wrote:

> Jason House, el 23 de abril a las 12:51 me escribiste:
> > > >     T opCall(){
> > > >         T tmp = t; // force future conservative GC scan to find the pointer
> > > >         if ( (tmp is null) || (pool.mark[index] == false) ){
> > > 
> > > pool.mark.test(index) is used in the GC code, I don't know if the array syntax works. And to use the mark bit trick, I think something in the lines of my patch is needed to ensure the mark bit is set for all live objects.
> > > 
> > > >             t = null;
> > > >             return null;
> > > >         }
> > > >         tmp = t; // avoid race where t was replaced with new data
> > > 
> > > I don't understand exactly what kind of race are you trying to avoid with this (and how this assignation can avoid any race if there is one).
> > 
> > Consider this sequence:
> > 1. GC runs mark phase and leaves object unmarked.
> > 2. Weakref starts dereferencing and reads its hidden pointer.
> 
> Ok, I see now that this can happen because you first store the reference into the stack so it can be seen in future collections.

Yeah.


> What I'm not sure is if it's really necessary to do that step. What can go wrong with this simple approach?
> 
>      T opCall() {
>          if (!pool.mark.test(index))
>              t = null;
>          return t;
>      }

What happens when a collection runs after test returns? You need to copy t onto the stack in order to be safe.

> Weakref only reads the reference *if* the mark bit is set, in which case is safe to assume that the object is live.

How do you check the mark bit? In the sample code, it used the reference... Admittedly, one could store the right info to avoid that, but it hardly matters.


> If the object is garbage, the mark bit is unset and in that case the reference is only *written* (the only race it could happen is the sweep() can be called but in that case the reference is written to null too, so there should be no problem with that, I guess...
> 
> As long as the test are successful (t is not overwritten to null), the GC should be able to find the reference in the stack when the function returns.
> 
> I'm probably missing something else...

You're not considering what can happen if the weak ref dereferencing thread stops and the rest of the world wreaks havoc on the state of the world. A collection could run after checking the mark. If one is careful with that, and a copy of t is kept on the stack, will the optimizer reuse it? Or will it reread the value? That matters if the finalizer runs. The mark bit check can fail from reallocation after deletion.

I hope that helps...



> > 3. Sweep calls finalizer and deallocates
> > 4. A new object is allocated in the old location
> > 5. Query for GC mark says we're ok
> > 6. Weakref returns its old copy of the pointer
> > 7. Pointer is used
> > 8. Random behavior
> 
> -- 
> Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/
> ----------------------------------------------------------------------------
> GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
> ----------------------------------------------------------------------------

April 25, 2009
Jason House, el 23 de abril a las 16:48 me escribiste:
> > What I'm not sure is if it's really necessary to do that step. What can go wrong with this simple approach?
> > 
> >      T opCall() {
> >          if (!pool.mark.test(index))
> >              t = null;
> >          return t;
> >      }
> 
> What happens when a collection runs after test returns? You need to copy t onto the stack in order to be safe.

You're right, I definitely underestimated the problem. Now I see that this sequence breaks that implementation:

1) WeakRef.opCall() is called (whick stores a reference to R)
2) The mark bit for R is tested and returns true
3) CPU time is given to other threads with reference to R, which are
   removed
4) Other thread triggers a collection and the world is stopped
5) R gets unmarked because there are no other references to it
6) The world is started
7) WeakRef.opCall() returns R when it should returned null

The problem I see with your original proposal:

    T opCall(){
        T tmp = t; // force future conservative GC scan to find the pointer
        if ( (tmp is null) || (pool.mark[index] == false) ){
            t = null;
            return null;
        }
        tmp = t; // avoid race where t was replaced with new data
        return tmp;
    }

Is that I guess is very likely that 'tmp' get optimized out. Would declaring it as volatile help? If not, I guess the only way to avoid that race is add a root manually to the GC (or mark the weakref again as no NO_SCAN). But both requires synchronization. =(

> > Weakref only reads the reference *if* the mark bit is set, in which case is safe to assume that the object is live.
> 
> How do you check the mark bit? In the sample code, it used the reference... Admittedly, one could store the right info to avoid that, but it hardly matters.

Right.

> > If the object is garbage, the mark bit is unset and in that case the reference is only *written* (the only race it could happen is the sweep() can be called but in that case the reference is written to null too, so there should be no problem with that, I guess...
> > 
> > As long as the test are successful (t is not overwritten to null), the GC should be able to find the reference in the stack when the function returns.
> > 
> > I'm probably missing something else...
> 
> You're not considering what can happen if the weak ref dereferencing thread stops and the rest of the world wreaks havoc on the state of the world. A collection could run after checking the mark. If one is careful with that, and a copy of t is kept on the stack, will the optimizer reuse it? Or will it reread the value? That matters if the finalizer runs. The mark bit check can fail from reallocation after deletion.
> 
> I hope that helps...

Yes, thank you.

-- 
Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/
----------------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------------
- Que hacés, ratita?
- Espero un ratito...
April 25, 2009
Leandro Lucarella Wrote:

> Jason House, el 23 de abril a las 16:48 me escribiste:
> > > What I'm not sure is if it's really necessary to do that step. What can go wrong with this simple approach?
> > > 
> > >      T opCall() {
> > >          if (!pool.mark.test(index))
> > >              t = null;
> > >          return t;
> > >      }
> > 
> > What happens when a collection runs after test returns? You need to copy t onto the stack in order to be safe.
> 
> You're right, I definitely underestimated the problem. Now I see that this sequence breaks that implementation:
> 
> 1) WeakRef.opCall() is called (whick stores a reference to R)
> 2) The mark bit for R is tested and returns true
> 3) CPU time is given to other threads with reference to R, which are
>    removed
> 4) Other thread triggers a collection and the world is stopped
> 5) R gets unmarked because there are no other references to it
> 6) The world is started
> 7) WeakRef.opCall() returns R when it should returned null
> 
> The problem I see with your original proposal:
> 
>     T opCall(){
>         T tmp = t; // force future conservative GC scan to find the pointer
>         if ( (tmp is null) || (pool.mark[index] == false) ){
>             t = null;
>             return null;
>         }
>         tmp = t; // avoid race where t was replaced with new data
>         return tmp;
>     }
> 
> Is that I guess is very likely that 'tmp' get optimized out. Would declaring it as volatile help? If not, I guess the only way to avoid that race is add a root manually to the GC (or mark the weakref again as no NO_SCAN). But both requires synchronization. =(

I would use tango.core.atomic that I took from the Tango D2 branch. Another option is inline asm, but I'd have to research how to do that.


> > > Weakref only reads the reference *if* the mark bit is set, in which case is safe to assume that the object is live.
> > 
> > How do you check the mark bit? In the sample code, it used the reference... Admittedly, one could store the right info to avoid that, but it hardly matters.
> 
> Right.
> 
> > > If the object is garbage, the mark bit is unset and in that case the reference is only *written* (the only race it could happen is the sweep() can be called but in that case the reference is written to null too, so there should be no problem with that, I guess...
> > > 
> > > As long as the test are successful (t is not overwritten to null), the GC should be able to find the reference in the stack when the function returns.
> > > 
> > > I'm probably missing something else...
> > 
> > You're not considering what can happen if the weak ref dereferencing thread stops and the rest of the world wreaks havoc on the state of the world. A collection could run after checking the mark. If one is careful with that, and a copy of t is kept on the stack, will the optimizer reuse it? Or will it reread the value? That matters if the finalizer runs. The mark bit check can fail from reallocation after deletion.
> > 
> > I hope that helps...
> 
> Yes, thank you.

It's amazingly difficult to get right for something so "simple"

> -- 
> Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/
> ----------------------------------------------------------------------------
> GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
> ----------------------------------------------------------------------------
> - Que hacés, ratita?
> - Espero un ratito...

April 25, 2009
Jason House, el 25 de abril a las 14:19 me escribiste:
> > Is that I guess is very likely that 'tmp' get optimized out. Would declaring it as volatile help? If not, I guess the only way to avoid that race is add a root manually to the GC (or mark the weakref again as no NO_SCAN). But both requires synchronization. =(
> 
> I would use tango.core.atomic that I took from the Tango D2 branch. Another option is inline asm, but I'd have to research how to do that.

I don't know how an atomic can help, I don't know much about atomics but I think they don't have to be pointer sized (different architectures provide different atomic types). And in any case you don't want tmp to be atomic, you just don't want it to be optimized out, I think..

I guess asm can never get optimized (right?) so I think that should do.

BTW, that's wrong with volatile? I think it should work too.

> > > You're not considering what can happen if the weak ref dereferencing thread stops and the rest of the world wreaks havoc on the state of the world. A collection could run after checking the mark. If one is careful with that, and a copy of t is kept on the stack, will the optimizer reuse it? Or will it reread the value? That matters if the finalizer runs. The mark bit check can fail from reallocation after deletion.
> > > 
> > > I hope that helps...
> > 
> > Yes, thank you.
> 
> It's amazingly difficult to get right for something so "simple"

Indeed.

-- 
Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/
----------------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------------
Wake from your sleep,
the drying of your tears,
Today we escape, we escape.
April 25, 2009
Leandro Lucarella Wrote:

> Jason House, el 25 de abril a las 14:19 me escribiste:
> > > Is that I guess is very likely that 'tmp' get optimized out. Would declaring it as volatile help? If not, I guess the only way to avoid that race is add a root manually to the GC (or mark the weakref again as no NO_SCAN). But both requires synchronization. =(
> > 
> > I would use tango.core.atomic that I took from the Tango D2 branch. Another option is inline asm, but I'd have to research how to do that.
> 
> I don't know how an atomic can help, I don't know much about atomics but I think they don't have to be pointer sized (different architectures provide different atomic types). And in any case you don't want tmp to be atomic, you just don't want it to be optimized out, I think..

Not tmp, the hidden pointer t. The read calls can't be optimized away, even with inlining because they use asm code.


> I guess asm can never get optimized (right?) so I think that should do.

Right. D2 treats all asm as volatile asm.

> BTW, that's wrong with volatile? I think it should work too.

The volatile keyword does not exist in D2. Declaring the t (reference) as volatile would work if it existed in D2.

> > > > You're not considering what can happen if the weak ref dereferencing thread stops and the rest of the world wreaks havoc on the state of the world. A collection could run after checking the mark. If one is careful with that, and a copy of t is kept on the stack, will the optimizer reuse it? Or will it reread the value? That matters if the finalizer runs. The mark bit check can fail from reallocation after deletion.
> > > > 
> > > > I hope that helps...
> > > 
> > > Yes, thank you.
> > 
> > It's amazingly difficult to get right for something so "simple"
> 
> Indeed.
> 
> -- 
> Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/
> ----------------------------------------------------------------------------
> GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
> ----------------------------------------------------------------------------
> Wake from your sleep,
> the drying of your tears,
> Today we escape, we escape.

1 2 3 4 5
Next ›   Last »