The case for lack of recursive functions in kernel

[iansjack]

Just make if(symlink.pointsTo->pointsTo!=symlink)return; and be happy.

I wouldn't be that happy. It's a gross oversimplification to suppose that a circular reference can only happen directly.

[Roman]

Just make if(symlink.pointsTo->pointsTo!=symlink)return; and be happy.

What if symbolic link #1 points to symbolic link #2, which then points to symbolic link #3, which returns to the first symbolic link?

[Combuster]

To guarantee stack safety you'd want to write out the tail recursion optimisation by hand and don't rely on the compiler to fix the recursive function call for you:

Code: Select all

while (file->is_symlink()) file = resolve_symlink(file);

Note that while() loops, as opposed to your common for(i=...;i<...;i++), loops provokes pretty much the same demand for code scrutiny as recursive calls do.


The second part of the problem is less trivial. To detect circular dependencies exactly you'd need to cache all resolutions thus far:

Code: Select all

hash_set->add(file);
file = resolve_symlink(file);
if (hash_set->contains(file)) generate_error();

Of course caching all symlinks might be a optimisation issue for the common 1-2 symlink case and a potentional memory issue for (an attacker's) really long symlink chains, so taking a heuristic approach to the issue to prevent abuse might be an overall better idea.

Code: Select all

iterations++;
if (iterations > 8) generate_error();
file = resolve_symlink(file);

$.02

[alexfru]

The second part of the problem is less trivial. To detect circular dependencies exactly you'd need to cache all resolutions thus far:

Loop detection in a linked list a classical problem, which is often asked on interviews.
See Floyd's "tortoise and hare" cycle detection algorithm.

[Combuster]

Mind that symlink resolution means (slow) disk I/O, and tortoise-hare solutions make up to thrice as many accesses to disk as strictly needed.