2 * sgen-array-list.c: A pointer array list that doesn't require reallocs
4 * Copyright (C) 2016 Xamarin Inc
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;
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.
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.
24 #include "mono/sgen/sgen-gc.h"
25 #include "mono/sgen/sgen-array-list.h"
28 sgen_array_list_grow (SgenArrayList *array, guint32 old_capacity)
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;
35 if (array->capacity >= new_capacity)
37 if (array->mem_type != -1)
38 entries = (gpointer*) sgen_alloc_internal_dynamic (new_bucket_size, array->mem_type, TRUE);
40 entries = (gpointer*) g_malloc0 (new_bucket_size);
41 if (array->bucket_alloc_callback)
42 array->bucket_alloc_callback (entries, new_bucket_size, TRUE);
44 * The zeroing of the newly allocated bucket must be complete before storing
45 * the new bucket pointer.
47 mono_memory_write_barrier ();
48 if (InterlockedCompareExchangePointer ((volatile gpointer *)&array->entries [new_bucket], entries, NULL) == NULL) {
50 * It must not be the case that we succeeded in setting the bucket
51 * pointer, while someone else succeeded in changing the capacity.
53 if (InterlockedCompareExchange ((volatile gint32 *)&array->capacity, new_capacity, old_capacity) != old_capacity)
54 g_assert_not_reached ();
55 array->slot_hint = old_capacity;
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);
68 sgen_array_list_find_unset (SgenArrayList *array, guint32 capacity)
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)
76 guint32 slot_hint = array->slot_hint;
78 volatile gpointer *slot;
80 SGEN_ARRAY_LIST_FOREACH_SLOT_RANGE(array, slot_hint, capacity, slot, index) {
81 if (!array->is_slot_set_func (slot))
83 } SGEN_ARRAY_LIST_END_FOREACH_SLOT_RANGE;
85 SGEN_ARRAY_LIST_FOREACH_SLOT_RANGE (array, 0, slot_hint, slot, index) {
86 if (!array->is_slot_set_func (slot))
88 } SGEN_ARRAY_LIST_END_FOREACH_SLOT_RANGE;
95 sgen_array_list_update_next_slot (SgenArrayList *array, guint32 new_index)
97 if (!array->set_slot_func) {
99 * If we don't have a custom setter it means we don't have thread
100 * safety requirements.
102 if (new_index >= array->next_slot)
103 array->next_slot = new_index + 1;
105 guint32 old_next_slot;
106 /* Thread safe update */
108 old_next_slot = array->next_slot;
109 if (new_index < old_next_slot)
111 } while (InterlockedCompareExchange ((volatile gint32 *)&array->next_slot, new_index + 1, old_next_slot) != old_next_slot);
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.
120 sgen_array_list_alloc_block (SgenArrayList *array, guint32 slots_to_add)
122 guint32 new_index = array->next_slot;
123 guint32 old_capacity = array->capacity;
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;
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");
136 array->next_slot = new_index + slots_to_add;
137 /* The slot address will point to the allocated memory */
142 sgen_array_list_add (SgenArrayList *array, gpointer ptr, int data, gboolean increase_size_before_set)
144 guint32 index, capacity;
145 volatile gpointer *slot;
147 if (!array->capacity)
148 sgen_array_list_grow (array, 0);
150 capacity = array->capacity;
151 index = sgen_array_list_find_unset (array, capacity);
153 sgen_array_list_grow (array, capacity);
156 array->slot_hint = index;
158 if (increase_size_before_set) {
159 sgen_array_list_update_next_slot (array, index);
160 mono_memory_write_barrier ();
163 slot = sgen_array_list_get_slot (array, index);
164 if (array->set_slot_func) {
165 if (!array->set_slot_func (slot, ptr, data))
171 if (!increase_size_before_set) {
172 mono_memory_write_barrier ();
173 sgen_array_list_update_next_slot (array, index);
180 * Does a linear search through the pointer array to find `ptr`. Returns the index if
181 * found, otherwise (guint32)-1.
184 sgen_array_list_find (SgenArrayList *array, gpointer ptr)
186 volatile gpointer *slot;
188 SGEN_ARRAY_LIST_FOREACH_SLOT (array, slot) {
191 } SGEN_ARRAY_LIST_END_FOREACH_SLOT;
196 sgen_array_list_default_cas_setter (volatile gpointer *slot, gpointer ptr, int data)
198 if (InterlockedCompareExchangePointer (slot, ptr, NULL) == NULL)
204 sgen_array_list_default_is_slot_set (volatile gpointer *slot)
206 return *slot != NULL;