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