/[dynamips]/trunk/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

Annotation of /trunk/insn_lookup.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 11 - (hide annotations)
Sat Oct 6 16:33:40 2007 UTC (16 years, 5 months ago) by dpavlin
Original Path: upstream/dynamips-0.2.8-RC1/insn_lookup.c
File MIME type: text/plain
File size: 12218 byte(s)
dynamips-0.2.8-RC1

1 dpavlin 1 /*
2 dpavlin 7 * Cisco router simulation platform.
3 dpavlin 1 * 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 dpavlin 8 #include "dynamips.h"
21 dpavlin 1
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 dpavlin 8 /* Dump an instruction lookup table */
318 dpavlin 11 static int ilt_dump(char *table_name,insn_lookup_t *ilt)
319 dpavlin 8 {
320     rfc_array_t *rfct;
321 dpavlin 11 char *filename;
322     FILE *fd;
323 dpavlin 8 int i,j;
324    
325 dpavlin 11 filename = dyn_sprintf("ilt_dump_%s_%s.txt",sw_version_tag,table_name);
326     assert(filename != NULL);
327 dpavlin 8
328 dpavlin 11 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);
333    
334 dpavlin 8 for(i=0;i<RFC_ARRAY_NUMBER;i++) {
335     rfct = ilt->rfct[i];
336    
337 dpavlin 11 fprintf(fd,"RFCT %d: nr_elements=%d, nr_eqid=%d\n",
338     i,rfct->nr_elements,rfct->nr_eqid);
339    
340 dpavlin 8 for(j=0;j<rfct->nr_elements;j++)
341 dpavlin 11 fprintf(fd," (0x%4.4x,0x%4.4x) = 0x%4.4x\n",i,j,rfct->eqID[j]);
342 dpavlin 8 }
343 dpavlin 11
344     fclose(fd);
345     return(0);
346 dpavlin 8 }
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    
356 dpavlin 11 fwrite(rfct->eqID,sizeof(int),rfct->nr_elements,fd);
357 dpavlin 8 }
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);
381 dpavlin 11
382 dpavlin 8 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;
394 dpavlin 11
395 dpavlin 8 /* Read the equivalent ID array */
396 dpavlin 11 if (fread(rfct->eqID,sizeof(int),nr_elements,fd) != nr_elements) {
397     free(rfct);
398     return(-1);
399     }
400 dpavlin 8
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;
422 dpavlin 11 int i;
423    
424 dpavlin 8 if (!(ilt = malloc(sizeof(*ilt))))
425     return NULL;
426    
427     memset(ilt,0,sizeof(*ilt));
428 dpavlin 11 fseek(fd,0,SEEK_SET);
429 dpavlin 8
430 dpavlin 11 for(i=0;i<RFC_ARRAY_NUMBER;i++) {
431 dpavlin 8 if (ilt_load_rfct(fd,ilt) == -1)
432 dpavlin 11 return NULL;
433 dpavlin 8 }
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    
457 dpavlin 11 if (!(fd = fopen(filename,"rb"))) {
458 dpavlin 8 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    
476 dpavlin 11 if (!(fd = fopen(filename,"wb"))) {
477 dpavlin 8 free(filename);
478     return(-1);
479     }
480    
481     ilt_store_table(fd,ilt);
482     fclose(fd);
483 dpavlin 11 free(filename);
484 dpavlin 8 return(0);
485     }
486    
487 dpavlin 1 /* Create an instruction lookup table */
488 dpavlin 8 insn_lookup_t *ilt_create(char *table_name,
489     int nr_insn,ilt_get_insn_cbk_t get_insn,
490 dpavlin 1 ilt_check_cbk_t chk_lo,ilt_check_cbk_t chk_hi)
491     {
492     insn_lookup_t *ilt;
493    
494 dpavlin 8 /* 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... */
501 dpavlin 1 ilt = malloc(sizeof(*ilt));
502     assert(ilt);
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    
511 dpavlin 8 /* Compile the instruction opcodes */
512 dpavlin 1 ilt_compile(ilt);
513 dpavlin 8
514     /* Store the result on disk for future exec */
515     ilt_cache_store(table_name,ilt);
516 dpavlin 1 return(ilt);
517     }

  ViewVC Help
Powered by ViewVC 1.1.26