Page MenuHomeFreeBSD

Optimize telldir(3)
ClosedPublic

Authored by asomers on Dec 5 2017, 10:39 PM.

Details

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.

Diff Detail

Repository
rS FreeBSD src repository
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

asomers created this revision.Dec 5 2017, 10:39 PM
mckusick accepted this revision.Dec 6 2017, 4:46 PM

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

This revision is now accepted and ready to land.Dec 6 2017, 4:46 PM

@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 accepted this revision.Dec 6 2017, 5:10 PM
kib added a subscriber: kib.
kib added inline comments.
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 added inline comments.Dec 6 2017, 5:28 PM
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 accepted this revision.Dec 6 2017, 8:31 PM

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

In D13385#279912, @mav wrote:

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

What's original offset reporting?

mav added a comment.Dec 6 2017, 8:41 PM
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.

In D13385#279917, @mav 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 added a comment.Dec 6 2017, 8:59 PM
In D13385#279917, @mav 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.

Closed by commit rS326640: Optimize telldir(3) (authored by asomers, committed by ). · Explain WhyDec 6 2017, 10:06 PM
This revision was automatically updated to reflect the committed changes.