Question about vZOOM reference handling
Dmitriy Vyukov
<cristom_nospam@comcast._nospam_net> wrote:
> I have a solution for this that uses %99.99 POSIX mutexs; only relies on
> dependent load ordering. I will now briefly describe how the garbage
> collection part of my solution works:
>
> - Each thread has two mutexs ( owner_lock, memory_lock ) an array of
> persistent reference counters (prefs[] ), a synchronization state
> variable ( sync_state ), and a list of deferred objects ( my_defer ).
>
> - A polling thread has a condition variable ( poll_cond ), a mutex (
> poll_lock ), a list of registered threads ( treg ) and three lists of
> deferred objects ( new_defer, old_defer, final_defer )
>
> - Each thread that registers with the polling thread shall lock the
> poll_lock; "lock memory_lock"; push itself onto treg; unlock poll_lock
> and signal poll_cond.
>
> - Each thread that unregisters with the polling thread shall lock the
> poll_lock; "unlock memory_lock"; pop itself from treg; move my_defer to
> the polling threads new_defer; unlock poll_lock and signal poll_cond.
>
> - A registered thread is supposed to periodically or episodically
> execute a synchronization operation. This can be achieved by locking the
> owner_lock; unlocking the memory_lock; set a flag in sync_state; lock
> the memory_lock and finally unlock the owner_lock. When the thread
> "unlocks and subsequently locks" the memory_mutex "inside of the
> owner_locks critical region" it has the effect of making the critical
> section that was protected by memory_mutex "visible to the polling
> thread". All of the modifications to theprefs[] array are carried out
> under the critical section of the memory_mutex because it is "always
> locked", except for "explicit synchronization".
>
> - A registered thread acquires persistent references to an object by
> loading a pointer to object; dependent load barrier; hash pointer to
> object into index; the indexed counter inprefs[] is incremented.
>
> - A registered thread releases persistent references to an object by
> hashing a previously acquired object into an index; the indexed counter
> inprefs[] is decremented.
>
> - A registered thread defers an object by making it unreachable and
> queuing it into my_defer.
>
> - The polling thread periodically or episodically checks to see if each
> registered thread has executed a synchronization operation. This is
> achieved by waiting on poll_cond for the desired polling interval. When
> its time to poll it iterates through treg and for each thread: lock
> owner_lock; examining the sync_state variable for a flag; if the flag is
> set continue, if not unlock previously acquired owner_locks and wait for
> another polling interval.
>
> - After the polling thread has determined that all of the threads have
> executed a synchronization then it resets the sync_state flag of each
> thread and unlocks all previously acquired owner_locks; It is now
> guaranteed that all "previous effects" on theprefs[] arrays "since the
> last synchronization" are "fully visible". It then calls the deferred
> requests that exist in final_defer and empties it; swaps new_defer with
> old_defer; collects a new generation of deferred requests from my_defer
> in all registered threads into new_defer; checks the old_defer list
> against each threadsprefs[] array. If a old deferred request is not
> found to have any persistent references, it is then moved into a the
> final_defer list. Then another polling interval is waited for.
---------------------------------------------------------------
Original post:
http://groups.google.ru/group/comp.programming.threads/msg/59e9b6e427b4a144
---------------------------------------------------------------
Question particularly about this statement:
"checks the old_defer list against each threads prefs[] array"
As I understand particular cell in prefs[] contain sum of references
for objects that hash to that cell. So how can you check object in
old_defer list against prefs[] array? Are you check that
(prefs[hash(object)] == 0)?
But for example if I have 1'000'000 objects and size of prefs is
1'000, so it is 1000 objects per cell in prefs[]. Every particular
cell in prefs[] can not drop to zero at all. Or it can drop to zero
very infrequently...
What I miss?
Dmitriy V'jukov
Chris Thomasson
news:1181038651....@o5g2000hsb.googlegroups.com...
> On 18 мар 2006, 02:06, Chris Thomasson
> <cristom_nospam@comcast._nospam_net> wrote:
> ---------------------------------------------------------------
>
> Original post:
> http://groups.google.ru/group/comp.programming.threads/msg/59e9b6e427b4a144
>
> ---------------------------------------------------------------
>
> Question particularly about this statement:
>
> "checks the old_defer list against each threads prefs[] array"
> As I understand particular cell in prefs[] contain sum of references
> for objects that hash to that cell.
Right.
> So how can you check object in
> old_defer list against prefs[] array? Are you check that
> (prefs[hash(object)] == 0)?
Yes.
> But for example if I have 1'000'000 objects and size of prefs is
> 1'000, so it is 1000 objects per cell in prefs[].
That would be:
#define HASH_DEPTH() 1000
struct per_thread_s {
unsigned long prefs[HASH_DEPTH()];
};
> Every particular
> cell in prefs[] can not drop to zero at all. Or it can drop to zero
> very infrequently...
> What I miss?
Each cell in prefs can handle ULONG_MAX references.
So, if object A hashes to cell B... Well, cell B can contain ULONG_MAX
references of object A.
If objects B-F hash to cell C, then cell C can contain ULONG_MAX references
of objects B-F combined.
Does that address some of you concerns at all?
Dmitriy Vyukov
> Each cell in prefs can handle ULONG_MAX references.
>
> So, if object A hashes to cell B... Well, cell B can contain ULONG_MAX
> references of object A.
>
> If objects B-F hash to cell C, then cell C can contain ULONG_MAX references
> of objects B-F combined.
>
> Does that address some of you concerns at all?
Not, I mean different thing.
If objects obj1 - obj1000 hash to cell A, and new objects continuously
appers that hash to cell A too. Can't I get situation, when counter in
cell A doesn't drop to zero at all?
Dmitriy V'jukov
Dmitriy Vyukov
> Not, I mean different thing.
I mean what you write here:
http://groups.google.ru/group/comp.programming.threads/msg/97c7014ef64deea9
So you propose to make hash table size around 100'000 elements...
hmm... 400kb... So it is acceptably provided thread's stack 1Mb.
I think such size of hash table solve the problem I am talking about.
Dmitriy V'jukov
Chris Thomasson
Yes, if your program is consistently and rapidly acquiring tons of
persistent references, and the hash-collisions happen to execute in the
order your described.
BTW, thanks for taking the time to look at the algorithm.
Chris Thomasson
> On 5 июн, 15:01, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
>
>> Not, I mean different thing.
>
> I mean what you write here:
> http://groups.google.ru/group/comp.programming.threads/msg/97c7014ef64deea9
>
> So you propose to make hash table size around 100'000 elements...
> hmm... 400kb... So it is acceptably provided thread's stack 1Mb.
Also, I think its good to keep in mind that the per-thread structures could
be allocated on the heap instead of the stack; I guess it would be an
implementation detail.
> I think such size of hash table solve the problem I am talking about.
I do believe it would drastically reduce the possibility, and perhaps couple
that with a hashing algorithm that was a little bit "smart", well, that
would help things out even further...
Again, thanks for your interest Dmitriy.
Dmitriy Vyukov
One more question.
Consider next situation. Message-passing system. Producer creates
message. Then producer put this message to two different producer-
consumer message queues which go to two different consumer threads.
When message will be consumed by both threads, it must be deleted.
Can vZOOM handle lifetime management of the message?
It seems for me that the answer will be NO.
As far as I see vZOOM can handle only "weak" references, and for
"strong" references one must use reference-counting anyway.
Another situation.
Graph structure where to node can point several other nodes. And this
links are removed not all at once by one thread, but one by one by
different threads.
Can vZOOM handle lifetime management of the node in graph?
It seems that threads that remove links to node must use reference-
counting. But vZOOM still can be used here for readers.
Am I right?
Dmitriy V'jukov
Joe Seigh
> On Jun 5, 2:17 pm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
>
> One more question.
> Consider next situation. Message-passing system. Producer creates
> message. Then producer put this message to two different producer-
> consumer message queues which go to two different consumer threads.
> When message will be consumed by both threads, it must be deleted.
>
> Can vZOOM handle lifetime management of the message?
>
> It seems for me that the answer will be NO.
If you can use a multi-tailed fifo queue instead of 2 different
queues. Make the queue backward linked and use PDR to keep
track of when to free the nodes. The readers will be lock-free.
>
> As far as I see vZOOM can handle only "weak" references, and for
> "strong" references one must use reference-counting anyway.
>
>
> Another situation.
> Graph structure where to node can point several other nodes. And this
> links are removed not all at once by one thread, but one by one by
> different threads.
> Can vZOOM handle lifetime management of the node in graph?
> It seems that threads that remove links to node must use reference-
> counting. But vZOOM still can be used here for readers.
>
> Am I right?
>
>
vZOOM and other forms of PDR are mainly useful in read lock-free
reader/writer solutions. Writers can be lock-free as long as you
have some form of multi-word compare and swap. Usually it's easier
to just use a lock on the writer side. And since the readers don't
need to perform any locking, the lock contention is likely to be
low enough to keep the lock uncontended most of the time and
uncontended locks are pretty efficient. The trick is keeping
contention low.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
Dmitriy Vyukov
> > Can vZOOM handle lifetime management of the message?
> > It seems for me that the answer will be NO.
>
> If you can use a multi-tailed fifo queue instead of 2 different
> queues.
What is "multi-tailed fifo queue"?
I mean messaging system where threads are fully connected with queues.
So every arbitrary thread can pass message to every arbitrary set of
other threads...
> Make the queue backward linked and use PDR to keep
> track of when to free the nodes.
I don't understand...
> > Another situation.
> > Graph structure where to node can point several other nodes. And this
> > links are removed not all at once by one thread, but one by one by
> > different threads.
> > Can vZOOM handle lifetime management of the node in graph?
> > It seems that threads that remove links to node must use reference-
> > counting. But vZOOM still can be used here for readers.
> > Am I right?
>
> vZOOM and other forms of PDR are mainly useful in read lock-free
> reader/writer solutions. Writers can be lock-free as long as you
> have some form of multi-word compare and swap.
???
There are solutions based on single-word CAS to lists, fifo queues,
lifo stacks, hash tables...
> Usually it's easier
> to just use a lock on the writer side.
In messaging system (that I am talking about) there are no "readers"
and "writers". All threads like "writers". Producer just need to
increment reference counter of the message and consumer just need to
decrement reference counter of the message. It solves trivially with
intrustive reference counting (just atomic_inc/atomic_dec). But
overhead is significant. So I try to understand can vZOOM handle this
kind of references and this kind of lifetime management? Or it's just
for lock-free reader pattern for data structures...
Dmitriy V'jukov
Joe Seigh
> On 6 июн, 05:51, Joe Seigh <jseigh...@xemaps.com> wrote:
>
>
>>>Can vZOOM handle lifetime management of the message?
>>>It seems for me that the answer will be NO.
>>
>>If you can use a multi-tailed fifo queue instead of 2 different
>>queues.
>
>
> What is "multi-tailed fifo queue"?
>
> I mean messaging system where threads are fully connected with queues.
> So every arbitrary thread can pass message to every arbitrary set of
> other threads...
>
>
>
>>Make the queue backward linked and use PDR to keep
>>track of when to free the nodes.
>
>
> I don't understand...
>
http://groups.google.com/group/comp.lang.java.programmer/msg/74822cb35669ea29
Ignore the second example. I was thinking Java locks had full memory
barrier semantics at the time which is wrong.
>
>
>
>>>Another situation.
>>>Graph structure where to node can point several other nodes. And this
>>>links are removed not all at once by one thread, but one by one by
>>>different threads.
>>>Can vZOOM handle lifetime management of the node in graph?
>>>It seems that threads that remove links to node must use reference-
>>>counting. But vZOOM still can be used here for readers.
>>>Am I right?
>>
>>vZOOM and other forms of PDR are mainly useful in read lock-free
>>reader/writer solutions. Writers can be lock-free as long as you
>>have some form of multi-word compare and swap.
>
>
> ???
> There are solutions based on single-word CAS to lists, fifo queues,
> lifo stacks, hash tables...
which you can count with the fingers on one hand. Other solutions
require MCAS or STM.
Dmitriy Vyukov
> Seehttp://groups.google.com/group/comp.lang.java.programmer/msg/74822cb3...
> Ignore the second example. I was thinking Java locks had full memory
> barrier semantics at the time which is wrong.
No. This don't solve the problem. Because of:
> > I mean messaging system where threads are fully connected by queues.
> > So every arbitrary thread can pass message to every arbitrary set of
> > other threads...
> > There are solutions based on single-word CAS to lists, fifo queues,
> > lifo stacks, hash tables...
> which you can count with the fingers on one hand. Other solutions
> require MCAS or STM.
But I can build all base infrastructure on solutions based on CAS
(memory management/messaging/object lifetime management).
And if someone wants red_black_hashed_double_linked_skip_balanced_tree
then he must use mutexes... :)
Dmitriy V'jukov
Chris Thomasson
news:LdudneXy0YFTjPvb...@comcast.com...
> Dmitriy Vyukov wrote:
>> On Jun 5, 2:17 pm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
>>
>> One more question.
>> Consider next situation. Message-passing system. Producer creates
>> message. Then producer put this message to two different producer-
>> consumer message queues which go to two different consumer threads.
>> When message will be consumed by both threads, it must be deleted.
>>
>> Can vZOOM handle lifetime management of the message?
First of all, PDR is not approitpratire in all scenarios. A message-passing
system really only needs basic thread safety:
http://groups.google.com/group/comp.programming.threads/msg/1b2e1c98fa9ad7c7
(refer to the latter example...)
>> It seems for me that the answer will be NO.
I could be made to work. (e.g., Joe Seighs example)
>> As far as I see vZOOM can handle only "weak" references, and for
>> "strong" references one must use reference-counting anyway.
vZOOM allows thread to acquire strong references to shared objects:
static Foo_t *g_Foo = new Foo_t;
Readers_With_Automatic_Epoch() {
vzThread_t* const vzSelf = vzThread_Self();
for(;;) {
Foo_t *l_Foo = vzThread_Self_Acquire(vzSelf, VZTHREAD_SELF_PERSISTENT(),
&g_Foo);
if (l_Foo) {
l_Foo->Do_Something();
}
vzThread_Self_Release(vzSelf, VZTHREAD_SELF_PERSISTENT(), l_Foo);
}
}
>> Another situation.
>> Graph structure where to node can point several other nodes. And this
>> links are removed not all at once by one thread, but one by one by
>> different threads.
>> Can vZOOM handle lifetime management of the node in graph?
>> It seems that threads that remove links to node must use reference-
>> counting. But vZOOM still can be used here for readers.
This is getting into PDR usage patterns. A solid marriage between clever
locking schemes and lock-free zero-overhead PDR can be used to create very
interesting things indeed.
[...]
Chris Thomasson
> On 6 июн, 05:51, Joe Seigh <jseigh...@xemaps.com> wrote:
>
>> > Can vZOOM handle lifetime management of the message?
>> > It seems for me that the answer will be NO.
>>
>> If you can use a multi-tailed fifo queue instead of 2 different
>> queues.
>
> What is "multi-tailed fifo queue"?
>
> I mean messaging system where threads are fully connected with queues.
> So every arbitrary thread can pass message to every arbitrary set of
> other threads...
> So I try to understand can vZOOM handle this
> kind of references and this kind of lifetime management? Or it's just
> for lock-free reader pattern for data structures...
The vZOOM Library per-thread message multiplexer/demultiplexer subsystem
(e.g., the distributed multicaster) does not really need to rely on the PDR
subsystem.
I guess you can use the persistent reference counting in a message passing
algorithm like this:
producers() {
for(;;) {
/* acquire group of persistent references */
/* produce group of messages with those references */
/* acquire a group of release responses */
for_each_release_response() {
/* release persistent references */
}
}
}
consumers() {
for(;;) {
/* acquire group of messages */
for_each_message() {
/* acquire persistent reference */
/* add release response to local group */
}
/* send local group of release responses */
/* process messages */
/* release persistent messages */
}
}
This all could be interlocked operation free with the distributed vZOOM
multicast because it entirely made up of single producer/consumer lock-free
queues.
Chris Thomasson
[...]
> producers() {
> for(;;) {
> /* acquire group of persistent references */
>
> /* produce group of messages with those references */
>
> /* acquire a group of release responses */
^^^^^^^^^^^^^^^
/* try to acquire a group of release responses */
> for_each_release_response() {
> /* release persistent references */
> }
> }
> }
> consumers() {
> for(;;) {
> /* acquire group of messages */
^^^^^^^^^^^^^^^^^^^^^^^^^^
/* wait for, and then acquire group of messages */
Dmitriy Vyukov
> I guess you can use the persistent reference counting in a message passing
> algorithm like this:
> ...
> This all could be interlocked operation free with the distributed vZOOM
> multicast because it entirely made up of single producer/consumer lock-free
> queues.
You read my thoughts! :)
Dmitriy V'jukov
Dmitriy Vyukov
> >> As far as I see vZOOM can handle only "weak" references, and for
> >> "strong" references one must use reference-counting anyway.
>
> vZOOM allows thread to acquire strong references to shared objects:
I mean "strong" in another sense. I mean "string" reference - link in
data-structure.
Thank you for clarification. Now I understand.
Dmitriy V'jukov
Chris Thomasson
> On 7 , 04:41, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> >> As far as I see vZOOM can handle only "weak" references, and for
>> >> "strong" references one must use reference-counting anyway.
>>
>> vZOOM allows thread to acquire strong references to shared objects:
>
> I mean "strong" in another sense. I mean "string" reference - link in
> data-structure.
You could protect a linked-structure like:
struct Foo_t {
Foo_t *m_Next;
void Do_Something(...) const; // read-only
[...];
};
static Foo_t *g_Foo = new Foo_t;
Readers_With_Automatic_Or_Manual_Epoch() {
vzThread_t* const vzSelf = vzThread_Self();
if (vzSelf) { for(;;) {
vzThread_Read_t* const vzRead =
vzThread_Self_Acquire(vzSelf,
VZTHREAD_SELF_READ_PROXY(), 0);
if (vzRead) {
Foo_t *l_Foo =
vzThread_Self_Acquire(vzSelf,
VZTHREAD_SELF_NONPERSISTENT(), &g_Foo);
while (l_Foo) {
Foo_t* const l_Next =
vzThread_Self_Acquire(vzSelf,
VZTHREAD_SELF_NONPERSISTENT(), &l_Foo->m_Next);
l_Foo->Do_Something();
vzThread_Self_Release(vzSelf,
VZTHREAD_SELF_NONPERSISTENT(), l_Foo);
l_Foo = l_Next;
} // while (l_Foo)
vzThread_Self_Release(vzSelf,
VZTHREAD_SELF_READ_PROXY(), vzRead);
} // if (vzRead)
}} // if (vzSelf) { for(;;)
}
Dmitriy Vyukov
And one more question.
The important point in vZOOM PDR - handling of long-term references. I
am thinking - is it really important thing - long-term references... I
can't remember many examples of using long-term references... Mabe I
just thinking in the wrong way... Can you provide few examples where
handling of long-term references is really useful for me?
Thank you
Dmitriy V'jukov
Chris Thomasson
Long-term references are useful if you want objects to be able to persist
outside of a extensive search. For instance, say a reader thread needs to
search through a data-structure and gather references to nodes that contain
state which match the search criteria. So, the reader would acquire proxy
read access, perform the search, gather the references to the nodes that
match and release the previous acquired proxy read access. Now, the reader
thread can iterate through and "process" all of the node references it
gathered during the previous search.This is not legal in RCU.
Long-term references make it possible to do robust searches and return
references to multiple nodes.