{"thread":{"id":"46643","subject":"[PATCH 0/3] read-cache: use stack ondisk struct when writing index","startedAt":"2017-08-21T21:17:00Z","lastAt":"2017-08-21T23:42:30Z","messageCount":6,"participants":["Kevin Willford","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"326905","messageId":"20170821212432.47364-1-kewillf@microsoft.com","threadId":"46643","inReplyTo":null,"subject":"[PATCH 0/3] read-cache: use stack ondisk struct when writing index","fromName":"Kevin Willford","fromEmail":"kewillf@microsoft.com","sentAt":"2017-08-21T21:24:29Z","receivedAt":"2017-08-21T21:17:00Z","isPatch":true,"sender":{"key":"kewillf@microsoft.com","avatar":null},"body":"When writing out the index, the ondisk struct was being allocated and freed\nwithin the loop of cache entries.  A better way would be to use a ondisk\nstruct on the stack and reuse it avoiding the alloc and free calls.\n\nA test has been added to measure the performance of writing the index\n(p0007-write-cache).  Running this test on smaller repos showed no\ndegradation in performance.  On larger repos there was ~3-7% improvement.\n\n0007.2: write_locked_index 10 times (1000001 files)   5.98(0.00+0.04)   5.75(0.01+0.04) -3.8%\n0007.2: write_locked_index 10 times (1000001 files)   6.20(0.00+0.06)   5.86(0.01+0.03) -5.5%\n0007.2: write_locked_index 3 times (4394531 files)   10.29(0.04+0.03)   9.75(0.04+0.01) -5.2%\n0007.2: write_locked_index 3 times (4394531 files)   10.52(0.00+0.04)   9.79(0.03+0.03) -6.9%\n\nKevin Willford (3):\n  perf: add test for writing the index\n  read-cache: fix memory leak in do_write_index\n  read-cache: avoid allocating every ondisk entry when writing\n\n Makefile                    |  1 +\n read-cache.c                | 62 +++++++++++++++++++++++++--------------------\n t/helper/test-write-cache.c | 23 +++++++++++++++++\n t/perf/p0007-write-cache.sh | 29 +++++++++++++++++++++\n 4 files changed, 87 insertions(+), 28 deletions(-)\n create mode 100644 t/helper/test-write-cache.c\n create mode 100755 t/perf/p0007-write-cache.sh\n\n-- \n2.14.1.205.g2812f3410d\n\n"},{"id":"326906","messageId":"20170821212432.47364-2-kewillf@microsoft.com","threadId":"46643","inReplyTo":"20170821212432.47364-1-kewillf@microsoft.com","subject":"[PATCH 1/3] perf: add test for writing the index","fromName":"Kevin Willford","fromEmail":"kewillf@microsoft.com","sentAt":"2017-08-21T21:24:30Z","receivedAt":"2017-08-21T21:17:03Z","isPatch":true,"sender":{"key":"kewillf@microsoft.com","avatar":null},"body":"A performance test for writing the index to be able to\ndetermine if changes to allocating ondisk structure help.\n\nSigned-off-by: Kevin Willford <kewillf@microsoft.com>\n---\n Makefile                    |  1 +\n t/helper/test-write-cache.c | 23 +++++++++++++++++++++++\n t/perf/p0007-write-cache.sh | 29 +++++++++++++++++++++++++++++\n 3 files changed, 53 insertions(+)\n create mode 100644 t/helper/test-write-cache.c\n create mode 100755 t/perf/p0007-write-cache.sh\n\ndiff --git a/Makefile b/Makefile\nindex 86ec29202b..c6b061086f 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -655,6 +655,7 @@ TEST_PROGRAMS_NEED_X += test-parse-options\n TEST_PROGRAMS_NEED_X += test-path-utils\n TEST_PROGRAMS_NEED_X += test-prio-queue\n TEST_PROGRAMS_NEED_X += test-read-cache\n+TEST_PROGRAMS_NEED_X += test-write-cache\n TEST_PROGRAMS_NEED_X += test-ref-store\n TEST_PROGRAMS_NEED_X += test-regex\n TEST_PROGRAMS_NEED_X += test-revision-walking\ndiff --git a/t/helper/test-write-cache.c b/t/helper/test-write-cache.c\nnew file mode 100644\nindex 0000000000..b7ee039669\n--- /dev/null\n+++ b/t/helper/test-write-cache.c\n@@ -0,0 +1,23 @@\n+#include \"cache.h\"\n+#include \"lockfile.h\"\n+\n+static struct lock_file index_lock;\n+\n+int cmd_main(int argc, const char **argv)\n+{\n+\tint i, cnt = 1, lockfd;\n+\tif (argc == 2)\n+\t\tcnt = strtol(argv[1], NULL, 0);\n+\tsetup_git_directory();\n+\tread_cache();\n+\tfor (i = 0; i < cnt; i++) {\n+\t\tlockfd = hold_locked_index(&index_lock, LOCK_DIE_ON_ERROR);\n+\t\tif (0 <= lockfd) {\n+\t\t\twrite_locked_index(&the_index, &index_lock, COMMIT_LOCK);\n+\t\t} else {\n+\t\t\trollback_lock_file(&index_lock);\n+\t\t}\n+\t}\n+\n+\treturn 0;\n+}\ndiff --git a/t/perf/p0007-write-cache.sh b/t/perf/p0007-write-cache.sh\nnew file mode 100755\nindex 0000000000..261fe92fd9\n--- /dev/null\n+++ b/t/perf/p0007-write-cache.sh\n@@ -0,0 +1,29 @@\n+#!/bin/sh\n+\n+test_description=\"Tests performance of writing the index\"\n+\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+\n+test_expect_success \"setup repo\" '\n+\tif git rev-parse --verify refs/heads/p0006-ballast^{commit}\n+\tthen\n+\t\techo Assuming synthetic repo from many-files.sh\n+\t\tgit config --local core.sparsecheckout 1\n+\t\tcat >.git/info/sparse-checkout <<-EOF\n+\t\t/*\n+\t\t!ballast/*\n+\t\tEOF\n+\telse\n+\t\techo Assuming non-synthetic repo...\n+\tfi &&\n+\tnr_files=$(git ls-files | wc -l)\n+'\n+\n+count=3\n+test_perf \"write_locked_index $count times ($nr_files files)\" \"\n+\ttest-write-cache $count\n+\"\n+\n+test_done\n-- \n2.14.1.205.g2812f3410d\n\n"},{"id":"326907","messageId":"20170821212432.47364-3-kewillf@microsoft.com","threadId":"46643","inReplyTo":"20170821212432.47364-1-kewillf@microsoft.com","subject":"[PATCH 2/3] read-cache: fix memory leak in do_write_index","fromName":"Kevin Willford","fromEmail":"kewillf@microsoft.com","sentAt":"2017-08-21T21:24:31Z","receivedAt":"2017-08-21T21:17:07Z","isPatch":true,"sender":{"key":"kewillf@microsoft.com","avatar":null},"body":"The previous_name_buf was never getting released when there\nwas an error in ce_write_entry or allow was false and execution\nwas returned to the caller.\n\nSigned-off-by: Kevin Willford <kewillf@microsoft.com>\n---\n read-cache.c | 12 +++++++++---\n 1 file changed, 9 insertions(+), 3 deletions(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex acfb028f48..47220cc30d 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -2192,7 +2192,7 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \tint newfd = tempfile->fd;\n \tgit_SHA_CTX c;\n \tstruct cache_header hdr;\n-\tint i, err, removed, extended, hdr_version;\n+\tint i, err = 0, removed, extended, hdr_version;\n \tstruct cache_entry **cache = istate->cache;\n \tint entries = istate->cache_nr;\n \tstruct stat st;\n@@ -2247,15 +2247,21 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \t\t\tif (allow)\n \t\t\t\twarning(msg, ce->name);\n \t\t\telse\n-\t\t\t\treturn error(msg, ce->name);\n+\t\t\t\terr = error(msg, ce->name);\n \n \t\t\tdrop_cache_tree = 1;\n \t\t}\n \t\tif (ce_write_entry(&c, newfd, ce, previous_name) < 0)\n-\t\t\treturn -1;\n+\t\t\terr = -1;\n+\n+\t\tif (err)\n+\t\t\tbreak;\n \t}\n \tstrbuf_release(&previous_name_buf);\n \n+\tif (err)\n+\t\treturn err;\n+\n \t/* Write extension data here */\n \tif (!strip_extensions && istate->split_index) {\n \t\tstruct strbuf sb = STRBUF_INIT;\n-- \n2.14.1.205.g2812f3410d\n\n"},{"id":"326908","messageId":"20170821212432.47364-4-kewillf@microsoft.com","threadId":"46643","inReplyTo":"20170821212432.47364-1-kewillf@microsoft.com","subject":"[PATCH 3/3] read-cache: avoid allocating every ondisk entry when writing","fromName":"Kevin Willford","fromEmail":"kewillf@microsoft.com","sentAt":"2017-08-21T21:24:32Z","receivedAt":"2017-08-21T21:17:09Z","isPatch":true,"sender":{"key":"kewillf@microsoft.com","avatar":null},"body":"When writing the index for each entry an ondisk struct will be\nallocated and freed in ce_write_entry.  We can do better by\nusing a ondisk struct on the stack for each entry.\n\nThis is accomplished by using a stack ondisk_cache_entry_extended\noutside looping through the entries in do_write_index.  Only the\nfixed fields of this struct are used when writing and depending on\nwhether it is extended or not the flags2 field will be written.\nThe name field is not used and instead the cache_entry name field\nis used directly when writing out the name.  Because ce_write is\nusing a buffer and memcpy to fill the buffer before flushing to disk,\nwe don't have to worry about doing multiple ce_write calls.\n\nRunning the p0007-write-cache.sh tests would save anywhere\nbetween 3-7% when the index had over a million entries with no\nperformance degradation on small repos.\n\nSigned-off-by: Kevin Willford <kewillf@microsoft.com>\n---\n read-cache.c | 50 +++++++++++++++++++++++++-------------------------\n 1 file changed, 25 insertions(+), 25 deletions(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex 47220cc30d..694bed8d82 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1499,6 +1499,7 @@ struct ondisk_cache_entry_extended {\n };\n \n /* These are only used for v3 or lower */\n+#define align_padding_size(size, len) ((size + (len) + 8) & ~7) - (size + len)\n #define align_flex_name(STRUCT,len) ((offsetof(struct STRUCT,name) + (len) + 8) & ~7)\n #define ondisk_cache_entry_size(len) align_flex_name(ondisk_cache_entry,len)\n #define ondisk_cache_entry_extended_size(len) align_flex_name(ondisk_cache_entry_extended,len)\n@@ -2032,7 +2033,7 @@ static void ce_smudge_racily_clean_entry(struct cache_entry *ce)\n }\n \n /* Copy miscellaneous fields but not the name */\n-static char *copy_cache_entry_to_ondisk(struct ondisk_cache_entry *ondisk,\n+static void copy_cache_entry_to_ondisk(struct ondisk_cache_entry *ondisk,\n \t\t\t\t       struct cache_entry *ce)\n {\n \tshort flags;\n@@ -2056,32 +2057,35 @@ static char *copy_cache_entry_to_ondisk(struct ondisk_cache_entry *ondisk,\n \t\tstruct ondisk_cache_entry_extended *ondisk2;\n \t\tondisk2 = (struct ondisk_cache_entry_extended *)ondisk;\n \t\tondisk2->flags2 = htons((ce->ce_flags & CE_EXTENDED_FLAGS) >> 16);\n-\t\treturn ondisk2->name;\n-\t}\n-\telse {\n-\t\treturn ondisk->name;\n \t}\n }\n \n static int ce_write_entry(git_SHA_CTX *c, int fd, struct cache_entry *ce,\n-\t\t\t  struct strbuf *previous_name)\n+\t\t\t  struct strbuf *previous_name, struct ondisk_cache_entry *ondisk)\n {\n \tint size;\n-\tstruct ondisk_cache_entry *ondisk;\n \tint saved_namelen = saved_namelen; /* compiler workaround */\n-\tchar *name;\n \tint result;\n+\tstatic unsigned char padding[8] = { 0x00 };\n \n \tif (ce->ce_flags & CE_STRIP_NAME) {\n \t\tsaved_namelen = ce_namelen(ce);\n \t\tce->ce_namelen = 0;\n \t}\n \n+\tif (ce->ce_flags & CE_EXTENDED)\n+\t\tsize = offsetof(struct ondisk_cache_entry_extended, name);\n+\telse\n+\t\tsize = offsetof(struct ondisk_cache_entry, name);\n+\n \tif (!previous_name) {\n-\t\tsize = ondisk_ce_size(ce);\n-\t\tondisk = xcalloc(1, size);\n-\t\tname = copy_cache_entry_to_ondisk(ondisk, ce);\n-\t\tmemcpy(name, ce->name, ce_namelen(ce));\n+\t\tint len = ce_namelen(ce);\n+\t\tcopy_cache_entry_to_ondisk(ondisk, ce);\n+\t\tresult = ce_write(c, fd, ondisk, size);\n+\t\tif (!result)\n+\t\t\tresult = ce_write(c, fd, ce->name, len);\n+\t\tif (!result)\n+\t\t\tresult = ce_write(c, fd, padding, align_padding_size(size, len));\n \t} else {\n \t\tint common, to_remove, prefix_size;\n \t\tunsigned char to_remove_vi[16];\n@@ -2094,16 +2098,12 @@ static int ce_write_entry(git_SHA_CTX *c, int fd, struct cache_entry *ce,\n \t\tto_remove = previous_name->len - common;\n \t\tprefix_size = encode_varint(to_remove, to_remove_vi);\n \n-\t\tif (ce->ce_flags & CE_EXTENDED)\n-\t\t\tsize = offsetof(struct ondisk_cache_entry_extended, name);\n-\t\telse\n-\t\t\tsize = offsetof(struct ondisk_cache_entry, name);\n-\t\tsize += prefix_size + (ce_namelen(ce) - common + 1);\n-\n-\t\tondisk = xcalloc(1, size);\n-\t\tname = copy_cache_entry_to_ondisk(ondisk, ce);\n-\t\tmemcpy(name, to_remove_vi, prefix_size);\n-\t\tmemcpy(name + prefix_size, ce->name + common, ce_namelen(ce) - common);\n+\t\tcopy_cache_entry_to_ondisk(ondisk, ce);\n+\t\tresult = ce_write(c, fd, ondisk, size);\n+\t\tif (!result)\n+\t\t\tresult = ce_write(c, fd, to_remove_vi, prefix_size);\n+\t\tif (!result)\n+\t\t\tresult = ce_write(c, fd, ce->name + common, ce_namelen(ce) - common + 1);\n \n \t\tstrbuf_splice(previous_name, common, to_remove,\n \t\t\t      ce->name + common, ce_namelen(ce) - common);\n@@ -2113,8 +2113,6 @@ static int ce_write_entry(git_SHA_CTX *c, int fd, struct cache_entry *ce,\n \t\tce->ce_flags &= ~CE_STRIP_NAME;\n \t}\n \n-\tresult = ce_write(c, fd, ondisk, size);\n-\tfree(ondisk);\n \treturn result;\n }\n \n@@ -2196,6 +2194,7 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \tstruct cache_entry **cache = istate->cache;\n \tint entries = istate->cache_nr;\n \tstruct stat st;\n+\tstruct ondisk_cache_entry_extended ondisk;\n \tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n \tint drop_cache_tree = 0;\n \n@@ -2232,6 +2231,7 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \t\treturn -1;\n \n \tprevious_name = (hdr_version == 4) ? &previous_name_buf : NULL;\n+\n \tfor (i = 0; i < entries; i++) {\n \t\tstruct cache_entry *ce = cache[i];\n \t\tif (ce->ce_flags & CE_REMOVE)\n@@ -2251,7 +2251,7 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \n \t\t\tdrop_cache_tree = 1;\n \t\t}\n-\t\tif (ce_write_entry(&c, newfd, ce, previous_name) < 0)\n+\t\tif (ce_write_entry(&c, newfd, ce, previous_name, (struct ondisk_cache_entry *)&ondisk) < 0)\n \t\t\terr = -1;\n \n \t\tif (err)\n-- \n2.14.1.205.g2812f3410d\n\n"},{"id":"326914","messageId":"xmqq1so45xsy.fsf@gitster.mtv.corp.google.com","threadId":"46643","inReplyTo":"20170821212432.47364-3-kewillf@microsoft.com","subject":"Re: [PATCH 2/3] read-cache: fix memory leak in do_write_index","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-21T23:02:53Z","receivedAt":"2017-08-21T23:03:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Willford <kewillf@microsoft.com> writes:\n\n> The previous_name_buf was never getting released when there\n> was an error in ce_write_entry or allow was false and execution\n> was returned to the caller.\n>\n> Signed-off-by: Kevin Willford <kewillf@microsoft.com>\n> ---\n\nThanks for spotting an old error that dates back to at least 2013\nthis month.  The patch looks sensible.\n\n\n\n>  read-cache.c | 12 +++++++++---\n>  1 file changed, 9 insertions(+), 3 deletions(-)\n>\n> diff --git a/read-cache.c b/read-cache.c\n> index acfb028f48..47220cc30d 100644\n> --- a/read-cache.c\n> +++ b/read-cache.c\n> @@ -2192,7 +2192,7 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n>  \tint newfd = tempfile->fd;\n>  \tgit_SHA_CTX c;\n>  \tstruct cache_header hdr;\n> -\tint i, err, removed, extended, hdr_version;\n> +\tint i, err = 0, removed, extended, hdr_version;\n>  \tstruct cache_entry **cache = istate->cache;\n>  \tint entries = istate->cache_nr;\n>  \tstruct stat st;\n> @@ -2247,15 +2247,21 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n>  \t\t\tif (allow)\n>  \t\t\t\twarning(msg, ce->name);\n>  \t\t\telse\n> -\t\t\t\treturn error(msg, ce->name);\n> +\t\t\t\terr = error(msg, ce->name);\n>  \n>  \t\t\tdrop_cache_tree = 1;\n>  \t\t}\n>  \t\tif (ce_write_entry(&c, newfd, ce, previous_name) < 0)\n> -\t\t\treturn -1;\n> +\t\t\terr = -1;\n> +\n> +\t\tif (err)\n> +\t\t\tbreak;\n>  \t}\n>  \tstrbuf_release(&previous_name_buf);\n>  \n> +\tif (err)\n> +\t\treturn err;\n> +\n>  \t/* Write extension data here */\n>  \tif (!strip_extensions && istate->split_index) {\n>  \t\tstruct strbuf sb = STRBUF_INIT;\n"},{"id":"326915","messageId":"xmqqwp5w4hev.fsf@gitster.mtv.corp.google.com","threadId":"46643","inReplyTo":"20170821212432.47364-4-kewillf@microsoft.com","subject":"Re: [PATCH 3/3] read-cache: avoid allocating every ondisk entry when writing","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-21T23:42:16Z","receivedAt":"2017-08-21T23:42:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Willford <kewillf@microsoft.com> writes:\n\n> When writing the index for each entry an ondisk struct will be\n> allocated and freed in ce_write_entry.  We can do better by\n> using a ondisk struct on the stack for each entry.\n>\n> This is accomplished by using a stack ondisk_cache_entry_extended\n> outside looping through the entries in do_write_index.  Only the\n> fixed fields of this struct are used when writing and depending on\n> whether it is extended or not the flags2 field will be written.\n> The name field is not used and instead the cache_entry name field\n> is used directly when writing out the name.  Because ce_write is\n> using a buffer and memcpy to fill the buffer before flushing to disk,\n> we don't have to worry about doing multiple ce_write calls.\n\nThe code already heavily assumes that the only difference between\nondisk_cache_entry and its _extended variant are identical in their\nearlier parts, so having a single instance of the larger one on the\nstack and passing it around makes sense as an optimization.\n\nMultiple chomped calls to ce_write() does make me nervous, not due\nto potential I/O cost (which is none) but to potential programming\nmistakes for people who touch the code.  The version immediately\nafter this patch looks correct in that once \"result\" is set to non\nzero to indicate an error nothing is written out, but keeping that\nproperty over time, when a newer index format is eventually invented,\nmay become an additional burden.\n\nBut overall, I think this is a good change.  Will queue all three.\n\nThanks.\n\n"}]}