{"thread":{"id":"4117","subject":"[PATCH] fix diff-delta bad memory access","startedAt":"2006-05-10T16:26:08Z","lastAt":"2006-05-10T19:57:39Z","messageCount":7,"participants":["Nicolas Pitre","Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"19833","messageId":"Pine.LNX.4.64.0605101216360.24505@localhost.localdomain","threadId":"4117","inReplyTo":null,"subject":"[PATCH] fix diff-delta bad memory access","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-05-10T16:26:08Z","receivedAt":"2006-05-10T16:26:08Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"It cannot be assumed that the given buffer will never be moved when \nshrinking the allocated memory size with realloc().  So let's ignore \nthat optimization for now.\n\nThis patch makes Electric Fence happy on Linux.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\n---\n\nI can't tell if that fixes it on BSD and Cygwin though.\n\n\ndiff --git a/Makefile b/Makefile\ndiff --git a/diff-delta.c b/diff-delta.c\nindex c618875..25a798d 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -199,7 +199,6 @@ struct delta_index * create_delta_index(\n \t\t\tentry->next = hash[i];\n \t\t\thash[i] = entry++;\n \t\t\thash_count[i]++;\n-\t\t\tentries--;\n \t\t}\n \t}\n \n@@ -230,10 +229,6 @@ struct delta_index * create_delta_index(\n \t}\n \tfree(hash_count);\n \n-\t/* If we didn't use all hash entries, free the unused memory. */\n-\tif (entries)\n-\t\tindex = realloc(index, memsize - entries * sizeof(*entry));\n-\n \treturn index;\n }\n \n"},{"id":"19835","messageId":"Pine.LNX.4.64.0605100953090.3718@g5.osdl.org","threadId":"4117","inReplyTo":"Pine.LNX.4.64.0605101216360.24505@localhost.localdomain","subject":"Re: [PATCH] fix diff-delta bad memory access","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-05-10T17:00:44Z","receivedAt":"2006-05-10T17:00:44Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 10 May 2006, Nicolas Pitre wrote:\n>\n> It cannot be assumed that the given buffer will never be moved when \n> shrinking the allocated memory size with realloc().  So let's ignore \n> that optimization for now.\n\nYeah, that was totally bogus. It would re-allocate _part_ of an \nallocation, but that allocation contained not just the index, but all the \nhashes and the hash entries too!\n\nThis has nothing to do with moving a buffer - it has everything to do with \nthe fact that you shrunk a buffer that still contained all the other \nbuffers: you shrunk the \"mem\" allocation to fit just the first part of it, \nand entirely ignored the \"hash\" and \"entry\" parts of it.\n\nBtw, I think that whole \"allocate everything in one allocation\" thing is \npotentially bogus even the way it is now, if the alignment constraints of \n\"index\", \"hash\" and \"entry\" are different.\n\nWhen you do\n\n\t..\n\tindex = mem;\n\tmem = index + 1;\n\thash = mem;\n\tmem = hash + hsize;\n\tentry = mem;\n\t..\n\nit's perfectly fine for \"index\", but \"hash\" and \"entry\" end up having \nalignments that depend on the size/alignment of \"index\" (and for \"entry\" \non \"hash\").\n\nSo if their alignment requirements are different, you're basically \nscrewed.\n\nIt may work in practice (maybe they all align on pointer boundaries), but \nit's damn scary. You should re-consider, or at least make that code be a \nlot safer (like actually taking alignment into consideration, both for \ntotal size and for the offset calculations).\n\nThat could be done by using unions or something.\n\n\t\t\tLinus\n"},{"id":"19836","messageId":"Pine.LNX.4.64.0605101015060.3718@g5.osdl.org","threadId":"4117","inReplyTo":"Pine.LNX.4.64.0605100953090.3718@g5.osdl.org","subject":"Re: [PATCH] fix diff-delta bad memory access","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-05-10T17:18:30Z","receivedAt":"2006-05-10T17:18:30Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 10 May 2006, Linus Torvalds wrote:\n> \n> Yeah, that was totally bogus. It would re-allocate _part_ of an \n> allocation, but that allocation contained not just the index, but all the \n> hashes and the hash entries too!\n\nActually, no, you got that part right. Mea culpa. It really only ended up \nbeing a problem when the area was moved, since the pointers into that area \nweren't updated.\n\nThe alignment issue is real, but looking at the different structures, \nthey'll all have pointers that end up being the real (and only) alignment \nconstraint, so as a result, on any reasonable machine they all have the \nsame alignment and things are fine.\n\nJunio - pls apply Nico's patch asap. It's correct, and fixes a really \nnasty problem. And I'll withdraw my other worries as \"not consequential\".\n\n\t\tLinus\n"},{"id":"19837","messageId":"Pine.LNX.4.64.0605101311020.24505@localhost.localdomain","threadId":"4117","inReplyTo":"Pine.LNX.4.64.0605100953090.3718@g5.osdl.org","subject":"Re: [PATCH] fix diff-delta bad memory access","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-05-10T17:27:26Z","receivedAt":"2006-05-10T17:27:26Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 10 May 2006, Linus Torvalds wrote:\n\n> On Wed, 10 May 2006, Nicolas Pitre wrote:\n> >\n> > It cannot be assumed that the given buffer will never be moved when \n> > shrinking the allocated memory size with realloc().  So let's ignore \n> > that optimization for now.\n> \n> Yeah, that was totally bogus. It would re-allocate _part_ of an \n> allocation, but that allocation contained not just the index, but all the \n> hashes and the hash entries too!\n\nYep.\n\n> This has nothing to do with moving a buffer - it has everything to do with \n> the fact that you shrunk a buffer that still contained all the other \n> buffers: you shrunk the \"mem\" allocation to fit just the first part of it, \n> and entirely ignored the \"hash\" and \"entry\" parts of it.\n\nNo.\n\nThe initial allocation assumes a perfectly even distribution of entries \nin which case the entry array would be all populated.\n\nWhen there are repeated bytes then consecutive blocks will have the same \nhash, and in that case keeping only the first one is useful.\n\nWhich means that the entry pointer won't get to the end of the allocated \nspace for all entries and I naively assumed that using realloc would \nonly mark the allocated memory as smaller than it originally was without \nactually copying any of the remaining data, which is what happened in \nmost cases but evidently not always.\n\nBut if the buffer moves the hash array containing _pointers_ to hash \nentries gets totally screwed.\n\n> Btw, I think that whole \"allocate everything in one allocation\" thing is \n> potentially bogus even the way it is now, if the alignment constraints of \n> \"index\", \"hash\" and \"entry\" are different.\n\nYeah...  I might just do a separate allocation for hash entries as well.\n\nOr maybe even drop the hash chaining altogether (now that the code does \nbackward matching that might be worth the code simplification).\n\n\nNicolas\n"},{"id":"19839","messageId":"Pine.LNX.4.64.0605101159160.3718@g5.osdl.org","threadId":"4117","inReplyTo":"Pine.LNX.4.64.0605101311020.24505@localhost.localdomain","subject":"Re: [PATCH] fix diff-delta bad memory access","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-05-10T19:01:58Z","receivedAt":"2006-05-10T19:01:58Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nBtw, Nico, that rabin hash code is _extremely_ confusing.\n\nThe hash entry pointers point to \"data + RABIN_WINDOW\", and then to make \nthings even _more_ confusing, the hash calculation code is actually offset \nby one, so it will have computed the hash with\n\n\tval = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];\n\nwhere \"i\" goes from _1_ to RABIN_WINDOW instead of 0..WINDOW-1.\n\nSo, if I read that correctly, the \"entry->ptr\" actually points not to the \nbeginning of the data that was hashed, or even the end, but literally to \nthe last byte of the data that was hashed in that window.\n\nIsn't that just _really_ confusing?\n\nOr is there some sense to this?\n\n\t\t\tLinus\n"},{"id":"19840","messageId":"Pine.LNX.4.64.0605101515420.24505@localhost.localdomain","threadId":"4117","inReplyTo":"Pine.LNX.4.64.0605101159160.3718@g5.osdl.org","subject":"Re: [PATCH] fix diff-delta bad memory access","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-05-10T19:43:34Z","receivedAt":"2006-05-10T19:43:34Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 10 May 2006, Linus Torvalds wrote:\n\n> \n> \n> Btw, Nico, that rabin hash code is _extremely_ confusing.\n\nPossible.\n\n> The hash entry pointers point to \"data + RABIN_WINDOW\", and then to make \n> things even _more_ confusing, the hash calculation code is actually offset \n> by one, so it will have computed the hash with\n> \n> \tval = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];\n> \n> where \"i\" goes from _1_ to RABIN_WINDOW instead of 0..WINDOW-1.\n> \n> So, if I read that correctly, the \"entry->ptr\" actually points not to the \n> beginning of the data that was hashed, or even the end, but literally to \n> the last byte of the data that was hashed in that window.\n> \n> Isn't that just _really_ confusing?\n> \n> Or is there some sense to this?\n\nYes, ptr points to the last byte of the window for given hash value.\n\nThis is so because in the matching loop the window is scrolled byte by \nbyte and the new hash value is always made of ROBIN_WINDOW-1 bytes which \nalready have been processed (most probably added as literal bytes in the \ndelta buffer) plus one new byte.  So it makes sense to start forward \nbyte matching only from that last byte to find the longest source area \nto match, especially since all the other bytes in the window are likely \nto be identical already and comparing them repeatedly for entries with \nthe same hash would be wasteful in most cases.\n\nFurther down, once the best offset with the longest match in the source \nbuffer has been found, backward matching is performed to remove as much \nliteral bytes that were added to the delta output as possible, which is \nmost likely to catch the whole Robin window that hasn't been compared \npreviously, but in that case the window content is compared only once.\n\nAnd the reason why the reference hash is computed with an offset of 1 to \nRABIN_WINDOW inclusive in create_delta_index() is to allow for quick \ninitialization of the Rabin window _outside_ of the main loop in \ncreate_delta().  There is a comment to that effect near the top of \ncreate_delta_index but probably a small reminder should be added in the \nindex loop as well.\n\n\nNicolas\n"},{"id":"19841","messageId":"Pine.LNX.4.64.0605101555390.24505@localhost.localdomain","threadId":"4117","inReplyTo":"Pine.LNX.4.64.0605101515420.24505@localhost.localdomain","subject":"Re: [PATCH] fix diff-delta bad memory access","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-05-10T19:57:39Z","receivedAt":"2006-05-10T19:57:39Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nAnd of course s/robin/rabin/ (I can't type RABIN without having my \nfingers decide on ROBIN by themselves).\n\nOn Wed, 10 May 2006, Nicolas Pitre wrote:\n\n> On Wed, 10 May 2006, Linus Torvalds wrote:\n> \n> > \n> > \n> > Btw, Nico, that rabin hash code is _extremely_ confusing.\n> \n> Possible.\n> \n> > The hash entry pointers point to \"data + RABIN_WINDOW\", and then to make \n> > things even _more_ confusing, the hash calculation code is actually offset \n> > by one, so it will have computed the hash with\n> > \n> > \tval = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];\n> > \n> > where \"i\" goes from _1_ to RABIN_WINDOW instead of 0..WINDOW-1.\n> > \n> > So, if I read that correctly, the \"entry->ptr\" actually points not to the \n> > beginning of the data that was hashed, or even the end, but literally to \n> > the last byte of the data that was hashed in that window.\n> > \n> > Isn't that just _really_ confusing?\n> > \n> > Or is there some sense to this?\n> \n> Yes, ptr points to the last byte of the window for given hash value.\n> \n> This is so because in the matching loop the window is scrolled byte by \n> byte and the new hash value is always made of ROBIN_WINDOW-1 bytes which \n> already have been processed (most probably added as literal bytes in the \n> delta buffer) plus one new byte.  So it makes sense to start forward \n> byte matching only from that last byte to find the longest source area \n> to match, especially since all the other bytes in the window are likely \n> to be identical already and comparing them repeatedly for entries with \n> the same hash would be wasteful in most cases.\n> \n> Further down, once the best offset with the longest match in the source \n> buffer has been found, backward matching is performed to remove as much \n> literal bytes that were added to the delta output as possible, which is \n> most likely to catch the whole Robin window that hasn't been compared \n> previously, but in that case the window content is compared only once.\n> \n> And the reason why the reference hash is computed with an offset of 1 to \n> RABIN_WINDOW inclusive in create_delta_index() is to allow for quick \n> initialization of the Rabin window _outside_ of the main loop in \n> create_delta().  There is a comment to that effect near the top of \n> create_delta_index but probably a small reminder should be added in the \n> index loop as well.\n> \n> \n> Nicolas\n> -\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at  http://vger.kernel.org/majordomo-info.html\n> \n\n\nNicolas\n"}]}