| Message ID | af2742e05dff48c4ba0a9f36d58bcbfc052dca40.1697144959.git.me@ttaylorr.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | Documentation/gitformat-pack.txt: correct a few issues/typos | expand |
Taylor Blau <me@ttaylorr.com> writes: > diff --git a/Documentation/gitformat-pack.txt b/Documentation/gitformat-pack.txt > index d7153962d4..54000c9412 100644 > --- a/Documentation/gitformat-pack.txt > +++ b/Documentation/gitformat-pack.txt > @@ -392,8 +392,9 @@ CHUNK DATA: > Packfile Names (ID: {'P', 'N', 'A', 'M'}) > Stores the packfile names as concatenated, NUL-terminated strings. Not a problem this series (neither this or the previous step) introduces, but I had to read the implementation of write_midx_pack_names() to find out what "concatenated NUL-terminated string" really means. The code has a list of strings, writes each of them as a NUL-terminated string in sequence, and to align the beginning of the next chunk, NULs are added to make the whole thing multiple of MIDX_CHUNK_ALIGNMENT bytes. A naive reader code might implement a loop like so: while (ptr[0] != '\0') { endp = strlen(ptr); ... ptr[0..endp] is one pathname ... ptr = endp + 1; } expecting that the terminating NUL of the last entry would be followed by a NUL, but that is buggy. The sum of the pathname strings (with one NUL after each) may happen to be multiple of MIDX_CHUNK_ALIGNMENT bytes, in which case no extra padding NUL bytes will be there. So the reader also needs to pay attention to the chunk size to notice when to stop reading. It feels somewhat suboptimal. > Packfiles must be listed in lexicographic order for fast lookups by > - name. This is the only chunk not guaranteed to be a multiple of four > - bytes in length, so should be the last chunk for alignment reasons. > + name. Individual entries in this chunk are not guarenteed to be > + aligned. The chunk is externally padded with zeros to align > + remaining chunks. I am not sure what "externally padded" means. Before write_midx_pack_names() returns, there is a code to pad the space after it writes those names, which does not look any external than the bytes used to record the pathnames or NUL bytes used to terminate these pathnames. To me, "externally padded" is an appropriate phrase to use if this function does not bother with the alignment after what it needs to record, but the caller, i.e., write_chunkfile(), has code to notice that the number of bytes written by cf->chunks[i].write_fn() it just called is not a multiple of some required alignment and adds padding bytes after .write_fn() returned. I do not think that is what is going on here. My observations. * The packfile names chunk is used to record N pathnames; N is not recorded anywhere explicitly. To record N pathnames, a single chunk with N names in it is used. It is not like N chunks, each with one name is used. * Each of these pathname is recorded literally, followed by a NUL, in some order, without any extra padding. * To keep the size of the chunk multiple of alignment requirement, there may be extra NUL bytes after the names. This data structure does not allow you to binary search or hash lookup without an extra table of pointers into this table of strings at runtime, and once you build such a table, the source being sorted does not help all that much. So I am not sure how strict the "lexicographic" requirement needs to be, but of course, starting strict and loosening later is much easier than starting loose, so documenting "must be listed" and following that rule is fine. Thanks.
On Thu, Oct 12, 2023 at 02:54:17PM -0700, Junio C Hamano wrote: > Taylor Blau <me@ttaylorr.com> writes: > > > diff --git a/Documentation/gitformat-pack.txt b/Documentation/gitformat-pack.txt > > index d7153962d4..54000c9412 100644 > > --- a/Documentation/gitformat-pack.txt > > +++ b/Documentation/gitformat-pack.txt > > @@ -392,8 +392,9 @@ CHUNK DATA: > > Packfile Names (ID: {'P', 'N', 'A', 'M'}) > > Stores the packfile names as concatenated, NUL-terminated strings. > > Not a problem this series (neither this or the previous step) > introduces, but I had to read the implementation of > write_midx_pack_names() to find out what "concatenated > NUL-terminated string" really means. The code has a list of > strings, writes each of them as a NUL-terminated string in sequence, > and to align the beginning of the next chunk, NULs are added to make > the whole thing multiple of MIDX_CHUNK_ALIGNMENT bytes. > > A naive reader code might implement a loop like so: > > while (ptr[0] != '\0') { > endp = strlen(ptr); > ... ptr[0..endp] is one pathname ... > ptr = endp + 1; > } > > expecting that the terminating NUL of the last entry would be > followed by a NUL, but that is buggy. The sum of the pathname > strings (with one NUL after each) may happen to be multiple of > MIDX_CHUNK_ALIGNMENT bytes, in which case no extra padding NUL bytes > will be there. So the reader also needs to pay attention to the > chunk size to notice when to stop reading. It feels somewhat > suboptimal. I agree. > > Packfiles must be listed in lexicographic order for fast lookups by > > - name. This is the only chunk not guaranteed to be a multiple of four > > - bytes in length, so should be the last chunk for alignment reasons. > > + name. Individual entries in this chunk are not guarenteed to be > > + aligned. The chunk is externally padded with zeros to align > > + remaining chunks. > > I am not sure what "externally padded" means. How about something like this, instead? --- 8< --- diff --git a/Documentation/gitformat-pack.txt b/Documentation/gitformat-pack.txt index 0bc80f0d46..229490f82f 100644 --- a/Documentation/gitformat-pack.txt +++ b/Documentation/gitformat-pack.txt @@ -392,9 +392,10 @@ CHUNK DATA: Packfile Names (ID: {'P', 'N', 'A', 'M'}) Stores the packfile names as concatenated, NUL-terminated strings. Packfiles must be listed in lexicographic order for fast lookups by - name. Individual entries in this chunk are not guarenteed to be - aligned. The chunk is externally padded with zeros to align - remaining chunks. + name. Individual entries in this chunk are not guaranteed to be + aligned, since the packfile names can be of arbitrary length. The + chunk itself is padded at the end with NUL bytes in order to align + the remaining chunks. OID Fanout (ID: {'O', 'I', 'D', 'F'}) The ith entry, F[i], stores the number of OIDs with first --- >8 --- Thanks, Taylor
Taylor Blau <me@ttaylorr.com> writes: >> > Packfiles must be listed in lexicographic order for fast lookups by >> > - name. This is the only chunk not guaranteed to be a multiple of four >> > - bytes in length, so should be the last chunk for alignment reasons. >> > + name. Individual entries in this chunk are not guarenteed to be >> > + aligned. The chunk is externally padded with zeros to align >> > + remaining chunks. >> >> I am not sure what "externally padded" means. > > How about something like this, instead? > > --- 8< --- > diff --git a/Documentation/gitformat-pack.txt b/Documentation/gitformat-pack.txt > index 0bc80f0d46..229490f82f 100644 > --- a/Documentation/gitformat-pack.txt > +++ b/Documentation/gitformat-pack.txt > @@ -392,9 +392,10 @@ CHUNK DATA: > Packfile Names (ID: {'P', 'N', 'A', 'M'}) > Stores the packfile names as concatenated, NUL-terminated strings. > Packfiles must be listed in lexicographic order for fast lookups by > - name. Individual entries in this chunk are not guarenteed to be > - aligned. The chunk is externally padded with zeros to align > - remaining chunks. > + name. Individual entries in this chunk are not guaranteed to be > + aligned, since the packfile names can be of arbitrary length. The > + chunk itself is padded at the end with NUL bytes in order to align > + the remaining chunks. There is no alignment requirement described, so "not guaranteed" and "in order to align" sound hollow. These are always byte-aligned ;-) How about something along this line to simplify it a bit? Store the names of packfiles as a sequence of NUL-terminated strings. There is no extra padding between the filenames, and they are listed in lexicographic order. The chunk itself is padded at the end with NUL bytes to make the chunk size a multiple of 4 bytes. I did not ccheck if the chunks need to be 4-byte aligned, so if the number is wrong, please adjust accordingly.
diff --git a/Documentation/gitformat-pack.txt b/Documentation/gitformat-pack.txt index d7153962d4..54000c9412 100644 --- a/Documentation/gitformat-pack.txt +++ b/Documentation/gitformat-pack.txt @@ -392,8 +392,9 @@ CHUNK DATA: Packfile Names (ID: {'P', 'N', 'A', 'M'}) Stores the packfile names as concatenated, NUL-terminated strings. Packfiles must be listed in lexicographic order for fast lookups by - name. This is the only chunk not guaranteed to be a multiple of four - bytes in length, so should be the last chunk for alignment reasons. + name. Individual entries in this chunk are not guarenteed to be + aligned. The chunk is externally padded with zeros to align + remaining chunks. OID Fanout (ID: {'O', 'I', 'D', 'F'}) The ith entry, F[i], stores the number of OIDs with first
Back in 32f3c541e3 (multi-pack-index: write pack names in chunk, 2018-07-12) the MIDX's "Packfile Names" (or "PNAM", for short) chunk was described as containing an array of string entries. e0d1bcf825 notes that this is the only chunk in the MIDX format's specification that is not guaranteed to be 4-byte aligned, and so should be placed last. This isn't quite accurate: the entries within the PNAM chunk are not guaranteed to be aligned since they are arbitrary strings, but the chunk itself is aligned since the ending is padded with NUL bytes. That external padding has always been there since 32f3c541e3 via midx.c::write_midx_pack_names(), which ended with: i = MIDX_CHUNK_ALIGNMENT - (written % MIDX_CHUNK_ALIGNMENT) if (i < MIDX_CHUNK_ALIGNMENT) { unsigned char padding[MIDX_CHUNK_ALIGNMENT]; memset(padding, 0, sizeof(padding)) hashwrite(f, padding, i); written += i; } In fact, 32f3c541e3's log message itself describes the chunk in its first paragraph with: Since filenames are not well structured, add padding to keep good alignment in later chunks. So these have always been externally aligned. Correct the corresponding part of our documentation to reflect that. Signed-off-by: Taylor Blau <me@ttaylorr.com> --- Documentation/gitformat-pack.txt | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-)