Print this page
11462 enable smatch by default
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/tools/smatch/src/smatch_implied.c
+++ new/usr/src/tools/smatch/src/smatch_implied.c
1 1 /*
2 2 * Copyright (C) 2008 Dan Carpenter.
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
|
↓ open down ↓ |
5 lines elided |
↑ open up ↑ |
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 + *
17 + * Copyright 2019 Joyent, Inc.
16 18 */
17 19
18 20 /*
19 21 * Imagine we have this code:
20 22 * foo = 1;
21 23 * if (bar)
22 24 * foo = 99;
23 25 * else
24 26 * frob();
25 27 * // <-- point #1
26 28 * if (foo == 99) // <-- point #2
27 29 * bar->baz; // <-- point #3
28 30 *
29 31 *
30 32 * At point #3 bar is non null and can be dereferenced.
31 33 *
32 34 * It's smatch_implied.c which sets bar to non null at point #2.
33 35 *
34 36 * At point #1 merge_slist() stores the list of states from both
35 37 * the true and false paths. On the true path foo == 99 and on
36 38 * the false path foo == 1. merge_slist() sets their pool
37 39 * list to show the other states which were there when foo == 99.
38 40 *
39 41 * When it comes to the if (foo == 99) the smatch implied hook
40 42 * looks for all the pools where foo was not 99. It makes a list
41 43 * of those.
42 44 *
43 45 * Then for bar (and all the other states) it says, ok bar is a
44 46 * merged state that came from these previous states. We'll
45 47 * chop out all the states where it came from a pool where
46 48 * foo != 99 and merge it all back together.
47 49 *
48 50 * That is the implied state of bar.
49 51 *
50 52 * merge_slist() sets up ->pool. An sm_state only has one ->pool and
51 53 * that is the pool where it was first set. The my pool gets set when
52 54 * code paths merge. States that have been set since the last merge do
53 55 * not have a ->pool.
54 56 * merge_sm_state() sets ->left and ->right. (These are the states which were
55 57 * merged to form the current state.)
56 58 * a pool: a pool is an slist that has been merged with another slist.
57 59 */
58 60
59 61 #include <sys/time.h>
60 62 #include <time.h>
61 63 #include "smatch.h"
62 64 #include "smatch_slist.h"
63 65 #include "smatch_extra.h"
64 66
65 67 char *implied_debug_msg;
66 68 #define DIMPLIED(msg...) do { if (option_debug_implied || option_debug) printf(msg); } while (0)
67 69
68 70 int option_debug_implied = 0;
69 71
70 72 /*
71 73 * tmp_range_list():
72 74 * It messes things up to free range list allocations. This helper fuction
73 75 * lets us reuse memory instead of doing new allocations.
74 76 */
75 77 static struct range_list *tmp_range_list(struct symbol *type, long long num)
76 78 {
77 79 static struct range_list *my_list = NULL;
78 80 static struct data_range *my_range;
79 81
80 82 __free_ptr_list((struct ptr_list **)&my_list);
81 83 my_range = alloc_range(ll_to_sval(num), ll_to_sval(num));
82 84 add_ptr_list(&my_list, my_range);
83 85 return my_list;
84 86 }
85 87
86 88 static void print_debug_tf(struct sm_state *sm, int istrue, int isfalse)
87 89 {
88 90 if (!option_debug_implied && !option_debug)
89 91 return;
90 92
91 93 if (istrue && isfalse) {
92 94 printf("%s: %d: does not exist.\n", show_sm(sm), sm->line);
93 95 } else if (istrue) {
94 96 printf("'%s = %s' from %d is true. %s[stree %d]\n", sm->name, show_state(sm->state),
95 97 sm->line, sm->merged ? "[merged]" : "[leaf]",
96 98 get_stree_id(sm->pool));
97 99 } else if (isfalse) {
98 100 printf("'%s = %s' from %d is false. %s[stree %d]\n", sm->name, show_state(sm->state),
99 101 sm->line,
100 102 sm->merged ? "[merged]" : "[leaf]",
101 103 get_stree_id(sm->pool));
102 104 } else {
103 105 printf("'%s = %s' from %d could be true or false. %s[stree %d]\n", sm->name,
104 106 show_state(sm->state), sm->line,
105 107 sm->merged ? "[merged]" : "[leaf]",
106 108 get_stree_id(sm->pool));
107 109 }
108 110 }
109 111
110 112 static int create_fake_history(struct sm_state *sm, int comparison, struct range_list *rl)
111 113 {
112 114 struct range_list *orig_rl;
113 115 struct range_list *true_rl, *false_rl;
114 116 struct stree *true_stree, *false_stree;
115 117 struct sm_state *true_sm, *false_sm;
116 118 sval_t sval;
117 119
118 120 if (is_merged(sm) || sm->left || sm->right)
119 121 return 0;
120 122 if (!rl_to_sval(rl, &sval))
121 123 return 0;
122 124 if (!estate_rl(sm->state))
123 125 return 0;
124 126
125 127 orig_rl = cast_rl(rl_type(rl), estate_rl(sm->state));
126 128 split_comparison_rl(orig_rl, comparison, rl, &true_rl, &false_rl, NULL, NULL);
127 129
128 130 true_rl = rl_truncate_cast(estate_type(sm->state), true_rl);
129 131 false_rl = rl_truncate_cast(estate_type(sm->state), false_rl);
130 132 if (is_whole_rl(true_rl) || is_whole_rl(false_rl) ||
131 133 !true_rl || !false_rl ||
132 134 rl_equiv(orig_rl, true_rl) || rl_equiv(orig_rl, false_rl) ||
133 135 rl_equiv(estate_rl(sm->state), true_rl) || rl_equiv(estate_rl(sm->state), false_rl))
134 136 return 0;
135 137
136 138 if (rl_intersection(true_rl, false_rl)) {
137 139 sm_perror("parsing (%s (%s) %s %s)",
138 140 sm->name, sm->state->name, show_special(comparison), show_rl(rl));
139 141 sm_msg("true_rl = %s false_rl = %s intersection = %s",
140 142 show_rl(true_rl), show_rl(false_rl), show_rl(rl_intersection(true_rl, false_rl)));
141 143 return 0;
142 144 }
143 145
144 146 if (option_debug)
145 147 sm_info("fake_history: %s vs %s. %s %s %s. --> T: %s F: %s",
146 148 sm->name, show_rl(rl), sm->state->name, show_special(comparison), show_rl(rl),
147 149 show_rl(true_rl), show_rl(false_rl));
148 150
149 151 true_sm = clone_sm(sm);
150 152 false_sm = clone_sm(sm);
151 153
152 154 true_sm->state = alloc_estate_rl(cast_rl(estate_type(sm->state), true_rl));
153 155 free_slist(&true_sm->possible);
154 156 add_possible_sm(true_sm, true_sm);
155 157 false_sm->state = alloc_estate_rl(cast_rl(estate_type(sm->state), false_rl));
156 158 free_slist(&false_sm->possible);
157 159 add_possible_sm(false_sm, false_sm);
158 160
159 161 true_stree = clone_stree(sm->pool);
160 162 false_stree = clone_stree(sm->pool);
161 163
162 164 overwrite_sm_state_stree(&true_stree, true_sm);
163 165 overwrite_sm_state_stree(&false_stree, false_sm);
164 166
165 167 true_sm->pool = true_stree;
166 168 false_sm->pool = false_stree;
167 169
168 170 sm->merged = 1;
169 171 sm->left = true_sm;
170 172 sm->right = false_sm;
171 173
172 174 return 1;
173 175 }
174 176
175 177 /*
176 178 * add_pool() adds a slist to *pools. If the slist has already been
177 179 * added earlier then it doesn't get added a second time.
178 180 */
179 181 void add_pool(struct state_list **pools, struct sm_state *new)
180 182 {
181 183 struct sm_state *tmp;
182 184
183 185 FOR_EACH_PTR(*pools, tmp) {
184 186 if (tmp->pool < new->pool)
185 187 continue;
186 188 else if (tmp->pool == new->pool) {
187 189 return;
188 190 } else {
189 191 INSERT_CURRENT(new, tmp);
190 192 return;
191 193 }
192 194 } END_FOR_EACH_PTR(tmp);
193 195 add_ptr_list(pools, new);
194 196 }
195 197
196 198 static int pool_in_pools(struct stree *pool,
197 199 const struct state_list *slist)
198 200 {
199 201 struct sm_state *tmp;
200 202
201 203 FOR_EACH_PTR(slist, tmp) {
202 204 if (!tmp->pool)
203 205 continue;
204 206 if (tmp->pool == pool)
205 207 return 1;
206 208 } END_FOR_EACH_PTR(tmp);
207 209 return 0;
208 210 }
209 211
210 212 static int remove_pool(struct state_list **pools, struct stree *remove)
211 213 {
212 214 struct sm_state *tmp;
213 215 int ret = 0;
214 216
215 217 FOR_EACH_PTR(*pools, tmp) {
216 218 if (tmp->pool == remove) {
217 219 DELETE_CURRENT_PTR(tmp);
218 220 ret = 1;
219 221 }
220 222 } END_FOR_EACH_PTR(tmp);
221 223
222 224 return ret;
223 225 }
224 226
225 227 /*
226 228 * If 'foo' == 99 add it that pool to the true pools. If it's false, add it to
227 229 * the false pools. If we're not sure, then we don't add it to either.
228 230 */
229 231 static void do_compare(struct sm_state *sm, int comparison, struct range_list *rl,
230 232 struct state_list **true_stack,
231 233 struct state_list **maybe_stack,
232 234 struct state_list **false_stack,
233 235 int *mixed, struct sm_state *gate_sm)
234 236 {
235 237 int istrue;
236 238 int isfalse;
237 239 struct range_list *var_rl;
238 240
239 241 if (!sm->pool)
240 242 return;
241 243
242 244 var_rl = cast_rl(rl_type(rl), estate_rl(sm->state));
243 245
244 246 istrue = !possibly_false_rl(var_rl, comparison, rl);
245 247 isfalse = !possibly_true_rl(var_rl, comparison, rl);
246 248
247 249 print_debug_tf(sm, istrue, isfalse);
248 250
249 251 /* give up if we have borrowed implications (smatch_equiv.c) */
250 252 if (sm->sym != gate_sm->sym ||
251 253 strcmp(sm->name, gate_sm->name) != 0) {
252 254 if (mixed)
253 255 *mixed = 1;
254 256 }
255 257
256 258 if (mixed && !*mixed && !is_merged(sm) && !istrue && !isfalse) {
257 259 if (!create_fake_history(sm, comparison, rl))
258 260 *mixed = 1;
259 261 }
260 262
261 263 if (istrue)
262 264 add_pool(true_stack, sm);
263 265 else if (isfalse)
264 266 add_pool(false_stack, sm);
265 267 else
266 268 add_pool(maybe_stack, sm);
267 269
268 270 }
269 271
270 272 static int is_checked(struct state_list *checked, struct sm_state *sm)
271 273 {
272 274 struct sm_state *tmp;
273 275
274 276 FOR_EACH_PTR(checked, tmp) {
275 277 if (tmp == sm)
276 278 return 1;
277 279 } END_FOR_EACH_PTR(tmp);
278 280 return 0;
279 281 }
280 282
281 283 /*
282 284 * separate_pools():
283 285 * Example code: if (foo == 99) {
284 286 *
285 287 * Say 'foo' is a merged state that has many possible values. It is the combination
286 288 * of merges. separate_pools() iterates through the pools recursively and calls
287 289 * do_compare() for each time 'foo' was set.
288 290 */
289 291 static void __separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
290 292 struct state_list **true_stack,
291 293 struct state_list **maybe_stack,
292 294 struct state_list **false_stack,
293 295 struct state_list **checked, int *mixed, struct sm_state *gate_sm)
294 296 {
295 297 int free_checked = 0;
296 298 struct state_list *checked_states = NULL;
297 299
298 300 if (!sm)
299 301 return;
300 302
301 303 /*
302 304 * If it looks like this is going to take too long as-is, then don't
303 305 * create even more fake history.
304 306 */
305 307 if (mixed && sm->nr_children > 100)
306 308 *mixed = 1;
307 309
308 310 /*
309 311 Sometimes the implications are just too big to deal with
310 312 so we bail. Theoretically, bailing out here can cause more false
311 313 positives but won't hide actual bugs.
312 314 */
313 315 if (sm->nr_children > 4000) {
314 316 if (option_debug || option_debug_implied) {
315 317 static char buf[1028];
316 318 snprintf(buf, sizeof(buf), "debug: %s: nr_children over 4000 (%d). (%s %s)",
317 319 __func__, sm->nr_children, sm->name, show_state(sm->state));
318 320 implied_debug_msg = buf;
319 321 }
320 322 return;
321 323 }
322 324
323 325 if (checked == NULL) {
324 326 checked = &checked_states;
325 327 free_checked = 1;
326 328 }
327 329 if (is_checked(*checked, sm))
328 330 return;
329 331 add_ptr_list(checked, sm);
330 332
331 333 do_compare(sm, comparison, rl, true_stack, maybe_stack, false_stack, mixed, gate_sm);
332 334
333 335 __separate_pools(sm->left, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm);
334 336 __separate_pools(sm->right, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm);
335 337 if (free_checked)
336 338 free_slist(checked);
337 339 }
338 340
339 341 static void separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
340 342 struct state_list **true_stack,
341 343 struct state_list **false_stack,
342 344 struct state_list **checked, int *mixed)
343 345 {
344 346 struct state_list *maybe_stack = NULL;
345 347 struct sm_state *tmp;
346 348
347 349 __separate_pools(sm, comparison, rl, true_stack, &maybe_stack, false_stack, checked, mixed, sm);
348 350
349 351 if (option_debug) {
350 352 struct sm_state *sm;
351 353
352 354 FOR_EACH_PTR(*true_stack, sm) {
353 355 sm_msg("TRUE %s [stree %d]", show_sm(sm), get_stree_id(sm->pool));
354 356 } END_FOR_EACH_PTR(sm);
355 357
356 358 FOR_EACH_PTR(maybe_stack, sm) {
357 359 sm_msg("MAYBE %s [stree %d]", show_sm(sm), get_stree_id(sm->pool));
358 360 } END_FOR_EACH_PTR(sm);
359 361
360 362 FOR_EACH_PTR(*false_stack, sm) {
361 363 sm_msg("FALSE %s [stree %d]", show_sm(sm), get_stree_id(sm->pool));
362 364 } END_FOR_EACH_PTR(sm);
363 365 }
364 366 /* if it's a maybe then remove it */
365 367 FOR_EACH_PTR(maybe_stack, tmp) {
366 368 remove_pool(false_stack, tmp->pool);
367 369 remove_pool(true_stack, tmp->pool);
368 370 } END_FOR_EACH_PTR(tmp);
369 371
370 372 /* if it's both true and false remove it from both */
371 373 FOR_EACH_PTR(*true_stack, tmp) {
372 374 if (remove_pool(false_stack, tmp->pool))
373 375 DELETE_CURRENT_PTR(tmp);
374 376 } END_FOR_EACH_PTR(tmp);
375 377 }
376 378
377 379 static int sm_in_keep_leafs(struct sm_state *sm, const struct state_list *keep_gates)
378 380 {
379 381 struct sm_state *tmp, *old;
380 382
381 383 FOR_EACH_PTR(keep_gates, tmp) {
382 384 if (is_merged(tmp))
383 385 continue;
384 386 old = get_sm_state_stree(tmp->pool, sm->owner, sm->name, sm->sym);
385 387 if (!old)
386 388 continue;
387 389 if (old == sm)
388 390 return 1;
389 391 } END_FOR_EACH_PTR(tmp);
|
↓ open down ↓ |
364 lines elided |
↑ open up ↑ |
390 392 return 0;
391 393 }
392 394
393 395 static int taking_too_long(void)
394 396 {
395 397 static void *printed;
396 398
397 399 if (out_of_memory())
398 400 return 1;
399 401
400 - if (time_parsing_function() < 60)
402 + if (time_parsing_function() < option_timeout)
401 403 return 0;
402 404
403 405 if (!__inline_fn && printed != cur_func_sym) {
404 406 if (!is_skipped_function())
405 407 sm_perror("turning off implications after 60 seconds");
406 408 printed = cur_func_sym;
407 409 }
408 410 return 1;
409 411 }
410 412
411 413 /*
412 414 * NOTE: If a state is in both the keep stack and the remove stack then that is
413 415 * a bug. Only add states which are definitely true or definitely false. If
414 416 * you have a leaf state that could be both true and false, then create a fake
415 417 * split history where one side is true and one side is false. Otherwise, if
416 418 * you can't do that, then don't add it to either list.
417 419 */
418 420 struct sm_state *filter_pools(struct sm_state *sm,
419 421 const struct state_list *remove_stack,
420 422 const struct state_list *keep_stack,
421 423 int *modified, int *recurse_cnt,
422 424 struct timeval *start)
423 425 {
424 426 struct sm_state *ret = NULL;
425 427 struct sm_state *left;
426 428 struct sm_state *right;
427 429 int removed = 0;
428 430 struct timeval now;
429 431
430 432 if (!sm)
431 433 return NULL;
432 434 if (sm->skip_implications)
433 435 return sm;
434 436 if (taking_too_long())
435 437 return sm;
436 438
437 439 gettimeofday(&now, NULL);
438 440 if ((*recurse_cnt)++ > 1000 || now.tv_sec - start->tv_sec > 5) {
439 441 if (local_debug || option_debug_implied) {
440 442 static char buf[1028];
441 443 snprintf(buf, sizeof(buf), "debug: %s: nr_children over 4000 (%d). (%s %s)",
442 444 __func__, sm->nr_children, sm->name, show_state(sm->state));
443 445 implied_debug_msg = buf;
444 446 }
445 447 sm->skip_implications = 1;
446 448 return sm;
447 449 }
448 450
449 451 if (pool_in_pools(sm->pool, remove_stack)) {
450 452 DIMPLIED("removed [stree %d] %s from %d\n", get_stree_id(sm->pool), show_sm(sm), sm->line);
451 453 *modified = 1;
452 454 return NULL;
453 455 }
454 456
455 457 if (!is_merged(sm) || pool_in_pools(sm->pool, keep_stack) || sm_in_keep_leafs(sm, keep_stack)) {
456 458 DIMPLIED("kept [stree %d] %s from %d. %s. %s. %s.\n", get_stree_id(sm->pool), show_sm(sm), sm->line,
457 459 is_merged(sm) ? "merged" : "not merged",
458 460 pool_in_pools(sm->pool, keep_stack) ? "not in keep pools" : "in keep pools",
459 461 sm_in_keep_leafs(sm, keep_stack) ? "reachable keep leaf" : "no keep leaf");
460 462 return sm;
461 463 }
462 464
463 465 DIMPLIED("checking [stree %d] %s from %d (%d) left = %s [stree %d] right = %s [stree %d]\n",
464 466 get_stree_id(sm->pool),
465 467 show_sm(sm), sm->line, sm->nr_children,
466 468 sm->left ? sm->left->state->name : "<none>", sm->left ? get_stree_id(sm->left->pool) : -1,
467 469 sm->right ? sm->right->state->name : "<none>", sm->right ? get_stree_id(sm->right->pool) : -1);
468 470 left = filter_pools(sm->left, remove_stack, keep_stack, &removed, recurse_cnt, start);
469 471 right = filter_pools(sm->right, remove_stack, keep_stack, &removed, recurse_cnt, start);
470 472 if (!removed) {
471 473 DIMPLIED("kept [stree %d] %s from %d\n", get_stree_id(sm->pool), show_sm(sm), sm->line);
472 474 return sm;
473 475 }
474 476 *modified = 1;
475 477 if (!left && !right) {
476 478 DIMPLIED("removed [stree %d] %s from %d <none>\n", get_stree_id(sm->pool), show_sm(sm), sm->line);
477 479 return NULL;
478 480 }
479 481
480 482 if (!left) {
481 483 ret = clone_sm(right);
482 484 ret->merged = 1;
483 485 ret->right = right;
484 486 ret->left = NULL;
485 487 } else if (!right) {
486 488 ret = clone_sm(left);
487 489 ret->merged = 1;
488 490 ret->left = left;
489 491 ret->right = NULL;
490 492 } else {
491 493 if (left->sym != sm->sym || strcmp(left->name, sm->name) != 0) {
492 494 left = clone_sm(left);
493 495 left->sym = sm->sym;
494 496 left->name = sm->name;
495 497 }
496 498 if (right->sym != sm->sym || strcmp(right->name, sm->name) != 0) {
497 499 right = clone_sm(right);
498 500 right->sym = sm->sym;
499 501 right->name = sm->name;
500 502 }
501 503 ret = merge_sm_states(left, right);
502 504 }
503 505
504 506 ret->pool = sm->pool;
505 507
506 508 DIMPLIED("partial %s => ", show_sm(sm));
507 509 DIMPLIED("%s from %d [stree %d]\n", show_sm(ret), sm->line, get_stree_id(sm->pool));
508 510 return ret;
509 511 }
510 512
511 513 static struct stree *filter_stack(struct sm_state *gate_sm,
512 514 struct stree *pre_stree,
513 515 const struct state_list *remove_stack,
514 516 const struct state_list *keep_stack)
515 517 {
516 518 struct stree *ret = NULL;
517 519 struct sm_state *tmp;
518 520 struct sm_state *filtered_sm;
519 521 int modified;
520 522 int recurse_cnt;
521 523 struct timeval start;
522 524
523 525 if (!remove_stack)
524 526 return NULL;
525 527
526 528 if (taking_too_long())
527 529 return NULL;
528 530
529 531 FOR_EACH_SM(pre_stree, tmp) {
530 532 if (option_debug)
531 533 sm_msg("%s: %s", __func__, show_sm(tmp));
532 534 if (!tmp->merged)
533 535 continue;
534 536 if (sm_in_keep_leafs(tmp, keep_stack))
535 537 continue;
536 538 modified = 0;
537 539 recurse_cnt = 0;
538 540 gettimeofday(&start, NULL);
539 541 filtered_sm = filter_pools(tmp, remove_stack, keep_stack, &modified, &recurse_cnt, &start);
540 542 if (!filtered_sm || !modified)
541 543 continue;
542 544 /* the assignments here are for borrowed implications */
543 545 filtered_sm->name = tmp->name;
544 546 filtered_sm->sym = tmp->sym;
545 547 avl_insert(&ret, filtered_sm);
546 548 if (out_of_memory() || taking_too_long())
547 549 return NULL;
548 550
549 551 } END_FOR_EACH_SM(tmp);
550 552 return ret;
551 553 }
552 554
553 555 static void separate_and_filter(struct sm_state *sm, int comparison, struct range_list *rl,
554 556 struct stree *pre_stree,
555 557 struct stree **true_states,
556 558 struct stree **false_states,
557 559 int *mixed)
558 560 {
559 561 struct state_list *true_stack = NULL;
560 562 struct state_list *false_stack = NULL;
561 563 struct timeval time_before;
562 564 struct timeval time_after;
563 565 int sec;
564 566
565 567 gettimeofday(&time_before, NULL);
566 568
567 569 if (!is_merged(sm)) {
568 570 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm->name);
569 571 return;
570 572 }
571 573
572 574 if (option_debug_implied || option_debug) {
573 575 sm_msg("checking implications: (%s %s %s)",
574 576 sm->name, show_special(comparison), show_rl(rl));
575 577 }
576 578
577 579 separate_pools(sm, comparison, rl, &true_stack, &false_stack, NULL, mixed);
578 580
579 581 DIMPLIED("filtering true stack.\n");
580 582 *true_states = filter_stack(sm, pre_stree, false_stack, true_stack);
581 583 DIMPLIED("filtering false stack.\n");
582 584 *false_states = filter_stack(sm, pre_stree, true_stack, false_stack);
583 585 free_slist(&true_stack);
584 586 free_slist(&false_stack);
585 587 if (option_debug_implied || option_debug) {
|
↓ open down ↓ |
175 lines elided |
↑ open up ↑ |
586 588 printf("These are the implied states for the true path: (%s %s %s)\n",
587 589 sm->name, show_special(comparison), show_rl(rl));
588 590 __print_stree(*true_states);
589 591 printf("These are the implied states for the false path: (%s %s %s)\n",
590 592 sm->name, show_special(comparison), show_rl(rl));
591 593 __print_stree(*false_states);
592 594 }
593 595
594 596 gettimeofday(&time_after, NULL);
595 597 sec = time_after.tv_sec - time_before.tv_sec;
596 - if (sec > 20) {
598 + if (sec > option_timeout) {
597 599 sm->nr_children = 4000;
598 600 sm_perror("Function too hairy. Ignoring implications after %d seconds.", sec);
599 601 }
600 602 }
601 603
602 604 static struct expression *get_last_expr(struct statement *stmt)
603 605 {
604 606 struct statement *last;
605 607
606 608 last = last_ptr_list((struct ptr_list *)stmt->stmts);
607 609 if (last->type == STMT_EXPRESSION)
608 610 return last->expression;
609 611
610 612 if (last->type == STMT_LABEL) {
611 613 if (last->label_statement &&
612 614 last->label_statement->type == STMT_EXPRESSION)
613 615 return last->label_statement->expression;
614 616 }
615 617
616 618 return NULL;
617 619 }
618 620
619 621 static struct expression *get_left_most_expr(struct expression *expr)
620 622 {
621 623 struct statement *compound;
622 624
623 625 compound = get_expression_statement(expr);
624 626 if (compound)
625 627 return get_last_expr(compound);
626 628
627 629 expr = strip_parens(expr);
628 630 if (expr->type == EXPR_ASSIGNMENT)
629 631 return get_left_most_expr(expr->left);
630 632 return expr;
631 633 }
632 634
633 635 static int is_merged_expr(struct expression *expr)
634 636 {
635 637 struct sm_state *sm;
636 638 sval_t dummy;
637 639
638 640 if (get_value(expr, &dummy))
639 641 return 0;
640 642 sm = get_sm_state_expr(SMATCH_EXTRA, expr);
641 643 if (!sm)
642 644 return 0;
643 645 if (is_merged(sm))
644 646 return 1;
645 647 return 0;
646 648 }
647 649
648 650 static void delete_gate_sm_equiv(struct stree **stree, const char *name, struct symbol *sym)
649 651 {
650 652 struct smatch_state *state;
651 653 struct relation *rel;
652 654
653 655 state = get_state(SMATCH_EXTRA, name, sym);
654 656 if (!state)
655 657 return;
656 658 FOR_EACH_PTR(estate_related(state), rel) {
657 659 delete_state_stree(stree, SMATCH_EXTRA, rel->name, rel->sym);
658 660 } END_FOR_EACH_PTR(rel);
659 661 }
660 662
661 663 static void delete_gate_sm(struct stree **stree, const char *name, struct symbol *sym)
662 664 {
663 665 delete_state_stree(stree, SMATCH_EXTRA, name, sym);
664 666 }
665 667
666 668 static int handle_comparison(struct expression *expr,
667 669 struct stree **implied_true,
668 670 struct stree **implied_false)
669 671 {
670 672 struct sm_state *sm = NULL;
671 673 struct range_list *rl = NULL;
672 674 struct expression *left;
673 675 struct expression *right;
674 676 struct symbol *type;
675 677 int comparison = expr->op;
676 678 int mixed = 0;
677 679
678 680 left = get_left_most_expr(expr->left);
679 681 right = get_left_most_expr(expr->right);
680 682
681 683 if (is_merged_expr(left)) {
682 684 sm = get_sm_state_expr(SMATCH_EXTRA, left);
683 685 get_implied_rl(right, &rl);
684 686 } else if (is_merged_expr(right)) {
685 687 sm = get_sm_state_expr(SMATCH_EXTRA, right);
686 688 get_implied_rl(left, &rl);
687 689 comparison = flip_comparison(comparison);
688 690 }
689 691
690 692 if (!rl || !sm)
691 693 return 0;
692 694
693 695 type = get_type(expr);
694 696 if (!type)
695 697 return 0;
696 698 if (type_positive_bits(rl_type(rl)) > type_positive_bits(type))
697 699 type = rl_type(rl);
698 700 if (type_positive_bits(type) < 31)
699 701 type = &int_ctype;
700 702 rl = cast_rl(type, rl);
701 703
702 704 separate_and_filter(sm, comparison, rl, __get_cur_stree(), implied_true, implied_false, &mixed);
703 705
704 706 delete_gate_sm_equiv(implied_true, sm->name, sm->sym);
705 707 delete_gate_sm_equiv(implied_false, sm->name, sm->sym);
706 708 if (mixed) {
707 709 delete_gate_sm(implied_true, sm->name, sm->sym);
708 710 delete_gate_sm(implied_false, sm->name, sm->sym);
709 711 }
710 712
711 713 return 1;
712 714 }
713 715
714 716 static int handle_zero_comparison(struct expression *expr,
715 717 struct stree **implied_true,
716 718 struct stree **implied_false)
717 719 {
718 720 struct symbol *sym;
719 721 char *name;
720 722 struct sm_state *sm;
721 723 int mixed = 0;
722 724 int ret = 0;
723 725
724 726 if (expr->type == EXPR_POSTOP)
725 727 expr = strip_expr(expr->unop);
726 728
727 729 if (expr->type == EXPR_ASSIGNMENT) {
728 730 /* most of the time ->pools will be empty here because we
729 731 just set the state, but if have assigned a conditional
730 732 function there are implications. */
731 733 expr = expr->left;
732 734 }
733 735
734 736 name = expr_to_var_sym(expr, &sym);
735 737 if (!name || !sym)
736 738 goto free;
737 739 sm = get_sm_state(SMATCH_EXTRA, name, sym);
738 740 if (!sm)
739 741 goto free;
740 742
741 743 separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(estate_type(sm->state), 0), __get_cur_stree(), implied_true, implied_false, &mixed);
742 744 delete_gate_sm_equiv(implied_true, sm->name, sm->sym);
743 745 delete_gate_sm_equiv(implied_false, sm->name, sm->sym);
744 746 if (mixed) {
745 747 delete_gate_sm(implied_true, sm->name, sm->sym);
746 748 delete_gate_sm(implied_false, sm->name, sm->sym);
747 749 }
748 750
749 751 ret = 1;
750 752 free:
751 753 free_string(name);
752 754 return ret;
753 755 }
754 756
755 757 static int handled_by_comparison_hook(struct expression *expr,
756 758 struct stree **implied_true,
757 759 struct stree **implied_false)
758 760 {
759 761 struct state_list *true_stack = NULL;
760 762 struct state_list *false_stack = NULL;
761 763 struct stree *pre_stree;
762 764 struct sm_state *sm;
763 765
764 766 sm = comparison_implication_hook(expr, &true_stack, &false_stack);
765 767 if (!sm)
766 768 return 0;
767 769
768 770 pre_stree = clone_stree(__get_cur_stree());
769 771
770 772 *implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
771 773 *implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
772 774
773 775 free_stree(&pre_stree);
774 776 free_slist(&true_stack);
775 777 free_slist(&false_stack);
776 778
777 779 return 1;
778 780 }
779 781
780 782 static int handled_by_extra_states(struct expression *expr,
781 783 struct stree **implied_true,
782 784 struct stree **implied_false)
783 785 {
784 786 if (expr->type == EXPR_COMPARE)
785 787 return handle_comparison(expr, implied_true, implied_false);
786 788 else
787 789 return handle_zero_comparison(expr, implied_true, implied_false);
788 790 }
789 791
790 792 static int handled_by_stored_conditions(struct expression *expr,
791 793 struct stree **implied_true,
792 794 struct stree **implied_false)
793 795 {
794 796 struct state_list *true_stack = NULL;
795 797 struct state_list *false_stack = NULL;
796 798 struct stree *pre_stree;
797 799 struct sm_state *sm;
798 800
799 801 sm = stored_condition_implication_hook(expr, &true_stack, &false_stack);
800 802 if (!sm)
801 803 return 0;
802 804
803 805 pre_stree = clone_stree(__get_cur_stree());
804 806
805 807 *implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
806 808 *implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
807 809
808 810 free_stree(&pre_stree);
809 811 free_slist(&true_stack);
810 812 free_slist(&false_stack);
811 813
812 814 return 1;
813 815 }
814 816
815 817 static int found_implications;
816 818 static struct stree *saved_implied_true;
817 819 static struct stree *saved_implied_false;
818 820 static struct stree *extra_saved_implied_true;
819 821 static struct stree *extra_saved_implied_false;
820 822
821 823 static void separate_extra_states(struct stree **implied_true,
822 824 struct stree **implied_false)
823 825 {
824 826 struct sm_state *sm;
825 827
826 828 /* We process extra states later to preserve the implications. */
827 829 FOR_EACH_SM(*implied_true, sm) {
828 830 if (sm->owner == SMATCH_EXTRA)
829 831 overwrite_sm_state_stree(&extra_saved_implied_true, sm);
830 832 } END_FOR_EACH_SM(sm);
831 833 FOR_EACH_SM(extra_saved_implied_true, sm) {
832 834 delete_state_stree(implied_true, sm->owner, sm->name, sm->sym);
833 835 } END_FOR_EACH_SM(sm);
834 836
835 837 FOR_EACH_SM(*implied_false, sm) {
836 838 if (sm->owner == SMATCH_EXTRA)
837 839 overwrite_sm_state_stree(&extra_saved_implied_false, sm);
838 840 } END_FOR_EACH_SM(sm);
839 841 FOR_EACH_SM(extra_saved_implied_false, sm) {
840 842 delete_state_stree(implied_false, sm->owner, sm->name, sm->sym);
841 843 } END_FOR_EACH_SM(sm);
842 844 }
843 845
844 846 static void get_tf_states(struct expression *expr,
845 847 struct stree **implied_true,
846 848 struct stree **implied_false)
847 849 {
848 850 if (handled_by_comparison_hook(expr, implied_true, implied_false))
849 851 goto found;
850 852
851 853 if (handled_by_extra_states(expr, implied_true, implied_false)) {
852 854 separate_extra_states(implied_true, implied_false);
853 855 goto found;
854 856 }
855 857
856 858 if (handled_by_stored_conditions(expr, implied_true, implied_false))
857 859 goto found;
858 860
859 861 return;
860 862 found:
861 863 found_implications = 1;
862 864 }
863 865
864 866 static void save_implications_hook(struct expression *expr)
865 867 {
866 868 if (taking_too_long())
867 869 return;
868 870 get_tf_states(expr, &saved_implied_true, &saved_implied_false);
869 871 }
870 872
871 873 static void set_implied_states(struct expression *expr)
872 874 {
873 875 struct sm_state *sm;
874 876
875 877 FOR_EACH_SM(saved_implied_true, sm) {
876 878 __set_true_false_sm(sm, NULL);
877 879 } END_FOR_EACH_SM(sm);
878 880 free_stree(&saved_implied_true);
879 881
880 882 FOR_EACH_SM(saved_implied_false, sm) {
881 883 __set_true_false_sm(NULL, sm);
882 884 } END_FOR_EACH_SM(sm);
883 885 free_stree(&saved_implied_false);
884 886 }
885 887
886 888 static void set_extra_implied_states(struct expression *expr)
887 889 {
888 890 saved_implied_true = extra_saved_implied_true;
889 891 saved_implied_false = extra_saved_implied_false;
890 892 extra_saved_implied_true = NULL;
891 893 extra_saved_implied_false = NULL;
892 894 set_implied_states(NULL);
893 895 }
894 896
895 897 void param_limit_implications(struct expression *expr, int param, char *key, char *value)
896 898 {
897 899 struct expression *arg;
898 900 struct symbol *compare_type;
899 901 char *name;
900 902 struct symbol *sym;
901 903 struct sm_state *sm;
902 904 struct sm_state *tmp;
903 905 struct stree *implied_true = NULL;
904 906 struct stree *implied_false = NULL;
905 907 struct range_list *orig, *limit;
906 908
907 909 while (expr->type == EXPR_ASSIGNMENT)
908 910 expr = strip_expr(expr->right);
909 911 if (expr->type != EXPR_CALL)
910 912 return;
911 913
912 914 arg = get_argument_from_call_expr(expr->args, param);
913 915 if (!arg)
914 916 return;
915 917
916 918 arg = strip_parens(arg);
917 919 while (arg->type == EXPR_ASSIGNMENT && arg->op == '=')
918 920 arg = strip_parens(arg->left);
919 921
920 922 name = get_variable_from_key(arg, key, &sym);
921 923 if (!name || !sym)
922 924 goto free;
923 925
924 926 sm = get_sm_state(SMATCH_EXTRA, name, sym);
925 927 if (!sm || !sm->merged)
926 928 goto free;
927 929
928 930 if (strcmp(key, "$") == 0)
929 931 compare_type = get_arg_type(expr->fn, param);
930 932 else
931 933 compare_type = get_member_type_from_key(arg, key);
932 934
933 935 orig = estate_rl(sm->state);
934 936 orig = cast_rl(compare_type, orig);
935 937
936 938 call_results_to_rl(expr, compare_type, value, &limit);
937 939
938 940 separate_and_filter(sm, SPECIAL_EQUAL, limit, __get_cur_stree(), &implied_true, &implied_false, NULL);
939 941
940 942 FOR_EACH_SM(implied_true, tmp) {
941 943 __set_sm_fake_stree(tmp);
942 944 } END_FOR_EACH_SM(tmp);
943 945
944 946 free_stree(&implied_true);
945 947 free_stree(&implied_false);
946 948 free:
947 949 free_string(name);
948 950 }
949 951
950 952 struct stree *__implied_case_stree(struct expression *switch_expr,
951 953 struct range_list *rl,
952 954 struct range_list_stack **remaining_cases,
953 955 struct stree **raw_stree)
954 956 {
955 957 char *name;
956 958 struct symbol *sym;
957 959 struct var_sym_list *vsl;
958 960 struct sm_state *sm;
959 961 struct stree *true_states = NULL;
960 962 struct stree *false_states = NULL;
961 963 struct stree *extra_states;
962 964 struct stree *ret = clone_stree(*raw_stree);
963 965
964 966 name = expr_to_chunk_sym_vsl(switch_expr, &sym, &vsl);
965 967
966 968 if (rl)
967 969 filter_top_rl(remaining_cases, rl);
968 970 else
969 971 rl = clone_rl(top_rl(*remaining_cases));
970 972
971 973 if (name) {
972 974 sm = get_sm_state_stree(*raw_stree, SMATCH_EXTRA, name, sym);
973 975 if (sm)
974 976 separate_and_filter(sm, SPECIAL_EQUAL, rl, *raw_stree, &true_states, &false_states, NULL);
975 977 }
976 978
977 979 __push_fake_cur_stree();
978 980 __unnullify_path();
979 981 if (name)
980 982 set_extra_nomod_vsl(name, sym, vsl, NULL, alloc_estate_rl(rl));
981 983 __pass_case_to_client(switch_expr, rl);
982 984 extra_states = __pop_fake_cur_stree();
983 985 overwrite_stree(extra_states, &true_states);
984 986 overwrite_stree(true_states, &ret);
985 987 free_stree(&extra_states);
986 988 free_stree(&true_states);
987 989 free_stree(&false_states);
988 990
989 991 free_string(name);
990 992 return ret;
991 993 }
992 994
993 995 static void match_end_func(struct symbol *sym)
994 996 {
995 997 if (__inline_fn)
996 998 return;
997 999 implied_debug_msg = NULL;
998 1000 }
999 1001
1000 1002 static void get_tf_stacks_from_pool(struct sm_state *gate_sm,
1001 1003 struct sm_state *pool_sm,
1002 1004 struct state_list **true_stack,
1003 1005 struct state_list **false_stack)
1004 1006 {
1005 1007 struct sm_state *tmp;
1006 1008 int possibly_true = 0;
1007 1009
1008 1010 if (!gate_sm)
1009 1011 return;
1010 1012
1011 1013 if (strcmp(gate_sm->state->name, pool_sm->state->name) == 0) {
1012 1014 add_ptr_list(true_stack, pool_sm);
1013 1015 return;
1014 1016 }
1015 1017
1016 1018 FOR_EACH_PTR(gate_sm->possible, tmp) {
1017 1019 if (strcmp(tmp->state->name, pool_sm->state->name) == 0) {
1018 1020 possibly_true = 1;
1019 1021 break;
1020 1022 }
1021 1023 } END_FOR_EACH_PTR(tmp);
1022 1024
1023 1025 if (!possibly_true) {
1024 1026 add_ptr_list(false_stack, gate_sm);
1025 1027 return;
1026 1028 }
1027 1029
1028 1030 get_tf_stacks_from_pool(gate_sm->left, pool_sm, true_stack, false_stack);
1029 1031 get_tf_stacks_from_pool(gate_sm->right, pool_sm, true_stack, false_stack);
1030 1032 }
1031 1033
1032 1034 /*
1033 1035 * The situation is we have a SMATCH_EXTRA state and we want to break it into
1034 1036 * each of the ->possible states and find the implications of each. The caller
1035 1037 * has to use __push_fake_cur_stree() to preserve the correct states so they
1036 1038 * can be restored later.
1037 1039 */
1038 1040 void overwrite_states_using_pool(struct sm_state *gate_sm, struct sm_state *pool_sm)
1039 1041 {
1040 1042 struct state_list *true_stack = NULL;
1041 1043 struct state_list *false_stack = NULL;
1042 1044 struct stree *pre_stree;
1043 1045 struct stree *implied_true;
1044 1046 struct sm_state *tmp;
1045 1047
1046 1048 if (!pool_sm->pool)
1047 1049 return;
1048 1050
1049 1051 get_tf_stacks_from_pool(gate_sm, pool_sm, &true_stack, &false_stack);
1050 1052
1051 1053 pre_stree = clone_stree(__get_cur_stree());
1052 1054
1053 1055 implied_true = filter_stack(gate_sm, pre_stree, false_stack, true_stack);
1054 1056
1055 1057 free_stree(&pre_stree);
1056 1058 free_slist(&true_stack);
1057 1059 free_slist(&false_stack);
1058 1060
1059 1061 FOR_EACH_SM(implied_true, tmp) {
1060 1062 set_state(tmp->owner, tmp->name, tmp->sym, tmp->state);
1061 1063 } END_FOR_EACH_SM(tmp);
1062 1064
1063 1065 free_stree(&implied_true);
1064 1066 }
1065 1067
1066 1068 int assume(struct expression *expr)
1067 1069 {
1068 1070 int orig_final_pass = final_pass;
1069 1071
1070 1072 in_fake_env++;
1071 1073 final_pass = 0;
1072 1074 __push_fake_cur_stree();
1073 1075 found_implications = 0;
1074 1076 __split_whole_condition(expr);
1075 1077 final_pass = orig_final_pass;
1076 1078 in_fake_env--;
1077 1079
1078 1080 return 1;
1079 1081 }
1080 1082
1081 1083 void end_assume(void)
1082 1084 {
1083 1085 __discard_false_states();
1084 1086 __free_fake_cur_stree();
1085 1087 }
1086 1088
1087 1089 int impossible_assumption(struct expression *left, int op, sval_t sval)
1088 1090 {
1089 1091 struct expression *value;
1090 1092 struct expression *comparison;
1091 1093 int ret;
1092 1094
1093 1095 value = value_expr(sval.value);
1094 1096 comparison = compare_expression(left, op, value);
1095 1097
1096 1098 if (!assume(comparison))
1097 1099 return 0;
1098 1100 ret = is_impossible_path();
1099 1101 end_assume();
1100 1102
1101 1103 return ret;
1102 1104 }
1103 1105
1104 1106 void __extra_match_condition(struct expression *expr);
1105 1107 void __comparison_match_condition(struct expression *expr);
1106 1108 void __stored_condition(struct expression *expr);
1107 1109 void register_implications(int id)
1108 1110 {
1109 1111 add_hook(&save_implications_hook, CONDITION_HOOK);
1110 1112 add_hook(&set_implied_states, CONDITION_HOOK);
1111 1113 add_hook(&__extra_match_condition, CONDITION_HOOK);
1112 1114 add_hook(&set_extra_implied_states, CONDITION_HOOK);
1113 1115 add_hook(&__comparison_match_condition, CONDITION_HOOK);
1114 1116 add_hook(&__stored_condition, CONDITION_HOOK);
1115 1117 add_hook(&match_end_func, END_FUNC_HOOK);
1116 1118 }
|
↓ open down ↓ |
510 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX