Merge lp:~gagern/bzr/bug396819-lazy_import-threadsafe into lp:bzr

[Martin von Gagern]

Make lazy imports (more) thread-safe

I know this still lacks a news entry, but apart from that, would you be willing to merge something along these lines to make lazy imports properly thread safe?

As I argued in bug #396819, I believe that you cannot have guaranteed tread-safe lazy imports without allowing the same replacer to resolve to the real object an arbitrary number of times. And you cannot avoid duplicate calls to the fatory (i.e. duplicate imports) unless you want to use locks.

The attached code avoids locks, as concurrent replacements should be rare and as duplicate imports should be harmless except for a slight cpu time penalty to detect it. It simplifies the replacer class by introducing a _resolve method which always returns the actual object.

As there are no longer any errors when the replace code is called repeatedly, we might miss the fact that the replacer object itself has been copied to some other name. To deal with this problem, the old error-raising behaviour will be restored for selftests, thus ensuring that the code is clean in that respect. Obviously, when the selftests reach the part where the thread safety of the replacer is tested, those checks have to be disabled again...

If you want any kind of beautification, name changes, or whatever, simply ask me or feel free to branch this yourself and apply changes as you see fit. I'm only proposing the general idea as a kind of proof of concept, and thus am most interested in your overall general opinion.

[Vincent Ladeuil (vila)]

Thanks for working on this !

This looks promising and I won't mind polishing it as patch pilot
(or helping you) but before digging I'd like some feedback from
jam and benji which have been involved recently.

[feedback] Overall, the approach sounds good. I'm not sure I'm
reading this correctly but it seems you've now made
ScopeReplacer._replace() the only place where races can occur. If
that's the case and we want to lock something, that should
probably be there.

[nit]

17 +
18 + disallow_proxying()

A bit naked ;) A comment explaining why it's done here (as early
as possible but no sooner) will be good.

[needsinfo]

218 - if event == 'line' and 'lazy_import.py' in filename:
219 - line = linecache.getline(filename, frame.f_lineno)
220 - # ...and the line of code is the one we're looking for...
221 - if 'del self._factory' in line:
<...>
228 + if (filename.endswith('lazy_import.py') and
229 + function_name == self.method_to_trace):

This looks nice and less hackish, but I thought you were relying
on the code you're replacing here in lp:~gagern/bzr/bug-702914 ?

I wouldn't mind merging these tests instead (or their moral equivalent).

review: Needs Information

[Martin von Gagern (gagern)]

On 01.09.2011 10:11, Vincent Ladeuil wrote:
> [feedback] Overall, the approach sounds good. I'm not sure I'm
> reading this correctly but it seems you've now made
> ScopeReplacer._replace() the only place where races can occur. If
> that's the case and we want to lock something, that should
> probably be there.

Depends on what race you're talking about.

A race resulting in double import will occur if the second thread reads
the _real_obj member before the first thread has written it. As the read
of _real_obj occurs in _resolve, that's involved in the race as well,
and a lock should encompass that whole code section, i.e. be aquired
before _real_obj is first accessed.

A race resulting in an UNDETECTED double replacement is restricted to
the very end of _replace, starting at the second read for _real_obj, the
one to the prev_obj local variable.

Reducing the chances for the second kind of race is the only reason for
the duplicate read of _real_obj. The assumption is that importing a
module might take considerable time, so a critical code section only
after the import represents a much shorter timespan.

> [nit]
>
> 17 +
> 18 + disallow_proxying()
>
> A bit naked ;) A comment explaining why it's done here (as early
> as possible but no sooner) will be good.

Guess you're right. To make things even cleaner, I could import the
lazy_import module instead of the function of the same name. That would
make this call use a qualified name, giving it more context. Will do
both soon.

> [needsinfo]
>
> 218 - if event == 'line' and 'lazy_import.py' in filename:
> 219 - line = linecache.getline(filename, frame.f_lineno)
> 220 - # ...and the line of code is the one we're looking for...
> 221 - if 'del self._factory' in line:
> <...>
> 228 + if (filename.endswith('lazy_import.py') and
> 229 + function_name == self.method_to_trace):
>
> This looks nice and less hackish, but I thought you were relying
> on the code you're replacing here in lp:~gagern/bzr/bug-702914 ?

This branch here supersedes that one, in my opinion. Notice that I never
requested that one to be merged. It was only intended as a proof that
the race problems hadn't been completely resolved yet. And the fact that
problems remained despite the original test cases shows another fact:
you cannot reasonably test for all possible races, but only those you
can think of. Thus the more people reviewing the code and thinking of
possible races, the more likely they won't miss one. The number of test
cases alone does little to increase confidence.

> I wouldn't mind merging these tests instead (or their moral equivalent).

There is no direct equivalent, as the lines of code mentioned no longer
exist in that fashion. I also came to believe that the scenarios
approach was bad, as it implied that all three kinds of test could be
matched by the same break point line regexp, which isn't necessarily
obvious.

The tests here are imo suitable to guard against a wide range of likely
races. The fact that the method name is an argument makes adding more
tests easy. So I'd rather prefer these tests here over the ones from
lp:~gagern/bzr/bug-702914 . I'd be happy to add three more tests for
_replace instead of ...

[Martin von Gagern (gagern)]

Ping?

[Jelmer Vernooij (jelmer)]

On Tue 06 Sep 2011 20:53:04 CEST, Martin von Gagern wrote:
> Ping?
John is sprinting this week so it might take a while longer before he
has time to look at this.

Cheers,

Jelmer

[Jelmer Vernooij (jelmer)]

review: Abstain

[Martin von Gagern (gagern)]

Second ping? Merge request has been out more than a month, please don't forget about it!

[Martin Packman (gz)]

Sorry we've not managed to get this reviewed MvG. Your analysis here and in the bug about the previous change seem correct to me, but I'm unconvinced about making further changes to lazy_import in this regard.

I can't offer useful suggestions for improving the branch, only complain about the state of the pitch:

* There's no way to disable lazy imports for things like loggerhead that care about threading not startup time.

* Telling whether a given lazy import is actually doing anything useful is far too hard.

  * It's not uncommon to see an object get imported then unconditionally used further down in the module.

  * Many parts of bzrlib are lazily imported somewhere, but end up always being required anyway.

  * The import tariff tests are nice, but very heavy compared to say, a lint style check.

* Parsing import statements out of strings is silly in many respects.

What I'd like to see would be a replacement with fewer features bzrlib could move to instead. I'm imagining it would:

* Use the import statement directly.

* Only works on module objects.

* Use a proxy that remains in place but gains attributes.

Since bzrlib.lazy_import was introduced we've gained a bunch of other lazy mechanisms which take over some of the work, but it's all very ad hoc.

[Martin von Gagern (gagern)]

Am 23.11.11 15:19, schrieb Martin Packman:
> Sorry we've not managed to get this reviewed MvG. Your analysis here and in the bug about the previous change seem correct to me, but I'm unconvinced about making further changes to lazy_import in this regard.

Currently, lazy_import is not merely ill designed, but actually breaking
stuff. So I believe that this proposal still should receive a proper
review, and the fix be committed. Unless there actually is code ready to
replace it, fixing it is better than not fixing it.

> I can't offer useful suggestions for improving the branch, only complain about the state of the pitch:
> * There's no way to disable lazy imports for things like loggerhead that care about threading not startup time.

Would be easy, but a different issue, to be implemented in a different
branch, preferrably on top of this one.

> * Telling whether a given lazy import is actually doing anything useful is far too hard.
> * It's not uncommon to see an object get imported then unconditionally used further down in the module.
> * Many parts of bzrlib are lazily imported somewhere, but end up always being required anyway.
> * The import tariff tests are nice, but very heavy compared to say, a lint style check.

tariff tests can deal with only a very limited number of scenarios to
check, but will by design also catch obscure paths leading to some
import. Lint-style checks could process a lot more code paths, detecting
lots of the stuff you describe above, but would be likely to miss some
more obscure constructs. So I'd consider them complementary.

> What I'd like to see would be a replacement with fewer features bzrlib could move to instead. I'm imagining it would:
>
> * Use the import statement directly.

I know that strange things are possible, but how would this work?
"from bzrlib.lazyly import foobar", with "lazily" not being a module but
instead an object working as a proxy factory? I guess that should be
possible, although I have some concerns about nested modules.

> * Only works on module objects.

That would surely make things a lot easier and cleaner.

> * Use a proxy that remains in place but gains attributes.

Not sure about performance here. I can imagine why a self-replacing
proxy would at least feel faster. It should be possible to do some
benchmarks on this.

[Martin Packman (gz)]

> Currently, lazy_import is not merely ill designed, but actually breaking
> stuff. So I believe that this proposal still should receive a proper
> review, and the fix be committed. Unless there actually is code ready to
> replace it, fixing it is better than not fixing it.

That's fair. Between me and Jelmer I'll see if we can manage a review here.

I'll leave the discussion of alternatives to a later merge proposal. :)

[Martin Packman (gz)]

Okay, Jelmer and I have discussed the general issue and the approach this branch takes. So, the code here is aimed at removing cases that result in exceptions, either usefully (in the case of multiply assigned proxies), or incorrectly (in the case of thread races). On that basis, the branch should land, and soon so it has some time on trunk to shake out any further issues.

The disallow_proxying mechanism for keeping the old testing for accidentally assigning a lazy object before it gets thunked I'm not convinced should be included with this change.

+ ScopeReplacer._last_duplicate_replacement = self

This is module-global state which is only used so the one call point of disallow_proxying() in selftest can retroactively raise (the most recent occurrence of) the error. Given that bzrlib.tests and test modules do not lazily import the will have already pulled in many things (varying if -s is used), this will only test one real import path.

For this branch, I suggest pulling out that code and living with the reduced coverage of assignment accidents, and just using `self.overrideAttr(ScopeReplacer, "_should_proxy", False)` for tests.

To get coverage for import issues again, using a debug flag to set the _should_proxy value and something similar to the import tarrif tests would work, and should be done in a future branch.

+ The loosing caller used to see an exception (bugs 396819 and 702914).
...
+ in order win the race, setting up the original caller to loose.

When changing this docstring it'd be nice to fix the spelling of 'lose'. :)

review: Needs Fixing

=== modified file 'bzrlib/builtins.py'
--- bzrlib/builtins.py	2011-08-31 15:25:11 +0000
+++ bzrlib/builtins.py	2011-09-01 20:49:31 +0000
@@ -18,8 +18,8 @@
 
 import os
 
-from bzrlib.lazy_import import lazy_import
-lazy_import(globals(), """
+from bzrlib import lazy_import
+lazy_import.lazy_import(globals(), """
 import cStringIO
 import sys
 import time
@@ -3800,6 +3800,15 @@
             randomize=None, exclude=None, strict=False,
             load_list=None, debugflag=None, starting_with=None, subunit=False,
             parallel=None, lsprof_tests=False):
+
+        # During selftest, disallow proxying, as it can cause severe
+        # performance penalties and is only needed for thread
+        # safety. The selftest command is assumed to not use threads
+        # too heavily. The call should be as early as possible, as
+        # error reporting for past duplicate imports won't have useful
+        # backtraces.
+        lazy_import.disallow_proxying()
+
         from bzrlib import tests
 
         if testspecs_list is not None:

=== modified file 'bzrlib/lazy_import.py'
--- bzrlib/lazy_import.py	2011-08-19 18:02:37 +0000
+++ bzrlib/lazy_import.py	2011-09-01 20:49:31 +0000
@@ -51,10 +51,15 @@
 
     __slots__ = ('_scope', '_factory', '_name', '_real_obj')
 
-    # Setting this to True will allow you to do x = y, and still access members
-    # from both variables. This should not normally be enabled, but is useful
-    # when building documentation.
-    _should_proxy = False
+    # This will record the last duplicate replacement. It is used
+    # during selftests where duplicate replacements are forbidden.
+    _last_duplicate_replacement = None
+
+    # If you to do x = y, setting this to False will disallow access to
+    # members from the second variable (i.e. x). This should normally
+    # be enabled for reasons of thread safety and documentation, but
+    # will be disabled during the selftest command to check for abuse.
+    _should_proxy = True
 
     def __init__(self, scope, factory, name):
         """Create a temporary object in the specified scope.
@@ -71,74 +76,83 @@
         object.__setattr__(self, '_real_obj', None)
         scope[name] = self
 
+    def _resolve(self):
+        """Return the real object for which this is a placeholder"""
+        real_obj = object.__getattribute__(self, '_real_obj')
+        if real_obj is not None:
+            object.__getattribute__(self, '_duplicate_replacement')()
+            return real_obj
+        replace = object.__getattribute__(self, '_replace')
+        return replace()
+
     def _replace(self):
         """Actually replace self with other in the given scope"""
         name = object.__getattribute__(self, '_name')
-        try:
-            factory = object.__getattribute__(self, '_factory')
-            scope = object.__getattribute__(self, '_scope')
-        except AttributeError, e:
-            # Because ScopeReplacer objects only replace a single
-            # item, passing them to another variable before they are
-            # replaced would cause them to keep getting replaced
-            # (only they are replacing the wrong variable). So we
-            # make it forbidden, and try to give a good error.
-            raise errors.IllegalUseOfScopeReplacer(
-                name, msg="Object already cleaned up, did you assign it"
-                          " to another variable?",
-                extra=e)
+        factory = object.__getattribute__(self, '_factory')
+        scope = object.__getattribute__(self, '_scope')
         obj = factory(self, scope, name)
         if obj is self:
             raise errors.IllegalUseOfScopeReplacer(name, msg="Object tried"
                 " to replace itself, check it's not using its own scope.")
-        if ScopeReplacer._should_proxy:
+
+        # The same object might be replaced repeatedly due to a race
+        # condition. We want to detect this fact for possible reporting.
+        prev_obj = object.__getattribute__(self, '_real_obj')
+        if prev_obj is None:
             object.__setattr__(self, '_real_obj', obj)
-        scope[name] = obj
+            scope[name] = obj
+        else:
+            # This indicates a duplicate replacement and should never
+            # happen except under rare race conditions. See lp:396819.
+            # Note: the above check is not thread-safe, so there is a
+            # slight chance that concurrent duplicate replacements are
+            # missed. Not worth the cost of a lock, though.
+            object.__getattribute__(self, '_duplicate_replacement')()
         return obj
 
-    def _cleanup(self):
-        """Stop holding on to all the extra stuff"""
-        try:
-            del self._factory
-        except AttributeError:
-            # Oops, we just lost a race with another caller of _cleanup.  Just
-            # ignore it.
-            pass
-
-        try:
-            del self._scope
-        except AttributeError:
-            # Another race loss.  See above.
-            pass
-
-        # We keep _name, so that we can report errors
-        # del self._name
-
     def __getattribute__(self, attr):
-        obj = object.__getattribute__(self, '_real_obj')
-        if obj is None:
-            _replace = object.__getattribute__(self, '_replace')
-            obj = _replace()
-            _cleanup = object.__getattribute__(self, '_cleanup')
-            _cleanup()
+        obj = object.__getattribute__(self, '_resolve')()
         return getattr(obj, attr)
 
     def __setattr__(self, attr, value):
-        obj = object.__getattribute__(self, '_real_obj')
-        if obj is None:
-            _replace = object.__getattribute__(self, '_replace')
-            obj = _replace()
-            _cleanup = object.__getattribute__(self, '_cleanup')
-            _cleanup()
+        obj = object.__getattribute__(self, '_resolve')()
         return setattr(obj, attr, value)
 
     def __call__(self, *args, **kwargs):
-        _replace = object.__getattribute__(self, '_replace')
-        obj = _replace()
-        _cleanup = object.__getattribute__(self, '_cleanup')
-        _cleanup()
+        obj = object.__getattribute__(self, '_resolve')()
         return obj(*args, **kwargs)
 
+    def _duplicate_replacement(self):
+        if object.__getattribute__(self, '_should_proxy'):
+            # Do not report now, but remember in case we want to
+            # report this later.
+            ScopeReplacer._last_duplicate_replacement = self
+        else:
+            name = object.__getattribute__(self, '_name')
+            raise errors.IllegalUseOfScopeReplacer(
+                name, msg="Object already replaced, did you assign it"
+                          " to another variable?")
+
+
+def disallow_proxying():
+    """Disallow lazily imported modules to be used as proxies.
+
+    Calling this function might cause problems with concurrent imports
+    in multithreaded environments, but will help detecting wasteful
+    indirection, so it should be called when executing unit tests.
+
+    Calling this function will even act for the most recent past case
+    of proxying, reporting the name of the proxied object. So a
+    successful call to this function will ensure that scope replacer
+    objects were never misused as proxies in the past and will never
+    be misused in the future."""
+
+    ScopeReplacer._should_proxy = False
+    last = ScopeReplacer._last_duplicate_replacement
+    if last is not None:
+        ScopeReplacer._last_duplicate_replacement = None
+        object.__getattribute__(last, '_duplicate_replacement')()
+
 
 class ImportReplacer(ScopeReplacer):
     """This is designed to replace only a portion of an import list.

=== modified file 'bzrlib/tests/test_lazy_import.py'
--- bzrlib/tests/test_lazy_import.py	2011-08-19 18:19:31 +0000
+++ bzrlib/tests/test_lazy_import.py	2011-09-01 20:49:31 +0000
@@ -375,7 +375,6 @@
                           ('foo', 2),
                           ('foo', 3),
                           ('__getattribute__', 'foo'),
-                          '_replace',
                          ], actions)
 
     def test_enable_proxying(self):
@@ -1171,51 +1170,62 @@
                          ], self.actions)
 
 
+class ProxyingReplacer(lazy_import.ScopeReplacer):
+    """Replacer class that will do proxying even during selftest.
+    
+    This is useful to check that the lazy import code is sufficiently
+    thread-safe.
+    """
+
+    _should_proxy = True
+
+
 class TestScopeReplacerReentrance(TestCase):
     """The ScopeReplacer should be reentrant.
 
     Invoking a replacer while an invocation was already on-going leads to a
-    race to see which invocation will be the first to delete the _factory and
-    _scope attributes.  The loosing caller used to see AttributeErrors (bug
-    702914).
+    race to see which invocation will be the first to call _replace.
+    The loosing caller used to see an exception (bugs 396819 and 702914).
 
-    These tests set up a tracer that stops at the moment just before one of
-    the attributes is being deleted and starts another call to the
-    functionality in question (__call__, __getattribute__, __setattr_) in
-    order win the race, setting up the originall caller to loose.
+    These tests set up a tracer that stops at a suitable moment (upon
+    entry of a specified method) and starts another call to the
+    functionality in question (__call__, __getattribute__, __setattr_)
+    in order win the race, setting up the original caller to loose.
     """
 
     def tracer(self, frame, event, arg):
+        if event != 'call':
+            return self.tracer
         # Grab the name of the file that contains the code being executed.
-        filename = frame.f_globals["__file__"]
+        code = frame.f_code
+        filename = code.co_filename
         # Convert ".pyc" and ".pyo" file names to their ".py" equivalent.
         filename = re.sub(r'\.py[co]$', '.py', filename)
+        function_name = code.co_name
         # If we're executing a line of code from the right module...
-        if event == 'line' and 'lazy_import.py' in filename:
-            line = linecache.getline(filename, frame.f_lineno)
-            # ...and the line of code is the one we're looking for...
-            if 'del self._factory' in line:
-                # We don't need to trace any more.
-                sys.settrace(None)
-                # Run another racer.  This one will "win" the race, deleting
-                # the attributes.  When the first racer resumes it will loose
-                # the race, generating an AttributeError.
-                self.racer()
+        if (filename.endswith('lazy_import.py') and
+            function_name == self.method_to_trace):
+            # We don't need to trace any more.
+            sys.settrace(None)
+            # Run another racer.  This one will "win" the race.
+            self.racer()
         return self.tracer
 
-    def run_race(self, racer):
+    def run_race(self, racer, method_to_trace='_resolve'):
+        lazy_import.ScopeReplacer._should_proxy = True
         self.racer = racer
+        self.method_to_trace = method_to_trace
         sys.settrace(self.tracer)
-        self.racer() # Should not raise an AttributeError
-        # Make sure the tracer actually found the code it was looking for.  If
-        # not, maybe the code was refactored in such a way that these tests
-        # aren't needed any more.
+        self.racer() # Should not raise any exception
+        # Make sure the tracer actually found the code it was
+        # looking for.  If not, maybe the code was refactored in
+        # such a way that these tests aren't needed any more.
         self.assertEqual(None, sys.gettrace())
 
     def test_call(self):
         def factory(*args):
             return factory
-        replacer = lazy_import.ScopeReplacer({}, factory, 'name')
+        replacer = ProxyingReplacer({}, factory, 'name')
         self.run_race(replacer)
 
     def test_setattr(self):
@@ -1225,7 +1235,7 @@
         def factory(*args):
             return Replaced()
 
-        replacer = lazy_import.ScopeReplacer({}, factory, 'name')
+        replacer = ProxyingReplacer({}, factory, 'name')
 
         def racer():
             replacer.foo = 42
@@ -1239,7 +1249,7 @@
         def factory(*args):
             return Replaced()
 
-        replacer = lazy_import.ScopeReplacer({}, factory, 'name')
+        replacer = ProxyingReplacer({}, factory, 'name')
 
         def racer():
             replacer.foo