michael@0: /*
michael@0:  * Copyright (c) 1997-1999
michael@0:  * Silicon Graphics Computer Systems, Inc.
michael@0:  *
michael@0:  * Copyright (c) 1999
michael@0:  * Boris Fomitchev
michael@0:  *
michael@0:  * This material is provided "as is", with absolutely no warranty expressed
michael@0:  * or implied. Any use is at your own risk.
michael@0:  *
michael@0:  * Permission to use or copy this software for any purpose is hereby granted
michael@0:  * without fee, provided the above notices are retained on all copies.
michael@0:  * Permission to modify the code and to distribute modified code is granted,
michael@0:  * provided the above notices are retained, and a notice that the code was
michael@0:  * modified is included with the above copyright notice.
michael@0:  *
michael@0:  */
michael@0: 
michael@0: #ifndef _STLP_LOCK_FREE_SLIST_H
michael@0: #define _STLP_LOCK_FREE_SLIST_H
michael@0: 
michael@0: #if defined(_STLP_PTHREADS)
michael@0: #  include <pthread.h>
michael@0: 
michael@0: #  if defined (__GNUC__) && defined (__i386__)
michael@0: 
michael@0: #    define _STLP_HAS_ATOMIC_FREELIST
michael@0: /**
michael@0:  * Class that implements a non-blocking and thread-safe freelist.
michael@0:  * It is used for the lock-free node allocation engine.
michael@0:  *
michael@0:  * @author felixw@inin.com
michael@0:  */
michael@0: class _STLP_atomic_freelist {
michael@0: public:
michael@0:   /**
michael@0:    * Type representing items of the freelist
michael@0:    */
michael@0:   struct item {
michael@0:     item* _M_next;
michael@0:   };
michael@0: 
michael@0:   _STLP_atomic_freelist() {
michael@0:     // Statically assert layout of member is as expected by assembly code
michael@0:     _STLP_STATIC_ASSERT(sizeof(_M) == 8)
michael@0:     _M._M_data._M_top       = 0;
michael@0:     _M._M_data._M_sequence  = 0;
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Atomically pushes the specified item onto the freelist.
michael@0:    *
michael@0:    * @param __item [in] Item to add to the front of the list
michael@0:    */
michael@0:   void push(item* __item) {
michael@0:     // NOTE: GCC uses ebx as the PIC register for globals in shared libraries.
michael@0:     //       The GCC version I'm using (3.4.1) won't temporarily spill it if it's
michael@0:     //       used as input, output, or clobber.  Instead, it complains with a
michael@0:     //       "can't find a register in class `BREG' while reloading `asm'" error.
michael@0:     //       This is probably a compiler bug, but as the cmpxchg8b instruction
michael@0:     //       requires ebx, I work around this here by using ecx for the '__item'
michael@0:     //       input and spilling ebx into edi.  This also precludes us from using
michael@0:     //       a "m" operand for the cmpxchg8b argument (GCC might think it can make
michael@0:     //       it relative to ebx).  Instead, we're using esi for the address of _M_data.
michael@0:     //
michael@0:     int __tmp1;     // These dummy variables are used to tell GCC that the eax, ecx,
michael@0:     int __tmp2;     // and edx registers will not have the same value as their input.
michael@0:     int __tmp3;     // The optimizer will remove them as their values are not used.
michael@0:     __asm__ __volatile__
michael@0:       ("       movl       %%ebx, %%edi\n\t"
michael@0:        "       movl       %%ecx, %%ebx\n\t"
michael@0:        "L1_%=: movl       %%eax, (%%ebx)\n\t"     // __item._M_next = _M._M_data._M_top
michael@0:        "       leal       1(%%edx),%%ecx\n\t"     // new sequence = _M._M_data._M_sequence + 1
michael@0:        "lock;  cmpxchg8b  (%%esi)\n\t"
michael@0:        "       jne        L1_%=\n\t"              // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
michael@0:        "       movl       %%edi, %%ebx"
michael@0:       :"=a" (__tmp1), "=d" (__tmp2), "=c" (__tmp3)
michael@0:       :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "c" (__item), "S" (&_M._M_data)
michael@0:       :"edi", "memory", "cc");
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Atomically removes the topmost item from the freelist and returns a
michael@0:    * pointer to it.  Returns NULL if the list is empty.
michael@0:    *
michael@0:    * @return Item that was removed from front of list; NULL if list empty
michael@0:    */
michael@0:   item* pop() {
michael@0:     item*   __result;
michael@0:     int     __tmp;
michael@0:     __asm__ __volatile__
michael@0:       ("       movl       %%ebx, %%edi\n\t"
michael@0:        "L1_%=: testl      %%eax, %%eax\n\t"       // _M_top == NULL?
michael@0:        "       je         L2_%=\n\t"              // If yes, we're done
michael@0:        "       movl       (%%eax), %%ebx\n\t"     // new top = _M._M_data._M_top->_M_next
michael@0:        "       leal       1(%%edx),%%ecx\n\t"     // new sequence = _M._M_data._M_sequence + 1
michael@0:        "lock;  cmpxchg8b  (%%esi)\n\t"
michael@0:        "       jne        L1_%=\n\t"              // We failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
michael@0:        "L2_%=: movl       %%edi, %%ebx"
michael@0:       :"=a" (__result), "=d" (__tmp)
michael@0:       :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "S" (&_M._M_data)
michael@0:       :"edi", "ecx", "memory", "cc");
michael@0:     return __result;
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Atomically detaches all items from the list and returns a pointer to the
michael@0:    * topmost item.  The items are still chained and may be traversed safely as
michael@0:    * they're now "owned" by the calling thread.
michael@0:    *
michael@0:    * @return Pointer to topmost item in the list; NULL if list empty
michael@0:    */
michael@0:   item* clear() {
michael@0:     item*   __result;
michael@0:     int     __tmp;
michael@0:     __asm__ __volatile__
michael@0:       ("       movl       %%ebx, %%edi\n\t"
michael@0:        "L1_%=: testl      %%eax, %%eax\n\t"       // _M_top == NULL?
michael@0:        "       je         L2_%=\n\t"              // If yes, we're done
michael@0:        "       xorl       %%ebx, %%ebx\n\t"       // We're attempting to set _M_top to NULL
michael@0:        "       leal       1(%%edx),%%ecx\n\t"     // new sequence = _M._M_data._M_sequence + 1
michael@0:        "lock;  cmpxchg8b  (%%esi)\n\t"
michael@0:        "       jne        L1_%=\n\t"              // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
michael@0:        "L2_%=: movl       %%edi, %%ebx"
michael@0:       :"=a" (__result), "=d" (__tmp)
michael@0:       :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "S" (&_M._M_data)
michael@0:       :"edi", "ecx", "memory", "cc");
michael@0:     return __result;
michael@0:   }
michael@0: 
michael@0: private:
michael@0:     union {
michael@0:       long long   _M_align;
michael@0:       struct {
michael@0:         item*           _M_top;         // Topmost element in the freelist
michael@0:         unsigned int    _M_sequence;    // Sequence counter to prevent "ABA problem"
michael@0:       } _M_data;
michael@0:     } _M;
michael@0: 
michael@0:   _STLP_atomic_freelist(const _STLP_atomic_freelist&);
michael@0:   _STLP_atomic_freelist& operator=(const _STLP_atomic_freelist&);
michael@0: };
michael@0: 
michael@0: #  endif /* if defined(__GNUC__) && defined(__i386__) */
michael@0: 
michael@0: #elif defined (_STLP_WIN32THREADS)
michael@0: 
michael@0: #  if !defined (_WIN64)
michael@0: #    define _STLP_USE_ASM_IMPLEMENTATION
michael@0: #  endif
michael@0: 
michael@0: // Here are the compiler/platform requirements for the thread safe and
michael@0: // lock free singly linked list implementation:
michael@0: #  if defined (_STLP_USE_ASM_IMPLEMENTATION)
michael@0: // For the asm version:
michael@0: #    if defined (_STLP_MSVC) && defined (_M_IX86) && (_M_IX86 >= 500)
michael@0: #      define _STLP_HAS_ATOMIC_FREELIST
michael@0: #    endif
michael@0: #  else
michael@0: // For the API based version:
michael@0: #    if defined (_STLP_NEW_PLATFORM_SDK) && (!defined (WINVER) || (WINVER >= 0x0501)) && \
michael@0:                                             (!defined (_WIN32_WINNT) || (_WIN32_WINNT >= 0x0501))
michael@0: #      define _STLP_HAS_ATOMIC_FREELIST
michael@0: #    endif
michael@0: #  endif
michael@0: 
michael@0: #  if defined (_STLP_HAS_ATOMIC_FREELIST)
michael@0: #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
michael@0: #      if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) || defined (__ICL)
michael@0: #        pragma warning (push)
michael@0: #        pragma warning (disable : 4035) //function has no return value
michael@0: #      endif
michael@0: #    endif
michael@0: /**
michael@0:  * Class that implements a non-blocking and thread-safe freelist.
michael@0:  * It is used for the lock-free node allocation engine.
michael@0:  *
michael@0:  * @author felixw@inin.com
michael@0:  */
michael@0: class _STLP_atomic_freelist {
michael@0: public:
michael@0:   /**
michael@0:    * Type representing items of the freelist
michael@0:    */
michael@0: #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
michael@0:   struct item {
michael@0:       item*   _M_next;
michael@0:   };
michael@0: #    else
michael@0:   typedef SLIST_ENTRY item;
michael@0: #    endif
michael@0: 
michael@0:   _STLP_atomic_freelist() {
michael@0:     // Statically assert layout of member is as expected by assembly code
michael@0: #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
michael@0:     _STLP_STATIC_ASSERT((sizeof(item) == sizeof(item*)) && (sizeof(_M) == 8))
michael@0:     _M._M_data._M_top       = 0;
michael@0:     _M._M_data._M_sequence  = 0;
michael@0: #    else
michael@0:     InitializeSListHead(&_M_head);
michael@0: #    endif
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Atomically pushes the specified item onto the freelist.
michael@0:    *
michael@0:    * @param __item [in] Item to add to the front of the list
michael@0:    */
michael@0:   void push(item* __item) {
michael@0: #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
michael@0:     __asm
michael@0:     {
michael@0:         mov             esi, this
michael@0:         mov             ebx, __item
michael@0:         mov             eax, [esi]              // _M._M_data._M_top
michael@0:         mov             edx, [esi+4]            // _M._M_data._M_sequence
michael@0:     L1: mov             [ebx], eax              // __item._M_next = _M._M_data._M_top
michael@0:         lea             ecx, [edx+1]            // new sequence = _M._M_data._M_sequence + 1
michael@0:         lock cmpxchg8b  qword ptr [esi]
michael@0:         jne             L1                      // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
michael@0:     }
michael@0: #    else
michael@0:     InterlockedPushEntrySList(&_M_head, __item);
michael@0: #    endif
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Atomically removes the topmost item from the freelist and returns a
michael@0:    * pointer to it.  Returns NULL if the list is empty.
michael@0:    *
michael@0:    * @return Item that was removed from front of list; NULL if list empty
michael@0:    */
michael@0:   item* pop() {
michael@0: #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
michael@0:     __asm
michael@0:     {
michael@0:         mov             esi, this
michael@0:         mov             eax, [esi]              // _M._M_data._M_top
michael@0:         mov             edx, [esi+4]            // _M._M_data._M_sequence
michael@0:     L1: test            eax, eax                // _M_top == NULL?
michael@0:         je              L2                      // Yes, we're done
michael@0:         mov             ebx, [eax]              // new top = _M._M_data._M_top->_M_next
michael@0:         lea             ecx, [edx+1]            // new sequence = _M._M_data._M_sequence + 1
michael@0:         lock cmpxchg8b  qword ptr [esi]
michael@0:         jne             L1                      // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
michael@0:     L2:
michael@0:     }
michael@0: #    else
michael@0:     return InterlockedPopEntrySList(&_M_head);
michael@0: #    endif
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Atomically detaches all items from the list and returns pointer to the
michael@0:    * topmost.  The items are still chained and may be traversed safely as
michael@0:    * they're now "owned" by the calling thread.
michael@0:    *
michael@0:    * @return Pointer to topmost item in the list; NULL if list empty
michael@0:    */
michael@0:   item* clear() {
michael@0: #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
michael@0:     __asm
michael@0:     {
michael@0:         mov             esi, this
michael@0:         mov             eax, [esi]              // _M._M_data._M_top
michael@0:         mov             edx, [esi+4]            // _M._M_data._M_sequence
michael@0:     L1: test            eax, eax                // _M_top == NULL?
michael@0:         je              L2                      // Yes, we're done
michael@0:         xor             ebx,ebx                 // We're attempting to set _M._M_data._M_top to NULL
michael@0:         lea             ecx, [edx+1]            // new sequence = _M._M_data._M_sequence + 1
michael@0:         lock cmpxchg8b  qword ptr [esi]
michael@0:         jne             L1                      // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
michael@0:     L2:
michael@0:     }
michael@0: #    else
michael@0:     return InterlockedFlushSList(&_M_head);
michael@0: #    endif
michael@0:   }
michael@0: 
michael@0: private:
michael@0: #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
michael@0:   union {
michael@0:     __int64     _M_align;
michael@0:     struct {
michael@0:       item*           _M_top;         // Topmost element in the freelist
michael@0:       unsigned int    _M_sequence;    // Sequence counter to prevent "ABA problem"
michael@0:     } _M_data;
michael@0:   } _M;
michael@0: #    else
michael@0:   SLIST_HEADER _M_head;
michael@0: #    endif
michael@0: 
michael@0:   _STLP_atomic_freelist(const _STLP_atomic_freelist&);
michael@0:   _STLP_atomic_freelist& operator = (const _STLP_atomic_freelist&);
michael@0: };
michael@0: 
michael@0: #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
michael@0: #      if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) || defined (__ICL)
michael@0: #        pragma warning (pop)
michael@0: #      endif
michael@0: #    endif
michael@0: 
michael@0: #  endif /* _STLP_HAS_ATOMIC_FREELIST */
michael@0: 
michael@0: #endif
michael@0: 
michael@0: #endif /* _STLP_LOCK_FREE_SLIST_H */