3 * A lock-free split ordered list.
6 * Rodrigo Kumpera (kumpera@gmail.com)
10 * This is an implementation of Maged Michael's lock-free linked-list set.
11 * For more details see:
12 * "High Performance Dynamic Lock-Free Hash Tables and List-Based Sets"
13 * Maged M. Michael 2002
15 * http://www.research.ibm.com/people/m/michael/spaa-2002.pdf
18 #include <mono/utils/mono-linked-list-set.h>
20 #include <mono/utils/atomic.h>
22 static inline gpointer
23 mask (gpointer n
, uintptr_t bit
)
25 return (gpointer
)(((uintptr_t)n
) | bit
);
29 mono_lls_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.
74 mono_lls_find (MonoLinkedListSet
*list
, MonoThreadHazardPointers
*hp
, uintptr_t key
)
76 MonoLinkedListSetNode
*cur
, *next
;
77 MonoLinkedListSetNode
**prev
;
84 * prev is not really a hazardous pointer, but we return prev
85 * in hazard pointer 2, so we set it here. Note also that
86 * prev is not a pointer to a node. We use here the fact that
87 * the first element in a node is the next pointer, so it
88 * works, but it's not pretty.
90 mono_hazard_pointer_set (hp
, 2, prev
);
92 cur
= (MonoLinkedListSetNode
*) mono_lls_get_hazardous_pointer_with_mask ((gpointer
*)prev
, hp
, 1);
97 next
= (MonoLinkedListSetNode
*) mono_lls_get_hazardous_pointer_with_mask ((gpointer
*)&cur
->next
, hp
, 0);
101 * We need to make sure that we dereference prev below
102 * after reading cur->next above, so we need a read
105 mono_memory_read_barrier ();
110 if (!mono_lls_pointer_get_mark (next
)) {
112 return cur_key
== key
;
115 mono_hazard_pointer_set (hp
, 2, cur
);
117 next
= (MonoLinkedListSetNode
*) mono_lls_pointer_unmask (next
);
118 if (InterlockedCompareExchangePointer ((volatile gpointer
*)prev
, next
, cur
) == cur
) {
119 /* The hazard pointer must be cleared after the CAS. */
120 mono_memory_write_barrier ();
121 mono_hazard_pointer_clear (hp
, 1);
122 if (list
->free_node_func
)
123 mono_thread_hazardous_queue_free (cur
, list
->free_node_func
);
127 cur
= (MonoLinkedListSetNode
*) mono_lls_pointer_unmask (next
);
128 mono_hazard_pointer_set (hp
, 1, cur
);
133 Insert @value into @list.
134 The nodes value, cur and prev are returned in @hp.
135 Return true if @value was inserted by this call. If it returns FALSE, it's the caller
136 resposibility to release memory.
139 mono_lls_insert (MonoLinkedListSet
*list
, MonoThreadHazardPointers
*hp
, MonoLinkedListSetNode
*value
)
141 MonoLinkedListSetNode
*cur
, **prev
;
142 /*We must do a store barrier before inserting
143 to make sure all values in @node are globally visible.*/
144 mono_memory_barrier ();
147 if (mono_lls_find (list
, hp
, value
->key
))
149 cur
= (MonoLinkedListSetNode
*) mono_hazard_pointer_get_val (hp
, 1);
150 prev
= (MonoLinkedListSetNode
**) mono_hazard_pointer_get_val (hp
, 2);
153 mono_hazard_pointer_set (hp
, 0, value
);
154 /* The CAS must happen after setting the hazard pointer. */
155 mono_memory_write_barrier ();
156 if (InterlockedCompareExchangePointer ((volatile gpointer
*)prev
, value
, cur
) == cur
)
162 Search @list for element with key @key and remove it.
163 The nodes next, cur and prev are returned in @hp
164 Returns true if @value was removed by this call.
167 mono_lls_remove (MonoLinkedListSet
*list
, MonoThreadHazardPointers
*hp
, MonoLinkedListSetNode
*value
)
169 MonoLinkedListSetNode
*cur
, **prev
, *next
;
171 if (!mono_lls_find (list
, hp
, value
->key
))
174 next
= (MonoLinkedListSetNode
*) mono_hazard_pointer_get_val (hp
, 0);
175 cur
= (MonoLinkedListSetNode
*) mono_hazard_pointer_get_val (hp
, 1);
176 prev
= (MonoLinkedListSetNode
**) mono_hazard_pointer_get_val (hp
, 2);
178 g_assert (cur
== value
);
180 if (InterlockedCompareExchangePointer ((volatile gpointer
*)&cur
->next
, mask (next
, 1), next
) != next
)
182 /* The second CAS must happen before the first. */
183 mono_memory_write_barrier ();
184 if (InterlockedCompareExchangePointer ((volatile gpointer
*)prev
, mono_lls_pointer_unmask (next
), cur
) == cur
) {
185 /* The CAS must happen before the hazard pointer clear. */
186 mono_memory_write_barrier ();
187 mono_hazard_pointer_clear (hp
, 1);
188 if (list
->free_node_func
)
189 mono_thread_hazardous_queue_free (value
, list
->free_node_func
);
191 mono_lls_find (list
, hp
, value
->key
);