Subject: END_STREAM flag and trailing headers

From: Greg Wilkins <[email-masked]>
Date: Wed, 7 May 2014 16:27:16 +0200

Sorry if this has previously been discussed, but my searches of spec/list
don't find it... so...

What is the reason for the multiple statements in the spec like:

  A HEADERS frame bearing an END_STREAM flag can be followed by
CONTINUATION frames.

Specifically why isn't the END_STREAM flag set iff the frame is the last
frame in that stream (in that direction)?  Why are CONTINUATION frames
allowed after the end of the stream?

As a side note that there is some confusion of the sequence of continuation
frames ends with just and END_HEADERS flag, or does it need both the
END_HEADERS and END_STREAM?  Should each of the CONTINUATION frames sent
before the final one have the END_STREAM bit set?

But back to the main question, what purpose does it serve?  Is it because
when a trailing HEADERS frame is sent, the HPACK encoding is not sure how
many frames will be needed to send the headers, so the first one is marked
with the END_STREAM and any overflows can be sent afterwards?      If so,
why not just set the end stream on the last continuation frame?

It will be clear to any HTTP receiver that the stream is about to end
because they have received a HEADERS frame after the initial headers and/or
data, so having the END_STREAM bit set provides no extra information other
than devaluing the clear meaning of the end of the stream.   Currently we
can only stop expecting more frames for a stream if ( we have seen
END_STREAM seen on a HEADERS (potentially some frames ago)  && we receive
END_HEADERS ) || (We received a DATA frame with END_STREAM) .

This is really complex and I'd like to understand why?

thanks

-- 
Greg Wilkins <[email-masked]>
http://eclipse.org/jetty HTTP, SPDY, Websocket server and client that scales
http://www.webtide.com  advice and support for jetty and cometd.

---

From: Martin Thomson <[email-masked]>
Date: Wed, 7 May 2014 10:51:52 -0700

On 7 May 2014 07:27, Greg Wilkins <[email-masked]> wrote:
>   A HEADERS frame bearing an END_STREAM flag can be followed by CONTINUATION
> frames.

There's basically two ways to roll this (I hope that you can infer my
shorthand correctly here...):

What we have is a formulation for a stream that looks like this:

H C C C(EH) D D D D D H(ES) C C C(EH)

We discussed the logical alternative, which was in the draft for quite
a long time:

H C C C(EH) D D D D H C C C(ES,EH)

The problem came about when we looked at the use of CONTINUATION
frames for PUSH_PROMISE.  If we wanted to do the latter, we would have
to permit the use of END_STREAM on CONTINUATION if it was used after
HEADERS, but prohibit it if it followed PUSH_PROMISE.

The solution we came to was what you see in the spec.

> before the final one have the END_STREAM bit set?

CONTINUATION doesn't define an END_STREAM bit.

> than devaluing the clear meaning of the end of the stream.

That's not quite right, we permit the sending of additional HEADERS
frames, but they can be treated as line noise (i.e., discarded).  See
http://http2.github.io/http2-spec/#HttpSequence, which says: "Header
blocks after the first that do not terminate the stream are not part
of an HTTP request or response. "

> Currently we

Correct, though it might be better to consider any CONTINUATION frame
as part of the HEADERS frame for the purposes of stream handling.
That simplifies the logic considerably.  That means that reading the
full header block will cause the connection to be blocked, but that's
a natural consequence of having oversized header blocks anyway:
nothing can be interspersed with CONTINUATION frames.

---

From: Greg Wilkins <[email-masked]>
Date: Fri, 9 May 2014 00:14:37 +0200

Martin,

again apologies for raising this long after it was discussed.    I found
and read https://github.com/http2/http2-spec/issues/228.

However, if I have this right, this now means that a PUSH_PROMISE, must
have data?    I don't see why that should be, as it may be that a server
discovers needs to push 30x redirects.

I have to say I don't fully understand what issue an intermediary would
have if it ignores push promises that do not have data?    But surely it
would be better to find a fix for that rather than complicate END_STREAM,
which should be a very straight forward flag

Actually I think that it is poor protocol layering to have to interpret the
type of a frame in order to workout stream boundaries.    END_STREAM should
be a flag available on all frames regardless of type. A stream should
exists from the first frame sent with its ID until a frame with the
END_STREAM flag set.  No frame types need to be considered.      Sure that
allows invalid sequences of frame types, but then there will always be
invalid sequences of frame types.

It is going to be a real pain in the future if every time a new frame type
is introduced we have to go back and work out what that means for stream
creation/destruction.

cheers

On 7 May 2014 19:51, Martin Thomson <[email-masked]> wrote:

> CONTINUATION

---

From: Martin Thomson <[email-masked]>
Date: Thu, 8 May 2014 15:29:26 -0700

On 8 May 2014 15:14, Greg Wilkins <[email-masked]> wrote:
> However, if I have this right, this now means that a PUSH_PROMISE, must have
> data?    I don't see why that should be, as it may be that a server

PUSH_PROMISE has no data associated with it directly.  A PUSH_PROMISE
is a single frame (plus CONTINUATION) that does not end a stream
because it sits on another stream (we use the term "associated stream"
in the draft).  It has no impact on the state of the associated
stream, and doesn't end that stream.

PUSH_PROMISE includes a synthesized request.  It's the response that
results from the PUSH_PROMISE (on the promised stream) that could
contain data.  That response follows the normal structure for a
stream, it's just that PUSH_PROMISE causes the promised stream to
start later in the normal state machine, since the request is carried
in the PUSH_PROMISE.

So it's perfectly valid to push a 3xx redirect.  Or even a 5xx if you
really feel like it.  Entity bodies are merely optional on pushed
responses.  (They are not at all possible on pushed requests, despite
there being some DAV cases that describe uses for entity bodies on
safe methods, we decided against supporting that complication.)

Say that you get a request for /foo on stream 7.  Maybe you want to send this:

Stream7: PUSH_PROMISE GET /bar ;Stream8
Stream7: HEADERS 200 OK (for /foo)
Stream7: DATA ...for /foo
Stream8: HEADERS[END_STREAM] 3xx Location: /bar100
Stream7: PUSH_PROMISE GET /bar100; Stream10
Stream10: HEADERS 200 OK
Stream10: DATA .... for /bar (actually /bar100)

> Actually I think that it is poor protocol layering to have to interpret the type of a
> frame in order to workout stream boundaries.

I used to think the same, and if you care to do some git spelunking,
there's good evidence of that.  I think that it was at the point that
I went through the process of working through the state machine that I
changed my mind.  What we've actually done here is conflate some of
the stream control functions with the application semantics functions
in the interests of efficiency.

---

From: Julian Reschke <[email-masked]>
Date: Fri, 09 May 2014 08:16:37 +0200

On 2014-05-09 00:29, Martin Thomson wrote:
> ...
> ...

I still believe this to be a mistake.

The question about a safe method that allows a request body comes up 
over and over, and right now people use POST for it. If we ever define 
that method, it won't be supported in HTTP2 push.

Best regards, Julian

---

From: David Krauss <[email-masked]>
Date: Sat, 10 May 2014 11:08:05 +0800

On 2014–05–09, at 2:16 PM, Julian Reschke <[email-masked]> wrote:

> The question about a safe method that allows a request body comes up over and over, and right now people use POST for it. If we ever define that method, it won't be supported in HTTP2 push.

Can you clarify? Pushes eliminate (or “skip over”) the request by definition. Pushing a redirect or error simply anticipates a client request with such a response. POST (or anything with a request body) would usually bypass prior PUSH_PROMISEs along with the rest of the cache. An exception to this rule could be defined in HTTP/2 using multiple header blocks, and perhaps segmentation: push the request, then the response. But, it would have to be an application-specific extension for now.

---

From: Julian Reschke <[email-masked]>
Date: Sat, 10 May 2014 09:36:09 +0200

> Can you clarify? Pushes eliminate (or “skip over”) the request by definition. Pushing a redirect or error simply anticipates a client request with such a response. POST (or anything with a request…

I'm not sure *what* needs to be clarified. Can you clarify?

The use case is pushing responses for safe requests that *do* have q 
request body, such as a directory update (PROPFIND).

Best regards, Julian

---

From: David Krauss <[email-masked]>
Date: Sat, 10 May 2014 16:01:04 +0800

> I'm not sure *what* needs to be clarified. Can you clarify?

Well, I already did. The above paragraph explains that PUSH_PROMISE does not allocate a spot for any part of a request, never mind the request body. I also propose a solution to the problem.

> The use case is pushing responses for safe requests that *do* have q request body, such as a directory update (PROPFIND).

What do you think such a push would look like? Perhaps a progressive change-set? What need is there for a fake request body, if the response already identifies the changed properties? Specific application protocols will need to refine their caching schemes to fit pushing.

---

From: Julian Reschke <[email-masked]>
Date: Sat, 10 May 2014 10:15:18 +0200

> Well, I already did. The above paragraph explains that PUSH_PROMISE does not allocate a spot for any part of a request, never mind the request body. I also propose a solution to the problem.

Yes, that's the problem. Another simple approach would be to cram the 
payload into a ":payload" header field (and to Vary on that), but what 
I'm looking for is a protocol where we don't need to find workarounds 
for an IMHO legitimate use case.

> What do you think such a push would look like? Perhaps a progressive change-set? What need is there for a fake request body, if the response already identifies the changed properties? Specific appl…

That's an orthogonal issue. With PROPFIND it could be a full new 
directory listing, just an update for an individual entry, or a new 
entry. In CalDAV/CardDAV there are REPORT requests that allow reporting 
incremental changes, for instance.

But please do not conclude that this is a "WebDAV thing". As mentioned 
earlier, I believe we really should have a new method that is defined to 
be safe but does have a payload, so that we can get rid of the very 
widely used "POST-for-query" pattern.

Best regards, Julian

---

From: Martin Thomson <[email-masked]>
Date: Mon, 12 May 2014 10:05:23 -0700

On 10 May 2014 00:36, Julian Reschke <[email-masked]> wrote:
> The use case is pushing responses for safe requests that *do* have q request
> body, such as a directory update (PROPFIND).

Yes, this is a perfectly valid use case, but we didn't find enough
support for it.  That's all.

The counterarguments were, if I recall:

1. as requests increase in complexity, the odds that a server
correctly synthesizes a request that the client can subsequently use
diminishes
2. adding a request body represents a non-trivial increase in protocol
complexity; this would probably require an additional state in the
promised stream that would be used for sending the request entity

Other than that, there isn't much more to be said.  I'm sure that if
circumstances change significantly, we can reopen the issue.

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 19 May 2014 15:58:39 +0200

On 9 May 2014 00:29, Martin Thomson <[email-masked]> wrote:

> have
> > data?
> PUSH_PROMISE has no data associated with it directly.
>

Sorry my bad interpretation of the spec.   It could definitely use an
example like yours.

> in the interests of efficiency.

I find that scary!  in the battle of compromises of efficiency vs
complexity, I have rarely seen efficiency achieved though complexity.  In
this case I see little efficiency to be gained by have a few frame types
not support END_STREAM when all frame types so far defined have many spare
flag bits anyway.  But the cost in complexity is significant, not least in
poor CPU branch prediction, but also in likely bugs and future constraints
on protocol development.

More over, the spec does not contain a formalisation of what is a legal
stream. Section 5.1 looks to be a formalisation of stream states, but it is
not because you are still required to read the detailed text to interpret
the state machine and i do not think the text descriptions of the states
adequately describe what can/can't be done in each state.

Problems with 5.1 include:

   - The text description of PUSH_PROMISE does not adequately describe the
   fact that two streams are involved and that it is the transmission of a
   PUSH_PROMISE on one stream that puts a different stream into the reserved
   states.
   - The half closed states are insufficient as they do not capture the
   sending of CONTINUATION frames after a frame with the ES bit.  The text
   "cannot be used for sending frames" is wrong as CONTINUATION, RST_STREAM
   and WINDOW_UPDATE frames at least can be sent from this state.   A proper
   formalisation probably needs to split this state into trailer and half
   closed states to indicate if the close was invoked via a DATA or HEADER
   frame.
   - The closed state suffers similar problems, as it currently can be
   entered by a half closed stream sending or receiving a frame with ES set,
   even though it has not yet received all the CONTINUATION frames that it
   might receive, or sent all the CONTINUATION frames that it may send.
   - A stream in closed state may receive frames (eg PUSH_PROMISE) that it
   must act on and reserve the stream.  There appears no end to this state as
   RST_STREAM has no response, so an implementation that sends a RST_STREAM
   will have a closed stream that it will have to monitor forever for
   potential PUSH_PROMISES!  (why doesn't RST_STREAM just push the stream into
   half closed, so the other end can acknowledge it?)

Some of these issues might be able to be solved with a better formalisation
of the stream state,  I started to give that a go as follows:

                                         +--------+
                                   PP    |        |    PP
                                ,--------|  idle  |--------.
                               /         |        |         \
                              v          +--------+          v
                       +----------+          |           +----------+
                       |          |          | H         |          |
                   ,---| reserved |          |           | reserved |---.
                   |   | (local)  |          |           | (remote) |   |
                   |   +----------+          |           +----------+   |
                   |      |                  v                   |      |
  +---------+      |      |              +--------+              |
 |    +---------+   |         |      |      |        H(ES) |        |
H(ES)       |      |    |         |  | trailer |<---- | ---- |
-------------|        |------------- | ---- | -->| trailer |
  | (remote)|      |      |              |        |              |
 |    | (local) |
  |         |      |      |     H(ES,EH) |  open  |  H(ES,EH)    |
 |    |         |
  +---------+      |      |       D(ES)  |        |  D(ES)       |
 |    +---------+
          \        |      | H    ,-------|        |-------.      | H    |      /
     C(EH) \       |      |     /        |        |        \     |
 |     /C(EH)
            \      |      v    v         +--------+         v    v      |    /
             \     |   +----------+          |           +----------+   |   /
              `--- | ->|   half   |          |           |   half   |<- | -'
                   |   |  closed  |          | R         |  closed  |   |
                   |   | (remote) |          |           | (local)  |   |
                   |   +----------+          |           +----------+   |
                   |        |                v                 |        |
                   |        |  ES / R    +--------+  ES / R    |        |
                   |        `----------->|        |<-----------'        |
                   |  R                  | closed |                  R  |
                   `-------------------->|        |<--------------------'
                                         +--------+

      H:  HEADERS frame (with implied CONTINUATIONs)
      PP: PUSH_PROMISE frame (with implied CONTINUATIONs)
      D(ES): DATA frame with END_STREAM flag
      H(ES,EH): HEADER frame with END_STREAM and END_HEADER flags
      H(ES) : HEADER frame with END_STREAM flag
      C(EH) : CONTINUATION frame with END_HEADER flag
      R:  RST_STREAM frame

But that is still insufficient as it needs to handle the case of H(ES) from
the other end while you are in one of the trailer states.  This get's way
too complex for one state machine.   So perhaps we should formalise the
half state of a stream in isolation from the other half (as this is probaly
how it will be implemented), but the two halves are not truly independent.

I think the fundamental problem is simply that the stream state is too
complex.  If it cannot be formalised without resorting to complex textual
descriptions, then that is a big worry for the ability of the protocol to
understood, implemented, tested, debug, hacked, exploited, etc!

I think that we should really reconsider reinstating the ES bit on all
frames and then we can have a much simpler formalisation of the stream
state and we can have some definitive statements like:

   - After sending an ES flag, the stream is half closed local, which means:
      - it shall not send any DATA, HEADER or CONTINUATION frames
      - it shall ignore any WINDOW_UPDATE or RST_STREAM frames sent
   - After receiving an ES flag, the stream is half closed remote, which
   means:
      - any frames other than WINDOW_UPDATE or RST_STREAM is a stream error
   - After sending and receiving an ES flag, the stream is closed, which
   means:
      - no frames should be sent or received on the stream.

Further:

   - The RST_FRAME must have the ES flag and on receipt of a RST_FRAME in
   any state other that closed or half closed, then a REST_FRAME frame should
   be immediately sent in reply.

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 19 May 2014 18:20:50 +0200

I had another go at the state machine for how the protocol is now and I
think this is correct?

I've attached it rather than include inline as it is much larger and will
probably wrap in many email readers.

I've added states for quarter closed (trailer started), three quarter
closed (you were half closed and then a trailer started) and two quarter
closed (both sending and receiving a trailer).

It's obviously not impossible, but I still think it is over complex and
that the spec needs to have some kind of formal definition of stream
lifecycle such as a full state machine like this or maybe BNF of legal
frame sequences?

regards

On 19 May 2014 15:58, Greg Wilkins <[email-masked]> wrote:

>    - The text description of PUSH_PROMISE does not adequately describe
>    the fact that two streams are involved and that it is the transmission of a
>    - A stream in closed state may receive frames (eg PUSH_PROMISE) that
>    it must act on and reserve the stream.  There appears no end to this state
>    as RST_STREAM has no response, so an implementation that sends a RST_STREAM
> Some of these issues might be able to be solved with a better
> formalisation of the stream state,  I started to give that a go as follows:
>
>                                          +--------+
>                                    PP    |        |    PP
>   +---------+      |      |              +--------+              |      |    +---------+   |         |      |      |        H(ES) |        |  H(ES)       |      |    |         |  | trailer |<---- | ---- | -------------|        |------------- | ---- | -->| trailer |
>   | (remote)|      |      |              |        |              |      |    | (local) |
>   |         |      |      |     H(ES,EH) |  open  |  H(ES,EH)    |      |    |         |
>   +---------+      |      |       D(ES)  |        |  D(ES)       |      |    +---------+
>      C(EH) \       |      |     /        |        |        \     |      |     /C(EH)
> But that is still insufficient as it needs to handle the case of H(ES)
> from the other end while you are in one of the trailer states.  This get's
> way too complex for one state machine.   So perhaps we should formalise the