It made me wonder if we can convert/optimize mutual recursion in a way transparent to users. As basic example I chose following code:
int even(int n) { if (n == 0) return 1; else return odd(abs(n) - 1); } int odd(int n) { if (n == 0) return 0; else return even(abs(n) - 1); }
Like in previous example I decided to use context manipulations plus function wrappers for even() and odd().
Unfortunately there is no way to wrap functions (symbols) referenced in same file as the symbol (check this). It gives some limitations: in our case even() and odd() should be separated into different source files. In common case our approach will not work with normal recursion (a()->a()) without source modification (not just recompiling with wrapper library as I wanted). Note, that if even() and odd() are in the shared library (most likely), then you can use LD_PRELOAD to wrap these functions and it will work just fine.
even.c:
int odd(int); int even(int n) { if (n == 0) return 1; else return odd(abs(n) - 1); }
odd.c:
int even(int); int odd(int n) { if (n == 0) return 0; else return even(abs(n) - 1); }
wrapped.c:
int __real_even(int n); int __real_odd(int n); volatile int even_odd_arg; int (*volatile fp)(int); volatile int even_odd_res; void dispatch(ucontext_t *_return_context) { static ucontext_t *return_context = 0; if (return_context == NULL) { return_context = _return_context; } even_odd_res = fp(even_odd_arg); setcontext(return_context); } ucontext_t* get_dispatcher_context(ucontext_t* return_context) { static ucontext_t dispatcher_context; static char iterator_stack[SIGSTKSZ]; static initialized = 0; if (initialized) return &dispatcher_context; dispatcher_context.uc_stack.ss_sp = iterator_stack; dispatcher_context.uc_stack.ss_size = sizeof(iterator_stack); getcontext(&dispatcher_context); makecontext(&dispatcher_context, (void (*)(void)) dispatch, 1, return_context); return &dispatcher_context; } int __wrap_even(int n) { ucontext_t this_context; even_odd_arg = n; fp = __real_even; swapcontext(&this_context, get_dispatcher_context(&this_context)); return even_odd_res; } int __wrap_odd(int n) { ucontext_t this_context; even_odd_arg = n; fp = __real_odd; swapcontext(&this_context, get_dispatcher_context(&this_context)); return even_odd_res; }
main.c:
int even(int); int main() { int i; for (i = 0; i <= 10; i++) { int is_even = even(i); if (is_even) printf("%d is even\n", i); else printf("%d is odd\n", i); } return 0; }
To compile use "gcc -c -O0 *.c; gcc *.o -Wl,-wrap,even -Wl,-wrap,odd -o test_mut_rec".
3 comments:
why does it need volatile?
Alex
When we switch contexts registers are reloaded, thus we need a guarantee that variable is stored in the memory (not in register).
Recently I had a bug with this: ACK (compiler) generated wrong code for volatile.
You may use memory barriers instead. volatile is usually a bad idea.
Post a Comment