[gegl] buffer, tests: specify iterator aliasing rules, and prevent deadlocks



commit 4294bad2e543040a9d7443e4eaa6c926ac4715dd
Author: Ell <ell_se yahoo com>
Date:   Mon Sep 17 13:40:26 2018 -0400

    buffer, tests: specify iterator aliasing rules, and prevent deadlocks
    
    Specify the rules under which aliased buffers, i.e., buffers
    sharing the same tile storage, may be added to the same iterator.
    The rules state that if a buffer is acessed for writing, then the
    iterated-over areas of each of its aliases must either overlap its
    iterated-over area completely, or not at all, and that none of the
    other overlapping aliases may be accessed for writing as well.
    
    Make sure that when these rules are followed, no deadlocks occur
    during iteration, regardless of the order in which the buffers are
    added to the iterator.  This is done by locking all the write-
    accessed tiles before the read-accessed tiles, and unlocking all
    the read-accessed tiles before unlocking/gegl_buffer_set()ing the
    write-accessed tiles.
    
    Add a test case, checking that no deadlocks occur.

 gegl/buffer/gegl-buffer-iterator2.c          | 159 +++++++++++++--------
 gegl/buffer/gegl-buffer-iterator2.h          |  10 ++
 tests/simple/Makefile.am                     |   1 +
 tests/simple/test-buffer-iterator-aliasing.c | 205 +++++++++++++++++++++++++++
 4 files changed, 317 insertions(+), 58 deletions(-)
---
diff --git a/gegl/buffer/gegl-buffer-iterator2.c b/gegl/buffer/gegl-buffer-iterator2.c
index 27aee57b6..53795969c 100644
--- a/gegl/buffer/gegl-buffer-iterator2.c
+++ b/gegl/buffer/gegl-buffer-iterator2.c
@@ -79,17 +79,29 @@ struct _GeglBufferIterator2Priv
   gint              remaining_rows;
   gint              max_slots;
   SubIterState      sub_iter[];
+  /* gint           access_order[]; */ /* allocated, but accessed through
+                                        * get_access_order().
+                                        */
 };
 
 static gboolean threaded = TRUE;
 
+static inline gint *
+get_access_order (GeglBufferIterator2 *iter)
+{
+  GeglBufferIterator2Priv *priv = iter->priv;
+
+  return (gint *) &priv->sub_iter[priv->max_slots];
+}
+
 static inline GeglBufferIterator2 *
 _gegl_buffer_iterator2_empty_new (gint max_slots)
 {
   GeglBufferIterator2 *iter = g_malloc0 (sizeof (GeglBufferIterator2) +
                                          max_slots * sizeof (GeglBufferIterator2Item) +
                                          sizeof (GeglBufferIterator2Priv) +
-                                         max_slots * sizeof (SubIterState));
+                                         max_slots * sizeof (SubIterState) +
+                                         max_slots * sizeof (gint));
   iter->priv      = (void*)(((char*)iter) + sizeof (GeglBufferIterator2) +
                                          max_slots * sizeof (GeglBufferIterator2Item));
 
@@ -440,10 +452,11 @@ needs_rows (GeglBufferIterator2 *iter,
 static inline void
 prepare_iteration (GeglBufferIterator2 *iter)
 {
-  int index;
   GeglBufferIterator2Priv *priv = iter->priv;
+  gint *access_order = get_access_order (iter);
   gint origin_offset_x;
   gint origin_offset_y;
+  gint i;
 
   /* Set up the origin tile */
   /* FIXME: Pick the most compatable buffer, not just the first */
@@ -459,10 +472,30 @@ prepare_iteration (GeglBufferIterator2 *iter)
     origin_offset_y = buf->shift_y + priv->sub_iter[0].full_rect.y;
   }
 
-  for (index = 0; index < priv->num_buffers; index++)
+  /* Set up access order */
+  {
+    gint i_write = 0;
+    gint i_read  = priv->num_buffers - 1;
+    gint index;
+
+    /* Sort the write-access sub-iterators before the read-access ones */
+
+    for (index = 0; index < priv->num_buffers; index++)
+      {
+        SubIterState *sub = &priv->sub_iter[index];
+
+        if (sub->access_mode & GEGL_ACCESS_WRITE)
+          access_order[i_write++] = index;
+        else
+          access_order[i_read--]  = index;
+      }
+  }
+
+  for (i = 0; i < priv->num_buffers; i++)
     {
-      SubIterState *sub = &priv->sub_iter[index];
-      GeglBuffer *buf   = sub->buffer;
+      gint          index = access_order[i];
+      SubIterState *sub   = &priv->sub_iter[index];
+      GeglBuffer   *buf   = sub->buffer;
 
       gint current_offset_x = buf->shift_x + priv->sub_iter[index].full_rect.x;
       gint current_offset_y = buf->shift_y + priv->sub_iter[index].full_rect.y;
@@ -501,11 +534,14 @@ static inline void
 load_rects (GeglBufferIterator2 *iter)
 {
   GeglBufferIterator2Priv *priv = iter->priv;
+  const gint *access_order = get_access_order (iter);
   GeglIteratorState next_state = GeglIteratorState_InTile;
-  int index;
+  gint i;
 
-  for (index = 0; index < priv->num_buffers; index++)
+  for (i = 0; i < priv->num_buffers; i++)
     {
+      gint index = access_order[i];
+
       if (needs_indirect_read (iter, index))
         get_indirect (iter, index);
       else
@@ -519,6 +555,8 @@ load_rects (GeglBufferIterator2 *iter)
 
   if (next_state == GeglIteratorState_InRows)
     {
+      gint index;
+
       if (iter->items[0].roi.height == 1)
         next_state = GeglIteratorState_InTile;
 
@@ -543,16 +581,18 @@ load_rects (GeglBufferIterator2 *iter)
 static inline void
 _gegl_buffer_iterator2_stop (GeglBufferIterator2 *iter)
 {
-  int index;
   GeglBufferIterator2Priv *priv = iter->priv;
+  const gint *access_order = get_access_order (iter);
+  gint i;
 
   if (priv->state != GeglIteratorState_Invalid)
     {
       priv->state = GeglIteratorState_Invalid;
 
-      for (index = 0; index < priv->num_buffers; index++)
+      for (i = priv->num_buffers - 1; i >= 0; i--)
         {
-          SubIterState *sub = &priv->sub_iter[index];
+          gint          index = access_order[i];
+          SubIterState *sub   = &priv->sub_iter[index];
 
           if (sub->current_tile_mode != GeglIteratorTileMode_Empty)
             release_tile (iter, index);
@@ -605,74 +645,75 @@ gegl_buffer_iterator2_stop (GeglBufferIterator2 *iter)
 static void linear_shortcut (GeglBufferIterator2 *iter)
 {
   GeglBufferIterator2Priv *priv = iter->priv;
-  SubIterState *sub0 = &priv->sub_iter[0];
-  int index;
-  int re_use_first[16] = {0,};
+  const gint *access_order = get_access_order (iter);
+  gint index0 = access_order[0];
+  SubIterState *sub0 = &priv->sub_iter[index0];
+  gint i;
 
-  for (index = priv->num_buffers-1; index >=0 ; index--)
+  for (i = 0; i < priv->num_buffers; i++)
   {
-    SubIterState *sub = &priv->sub_iter[index];
+    gint          index        = access_order[i];
+    SubIterState *sub          = &priv->sub_iter[index];
 
     sub->real_roi    = sub0->full_rect;
-    iter->items[index].roi = sub0->full_rect;
-    iter->length = iter->items[0].roi.width * iter->items[0].roi.height;
+    sub->real_roi.x += sub->full_rect.x - sub0->full_rect.x;
+    sub->real_roi.y += sub->full_rect.y - sub0->full_rect.y;
 
-    if (priv->sub_iter[0].buffer == sub->buffer && index != 0)
-    {
-      if (sub->format == priv->sub_iter[0].format)
-        re_use_first[index] = 1;
-    }
+    iter->items[index].roi = sub->real_roi;
+
+    gegl_buffer_lock (sub->buffer);
 
-    if (!re_use_first[index])
+    if (index == index0)
     {
-      gegl_buffer_lock (sub->buffer);
-      if (index == 0)
-        get_tile (iter, index);
-      else
-      {
-        if (sub->buffer->tile_width == sub->buffer->extent.width 
-            && sub->buffer->tile_height == sub->buffer->extent.height
-            && sub->buffer->extent.x == iter->items[index].roi.x
-            && sub->buffer->extent.y == iter->items[index].roi.y)
-        {
-          get_tile (iter, index);
-        }
-        else
-          get_indirect (iter, index);
-      }
+      get_tile (iter, index);
     }
-  }
-  for (index = 1; index < priv->num_buffers; index++)
-  {
-    if (re_use_first[index])
+    else if (sub->buffer == sub0->buffer && sub->format == sub0->format)
     {
       g_print ("!\n");
-      iter->items[index].data = iter->items[0].data;
+      iter->items[index].data = iter->items[index0].data;
+    }
+    else if (sub->buffer->tile_width == sub->buffer->extent.width
+             && sub->buffer->tile_height == sub->buffer->extent.height
+             && sub->buffer->extent.x == iter->items[index].roi.x
+             && sub->buffer->extent.y == iter->items[index].roi.y)
+    {
+      get_tile (iter, index);
+    }
+    else
+    {
+      get_indirect (iter, index);
     }
   }
 
-  priv->state = GeglIteratorState_Stop; /* quit on next iterator_next */
+  iter->length = iter->items[0].roi.width * iter->items[0].roi.height;
+  priv->state  = GeglIteratorState_Stop; /* quit on next iterator_next */
 }
 
 gboolean
 gegl_buffer_iterator2_next (GeglBufferIterator2 *iter)
 {
   GeglBufferIterator2Priv *priv = iter->priv;
+  const gint *access_order = get_access_order (iter);
 
   if (priv->state == GeglIteratorState_Start)
     {
-      int index;
-      GeglBuffer *primary = priv->sub_iter[0].buffer;
-      if (primary->tile_width == primary->extent.width 
-          && primary->tile_height == primary->extent.height 
-          && priv->sub_iter[0].full_rect.width == primary->tile_width 
-          && priv->sub_iter[0].full_rect.height == primary->tile_height
-          && priv->sub_iter[0].full_rect.x == primary->extent.x
-          && priv->sub_iter[0].full_rect.y == primary->extent.y
-          && priv->sub_iter[0].buffer->extent.x == iter->items[0].roi.x
-          && priv->sub_iter[0].buffer->extent.y == iter->items[0].roi.y
+      gint          index0  = access_order[0];
+      SubIterState *sub0    = &priv->sub_iter[index0];
+      GeglBuffer   *primary = sub0->buffer;
+      gint          index;
+
+      if (primary->tile_width == primary->extent.width
+          && primary->tile_height == primary->extent.height
+          && sub0->full_rect.width == primary->tile_width
+          && sub0->full_rect.height == primary->tile_height
+          && sub0->full_rect.x == primary->extent.x
+          && sub0->full_rect.y == primary->extent.y
+          && primary->shift_x == 0
+          && primary->shift_y == 0
           && FALSE) /* XXX: conditions are not strict enough, GIMPs TIFF
-                       plug-in fails; but GEGLs buffer test suite passes */
+                       plug-in fails; but GEGLs buffer test suite passes
+
+                       XXX: still? */
       {
         if (gegl_cl_is_accelerated ())
           for (index = 0; index < priv->num_buffers; index++)
@@ -701,7 +742,7 @@ gegl_buffer_iterator2_next (GeglBufferIterator2 *iter)
     }
   else if (priv->state == GeglIteratorState_InRows)
     {
-      int index;
+      gint index;
 
       for (index = 0; index < priv->num_buffers; index++)
         {
@@ -718,10 +759,12 @@ gegl_buffer_iterator2_next (GeglBufferIterator2 *iter)
     }
   else if (priv->state == GeglIteratorState_InTile)
     {
-      int index;
+      gint i;
 
-      for (index = 0; index < priv->num_buffers; index++)
+      for (i = priv->num_buffers - 1; i >= 0; i--)
         {
+          gint index = access_order[i];
+
           release_tile (iter, index);
         }
 
diff --git a/gegl/buffer/gegl-buffer-iterator2.h b/gegl/buffer/gegl-buffer-iterator2.h
index 03ff9f256..49f44fab8 100644
--- a/gegl/buffer/gegl-buffer-iterator2.h
+++ b/gegl/buffer/gegl-buffer-iterator2.h
@@ -98,6 +98,16 @@ GeglBufferIterator2 * gegl_buffer_iterator2_new  (
  * the corresponding scans and regions will be serialized automatically using
  * gegl_buffer_get.
  *
+ * If the buffer shares its tiles with a previously-added buffer (in
+ * particular, if the same buffer is added more than once), and at least one of
+ * the buffers is accessed for writing, the corresponding iterated-over areas
+ * should either completely overlap, or not overlap at all, in the coordinate-
+ * system of the underlying tile storage (that is, after shifting each area by
+ * the corresponding buffer's shift-x and shift-y properties).  If the areas
+ * overlap, at most one of the buffers may be accessed for writing, and the
+ * data pointers of the corresponding iterator items may refer to the same
+ * data.
+ *
  * Returns: an integer handle refering to the indice in the iterator structure
  * of the added buffer.
  */
diff --git a/tests/simple/Makefile.am b/tests/simple/Makefile.am
index c27296dff..866464715 100644
--- a/tests/simple/Makefile.am
+++ b/tests/simple/Makefile.am
@@ -5,6 +5,7 @@ noinst_PROGRAMS =                       \
        test-buffer-changes             \
        test-buffer-extract             \
        test-buffer-hot-tile    \
+       test-buffer-iterator-aliasing   \
        test-buffer-sharing     \
        test-buffer-tile-voiding        \
        test-buffer-unaligned-access    \
diff --git a/tests/simple/test-buffer-iterator-aliasing.c b/tests/simple/test-buffer-iterator-aliasing.c
new file mode 100644
index 000000000..85f66dac6
--- /dev/null
+++ b/tests/simple/test-buffer-iterator-aliasing.c
@@ -0,0 +1,205 @@
+/* This file is a test-case for GEGL
+ *
+ * GEGL 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 3 of the License, or (at your option) any later version.
+ *
+ * GEGL 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 GEGL; if not, see <https://www.gnu.org/licenses/>.
+ *
+ * Copyright (C) 2018 Ell
+ */
+
+#define GEGL_ITERATOR2_API
+#include "config.h"
+
+#include <stdio.h>
+
+#include "gegl.h"
+
+
+#define SUCCESS    0
+#define FAILURE    -1
+
+#define MAX_TEST_TIME (10 * G_TIME_SPAN_SECOND)
+
+
+static GMutex   mutex;
+static GCond    cond;
+static gboolean finished;
+
+
+static gint
+test_aligned_read_write (void)
+{
+  GeglBuffer         *buffer1;
+  GeglBuffer         *buffer2;
+  GeglColor          *color;
+  GeglBufferIterator *iter;
+  GeglRectangle       rect = {};
+
+  g_object_get (gegl_config (),
+                "tile-width",  &rect.width,
+                "tile-height", &rect.height,
+                NULL);
+
+  buffer1 = gegl_buffer_new (&rect, babl_format ("RGBA float"));
+
+  color = gegl_color_new ("white");
+
+  gegl_buffer_set_color (buffer1, NULL, color);
+
+  g_object_unref (color);
+
+  buffer2 = gegl_buffer_dup (buffer1);
+
+  iter = gegl_buffer_iterator_new (buffer2, NULL, 0, NULL, GEGL_ACCESS_READ,
+                                   GEGL_ABYSS_NONE, 2);
+  gegl_buffer_iterator_add        (iter,
+                                   buffer2, NULL, 0, NULL, GEGL_ACCESS_WRITE,
+                                   GEGL_ABYSS_NONE);
+
+  while (gegl_buffer_iterator_next (iter));
+
+  g_object_unref (buffer2);
+  g_object_unref (buffer1);
+
+  return SUCCESS;
+}
+
+static gint
+test_unaligned_read_write_read (void)
+{
+  GeglBuffer         *buffer1;
+  GeglBuffer         *buffer2;
+  GeglColor          *color;
+  GeglBufferIterator *iter;
+  gint                width;
+  gint                height;
+
+  g_object_get (gegl_config (),
+                "tile-width",  &width,
+                "tile-height", &height,
+                NULL);
+
+  buffer1 = gegl_buffer_new (GEGL_RECTANGLE (0, 0, width + 1, height + 1),
+                             babl_format ("RGBA float"));
+
+  color = gegl_color_new ("white");
+
+  gegl_buffer_set_color (buffer1, NULL, color);
+
+  g_object_unref (color);
+
+  buffer2 = gegl_buffer_dup (buffer1);
+
+  iter = gegl_buffer_iterator_new (buffer2,
+                                   GEGL_RECTANGLE (0,         0,
+                                                   width / 2, height / 2),
+                                   0, NULL, GEGL_ACCESS_READ, GEGL_ABYSS_NONE,
+                                   3);
+  gegl_buffer_iterator_add        (iter,
+                                   buffer2,
+                                   GEGL_RECTANGLE (width / 2, height / 2,
+                                                   width / 2, height / 2),
+                                   0, NULL, GEGL_ACCESS_WRITE, GEGL_ABYSS_NONE);
+  gegl_buffer_iterator_add        (iter,
+                                   buffer2,
+                                   GEGL_RECTANGLE (0,         0,
+                                                   width / 2, height / 2),
+                                   0, NULL, GEGL_ACCESS_READ, GEGL_ABYSS_NONE);
+
+  while (gegl_buffer_iterator_next (iter));
+
+  g_object_unref (buffer2);
+  g_object_unref (buffer1);
+
+  return SUCCESS;
+}
+
+static gpointer
+run_test_thread_func (gint (* func) (void))
+{
+  gint result;
+
+  result = func ();
+
+  g_mutex_lock (&mutex);
+
+  finished = TRUE;
+  g_cond_signal (&cond);
+
+  g_mutex_unlock (&mutex);
+
+  return GINT_TO_POINTER (result);
+}
+
+static gint
+run_test (const gchar   *name,
+          gint        (* func) (void))
+{
+  GThread *thread;
+  gint64   end_time;
+  gint     result = SUCCESS;
+
+  printf ("%s ... ", name);
+  fflush (stdout);
+
+  g_mutex_lock (&mutex);
+
+  finished = FALSE;
+
+  thread = g_thread_new ("test", (GThreadFunc) run_test_thread_func, func);
+
+  end_time = g_get_monotonic_time () + MAX_TEST_TIME;
+
+  while (! finished)
+    {
+      if (! g_cond_wait_until (&cond, &mutex, end_time))
+        {
+          result = FAILURE;
+
+          break;
+        }
+    }
+
+  if (result == SUCCESS)
+    result = GPOINTER_TO_INT (g_thread_join (thread));
+
+  g_mutex_unlock (&mutex);
+
+  printf ("%s\n", result == SUCCESS ? "pass" : "FAIL");
+
+  return result;
+}
+
+#define RUN_TEST(test)                          \
+  G_STMT_START                                  \
+    {                                           \
+      if (result == SUCCESS)                    \
+        result = run_test (#test, test_##test); \
+    }                                           \
+  G_STMT_END
+
+gint
+main (gint    argc,
+      gchar **argv)
+{
+  gint result = SUCCESS;
+
+  gegl_init (&argc, &argv);
+
+  RUN_TEST (aligned_read_write);
+  RUN_TEST (unaligned_read_write_read);
+
+  if (result == SUCCESS)
+    gegl_exit ();
+
+  return result;
+}


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]