Blogs

My day at work alternated between trying to put out a new release of my kernel patches (complicated by a failing machine at citi making some of our services unreliable), working on various ACL-related stuff (mainly talking over things with Andreas and then trying to read through some of his code), and helping Fred with some debugging (a little; Fred was the one that actually figured it out).

Some days a problem really grabs me and I just can't stop thinking about it; this wasn't such a day.

After work I met Trond, Laura, Sara, and (eventually) Paul at Dominicks. Trond suggested the nfsd readahead problem as the sort of thing that should keep a person up at night.

In particular, the problem is this: every time an application asks for data from a file, you have to go read the data from disk. But that's terribly inefficient. It takes eons (ok, milliseconds--but that's eons on today's hardware, where a processor executes an instruction every nanosecond) to move the disk head to the right place, wait for the disk to spin around to the right spot, and read the data. So, ideally, you'd like the data to already have been read. How is that possible? Well, it's not always possible for the operating system to predict what's going to be asked for next. But often it is, because often applications just read through whole files sequentially from beginning to end.

So any modern operating system recognizes when an application is reading straight through a file from beginning to end, and starts anticipating by performing "readahead"--reading the next few chunks of the file before they're requested, assuming that they'll be needed soon.

The problem comes when you throw NFS into the mix--now the application is split from the disk by a network, and the read requests may sometimes be switched around and arrive in a different order. So even though the application is reading through the file in order, it looks to the NFS server like they're going back and forth a little, and the standard readahead algorithm fails because it doesn't recognize that this is basically not that different from sequential reads.

I actually read a paper recently where they dealt with this problem, but can't for the life of me remember where it was....

When I got home I tried reading through Pike and Weinberger's "the Hideous Name", but found it kind of a pointless paper.

McKusick and Kowalski's "Fsck -- The UNIX File System Check Program" (1985) rehashes some details from the FFS paper before talking about corruption.

Note that all writes required to deallocate a block from an inode are done synchronously, and all directory operations are done synchronously, to prevent, for example, a block ever being referenced from two different inodes (no longer an automatically recoverable situation since you can't decide which it should belong to).

The rest of the paper is a list of the various sanity checks performed by fsck; mostly fairly obvious. There's no discussion of performance, which must be terrible--multiple passes through the whole filesystem seem to be required, and memory requirements for some of the calculations are probably unbounded.

I ran across Filesystems Reading List recently and thought I should skim through some of the references.

McKusick, Joy, Leffler, and Fabry, "A Fast File System for UNIX" describes improvements to "the" UNIX file system, including:

• increasing the minimum block size to 4096, to make it possible to address larger files without adding more indirection, and to reduce seeks (and overhead of data transfers?),
• adding redundant copies of the superblock (which never changes) to aid recovery
• representing free/allocated blocks using bitmaps (one for each "cyclinder group") instead of just a single list of free blocks, to allow smarter allocations that manage fragmentation,
• adding the rule reserving the last few percent of free space to the system administrator, mainly to prevent fragmentation,
• adding more complex allocation policies designed to group inodes from the same directory together, and file data for the same inode together, to reduce seeks.

To prevent wasting space on (typical) filesystems with lots of small files, they actually allocate space in units of fragments, with size set to some fixed fraction of the block size. To keep down fragmentation (I guess) they'll allocate a new block and copy a bunch of fragments to it if a new write would create enough fragments to fill a block. But this being inefficient, they discourage it by introducing what I guess must be the st_blksize state field.

The basic motivation for all of this was to increase reliability and performance (the old filesystem was using only a few percent of the theoretically available bandwidth to storage).

They were limited by disk drivers that would only transfer one block at a time; so reading two contiguous blocks ends up not being as fast as expected, since by the time you're ready to read the second you've already spun past it. So they have some bizarre allocation policies that try to locate blocks that are spaced at the right intervals around the platter so that you don't overshoot them when you do a big sequential read.

They also introduce long file names (and discuss the directory layout), symlinks, "flock" locks, and quotas.

They also add the rename operation, motivating by desire to atomically replace a file by a new version of the file. If that has to be done by removing the old file, linking in the new file at the old file's location, then unlinking the new file's temporary location, then there are times when the neither the old nor new version is visible at the target location, etc. So "rename" is added to do all of this atomically.

The paper is from 1984, so I would have been in seventh grade.

Somebody signing themselves "a busker" posted a comment to arborupdate today including the following:

"buskers are not panhandlers or beggers. they are intellectuals. if you can’t tell the difference between a busker and a begger u may be a moron. morons are incapable of perceiving intellectual concepts."

I've been more motivated than usual by work; I worked a bit Sunday, and then was up late Monday and Tuesday nights trying to finish off a couple things that were really obsessing me, including the long-delayed project to emulate the full nfsv4 acl model using linux native posix draft acls. Staying up late also means I don't get to work till almost noon.

Today, though, was donuts, so I actually got in a little before 10.

This morning my sister sent me a picture of people I hadn't seen in fifteen years or so--the parents of the friend Shawn who lived across the street when I was in junior high and elementary school in Hampton Virginia. Apparently they'd called up my parents a few days ago to say they were in town, visiting Shawn and his family, who now live in Maryland. (The parents now live in Norfolk; we'd lost touch with them since they'd moved there from Hampton). So my parents had them over to dinner, and Shawn wasn't able to come, but his parents, wife, and kids were.

Shawn and I and the other neighborhood rode our bikes around a lot, played games, played with lego, and played D&D. We moved to Maryland when I started high school, and that's probably the last time when I've really known the people who were my neighbors.

Andreas G., who wrote the linux's draft posix acl implementation, has been doing a bunch of work figuring out how to implement NFSv4 ACL's on linux without losing posix compliance. That means figuring the rather tricky interactions between mode bits and NFSv4 ACLs. So he proposed that the four of us working on this have a meeting to figure out some of this stuff. The two Sun people couldn't travel, so we decided to meet at their offices in Broomfield, Colorado.

It also happened that my parents were renting a cabin in Estes Park for two weeks during the same time. And Sara got talked into this too. So last Friday Sara and I found ourselves in the Denver Airport. My parents met us there and whisked us off to Boulder for a tasty dinner at the Boulder Dushanbe Teahouse before making the rest of the drive to Estes.

Saturday we went to the Rocky Mountain Nature Association's picnic, and at night had dinner at the Twin Owls Steakhouse, where Sara and I had our wedding reception four hears ago.

I think it must have been Sunday that my dad took Sara and I up to Dream Lake, but I know it was Sunday that my cousin Wallace and his wife Rebecca met us for hiking and a dinner at the Baldpate Inn. And I'm having trouble figuring how we did both in the same day. So maybe Dream Lake was actually Saturday? Oh well.

Monday we walked most of the way up to Mount Chapin. The walk starts in the forest, then as it goes up (very steeply at times), the trees get shorter and shorter until they're just little clumps of scrappy "Krumholtz", the sort of naturally-occuring bonsai that's formed by the wind at high altitudes. There are also lots of tiny wildflowers, succulents, and the occasional odd mushroom, all clinging as close to the ground as they can.

Sara and my mom stopped off at some point along the trail, and then my dad and I walked another half hour or so, to the point where they trail disappears and you're mainly clambering over fields or rocks, which is tiring and hard on the ankles, but fun. Due to a slight error in aim, we ended at a local maximum in the ridge that lead to the peak of Chapin, but not quite at the actual peak. But I was content just to be on top of something, and ready to have a sandwich and walk back down. So we met the others on the way back down, then continued up the Fall River Road to the visitor center, and went back down Trail Ridge road.

Having had enough big meals out, we ate at home Monday night.

Tuesday morning my parents took me back to Broomfield and dropped me off at the Sun campus around 9ish; we said our goodbyes and they took Sara off to catch a noon flight back to Detroit.

With just four of us (and Mario calling in from Boston occasionally), the meetings were intense and productive, and we figured out some important things. Sam and Lisa also took us to some excellent restaurants in the area of Broomfield and Boulder; in order:

• A local sandwich place with character, whose name I've forgotten; but the sandwiches were good.
• A Mexican place ("Three Margaritas") with a much more interesting menu than what you'd usually get around Ann Arbor.
• A great Pho place in a little strip mall whose name I've again forgotten.
• Shushi Zanmai, in Boulder: Yummy!
• A restaurant at the local airport (not the main Denver Airport), where you could watch the planes and the mountains. The food (sandwiches and such) might not have been quite as exciting, but it was fine, and the view was fun.

Thursday night Andreas dropped me off at the airport. The security lines were long, but not horribly so (with a 25 minute wait), despite the morning's bomb scare in London. While getting some quick dinner, I ran into Mike, an old friend of graduate school I hadn't seen in years, and we chatted for just a minute or two before I had to run.

The flight home was uneventful, but I was tired and bored, and sandwiched between two largish people with elbows.

Andreas figured he may as well make a side trip to Ann Arbor as long as he was in the states, so I met him at citi the next day, and he, Trond, Andy, Jim, and I went out for lunch at the Arbor Brewing Company. Andreas and I worked together the rest of the afternoon, then met Sara and Chuck at Madras Masala for dinner, and (after parting with Chuck) met Dave and Paul at the CJS film series' showing of "Crazed Fruit". I thought Crazed Fruit was fun, though the others found it slow in parts.

My sister had also flown into town Thursday, the same night as Andreas and I, and stayed with us overnight--her plan was to meet her college friend Jill and her new baby, but thought she should avoid the baby a little while due to a cold. So she'd been mostly staying home sniffling Friday, but Friday night she'd stayed with Jill, and Saturday she met Sara and I at juggling, after I'd met with Andreas a little more at citi in the morning before he left for Germany.

We spent the rest of the afternoon with the jugglers, browsing bookstores and then seeing a couple Buster Keaton movies at Paul's place.

So, Top of the Park ended with an old silent version of "The Hunchback of Notre Dame" accompanied by the Carillon. We went to the Townie Party that's preceded art fair for the last two years (last year we skipped it). It was very hot out, and not that exciting an event.

Last week was OLS. I know a few more people each year, which makes it a little better each year.

I carried around a notebook with me through the weekend and made some notes during Top of the Park and elsewhere, and thought I'd figured out a reasonably elegant way to solve a problem with blocking locks that we spent some time beating our heads against last year and gave up on. So I was reasonably happy about that.

I talked about it with Trond a bit over lunch on Monday and he seemed to think it sounded like a reasonable approach.

Monday night both bands were Andy's (Sandbox, his fusion band, and Fubar, which plays more covers), so besides Sara and me, a bunch of Andy's relatives were there, along with Trond and Laura.

Sara stayed for the movie, "Wallace and Gromit and the Curse of the Were-Rabbit", and I went off with Trond and Laura to Andy's place, where Leslie served us some yummy pie, Stuart set off some fireworks, and we listened to a recording of the evening's show. All very pleasant but I was feeling tired and not terrifically social at that point, so I was happy when Trond dropped me off at home around midnight.

It turned out that not only had Sara stayed for the whole movie (and enjoyed it, despite it being rained on), but she'd also gone out with Dave and some friends and had coffee and then competed in some trivia competition at Buffalo Wild Wings. So she got home much later than me.

Despite all this, I woke up fairly early the next morning and decided I could make it to the Ann Arbor 4th of July parade. I walked downtown as fast as I could (there wasn't any bus service), but made it with plenty of time to spare, and carried a sign (who knew the stupid mp3-player port on top of my backpack would be useful for something some day) and juggled a bit in the WBWC group.

Afterwards I walked backwards around the parade (the WBWC was one of the first groups), then had a sandwich at Subway (my usual haunts were closed for the holiday), and went to citi and worked on my new locking patches.

We saw the civic band and then the Forbes Brothers (who were great fun), then went home. I kept working throughout and had finished most of the new locking code by the end of the day. Whee. We'll give it a few more days and see if it still looks good, or if I realize the whole approach is doomed from the start and I need to start over again....

The one unqualified piece of progress is that I now feel like I really understand the locking code. If nothing else I should do some documentation and cleanup work before I forget how it all works.

Friday night was the Sun Messengers. Alas, they didn't play "Celebration", but it was fine anyway. Sara even made me get up and dance. Um, well, sort of. She danced a little and I sort of bounced up and down slightly at the edge of the crowd.

Saturday we did some shopping for produce at Kerrytown and then mostly hung out with the jugglers for the afternoon. I stole away for an hour to do a little bit of work. Somehow I found myself more antisocial lately--I'm happier if I can do stuff on my own a few hours a day. The band that night was a reggae band ("Roots Rock Society") that I found boring, so we didn't stay to the end.

Sunday we heard the Carillon concert again, stsayed for Repercussions (which I find sort of inoffensive but for some reason unengaging), then saw Harry Potter and the Goblet of Fire. Which was frantic--the ball was well done, partly because it was one of the few things that was actually prepared for and dealt with over a period of time--but the rest of it seemed like a mad rush from one event to the next.

Also, most of the scenes in the movie are quite dark, and one of the problems with Top of the Park is that they can't really remove all the ambient lighting, with the result that in some scenes you could see the shadow of the trees from street lamps easier than the scene itself.

Sara and I have been continuing to meet at Top of the Park most nights.

Last night was their bohemian-themed night. I don't know what precisely the claimed connection is between bohemians and jugglers, but someone thought it would be cute to have jugglers there, and for me (and the other jugglers who signed up) it just meant an hour to two doing our usual thing--hanging out juggling--and maybe being a little more extroverted than usual. In return for that we got comp tickets to the night's show indoors, Les Yeux Noirs.

And Les Yeux Noirs were indeed great fun--interesting music, lots of music, crowd-pleasing showmanship.