[glib/gobject-performance: 8/12] Add GAtomicArray for RCU-style lockless updates

[Alexander Larsson <alexl src gnome org>]

commit d39c19012536997daff2caa5617b91b8208ab2f2
Author: Alexander Larsson <alexl redhat com>
Date:   Wed Sep 9 16:47:44 2009 +0200

    Add GAtomicArray for RCU-style lockless updates
    
    This adds supports for a lock-less a non-shrinking growable array.
    You can use it to do reads using no locks, as long as your read-code
    can handle that during the read transaction the object can be modified
    by another writer (but it will not change size or be freed), and you
    can only trust the result once the transaction has finished successfully.
    
    This doesn't free things like RCU normally does, instead it pushes the
    memory on a free list that is reused for other atomic arrays.

 gobject/Makefile.am    |    3 +-
 gobject/gatomicarray.c |  103 ++++++++++++++++++++++++++++++++++++++++++++++++
 gobject/gatomicarray.h |   59 +++++++++++++++++++++++++++
 3 files changed, 164 insertions(+), 1 deletions(-)
---
diff --git a/gobject/Makefile.am b/gobject/Makefile.am
index ec27aa1..2157208 100644
--- a/gobject/Makefile.am
+++ b/gobject/Makefile.am
@@ -109,9 +109,10 @@ gobject_public_h_sources = \
 	gmarshal.h
 
 # GObject library header files that don't get installed
-gobject_private_h_sources = 
+gobject_private_h_sources = gatomicarray.h
 # GObject library C sources to build the library from
 gobject_c_sources = \
+	gatomicarray.c		\
 	gboxed.c		\
 	gclosure.c		\
 	genums.c		\
diff --git a/gobject/gatomicarray.c b/gobject/gatomicarray.c
new file mode 100644
index 0000000..b464403
--- /dev/null
+++ b/gobject/gatomicarray.c
@@ -0,0 +1,103 @@
+/* GObject - GLib Type, Object, Parameter and Signal Library
+ * Copyright (C) 2009 Benjamin Otte <otte gnome org>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General
+ * Public License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place, Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include "config.h"
+
+#include "gatomicarray.h"
+
+#include <string.h>
+
+G_LOCK_DEFINE_STATIC (array);
+static GList *freelist;
+
+/* must hold array lock */
+static gpointer
+freelist_alloc (gsize size)
+{
+  GList *walk;
+  gpointer mem;
+
+  for (walk = freelist; walk; walk = walk->next) {
+    mem = walk->data;
+    if (ATOMIC_ARRAY_DATA_SIZE (mem) == size) {
+      freelist = g_list_delete_link (freelist, walk);
+      return mem;
+    }
+  }
+
+  mem = g_slice_alloc (size + sizeof (gsize));
+  mem += sizeof (gsize);
+  ATOMIC_ARRAY_DATA_SIZE (mem) = size;
+  return mem;
+}
+
+/* must hold array lock */
+static void
+freelist_free (gpointer mem)
+{
+  freelist = g_list_prepend (freelist, mem);
+}
+
+void
+g_atomic_array_init (GAtomicArray *array)
+{
+  array->data = NULL;
+}
+
+gpointer
+g_atomic_array_copy (GAtomicArray *array,
+		     gsize header_size,
+		     gsize additional_element_size)
+{
+  guint8 *new, *old;
+  gsize old_size, new_size;
+
+  G_LOCK (array);
+  old = g_atomic_pointer_get (&array->data);
+  if (old)
+    {
+      old_size = ATOMIC_ARRAY_DATA_SIZE (old);
+      new_size = old_size + additional_element_size;
+      new = freelist_alloc (new_size);
+      memcpy (new, old, old_size);
+    }
+  else if (additional_element_size != 0)
+    {
+      new_size = header_size + additional_element_size;
+      new = freelist_alloc (new_size);
+    }
+  else
+    new = NULL;
+  G_UNLOCK (array);
+  return new;
+}
+
+void
+g_atomic_array_update (GAtomicArray *array, gpointer new_data)
+{
+  guint8 *old;
+
+  G_LOCK (array);
+  old = g_atomic_pointer_get (&array->data);
+  g_atomic_pointer_set (&array->data, new_data);
+  if (old)
+    freelist_free (old);
+  G_UNLOCK (array);
+}
+
diff --git a/gobject/gatomicarray.h b/gobject/gatomicarray.h
new file mode 100644
index 0000000..99e94a6
--- /dev/null
+++ b/gobject/gatomicarray.h
@@ -0,0 +1,59 @@
+/* GObject - GLib Type, Object, Parameter and Signal Library
+ * Copyright (C) 2009 Benjamin Otte <otte gnome org>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General
+ * Public License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place, Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+#if !defined (__GLIB_GOBJECT_H_INSIDE__) && !defined (GOBJECT_COMPILATION)
+#error "Only <glib-object.h> can be included directly."
+#endif
+
+#ifndef __G_ATOMIC_ARRAY_H__
+#define __G_ATOMIC_ARRAY_H__
+
+#include <glib/glib.h>
+
+G_BEGIN_DECLS
+
+#define ATOMIC_ARRAY_DATA_SIZE(mem) (*((gsize *) (mem) - 1))
+
+typedef struct _GAtomicArray GAtomicArray;
+struct _GAtomicArray {
+  volatile gpointer data;               /* elements - atomic */
+};
+
+void     g_atomic_array_init   (GAtomicArray *array);
+gpointer g_atomic_array_copy   (GAtomicArray *array,
+				gsize         header_size,
+				gsize         additional_element_size);
+void     g_atomic_array_update (GAtomicArray *array,
+				gpointer      new_data);
+
+#define  G_ATOMIC_ARRAY_GET_LOCKED(array, _type) ((_type *)((array)->data))
+
+#define G_ATOMIC_ARRAY_DO_TRANSACTION(array, _type, _C_) G_STMT_START {	\
+    _type *transaction_data, *__check;					\
+								\
+    __check = g_atomic_pointer_get (&(array)->data);		\
+    do {							\
+      transaction_data = __check;						\
+      {_C_;}							\
+      __check = g_atomic_pointer_get (&(array)->data);		\
+    } while (transaction_data != __check);					\
+  } G_STMT_END
+
+G_END_DECLS
+
+#endif	/* __G_ATOMIC_ARRAY_H__ */