# [PATCH] fix diff-delta bad memory access 7 messages from 2006-05-10 to 2006-05-10. Participants: Nicolas Pitre, Linus Torvalds. Thread: https://gitlist.dev/t/4117 ## Nicolas Pitre, 2006-05-10 16:26 Subject: [PATCH] fix diff-delta bad memory access Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0605101216360.24505%40localhost.localdomain ``` It cannot be assumed that the given buffer will never be moved when shrinking the allocated memory size with realloc(). So let's ignore that optimization for now. This patch makes Electric Fence happy on Linux. Signed-off-by: Nicolas Pitre --- I can't tell if that fixes it on BSD and Cygwin though. diff --git a/Makefile b/Makefile diff --git a/diff-delta.c b/diff-delta.c index c618875..25a798d 100644 --- a/diff-delta.c +++ b/diff-delta.c @@ -199,7 +199,6 @@ struct delta_index * create_delta_index( entry->next = hash[i]; hash[i] = entry++; hash_count[i]++; - entries--; } } @@ -230,10 +229,6 @@ struct delta_index * create_delta_index( } free(hash_count); - /* If we didn't use all hash entries, free the unused memory. */ - if (entries) - index = realloc(index, memsize - entries * sizeof(*entry)); - return index; } ``` ## Linus Torvalds, 2006-05-10 17:00 Subject: Re: [PATCH] fix diff-delta bad memory access Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0605100953090.3718%40g5.osdl.org In-Reply-To: ``` On Wed, 10 May 2006, Nicolas Pitre wrote: > > It cannot be assumed that the given buffer will never be moved when > shrinking the allocated memory size with realloc(). So let's ignore > that optimization for now. Yeah, that was totally bogus. It would re-allocate _part_ of an allocation, but that allocation contained not just the index, but all the hashes and the hash entries too! This has nothing to do with moving a buffer - it has everything to do with the fact that you shrunk a buffer that still contained all the other buffers: you shrunk the "mem" allocation to fit just the first part of it, and entirely ignored the "hash" and "entry" parts of it. Btw, I think that whole "allocate everything in one allocation" thing is potentially bogus even the way it is now, if the alignment constraints of "index", "hash" and "entry" are different. When you do .. index = mem; mem = index + 1; hash = mem; mem = hash + hsize; entry = mem; .. it's perfectly fine for "index", but "hash" and "entry" end up having alignments that depend on the size/alignment of "index" (and for "entry" on "hash"). So if their alignment requirements are different, you're basically screwed. It may work in practice (maybe they all align on pointer boundaries), but it's damn scary. You should re-consider, or at least make that code be a lot safer (like actually taking alignment into consideration, both for total size and for the offset calculations). That could be done by using unions or something. Linus ``` ## Linus Torvalds, 2006-05-10 17:18 Subject: Re: [PATCH] fix diff-delta bad memory access Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0605101015060.3718%40g5.osdl.org In-Reply-To: ``` On Wed, 10 May 2006, Linus Torvalds wrote: > > Yeah, that was totally bogus. It would re-allocate _part_ of an > allocation, but that allocation contained not just the index, but all the > hashes and the hash entries too! Actually, no, you got that part right. Mea culpa. It really only ended up being a problem when the area was moved, since the pointers into that area weren't updated. The alignment issue is real, but looking at the different structures, they'll all have pointers that end up being the real (and only) alignment constraint, so as a result, on any reasonable machine they all have the same alignment and things are fine. Junio - pls apply Nico's patch asap. It's correct, and fixes a really nasty problem. And I'll withdraw my other worries as "not consequential". Linus ``` ## Nicolas Pitre, 2006-05-10 17:27 Subject: Re: [PATCH] fix diff-delta bad memory access Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0605101311020.24505%40localhost.localdomain In-Reply-To: ``` On Wed, 10 May 2006, Linus Torvalds wrote: > On Wed, 10 May 2006, Nicolas Pitre wrote: > > > > It cannot be assumed that the given buffer will never be moved when > > shrinking the allocated memory size with realloc(). So let's ignore > > that optimization for now. > > Yeah, that was totally bogus. It would re-allocate _part_ of an > allocation, but that allocation contained not just the index, but all the > hashes and the hash entries too! Yep. > This has nothing to do with moving a buffer - it has everything to do with > the fact that you shrunk a buffer that still contained all the other > buffers: you shrunk the "mem" allocation to fit just the first part of it, > and entirely ignored the "hash" and "entry" parts of it. No. The initial allocation assumes a perfectly even distribution of entries in which case the entry array would be all populated. When there are repeated bytes then consecutive blocks will have the same hash, and in that case keeping only the first one is useful. Which means that the entry pointer won't get to the end of the allocated space for all entries and I naively assumed that using realloc would only mark the allocated memory as smaller than it originally was without actually copying any of the remaining data, which is what happened in most cases but evidently not always. But if the buffer moves the hash array containing _pointers_ to hash entries gets totally screwed. > Btw, I think that whole "allocate everything in one allocation" thing is > potentially bogus even the way it is now, if the alignment constraints of > "index", "hash" and "entry" are different. Yeah... I might just do a separate allocation for hash entries as well. Or maybe even drop the hash chaining altogether (now that the code does backward matching that might be worth the code simplification). Nicolas ``` ## Linus Torvalds, 2006-05-10 19:01 Subject: Re: [PATCH] fix diff-delta bad memory access Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0605101159160.3718%40g5.osdl.org In-Reply-To: ``` Btw, Nico, that rabin hash code is _extremely_ confusing. The hash entry pointers point to "data + RABIN_WINDOW", and then to make things even _more_ confusing, the hash calculation code is actually offset by one, so it will have computed the hash with val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT]; where "i" goes from _1_ to RABIN_WINDOW instead of 0..WINDOW-1. So, if I read that correctly, the "entry->ptr" actually points not to the beginning of the data that was hashed, or even the end, but literally to the last byte of the data that was hashed in that window. Isn't that just _really_ confusing? Or is there some sense to this? Linus ``` ## Nicolas Pitre, 2006-05-10 19:43 Subject: Re: [PATCH] fix diff-delta bad memory access Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0605101515420.24505%40localhost.localdomain In-Reply-To: ``` On Wed, 10 May 2006, Linus Torvalds wrote: > > > Btw, Nico, that rabin hash code is _extremely_ confusing. Possible. > The hash entry pointers point to "data + RABIN_WINDOW", and then to make > things even _more_ confusing, the hash calculation code is actually offset > by one, so it will have computed the hash with > > val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT]; > > where "i" goes from _1_ to RABIN_WINDOW instead of 0..WINDOW-1. > > So, if I read that correctly, the "entry->ptr" actually points not to the > beginning of the data that was hashed, or even the end, but literally to > the last byte of the data that was hashed in that window. > > Isn't that just _really_ confusing? > > Or is there some sense to this? Yes, ptr points to the last byte of the window for given hash value. This is so because in the matching loop the window is scrolled byte by byte and the new hash value is always made of ROBIN_WINDOW-1 bytes which already have been processed (most probably added as literal bytes in the delta buffer) plus one new byte. So it makes sense to start forward byte matching only from that last byte to find the longest source area to match, especially since all the other bytes in the window are likely to be identical already and comparing them repeatedly for entries with the same hash would be wasteful in most cases. Further down, once the best offset with the longest match in the source buffer has been found, backward matching is performed to remove as much literal bytes that were added to the delta output as possible, which is most likely to catch the whole Robin window that hasn't been compared previously, but in that case the window content is compared only once. And the reason why the reference hash is computed with an offset of 1 to RABIN_WINDOW inclusive in create_delta_index() is to allow for quick initialization of the Rabin window _outside_ of the main loop in create_delta(). There is a comment to that effect near the top of create_delta_index but probably a small reminder should be added in the index loop as well. Nicolas ``` ## Nicolas Pitre, 2006-05-10 19:57 Subject: Re: [PATCH] fix diff-delta bad memory access Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0605101555390.24505%40localhost.localdomain In-Reply-To: ``` And of course s/robin/rabin/ (I can't type RABIN without having my fingers decide on ROBIN by themselves). On Wed, 10 May 2006, Nicolas Pitre wrote: > On Wed, 10 May 2006, Linus Torvalds wrote: > > > > > > > Btw, Nico, that rabin hash code is _extremely_ confusing. > > Possible. > > > The hash entry pointers point to "data + RABIN_WINDOW", and then to make > > things even _more_ confusing, the hash calculation code is actually offset > > by one, so it will have computed the hash with > > > > val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT]; > > > > where "i" goes from _1_ to RABIN_WINDOW instead of 0..WINDOW-1. > > > > So, if I read that correctly, the "entry->ptr" actually points not to the > > beginning of the data that was hashed, or even the end, but literally to > > the last byte of the data that was hashed in that window. > > > > Isn't that just _really_ confusing? > > > > Or is there some sense to this? > > Yes, ptr points to the last byte of the window for given hash value. > > This is so because in the matching loop the window is scrolled byte by > byte and the new hash value is always made of ROBIN_WINDOW-1 bytes which > already have been processed (most probably added as literal bytes in the > delta buffer) plus one new byte. So it makes sense to start forward > byte matching only from that last byte to find the longest source area > to match, especially since all the other bytes in the window are likely > to be identical already and comparing them repeatedly for entries with > the same hash would be wasteful in most cases. > > Further down, once the best offset with the longest match in the source > buffer has been found, backward matching is performed to remove as much > literal bytes that were added to the delta output as possible, which is > most likely to catch the whole Robin window that hasn't been compared > previously, but in that case the window content is compared only once. > > And the reason why the reference hash is computed with an offset of 1 to > RABIN_WINDOW inclusive in create_delta_index() is to allow for quick > initialization of the Rabin window _outside_ of the main loop in > create_delta(). There is a comment to that effect near the top of > create_delta_index but probably a small reminder should be added in the > index loop as well. > > > Nicolas > - > To unsubscribe from this list: send the line "unsubscribe git" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html > Nicolas ```