mono/utils/mono-linked-list-set.h

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