A full TCP/IP stack in under 200 LoC (and the power of DSLs)

http://www.moserware.com/2008/04/towards-moores-law-software-part-3-of-3.html

by dschobel • 17 years ago

132 20 17 years ago

daeken3• 17 years ago

Downright impressive. I'm implementing the TCP/IP stack for my OS at the moment, and it's sitting at about 400 lines before TCP (ethernet, IP, DHCP, and ARP). Definitely going to see how I can improve it after this.

shailesh18feb81• 17 years ago

Hi Daeken,

That's impressive. Are you writing your OS for study purposes or you have something special in mind? I am interested in knowing as I am planning to do the same and might want to consult you.

daeken3• 17 years ago

There's a post about the background and motivation for the OS (Renraku) here: http://daeken.com/renraku-future-os

If you want to talk more about it or OS dev in general, feel free to ping me on IRC (Daeken on freenode) or on AIM (bloomfilter).

mahmud• 17 years ago

A friend of mine made millions selling his TCP/IP stacks since the mid 80s; he has written tens of them, all in various assembly languages.

Let me add that most of his work was for TCP/IP over serial ..

morphle• 17 years ago

At my startup I'm implementing these ideas from VPRI right now, we focus on implementing a parallel message-passing architecture in hardware and software. Founders wanted!

2bit• 17 years ago

The "meta-meta language-language" he mentions is OMeta. OMeta combines parsing and lexing and allows you to build your AST in your host language. It's really expressive and beats the pants off any other parsing framework I've used. The Viewpoints group is doing some of the most exciting work in CS right now, there's a lot of other interesting ideas they've been working on.

There are Python and Ruby implementations available. You can play with OMeta here: http://tinlizzie.org/ometa/

sb• 17 years ago

aside of alan kay, ian piumarta is working at vpri at cola (common object lambda abstration) and ometa right now. i recently posted a relevant video of alan kay's talk at intel's berkeley research lab on the topic of programming languages:

http://irbseminars.intel-research.net/ (since this link is very interesting in its own right, i am going to post it directly to HN as an article)

yters• 17 years ago

I think lisps, such as common lisp, do this too, since they also allow you to manipulate the repl lexer besides defining your own DSL.

tptacek2• 17 years ago

Yes, TCP/IP is damned simple if you model it as a trivial lock-step protocol. And this is a slick little piece of code. But it has nothing whatsoever to do with the 10,000+ lines of code that modern operating systems deploy to allow hundreds of competing TCPs to figure out how to share a link.

Interview question: what's the important thing TCP provides over UDP?

Fail answer: I don't know.

Push answer: Reliability.

Win answer: Congestion control.

dschobel• 17 years ago

Can you explain why there would be hundreds of competing TCPs?

I thought there were only a handful (Tahoe, Reno, Vegas, New Reno et al) of popular algorithms for the congestion control bit but it's all still TCP as specced in RFC 2581, no?

From where does all the complexity come?

wmf• 17 years ago

He probably means hundreds of competing TCP connections across a single link, which is common in the Internet (or in your LAN if you use BitTorrent).

tptacek2• 17 years ago

Two laptops attach to a wi-fi hub connected to a DSL line provided by a major telco. One starts a large download. Why doesn't it completely monopolize the skinny straw that connects the 10+mb/s network it actually sees to the gigabit network beyond the DSL? Why can the second laptop start another large download and both see reasonable download speeds? At a more basic level, how do these TCP's even know how fast to drive the transfer? All they see is a multimegabit wireless network. They're not psychic, and there's no configuration box or DHCP setting for "256 kb/s dsl uplink".

That's what TCP actually buys you.

You can make a reliable UDP protocol with a few tens of lines of code. It's called "TFTP", and it's god-awful slow.

scott_s• 17 years ago

This is an important distinction - the difference between production code that takes care of all of the edge cases that make things work in practice and the straight-forward implementation of the basic idea. But I think that's besides the point. The production implementations of TCP could probably be simpler and easier to understand if they were implemented in a similar manner as what's in this article.

andreyf• 17 years ago

I thought the language implementation was much more impressive: http://3.bp.blogspot.com/_Zfbv3mHcYrc/R_cAAN-Jc2I/AAAAAAAAAZ...

So close to BNF, and so clear in its deviations. Would be nice if I could use something like this to extend Python or JS and compile to them...

10ren• 17 years ago

It was a risk though, because I had to trust that I understood the problem domain well enough to invest a lot of time in the parser/interpreter. - First comment on blog http://www.moserware.com/2008/04/towards-moores-law-software...

Solving a problem is hard. Generalizing it to a class of problems is harder. Encapsulating it in a language with specialized syntax and semantics is harder still.

I think this is one reason that DSLs are not that popular, and is one reason why most new languages mimic existing languages like crazy (apart from for user-familiarity to ease adoption). The exceptions, like brainfuck and lolcats, use familiar semantics; and are only novel in syntax.

As for a Moore's Law for software, I'm going with Fred Brooks' Law of "No Silver Bullet". Complexity is hard, the best we can do is abstract away foundational concepts into components, as we understand them, and then SOTSOG.

The TCP/IP diagram syntax is really cool - but because it's clear, not because it's short; I think the parsing code in C would actually be shorter than the ASCII art.

toadpipe2• 17 years ago

Given that DSLs are hard, it does not follow that sticking "foundational concepts" into "components" is a better strategy than DSLs. If you write a DSL, you are standing on the shoulders of real giants. If you rely on components, you are going with the recently formed current conventional wisdom, and you are standing on the shoulders of relative peons.

Note that Fred Brooks argues for conceptual integrity, provided by a single human being, as the most important guarantee of product quality. If you use components, then you are accepting a system partitioning that has been decided many layers above you. If you design languages, then you cut out most of those layers. This gives you far more control over product quality.

Yeah, it's hard. Quality is hard. If your primary goal is anything other than quality, you will probably not produce a product with much of it. That's the real reason why there's no silver bullet.

jerf• 17 years ago

"If you write a DSL, you are standing on the shoulders of real giants."

In what sense do you mean that? Serious question, not sarcastic. It seems to me that if you build a DSL you're not standing on anybody's shoulders, which seems rather a disadvantage, but I say this to show you what I'm not understanding in your point, not as a criticism, as I believe you meant something else.

A full TCP/IP stack in under 200 LoC (and the power of DSLs)

Related Stories