![[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: /*
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 */
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.