ReactOS 0.4.15-dev-7842-g558ab78
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
34class _STLP_atomic_freelist {
35public:
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
131private:
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
180class _STLP_atomic_freelist {
181public:
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
280private:
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 */
#define __int64
Definition: basetyps.h:16
static void xor(unsigned char *dst, const unsigned char *a, const unsigned char *b, const int count)
Definition: crypt_des.c:251
#define _STLP_STATIC_ASSERT(expr)
Definition: features.h:313
static PVOID ptr
Definition: dispmode.c:27
static ATOM item
Definition: dde.c:856
__asm__(".p2align 4, 0x90\n" ".seh_proc __seh2_global_filter_func\n" "__seh2_global_filter_func:\n" "\tpush %rbp\n" "\t.seh_pushreg %rbp\n" "\tsub $32, %rsp\n" "\t.seh_stackalloc 32\n" "\t.seh_endprologue\n" "\tmov %rdx, %rbp\n" "\tjmp *%rax\n" "__seh2_global_filter_func_exit:\n" "\t.p2align 4\n" "\tadd $32, %rsp\n" "\tpop %rbp\n" "\tret\n" "\t.seh_endproc")
#define test
Definition: rosglue.h:37
static calc_node_t * pop(void)
Definition: rpn_ieee.c:90
static void push(calc_node_t *op)
Definition: rpn_ieee.c:113
ecx edi movl ebx edx edi decl ecx esi eax jecxz decl eax andl ebx
Definition: synth_sse3d.h:83
ecx edi movl ebx edx edi decl ecx esi eax jecxz decl eax andl eax esi movl eax
Definition: synth_sse3d.h:85
ecx edi movl ebx edx edi decl ecx esi eax jecxz decl eax andl eax esi movl edx movl TEMP incl eax andl eax ecx incl ebx testl eax jnz xchgl ecx incl TEMP esi
Definition: synth_sse3d.h:103
ecx edi movl ebx edx edi decl ecx esi eax jecxz decl eax andl eax esi movl edx
Definition: synth_sse3d.h:87
#define SLIST_ENTRY(type)
Definition: queue.h:102
rwlock_t lock
Definition: tcpcore.h:0
#define InterlockedPushEntrySList(SListHead, SListEntry)
Definition: rtlfuncs.h:3389
#define InterlockedFlushSList(SListHead)
Definition: rtlfuncs.h:3395
#define InterlockedPopEntrySList(SListHead)
Definition: rtlfuncs.h:3392
FORCEINLINE VOID InitializeSListHead(_Out_ PSLIST_HEADER SListHead)
Definition: rtlfuncs.h:3351