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

   1 /*
   2  * mono-split-ordered-list.c: A lock-free split ordered list.
   3  *
   4  * Author:
   5  *      Rodrigo Kumpera (kumpera@gmail.com)
   6  *
   7  * (C) 2011 Novell, Inc
   8  *
   9  * This is an implementation of Maged Michael's lock-free linked-list set.
  10  * For more details see:
  11  *      "High Performance Dynamic Lock-Free Hash Tables and List-Based Sets"
  12  *  Maged M. Michael 2002
  13  *
  14  *  http://www.research.ibm.com/people/m/michael/spaa-2002.pdf
  15  */
  16
  17 #include <mono/utils/mono-linked-list-set.h>
  18
  19 #include <mono/utils/atomic.h>
  20
  21 static inline gpointer
  22 mask (gpointer n, uintptr_t bit)
  23 {
  24         return (gpointer)(((uintptr_t)n) | bit);
  25 }
  26
  27 gpointer
  28 get_hazardous_pointer_with_mask (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index)
  29 {
  30         gpointer p;
  31
  32         for (;;) {
  33                 /* Get the pointer */
  34                 p = *pp;
  35                 /* If we don't have hazard pointers just return the
  36                    pointer. */
  37                 if (!hp)
  38                         return p;
  39                 /* Make it hazardous */
  40                 mono_hazard_pointer_set (hp, hazard_index, mono_lls_pointer_unmask (p));
  41
  42                 mono_memory_barrier ();
  43
  44                 /* Check that it's still the same.  If not, try
  45                    again. */
  46                 if (*pp != p) {
  47                         mono_hazard_pointer_clear (hp, hazard_index);
  48                         continue;
  49                 }
  50                 break;
  51         }
  52
  53         return p;
  54 }
  55
  56 /*
  57 Initialize @list and will use @free_node_func to release memory.
  58 If @free_node_func is null the caller is responsible for releasing node memory.
  59 If @free_node_func may lock, @free_node_func_locking must be
  60 HAZARD_FREE_MAY_LOCK; otherwise, HAZARD_FREE_NO_LOCK. It is ignored if
  61 @free_node_func is null.
  62 */
  63 void
  64 mono_lls_init (MonoLinkedListSet *list, void (*free_node_func)(void *), HazardFreeLocking free_node_func_locking)
  65 {
  66         list->head = NULL;
  67         list->free_node_func = free_node_func;
  68         list->locking = free_node_func_locking;
  69 }
  70
  71 /*
  72 Search @list for element with key @key.
  73 @context specifies whether the function is being called from a lock-free (i.e.
  74 signal handler or world stopped) context. It is only relevant if a node free
  75 function was given.
  76 The nodes next, cur and prev are returned in @hp.
  77 Returns true if a node with key @key was found.
  78 */
  79 gboolean
  80 mono_lls_find (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, uintptr_t key, HazardFreeContext context)
  81 {
  82         MonoLinkedListSetNode *cur, *next;
  83         MonoLinkedListSetNode **prev;
  84         uintptr_t cur_key;
  85
  86 try_again:
  87         prev = &list->head;
  88
  89         /*
  90          * prev is not really a hazardous pointer, but we return prev
  91          * in hazard pointer 2, so we set it here.  Note also that
  92          * prev is not a pointer to a node.  We use here the fact that
  93          * the first element in a node is the next pointer, so it
  94          * works, but it's not pretty.
  95          */
  96         mono_hazard_pointer_set (hp, 2, prev);
  97
  98         cur = (MonoLinkedListSetNode *) get_hazardous_pointer_with_mask ((gpointer*)prev, hp, 1);
  99
 100         while (1) {
 101                 if (cur == NULL)
 102                         return FALSE;
 103                 next = (MonoLinkedListSetNode *) get_hazardous_pointer_with_mask ((gpointer*)&cur->next, hp, 0);
 104                 cur_key = cur->key;
 105
 106                 /*
 107                  * We need to make sure that we dereference prev below
 108                  * after reading cur->next above, so we need a read
 109                  * barrier.
 110                  */
 111                 mono_memory_read_barrier ();
 112
 113                 if (*prev != cur)
 114                         goto try_again;
 115
 116                 if (!mono_lls_pointer_get_mark (next)) {
 117                         if (cur_key >= key)
 118                                 return cur_key == key;
 119
 120                         prev = &cur->next;
 121                         mono_hazard_pointer_set (hp, 2, cur);
 122                 } else {
 123                         next = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (next);
 124                         if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, next, cur) == cur) {
 125                                 /* The hazard pointer must be cleared after the CAS. */
 126                                 mono_memory_write_barrier ();
 127                                 mono_hazard_pointer_clear (hp, 1);
 128                                 if (list->free_node_func)
 129                                         mono_thread_hazardous_queue_free (cur, list->free_node_func);
 130                         } else
 131                                 goto try_again;
 132                 }
 133                 cur = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (next);
 134                 mono_hazard_pointer_set (hp, 1, cur);
 135         }
 136 }
 137
 138 /*
 139 Insert @value into @list.
 140 @context specifies whether the function is being called from a lock-free (i.e.
 141 signal handler or world stopped) context. It is only relevant if a node free
 142 function was given.
 143 The nodes value, cur and prev are returned in @hp.
 144 Return true if @value was inserted by this call. If it returns FALSE, it's the caller
 145 resposibility to release memory.
 146 */
 147 gboolean
 148 mono_lls_insert (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value, HazardFreeContext context)
 149 {
 150         MonoLinkedListSetNode *cur, **prev;
 151         /*We must do a store barrier before inserting
 152         to make sure all values in @node are globally visible.*/
 153         mono_memory_barrier ();
 154
 155         while (1) {
 156                 if (mono_lls_find (list, hp, value->key, context))
 157                         return FALSE;
 158                 cur = (MonoLinkedListSetNode *) mono_hazard_pointer_get_val (hp, 1);
 159                 prev = (MonoLinkedListSetNode **) mono_hazard_pointer_get_val (hp, 2);
 160
 161                 value->next = cur;
 162                 mono_hazard_pointer_set (hp, 0, value);
 163                 /* The CAS must happen after setting the hazard pointer. */
 164                 mono_memory_write_barrier ();
 165                 if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, value, cur) == cur)
 166                         return TRUE;
 167         }
 168 }
 169
 170 /*
 171 Search @list for element with key @key and remove it.
 172 @context specifies whether the function is being called from a lock-free (i.e.
 173 signal handler or world stopped) context. It is only relevant if a node free
 174 function was given.
 175 The nodes next, cur and prev are returned in @hp
 176 Returns true if @value was removed by this call.
 177 */
 178 gboolean
 179 mono_lls_remove (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value, HazardFreeContext context)
 180 {
 181         MonoLinkedListSetNode *cur, **prev, *next;
 182         while (1) {
 183                 if (!mono_lls_find (list, hp, value->key, context))
 184                         return FALSE;
 185
 186                 next = (MonoLinkedListSetNode *) mono_hazard_pointer_get_val (hp, 0);
 187                 cur = (MonoLinkedListSetNode *) mono_hazard_pointer_get_val (hp, 1);
 188                 prev = (MonoLinkedListSetNode **) mono_hazard_pointer_get_val (hp, 2);
 189
 190                 g_assert (cur == value);
 191
 192                 if (InterlockedCompareExchangePointer ((volatile gpointer*)&cur->next, mask (next, 1), next) != next)
 193                         continue;
 194                 /* The second CAS must happen before the first. */
 195                 mono_memory_write_barrier ();
 196                 if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, mono_lls_pointer_unmask (next), cur) == cur) {
 197                         /* The CAS must happen before the hazard pointer clear. */
 198                         mono_memory_write_barrier ();
 199                         mono_hazard_pointer_clear (hp, 1);
 200                         if (list->free_node_func)
 201                                 mono_thread_hazardous_try_free (value, list->free_node_func);
 202                 } else
 203                         mono_lls_find (list, hp, value->key, context);
 204                 return TRUE;
 205         }
 206 }