Chrome Server-Sent Event Parsing
Server-sent events are a standard for web servers to stream a sequence of events to a browser over a single HTTP connection. You can view them as a simpler, unidirectional, alternative to websockets (that doesn't require support from any middleboxes), or as an optimization over one-event-per-request longpolling.
The wire format for an event consists of a number of newline-separated key-value pairs, in a simple key: value format. For instance, the documentation provides the example event:
event: userconnect data: {"username": "bobby", "time": "02:33:48"}
Until recently, Chrome's parser for this format worked strictly line-at-a-time, maintaining no additional state. When it received data from the server, it appended the data to its buffer, and then attempted to parse a k-v pair off the first line:
void EventSource::didReceiveData(const char* data, unsigned length) { append(m_receiveBuf, m_decoder->decode(data, length)); parseEventStream(); }
If it didn't find a complete event (e.g. missing newline), the parser just stopped, waiting for the next batch of data to arrive.
This works well as long each line arrives in a relatively small number of packets. However, if you have a very long line (e.g. a 16MB data field), it will (of necessity) be chunked into many smaller packets on the wire, which will end up getting passed to didReceiveData separately. In response to each packet, the parser will scan the entire line to the end, note the lack of newline, and then abort. Thus, we will do N/chunk-size scans of our line, each one scanning more and more bytes, resulting in an overall quadratic blowup!
The fix makes the new parser more stateful, so that it keeps track of its progress in the parse across each new packet, and avoids scanning the buffer O(N) times.
(bug submitted by @whyareallthesenamestakenalready)
