Print this page
new smatch
Split |
Close |
Expand all |
Collapse all |
--- old/usr/src/tools/smatch/src/smatch_bits.c
+++ new/usr/src/tools/smatch/src/smatch_bits.c
1 1 /*
2 2 * Copyright (C) 2015 Oracle.
3 3 *
4 4 * This program is free software; you can redistribute it and/or
5 5 * modify it under the terms of the GNU General Public License
6 6 * as published by the Free Software Foundation; either version 2
7 7 * of the License, or (at your option) any later version.
8 8 *
9 9 * This program is distributed in the hope that it will be useful,
10 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 12 * GNU General Public License for more details.
13 13 *
14 14 * You should have received a copy of the GNU General Public License
15 15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16 16 */
17 17
18 18 /*
19 19 * This is to track when variables are masked away.
20 20 *
21 21 */
22 22
23 23 #include "smatch.h"
24 24 #include "smatch_extra.h"
25 25 #include "smatch_slist.h"
26 26
27 27 static int my_id;
28 28
29 29 static const struct bit_info unknown_bit_info = {
30 30 .possible = -1ULL,
31 31 };
32 32
33 33 ALLOCATOR(bit_info, "bit data");
34 34 static struct bit_info *alloc_bit_info(unsigned long long set, unsigned long long possible)
35 35 {
36 36 struct bit_info *bit_info = __alloc_bit_info(0);
37 37
38 38 bit_info->set = set;
39 39 bit_info->possible = possible;
40 40
41 41 return bit_info;
42 42 }
43 43
44 44 static struct smatch_state *alloc_bstate(unsigned long long set, unsigned long long possible)
45 45 {
46 46 struct smatch_state *state;
↓ open down ↓ |
46 lines elided |
↑ open up ↑ |
47 47 char buf[64];
48 48
49 49 state = __alloc_smatch_state(0);
50 50 snprintf(buf, sizeof(buf), "0x%llx + 0x%llx", set, possible);
51 51 state->name = alloc_sname(buf);
52 52 state->data = alloc_bit_info(set, possible);
53 53
54 54 return state;
55 55 }
56 56
57 -static struct bit_info *rl_to_binfo(struct range_list *rl)
57 +struct bit_info *rl_to_binfo(struct range_list *rl)
58 58 {
59 59 struct bit_info *ret = __alloc_bit_info(0);
60 60 sval_t sval;
61 61
62 62 if (rl_to_sval(rl, &sval)) {
63 63 ret->set = sval.uvalue;
64 64 ret->possible = sval.uvalue;
65 65
66 66 return ret;
67 67 }
68 68
69 69 ret->set = 0;
70 70 ret->possible = sval_fls_mask(rl_max(rl));
71 71 // FIXME: what about negatives?
72 72
73 73 return ret;
74 74 }
75 75
76 76 static int is_unknown_binfo(struct symbol *type, struct bit_info *binfo)
77 77 {
78 78 if (!type)
79 79 type = &ullong_ctype;
80 80
81 81 if (binfo->set != 0)
82 82 return 0;
83 83 if (binfo->possible < (-1ULL >> (64 - type_bits(type))))
84 84 return 0;
85 85
86 86 return 1;
87 87 }
88 88
89 89 static struct smatch_state *unmatched_state(struct sm_state *sm)
90 90 {
91 91 struct smatch_state *estate;
92 92 struct symbol *type;
93 93 unsigned long long possible;
94 94 struct bit_info *p;
95 95
96 96 estate = get_state(SMATCH_EXTRA, sm->name, sm->sym);
97 97 if (estate_rl(estate)) {
98 98 p = rl_to_binfo(estate_rl(estate));
99 99 return alloc_bstate(p->set, p->possible);
100 100 }
101 101
102 102 type = estate_type(estate);
103 103 if (!type)
104 104 return alloc_bstate(0, -1ULL);
105 105
106 106 if (type_bits(type) == 64)
107 107 possible = -1ULL;
108 108 else
109 109 possible = (1ULL << type_bits(type)) - 1;
110 110
111 111 return alloc_bstate(0, possible);
112 112 }
113 113
114 114 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
115 115 {
116 116 // FIXME: we really need to store the type
117 117
118 118 set_state(my_id, sm->name, sm->sym, alloc_bstate(0, -1ULL));
119 119 }
120 120
121 121 static int binfo_equiv(struct bit_info *one, struct bit_info *two)
122 122 {
123 123 if (one->set == two->set &&
124 124 one->possible == two->possible)
125 125 return 1;
126 126 return 0;
127 127 }
128 128
129 129 static struct smatch_state *merge_bstates(struct smatch_state *one_state, struct smatch_state *two_state)
130 130 {
131 131 struct bit_info *one, *two;
132 132
133 133 one = one_state->data;
134 134 two = two_state->data;
135 135
136 136 if (binfo_equiv(one, two))
137 137 return one_state;
138 138
139 139 return alloc_bstate(one->set & two->set, one->possible | two->possible);
140 140 }
141 141
142 142 /*
143 143 * The combine_bit_info() takes two bit_infos and takes creates the most
144 144 * accurate picture we can assuming both are true. Or it returns unknown if
145 145 * the information is logically impossible.
146 146 *
147 147 * Which means that it takes the | of the ->set bits and the & of the possibly
148 148 * set bits, which is the opposite of what merge_bstates() does.
149 149 *
150 150 */
151 151 static struct bit_info *combine_bit_info(struct bit_info *one, struct bit_info *two)
152 152 {
153 153 struct bit_info *ret = __alloc_bit_info(0);
154 154
155 155 if ((one->set & two->possible) != one->set)
156 156 return alloc_bit_info(0, -1ULL);
157 157 if ((two->set & one->possible) != two->set)
158 158 return alloc_bit_info(0, -1ULL);
159 159
160 160 ret->set = one->set | two->set;
161 161 ret->possible = one->possible & two->possible;
162 162
163 163 return ret;
164 164 }
165 165
166 166 static struct bit_info *binfo_AND(struct bit_info *left, struct bit_info *right)
167 167 {
168 168 unsigned long long set = 0;
169 169 unsigned long long possible = -1ULL;
170 170
171 171 if (!left && !right) {
172 172 /* nothing */
173 173 } else if (!left) {
174 174 possible = right->possible;
175 175 } else if (!right) {
176 176 possible = left->possible;
177 177 } else {
178 178 set = left->set & right->set;
179 179 possible = left->possible & right->possible;
180 180 }
181 181
182 182 return alloc_bit_info(set, possible);
183 183 }
184 184
185 185 static struct bit_info *binfo_OR(struct bit_info *left, struct bit_info *right)
186 186 {
187 187 unsigned long long set = 0;
188 188 unsigned long long possible = -1ULL;
189 189
190 190 if (!left && !right) {
191 191 /* nothing */
192 192 } else if (!left) {
193 193 set = right->set;
194 194 } else if (!right) {
195 195 set = left->set;
196 196 } else {
197 197 set = left->set | right->set;
198 198 possible = left->possible | right->possible;
199 199 }
200 200
201 201 return alloc_bit_info(set, possible);
202 202 }
203 203
204 204 struct bit_info *get_bit_info(struct expression *expr)
205 205 {
206 206 struct range_list *rl;
207 207 struct smatch_state *bstate;
208 208 struct bit_info tmp;
209 209 struct bit_info *extra_info;
210 210 struct bit_info *bit_info;
211 211 sval_t known;
212 212
213 213 expr = strip_parens(expr);
214 214
215 215 if (get_implied_value(expr, &known))
216 216 return alloc_bit_info(known.value, known.value);
217 217
218 218 if (expr->type == EXPR_BINOP) {
219 219 if (expr->op == '&')
220 220 return binfo_AND(get_bit_info(expr->left),
221 221 get_bit_info(expr->right));
222 222 if (expr->op == '|')
223 223 return binfo_OR(get_bit_info(expr->left),
224 224 get_bit_info(expr->right));
225 225 }
226 226
227 227 if (get_implied_rl(expr, &rl))
228 228 extra_info = rl_to_binfo(rl);
229 229 else {
230 230 struct symbol *type;
231 231
232 232 tmp = unknown_bit_info;
233 233 extra_info = &tmp;
234 234
235 235 type = get_type(expr);
236 236 if (!type)
237 237 type = &ullong_ctype;
238 238 if (type_bits(type) == 64)
239 239 extra_info->possible = -1ULL;
240 240 else
241 241 extra_info->possible = (1ULL << type_bits(type)) - 1;
242 242 }
243 243
244 244 bstate = get_state_expr(my_id, expr);
245 245 if (bstate)
246 246 bit_info = bstate->data;
247 247 else
248 248 bit_info = (struct bit_info *)&unknown_bit_info;
249 249
250 250 return combine_bit_info(extra_info, bit_info);
251 251 }
252 252
253 253 static int is_single_bit(sval_t sval)
254 254 {
255 255 int i;
256 256 int count = 0;
257 257
258 258 for (i = 0; i < 64; i++) {
259 259 if (sval.uvalue & 1ULL << i &&
260 260 count++)
261 261 return 0;
262 262 }
263 263 if (count == 1)
264 264 return 1;
265 265 return 0;
266 266 }
267 267
268 268 static void match_compare(struct expression *expr)
269 269 {
270 270 sval_t val;
271 271
272 272 if (expr->type != EXPR_COMPARE)
273 273 return;
274 274 if (expr->op != SPECIAL_EQUAL &&
275 275 expr->op != SPECIAL_NOTEQUAL)
276 276 return;
277 277
278 278 if (!get_implied_value(expr->right, &val))
279 279 return;
280 280
281 281 set_true_false_states_expr(my_id, expr->left,
282 282 (expr->op == SPECIAL_EQUAL) ? alloc_bstate(val.uvalue, val.uvalue) : NULL,
283 283 (expr->op == SPECIAL_EQUAL) ? NULL : alloc_bstate(val.uvalue, val.uvalue));
284 284 }
285 285
286 286 static bool is_loop_iterator(struct expression *expr)
287 287 {
288 288 struct statement *pre_stmt, *loop_stmt;
289 289
290 290 pre_stmt = expr_get_parent_stmt(expr);
291 291 if (!pre_stmt || pre_stmt->type != STMT_EXPRESSION)
292 292 return false;
293 293
294 294 loop_stmt = stmt_get_parent_stmt(pre_stmt);
295 295 if (!loop_stmt || loop_stmt->type != STMT_ITERATOR)
296 296 return false;
297 297 if (loop_stmt->iterator_pre_statement != pre_stmt)
298 298 return false;
299 299
300 300 return true;
301 301 }
302 302
303 303 static void match_assign(struct expression *expr)
304 304 {
305 305 struct bit_info *binfo;
306 306
307 307 if (expr->op != '=')
308 308 return;
309 309 if (__in_fake_assign)
310 310 return;
311 311 if (is_loop_iterator(expr))
312 312 return;
313 313
314 314 binfo = get_bit_info(expr->right);
315 315 if (!binfo)
316 316 return;
317 317 if (is_unknown_binfo(get_type(expr->left), binfo))
318 318 return;
319 319 set_state_expr(my_id, expr->left, alloc_bstate(binfo->set, binfo->possible));
320 320 }
321 321
322 322 static void match_condition(struct expression *expr)
323 323 {
324 324 struct bit_info *orig;
325 325 struct bit_info true_info;
326 326 struct bit_info false_info;
327 327 sval_t right;
328 328
329 329 if (expr->type != EXPR_BINOP ||
330 330 expr->op != '&')
331 331 return;
332 332
333 333 if (!get_value(expr->right, &right))
334 334 return;
335 335
336 336 orig = get_bit_info(expr->left);
337 337 true_info = *orig;
338 338 false_info = *orig;
339 339
340 340 if (right.uvalue == 0 || is_single_bit(right))
341 341 true_info.set &= right.uvalue;
342 342
343 343 true_info.possible &= right.uvalue;
344 344 false_info.possible &= ~right.uvalue;
345 345
346 346 set_true_false_states_expr(my_id, expr->left,
347 347 alloc_bstate(true_info.set, true_info.possible),
348 348 alloc_bstate(false_info.set, false_info.possible));
349 349 }
350 350
351 351 static void match_call_info(struct expression *expr)
352 352 {
353 353 struct bit_info *binfo, *rl_binfo;
354 354 struct expression *arg;
355 355 struct range_list *rl;
356 356 char buf[64];
357 357 int i;
358 358
359 359 i = -1;
360 360 FOR_EACH_PTR(expr->args, arg) {
361 361 i++;
362 362 binfo = get_bit_info(arg);
363 363 if (!binfo)
364 364 continue;
365 365 if (is_unknown_binfo(get_type(arg), binfo))
366 366 continue;
367 367 if (get_implied_rl(arg, &rl)) {
368 368 rl_binfo = rl_to_binfo(rl);
369 369 if (binfo_equiv(rl_binfo, binfo))
370 370 continue;
371 371 }
372 372 // If is just non-negative continue
373 373 // If ->set == ->possible continue
374 374 snprintf(buf, sizeof(buf), "0x%llx,0x%llx", binfo->set, binfo->possible);
375 375 sql_insert_caller_info(expr, BIT_INFO, i, "$", buf);
376 376 } END_FOR_EACH_PTR(arg);
377 377 }
378 378
379 379 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
380 380 {
381 381 struct bit_info *binfo = sm->state->data;
382 382 struct smatch_state *estate;
383 383 struct bit_info *implied_binfo;
384 384 char buf[64];
385 385
386 386 if (!binfo)
387 387 return;
388 388
389 389 /* This means it can only be one value, so it's handled by smatch_extra. */
390 390 if (binfo->set == binfo->possible)
391 391 return;
392 392
393 393 estate = get_state(SMATCH_EXTRA, sm->name, sm->sym);
394 394 if (is_unknown_binfo(estate_type(estate), binfo))
395 395 return;
396 396
397 397 if (estate_rl(estate)) {
398 398 sval_t sval;
399 399
400 400 if (estate_get_single_value(estate, &sval))
401 401 return;
402 402
403 403 implied_binfo = rl_to_binfo(estate_rl(estate));
404 404 if (binfo_equiv(implied_binfo, binfo))
405 405 return;
406 406 }
407 407
408 408 snprintf(buf, sizeof(buf), "0x%llx,0x%llx", binfo->set, binfo->possible);
409 409 sql_insert_caller_info(call, BIT_INFO, param, printed_name, buf);
410 410 }
411 411
412 412 static void set_param_bits(const char *name, struct symbol *sym, char *key, char *value)
413 413 {
414 414 char fullname[256];
415 415 unsigned long long set, possible;
416 416
417 417 if (strcmp(key, "*$") == 0)
418 418 snprintf(fullname, sizeof(fullname), "*%s", name);
419 419 else if (strncmp(key, "$", 1) == 0)
420 420 snprintf(fullname, 256, "%s%s", name, key + 1);
421 421 else
422 422 return;
423 423
424 424 set = strtoull(value, &value, 16);
425 425 if (*value != ',')
426 426 return;
427 427 value++;
428 428 possible = strtoull(value, &value, 16);
429 429
430 430 set_state(my_id, fullname, sym, alloc_bstate(set, possible));
431 431 }
432 432
433 433 void register_bits(int id)
434 434 {
435 435 my_id = id;
436 436
437 437 set_dynamic_states(my_id);
438 438
439 439 add_unmatched_state_hook(my_id, &unmatched_state);
440 440 add_merge_hook(my_id, &merge_bstates);
441 441
442 442 add_hook(&match_condition, CONDITION_HOOK);
443 443 add_hook(&match_compare, CONDITION_HOOK);
444 444 add_hook(&match_assign, ASSIGNMENT_HOOK);
445 445 add_modification_hook(my_id, &match_modify);
446 446
447 447 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
448 448 add_member_info_callback(my_id, struct_member_callback);
449 449 select_caller_info_hook(set_param_bits, BIT_INFO);
450 450 }
↓ open down ↓ |
383 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX