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 /*
 116  * Extension for the array list that allows fast allocation and index based fetching
 117  * of long lived memory of various sizes, without the need of realloc. Not thread safe.
 118  */
 119 guint32
 120 sgen_array_list_alloc_block (SgenArrayList *array, guint32 slots_to_add)
 121 {
 122         guint32 new_index = array->next_slot;
 123         guint32 old_capacity = array->capacity;
 124
 125         /* FIXME Don't allocate arrays that will be skipped */
 126         /* There are no empty arrays between next_slot and capacity because we allocate incrementally */
 127         while ((old_capacity - new_index) < slots_to_add) {
 128                 sgen_array_list_grow (array, old_capacity);
 129                 new_index = old_capacity;
 130                 old_capacity = array->capacity;
 131         }
 132
 133         SGEN_ASSERT (0, sgen_array_list_index_bucket (new_index) == sgen_array_list_index_bucket (new_index + slots_to_add - 1),
 134                         "We failed to allocate a continuous block of slots");
 135
 136         array->next_slot = new_index + slots_to_add;
 137         /* The slot address will point to the allocated memory */
 138         return new_index;
 139 }
 140
 141 guint32
 142 sgen_array_list_add (SgenArrayList *array, gpointer ptr, int data, gboolean increase_size_before_set)
 143 {
 144         guint32 index, capacity;
 145         volatile gpointer *slot;
 146
 147         if (!array->capacity)
 148                 sgen_array_list_grow (array, 0);
 149 retry:
 150         capacity = array->capacity;
 151         index = sgen_array_list_find_unset (array, capacity);
 152         if (index == -1) {
 153                 sgen_array_list_grow (array, capacity);
 154                 goto retry;
 155         }
 156         array->slot_hint = index;
 157
 158         if (increase_size_before_set) {
 159                 sgen_array_list_update_next_slot (array, index);
 160                 mono_memory_write_barrier ();
 161         }
 162
 163         slot = sgen_array_list_get_slot (array, index);
 164         if (array->set_slot_func) {
 165                 if (!array->set_slot_func (slot, ptr, data))
 166                         goto retry;
 167         } else {
 168                 *slot = ptr;
 169         }
 170
 171         if (!increase_size_before_set) {
 172                 mono_memory_write_barrier ();
 173                 sgen_array_list_update_next_slot (array, index);
 174         }
 175
 176         return index;
 177 }
 178
 179 /*
 180  * Removes all NULL pointers from the array. Not thread safe
 181  */
 182 void
 183 sgen_array_list_remove_nulls (SgenArrayList *array)
 184 {
 185         guint32 start = 0;
 186         volatile gpointer *slot;
 187
 188         SGEN_ARRAY_LIST_FOREACH_SLOT (array, slot) {
 189                 if (*slot)
 190                         *sgen_array_list_get_slot (array, start++) = *slot;
 191         } SGEN_ARRAY_LIST_END_FOREACH_SLOT;
 192
 193         mono_memory_write_barrier ();
 194         array->next_slot = start;
 195 }
 196
 197 /*
 198  * Does a linear search through the pointer array to find `ptr`.  Returns the index if
 199  * found, otherwise (guint32)-1.
 200  */
 201 guint32
 202 sgen_array_list_find (SgenArrayList *array, gpointer ptr)
 203 {
 204         volatile gpointer *slot;
 205
 206         SGEN_ARRAY_LIST_FOREACH_SLOT (array, slot) {
 207                 if (*slot == ptr)
 208                         return __index;
 209         } SGEN_ARRAY_LIST_END_FOREACH_SLOT;
 210         return (guint32)-1;
 211 }
 212
 213 #endif