Strong vs. Normal Thread Safety.

90 views
Skip to first unread message

Chris Thomasson

unread,
May 6, 2007, 1:09:26 AM5/6/07
to

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

unread,
May 6, 2007, 1:31:51 AM5/6/07
to
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.

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

unread,
May 6, 2007, 4:10:57 AM5/6/07
to
"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 am
focusing on the data-structures that make up the reference counting
implementation.


Chris Thomasson

unread,
May 6, 2007, 4:11:59 AM5/6/07
to
"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.
> 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

unread,
May 6, 2007, 5:12:18 AM5/6/07
to
Normal thread safety is also referred to as Basic thread safety.


Gianni Mariani

unread,
May 6, 2007, 7:25:10 AM5/6/07
to
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.

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

unread,
May 6, 2007, 5:14:35 PM5/6/07
to
On May 5, 10:09 pm, "Chris Thomasson" <cris...@comcast.net> wrote:

> 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

unread,
May 6, 2007, 5:52:15 PM5/6/07
to
Chris Thomasson wrote:
> 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

unread,
May 6, 2007, 11:41:59 PM5/6/07
to
"David Schwartz" <dav...@webmaster.com> wrote in message
news:1178486075.0...@q75g2000hsh.googlegroups.com...

> On May 5, 10:09 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
[...]

>> 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

unread,
May 6, 2007, 11:43:40 PM5/6/07
to
"David Hopwood" <david....@industrial-designers.co.uk> wrote in message
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

unread,
May 7, 2007, 12:03:36 AM5/7/07
to
"David Schwartz" <dav...@webmaster.com> wrote in message
news:1178486075.0...@q75g2000hsh.googlegroups.com...
> On May 5, 10:09 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
[...]>> 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.

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

unread,
May 7, 2007, 12:14:39 AM5/7/07
to
"Gianni Mariani" <gi3n...@mariani.ws> wrote in message
news:463dbd39$0$9070$5a62...@per-qv1-newsreader-01.iinet.net.au...

> 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

unread,
May 7, 2007, 1:19:41 AM5/7/07
to
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, ...

DS

Chris Thomasson

unread,
May 7, 2007, 3:04:10 AM5/7/07
to
"David Schwartz" <dav...@webmaster.com> wrote in message
news:1178515181....@u30g2000hsc.googlegroups.com...

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

unread,
May 7, 2007, 3:05:30 AM5/7/07
to
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:5t6dnagQYKpAU6Pb...@comcast.com...

> "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

unread,
May 7, 2007, 3:07:03 AM5/7/07
to
"David Schwartz" <dav...@webmaster.com> wrote in message
news:1178515181....@u30g2000hsc.googlegroups.com...


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

unread,
May 7, 2007, 3:10:00 AM5/7/07
to
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:qtWdnXWlQLUXUqPb...@comcast.com...

> "David Schwartz" <dav...@webmaster.com> wrote in message
> news:1178515181....@u30g2000hsc.googlegroups.com...
[...]>> No, I don't. But it's uncommented and uses nonsense names, so it's
[...]
> 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

unread,
May 7, 2007, 3:14:16 AM5/7/07
to
[...]
> LOOK AT g_foo!!

In the first example.


Markus Elfring

unread,
May 7, 2007, 7:59:31 AM5/7/07
to
> 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.

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

unread,
May 7, 2007, 11:09:32 AM5/7/07
to
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?

--
David Hopwood <david....@industrial-designers.co.uk>

Chris Thomasson

unread,
May 7, 2007, 2:44:12 PM5/7/07
to
"David Hopwood" <david....@industrial-designers.co.uk> wrote in message
news:MiH%h.10227$1J....@fe1.news.blueyonder.co.uk...

> 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

unread,
May 7, 2007, 4:14:16 PM5/7/07
to
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. 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

unread,
May 7, 2007, 6:49:41 PM5/7/07
to
"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.
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

unread,
May 7, 2007, 6:51:15 PM5/7/07
to
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:4omdnQQV7JHrMaLb...@comcast.com...

> "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

unread,
May 7, 2007, 6:55:09 PM5/7/07
to
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:4omdnQQV7JHrMaLb...@comcast.com...

> "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

unread,
May 7, 2007, 6:56:44 PM5/7/07
to
> template<typename T>
> struct refcount {
> struct inner {
> T *m_ptr;
> int m_refs;
> };


void swap(T *ptr) {
// strong thread-safe atomic swap
}


>
> inner *m_inner;
> }


Chris Thomasson

unread,
May 7, 2007, 6:58:26 PM5/7/07
to
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:PtSdnWBuY8gjMKLb...@comcast.com...
^^^^^^^^^^^^^^^^^^^^^^^^

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

unread,
May 7, 2007, 7:02:00 PM5/7/07
to
"David Hopwood" <david....@industrial-designers.co.uk> wrote in message
news:MiH%h.10227$1J....@fe1.news.blueyonder.co.uk...

> 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

unread,
May 7, 2007, 7:09:50 PM5/7/07
to
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:UPadneIcedvh_6Db...@comcast.com...
>
[...]

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

unread,
May 7, 2007, 8:14:18 PM5/7/07
to

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

unread,
May 8, 2007, 1:39:43 AM5/8/07
to
"David Schwartz" <dav...@webmaster.com> wrote in message
news:1178583258.1...@q75g2000hsh.googlegroups.com...

>
> 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

unread,
May 8, 2007, 1:49:52 AM5/8/07
to
[...]

> 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

unread,
May 8, 2007, 1:53:02 AM5/8/07
to
I think I accidentally mailed this to you, sorry:

"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

unread,
May 8, 2007, 2:40:35 PM5/8/07
to
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 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

unread,
May 8, 2007, 6:56:08 PM5/8/07
to
"David Schwartz" <dav...@webmaster.com> wrote in message
news:1178649635....@e51g2000hsg.googlegroups.com...

> 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:

http://citeseer.ist.psu.edu/cache/papers/cs/25408/http:zSzzSzwww.sun.comzSzresearchzSzpeoplezSzdetlefszSzpaperszSz01-podc.pdf/detlefs01lockfree.pdf

http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PG01&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.html&r=1&f=G&l=50&s1=%2220060037026%22.PGNR.&OS=DN/20060037026&RS=DN/20060037026

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

unread,
May 8, 2007, 7:42:59 PM5/8/07
to
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). 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

unread,
May 8, 2007, 8:08:01 PM5/8/07
to
"David Schwartz" <dav...@webmaster.com> wrote in message
news:1178667779....@u30g2000hsc.googlegroups.com...

> 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

unread,
May 8, 2007, 8:10:01 PM5/8/07
to
David Schwartz wrote:
>
> 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

unread,
May 8, 2007, 11:13:37 PM5/8/07
to
On May 8, 8:08 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
> "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. 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

unread,
May 9, 2007, 5:52:27 AM5/9/07
to
On 9 май, 03:42, David Schwartz <dav...@webmaster.com> wrote:

> 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

unread,
May 9, 2007, 6:37:45 AM5/9/07
to
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.
>
>
> 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

unread,
May 9, 2007, 5:08:07 PM5/9/07
to
"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;
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

unread,
May 9, 2007, 6:44:46 PM5/9/07
to
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.


#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

unread,
May 9, 2007, 11:26:39 PM5/9/07
to

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

unread,
May 10, 2007, 2:22:02 AM5/10/07
to
"David Schwartz" <dav...@webmaster.com> wrote in message
news:1178767599.9...@e65g2000hsc.googlegroups.com...

>
> 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

unread,
May 10, 2007, 2:23:32 AM5/10/07
to

"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

unread,
May 10, 2007, 2:43:28 AM5/10/07
to
Sorry for all of the exclamation points...

But , man I know this race-condition is REAL!

:^(


Chris Thomasson

unread,
May 10, 2007, 3:01:47 AM5/10/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1178704347.6...@e51g2000hsg.googlegroups.com...

> On 9 май, 03:42, David Schwartz <dav...@webmaster.com> wrote:
>

Thank you Mr Vyukov, my friend.

:^)


Chris Thomasson

unread,
May 10, 2007, 3:02:39 AM5/10/07
to
"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
>>
>> > 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

unread,
May 10, 2007, 3:05:42 AM5/10/07
to
Strong Thread-Safety Is basically Analogous to Java References


Really!

:^)


Chris Thomasson

unread,
May 10, 2007, 4:14:11 AM5/10/07
to
"David Schwartz" <dav...@webmaster.com> wrote in message
news:1178667779....@u30g2000hsc.googlegroups.com...
[...]

> 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

unread,
May 11, 2007, 5:03:40 AM5/11/07
to
Since Your Austria C++ library has the ability to stare various Strong
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

unread,
May 11, 2007, 5:06:17 AM5/11/07
to
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:z9-dneDyCsJKrdnb...@comcast.com...

We can help you create a PDR, an possibly introduce it as a real aspect of
your library!


frege

unread,
May 12, 2007, 12:07:33 AM5/12/07
to
On May 9, 11:26 pm, David Schwartz <dav...@webmaster.com> wrote:

> 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

unread,
May 12, 2007, 12:14:45 AM5/12/07
to
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 - 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

unread,
May 12, 2007, 1:55:46 AM5/12/07
to
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. 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

unread,
May 14, 2007, 8:38:01 PM5/14/07
to
"frege" <gottlo...@gmail.com> wrote in message
news:1178943285.1...@l77g2000hsb.googlegroups.com...

> 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 -
Here are links to the source code:

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

unread,
May 14, 2007, 8:39:56 PM5/14/07
to
"David Schwartz" <dav...@webmaster.com> wrote in message
news:1178949346.0...@q75g2000hsh.googlegroups.com...

> 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

unread,
May 14, 2007, 8:41:25 PM5/14/07
to
...

> My documentation is almost complete; it should help clear things up. Did
> my
> description address some of your initial concerns?

http://appcore.home.comcast.net/vzoom/refcount/doc/

Dmitriy Vyukov

unread,
May 14, 2007, 11:51:53 PM5/14/07
to
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?
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

unread,
May 15, 2007, 4:26:04 AM5/15/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1179201113.2...@w5g2000hsg.googlegroups.com...

> 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

unread,
May 15, 2007, 4:34:46 AM5/15/07