Tuesday Jun 14, 2005

Now It Can Be Told

For thirty years, people have speculated on the identity of Deep Throat. Last week the mystery was finally revealed: the man called Deep Throat was not John Dean, not G Gordon Liddy, not Al Haig -- no, it was none other than Mark Felt. That's right, Mark Felt.

I'm sorry -- who? Who the f\*\*\* is Mark Felt? Felt, F-E-L-T? Let me think for a minute... Felt... Felt... nope, never heard of him. Ever. You've got to be kidding me. I've waited thirty years for this?

Well, if you think that revelation was a letdown, just keep scrolling: because while the chattering classes in Washington were playing the Deep Throat parlor game, an even less compelling question was nagging at far fewer people: where did the slab allocator get its name?

About 20 years ago Kellogg's ran a commercial for Special K cereal with the tag line, "Can you pinch an inch?" The implication was that you were overweight if you could pinch more than an inch of fat on your waist -- and that hoovering a bowl of corn flakes would help.

Back in high school I was watching TV with some friends, and this commercial came on. The voice intoned: "Can you pinch an inch?" Without missing a beat, Tommy, who weighed about 250 pounds, reached for his midsection and offered his response: "Hell, I can grab a slab!"

Fast forward 10 years. I was debugging a heap corruption bug in the Solaris 2.2 kernel. The kernel had actually crashed in the allocator itself, as often happens when something corrupts the heap. Trying to disentangle the state, I had the crash dump in one window and the source code for the Solaris 2.2 kernel memory allocator in another.

The code had all the hallmarks of what we in the industry call "swill": mysterious hard-coded constants, global locks, fixed-size arrays, unions, macros that implicitly reference global state, and variable names that are at once long and uninformative. A small taste:

mutex_enter(&kma_lock);
if ((listp->fl_slack >= 2) || (tmpsiz == max)) {
        listp->fl_slack -= 2;
        HEADFREE(listp, bufp);
        if (tmpsiz < max)
                bufp->fb_union.fb_state = DELAYED;
        else {
                LOOKUP(addr, bufp->fb_union.fb_poolp);
                if (--(bufp->fb_union.fb_poolp->bp_inuse) == 0 &&
                   bufp->fb_union.fb_poolp != Km_NewSmall &&
                   bufp->fb_union.fb_poolp != Km_NewBig) {
                        if (Km_IdleI < NIDLEP) {
                                if ((bufp->fb_union.fb_poolp->bp_status &
                                    BP_IDLE) == 0) {
                                        Km_Idlep[Km_IdleI++] = ...

and on and on it went.

All of this might have been tolerable if the allocator performed well, or was space-efficient, or had some other redeeming virtue. But no. It was big, fat, slow, and had to die. I went home that night determined to burn it to the ground. (The allocator, not my home.)

The basic idea for the new allocator was to grab a page of memory, carve it up into equal-size chunks, and use a reference count to keep track of how many chunks were allocated. When the reference count went to zero, the page could be freed.

That worked fine for small buffers (say 1/8 of a page or smaller), but wouldn't quite work for larger buffers: those would require more than one page. So I couldn't just grab a page; I'd have to grab a ... something. "Grab" must have been a mental trigger: all of a sudden I remembered Tommy, and how much I loved that line, and that sealed it: we would grab a slab, and this would be called the slab allocator.

Now you know. And Mark Felt is looking pretty dang interesting.


Technorati Tag:
Technorati Tag:
About

bonwick

Search

Categories
Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today