TCP in 30 instructions (1993)
pdl.cmu.edu
pdl.cmu.edu
https://news.ycombinator.com/item?id=6971935
I was looking for a good link, this is a bit nicer to read but in pdf:
http://people.cs.clemson.edu/~westall/853/notes/vanjtcp.pdf
Stumbled upon when reading the linux receive path:
https://github.com/torvalds/linux/blob/dd5cdb48edfd344017990...
"In the case of TCP, the upcalls almost always go two levels: IP finds the datagram is for this host & it upcalls a TCP demuxer which hashes the ports + SYN to find a PCB, lays the packet on the tail of the PCB's queue and wakes up any process sleeping on the PCB. The IP processing is about 25 instructions & the demuxer is about 10."
Further, note the "almost always"; it's true, but it's not "always".
Also, there's
"So, the first term of the 'if' checks four different things simultaneously: - that the window is what we expect - that there are no tcp options - that the packet has ACK set & doesn't have SYN, FIN, RST or URG set - that the connection is in the right state and the 2nd term of the if checks that the packet is in sequence..."
The result is that
"On the normal receive data path we execute 16 lines of C which turn into 33 instructions on a sparc (it would be 30 if I could trick gcc into generating double word loads for the header & my carefully aligned pcb fields)."
Note the phrase, "normal receive data path". Again, "almost always" is not necessarily "always". This heavily optimizes the common path while penalizing the uncommon path.
IBM's AIX also did something similar, back when I knew anything about it; it did almost all of TCP in the hardware interrupt handler, making the same assumptions of windows, options, flags, connections, and sequence numbers. It was ridiculously fast.
On the other hand, the non-fast-path cases have to be handled somewhere and are considerably more than 16 lines of C. Further, I'm not sure all of the assumptions are valid any longer. One assumption in AIX was that the incoming packet was the next segment of the same connection as the previous packet. That was true then, but may not be true now given that servers are handling more connections than back in 1993.
YMMV. Offer not valid in all 50 states. Don't shoot the messenger. Yes, we have no bananas.
http://www.moserware.com/2008/04/towards-moores-law-software...
which has a previous HN discussion: https://news.ycombinator.com/item?id=846028
I was interested to read this line:
> There is exactly one, contiguous, packet per 'pbuf' (none of that 'mbuf' chain stupidity)
because we recently switched to the same design in Snabb Switch: https://groups.google.com/d/msg/snabb-devel/8P7U3a55hVQ/_GAs...
Should probably add a few more for the called function, no?