git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v2 4/5] split-index: don't compare stat data of entries already marked for split index

From
SZEDER Gábor <szeder.dev@gmail.com>
Date
Sep 27, 2018, 12:44 UTC
Message-ID
<20180927124434.30835-5-szeder.dev@gmail.com>
In-Reply-To
<20180927124434.30835-1-szeder.dev@gmail.com>

When unpack_trees() constructs a new index, it copies cache entries from the original index [1]. prepare_to_write_split_index() has to deal with this, and it has a dedicated code path for copied entries that are present in the shared index, where it compares the cached data in the corresponding copied and original entries. If the cached data matches, then they are considered the same; if it differs, then the copied entry will be marked for inclusion as a replacement entry in the just about to be written split index by setting the CE_UPDATE_IN_BASE flag.

However, a cache entry already has its CE_UPDATE_IN_BASE flag set upon reading the split index, if the entry already has a replacement entry there, or upon refreshing the cached stat data, if the corresponding file was modified. The state of this flag is then preserved when unpack_trees() copies a cache entry from the shared index.

So modify prepare_to_write_split_index() to check the copied cache entries' CE_UPDATE_IN_BASE flag first, and skip the thorough comparison of cached data if the flag is already set.

Note that comparing the cached data in copied and original entries in the shared index might actually be entirely unnecessary. In theory all code paths refreshing the cached stat data of an entry in the shared index should set the CE_UPDATE_IN_BASE flag in that entry, and unpack_trees() should preserve this flag when copying cache entries. This means that the cached data is only ever changed if the CE_UPDATE_IN_BASE flag is set as well. Our test suite seems to confirm this: instrumenting the conditions in question and running the test suite repeatedly with 'GIT_TEST_SPLIT_INDEX=yes' showed that the cached data in a copied entry differs from the data in the shared entry only if its CE_UPDATE_IN_BASE flag is indeed set.

In practice, however, our test suite doesn't have 100% coverage, GIT_TEST_SPLIT_INDEX is inherently random, and I certainly can't claim to possess complete understanding of what goes on in unpack_trees()... Therefore I kept the comparison of the cached data when CE_UPDATE_IN_BASE is not set, just in case that an unnoticed or future code path were to accidentally miss setting this flag upon refreshing the cached stat data or unpack_trees() were to drop this flag while copying a cache entry.

[1] Note that when unpack_trees() constructs the new index and decides
    that a cache entry should now refer to different content than what
    was recorded in the original index (e.g. 'git read-tree -m
    HEAD^'), then that can't really be considered a copy of the
    original, but rather the creation of a new entry.  Notably and
    pertinent to the split index feature, such a new entry doesn't
    have a reference to the original's shared index entry anymore,
    i.e. its 'index' field is set to 0.  Consequently, such an entry
    is treated by prepare_to_write_split_index() as an entry not
    present in the shared index and it will be added to the new split
    index, while the original entry will be marked as deleted, and
    neither the above discussion nor the changes in this patch apply
    to them.
Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
 split-index.c | 79 ++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 62 insertions(+), 17 deletions(-)
diff --git a/split-index.c b/split-index.c
index 548272ec33..7d8799f6b7 100644
--- a/split-index.c
+++ b/split-index.c
@@ -204,19 +204,34 @@ void prepare_to_write_split_index(struct index_state *istate)
 		 * that are not marked with either CE_MATCHED or
 		 * CE_UPDATE_IN_BASE. If istate->cache[i] is a
 		 * duplicate, deduplicate it.
 		 */
 		for (i = 0; i < istate->cache_nr; i++) {
 			struct cache_entry *base;
-			/* namelen is checked separately */
-			const unsigned int ondisk_flags =
-				CE_STAGEMASK | CE_VALID | CE_EXTENDED_FLAGS;
-			unsigned int ce_flags, base_flags, ret;
 			ce = istate->cache[i];
-			if (!ce->index)
+			if (!ce->index) {
+				/*
+				 * During simple update index operations this
+				 * is a cache entry that is not present in
+				 * the shared index.  It will be added to the
+				 * split index.
+				 *
+				 * However, it might also represent a file
+				 * that already has a cache entry in the
+				 * shared index, but a new index has just
+				 * been constructed by unpack_trees(), and
+				 * this entry now refers to different content
+				 * than what was recorded in the original
+				 * index, e.g. during 'read-tree -m HEAD^' or
+				 * 'checkout HEAD^'.  In this case the
+				 * original entry in the shared index will be
+				 * marked as deleted, and this entry will be
+				 * added to the split index.
+				 */
 				continue;
+			}
 			if (ce->index > si->base->cache_nr) {
 				ce->index = 0;
 				continue;
 			}
 			ce->ce_flags |= CE_MATCHED; /* or "shared" */
 			base = si->base->cache[ce->index - 1];
@@ -224,24 +239,54 @@ void prepare_to_write_split_index(struct index_state *istate)
 				continue;
 			if (ce->ce_namelen != base->ce_namelen ||
 			    strcmp(ce->name, base->name)) {
 				ce->index = 0;
 				continue;
 			}
-			ce_flags = ce->ce_flags;
-			base_flags = base->ce_flags;
-			/* only on-disk flags matter */
-			ce->ce_flags   &= ondisk_flags;
-			base->ce_flags &= ondisk_flags;
-			ret = memcmp(&ce->ce_stat_data, &base->ce_stat_data,
-				     offsetof(struct cache_entry, name) -
-				     offsetof(struct cache_entry, ce_stat_data));
-			ce->ce_flags = ce_flags;
-			base->ce_flags = base_flags;
-			if (ret)
-				ce->ce_flags |= CE_UPDATE_IN_BASE;
+			/*
+			 * This is the copy of a cache entry that is present
+			 * in the shared index, created by unpack_trees()
+			 * while it constructed a new index.
+			 */
+			if (ce->ce_flags & CE_UPDATE_IN_BASE) {
+				/*
+				 * Already marked for inclusion in the split
+				 * index, either because the corresponding
+				 * file was modified and the cached stat data
+				 * was refreshed, or because the original
+				 * entry already had a replacement entry in
+				 * the split index.
+				 * Nothing to do.
+				 */
+			} else {
+				/*
+				 * Thoroughly compare the cached data to see
+				 * whether it should be marked for inclusion
+				 * in the split index.
+				 *
+				 * This comparison might be unnecessary, as
+				 * code paths modifying the cached data do
+				 * set CE_UPDATE_IN_BASE as well.
+				 */
+				const unsigned int ondisk_flags =
+					CE_STAGEMASK | CE_VALID |
+					CE_EXTENDED_FLAGS;
+				unsigned int ce_flags, base_flags, ret;
+				ce_flags = ce->ce_flags;
+				base_flags = base->ce_flags;
+				/* only on-disk flags matter */
+				ce->ce_flags   &= ondisk_flags;
+				base->ce_flags &= ondisk_flags;
+				ret = memcmp(&ce->ce_stat_data, &base->ce_stat_data,
+					     offsetof(struct cache_entry, name) -
+					     offsetof(struct cache_entry, ce_stat_data));
+				ce->ce_flags = ce_flags;
+				base->ce_flags = base_flags;
+				if (ret)
+					ce->ce_flags |= CE_UPDATE_IN_BASE;
+			}
 			discard_cache_entry(base);
 			si->base->cache[ce->index - 1] = ce;
 		}
 		for (i = 0; i < si->base->cache_nr; i++) {
 			ce = si->base->cache[i];
 			if ((ce->ce_flags & CE_REMOVE) ||

-- 
2.19.0.361.gafc87ffe72
Previous: SZEDER GáborNext: SZEDER Gábor
Message 8 of 42 in “Fix the racy split index problem”
  1. 0/5 Fix the racy split index problemSZEDER Gábor, Sep 27, 2018
  2. 1/5 split-index: add tests to demonstrate the racy split index problemSZEDER Gábor, Sep 27, 2018
  3. SZEDER GáborSep 28, 2018
  4. SZEDER GáborSep 28, 2018
  5. Junio C HamanoSep 28, 2018
  6. 2/5 t1700-split-index: date back files to avoid racy situationsSZEDER Gábor, Sep 27, 2018
  7. 3/5 split-index: count the number of deleted entriesSZEDER Gábor, Sep 27, 2018
  8. 4/5 split-index: don't compare stat data of entries already marked for split indexSZEDER Gábor, Sep 27, 2018
  9. SZEDER GáborSep 27, 2018
  10. 5/5 split-index: smudge and add racily clean cache entries to split indexSZEDER Gábor, Sep 27, 2018
  11. Ævar Arnfjörð BjarmasonSep 27, 2018
  12. SZEDER GáborSep 27, 2018
  13. Ævar Arnfjörð BjarmasonSep 27, 2018
  14. Ævar Arnfjörð BjarmasonSep 28, 2018
  15. SZEDER GáborSep 28, 2018
  16. Ævar Arnfjörð BjarmasonOct 8, 2018
  17. SZEDER GáborOct 8, 2018
  18. 0/6 Fix the racy split index problemSZEDER Gábor, Sep 28, 2018
  19. 1/6 t1700-split-index: document why FSMONITOR is disabled in this test scriptSZEDER Gábor, Sep 28, 2018
  20. 2/6 split-index: add tests to demonstrate the racy split index problemSZEDER Gábor, Sep 28, 2018
  21. 3/6 t1700-split-index: date back files to avoid racy situationsSZEDER Gábor, Sep 28, 2018
  22. 4/6 split-index: count the number of deleted entriesSZEDER Gábor, Sep 28, 2018
  23. 5/6 split-index: don't compare stat data of entries already marked for split indexSZEDER Gábor, Sep 28, 2018
  24. Duy NguyenSep 29, 2018
  25. SZEDER GáborSep 29, 2018
  26. SZEDER GáborSep 29, 2018
  27. 6/6 split-index: smudge and add racily clean cache entries to split indexSZEDER Gábor, Sep 28, 2018
  28. Duy NguyenSep 29, 2018
  29. SZEDER GáborSep 29, 2018
  30. SZEDER GáborSep 30, 2018
  31. Junio C HamanoOct 5, 2018
  32. 0/6 Fix the racy split index problemSZEDER Gábor, Oct 11, 2018
  33. 1/6 t1700-split-index: document why FSMONITOR is disabled in this test scriptSZEDER Gábor, Oct 11, 2018
  34. 3/6 t1700-split-index: date back files to avoid racy situationsSZEDER Gábor, Oct 11, 2018
  35. 2/6 split-index: add tests to demonstrate the racy split index problemSZEDER Gábor, Oct 11, 2018
  36. 4/6 split-index: count the number of deleted entriesSZEDER Gábor, Oct 11, 2018
  37. 5/6 split-index: don't compare cached data of entries already marked for split indexSZEDER Gábor, Oct 11, 2018
  38. 6/6 split-index: smudge and add racily clean cache entries to split indexSZEDER Gábor, Oct 11, 2018
  39. 7/6 split-index: BUG() when cache entry refers to non-existing shared entrySZEDER Gábor, Oct 11, 2018
  40. Ævar Arnfjörð BjarmasonOct 11, 2018
  41. SZEDER GáborOct 11, 2018
  42. Junio C HamanoOct 12, 2018

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.