2 * lock-free-array-queue.c: A lock-free somewhat-queue that doesn't
3 * require hazard pointers.
5 * (C) Copyright 2011 Xamarin Inc.
6 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
10 * The queue is a linked list of arrays (chunks). Chunks are never
11 * removed from the list, only added to the end, in a lock-free manner.
13 * Adding or removing an entry in the queue is only possible at the
14 * end. To do so, the thread first has to increment or decrement
15 * q->num_used_entries. The entry thus added or removed now "belongs"
16 * to that thread. It first CASes the state to BUSY, writes/reads the
17 * entry data, and then sets the state to USED or FREE.
22 #include <mono/utils/atomic.h>
23 #include <mono/utils/mono-membar.h>
24 #ifdef SGEN_WITHOUT_MONO
25 #include <mono/sgen/sgen-gc.h>
26 #include <mono/sgen/sgen-client.h>
28 #include <mono/utils/mono-mmap.h>
31 #include <mono/utils/lock-free-array-queue.h>
33 struct _MonoLockFreeArrayChunk {
34 MonoLockFreeArrayChunk *next;
36 char entries [MONO_ZERO_LEN_ARRAY];
39 typedef MonoLockFreeArrayChunk Chunk;
41 #define CHUNK_NTH(arr,chunk,index) ((chunk)->entries + (index) * (arr)->entry_size)
44 alloc_chunk (MonoLockFreeArray *arr)
46 int size = mono_pagesize ();
47 int num_entries = (size - (sizeof (Chunk) - arr->entry_size * MONO_ZERO_LEN_ARRAY)) / arr->entry_size;
48 Chunk *chunk = (Chunk *) mono_valloc (NULL, size, MONO_MMAP_READ | MONO_MMAP_WRITE, arr->account_type);
50 chunk->num_entries = num_entries;
55 free_chunk (Chunk *chunk, MonoMemAccountType type)
57 mono_vfree (chunk, mono_pagesize (), type);
61 mono_lock_free_array_nth (MonoLockFreeArray *arr, int index)
65 g_assert (index >= 0);
67 if (!arr->chunk_list) {
68 chunk = alloc_chunk (arr);
69 mono_memory_write_barrier ();
70 if (InterlockedCompareExchangePointer ((volatile gpointer *)&arr->chunk_list, chunk, NULL) != NULL)
71 free_chunk (chunk, arr->account_type);
74 chunk = arr->chunk_list;
77 while (index >= chunk->num_entries) {
78 Chunk *next = chunk->next;
80 next = alloc_chunk (arr);
81 mono_memory_write_barrier ();
82 if (InterlockedCompareExchangePointer ((volatile gpointer *) &chunk->next, next, NULL) != NULL) {
83 free_chunk (next, arr->account_type);
88 index -= chunk->num_entries;
92 return CHUNK_NTH (arr, chunk, index);
96 mono_lock_free_array_iterate (MonoLockFreeArray *arr, MonoLockFreeArrayIterateFunc func, gpointer user_data)
99 for (chunk = arr->chunk_list; chunk; chunk = chunk->next) {
101 for (i = 0; i < chunk->num_entries; ++i) {
102 gpointer result = func (i, CHUNK_NTH (arr, chunk, i), user_data);
111 mono_lock_free_array_cleanup (MonoLockFreeArray *arr)
115 chunk = arr->chunk_list;
116 arr->chunk_list = NULL;
118 Chunk *next = chunk->next;
119 free_chunk (chunk, arr->account_type);
132 gpointer data [MONO_ZERO_LEN_ARRAY];
135 typedef MonoLockFreeArrayQueue Queue;
137 /* The queue's entry size, calculated from the array's. */
138 #define ENTRY_SIZE(q) ((q)->array.entry_size - sizeof (gpointer))
141 mono_lock_free_array_queue_push (MonoLockFreeArrayQueue *q, gpointer entry_data_ptr)
147 index = InterlockedIncrement (&q->num_used_entries) - 1;
148 entry = (Entry *) mono_lock_free_array_nth (&q->array, index);
149 } while (InterlockedCompareExchange (&entry->state, STATE_BUSY, STATE_FREE) != STATE_FREE);
151 mono_memory_write_barrier ();
153 memcpy (entry->data, entry_data_ptr, ENTRY_SIZE (q));
155 mono_memory_write_barrier ();
157 entry->state = STATE_USED;
159 mono_memory_barrier ();
162 num_used = q->num_used_entries;
163 if (num_used > index)
165 } while (InterlockedCompareExchange (&q->num_used_entries, index + 1, num_used) != num_used);
167 mono_memory_write_barrier ();
171 mono_lock_free_array_queue_pop (MonoLockFreeArrayQueue *q, gpointer entry_data_ptr)
178 index = q->num_used_entries;
181 } while (InterlockedCompareExchange (&q->num_used_entries, index - 1, index) != index);
183 entry = (Entry *) mono_lock_free_array_nth (&q->array, index - 1);
184 } while (InterlockedCompareExchange (&entry->state, STATE_BUSY, STATE_USED) != STATE_USED);
186 /* Reading the item must happen before CASing the state. */
187 mono_memory_barrier ();
189 memcpy (entry_data_ptr, entry->data, ENTRY_SIZE (q));
191 mono_memory_barrier ();
193 entry->state = STATE_FREE;
195 mono_memory_write_barrier ();
201 mono_lock_free_array_queue_cleanup (MonoLockFreeArrayQueue *q)
203 mono_lock_free_array_cleanup (&q->array);
204 q->num_used_entries = 0;