Stack limit and recursive functions

Question

A C program uses recursion to find a property of a graph. Large graphs can't be processed because the stack space is too small. The program has to be recoded to use an explicit stack and a loop.

Should recursive functions check the input will "fit" in stack space first?

Is there an example in the linux kernel where a recursive function had to be replaced with 'explicit' recursion?

Answer 1

Should recursive functions check the input will "fit" in stack space first?

This is generally very difficult. The amount of stack memory required for each recursive call might be different when compiling the code using different compilers or different versions of the same compiler or using different compiler switches to compile the code. In fact, the function may require different amounts of stack memory in different calls depending on its control flow.

So if you think that there is a serious risk of overflowing the stack, you should convert recursion to iteration (potentially using an explicit stack) and/or limit the number of recursions/iterations.

Is there an example in the linux kernel where a recursive function had to be replaced with 'explicit' recursion?

Yes. A nice example of this would be the code that implements the resolution of symbolic links. Prior to Linux 4.2, the code was recursive as follows:

link_path_walk -> nested_symlink -> follow_link -> link_path_walk

link_path_walk is the main name resolution function. If it detects a symbolic link, it calls nested_symlink, which may in turn call link_path_walk recursively. To mitigate stack overflow in the kernel, nested_symlink performs the following check:

if (unlikely(current->link_count >= MAX_NESTED_LINKS)) {
    path_put_conditional(path, nd);
    path_put(&nd->path);
    return -ELOOP;
}

Each task descriptor has a link_count field, which is increased each time nested_symlink is called. If it exceeds a fixed threshold (MAX_NESTED_LINKS is 8 in Linux 4.1.51), the whole operation terminates with an error.

Starting with Linux 4.2, the recursive code was changed into an iterative code with an explicit stack and the threshold was relaxed to 40. This article discusses the iterative code in detail.