Hello,
It looks like the rmdir syscall behaves strangely in 2.4 kernels :
saffroy@sisley:~> uname -a
Linux sisley 2.2.14-5.0smp #1 SMP Tue Mar 7 21:01:40 EST 2000 i686 unknown
saffroy@sisley:/tmp> mkdir foo
saffroy@sisley:/tmp> rmdir foo/.
saffroy@sisley:/tmp> mkdir foo
saffroy@sisley:/tmp> cd foo/
saffroy@sisley:/tmp/foo> rmdir .
saffroy@sisley:/tmp/foo> cd ..
saffroy@sisley:/tmp>
[root@picasso /tmp]# uname -a
Linux picasso 2.4.0-test10 #1 SMP Thu Nov 9 14:30:23 GMT+2 2000 i586 unknown
[root@picasso /tmp]# mkdir foo
[root@picasso /tmp]# rmdir foo/.
rmdir: foo/.: Device or resource busy
[root@picasso /tmp]# rmdir foo/
[root@picasso /tmp]# mkdir foo
[root@picasso /tmp]# cd foo
[root@picasso foo]# rmdir .
rmdir: .: Device or resource busy
[root@picasso foo]# rmdir ../foo/
[root@picasso foo]#
As you see, it looks like the rmdir fails simply because the dir name ends
with a dot !! This is confirmed by sys_rmdir in fs/namei.c, around line
1384 :
switch(nd.last_type) {
case LAST_DOTDOT:
error = -ENOTEMPTY;
goto exit1;
case LAST_ROOT: case LAST_DOT:
error = -EBUSY;
goto exit1;
}
Should we rip off the offending "case LAST_DOT" ? Or do we need a smarter
patch ? Is it really a problem that a process has its current directory
deleted ? How about the root ?
The man page for rmdir(2) should be updated as well, the current one
states :
EBUSY pathname is the current working directory or root
directory of some process.
Maybe rmdir should return EBUSY only when trying to remove a mount point ?
Regards,
--
Jean-Marc Saffroy - Research Engineer - Silicomp Research Institute
mailto:[email protected]
On Thu, 16 Nov 2000, Jean-Marc Saffroy wrote:
>
> As you see, it looks like the rmdir fails simply because the dir name ends
> with a dot !! This is confirmed by sys_rmdir in fs/namei.c, around line
> 1384 :
>
> switch(nd.last_type) {
> case LAST_DOTDOT:
> error = -ENOTEMPTY;
> goto exit1;
> case LAST_ROOT: case LAST_DOT:
> error = -EBUSY;
> goto exit1;
> }
>
> Should we rip off the offending "case LAST_DOT" ? Or do we need a smarter
> patch ? Is it really a problem that a process has its current directory
> deleted ? How about the root ?
The cwd is not the problem. The '.' is.
The reason for that check is that allowing "rmdir(".")" confuses a lot of
UNIX programs, because it wasn't traditionally allowed.
> The man page for rmdir(2) should be updated as well, the current one
> states :
> EBUSY pathname is the current working directory or root
> directory of some process.
That's definitely wrong. You can do
rmdir `pwd`
and that's fine (not all filesystems will let you do that, but that's a
low-level filesystem issue). It's really only the special names "." and
".." that cannot be removed.
Linus
Jean-Marc Saffroy <[email protected]>:
>
> It looks like the rmdir syscall behaves strangely in 2.4 kernels :
>
> saffroy@sisley:~> uname -a
> Linux sisley 2.2.14-5.0smp #1 SMP Tue Mar 7 21:01:40 EST 2000 i686 unknown
> saffroy@sisley:/tmp> mkdir foo
> saffroy@sisley:/tmp> rmdir foo/.
> saffroy@sisley:/tmp> mkdir foo
> saffroy@sisley:/tmp> cd foo/
> saffroy@sisley:/tmp/foo> rmdir .
> saffroy@sisley:/tmp/foo> cd ..
> saffroy@sisley:/tmp>
>
> [root@picasso /tmp]# uname -a
> Linux picasso 2.4.0-test10 #1 SMP Thu Nov 9 14:30:23 GMT+2 2000 i586 unknown
> [root@picasso /tmp]# mkdir foo
> [root@picasso /tmp]# rmdir foo/.
> rmdir: foo/.: Device or resource busy
> [root@picasso /tmp]# rmdir foo/
> [root@picasso /tmp]# mkdir foo
> [root@picasso /tmp]# cd foo
> [root@picasso foo]# rmdir .
> rmdir: .: Device or resource busy
> [root@picasso foo]# rmdir ../foo/
> [root@picasso foo]#
>
> As you see, it looks like the rmdir fails simply because the dir name ends
> with a dot !! This is confirmed by sys_rmdir in fs/namei.c, around line
> 1384 :
>
> switch(nd.last_type) {
> case LAST_DOTDOT:
> error = -ENOTEMPTY;
> goto exit1;
> case LAST_ROOT: case LAST_DOT:
> error = -EBUSY;
> goto exit1;
> }
>
> Should we rip off the offending "case LAST_DOT" ? Or do we need a smarter
> patch ? Is it really a problem that a process has its current directory
> deleted ? How about the root ?
>
> The man page for rmdir(2) should be updated as well, the current one
> states :
> EBUSY pathname is the current working directory or root
> directory of some process.
>
> Maybe rmdir should return EBUSY only when trying to remove a mount point ?
This may not be relevent, but it actually is busy - consider that the
namei lookup must open the directory named "foo" (during the unlink
processing. While that directory is open it is searched for the name ".".
Now that the path is recognized, the unlink attempts to remove the directory
"." from the directory. This is a loop, which is held busy by the lookup of
the name "foo/.". Since this REALLY is a hard link between "." and "foo",
there is no way to know what is causing it to be busy - another process, or
a different open on the directory (foo is open for modification after all).
I admit that some special case handling such as verifying that the use
count of . equals 1 AND that the inode of "." equals the inode of "foo"
before allowing it (and foo) to be removed would work.
But why bother. It is busy, even if only by the process attempting the
unlink, and then only during the unlink system call. This becomes a
sort of recursive use of the unlink system call, that must also unlink
the name "foo" from the parent directory (.., or the directory containing foo).
If the parent directory is NOT handled then you get a corrupted directory
named foo, that doesn't have "." in it.
It would be simpler to just say "don't do that".
-------------------------------------------------------------------------
Jesse I Pollard, II
Email: [email protected]
Any opinions expressed are solely my own.
On Thu, 16 Nov 2000, Linus Torvalds wrote:
> The cwd is not the problem. The '.' is.
>
> The reason for that check is that allowing "rmdir(".")" confuses a lot of
> UNIX programs, because it wasn't traditionally allowed.
Moreover, allowing it means that you overload the semantics of rmdir()
(and rename(), where it becomes really nasty). And I'm not talking about
the locking issues - the things become extremely nasty there, esp. in
cases like foo/bar/., where bar is a symlink.
On Thu, 16 Nov 2000, Linus Torvalds wrote:
> The cwd is not the problem. The '.' is.
>
> The reason for that check is that allowing "rmdir(".")" confuses a lot of
> UNIX programs, because it wasn't traditionally allowed.
This is a point I don't understand here : do you mean that they are
confused if they can rmdir "." but not if they can rmdir their cwd
differently ? What's the difference ?
I am not saying that rmdir MUST be allowed on "." ; I just suggested that
it be allowed _because_ you can rmdir your cwd anyway. Now if rmdir "." is
forbidden, then I think rmdir `pwd` should fail as well. Or am I missing
something ?
--
Jean-Marc Saffroy - Research Engineer - Silicomp Research Institute
mailto:[email protected]
On Thu, 16 Nov 2000, Jean-Marc Saffroy wrote:
> On Thu, 16 Nov 2000, Linus Torvalds wrote:
>
> > The cwd is not the problem. The '.' is.
> >
> > The reason for that check is that allowing "rmdir(".")" confuses a lot of
> > UNIX programs, because it wasn't traditionally allowed.
>
> This is a point I don't understand here : do you mean that they are
> confused if they can rmdir "." but not if they can rmdir their cwd
> differently ? What's the difference ?
rmdir() is _not_ "kill the directory identified by name and remove all
links to it". It's "remove a given link and .. in directory pointed
by it, then schedule directory for removal".
BTW, cwd is irrelevant - /tmp/foo/. would demonstrate the same behaviour.
It becomes really obvious when you look at rename() - you act on links,
not on inodes. The only reason why we could try to overload that for
directories was that there is a special link - one from the parent.
However, _finding_ said link in race-free way is extremely nasty.
Especially for cases like /tmp/foo/. where /tmp/foo is a symlink to
/tmp/bar/baz. AFAIK Linux was the only system that tried to be smart
in that area. And that attempt was _not_ successful - there were rather
interesting races around the thing. Besides, we clearly violated
all relevant standards - rmdir() and rename() are required to fail
if the last component of name happens to "." or "..".
On Thu, 16 Nov 2000, Alexander Viro wrote:
> > This is a point I don't understand here : do you mean that they are
> > confused if they can rmdir "." but not if they can rmdir their cwd
> > differently ? What's the difference ?
>
> rmdir() is _not_ "kill the directory identified by name and remove all
> links to it". It's "remove a given link and .. in directory pointed
> by it, then schedule directory for removal".
Now I see your point : by "." or "foo/." you mean the directory itself,
while "foo" or "foo/" refer to the link to the directory, and they are
obviously different objects... at least since hard links on directories
were introduced. Fine.
> BTW, cwd is irrelevant - /tmp/foo/. would demonstrate the same behaviour.
We saw it, and found it shocking for the very same reasons...
> It becomes really obvious when you look at rename() - you act on links,
> not on inodes. The only reason why we could try to overload that for
> directories was that there is a special link - one from the parent.
> However, _finding_ said link in race-free way is extremely nasty.
> Especially for cases like /tmp/foo/. where /tmp/foo is a symlink to
> /tmp/bar/baz. AFAIK Linux was the only system that tried to be smart
> in that area. And that attempt was _not_ successful - there were rather
> interesting races around the thing.
Ok, now I get it. Thanks for this much clearer explanation.
I guess that this was not a problem in 2.2 precisely because hard links on
directories were forbidden, right ?
> Besides, we clearly violated
> all relevant standards - rmdir() and rename() are required to fail
> if the last component of name happens to "." or "..".
By standard, do you imply 'de facto' ? Or does any source clearly state
this ?
--
Jean-Marc Saffroy - Research Engineer - Silicomp Research Institute
mailto:[email protected]
On Thu, 16 Nov 2000, Jean-Marc Saffroy wrote:
> Now I see your point : by "." or "foo/." you mean the directory itself,
> while "foo" or "foo/" refer to the link to the directory, and they are
> obviously different objects... at least since hard links on directories
> were introduced. Fine.
Sorry, no. Directories still have only one parent. However, "." _is_ a
link. It's not a shortcut or something like that - it's a real, normal,
honest-to-$DEITY directory entry. Aka link.
> Ok, now I get it. Thanks for this much clearer explanation.
>
> I guess that this was not a problem in 2.2 precisely because hard links on
> directories were forbidden, right ?
That was a problem and that still _is_ a problem - these races are unsolvable
without a pretty serious namei.c rewrite and unless Alan is willing to go
for that in 2.2 they are there to stay.
As for the hard links being forbidden - in some sense they never were, in
some sense they still are. Situation didn't change - directory can't have
more than one parent. OTOH, every directory has at least two links - from
the parent and from itself (+ one from each child).
> > Besides, we clearly violated
> > all relevant standards - rmdir() and rename() are required to fail
> > if the last component of name happens to "." or "..".
>
> By standard, do you imply 'de facto' ? Or does any source clearly state
> this ?
POSIX, for one thing.
At 07:51 PM 11/16/2000 +0100, you wrote:
>Now I see your point : by "." or "foo/." you mean the directory itself,
>while "foo" or "foo/" refer to the link to the directory, and they are
>obviously different objects... at least since hard links on directories
>were introduced. Fine.
. and foo/. are also links, not directories... the directories themselves
are filesystem internal objects, and not discussed by the standard. I
didn't know that linux supported hard links to directories... Isn't that
just asking for trouble?
> > Besides, we clearly violated
> > all relevant standards - rmdir() and rename() are required to fail
> > if the last component of name happens to "." or "..".
>
>By standard, do you imply 'de facto' ? Or does any source clearly state
>this ?
It rarely hurts to violate even a written standard when it says something
like this... If it says something like this (which can only happen
intentionally, afaict) should fail, but you can do something intelligent
instead, you probably should.
--
This message has been brought to you by the letter alpha and the number pi.
Open Source: Think locally, act globally.
David Feuer
[email protected]
Followup to: <[email protected]>
By author: David Feuer <[email protected]>
In newsgroup: linux.dev.kernel
>
> . and foo/. are also links, not directories... the directories themselves
> are filesystem internal objects, and not discussed by the standard. I
> didn't know that linux supported hard links to directories... Isn't that
> just asking for trouble?
>
It is on filesystems which has ".." physically on disk. Linux no
longer requires this, although for example ext2 does have this.
I don't believe it's inherently impossible in Linux anymore. In fact,
vfsbinds provide a lot of the same kind of functionality; the main
difference between vfsbinds and hard links are that the former (a) can
cross filesystem boundaries and (b) aren't persistent.
-hpa
--
<[email protected]> at work, <[email protected]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt
On 16 Nov 2000, H. Peter Anvin wrote:
[hardlinks on directories]
> I don't believe it's inherently impossible in Linux anymore. In fact,
Yes, it is. bindings are asymmetrical. And that's the reason why they
work while links to directories do not.
> vfsbinds provide a lot of the same kind of functionality; the main
> difference between vfsbinds and hard links are that the former (a) can
> cross filesystem boundaries and (b) aren't persistent.
Here's one more: you can't rename across the binding boundary. They _are_
mounts, so they avoid all that crap with loop creation on rename, etc.
Take a generic DAG and try to implement rename() analog on it. Have fun
catching the cases that would make the graph disconnected.
At 06:10 PM 11/16/2000 -0500, you wrote:
>Here's one more: you can't rename across the binding boundary. They _are_
>mounts, so they avoid all that crap with loop creation on rename, etc.
>Take a generic DAG and try to implement rename() analog on it. Have fun
>catching the cases that would make the graph disconnected.
How could the graph become disconnected? What does connectedness have to
do with naming?
--
This message has been brought to you by the letter alpha and the number pi.
Open Source: Think locally, act globally.
David Feuer
[email protected]
On Thu, 16 Nov 2000, David Feuer wrote:
> At 06:10 PM 11/16/2000 -0500, you wrote:
> >Here's one more: you can't rename across the binding boundary. They _are_
> >mounts, so they avoid all that crap with loop creation on rename, etc.
> >Take a generic DAG and try to implement rename() analog on it. Have fun
> >catching the cases that would make the graph disconnected.
>
> How could the graph become disconnected? What does connectedness have to
> do with naming?
If every way from foo to target goes through the source rename(source,target)
_will_ make the graph disconnected. Checking that for generic DAG is a hell.
Moreover, if there is an oriented path from source to target rename(source,
target) will create a loop. Again, good luck checking whether there is
such a path. If you think that loops are not a problem - fine, their presense
will make checking the first condition (for every node foo there exists a
path foo,p1,...,pn,target such that source doesn't belong to {p1,...,pn})
_much_ funnier.
For trees both conditions turn into (source is not an ancestor of target)
and that's easy to check. Try to do that for generic DAG. Solutions that
cost O(graph size) are _not_ acceptable - graph is the whole directory
structure.
On Thu, Nov 16, 2000 at 02:47:35PM +0100, Jean-Marc Saffroy wrote:
> As you see, it looks like the rmdir fails simply because the dir name ends
> with a dot !! This is confirmed by sys_rmdir in fs/namei.c, around line
> 1384 :
>
> switch(nd.last_type) {
> case LAST_DOTDOT:
> error = -ENOTEMPTY;
> goto exit1;
> case LAST_ROOT: case LAST_DOT:
> error = -EBUSY;
> goto exit1;
> }
I see that an entire discussion has taken place. Let me just remark this,
quoting the Austin draft:
If the path argument refers to a path whose final component is either
dot or dot-dot, rmdir( ) shall fail.
EINVAL The path argument contains a last component that is dot.
EEXIST or ENOTEMPTY The path argument names a directory that is not an empty directory,
EBUSY The directory to be removed is currently in use by the system or some process
and the implementation considers this to be an error.
So, it seems that -EINVAL would be a better return value in case LAST_DOT.
Andries
On Fri, 17 Nov 2000, Guest section DW wrote:
> I see that an entire discussion has taken place. Let me just remark this,
> quoting the Austin draft:
>
> If the path argument refers to a path whose final component is either
> dot or dot-dot, rmdir( ) shall fail.
>
> EINVAL The path argument contains a last component that is dot.
[snip]
> So, it seems that -EINVAL would be a better return value in case LAST_DOT.
No problems with that... Linus, could you apply the following (cut-and-paste
alert)?
--- fs/namei.c Fri Nov 17 18:43:20 2000
+++ fs/namei.c.new Fri Nov 17 18:48:00 2000
@@ -1381,8 +1381,11 @@
case LAST_DOTDOT:
error = -ENOTEMPTY;
goto exit1;
- case LAST_ROOT: case LAST_DOT:
+ case LAST_ROOT:
error = -EBUSY;
+ goto exit1;
+ case LAST_DOT:
+ error = -EINVAL;
goto exit1;
}
down(&nd.dentry->d_inode->i_sem);
Alexander Viro <[email protected]> writes:
> If every way from foo to target goes through the source rename(source,target)
> _will_ make the graph disconnected. Checking that for generic DAG is a hell.
Why do you say this? Algorithms for cycle detection are comparatively
computationally expensive, to be sure, but they are well understood. In
fact, this is only a limited case of cycle detection; unless I
misunderstand, it's a form of dominator detection, as seen, for
instance, in compilers. You're looking to see if the source dominates
the target, and if it does, you scream.
It needn't be hellish, *if* we can get a list of all a directory's
parents given that directory in reasonable time, and that depends on how
multiple-parents is implemented. Checking if the source dominates the
target (for paths from the root) wouldn't be anywhere near so bad
then. See below for an algorithm to try out --- well, for its name. I
have a good few references to relevant papers too (so too will anyone
with much to do with compiler hacking.)
> Moreover, if there is an oriented path from source to target rename(source,
> target) will create a loop. Again, good luck checking whether there is
> such a path.
Loops and what they do to things like ftw() --- and thus to the
expectations of userspace programs --- are I think the *real* reason why
no Unix has ever implemented this. There are probably a good few
programs that depend on ftw() and friends descending into all
directories that you asked them to, and then there's all those recursive
tree traversers in userspace that *don't* use ftw().
Certainly all cycles must be banned. Luckily the cycles aren't that
nasty to detect. You can detect cycles with the same algorithm you use
to detect the rename(source,target) case; if the source dominates the
target you can't have a link to the source in the target, as that would
make a cycle. (I may be missing some cases that make cycle detection
harder than this; it's late and I'm drunk and tired, and it's been years
since I paid much attention to anything much to do with cycle
detection.)
> If you think that loops are not a problem - fine, their presense
> will make checking the first condition (for every node foo there exists a
> path foo,p1,...,pn,target such that source doesn't belong to {p1,...,pn})
> _much_ funnier.
It's userspace that this kills; the kernel can be fixed, but fixing the
entirety of userspace isn't going to happen :)
> For trees both conditions turn into (source is not an ancestor of target)
> and that's easy to check. Try to do that for generic DAG. Solutions that
> cost O(graph size) are _not_ acceptable - graph is the whole directory
> structure.
There are well-understood algorithms for computing dominators that do
not cost that much. The Lengauer-Tarjan algorithm takes O(n ln n) time,
where n is the depth of the graph (== the depth of the deepest path to
get to the target). However it is rather heavy-duty for a kernel, and I
rather doubt that any kernels use it :)
The O(graph size) solutions are deeply crap ways of computing
dominators; they normally start by sweeping over the whole graph working
out who dominates who from the top down. Algorithms like that were
obsolete by the late seventies!
Lengauer-Tarjan works from the bottom up; as long as you can do that,
you're home free. (Well, not free; O(n ln n.) ;} )
Ancient paper reference (there are probably newer papers than this):
Lengauer, T., & Tarjan, R. E., _A fast algorithm for finding dominators
in a flow graph_, 1979, _Transactions on Programming Languages and
Systems_ 13(4): 451--490.
(Somewhere, I have a copy of this paper. Cthulhu alone knows where
though.)
(Disclaimer: I've never tried to use Lengauer-Tarjan in filesystem code;
it just seems likely to me that it or some variant of it would work
there, except of course that it is a somewhat overblown algorithm to
find in a kernel. :) )
--
`The phrase `causes storage to be reserved', doesn't mean that it causes
storage to be reserved. This is a fundamental misunderstanding of
Standardeze.' --- Mike Stump on the GCC list
On 18 Nov 2000, Nix wrote:
> Alexander Viro <[email protected]> writes:
>
> > If every way from foo to target goes through the source rename(source,target)
> > _will_ make the graph disconnected. Checking that for generic DAG is a hell.
>
> Why do you say this? Algorithms for cycle detection are comparatively
> computationally expensive, to be sure, but they are well understood. In
s/computationally/& and IO/. If we are thinking about the same algorithm -
good luck doing that if your data structures are on disk. Think of
reference locality in that animal. Try to estimate the amount of IO and
fun with seeks. It's nice when you have your data in-core, but when it's
on-disk and you want reasonable locality of references for normal uses...
>
> On Fri, 17 Nov 2000, Guest section DW wrote:
>
> > I see that an entire discussion has taken place. Let me just remark this,
> > quoting the Austin draft:
> >
> > If the path argument refers to a path whose final component is either
> > dot or dot-dot, rmdir( ) shall fail.
> >
> > EINVAL The path argument contains a last component that is dot.
> [snip]
>
Then, I don't understand why the EINVAL error condition does not also include
dot-dot as last component.
> > So, it seems that -EINVAL would be a better return value in case LAST_DOT.
>
> No problems with that... Linus, could you apply the following (cut-and-paste
> alert)?
>
I think that there is another case where EINVAL (or EBUSY) should be more
relevant than ENOTEMPTY: consider a process invoking 'rmdir("..")' where "."
is empty and its current root directory (just because ".." and "." refer
to the same directory which is actually empty).
Anyway, thanks for your explainations on this special UNIX FS behaviour.
-Eric
+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ Eric PAIRE
Web : http://www.ri.silicomp.com/~paire | Groupe SILICOMP - Research Institute
Email: [email protected] | 2, avenue de Vignate
Phone: +33 (0) 476 63 48 71 | F-38610 Gieres
Fax : +33 (0) 476 51 05 32 | FRANCE
On Mon, Nov 20, 2000 at 09:32:39AM +0100, Eric Paire wrote:
> >
> > On Fri, 17 Nov 2000, Guest section DW wrote:
> >
> > > I see that an entire discussion has taken place. Let me just remark this,
> > > quoting the Austin draft:
> > >
> > > If the path argument refers to a path whose final component is either
> > > dot or dot-dot, rmdir( ) shall fail.
> > >
> > > EINVAL The path argument contains a last component that is dot.
> > [snip]
> >
> Then, I don't understand why the EINVAL error condition does not also include
> dot-dot as last component.
Answer 1: It is the (draft) standard. No understanding required.
Answer 2: Whenever ENOTEMPTY is available, this much more precise error return
is to be preferred above EINVAL.