3 * A lock-free somewhat-queue that doesn't
4 * require hazard pointers.
6 * (C) Copyright 2011 Xamarin Inc.
7 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
11 * The queue is a linked list of arrays (chunks). Chunks are never
12 * removed from the list, only added to the end, in a lock-free manner.
14 * Adding or removing an entry in the queue is only possible at the
15 * end. To do so, the thread first has to increment or decrement
16 * q->num_used_entries. The entry thus added or removed now "belongs"
17 * to that thread. It first CASes the state to BUSY, writes/reads the
18 * entry data, and then sets the state to USED or FREE.
23 #include <mono/utils/atomic.h>
24 #include <mono/utils/mono-membar.h>
25 #ifdef SGEN_WITHOUT_MONO
26 #include <mono/sgen/sgen-gc.h>
27 #include <mono/sgen/sgen-client.h>
29 #include <mono/utils/mono-mmap.h>
32 #include <mono/utils/lock-free-array-queue.h>
34 struct _MonoLockFreeArrayChunk {
35 MonoLockFreeArrayChunk *next;
37 char entries [MONO_ZERO_LEN_ARRAY];
40 typedef MonoLockFreeArrayChunk Chunk;
42 #define CHUNK_NTH(arr,chunk,index) ((chunk)->entries + (index) * (arr)->entry_size)
45 alloc_chunk (MonoLockFreeArray *arr)
47 int size = mono_pagesize ();
48 int num_entries = (size - (sizeof (Chunk) - arr->entry_size * MONO_ZERO_LEN_ARRAY)) / arr->entry_size;
49 Chunk *chunk = (Chunk *) mono_valloc (NULL, size, MONO_MMAP_READ | MONO_MMAP_WRITE, arr->account_type);
51 chunk->num_entries = num_entries;
56 free_chunk (Chunk *chunk, MonoMemAccountType type)
58 mono_vfree (chunk, mono_pagesize (), type);
62 mono_lock_free_array_nth (MonoLockFreeArray *arr, int index)
66 g_assert (index >= 0);
68 if (!arr->chunk_list) {
69 chunk = alloc_chunk (arr);
70 mono_memory_write_barrier ();
71 if (InterlockedCompareExchangePointer ((volatile gpointer *)&arr->chunk_list, chunk, NULL) != NULL)
72 free_chunk (chunk, arr->account_type);
75 chunk = arr->chunk_list;
78 while (index >= chunk->num_entries) {
79 Chunk *next = chunk->next;
81 next = alloc_chunk (arr);
82 mono_memory_write_barrier ();
83 if (InterlockedCompareExchangePointer ((volatile gpointer *) &chunk->next, next, NULL) != NULL) {
84 free_chunk (next, arr->account_type);
89 index -= chunk->num_entries;
93 return CHUNK_NTH (arr, chunk, index);
97 mono_lock_free_array_iterate (MonoLockFreeArray *arr, MonoLockFreeArrayIterateFunc func, gpointer user_data)
100 for (chunk = arr->chunk_list; chunk; chunk = chunk->next) {
102 for (i = 0; i < chunk->num_entries; ++i) {
103 gpointer result = func (i, CHUNK_NTH (arr, chunk, i), user_data);
112 mono_lock_free_array_cleanup (MonoLockFreeArray *arr)
116 chunk = arr->chunk_list;
117 arr->chunk_list = NULL;
119 Chunk *next = chunk->next;
120 free_chunk (chunk, arr->account_type);
133 gpointer data [MONO_ZERO_LEN_ARRAY];
136 typedef MonoLockFreeArrayQueue Queue;
138 /* The queue's entry size, calculated from the array's. */
139 #define ENTRY_SIZE(q) ((q)->array.entry_size - sizeof (gpointer))
142 mono_lock_free_array_queue_push (MonoLockFreeArrayQueue *q, gpointer entry_data_ptr)
148 index = InterlockedIncrement (&q->num_used_entries) - 1;
149 entry = (Entry *) mono_lock_free_array_nth (&q->array, index);
150 } while (InterlockedCompareExchange (&entry->state, STATE_BUSY, STATE_FREE) != STATE_FREE);
152 mono_memory_write_barrier ();
154 memcpy (entry->data, entry_data_ptr, ENTRY_SIZE (q));
156 mono_memory_write_barrier ();
158 entry->state = STATE_USED;
160 mono_memory_barrier ();
163 num_used = q->num_used_entries;
164 if (num_used > index)
166 } while (InterlockedCompareExchange (&q->num_used_entries, index + 1, num_used) != num_used);
168 mono_memory_write_barrier ();
172 mono_lock_free_array_queue_pop (MonoLockFreeArrayQueue *q, gpointer entry_data_ptr)
179 index = q->num_used_entries;
182 } while (InterlockedCompareExchange (&q->num_used_entries, index - 1, index) != index);
184 entry = (Entry *) mono_lock_free_array_nth (&q->array, index - 1);
185 } while (InterlockedCompareExchange (&entry->state, STATE_BUSY, STATE_USED) != STATE_USED);
187 /* Reading the item must happen before CASing the state. */
188 mono_memory_barrier ();
190 memcpy (entry_data_ptr, entry->data, ENTRY_SIZE (q));
192 mono_memory_barrier ();
194 entry->state = STATE_FREE;
196 mono_memory_write_barrier ();
202 mono_lock_free_array_queue_cleanup (MonoLockFreeArrayQueue *q)
204 mono_lock_free_array_cleanup (&q->array);
205 q->num_used_entries = 0;