| Message ID | 20180906210227.54368-3-benpeart@microsoft.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | read-cache: speed up index load through parallelization | expand |
Ben Peart <benpeart@microsoft.com> writes: > The extension consists of: > > - 32-bit offset to the end of the index entries > > - 160-bit SHA-1 over the extension types and their sizes (but not > their contents). E.g. if we have "TREE" extension that is N-bytes > long, "REUC" extension that is M-bytes long, followed by "EOIE", > then the hash would be: > > SHA-1("TREE" + <binary representation of N> + > "REUC" + <binary representation of M>) I didn't look at the documentation patch in the larger context, but please make sure that it is clear to the readers that these fixed width integers "binary representations" use network byte order. I briefly wondered if the above should include + "EOIE" + <binary representation of (32+160)/8 = 24> as it is pretty much common file format design to include the header part of the checksum record (with checksum values padded out with NUL bytes) when you define a record to hold the checksum of the entire file. Since this does not protect the contents of each section from bit-flipping, adding the data for EOIE itself in the sum does not give us much (iow, what I am adding above is a constant that does not contribute any entropy). How big is a typical TREE extension in _your_ work repository housing Windows sources? I am guessing that replacing SHA-1 with something faster (as this is not about security but is about disk corruption) and instead hash also the contents of these sections would NOT help all that much in the performance department, as having to page them in to read through would already consume non-trivial amount of time, and that is why you are not hashing the contents. > + /* > + * CACHE_EXT_ENDOFINDEXENTRIES must be written as the last entry before the SHA1 s/SHA1/trailing checksum/ or something so that we can withstand NewHash world order? > + * so that it can be found and processed before all the index entries are > + * read. > + */ > + if (!strip_extensions && offset && !git_env_bool("GIT_TEST_DISABLE_EOIE", 0)) { > + struct strbuf sb = STRBUF_INIT; > + > + write_eoie_extension(&sb, &eoie_c, offset); > + err = write_index_ext_header(&c, NULL, newfd, CACHE_EXT_ENDOFINDEXENTRIES, sb.len) < 0 > || ce_write(&c, newfd, sb.buf, sb.len) < 0; > strbuf_release(&sb); > if (err) OK. > +#define EOIE_SIZE 24 /* <4-byte offset> + <20-byte hash> */ > +#define EOIE_SIZE_WITH_HEADER (4 + 4 + EOIE_SIZE) /* <4-byte signature> + <4-byte length> + EOIE_SIZE */ > + > +#ifndef NO_PTHREADS > +static unsigned long read_eoie_extension(void *mmap, size_t mmap_size) > +{ > + /* > + * The end of index entries (EOIE) extension is guaranteed to be last > + * so that it can be found by scanning backwards from the EOF. > + * > + * "EOIE" > + * <4-byte length> > + * <4-byte offset> > + * <20-byte hash> > + */ > + const char *index, *eoie = (const char *)mmap + mmap_size - GIT_SHA1_RAWSZ - EOIE_SIZE_WITH_HEADER; > + uint32_t extsize; > + unsigned long offset, src_offset; > + unsigned char hash[GIT_MAX_RAWSZ]; > + git_hash_ctx c; > + > + /* validate the extension signature */ > + index = eoie; > + if (CACHE_EXT(index) != CACHE_EXT_ENDOFINDEXENTRIES) > + return 0; > + index += sizeof(uint32_t); > + > + /* validate the extension size */ > + extsize = get_be32(index); > + if (extsize != EOIE_SIZE) > + return 0; > + index += sizeof(uint32_t); Do we know we have at least 8-byte to consume to perform the above two checks, or is that something we need to verify at the beginning of this function? Better yet, as we know that a correct EOIE with its own header is 28-byte long, we probably should abort if mmap_size is smaller than that. > + /* > + * Validate the offset we're going to look for the first extension > + * signature is after the index header and before the eoie extension. > + */ > + offset = get_be32(index); > + if ((const char *)mmap + offset < (const char *)mmap + sizeof(struct cache_header)) > + return 0; Claims that the end is before the beginning, which we reject as bogus. Good. > + if ((const char *)mmap + offset >= eoie) > + return 0; Claims that the end is beyond the EOIE marker we should have placed after it, which we reject as bogus. Good. > + index += sizeof(uint32_t); > + > + /* > + * The hash is computed over extension types and their sizes (but not > + * their contents). E.g. if we have "TREE" extension that is N-bytes > + * long, "REUC" extension that is M-bytes long, followed by "EOIE", > + * then the hash would be: > + * > + * SHA-1("TREE" + <binary representation of N> + > + * "REUC" + <binary representation of M>) > + */ > + src_offset = offset; > + the_hash_algo->init_fn(&c); > + while (src_offset < mmap_size - the_hash_algo->rawsz - EOIE_SIZE_WITH_HEADER) { > + /* After an array of active_nr index entries, (Style nit). > + * there can be arbitrary number of extended > + * sections, each of which is prefixed with > + * extension name (4-byte) and section length > + * in 4-byte network byte order. > + */ > + uint32_t extsize; > + memcpy(&extsize, (char *)mmap + src_offset + 4, 4); > + extsize = ntohl(extsize); Earlier we were using get_be32() but now we use memcpy with ntohl()? How are we choosing which one to use? I think you meant to cast mmap to (const char *) here. It may make it easier to write and read if we started this function like so: static unsigned long read_eoie_extension(void *mmap_, size_t mmap_size) { const char *mmap = mmap_; then we do not have to keep casting mmap and cast to a wrong type by mistake. > + > + /* verify the extension size isn't so large it will wrap around */ > + if (src_offset + 8 + extsize < src_offset) > + return 0; Good. > + the_hash_algo->update_fn(&c, (const char *)mmap + src_offset, 8); > + > + src_offset += 8; > + src_offset += extsize; > + } > + the_hash_algo->final_fn(hash, &c); > + if (hashcmp(hash, (unsigned char *)index)) > + return 0; > + > + /* Validate that the extension offsets returned us back to the eoie extension. */ > + if (src_offset != mmap_size - the_hash_algo->rawsz - EOIE_SIZE_WITH_HEADER) > + return 0; Very good. > + return offset; > +} > +#endif Overall it looks like it is carefully done. Thanks.
On 9/7/2018 1:55 PM, Junio C Hamano wrote: > Ben Peart <benpeart@microsoft.com> writes: > >> The extension consists of: >> >> - 32-bit offset to the end of the index entries >> >> - 160-bit SHA-1 over the extension types and their sizes (but not >> their contents). E.g. if we have "TREE" extension that is N-bytes >> long, "REUC" extension that is M-bytes long, followed by "EOIE", >> then the hash would be: >> >> SHA-1("TREE" + <binary representation of N> + >> "REUC" + <binary representation of M>) > > I didn't look at the documentation patch in the larger context, but > please make sure that it is clear to the readers that these fixed > width integers "binary representations" use network byte order. > At the top of the documentation it says "All binary numbers are in network byte order" and that is not repeated for any of the other sections that are documenting the file format. > I briefly wondered if the above should include > > + "EOIE" + <binary representation of (32+160)/8 = 24> > > as it is pretty much common file format design to include the header > part of the checksum record (with checksum values padded out with NUL > bytes) when you define a record to hold the checksum of the entire > file. Since this does not protect the contents of each section from > bit-flipping, adding the data for EOIE itself in the sum does not > give us much (iow, what I am adding above is a constant that does > not contribute any entropy). > > How big is a typical TREE extension in _your_ work repository > housing Windows sources? I am guessing that replacing SHA-1 with > something faster (as this is not about security but is about disk > corruption) and instead hash also the contents of these sections > would NOT help all that much in the performance department, as > having to page them in to read through would already consume > non-trivial amount of time, and that is why you are not hashing the > contents. > The purpose of the SHA isn't to detect disk corruption (we already have a SHA for the entire index that can serve that purpose) but to help ensure that this was actually a valid EOIE extension and not a lucky random set of bytes. I had used leading and trailing signature bytes along with the length and version bytes to validate it was an actual EOIE extension but you suggested [1] that I use a SHA of the 4 byte extension type + 4 byte extension length instead so I rewrote it that way. [1] https://public-inbox.org/git/xmqq1sl017dw.fsf@gitster.mtv.corp.google.com/ >> + /* >> + * CACHE_EXT_ENDOFINDEXENTRIES must be written as the last entry before the SHA1 > > s/SHA1/trailing checksum/ or something so that we can withstand > NewHash world order? > I thought about this but in the document elsewhere it refers to it as "160-bit SHA-1 over the content of the index file before this checksum." and there are at least a dozen other references to "SHA-1" so I figured we can fix them all at the same time when we have a new/better name. :-) >> + * so that it can be found and processed before all the index entries are >> + * read. >> + */ >> + if (!strip_extensions && offset && !git_env_bool("GIT_TEST_DISABLE_EOIE", 0)) { >> + struct strbuf sb = STRBUF_INIT; >> + >> + write_eoie_extension(&sb, &eoie_c, offset); >> + err = write_index_ext_header(&c, NULL, newfd, CACHE_EXT_ENDOFINDEXENTRIES, sb.len) < 0 >> || ce_write(&c, newfd, sb.buf, sb.len) < 0; >> strbuf_release(&sb); >> if (err) > > OK. > >> +#define EOIE_SIZE 24 /* <4-byte offset> + <20-byte hash> */ >> +#define EOIE_SIZE_WITH_HEADER (4 + 4 + EOIE_SIZE) /* <4-byte signature> + <4-byte length> + EOIE_SIZE */ >> + >> +#ifndef NO_PTHREADS >> +static unsigned long read_eoie_extension(void *mmap, size_t mmap_size) >> +{ >> + /* >> + * The end of index entries (EOIE) extension is guaranteed to be last >> + * so that it can be found by scanning backwards from the EOF. >> + * >> + * "EOIE" >> + * <4-byte length> >> + * <4-byte offset> >> + * <20-byte hash> >> + */ >> + const char *index, *eoie = (const char *)mmap + mmap_size - GIT_SHA1_RAWSZ - EOIE_SIZE_WITH_HEADER; >> + uint32_t extsize; >> + unsigned long offset, src_offset; >> + unsigned char hash[GIT_MAX_RAWSZ]; >> + git_hash_ctx c; >> + >> + /* validate the extension signature */ >> + index = eoie; >> + if (CACHE_EXT(index) != CACHE_EXT_ENDOFINDEXENTRIES) >> + return 0; >> + index += sizeof(uint32_t); >> + >> + /* validate the extension size */ >> + extsize = get_be32(index); >> + if (extsize != EOIE_SIZE) >> + return 0; >> + index += sizeof(uint32_t); > > Do we know we have at least 8-byte to consume to perform the above > two checks, or is that something we need to verify at the beginning > of this function? Better yet, as we know that a correct EOIE with > its own header is 28-byte long, we probably should abort if > mmap_size is smaller than that. > I'll add that additional test. >> + /* >> + * Validate the offset we're going to look for the first extension >> + * signature is after the index header and before the eoie extension. >> + */ >> + offset = get_be32(index); >> + if ((const char *)mmap + offset < (const char *)mmap + sizeof(struct cache_header)) >> + return 0; > > Claims that the end is before the beginning, which we reject as bogus. Good. > >> + if ((const char *)mmap + offset >= eoie) >> + return 0; > > Claims that the end is beyond the EOIE marker we should have placed > after it, which we reject as bogus. Good. > >> + index += sizeof(uint32_t); >> + >> + /* >> + * The hash is computed over extension types and their sizes (but not >> + * their contents). E.g. if we have "TREE" extension that is N-bytes >> + * long, "REUC" extension that is M-bytes long, followed by "EOIE", >> + * then the hash would be: >> + * >> + * SHA-1("TREE" + <binary representation of N> + >> + * "REUC" + <binary representation of M>) >> + */ >> + src_offset = offset; >> + the_hash_algo->init_fn(&c); >> + while (src_offset < mmap_size - the_hash_algo->rawsz - EOIE_SIZE_WITH_HEADER) { >> + /* After an array of active_nr index entries, > (Style nit). >> + * there can be arbitrary number of extended >> + * sections, each of which is prefixed with >> + * extension name (4-byte) and section length >> + * in 4-byte network byte order. >> + */ >> + uint32_t extsize; >> + memcpy(&extsize, (char *)mmap + src_offset + 4, 4); >> + extsize = ntohl(extsize); > > Earlier we were using get_be32() but now we use memcpy with ntohl()? > How are we choosing which one to use? > I literally copy/pasted this logic from the code that actually loads the extensions then removed the call to load the extension and replaced it with the call to update the hash. I kept it the same to facilitate consistency for any future fixes or changes. > I think you meant to cast mmap to (const char *) here. It may make it > easier to write and read if we started this function like so: > > static unsigned long read_eoie_extension(void *mmap_, size_t mmap_size) > { > const char *mmap = mmap_; > > then we do not have to keep casting mmap and cast to a wrong type by > mistake. > Good suggestion. >> + >> + /* verify the extension size isn't so large it will wrap around */ >> + if (src_offset + 8 + extsize < src_offset) >> + return 0; > > Good. > >> + the_hash_algo->update_fn(&c, (const char *)mmap + src_offset, 8); >> + >> + src_offset += 8; >> + src_offset += extsize; >> + } >> + the_hash_algo->final_fn(hash, &c); >> + if (hashcmp(hash, (unsigned char *)index)) >> + return 0; >> + >> + /* Validate that the extension offsets returned us back to the eoie extension. */ >> + if (src_offset != mmap_size - the_hash_algo->rawsz - EOIE_SIZE_WITH_HEADER) >> + return 0; > > Very good. > >> + return offset; >> +} >> +#endif > > Overall it looks like it is carefully done. Thanks for the careful review! > Thanks. >
On Fri, 7 Sep 2018 at 22:24, Ben Peart <peartben@gmail.com> wrote: > > Ben Peart <benpeart@microsoft.com> writes: > >> - 160-bit SHA-1 over the extension types and their sizes (but not > >> their contents). E.g. if we have "TREE" extension that is N-bytes > >> long, "REUC" extension that is M-bytes long, followed by "EOIE", > >> then the hash would be: > The purpose of the SHA isn't to detect disk corruption (we already have > a SHA for the entire index that can serve that purpose) but to help > ensure that this was actually a valid EOIE extension and not a lucky > random set of bytes. [...] > >> +#define EOIE_SIZE 24 /* <4-byte offset> + <20-byte hash> */ > >> + the_hash_algo->init_fn(&c); > >> + while (src_offset < mmap_size - the_hash_algo->rawsz - EOIE_SIZE_WITH_HEADER) { [...] > >> + the_hash_algo->final_fn(hash, &c); > >> + if (hashcmp(hash, (unsigned char *)index)) > >> + return 0; > >> + > >> + /* Validate that the extension offsets returned us back to the eoie extension. */ > >> + if (src_offset != mmap_size - the_hash_algo->rawsz - EOIE_SIZE_WITH_HEADER) > >> + return 0; Besides the issue you and Junio discussed with "should we document this as being SHA-1 or NewHash" (or "the hash algo"), it seems to me that this implementation is living somewhere between using SHA-1 and "the hash algo". The hashing uses `the_hash_algo`, but the hash size is hardcoded at 20 bytes. Maybe it all works out, e.g., so that when someone (brian) merges a NewHash and runs the testsuite, this will fail consistently and in a safe way. But I wonder if it would be too hard to avoid the hardcoded 24 already now. Martin
On 9/8/2018 2:29 AM, Martin Ågren wrote: > On Fri, 7 Sep 2018 at 22:24, Ben Peart <peartben@gmail.com> wrote: >>> Ben Peart <benpeart@microsoft.com> writes: > >>>> - 160-bit SHA-1 over the extension types and their sizes (but not >>>> their contents). E.g. if we have "TREE" extension that is N-bytes >>>> long, "REUC" extension that is M-bytes long, followed by "EOIE", >>>> then the hash would be: > >> The purpose of the SHA isn't to detect disk corruption (we already have >> a SHA for the entire index that can serve that purpose) but to help >> ensure that this was actually a valid EOIE extension and not a lucky >> random set of bytes. [...] > >>>> +#define EOIE_SIZE 24 /* <4-byte offset> + <20-byte hash> */ > >>>> + the_hash_algo->init_fn(&c); >>>> + while (src_offset < mmap_size - the_hash_algo->rawsz - EOIE_SIZE_WITH_HEADER) { > [...] >>>> + the_hash_algo->final_fn(hash, &c); >>>> + if (hashcmp(hash, (unsigned char *)index)) >>>> + return 0; >>>> + >>>> + /* Validate that the extension offsets returned us back to the eoie extension. */ >>>> + if (src_offset != mmap_size - the_hash_algo->rawsz - EOIE_SIZE_WITH_HEADER) >>>> + return 0; > > Besides the issue you and Junio discussed with "should we document this > as being SHA-1 or NewHash" (or "the hash algo"), it seems to me that > this implementation is living somewhere between using SHA-1 and "the > hash algo". The hashing uses `the_hash_algo`, but the hash size is > hardcoded at 20 bytes. > > Maybe it all works out, e.g., so that when someone (brian) merges a > NewHash and runs the testsuite, this will fail consistently and in a > safe way. But I wonder if it would be too hard to avoid the hardcoded 24 > already now. > > Martin > I can certainly change this to be: #define EOIE_SIZE (4 + GIT_SHA1_RAWSZ) which should (hopefully) make it easier to find this hard coded hash length in the sea of hard coded "20" and "160" (bits) littered through the codebase.
On Sat, 8 Sep 2018 at 16:04, Ben Peart <peartben@gmail.com> wrote: > On 9/8/2018 2:29 AM, Martin Ågren wrote: > > Maybe it all works out, e.g., so that when someone (brian) merges a > > NewHash and runs the testsuite, this will fail consistently and in a > > safe way. But I wonder if it would be too hard to avoid the hardcoded 24 > > already now. > > I can certainly change this to be: > > #define EOIE_SIZE (4 + GIT_SHA1_RAWSZ) > > which should (hopefully) make it easier to find this hard coded hash > length in the sea of hard coded "20" and "160" (bits) littered through > the codebase. Yeah, that seems more grep-friendly. Martin
diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt index db3572626b..6bc2d90f7f 100644 --- a/Documentation/technical/index-format.txt +++ b/Documentation/technical/index-format.txt @@ -314,3 +314,26 @@ The remaining data of each directory block is grouped by type: - An ewah bitmap, the n-th bit indicates whether the n-th index entry is not CE_FSMONITOR_VALID. + +== End of Index Entry + + The End of Index Entry (EOIE) is used to locate the end of the variable + length index entries and the begining of the extensions. Code can take + advantage of this to quickly locate the index extensions without having + to parse through all of the index entries. + + Because it must be able to be loaded before the variable length cache + entries and other index extensions, this extension must be written last. + The signature for this extension is { 'E', 'O', 'I', 'E' }. + + The extension consists of: + + - 32-bit offset to the end of the index entries + + - 160-bit SHA-1 over the extension types and their sizes (but not + their contents). E.g. if we have "TREE" extension that is N-bytes + long, "REUC" extension that is M-bytes long, followed by "EOIE", + then the hash would be: + + SHA-1("TREE" + <binary representation of N> + + "REUC" + <binary representation of M>) diff --git a/read-cache.c b/read-cache.c index 382cc16bdc..d0d2793780 100644 --- a/read-cache.c +++ b/read-cache.c @@ -43,6 +43,7 @@ #define CACHE_EXT_LINK 0x6c696e6b /* "link" */ #define CACHE_EXT_UNTRACKED 0x554E5452 /* "UNTR" */ #define CACHE_EXT_FSMONITOR 0x46534D4E /* "FSMN" */ +#define CACHE_EXT_ENDOFINDEXENTRIES 0x454F4945 /* "EOIE" */ /* changes that can be kept in $GIT_DIR/index (basically all extensions) */ #define EXTMASK (RESOLVE_UNDO_CHANGED | CACHE_TREE_CHANGED | \ @@ -1693,6 +1694,9 @@ static int read_index_extension(struct index_state *istate, case CACHE_EXT_FSMONITOR: read_fsmonitor_extension(istate, data, sz); break; + case CACHE_EXT_ENDOFINDEXENTRIES: + /* already handled in do_read_index() */ + break; default: if (*ext < 'A' || 'Z' < *ext) return error("index uses %.4s extension, which we do not understand", @@ -1888,6 +1892,11 @@ static size_t estimate_cache_size(size_t ondisk_size, unsigned int entries) return ondisk_size + entries * per_entry; } +#ifndef NO_PTHREADS +static unsigned long read_eoie_extension(void *mmap, size_t mmap_size); +#endif +static void write_eoie_extension(struct strbuf *sb, git_hash_ctx *eoie_context, unsigned long offset); + /* remember to discard_cache() before reading a different cache! */ int do_read_index(struct index_state *istate, const char *path, int must_exist) { @@ -2197,11 +2206,15 @@ static int ce_write(git_hash_ctx *context, int fd, void *data, unsigned int len) return 0; } -static int write_index_ext_header(git_hash_ctx *context, int fd, - unsigned int ext, unsigned int sz) +static int write_index_ext_header(git_hash_ctx *context, git_hash_ctx *eoie_context, + int fd, unsigned int ext, unsigned int sz) { ext = htonl(ext); sz = htonl(sz); + if (eoie_context) { + the_hash_algo->update_fn(eoie_context, &ext, 4); + the_hash_algo->update_fn(eoie_context, &sz, 4); + } return ((ce_write(context, fd, &ext, 4) < 0) || (ce_write(context, fd, &sz, 4) < 0)) ? -1 : 0; } @@ -2444,7 +2457,7 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile, { uint64_t start = getnanotime(); int newfd = tempfile->fd; - git_hash_ctx c; + git_hash_ctx c, eoie_c; struct cache_header hdr; int i, err = 0, removed, extended, hdr_version; struct cache_entry **cache = istate->cache; @@ -2453,6 +2466,7 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile, struct ondisk_cache_entry_extended ondisk; struct strbuf previous_name_buf = STRBUF_INIT, *previous_name; int drop_cache_tree = istate->drop_cache_tree; + unsigned long offset; for (i = removed = extended = 0; i < entries; i++) { if (cache[i]->ce_flags & CE_REMOVE) @@ -2519,11 +2533,13 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile, return err; /* Write extension data here */ + offset = lseek(newfd, 0, SEEK_CUR) + write_buffer_len; + the_hash_algo->init_fn(&eoie_c); if (!strip_extensions && istate->split_index) { struct strbuf sb = STRBUF_INIT; err = write_link_extension(&sb, istate) < 0 || - write_index_ext_header(&c, newfd, CACHE_EXT_LINK, + write_index_ext_header(&c, &eoie_c, newfd, CACHE_EXT_LINK, sb.len) < 0 || ce_write(&c, newfd, sb.buf, sb.len) < 0; strbuf_release(&sb); @@ -2534,7 +2550,7 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile, struct strbuf sb = STRBUF_INIT; cache_tree_write(&sb, istate->cache_tree); - err = write_index_ext_header(&c, newfd, CACHE_EXT_TREE, sb.len) < 0 + err = write_index_ext_header(&c, &eoie_c, newfd, CACHE_EXT_TREE, sb.len) < 0 || ce_write(&c, newfd, sb.buf, sb.len) < 0; strbuf_release(&sb); if (err) @@ -2544,7 +2560,7 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile, struct strbuf sb = STRBUF_INIT; resolve_undo_write(&sb, istate->resolve_undo); - err = write_index_ext_header(&c, newfd, CACHE_EXT_RESOLVE_UNDO, + err = write_index_ext_header(&c, &eoie_c, newfd, CACHE_EXT_RESOLVE_UNDO, sb.len) < 0 || ce_write(&c, newfd, sb.buf, sb.len) < 0; strbuf_release(&sb); @@ -2555,7 +2571,7 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile, struct strbuf sb = STRBUF_INIT; write_untracked_extension(&sb, istate->untracked); - err = write_index_ext_header(&c, newfd, CACHE_EXT_UNTRACKED, + err = write_index_ext_header(&c, &eoie_c, newfd, CACHE_EXT_UNTRACKED, sb.len) < 0 || ce_write(&c, newfd, sb.buf, sb.len) < 0; strbuf_release(&sb); @@ -2566,7 +2582,23 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile, struct strbuf sb = STRBUF_INIT; write_fsmonitor_extension(&sb, istate); - err = write_index_ext_header(&c, newfd, CACHE_EXT_FSMONITOR, sb.len) < 0 + err = write_index_ext_header(&c, &eoie_c, newfd, CACHE_EXT_FSMONITOR, sb.len) < 0 + || ce_write(&c, newfd, sb.buf, sb.len) < 0; + strbuf_release(&sb); + if (err) + return -1; + } + + /* + * CACHE_EXT_ENDOFINDEXENTRIES must be written as the last entry before the SHA1 + * so that it can be found and processed before all the index entries are + * read. + */ + if (!strip_extensions && offset && !git_env_bool("GIT_TEST_DISABLE_EOIE", 0)) { + struct strbuf sb = STRBUF_INIT; + + write_eoie_extension(&sb, &eoie_c, offset); + err = write_index_ext_header(&c, NULL, newfd, CACHE_EXT_ENDOFINDEXENTRIES, sb.len) < 0 || ce_write(&c, newfd, sb.buf, sb.len) < 0; strbuf_release(&sb); if (err) @@ -2977,3 +3009,104 @@ int should_validate_cache_entries(void) return validate_index_cache_entries; } + +#define EOIE_SIZE 24 /* <4-byte offset> + <20-byte hash> */ +#define EOIE_SIZE_WITH_HEADER (4 + 4 + EOIE_SIZE) /* <4-byte signature> + <4-byte length> + EOIE_SIZE */ + +#ifndef NO_PTHREADS +static unsigned long read_eoie_extension(void *mmap, size_t mmap_size) +{ + /* + * The end of index entries (EOIE) extension is guaranteed to be last + * so that it can be found by scanning backwards from the EOF. + * + * "EOIE" + * <4-byte length> + * <4-byte offset> + * <20-byte hash> + */ + const char *index, *eoie = (const char *)mmap + mmap_size - GIT_SHA1_RAWSZ - EOIE_SIZE_WITH_HEADER; + uint32_t extsize; + unsigned long offset, src_offset; + unsigned char hash[GIT_MAX_RAWSZ]; + git_hash_ctx c; + + /* validate the extension signature */ + index = eoie; + if (CACHE_EXT(index) != CACHE_EXT_ENDOFINDEXENTRIES) + return 0; + index += sizeof(uint32_t); + + /* validate the extension size */ + extsize = get_be32(index); + if (extsize != EOIE_SIZE) + return 0; + index += sizeof(uint32_t); + + /* + * Validate the offset we're going to look for the first extension + * signature is after the index header and before the eoie extension. + */ + offset = get_be32(index); + if ((const char *)mmap + offset < (const char *)mmap + sizeof(struct cache_header)) + return 0; + if ((const char *)mmap + offset >= eoie) + return 0; + index += sizeof(uint32_t); + + /* + * The hash is computed over extension types and their sizes (but not + * their contents). E.g. if we have "TREE" extension that is N-bytes + * long, "REUC" extension that is M-bytes long, followed by "EOIE", + * then the hash would be: + * + * SHA-1("TREE" + <binary representation of N> + + * "REUC" + <binary representation of M>) + */ + src_offset = offset; + the_hash_algo->init_fn(&c); + while (src_offset < mmap_size - the_hash_algo->rawsz - EOIE_SIZE_WITH_HEADER) { + /* After an array of active_nr index entries, + * there can be arbitrary number of extended + * sections, each of which is prefixed with + * extension name (4-byte) and section length + * in 4-byte network byte order. + */ + uint32_t extsize; + memcpy(&extsize, (char *)mmap + src_offset + 4, 4); + extsize = ntohl(extsize); + + /* verify the extension size isn't so large it will wrap around */ + if (src_offset + 8 + extsize < src_offset) + return 0; + + the_hash_algo->update_fn(&c, (const char *)mmap + src_offset, 8); + + src_offset += 8; + src_offset += extsize; + } + the_hash_algo->final_fn(hash, &c); + if (hashcmp(hash, (unsigned char *)index)) + return 0; + + /* Validate that the extension offsets returned us back to the eoie extension. */ + if (src_offset != mmap_size - the_hash_algo->rawsz - EOIE_SIZE_WITH_HEADER) + return 0; + + return offset; +} +#endif + +static void write_eoie_extension(struct strbuf *sb, git_hash_ctx *eoie_context, unsigned long offset) +{ + uint32_t buffer; + unsigned char hash[GIT_MAX_RAWSZ]; + + /* offset */ + put_be32(&buffer, offset); + strbuf_add(sb, &buffer, sizeof(uint32_t)); + + /* hash */ + the_hash_algo->final_fn(hash, eoie_context); + strbuf_add(sb, hash, the_hash_algo->rawsz); +} diff --git a/t/README b/t/README index 9028b47d92..d8754dd23a 100644 --- a/t/README +++ b/t/README @@ -319,6 +319,11 @@ GIT_TEST_OE_DELTA_SIZE=<n> exercises the uncomon pack-objects code path where deltas larger than this limit require extra memory allocation for bookkeeping. +GIT_TEST_DISABLE_EOIE=<boolean> disables writing the EOIE extension. +This is used to allow tests 1, 4-9 in t1700-split-index.sh to succeed +as they currently hard code SHA values for the index which are no longer +valid due to the addition of the EOIE extension. + Naming Tests ------------ diff --git a/t/t1700-split-index.sh b/t/t1700-split-index.sh index 39133bcbc8..f613dd72e3 100755 --- a/t/t1700-split-index.sh +++ b/t/t1700-split-index.sh @@ -7,6 +7,7 @@ test_description='split index mode tests' # We need total control of index splitting here sane_unset GIT_TEST_SPLIT_INDEX sane_unset GIT_FSMONITOR_TEST +export GIT_TEST_DISABLE_EOIE=true test_expect_success 'enable split index' ' git config splitIndex.maxPercentChange 100 &&
The End of Index Entry (EOIE) is used to locate the end of the variable length index entries and the beginning of the extensions. Code can take advantage of this to quickly locate the index extensions without having to parse through all of the index entries. Because it must be able to be loaded before the variable length cache entries and other index extensions, this extension must be written last. The signature for this extension is { 'E', 'O', 'I', 'E' }. The extension consists of: - 32-bit offset to the end of the index entries - 160-bit SHA-1 over the extension types and their sizes (but not their contents). E.g. if we have "TREE" extension that is N-bytes long, "REUC" extension that is M-bytes long, followed by "EOIE", then the hash would be: SHA-1("TREE" + <binary representation of N> + "REUC" + <binary representation of M>) Signed-off-by: Ben Peart <Ben.Peart@microsoft.com> --- Documentation/technical/index-format.txt | 23 ++++ read-cache.c | 149 +++++++++++++++++++++-- t/README | 5 + t/t1700-split-index.sh | 1 + 4 files changed, 170 insertions(+), 8 deletions(-)