Re: RFA: Objective-C patch fixing libobjc/9969

[Nicola Pero <nicola at brainstorm dot co dot uk>]

> >Ok to apply (tested, no regressions, and gnustep-base seems to be still
> >working fine with this change) ?
> >
> >Wed May 14 11:25:41 2003  Nicola Pero  <n.pero@mi.flashnet.it>
> >
> >        libobjc/9969
> >        * sendmsg.c (get_imp): Fixed threading problem which might cause
> >        in extremely rare cases to return the forward method
> >        implementation instead of the actual method when the dispatch
> >        table was being installed by a concurrent thread.  Fixed threading
> >        problem which might cause in extremely rare cases the dispatch
> >        table to be installed twice - with a small memory leak - in
> >        similar situations.  This change adds some overhead to messaging
> >        whenever a forward implementation is returned.
> >        (__objc_responds_to): Similar fixes.
> >        (objc_msg_lookup): Similar fixes.
> >
> This just seems like it lowers the odds of messing up without
> really solving the problem.  The rule of thumb is that a
> concurrent thread can kick in between any pair of instructions,
> and the "if (class->dtable == __objc_uninstalled_dtable)" will
> be several instructions usually. (That's why atomic test-and-set
> instructions are so important.)
> 
> Shouldn't the runtime mutex be locking out dispatch table installs
> by other threads?

Thanks - yes, it's locking (a double-check locking pattern is used for
efficiency) - just for reference, here is the complete (patched) function
-


/* Given a class and selector, return the selector's implementation.  */
__inline__
IMP
get_imp (Class class, SEL sel)
{
  void *res = sarray_get_safe (class->dtable, (size_t) sel->sel_id);
  if (res == 0)
    {
      /* Not a valid method */
      if (class->dtable == __objc_uninstalled_dtable)
	{
	  /* The dispatch table needs to be installed. */
	  objc_mutex_lock (__objc_runtime_mutex);

	  /* Check __objc_uninstalled_dtable again in case another
	     thread installed the dtable while we were waiting for the
	     lock to be released.  */
	  if (class->dtable == __objc_uninstalled_dtable)
	    {
	      __objc_install_dispatch_table_for_class (class);
	    }
	  objc_mutex_unlock (__objc_runtime_mutex);
	  /* Call ourselves with the installed dispatch table
	     and get the real method */
	  res = get_imp (class, sel);
	}
      else
	{
	  /* The dispatch table has been installed so the
	     method just doesn't exist for the class.
	     Return the forwarding implementation. */

	  /* First check again if the method exists in case another
	     thread has installed the dtable just between we checked
	     res == 0 and class->dtable == __objc_uninstalled_dtable.
	  */
	  res = sarray_get_safe (class->dtable, (size_t) sel->sel_id);
	  if (res == 0)
	    {
	      res = __objc_get_forward_imp (sel);
	    }
	}
    }
  return res;
}


The class->dtable is basically protected using a Double-Checked Locking
Pattern (I'm sure you're familiar with it - if not, you find discussions
everywhere on the web).  It's a standard C pattern for protecting
variables to be initialized only once, and guaranteeing thread-safe
initialization, but still not requiring acquiring a lock whenever the
check is done - which would be prohibitively expensive since this is the
messaging function!

The current code doesn't use the double-check (it checks only once), so
using double-checked locking is an improvement :-)

I think that was your main question :-) but the other double-check might 
need explaining too - it can be explained as follows:

the "straightforward/naive/thread-safe" implementation of the messaging
function would be as follows:

 - first check that the dispatch table is installed, and if not, install 
it; this done using double-checked locking.

 - once the dispatch table is installed, look up the selector, and return
the implementation (or the forward one if the implementation is not
found).

The reason that the function is not written in this way is (IMO) to get
more speed for the standard case.

To squeeze out a little bit more speed for the standard case (that the
dispatch table is already installed, and the method is in the dispatch
table) at the expense of the speed of the more rare cases (that the
dispatch table is not installed, or the method is not in the dispatch
table), the function has been modified to first brutely try to get the
method from the dispatch table regardless.  In the standard case, that
retrieves the method immediately, and the function can return immediately;  
it saves the check that the dispatch table is installed in the standard
case.

If the method is not found in the dispatch table, then the "naive"  
implementation is used: the dispatch table is installed if not there, and
then the selector is looked up; if not found, the forward implementation
is returned.


I'm willing to change the comments / rearrange the code (maybe add a
recursive call to get_imp()  also in the second branch ?) to make the
logic behind it more clear.

Let me know if you think a second modified patch would be appropriate.