Messages in this thread | | | Date | Tue, 16 Nov 1999 19:22:07 +0100 | From | Jamie Lokier <> | Subject | Re: Ext2 defragmentation |
| |
Alexander Viro wrote: > > If `a/b' is updated many times, `a' is updated just once between tree > > searching operations. That's once a day if your operation is updatedb. > > It applies recursively, therefore the filesystem very quickly settles > > into a state where all the paths that need flagging are already flagged. > > The path inodes don't have to remain in memory. > > Oh, please. How the heck will tree search tell the kernel what it is? How > will you deal with changes that happen _during_ the search? What > privileges will you need for 'cleaning' directory?
I've already offered several thoughts on implementation. Don't you read my posts? <g>
The one flag method: Only one search program is allowed. So it had better be root only, for updatedb type of thing. ioctl() on a directory (or optionally object) atomically does test_and_set on the bit. Modifying an object clears the bit on its parent directory if it was set. And if the parent bit changed, it clears the parent's parent etc. This stops as soon as you reach a clear bit.
The serial number method. Any number of search programs are allowed and don't interfere. ioctl() does "read number and increment if bottom bit clear". Modifying object does "increment number if bottom bit set", recursively like the flag method. Only a few bits are required if you do a combination thing with ctime, and those bits could be stolen from the NFS revision word. Exercise for reader: show why that doesn't lead to lots of inode updates.
Hard links are complicated in both methods. One strategy is to have a second flag: "this path may leads to a directory containing a hard link", and let the find program deal with those paths in the traditional way. Most paths do not lead to hard links.
-- Jamie
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |