{"thread":{"id":"46155","subject":"[BUG] add_again() off-by-one error in custom format","startedAt":"2017-06-12T03:13:46Z","lastAt":"2017-06-24T14:12:24Z","messageCount":30,"participants":["Michael Giuffrida","Junio C Hamano","René Scharfe","SZEDER Gábor","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"321943","messageId":"CACi5S_1j46SbP7cQMdUnULmgGD7xBkSUrS2PKbzq8ZydybHE=w@mail.gmail.com","threadId":"46155","inReplyTo":null,"subject":"[BUG] add_again() off-by-one error in custom format","fromName":"Michael Giuffrida","fromEmail":"michaelpg@chromium.org","sentAt":"2017-06-12T03:13:16Z","receivedAt":"2017-06-12T03:13:46Z","isPatch":false,"sender":{"key":"michaelpg@chromium.org","avatar":null},"body":"In a custom pretty format, using the '+' or ' ' combinators to prefix\na non-empty expansion with whitespace will erroneously truncate\nsubsequent expansions of the same type.\n\nNormally '%+X' inserts a newline before , IFF the expansion of X is\nnon-empty:\n\n $ git log -n 1 --pretty='format:newline:%+an'\n newline:\n MyName\n\nFor the abbreviated commit hash placeholder ('h'), pretty.c uses\nadd_again() to cache the result of the expansion, and then uses that\nresult in future expansions. This causes problems when the expansion\nincludes whitespace:\n\n $ git log -n 1 --pretty='format:newline:%+h%nno_newline:%h'\n newline:\n a0b1c2d\n no_newline:\n a0b1c2\n\nThe second expansion of the hash added an unwanted newline and removed\nthe final character. It seemingly used the cached expansion *starting\nfrom the inserted newline*.\n\nThe expected output is:\n\n $ git log -n 1 --pretty='format:newline:%+h%nno_newline:%h'\n newline:\n a0b1c2d\n no_newline:a0b1c2d\n\n\n/CC René from commit b9c62321 and Junio from 9fa708d\n"},{"id":"322031","messageId":"xmqqd1a8n7o8.fsf@gitster.mtv.corp.google.com","threadId":"46155","inReplyTo":"CACi5S_1j46SbP7cQMdUnULmgGD7xBkSUrS2PKbzq8ZydybHE=w@mail.gmail.com","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-06-12T22:49:11Z","receivedAt":"2017-06-12T22:49:19Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Giuffrida writes:\n\n> For the abbreviated commit hash placeholder ('h'), pretty.c uses\n> add_again() to cache the result of the expansion, and then uses that\n> result in future expansions. This causes problems when the expansion\n> includes whitespace:\n>\n> $ git log -n 1 --pretty='format:newline:%+h%nno_newline:%h'\n> newline:\n> a0b1c2d\n> no_newline:\n> a0b1c2\n>\n> The second expansion of the hash added an unwanted newline and removed\n> the final character. It seemingly used the cached expansion *starting\n> from the inserted newline*.\n>\n> The expected output is:\n>\n> $ git log -n 1 --pretty='format:newline:%+h%nno_newline:%h'\n> newline:\n> a0b1c2d\n> no_newline:a0b1c2d\n\nNicely explained. The add_again() mechanism caches an earlier\nresult by remembering the offset and the length in the strbuf the\nformatted string is being accumulated to, but because %+x (and\nprobably %-x) magic placeholders futz with the result of\nformat_commit_one() in place, the cache goes out of sync, of course.\n\nI think the call to format_commit_one() needs to be taught to pass\n'magic' through, and then add_again() mechanism needs to be told not\nto cache when magic is in effect, or something like that.\n\nPerhaps something along this line...?\n\n pretty.c | 64 ++++++++++++++++++++++++++++++++++++++--------------------------\n 1 file changed, 38 insertions(+), 26 deletions(-)\n\ndiff --git a/pretty.c b/pretty.c\nindex 09701bd2ff..be22b12986 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -789,20 +789,22 @@ struct format_commit_context {\n \tsize_t wrap_start;\n };\n \n-static int add_again(struct strbuf *sb, struct chunk *chunk)\n+static int add_again(struct strbuf *sb, struct chunk *chunk, int no_cache)\n {\n \tif (chunk->len) {\n \t\tstrbuf_adddup(sb, chunk->off, chunk->len);\n \t\treturn 1;\n \t}\n \n-\t/*\n-\t * We haven't seen this chunk before. Our caller is surely\n-\t * going to add it the hard way now. Remember the most likely\n-\t * start of the to-be-added chunk: the current end of the\n-\t * struct strbuf.\n-\t */\n-\tchunk->off = sb->len;\n+\tif (!no_cache) {\n+\t\t/*\n+\t\t * We haven't seen this chunk before. Our caller is surely\n+\t\t * going to add it the hard way now. Remember the most likely\n+\t\t * start of the to-be-added chunk: the current end of the\n+\t\t * struct strbuf.\n+\t\t */\n+\t\tchunk->off = sb->len;\n+\t}\n \treturn 0;\n }\n \n@@ -1066,15 +1068,24 @@ static size_t parse_padding_placeholder(struct strbuf *sb,\n \treturn 0;\n }\n \n+enum format_commit_item_magic {\n+\tNO_MAGIC,\n+\tADD_LF_BEFORE_NON_EMPTY,\n+\tDEL_LF_BEFORE_EMPTY,\n+\tADD_SP_BEFORE_NON_EMPTY\n+};\n+\n static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \t\t\t\tconst char *placeholder,\n-\t\t\t\tvoid *context)\n+\t\t\t\tvoid *context,\n+\t\t\t\tenum format_commit_item_magic magic)\n {\n \tstruct format_commit_context *c = context;\n \tconst struct commit *commit = c->commit;\n \tconst char *msg = c->message;\n \tstruct commit_list *p;\n \tint ch;\n+\tint no_cache;\n \n \t/* these are independent of the commit */\n \tswitch (placeholder[0]) {\n@@ -1139,6 +1150,8 @@ static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \tif (!commit->object.parsed)\n \t\tparse_object(&commit->object.oid);\n \n+\tno_cache = magic != NO_MAGIC;\n+\n \tswitch (placeholder[0]) {\n \tcase 'H':\t\t/* commit hash */\n \t\tstrbuf_addstr(sb, diff_get_color(c->auto_color, DIFF_COMMIT));\n@@ -1147,24 +1160,26 @@ static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \t\treturn 1;\n \tcase 'h':\t\t/* abbreviated commit hash */\n \t\tstrbuf_addstr(sb, diff_get_color(c->auto_color, DIFF_COMMIT));\n-\t\tif (add_again(sb, &c->abbrev_commit_hash)) {\n+\t\tif (add_again(sb, &c->abbrev_commit_hash, no_cache)) {\n \t\t\tstrbuf_addstr(sb, diff_get_color(c->auto_color, DIFF_RESET));\n \t\t\treturn 1;\n \t\t}\n \t\tstrbuf_add_unique_abbrev(sb, commit->object.oid.hash,\n \t\t\t\t\t c->pretty_ctx->abbrev);\n \t\tstrbuf_addstr(sb, diff_get_color(c->auto_color, DIFF_RESET));\n-\t\tc->abbrev_commit_hash.len = sb->len - c->abbrev_commit_hash.off;\n+\t\tif (!no_cache)\n+\t\t\tc->abbrev_commit_hash.len = sb->len - c->abbrev_commit_hash.off;\n \t\treturn 1;\n \tcase 'T':\t\t/* tree hash */\n \t\tstrbuf_addstr(sb, oid_to_hex(&commit->tree->object.oid));\n \t\treturn 1;\n \tcase 't':\t\t/* abbreviated tree hash */\n-\t\tif (add_again(sb, &c->abbrev_tree_hash))\n+\t\tif (add_again(sb, &c->abbrev_tree_hash, no_cache))\n \t\t\treturn 1;\n \t\tstrbuf_add_unique_abbrev(sb, commit->tree->object.oid.hash,\n \t\t\t\t\t c->pretty_ctx->abbrev);\n-\t\tc->abbrev_tree_hash.len = sb->len - c->abbrev_tree_hash.off;\n+\t\tif (!no_cache)\n+\t\t\tc->abbrev_tree_hash.len = sb->len - c->abbrev_tree_hash.off;\n \t\treturn 1;\n \tcase 'P':\t\t/* parent hashes */\n \t\tfor (p = commit->parents; p; p = p->next) {\n@@ -1174,7 +1189,7 @@ static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \t\t}\n \t\treturn 1;\n \tcase 'p':\t\t/* abbreviated parent hashes */\n-\t\tif (add_again(sb, &c->abbrev_parent_hashes))\n+\t\tif (add_again(sb, &c->abbrev_parent_hashes, no_cache))\n \t\t\treturn 1;\n \t\tfor (p = commit->parents; p; p = p->next) {\n \t\t\tif (p != commit->parents)\n@@ -1182,8 +1197,9 @@ static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \t\t\tstrbuf_add_unique_abbrev(sb, p->item->object.oid.hash,\n \t\t\t\t\t\t c->pretty_ctx->abbrev);\n \t\t}\n-\t\tc->abbrev_parent_hashes.len = sb->len -\n-\t\t c->abbrev_parent_hashes.off;\n+\t\tif (!no_cache)\n+\t\t\tc->abbrev_parent_hashes.len = \n+\t\t\t\tsb->len - c->abbrev_parent_hashes.off;\n \t\treturn 1;\n \tcase 'm':\t\t/* left/right/bottom */\n \t\tstrbuf_addstr(sb, get_revision_mark(NULL, commit));\n@@ -1314,7 +1330,8 @@ static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \n static size_t format_and_pad_commit(struct strbuf *sb, /* in UTF-8 */\n \t\t\t\t const char *placeholder,\n-\t\t\t\t struct format_commit_context *c)\n+\t\t\t\t struct format_commit_context *c,\n+\t\t\t\t enum format_commit_item_magic magic)\n {\n \tstruct strbuf local_sb = STRBUF_INIT;\n \tint total_consumed = 0, len, padding = c->padding;\n@@ -1329,7 +1346,7 @@ static size_t format_and_pad_commit(struct strbuf *sb, /* in UTF-8 */\n \t}\n \twhile (1) {\n \t\tint modifier = *placeholder == 'C';\n-\t\tint consumed = format_commit_one(&local_sb, placeholder, c);\n+\t\tint consumed = format_commit_one(&local_sb, placeholder, c, magic);\n \t\ttotal_consumed += consumed;\n \n \t\tif (!modifier)\n@@ -1420,12 +1437,7 @@ static size_t format_commit_item(struct strbuf *sb, /* in UTF-8 */\n {\n \tint consumed;\n \tsize_t orig_len;\n-\tenum {\n-\t\tNO_MAGIC,\n-\t\tADD_LF_BEFORE_NON_EMPTY,\n-\t\tDEL_LF_BEFORE_EMPTY,\n-\t\tADD_SP_BEFORE_NON_EMPTY\n-\t} magic = NO_MAGIC;\n+\tenum format_commit_item_magic magic = NO_MAGIC;\n \n \tswitch (placeholder[0]) {\n \tcase '-':\n@@ -1445,9 +1457,9 @@ static size_t format_commit_item(struct strbuf *sb, /* in UTF-8 */\n \n \torig_len = sb->len;\n \tif (((struct format_commit_context *)context)->flush_type != no_flush)\n-\t\tconsumed = format_and_pad_commit(sb, placeholder, context);\n+\t\tconsumed = format_and_pad_commit(sb, placeholder, context, magic);\n \telse\n-\t\tconsumed = format_commit_one(sb, placeholder, context);\n+\t\tconsumed = format_commit_one(sb, placeholder, context, magic);\n \tif (magic == NO_MAGIC)\n \t\treturn consumed;\n \n"},{"id":"322127","messageId":"d229403a-d078-87b4-f3e8-89058fa4b548@web.de","threadId":"46155","inReplyTo":"xmqqd1a8n7o8.fsf@gitster.mtv.corp.google.com","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-06-13T18:09:17Z","receivedAt":"2017-06-13T18:09:38Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 13.06.2017 um 00:49 schrieb Junio C Hamano:\n> Michael Giuffrida writes:\n> \n>> For the abbreviated commit hash placeholder ('h'), pretty.c uses\n>> add_again() to cache the result of the expansion, and then uses that\n>> result in future expansions. This causes problems when the expansion\n>> includes whitespace:\n>>\n>> $ git log -n 1 --pretty='format:newline:%+h%nno_newline:%h'\n>> newline:\n>> a0b1c2d\n>> no_newline:\n>> a0b1c2\n>>\n>> The second expansion of the hash added an unwanted newline and removed\n>> the final character. It seemingly used the cached expansion *starting\n>> from the inserted newline*.\n>>\n>> The expected output is:\n>>\n>> $ git log -n 1 --pretty='format:newline:%+h%nno_newline:%h'\n>> newline:\n>> a0b1c2d\n>> no_newline:a0b1c2d\n> \n> Nicely explained. The add_again() mechanism caches an earlier\n> result by remembering the offset and the length in the strbuf the\n> formatted string is being accumulated to, but because %+x (and\n> probably %-x) magic placeholders futz with the result of\n> format_commit_one() in place, the cache goes out of sync, of course.\n\nIndeed, a very nice bug report!\n\n> I think the call to format_commit_one() needs to be taught to pass\n> 'magic' through, and then add_again() mechanism needs to be told not\n> to cache when magic is in effect, or something like that.\n> \n> Perhaps something along this line...?\n> \n> pretty.c | 64 ++++++++++++++++++++++++++++++++++++++--------------------------\n> 1 file changed, 38 insertions(+), 26 deletions(-)\n\nThat looks quite big. You even invent a way to classify magic. Does the\ncaching feature justify the added complexity? Alternatives:\n\n- Don't cache anymore, now that we have placeholders that change output\n on top of the original append-only ones. Yields a net code reduction.\n Duplicated %h, %t and %p will have to be resolved at each occurrence.\n\n- Provide some space for the cache instead of reusing the output, like\n a strbuf for each placeholder. Adds a memory allocation to each\n first occurrence of %h, %t and %p. Such a cache could be reused for\n multiple commits by truncating it instead of releasing; not sure how\n to pass it in nicely for it to survive a sequence of calls, though.\n\nRené\n"},{"id":"322129","messageId":"xmqqtw3j68rc.fsf@gitster.mtv.corp.google.com","threadId":"46155","inReplyTo":"d229403a-d078-87b4-f3e8-89058fa4b548@web.de","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-06-13T18:29:59Z","receivedAt":"2017-06-13T18:30:06Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Indeed, a very nice bug report!\n>\n>> I think the call to format_commit_one() needs to be taught to pass\n>> 'magic' through, and then add_again() mechanism needs to be told not\n>> to cache when magic is in effect, or something like that.\n>>\n>> Perhaps something along this line...?\n>>\n>> pretty.c | 64 ++++++++++++++++++++++++++++++++++++++--------------------------\n>> 1 file changed, 38 insertions(+), 26 deletions(-)\n>\n> That looks quite big. You even invent a way to classify magic. \n\nHmph, by \"a way to classify\", do you mean the enum? That thing was\nthere from before, just moved.\n\nAlso I think we do not have to change add_again() at all, because\nchunk->off tolerates being given a garbage value as long as\nchunk->len stays 0, and add_again() does not change chunk->len at\nall.\n\nWhich cuts the diffstat down to\n\n pretty.c | 40 +++++++++++++++++++++++++---------------\n 1 file changed, 25 insertions(+), 15 deletions(-)\n\n> Does the caching feature justify the added complexity?\n\nThat's a good question. I thought about your second alternative\nwhile adding the \"don't cache\" thing, but if we can measure and find\nout that we are not gaining much from caching, certainly that sounds\nmuch simpler.\n\n>\n> - Don't cache anymore, now that we have placeholders that change output\n> on top of the original append-only ones. Yields a net code reduction.\n> Duplicated %h, %t and %p will have to be resolved at each occurrence.\n>\n> - Provide some space for the cache instead of reusing the output, like\n> a strbuf for each placeholder. Adds a memory allocation to each\n> first occurrence of %h, %t and %p. Such a cache could be reused for\n> multiple commits by truncating it instead of releasing; not sure how\n> to pass it in nicely for it to survive a sequence of calls, though.\n>\n> René\n"},{"id":"322137","messageId":"99d19e5a-9f79-9c1e-3a23-7b2437b04ce9@web.de","threadId":"46155","inReplyTo":"xmqqtw3j68rc.fsf@gitster.mtv.corp.google.com","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-06-13T20:29:01Z","receivedAt":"2017-06-13T20:29:21Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 13.06.2017 um 20:29 schrieb Junio C Hamano:\n> René Scharfe writes:\n> \n>> Indeed, a very nice bug report!\n>>\n>>> I think the call to format_commit_one() needs to be taught to pass\n>>> 'magic' through, and then add_again() mechanism needs to be told not\n>>> to cache when magic is in effect, or something like that.\n>>>\n>>> Perhaps something along this line...?\n>>>\n>>> pretty.c | 64 ++++++++++++++++++++++++++++++++++++++--------------------------\n>>> 1 file changed, 38 insertions(+), 26 deletions(-)\n>>\n>> That looks quite big. You even invent a way to classify magic.\n> \n> Hmph, by \"a way to classify\", do you mean the enum? That thing was\n> there from before, just moved.\n\nOh, yes, sorry. I didn't even get that far into the patch. (I'll\nbetter go to bed after hitting send..)\n\n> Also I think we do not have to change add_again() at all, because\n> chunk->off tolerates being given a garbage value as long as\n> chunk->len stays 0, and add_again() does not change chunk->len at\n> all.\n> \n> Which cuts the diffstat down to\n> \n> pretty.c | 40 +++++++++++++++++++++++++---------------\n> 1 file changed, 25 insertions(+), 15 deletions(-)\n> \n>> Does the caching feature justify the added complexity?\n> \n> That's a good question. I thought about your second alternative\n> while adding the \"don't cache\" thing, but if we can measure and find\n> out that we are not gaining much from caching, certainly that sounds\n> much simpler.\n\nThe difference is about the same as the one between:\n\n\t$ time git log --format=\"\" >/dev/null\n\n\treal 0m0.463s\n\tuser 0m0.448s\n\tsys 0m0.012s\n\nand:\n\n\t$ time git log --format=\"%h\" >/dev/null\n\n\treal 0m1.062s\n\tuser 0m0.636s\n\tsys 0m0.416s\n\nWith caching duplicates are basically free and without it short\nhashes have to be looked up again. Other placeholders may reduce\nthe relative slowdown, depending on how expensive they are.\n\nForgot a third option, probably because it's not a particularly good\nidea: Replacing the caching in pretty.c with a short static cache in\nfind_unique_abbrev_r().\n\nRené\n"},{"id":"322155","messageId":"xmqqwp8f4mb2.fsf@gitster.mtv.corp.google.com","threadId":"46155","inReplyTo":"99d19e5a-9f79-9c1e-3a23-7b2437b04ce9@web.de","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-06-13T21:20:17Z","receivedAt":"2017-06-13T21:20:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> The difference is about the same as the one between:\n>\n> \t$ time git log --format=\"\" >/dev/null\n>\n> \treal 0m0.463s\n> \tuser 0m0.448s\n> \tsys 0m0.012s\n>\n> and:\n>\n> \t$ time git log --format=\"%h\" >/dev/null\n>\n> \treal 0m1.062s\n> \tuser 0m0.636s\n> \tsys 0m0.416s\n>\n> With caching duplicates are basically free and without it short\n> hashes have to be looked up again. Other placeholders may reduce\n> the relative slowdown, depending on how expensive they are.\n\nI think the real question is how likely people use more than one\noccurrence of the same thing in their custom format, and how deeply\nthey care that --format='%h %h' costs more than --format='%h'. The\ncost won't of course be double (because the main traversal costs\nwithout any output), but it would be rather unreasonable to expect\nthat --format='%h %h %h %h %h' to cost the same as --format='%h';\nafter all, Git is doing more for them ;-)\n\nSo in that sense, I am actually OK if we decide to remove the caching.\n\n> Forgot a third option, probably because it's not a particularly good\n> idea: Replacing the caching in pretty.c with a short static cache in\n> find_unique_abbrev_r().\n\nIndeed.\n"},{"id":"322166","messageId":"20170613222445.15575-1-szeder.dev@gmail.com","threadId":"46155","inReplyTo":"99d19e5a-9f79-9c1e-3a23-7b2437b04ce9@web.de","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2017-06-13T22:24:45Z","receivedAt":"2017-06-13T22:25:04Z","isPatch":false,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"[sorry for double post, forgot the mailing list...]\n\nTo throw in a fourth option, this one adjusts the expansions' cached\noffsets when the magic makes it necessary. It's not necessary for\n'%-', because it only makes a difference when the expansion is empty,\nand in that case\n\n - add_again() doesn't consider it cached,\n - and even if it did, the offset of a zero-length string wouldn't\n matter.\n\n pretty.c | 32 +++++++++++++++++++++-----------\n 1 file changed, 21 insertions(+), 11 deletions(-)\n\ndiff --git a/pretty.c b/pretty.c\nindex d0f86f5d8..69c4f2a21 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -1066,9 +1066,17 @@ static size_t parse_padding_placeholder(struct strbuf *sb,\n \treturn 0;\n }\n \n+enum format_commit_item_magic {\n+\tNO_MAGIC,\n+\tADD_LF_BEFORE_NON_EMPTY,\n+\tDEL_LF_BEFORE_EMPTY,\n+\tADD_SP_BEFORE_NON_EMPTY\n+};\n+\n static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \t\t\t\tconst char *placeholder,\n-\t\t\t\tvoid *context)\n+\t\t\t\tvoid *context,\n+\t\t\t\tenum format_commit_item_magic magic)\n {\n \tstruct format_commit_context *c = context;\n \tconst struct commit *commit = c->commit;\n@@ -1155,6 +1163,8 @@ static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \t\t\t\t\t c->pretty_ctx->abbrev);\n \t\tstrbuf_addstr(sb, diff_get_color(c->auto_color, DIFF_RESET));\n \t\tc->abbrev_commit_hash.len = sb->len - c->abbrev_commit_hash.off;\n+\t\tif (magic == ADD_LF_BEFORE_NON_EMPTY || magic == ADD_SP_BEFORE_NON_EMPTY)\n+\t\t\tc->abbrev_commit_hash.off++;\n \t\treturn 1;\n \tcase 'T':\t\t/* tree hash */\n \t\tstrbuf_addstr(sb, oid_to_hex(&commit->tree->object.oid));\n@@ -1165,6 +1175,8 @@ static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \t\tstrbuf_add_unique_abbrev(sb, commit->tree->object.oid.hash,\n \t\t\t\t\t c->pretty_ctx->abbrev);\n \t\tc->abbrev_tree_hash.len = sb->len - c->abbrev_tree_hash.off;\n+\t\tif (magic == ADD_LF_BEFORE_NON_EMPTY || magic == ADD_SP_BEFORE_NON_EMPTY)\n+\t\t\tc->abbrev_tree_hash.off++;\n \t\treturn 1;\n \tcase 'P':\t\t/* parent hashes */\n \t\tfor (p = commit->parents; p; p = p->next) {\n@@ -1184,6 +1196,8 @@ static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \t\t}\n \t\tc->abbrev_parent_hashes.len = sb->len -\n \t\t c->abbrev_parent_hashes.off;\n+\t\tif (magic == ADD_LF_BEFORE_NON_EMPTY || magic == ADD_SP_BEFORE_NON_EMPTY)\n+\t\t\tc->abbrev_parent_hashes.off++;\n \t\treturn 1;\n \tcase 'm':\t\t/* left/right/bottom */\n \t\tstrbuf_addstr(sb, get_revision_mark(NULL, commit));\n@@ -1314,7 +1328,8 @@ static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \n static size_t format_and_pad_commit(struct strbuf *sb, /* in UTF-8 */\n \t\t\t\t const char *placeholder,\n-\t\t\t\t struct format_commit_context *c)\n+\t\t\t\t struct format_commit_context *c,\n+\t\t\t\t enum format_commit_item_magic magic)\n {\n \tstruct strbuf local_sb = STRBUF_INIT;\n \tint total_consumed = 0, len, padding = c->padding;\n@@ -1329,7 +1344,7 @@ static size_t format_and_pad_commit(struct strbuf *sb, /* in UTF-8 */\n \t}\n \twhile (1) {\n \t\tint modifier = *placeholder == 'C';\n-\t\tint consumed = format_commit_one(&local_sb, placeholder, c);\n+\t\tint consumed = format_commit_one(&local_sb, placeholder, c, magic);\n \t\ttotal_consumed += consumed;\n \n \t\tif (!modifier)\n@@ -1420,12 +1435,7 @@ static size_t format_commit_item(struct strbuf *sb, /* in UTF-8 */\n {\n \tint consumed;\n \tsize_t orig_len;\n-\tenum {\n-\t\tNO_MAGIC,\n-\t\tADD_LF_BEFORE_NON_EMPTY,\n-\t\tDEL_LF_BEFORE_EMPTY,\n-\t\tADD_SP_BEFORE_NON_EMPTY\n-\t} magic = NO_MAGIC;\n+\tenum format_commit_item_magic magic = NO_MAGIC;\n \n \tswitch (placeholder[0]) {\n \tcase '-':\n@@ -1445,9 +1455,9 @@ static size_t format_commit_item(struct strbuf *sb, /* in UTF-8 */\n \n \torig_len = sb->len;\n \tif (((struct format_commit_context *)context)->flush_type != no_flush)\n-\t\tconsumed = format_and_pad_commit(sb, placeholder, context);\n+\t\tconsumed = format_and_pad_commit(sb, placeholder, context, magic);\n \telse\n-\t\tconsumed = format_commit_one(sb, placeholder, context);\n+\t\tconsumed = format_commit_one(sb, placeholder, context, magic);\n \tif (magic == NO_MAGIC)\n \t\treturn consumed;\n \n-- \n2.13.1.438.gc638325b1\n\n"},{"id":"322268","messageId":"1d4c9a93-5061-96db-d8aa-e798948650dc@web.de","threadId":"46155","inReplyTo":"20170613222445.15575-1-szeder.dev@gmail.com","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-06-14T17:34:26Z","receivedAt":"2017-06-14T17:34:43Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 14.06.2017 um 00:24 schrieb SZEDER Gábor:\n> [sorry for double post, forgot the mailing list...]\n> \n> To throw in a fourth option, this one adjusts the expansions' cached\n> offsets when the magic makes it necessary. It's not necessary for\n> '%-', because it only makes a difference when the expansion is empty,\n> and in that case\n> \n> - add_again() doesn't consider it cached,\n> - and even if it did, the offset of a zero-length string wouldn't\n> matter.\n> \n> pretty.c | 32 +++++++++++++++++++++-----------\n> 1 file changed, 21 insertions(+), 11 deletions(-)\n\nThere are other modifiers, e.g. try the format '%h%>(20)%h' -- its\noutput is obviously wrong (contains control characters), even with your\npatch. We'd have to update the offsets for each placeholder that\nchanges the output of others. I don't think that approach scales, alas.\n\nRené\n"},{"id":"322279","messageId":"dae96f72-761c-3ed1-4567-0933acc7618a@web.de","threadId":"46155","inReplyTo":"xmqqwp8f4mb2.fsf@gitster.mtv.corp.google.com","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-06-14T18:24:25Z","receivedAt":"2017-06-14T18:24:56Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 13.06.2017 um 23:20 schrieb Junio C Hamano:\n> René Scharfe writes:\n> \n>> The difference is about the same as the one between:\n>>\n>> \t$ time git log --format=\"\" >/dev/null\n>>\n>> \treal 0m0.463s\n>> \tuser 0m0.448s\n>> \tsys 0m0.012s\n>>\n>> and:\n>>\n>> \t$ time git log --format=\"%h\" >/dev/null\n>>\n>> \treal 0m1.062s\n>> \tuser 0m0.636s\n>> \tsys 0m0.416s\n>>\n>> With caching duplicates are basically free and without it short\n>> hashes have to be looked up again. Other placeholders may reduce\n>> the relative slowdown, depending on how expensive they are.\n> \n> I think the real question is how likely people use more than one\n> occurrence of the same thing in their custom format, and how deeply\n> they care that --format='%h %h' costs more than --format='%h'. The\n> cost won't of course be double (because the main traversal costs\n> without any output), but it would be rather unreasonable to expect\n> that --format='%h %h %h %h %h' to cost the same as --format='%h';\n> after all, Git is doing more for them ;-)\n\nThe answer to the first half is obviously \"very likely\" -- otherwise\nthis bug wouldn't have been found, right? :)\n\nRegarding the question of how bad a 50% slowdown for a second %h\nwould be: No idea. If ran interactively it may not even be noticeable\nbecause the user can read the first few lines in less while the rest\nis prepared in the background. We don't have a perf test for formats\nwith duplicate short hashes, so we don't promise anything, right? :)\n\nRené\n\n-- >8 --\nSubject: [PATCH] pretty: recalculate duplicate short hashes\n\nb9c6232138 (--format=pretty: avoid calculating expensive expansions\ntwice) optimized adding short hashes multiple times by using the\nfact that the output strbuf was only ever simply appended to and\ncopying the added string from the previous run. That prerequisite\nis no longer given; we now have modfiers like %< and %+ that can\ncause the cache to lose track of the correct offsets. Remove it.\n\nReported-by: Michael Giuffrida \nSigned-off-by: Rene Scharfe \n---\nI'm sending this out in the hope that there might be a simple way\nto fix it after all, like Gábor's patch does for %+. %< and %>\nseem to be the only other problematic modifiers for now -- I'm\nactually surprised that %w seems to be OK.\n\n pretty.c | 32 --------------------------------\n strbuf.c | 7 -------\n strbuf.h | 6 ------\n 3 files changed, 45 deletions(-)\n\ndiff --git a/pretty.c b/pretty.c\nindex 09701bd2ff..cc099dfdd1 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -783,29 +783,9 @@ struct format_commit_context {\n \tsize_t body_off;\n \n \t/* The following ones are relative to the result struct strbuf. */\n-\tstruct chunk abbrev_commit_hash;\n-\tstruct chunk abbrev_tree_hash;\n-\tstruct chunk abbrev_parent_hashes;\n \tsize_t wrap_start;\n };\n \n-static int add_again(struct strbuf *sb, struct chunk *chunk)\n-{\n-\tif (chunk->len) {\n-\t\tstrbuf_adddup(sb, chunk->off, chunk->len);\n-\t\treturn 1;\n-\t}\n-\n-\t/*\n-\t * We haven't seen this chunk before. Our caller is surely\n-\t * going to add it the hard way now. Remember the most likely\n-\t * start of the to-be-added chunk: the current end of the\n-\t * struct strbuf.\n-\t */\n-\tchunk->off = sb->len;\n-\treturn 0;\n-}\n-\n static void parse_commit_header(struct format_commit_context *context)\n {\n \tconst char *msg = context->message;\n@@ -1147,24 +1127,16 @@ static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \t\treturn 1;\n \tcase 'h':\t\t/* abbreviated commit hash */\n \t\tstrbuf_addstr(sb, diff_get_color(c->auto_color, DIFF_COMMIT));\n-\t\tif (add_again(sb, &c->abbrev_commit_hash)) {\n-\t\t\tstrbuf_addstr(sb, diff_get_color(c->auto_color, DIFF_RESET));\n-\t\t\treturn 1;\n-\t\t}\n \t\tstrbuf_add_unique_abbrev(sb, commit->object.oid.hash,\n \t\t\t\t\t c->pretty_ctx->abbrev);\n \t\tstrbuf_addstr(sb, diff_get_color(c->auto_color, DIFF_RESET));\n-\t\tc->abbrev_commit_hash.len = sb->len - c->abbrev_commit_hash.off;\n \t\treturn 1;\n \tcase 'T':\t\t/* tree hash */\n \t\tstrbuf_addstr(sb, oid_to_hex(&commit->tree->object.oid));\n \t\treturn 1;\n \tcase 't':\t\t/* abbreviated tree hash */\n-\t\tif (add_again(sb, &c->abbrev_tree_hash))\n-\t\t\treturn 1;\n \t\tstrbuf_add_unique_abbrev(sb, commit->tree->object.oid.hash,\n \t\t\t\t\t c->pretty_ctx->abbrev);\n-\t\tc->abbrev_tree_hash.len = sb->len - c->abbrev_tree_hash.off;\n \t\treturn 1;\n \tcase 'P':\t\t/* parent hashes */\n \t\tfor (p = commit->parents; p; p = p->next) {\n@@ -1174,16 +1146,12 @@ static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \t\t}\n \t\treturn 1;\n \tcase 'p':\t\t/* abbreviated parent hashes */\n-\t\tif (add_again(sb, &c->abbrev_parent_hashes))\n-\t\t\treturn 1;\n \t\tfor (p = commit->parents; p; p = p->next) {\n \t\t\tif (p != commit->parents)\n \t\t\t\tstrbuf_addch(sb, ' ');\n \t\t\tstrbuf_add_unique_abbrev(sb, p->item->object.oid.hash,\n \t\t\t\t\t\t c->pretty_ctx->abbrev);\n \t\t}\n-\t\tc->abbrev_parent_hashes.len = sb->len -\n-\t\t c->abbrev_parent_hashes.off;\n \t\treturn 1;\n \tcase 'm':\t\t/* left/right/bottom */\n \t\tstrbuf_addstr(sb, get_revision_mark(NULL, commit));\ndiff --git a/strbuf.c b/strbuf.c\nindex 00457940cf..9103bc75e4 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -204,13 +204,6 @@ void strbuf_addbuf(struct strbuf *sb, const struct strbuf *sb2)\n \tstrbuf_setlen(sb, sb->len + sb2->len);\n }\n \n-void strbuf_adddup(struct strbuf *sb, size_t pos, size_t len)\n-{\n-\tstrbuf_grow(sb, len);\n-\tmemcpy(sb->buf + sb->len, sb->buf + pos, len);\n-\tstrbuf_setlen(sb, sb->len + len);\n-}\n-\n void strbuf_addchars(struct strbuf *sb, int c, size_t n)\n {\n \tstrbuf_grow(sb, n);\ndiff --git a/strbuf.h b/strbuf.h\nindex 80047b1bb7..d785258649 100644\n--- a/strbuf.h\n+++ b/strbuf.h\n@@ -264,12 +264,6 @@ static inline void strbuf_addstr(struct strbuf *sb, const char *s)\n extern void strbuf_addbuf(struct strbuf *sb, const struct strbuf *sb2);\n \n /**\n- * Copy part of the buffer from a given position till a given length to the\n- * end of the buffer.\n- */\n-extern void strbuf_adddup(struct strbuf *sb, size_t pos, size_t len);\n-\n-/**\n * This function can be used to expand a format string containing\n * placeholders. To that end, it parses the string and calls the specified\n * function for every percent sign found.\n-- \n2.13.0\n\n"},{"id":"322294","messageId":"20170615055654.efvsouhr3leszz3i@sigill.intra.peff.net","threadId":"46155","inReplyTo":"dae96f72-761c-3ed1-4567-0933acc7618a@web.de","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-06-15T05:56:54Z","receivedAt":"2017-06-15T05:57:00Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 14, 2017 at 08:24:25PM +0200, René Scharfe wrote:\n\n> > I think the real question is how likely people use more than one\n> > occurrence of the same thing in their custom format, and how deeply\n> > they care that --format='%h %h' costs more than --format='%h'. The\n> > cost won't of course be double (because the main traversal costs\n> > without any output), but it would be rather unreasonable to expect\n> > that --format='%h %h %h %h %h' to cost the same as --format='%h';\n> > after all, Git is doing more for them ;-)\n> \n> The answer to the first half is obviously \"very likely\" -- otherwise\n> this bug wouldn't have been found, right? :)\n> \n> Regarding the question of how bad a 50% slowdown for a second %h\n> would be: No idea. If ran interactively it may not even be noticeable\n> because the user can read the first few lines in less while the rest\n> is prepared in the background. We don't have a perf test for formats\n> with duplicate short hashes, so we don't promise anything, right? :)\n\nOne interesting thing is that the cost of finding short hashes very much\ndepends on your loose object setup. I timed:\n\n git log --format=%H >/dev/null\n\nversus\n\n git log --format=%h >/dev/null\n\non git.git. It went from about 400ms to about 800ms. But then I noticed\nI had a lot of loose object directories, and ran \"git gc --prune=now\".\nAfterwards, my timings were more like 380ms and 460ms.\n\nThe difference is that in the \"before\" case, we actually opened each\ndirectory and ran getdents(). But after gc, the directories are gone\ntotally and open() fails. We also have to do a linear walk through the\nobjects in each directory, since the contents are sorted.\n\nSo I wonder if it is worth trying to optimize the short-sha1 computation\nin the first place. Double-%h aside, that would make _everything_\nfaster, including --oneline.\n\nI'm not really sure how, though, short of caching the directory\ncontents. That opens up questions of whether and when to invalidate the\ncache. If the cache were _just_ about short hashes, it might be OK to\njust assume that it remains valid through the length of the program (so\nworst case, a simultaneous write might mean that we generate a sha1\nwhich just became ambiguous, but that's generally going to be racy\nanyway).\n\nThe other downside of course is that we'd spend RAM on it. We could\nbound the size of the cache, I suppose.\n\n-Peff\n"},{"id":"322312","messageId":"ec36f9fa-5f3e-b511-3985-3d0301b4847f@web.de","threadId":"46155","inReplyTo":"20170615055654.efvsouhr3leszz3i@sigill.intra.peff.net","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-06-15T11:33:34Z","receivedAt":"2017-06-15T11:33:58Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 15.06.2017 um 07:56 schrieb Jeff King:\n> One interesting thing is that the cost of finding short hashes very much\n> depends on your loose object setup. I timed:\n> \n> git log --format=%H >/dev/null\n> \n> versus\n> \n> git log --format=%h >/dev/null\n> \n> on git.git. It went from about 400ms to about 800ms. But then I noticed\n> I had a lot of loose object directories, and ran \"git gc --prune=now\".\n> Afterwards, my timings were more like 380ms and 460ms.\n> \n> The difference is that in the \"before\" case, we actually opened each\n> directory and ran getdents(). But after gc, the directories are gone\n> totally and open() fails. We also have to do a linear walk through the\n> objects in each directory, since the contents are sorted.\n\nDo you mean \"unsorted\"?\n\n> So I wonder if it is worth trying to optimize the short-sha1 computation\n> in the first place. Double-%h aside, that would make _everything_\n> faster, including --oneline.\n\nRight.\n\n> I'm not really sure how, though, short of caching the directory\n> contents. That opens up questions of whether and when to invalidate the\n> cache. If the cache were _just_ about short hashes, it might be OK to\n> just assume that it remains valid through the length of the program (so\n> worst case, a simultaneous write might mean that we generate a sha1\n> which just became ambiguous, but that's generally going to be racy\n> anyway).\n> \n> The other downside of course is that we'd spend RAM on it. We could\n> bound the size of the cache, I suppose.\n\nYou mean like an in-memory pack index for loose objects? In order to\navoid the readdir call in sha1_name.c::find_short_object_filename()?\nWe'd only need to keep the hashes of found objects. An oid_array\nwould be quite compact.\n\nNon-racy writes inside a process should not be ignored (write, read\nlater) -- e.g. checkout does something like that.\n\nCan we trust object directory time stamps for cache invalidation?\n\nRené\n"},{"id":"322321","messageId":"20170615132532.nivmj22dctowxssm@sigill.intra.peff.net","threadId":"46155","inReplyTo":"ec36f9fa-5f3e-b511-3985-3d0301b4847f@web.de","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-06-15T13:25:32Z","receivedAt":"2017-06-15T13:25:39Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 15, 2017 at 01:33:34PM +0200, René Scharfe wrote:\n\n> > The difference is that in the \"before\" case, we actually opened each\n> > directory and ran getdents(). But after gc, the directories are gone\n> > totally and open() fails. We also have to do a linear walk through the\n> > objects in each directory, since the contents are sorted.\n> \n> Do you mean \"unsorted\"?\n\nEr yeah, sorry, I meant to say \"aren't\".\n\n> > I'm not really sure how, though, short of caching the directory\n> > contents. That opens up questions of whether and when to invalidate the\n> > cache. If the cache were _just_ about short hashes, it might be OK to\n> > just assume that it remains valid through the length of the program (so\n> > worst case, a simultaneous write might mean that we generate a sha1\n> > which just became ambiguous, but that's generally going to be racy\n> > anyway).\n> > \n> > The other downside of course is that we'd spend RAM on it. We could\n> > bound the size of the cache, I suppose.\n> \n> You mean like an in-memory pack index for loose objects? In order to\n> avoid the readdir call in sha1_name.c::find_short_object_filename()?\n> We'd only need to keep the hashes of found objects. An oid_array\n> would be quite compact.\n\nYes, that's what I was thinking of.\n\n> Non-racy writes inside a process should not be ignored (write, read\n> later) -- e.g. checkout does something like that.\n\nIdeally, yes. Though thinking on this more, it's racy even today,\nbecause we rely on the in-memory packed_git list. We usually re-check the\ndirectory only when we look for an object and it's missing. So any new\npacks which have been added while the process runs will be missed when\ndoing short-sha1 lookups (and actually, find_short_packed_object does\nnot even seem to do the usual retry-on-miss).\n\nA normal process like \"checkout\" isn't writing new packs, but a\nsimultaneous repack could be migrating its new objects to a pack behind\nits back. (It also _can_ write packs, but only for large blobs).\n\nGiven that we are talking about finding \"unique\" abbreviations here, and\nthat those abbreviations can become invalidated immediately anyway as\nmore objects are added (even by the same process), I'm not sure we need\nto strive for absolute accuracy.\n\n> Can we trust object directory time stamps for cache invalidation?\n\nI think it would work on POSIX-ish systems, since loose object changes\nalways involve new files, not modifications of existing ones. I don't\nknow if there are systems that don't update directory mtimes even for\nnewly added files.\n\nThat would still be a stat() per request. I'd be curious how the timing\ncompares to the opendir/readdir that happens now.\n\n-Peff\n"},{"id":"322373","messageId":"xmqqtw3h14hs.fsf@gitster.mtv.corp.google.com","threadId":"46155","inReplyTo":"dae96f72-761c-3ed1-4567-0933acc7618a@web.de","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-06-15T18:37:51Z","receivedAt":"2017-06-15T18:38:10Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Am 13.06.2017 um 23:20 schrieb Junio C Hamano:\n>\n>> I think the real question is how likely people use more than one\n>> occurrence of the same thing in their custom format, and how deeply\n>> they care that --format='%h %h' costs more than --format='%h'. The\n>> cost won't of course be double (because the main traversal costs\n>> without any output), but it would be rather unreasonable to expect\n>> that --format='%h %h %h %h %h' to cost the same as --format='%h';\n>> after all, Git is doing more for them ;-)\n>\n> The answer to the first half is obviously \"very likely\" -- otherwise\n> this bug wouldn't have been found, right? :)\n\nNot really. There was only one (this one) after all these years.\nThe question we are asking is not \"very rarely this is used and we\ncan afford to leave it broken?\" It is \"very rarely this is used\nand we can afford not to optimize for that rare use case?\".\n\n> Regarding the question of how bad a 50% slowdown for a second %h\n> would be: No idea. If ran interactively it may not even be noticeable\n> because the user can read the first few lines in less while the rest\n> is prepared in the background. We don't have a perf test for formats\n> with duplicate short hashes, so we don't promise anything, right? :)\n\nOK.\n\n> -- >8 --\n> Subject: [PATCH] pretty: recalculate duplicate short hashes\n>\n> b9c6232138 (--format=pretty: avoid calculating expensive expansions\n> twice) optimized adding short hashes multiple times by using the\n> fact that the output strbuf was only ever simply appended to and\n> copying the added string from the previous run. That prerequisite\n> is no longer given; we now have modfiers like %< and %+ that can\n> cause the cache to lose track of the correct offsets. Remove it.\n>\n> Reported-by: Michael Giuffrida \n> Signed-off-by: Rene Scharfe \n> ---\n> I'm sending this out in the hope that there might be a simple way\n> to fix it after all, like Gábor's patch does for %+. %< and %>\n> seem to be the only other problematic modifiers for now -- I'm\n> actually surprised that %w seems to be OK.\n\nThanks, this looks like a sensible first step. Will queue.\n"},{"id":"322520","messageId":"b0bc9dab-bd93-c321-9f2e-f1621f857708@web.de","threadId":"46155","inReplyTo":"20170615132532.nivmj22dctowxssm@sigill.intra.peff.net","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-06-18T10:58:37Z","receivedAt":"2017-06-18T10:59:11Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 15.06.2017 um 15:25 schrieb Jeff King:\n> On Thu, Jun 15, 2017 at 01:33:34PM +0200, René Scharfe wrote:\n>>> I'm not really sure how, though, short of caching the directory\n>>> contents. That opens up questions of whether and when to invalidate the\n>>> cache. If the cache were _just_ about short hashes, it might be OK to\n>>> just assume that it remains valid through the length of the program (so\n>>> worst case, a simultaneous write might mean that we generate a sha1\n>>> which just became ambiguous, but that's generally going to be racy\n>>> anyway).\n>>>\n>>> The other downside of course is that we'd spend RAM on it. We could\n>>> bound the size of the cache, I suppose.\n>>\n>> You mean like an in-memory pack index for loose objects? In order to\n>> avoid the readdir call in sha1_name.c::find_short_object_filename()?\n>> We'd only need to keep the hashes of found objects. An oid_array\n>> would be quite compact.\n> \n> Yes, that's what I was thinking of.\n\nAn oid_array spends ca. 30 bytes per entry (20 bytes for a hash times\na factor of 1.5 from alloc_nr). How many loose objects do we have to\nexpect? 30 MB for a million of them sounds not too bad, but can there\nrealistically be orders of magnitude more?\n\n>> Non-racy writes inside a process should not be ignored (write, read\n>> later) -- e.g. checkout does something like that.\n> \n> Ideally, yes. Though thinking on this more, it's racy even today,\n> because we rely on the in-memory packed_git list. We usually re-check the\n> directory only when we look for an object and it's missing. So any new\n> packs which have been added while the process runs will be missed when\n> doing short-sha1 lookups (and actually, find_short_packed_object does\n> not even seem to do the usual retry-on-miss).\n> \n> A normal process like \"checkout\" isn't writing new packs, but a\n> simultaneous repack could be migrating its new objects to a pack behind\n> its back. (It also _can_ write packs, but only for large blobs).\n> \n> Given that we are talking about finding \"unique\" abbreviations here, and\n> that those abbreviations can become invalidated immediately anyway as\n> more objects are added (even by the same process), I'm not sure we need\n> to strive for absolute accuracy.\n\nAgreed. And processes that add objects and use them later probably use\nfull hashes (at least checkout does).\n\nSo here's a patch for caching loose object hashes in an oid_array\nwithout a way to invalidate or release the cache. It uses a single\noid_array for simplicity, but reads each subdirectory individually and\nremembers that fact using a bitmap.\n---\n cache.h | 4 ++++\n sha1_name.c | 69 +++++++++++++++++++++++++++++++++++++++++++------------------\n 2 files changed, 53 insertions(+), 20 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 4d92aae0e8..8c6748907b 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -11,6 +11,7 @@\n #include \"string-list.h\"\n #include \"pack-revindex.h\"\n #include \"hash.h\"\n+#include \"sha1-array.h\"\n \n #ifndef platform_SHA_CTX\n /*\n@@ -1586,6 +1587,9 @@ extern struct alternate_object_database {\n \tstruct strbuf scratch;\n \tsize_t base_len;\n \n+\tuint32_t loose_objects_subdir_bitmap[8];\n+\tstruct oid_array loose_objects_cache;\n+\n \tchar path[FLEX_ARRAY];\n } *alt_odb_list;\n extern void prepare_alt_odb(void);\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 5126853bb5..ae6a5c3abe 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -77,10 +77,46 @@ static void update_candidates(struct disambiguate_state *ds, const struct object\n \t/* otherwise, current can be discarded and candidate is still good */\n }\n \n+static void read_loose_object_subdir(struct alternate_object_database *alt,\n+\t\t\t\t int subdir_nr)\n+{\n+\tstruct strbuf *buf;\n+\tchar hex[GIT_MAX_HEXSZ];\n+\tDIR *dir;\n+\tstruct dirent *de;\n+\tsize_t bitmap_index = subdir_nr / 32;\n+\tuint32_t bitmap_mask = 1 << (subdir_nr % 32);\n+\n+\tif (alt->loose_objects_subdir_bitmap[bitmap_index] & bitmap_mask)\n+\t\treturn;\n+\talt->loose_objects_subdir_bitmap[bitmap_index] |= bitmap_mask;\n+\n+\tbuf = alt_scratch_buf(alt);\n+\tstrbuf_addf(buf, \"%02x/\", subdir_nr);\n+\txsnprintf(hex, sizeof(hex), \"%02x\", subdir_nr);\n+\n+\tdir = opendir(buf->buf);\n+\tif (!dir)\n+\t\treturn;\n+\n+\twhile ((de = readdir(dir)) != NULL) {\n+\t\tstruct object_id oid;\n+\n+\t\tif (strlen(de->d_name) != GIT_SHA1_HEXSZ - 2)\n+\t\t\tcontinue;\n+\t\tmemcpy(hex + 2, de->d_name, GIT_SHA1_HEXSZ - 2);\n+\t\tif (!get_oid_hex(hex, &oid))\n+\t\t\toid_array_append(&alt->loose_objects_cache, &oid);\n+\t}\n+\tclosedir(dir);\n+}\n+\n+static int match_sha(unsigned, const unsigned char *, const unsigned char *);\n+\n static void find_short_object_filename(struct disambiguate_state *ds)\n {\n+\tint subdir_nr = ds->bin_pfx.hash[0];\n \tstruct alternate_object_database *alt;\n-\tchar hex[GIT_MAX_HEXSZ];\n \tstatic struct alternate_object_database *fakeent;\n \n \tif (!fakeent) {\n@@ -95,29 +131,22 @@ static void find_short_object_filename(struct disambiguate_state *ds)\n \t}\n \tfakeent->next = alt_odb_list;\n \n-\txsnprintf(hex, sizeof(hex), \"%.2s\", ds->hex_pfx);\n \tfor (alt = fakeent; alt && !ds->ambiguous; alt = alt->next) {\n-\t\tstruct strbuf *buf = alt_scratch_buf(alt);\n-\t\tstruct dirent *de;\n-\t\tDIR *dir;\n-\n-\t\tstrbuf_addf(buf, \"%.2s/\", ds->hex_pfx);\n-\t\tdir = opendir(buf->buf);\n-\t\tif (!dir)\n-\t\t\tcontinue;\n+\t\tint pos;\n \n-\t\twhile (!ds->ambiguous && (de = readdir(dir)) != NULL) {\n-\t\t\tstruct object_id oid;\n+\t\tread_loose_object_subdir(alt, subdir_nr);\n \n-\t\t\tif (strlen(de->d_name) != GIT_SHA1_HEXSZ - 2)\n-\t\t\t\tcontinue;\n-\t\t\tif (memcmp(de->d_name, ds->hex_pfx + 2, ds->len - 2))\n-\t\t\t\tcontinue;\n-\t\t\tmemcpy(hex + 2, de->d_name, GIT_SHA1_HEXSZ - 2);\n-\t\t\tif (!get_oid_hex(hex, &oid))\n-\t\t\t\tupdate_candidates(ds, &oid);\n+\t\tpos = oid_array_lookup(&alt->loose_objects_cache, &ds->bin_pfx);\n+\t\tif (pos < 0)\n+\t\t\tpos = -1 - pos;\n+\t\twhile (!ds->ambiguous && pos < alt->loose_objects_cache.nr) {\n+\t\t\tconst struct object_id *oid;\n+\t\t\toid = alt->loose_objects_cache.oid + pos;\n+\t\t\tif (!match_sha(ds->len, ds->bin_pfx.hash, oid->hash))\n+\t\t\t\tbreak;\n+\t\t\tupdate_candidates(ds, oid);\n+\t\t\tpos++;\n \t\t}\n-\t\tclosedir(dir);\n \t}\n }\n \n-- \n2.13.0\n"},{"id":"322521","messageId":"b728352d-7fa5-2adb-af00-5f232b85b2bf@web.de","threadId":"46155","inReplyTo":"20170615132532.nivmj22dctowxssm@sigill.intra.peff.net","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-06-18T10:58:49Z","receivedAt":"2017-06-18T10:59:15Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 15.06.2017 um 15:25 schrieb Jeff King:\n> On Thu, Jun 15, 2017 at 01:33:34PM +0200, René Scharfe wrote:\n>> Can we trust object directory time stamps for cache invalidation?\n> \n> I think it would work on POSIX-ish systems, since loose object changes\n> always involve new files, not modifications of existing ones. I don't\n> know if there are systems that don't update directory mtimes even for\n> newly added files.\n> \n> That would still be a stat() per request. I'd be curious how the timing\n> compares to the opendir/readdir that happens now.\n\nModification times wouldn't be exact, as you mentioned above: An object\ncould be added just after checking the time stamp. So perhaps we don't\nneed that, or a time-based invalidation suffices, e.g. we discard the\ncache after five minutes or so?\n\nAnyway, here's a patch for stat-based invalidation, on top of the other\none. Array removal is really slow (hope I didn't sneak a bug in there,\nbut my confidence in this code isn't very high). No locking is done;\nparallel threads removing and adding entries could make a mess, but\nthat's not an issue for log.\n\nTimings for \"time git log --pretty=%h >/dev/null\" in my git repository\nwith 5094 loose objects on Debian:\n\n master first patch this patch\nreal 0m1.065s 0m0.581s 0m0.633s\nuser 0m0.648s 0m0.564s 0m0.580s\nsys 0m0.412s 0m0.016s 0m0.052s\n\n\nAnd on mingw with 227 loose objects:\n\n master first patch this patch\nreal 0m1.756s 0m0.546s 0m1.659s\nuser 0m0.000s 0m0.000s 0m0.000s\nsys 0m0.000s 0m0.000s 0m0.000s\n\nSo at least for Windows it would be really nice if we could avoid\ncalling stat..\n---\n cache.h | 1 +\n sha1_name.c | 32 ++++++++++++++++++++++++++++----\n 2 files changed, 29 insertions(+), 4 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 8c6748907b..386b09710d 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1589,6 +1589,7 @@ extern struct alternate_object_database {\n \n \tuint32_t loose_objects_subdir_bitmap[8];\n \tstruct oid_array loose_objects_cache;\n+\ttime_t loose_objects_subdir_mtime[256];\n \n \tchar path[FLEX_ARRAY];\n } *alt_odb_list;\ndiff --git a/sha1_name.c b/sha1_name.c\nindex ae6a5c3abe..baecb10454 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -77,6 +77,24 @@ static void update_candidates(struct disambiguate_state *ds, const struct object\n \t/* otherwise, current can be discarded and candidate is still good */\n }\n \n+static void remove_subdir_entries(struct oid_array *array, int subdir_nr)\n+{\n+\tstruct object_id oid;\n+\tint start, end;\n+\n+\tmemset(&oid, 0, sizeof(oid));\n+\toid.hash[0] = subdir_nr;\n+\tstart = oid_array_lookup(array, &oid);\n+\tif (start < 0)\n+\t\tstart = -1 - start;\n+\tend = start;\n+\twhile (end < array->nr && array->oid[end].hash[0] == subdir_nr)\n+\t\tend++;\n+\tmemmove(array->oid + start, array->oid + end,\n+\t\t(array->nr - end) * sizeof(array->oid[0]));\n+\tarray->nr -= end - start;\n+}\n+\n static void read_loose_object_subdir(struct alternate_object_database *alt,\n \t\t\t\t int subdir_nr)\n {\n@@ -86,15 +104,21 @@ static void read_loose_object_subdir(struct alternate_object_database *alt,\n \tstruct dirent *de;\n \tsize_t bitmap_index = subdir_nr / 32;\n \tuint32_t bitmap_mask = 1 << (subdir_nr % 32);\n-\n-\tif (alt->loose_objects_subdir_bitmap[bitmap_index] & bitmap_mask)\n-\t\treturn;\n-\talt->loose_objects_subdir_bitmap[bitmap_index] |= bitmap_mask;\n+\tstruct stat st;\n \n \tbuf = alt_scratch_buf(alt);\n \tstrbuf_addf(buf, \"%02x/\", subdir_nr);\n \txsnprintf(hex, sizeof(hex), \"%02x\", subdir_nr);\n \n+\tstat(buf->buf, &st);\n+\tif (alt->loose_objects_subdir_bitmap[bitmap_index] & bitmap_mask) {\n+\t\tif (alt->loose_objects_subdir_mtime[subdir_nr] == st.st_mtime)\n+\t\t\treturn;\n+\t\tremove_subdir_entries(&alt->loose_objects_cache, subdir_nr);\n+\t}\n+\talt->loose_objects_subdir_mtime[subdir_nr] = st.st_mtime;\n+\talt->loose_objects_subdir_bitmap[bitmap_index] |= bitmap_mask;\n+\n \tdir = opendir(buf->buf);\n \tif (!dir)\n \t\treturn;\n-- \n2.13.0\n"},{"id":"322523","messageId":"20170618114923.bffmbr5dqe4oivyw@sigill.intra.peff.net","threadId":"46155","inReplyTo":"b0bc9dab-bd93-c321-9f2e-f1621f857708@web.de","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-06-18T11:49:23Z","receivedAt":"2017-06-18T11:49:33Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jun 18, 2017 at 12:58:37PM +0200, René Scharfe wrote:\n\n> An oid_array spends ca. 30 bytes per entry (20 bytes for a hash times\n> a factor of 1.5 from alloc_nr). How many loose objects do we have to\n> expect? 30 MB for a million of them sounds not too bad, but can there\n> realistically be orders of magnitude more?\n\nGood point. We gc by default at 6000 loose objects, and lots of thing\nwill suffer poor performance by the time you hit a million. So a little\nextra space is probably not worth worrying about.\n\n> So here's a patch for caching loose object hashes in an oid_array\n> without a way to invalidate or release the cache. It uses a single\n> oid_array for simplicity, but reads each subdirectory individually and\n> remembers that fact using a bitmap.\n\nI like the direction of this very much.\n\n> @@ -1586,6 +1587,9 @@ extern struct alternate_object_database {\n> \tstruct strbuf scratch;\n> \tsize_t base_len;\n> \n> +\tuint32_t loose_objects_subdir_bitmap[8];\n\nIs it worth the complexity of having an actual bitmap and not just an\narray of char? I guess it's not _that_ complex to access the bits, but\nthere are a lot of magic numbers involved.\n\n> +\tstruct oid_array loose_objects_cache;\n\nWe should probably insert a comment here warning that the cache may go\nout of date during the process run, and should only be used when that's\nan acceptable tradeoff.\n\n> +static void read_loose_object_subdir(struct alternate_object_database *alt,\n> +\t\t\t\t int subdir_nr)\n\nI think it's nice to pull this out into a helper function. I do wonder\nif it should just be reusing for_each_loose_file_in_objdir(). You'd just\nneed to expose the in_obj_subdir() variant publicly.\n\nIt does do slightly more than we need (for the callbacks it actually\nbuilds the filename), but I doubt memcpy()ing a few bytes would be\nmeasurable.\n\n> +\t\tpos = oid_array_lookup(&alt->loose_objects_cache, &ds->bin_pfx);\n> +\t\tif (pos < 0)\n> +\t\t\tpos = -1 - pos;\n> +\t\twhile (!ds->ambiguous && pos < alt->loose_objects_cache.nr) {\n> +\t\t\tconst struct object_id *oid;\n> +\t\t\toid = alt->loose_objects_cache.oid + pos;\n> +\t\t\tif (!match_sha(ds->len, ds->bin_pfx.hash, oid->hash))\n> +\t\t\t\tbreak;\n> +\t\t\tupdate_candidates(ds, oid);\n> +\t\t\tpos++;\n> \t\t}\n\nThis part looks quite nice and straightforward.\n\n-Peff\n"},{"id":"322524","messageId":"20170618115017.wyroncb3jka6lrdt@sigill.intra.peff.net","threadId":"46155","inReplyTo":"b728352d-7fa5-2adb-af00-5f232b85b2bf@web.de","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-06-18T11:50:17Z","receivedAt":"2017-06-18T11:50:23Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jun 18, 2017 at 12:58:49PM +0200, René Scharfe wrote:\n\n> Anyway, here's a patch for stat-based invalidation, on top of the other\n> one. Array removal is really slow (hope I didn't sneak a bug in there,\n> but my confidence in this code isn't very high). No locking is done;\n> parallel threads removing and adding entries could make a mess, but\n> that's not an issue for log.\n> \n> Timings for \"time git log --pretty=%h >/dev/null\" in my git repository\n> with 5094 loose objects on Debian:\n> \n> master first patch this patch\n> real 0m1.065s 0m0.581s 0m0.633s\n> user 0m0.648s 0m0.564s 0m0.580s\n> sys 0m0.412s 0m0.016s 0m0.052s\n> \n> \n> And on mingw with 227 loose objects:\n> \n> master first patch this patch\n> real 0m1.756s 0m0.546s 0m1.659s\n> user 0m0.000s 0m0.000s 0m0.000s\n> sys 0m0.000s 0m0.000s 0m0.000s\n> \n> So at least for Windows it would be really nice if we could avoid\n> calling stat..\n\nThanks for doing the timings. Given those numbers and the earlier\ndiscussion, I'd be inclined to skip the mtime check.\n\n-Peff\n"},{"id":"322525","messageId":"96c26ba2-8548-1693-e803-3a3434ae3a62@web.de","threadId":"46155","inReplyTo":"20170618114923.bffmbr5dqe4oivyw@sigill.intra.peff.net","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-06-18T12:59:04Z","receivedAt":"2017-06-18T12:59:26Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 18.06.2017 um 13:49 schrieb Jeff King:\n> On Sun, Jun 18, 2017 at 12:58:37PM +0200, René Scharfe wrote:\n> \n>> An oid_array spends ca. 30 bytes per entry (20 bytes for a hash times\n>> a factor of 1.5 from alloc_nr). How many loose objects do we have to\n>> expect? 30 MB for a million of them sounds not too bad, but can there\n>> realistically be orders of magnitude more?\n> \n> Good point. We gc by default at 6000 loose objects, and lots of thing\n> will suffer poor performance by the time you hit a million. So a little\n> extra space is probably not worth worrying about.\n> \n>> So here's a patch for caching loose object hashes in an oid_array\n>> without a way to invalidate or release the cache. It uses a single\n>> oid_array for simplicity, but reads each subdirectory individually and\n>> remembers that fact using a bitmap.\n> \n> I like the direction of this very much.\n> \n>> @@ -1586,6 +1587,9 @@ extern struct alternate_object_database {\n>> \tstruct strbuf scratch;\n>> \tsize_t base_len;\n>> \n>> +\tuint32_t loose_objects_subdir_bitmap[8];\n> \n> Is it worth the complexity of having an actual bitmap and not just an\n> array of char? I guess it's not _that_ complex to access the bits, but\n> there are a lot of magic numbers involved.\n\nThat would be 224 bytes more per alternate_object_database, and we'd\ngain simpler code. Hmm. We could add some bitmap helper macros, but\nyou're probably right that the first version should use the simplest\nform for representing small bitmaps that we currently have.\n\n>> +\tstruct oid_array loose_objects_cache;\n> \n> We should probably insert a comment here warning that the cache may go\n> out of date during the process run, and should only be used when that's\n> an acceptable tradeoff.\n\nThen we need to offer a way for opting out. Through a global variable?\n(I'd rather reduce their number, but don't see how allow programs to\nnicely toggle this cache otherwise.)\n\n>> +static void read_loose_object_subdir(struct alternate_object_database *alt,\n>> +\t\t\t\t int subdir_nr)\n> \n> I think it's nice to pull this out into a helper function. I do wonder\n> if it should just be reusing for_each_loose_file_in_objdir(). You'd just\n> need to expose the in_obj_subdir() variant publicly.\n> \n> It does do slightly more than we need (for the callbacks it actually\n> builds the filename), but I doubt memcpy()ing a few bytes would be\n> measurable.\n\nGood point. The function also copies the common first two hex digits\nfor each entry. But all that extra work is certainly dwarfed by the\nreaddir calls.\n\nRené\n"},{"id":"322530","messageId":"20170618135623.3b27zhzdxur6gpg3@sigill.intra.peff.net","threadId":"46155","inReplyTo":"96c26ba2-8548-1693-e803-3a3434ae3a62@web.de","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-06-18T13:56:23Z","receivedAt":"2017-06-18T13:56:31Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jun 18, 2017 at 02:59:04PM +0200, René Scharfe wrote:\n\n> > > @@ -1586,6 +1587,9 @@ extern struct alternate_object_database {\n> > > \tstruct strbuf scratch;\n> > > \tsize_t base_len;\n> > > +\tuint32_t loose_objects_subdir_bitmap[8];\n> > \n> > Is it worth the complexity of having an actual bitmap and not just an\n> > array of char? I guess it's not _that_ complex to access the bits, but\n> > there are a lot of magic numbers involved.\n> \n> That would be 224 bytes more per alternate_object_database, and we'd\n> gain simpler code. Hmm. We could add some bitmap helper macros, but\n> you're probably right that the first version should use the simplest\n> form for representing small bitmaps that we currently have.\n\nI'd be OK with keeping it if we could reduce the number of magic\nnumbers. E.g,. rather than 32 elsewhere use:\n\n (sizeof(*loose_objects_subdir_bitmap) * CHAR_BIT)\n\nand similarly rather than 8 here use\n\n 256 / sizeof(*loose_objects_subdir_bitmap) / CHAR_BIT\n\nThere's also already a bitmap data structure in ewah/bitmap.c. It's a\nlittle bit overkill, though, because it mallocs and will grow the bitmap\nas needed.\n\n> > We should probably insert a comment here warning that the cache may go\n> > out of date during the process run, and should only be used when that's\n> > an acceptable tradeoff.\n> \n> Then we need to offer a way for opting out. Through a global variable?\n> (I'd rather reduce their number, but don't see how allow programs to\n> nicely toggle this cache otherwise.)\n\nSorry, I didn't mean disabling it for a particular run of a program. I\njust meant that we know this is an OK tradeoff for short-sha1 lookups,\nbut has_sha1_file(), for example, would never want to use it. So we are\nwarning programmers from using it in more code, not giving users a way\nto turn it off run-to-run.\n\n> > > +static void read_loose_object_subdir(struct alternate_object_database *alt,\n> > > +\t\t\t\t int subdir_nr)\n> > \n> > I think it's nice to pull this out into a helper function. I do wonder\n> > if it should just be reusing for_each_loose_file_in_objdir(). You'd just\n> > need to expose the in_obj_subdir() variant publicly.\n> > \n> > It does do slightly more than we need (for the callbacks it actually\n> > builds the filename), but I doubt memcpy()ing a few bytes would be\n> > measurable.\n> \n> Good point. The function also copies the common first two hex digits\n> for each entry. But all that extra work is certainly dwarfed by the\n> readdir calls.\n\nYes. You're welcome to micro-optimize that implementation if you want. ;)\n\n-Peff\n"},{"id":"322546","messageId":"xmqqd1a0vb2t.fsf@gitster.mtv.corp.google.com","threadId":"46155","inReplyTo":"20170618115017.wyroncb3jka6lrdt@sigill.intra.peff.net","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-06-19T04:46:34Z","receivedAt":"2017-06-19T04:46:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Sun, Jun 18, 2017 at 12:58:49PM +0200, René Scharfe wrote:\n>\n>> Anyway, here's a patch for stat-based invalidation, on top of the other\n>> one. Array removal is really slow (hope I didn't sneak a bug in there,\n>> but my confidence in this code isn't very high). No locking is done;\n>> parallel threads removing and adding entries could make a mess, but\n>> that's not an issue for log.\n>> \n>> Timings for \"time git log --pretty=%h >/dev/null\" in my git repository\n>> with 5094 loose objects on Debian:\n>> \n>> master first patch this patch\n>> real 0m1.065s 0m0.581s 0m0.633s\n>> user 0m0.648s 0m0.564s 0m0.580s\n>> sys 0m0.412s 0m0.016s 0m0.052s\n>> \n>> \n>> And on mingw with 227 loose objects:\n>> \n>> master first patch this patch\n>> real 0m1.756s 0m0.546s 0m1.659s\n>> user 0m0.000s 0m0.000s 0m0.000s\n>> sys 0m0.000s 0m0.000s 0m0.000s\n>> \n>> So at least for Windows it would be really nice if we could avoid\n>> calling stat..\n>\n> Thanks for doing the timings. Given those numbers and the earlier\n> discussion, I'd be inclined to skip the mtime check.\n\nYeah, thanks for these experiments. With or without invalidation,\nwe already accept that racing with other processes will make the\nresult inaccurate, so I am also inclined to say that it would be\nbest to take the first one alone.\n\n"},{"id":"322938","messageId":"d06fb033-294e-f364-3dde-394624e83cd6@web.de","threadId":"46155","inReplyTo":"xmqqd1a0vb2t.fsf@gitster.mtv.corp.google.com","subject":"[PATCH] sha1_name: cache readdir(3) results in find_short_object_filename()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-06-22T18:19:48Z","receivedAt":"2017-06-22T18:20:11Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Read each loose object subdirectory at most once when looking for unique\nabbreviated hashes. This speeds up commands like \"git log --pretty=%h\"\nconsiderably, which previously caused one readdir(3) call for each\ncandidate, even for subdirectories that were visited before.\n\nThe new cache is kept until the program ends and never invalidated. The\nsame is already true for pack indexes. The inherent racy nature of\nfinding unique short hashes makes it still fit for this purpose -- a\nconflicting new object may be added at any time. Tasks with higher\nconsistency requirements should not use it, though.\n\nThe cached object names are stored in an oid_array, which is quite\ncompact. The bitmap for remembering which subdir was already read is\nstored as a char array, with one char per directory -- that's not quite\nas compact, but really simple and incurs only an overhead equivalent to\n11 hashes after all.\n\nSuggested-by: Jeff King \nHelped-by: Jeff King \nSigned-off-by: Rene Scharfe \n---\n cache.h | 17 +++++++++++++++++\n sha1_file.c | 12 ++++++------\n sha1_name.c | 50 ++++++++++++++++++++++++++++++--------------------\n 3 files changed, 53 insertions(+), 26 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex d6ba8a2f11..00a017dfcb 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -11,6 +11,7 @@\n #include \"string-list.h\"\n #include \"pack-revindex.h\"\n #include \"hash.h\"\n+#include \"sha1-array.h\"\n \n #ifndef platform_SHA_CTX\n /*\n@@ -1593,6 +1594,16 @@ extern struct alternate_object_database {\n \tstruct strbuf scratch;\n \tsize_t base_len;\n \n+\t/*\n+\t * Used to store the results of readdir(3) calls when searching\n+\t * for unique abbreviated hashes. This cache is never\n+\t * invalidated, thus it's racy and not necessarily accurate.\n+\t * That's fine for its purpose; don't use it for tasks requiring\n+\t * greater accuracy!\n+\t */\n+\tchar loose_objects_subdir_seen[256];\n+\tstruct oid_array loose_objects_cache;\n+\n \tchar path[FLEX_ARRAY];\n } *alt_odb_list;\n extern void prepare_alt_odb(void);\n@@ -1811,6 +1822,12 @@ typedef int each_loose_cruft_fn(const char *basename,\n typedef int each_loose_subdir_fn(int nr,\n \t\t\t\t const char *path,\n \t\t\t\t void *data);\n+int for_each_file_in_obj_subdir(int subdir_nr,\n+\t\t\t\tstruct strbuf *path,\n+\t\t\t\teach_loose_object_fn obj_cb,\n+\t\t\t\teach_loose_cruft_fn cruft_cb,\n+\t\t\t\teach_loose_subdir_fn subdir_cb,\n+\t\t\t\tvoid *data);\n int for_each_loose_file_in_objdir(const char *path,\n \t\t\t\t each_loose_object_fn obj_cb,\n \t\t\t\t each_loose_cruft_fn cruft_cb,\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 59a4ed2ed3..5e0ee2b68b 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -3735,12 +3735,12 @@ void assert_sha1_type(const unsigned char *sha1, enum object_type expect)\n \t\t typename(expect));\n }\n \n-static int for_each_file_in_obj_subdir(int subdir_nr,\n-\t\t\t\t struct strbuf *path,\n-\t\t\t\t each_loose_object_fn obj_cb,\n-\t\t\t\t each_loose_cruft_fn cruft_cb,\n-\t\t\t\t each_loose_subdir_fn subdir_cb,\n-\t\t\t\t void *data)\n+int for_each_file_in_obj_subdir(int subdir_nr,\n+\t\t\t\tstruct strbuf *path,\n+\t\t\t\teach_loose_object_fn obj_cb,\n+\t\t\t\teach_loose_cruft_fn cruft_cb,\n+\t\t\t\teach_loose_subdir_fn subdir_cb,\n+\t\t\t\tvoid *data)\n {\n \tsize_t baselen = path->len;\n \tDIR *dir = opendir(path->buf);\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 5126853bb5..ccb5144d0d 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -77,10 +77,19 @@ static void update_candidates(struct disambiguate_state *ds, const struct object\n \t/* otherwise, current can be discarded and candidate is still good */\n }\n \n+static int append_loose_object(const struct object_id *oid, const char *path,\n+\t\t\t void *data)\n+{\n+\toid_array_append(data, oid);\n+\treturn 0;\n+}\n+\n+static int match_sha(unsigned, const unsigned char *, const unsigned char *);\n+\n static void find_short_object_filename(struct disambiguate_state *ds)\n {\n+\tint subdir_nr = ds->bin_pfx.hash[0];\n \tstruct alternate_object_database *alt;\n-\tchar hex[GIT_MAX_HEXSZ];\n \tstatic struct alternate_object_database *fakeent;\n \n \tif (!fakeent) {\n@@ -95,29 +104,30 @@ static void find_short_object_filename(struct disambiguate_state *ds)\n \t}\n \tfakeent->next = alt_odb_list;\n \n-\txsnprintf(hex, sizeof(hex), \"%.2s\", ds->hex_pfx);\n \tfor (alt = fakeent; alt && !ds->ambiguous; alt = alt->next) {\n-\t\tstruct strbuf *buf = alt_scratch_buf(alt);\n-\t\tstruct dirent *de;\n-\t\tDIR *dir;\n-\n-\t\tstrbuf_addf(buf, \"%.2s/\", ds->hex_pfx);\n-\t\tdir = opendir(buf->buf);\n-\t\tif (!dir)\n-\t\t\tcontinue;\n+\t\tint pos;\n \n-\t\twhile (!ds->ambiguous && (de = readdir(dir)) != NULL) {\n-\t\t\tstruct object_id oid;\n+\t\tif (!alt->loose_objects_subdir_seen[subdir_nr]) {\n+\t\t\tstruct strbuf *buf = alt_scratch_buf(alt);\n+\t\t\tstrbuf_addf(buf, \"%02x/\", subdir_nr);\n+\t\t\tfor_each_file_in_obj_subdir(subdir_nr, buf,\n+\t\t\t\t\t\t append_loose_object,\n+\t\t\t\t\t\t NULL, NULL,\n+\t\t\t\t\t\t &alt->loose_objects_cache);\n+\t\t\talt->loose_objects_subdir_seen[subdir_nr] = 1;\n+\t\t}\n \n-\t\t\tif (strlen(de->d_name) != GIT_SHA1_HEXSZ - 2)\n-\t\t\t\tcontinue;\n-\t\t\tif (memcmp(de->d_name, ds->hex_pfx + 2, ds->len - 2))\n-\t\t\t\tcontinue;\n-\t\t\tmemcpy(hex + 2, de->d_name, GIT_SHA1_HEXSZ - 2);\n-\t\t\tif (!get_oid_hex(hex, &oid))\n-\t\t\t\tupdate_candidates(ds, &oid);\n+\t\tpos = oid_array_lookup(&alt->loose_objects_cache, &ds->bin_pfx);\n+\t\tif (pos < 0)\n+\t\t\tpos = -1 - pos;\n+\t\twhile (!ds->ambiguous && pos < alt->loose_objects_cache.nr) {\n+\t\t\tconst struct object_id *oid;\n+\t\t\toid = alt->loose_objects_cache.oid + pos;\n+\t\t\tif (!match_sha(ds->len, ds->bin_pfx.hash, oid->hash))\n+\t\t\t\tbreak;\n+\t\t\tupdate_candidates(ds, oid);\n+\t\t\tpos++;\n \t\t}\n-\t\tclosedir(dir);\n \t}\n }\n \n-- \n2.13.1\n\n"},{"id":"322939","messageId":"87848e2d-9766-7dad-62cf-ded0c18f6dc3@web.de","threadId":"46155","inReplyTo":"20170618135623.3b27zhzdxur6gpg3@sigill.intra.peff.net","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-06-22T18:19:40Z","receivedAt":"2017-06-22T18:20:13Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 18.06.2017 um 15:56 schrieb Jeff King:\n> On Sun, Jun 18, 2017 at 02:59:04PM +0200, René Scharfe wrote:\n> \n>>>> @@ -1586,6 +1587,9 @@ extern struct alternate_object_database {\n>>>> \tstruct strbuf scratch;\n>>>> \tsize_t base_len;\n>>>> +\tuint32_t loose_objects_subdir_bitmap[8];\n>>>\n>>> Is it worth the complexity of having an actual bitmap and not just an\n>>> array of char? I guess it's not _that_ complex to access the bits, but\n>>> there are a lot of magic numbers involved.\n>>\n>> That would be 224 bytes more per alternate_object_database, and we'd\n>> gain simpler code. Hmm. We could add some bitmap helper macros, but\n>> you're probably right that the first version should use the simplest\n>> form for representing small bitmaps that we currently have.\n> \n> I'd be OK with keeping it if we could reduce the number of magic\n> numbers. E.g,. rather than 32 elsewhere use:\n> \n> (sizeof(*loose_objects_subdir_bitmap) * CHAR_BIT)\n\nWe have a bitsizeof macro for that.\n\n> and similarly rather than 8 here use\n> \n> 256 / sizeof(*loose_objects_subdir_bitmap) / CHAR_BIT\n\nIf we're pretending not to know the number of bits in a byte then we\nneed to round up, and we have DIV_ROUND_UP for that. :)\n\n> There's also already a bitmap data structure in ewah/bitmap.c. It's a\n> little bit overkill, though, because it mallocs and will grow the bitmap\n> as needed.\n\nYes, I feel that's too big a hammer for this purpose.\n\nThere is another example of a bitmap in shallow_c (just search for\n\"32\"). It would benefit from the macros mentioned above. That\nmight make it easier to switch to the native word size (unsigned int)\ninstead of using uint32_t everywhere.\n\nBut perhaps this one is actually a candidate for using EWAH, depending\non the number of refs the code is supposed to handle.\n\n>>>> +static void read_loose_object_subdir(struct alternate_object_database *alt,\n>>>> +\t\t\t\t int subdir_nr)\n>>>\n>>> I think it's nice to pull this out into a helper function. I do wonder\n>>> if it should just be reusing for_each_loose_file_in_objdir(). You'd just\n>>> need to expose the in_obj_subdir() variant publicly.\n>>>\n>>> It does do slightly more than we need (for the callbacks it actually\n>>> builds the filename), but I doubt memcpy()ing a few bytes would be\n>>> measurable.\n>>\n>> Good point. The function also copies the common first two hex digits\n>> for each entry. But all that extra work is certainly dwarfed by the\n>> readdir calls.\n> \n> Yes. You're welcome to micro-optimize that implementation if you want. ;)\n\nMy knee-jerk reaction was that this would lead to ugliness, but on\nsecond look it might actually be doable. Will check, but I don't\nexpect much of a speedup.\n\nRené\n"},{"id":"323016","messageId":"20170622231041.2zdjypviwmndjnsb@sigill.intra.peff.net","threadId":"46155","inReplyTo":"d06fb033-294e-f364-3dde-394624e83cd6@web.de","subject":"Re: [PATCH] sha1_name: cache readdir(3) results in find_short_object_filename()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-06-22T23:10:41Z","receivedAt":"2017-06-22T23:10:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 22, 2017 at 08:19:48PM +0200, René Scharfe wrote:\n\n> Read each loose object subdirectory at most once when looking for unique\n> abbreviated hashes. This speeds up commands like \"git log --pretty=%h\"\n> considerably, which previously caused one readdir(3) call for each\n> candidate, even for subdirectories that were visited before.\n\nIs it worth adding a perf test that's heavy on abbreviations?\n\n> The new cache is kept until the program ends and never invalidated. The\n> same is already true for pack indexes. The inherent racy nature of\n> finding unique short hashes makes it still fit for this purpose -- a\n> conflicting new object may be added at any time. Tasks with higher\n> consistency requirements should not use it, though.\n> \n> The cached object names are stored in an oid_array, which is quite\n> compact. The bitmap for remembering which subdir was already read is\n> stored as a char array, with one char per directory -- that's not quite\n> as compact, but really simple and incurs only an overhead equivalent to\n> 11 hashes after all.\n\nSounds reasonable. The code itself looks good, with one minor nit below.\n\n> @@ -1593,6 +1594,16 @@ extern struct alternate_object_database {\n> \tstruct strbuf scratch;\n> \tsize_t base_len;\n> \n> +\t/*\n> +\t * Used to store the results of readdir(3) calls when searching\n> +\t * for unique abbreviated hashes. This cache is never\n> +\t * invalidated, thus it's racy and not necessarily accurate.\n> +\t * That's fine for its purpose; don't use it for tasks requiring\n> +\t * greater accuracy!\n> +\t */\n> +\tchar loose_objects_subdir_seen[256];\n> +\tstruct oid_array loose_objects_cache;\n> +\n\nThanks for adding this comment.\n\n> @@ -1811,6 +1822,12 @@ typedef int each_loose_cruft_fn(const char *basename,\n> typedef int each_loose_subdir_fn(int nr,\n> \t\t\t\t const char *path,\n> \t\t\t\t void *data);\n> +int for_each_file_in_obj_subdir(int subdir_nr,\n> +\t\t\t\tstruct strbuf *path,\n> +\t\t\t\teach_loose_object_fn obj_cb,\n> +\t\t\t\teach_loose_cruft_fn cruft_cb,\n> +\t\t\t\teach_loose_subdir_fn subdir_cb,\n> +\t\t\t\tvoid *data);\n\nNow that this is becoming public, I think we need to document what\nshould be in \"path\" here. It is the complete path, including the 2-hex\nsubdir.\n\nThat's redundant with \"subdir_nr\". Should we push that logic down into\nthe function, and basically do:\n\n if (subdir_nr < 0 || subdir_nr > 256)\n\tBUG(\"object subdir number out of range\");\n orig_len = path->len;\n strbuf_addf(path, \"/%02x\", subdir_nr);\n baselen = path->len;\n\n ...\n\n strbuf_setlen(path, orig_len);\n\nThat's one less thing for the caller to worry about, and it's easy to\nexplain the argument as \"the path to the object directory root\".\n\n> +\t\tif (!alt->loose_objects_subdir_seen[subdir_nr]) {\n> +\t\t\tstruct strbuf *buf = alt_scratch_buf(alt);\n> +\t\t\tstrbuf_addf(buf, \"%02x/\", subdir_nr);\n> +\t\t\tfor_each_file_in_obj_subdir(subdir_nr, buf,\n> +\t\t\t\t\t\t append_loose_object,\n> +\t\t\t\t\t\t NULL, NULL,\n> +\t\t\t\t\t\t &alt->loose_objects_cache);\n\nI think the trailing slash here is superfluous. If you take my\nsuggestion above, that line goes away. But then the front slash it adds\nbecomes superfluous. It should probably just do:\n\n strbuf_complete(path, '/');\n strbuf_addf(path, \"%02x\", subdir_nr);\n\n-Peff\n"},{"id":"323017","messageId":"20170622231506.prfndno7cipp2d7f@sigill.intra.peff.net","threadId":"46155","inReplyTo":"87848e2d-9766-7dad-62cf-ded0c18f6dc3@web.de","subject":"Re: [BUG] add_again() off-by-one error in custom format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-06-22T23:15:06Z","receivedAt":"2017-06-22T23:15:12Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 22, 2017 at 08:19:40PM +0200, René Scharfe wrote:\n\n> > I'd be OK with keeping it if we could reduce the number of magic\n> > numbers. E.g,. rather than 32 elsewhere use:\n> > \n> > (sizeof(*loose_objects_subdir_bitmap) * CHAR_BIT)\n> \n> We have a bitsizeof macro for that.\n> \n> > and similarly rather than 8 here use\n> > \n> > 256 / sizeof(*loose_objects_subdir_bitmap) / CHAR_BIT\n> \n> If we're pretending not to know the number of bits in a byte then we\n> need to round up, and we have DIV_ROUND_UP for that. :)\n\nThanks, I meant to mention the rounding thing but forgot. I didn't know\nabout either of those macros, though.\n\n> There is another example of a bitmap in shallow_c (just search for\n> \"32\"). It would benefit from the macros mentioned above. That\n> might make it easier to switch to the native word size (unsigned int)\n> instead of using uint32_t everywhere.\n> \n> But perhaps this one is actually a candidate for using EWAH, depending\n> on the number of refs the code is supposed to handle.\n\nI thought at first you meant real EWAH bitmaps. But those aren't random\naccess (so you have to read them into an uncompressed bitmap in memory,\nwhich is why ewah/bitmap.c exists). But if you just mean reusing those\nbitmaps, then yeah, possibly.\n\nIt looks like it's using a commit slab, though. If you know the number\nof bits you need up front, then the commit slab can do it without any\nwaste. I didn't dig enough to see if that's what it's doing or not.\n\n-Peff\n"},{"id":"323192","messageId":"2cd8a407-f9a2-687a-3c78-6b502da2ad94@web.de","threadId":"46155","inReplyTo":"20170622231041.2zdjypviwmndjnsb@sigill.intra.peff.net","subject":"Re: [PATCH] sha1_name: cache readdir(3) results in find_short_object_filename()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-06-24T12:12:07Z","receivedAt":"2017-06-24T12:12:25Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 23.06.2017 um 01:10 schrieb Jeff King:\n> On Thu, Jun 22, 2017 at 08:19:48PM +0200, René Scharfe wrote:\n> \n>> Read each loose object subdirectory at most once when looking for unique\n>> abbreviated hashes. This speeds up commands like \"git log --pretty=%h\"\n>> considerably, which previously caused one readdir(3) call for each\n>> candidate, even for subdirectories that were visited before.\n> \n> Is it worth adding a perf test that's heavy on abbreviations?\n\nSure. Here's a simple one. It currently reports for me:\n\nTest origin/master origin/next origin/pu\n---------------------------------------------------------------------------------------------\n4205.1: log with %H 0.44(0.41+0.02) 0.43(0.42+0.01) -2.3% 0.43(0.43+0.00) -2.3%\n4205.2: log with %h 1.03(0.60+0.42) 1.04(0.64+0.39) +1.0% 0.57(0.55+0.01) -44.7%\n4205.3: log with %T 0.43(0.42+0.00) 0.43(0.42+0.01) +0.0% 0.43(0.40+0.02) +0.0%\n4205.4: log with %t 1.05(0.64+0.38) 1.05(0.61+0.42) +0.0% 0.59(0.58+0.00) -43.8%\n4205.5: log with %P 0.45(0.42+0.02) 0.43(0.42+0.00) -4.4% 0.43(0.42+0.01) -4.4%\n4205.6: log with %p 1.21(0.63+0.57) 1.17(0.68+0.47) -3.3% 0.59(0.58+0.00) -51.2%\n4205.7: log with %h-%h-%h 1.05(0.64+0.39) 2.00(0.83+1.15) +90.5% 0.69(0.66+0.02) -34.3%\n\norigin/next has fe9e2aefd4 (pretty: recalculate duplicate short hashes),\nwhile origin/pu has cc817ca3ef (sha1_name: cache readdir(3) results in\nfind_short_object_filename()).\n\n-- >8 --\nSubject: [PATCH] p4205: add perf test script for pretty log formats\n\nAdd simple performance tests for expanded log format placeholders.\n\nSuggested-by: Jeff King \nSigned-off-by: Rene Scharfe \n---\n t/perf/p4205-log-pretty-formats.sh | 16 ++++++++++++++++\n 1 file changed, 16 insertions(+)\n create mode 100755 t/perf/p4205-log-pretty-formats.sh\n\ndiff --git a/t/perf/p4205-log-pretty-formats.sh b/t/perf/p4205-log-pretty-formats.sh\nnew file mode 100755\nindex 0000000000..7c26f4f337\n--- /dev/null\n+++ b/t/perf/p4205-log-pretty-formats.sh\n@@ -0,0 +1,16 @@\n+#!/bin/sh\n+\n+test_description='Tests the performance of various pretty format placeholders'\n+\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+\n+for format in %H %h %T %t %P %p %h-%h-%h\n+do\n+\ttest_perf \"log with $format\" \"\n+\t\tgit log --format=\\\"$format\\\" >/dev/null\n+\t\"\n+done\n+\n+test_done\n-- \n2.13.1\n\n"},{"id":"323194","messageId":"97a8def3-d2ed-9212-4d87-8767de6f2695@web.de","threadId":"46155","inReplyTo":"20170622231041.2zdjypviwmndjnsb@sigill.intra.peff.net","subject":"Re: [PATCH] sha1_name: cache readdir(3) results in find_short_object_filename()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-06-24T12:12:30Z","receivedAt":"2017-06-24T12:12:45Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 23.06.2017 um 01:10 schrieb Jeff King:\n> On Thu, Jun 22, 2017 at 08:19:48PM +0200, René Scharfe wrote:\n>> @@ -1811,6 +1822,12 @@ typedef int each_loose_cruft_fn(const char *basename,\n>> typedef int each_loose_subdir_fn(int nr,\n>> \t\t\t\t const char *path,\n>> \t\t\t\t void *data);\n>> +int for_each_file_in_obj_subdir(int subdir_nr,\n>> +\t\t\t\tstruct strbuf *path,\n>> +\t\t\t\teach_loose_object_fn obj_cb,\n>> +\t\t\t\teach_loose_cruft_fn cruft_cb,\n>> +\t\t\t\teach_loose_subdir_fn subdir_cb,\n>> +\t\t\t\tvoid *data);\n> \n> Now that this is becoming public, I think we need to document what\n> should be in \"path\" here. It is the complete path, including the 2-hex\n> subdir.\n> \n> That's redundant with \"subdir_nr\". Should we push that logic down into\n> the function, and basically do:\n> \n> if (subdir_nr < 0 || subdir_nr > 256)\n> \tBUG(\"object subdir number out of range\");\n\nHmm. I don't expect many more callers, so do we really need this safety\ncheck? It's cheap compared to the readdir(3) call, of course.\n\nBut wouldn't it make more sense to use an unsigned data type to avoid\nthe first half? And an unsigned char specifically to only accept valid\nvalues, leaving the overflow concern to the caller? It warrants a\nseparate patch in any case IMHO.\n\n> orig_len = path->len;\n> strbuf_addf(path, \"/%02x\", subdir_nr);\n> baselen = path->len;\n> \n> ...\n> \n> strbuf_setlen(path, orig_len);\n> \n> That's one less thing for the caller to worry about, and it's easy to\n> explain the argument as \"the path to the object directory root\".\n> \n>> +\t\tif (!alt->loose_objects_subdir_seen[subdir_nr]) {\n>> +\t\t\tstruct strbuf *buf = alt_scratch_buf(alt);\n>> +\t\t\tstrbuf_addf(buf, \"%02x/\", subdir_nr);\n>> +\t\t\tfor_each_file_in_obj_subdir(subdir_nr, buf,\n>> +\t\t\t\t\t\t append_loose_object,\n>> +\t\t\t\t\t\t NULL, NULL,\n>> +\t\t\t\t\t\t &alt->loose_objects_cache);\n> \n> I think the trailing slash here is superfluous. If you take my\n> suggestion above, that line goes away. But then the front slash it adds\n> becomes superfluous. It should probably just do:\n> \n> strbuf_complete(path, '/');\n> strbuf_addf(path, \"%02x\", subdir_nr);\n\nSo how about this then as a follow-up patch?\n\n-- >8 --\nSubject: [PATCH] sha1_file: let for_each_file_in_obj_subdir() handle subdir names\n\nThe function for_each_file_in_obj_subdir() takes a object subdirectory\nnumber and expects the name of the same subdirectory to be included in\nthe path strbuf. Avoid this redundancy by letting the function append\nthe hexadecimal subdirectory name itself. This makes it a bit easier\nand safer to use the function -- it becomes impossible to specify\ndifferent subdirectories in subdir_nr and path.\n\nSuggested-by: Jeff King \nSigned-off-by: Rene Scharfe \n---\n sha1_file.c | 22 ++++++++++++++--------\n sha1_name.c | 1 -\n 2 files changed, 14 insertions(+), 9 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 5e0ee2b68b..98ce85acf9 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -3742,15 +3742,22 @@ int for_each_file_in_obj_subdir(int subdir_nr,\n \t\t\t\teach_loose_subdir_fn subdir_cb,\n \t\t\t\tvoid *data)\n {\n-\tsize_t baselen = path->len;\n-\tDIR *dir = opendir(path->buf);\n+\tsize_t origlen, baselen;\n+\tDIR *dir;\n \tstruct dirent *de;\n \tint r = 0;\n \n+\toriglen = path->len;\n+\tstrbuf_complete(path, '/');\n+\tstrbuf_addf(path, \"%02x\", subdir_nr);\n+\tbaselen = path->len;\n+\n+\tdir = opendir(path->buf);\n \tif (!dir) {\n-\t\tif (errno == ENOENT)\n-\t\t\treturn 0;\n-\t\treturn error_errno(\"unable to open %s\", path->buf);\n+\t\tif (errno != ENOENT)\n+\t\t\tr = error_errno(\"unable to open %s\", path->buf);\n+\t\tstrbuf_setlen(path, origlen);\n+\t\treturn r;\n \t}\n \n \twhile ((de = readdir(dir))) {\n@@ -3788,6 +3795,8 @@ int for_each_file_in_obj_subdir(int subdir_nr,\n \tif (!r && subdir_cb)\n \t\tr = subdir_cb(subdir_nr, path->buf, data);\n \n+\tstrbuf_setlen(path, origlen);\n+\n \treturn r;\n }\n \n@@ -3797,15 +3806,12 @@ int for_each_loose_file_in_objdir_buf(struct strbuf *path,\n \t\t\t each_loose_subdir_fn subdir_cb,\n \t\t\t void *data)\n {\n-\tsize_t baselen = path->len;\n \tint r = 0;\n \tint i;\n \n \tfor (i = 0; i < 256; i++) {\n-\t\tstrbuf_addf(path, \"/%02x\", i);\n \t\tr = for_each_file_in_obj_subdir(i, path, obj_cb, cruft_cb,\n \t\t\t\t\t\tsubdir_cb, data);\n-\t\tstrbuf_setlen(path, baselen);\n \t\tif (r)\n \t\t\tbreak;\n \t}\ndiff --git a/sha1_name.c b/sha1_name.c\nindex ccb5144d0d..5670e2540f 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -109,7 +109,6 @@ static void find_short_object_filename(struct disambiguate_state *ds)\n \n \t\tif (!alt->loose_objects_subdir_seen[subdir_nr]) {\n \t\t\tstruct strbuf *buf = alt_scratch_buf(alt);\n-\t\t\tstrbuf_addf(buf, \"%02x/\", subdir_nr);\n \t\t\tfor_each_file_in_obj_subdir(subdir_nr, buf,\n \t\t\t\t\t\t append_loose_object,\n \t\t\t\t\t\t NULL, NULL,\n-- \n2.13.1\n"},{"id":"323195","messageId":"20170624121433.bnrn56njycnksf3g@sigill.intra.peff.net","threadId":"46155","inReplyTo":"2cd8a407-f9a2-687a-3c78-6b502da2ad94@web.de","subject":"Re: [PATCH] sha1_name: cache readdir(3) results in find_short_object_filename()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-06-24T12:14:33Z","receivedAt":"2017-06-24T12:14:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Jun 24, 2017 at 02:12:07PM +0200, René Scharfe wrote:\n\n> Am 23.06.2017 um 01:10 schrieb Jeff King:\n> > On Thu, Jun 22, 2017 at 08:19:48PM +0200, René Scharfe wrote:\n> > \n> >> Read each loose object subdirectory at most once when looking for unique\n> >> abbreviated hashes. This speeds up commands like \"git log --pretty=%h\"\n> >> considerably, which previously caused one readdir(3) call for each\n> >> candidate, even for subdirectories that were visited before.\n> > \n> > Is it worth adding a perf test that's heavy on abbreviations?\n> \n> Sure. Here's a simple one. It currently reports for me:\n> \n> Test origin/master origin/next origin/pu\n> ---------------------------------------------------------------------------------------------\n> 4205.1: log with %H 0.44(0.41+0.02) 0.43(0.42+0.01) -2.3% 0.43(0.43+0.00) -2.3%\n> 4205.2: log with %h 1.03(0.60+0.42) 1.04(0.64+0.39) +1.0% 0.57(0.55+0.01) -44.7%\n> 4205.3: log with %T 0.43(0.42+0.00) 0.43(0.42+0.01) +0.0% 0.43(0.40+0.02) +0.0%\n> 4205.4: log with %t 1.05(0.64+0.38) 1.05(0.61+0.42) +0.0% 0.59(0.58+0.00) -43.8%\n> 4205.5: log with %P 0.45(0.42+0.02) 0.43(0.42+0.00) -4.4% 0.43(0.42+0.01) -4.4%\n> 4205.6: log with %p 1.21(0.63+0.57) 1.17(0.68+0.47) -3.3% 0.59(0.58+0.00) -51.2%\n> 4205.7: log with %h-%h-%h 1.05(0.64+0.39) 2.00(0.83+1.15) +90.5% 0.69(0.66+0.02) -34.3%\n> \n> origin/next has fe9e2aefd4 (pretty: recalculate duplicate short hashes),\n> while origin/pu has cc817ca3ef (sha1_name: cache readdir(3) results in\n> find_short_object_filename()).\n\nPerfect. That last one says everything we need to know about which\napproach to take. :)\n\n-Peff\n"},{"id":"323198","messageId":"20170624122057.ndmlsa7e7dksejg3@sigill.intra.peff.net","threadId":"46155","inReplyTo":"97a8def3-d2ed-9212-4d87-8767de6f2695@web.de","subject":"Re: [PATCH] sha1_name: cache readdir(3) results in find_short_object_filename()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-06-24T12:20:57Z","receivedAt":"2017-06-24T12:21:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Jun 24, 2017 at 02:12:30PM +0200, René Scharfe wrote:\n\n> > That's redundant with \"subdir_nr\". Should we push that logic down into\n> > the function, and basically do:\n> > \n> > if (subdir_nr < 0 || subdir_nr > 256)\n> > \tBUG(\"object subdir number out of range\");\n> \n> Hmm. I don't expect many more callers, so do we really need this safety\n> check? It's cheap compared to the readdir(3) call, of course.\n\nTo me it's as much about documenting the assumptions as it is about\ncatching buggy callers. I'd be OK with a comment, too.\n\n> But wouldn't it make more sense to use an unsigned data type to avoid\n> the first half? And an unsigned char specifically to only accept valid\n> values, leaving the overflow concern to the caller? It warrants a\n> separate patch in any case IMHO.\n\nUsing unsigned makes sense. Using \"char\" because you know it only goes\nto 256 is a bit too subtle for my taste. And yes, I'd do it in a\npreparatory patch (or follow-on if you prefer).\n\n> -- >8 --\n> Subject: [PATCH] sha1_file: let for_each_file_in_obj_subdir() handle subdir names\n> \n> The function for_each_file_in_obj_subdir() takes a object subdirectory\n> number and expects the name of the same subdirectory to be included in\n> the path strbuf. Avoid this redundancy by letting the function append\n> the hexadecimal subdirectory name itself. This makes it a bit easier\n> and safer to use the function -- it becomes impossible to specify\n> different subdirectories in subdir_nr and path.\n\nYeah, this is what I had in mind.\n\n> \tfor (i = 0; i < 256; i++) {\n> -\t\tstrbuf_addf(path, \"/%02x\", i);\n> \t\tr = for_each_file_in_obj_subdir(i, path, obj_cb, cruft_cb,\n> \t\t\t\t\t\tsubdir_cb, data);\n> -\t\tstrbuf_setlen(path, baselen);\n\nOne side effect of the original code is that this trailing setlen()\nwould catch any early-exits from for_each_file_in_obj_subdir() which\nforgot to reset the strbuf. If any exist, that's a bug that should be in\nfixed in that function, though. I double-checked, and there aren't any\n(your patch already handles the extra setlen required when opendir\nfails).\n\n-Peff\n"},{"id":"323206","messageId":"03dc365d-41f7-dbe7-3c22-bdeee77a817c@web.de","threadId":"46155","inReplyTo":"20170624122057.ndmlsa7e7dksejg3@sigill.intra.peff.net","subject":"Re: [PATCH] sha1_name: cache readdir(3) results in find_short_object_filename()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-06-24T14:09:39Z","receivedAt":"2017-06-24T14:10:04Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 24.06.2017 um 14:20 schrieb Jeff King:\n> On Sat, Jun 24, 2017 at 02:12:30PM +0200, René Scharfe wrote:\n> \n>>> That's redundant with \"subdir_nr\". Should we push that logic down into\n>>> the function, and basically do:\n>>>\n>>> if (subdir_nr < 0 || subdir_nr > 256)\n>>> \tBUG(\"object subdir number out of range\");\n>>\n>> Hmm. I don't expect many more callers, so do we really need this safety\n>> check? It's cheap compared to the readdir(3) call, of course.\n> \n> To me it's as much about documenting the assumptions as it is about\n> catching buggy callers. I'd be OK with a comment, too.\n\nI didn't catch the off-by-one error above in the first reading. Did you\nadd it intentionally? ;-) In any case, I'm convinced now that we need\nsuch a check, but with hexadecimal notation to avoid such mistakes.\n\n>> But wouldn't it make more sense to use an unsigned data type to avoid\n>> the first half? And an unsigned char specifically to only accept valid\n>> values, leaving the overflow concern to the caller? It warrants a\n>> separate patch in any case IMHO.\n> \n> Using unsigned makes sense. Using \"char\" because you know it only goes\n> to 256 is a bit too subtle for my taste. And yes, I'd do it in a\n> preparatory patch (or follow-on if you prefer).\n\nIt's subtle on the caller's side, as big numbers would just wrap if the\nprogrammer ignored the limits of the type. On the callee's side it's\nfundamental, though.\n\nAnyway, here's a patch on top of the others.\n\n-- >8 --\nSubject: [PATCH] sha1_file: guard against invalid loose subdirectory numbers\n\nLoose object subdirectories have hexadecimal names based on the first\nbyte of the hash of contained objects, thus their numerical\nrepresentation can range from 0 (0x00) to 255 (0xff). Change the type\nof the corresponding variable in for_each_file_in_obj_subdir() and\nassociated callback functions to unsigned int and add a range check.\n\nSuggested-by: Jeff King \nSigned-off-by: Rene Scharfe \n---\n builtin/fsck.c | 2 +-\n builtin/prune-packed.c | 2 +-\n builtin/prune.c | 2 +-\n cache.h | 4 ++--\n sha1_file.c | 5 ++++-\n 5 files changed, 9 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/fsck.c b/builtin/fsck.c\nindex 3a2c27f241..5d113f8bc0 100644\n--- a/builtin/fsck.c\n+++ b/builtin/fsck.c\n@@ -536,7 +536,7 @@ static int fsck_cruft(const char *basename, const char *path, void *data)\n \treturn 0;\n }\n \n-static int fsck_subdir(int nr, const char *path, void *progress)\n+static int fsck_subdir(unsigned int nr, const char *path, void *progress)\n {\n \tdisplay_progress(progress, nr + 1);\n \treturn 0;\ndiff --git a/builtin/prune-packed.c b/builtin/prune-packed.c\nindex c026299e78..ac978ad401 100644\n--- a/builtin/prune-packed.c\n+++ b/builtin/prune-packed.c\n@@ -10,7 +10,7 @@ static const char * const prune_packed_usage[] = {\n \n static struct progress *progress;\n \n-static int prune_subdir(int nr, const char *path, void *data)\n+static int prune_subdir(unsigned int nr, const char *path, void *data)\n {\n \tint *opts = data;\n \tdisplay_progress(progress, nr + 1);\ndiff --git a/builtin/prune.c b/builtin/prune.c\nindex f0e2bff04c..c378690545 100644\n--- a/builtin/prune.c\n+++ b/builtin/prune.c\n@@ -68,7 +68,7 @@ static int prune_cruft(const char *basename, const char *path, void *data)\n \treturn 0;\n }\n \n-static int prune_subdir(int nr, const char *path, void *data)\n+static int prune_subdir(unsigned int nr, const char *path, void *data)\n {\n \tif (!show_only)\n \t\trmdir(path);\ndiff --git a/cache.h b/cache.h\nindex 00a017dfcb..04dd2961ad 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1819,10 +1819,10 @@ typedef int each_loose_object_fn(const struct object_id *oid,\n typedef int each_loose_cruft_fn(const char *basename,\n \t\t\t\tconst char *path,\n \t\t\t\tvoid *data);\n-typedef int each_loose_subdir_fn(int nr,\n+typedef int each_loose_subdir_fn(unsigned int nr,\n \t\t\t\t const char *path,\n \t\t\t\t void *data);\n-int for_each_file_in_obj_subdir(int subdir_nr,\n+int for_each_file_in_obj_subdir(unsigned int subdir_nr,\n \t\t\t\tstruct strbuf *path,\n \t\t\t\teach_loose_object_fn obj_cb,\n \t\t\t\teach_loose_cruft_fn cruft_cb,\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 98ce85acf9..90b9414170 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -3735,7 +3735,7 @@ void assert_sha1_type(const unsigned char *sha1, enum object_type expect)\n \t\t typename(expect));\n }\n \n-int for_each_file_in_obj_subdir(int subdir_nr,\n+int for_each_file_in_obj_subdir(unsigned int subdir_nr,\n \t\t\t\tstruct strbuf *path,\n \t\t\t\teach_loose_object_fn obj_cb,\n \t\t\t\teach_loose_cruft_fn cruft_cb,\n@@ -3747,6 +3747,9 @@ int for_each_file_in_obj_subdir(int subdir_nr,\n \tstruct dirent *de;\n \tint r = 0;\n \n+\tif (subdir_nr > 0xff)\n+\t\tBUG(\"invalid loose object subdirectory: %x\", subdir_nr);\n+\n \toriglen = path->len;\n \tstrbuf_complete(path, '/');\n \tstrbuf_addf(path, \"%02x\", subdir_nr);\n-- \n2.13.1\n"},{"id":"323207","messageId":"20170624141217.oj3nnzycn6bsilzo@sigill.intra.peff.net","threadId":"46155","inReplyTo":"03dc365d-41f7-dbe7-3c22-bdeee77a817c@web.de","subject":"Re: [PATCH] sha1_name: cache readdir(3) results in find_short_object_filename()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-06-24T14:12:17Z","receivedAt":"2017-06-24T14:12:24Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Jun 24, 2017 at 04:09:39PM +0200, René Scharfe wrote:\n\n> Am 24.06.2017 um 14:20 schrieb Jeff King:\n> > On Sat, Jun 24, 2017 at 02:12:30PM +0200, René Scharfe wrote:\n> > \n> >>> That's redundant with \"subdir_nr\". Should we push that logic down into\n> >>> the function, and basically do:\n> >>>\n> >>> if (subdir_nr < 0 || subdir_nr > 256)\n> >>> \tBUG(\"object subdir number out of range\");\n> >>\n> >> Hmm. I don't expect many more callers, so do we really need this safety\n> >> check? It's cheap compared to the readdir(3) call, of course.\n> > \n> > To me it's as much about documenting the assumptions as it is about\n> > catching buggy callers. I'd be OK with a comment, too.\n> \n> I didn't catch the off-by-one error above in the first reading. Did you\n> add it intentionally? ;-) In any case, I'm convinced now that we need\n> such a check, but with hexadecimal notation to avoid such mistakes.\n\nErr...yeah, it was totally intentional. ;)\n\nI agree writing it in hex is better.\n\n> -- >8 --\n> Subject: [PATCH] sha1_file: guard against invalid loose subdirectory numbers\n> \n> Loose object subdirectories have hexadecimal names based on the first\n> byte of the hash of contained objects, thus their numerical\n> representation can range from 0 (0x00) to 255 (0xff). Change the type\n> of the corresponding variable in for_each_file_in_obj_subdir() and\n> associated callback functions to unsigned int and add a range check.\n> \n> Suggested-by: Jeff King \n> Signed-off-by: Rene Scharfe \n\nThis looks great. Thanks.\n\n-Peff\n"}]}