mono/sgen/sgen-array-list.c

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