ysbaddaden/http2

Implement Flow Control (outgoing)

ysbaddaden opened this issue · 6 comments

ysbaddaden commented

This requires to implement:

  • support for WINDOW_UPDATE frames (partially done);
  • count bytes consumption (stream) when sending DATA frames;
  • count bytes consumption (connection) when sending DATA frames;
  • don't send DATA frames that would cause overflow;
  • send has many bytes in DATA frames as possible;
  • send 0 bytes in DATA frames (for END_STREAM flag to be delivered);
  • send pending DATA frames after receiving a WINDOW_UPDATE;
  • add a waiting mecanism so a coroutine can put itself to sleep until enough bandwidth is available.

References:

ysbaddaden commented

This will most likely involve extracting the frame sender coroutine from HTTP2::Connection into it's own HTTP2::Connection::FrameSender class, capable to store pending frames until enough bandwidth is allowed.

ysbaddaden commented

Mostly implemented, except for the connection window size... that I'm not sure I really understand.

ysbaddaden commented

Implemented but... totally broken.
Fixed in aa7d4bd

ysbaddaden commented

There are two h2spec failures left (http2/6.9.2/1 and http2/6.9.2/2):

    × 1: Changes SETTINGS_INITIAL_WINDOW_SIZE after sending HEADERS frame     
      -> The endpoint MUST adjust the size of all stream flow-control windows.
         Expected: DATA Frame (length:1, flags:0x00, stream_id:1)             
           Actual: HEADERS Frame (length:16, flags:0x04, stream_id:1)         

    × 2: Sends a SETTINGS frame for window size to be negative                
      -> The endpoint MUST track the negative flow-control window.            
         Expected: DATA Frame (length:1, flags:0x00, stream_id:1)             
           Actual: DATA Frame (length:2, flags:0x00, stream_id:1)

Fixed in 40eedfd

ysbaddaden commented

Last thing to achieve: we MUST count outgoing window size at the connection level (not just the stream) and prevent sending more DATA frames until we receive a WINDOW_UPDATE for stream #0.

ysbaddaden commented

Sigh, I guess I'm doing it all wrong.

First, some vocabulary (hopefully I got it correctly):

  • CONNECTION: the HTTP/2 connection —basically a TCP socket with/out SSL;
  • STREAM: a HTTP request/response —multiplexed, so we can have many in parallel;
  • WINDOW_SIZE: how many bytes a STREAM may send OR how many bytes the whole CONNECTION may send (sum of sent bytes of all STREAM) in flow-controlled frames (i.e. DATA frames);
  • WINDOW_UPDATE frame: increase the WINDOW_SIZE for the CONNECTION or a STREAM.

Currently, a STREAM is responsible for creating DATA frames, respecting it's personal outbound WINDOW_SIZE by cutting the bytes to send to fit within the allowed limit, exhausting it down to zero if possible, then blocking the current fiber once exhausted, then resuming it when the stream window size is increased by a WINDOW_UPDATE frame.

It works as expected... for one stream. Try to multiplex many and you'll quickly get a GOAWAY (CONTROL_FLOW_ERROR) frame. Okay, I don't respect the CONNECTION WINDOW_SIZE. I have a fiber dedicated to send frames (so concurrent writers don't mess the protocol), so if a DATA frame doesn't fit the connection window size, let's skip/requeue and try the next one? Sounds legit? Nope: deadlock 😭

What happens is the receiver is waiting for DATA frames, and it doesn't care that the connection window size ain't big enough to fit at least one stream's window size. If we can't send any DATA frame for any stream, despite each stream being given enough bandwidth, then: the sender waits forever + the receiver waits forever = deadlock :trollface:

I guess we must (try to) exhaust the CONNECTION WINDOW_SIZE, which means a STREAM isn't capable to create DATA frames and pass them to the sending fiber: it must pass bytes directly to some kind of per-connection-flow-control-cutting-and-respecting-routine-with-priority-tree-graph-of-the-returning-living-dead-from-halloween that will cut bytes and create the DATA frames to exhaust-yet-respect-limits of both the stream & connection window sizes.

I.e., yet another complexity level :feelsgood: