The Tor Browser / file comparison

comparison: build/stlport/src/lock_free_slist.h

build/stlport/src/lock_free_slist.h

changeset 0
6474c204b198
equal deleted inserted replaced
-1:000000000000 0:f999f12d4beb
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 */

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial