6 ms·

I'm the author of the fastest open source HTTP server. Parsing HTTP 0.9, 1.0, and 1.1 is trivial. It's a walk in the park. It only takes about a hundred lines o

by jart 5y ago

I'm the author of the fastest open source HTTP server. Parsing HTTP 0.9, 1.0, and 1.1 is trivial. It's a walk in the park. It only takes about a hundred lines of code to create a proper O(n) parser. https://github.com/jart/cosmopolitan/blob/0b317523a0875d83d650ce8a7b288e3b3500fbba/net/http/parsehttpmessage.c#L54 https://github.com/jart/cosmopolitan/blob/0b317523a0875d83d6... The Joyent HTTP parser used by Node is very good but it's implemented in a way that makes the problem much more complicated than it needs to be. The biggest obstacle with high-performance HTTP message parsing is the case-insensitive string comparison of header field names. Some servers like thttpd do the naive thing and just use a long sequence of strcasecmp() statements. Joyent goes "fast" because it uses callbacks, which effectively punts the problem to the caller, and, for a few select headers which it handles itself, like Content-Length, it uses this really complicated internal "h_matching" thing for doing painstakingly written out hardcoded character compares. Redbean solves the problem by using better computer science: perfect hash tables. Thanks to gperf command. That makes the API itself much more elegant since the parser can not only go faster but return a hash-table like structure where individual headers can be indexed without performing string comparisons.

mariusor 5y ago
I think that implementing a proper state machine for the header parsing with ragel would give a more comprehensive result than using gperf or even the handmade one from your code. I think there are already some versions of the ragel code online, but they might be for other target programming languages.
- jart 5y ago
  I'm one of the authors of Ragel and I disagree with you. HTTP is trivial enough that you'd be better served writing the state machine yourself using a switch statement. See my GitHub link above for an example. The code easily ports to other languages, like Java. Lastly when it comes to Ragel and gperf, they both do two completely different things. Ragel would generate a prefix trie search in generated code which would have enormous code size compared to what gperf is doing, which is much faster. With gperf, you only need to consider exactly O(3) octets total to tell which header it is. After that, it does a single quick string compare to confirm it's one of the predetermined headers rather than some unknowable value.
  - mariusor 5y ago
    I apparently never paid enough attention to how in the spec there's a clear defined list and I always assumed that a "parser" should handle all valid header*ish looking pairs. Based on this consideration I was thinking that the ragel state machine would generate faster code for the non happy path (invalid non-ascii, or other types of error) at least in the GOTO version. When working on the full list it makes perfect sense to check the minimum amount of bytes for identifying headers, so thank you for the clarifications, very informative. :)
ysleepy 5y ago
I consider Header value parsing and URL parsing part of HTTP, those are certainly not trivial. The charset problems alone are a nightmare. Parsing the wire format is pretty breezy, (Don't forget trailers!)
- jart 5y ago
  Trailers can be parsed by invoking the function using something along the lines of ParseHttpMessage((struct HttpMessage){.t = kHttpStateName}, p, n) where you just tell the parser to skip the first-line states. Charset isn't a nightmare either. Headers are ISO-8601-1 so you just say {0300 | c >> 6, 0200 | c & 077} to turn them into UTF-8. It's not difficult. It might be if you want to support MIME. But this is HTTP we're talking about. It was made to be simple! We're talking Internet engineering on the lowest difficulty setting. Implement a TCP or SIP stack if you want hard.
  - cormacrelf 5y ago
    I think ysleepy might be referring to HTML charsets, which can be set in the HTTP header. They are a nightmare, I have come across HTML documents with so many “if lt IE 9” comments that they move the charset declaration out of the first 1000 bytes, causing browsers to ignore it and interpret as Latin 1. But yes, not actually anything to do with parsing HTTP.
nly 5y ago
Are you handling the obs-fold? Because this is something the joyent parser falls over at (a streaming parser must buffer the obs-fold to disambiguate). I don't see it in your code. If you handle it your parser can't be O(1) space. See the remark at the bottom of the Boost Beast parser docs for a hint at the trade off here: https://www.boost.org/doc/libs/1_75_0/libs/beast/doc/html/beast/ref/boost__beast__http__basic_parser.html https://www.boost.org/doc/libs/1_75_0/libs/beast/doc/html/be... I think the implementation is gold standard: https://github.com/boostorg/beast/blob/develop/include/boost/beast/http/detail/basic_parser.ipp https://github.com/boostorg/beast/blob/develop/include/boost...
- lttlrck 5y ago
  From the link: > Line folding is forbidden.
- jart 5y ago
  We are no longer required to support line folding so redbean doesn't (see RFC7230 §3.2.4) Do you know what if anything needs it?
javajosh 5y ago
>I'm the author of the fastest open source HTTP server Okay, I'll bite: What are you talking about? Fastest under what conditions, using what measurements? What is the project, and where is the analysis? EDIT: you probably mean redbean (https://redbean.dev/ https://redbean.dev/) - the source of which is, oddly, embedded within cosmopolitan. However the question about analysis stands.
- jart 5y ago
  Messages per second, latency, footprint, name it. Particularly if it's gzip encoded. See https://youtu.be/1ZTRb-2DZGs?t=717 https://youtu.be/1ZTRb-2DZGs?t=717 I'm working on giving redbean the fastest https serving too. Recently I've been helping to make the strongest elliptic curves go 3x faster.
  - javajosh 5y ago
    You seem to have written a glorious series of interlocking hacks which yields a small, tight, simple, fast, portable, useful nugget of functionality in a single file. Bravo. I really like it and will attempt to use it for something real. However, I fear that even this bit of magic doesn't address the central problem of our time, which is software distribution. I believe that the web has solved that problem, and although the web is currently abused by central power, and webapps tend to be thin, animated protocol viewers, it doesn't have to be that way. You've created/discovered a local (maybe global, given real-world limits) minima of what a binary executable can be, but this only finds the minima of the pain of traditional software distribution, but doesn't eliminate it. The real path forward, if I might be so bold, is to make a browser on top of cosmopolitan/redbean, and bring TBL's original dream of a singular client+server http/html runtime to modern fruition - but with additional superpowers that cosmo brings which I don't think TBL anticipated. No doubt some enterprising souls are already working to get Bellard's QuickJS into redbean to mimic node. Then you need window/drawing context, and the rest of the browser, including layout, could be done in (presumably equally tight) JS. Have you given any thought to exposing those drawing syscalls directly instead of delegating to the browser? And if you haven't and are interested, may I suggest Java's AWT v. SWT as an interesting case study in "where the indirection should go".
pornel 5y ago
HTTP/1 is deceptive, because you think "oh, I'll just read RFC 2616, make a state machine, and I'm done!". But then writing a browser-compatible HTTP/1 client is a whole another bag of problems that weren't even documented until recently. For example, Content-Length isn't just a single header with an integer, like the spec says. You need to support responses with multiple Content-Length headers and comma-separated lists of potentially contradictory lengths, and then perform garbage error-recovery the way Internet Explorer or Chrome did. Getting this wrong will make your client hang, consume garbage, or allow response stuffing. https://github.com/web-platform-tests/wpt/pull/10548/files https://github.com/web-platform-tests/wpt/pull/10548/files This problem does not exist in HTTP/2.
- cookiengineer 5y ago
  ^ This. Multiple responses, especially with chunked encodings, are really really hard to get right. Even more so when you have to be able to resume downloads due to socket instability.
cookiengineer 5y ago
Building an HTTP library myself, I have to disagree. I drop two things here to counterargue that HTTP is easy to parse: 206 multiple ranges (requests will not always be responded to, and ranges from servers are almost always invalid when resumed) and Transfer Encodings (br inside gzip inside deflate inside chunked, anyone?) Both headers are implemented spec incompliant by every single web server I've seen, including nginx, apache and others. Source: building a peer to peer web browser that shares its bandwidth (and cache and downloads) with trusted peers. [1] [1] https://github.com/tholian-network/stealth https://github.com/tholian-network/stealth

by jart 5y ago

mariusor 5y ago

I think that implementing a proper state machine for the header parsing with ragel would give a more comprehensive result than using gperf or even the handmade one from your code. I think there are already some versions of the ragel code online, but they might be for other target programming languages.

jart 5y ago
I'm one of the authors of Ragel and I disagree with you. HTTP is trivial enough that you'd be better served writing the state machine yourself using a switch statement. See my GitHub link above for an example. The code easily ports to other languages, like Java. Lastly when it comes to Ragel and gperf, they both do two completely different things. Ragel would generate a prefix trie search in generated code which would have enormous code size compared to what gperf is doing, which is much faster. With gperf, you only need to consider exactly O(3) octets total to tell which header it is. After that, it does a single quick string compare to confirm it's one of the predetermined headers rather than some unknowable value.
- mariusor 5y ago
  I apparently never paid enough attention to how in the spec there's a clear defined list and I always assumed that a "parser" should handle all valid header*ish looking pairs. Based on this consideration I was thinking that the ragel state machine would generate faster code for the non happy path (invalid non-ascii, or other types of error) at least in the GOTO version. When working on the full list it makes perfect sense to check the minimum amount of bytes for identifying headers, so thank you for the clarifications, very informative. :)

ysleepy 5y ago

I consider Header value parsing and URL parsing part of HTTP, those are certainly not trivial. The charset problems alone are a nightmare. Parsing the wire format is pretty breezy, (Don't forget trailers!)

jart 5y ago
Trailers can be parsed by invoking the function using something along the lines of ParseHttpMessage((struct HttpMessage){.t = kHttpStateName}, p, n) where you just tell the parser to skip the first-line states. Charset isn't a nightmare either. Headers are ISO-8601-1 so you just say {0300 | c >> 6, 0200 | c & 077} to turn them into UTF-8. It's not difficult. It might be if you want to support MIME. But this is HTTP we're talking about. It was made to be simple! We're talking Internet engineering on the lowest difficulty setting. Implement a TCP or SIP stack if you want hard.
- cormacrelf 5y ago
  I think ysleepy might be referring to HTML charsets, which can be set in the HTTP header. They are a nightmare, I have come across HTML documents with so many “if lt IE 9” comments that they move the charset declaration out of the first 1000 bytes, causing browsers to ignore it and interpret as Latin 1. But yes, not actually anything to do with parsing HTTP.

nly 5y ago

Are you handling the obs-fold? Because this is something the joyent parser falls over at (a streaming parser must buffer the obs-fold to disambiguate). I don't see it in your code. If you handle it your parser can't be O(1) space. See the remark at the bottom of the Boost Beast parser docs for a hint at the trade off here: https://www.boost.org/doc/libs/1_75_0/libs/beast/doc/html/beast/ref/boost__beast__http__basic_parser.html https://www.boost.org/doc/libs/1_75_0/libs/beast/doc/html/be... I think the implementation is gold standard: https://github.com/boostorg/beast/blob/develop/include/boost/beast/http/detail/basic_parser.ipp https://github.com/boostorg/beast/blob/develop/include/boost...

lttlrck 5y ago
From the link: > Line folding is forbidden.
jart 5y ago
We are no longer required to support line folding so redbean doesn't (see RFC7230 §3.2.4) Do you know what if anything needs it?

javajosh 5y ago

>I'm the author of the fastest open source HTTP server Okay, I'll bite: What are you talking about? Fastest under what conditions, using what measurements? What is the project, and where is the analysis? EDIT: you probably mean redbean (https://redbean.dev/ https://redbean.dev/) - the source of which is, oddly, embedded within cosmopolitan. However the question about analysis stands.

jart 5y ago
Messages per second, latency, footprint, name it. Particularly if it's gzip encoded. See https://youtu.be/1ZTRb-2DZGs?t=717 https://youtu.be/1ZTRb-2DZGs?t=717 I'm working on giving redbean the fastest https serving too. Recently I've been helping to make the strongest elliptic curves go 3x faster.
- javajosh 5y ago
  You seem to have written a glorious series of interlocking hacks which yields a small, tight, simple, fast, portable, useful nugget of functionality in a single file. Bravo. I really like it and will attempt to use it for something real. However, I fear that even this bit of magic doesn't address the central problem of our time, which is software distribution. I believe that the web has solved that problem, and although the web is currently abused by central power, and webapps tend to be thin, animated protocol viewers, it doesn't have to be that way. You've created/discovered a local (maybe global, given real-world limits) minima of what a binary executable can be, but this only finds the minima of the pain of traditional software distribution, but doesn't eliminate it. The real path forward, if I might be so bold, is to make a browser on top of cosmopolitan/redbean, and bring TBL's original dream of a singular client+server http/html runtime to modern fruition - but with additional superpowers that cosmo brings which I don't think TBL anticipated. No doubt some enterprising souls are already working to get Bellard's QuickJS into redbean to mimic node. Then you need window/drawing context, and the rest of the browser, including layout, could be done in (presumably equally tight) JS. Have you given any thought to exposing those drawing syscalls directly instead of delegating to the browser? And if you haven't and are interested, may I suggest Java's AWT v. SWT as an interesting case study in "where the indirection should go".

pornel 5y ago

HTTP/1 is deceptive, because you think "oh, I'll just read RFC 2616, make a state machine, and I'm done!". But then writing a browser-compatible HTTP/1 client is a whole another bag of problems that weren't even documented until recently. For example, Content-Length isn't just a single header with an integer, like the spec says. You need to support responses with multiple Content-Length headers and comma-separated lists of potentially contradictory lengths, and then perform garbage error-recovery the way Internet Explorer or Chrome did. Getting this wrong will make your client hang, consume garbage, or allow response stuffing. https://github.com/web-platform-tests/wpt/pull/10548/files https://github.com/web-platform-tests/wpt/pull/10548/files This problem does not exist in HTTP/2.

cookiengineer 5y ago
^ This. Multiple responses, especially with chunked encodings, are really really hard to get right. Even more so when you have to be able to resume downloads due to socket instability.

cookiengineer 5y ago

Building an HTTP library myself, I have to disagree. I drop two things here to counterargue that HTTP is easy to parse: 206 multiple ranges (requests will not always be responded to, and ranges from servers are almost always invalid when resumed) and Transfer Encodings (br inside gzip inside deflate inside chunked, anyone?) Both headers are implemented spec incompliant by every single web server I've seen, including nginx, apache and others. Source: building a peer to peer web browser that shares its bandwidth (and cache and downloads) with trusted peers. [1] [1] https://github.com/tholian-network/stealth https://github.com/tholian-network/stealth