The 25-Year-Old BSD Bug

sproketboy writes with news that a developer named Marc Balmer has recently fixed a bug in a bit of BSD code which is roughly 25 years old. In addition to the OSnews summary, you can read Balmer's comments and a technical description of the bug. "This code will not work as expected when seeking to the second entry of a block where the first has been deleted: seekdir() calls readdir() which happily skips the first entry (it has inode set to zero), and advance to the second entry. When the user now calls readdir() to read the directory entry to which he just seekdir()ed, he does not get the second entry but the third. Much to my surprise I not only found this problem in all other BSDs or BSD derived systems like Mac OS X, but also in very old BSD versions. I first checked 4.4BSD Lite 2, and Otto confirmed it is also in 4.2BSD. The bug has been around for roughly 25 years or more."

Re:Wait... Would you ever hit this?

[TheRaven64]

The first entry in a disk block, not the first entry in a directory. Each disk block is 512 bytes, so you can store around 30 files in there with shortish file names (each stores the name, the inode and a cumulative free space counter). For large directories you have around a one in 30 chance that the deleted file will be the first one in a block. Delete a dozen files from a large directory and there's a pretty large chance you'll hit this bug.

Re:Many eyes make bugs shallow...

[TheRaven64]

This bug has been around for a long time, but is only visible if you have large directories and delete files from them in between calls to readdir and seekdir. This is quite uncommon behaviour, and was incredibly uncommon 25 years ago when filesystems were much smaller and directories almost never contained enough files to require more than one or two disk blocks to store the directory.

When the Samba people found it, they decided to just code a work-around and not bother to report it to any of the BSD teams. If they had done, it would probably have been fixed in 22 years.

Now that it has been fixed in OpenBSD, the change can easily be taken and incorporated into FreeBSD, NetBSD, DragonFlyBSD and Darwin.

Re:Now it's time for a little housekeeping

[TheRaven64]

It doesn't let you hide an executable. Something like ls, which iterates over the directory entries, will see the executable. It's only things which maintain an internal cache of directory entries which will have the problem. The 'fix' for Samba was to turn off directory caching and this made all of the files visible again.

Re:Many eyes make bugs shallow...

[kithrup]

seekdir and readdir are unreliable when you're modifying the directory being read. The API requirement is that readdir return each directory entry that existed at the time the directory was opened exactly once. In the traditional UNIX implementation, the directory is simply a sequential stream of bytes; this is pretty easy -- you can simply lseek to the position that telldir returned. However, other systems don't use something that simple -- Mac OS X, for example, uses a B-Tree for the catalog file. Worse, they use a single catalog file for the entire filesystem's catalog, meaning that any modifications (adding, removing, or renaming files anywhere) causes the layout to change.

And telldir only returns a long, which -- in most implementations -- is smaller than off_t, so a simplistic implementation can have some problems. Of course, having a directory that's larger than 4GBytes could result in some other problems 8-).

Re:the developers probably knew about it

[Anonymous Coward]

Modded Offtopic?

Marc Balmer uncovered the bug.

Marc Balmer confirmed the bug was sitting in the code of all BSDs (including Mac OS X), including a lot of old releases.

Marc Balmer confirmed the bug was already in 4.2BSD, released in August of 1983.

Mildly amusing, so +1 Funny in my book.

Re:Old Code

[irc.goatse.cx troll]

Windows 2000 & NT4 source code leak [slashdot.org]
Only 4 years ago.

Re:Should it be fixed?

[irc.goatse.cx troll]

Most workarounds involve disabling caching. As a result they could re-enable caching for a performance increase, but leaving it off should have no iller effects with the patch than without.

Re:Many eyes make bugs shallow...

[VGPowerlord]

Samba could have reported it, but perhaps when they noticed in 2005, they also noticed that the July 2003 discussion [freebsd.org] on freebsd-hackers [freebsd.org] already acknowledged the existance of the bug [freebsd.org], but never actually fixed it.

Re:Many eyes make bugs shallow...

[Anonymous Coward]

Because the bug was found in the libdir code in 4.2BSD, which was never in SysV. Every non-BSD system that implemented the same API did it themselves, and won't have the (same) bug.

Re:Should it be fixed?

[Anonymous Coward]

I just read on the OpenBSD Journal discussion of the bug, a post from Otto that suggests this bug even made it into the POSIX standard:

The single Unix standard talks about that on some types of filesystems seekdir(3) cannot work:

"The original standard developers perceived that there were restrictions on the use of the seekdir() and telldir() functions related to implementation details, and for that reason these functions need not be supported on all POSIX-conforming systems. They are required on implementations supporting the XSI extension.

One of the perceived problems of implementation is that returning to a given point in a directory is quite difficult to describe formally, in spite of its intuitive appeal, when systems that use B-trees, hashing functions, or other similar mechanisms to order their directories are considered. The definition of seekdir() and telldir() does not specify whether, when using these interfaces, a given directory entry will be seen at all, or more than once."

So it seems like POSIX says, "this function is not guaranteed to work". Sounds like people were aware of the problem for a long time.

Re:Old Code

[EpsCylonB]

http://www.kuro5hin.org/story/2004/2/15/71552/7795 [kuro5hin.org]

analysis of th win2000 source code

Re:Many eyes make bugs shallow...

[Jeremy Allison - Sam]

No, we did report it. The answer at the time was "this is allowed by POSIX, deal with it", can be seen in the bug report here :

https://bugzilla.samba.org/show_bug.cgi?id=4715 [samba.org]

I did point out that no other POSIX system behaved like that, but that didn't seem to make much difference :-). Eventually I just added a parameter that allowed our open directory cache to be turned off on *BSD. Once it got into the hands of Marc Balmer he took us seriously and fixed the bug.

Jeremy.

Re:Many eyes make bugs shallow...

[Sparr0]

a) large "tooltips" (by which I assume you mean img title attributes) render "properly" instead of truncated in FF3b5

b) truncating title attributes is not a bug