2 * lock-free-array-queue.c: A lock-free somewhat-queue that doesn't
3 * require hazard pointers.
5 * (C) Copyright 2011 Xamarin Inc.
9 * The queue is a linked list of arrays (chunks). Chunks are never
10 * removed from the list, only added to the end, in a lock-free manner.
12 * Adding or removing an entry in the queue is only possible at the
13 * end. To do so, the thread first has to increment or decrement
14 * q->num_used_entries. The entry thus added or removed now "belongs"
15 * to that thread. It first CASes the state to BUSY, writes/reads the
16 * entry data, and then sets the state to USED or FREE.
21 #include <mono/utils/atomic.h>
22 #include <mono/utils/mono-membar.h>
23 #ifdef SGEN_WITHOUT_MONO
24 #include <mono/sgen/sgen-gc.h>
25 #include <mono/sgen/sgen-client.h>
27 #include <mono/utils/mono-mmap.h>
30 #include <mono/utils/lock-free-array-queue.h>
32 struct _MonoLockFreeArrayChunk {
33 MonoLockFreeArrayChunk *next;
35 char entries [MONO_ZERO_LEN_ARRAY];
38 typedef MonoLockFreeArrayChunk Chunk;
40 #define CHUNK_NTH(arr,chunk,index) ((chunk)->entries + (index) * (arr)->entry_size)
43 alloc_chunk (MonoLockFreeArray *arr)
45 int size = mono_pagesize ();
46 int num_entries = (size - (sizeof (Chunk) - arr->entry_size * MONO_ZERO_LEN_ARRAY)) / arr->entry_size;
47 Chunk *chunk = (Chunk *) mono_valloc (NULL, size, MONO_MMAP_READ | MONO_MMAP_WRITE);
49 chunk->num_entries = num_entries;
54 free_chunk (Chunk *chunk)
56 mono_vfree (chunk, mono_pagesize ());
60 mono_lock_free_array_nth (MonoLockFreeArray *arr, int index)
64 g_assert (index >= 0);
66 if (!arr->chunk_list) {
67 chunk = alloc_chunk (arr);
68 mono_memory_write_barrier ();
69 if (InterlockedCompareExchangePointer ((volatile gpointer *)&arr->chunk_list, chunk, NULL) != NULL)
73 chunk = arr->chunk_list;
76 while (index >= chunk->num_entries) {
77 Chunk *next = chunk->next;
79 next = alloc_chunk (arr);
80 mono_memory_write_barrier ();
81 if (InterlockedCompareExchangePointer ((volatile gpointer *) &chunk->next, next, NULL) != NULL) {
87 index -= chunk->num_entries;
91 return CHUNK_NTH (arr, chunk, index);
95 mono_lock_free_array_iterate (MonoLockFreeArray *arr, MonoLockFreeArrayIterateFunc func, gpointer user_data)
98 for (chunk = arr->chunk_list; chunk; chunk = chunk->next) {
100 for (i = 0; i < chunk->num_entries; ++i) {
101 gpointer result = func (i, CHUNK_NTH (arr, chunk, i), user_data);
110 mono_lock_free_array_cleanup (MonoLockFreeArray *arr)
114 chunk = arr->chunk_list;
115 arr->chunk_list = NULL;
117 Chunk *next = chunk->next;
131 gpointer data [MONO_ZERO_LEN_ARRAY];
134 typedef MonoLockFreeArrayQueue Queue;
136 /* The queue's entry size, calculated from the array's. */
137 #define ENTRY_SIZE(q) ((q)->array.entry_size - sizeof (gpointer))
140 mono_lock_free_array_queue_push (MonoLockFreeArrayQueue *q, gpointer entry_data_ptr)
146 index = InterlockedIncrement (&q->num_used_entries) - 1;
147 entry = (Entry *) mono_lock_free_array_nth (&q->array, index);
148 } while (InterlockedCompareExchange (&entry->state, STATE_BUSY, STATE_FREE) != STATE_FREE);
150 mono_memory_write_barrier ();
152 memcpy (entry->data, entry_data_ptr, ENTRY_SIZE (q));
154 mono_memory_write_barrier ();
156 entry->state = STATE_USED;
158 mono_memory_barrier ();
161 num_used = q->num_used_entries;
162 if (num_used > index)
164 } while (InterlockedCompareExchange (&q->num_used_entries, index + 1, num_used) != num_used);
166 mono_memory_write_barrier ();
170 mono_lock_free_array_queue_pop (MonoLockFreeArrayQueue *q, gpointer entry_data_ptr)
177 index = q->num_used_entries;
180 } while (InterlockedCompareExchange (&q->num_used_entries, index - 1, index) != index);
182 entry = (Entry *) mono_lock_free_array_nth (&q->array, index - 1);
183 } while (InterlockedCompareExchange (&entry->state, STATE_BUSY, STATE_USED) != STATE_USED);
185 /* Reading the item must happen before CASing the state. */
186 mono_memory_barrier ();
188 memcpy (entry_data_ptr, entry->data, ENTRY_SIZE (q));
190 mono_memory_barrier ();
192 entry->state = STATE_FREE;
194 mono_memory_write_barrier ();
200 mono_lock_free_array_queue_cleanup (MonoLockFreeArrayQueue *q)
202 mono_lock_free_array_cleanup (&q->array);
203 q->num_used_entries = 0;