seekdir

[fivetonsflax]

Marc Balmer found a 25-year-old bug in the BSD *dir libraries.

Marc says that if you write a directory that spans two blocks, delete the first directory entry in the second block, then seekdir to the second entry in the second block (using a saved value from telldir), you'll be placed at the third entry instead. And he generously provides you

Comments

[xlerb]

ls -f is giving you unsorted output, straight from the filesystem. HFS uses a kind of B-tree to store directory information; the key is, IIRC, the ordered pair of directory id and file name. Thus, your directory is not a separate file like in UFS, but a contiguous extent of the directory tree leaf records, and those are stored sorted by filename.

Note that case-insensitive HFS sorts case-insensitively, while case-sensitive HFS should sort case-sensitively.

That said: I don't think it's kosher to do arithmetic on the values returned by telldir, the way you are.

telldir arithmetic

[fivetonsflax]

It was the only way I could find to get the desired result out of seekdir/readdir. I wasn't sure it was right either. How would you work this problem without it?

Re: telldir arithmetic

[fivetonsflax]

OK, I see how you did it. That is better, yeah.

Re: telldir arithmetic

[xlerb]

As in my altered version: telldir, then readdir, then check for end-of-directory, so that the handle is from before the entry that gets readdirred. (Oh, ha. LJ doesn't mail me responses to responses. Never mind that, then.)

I notice that, on Linux tmpfs, the position for the file named “26” is 4. Make of that what you will.

[xlerb]

I've adjusted your script a little, and run it on a few things.

Linux/XFS: 26, except when 26 has been deleted, in which case 27.
Linux/tmpfs: 26, except {26..28} where it's 25.
NetBSD/{FFS,LFS,MFS}: 27, except {27,28} where it's 26.
NetBSD/FFS/NFS/Linux: as above.
MacOSX/HFS+: 27, except {3..9,27,28} where it's 26. Not so odd after all, if you think about it.

Also, I somehow failed to know about zsh brace expansion until now. I might owe you a beverage or baked good.

[fivetonsflax]

I don't turn down grain-and-yeast products nearly as often as I perhaps should. I don't have any plans to be in Boston soon, alas.

[xlerb]

POSIX 2004 notes, in an informative section describing seekdir, 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.” It is also stated normatively, under readdir, that “[i]f a file is removed from or added to the directory after the most recent call to opendir() or rewinddir(), whether a subsequent call to readdir() returns an entry for that file is unspecified.”

The issue of what a position within a directory actually means seems to be entirely handwaved.

[fivetonsflax]

Alright, but Marc says: "Create 28 files, delete file 25 and seekdir to file 26: You end up at file 27!"

I realize now that I am not reproducing this on FreeBSD 6.2:

% ./youcantelladirbutyoucanttellitmuch.pl 25
26

[xlerb]

And, more to the point, lots of systems/FSes do weird stuff when you alter the directory between telldir and seekdir.

Anyway, I don't think 26 is the magic number. At least on NetBSD, each __getdents30 call (i.e., getdirentries) is done with a 4kB buffer, of which only 464 bytes are needed for your test case. A little checking shows that the 202nd file is the first in the second batch. On my system, anyway.