Re: A race-condition in a SUN paper by Detlefs on reference counting...

"Greg Herlihy" <greghe@xxxxxxx> wrote in message news:c1ca49f2-5aed-426e-8506-e60da294d9e2@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Apr 4, 6:55 am, "Chris Thomasson" <cris...@xxxxxxxxxxx> wrote:
Here is the paper in question:

http://citeseer.ist.psu.edu/cache/papers/cs/25408/http:zSzzSzwww.sun....

on page 8 they present pseudo-code. Here is the function:
___________________________________________________________
void LFRCLoad(SNode **A, SNode **dest) {
1 SNode *a, *olddest = *dest;
2 long r;
3 while (true) {
4 a = *A;
5 if (a == Null) {
6 *dest = Null;
7 break;
}
8 r = a->rc;
9 if (DCAS(A, &a->rc, a, r, a, r+1)) {
10 *dest = a;
11 break;
}
}
12 LFRCDestroy(olddest);}

___________________________________________________________

AFAICT, this will not work at all. The reference count can be dropped to
zero right before 'line 8'. Then it goes BOOM!

There is a note in Section 5 of the paper that explains why "a"'s
reference count will not fall to zero while LFRCLoad() is executing:

"(Note that there is no risk that the object containing the pointer
being read by LFRCLoad is freed during the execution of LFRCLoad
because the calling thread has a pointer to this object that is not
destroyed during the execution of LFRCLoad, so its reference count
cannot fall to zero.)"

In other words, "a" will not free until "A" is freed - and "A" will
not be freed as long as LFRCLoad() is executing - because LFRCLoad()'s
caller will still be holding a reference to "A" (namely, the "A"
argument that was passed to LFRCLoad () when the function was called).

AFAICT, LFRCLoad allows a thread to load a reference from a shared location. In other words:


static SNode* g_shared_location = new SNode;




The reference count of the object in the shared location is 1. Now, lets say a thread wants to grab a reference:


void Thread() {
SNode* local_location = NULL;
LFRCLoad(&g_shared_location, &local_location);
[...];
}



The calling thread does not own a reference to the object in g_shared_location before it calls LFRCLoad. I thought that this was legal because their description of LFRCLoad goes like this:

"LFRCLoad(p,A) A is a pointer to a shared memory location that contains a pointer, and p is a pointer to a local pointer variable. The effect is to load the value from the location pointed to by A into the variable
pointed to by p."

This implies that the algorithm is strongly thread-safe such that a thread can acquire a reference to an object in a shared location that it previously did not own a reference to. Just like in the example I gave. According to the note you cited, well, that means that their algorithm is only provides basic thread-safety such that a thread can only acquire a reference to an object that it already owns a reference to. Is my example breaking the rules? I was always under the impression that this algorithm was strongly thread-safe due to the wording in the description of the LFRCLoad function.

If I am wrong, and this algorithm is only has basic thread-safety, then I know why they put a patent application out on a counting algorithm with strong-thread safety. That algorithm was invented by Joe Seigh:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/f2c94118046142e8

SUN is trying to patent Joe's work. I was wondering why they would try and patent (20060037026) a new reference count algorithm when that already had one. Its because the one they had was not atomically thread-safe.

Here is some more information on strong-thread safety:

http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2007/n2297.html#atomic


It looks like they are going to add this feature to shared_ptr. Won't that be nice?

:^)

.

Relevant Pages

  • Re: A race-condition in a SUN paper by Detlefs on reference counting...
    ... zero right before 'line 8'. ... reference count will not fall to zero while LFRCLoadis executing: ... "(Note that there is no risk that the object containing the pointer ... being read by LFRCLoad is freed during the execution of LFRCLoad ...
    (comp.programming.threads)
  • Re: A race-condition in a SUN paper by Detlefs on reference counting...
    ... reference count will not fall to zero while LFRCLoadis executing: ... being read by LFRCLoad is freed during the execution of LFRCLoad ... know what exactly pointer LFRCLoad will load from A. ...
    (comp.programming.threads)
  • Re: Question on LSP
    ... Sure, the developer must keep track of which type has been assigned to each pointer to manage complexity in creating the design, which is why the 'T' is in T*. ... Subtyping is a relation which does not ... Those object types are completely orthogonal to the semantics of being an object reference. ... aggregate references, is the aggregate of referenced objects or target ...
    (comp.object)
  • Re: Question on LSP
    ... Because construction paradigms have different goals. ... But that has nothing to do with what a pointer type ... But that does not mean that the semantics of an object reference is ... aggregate references, is the aggregate of referenced objects or target ...
    (comp.object)
  • Re: Modifying Class Object
    ... Before I start, note we're talking about semantics, not ... For example, as I used as reference in my first posting, the Java language spec. ... A pointer stores a reference to something. ...
    (comp.lang.python)