3 * A lock-free split ordered list.
6 * Rodrigo Kumpera (kumpera@gmail.com)
11 #ifndef __MONO_SPLIT_ORDERED_LIST_H__
12 #define __MONO_SPLIT_ORDERED_LIST_H__
14 #include <mono/utils/hazard-pointer.h>
15 #include <mono/utils/mono-membar.h>
17 typedef struct _MonoLinkedListSetNode MonoLinkedListSetNode
;
19 struct _MonoLinkedListSetNode
{
20 /* next must be the first element in this struct! */
21 MonoLinkedListSetNode
*next
;
26 MonoLinkedListSetNode
*head
;
27 void (*free_node_func
)(void *);
31 static inline gpointer
32 mono_lls_pointer_unmask (gpointer p
)
34 return (gpointer
)((uintptr_t)p
& ~(uintptr_t)0x3);
37 static inline uintptr_t
38 mono_lls_pointer_get_mark (gpointer n
)
40 return (uintptr_t)n
& 0x1;
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.
49 mono_lls_init (MonoLinkedListSet
*list
, void (*free_node_func
)(void *));
52 mono_lls_find (MonoLinkedListSet
*list
, MonoThreadHazardPointers
*hp
, uintptr_t key
);
55 mono_lls_insert (MonoLinkedListSet
*list
, MonoThreadHazardPointers
*hp
, MonoLinkedListSetNode
*value
);
58 mono_lls_remove (MonoLinkedListSet
*list
, MonoThreadHazardPointers
*hp
, MonoLinkedListSetNode
*value
);
61 mono_lls_get_hazardous_pointer_with_mask (gpointer
volatile *pp
, MonoThreadHazardPointers
*hp
, int hazard_index
);
63 static inline gboolean
64 mono_lls_filter_accept_all (gpointer elem
, gpointer dummy
)
70 * These macros assume that no other threads are actively modifying the list.
73 #define MONO_LLS_FOREACH_FILTERED(list, type, elem, filter, ...) \
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, __VA_ARGS__)) {
81 #define MONO_LLS_FOREACH_END \
87 #define MONO_LLS_FOREACH(list, type, elem) \
88 MONO_LLS_FOREACH_FILTERED ((list), type, elem, mono_lls_filter_accept_all, NULL)
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.
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 (return, goto, etc) will skip
96 * past important cleanup work.
99 #define MONO_LLS_FOREACH_FILTERED_SAFE(list, type, elem, filter, ...) \
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__ = 0; \
106 gboolean 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); \
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__) { \
123 if (!mono_lls_pointer_get_mark (next__)) { \
124 if (!progress__ || ckey__ > hkey__) { \
127 type *elem = (type *) cur__; \
128 if (filter (elem, __VA_ARGS__)) { \
129 gboolean broke__ = TRUE; \
130 gboolean done__ = FALSE; \
138 #define MONO_LLS_FOREACH_SAFE_END \
147 prev__ = &cur__->next; \
148 mono_hazard_pointer_set (hp__, 2, cur__); \
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); \
162 cur__ = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (next__); \
163 mono_hazard_pointer_set (hp__, 1, cur__); \
165 } while (restart__); \
166 mono_hazard_pointer_clear (hp__, 0); \
167 mono_hazard_pointer_clear (hp__, 1); \
168 mono_hazard_pointer_clear (hp__, 2); \
171 #define MONO_LLS_FOREACH_SAFE(list, type, elem) \
172 MONO_LLS_FOREACH_FILTERED_SAFE ((list), type, elem, mono_lls_filter_accept_all, NULL)
174 #endif /* __MONO_SPLIT_ORDERED_LIST_H__ */