|
|
Boost : |
From: Alexander Terekhov (terekhov_at_[hidden])
Date: 2003-06-02 14:24:28
"William E. Kempf" wrote:
>
> Alexander Terekhov said:
> >
> > Trevor Taylor wrote:
> > [...]
> >> Why wait? With so many people contributing to boost, why not introduce
> >> a pthread_refcount_t into into boost threads (or is there one
> >> already?), provide a default implementation equivalent to what
> >> shared_ptr does now,
> >
> > Nah. atomic<> based stuff would surely be much better than what
> > shared_ptr does now, I think.
> >
> >> and let the platform experts provide the optimal specialisations.
> >
> > http://groups.google.com/groups?selm=3EC4F194.2DA8701C%40web.de
> > (Subject: Re: Is this thread-safe on multi-processor Win32?)
> >
> > regards,
> > alexander.
> >
> > P.S. ``Where's Bill?'' ;-)
>
> Please, drop the adversarial tone in your posts.
I can't. Really.
> It's rude at best.
Sorry for that; well, try to not take it seriously.
>
> I was on vacation, but I'm hardly ignoring any of this. I had an atomic
> class in Boost.Threads pre-review, but it was removed because it needed a
> lot more research and effort than I had time for in that release. I'm
> trying to track the efforts you've been doing in this area, but you
> scatter things so much with "see this link" type posts that it's
> difficult.
Okay. <copy&paste>
/* This is my experimental C++ take on >UNOFFICIAL< "pthread_refcount_t"-API
----------------------------------------------------------------------------
File: refcount.cpp
Originally written by Alexander Terekhov and released into the public domain.
This may be used for any purposes whatsoever without acknowledgment. Thanks
for the assistance and support of Pavel Vasiliev, Mike Mowbray, c.p.t.-group
participants and everyone contributing, testing, and using this code.
http://groups.google.com/groups?threadm=3E4820EE.6F408B25%40web.de
(Subject: Re: threadsafe reference counting)
----------------------------------------------------------------------------
*/
#include <limits>
#include <cassert>
#include <stdexcept>
struct msync {
enum hlb_t { hlb }; // hoist-load barrier
enum ddhlb_t { ddhlb }; // hoist-load barrier with data-dependency "hint"
enum hsb_t { hsb }; // hoist-store barrier
enum slb_t { slb }; // sink-load barrier
enum ddslb_t { ddslb }; // sink-load barrier with data-dependency "hint"
enum ssb_t { ssb }; // sink-store barrier
enum acq_t { acq }; // hoist-load + hoist-store barrier
enum rel_t { rel }; // sink-load + sink-store barrier
enum none_t { none }; // naked
};
template<class T>
struct atomic { //
atomic(T n) : t(n) { }
T load(msync::none_t) const { return t;}
T load(msync::hlb_t) const { return t; }
T load(msync::ddhlb_t) const { return t; }
void store(T n, msync::none_t) { t = n; }
void store(T n, msync::ssb_t) { t = n; }
void store(T n, msync::acq_t) { t = n; }
void store(T n, msync::rel_t) { t = n; }
bool attempt_update(T o,T n, msync::none_t) { return (t == o) ? (t=n, true) : false; }
bool attempt_update(T o,T n, msync::ssb_t) { return (t == o) ? (t=n, true) : false; }
bool attempt_update(T o,T n, msync::acq_t) { return (t == o) ? (t=n, true) : false; }
bool attempt_update(T o,T n, msync::rel_t) { return (t == o) ? (t=n, true) : false; }
T t;
};
enum thread_safety { unsafe, basic }; // strong aside for a moment
template<typename numeric, thread_safety scheme_thread_safety>
class refcount;
template<bool is_signed>
class is_nonnegative; // just to suppress gcc 3.2 warning
template<>
struct is_nonnegative<false> {
template<typename numeric>
static bool test(numeric) { return true; }
};
template<>
struct is_nonnegative<true> {
template<typename numeric>
static bool test(numeric value) { return value >= 0; }
};
template<typename numeric>
class refcount<numeric, unsafe> {
numeric m_value;
public:
static numeric min() throw() {
return std::numeric_limits<numeric>::min();
}
static numeric max() throw() {
return std::numeric_limits<numeric>::max();
}
refcount(numeric initial_value = min()) throw() :
m_value(initial_value) {
}
numeric get() const throw() {
return m_value;
}
void set(numeric value) throw() {
m_value = value;
}
void increment() throw() {
assert(max() > m_value);
++m_value;
}
void add(numeric value) throw(std::overflow_error) {
assert(is_nonnegative<std::numeric_limits<numeric>::is_signed>::test(value));
if (max() - value < m_value)
throw std::overflow_error("refcount::add(): overflow");
m_value += value;
}
bool increment_if_not_min() throw() {
assert(max() > m_value);
if (min() == m_value)
return false;
++m_value;
return true;
}
bool add_if_not_min(numeric value) throw(std::overflow_error) {
assert(is_nonnegative<std::numeric_limits<numeric>::is_signed>::test(value));
if (max() - value < m_value)
throw std::overflow_error("refcount::add_if_not_min(): overflow");
if (min() == m_value)
return false;
m_value += value;
return true;
}
bool decrement() throw() {
assert(min() < m_value);
return min() < --m_value;
}
bool decrement(msync::acq_t) throw() {
return decrement();
}
bool decrement(msync::rel_t) throw() {
return decrement();
}
bool decrement(msync::none_t) throw() {
return decrement();
}
bool subtract(numeric value) throw(std::underflow_error) {
assert(is_nonnegative<std::numeric_limits<numeric>::is_signed>::test(value));
if (min() + value > m_value)
throw std::underflow_error("refcount::subtract(): underflow");
return min() < (m_value -= value);
}
bool subtract(numeric value, msync::acq_t) throw(std::underflow_error) {
return subtract(value);
}
bool subtract(numeric value, msync::rel_t) throw(std::underflow_error) {
return subtract(value);
}
bool subtract(numeric value, msync::none_t) throw(std::underflow_error) {
return subtract(value);
}
};
template<typename numeric>
class refcount<numeric, basic> {
atomic<numeric> m_value;
template<typename min_store_msync, typename attempt_update_msync>
bool decrement(min_store_msync msm, attempt_update_msync aum) throw() {
numeric val;
do {
val = m_value.load(msync::none);
assert(min() < val);
if (min() + 1 == val) {
m_value.store(min(), msm);
return false;
}
} while (!m_value.attempt_update(val, val - 1, aum));
return true;
}
template<typename min_store_msync, typename attempt_update_msync>
bool subtract(numeric value, min_store_msync msm, attempt_update_msync aum)
throw(std::underflow_error) {
assert(is_nonnegative<std::numeric_limits<numeric>::is_signed>::test(value));
numeric val;
do {
val = m_value.load(msync::none);
if (min() + value > val)
throw std::underflow_error("refcount::subtract(): underflow");
if (min() + value == val) {
m_value.store(min(), msm);
return false;
}
} while (!m_value.attempt_update(val, val - value, aum));
return true;
}
public:
static numeric min() throw() {
return std::numeric_limits<numeric>::min();
}
static numeric max() throw() {
return std::numeric_limits<numeric>::max();
}
refcount(numeric initial_value = min()) throw() :
m_value(initial_value) {
}
numeric get() const throw() {
return m_value.load(msync::none);
}
void set(numeric value) throw() {
m_value.store(value, msync::none);
}
void increment() throw() {
numeric val;
do {
val = m_value.load(msync::none);
assert(max() > val);
} while (!m_value.attempt_update(val, val + 1, msync::none));
}
void add(numeric value) throw(std::overflow_error) {
assert(is_nonnegative<std::numeric_limits<numeric>::is_signed>::test(value));
numeric val;
do {
val = m_value.load(msync::none);
if (max() - value < val)
throw std::overflow_error("refcount::add(): overflow");
} while (!m_value.attempt_update(val, val + value, msync::none));
}
bool increment_if_not_min() throw() {
numeric val;
do {
val = m_value.load(msync::none);
assert(max() > val);
if (min() == val)
return false;
} while (!m_value.attempt_update(val, val + 1, msync::none));
return true;
}
bool add_if_not_min(numeric value) throw(std::overflow_error) {
assert(is_nonnegative<std::numeric_limits<numeric>::is_signed>::test(value));
numeric val;
do {
val = m_value.load(msync::none);
if (max() - value < val)
throw std::overflow_error("refcount::add(): overflow");
if (min() == val)
return false;
} while (!m_value.attempt_update(val, val + value, msync::none));
return true;
}
bool decrement() throw() {
return decrement(msync::acq, msync::rel);
}
bool decrement(msync::acq_t) throw() {
return decrement(msync::acq, msync::none);
}
bool decrement(msync::rel_t) throw() {
return decrement(msync::none, msync::rel);
}
bool decrement(msync::none_t) throw() {
return decrement(msync::none, msync::none);
}
bool subtract(numeric value) throw(std::underflow_error) {
return subtract(value, msync::acq, msync::rel);
}
bool subtract(numeric value, msync::acq_t) throw(std::underflow_error) {
return subtract(value, msync::acq, msync::none);
}
bool subtract(numeric value, msync::rel_t) throw(std::underflow_error) {
return subtract(value, msync::none, msync::rel);
}
bool subtract(numeric value, msync::none_t) throw(std::underflow_error) {
return subtract(value, msync::none, msync::none);
}
};
</copy&paste>
Now, and for the "refs" thing we can use something along the lines of:
template<typename T, typename numeric, thread_safety scheme_thread_safety>
class refs /* noncopyable */ {
typedef refcount<numeric, scheme_thread_safety> count;
count m_strong_count, m_weak_count;
T * m_p; // to do: no msync for strong counting needed for "T const"
/* ... */ // to do: no msync for weak counting needed for immutable *this
// (counts aside, of course)
void destruct_object() {
// deleter...
delete m_p;
}
void destruct_self() {
delete this;
}
public:
refs(T * p) throw() : m_strong_count(count::min() + 1),
m_weak_count(count::min() + 1),
m_p(p) {
}
~refs() throw() {
/* ... */
}
//*** Called by existing "strong_ptr".
void acquire_strong() throw() {
m_strong_count.increment();
}
void release_strong() throw() {
if (!m_strong_count.decrement()) {
destruct_object();
if (!m_weak_count.decrement(msync::rel))
destruct_self();
}
}
void acquire_weak_from_strong() throw() {
acquire_weak();
}
//*** Called by existing "weak_ref".
void acquire_weak() throw() {
m_weak_count.increment();
}
void release_weak() throw() {
if (!m_weak_count.decrement(msync::acq))
destruct_self();
}
bool acquire_strong_from_weak() throw() {
return m_strong_count.increment_if_not_min();
}
};
> If you can write a summary paper or even provide a base
> implementation with thorough documentation, I'd definately be interested.
Well, I'm basically done with "introduction". Here we go: <Forward Inline>
-------- Original Message --------
Message-ID: <3EDB59F3.982399EB_at_[hidden]>
Newsgroups: comp.programming.threads
Subject: Re: using atomic_ptr for a lock-free instance once algo?
References: ... <%aICa.21085$DV.25030_at_[hidden]>
SenderX wrote:
>
> > The acquire/release semantic are associated with the external pointer load
> and store
> > actions as observed by the program. Nothing to do with the cas operations
> since
> > atomic_ptr's are atomic and are safe without them but would then be about
> as useful
> > as pre-JSR 133 references.
>
> Is that why Alex says that the server 2003
> InterlockedCompareExchangeAcquire/Release API's are brain-damaged?
MS interlocked stuff is totally brain-damaged because it *DOESN'T*
1. extend C99's <stdint.h> with:
— atomic integer types having certain exact widths;
— atomic integer types having at least certain specified widths;
— atomic fastest integer types having at least certain specified widths;
— atomic integer types wide enough to hold pointers to objects;
— atomic integer types having greatest width.
providing "interlocked" function like macros with various memory
synch semantics for atomic operations.
2. introduce a "plusified" version of <stdint.h> with atomic integers
(<stdint> would be a good name for it, probably).
3. introduce <atomic> header that would provide a C++ <atomic>
template covering scalar types (based on "certain", or "least",
or "fastest" integers as optionally specified template argument)
via atomic<> specializations ala numeric_limits<> ones.
regards,
alexander.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk