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