Subject: Are HTTP/2 state changes atomic with respect to SETTINGS_MAX_CONCURRENT_STREAMS?

From: Cory Benfield <[email-masked]>
Date: Fri, 8 Feb 2019 16:42:45 +0000

Hey folks,

While implementing (yet another) HTTP/2 stack, I have bumped into an
edge case that I hadn't noticed before and wanted to get feedback from
the WG about what the consensus interpretation is.

Here's the text of RFC 7540 § 5.1.2:

>  Streams that are in the "open" state or in either of the "half-
> closed" states count toward the maximum number of streams that an
> endpoint is permitted to open.  Streams in any of these three states
> count toward the limit advertised in the
> SETTINGS_MAX_CONCURRENT_STREAMS setting.  Streams in either of the
> "reserved" states do not count toward the stream limit.

So far so clear. My question is this: if a server reserves a stream,
and then on the reserved stream sends a HEADERS frame with END_STREAM
set, does the reserved stream ever count against
SETTINGS_MAX_CONCURRENT_STREAMS?

This can be thought about through this thought experiment. Imagine a
client sets SETTINGS_MAX_CONCURRENT_STREAMS to 5. The server sends six
PUSH_PROMISE frames, and then opens 5 streams with
HEADERS(END_HEADERS). Then, the server sends
HEADERS(END_HEADERS,END_STREAM) on the sixth reserved stream. Does
this trigger a violation of SETTINGS_MAX_CONCURRENT_STREAMS?

RFC 7540 never quite says whether or not HEADERS + END_STREAM triggers
atomic or sequential state transitions. § 5.1 says (while describing
the idle state):

> Sending or receiving a HEADERS frame causes the stream to
> become "open".  The stream identifier is selected as described
>  in Section 5.1.1.  The same HEADERS frame can also cause a
> stream to immediately become "half-closed".

This says "immediately", without defining the semantics of immediacy.
This text stands in contrast to the text describing the reserved
states, which says:

> The endpoint can send a HEADERS frame.  This causes the stream
> to open in a "half-closed (remote)" state.

This does not say "immediately transition" but instead "open in".

This is made more complex by the stream state diagram, which implies
that the END_STREAM transition occurs separately from the HEADERS
transition.

My instinct is to say that these streams do not count against
SETTINGS_MAX_CONCURRENT_STREAMS. This instinct is largely informed by
Martin's previous characterisation of RFC 7540 as being written "as
though headers were free". In a model where headers cost nothing, a
stream guaranteed to be made only of headers never counts against
SETTINGS_MAX_CONCURRENT_STREAMS.

That said, I'm interested in knowing what other implementations do. We
should also consider whether it is worth drafting an erratum to
attempt to clarify the state transitions of END_STREAM.

Thanks,

Cory

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 8 Feb 2019 21:15:25 +0100

Hi Cory,

On Fri, Feb 08, 2019 at 04:42:45PM +0000, Cory Benfield wrote:
(...)
> SETTINGS_MAX_CONCURRENT_STREAMS.

I agree with you here. In fact whenever you think about concurrency, you
need to think of it including the time and space factors : if it is *not*
this way, then what is the scope where this concurrency is counted on ?
Do you need to measure it over a certain time window ? Fortunately not.
Do you have to measure it at any given point (e.g. your H2 connection
buffer) ? Not at all either since what your agent sees will differ from
what any other agent along the chain sees. Thus this concurrency is purely
event-driven (HEADERS/PUSH_PROMISE = +1, END_STREAM/RST_STREAM = -1) and
you have no other way to accurately measure, hence enforce your limit.
So you can very well have a series of messages each creating and closing
a stream. Similarly you could have a client send HEADERS followed by
RST_STREAM. Any observator outside would see series of +1/-1 and a
concurrency that never exceeds the number of subsequent creations
before an RST.

> This instinct is largely informed by

For me this is distinct, because in your case the HEADERS frame carries
the END_STREAM bit which closes the stream. So in fact between PUSH_PROMISE
and HEADERS it exists. If for any reason your agent sends a series of PP,
then can't send for a while due to poor network conditions, then sends a
series of HEADERS+ES you clearly see that the concurrency really exists.
It's just that in your specific case it's very ephemeral and you can
arrange for it never to exceed 1.

Cheers,
Willy

---

From: Mike Bishop <[email-masked]>
Date: Fri, 8 Feb 2019 23:40:46 +0000

From 5.1:  "For the purpose of state transitions, the END_STREAM flag is
   processed as a separate event to the frame that bears it; a HEADERS
   frame with the END_STREAM flag set can cause two state transitions."

This means that the frame causes two events -- increasing the number of concurrent streams, then decreasing it again.  If the increase violates the limit, the limit has been violated -- regardless of the fact that you pop back below the limit as the next event.

Of course, that also means that despite your limit of 5, you could have twenty such HEADERS-w/-END_STREAM in a row and be perfectly compliant.

-----Original Message-----
From: Cory Benfield <[email-masked]> 
Sent: Friday, February 8, 2019 8:43 AM
To: [email-masked]
Subject: Are HTTP/2 state changes atomic with respect to SETTINGS_MAX_CONCURRENT_STREAMS?

Hey folks,

While implementing (yet another) HTTP/2 stack, I have bumped into an edge case that I hadn't noticed before and wanted to get feedback from the WG about what the consensus interpretation is.

> "reserved" states do not count toward the stream limit.

So far so clear. My question is this: if a server reserves a stream, and then on the reserved stream sends a HEADERS frame with END_STREAM set, does the reserved stream ever count against SETTINGS_MAX_CONCURRENT_STREAMS?

This can be thought about through this thought experiment. Imagine a client sets SETTINGS_MAX_CONCURRENT_STREAMS to 5. The server sends six PUSH_PROMISE frames, and then opens 5 streams with HEADERS(END_HEADERS). Then, the server sends
HEADERS(END_HEADERS,END_STREAM) on the sixth reserved stream. Does this trigger a violation of SETTINGS_MAX_CONCURRENT_STREAMS?

RFC 7540 never quite says whether or not HEADERS + END_STREAM triggers atomic or sequential state transitions. § 5.1 says (while describing the idle state):

> Sending or receiving a HEADERS frame causes the stream to become 
> "open".  The stream identifier is selected as described  in Section 
> 5.1.1.  The same HEADERS frame can also cause a stream to immediately 
> become "half-closed".

This says "immediately", without defining the semantics of immediacy.
This text stands in contrast to the text describing the reserved states, which says:

> The endpoint can send a HEADERS frame.  This causes the stream to open 
> in a "half-closed (remote)" state.

This is made more complex by the stream state diagram, which implies that the END_STREAM transition occurs separately from the HEADERS transition.

My instinct is to say that these streams do not count against SETTINGS_MAX_CONCURRENT_STREAMS. This instinct is largely informed by Martin's previous characterisation of RFC 7540 as being written "as though headers were free". In a model where headers cost nothing, a stream guaranteed to be made only of headers never counts against SETTINGS_MAX_CONCURRENT_STREAMS.

That said, I'm interested in knowing what other implementations do. We should also consider whether it is worth drafting an erratum to attempt to clarify the state transitions of END_STREAM.

Thanks,

Cory

---

From: Willy Tarreau <[email-masked]>
Date: Sat, 9 Feb 2019 07:57:37 +0100

On Fri, Feb 08, 2019 at 11:40:46PM +0000, Mike Bishop wrote:
> This means that the frame causes two events -- increasing the number of
> concurrent streams, then decreasing it again.

I was surprised by this assertion, until I found that streams in the
reserved state are not counted. Do you have an idea why it's done this
way ? This means that a server can trivially DoS a client or intermediary
by pushing 1 billion streams that must be memorized and are not accounted
for :-/

Willy

---

From: Martin Thomson <[email-masked]>
Date: Mon, 11 Feb 2019 10:18:08 +1100

> by pushing 1 billion streams that must be memorized and are not accounted

Yep.  There is no practical limit on push in HTTP/2.  We fixed that in HTTP/3.  Well, it would be impossible not to fix this in some way, but we doubly fixed it anyway.

As for the original question, I think that Mike's interpretation is closest to intent.  If you have 5 streams open and a limit of 5, then opening another would be a violation of expectations.

p.s., I find it amusing when people start to read meaning into words.  Remember that RFCs were written by humans in something of a hurry and without the benefit of experience.  It is usually best to consider first what might have been intended before wondering about the relative placement of certain words.

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 11 Feb 2019 07:55:09 +0100

On Mon, Feb 11, 2019 at 10:18:08AM +1100, Martin Thomson wrote:
> Yep.  There is no practical limit on push in HTTP/2.  We fixed that in
> HTTP/3.  Well, it would be impossible not to fix this in some way, but we
> doubly fixed it anyway.

I think even for H2 we could address this, because I find it extremely
unlikely that some real workloads depend on the unbound aspect of this.
The change could be as simple as sayng that the stream is counted when
it is created (PUSH_PROMISE) just the way it works in the other direction.
And it most likely matches what implementations can naturally do. I would
not be surprised if some of them continue to count the allocated streams
towards the limit anyway.

> As for the original question, I think that Mike's interpretation is closest
> to intent.  If you have 5 streams open and a limit of 5, then opening another
> would be a violation of expectations.

Yes I agree.

> p.s., I find it amusing when people start to read meaning into words.
> Remember that RFCs were written by humans in something of a hurry and without
> the benefit of experience.  It is usually best to consider first what might
> have been intended before wondering about the relative placement of certain
> words.

Definitely! This is why I personally don't like when we go too much into
the algorithms or code-like sequence in RFCs, and I strongly prefer to
illustrate corner cases and possible solutions to better deliver the intent
and let implementers adapt to this.

Willy

---

From: Martin Thomson <[email-masked]>
Date: Mon, 11 Feb 2019 19:04:34 +1100

> towards the limit anyway.

That would be a breaking change, so you would want to signal it.  And I'm not sure that it would place any meaningful limit on the number of pushes.  You can still send PUSH_PROMISE and fulfill the promise without any feedback, meaning that as long as you can complete the entire cycle, you can send unbounded pushes if even a single push is allowed.  The only meaningful limit in that case would be TCP flow/congestion control.

The real fix is to add feedback into the loop and force the server to wait until the client allows it.  The MAX_PUSH_ID in h3 does that; a similar fix could be used here.

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 11 Feb 2019 10:17:16 +0100

On Mon, Feb 11, 2019 at 07:04:34PM +1100, Martin Thomson wrote:
> That would be a breaking change, so you would want to signal it.

Unless everyone agrees it's a bug :-)

> And I'm not
> sure that it would place any meaningful limit on the number of pushes.

I'm not speaking about a limit on the number of pushes, but on the number
of allocated streams, which are immediately created in the reserved state
once the PUSH_PROMISE frame is seen. If I were to implement push in haproxy,
I would have no choice but to enforce this limit anyway because memory is
not an infinite resource.

The problem is that the period between PUSH_PROMISE and HEADERS consumes
memory that is not accounted for. I'd just want to be sure this period is
covered by the count. That basically means that if a client says it
supports up to 100 concurrent streams, there are no more than 100 consecutive
PP frames without a HEADERS or DATA frame carrying an ES flag in the middle.
Not only I don't see this as an unreasonable expectation, but I do find the
opposite unreasonable.

> You
> can still send PUSH_PROMISE and fulfill the promise without any feedback,
> meaning that as long as you can complete the entire cycle, you can send
> unbounded pushes if even a single push is allowed.

That's perfectly fine because then streams are allocated and released.

> The real fix is to add feedback into the loop and force the server to wait
> until the client allows it.  The MAX_PUSH_ID in h3 does that; a similar fix
> could be used here.

It addresses a different problem in my opinion (though probably a very valid
one) and fixes the unbounded memory issue as a byproduct.

Cheers,
Willy

---

From: Stefan Eissing <[email-masked]>
Date: Mon, 11 Feb 2019 11:18:15 +0100

> Am 11.02.2019 um 10:17 schrieb Willy Tarreau <[email-masked]>:
> 

Alas, the limited memory is also true for httpd. I was rather hoping haproxy found a way around this...

> Not only I don't see this as an unreasonable expectation, but I do find the

I agree. Servers should count PPs agains the stream limit.

However the question remains what Cory should implement here? 

If there is a scenario where a near unlimited number of PPs can be triggered, this becomes a DoS vector either way. Experience says that an early and deterministic PROTOCOL_ERROR might serve us better than some dynamic mitigation that does not really solve the problem but makes breakage more obscure.

- Stefan

PS. httpd's mod_proxy_http2 does disable PUSH on backend connections. With 103 Early Hints, there seems to be no benefit on low latency.

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 11 Feb 2019 11:23:45 +0100

Hi Stefan,

> However the question remains what Cory should implement here? 

At the very least he should respect what the protocol says, i.e. +1
when seeing the HEADERS frame, check the limit then -1 when seeing
ES on the same frame. The state machine shows multiple steps for a
possible single state, indicating checks must be performed following
a strict sequence.

> If there is a scenario where a near unlimited number of PPs can be triggered,
> this becomes a DoS vector either way. Experience says that an early and
> deterministic PROTOCOL_ERROR might serve us better than some dynamic
> mitigation that does not really solve the problem but makes breakage more
> obscure.

Agreed.

> PS. httpd's mod_proxy_http2 does disable PUSH on backend connections. With
> 103 Early Hints, there seems to be no benefit on low latency.

Same for haproxy. Eventhough 103 is still young, it does have a certain
number of benefits over push and is (in my opinion) much more elegant.

Willy

---

From: Mike Bishop <[email-masked]>
Date: Mon, 11 Feb 2019 17:58:11 +0000

Two reasons, I think....

Separation of PUSH_PROMISE and stream concurrency was used as a predecessor to 103 -- if a client permitted push but set the max streams to zero, then the sequence of promises just becomes a stream of suggested dependent resources that can be delivered at any point during the response rather than only at the beginning.

The attack we were concerned about at the time was giving you a partial response and forcing you to buffer state for it, then another, then another, and never actually finish anything.  If you have fully consumed a push, you can flush the state, either by delivering it to the application or by discarding it entirely.  Since the TCP bytestream enforces consuming everything in order, you'll be done with one push before you begin consuming another -- from the HTTP layer's perspective, you *do* only have 5 outstanding no matter how many are in the pipe.  If the responses are coming faster than you can keep up, then TCP will generate backpressure.  If the server doesn't want that, it needs to moderate how much it pushes to how much it can send.

The DoS this permits is blocking the actual response behind lots of pushes -- something the server can do anyway by simply withholding the response.  The true cost is in HPACK processing all the promises and responses -- we chose to implement a "fast path" in the HPACK processor which updates table state and discards all output to mitigate this.

-----Original Message-----
From: Willy Tarreau <[email-masked]> 
Sent: Friday, February 8, 2019 10:58 PM
To: Mike Bishop <[email-masked]>
Cc: Cory Benfield <[email-masked]>; [email-masked]
Subject: Re: Are HTTP/2 state changes atomic with respect to SETTINGS_MAX_CONCURRENT_STREAMS?

On Fri, Feb 08, 2019 at 11:40:46PM +0000, Mike Bishop wrote:
> This means that the frame causes two events -- increasing the number 
> of concurrent streams, then decreasing it again.

I was surprised by this assertion, until I found that streams in the reserved state are not counted. Do you have an idea why it's done this way ? This means that a server can trivially DoS a client or intermediary by pushing 1 billion streams that must be memorized and are not accounted for :-/

Willy

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 11 Feb 2019 19:46:33 +0100

On Mon, Feb 11, 2019 at 05:58:11PM +0000, Mike Bishop wrote:
> The attack we were concerned about at the time was giving you a partial
> response and forcing you to buffer state for it, then another, then another,
> and never actually finish anything.

In the end that's exactly what we currently have : a PUSH_PROMISE frame
creates a stream on the client, which needs to buffer some elements from
this frame, until possibly forever (even due to server bugs where the
stream is lost there and the HEADERS frame never delivered).

> If you have fully consumed a push, you
> can flush the state, either by delivering it to the application or by
> discarding it entirely.

Sure but my point was regarding the cases where you can't consume it
because it is never completely sent.

(...)
> The DoS this permits is blocking the actual response behind lots of pushes --
> something the server can do anyway by simply withholding the response.

But if the stream was counted from the PP frame, that would hold true
as well.

Willy

---

From: Cory Benfield <[email-masked]>
Date: Mon, 18 Feb 2019 11:34:46 +0000

> However the question remains what Cory should implement here?

With thanks to Mike, my first question was answered: HEADERS +
END_STREAM is not atomic, so it causes two state transitions, and so a
HEADERS + END_STREAM frame after a PUSH_PROMISE can cause a violation
of SETTINGS_MAX_CONCURRENT_STREAMS. I'll some tests for this and
enforce it appropriately in my code.

As to the second question regarding unbounded PPs, I'll likely lift an
approach from Netty, which is to enforce an entirely separate limit
internally. If this limit is exceeded we'll simply RST_STREAM in
response to any pushed stream and never deliver frames to users. This
is safe enough to do, given the advisory nature of pushes anyway.