1 /**
2 * \file
3 * A lock-free split ordered list.
4 *
5 * Author:
6 * Rodrigo Kumpera (kumpera@gmail.com)
7 *
8 * (C) 2011 Novell, Inc
9 *
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
14 *
15 * http://www.research.ibm.com/people/m/michael/spaa-2002.pdf
16 */
17
18 #include <mono/utils/mono-linked-list-set.h>
19
20 #include <mono/utils/atomic.h>
21
22 static inline gpointer
mask(gpointer n,uintptr_t bit)23 mask (gpointer n, uintptr_t bit)
24 {
25 return (gpointer)(((uintptr_t)n) | bit);
26 }
27
28 gpointer
mono_lls_get_hazardous_pointer_with_mask(gpointer volatile * pp,MonoThreadHazardPointers * hp,int hazard_index)29 mono_lls_get_hazardous_pointer_with_mask (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index)
30 {
31 gpointer p;
32
33 for (;;) {
34 /* Get the pointer */
35 p = *pp;
36 /* If we don't have hazard pointers just return the
37 pointer. */
38 if (!hp)
39 return p;
40 /* Make it hazardous */
41 mono_hazard_pointer_set (hp, hazard_index, mono_lls_pointer_unmask (p));
42
43 mono_memory_barrier ();
44
45 /* Check that it's still the same. If not, try
46 again. */
47 if (*pp != p) {
48 mono_hazard_pointer_clear (hp, hazard_index);
49 continue;
50 }
51 break;
52 }
53
54 return p;
55 }
56
57 /*
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.
60 */
61 void
mono_lls_init(MonoLinkedListSet * list,void (* free_node_func)(void *))62 mono_lls_init (MonoLinkedListSet *list, void (*free_node_func)(void *))
63 {
64 list->head = NULL;
65 list->free_node_func = free_node_func;
66 }
67
68 /*
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 */
73 gboolean
mono_lls_find(MonoLinkedListSet * list,MonoThreadHazardPointers * hp,uintptr_t key)74 mono_lls_find (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, uintptr_t key)
75 {
76 MonoLinkedListSetNode *cur, *next;
77 MonoLinkedListSetNode **prev;
78 uintptr_t cur_key;
79
80 try_again:
81 prev = &list->head;
82
83 /*
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.
89 */
90 mono_hazard_pointer_set (hp, 2, prev);
91
92 cur = (MonoLinkedListSetNode *) mono_lls_get_hazardous_pointer_with_mask ((gpointer*)prev, hp, 1);
93
94 while (1) {
95 if (cur == NULL)
96 return FALSE;
97 next = (MonoLinkedListSetNode *) mono_lls_get_hazardous_pointer_with_mask ((gpointer*)&cur->next, hp, 0);
98 cur_key = cur->key;
99
100 /*
101 * We need to make sure that we dereference prev below
102 * after reading cur->next above, so we need a read
103 * barrier.
104 */
105 mono_memory_read_barrier ();
106
107 if (*prev != cur)
108 goto try_again;
109
110 if (!mono_lls_pointer_get_mark (next)) {
111 if (cur_key >= key)
112 return cur_key == key;
113
114 prev = &cur->next;
115 mono_hazard_pointer_set (hp, 2, cur);
116 } else {
117 next = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (next);
118 if (mono_atomic_cas_ptr ((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);
124 } else
125 goto try_again;
126 }
127 cur = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (next);
128 mono_hazard_pointer_set (hp, 1, cur);
129 }
130 }
131
132 /*
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.
137 */
138 gboolean
mono_lls_insert(MonoLinkedListSet * list,MonoThreadHazardPointers * hp,MonoLinkedListSetNode * value)139 mono_lls_insert (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value)
140 {
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 ();
145
146 while (1) {
147 if (mono_lls_find (list, hp, value->key))
148 return FALSE;
149 cur = (MonoLinkedListSetNode *) mono_hazard_pointer_get_val (hp, 1);
150 prev = (MonoLinkedListSetNode **) mono_hazard_pointer_get_val (hp, 2);
151
152 value->next = cur;
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 (mono_atomic_cas_ptr ((volatile gpointer*)prev, value, cur) == cur)
157 return TRUE;
158 }
159 }
160
161 /*
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.
165 */
166 gboolean
mono_lls_remove(MonoLinkedListSet * list,MonoThreadHazardPointers * hp,MonoLinkedListSetNode * value)167 mono_lls_remove (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value)
168 {
169 MonoLinkedListSetNode *cur, **prev, *next;
170 while (1) {
171 if (!mono_lls_find (list, hp, value->key))
172 return FALSE;
173
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);
177
178 g_assert (cur == value);
179
180 if (mono_atomic_cas_ptr ((volatile gpointer*)&cur->next, mask (next, 1), next) != next)
181 continue;
182 /* The second CAS must happen before the first. */
183 mono_memory_write_barrier ();
184 if (mono_atomic_cas_ptr ((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);
190 } else
191 mono_lls_find (list, hp, value->key);
192 return TRUE;
193 }
194 }
195