The maximum number of followed symlinks seems to be set to 5.
This seems small when compared to other filesystem limits.
Is there some objection to it being raised? Should it be
something like Glib's '20' or '255'?
It would involve a change in include/namei.h and perhaps
a cleanup of the comment (which states the limit is '8') in
namei.c
There is some confusion with the shell utilities thinking
some links are valid, but other utilities giving an error:
> readlink -f cpu/args.t
/usr/src/packages/BUILD/perl-5.8.6/t/op/args.t
> cat cpu/args.t
cat: cpu/args.t: Too many levels of symbolic links
> namei cpu/args.t
f: cpu/args.t
d cpu
l args.t -> ../op/args.t
d ..
l op -> ../t/op/
d ..
l t -> perldir/t
l perldir -> perl-5.8.6
l perl-5.8.6 -> ../build/perl-5.8.6
d ..
l build -> BUILD
d BUILD
d perl-5.8.6
d t
d op
- args.t
> The maximum number of followed symlinks seems to be set to 5.
>
# grep 40 fs/namei.c
namei.c: * limiting consecutive symlinks to 40.
namei.c: if (current->total_link_count >= 40)
Jan Engelhardt
--
That limit should be a *recursion* limit only.
Symlinks in the last component of a path are looked up
iteratively (to save kernel stack space), but a symlink in
the middle of a path can't be done tail-recursively.
E.g. in your example
> namei cpu/args.t
f: cpu/args.t
d cpu
l args.t -> ../op/args.t
d ..
l op -> ../t/op/
d ..
l t -> perldir/t
l perldir -> perl-5.8.6
l perl-5.8.6 -> ../build/perl-5.8.6
d ..
l build -> BUILD
d BUILD
d perl-5.8.6
d t
d op
- args.t
Wow, what a symlink maze. The args.t -> ../op/args.t
symlink is no problems, but it's the mess of directory links
that the system has to traverse:
cpu/args.t
cpu/../op/args.t Tail-recursive expansion
cpu/../(../t/op)/args.t
cpu/../(../(perldir/t)/op)/args.t
cpu/../(../((perl-5.8.6)/t)/op)/args.t
cpu/../(../((../build/perl-5.8.6)/t)/op)/args.t
cpu/../(../((../(BUILD)/perl-5.8.6)/t)/op)/args.t
I'm supposing the initial level counts as 1, so 1+5 = 6 and blows the
limit.
There's also an iteration limit, to stop a -> b -> c -> a cycles,
but that's much higher. The recursion limit is a stack space issue.
On Fri, Feb 10, 2006 at 07:31:07PM -0800, Linda Walsh wrote:
> The maximum number of followed symlinks seems to be set to 5.
>
> This seems small when compared to other filesystem limits.
> Is there some objection to it being raised? Should it be
> something like Glib's '20' or '255'?
20 or 255 - not feasible (we'll get stack overflow from hell).
8 - probably can be switched already; anybody who hadn't converted their
fs ->follow_link() to new model will just lose; in-tree instances are
already OK with that and out-of-tree folks had at least half a year
of warning.
Unless anybody yells right now, I'm switching it to 8 in post-2.6.16.
On Sun, Feb 12, 2006 at 06:06:01PM +0000, Al Viro wrote:
> On Fri, Feb 10, 2006 at 07:31:07PM -0800, Linda Walsh wrote:
> > The maximum number of followed symlinks seems to be set to 5.
> >
> > This seems small when compared to other filesystem limits.
> > Is there some objection to it being raised? Should it be
> > something like Glib's '20' or '255'?
>
> 20 or 255 - not feasible (we'll get stack overflow from hell).
> 8 - probably can be switched already; anybody who hadn't converted their
> fs ->follow_link() to new model will just lose; in-tree instances are
> already OK with that and out-of-tree folks had at least half a year
> of warning.
>
> Unless anybody yells right now, I'm switching it to 8 in post-2.6.16.
FWIW, Fedora/RHEL4 has done this for a long time.
I don't think I've ever seen any problems arise, but then symlink
mazes are thankfully somewhat rare.
Dave
On Sun, Feb 12, 2006 at 06:06:01PM +0000, Al Viro wrote:
> On Fri, Feb 10, 2006 at 07:31:07PM -0800, Linda Walsh wrote:
> > The maximum number of followed symlinks seems to be set to 5.
> >
> > This seems small when compared to other filesystem limits.
> > Is there some objection to it being raised? Should it be
> > something like Glib's '20' or '255'?
Just a note (which Al probably considered too obvious to point out), but
MAX_NESTED_LINKS isn't the maximum number of followed symlinks. It's
the number of recursions we're limited to. The maximum number of
symlinks followed is 40 (see fs/namei.c:do_follow_link).
Al, would it be worth making 40 an enumerated constant in the same
enumeration as MAX_NESTED_LINKS? Something like this:
Index: include/linux/namei.h
===================================================================
RCS file: /var/cvs/linux-2.6/include/linux/namei.h,v
retrieving revision 1.4
diff -u -p -r1.4 namei.h
--- include/linux/namei.h 12 Nov 2005 04:09:17 -0000 1.4
+++ include/linux/namei.h 12 Feb 2006 19:35:31 -0000
@@ -11,7 +11,10 @@ struct open_intent {
struct file *file;
};
-enum { MAX_NESTED_LINKS = 5 };
+enum {
+ MAX_NESTED_LINKS = 5,
+ MAX_FOLLOW_SYMLINKS = 40,
+};
struct nameidata {
struct dentry *dentry;
Index: fs/namei.c
===================================================================
RCS file: /var/cvs/linux-2.6/fs/namei.c,v
retrieving revision 1.31
diff -u -p -r1.31 namei.c
--- fs/namei.c 12 Nov 2005 04:08:32 -0000 1.31
+++ fs/namei.c 12 Feb 2006 19:35:31 -0000
@@ -598,7 +598,7 @@ static inline int do_follow_link(struct
int err = -ELOOP;
if (current->link_count >= MAX_NESTED_LINKS)
goto loop;
- if (current->total_link_count >= 40)
+ if (current->total_link_count >= MAX_FOLLOW_SYMLINKS)
goto loop;
BUG_ON(nd->depth >= MAX_NESTED_LINKS);
cond_resched();
On Sun, Feb 12, 2006 at 12:36:37PM -0700, Matthew Wilcox wrote:
> On Sun, Feb 12, 2006 at 06:06:01PM +0000, Al Viro wrote:
> > On Fri, Feb 10, 2006 at 07:31:07PM -0800, Linda Walsh wrote:
> > > The maximum number of followed symlinks seems to be set to 5.
> > >
> > > This seems small when compared to other filesystem limits.
> > > Is there some objection to it being raised? Should it be
> > > something like Glib's '20' or '255'?
>
> Just a note (which Al probably considered too obvious to point out), but
> MAX_NESTED_LINKS isn't the maximum number of followed symlinks. It's
> the number of recursions we're limited to. The maximum number of
> symlinks followed is 40 (see fs/namei.c:do_follow_link).
>
> Al, would it be worth making 40 an enumerated constant in the same
> enumeration as MAX_NESTED_LINKS? Something like this:
Umm... Maybe. Note that this 40 is to kill very long iterations in
symlinks that are not too deeply nested, but resolving them would
traverse a lot (symlink can have a _lot_ of components - easily as much
as 2048, which leads to 2^55 lookups with depth limited to 5; since
process is unkillable during lookup and it's easy to do a setup where it
wouldn't block on IO...)
IOW, this limit doesn't come from stack overflow concerns - it's just an
arbitrary cutoff point to stop a DoS. We can easily lift it to e.g.
256 if there's any real need. Or make it sysctl-controlled; whatever...
The real hard limit is on nested symlinks.
Jan Engelhardt wrote:
> # grep 40 fs/namei.c
> namei.c: * limiting consecutive symlinks to 40.
> namei.c: if (current->total_link_count >= 40)
>
---
I believe that is the case of appending successive path entries for
sequential case of case "a->b->c->d..." where successive entries
can replace previous entries. I hit the nested symlink amount
where a symlink contains two or more path components with a symlink in the
non-terminal position, i.e.in the dir-component of a dir/target.
I had something like "./symdir1/myfile"; with a symlink chain extending
along the directory chain. Not the end file.
Here are the lines in question:
include/linux/namei.h:14:enum { MAX_NESTED_LINKS = 5 };
&&
fs/namei.c:
590: * This limits recursive symlink follows to 8, while
591: * limiting consecutive symlinks to 40.
592: *
593: * Without that kind of total limit, nasty chains of consecutive
594: * symlinks can cause almost arbitrarily long lookups.
595: */
596:static inline int do_follow_link(struct path *path, struct nameidata
*nd)
599: if (current->link_count >= MAX_NESTED_LINKS)
600: goto loop;
601: if (current->total_link_count >= 40)
602: goto loop;
----------
The comment on line 590 refers to the "enum", MAX_NESTED_LINKS
on line 599 defined as "5" in namei.h, line 14.
My original post showed the nesting via the gnu namei command, which
appears to correctly expand the symlink even though the OS fails.
I'd suggest changing the number in line 14 in namei.h to 40
as well, thus using the same limit in both cases and clearing up
such confusion.
The following patch (against 2.6.15.4) seems to make this change and fixes
up the comments:
-----------------------
--- include/linux/namei.h 2006-01-02 19:21:10.000000000 -0800
+++ include/linux/namei.h 2006-02-12 12:25:37.500504876 -0800
@@ -11,7 +11,7 @@
struct file *file;
};
-enum { MAX_NESTED_LINKS = 5 };
+enum { MAX_PATH_SYMLINKS = 40 };
struct nameidata {
struct dentry *dentry;
@@ -20,7 +20,7 @@
unsigned int flags;
int last_type;
unsigned depth;
- char *saved_names[MAX_NESTED_LINKS + 1];
+ char *saved_names[MAX_PATH_SYMLINKS + 1];
/* Intent data */
union {
--- fs/namei.c.orig 2006-01-02 19:21:10.000000000 -0800
+++ fs/namei.c 2006-02-12 12:20:45.382792407 -0800
@@ -587,8 +587,7 @@
}
/*
- * This limits recursive symlink follows to 8, while
- * limiting consecutive symlinks to 40.
+ * This limits max symlinks in a pathname to "MAX_PATH_SYMLINKS"
*
* Without that kind of total limit, nasty chains of consecutive
* symlinks can cause almost arbitrarily long lookups.
@@ -596,11 +595,11 @@
static inline int do_follow_link(struct path *path, struct nameidata *nd)
{
int err = -ELOOP;
- if (current->link_count >= MAX_NESTED_LINKS)
+ if (current->link_count >= MAX_PATH_SYMLINKS ||
+ current->total_link_count >= MAX_PATH_SYMLINKS)
goto loop;
- if (current->total_link_count >= 40)
- goto loop;
- BUG_ON(nd->depth >= MAX_NESTED_LINKS);
+ /* Not sure next BUG_ON statement is ever needed */
+ BUG_ON(nd->depth >= MAX_PATH_SYMLINKS);
cond_resched();
err = security_inode_follow_link(path->dentry, nd);
if (err)
On Sun, Feb 12, 2006 at 12:46:14PM -0800, Linda Walsh wrote:
> I'd suggest changing the number in line 14 in namei.h to 40
> as well, thus using the same limit in both cases and clearing up
> such confusion.
>
> The following patch (against 2.6.15.4) seems to make this change and fixes
> up the comments:
It also creates a trivially exploitable stack overflow.
Al Viro wrote:
>> Should it be something like Glib's '20' or '255'?
>>
> 20 or 255 - not feasible (we'll get stack overflow from hell).
>
How much stack is used/iteration? It appears we have a local pointer in
__do_follow_link, and 2 passed parameters/call + call-returns ->5
pointers/iteration. "Forty" entries would seem to take 200 pointers or
800 bytes of stack space? A limit of 20 would use 400 bytes?
If the algorithm was rewritten to be iterative with a stack, that would
seem to reduce memory usage by 40%, (2 "return" addresses out of 5
addresses). Depends on how tight stack space is. If push came to
"shove" couldn't the iterative stack be allocated out of the the general
purpose kernel-memory allocator and not live on the stack, alleviating
the stack pressure entirely?
It doesn't seem it causes an outrageous additional load on the stack as
is, though dynamically allocating the structures out of general memory
would seem to eliminate the problem (if there is one).
On Sun, Feb 12, 2006 at 01:18:51PM -0800, Linda Walsh wrote:
> Al Viro wrote:
> >>Should it be something like Glib's '20' or '255'?
> >>
> > 20 or 255 - not feasible (we'll get stack overflow from hell).
> >
> How much stack is used/iteration? It appears we have a local pointer in
> __do_follow_link, and 2 passed parameters/call + call-returns ->5
> pointers/iteration. "Forty" entries would seem to take 200 pointers or
> 800 bytes of stack space? A limit of 20 would use 400 bytes?
Care to RTFS? I mean, really - at least to the point of seeing what's
involved in that recursion.
Al Viro wrote:
> Care to RTFS? I mean, really - at least to the point of seeing what's
> involved in that recursion.
>
Hmmm...that's where I got the original parameter numbers, but
I see it's not so straightforward. I tried a limit of
40, but I quickly get an OS hang when trying to reference a
13th link. Twelve works at the limit, but would take more testing
to find out the bottleneck.
As an algorithmic detail, I can see how
file a->b->c->d... etc can easily use tail-recursion, but I'm not
quite as clear why "prefix-recursion" couldn't be used to reduce
the recursion complexity as in the case:
dir0/, link0->dir0, link1->link2 ... It seems it would be the
left hand compliment of tail recursion. Not sure what would be
involved, but would eliminate some stack considerations if it was
doable.
On Sun, Feb 12, 2006 at 02:54:33PM -0800, Linda Walsh wrote:
> Al Viro wrote:
> >Care to RTFS? I mean, really - at least to the point of seeing what's
> >involved in that recursion.
> >
> Hmmm...that's where I got the original parameter numbers, but
> I see it's not so straightforward. I tried a limit of
> 40, but I quickly get an OS hang when trying to reference a
> 13th link. Twelve works at the limit, but would take more testing
> to find out the bottleneck.
Sigh... 12 works at the limit on your particular config, filesystems
being used and syscall being issued (hint: amount of stuff on stack
before we enter mutual recursion varies; so does the amount of stuff
on stack we get from function that are not part of mutual recursion,
but are called from the damn thing).
Al Viro wrote:
> On Sun, Feb 12, 2006 at 02:54:33PM -0800, Linda Walsh wrote:
>
>> Al Viro wrote:
>>
>>> Care to RTFS? I mean, really - at least to the point of seeing what's
>>> involved in that recursion.
>>>
>>>
>> Hmmm...that's where I got the original parameter numbers, but
>> I see it's not so straightforward. I tried a limit of
>> 40, but I quickly get an OS hang when trying to reference a
>> 13th link. Twelve works at the limit, but would take more testing
>> to find out the bottleneck.
>>
>
> Sigh... 12 works at the limit on your particular config, filesystems
> being used and syscall being issued (hint: amount of stuff on stack
> before we enter mutual recursion varies; so does the amount of stuff
> on stack we get from function that are not part of mutual recursion,
> but are called from the damn thing).
>
---
Yeah, I sorta figured that. Is there any easier way to
remove the recursion? I dunno about you, but I was always taught
that recursion, while elegant, was not always the most efficient in
terms of time and space requirements and one could get similar
functionality using iteration and a stack.
The GNU libraries _seem_ to indicate a max of 20 links supported
there. Googling around, I see I'm not the first person to be surprised
by the low limit. I don't recall running into such a limit on any
other Unixes, though I'm sure they had some limit.
It can be useful for creating a shadow file-system where only
root needs to point to a "target source", and the "symlink" overlay
lies over the top of any real, underlying file.
Why can't things just be easy sometimes...:-/
Linda
On Sun, Feb 12, 2006 at 04:54:23PM -0800, Linda Walsh wrote:
> Al Viro wrote:
> >On Sun, Feb 12, 2006 at 02:54:33PM -0800, Linda Walsh wrote:
> >
> >>Al Viro wrote:
> >>
> >>>Care to RTFS? I mean, really - at least to the point of seeing what's
> >>>involved in that recursion.
> >>>
> >>>
> >>Hmmm...that's where I got the original parameter numbers, but
> >>I see it's not so straightforward. I tried a limit of
> >>40, but I quickly get an OS hang when trying to reference a
> >>13th link. Twelve works at the limit, but would take more testing
> >>to find out the bottleneck.
> >>
> >
> >Sigh... 12 works at the limit on your particular config, filesystems
> >being used and syscall being issued (hint: amount of stuff on stack
> >before we enter mutual recursion varies; so does the amount of stuff
> >on stack we get from function that are not part of mutual recursion,
> >but are called from the damn thing).
> >
> ---
> Yeah, I sorta figured that. Is there any easier way to
> remove the recursion? I dunno about you, but I was always taught
> that recursion, while elegant, was not always the most efficient in
> terms of time and space requirements and one could get similar
> functionality using iteration and a stack.
I don't know exactly why recursion is used to follow symlinks,
which at first thought seems like it could be iterated, but
I've not checked the code, there certainly are specific reasons
for this. However, there's often an alternative to recursion, it
consists in implementing a local stack onto the stack. I mean,
when you need recursion, it is because you want to be able to
get back to where you were previously (eg: try another branch
in a tree). Recursing through functions has a high cost in
terms of memory because many things get saved multiple times,
while you will often only need a few pointers and a recursion
level.
I have already implemented this in a few programs and it's very
easy, although I don't know how it would be with the symlink code :
foobar() {
void *stack[MAXDEPTH];
void *ptr;
int level;
level = 0;
...
recurse:
if (level >= MAXDEPTH)
return -ELOOP;
/* this level's work before the recursive call */
...
ptr = some_useful_pointer();
printf("before: ptr=%p, level=%d\n", ptr, level);
...
if (need_to_recurse) {
stack[level++] = ptr;
goto recurse;
}
after_return:
/* this level's work after the return */
...
printf("after: ptr=%p, level=%d\n", ptr, level);
...
/* return to outer level */
if (level > 0) {
ptr = stack[--level];
goto after_return;
}
...
/* end of the work for level 0 */
}
Saving paths components this way is easy too, with the full name copied
only once in memory, and with one byte per recursion level :
char path[MAXPATHLEN]; /* <= 255 */
__uint8_t pathlen[MAXDEPTH];
char *path_end;
path_end = path;
...
snprintf(path_end, path+MAXPATHLEN-path_end, "foobar/");
...
if (need_to_recurse) {
pathlen[level++] = path_end - path;
goto recurse;
}
...
/* return to outer level */
if (level > 0) {
path_end = path + pathlen[--level];
*path_end = '\0';
goto after_return;
}
> The GNU libraries _seem_ to indicate a max of 20 links supported
> there. Googling around, I see I'm not the first person to be surprised
> by the low limit. I don't recall running into such a limit on any
> other Unixes, though I'm sure they had some limit.
>
> It can be useful for creating a shadow file-system where only
> root needs to point to a "target source", and the "symlink" overlay
> lies over the top of any real, underlying file.
I've already encountered such setups in which I was worried that they
might break under some 2.6 kernels.
> Why can't things just be easy sometimes...:-/
Probably because having both performance and maintainability often
implies a tradeoff between easy and ugly, and the maintainer's job
is to find the best tradeoff.
> Linda
Regards,
Willy
> I don't know exactly why recursion is used to follow symlinks,
> which at first thought seems like it could be iterated, but
> I've not checked the code, there certainly are specific reasons
> for this.
the problem is not following symlinks. the problem is symlinks to
symlink to symlink to ...
Hi Arjan,
On Mon, Feb 13, 2006 at 08:48:15AM +0100, Arjan van de Ven wrote:
>
> > I don't know exactly why recursion is used to follow symlinks,
> > which at first thought seems like it could be iterated, but
> > I've not checked the code, there certainly are specific reasons
> > for this.
>
> the problem is not following symlinks. the problem is symlinks to
> symlink to symlink to ...
That's how I understood it, but I only thought about easy cases. Now,
I can imagine cross-FS links and I don't see an easy way to resolve
them :-/
Cheers,
Willy
On Mon, Feb 13, 2006 at 09:03:31AM +0100, Willy Tarreau wrote:
> Hi Arjan,
>
> On Mon, Feb 13, 2006 at 08:48:15AM +0100, Arjan van de Ven wrote:
> >
> > > I don't know exactly why recursion is used to follow symlinks,
> > > which at first thought seems like it could be iterated, but
> > > I've not checked the code, there certainly are specific reasons
> > > for this.
> >
> > the problem is not following symlinks. the problem is symlinks to
> > symlink to symlink to ...
>
> That's how I understood it, but I only thought about easy cases. Now,
> I can imagine cross-FS links and I don't see an easy way to resolve
> them :-/
The real problem is that there is no promise that resolution of a symlink
consists of following some path. It's a very common case, all right,
but not the only one. And trying to take that into account makes iterative
schemes very ugly.
Willy Tarreau wrote:
>On Sun, Feb 12, 2006 at 04:54:23PM -0800, Linda Walsh wrote:
>
>
>>Al Viro wrote:
>>
>>
>>>On Sun, Feb 12, 2006 at 02:54:33PM -0800, Linda Walsh wrote:
>>>
>>>
>>>
>>>>Al Viro wrote:
>>>>
>>>>
>>>>
>>>>>Care to RTFS? I mean, really - at least to the point of seeing what's
>>>>>involved in that recursion.
>>>>>
>>>>>
>>>>>
>>>>>
>>>>Hmmm...that's where I got the original parameter numbers, but
>>>>I see it's not so straightforward. I tried a limit of
>>>>40, but I quickly get an OS hang when trying to reference a
>>>>13th link. Twelve works at the limit, but would take more testing
>>>>to find out the bottleneck.
>>>>
>>>>
>>>>
>>>Sigh... 12 works at the limit on your particular config, filesystems
>>>being used and syscall being issued (hint: amount of stuff on stack
>>>before we enter mutual recursion varies; so does the amount of stuff
>>>on stack we get from function that are not part of mutual recursion,
>>>but are called from the damn thing).
>>>
>>>
>>>
>>---
>> Yeah, I sorta figured that. Is there any easier way to
>>remove the recursion? I dunno about you, but I was always taught
>>that recursion, while elegant, was not always the most efficient in
>>terms of time and space requirements and one could get similar
>>functionality using iteration and a stack.
>>
>>
>
>I don't know exactly why recursion is used to follow symlinks,
>which at first thought seems like it could be iterated, but
>I've not checked the code, there certainly are specific reasons
>for this. However, there's often an alternative to recursion, it
>consists in implementing a local stack onto the stack. I mean,
>
>
Sometimes, there are better ways than implementing your
own stack. For example, not having any kind of stack.
That means memory usage don't increase with the number of
chained symlinks.
>when you need recursion, it is because you want to be able to
>get back to where you were previously (eg: try another branch
>in a tree).
>
Yes, but what if we don't need the ability to go back?
Consider this approach to symlinks:
1. We have a path component to resolve
2. It turns out to be a symlink. So look it up, then
loop back to (1)
This goes on until what we find isn't a symlink, or till some
overflow counter decides that we probably have a symlink loop.
With no memory of where we came from, there is no
recursive use of memory. And no way of going back in
single steps, but I assume that isn't necessary here.
I could be wrong about that though.
Helge Hafting
On Mon, Feb 13, 2006 at 09:03:31AM +0100, Willy Tarreau wrote:
> That's how I understood it, but I only thought about easy cases. Now,
> I can imagine cross-FS links and I don't see an easy way to resolve
> them :-/
And don't forget automount points too...
OG.