i386/108961: High CPU use on directories containing files with multiple UIDs

[Jonathan Hammond]

>Number:         108961
>Category:       i386
>Synopsis:       High CPU use on directories containing files with multiple UIDs
>Confidential:   no
>Severity:       non-critical
>Priority:       medium
>Responsible:    freebsd-i386
>State:          open
>Quarter:        
>Keywords:       
>Date-Required:
>Class:          sw-bug
>Submitter-Id:   current-users
>Arrival-Date:   Fri Feb 09 10:00:29 GMT 2007
>Closed-Date:
>Last-Modified:
>Originator:     Jonathan Hammond
>Release:        5.1 Release (affects 5.1 up to latest 6)
>Organization:
>Environment:
FreeBSD test.skynet.co.uk 5.1-RELEASE-p18 FreeBSD 5.1-RELEASE-p18 #0: Thu Feb  8 17:06:18 GMT 2007     root at test.skynet.co.uk:/usr/src/sys/i386/compile/TEST  i386
>Description:
We have noticed an issue where multiple files exist in a directory with
different UIDs.  We are running a sendmail mailserver , and all user
mail gets written to /var/mail directory as is usual, each mailbox file
with the UID of the user.  We have moved the server to FreeBSD 6, and
straightaway noticed much higher CPU load while accessing that
directory; a simple "ls -l" command would take over 10 seconds to
complete on the new server where before it took less than a second.

After replicating the problem on a test server, we were able to confirm
that the issue only occured when there were multiple files owned by
multiple UIDs in a directory, a thousand files of the same UID would
take less than a second to list.  

After performing tests on multiple versions of FreeBSD we have narrowed
it down to some change that occured between 5.0 and 5.1 and is still
present in the latest 6-BRANCH RELEASE.  We created a
test script that creates 1000 users and creates a file owned by each of
them in one directory.  An ls -l command is then performed and timed. 
Here are the results with both FreeBSD 5.0 and 5.1

FreeBSD-5.0 RELEASE

Creating 1000 users
User: 01000

Doing a ls -l in /tmp/ownership-slowdown for 1000 users took ...
        0.08s real              0.03s user              0.04s sys
Chowning all files in /tmp/ownership-slowdown to nobody
Doing a ls -l again in /tmp/ownership-slowdown for 1000 users took ...
        0.03s real              0.00s user              0.02s sys


FreeBSD-5.1 RELEASE

Creating 1000 users
User: 01000

Doing a ls -l in /tmp/ownership-slowdown for 1000 users took ...
        12.43s real             1.57s user              10.79s sys
Chowning all files in /tmp/ownership-slowdown to nobody
Doing a ls -l again in /tmp/ownership-slowdown for 1000 users took ...
        0.03s real              0.02s user              0.00s sys



>How-To-Repeat:
Create multiple files owned by multiple users in a single directory.  time an ls -l on this directory. Test script can be provided.
>Fix:

>Release-Note:
>Audit-Trail:
>Unformatted: