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