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 @free_node_func must be lock-free.  That implies that it cannot use malloc/free.
  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 This function cannot be called from a signal nor within interrupt context*.
  73 XXX A variant that works within interrupted is possible if needed.
  74
  75 * interrupt context is when the current thread is reposible for another thread
  76 been suspended at an arbritary point. This is a limitation of our SMR implementation.
  77 */
  78 gboolean
  79 mono_lls_find (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, uintptr_t key)
  80 {
  81         MonoLinkedListSetNode *cur, *next;
  82         MonoLinkedListSetNode **prev;
  83         uintptr_t cur_key;
  84
  85 try_again:
  86         prev = &list->head;
  87
  88         /*
  89          * prev is not really a hazardous pointer, but we return prev
  90          * in hazard pointer 2, so we set it here.  Note also that
  91          * prev is not a pointer to a node.  We use here the fact that
  92          * the first element in a node is the next pointer, so it
  93          * works, but it's not pretty.
  94          */
  95         mono_hazard_pointer_set (hp, 2, prev);
  96
  97         cur = get_hazardous_pointer_with_mask ((gpointer*)prev, hp, 1);
  98
  99         while (1) {
 100                 if (cur == NULL)
 101                         return FALSE;
 102                 next = get_hazardous_pointer_with_mask ((gpointer*)&cur->next, hp, 0);
 103                 cur_key = cur->key;
 104
 105                 /*
 106                  * We need to make sure that we dereference prev below
 107                  * after reading cur->next above, so we need a read
 108                  * barrier.
 109                  */
 110                 mono_memory_read_barrier ();
 111
 112                 if (*prev != cur)
 113                         goto try_again;
 114
 115                 if (!mono_lls_pointer_get_mark (next)) {
 116                         if (cur_key >= key)
 117                                 return cur_key == key;
 118
 119                         prev = &cur->next;
 120                         mono_hazard_pointer_set (hp, 2, cur);
 121                 } else {
 122                         next = mono_lls_pointer_unmask (next);
 123                         if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, next, cur) == cur) {
 124                                 /* The hazard pointer must be cleared after the CAS. */
 125                                 mono_memory_write_barrier ();
 126                                 mono_hazard_pointer_clear (hp, 1);
 127                                 if (list->free_node_func)
 128                                         mono_thread_hazardous_free_or_queue (cur, list->free_node_func, FALSE, TRUE);
 129                         } else
 130                                 goto try_again;
 131                 }
 132                 cur = mono_lls_pointer_unmask (next);
 133                 mono_hazard_pointer_set (hp, 1, cur);
 134         }
 135 }
 136
 137 /*
 138 Insert @value into @list.
 139 The nodes value, cur and prev are returned in @hp.
 140 Return true if @value was inserted by this call. If it returns FALSE, it's the caller
 141 resposibility to release memory.
 142 This function cannot be called from a signal nor with the world stopped.
 143 */
 144 gboolean
 145 mono_lls_insert (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value)
 146 {
 147         MonoLinkedListSetNode *cur, **prev;
 148         /*We must do a store barrier before inserting
 149         to make sure all values in @node are globally visible.*/
 150         mono_memory_barrier ();
 151
 152         while (1) {
 153                 if (mono_lls_find (list, hp, value->key))
 154                         return FALSE;
 155                 cur = mono_hazard_pointer_get_val (hp, 1);
 156                 prev = mono_hazard_pointer_get_val (hp, 2);
 157
 158                 value->next = cur;
 159                 mono_hazard_pointer_set (hp, 0, value);
 160                 /* The CAS must happen after setting the hazard pointer. */
 161                 mono_memory_write_barrier ();
 162                 if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, value, cur) == cur)
 163                         return TRUE;
 164         }
 165 }
 166
 167 /*
 168 Search @list for element with key @key.
 169 The nodes next, cur and prev are returned in @hp
 170 Returns true if @value was removed by this call.
 171 This function cannot be called from a signal nor with the world stopped.
 172 */
 173 gboolean
 174 mono_lls_remove (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value)
 175 {
 176         MonoLinkedListSetNode *cur, **prev, *next;
 177         while (1) {
 178                 if (!mono_lls_find (list, hp, value->key))
 179                         return FALSE;
 180
 181                 next = mono_hazard_pointer_get_val (hp, 0);
 182                 cur = mono_hazard_pointer_get_val (hp, 1);
 183                 prev = mono_hazard_pointer_get_val (hp, 2);
 184
 185                 g_assert (cur == value);
 186
 187                 if (InterlockedCompareExchangePointer ((volatile gpointer*)&cur->next, mask (next, 1), next) != next)
 188                         continue;
 189                 /* The second CAS must happen before the first. */
 190                 mono_memory_write_barrier ();
 191                 if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, next, cur) == cur) {
 192                         /* The CAS must happen before the hazard pointer clear. */
 193                         mono_memory_write_barrier ();
 194                         mono_hazard_pointer_clear (hp, 1);
 195                         if (list->free_node_func)
 196                                 mono_thread_hazardous_free_or_queue (value, list->free_node_func, FALSE, TRUE);
 197                 } else
 198                         mono_lls_find (list, hp, value->key);
 199                 return TRUE;
 200         }
 201 }