TCP in 30 instructions (1993)

http://www.pdl.cmu.edu/mailinglists/ips/mail/msg00133.html

by adamnemecek • 13 years ago

132 38 13 years ago

pdl.cmu.edu

tptacek4• 13 years ago

This is a very famous post, and Van Jacobsen is the archetypical networking systems programming bad-ass. Important context here though: this is just the per-segment receive processing piece of TCP; it's describing a very simple fast path that segments can take, but not all the TCP logic!

FuckFrankie3• 13 years ago

Wouldn't "all the TCP logic" be the entire internet?

tptacek4• 13 years ago

No, it would not be anything close.

lussier• 13 years ago

randyrand• 13 years ago

The internet is a very large and general term. It comprises millions of servers, routers, generally includes things like web browsers, http, etc.

TCP is just one protocol of the thousands of protocols used for the internet, typically to carry other protocols. UDP is also used on the internet.

"not all the logic" means that this implementation is not a full implementation of the TCP protocol.

Check out: http://en.wikipedia.org/wiki/Internet_protocol_suite http://en.wikipedia.org/wiki/OSI_model

stonemetal• 13 years ago

It shows receiving data, it doesn't show anything about sending data including congestion control. It doesn't even show the full TCP receive a packet process since acking a packet is ... in the code. I also don't see anything about the state machine that occurs during connection creation or tear down. etc. Calling what is in the link TCP is about like claiming to describe the entire postal system in three steps(pick up envelope that has been delivered to your mailbox, open envelope, read letter).

stplsd• 13 years ago

Van Jacobsen

Van Jacobson

He is probably most famous for his work on early congestion control algorithms in 1988 (http://ee.lbl.gov/papers/congavoid.pdf)

caf• 13 years ago

Right - the famous 30 instructions are in the hardware interrupt path, and responsible for putting the packet on the correct process's queue and waking that process up. As the original post says:

  The TCP protocol processing is done as we remove packets
  from the queue & copy their data to user space (and since
  we're in process context, it's possible to do a 
  checksum-and-copy).

The TCP protocol processing mentioned here done in process context is certainly not covered by the 30 instructions.

wslh• 13 years ago

If you liked this post you might like the "Appendix E: Extended Example: A Tiny TCP/IP Done as a Parser" by Ian Piumarta. The paper is available at: http://www.vpri.org/pdf/tr2007008_steps.pdf

grannyg00se• 13 years ago

I love the opinionated writing style. I wish I knew more about this so I could relate to the comments about the "compiler braindamage", "mbuf chain stupidity", and "netipl software interrupt bs".

delinka• 13 years ago

I read those things as sarcasm (e.g. "none of that buffer-overrun-checking garbage") but perhaps there's more to it.

minimax• 13 years ago

The "compiler braindamage" is that it is generating instructions to load individual registers 4 bytes at a time where it could instead generate instructions that load eight (properly aligned) bytes at a time into two four-byte registers at once. The bytes in question are some fields in the tcp header and some fields in the pcb (which is like all the state related to the TCP connection).

These instructions here are loading the header into registers:

        ld [%i0+4],%l3     ! load packet tcp header fields
        ld [%i0+8],%l4
        ld [%i0+12],%l2
        ld [%i0+16],%l0

That's the assembler for this:

        u_long seq = ((u_long*)ti)[1];
        u_long ack = ((u_long*)ti)[2];
        u_long flg = ((u_long*)ti)[3];
        u_long sum = ((u_long*)ti)[4];

ld loads 4 bytes at a time into a register but there is a sparc instruction ldd that will load 8 bytes into two registers at a time. If the compiler used ldd these four instructions turn into two. That gets us from 33 to 31. I'm not 100% clear which two fields from the pcb can be loaded simultaneously but there is this line

        ld [%i1+72],%o0                 ! compute header checksum

and then further down

       ld [%i1+68],%o0

which I think are:

       u_long cksum = tp->ph_sum;

and

        if ((flg & FMASK) == tp->pred_flags && seq == tp->rcv_nxt) {

Obviously that line is multiple instructions but what I meant is the part where tp->rcv_nxt is loaded into a register.

So probably tp->ph_sum and tp->rcv_nxt are adjacent in his version of struct tcpcb and he thinks the compiler should do use the same parallel load instruction (loading two registers from 8 bytes at once) for those fields.

darbelo• 13 years ago

The "mbuf chain stupidity" refers to the way memory buffers are handled in the kernel. His implementation uses 'pbufs' to store a single packet contiguously in kernel memory. This is in contrast to BSD[1], where a packet could span multiple 'mbufs' which were 'chained' into a linked list.

You can "man 9 mbuf" on your nearest BSD derivative to glean a bit more information about what he is opposing. Today's mbufs are not quite the same as they were back then, but the parts that he hated are still there :)

[1] "my kernel looks nothing at all like any version of BSD"

laichzeit0• 13 years ago

For a walk through of the BSD TCP/IP source code there's also Steven's TCP/IP illustrated volume 2. The first few chapters painstakingly go through mbufs and exactly how the data structure is implemented and used. Much of this won't apply to current kernels but it's probably close enough for what Van Jacobson is talking about.

http://www.amazon.com/TCP-IP-Illustrated-Implementation-Vol/...

chetanahuja• 13 years ago

mbuf chains [1] (or something like them) are the canonical way of receiving data from the network. You basically "tag" every incoming chunk of data as an mbuf, and keep the data as linked lists of said mbufs (hence the mubf "chain"). Some key properties of incoming network data are that it's:

1) Arriving asynchronously, at arbitrary time points (actually the OS code gets to handle the incoming data in interrupt processing routines)

2) Arriving in arbitrary quantities in each new chunk(as opposed to, say, reading nice, aligned, blocks from the disk)

3) Possibly arriving out of order.

Now if you consider the requirements that you have this uncertain sized chunks of data that you (the network stack code) need to parse into (and possibly reorder into) one of many possible protocols then deliver it in a nicely packaged form to a user process (which may or may not be ready to receive this data at this moment) --- and, additionally, there's a lot of pressure to avoid unnecessary memory copies -- you'll be inevitably led towards an architecture that looks somewhat like mbuf chains.

The cited writeup and accompanying code has some crucial details hiding in the following snippet

"the Packets go in 'pbufs' which are, in general, the property of a particular device."

The point I think is that it's special purpose code written for a narrow use/demo case. Not meant to be taken seriously for an actual, general purpose OS.

tl;dr mbuf chains are inevitable for general purpose networking. Resistance is futile.

[1] https://developer.apple.com/library/mac/documentation/darwin...

anonu• 13 years ago

I am curious to know if today's modern TCP stacks (windows, popular linux distros,etc..) are coded with the same approach. Does anyone know?

bodyfour2• 13 years ago

More or less, yes.

In the original TCP implementations from the early 80s, performance was (understandably) not the main priority.. they just wanted to get it working first. Also, nobody was sure what networking protocols would become popular (IP? OSI? XNS?) so a lot of work went into making everything as flexible as possible. This reached an apogee with AT&T's "STREAMS" subsystem (a competitor to the sockets API for writing networking code on UNIX) which was very flexible but also extremely complicated.

What Van Jacobson's work was saying is "look guys: by paying close attention to the fastpath you can saturate your 10Mbps network with TCP traffic" I'm sure everybody who has written a TCP stack has seen this email and has taken the tricks to heart.

These days not all of the tweaks might be still relevant. For instance, the hardware is probably doing the hardware checksum for you. However, the spirit of "do as little as possible in the fastpath" is certainly still followed in modern stacks.

oofabz• 13 years ago

Just as a historical note, classic Mac OS (versions 7-9) used STREAMS for TCP, in the Open Transport networking API. Sockets were provided as a wrapper around STREAMS, which worked about as well as you might expect. It had its fans but most of us were pleased to get real sockets in Mac OS X.

nashashmi• 13 years ago

Might be off topic, but I have always wondered where do these public domain university emails come from? Was E-mail a public forum back then?

michaelhoffman• 13 years ago

I'm not sure what you mean by "these public domain university emails." This is an email that has been saved and re-forwarded many times, including to mailing lists such as the one archived in the main link. Originally it would have been forwarded by either the sender or one of the recipients.

Buge• 13 years ago

In the header at the top it says Cc: ips@ece.cmu.edu, so it was carbon copied to the mailing list.

radikalus• 13 years ago

TCP in 30 instructions (1993)

Related Stories