vZOOM can handle cross-thread long-term references?
Dmitriy Vyukov
http://groups.google.ru/group/comp.programming.threads/msg/90ff5d5a17c0450f
you say that vZOOM can't handle references to messages in message-
passing system.
It seems that vZOOM *can* handle such references. You just need to
slightly modify... documentation :)
So producer create message object.
Then producer acquire 2 long-term references to message.
Then producer put message to 2 different queues.
Then producer call long_term_reclaim(message) (i.e. delete message).
Then every consumer receive message.
Then every consumer process message somehow.
And then every consumer release long-term references to message.
So long-term references acquired and released in different threads!
Accoring to your algorithm it must work out-of-the-box without any
modifications or problems. I don't see here any problems with counters
overfrow or memory visibility or something else. The only requirement
- pulling thread must see acquire operation not later than release
operation. But it seems to me that this requirement will be always
keeped. Long term counters become differential.
And after producer call long_term_reclaim(message), message handled
with only basic thread safety, but this is enough here. Consumers can
pass this message to other consumers and so on.
So this makes vZOOM long-term reference handling far more powerful.
Any thoughts? ;)
Dmitriy V'jukov
Chris Thomasson
news:1184150507....@w3g2000hsg.googlegroups.com...
> Chris Thomasson, here
> http://groups.google.ru/group/comp.programming.threads/msg/90ff5d5a17c0450f
> you say that vZOOM can't handle references to messages in message-
> passing system.
>
> It seems that vZOOM *can* handle such references. You just need to
> slightly modify... documentation :)
>
> So producer create message object.
> Then producer acquire 2 long-term references to message.
> Then producer put message to 2 different queues.
> Then producer call long_term_reclaim(message) (i.e. delete message).
> Then every consumer receive message.
> Then every consumer process message somehow.
> And then every consumer release long-term references to message.
The consumer cannot release a reference from the pref[] that is owned by a
foreign thread. Here is how you wouold have to do it:
http://groups.google.ru/group/comp.programming.threads/msg/accdc949d8b08957
Dmitriy Vyukov
> The consumer cannot release a reference from the pref[] that is owned by a
> foreign thread.
Why? I don't see any reasons for that.
> Here is how you wouold have to do it:
> http://groups.google.ru/group/comp.programming.threads/msg/accdc949d8...
Yes, I remember about that.
Dmitriy V'jukov
Dmitriy Vyukov
> On 20 , 13:47, "Chris Thomasson" <cris...@comcast.net> wrote:
>
> > The consumer cannot release a reference from the pref[] that is owned by a
> > foreign thread.
>
> Why? I don't see any reasons for that.
I mean that you only use sum of pref[] of all threads, so it is no
matter to which thread's pref[] you make '+1' and to which - '-1'.
Dmitriy V'jukov
Chris Thomasson
> On 20 , 13:47, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> The consumer cannot release a reference from the pref[] that is owned by
>> a
>> foreign thread.
>
> Why? I don't see any reasons for that.
You don't really want a non-polling processor thread to be able to access
any data on a foreign thread unless you within the context of a memory
allocator operating with a local block of processors.
The rule of thumb is: A vzoom standard thread should not be able to access
another thread.
The code within the framework really strives to adhere to that rule.
>> Here is how you wouold have to do it:
>> http://groups.google.ru/group/comp.programming.threads/msg/accdc949d8...
>
> Yes, I remember about that.
This simply uses a message-passing medium to do a prototype of how one vzoom
thread could modify another vzoom threads data...
Dmitriy Vyukov
> > Why? I don't see any reasons for that.
>
> You don't really want a non-polling processor thread to be able to access
> any data on a foreign thread unless you within the context of a memory
> allocator operating with a local block of processors.
Either I don't understand you or you don't understand me...
I am not saying about situation when one thread accesses foreign
thread data.
First thread executes:
vzoom_long_term_acquire(p);
and this affects only first thread's data.
and second thread executes:
vzoom_long_term_release(p);
and this affects only second thread's data.
Then polling thread combines local data from first and second threads
and decides when it is safe to delete pointer p.
How first thread pass pointer p to second thread - this is separate
question - for example by some producer-consumer queue.
Dmitriy V'jukov
Chris Thomasson
> On Jul 26, 8:06 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> > Why? I don't see any reasons for that.
>>
>> You don't really want a non-polling processor thread to be able to access
>> any data on a foreign thread unless you within the context of a memory
>> allocator operating with a local block of processors.
>
> Either I don't understand you or you don't understand me...
> I am not saying about situation when one thread accesses foreign
> thread data.
>
> First thread executes:
> vzoom_long_term_acquire(p);
> and this affects only first thread's data.
>
> and second thread executes:
> vzoom_long_term_release(p);
> and this affects only second thread's data.
>
> Then polling thread combines local data from first and second threads
> and decides when it is safe to delete pointer p.
Okay. I was confused by your initial question. Now I think see what your
talking about here. At the end of the entire operation the first thread
would contain a 1 in prefs[hash(p)], and the second thread would contain a
(-1) in prefs[hash(p)]. The polling thread sums them up and comes up with
zero which means 'p' is indeed quiescent. Humm. Yeah, this will work...
> How first thread pass pointer p to second thread - this is separate
> question - for example by some producer-consumer queue.
Indeed.
Chris Thomasson
> Chris Thomasson, here
> http://groups.google.ru/group/comp.programming.threads/msg/90ff5d5a17c0450f
> you say that vZOOM can't handle references to messages in message-
> passing system.
>
> It seems that vZOOM *can* handle such references. You just need to
> slightly modify... documentation :)
>
> So this makes vZOOM long-term reference handling far more powerful.
>
> Any thoughts? ;)
Yes, I agree. Indeed it would make persistent references more flexible, and
"powerful"...
:^)
Chris Thomasson
news:hN-dnSDO58HzTjDb...@comcast.com...
I think I am losing my fuc%ing mind! I was browsing some of my older
experimental vZOOM code and found where I was doing something very similar.
I totally forgot about it. Damn! I can't believe I did that. No wonder why I
named the technique "Distributed Differential Reference Counting" to begin
with:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/1216861ac568b2be/
sh%it. My brain is crapping out on me!
;^0
Dmitriy Vyukov
> Yes, I agree. Indeed it would make persistent references more flexible, and
> "powerful"...
This way vZOOM scheme can handle any kind of reference counting with
basic thread safety.
For example, strings with COW, message lifetime in message-passing
system, plain reference counting (objects with add_ref()/release()
functions) etc.
And with epoch tracking mechanism vZOOM scheme can handle any kind of
reference counting with strong thread safety too.
So Joe Seigh's atomic_ptr API can be fully emulated with vZOOM means.
Dmitriy V'jukov
Dmitriy Vyukov
> I think I am losing my fuc%ing mind! I was browsing some of my older
> experimental vZOOM code and found where I was doing something very similar.
Do you see here any problems with memory visibility?
For example consider next scenario.
Thread 1 execute synchronization procedure.
Thread 2 doesn't yet execute synchronization procedure.
So polling thread is waiting for thread 2.
Thread 1 execute vzoom_long_term_acquire(p), then pass p to thread 2.
Thread 2 receive p, and execute vzoom_long_term_release(p), then
thread 2 execute synchronization procedure.
Now polling thread see that all threads execute synchronization
procedure, and begin to collect garbage.
Note that thread 1 doesn't execute synchronization procedure since he
execute vzoom_long_term_acquire(p). So polling thread will see release
operation from thread 2, but he will can miss acquire operation from
thread 1. This will break the algorithm. The most dreadful thing -
polling thread can yield false positive answer for question "whether
some other object p2 is ready for freeing".
Note also that procedure "pass p to thread 2" might not include any
memory barriers.
What do you think?
Dmitriy V'jukov
Chris Thomasson
> On 30 , 16:09, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> I think I am losing my fuc%ing mind! I was browsing some of my older
>> experimental vZOOM code and found where I was doing something very
>> similar.
>
> Do you see here any problems with memory visibility?
[...]
I can't see any right off the bat. BTW, the polling processor makes sure
that it waits an extra epoch before calling back the deferred requests:
http://groups.google.com/group/comp.programming.threads/msg/b6428e1ddbeb450c
Dmitriy Vyukov
> I can't see any right off the bat.
But what about my example?
> BTW, the polling processor makes sure
> that it waits an extra epoch before calling back the deferred requests:
> Drop object to zero; wait for "another" sync-epoch; dtor
This won't help in this situation.
Because if polling thread yield false positive answer for question
"whether
some other object p2 is ready for freeing", you can wait any number of
"another" sync-epochs, but it will be still early to free p2.
There must be something like:
Drop object to zero; wait for "another" sync-epoch; check whether
object is still zero; dtor
But I think it is very high price - waiting for 2 epochs instead of
1...
And I still hope that I am not right with my line of reasoning :)
Dmitriy V'jukov
Chris Thomasson
> On 31 , 22:38, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> I can't see any right off the bat.
>
> But what about my example?
>
>> BTW, the polling processor makes sure
>> that it waits an extra epoch before calling back the deferred requests:
>
>> Drop object to zero; wait for "another" sync-epoch; dtor
>
> This won't help in this situation.
> Because if polling thread yield false positive answer for question
> "whether
> some other object p2 is ready for freeing", you can wait any number of
> "another" sync-epochs, but it will be still early to free p2.
>
> There must be something like:
>
> Drop object to zero; wait for "another" sync-epoch; check whether
> object is still zero; dtor
I need to think some more on this. However, keep in mind that an object has
to be put into a threads defer list in order for the polling thread to even
see it. An object can only be put into a defer list once there are no longer
any global pointers, just like with SMR. I can't quite see how the polling
thread could yield false positives in this case. If you enqueue an object
into a thread defer queue while it can be reached by other threads then your
sort of breaking the rules.
Chris Thomasson
> On Jul 30, 4:03 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> Yes, I agree. Indeed it would make persistent references more flexible,
>> and
>> "powerful"...
>
> So Joe Seigh's atomic_ptr API can be fully emulated with vZOOM means.
I think I would have to define some new rules in order for this to work.
vZOOM was not really intended to handle this type of reference counting. It
was basically designed to get around the static nature of SMR. I wanted a
thread to be able to hold a dynamic number of references which was not
possible in SMR. The old code I am looking at that has reference counting
similar to your question was extremely experimental and was running under
some different polling logic.
Chris Thomasson
> "Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
> news:1185771336.1...@d30g2000prg.googlegroups.com...
>> On Jul 26, 8:06 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>>
>>> > Why? I don't see any reasons for that.
>>>
>>> You don't really want a non-polling processor thread to be able to
>>> access
>>> any data on a foreign thread unless you within the context of a memory
>>> allocator operating with a local block of processors.
>>
>> Either I don't understand you or you don't understand me...
>> I am not saying about situation when one thread accesses foreign
>> thread data.
>>
>> First thread executes:
>> vzoom_long_term_acquire(p);
>> and this affects only first thread's data.
>>
>> and second thread executes:
>> vzoom_long_term_release(p);
>> and this affects only second thread's data.
>>
>> Then polling thread combines local data from first and second threads
>> and decides when it is safe to delete pointer p.
>
> Okay. I was confused by your initial question. Now I think see what your
> talking about here.
[...]
The polling thread won't be able to see pointer p unless it was deferred.
The rules for deferment are the same as the rules for RCU, pc_sample, SMR,
ect... I would have to redefine the rules in order for this to work. Your
seem to be thinking that the polling thread has access to object p before it
gets deferred... Not the case...
Chris Thomasson
> "Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
> news:1185799894.9...@e16g2000pri.googlegroups.com...
>> On Jul 30, 4:03 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>>
>>> Yes, I agree. Indeed it would make persistent references more flexible,
>>> and
>>> "powerful"...
> [...]
>>
>> So Joe Seigh's atomic_ptr API can be fully emulated with vZOOM means.
>
> I think I would have to define some new rules in order for this to work.
> vZOOM was not really intended to handle this type of reference counting.
[...]
I was thinking more along the lines of:
http://groups.google.com/group/comp.programming.threads/msg/a382fff669340d86
http://groups.google.com/group/comp.programming.threads/msg/fc72dd504fd7a65a
Reader threads could perform a search on a data-structure and hold
references to each node that matched the search criteria across multiple
epochs.
Dmitriy Vyukov
> The polling thread won't be able to see pointer p unless it was deferred.
> The rules for deferment are the same as the rules for RCU, pc_sample, SMR,
> ect... I would have to redefine the rules in order for this to work. Your
> seem to be thinking that the polling thread has access to object p before it
> gets deferred... Not the case...
Is my example in the first post is correct?
Dmitriy V'jukov
Dmitriy Vyukov
> I need to think some more on this. However, keep in mind that an object has
> to be put into a threads defer list in order for the polling thread to even
> see it. An object can only be put into a defer list once there are no longer
> any global pointers, just like with SMR. I can't quite see how the polling
> thread could yield false positives in this case. If you enqueue an object
> into a thread defer queue while it can be reached by other threads then your
> sort of breaking the rules.
Yes. Now I am foolish.
I look at my example in the first post one more time.
Thread 1 execute vzoom_long_term_acquire(p) and only then
vzoom_long_term_defer(p). So, if polling thread see object p, he
necessarily must see acquire operation too.
So cross-thread long-term references are still working.
False alarm :)
Dmitriy V'jukov
Dmitriy Vyukov
> > So Joe Seigh's atomic_ptr API can be fully emulated with vZOOM means.
>
> I think I would have to define some new rules in order for this to work.
Exactly. Only the rules. But not the algorithm or the code! :)
> vZOOM was not really intended to handle this type of reference counting. It
> was basically designed to get around the static nature of SMR. I wanted a
> thread to be able to hold a dynamic number of references which was not
> possible in SMR. The old code I am looking at that has reference counting
> similar to your question was extremely experimental and was running under
> some different polling logic.
Now I am sure again that my example in first post is working. With
existing polling logic. So I don't see any reasons to prohibit such
usage.
Dmitriy V'jukov
Dmitriy Vyukov
> > > So Joe Seigh's atomic_ptr API can be fully emulated with vZOOM means.
>
> > I think I would have to define some new rules in order for this to work.
>
> Exactly. Only the rules. But not the algorithm or the code! :)
I think that assignment from global_ptr to global_ptr have to use
plain old atomic reference counting, i.e. when copying global_ptr
object's counter must be incremented. And destruction of global_ptr
must decrement object's counter.
This needed in order to know when to call vzoom_long_term_defer().
vzoom_long_term_defer() must be called when last global_ptr is gone.
Because vzoom itself can't resolve situation when there are several
persistent pointers to object.
All other assignments (global_ptr to local_ptr, local_ptr to
local_ptr) can use vzoom_long_term_acquire/vzoom_long_term_release.
So my example from first post can be rewritten:
typedef fifo_queue_t<local_ptr<msg> > queue_t;
void producer()
{
for (;;)
{
global_ptr<msg> g (new msg());
queue1.enqueue(local_ptr<msg>(g));
queue2.enqueue(local_ptr<msg>(g));
}
}
void consumer()
{
for(;;)
{
local_ptr<msg> l = queue.dequeue();
//...
}
}
Since copying of local_ptr is very light operation, queue can hold
local_ptrs by value.
Dmitriy V'jukov
Dmitriy Vyukov
> So my example from first post can be rewritten:
This gives second life to vZOOM :)
Dmitriy V'jukov
Chris Thomasson
I believe it is.