![[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 */ 1.1.1.5 ! root 318: static int ilt_dump(char *table_name,insn_lookup_t *ilt) 1.1.1.4 root 319: { 320: rfc_array_t *rfct; 1.1.1.5 ! root 321: char *filename; ! 322: FILE *fd; 1.1.1.4 root 323: int i,j; 324: 1.1.1.5 ! root 325: filename = dyn_sprintf("ilt_dump_%s_%s.txt",sw_version_tag,table_name); ! 326: assert(filename != NULL); ! 327: ! 328: fd = fopen(filename,"w"); ! 329: assert(fd != NULL); ! 330: ! 331: fprintf(fd,"ILT %p: nr_insn=%d, cbm_size=%d\n", ! 332: ilt,ilt->nr_insn,ilt->cbm_size); 1.1.1.4 root 333: 334: for(i=0;i<RFC_ARRAY_NUMBER;i++) { 335: rfct = ilt->rfct[i]; 336: 1.1.1.5 ! root 337: fprintf(fd,"RFCT %d: nr_elements=%d, nr_eqid=%d\n", ! 338: i,rfct->nr_elements,rfct->nr_eqid); ! 339: 1.1.1.4 root 340: for(j=0;j<rfct->nr_elements;j++) 1.1.1.5 ! root 341: fprintf(fd," (0x%4.4x,0x%4.4x) = 0x%4.4x\n",i,j,rfct->eqID[j]); 1.1.1.4 root 342: } 1.1.1.5 ! root 343: ! 344: fclose(fd); ! 345: return(0); 1.1.1.4 root 346: } 347: 348: /* Write the specified RFC array to disk */ 349: static void ilt_store_rfct(FILE *fd,int id,rfc_array_t *rfct) 350: { 351: /* Store RFC array ID + number of elements */ 352: fwrite(&id,sizeof(id),1,fd); 353: fwrite(&rfct->nr_elements,sizeof(rfct->nr_elements),1,fd); 354: fwrite(&rfct->nr_eqid,sizeof(rfct->nr_eqid),1,fd); 355: 1.1.1.5 ! root 356: fwrite(rfct->eqID,sizeof(int),rfct->nr_elements,fd); 1.1.1.4 root 357: } 358: 359: /* Write the full instruction lookup table */ 360: static void ilt_store_table(FILE *fd,insn_lookup_t *ilt) 361: { 362: int i; 363: 364: for(i=0;i<RFC_ARRAY_NUMBER;i++) 365: if (ilt->rfct[i] != NULL) 366: ilt_store_rfct(fd,i,ilt->rfct[i]); 367: } 368: 369: /* Load an RFC array from disk */ 370: static int ilt_load_rfct(FILE *fd,insn_lookup_t *ilt) 371: { 372: u_int id,nr_elements,nr_eqid; 373: rfc_array_t *rfct; 374: size_t len; 375: 376: /* Read ID and number of elements */ 377: if ((fread(&id,sizeof(id),1,fd) != 1) || 378: (fread(&nr_elements,sizeof(nr_elements),1,fd) != 1) || 379: (fread(&nr_eqid,sizeof(nr_eqid),1,fd) != 1)) 380: return(-1); 1.1.1.5 ! root 381: 1.1.1.4 root 382: if ((id >= RFC_ARRAY_NUMBER) || (nr_elements > RFC_ARRAY_MAXSIZE)) 383: return(-1); 384: 385: /* Allocate the RFC array with the eqID table */ 386: len = sizeof(*rfct) + (nr_elements * sizeof(int)); 387: 388: if (!(rfct = malloc(len))) 389: return(-1); 390: 391: memset(rfct,0,sizeof(*rfct)); 392: rfct->nr_elements = nr_elements; 393: rfct->nr_eqid = nr_eqid; 1.1.1.5 ! root 394: 1.1.1.4 root 395: /* Read the equivalent ID array */ 1.1.1.5 ! root 396: if (fread(rfct->eqID,sizeof(int),nr_elements,fd) != nr_elements) { ! 397: free(rfct); ! 398: return(-1); ! 399: } 1.1.1.4 root 400: 401: ilt->rfct[id] = rfct; 402: return(0); 403: } 404: 405: /* Check an instruction table loaded from disk */ 406: static int ilt_check_cached_table(insn_lookup_t *ilt) 407: { 408: int i; 409: 410: /* All arrays must have been loaded */ 411: for(i=0;i<RFC_ARRAY_NUMBER;i++) 412: if (!ilt->rfct[i]) 413: return(-1); 414: 415: return(0); 416: } 417: 418: /* Load a full instruction table from disk */ 419: static insn_lookup_t *ilt_load_table(FILE *fd) 420: { 421: insn_lookup_t *ilt; 1.1.1.5 ! root 422: int i; ! 423: 1.1.1.4 root 424: if (!(ilt = malloc(sizeof(*ilt)))) 425: return NULL; 426: 427: memset(ilt,0,sizeof(*ilt)); 1.1.1.5 ! root 428: fseek(fd,0,SEEK_SET); 1.1.1.4 root 429: 1.1.1.5 ! root 430: for(i=0;i<RFC_ARRAY_NUMBER;i++) { 1.1.1.4 root 431: if (ilt_load_rfct(fd,ilt) == -1) 1.1.1.5 ! root 432: return NULL; 1.1.1.4 root 433: } 434: 435: if (ilt_check_cached_table(ilt) == -1) 436: return NULL; 437: 438: return ilt; 439: } 440: 441: /* Build a filename for a cached ILT table on disk */ 442: static char *ilt_build_filename(char *table_name) 443: { 444: return(dyn_sprintf("ilt_%s_%s",sw_version_tag,table_name)); 445: } 446: 447: /* Try to load a cached ILT table from disk */ 448: static insn_lookup_t *ilt_cache_load(char *table_name) 449: { 450: insn_lookup_t *ilt; 451: char *filename; 452: FILE *fd; 453: 454: if (!(filename = ilt_build_filename(table_name))) 455: return NULL; 456: 1.1.1.5 ! root 457: if (!(fd = fopen(filename,"rb"))) { 1.1.1.4 root 458: free(filename); 459: return NULL; 460: } 461: 462: ilt = ilt_load_table(fd); 463: fclose(fd); 464: return ilt; 465: } 466: 467: /* Store the specified ILT table on disk for future use (cache) */ 468: static int ilt_cache_store(char *table_name,insn_lookup_t *ilt) 469: { 470: char *filename; 471: FILE *fd; 472: 473: if (!(filename = ilt_build_filename(table_name))) 474: return(-1); 475: 1.1.1.5 ! root 476: if (!(fd = fopen(filename,"wb"))) { 1.1.1.4 root 477: free(filename); 478: return(-1); 479: } 480: 481: ilt_store_table(fd,ilt); 482: fclose(fd); 1.1.1.5 ! root 483: free(filename); 1.1.1.4 root 484: return(0); 485: } 486: 1.1 root 487: /* Create an instruction lookup table */ 1.1.1.4 root 488: insn_lookup_t *ilt_create(char *table_name, 489: int nr_insn,ilt_get_insn_cbk_t get_insn, 1.1 root 490: ilt_check_cbk_t chk_lo,ilt_check_cbk_t chk_hi) 491: { 492: insn_lookup_t *ilt; 493: 1.1.1.4 root 494: /* Try to load a cached table from disk */ 495: if ((ilt = ilt_cache_load(table_name))) { 496: printf("ILT: loaded table \"%s\" from cache.\n",table_name); 497: return ilt; 498: } 499: 500: /* We have to build the full table... */ 1.1.1.2 root 501: ilt = malloc(sizeof(*ilt)); 502: assert(ilt); 1.1 root 503: memset(ilt,0,sizeof(*ilt)); 504: 505: ilt->cbm_size = normalize_size(nr_insn,CBM_SIZE,CBM_SHIFT); 506: ilt->nr_insn = nr_insn; 507: ilt->get_insn = get_insn; 508: ilt->chk_lo = chk_lo; 509: ilt->chk_hi = chk_hi; 510: 1.1.1.4 root 511: /* Compile the instruction opcodes */ 1.1 root 512: ilt_compile(ilt); 1.1.1.4 root 513: 514: /* Store the result on disk for future exec */ 515: ilt_cache_store(table_name,ilt); 1.1 root 516: return(ilt); 517: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.