On 11/9/2017 11:46 PM, Junio C Hamano wrote:
Ben Peart <benpeart@xxxxxxxxxxxxx> writes:
To make this work for V4 indexes, when writing the index, it periodically
"resets" the prefix-compression by encoding the current entry as if the
path name for the previous entry is completely different and saves the
offset of that entry in the IEOT. Basically, with V4 indexes, it
generates offsets into blocks of prefix-compressed entries.
You specifically mentioned about this change in your earlier
correspondence on this series, and it reminds me of Shawn's reftable
proposal that also is heavily depended on prefix compression with
occasional reset to allow scanning from an entry in the middle. I
find it a totally sensible design choice.
Great! I didn't realize there was already precedent for this in other
patches. I guess good minds think alike... :)
To enable reading the IEOT extension before reading all the variable
length cache entries and other extensions, the IEOT is written last,
right before the trailing SHA1.
OK, we have already closed the door for further enhancements to
place something other than the index extensions after this block by
mistakenly made it the rule that the end of the series of extended
sections must coincide with the beginning of the trailing checksum,
so it does not sound all that bad to insist on this particular one
to be the last, I guess. But see below...
The format of that extension has the signature bytes and size at the
beginning (like a normal extension) as well as at the end in reverse
order to enable parsing the extension by seeking back from the end of
the file.
I think this is a reasonable workaround to allow a single extension
that needs to be read before the main index is loaded.
But I'd suggest taking this approach one step further. Instead,
what if we introduce a new extension EOIE ("end of index entries")
whose sole purpose is to sit at the end of the series of extensions
and point at the beginning of the index extension section of the
file, to tell you where to seek in order to skip the main index?
That way, you can
- seek to the end of the index file;
- go backward skiping the trailing file checksum;
- now you might be at the end of the EOIE extension. seek back
necessary number of bytes and verify EOIE header, pick up the
recorded file offset of the beginning of the extensions section.
- The 4-byte sequence you found may happen to match EOIE but that
is not enough to be sure that you indeed have such an extension.
So the following must be done carefully, allowing the possibility
that there wasn't any EOIE extension at the end.
Seek back to that offset, and repeat these three steps to skip
over all extensions:
- read the (possible) 4-byte header
- read the (possible) extsize (validate that this is a sane value)
- skip that many bytes
until you come back to the location you assumed that you found
your EOIE header, to make sure you did not get fooled by bytes
that happened to look like one. Some "extsize" you picked up
during that process may lead you beyond the end of the index
file, which would be a sure sign that what you found at the end
of the index file was *not* the EOIE extension but a part of
some other extension who happened to have these four bytes at the
right place.
I'm doing this careful examination and verification in the patch
already. Please look closely at read_ieot_extension() to make sure
there isn't a test I should be doing but missed.
which would be a lot more robust way to allow any extensions to be
read before the main body of the index.
And a lot more importantly, we will leave the door open to allow
more than one index extensions that we would prefer to read before
reading the main body if we do it this way, because we can easily
skip things over without spending cycles once we have a robust way
to find where the end of the main index is. After all, the reason
you placed IEOT at the end is not because you wanted to have it at
the very end. You only wanted to be able to find where it is
without having to parse the variable-length records of the main
index. And there may be other index extensions that wants to be
readable without reading the main part just like IEOT, and we do not
want to close the door for them.
The proposed format for extensions (ie having both a header and a footer
with name and size) in the current patch already enables having multiple
extensions that can be parsed forward or backward. Any extensions that
would want to be parse-able in reverse would just all need to be written
one after the other after right before the trailing SHA1 (and of course,
include the proper footer). The same logic that parses the IEOT
extension could be extended to continue looking backwards through the
file parsing extensions until it encounters an unknown signature,
invalid size, etc.
That said, the IEOT is essentially a table of contents into the index (I
hesitate to call it an index of the index as that could get confusing
:)). While in the current iteration of this patch it only contains
offsets into blocks of cache entries that are independently parse-able,
I had initially considered including an offset into the index where the
extensions start just as you suggest above.
When I looked at the existing extensions to see if they could be sped up
by loading them on parallel threads I found that some of them
assume/require they are processed in a specific order so there was no
real benefit to loading them in parallel threads.
I ended up removing the offset to the first extension because I've found
that trying to speculatively design a feature for a potential future
need often doesn't result in what you actually need once you get there.
:) Instead, I made sure there was a version number in the IEOT
structure so if we actually needed a way to extend the table of contents
at some point in the future (like to include an offset to the
extensions), we could easily add it and increment the IEOT version.
I could add the offset back in but currently nothing would use it so
we're just adding additional complexity to calculate and parse it with
with no (current) benefit.
How about I rename this the "Index Table of Contents" (ITOC) to make
it's potential more clear and if/when we need to enhance it with an
offset to the extensions, we do so at that point in time?
Hmm?
