Return to insn_lookup.c CVS log

Up to [Dynamips Cisco Emulator] / cf

Annotation of cf/insn_lookup.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Cisco 7200 (Predator) simulation platform.
        !             3:  * Copyright (c) 2006 Christophe Fillot ([email protected])
        !             4:  *
        !             5:  * Instruction Lookup Tables.
        !             6:  */
        !             7: 
        !             8: #include <stdio.h>
        !             9: #include <stdlib.h>
        !            10: #include <unistd.h>
        !            11: #include <string.h>
        !            12: #include <sys/types.h>
        !            13: #include <sys/stat.h>
        !            14: #include <sys/mman.h>
        !            15: #include <assert.h>
        !            16: 
        !            17: #include "utils.h"
        !            18: #include "hash.h"
        !            19: #include "insn_lookup.h"
        !            20: 
        !            21: /* Hash function for a CBM */
        !            22: static inline u_int cbm_hash_f(void *ccbm)
        !            23: {
        !            24:    cbm_array_t *cbm = (cbm_array_t *)ccbm;
        !            25:    char *p,*s = (char *)(cbm->tab);
        !            26:    u_int h,g,i;
        !            27: 
        !            28:    for(h=0,i=0,p=s;i<(cbm->nr_entries*sizeof(int));p+=1,i++)
        !            29:    {
        !            30:       h = (h << 4) + *p;
        !            31:       if ((g = h & 0xf0000000)) {
        !            32:          h = h ^ (g >> 24);
        !            33:          h = h ^ g;
        !            34:       }
        !            35:    }
        !            36: 
        !            37:    return(h);
        !            38: }
        !            39: 
        !            40: /* Comparison function for 2 CBM */
        !            41: static inline int cbm_cmp_f(void *b1,void *b2)
        !            42: {
        !            43:    cbm_array_t *cbm1 = (cbm_array_t *)b1;
        !            44:    cbm_array_t *cbm2 = (cbm_array_t *)b2;
        !            45:    int i;
        !            46:    
        !            47:    for(i=0;i<cbm1->nr_entries;i++)
        !            48:       if (cbm1->tab[i] != cbm2->tab[i])
        !            49:          return(FALSE);
        !            50:    
        !            51:    return(TRUE);
        !            52: }
        !            53: 
        !            54: /* Set bit corresponding to a rule number in a CBM */
        !            55: static inline void cbm_set_rule(cbm_array_t *cbm,int rule_id)
        !            56: {
        !            57:    CBM_ARRAY(cbm,(rule_id >> CBM_SHIFT)) |= 1 << (rule_id & (CBM_SIZE-1));
        !            58: }
        !            59: 
        !            60: /* Clear bit corresponding to a rule number in a CBM */
        !            61: static inline void cbm_unset_rule(cbm_array_t *cbm,int rule_id)
        !            62: {
        !            63:    CBM_ARRAY(cbm,(rule_id >> CBM_SHIFT)) &= ~(1 << (rule_id & (CBM_SIZE-1)));
        !            64: }
        !            65: 
        !            66: /* Returns TRUE if  bit corresponding to a rule number in a CBM is set */
        !            67: static inline int cbm_check_rule(cbm_array_t *cbm,int rule_id)
        !            68: {
        !            69:    return(CBM_ARRAY(cbm,(rule_id >> CBM_SHIFT)) & 
        !            70:          (1 << (rule_id & (CBM_SIZE-1))));
        !            71: }
        !            72: 
        !            73: /* Compute bitwise ANDing of two CBM */
        !            74: static inline void 
        !            75: cbm_bitwise_and(cbm_array_t *result,cbm_array_t *a1,cbm_array_t *a2)
        !            76: {
        !            77:    int i;
        !            78: 
        !            79:    /* Compute bitwise ANDing */
        !            80:    for(i=0;i<a1->nr_entries;i++)
        !            81:       CBM_ARRAY(result,i) = CBM_ARRAY(a1,i) & CBM_ARRAY(a2,i);
        !            82: }
        !            83: 
        !            84: /* Get first matching rule number */
        !            85: static inline int cbm_first_match(insn_lookup_t *ilt,cbm_array_t *cbm)
        !            86: {
        !            87:    int i;
        !            88: 
        !            89:    for(i=0;i<ilt->nr_insn;i++)
        !            90:       if (cbm_check_rule(cbm,i)) 
        !            91:          return(i);
        !            92:    
        !            93:    return(-1);
        !            94: }
        !            95: 
        !            96: /* Create a class bitmap (CBM) */
        !            97: static cbm_array_t *cbm_create(insn_lookup_t *ilt)
        !            98: {
        !            99:    cbm_array_t *array;
        !           100:    int size;
        !           101: 
        !           102:    size = CBM_CSIZE(ilt->cbm_size);
        !           103: 
        !           104:    /* CBM are simply bit arrays */
        !           105:    assert((array = malloc(size)) != NULL);
        !           106:    memset(array,0,size);
        !           107:    array->nr_entries = ilt->cbm_size;
        !           108:    return array;
        !           109: }
        !           110: 
        !           111: /* Duplicate a class bitmap */
        !           112: static cbm_array_t *cbm_duplicate(cbm_array_t *cbm)
        !           113: {
        !           114:    int size = CBM_CSIZE(cbm->nr_entries);
        !           115:    cbm_array_t *array;
        !           116: 
        !           117:    assert((array = malloc(size)) != NULL);
        !           118:    memcpy(array,cbm,size);
        !           119:    return array;
        !           120: }
        !           121: 
        !           122: /* 
        !           123:  * Get equivalent class corresponding to a class bitmap. Create eqclass 
        !           124:  * structure if needed (CBM not previously seen).
        !           125:  */
        !           126: static rfc_eqclass_t *cbm_get_eqclass(rfc_array_t *rfct,cbm_array_t *cbm)
        !           127: {
        !           128:    rfc_eqclass_t *eqcl;
        !           129:    cbm_array_t *bmp;
        !           130: 
        !           131:    /* Lookup for CBM into hash table */
        !           132:    if ((eqcl = hash_table_lookup(rfct->cbm_hash,cbm)) == NULL)
        !           133:    {
        !           134:       /* Duplicate CBM */
        !           135:       assert((bmp = cbm_duplicate(cbm)) != NULL);
        !           136: 
        !           137:       /* CBM is not already known */
        !           138:       assert((eqcl = malloc(sizeof(rfc_eqclass_t))) != NULL);
        !           139:       assert(rfct->nr_eqid < rfct->nr_elements);
        !           140: 
        !           141:       /* Get a new equivalent ID */
        !           142:       eqcl->eqID = rfct->nr_eqid++;
        !           143:       eqcl->cbm = bmp;
        !           144:       rfct->id2cbm[eqcl->eqID] = bmp;
        !           145: 
        !           146:       /* Insert it in hash table */
        !           147:       assert(hash_table_insert(rfct->cbm_hash,bmp,eqcl) == 0);
        !           148:    }
        !           149: 
        !           150:    return eqcl;
        !           151: }
        !           152: 
        !           153: /* Allocate an array for Recursive Flow Classification */
        !           154: static rfc_array_t *rfc_alloc_array(int nr_elements)
        !           155: {
        !           156:    rfc_array_t *array;
        !           157:    int total_size;
        !           158: 
        !           159:    /* Compute size of memory chunk needed to store the array */
        !           160:    total_size = (nr_elements * sizeof(int)) + sizeof(rfc_array_t);
        !           161:    assert((array = malloc(total_size)) != NULL);
        !           162: 
        !           163:    memset(array,0,total_size);
        !           164:    array->nr_elements = nr_elements;
        !           165:    
        !           166:    /* Initialize hash table for Class Bitmaps */
        !           167:    array->cbm_hash = hash_table_create(cbm_hash_f,cbm_cmp_f,CBM_HASH_SIZE);
        !           168:    assert(array->cbm_hash != NULL);
        !           169: 
        !           170:    /* Initialize table for converting ID to CBM */
        !           171:    array->id2cbm = calloc(nr_elements,sizeof(cbm_array_t *));
        !           172:    assert(array->id2cbm != NULL);
        !           173: 
        !           174:    return(array);
        !           175: }
        !           176: 
        !           177: /* Check an instruction with specified parameter */
        !           178: static void rfc_check_insn(insn_lookup_t *ilt,cbm_array_t *cbm,
        !           179:                            ilt_check_cbk_t pcheck,int value)
        !           180: {
        !           181:    void *p;
        !           182:    int i;
        !           183: 
        !           184:    for(i=0;i<ilt->nr_insn;i++) {
        !           185:       p = ilt->get_insn(i);
        !           186: 
        !           187:       if (pcheck(p,value)) 
        !           188:          cbm_set_rule(cbm,i);
        !           189:       else
        !           190:          cbm_unset_rule(cbm,i);
        !           191:    }
        !           192: }
        !           193: 
        !           194: /* RFC Chunk preprocessing: phase 0 */
        !           195: static rfc_array_t *rfc_phase_0(insn_lookup_t *ilt,ilt_check_cbk_t pcheck)
        !           196: {
        !           197:    rfc_eqclass_t *eqcl;
        !           198:    rfc_array_t *rfct;
        !           199:    cbm_array_t *bmp;
        !           200:    int i;
        !           201: 
        !           202:    /* allocate a temporary class bitmap */
        !           203:    assert((bmp = cbm_create(ilt)) != NULL);
        !           204: 
        !           205:    /* Allocate a new RFC array of 16-bits entries */
        !           206:    assert((rfct = rfc_alloc_array(RFC_ARRAY_MAXSIZE)) != NULL);
        !           207: 
        !           208:    for(i=0;i<RFC_ARRAY_MAXSIZE;i++)
        !           209:    {
        !           210:       /* determine all instructions that match this value */
        !           211:       rfc_check_insn(ilt,bmp,pcheck,i);
        !           212: 
        !           213:       /* get equivalent class for this bitmap */
        !           214:       assert((eqcl = cbm_get_eqclass(rfct,bmp)) != NULL);
        !           215: 
        !           216:       /* fill the RFC table */
        !           217:       rfct->eqID[i] = eqcl->eqID;
        !           218:    }
        !           219: 
        !           220:    free(bmp);
        !           221:    return rfct;
        !           222: }
        !           223: 
        !           224: /* RFC Chunk preprocessing: phase j (j > 0) */
        !           225: static rfc_array_t *rfc_phase_j(insn_lookup_t *ilt,rfc_array_t *p0,
        !           226:                                 rfc_array_t *p1)
        !           227: {
        !           228:    rfc_eqclass_t *eqcl;
        !           229:    rfc_array_t *rfct;
        !           230:    cbm_array_t *bmp;
        !           231:    int nr_elements;
        !           232:    int index = 0;
        !           233:    int i,j;
        !           234: 
        !           235:    /* allocate a temporary class bitmap */
        !           236:    assert((bmp = cbm_create(ilt)) != NULL);
        !           237: 
        !           238:    /* compute number of elements */
        !           239:    nr_elements = p0->nr_eqid * p1->nr_eqid;
        !           240: 
        !           241:    /* allocate a new RFC array */
        !           242:    assert((rfct = rfc_alloc_array(nr_elements)) != NULL);
        !           243:    rfct->parent0 = p0;
        !           244:    rfct->parent1 = p1;
        !           245: 
        !           246:    /* make a cross product between p0 and p1 */
        !           247:    for(i=0;i<p0->nr_eqid;i++)
        !           248:       for(j=0;j<p1->nr_eqid;j++)
        !           249:       {
        !           250:          /* compute bitwise AND */
        !           251:          cbm_bitwise_and(bmp,p0->id2cbm[i],p1->id2cbm[j]);
        !           252: 
        !           253:          /* get equivalent class for this bitmap */
        !           254:          assert((eqcl = cbm_get_eqclass(rfct,bmp)) != NULL);
        !           255: 
        !           256:          /* fill RFC table */
        !           257:          rfct->eqID[index++] = eqcl->eqID;
        !           258:       }
        !           259: 
        !           260:    free(bmp);
        !           261:    return rfct;
        !           262: }
        !           263: 
        !           264: /* Compute RFC phase 0 */
        !           265: static void ilt_phase_0(insn_lookup_t *ilt,int idx,ilt_check_cbk_t pcheck)
        !           266: {
        !           267:    rfc_array_t *rfct;
        !           268: 
        !           269:    assert((rfct = rfc_phase_0(ilt,pcheck)) != NULL);
        !           270:    ilt->rfct[idx] = rfct;
        !           271: }
        !           272: 
        !           273: /* Compute RFC phase j */
        !           274: static void ilt_phase_j(insn_lookup_t *ilt,int p0,int p1,int res)
        !           275: {
        !           276:    rfc_array_t *rfct;
        !           277: 
        !           278:    assert((rfct = rfc_phase_j(ilt,ilt->rfct[p0],ilt->rfct[p1])) != NULL);
        !           279:    ilt->rfct[res] = rfct;
        !           280: }
        !           281: 
        !           282: /* Postprocessing */
        !           283: static void ilt_postprocessing(insn_lookup_t *ilt)
        !           284: {
        !           285:    rfc_array_t *rfct = ilt->rfct[2];
        !           286:    int i;
        !           287: 
        !           288:    for(i=0;i<rfct->nr_elements;i++)
        !           289:       rfct->eqID[i] = cbm_first_match(ilt,rfct->id2cbm[rfct->eqID[i]]);
        !           290: }
        !           291: 
        !           292: /* Instruction lookup table compilation */
        !           293: static void ilt_compile(insn_lookup_t *ilt)
        !           294: {  
        !           295:    ilt_phase_0(ilt,0,ilt->chk_hi);
        !           296:    ilt_phase_0(ilt,1,ilt->chk_lo);
        !           297:    ilt_phase_j(ilt,0,1,2);
        !           298:    ilt_postprocessing(ilt);
        !           299: }
        !           300: 
        !           301: /* Create an instruction lookup table */
        !           302: insn_lookup_t *ilt_create(int nr_insn,ilt_get_insn_cbk_t get_insn,
        !           303:                           ilt_check_cbk_t chk_lo,ilt_check_cbk_t chk_hi)
        !           304: {
        !           305:    insn_lookup_t *ilt;
        !           306:    
        !           307:    assert((ilt = malloc(sizeof(*ilt))) != NULL);
        !           308:    memset(ilt,0,sizeof(*ilt));
        !           309: 
        !           310:    ilt->cbm_size = normalize_size(nr_insn,CBM_SIZE,CBM_SHIFT);
        !           311:    ilt->nr_insn  = nr_insn;
        !           312:    ilt->get_insn = get_insn;
        !           313:    ilt->chk_lo   = chk_lo;
        !           314:    ilt->chk_hi   = chk_hi;
        !           315: 
        !           316:    ilt_compile(ilt);
        !           317:    return(ilt);
        !           318: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.