ReactOS  0.4.15-dev-1039-gb9754fa
lock_free_slist.h
Go to the documentation of this file.
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 
34 class _STLP_atomic_freelist {
35 public:
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 
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 
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 
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 
180 class _STLP_atomic_freelist {
181 public:
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 
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 
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 
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 */
static void xor(unsigned char *dst, const unsigned char *a, const unsigned char *b, const int count)
Definition: crypt_des.c:251
rwlock_t lock
Definition: tcpcore.h:1163
ecx edi ebx edx edi decl ecx esi eax jecxz decl eax andl eax esi movl edx movl TEMP incl eax andl eax ecx incl ebx eax jnz xchgl ecx incl TEMP esi
Definition: synth_sse3d.h:103
#define test
Definition: rosglue.h:37
static calc_node_t * pop(void)
Definition: rpn_ieee.c:90
PSLIST_ENTRY WINAPI InterlockedPopEntrySList(PSLIST_HEADER ListHead)
Definition: interlocked.c:55
__asm__("\t.globl GetPhys\n" "GetPhys:\t\n" "mflr 0\n\t" "stwu 0,-16(1)\n\t" "mfmsr 5\n\t" "andi. 6,5,0xffef\n\t" "mtmsr 6\n\t" "isync\n\t" "sync\n\t" "lwz 3,0(3)\n\t" "mtmsr 5\n\t" "isync\n\t" "sync\n\t" "lwz 0,0(1)\n\t" "addi 1,1,16\n\t" "mtlr 0\n\t" "blr")
static PVOID ptr
Definition: dispmode.c:27
FORCEINLINE VOID InitializeSListHead(_Out_ PSLIST_HEADER SListHead)
Definition: rtlfuncs.h:3353
ecx edi ebx edx edi decl ecx esi eax jecxz decl eax andl eax esi movl eax
Definition: synth_sse3d.h:85
_STLP_STATIC_ASSERT(sizeof(nl_catd_type)<=sizeof(int)) class _STLP_CLASS_DECLSPEC _Catalog_nl_catd_map
#define InterlockedFlushSList(SListHead)
Definition: rtlfuncs.h:3397
ecx edi ebx edx edi decl ecx esi eax jecxz decl eax andl ebx
Definition: synth_sse3d.h:83
NTKERNELAPI PSLIST_ENTRY FASTCALL InterlockedPushEntrySList(IN PSLIST_HEADER ListHead, IN PSLIST_ENTRY ListEntry)
Definition: interlocked.c:82
static ATOM item
Definition: dde.c:856
#define _M
#define SLIST_ENTRY(type)
Definition: queue.h:102
ecx edi ebx edx edi decl ecx esi eax jecxz decl eax andl eax esi movl edx
Definition: synth_sse3d.h:85
static void push(calc_node_t *op)
Definition: rpn_ieee.c:113
#define __int64
Definition: basetyps.h:16