2 * mono-linked-list-set.h: A lock-free split ordered list.
5 * Rodrigo Kumpera (kumpera@gmail.com)
10 #ifndef __MONO_SPLIT_ORDERED_LIST_H__
11 #define __MONO_SPLIT_ORDERED_LIST_H__
13 #include <mono/utils/hazard-pointer.h>
14 #include <mono/utils/mono-membar.h>
16 typedef struct _MonoLinkedListSetNode MonoLinkedListSetNode;
18 struct _MonoLinkedListSetNode {
19 /* next must be the first element in this struct! */
20 MonoLinkedListSetNode *next;
25 MonoLinkedListSetNode *head;
26 void (*free_node_func)(void *);
27 HazardFreeLocking locking;
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 *), HazardFreeLocking free_node_func_locking);
52 mono_lls_find (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, uintptr_t key, HazardFreeContext context);
55 mono_lls_insert (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value, HazardFreeContext context);
58 mono_lls_remove (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value, HazardFreeContext context);
61 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)
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__; \
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)
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 will skip past important
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; \
106 gboolean restart__; \
109 MonoLinkedListSetNode **prev__ = &list__->head; \
110 mono_hazard_pointer_set (hp__, 2, prev__); \
111 MonoLinkedListSetNode *cur__ = (MonoLinkedListSetNode *) get_hazardous_pointer_with_mask ((gpointer *) prev__, hp__, 1); \
116 MonoLinkedListSetNode *next__ = (MonoLinkedListSetNode *) 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)) { \
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 (InterlockedCompareExchangePointer ((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_free_or_queue (cur__, list__->free_node_func, list__->locking, HAZARD_FREE_ASYNC_CTX); \
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)
174 #endif /* __MONO_SPLIT_ORDERED_LIST_H__ */