Re: [Vala] Gee RFC: Hazard pointers

[Maciej Marcin Piechotka <uzytkownik2 gmail com>]

On Sun, 2011-09-04 at 19:59 +0100, Maciej Marcin Piechotka wrote:
> As I slowly prepare for 0.7.1 release I have some good news. After
> talking to Jürg during Desktop Summit bug blocking the support for lock
> free collections have been solved. It means that they will be in 0.8 (I
> hope I will port patches I currently have over September).
>
> Vala however does not have atomic garbage collection and hence the
> hazard pointers are needed to be employed. In short - when thread
> deletes an element it checks if the element is used by other thread. If
> this is the case it refrain from deleting it and frees the memory later
> on (in vala case it is usually unref'ing object).
>
> However the scheme assumes that single thread checks the list from time
> to time. It poses 2 problems:
>
> 1. What to do when thread finishes?
> 2. What to do if thread frees a lot of memory (still in use by other
> threads) and continue without calling lock-free collection methods?
>
> I come up with following solutions:
>
>  - Block on exit from top-most lock-free methods. It have the drawback
> of effectivly blocking the thread until other threads move on hence
> making the collection busy-waiting rather then lock-free.
>  - Block on exit from thread. It might put thread into deadlock if the
> thread joining it holds iterator pointing to deleted memory (the problem
> present previously). 
>  - Spawn special thread (use glib main loop IDLE) to handle the freeing
> elements after exit from thread using blocking queue
>  - Spawn special thread (use glib main loop IDLE) to handle the freeing
> elements after exit from top-most lock-free method.
>  - Add API to allow fine-tuning:
>
> HazardPointer.try_free();
> HazardPointer.free(); // may block
> HazardPointer.release(); // Puts to IDLE/helper thread blocking queue
> HazardPointer.try_release(); // As above but avoiding blocking
> HazardPointer.default(); // Behave as if the topmost lock-free method 
>                          // was exited
> HazardPointer.thread_exit(); // Behave as if the thread
>                              // was terminated
>
> + methods to override defaults.
>
> I would propose API + such defaults:
>  - try_free on exit from method
>  - release on exit from thread
>
> (+ try_free on every 'unref').
>
> Best regards

In slist branch on gitorious[1] the hazard pointer and concurrent linked
list implementation are pushed. Please note that they are under heavy
bug fixing and are not passing tests.

However if anyone would like to comment about API please do so. I hope
that there will be 0.7.1 release after polishing the code.

Regards

[1]
http://gitorious.org/~uzytkownik/libgee/mpiechotkas-libgee/commits/slist