1 |
dpavlin |
1 |
/* |
2 |
|
|
* Cisco 7200 (Predator) 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 |
|
|
|
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 |
|
|
array = malloc(size); |
106 |
|
|
assert(array); |
107 |
|
|
|
108 |
|
|
memset(array,0,size); |
109 |
|
|
array->nr_entries = ilt->cbm_size; |
110 |
|
|
return array; |
111 |
|
|
} |
112 |
|
|
|
113 |
|
|
/* Duplicate a class bitmap */ |
114 |
|
|
static cbm_array_t *cbm_duplicate(cbm_array_t *cbm) |
115 |
|
|
{ |
116 |
|
|
int size = CBM_CSIZE(cbm->nr_entries); |
117 |
|
|
cbm_array_t *array; |
118 |
|
|
|
119 |
|
|
array = malloc(size); |
120 |
|
|
assert(array); |
121 |
|
|
memcpy(array,cbm,size); |
122 |
|
|
return array; |
123 |
|
|
} |
124 |
|
|
|
125 |
|
|
/* |
126 |
|
|
* Get equivalent class corresponding to a class bitmap. Create eqclass |
127 |
|
|
* structure if needed (CBM not previously seen). |
128 |
|
|
*/ |
129 |
|
|
static rfc_eqclass_t *cbm_get_eqclass(rfc_array_t *rfct,cbm_array_t *cbm) |
130 |
|
|
{ |
131 |
|
|
rfc_eqclass_t *eqcl; |
132 |
|
|
cbm_array_t *bmp; |
133 |
|
|
|
134 |
|
|
/* Lookup for CBM into hash table */ |
135 |
|
|
if ((eqcl = hash_table_lookup(rfct->cbm_hash,cbm)) == NULL) |
136 |
|
|
{ |
137 |
|
|
/* Duplicate CBM */ |
138 |
|
|
bmp = cbm_duplicate(cbm); |
139 |
|
|
assert(bmp); |
140 |
|
|
|
141 |
|
|
/* CBM is not already known */ |
142 |
|
|
eqcl = malloc(sizeof(rfc_eqclass_t)); |
143 |
|
|
assert(eqcl); |
144 |
|
|
|
145 |
|
|
assert(rfct->nr_eqid < rfct->nr_elements); |
146 |
|
|
|
147 |
|
|
/* Get a new equivalent ID */ |
148 |
|
|
eqcl->eqID = rfct->nr_eqid++; |
149 |
|
|
eqcl->cbm = bmp; |
150 |
|
|
rfct->id2cbm[eqcl->eqID] = bmp; |
151 |
|
|
|
152 |
|
|
/* Insert it in hash table */ |
153 |
|
|
if (hash_table_insert(rfct->cbm_hash,bmp,eqcl) == -1) |
154 |
|
|
return NULL; |
155 |
|
|
} |
156 |
|
|
|
157 |
|
|
return eqcl; |
158 |
|
|
} |
159 |
|
|
|
160 |
|
|
/* Allocate an array for Recursive Flow Classification */ |
161 |
|
|
static rfc_array_t *rfc_alloc_array(int nr_elements) |
162 |
|
|
{ |
163 |
|
|
rfc_array_t *array; |
164 |
|
|
int total_size; |
165 |
|
|
|
166 |
|
|
/* Compute size of memory chunk needed to store the array */ |
167 |
|
|
total_size = (nr_elements * sizeof(int)) + sizeof(rfc_array_t); |
168 |
|
|
array = malloc(total_size); |
169 |
|
|
assert(array); |
170 |
|
|
memset(array,0,total_size); |
171 |
|
|
array->nr_elements = nr_elements; |
172 |
|
|
|
173 |
|
|
/* Initialize hash table for Class Bitmaps */ |
174 |
|
|
array->cbm_hash = hash_table_create(cbm_hash_f,cbm_cmp_f,CBM_HASH_SIZE); |
175 |
|
|
assert(array->cbm_hash); |
176 |
|
|
|
177 |
|
|
/* Initialize table for converting ID to CBM */ |
178 |
|
|
array->id2cbm = calloc(nr_elements,sizeof(cbm_array_t *)); |
179 |
|
|
assert(array->id2cbm); |
180 |
|
|
|
181 |
|
|
return(array); |
182 |
|
|
} |
183 |
|
|
|
184 |
|
|
/* Check an instruction with specified parameter */ |
185 |
|
|
static void rfc_check_insn(insn_lookup_t *ilt,cbm_array_t *cbm, |
186 |
|
|
ilt_check_cbk_t pcheck,int value) |
187 |
|
|
{ |
188 |
|
|
void *p; |
189 |
|
|
int i; |
190 |
|
|
|
191 |
|
|
for(i=0;i<ilt->nr_insn;i++) { |
192 |
|
|
p = ilt->get_insn(i); |
193 |
|
|
|
194 |
|
|
if (pcheck(p,value)) |
195 |
|
|
cbm_set_rule(cbm,i); |
196 |
|
|
else |
197 |
|
|
cbm_unset_rule(cbm,i); |
198 |
|
|
} |
199 |
|
|
} |
200 |
|
|
|
201 |
|
|
/* RFC Chunk preprocessing: phase 0 */ |
202 |
|
|
static rfc_array_t *rfc_phase_0(insn_lookup_t *ilt,ilt_check_cbk_t pcheck) |
203 |
|
|
{ |
204 |
|
|
rfc_eqclass_t *eqcl; |
205 |
|
|
rfc_array_t *rfct; |
206 |
|
|
cbm_array_t *bmp; |
207 |
|
|
int i; |
208 |
|
|
|
209 |
|
|
/* allocate a temporary class bitmap */ |
210 |
|
|
bmp = cbm_create(ilt); |
211 |
|
|
assert(bmp); |
212 |
|
|
|
213 |
|
|
/* Allocate a new RFC array of 16-bits entries */ |
214 |
|
|
rfct = rfc_alloc_array(RFC_ARRAY_MAXSIZE); |
215 |
|
|
assert(rfct); |
216 |
|
|
|
217 |
|
|
for(i=0;i<RFC_ARRAY_MAXSIZE;i++) |
218 |
|
|
{ |
219 |
|
|
/* determine all instructions that match this value */ |
220 |
|
|
rfc_check_insn(ilt,bmp,pcheck,i); |
221 |
|
|
|
222 |
|
|
/* get equivalent class for this bitmap */ |
223 |
|
|
eqcl = cbm_get_eqclass(rfct,bmp); |
224 |
|
|
assert(eqcl); |
225 |
|
|
|
226 |
|
|
/* fill the RFC table */ |
227 |
|
|
rfct->eqID[i] = eqcl->eqID; |
228 |
|
|
} |
229 |
|
|
|
230 |
|
|
free(bmp); |
231 |
|
|
return rfct; |
232 |
|
|
} |
233 |
|
|
|
234 |
|
|
/* RFC Chunk preprocessing: phase j (j > 0) */ |
235 |
|
|
static rfc_array_t *rfc_phase_j(insn_lookup_t *ilt,rfc_array_t *p0, |
236 |
|
|
rfc_array_t *p1) |
237 |
|
|
{ |
238 |
|
|
rfc_eqclass_t *eqcl; |
239 |
|
|
rfc_array_t *rfct; |
240 |
|
|
cbm_array_t *bmp; |
241 |
|
|
int nr_elements; |
242 |
|
|
int index = 0; |
243 |
|
|
int i,j; |
244 |
|
|
|
245 |
|
|
/* allocate a temporary class bitmap */ |
246 |
|
|
bmp = cbm_create(ilt); |
247 |
|
|
assert(bmp); |
248 |
|
|
|
249 |
|
|
/* compute number of elements */ |
250 |
|
|
nr_elements = p0->nr_eqid * p1->nr_eqid; |
251 |
|
|
|
252 |
|
|
/* allocate a new RFC array */ |
253 |
|
|
rfct = rfc_alloc_array(nr_elements); |
254 |
|
|
assert(rfct); |
255 |
|
|
rfct->parent0 = p0; |
256 |
|
|
rfct->parent1 = p1; |
257 |
|
|
|
258 |
|
|
/* make a cross product between p0 and p1 */ |
259 |
|
|
for(i=0;i<p0->nr_eqid;i++) |
260 |
|
|
for(j=0;j<p1->nr_eqid;j++) |
261 |
|
|
{ |
262 |
|
|
/* compute bitwise AND */ |
263 |
|
|
cbm_bitwise_and(bmp,p0->id2cbm[i],p1->id2cbm[j]); |
264 |
|
|
|
265 |
|
|
/* get equivalent class for this bitmap */ |
266 |
|
|
eqcl = cbm_get_eqclass(rfct,bmp); |
267 |
|
|
assert(eqcl); |
268 |
|
|
|
269 |
|
|
/* fill RFC table */ |
270 |
|
|
rfct->eqID[index++] = eqcl->eqID; |
271 |
|
|
} |
272 |
|
|
|
273 |
|
|
free(bmp); |
274 |
|
|
return rfct; |
275 |
|
|
} |
276 |
|
|
|
277 |
|
|
/* Compute RFC phase 0 */ |
278 |
|
|
static void ilt_phase_0(insn_lookup_t *ilt,int idx,ilt_check_cbk_t pcheck) |
279 |
|
|
{ |
280 |
|
|
rfc_array_t *rfct; |
281 |
|
|
|
282 |
|
|
rfct = rfc_phase_0(ilt,pcheck); |
283 |
|
|
assert(rfct); |
284 |
|
|
ilt->rfct[idx] = rfct; |
285 |
|
|
} |
286 |
|
|
|
287 |
|
|
/* Compute RFC phase j */ |
288 |
|
|
static void ilt_phase_j(insn_lookup_t *ilt,int p0,int p1,int res) |
289 |
|
|
{ |
290 |
|
|
rfc_array_t *rfct; |
291 |
|
|
|
292 |
|
|
rfct = rfc_phase_j(ilt,ilt->rfct[p0],ilt->rfct[p1]); |
293 |
|
|
assert(rfct); |
294 |
|
|
ilt->rfct[res] = rfct; |
295 |
|
|
} |
296 |
|
|
|
297 |
|
|
/* Postprocessing */ |
298 |
|
|
static void ilt_postprocessing(insn_lookup_t *ilt) |
299 |
|
|
{ |
300 |
|
|
rfc_array_t *rfct = ilt->rfct[2]; |
301 |
|
|
int i; |
302 |
|
|
|
303 |
|
|
for(i=0;i<rfct->nr_elements;i++) |
304 |
|
|
rfct->eqID[i] = cbm_first_match(ilt,rfct->id2cbm[rfct->eqID[i]]); |
305 |
|
|
} |
306 |
|
|
|
307 |
|
|
/* Instruction lookup table compilation */ |
308 |
|
|
static void ilt_compile(insn_lookup_t *ilt) |
309 |
|
|
{ |
310 |
|
|
ilt_phase_0(ilt,0,ilt->chk_hi); |
311 |
|
|
ilt_phase_0(ilt,1,ilt->chk_lo); |
312 |
|
|
ilt_phase_j(ilt,0,1,2); |
313 |
|
|
ilt_postprocessing(ilt); |
314 |
|
|
} |
315 |
|
|
|
316 |
|
|
/* Create an instruction lookup table */ |
317 |
|
|
insn_lookup_t *ilt_create(int nr_insn,ilt_get_insn_cbk_t get_insn, |
318 |
|
|
ilt_check_cbk_t chk_lo,ilt_check_cbk_t chk_hi) |
319 |
|
|
{ |
320 |
|
|
insn_lookup_t *ilt; |
321 |
|
|
|
322 |
|
|
ilt = malloc(sizeof(*ilt)); |
323 |
|
|
assert(ilt); |
324 |
|
|
memset(ilt,0,sizeof(*ilt)); |
325 |
|
|
|
326 |
|
|
ilt->cbm_size = normalize_size(nr_insn,CBM_SIZE,CBM_SHIFT); |
327 |
|
|
ilt->nr_insn = nr_insn; |
328 |
|
|
ilt->get_insn = get_insn; |
329 |
|
|
ilt->chk_lo = chk_lo; |
330 |
|
|
ilt->chk_hi = chk_hi; |
331 |
|
|
|
332 |
|
|
ilt_compile(ilt); |
333 |
|
|
return(ilt); |
334 |
|
|
} |