{"thread":{"id":"60760","subject":"[PATCH 0/2] reftable/stack: fix race in up-to-date check","startedAt":"2024-01-18T13:41:51Z","lastAt":"2024-01-23T00:32:46Z","messageCount":7,"participants":["Patrick Steinhardt","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"486975","messageId":"cover.1705585037.git.ps@pks.im","threadId":"60760","inReplyTo":null,"subject":"[PATCH 0/2] reftable/stack: fix race in up-to-date check","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-18T13:41:46Z","receivedAt":"2024-01-18T13:41:51Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nIn 6fdfaf15 (reftable/stack: use stat info to avoid re-reading stack\nlist, 2024-01-11) we have introduced a new mechanism to avoid re-reading\nthe table list in case stat(3P) figures out that the stack didn't change\nsince the last time we read it.\n\nUnfortunately, I've been able to hit a bug there that can happen under\nvery specific circumstances when a reading and writing process race with\neach other. When the writer appends to the stack and then compacts it,\nit may happen that we recycle the previously-used inode of \"tables.list\"\nso that the resulting `struct stat` exactly matches the cached value of\nthe reading process.\n\nThe first patch is merely cosmetic, whereas the second patch fixes the\ndescribed race. The topic depends on ps/reftable-optimize-io, which has\nintroduced the issue.\n\nPatrick\n\nPatrick Steinhardt (2):\n  reftable/stack: unconditionally reload stack after commit\n  reftable/stack: fix race in up-to-date check\n\n reftable/stack.c  | 101 ++++++++++++++++++++++++++++++++++++++++++----\n reftable/stack.h  |   4 +-\n reftable/system.h |   1 -\n 3 files changed, 96 insertions(+), 10 deletions(-)\n\n\nbase-commit: 718a93ecc06ed59dda4e6a5d91b1c2169275694f\n-- \n2.43.GIT\n\n"},{"id":"486976","messageId":"568aa5b808013ca782fac45d03e01bbf9323bb38.1705585037.git.ps@pks.im","threadId":"60760","inReplyTo":"cover.1705585037.git.ps@pks.im","subject":"[PATCH 1/2] reftable/stack: unconditionally reload stack after commit","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-18T13:41:51Z","receivedAt":"2024-01-18T13:41:54Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"After we have committed an addition to the reftable stack we call\n`reftable_stack_reload()` to reload the stack and thus reflect the\nchanges that were just added. This function will only conditionally\nreload the stack in case `stack_uptodate()` tells us that the stack\nneeds reloading. This check is wasteful though because we already know\nthat the stack needs reloading.\n\nCall `reftable_stack_reload_maybe_reuse()` instead, which will\nunconditionally reload the stack. This is merely a conceptual fix, the\ncode in question was not found to cause any problems in practice.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/stack.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/reftable/stack.c b/reftable/stack.c\nindex c28d82299d..705cfb6caa 100644\n--- a/reftable/stack.c\n+++ b/reftable/stack.c\n@@ -585,7 +585,7 @@ int reftable_addition_commit(struct reftable_addition *add)\n \tadd->new_tables = NULL;\n \tadd->new_tables_len = 0;\n \n-\terr = reftable_stack_reload(add->stack);\n+\terr = reftable_stack_reload_maybe_reuse(add->stack, 1);\n \tif (err)\n \t\tgoto done;\n \n-- \n2.43.GIT\n\n"},{"id":"486977","messageId":"713e51a25c1c4cfa830db97f71cd7c39e85864d4.1705585037.git.ps@pks.im","threadId":"60760","inReplyTo":"cover.1705585037.git.ps@pks.im","subject":"[PATCH 2/2] reftable/stack: fix race in up-to-date check","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-18T13:41:56Z","receivedAt":"2024-01-18T13:41:59Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In 6fdfaf15a0 (reftable/stack: use stat info to avoid re-reading stack\nlist, 2024-01-11) we have introduced a new mechanism to avoid re-reading\nthe table list in case stat(3P) figures out that the stack didn't change\nsince the last time we read it.\n\nWhile this change significantly improved performance when writing many\nrefs, it can unfortunately lead to false negatives in very specific\nscenarios. Given two processes A and B, there is a feasible sequence of\nevents that cause us to accidentally treat the table list as up-to-date\neven though it changed:\n\n  1. A reads the reftable stack and caches its stat info.\n\n  2. B updates the stack, appending a new table to \"tables.list\". This\n     will both use a new inode and result in a different file size, thus\n     invalidating A's cache in theory.\n\n  3. B decides to auto-compact the stack and merges two tables. The file\n     size now matches what A has cached again. Furthermore, the\n     filesystem may decide to recycle the inode number of the file we\n     have replaced in (2) because it is not in use anymore.\n\n  4. A reloads the reftable stack. Neither the inode number nor the\n     file size changed. If the timestamps did not change either then we\n     think the cached copy of our stack is up-to-date.\n\nIn fact, the commit introduced three related issues:\n\n  - Non-POSIX compliant systems may not report proper `st_dev` and\n    `st_ino` values in stat(3P), which made us rely solely on the\n    file's potentially coarse-grained mtime and ctime.\n\n  - `stat_validity_check()` and friends may end up not comparing\n    `st_dev` and `st_ino` depending on the \"core.checkstat\" config,\n    again reducing the signal to the mtime and ctime.\n\n  - `st_ino` can be recycled, rendering the check moot even on\n    POSIX-compliant systems.\n\nGiven that POSIX defines that \"The st_ino and st_dev fields taken\ntogether uniquely identify the file within the system\", these issues led\nto the most important signal to establish file identity to be ignored or\nbecome useless in some cases.\n\nRefactor the code to stop using `stat_validity_check()`. Instead, we\nmanually stat(3P) the file descriptors to make relevant information\navailable. On Windows and MSYS2 the result will have both `st_dev` and\n`st_ino` set to 0, which allows us to address the first issue by not\nusing the stat-based cache in that case. It also allows us to make sure\nthat we always compare `st_dev` and `st_ino`, addressing the second\nissue.\n\nThe third issue of inode recycling can be addressed by keeping the file\ndescriptor of \"files.list\" open during the lifetime of the reftable\nstack. As the file will still exist on disk even though it has been\nunlinked it is impossible for its inode to be recycled as long as the\nfile descriptor is still open.\n\nThis should address the race in a POSIX-compliant way. The only real\ndownside is that this mechanism cannot be used on non-POSIX-compliant\nsystems like Windows. But we at least have the second-level caching\nmechanism in place that compares contents of \"files.list\" with the\ncurrently loaded list of tables.\n\nThis new mechanism performs roughly the same as the previous one that\nrelied on `stat_validity_check()`:\n\n  Benchmark 1: update-ref: create many refs (HEAD~)\n    Time (mean ± σ):      4.754 s ±  0.026 s    [User: 2.204 s, System: 2.549 s]\n    Range (min … max):    4.694 s …  4.802 s    20 runs\n\n  Benchmark 2: update-ref: create many refs (HEAD)\n    Time (mean ± σ):      4.721 s ±  0.020 s    [User: 2.194 s, System: 2.527 s]\n    Range (min … max):    4.691 s …  4.753 s    20 runs\n\n  Summary\n    update-ref: create many refs (HEAD~) ran\n      1.01 ± 0.01 times faster than update-ref: create many refs (HEAD)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/stack.c  | 99 +++++++++++++++++++++++++++++++++++++++++++----\n reftable/stack.h  |  4 +-\n reftable/system.h |  1 -\n 3 files changed, 95 insertions(+), 9 deletions(-)\n\ndiff --git a/reftable/stack.c b/reftable/stack.c\nindex 705cfb6caa..77a387a86c 100644\n--- a/reftable/stack.c\n+++ b/reftable/stack.c\n@@ -66,6 +66,7 @@ int reftable_new_stack(struct reftable_stack **dest, const char *dir,\n \tstrbuf_addstr(&list_file_name, \"/tables.list\");\n \n \tp->list_file = strbuf_detach(&list_file_name, NULL);\n+\tp->list_fd = -1;\n \tp->reftable_dir = xstrdup(dir);\n \tp->config = config;\n \n@@ -175,7 +176,12 @@ void reftable_stack_destroy(struct reftable_stack *st)\n \t\tst->readers_len = 0;\n \t\tFREE_AND_NULL(st->readers);\n \t}\n-\tstat_validity_clear(&st->list_validity);\n+\n+\tif (st->list_fd >= 0) {\n+\t\tclose(st->list_fd);\n+\t\tst->list_fd = -1;\n+\t}\n+\n \tFREE_AND_NULL(st->list_file);\n \tFREE_AND_NULL(st->reftable_dir);\n \treftable_free(st);\n@@ -375,11 +381,59 @@ static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,\n \t\tsleep_millisec(delay);\n \t}\n \n-\tstat_validity_update(&st->list_validity, fd);\n-\n out:\n-\tif (err)\n-\t\tstat_validity_clear(&st->list_validity);\n+\t/*\n+\t * Invalidate the stat cache. It is sufficient to only close the file\n+\t * descriptor and keep the cached stat info because we never use the\n+\t * latter when the former is negative.\n+\t */\n+\tif (st->list_fd >= 0) {\n+\t\tclose(st->list_fd);\n+\t\tst->list_fd = -1;\n+\t}\n+\n+\t/*\n+\t * Cache stat information in case it provides a useful signal to us.\n+\t * According to POSIX, \"The st_ino and st_dev fields taken together\n+\t * uniquely identify the file within the system.\" That being said,\n+\t * Windows is not POSIX compliant and we do not have these fields\n+\t * available. So the information we have there is insufficient to\n+\t * determine whether two file descriptors point to the same file.\n+\t *\n+\t * While we could fall back to using other signals like the file's\n+\t * mtime, those are not sufficient to avoid races. We thus refrain from\n+\t * using the stat cache on such systems and fall back to the secondary\n+\t * caching mechanism, which is to check whether contents of the file\n+\t * have changed.\n+\t *\n+\t * On other systems which are POSIX compliant we must keep the file\n+\t * descriptor open. This is to avoid a race condition where two\n+\t * processes access the reftable stack at the same point in time:\n+\t *\n+\t *   1. A reads the reftable stack and caches its stat info.\n+\t *\n+\t *   2. B updates the stack, appending a new table to \"tables.list\".\n+\t *      This will both use a new inode and result in a different file\n+\t *      size, thus invalidating A's cache in theory.\n+\t *\n+\t *   3. B decides to auto-compact the stack and merges two tables. The\n+\t *      file size now matches what A has cached again. Furthermore, the\n+\t *      filesystem may decide to recycle the inode number of the file\n+\t *      we have replaced in (2) because it is not in use anymore.\n+\t *\n+\t *   4. A reloads the reftable stack. Neither the inode number nor the\n+\t *      file size changed. If the timestamps did not change either then\n+\t *      we think the cached copy of our stack is up-to-date.\n+\t *\n+\t * By keeping the file descriptor open the inode number cannot be\n+\t * recycled, mitigating the race.\n+\t */\n+\tif (!err && fd >= 0 && !fstat(fd, &st->list_st) &&\n+\t    st->list_st.st_dev && st->list_st.st_ino) {\n+\t\tst->list_fd = fd;\n+\t\tfd = -1;\n+\t}\n+\n \tif (fd >= 0)\n \t\tclose(fd);\n \tfree_names(names);\n@@ -396,8 +450,39 @@ static int stack_uptodate(struct reftable_stack *st)\n \tint err;\n \tint i = 0;\n \n-\tif (stat_validity_check(&st->list_validity, st->list_file))\n-\t\treturn 0;\n+\t/*\n+\t * When we have cached stat information available then we use it to\n+\t * verify whether the file has been rewritten.\n+\t *\n+\t * Note that we explicitly do not want to use `stat_validity_check()`\n+\t * and friends here because they may end up not comparing the `st_dev`\n+\t * and `st_ino` fields. These functions thus cannot guarantee that we\n+\t * indeed still have the same file.\n+\t */\n+\tif (st->list_fd >= 0) {\n+\t\tstruct stat list_st;\n+\n+\t\tif (stat(st->list_file, &list_st) < 0) {\n+\t\t\t/*\n+\t\t\t * It's fine for \"tables.list\" to not exist. In that\n+\t\t\t * case, we have to refresh when the loaded stack has\n+\t\t\t * any readers.\n+\t\t\t */\n+\t\t\tif (errno == ENOENT)\n+\t\t\t\treturn !!st->readers_len;\n+\t\t\treturn REFTABLE_IO_ERROR;\n+\t\t}\n+\n+\t\t/*\n+\t\t * When \"tables.list\" refers to the same file we can assume\n+\t\t * that it didn't change. This is because we always use\n+\t\t * rename(3P) to update the file and never write to it\n+\t\t * directly.\n+\t\t */\n+\t\tif (st->list_st.st_dev == list_st.st_dev &&\n+\t\t    st->list_st.st_ino == list_st.st_ino)\n+\t\t\treturn 0;\n+\t}\n \n \terr = read_lines(st->list_file, &names);\n \tif (err < 0)\ndiff --git a/reftable/stack.h b/reftable/stack.h\nindex 3f80cc598a..c1e3efa899 100644\n--- a/reftable/stack.h\n+++ b/reftable/stack.h\n@@ -14,8 +14,10 @@ license that can be found in the LICENSE file or at\n #include \"reftable-stack.h\"\n \n struct reftable_stack {\n-\tstruct stat_validity list_validity;\n+\tstruct stat list_st;\n \tchar *list_file;\n+\tint list_fd;\n+\n \tchar *reftable_dir;\n \tint disable_auto_compact;\n \ndiff --git a/reftable/system.h b/reftable/system.h\nindex 2cc7adf271..6b74a81514 100644\n--- a/reftable/system.h\n+++ b/reftable/system.h\n@@ -12,7 +12,6 @@ license that can be found in the LICENSE file or at\n /* This header glues the reftable library to the rest of Git */\n \n #include \"git-compat-util.h\"\n-#include \"statinfo.h\"\n #include \"strbuf.h\"\n #include \"hash-ll.h\" /* hash ID, sizes.*/\n #include \"dir.h\" /* remove_dir_recursively, for tests.*/\n-- \n2.43.GIT\n\n"},{"id":"486995","messageId":"xmqqcytyquc5.fsf@gitster.g","threadId":"60760","inReplyTo":"713e51a25c1c4cfa830db97f71cd7c39e85864d4.1705585037.git.ps@pks.im","subject":"Re: [PATCH 2/2] reftable/stack: fix race in up-to-date check","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-01-18T20:07:06Z","receivedAt":"2024-01-18T20:07:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n\n> This should address the race in a POSIX-compliant way. The only real\n> downside is that this mechanism cannot be used on non-POSIX-compliant\n> systems like Windows. But we at least have the second-level caching\n> mechanism in place that compares contents of \"files.list\" with the\n> currently loaded list of tables.\n\nOK.\n\n\n> +\t/*\n> +\t * Cache stat information in case it provides a useful signal to us.\n> +\t * According to POSIX, \"The st_ino and st_dev fields taken together\n> +\t * uniquely identify the file within the system.\" That being said,\n> +\t * Windows is not POSIX compliant and we do not have these fields\n> +\t * available. So the information we have there is insufficient to\n> +\t * determine whether two file descriptors point to the same file.\n> +\t *\n> +\t * While we could fall back to using other signals like the file's\n> +\t * mtime, those are not sufficient to avoid races. We thus refrain from\n> +\t * using the stat cache on such systems and fall back to the secondary\n> +\t * caching mechanism, which is to check whether contents of the file\n> +\t * have changed.\n\nOK.\n\n> +\t *\n> +\t * On other systems which are POSIX compliant we must keep the file\n> +\t * descriptor open. This is to avoid a race condition where two\n> +\t * processes access the reftable stack at the same point in time:\n> +\t *\n> +\t *   1. A reads the reftable stack and caches its stat info.\n> +\t *\n> +\t *   2. B updates the stack, appending a new table to \"tables.list\".\n> +\t *      This will both use a new inode and result in a different file\n> +\t *      size, thus invalidating A's cache in theory.\n> +\t *\n> +\t *   3. B decides to auto-compact the stack and merges two tables. The\n> +\t *      file size now matches what A has cached again. Furthermore, the\n> +\t *      filesystem may decide to recycle the inode number of the file\n> +\t *      we have replaced in (2) because it is not in use anymore.\n> +\t *\n> +\t *   4. A reloads the reftable stack. Neither the inode number nor the\n> +\t *      file size changed. If the timestamps did not change either then\n> +\t *      we think the cached copy of our stack is up-to-date.\n> +\t *\n> +\t * By keeping the file descriptor open the inode number cannot be\n> +\t * recycled, mitigating the race.\n> +\t */\n\nThis is nasty.  Well diagnosed and fixed.\n\nWill queue.\n\nThanks.\n"},{"id":"487124","messageId":"20240120010559.GE117170@coredump.intra.peff.net","threadId":"60760","inReplyTo":"713e51a25c1c4cfa830db97f71cd7c39e85864d4.1705585037.git.ps@pks.im","subject":"Re: [PATCH 2/2] reftable/stack: fix race in up-to-date check","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-01-20T01:05:59Z","receivedAt":"2024-01-20T01:06:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 18, 2024 at 02:41:56PM +0100, Patrick Steinhardt wrote:\n\n> Refactor the code to stop using `stat_validity_check()`. Instead, we\n> manually stat(3P) the file descriptors to make relevant information\n> available. On Windows and MSYS2 the result will have both `st_dev` and\n> `st_ino` set to 0, which allows us to address the first issue by not\n> using the stat-based cache in that case. It also allows us to make sure\n> that we always compare `st_dev` and `st_ino`, addressing the second\n> issue.\n\nI didn't think too hard about the details, but does this mean that\nevery user of stat_validity_check() has the same issue? The other big\none is packed-refs (for which the code was originally written). Should\nthis fix go into that API?\n\n-Peff\n"},{"id":"487192","messageId":"Za5ELqZps0DLbb5q@tanuki","threadId":"60760","inReplyTo":"20240120010559.GE117170@coredump.intra.peff.net","subject":"Re: [PATCH 2/2] reftable/stack: fix race in up-to-date check","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-22T10:32:14Z","receivedAt":"2024-01-22T10:32:21Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Jan 19, 2024 at 08:05:59PM -0500, Jeff King wrote:\n> On Thu, Jan 18, 2024 at 02:41:56PM +0100, Patrick Steinhardt wrote:\n> \n> > Refactor the code to stop using `stat_validity_check()`. Instead, we\n> > manually stat(3P) the file descriptors to make relevant information\n> > available. On Windows and MSYS2 the result will have both `st_dev` and\n> > `st_ino` set to 0, which allows us to address the first issue by not\n> > using the stat-based cache in that case. It also allows us to make sure\n> > that we always compare `st_dev` and `st_ino`, addressing the second\n> > issue.\n> \n> I didn't think too hard about the details, but does this mean that\n> every user of stat_validity_check() has the same issue? The other big\n> one is packed-refs (for which the code was originally written). Should\n> this fix go into that API?\n\nIn theory, the issue is the same for the `packed-refs` file. But in\npractice it's much less likely to be an issue:\n\n  - The file gets rewritten a lot less frequently than the \"tables.list\"\n    file, making the race less likely in the first place. It can only\n    happen when git-pack-refs(1) races with concurrent readers, whereas\n    it can happen for any two concurrent process with reftables.\n\n  - Due to entries in the `packed-refs` being of variable length it's\n    less likely that the size will be exactly the same after the file\n    has been rewritten. For reftables we have constant-length entries in\n    the \"tables.list\", so it's likely to happen there.\n\n  - It is very unlikely that we have the same issue with inode reuse\n    with the packed-refs file. The only reason why we have it with the\n    reftable backend is that it is very likely that we end up writing to\n    \"tables.list\" twice, once for the normal update and once for auto\n    compaction.\n\nSo overall, I doubt that it's all that critical in practice for the\npacked-refs backend. It _is_ possible to happen, but chances are\nsignificantly lower. I cannot recall a single report of this issue,\nwhich underpins how unlikely it seems to be for the files backend.\n\nAlso, applying the same fix for the packed-refs would essentially mean\nthat the caching mechanism is now ineffective on Windows systems where\nwe do not have proper `st_dev` and `st_ino` values available. I think\nthis is a no-go in the context of packed-refs because we don't have a\nsecond-level caching mechanism like we do in the reftable backend. It's\nnot great that we have to reread the \"tables.list\" file on Windows\nsystems for now, but at least it's better than having to reread the\ncomplete \"packed-refs\" file like we'd have to do with the files backend.\n\nPatrick\n"},{"id":"487241","messageId":"20240123003244.GB827890@coredump.intra.peff.net","threadId":"60760","inReplyTo":"Za5ELqZps0DLbb5q@tanuki","subject":"Re: [PATCH 2/2] reftable/stack: fix race in up-to-date check","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-01-23T00:32:44Z","receivedAt":"2024-01-23T00:32:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jan 22, 2024 at 11:32:14AM +0100, Patrick Steinhardt wrote:\n\n> > I didn't think too hard about the details, but does this mean that\n> > every user of stat_validity_check() has the same issue? The other big\n> > one is packed-refs (for which the code was originally written). Should\n> > this fix go into that API?\n> \n> In theory, the issue is the same for the `packed-refs` file. But in\n> practice it's much less likely to be an issue:\n\nThanks for laying this all out. It does concern me a little that there's\nstill a possible race, because they can be so hard to catch and debug in\npractice. But I think you make a compelling argument that it's probably\nnot happening a lot in practice, and especially...\n\n> Also, applying the same fix for the packed-refs would essentially mean\n> that the caching mechanism is now ineffective on Windows systems where\n> we do not have proper `st_dev` and `st_ino` values available. I think\n> this is a no-go in the context of packed-refs because we don't have a\n> second-level caching mechanism like we do in the reftable backend. It's\n> not great that we have to reread the \"tables.list\" file on Windows\n> systems for now, but at least it's better than having to reread the\n> complete \"packed-refs\" file like we'd have to do with the files backend.\n\n...here that the performance profile is so different. If the \"fix\"\nmeans re-reading the whole packed-refs file constantly, that's going\nto be quite noticeable.\n\nGiven that this race has been here forever-ish, I agree with you that we\nshould leave it be.\n\n-Peff\n"}]}