Re: max symlink = 5? ?bug? ?feature deficit?

Re: max symlink = 5? ?bug? ?feature deficit?

[Al Viro]

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.

Re: max symlink = 5? ?bug? ?feature deficit?

[Dave Jones]

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

Re: max symlink = 5? ?bug? ?feature deficit?

[Matthew Wilcox]

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();

Re: max symlink = 5? ?bug? ?feature deficit?

[Al Viro]

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.

Re: max symlink = 5? ?bug? ?feature deficit?

[Linda Walsh]

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).

Re: max symlink = 5? ?bug? ?feature deficit?

[Al Viro]

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.

Re: max symlink = 5? ?bug? ?feature deficit?

[Linda Walsh]

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.

Re: max symlink = 5? ?bug? ?feature deficit?

[Al Viro]

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).

Re: max symlink = 5? ?bug? ?feature deficit?

[Linda Walsh]

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

Re: max symlink = 5? ?bug? ?feature deficit?

[Willy Tarreau]

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

Re: max symlink = 5? ?bug? ?feature deficit?

[Arjan van de Ven]

> 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 ...

Re: max symlink = 5? ?bug? ?feature deficit?

[Willy Tarreau]

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

Re: max symlink = 5? ?bug? ?feature deficit?

[Al Viro]

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.

Re: max symlink = 5? ?bug? ?feature deficit?

[Olivier Galibert]

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.

Re: max symlink = 5? ?bug? ?feature deficit?

[Helge Hafting]

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