Branch data Line data Source code
1 : : /* GObject - GLib Type, Object, Parameter and Signal Library
2 : : * Copyright (C) 2009 Benjamin Otte <otte@gnome.org>
3 : : *
4 : : * SPDX-License-Identifier: LGPL-2.1-or-later
5 : : *
6 : : * This library is free software; you can redistribute it and/or
7 : : * modify it under the terms of the GNU Lesser General Public
8 : : * License as published by the Free Software Foundation; either
9 : : * version 2.1 of the License, or (at your option) any later version.
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 : : * Lesser General Public License for more details.
15 : : *
16 : : * You should have received a copy of the GNU Lesser General
17 : : * Public License along with this library; if not, see <http://www.gnu.org/licenses/>.
18 : : */
19 : :
20 : : #include "config.h"
21 : :
22 : : #include "../glib/gvalgrind.h"
23 : : #include <string.h>
24 : :
25 : : #include "gatomicarray.h"
26 : :
27 : : /* A GAtomicArray is a growable, mutable array of data
28 : : * generally of the form of a header of a specific size and
29 : : * then an array of items of a fixed size.
30 : : *
31 : : * It is possible to do lock-less read transactions from the
32 : : * array without any protection against other reads or writes,
33 : : * but such read operation must be aware that the data in the
34 : : * atomic array can change at any time during the transaction,
35 : : * and only at the end can we verify if the transaction succeeded
36 : : * or not. Thus the reading transaction cannot for instance
37 : : * dereference a pointer in the array inside the transaction.
38 : : *
39 : : * The size of an array however cannot change during a read
40 : : * transaction.
41 : : *
42 : : * Writes to the array is done in a copy-update style, but there
43 : : * is no real protection against multiple writers overwriting each
44 : : * others updates, so writes must be protected by an external lock.
45 : : */
46 : :
47 : : G_LOCK_DEFINE_STATIC (array);
48 : :
49 : : typedef struct _FreeListNode FreeListNode;
50 : : struct _FreeListNode {
51 : : FreeListNode *next;
52 : : };
53 : :
54 : : /* This is really a list of array memory blocks, using the
55 : : * first item as the next pointer to chain them together.
56 : : * Protected by array lock */
57 : : static FreeListNode *freelist = NULL;
58 : :
59 : : /* must hold array lock */
60 : : static gpointer
61 : 9468 : freelist_alloc (gsize size, gboolean reuse)
62 : : {
63 : : gpointer mem;
64 : : FreeListNode *free, **prev;
65 : : gsize real_size;
66 : :
67 : 9468 : if (reuse)
68 : : {
69 : 13111 : for (free = freelist, prev = &freelist; free != NULL; prev = &free->next, free = free->next)
70 : : {
71 : 6992 : if (G_ATOMIC_ARRAY_DATA_SIZE (free) == size)
72 : : {
73 : 1996 : *prev = free->next;
74 : 1996 : return (gpointer)free;
75 : : }
76 : : }
77 : : }
78 : :
79 : 7472 : real_size = sizeof (GAtomicArrayMetadata) + MAX (size, sizeof (FreeListNode));
80 : 7472 : mem = g_slice_alloc (real_size);
81 : 7472 : mem = ((char *) mem) + sizeof (GAtomicArrayMetadata);
82 : 7472 : G_ATOMIC_ARRAY_DATA_SIZE (mem) = size;
83 : :
84 : : #if ENABLE_VALGRIND
85 : 7472 : VALGRIND_MALLOCLIKE_BLOCK (mem, real_size - sizeof (GAtomicArrayMetadata),
86 : : FALSE, FALSE);
87 : : #endif
88 : :
89 : 7472 : return mem;
90 : : }
91 : :
92 : : /* must hold array lock */
93 : : static void
94 : 2433 : freelist_free (gpointer mem)
95 : : {
96 : : FreeListNode *free;
97 : :
98 : 2433 : free = mem;
99 : 2433 : free->next = freelist;
100 : 2433 : freelist = free;
101 : 2433 : }
102 : :
103 : : void
104 : 10912 : _g_atomic_array_init (GAtomicArray *array)
105 : : {
106 : 10912 : array->data = NULL;
107 : 10912 : }
108 : :
109 : : /* Get a copy of the data (if non-NULL) that
110 : : * can be changed and then re-applied with
111 : : * g_atomic_array_update().
112 : : *
113 : : * If additional_element_size is > 0 then
114 : : * then the new memory chunk is that much
115 : : * larger, or there were no data we return
116 : : * a chunk of header_size + additional_element_size.
117 : : * This means you can use this to grow the
118 : : * array part and it handles the first element
119 : : * being added automatically.
120 : : *
121 : : * We don't support shrinking arrays, as if
122 : : * we then re-grow we may reuse an old pointer
123 : : * value and confuse the transaction check.
124 : : */
125 : : gpointer
126 : 34001 : _g_atomic_array_copy (GAtomicArray *array,
127 : : gsize header_size,
128 : : gsize additional_element_size)
129 : : {
130 : : guint8 *new, *old;
131 : : gsize old_size, new_size;
132 : :
133 : 34001 : G_LOCK (array);
134 : 34001 : old = g_atomic_pointer_get (&array->data);
135 : 34001 : if (old)
136 : : {
137 : 3681 : old_size = G_ATOMIC_ARRAY_DATA_SIZE (old);
138 : 3681 : new_size = old_size + additional_element_size;
139 : : /* Don't reuse if copying to same size, as this may end
140 : : up reusing the same pointer for the same array thus
141 : : confusing the transaction check */
142 : 3681 : new = freelist_alloc (new_size, additional_element_size != 0);
143 : 3681 : memcpy (new, old, old_size);
144 : : }
145 : 30320 : else if (additional_element_size != 0)
146 : : {
147 : 5787 : new_size = header_size + additional_element_size;
148 : 5787 : new = freelist_alloc (new_size, TRUE);
149 : : }
150 : : else
151 : 24533 : new = NULL;
152 : 34001 : G_UNLOCK (array);
153 : 34001 : return new;
154 : : }
155 : :
156 : : /* Replace the data in the array with the new data,
157 : : * freeing the old data (for reuse). The new data may
158 : : * not be smaller than the current data.
159 : : */
160 : : void
161 : 9468 : _g_atomic_array_update (GAtomicArray *array,
162 : : gpointer new_data)
163 : : {
164 : : guint8 *old;
165 : :
166 : 9468 : G_LOCK (array);
167 : 9468 : old = g_atomic_pointer_exchange (&array->data, new_data);
168 : :
169 : : #ifdef G_DISABLE_ASSERT
170 : : if (old && G_ATOMIC_ARRAY_DATA_SIZE (new_data) < G_ATOMIC_ARRAY_DATA_SIZE (old))
171 : : {
172 : : g_atomic_pointer_set (&array->data, old);
173 : : g_return_if_reached ();
174 : : }
175 : : #else
176 : 9468 : g_assert (old == NULL || G_ATOMIC_ARRAY_DATA_SIZE (old) <= G_ATOMIC_ARRAY_DATA_SIZE (new_data));
177 : : #endif
178 : :
179 : 9468 : if (old)
180 : 2433 : freelist_free (old);
181 : 9468 : G_UNLOCK (array);
182 : 9468 : }
|
