Re: Remove data race in libgcj interpreter

[Andrew Haley <aph@redhat.com>]

I've thought about this a good deal.

Following Hans's suggestion I've added a field thread_count to
class _Jv_InterpMethod and a mutex that's used whenever we rewrite
instructions.  Whenever we enter a method context we create an
instance of ThreadCountAdjuster.  In the ThreadCountAdjuster constructor
we lock the mutex and increment the thread_count in the method.
We also look at the previous method we were executing and decrement
its thread count.  Iff the thread count of a method is <= 1 we
are allowed to rewrite instructions in the method.

We don't have a data race if another thread enters a method while we
are rewriting an instruction because the new thread will block on
the mutex on entry.

There is a small wrinkle in that proxy frames and JNI frames appear
in the method stack but don't have an associated _Jv_InterpMethod.
We detect this case and don't attempt to adjust the thread count.
This means that we might miss an optimization opportunity, but
this is an unusual case and is of little importance.

Andrew.


2008-09-17  Andrew Haley  <aph@redhat.com>

	PR libgcj/8995:
	
	* defineclass.cc (_Jv_ClassReader::handleCodeAttribute):
	Initialize thread_count.
	* include/java-interp.h (_Jv_InterpMethod::thread_count): New
	field.
	 (_Jv_InterpMethod::rewrite_insn_mutex): New mutex.
	(_Jv_InterpFrame:: _Jv_InterpFrame): Pass frame_type.
	* interpret.cc
	(ThreadCountAdjuster): New class.
	(_Jv_InterpMethod::thread_count): New field.
	(_Jv_InitInterpreter): Initialize rewrite_insn_mutex.
	Increment and decrement thread_count field in methods.
	* interpret-run.cc (REWRITE_INSN): Check thread_count <= 1.
	(REWRITE_INSN): Likewise.
	Declare a ThreadCountAdjuster.
	* java/lang/reflect/natVMProxy.cc (run_proxy): Initialize frame
	type as frame_proxy..
	
Index: interpret.cc
===================================================================
*** interpret.cc	(revision 139469)
--- interpret.cc	(working copy)
*************** static void find_catch_location (jthrowa
*** 78,87 ****
--- 78,92 ----
  // the Class monitor as user code in another thread could hold it.
  static _Jv_Mutex_t compile_mutex;

+ // See class ThreadCountAdjuster and REWRITE_INSN for how this is
+ // used.
+ _Jv_Mutex_t _Jv_InterpMethod::rewrite_insn_mutex;
+
  void
  _Jv_InitInterpreter()
  {
    _Jv_MutexInit (&compile_mutex);
+   _Jv_MutexInit (&_Jv_InterpMethod::rewrite_insn_mutex);
  }
  #else
  void _Jv_InitInterpreter() {}
Index: include/java-interp.h
===================================================================
*** include/java-interp.h	(revision 139469)
--- include/java-interp.h	(working copy)
*************** class _Jv_InterpMethod : public _Jv_Meth
*** 175,180 ****
--- 175,191 ----
    static pc_t breakpoint_insn;
  #ifdef DIRECT_THREADED
    static insn_slot bp_insn_slot;
+
+ public:
+   // Mutex to prevent a data race between threads when rewriting
+   // instructions.  See interpret-run.cc for an explanation of its use.
+   static _Jv_Mutex_t rewrite_insn_mutex;
+
+   // The count of threads executing this method.
+   long thread_count;
+
+ private:
+
  #else
    static unsigned char bp_insn_opcode;
  #endif
*************** public:
*** 455,463 ****
    jobject obj_ptr;

    _Jv_InterpFrame (void *meth, java::lang::Thread *thr, jclass proxyCls = NULL,
!                    pc_t *pc = NULL)
    : _Jv_Frame (reinterpret_cast<_Jv_MethodBase *> (meth), thr,
! 	             frame_interpreter)
    {
      next_interp = (_Jv_InterpFrame *) thr->interp_frame;
      proxyClass = proxyCls;
--- 466,475 ----
    jobject obj_ptr;

    _Jv_InterpFrame (void *meth, java::lang::Thread *thr, jclass proxyCls = NULL,
!                    pc_t *pc = NULL,
! 		   _Jv_FrameType frame_type = frame_interpreter)
    : _Jv_Frame (reinterpret_cast<_Jv_MethodBase *> (meth), thr,
! 	             frame_type)
    {
      next_interp = (_Jv_InterpFrame *) thr->interp_frame;
      proxyClass = proxyCls;
*************** public:
*** 501,506 ****
--- 513,588 ----
    }
  };

+ #ifdef DIRECT_THREADED
+ // This class increments and decrements the thread_count field in an
+ // interpreted method.  On entry to the interpreter a
+ // ThreadCountAdjuster is created when increments the thread_count in
+ // the current method and uses the next_interp field in the frame to
+ // find the previous method and decrement its thread_count.
+ class ThreadCountAdjuster
+ {
+
+   // A class used to handle the rewrite_insn_mutex while we're
+   // adjusting the thread_count in a method.  Unlocking the mutex in a
+   // destructor ensures that it's unlocked even if (for example) a
+   // segfault occurs in the critical section.
+   class MutexLock
+   {
+   private:
+     _Jv_Mutex_t *mutex;
+   public:
+     MutexLock (_Jv_Mutex_t *m)
+     {
+       mutex = m;
+       _Jv_MutexLock (mutex);
+     }
+     ~MutexLock ()
+     {
+       _Jv_MutexUnlock (mutex);
+     }
+   };
+
+   _Jv_InterpMethod *method;
+   _Jv_InterpMethod *next_method;
+
+ public:
+
+   ThreadCountAdjuster (_Jv_InterpMethod *m, _Jv_InterpFrame *fr)
+   {
+     MutexLock lock (&::_Jv_InterpMethod::rewrite_insn_mutex);
+
+     method = m;
+     next_method = NULL;
+
+     _Jv_InterpFrame *next_interp = fr->next_interp;
+
+     // Record the fact that we're executing this method and that
+     // we're no longer executing the method that called us.
+     method->thread_count++;
+
+     if (next_interp && next_interp->frame_type == frame_interpreter)
+       {
+ 	next_method
+ 	  = reinterpret_cast<_Jv_InterpMethod *> (next_interp->meth);
+ 	next_method->thread_count--;
+       }
+   }
+
+   ~ThreadCountAdjuster ()
+   {
+     MutexLock lock (&::_Jv_InterpMethod::rewrite_insn_mutex);
+
+     // We're going to return to the method that called us, so bump its
+     // thread_count and decrement our own.
+
+     method->thread_count--;
+
+     if (next_method)
+       next_method->thread_count++;
+   }
+ };
+ #endif // DIRECT_THREADED
+
  #endif /* INTERPRETER */

  #endif /* __JAVA_INTERP_H__ */
Index: ChangeLog
===================================================================
*** ChangeLog	(revision 139493)
--- ChangeLog	(working copy)
***************
*** 1,3 ****
--- 1,24 ----
+ 2008-09-17  Andrew Haley  <aph@redhat.com>
+
+ 	PR libgcj/8995:
+ 	
+ 	* defineclass.cc (_Jv_ClassReader::handleCodeAttribute):
+ 	Initialize thread_count.
+ 	* include/java-interp.h (_Jv_InterpMethod::thread_count): New
+ 	field.
+ 	 (_Jv_InterpMethod::rewrite_insn_mutex): New mutex.
+ 	(_Jv_InterpFrame:: _Jv_InterpFrame): Pass frame_type.
+ 	* interpret.cc
+ 	(ThreadCountAdjuster): New class.
+ 	(_Jv_InterpMethod::thread_count): New field.
+ 	(_Jv_InitInterpreter): Initialize rewrite_insn_mutex.
+ 	Increment and decrement thread_count field in methods.
+ 	* interpret-run.cc (REWRITE_INSN): Check thread_count <= 1.
+ 	(REWRITE_INSN): Likewise.
+ 	Declare a ThreadCountAdjuster.
+ 	* java/lang/reflect/natVMProxy.cc (run_proxy): Initialize frame
+ 	type as frame_proxy..
+ 	
  2008-08-22  Andrew Haley  <aph@redhat.com>

  	PR libgcj/8995:
Index: interpret-run.cc
===================================================================
*** interpret-run.cc	(revision 139978)
--- interpret-run.cc	(working copy)
*************** details.  */
*** 29,34 ****
--- 29,38 ----
    _Jv_InterpFrame frame_desc (meth, thread);
  #endif

+ #ifdef DIRECT_THREADED
+   ThreadCountAdjuster adj (meth, &frame_desc);
+ #endif // DIRECT_THREADED
+
    _Jv_word stack[meth->max_stack];
    _Jv_word *sp = stack;

*************** details.  */
*** 361,380 ****
      }									\
    while (0)

  #undef REWRITE_INSN
  #define REWRITE_INSN(INSN,SLOT,VALUE)					\
!   do {									\
!     if (pc[-2].insn == breakpoint_insn->insn)				\
!       {									\
! 	using namespace ::gnu::gcj::jvmti;				\
! 	jlocation location = meth->insn_index (pc - 2);			\
! 	_Jv_RewriteBreakpointInsn (meth->self, location, (pc_t) INSN);	\
!       }									\
!     else								\
!       pc[-2].insn = INSN;						\
  									\
!     pc[-1].SLOT = VALUE;						\
!   }									\
    while (0)

  #undef INTERP_REPORT_EXCEPTION
--- 365,393 ----
      }									\
    while (0)

+ // We fail to rewrite a breakpoint if there is another thread
+ // currently executing this method.  This is a bug, but there's
+ // nothing else we can do that doesn't cause a data race.
  #undef REWRITE_INSN
  #define REWRITE_INSN(INSN,SLOT,VALUE)					\
!   do									\
!     {									\
!       _Jv_MutexLock (&rewrite_insn_mutex);				\
!       if (meth->thread_count <= 1)					\
! 	{								\
! 	  if (pc[-2].insn == breakpoint_insn->insn)			\
! 	    {								\
! 	      using namespace ::gnu::gcj::jvmti;			\
! 	      jlocation location = meth->insn_index (pc - 2);		\
! 	      _Jv_RewriteBreakpointInsn (meth->self, location, (pc_t) INSN); \
! 	    }								\
! 	  else								\
! 	    pc[-2].insn = INSN;						\
  									\
! 	  pc[-1].SLOT = VALUE;						\
! 	}								\
!       _Jv_MutexUnlock (&rewrite_insn_mutex);				\
!     }									\
    while (0)

  #undef INTERP_REPORT_EXCEPTION
*************** details.  */
*** 383,405 ****
  #undef NEXT_INSN
  #define NEXT_INSN goto *((pc++)->insn)

- // REWRITE_INSN does nothing.
- //
  // Rewriting a multi-word instruction in the presence of multiple
! // threads leads to a data race if a thread reads part of an
! // instruction while some other thread is rewriting that instruction.
! // For example, an invokespecial instruction may be rewritten to
! // invokespecial_resolved and its operand changed from an index to a
! // pointer while another thread is executing invokespecial.  This
! // other thread then reads the pointer that is now the operand of
! // invokespecial_resolved and tries to use it as an index.
! //
! // Fixing this requires either spinlocks, a more elaborate data
! // structure, or even per-thread allocated pages.  It's clear from the
! // locking in meth->compile below that the presence of multiple
! // threads was contemplated when this code was written, but the full
! // consequences were not fully appreciated.
! #define REWRITE_INSN(INSN,SLOT,VALUE)

  #undef INTERP_REPORT_EXCEPTION
  #define INTERP_REPORT_EXCEPTION(Jthrowable) /* not needed when not debugging */
--- 396,418 ----
  #undef NEXT_INSN
  #define NEXT_INSN goto *((pc++)->insn)

  // Rewriting a multi-word instruction in the presence of multiple
! // threads is a data race if a thread reads part of an instruction
! // while some other thread is rewriting that instruction.  We detect
! // more than one thread executing a method and don't rewrite the
! // instruction.  A thread entering a method blocks on
! // rewrite_insn_mutex until the write is complete.
! #define REWRITE_INSN(INSN,SLOT,VALUE)		\
!   do {						\
!     _Jv_MutexLock (&rewrite_insn_mutex);	\
!     if (meth->thread_count <= 1)		\
!       {						\
! 	pc[-2].insn = INSN;			\
! 	pc[-1].SLOT = VALUE;			\
!       }						\
!     _Jv_MutexUnlock (&rewrite_insn_mutex);	\
!   }						\
!   while (0)

  #undef INTERP_REPORT_EXCEPTION
  #define INTERP_REPORT_EXCEPTION(Jthrowable) /* not needed when not debugging */
Index: java/lang/reflect/natVMProxy.cc
===================================================================
*** java/lang/reflect/natVMProxy.cc	(revision 139469)
--- java/lang/reflect/natVMProxy.cc	(working copy)
*************** run_proxy (ffi_cif *cif,
*** 350,356 ****
    // than about Proxy.class itself.  FRAME_DESC has a destructor so it
    // cleans up automatically when this proxy invocation returns.
    Thread *thread = Thread::currentThread();
!   _Jv_InterpFrame frame_desc (self->self, thread, proxyClass);

    // The method to invoke is saved in $Proxy0.m[method_index].
    // FIXME: We could somewhat improve efficiency by storing a pointer
--- 350,357 ----
    // than about Proxy.class itself.  FRAME_DESC has a destructor so it
    // cleans up automatically when this proxy invocation returns.
    Thread *thread = Thread::currentThread();
!   _Jv_InterpFrame frame_desc (self->self, thread, proxyClass,
! 			      NULL, frame_proxy);

    // The method to invoke is saved in $Proxy0.m[method_index].
    // FIXME: We could somewhat improve efficiency by storing a pointer
Index: defineclass.cc
===================================================================
*** defineclass.cc	(revision 139469)
--- defineclass.cc	(working copy)
*************** void _Jv_ClassReader::handleCodeAttribut
*** 1682,1688 ****
    method->prepared       = NULL;
    method->line_table_len = 0;
    method->line_table     = NULL;
!

    // grab the byte code!
    memcpy ((void*) method->bytecode (),
--- 1682,1690 ----
    method->prepared       = NULL;
    method->line_table_len = 0;
    method->line_table     = NULL;
! #ifdef DIRECT_THREADED
!   method->thread_count   = 0;
! #endif

    // grab the byte code!
    memcpy ((void*) method->bytecode (),