[PATCH/RFC] fast-import doc: deadlock avoidance in bidirectional mode

From: Jonathan Nieder <jrnieder@gmail.com>
Date: Apr 11, 2012, 17:17 UTC
Message-ID: <20120411171707.GD4248@burratino>
In-Reply-To: <7v1ununtb2.fsf@alter.siamese.dyndns.org>

If fast-import's command pipe and the frontend's cat-blob/ls response pipe are both filled, there can be a deadlock. Luckily all existing frontends consume any pending cat-blob/ls responses completely before writing the next command.

Document the requirements so future frontend authors and users can be spared from the problem, too. It is not always easy to catch that kind of bug by testing.

Reported-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
---
Junio C Hamano wrote:

> Does this essentially connect the frontend and fast-import via
> bidirectional pipes?  How is the flow control and deadlock avoidance
> supposed to happen

fast-import never asks the frontend for information, which makes life a little simpler.

Typically the interaction works just as you described:

 1. Frontend sends "ls" or "cat-blob" request and flushes it, and then
    blocks waiting for the response.

 2. Once fast-import catches up with pending commands, it sends its
    response to the "cat-blob response" pipe.

    (If the pipe does not have enough room, it fills the pipe and then
    blocks until some more room is available.  If the reader has
    closed the pipe, it assumes the import was botched and just exits.)

 3. Only once the frontend has received its response, it moves on and
    starts to send new commands.

A frontend can be more clever than that and use slack to queue some extra commands, as long as the author understands:

 i.  fast-import is not guaranteed to make any progress in consuming
     its input until the "cat-blob response" pipe has been drained.

 ii. the command pipe is not guaranteed to be able to hold extra
     commands when fast-import is not consuming its input.  Probably
     512 bytes (_POSIX_PIPE_BUF) will fit but I don't know how
     portable that is to other fast-import backends so let's say the
     limit is 1 byte.

In other words, in practice it's best not to rely on the extra space at all.

How about this?

 Documentation/git-fast-import.txt |   13 ++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)

diff --git a/Documentation/git-fast-import.txt b/Documentation/git-fast-import.txt
index ec6ef311..0ea649f4 100644
--- a/Documentation/git-fast-import.txt
+++ b/Documentation/git-fast-import.txt
@@ -942,6 +942,12 @@ This command can be used anywhere in the stream that comments are
 accepted.  In particular, the `cat-blob` command can be used in the
 middle of a commit but not in the middle of a `data` command.
 
+While in some cases the 'cat-blob' result will fit in the pipe buffer,
+allowing fast-import to continue processing additional commands, this
+is not guaranteed.  Frontends must consume the cat-blob response
+completely before performing any writes to fast-import that might
+block.
+
 `ls`
 ~~~~
 Prints information about the object at a path to a file descriptor
@@ -975,7 +981,12 @@ Reading from a named tree::
 
 See `filemodify` above for a detailed description of `<path>`.
 
-Output uses the same format as `git ls-tree <tree> {litdd} <path>`:
+While in some cases the 'ls' response will fit in the pipe buffer,
+allowing fast-import to continue processing additional commands, this
+is not guaranteed.  Frontends must consume the ls response completely
+before performing any writes to fast-import that might block.
+
+The 'ls' response uses the same format as `git ls-tree <tree> {litdd} <path>`:
 
 ====
 	<mode> SP ('blob' | 'tree' | 'commit') SP <dataref> HT <path> LF

-- 
1.7.10