{"thread":{"id":"30707","subject":"[GSoC] Designing a faster index format - Progress report week 7","startedAt":"2012-06-04T20:07:46Z","lastAt":"2012-06-06T17:31:26Z","messageCount":4,"participants":["Thomas Gummerer","Thomas Rast","Johannes Sixt","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"192843","messageId":"20120604200746.GK6449@tgummerer","threadId":"30707","inReplyTo":null,"subject":"[GSoC] Designing a faster index format - Progress report week 7","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-06-04T20:07:46Z","receivedAt":"2012-06-04T20:07:46Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"== Work done in the previous 6 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- 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== Work done in the last week ==\n\n- Continued working on the git code, which now maps the index to\n  the internal format. This includes reading the conflicted data\n  at the far end of the index. [4]\n\n== Outlook for the next week ==\n\n- Read the cache-tree (convert the directories on the disk to the\n  current in-memory cache-tree structure)\n- Start implementing an API, as it was discussed at [5]\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[5] http://thread.gmane.org/gmane.comp.version-control.git/198283/focus=198474\n"},{"id":"192969","messageId":"87aa0gbwon.fsf@thomas.inf.ethz.ch","threadId":"30707","inReplyTo":"20120604200746.GK6449@tgummerer","subject":"Handling racy entries in the v5 format [Re: [GSoC] Designing a faster index format - Progress report week 7]","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-06-06T09:45:44Z","receivedAt":"2012-06-06T09:45:44Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Hi,\n\nMichael, Thomas and me just had a lengthy discussion on IRC about racy\nentries.  I'll use \"simultaneously\" from the perspective of the\nfilesystem's mtimes; depending on your USE_NSEC, that may mean in the\nsame second, or the same nanosecond.\n\n\nBackground: Racy Entries\n------------------------\n\nThere are two cases of racy index entries:\n\n(A)  echo foo >foo\n     git add foo\n     echo bar >foo\n\nIf the latter two commands happen simultaneously, lstat() will match the\nindex entry.  Git handles this by checking foo.mtime >= index.mtime, and\nif so, doing a content check.  Such entries are called racy.\n\n(B) echo foo >foo\n    git add foo     # (i)\n    echo bar >foo\n    sleep 2\n    : >dummy\n    git add dummy   # (ii)\n\nIf the commands before the sleep happen simultaneously, then foo.mtime\nhas not changed since (i), but due to (ii) index.mtime has, defeating\nthe raciness check.  To handle this, git checks for racy entries\n*w.r.t. the old index* immediately before it writes a new index.  For\nall[1] such entries it does a content check.  All racy entries found to\nbe modified get ce_size=0, which tells the next git that \"we know they\nare modified\".  We call them \"smudged\".\n\n\nThe Problem\n-----------\n\nThe use of ce_size=0 is a problem for index v5.  The current drafts\nexclude the size field, instead wrapping it in stat_crc along with most\nof the other stat fields.\n\nThere are some obvious solutions:\n\n* Put the size field back, costing us 4B/entry.\n\n* Use some other marker field for the v5 format, e.g., the stat crc.\n\nNeither of these is good, for an entirely different reason: The current\nscheme checks *all* entries for being racy w.r.t. the old index, before\nany write.  This completely defeats the point of index v5: *avoid*\nloading the entire index for small changes.\n\n\nProposed Solution\n-----------------\n\n(Michael, we have adapted it somewhat this since you left IRC.)\n\n  When writing an entry: check whether ce_mtime >= index.mtime.  If so,\n  write out ce_mtime=0.\n\nThe index.mtime here is a lower bound on the mtime of the new index,\nobtained e.g. by touching the index and then stat()ing it immediately\nbefore writing out the changed entries.\n\nNote that this is a fundamentally different approach from the one taken\nin v[2-4] indexes.  In the old approach, it is the *next* writer's\nresponsibility to ensure that all racy entries are either truly clean,\nor smudged (since they will presumably lose their raciness).  In the new\napproach, racy entries are immediately smudged and remain so until an\nupdate.\n\n\n\nFootnotes: \n[1]  Ignoring the case where st_size==0 at the beginning, which needs\nsome arguing around because st_size is also the smudge marker.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"192981","messageId":"4FCF548E.8060708@viscovery.net","threadId":"30707","inReplyTo":"87aa0gbwon.fsf@thomas.inf.ethz.ch","subject":"Re: Handling racy entries in the v5 format [Re: [GSoC] Designing a faster index format - Progress report week 7]","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2012-06-06T13:01:02Z","receivedAt":"2012-06-06T13:01:02Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 6/6/2012 11:45, schrieb Thomas Rast:\n> Proposed Solution\n> -----------------\n> \n>   When writing an entry: check whether ce_mtime >= index.mtime.  If so,\n>   write out ce_mtime=0.\n> \n> The index.mtime here is a lower bound on the mtime of the new index,\n> obtained e.g. by touching the index and then stat()ing it immediately\n> before writing out the changed entries.\n\nPortability note: To \"touch\" on Windows will mean that the file is\nmodified (at least one byte is written), then closed. Only then the stat\ninformation is reliable. The reason is that the time stamp is only valid\nafter (the last handle of) the file was closed.\n\n> Note that this is a fundamentally different approach from the one taken\n> in v[2-4] indexes.  In the old approach, it is the *next* writer's\n> responsibility to ensure that all racy entries are either truly clean,\n> or smudged (since they will presumably lose their raciness).  In the new\n> approach, racy entries are immediately smudged and remain so until an\n> update.\n\n-- Hannes\n"},{"id":"192999","messageId":"7vk3zkmjo1.fsf@alter.siamese.dyndns.org","threadId":"30707","inReplyTo":"87aa0gbwon.fsf@thomas.inf.ethz.ch","subject":"Re: Handling racy entries in the v5 format [Re: [GSoC] Designing a faster index format - Progress report week 7]","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-06-06T17:31:26Z","receivedAt":"2012-06-06T17:31:26Z","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> (Michael, we have adapted it somewhat this since you left IRC.)\n>\n>   When writing an entry: check whether ce_mtime >= index.mtime.  If so,\n>   write out ce_mtime=0.\n>\n> The index.mtime here is a lower bound on the mtime of the new index,\n> obtained e.g. by touching the index and then stat()ing it immediately\n> before writing out the changed entries.\n\nIs this even workable?  I found that \"open, read a byte, write it\nback in place, then stat\" was not giving useful timestamp and that\nwas the reason the original racy-git code chose not to do this.\n\nYou may be able to do \"open, read a byte, write it back in place,\nfsync, close and then stat\", but doing so while holding that file\nalso as a lock feels somewhat dirty...\n"}]}