Subject: [quicwg/base-drafts] Flow control hazards (#1927)

From: Martin Thomson <[email-masked]>
Date: Sun, 28 Oct 2018 21:47:27 -0700

This describes some of the risks entailed by flow control.  I'm starting
to think that this sort of language is best moved to the applicability
statement, but I'd like other opinions on that.

I'm also not completely happy with how this turned out.  This is just
the first rough cut.  Concrete suggestions for how to improve this would
be greatly appreciated.

Closes #1432.
You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/1927

-- Commit Summary --

  * Flow control hazards

-- File Changes --

    M draft-ietf-quic-transport.md (48)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/1927.patch
https://github.com/quicwg/base-drafts/pull/1927.diff

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927

---

From: ianswett <[email-masked]>
Date: Mon, 29 Oct 2018 06:17:33 -0700

ianswett commented on this pull request.

I think the text on large messages that aren't incrementally processed and interdependent streams are both important ones to call out, but the rest of the two paragraphs between them don't add much for me.

> +several ways in which limits can produce conditions that can cause a connection
+to either perform suboptimally or deadlock.
+
+Implementations need to be aware of the possibility of deadlocking and that some
+conditions that lead to deadlocking cannot be completely avoided in a protocol
+design.
+
+Large messages can produce deadlocking if the recipient does not process the
+message incrementally.  If the message is larger than flow control credit
+available and the recipient does not release additional flow control credit, a
+deadlock can occur.  This is possible even where stream flow control limits are
+not reached because connection flow control limits can be consumed by other
+streams.
+
+A common implementation technique has flow control credit extended as data is
+read from receive buffers.  In that setting, a length-prefixed message format

I'm confused about why this is so.  The only thing I can think of is if the payload is too big, you can reset/stop_sending the stream.

> +design.
+
+Large messages can produce deadlocking if the recipient does not process the
+message incrementally.  If the message is larger than flow control credit
+available and the recipient does not release additional flow control credit, a
+deadlock can occur.  This is possible even where stream flow control limits are
+not reached because connection flow control limits can be consumed by other
+streams.
+
+A common implementation technique has flow control credit extended as data is
+read from receive buffers.  In that setting, a length-prefixed message format
+makes it easier for a recipient to leave data unread and thereby withhold flow
+control credit.  If flow control limits prevent the remainder of a message from
+being sent, a deadlock will result.  However, a length prefix might enable the
+detection of this sort of deadlocks.  Where protocols have messages that might
+be processed as a single unit, reserving flow control credit for the entire

Connection level flow control can't be reduced, so are you suggesting it not be further increased until the message arrives?  I haven't implemented this sort of logic, but it seems very tricky to get right and done incorrectly, could result in deadlocks.

> +message incrementally.  If the message is larger than flow control credit
+available and the recipient does not release additional flow control credit, a
+deadlock can occur.  This is possible even where stream flow control limits are
+not reached because connection flow control limits can be consumed by other
+streams.
+
+A common implementation technique has flow control credit extended as data is
+read from receive buffers.  In that setting, a length-prefixed message format
+makes it easier for a recipient to leave data unread and thereby withhold flow
+control credit.  If flow control limits prevent the remainder of a message from
+being sent, a deadlock will result.  However, a length prefix might enable the
+detection of this sort of deadlocks.  Where protocols have messages that might
+be processed as a single unit, reserving flow control credit for the entire
+message atomically ensures that this style of deadlock is less likely.
+
+Even a message as small as two bytes could produce a deadlock.  Though the

This paragraph isn't adding anything for me.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927#pullrequestreview-169291253

---

From: Mike Bishop <[email-masked]>
Date: Mon, 29 Oct 2018 11:53:59 -0700

MikeBishop commented on this pull request.

You might be right about putting this in the applicability doc instead.

+

Concrete example:  You can't consume less than a full QPACK instruction on the encoder stream.  If you read far enough to see that you have a 64KB auth header coming at you, you might logically not continue reading until you've received those 64KB.  If there's not sufficient flow control for the sender to complete sending, nothing gets read and you deadlock.

That might be because the connection flow control never gets increased, or it might be because it got increased but allocated to other streams that have data to send.

I agree, except that the last sentence is important.

> +deadlock is to read every byte as it becomes available.  However, incremental
+processing of messages can greatly increase complexity of implementations.
+Also, releasing flow control credit might mean that an endpoint might need other
+means of holding a peer accountable for the state commitment for partially
+processed messages.
+
+Deadlocking can also occur if data on different streams is interdependent.  In
+this case, data on one stream arrives before the data on a second stream on
+which it depends.  A deadlock can occur if first stream cannot be read and that
+prevents flow control limits for the second stream being increased.  To reduce
+the likelihood of deadlock for interdependent data, implementations can ensure
+that data is not sent until the data it depends on has consumed both stream- and
+connection- level flow control credit.
+
+Some deadlocking scenarios might be resolved by cancelling affected streams with
+STOP_SENDING or RST_STREAM, if the protocol permits that.

I'd change "if the protocol permits that" to "but depending on the application protocol, this might result in terminating the connection."

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927#pullrequestreview-169461264

---

From: Martin Thomson <[email-masked]>
Date: Mon, 29 Oct 2018 17:35:48 -0700

@martinthomson pushed 1 commit.

d4ceec2  Tweakin'

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927/files/9f8585f34dda6b5255d659aee29e31b09793c8d1..d4ceec2ecc45c0e9eab0d3e44b0e79b26d9fa323

---

From: Martin Thomson <[email-masked]>
Date: Mon, 29 Oct 2018 17:36:06 -0700

martinthomson commented on this pull request.

Having slept on this, I think that applicability is a better venue for this sort of thing.

I'm not following your comment here.

Suggestions sought.  I don't think that I can just leave the last sentence without the preface.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927#pullrequestreview-169573079

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 30 Oct 2018 12:31:30 +0000 (UTC)

dtikhonov commented on this pull request.

+

> Concrete example: You can't consume less than a full QPACK instruction on the encoder stream.

Yes, you can. See [lsqpack_dec_enc_in()](https://github.com/litespeedtech/ls-qpack/blob/5f17c82e8c0f3b2b2faa8984256ff355bc5dc657/src/lsqpack.c#L4186)

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927#discussion_r229286361

---

From: afrind <[email-masked]>
Date: Tue, 30 Oct 2018 16:16:02 +0000 (UTC)

afrind commented on this pull request.

+

I think he's just giving an example of an implementation that cannot handle this.  You are correct that the protocol does not mandate this specific behavior.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927#discussion_r229373995

---

From: janaiyengar <[email-masked]>
Date: Tue, 30 Oct 2018 16:30:04 -0700

janaiyengar commented on this pull request.

A few suggestions. I agree that this belongs in applicability.

> @@ -884,6 +884,55 @@ provide an interface to QUIC to tell it about its buffering limits so that there
 is not excessive buffering at multiple layers.

+## Flow Control Deadlocks {#flow-control-deadlocks}
+
+Flow control provides a means of managing access to the limited buffers
+endpoints have for incoming data.  This mechanism limits the amount of data that
+can be in buffers in endpoints or in transit on the network.  However, there are
+several ways in which limits can produce conditions that can cause a connection
+to either perform suboptimally or deadlock.
+
+Implementations need to be aware of the possibility of deadlocking and that some
+conditions that lead to deadlocking cannot be completely avoided in a protocol
+design.

I don't think this is accurate. The deadlock problem is not within a protocol here, but in how two protocol implementations (HTTP and QUIC) might interact.

> @@ -884,6 +884,55 @@ provide an interface to QUIC to tell it about its buffering limits so that there
 is not excessive buffering at multiple layers.

+## Flow Control Deadlocks {#flow-control-deadlocks}
+
+Flow control provides a means of managing access to the limited buffers
+endpoints have for incoming data.  This mechanism limits the amount of data that
+can be in buffers in endpoints or in transit on the network.  However, there are
+several ways in which limits can produce conditions that can cause a connection
+to either perform suboptimally or deadlock.
+
+Implementations need to be aware of the possibility of deadlocking and that some
+conditions that lead to deadlocking cannot be completely avoided in a protocol
+design.
+
+Large messages can produce deadlocking if the recipient does not process the
+message incrementally.  If the message is larger than flow control credit
+available and the recipient does not release additional flow control credit, a

```suggestion
available and the recipient does not release additional flow control credit
until the entire message is received and delivered, a
```

> +can be in buffers in endpoints or in transit on the network.  However, there are

```suggestion
A common flow control implementation technique is for a receiver to extend
credit to the sender as a the data consumer reads data out of the receiver's
buffers. In this setting, a length-prefixed message format
```

```suggestion
```

+

```suggestion
makes it easier for the data consumer to leave data unread in the receiver's
buffers and thereby withhold flow
```

How about "A data consumer can read bytes out of a receiver's buffer as they become available to cause the receiver to extend flow control credit to the sender and reduce chances of a deadlock. However, releasing flow control credit might mean that the data consumer might need other means of holding a peer accountable for the state commitment for partially processed messages."

+detection of this sort of deadlock.  Where protocols have messages that might
+chances of deadlock are reduced for smaller messages, the only way to prevent

```suggestion
Deadlocking can also occur if a data consumer introduces dependencies between
data sent and received on different streams.
```

> +detection of this sort of deadlock.  Where protocols have messages that might
+chances of deadlock are reduced for smaller messages, the only way to prevent

```suggestion
prevents the receiver from extending flow control credit for the second stream.
To reduce
```

+chances of deadlock are reduced for smaller messages, the only way to prevent

```suggestion
the likelihood of deadlock for interdependent data, the application sender
should ensure
```

+
+chances of deadlock are reduced for smaller messages, the only way to prevent

```suggestion
that dependent data is not sent until the data it depends on has been accounted
for in both stream- and connection- level flow control credit.
```

+chances of deadlock are reduced for smaller messages, the only way to prevent

```suggestion
```

+detection of this sort of deadlock.  Where protocols have messages that might
+chances of deadlock are reduced for smaller messages, the only way to prevent

```suggestion
Suppose that data on one stream arrives before the data on a second stream on
```

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927#pullrequestreview-170037653

---

From: Martin Thomson <[email-masked]>
Date: Tue, 30 Oct 2018 17:26:31 -0700

031e5fa  Update draft-ietf-quic-transport.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927/files/d4ceec2ecc45c0e9eab0d3e44b0e79b26d9fa323..031e5fae503c5d80b19ec6ccfb3d70061ec924c8

---

From: Martin Thomson <[email-masked]>
Date: Tue, 30 Oct 2018 17:26:42 -0700

e88a74e  Update draft-ietf-quic-transport.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927/files/031e5fae503c5d80b19ec6ccfb3d70061ec924c8..e88a74e7ca95cf1f1773ea1ce946053549f220f1

---

From: Martin Thomson <[email-masked]>
Date: Tue, 30 Oct 2018 17:26:52 -0700

955acd7  Update draft-ietf-quic-transport.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927/files/e88a74e7ca95cf1f1773ea1ce946053549f220f1..955acd7f0b84b407cd12ab0d0be1bf314063254d

---

From: Martin Thomson <[email-masked]>
Date: Tue, 30 Oct 2018 17:26:59 -0700

5192364  Update draft-ietf-quic-transport.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927/files/955acd7f0b84b407cd12ab0d0be1bf314063254d..5192364d3c3c3e84ab2a3af3381744ac14c5db9a

---

From: Martin Thomson <[email-masked]>
Date: Tue, 30 Oct 2018 17:29:24 -0700

7266cc4  Update draft-ietf-quic-transport.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927/files/5192364d3c3c3e84ab2a3af3381744ac14c5db9a..7266cc4f36e5ae3f4fae9c9ac3c5a7338e16448e

---

From: Martin Thomson <[email-masked]>
Date: Tue, 30 Oct 2018 17:29:31 -0700

6511027  Update draft-ietf-quic-transport.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927/files/7266cc4f36e5ae3f4fae9c9ac3c5a7338e16448e..65110279bc8635d14b2ac81769d26c90d576b8b3

---

From: Martin Thomson <[email-masked]>
Date: Tue, 30 Oct 2018 17:29:38 -0700

e336de8  Update draft-ietf-quic-transport.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927/files/65110279bc8635d14b2ac81769d26c90d576b8b3..e336de8d2d43d0fa1d8691a8d699afa1598e11a9

---

From: Martin Thomson <[email-masked]>
Date: Tue, 30 Oct 2018 17:29:42 -0700

89b1794  Update draft-ietf-quic-transport.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927/files/e336de8d2d43d0fa1d8691a8d699afa1598e11a9..89b17941405881cb54217c1590a9af1ab061b3a3

---

From: Martin Thomson <[email-masked]>
Date: Tue, 30 Oct 2018 17:29:45 -0700

0c5604e  Update draft-ietf-quic-transport.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927/files/89b17941405881cb54217c1590a9af1ab061b3a3..0c5604e86a295ce4f9928ba0a84dd144c3b753ca

---

From: Martin Thomson <[email-masked]>
Date: Tue, 30 Oct 2018 17:41:55 -0700

Closed #1927.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927#event-1936649791

---

From: Martin Thomson <[email-masked]>
Date: Tue, 30 Oct 2018 17:41:56 -0700

Closing in favour of quicwg/ops-drafts#53

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1927#issuecomment-434521017