{"thread":{"id":"42769","subject":"[PATCH/RFC] fast-import: Keep a fake pack window on the recently written data","startedAt":"2016-07-03T23:58:03Z","lastAt":"2016-07-22T22:19:42Z","messageCount":3,"participants":["Mike Hommey"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"290780","messageId":"20160703234439.8889-1-mh@glandium.org","threadId":"42769","inReplyTo":null,"subject":"[PATCH/RFC] fast-import: Keep a fake pack window on the recently written data","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2016-07-03T23:44:39Z","receivedAt":"2016-07-03T23:58:03Z","isPatch":true,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"The are many ways in which fast-import ends up calling gfi_unpack_entry,\nand fery few work-arounds. I've patched fast-import for it to be smarter\nin corner cases, allowing some additional work-arounds, but it's just\ntoo easy to fall on gfi_unpack_entry again, so I abandonned that path.\n\nThe problem with gfi_unpack_entry is that if something has been written\nto the pack after last time it was used, it closes all pack windows. On\nOSX, this triggers munmap, which shows up in performance profiles.\n\nTo give an idea how bad this is, here is how long it takes to clone\nhttps://hg.mozilla.org/mozilla-unified/ with the master branch of\ngit-cinnabar (which uses fast-import) on a mac mini: more than 5 hours.\nI can't actually give the exact number, because it was killed, after\nspending 2 hours importing 1.77M files and 3 hours importing 120k\nmanifests.\n\nThe same clone, with a variant of this patch, *finished* in 2 hours and\n10 minutes, spending 24 minutes importing the same 1.77M files and only\n13 minutes to cover the same 120k manifests. It took an hour and 20\nminutes to cover the remaining 210k manifests. You can imagine how long\nit would have taken without the patch if it hadn't been killed...\n\nNow, this is proof of concept level. There are many things that are not\nright with this patch, starting from the fact it doesn't handle\ncheckpoints, and isn't safe for every kind of integer overflows. Or\nmalloc'ating exactly packed_git_window_size bytes (which on 64-bits\nsystems, is 1GB), etc.\n\nBut it feels to me this kind of fake pack window is a cheap way to\ncounter the slowness of munmap on OSX, although the fact that it's a\nhack around the pack code in sha1_file.c is not very nice. Maybe a\nbetter start to fix the issue would be to add better interfaces to\nthe pack code to handle pack writers that can read at the same time.\n\nThoughts?\n\nPast related discussions:\n  $gmane/291717\n  $gmane/273465\n---\n fast-import.c | 90 +++++++++++++++++++++++++++++++++++++++++------------------\n 1 file changed, 63 insertions(+), 27 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex c504ef7..4e26883 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -316,6 +316,7 @@ static struct atom_str **atom_table;\n static struct pack_idx_option pack_idx_opts;\n static unsigned int pack_id;\n static struct sha1file *pack_file;\n+static struct pack_window *pack_win;\n static struct packed_git *pack_data;\n static struct packed_git **all_packs;\n static off_t pack_size;\n@@ -862,6 +863,39 @@ static struct tree_content *dup_tree_content(struct tree_content *s)\n \treturn d;\n }\n \n+static void _sha1write(struct sha1file *f, const void *buf, unsigned int count)\n+{\n+\tsha1write(f, buf, count);\n+\t/* Always last used */\n+\tpack_win->last_used = -1;\n+\tpack_win->inuse_cnt = -1;\n+\n+\tpack_data->pack_size += count;\n+\n+\tif (packed_git_window_size - pack_win->len >= count) {\n+\t\tmemcpy(pack_win->base + pack_win->len - 20, buf, count);\n+\t\tpack_win->len += count;\n+\t} else {\n+\t\tstruct pack_window *cursor = NULL;\n+\t\t/* We're sliding the window, so we don't need to memcpy\n+\t\t * everything. */\n+\t\tpack_win->offset += ((pack_win->len - 20 + count)\n+\t\t\t / packed_git_window_size) * packed_git_window_size;\n+\t\tpack_win->len = count % packed_git_window_size -\n+\t\t\t(packed_git_window_size - pack_win->len);\n+\t\tmemcpy(pack_win->base, buf + count - pack_win->len + 20,\n+\t\t       pack_win->len - 20);\n+\n+\t\t/* Ensure a pack window on the data before that, otherwise,\n+\t\t * use_pack() may try to create a window that overlaps with\n+\t\t * this one, and that won't work because it won't be complete. */\n+\t\tsha1flush(f);\n+\t\tuse_pack(pack_data, &cursor,\n+\t\t\t pack_win->offset - packed_git_window_size, NULL);\n+\t\tunuse_pack(&cursor);\n+\t}\n+}\n+\n static void start_packfile(void)\n {\n \tstatic char tmp_file[PATH_MAX];\n@@ -873,15 +907,22 @@ static void start_packfile(void)\n \t\t\t      \"pack/tmp_pack_XXXXXX\");\n \tFLEX_ALLOC_STR(p, pack_name, tmp_file);\n \tp->pack_fd = pack_fd;\n+\tp->pack_size = 20;\n \tp->do_not_close = 1;\n \tpack_file = sha1fd(pack_fd, p->pack_name);\n \n+\tp->windows = pack_win = xcalloc(1, sizeof(*p->windows));\n+\tpack_win->offset = 0;\n+\tpack_win->len = 20;\n+\tpack_win->base = xmalloc(packed_git_window_size);\n+\tpack_win->next = NULL;\n+\n \thdr.hdr_signature = htonl(PACK_SIGNATURE);\n \thdr.hdr_version = htonl(2);\n \thdr.hdr_entries = 0;\n-\tsha1write(pack_file, &hdr, sizeof(hdr));\n-\n \tpack_data = p;\n+\t_sha1write(pack_file, &hdr, sizeof(hdr));\n+\n \tpack_size = sizeof(hdr);\n \tobject_count = 0;\n \n@@ -954,10 +995,25 @@ static void unkeep_all_packs(void)\n static void end_packfile(void)\n {\n \tstatic int running;\n+\tstruct pack_window *win, *prev;\n \n \tif (running || !pack_data)\n \t\treturn;\n \n+\t/* Remove the fake pack window first */\n+\tfor (prev = NULL, win = pack_data->windows; win;\n+\t     prev = win, win = win->next) {\n+\t\tif (win != pack_win)\n+\t\t\tcontinue;\n+\t\tif (prev)\n+\t\t\tprev->next = win->next;\n+\t\telse\n+\t\t\tpack_data->windows = win->next;\n+\t\tbreak;\n+\t}\n+\tfree(pack_win->base);\n+\tfree(pack_win);\n+\n \trunning = 1;\n \tclear_delta_base_cache();\n \tif (object_count) {\n@@ -1122,22 +1178,22 @@ static int store_object(\n \t\te->depth = last->depth + 1;\n \n \t\thdrlen = encode_in_pack_object_header(OBJ_OFS_DELTA, deltalen, hdr);\n-\t\tsha1write(pack_file, hdr, hdrlen);\n+\t\t_sha1write(pack_file, hdr, hdrlen);\n \t\tpack_size += hdrlen;\n \n \t\thdr[pos] = ofs & 127;\n \t\twhile (ofs >>= 7)\n \t\t\thdr[--pos] = 128 | (--ofs & 127);\n-\t\tsha1write(pack_file, hdr + pos, sizeof(hdr) - pos);\n+\t\t_sha1write(pack_file, hdr + pos, sizeof(hdr) - pos);\n \t\tpack_size += sizeof(hdr) - pos;\n \t} else {\n \t\te->depth = 0;\n \t\thdrlen = encode_in_pack_object_header(type, dat->len, hdr);\n-\t\tsha1write(pack_file, hdr, hdrlen);\n+\t\t_sha1write(pack_file, hdr, hdrlen);\n \t\tpack_size += hdrlen;\n \t}\n \n-\tsha1write(pack_file, out, s.total_out);\n+\t_sha1write(pack_file, out, s.total_out);\n \tpack_size += s.total_out;\n \n \te->idx.crc32 = crc32_end(pack_file);\n@@ -1220,7 +1276,7 @@ static void stream_blob(uintmax_t len, unsigned char *sha1out, uintmax_t mark)\n \n \t\tif (!s.avail_out || status == Z_STREAM_END) {\n \t\t\tsize_t n = s.next_out - out_buf;\n-\t\t\tsha1write(pack_file, out_buf, n);\n+\t\t\t_sha1write(pack_file, out_buf, n);\n \t\t\tpack_size += n;\n \t\t\ts.next_out = out_buf;\n \t\t\ts.avail_out = out_sz;\n@@ -1295,26 +1351,6 @@ static void *gfi_unpack_entry(\n {\n \tenum object_type type;\n \tstruct packed_git *p = all_packs[oe->pack_id];\n-\tif (p == pack_data && p->pack_size < (pack_size + 20)) {\n-\t\t/* The object is stored in the packfile we are writing to\n-\t\t * and we have modified it since the last time we scanned\n-\t\t * back to read a previously written object.  If an old\n-\t\t * window covered [p->pack_size, p->pack_size + 20) its\n-\t\t * data is stale and is not valid.  Closing all windows\n-\t\t * and updating the packfile length ensures we can read\n-\t\t * the newly written data.\n-\t\t */\n-\t\tclose_pack_windows(p);\n-\t\tsha1flush(pack_file);\n-\n-\t\t/* We have to offer 20 bytes additional on the end of\n-\t\t * the packfile as the core unpacker code assumes the\n-\t\t * footer is present at the file end and must promise\n-\t\t * at least 20 bytes within any window it maps.  But\n-\t\t * we don't actually create the footer here.\n-\t\t */\n-\t\tp->pack_size = pack_size + 20;\n-\t}\n \treturn unpack_entry(p, oe->idx.offset, &type, sizep);\n }\n \n-- \n2.9.0.dirty\n\n"},{"id":"290781","messageId":"20160704000135.GA9467@glandium.org","threadId":"42769","inReplyTo":"20160703234439.8889-1-mh@glandium.org","subject":"Re: [PATCH/RFC] fast-import: Keep a fake pack window on the recently written data","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2016-07-04T00:01:36Z","receivedAt":"2016-07-04T00:01:46Z","isPatch":true,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Mon, Jul 04, 2016 at 08:44:39AM +0900, Mike Hommey wrote:\n> +\t\t/* Ensure a pack window on the data before that, otherwise,\n> +\t\t * use_pack() may try to create a window that overlaps with\n> +\t\t * this one, and that won't work because it won't be complete. */\n\nIn fact, there is still a possibility of this happening after that pack\nwindow in closed when opening windows on other packs.\n\nMike\n"},{"id":"292019","messageId":"20160722221929.uusi4lowxow3ddmh@glandium.org","threadId":"42769","inReplyTo":"20160703234439.8889-1-mh@glandium.org","subject":"Re: [PATCH/RFC] fast-import: Keep a fake pack window on the recently written data","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2016-07-22T22:19:29Z","receivedAt":"2016-07-22T22:19:42Z","isPatch":true,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"Hi,\n\nAny thoughts on the following?\n\nMike\n\nOn Mon, Jul 04, 2016 at 08:44:39AM +0900, Mike Hommey wrote:\n> The are many ways in which fast-import ends up calling gfi_unpack_entry,\n> and fery few work-arounds. I've patched fast-import for it to be smarter\n> in corner cases, allowing some additional work-arounds, but it's just\n> too easy to fall on gfi_unpack_entry again, so I abandonned that path.\n> \n> The problem with gfi_unpack_entry is that if something has been written\n> to the pack after last time it was used, it closes all pack windows. On\n> OSX, this triggers munmap, which shows up in performance profiles.\n> \n> To give an idea how bad this is, here is how long it takes to clone\n> https://hg.mozilla.org/mozilla-unified/ with the master branch of\n> git-cinnabar (which uses fast-import) on a mac mini: more than 5 hours.\n> I can't actually give the exact number, because it was killed, after\n> spending 2 hours importing 1.77M files and 3 hours importing 120k\n> manifests.\n> \n> The same clone, with a variant of this patch, *finished* in 2 hours and\n> 10 minutes, spending 24 minutes importing the same 1.77M files and only\n> 13 minutes to cover the same 120k manifests. It took an hour and 20\n> minutes to cover the remaining 210k manifests. You can imagine how long\n> it would have taken without the patch if it hadn't been killed...\n> \n> Now, this is proof of concept level. There are many things that are not\n> right with this patch, starting from the fact it doesn't handle\n> checkpoints, and isn't safe for every kind of integer overflows. Or\n> malloc'ating exactly packed_git_window_size bytes (which on 64-bits\n> systems, is 1GB), etc.\n> \n> But it feels to me this kind of fake pack window is a cheap way to\n> counter the slowness of munmap on OSX, although the fact that it's a\n> hack around the pack code in sha1_file.c is not very nice. Maybe a\n> better start to fix the issue would be to add better interfaces to\n> the pack code to handle pack writers that can read at the same time.\n> \n> Thoughts?\n> \n> Past related discussions:\n>   $gmane/291717\n>   $gmane/273465\n> ---\n>  fast-import.c | 90 +++++++++++++++++++++++++++++++++++++++++------------------\n>  1 file changed, 63 insertions(+), 27 deletions(-)\n> \n> diff --git a/fast-import.c b/fast-import.c\n> index c504ef7..4e26883 100644\n> --- a/fast-import.c\n> +++ b/fast-import.c\n> @@ -316,6 +316,7 @@ static struct atom_str **atom_table;\n>  static struct pack_idx_option pack_idx_opts;\n>  static unsigned int pack_id;\n>  static struct sha1file *pack_file;\n> +static struct pack_window *pack_win;\n>  static struct packed_git *pack_data;\n>  static struct packed_git **all_packs;\n>  static off_t pack_size;\n> @@ -862,6 +863,39 @@ static struct tree_content *dup_tree_content(struct tree_content *s)\n>  \treturn d;\n>  }\n>  \n> +static void _sha1write(struct sha1file *f, const void *buf, unsigned int count)\n> +{\n> +\tsha1write(f, buf, count);\n> +\t/* Always last used */\n> +\tpack_win->last_used = -1;\n> +\tpack_win->inuse_cnt = -1;\n> +\n> +\tpack_data->pack_size += count;\n> +\n> +\tif (packed_git_window_size - pack_win->len >= count) {\n> +\t\tmemcpy(pack_win->base + pack_win->len - 20, buf, count);\n> +\t\tpack_win->len += count;\n> +\t} else {\n> +\t\tstruct pack_window *cursor = NULL;\n> +\t\t/* We're sliding the window, so we don't need to memcpy\n> +\t\t * everything. */\n> +\t\tpack_win->offset += ((pack_win->len - 20 + count)\n> +\t\t\t / packed_git_window_size) * packed_git_window_size;\n> +\t\tpack_win->len = count % packed_git_window_size -\n> +\t\t\t(packed_git_window_size - pack_win->len);\n> +\t\tmemcpy(pack_win->base, buf + count - pack_win->len + 20,\n> +\t\t       pack_win->len - 20);\n> +\n> +\t\t/* Ensure a pack window on the data before that, otherwise,\n> +\t\t * use_pack() may try to create a window that overlaps with\n> +\t\t * this one, and that won't work because it won't be complete. */\n> +\t\tsha1flush(f);\n> +\t\tuse_pack(pack_data, &cursor,\n> +\t\t\t pack_win->offset - packed_git_window_size, NULL);\n> +\t\tunuse_pack(&cursor);\n> +\t}\n> +}\n> +\n>  static void start_packfile(void)\n>  {\n>  \tstatic char tmp_file[PATH_MAX];\n> @@ -873,15 +907,22 @@ static void start_packfile(void)\n>  \t\t\t      \"pack/tmp_pack_XXXXXX\");\n>  \tFLEX_ALLOC_STR(p, pack_name, tmp_file);\n>  \tp->pack_fd = pack_fd;\n> +\tp->pack_size = 20;\n>  \tp->do_not_close = 1;\n>  \tpack_file = sha1fd(pack_fd, p->pack_name);\n>  \n> +\tp->windows = pack_win = xcalloc(1, sizeof(*p->windows));\n> +\tpack_win->offset = 0;\n> +\tpack_win->len = 20;\n> +\tpack_win->base = xmalloc(packed_git_window_size);\n> +\tpack_win->next = NULL;\n> +\n>  \thdr.hdr_signature = htonl(PACK_SIGNATURE);\n>  \thdr.hdr_version = htonl(2);\n>  \thdr.hdr_entries = 0;\n> -\tsha1write(pack_file, &hdr, sizeof(hdr));\n> -\n>  \tpack_data = p;\n> +\t_sha1write(pack_file, &hdr, sizeof(hdr));\n> +\n>  \tpack_size = sizeof(hdr);\n>  \tobject_count = 0;\n>  \n> @@ -954,10 +995,25 @@ static void unkeep_all_packs(void)\n>  static void end_packfile(void)\n>  {\n>  \tstatic int running;\n> +\tstruct pack_window *win, *prev;\n>  \n>  \tif (running || !pack_data)\n>  \t\treturn;\n>  \n> +\t/* Remove the fake pack window first */\n> +\tfor (prev = NULL, win = pack_data->windows; win;\n> +\t     prev = win, win = win->next) {\n> +\t\tif (win != pack_win)\n> +\t\t\tcontinue;\n> +\t\tif (prev)\n> +\t\t\tprev->next = win->next;\n> +\t\telse\n> +\t\t\tpack_data->windows = win->next;\n> +\t\tbreak;\n> +\t}\n> +\tfree(pack_win->base);\n> +\tfree(pack_win);\n> +\n>  \trunning = 1;\n>  \tclear_delta_base_cache();\n>  \tif (object_count) {\n> @@ -1122,22 +1178,22 @@ static int store_object(\n>  \t\te->depth = last->depth + 1;\n>  \n>  \t\thdrlen = encode_in_pack_object_header(OBJ_OFS_DELTA, deltalen, hdr);\n> -\t\tsha1write(pack_file, hdr, hdrlen);\n> +\t\t_sha1write(pack_file, hdr, hdrlen);\n>  \t\tpack_size += hdrlen;\n>  \n>  \t\thdr[pos] = ofs & 127;\n>  \t\twhile (ofs >>= 7)\n>  \t\t\thdr[--pos] = 128 | (--ofs & 127);\n> -\t\tsha1write(pack_file, hdr + pos, sizeof(hdr) - pos);\n> +\t\t_sha1write(pack_file, hdr + pos, sizeof(hdr) - pos);\n>  \t\tpack_size += sizeof(hdr) - pos;\n>  \t} else {\n>  \t\te->depth = 0;\n>  \t\thdrlen = encode_in_pack_object_header(type, dat->len, hdr);\n> -\t\tsha1write(pack_file, hdr, hdrlen);\n> +\t\t_sha1write(pack_file, hdr, hdrlen);\n>  \t\tpack_size += hdrlen;\n>  \t}\n>  \n> -\tsha1write(pack_file, out, s.total_out);\n> +\t_sha1write(pack_file, out, s.total_out);\n>  \tpack_size += s.total_out;\n>  \n>  \te->idx.crc32 = crc32_end(pack_file);\n> @@ -1220,7 +1276,7 @@ static void stream_blob(uintmax_t len, unsigned char *sha1out, uintmax_t mark)\n>  \n>  \t\tif (!s.avail_out || status == Z_STREAM_END) {\n>  \t\t\tsize_t n = s.next_out - out_buf;\n> -\t\t\tsha1write(pack_file, out_buf, n);\n> +\t\t\t_sha1write(pack_file, out_buf, n);\n>  \t\t\tpack_size += n;\n>  \t\t\ts.next_out = out_buf;\n>  \t\t\ts.avail_out = out_sz;\n> @@ -1295,26 +1351,6 @@ static void *gfi_unpack_entry(\n>  {\n>  \tenum object_type type;\n>  \tstruct packed_git *p = all_packs[oe->pack_id];\n> -\tif (p == pack_data && p->pack_size < (pack_size + 20)) {\n> -\t\t/* The object is stored in the packfile we are writing to\n> -\t\t * and we have modified it since the last time we scanned\n> -\t\t * back to read a previously written object.  If an old\n> -\t\t * window covered [p->pack_size, p->pack_size + 20) its\n> -\t\t * data is stale and is not valid.  Closing all windows\n> -\t\t * and updating the packfile length ensures we can read\n> -\t\t * the newly written data.\n> -\t\t */\n> -\t\tclose_pack_windows(p);\n> -\t\tsha1flush(pack_file);\n> -\n> -\t\t/* We have to offer 20 bytes additional on the end of\n> -\t\t * the packfile as the core unpacker code assumes the\n> -\t\t * footer is present at the file end and must promise\n> -\t\t * at least 20 bytes within any window it maps.  But\n> -\t\t * we don't actually create the footer here.\n> -\t\t */\n> -\t\tp->pack_size = pack_size + 20;\n> -\t}\n>  \treturn unpack_entry(p, oe->idx.offset, &type, sizep);\n>  }\n>  \n> -- \n> 2.9.0.dirty\n> \n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at  http://vger.kernel.org/majordomo-info.html\n"}]}