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 |
} |