> > Uncached_readdir is not really a problem. The real problem is
> > filesystems that generate "infinite directories" by producing looping
> > combinations of cookies.
> >
> > IOW: I've seen servers that generate cookies in a sequence of a form
> > vaguely resembling
> >
> > 1 2 3 4 5 6 7 8 9 10 11 12 3...
> >
> > (with possibly a thousand or so entries between the first and second
> > copy of '3')
> >
> > The kernel won't loop forever with something like that (because
> > eventually filldir() will declare it is out of buffer space), but
> > userland has a halting problem: it needs to detect that every
> > sys_getdents() call it is making is generating another copy of the
> > sequence associated with '4 5 6 7 8 9 10 11 12 3'...
>
> Huh? This is not only an easy problem, it's a well-known problem.
>
http://en.wikipedia.org/wiki/Cycle_detection
>
> Here's Brent's algorithm:
>
> n = 0;
> saved_cookie = <invalid>
> For each cookie {
> if (n && cookie == saved_cookie)
> die("Loop detected!");
> if (++n is a power of 2)
> saved_cookie = cookie;
> }
>
> You can tweak the performance with other exponentially-growing
> functions, saving k > 1 old cookies for comparison, etc., but the
> above will work very well.
