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         HazardFreeLocking locking;
  28 } MonoLinkedListSet;
  29
  30
  31 static inline gpointer
  32 mono_lls_pointer_unmask (gpointer p)
  33 {
  34         return (gpointer)((uintptr_t)p & ~(uintptr_t)0x3);
  35 }
  36
  37 static inline uintptr_t
  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 void
  49 mono_lls_init (MonoLinkedListSet *list, void (*free_node_func)(void *), HazardFreeLocking free_node_func_locking);
  50
  51 gboolean
  52 mono_lls_find (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, uintptr_t key, HazardFreeContext context);
  53
  54 gboolean
  55 mono_lls_insert (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value, HazardFreeContext context);
  56
  57 gboolean
  58 mono_lls_remove (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value, HazardFreeContext context);
  59
  60 gpointer
  61 get_hazardous_pointer_with_mask (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index);
  62
  63 static inline gboolean
  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 *) get_hazardous_pointer_with_mask ((gpointer *) prev__, hp__, 1); \
 112                         while (1) { \
 113                                 if (!cur__) { \
 114                                         break; \
 115                                 } \
 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__) { \
 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 (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_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__ */