topic Re: Thread implementation in Linux in Intel® Moderncode for Parallel Architectures

Thread implementation in Linux

Yasaman_G_Intel — Sat, 31 May 2003 07:18:25 GMT

A customer asks:

"The implementation of the following threading functions, InterlockedIncrement()& InterlockedDecrement() are available for MS Windows. Are these, or counterparts, available for Linux?"

The following article suggests that there is no such implementation. Has that changes since then? If not, what is a good solution. http://www.cs.helsinki.fi/linux/linux-kernel/2002-10/0314.html

Thanks for your help.

Re: Thread implementation in Linux

Intel_C_Intel — Sun, 01 Jun 2003 03:32:35 GMT

> A customer asks:
>
> "The implementation of the following threading
> functions,
[...MS-interlocked silliness...]
> are available for MS Windows.
> Are these, or counterparts, available for Linux?"

Low level "atomic.h" aside, ``not yet.''

>
> The following article suggests that there is no such
> implementation. Has that changes since then? If not,
> what is a good solution.
> http://www.cs.helsinki.fi/linux/linux-kernel/2002-10/0
> 14.html

A second problem is implementing a use-count mechanism to
control object lifetimes in a multi-threaded environment.
The two alternatives are to use mutexes or other synchronization
mechanisms to protect all addRef/release calls (very, very
expensive) or to use interlocked increment/decrement mechanisms.
Unfortunately, while Microsoft provides intrinsic
InterlockedIncrement/InterlockedDecrement functions that perform
atomic multiprocessor interlocked operations that correctly
return the result of the operation. Unfortunately, there
are no such functions available on Linux. Atomic.h provides
interlocked increment/decrement, but they don't return values.
Interestingly enough, Google couldn't find any example of
the Intel instruction sequences required to implement the
necessary atomic operations using the GNU assembler dialect.

For portable reference counting, you might want to take a look at "shared_ptr/weak_ptr and thread-safety" threads at <> and . I've recently injected the following (to both threads):

Alexander Terekhov wrote:
>
> Russell Hind wrote:
> >
> > Trevor Taylor wrote:
> > >
> > > Who? Me?
> > >
> >
> > I think Peter meant Alexander
>
> I got the message. I'll post refcount> typename integer_t> once I'll have some time for it. It won't include
> atomic<> implementation(s), however. ;-)

http://terekhov.de/pthread_refcount_t/experimental/refcount.cpp

regards,
alexander.

--
http://groups.google.com/groups?selm=3EC4F194.2DA8701C%40web.de

Re: Thread implementation in Linux

ClayB — Mon, 02 Jun 2003 22:47:24 GMT

Alexander -

I looked at the code first and thought "How can this work and use atomic increment/decrement if there is no support from the operating system?" The MS-interlocked functions must have this in order to ensure that the few assembly instructions needed to perform the operation are not swapped out of the processor. Then I looked at your "man" pages for the operations and realized the code was just part of something larger being planned that would get support for atomicity from the OS.

One thing that I found to be curious: I can understand why there is a special return value for when a counter has been decremented down to zero, but why would you want to know if a counter has been incremented to zero? If this is a counter, would it not start at zero or some other positive number?

Also, perhaps I'm unclear about the intended use of pthread_refcount_increment_positive, but why would you not allow this operation to increment a zero value? It seems clunky to make sure the first increment of a zero counter must be done with one function, but all the rest of the increments should be done with another.

-- clay

Re: Thread implementation in Linux

Intel_C_Intel — Tue, 03 Jun 2003 15:51:26 GMT

> Alexander -
>
> I looked at the code first and thought "How can this
> work and use atomic increment/decrement if there is
> no support from the operating system?"

Well, you don't really need "the operating system" for
thread-safe reference counting. All you need is LL/SC
or CAS things (plus memory barriers) meant to be
executed in the "user land"... AND *compilers* that
should also follow the rules with respect to memory
access reordering constraints.

> The
> MS-interlocked functions must have this in order to
> ensure that the few assembly instructions needed to
> perform the operation are not swapped out of the
> processor.

Really? Well, it's even more brain-damaged than I
thought previously, then.

> Then I looked at your "man" pages for the
> operations and realized the code was just part of
> something larger being planned that would get support
> for atomicity from the OS.

Not really. It's just a specification of plain C
reference counting API with a "non-blocking" option
that doesn't allow to parameterize the refcount object
with "thread_safety" policy and/or integer type to be
used for the count. The C++ "experimental" stuff allows
both these things and is a much better/powerful approach
than a plain-C pthread_refcount_t API. The idea is that
non-blocking pthread_refcount_t can be fully implemented
using refcount<> template.

>
> One thing that I found to be curious: I can
> understand why there is a special return value for
> when a counter has been decremented down to zero, but
> why would you want to know if a counter has been
> incremented to zero?

I don't know why. Neither increment nor add operations
do that. Are you sure that you're not confusing it with
pthread_refcount_increment_positive() (or refcount::
increment_if_not_min())?

> If this is a counter, would it
> not start at zero or some other positive number?

The C++ version starts at std::numeric_limits::
min() by default. The "refs" thing [see below] starts
both counts at "min() + 1".

>
> Also, perhaps I'm unclear about the intended use of
> pthread_refcount_increment_positive, but why would
> you not allow this operation to increment a zero
> value?

This is needed to support "weak" pointers. Take a look
at:

http://std.dkuug.dk/JTC1/SC22/WG21/docs/papers/2003/n1450.html
(A Proposal to Add General Purpose Smart Pointers to...)

Here's the "refs" thing that illustrates the point.

http://lists.boost.org/MailArchives/boost/msg48041.php

template
class refs /* noncopyable */ { 

  typedef refcount 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();
  }

};

Here's the refcount.cpp:

/* 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 
#include 
#include 

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
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
class refcount;

template
class is_nonnegative; // just to suppress gcc 3.2 warning

template<>
struct is_nonnegative {
  template
  static bool test(numeric) { return true; } 
};

template<>
struct is_nonnegative {
  template
  static bool test(numeric value) { return value >= 0; } 
};

template
class refcount {

  numeric m_value;

public:

  static numeric min() throw() {
    return std::numeric_limits::min();
  }

  static numeric max() throw() {
    return std::numeric_limits::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<:NUMERIC_LIMITS>::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<:NUMERIC_LIMITS>::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<:NUMERIC_LIMITS>::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
class refcount {

  atomic m_value;

  template
  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
  bool subtract(numeric value, min_store_msync msm, attempt_update_msync aum) 
        throw(std::underflow_error) {
    assert(is_nonnegative<:NUMERIC_LIMITS>::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::min();
  }

  static numeric max() throw() {
    return std::numeric_limits::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<:NUMERIC_LIMITS>::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<:NUMERIC_LIMITS>::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);
  }

};

Questions? Comments? TIA.

regards,
alexander.

Re: Thread implementation in Linux

ClayB — Wed, 04 Jun 2003 00:41:39 GMT

> Really? Well, it's even more brain-damaged than I
> thought previously, then.

No comment on the state of MS Windows, but I must be a bit brain damaged not to realize the "simpler" solution. I'm used to looking at things in a bigger picture way when the details are what should really be focused on. (After banging my head around a problem for a while, this tends to sink in until next time. :-)

> > One thing that I found to be curious: I can
> > understand why there is a special return value for
> > when a counter has been decremented down to zero,
> but
> > why would you want to know if a counter has been
> > incremented to zero?
>
> I don't know why. Neither increment nor add
> operations
> do that. Are you sure that you're not confusing it
> with
> pthread_refcount_increment_positive() (or refcount::
> increment_if_not_min())?

Yes, looking more closely at the specification, this does refer to pthread_refcount_increment_positive(). I'll look over the citations you have listed to see if I can get a better understanding of the need and use of these routines.

-- clay

Re: Thread implementation in Linux

Yasaman_G_Intel — Wed, 04 Jun 2003 02:36:17 GMT

Folks,
This is a great discussion :-)

To go back to the original question & the suggestion on using the atomic.h file, how one would implement this API? Does anyone have a sample code? What I am looking for is the implementation of similar function calls as InterlockIncrement() & InterlockDecrement() within Linux. Is anyone taking initiatives on writing these APIs in Linux?

Thanks for your help.
--Yasaman

Re: Thread implementation in Linux

davids — Wed, 11 Jun 2003 14:28:30 GMT

It is trivial to implement them with a global mutex. The funny thing is, the cost is only about twice as much as if you do it with inline assembly. Basically, it comes down to one synchronizing operation (if you do it the 'right' way) versus two synchronizing operations (if you lock/unlock a mutex).

Amusingly, the WIN32 implementation of InterlockedIncrement seems to be very slow. I think it's because it doesn't inline and requires a function call.

Re: Thread implementation in Linux

davids — Fri, 20 Jun 2003 05:26:39 GMT

ClayB writes:
One thing that I found to be curious: I can understand why there is a special return value for when a counter has been decremented down to zero, but why would you want to know if a counter has been incremented to zero? If this is a counter, would it not start at zero or some other positive number?

I use this a lot. I set a variable to '-1' to mean 'queue empty'. Threads that queue work do an InterlockedIncrement to the count variable. If it returns zero, they know they need to dispatch a thread to serve the queue. The dispatch thread sets the variable back to '-1', checks one more time to make sure there's no work, and then returns.

DS

Re: Thread implementation in Linux

goanuj — Sat, 14 Aug 2004 07:34:18 GMT

ok, so is there or isn't there some way to provide for atomic instructions?

I really wish POSIX would get off their butts and provide a standard for this. It can be a complicated problem and every os/architecture does it a different way.

for reference counting on a a n-way box (where n is 2 or greater) is __extremely__ important for users of STLport std::wrope and std::crope(which uses reference counting all over the place)

we tracked down a 50% performance bug to STLPort for HPUX using locks instead of atomic instructions for reference counting.

I would really like Intel to step up to the plate and ask POSIX to specify a standard API for a couple instructions. These are very similar to the AIX API and solaris and hpux also have very similar ways of atomically incrementing and decrementing ints, longs, shorts. There should also be ways to safely compare/exchange pointers instead of casting to (int*, long*) which will cause problems on 32,64 bit operating systems.

int fetch_and_add();
uint fetch_and_and();
uint fetch_and_or();
boolean_t compare_and_swap();
long fetch_and_addlp();
ulong fetch_and_andlp();
ulong fetch_and_orlp();
boolean_t compare_and_swaplp();
ushort fetch_and_add_h();

Re: Thread implementation in Linux

goanuj — Sat, 14 Aug 2004 14:19:50 GMT

oi, I read through my post, it is completely orthagonal to the discussion. *sigh* this stuff is sometimes over my head. anyways, I'd revise my previous post if I could (get a better forum Intel http://www.phpbb.com/) but instead i'll have to modify what I asked for.

Though atomic instructions can be quite complicated to use (with great power comes great responsibility) every single operating system seems to offer some variation of the atomic_increment, atomic_increment, and atomic_swap (even though it could possibly for programmers to use these instructions w/o knowledge of their full impact)

It would still nice for POSIX to provide an API for vendors to adhere to, I am honest to god sick and tired of dealing w/ atomic instructions.

On a completely unrelated note do people here code against kdb/k?

Re: Thread implementation in Linux

Chris_M__Thomasson — Sun, 15 Aug 2004 03:42:51 GMT

http://groups.google.com/groups?selm=kqUDc.129305%24Sw.117350%40attbi_s51&rnum=8

There's my stuff.