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 /*atomics.*/
  20 #include <mono/io-layer/io-layer.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 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 @free_node_func must be lock-free.  That implies that it cannot use malloc/free.
  61 */
  62 void
  63 mono_lls_init (MonoLinkedListSet *list, void (*free_node_func)(void *))
  64 {
  65         list->head = NULL;
  66         list->free_node_func = free_node_func;
  67 }
  68
  69 /*
  70 Search @list for element with key @key.
  71 The nodes next, cur and prev are returned in @hp.
  72 Returns true if a node with key @key was found.
  73 This function cannot be called from a signal nor within interrupt context*.
  74 XXX A variant that works within interrupted is possible if needed.
  75
  76 * interrupt context is when the current thread is reposible for another thread
  77 been suspended at an arbritary point. This is a limitation of our SMR implementation.
  78 */
  79 gboolean
  80 mono_lls_find (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, uintptr_t key)
  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 = get_hazardous_pointer_with_mask ((gpointer*)prev, hp, 1);
  99
 100         while (1) {
 101                 if (cur == NULL)
 102                         return FALSE;
 103                 next = 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 = 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_free_or_queue (cur, list->free_node_func, FALSE, TRUE);
 130                         } else
 131                                 goto try_again;
 132                 }
 133                 cur = mono_lls_pointer_unmask (next);
 134                 mono_hazard_pointer_set (hp, 1, cur);
 135         }
 136 }
 137
 138 /*
 139 Insert @value into @list.
 140 The nodes value, cur and prev are returned in @hp.
 141 Return true if @value was inserted by this call. If it returns FALSE, it's the caller
 142 resposibility to release memory.
 143 This function cannot be called from a signal nor with the world stopped.
 144 */
 145 gboolean
 146 mono_lls_insert (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value)
 147 {
 148         MonoLinkedListSetNode *cur, **prev;
 149         /*We must do a store barrier before inserting
 150         to make sure all values in @node are globally visible.*/
 151         mono_memory_barrier ();
 152
 153         while (1) {
 154                 if (mono_lls_find (list, hp, value->key))
 155                         return FALSE;
 156                 cur = mono_hazard_pointer_get_val (hp, 1);
 157                 prev = mono_hazard_pointer_get_val (hp, 2);
 158
 159                 value->next = cur;
 160                 mono_hazard_pointer_set (hp, 0, value);
 161                 /* The CAS must happen after setting the hazard pointer. */
 162                 mono_memory_write_barrier ();
 163                 if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, value, cur) == cur)
 164                         return TRUE;
 165         }
 166 }
 167
 168 /*
 169 Search @list for element with key @key.
 170 The nodes next, cur and prev are returned in @hp
 171 Returns true if @value was removed by this call.
 172 This function cannot be called from a signal nor with the world stopped.
 173 */
 174 gboolean
 175 mono_lls_remove (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value)
 176 {
 177         MonoLinkedListSetNode *cur, **prev, *next;
 178         while (1) {
 179                 if (!mono_lls_find (list, hp, value->key))
 180                         return FALSE;
 181
 182                 next = mono_hazard_pointer_get_val (hp, 0);
 183                 cur = mono_hazard_pointer_get_val (hp, 1);
 184                 prev = mono_hazard_pointer_get_val (hp, 2);
 185
 186                 g_assert (cur == value);
 187
 188                 if (InterlockedCompareExchangePointer ((volatile gpointer*)&cur->next, mask (next, 1), next) != next)
 189                         continue;
 190                 /* The second CAS must happen before the first. */
 191                 mono_memory_write_barrier ();
 192                 if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, next, cur) == cur) {
 193                         /* The CAS must happen before the hazard pointer clear. */
 194                         mono_memory_write_barrier ();
 195                         mono_hazard_pointer_clear (hp, 1);
 196                         if (list->free_node_func)
 197                                 mono_thread_hazardous_free_or_queue (value, list->free_node_func, FALSE, TRUE);
 198                 } else
 199                         mono_lls_find (list, hp, value->key);
 200                 return TRUE;
 201         }
 202 }