Boost weak_ptr
Joe Seigh
need weak_ptr to implement thinks like object caching.
Except in Java you don't need weak pointers to implement caching in it.
And in C++ you can use atomic_ptr to implement caching w/o weak pointer
capability.
Anyway, using Boost's weak_ptr you'd access an object cache using something
like the following I think.
weak_ptr<T> wp; // part of cached object collection
shared_ptr<T> sp; // thread local shared ptr
// somewhere in a method accessing cached objects
if ((sp = cc.wp.lock()) == 0) {
lock(); // get collection lock
cc.sp = ...; // collect shared_ptr updated to a new copy of object
cc.wp = cc.sp; // update weak pointer
sp = cc.cp; // update local shared pointer
unlock(); // release collection lock
}
// use cached object...
Look like DCL? "thread-safe as int" doesn't save them here AFAICT.
Joe Seigh
Alexander Terekhov
Joe Seigh wrote:
[...]
> Look like DCL?
No.
regards,
alexander.
Joe Seigh
Alexander Terekhov wrote:
>
> Joe Seigh wrote:
> [...]
> > Look like DCL?
>
> No.
>
Another thread can allocate an object which can then be accessed by
another thread via the newly reset weak_ptr. There would need to
be a memory barrier or something to guarantee proper visibility.
Joe Seigh
SenderX
> Except in Java you don't need weak pointers to implement caching in it.
> And in C++ you can use atomic_ptr to implement caching w/o weak pointer
> capability.
It looks like dcl...
It would be nice to have true atomic pointers that don't rely on dwcas. I
believe you can do that with a single hazard pointer per-thread, and a
normal cas... You could use strong ll/sc logic, emulated with cas, to modify
the reference count. The atomic_ptr_ref's would be protected with the hazard
pointer...
pseudo-code:
A ll operation would go something like:
atomic_ptr_ref* ll( volatile atomic_ptr_ref **ppState )
{
atomic_ptr_ref *pLocal;
volatile atomic_ptr_ref **ppHazard = GetAtomicPtrHazard( 0 );
do
{
*ppHazard = *ppState;
pLocal = *ppState;
}
while ( pLocal != *ppHazard );
return pLocal;
}
And the sc would go:
atomic_ptr_ref* sc( volatile atomic_ptr_ref **ppState, atomic_ptr_ref
*pStoreState )
{
atomic_ptr_ref *pLocal, *pNew;
volatile atomic_ptr_ref **ppHazard = GetHazardPtr( 0 );
pLocal = *ppState;
if ( pLocal != *ppHazard )
{
*ppHazard = 0;
return 0;
}
pNew = AllocAtomicPtr();
/* atomic_ptr_ref objects are very small */
*pNew = *pStoreState;
if ( cas( ppState, pLocal, pNew ) != pLocal )
{
*ppHazard = 0;
FreeAtomicPtr( pNew );
return 0;
}
*ppHazard = 0;
smr_free( pLocal, FreeAtomicPtr );
return pNew;
}
The AllocAtomicPtr() and FreeAtomicPtr() would first try to allocate or free
atomic_ptr_ref's from/to tls, and
if the local pool was empty/full it would go for the global pools.
In order to modify the reference count, you would do this:
atomic_ptr_ref* AtomicPtrAdjust( volatile atomic_ptr_ref **ppRefs, int
iCount )
{
atomic_ptr_ref *pLocal, Store;
do
{
pLocal = ll( ppRefs );
/* Start of garbage collected reigon for pLocal */
Store = *pLocal;
Store.Refs += iCount;
pLocal = sc( ppRefs, &Store );
/* End of garbage collected reigon for pLocal */
}
while ( ! pLocal )
if ( ! Store.Refs )
{
/* Quiescent period */
delete Store.pUserObject;
return 0;
}
/* The reference was modified */
/* If iCount > 0, pLocal is now protected by the reference count */
/* If iCount < 0, pLocal was released by this thread */
return pLocal;
}
When a quiescent period is hit for the object protected by the
atomic_ptr_ref, the object is deleted on the spot. Only the atomic_ptr_refs
go through smr.
This would probably work...
http://www.research.ibm.com/people/m/michael/disc-2004.pdf
:)
SenderX
> Except in Java you don't need weak pointers to implement caching in it.
> And in C++ you can use atomic_ptr to implement caching w/o weak pointer
> capability.
It looks like dcl...
Joe Seigh
SenderX wrote:
>
> > Look like DCL? "thread-safe as int" doesn't save them here AFAICT.
>
> > Except in Java you don't need weak pointers to implement caching in it.
> > And in C++ you can use atomic_ptr to implement caching w/o weak pointer
> > capability.
>
> It looks like dcl...
>
> It would be nice to have true atomic pointers that don't rely on dwcas. I
> believe you can do that with a single hazard pointer per-thread, and a
> normal cas... You could use strong ll/sc logic, emulated with cas, to modify
> the reference count. The atomic_ptr_ref's would be protected with the hazard
> pointer...
>
or RCU (which I've mentioned before) or any other form of GC. I'm not sure how
much it buys you since local_ptr has about as little overhead as anything and
most of the access would be via local_ptr.
Joe Seigh
Joe Seigh
SenderX wrote:
>
> This would probably work...
>
> http://www.research.ibm.com/people/m/michael/disc-2004.pdf
>
Check out Nonblocking k-compare-single-swap here
http://research.sun.com/people/moir/Papers/p004-luchangco.pdf
Haven't really figured it all out yet, but I think "obstruction-free"
really means "I hope livelock doesn't occur".
Joe Seigh
SenderX
sure how
> much it buys you since local_ptr has about as little overhead as anything
and
> most of the access would be via local_ptr.
Very true. I think the major benefit would be the compatibility with normal
cas.
SenderX
> Haven't really figured it all out yet, but I think "obstruction-free"
> really means "I hope livelock doesn't occur".
Livelock should occur in their ll/sc code...
A thread makes a reservation by incrementing its local tag, and replaces the
original value with via. cas. This changes the shared location "before" the
store-conditionals cas can be executed.
Two threads can livelock like this:
ThreadA
---------------
a1: cas in local tag
a2: cas again comparing tag to local tag.
a3: loop to a1 if a2 fails
ThreadB
---------------
b1: cas in local tag
b2: cas again comparing tag to local tag.
b3: loop to a1 if a2 fails
a1
b1 * will cause a2 cas to fail
a2
a3
a1 * will cause b2 cas to fail
Start of livelock cycle:
b2
b3
b1 * will cause a2 to fail
a2
a3
a1 * will cause b2 to fail
b2
b3
b1 * ect.
ect...
Yikes!
:O
SenderX
> ---------------
> b1: cas in local tag
> b2: cas again comparing tag to local tag.
> b3: loop to a1 if a2 fails
^^^^^^^^^^^^^^
I mean:
b3: loop to b1 if b2 fails
Joe Seigh
SenderX wrote:
>
> > Haven't really figured it all out yet, but I think "obstruction-free"
> > really means "I hope livelock doesn't occur".
>
> Livelock should occur in their ll/sc code...
>
I think they're saying that in practice, under some conditions at least,
it's not a problem. "obstruction-free" does sound better than live-lock.
A simple compare and swap is obstruction-free. In practice the contention
level has to get extremely high before there are problems.
Joe Seigh
SenderX
> level has to get extremely high before there are problems.
>
True.
Alexander Terekhov
Joe Seigh wrote:
[...]
> Another thread can allocate an object which can then be accessed by
> another thread via the newly reset weak_ptr.
Nope. Not allowed (without locking). boost::weak_ptr's thread-safety
is "basic", not "strong".
regards,
alexander.
Joe Seigh
If you use locking, there is no need for weak_ptr. Boost thread safety
is basic alright, basically lame. It's not well defined and Boost
architects aren't all that thread savvy.
Joe Seigh
Alexander Terekhov
Joe Seigh wrote:
>
> Alexander Terekhov wrote:
> >
> > Joe Seigh wrote:
> > [...]
> > > Another thread can allocate an object which can then be accessed by
> > > another thread via the newly reset weak_ptr.
> >
> > Nope. Not allowed (without locking). boost::weak_ptr's thread-safety
> > is "basic", not "strong".
> >
> If you use locking, there is no need for weak_ptr. Boost thread safety
> is basic alright, basically lame. It's not well defined
It IS well-defined.
> and Boost
> architects aren't all that thread savvy.
No comment. Uhmm,
http://groups.google.com/groups?selm=3ECCB611.97DC2280%40web.de
;-)
regards,
alexander.