Per-generation lists of weak pointers

Simon Marlow marlowsd at gmail.com
Fri May 3 13:04:13 CEST 2013 

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
>>>>>>>
>>>>>>>
>>>>>
>>>

More information about the ghc-devs mailing list