[PATCH 0/5] Fix two mkdir/rmdir races

There seem to be a lot of mkdir/rmdir races in the Git code.  Fix two
of them.

It is hard to construct test cases for races without a lot of extra
test infrastructure.  So I have tested them as best I can using
instrumented code (not included here).

Michael Haggerty (5):
  safe_create_leading_directories(): modernize format of "if" chaining
  safe_create_leading_directories(): reduce scope of local variable
  safe_create_leading_directories(): add "slash" pointer
  safe_create_leading_directories(): fix a mkdir/rmdir race
  rename_ref(): fix a mkdir()/rmdir() race

 refs.c      | 10 +++++++++-
 sha1_file.c | 56 +++++++++++++++++++++++++++++++++-----------------------
 2 files changed, 42 insertions(+), 24 deletions(-)

-- 
1.8.5.1

Keep track of the position of the slash character separately, and
restore the slash character at a single place, at the end of the while
loop.  This makes the next change easier to implement.

Signed-off-by: Michael Haggerty <redacted>
---
 sha1_file.c | 36 ++++++++++++++++++------------------
 1 file changed, 18 insertions(+), 18 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index cc9957e..dcfd35a 100644
--- a/sha1_file.c
+++ b/sha1_file.c

@@ -107,40 +107,40 @@ int mkdir_in_gitdir(const char *path)
 
 int safe_create_leading_directories(char *path)
 {
-	char *pos = path + offset_1st_component(path);
+	char *next_component = path + offset_1st_component(path);
+	int retval = 0;
 
-	while (pos) {
+	while (!retval && next_component) {
 		struct stat st;
+		char *slash = strchr(next_component, '/');
 
-		pos = strchr(pos, '/');
-		if (!pos)
-			break;
-		while (*++pos == '/')
-			;
-		if (!*pos)
-			break;
-		*--pos = '\0';
+		if (!slash)
+			return 0;
+		while (*(slash + 1) == '/')
+			slash++;
+		next_component = slash + 1;
+		if (!*next_component)
+			return 0;
+
+		*slash = '\0';
 		if (!stat(path, &st)) {
 			/* path exists */
 			if (!S_ISDIR(st.st_mode)) {
-				*pos = '/';
-				return -3;
+				retval = -3;
 			}
 		} else if (mkdir(path, 0777)) {
 			if (errno == EEXIST &&
 			    !stat(path, &st) && S_ISDIR(st.st_mode)) {
 				; /* somebody created it since we checked */
 			} else {
-				*pos = '/';
-				return -1;
+				retval = -1;
 			}
 		} else if (adjust_shared_perm(path)) {
-			*pos = '/';
-			return -2;
+			retval = -2;
 		}
-		*pos++ = '/';
+		*slash = '/';
 	}
-	return 0;
+	return retval;
 }
 
 int safe_create_leading_directories_const(const char *path)

-- 
1.8.5.1

Signed-off-by: Michael Haggerty <redacted>
---
 sha1_file.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/sha1_file.c b/sha1_file.c
index c9245a6..cc9957e 100644
--- a/sha1_file.c
+++ b/sha1_file.c

@@ -108,9 +108,10 @@ int mkdir_in_gitdir(const char *path)
 int safe_create_leading_directories(char *path)
 {
 	char *pos = path + offset_1st_component(path);
-	struct stat st;
 
 	while (pos) {
+		struct stat st;
+
 		pos = strchr(pos, '/');
 		if (!pos)
 			break;

-- 
1.8.5.1

When renaming a reflog file, it was possible that an empty directory
that we just created using safe_create_leading_directories() might get
deleted by another process before we have a chance to move the new
file into it.

So if the rename fails with ENOENT, then retry from the beginning.
Make up to three attempts before giving up.

It could theoretically happen that the ENOENT comes from the
disappearance of TMP_RENAMED_LOG.  In that case three pointless
attempts will be made to move the nonexistent file, but no other harm
should come of it.

Signed-off-by: Michael Haggerty <redacted>
---
 refs.c | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)

diff --git a/refs.c b/refs.c
index 3926136..3ab1491 100644
--- a/refs.c
+++ b/refs.c

@@ -2516,6 +2516,7 @@ int rename_ref(const char *oldrefname, const char *newrefname, const char *logms
 	struct stat loginfo;
 	int log = !lstat(git_path("logs/%s", oldrefname), &loginfo);
 	const char *symref = NULL;
+	int attempts = 3;
 
 	if (log && S_ISLNK(loginfo.st_mode))
 		return error("reflog for %s is a symlink", oldrefname);

@@ -2555,12 +2556,12 @@ int rename_ref(const char *oldrefname, const char *newrefname, const char *logms
 		}
 	}
 
+ retry:
 	if (log && safe_create_leading_directories(git_path("logs/%s", newrefname))) {
 		error("unable to create directory for %s", newrefname);
 		goto rollback;
 	}
 
- retry:
 	if (log && rename(git_path(TMP_RENAMED_LOG), git_path("logs/%s", newrefname))) {
 		if (errno==EISDIR || errno==ENOTDIR) {
 			/*

@@ -2574,6 +2575,13 @@ int rename_ref(const char *oldrefname, const char *newrefname, const char *logms
 			}
 			goto retry;
 		} else {
+			if (errno == ENOENT && --attempts)
+				/*
+				 * Perhaps somebody just pruned the empty
+				 * directory into which we wanted to move the
+				 * file.
+				 */
+				goto retry;
 			error("unable to move logfile "TMP_RENAMED_LOG" to logs/%s: %s",
 				newrefname, strerror(errno));
 			goto rollback;

-- 
1.8.5.1

It could be that some other process is trying to clean up empty
directories at the same time that safe_create_leading_directories() is
attempting to create them.  In this case, it could happen that
directory "a/b" was present at the end of one iteration of the loop
(either it was already present or we just created it ourselves), but
by the time we try to create directory "a/b/c", directory "a/b" has
been deleted.  In fact, directory "a" might also have been deleted.

So, if a call to mkdir() fails with ENOENT, then try checking/making
all directories again from the beginning.  Attempt up to three times
before giving up.

Signed-off-by: Michael Haggerty <redacted>
---
 sha1_file.c | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/sha1_file.c b/sha1_file.c
index dcfd35a..abcb56b 100644
--- a/sha1_file.c
+++ b/sha1_file.c

@@ -108,6 +108,7 @@ int mkdir_in_gitdir(const char *path)
 int safe_create_leading_directories(char *path)
 {
 	char *next_component = path + offset_1st_component(path);
+	int attempts = 3;
 	int retval = 0;
 
 	while (!retval && next_component) {

@@ -132,6 +133,16 @@ int safe_create_leading_directories(char *path)
 			if (errno == EEXIST &&
 			    !stat(path, &st) && S_ISDIR(st.st_mode)) {
 				; /* somebody created it since we checked */
+			} else if (errno == ENOENT && --attempts) {
+				/*
+				 * Either mkdir() failed bacause
+				 * somebody just pruned the containing
+				 * directory, or stat() failed because
+				 * the file that was in our way was
+				 * just removed.  Either way, try
+				 * again from the beginning:
+				 */
+				next_component = path + offset_1st_component(path);
 			} else {
 				retval = -1;
 			}

-- 
1.8.5.1

Signed-off-by: Michael Haggerty <redacted>
---
 sha1_file.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index daacc0c..c9245a6 100644
--- a/sha1_file.c
+++ b/sha1_file.c

@@ -125,8 +125,7 @@ int safe_create_leading_directories(char *path)
 				*pos = '/';
 				return -3;
 			}
-		}
-		else if (mkdir(path, 0777)) {
+		} else if (mkdir(path, 0777)) {
 			if (errno == EEXIST &&
 			    !stat(path, &st) && S_ISDIR(st.st_mode)) {
 				; /* somebody created it since we checked */

@@ -134,8 +133,7 @@ int safe_create_leading_directories(char *path)
 				*pos = '/';
 				return -1;
 			}
-		}
-		else if (adjust_shared_perm(path)) {
+		} else if (adjust_shared_perm(path)) {
 			*pos = '/';
 			return -2;
 		}

-- 
1.8.5.1

On 22/12/13 07:14, Michael Haggerty wrote:

s/bacause/because/

+				 * somebody just pruned the containing
+				 * directory, or stat() failed because
+				 * the file that was in our way was
+				 * just removed.  Either way, try
+				 * again from the beginning:
+				 */
+				next_component = path + offset_1st_component(path);
 			} else {
 				retval = -1;
 			}

ATB,
Ramsay Jones

Michael Haggerty wrote:

[Subject: safe_create_leading_directories(): modernize format of "if" chaining]

Trivia: it's not so much modernizing as following K&R style, which git
more or less followed since day 1.  Linux's Documentation/CodingStyle
explains:

  Note that the closing brace is empty on a line of its own, _except_ in
  the cases where it is followed by a continuation of the same statement,
  ie a "while" in a do-statement or an "else" in an if-statement, like
  this:
[...]
  Rationale: K&R.

  Also, note that this brace-placement also minimizes the number of empty
  (or almost empty) lines, without any loss of readability.  Thus, as the
  supply of new-lines on your screen is not a renewable resource (think
  25-line terminal screens here), you have more empty lines to put
  comments on.

Here it's especially jarring since the function uses a mix of styles.
Thanks for cleaning it up.

Michael Haggerty wrote:

Is this to make it easier to reason about whether 'st' has been
properly initialized at any given moment, or is there a more subtle
reason?

Curious,
Jonathan

Michael Haggerty wrote:

[Subject: safe_create_leading_directories(): add "slash" pointer]

Is this a cleanup or improving the (internal) functionality of the
function somehow?  The above one-liner doesn't sum up for me in an
obvious way why this is a good change.

Keep track of the position of the slash character separately, and

Separately from what?

restore the slash character at a single place, at the end of the while
loop.  This makes the next change easier to implement.

Signed-off-by: Michael Haggerty <redacted>

Ah, do I understand correctly that this is about cleaning up
after the code that scribbles over 'path' in one place, to make
it harder to forget to do that cleanup as new code paths are
introduced?

It's too bad there's no variant of 'stat' and 'mkdir' that takes
a (buf, len) pair which would avoid the scribbling altogether.

This name change is probably worth also mentioning in the commit
message (or lifting into a separate patch) so the reader doesn't get
distracted.

+	int retval = 0;
 
-	while (pos) {
+	while (!retval && next_component) {

A more usual style would be

	int ... = 0;

	while (pos) {
		...
		if (!stat(path, &st)) {
			/* path exists */
			if (!S_ISDIR(st.st_mode)) {
				... = -3;
				goto out;
			}
		} else if (...) {
			...
		}
		...
	}
 out:
	*slash = '/';
	return ...;
 }

which makes it more explicit that the slash needs to be written back.
In this example, that would look like:

	char *slash = NULL;
	int ret;

	while (pos) {
		...
		if (!slash)
			break;

		...
		if (!*pos)
			break;

		*slash = '\0';
		if (!stat(path, &st)) {
			if (!S_ISDIR(st.st_mode)) {
				ret = -3;
				goto out;
			}
		} else if (mkdir(...)) {
			if (errno == EEXIST && ...) {
				; /* ok */
			} else {
				ret = -1;
				goto out;
			}
		} else if (adjust_shared_perm(...)) {
			ret = -2;
			goto out;
		}
		*slash = '/';
	}
	ret = 0;
 out:
 	if (slash)
		*slash = '/';
	return ret;

Using retval for control flow instead makes it eight lines more
concise, which is probably worth it.

[...]

			if (!S_ISDIR(st.st_mode)) {
-				*pos = '/';
-				return -3;
+				retval = -3;
			}

Now the 'if' body is one line, so we can drop the braces and save
another line. :)

One more nit: elsewhere in this file, a variable keeping track of the
return value is named 'ret', so it probably makes sense to also use
that name here.

That would mean the following changes to be potentially squashed in
(keeping 'pos' name to make the patch easier to read, s/retval/ret/,
removing unnecessary braces).  None of these tweaks are particularly
important.  Feel free to skip them --- the only comment I've made that
matters is about the commit message.

Thanks for a nice cleanup,
Jonathan

diff --git i/sha1_file.c w/sha1_file.c
index dcfd35a..18cb50a 100644
--- i/sha1_file.c
+++ w/sha1_file.c

@@ -107,40 +107,38 @@ int mkdir_in_gitdir(const char *path)
 
 int safe_create_leading_directories(char *path)
 {
-	char *next_component = path + offset_1st_component(path);
-	int retval = 0;
+	char *pos = path + offset_1st_component(path);
+	int ret = 0;
 
-	while (!retval && next_component) {
+	while (!ret && pos) {
 		struct stat st;
-		char *slash = strchr(next_component, '/');
+		char *slash = strchr(pos, '/');
 
 		if (!slash)
 			return 0;
 		while (*(slash + 1) == '/')
 			slash++;
-		next_component = slash + 1;
-		if (!*next_component)
+		pos = slash + 1;
+		if (!*pos)
 			return 0;
 
 		*slash = '\0';
 		if (!stat(path, &st)) {
 			/* path exists */
-			if (!S_ISDIR(st.st_mode)) {
-				retval = -3;
-			}
+			if (!S_ISDIR(st.st_mode))
+				ret = -3;
 		} else if (mkdir(path, 0777)) {
 			if (errno == EEXIST &&
-			    !stat(path, &st) && S_ISDIR(st.st_mode)) {
+			    !stat(path, &st) && S_ISDIR(st.st_mode))
 				; /* somebody created it since we checked */
-			} else {
-				retval = -1;
-			}
+			else
+				ret = -1;
 		} else if (adjust_shared_perm(path)) {
-			retval = -2;
+			ret = -2;
 		}
 		*slash = '/';
 	}
-	return retval;
+	return ret;
 }
 
 int safe_create_leading_directories_const(const char *path)

Hi,

Michael Haggerty wrote:

It could be that some other process is trying to clean up empty
directories at the same time that safe_create_leading_directories() is
attempting to create them.  In this case, it could happen that
directory "a/b" was present at the end of one iteration of the loop
(either it was already present or we just created it ourselves), but
by the time we try to create directory "a/b/c", directory "a/b" has
been deleted.  In fact, directory "a" might also have been deleted.

When does this happen in practice?  Is this about git racing with
itself or with some other program?

I fear that the aggressive directory creator fighting the aggressive
directory remover might be waging a losing battle.

Is this about a push that creates a ref racing against a push that
deletes a ref from the same hierarchy?

So, if a call to mkdir() fails with ENOENT, then try checking/making
all directories again from the beginning.  Attempt up to three times
before giving up.

If we are racing against a ref deletion, then we can retry while our
rival keeps walking up the directory tree and deleting parent
directories.  As soon as we successfully create a directory, we have
won the race.

But what happens if the entire safe_create_leading_directories
operation succeeds and *then* our racing partner deletes the
directory?  No one is putting in a file to reserve the directory for
the directory creator.

If we care enough to retry more than once, I fear this is retrying at
the wrong level.

Signed-off-by: Michael Haggerty <redacted>
---
 sha1_file.c | 11 +++++++++++
 1 file changed, 11 insertions(+)

Tests?

The code is clear and implements the design correctly.

Thanks for some food for thought,
Jonathan

Michael Haggerty wrote:

 refs.c | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)

A test or example reproduction recipe would be nice.  (But I can
understand not having one --- races are hard to test.)

[...]

[...]

Style nit: it's easier to read a test of errno when the 'else's
cascade (i.e., using 'else if' here).

This patch doesn't depend on any of the others from the series.  For
what it's worth, with or without the following squashed in,

Reviewed-by: Jonathan Nieder <redacted>

Thanks.

diff --git i/refs.c w/refs.c
index 3ab1491..ea62395 100644
--- i/refs.c
+++ w/refs.c

@@ -2574,14 +2574,14 @@ int rename_ref(const char *oldrefname, const char *newrefname, const char *logms
 				goto rollback;
 			}
 			goto retry;
+		} else if (errno == ENOENT && --attempts)
+			/*
+			 * Perhaps somebody just pruned the empty
+			 * directory into which we wanted to move the
+			 * file.
+			 */
+			goto retry;
 		} else {
-			if (errno == ENOENT && --attempts)
-				/*
-				 * Perhaps somebody just pruned the empty
-				 * directory into which we wanted to move the
-				 * file.
-				 */
-				goto retry;
 			error("unable to move logfile "TMP_RENAMED_LOG" to logs/%s: %s",
 				newrefname, strerror(errno));
 			goto rollback;

On 12/26/2013 10:55 PM, Jonathan Nieder wrote:

Michael Haggerty wrote:

quoted

Signed-off-by: Michael Haggerty <redacted>
---
 sha1_file.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/sha1_file.c b/sha1_file.c
index c9245a6..cc9957e 100644
--- a/sha1_file.c
+++ b/sha1_file.c

@@ -108,9 +108,10 @@ int mkdir_in_gitdir(const char *path)
 int safe_create_leading_directories(char *path)
 {
 	char *pos = path + offset_1st_component(path);
-	struct stat st;
 
 	while (pos) {
+		struct stat st;

Is this to make it easier to reason about whether 'st' has been
properly initialized at any given moment, or is there a more subtle
reason?

No, just the boring reason, the one that makes me reduce the scope of
variables whenever possible.  I'll buff up the log message.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

On 12/26/2013 11:34 PM, Jonathan Nieder wrote:

Michael Haggerty wrote:

quoted

[Subject: safe_create_leading_directories(): add "slash" pointer]

Is this a cleanup or improving the (internal) functionality of the
function somehow?  The above one-liner doesn't sum up for me in an
obvious way why this is a good change.

It's hard to make the subject more self-explanatory, given so few
characters.  But I will make the rest of the log message better in the
reroll.

quoted

Keep track of the position of the slash character separately, and

Separately from what?

quoted

restore the slash character at a single place, at the end of the while
loop.  This makes the next change easier to implement.

Signed-off-by: Michael Haggerty <redacted>

Ah, do I understand correctly that this is about cleaning up
after the code that scribbles over 'path' in one place, to make
it harder to forget to do that cleanup as new code paths are
introduced?

Yes.

It's too bad there's no variant of 'stat' and 'mkdir' that takes
a (buf, len) pair which would avoid the scribbling altogether.

Yes.

quoted

---
 sha1_file.c | 36 ++++++++++++++++++------------------
 1 file changed, 18 insertions(+), 18 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index cc9957e..dcfd35a 100644
--- a/sha1_file.c
+++ b/sha1_file.c

@@ -107,40 +107,40 @@ int mkdir_in_gitdir(const char *path)
 
 int safe_create_leading_directories(char *path)
 {
-	char *pos = path + offset_1st_component(path);
+	char *next_component = path + offset_1st_component(path);

This name change is probably worth also mentioning in the commit
message (or lifting into a separate patch) so the reader doesn't get
distracted.

OK, I split the renaming into a separate commit.

quoted

+	int retval = 0;
 
-	while (pos) {
+	while (!retval && next_component) {

A more usual style would be
[...]
Using retval for control flow instead makes it eight lines more
concise, which is probably worth it.

Agreed.

[...]

quoted

			if (!S_ISDIR(st.st_mode)) {
-				*pos = '/';
-				return -3;
+				retval = -3;
			}

Now the 'if' body is one line, so we can drop the braces and save
another line. :)

Will fix.

One more nit: elsewhere in this file, a variable keeping track of the
return value is named 'ret', so it probably makes sense to also use
that name here.

OK, will change.

That would mean the following changes to be potentially squashed in
[...]

While going over the code again, I noticed another problem in the
original version; namely, that the handling of redundant multiple
slashes in the input path is not correct.  I will fix this problem and
split up the commit into smaller steps in the re-roll.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

On 12/27/2013 12:02 AM, Jonathan Nieder wrote:

Michael Haggerty wrote:

quoted

It could be that some other process is trying to clean up empty
directories at the same time that safe_create_leading_directories() is
attempting to create them.  In this case, it could happen that
directory "a/b" was present at the end of one iteration of the loop
(either it was already present or we just created it ourselves), but
by the time we try to create directory "a/b/c", directory "a/b" has
been deleted.  In fact, directory "a" might also have been deleted.

When does this happen in practice?  Is this about git racing with
itself or with some other program?

I think it could be triggered by a reference creation racing with a
reference packing.  See below.

I fear that the aggressive directory creator fighting the aggressive
directory remover might be waging a losing battle.

That may be so, but it would be strange for a directory remover to be
aggressive.  And even if it were, the worst consequence would be that
the director creator would try three times before giving up.

Is this about a push that creates a ref racing against a push that
deletes a ref from the same hierarchy?

The race could be triggered in this scenario but I don't think it would
result in a spurious error (at least not if there are only two
racers...)  The reason is that empty loose reference directories are not
deleted when a reference is *deleted*, but rather when a new
d/f-conflicting reference is *created*.  E.g., if

    git branch foo/bar
    git branch -d foo/bar # this leaves directory foo behind
    # this removes directory foo and creates file foo:
    git branch foo &
        git branch foo/baz

The last two commands could fight.  However, in this scenario one of the
reference creations would ultimately have to fail anyway, so this patch
doesn't really help.

However, when packing references, the directories that used to hold the
old references are deleted right away.  So

    git branch foo/bar
    git pack-refs --all &
        git branch foo/baz

Here, the last two commands could fight.

quoted

So, if a call to mkdir() fails with ENOENT, then try checking/making
all directories again from the beginning.  Attempt up to three times
before giving up.

If we are racing against a ref deletion, then we can retry while our
rival keeps walking up the directory tree and deleting parent
directories.  As soon as we successfully create a directory, we have
won the race.

But what happens if the entire safe_create_leading_directories
operation succeeds and *then* our racing partner deletes the
directory?  No one is putting in a file to reserve the directory for
the directory creator.

If we care enough to retry more than once, I fear this is retrying at
the wrong level.

I realize that this change doesn't solve the whole problem.  But you
make a good point, that if the caller is going to retry anyway, then
there is no need to retry within this function.  It would be sufficient
for this function to return a specific error value indicating that
"creating the directory failed, but there's a chance of success if you
try again".

On the other hand, your argument assumes that all callers really *do*
retry, which isn't the case, and I doubt that all callers are going to
be fixed.  So there might be some value in retrying within this function
anyway (it's a game of averages we're playing here anyway).

I'll think some more about it.

Tests?

I can't think of how to test this short of either instrumenting the code
(which I did for my own tests, but didn't include the test code in this
submission) or running the test within some kind of malicious virtual
filesystem.  Ideas?

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/