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 */ 34class _STLP_atomic_freelist { 35public: 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 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 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 */ 180class _STLP_atomic_freelist { 181public: 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 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 */ 308