src/lock_free_slist.h - mainline in STLport

/*
 * Copyright (c) 1997-1999
 * Silicon Graphics Computer Systems, Inc.
 *
 * Copyright (c) 1999
 * Boris Fomitchev
 *
 * This material is provided "as is", with absolutely no warranty expressed
 * or implied. Any use is at your own risk.
 *
 * Permission to use or copy this software for any purpose is hereby granted
 * without fee, provided the above notices are retained on all copies.
 * Permission to modify the code and to distribute modified code is granted,
 * provided the above notices are retained, and a notice that the code was
 * modified is included with the above copyright notice.
 *
 */

#ifndef _STLP_LOCK_FREE_SLIST_H
#define _STLP_LOCK_FREE_SLIST_H

#if defined(_STLP_PTHREADS)
#  include <pthread.h>

#  if defined (__GNUC__) && defined (__i386__)

#    define _STLP_HAS_ATOMIC_FREELIST
/**
 * Class that implements a non-blocking and thread-safe freelist.
 * It is used for the lock-free node allocation engine.
 *
 * @author felixw@inin.com
 */
class _STLP_atomic_freelist {
public:
  /**
   * Type representing items of the freelist
   */
  struct item {
    item* _M_next;
  };

  _STLP_atomic_freelist() {
    // Statically assert layout of member is as expected by assembly code
    _STLP_STATIC_ASSERT(sizeof(_M) == 8)
    _M._M_data._M_top       = 0;
    _M._M_data._M_sequence  = 0;
  }

  /**
   * Atomically pushes the specified item onto the freelist.
   *
   * @param __item [in] Item to add to the front of the list
   */
  void push(item* __item) {
    // NOTE: GCC uses ebx as the PIC register for globals in shared libraries.
    //       The GCC version I'm using (3.4.1) won't temporarily spill it if it's
    //       used as input, output, or clobber.  Instead, it complains with a
    //       "can't find a register in class `BREG' while reloading `asm'" error.
    //       This is probably a compiler bug, but as the cmpxchg8b instruction
    //       requires ebx, I work around this here by using ecx for the '__item'
    //       input and spilling ebx into edi.  This also precludes us from using
    //       a "m" operand for the cmpxchg8b argument (GCC might think it can make
    //       it relative to ebx).  Instead, we're using esi for the address of _M_data.
    //
    int __tmp1;     // These dummy variables are used to tell GCC that the eax, ecx,
    int __tmp2;     // and edx registers will not have the same value as their input.
    int __tmp3;     // The optimizer will remove them as their values are not used.
    __asm__ __volatile__
      ("       movl       %%ebx, %%edi\n\t"
       "       movl       %%ecx, %%ebx\n\t"
       "L1_%=: movl       %%eax, (%%ebx)\n\t"     // __item._M_next = _M._M_data._M_top
       "       leal       1(%%edx),%%ecx\n\t"     // new sequence = _M._M_data._M_sequence + 1
       "lock;  cmpxchg8b  (%%esi)\n\t"
       "       jne        L1_%=\n\t"              // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
       "       movl       %%edi, %%ebx"
      :"=a" (__tmp1), "=d" (__tmp2), "=c" (__tmp3)
      :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "c" (__item), "S" (&_M._M_data)
      :"edi", "memory", "cc");
  }

  /**
   * Atomically removes the topmost item from the freelist and returns a
   * pointer to it.  Returns NULL if the list is empty.
   *
   * @return Item that was removed from front of list; NULL if list empty
   */
  item* pop() {
    item*   __result;
    int     __tmp;
    __asm__ __volatile__
      ("       movl       %%ebx, %%edi\n\t"
       "L1_%=: testl      %%eax, %%eax\n\t"       // _M_top == NULL?
       "       je         L2_%=\n\t"              // If yes, we're done
       "       movl       (%%eax), %%ebx\n\t"     // new top = _M._M_data._M_top->_M_next
       "       leal       1(%%edx),%%ecx\n\t"     // new sequence = _M._M_data._M_sequence + 1
       "lock;  cmpxchg8b  (%%esi)\n\t"
       "       jne        L1_%=\n\t"              // We failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
       "L2_%=: movl       %%edi, %%ebx"
      :"=a" (__result), "=d" (__tmp)
      :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "S" (&_M._M_data)
      :"edi", "ecx", "memory", "cc");
    return __result;
  }

  /**
   * Atomically detaches all items from the list and returns a pointer to the
   * topmost item.  The items are still chained and may be traversed safely as
   * they're now "owned" by the calling thread.
   *
   * @return Pointer to topmost item in the list; NULL if list empty
   */
  item* clear() {
    item*   __result;
    int     __tmp;
    __asm__ __volatile__
      ("       movl       %%ebx, %%edi\n\t"
       "L1_%=: testl      %%eax, %%eax\n\t"       // _M_top == NULL?
       "       je         L2_%=\n\t"              // If yes, we're done
       "       xorl       %%ebx, %%ebx\n\t"       // We're attempting to set _M_top to NULL
       "       leal       1(%%edx),%%ecx\n\t"     // new sequence = _M._M_data._M_sequence + 1
       "lock;  cmpxchg8b  (%%esi)\n\t"
       "       jne        L1_%=\n\t"              // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
       "L2_%=: movl       %%edi, %%ebx"
      :"=a" (__result), "=d" (__tmp)
      :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "S" (&_M._M_data)
      :"edi", "ecx", "memory", "cc");
    return __result;
  }

private:
    union {
      long long   _M_align;
      struct {
        item*           _M_top;         // Topmost element in the freelist
        unsigned int    _M_sequence;    // Sequence counter to prevent "ABA problem"
      } _M_data;
    } _M;

  _STLP_atomic_freelist(const _STLP_atomic_freelist&);
  _STLP_atomic_freelist& operator=(const _STLP_atomic_freelist&);
};

#  endif /* if defined(__GNUC__) && defined(__i386__) */

#elif defined (_STLP_WIN32THREADS)

#  if !defined (_WIN64)
#    define _STLP_USE_ASM_IMPLEMENTATION
#  endif

// Here are the compiler/platform requirements for the thread safe and
// lock free singly linked list implementation:
#  if defined (_STLP_USE_ASM_IMPLEMENTATION)
// For the asm version:
#    if defined (_STLP_MSVC) && defined (_M_IX86) && (_M_IX86 >= 500)
#      define _STLP_HAS_ATOMIC_FREELIST
#    endif
#  else
// For the API based version:
#    if defined (_STLP_NEW_PLATFORM_SDK) && (!defined (WINVER) || (WINVER >= 0x0501)) && \
                                            (!defined (_WIN32_WINNT) || (_WIN32_WINNT >= 0x0501))
#      define _STLP_HAS_ATOMIC_FREELIST
#    endif
#  endif

#  if defined (_STLP_HAS_ATOMIC_FREELIST)
#    if defined (_STLP_USE_ASM_IMPLEMENTATION)
#      if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) || defined (__ICL)
#        pragma warning (push)
#        pragma warning (disable : 4035) //function has no return value
#      endif
#    endif
/**
 * Class that implements a non-blocking and thread-safe freelist.
 * It is used for the lock-free node allocation engine.
 *
 * @author felixw@inin.com
 */
class _STLP_atomic_freelist {
public:
  /**
   * Type representing items of the freelist
   */
#    if defined (_STLP_USE_ASM_IMPLEMENTATION)
  struct item {
      item*   _M_next;
  };
#    else
  typedef SLIST_ENTRY item;
#    endif

  _STLP_atomic_freelist() {
    // Statically assert layout of member is as expected by assembly code
#    if defined (_STLP_USE_ASM_IMPLEMENTATION)
    _STLP_STATIC_ASSERT((sizeof(item) == sizeof(item*)) && (sizeof(_M) == 8))
    _M._M_data._M_top       = 0;
    _M._M_data._M_sequence  = 0;
#    else
    InitializeSListHead(&_M_head);
#    endif
  }

  /**
   * Atomically pushes the specified item onto the freelist.
   *
   * @param __item [in] Item to add to the front of the list
   */
  void push(item* __item) {
#    if defined (_STLP_USE_ASM_IMPLEMENTATION)
    __asm
    {
        mov             esi, this
        mov             ebx, __item
        mov             eax, [esi]              // _M._M_data._M_top
        mov             edx, [esi+4]            // _M._M_data._M_sequence
    L1: mov             [ebx], eax              // __item._M_next = _M._M_data._M_top
        lea             ecx, [edx+1]            // new sequence = _M._M_data._M_sequence + 1
        lock cmpxchg8b  qword ptr [esi]
        jne             L1                      // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
    }
#    else
    InterlockedPushEntrySList(&_M_head, __item);
#    endif
  }

  /**
   * Atomically removes the topmost item from the freelist and returns a
   * pointer to it.  Returns NULL if the list is empty.
   *
   * @return Item that was removed from front of list; NULL if list empty
   */
  item* pop() {
#    if defined (_STLP_USE_ASM_IMPLEMENTATION)
    __asm
    {
        mov             esi, this
        mov             eax, [esi]              // _M._M_data._M_top
        mov             edx, [esi+4]            // _M._M_data._M_sequence
    L1: test            eax, eax                // _M_top == NULL?
        je              L2                      // Yes, we're done
        mov             ebx, [eax]              // new top = _M._M_data._M_top->_M_next
        lea             ecx, [edx+1]            // new sequence = _M._M_data._M_sequence + 1
        lock cmpxchg8b  qword ptr [esi]
        jne             L1                      // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
    L2:
    }
#    else
    return InterlockedPopEntrySList(&_M_head);
#    endif
  }

  /**
   * Atomically detaches all items from the list and returns pointer to the
   * topmost.  The items are still chained and may be traversed safely as
   * they're now "owned" by the calling thread.
   *
   * @return Pointer to topmost item in the list; NULL if list empty
   */
  item* clear() {
#    if defined (_STLP_USE_ASM_IMPLEMENTATION)
    __asm
    {
        mov             esi, this
        mov             eax, [esi]              // _M._M_data._M_top
        mov             edx, [esi+4]            // _M._M_data._M_sequence
    L1: test            eax, eax                // _M_top == NULL?
        je              L2                      // Yes, we're done
        xor             ebx,ebx                 // We're attempting to set _M._M_data._M_top to NULL
        lea             ecx, [edx+1]            // new sequence = _M._M_data._M_sequence + 1
        lock cmpxchg8b  qword ptr [esi]
        jne             L1                      // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
    L2:
    }
#    else
    return InterlockedFlushSList(&_M_head);
#    endif
  }

private:
#    if defined (_STLP_USE_ASM_IMPLEMENTATION)
  union {
    __int64     _M_align;
    struct {
      item*           _M_top;         // Topmost element in the freelist
      unsigned int    _M_sequence;    // Sequence counter to prevent "ABA problem"
    } _M_data;
  } _M;
#    else
  SLIST_HEADER _M_head;
#    endif

  _STLP_atomic_freelist(const _STLP_atomic_freelist&);
  _STLP_atomic_freelist& operator = (const _STLP_atomic_freelist&);
};

#    if defined (_STLP_USE_ASM_IMPLEMENTATION)
#      if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) || defined (__ICL)
#        pragma warning (pop)
#      endif
#    endif

#  endif /* _STLP_HAS_ATOMIC_FREELIST */

#endif

#endif /* _STLP_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_WINNT) \|\| (_WIN32_WINNT >= 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	# if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) \|\| defined (__ICL)
170	# pragma warning (push)
171	# pragma warning (disable : 4035) //function has no return value
172	# endif
173	# endif
174	/**
175	* Class that implements a non-blocking and thread-safe freelist.
176	* It is used for the lock-free node allocation engine.
177	*
178	* @author felixw@inin.com
179	*/
180	class _STLP_atomic_freelist {
181	public:
182	/**
183	* Type representing items of the freelist
184	*/
185	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
186	struct item {
187	item* _M_next;
188	};
189	# else
190	typedef SLIST_ENTRY item;
191	# endif
192
193	_STLP_atomic_freelist() {
194	// Statically assert layout of member is as expected by assembly code
195	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
196	_STLP_STATIC_ASSERT((sizeof(item) == sizeof(item*)) && (sizeof(_M) == 8))
197	_M._M_data._M_top = 0;
198	_M._M_data._M_sequence = 0;
199	# else
200	InitializeSListHead(&_M_head);
201	# endif
202	}
203
204	/**
205	* Atomically pushes the specified item onto the freelist.
206	*
207	* @param __item [in] Item to add to the front of the list
208	*/
209	void push(item* __item) {
210	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
211	__asm
212	{
213	mov esi, this
214	mov ebx, __item
215	mov eax, [esi] // _M._M_data._M_top
216	mov edx, [esi+4] // _M._M_data._M_sequence
217	L1: mov [ebx], eax // __item._M_next = _M._M_data._M_top
218	lea ecx, [edx+1] // new sequence = _M._M_data._M_sequence + 1
219	lock cmpxchg8b qword ptr [esi]
220	jne L1 // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
221	}
222	# else
223	InterlockedPushEntrySList(&_M_head, __item);
224	# endif
225	}
226
227	/**
228	* Atomically removes the topmost item from the freelist and returns a
229	* pointer to it. Returns NULL if the list is empty.
230	*
231	* @return Item that was removed from front of list; NULL if list empty
232	*/
233	item* pop() {
234	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
235	__asm
236	{
237	mov esi, this
238	mov eax, [esi] // _M._M_data._M_top
239	mov edx, [esi+4] // _M._M_data._M_sequence
240	L1: test eax, eax // _M_top == NULL?
241	je L2 // Yes, we're done
242	mov ebx, [eax] // new top = _M._M_data._M_top->_M_next
243	lea ecx, [edx+1] // new sequence = _M._M_data._M_sequence + 1
244	lock cmpxchg8b qword ptr [esi]
245	jne L1 // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
246	L2:
247	}
248	# else
249	return InterlockedPopEntrySList(&_M_head);
250	# endif
251	}
252
253	/**
254	* Atomically detaches all items from the list and returns pointer to the
255	* topmost. The items are still chained and may be traversed safely as
256	* they're now "owned" by the calling thread.
257	*
258	* @return Pointer to topmost item in the list; NULL if list empty
259	*/
260	item* clear() {
261	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
262	__asm
263	{
264	mov esi, this
265	mov eax, [esi] // _M._M_data._M_top
266	mov edx, [esi+4] // _M._M_data._M_sequence
267	L1: test eax, eax // _M_top == NULL?
268	je L2 // Yes, we're done
269	xor ebx,ebx // We're attempting to set _M._M_data._M_top to NULL
270	lea ecx, [edx+1] // new sequence = _M._M_data._M_sequence + 1
271	lock cmpxchg8b qword ptr [esi]
272	jne L1 // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
273	L2:
274	}
275	# else
276	return InterlockedFlushSList(&_M_head);
277	# endif
278	}
279
280	private:
281	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
282	union {
283	__int64 _M_align;
284	struct {
285	item* _M_top; // Topmost element in the freelist
286	unsigned int _M_sequence; // Sequence counter to prevent "ABA problem"
287	} _M_data;
288	} _M;
289	# else
290	SLIST_HEADER _M_head;
291	# endif
292
293	_STLP_atomic_freelist(const _STLP_atomic_freelist&);
294	_STLP_atomic_freelist& operator = (const _STLP_atomic_freelist&);
295	};
296
297	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
298	# if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) \|\| defined (__ICL)
299	# pragma warning (pop)
300	# endif
301	# endif
302
303	# endif /* _STLP_HAS_ATOMIC_FREELIST */
304
305	#endif
306
307	#endif /* _STLP_LOCK_FREE_SLIST_H */

Gitorious