Patchwork [RFC] libitm: Filter out undo writes that overlap with the libitm stack.

login
register
mail settings
Submitter Torvald Riegel
Date Jan. 10, 2012, 1:43 p.m.
Message ID <1326202985.23708.1320.camel@triegel.csb>
Download mbox | patch
Permalink /patch/135246/
State New
Headers show

Comments

Torvald Riegel - Jan. 10, 2012, 1:43 p.m.
On Tue, 2012-01-10 at 16:35 +1100, Richard Henderson wrote:
> On 01/09/2012 06:26 AM, Torvald Riegel wrote:
> >     libitm: Filter out undo writes that overlap with the libitm stack.
> >     
> >     	libitm/
> >     	* config/generic/tls.h (GTM::mask_stack_top,
> >     	GTM::mask_stack_bottom): New.
> >     	* local.cc (gtm_undolog::rollback): Filter out any updates that
> >     	overlap the libitm stack.  Add current transaction as parameter.
> >     	* libitm_i.h (GTM::gtm_undolog::rollback): Adapt.
> >     	* beginend.cc (GTM::gtm_thread::rollback): Adapt.
> >     	* testsuite/libitm.c/stackundo.c: New test.
> 
> One could steal code from bohem-gc for this.
> See GC_get_stack_base in os_dep.c.

Thanks for the pointer.  I looked at this code, and it seems fairly
complex given the dependencies on OS/libc and OS/libc behavior.  From a
maintenance point-of-view, does it make sense to copy that complexity
into libitm?  boehm-gc is used in GCC, so perhaps that's not much of a
problem, however.  I also looked at glibc's memcpy implementations, and
copying those plus a simple byte-wise copy for the generic case could be
also a fairly clean solution.
Also, is the license compatible with the GPL wrt. mixing sources?

What about keeping the patch/hack that I posted for now, creating a PR,
and looking at this again for another release?

Attached a slightly updated version with just comments in local.cc
changed.
commit 02357c5f11138f512e714d1740491abc86c61388
Author: Torvald Riegel <triegel@redhat.com>
Date:   Sun Jan 8 20:12:33 2012 +0100

    libitm: Filter out undo writes that overlap with the libitm stack.
    
    	libitm/
    	* config/generic/tls.h (GTM::mask_stack_top,
    	GTM::mask_stack_bottom): New.
    	* local.cc (gtm_undolog::rollback): Filter out any updates that
    	overlap the libitm stack.  Add current transaction as parameter.
    	* libitm_i.h (GTM::gtm_undolog::rollback): Adapt.
    	* beginend.cc (GTM::gtm_thread::rollback): Adapt.
    	* testsuite/libitm.c/stackundo.c: New test.
Richard Henderson - Jan. 10, 2012, 9:09 p.m.
On 01/11/2012 12:43 AM, Torvald Riegel wrote:
>> One could steal code from bohem-gc for this.
>> See GC_get_stack_base in os_dep.c.
> 
> Thanks for the pointer.  I looked at this code, and it seems fairly
> complex given the dependencies on OS/libc and OS/libc behavior.  From a
> maintenance point-of-view, does it make sense to copy that complexity
> into libitm?  boehm-gc is used in GCC, so perhaps that's not much of a
> problem, however.  I also looked at glibc's memcpy implementations, and
> copying those plus a simple byte-wise copy for the generic case could be
> also a fairly clean solution.
> Also, is the license compatible with the GPL wrt. mixing sources?

From the maintenance point of view, I do think it makes sense to copy.
As for the license, I expect we'd want to copy into a separate file so
that we can keep things vaguely separated.

> What about keeping the patch/hack that I posted for now, creating a PR,
> and looking at this again for another release?

I suppose that's not unreasonable.  Ok with...

> +static inline void *
> +mask_stack_bottom(gtm_thread *tx)
> +{
> +  return (uint8_t*)__builtin_dwarf_cfa() - 128;
> +}

Not only can this not be inline, it must be out-of-line.  Otherwise you're not including the stack frame of gtm_undolog::rollback much less memcpy.  You could get this result inline if you specialized for the arch by looking at the hard stack pointer register, but __builtin_dwarf_cfa is at the wrong end of the stack.

You might as well make the fudge factor a lot larger.  Like 4-8k.

> +          if (likely(ptr > top || (uint8_t*)ptr + len <=bot))

Missing space before "bot".


r~
Torvald Riegel - Jan. 13, 2012, 11:52 p.m.
On Wed, 2012-01-11 at 08:09 +1100, Richard Henderson wrote:
> On 01/11/2012 12:43 AM, Torvald Riegel wrote:
> >> One could steal code from bohem-gc for this.
> >> See GC_get_stack_base in os_dep.c.
> > 
> > Thanks for the pointer.  I looked at this code, and it seems fairly
> > complex given the dependencies on OS/libc and OS/libc behavior.  From a
> > maintenance point-of-view, does it make sense to copy that complexity
> > into libitm?  boehm-gc is used in GCC, so perhaps that's not much of a
> > problem, however.  I also looked at glibc's memcpy implementations, and
> > copying those plus a simple byte-wise copy for the generic case could be
> > also a fairly clean solution.
> > Also, is the license compatible with the GPL wrt. mixing sources?
> 
> From the maintenance point of view, I do think it makes sense to copy.
> As for the license, I expect we'd want to copy into a separate file so
> that we can keep things vaguely separated.
> 
> > What about keeping the patch/hack that I posted for now, creating a PR,
> > and looking at this again for another release?
> 
> I suppose that's not unreasonable.  Ok with...
> 
> > +static inline void *
> > +mask_stack_bottom(gtm_thread *tx)
> > +{
> > +  return (uint8_t*)__builtin_dwarf_cfa() - 128;
> > +}
> 
> Not only can this not be inline, it must be out-of-line.  Otherwise you're not including the stack frame of gtm_undolog::rollback much less memcpy.  You could get this result inline if you specialized for the arch by looking at the hard stack pointer register, but __builtin_dwarf_cfa is at the wrong end of the stack.

Oops.  Based on the previous code I thought it would return the bottom
end of the stack frame.  Made this function noinline and moved it to
config/generic/tls.c.

> 
> You might as well make the fudge factor a lot larger.  Like 4-8k.

Opted for 256 because too large might prevents undos to more than
expected with tight stack space.

> 
> > +          if (likely(ptr > top || (uint8_t*)ptr + len <=bot))
> 
> Missing space before "bot".

Committed with those changes as rev 183172.  Created PR libitm/51855.

Patch

diff --git a/libitm/beginend.cc b/libitm/beginend.cc
index fe14f32..08c2174 100644
--- a/libitm/beginend.cc
+++ b/libitm/beginend.cc
@@ -327,7 +327,7 @@  GTM::gtm_thread::rollback (gtm_transaction_cp *cp, bool aborting)
   // data. Because of the latter, we have to roll it back before any
   // dispatch-specific rollback (which handles synchronization with other
   // transactions).
-  undolog.rollback (cp ? cp->undolog_size : 0);
+  undolog.rollback (this, cp ? cp->undolog_size : 0);
 
   // Perform dispatch-specific rollback.
   abi_disp()->rollback (cp);
diff --git a/libitm/config/generic/tls.h b/libitm/config/generic/tls.h
index 6bbdccf..07efef3 100644
--- a/libitm/config/generic/tls.h
+++ b/libitm/config/generic/tls.h
@@ -60,6 +60,25 @@  static inline abi_dispatch * abi_disp() { return _gtm_thr_tls.disp; }
 static inline void set_abi_disp(abi_dispatch *x) { _gtm_thr_tls.disp = x; }
 #endif
 
+#ifndef HAVE_ARCH_GTM_MASK_STACK
+// To filter out any updates that overlap the libitm stack, we define
+// gtm_mask_stack_top to the entry point to the library and
+// gtm_mask_stack_bottom to below current function.  This
+// definition should be fine for all stack-grows-down architectures.
+// FIXME We fake the bottom to be lower so that we are safe even if we might
+// call further functions (compared to where we called gtm_mask_stack_bottom
+// in the call hierarchy) to actually undo or redo writes (e.g., memcpy).
+// This is a completely arbitrary value; can we instead ensure that there are
+// no such calls, or can we determine a future-proof value otherwise?
+static inline void *
+mask_stack_top(gtm_thread *tx) { return tx->jb.cfa; }
+static inline void *
+mask_stack_bottom(gtm_thread *tx)
+{
+  return (uint8_t*)__builtin_dwarf_cfa() - 128;
+}
+#endif
+
 } // namespace GTM
 
 #endif // LIBITM_TLS_H
diff --git a/libitm/libitm_i.h b/libitm/libitm_i.h
index f922d22..f849654 100644
--- a/libitm/libitm_i.h
+++ b/libitm/libitm_i.h
@@ -138,7 +138,7 @@  struct gtm_undolog
   size_t size() const { return undolog.size(); }
 
   // In local.cc
-  void rollback (size_t until_size = 0);
+  void rollback (gtm_thread* tx, size_t until_size = 0);
 };
 
 // Contains all thread-specific data required by the entire library.
diff --git a/libitm/local.cc b/libitm/local.cc
index 39b6da3..8123063 100644
--- a/libitm/local.cc
+++ b/libitm/local.cc
@@ -26,11 +26,20 @@ 
 
 namespace GTM HIDDEN {
 
-
-void
-gtm_undolog::rollback (size_t until_size)
+// This function needs to be noinline because we need to prevent that it gets
+// inlined into another function that calls further functions. This could
+// break our assumption that we only call memcpy and thus only need to
+// additionally protect the memcpy stack (see the hack in mask_stack_bottom()).
+// Even if that isn't an issue because those other calls don't happen during
+// copying, we still need mask_stack_bottom() to be called "close" to the
+// memcpy in terms of stack frames, so just ensure that for now using the
+// noinline.
+void __attribute__((noinline))
+gtm_undolog::rollback (gtm_thread* tx, size_t until_size)
 {
   size_t i, n = undolog.size();
+  void *top = mask_stack_top(tx);
+  void *bot = mask_stack_bottom(tx);
 
   if (n > 0)
     {
@@ -40,7 +49,17 @@  gtm_undolog::rollback (size_t until_size)
           size_t len = undolog[i];
           size_t words = (len + sizeof(gtm_word) - 1) / sizeof(gtm_word);
           i -= words;
-          __builtin_memcpy (ptr, &undolog[i], len);
+          // Filter out any updates that overlap the libitm stack.  We don't
+          // bother filtering out just the overlapping bytes because we don't
+          // merge writes and thus any overlapping write is either bogus or
+          // would restore data on stack frames that are not in use anymore.
+          // FIXME The memcpy can/will end up as another call but we
+          // calculated BOT based on the current function.  Can we inline or
+          // reimplement this without too much trouble due to unaligned calls
+          // and still have good performance, so that we can remove the hack
+          // in mask_stack_bottom()?
+          if (likely(ptr > top || (uint8_t*)ptr + len <=bot))
+            __builtin_memcpy (ptr, &undolog[i], len);
 	}
     }
 }
diff --git a/libitm/testsuite/libitm.c/stackundo.c b/libitm/testsuite/libitm.c/stackundo.c
new file mode 100644
index 0000000..02759d7
--- /dev/null
+++ b/libitm/testsuite/libitm.c/stackundo.c
@@ -0,0 +1,23 @@ 
+int __attribute__((noinline)) test2(int x[1000])
+{
+  int i;
+  return x[12];
+}
+
+int __attribute__((noinline)) test1()
+{
+  int x[1000], i;
+
+  for (i = 0; i < 1000; i++)
+    x[i] = i;
+  return test2(x);
+}
+
+int main()
+{
+  __transaction_atomic {
+    if (test1() !=0)
+      __transaction_cancel;
+  }
+  return 0;
+}