/[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

Contents of /trunk/insn_lookup.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 12 - (show annotations)
Sat Oct 6 16:45:40 2007 UTC (11 years, 11 months ago) by dpavlin
File MIME type: text/plain
File size: 12218 byte(s)
make working copy

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

  ViewVC Help
Powered by ViewVC 1.1.26