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>
20 #include <mono/io-layer/io-layer.h>
22 static inline gpointer
23 mask (gpointer n
, uintptr_t bit
)
25 return (gpointer
)(((uintptr_t)n
) | bit
);
29 get_hazardous_pointer_with_mask (gpointer
volatile *pp
, MonoThreadHazardPointers
*hp
, int hazard_index
)
36 /* If we don't have hazard pointers just return the
40 /* Make it hazardous */
41 mono_hazard_pointer_set (hp
, hazard_index
, mono_lls_pointer_unmask (p
));
43 mono_memory_barrier ();
45 /* Check that it's still the same. If not, try
48 mono_hazard_pointer_clear (hp
, hazard_index
);
58 Initialize @list and will use @free_node_func to release memory.
59 If @free_node_func is null the caller is responsible for releasing node memory.
62 mono_lls_init (MonoLinkedListSet
*list
, void (*free_node_func
)(void *))
65 list
->free_node_func
= free_node_func
;
69 Search @list for element with key @key.
70 The nodes next, cur and prev are returned in @hp.
71 Returns true if a node with key @key was found.
72 This function cannot be called from a signal nor within interrupt context*.
73 XXX A variant that works within interrupted is possible if needed.
75 * interrupt context is when the current thread is reposible for another thread
76 been suspended at an arbritary point. This is a limitation of our SMR implementation.
79 mono_lls_find (MonoLinkedListSet
*list
, MonoThreadHazardPointers
*hp
, uintptr_t key
)
81 MonoLinkedListSetNode
*cur
, *next
;
82 MonoLinkedListSetNode
**prev
;
89 * prev is not really a hazardous pointer, but we return prev
90 * in hazard pointer 2, so we set it here. Note also that
91 * prev is not a pointer to a node. We use here the fact that
92 * the first element in a node is the next pointer, so it
93 * works, but it's not pretty.
95 mono_hazard_pointer_set (hp
, 2, prev
);
97 cur
= get_hazardous_pointer_with_mask ((gpointer
*)prev
, hp
, 1);
102 next
= get_hazardous_pointer_with_mask ((gpointer
*)&cur
->next
, hp
, 0);
106 * We need to make sure that we dereference prev below
107 * after reading cur->next above, so we need a read
110 mono_memory_read_barrier ();
115 if (!mono_lls_pointer_get_mark (next
)) {
117 return cur_key
== key
;
120 mono_hazard_pointer_set (hp
, 2, cur
);
122 next
= mono_lls_pointer_unmask (next
);
123 if (InterlockedCompareExchangePointer ((volatile gpointer
*)prev
, next
, cur
) == cur
) {
124 /* The hazard pointer must be cleared after the CAS. */
125 mono_memory_write_barrier ();
126 mono_hazard_pointer_clear (hp
, 1);
127 if (list
->free_node_func
)
128 mono_thread_hazardous_free_or_queue (cur
, list
->free_node_func
);
132 cur
= mono_lls_pointer_unmask (next
);
133 mono_hazard_pointer_set (hp
, 1, cur
);
138 Insert @value into @list.
139 The nodes value, cur and prev are returned in @hp.
140 Return true if @value was inserted by this call. If it returns FALSE, it's the caller
141 resposibility to release memory.
142 This function cannot be called from a signal nor with the world stopped.
145 mono_lls_insert (MonoLinkedListSet
*list
, MonoThreadHazardPointers
*hp
, MonoLinkedListSetNode
*value
)
147 MonoLinkedListSetNode
*cur
, **prev
;
148 /*We must do a store barrier before inserting
149 to make sure all values in @node are globally visible.*/
150 mono_memory_barrier ();
153 if (mono_lls_find (list
, hp
, value
->key
))
155 cur
= mono_hazard_pointer_get_val (hp
, 1);
156 prev
= mono_hazard_pointer_get_val (hp
, 2);
159 mono_hazard_pointer_set (hp
, 0, value
);
160 /* The CAS must happen after setting the hazard pointer. */
161 mono_memory_write_barrier ();
162 if (InterlockedCompareExchangePointer ((volatile gpointer
*)prev
, value
, cur
) == cur
)
168 Search @list for element with key @key.
169 The nodes next, cur and prev are returned in @hp
170 Returns true if @value was removed by this call.
171 This function cannot be called from a signal nor with the world stopped.
174 mono_lls_remove (MonoLinkedListSet
*list
, MonoThreadHazardPointers
*hp
, MonoLinkedListSetNode
*value
)
176 MonoLinkedListSetNode
*cur
, **prev
, *next
;
178 if (!mono_lls_find (list
, hp
, value
->key
))
181 next
= mono_hazard_pointer_get_val (hp
, 0);
182 cur
= mono_hazard_pointer_get_val (hp
, 1);
183 prev
= mono_hazard_pointer_get_val (hp
, 2);
185 g_assert (cur
== value
);
187 if (InterlockedCompareExchangePointer ((volatile gpointer
*)&cur
->next
, mask (next
, 1), next
) != next
)
189 /* The second CAS must happen before the first. */
190 mono_memory_write_barrier ();
191 if (InterlockedCompareExchangePointer ((volatile gpointer
*)prev
, next
, cur
) == cur
) {
192 /* The CAS must happen before the hazard pointer clear. */
193 mono_memory_write_barrier ();
194 mono_hazard_pointer_clear (hp
, 1);
195 if (list
->free_node_func
)
196 mono_thread_hazardous_free_or_queue (value
, list
->free_node_func
);
198 mono_lls_find (list
, hp
, value
->key
);