Re: Request for more info on trampolines

holmer@rose.eecs.nwu.edu (Bruce Holmer) writes:
>I'm wondering if there is a good article on trampoline code which
>describes when it is needed and what exactly needs to be done.


>The GNU document "Using and Porting GNU CC" has a couple of pages,
>but I'm looking for more detail.


Here's an implementation, for Sparc, running Solaris 2.*, using a compiler
capable of reading .il files. This implementation uses separate paired
code and data pages to reduce the need to flush the cache. That is, there
is a trampoline allocator and a trampoline deallocator. You could use
this code to (for instance) implement nested scope in a Pascal or Modula
to C translator. The fact that the trampolines are not allocated on the
stack means that you could do more than that, if you were ambitious.


The code below contains horrible non-portable casts, but it also contains
hex constants encoding Sparc machine instructions, so I can't make too
many claims to portability anyway.


IMPORTANT NOTICE:


    SUN MICROSYSTEMS HAS NOTHING TO DO WITH THIS CODE, AND IT PROBABLY
    DOESN'T WORK ANYWAY. THIS IS FOR DEMONSTRATION/EDUCATIONAL
    PURPOSES ONLY.


================================================================
#define TEST_TRAMP


/*
  * Prototype code demonstrating the use of trampolines
  * on Sparc under SVR4. It is not seriously tested, and
  * contains random exits that make it unsafe for general
  * use.
  *
  * Types used:
  *
  * PFoIrI -- Pointer to function of int returning int.
  *
  * Procedures exported:
  *
  * PFoIrI tramp_alloc(PFoIrI f, int data1, int data2, char * name)
  *
  * This returns a "trampoline", with C type "pointer to function
  * of int returning int". When the trampoline is called with one
  * parameter "x", the trampoline will load data1 and data2 into
  * global registers %g2 and %g3 respectively, then calls "f",
  * passing it the parameter "x". If 0 is passed in for "name",
  * "anonymous" is used as the trampoline's name.
  *
  * In practice, (let's not have any pretensions to portability
  * here) as many parameters as are desired may be passed to the
  * trampoline, and they will ALL be passed to "f". However,
  * this might be an unportable practice, in that it may be difficult
  * to implement on other architectures (the use of the side door
  * for passing the hidden arguments, instead of adding them to the
  * parameter list, should make this less of a problem).
  *
  * PFoIrI tramp_alloc1(PFoIrI f, int i1, char * name)
  * equivalent to tramp_alloc(f,i1,0,name)
  *
  * void tramp_free(PFoIrI f)
  *
  * This frees the trampoline for later use. Things recognized to
  * be non-trampolines (in practice, almost any non-trampoline)
  * are quietly ignored.
  *
  * int tramp_valid(PFoIrI f)
  *
  * Returns 1 if and only if f is an allocated trampoline.
  *
  * int tramp_data(PFoIrI f, PFoIriI *pfunc, int * pdata1,
  * int * pdata2, char ** pname)
  *
  * Retrieves information from an allocated trampoline.
  * Returns 1 if this was successful, or 0 if the first parameter
  * was not an allocated trampoline. Values are returned through
  * those pointers that are not zero.
  *
  * void tramp_dump(FILE * f)
  *
  * Dump out information about all allocated trampolines.
  *
  * For writing trampolines, compile with the inline file "get_g2.il"
  * and call "get_g2()" and "get_g3()" to read the hidden parameters.
  * This is the entire contents of the expected inline file:
  *
  *****************************
.inline get_g2,0
mov %g2,%o0
.end


.inline get_g3,0
mov %g3,%o0
.end


.inline flush,1
iflush %o0
.end
  *****************************
  *
  * For testing and illustration, compile this code with -DTEST_TRAMP.
  *
  */


typedef int (*PFoIrI)(int);


#include <sys/types.h>
#include <sys/mman.h>
#include <fcntl.h>
#include <stdio.h>


#define BLOBSIZE 8192


/*
    sethi %hi(loc),%g1
    add %g1,%lo(loc),%g1
    ldd [%g1],%g2
    ld [%g1+8],%g1
    jmp %g1
    nop
    nop
    nop
*/


#define SETHILOC(loc) (0x03000000 + ((unsigned int)(loc)>>10))
#define ADDLOLOC(loc) (0x82006000 + ((unsigned int)(loc)&0x3FF))
#define NOP 0x01000123 /* Tagged NOP. */
#define LD1 0xc4184000
#define LD2 0xc2006008
#define JMP 0x81c04000


struct code_blob {
    unsigned int sethi,add,ld1,ld2,jmp,nop;
    struct data_blob * data_ptr;
    int pad[1];
};


struct data_blob {
    unsigned int data1;
    unsigned int data2;
    unsigned int function;
    struct data_blob * next_free;
    char * name;
    struct code_blob * code_ptr;
    struct data_blob * next;
    struct data_blob * prev;
};


/* Helper routine to get a page. */
static void * a_page() {
static int zfd = 0;
            int memory_at;


            if (zfd == 0)
{
zfd = open("/dev/zero", O_RDONLY, 0);
}


            memory_at = (int) mmap(0, BLOBSIZE,
PROT_READ|PROT_WRITE|PROT_EXEC,
MAP_PRIVATE, zfd, 0);


            if (memory_at == -1)
exit(-1);


              return (void *) memory_at;
}


struct data_blob * init_a_bunch() {
    struct code_blob * cp = (struct code_blob *) a_page();
    struct data_blob * dp = (struct data_blob *) a_page();
    int i;
    int cl = BLOBSIZE/sizeof(struct code_blob);
    /* Note -- dl must be a multiple of 8, because ldd is applied
          to it. */
    int dl = BLOBSIZE/((sizeof(struct data_blob)+7)&~7);
    int rc;


    if (cl > dl) cl = dl;


    for (i = 0; i < cl; i++) {
cp[i].sethi = SETHILOC(dp+i);
cp[i].add = ADDLOLOC(dp+i);
                cp[i].ld1 = LD1;
                cp[i].ld2 = LD2;
                cp[i].jmp = JMP;
                cp[i].nop = NOP;
cp[i].data_ptr = dp+i;
        }


    for (i = 0; i < cl; i++) {
            flush(cp+i);
        }


    for (i = 0; i < cl; i++) {
dp[i].code_ptr = cp+i;
dp[i].next = dp+i+1;
dp[i].next_free = dp+i+1;
dp[i].prev = dp+i-1;
dp[i].name = 0;
        }


    dp[0].prev = dp+i-1;
    dp[i-1].next = dp+0;
    dp[i-1].next_free = 0;


    /* Change the page protection on the code to forbid writes.
          The code has to be readable, because it is necessary
          to read pointers written there to verify that a trampoline
          is a trampoline, and to get to the data pointer when it
          is freed. */


    rc = mprotect((char *) cp, BLOBSIZE, PROT_EXEC|PROT_READ);
    if (rc) {
        perror("Mprotect failed: ");
    }
    return dp;
}


int tramp_valid(PFoIrI f) {
      struct code_blob * cb = (struct code_blob *) f;


      /* Verify thoroughly that this is our data.
            Postpone indirection through potentially bogus
            addresses as long as possible. */
      return (
cb -> ld1 == LD1 &&
cb -> ld2 == LD2 &&
cb -> jmp == JMP &&
cb -> nop == NOP &&
cb -> sethi == SETHILOC(cb -> data_ptr) &&
cb -> add == ADDLOLOC(cb -> data_ptr) &&
cb -> data_ptr -> code_ptr == cb &&
cb -> data_ptr -> name != 0);
}


static struct data_blob * tramp_list = 0;
static struct data_blob * tramp_free_list = 0;


PFoIrI tramp_alloc(PFoIrI f, int i1, int i2, char * name) {
      struct data_blob * this;


      /* Name is used as the is-allocated flag, so it cannot
            be zero. */
      if (name == 0) name = "anonymous";


      if (tramp_list == 0) {
          /* The first time, the default circular list is what is needed. */


          tramp_free_list = init_a_bunch();
          tramp_list = tramp_free_list;
      }


      if (tramp_free_list == 0) {
tramp_free_list = init_a_bunch();


/* update the circular list. */


tramp_free_list -> prev -> next = tramp_list;
tramp_list -> prev -> next = tramp_free_list;
this = tramp_list -> prev;
tramp_list -> prev = tramp_free_list -> prev;
tramp_free_list -> prev = this;
      }


      this = tramp_free_list;
      tramp_free_list = this -> next_free;


      this -> name = name;
      this -> data1 = (unsigned int) i1;
      this -> data2 = (unsigned int) i2;
      this -> function = (unsigned int) f;
      return (PFoIrI) (this -> code_ptr);
}


PFoIrI tramp_alloc1(PFoIrI f, int i1, char * name) {
    return tramp_alloc(f,i1,0,name);
}


void tramp_free(PFoIrI f) {
      if (tramp_valid(f)) {
          struct code_blob * cb = (struct code_blob *) f;
          struct data_blob * db = (struct data_blob *) cb -> data_ptr;
          db -> next_free = tramp_free_list;
          db -> name = 0;
          tramp_free_list = db;
      }
      return;
  }


int tramp_data(PFoIrI f, PFoIrI *pfunc, int * pdata1,
                                                    int * pdata2, char ** pname)
{
    if (tramp_valid(f)) {
        struct code_blob * cb = (struct code_blob *) f;
        struct data_blob * db = (struct data_blob *) cb -> data_ptr;


        if (pfunc != 0) *pfunc = db -> function;
        if (pdata1 != 0) *pdata1 = db -> data1;
        if (pdata2 != 0) *pdata2 = db -> data2;
        if (pname != 0) *pname = db -> name;
        return 1;
    } else return 0;
}


void tramp_dump(FILE * f) {
    struct data_blob * start = tramp_list;
    struct data_blob * next = start;


    if (next != 0) do {
        if (next -> name) {
            fprintf(f, "data_p = %x, code_p = %x, func = %x, "
             "data1 = %x, data2 = %x, name = %s\n",
next, next -> code_ptr, next -> function, next -> data1,
next -> data2, next -> name);
        }
        next = next -> next;
    } while (next != start);
}


#ifdef TEST_TRAMP
int compose_helper(int x) {
    PFoIrI f = (PFoIrI) get_g2(),
                  g = (PFoIrI) get_g3();
    printf("Compose_helper (%x)(%x)(%d)\n", f, g, x);
    return f(g(x));
}


int plus_helper(int x) {
    PFoIrI f = (PFoIrI) get_g2(),
                  g = (PFoIrI) get_g3();
    printf("Plus_helper ((%x)+(%x))(%d)\n", f, g, x);
    return f(x)+g(x);
}


PFoIrI compose(PFoIrI f, PFoIrI g) {
    int i_f = (int) f, i_g = (int) g;
    return tramp_alloc(compose_helper, i_f, i_g, "compose");
}


PFoIrI plus_func(PFoIrI f, PFoIrI g) {
    int i_f = (int) f, i_g = (int) g;
    return tramp_alloc(plus_helper, i_f, i_g, "plus_func");
}


int zero(int i) {
    return 0;
}


int one(int i) {
    return 1;
}


int plus_one(int i) {
    return i+1;
}


int plus_two(int i) {
    return i+2;
}


int print_hidden_int(int i_f) {
    FILE * f = (FILE *) i_f;
    int x = get_g2();
    fprintf(f, "Get_g2() returned %d\n", x);
    return x;
}


#define MANY 6


main() {
    PFoIrI e,f,g,h;
    PFoIrI F[MANY];
    int i;
    int er, fr, gr, hr;


    e = tramp_alloc1(print_hidden_int, 0, "phi");
    f = tramp_alloc1(print_hidden_int, 1, "phi");
    g = tramp_alloc1(print_hidden_int, 2, "phi");
    h = tramp_alloc1(print_hidden_int, 3, "phi");


    tramp_dump(stdout);


    er = e((int)stdout);
    fr = f((int)stdout);
    gr = g((int)stdout);
    hr = h((int)stdout);


    fprintf(stdout, "e returned %d\n", er);
    fprintf(stdout, "f returned %d\n", fr);
    fprintf(stdout, "g returned %d\n", gr);
    fprintf(stdout, "h returned %d\n", hr);


    tramp_free(e);
    tramp_free(f);
    tramp_free(g);
    tramp_free(h);


    tramp_dump(stdout);


    F[0] = zero;
    F[1] = one;
    for (i = 2; i < MANY; i++) {
        F[i] = plus_func(F[i-1],F[i-2]);
    }


    tramp_dump(stdout);
    for (i = 0; i < MANY; i++) {
        fprintf(stdout, "%x(0) = %d\n", F[i], F[i](0));
    }
}
#endif
================================================================
! get_g2.il
.inline get_g2,0
mov %g2,%o0
.end


.inline get_g3,0
mov %g3,%o0
.end


.inline flush,1
iflush %o0
.end
================================================================
! get_g2.s
.section ".text"
.global get_g2
  get_g2:
retl
mov %g2,%o0


.global get_g3
  get_g3:
retl
mov %g3,%o0


.global flush
  flush:
retl
iflush %o0
================================================================


David Chase
Sun (speaking for myself)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.