mono/sgen/sgen-array-list.c

   1 /*
   2  * sgen-array-list.c: A pointer array list that doesn't require reallocs
   3  *
   4  * Copyright (C) 2016 Xamarin Inc
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Library General Public
   8  * License 2.0 as published by the Free Software Foundation;
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public
  16  * License 2.0 along with this library; if not, write to the Free
  17  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  */
  19
  20 #ifdef HAVE_SGEN_GC
  21
  22 #include <string.h>
  23
  24 #include "mono/sgen/sgen-gc.h"
  25 #include "mono/sgen/sgen-array-list.h"
  26
  27 static void
  28 sgen_array_list_grow (SgenArrayList *array, guint32 old_capacity)
  29 {
  30         const guint32 new_bucket = sgen_array_list_index_bucket (old_capacity);
  31         const guint32 growth = sgen_array_list_bucket_size (new_bucket);
  32         const guint32 new_capacity = old_capacity + growth;
  33         const guint32 new_bucket_size = sizeof (**array->entries) * growth;
  34         gpointer *entries;
  35         if (array->capacity >= new_capacity)
  36                 return;
  37         if (array->mem_type != -1)
  38                 entries = (gpointer*) sgen_alloc_internal_dynamic (new_bucket_size, array->mem_type, TRUE);
  39         else
  40                 entries = (gpointer*) g_malloc0 (new_bucket_size);
  41         if (array->bucket_alloc_callback)
  42                 array->bucket_alloc_callback (entries, new_bucket_size, TRUE);
  43         /*
  44          * The zeroing of the newly allocated bucket must be complete before storing
  45          * the new bucket pointer.
  46          */
  47         mono_memory_write_barrier ();
  48         if (InterlockedCompareExchangePointer ((volatile gpointer *)&array->entries [new_bucket], entries, NULL) == NULL) {
  49                 /*
  50                  * It must not be the case that we succeeded in setting the bucket
  51                  * pointer, while someone else succeeded in changing the capacity.
  52                  */
  53                 if (InterlockedCompareExchange ((volatile gint32 *)&array->capacity, new_capacity, old_capacity) != old_capacity)
  54                         g_assert_not_reached ();
  55                 array->slot_hint = old_capacity;
  56                 return;
  57         }
  58         /* Someone beat us to the allocation. */
  59         if (array->bucket_alloc_callback)
  60                 array->bucket_alloc_callback (entries, new_bucket_size, FALSE);
  61         if (array->mem_type != -1)
  62                 sgen_free_internal_dynamic (entries, new_bucket_size, array->mem_type);
  63         else
  64                 g_free (entries);
  65 }
  66
  67 static guint32
  68 sgen_array_list_find_unset (SgenArrayList *array, guint32 capacity)
  69 {
  70         if (!array->is_slot_set_func) {
  71                 guint32 next_slot = array->next_slot;
  72                 /* We can't lookup empty slots, use next_slot */
  73                 if (next_slot < capacity)
  74                         return next_slot;
  75         } else {
  76                 guint32 slot_hint = array->slot_hint;
  77                 guint32 index;
  78                 volatile gpointer *slot;
  79
  80                 SGEN_ARRAY_LIST_FOREACH_SLOT_RANGE(array, slot_hint, capacity, slot, index) {
  81                         if (!array->is_slot_set_func (slot))
  82                                 return index;
  83                 } SGEN_ARRAY_LIST_END_FOREACH_SLOT_RANGE;
  84
  85                 SGEN_ARRAY_LIST_FOREACH_SLOT_RANGE (array, 0, slot_hint, slot, index) {
  86                         if (!array->is_slot_set_func (slot))
  87                                 return index;
  88                 } SGEN_ARRAY_LIST_END_FOREACH_SLOT_RANGE;
  89         }
  90
  91         return -1;
  92 }
  93
  94 static void
  95 sgen_array_list_update_next_slot (SgenArrayList *array, guint32 new_index)
  96 {
  97         if (!array->set_slot_func) {
  98                 /*
  99                  * If we don't have a custom setter it means we don't have thread
 100                  * safety requirements.
 101                  */
 102                 if (new_index >= array->next_slot)
 103                         array->next_slot = new_index + 1;
 104         } else {
 105                 guint32 old_next_slot;
 106                 /* Thread safe update */
 107                 do {
 108                         old_next_slot = array->next_slot;
 109                         if (new_index < old_next_slot)
 110                                 break;
 111                 } while (InterlockedCompareExchange ((volatile gint32 *)&array->next_slot, new_index + 1, old_next_slot) != old_next_slot);
 112         }
 113 }
 114
 115 guint32
 116 sgen_array_list_add (SgenArrayList *array, gpointer ptr, int data, gboolean increase_size_before_set)
 117 {
 118         guint32 index, capacity;
 119         volatile gpointer *slot;
 120
 121         if (!array->capacity)
 122                 sgen_array_list_grow (array, 0);
 123 retry:
 124         capacity = array->capacity;
 125         index = sgen_array_list_find_unset (array, capacity);
 126         if (index == -1) {
 127                 sgen_array_list_grow (array, capacity);
 128                 goto retry;
 129         }
 130         array->slot_hint = index;
 131
 132         if (increase_size_before_set) {
 133                 sgen_array_list_update_next_slot (array, index);
 134                 mono_memory_write_barrier ();
 135         }
 136
 137         slot = sgen_array_list_get_slot (array, index);
 138         if (array->set_slot_func) {
 139                 if (!array->set_slot_func (slot, ptr, data))
 140                         goto retry;
 141         } else {
 142                 *slot = ptr;
 143         }
 144
 145         if (!increase_size_before_set) {
 146                 mono_memory_write_barrier ();
 147                 sgen_array_list_update_next_slot (array, index);
 148         }
 149
 150         return index;
 151 }
 152
 153 /*
 154  * Removes all NULL pointers from the array. Not thread safe
 155  */
 156 void
 157 sgen_array_list_remove_nulls (SgenArrayList *array)
 158 {
 159         guint32 start = 0;
 160         volatile gpointer *slot;
 161
 162         SGEN_ARRAY_LIST_FOREACH_SLOT (array, slot) {
 163                 if (*slot)
 164                         *sgen_array_list_get_slot (array, start++) = *slot;
 165         } SGEN_ARRAY_LIST_END_FOREACH_SLOT;
 166
 167         mono_memory_write_barrier ();
 168         array->next_slot = start;
 169 }
 170
 171 /*
 172  * Does a linear search through the pointer array to find `ptr`.  Returns the index if
 173  * found, otherwise (guint32)-1.
 174  */
 175 guint32
 176 sgen_array_list_find (SgenArrayList *array, gpointer ptr)
 177 {
 178         volatile gpointer *slot;
 179
 180         SGEN_ARRAY_LIST_FOREACH_SLOT (array, slot) {
 181                 if (*slot == ptr)
 182                         return __index;
 183         } SGEN_ARRAY_LIST_END_FOREACH_SLOT;
 184         return (guint32)-1;
 185 }
 186
 187 #endif