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