{"thread":{"id":"19277","subject":"[JGIT PATCH 1/2] Fix deadlock in native git protocol client for upload-pack","startedAt":"2009-05-10T22:48:04Z","lastAt":"2009-05-11T14:23:47Z","messageCount":7,"participants":["Shawn O. Pearce","Junio C Hamano","Carl Mercier"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"113495","messageId":"1241995685-13260-1-git-send-email-spearce@spearce.org","threadId":"19277","inReplyTo":null,"subject":"[JGIT PATCH 1/2] Fix deadlock in native git protocol client for upload-pack","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-05-10T22:48:04Z","receivedAt":"2009-05-10T22:48:04Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"The upload-pack protocol states that for every flush packet\n(aka \"0000\") sent by the client, we get exactly one NAK or\nACK line back.  However, if multi_ack is enabled, we may\nget multiple \"ACK %s continue\" lines before the ACK/NAK is\nsent by the upload-pack server.\n\nUnfortunately, JGit was counting an \"ACK %s continue\" as a response\nto a flush packet, causing the client side to stop reading from\nthe server too early.  This left a lot of \"ACK %s continue\" lines\nin the server output buffer, eventually causing the server to stop\nand wait for the output buffer to drain.  However, the client would\nalso get stuck after sending too many \"have %s\" lines, eventually\ndeadlocking the entire client-server pair.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n .../jgit/transport/BasePackFetchConnection.java    |    4 ++--\n 1 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/BasePackFetchConnection.java b/org.spearce.jgit/src/org/spearce/jgit/transport/BasePackFetchConnection.java\nindex f07cc4e..eaa94bd 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/transport/BasePackFetchConnection.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/BasePackFetchConnection.java\n@@ -359,15 +359,15 @@ private void negotiate(final ProgressMonitor monitor) throws IOException,\n \t\t\t\tcontinue;\n \t\t\t}\n \n-\t\t\twhile (resultsPending > 0) {\n+\t\t\tfor (;;) {\n \t\t\t\tfinal PacketLineIn.AckNackResult anr;\n \n \t\t\t\tanr = pckIn.readACK(ackId);\n-\t\t\t\tresultsPending--;\n \t\t\t\tif (anr == PacketLineIn.AckNackResult.NAK) {\n \t\t\t\t\t// More have lines are necessary to compute the\n \t\t\t\t\t// pack on the remote side. Keep doing that.\n \t\t\t\t\t//\n+\t\t\t\t\tresultsPending--;\n \t\t\t\t\tbreak;\n \t\t\t\t}\n \n-- \n1.6.3.48.g99c76\n"},{"id":"113496","messageId":"1241995685-13260-2-git-send-email-spearce@spearce.org","threadId":"19277","inReplyTo":"1241995685-13260-1-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 2/2] Decrease the fetch pack client buffer to the lower minimum","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-05-10T22:48:05Z","receivedAt":"2009-05-10T22:48:05Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"This is the lowest buffer size we actually require to keep the\nclient and server sides from deadlocking against each other.\n\nAlso added documentation, and renamed the symbol to better match\nits real purpose; naming the lower threshold we can allow for a\nbuffer.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n .../jgit/transport/BasePackFetchConnection.java    |   10 +++++++++-\n .../org/spearce/jgit/transport/TransportLocal.java |    2 +-\n 2 files changed, 10 insertions(+), 2 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/BasePackFetchConnection.java b/org.spearce.jgit/src/org/spearce/jgit/transport/BasePackFetchConnection.java\nindex eaa94bd..1d1b801 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/transport/BasePackFetchConnection.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/BasePackFetchConnection.java\n@@ -89,7 +89,15 @@\n \t */\n \tprivate static final int MAX_HAVES = 256;\n \n-\tprotected static final int MAX_CLIENT_BUFFER = MAX_HAVES * 46 + 1024;\n+\t/**\n+\t * Amount of data the client sends before starting to read.\n+\t * <p>\n+\t * Any output stream given to the client must be able to buffer this many\n+\t * bytes before the client will stop writing and start reading from the\n+\t * input stream. If the output stream blocks before this many bytes are in\n+\t * the send queue, the system will deadlock.\n+\t */\n+\tprotected static final int MIN_CLIENT_BUFFER = 2 * 32 * 46 + 4;\n \n \tstatic final String OPTION_INCLUDE_TAG = \"include-tag\";\n \ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/TransportLocal.java b/org.spearce.jgit/src/org/spearce/jgit/transport/TransportLocal.java\nindex cffdba1..428f73e 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/transport/TransportLocal.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/TransportLocal.java\n@@ -175,7 +175,7 @@ InternalLocalFetchConnection() throws TransportException {\n \t\t\t\t\t// force the buffer to be big enough, otherwise it\n \t\t\t\t\t// will deadlock both threads.\n \t\t\t\t\t{\n-\t\t\t\t\t\tbuffer = new byte[MAX_CLIENT_BUFFER];\n+\t\t\t\t\t\tbuffer = new byte[MIN_CLIENT_BUFFER];\n \t\t\t\t\t}\n \t\t\t\t};\n \t\t\t\tout_w = new PipedOutputStream(out_r);\n-- \n1.6.3.48.g99c76\n"},{"id":"113503","messageId":"7vfxfctqon.fsf@alter.siamese.dyndns.org","threadId":"19277","inReplyTo":"1241995685-13260-2-git-send-email-spearce@spearce.org","subject":"Re: [JGIT PATCH 2/2] Decrease the fetch pack client buffer to the lower minimum","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-05-11T00:43:20Z","receivedAt":"2009-05-11T00:43:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> writes:\n\n> This is the lowest buffer size we actually require to keep the\n> client and server sides from deadlocking against each other.\n\nIs this about the fetch-pack protocol where\n\n (1) upload-pack shows what it has; fetch-pack keeps reading until it sees\n     a flush; then\n\n (2) fetch-pack shows what it wants; upload-pack keeps reading; then\n\n (3) fetch-pack sends a bunch of have's, followed by a flush; upload-pack\n     keeps reading and then responds with an ACK-continue or NAK, which\n     fetch-pack reads; this step continues zero or more times; and then\n     finally\n\n (4) fetch-pack sends a bunch of have's, followed by a flush; upload-pack\n     keeps reading and then responds with an ACK, fetch-pack says done.\n\nWhere do you need \"enough buffer\"?  The conversation looks very much \"it's\nmy turn to talk\", \"now it's your turn to talk and I'll wait until I hear\nfrom you\", to me.  I am puzzled.\n\n> Also added documentation, and renamed the symbol to better match\n> its real purpose; naming the lower threshold we can allow for a\n> buffer.\n>\n> Signed-off-by: Shawn O. Pearce <spearce@spearce.org>\n> ---\n>  .../jgit/transport/BasePackFetchConnection.java    |   10 +++++++++-\n>  .../org/spearce/jgit/transport/TransportLocal.java |    2 +-\n>  2 files changed, 10 insertions(+), 2 deletions(-)\n>\n> diff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/BasePackFetchConnection.java b/org.spearce.jgit/src/org/spearce/jgit/transport/BasePackFetchConnection.java\n> index eaa94bd..1d1b801 100644\n> --- a/org.spearce.jgit/src/org/spearce/jgit/transport/BasePackFetchConnection.java\n> +++ b/org.spearce.jgit/src/org/spearce/jgit/transport/BasePackFetchConnection.java\n> @@ -89,7 +89,15 @@\n>  \t */\n>  \tprivate static final int MAX_HAVES = 256;\n>  \n> -\tprotected static final int MAX_CLIENT_BUFFER = MAX_HAVES * 46 + 1024;\n> +\t/**\n> +\t * Amount of data the client sends before starting to read.\n> +\t * <p>\n> +\t * Any output stream given to the client must be able to buffer this many\n> +\t * bytes before the client will stop writing and start reading from the\n> +\t * input stream. If the output stream blocks before this many bytes are in\n> +\t * the send queue, the system will deadlock.\n> +\t */\n> +\tprotected static final int MIN_CLIENT_BUFFER = 2 * 32 * 46 + 4;\n>  \n>  \tstatic final String OPTION_INCLUDE_TAG = \"include-tag\";\n>  \n> diff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/TransportLocal.java b/org.spearce.jgit/src/org/spearce/jgit/transport/TransportLocal.java\n> index cffdba1..428f73e 100644\n> --- a/org.spearce.jgit/src/org/spearce/jgit/transport/TransportLocal.java\n> +++ b/org.spearce.jgit/src/org/spearce/jgit/transport/TransportLocal.java\n> @@ -175,7 +175,7 @@ InternalLocalFetchConnection() throws TransportException {\n>  \t\t\t\t\t// force the buffer to be big enough, otherwise it\n>  \t\t\t\t\t// will deadlock both threads.\n>  \t\t\t\t\t{\n> -\t\t\t\t\t\tbuffer = new byte[MAX_CLIENT_BUFFER];\n> +\t\t\t\t\t\tbuffer = new byte[MIN_CLIENT_BUFFER];\n>  \t\t\t\t\t}\n>  \t\t\t\t};\n>  \t\t\t\tout_w = new PipedOutputStream(out_r);\n> -- \n> 1.6.3.48.g99c76\n"},{"id":"113506","messageId":"20090511005526.GI30527@spearce.org","threadId":"19277","inReplyTo":"7vfxfctqon.fsf@alter.siamese.dyndns.org","subject":"Re: [JGIT PATCH 2/2] Decrease the fetch pack client buffer to the lower minimum","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-05-11T00:55:26Z","receivedAt":"2009-05-11T00:55:26Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <gitster@pobox.com> wrote:\n> \"Shawn O. Pearce\" <spearce@spearce.org> writes:\n> \n> > This is the lowest buffer size we actually require to keep the\n> > client and server sides from deadlocking against each other.\n> \n> Is this about the fetch-pack protocol where\n\nYes.\n \n>  (1) upload-pack shows what it has; fetch-pack keeps reading until it sees\n>      a flush; then\n> \n>  (2) fetch-pack shows what it wants; upload-pack keeps reading; then\n> \n>  (3) fetch-pack sends a bunch of have's, followed by a flush; upload-pack\n>      keeps reading and then responds with an ACK-continue or NAK, which\n>      fetch-pack reads; this step continues zero or more times; and then\n>      finally\n> \n>  (4) fetch-pack sends a bunch of have's, followed by a flush; upload-pack\n>      keeps reading and then responds with an ACK, fetch-pack says done.\n> \n> Where do you need \"enough buffer\"?  The conversation looks very much \"it's\n> my turn to talk\", \"now it's your turn to talk and I'll wait until I hear\n> from you\", to me.  I am puzzled.\n\nIn step 3 during the first round the client can send up to 2 blocks\nworth of data, with 32 haves per block.  This means the client\nwrites 2952 bytes of data before it reads.\n\nC Git doesn't run into this sort of problem because a normal pipe\nwould get 1 page (~4096 bytes) in the kernel for the FIFO buffer.\n\nIn SSH transport, we still have 4096 between us and the ssh client\nprocess, plus that has its own buffering.\n\nIn TCP transport, we have the kernel TX buffer on this side, and the\nkernel RX buffer on the remote side, plus network switch buffers in\nthe middle.  2952 bytes nicely fits into just over 2 IP packets,\nand the TCP window is sufficiently large enough to allow these to\nbe sent without blocking the writer.\n\nWe need to be able to shove 2952 bytes down at the other guy before\nwe start listening to him.  The upload-pack side of the system can\n(at worst) send us 64 \"ACK %s continue\" lines.  We must be able\nto enter into the receive mode before the upload-pack side fills\ntheir outgoing buffer.\n\nIn the Sun JVMs a pure in-memory pipe only has room for 1024 bytes\nin the FIFO before it blocks.  Though the technique I am using to\nboost the FIFO from 1024 to 2952 bytes isn't necessarily going to\nbe portable to other JVMs.  If both sides only have 1024 bytes of\nbuffer available and both sides can possibly write more than that,\nwe deadlock.\n\n> > +\t/**\n> > +\t * Amount of data the client sends before starting to read.\n> > +\t * <p>\n> > +\t * Any output stream given to the client must be able to buffer this many\n> > +\t * bytes before the client will stop writing and start reading from the\n> > +\t * input stream. If the output stream blocks before this many bytes are in\n> > +\t * the send queue, the system will deadlock.\n> > +\t */\n> > +\tprotected static final int MIN_CLIENT_BUFFER = 2 * 32 * 46 + 4;\n\nAnd this should be + 8 here.  F@!*!\n\nRobin, can you amend?  It should be + 8 because we send to end()\npackets in that initial burst, each packet is 4 bytes in size.\n\n-- \nShawn.\n"},{"id":"113512","messageId":"7vr5yws3fe.fsf@alter.siamese.dyndns.org","threadId":"19277","inReplyTo":"20090511005526.GI30527@spearce.org","subject":"Re: [JGIT PATCH 2/2] Decrease the fetch pack client buffer to the lower minimum","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-05-11T03:51:01Z","receivedAt":"2009-05-11T03:51:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> writes:\n\n> In step 3 during the first round the client can send up to 2 blocks\n> worth of data, with 32 haves per block.  This means the client\n> writes 2952 bytes of data before it reads.\n\nSorry, perhaps I am being extremely slow, but even if the client writes\nmillions of bytes before it starts reading, I do not see how it would be a\nproblem as long as the other side reads these millions of bytes before\nsaying \"Ok, I've heard about them and my response so far is Ack-continue\n(or NAK)\", which the client needs to read.\n"},{"id":"113541","messageId":"20090511141021.GJ30527@spearce.org","threadId":"19277","inReplyTo":"7vr5yws3fe.fsf@alter.siamese.dyndns.org","subject":"Re: [JGIT PATCH 2/2] Decrease the fetch pack client buffer to the lower minimum","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-05-11T14:10:22Z","receivedAt":"2009-05-11T14:10:22Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <gitster@pobox.com> wrote:\n> \"Shawn O. Pearce\" <spearce@spearce.org> writes:\n> \n> > In step 3 during the first round the client can send up to 2 blocks\n> > worth of data, with 32 haves per block.  This means the client\n> > writes 2952 bytes of data before it reads.\n> \n> Sorry, perhaps I am being extremely slow, but even if the client writes\n> millions of bytes before it starts reading, I do not see how it would be a\n> problem as long as the other side reads these millions of bytes before\n> saying \"Ok, I've heard about them and my response so far is Ack-continue\n> (or NAK)\", which the client needs to read.\n\nOk, maybe my understanding of the fetch-pack/upload-pack protocol\nis incorrect.\n\nIf multi_ack is enabled then isn't it possible for the remote to\nreturn \"ACK %s continue\" for the first 63 \"have %s\" lines the\nclient sent?\n\nE.g. the case is the client has only one ref, and has only 1 commit\nthe other side doesn't have, and the other side has only one ref,\nand has only 1 commit the client doesn't have (so the client will\nfetch 1 commit).  In such a case, the client will blast 64 have lines\nbefore pausing to listen to the server.  But the server will have\n63 of those lines, and will try to send \"ACK %s continue\" in vain\nat the client, hoping it will stop enumerating along that branch.\n\nIf there is insufficient buffering along one of those writers,\nthe entire thing deadlocks.\n\n-- \nShawn.\n"},{"id":"113543","messageId":"F54ED060-E64A-44DC-B4BA-5508D76F6E20@websense.com","threadId":"19277","inReplyTo":"20090511141021.GJ30527@spearce.org","subject":"(unknown)","fromName":"Carl Mercier","fromEmail":"cmercier@websense.com","sentAt":"2009-05-11T14:23:47Z","receivedAt":"2009-05-11T14:23:47Z","isPatch":false,"sender":{"key":"cmercier@websense.com","avatar":null},"body":"unsubscribe git\n\n\n Protected by Websense Hosted Email Security -- www.websense.com \n"}]}