{"thread":{"id":"24384","subject":"[PATCH] fast-import: export correctly marks larger than 2^20-1","startedAt":"2010-07-13T11:51:48Z","lastAt":"2010-08-10T14:20:19Z","messageCount":4,"participants":["Raja R Harinath","Jonathan Nieder","Shawn Pearce"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"145446","messageId":"1279021908-21291-1-git-send-email-harinath@hurrynot.org","threadId":"24384","inReplyTo":null,"subject":"[PATCH] fast-import: export correctly marks larger than 2^20-1","fromName":"Raja R Harinath","fromEmail":"harinath@hurrynot.org","sentAt":"2010-07-13T11:51:48Z","receivedAt":"2010-07-13T11:51:48Z","isPatch":true,"sender":{"key":"harinath@hurrynot.org","avatar":"https://avatars.githubusercontent.com/u/4610?v=4"},"body":"dump_marks_helper() has a bug when dumping marks larger than 2^20-1,\ni.e., when the sparse array has more than two levels.  The bug was\nthat the 'base' counter was being shifted by 20 bits at level 3, and\nthen again by 10 bits at level 2, rather than a total shift of 20 bits\nin this argument to the recursive call:\n\n  (base + k) << m->shift\n\nThere are two ways to fix this correctly, the elegant:\n\n  (base + k) << 10\n\nand the one I chose due to edit distance:\n\n  base + (k << m->shift)\n\nCc: Shawn O. Pearce <spearce@spearce.org>\nSigned-off-by: Raja R Harinath <harinath@hurrynot.org>\n---\n fast-import.c          |    2 +-\n t/t9300-fast-import.sh |   57 ++++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 58 insertions(+), 1 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 309f2c5..0c79289 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1666,7 +1666,7 @@ static void dump_marks_helper(FILE *f,\n \tif (m->shift) {\n \t\tfor (k = 0; k < 1024; k++) {\n \t\t\tif (m->data.sets[k])\n-\t\t\t\tdump_marks_helper(f, (base + k) << m->shift,\n+\t\t\t\tdump_marks_helper(f, base + (k << m->shift),\n \t\t\t\t\tm->data.sets[k]);\n \t\t}\n \t} else {\ndiff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh\nindex 131f032..2aeed7b 100755\n--- a/t/t9300-fast-import.sh\n+++ b/t/t9300-fast-import.sh\n@@ -166,6 +166,63 @@ test_expect_success \\\n \t test `git rev-parse --verify master:file2` \\\n \t    = `git rev-parse --verify verify--import-marks:copy-of-file2`'\n \n+test_tick\n+mt=$(git hash-object --stdin < /dev/null)\n+: >input.blob\n+: >marks.exp\n+: >tree.exp\n+\n+cat >input.commit <<EOF\n+commit refs/heads/verify--dump-marks\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+data <<COMMIT\n+test the sparse array dumping routines with exponentially growing marks\n+COMMIT\n+EOF\n+\n+i=0\n+l=4\n+m=6\n+n=7\n+while test \"$i\" -lt 27; do\n+    cat >>input.blob <<EOF\n+blob\n+mark :$l\n+data 0\n+blob\n+mark :$m\n+data 0\n+blob\n+mark :$n\n+data 0\n+EOF\n+    echo \"M 100644 :$l l$i\" >>input.commit\n+    echo \"M 100644 :$m m$i\" >>input.commit\n+    echo \"M 100644 :$n n$i\" >>input.commit\n+\n+    echo \":$l $mt\" >>marks.exp\n+    echo \":$m $mt\" >>marks.exp\n+    echo \":$n $mt\" >>marks.exp\n+\n+    printf \"100644 blob $mt\\tl$i\\n\" >>tree.exp\n+    printf \"100644 blob $mt\\tm$i\\n\" >>tree.exp\n+    printf \"100644 blob $mt\\tn$i\\n\" >>tree.exp\n+\n+    l=$(($l + $l))\n+    m=$(($m + $m))\n+    n=$(($l + $n))\n+\n+    i=$((1 + $i))\n+done\n+\n+sort tree.exp > tree.exp_s\n+\n+test_expect_success 'A: export marks with large values' '\n+\tcat input.blob input.commit | git fast-import --export-marks=marks.large &&\n+\tgit ls-tree refs/heads/verify--dump-marks >tree.out &&\n+\ttest_cmp tree.exp_s tree.out &&\n+\ttest_cmp marks.exp marks.large'\n+\n ###\n ### series B\n ###\n-- \n1.7.2.rc2.11.g03e33\n"},{"id":"145454","messageId":"20100713183126.GA2458@burratino","threadId":"24384","inReplyTo":"1279021908-21291-1-git-send-email-harinath@hurrynot.org","subject":"Re: [PATCH] fast-import: export correctly marks larger than 2^20-1","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-07-13T18:31:27Z","receivedAt":"2010-07-13T18:31:27Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"(+cc David, who I think mentioned wishing for something like this)\n\nRaja R Harinath wrote:\n\n> Subject: fast-import: export correctly marks larger than 2^20-1\n\nThank you!  That would be a very good thing.\n\n> dump_marks_helper() has a bug when dumping marks larger than 2^20-1,\n> i.e., when the sparse array has more than two levels.  The bug was\n> that the 'base' counter was being shifted by 20 bits at level 3, and\n> then again by 10 bits at level 2, rather than a total shift of 20 bits\n> in this argument to the recursive call:\n\nI haven’t read or grokked that code you are changing, so I can’t\ncomment on the substance of your patch.  In case no one with such\nknowledge turns up, could you give a quick summary of what the\nexisting code does and why?\n\nBarring that, v1.5.0-rc4~14^2~61 (Added option to export the marks\ntable when fast-import terminates., 2006-08-25) might be a good\nstarting point for a person looking to understand.\n"},{"id":"145516","messageId":"87iq4i8som.fsf@hariville.hurrynot.org","threadId":"24384","inReplyTo":"20100713183126.GA2458@burratino","subject":"Re: [PATCH] fast-import: export correctly marks larger than 2^20-1","fromName":"Raja R Harinath","fromEmail":"harinath@hurrynot.org","sentAt":"2010-07-14T06:48:41Z","receivedAt":"2010-07-14T06:48:41Z","isPatch":true,"sender":{"key":"harinath@hurrynot.org","avatar":"https://avatars.githubusercontent.com/u/4610?v=4"},"body":"Hi,\n\nJonathan Nieder <jrnieder@gmail.com> writes:\n\n> (+cc David, who I think mentioned wishing for something like this)\n>\n> Raja R Harinath wrote:\n>\n>> Subject: fast-import: export correctly marks larger than 2^20-1\n>\n> Thank you!  That would be a very good thing.\n\nI needed this so that I could maintain two 'marks' counters, one for\ncommits counting up from 1, and one for files counting down from some\nlarge value, where the file marks could be re-used.\n\n  http://gitorious.org/~harinath/svn2git/rrh-svn2git/commit/ffc5270a6fa106fecad1a6a9f1520ca8f075c6b7\n\nHowever, the 1M limit on marks is a bit too tight.  For instance, the\nmono SVN repository has 160K commits, with one project alone using 60K\ncommits.  And one of the commits touched nearly 24K files.  The number\nof marks used is uncomfortably close: within one order of magnitude of\nthe limit.  I'd like 10 more bits of breathing space, please :-)\n\n>> dump_marks_helper() has a bug when dumping marks larger than 2^20-1,\n>> i.e., when the sparse array has more than two levels.  The bug was\n>> that the 'base' counter was being shifted by 20 bits at level 3, and\n>> then again by 10 bits at level 2, rather than a total shift of 20 bits\n>> in this argument to the recursive call:\n>\n> I haven’t read or grokked that code you are changing, so I can’t\n> comment on the substance of your patch.  In case no one with such\n> knowledge turns up, could you give a quick summary of what the\n> existing code does and why?\n\nThis is not particular quick or clear, but here goes.\n\nThe marks are stored in a sparse array data structure.  The sparse array\nis represented as a 1024-tree, with object storage only at the leafs,\nand every path from root to leaf being the same length.  So, each node\ncan, and does, have the notion of a level, which is represented by a\nnumber of bits to shift.\n\nWhen you try to lookup at a non-leaf, the lookup index can be shifted\nright the given number of bits, and masked to 10 bits [1], to get the\nsub-tree to continue lookup in.  IOW, all the indices in a subtree have\na common prefix.\n\nIn dump_marks_helper, the 'base' argument contains that common prefix to\nthe current tree.  In the recursive case, the common prefix of the\nsub-tree is computed by taking this 'base', and adding to it the\ncontribution from this node, i.e., k << shift [2].  The bug was that\n'base' was being shifted too, even though it already had the correct\nvalue from its caller.\n\n- Hari\n\n[1] The code actually does something different, but equivalent.  It\n    masks off the top bits immediately before recursing.  However, it's\n    easier to explain dump_marks_helper if we think of the index\n    surviving to the leaf.\n\n[2] Now that I think of it, the other fix, that I called more elegant,\n    is harder to explain.  So, let's not go with that.\n"},{"id":"147642","messageId":"AANLkTiniC0JeeZZeYSTg7M6WuhzJzChiqZ+9EBMoZwxQ@mail.gmail.com","threadId":"24384","inReplyTo":"1279021908-21291-1-git-send-email-harinath@hurrynot.org","subject":"Re: [PATCH] fast-import: export correctly marks larger than 2^20-1","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2010-08-10T14:20:19Z","receivedAt":"2010-08-10T14:20:19Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Tue, Jul 13, 2010 at 4:51 AM, Raja R Harinath <harinath@hurrynot.org> wrote:\n> dump_marks_helper() has a bug when dumping marks larger than 2^20-1,\n> i.e., when the sparse array has more than two levels.  The bug was\n> that the 'base' counter was being shifted by 20 bits at level 3, and\n> then again by 10 bits at level 2, rather than a total shift of 20 bits\n> in this argument to the recursive call:\n>\n>  (base + k) << m->shift\n>\n> There are two ways to fix this correctly, the elegant:\n>\n>  (base + k) << 10\n>\n> and the one I chose due to edit distance:\n>\n>  base + (k << m->shift)\n>\n> Cc: Shawn O. Pearce <spearce@spearce.org>\n> Signed-off-by: Raja R Harinath <harinath@hurrynot.org>\n\nDang, that's a very old bug.  This change makes sense, thanks.\n\nAcked-by: Shawn O. Pearce <spearce@spearce.org>\n\n-- \nShawn.\n"}]}