{"thread":{"id":"11730","subject":"btrfs and git-reflog","startedAt":"2008-01-25T08:15:26Z","lastAt":"2008-01-27T08:08:59Z","messageCount":10,"participants":["Paul Collins","Chris Mason","Linus Torvalds","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"66545","messageId":"873asmcodd.fsf@burly.wgtn.ondioline.org","threadId":"11730","inReplyTo":null,"subject":"btrfs and git-reflog","fromName":"Paul Collins","fromEmail":"paul@burly.ondioline.org","sentAt":"2008-01-25T08:15:26Z","receivedAt":"2008-01-25T08:15:26Z","isPatch":false,"sender":{"key":"paul@burly.ondioline.org","avatar":null},"body":"I was just playing with git 1.5.3.8 and btrfs 0.11, and I noticed\nsomething odd.\n\nIf I prepare a very simple repository:\n\n $ mkdir foo\n $ cd foo\n $ git init\n Initialized empty Git repository in .git/\n $ echo hi > blort\n $ git add .\n $ git commit -m create\n Created initial commit 4ae9415: create\n 1 files changed, 1 insertions(+), 0 deletions(-)\n create mode 100644 blort\n\nand then attempt to expire the reflogs\n\n $ git-reflog --expire --all\n\non ext3, git-reflog completes its work and exits immediately;\n\nand on btrfs, it gets stuck in some sort of loop that causes it to\nallocate more and more memory until I kill it or it pushes the\nmachine into OOM.\n\nKernel is 2.6.24 or so on x86-64.\n\n-- \nPaul Collins\nWellington, New Zealand\n\nDag vijandelijk luchtschip de huismeester is dood\n"},{"id":"66552","messageId":"87tzl2b5ef.fsf@burly.wgtn.ondioline.org","threadId":"11730","inReplyTo":"873asmcodd.fsf@burly.wgtn.ondioline.org","subject":"Re: btrfs and git-reflog","fromName":"Paul Collins","fromEmail":"paul@burly.ondioline.org","sentAt":"2008-01-25T09:50:32Z","receivedAt":"2008-01-25T09:50:32Z","isPatch":false,"sender":{"key":"paul@burly.ondioline.org","avatar":null},"body":"Correction.\n\nPaul Collins writes:\n\n> and then attempt to expire the reflogs\n>\n> $ git-reflog --expire --all\n\n $ git-reflog expire --all\n\n-- \nPaul Collins\nWellington, New Zealand\n\nDag vijandelijk luchtschip de huismeester is dood\n"},{"id":"66570","messageId":"200801251001.23462.chris.mason@oracle.com","threadId":"11730","inReplyTo":"873asmcodd.fsf@burly.wgtn.ondioline.org","subject":"Re: [Btrfs-devel] btrfs and git-reflog","fromName":"Chris Mason","fromEmail":"chris.mason@oracle.com","sentAt":"2008-01-25T15:01:23Z","receivedAt":"2008-01-25T15:01:23Z","isPatch":false,"sender":{"key":"chris.mason@oracle.com","avatar":null},"body":"On Friday 25 January 2008, Paul Collins wrote:\n> I was just playing with git 1.5.3.8 and btrfs 0.11, and I noticed\n> something odd.\n>\n> If I prepare a very simple repository:\n>\n> $ mkdir foo\n> $ cd foo\n> $ git init\n> Initialized empty Git repository in .git/\n> $ echo hi > blort\n> $ git add .\n> $ git commit -m create\n> Created initial commit 4ae9415: create\n> 1 files changed, 1 insertions(+), 0 deletions(-)\n> create mode 100644 blort\n>\n> and then attempt to expire the reflogs\n>\n> $ git-reflog --expire --all\n>\n> on ext3, git-reflog completes its work and exits immediately;\n\nStrange, but I can reproduce here. I'll take a look, thanks for this report.\n\n-chris\n"},{"id":"66573","messageId":"200801251050.16697.chris.mason@oracle.com","threadId":"11730","inReplyTo":"873asmcodd.fsf@burly.wgtn.ondioline.org","subject":"Re: [Btrfs-devel] btrfs and git-reflog","fromName":"Chris Mason","fromEmail":"chris.mason@oracle.com","sentAt":"2008-01-25T15:50:16Z","receivedAt":"2008-01-25T15:50:16Z","isPatch":false,"sender":{"key":"chris.mason@oracle.com","avatar":null},"body":"On Friday 25 January 2008, Paul Collins wrote:\n> I was just playing with git 1.5.3.8 and btrfs 0.11, and I noticed\n> something odd.\n>\n> If I prepare a very simple repository:\n>\n> $ mkdir foo\n> $ cd foo\n> $ git init\n> Initialized empty Git repository in .git/\n> $ echo hi > blort\n> $ git add .\n> $ git commit -m create\n> Created initial commit 4ae9415: create\n> 1 files changed, 1 insertions(+), 0 deletions(-)\n> create mode 100644 blort\n>\n> and then attempt to expire the reflogs\n>\n> $ git-reflog expire --all\n>\n> on ext3, git-reflog completes its work and exits immediately;\n>\n> and on btrfs, it gets stuck in some sort of loop that causes it to\n> allocate more and more memory until I kill it or it pushes the\n> machine into OOM.\n>\nIt works something like this:\n\nreaddir(.git/logs/refs/heads)\n# this returns .git/logs/refs/heads/master\n# \n\nopen(.git/logs/refs/heads/master.lock, O_CREAT);\n# , write to master.lock\n\nrename(master.lock, master)\n\nreaddir(.git/logs/refs/heads)\n\nreaddir again returns .git/logs/refs/heads/master, which is arguably\ncorrect. It is a new file that just happens to have a name\nthat git already saw. So, git loops over this file infinitely because\nit doesn't realize it has already processed it.\n\nThis happens because btrfs doesn't return the hash of the\nfile name as the offset to readdir. It returns the inode number,\nand since master is a new file, btrfs considers it a non-duplicate\nentry.\n\nThe btrfs patch below changes my readdir code to force the\ndirectory f_pos field to the max offset allowed when we've\nseen all the directory entries. This prevents the readdir\ncall from looping forever in the face of newly added files.\n\nBut, git might want to add some checks to see if it has\nalready processed things.\n\ndiff -r 21e9b461f802 inode.c\n--- a/inode.c\tThu Jan 24 16:13:14 2008 -0500\n+++ b/inode.c\tFri Jan 25 10:28:49 2008 -0500\n@@ -1430,7 +1431,7 @@ read_dir_items:\n \t\t\tdi = (struct btrfs_dir_item *)((char *)di + di_len);\n \t\t}\n \t}\n-\tfilp->f_pos++;\n+\tfilp->f_pos = INT_LIMIT(typeof(filp->f_pos));\n nopos:\n \tret = 0;\n err:\n"},{"id":"66578","messageId":"alpine.LFD.1.00.0801250905570.14161@hp.linux-foundation.org","threadId":"11730","inReplyTo":"200801251050.16697.chris.mason@oracle.com","subject":"Re: [Btrfs-devel] btrfs and git-reflog","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-25T17:09:05Z","receivedAt":"2008-01-25T17:09:05Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 25 Jan 2008, Chris Mason wrote:\n> \n> The btrfs patch below changes my readdir code to force the\n> directory f_pos field to the max offset allowed when we've\n> seen all the directory entries. This prevents the readdir\n> call from looping forever in the face of newly added files.\n\nI think such a change may be sensible if we also taught the Linux VFS \nlayer about it (so that we could avoid the costly parts of readdir() \ngetting a semaphore etc the next call), but in this particular format it's \njust an ugly hack for what is a git bug.\n\n> But, git might want to add some checks to see if it has\n> already processed things.\n\nYes indeed. This is clearly git mis-using \"readdir()\", and should be \nfixed. It could happen on other filesystems, and very much including ones \nwhere there is no option of just \"fixing\" the filesystem (including \nLinux: not everybody can upgrade their kernels just because git makes \nsome broken assumptions).\n\n\t\tLinus\n"},{"id":"66592","messageId":"7vmyqt657t.fsf@gitster.siamese.dyndns.org","threadId":"11730","inReplyTo":"alpine.LFD.1.00.0801250905570.14161@hp.linux-foundation.org","subject":"Re: [Btrfs-devel] btrfs and git-reflog","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-25T20:05:42Z","receivedAt":"2008-01-25T20:05:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Yes indeed. This is clearly git mis-using \"readdir()\", and should be \n> fixed. It could happen on other filesystems, and very much including ones \n> where there is no option of just \"fixing\" the filesystem (including \n> Linux: not everybody can upgrade their kernels just because git makes \n> some broken assumptions).\n\nI agree that this is a broken assumption on git's part. When we\nhave this loop:\n\n\twhile (ent = readdir()) {\n \t... do something in that directory ...\n\t}\n\nwe should expect readdir() may return new entries and cope with\nit, as \"If a file is removed from or added to the directory\nafter the most recent call to opendir() or rewinddir(), whether\na subsequent call to readdir() returns an entry for that file is\nunspecified.\" [*1*]\n\nThe modification may not be done by us, but by \"git push\" from\nelsewhere to update an existing ref, which can run while we are\ninside this loop.\n\nFor this particular case, I think keeping track of what we have\nalready dealt with and skipping when we see duplicates is a good\nenough solution. Removal of a loose ref is protected by taking\na lock on the packed-refs file, so we shouldn't have to worry\nabout races between pack-refs and a push to delete a ref (IOW,\nit won't be an issue that readdir(3) may report a file that is\nremovd by simultaneous git-push).\n\nHowever, I am not sure if the way delete_ref() takes locks (one\nfor the ref itself and another for packed-refs file) is\ndeadlock-free. That may need an independent fix if there is; I\nhaven't closely looked at this.\n\nI suspect we might want to change the current \".lock\" suffix to\nsomething that would make the lock filenames an invalid ref\n(e.g., \"..lock\", or \"~\"), so that people can use \"foo.lock\" as a\nbranch name. That is also outside of the scope of readdir(3)\nabuse fix, though.\n\n\n[Reference]\n\n*1* http://www.opengroup.org/onlinepubs/000095399/functions/readdir.html\n"},{"id":"66622","messageId":"7v7ihx2fdb.fsf@gitster.siamese.dyndns.org","threadId":"11730","inReplyTo":"7vmyqt657t.fsf@gitster.siamese.dyndns.org","subject":"Re: [Btrfs-devel] btrfs and git-reflog","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-26T07:52:16Z","receivedAt":"2008-01-26T07:52:16Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> I agree that this is a broken assumption on git's part. When we\n> have this loop:\n>\n> \twhile (ent = readdir()) {\n> \t... do something in that directory ...\n> \t}\n>\n> we should expect readdir() may return new entries and cope with\n> it, as \"If a file is removed from or added to the directory\n> after the most recent call to opendir() or rewinddir(), whether\n> a subsequent call to readdir() returns an entry for that file is\n> unspecified.\" [*1*]\n\nHere is a result of a mini-audit.\n\n* builtin-prune-packed.c::prune_dir() loops and unlinks (some\n of) returned paths while in the loop. This should not\n interfere with readdir(3). I am presuming that we can declare\n readdir(3) implementation buggy if this happens:\n\n\t* opendir();\n\t* readdir() gives $P;\n * unlink($P);\n * readdir() later gives $P again.\n\n Otherwise we need to lose check for return value from\n unlink().\n\n* builtin-prune.c::prune_dir() has a similar construct and the\n same (non-)issue.\n\n* dir.c::remove_dir_recursively() -- likewise.\n\n* entry.c::remove_subtree() -- likewise. We might want to unify\n this with the previous one.\n\nA patch to \"reflog-expire --all\" will follow in a separate\nmessage.\n"},{"id":"66623","messageId":"7v63xh2fby.fsf_-_@gitster.siamese.dyndns.org","threadId":"11730","inReplyTo":"7vmyqt657t.fsf@gitster.siamese.dyndns.org","subject":"reflog-expire: Avoid creating new files in a directory inside readdir(3) loop","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-26T07:53:05Z","receivedAt":"2008-01-26T07:53:05Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"git reflog expire --all\" opened a directory in $GIT_DIR/logs/,\nread reflog files in there readdir(3), and rewrote the file by\ncreating a new file and renaming it back inside the loop. This\ncode structure can cause the newly created file to be returned\nby subsequent call to readdir(3), and fall into an infinite loop\nin the worst case.\n\nThis separates the processing to two phase. Running\nfor_each_reflog() to find out and collect all refs, and then\niterate over them, calling expire_reflog(). This way, the\nprogram would behave exactly the same way as if all the refs\nwere given by the user from the command line.\n\nSigned-off-by: Junio C Hamano \n---\n\n builtin-reflog.c | 40 ++++++++++++++++++++++++++++++++++++++--\n 1 files changed, 38 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin-reflog.c b/builtin-reflog.c\nindex ce093ca..e6834dd 100644\n--- a/builtin-reflog.c\n+++ b/builtin-reflog.c\n@@ -34,6 +34,16 @@ struct expire_reflog_cb {\n \tstruct cmd_reflog_expire_cb *cmd;\n };\n \n+struct collected_reflog {\n+\tunsigned char sha1[20];\n+\tchar reflog[FLEX_ARRAY];\n+};\n+struct collect_reflog_cb {\n+\tstruct collected_reflog **e;\n+\tint alloc;\n+\tint nr;\n+};\n+\n #define INCOMPLETE\t(1u<<10)\n #define STUDYING\t(1u<<11)\n \n@@ -281,6 +291,20 @@ static int expire_reflog(const char *ref, const unsigned char *sha1, int unused,\n \treturn status;\n }\n \n+static int collect_reflog(const char *ref, const unsigned char *sha1, int unused, void *cb_data)\n+{\n+\tstruct collected_reflog *e;\n+\tstruct collect_reflog_cb *cb = cb_data;\n+\tsize_t namelen = strlen(ref);\n+\n+\te = xmalloc(sizeof(*e) + namelen + 1);\n+\thashcpy(e->sha1, sha1);\n+\tmemcpy(e->reflog, ref, namelen + 1);\n+\tALLOC_GROW(cb->e, cb->nr + 1, cb->alloc);\n+\tcb->e[cb->nr++] = e;\n+\treturn 0;\n+}\n+\n static int reflog_expire_config(const char *var, const char *value)\n {\n \tif (!strcmp(var, \"gc.reflogexpire\"))\n@@ -349,8 +373,20 @@ static int cmd_reflog_expire(int argc, const char **argv, const char *prefix)\n \t\t\tputchar('\\n');\n \t}\n \n-\tif (do_all)\n-\t\tstatus |= for_each_reflog(expire_reflog, &cb);\n+\tif (do_all) {\n+\t\tstruct collect_reflog_cb collected;\n+\t\tint i;\n+\n+\t\tmemset(&collected, 0, sizeof(collected));\n+\t\tfor_each_reflog(collect_reflog, &collected);\n+\t\tfor (i = 0; i < collected.nr; i++) {\n+\t\t\tstruct collected_reflog *e = collected.e[i];\n+\t\t\tstatus |= expire_reflog(e->reflog, e->sha1, 0, &cb);\n+\t\t\tfree(e);\n+\t\t}\n+\t\tfree(collected.e);\n+\t}\n+\n \twhile (i < argc) {\n \t\tconst char *ref = argv[i++];\n \t\tunsigned char sha1[20];\n"},{"id":"66665","messageId":"alpine.LFD.1.00.0801262314360.3222@www.l.google.com","threadId":"11730","inReplyTo":"7v7ihx2fdb.fsf@gitster.siamese.dyndns.org","subject":"Re: [Btrfs-devel] btrfs and git-reflog","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-27T07:22:32Z","receivedAt":"2008-01-27T07:22:32Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 25 Jan 2008, Junio C Hamano wrote:\n> \n> * builtin-prune-packed.c::prune_dir() loops and unlinks (some\n> of) returned paths while in the loop. This should not\n> interfere with readdir(3).\n\nCorrect. The \"loop and unlink\" behaviour is common and accepted practice, \nand is, for example, what things like \"rm -rf\" tend to do. \n\nIt's only newly created files that may or may not show up in readdir() \nafter they've been created, regardless of whether they were created under \na name that was previously existed.\n\n> I am presuming that we can declare\n> readdir(3) implementation buggy if this happens:\n> \n> \t* opendir();\n> \t* readdir() gives $P;\n> * unlink($P);\n> * readdir() later gives $P again.\n\nYes, but the potential problem is actually very different:\n\n - directory contains 'a', 'b' and 'c'\n\n\t* opendir()\n\t* readdir() returns 'a'\n\t * unlink('a');\n\t* readdir() returns 'c', having skipped 'b'.\n\nThis is something that could in theory happen if a directory is indexed \nusing the *position* of a filename in a directory. 'a' was position 1, 'b' \nwas position 2, and 'c' was position 3. After the first readdir(), the \nfile position was 2 (pointing at 'b'), but when we removed 'a', the other \nentries positions moved down, and now 'b' is at position 1, and 'c' is at \nposition '2'. When we call readdir() the next time, it skips 'b' (because \nit already returned position 1!), and returns 'c'.\n\nSee? It's basically the issue of removing an entry in a linked list. And \nyes, we've actually had bugs like that in our in-memory tmpfs. But they \nwere bugs, and they got fixed, and that's not how readdir() is supposed to \nwork, exactly because it makes doing an \"rm -rf\" very hard.\n\nSo readdir() should basically be safe wrt 'unlink()' happening while the \nreaddir() is running, and the only entry that can disappear is the one \nthat is unlinekd.\n\nSo don't worry about unlink's, it's only new files being created in the \nsame directory that can be problematic in that you don't know if \nreaddir() will return them or not..\n\n\t\tLinus\n"},{"id":"66666","messageId":"7vprvny9k4.fsf@gitster.siamese.dyndns.org","threadId":"11730","inReplyTo":"alpine.LFD.1.00.0801262314360.3222@www.l.google.com","subject":"Re: [Btrfs-devel] btrfs and git-reflog","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-27T08:08:59Z","receivedAt":"2008-01-27T08:08:59Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Yes, but the potential problem is actually very different:\n>\n> - directory contains 'a', 'b' and 'c'\n>\n> \t* opendir()\n> \t* readdir() returns 'a'\n> \t * unlink('a');\n> \t* readdir() returns 'c', having skipped 'b'.\n>\n> This is something that could in theory happen if a directory is indexed \n> using the *position* of a filename in a directory. 'a' was position 1, 'b' \n> was position 2, and 'c' was position 3. After the first readdir(), the \n> file position was 2 (pointing at 'b'), but when we removed 'a', the other \n> entries positions moved down, and now 'b' is at position 1, and 'c' is at \n> position '2'. When we call readdir() the next time, it skips 'b' (because \n> it already returned position 1!), and returns 'c'.\n>\n> See?\n\nYes, I had that one in mind too, but that will cause us to miss\n'b' and its only effect is to leave 'b' unpacked. If we somehow\ndropped 'b' and lost information that is a different story, but\nI do not think this failure mode would cause our current code to\ndo so. So I do not think is a big deal even if some filesystem\nhad a bug like that.\n"}]}