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 mono_lls_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 */
  60 void
  61 mono_lls_init (MonoLinkedListSet *list, void (*free_node_func)(void *))
  62 {
  63         list->head = NULL;
  64         list->free_node_func = free_node_func;
  65 }
  66
  67 /*
  68 Search @list for element with key @key.
  69 The nodes next, cur and prev are returned in @hp.
  70 Returns true if a node with key @key was found.
  71 */
  72 gboolean
  73 mono_lls_find (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, uintptr_t key)
  74 {
  75         MonoLinkedListSetNode *cur, *next;
  76         MonoLinkedListSetNode **prev;
  77         uintptr_t cur_key;
  78
  79 try_again:
  80         prev = &list->head;
  81
  82         /*
  83          * prev is not really a hazardous pointer, but we return prev
  84          * in hazard pointer 2, so we set it here.  Note also that
  85          * prev is not a pointer to a node.  We use here the fact that
  86          * the first element in a node is the next pointer, so it
  87          * works, but it's not pretty.
  88          */
  89         mono_hazard_pointer_set (hp, 2, prev);
  90
  91         cur = (MonoLinkedListSetNode *) mono_lls_get_hazardous_pointer_with_mask ((gpointer*)prev, hp, 1);
  92
  93         while (1) {
  94                 if (cur == NULL)
  95                         return FALSE;
  96                 next = (MonoLinkedListSetNode *) mono_lls_get_hazardous_pointer_with_mask ((gpointer*)&cur->next, hp, 0);
  97                 cur_key = cur->key;
  98
  99                 /*
 100                  * We need to make sure that we dereference prev below
 101                  * after reading cur->next above, so we need a read
 102                  * barrier.
 103                  */
 104                 mono_memory_read_barrier ();
 105
 106                 if (*prev != cur)
 107                         goto try_again;
 108
 109                 if (!mono_lls_pointer_get_mark (next)) {
 110                         if (cur_key >= key)
 111                                 return cur_key == key;
 112
 113                         prev = &cur->next;
 114                         mono_hazard_pointer_set (hp, 2, cur);
 115                 } else {
 116                         next = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (next);
 117                         if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, next, cur) == cur) {
 118                                 /* The hazard pointer must be cleared after the CAS. */
 119                                 mono_memory_write_barrier ();
 120                                 mono_hazard_pointer_clear (hp, 1);
 121                                 if (list->free_node_func)
 122                                         mono_thread_hazardous_queue_free (cur, list->free_node_func);
 123                         } else
 124                                 goto try_again;
 125                 }
 126                 cur = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (next);
 127                 mono_hazard_pointer_set (hp, 1, cur);
 128         }
 129 }
 130
 131 /*
 132 Insert @value into @list.
 133 The nodes value, cur and prev are returned in @hp.
 134 Return true if @value was inserted by this call. If it returns FALSE, it's the caller
 135 resposibility to release memory.
 136 */
 137 gboolean
 138 mono_lls_insert (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value)
 139 {
 140         MonoLinkedListSetNode *cur, **prev;
 141         /*We must do a store barrier before inserting
 142         to make sure all values in @node are globally visible.*/
 143         mono_memory_barrier ();
 144
 145         while (1) {
 146                 if (mono_lls_find (list, hp, value->key))
 147                         return FALSE;
 148                 cur = (MonoLinkedListSetNode *) mono_hazard_pointer_get_val (hp, 1);
 149                 prev = (MonoLinkedListSetNode **) mono_hazard_pointer_get_val (hp, 2);
 150
 151                 value->next = cur;
 152                 mono_hazard_pointer_set (hp, 0, value);
 153                 /* The CAS must happen after setting the hazard pointer. */
 154                 mono_memory_write_barrier ();
 155                 if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, value, cur) == cur)
 156                         return TRUE;
 157         }
 158 }
 159
 160 /*
 161 Search @list for element with key @key and remove it.
 162 The nodes next, cur and prev are returned in @hp
 163 Returns true if @value was removed by this call.
 164 */
 165 gboolean
 166 mono_lls_remove (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value)
 167 {
 168         MonoLinkedListSetNode *cur, **prev, *next;
 169         while (1) {
 170                 if (!mono_lls_find (list, hp, value->key))
 171                         return FALSE;
 172
 173                 next = (MonoLinkedListSetNode *) mono_hazard_pointer_get_val (hp, 0);
 174                 cur = (MonoLinkedListSetNode *) mono_hazard_pointer_get_val (hp, 1);
 175                 prev = (MonoLinkedListSetNode **) mono_hazard_pointer_get_val (hp, 2);
 176
 177                 g_assert (cur == value);
 178
 179                 if (InterlockedCompareExchangePointer ((volatile gpointer*)&cur->next, mask (next, 1), next) != next)
 180                         continue;
 181                 /* The second CAS must happen before the first. */
 182                 mono_memory_write_barrier ();
 183                 if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, mono_lls_pointer_unmask (next), cur) == cur) {
 184                         /* The CAS must happen before the hazard pointer clear. */
 185                         mono_memory_write_barrier ();
 186                         mono_hazard_pointer_clear (hp, 1);
 187                         if (list->free_node_func)
 188                                 mono_thread_hazardous_queue_free (value, list->free_node_func);
 189                 } else
 190                         mono_lls_find (list, hp, value->key);
 191                 return TRUE;
 192         }
 193 }