problem with get_empty_filp().

Michael O'Reilly (
Thu, 22 Aug 1996 10:15:49 +0800

I finally managed to work out why the current version of
get_empty_filp() is so slow. The basic problem is the model used in
writing it. The current version will work well if all file descriptors
are used for a reasonably constant amount of time.

The problem is that in practice this isn't so. Most file descriptors
are in use for a few seconds, or for a signficantly longer period of
time. (i.e. inetd vs ls)

The current version tends to move all the 'old' in-use file
descriptors to the front of the list (by moving all the free ends to
the end as they get used), where they get searched every time in an
effort to find an unused one.

With 1000 allocated desciptors (say), and 500 being in use in programs
like inetd, and syslogd and web servers, then after only a few hours
usage, the first_file list will have the 500 in-use descriptors at the
front, and all the empty ones will only come after those 500. As
descriptors in the first 500 get free'd, they immediately get moved to
the end, leaving the front of the list being solid used descriptors.

On a machine with a large number of file descriptors in use, with a
large number of those being long held, you end up with
get_empty_filp() needing to search most of the list every time to find
a free one.

Which all explains the huge speed difference between the current
version, and the patch I posted a few weeks ago. (for those that
missed it, the patch simply changes things so a search starts from one
after the last FD found, and doesn't move any items around the list).


Ps. quick look over the 5 machines with profiling turned on shows
get_empty_filp() in the top 5 functions (by CPU time used) on every
one, with get_empty_filp() being number 1 on the WWW machine, and the
un-patched terminal server.