What is a trampoline function?

Question

During recent discussions at work, someone referred to a trampoline function.

I have read the description at Wikipedia. It is enough to give a general idea of the functionality, but I would like something a bit more concrete.

Do you have a simple snippet of code that would illustrate a trampoline?

Answer 1

Here's a good example, used in modern-day Linux.

Answer 2

I'll give you an example that I used in an anti-cheat patch for an online game.

I needed to be able to scan all files that were being loaded by the game for modification. So the most robust way I found to do this was to use a trampoline for CreateFileA. So when the game was launched I would find the address for CreateFileA using GetProcAddress, then I would modify the first few bytes of the function and insert assembly code that would jump to my own "trampoline" function, where I would do some things, and then I would jump back to the next location in CreateFile after my jmp code. To be able to do it reliably is a little trickier than that, but the basic concept is just to hook one function, force it to redirect to another function, and then jump back to the original function.

Edit: Microsoft has a framework for this type of thing that you can look at. Called Detours

Answer 3

In the Microsoft world, trampolines are usually called 'thunks'.

Here's a page from Andrei Alexandrescu's "Modern C++ Design"

---

Answer 4

Here's an example of nested functions:

#include <stdlib.h>
#include <string.h>
/* sort an array, starting at address `base`,
 * containing `nmemb` members, separated by `size`,
 * comparing on the first `nbytes` only. */
void sort_bytes(void *base,  size_t nmemb, size_t size, size_t nbytes) {
    int compar(const void *a, const void *b) {
        return memcmp(a, b, nbytes);
    }
    qsort(base, nmemb, size, compar);
}

compar can't be an external function, because it uses nbytes, which only exists during the sort_bytes call. On some architectures, a small stub function -- the trampoline -- is generated at runtime, and contains the stack location of the current invocation of sort_bytes. When called, it jumps to the compar code, passing that address.

This mess isn't required on architectures like PowerPC, where the ABI specifies that a function pointer is actually a "fat pointer", a structure containing both a pointer to the executable code and another pointer to data. However, on x86, a function pointer is just a pointer.

Answer 5

There is also the LISP sense of 'trampoline' as described on Wikipedia:

Used in some LISP implementations, a trampoline is a loop that iteratively invokes thunk-returning functions. A single trampoline is sufficient to express all control transfers of a program; a program so expressed is trampolined or in "trampolined style"; converting a program to trampolined style is trampolining. Trampolined functions can be used to implement tail recursive function calls in stack-oriented languages

Let us say we are using Javascript and want to write the naive Fibonacci function in continuation-passing-style. The reason we would do this is not relevant - to port Scheme to JS for instance, or to play with CPS which we have to use anyway to call server-side functions.

So, the first attempt is

function fibcps(n, c) {
    if (n <= 1) {
        c(n);
    } else {
        fibcps(n-1, function(x) {
            fibcps(n-2, function(y) {
                c(x+y)})});
    }
}

But, running this with n = 25 in Firefox gives an error 'Too much recursion!'. Now this is exactly the problem (missing tail-call optimization in Javascript) that trampolining solves. Instead of making a (recursive) call to a function, let us return an instruction (thunk) to call that function, to be interpreted in a loop.

function fibt(n, c) {
    function trampoline(x) {
        while (x && x.func) {
            x = x.func.apply(null, x.args);
        }
    }
    function fibtramp(n, c) {
        if (n <= 1) {
            return {func: c, args: [n]};
        } else {
            return {func: fibtramp, 
                    args: [n - 1,
                           function (x) {
                               return {func: fibtramp, 
                                       args: [n - 2,
                                              function (y) {
                                                  return {func: c,
                                                          args: [x + y]}}
       ]}}]}}}
    trampoline({ func : fibtramp, args: [n, c] });
}

Answer 6

For C, a trampoline would be a function pointer:

size_t (*trampoline_example)(const char *, const char *);
trampoline_example= strcspn;
size_t result_1= trampoline_example("xyzbxz", "abc");

trampoline_example= strspn;
size_t result_2= trampoline_example("xyzbxz", "abc");

Edit: More esoteric trampolines would be implicitly generated by the compiler. One such use would be a jump table. (Although there are clearly more complicated ones the farther down you start attempting to generate complicated code.)

Answer 7

I couldn't help but laugh at the irony of this question being asked on Stack Overflow :P

Answer 8

I am currently experimenting with ways to implement tail call optimization for a Scheme interpreter, and so at the moment I am trying to figure out whether the trampoline would be feasible for me.

As I understand it, it is basically just a series of function calls performed by a trampoline function. Each function is called a thunk and returns the next step in the computation until the program terminates (empty continuation).

Here is the first piece of code that I wrote to improve my understanding of the trampoline:

#include <stdio.h>

typedef void *(*CONTINUATION)(int);

void trampoline(CONTINUATION cont)
{
  int counter = 0;
  CONTINUATION currentCont = cont;
  while (currentCont != NULL) {
    currentCont = (CONTINUATION) currentCont(counter);
    counter++;
  }
  printf("got off the trampoline - happy happy joy joy !\n");
}

void *thunk3(int param)
{
  printf("*boing* last thunk\n");
  return NULL;
}

void *thunk2(int param)
{
  printf("*boing* thunk 2\n");
  return thunk3;
}

void *thunk1(int param)
{
  printf("*boing* thunk 1\n");
  return thunk2;
}

int main(int argc, char **argv)
{
  trampoline(thunk1);
}

results in:

meincompi $ ./trampoline 
*boing* thunk 1
*boing* thunk 2
*boing* last thunk
got off the trampoline - happy happy joy joy !