lib/c++/stlport/lock_free_slist.h

   1 /*
   2  * Copyright (c) 1997-1999
   3  * Silicon Graphics Computer Systems, Inc.
   4  *
   5  * Copyright (c) 1999
   6  * Boris Fomitchev
   7  *
   8  * This material is provided "as is", with absolutely no warranty expressed
   9  * or implied. Any use is at your own risk.
  10  *
  11  * Permission to use or copy this software for any purpose is hereby granted
  12  * without fee, provided the above notices are retained on all copies.
  13  * Permission to modify the code and to distribute modified code is granted,
  14  * provided the above notices are retained, and a notice that the code was
  15  * modified is included with the above copyright notice.
  16  *
  17  */
  18
  19 #ifndef _STLP_LOCK_FREE_SLIST_H
  20 #define _STLP_LOCK_FREE_SLIST_H
  21
  22 #if defined(_STLP_PTHREADS)
  23 #  include <pthread.h>
  24
  25 #  if defined (__GNUC__) && defined (__i386__)
  26
  27 #    define _STLP_HAS_ATOMIC_FREELIST
  28 /**
  29  * Class that implements a non-blocking and thread-safe freelist.
  30  * It is used for the lock-free node allocation engine.
  31  *
  32  * @author felixw@inin.com
  33  */
  34 class _STLP_atomic_freelist {
  35 public:
  36   /**
  37    * Type representing items of the freelist
  38    */
  39   struct item {
  40     item* _M_next;
  41   };
  42
  43   _STLP_atomic_freelist() {
  44     // Statically assert layout of member is as expected by assembly code
  45     _STLP_STATIC_ASSERT(sizeof(_M) == 8)
  46     _M._M_data._M_top       = 0;
  47     _M._M_data._M_sequence  = 0;
  48   }
  49
  50   /**
  51    * Atomically pushes the specified item onto the freelist.
  52    *
  53    * @param __item [in] Item to add to the front of the list
  54    */
  55   void push(item* __item) {
  56     // NOTE: GCC uses ebx as the PIC register for globals in shared libraries.
  57     //       The GCC version I'm using (3.4.1) won't temporarily spill it if it's
  58     //       used as input, output, or clobber.  Instead, it complains with a
  59     //       "can't find a register in class `BREG' while reloading `asm'" error.
  60     //       This is probably a compiler bug, but as the cmpxchg8b instruction
  61     //       requires ebx, I work around this here by using ecx for the '__item'
  62     //       input and spilling ebx into edi.  This also precludes us from using
  63     //       a "m" operand for the cmpxchg8b argument (GCC might think it can make
  64     //       it relative to ebx).  Instead, we're using esi for the address of _M_data.
  65     //
  66     int __tmp1;     // These dummy variables are used to tell GCC that the eax, ecx,
  67     int __tmp2;     // and edx registers will not have the same value as their input.
  68     int __tmp3;     // The optimizer will remove them as their values are not used.
  69     __asm__ __volatile__
  70       ("       movl       %%ebx, %%edi\n\t"
  71        "       movl       %%ecx, %%ebx\n\t"
  72        "L1_%=: movl       %%eax, (%%ebx)\n\t"     // __item._M_next = _M._M_data._M_top
  73        "       leal       1(%%edx),%%ecx\n\t"     // new sequence = _M._M_data._M_sequence + 1
  74        "lock;  cmpxchg8b  (%%esi)\n\t"
  75        "       jne        L1_%=\n\t"              // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
  76        "       movl       %%edi, %%ebx"
  77       :"=a" (__tmp1), "=d" (__tmp2), "=c" (__tmp3)
  78       :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "c" (__item), "S" (&_M._M_data)
  79       :"edi", "memory", "cc");
  80   }
  81
  82   /**
  83    * Atomically removes the topmost item from the freelist and returns a
  84    * pointer to it.  Returns NULL if the list is empty.
  85    *
  86    * @return Item that was removed from front of list; NULL if list empty
  87    */
  88   item* pop() {
  89     item*   __result;
  90     int     __tmp;
  91     __asm__ __volatile__
  92       ("       movl       %%ebx, %%edi\n\t"
  93        "L1_%=: testl      %%eax, %%eax\n\t"       // _M_top == NULL?
  94        "       je         L2_%=\n\t"              // If yes, we're done
  95        "       movl       (%%eax), %%ebx\n\t"     // new top = _M._M_data._M_top->_M_next
  96        "       leal       1(%%edx),%%ecx\n\t"     // new sequence = _M._M_data._M_sequence + 1
  97        "lock;  cmpxchg8b  (%%esi)\n\t"
  98        "       jne        L1_%=\n\t"              // We failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
  99        "L2_%=: movl       %%edi, %%ebx"
 100       :"=a" (__result), "=d" (__tmp)
 101       :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "S" (&_M._M_data)
 102       :"edi", "ecx", "memory", "cc");
 103     return __result;
 104   }
 105
 106   /**
 107    * Atomically detaches all items from the list and returns a pointer to the
 108    * topmost item.  The items are still chained and may be traversed safely as
 109    * they're now "owned" by the calling thread.
 110    *
 111    * @return Pointer to topmost item in the list; NULL if list empty
 112    */
 113   item* clear() {
 114     item*   __result;
 115     int     __tmp;
 116     __asm__ __volatile__
 117       ("       movl       %%ebx, %%edi\n\t"
 118        "L1_%=: testl      %%eax, %%eax\n\t"       // _M_top == NULL?
 119        "       je         L2_%=\n\t"              // If yes, we're done
 120        "       xorl       %%ebx, %%ebx\n\t"       // We're attempting to set _M_top to NULL
 121        "       leal       1(%%edx),%%ecx\n\t"     // new sequence = _M._M_data._M_sequence + 1
 122        "lock;  cmpxchg8b  (%%esi)\n\t"
 123        "       jne        L1_%=\n\t"              // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
 124        "L2_%=: movl       %%edi, %%ebx"
 125       :"=a" (__result), "=d" (__tmp)
 126       :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "S" (&_M._M_data)
 127       :"edi", "ecx", "memory", "cc");
 128     return __result;
 129   }
 130
 131 private:
 132     union {
 133       long long   _M_align;
 134       struct {
 135         item*           _M_top;         // Topmost element in the freelist
 136         unsigned int    _M_sequence;    // Sequence counter to prevent "ABA problem"
 137       } _M_data;
 138     } _M;
 139
 140   _STLP_atomic_freelist(const _STLP_atomic_freelist&);
 141   _STLP_atomic_freelist& operator=(const _STLP_atomic_freelist&);
 142 };
 143
 144 #  endif /* if defined(__GNUC__) && defined(__i386__) */
 145
 146 #elif defined (_STLP_WIN32THREADS)
 147
 148 #  if !defined (_WIN64)
 149 #    define _STLP_USE_ASM_IMPLEMENTATION
 150 #  endif
 151
 152 // Here are the compiler/platform requirements for the thread safe and
 153 // lock free singly linked list implementation:
 154 #  if defined (_STLP_USE_ASM_IMPLEMENTATION)
 155 // For the asm version:
 156 #    if defined (_STLP_MSVC) && defined (_M_IX86) && (_M_IX86 >= 500)
 157 #      define _STLP_HAS_ATOMIC_FREELIST
 158 #    endif
 159 #  else
 160 // For the API based version:
 161 #    if defined (_STLP_NEW_PLATFORM_SDK) && (!defined (WINVER) || (WINVER >= 0x0501)) && \
 162                                             (!defined (_WIN32_WINDOWS) || (_WIN32_WINDOWS >= 0x0501))
 163 #      define _STLP_HAS_ATOMIC_FREELIST
 164 #    endif
 165 #  endif
 166
 167 #  if defined (_STLP_HAS_ATOMIC_FREELIST)
 168 #    if !defined (_STLP_USE_ASM_IMPLEMENTATION)
 169 #      include <windows.h>
 170 #    else
 171 #      if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) || defined (__ICL)
 172 #        pragma warning (push)
 173 #        pragma warning (disable : 4035) //function has no return value
 174 #      endif
 175 #    endif
 176 /**
 177  * Class that implements a non-blocking and thread-safe freelist.
 178  * It is used for the lock-free node allocation engine.
 179  *
 180  * @author felixw@inin.com
 181  */
 182 class _STLP_atomic_freelist {
 183 public:
 184   /**
 185    * Type representing items of the freelist
 186    */
 187 #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
 188   struct item {
 189       item*   _M_next;
 190   };
 191 #    else
 192   typedef SLIST_ENTRY item;
 193 #    endif
 194
 195   _STLP_atomic_freelist() {
 196     // Statically assert layout of member is as expected by assembly code
 197 #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
 198     _STLP_STATIC_ASSERT((sizeof(item) == sizeof(item*)) && (sizeof(_M) == 8))
 199     _M._M_data._M_top       = 0;
 200     _M._M_data._M_sequence  = 0;
 201 #    else
 202     InitializeSListHead(&_M_head);
 203 #    endif
 204   }
 205
 206   /**
 207    * Atomically pushes the specified item onto the freelist.
 208    *
 209    * @param __item [in] Item to add to the front of the list
 210    */
 211   void push(item* __item) {
 212 #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
 213     __asm
 214     {
 215         mov             esi, this
 216         mov             ebx, __item
 217         mov             eax, [esi]              // _M._M_data._M_top
 218         mov             edx, [esi+4]            // _M._M_data._M_sequence
 219     L1: mov             [ebx], eax              // __item._M_next = _M._M_data._M_top
 220         lea             ecx, [edx+1]            // new sequence = _M._M_data._M_sequence + 1
 221         lock cmpxchg8b  qword ptr [esi]
 222         jne             L1                      // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
 223     }
 224 #    else
 225     InterlockedPushEntrySList(&_M_head, __item);
 226 #    endif
 227   }
 228
 229   /**
 230    * Atomically removes the topmost item from the freelist and returns a
 231    * pointer to it.  Returns NULL if the list is empty.
 232    *
 233    * @return Item that was removed from front of list; NULL if list empty
 234    */
 235   item* pop() {
 236 #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
 237     __asm
 238     {
 239         mov             esi, this
 240         mov             eax, [esi]              // _M._M_data._M_top
 241         mov             edx, [esi+4]            // _M._M_data._M_sequence
 242     L1: test            eax, eax                // _M_top == NULL?
 243         je              L2                      // Yes, we're done
 244         mov             ebx, [eax]              // new top = _M._M_data._M_top->_M_next
 245         lea             ecx, [edx+1]            // new sequence = _M._M_data._M_sequence + 1
 246         lock cmpxchg8b  qword ptr [esi]
 247         jne             L1                      // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
 248     L2:
 249     }
 250 #    else
 251     return InterlockedPopEntrySList(&_M_head);
 252 #    endif
 253   }
 254
 255   /**
 256    * Atomically detaches all items from the list and returns pointer to the
 257    * topmost.  The items are still chained and may be traversed safely as
 258    * they're now "owned" by the calling thread.
 259    *
 260    * @return Pointer to topmost item in the list; NULL if list empty
 261    */
 262   item* clear() {
 263 #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
 264     __asm
 265     {
 266         mov             esi, this
 267         mov             eax, [esi]              // _M._M_data._M_top
 268         mov             edx, [esi+4]            // _M._M_data._M_sequence
 269     L1: test            eax, eax                // _M_top == NULL?
 270         je              L2                      // Yes, we're done
 271         xor             ebx,ebx                 // We're attempting to set _M._M_data._M_top to NULL
 272         lea             ecx, [edx+1]            // new sequence = _M._M_data._M_sequence + 1
 273         lock cmpxchg8b  qword ptr [esi]
 274         jne             L1                      // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
 275     L2:
 276     }
 277 #    else
 278     return InterlockedFlushSList(&_M_head);
 279 #    endif
 280   }
 281
 282 private:
 283 #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
 284   union {
 285     __int64     _M_align;
 286     struct {
 287       item*           _M_top;         // Topmost element in the freelist
 288       unsigned int    _M_sequence;    // Sequence counter to prevent "ABA problem"
 289     } _M_data;
 290   } _M;
 291 #    else
 292   SLIST_HEADER _M_head;
 293 #    endif
 294
 295   _STLP_atomic_freelist(const _STLP_atomic_freelist&);
 296   _STLP_atomic_freelist& operator = (const _STLP_atomic_freelist&);
 297 };
 298
 299 #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
 300 #      if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) || defined (__ICL)
 301 #        pragma warning (pop)
 302 #      endif
 303 #    endif
 304
 305 #  endif /* _STLP_HAS_ATOMIC_FREELIST */
 306
 307 #endif
 308
 309 #endif /* _STLP_LOCK_FREE_SLIST_H */