[trans-mem] implement _ITM_dropReferences

[trans-mem] implement _ITM_dropReferences

[Aldy Hernandez]

The following patch implements _ITM_dropReferences() in the library.
This function removes any internal reference to a given chunk of memory.

Two comments.

First, we are effectively ignoring length, especially in the allocations
tree (drop_references_allocations).  Will this make a difference?  In
the local log (drop_references_local) I bend over backwards to
ignore any pointer that would effectively be within [PTR + len].  Again,
does this make a difference?  You keep saying something about
cancel-and-throw which I obviously don't know what it is...

Second, I had to mark _ITM_dropReferences() as `transaction_pure' so it
can be user-called, otherwise we try to call the clone
of _ITM_dropReferences().  We probably need to provide similar treatment
to other functions in <libitm.h> (say _ITM_addUserCommitAction, etc)?

How does this look?

	* alloc_c.cc (_ITM_dropReferences): New.
	* libitm.map (_ITM_dropReferences): Add.
	* libitm.h (_ITM_dropReferences): Add transaction_pure attribute.
	* alloc.cc (record_allocation): Ignore when applicable.
	(forget_allocation): Same.
	(commit_allocations_1): Same.
	(drop_references_allocations): New.
	* libitm_i.h (struct gtm_alloc_action): Add ignore field.
	(struct gtm_transaction): Declare drop_references_allocations.
	Declare drop_references_local.
	* local.cc (struct gtm_local_undo): Add ignore field.
	(rollback_local): Ignore when applicable.
	(drop_references_local): New.
	(GTM_LB): Set ignore field.

Index: alloc_c.cc
===================================================================
--- alloc_c.cc	(revision 161187)
+++ alloc_c.cc	(working copy)
@@ -57,4 +57,15 @@ _ITM_free (void *ptr)
     gtm_tx()->forget_allocation (ptr, free);
 }
 
+/* Forget any internal references to PTR.  */
+
+__attribute__((transaction_pure))
+void ITM_REGPARM
+_ITM_dropReferences (const void *ptr, size_t len)
+{
+  gtm_transaction *tx = gtm_tx();
+  tx->drop_references_local (ptr, len);
+  tx->drop_references_allocations (ptr);
+}
+
 } // extern "C"
Index: libitm.map
===================================================================
--- libitm.map	(revision 161187)
+++ libitm.map	(working copy)
@@ -167,6 +167,7 @@ LIBITM_1.0 {
 	_ITM_malloc;
 	_ITM_calloc;
 	_ITM_free;
+	_ITM_dropReferences;
 
 	_ZGTtnwm;
 	_ZGTtnam;
Index: libitm.h
===================================================================
--- libitm.h	(revision 161187)
+++ libitm.h	(working copy)
@@ -152,6 +152,7 @@ extern void _ITM_addUserUndoAction(_ITM_
 
 extern int _ITM_getThreadnum(void) ITM_REGPARM;
 
+__attribute__((transaction_pure))
 extern void _ITM_dropReferences (const void *, size_t) ITM_REGPARM;
 
 
Index: alloc.cc
===================================================================
--- alloc.cc	(revision 161187)
+++ alloc.cc	(working copy)
@@ -33,7 +33,10 @@ gtm_transaction::record_allocation (void
 
   gtm_alloc_action *a = this->alloc_actions.find(iptr);
   if (a == 0)
-    a = this->alloc_actions.insert(iptr);
+    {
+      a = this->alloc_actions.insert(iptr);
+      a->ignore = false;
+    }
 
   a->free_fn = free_fn;
   a->allocated = true;
@@ -46,7 +49,10 @@ gtm_transaction::forget_allocation (void
 
   gtm_alloc_action *a = this->alloc_actions.find(iptr);
   if (a == 0)
-    a = this->alloc_actions.insert(iptr);
+    {
+      a = this->alloc_actions.insert(iptr);
+      a->ignore = false;
+    }
 
   a->free_fn = free_fn;
   a->allocated = false;
@@ -58,6 +64,9 @@ commit_allocations_1 (uintptr_t key, gtm
   void *ptr = (void *)key;
   uintptr_t revert_p = (uintptr_t) cb_data;
 
+  if (a->ignore)
+    return;
+
   if (a->allocated == revert_p)
     a->free_fn (ptr);
 }
@@ -74,4 +83,24 @@ gtm_transaction::commit_allocations (boo
   this->alloc_actions.clear ();
 }
 
+/* Forget any references to PTR in the allocations tree.
+
+   ?? We ignore the chunk length.  Pray this doesn't wreck havoc.  */
+
+void
+gtm_transaction::drop_references_allocations (const void *ptr)
+{
+  uintptr_t iptr = (uintptr_t) ptr;
+
+  gtm_alloc_action *a = this->alloc_actions.find(iptr);
+  if (a == 0)
+    {
+      a = this->alloc_actions.insert(iptr);
+      a->free_fn = NULL;
+      a->allocated = false;
+    }
+
+  a->ignore = true;
+}
+
 } // namespace GTM
Index: testsuite/libitm.c/dropref.c
===================================================================
--- testsuite/libitm.c/dropref.c	(revision 0)
+++ testsuite/libitm.c/dropref.c	(revision 0)
@@ -0,0 +1,11 @@
+#include <libitm.h>
+
+char *pp;
+
+int main()
+{
+  __transaction {
+    _ITM_dropReferences (pp, 555);
+  }
+  return 0;
+}
Index: testsuite/libitm.c++/dropref.C
===================================================================
--- testsuite/libitm.c++/dropref.C	(revision 0)
+++ testsuite/libitm.c++/dropref.C	(revision 0)
@@ -0,0 +1,11 @@
+#include <libitm.h>
+
+char *pp;
+
+int main()
+{
+  __transaction {
+    _ITM_dropReferences (pp, 555);
+  }
+  return 0;
+}
Index: libitm_i.h
===================================================================
--- libitm_i.h	(revision 161187)
+++ libitm_i.h	(working copy)
@@ -155,6 +155,7 @@ struct gtm_alloc_action
 {
   void (*free_fn)(void *);
   bool allocated;
+  bool ignore;
 };
 
 // This type is private to local.c.
@@ -226,6 +227,7 @@ struct gtm_transaction
   void commit_allocations (bool);
   void record_allocation (void *, void (*)(void *));
   void forget_allocation (void *, void (*)(void *));
+  void drop_references_allocations (const void *);
 
   // In beginend.cc
   void rollback ();
@@ -247,6 +249,7 @@ struct gtm_transaction
   // In local.cc
   void commit_local (void);
   void rollback_local (void);
+  void drop_references_local (const void *, size_t);
 
   // In retry.cc
   void decide_retry_strategy (gtm_restart_reason);
Index: local.cc
===================================================================
--- local.cc	(revision 161187)
+++ local.cc	(working copy)
@@ -30,6 +30,7 @@ struct gtm_local_undo
 {
   void *addr;
   size_t len;
+  bool ignore;
   char saved[];
 };
 
@@ -65,13 +66,36 @@ gtm_transaction::rollback_local (void)
       for (i = n; i-- > 0; )
 	{
 	  gtm_local_undo *u = local_undo[i];
-	  memcpy (u->addr, u->saved, u->len);
+	  if (!u->ignore)
+	    memcpy (u->addr, u->saved, u->len);
 	  free (u);
 	}
       this->n_local_undo = 0;
     }
 }
 
+/* Forget any references to PTR in the local log.  */
+
+void
+gtm_transaction::drop_references_local (const void *ptr, size_t len)
+{
+  gtm_local_undo **local_undo = this->local_undo;
+  size_t i, n = this->n_local_undo;
+
+  if (n > 0)
+    {
+      for (i = n; i > 0; i--)
+	{
+	  gtm_local_undo *u = local_undo[i];
+	  /* ?? Do we need such granularity, or can we get away with
+	     just comparing PTR and LEN. ??  */
+	  if ((const char *)u->addr >= (const char *)ptr
+	      && ((const char *)u->addr + u->len <= (const char *)ptr + len))
+	    u->ignore = true;
+	}
+    }
+}
+
 void ITM_REGPARM
 GTM_LB (const void *ptr, size_t len)
 {
@@ -81,6 +105,7 @@ GTM_LB (const void *ptr, size_t len)
   undo = (gtm_local_undo *) xmalloc (sizeof (struct gtm_local_undo) + len);
   undo->addr = (void *) ptr;
   undo->len = len;
+  undo->ignore = false;
 
   if (tx->local_undo == NULL)
     {

Re: [trans-mem] implement _ITM_dropReferences

[Richard Henderson]

On 06/23/2010 10:12 AM, Aldy Hernandez wrote:
> +void ITM_REGPARM
> +_ITM_dropReferences (const void *ptr, size_t len)
> +{
> +  gtm_transaction *tx = gtm_tx();
> +  tx->drop_references_local (ptr, len);
> +  tx->drop_references_allocations (ptr);
> +}

The primary thing missing here is dropping references inside
the actual transactional memory backend, i.e. gtm_dispatch.

> +/* Forget any references to PTR in the allocations tree.
> +
> +   ?? We ignore the chunk length.  Pray this doesn't wreck havoc.  */
> +
> +void
> +gtm_transaction::drop_references_allocations (const void *ptr)
> +{
> +  uintptr_t iptr = (uintptr_t) ptr;
> +
> +  gtm_alloc_action *a = this->alloc_actions.find(iptr);
> +  if (a == 0)
> +    {
> +      a = this->alloc_actions.insert(iptr);
> +      a->free_fn = NULL;
> +      a->allocated = false;
> +    }
> +
> +  a->ignore = true;
> +}

Why add the ignore field when you could simply alloc_actions.erase?

> @@ -65,13 +66,36 @@ gtm_transaction::rollback_local (void)
>        for (i = n; i-- > 0; )
>  	{
>  	  gtm_local_undo *u = local_undo[i];
> -	  memcpy (u->addr, u->saved, u->len);
> +	  if (!u->ignore)
> +	    memcpy (u->addr, u->saved, u->len);
>  	  free (u);
>  	}
>        this->n_local_undo = 0;
>      }
>  }
>  
> +/* Forget any references to PTR in the local log.  */
> +
> +void
> +gtm_transaction::drop_references_local (const void *ptr, size_t len)
> +{
> +  gtm_local_undo **local_undo = this->local_undo;
> +  size_t i, n = this->n_local_undo;
> +
> +  if (n > 0)
> +    {
> +      for (i = n; i > 0; i--)
> +	{
> +	  gtm_local_undo *u = local_undo[i];
> +	  /* ?? Do we need such granularity, or can we get away with
> +	     just comparing PTR and LEN. ??  */
> +	  if ((const char *)u->addr >= (const char *)ptr
> +	      && ((const char *)u->addr + u->len <= (const char *)ptr + len))
> +	    u->ignore = true;
> +	}
> +    }
> +}

Similarly, it seems easy enough to free the one element and test instead
in rollback_local for u == NULL.



r~

Re: [trans-mem] implement _ITM_dropReferences

[Aldy Hernandez]

On Wed, Jun 23, 2010 at 11:59:10AM -0700, Richard Henderson wrote:
> On 06/23/2010 10:12 AM, Aldy Hernandez wrote:
> > +void ITM_REGPARM
> > +_ITM_dropReferences (const void *ptr, size_t len)
> > +{
> > +  gtm_transaction *tx = gtm_tx();
> > +  tx->drop_references_local (ptr, len);
> > +  tx->drop_references_allocations (ptr);
> > +}
> 
> The primary thing missing here is dropping references inside
> the actual transactional memory backend, i.e. gtm_dispatch.

Ughhhhh... Ok, since I'm about to seriously botch this part of the
implementation as I fight with cachelines and masks, can I get a commit
of the rest of the patch, and continue on to the dispatch code?

> Why add the ignore field when you could simply alloc_actions.erase?

Cause my brain wasn't working?

> Similarly, it seems easy enough to free the one element and test instead
> in rollback_local for u == NULL.

Likewise.

Fixed below.  OK provided I work on the dispatch code next?

	* alloc_c.cc (_ITM_dropReferences): New.
	* libitm.map (_ITM_dropReferences): Add.
	* libitm.h (_ITM_dropReferences): Add transaction_pure attribute.
	* libitm_i.h (struct gtm_transaction): Declare
	drop_references_allocations and drop_references_local.
	* local.cc (rollback_local): Ignore memory when applicable.
	(drop_references_local): New.

Index: alloc_c.cc
===================================================================
--- alloc_c.cc	(revision 161318)
+++ alloc_c.cc	(working copy)
@@ -57,4 +57,15 @@ _ITM_free (void *ptr)
     gtm_tx()->forget_allocation (ptr, free);
 }
 
+/* Forget any internal references to PTR.  */
+
+__attribute__((transaction_pure))
+void ITM_REGPARM
+_ITM_dropReferences (const void *ptr, size_t len)
+{
+  gtm_transaction *tx = gtm_tx();
+  tx->drop_references_local (ptr, len);
+  tx->drop_references_allocations (ptr);
+}
+
 } // extern "C"
Index: libitm.map
===================================================================
--- libitm.map	(revision 161318)
+++ libitm.map	(working copy)
@@ -167,6 +167,7 @@ LIBITM_1.0 {
 	_ITM_malloc;
 	_ITM_calloc;
 	_ITM_free;
+	_ITM_dropReferences;
 
 	_ZGTtnwm;
 	_ZGTtnam;
Index: libitm.h
===================================================================
--- libitm.h	(revision 161318)
+++ libitm.h	(working copy)
@@ -152,6 +152,7 @@ extern void _ITM_addUserUndoAction(_ITM_
 
 extern int _ITM_getThreadnum(void) ITM_REGPARM;
 
+__attribute__((transaction_pure))
 extern void _ITM_dropReferences (const void *, size_t) ITM_REGPARM;
 
 
Index: testsuite/libitm.c/dropref.c
===================================================================
--- testsuite/libitm.c/dropref.c	(revision 0)
+++ testsuite/libitm.c/dropref.c	(revision 0)
@@ -0,0 +1,11 @@
+#include <libitm.h>
+
+char *pp;
+
+int main()
+{
+  __transaction {
+    _ITM_dropReferences (pp, 555);
+  }
+  return 0;
+}
Index: testsuite/libitm.c++/dropref.C
===================================================================
--- testsuite/libitm.c++/dropref.C	(revision 0)
+++ testsuite/libitm.c++/dropref.C	(revision 0)
@@ -0,0 +1,11 @@
+#include <libitm.h>
+
+char *pp;
+
+int main()
+{
+  __transaction {
+    _ITM_dropReferences (pp, 555);
+  }
+  return 0;
+}
Index: libitm_i.h
===================================================================
--- libitm_i.h	(revision 161318)
+++ libitm_i.h	(working copy)
@@ -226,6 +226,10 @@ struct gtm_transaction
   void commit_allocations (bool);
   void record_allocation (void *, void (*)(void *));
   void forget_allocation (void *, void (*)(void *));
+  void drop_references_allocations (const void *ptr)
+  {
+    this->alloc_actions.erase((uintptr_t) ptr);
+  }
 
   // In beginend.cc
   void rollback ();
@@ -247,6 +251,7 @@ struct gtm_transaction
   // In local.cc
   void commit_local (void);
   void rollback_local (void);
+  void drop_references_local (const void *, size_t);
 
   // In retry.cc
   void decide_retry_strategy (gtm_restart_reason);
Index: local.cc
===================================================================
--- local.cc	(revision 161318)
+++ local.cc	(working copy)
@@ -65,13 +65,38 @@ gtm_transaction::rollback_local (void)
       for (i = n; i-- > 0; )
 	{
 	  gtm_local_undo *u = local_undo[i];
-	  memcpy (u->addr, u->saved, u->len);
-	  free (u);
+	  if (u)
+	    {
+	      memcpy (u->addr, u->saved, u->len);
+	      free (u);
+	    }
 	}
       this->n_local_undo = 0;
     }
 }
 
+/* Forget any references to PTR in the local log.  */
+
+void
+gtm_transaction::drop_references_local (const void *ptr, size_t len)
+{
+  gtm_local_undo **local_undo = this->local_undo;
+  size_t i, n = this->n_local_undo;
+
+  if (n > 0)
+    {
+      for (i = n; i > 0; i--)
+	{
+	  gtm_local_undo *u = local_undo[i];
+	  /* ?? Do we need such granularity, or can we get away with
+	     just comparing PTR and LEN. ??  */
+	  if ((const char *)u->addr >= (const char *)ptr
+	      && ((const char *)u->addr + u->len <= (const char *)ptr + len))
+	    this->local_undo = NULL;
+	}
+    }
+}
+
 void ITM_REGPARM
 GTM_LB (const void *ptr, size_t len)
 {

Re: [trans-mem] implement _ITM_dropReferences

[Richard Henderson]

On 06/24/2010 07:50 AM, Aldy Hernandez wrote:
> +	  gtm_local_undo *u = local_undo[i];
> +	  /* ?? Do we need such granularity, or can we get away with
> +	     just comparing PTR and LEN. ??  */
> +	  if ((const char *)u->addr >= (const char *)ptr
> +	      && ((const char *)u->addr + u->len <= (const char *)ptr + len))
> +	    this->local_undo = NULL;
> +	}

Um, no.

  free (u);
  local_undo[i] = NULL;

Ok with that fix.


r~

Re: [trans-mem] implement _ITM_dropReferences

[Aldy Hernandez]

On Thu, Jun 24, 2010 at 09:47:28AM -0700, Richard Henderson wrote:
> On 06/24/2010 07:50 AM, Aldy Hernandez wrote:
> > +	  gtm_local_undo *u = local_undo[i];
> > +	  /* ?? Do we need such granularity, or can we get away with
> > +	     just comparing PTR and LEN. ??  */
> > +	  if ((const char *)u->addr >= (const char *)ptr
> > +	      && ((const char *)u->addr + u->len <= (const char *)ptr + len))
> > +	    this->local_undo = NULL;
> > +	}
> 
> Um, no.
> 
>   free (u);
>   local_undo[i] = NULL;

Whooops :).

OK, fixed and committing.