2 * mono-split-ordered-list.c: A lock-free split ordered list.
5 * Rodrigo Kumpera (kumpera@gmail.com)
9 * This is an implementation of Maged Michael's lock-free linked-list set.
10 * For more details see:
11 * "High Performance Dynamic Lock-Free Hash Tables and List-Based Sets"
12 * Maged M. Michael 2002
14 * http://www.research.ibm.com/people/m/michael/spaa-2002.pdf
17 #include <mono/utils/mono-linked-list-set.h>
19 #include <mono/utils/atomic.h>
21 static inline gpointer
22 mask (gpointer n, uintptr_t bit)
24 return (gpointer)(((uintptr_t)n) | bit);
28 get_hazardous_pointer_with_mask (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index)
35 /* If we don't have hazard pointers just return the
39 /* Make it hazardous */
40 mono_hazard_pointer_set (hp, hazard_index, mono_lls_pointer_unmask (p));
42 mono_memory_barrier ();
44 /* Check that it's still the same. If not, try
47 mono_hazard_pointer_clear (hp, hazard_index);
57 Initialize @list and will use @free_node_func to release memory.
58 If @free_node_func is null the caller is responsible for releasing node memory.
59 If @free_node_func may lock, @free_node_func_locking must be
60 HAZARD_FREE_MAY_LOCK; otherwise, HAZARD_FREE_NO_LOCK. It is ignored if
61 @free_node_func is null.
64 mono_lls_init (MonoLinkedListSet *list, void (*free_node_func)(void *), HazardFreeLocking free_node_func_locking)
67 list->free_node_func = free_node_func;
68 list->locking = free_node_func_locking;
72 Search @list for element with key @key.
73 @context specifies whether the function is being called from a lock-free (i.e.
74 signal handler or world stopped) context. It is only relevant if a node free
76 The nodes next, cur and prev are returned in @hp.
77 Returns true if a node with key @key was found.
80 mono_lls_find (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, uintptr_t key, HazardFreeContext context)
82 MonoLinkedListSetNode *cur, *next;
83 MonoLinkedListSetNode **prev;
90 * prev is not really a hazardous pointer, but we return prev
91 * in hazard pointer 2, so we set it here. Note also that
92 * prev is not a pointer to a node. We use here the fact that
93 * the first element in a node is the next pointer, so it
94 * works, but it's not pretty.
96 mono_hazard_pointer_set (hp, 2, prev);
98 cur = (MonoLinkedListSetNode *) get_hazardous_pointer_with_mask ((gpointer*)prev, hp, 1);
103 next = (MonoLinkedListSetNode *) get_hazardous_pointer_with_mask ((gpointer*)&cur->next, hp, 0);
107 * We need to make sure that we dereference prev below
108 * after reading cur->next above, so we need a read
111 mono_memory_read_barrier ();
116 if (!mono_lls_pointer_get_mark (next)) {
118 return cur_key == key;
121 mono_hazard_pointer_set (hp, 2, cur);
123 next = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (next);
124 if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, next, cur) == cur) {
125 /* The hazard pointer must be cleared after the CAS. */
126 mono_memory_write_barrier ();
127 mono_hazard_pointer_clear (hp, 1);
128 if (list->free_node_func)
129 mono_thread_hazardous_queue_free (cur, list->free_node_func);
133 cur = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (next);
134 mono_hazard_pointer_set (hp, 1, cur);
139 Insert @value into @list.
140 @context specifies whether the function is being called from a lock-free (i.e.
141 signal handler or world stopped) context. It is only relevant if a node free
143 The nodes value, cur and prev are returned in @hp.
144 Return true if @value was inserted by this call. If it returns FALSE, it's the caller
145 resposibility to release memory.
148 mono_lls_insert (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value, HazardFreeContext context)
150 MonoLinkedListSetNode *cur, **prev;
151 /*We must do a store barrier before inserting
152 to make sure all values in @node are globally visible.*/
153 mono_memory_barrier ();
156 if (mono_lls_find (list, hp, value->key, context))
158 cur = (MonoLinkedListSetNode *) mono_hazard_pointer_get_val (hp, 1);
159 prev = (MonoLinkedListSetNode **) mono_hazard_pointer_get_val (hp, 2);
162 mono_hazard_pointer_set (hp, 0, value);
163 /* The CAS must happen after setting the hazard pointer. */
164 mono_memory_write_barrier ();
165 if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, value, cur) == cur)
171 Search @list for element with key @key and remove it.
172 @context specifies whether the function is being called from a lock-free (i.e.
173 signal handler or world stopped) context. It is only relevant if a node free
175 The nodes next, cur and prev are returned in @hp
176 Returns true if @value was removed by this call.
179 mono_lls_remove (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value, HazardFreeContext context)
181 MonoLinkedListSetNode *cur, **prev, *next;
183 if (!mono_lls_find (list, hp, value->key, context))
186 next = (MonoLinkedListSetNode *) mono_hazard_pointer_get_val (hp, 0);
187 cur = (MonoLinkedListSetNode *) mono_hazard_pointer_get_val (hp, 1);
188 prev = (MonoLinkedListSetNode **) mono_hazard_pointer_get_val (hp, 2);
190 g_assert (cur == value);
192 if (InterlockedCompareExchangePointer ((volatile gpointer*)&cur->next, mask (next, 1), next) != next)
194 /* The second CAS must happen before the first. */
195 mono_memory_write_barrier ();
196 if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, mono_lls_pointer_unmask (next), cur) == cur) {
197 /* The CAS must happen before the hazard pointer clear. */
198 mono_memory_write_barrier ();
199 mono_hazard_pointer_clear (hp, 1);
200 if (list->free_node_func)
201 mono_thread_hazardous_try_free (value, list->free_node_func);
203 mono_lls_find (list, hp, value->key, context);