Merge lp:~gz/bzr/create_delta_index_memoryerror_633336 into lp:bzr

[Martin Packman]

Adapt delta_index functions in diff-delta.c to always return a struct pointer on success, even if it's not a newly allocated one. This allows the callers in _groupcompress_pyx to treat NULL returns as a malloc failure and raise MemoryError. Some parameter preconditions are also asserted in the pyrex source just to make sure. This won't help people who are running out of memory during groupcompress, but at least they should know about it.

I'd like to test this, but short of forking and messing around with rlimit I don't have any good ideas.

[John A Meinel (jameinel)]

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

On 3/4/2011 9:17 PM, Martin [gz] wrote:
> Martin [gz] has proposed merging lp:~gz/bzr/create_delta_index_memoryerror_633336 into lp:bzr.
>
> Requested reviews:
> bzr-core (bzr-core)
> Related bugs:
> #633336 AssertionError in bzrlib._groupcompress_pyx.DeltaIndex._populate_first_index
> https://bugs.launchpad.net/bugs/633336
>
> For more details, see:
> https://code.launchpad.net/~gz/bzr/create_delta_index_memoryerror_633336/+merge/52251
>
> Adapt delta_index functions in diff-delta.c to always return a struct pointer on success, even if it's not a newly allocated one. This allows the callers in _groupcompress_pyx to treat NULL returns as a malloc failure and raise MemoryError. Some parameter preconditions are also asserted in the pyrex source just to make sure. This won't help people who are running out of memory during groupcompress, but at least they should know about it.
>
> I'd like to test this, but short of forking and messing around with rlimit I don't have any good ideas.

I'd like to avoid asserts like this:
+ assert src.buf and src.size and self._index

Specifically, if it trips, the user gets back:

 AssertionError

With no context, and a traceback, which points to a line. But on that
line, all we know is that *one* of those three cases failed.

If you are comfortable with it, remove it entirely. Alt 1 is to move it
into 3 lines, alt 2 is to move it into:

if not src.buf:
  raise AssertionError("src.buf is None, but should be valid")

etc.

This one the same thing:
+ assert src.size and src.buf

&cp_size)
                 if (cp_off + cp_size < cp_size or
- - cp_off + cp_size > source_size or
- - cp_size > size):
+ cp_off + cp_size > <unsigned int>source_size or
+ cp_size > <unsigned int>size):
                     failed = 1
                     break
                 memcpy(out, source + cp_off, cp_size)
^- I assume this is more about silencing compiler warnings. I think
there was some question about the 'right' fix, but source_size should
never be negative, and neither should size, so this seems reasonable to me.

- - * Rewritten for GIT by Nicolas Pitre <email address hidden>, (C) 2005-2007
+ * Rewritten for GIT by Nicolas Pitre <email address hidden>, (C) 2005-2007

^- Interesting, haven't seen anything about that before...

- - if (old) {
- - old->last_src = src;
- - }

^- Is last_src still getting set in another code path? I don't remember
exactly where it mattered, but it was important at one time.

+ assert(old_index != NULL);

+ /* GZ 2011-03-04: What is 'something' exactly? If this an unrecoverable
+ error perhaps it should be an assert? */
     if (data != top) {
         /* Something was wrong with this delta */
         free(entries);
- - return NULL;
+ return old_index;
     }

^- We need to die here. Not carry on as if everything went ok. It means
that the delta was incorrectly formatted. Something like having an
insert of 10 bytes, but only 8 bytes available, etc.

Unfortunately, we only have 1 bit of information to hand...

[Martin Packman (gz)]

> I'd like to avoid asserts like this:
> + assert src.buf and src.size and self._index

Yup. I added these so it was explicit about how the previous ways of tripping the assert were segmented into malloc problems vs. something else.

> If you are comfortable with it, remove it entirely. Alt 1 is to move it
> into 3 lines, alt 2 is to move it into:
>
> if not src.buf:
> raise AssertionError("src.buf is None, but should be valid")

Well, I was trying to get out of reading and understanding all of groupcompress by shifting that decision off onto you. :)

I think if these conditions could be hit from environmental circumstances, like bad bytes on the disk or running out of memory, they should be changed to a pretty python exception like your example. If it's just down to the code, it should simply make sure the preconditions are true, and bare/no assert are fine. I will try and work out which applies if you don't know either. :)

> + cp_off + cp_size > <unsigned int>source_size or
> + cp_size > <unsigned int>size):
> failed = 1
> break
> memcpy(out, source + cp_off, cp_size)
> ^- I assume this is more about silencing compiler warnings. I think
> there was some question about the 'right' fix, but source_size should
> never be negative, and neither should size, so this seems reasonable to me.

Yeah, that was just a drive-by implict->explict cast change I noticed while compiling. Rationalising the types used would be better, but there are several functions involved so I didn't launch on it.

> - - * Rewritten for GIT by Nicolas Pitre <email address hidden>, (C) 2005-2007
> + * Rewritten for GIT by Nicolas Pitre <email address hidden>, (C) 2005-2007
>
> ^- Interesting, haven't seen anything about that before...

Just noticed it when looking at <http://git.kernel.org/?p=git/git.git;a=history;f=diff-delta.c> and being confused at how different their version of the file is.

> - - if (old) {
> - - old->last_src = src;
> - - }
>
> ^- Is last_src still getting set in another code path? I don't remember
> exactly where it mattered, but it was important at one time.

Sorry yes, not enough context in the diff to see that one. Changing to return 'old' if it's being reused rather than NULL from pack_delta_index means the later `index->last_src = src;` line covers this:

- if (old) {
- old->last_src = src;
- }
     index = pack_delta_index(hash, hsize, total_num_entries, old);
     free(hash);
     if (!index) {
         return NULL;
     }
     index->last_src = src;

> + /* GZ 2011-03-04: What is 'something' exactly? If this an unrecoverable
> + error perhaps it should be an assert? */
> if (data != top) {
> /* Something was wrong with this delta */
> free(entries);
> - - return NULL;
> + return old_index;
> }
>
> ^- We need to die here. Not carry on as if everything went ok. It means
> that the delta was incorrectly formatted. Something like having an
> insert of 10 bytes, but only 8 bytes available, etc.
>
> Unfortunately, we only have 1 bit of information to hand back ...

[Martin Packman (gz)]

So, the better way of handling 'data' being something bogus would be to split out that logic in create_delta_index_from_delta to a separate function that can then have a richer interface.

[John A Meinel (jameinel)]

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

...
>> + /* GZ 2011-03-04: What is 'something' exactly? If this an unrecoverable
>> + error perhaps it should be an assert? */
>> if (data != top) {
>> /* Something was wrong with this delta */
>> free(entries);
>> - - return NULL;
>> + return old_index;
>> }
>>
>> ^- We need to die here. Not carry on as if everything went ok. It means
>> that the delta was incorrectly formatted. Something like having an
>> insert of 10 bytes, but only 8 bytes available, etc.
>>
>> Unfortunately, we only have 1 bit of information to hand back to the
>> caller at this point. NULL or new index. But really, this change is not
>> sufficient. And assert in C code will probably cause SIGABRT, or worse,
>> is a no-op because of -O3 compile-time flags. Neither is great for this
>> condition. Thoughts?
>
> Is that the sort of thing that could happen from reading corrupted data from disk, or only in case of programming error? If the latter, I think it should just be an assert. Otherwise yes, we have the problem of packing multiple return states into one pointer.
>

Well, wherever bad data comes from. But yes, bad data, and not
programmer error causes this failure.

>> Thoughts on how to send back a more tasteful error? Otherwise I like the
>> idea, but this one in particular is a bit of an ugly side-case.
>
> Well, I was considering doing a int/ptr union before the idea of returning the old index dawned. 0x00000001 is just as unlikely as 0x00000000 to be a valid object. That's a much uglier way of doing business though.

I'm sure you could get away with a few states like this, but I agree it
isn't very tasteful. The other one is -1 (0xFFFFFFFF).

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk1yCroACgkQJdeBCYSNAANFfQCcCUkMhmU8mED4GuD1QQWs4Akk
9dYAoLouLtrNrG8ivbZRpf1FICKRWwU6
=hYWv
-----END PGP SIGNATURE-----

=== modified file 'bzrlib/_groupcompress_pyx.pyx'
--- bzrlib/_groupcompress_pyx.pyx	2010-08-02 17:08:29 +0000
+++ bzrlib/_groupcompress_pyx.pyx	2011-03-04 20:17:15 +0000
@@ -164,10 +164,13 @@
         src.buf = c_delta
         src.size = c_delta_size
         src.agg_offset = self._source_offset + unadded_bytes
+        assert src.buf and src.size and self._index
         with nogil:
             index = create_delta_index_from_delta(src, self._index)
+        if index == NULL:
+            raise MemoryError
         self._source_offset = src.agg_offset + src.size
-        if index != NULL:
+        if index != self._index:
             free_delta_index(self._index)
             self._index = index
 
@@ -205,9 +208,12 @@
         self._source_offset = src.agg_offset + src.size
         # We delay creating the index on the first insert
         if source_location != 0:
+            assert src.size and src.buf
             with nogil:
                 index = create_delta_index(src, self._index)
-            if index != NULL:
+            if index == NULL:
+                raise MemoryError
+            if index != self._index:
                 free_delta_index(self._index)
                 self._index = index
 
@@ -218,10 +224,12 @@
                 ' called when we have a single source and no index yet')
 
         # We know that self._index is already NULL, so whatever
-        # create_delta_index returns is fine
+        # create_delta_index returns is fine unless there's a malloc failure
+        assert self._source_infos[0].size and self._source_infos[0].buf
         with nogil:
             self._index = create_delta_index(&self._source_infos[0], NULL)
-        assert self._index != NULL
+        if self._index == NULL:
+            raise MemoryError
 
     cdef _expand_sources(self):
         raise RuntimeError('if we move self._source_infos, then we need to'
@@ -369,8 +377,8 @@
                 # Copy instruction
                 data = _decode_copy_instruction(data, cmd, &cp_off, &cp_size)
                 if (cp_off + cp_size < cp_size or
-                    cp_off + cp_size > source_size or
-                    cp_size > size):
+                    cp_off + cp_size > <unsigned int>source_size or
+                    cp_size > <unsigned int>size):
                     failed = 1
                     break
                 memcpy(out, source + cp_off, cp_size)

=== modified file 'bzrlib/diff-delta.c'
--- bzrlib/diff-delta.c	2010-08-02 16:35:11 +0000
+++ bzrlib/diff-delta.c	2011-03-04 20:17:15 +0000
@@ -4,7 +4,7 @@
  * This code was greatly inspired by parts of LibXDiff from Davide Libenzi
  * http://www.xmailserver.org/xdiff-lib.html
  *
- * Rewritten for GIT by Nicolas Pitre <[e-mail]>, (C) 2005-2007
+ * Rewritten for GIT by Nicolas Pitre <[e-mail]>, (C) 2005-2007
  * Adapted for Bazaar by John Arbash Meinel <[e-mail]> (C) 2009
  *
  * This program is free software; you can redistribute it and/or modify
@@ -280,8 +280,11 @@
         if (fit_in_old) {
             // fprintf(stderr, "Fit all %d entries into old index\n",
             //                 copied_count);
-            /* No need to allocate a new buffer */
-            return NULL;
+            /*
+             * No need to allocate a new buffer, but return old_index ptr so
+             * callers can distinguish this from an OOM failure.
+             */
+            return old_index;
         } else {
             // fprintf(stderr, "Fit only %d entries into old index,"
             //                 " reallocating\n", copied_count);
@@ -450,9 +453,6 @@
     total_num_entries = limit_hash_buckets(hash, hash_count, hsize,
                                            total_num_entries);
     free(hash_count);
-    if (old) {
-        old->last_src = src;
-    }
     index = pack_delta_index(hash, hsize, total_num_entries, old);
     free(hash);
     if (!index) {
@@ -690,6 +690,7 @@
     struct delta_index *new_index;
     struct index_entry *entry, *entries;
 
+    assert(old_index != NULL);
     if (!src->buf || !src->size)
         return NULL;
     buffer = src->buf;
@@ -773,17 +774,18 @@
             break;
         }
     }
+    /* GZ 2011-03-04: What is 'something' exactly? If this an unrecoverable
+                      error perhaps it should be an assert? */
     if (data != top) {
         /* Something was wrong with this delta */
         free(entries);
-        return NULL;
+        return old_index;
     }
     if (num_entries == 0) {
         /** Nothing to index **/
         free(entries);
-        return NULL;
+        return old_index;
     }
-    assert(old_index != NULL);
     old_index->last_src = src;
     /* See if we can fill in these values into the holes in the array */
     entry = entries;
@@ -841,7 +843,7 @@
         new_index = create_index_from_old_and_new_entries(old_index,
             entry, num_entries);
     } else {
-        new_index = NULL;
+        new_index = old_index;
         // fprintf(stderr, "inserted %d without resizing\n", num_inserted);
     }
     free(entries);