Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

TCP in 30 instructions (1993)

pdl.cmu.edu

Post reply on HN
Print view View original

31–40 of 41 posts

Re: TCP in 30 instructions (1993)

#31

Post by darbelo »

grannyg00se wrote: post #12

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".

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"

Re: TCP in 30 instructions (1993)

#32

Post by bodyfour »

oofabz wrote: post #27
bodyfour wrote: post #26

Earlier quoted context omitted.

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…

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.

I wasn't aware classic MacOS worked that way. The "sockets-emulated-over-STREAMS" was the standard way of doing things in SVR4-based UNIXes. In the early-to-mid 90s this gave them a poor reputation among early web admins since they just didn't handle high rates of connections as well as BSD or even the early linux stacks.

In the case of Solaris, this was largely fixed in the 2.6 release where they went back to a sockets-based stack and ran the STREAMS stack in parallel. (Actually this was originally supplied as a semi-supported patch to 2.5.1 since the scalability of the network stack was becoming a critical issue at large customers) Many of the OS-supplied services (like rpcbind I think) still used the STREAMS API but the 99.9% of external software that used the sockets API now had a fast native path to the network.

As far as I'm aware this is still the state there today, with STREAMS probably still existing for compatibility but basically ignored by everyone.

There were some interesting things Solaris did with STREAMS.. for instance telnetd and rlogind would just push a kernel-land module that would copy data between the pty and socket. This way you didn't have to make the kernel->user->kernel->user transition on every keystroke. In the heyday of shell accounts this was terrific. Of course these days CPUs are so much faster and everyone uses ssh anyway so it wouldn't be a useful optimization.

STREAMS was an interesting experiment, but I don't mourn its passing at all.

Re: TCP in 30 instructions (1993)

#33

Post by tptacek »

userbinator wrote: post #30
eloff wrote: post #28

Earlier quoted context omitted.

TCP is actually extremely complex, see http://en.m.wikipedia.org/wiki/Transmission_Control_Protocol I don't think I could implement it in under 4000 sloc, and I'd guess it'd be over two months worth of work for just a minimal TCP stack that could interoperate with the internet at large.

TCP is only complex because of all the optional bits for performance tuning, but if you are only interested in size, look on the embedded side. The actual core functionality is much smaller, and I would even go as far as to say that a lot of the widely used open-source TCP/IP stacks obfuscate this with their added complexities. E.g. http://en.wikipedia.org/wiki/UIP_(micro_IP)

Uh. No. TCP is complex because it works in the scenario where you, me, and 20 coworkers share a fast LAN hooked up to a slow pipe to the Internet and we all have to share that pipe constantly but nobody actually knows exactly who's trying to do what with it. TCP congestion control is a minor miracle even before you realize that this plays out writ large across the whole Internet, large-pipe-huge-pipe-small-pipe-big-pipe, without the Internet collapsing, which is what it used to do. One of the big challenges in designing fast scalable transports that gain speed by allowing drops or out of order delivery is in making them compatible with the congestion control regime that TCP implements.

TCP is complex because it solves a mindbogglingly complex problem. That it is as small as it actually is makes it one of the more elegant things ever to come out of computer networking.

Re: TCP in 30 instructions (1993)

#34

Post by derefr »

tptacek wrote: post #33
userbinator wrote: post #30

Earlier quoted context omitted.

TCP is only complex because of all the optional bits for performance tuning, but if you are only interested in size, look on the embedded side. The actual core functionality is much smaller, and I would even go as far as to say that a lot of the widely used open-source TCP/IP stacks obfuscate this with their added complexities. E.g. http://en.wikipedia.org/wiki/UIP_(micro_IP)

Uh. No. TCP is complex because it works in the scenario where you, me, and 20 coworkers share a fast LAN hooked up to a slow pipe to the Internet and we all have to share that pipe constantly but nobody actually knows exactly who's trying to do what with it. TCP congestion control is a minor miracle even before you realize that this plays out writ large across the whole Internet, large-pipe-huge-pipe-small-pipe-big-p…

> One of the big challenges in designing fast scalable transports that gain speed by allowing drops or out of order delivery is in making them compatible with the congestion control regime that TCP implements.

I would argue that this very thing makes TCP inelegant; congestion-control should really have been its own layer between IP and TCP, instead of being something that every protocol that's not UDP has to carefully reimplement.

Re: TCP in 30 instructions (1993)

#35

Post by tptacek »

derefr wrote: post #34
tptacek wrote: post #33

Earlier quoted context omitted.

Uh. No. TCP is complex because it works in the scenario where you, me, and 20 coworkers share a fast LAN hooked up to a slow pipe to the Internet and we all have to share that pipe constantly but nobody actually knows exactly who's trying to do what with it. TCP congestion control is a minor miracle even before you realize that this plays out writ large across the whole Internet, large-pipe-huge-pipe-small-pipe-big-p…

> One of the big challenges in designing fast scalable transports that gain speed by allowing drops or out of order delivery is in making them compatible with the congestion control regime that TCP implements. I would argue that this very thing makes TCP inelegant ; congestion-control should really have been its own layer between IP and TCP, instead of being something that every protocol that's not UDP has to careful…

I said TCP was elegant, not that it was perfect. It also has the "urgent data pointer". :)

Re: TCP in 30 instructions (1993)

#36

Post by laichzeit0 »

darbelo wrote: post #31
grannyg00se wrote: post #12

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".

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 n…

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/...

Re: TCP in 30 instructions (1993)

#37

Post by chetanahuja »

grannyg00se wrote: post #12

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".

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...

Re: TCP in 30 instructions (1993)

#38

Post by caf »

tptacek wrote: post #2

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!

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.

Re: TCP in 30 instructions (1993)

#39

Post by dlitz »

userbinator wrote: post #30
eloff wrote: post #28

Earlier quoted context omitted.

TCP is actually extremely complex, see http://en.m.wikipedia.org/wiki/Transmission_Control_Protocol I don't think I could implement it in under 4000 sloc, and I'd guess it'd be over two months worth of work for just a minimal TCP stack that could interoperate with the internet at large.

TCP is only complex because of all the optional bits for performance tuning, but if you are only interested in size, look on the embedded side. The actual core functionality is much smaller, and I would even go as far as to say that a lot of the widely used open-source TCP/IP stacks obfuscate this with their added complexities. E.g. http://en.wikipedia.org/wiki/UIP_(micro_IP)

You're not necessarily wrong, but uIP may not be the best example of a good minimal TCP implementation. I've seen it routinely put the wrong value into the TCP window-size field. This creates an illusion of packet loss, causing senders to retransmit and performance to drop exponentially to zero.

As a workaround, I wrote a custom tool that avoids sending more than one TCP segment at a time:

https://github.com/dlitz/dlink-firmware-uploader/blob/581b64...

Post reply on HN