Optimize telldir(3)

[asomers]

Summary

Optimize telldir(3)

Currently each call to telldir() requires a malloc and adds an entry to a
linked list which must be traversed on future telldir(), seekdir(),
closedir(), and readdir() calls. Applications that call telldir() for every
directory entry incur O(n^2) behavior in readdir() and O(n) in telldir() and
closedir().

This optimization eliminates the malloc() and linked list in most cases by
packing the relevant information into a single long. On 64-bit
architectures, msdosfs, NFS, tmpfs, UFS, and ZFS can all use the packed
representation. Memory savings is about 50 bytes per telldir(3) call.
Speedup for telldir()-heavy directory traversals is about 20-30x for one
million files per directory.

An outstanding question is how to handle directories with > 2^31 files on
32-bit architectures. The current implementation breaks telldir() for such
directories.

Test Plan

ATF test cases added run on UFS, ZFS, msdosfs, TMPFS. Benchmarks on the
same filesystems for both amd64 and i386.

[mckusick]

This looks like an excellent improvement. I have not reviewed every line of code, but the concept is sound.

[asomers]

@mckusick what do you think I should do on 32-bit architectures for directories with > 2 billion files? telldir(3) can't return an error, so my choices are basically to assert() or to return a bogus value that won't work with seekdir().

[kib]

lib/libc/gen/telldir.c

60 ↗

(On Diff #36272)

Why doing this in a function body instead of placing the assert right after the union definition ?

61 ↗

(On Diff #36272)

Style: continuation line should have 4-spaces indent.

71 ↗

(On Diff #36272)

Style: spaces around binary op (' << ').

109 ↗

(On Diff #36272)

I am sure that the question is theoretical, because address space would not allow to allocate that many ddlocs. size_t is long (morally).

[asomers]

lib/libc/gen/telldir.c

109 ↗

(On Diff #36272)

Good point. I didn't think about ENOMEM. I'll just document the issue and suppress the inevitable Coverity CID. I'll make your suggested style changes, too.

[mav]

Looks good to me, at least until we implement original offset reporting.

[asomers]

In D13385#279912, @mav wrote:

Looks good to me, at least until we implement original offset reporting.

What's original offset reporting?

[mav]

In D13385#279914, @asomers wrote:

In D13385#279912, @mav wrote:

Looks good to me, at least until we implement original offset reporting.

What's original offset reporting?

64-bit inode project commit r318736 introduced new field d_off into struct dirent. If supported by all file systems, it would obsolete all this code.

[asomers]

In D13385#279917, @mav wrote:

In D13385#279914, @asomers wrote:

In D13385#279912, @mav wrote:

Looks good to me, at least until we implement original offset reporting.

What's original offset reporting?

64-bit inode project commit r318736 introduced new field d_off into struct dirent. If supported by all file systems, it would obsolete all this code.

It looks like d_off is currently supported by no file systems. Is the intent that one could pass a d_off directly to lseek to seek to a particular directory entry?

[kib]

In D13385#279931, @asomers wrote:

In D13385#279917, @mav wrote:

In D13385#279914, @asomers wrote:

In D13385#279912, @mav wrote:

Looks good to me, at least until we implement original offset reporting.

What's original offset reporting?

64-bit inode project commit r318736 introduced new field d_off into struct dirent. If supported by all file systems, it would obsolete all this code.

It looks like d_off is currently supported by no file systems. Is the intent that one could pass a d_off directly to lseek to seek to a particular directory entry?

Yes.

But telldir() still must work with long results, and I am sure that the support will not be implemented for all filesystems. d_off is mostly for (future) NFS server benefit.