Messages in this thread | | | Date | Thu, 18 Feb 1999 18:34:28 -0500 (EST) | From | Alexander Viro <> | Subject | Re: fsync on large files |
| |
On Thu, 18 Feb 1999, Raul Miller wrote:
> > > Note that I'm presuming that, within the filesystem, each directory must > > > have an internal unique id (perhaps block # -- if the file system doesn't > > > have inodes), and that the test you want to perform is: directory being > > > renamed is not in the set of {target directory, ancestors of target > > > directory in this same filesystem}. > > > > *All* ancestors, right? How would you recalculate this set on > > rename/rmdir/unlink? And besides, it's O(n^2) memory (n - number > > of inodes in the game) in the worst case, O(n*depth) in best. > > I'm presuming that I could have a way of recognizing when I'm doing a > lookup on a directory that has already been examined, and that I can at > that point skip any further examination of the children of that directory. > > I guess that means that I'd have to normalize each path to match the > way I'm pruning things.. which kinda trashes the idea of a cache. > Hmnm... bad. *And* you have to watch your steps wrt some operation changing the ordering. As I've said - priority inversions. Anyway, suppose you have such sets. How will you recalculate them on rename()? Single rename() may change them big way. *Really* big way. And nonlocal one (i.e. you can't find a new set knowing only the old one and arguments of rename - you'll need to involve other sets too).
> > > > Now, assume that another lookup goes through the alternative path in the > > > > same time from the other direction. Your actions wrt locking? > > > > > > Use a per-filesystem directory rename lock when renaming a directory > > > and parallel parents are an issue. [I guess, to be safe, we'd have to > > > use the lock to determine if parallel parents are an issue.] > > > > Erm... You'll need to do it on any lookup. > > Why? Maybe I'm getting into hot water here, but can't you just get > away with the existing "one dcache entry for the path you're looking > up" mechanism?
*If* it is already in dcache. When you are doing real lookup (i.e. fs-level one) you will have to lock the directory.
> > Right now we lock the parent on each lookup step and release it before > > the next one. It is not rename-specific. Locking issues will become > > very tricky unless you are going to throttle lookups in the same way > > it is done with rename. I.e. single-threaded fs. Welcome back to > > Minix. Locking is used *not* only for rename/rename race prevention. > > Without it you'll get a race in about any pair of namespace-related > > operations. > > Eh? > > I can see that you need the rename lock for rename. > I can see that you need it to link directories. > I don't see that you need it for readdir. > I don't see that you need it for mkdir.
You'll get mkdir racing with lookup. You'll get creat and unlink racing with lookup. You'll get all sorts of nastyness when one thing tries to parse the data structure and other modifies it. Things will get even worse if you will get two writers on the same directory. You will have to make low-level lookup stuff aware of the intermediate states of link creation. It's *not* easy. Directory may be much more complex beast that array of fixed-sized elements. Even on ffs/ext2/ufs it's a list of variable-sized structures and adding a link involves finding an entry with sufficient amount of slack and splitting it up. If it's btree-based... shrug. We might go for some analog of read-write lock, but if your change assumes that VFS wants filesystems to sustain several writers or writer + reader in the same directory... As far as I'm concerned it's *not* a variant. Up to Linus, indeed, but IMO it's *the* way to madness. Please, read fs/namei.c and fs/dcache.c (along with, say it, ext2/namei.c) to figure out what happens. Watch the ->i_sem stuff - it handles all race-prevention logics. Holding semaphores on parent *is* needed, otherwise it will come back in fs drivers and will give you mind-boggling amount of deadlocks.
- 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/
| |