FreeRDP
Loading...
Searching...
No Matches
interlocked.c
1
20#include <winpr/config.h>
21
22#include <winpr/assert.h>
23#include <winpr/wlog.h>
24#include <winpr/platform.h>
25#include <winpr/synch.h>
26#include <winpr/handle.h>
27
28#include <winpr/interlocked.h>
29
30/* Singly-Linked List */
31
32#ifndef _WIN32
33
34#include <stdio.h>
35#include <stdlib.h>
36
37VOID InitializeSListHead(WINPR_PSLIST_HEADER ListHead)
38{
39 WINPR_ASSERT(ListHead);
40#ifdef _WIN64
41 ListHead->s.Alignment = 0;
42 ListHead->s.Region = 0;
43 ListHead->Header8.Init = 1;
44#else
45 ListHead->Alignment = 0;
46#endif
47}
48
49WINPR_PSLIST_ENTRY InterlockedPushEntrySList(WINPR_PSLIST_HEADER ListHead,
50 WINPR_PSLIST_ENTRY ListEntry)
51{
52 WINPR_SLIST_HEADER old = WINPR_C_ARRAY_INIT;
53 WINPR_SLIST_HEADER newHeader = WINPR_C_ARRAY_INIT;
54
55 WINPR_ASSERT(ListHead);
56 WINPR_ASSERT(ListEntry);
57#ifdef _WIN64
58 newHeader.HeaderX64.NextEntry = (((ULONG_PTR)ListEntry) >> 4);
59
60 while (1)
61 {
62 old = *ListHead;
63
64 ListEntry->Next = (PSLIST_ENTRY)(((ULONG_PTR)old.HeaderX64.NextEntry) << 4);
65
66 newHeader.HeaderX64.Depth = old.HeaderX64.Depth + 1;
67 newHeader.HeaderX64.Sequence = old.HeaderX64.Sequence + 1;
68
69 if (InterlockedCompareExchange64((LONGLONG*)ListHead, newHeader).Alignment, old).Alignment))
70 {
71 InterlockedCompareExchange64(&((LONGLONG*)ListHead)[1], newHeader).Region,
72 old).Region);
73 break;
74 }
75 }
76
77 return (PSLIST_ENTRY)((ULONG_PTR)old.HeaderX64.NextEntry << 4);
78#else
79 newHeader.s.Next.Next = ListEntry;
80
81 do
82 {
83 old = *ListHead;
84 ListEntry->Next = old.s.Next.Next;
85 newHeader.s.Depth = old.s.Depth + 1;
86 newHeader.s.Sequence = old.s.Sequence + 1;
87 if (old.Alignment > INT64_MAX)
88 return nullptr;
89 if (newHeader.Alignment > INT64_MAX)
90 return nullptr;
91 if (ListHead->Alignment > INT64_MAX)
92 return nullptr;
93 } while (InterlockedCompareExchange64((LONGLONG*)&ListHead->Alignment,
94 (LONGLONG)newHeader.Alignment,
95 (LONGLONG)old.Alignment) != (LONGLONG)old.Alignment);
96
97 return old.s.Next.Next;
98#endif
99}
100
101WINPR_PSLIST_ENTRY InterlockedPushListSListEx(WINPR_ATTR_UNUSED WINPR_PSLIST_HEADER ListHead,
102 WINPR_ATTR_UNUSED WINPR_PSLIST_ENTRY List,
103 WINPR_ATTR_UNUSED WINPR_PSLIST_ENTRY ListEnd,
104 WINPR_ATTR_UNUSED ULONG Count)
105{
106 WINPR_ASSERT(ListHead);
107 WINPR_ASSERT(List);
108 WINPR_ASSERT(ListEnd);
109
110 WLog_ERR("TODO", "TODO: implement");
111#ifdef _WIN64
112
113#else
114
115#endif
116 return nullptr;
117}
118
119WINPR_PSLIST_ENTRY InterlockedPopEntrySList(WINPR_PSLIST_HEADER ListHead)
120{
121 WINPR_SLIST_HEADER old = WINPR_C_ARRAY_INIT;
122 WINPR_SLIST_HEADER newHeader = WINPR_C_ARRAY_INIT;
123 WINPR_PSLIST_ENTRY entry = nullptr;
124
125 WINPR_ASSERT(ListHead);
126
127#ifdef _WIN64
128 while (1)
129 {
130 old = *ListHead;
131
132 entry = (PSLIST_ENTRY)(((ULONG_PTR)old.HeaderX64.NextEntry) << 4);
133
134 if (!entry)
135 return nullptr;
136
137 newHeader.HeaderX64.NextEntry = ((ULONG_PTR)entry->Next) >> 4;
138 newHeader.HeaderX64.Depth = old.HeaderX64.Depth - 1;
139 newHeader.HeaderX64.Sequence = old.HeaderX64.Sequence - 1;
140
141 if (InterlockedCompareExchange64((LONGLONG*)ListHead, newHeader).Alignment, old).Alignment))
142 {
143 InterlockedCompareExchange64(&((LONGLONG*)ListHead)[1], newHeader).Region,
144 old).Region);
145 break;
146 }
147 }
148#else
149 do
150 {
151 old = *ListHead;
152
153 entry = old.s.Next.Next;
154
155 if (!entry)
156 return nullptr;
157
158 newHeader.s.Next.Next = entry->Next;
159 newHeader.s.Depth = old.s.Depth - 1;
160 newHeader.s.Sequence = old.s.Sequence + 1;
161
162 if (old.Alignment > INT64_MAX)
163 return nullptr;
164 if (newHeader.Alignment > INT64_MAX)
165 return nullptr;
166 if (ListHead->Alignment > INT64_MAX)
167 return nullptr;
168 } while (InterlockedCompareExchange64((LONGLONG*)&ListHead->Alignment,
169 (LONGLONG)newHeader.Alignment,
170 (LONGLONG)old.Alignment) != (LONGLONG)old.Alignment);
171#endif
172 return entry;
173}
174
175WINPR_PSLIST_ENTRY InterlockedFlushSList(WINPR_PSLIST_HEADER ListHead)
176{
177 WINPR_SLIST_HEADER old = WINPR_C_ARRAY_INIT;
178 WINPR_SLIST_HEADER newHeader = WINPR_C_ARRAY_INIT;
179
180 WINPR_ASSERT(ListHead);
181 if (!QueryDepthSList(ListHead))
182 return nullptr;
183
184#ifdef _WIN64
185 newHeader).Alignment = 0;
186 newHeader).Region = 0;
187 newHeader.HeaderX64.HeaderType = 1;
188
189 while (1)
190 {
191 old = *ListHead;
192 newHeader.HeaderX64.Sequence = old.HeaderX64.Sequence + 1;
193
194 if (InterlockedCompareExchange64((LONGLONG*)ListHead, newHeader).Alignment, old).Alignment))
195 {
196 InterlockedCompareExchange64(&((LONGLONG*)ListHead)[1], newHeader).Region,
197 old).Region);
198 break;
199 }
200 }
201
202 return (PSLIST_ENTRY)(((ULONG_PTR)old.HeaderX64.NextEntry) << 4);
203#else
204 newHeader.Alignment = 0;
205
206 do
207 {
208 old = *ListHead;
209 newHeader.s.Sequence = old.s.Sequence + 1;
210
211 if (old.Alignment > INT64_MAX)
212 return nullptr;
213 if (newHeader.Alignment > INT64_MAX)
214 return nullptr;
215 if (ListHead->Alignment > INT64_MAX)
216 return nullptr;
217 } while (InterlockedCompareExchange64((LONGLONG*)&ListHead->Alignment,
218 (LONGLONG)newHeader.Alignment,
219 (LONGLONG)old.Alignment) != (LONGLONG)old.Alignment);
220
221 return old.s.Next.Next;
222#endif
223}
224
225USHORT QueryDepthSList(WINPR_PSLIST_HEADER ListHead)
226{
227 WINPR_ASSERT(ListHead);
228
229#ifdef _WIN64
230 return ListHead->HeaderX64.Depth;
231#else
232 return ListHead->s.Depth;
233#endif
234}
235
236LONG InterlockedIncrement(LONG volatile* Addend)
237{
238 WINPR_ASSERT(Addend);
239
240#if defined(__GNUC__) || defined(__clang__)
241 WINPR_PRAGMA_DIAG_PUSH
242 WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
243 return __sync_add_and_fetch(Addend, 1);
244 WINPR_PRAGMA_DIAG_POP
245#else
246 return 0;
247#endif
248}
249
250LONG InterlockedDecrement(LONG volatile* Addend)
251{
252 WINPR_ASSERT(Addend);
253
254#if defined(__GNUC__) || defined(__clang__)
255 WINPR_PRAGMA_DIAG_PUSH
256 WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
257 return __sync_sub_and_fetch(Addend, 1);
258 WINPR_PRAGMA_DIAG_POP
259#else
260 return 0;
261#endif
262}
263
264LONG InterlockedExchange(LONG volatile* Target, LONG Value)
265{
266 WINPR_ASSERT(Target);
267
268#if defined(__GNUC__) || defined(__clang__)
269 WINPR_PRAGMA_DIAG_PUSH
270 WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
271 return __sync_val_compare_and_swap(Target, *Target, Value);
272 WINPR_PRAGMA_DIAG_POP
273#else
274 return 0;
275#endif
276}
277
278LONG InterlockedExchangeAdd(LONG volatile* Addend, LONG Value)
279{
280 WINPR_ASSERT(Addend);
281
282#if defined(__GNUC__) || defined(__clang__)
283 WINPR_PRAGMA_DIAG_PUSH
284 WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
285 return __sync_fetch_and_add(Addend, Value);
286 WINPR_PRAGMA_DIAG_POP
287#else
288 return 0;
289#endif
290}
291
292LONG InterlockedCompareExchange(LONG volatile* Destination, LONG Exchange, LONG Comperand)
293{
294 WINPR_ASSERT(Destination);
295
296#if defined(__GNUC__) || defined(__clang__)
297 WINPR_PRAGMA_DIAG_PUSH
298 WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
299 return __sync_val_compare_and_swap(Destination, Comperand, Exchange);
300 WINPR_PRAGMA_DIAG_POP
301#else
302 return 0;
303#endif
304}
305
306PVOID InterlockedCompareExchangePointer(PVOID volatile* Destination, PVOID Exchange,
307 PVOID Comperand)
308{
309 WINPR_ASSERT(Destination);
310
311#if defined(__GNUC__) || defined(__clang__)
312 WINPR_PRAGMA_DIAG_PUSH
313 WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
314 return __sync_val_compare_and_swap(Destination, Comperand, Exchange);
315 WINPR_PRAGMA_DIAG_POP
316#else
317 return 0;
318#endif
319}
320
321#endif /* _WIN32 */
322
323#if defined(_WIN32) && !defined(WINPR_INTERLOCKED_COMPARE_EXCHANGE64)
324
325/* InterlockedCompareExchange64 already defined */
326
327#elif defined(_WIN32) && defined(WINPR_INTERLOCKED_COMPARE_EXCHANGE64)
328
329static volatile HANDLE mutex = nullptr;
330
331BOOL static_mutex_lock(volatile HANDLE* static_mutex)
332{
333 if (*static_mutex == nullptr)
334 {
335 HANDLE handle;
336
337 if (!(handle = CreateMutex(nullptr, FALSE, nullptr)))
338 return FALSE;
339
340 if (InterlockedCompareExchangePointer((PVOID*)static_mutex, (PVOID)handle, nullptr) !=
341 nullptr)
342 (void)CloseHandle(handle);
343 }
344
345 return (WaitForSingleObject(*static_mutex, INFINITE) == WAIT_OBJECT_0);
346}
347
348LONGLONG InterlockedCompareExchange64(LONGLONG volatile* Destination, LONGLONG Exchange,
349 LONGLONG Comperand)
350{
351 LONGLONG previousValue = 0;
352 BOOL locked = static_mutex_lock(&mutex);
353
354 previousValue = *Destination;
355
356 if (*Destination == Comperand)
357 *Destination = Exchange;
358
359 if (locked)
360 (void)ReleaseMutex(mutex);
361 else
362 (void)fprintf(stderr,
363 "WARNING: InterlockedCompareExchange64 operation might have failed\n");
364
365 return previousValue;
366}
367
368#elif (defined(ANDROID) && ANDROID) || \
369 (defined(__GNUC__) && !defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_8))
370
371#include <pthread.h>
372
373static pthread_mutex_t mutex;
374
375LONGLONG InterlockedCompareExchange64(LONGLONG volatile* Destination, LONGLONG Exchange,
376 LONGLONG Comperand)
377{
378 LONGLONG previousValue = 0;
379
380 pthread_mutex_lock(&mutex);
381
382 previousValue = *Destination;
383
384 if (*Destination == Comperand)
385 *Destination = Exchange;
386
387 pthread_mutex_unlock(&mutex);
388
389 return previousValue;
390}
391
392#else
393
394LONGLONG InterlockedCompareExchange64(LONGLONG volatile* Destination, LONGLONG Exchange,
395 LONGLONG Comperand)
396{
397 WINPR_ASSERT(Destination);
398
399#if defined(__GNUC__) || defined(__clang__)
400 WINPR_PRAGMA_DIAG_PUSH
401 WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
402 return __sync_val_compare_and_swap(Destination, Comperand, Exchange);
403 WINPR_PRAGMA_DIAG_POP
404#else
405 return 0;
406#endif
407}
408
409#endif
410
411/* Doubly-Linked List */
412
421VOID InitializeListHead(WINPR_PLIST_ENTRY ListHead)
422{
423 WINPR_ASSERT(ListHead);
424 ListHead->Flink = ListHead->Blink = ListHead;
425}
426
427BOOL IsListEmpty(const WINPR_LIST_ENTRY* ListHead)
428{
429 WINPR_ASSERT(ListHead);
430 return (BOOL)(ListHead->Flink == ListHead);
431}
432
433BOOL RemoveEntryList(WINPR_PLIST_ENTRY Entry)
434{
435 WINPR_ASSERT(Entry);
436 WINPR_PLIST_ENTRY OldFlink = Entry->Flink;
437 WINPR_ASSERT(OldFlink);
438
439 WINPR_PLIST_ENTRY OldBlink = Entry->Blink;
440 WINPR_ASSERT(OldBlink);
441
442 OldFlink->Blink = OldBlink;
443 OldBlink->Flink = OldFlink;
444
445 return (BOOL)(OldFlink == OldBlink);
446}
447
448VOID InsertHeadList(WINPR_PLIST_ENTRY ListHead, WINPR_PLIST_ENTRY Entry)
449{
450 WINPR_ASSERT(ListHead);
451 WINPR_ASSERT(Entry);
452
453 WINPR_PLIST_ENTRY OldFlink = ListHead->Flink;
454 WINPR_ASSERT(OldFlink);
455
456 Entry->Flink = OldFlink;
457 Entry->Blink = ListHead;
458 OldFlink->Blink = Entry;
459 ListHead->Flink = Entry;
460}
461
462WINPR_PLIST_ENTRY RemoveHeadList(WINPR_PLIST_ENTRY ListHead)
463{
464 WINPR_ASSERT(ListHead);
465
466 WINPR_PLIST_ENTRY Entry = ListHead->Flink;
467 WINPR_ASSERT(Entry);
468
469 WINPR_PLIST_ENTRY Flink = Entry->Flink;
470 WINPR_ASSERT(Flink);
471
472 ListHead->Flink = Flink;
473 Flink->Blink = ListHead;
474
475 return Entry;
476}
477
478VOID InsertTailList(WINPR_PLIST_ENTRY ListHead, WINPR_PLIST_ENTRY Entry)
479{
480 WINPR_ASSERT(ListHead);
481 WINPR_ASSERT(Entry);
482
483 WINPR_PLIST_ENTRY OldBlink = ListHead->Blink;
484 WINPR_ASSERT(OldBlink);
485
486 Entry->Flink = ListHead;
487 Entry->Blink = OldBlink;
488 OldBlink->Flink = Entry;
489 ListHead->Blink = Entry;
490}
491
492WINPR_PLIST_ENTRY RemoveTailList(WINPR_PLIST_ENTRY ListHead)
493{
494 WINPR_ASSERT(ListHead);
495
496 WINPR_PLIST_ENTRY Entry = ListHead->Blink;
497 WINPR_ASSERT(Entry);
498
499 WINPR_PLIST_ENTRY Blink = Entry->Blink;
500 WINPR_ASSERT(Blink);
501
502 ListHead->Blink = Blink;
503 Blink->Flink = ListHead;
504
505 return Entry;
506}
507
508VOID AppendTailList(WINPR_PLIST_ENTRY ListHead, WINPR_PLIST_ENTRY ListToAppend)
509{
510 WINPR_ASSERT(ListHead);
511 WINPR_ASSERT(ListToAppend);
512
513 WINPR_PLIST_ENTRY ListEnd = ListHead->Blink;
514
515 ListHead->Blink->Flink = ListToAppend;
516 ListHead->Blink = ListToAppend->Blink;
517 ListToAppend->Blink->Flink = ListHead;
518 ListToAppend->Blink = ListEnd;
519}
520
521VOID PushEntryList(WINPR_PSINGLE_LIST_ENTRY ListHead, WINPR_PSINGLE_LIST_ENTRY Entry)
522{
523 WINPR_ASSERT(ListHead);
524 WINPR_ASSERT(Entry);
525
526 Entry->Next = ListHead->Next;
527 ListHead->Next = Entry;
528}
529
530WINPR_PSINGLE_LIST_ENTRY PopEntryList(WINPR_PSINGLE_LIST_ENTRY ListHead)
531{
532 WINPR_ASSERT(ListHead);
533 WINPR_PSINGLE_LIST_ENTRY FirstEntry = ListHead->Next;
534
535 if (FirstEntry != nullptr)
536 ListHead->Next = FirstEntry->Next;
537
538 return FirstEntry;
539}
WINPR_SLIST_HEADER
Definition interlocked.h:127