![[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" 1.1.1.4 ! root 20: #include "dynamips.h" 1.1 root 21: 22: /* Hash function for a CBM */ 23: static inline u_int cbm_hash_f(void *ccbm) 24: { 25: cbm_array_t *cbm = (cbm_array_t *)ccbm; 26: char *p,*s = (char *)(cbm->tab); 27: u_int h,g,i; 28: 29: for(h=0,i=0,p=s;i<(cbm->nr_entries*sizeof(int));p+=1,i++) 30: { 31: h = (h << 4) + *p; 32: if ((g = h & 0xf0000000)) { 33: h = h ^ (g >> 24); 34: h = h ^ g; 35: } 36: } 37: 38: return(h); 39: } 40: 41: /* Comparison function for 2 CBM */ 42: static inline int cbm_cmp_f(void *b1,void *b2) 43: { 44: cbm_array_t *cbm1 = (cbm_array_t *)b1; 45: cbm_array_t *cbm2 = (cbm_array_t *)b2; 46: int i; 47: 48: for(i=0;i<cbm1->nr_entries;i++) 49: if (cbm1->tab[i] != cbm2->tab[i]) 50: return(FALSE); 51: 52: return(TRUE); 53: } 54: 55: /* Set bit corresponding to a rule number in a CBM */ 56: static inline void cbm_set_rule(cbm_array_t *cbm,int rule_id) 57: { 58: CBM_ARRAY(cbm,(rule_id >> CBM_SHIFT)) |= 1 << (rule_id & (CBM_SIZE-1)); 59: } 60: 61: /* Clear bit corresponding to a rule number in a CBM */ 62: static inline void cbm_unset_rule(cbm_array_t *cbm,int rule_id) 63: { 64: CBM_ARRAY(cbm,(rule_id >> CBM_SHIFT)) &= ~(1 << (rule_id & (CBM_SIZE-1))); 65: } 66: 67: /* Returns TRUE if bit corresponding to a rule number in a CBM is set */ 68: static inline int cbm_check_rule(cbm_array_t *cbm,int rule_id) 69: { 70: return(CBM_ARRAY(cbm,(rule_id >> CBM_SHIFT)) & 71: (1 << (rule_id & (CBM_SIZE-1)))); 72: } 73: 74: /* Compute bitwise ANDing of two CBM */ 75: static inline void 76: cbm_bitwise_and(cbm_array_t *result,cbm_array_t *a1,cbm_array_t *a2) 77: { 78: int i; 79: 80: /* Compute bitwise ANDing */ 81: for(i=0;i<a1->nr_entries;i++) 82: CBM_ARRAY(result,i) = CBM_ARRAY(a1,i) & CBM_ARRAY(a2,i); 83: } 84: 85: /* Get first matching rule number */ 86: static inline int cbm_first_match(insn_lookup_t *ilt,cbm_array_t *cbm) 87: { 88: int i; 89: 90: for(i=0;i<ilt->nr_insn;i++) 91: if (cbm_check_rule(cbm,i)) 92: return(i); 93: 94: return(-1); 95: } 96: 97: /* Create a class bitmap (CBM) */ 98: static cbm_array_t *cbm_create(insn_lookup_t *ilt) 99: { 100: cbm_array_t *array; 101: int size; 102: 103: size = CBM_CSIZE(ilt->cbm_size); 104: 105: /* CBM are simply bit arrays */ 1.1.1.2 root 106: array = malloc(size); 107: assert(array); 108: 1.1 root 109: memset(array,0,size); 110: array->nr_entries = ilt->cbm_size; 111: return array; 112: } 113: 114: /* Duplicate a class bitmap */ 115: static cbm_array_t *cbm_duplicate(cbm_array_t *cbm) 116: { 117: int size = CBM_CSIZE(cbm->nr_entries); 118: cbm_array_t *array; 119: 1.1.1.2 root 120: array = malloc(size); 121: assert(array); 1.1 root 122: memcpy(array,cbm,size); 123: return array; 124: } 125: 126: /* 127: * Get equivalent class corresponding to a class bitmap. Create eqclass 128: * structure if needed (CBM not previously seen). 129: */ 130: static rfc_eqclass_t *cbm_get_eqclass(rfc_array_t *rfct,cbm_array_t *cbm) 131: { 132: rfc_eqclass_t *eqcl; 133: cbm_array_t *bmp; 134: 135: /* Lookup for CBM into hash table */ 136: if ((eqcl = hash_table_lookup(rfct->cbm_hash,cbm)) == NULL) 137: { 138: /* Duplicate CBM */ 1.1.1.2 root 139: bmp = cbm_duplicate(cbm); 140: assert(bmp); 1.1 root 141: 142: /* CBM is not already known */ 1.1.1.2 root 143: eqcl = malloc(sizeof(rfc_eqclass_t)); 144: assert(eqcl); 145: 1.1 root 146: assert(rfct->nr_eqid < rfct->nr_elements); 147: 148: /* Get a new equivalent ID */ 149: eqcl->eqID = rfct->nr_eqid++; 150: eqcl->cbm = bmp; 151: rfct->id2cbm[eqcl->eqID] = bmp; 152: 153: /* Insert it in hash table */ 1.1.1.2 root 154: if (hash_table_insert(rfct->cbm_hash,bmp,eqcl) == -1) 155: return NULL; 1.1 root 156: } 157: 158: return eqcl; 159: } 160: 161: /* Allocate an array for Recursive Flow Classification */ 162: static rfc_array_t *rfc_alloc_array(int nr_elements) 163: { 164: rfc_array_t *array; 165: int total_size; 166: 167: /* Compute size of memory chunk needed to store the array */ 168: total_size = (nr_elements * sizeof(int)) + sizeof(rfc_array_t); 1.1.1.2 root 169: array = malloc(total_size); 170: assert(array); 1.1 root 171: memset(array,0,total_size); 172: array->nr_elements = nr_elements; 173: 174: /* Initialize hash table for Class Bitmaps */ 175: array->cbm_hash = hash_table_create(cbm_hash_f,cbm_cmp_f,CBM_HASH_SIZE); 1.1.1.2 root 176: assert(array->cbm_hash); 1.1 root 177: 178: /* Initialize table for converting ID to CBM */ 179: array->id2cbm = calloc(nr_elements,sizeof(cbm_array_t *)); 1.1.1.2 root 180: assert(array->id2cbm); 1.1 root 181: 182: return(array); 183: } 184: 185: /* Check an instruction with specified parameter */ 186: static void rfc_check_insn(insn_lookup_t *ilt,cbm_array_t *cbm, 187: ilt_check_cbk_t pcheck,int value) 188: { 189: void *p; 190: int i; 191: 192: for(i=0;i<ilt->nr_insn;i++) { 193: p = ilt->get_insn(i); 194: 195: if (pcheck(p,value)) 196: cbm_set_rule(cbm,i); 197: else 198: cbm_unset_rule(cbm,i); 199: } 200: } 201: 202: /* RFC Chunk preprocessing: phase 0 */ 203: static rfc_array_t *rfc_phase_0(insn_lookup_t *ilt,ilt_check_cbk_t pcheck) 204: { 205: rfc_eqclass_t *eqcl; 206: rfc_array_t *rfct; 207: cbm_array_t *bmp; 208: int i; 209: 210: /* allocate a temporary class bitmap */ 1.1.1.2 root 211: bmp = cbm_create(ilt); 212: assert(bmp); 1.1 root 213: 214: /* Allocate a new RFC array of 16-bits entries */ 1.1.1.2 root 215: rfct = rfc_alloc_array(RFC_ARRAY_MAXSIZE); 216: assert(rfct); 1.1 root 217: 218: for(i=0;i<RFC_ARRAY_MAXSIZE;i++) 219: { 220: /* determine all instructions that match this value */ 221: rfc_check_insn(ilt,bmp,pcheck,i); 222: 223: /* get equivalent class for this bitmap */ 1.1.1.2 root 224: eqcl = cbm_get_eqclass(rfct,bmp); 225: assert(eqcl); 1.1 root 226: 227: /* fill the RFC table */ 228: rfct->eqID[i] = eqcl->eqID; 229: } 230: 231: free(bmp); 232: return rfct; 233: } 234: 235: /* RFC Chunk preprocessing: phase j (j > 0) */ 236: static rfc_array_t *rfc_phase_j(insn_lookup_t *ilt,rfc_array_t *p0, 237: rfc_array_t *p1) 238: { 239: rfc_eqclass_t *eqcl; 240: rfc_array_t *rfct; 241: cbm_array_t *bmp; 242: int nr_elements; 243: int index = 0; 244: int i,j; 245: 246: /* allocate a temporary class bitmap */ 1.1.1.2 root 247: bmp = cbm_create(ilt); 248: assert(bmp); 1.1 root 249: 250: /* compute number of elements */ 251: nr_elements = p0->nr_eqid * p1->nr_eqid; 252: 253: /* allocate a new RFC array */ 1.1.1.2 root 254: rfct = rfc_alloc_array(nr_elements); 255: assert(rfct); 1.1 root 256: rfct->parent0 = p0; 257: rfct->parent1 = p1; 258: 259: /* make a cross product between p0 and p1 */ 260: for(i=0;i<p0->nr_eqid;i++) 261: for(j=0;j<p1->nr_eqid;j++) 262: { 263: /* compute bitwise AND */ 264: cbm_bitwise_and(bmp,p0->id2cbm[i],p1->id2cbm[j]); 265: 266: /* get equivalent class for this bitmap */ 1.1.1.2 root 267: eqcl = cbm_get_eqclass(rfct,bmp); 268: assert(eqcl); 1.1 root 269: 270: /* fill RFC table */ 271: rfct->eqID[index++] = eqcl->eqID; 272: } 273: 274: free(bmp); 275: return rfct; 276: } 277: 278: /* Compute RFC phase 0 */ 279: static void ilt_phase_0(insn_lookup_t *ilt,int idx,ilt_check_cbk_t pcheck) 280: { 281: rfc_array_t *rfct; 282: 1.1.1.2 root 283: rfct = rfc_phase_0(ilt,pcheck); 284: assert(rfct); 1.1 root 285: ilt->rfct[idx] = rfct; 286: } 287: 288: /* Compute RFC phase j */ 289: static void ilt_phase_j(insn_lookup_t *ilt,int p0,int p1,int res) 290: { 291: rfc_array_t *rfct; 292: 1.1.1.2 root 293: rfct = rfc_phase_j(ilt,ilt->rfct[p0],ilt->rfct[p1]); 294: assert(rfct); 1.1 root 295: ilt->rfct[res] = rfct; 296: } 297: 298: /* Postprocessing */ 299: static void ilt_postprocessing(insn_lookup_t *ilt) 300: { 301: rfc_array_t *rfct = ilt->rfct[2]; 302: int i; 303: 304: for(i=0;i<rfct->nr_elements;i++) 305: rfct->eqID[i] = cbm_first_match(ilt,rfct->id2cbm[rfct->eqID[i]]); 306: } 307: 308: /* Instruction lookup table compilation */ 309: static void ilt_compile(insn_lookup_t *ilt) 310: { 311: ilt_phase_0(ilt,0,ilt->chk_hi); 312: ilt_phase_0(ilt,1,ilt->chk_lo); 313: ilt_phase_j(ilt,0,1,2); 314: ilt_postprocessing(ilt); 315: } 316: 1.1.1.4 ! root 317: /* Dump an instruction lookup table */ ! 318: static void ilt_dump(insn_lookup_t *ilt) ! 319: { ! 320: rfc_array_t *rfct; ! 321: int i,j; ! 322: ! 323: printf("ILT %p: nr_insn=%d, cbm_size=%d\n",ilt,ilt->nr_insn,ilt->cbm_size); ! 324: ! 325: for(i=0;i<RFC_ARRAY_NUMBER;i++) { ! 326: rfct = ilt->rfct[i]; ! 327: ! 328: for(j=0;j<rfct->nr_elements;j++) ! 329: printf(" (0x%4.4x,0x%4.4x) = 0x%4.4x\n",i,j,rfct->eqID[j]); ! 330: } ! 331: } ! 332: ! 333: /* Write the specified RFC array to disk */ ! 334: static void ilt_store_rfct(FILE *fd,int id,rfc_array_t *rfct) ! 335: { ! 336: /* Store RFC array ID + number of elements */ ! 337: fwrite(&id,sizeof(id),1,fd); ! 338: fwrite(&rfct->nr_elements,sizeof(rfct->nr_elements),1,fd); ! 339: fwrite(&rfct->nr_eqid,sizeof(rfct->nr_eqid),1,fd); ! 340: ! 341: fwrite(rfct->eqID,rfct->nr_elements,sizeof(int),fd); ! 342: } ! 343: ! 344: /* Write the full instruction lookup table */ ! 345: static void ilt_store_table(FILE *fd,insn_lookup_t *ilt) ! 346: { ! 347: int i; ! 348: ! 349: for(i=0;i<RFC_ARRAY_NUMBER;i++) ! 350: if (ilt->rfct[i] != NULL) ! 351: ilt_store_rfct(fd,i,ilt->rfct[i]); ! 352: } ! 353: ! 354: /* Load an RFC array from disk */ ! 355: static int ilt_load_rfct(FILE *fd,insn_lookup_t *ilt) ! 356: { ! 357: u_int id,nr_elements,nr_eqid; ! 358: rfc_array_t *rfct; ! 359: size_t len; ! 360: ! 361: /* Read ID and number of elements */ ! 362: if ((fread(&id,sizeof(id),1,fd) != 1) || ! 363: (fread(&nr_elements,sizeof(nr_elements),1,fd) != 1) || ! 364: (fread(&nr_eqid,sizeof(nr_eqid),1,fd) != 1)) ! 365: return(-1); ! 366: ! 367: if ((id >= RFC_ARRAY_NUMBER) || (nr_elements > RFC_ARRAY_MAXSIZE)) ! 368: return(-1); ! 369: ! 370: /* Allocate the RFC array with the eqID table */ ! 371: len = sizeof(*rfct) + (nr_elements * sizeof(int)); ! 372: ! 373: if (!(rfct = malloc(len))) ! 374: return(-1); ! 375: ! 376: memset(rfct,0,sizeof(*rfct)); ! 377: rfct->nr_elements = nr_elements; ! 378: rfct->nr_eqid = nr_eqid; ! 379: ! 380: /* Read the equivalent ID array */ ! 381: fread(rfct->eqID,rfct->nr_elements,sizeof(int),fd); ! 382: ! 383: ilt->rfct[id] = rfct; ! 384: return(0); ! 385: } ! 386: ! 387: /* Check an instruction table loaded from disk */ ! 388: static int ilt_check_cached_table(insn_lookup_t *ilt) ! 389: { ! 390: int i; ! 391: ! 392: /* All arrays must have been loaded */ ! 393: for(i=0;i<RFC_ARRAY_NUMBER;i++) ! 394: if (!ilt->rfct[i]) ! 395: return(-1); ! 396: ! 397: return(0); ! 398: } ! 399: ! 400: /* Load a full instruction table from disk */ ! 401: static insn_lookup_t *ilt_load_table(FILE *fd) ! 402: { ! 403: insn_lookup_t *ilt; ! 404: ! 405: if (!(ilt = malloc(sizeof(*ilt)))) ! 406: return NULL; ! 407: ! 408: memset(ilt,0,sizeof(*ilt)); ! 409: ! 410: while(!feof(fd)) { ! 411: if (ilt_load_rfct(fd,ilt) == -1) ! 412: break; ! 413: } ! 414: ! 415: if (ilt_check_cached_table(ilt) == -1) ! 416: return NULL; ! 417: ! 418: return ilt; ! 419: } ! 420: ! 421: /* Build a filename for a cached ILT table on disk */ ! 422: static char *ilt_build_filename(char *table_name) ! 423: { ! 424: return(dyn_sprintf("ilt_%s_%s",sw_version_tag,table_name)); ! 425: } ! 426: ! 427: /* Try to load a cached ILT table from disk */ ! 428: static insn_lookup_t *ilt_cache_load(char *table_name) ! 429: { ! 430: insn_lookup_t *ilt; ! 431: char *filename; ! 432: FILE *fd; ! 433: ! 434: if (!(filename = ilt_build_filename(table_name))) ! 435: return NULL; ! 436: ! 437: if (!(fd = fopen(filename,"r"))) { ! 438: free(filename); ! 439: return NULL; ! 440: } ! 441: ! 442: ilt = ilt_load_table(fd); ! 443: fclose(fd); ! 444: return ilt; ! 445: } ! 446: ! 447: /* Store the specified ILT table on disk for future use (cache) */ ! 448: static int ilt_cache_store(char *table_name,insn_lookup_t *ilt) ! 449: { ! 450: char *filename; ! 451: FILE *fd; ! 452: ! 453: if (!(filename = ilt_build_filename(table_name))) ! 454: return(-1); ! 455: ! 456: if (!(fd = fopen(filename,"w"))) { ! 457: free(filename); ! 458: return(-1); ! 459: } ! 460: ! 461: ilt_store_table(fd,ilt); ! 462: fclose(fd); ! 463: return(0); ! 464: } ! 465: 1.1 root 466: /* Create an instruction lookup table */ 1.1.1.4 ! root 467: insn_lookup_t *ilt_create(char *table_name, ! 468: int nr_insn,ilt_get_insn_cbk_t get_insn, 1.1 root 469: ilt_check_cbk_t chk_lo,ilt_check_cbk_t chk_hi) 470: { 471: insn_lookup_t *ilt; 472: 1.1.1.4 ! root 473: /* Try to load a cached table from disk */ ! 474: if ((ilt = ilt_cache_load(table_name))) { ! 475: printf("ILT: loaded table \"%s\" from cache.\n",table_name); ! 476: return ilt; ! 477: } ! 478: ! 479: /* We have to build the full table... */ 1.1.1.2 root 480: ilt = malloc(sizeof(*ilt)); 481: assert(ilt); 1.1 root 482: memset(ilt,0,sizeof(*ilt)); 483: 484: ilt->cbm_size = normalize_size(nr_insn,CBM_SIZE,CBM_SHIFT); 485: ilt->nr_insn = nr_insn; 486: ilt->get_insn = get_insn; 487: ilt->chk_lo = chk_lo; 488: ilt->chk_hi = chk_hi; 489: 1.1.1.4 ! root 490: /* Compile the instruction opcodes */ 1.1 root 491: ilt_compile(ilt); 1.1.1.4 ! root 492: ! 493: /* Store the result on disk for future exec */ ! 494: ilt_cache_store(table_name,ilt); 1.1 root 495: return(ilt); 496: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.