Merge lp:~weyrick/bzr/720853-max-recursion-depth into lp:bzr

[Shannon Weyrick]

raise BadIndexKey rather than crashing if the key is unreasonably long

Fix recursion problem by explicitly checking for a key that is too big to fit in a page.

[John A Meinel (jameinel)]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/04/2011 05:41 PM, Shannon Weyrick wrote:
> Shannon Weyrick has proposed merging
> lp:~weyrick/bzr/720853-max-recursion-depth into lp:bzr.
>
> Requested reviews: Robert Collins (lifeless) Related bugs: Bug
> #720853 in Bazaar: "bzr crashed with RuntimeError in normpath():
> maximum recursion depth exceeded while calling a Python object"
> https://bugs.launchpad.net/bzr/+bug/720853
>
> For more details, see:
> https://code.launchpad.net/~weyrick/bzr/720853-max-recursion-depth/+merge/81297
>
> Fix recursion problem by explicitly checking for a key that is too
> big to fit in a page. In that case, the key is skipped.

Silently discarding user data is not a good way to go. I can see
teaching something like bzr-search handling an error that indicates it
can ignore the request, but we really don't want to silently skip data
that cannot be recorded.

 review: needsfixing

John
=:->

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk60SBQACgkQJdeBCYSNAAPz9gCfd4Hom4IBhhiNrw25Gw+SF02e
K5sAn3rstL/S7m+9yJXK7688K58VIM5s
=XxxO
-----END PGP SIGNATURE-----

review: Needs Fixing

[Martin Packman (gz)]

Thanks for working on this!

Do you need any help working out how to write a test that hits this code?

[Shannon Weyrick (weyrick)]

I've added a test, please review.

[Martin Pool (mbp)]

that seems to make sense to me.

i would kind of like a second review from john or robert.

review: Approve

[Martin Pool (mbp)]

the other question is, what will happen to bzr-search when it gets BadIndexKey from this? Does the program abort, but with a cleaner message, or does it cope, and if so how?

[Shannon Weyrick (weyrick)]

Yes so this patch is just the bzrlib side. bzr-search would ideally handle this raised exception better. Currently, yes, it aborts with a cleaner message, not to mention much faster than without this patch.

[Martin Pool (mbp)]

robert agreed on irc

[Martin Pool (mbp)]

sent to pqm by email

=== modified file 'bzrlib/btree_index.py'
--- bzrlib/btree_index.py	2011-08-19 22:34:02 +0000
+++ bzrlib/btree_index.py	2011-11-11 01:10:29 +0000
@@ -320,6 +320,12 @@
                 optimize_for_size=self._optimize_for_size)
             rows[-1].writer.write(_LEAF_FLAG)
         if rows[-1].writer.write(line):
+            # if we failed to write, despite having an empty page to write to,
+            # then line is too big. len is 2 here because we've already written
+            # some header. raising the error avoids infinite recursion searching
+            # for a suitably large page that will not be found.
+            if rows[-1].writer.bytes_out_len <= 2:
+                raise errors.BadIndexKey(string_key)
             # this key did not fit in the node:
             rows[-1].finish_node()
             key_line = string_key + "\n"

=== modified file 'bzrlib/tests/test_btree_index.py'
--- bzrlib/tests/test_btree_index.py	2011-08-19 22:34:02 +0000
+++ bzrlib/tests/test_btree_index.py	2011-11-11 01:10:29 +0000
@@ -831,6 +831,14 @@
             btree_index.BTreeGraphIndex(t1, 'index', 10) !=
             btree_index.BTreeGraphIndex(t1, 'index', 20))
 
+    def test_key_too_big(self):
+        # the size that matters here is the _compressed_ size of the key, so we can't
+        # do a simple character repeat.
+        bigKey = ''.join(map(repr, xrange(btree_index._PAGE_SIZE)))
+        self.assertRaises(errors.BadIndexKey,
+                          self.make_index,
+                          nodes=[((bigKey,), 'value', ())])
+        
     def test_iter_all_only_root_no_size(self):
         self.make_index(nodes=[(('key',), 'value', ())])
         t = transport.get_transport_from_url('trace+' + self.get_url(''))

=== modified file 'doc/en/release-notes/bzr-2.5.txt'
--- doc/en/release-notes/bzr-2.5.txt	2011-11-10 13:56:18 +0000
+++ doc/en/release-notes/bzr-2.5.txt	2011-11-11 01:10:29 +0000
@@ -511,6 +511,9 @@
   operations that use it, like merge, can now create trees without a root.
   (Aaron Bentley)
 
+* Raise BadIndexKey exception in btree_index when a key is too large, fixing 
+  an infinite recursion issue. (Shannon Weyrick, #720853)
+
 Documentation
 *************