Strong vs. Normal Thread Safety.
Chris Thomasson
In a recent thread:
http://groups.google.com/group/comp.programming.threads/msg/91fdd6b0b8966936
There were the beginnings of a discussion on the differences between the
various thread safety levels and how they relate to reference counting. The
rule is simple and clear:
If any one of your threads can acquire a reference to a shared data-object
that it does not already own a reference to, then you need strong thread
safety. Otherwise, you can use normal thread safety.
Strong thread safety can handle multiple parallel accesses from an arbitrary
number of threads at any time. Normal thread safety cannot handle this type
of scenario at all.
For instance, here is an example of a scheme that requires strong thread
safety:
_____________
static refcount<foo> g_foo = new foo;
threads_a_y() {
for(;;) {
refcount<foo> l_foo = g_foo;
if (l_foo) {
l_foo->foo();
}
}
}
thread_z() {
for(;;) {
refcount<foo> l_foo = new foo;
g_foo.swap(l_foo);
}
}
______________
The example is relies on strong competing access to the g_foo variable.
Threads a-y can acquire references to a foo object that they do not
previously own. The above example is no compatible even with Boost
shared_ptr. If you replace the refcount object with shared_ptr, you can
seg-fault in the threads_a_y() code. This is because shared_ptr being
normally thread safe cannot handle the multiple access from threads a-y. Or
even a and z.
Here is an example of a scheme that requires normal thread safety:
__________
static queue<foo> g_fooq;
threads_a_y() {
for(;;) {
refcount<foo> l_foo = g_fooq.pop();
if (l_foo) {
l_foo->foo();
}
}
}
thread_z() {
for(;;) {
refcount<foo> l_foo = new foo;
l_foo.increment();
g_fooq.push(l_foo);
}
}
____________
This can use normal thread safety because no threads tries to increment an
object that is does not previously own. This is 100% compatible with boost
shared_ptr.
Any thoughts?
Gianni Mariani
....
> Any thoughts?
Where do you put transfer of ownership e.g. A thread reads messages
from a socket and places the message object in a queue which is consumed
by another thread ? In this case, the reference count needs to be thread
safe, but the message itself does not.
There is the other issue, the reference counting mechanism can be thread
safe but the smart pointer may not be.
In the latest austria C++ reference counted smart pointers, there is a
"thread safe" smart pointer. (http://netcabletv.org/public_releases/
warning big...) The issue is that arose from this design is that no
thread is really allowed to do anything but copy the pointer to or from
the smart pointer to a non thread safe smart pointer.
Consider this:
Ptr<T*> global = new T;
void thread1()
{
global->Dosomthing();
}
void thread2()
{
global = new T;
}
The problem here is that thread2() can destroy the object that thread1()
is using (with or without actual threads).
To relieve this issue, an austria thread safe smart pointer does not
allow access to non thread safe operations ....
i.e. global->Dosomthing(); is illegal if "global" is a thread safe smart
pointer.
The code would need to be rewritten to:
Ptr<T*,ThreadSafe> global = new T;
void thread1()
{
Ptr<T*> local = global;
local->Dosomthing();
}
void thread2()
{
global = new T;
}
Chris Thomasson
news:463d6a6c$0$9075$5a62...@per-qv1-newsreader-01.iinet.net.au...
> Chris Thomasson wrote:
> ....
>> Any thoughts?
>
> Where do you put transfer of ownership e.g. A thread reads messages from
> a socket and places the message object in a queue which is consumed by
> another thread ? In this case, the reference count needs to be thread
> safe, but the message itself does not.
Sure. You can use transfer of ownership with normal thread-safety level. You
can transfer ownership without using strong thread safety. So, lock-free
auto_ptr is possible with normal threads safety. Here is an example:
http://appcore.home.comcast.net/vzoom/refcount/doc/api/refcount_add_swap_weak.htm
I am not concerned with the thread safety level of the user object. I am
focusing on the data-structures that make up the reference counting
implementation.
Chris Thomasson
news:r_CdnTqC4PCUEKDb...@comcast.com...
> "Gianni Mariani" <gi3n...@mariani.ws> wrote in message
> news:463d6a6c$0$9075$5a62...@per-qv1-newsreader-01.iinet.net.au...
>> Chris Thomasson wrote:
>> ....
>>> Any thoughts?
>>
>> Where do you put transfer of ownership e.g. A thread reads messages from
>> a socket and places the message object in a queue which is consumed by
>> another thread ? In this case, the reference count needs to be thread
>> safe, but the message itself does not.
>
> Sure. You can use transfer of ownership with normal thread-safety level.
> You can transfer ownership without using strong thread safety. So,
> lock-free auto_ptr is possible with normal threads safety. Here is an
> example:
>
> http://appcore.home.comcast.net/vzoom/refcount/doc/api/refcount_add_swap_weak.htm
>
> I am not concerned with the thread safety level of the user object.
I can only guarantee the a user object will be visible to any thread that
acquires a new reference to it.
Chris Thomasson
Gianni Mariani
> "Chris Thomasson" <cri...@comcast.net> wrote in message
> news:r_CdnTqC4PCUEKDb...@comcast.com...
>> "Gianni Mariani" <gi3n...@mariani.ws> wrote in message
>> news:463d6a6c$0$9075$5a62...@per-qv1-newsreader-01.iinet.net.au...
>>> Chris Thomasson wrote:
>>> ....
>>>> Any thoughts?
>>> Where do you put transfer of ownership e.g. A thread reads messages from
>>> a socket and places the message object in a queue which is consumed by
>>> another thread ? In this case, the reference count needs to be thread
>>> safe, but the message itself does not.
>> Sure. You can use transfer of ownership with normal thread-safety level.
I have no idea what you mean by "normal thread-safety" in this case.
If you're manipulating a reference count from multiple threads
simultaneously, then the reference count increment and decrement must be
thread safe -period-.
>> You can transfer ownership without using strong thread safety. So,
>> lock-free auto_ptr is possible with normal threads safety. Here is an
>> example:
>>
>> http://appcore.home.comcast.net/vzoom/refcount/doc/api/refcount_add_swap_weak.htm
>>
>> I am not concerned with the thread safety level of the user object.
>
> I can only guarantee the a user object will be visible to any thread that
> acquires a new reference to it.
Now I am totally lost as what you're trying to say.
There are two objects that are involved with reference counting. One is
the reference count itself (including the weak count if you implement
weak pointers), the other is also the actual pointer contained within
the smart pointer.
A thread safe reference count is a relatively easy thing to achieve
although platform specific. The thread safe smart pointer requires a
swap of the pointer contained in the smart pointer AND incrementing the
reference count (both) atomically.
The scenario is this:
Ptr<T*> gt1;
Ptr<T*> gt2;
void thread1()
{
gt1 = new T;
}
void thread2()
{
gt2 = gt1;
}
When the assignment process has taken a copy of the pointer from gt1, it
had better have a reference count of 2 (even before assignment to gt2 is
complete) otherwise you have a race condition where the assignment to
gt1 (thread1) can delete the object before you have a chance to
increment the reference count before assigning it to gt2.
In Austria C++, it's accomplished through using what amounts to a lock
in the pointer contained within the smart pointer itself. Two swaps of
the pointer are made, the first one is used to swap a sentinel, in its
place, (using a compare and swap atomic instruction) and then an
increment to the reference count, followed by assignment back to the
smart pointer being copied from. It's lock free in the sense there are
no system locks but it essentially amounts to spin to grab the pointer,
increment the reference count and unlock.
Having said all this, there is only one place in the Austria C++ library
that really needs this kind of mechanism and that's in what I term the
"Twin" interface to manage a reference counted lock. The twin interface
is a coupling of two objects where one object can call the other and
either can decide to terminate at any time. To manage the association
of the two objects a lock is needed to make sure the other object does
not go away in the meantime. This is used heavily in the network
interface where the socket object informs it's client of various events
(arrival of data) and the client gets to do things like request data,
send data and terminate the relationship (close the socket). Usually
the only thing the client can do it enqueue itself to be called by the
thread pool and modify some object specific data. Call backs from the
thread pool can be made to be single threaded so you end up only needing
to have light levels of locking within the client object itself.
I don't know if this helps you at all, but it's a model that has been
very successful in eliminating many of the usual pitfalls of MT programming.
David Schwartz
> If any one of your threads can acquire a reference to a shared data-object
> that it does not already own a reference to, then you need strong thread
> safety. Otherwise, you can use normal thread safety.
I find that talking this way hampers understanding. It is not so much
a thread that owns a reference but a logical function. If, for
example, a message is popped off a queue to process, it's the "process
this message" logical operation that owns the reference. Various
different threads can participate in the process, handing off the
message's same reference, until the processing is done. When the
processing is complete, regardless of what thread does it, then the
reference should be dropped.
Similarly, while a message is owned by a queue, the queue has a
reference. This is true even though no threads is currently associated
with that message. The reference exists because the message cannot be
destroyed until it is process.
> Threads a-y can acquire references to a foo object that they do not
> previously own.
So long as something own a reference to that object. Otherwise, there
is no way the threads would even know that object exists. There should
be no way to obtain a pointer to an object except from something that
has a reference to that object.
DS
David Hopwood
> Any thoughts?
You didn't explain what strong thread safety *is*; only when it is
required.
--
David Hopwood <david....@industrial-designers.co.uk>
Chris Thomasson
news:1178486075.0...@q75g2000hsh.googlegroups.com...[...]
>> Threads a-y can acquire references to a foo object that they do not
>> previously own.
>
> So long as something own a reference to that object. Otherwise, there
> is no way the threads would even know that object exists. There should
> be no way to obtain a pointer to an object except from something that
> has a reference to that object.
There is a way to obtain a pointer. You seem to not be grasping the point of
strong thread safety. Your 100% correct with Normal/Basic thread safety, not
with Strong...
Chris Thomasson
news:j6s%h.149355$Zb2....@fe2.news.blueyonder.co.uk...
> Chris Thomasson wrote:
>> Any thoughts?
>
> You didn't explain what strong thread safety *is*; only when it is
> required.
Well, strong thread safety IMHO, basically is when concurrent writes,
concurrent reads+writes are 100% safe, 100% of the time.
Chris Thomasson
news:1178486075.0...@q75g2000hsh.googlegroups.com...
>> previously own.
>
> So long as something own a reference to that object.
Look at the first example I gave one more time. See how any thread can try
to grab a reference no matter what?
> Otherwise, there
> is no way the threads would even know that object exists.
What about g_foo in the first example???
Notice how any thread can do this:
refcount<foo> l_foo = g_foo;
at any time?
Chris Thomasson
> Chris Thomasson wrote:
>> "Chris Thomasson" <cri...@comcast.net> wrote in message
>> news:r_CdnTqC4PCUEKDb...@comcast.com...
>>> "Gianni Mariani" <gi3n...@mariani.ws> wrote in message
>>> news:463d6a6c$0$9075$5a62...@per-qv1-newsreader-01.iinet.net.au...
>>>> Chris Thomasson wrote:
>>>> ....
>>>>> Any thoughts?
>>>> Where do you put transfer of ownership e.g. A thread reads messages
>>>> from a socket and places the message object in a queue which is
>>>> consumed by another thread ? In this case, the reference count needs to
>>>> be thread safe, but the message itself does not.
>>> Sure. You can use transfer of ownership with normal thread-safety level.
>
> I have no idea what you mean by "normal thread-safety" in this case.
Well, the transfer of ownership can be accomplished by a thread A
guaranteeing that it will not decrement the reference count of an object A
after it transfers it over to a Thread B.
So, Thread A gave up its right to decrement the reference count therefore
transferring ownership to someone else, Thread B in this case...
This requires no concurrent writes, or concurrent reads and writes,
therefore, Basic or Normal thread-safety can be used...
[...]
http://appcore.home.comcast.net/vzoom/refcount/doc/api/refcount_add_swap_weak.htm
>>>
>>> I am not concerned with the thread safety level of the user object.
>>
>> I can only guarantee the a user object will be visible to any thread that
>> acquires a new reference to it.
>
> Now I am totally lost as what you're trying to say.
For Strong Thread-Safety, not only do the counter operations themselves have
to be thread-safe, but a separate pointer location (e.g., anchor) has to be
kept ATOMIC in conjunction with the thread-safe refcount modifications...
For Normal Thread-Safety, only the counter operations need to be
thread-safe.
As for user objects, well I am not talking about extending any mutual
exclusion functionality to them... I only focus on the reference counting
internal structures.
As for:
>> I can only guarantee the a user object will be visible to any thread that
>> acquires a new reference to it.
Well, that means that any threads that takes a valid reference to an object
will have a complete view of the object.
David Schwartz
> Look at the first example I gave one more time. See how any thread can try
> to grab a reference no matter what?
No, I don't. But it's uncommented and uses nonsense names, so it's
very difficult to follow. If your thought was that this would be clear
easy to follow code, ...
DS
Chris Thomasson
What is hard to follow:
_____________
static refcount<foo> g_foo = new foo;
threads_a_y() {
for(;;) {
refcount<foo> l_foo = g_foo;
if (l_foo) {
l_foo->foo();
}
}
}
thread_z() {
for(;;) {
refcount<foo> l_foo = new foo;
g_foo.swap(l_foo);
}
}
______________
????
Please explain?????
Chris Thomasson
> "David Schwartz" <dav...@webmaster.com> wrote in message
> news:1178515181....@u30g2000hsc.googlegroups.com...
>> On May 6, 9:03 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>>
>>> Look at the first example I gave one more time. See how any thread can
>>> try
>>> to grab a reference no matter what?
>>
>> No, I don't. But it's uncommented and uses nonsense names, so it's
>> very difficult to follow. If your thought was that this would be clear
>> easy to follow code, ...
The l_* prefix in my code means local. The g_* prefix means global.
Chris Thomasson
LOOK AT g_foo!!
See how a thread a-y can try to load a refcount<foo> from g_foo even though
it does not own a previous reference???
Keep in mind that g_foo is global!
Chris Thomasson
> "David Schwartz" <dav...@webmaster.com> wrote in message
> news:1178515181....@u30g2000hsc.googlegroups.com...
[...]
> LOOK AT g_foo!!
[...]
> Keep in mind that g_foo is global!
g_foo is global and therefore reachable at any time and place from a
plurality of application threads.
You need atomic thread-safe counting algorithm in order to handle the
described senerio.
Chris Thomasson
> LOOK AT g_foo!!
In the first example.
Markus Elfring
> to be thread-safe, but a separate pointer location (e.g., anchor) has to be
> kept ATOMIC in conjunction with the thread-safe refcount modifications...
>
> For Normal Thread-Safety, only the counter operations need to be
> thread-safe.
Is there any noteable difference to guarantee that mutual exclusion will be
achieved for two data fields at least?
Would you like to suggest a different term to distinguish the number of memory
locations that must be protected?
Regards,
Markus
David Hopwood
> "David Hopwood" <david....@industrial-designers.co.uk> wrote:
>>Chris Thomasson wrote:
>>
>>>Any thoughts?
>>
>>You didn't explain what strong thread safety *is*; only when it is
>>required.
>
> Well, strong thread safety IMHO, basically is when concurrent writes,
> concurrent reads+writes are 100% safe, 100% of the time.
Safe in what sense, precisely?
--
David Hopwood <david....@industrial-designers.co.uk>
Chris Thomasson
> Chris Thomasson wrote:
>> "David Hopwood" <david....@industrial-designers.co.uk> wrote:
>>>Chris Thomasson wrote:
>>>
>>>>Any thoughts?
>>>
>>>You didn't explain what strong thread safety *is*; only when it is
>>>required.
>>
>> Well, strong thread safety IMHO, basically is when concurrent writes,
>> concurrent reads+writes are 100% safe, 100% of the time.
>
> Safe in what sense, precisely?
Strong thread safety within the context of reference counting:
"It shall be safe for any thread to try to acquire a reference to any object
at any time under any conditions."
It shall be safe to acquire references in any sense, under any conditions.
David Schwartz
> g_foo is global and therefore reachable at any time and place from a
> plurality of application threads.
>
> You need atomic thread-safe counting algorithm in order to handle the
> described senerio.
I don't know if you're deliberately trying to be confusing, but a
global object is created before any other code runs and can never be
destroyed while the application is running. So there can never be a
race condition regarding the lifetime of a global object. Effectively,
the application itself holds a reference to a global object when it
created it.
DS
Chris Thomasson
> On May 7, 12:10 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> g_foo is global and therefore reachable at any time and place from a
>> plurality of application threads.
>>
>> You need atomic thread-safe counting algorithm in order to handle the
>> described senerio.
>
> I don't know if you're deliberately trying to be confusing, but a
> global object is created before any other code runs and can never be
> destroyed while the application is running.
No. The refcount<foo> object is a global reference counted pointer.
Therefore, it can be pointed to different objects throughout the
applications lifetime.
Please look at:
thread_z() {
for(;;) {
refcount<foo> l_foo = new foo;
g_foo.swap(l_foo);
}
}
See? Thread Z creates a new object, then swaps whatever g_foo points to with
the new object.
g_foo will be pointed to a lot of different object throughout it lifetime.
This 100% legal with strong thread safety level.
Chris Thomasson
> "David Schwartz" <dav...@webmaster.com> wrote in message
> news:1178568856.8...@n59g2000hsh.googlegroups.com...
>> On May 7, 12:10 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>>
>>> g_foo is global and therefore reachable at any time and place from a
>>> plurality of application threads.
>>>
>>> You need atomic thread-safe counting algorithm in order to handle the
>>> described senerio.
>>
>> I don't know if you're deliberately trying to be confusing, but a
>> global object is created before any other code runs and can never be
>> destroyed while the application is running.
>
> No. The refcount<foo> object is a global reference counted pointer.
The refcount object can be as simple as this:
template<typename T>
struct refcount {
struct inner {
T *m_ptr;
int m_refs;
};
inner *m_inner;
}
Chris Thomasson
> "David Schwartz" <dav...@webmaster.com> wrote in message
> news:1178568856.8...@n59g2000hsh.googlegroups.com...
>> On May 7, 12:10 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>>
>>> g_foo is global and therefore reachable at any time and place from a
>>> plurality of application threads.
>>>
>>> You need atomic thread-safe counting algorithm in order to handle the
>>> described senerio.
>>
>> I don't know if you're deliberately trying to be confusing, but a
>> global object is created before any other code runs and can never be
>> destroyed while the application is running.
>
> No. The refcount<foo> object is a global reference counted pointer.
To clarify, refcount in the first example represents an atomic counted
pointer.
You can use it as a global:
static refcount<foo> g_foo = new foo;
And point it to another object on the fly:
refcount<foo> l_foo = new foo;
g_foo.swap(l_foo);
And you can have reads that are concurrent with the above write:
refcount<foo> l_foo = new foo;
if (l_foo) { l_foo->foo(); }
See?
Chris Thomasson
> struct refcount {
> struct inner {
> T *m_ptr;
> int m_refs;
> };
void swap(T *ptr) {
// strong thread-safe atomic swap
}
>
> inner *m_inner;
> }
Chris Thomasson
Of course this is suppose to be:
refcount<foo> l_foo = g_foo; // acquire ref from g_foo
if (l_foo) { l_foo->foo(); }
Sorry about that!
Chris Thomasson
> Chris Thomasson wrote:
>> "David Hopwood" <david....@industrial-designers.co.uk> wrote:
>>>Chris Thomasson wrote:
>>>
>>>>Any thoughts?
>>>
>>>You didn't explain what strong thread safety *is*; only when it is
>>>required.
>>
>> Well, strong thread safety IMHO, basically is when concurrent writes,
>> concurrent reads+writes are 100% safe, 100% of the time.
>
> Safe in what sense, precisely?
Crowbar Proof!
;^)
Chris Thomasson
>
[...]
It seems that there is some confusion about the following code:
_____________
static refcount<foo> g_foo = new foo;
threads_a_y() {
for(;;) {
refcount<foo> l_foo = g_foo;
if (l_foo) {
l_foo->foo();
}
}
}
thread_z() {
for(;;) {
refcount<foo> l_foo = new foo;
g_foo.swap(l_foo);
}
}
______________
Some quick questions:
1. Does the code make it clear to you that g_foo is a global variable
containing a reference counted pointer (e.g., refcount) for 'foo' objects?
2. Does thread_z() clearly show that a new object created by thread z can be
swapped with the object that the reference counted pointer in g_foo
currently points to?
3. Does threads_a_y() clearly show that a reference can be loaded from g_foo
at anytime?
Humm...
David Schwartz
Chris Thomasson wrote:
> To clarify, refcount in the first example represents an atomic counted
> pointer.
>
> You can use it as a global:
>
> static refcount<foo> g_foo = new foo;
>
> And point it to another object on the fly:
>
> refcount<foo> l_foo = new foo;
> g_foo.swap(l_foo);
Of course, you can only point it to another object if that object is
guaranteed to be stable for the time it takes you to point it.
> And you can have reads that are concurrent with the above write:
>
> refcount<foo> l_foo = new foo;
> if (l_foo) { l_foo->foo(); }
>
> See?
I don't see how there can be any race condition.
Again, as I said, I think the race condition you keep talking about is
impossible unless code is so fundamentally broken that this race is
the least of your problems. I have yet to see any code that is
perfectly sane and reasonable except for this race.
DS
Chris Thomasson
>
> Chris Thomasson wrote:
>
>> To clarify, refcount in the first example represents an atomic counted
>> pointer.
>>
>> You can use it as a global:
>>
>> static refcount<foo> g_foo = new foo;
>>
>> And point it to another object on the fly:
>>
>> refcount<foo> l_foo = new foo;
>> g_foo.swap(l_foo);
>
> Of course, you can only point it to another object if that object is
> guaranteed to be stable for the time it takes you to point it.
You have lost me here. Everything is atomically reference counted. What do
you mean by 'stable' objects?
>> And you can have reads that are concurrent with the above write:
>>
>> refcount<foo> l_foo = new foo;
>> if (l_foo) { l_foo->foo(); }
>>
>> See?
>
> I don't see how there can be any race condition.
Try to implement my first example using reference counting w/ only a
basic/normal thread safety level... You will be seg-faulting all over the
place because of the race-condition.
I have explained the race-condition several times, I pointed you to several
academic papers that explain it in great detail. I can't imagine why you
think the first example I gave is broken. I already mention real-world uses
for atomic thread-safe counting. Such as transform GC based lock-free
algorithms into GC independent ones.
Chris Thomasson
> Again, as I said, I think the race condition you keep talking about is
> impossible unless code is so fundamentally broken that this race is
> the least of your problems.
Non-Sense! Are you honestly saying that any code which makes use of The
Strong Thread-Safety Guarantee wrt reference counting is broken by
default???
Chris Thomasson
"Markus Elfring" <Markus....@web.de> wrote in message
news:5a8il3F...@mid.individual.net...
Well, the actual number of memory locations is an implementation detail... I
can do it with XCHG and XADD with a pointer location and a non-contiguous
counter field. Some implementation use DWCAS with pointer and contiguous
counter... ect...
David Schwartz
> Non-Sense! Are you honestly saying that any code which makes use of The
> Strong Thread-Safety Guarantee wrt reference counting is broken by
> default???
I am saying that any code that provides a way to find an object
without guaranteeing that the object you find actually exists is
broken. I am saying that I cannot imagine any possible way that you
could have that particular problem without having dozens of other
problems all over the place.
Your examples all talk about "finding" an object without explaining
what the object is found in or why the object logically exists at the
time it is found. The code you create that you claim displays this
race condition is meaningless and uncommented, so there's no way to
tell what its logic even is, much less whether it is sound or not.
In order to find an object you, you must find it in something.
Whatever that something you find it in *is*, it is at least one of the
reasons the object continues to exist. So long as there is at least
one reason for an object to exist, it cannot be destroyed -- that's
the whole point of reference counting.
Whatever the thing is that you found the object in is, that thing is
logically responsible for ensuring that you can safely access the
object. That is the whole point of that thing, whatever it is. If it
fails to do so, it is horribly broken. This alleged race would be
least of the problems with such a thing.
For example, suppose you find an object that logically represents a
connection to a server in the server's list of connection objects. If
that list gives you an object without a reference, it is fundamentally
broken. Reference counted object must always be given by or with a
reference.
DS
Chris Thomasson
> On May 7, 10:49 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> Non-Sense! Are you honestly saying that any code which makes use of The
>> Strong Thread-Safety Guarantee wrt reference counting is broken by
>> default???
>
> I am saying that I cannot imagine any possible way that you
> could have that particular problem without having dozens of other
> problems all over the place.
The only time you will have that problem wrt reference counting is when you
try to do things that require strong thread safety with an implementation
that only guarantees normal thread safety.
Please read this:
http://groups.google.com/group/comp.programming.threads/msg/f0b7052bd95ca852
http://groups.google.com/group/comp.programming.threads/msg/c957681c1c3081f9
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/3c763698da537d8f
We have had lengthy discussions about this type of reference counting in the
past. I think Joe is right... You either get it or you don't... BTW, did you
read any of the papers I pointed you to:
I would advise you to read the first one at least.
I posted the simplest example I could think of.
I give up!
;^(...
David Schwartz
> I posted the simplest example I could think of.
Your example is utterly meaningless because it contains no comments
about the actual *meaning* underlying the operation. This kind of good
is right or wrong based on what it is *supposed* to do, not just the
actual functions it calls. It contained no comments and used nonsense
variable names. It was, in a word, incomprehensible.
In any event, my argument is fundamental. The race condition you
describe simply cannot happen because any mechanism of finding an
object entails having a reference to that object (or it wouldn't exist
and you couldn't find it). Any method of finding an object that
returns an object without a reference is fundamentally broken as
nothing useful would be returned.
DS
Chris Thomasson
> On May 8, 3:56 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> I posted the simplest example I could think of.
>
> Your example is utterly meaningless because it contains no comments
> about the actual *meaning* underlying the operation. This kind of good
> is right or wrong based on what it is *supposed* to do, not just the
> actual functions it calls. It contained no comments and used nonsense
> variable names. It was, in a word, incomprehensible.
>
> In any event, my argument is fundamental. The race condition you
> describe simply cannot happen because any mechanism of finding an
> object entails having a reference to that object (or it wouldn't exist
> and you couldn't find it).
You just don't seem to want to get it. I know that your smart enough to
understand that academic papers I pointed you to...
Your assertion that the race-condition cannot happen is simply wrong. I have
to make sure that others understand that this race-condition is real!
Perhaps later on today I will try to post one more example that's loaded
with comments and variable names that you can better understand.
I am sorry for not being able to do this in the first place!
Joe Seigh
>
> For example, suppose you find an object that logically represents a
> connection to a server in the server's list of connection objects. If
> that list gives you an object without a reference, it is fundamentally
> broken. Reference counted object must always be given by or with a
> reference.
>
You could use a different PDR scheme for short term object references
and refcounting for long term ones. I believe deferred reference counting
uses something like that.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
frege
> "David Schwartz" <dav...@webmaster.com> wrote in message
>
> > about the actual *meaning* underlying the operation. This kind of good
> > is right or wrong based on what it is *supposed* to do, not just the
> > actual functions it calls. It contained no comments and used nonsense
> > variable names. It was, in a word, incomprehensible.
>
> > In any event, my argument is fundamental. The race condition you
> > describe simply cannot happen because any mechanism of finding an
> > object entails having a reference to that object (or it wouldn't exist
> > and you couldn't find it).
>
> You just don't seem to want to get it. I know that your smart enough to
> understand that academic papers I pointed you to...
>
> Your assertion that the race-condition cannot happen is simply wrong. I have
> to make sure that others understand that this race-condition is real!
>
> Perhaps later on today I will try to post one more example that's loaded
> with comments and variable names that you can better understand.
>
> I am sorry for not being able to do this in the first place!
Although I'm somewhat afraid of stepping into this conversation, I'm
going to anyhow. I understand what Chris is talking about (because
I've run into the same situation), and I also have a question, so
maybe I'm stepping in for selfish reasons. :-)
So you have a global object Global_Foo, and a GLOBAL REF COUNTED
POINTER to the global object. Let's call this global ref counted
pointer 'g_foo'.
Now some thread wants to use g_foo (or actaully the Global_Foo that
g_foo points to), so they get their own reference. Let's call this
local reference l_foo. (that's an L at the start there):
l_foo = g_foo;
since l_foo is also a ref-counted ptr, the refcount on Global_Foo is
incremented.
All fine and good.
HOWEVER, the real question (and race condition) is what happens when
someone wants to replace Global_Foo with Global_Foo2ElectricBoogaloo,
but still have 'everyone' access it via g_foo. So they want to swap
what g_foo points to "when no one is looking". So this might appear
strange and atypical - ie typically if you have a global object, you
only have one, and it doesn't change. But, hey, strange things
happen, and for some reason sometimes we want to switch to a new
global for some reason. FURTHERMORE, and yet more atypical, we want
to do this magic slight-of-hand while g_foo is in use, AND - *this is
important* - we are OK if existing users use the 'old' global (ie
Global_Foo, that g_foo originally points to), while 'new' users use
the new global (Global_Foo2ElectricBoogaloo).
So we want to swap g_foo 'live' like a hot-swappable harddrive or
something like that.
So for THREAD A:
local_foo = g_foo;
while THREAD B changes g_foo:
g_foo = new Foo... or g_foo = &GlobalFoo2_ElectricBoogaloo, etc;
so thread A either gets the old Global_Foo, or the new one, we don't
care *** BUT *** whichever it gets, it better get the ref-counting
correct.
The gist of Chris' post is that
- boost::shared_ptr doesn't do this.
- Chris has a smart_ptr that can do this.
That's his point.
Now, my question:
I also have a smart_ptr that can handle this situation, however...
when setting g_foo to the new global:
g_foo = some_other_ref_counted_ptr;
do you (Chris) have a version where some_other_ref_counted_ptr might
also be in the middle of an assignment? In my version,
some_other_ref_counted_ptr has to be 'stable' during the assign (the
refcount can change, but what it points to cannot change).
My use cases always had some_other_ref_counted_ptr being stable, so I
didn't persue it too far, but it would be nice to remove that
limitation.
Thanks, and I *hope* I've helped!
Tony
Dmitriy Vyukov
> In any event, my argument is fundamental. The race condition you
> describe simply cannot happen because any mechanism of finding an
> object entails having a reference to that object (or it wouldn't exist
> and you couldn't find it). Any method of finding an object that
> returns an object without a reference is fundamentally broken as
> nothing useful would be returned.
You can find for object w/o having reference to it. And use some
tricky mechanism for getting pointer to objects and incrementing it
reference counter. So method _not_ returns object w/o reference and
_not_ fundamentally broken.
Here are solutions:
http://groups.google.com/group/comp.programming.threads/msg/bbea1d0142adb5c7
http://home.comcast.net/~vzoom/demos/pc_sample.c
http://sourceforge.net/project/showfiles.php?group_id=127837&package_id=139944
Dmitriy V'jukov
Joe Seigh
...
>
> The gist of Chris' post is that
> - boost::shared_ptr doesn't do this.
> - Chris has a smart_ptr that can do this.
> That's his point.
>
>
> Now, my question:
>
> I also have a smart_ptr that can handle this situation, however...
> when setting g_foo to the new global:
>
> g_foo = some_other_ref_counted_ptr;
>
> do you (Chris) have a version where some_other_ref_counted_ptr might
> also be in the middle of an assignment? In my version,
> some_other_ref_counted_ptr has to be 'stable' during the assign (the
> refcount can change, but what it points to cannot change).
>
> My use cases always had some_other_ref_counted_ptr being stable, so I
> didn't persue it too far, but it would be nice to remove that
> limitation.
AFAIK, yes. Everything is atomic. You will either see the new value
of the source ptr or the old value.
Should even handle
g_foo = g_foo;
while
g_bar = g_foo;
and while
g_foo = g_bar;
are happening all simutaneously. Note that the expressions aren't atomic.
Just the pointer loads and stores.
Chris Thomasson
news:1178680417....@e65g2000hsc.googlegroups.com...
> On May 8, 8:08 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>> "David Schwartz" <dav...@webmaster.com> wrote in message
> do you (Chris) have a version where some_other_ref_counted_ptr might
> also be in the middle of an assignment? In my version,
> some_other_ref_counted_ptr has to be 'stable' during the assign (the
> refcount can change, but what it points to cannot change).
For the c++ version I separate the reference counting logic into two smart
pointer types:
http://appcore.home.comcast.net/vzoom/refcount/refcount.hpp
vzsync::ptr::global
vzsync::ptr::local
You can have:
static vzsync::ptr::global<foo> g_foo1 = new foo;
static vzsync::ptr::global<foo> g_foo2 = new foo;
multiple_threads() {
for(;;) {
g_foo1 = g_foo2;
g_foo2 = new foo;
}
}
multiple_threads() {
for(;;) {
vzsync::ptr::local<foo> l_foo1 = g_foo1;
vzsync::ptr::local<foo> l_foo2 = g_foo2;
if (l_foo1 && l_foo2) {
l_foo1->foo();
l_foo2->foo();
}
}
}
So the answer to your question is yes.
Gianni Mariani
> "frege" <gottlo...@gmail.com> wrote in message
> news:1178680417....@e65g2000hsc.googlegroups.com...
>> On May 8, 8:08 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>>> "David Schwartz" <dav...@webmaster.com> wrote in message
> [...]
>
>> do you (Chris) have a version where some_other_ref_counted_ptr might
>> also be in the middle of an assignment? In my version,
>> some_other_ref_counted_ptr has to be 'stable' during the assign (the
>> refcount can change, but what it points to cannot change).
>
> For the c++ version I separate the reference counting logic into two smart
> pointer types:
In Austria C++, this is achieved using a single pointer template type
(at::Ptr) with different pointer traits.
#include "at_lifetime_mt.h"
typedef at::Ptr<foo *,at::PtrTraits<foo *,at::PtrClassRefWrapperMT<foo *
> > > global_foo_ptr;
// can't wait for typedef templates ... :-(
static global_foo_ptr g_foo1 = new foo;
static global_foo_ptr g_foo2 = new foo;
void multiple_threads() {
for(;;) {
g_foo1 = g_foo2;
g_foo2 = new foo;
}
}
void multiple_threads() {
for(;;) {
at::Ptr<foo *> l_foo1 = g_foo1;
at::Ptr<foo *> l_foo2 = g_foo2;
if (l_foo1 && l_foo2) {
l_foo1->foo();
l_foo2->foo();
}
}
}
void illegal()
{
g_foo1->foo(); // won't compile
at::Ptr<foo *>( g_foo )->foo(); // will compile
}
David Schwartz
frege wrote:
> So we want to swap g_foo 'live' like a hot-swappable harddrive or
> something like that.
> So for THREAD A:
>
> local_foo = g_foo;
>
> while THREAD B changes g_foo:
>
> g_foo = new Foo... or g_foo = &GlobalFoo2_ElectricBoogaloo, etc;
>
> so thread A either gets the old Global_Foo, or the new one, we don't
> care *** BUT *** whichever it gets, it better get the ref-counting
> correct.
If you have something that acts as a "get me some reference object,
you don't have to care which", it must get you both the object and the
reference. For a reference counted object, the object must always move
with its reference count (at least logically).
> The gist of Chris' post is that
> - boost::shared_ptr doesn't do this.
> - Chris has a smart_ptr that can do this.
> That's his point.
You are saying that boost's shared pointer doesn't make sure a
reference always accompanies a pointer? Then what's its purpose?
> Now, my question:
>
> I also have a smart_ptr that can handle this situation, however...
> when setting g_foo to the new global:
>
> g_foo = some_other_ref_counted_ptr;
>
> do you (Chris) have a version where some_other_ref_counted_ptr might
> also be in the middle of an assignment? In my version,
> some_other_ref_counted_ptr has to be 'stable' during the assign (the
> refcount can change, but what it points to cannot change).
>
> My use cases always had some_other_ref_counted_ptr being stable, so I
> didn't persue it too far, but it would be nice to remove that
> limitation.
You may need to reference count your reference counts.
DS
Chris Thomasson
>
> frege wrote:
>
>> So we want to swap g_foo 'live' like a hot-swappable harddrive or
>> something like that.
>
> If you have something that acts as a "get me some reference object,
> you don't have to care which", it must get you both the object and the
> reference. For a reference counted object, the object must always move
> with its reference count (at least logically).
I agree. Luckily; that's what strong thread safety buys us, indeed!
>> The gist of Chris' post is that
>> - boost::shared_ptr doesn't do this.
>> - Chris has a smart_ptr that can do this.
>> That's his point.
>
> You are saying that boost's shared pointer doesn't make sure a
> reference always accompanies a pointer? Then what's its purpose?
Its purpose is when ever you use Boost shared_ptr you FOLLOW THE DAMN RULES
TO THE TEE!!!!
Ever read the posting I reference by Peter Dimov? He should know a thing or
two about shared_ptr? Agreed?????
Search google groups for "atomic_ptr question"!!!!!!!
;^)
>> Now, my question:
>>
>> I also have a smart_ptr that can handle this situation, however...
>> when setting g_foo to the new global:
>>
>> g_foo = some_other_ref_counted_ptr;
>>
>> do you (Chris) have a version where some_other_ref_counted_ptr might
>> also be in the middle of an assignment?
[...]
>> My use cases always had some_other_ref_counted_ptr being stable, so I
>> didn't persue it too far, but it would be nice to remove that
>> limitation.
>
> You may need to reference count your reference counts.
Humm. I can do this fine. What implementation do you have in mind, which can
handle strong atomically thread-safe reference counting?
Chris Thomasson
"Gianni Mariani" <gi3n...@mariani.ws> wrote in message
news:46424ee0$0$9117$5a62...@per-qv1-newsreader-01.iinet.net.au...
> Chris Thomasson wrote:
>> "frege" <gottlo...@gmail.com> wrote in message
>> news:1178680417....@e65g2000hsc.googlegroups.com...
>>> On May 8, 8:08 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>>>> "David Schwartz" <dav...@webmaster.com> wrote in message
>> [...]
>>
>>> do you (Chris) have a version where some_other_ref_counted_ptr might
>>> also be in the middle of an assignment? In my version,
>>> some_other_ref_counted_ptr has to be 'stable' during the assign (the
>>> refcount can change, but what it points to cannot change).
>>
>> For the c++ version I separate the reference counting logic into two
>> smart pointer types:
>
> In Austria C++, this is achieved using a single pointer template type
> (at::Ptr) with different pointer traits.
Your library looks like a good one.
Chris Thomasson
But , man I know this race-condition is REAL!
:^(
Chris Thomasson
news:1178704347.6...@e51g2000hsg.googlegroups.com...
Thank you Mr Vyukov, my friend.
:^)
Chris Thomasson
>> "David Schwartz" <dav...@webmaster.com> wrote in message
>>
>> > Your example is utterly meaningless because it contains no comments
>> > about the actual *meaning* underlying the operation.
[...]
> HOWEVER, the real question (and race condition) is what happens when
> someone wants to replace Global_Foo with Global_Foo2ElectricBoogaloo,
> but still have 'everyone' access it via g_foo.
[...]
Thanks for you kind help sir!
Chris Thomasson
Really!
:^)
Chris Thomasson
[...]
> In any event, my argument is fundamental. The race condition you
> describe simply cannot happen because any mechanism of finding an
> object entails having a reference to that object (or it wouldn't exist
> and you couldn't find it).
This line of thinking makes me remember an old twilight zone episode
entitled something like "The Obsolete Man"...
;^/...
Chris Thomasson
Safety-Based Usage Pattern(s) directly in the face, and force the threads
involved to behave like gentlemen, well, does Austria C++ provide a PDR,
possible in the form of proxy collector, interface?
Remember, proxy collector is 100% compatible with locks. Therefore, your
library is workable. But, I notice that you have these smart pointers. Well,
you can work out a proxy collection scheme. You claim that your reference
counted pointers can handle strong threads safety, well, create a proxy
collector!
You library will only benefit from your hard work!
Seriously!
Chris Thomasson
We can help you create a PDR, an possibly introduce it as a real aspect of
your library!
frege
> frege wrote:
> > The gist of Chris' post is that
> > - boost::shared_ptr doesn't do this.
> > - Chris has a smart_ptr that can do this.
> > That's his point.
>
> You are saying that boost's shared pointer doesn't make sure a
> reference always accompanies a pointer? Then what's its purpose?
Yes, a ref count always accompanies the pointer. However, a
boost::shared_ptr can NOT handle being written and read at the same
time. It CAN handle multiple threads changing the refcount, but not
changing the pointer.
>
> DS
Tony
frege
> "frege" <gottlobfr...@gmail.com> wrote in message
>
> > do you (Chris) have a version where some_other_ref_counted_ptr might
> > also be in the middle of an assignment? In my version,
> > some_other_ref_counted_ptr has to be 'stable' during the assign (the
> > refcount can change, but what it points to cannot change).
>
>
Do you use CAS64 to swap/incr the refcount and the pointer together,
or do you defer the destruction of the object?
ie in the case of local_foo = g_foo, while g_foo is being changed, and
the old g_foo is being decremented to 0 - how do you avoid addref'ing
the old g_foo that has gone to zero?
Maybe part of the problem is that my case dealt with objects where the
refcount was internal to the object, and not part of the pointer (ie
like boost::intrusive_ptr). So I can't reliably addref via a pointer
if that pointer is being decremented and deleted. I need to know the
object is stable.
Tony
David Schwartz
> Yes, a ref count always accompanies the pointer. However, a
> boost::shared_ptr can NOT handle being written and read at the same
> time. It CAN handle multiple threads changing the refcount, but not
> changing the pointer.
That is the default case with the POSIX threading model. It's just
hard to imagine why someone would want a reference count that they had
to lock. Sounds like it's one of those weird, quirky things to use in
those cases where you happen to know that it's exactly what you need
and use of more reasonable code has demonstrable performance problems.
I'm almost willing to bet that more than half of the users of this
thing are due to premature optimization.
DS
Chris Thomasson
> On May 9, 5:08 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>> "frege" <gottlobfr...@gmail.com> wrote in message
>>
>> > do you (Chris) have a version where some_other_ref_counted_ptr might
>> > also be in the middle of an assignment? In my version,
>> > some_other_ref_counted_ptr has to be 'stable' during the assign (the
>> > refcount can change, but what it points to cannot change).
>>
>>
>> So the answer to your question is yes.
>
> Do you use CAS64 to swap/incr the refcount and the pointer together,
> or do you defer the destruction of the object?
> ie in the case of local_foo = g_foo, while g_foo is being changed, and
> the old g_foo is being decremented to 0 -
http://appcore.home.comcast.net/vzoom/refcount/
> how do you avoid addref'ing
> the old g_foo that has gone to zero?
I use a tricky locking pattern for this case.
> Maybe part of the problem is that my case dealt with objects where the
> refcount was internal to the object, and not part of the pointer (ie
> like boost::intrusive_ptr). So I can't reliably addref via a pointer
> if that pointer is being decremented and deleted. I need to know the
> object is stable.
Here is a link to some pseudo-code for my refcount:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/4e8717d3bcdedfe9
http://thread.gmane.org/gmane.comp.lib.boost.devel/149670
The basic technique for 'copying' is as follows:
Here is some more detailed pseudo-code I posted in response to Joe Seigh:
http://groups.google.com/group/comp.programming.threads/msg/224aa9d097f4300e
Here is some more detailed pseudo-code I posted in response to Joe Seigh:
http://groups.google.com/group/comp.programming.threads/msg/224aa9d097f4300e
The basic technique for 'copying' is as follows:
rc* copy(rc **sloc, int count) {
1: load ptr from *sloc
if ptr is null goto 2
lock spinlock associated with ptr
re-load ptr from *sloc
compare w/ previous load
if not equal unlock and goto 1
XADD ptr's with count
* if the previous value was less than 1 unlock and goto 1
unlock
2: return ptr
}
It also good to keep the following in mind:
*: If the value was less than 1, that means that we detected a drop to zero
condition on the 'ptr'. Keep in mind that we are locked on the spinlock that
is associated with 'ptr'. The decrement thread always locks before it
destroys, so it will have to wait for us. It also means that all of the
shared locations that previously contained a pointer value equal to 'ptr'
are now either null or have **changed to another value; we fail, and try
again.
The decrement logic looks like this:
bool dec(rc *ptr, int count) {
XADD ptr's refs with negated count;
if new value is greater than 0 then return false;
D1: lock spinlock associated with ptr;
unlock spinlock associated with ptr;
call ptr dtor;
return true;
}
If D1 is reached, that means we have to lock the spinlock for 'ptr'. This
must be done because there could be an increment thread(s) trying to
increment; if any of them has it locked, we have to wait until they
fail-and-unlock: If there is an increment thread that has locked, that means
that it will fail because it will notice that it tried to decrement a value
that was less than 1. If there happens to be an increment thread that has
loaded a pointer value that is equal to 'ptr' and is waiting or just about
to lock the same spinlock, then it will also fail; it's re-load and compare
will ensure that.
**: If there happens to be an increment thread that has loaded a pointer
value that is equal to 'ptr' and is waiting or just about to lock the same
spinlock, and the decrement thread runs the dtor and the user-application
reuses the 'ptr' and swaps it into the exact location that the increment
thread loaded its pointer from, then all is well. The increment threads
lock-and-compare will succeed, and the increment will attempt to proceed.
This algorithm is ABA proof.
My documentation is almost complete; it should help clear things up. Did my
description address some of your initial concerns?
Chris Thomasson
> On May 11, 9:07 pm, frege <gottlobfr...@gmail.com> wrote:
>
>> Yes, a ref count always accompanies the pointer. However, a
>> boost::shared_ptr can NOT handle being written and read at the same
>> time. It CAN handle multiple threads changing the refcount, but not
>> changing the pointer.
>
> That is the default case with the POSIX threading model. It's just
> hard to imagine why someone would want a reference count that they had
> to lock.
What do you mean? If your not using a lock-free counting algorithm, well of
course you have to use locks.
> I'm almost willing to bet that more than half of the users of this
> thing are due to premature optimization.
We use Strong Thread Safety when its needed.
Chris Thomasson
> My documentation is almost complete; it should help clear things up. Did
> my
> description address some of your initial concerns?
Dmitriy Vyukov
> The basic technique for 'copying' is as follows:
>
> rc* copy(rc **sloc, int count) {
> 1: load ptr from *sloc
> if ptr is null goto 2
> lock spinlock associated with ptr
> re-load ptr from *sloc
> compare w/ previous load
> if not equal unlock and goto 1
> XADD ptr's with count
> * if the previous value was less than 1 unlock and goto 1
> unlock
> 2: return ptr
> }
What is the point to use spin-locks instead of proxy-collector scheme?
Some time ago you write:
> I could replace the hashed spinlocks with hashed proxy collector
> anchors (e.g., static my_proxy_anchor_t g_px[0x100]).
Here:
http://groups.google.com/group/comp.programming.threads/msg/64a46f3ef24b786a
But you don't explain nothing more...
spin-locks are blocking - you must block anyway if you have more
threads than processors...
spin-locks would add more heavy atomic operations...
And the second question. Why you need "static my_proxy_anchor_t
g_px[0x100]" at all? As far as I understand proxy-collector scheme
don't need any global table...
Dmitriy V'jukov
Chris Thomasson
> On 15 май, 04:38, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> The basic technique for 'copying' is as follows:
>>
>> rc* copy(rc **sloc, int count) {
>> 1: load ptr from *sloc
>> if ptr is null goto 2
>> lock spinlock associated with ptr
>> re-load ptr from *sloc
>> compare w/ previous load
>> if not equal unlock and goto 1
>> XADD ptr's with count
>> * if the previous value was less than 1 unlock and goto 1
>> unlock
>> 2: return ptr
>> }
>
> What is the point to use spin-locks instead of proxy-collector scheme?
It works with POSIX.
> Some time ago you write:
>> I could replace the hashed spinlocks with hashed proxy collector
>> anchors (e.g., static my_proxy_anchor_t g_px[0x100]).
> Here:
> http://groups.google.com/group/comp.programming.threads/msg/64a46f3ef24b786a
> But you don't explain nothing more...
[...]
>
> And the second question. Why you need "static my_proxy_anchor_t
> g_px[0x100]" at all? As far as I understand proxy-collector scheme
> don't need any global table...
It depends. You can use a global variable to hold the anchor to a collector,
or you could use something like vZOOM which is based on per-thread or
per-cpu synchronization.
Chris Thomasson
> And the second question. Why you need "static my_proxy_anchor_t
> g_px[0x100]" at all? As far as I understand proxy-collector scheme
> don't need any global table...
A global table of proxy collector anchors will reduce the contention of the
loads and stores issued by multiple threads.
If collection A and collection B map to different proxy collectors in the
table, well, then Threads A-C that access collection A will not contend with
Threads D-F because the proxy collector that governs collection A is on
another level-2 cache-line than the collector for collection B.
So, using a global table can be a good thing to do in high-contention
cases...
Chris Thomasson
news:1179201113.2...@w5g2000hsg.googlegroups.com...
>
>> The basic technique for 'copying' is as follows:
>>
>> rc* copy(rc **sloc, int count) {
>> 1: load ptr from *sloc
>> if ptr is null goto 2
>> lock spinlock associated with ptr
>> re-load ptr from *sloc
>> compare w/ previous load
>> if not equal unlock and goto 1
>> XADD ptr's with count
>> * if the previous value was less than 1 unlock and goto 1
>> unlock
>> 2: return ptr
>> }
>
> What is the point to use spin-locks instead of proxy-collector scheme?
Is good to keep in mind that you don't have to use the spinlocks for
increments that just need to follow basic thread safety:
http://appcore.home.comcast.net/vzoom/refcount/doc/api/refcount_add_swap_weak.htm
http://appcore.home.comcast.net/vzoom/refcount/doc/api/refcount_add_weak.htm
All of the functions that are post-fixed with "_weak" can skip the spinlock.
Dmitriy Vyukov
> > What is the point to use spin-locks instead of proxy-collector scheme?
>
> It works with POSIX.
Oh, I see.
But am I right, what on most widespread platforms proxy-collector
scheme _can_ be implemented?
And you leave spin-lock only as backup for very specific or unknown
platforms?
Dmitriy V'jukov
Dmitriy Vyukov
> > And the second question. Why you need "static my_proxy_anchor_t
> > g_px[0x100]" at all? As far as I understand proxy-collector scheme
> > don't need any global table...
>
> It depends. You can use a global variable to hold the anchor to a collector,
> or you could use something like vZOOM which is based on per-thread or
> per-cpu synchronization.
I mean another thing. I mean next:
In proxy-collector scheme I have "pointer" to object with embed
"outer" counter and I have object itself with "inner" counter. That is
all. I don't need any other global objects to make this work...
Why you need some additional global table?
W/o hashed global table contention would be less, because contention
would be only if two threads work with one object.
Dmitriy V'jukov
Dmitriy Vyukov
> > What is the point to use spin-locks instead of proxy-collector scheme?
>
> Is good to keep in mind that you don't have to use the spinlocks for
> increments that just need to follow basic thread safety:
> All of the functions that are post-fixed with "_weak" can skip the spinlock.
I know that you target not only to x86 platform. But on x86 (and maybe
on some other) you must use Interlocked operations for basic thread
safety increments anyway and spin-lock would involve 2 Interlocked
operations, so it would be 2 times expensive...
Dmitriy V'jukov
Chris Thomasson
> On May 15, 12:26 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> > And the second question. Why you need "static my_proxy_anchor_t
>> > g_px[0x100]" at all? As far as I understand proxy-collector scheme
>> > don't need any global table...
>>
>> It depends. You can use a global variable to hold the anchor to a
>> collector,
>> or you could use something like vZOOM which is based on per-thread or
>> per-cpu synchronization.
>
> I mean another thing. I mean next:
> In proxy-collector scheme I have "pointer" to object with embed
> "outer" counter and I have object itself with "inner" counter. That is
> all. I don't need any other global objects to make this work...
Its just a easy way for the reference counting library implementation to see
the private proxy anchor table:
refcount_private_imply.c
---------------------
static proxy_anchor_t *g_proxy[0x100];
refcount_api_function(...) {
// has easy access to g_proxy...
}
// rest of refcount_api_functions...
That's all. BTW, the my reference counting thing:
http://appcore.home.comcast.net/vzoom/refcount/
was basically designed as a simple example for the Boost community to take a
look at. I wanted to show them that allowing shared_ptr to handle strong
thread-safety could be worth their while in the long run... The global vs.
local debate usually turns out to be an implementation detail. For instance,
if your implementation is running on highly distributed systems, well, I
would avoid global accesses like the plague...
Chris Thomasson
> On May 15, 12:39 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> > What is the point to use spin-locks instead of proxy-collector scheme?
>>
>> Is good to keep in mind that you don't have to use the spinlocks for
>> increments that just need to follow basic thread safety:
>> All of the functions that are post-fixed with "_weak" can skip the
>> spinlock.
>
> I know that you target not only to x86 platform. But on x86 (and maybe
> on some other) you must use Interlocked operations for basic thread
> safety increments
I know.
> anyway and spin-lock would involve 2 Interlocked
> operations, so it would be 2 times expensive...
Your misunderstanding me. The _weak functions use XADD to modify the
reference count. They do not use the spinlock. That's 1 interlocked rmw
operation period.
Dmitriy Vyukov
>
> > anyway and spin-lock would involve 2 Interlocked
> > operations, so it would be 2 times expensive...
>
> Your misunderstanding me. The _weak functions use XADD to modify the
> reference count. They do not use the spinlock. That's 1 interlocked rmw
> operation period.
???
If you have working XADD, then you can start up fully charged PDR for
all operations, including strong acquire...
So... you use spin-lock for all operations, including weak acquire,
or... you can not use it for all operations, including strong
acquire...
Using spin-lock for strong acquire and atomic rmw for weak... I don't
understand something anyway...
Dmitriy V'jukov
Chris Thomasson
> On 17 май, 02:48, "Chris Thomasson" <cris...@comcast.net> wrote:
>>
>> > anyway and spin-lock would involve 2 Interlocked
>> > operations, so it would be 2 times expensive...
>>
>> Your misunderstanding me. The _weak functions use XADD to modify the
>> reference count. They do not use the spinlock. That's 1 interlocked rmw
>> operation period.
>
> ???
> If you have working XADD, then you can start up fully charged PDR for
> all operations, including strong acquire...
This is a reference counting algorithm, not proxy.
> So... you use spin-lock for all operations, including weak acquire,
> or... you can not use it for all operations, including strong
> acquire...
The refcount algorithm is "mostly" lock-free. I most certainly do not use
spinlock ops for _weak operations. You seem to be suggesting that mostly
lock-free algorithms are impossible?
> Using spin-lock for strong acquire and atomic rmw for weak... I don't
> understand something anyway...
My refcount algorithm only uses the spinlock when for strong increments and
when the count drops to zero:
http://appcore.home.comcast.net/vzoom/refcount/refcount-ia32-gcc.asm
(refcount source code)
Notice how the _weak function do not use the spinlock table?
Chris Thomasson
>> On 17 май, 02:48, "Chris Thomasson" <cris...@comcast.net> wrote:
>>>
>>> > anyway and spin-lock would involve 2 Interlocked
>>> > operations, so it would be 2 times expensive...
>>>
>>> Your misunderstanding me. The _weak functions use XADD to modify the
>>> reference count. They do not use the spinlock. That's 1 interlocked rmw
>>> operation period.
>>
>> ???
>> If you have working XADD, then you can start up fully charged PDR for
>> all operations, including strong acquire...
>
Using a proxy algorithm with alignment/offset trick limits the number of
outstand references there can be to an object at any one time. Not to sure
how well this would work with a general purpose reference counted pointer...
I want any number of threads to be able to hit the refcount algorithm at any
time..
Dmitriy Vyukov
> Using a proxy algorithm with alignment/offset trick limits the number of
> outstand references there can be to an object at any one time. Not to sure
> how well this would work with a general purpose reference counted pointer...
> I want any number of threads to be able to hit the refcount algorithm at any
> time..
This is the point!
Chris, thank you for patience. The question is closed.
Dmitriy V'jukov
Dmitriy Vyukov
> Its just a easy way for the reference counting library implementation to see
> the private proxy anchor table:
>
> static proxy_anchor_t *g_proxy[0x100];
>
> refcount_api_function(...) {
> // has easy access to g_proxy...
> }
[My previous answer to this post get lost again, sh#t!]
I don't understand what I can store in this global table.
I can't store "outer" counter and I can't store "inner" counter,
because they are strictly object specific. I can't just sum two
counters from two different objects and place this sum into one cell
of global hashed table.
The difference with global table of spin-locks is that spin-locks
don't hold any object-specific state.
Dmitriy V'jukov
Chris Thomasson
> On May 15, 12:26 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> > What is the point to use spin-locks instead of proxy-collector scheme?
>>
>> It works with POSIX.
>
> Oh, I see.
> But am I right, what on most widespread platforms proxy-collector
> scheme _can_ be implemented?
Well, you can do vZOOM lock-based PDR on any platform that exports Mutex and
TLS functionality.
> And you leave spin-lock only as backup for very specific or unknown
> platforms?
Sure. That's fine.
Chris Thomasson
> On May 17, 2:45 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> Its just a easy way for the reference counting library implementation to
>> see
>> the private proxy anchor table:
>>
>> static proxy_anchor_t *g_proxy[0x100];
>>
>> refcount_api_function(...) {
>> // has easy access to g_proxy...
>> }
>
> [My previous answer to this post get lost again, sh#t!]
>
> I don't understand what I can store in this global table.
> I can't store "outer" counter and I can't store "inner" counter,
You can store the master count anchors (e.g., in pc_sample.c) in a global
table....
Dmitriy Vyukov
> You can store the master count anchors (e.g., in pc_sample.c) in a global
> table....
???
But if you have 2 different objects that hash to one cell of global
table, what will you do? How can we put 2 different master count
anchors in one cell? If master count of 2 different objects can be
added up (but anyway I don't understand what sense in addition of
counters), what can we do with 2 different pointers to inner part?
Dmitriy V'jukov
Chris Thomasson
> On May 23, 8:35 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> You can store the master count anchors (e.g., in pc_sample.c) in a global
>> table....
>
> ???
> But if you have 2 different objects that hash to one cell of global
> table, what will you do?
I can post/e-mail you some fairly detailed pseudo-code if you want. Just let
me know.
Also, please keep in mind that a single master proxy reference can govern
multiple objects...
In other words, two collections that map to the same master anchor is no
problem. In fact, its the way things work wrt proxy collectors.
The proxy reference is tied to a proxy object in which multiple objects can
be covered.
Chris Thomasson
> can be covered.
For instance, you can acquire the master proxy reference on collection A,
therefore every single object that exists in collection A can be deferred
through it.
This works with pc_sample.c 100% guaranteed. The backlinks ensure it!
Again, I can post pseudo-code, if you interested ask.
Chris Thomasson
>> The proxy reference is tied to a proxy object in which multiple objects
>> can be covered.
>
> For instance, you can acquire the master proxy reference on collection A,
> therefore every single object that exists in collection A can be deferred
> through it.
Even if collections A-D map top the exact same master anchor, so be it.
That's fine.
Every object in collections A-D can be deferred through the same proxy...
Dmitriy Vyukov
> > ???
> > But if you have 2 different objects that hash to one cell of global
> > table, what will you do?
>
> I can post/e-mail you some fairly detailed pseudo-code if you want. Just let
> me know.
Yes, I want. I would be very appreciate. You can email me.
Dmitriy V'jukov
Chris Thomasson
[...]
Using pc_sample.c:
#define PDR_HASH_DEPTH() 128
#define PDR_DEPTH() (PDR_HASH_DEPTH() + 1)
static pc_t pxy_master[PDR_DEPTH()];
#define PXY_HASHPTR(__ptr) \
(((ptrdiff_t)(__ptr)) % PDR_HASH_DEPTH())
#define PXY_MASTER_HASH(__ptr) \
(&pxy_master[PXY_HASHPTR(__ptr)])
static user_collection_t g_col1;
static user_collection_t g_col2;
static user_collection_t g_col3;
void user_collection_iterate(user_collection_t* const _this) {
pc_t *master = PXY_MASTER_HASH(_this);
pc_deferred_t *pcd = pc_inc(master);
/* iterate read-only _this */
pc_dec(pcd);
}
void user_collection_defer(void *state) {
user_collection_node_t* const _this = state;
user_collection_node_free(_this);
}
void user_collection_pop(user_collection_t* const _this) {
user_collection_node_t *node;
pc_t *master = PXY_MASTER_HASH(_this);
global_hash_lock(_this);
/* pop node from _this into node */
global_hash_unlock(_this);
pc_defer(master, user_collection_defer, node);
}
void reader_threads() {
for(;;) {
user_collection_iterate(&g_col1);
user_collection_iterate(&g_col2);
user_collection_iterate(&g_col3);
}
}
void writer_remove_threads() {
for(;;) {
user_collection_pop(&g_col1);
user_collection_pop(&g_col2);
user_collection_pop(&g_col3);
}
}
/* writer add threads removed for brevity. Hint, you can take a proxy
reference for writer algorithms... */
Any thoughts?
;^)
Dmitriy Vyukov
> Using pc_sample.c:
>
> Any thoughts?
>
> ;^)
Thanks. I will try to examine.
Dmitriy V'jukov
Chris Thomasson
> "frege" <gottlo...@gmail.com> wrote in message
> news:1178680417....@e65g2000hsc.googlegroups.com...
>> On May 8, 8:08 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>>> "David Schwartz" <dav...@webmaster.com> wrote in message
>
>> do you (Chris) have a version where some_other_ref_counted_ptr might
>> also be in the middle of an assignment? In my version,
>> some_other_ref_counted_ptr has to be 'stable' during the assign (the
>> refcount can change, but what it points to cannot change).
>
> For the c++ version I separate the reference counting logic into two smart
> pointer types:
>
> http://appcore.home.comcast.net/vzoom/refcount/refcount.hpp
>
> vzsync::ptr::global
> vzsync::ptr::local
>
>
> You can have:
>
> static vzsync::ptr::global<foo> g_foo1 = new foo;
> static vzsync::ptr::global<foo> g_foo2 = new foo;
>
>
> multiple_threads() {
> for(;;) {
> g_foo1 = g_foo2;
the following line:
> g_foo2 = new foo;
should be:
vzsync::ptr::local<foo> l_foo = new g_foo1;
g_foo2 = l_foo;
> }
> }
>
> multiple_threads() {
> for(;;) {
> vzsync::ptr::local<foo> l_foo1 = g_foo1;
> vzsync::ptr::local<foo> l_foo2 = g_foo2;
> if (l_foo1 && l_foo2) {
> l_foo1->foo();
> l_foo2->foo();
> }
> }
> }
To sum up:
typedef vzsync::ptr::local<foo> foo_lptr;
typedef vzsync::ptr::global<foo> foo_gptr;
To store to a shared object:
static foo_gptr g_foo(new foo);
store {
foo_lptr l_foo(new foo);
g_foo = l_foo; // atomic
}
to load from a shared object:
load {
foo_lptr l_foo(g_foo); // atomic
if (l_foo) {
l_foo->do_something(...);
}
}