Date: Sat, 16 Aug 1997 12:10:35 -0700 (MST) From: Terry Lambert <terry@lambert.org> To: dg@root.com Cc: ponds!rivers@dg-rtp.dg.com, hackers@FreeBSD.ORG Subject: Re: More info on slow "rm" times with 2.2.1+. Message-ID: <199708161910.MAA04371@phaeton.artisoft.com> In-Reply-To: <199708161207.FAA26252@implode.root.com> from "David Greenman" at Aug 16, 97 05:07:22 am
next in thread | previous in thread | raw e-mail | index | archive | help
> > It would be trivial for me to verify any slow or fast times - all > >I've got to do is make a big directory... seems that ~300 files is > >enough to run into whatever the problem may be... > > How many files are in the directory isn't important. What is important is > the size of the directory. You can have a 20MB directory and yet have only a > 100 files in it. There is code to free up unused space in directories, but > it only works if the free space is at the end. If the directory is large, > then it will take a large amount of time to search through it. Specifically, if I have a directory with 20,000 entries, and I average 32 entries per block ((512/32) - 8 bytes entry data per 4-7 byte name), then I am using 625 blocks. The opendir/readdir library routines operate by calling getdents() once per block to refill the user space "snapshot" of a directory block, on a block by block basis. That is, I call opendir and it calls getdents() and grabs the first 32 entries. I call readdir and move forward unitil I've returned all 32, and then call getdents() again. Now you are linearly traversing the directory forward (using getdents()) to do this. Say you want to remove all entries. You delete the first entry (ignore the vagries of "." and ".." for a second). This modifies the first directory block. Now you get halfway through. You must linearly traverse 312 directory blocks in the lookup for the entry you are going to delete. Now you are 3/4 of the way thorugh. You must linearly traverse 466 directory blocks in the lookup for the entry you are going to delete. In other words, your traversal is going to increase exponentially with a slope equalt to a square exponential progreassion divided by 32 (or whatever your average number of entries per block is, given your average file name length). Deleteing the last entries are going to take the longest of all. There were some additional things added into the unlink path in respect for the lease code, and there were some additional things added into the getdents path in support of NFSv3. And there is a *lot* of additional function call and contention overhead from the BSD4.4-Lite2 locking code, which is upside down (IMO, anyway). So yes, it's slower than it was, but no, it wasn't fast before; it had the same problems. Note that changing the on disk structure for installed systems is problematic. You *could* treat the directory block as a skliplist structure, and deal with it that way. That would gain you significant speedup, a the cost of modifying the ondisk structure to add skip records to the front of blocks. Alternately, you could truncate blocks off the front of the directory, as they were deleted (the first block could not be truncated, since it must contain "." and "..", but subsequent blocks could be, rendering the directory "sparse"; a bit of a pain for fsck, but it would let you skip the intermediate block reads, if you looked for 0 blocks in the directory traversal). Short of changing the directory structure, or changing the way large deletes are handled, or fixing some of the FS locking and caching issues, there's really nothing you can do about it. Regards, Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199708161910.MAA04371>