[babl] palette: make palette conversion thread safe

[N/A <ell src gnome org>]

commit aab1ef832fc61c5d21773eb23b17f2b906e0060e
Author: Ell <ell_se yahoo com>
Date:   Wed Jun 21 13:53:08 2017 -0400

    palette: make palette conversion thread safe
    
    Conversion from RGBA u8 to an 8-bit palette format caches conversion
    results in a hash table, belonging to the palette model.  Currently,
    manipulation of the hash table is not thread safe -- when multiple
    threads convert to the same palette format concurrently, the result
    may be wrong.  In particular, there is a race condition when two
    different colors that share the same hash are converted concurrently.
    
    Fix this by changing the hash table layout, so that it can be
    modified atomically.  We assume that aligned 32-bit writes are
    atomic.
    
    Note that the new layout is only suitable for palettes with up to
    256 colors, but this is all we use the hash table for ATM anyway.
    
    Add a regression test.

 babl/babl-palette.c                     |   26 ++++---
 tests/Makefile.am                       |    6 +-
 tests/palette-concurrency-stress-test.c |  133 +++++++++++++++++++++++++++++++
 3 files changed, 152 insertions(+), 13 deletions(-)
---
diff --git a/babl/babl-palette.c b/babl/babl-palette.c
index 2f9bf8d..3c32601 100644
--- a/babl/babl-palette.c
+++ b/babl/babl-palette.c
@@ -60,8 +60,7 @@ typedef struct BablPalette
   unsigned char *data;  /* one linear segment of all the pixels representing the palette, in   order */
   double        *data_double;
   unsigned char *data_u8;
-  int          hash[HASH_TABLE_SIZE];
-  unsigned int hashpx[HASH_TABLE_SIZE];
+  unsigned int   hash[HASH_TABLE_SIZE];
 } BablPalette;
 
 static void
@@ -70,8 +69,7 @@ babl_palette_reset_hash (BablPalette *pal)
   int i;
   for (i = 0; i < HASH_TABLE_SIZE; i++)
     {
-      pal->hashpx[i] = ((255 << 16) | (255 << 8) | 255) + 11; /* non existant pixel */
-      pal->hash[i] = -1;
+      pal->hash[i] = i + 1; /* always a miss */
     }
 }
 
@@ -80,10 +78,18 @@ babl_palette_lookup (BablPalette *pal, int r, int g, int b, int a)
 {
   unsigned int pixel      = (r << 16) | (g << 8) | b;
   int          hash_index = pixel % HASH_TABLE_SIZE;
-  int          idx = pal->hash[hash_index];
-  
-  if (idx >= 0 &&
-      pal->hashpx[hash_index] == pixel)
+  unsigned int hash_value = pal->hash[hash_index];
+  unsigned int hash_pixel = hash_value & 0x00ffffffu;
+  int          idx        = hash_value >> 24;
+
+  /* note:  we're assuming the palette has no more than 256 colors, otherwise
+   * the index doesn't fit in the top 8 bits of the hash-table value.  since
+   * we're only using this functions with u8 palette formats, there's no need
+   * to actually verify this, but if we add wider formats in the future, it's
+   * something to be aware of.
+   */
+
+  if (pixel == hash_pixel)
     {
       return idx;
     }
@@ -108,11 +114,9 @@ babl_palette_lookup (BablPalette *pal, int r, int g, int b, int a)
               best_idx  = idx;
             }
         }
-      pal->hash[hash_index] = best_idx;
-      pal->hashpx[hash_index] = pixel;
+      pal->hash[hash_index] = ((unsigned int) best_idx << 24) | pixel;
       return best_idx;
     }
-  return 0;
 }
 
 static BablPalette *make_pal (const Babl *format, const void *data, int count)
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 61c926a..0db0ccd 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -1,5 +1,7 @@
 if OS_UNIX
-CONCURRENCY_STRESS_TEST = concurrency-stress-test 
+CONCURRENCY_STRESS_TESTS =             \
+       concurrency-stress-test         \
+       palette-concurrency-stress-test
 endif
 
 C_TESTS =                              \
@@ -23,7 +25,7 @@ C_TESTS =                             \
        models                  \
        cairo-RGB24             \
        transparent             \
-       $(CONCURRENCY_STRESS_TEST)
+       $(CONCURRENCY_STRESS_TESTS)
 
 TESTS = \
        $(C_TESTS)
diff --git a/tests/palette-concurrency-stress-test.c b/tests/palette-concurrency-stress-test.c
new file mode 100644
index 0000000..806c8ce
--- /dev/null
+++ b/tests/palette-concurrency-stress-test.c
@@ -0,0 +1,133 @@
+/* babl - dynamically extendable universal pixel conversion library.
+ * Copyright (C) 2009 Martin Nordholts
+ *
+ * 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 3 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, see
+ * <http://www.gnu.org/licenses/>.
+ */
+
+
+#include "config.h"
+
+#include <stdlib.h>
+#include <pthread.h>
+
+#include "babl.h"
+
+
+#define N_THREADS 10
+#define N_PIXELS  1000000 /* (per thread) */
+
+
+/* should be the same as HASH_TABLE_SIZE in babl/babl-palette.c */
+#define BABL_PALETTE_HASH_TABLE_SIZE 1111
+
+
+typedef struct
+{
+  const Babl    *fish;
+  unsigned char  src[4 * N_PIXELS];
+  unsigned char  dest[N_PIXELS];
+} ThreadContext;
+
+
+static void *
+thread_proc (void *data)
+{
+  ThreadContext *ctx = data;
+
+  babl_process (ctx->fish, ctx->src, ctx->dest, N_PIXELS);
+
+  return NULL;
+}
+
+int
+main (int    argc,
+      char **argv)
+{
+  const Babl    *pal;
+  const Babl    *pal_format;
+  unsigned char  colors[4 * N_THREADS];
+  pthread_t      threads[N_THREADS];
+  ThreadContext *ctx[N_THREADS];
+  int            i, j;
+  int            OK = 1;
+
+  babl_init ();
+
+  /* create a palette of N_THREADS different colors, all of which have the same
+   * hash
+   */
+  pal = babl_new_palette (NULL, &pal_format, NULL);
+
+  for (i = 0; i < N_THREADS; i++)
+    {
+      unsigned char *p = &colors[4 * i];
+      unsigned int   v;
+
+      v = i * BABL_PALETTE_HASH_TABLE_SIZE;
+
+      p[0] = (v >> 16) & 0xff;
+      p[1] = (v >>  8) & 0xff;
+      p[2] = (v >>  0) & 0xff;
+      p[3] = 0xff;
+    }
+
+  babl_palette_set_palette (pal, babl_format ("RGBA u8"), colors, N_THREADS);
+
+  /* initialize the thread contexts such that each thread processes a buffer
+   * containing a single, distinct color
+   */
+  for (i = 0; i < N_THREADS; i++)
+    {
+      ctx[i] = malloc (sizeof (ThreadContext));
+
+      ctx[i]->fish = babl_fish (babl_format ("RGBA u8"), pal_format);
+
+      for (j = 0; j < 4 * N_PIXELS; j++)
+        {
+          ctx[i]->src[j] = colors[4 * i + j % 4];
+        }
+    }
+
+  /* run all threads at the same time */
+  for (i = 0; i < N_THREADS; i++)
+    {
+      pthread_create (&threads[i],
+                      NULL, /* attr */
+                      thread_proc,
+                      ctx[i]);
+    }
+
+  /* wait for them to finish */
+  for (i = 0; i < N_THREADS; i++)
+    {
+      pthread_join (threads[i],
+                    NULL /* thread_return */);
+    }
+
+  /* verify the results */
+  for (i = 0; i < N_THREADS; i++)
+    {
+      for (j = 0; OK && j < N_PIXELS; j++)
+        {
+          OK = (ctx[i]->dest[j] == i);
+        }
+
+      free (ctx[i]);
+    }
+
+  babl_exit ();
+
+  return ! OK;
+}