linux-mips-fnet
[Top] [All Lists]

Ralf's ideas: inline generic functions ?

To: ralf@uni-koblenz.de, linux-mips@fnet.fr
Subject: Ralf's ideas: inline generic functions ?
From: Vladimir Roganov <roganov@niisi.msk.ru>
Date: Mon, 19 Oct 1998 14:47:06 +0400
Organization: NIISI RAS
References: <19981013215927.A2692@uni-koblenz.de> <3625D799.7D923FA9@niisi.msk.ru> <19981017004408.E3370@uni-koblenz.de>
Sender: vladimir@niisi.msk.ru
ralf@uni-koblenz.de wrote:
> 
> Ok, here is the first working and tested version of my runtime patched
> get_mmu_context thing.  While writing the code I noticed that the code
> patching stuff is actually already a part of what I was intending to implement
> since long time like for example getting rid of function pointers and can
> be used to optimize many more things throughout the kernel.  So while some
> parts already look somewhat generic I'd like to make them really generic.
> The thing is probably going to look somewhat similar to the Sparc btfixup
> code which I'm going to read now.
> 
>   Ralf
> 
>   ------------------------------------------------------------------------
> 
>    asid-patch   Name: asid-patch
>                 Type: Plain Text (text/plain)

Hi Ralf, Hi others !

Looking to code switches across Linux sources, I also think about idea
to implement emulation of generic functions (method dispatchers), 
for GCC which are self-(re)inlining at runtime. 

Really, this think can reasonable express any quantity of 
machine/processor/other_condition specific, same time code using one 
will looks okey and run faster. 

It looks You mean something analogical, so it should be nice thing.
What about BTFIXUP, it looks less flexible as I understand from sources.

We have i386,R3000,Sparc computers under Linux, so we are able (and
interesting)
to help with testing such thing. Please send ideas/proposals/code.

Attached code contains few ideas (or, for optimistic people, prototype)
of "Generic Function Inliner", working (as a little demo) at i386.
It allows to define generic function, any time to add methods and
(re)inline best candidate from methods using priority-based scheme.
It should be enforced and extended many ways to be useful in practice...
It is also interesting to receive comments about this idea.  

In hope to be useful,
With best regards,
Vladimir
/*  
 *   Generic Function Inliner  (prototype!)
 * 
 *   GCC supports smart asm(...) directive, so it looks able to use it
 *   for runtime code inlining.  To support inline 'methods' 
 *   few structures for code manipulation are created.
 *   During initialization and work somebody can define their method for
 *   any generic function, what will hook reinlining using priority-based
 *   scheme.
 */

#include <stdio.h>    
#include <stdlib.h>
#include <sys/mman.h> 

/*
 *  The body of generic function, containing self-inliner stuff.
 *  The important parameters of code are:
 *     1) reserved size (10 bytes for this example)
 *     2) convention for parameter pass, value return and regs/mem changes
 *  All methods must have same interface (signature). 
 */
#define generic3(fun,a,b,c) ({ \
   register unsigned long out asm("eax"); \
   register unsigned long aa  asm("ebx") = a; \
   register unsigned long bb  asm("ecx") = b; \
   register unsigned long cc  asm("edx") = c; \
   asm ("call __generic_inliner; .asciz \"" fun "\"; .asciz \"\""\
                            : "=r" (out) \
                            : "r"  (aa), "r" (bb), "r" (cc) \
                            : "eax", "ebx", "ecx", "edx" ); \
   out; \
})

/*
 *  Structures needed to store functions/methods/usages
 */

typedef int (*pred_t)(); /* Priority predicate (using global vars) */

struct method {
        struct method* next;
        char *name;
        char *from;
        char *to;
        pred_t pred;
};
struct usage {
        struct usage *next;
        char *from;
        char *to;
};
struct generic {
        struct generic *next;
        char *fun;
        struct method *best_method;
        struct method *methods;
        struct usage *usages;
        int    usage_count;
} *generics = NULL; 

/* Utility */
void *xmalloc (int size) 
{
        void *m = malloc(size);
        if (!m)
                printf("memory exceeded\n");
        memset(m,0,size);
        return m;
}

/* Find generic or return last link address */
struct generic **find_generic(char *fun) 
{
        struct generic **g = &generics;
        while (*g) {
                if (!strcmp(fun,(*g)->fun)) 
                        break;
                g = &(*g)->next;
        }
        return g;
}

/* Return or create new generic */
struct generic *intern_generic(char *fun) 
{
        struct generic **g = find_generic(fun);
        if (!*g) {
                *g = xmalloc(sizeof(**g));
                (*g)->fun  = fun;
        }
        return *g;
}

/* Icache invalidation (for test only ) */
static flush_icache_range (char* from, char *to)
{
        mprotect((void*)((unsigned long)from & ~0xfff), 
                 0x1000, PROT_EXEC|PROT_WRITE);
}


/*  
 *  Inline given method to given usage place
 */
#define NOP_CODE   0x90
static void do_inline (struct method *m, struct usage* u)
{
        if (m->to-m->from > u->to-u->from)
          /* In this case we can generate trampoline with call ?! */
                printf ("unable to inline: method too long\n");
        flush_icache_range (u->from, u->to); // to be able to modify code !
        printf("Inlining code from %x to %x\n", u->from, u->to);
        printf("%s:%d\n", __FUNCTION__, __LINE__);
        memset(u->from, NOP_CODE, u->to-u->from);
        printf("u->from=%x, m->from=%x, m->to-m->from=%d\n", 
               u->from, m->from, m->to-m->from);
        memcpy(u->from, m->from,  m->to-m->from);
        printf("code: %x %x %x %x %x %x\n",
               u->from[0], u->from[1], u->from[2],
               u->from[3], u->from[4], u->from[5]);
        flush_icache_range (u->from, u->to);
}


/*
 *  Reinline given function choosing best candidate
 */
void reinline_generic(char *fun)
{
        struct generic *g = *find_generic(fun);
        struct method *m, *old_best = NULL;
        struct usage *u;

        int max = 0;
        int val;

        if (!g) 
                printf ("no methods for '%s'", fun);

        old_best = g -> best_method;
        g -> best_method = NULL;

        m = g -> methods;
        while(m) {
                val = m->pred();
                if (val > max) { 
                        g -> best_method = m; 
                        max = val; 
                }
                m = m->next;
        }

        u = g -> usages;
        if (!g->best_method && u)
                printf("no candidates for '%s' function usages\n", fun);
        
        if (old_best != g->best_method)
                while(u) {
                        do_inline(g->best_method, u);
                        u = u -> next;
                }
}

/* Define new method */
void __defmethod(char *fun, pred_t pred, char *name,
                 char* code_start, char* code_end) 
{
        struct generic *g = intern_generic(fun);
        struct method  *m = xmalloc(sizeof(*m));

        m->next = g->methods;
        m->from = code_start;
        m->to   = code_end;
        m->pred = pred;
        m->name = name;

        g->methods = m;

        reinline_generic(fun);
}

#ifndef __STR
#define __STR(x) #x
#endif
#ifndef STR
#define STR(x) __STR(x)
#endif
 
/* Macro used to define method as asm(...) inline code */
#define defmethod(fun,pred,code) {\
      register char* code_start asm("eax"); \
      register char* code_end   asm("ebx"); \
      asm ("movl $start_" STR(pred) ", %%eax\n" \
           "movl $end_"   STR(pred) ", %%ebx\n" \
           "jmp  end_" STR(pred)"\n" \
           "start_" STR(pred)":\n" \
            code  "\n"  \
           "end_" STR(pred)":\n" \
           : \
           : "r" (code_start), "r" (code_end)); \
      __defmethod(fun,pred,STR(pred),code_start,code_end); \
}

/*
 *  Function called from usage places, which register
 *  generic function usage and overlaps itself by best method
 */
#define CALL_SIZE  5

static unsigned char* _generic_inliner (char* address) 
{
        unsigned char* fun  = address;
        unsigned char* from = address - CALL_SIZE;
        unsigned char* to   = address;

        while (*to) to++; // Skip name
        to++;
        while (*to) to++; // Skip NOPs
        to++;

        printf ("fun = %s, address = %x, size = %d, to = %x\n", 
                fun, from, to-from, to);

        {
                struct usage *u;
                struct generic *g = *find_generic(fun);
                if (!g)
                        printf ("Undefined generic '%s'\n", fun);
                if (!g->best_method)
                        printf("No best method for '%s'\n", fun);
                
                u = xmalloc(sizeof(*u));

                u -> from = from;
                u -> to   = to;
                u -> next = g -> usages;

                g -> usages = u;
                g -> usage_count++;

                do_inline (g->best_method, u);
        }
        printf("%s:%d\n", __FUNCTION__, __LINE__);

        if (address) /* To prevent GCC optimization */
                return from;

        /* __generic_inliner is a trampoline for above */
        asm(".globl __generic_inliner; __generic_inliner:\n"
            "call _generic_inliner\n"
            "pop %%ebx\n" 
            "jmp %%eax\n"
            : 
            :
            : "eax", "ebx");
        
        return "Impossible to be here";
}


/*
 *   Control routine, printing some statistic
 */
void show_generics(void)
{
        struct generic *g = generics;
        printf ("Generic functions in use:\n");
        while (g) {
                printf("\t%s:\tbest_method=%s\tusages=%d\n",
                       g->fun, 
                       g->best_method ? g->best_method->name : "(NULL)", 
                       g->usage_count);
                g = g -> next;
        }
        printf ("----------------------------------------------\n");
}








/* ------------------------------------------
 *  All above should have simple interface, 
 *  to make it's usage as simple as possible
/* ------------------------------------------

/* Something in headers: */

#define fun(a,b,c) generic3("fun",a,b,c)

/* Module code */

#define R3000 1
#define R4000 2
int cpu = R3000;

static int r3000_fun() 
{
        return cpu == R3000;
}

static int r4000_fun()
{
        return cpu == R4000;
}

void r3000_init(void)
{
        printf("%s:%d\n", __FUNCTION__, __LINE__);
        defmethod("fun", r3000_fun, "movl $12345, %%eax");
        printf("%s:%d\n", __FUNCTION__, __LINE__);
}

/* Code users */

main () 
{
        show_generics();
        r3000_init();
        show_generics();
        printf ("%d\n", fun(1,2,3));
        cpu = R4000;
        defmethod("fun", r4000_fun, "movl $54321, %%eax");
        show_generics();
        printf ("%d\n", fun(1,2,3));
        show_generics();
}
Generic functions in use:
----------------------------------------------
r3000_init:311
r3000_init:313
Generic functions in use:
        fun:    best_method=r3000_fun   usages=0
----------------------------------------------
fun = fun, address = 8048a42, size = 10, to = 8048a4c
Inlining code from 8048a42 to 8048a4c
do_inline:112
u->from=8048a42, m->from=80489e8, m->to-m->from=5
code: ffffffb8 39 30 0 0 ffffff90
_generic_inliner:242
12345
Inlining code from 8048a42 to 8048a4c
do_inline:112
u->from=8048a42, m->from=8048a6d, m->to-m->from=5
code: ffffffb8 31 ffffffd4 0 0 ffffff90
Generic functions in use:
        fun:    best_method=r4000_fun   usages=1
----------------------------------------------
fun = fun, address = 8048a9f, size = 10, to = 8048aa9
Inlining code from 8048a9f to 8048aa9
do_inline:112
u->from=8048a9f, m->from=8048a6d, m->to-m->from=5
code: ffffffb8 31 ffffffd4 0 0 ffffff90
_generic_inliner:242
54321
Generic functions in use:
        fun:    best_method=r4000_fun   usages=2
----------------------------------------------
<Prev in Thread] Current Thread [Next in Thread>