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

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