{"thread":{"id":"5942","subject":"heads-up: git-index-pack in \"next\" is broken","startedAt":"2006-10-17T04:55:57Z","lastAt":"2006-10-18T22:34:35Z","messageCount":33,"participants":["Junio C Hamano","Nicolas Pitre","Sergey Vlasov","Linus Torvalds","Davide Libenzi","Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"28902","messageId":"7vy7rfsfqa.fsf@assigned-by-dhcp.cox.net","threadId":"5942","inReplyTo":null,"subject":"heads-up: git-index-pack in \"next\" is broken","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-17T04:55:57Z","receivedAt":"2006-10-17T04:55:57Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I'm still a bit under the weather and do not have enough\nconcentration to dig into the problem tonight, but I noticed\nthat something in \"next\", most likely the delta-base-offset\npatchset, broke git-index-pack:\n\n$ X=ec0c3491753e115e1775256f6b7bd1bce4dea7cd\n$ wget http://www.kernel.org/pub/scm/git/git.git/objects/pack/pack-$X.pack\n$ ~/git-master/bin/git-index-pack pack-$X.pack\nec0c3491753e115e1775256f6b7bd1bce4dea7cd\n$ git-index-pack pack-$X.pack\nfatal: packfile 'pack-ec0c3491753e115e1775256f6b7bd1bce4dea7cd.pack' has unresolved deltas\n"},{"id":"28972","messageId":"Pine.LNX.4.64.0610171134130.1971@xanadu.home","threadId":"5942","inReplyTo":"7vy7rfsfqa.fsf@assigned-by-dhcp.cox.net","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-10-17T15:39:20Z","receivedAt":"2006-10-17T15:39:20Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 16 Oct 2006, Junio C Hamano wrote:\n\n> I'm still a bit under the weather and do not have enough\n> concentration to dig into the problem tonight, but I noticed\n> that something in \"next\", most likely the delta-base-offset\n> patchset, broke git-index-pack:\n> \n> $ X=ec0c3491753e115e1775256f6b7bd1bce4dea7cd\n> $ wget http://www.kernel.org/pub/scm/git/git.git/objects/pack/pack-$X.pack\n> $ ~/git-master/bin/git-index-pack pack-$X.pack\n> ec0c3491753e115e1775256f6b7bd1bce4dea7cd\n> $ git-index-pack pack-$X.pack\n> fatal: packfile 'pack-ec0c3491753e115e1775256f6b7bd1bce4dea7cd.pack' has unresolved deltas\n\nUsing the tip of the \"next\" branch (git version 1.4.2.4.gf9fe) I just \ncannot reproduce this problem at all. I always get a good index and \nec0c3491753e115e1775256f6b7bd1bce4dea7cd back.\n\n\nNicolas\n"},{"id":"28974","messageId":"7vslhnj58e.fsf@assigned-by-dhcp.cox.net","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610171134130.1971@xanadu.home","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-17T16:07:29Z","receivedAt":"2006-10-17T16:07:29Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> On Mon, 16 Oct 2006, Junio C Hamano wrote:\n>\n>> I'm still a bit under the weather and do not have enough\n>> concentration to dig into the problem tonight, but I noticed\n>> that something in \"next\", most likely the delta-base-offset\n>> patchset, broke git-index-pack:\n>> \n>> $ X=ec0c3491753e115e1775256f6b7bd1bce4dea7cd\n>> $ wget http://www.kernel.org/pub/scm/git/git.git/objects/pack/pack-$X.pack\n>> $ ~/git-master/bin/git-index-pack pack-$X.pack\n>> ec0c3491753e115e1775256f6b7bd1bce4dea7cd\n>> $ git-index-pack pack-$X.pack\n>> fatal: packfile 'pack-ec0c3491753e115e1775256f6b7bd1bce4dea7cd.pack' has unresolved deltas\n>\n> Using the tip of the \"next\" branch (git version 1.4.2.4.gf9fe) I just \n> cannot reproduce this problem at all. I always get a good index and \n> ec0c3491753e115e1775256f6b7bd1bce4dea7cd back.\n\nHmph. I just got exactly the same breakage; could this be\nanother 64-bit breakage? My breakage was on x86-64.\n"},{"id":"28978","messageId":"Pine.LNX.4.64.0610171251210.1971@xanadu.home","threadId":"5942","inReplyTo":"7vslhnj58e.fsf@assigned-by-dhcp.cox.net","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-10-17T17:00:09Z","receivedAt":"2006-10-17T17:00:09Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 17 Oct 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > On Mon, 16 Oct 2006, Junio C Hamano wrote:\n> >\n> >> I'm still a bit under the weather and do not have enough\n> >> concentration to dig into the problem tonight, but I noticed\n> >> that something in \"next\", most likely the delta-base-offset\n> >> patchset, broke git-index-pack:\n> >> \n> >> $ X=ec0c3491753e115e1775256f6b7bd1bce4dea7cd\n> >> $ wget http://www.kernel.org/pub/scm/git/git.git/objects/pack/pack-$X.pack\n> >> $ ~/git-master/bin/git-index-pack pack-$X.pack\n> >> ec0c3491753e115e1775256f6b7bd1bce4dea7cd\n> >> $ git-index-pack pack-$X.pack\n> >> fatal: packfile 'pack-ec0c3491753e115e1775256f6b7bd1bce4dea7cd.pack' has unresolved deltas\n> >\n> > Using the tip of the \"next\" branch (git version 1.4.2.4.gf9fe) I just \n> > cannot reproduce this problem at all. I always get a good index and \n> > ec0c3491753e115e1775256f6b7bd1bce4dea7cd back.\n> \n> Hmph. I just got exactly the same breakage; could this be\n> another 64-bit breakage? My breakage was on x86-64.\n\nI've been suspecting that since then as well. I indeed tested on i386.\nBut reviewing the code I just can't find any obvious spot where 64-bit \nwould be an issue, especially since your pack does not have any \nOFS_DELTA objects.\n\nCould you instrument the code at the end of \nindex-pack.c:parse_pack_objects() to display how many deltas were \nactually resolved and how many were not? IOW is it a case of all or \nnothing, or is there an isolated case of corruption lurking somewhere?\n\n\nNicolas\n"},{"id":"28981","messageId":"7vbqoake1v.fsf@assigned-by-dhcp.cox.net","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610171251210.1971@xanadu.home","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-17T18:11:40Z","receivedAt":"2006-10-17T18:11:40Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> On Tue, 17 Oct 2006, Junio C Hamano wrote:\n>\n>> Nicolas Pitre writes:\n>> \n>> > On Mon, 16 Oct 2006, Junio C Hamano wrote:\n>> >\n>> >> I'm still a bit under the weather and do not have enough\n>> >> concentration to dig into the problem tonight, but I noticed\n>> >> that something in \"next\", most likely the delta-base-offset\n>> >> patchset, broke git-index-pack:\n>> >> \n>> >> $ X=ec0c3491753e115e1775256f6b7bd1bce4dea7cd\n>> >> $ wget http://www.kernel.org/pub/scm/git/git.git/objects/pack/pack-$X.pack\n>> >> $ ~/git-master/bin/git-index-pack pack-$X.pack\n>> >> ec0c3491753e115e1775256f6b7bd1bce4dea7cd\n>> >> $ git-index-pack pack-$X.pack\n>> >> fatal: packfile 'pack-ec0c3491753e115e1775256f6b7bd1bce4dea7cd.pack' has unresolved deltas\n>> >\n>> > Using the tip of the \"next\" branch (git version 1.4.2.4.gf9fe) I just \n>> > cannot reproduce this problem at all. I always get a good index and \n>> > ec0c3491753e115e1775256f6b7bd1bce4dea7cd back.\n>> \n>> Hmph. I just got exactly the same breakage; could this be\n>> another 64-bit breakage? My breakage was on x86-64.\n>\n> I've been suspecting that since then as well. I indeed tested on i386.\n> But reviewing the code I just can't find any obvious spot where 64-bit \n> would be an issue, especially since your pack does not have any \n> OFS_DELTA objects.\n>\n> Could you instrument the code at the end of \n> index-pack.c:parse_pack_objects() to display how many deltas were \n> actually resolved and how many were not? IOW is it a case of all or \n> nothing, or is there an isolated case of corruption lurking somewhere?\n\nfatal: packfile 'pack-ec0c3491753e115e1775256f6b7bd1bce4dea7cd.pack' has\n18915 unresolved ref-deltas and 0 ofs-deltas among 21205\n\nBy the way, \"Gaaaah\". Is this find_delta() called from\nfind_delta_children() doing the right thing? I wonder if this\nis open to accidental collisions?. If you have an object name\nwhose last 12-bytes are all NUL and you have a pack offset whose\nbytes happens to be a good prefix for an object, what happens?\n"},{"id":"28985","messageId":"Pine.LNX.4.64.0610171437250.1971@xanadu.home","threadId":"5942","inReplyTo":"7vbqoake1v.fsf@assigned-by-dhcp.cox.net","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-10-17T18:47:16Z","receivedAt":"2006-10-17T18:47:16Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 17 Oct 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > Could you instrument the code at the end of \n> > index-pack.c:parse_pack_objects() to display how many deltas were \n> > actually resolved and how many were not? IOW is it a case of all or \n> > nothing, or is there an isolated case of corruption lurking somewhere?\n> \n> fatal: packfile 'pack-ec0c3491753e115e1775256f6b7bd1bce4dea7cd.pack' has\n> 18915 unresolved ref-deltas and 0 ofs-deltas among 21205\n\nHmmm.... Interesting.\n\nIs it possible that sizeof(union delta_base) might not be equal to 20 \nfor you?\n\n> By the way, \"Gaaaah\". Is this find_delta() called from\n> find_delta_children() doing the right thing? I wonder if this\n> is open to accidental collisions?. If you have an object name\n> whose last 12-bytes are all NUL and you have a pack offset whose\n> bytes happens to be a good prefix for an object, what happens?\n\nIt is filtered out later thusly:\n\n\t...\n\tfor (j = ref_first; j <= ref_last; j++)\n\t\tif (deltas[j].obj->type == OBJ_REF_DELTA)\n\t\t\tresolve_delta(&deltas[j], data, ...);\n\nSo if a collision happens the object won't be of the right type and it \nis simply skipped.\n\n\nNicolas\n"},{"id":"28990","messageId":"20061017233630.72a0aae5.vsu@altlinux.ru","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610171437250.1971@xanadu.home","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Sergey Vlasov","fromEmail":"vsu@altlinux.ru","sentAt":"2006-10-17T19:36:30Z","receivedAt":"2006-10-17T19:36:30Z","isPatch":false,"sender":{"key":"vsu@altlinux.ru","avatar":"https://avatars.githubusercontent.com/u/616082?v=4"},"body":"On Tue, 17 Oct 2006 14:47:16 -0400 (EDT) Nicolas Pitre wrote:\n\n> On Tue, 17 Oct 2006, Junio C Hamano wrote:\n> \n> > Nicolas Pitre writes:\n> > \n> > > Could you instrument the code at the end of \n> > > index-pack.c:parse_pack_objects() to display how many deltas were \n> > > actually resolved and how many were not? IOW is it a case of all or \n> > > nothing, or is there an isolated case of corruption lurking somewhere?\n> > \n> > fatal: packfile 'pack-ec0c3491753e115e1775256f6b7bd1bce4dea7cd.pack' has\n> > 18915 unresolved ref-deltas and 0 ofs-deltas among 21205\n> \n> Hmmm.... Interesting.\n> \n> Is it possible that sizeof(union delta_base) might not be equal to 20 \n> for you?\n\nYes, on x86_64 this is 24 because of 8-byte alignment for longs:\n\n\n$ echo 'unsigned x = sizeof(union{unsigned char sha1[20]; long offset;});' | gcc -S -x c -m64 -o - - | grep long\n .long 24\n\n$ echo 'unsigned x = sizeof(union{unsigned char sha1[20]; long offset;});' | gcc -S -x c -m32 -o - - | grep long\n .long 20\n\n"},{"id":"28994","messageId":"7vy7reitzm.fsf@assigned-by-dhcp.cox.net","threadId":"5942","inReplyTo":"20061017233630.72a0aae5.vsu@altlinux.ru","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-17T20:10:21Z","receivedAt":"2006-10-17T20:10:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Sergey Vlasov writes:\n\n> On Tue, 17 Oct 2006 14:47:16 -0400 (EDT) Nicolas Pitre wrote:\n>\n>> Is it possible that sizeof(union delta_base) might not be equal to 20 \n>> for you?\n>\n> Yes, on x86_64 this is 24 because of 8-byte alignment for longs:\n\nEnough eyeballs made this bug shallow ;-) Thanks.\n\ndiff --git a/index-pack.c b/index-pack.c\nindex fffddd2..49b6efe 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -166,6 +166,7 @@ static void *unpack_raw_entry(unsigned l\n \tcase OBJ_REF_DELTA:\n \t\tif (pos + 20 >= pack_limit)\n \t\t\tbad_object(offset, \"object extends past end of pack\");\n+\t\tmemset(delta_base, 0, sizeof(*delta_base));\n \t\thashcpy(delta_base->sha1, pack_base + pos);\n \t\tpos += 20;\n \t\tbreak;\n@@ -290,6 +291,7 @@ static void resolve_delta(struct delta_e\n \t\tbad_object(obj->offset, \"failed to apply delta\");\n \tsha1_object(result, result_size, type, obj->sha1);\n \n+\tmemset(&delta_base, 0, sizeof(delta_base));\n \thashcpy(delta_base.sha1, obj->sha1);\n \tif (!find_delta_childs(&delta_base, &first, &last)) {\n \t\tfor (j = first; j <= last; j++)\n@@ -365,6 +367,7 @@ static void parse_pack_objects(void)\n \n \t\tif (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA)\n \t\t\tcontinue;\n+\t\tmemset(&base, 0, sizeof(base));\n \t\thashcpy(base.sha1, obj->sha1);\n \t\tref = !find_delta_childs(&base, &ref_first, &ref_last);\n \t\tmemset(&base, 0, sizeof(base));\n"},{"id":"28995","messageId":"Pine.LNX.4.64.0610171615340.1971@xanadu.home","threadId":"5942","inReplyTo":"20061017233630.72a0aae5.vsu@altlinux.ru","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-10-17T20:23:26Z","receivedAt":"2006-10-17T20:23:26Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 17 Oct 2006, Sergey Vlasov wrote:\n\n> On Tue, 17 Oct 2006 14:47:16 -0400 (EDT) Nicolas Pitre wrote:\n> \n> > Is it possible that sizeof(union delta_base) might not be equal to 20 \n> > for you?\n> \n> Yes, on x86_64 this is 24 because of 8-byte alignment for longs:\n\nAh bummer. Then this is most likely the cause. And here's a simple \nfix (Junio please confirm):\n\ndiff --git a/index-pack.c b/index-pack.c\nindex fffddd2..56c590e 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -23,6 +23,12 @@ union delta_base {\n \tunsigned long offset;\n };\n \n+/*\n+ * Even if sizeof(union delta_base) == 24 on 64-bit archs, we really want\n+ * to memcmp() only the first 20 bytes.\n+ */\n+#define UNION_BASE_SZ\t20\n+\n struct delta_entry\n {\n \tstruct object_entry *obj;\n@@ -211,7 +217,7 @@ static int find_delta(const union delta_\n struct delta_entry *delta = &deltas[next];\n int cmp;\n \n- cmp = memcmp(base, &delta->base, sizeof(*base));\n+ cmp = memcmp(base, &delta->base, UNION_BASE_SZ);\n if (!cmp)\n return next;\n if (cmp < 0) {\n@@ -232,9 +238,9 @@ static int find_delta_childs(const union\n \n \tif (first < 0)\n \t\treturn -1;\n-\twhile (first > 0 && !memcmp(&deltas[first - 1].base, base, sizeof(*base)))\n+\twhile (first > 0 && !memcmp(&deltas[first - 1].base, base, UNION_BASE_SZ))\n \t\t--first;\n-\twhile (last < end && !memcmp(&deltas[last + 1].base, base, sizeof(*base)))\n+\twhile (last < end && !memcmp(&deltas[last + 1].base, base, UNION_BASE_SZ))\n \t\t++last;\n \t*first_index = first;\n \t*last_index = last;\n@@ -312,7 +318,7 @@ static int compare_delta_entry(const voi\n {\n \tconst struct delta_entry *delta_a = a;\n \tconst struct delta_entry *delta_b = b;\n-\treturn memcmp(&delta_a->base, &delta_b->base, sizeof(union delta_base));\n+\treturn memcmp(&delta_a->base, &delta_b->base, UNION_BASE_SZ);\n }\n \n static void parse_pack_objects(void)\n\n\nNicolas\n"},{"id":"28996","messageId":"Pine.LNX.4.64.0610171624130.1971@xanadu.home","threadId":"5942","inReplyTo":"7vy7reitzm.fsf@assigned-by-dhcp.cox.net","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-10-17T20:25:30Z","receivedAt":"2006-10-17T20:25:30Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 17 Oct 2006, Junio C Hamano wrote:\n\n> Sergey Vlasov writes:\n> \n> > On Tue, 17 Oct 2006 14:47:16 -0400 (EDT) Nicolas Pitre wrote:\n> >\n> >> Is it possible that sizeof(union delta_base) might not be equal to 20 \n> >> for you?\n> >\n> > Yes, on x86_64 this is 24 because of 8-byte alignment for longs:\n> \n> Enough eyeballs made this bug shallow ;-) Thanks.\n> \n> diff --git a/index-pack.c b/index-pack.c\n> index fffddd2..49b6efe 100644\n> --- a/index-pack.c\n> +++ b/index-pack.c\n> @@ -166,6 +166,7 @@ static void *unpack_raw_entry(unsigned l\n> \tcase OBJ_REF_DELTA:\n> \t\tif (pos + 20 >= pack_limit)\n> \t\t\tbad_object(offset, \"object extends past end of pack\");\n> +\t\tmemset(delta_base, 0, sizeof(*delta_base));\n> \t\thashcpy(delta_base->sha1, pack_base + pos);\n\nYeah.... but this is a bit wasteful since (especially on 32-bit archs) \nyou just write to the same memory twice in a row.\n\n\nNicolas\n"},{"id":"28997","messageId":"Pine.LNX.4.64.0610171339030.3962@g5.osdl.org","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610171615340.1971@xanadu.home","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-10-17T20:51:08Z","receivedAt":"2006-10-17T20:51:08Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 17 Oct 2006, Nicolas Pitre wrote:\n> On Tue, 17 Oct 2006, Sergey Vlasov wrote:\n> > \n> > Yes, on x86_64 this is 24 because of 8-byte alignment for longs:\n> \n> Ah bummer. Then this is most likely the cause. And here's a simple \n> fix (Junio please confirm):\n\nWhy do you use \"unsigned long\" in the first place?\n\nFor some structure like this, it sounds positively wrong. Pack-files \nshould be architecture-neutral, which means that they shouldn't depend on \nword-size, and they should be in some neutral byte-order.\n\nQuite frankly, this all makes me go \"Eww..\". The original pack-file (well, \nv2) format was well-defined and had none of these issues. In contrast, the \nnew code in 'next' is just _ugly_.\n\nAnd the thing about \"ugly\" is that it also tends to mean \"fragile\" and \n\"buggy\" and \"hard to extend later\".\n\nAnd maybe it's just me, but I consider unions to be bug-prone on their \nown. The \"master\" branch has exactly two unions: the \"grep_expr\" structure \ncontains one (where the union member is clearly defined by the node type \nin that structure), and object.c has a \"union any_object\" that _literally_ \nexists as purely an allocation size issue (ie it is used _only_ to \nallocate the maximum size of any of the possible structures).\n\nIn contrast, the new union introduced in \"next\" is just horrid. There's \nnot even any way to know which member to use, except apparently that it \nexpects that a SHA1 is never zero in the last 12 bytes. Which is probably \ntrue, but still - that's some ugly stuff.\n\nIs this something you want to bet a big project on?\n\n\t\t\tLinus\n"},{"id":"28999","messageId":"Pine.LNX.4.64.0610171706260.1971@xanadu.home","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610171339030.3962@g5.osdl.org","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-10-17T21:21:39Z","receivedAt":"2006-10-17T21:21:39Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 17 Oct 2006, Linus Torvalds wrote:\n\n> \n> \n> On Tue, 17 Oct 2006, Nicolas Pitre wrote:\n> > On Tue, 17 Oct 2006, Sergey Vlasov wrote:\n> > > \n> > > Yes, on x86_64 this is 24 because of 8-byte alignment for longs:\n> > \n> > Ah bummer. Then this is most likely the cause. And here's a simple \n> > fix (Junio please confirm):\n> \n> Why do you use \"unsigned long\" in the first place?\n\nBecause offsets into packs are expressed as unsigned long everywhere \nelse (except in the current pack index on-disk format).\n\n> For some structure like this, it sounds positively wrong. Pack-files \n> should be architecture-neutral, which means that they shouldn't depend on \n> word-size, and they should be in some neutral byte-order.\n\nBut they do. Please consider this code:\n\n\tcase OBJ_OFS_DELTA:\n\t\tmemset(delta_base, 0, sizeof(*delta_base));\n\t\tc = pack_base[pos++];\n\t\tbase_offset = c & 127;\n\t\twhile (c & 128) {\n\t\t\tbase_offset += 1;\n\t\t\tif (!base_offset || base_offset & ~(~0UL >> 7))\n\t\t\t\tbad_object(offset, \"offset value overflow for delta base object\");\n\t\t\tif (pos >= pack_limit)\n\t\t\t\tbad_object(offset, \"object extends past end of pack\");\n\t\t\tc = pack_base[pos++];\n\t\t\tbase_offset = (base_offset << 7) + (c & 127);\n\t\t}\n\t\tdelta_base->offset = offset - base_offset;\n\t\tif (delta_base->offset >= offset)\n\t\t\tbad_object(offset, \"delta base offset is out of bound\");\n\t\tbreak;\n\nDo you see anything inerently wrong in this code? The above is already \n64-bit ready such that it'll just work on 64-bit archs and will display \na sensible message if a 32-bit arch encounter a pack larger than 4GB. \nBut the on-disk pack format has no limitation what so ever.\n\n> Quite frankly, this all makes me go \"Eww..\". The original pack-file (well, \n> v2) format was well-defined and had none of these issues. In contrast, the \n> new code in 'next' is just _ugly_.\n\nI beg to differ. Please reconsider in light of the above.\n\n> And maybe it's just me, but I consider unions to be bug-prone on their \n> own. The \"master\" branch has exactly two unions: the \"grep_expr\" structure \n> contains one (where the union member is clearly defined by the node type \n> in that structure), and object.c has a \"union any_object\" that _literally_ \n> exists as purely an allocation size issue (ie it is used _only_ to \n> allocate the maximum size of any of the possible structures).\n> \n> In contrast, the new union introduced in \"next\" is just horrid. There's \n> not even any way to know which member to use, except apparently that it \n> expects that a SHA1 is never zero in the last 12 bytes. Which is probably \n> true, but still - that's some ugly stuff.\n\nThis union should be looked at just like a sortable hash pointing to a \nbase object so that deltas with the same base object can be sorted \ntogether. And the field to use is well defined of course: deltas with \nsha1 to base use the sha1 member, deltas with offset to base use the \noffset member. This hash, together with the delta type, constitute a \ntuple guaranteed to be unique so there can't be any confusion.\n\n> Is this something you want to bet a big project on?\n\nI don't see why not.\n\n\nNicolas\n"},{"id":"29001","messageId":"Pine.LNX.4.64.0610171440080.3962@g5.osdl.org","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610171706260.1971@xanadu.home","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-10-17T21:46:04Z","receivedAt":"2006-10-17T21:46:04Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 17 Oct 2006, Nicolas Pitre wrote:\n> \n> Because offsets into packs are expressed as unsigned long everywhere \n> else (except in the current pack index on-disk format).\n\nUntil your work, that \"unsigned long\" was totally just an internal thing \nthat didn't actually bleed into anything else.\n\n> > For some structure like this, it sounds positively wrong. Pack-files \n> > should be architecture-neutral, which means that they shouldn't depend on \n> > word-size, and they should be in some neutral byte-order.\n> \n> But they do. Please consider this code:\n\nRight. The pack-file itself. But the code that actually _generates_ it \nmixes things in alarming ways.\n\n> > In contrast, the new union introduced in \"next\" is just horrid. There's \n> > not even any way to know which member to use, except apparently that it \n> > expects that a SHA1 is never zero in the last 12 bytes. Which is probably \n> > true, but still - that's some ugly stuff.\n> \n> This union should be looked at just like a sortable hash pointing to a \n> base object so that deltas with the same base object can be sorted \n> together.\n\n.. and it sorts _differently_ on a big-endian vs little-endian thing, \ndoesn't it?\n\nSo now the sort order depends on endianness and/or wordsize. That just \nsounds really really wrong.\n\n\t\t\tLinus\n"},{"id":"29004","messageId":"7vr6x6ip5d.fsf@assigned-by-dhcp.cox.net","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610171339030.3962@g5.osdl.org","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-17T21:54:54Z","receivedAt":"2006-10-17T21:54:54Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Tue, 17 Oct 2006, Nicolas Pitre wrote:\n>> On Tue, 17 Oct 2006, Sergey Vlasov wrote:\n>> > \n>> > Yes, on x86_64 this is 24 because of 8-byte alignment for longs:\n>> \n>> Ah bummer. Then this is most likely the cause. And here's a simple \n>> fix (Junio please confirm):\n>\n> Why do you use \"unsigned long\" in the first place?\n>\n> For some structure like this, it sounds positively wrong. Pack-files \n> should be architecture-neutral, which means that they shouldn't depend on \n> word-size, and they should be in some neutral byte-order.\n\nThis is an in-core structure if I am not mistaken, and is never\nwritten out in the resulting pack file. The program is reading\nfrom .pack and building .idx that corresponds to it. I agree\nthat it is ugly, but I do not hink using neutral byte-order in\nthis part of the processing buys us anything in this particular\ncase.\n\n> In contrast, the new union introduced in \"next\" is just horrid. There's \n> not even any way to know which member to use, except apparently that it \n> expects that a SHA1 is never zero in the last 12 bytes. Which is probably \n> true, but still - that's some ugly stuff.\n\nAgain I agree with the ugliness objection, and I raised the\n\"expecting no collision\" issue which Nico refuted later. The\ncode is probably safe (not just safe in practice but safe in\ntheory as well), although that would not change the fact that it\nis ugly X-<.\n\nNico, could we have an un-uglied version please?\n"},{"id":"29029","messageId":"Pine.LNX.4.64.0610171959070.1971@xanadu.home","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610171440080.3962@g5.osdl.org","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-10-18T00:20:09Z","receivedAt":"2006-10-18T00:20:09Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 17 Oct 2006, Linus Torvalds wrote:\n\n> \n> \n> On Tue, 17 Oct 2006, Nicolas Pitre wrote:\n> > \n> > Because offsets into packs are expressed as unsigned long everywhere \n> > else (except in the current pack index on-disk format).\n> \n> Until your work, that \"unsigned long\" was totally just an internal thing \n> that didn't actually bleed into anything else.\n\nAnd would you please explain how my work changes that state of affairs?\nSorry but I don't follow you here. Still _I_ wrote that code.\n\n> > > For some structure like this, it sounds positively wrong. Pack-files \n> > > should be architecture-neutral, which means that they shouldn't depend on \n> > > word-size, and they should be in some neutral byte-order.\n> > \n> > But they do. Please consider this code:\n> \n> Right. The pack-file itself. But the code that actually _generates_ it \n> mixes things in alarming ways.\n\n???\n\n> > > In contrast, the new union introduced in \"next\" is just horrid. There's \n> > > not even any way to know which member to use, except apparently that it \n> > > expects that a SHA1 is never zero in the last 12 bytes. Which is probably \n> > > true, but still - that's some ugly stuff.\n> > \n> > This union should be looked at just like a sortable hash pointing to a \n> > base object so that deltas with the same base object can be sorted \n> > together.\n> \n> .. and it sorts _differently_ on a big-endian vs little-endian thing, \n> doesn't it?\n\nSure. But who cares? The sorting is just there to 1) perform binary \nsearches on the list of deltas based from a given object, and 2) find a \nlist of all deltas with the same base object.\n\n> So now the sort order depends on endianness and/or wordsize. That just \n> sounds really really wrong.\n\nAgain, who cares? That ordering doesn't influence any data produced by \nthe tool. It is an internal and private strategy to speed up the \n_local_ _searching_ process. It could be replaced by a dumb linear \nlist walk if you wish and the end result i.e. \nthe produced pack index would be exactly the same (with a significant \nslowdown notwitstanding).\n\nSo let me summarize:\n\n - the union is a hash.\n\n - the hash is either an offset value or a sha1 digest.\n\n - this hash is used for fast object lookup _only_.\n\n - it does sort differently on big vs little endian machines.\n\n - but we don't care at all because\n\n - it is a private algorithmic thing that doesn't \"bleed\" into any \n _real_ data structure, and\n\n - it doesn't have any influence on the format of the end result.\n\n - it is only a runtime abstraction and nothing else.\n\n - It never gets into the pack nor the pack index themselves.\n\nDo you still have issues with that?\n\n\nNicolas\n"},{"id":"29051","messageId":"Pine.LNX.4.64.0610171754040.3962@g5.osdl.org","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610171959070.1971@xanadu.home","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-10-18T00:57:03Z","receivedAt":"2006-10-18T00:57:03Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 17 Oct 2006, Nicolas Pitre wrote:\n> > \n> > .. and it sorts _differently_ on a big-endian vs little-endian thing, \n> > doesn't it?\n> \n> Sure. But who cares? The sorting is just there to 1) perform binary \n> searches on the list of deltas based from a given object, and 2) find a \n> list of all deltas with the same base object.\n\n_I_ care.\n\nThe new code is messy. It's fragile, and already showed one very \nfundamental bug which depended on architectures.\n\nThese things matter. We have had very few bugs in git, and one of the \nreasons is (I believe) that we haven't had ad-hoc code. I get _very_ \nnervous when you mix up SHA1 names with somethign totally different \nwithout even a flag to say which one it is. That's just nasty. The fact \nthat the code then behaves (and behave_d_) differently on different \narchitectures is just a sign of the problem.\n\n\"Who cares?\" is not a good question to ask for a SCM. \n\n\t\tLinus\n"},{"id":"29049","messageId":"7vac3uif6i.fsf@assigned-by-dhcp.cox.net","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610171959070.1971@xanadu.home","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-18T01:30:13Z","receivedAt":"2006-10-18T01:30:13Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> So let me summarize:\n>\n> - the union is a hash.\n>\n> - the hash is either an offset value or a sha1 digest.\n>\n> - this hash is used for fast object lookup _only_.\n>\n> - it does sort differently on big vs little endian machines.\n>\n> - but we don't care at all because\n>\n> - it is a private algorithmic thing that doesn't \"bleed\" into any \n> _real_ data structure, and\n>\n> - it doesn't have any influence on the format of the end result.\n>\n> - it is only a runtime abstraction and nothing else.\n>\n> - It never gets into the pack nor the pack index themselves.\n>\n> Do you still have issues with that?\n\nThe part you pointed out to me about \"accidental collision\"\nstill bothers me somewhat.\n\nRight now we do not produce ref-delta and ofs-delta in the same\nstream, but if somebody did so then it would mean a disaster to\nhave an accidental collision of an 8-byte offset value plus\n12-byte traiing NUL and another base object whose object name\nhappens to match that pattern.\n\nI am actually Ok if we say the code assumes one stream has only\nref-delta or ofs-delta and never both.\n\nBut then I suspect the first pass of parse_pack_objects() should\nmake sure that assumption holds true for the pack being\ninspected and barf if it is not. Also the second pass do not\nhave to run two find_delta_childs() calls per delta object\nbecause by that time we know which kind would never appear in\nthe packfile.\n\nBy the way can we call that find_delta_children() pretty please?\n"},{"id":"29055","messageId":"Pine.LNX.4.64.0610172021320.1971@xanadu.home","threadId":"5942","inReplyTo":"7vr6x6ip5d.fsf@assigned-by-dhcp.cox.net","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-10-18T01:38:50Z","receivedAt":"2006-10-18T01:38:50Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 17 Oct 2006, Junio C Hamano wrote:\n\n> Linus Torvalds writes:\n> \n> > On Tue, 17 Oct 2006, Nicolas Pitre wrote:\n> >> On Tue, 17 Oct 2006, Sergey Vlasov wrote:\n> >> > \n> >> > Yes, on x86_64 this is 24 because of 8-byte alignment for longs:\n> >> \n> >> Ah bummer. Then this is most likely the cause. And here's a simple \n> >> fix (Junio please confirm):\n> >\n> > Why do you use \"unsigned long\" in the first place?\n> >\n> > For some structure like this, it sounds positively wrong. Pack-files \n> > should be architecture-neutral, which means that they shouldn't depend on \n> > word-size, and they should be in some neutral byte-order.\n> \n> This is an in-core structure if I am not mistaken, and is never\n> written out in the resulting pack file. The program is reading\n> from .pack and building .idx that corresponds to it. I agree\n> that it is ugly, but I do not hink using neutral byte-order in\n> this part of the processing buys us anything in this particular\n> case.\n\nExact.\n\n> > In contrast, the new union introduced in \"next\" is just horrid. There's \n> > not even any way to know which member to use, except apparently that it \n> > expects that a SHA1 is never zero in the last 12 bytes. Which is probably \n> > true, but still - that's some ugly stuff.\n> \n> Again I agree with the ugliness objection, and I raised the\n> \"expecting no collision\" issue which Nico refuted later. The\n> code is probably safe (not just safe in practice but safe in\n> theory as well), although that would not change the fact that it\n> is ugly X-<.\n\nThe problem is that I just don't see what you find \"ugly\" in the thing.\nMaybe it is just a matter of few missing comments?\n\nPlease let me walk you through bits of the code. I hope you'll \nunderstand better why it is like it is after that.\n\nIn parse_pack_objects() you can read this:\n\n /*\n * First pass:\n * - find locations of all objects;\n * - calculate SHA1 of all non-delta objects;\n * - remember base SHA1 for all deltas.\n */\n\nSo we reads through the whole pack to find where objects are located. \nThis information is stored in the objects[] array for all objects. \nEntries for that array are:\n\nstruct object_entry\n{\n unsigned long offset;\n enum object_type type;\n enum object_type real_type;\n unsigned char sha1[20];\n};\n\nON that first pass only the offset and type can be determined for all \nobjects. The sha1 can be determined for non delta objects only.\n\nThere is a second array, deltas[], to record information about deltas as \nthey are found:\n\nstruct delta_entry\n{\n struct object_entry *obj;\n union delta_base base;\n};\n\nThe \"obj\" member points to the entry in the objects[] array for given \ndelta entry. And the \"base\" member, as you may guess, is a reference to \nthe base object for that delta.\n\nSo here we are with that dreaded union.\n\nNow why isn't it a second struct object_entry pointer instead? Because \none kind of delta allows for its base object to appear later in the pack \nand all we've got for identifying that base object is a sha1 reference \nsince we cannot predict where the base object will be. With the other \nobject type we _could_ find out about the location of the base object \nright away. But that would mean adding a special case for those objects \nthrough a different code path unnecessarily. Instead, the base offset \nis treated just like a very special sha1 value and the same array is \nused. So maybe the comment that says \"remember base SHA1 for all \ndeltas\" could be adjusted to mention \"base sha1 or offset\" to be exact.\n\nNow what next:\n\n /* Sort deltas by base SHA1/offset for fast searching */\n qsort(deltas, nr_deltas, sizeof(struct delta_entry),\n compare_delta_entry);\n\nThis comment, though, is extremely accurate. We sort delta entries \"for \nfast searching\". There is no other use for the union blob. To avoid \nthe union there could have been two separate delta arrays: one for \nOBJ_REF_DELTA and another for OBJ_OFS_DELTA. Then two \ncompare_delta_entry functions whould have been needed instead of only \none. But because we only use the union blob for searching given another \nsuch union blob for target, we actually don't care if the union content \nis a sha1 or an offset, and we don't care if that offset is 32-bit, \n64-bit, little endian or big endian. All that we care about is that the \ndelta entries are sorted according to that union blob for fast binary \nsearch. That is really all there is about it and therefore a single \nqsort() does the trick.\n\nNext:\n\n /*\n * Second pass:\n * - for all non-delta objects, look if it is used as a base for\n * deltas;\n * - if used as a base, uncompress the object and apply all deltas,\n * recursively checking if the resulting object is used as a base\n * for some more deltas.\n */\n\nHere we want to fill out the blanks in the objects[] array for delta \nobjects. It is of course much more efficient to start from a given base \nobject, inflate it, and use it successively on all delta objects that \ndepend on it. And let's do it recursively if the delta is also a \nbase object itself while at it.\n\nSo how does the dreaded union comes into play? It is simple. For each \nnon-delta objects, we create two union blobs. One with the sha1 member, \nthe other with the offset member. Those blobs are used as the key to \nsearch for a range of deltas that have that non-delta object for base. \nThis has the possibility to find two ranges: one for deltas with base as \nsha1, and the other range for deltas with offsets as sha1. Once the \ndelta ranges are known, the deltas are applied on that base object, the \nresulting object's sha1 is computed and \nthe whole thing is repeated for those resulting objects as potential \nbase objects for more deltas.\n\nJunio mentioned the possibility for collision between a union value that \nshould be treated as a sha1 and a union value that should be treated as \na delta base offset. Although such a collision is extremely improbable, \nit is still possible and if so the wrong delta type could be applied on \ntop of the wrong base object. To avoid this issue, a test is made on \nthe delta type before it is replayed. So if the search key \nwas created using the sha1 union member, we make sure that it is used \nwith OBJ_REF_DELTA objects only. And ditto for the search key created \nwith the offset union member. This way there just can not be any \nmistake even if there happens to be a collision in the base object \nreference namespace.\n\nFinally, the objects[] array is completely populated with objects sha1 \nand offsets. The dreaded union is completely forgotten (the deltas array \nis actually freed). And only then the pack index is written out to \ndisk.\n\n> Nico, could we have an un-uglied version please?\n\nI'm really sorry to say that I don't know how I could make it less \n\"ugly\". To me it is beautiful and efficient as is and I don't see why \nit needs to be done another way. If you still think otherwise then your \nguidance would be highly appreciated.\n\n\nNicolas\n"},{"id":"29062","messageId":"Pine.LNX.4.64.0610172140270.1971@xanadu.home","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610171754040.3962@g5.osdl.org","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-10-18T02:08:57Z","receivedAt":"2006-10-18T02:08:57Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 17 Oct 2006, Linus Torvalds wrote:\n\n> \n> \n> On Tue, 17 Oct 2006, Nicolas Pitre wrote:\n> > > \n> > > .. and it sorts _differently_ on a big-endian vs little-endian thing, \n> > > doesn't it?\n> > \n> > Sure. But who cares? The sorting is just there to 1) perform binary \n> > searches on the list of deltas based from a given object, and 2) find a \n> > list of all deltas with the same base object.\n> \n> _I_ care.\n\nOK, So I do.\n\n> The new code is messy. It's fragile, and already showed one very \n> fundamental bug which depended on architectures.\n\nMy stance is that it is not fragile. Sure it had one bug that depended \non an architecture difference, but so was commit ac58c7b18e about.\n\nThe code also has many consistency checks all over so that it doesn't \nwrite out garbage if such bugs arise. And that fundamental bug was \nactually a trivial one that was caught right away by such consistency \ncheck.\n\n> These things matter. We have had very few bugs in git, and one of the \n> reasons is (I believe) that we haven't had ad-hoc code. I get _very_ \n> nervous when you mix up SHA1 names with somethign totally different \n> without even a flag to say which one it is. That's just nasty.\n\nBut there _is_ a flag for damn sake. Did you at least try to understand \nthe code and not just skim over it from 10000 feet above?\n\nIt is really simple:\n\n - if the found union content matches with a reference union initialized \n through the sha1 member then deltas[j].obj->type == OBJ_REF_DELTA \n must be true.\n\n - if the found union content matches with a reference union initialized \n through the sha1 member then deltas[j].obj->type == OBJ_OFS_DELTA \n must be true.\n\n - For all deltas with deltas[j].obj->type == OBJ_REF_DELTA there can \n not be more than one of them with the same union value.\n\n - For all deltas with deltas[j].obj->type == OBJ_OFS_DELTA there can \n not be more than one of them with the same union value.\n\nThere is _no_ confusion possible.\n\n> The fact that the code then behaves (and behave_d_) differently on \n> different architectures is just a sign of the problem.\n\nDoes this mean that, with your own change to xdiff that has just been \ncommitted, you actually created a \"problem\"? Because this is a change \nthat creates different behaviors whether a 32-bit or 64-bit architecture \nis used, Right?\n\nBut of course not. We want it to behave differently on 64-bit than \n32-bit. My code is in the _same_ camp since I explicitly want it to \nsort numbers differently whether it is a little endian or big endian \nmachine.\n\nSo this is not a problem this is a feature, and very by design.\n\n> \"Who cares?\" is not a good question to ask for a SCM. \n\nPlease just try to understand why I'm claming this is not important in \nthis very case. Please do me this favor.\n\n\nNicolas\n"},{"id":"29063","messageId":"Pine.LNX.4.64.0610172209070.1971@xanadu.home","threadId":"5942","inReplyTo":"7vac3uif6i.fsf@assigned-by-dhcp.cox.net","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-10-18T02:23:30Z","receivedAt":"2006-10-18T02:23:30Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 17 Oct 2006, Junio C Hamano wrote:\n\n> The part you pointed out to me about \"accidental collision\"\n> still bothers me somewhat.\n\nI'll try to clear them away.\n\n> Right now we do not produce ref-delta and ofs-delta in the same\n> stream, \n\nIt is fully supported nevertheless.\n\n> but if somebody did so then it would mean a disaster to have an \n> accidental collision of an 8-byte offset value plus 12-byte traiing \n> NUL and another base object whose object name happens to match that \n> pattern.\n\nNot really. The only effect that would have on the sorted list of \ndelta entries -- such sorting used to bring all deltas with the same \nbase object contigously -- is that those deltas might not be perfectly \ncontigous wrt their base object. This is why there is a test to skip \ndeltas if they happen not to be of the expected type.\n\n> I am actually Ok if we say the code assumes one stream has only\n> ref-delta or ofs-delta and never both.\n\nI'm perfectly OK with both types completely randomized.\n\n> But then I suspect the first pass of parse_pack_objects() should\n> make sure that assumption holds true for the pack being\n> inspected and barf if it is not.\n\nThis is an unnecessary restriction though.\n\n> Also the second pass do not have to run two find_delta_childs() calls \n> per delta object because by that time we know which kind would never \n> appear in the packfile.\n\nTrue, but the flexibility is worth having I think. It makes the thing \nmore robust instead of less.\n\n> By the way can we call that find_delta_children() pretty please?\n\nI have no problem with that.\n\n\nNicolas\n"},{"id":"29065","messageId":"Pine.LNX.4.64.0610171959180.3962@g5.osdl.org","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610172140270.1971@xanadu.home","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-10-18T03:12:14Z","receivedAt":"2006-10-18T03:12:14Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 17 Oct 2006, Nicolas Pitre wrote:\n> \n> But there _is_ a flag for damn sake. Did you at least try to understand \n> the code and not just skim over it from 10000 feet above?\n\nI only looked at it from the patches, and the actual data structure, \nand they didn't have it, so..\n\n> There is _no_ confusion possible.\n\nOk. Good.\n\n> Does this mean that, with your own change to xdiff that has just been \n> committed, you actually created a \"problem\"? Because this is a change \n> that creates different behaviors whether a 32-bit or 64-bit architecture \n> is used, Right?\n\nIf you go back to that discussion, I actually pointed out several times \nthat the whole bug _was_ actually introduced exactly because the xdiff \ncode used things that behave differently depending on word-size.\n\nMy suggestion for a _proper_ fix was to not use \"unsigned long\" for that, \nand the patch I suggested (and eventually got merged) was to use the _low_ \nbits of the hash, exactly because the low bits are the ones that act the \nsame, regardless of wordsize.\n\n> But of course not. We want it to behave differently on 64-bit than \n> 32-bit.\n\nNo, we actually don't. Not for xdiff, at least. The last thing you want is \nfor different architectures to get different results. It's horrible. It \nmeans that bugs are hard to reproduce, and it means that even code that is \n\"tested\" is actually tested only for a particular architecture.\n\nSo the bug in xdiff was _exactly_ that somebody - totally incorrectly - \nthought it should work \"better\" on 64-bits. \n\n> Please just try to understand why I'm claming this is not important in \n> this very case. Please do me this favor.\n\nMaybe the code is fine. Maybe the particular detail wasn't important. But \nthe original code didn't have _any_ dependencies on things like structure \nalignment that caused it to do strange things. \n\nAnd dammit, the fact is, I think the new format is just worse. I think it \nwas a good thing to have the full SHA1 in the pack-file. I think the code \ngot less understandable, and had more special cases, just because now we \nhave two totally different kinds of deltas. So maybe I'm reacting to the \nfact that I think the bug happened in the first place for a very simple \nreason: the data structure wasn't unambiguous any more. \n\n\t\tLinus\n"},{"id":"29069","messageId":"7v64eii7hh.fsf@assigned-by-dhcp.cox.net","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610172209070.1971@xanadu.home","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-18T04:16:26Z","receivedAt":"2006-10-18T04:16:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n>> but if somebody did so then it would mean a disaster to have an \n>> accidental collision of an 8-byte offset value plus 12-byte traiing \n>> NUL and another base object whose object name happens to match that \n>> pattern.\n>\n> Not really. The only effect that would have on the sorted list of \n> delta entries -- such sorting used to bring all deltas with the same \n> base object contigously -- is that those deltas might not be perfectly \n> contigous wrt their base object. This is why there is a test to skip \n> deltas if they happen not to be of the expected type.\n\nAh, I misread the code that uses union actually checks the type\nin struct delta_entry (which embeds the union). There won't be\nany collision problem and you support both types at the same\ntime just fine.\n\nAnd your patch to compare only the first 20-bytes makes sense\n(assuming ulong is always shorter than 20-bytes which I think is\nsafe to assume).\n"},{"id":"29070","messageId":"7vu022gqji.fsf@assigned-by-dhcp.cox.net","threadId":"5942","inReplyTo":"7v64eii7hh.fsf@assigned-by-dhcp.cox.net","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-10-18T05:07:45Z","receivedAt":"2006-10-18T05:07:45Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Ah, I misread the code that uses union actually checks the type\n> in struct delta_entry (which embeds the union). There won't be\n> any collision problem and you support both types at the same\n> time just fine.\n>\n> And your patch to compare only the first 20-bytes makes sense\n> (assuming ulong is always shorter than 20-bytes which I think is\n> safe to assume).\n\nDoes this sound fair (the code is yours, just asking about the\nlog message)?\n\nIf we really wanted to be purist, we could run comparison with\nthe union and obj->type as two keys, but I do not think it is\nworth it.\n\n-- >8 --\nFrom: Nicolas Pitre \nDate: Tue, 17 Oct 2006 16:23:26 -0400\nSubject: [PATCH] index-pack: compare the first 20-bytes of the key.\n\nThe \"union delta_base\" is a strange beast. It is a 20-byte\nbinary blob key to search a binary searchable deltas[] array,\neach element of which uses it to represent its base object with\neither a full 20-byte SHA-1 or an offset in the pack. Which\nrepresentation is used is determined by another field of the\ndeltas[] array element, obj->type, so there is no room for\nconfusion, as long as we make sure we compare the keys for the\nsame type only with appropriate length. The code compared the\nfull union with memcmp().\n\nWhen storing the in-pack offset, the union was first cleared\nbefore storing an unsigned long, so comparison worked fine.\n\nOn 64-bit architectures, however, the union typically is 24-byte\nlong; the code did not clear the remaining 4-byte alignment\npadding when storing a full 20-byte SHA-1 representation. Using\nmemcmp() to compare the whole union was wrong.\n\nThis fixes the comparison to look at the first 20-bytes of the\nunion, regardless of the architecture. As long as ulong is\nsmaller than 20-bytes this works fine.\n\nSigned-off-by: Junio C Hamano \n---\n index-pack.c | 14 ++++++++++----\n 1 files changed, 10 insertions(+), 4 deletions(-)\n\ndiff --git a/index-pack.c b/index-pack.c\nindex fffddd2..56c590e 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -23,6 +23,12 @@ union delta_base {\n \tunsigned long offset;\n };\n \n+/*\n+ * Even if sizeof(union delta_base) == 24 on 64-bit archs, we really want\n+ * to memcmp() only the first 20 bytes.\n+ */\n+#define UNION_BASE_SZ\t20\n+\n struct delta_entry\n {\n \tstruct object_entry *obj;\n@@ -211,7 +217,7 @@ static int find_delta(const union delta_\n struct delta_entry *delta = &deltas[next];\n int cmp;\n \n- cmp = memcmp(base, &delta->base, sizeof(*base));\n+ cmp = memcmp(base, &delta->base, UNION_BASE_SZ);\n if (!cmp)\n return next;\n if (cmp < 0) {\n@@ -232,9 +238,9 @@ static int find_delta_childs(const union\n \n \tif (first < 0)\n \t\treturn -1;\n-\twhile (first > 0 && !memcmp(&deltas[first - 1].base, base, sizeof(*base)))\n+\twhile (first > 0 && !memcmp(&deltas[first - 1].base, base, UNION_BASE_SZ))\n \t\t--first;\n-\twhile (last < end && !memcmp(&deltas[last + 1].base, base, sizeof(*base)))\n+\twhile (last < end && !memcmp(&deltas[last + 1].base, base, UNION_BASE_SZ))\n \t\t++last;\n \t*first_index = first;\n \t*last_index = last;\n@@ -312,7 +318,7 @@ static int compare_delta_entry(const voi\n {\n \tconst struct delta_entry *delta_a = a;\n \tconst struct delta_entry *delta_b = b;\n-\treturn memcmp(&delta_a->base, &delta_b->base, sizeof(union delta_base));\n+\treturn memcmp(&delta_a->base, &delta_b->base, UNION_BASE_SZ);\n }\n \n static void parse_pack_objects(void)\n-- \n1.4.2.4.gf9fe\n"},{"id":"29076","messageId":"Pine.LNX.4.64.0610172242430.17253@alien.or.mcafeemobile.com","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610171959180.3962@g5.osdl.org","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-10-18T06:09:50Z","receivedAt":"2006-10-18T06:09:50Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Tue, 17 Oct 2006, Linus Torvalds wrote:\n\n> > Does this mean that, with your own change to xdiff that has just been \n> > committed, you actually created a \"problem\"? Because this is a change \n> > that creates different behaviors whether a 32-bit or 64-bit architecture \n> > is used, Right?\n> \n> If you go back to that discussion, I actually pointed out several times \n> that the whole bug _was_ actually introduced exactly because the xdiff \n> code used things that behave differently depending on word-size.\n\nEhm, I think there's a little bit of confusion. The incorrect golden ratio \nprime selection for 64 bits machines was coalescing hash indexes into a \nvery limited number of buckets, hence creating very bad performance on diff \noperations. The result of the diff would have been exacly the same, just \ncoming out after the time for a cup of coffee and a croissant ;)\n\n\n> So the bug in xdiff was _exactly_ that somebody - totally incorrectly - \n> thought it should work \"better\" on 64-bits. \n\nHaha, not exactly. I had just forgot about the incoming 64 bits world at \nthe time.\n\n\n\n- Davide\n"},{"id":"29099","messageId":"Pine.LNX.4.63.0610181159050.14200@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5942","inReplyTo":"7vu022gqji.fsf@assigned-by-dhcp.cox.net","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-10-18T10:00:28Z","receivedAt":"2006-10-18T10:00:28Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 17 Oct 2006, Junio C Hamano wrote:\n\n> +/*\n> + * Even if sizeof(union delta_base) == 24 on 64-bit archs, we really want\n> + * to memcmp() only the first 20 bytes.\n> + */\n> +#define UNION_BASE_SZ\t20\n\nExcuse me for joining the game, but why don't you just use the \nrecently introduced hashcmp() for that purpose? AFAIU you do exactly that, \nyou compare hashes.\n\nCiao,\nDscho\n"},{"id":"29112","messageId":"Pine.LNX.4.64.0610180901210.1971@xanadu.home","threadId":"5942","inReplyTo":"7vu022gqji.fsf@assigned-by-dhcp.cox.net","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-10-18T13:02:44Z","receivedAt":"2006-10-18T13:02:44Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 17 Oct 2006, Junio C Hamano wrote:\n\n> Junio C Hamano writes:\n> \n> > Ah, I misread the code that uses union actually checks the type\n> > in struct delta_entry (which embeds the union). There won't be\n> > any collision problem and you support both types at the same\n> > time just fine.\n> >\n> > And your patch to compare only the first 20-bytes makes sense\n> > (assuming ulong is always shorter than 20-bytes which I think is\n> > safe to assume).\n> \n> Does this sound fair (the code is yours, just asking about the\n> log message)?\n> \n> If we really wanted to be purist, we could run comparison with\n> the union and obj->type as two keys, but I do not think it is\n> worth it.\n> \n> -- >8 --\n> From: Nicolas Pitre \n> Date: Tue, 17 Oct 2006 16:23:26 -0400\n> Subject: [PATCH] index-pack: compare the first 20-bytes of the key.\n> \n> The \"union delta_base\" is a strange beast. It is a 20-byte\n> binary blob key to search a binary searchable deltas[] array,\n> each element of which uses it to represent its base object with\n> either a full 20-byte SHA-1 or an offset in the pack. Which\n> representation is used is determined by another field of the\n> deltas[] array element, obj->type, so there is no room for\n> confusion, as long as we make sure we compare the keys for the\n> same type only with appropriate length. The code compared the\n> full union with memcmp().\n> \n> When storing the in-pack offset, the union was first cleared\n> before storing an unsigned long, so comparison worked fine.\n> \n> On 64-bit architectures, however, the union typically is 24-byte\n> long; the code did not clear the remaining 4-byte alignment\n> padding when storing a full 20-byte SHA-1 representation. Using\n> memcmp() to compare the whole union was wrong.\n> \n> This fixes the comparison to look at the first 20-bytes of the\n> union, regardless of the architecture. As long as ulong is\n> smaller than 20-bytes this works fine.\n> \n> Signed-off-by: Junio C Hamano \n\nSigned-off-by: Nicolas Pitre \n"},{"id":"29115","messageId":"Pine.LNX.4.64.0610180902580.1971@xanadu.home","threadId":"5942","inReplyTo":"Pine.LNX.4.63.0610181159050.14200@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-10-18T13:13:04Z","receivedAt":"2006-10-18T13:13:04Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 18 Oct 2006, Johannes Schindelin wrote:\n\n> Hi,\n> \n> On Tue, 17 Oct 2006, Junio C Hamano wrote:\n> \n> > +/*\n> > + * Even if sizeof(union delta_base) == 24 on 64-bit archs, we really want\n> > + * to memcmp() only the first 20 bytes.\n> > + */\n> > +#define UNION_BASE_SZ\t20\n> \n> Excuse me for joining the game, but why don't you just use the \n> recently introduced hashcmp() for that purpose? AFAIU you do exactly that, \n> you compare hashes.\n\nYes, and that is what I did originally.\n\nBut that could lead to false assumptions (and this thread already proved \nthis code has its share of false assumption leads already). The thing \nis that the memory chunk that is being compared is not always the same \nkind of hash as usually used with hashcmp(). Throughout the code \nhashcmp() is always used with a 20-byte sha1 digest. In this case it \ncan be either a 20-byte sha1 digest, or a long offset value. And by \nusing hashcmp() I would be afraid someone else could assume the hash is \nalways a sha1 digest which it is not.\n\n\nNicolas\n"},{"id":"29120","messageId":"Pine.LNX.4.64.0610180752500.3962@g5.osdl.org","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610172242430.17253@alien.or.mcafeemobile.com","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-10-18T14:56:51Z","receivedAt":"2006-10-18T14:56:51Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 17 Oct 2006, Davide Libenzi wrote:\n> \n> Ehm, I think there's a little bit of confusion. The incorrect golden ratio \n> prime selection for 64 bits machines was coalescing hash indexes into a \n> very limited number of buckets, hence creating very bad performance on diff \n> operations. The result of the diff would have been exacly the same, just \n> coming out after the time for a cup of coffee and a croissant ;)\n\nBut my point is, you would have been better off _without_ an algorithm \nthat cared about the word-size at all, or with just using \"uint32_t\".\n\nSee? Yes, a \"unsigned long\" has more bits for hashing on a 64-bit \narchitecture. But that's totally the wrong way of thinking about it. YOU \nDO NOT WANT MORE BITS! You want the same damn answer regardless of \narchitecture!\n\nA diff algorithm that gives different answers on a 32-bit LE architecture \nthan on a 64-bit BE architecture is BROKEN. If I run on x86-64, I want the \nsame answers I got on x86-32, and the same ones I get on ppc32. Anything \nelse is SIMPLY NOT ACCEPTABLE!\n\nSo the whole idea that you should have used 64-bit values was broken, \nbroken, broken. You should never have had anything that cared, because \nanything that cares is by definition buggy.\n\nThis is why we should use the _low_ bits. Never the high bits.\n\n\t\tLinus\n"},{"id":"29126","messageId":"Pine.LNX.4.64.0610180845040.18388@alien.or.mcafeemobile.com","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610180752500.3962@g5.osdl.org","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-10-18T16:17:04Z","receivedAt":"2006-10-18T16:17:04Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Wed, 18 Oct 2006, Linus Torvalds wrote:\n\n> On Tue, 17 Oct 2006, Davide Libenzi wrote:\n> > \n> > Ehm, I think there's a little bit of confusion. The incorrect golden ratio \n> > prime selection for 64 bits machines was coalescing hash indexes into a \n> > very limited number of buckets, hence creating very bad performance on diff \n> > operations. The result of the diff would have been exacly the same, just \n> > coming out after the time for a cup of coffee and a croissant ;)\n> \n> But my point is, you would have been better off _without_ an algorithm \n> that cared about the word-size at all, or with just using \"uint32_t\".\n\nYes. At the time I picked Knuth's hash function because it was simple and \nfast enough. But it needed special handling for different word sizes, \nexactly like kernel's hash_long() does.\n\n\n\n> A diff algorithm that gives different answers on a 32-bit LE architecture \n> than on a 64-bit BE architecture is BROKEN. If I run on x86-64, I want the \n> same answers I got on x86-32, and the same ones I get on ppc32. Anything \n> else is SIMPLY NOT ACCEPTABLE!\n\nSpeaking in general, seen at the hash function level, of course an interface \nshould not give different result for different word sizes or word endianess. \nConsidering the diff algorithm as interface, as I said, the output was \nunaffected by the 64 bits word size. It was just very slow.\n\n\n\n- Davide\n"},{"id":"29130","messageId":"Pine.LNX.4.64.0610180938540.3962@g5.osdl.org","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610180845040.18388@alien.or.mcafeemobile.com","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-10-18T16:52:23Z","receivedAt":"2006-10-18T16:52:23Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 18 Oct 2006, Davide Libenzi wrote:\n>\n> Speaking in general, seen at the hash function level, of course an interface \n> should not give different result for different word sizes or word endianess. \n> Considering the diff algorithm as interface, as I said, the output was \n> unaffected by the 64 bits word size. It was just very slow.\n\nWell, even the output may actually be affected, in the case of _real_ hash \ncollisions (as opposed to just the hash _list_ collision that XDL_HASHLONG \ncaused).\n\nSo I actually think it would be better to have \"uint32_t\" as the hash \nvalue - because that would mean that all diffs (or, in the case of the \nblock-algorithm, the deltas) are guaranteed to give the same results \nregardless of architecture.\n\nRight now, we actually generate a 64-bit hash value (BUT: for short lines, \nit's likely only _interesting_ in the low bits, so the high bits tend to \nhave a very high likelihood of being zero). So hash collisions are \ndifferent: on a 32-bit architecture, two lines may have the same hash, \nwhile on a 64-bit one, they are different.\n\nAnd together with some of the limiters we have (eg XDL_MAX_EQLIMIT) hash \ncollisions can sometimes affect the output.\n\nAdmittedly, in _practice_ this is really unlikely to affect anything \n(you'd get a valid diff in either case, they'd just possibly be subtly \ndifferent, and the input data must be _really_ strange to even see that \ncase), but I do think that the hash algorithm can matter.\n\nNOTE! I'm not talking about XDL_HASHLONG(), I'm talking about the \nxdl_hash_record() hash, which returns differently-sized hash results on \n32-bit and 64-bit. And there are cases where we _only_ compare the hashes, \nand don't actually double-check the contents.\n\nSo I think that in _practice_ you can't see differences between a 32-bit \nversion and a 64-bit one, but the possibility is there. Using \"uint32_t\" \ninstead of \"unsigned long\" to keep track of hashes would avoid that \ntheoretical problem (and might actually make for better performance on \n64-bit archtiectures, if only because of denser data structures and thus \nbetter cache behaviour).\n\n\t\t\tLinus\n"},{"id":"29152","messageId":"Pine.LNX.4.64.0610181407040.18885@alien.or.mcafeemobile.com","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610180938540.3962@g5.osdl.org","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-10-18T21:21:58Z","receivedAt":"2006-10-18T21:21:58Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Wed, 18 Oct 2006, Linus Torvalds wrote:\n\n> On Wed, 18 Oct 2006, Davide Libenzi wrote:\n> >\n> > Speaking in general, seen at the hash function level, of course an interface \n> > should not give different result for different word sizes or word endianess. \n> > Considering the diff algorithm as interface, as I said, the output was \n> > unaffected by the 64 bits word size. It was just very slow.\n> \n> Well, even the output may actually be affected, in the case of _real_ hash \n> collisions (as opposed to just the hash _list_ collision that XDL_HASHLONG \n> caused).\n> \n> So I actually think it would be better to have \"uint32_t\" as the hash \n> value - because that would mean that all diffs (or, in the case of the \n> block-algorithm, the deltas) are guaranteed to give the same results \n> regardless of architecture.\n> \n> Right now, we actually generate a 64-bit hash value (BUT: for short lines, \n> it's likely only _interesting_ in the low bits, so the high bits tend to \n> have a very high likelihood of being zero). So hash collisions are \n> different: on a 32-bit architecture, two lines may have the same hash, \n> while on a 64-bit one, they are different.\n> \n> And together with some of the limiters we have (eg XDL_MAX_EQLIMIT) hash \n> collisions can sometimes affect the output.\n> \n> Admittedly, in _practice_ this is really unlikely to affect anything \n> (you'd get a valid diff in either case, they'd just possibly be subtly \n> different, and the input data must be _really_ strange to even see that \n> case), but I do think that the hash algorithm can matter.\n> \n> NOTE! I'm not talking about XDL_HASHLONG(), I'm talking about the \n> xdl_hash_record() hash, which returns differently-sized hash results on \n> 32-bit and 64-bit. And there are cases where we _only_ compare the hashes, \n> and don't actually double-check the contents.\n\nThe hash value (hence the hash bucket index) simply directs you to the \nbucket where a real record-compare loop is performed. Collisions here \nmeans only performance loss (you don't spread buckets enough), nothing \nmore. So the different behaviour does not apply to the diff algo.\nBut, it would apply if the knowledge of the hash indexing would be \n\"exported\", for example inside an external file. Think about a trivial DB \nfile where you store hash buckets on file an you want to lookup records \nbased on the store hash layout. In that case, of course, if the hash \nfunction that generated the DB bucket layout is different from the one \nthat you use to get the bucket index at lookup time, you're in trouble.\nIOW if the hash function result is not \"exported\" is some way, it doesn't \nreally matter if it's an 'unsigned long' or a 'uint32_t'. In the same way \nyou cannot export binary structures using 'int' or 'long', and expect to \nbe compatible over different architectures.\n\n\n\n- Davide\n"},{"id":"29162","messageId":"Pine.LNX.4.64.0610181434510.3962@g5.osdl.org","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610181407040.18885@alien.or.mcafeemobile.com","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-10-18T21:48:43Z","receivedAt":"2006-10-18T21:48:43Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 18 Oct 2006, Davide Libenzi wrote:\n> \n> The hash value (hence the hash bucket index) simply directs you to the \n> bucket where a real record-compare loop is performed.\n\nAs far as I can tell not all loops do a real \"record-compare\" thing.\n\nSome of the hash loops _only_ look at the hash, and as such a bad hash \nwill do more than just cause bad performance, it will actually degrade the \ndiff itself. Isn't that what XDL_MAX_EQLIMIT effectively does?\n\nBtw, the binary delta generator doesn't seem to have this issue at all: it \nuses \"unsigned int\" for the hash values, so the xdiff delta generation \nwill give the same exact results on 32-bit and 64-bit architectures.\n\nOr was that one of the changes by Nico? (I only looked at the git version \nof that code)\n\n\t\tLinus\n"},{"id":"29176","messageId":"Pine.LNX.4.64.0610181527350.18885@alien.or.mcafeemobile.com","threadId":"5942","inReplyTo":"Pine.LNX.4.64.0610181434510.3962@g5.osdl.org","subject":"Re: heads-up: git-index-pack in \"next\" is broken","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-10-18T22:34:35Z","receivedAt":"2006-10-18T22:34:35Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Wed, 18 Oct 2006, Linus Torvalds wrote:\n\n> \n> \n> On Wed, 18 Oct 2006, Davide Libenzi wrote:\n> > \n> > The hash value (hence the hash bucket index) simply directs you to the \n> > bucket where a real record-compare loop is performed.\n> \n> As far as I can tell not all loops do a real \"record-compare\" thing.\n> \n> Some of the hash loops _only_ look at the hash, and as such a bad hash \n> will do more than just cause bad performance, it will actually degrade the \n> diff itself. Isn't that what XDL_MAX_EQLIMIT effectively does?\n\nThe XDL_MAX_EQLIMIT is used to limit the search for equal records, in the \nrecord-discard phase. Note though, that at that point that \"ha\" value is a \nrecord-class ID (every different record/line in the input has a unique ID).\nLook at what xdl_classify_record() does. So in that case, XDL_HASHLONG can \nreally simply be a bitmask. So comparing \"ha\" in the loop in there, does \nactually the right thing in any case (equal \"ha\" means really equal \nrecord).\n\n\n\n> Btw, the binary delta generator doesn't seem to have this issue at all: it \n> uses \"unsigned int\" for the hash values, so the xdiff delta generation \n> will give the same exact results on 32-bit and 64-bit architectures.\n> \n> Or was that one of the changes by Nico? (I only looked at the git version \n> of that code)\n\nThe binary diff in libxdiff uses a chaining hash, so even in that case it \nwouldn't have made a difference. I think Nico changed the hash to be a \ncoalesced hash, and in that case it does change the output.\n\n\n\n\n- Davide\n"}]}