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