Seibel Peter. Coders at Work
Подождите немного. Документ загружается.
Ken Thompson
465
Seibel: So you basically wrote an OS so you’d have a better environment
to test your file system.
Thompson: Yes. Halfway through there that I realized it was a real time-
sharing system. I was writing the shell to drive the file system. And then I
was writing a couple other programs that drove the file system. And right
about there I said, “All I need is an editor and I’ve got an operating system.”
Seibel: What’s the worst bug you’ve ever had to track down?
Thompson: Basically bugs where memory gets corrupted. It never happens
anymore. I don’t know why. But in the early days we were always working
with experimental hardware of various sorts, and there’d be some hardware
bug.
Seibel: So memory would get corrupted by the hardware screwing up, not
by a runaway pointer?
Thompson: It could be pointer. It could be hardware. Or a combination.
The one I’m actually thinking of, the worst example, was the on PDP-11. It
didn’t have multiply but you could buy a multiply unit and plug it in, but it
was an I/O peripheral. You would store a numerator and a denominator
and say go. You’d busy-loop and then pull out the answer, the quotient and
the remainder. And this thing was built for a non-memory-managed PDP-11
and we got the first experimental hardware for a memory-managed PDP-11
and this multiply unit didn’t fit with the memory management well.
So you’d store into this thing and then you’d busy-test. And during certain
aspects of the busy test it would send a physical address down instead of a
virtual address and some piece of memory would get clobbered with a
numerator of what you were trying to divide by. And it’d be ages before
you’d find it, and it’d be different places. That’s by far the hardest one I’d
ever had to find.
Seibel: How did you track it down?
Thompson: There was a program that I wrote that was going after a world
record for the number of digits of e. Previous world records were limited
not by computation—by cycles per second—but by I/O. I came up with a
Download at Boykma.Com
Ken Thompson
466
new algorithm where it was computation-bound and I/O became trivial. It
was monstrously heavy on multiply and divide. And we noticed that the
machine just crumbled whenever I put on my program. And therefore we
got the connection.
Seibel: So that gave you the clue that there was a problem with the
multiplier; did you ultimately track it down to some root cause?
Thompson: At some point we got it to where you store in the multiplier
in the multiply unit, and you pull it back and it wasn’t there. We reported
that to DEC and DEC couldn’t find it, and they didn’t want to deal with it.
Their normal people didn’t want to deal with this hybrid machine. In those
days you actually got the circuit diagrams of the machines, and we actually
found the bug in the circuit diagrams. Then we just called DEC and said,
“Connect that wire and that wire.”
Seibel: So, thankfully, hardware mostly doesn’t flake out on us that way
these days.
Thompson: Yeah. That’s why I think they’re rare. Plus things are isolated
from each other more—if you go bizarrely wild you’ll get a fault. Also you
did it in assembly language—it’s really easy to have the wrong thing in some
register through some subroutine call. When you have a high-level language
where the arguments all have to match up, these things become more and
more rare.
In the early days, in assembly language, you’d find them a lot. If it was
software, as opposed to a combination of software/hardware, usually it
would happen in one spot—the same spot would be corrupted. There’d be
some correlation of the bug with something. And you could sit there and
put a monitor in the operating system. And every so often, or very often,
you’d check and see if the error occurred, and stop as quick as you can, and
see what’s going on elsewhere, and chase them down that way. So you
could attack them.
This one you couldn’t attack. It wasn’t until I wrote this intensive
multiply/divide program that it saw the frequency of the error went way,
way up. Instead of crashing once every couple of days you’d crash once
Download at Boykma.Com
Ken Thompson
467
every couple of minutes. And then as soon as you got something that would
crash the machine you had a fighting chance to find it.
Seibel: So some folks today would say, “Well, certainly assembly has all
these opportunities to really corrupt memory through software bugs, but C
is also more prone to that than some other languages.” You can get
pointers off into la-la land and you can walk past the ends of arrays. You
don’t find that at all problematic?
Thompson: No, you get around that with idioms in the language. Some
people write fragile code and some people write very structurally sound
code, and this is a condition of people. I think in almost any language you
can write fragile code. My definition of fragile code is, suppose you want to
add a feature—good code, there’s one place where you add that feature
and it fits; fragile code, you’ve got to touch ten places.
Seibel: So when there’s a security breach that turns out to be due to a
buffer overflow, what do you say to the criticism that C and C++ are partly
responsible—that if people would use a language that checked array bounds
or had garbage collection, they’d avoid a lot of these kinds of problems?
Thompson: Bugs are bugs. You write code with bugs because you do. If
it’s a safe language in the sense of run-time-safe, the operating system
crashes instead of doing a buffer overflow in a way that’s exploitable. The
ping of death was the IP stack in the operating system. It seems to me that
there’d be more pings of death. There wouldn’t be pings of “take over the
machine becoming superuser.” There’d be pings of death.
Seibel: But there is a difference between a denial-of-service attack and an
exploit where you get root and can then do whatever you want with the
box.
Thompson: But there are two ways to get root—one is to overflow a
buffer and the other is to talk the program into doing something it shouldn’t
do. And most of them are the latter, not overflowing a buffer. You can
become root without overflowing any buffers. So your argument’s just not
on. All you’ve got to do is talk su into giving you a shell—the paths are all
there without any run-time errors.
Download at Boykma.Com
Ken Thompson
468
Seibel: OK. Leaving aside whether it results in a crash or an exploit or
whatever else—there is a class of bugs that happen in C, and C++ for the
same reason, that wouldn’t happen in, say, Java. So for certain kinds of
applications, is the advantage that you get from allowing that class of bugs
really worth the pain that it causes?
Thompson: I think that class is actually a minority of the problems.
Certainly every time I’ve written one of these non-compare subroutine
calls,
strcpy and stuff like that, I know that I’m writing a bug. And I
somehow take the economic decision of whether the bug is worth the extra
arguments. Usually now I routinely write it out. But there’s a semantic
problem that if you truncate a string and you use the truncated string are
you getting into another problem. The bug is still there—it just hasn’t
overflown the buffer.
Seibel: When you’re debugging, what tools do you use?
Thompson: Mostly I just print values. When I’m developing a program I do
a tremendous amount of printing. And by the time I take out, or comment
out, the prints it really is pretty solid. I rarely have to go back.
Seibel: And what kinds of things do you print out?
Thompson: Whatever I need; whatever is dragging along. Invariants. But
mostly I just print while I’m developing it. That’s how I debug it. I don’t
write programs from scratch. I take a program and modify it. Even a big
program, I’ll say “main, left, right, print, hello.” And well, “hello” isn’t what I
wanted out from this program. What’s the first thing I want out, and I’ll
write that and debug that part. I’ll run a program 20 times an hour that I’m
developing, building up to it.
Seibel: You print out invariants; do you also use asserts that check
invariants?
Thompson: Rarely. I convince myself it’s correct and then either comment
out the prints or throw them away.
Seibel: So why is it easier for you to print that an invariant is true rather
than just using
assert to check it automatically?
Download at Boykma.Com
Ken Thompson
469
Thompson: Because when you print you actually see what it is as opposed
to it being a particular value, and you print a bunch of stuff that aren’t
invariants. It’s just the way that I do it. I’m not proposing it as a paradigm.
It’s just what I’ve always done.
Seibel: When we talked about how you design software, you described a
bottom-up process. Do you build those bottom-up pieces in isolation?
Thompson: Sometimes I do.
Seibel: And do you write test scaffolds for testing your low-level functions?
Thompson: Yeah, very often I do that. It really depends on the program
I’m working on. If the program is a translator from A to B, I’ll have a whole
bunch of As lying around and the corresponding Bs. And I’ll regress it by
running in all the As and comparing it to all the Bs. A compiler or a
translator or a regular-expression search. Something like that. But there are
other kinds of programs that aren’t like that. I’ve never been into testing
much, and those kinds of programs I’m kind of at a loss. I’ll throw in some
checks, but very often they don’t last in the program or around the program
because they’re too hard to maintain with the program. Mostly just
regression tests.
Seibel: By things that are harder to test, you mean things like device
drivers or networking protocols?
Thompson: Well, they’re run all the time when you’re actually running an
operating system.
Seibel: So you figure you’ll shake the bugs out that way?
Thompson: Oh, absolutely. I mean, what’s better as a test of an operating
system than people beating on it?
Seibel: Another phase of programming is optimization. Some people
optimize things from the very beginning. Others like to write it one way and
then worry about optimizing it later. What’s your approach?
Thompson: I’ll do it as simply as possible the first time and very often that
suffices for all time. To build a very complex algorithm for something that’s
Download at Boykma.Com
Ken Thompson
470
never run is just stupid. It’s just a waste of time. It’s a bug generator. And it
makes it impossible to maintain because you’ve got to have 50 pages of
math to tell the next guy what you’re actually doing.
Ninety-nine percent of the time something simple and brute-force will work
fine. If you really are building a tool that is used a lot and it has some sort of
minor quadratic behavior sometimes you have to go in and beat on it. But
typically not. The simpler the better.
Seibel: Some people just like bumming code down to a jewel-like
perfection, for it’s own sake.
Thompson: Well, I do too, but part of that is sacrificing the algorithm for
the code. I mean, typically a complex algorithm requires complex code. And
I’d much rather have a simple algorithm and simple code than some big
horror. And if there’s one thing that characterizes my code, it’s that it’s
simple, choppy, and little. Nothing fancy. Anybody can read it.
Seibel: Are there still tasks which, for performance reasons, people still
have to get down to hand-tuned assembly code?
Thompson: It’s rare. It’s extremely rare unless you can really get an order
of magnitude and you can’t. If you can really work hard and get some little
piece of a big program to run twice as fast, then you could have gotten the
whole program to run twice as fast if you had just waited a year or two. If
you’re writing a compiler—certainly 99 percent of the code you produce is
going to be run once or twice. But some of it’s going to be in an operating
system that’s run 24 hours a day. And some of it’s going to be in the inner,
inner loop of that operating system. So maybe 0.1 percent of the
optimization you put into a compiler here is going to have any effect on
your users. But it can have profound effect, so there maybe you want to do
it.
Seibel: But that would be a result of generating better code in the compiler
rather than writing the compiler itself in assembly.
Thompson: Oh, yes, yes.
Download at Boykma.Com
Ken Thompson
471
Seibel: And presumably part of the reason writing programs directly in
assembly is less important these days is because compilers have gotten
better.
Thompson: No. I think it’s mostly because the machines have gotten a lot
better. Compilers stink. You look at the code coming out of GCC and it’s
awful. It’s really not good. And it’s slow; oh, man. I mean, the compiler itself
is over 20 passes. It’s just monstrously slow, but computers have gotten
1,000 times faster since GCC came out. So it may seem like it’s getting
faster because it’s not getting slower as much as computers are getting
faster underneath it.
Seibel: On a somewhat related note, what about garbage collection? With
Java, GC has finally made it into the mainstream. As Dennis Ritchie once
said, C is actively hostile to garbage collection. Is it good that folks are
moving toward garbage-collected languages—is it a technology that
deserves to finally be in mainstream use?
Thompson: I don’t know. I’m schizophrenic on the subject. If you’re
writing an operating system or a C compiler or something that’s used by
lots and lots of people, I think garbage collection is a mistake, almost. It’s a
cheat for you where you can do it by hand and do it better—much better.
What you’re doing is your sloughing your task, your job, making it slower
for your users. So I think it’s a mistake in an operating system. It almost just
doesn’t fit in an operating system. But if you are writing a hack program to
do a job, get an answer and then throw the program away, it’s beautiful. It
takes a layer of stuff you don’t want to think about, at a cost you can afford,
because computers are so fast, and it’s nothing but a win-win-win position.
So I’m really schizophrenic on this subject.
Part of the problem is there are different garbage-collection algorithms and
they have different properties—massively different properties. So you’re
writing some really general-purpose thing like an operating system—if
you’re going to write it in a language that garbage-collects underneath, you
don’t even have the choice of the algorithm for the operating systems.
Suppose that you just can’t stand big real-time gaps and you have a garbage
collector that runs up to some threshold and then does mark and sweep.
You’re screwed before you start.
Download at Boykma.Com
Ken Thompson
472
So if you’re doing some general-purpose task that you don’t know who your
real users are, you just can’t do that. Plus, garbage collection fights cache
coherency massively. And there’s no garbage-collection algorithm that is
right for all machines. There are machines where you can speed it up by a
factor of five or more by messing around with the cache. They should be
tied to the machine much more than they are. Usually they treat them as
separate algorithms that have nothing to do with machines, but the cache
coherency is very important for garbage-collection algorithms.
Seibel: Do you think of yourself as a scientist, an engineer, an artist, a
craftsman, or something else?
Thompson: I don’t know. I hate to use the word scientist because I think
it’s elitist. And implies a PhD. There’s no certificate that says “scientist” on
it when you complete the scientist course, so I don’t like the term or use it.
Engineer, I do have a degree that says “engineer” on it, so I can use the
word engineer. And when I fill out an occupation I either put engineer or
programmer because I can justify those. But mostly I just don’t worry about
it.
Seibel: Well, leaving aside what you call yourself, who do you feel the most
affinity with? Is it a physicist, a guy who builds bridges, a painter, or a
carpenter?
Thompson: Kind of the lower things. I believe a craftsman but with a
certain amount of artistry to keep it alive.
Seibel: How do you identify talented programmers?
Thompson: It’s just enthusiasm. You ask them what’s the most interesting
program they worked on. And then you get them to describe it and its
algorithms and what’s going on. If they can’t withstand my questioning on
their program, then they’re not good. If I can attack them or find problems
with their algorithms and their solutions and they can’t defend it, being
much more personally involved than I am, then no. At the same time you
can get a sense of enthusiasm. It’s not something you ask directly, but in the
conversation you’ll come with this enthusiasm-ometer, and that is
tremendously helpful for me. That’s how I interview. I’ve been told that it’s
devastating to be on the receiving side of that.
Download at Boykma.Com
Ken Thompson
473
Seibel: I would imagine. It’s sort of like an oral exam. Do you suppose
you’ve ever run into people who just didn’t have the personality that can
deal with that, independent of their programming ability?
Thompson: No, I don’t think it’s independent of programming. It would be
if I started asking them classical computer-science kind of questions, but
that’s not what I’m asking them. I’m asking them to describe something
they’ve done that they’ve spent blood on. I’ve never met anybody who
really did spend blood on something who wasn’t eager to describe what
they’ve done and how they did it and why. I let them pick the subject. I
don’t pick the subject, so I’m the amateur and they’re the professional in
this subject. If they can’t stand an amateur asking them questions about their
profession, then they don’t belong.
Seibel: What are you doing here at Google?
Thompson: Infrastructure. Operating-systems kind of stuff. Glue between
the pieces. I have a charter for anything I want. The challenge is to get a
bunch of unreliable machines to work like a reliable multiprocessor
machine. I guess that’s the closest thing.
Seibel: Isn’t the point of Google’s famous MapReduce machinery that it’s
shared-nothing message-passing rather than a shared memory?
Thompson: Well, it’s a process that has well-known semantics and no
feedback loops. If you have a reliable structure to do that, you can fit a lot
of problems into that structure.
Seibel: And are you working on things within that kind of framework?
Thompson: No, it’s just trying to keep the burden of reliability off the
individual programmers. It’s a real tough challenge. All the software here has
layers and layers and layers of what happens if this doesn’t work, what
happens if that doesn’t work. What happens if I don’t work—who kills me
and who starts up, who does what. I would guess way more than 50 percent
of the code is the what-if kind.
Seibel: So your goal is to have that half of the code go away?
Download at Boykma.Com
Ken Thompson
474
Thompson: Well, it would be hidden somewhere. It would apply in a
systematic way to the other code. Hopefully. It’s a hard job.
Seibel: Do you like working here at Google?
Thompson: Parts of it I like, very much. But parts of it are just ponderous
because there’s money involved in bugs and there’s money involved in lots
of the stuff. The size is unimaginable. Like day one you kind of get something
crippling along and day two you’ve got two million users. You just can’t
imagine such a thing.
Seibel: And you’re actually on the production side. As opposed to being in
Google Labs, which might be more akin to your past at Bell Labs.
Thompson: But I’m not actually production either. I’m in projects that will
become production. But I don’t babysit them after they’ve gone. Probably
my job description—whether I follow it or not, that’s a different question—
would be just to find something to make life better. Or have some new idea
of new stuff that replaces old stuff. Try to make it better. Whatever it is
that’s wrong, that takes time, that causes bugs. If there’s anything in the
structure of Google, anything that you can put your finger on that could be
done better, try to do it better.
Seibel: I know Google has a policy where every new employee has to get
checked out on languages before they’re allowed to check code in. Which
means you had to get checked out on C.
Thompson: Yeah, I haven’t been.
Seibel: You haven’t been! You’re not allowed to check in code?
Thompson: I’m not allowed to check in code, no.
Seibel: You just haven’t gotten around to it, or you have philosophical
objections to the Google coding standard?
Thompson: I just haven’t done it. I’ve so far found no need to.
Seibel: So you’re doing your stuff in your own sandbox? Do you mostly do
your stuff in C?