Hacker News Reader

Comment by MaxBarraclough | Hacker News Reader

Doing Boyer and Moore proud.

I think that if you want to support all verbs, you face at least 3 'ambiguities' whether you first check the first, second, or third character of the string. (It must be at most the third, as the shortest verbs are 3 characters long.)

First checking the first character is ambiguous between POST, PUT and PATCH. First checking the second character is ambiguous between HEAD, DELETE, and GET. First checking the third character is ambiguous between GET, PUT, OPTIONS, and PATCH. [0]

edit As danachow points out, the verbs are not all used with the same frequency. If real-world performance is the goal we'd presumably want to optimise for the GET case, which presumably means first checking the first character, as the 'G' is unique to GET.

[0] https://developer.mozilla.org/en-US/docs/Web/HTTP/Methods

View on HN

A bit of a micro-optimization, but couldn’t you interpret 4 bytes (including the trailing null on the three-letter verbs) as a 32-bit unsigned int and then do integer comparisons or a case statement?

You could add a computed goto to really spice things up.

call it "adventure plumbing"

This is close to what nginx does today, if your platform supports unaligned reads. The check for 'O' is a specific fast-path only for HEAD, most others are done via ordinary comparisons.

NGINX does exactly that (after finding the space character after the verb):

https://github.com/nginx/nginx/blob/7587778a33bea0ce6f203a8c...

There are several points to note: This trick only works if the architecture supports unaligned memory access. Macros are used instead of functions, so you don't have to rely on the compiler to do inlining. The shifts and ors should get optimized out by the compiler. I once tried something similar in C#, but sadly the JIT doesn't do that optimization.

Ah nice! I was interested in looking but don’t know the codebase.

That method does look better. My idea assumes that the method has already been checked to see if it is a valid method, which has its own cost. Otherwise, POSABC would be parsed as POST. Their method does that more or less on the fly.

> This trick only works if the architecture supports unaligned memory access

Presumably then it's relying on undefined behaviour.

pretty sure it's just implementation defined. In the sense that the implementation defines the allowed alignment, if nothing else (ie. on x86 the allowed alignment is 1 byte even if that's not optimal).

I don't think so. What I can find on this topic with a quick search points to it being outright UB.

https://stackoverflow.com/a/47622343/

https://stackoverflow.com/a/28895321/

https://blog.quarkslab.com/unaligned-accesses-in-cc-what-why...

Most requests in reality are GET. So if you first check for G,

  if (m[0] == 'G') {
    r->method = NGX_HTTP_GET;
      break;
  } else if (m[0] == 'P') {
    switch(m[1]) { ... }
  } else if ...

this should be fast enough.

How would this work if the method field was something like "Gibberish"? Would this have any security vulnerabilities?

If its "Gibberish" I'd suggest it's safer to assume it as a Get request regardless.

Something I don't see many people talk about, but I've setup web instances with both read and write clusters similar to db's, and have the nicety to getting more umph from the read cluster by making sure it only hits read db nodes and disabling any framework stuff for tracking changes on a model.

Did you experience any read after write inconsistencies that present as heisenbugs?

Would you expect that to be more of an issue under GP's method than with traditional sharding and replication? Presumably writes are then replicated to all instances, just not all instances accept them.

"Safer to assume" is making a lot of assumptions already. What if nginx itself or some other application behind it makes assumptions about the maximum length of a request method, and it causes a buffer overflow?

I expect anything that talks HTTP to reject requests with invalid HTTP methods. HTTP is a well-known standard and servers do not need to accomodate for sloppy, wrong, or malicious implementations.

Yep, you can generally get request splitting style vulnerabilities especially as a reverse proxy if you misparse reqs. (And sometimes even if you don't, one reason a rev proxy architecture is somewhat insecure).

Hopefully the actual code does a full parse after guessing what to try by the character test heuristic.

> this should be fast enough.

'Should' implies uncertainty; 'fast enough' implies there's no speed constraints / requirements. This particular bit of code - checking what request type is coming in - will be executed trillions of times across millions of servers across decades; it's the kind of thing you want to be as fast and secure as possible, so it's worth taking away these insecurities and guesses about performance.

Seems likely an optimal algorithm could probably get there just looking sequentially at the first three letters in order. Would be an interesting code-golf.

Reply on news.ycombinator.com