/[dynamips]/upstream/dynamips-0.2.7-RC2/insn_lookup.c
This is repository of my old source code which isn't updated any more. Go to git.rot13.org for current projects!
ViewVC logotype

Contents of /upstream/dynamips-0.2.7-RC2/insn_lookup.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 8 - (show annotations)
Sat Oct 6 16:24:54 2007 UTC (12 years, 1 month ago) by dpavlin
File MIME type: text/plain
File size: 11698 byte(s)
dynamips-0.2.7-RC2

1 /*
2 * Cisco router simulation platform.
3 * Copyright (c) 2006 Christophe Fillot (cf@utc.fr)
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 #include "dynamips.h"
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 */
106 array = malloc(size);
107 assert(array);
108
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
120 array = malloc(size);
121 assert(array);
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 */
139 bmp = cbm_duplicate(cbm);
140 assert(bmp);
141
142 /* CBM is not already known */
143 eqcl = malloc(sizeof(rfc_eqclass_t));
144 assert(eqcl);
145
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 */
154 if (hash_table_insert(rfct->cbm_hash,bmp,eqcl) == -1)
155 return NULL;
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);
169 array = malloc(total_size);
170 assert(array);
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);
176 assert(array->cbm_hash);
177
178 /* Initialize table for converting ID to CBM */
179 array->id2cbm = calloc(nr_elements,sizeof(cbm_array_t *));
180 assert(array->id2cbm);
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 */
211 bmp = cbm_create(ilt);
212 assert(bmp);
213
214 /* Allocate a new RFC array of 16-bits entries */
215 rfct = rfc_alloc_array(RFC_ARRAY_MAXSIZE);
216 assert(rfct);
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 */
224 eqcl = cbm_get_eqclass(rfct,bmp);
225 assert(eqcl);
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 */
247 bmp = cbm_create(ilt);
248 assert(bmp);
249
250 /* compute number of elements */
251 nr_elements = p0->nr_eqid * p1->nr_eqid;
252
253 /* allocate a new RFC array */
254 rfct = rfc_alloc_array(nr_elements);
255 assert(rfct);
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 */
267 eqcl = cbm_get_eqclass(rfct,bmp);
268 assert(eqcl);
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
283 rfct = rfc_phase_0(ilt,pcheck);
284 assert(rfct);
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
293 rfct = rfc_phase_j(ilt,ilt->rfct[p0],ilt->rfct[p1]);
294 assert(rfct);
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
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
466 /* Create an instruction lookup table */
467 insn_lookup_t *ilt_create(char *table_name,
468 int nr_insn,ilt_get_insn_cbk_t get_insn,
469 ilt_check_cbk_t chk_lo,ilt_check_cbk_t chk_hi)
470 {
471 insn_lookup_t *ilt;
472
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... */
480 ilt = malloc(sizeof(*ilt));
481 assert(ilt);
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
490 /* Compile the instruction opcodes */
491 ilt_compile(ilt);
492
493 /* Store the result on disk for future exec */
494 ilt_cache_store(table_name,ilt);
495 return(ilt);
496 }

  ViewVC Help
Powered by ViewVC 1.1.26