Print this page
12724 update smatch to 0.6.1-rc1-il-5
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;
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 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)
↓ open down ↓ |
103 lines elided |
↑ open up ↑ |
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 +static bool is_loop_iterator(struct expression *expr)
115 +{
116 + struct statement *pre_stmt, *loop_stmt;
117 +
118 + pre_stmt = expr_get_parent_stmt(expr);
119 + if (!pre_stmt || pre_stmt->type != STMT_EXPRESSION)
120 + return false;
121 +
122 + loop_stmt = stmt_get_parent_stmt(pre_stmt);
123 + if (!loop_stmt || loop_stmt->type != STMT_ITERATOR)
124 + return false;
125 + if (loop_stmt->iterator_pre_statement != pre_stmt)
126 + return false;
127 +
128 + return true;
129 +}
130 +
131 +static bool handled_by_assign_hook(struct expression *expr)
132 +{
133 + if (!expr || expr->type != EXPR_ASSIGNMENT)
134 + return false;
135 + if (__in_fake_assign)
136 + return false;
137 + if (is_loop_iterator(expr))
138 + return false;
139 +
140 + if (expr->op == '=' ||
141 + expr->op == SPECIAL_OR_ASSIGN ||
142 + expr->op == SPECIAL_AND_ASSIGN)
143 + return true;
144 +
145 + return false;
146 +}
147 +
114 148 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
115 149 {
116 150 // FIXME: we really need to store the type
117 151
152 + if (handled_by_assign_hook(mod_expr))
153 + return;
118 154 set_state(my_id, sm->name, sm->sym, alloc_bstate(0, -1ULL));
119 155 }
120 156
121 157 static int binfo_equiv(struct bit_info *one, struct bit_info *two)
122 158 {
123 159 if (one->set == two->set &&
124 160 one->possible == two->possible)
125 161 return 1;
126 162 return 0;
127 163 }
128 164
129 165 static struct smatch_state *merge_bstates(struct smatch_state *one_state, struct smatch_state *two_state)
130 166 {
131 167 struct bit_info *one, *two;
132 168
133 169 one = one_state->data;
134 170 two = two_state->data;
135 171
136 172 if (binfo_equiv(one, two))
137 173 return one_state;
138 174
139 175 return alloc_bstate(one->set & two->set, one->possible | two->possible);
140 176 }
141 177
142 178 /*
143 179 * The combine_bit_info() takes two bit_infos and takes creates the most
144 180 * accurate picture we can assuming both are true. Or it returns unknown if
145 181 * the information is logically impossible.
146 182 *
147 183 * Which means that it takes the | of the ->set bits and the & of the possibly
148 184 * set bits, which is the opposite of what merge_bstates() does.
149 185 *
150 186 */
151 187 static struct bit_info *combine_bit_info(struct bit_info *one, struct bit_info *two)
152 188 {
153 189 struct bit_info *ret = __alloc_bit_info(0);
154 190
155 191 if ((one->set & two->possible) != one->set)
156 192 return alloc_bit_info(0, -1ULL);
157 193 if ((two->set & one->possible) != two->set)
158 194 return alloc_bit_info(0, -1ULL);
159 195
160 196 ret->set = one->set | two->set;
161 197 ret->possible = one->possible & two->possible;
162 198
163 199 return ret;
164 200 }
165 201
166 202 static struct bit_info *binfo_AND(struct bit_info *left, struct bit_info *right)
167 203 {
168 204 unsigned long long set = 0;
169 205 unsigned long long possible = -1ULL;
170 206
171 207 if (!left && !right) {
172 208 /* nothing */
173 209 } else if (!left) {
174 210 possible = right->possible;
175 211 } else if (!right) {
176 212 possible = left->possible;
177 213 } else {
178 214 set = left->set & right->set;
179 215 possible = left->possible & right->possible;
180 216 }
181 217
182 218 return alloc_bit_info(set, possible);
183 219 }
184 220
185 221 static struct bit_info *binfo_OR(struct bit_info *left, struct bit_info *right)
186 222 {
187 223 unsigned long long set = 0;
188 224 unsigned long long possible = -1ULL;
189 225
190 226 if (!left && !right) {
191 227 /* nothing */
192 228 } else if (!left) {
193 229 set = right->set;
194 230 } else if (!right) {
195 231 set = left->set;
196 232 } else {
197 233 set = left->set | right->set;
198 234 possible = left->possible | right->possible;
199 235 }
200 236
201 237 return alloc_bit_info(set, possible);
202 238 }
203 239
204 240 struct bit_info *get_bit_info(struct expression *expr)
205 241 {
206 242 struct range_list *rl;
207 243 struct smatch_state *bstate;
208 244 struct bit_info tmp;
209 245 struct bit_info *extra_info;
210 246 struct bit_info *bit_info;
211 247 sval_t known;
212 248
213 249 expr = strip_parens(expr);
214 250
215 251 if (get_implied_value(expr, &known))
216 252 return alloc_bit_info(known.value, known.value);
217 253
218 254 if (expr->type == EXPR_BINOP) {
219 255 if (expr->op == '&')
220 256 return binfo_AND(get_bit_info(expr->left),
221 257 get_bit_info(expr->right));
222 258 if (expr->op == '|')
223 259 return binfo_OR(get_bit_info(expr->left),
224 260 get_bit_info(expr->right));
225 261 }
226 262
227 263 if (get_implied_rl(expr, &rl))
228 264 extra_info = rl_to_binfo(rl);
229 265 else {
230 266 struct symbol *type;
231 267
232 268 tmp = unknown_bit_info;
233 269 extra_info = &tmp;
234 270
235 271 type = get_type(expr);
236 272 if (!type)
237 273 type = &ullong_ctype;
238 274 if (type_bits(type) == 64)
239 275 extra_info->possible = -1ULL;
240 276 else
241 277 extra_info->possible = (1ULL << type_bits(type)) - 1;
242 278 }
243 279
244 280 bstate = get_state_expr(my_id, expr);
245 281 if (bstate)
246 282 bit_info = bstate->data;
247 283 else
248 284 bit_info = (struct bit_info *)&unknown_bit_info;
249 285
250 286 return combine_bit_info(extra_info, bit_info);
251 287 }
252 288
253 289 static int is_single_bit(sval_t sval)
254 290 {
255 291 int i;
256 292 int count = 0;
257 293
258 294 for (i = 0; i < 64; i++) {
259 295 if (sval.uvalue & 1ULL << i &&
260 296 count++)
261 297 return 0;
262 298 }
263 299 if (count == 1)
264 300 return 1;
265 301 return 0;
266 302 }
267 303
268 304 static void match_compare(struct expression *expr)
269 305 {
270 306 sval_t val;
271 307
272 308 if (expr->type != EXPR_COMPARE)
273 309 return;
274 310 if (expr->op != SPECIAL_EQUAL &&
275 311 expr->op != SPECIAL_NOTEQUAL)
↓ open down ↓ |
148 lines elided |
↑ open up ↑ |
276 312 return;
277 313
278 314 if (!get_implied_value(expr->right, &val))
279 315 return;
280 316
281 317 set_true_false_states_expr(my_id, expr->left,
282 318 (expr->op == SPECIAL_EQUAL) ? alloc_bstate(val.uvalue, val.uvalue) : NULL,
283 319 (expr->op == SPECIAL_EQUAL) ? NULL : alloc_bstate(val.uvalue, val.uvalue));
284 320 }
285 321
286 -static bool is_loop_iterator(struct expression *expr)
287 -{
288 - struct statement *pre_stmt, *loop_stmt;
289 -
290 - pre_stmt = expr_get_parent_stmt(expr);
291 - if (!pre_stmt || pre_stmt->type != STMT_EXPRESSION)
292 - return false;
293 -
294 - loop_stmt = stmt_get_parent_stmt(pre_stmt);
295 - if (!loop_stmt || loop_stmt->type != STMT_ITERATOR)
296 - return false;
297 - if (loop_stmt->iterator_pre_statement != pre_stmt)
298 - return false;
299 -
300 - return true;
301 -}
302 -
303 322 static void match_assign(struct expression *expr)
304 323 {
305 - struct bit_info *binfo;
324 + struct bit_info *start, *binfo;
325 + struct smatch_state *new;
306 326
307 - if (expr->op != '=')
327 + if (!handled_by_assign_hook(expr))
308 328 return;
309 - if (__in_fake_assign)
310 - return;
311 - if (is_loop_iterator(expr))
312 - return;
313 329
314 330 binfo = get_bit_info(expr->right);
315 331 if (!binfo)
316 332 return;
317 - if (is_unknown_binfo(get_type(expr->left), binfo))
318 - return;
319 - set_state_expr(my_id, expr->left, alloc_bstate(binfo->set, binfo->possible));
333 + if (expr->op == '=') {
334 + if (is_unknown_binfo(get_type(expr->left), binfo))
335 + return;
336 +
337 + set_state_expr(my_id, expr->left, alloc_bstate(binfo->set, binfo->possible));
338 + } else if (expr->op == SPECIAL_OR_ASSIGN) {
339 + start = get_bit_info(expr->left);
340 + new = alloc_bstate(start->set | binfo->set, start->possible | binfo->possible);
341 + set_state_expr(my_id, expr->left, new);
342 + } else if (expr->op == SPECIAL_AND_ASSIGN) {
343 + start = get_bit_info(expr->left);
344 + new = alloc_bstate(start->set & binfo->set, start->possible & binfo->possible);
345 + set_state_expr(my_id, expr->left, new);
346 + }
320 347 }
321 348
322 349 static void match_condition(struct expression *expr)
323 350 {
324 351 struct bit_info *orig;
325 352 struct bit_info true_info;
326 353 struct bit_info false_info;
327 354 sval_t right;
328 355
329 356 if (expr->type != EXPR_BINOP ||
330 357 expr->op != '&')
331 358 return;
332 359
333 360 if (!get_value(expr->right, &right))
334 361 return;
335 362
336 363 orig = get_bit_info(expr->left);
337 364 true_info = *orig;
338 365 false_info = *orig;
339 366
340 367 if (right.uvalue == 0 || is_single_bit(right))
341 368 true_info.set &= right.uvalue;
342 369
343 370 true_info.possible &= right.uvalue;
344 371 false_info.possible &= ~right.uvalue;
345 372
346 373 set_true_false_states_expr(my_id, expr->left,
347 374 alloc_bstate(true_info.set, true_info.possible),
348 375 alloc_bstate(false_info.set, false_info.possible));
349 376 }
350 377
351 378 static void match_call_info(struct expression *expr)
352 379 {
353 380 struct bit_info *binfo, *rl_binfo;
354 381 struct expression *arg;
355 382 struct range_list *rl;
356 383 char buf[64];
357 384 int i;
358 385
359 386 i = -1;
360 387 FOR_EACH_PTR(expr->args, arg) {
361 388 i++;
362 389 binfo = get_bit_info(arg);
363 390 if (!binfo)
364 391 continue;
365 392 if (is_unknown_binfo(get_type(arg), binfo))
366 393 continue;
367 394 if (get_implied_rl(arg, &rl)) {
368 395 rl_binfo = rl_to_binfo(rl);
369 396 if (binfo_equiv(rl_binfo, binfo))
370 397 continue;
371 398 }
372 399 // If is just non-negative continue
373 400 // If ->set == ->possible continue
374 401 snprintf(buf, sizeof(buf), "0x%llx,0x%llx", binfo->set, binfo->possible);
375 402 sql_insert_caller_info(expr, BIT_INFO, i, "$", buf);
376 403 } END_FOR_EACH_PTR(arg);
377 404 }
378 405
379 406 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
380 407 {
381 408 struct bit_info *binfo = sm->state->data;
382 409 struct smatch_state *estate;
383 410 struct bit_info *implied_binfo;
384 411 char buf[64];
385 412
386 413 if (!binfo)
387 414 return;
388 415
389 416 /* This means it can only be one value, so it's handled by smatch_extra. */
390 417 if (binfo->set == binfo->possible)
391 418 return;
392 419
393 420 estate = get_state(SMATCH_EXTRA, sm->name, sm->sym);
394 421 if (is_unknown_binfo(estate_type(estate), binfo))
395 422 return;
396 423
397 424 if (estate_rl(estate)) {
398 425 sval_t sval;
399 426
400 427 if (estate_get_single_value(estate, &sval))
401 428 return;
402 429
403 430 implied_binfo = rl_to_binfo(estate_rl(estate));
404 431 if (binfo_equiv(implied_binfo, binfo))
405 432 return;
406 433 }
407 434
408 435 snprintf(buf, sizeof(buf), "0x%llx,0x%llx", binfo->set, binfo->possible);
409 436 sql_insert_caller_info(call, BIT_INFO, param, printed_name, buf);
410 437 }
411 438
412 439 static void set_param_bits(const char *name, struct symbol *sym, char *key, char *value)
413 440 {
414 441 char fullname[256];
415 442 unsigned long long set, possible;
416 443
417 444 if (strcmp(key, "*$") == 0)
418 445 snprintf(fullname, sizeof(fullname), "*%s", name);
419 446 else if (strncmp(key, "$", 1) == 0)
420 447 snprintf(fullname, 256, "%s%s", name, key + 1);
421 448 else
422 449 return;
423 450
424 451 set = strtoull(value, &value, 16);
425 452 if (*value != ',')
426 453 return;
427 454 value++;
428 455 possible = strtoull(value, &value, 16);
429 456
430 457 set_state(my_id, fullname, sym, alloc_bstate(set, possible));
431 458 }
432 459
433 460 void register_bits(int id)
434 461 {
435 462 my_id = id;
436 463
437 464 set_dynamic_states(my_id);
438 465
439 466 add_unmatched_state_hook(my_id, &unmatched_state);
440 467 add_merge_hook(my_id, &merge_bstates);
441 468
442 469 add_hook(&match_condition, CONDITION_HOOK);
443 470 add_hook(&match_compare, CONDITION_HOOK);
444 471 add_hook(&match_assign, ASSIGNMENT_HOOK);
445 472 add_modification_hook(my_id, &match_modify);
446 473
447 474 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
448 475 add_member_info_callback(my_id, struct_member_callback);
449 476 select_caller_info_hook(set_param_bits, BIT_INFO);
450 477 }
↓ open down ↓ |
121 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX