]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/commit
Optimize telldir(3)
authorAlan Somers <asomers@FreeBSD.org>
Wed, 6 Dec 2017 22:06:48 +0000 (22:06 +0000)
committerAlan Somers <asomers@FreeBSD.org>
Wed, 6 Dec 2017 22:06:48 +0000 (22:06 +0000)
commit82241ed55ce11de0aaf52d62728f3ef80f814ae7
tree280b6abc75a8c67b5fda6d64ece2779332d72e69
parentb32f18904684ca597e2f4bfc9db9024343e3b203
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.  On
32-bit architectures msdosfs, NFS, and UFS can use the packed
representation, but ZFS and tmpfs can only use it for about the first 128
files per directory.  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.

Reviewed by: kib, mav, mckusick
MFC after: 3 weeks
Sponsored by: Spectra Logic Corp
Differential Revision: https://reviews.freebsd.org/D13385
lib/libc/gen/telldir.c
lib/libc/gen/telldir.h
lib/libc/tests/gen/Makefile
lib/libc/tests/gen/dir2_test.c [new file with mode: 0644]