Re: [Vala] Gee RFC: Hazard pointers



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




[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]