gobject/gatomicarray.c

   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 freelist_alloc (gsize size, gboolean reuse)
  62 {
  63   gpointer mem;
  64   FreeListNode *free, **prev;
  65   gsize real_size;
  66
  67   if (reuse)
  68     {
  69       for (free = freelist, prev = &freelist; free != NULL; prev = &free->next, free = free->next)
  70         {
  71           if (G_ATOMIC_ARRAY_DATA_SIZE (free) == size)
  72             {
  73               *prev = free->next;
  74               return (gpointer)free;
  75             }
  76         }
  77     }
  78
  79   real_size = sizeof (GAtomicArrayMetadata) + MAX (size, sizeof (FreeListNode));
  80   mem = g_slice_alloc (real_size);
  81   mem = ((char *) mem) + sizeof (GAtomicArrayMetadata);
  82   G_ATOMIC_ARRAY_DATA_SIZE (mem) = size;
  83
  84 #if ENABLE_VALGRIND
  85   VALGRIND_MALLOCLIKE_BLOCK (mem, real_size - sizeof (GAtomicArrayMetadata),
  86                              FALSE, FALSE);
  87 #endif
  88
  89   return mem;
  90 }
  91
  92 /* must hold array lock */
  93 static void
  94 freelist_free (gpointer mem)
  95 {
  96   FreeListNode *free;
  97
  98   free = mem;
  99   free->next = freelist;
 100   freelist = free;
 101 }
 102
 103 void
 104 _g_atomic_array_init (GAtomicArray *array)
 105 {
 106   array->data = NULL;
 107 }
 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 _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   G_LOCK (array);
 134   old = g_atomic_pointer_get (&array->data);
 135   if (old)
 136     {
 137       old_size = G_ATOMIC_ARRAY_DATA_SIZE (old);
 138       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       new = freelist_alloc (new_size, additional_element_size != 0);
 143       memcpy (new, old, old_size);
 144     }
 145   else if (additional_element_size != 0)
 146     {
 147       new_size = header_size + additional_element_size;
 148       new = freelist_alloc (new_size, TRUE);
 149     }
 150   else
 151     new = NULL;
 152   G_UNLOCK (array);
 153   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 _g_atomic_array_update (GAtomicArray *array,
 162                         gpointer new_data)
 163 {
 164   guint8 *old;
 165
 166   G_LOCK (array);
 167   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   g_assert (old == NULL || G_ATOMIC_ARRAY_DATA_SIZE (old) <= G_ATOMIC_ARRAY_DATA_SIZE (new_data));
 177 #endif
 178
 179   if (old)
 180     freelist_free (old);
 181   G_UNLOCK (array);
 182 }