Per-generation lists of weak pointers

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

Per-generation lists of weak pointers

Akio Takano
Hi,

I'm working on implementing per-generation lists of weak pointers to
speed up garbage collection in programs that allocate a lot of weak
pointers. I have a patch [1] that validates and gives a 3x speed up on
a benchmark. However I'd like to ask for some advise before finishing
and submitting the patch.

[1] https://github.com/takano-akio/ghc/commit/c7345c68eaa1e7f9572e693b5e352e386df7d680

The problem is that since my patch splits the weak pointer list
between generations, it no longer maintains the right order of weak
pointers. This could cause finalizers added with
addForeignPtrFinalizer to run in the wrong order.

I can think of one way to fix it; to make sure that when a WEAK object
gets promoted, it is always added to the front of the new list. So my
questions are:

- Would it be a correct fix?
- If so, is it an acceptable fix? For example, is it too fragile a
reasoning to rely on?

Thank you in advance,

Takano Akio


Reply | Threaded
Open this post in threaded view
|

Per-generation lists of weak pointers

Edward Z. Yang
I was under the impression that foreign pointers finalizers were only
ordered with respect to multiple finalizers on a single object.  So if
you can show your implementation preserves same-object ordering, that
should be sufficient. (Nota bene: I haven't CR'd your code.)

Edward

Excerpts from Akio Takano's message of Mon Mar 11 03:17:48 -0700 2013:

> Hi,
>
> I'm working on implementing per-generation lists of weak pointers to
> speed up garbage collection in programs that allocate a lot of weak
> pointers. I have a patch [1] that validates and gives a 3x speed up on
> a benchmark. However I'd like to ask for some advise before finishing
> and submitting the patch.
>
> [1] https://github.com/takano-akio/ghc/commit/c7345c68eaa1e7f9572e693b5e352e386df7d680
>
> The problem is that since my patch splits the weak pointer list
> between generations, it no longer maintains the right order of weak
> pointers. This could cause finalizers added with
> addForeignPtrFinalizer to run in the wrong order.
>
> I can think of one way to fix it; to make sure that when a WEAK object
> gets promoted, it is always added to the front of the new list. So my
> questions are:
>
> - Would it be a correct fix?
> - If so, is it an acceptable fix? For example, is it too fragile a
> reasoning to rely on?
>
> Thank you in advance,
>
> Takano Akio
>


Reply | Threaded
Open this post in threaded view
|

Per-generation lists of weak pointers

Akio Takano
Hi Edward,

Thank you for your reply!

On Mon, Mar 11, 2013 at 8:17 PM, Edward Z. Yang <ezyang at mit.edu> wrote:
> I was under the impression that foreign pointers finalizers were only
> ordered with respect to multiple finalizers on a single object.  So if
> you can show your implementation preserves same-object ordering, that
> should be sufficient. (Nota bene: I haven't CR'd your code.)

Yes I understand that. However my understanding is that
addForeignPtrFinalizer creates a fresh WEAK object with just one
finalizer. So in order to maintain the same-object ordering of C
finalizers, I still somehow need to deal with ordering between
multiple WEAK objects.

>
> Edward
>
> Excerpts from Akio Takano's message of Mon Mar 11 03:17:48 -0700 2013:
>> Hi,
>>
>> I'm working on implementing per-generation lists of weak pointers to
>> speed up garbage collection in programs that allocate a lot of weak
>> pointers. I have a patch [1] that validates and gives a 3x speed up on
>> a benchmark. However I'd like to ask for some advise before finishing
>> and submitting the patch.
>>
>> [1] https://github.com/takano-akio/ghc/commit/c7345c68eaa1e7f9572e693b5e352e386df7d680
>>
>> The problem is that since my patch splits the weak pointer list
>> between generations, it no longer maintains the right order of weak
>> pointers. This could cause finalizers added with
>> addForeignPtrFinalizer to run in the wrong order.
>>
>> I can think of one way to fix it; to make sure that when a WEAK object
>> gets promoted, it is always added to the front of the new list. So my
>> questions are:
>>
>> - Would it be a correct fix?
>> - If so, is it an acceptable fix? For example, is it too fragile a
>> reasoning to rely on?
>>
>> Thank you in advance,
>>
>> Takano Akio
>>


Reply | Threaded
Open this post in threaded view
|

Per-generation lists of weak pointers

Edward Z. Yang
Aha! That's right. It's possible, then, that foreign pointers need to
be reworked a bit, since they are relying on a weak pointer invariant
that they really shouldn't be relying on.  I think Simon Marlow would
have better guidance here.

Edward

Excerpts from Akio Takano's message of Mon Mar 11 05:15:23 -0700 2013:

> Hi Edward,
>
> Thank you for your reply!
>
> On Mon, Mar 11, 2013 at 8:17 PM, Edward Z. Yang <ezyang at mit.edu> wrote:
> > I was under the impression that foreign pointers finalizers were only
> > ordered with respect to multiple finalizers on a single object.  So if
> > you can show your implementation preserves same-object ordering, that
> > should be sufficient. (Nota bene: I haven't CR'd your code.)
>
> Yes I understand that. However my understanding is that
> addForeignPtrFinalizer creates a fresh WEAK object with just one
> finalizer. So in order to maintain the same-object ordering of C
> finalizers, I still somehow need to deal with ordering between
> multiple WEAK objects.
>
> >
> > Edward
> >
> > Excerpts from Akio Takano's message of Mon Mar 11 03:17:48 -0700 2013:
> >> Hi,
> >>
> >> I'm working on implementing per-generation lists of weak pointers to
> >> speed up garbage collection in programs that allocate a lot of weak
> >> pointers. I have a patch [1] that validates and gives a 3x speed up on
> >> a benchmark. However I'd like to ask for some advise before finishing
> >> and submitting the patch.
> >>
> >> [1] https://github.com/takano-akio/ghc/commit/c7345c68eaa1e7f9572e693b5e352e386df7d680
> >>
> >> The problem is that since my patch splits the weak pointer list
> >> between generations, it no longer maintains the right order of weak
> >> pointers. This could cause finalizers added with
> >> addForeignPtrFinalizer to run in the wrong order.
> >>
> >> I can think of one way to fix it; to make sure that when a WEAK object
> >> gets promoted, it is always added to the front of the new list. So my
> >> questions are:
> >>
> >> - Would it be a correct fix?
> >> - If so, is it an acceptable fix? For example, is it too fragile a
> >> reasoning to rely on?
> >>
> >> Thank you in advance,
> >>
> >> Takano Akio
> >>


Reply | Threaded
Open this post in threaded view
|

Per-generation lists of weak pointers

Simon Marlow-7
In reply to this post by Akio Takano
On 11/03/13 03:17, Akio Takano wrote:

> Hi,
>
> I'm working on implementing per-generation lists of weak pointers to
> speed up garbage collection in programs that allocate a lot of weak
> pointers. I have a patch [1] that validates and gives a 3x speed up on
> a benchmark. However I'd like to ask for some advise before finishing
> and submitting the patch.
>
> [1] https://github.com/takano-akio/ghc/commit/c7345c68eaa1e7f9572e693b5e352e386df7d680
>
> The problem is that since my patch splits the weak pointer list
> between generations, it no longer maintains the right order of weak
> pointers. This could cause finalizers added with
> addForeignPtrFinalizer to run in the wrong order.
>
> I can think of one way to fix it; to make sure that when a WEAK object
> gets promoted, it is always added to the front of the new list. So my
> questions are:
>
> - Would it be a correct fix?
> - If so, is it an acceptable fix? For example, is it too fragile a
> reasoning to rely on?

I don't like the way that we rely on the ordering of the weak pointer
list right now.  I think this invariant arose accidentally when the
support for C finalizers was added.  It was wrong for some time, see:

http://hackage.haskell.org/trac/ghc/ticket/7160

and as per my comments in that commit log, I think we should do it
differently.  I don't know how hard that would be though.

Incidentally, I implemented per-generation weak pointers in the local-gc
branch, but didn't get around to porting it back over into the mainline
(I still have a ToDo for that).  My version probably has the ordering
bug, but you could always look at the branch to see how my approach
compares to yours.

Cheers,
        Simon



Reply | Threaded
Open this post in threaded view
|

Per-generation lists of weak pointers

Akio Takano
I removed the invariant by adding a new primop, addCFinalizerToWeak#. I
opened a ticket for the issue.

http://hackage.haskell.org/trac/ghc/ticket/7847

- Akio


On Thu, Mar 21, 2013 at 2:40 PM, Simon Marlow <marlowsd at gmail.com> wrote:

> On 11/03/13 03:17, Akio Takano wrote:
>
>> Hi,
>>
>> I'm working on implementing per-generation lists of weak pointers to
>> speed up garbage collection in programs that allocate a lot of weak
>> pointers. I have a patch [1] that validates and gives a 3x speed up on
>> a benchmark. However I'd like to ask for some advise before finishing
>> and submitting the patch.
>>
>> [1] https://github.com/takano-**akio/ghc/commit/**
>> c7345c68eaa1e7f9572e693b5e352e**386df7d680<https://github.com/takano-akio/ghc/commit/c7345c68eaa1e7f9572e693b5e352e386df7d680>
>>
>> The problem is that since my patch splits the weak pointer list
>> between generations, it no longer maintains the right order of weak
>> pointers. This could cause finalizers added with
>> addForeignPtrFinalizer to run in the wrong order.
>>
>> I can think of one way to fix it; to make sure that when a WEAK object
>> gets promoted, it is always added to the front of the new list. So my
>> questions are:
>>
>> - Would it be a correct fix?
>> - If so, is it an acceptable fix? For example, is it too fragile a
>> reasoning to rely on?
>>
>
> I don't like the way that we rely on the ordering of the weak pointer list
> right now.  I think this invariant arose accidentally when the support for
> C finalizers was added.  It was wrong for some time, see:
>
> http://hackage.haskell.org/**trac/ghc/ticket/7160<http://hackage.haskell.org/trac/ghc/ticket/7160>
>
> and as per my comments in that commit log, I think we should do it
> differently.  I don't know how hard that would be though.
>
> Incidentally, I implemented per-generation weak pointers in the local-gc
> branch, but didn't get around to porting it back over into the mainline (I
> still have a ToDo for that).  My version probably has the ordering bug, but
> you could always look at the branch to see how my approach compares to
> yours.
>
> Cheers,
>         Simon
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20130419/c0dd0ea4/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

Per-generation lists of weak pointers

Akio Takano
Thank you very much for your help, I just updated the patches on the ticket.


On Sun, Apr 21, 2013 at 10:50 AM, Edward Z. Yang <ezyang at cs.stanford.edu>wrote:

> In your ticket, you mention this patch introduces a race condition.  One
> possible fix is to have addCFinalizerToWeak# check if the pointer is
> already
> dead, and just run the finalizer immediately if it is.  I think this
> preserves the semantics, but this needs to be checked closely.
>
> Edward
>
> Excerpts from Akio Takano's message of Fri Apr 19 02:58:50 -0700 2013:
> > I removed the invariant by adding a new primop, addCFinalizerToWeak#. I
> > opened a ticket for the issue.
> >
> > http://hackage.haskell.org/trac/ghc/ticket/7847
> >
> > - Akio
> >
> > On Thu, Mar 21, 2013 at 2:40 PM, Simon Marlow <marlowsd at gmail.com>
> wrote:
> >
> > > On 11/03/13 03:17, Akio Takano wrote:
> > >
> > >> Hi,
> > >>
> > >> I'm working on implementing per-generation lists of weak pointers to
> > >> speed up garbage collection in programs that allocate a lot of weak
> > >> pointers. I have a patch [1] that validates and gives a 3x speed up on
> > >> a benchmark. However I'd like to ask for some advise before finishing
> > >> and submitting the patch.
> > >>
> > >> [1] https://github.com/takano-**akio/ghc/commit/**
> > >> c7345c68eaa1e7f9572e693b5e352e**386df7d680<
> https://github.com/takano-akio/ghc/commit/c7345c68eaa1e7f9572e693b5e352e386df7d680
> >
> > >>
> > >> The problem is that since my patch splits the weak pointer list
> > >> between generations, it no longer maintains the right order of weak
> > >> pointers. This could cause finalizers added with
> > >> addForeignPtrFinalizer to run in the wrong order.
> > >>
> > >> I can think of one way to fix it; to make sure that when a WEAK object
> > >> gets promoted, it is always added to the front of the new list. So my
> > >> questions are:
> > >>
> > >> - Would it be a correct fix?
> > >> - If so, is it an acceptable fix? For example, is it too fragile a
> > >> reasoning to rely on?
> > >>
> > >
> > > I don't like the way that we rely on the ordering of the weak pointer
> list
> > > right now.  I think this invariant arose accidentally when the support
> for
> > > C finalizers was added.  It was wrong for some time, see:
> > >
> > > http://hackage.haskell.org/**trac/ghc/ticket/7160<
> http://hackage.haskell.org/trac/ghc/ticket/7160>
> > >
> > > and as per my comments in that commit log, I think we should do it
> > > differently.  I don't know how hard that would be though.
> > >
> > > Incidentally, I implemented per-generation weak pointers in the
> local-gc
> > > branch, but didn't get around to porting it back over into the
> mainline (I
> > > still have a ToDo for that).  My version probably has the ordering
> bug, but
> > > you could always look at the branch to see how my approach compares to
> > > yours.
> > >
> > > Cheers,
> > >         Simon
> > >
> > >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20130424/85f0746b/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

Per-generation lists of weak pointers

Akio Takano
Thank you for your comments!

On Wed, Apr 24, 2013 at 8:23 PM, Edward Z. Yang <ezyang at cs.stanford.edu>wrote:

> Great, good to see.
>
> Some questions:
>
> - You seem to be stubbing out cfinalizers with stg_WEAK_IS_DEAD_closure
>   when a weak pointer gets finalized; your locking is predicated on
>   operations on this field being cas'es.  Another design is to lock
>   the closure itself, via the info table header (using lockClosure).
>   I think both strategies should be sound, but I suspect lockClosure
>   is bound to be safer, in case you end up mutating other fields.
>

You are right, I updated the patches to use lockClosure. I was not aware of
the existence of lockClosure when I wrote the previous patches, which is
why I used cas().


> - Typo "Kill a weak poitner"
>

Now the comment is gone.


> - There was a comment about LDV which was removed. Why is that comment
>   irrelevant in the new world order?
>

In that version of the patches finalizeWeak# didn't modify the infoptr, so
the comment didn't apply. It is back in the latest version of the patches,
though.


>
> Edward
>
> Excerpts from Akio Takano's message of Wed Apr 24 02:12:42 -0700 2013:
> > Thank you very much for your help, I just updated the patches on the
> ticket.
> >
> > On Sun, Apr 21, 2013 at 10:50 AM, Edward Z. Yang <ezyang at cs.stanford.edu
> >wrote:
> >
> > > In your ticket, you mention this patch introduces a race condition.
>  One
> > > possible fix is to have addCFinalizerToWeak# check if the pointer is
> > > already
> > > dead, and just run the finalizer immediately if it is.  I think this
> > > preserves the semantics, but this needs to be checked closely.
> > >
> > > Edward
> > >
> > > Excerpts from Akio Takano's message of Fri Apr 19 02:58:50 -0700 2013:
> > > > I removed the invariant by adding a new primop,
> addCFinalizerToWeak#. I
> > > > opened a ticket for the issue.
> > > >
> > > > http://hackage.haskell.org/trac/ghc/ticket/7847
> > > >
> > > > - Akio
> > > >
> > > > On Thu, Mar 21, 2013 at 2:40 PM, Simon Marlow <marlowsd at gmail.com>
> > > wrote:
> > > >
> > > > > On 11/03/13 03:17, Akio Takano wrote:
> > > > >
> > > > >> Hi,
> > > > >>
> > > > >> I'm working on implementing per-generation lists of weak pointers
> to
> > > > >> speed up garbage collection in programs that allocate a lot of
> weak
> > > > >> pointers. I have a patch [1] that validates and gives a 3x speed
> up on
> > > > >> a benchmark. However I'd like to ask for some advise before
> finishing
> > > > >> and submitting the patch.
> > > > >>
> > > > >> [1] https://github.com/takano-**akio/ghc/commit/**
> > > > >> c7345c68eaa1e7f9572e693b5e352e**386df7d680<
> > >
> https://github.com/takano-akio/ghc/commit/c7345c68eaa1e7f9572e693b5e352e386df7d680
> > > >
> > > > >>
> > > > >> The problem is that since my patch splits the weak pointer list
> > > > >> between generations, it no longer maintains the right order of
> weak
> > > > >> pointers. This could cause finalizers added with
> > > > >> addForeignPtrFinalizer to run in the wrong order.
> > > > >>
> > > > >> I can think of one way to fix it; to make sure that when a WEAK
> object
> > > > >> gets promoted, it is always added to the front of the new list.
> So my
> > > > >> questions are:
> > > > >>
> > > > >> - Would it be a correct fix?
> > > > >> - If so, is it an acceptable fix? For example, is it too fragile a
> > > > >> reasoning to rely on?
> > > > >>
> > > > >
> > > > > I don't like the way that we rely on the ordering of the weak
> pointer
> > > list
> > > > > right now.  I think this invariant arose accidentally when the
> support
> > > for
> > > > > C finalizers was added.  It was wrong for some time, see:
> > > > >
> > > > > http://hackage.haskell.org/**trac/ghc/ticket/7160<
> > > http://hackage.haskell.org/trac/ghc/ticket/7160>
> > > > >
> > > > > and as per my comments in that commit log, I think we should do it
> > > > > differently.  I don't know how hard that would be though.
> > > > >
> > > > > Incidentally, I implemented per-generation weak pointers in the
> > > local-gc
> > > > > branch, but didn't get around to porting it back over into the
> > > mainline (I
> > > > > still have a ToDo for that).  My version probably has the ordering
> > > bug, but
> > > > > you could always look at the branch to see how my approach
> compares to
> > > > > yours.
> > > > >
> > > > > Cheers,
> > > > >         Simon
> > > > >
> > > > >
> > >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20130425/3ec5b827/attachment-0001.htm>

Reply | Threaded
Open this post in threaded view
|

Per-generation lists of weak pointers

Simon Marlow-7
I haven't got around to looking at this, but I see Edward is on the case
with some code review.  Do you think I should look at it before it goes in?

Cheers,
        Simon


On 01/05/13 23:02, Edward Z. Yang wrote:

> Thanks for being patient.
>
> I think there is still a race condition for finalizeWeak and addCFinalizer.
> The race goes as follows:
>
>      finalizeWeak: lockClosure
>      finalizeWeak: unlockClosure - weak pointer is now dead
>      addCFinalizer: lockClosure
>      addCFinalizer: weak pointer is already dead!
>      addCFinalizer: unlockClosure
>      addCFinalizer: run newest finalizer
>      finalizeWeak: run list of finalizers
>
> However, addCFinalizer's finalizer should be run after the list.
>
> The obvious fix is to keep the closure locked until all the finalizers
> are done running, but maybe there is something more clever you can do
> to avoid having to have the lock taken out while runnig arbitrary C code.
>
> Minor style nits:
>
>      - Why isn't the type: runCFinalizers(StgCFinalizerList*)?  (Yes, a
>        stg_NO_FINALIZER_closure is not a StgCFinalizerList, but it should
>        be treated as a "null" type value; see END_TSO_QUEUE in includes/rts/storage/TSO.h
>        for an example).
>      - I don't think finalizer lists will ever be tagged, so it should
>        not be necessary to untag them. (Tagging wouldn't help, because
>        the only other "constructor" is stg_NO_FINALIZER_closure, which is
>        static so we can test for it using a pointer comparison).
>      - Some of your w != NULL tests are abbreviated to just w; I think we
>        prefer to have the explicit '!= NULL' afterwards
>      - You can probably add some ASSERTs for the linked list manipulation
>        in collectDeadWeakPtrs (e.g.  ASSERT(dead_weak_ptrt_list_tail !=
>        NULL) in the latter conditional branch)
>      - In tidyWeakList, you have 'new_gen = Bdescr((P_)w)->gen;' A brief
>        comment about what this is doing would be good (it is the primary
>        semantic change for the algorithm from the old version)
>
> The rest looks good; after it validates I'll be happy to push.
>
> Cheers,
> Edward
>
> Excerpts from Akio Takano's message of Thu Apr 25 03:42:10 -0700 2013:
>> Thank you for your comments!
>>
>> On Wed, Apr 24, 2013 at 8:23 PM, Edward Z. Yang <ezyang at cs.stanford.edu>wrote:
>>
>>> Great, good to see.
>>>
>>> Some questions:
>>>
>>> - You seem to be stubbing out cfinalizers with stg_WEAK_IS_DEAD_closure
>>>    when a weak pointer gets finalized; your locking is predicated on
>>>    operations on this field being cas'es.  Another design is to lock
>>>    the closure itself, via the info table header (using lockClosure).
>>>    I think both strategies should be sound, but I suspect lockClosure
>>>    is bound to be safer, in case you end up mutating other fields.
>>>
>>
>> You are right, I updated the patches to use lockClosure. I was not aware of
>> the existence of lockClosure when I wrote the previous patches, which is
>> why I used cas().
>>
>>> - Typo "Kill a weak poitner"
>>>
>>
>> Now the comment is gone.
>>
>>> - There was a comment about LDV which was removed. Why is that comment
>>>    irrelevant in the new world order?
>>>
>>
>> In that version of the patches finalizeWeak# didn't modify the infoptr, so
>> the comment didn't apply. It is back in the latest version of the patches,
>> though.
>>
>>>
>>> Edward
>>>
>>> Excerpts from Akio Takano's message of Wed Apr 24 02:12:42 -0700 2013:
>>>> Thank you very much for your help, I just updated the patches on the
>>> ticket.
>>>>
>>>> On Sun, Apr 21, 2013 at 10:50 AM, Edward Z. Yang <ezyang at cs.stanford.edu
>>>> wrote:
>>>>
>>>>> In your ticket, you mention this patch introduces a race condition.
>>>   One
>>>>> possible fix is to have addCFinalizerToWeak# check if the pointer is
>>>>> already
>>>>> dead, and just run the finalizer immediately if it is.  I think this
>>>>> preserves the semantics, but this needs to be checked closely.
>>>>>
>>>>> Edward
>>>>>
>>>>> Excerpts from Akio Takano's message of Fri Apr 19 02:58:50 -0700 2013:
>>>>>> I removed the invariant by adding a new primop,
>>> addCFinalizerToWeak#. I
>>>>>> opened a ticket for the issue.
>>>>>>
>>>>>> http://hackage.haskell.org/trac/ghc/ticket/7847
>>>>>>
>>>>>> - Akio
>>>>>>
>>>>>> On Thu, Mar 21, 2013 at 2:40 PM, Simon Marlow <marlowsd at gmail.com>
>>>>> wrote:
>>>>>>
>>>>>>> On 11/03/13 03:17, Akio Takano wrote:
>>>>>>>
>>>>>>>> Hi,
>>>>>>>>
>>>>>>>> I'm working on implementing per-generation lists of weak pointers
>>> to
>>>>>>>> speed up garbage collection in programs that allocate a lot of
>>> weak
>>>>>>>> pointers. I have a patch [1] that validates and gives a 3x speed
>>> up on
>>>>>>>> a benchmark. However I'd like to ask for some advise before
>>> finishing
>>>>>>>> and submitting the patch.
>>>>>>>>
>>>>>>>> [1] https://github.com/takano-**akio/ghc/commit/**
>>>>>>>> c7345c68eaa1e7f9572e693b5e352e**386df7d680<
>>>>>
>>> https://github.com/takano-akio/ghc/commit/c7345c68eaa1e7f9572e693b5e352e386df7d680
>>>>>>
>>>>>>>>
>>>>>>>> The problem is that since my patch splits the weak pointer list
>>>>>>>> between generations, it no longer maintains the right order of
>>> weak
>>>>>>>> pointers. This could cause finalizers added with
>>>>>>>> addForeignPtrFinalizer to run in the wrong order.
>>>>>>>>
>>>>>>>> I can think of one way to fix it; to make sure that when a WEAK
>>> object
>>>>>>>> gets promoted, it is always added to the front of the new list.
>>> So my
>>>>>>>> questions are:
>>>>>>>>
>>>>>>>> - Would it be a correct fix?
>>>>>>>> - If so, is it an acceptable fix? For example, is it too fragile a
>>>>>>>> reasoning to rely on?
>>>>>>>>
>>>>>>>
>>>>>>> I don't like the way that we rely on the ordering of the weak
>>> pointer
>>>>> list
>>>>>>> right now.  I think this invariant arose accidentally when the
>>> support
>>>>> for
>>>>>>> C finalizers was added.  It was wrong for some time, see:
>>>>>>>
>>>>>>> http://hackage.haskell.org/**trac/ghc/ticket/7160<
>>>>> http://hackage.haskell.org/trac/ghc/ticket/7160>
>>>>>>>
>>>>>>> and as per my comments in that commit log, I think we should do it
>>>>>>> differently.  I don't know how hard that would be though.
>>>>>>>
>>>>>>> Incidentally, I implemented per-generation weak pointers in the
>>>>> local-gc
>>>>>>> branch, but didn't get around to porting it back over into the
>>>>> mainline (I
>>>>>>> still have a ToDo for that).  My version probably has the ordering
>>>>> bug, but
>>>>>>> you could always look at the branch to see how my approach
>>> compares to
>>>>>>> yours.
>>>>>>>
>>>>>>> Cheers,
>>>>>>>          Simon
>>>>>>>
>>>>>>>
>>>>>
>>>



Reply | Threaded
Open this post in threaded view
|

Per-generation lists of weak pointers

Akio Takano
On Sat, May 4, 2013 at 8:50 AM, Edward Z. Yang <ezyang at cs.stanford.edu>wrote:

> Akio, your derefWeak WHITEHOLE fix looks really weird. I don't
> know what the right pattern is, but it seems like asking for trouble
> when there are multiple concurrent derefs:
>
>     if (info == stg_WHITEHOLE_info) {
>       ("ptr" info) = ccall lockClosure(w "ptr");
>        unlockClosure(w, info);
>     }
>
>
I don't see what the problem is, could you elaborate?

The purpose of the fix was to prevent a sequence like this:

- w is a dead weak pointer.
- Thread A: finalizeWeak# w.
- Thread A: finalizeWeak#  calls lockClosure(w), overwriting w->info with
stg_WHITEHOLE_info.
- Thread B: deRefWeak# w
- Thread B: deRefWeak# sees stg_WHITEHOLE_info, and since it's not the same
as stg_DEAD_WEAK_info, it thinks w is alive.

The problem was that if deRefWeak# saw stg_WHITEHOLE_info, it was not clear
whether the weak pointer was alive or not. So my fix adds a call to
lockClosure, which never returns stg_WHITEHOLE_info.


> > addForeignPtrFinalizer retries in this case.
>
> This can't be right; a dead weak pointer always stays dead, so won't
> this infinite loop?
>

No. When addForeignPtrFinalizer retries, it will use a new Weak# object,
because foreignPtrFinalizer must have been replaced the content of the
IORef.


>
> > I haven't got around to looking at this, but I see Edward is on the case
> > with some code review.  Do you think I should look at it before it goes
> in?
>
> Now you're asking for it :)  I would always be interested in seeing if I
> missed anything.
>
> Cheers,
> Edward
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20130505/c215f4c6/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

Per-generation lists of weak pointers

Simon Marlow-7
Akio, I looked at your first patch, which mostly seems good.  The
sequence at the beginning of deRefWeak certainly looks strange - I think
it's ok, but it needs a comment.

One thing I'm confused about is the handling of DEAD_WEAK pointers.  You
removed the StgDeadWeak struct - how is that possible?  I don't
understand why DEAD_WEAK has 4 payload words, but StgDeadWeak has only
one, and furthermore a DEAD_WEAK appears to have the link field in a
different place from the WEAK closure.  Something is suspicious here.

Cheers,
        Simon



Reply | Threaded
Open this post in threaded view
|

Per-generation lists of weak pointers

Akio Takano
In reply to this post by Akio Takano
Thank you for your comments, I updated the patches on the ticket (comment
changes only).

http://hackage.haskell.org/trac/ghc/ticket/7847


On Sun, May 5, 2013 at 7:50 PM, Edward Z. Yang <ezyang at cs.stanford.edu>wrote:

> > The purpose of the fix was to prevent a sequence like this:
> >
> > - w is a dead weak pointer.
> > - Thread A: finalizeWeak# w.
> > - Thread A: finalizeWeak#  calls lockClosure(w), overwriting w->info with
> > stg_WHITEHOLE_info.
> > - Thread B: deRefWeak# w
> > - Thread B: deRefWeak# sees stg_WHITEHOLE_info, and since it's not the
> same
> > as stg_DEAD_WEAK_info, it thinks w is alive.
> >
> > The problem was that if deRefWeak# saw stg_WHITEHOLE_info, it was not
> clear
> > whether the weak pointer was alive or not. So my fix adds a call to
> > lockClosure, which never returns stg_WHITEHOLE_info.
>
> OK, but you should add a comment about what this code is doing.
>

Done.


> (You will also unnecessarily lock when GET_INFO snags a transient
> whitehole),
>

> > > > addForeignPtrFinalizer retries in this case.
> > >
> > > This can't be right; a dead weak pointer always stays dead, so won't
> > > this infinite loop?
> > >
> >
> > No. When addForeignPtrFinalizer retries, it will use a new Weak# object,
> > because foreignPtrFinalizer must have been replaced the content of the
> > IORef.
>
> Sorry, I still don't understand. Tracing the code execution, no change
> is made to the IORef when Finalizers is CFinalizers?
>

When addCFinalizerToWeak fails, some other thread must have called
foreignPtrFinalizer, and it must have replaced the content of the IORef
before calling finalizeWeak#. I updated the comment to mention this logic.


>
> Edward
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20130506/26d0855e/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

Per-generation lists of weak pointers

Akio Takano
In reply to this post by Simon Marlow-7
Thank you for your comments.


On Mon, May 6, 2013 at 4:32 AM, Simon Marlow <marlowsd at gmail.com> wrote:

> Akio, I looked at your first patch, which mostly seems good.  The sequence
> at the beginning of deRefWeak certainly looks strange - I think it's ok,
> but it needs a comment.
>

I update my patches and added a comment to that part.


>
> One thing I'm confused about is the handling of DEAD_WEAK pointers.  You
> removed the StgDeadWeak struct - how is that possible?  I don't understand
> why DEAD_WEAK has 4 payload words, but StgDeadWeak has only one, and
> furthermore a DEAD_WEAK appears to have the link field in a different place
> from the WEAK closure.  Something is suspicious here.
>

Before my patch, dead weak pointers had the same size as live ones,  but
they had the link field in different places.

With my patch, dead weak pointers have the same layout as live ones, so
they can be accessed with the single StgWeak struct. The only differences
between live and dead weak pointers now are the info pointer, and whether
the "cfinalizers" field is followed by the GC. The code is simplified a bit
because it doesn't need to deal with two different layouts.

I think I needed this change in order to keep finalizeWeak# atomic, but now
that I use lockClosure() to ensure atomicity, probably I can remove this
change from the patch. Should I do so?

- Akio



>
> Cheers,
>         Simon
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20130506/ffa2ed66/attachment.htm>