{"thread":{"id":"30644","subject":"[GSoC] Designing a faster index format - Progress report week 6","startedAt":"2012-05-28T21:44:01Z","lastAt":"2012-06-01T14:49:02Z","messageCount":5,"participants":["Thomas Gummerer","Thomas Rast","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"192403","messageId":"20120528214401.GB6449@tgummerer","threadId":"30644","inReplyTo":null,"subject":"[GSoC] Designing a faster index format - Progress report week 6","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-28T21:44:01Z","receivedAt":"2012-05-28T21:44:01Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"Here is another quick overview of the current progress of my\nGoogle Summer of Code project. I'm currently planning to do\nthose weekly, to keep you up to date with the progress.\n\n== Work done in the previous 5 weeks ==\n\n- Definition of a tentative index file v5 format [1]. This differs\n  from the proposal in making it possible to bisect the directory\n  entries and file entries, to do a binary search. The exact bits\n  for each section were also defined. To further compress the index,\n  along with prefix compression, the stat data is hashed, since\n  it's only used for comparison, but the plain data is never used.\n  Thanks to Michael Haggerty, Nguyen Thai Ngoc Duy, Thomas Rast\n  and Robin Rosenberg for feedback.\n- Prototype of a converter from the index format v2/v3 to the index\n  format v5. [2] The converter reads the index from a git repository,\n  can output parts of the index (header, index entries as in\n  git ls-files --debug, cache tree as in test-dump-cache-tree, or\n  the reuc data). Then it writes the v5 index file format to\n  .git/index-v5. Thanks to Michael Haggerty for the code review.\n- Prototype of a reader for the new index file format. [3] The\n  reader has mainly the purpose to show the algorithm used to read\n  the index lexicographically sorted after the full name which is\n  required by the current internal memory format. Big thanks for\n  reviewing this code and giving me advice on refactoring goes\n  to Michael Haggerty.\n\n== Work done in the last week ==\n\n- Started working on the actual git code. Git is now able to read\n  the index format v5, although the mapping of the new ondisk\n  format to the internal format is not done yet. The latest code\n  is not pushed to github yet, since it still needs some polishing,\n  but if anyone is interested in the general direction it's going,\n  the initial steps are on github. [4] Thanks for reviewing the\n  first steps to Thomas Rast.\n\n== Outlook for the next week ==\n\n- Refactoring of the read_index_v5 code, and possibly mapping of\n  the read index to the current internal format (If there's enough\n  time)\n- Make git ls-files read the new index format directly, to show\n  some of its advantages. (Thanks to Nguyen Thai Ngoc Duy, and\n  Junio C Hamano for the suggestion)\n\n[1] https://github.com/tgummerer/git/wiki/Index-file-format-v5\n[2] https://github.com/tgummerer/git/blob/pythonprototype/git-convert-index.py\n[3] https://github.com/tgummerer/git/blob/pythonprototype/git-read-index-v5.py\n[4] https://github.com/tgummerer/git/tree/index-v5\n"},{"id":"192599","messageId":"87pq9k8i4e.fsf@thomas.inf.ethz.ch","threadId":"30644","inReplyTo":"20120528214401.GB6449@tgummerer","subject":"Review of current github code [Re: [GSoC] Designing a faster index format - Progress report week 6]","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-05-31T15:50:25Z","receivedAt":"2012-05-31T15:50:25Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Hi,\n\nThomas has again been busy hacking, and the reading side is now capable\nof reading a v5 index into the (existing) array-of-cache_entry format.\nIt is actually already measurably faster than both v4 and v[23] on the\nWebkit index:\n\n  Test                      this tree      \n  -----------------------------------------\n  0002.1: v[23]: ls-files   0.13(0.11+0.02)\n  0002.4: v4: ls-files      0.11(0.08+0.02)\n  0002.5: v5: ls-files      0.09(0.06+0.02)\n\nI made up a hacky perf script on the spot, it's pasted at the far end of\nthis email.  It would most likely still be slower than v4 if we didn't\nswitch away from SHA1, though -- we haven't really spent much time\nlooking into the speed, except for one particular avoidance of name\ncopies that translated into a roughly 30% speedup.\n\nAs before, what follows is a review of the WIP code on github at\n\n  git://github.com/tgummerer/git.git index-v5\n\nI looked at version fed977b, however I will pretend it consists of just\ntwo commits (as far as the C code is concerned):\n\n* (174fea4) Refactoring to accomodate other index versions\n* All others (174fea4..fed977b), squashed\n\nI'm doing this because the history is still not in \"submission-style\"\nshape, as discussed in\n\n  http://thread.gmane.org/gmane.comp.version-control.git/198283/focus=198412\n\nand Junio's reply to it.\n\n\nAs far as 174fea4 goes: I think you could split it into two separate\ncommits, one for the code movement (i.e., refactoring of a large chunk\nof read_index_from into read_index_v2_from), and a second one for the\nintroduction of the separate header struct.  Other than that it looks\ngood.\n\n\nThe rest would look like this:\n\n>  cache.h                |  32 ++++-\n>  read-cache.c           | 315 ++++++++++++++++++++++++++++++++++++++++++++++---\n>  5 files changed, 334 insertions(+), 29 deletions(-)\n\nThe review follows, though note that as usual I have snipped all hunks\nwhere I didn't have anything to add:\n\n> @@ -108,6 +108,13 @@ struct cache_header_v2 {\n>  \tunsigned int hdr_entries;\n>  };\n>  \n> +struct cache_header_v5 {\n> +\tunsigned int hdr_ndir;\n> +\tunsigned int hdr_nfile;\n> +\tunsigned int hdr_fblockoffset;\n> +\tunsigned int hdr_nextension;\n> +};\n> +\n>  #define INDEX_FORMAT_LB 2\n>  #define INDEX_FORMAT_UB 4\n\nSomewhat confusingly, the non-update to INDEX_FORMAT_UB is correct since\nthat is only used by git-update-index to verify that a user request for\nthe *write* format is valid, and we don't currently support writing v5.\n\n> @@ -132,11 +139,27 @@ struct cache_entry {\n>  \tunsigned int ce_size;\n>  \tunsigned int ce_flags;\n>  \tunsigned char sha1[20];\n> +\tint ce_stat_crc;\n\nThis should probably be an unsigned int for correctness.  The docs for\nzlib actually say it has type 'uLong', whatever that might mean.  Don't\nturn it into an unsigned long though, that would be 64 bits at least on\nx86_64 Linux.\n\n> +\tunsigned int ce_namelen;\n\nYou are using this to hack around the issue that we dropped the name\nlength out of the flags to save bits.  Perhaps it would be a nice\ncleanup to keep it in the struct \"in the open\", instead of having the\nodd ce_namelen() wrapper that amounts to a maybe-strlen.\n\n> +struct directory_entry {\n> +\tunsigned short de_flags;\n> +\tunsigned int de_foffset;\n> +\tunsigned int de_cr;\n> +\tunsigned int de_ncr;\n> +\tunsigned int de_nsubtrees;\n> +\tunsigned int de_nfiles;\n> +\tunsigned int de_nentries;\n> +\tunsigned char sha1[20];\n> +\tstruct directory_entry *next;\n> +\tunsigned int de_pathlen;\n> +\tchar pathname[FLEX_ARRAY];\n> +};\n\nWhy are the flags out of order compared to the on-disk layout?\n\nAlso, if you make a linked list it would be more natural (to me) to put\nthe 'next' member at the top.  I suspect the precedent in 'cache_entry'\nmay be from times where that was the ondisk layout, and thus any\nnot-on-disk entries had to be at the end.  Perhaps Junio can clarify\nthis.\n\n> -extern void read_index_v2_from(struct index_state *, struct stat, void *mmap, int);\n> +extern void read_index_v2(struct index_state *, struct stat, void *mmap, int);\n> +extern void read_index_v5(struct index_state *, struct stat, void *mmap, int);\n\nYou should make up your mind in the refactoring patch ;-)\n\n> diff --git a/read-cache.c b/read-cache.c\n> index 750fbfa..fc8033a 100644\n> --- a/read-cache.c\n> +++ b/read-cache.c\n> @@ -397,8 +397,9 @@ int df_name_compare(const char *name1, int len1, int mode1,\n>  \n>  int cache_name_compare(const char *name1, int flags1, const char *name2, int flags2)\n>  {\n> -\tint len1 = flags1 & CE_NAMEMASK;\n> -\tint len2 = flags2 & CE_NAMEMASK;\n> +\t/* TODO: This possibly can be replaced with something faster */\n> +\tint len1 = strlen(name1);\n> +\tint len2 = strlen(name2);\n>  \tint len = len1 < len2 ? len1 : len2;\n>  \tint cmp;\n\nNow that you have the ce_namelen entry, shouldn't you use that here?\n\nIf it is not filled in correctly by the other readers, you'd have to\npatch them, preferably in an earlier patch where you introduce this\nfield (only -- not doing any v5 work yet).\n\n> +static int verify_hdr_v5(void *mmap)\n> +{\n> +\tuint32_t crc;\n> +\tuint32_t* filecrc;\n> +\tunsigned int header_size_v5;\n> +\tstruct cache_version_header *hdr;\n> +\tstruct cache_header_v5 *hdr_v5;\n> +\n> +\thdr = mmap;\n> +\thdr_v5 = mmap + sizeof(*hdr);\n> +\t/* Size of the header + the size of the extensionoffsets */\n> +\theader_size_v5 = sizeof(*hdr_v5) + hdr_v5->hdr_nextension * 4;\n> +\t/* Initialize crc */\n> +\tcrc = crc32(0, (Bytef*)hdr, sizeof(*hdr));\n> +\tcrc = crc32(crc, (Bytef*)hdr_v5, header_size_v5);\n\nCan't you crc32() this block in one go?\n\n> +\tfilecrc = mmap + sizeof(*hdr) + header_size_v5;\n> +\tif (crc != ntohl(*filecrc))\n> +\t\treturn error(\"bad index file header crc signature\");\n> +\treturn 0;\n> +}\n> +\n>  static int read_index_extension(struct index_state *istate,\n>  \t\t\t\tconst char *ext, void *data, unsigned long sz)\n>  {\n> @@ -1315,23 +1361,71 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on\n>  {\n>  \tstruct cache_entry *ce = xmalloc(cache_entry_size(len));\n>  \n> -\tce->ce_ctime.sec = ntoh_l(ondisk->ctime.sec);\n> -\tce->ce_mtime.sec = ntoh_l(ondisk->mtime.sec);\n> +\tce->ce_ctime.sec  = ntoh_l(ondisk->ctime.sec);\n> +\tce->ce_mtime.sec  = ntoh_l(ondisk->mtime.sec);\n>  \tce->ce_ctime.nsec = ntoh_l(ondisk->ctime.nsec);\n>  \tce->ce_mtime.nsec = ntoh_l(ondisk->mtime.nsec);\n> -\tce->ce_dev   = ntoh_l(ondisk->dev);\n> -\tce->ce_ino   = ntoh_l(ondisk->ino);\n> -\tce->ce_mode  = ntoh_l(ondisk->mode);\n> -\tce->ce_uid   = ntoh_l(ondisk->uid);\n> -\tce->ce_gid   = ntoh_l(ondisk->gid);\n> -\tce->ce_size  = ntoh_l(ondisk->size);\n> -\tce->ce_flags = flags;\n> +\tce->ce_dev        = ntoh_l(ondisk->dev);\n> +\tce->ce_ino        = ntoh_l(ondisk->ino);\n> +\tce->ce_mode       = ntoh_l(ondisk->mode);\n> +\tce->ce_uid        = ntoh_l(ondisk->uid);\n> +\tce->ce_gid        = ntoh_l(ondisk->gid);\n> +\tce->ce_size       = ntoh_l(ondisk->size);\n> +\tce->ce_flags      = flags;\n> +\tce->ce_namelen    = len;\n\nAFAICS all but the last one only change the alignment of the\nassignments.  Only the last addition is a true change, related to the\naddition of the ce_namelen field.  It would be far easier on the\nreviewers if you first did the alignment cleanup (it can then be checked\nto be a no-change patch simply with --ignore-space-change), and then the\nce_namelen, before any v5 work.\n\n> +static struct directory_entry *read_directories_v5(unsigned int dir_offset,\n> +\t\t\t\tunsigned int ndir,\n> +\t\t\t\tvoid *mmap,\n> +\t\t\t\tint mmap_size)\n> +{\n> +\tint i;\n> +\tuint32_t crc;\n> +\tuint32_t* filecrc;\n> +\tstruct directory_entry *entries = NULL;\n> +\tstruct directory_entry *current = NULL;\n> +\n> +\tfor (i = 0; i < ndir; i++) {\n> +\t\tstruct ondisk_directory_entry *disk_de;\n> +\t\tstruct directory_entry *de;\n> +\t\tunsigned int data_len; \n> +\t\tunsigned int len;\n> +\t\tchar *name;\n> +\n> +\t\tname = (char *)mmap + dir_offset;\n> +\t\tlen = strlen(name);\n> +\t\tdisk_de = (struct ondisk_directory_entry *)\n> +\t\t\t\t((char *)mmap + dir_offset + len + 1);\n> +\t\tde = directory_entry_from_ondisk(disk_de, name, len);\n> +\n> +\t\tif (entries == NULL) {\n> +\t\t\tentries = de;\n> +\t\t\tcurrent = de;\n> +\t\t} else {\n> +\t\t\tcurrent->next = de;\n> +\t\t\tcurrent = current->next;\n> +\t\t\tcurrent->next = NULL;\n> +\t\t}\n> +\n> +\t\t/* Length of pathname + nul byte for termination + size of\n> +\t\t * members of ondisk_directory_entry. (Just using the size\n> +\t\t * of the stuct doesn't work, because there may be padding\n> +\t\t * bytes for the struct)\n> +\t\t */\n\nStyle nit: \n\n> +\t\tdata_len = len + 1\n> +\t\t\t+ sizeof(disk_de->flags)\n> +\t\t\t+ sizeof(disk_de->foffset)\n> +\t\t\t+ sizeof(disk_de->cr)\n> +\t\t\t+ sizeof(disk_de->ncr)\n> +\t\t\t+ sizeof(disk_de->nsubtrees)\n> +\t\t\t+ sizeof(disk_de->nfiles)\n> +\t\t\t+ sizeof(disk_de->nentries)\n> +\t\t\t+ sizeof(disk_de->sha1);\n\nHow does this differ from\n\n  data_len = len + 1 + sizeof(struct ondisk_directory_entry);\n\n?\n\n> +\n> +\t\tcrc = crc32(0, (Bytef*)(mmap + dir_offset), data_len);\n> +\t\tfilecrc = mmap + dir_offset + data_len;\n> +\t\tif (crc != ntoh_l(*filecrc))\n> +\t\t\tgoto unmap;\n\nThe CRC checking code in general is a bit noisy on my eyes, increasing\nthe risk that I would miss a mistake in one of the calls.  I wonder if\nyou could refactor it as something like\n\n  static int check_crc32_chunk(void *data, size_t len, unsigned int expected_crc);\n\nThen again the pointer math would still be on the caller side.  Sigh.\n\n> +\n> +\t\tdir_offset += data_len + 4; /* crc code */\n> +\t}\n> +\n> +\treturn entries;\n> +unmap:\n> +\tmunmap(mmap, mmap_size);\n> +\terrno = EINVAL;\n> +\tdie(\"directory crc doesn't match for '%s'\", current->pathname);\n> +}\n\nI can see there's precedent for this in read_index_v2 (as of your patch;\nit used to be in read_index_from); but what's the point of setting errno\nimmediately before not using it and exiting?\n\nThat's all for today.  Thanks for reading.\n\n\n---- t/perf/p0002-index-v5.sh ----\n#!/bin/sh\n\ntest_description=\"Tests index versions [23]/4/5\"\n\n. ./perf-lib.sh\n\ntest_perf_large_repo\n\ntest_perf 'v[23]: ls-files' '\n\tgit ls-files >/dev/null\n'\n\ntest_expect_success 'convert to v5' '\n\t$GIT_BUILD_DIR/git-convert-index.py\n'\n\ntest_expect_success 'convert to v4' '\n\tgit update-index --index-version=4\n'\n\ntest_perf 'v4: ls-files' '\n\tgit ls-files >/dev/null\n'\n\ntest_perf 'v5: ls-files' '\n\tGIT_INDEX_FILE=.git/index-v5 git ls-files >/dev/null\n'\n\ntest_done\n----- t/perf/p0002-index-v5.sh ----\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"192606","messageId":"7vhauw6x0p.fsf@alter.siamese.dyndns.org","threadId":"30644","inReplyTo":"87pq9k8i4e.fsf@thomas.inf.ethz.ch","subject":"Re: Review of current github code [Re: [GSoC] Designing a faster index format - Progress report week 6]","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-31T18:11:34Z","receivedAt":"2012-05-31T18:11:34Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast <trast@student.ethz.ch> writes:\n\n> Thomas has again been busy hacking, and the reading side is now capable\n> of reading a v5 index into the (existing) array-of-cache_entry format.\n> It is actually already measurably faster than both v4 and v[23] on the\n> Webkit index:\n>\n>   Test                      this tree      \n>   -----------------------------------------\n>   0002.1: v[23]: ls-files   0.13(0.11+0.02)\n>   0002.4: v4: ls-files      0.11(0.08+0.02)\n>   0002.5: v5: ls-files      0.09(0.06+0.02)\n>\n> I made up a hacky perf script on the spot, it's pasted at the far end of\n> this email.  It would most likely still be slower than v4 if we didn't\n> switch away from SHA1, though -- we haven't really spent much time\n> looking into the speed, except for one particular avoidance of name\n> copies that translated into a roughly 30% speedup.\n\nDo you mean by \"switch away from SHA-1\" that your suspicion is a\nlarge part of the speed-up may be coming from the fact that the\nindex file as a whole is no longer hashed?\n\nAs long as the new format allows us to notice corruption in the file\nto a similar degree of confidence by some other means, I personally\ndo not see it as a regression in safety.\n\nWe however eventually would need to hook the logic to check for\nindex corruption into fsck.  Actually adding such a code to fsck can\nand probably should remain outside the GSoC project, but please make\nsure you have necessary checksums in the format to allow us to do so\nin the future.\n\nThanks.\n"},{"id":"192655","messageId":"87vcjb1bba.fsf@thomas.inf.ethz.ch","threadId":"30644","inReplyTo":"7vhauw6x0p.fsf@alter.siamese.dyndns.org","subject":"Re: Review of current github code [Re: [GSoC] Designing a faster index format - Progress report week 6]","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-06-01T12:11:37Z","receivedAt":"2012-06-01T12:11:37Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Thomas Rast <trast@student.ethz.ch> writes:\n>\n>>   Test                      this tree      \n>>   -----------------------------------------\n>>   0002.1: v[23]: ls-files   0.13(0.11+0.02)\n>>   0002.4: v4: ls-files      0.11(0.08+0.02)\n>>   0002.5: v5: ls-files      0.09(0.06+0.02)\n>>\n>> I made up a hacky perf script on the spot, it's pasted at the far end of\n>> this email.  It would most likely still be slower than v4 if we didn't\n>> switch away from SHA1, though -- we haven't really spent much time\n>> looking into the speed, except for one particular avoidance of name\n>> copies that translated into a roughly 30% speedup.\n>\n> Do you mean by \"switch away from SHA-1\" that your suspicion is a\n> large part of the speed-up may be coming from the fact that the\n> index file as a whole is no longer hashed?\n\nYes.  Since the v5 index is only slightly smaller than v4 one, the\nreduction in data read cannot explain the difference alone.\n\nI tried to quantify this a little.  For SHA1 and the v2/v4 index\n(25MB/14MB, resp.), I get about 70ms/44ms for\n\n  time git hash-object --stdin <.git/index\n\nOn the other hand I get about 35ms/22ms for\n\n  time ~/g/test-crc32 .git/index\n\nI do have a system crc32 utility, but it uses read() in 8k blocks\ninstead of mmap() and takes about 87ms.\n\nSo we can see that the switch from 25MB to 14MB fully explains the\nspeedup for v2->v4, and the switch from SHA1 to CRC32 explains the\nspeedup for v4->v5.\n\nHowever, aside from gaining 20ms here, CRC32 is also suitable for\nchecking very short chunks of data, as is planned for the partial\nloading support in v5.\n\n> As long as the new format allows us to notice corruption in the file\n> to a similar degree of confidence by some other means, I personally\n> do not see it as a regression in safety.\n> \n> We however eventually would need to hook the logic to check for\n> index corruption into fsck.  Actually adding such a code to fsck can\n> and probably should remain outside the GSoC project, but please make\n> sure you have necessary checksums in the format to allow us to do so\n> in the future.\n\nI actually expect that a full loading of the index will verify all\nchecksums that are present in the file.  Since file additions and such\nwill still need a full rewrite, and thus a full read, I expect this to\nhappen every so often as a matter of normal operations.  fsck could of\ncourse still learn to load the index at some point, for good measure.\n\n\ndiff --git i/Makefile w/Makefile\nindex 63eacda..76856bc 100644\n--- i/Makefile\n+++ w/Makefile\n@@ -481,6 +481,7 @@ X =\n PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS))\n \n TEST_PROGRAMS_NEED_X += test-chmtime\n+TEST_PROGRAMS_NEED_X += test-crc32\n TEST_PROGRAMS_NEED_X += test-credential\n TEST_PROGRAMS_NEED_X += test-ctype\n TEST_PROGRAMS_NEED_X += test-date\ndiff --git i/test-crc32.c w/test-crc32.c\nindex e69de29..092de48 100644\n--- i/test-crc32.c\n+++ w/test-crc32.c\n@@ -0,0 +1,32 @@\n+#include \"git-compat-util.h\"\n+#include <zlib.h>\n+#include <sys/types.h>\n+#include <sys/stat.h>\n+#include <fcntl.h>\n+#include <unistd.h>\n+#include <sys/mman.h>\n+\n+int main (int argc, char *argv[])\n+\n+{\n+\tunsigned int crc;\n+\tstruct stat st;\n+\tint fd;\n+\tvoid *map;\n+\n+\tif (argc != 2)\n+\t\tdie(\"usage: %s <file>\\n\", argv[0]);\n+\tfd = open(argv[1], O_RDONLY);\n+\tif (fd < 0)\n+\t\tdie_errno(\"open\");\n+\tif (fstat(fd, &st) < 0)\n+\t\tdie_errno(\"fstat\");\n+\tmap = mmap(NULL, st.st_size, PROT_READ, MAP_SHARED, fd, 0);\n+\tif (map == MAP_FAILED)\n+\t\tdie_errno(\"mmap\");\n+\n+\tcrc = crc32(0, map, st.st_size);\n+\tprintf(\"%8x\\n\", crc);\n+\n+\treturn 0;\n+}\n\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"192665","messageId":"20120601144902.GG6449@tgummerer","threadId":"30644","inReplyTo":"87pq9k8i4e.fsf@thomas.inf.ethz.ch","subject":"Re: Review of current github code [Re: [GSoC] Designing a faster index format - Progress report week 6]","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-06-01T14:49:02Z","receivedAt":"2012-06-01T14:49:02Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"On 05/31, Thomas Rast wrote:\n> As far as 174fea4 goes: I think you could split it into two separate\n> commits, one for the code movement (i.e., refactoring of a large chunk\n> of read_index_from into read_index_v2_from), and a second one for the\n> introduction of the separate header struct.  Other than that it looks\n> good.\n\nThanks for your review. I rebased the commits now, 174fea4 is now\n5eb9c21 and 946888d. There were also two commits to the python code,\nwhich I moved previous of the refactoring commits. (210d1ff and b99fdf8)\n\n> The rest would look like this:\n> \n> >  cache.h                |  32 ++++-\n> >  read-cache.c           | 315 ++++++++++++++++++++++++++++++++++++++++++++++---\n> >  5 files changed, 334 insertions(+), 29 deletions(-)\n> \n> The review follows, though note that as usual I have snipped all hunks\n> where I didn't have anything to add:\n> \n> > @@ -108,6 +108,13 @@ struct cache_header_v2 {\n> >  \tunsigned int hdr_entries;\n> >  };\n> >  \n> > +struct cache_header_v5 {\n> > +\tunsigned int hdr_ndir;\n> > +\tunsigned int hdr_nfile;\n> > +\tunsigned int hdr_fblockoffset;\n> > +\tunsigned int hdr_nextension;\n> > +};\n> > +\n> >  #define INDEX_FORMAT_LB 2\n> >  #define INDEX_FORMAT_UB 4\n> \n> Somewhat confusingly, the non-update to INDEX_FORMAT_UB is correct since\n> that is only used by git-update-index to verify that a user request for\n> the *write* format is valid, and we don't currently support writing v5.\n\nI left them as they are, since they aren't used in the read code, so I\nthought this would be fine.\n\n> > @@ -132,11 +139,27 @@ struct cache_entry {\n> >  \tunsigned int ce_size;\n> >  \tunsigned int ce_flags;\n> >  \tunsigned char sha1[20];\n> > +\tint ce_stat_crc;\n> \n> This should probably be an unsigned int for correctness.  The docs for\n> zlib actually say it has type 'uLong', whatever that might mean.  Don't\n> turn it into an unsigned long though, that would be 64 bits at least on\n> x86_64 Linux.\n\nI digged a bit in the git code, uint32_t seems to be the right way to\ndo it. (as in csum-file.h) I converted it to that for now.\n\n> > +\tunsigned int ce_namelen;\n> \n> You are using this to hack around the issue that we dropped the name\n> length out of the flags to save bits.  Perhaps it would be a nice\n> cleanup to keep it in the struct \"in the open\", instead of having the\n> odd ce_namelen() wrapper that amounts to a maybe-strlen.\n\nI guess that may better fit in a refactoring patch? I put it in\ne73adcf.\n\n> > +struct directory_entry {\n> > +\tunsigned short de_flags;\n> > +\tunsigned int de_foffset;\n> > +\tunsigned int de_cr;\n> > +\tunsigned int de_ncr;\n> > +\tunsigned int de_nsubtrees;\n> > +\tunsigned int de_nfiles;\n> > +\tunsigned int de_nentries;\n> > +\tunsigned char sha1[20];\n> > +\tstruct directory_entry *next;\n> > +\tunsigned int de_pathlen;\n> > +\tchar pathname[FLEX_ARRAY];\n> > +};\n> \n> Why are the flags out of order compared to the on-disk layout?\n> \n> Also, if you make a linked list it would be more natural (to me) to put\n> the 'next' member at the top.  I suspect the precedent in 'cache_entry'\n> may be from times where that was the ondisk layout, and thus any\n> not-on-disk entries had to be at the end.  Perhaps Junio can clarify\n> this.\n\nThey were in order at the beginning, before I moved the flags to the\nend in the ondisk format, and forgot to move them in the struct. It's\nin order now.\n\nI also moved the next member to the top. I originally put it at the\nend, because it was at the end for the cache_entry too.\n\n> > -extern void read_index_v2_from(struct index_state *, struct stat, void *mmap, int);\n> > +extern void read_index_v2(struct index_state *, struct stat, void *mmap, int);\n> > +extern void read_index_v5(struct index_state *, struct stat, void *mmap, int);\n> \n> You should make up your mind in the refactoring patch ;-)\n\nI thing read_index_v2 makes more sense, since from sounds like we expect\na pathname.\n\n> > diff --git a/read-cache.c b/read-cache.c\n> > index 750fbfa..fc8033a 100644\n> > --- a/read-cache.c\n> > +++ b/read-cache.c\n> > @@ -397,8 +397,9 @@ int df_name_compare(const char *name1, int len1, int mode1,\n> >  \n> >  int cache_name_compare(const char *name1, int flags1, const char *name2, int flags2)\n> >  {\n> > -\tint len1 = flags1 & CE_NAMEMASK;\n> > -\tint len2 = flags2 & CE_NAMEMASK;\n> > +\t/* TODO: This possibly can be replaced with something faster */\n> > +\tint len1 = strlen(name1);\n> > +\tint len2 = strlen(name2);\n> >  \tint len = len1 < len2 ? len1 : len2;\n> >  \tint cmp;\n> \n> Now that you have the ce_namelen entry, shouldn't you use that here?\n> \n> If it is not filled in correctly by the other readers, you'd have to\n> patch them, preferably in an earlier patch where you introduce this\n> field (only -- not doing any v5 work yet).\n\nYes, there would be more patching needed, since the function uses the\nflags too. The patch is not yet in the repository.\n\n> > +static int verify_hdr_v5(void *mmap)\n> > +{\n> > +\tuint32_t crc;\n> > +\tuint32_t* filecrc;\n> > +\tunsigned int header_size_v5;\n> > +\tstruct cache_version_header *hdr;\n> > +\tstruct cache_header_v5 *hdr_v5;\n> > +\n> > +\thdr = mmap;\n> > +\thdr_v5 = mmap + sizeof(*hdr);\n> > +\t/* Size of the header + the size of the extensionoffsets */\n> > +\theader_size_v5 = sizeof(*hdr_v5) + hdr_v5->hdr_nextension * 4;\n> > +\t/* Initialize crc */\n> > +\tcrc = crc32(0, (Bytef*)hdr, sizeof(*hdr));\n> > +\tcrc = crc32(crc, (Bytef*)hdr_v5, header_size_v5);\n> \n> Can't you crc32() this block in one go?\n\nYes, I just thought it's clearer this way, calculating the crc for the\nsignature + version and the rest of the header_v5. I changed it for now\nto one block.\n\n> > +\tfilecrc = mmap + sizeof(*hdr) + header_size_v5;\n> > +\tif (crc != ntohl(*filecrc))\n> > +\t\treturn error(\"bad index file header crc signature\");\n> > +\treturn 0;\n> > +}\n> > +\n> >  static int read_index_extension(struct index_state *istate,\n> >  \t\t\t\tconst char *ext, void *data, unsigned long sz)\n> >  {\n> > @@ -1315,23 +1361,71 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on\n> >  {\n> >  \tstruct cache_entry *ce = xmalloc(cache_entry_size(len));\n> >  \n> > -\tce->ce_ctime.sec = ntoh_l(ondisk->ctime.sec);\n> > -\tce->ce_mtime.sec = ntoh_l(ondisk->mtime.sec);\n> > +\tce->ce_ctime.sec  = ntoh_l(ondisk->ctime.sec);\n> > +\tce->ce_mtime.sec  = ntoh_l(ondisk->mtime.sec);\n> >  \tce->ce_ctime.nsec = ntoh_l(ondisk->ctime.nsec);\n> >  \tce->ce_mtime.nsec = ntoh_l(ondisk->mtime.nsec);\n> > -\tce->ce_dev   = ntoh_l(ondisk->dev);\n> > -\tce->ce_ino   = ntoh_l(ondisk->ino);\n> > -\tce->ce_mode  = ntoh_l(ondisk->mode);\n> > -\tce->ce_uid   = ntoh_l(ondisk->uid);\n> > -\tce->ce_gid   = ntoh_l(ondisk->gid);\n> > -\tce->ce_size  = ntoh_l(ondisk->size);\n> > -\tce->ce_flags = flags;\n> > +\tce->ce_dev        = ntoh_l(ondisk->dev);\n> > +\tce->ce_ino        = ntoh_l(ondisk->ino);\n> > +\tce->ce_mode       = ntoh_l(ondisk->mode);\n> > +\tce->ce_uid        = ntoh_l(ondisk->uid);\n> > +\tce->ce_gid        = ntoh_l(ondisk->gid);\n> > +\tce->ce_size       = ntoh_l(ondisk->size);\n> > +\tce->ce_flags      = flags;\n> > +\tce->ce_namelen    = len;\n> \n> AFAICS all but the last one only change the alignment of the\n> assignments.  Only the last addition is a true change, related to the\n> addition of the ce_namelen field.  It would be far easier on the\n> reviewers if you first did the alignment cleanup (it can then be checked\n> to be a no-change patch simply with --ignore-space-change), and then the\n> ce_namelen, before any v5 work.\n\nOk, this is changed in e73adcf. The alignment is done in bbc8928. Hope\nunderstood the alignment cleanup right.\n\n> > +static struct directory_entry *read_directories_v5(unsigned int dir_offset,\n> > +\t\t\t\tunsigned int ndir,\n> > +\t\t\t\tvoid *mmap,\n> > +\t\t\t\tint mmap_size)\n> > +{\n> > +\tint i;\n> > +\tuint32_t crc;\n> > +\tuint32_t* filecrc;\n> > +\tstruct directory_entry *entries = NULL;\n> > +\tstruct directory_entry *current = NULL;\n> > +\n> > +\tfor (i = 0; i < ndir; i++) {\n> > +\t\tstruct ondisk_directory_entry *disk_de;\n> > +\t\tstruct directory_entry *de;\n> > +\t\tunsigned int data_len; \n> > +\t\tunsigned int len;\n> > +\t\tchar *name;\n> > +\n> > +\t\tname = (char *)mmap + dir_offset;\n> > +\t\tlen = strlen(name);\n> > +\t\tdisk_de = (struct ondisk_directory_entry *)\n> > +\t\t\t\t((char *)mmap + dir_offset + len + 1);\n> > +\t\tde = directory_entry_from_ondisk(disk_de, name, len);\n> > +\n> > +\t\tif (entries == NULL) {\n> > +\t\t\tentries = de;\n> > +\t\t\tcurrent = de;\n> > +\t\t} else {\n> > +\t\t\tcurrent->next = de;\n> > +\t\t\tcurrent = current->next;\n> > +\t\t\tcurrent->next = NULL;\n> > +\t\t}\n> > +\n> > +\t\t/* Length of pathname + nul byte for termination + size of\n> > +\t\t * members of ondisk_directory_entry. (Just using the size\n> > +\t\t * of the stuct doesn't work, because there may be padding\n> > +\t\t * bytes for the struct)\n> > +\t\t */\n> \n> Style nit: \n> \n> > +\t\tdata_len = len + 1\n> > +\t\t\t+ sizeof(disk_de->flags)\n> > +\t\t\t+ sizeof(disk_de->foffset)\n> > +\t\t\t+ sizeof(disk_de->cr)\n> > +\t\t\t+ sizeof(disk_de->ncr)\n> > +\t\t\t+ sizeof(disk_de->nsubtrees)\n> > +\t\t\t+ sizeof(disk_de->nfiles)\n> > +\t\t\t+ sizeof(disk_de->nentries)\n> > +\t\t\t+ sizeof(disk_de->sha1);\n> \n> How does this differ from\n> \n>   data_len = len + 1 + sizeof(struct ondisk_directory_entry);\n> \n> ?\n\nThere is only a single 16-bit entry in struct ondisk_directory_entry\nfor which the compiler adds padding so the size of the struct is a\nmultiple of 32-bit. And since I'm not sure every compiler does that,\nI had to do it this way. (And adding a -2 magic number doesn't seem\ncleaner to me eiter)\n\n> > +\n> > +\t\tcrc = crc32(0, (Bytef*)(mmap + dir_offset), data_len);\n> > +\t\tfilecrc = mmap + dir_offset + data_len;\n> > +\t\tif (crc != ntoh_l(*filecrc))\n> > +\t\t\tgoto unmap;\n> \n> The CRC checking code in general is a bit noisy on my eyes, increasing\n> the risk that I would miss a mistake in one of the calls.  I wonder if\n> you could refactor it as something like\n> \n>   static int check_crc32_chunk(void *data, size_t len, unsigned int expected_crc);\n> \n> Then again the pointer math would still be on the caller side.  Sigh.\n\nYes, that makes sense, I changed it.\n\n> > +\n> > +\t\tdir_offset += data_len + 4; /* crc code */\n> > +\t}\n> > +\n> > +\treturn entries;\n> > +unmap:\n> > +\tmunmap(mmap, mmap_size);\n> > +\terrno = EINVAL;\n> > +\tdie(\"directory crc doesn't match for '%s'\", current->pathname);\n> > +}\n> \n> I can see there's precedent for this in read_index_v2 (as of your patch;\n> it used to be in read_index_from); but what's the point of setting errno\n> immediately before not using it and exiting?\n\nI just copy and pasted it from there, but thinking about it id doesn't\nmake sense.\n\n> That's all for today.  Thanks for reading.\n\nThanks a lot for reviewing my code.\n\n--\nThomas\n"}]}