using a trampoline with one function as an argument

Question

I know what a trampoline function is, but I've been having trouble avoiding stack overflow using trampolines. So far, the only method I can think of is to use global variables, which are discouraged and can complicate programs.

The trampoline function I want to use is shown below.

void trampoline(void *(*fun)()) {
  while (fun != NULL) {
    void *callback = fun();
    fun = (void *(*)())callback;
  }
}

When I try to pass in functions with parameters, such as those in the code fragment below, I end up creating stacks, which is not what I want. I was wondering if there was a way to use my trampoline function without using global variables or passing in any extra arguments?

void *f1();
void *f2();

void *f1(int *n) {
  if (*n == 0) {
    return NULL;
  } else {
    return f2(n);
  }
}

void *f2(int *n) {
  --*n;
  return f1(n);
}

int main() {
  int a = 1000000;
  trampoline(f1(&a));
  return 0;
}

The program below behaves how I want it to, but it uses a global variable, which is widely discouraged.

#include <stdio.h>
int a = 1000;

void trampoline(void *(*f)()) {
  while (f) {
    void *g = f();
    f = (void *(*)())g;
  }
}

void *f1();
void *f2();

void *f1() {
  if (a == 0) {
    return NULL;
  } else {
    return f2;
  }
}

void *f2() {
  --a;
  return f1;
}

int main() {

  trampoline(f1);
  return 0;
}

Clarification: I do not want to modify the trampoline function above, but I want reduced stack creation.

Strictly speaking, C doesn't guarantee that a `void *` can hold a function pointer, only a data pointer. — Tom Karzes, Apr 15 '20 at 15:48
but @TomKarzes the parameter syntax specifies that a trampoline must take in a void function pointer, right? — gt453, Apr 15 '20 at 15:55
@gt453 A void function pointer is not the same as a void pointer. In practice, you're almost certainly safe, but strictly speaking function pointers can have different sizes from data pointers. See [this link](https://stackoverflow.com/questions/31482624/is-there-such-a-thing-as-a-generic-function-pointer-in-c-that-can-be-assigned-ca) for more details. — Tom Karzes, Apr 15 '20 at 15:59

bruno · Accepted Answer · 2020-04-15T17:14:45.210

0

First probably you mean

void *f1(int *n) {
  if (*n == 0) {  /* <<< */
    return NULL;
  } else {
    return f2(n);
  }
}

rather than

void *f1(int *n) {
  if (n == 0) {
    return NULL;
  } else {
    return f2(n);
  }
}

Compiling with optimization the compiler will detect the final recursion in both function and the used size of the stack will be constant and not linked with a.

In fact like that for the compiler you main just does return 0; ;-)

To hope the calls you can do

int main(int argc, char ** argv) {
  int a = argc * 1000000;
  trampoline(f1(&a));
  return a;
}

With your second definition after your edit the compiler cannot optimize replacing all by the right return

On my PI4 gcc 8.3.0 with the option -O detects the final recursions and the program just uses time to finish, but without a stack overflow

Note gcc as a special management for the trampoline case, with the dedicated option "-Wtrampoline"

edited Apr 15 '20 at 17:14

answered Apr 15 '20 at 15:27

bruno

32,421
7
25
37

@gt453 I think this is a false problem because all compilers detect final recursions since long time, are you using a diplodocus compiling for 8080 ? – bruno Apr 15 '20 at 15:35
@gt453 I run on a PI4 (raspbian) and your new version just taken time to finish well – bruno Apr 15 '20 at 15:48
Yes, but can you find a version that works like my new version but doesn't use global variables? Global variables can create hidden dependencies b/w different parts of a program, but they are still manageable as long as I make the right function calls. Is there any way to avoid stack frame creation using the given trampoline function that doesn't involve using global variables? – gt453 Apr 15 '20 at 15:53
@gt453 please stop to delete your question, each time I loose the edition of my answer and I have to redo all, this is very stressing – bruno Apr 15 '20 at 15:55
okay, but I still don't know how to resolve my actual question. – gt453 Apr 15 '20 at 15:59
@gt453 while the compiler can manage a terminal call it does, your global variable just limit the optimization the compiler was able to do, and to not remoave allall – bruno Apr 15 '20 at 15:59
so @bruno how can I maximize optimization and avoid the creation of stack frames and use the given trampoline function? When I run your solution, my program still creates stack frames. – gt453 Apr 15 '20 at 16:05
@gt453 that depends on the compiler, _gcc_ has a special management about the trampoline and even the dedicated option "-Wtrampoline". What is your compiler ? – bruno Apr 15 '20 at 16:08
@gt453 with at least -O ? – bruno Apr 15 '20 at 16:30
@gt453 to produce *prog_name* rather than *a.out* use "-o prog_name" (lower case 'o'), to optimize use "-O" (upper case 'O'), so to have both "gcc -o prog_name -O prog_name.c" – bruno Apr 15 '20 at 16:33
@gt453 ask the people implementing _gcc_ ;-) More seriously, all is about the generated code, while the norm of C does not impose to always manage the terminal recursion whatever the optimize level you cannot 'blame' _gcc_ to request at least "-O" to do. Frankly the optimizations done by (at least) _gcc_ are awesome, I can only congratulate them – bruno Apr 15 '20 at 16:58
@gt453 finally is my answer useful for you ? – bruno Apr 15 '20 at 17:13

using a trampoline with one function as an argument

1 Answers1