Page 2 of 2
Re: The case for lack of recursive functions in kernel
Posted: Fri Oct 09, 2015 9:10 am
by iansjack
catnikita255 wrote: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.
Re: The case for lack of recursive functions in kernel
Posted: Fri Oct 09, 2015 2:03 pm
by 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?
Re: The case for lack of recursive functions in kernel
Posted: Mon Oct 12, 2015 3:59 am
by 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
Re: The case for lack of recursive functions in kernel
Posted: Mon Oct 12, 2015 4:11 am
by alexfru
Combuster wrote:
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.
Re: The case for lack of recursive functions in kernel
Posted: Mon Oct 12, 2015 5:56 am
by 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.