![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to insn_lookup.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Dynamips Cisco Emulator] / cf|
Return to insn_lookup.c CVS log | Up to [Dynamips Cisco Emulator] / cf |
1.1 root 1: /* 1.1.1.3 ! root 2: * Cisco router simulation platform. 1.1 root 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 */ 1.1.1.2 root 105: array = malloc(size); 106: assert(array); 107: 1.1 root 108: memset(array,0,size); 109: array->nr_entries = ilt->cbm_size; 110: return array; 111: } 112: 113: /* Duplicate a class bitmap */ 114: static cbm_array_t *cbm_duplicate(cbm_array_t *cbm) 115: { 116: int size = CBM_CSIZE(cbm->nr_entries); 117: cbm_array_t *array; 118: 1.1.1.2 root 119: array = malloc(size); 120: assert(array); 1.1 root 121: memcpy(array,cbm,size); 122: return array; 123: } 124: 125: /* 126: * Get equivalent class corresponding to a class bitmap. Create eqclass 127: * structure if needed (CBM not previously seen). 128: */ 129: static rfc_eqclass_t *cbm_get_eqclass(rfc_array_t *rfct,cbm_array_t *cbm) 130: { 131: rfc_eqclass_t *eqcl; 132: cbm_array_t *bmp; 133: 134: /* Lookup for CBM into hash table */ 135: if ((eqcl = hash_table_lookup(rfct->cbm_hash,cbm)) == NULL) 136: { 137: /* Duplicate CBM */ 1.1.1.2 root 138: bmp = cbm_duplicate(cbm); 139: assert(bmp); 1.1 root 140: 141: /* CBM is not already known */ 1.1.1.2 root 142: eqcl = malloc(sizeof(rfc_eqclass_t)); 143: assert(eqcl); 144: 1.1 root 145: assert(rfct->nr_eqid < rfct->nr_elements); 146: 147: /* Get a new equivalent ID */ 148: eqcl->eqID = rfct->nr_eqid++; 149: eqcl->cbm = bmp; 150: rfct->id2cbm[eqcl->eqID] = bmp; 151: 152: /* Insert it in hash table */ 1.1.1.2 root 153: if (hash_table_insert(rfct->cbm_hash,bmp,eqcl) == -1) 154: return NULL; 1.1 root 155: } 156: 157: return eqcl; 158: } 159: 160: /* Allocate an array for Recursive Flow Classification */ 161: static rfc_array_t *rfc_alloc_array(int nr_elements) 162: { 163: rfc_array_t *array; 164: int total_size; 165: 166: /* Compute size of memory chunk needed to store the array */ 167: total_size = (nr_elements * sizeof(int)) + sizeof(rfc_array_t); 1.1.1.2 root 168: array = malloc(total_size); 169: assert(array); 1.1 root 170: memset(array,0,total_size); 171: array->nr_elements = nr_elements; 172: 173: /* Initialize hash table for Class Bitmaps */ 174: array->cbm_hash = hash_table_create(cbm_hash_f,cbm_cmp_f,CBM_HASH_SIZE); 1.1.1.2 root 175: assert(array->cbm_hash); 1.1 root 176: 177: /* Initialize table for converting ID to CBM */ 178: array->id2cbm = calloc(nr_elements,sizeof(cbm_array_t *)); 1.1.1.2 root 179: assert(array->id2cbm); 1.1 root 180: 181: return(array); 182: } 183: 184: /* Check an instruction with specified parameter */ 185: static void rfc_check_insn(insn_lookup_t *ilt,cbm_array_t *cbm, 186: ilt_check_cbk_t pcheck,int value) 187: { 188: void *p; 189: int i; 190: 191: for(i=0;i<ilt->nr_insn;i++) { 192: p = ilt->get_insn(i); 193: 194: if (pcheck(p,value)) 195: cbm_set_rule(cbm,i); 196: else 197: cbm_unset_rule(cbm,i); 198: } 199: } 200: 201: /* RFC Chunk preprocessing: phase 0 */ 202: static rfc_array_t *rfc_phase_0(insn_lookup_t *ilt,ilt_check_cbk_t pcheck) 203: { 204: rfc_eqclass_t *eqcl; 205: rfc_array_t *rfct; 206: cbm_array_t *bmp; 207: int i; 208: 209: /* allocate a temporary class bitmap */ 1.1.1.2 root 210: bmp = cbm_create(ilt); 211: assert(bmp); 1.1 root 212: 213: /* Allocate a new RFC array of 16-bits entries */ 1.1.1.2 root 214: rfct = rfc_alloc_array(RFC_ARRAY_MAXSIZE); 215: assert(rfct); 1.1 root 216: 217: for(i=0;i<RFC_ARRAY_MAXSIZE;i++) 218: { 219: /* determine all instructions that match this value */ 220: rfc_check_insn(ilt,bmp,pcheck,i); 221: 222: /* get equivalent class for this bitmap */ 1.1.1.2 root 223: eqcl = cbm_get_eqclass(rfct,bmp); 224: assert(eqcl); 1.1 root 225: 226: /* fill the RFC table */ 227: rfct->eqID[i] = eqcl->eqID; 228: } 229: 230: free(bmp); 231: return rfct; 232: } 233: 234: /* RFC Chunk preprocessing: phase j (j > 0) */ 235: static rfc_array_t *rfc_phase_j(insn_lookup_t *ilt,rfc_array_t *p0, 236: rfc_array_t *p1) 237: { 238: rfc_eqclass_t *eqcl; 239: rfc_array_t *rfct; 240: cbm_array_t *bmp; 241: int nr_elements; 242: int index = 0; 243: int i,j; 244: 245: /* allocate a temporary class bitmap */ 1.1.1.2 root 246: bmp = cbm_create(ilt); 247: assert(bmp); 1.1 root 248: 249: /* compute number of elements */ 250: nr_elements = p0->nr_eqid * p1->nr_eqid; 251: 252: /* allocate a new RFC array */ 1.1.1.2 root 253: rfct = rfc_alloc_array(nr_elements); 254: assert(rfct); 1.1 root 255: rfct->parent0 = p0; 256: rfct->parent1 = p1; 257: 258: /* make a cross product between p0 and p1 */ 259: for(i=0;i<p0->nr_eqid;i++) 260: for(j=0;j<p1->nr_eqid;j++) 261: { 262: /* compute bitwise AND */ 263: cbm_bitwise_and(bmp,p0->id2cbm[i],p1->id2cbm[j]); 264: 265: /* get equivalent class for this bitmap */ 1.1.1.2 root 266: eqcl = cbm_get_eqclass(rfct,bmp); 267: assert(eqcl); 1.1 root 268: 269: /* fill RFC table */ 270: rfct->eqID[index++] = eqcl->eqID; 271: } 272: 273: free(bmp); 274: return rfct; 275: } 276: 277: /* Compute RFC phase 0 */ 278: static void ilt_phase_0(insn_lookup_t *ilt,int idx,ilt_check_cbk_t pcheck) 279: { 280: rfc_array_t *rfct; 281: 1.1.1.2 root 282: rfct = rfc_phase_0(ilt,pcheck); 283: assert(rfct); 1.1 root 284: ilt->rfct[idx] = rfct; 285: } 286: 287: /* Compute RFC phase j */ 288: static void ilt_phase_j(insn_lookup_t *ilt,int p0,int p1,int res) 289: { 290: rfc_array_t *rfct; 291: 1.1.1.2 root 292: rfct = rfc_phase_j(ilt,ilt->rfct[p0],ilt->rfct[p1]); 293: assert(rfct); 1.1 root 294: ilt->rfct[res] = rfct; 295: } 296: 297: /* Postprocessing */ 298: static void ilt_postprocessing(insn_lookup_t *ilt) 299: { 300: rfc_array_t *rfct = ilt->rfct[2]; 301: int i; 302: 303: for(i=0;i<rfct->nr_elements;i++) 304: rfct->eqID[i] = cbm_first_match(ilt,rfct->id2cbm[rfct->eqID[i]]); 305: } 306: 307: /* Instruction lookup table compilation */ 308: static void ilt_compile(insn_lookup_t *ilt) 309: { 310: ilt_phase_0(ilt,0,ilt->chk_hi); 311: ilt_phase_0(ilt,1,ilt->chk_lo); 312: ilt_phase_j(ilt,0,1,2); 313: ilt_postprocessing(ilt); 314: } 315: 316: /* Create an instruction lookup table */ 317: insn_lookup_t *ilt_create(int nr_insn,ilt_get_insn_cbk_t get_insn, 318: ilt_check_cbk_t chk_lo,ilt_check_cbk_t chk_hi) 319: { 320: insn_lookup_t *ilt; 321: 1.1.1.2 root 322: ilt = malloc(sizeof(*ilt)); 323: assert(ilt); 1.1 root 324: memset(ilt,0,sizeof(*ilt)); 325: 326: ilt->cbm_size = normalize_size(nr_insn,CBM_SIZE,CBM_SHIFT); 327: ilt->nr_insn = nr_insn; 328: ilt->get_insn = get_insn; 329: ilt->chk_lo = chk_lo; 330: ilt->chk_hi = chk_hi; 331: 332: ilt_compile(ilt); 333: return(ilt); 334: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.