[GSoC] Designing a faster index format - Progress report week 6

[GSoC] Designing a faster index format - Progress report week 6

[Thomas Gummerer]

Here is another quick overview of the current progress of my
Google Summer of Code project. I'm currently planning to do
those weekly, to keep you up to date with the progress.

== Work done in the previous 5 weeks ==

- Definition of a tentative index file v5 format [1]. This differs
  from the proposal in making it possible to bisect the directory
  entries and file entries, to do a binary search. The exact bits
  for each section were also defined. To further compress the index,
  along with prefix compression, the stat data is hashed, since
  it's only used for comparison, but the plain data is never used.
  Thanks to Michael Haggerty, Nguyen Thai Ngoc Duy, Thomas Rast
  and Robin Rosenberg for feedback.
- Prototype of a converter from the index format v2/v3 to the index
  format v5. [2] The converter reads the index from a git repository,
  can output parts of the index (header, index entries as in
  git ls-files --debug, cache tree as in test-dump-cache-tree, or
  the reuc data). Then it writes the v5 index file format to
  .git/index-v5. Thanks to Michael Haggerty for the code review.
- Prototype of a reader for the new index file format. [3] The
  reader has mainly the purpose to show the algorithm used to read
  the index lexicographically sorted after the full name which is
  required by the current internal memory format. Big thanks for
  reviewing this code and giving me advice on refactoring goes
  to Michael Haggerty.

== Work done in the last week ==

- Started working on the actual git code. Git is now able to read
  the index format v5, although the mapping of the new ondisk
  format to the internal format is not done yet. The latest code
  is not pushed to github yet, since it still needs some polishing,
  but if anyone is interested in the general direction it's going,
  the initial steps are on github. [4] Thanks for reviewing the
  first steps to Thomas Rast.

== Outlook for the next week ==

- Refactoring of the read_index_v5 code, and possibly mapping of
  the read index to the current internal format (If there's enough
  time)
- Make git ls-files read the new index format directly, to show
  some of its advantages. (Thanks to Nguyen Thai Ngoc Duy, and
  Junio C Hamano for the suggestion)

[1] https://github.com/tgummerer/git/wiki/Index-file-format-v5
[2] https://github.com/tgummerer/git/blob/pythonprototype/git-convert-index.py
[3] https://github.com/tgummerer/git/blob/pythonprototype/git-read-index-v5.py
[4] https://github.com/tgummerer/git/tree/index-v5

Review of current github code [Re: [GSoC] Designing a faster index format - Progress report week 6]

[Thomas Rast]

Hi,

Thomas has again been busy hacking, and the reading side is now capable
of reading a v5 index into the (existing) array-of-cache_entry format.
It is actually already measurably faster than both v4 and v[23] on the
Webkit index:

  Test                      this tree      
  -----------------------------------------
  0002.1: v[23]: ls-files   0.13(0.11+0.02)
  0002.4: v4: ls-files      0.11(0.08+0.02)
  0002.5: v5: ls-files      0.09(0.06+0.02)

I made up a hacky perf script on the spot, it's pasted at the far end of
this email.  It would most likely still be slower than v4 if we didn't
switch away from SHA1, though -- we haven't really spent much time
looking into the speed, except for one particular avoidance of name
copies that translated into a roughly 30% speedup.

As before, what follows is a review of the WIP code on github at

  git://github.com/tgummerer/git.git index-v5

I looked at version fed977b, however I will pretend it consists of just
two commits (as far as the C code is concerned):

* (174fea4) Refactoring to accomodate other index versions
* All others (174fea4..fed977b), squashed

I'm doing this because the history is still not in "submission-style"
shape, as discussed in

  http://thread.gmane.org/gmane.comp.version-control.git/198283/focus=198412

and Junio's reply to it.


As far as 174fea4 goes: I think you could split it into two separate
commits, one for the code movement (i.e., refactoring of a large chunk
of read_index_from into read_index_v2_from), and a second one for the
introduction of the separate header struct.  Other than that it looks
good.


The rest would look like this:

>  cache.h                |  32 ++++-
>  read-cache.c           | 315 ++++++++++++++++++++++++++++++++++++++++++++++---
>  5 files changed, 334 insertions(+), 29 deletions(-)

The review follows, though note that as usual I have snipped all hunks
where I didn't have anything to add:

> @@ -108,6 +108,13 @@ struct cache_header_v2 {
>  	unsigned int hdr_entries;
>  };
>  
> +struct cache_header_v5 {
> +	unsigned int hdr_ndir;
> +	unsigned int hdr_nfile;
> +	unsigned int hdr_fblockoffset;
> +	unsigned int hdr_nextension;
> +};
> +
>  #define INDEX_FORMAT_LB 2
>  #define INDEX_FORMAT_UB 4

Somewhat confusingly, the non-update to INDEX_FORMAT_UB is correct since
that is only used by git-update-index to verify that a user request for
the *write* format is valid, and we don't currently support writing v5.

> @@ -132,11 +139,27 @@ struct cache_entry {
>  	unsigned int ce_size;
>  	unsigned int ce_flags;
>  	unsigned char sha1[20];
> +	int ce_stat_crc;

This should probably be an unsigned int for correctness.  The docs for
zlib actually say it has type 'uLong', whatever that might mean.  Don't
turn it into an unsigned long though, that would be 64 bits at least on
x86_64 Linux.

> +	unsigned int ce_namelen;

You are using this to hack around the issue that we dropped the name
length out of the flags to save bits.  Perhaps it would be a nice
cleanup to keep it in the struct "in the open", instead of having the
odd ce_namelen() wrapper that amounts to a maybe-strlen.

> +struct directory_entry {
> +	unsigned short de_flags;
> +	unsigned int de_foffset;
> +	unsigned int de_cr;
> +	unsigned int de_ncr;
> +	unsigned int de_nsubtrees;
> +	unsigned int de_nfiles;
> +	unsigned int de_nentries;
> +	unsigned char sha1[20];
> +	struct directory_entry *next;
> +	unsigned int de_pathlen;
> +	char pathname[FLEX_ARRAY];
> +};

Why are the flags out of order compared to the on-disk layout?

Also, if you make a linked list it would be more natural (to me) to put
the 'next' member at the top.  I suspect the precedent in 'cache_entry'
may be from times where that was the ondisk layout, and thus any
not-on-disk entries had to be at the end.  Perhaps Junio can clarify
this.

> -extern void read_index_v2_from(struct index_state *, struct stat, void *mmap, int);
> +extern void read_index_v2(struct index_state *, struct stat, void *mmap, int);
> +extern void read_index_v5(struct index_state *, struct stat, void *mmap, int);

You should make up your mind in the refactoring patch ;-)

> diff --git a/read-cache.c b/read-cache.c
> index 750fbfa..fc8033a 100644
> --- a/read-cache.c
> +++ b/read-cache.c
> @@ -397,8 +397,9 @@ int df_name_compare(const char *name1, int len1, int mode1,
>  
>  int cache_name_compare(const char *name1, int flags1, const char *name2, int flags2)
>  {
> -	int len1 = flags1 & CE_NAMEMASK;
> -	int len2 = flags2 & CE_NAMEMASK;
> +	/* TODO: This possibly can be replaced with something faster */
> +	int len1 = strlen(name1);
> +	int len2 = strlen(name2);
>  	int len = len1 < len2 ? len1 : len2;
>  	int cmp;

Now that you have the ce_namelen entry, shouldn't you use that here?

If it is not filled in correctly by the other readers, you'd have to
patch them, preferably in an earlier patch where you introduce this
field (only -- not doing any v5 work yet).

> +static int verify_hdr_v5(void *mmap)
> +{
> +	uint32_t crc;
> +	uint32_t* filecrc;
> +	unsigned int header_size_v5;
> +	struct cache_version_header *hdr;
> +	struct cache_header_v5 *hdr_v5;
> +
> +	hdr = mmap;
> +	hdr_v5 = mmap + sizeof(*hdr);
> +	/* Size of the header + the size of the extensionoffsets */
> +	header_size_v5 = sizeof(*hdr_v5) + hdr_v5->hdr_nextension * 4;
> +	/* Initialize crc */
> +	crc = crc32(0, (Bytef*)hdr, sizeof(*hdr));
> +	crc = crc32(crc, (Bytef*)hdr_v5, header_size_v5);

Can't you crc32() this block in one go?

> +	filecrc = mmap + sizeof(*hdr) + header_size_v5;
> +	if (crc != ntohl(*filecrc))
> +		return error("bad index file header crc signature");
> +	return 0;
> +}
> +
>  static int read_index_extension(struct index_state *istate,
>  				const char *ext, void *data, unsigned long sz)
>  {
> @@ -1315,23 +1361,71 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on
>  {
>  	struct cache_entry *ce = xmalloc(cache_entry_size(len));
>  
> -	ce->ce_ctime.sec = ntoh_l(ondisk->ctime.sec);
> -	ce->ce_mtime.sec = ntoh_l(ondisk->mtime.sec);
> +	ce->ce_ctime.sec  = ntoh_l(ondisk->ctime.sec);
> +	ce->ce_mtime.sec  = ntoh_l(ondisk->mtime.sec);
>  	ce->ce_ctime.nsec = ntoh_l(ondisk->ctime.nsec);
>  	ce->ce_mtime.nsec = ntoh_l(ondisk->mtime.nsec);
> -	ce->ce_dev   = ntoh_l(ondisk->dev);
> -	ce->ce_ino   = ntoh_l(ondisk->ino);
> -	ce->ce_mode  = ntoh_l(ondisk->mode);
> -	ce->ce_uid   = ntoh_l(ondisk->uid);
> -	ce->ce_gid   = ntoh_l(ondisk->gid);
> -	ce->ce_size  = ntoh_l(ondisk->size);
> -	ce->ce_flags = flags;
> +	ce->ce_dev        = ntoh_l(ondisk->dev);
> +	ce->ce_ino        = ntoh_l(ondisk->ino);
> +	ce->ce_mode       = ntoh_l(ondisk->mode);
> +	ce->ce_uid        = ntoh_l(ondisk->uid);
> +	ce->ce_gid        = ntoh_l(ondisk->gid);
> +	ce->ce_size       = ntoh_l(ondisk->size);
> +	ce->ce_flags      = flags;
> +	ce->ce_namelen    = len;

AFAICS all but the last one only change the alignment of the
assignments.  Only the last addition is a true change, related to the
addition of the ce_namelen field.  It would be far easier on the
reviewers if you first did the alignment cleanup (it can then be checked
to be a no-change patch simply with --ignore-space-change), and then the
ce_namelen, before any v5 work.

> +static struct directory_entry *read_directories_v5(unsigned int dir_offset,
> +				unsigned int ndir,
> +				void *mmap,
> +				int mmap_size)
> +{
> +	int i;
> +	uint32_t crc;
> +	uint32_t* filecrc;
> +	struct directory_entry *entries = NULL;
> +	struct directory_entry *current = NULL;
> +
> +	for (i = 0; i < ndir; i++) {
> +		struct ondisk_directory_entry *disk_de;
> +		struct directory_entry *de;
> +		unsigned int data_len; 
> +		unsigned int len;
> +		char *name;
> +
> +		name = (char *)mmap + dir_offset;
> +		len = strlen(name);
> +		disk_de = (struct ondisk_directory_entry *)
> +				((char *)mmap + dir_offset + len + 1);
> +		de = directory_entry_from_ondisk(disk_de, name, len);
> +
> +		if (entries == NULL) {
> +			entries = de;
> +			current = de;
> +		} else {
> +			current->next = de;
> +			current = current->next;
> +			current->next = NULL;
> +		}
> +
> +		/* Length of pathname + nul byte for termination + size of
> +		 * members of ondisk_directory_entry. (Just using the size
> +		 * of the stuct doesn't work, because there may be padding
> +		 * bytes for the struct)
> +		 */

Style nit: 

> +		data_len = len + 1
> +			+ sizeof(disk_de->flags)
> +			+ sizeof(disk_de->foffset)
> +			+ sizeof(disk_de->cr)
> +			+ sizeof(disk_de->ncr)
> +			+ sizeof(disk_de->nsubtrees)
> +			+ sizeof(disk_de->nfiles)
> +			+ sizeof(disk_de->nentries)
> +			+ sizeof(disk_de->sha1);

How does this differ from

  data_len = len + 1 + sizeof(struct ondisk_directory_entry);

?

> +
> +		crc = crc32(0, (Bytef*)(mmap + dir_offset), data_len);
> +		filecrc = mmap + dir_offset + data_len;
> +		if (crc != ntoh_l(*filecrc))
> +			goto unmap;

The CRC checking code in general is a bit noisy on my eyes, increasing
the risk that I would miss a mistake in one of the calls.  I wonder if
you could refactor it as something like

  static int check_crc32_chunk(void *data, size_t len, unsigned int expected_crc);

Then again the pointer math would still be on the caller side.  Sigh.

> +
> +		dir_offset += data_len + 4; /* crc code */
> +	}
> +
> +	return entries;
> +unmap:
> +	munmap(mmap, mmap_size);
> +	errno = EINVAL;
> +	die("directory crc doesn't match for '%s'", current->pathname);
> +}

I can see there's precedent for this in read_index_v2 (as of your patch;
it used to be in read_index_from); but what's the point of setting errno
immediately before not using it and exiting?

That's all for today.  Thanks for reading.


---- t/perf/p0002-index-v5.sh ----
#!/bin/sh

test_description="Tests index versions [23]/4/5"

. ./perf-lib.sh

test_perf_large_repo

test_perf 'v[23]: ls-files' '
	git ls-files >/dev/null
'

test_expect_success 'convert to v5' '
	$GIT_BUILD_DIR/git-convert-index.py
'

test_expect_success 'convert to v4' '
	git update-index --index-version=4
'

test_perf 'v4: ls-files' '
	git ls-files >/dev/null
'

test_perf 'v5: ls-files' '
	GIT_INDEX_FILE=.git/index-v5 git ls-files >/dev/null
'

test_done
----- t/perf/p0002-index-v5.sh ----

-- 
Thomas Rast
trast@{inf,student}.ethz.ch

Re: Review of current github code [Re: [GSoC] Designing a faster index format - Progress report week 6]

[Junio C Hamano]

Thomas Rast <trast@student.ethz.ch> writes:

> Thomas has again been busy hacking, and the reading side is now capable
> of reading a v5 index into the (existing) array-of-cache_entry format.
> It is actually already measurably faster than both v4 and v[23] on the
> Webkit index:
>
>   Test                      this tree      
>   -----------------------------------------
>   0002.1: v[23]: ls-files   0.13(0.11+0.02)
>   0002.4: v4: ls-files      0.11(0.08+0.02)
>   0002.5: v5: ls-files      0.09(0.06+0.02)
>
> I made up a hacky perf script on the spot, it's pasted at the far end of
> this email.  It would most likely still be slower than v4 if we didn't
> switch away from SHA1, though -- we haven't really spent much time
> looking into the speed, except for one particular avoidance of name
> copies that translated into a roughly 30% speedup.

Do you mean by "switch away from SHA-1" that your suspicion is a
large part of the speed-up may be coming from the fact that the
index file as a whole is no longer hashed?

As long as the new format allows us to notice corruption in the file
to a similar degree of confidence by some other means, I personally
do not see it as a regression in safety.

We however eventually would need to hook the logic to check for
index corruption into fsck.  Actually adding such a code to fsck can
and probably should remain outside the GSoC project, but please make
sure you have necessary checksums in the format to allow us to do so
in the future.

Thanks.

Re: Review of current github code [Re: [GSoC] Designing a faster index format - Progress report week 6]

[Thomas Rast]

Junio C Hamano <gitster@pobox.com> writes:

> Thomas Rast <trast@student.ethz.ch> writes:
>
>>   Test                      this tree      
>>   -----------------------------------------
>>   0002.1: v[23]: ls-files   0.13(0.11+0.02)
>>   0002.4: v4: ls-files      0.11(0.08+0.02)
>>   0002.5: v5: ls-files      0.09(0.06+0.02)
>>
>> I made up a hacky perf script on the spot, it's pasted at the far end of
>> this email.  It would most likely still be slower than v4 if we didn't
>> switch away from SHA1, though -- we haven't really spent much time
>> looking into the speed, except for one particular avoidance of name
>> copies that translated into a roughly 30% speedup.
>
> Do you mean by "switch away from SHA-1" that your suspicion is a
> large part of the speed-up may be coming from the fact that the
> index file as a whole is no longer hashed?

Yes.  Since the v5 index is only slightly smaller than v4 one, the
reduction in data read cannot explain the difference alone.

I tried to quantify this a little.  For SHA1 and the v2/v4 index
(25MB/14MB, resp.), I get about 70ms/44ms for

  time git hash-object --stdin <.git/index

On the other hand I get about 35ms/22ms for

  time ~/g/test-crc32 .git/index

I do have a system crc32 utility, but it uses read() in 8k blocks
instead of mmap() and takes about 87ms.

So we can see that the switch from 25MB to 14MB fully explains the
speedup for v2->v4, and the switch from SHA1 to CRC32 explains the
speedup for v4->v5.

However, aside from gaining 20ms here, CRC32 is also suitable for
checking very short chunks of data, as is planned for the partial
loading support in v5.

> As long as the new format allows us to notice corruption in the file
> to a similar degree of confidence by some other means, I personally
> do not see it as a regression in safety.
> 
> We however eventually would need to hook the logic to check for
> index corruption into fsck.  Actually adding such a code to fsck can
> and probably should remain outside the GSoC project, but please make
> sure you have necessary checksums in the format to allow us to do so
> in the future.

I actually expect that a full loading of the index will verify all
checksums that are present in the file.  Since file additions and such
will still need a full rewrite, and thus a full read, I expect this to
happen every so often as a matter of normal operations.  fsck could of
course still learn to load the index at some point, for good measure.


diff --git i/Makefile w/Makefile
index 63eacda..76856bc 100644
--- i/Makefile
+++ w/Makefile
@@ -481,6 +481,7 @@ X =
 PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS))
 
 TEST_PROGRAMS_NEED_X += test-chmtime
+TEST_PROGRAMS_NEED_X += test-crc32
 TEST_PROGRAMS_NEED_X += test-credential
 TEST_PROGRAMS_NEED_X += test-ctype
 TEST_PROGRAMS_NEED_X += test-date
diff --git i/test-crc32.c w/test-crc32.c
index e69de29..092de48 100644
--- i/test-crc32.c
+++ w/test-crc32.c
@@ -0,0 +1,32 @@
+#include "git-compat-util.h"
+#include <zlib.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <sys/mman.h>
+
+int main (int argc, char *argv[])
+
+{
+	unsigned int crc;
+	struct stat st;
+	int fd;
+	void *map;
+
+	if (argc != 2)
+		die("usage: %s <file>\n", argv[0]);
+	fd = open(argv[1], O_RDONLY);
+	if (fd < 0)
+		die_errno("open");
+	if (fstat(fd, &st) < 0)
+		die_errno("fstat");
+	map = mmap(NULL, st.st_size, PROT_READ, MAP_SHARED, fd, 0);
+	if (map == MAP_FAILED)
+		die_errno("mmap");
+
+	crc = crc32(0, map, st.st_size);
+	printf("%8x\n", crc);
+
+	return 0;
+}


-- 
Thomas Rast
trast@{inf,student}.ethz.ch

Re: Review of current github code [Re: [GSoC] Designing a faster index format - Progress report week 6]

[Thomas Gummerer]

On 05/31, Thomas Rast wrote:
> As far as 174fea4 goes: I think you could split it into two separate
> commits, one for the code movement (i.e., refactoring of a large chunk
> of read_index_from into read_index_v2_from), and a second one for the
> introduction of the separate header struct.  Other than that it looks
> good.

Thanks for your review. I rebased the commits now, 174fea4 is now
5eb9c21 and 946888d. There were also two commits to the python code,
which I moved previous of the refactoring commits. (210d1ff and b99fdf8)

> The rest would look like this:
> 
> >  cache.h                |  32 ++++-
> >  read-cache.c           | 315 ++++++++++++++++++++++++++++++++++++++++++++++---
> >  5 files changed, 334 insertions(+), 29 deletions(-)
> 
> The review follows, though note that as usual I have snipped all hunks
> where I didn't have anything to add:
> 
> > @@ -108,6 +108,13 @@ struct cache_header_v2 {
> >  	unsigned int hdr_entries;
> >  };
> >  
> > +struct cache_header_v5 {
> > +	unsigned int hdr_ndir;
> > +	unsigned int hdr_nfile;
> > +	unsigned int hdr_fblockoffset;
> > +	unsigned int hdr_nextension;
> > +};
> > +
> >  #define INDEX_FORMAT_LB 2
> >  #define INDEX_FORMAT_UB 4
> 
> Somewhat confusingly, the non-update to INDEX_FORMAT_UB is correct since
> that is only used by git-update-index to verify that a user request for
> the *write* format is valid, and we don't currently support writing v5.

I left them as they are, since they aren't used in the read code, so I
thought this would be fine.

> > @@ -132,11 +139,27 @@ struct cache_entry {
> >  	unsigned int ce_size;
> >  	unsigned int ce_flags;
> >  	unsigned char sha1[20];
> > +	int ce_stat_crc;
> 
> This should probably be an unsigned int for correctness.  The docs for
> zlib actually say it has type 'uLong', whatever that might mean.  Don't
> turn it into an unsigned long though, that would be 64 bits at least on
> x86_64 Linux.

I digged a bit in the git code, uint32_t seems to be the right way to
do it. (as in csum-file.h) I converted it to that for now.

> > +	unsigned int ce_namelen;
> 
> You are using this to hack around the issue that we dropped the name
> length out of the flags to save bits.  Perhaps it would be a nice
> cleanup to keep it in the struct "in the open", instead of having the
> odd ce_namelen() wrapper that amounts to a maybe-strlen.

I guess that may better fit in a refactoring patch? I put it in
e73adcf.

> > +struct directory_entry {
> > +	unsigned short de_flags;
> > +	unsigned int de_foffset;
> > +	unsigned int de_cr;
> > +	unsigned int de_ncr;
> > +	unsigned int de_nsubtrees;
> > +	unsigned int de_nfiles;
> > +	unsigned int de_nentries;
> > +	unsigned char sha1[20];
> > +	struct directory_entry *next;
> > +	unsigned int de_pathlen;
> > +	char pathname[FLEX_ARRAY];
> > +};
> 
> Why are the flags out of order compared to the on-disk layout?
> 
> Also, if you make a linked list it would be more natural (to me) to put
> the 'next' member at the top.  I suspect the precedent in 'cache_entry'
> may be from times where that was the ondisk layout, and thus any
> not-on-disk entries had to be at the end.  Perhaps Junio can clarify
> this.

They were in order at the beginning, before I moved the flags to the
end in the ondisk format, and forgot to move them in the struct. It's
in order now.

I also moved the next member to the top. I originally put it at the
end, because it was at the end for the cache_entry too.

> > -extern void read_index_v2_from(struct index_state *, struct stat, void *mmap, int);
> > +extern void read_index_v2(struct index_state *, struct stat, void *mmap, int);
> > +extern void read_index_v5(struct index_state *, struct stat, void *mmap, int);
> 
> You should make up your mind in the refactoring patch ;-)

I thing read_index_v2 makes more sense, since from sounds like we expect
a pathname.

> > diff --git a/read-cache.c b/read-cache.c
> > index 750fbfa..fc8033a 100644
> > --- a/read-cache.c
> > +++ b/read-cache.c
> > @@ -397,8 +397,9 @@ int df_name_compare(const char *name1, int len1, int mode1,
> >  
> >  int cache_name_compare(const char *name1, int flags1, const char *name2, int flags2)
> >  {
> > -	int len1 = flags1 & CE_NAMEMASK;
> > -	int len2 = flags2 & CE_NAMEMASK;
> > +	/* TODO: This possibly can be replaced with something faster */
> > +	int len1 = strlen(name1);
> > +	int len2 = strlen(name2);
> >  	int len = len1 < len2 ? len1 : len2;
> >  	int cmp;
> 
> Now that you have the ce_namelen entry, shouldn't you use that here?
> 
> If it is not filled in correctly by the other readers, you'd have to
> patch them, preferably in an earlier patch where you introduce this
> field (only -- not doing any v5 work yet).

Yes, there would be more patching needed, since the function uses the
flags too. The patch is not yet in the repository.

> > +static int verify_hdr_v5(void *mmap)
> > +{
> > +	uint32_t crc;
> > +	uint32_t* filecrc;
> > +	unsigned int header_size_v5;
> > +	struct cache_version_header *hdr;
> > +	struct cache_header_v5 *hdr_v5;
> > +
> > +	hdr = mmap;
> > +	hdr_v5 = mmap + sizeof(*hdr);
> > +	/* Size of the header + the size of the extensionoffsets */
> > +	header_size_v5 = sizeof(*hdr_v5) + hdr_v5->hdr_nextension * 4;
> > +	/* Initialize crc */
> > +	crc = crc32(0, (Bytef*)hdr, sizeof(*hdr));
> > +	crc = crc32(crc, (Bytef*)hdr_v5, header_size_v5);
> 
> Can't you crc32() this block in one go?

Yes, I just thought it's clearer this way, calculating the crc for the
signature + version and the rest of the header_v5. I changed it for now
to one block.

> > +	filecrc = mmap + sizeof(*hdr) + header_size_v5;
> > +	if (crc != ntohl(*filecrc))
> > +		return error("bad index file header crc signature");
> > +	return 0;
> > +}
> > +
> >  static int read_index_extension(struct index_state *istate,
> >  				const char *ext, void *data, unsigned long sz)
> >  {
> > @@ -1315,23 +1361,71 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on
> >  {
> >  	struct cache_entry *ce = xmalloc(cache_entry_size(len));
> >  
> > -	ce->ce_ctime.sec = ntoh_l(ondisk->ctime.sec);
> > -	ce->ce_mtime.sec = ntoh_l(ondisk->mtime.sec);
> > +	ce->ce_ctime.sec  = ntoh_l(ondisk->ctime.sec);
> > +	ce->ce_mtime.sec  = ntoh_l(ondisk->mtime.sec);
> >  	ce->ce_ctime.nsec = ntoh_l(ondisk->ctime.nsec);
> >  	ce->ce_mtime.nsec = ntoh_l(ondisk->mtime.nsec);
> > -	ce->ce_dev   = ntoh_l(ondisk->dev);
> > -	ce->ce_ino   = ntoh_l(ondisk->ino);
> > -	ce->ce_mode  = ntoh_l(ondisk->mode);
> > -	ce->ce_uid   = ntoh_l(ondisk->uid);
> > -	ce->ce_gid   = ntoh_l(ondisk->gid);
> > -	ce->ce_size  = ntoh_l(ondisk->size);
> > -	ce->ce_flags = flags;
> > +	ce->ce_dev        = ntoh_l(ondisk->dev);
> > +	ce->ce_ino        = ntoh_l(ondisk->ino);
> > +	ce->ce_mode       = ntoh_l(ondisk->mode);
> > +	ce->ce_uid        = ntoh_l(ondisk->uid);
> > +	ce->ce_gid        = ntoh_l(ondisk->gid);
> > +	ce->ce_size       = ntoh_l(ondisk->size);
> > +	ce->ce_flags      = flags;
> > +	ce->ce_namelen    = len;
> 
> AFAICS all but the last one only change the alignment of the
> assignments.  Only the last addition is a true change, related to the
> addition of the ce_namelen field.  It would be far easier on the
> reviewers if you first did the alignment cleanup (it can then be checked
> to be a no-change patch simply with --ignore-space-change), and then the
> ce_namelen, before any v5 work.

Ok, this is changed in e73adcf. The alignment is done in bbc8928. Hope
understood the alignment cleanup right.

> > +static struct directory_entry *read_directories_v5(unsigned int dir_offset,
> > +				unsigned int ndir,
> > +				void *mmap,
> > +				int mmap_size)
> > +{
> > +	int i;
> > +	uint32_t crc;
> > +	uint32_t* filecrc;
> > +	struct directory_entry *entries = NULL;
> > +	struct directory_entry *current = NULL;
> > +
> > +	for (i = 0; i < ndir; i++) {
> > +		struct ondisk_directory_entry *disk_de;
> > +		struct directory_entry *de;
> > +		unsigned int data_len; 
> > +		unsigned int len;
> > +		char *name;
> > +
> > +		name = (char *)mmap + dir_offset;
> > +		len = strlen(name);
> > +		disk_de = (struct ondisk_directory_entry *)
> > +				((char *)mmap + dir_offset + len + 1);
> > +		de = directory_entry_from_ondisk(disk_de, name, len);
> > +
> > +		if (entries == NULL) {
> > +			entries = de;
> > +			current = de;
> > +		} else {
> > +			current->next = de;
> > +			current = current->next;
> > +			current->next = NULL;
> > +		}
> > +
> > +		/* Length of pathname + nul byte for termination + size of
> > +		 * members of ondisk_directory_entry. (Just using the size
> > +		 * of the stuct doesn't work, because there may be padding
> > +		 * bytes for the struct)
> > +		 */
> 
> Style nit: 
> 
> > +		data_len = len + 1
> > +			+ sizeof(disk_de->flags)
> > +			+ sizeof(disk_de->foffset)
> > +			+ sizeof(disk_de->cr)
> > +			+ sizeof(disk_de->ncr)
> > +			+ sizeof(disk_de->nsubtrees)
> > +			+ sizeof(disk_de->nfiles)
> > +			+ sizeof(disk_de->nentries)
> > +			+ sizeof(disk_de->sha1);
> 
> How does this differ from
> 
>   data_len = len + 1 + sizeof(struct ondisk_directory_entry);
> 
> ?

There is only a single 16-bit entry in struct ondisk_directory_entry
for which the compiler adds padding so the size of the struct is a
multiple of 32-bit. And since I'm not sure every compiler does that,
I had to do it this way. (And adding a -2 magic number doesn't seem
cleaner to me eiter)

> > +
> > +		crc = crc32(0, (Bytef*)(mmap + dir_offset), data_len);
> > +		filecrc = mmap + dir_offset + data_len;
> > +		if (crc != ntoh_l(*filecrc))
> > +			goto unmap;
> 
> The CRC checking code in general is a bit noisy on my eyes, increasing
> the risk that I would miss a mistake in one of the calls.  I wonder if
> you could refactor it as something like
> 
>   static int check_crc32_chunk(void *data, size_t len, unsigned int expected_crc);
> 
> Then again the pointer math would still be on the caller side.  Sigh.

Yes, that makes sense, I changed it.

> > +
> > +		dir_offset += data_len + 4; /* crc code */
> > +	}
> > +
> > +	return entries;
> > +unmap:
> > +	munmap(mmap, mmap_size);
> > +	errno = EINVAL;
> > +	die("directory crc doesn't match for '%s'", current->pathname);
> > +}
> 
> I can see there's precedent for this in read_index_v2 (as of your patch;
> it used to be in read_index_from); but what's the point of setting errno
> immediately before not using it and exiting?

I just copy and pasted it from there, but thinking about it id doesn't
make sense.

> That's all for today.  Thanks for reading.

Thanks a lot for reviewing my code.

--
Thomas