1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/build/stlport/src/lock_free_slist.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,307 @@
1.4 +/*
1.5 + * Copyright (c) 1997-1999
1.6 + * Silicon Graphics Computer Systems, Inc.
1.7 + *
1.8 + * Copyright (c) 1999
1.9 + * Boris Fomitchev
1.10 + *
1.11 + * This material is provided "as is", with absolutely no warranty expressed
1.12 + * or implied. Any use is at your own risk.
1.13 + *
1.14 + * Permission to use or copy this software for any purpose is hereby granted
1.15 + * without fee, provided the above notices are retained on all copies.
1.16 + * Permission to modify the code and to distribute modified code is granted,
1.17 + * provided the above notices are retained, and a notice that the code was
1.18 + * modified is included with the above copyright notice.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef _STLP_LOCK_FREE_SLIST_H
1.23 +#define _STLP_LOCK_FREE_SLIST_H
1.24 +
1.25 +#if defined(_STLP_PTHREADS)
1.26 +# include <pthread.h>
1.27 +
1.28 +# if defined (__GNUC__) && defined (__i386__)
1.29 +
1.30 +# define _STLP_HAS_ATOMIC_FREELIST
1.31 +/**
1.32 + * Class that implements a non-blocking and thread-safe freelist.
1.33 + * It is used for the lock-free node allocation engine.
1.34 + *
1.35 + * @author felixw@inin.com
1.36 + */
1.37 +class _STLP_atomic_freelist {
1.38 +public:
1.39 + /**
1.40 + * Type representing items of the freelist
1.41 + */
1.42 + struct item {
1.43 + item* _M_next;
1.44 + };
1.45 +
1.46 + _STLP_atomic_freelist() {
1.47 + // Statically assert layout of member is as expected by assembly code
1.48 + _STLP_STATIC_ASSERT(sizeof(_M) == 8)
1.49 + _M._M_data._M_top = 0;
1.50 + _M._M_data._M_sequence = 0;
1.51 + }
1.52 +
1.53 + /**
1.54 + * Atomically pushes the specified item onto the freelist.
1.55 + *
1.56 + * @param __item [in] Item to add to the front of the list
1.57 + */
1.58 + void push(item* __item) {
1.59 + // NOTE: GCC uses ebx as the PIC register for globals in shared libraries.
1.60 + // The GCC version I'm using (3.4.1) won't temporarily spill it if it's
1.61 + // used as input, output, or clobber. Instead, it complains with a
1.62 + // "can't find a register in class `BREG' while reloading `asm'" error.
1.63 + // This is probably a compiler bug, but as the cmpxchg8b instruction
1.64 + // requires ebx, I work around this here by using ecx for the '__item'
1.65 + // input and spilling ebx into edi. This also precludes us from using
1.66 + // a "m" operand for the cmpxchg8b argument (GCC might think it can make
1.67 + // it relative to ebx). Instead, we're using esi for the address of _M_data.
1.68 + //
1.69 + int __tmp1; // These dummy variables are used to tell GCC that the eax, ecx,
1.70 + int __tmp2; // and edx registers will not have the same value as their input.
1.71 + int __tmp3; // The optimizer will remove them as their values are not used.
1.72 + __asm__ __volatile__
1.73 + (" movl %%ebx, %%edi\n\t"
1.74 + " movl %%ecx, %%ebx\n\t"
1.75 + "L1_%=: movl %%eax, (%%ebx)\n\t" // __item._M_next = _M._M_data._M_top
1.76 + " leal 1(%%edx),%%ecx\n\t" // new sequence = _M._M_data._M_sequence + 1
1.77 + "lock; cmpxchg8b (%%esi)\n\t"
1.78 + " jne L1_%=\n\t" // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
1.79 + " movl %%edi, %%ebx"
1.80 + :"=a" (__tmp1), "=d" (__tmp2), "=c" (__tmp3)
1.81 + :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "c" (__item), "S" (&_M._M_data)
1.82 + :"edi", "memory", "cc");
1.83 + }
1.84 +
1.85 + /**
1.86 + * Atomically removes the topmost item from the freelist and returns a
1.87 + * pointer to it. Returns NULL if the list is empty.
1.88 + *
1.89 + * @return Item that was removed from front of list; NULL if list empty
1.90 + */
1.91 + item* pop() {
1.92 + item* __result;
1.93 + int __tmp;
1.94 + __asm__ __volatile__
1.95 + (" movl %%ebx, %%edi\n\t"
1.96 + "L1_%=: testl %%eax, %%eax\n\t" // _M_top == NULL?
1.97 + " je L2_%=\n\t" // If yes, we're done
1.98 + " movl (%%eax), %%ebx\n\t" // new top = _M._M_data._M_top->_M_next
1.99 + " leal 1(%%edx),%%ecx\n\t" // new sequence = _M._M_data._M_sequence + 1
1.100 + "lock; cmpxchg8b (%%esi)\n\t"
1.101 + " jne L1_%=\n\t" // We failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
1.102 + "L2_%=: movl %%edi, %%ebx"
1.103 + :"=a" (__result), "=d" (__tmp)
1.104 + :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "S" (&_M._M_data)
1.105 + :"edi", "ecx", "memory", "cc");
1.106 + return __result;
1.107 + }
1.108 +
1.109 + /**
1.110 + * Atomically detaches all items from the list and returns a pointer to the
1.111 + * topmost item. The items are still chained and may be traversed safely as
1.112 + * they're now "owned" by the calling thread.
1.113 + *
1.114 + * @return Pointer to topmost item in the list; NULL if list empty
1.115 + */
1.116 + item* clear() {
1.117 + item* __result;
1.118 + int __tmp;
1.119 + __asm__ __volatile__
1.120 + (" movl %%ebx, %%edi\n\t"
1.121 + "L1_%=: testl %%eax, %%eax\n\t" // _M_top == NULL?
1.122 + " je L2_%=\n\t" // If yes, we're done
1.123 + " xorl %%ebx, %%ebx\n\t" // We're attempting to set _M_top to NULL
1.124 + " leal 1(%%edx),%%ecx\n\t" // new sequence = _M._M_data._M_sequence + 1
1.125 + "lock; cmpxchg8b (%%esi)\n\t"
1.126 + " jne L1_%=\n\t" // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
1.127 + "L2_%=: movl %%edi, %%ebx"
1.128 + :"=a" (__result), "=d" (__tmp)
1.129 + :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "S" (&_M._M_data)
1.130 + :"edi", "ecx", "memory", "cc");
1.131 + return __result;
1.132 + }
1.133 +
1.134 +private:
1.135 + union {
1.136 + long long _M_align;
1.137 + struct {
1.138 + item* _M_top; // Topmost element in the freelist
1.139 + unsigned int _M_sequence; // Sequence counter to prevent "ABA problem"
1.140 + } _M_data;
1.141 + } _M;
1.142 +
1.143 + _STLP_atomic_freelist(const _STLP_atomic_freelist&);
1.144 + _STLP_atomic_freelist& operator=(const _STLP_atomic_freelist&);
1.145 +};
1.146 +
1.147 +# endif /* if defined(__GNUC__) && defined(__i386__) */
1.148 +
1.149 +#elif defined (_STLP_WIN32THREADS)
1.150 +
1.151 +# if !defined (_WIN64)
1.152 +# define _STLP_USE_ASM_IMPLEMENTATION
1.153 +# endif
1.154 +
1.155 +// Here are the compiler/platform requirements for the thread safe and
1.156 +// lock free singly linked list implementation:
1.157 +# if defined (_STLP_USE_ASM_IMPLEMENTATION)
1.158 +// For the asm version:
1.159 +# if defined (_STLP_MSVC) && defined (_M_IX86) && (_M_IX86 >= 500)
1.160 +# define _STLP_HAS_ATOMIC_FREELIST
1.161 +# endif
1.162 +# else
1.163 +// For the API based version:
1.164 +# if defined (_STLP_NEW_PLATFORM_SDK) && (!defined (WINVER) || (WINVER >= 0x0501)) && \
1.165 + (!defined (_WIN32_WINNT) || (_WIN32_WINNT >= 0x0501))
1.166 +# define _STLP_HAS_ATOMIC_FREELIST
1.167 +# endif
1.168 +# endif
1.169 +
1.170 +# if defined (_STLP_HAS_ATOMIC_FREELIST)
1.171 +# if defined (_STLP_USE_ASM_IMPLEMENTATION)
1.172 +# if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) || defined (__ICL)
1.173 +# pragma warning (push)
1.174 +# pragma warning (disable : 4035) //function has no return value
1.175 +# endif
1.176 +# endif
1.177 +/**
1.178 + * Class that implements a non-blocking and thread-safe freelist.
1.179 + * It is used for the lock-free node allocation engine.
1.180 + *
1.181 + * @author felixw@inin.com
1.182 + */
1.183 +class _STLP_atomic_freelist {
1.184 +public:
1.185 + /**
1.186 + * Type representing items of the freelist
1.187 + */
1.188 +# if defined (_STLP_USE_ASM_IMPLEMENTATION)
1.189 + struct item {
1.190 + item* _M_next;
1.191 + };
1.192 +# else
1.193 + typedef SLIST_ENTRY item;
1.194 +# endif
1.195 +
1.196 + _STLP_atomic_freelist() {
1.197 + // Statically assert layout of member is as expected by assembly code
1.198 +# if defined (_STLP_USE_ASM_IMPLEMENTATION)
1.199 + _STLP_STATIC_ASSERT((sizeof(item) == sizeof(item*)) && (sizeof(_M) == 8))
1.200 + _M._M_data._M_top = 0;
1.201 + _M._M_data._M_sequence = 0;
1.202 +# else
1.203 + InitializeSListHead(&_M_head);
1.204 +# endif
1.205 + }
1.206 +
1.207 + /**
1.208 + * Atomically pushes the specified item onto the freelist.
1.209 + *
1.210 + * @param __item [in] Item to add to the front of the list
1.211 + */
1.212 + void push(item* __item) {
1.213 +# if defined (_STLP_USE_ASM_IMPLEMENTATION)
1.214 + __asm
1.215 + {
1.216 + mov esi, this
1.217 + mov ebx, __item
1.218 + mov eax, [esi] // _M._M_data._M_top
1.219 + mov edx, [esi+4] // _M._M_data._M_sequence
1.220 + L1: mov [ebx], eax // __item._M_next = _M._M_data._M_top
1.221 + lea ecx, [edx+1] // new sequence = _M._M_data._M_sequence + 1
1.222 + lock cmpxchg8b qword ptr [esi]
1.223 + jne L1 // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
1.224 + }
1.225 +# else
1.226 + InterlockedPushEntrySList(&_M_head, __item);
1.227 +# endif
1.228 + }
1.229 +
1.230 + /**
1.231 + * Atomically removes the topmost item from the freelist and returns a
1.232 + * pointer to it. Returns NULL if the list is empty.
1.233 + *
1.234 + * @return Item that was removed from front of list; NULL if list empty
1.235 + */
1.236 + item* pop() {
1.237 +# if defined (_STLP_USE_ASM_IMPLEMENTATION)
1.238 + __asm
1.239 + {
1.240 + mov esi, this
1.241 + mov eax, [esi] // _M._M_data._M_top
1.242 + mov edx, [esi+4] // _M._M_data._M_sequence
1.243 + L1: test eax, eax // _M_top == NULL?
1.244 + je L2 // Yes, we're done
1.245 + mov ebx, [eax] // new top = _M._M_data._M_top->_M_next
1.246 + lea ecx, [edx+1] // new sequence = _M._M_data._M_sequence + 1
1.247 + lock cmpxchg8b qword ptr [esi]
1.248 + jne L1 // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
1.249 + L2:
1.250 + }
1.251 +# else
1.252 + return InterlockedPopEntrySList(&_M_head);
1.253 +# endif
1.254 + }
1.255 +
1.256 + /**
1.257 + * Atomically detaches all items from the list and returns pointer to the
1.258 + * topmost. The items are still chained and may be traversed safely as
1.259 + * they're now "owned" by the calling thread.
1.260 + *
1.261 + * @return Pointer to topmost item in the list; NULL if list empty
1.262 + */
1.263 + item* clear() {
1.264 +# if defined (_STLP_USE_ASM_IMPLEMENTATION)
1.265 + __asm
1.266 + {
1.267 + mov esi, this
1.268 + mov eax, [esi] // _M._M_data._M_top
1.269 + mov edx, [esi+4] // _M._M_data._M_sequence
1.270 + L1: test eax, eax // _M_top == NULL?
1.271 + je L2 // Yes, we're done
1.272 + xor ebx,ebx // We're attempting to set _M._M_data._M_top to NULL
1.273 + lea ecx, [edx+1] // new sequence = _M._M_data._M_sequence + 1
1.274 + lock cmpxchg8b qword ptr [esi]
1.275 + jne L1 // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
1.276 + L2:
1.277 + }
1.278 +# else
1.279 + return InterlockedFlushSList(&_M_head);
1.280 +# endif
1.281 + }
1.282 +
1.283 +private:
1.284 +# if defined (_STLP_USE_ASM_IMPLEMENTATION)
1.285 + union {
1.286 + __int64 _M_align;
1.287 + struct {
1.288 + item* _M_top; // Topmost element in the freelist
1.289 + unsigned int _M_sequence; // Sequence counter to prevent "ABA problem"
1.290 + } _M_data;
1.291 + } _M;
1.292 +# else
1.293 + SLIST_HEADER _M_head;
1.294 +# endif
1.295 +
1.296 + _STLP_atomic_freelist(const _STLP_atomic_freelist&);
1.297 + _STLP_atomic_freelist& operator = (const _STLP_atomic_freelist&);
1.298 +};
1.299 +
1.300 +# if defined (_STLP_USE_ASM_IMPLEMENTATION)
1.301 +# if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) || defined (__ICL)
1.302 +# pragma warning (pop)
1.303 +# endif
1.304 +# endif
1.305 +
1.306 +# endif /* _STLP_HAS_ATOMIC_FREELIST */
1.307 +
1.308 +#endif
1.309 +
1.310 +#endif /* _STLP_LOCK_FREE_SLIST_H */
