public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [gomp4.1] make libgomp's splay tree implementation key agnostic
@ 2015-10-11 19:47 Aldy Hernandez
  2015-10-15  7:56 ` Jakub Jelinek
  0 siblings, 1 reply; 3+ messages in thread
From: Aldy Hernandez @ 2015-10-11 19:47 UTC (permalink / raw)
  To: gcc-patches, Jakub Jelinek

[-- Attachment #1: Type: text/plain, Size: 1022 bytes --]

Hi.

I'm investigating balanced binary tree options for the multiple 
priorities variant of the task scheduler.  In looking at the splay tree 
adaption in libgomp, I noticed that it requires preexisting typedefs and 
other definitions before including splay-tree.h.  This makes it 
impossible to reuse for another key within the library because 
splay-tree.c must know about the node contents, and other files 
throughout libgomp all share the aforementioned typedefs (because they 
all include libgomp.h).

I also can't use libiberty's version because there are name conflicts 
with libgomp's adaptation.

I see no reason why the splay tree implementation itself (splay-tree.c) 
needs to know about the content of the nodes.  With a little rearranging 
of the data structures and some casts, we can reuse the splay trees at will.

With the following patch we achieve the above, with the only penalty of 
an indirection for a compare callback.

Tested with make check-target-libgomp on x86-64 Linux.

OK for branch?

Aldy

[-- Attachment #2: curr --]
[-- Type: text/plain, Size: 23956 bytes --]

commit 870adcc7fc9b0beb72a4cd78a5cda710c6bff661
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Sat Oct 10 16:28:06 2015 -0700

    	* libgomp.h: Include splay-tree.h earlier.  Use a splay_tree_key_s
    	pointer, instead of splay_tree_key throughout.
    	* oacc-mem.c (KEY): New macro.
    	Rename all uses of splay_tree_key to a splay_tree_key_s pointer.
    	Cast things appropriately.
    	* oacc-parallel.c: Same as oacc-mem.c.
    	* splay-tree.h: Adjust comment to reflect that we no longer need
    	preexisting typedefs before including file.
    	Rename splay_tree_node_s to __internal_splay_tree_node_s.  Move
    	left and right pointers before any other field, and make "key" a
    	generic array.
    	* target.c (KEY): New macro.
    	(splay_compare): Make function static.
    	Rename all uses of splay_tree_key to a splay_tree_key_s pointer.
    	Cast things appropriately.
    	(gomp_map_vars): Adjust gomp_malloc() call to take into account
    	size of key.
    	(gomp_load_image_to_device): Same.
    	(omp_target_associate_ptr): Same.
    	(gomp_target_init): Set mem_map.compare to its comparison
    	function.

diff --git a/libgomp/libgomp.h b/libgomp/libgomp.h
index 19b3dab..48c5442 100644
--- a/libgomp/libgomp.h
+++ b/libgomp/libgomp.h
@@ -44,6 +44,7 @@
 #include "config.h"
 #include "gstdint.h"
 #include "libgomp-plugin.h"
+#include "splay-tree.h"
 
 #include <pthread.h>
 #include <stdbool.h>
@@ -741,13 +742,27 @@ extern void gomp_init_targets_once (void);
 extern int gomp_get_num_devices (void);
 extern void gomp_target_task_fn (void *);
 
-typedef struct splay_tree_node_s *splay_tree_node;
-typedef struct splay_tree_s *splay_tree;
-typedef struct splay_tree_key_s *splay_tree_key;
+/* Special value for refcount - infinity.  */
+#define REFCOUNT_INFINITY (~(uintptr_t) 0)
+
+struct splay_tree_key_s {
+  /* Address of the host object.  */
+  uintptr_t host_start;
+  /* Address immediately after the host object.  */
+  uintptr_t host_end;
+  /* Descriptor of the target memory.  */
+  struct target_mem_desc *tgt;
+  /* Offset from tgt->tgt_start to the start of the target object.  */
+  uintptr_t tgt_offset;
+  /* Reference count.  */
+  uintptr_t refcount;
+  /* Asynchronous reference count.  */
+  uintptr_t async_refcount;
+};
 
 struct target_var_desc {
   /* Splay key.  */
-  splay_tree_key key;
+  struct splay_tree_key_s *key;
   /* True if data should be copied from device to host at the end.  */
   bool copy_from;
   /* True if data always should be copied from device to host at the end.  */
@@ -782,26 +797,6 @@ struct target_mem_desc {
   struct target_var_desc list[];
 };
 
-/* Special value for refcount - infinity.  */
-#define REFCOUNT_INFINITY (~(uintptr_t) 0)
-
-struct splay_tree_key_s {
-  /* Address of the host object.  */
-  uintptr_t host_start;
-  /* Address immediately after the host object.  */
-  uintptr_t host_end;
-  /* Descriptor of the target memory.  */
-  struct target_mem_desc *tgt;
-  /* Offset from tgt->tgt_start to the start of the target object.  */
-  uintptr_t tgt_offset;
-  /* Reference count.  */
-  uintptr_t refcount;
-  /* Asynchronous reference count.  */
-  uintptr_t async_refcount;
-};
-
-#include "splay-tree.h"
-
 typedef struct acc_dispatch_t
 {
   /* This is a linked list of data mapped using the
diff --git a/libgomp/oacc-mem.c b/libgomp/oacc-mem.c
index af067d6..873f3a5 100644
--- a/libgomp/oacc-mem.c
+++ b/libgomp/oacc-mem.c
@@ -35,21 +35,20 @@
 #include <stdint.h>
 #include <assert.h>
 
+#define KEY(K) ((struct splay_tree_key_s *) (K))
+
 /* Return block containing [H->S), or NULL if not contained.  The device lock
    for DEV must be locked on entry, and remains locked on exit.  */
 
-static splay_tree_key
+static struct splay_tree_key_s *
 lookup_host (struct gomp_device_descr *dev, void *h, size_t s)
 {
   struct splay_tree_key_s node;
-  splay_tree_key key;
 
   node.host_start = (uintptr_t) h;
   node.host_end = (uintptr_t) h + s;
 
-  key = splay_tree_lookup (&dev->mem_map, &node);
-
-  return key;
+  return KEY (splay_tree_lookup (&dev->mem_map, &node));
 }
 
 /* Return block containing [D->S), or NULL if not contained.
@@ -58,7 +57,7 @@ lookup_host (struct gomp_device_descr *dev, void *h, size_t s)
    operation.  The device lock associated with TGT must be locked on entry, and
    remains locked on exit.  */
 
-static splay_tree_key
+static struct splay_tree_key_s *
 lookup_dev (struct target_mem_desc *tgt, void *d, size_t s)
 {
   int i;
@@ -80,7 +79,7 @@ lookup_dev (struct target_mem_desc *tgt, void *d, size_t s)
     {
       void * offset;
 
-      splay_tree_key k = &t->array[i].key;
+      struct splay_tree_key_s *k = KEY (&t->array[i].key);
       offset = d - t->tgt_start + k->tgt_offset;
 
       if (k->host_start + offset <= (void *) k->host_end)
@@ -114,7 +113,7 @@ acc_malloc (size_t s)
 void
 acc_free (void *d)
 {
-  splay_tree_key k;
+  struct splay_tree_key_s *k;
 
   if (!d)
     return;
@@ -176,7 +175,6 @@ acc_memcpy_from_device (void *h, void *d, size_t s)
 void *
 acc_deviceptr (void *h)
 {
-  splay_tree_key n;
   void *d;
   void *offset;
 
@@ -187,7 +185,7 @@ acc_deviceptr (void *h)
 
   gomp_mutex_lock (&dev->lock);
 
-  n = lookup_host (dev, h, 1);
+  struct splay_tree_key_s *n = lookup_host (dev, h, 1);
 
   if (!n)
     {
@@ -210,7 +208,7 @@ acc_deviceptr (void *h)
 void *
 acc_hostptr (void *d)
 {
-  splay_tree_key n;
+  struct splay_tree_key_s *n;
   void *h;
   void *offset;
 
@@ -243,8 +241,6 @@ acc_hostptr (void *d)
 int
 acc_is_present (void *h, size_t s)
 {
-  splay_tree_key n;
-
   if (!s || !h)
     return 0;
 
@@ -255,7 +251,7 @@ acc_is_present (void *h, size_t s)
 
   gomp_mutex_lock (&acc_dev->lock);
 
-  n = lookup_host (acc_dev, h, s);
+  struct splay_tree_key_s *n = lookup_host (acc_dev, h, s);
 
   if (n && ((uintptr_t)h < n->host_start
 	    || (uintptr_t)h + s > n->host_end
@@ -340,7 +336,7 @@ acc_unmap_data (void *h)
 
   gomp_mutex_lock (&acc_dev->lock);
 
-  splay_tree_key n = lookup_host (acc_dev, h, 1);
+  struct splay_tree_key_s *n = lookup_host (acc_dev, h, 1);
   struct target_mem_desc *t;
 
   if (!n)
@@ -396,7 +392,6 @@ static void *
 present_create_copy (unsigned f, void *h, size_t s)
 {
   void *d;
-  splay_tree_key n;
 
   if (!h || !s)
     gomp_fatal ("[%p,+%d] is a bad range", (void *)h, (int)s);
@@ -408,7 +403,7 @@ present_create_copy (unsigned f, void *h, size_t s)
 
   gomp_mutex_lock (&acc_dev->lock);
 
-  n = lookup_host (acc_dev, h, s);
+  struct splay_tree_key_s *n = lookup_host (acc_dev, h, s);
   if (n)
     {
       /* Present. */
@@ -492,14 +487,13 @@ static void
 delete_copyout (unsigned f, void *h, size_t s)
 {
   size_t host_size;
-  splay_tree_key n;
   void *d;
   struct goacc_thread *thr = goacc_thread ();
   struct gomp_device_descr *acc_dev = thr->dev;
 
   gomp_mutex_lock (&acc_dev->lock);
 
-  n = lookup_host (acc_dev, h, s);
+  struct splay_tree_key_s *n = lookup_host (acc_dev, h, s);
 
   /* No need to call lazy open, as the data must already have been
      mapped.  */
@@ -545,14 +539,13 @@ void acc_copyout (void *h, size_t s)
 static void
 update_dev_host (int is_dev, void *h, size_t s)
 {
-  splay_tree_key n;
   void *d;
   struct goacc_thread *thr = goacc_thread ();
   struct gomp_device_descr *acc_dev = thr->dev;
 
   gomp_mutex_lock (&acc_dev->lock);
 
-  n = lookup_host (acc_dev, h, s);
+  struct splay_tree_key_s *n = lookup_host (acc_dev, h, s);
 
   /* No need to call lazy open, as the data must already have been
      mapped.  */
@@ -609,13 +602,12 @@ gomp_acc_remove_pointer (void *h, bool force_copyfrom, int async, int mapnum)
 {
   struct goacc_thread *thr = goacc_thread ();
   struct gomp_device_descr *acc_dev = thr->dev;
-  splay_tree_key n;
   struct target_mem_desc *t;
   int minrefs = (mapnum == 1) ? 2 : 3;
 
   gomp_mutex_lock (&acc_dev->lock);
 
-  n = lookup_host (acc_dev, h, 1);
+  struct splay_tree_key_s *n = lookup_host (acc_dev, h, 1);
 
   if (!n)
     {
diff --git a/libgomp/oacc-parallel.c b/libgomp/oacc-parallel.c
index 8f8ad77..9a452ca 100644
--- a/libgomp/oacc-parallel.c
+++ b/libgomp/oacc-parallel.c
@@ -38,6 +38,8 @@
 #include <stdarg.h>
 #include <assert.h>
 
+#define KEY(K) ((struct splay_tree_key_s *) (K))
+
 static int
 find_pset (int pos, size_t mapnum, unsigned short *kinds)
 {
@@ -66,7 +68,7 @@ GOACC_parallel (int device, void (*fn) (void *),
   void **devaddrs;
   unsigned int i;
   struct splay_tree_key_s k;
-  splay_tree_key tgt_fn_key;
+  struct splay_tree_key_s *tgt_fn_key;
   void (*tgt_fn);
 
   if (num_gangs != 1)
@@ -119,7 +121,7 @@ GOACC_parallel (int device, void (*fn) (void *),
       k.host_start = (uintptr_t) fn;
       k.host_end = k.host_start + 1;
       gomp_mutex_lock (&acc_dev->lock);
-      tgt_fn_key = splay_tree_lookup (&acc_dev->mem_map, &k);
+      tgt_fn_key = KEY (splay_tree_lookup (&acc_dev->mem_map, &k));
       gomp_mutex_unlock (&acc_dev->lock);
 
       if (tgt_fn_key == NULL)
diff --git a/libgomp/splay-tree.c b/libgomp/splay-tree.c
index 030ca8f..0d00faa 100644
--- a/libgomp/splay-tree.c
+++ b/libgomp/splay-tree.c
@@ -25,8 +25,8 @@
    <http://www.gnu.org/licenses/>.  */
 
 /* The splay tree code copied from include/splay-tree.h and adjusted,
-   so that all the data lives directly in splay_tree_node_s structure
-   and no extra allocations are needed.  */
+   so that all the data lives directly in the node structure and no
+   extra allocations are needed.  */
 
 /* For an easily readable description of splay-trees, see:
 
@@ -37,9 +37,6 @@
    are amortized O(log n) time for a tree with n nodes.  */
 
 #include "libgomp.h"
-#include "splay-tree.h"
-
-extern int splay_compare (splay_tree_key, splay_tree_key);
 
 /* Rotate the edge joining the left child N with its parent P.  PP is the
    grandparents' pointer to P.  */
@@ -80,7 +77,7 @@ splay_tree_splay (splay_tree sp, splay_tree_key key)
     splay_tree_node n, c;
 
     n = sp->root;
-    cmp1 = splay_compare (key, &n->key);
+    cmp1 = sp->compare (key, &n->key);
 
     /* Found.  */
     if (cmp1 == 0)
@@ -96,7 +93,7 @@ splay_tree_splay (splay_tree sp, splay_tree_key key)
 
     /* Next one left or right?  If found or no child, we're done
        after one rotation.  */
-    cmp2 = splay_compare (key, &c->key);
+    cmp2 = sp->compare (key, &c->key);
     if (cmp2 == 0
 	|| (cmp2 < 0 && !c->left)
 	|| (cmp2 > 0 && !c->right))
@@ -142,7 +139,7 @@ splay_tree_insert (splay_tree sp, splay_tree_node node)
   splay_tree_splay (sp, &node->key);
 
   if (sp->root)
-    comparison = splay_compare (&sp->root->key, &node->key);
+    comparison = sp->compare (&sp->root->key, &node->key);
 
   if (sp->root && comparison == 0)
     gomp_fatal ("Duplicate node");
@@ -175,7 +172,7 @@ splay_tree_remove (splay_tree sp, splay_tree_key key)
 {
   splay_tree_splay (sp, key);
 
-  if (sp->root && splay_compare (&sp->root->key, key) == 0)
+  if (sp->root && sp->compare (&sp->root->key, key) == 0)
     {
       splay_tree_node left, right;
 
@@ -210,7 +207,7 @@ splay_tree_lookup (splay_tree sp, splay_tree_key key)
 {
   splay_tree_splay (sp, key);
 
-  if (sp->root && splay_compare (&sp->root->key, key) == 0)
+  if (sp->root && sp->compare (&sp->root->key, key) == 0)
     return &sp->root->key;
   else
     return NULL;
diff --git a/libgomp/splay-tree.h b/libgomp/splay-tree.h
index 085021c..aed07c3 100644
--- a/libgomp/splay-tree.h
+++ b/libgomp/splay-tree.h
@@ -25,15 +25,8 @@
    <http://www.gnu.org/licenses/>.  */
 
 /* The splay tree code copied from include/splay-tree.h and adjusted,
-   so that all the data lives directly in splay_tree_node_s structure
-   and no extra allocations are needed.
-
-   Files including this header should before including it add:
-typedef struct splay_tree_node_s *splay_tree_node;
-typedef struct splay_tree_s *splay_tree;
-typedef struct splay_tree_key_s *splay_tree_key;
-   define splay_tree_key_s structure, and define
-   splay_compare inline function.  */
+   so that all the data lives directly in the node structure and no
+   extra allocations are needed.  */
 
 /* For an easily readable description of splay-trees, see:
 
@@ -46,18 +39,29 @@ typedef struct splay_tree_key_s *splay_tree_key;
 #ifndef _SPLAY_TREE_H
 #define _SPLAY_TREE_H 1
 
-/* The nodes in the splay tree.  */
-struct splay_tree_node_s {
-  struct splay_tree_key_s key;
+/* The nodes in the splay tree.  The sizeof this structure would be
+   sizeof(__internal_splay_tree_node_s) plus the size of the actual
+   key.  */
+typedef struct __internal_splay_tree_node_s {
   /* The left and right children, respectively.  */
-  splay_tree_node left;
-  splay_tree_node right;
-};
+  struct __internal_splay_tree_node_s *left;
+  struct __internal_splay_tree_node_s *right;
+  /* This is actually a place holder.  The actual key is embedded in
+     this node, and can be accessed by the bits starting at &key
+     here.  */
+  char key[1];
+} *splay_tree_node;
+
+/* Pointer to the KEY.  We declare it void, to make sure we don't
+   dereference it, since the splay-tree.c implementation should make
+   no assumptions as to its contents.  */
+typedef void *splay_tree_key;
 
 /* The splay tree.  */
-struct splay_tree_s {
+typedef struct splay_tree_s {
+  int (*compare)(splay_tree_key, splay_tree_key);
   splay_tree_node root;
-};
+} *splay_tree;
 
 extern splay_tree_key splay_tree_lookup (splay_tree, splay_tree_key);
 extern void splay_tree_insert (splay_tree, splay_tree_node);
diff --git a/libgomp/target.c b/libgomp/target.c
index de6a2c9..bb2ac03 100644
--- a/libgomp/target.c
+++ b/libgomp/target.c
@@ -45,6 +45,8 @@
 #include "plugin-suffix.h"
 #endif
 
+#define KEY(K) ((struct splay_tree_key_s *) (K))
+
 static void gomp_target_init (void);
 
 /* The whole initialization code for offloading plugins is only run one.  */
@@ -94,9 +96,11 @@ gomp_realloc_unlock (void *old, size_t size)
 
 /* The comparison function.  */
 
-attribute_hidden int
-splay_compare (splay_tree_key x, splay_tree_key y)
+static int
+splay_compare (splay_tree_key xp, splay_tree_key yp)
 {
+  struct splay_tree_key_s *x = KEY (xp);
+  struct splay_tree_key_s *y = KEY (yp);
   if (x->host_start == x->host_end
       && y->host_start == y->host_end)
     return 0;
@@ -143,8 +147,8 @@ resolve_device (int device_id)
 }
 
 
-static inline splay_tree_key
-gomp_map_lookup (splay_tree mem_map, splay_tree_key key)
+static inline struct splay_tree_key_s *
+gomp_map_lookup (splay_tree mem_map, struct splay_tree_key_s *key)
 {
   if (key->host_start != key->host_end)
     return splay_tree_lookup (mem_map, key);
@@ -158,16 +162,18 @@ gomp_map_lookup (splay_tree mem_map, splay_tree_key key)
   n = splay_tree_lookup (mem_map, key);
   key->host_start++;
   if (n)
-    return n;
-  return splay_tree_lookup (mem_map, key);
+    return KEY (n);
+  return KEY (splay_tree_lookup (mem_map, key));
 }
 
 /* Handle the case where gomp_map_lookup found oldn for newn.
    Helper function of gomp_map_vars.  */
 
 static inline void
-gomp_map_vars_existing (struct gomp_device_descr *devicep, splay_tree_key oldn,
-			splay_tree_key newn, struct target_var_desc *tgt_var,
+gomp_map_vars_existing (struct gomp_device_descr *devicep,
+			struct splay_tree_key_s *oldn,
+			struct splay_tree_key_s *newn,
+			struct target_var_desc *tgt_var,
 			unsigned char kind)
 {
   tgt_var->key = oldn;
@@ -226,7 +232,7 @@ gomp_map_pointer (struct target_mem_desc *tgt, uintptr_t host_ptr,
   /* Add bias to the pointer value.  */
   cur_node.host_start += bias;
   cur_node.host_end = cur_node.host_start;
-  splay_tree_key n = gomp_map_lookup (mem_map, &cur_node);
+  struct splay_tree_key_s *n = gomp_map_lookup (mem_map, &cur_node);
   if (n == NULL)
     {
       gomp_mutex_unlock (&devicep->lock);
@@ -247,7 +253,8 @@ gomp_map_pointer (struct target_mem_desc *tgt, uintptr_t host_ptr,
 }
 
 static void
-gomp_map_fields_existing (struct target_mem_desc *tgt, splay_tree_key n,
+gomp_map_fields_existing (struct target_mem_desc *tgt,
+			  struct splay_tree_key_s *n,
 			  size_t first, size_t i, void **hostaddrs,
 			  size_t *sizes, void *kinds)
 {
@@ -260,7 +267,7 @@ gomp_map_fields_existing (struct target_mem_desc *tgt, splay_tree_key n,
 
   cur_node.host_start = (uintptr_t) hostaddrs[i];
   cur_node.host_end = cur_node.host_start + sizes[i];
-  splay_tree_key n2 = splay_tree_lookup (mem_map, &cur_node);
+  struct splay_tree_key_s *n2 = KEY (splay_tree_lookup (mem_map, &cur_node));
   kind = get_kind (short_mapkind, kinds, i);
   if (n2
       && n2->tgt == n->tgt
@@ -351,7 +358,7 @@ gomp_map_vars (struct gomp_device_descr *devicep, size_t mapnum,
 	{
 	  cur_node.host_start = (uintptr_t) hostaddrs[i];
 	  cur_node.host_end = cur_node.host_start;
-	  splay_tree_key n = gomp_map_lookup (mem_map, &cur_node);
+	  struct splay_tree_key_s *n = gomp_map_lookup (mem_map, &cur_node);
 	  if (n == NULL)
 	    {
 	      gomp_mutex_unlock (&devicep->lock);
@@ -495,8 +502,9 @@ gomp_map_vars (struct gomp_device_descr *devicep, size_t mapnum,
   tgt->array = NULL;
   if (not_found_cnt || has_firstprivate)
     {
+      size_t asize = sizeof (*tgt->array) + sizeof (struct splay_tree_key_s);
       if (not_found_cnt)
-	tgt->array = gomp_malloc (not_found_cnt * sizeof (*tgt->array));
+	tgt->array = gomp_malloc (not_found_cnt * asize);
       splay_tree_node array = tgt->array;
       size_t j, field_tgt_offset = 0, field_tgt_clear = ~(size_t) 0;
       uintptr_t field_tgt_base = 0;
@@ -557,7 +565,7 @@ gomp_map_vars (struct gomp_device_descr *devicep, size_t mapnum,
 	      default:
 		break;
 	      }
-	    splay_tree_key k = &array->key;
+	    struct splay_tree_key_s *k = KEY (&array->key);
 	    k->host_start = (uintptr_t) hostaddrs[i];
 	    if (!GOMP_MAP_POINTER_P (kind & typemask))
 	      k->host_end = k->host_start + sizes[i];
@@ -774,7 +782,7 @@ gomp_copy_from_async (struct target_mem_desc *tgt)
       }
     else
       {
-	splay_tree_key k = tgt->list[i].key;
+	struct splay_tree_key_s *k = KEY (tgt->list[i].key);
 	if (tgt->list[i].copy_from)
 	  devicep->dev2host_func (devicep->target_id, (void *) k->host_start,
 				  (void *) (k->tgt->tgt_start + k->tgt_offset),
@@ -804,7 +812,7 @@ gomp_unmap_vars (struct target_mem_desc *tgt, bool do_copyfrom)
   size_t i;
   for (i = 0; i < tgt->list_count; i++)
     {
-      splay_tree_key k = tgt->list[i].key;
+      struct splay_tree_key_s *k = KEY (tgt->list[i].key);
       if (k == NULL)
 	continue;
 
@@ -867,7 +875,8 @@ gomp_update (struct gomp_device_descr *devicep, size_t mapnum, void **hostaddrs,
       {
 	cur_node.host_start = (uintptr_t) hostaddrs[i];
 	cur_node.host_end = cur_node.host_start + sizes[i];
-	splay_tree_key n = splay_tree_lookup (&devicep->mem_map, &cur_node);
+	struct splay_tree_key_s *n = KEY (splay_tree_lookup (&devicep->mem_map,
+							     &cur_node));
 	if (n)
 	  {
 	    int kind = get_kind (short_mapkind, kinds, i);
@@ -943,7 +952,8 @@ gomp_load_image_to_device (struct gomp_device_descr *devicep, unsigned version,
 
   /* Insert host-target address mapping into splay tree.  */
   struct target_mem_desc *tgt = gomp_malloc (sizeof (*tgt));
-  tgt->array = gomp_malloc ((num_funcs + num_vars) * sizeof (*tgt->array));
+  size_t asize = sizeof (*tgt->array) + sizeof (struct splay_tree_key_s);
+  tgt->array = gomp_malloc ((num_funcs + num_vars) * asize);
   tgt->refcount = REFCOUNT_INFINITY;
   tgt->tgt_start = 0;
   tgt->tgt_end = 0;
@@ -955,7 +965,7 @@ gomp_load_image_to_device (struct gomp_device_descr *devicep, unsigned version,
 
   for (i = 0; i < num_funcs; i++)
     {
-      splay_tree_key k = &array->key;
+      struct splay_tree_key_s *k = KEY (&array->key);
       k->host_start = (uintptr_t) host_func_table[i];
       k->host_end = k->host_start + 1;
       k->tgt = tgt;
@@ -980,7 +990,7 @@ gomp_load_image_to_device (struct gomp_device_descr *devicep, unsigned version,
 	  gomp_fatal ("Can't map target variables (size mismatch)");
 	}
 
-      splay_tree_key k = &array->key;
+      struct splay_tree_key_s *k = KEY (&array->key);
       k->host_start = (uintptr_t) host_var_table[i * 2];
       k->host_end = k->host_start + (uintptr_t) host_var_table[i * 2 + 1];
       k->tgt = tgt;
@@ -1016,7 +1026,7 @@ gomp_unload_image_from_device (struct gomp_device_descr *devicep,
 
   unsigned j;
   struct splay_tree_key_s k;
-  splay_tree_key node = NULL;
+  struct splay_tree_key_s *node = NULL;
 
   /* Find mapping at start of node array */
   if (num_funcs || num_vars)
@@ -1189,7 +1199,8 @@ gomp_free_memmap (struct splay_tree_s *mem_map)
 {
   while (mem_map->root)
     {
-      struct target_mem_desc *tgt = mem_map->root->key.tgt;
+      struct splay_tree_key_s *key = KEY (&mem_map->root->key);
+      struct target_mem_desc *tgt = key->tgt;
 
       splay_tree_remove (mem_map, &mem_map->root->key);
       free (tgt->array);
@@ -1241,7 +1252,8 @@ gomp_get_target_fn_addr (struct gomp_device_descr *devicep,
       struct splay_tree_key_s k;
       k.host_start = (uintptr_t) host_fn;
       k.host_end = k.host_start + 1;
-      splay_tree_key tgt_fn = splay_tree_lookup (&devicep->mem_map, &k);
+      struct splay_tree_key_s *tgt_fn
+	= KEY (splay_tree_lookup (&devicep->mem_map, &k));
       gomp_mutex_unlock (&devicep->lock);
       if (tgt_fn == NULL)
 	gomp_fatal ("Target function wasn't mapped");
@@ -1521,10 +1533,11 @@ gomp_exit_data (struct gomp_device_descr *devicep, size_t mapnum,
 	case GOMP_MAP_DELETE_ZERO_LEN_ARRAY_SECTION:
 	  cur_node.host_start = (uintptr_t) hostaddrs[i];
 	  cur_node.host_end = cur_node.host_start + sizes[i];
-	  splay_tree_key k = (kind == GOMP_MAP_DELETE_ZERO_LEN_ARRAY_SECTION
+	  struct splay_tree_key_s *k
+	    = (kind == GOMP_MAP_DELETE_ZERO_LEN_ARRAY_SECTION
 			      || kind == GOMP_MAP_ZERO_LEN_ARRAY_SECTION)
 	    ? gomp_map_lookup (&devicep->mem_map, &cur_node)
-	    : splay_tree_lookup (&devicep->mem_map, &cur_node);
+	    : KEY (splay_tree_lookup (&devicep->mem_map, &cur_node));
 	  if (!k)
 	    continue;
 
@@ -1977,7 +1990,7 @@ omp_target_associate_ptr (void *host_ptr, void *device_ptr, size_t size,
 
   cur_node.host_start = (uintptr_t) host_ptr;
   cur_node.host_end = cur_node.host_start + size;
-  splay_tree_key n = gomp_map_lookup (mem_map, &cur_node);
+  struct splay_tree_key_s *n = gomp_map_lookup (mem_map, &cur_node);
   if (n)
     {
       if (n->tgt->tgt_start + n->tgt_offset
@@ -1989,7 +2002,8 @@ omp_target_associate_ptr (void *host_ptr, void *device_ptr, size_t size,
   else
     {
       struct target_mem_desc *tgt = gomp_malloc (sizeof (*tgt));
-      tgt->array = gomp_malloc (sizeof (*tgt->array));
+      tgt->array = gomp_malloc (sizeof (*tgt->array)
+				+ sizeof (struct splay_tree_key_s));
       tgt->refcount = 1;
       tgt->tgt_start = 0;
       tgt->tgt_end = 0;
@@ -1998,7 +2012,7 @@ omp_target_associate_ptr (void *host_ptr, void *device_ptr, size_t size,
       tgt->list_count = 0;
       tgt->device_descr = devicep;
       splay_tree_node array = tgt->array;
-      splay_tree_key k = &array->key;
+      struct splay_tree_key_s *k = KEY (&array->key);
       k->host_start = cur_node.host_start;
       k->host_end = cur_node.host_end;
       k->tgt = tgt;
@@ -2038,7 +2052,7 @@ omp_target_disassociate_ptr (void *ptr, int device_num)
 
   cur_node.host_start = (uintptr_t) ptr;
   cur_node.host_end = cur_node.host_start;
-  splay_tree_key n = gomp_map_lookup (mem_map, &cur_node);
+  struct splay_tree_key_s *n = gomp_map_lookup (mem_map, &cur_node);
   if (n
       && n->host_start == cur_node.host_start
       && n->refcount == REFCOUNT_INFINITY
@@ -2224,6 +2238,7 @@ gomp_target_init (void)
 		/* current_device.capabilities has already been set.  */
 		current_device.type = current_device.get_type_func ();
 		current_device.mem_map.root = NULL;
+		current_device.mem_map.compare = splay_compare;
 		current_device.is_initialized = false;
 		current_device.openacc.data_environ = NULL;
 		for (i = 0; i < new_num_devices; i++)

^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [gomp4.1] make libgomp's splay tree implementation key agnostic
  2015-10-11 19:47 [gomp4.1] make libgomp's splay tree implementation key agnostic Aldy Hernandez
@ 2015-10-15  7:56 ` Jakub Jelinek
  2015-10-15 14:56   ` Aldy Hernandez
  0 siblings, 1 reply; 3+ messages in thread
From: Jakub Jelinek @ 2015-10-15  7:56 UTC (permalink / raw)
  To: Aldy Hernandez; +Cc: gcc-patches

On Sun, Oct 11, 2015 at 12:47:19PM -0700, Aldy Hernandez wrote:
> I'm investigating balanced binary tree options for the multiple priorities
> variant of the task scheduler.  In looking at the splay tree adaption in
> libgomp, I noticed that it requires preexisting typedefs and other
> definitions before including splay-tree.h.  This makes it impossible to
> reuse for another key within the library because splay-tree.c must know
> about the node contents, and other files throughout libgomp all share the
> aforementioned typedefs (because they all include libgomp.h).
> 
> I also can't use libiberty's version because there are name conflicts with
> libgomp's adaptation.
> 
> I see no reason why the splay tree implementation itself (splay-tree.c)
> needs to know about the content of the nodes.  With a little rearranging of
> the data structures and some casts, we can reuse the splay trees at will.
> 
> With the following patch we achieve the above, with the only penalty of an
> indirection for a compare callback.
> 
> Tested with make check-target-libgomp on x86-64 Linux.

What about the following patch instead?
Untested, other than compile time testing.

If one includes splay-tree.h (as already included from splay-tree.h) without
special macros, you get what we have right now, but you can instantiate it
again (though, in that case only for use within a single source file).
The typedefs and type definitions could be moved into libgomp.h if you need
them there, where you put the task_splay_compare inline doesn't matter
either (either libgomp.h or task.c if you only use it in there),
and it is just a matter of including splay-tree.h again in task.c
after defining splay_tree_prefix task.  You then use
task_splay_tree_{lookup,insert,remove} for the task instantiations.

--- libgomp/splay-tree.c.jj	2015-10-14 10:24:10.000000000 +0200
+++ libgomp/splay-tree.c	2015-10-15 08:58:17.301398630 +0200
@@ -37,9 +37,6 @@
    are amortized O(log n) time for a tree with n nodes.  */
 
 #include "libgomp.h"
-#include "splay-tree.h"
-
-extern int splay_compare (splay_tree_key, splay_tree_key);
 
 /* Rotate the edge joining the left child N with its parent P.  PP is the
    grandparents' pointer to P.  */
--- libgomp/target.c.jj	2015-10-14 10:24:10.000000000 +0200
+++ libgomp/target.c	2015-10-15 08:56:45.040779485 +0200
@@ -92,23 +92,6 @@ gomp_realloc_unlock (void *old, size_t s
   return ret;
 }
 
-/* The comparison function.  */
-
-attribute_hidden int
-splay_compare (splay_tree_key x, splay_tree_key y)
-{
-  if (x->host_start == x->host_end
-      && y->host_start == y->host_end)
-    return 0;
-  if (x->host_end <= y->host_start)
-    return -1;
-  if (x->host_start >= y->host_end)
-    return 1;
-  return 0;
-}
-
-#include "splay-tree.h"
-
 attribute_hidden void
 gomp_init_targets_once (void)
 {
--- libgomp/oacc-mem.c.jj	2015-10-14 10:24:10.000000000 +0200
+++ libgomp/oacc-mem.c	2015-10-15 08:58:45.351978800 +0200
@@ -31,7 +31,6 @@
 #include "libgomp.h"
 #include "gomp-constants.h"
 #include "oacc-int.h"
-#include "splay-tree.h"
 #include <stdint.h>
 #include <assert.h>
 
--- libgomp/libgomp.h.jj	2015-10-14 10:24:10.000000000 +0200
+++ libgomp/libgomp.h	2015-10-15 08:57:40.708946305 +0200
@@ -800,6 +800,21 @@ struct splay_tree_key_s {
   uintptr_t async_refcount;
 };
 
+/* The comparison function.  */
+
+static inline int
+splay_compare (splay_tree_key x, splay_tree_key y)
+{
+  if (x->host_start == x->host_end
+      && y->host_start == y->host_end)
+    return 0;
+  if (x->host_end <= y->host_start)
+    return -1;
+  if (x->host_start >= y->host_end)
+    return 1;
+  return 0;
+}
+
 #include "splay-tree.h"
 
 typedef struct acc_dispatch_t
--- libgomp/splay-tree.h.jj	2015-10-14 10:24:10.000000000 +0200
+++ libgomp/splay-tree.h	2015-10-15 09:45:55.073722692 +0200
@@ -33,7 +33,12 @@ typedef struct splay_tree_node_s *splay_
 typedef struct splay_tree_s *splay_tree;
 typedef struct splay_tree_key_s *splay_tree_key;
    define splay_tree_key_s structure, and define
-   splay_compare inline function.  */
+   splay_compare inline function.
+
+   Or, they can define splay_tree_prefix macro before including this
+   header and then all the above types, the splay_compare function
+   and the splay_tree_{lookup,insert_remove} function will be prefixed
+   by that prefix.  */
 
 /* For an easily readable description of splay-trees, see:
 
@@ -43,6 +48,32 @@ typedef struct splay_tree_key_s *splay_t
    The major feature of splay trees is that all basic tree operations
    are amortized O(log n) time for a tree with n nodes.  */
 
+#ifdef splay_tree_prefix
+# define splay_tree_name_1(prefix, name) prefix ## _ ## name
+# define splay_tree_name(prefix, name) splay_tree_name_1 (prefix, name)
+# define splay_tree_node_s	\
+    splay_tree_name (splay_tree_prefix, splay_tree_node_s)
+# define splay_tree_s		\
+    splay_tree_name (splay_tree_prefix, splay_tree_s)
+# define splay_tree_key_s	\
+    splay_tree_name (splay_tree_prefix, splay_tree_key_s)
+# define splay_tree_node	\
+    splay_tree_name (splay_tree_prefix, splay_tree_node)
+# define splay_tree		\
+    splay_tree_name (splay_tree_prefix, splay_tree)
+# define splay_tree_key		\
+    splay_tree_name (splay_tree_prefix, splay_tree_key)
+# define splay_compare		\
+    splay_tree_name (splay_tree_prefix, splay_compare)
+# define splay_tree_lookup	\
+    splay_tree_name (splay_tree_prefix, splay_tree_lookup)
+# define splay_tree_insert	\
+    splay_tree_name (splay_tree_prefix, splay_tree_insert)
+# define splay_tree_remove	\
+    splay_tree_name (splay_tree_prefix, splay_tree_remove)
+# undef _SPLAY_TREE_H
+#endif
+
 #ifndef _SPLAY_TREE_H
 #define _SPLAY_TREE_H 1
 
@@ -63,4 +94,21 @@ extern splay_tree_key splay_tree_lookup
 extern void splay_tree_insert (splay_tree, splay_tree_node);
 extern void splay_tree_remove (splay_tree, splay_tree_key);
 
+#ifdef splay_tree_prefix
+# include "splay-tree.c"
+# undef splay_tree_prefix
+# undef splay_tree_name_1
+# undef splay_tree_name
+# undef splay_tree_node_s
+# undef splay_tree_s
+# undef splay_tree_key_s
+# undef splay_tree_node
+# undef splay_tree
+# undef splay_tree_key
+# undef splay_compare
+# undef splay_tree_lookup
+# undef splay_tree_insert
+# undef splay_tree_remove
+#endif
+
 #endif /* _SPLAY_TREE_H */
--- libgomp/task.c.jj	2015-10-14 10:24:10.000000000 +0200
+++ libgomp/task.c	2015-10-15 09:42:57.513362943 +0200
@@ -59,6 +59,31 @@ htab_eq (hash_entry_type x, hash_entry_t
   return x->addr == y->addr;
 }
 
+/* Define another splay tree instantiation, for task.c priorities.  */
+
+typedef struct task_splay_tree_node_s *task_splay_tree_node;
+typedef struct task_splay_tree_s *task_splay_tree;
+typedef struct task_splay_tree_key_s *task_splay_tree_key;
+
+struct task_splay_tree_key_s {
+  int priority;
+};
+
+/* The comparison function.  */
+
+static inline int
+task_splay_compare (task_splay_tree_key x, task_splay_tree_key y)
+{
+  if (x->priority < y->priority)
+    return -1;
+  if (x->priority > y->priority)
+    return 1;
+  return 0;
+}
+
+#define splay_tree_prefix task
+#include "splay-tree.h"
+
 /* Create a new task data structure.  */
 
 void


	Jakub

^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [gomp4.1] make libgomp's splay tree implementation key agnostic
  2015-10-15  7:56 ` Jakub Jelinek
@ 2015-10-15 14:56   ` Aldy Hernandez
  0 siblings, 0 replies; 3+ messages in thread
From: Aldy Hernandez @ 2015-10-15 14:56 UTC (permalink / raw)
  To: Jakub Jelinek; +Cc: gcc-patches

On 10/15/2015 12:56 AM, Jakub Jelinek wrote:
> On Sun, Oct 11, 2015 at 12:47:19PM -0700, Aldy Hernandez wrote:
>> I'm investigating balanced binary tree options for the multiple priorities
>> variant of the task scheduler.  In looking at the splay tree adaption in
>> libgomp, I noticed that it requires preexisting typedefs and other
>> definitions before including splay-tree.h.  This makes it impossible to
>> reuse for another key within the library because splay-tree.c must know
>> about the node contents, and other files throughout libgomp all share the
>> aforementioned typedefs (because they all include libgomp.h).
>>
>> I also can't use libiberty's version because there are name conflicts with
>> libgomp's adaptation.
>>
>> I see no reason why the splay tree implementation itself (splay-tree.c)
>> needs to know about the content of the nodes.  With a little rearranging of
>> the data structures and some casts, we can reuse the splay trees at will.
>>
>> With the following patch we achieve the above, with the only penalty of an
>> indirection for a compare callback.
>>
>> Tested with make check-target-libgomp on x86-64 Linux.
>
> What about the following patch instead?
> Untested, other than compile time testing.

I would ideally like to look at sp->root from within header files 
(priority_queue.h) to quickly determine if we have an empty queue, and 
the contents of the splay tree are not available in the header file 
(task.c, or priority_queue.c as you describe).  I'd hate to have to call 
a splay-tree.c function to do so.

I could do pointer magic from the header file (yuck).

I could take sp == NULL to mean empty, but then we need to allocate the 
splay tree which is silly cause it's just one pointer.

Up to you, it's your baby. ;-)

Aldy

^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2015-10-15 14:56 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-10-11 19:47 [gomp4.1] make libgomp's splay tree implementation key agnostic Aldy Hernandez
2015-10-15  7:56 ` Jakub Jelinek
2015-10-15 14:56   ` Aldy Hernandez

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).