{"thread":{"id":"40432","subject":"broken racy detection and performance issues with nanosecond file times","startedAt":"2015-09-25T23:28:10Z","lastAt":"2015-09-29T13:42:39Z","messageCount":8,"participants":["Karsten Blees","Johannes Schindelin","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"270773","messageId":"5605D88A.20104@gmail.com","threadId":"40432","inReplyTo":null,"subject":"broken racy detection and performance issues with nanosecond file times","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2015-09-25T23:28:10Z","receivedAt":"2015-09-25T23:28:10Z","isPatch":false,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Hi there,\n\nI think I found a few nasty problems with racy detection, as well as\nperformance issues when using git implementations with different file\ntime resolutions on the same repository (e.g. git compiled with and\nwithout USE_NSEC, libgit2 compiled with and without USE_NSEC, JGit\nexecuted in different Java implementations...).\n\nLet me start by listing relevant file time gotchas (skip this if it\nsounds too familiar) before diving into problem descriptions. Some\nideas for potential solutions are at the end.\n\n\nNotable file time facts:\n========================\n\nThe st_ctime discrepancy:\n* stat.st_ctime means \"change time\" (of file metadata) on POSIX\n  systems and \"creation time\" on Windows\n* While some file systems may track all four time stamps (mtime,\n  atime, change time and creation time), there are no public OS APIs\n  to obtain creation time on POSIX / change time on Windows.\n\nLinux:\n* In-core file times may not be properly rounded to on-disk\n  precision, causing spurious file time changes when the cache is\n  refreshed from disk. This was fixed for typical Unix file systems\n  in kernel 2.6.11. The fix for CEPH, CIFS, NTFS, UFS and FUSE will\n  be in kernel 4.3. There's no fix for FAT-based file systems yet.\n* Maximum file time precision is 1 ns (or 1 s with really old glibc).\n\nWindows:\n* Maximum file time precision is 100 ns.\n\nJava <= 6:\n* Only exposes mtime in milliseconds (via File.getLastModifiedTime).\n\nJava >= 7:\n* Only exposes mtime, atime and creation time, no change time (see\n  java.nio.file.attribute.BasicFileAttributes).\n* Maximum file time precision is implementation specific (OpenJDK:\n  1 microsecond on both Unix [1] and Windows [2]).\n* On platforms or file systems that don't support creation time,\n  BasicFileAttribtes.creationTime() is implementation specific\n  (OpenJDK returns mtime instead). There's no public API to detect\n  whether creation time is supported or \"emulated\" in some way.\n\nGit Options:\n* NO_NSEC (git only): compile-time option that disables recording of\n  nanoseconds in the index, implies USE_NSEC=false.\n* USE_NSEC (git and libgit2 with [3]): compile-time option that\n  enables nanosecond comparison in both up-to-date and racy checks.\n* core.checkStat=minimal (git, libgit2, JGit): config-option that\n  disables nanosecond comparison in up-to-date checks, but not in\n  racy checks.\n\nJGit:\n* Only uses mtime, rounded to milliseconds. While there is a\n  DirCacheEntry.setCreationTime() [4] to set the index entry's ctime\n  field, AFAICT its not used anywhere.\n* Does not compare nanoseconds if the cached value recorded in the\n  index is 0, to prevent performance issues with NO_NSEC git\n  implementations [5].\n\n\nProblem 1: Failure to detect racy files (without USE_NSEC)\n==========================================================\n\nGit may not detect racy changes when 'update-index' runs in parallel\nto work tree updates.\n\nConsider this (where timestamps are t<seconds>.<nanoseconds>):\n\n t0.0$ echo \"foo\" > file1\n t0.1$ git update-index file1 &  # runs in background\n t0.2$ # update-index records stats and sha1 of file1 in new index\n t0.3$ echo \"bar\" > file1\n ....$ # update-index writes other index entries\n t1.0$ # update-index finishes (sets mtime of the new index to t1.0!)\n t1.1$ git status # doesn't detect that file1 has changed\n\nThe problem here is that racy checks in 'git status' compare against\nthe new index file's mtime (t1.0), which may be newer than the last\nchange of file1.\n\n\nProblem 2: Failure to detect racy files (mixed USE_NSEC)\n========================================================\n\nGit may fail to detect racy conditions if file times in .git/index\nhave been recorded by another git implementation with better file\ntime resolution.\n\nConsider the following sequence:\n\n t0.0$ echo \"foo\" > file1\n t0.1$ use-nsec-git update-index file1\n t0.2$ echo \"bar\" > file1\n ....$ sleep 1\n t1.0$ touch file2\n t1.1$ use-nsec-git status # rewrites index, to store file2 change\n t1.2$ git status # doesn't detect that file1 has changed\n\nThe problem here is that the first, nsec-enabled 'git status' does\nnot consider file1 racy (with nanosecond precision, the file is dirty\nalready (t0.0 != t0.2), so no racy-checks are performed). Thus, it\nwill not squash the size field (as a second-precision-git would).\nHowever, it will rewrite the index to capture the status change of\nfile2, and thus create a new index file with mtime = t1.1. Similar\nto problem 1, subsequent 'git status' with second-precision has no\nway to detect that file1 has changed.\n\nThis problem would not be limited to USE_NSEC-enabled/disabled git,\nit occurs whenever different file time resolutions are at play, e.g.:\n * second-based git vs. millisecond-based JGit\n * millisecond-based JGit vs. nanosecond-enabled git\n * GIT_WORK_TREE on ext2 (1 s) and GIT_DIR on ext4 (1 ns)\n * JGit executed by different Java implementations (with different\n   file time resolutions)\n\n\nProblem 3: Failure to detect racy files with core.checkStat=minimal\n===================================================================\n\nConsider the example above (problem 2). With core.checkStat=minimal,\nthe nanosecond-enabled git also fails to detect that file1 has\nchanged.\n\nThis is because racy checks are still done with nanosecond precision\n(despite checkStat=minimal), and against the *cached* mtime, not the\nreal one. I.e.:\n * in match_stat_data(), nanoseconds are ignored, and file1 is\n   considered unchanged (as t0[.0] == t0[.2]).\n * in ie_match_stat(), we pass the cache entry to is_racy_timestamp()\n   (which has mtime == t0.0), even though we know the current mtime\n   at this point (t0.2)\n * in is_racy_stat(), file1 is not considered racy, because the index\n   file's mtime (t0.1) is newer than the cached mtime (t0.0)\n\n\nProblem 4: Performance issues with mixed file time resolutions\n==============================================================\n\nA git implementation will consider files dirty (i.e. triggering a\ncontent check) if the index entry has been recorded by another git\nimplementation with lower file time resolution.\n\nExamples:\n\nGit compiled with NO_NSEC writes index entries with nanosecond\nfields == 0. A USE_NSEC-enabled git will consider these files dirty\n(except in the rare case that on-disk nanoseconds of the file time\nare really 0).\n\nJGit writes index entries with mtime nanosecond fields rounded to\nmilliseconds. Again, a USE_NSEC-enabled git will consider the files\ndirty.\n\nJGit writes index entries with ctime seconds and nanoseconds == 0.\nAll other git implementations will consider such files dirty.\n\n\nIdeas for potential solutions:\n==============================\n\nPerformance issues:\n-------------------\n\n1. Compare file times in minimum supported precision\n   When comparing file times, use the minimum precision supported by\n   both the writing and reading git implementations.\n1a. Simplest variant: Don't compare nanoseconds if the field in the\n   cached index entry is 0. JGit already does this [5], but at the\n   same time it is very unfriendly to USE_NSEC-enabled git by storing\n   only milliseconds in the nanosecond field. This \"simple\" solution\n   implies that git implementations that cannot provide full\n   nanosecond precision must leave the nanosecond field empty.\n1b. More involved: Store the precision in the index entry.\n   We only need 30 bits to encode nanoseconds, so the high 2 bits of\n   the nanosecond field could be used as follows:\n   00: second precision (i.e. ignore, for backward compatibility)\n   01: millisecond precision\n   10: microsecond precision\n   11: nanosecond precision\n   When reading the index, USE-NSEC-enabled git implementations would\n   do dirty checks with the minimum precision supported by themselves\n   and the creator of the index entry.\n\n\n2. Don't use ctime in dirty checks if ctime.sec == 0.\n\n\nRacy detection:\n---------------\n\n3. Minimal racy solution\n   * Do all racy checks with second-precision only.\n   * When committing an index.lock file, reset mtime to the time\n     before git started reading the old index (i.e. time(null) when\n     calling read_cache()).\n\n   I believe this should fix all three racy problems described above,\n   although restraining ourselves to second-precision somewhat\n   thwarts the ability to track nanoseconds in the first place.\n   \n   The problem with this solution is that files changed by git itself\n   will appear racy to the next git process, thus increasing the\n   performance penalty after e.g. a large checkout. Although I think\n   that re-reading the file after the file's mtime is the only way to\n   be really sure it hasn't been changed.\n\n\n4. More ideas to solve the racy problem\n   Conceptually, any changes that happen at the same time or after we\n   start capturing information about a file may be missed by the\n   recording process. Thus, a \"safe\" way to use file times for racy /\n   dirty checks would be as follows:\n\n     start_capture = filesystem(file).now()\n     oid = read_sha1(file)\n     mtime1 = lstat(file).mtime\n     racy = mtime1 >= start_capture\n     ...\n     mtime2 = lstat(file).mtime\n     check_content = mtime1 != mtime2 || racy\n\n   Whereas Git currently does something like this:\n\n     mtime1 = lstat(file).mtime\n     oid = read_sha1(file)\n     ...\n     end_capture = lstat(index).mtime\n     mtime2 = lstat(file).mtime\n     check_content = mtime1 != mtime2 || mtime1 >= end_capture   \n\n   One problem with this is that end_capture is only known after\n   closing the index file, which is why currently, racy checks can\n   only be done by the next git process that reads the index.\n\n   Additionally, rewriting the index file changes its mtime and thus\n   deprives subsequent git processes from doing racy checks. This is\n   currently solved by squashing the size field of racy entries.\n   Which means that a third git process needs to fill the size back\n   in, rewriting the index again...\n\n   I suspect that we could get away with fewer index rewrites if we\n   did racy checks in the git process that initially updates the\n   index entry. I.e.:\n    * get start_capture from index.lock immediately after creating it\n      (this ignores that index.lock may be on another file system\n      with different file time precision than the work tree)\n    * do racy checks immediately and store the results in the entry\n    * to accommodate different file time precisions, the racy \"flag\"\n      could indicate at which file time precision the entry would\n      have to be considered racy. E.g.\n        if (mtime1.sec < start_capture.sec)\n          return NOT_RACY;\n\telse if (mtime1.sec > start_capture.sec || \n                 mtime1.nsec >= start_capture.nsec)\n          return ALWAYS_RACY;\n        else if (mtime1.nsec / 1000 == start_capture.nsec / 1000)\n          return RACY_AT_USEC_MSEC_SEC;\n        else if (mitme1.nsec / 1000000 == start_capture.nsec / 1000000)\n          return RACY_AT_MSEC_SEC;\n        else\n          return RACY_AT_SEC;\n    * for backward compatibility, we could still squash the size and\n      store the original size + racy info in an index extension - on\n      the other hand, reliable change detection is so fundamental to\n      an SCM that we may want to keep racy info in the core index\n      entry structure, probably even if it means a format change\n\n   An advantage of this would be that when rewriting the index, git\n   is no longer required to treat racy entries in any special way -\n   if the git command is not interested in the racy entry, it can\n   simply copy it to the next index file, without checking file\n   content or squashing the size field. Commands like git status\n   would only need to rewrite the index if the racy info changes\n   (i.e. enough time has passed).\n\n\nPlease let me know what you think of this...maybe I've completely\nscrewed up and can no longer see the forest for all the trees.\n\nTIA,\nKarsten\n"},{"id":"270801","messageId":"560918F8.1080905@gmail.com","threadId":"40432","inReplyTo":"5605D88A.20104@gmail.com","subject":"[PATCH/RFC] read-cache: fix file time comparisons with different precisions","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2015-09-28T10:39:52Z","receivedAt":"2015-09-28T10:39:52Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Different git variants record file times in the index with different\nprecisions, according to their capabilities. E.g. git compiled with NO_NSEC\nrecords seconds only, JGit records the mtime in milliseconds, but leaves\nctime blank (because ctime is unavailable in Java).\n\nThis causes performance issues in git compiled with USE_NSEC, because index\nentries with such 'incomplete' timestamps are considered dirty, triggering\nunnecessary content checks.\n\nAdd a file time comparison function that auto-detects the precision based\non the number of trailing 0 digits, and compares with the lower precision\nof both values. This initial version supports the known precisions seconds\n(git + NO_NSEC), milliseconds (JGit) and nanoseconds (git + USE_NSEC), but\ncan be easily extended to e.g. microseconds.\n\nUse the new comparison function in both dirty and racy checks. As a side\neffect, this fixes racy detection in USE_NSEC-enabled git with\ncore.checkStat=minimal, as the coreStat setting now affects racy checks as\nwell.\n\nFinally, do not check ctime if ctime.sec is 0 (as recorded by JGit).\n\nSigned-off-by: Karsten Blees <blees@dcon.de>\n---\n read-cache.c | 62 ++++++++++++++++++++++++++++++++++++++++--------------------\n 1 file changed, 41 insertions(+), 21 deletions(-)\n\n\nThis patch fixes problems 3 and 4, by trying to auto-detect the recorded file\ntime precision.\n\n\ndiff --git a/read-cache.c b/read-cache.c\nindex 87204a5..3a4e6cd 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -99,23 +99,50 @@ void fill_stat_data(struct stat_data *sd, struct stat *st)\n \tsd->sd_size = st->st_size;\n }\n \n+/*\n+ * Compares two file times. Returns 0 if equal, <0 if t1 < t2, >0 if t1 > t2.\n+ * Auto-detects precision based on trailing 0 digits. Compares seconds only if\n+ * core.checkStat=minimal.\n+ */\n+static inline int cmp_filetime(uint32_t t1_sec, uint32_t t1_nsec,\n+\t\t\t       uint32_t t2_sec, uint32_t t2_nsec) {\n+#ifdef USE_NSEC\n+\t/*\n+\t * Compare seconds and return result if different, or checkStat=mimimal,\n+\t * or one of the time stamps has second precision only (nsec == 0).\n+\t */\n+\tint diff = t1_sec - t2_sec;\n+\tif (diff || !check_stat || !t1_nsec || !t2_nsec)\n+\t\treturn diff;\n+\n+\t/*\n+\t * Check if one of the time stamps has millisecond precision only (i.e.\n+\t * the trailing 6 digits are 0). First check the trailing 6 bits so that\n+\t * we only do (slower) modulo division if necessary.\n+\t */\n+\tif ((!(t1_nsec & 0x3f) && !(t1_nsec % 1000000)) ||\n+\t    (!(t2_nsec & 0x3f) && !(t2_nsec % 1000000)))\n+\t\t/* Compare milliseconds. */\n+\t\treturn (t1_nsec - t2_nsec) / 1000000;\n+\n+\t/* Compare nanoseconds */\n+\treturn t1_nsec - t2_nsec;\n+#else\n+\treturn t1_sec - t2_sec;\n+#endif\n+}\n+\n int match_stat_data(const struct stat_data *sd, struct stat *st)\n {\n \tint changed = 0;\n \n-\tif (sd->sd_mtime.sec != (unsigned int)st->st_mtime)\n-\t\tchanged |= MTIME_CHANGED;\n-\tif (trust_ctime && check_stat &&\n-\t    sd->sd_ctime.sec != (unsigned int)st->st_ctime)\n-\t\tchanged |= CTIME_CHANGED;\n-\n-#ifdef USE_NSEC\n-\tif (check_stat && sd->sd_mtime.nsec != ST_MTIME_NSEC(*st))\n+\tif (cmp_filetime(sd->sd_mtime.sec, sd->sd_mtime.nsec,\n+\t\t\t (unsigned) st->st_mtime, ST_MTIME_NSEC(*st)))\n \t\tchanged |= MTIME_CHANGED;\n-\tif (trust_ctime && check_stat &&\n-\t    sd->sd_ctime.nsec != ST_CTIME_NSEC(*st))\n+\tif (trust_ctime && check_stat && sd->sd_ctime.sec &&\n+\t    cmp_filetime(sd->sd_ctime.sec, sd->sd_ctime.nsec,\n+\t\t\t (unsigned) st->st_ctime, ST_CTIME_NSEC(*st)))\n \t\tchanged |= CTIME_CHANGED;\n-#endif\n \n \tif (check_stat) {\n \t\tif (sd->sd_uid != (unsigned int) st->st_uid ||\n@@ -276,16 +303,9 @@ static int ce_match_stat_basic(const struct cache_entry *ce, struct stat *st)\n static int is_racy_stat(const struct index_state *istate,\n \t\t\tconst struct stat_data *sd)\n {\n-\treturn (istate->timestamp.sec &&\n-#ifdef USE_NSEC\n-\t\t /* nanosecond timestamped files can also be racy! */\n-\t\t(istate->timestamp.sec < sd->sd_mtime.sec ||\n-\t\t (istate->timestamp.sec == sd->sd_mtime.sec &&\n-\t\t  istate->timestamp.nsec <= sd->sd_mtime.nsec))\n-#else\n-\t\tistate->timestamp.sec <= sd->sd_mtime.sec\n-#endif\n-\t\t);\n+\treturn istate->timestamp.sec &&\n+\t       (cmp_filetime(istate->timestamp.sec, istate->timestamp.nsec,\n+\t\t\t     sd->sd_mtime.sec, sd->sd_mtime.nsec) <= 0);\n }\n \n static int is_racy_timestamp(const struct index_state *istate,\n-- \n2.1.0.msysgit.0\n"},{"id":"270803","messageId":"763be6c1331ac57cf7dee3636d82f994@dscho.org","threadId":"40432","inReplyTo":"560918F8.1080905@gmail.com","subject":"Re: [PATCH/RFC] read-cache: fix file time comparisons with different precisions","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2015-09-28T12:52:38Z","receivedAt":"2015-09-28T12:52:38Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Karsten,\n\nOn 2015-09-28 12:39, Karsten Blees wrote:\n> Different git variants record file times in the index with different\n> precisions, according to their capabilities. E.g. git compiled with NO_NSEC\n> records seconds only, JGit records the mtime in milliseconds, but leaves\n> ctime blank (because ctime is unavailable in Java).\n> \n> This causes performance issues in git compiled with USE_NSEC, because index\n> entries with such 'incomplete' timestamps are considered dirty, triggering\n> unnecessary content checks.\n> \n> Add a file time comparison function that auto-detects the precision based\n> on the number of trailing 0 digits, and compares with the lower precision\n> of both values. This initial version supports the known precisions seconds\n> (git + NO_NSEC), milliseconds (JGit) and nanoseconds (git + USE_NSEC), but\n> can be easily extended to e.g. microseconds.\n> \n> Use the new comparison function in both dirty and racy checks. As a side\n> effect, this fixes racy detection in USE_NSEC-enabled git with\n> core.checkStat=minimal, as the coreStat setting now affects racy checks as\n> well.\n> \n> Finally, do not check ctime if ctime.sec is 0 (as recorded by JGit).\n\nGreat analysis, and nice patch. I would like to offer one suggestion in addition:\n\n> diff --git a/read-cache.c b/read-cache.c\n> index 87204a5..3a4e6cd 100644\n> --- a/read-cache.c\n> +++ b/read-cache.c\n> @@ -99,23 +99,50 @@ void fill_stat_data(struct stat_data *sd, struct stat *st)\n>  \tsd->sd_size = st->st_size;\n>  }\n>  \n> +/*\n> + * Compares two file times. Returns 0 if equal, <0 if t1 < t2, >0 if t1 > t2.\n> + * Auto-detects precision based on trailing 0 digits. Compares seconds only if\n> + * core.checkStat=minimal.\n> + */\n> +static inline int cmp_filetime(uint32_t t1_sec, uint32_t t1_nsec,\n> +\t\t\t       uint32_t t2_sec, uint32_t t2_nsec) {\n> +#ifdef USE_NSEC\n> +\t/*\n> +\t * Compare seconds and return result if different, or checkStat=mimimal,\n> +\t * or one of the time stamps has second precision only (nsec == 0).\n> +\t */\n> +\tint diff = t1_sec - t2_sec;\n> +\tif (diff || !check_stat || !t1_nsec || !t2_nsec)\n> +\t\treturn diff;\n> +\n> +\t/*\n> +\t * Check if one of the time stamps has millisecond precision only (i.e.\n> +\t * the trailing 6 digits are 0). First check the trailing 6 bits so that\n> +\t * we only do (slower) modulo division if necessary.\n> +\t */\n> +\tif ((!(t1_nsec & 0x3f) && !(t1_nsec % 1000000)) ||\n> +\t    (!(t2_nsec & 0x3f) && !(t2_nsec % 1000000)))\n> +\t\t/* Compare milliseconds. */\n> +\t\treturn (t1_nsec - t2_nsec) / 1000000;\n> +\n> +\t/* Compare nanoseconds */\n> +\treturn t1_nsec - t2_nsec;\n> +#else\n> +\treturn t1_sec - t2_sec;\n> +#endif\n> +}\n\nAs this affects only setups where the same repository is accessed via clients with different precision, would it make sense to hide this behind a config option? I.e. something like\n\nstatic int cmp_filetime_precise(uint32_t t1_sec, uint32_t t1_nsec,\n\t\t\t        uint32_t t2_sec, uint32_t t2_nsec)\n{\n#ifdef USE_NSEC\n\treturn t1_sec != t2_sec ? t1_sec - t2_sec : t1_nsec - t2_nsec;\n#else\n\treturn t1_sec - t2_sec;\n#endif\n}\n\nstatic int cmp_filetime_mixed(uint32_t t1_sec, uint32_t t1_nsec,\n\t\t\t      uint32_t t2_sec, uint32_t t2_nsec)\n{\n#ifdef USE_NSEC\n\t... detect lower precision and compare with lower precision only...\n#else\n\treturn t1_sec - t2_sec;\n#endif\n}\n\nstatic (int *)cmp_filetime(uint32_t t1_sec, uint32_t t1_nsec,\n\t\t\t   uint32_t t2_sec, uint32_t t2_nsec)\n\t= cmp_filetime_precise;\n\n... modify cmp_filetime_precise if core.mixedTimeSpec = true...\n\nOtherwise there would be that little loop-hole where (nsec % 1000) == 0 *by chance* and we assume the timestamps to be identical even if they are not.\n\nCiao,\nDscho\n"},{"id":"270821","messageId":"xmqqbncme95a.fsf@gitster.mtv.corp.google.com","threadId":"40432","inReplyTo":"5605D88A.20104@gmail.com","subject":"Re: broken racy detection and performance issues with nanosecond file times","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-09-28T17:38:57Z","receivedAt":"2015-09-28T17:38:57Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Karsten Blees <karsten.blees@gmail.com> writes:\n\n> Problem 1: Failure to detect racy files (without USE_NSEC)\n> ==========================================================\n>\n> Git may not detect racy changes when 'update-index' runs in parallel\n> to work tree updates.\n>\n> Consider this (where timestamps are t<seconds>.<nanoseconds>):\n>\n>  t0.0$ echo \"foo\" > file1\n>  t0.1$ git update-index file1 &  # runs in background\n\nI just wonder after looking at the ampersand here ...\n\n> Please let me know what you think of this...maybe I've completely\n> screwed up and can no longer see the forest for all the trees.\n\n... if your task would become much simpler if you declare \"once you\ngive Git the control, do not muck with the repository until you get\nthe control back\".\n"},{"id":"270828","messageId":"xmqqtwqecssw.fsf@gitster.mtv.corp.google.com","threadId":"40432","inReplyTo":"5605D88A.20104@gmail.com","subject":"Re: broken racy detection and performance issues with nanosecond file times","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-09-28T18:17:19Z","receivedAt":"2015-09-28T18:17:19Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Karsten Blees <karsten.blees@gmail.com> writes:\n\n> Ideas for potential solutions:\n> ==============================\n>\n> Performance issues:\n> -------------------\n>\n> 1. Compare file times in minimum supported precision\n>    When comparing file times, use the minimum precision supported by\n>    both the writing and reading git implementations.\n> 1a. Simplest variant: Don't compare nanoseconds if the field in the\n>    cached index entry is 0. JGit already does this [5], but at the\n>    same time it is very unfriendly to USE_NSEC-enabled git by storing\n>    only milliseconds in the nanosecond field. This \"simple\" solution\n>    implies that git implementations that cannot provide full\n>    nanosecond precision must leave the nanosecond field empty.\n> 1b. More involved: Store the precision in the index entry.\n>    We only need 30 bits to encode nanoseconds, so the high 2 bits of\n>    the nanosecond field could be used as follows:\n>    00: second precision (i.e. ignore, for backward compatibility)\n>    01: millisecond precision\n>    10: microsecond precision\n>    11: nanosecond precision\n>    When reading the index, USE-NSEC-enabled git implementations would\n>    do dirty checks with the minimum precision supported by themselves\n>    and the creator of the index entry.\n\nYeah, my gut feeling is that we should make sure that at least 1a is\ndone by all implementations.\n\nI agree that 1b. is a bit more involved in that all binary that was\nbuilt with USE_NSEC that is not aware of these 2-bits need to be\neradicated for a new version to be deployed --- the transition for\nusers who use multiple implementations will be a pain (those that\nuse just one implementation of Git can just say \"rm -f .git/index &&\ngit reset --hard\" or something after updating to the new version of\nGit).\n\n> 2. Don't use ctime in dirty checks if ctime.sec == 0.\n\nOK.  That is slightly less drastic than !trust_ctime, I guess.\n\n> Racy detection:\n> ---------------\n>\n> 3. Minimal racy solution\n>    * Do all racy checks with second-precision only.\n>    * When committing an index.lock file, reset mtime to the time\n>      before git started reading the old index (i.e. time(null) when\n>      calling read_cache()).\n>\n>    I believe this should fix all three racy problems described above,\n>    although restraining ourselves to second-precision somewhat\n>    thwarts the ability to track nanoseconds in the first place.\n>    \n>    The problem with this solution is that files changed by git itself\n>    will appear racy to the next git process, thus increasing the\n>    performance penalty after e.g. a large checkout. Although I think\n>    that re-reading the file after the file's mtime is the only way to\n>    be really sure it hasn't been changed.\n\n... the last of which is what is done anyway, so I think the above,\nespecally the second bullet-point, is all sensible.\n"},{"id":"270904","messageId":"560A66A9.2010606@gmail.com","threadId":"40432","inReplyTo":"763be6c1331ac57cf7dee3636d82f994@dscho.org","subject":"Re: [PATCH/RFC] read-cache: fix file time comparisons with different precisions","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2015-09-29T10:23:37Z","receivedAt":"2015-09-29T10:23:37Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 28.09.2015 um 14:52 schrieb Johannes Schindelin:\n> Otherwise there would be that little loop-hole where (nsec % 1000) == 0 *by chance* and we assume the timestamps to be identical even if they are not.\n\nYeah, but in this case the file would be racy, as racy-checks use\nthe same comparison now.\n\nIMO change detection is so fundamental that it should Just Work,\nwithout having a plethora of config options that we need to explain\nto end users.\n\nIf that means that once in a million cases we need an extra content\ncheck to revalidate such falsely racy entries, that's fine with me.\n\nCheers,\nKarsten\n"},{"id":"270905","messageId":"560A75D4.9000206@gmail.com","threadId":"40432","inReplyTo":"xmqqbncme95a.fsf@gitster.mtv.corp.google.com","subject":"Re: broken racy detection and performance issues with nanosecond file times","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2015-09-29T11:28:20Z","receivedAt":"2015-09-29T11:28:20Z","isPatch":false,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 28.09.2015 um 19:38 schrieb Junio C Hamano:\n> Karsten Blees <karsten.blees@gmail.com> writes:\n> \n>> Problem 1: Failure to detect racy files (without USE_NSEC)\n>> ==========================================================\n>>\n>> Git may not detect racy changes when 'update-index' runs in parallel\n>> to work tree updates.\n>>\n>> Consider this (where timestamps are t<seconds>.<nanoseconds>):\n>>\n>>  t0.0$ echo \"foo\" > file1\n>>  t0.1$ git update-index file1 &  # runs in background\n> \n> I just wonder after looking at the ampersand here ...\n> \n>> Please let me know what you think of this...maybe I've completely\n>> screwed up and can no longer see the forest for all the trees.\n> \n> ... if your task would become much simpler if you declare \"once you\n> give Git the control, do not muck with the repository until you get\n> the control back\".\n> \n\nThis is just to illustrate the problem. GUI-based applications will\noften do things in the background that you cannot control. E.g. gitk,\ngit gui, Eclipse or TortoiseGit don't tell you when and how long you\nshouldn't touch the working copy. At the same time, IntelliJ IDEA and\nmost office suits have the auto-save feature turned on by default,\nand you cannot tell them when *not* to auto-save.\n\nIt may still be quite unlikely that this happens (you need two\nchanges within a second, without changing the file size), but *if*\nit happens, the user may not even notice. And as git trusts the\nfalse stat data blindly, the problem won't go away automatically.\nYou can mark all entries racy by setting index mtime to some value\nfar in the past, but this implies that you noticed that something\nwas wrong...\n"},{"id":"270906","messageId":"acb5b10221675dd6cc6b9f3846cbe8c4@dscho.org","threadId":"40432","inReplyTo":"560A66A9.2010606@gmail.com","subject":"Re: [PATCH/RFC] read-cache: fix file time comparisons with different precisions","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2015-09-29T13:42:39Z","receivedAt":"2015-09-29T13:42:39Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Karsten,\n\nOn 2015-09-29 12:23, Karsten Blees wrote:\n> Am 28.09.2015 um 14:52 schrieb Johannes Schindelin:\n>> Otherwise there would be that little loop-hole where (nsec % 1000) == 0 *by chance* and we assume the timestamps to be identical even if they are not.\n> \n> Yeah, but in this case the file would be racy, as racy-checks use\n> the same comparison now.\n\nTrue.\n\n> IMO change detection is so fundamental that it should Just Work,\n> without having a plethora of config options that we need to explain\n> to end users.\n> \n> If that means that once in a million cases we need an extra content\n> check to revalidate such falsely racy entries, that's fine with me.\n\nYou have a good point there. I retract my objections.\n\nThanks,\nDscho\n"}]}