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
11 #ifndef __MONO_SPLIT_ORDERED_LIST_H__
12 #define __MONO_SPLIT_ORDERED_LIST_H__
13
14 #include <mono/utils/hazard-pointer.h>
15 #include <mono/utils/mono-membar.h>
16
17 typedef struct _MonoLinkedListSetNode MonoLinkedListSetNode;
18
19 struct _MonoLinkedListSetNode {
20 /* next must be the first element in this struct! */
21 MonoLinkedListSetNode *next;
22 uintptr_t key;
23 };
24
25 typedef struct {
26 MonoLinkedListSetNode *head;
27 void (*free_node_func)(void *);
28 } MonoLinkedListSet;
29
30
31 static inline gpointer
mono_lls_pointer_unmask(gpointer p)32 mono_lls_pointer_unmask (gpointer p)
33 {
34 return (gpointer)((uintptr_t)p & ~(uintptr_t)0x3);
35 }
36
37 static inline uintptr_t
mono_lls_pointer_get_mark(gpointer n)38 mono_lls_pointer_get_mark (gpointer n)
39 {
40 return (uintptr_t)n & 0x1;
41 }
42
43 /*
44 Those are low level operations. prev, cur, next are returned in the hazard pointer table.
45 You must manually clean the hazard pointer table after using them.
46 */
47
48 MONO_API void
49 mono_lls_init (MonoLinkedListSet *list, void (*free_node_func)(void *));
50
51 MONO_API gboolean
52 mono_lls_find (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, uintptr_t key);
53
54 MONO_API gboolean
55 mono_lls_insert (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value);
56
57 MONO_API gboolean
58 mono_lls_remove (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value);
59
60 MONO_API gpointer
61 mono_lls_get_hazardous_pointer_with_mask (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index);
62
63 static inline gboolean
mono_lls_filter_accept_all(gpointer elem)64 mono_lls_filter_accept_all (gpointer elem)
65 {
66 return TRUE;
67 }
68
69 /*
70 * These macros assume that no other threads are actively modifying the list.
71 */
72
73 #define MONO_LLS_FOREACH_FILTERED(list, type, elem, filter) \
74 do { \
75 MonoLinkedListSet *list__ = (list); \
76 for (MonoLinkedListSetNode *cur__ = list__->head; cur__; cur__ = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (cur__->next)) { \
77 if (!mono_lls_pointer_get_mark (cur__->next)) { \
78 type *elem = (type *) cur__; \
79 if (filter (elem)) {
80
81 #define MONO_LLS_FOREACH_END \
82 } \
83 } \
84 } \
85 } while (0);
86
87 #define MONO_LLS_FOREACH(list, type, elem) \
88 MONO_LLS_FOREACH_FILTERED ((list), type, elem, mono_lls_filter_accept_all)
89
90 /*
91 * These macros can be used while other threads are potentially modifying the
92 * list, but they only provide a snapshot of the list as a result.
93 *
94 * NOTE: Do NOT break out of the loop through any other means than a break
95 * statement, as other ways of breaking the loop will skip past important
96 * cleanup work.
97 */
98
99 #define MONO_LLS_FOREACH_FILTERED_SAFE(list, type, elem, filter) \
100 do { \
101 /* NOTE: Keep this macro's code in sync with the mono_lls_find () logic. */ \
102 MonoLinkedListSet *list__ = (list); \
103 MonoThreadHazardPointers *hp__ = mono_hazard_pointer_get (); \
104 gboolean progress__ = FALSE; \
105 uintptr_t hkey__; \
106 gboolean restart__; \
107 do { \
108 restart__ = FALSE; \
109 MonoLinkedListSetNode **prev__ = &list__->head; \
110 mono_hazard_pointer_set (hp__, 2, prev__); \
111 MonoLinkedListSetNode *cur__ = (MonoLinkedListSetNode *) mono_lls_get_hazardous_pointer_with_mask ((gpointer *) prev__, hp__, 1); \
112 while (1) { \
113 if (!cur__) { \
114 break; \
115 } \
116 MonoLinkedListSetNode *next__ = (MonoLinkedListSetNode *) mono_lls_get_hazardous_pointer_with_mask ((gpointer *) &cur__->next, hp__, 0); \
117 uintptr_t ckey__ = cur__->key; \
118 mono_memory_read_barrier (); \
119 if (*prev__ != cur__) { \
120 restart__ = TRUE; \
121 break; \
122 } \
123 if (!mono_lls_pointer_get_mark (next__)) { \
124 if (!progress__ || ckey__ > hkey__) { \
125 progress__ = TRUE; \
126 hkey__ = ckey__; \
127 type *elem = (type *) cur__; \
128 if (filter (elem)) { \
129 gboolean broke__ = TRUE; \
130 gboolean done__ = FALSE; \
131 do { \
132 if (done__) { \
133 broke__ = FALSE; \
134 break; \
135 } \
136 done__ = TRUE;
137
138 #define MONO_LLS_FOREACH_SAFE_END \
139 broke__ = FALSE; \
140 break; \
141 } while (1); \
142 if (broke__) { \
143 break; \
144 } \
145 } \
146 } \
147 prev__ = &cur__->next; \
148 mono_hazard_pointer_set (hp__, 2, cur__); \
149 } else { \
150 next__ = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (next__); \
151 if (mono_atomic_cas_ptr ((volatile gpointer *) prev__, next__, cur__) == cur__) { \
152 mono_memory_write_barrier (); \
153 mono_hazard_pointer_clear (hp__, 1); \
154 if (list__->free_node_func) { \
155 mono_thread_hazardous_queue_free (cur__, list__->free_node_func); \
156 } \
157 } else { \
158 restart__ = TRUE; \
159 break; \
160 } \
161 } \
162 cur__ = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (next__); \
163 mono_hazard_pointer_set (hp__, 1, cur__); \
164 } \
165 } while (restart__); \
166 mono_hazard_pointer_clear (hp__, 0); \
167 mono_hazard_pointer_clear (hp__, 1); \
168 mono_hazard_pointer_clear (hp__, 2); \
169 } while (0);
170
171 #define MONO_LLS_FOREACH_SAFE(list, type, elem) \
172 MONO_LLS_FOREACH_FILTERED_SAFE ((list), type, elem, mono_lls_filter_accept_all)
173
174 #endif /* __MONO_SPLIT_ORDERED_LIST_H__ */
175