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_states.c
+++ new/usr/src/tools/smatch/src/smatch_states.c
1 1 /*
2 2 * Copyright (C) 2006 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
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 * You have a lists of states. kernel = locked, foo = NULL, ...
20 20 * When you hit an if {} else {} statement then you swap the list
21 21 * of states for a different list of states. The lists are stored
22 22 * on stacks.
23 23 *
24 24 * At the beginning of this file there are list of the stacks that
25 25 * we use. Each function in this file does something to one of
26 26 * of the stacks.
27 27 *
28 28 * So the smatch_flow.c understands code but it doesn't understand states.
29 29 * smatch_flow calls functions in this file. This file calls functions
30 30 * in smatch_slist.c which just has boring generic plumbing for handling
31 31 * state lists. But really it's this file where all the magic happens.
32 32 */
33 33
34 34 #include <stdlib.h>
35 35 #include <stdio.h>
36 36 #include "smatch.h"
37 37 #include "smatch_slist.h"
38 38 #include "smatch_extra.h"
39 39
40 40 struct smatch_state undefined = { .name = "undefined" };
41 41 struct smatch_state ghost = { .name = "ghost" };
42 42 struct smatch_state merged = { .name = "merged" };
43 43 struct smatch_state true_state = { .name = "true" };
44 44 struct smatch_state false_state = { .name = "false" };
45 45
46 46 static struct stree *cur_stree; /* current states */
47 47 static struct stree *fast_overlay;
48 48
49 49 static struct stree_stack *true_stack; /* states after a t/f branch */
50 50 static struct stree_stack *false_stack;
51 51 static struct stree_stack *pre_cond_stack; /* states before a t/f branch */
52 52
53 53 static struct stree_stack *cond_true_stack; /* states affected by a branch */
54 54 static struct stree_stack *cond_false_stack;
55 55
56 56 static struct stree_stack *fake_cur_stree_stack;
57 57 static int read_only;
58 58
59 59 static struct stree_stack *break_stack;
60 60 static struct stree_stack *fake_break_stack;
61 61 static struct stree_stack *switch_stack;
62 62 static struct range_list_stack *remaining_cases;
63 63 static struct stree_stack *default_stack;
64 64 static struct stree_stack *continue_stack;
65 65
66 66 static struct named_stree_stack *goto_stack;
↓ open down ↓ |
66 lines elided |
↑ open up ↑ |
67 67
68 68 static struct ptr_list *backup;
69 69
70 70 int option_debug;
71 71
72 72 void __print_cur_stree(void)
73 73 {
74 74 __print_stree(cur_stree);
75 75 }
76 76
77 +bool __print_states(const char *owner)
78 +{
79 + struct sm_state *sm;
80 + bool found = false;
81 +
82 + if (!owner)
83 + return false;
84 +
85 + FOR_EACH_SM(__get_cur_stree(), sm) {
86 + if (!strstr(check_name(sm->owner), owner))
87 + continue;
88 + sm_msg("%s", show_sm(sm));
89 + found = true;
90 + } END_FOR_EACH_SM(sm);
91 +
92 + return found;
93 +}
94 +
77 95 int unreachable(void)
78 96 {
79 97 if (!cur_stree)
80 98 return 1;
81 99 return 0;
82 100 }
83 101
84 102 void __set_cur_stree_readonly(void)
85 103 {
86 104 read_only++;
87 105 }
88 106
89 107 void __set_cur_stree_writable(void)
90 108 {
91 109 read_only--;
92 110 }
93 111
112 +DECLARE_PTR_LIST(check_tracker_list, check_tracker_hook *);
113 +static struct check_tracker_list **tracker_hooks;
114 +
115 +void add_check_tracker(const char *check_name, check_tracker_hook *fn)
116 +{
117 + check_tracker_hook **p;
118 + int owner;
119 +
120 + owner = id_from_name(check_name);
121 + if (!owner) {
122 + printf("check not found. '%s'\n", check_name);
123 + return;
124 + }
125 +
126 + p = malloc(sizeof(check_tracker_hook *));
127 + *p = fn;
128 + add_ptr_list(&tracker_hooks[owner], p);
129 +}
130 +
131 +static void call_tracker_hooks(int owner, const char *name, struct symbol *sym, struct smatch_state *state)
132 +{
133 + struct check_tracker_list *hooks;
134 + check_tracker_hook **fn;
135 +
136 + if ((unsigned short)owner == USHRT_MAX)
137 + return;
138 +
139 + hooks = tracker_hooks[owner];
140 + FOR_EACH_PTR(hooks, fn) {
141 + (*fn)(owner, name, sym, state);
142 + } END_FOR_EACH_PTR(fn);
143 +}
144 +
145 +void allocate_tracker_array(int num_checks)
146 +{
147 + tracker_hooks = malloc(num_checks * sizeof(void *));
148 + memset(tracker_hooks, 0, num_checks * sizeof(void *));
149 +}
150 +
94 151 struct sm_state *set_state(int owner, const char *name, struct symbol *sym, struct smatch_state *state)
95 152 {
96 153 struct sm_state *ret;
97 154
98 155 if (!name || !state)
99 156 return NULL;
100 157
101 158 if (read_only)
102 159 sm_perror("cur_stree is read only.");
103 160
104 161 if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
105 162 struct smatch_state *s;
106 163
↓ open down ↓ |
3 lines elided |
↑ open up ↑ |
107 164 s = __get_state(owner, name, sym);
108 165 if (!s)
109 166 sm_msg("%s new [%s] '%s' %s", __func__,
110 167 check_name(owner), name, show_state(state));
111 168 else
112 169 sm_msg("%s change [%s] '%s' %s => %s",
113 170 __func__, check_name(owner), name, show_state(s),
114 171 show_state(state));
115 172 }
116 173
174 + call_tracker_hooks(owner, name, sym, state);
175 +
117 176 if (owner != -1 && unreachable())
118 177 return NULL;
119 178
120 179 if (fake_cur_stree_stack)
121 180 set_state_stree_stack(&fake_cur_stree_stack, owner, name, sym, state);
122 181
123 182 ret = set_state_stree(&cur_stree, owner, name, sym, state);
124 183
125 184 return ret;
126 185 }
127 186
128 187 struct sm_state *set_state_expr(int owner, struct expression *expr, struct smatch_state *state)
129 188 {
130 189 char *name;
131 190 struct symbol *sym;
132 191 struct sm_state *ret = NULL;
133 192
134 193 expr = strip_expr(expr);
135 194 name = expr_to_var_sym(expr, &sym);
136 195 if (!name || !sym)
137 196 goto free;
138 197 ret = set_state(owner, name, sym, state);
139 198 free:
140 199 free_string(name);
141 200 return ret;
142 201 }
143 202
144 203 struct stree *__swap_cur_stree(struct stree *stree)
145 204 {
146 205 struct stree *orig = cur_stree;
147 206
148 207 cur_stree = stree;
149 208 return orig;
150 209 }
151 210
152 211 void __push_fake_cur_stree(void)
153 212 {
154 213 push_stree(&fake_cur_stree_stack, NULL);
155 214 __save_pre_cond_states();
156 215 }
157 216
158 217 struct stree *__pop_fake_cur_stree(void)
159 218 {
160 219 if (!fake_cur_stree_stack)
161 220 sm_perror("popping too many fake cur strees.");
162 221 __use_pre_cond_states();
163 222 return pop_stree(&fake_cur_stree_stack);
164 223 }
165 224
166 225 void __free_fake_cur_stree(void)
167 226 {
168 227 struct stree *stree;
169 228
170 229 stree = __pop_fake_cur_stree();
171 230 free_stree(&stree);
172 231 }
173 232
174 233 void __set_fake_cur_stree_fast(struct stree *stree)
175 234 {
176 235 if (fast_overlay) {
177 236 sm_perror("cannot nest fast overlay");
178 237 return;
179 238 }
180 239 fast_overlay = stree;
181 240 set_fast_math_only();
182 241 }
183 242
184 243 void __pop_fake_cur_stree_fast(void)
185 244 {
186 245 fast_overlay = NULL;
187 246 clear_fast_math_only();
188 247 }
189 248
190 249 void __merge_stree_into_cur(struct stree *stree)
191 250 {
192 251 struct sm_state *sm;
193 252 struct sm_state *orig;
194 253 struct sm_state *merged;
195 254
196 255 FOR_EACH_SM(stree, sm) {
197 256 orig = get_sm_state(sm->owner, sm->name, sm->sym);
198 257 if (orig)
199 258 merged = merge_sm_states(orig, sm);
200 259 else
201 260 merged = sm;
202 261 __set_sm(merged);
203 262 } END_FOR_EACH_SM(sm);
204 263 }
205 264
206 265 void __set_sm(struct sm_state *sm)
207 266 {
208 267 if (read_only)
209 268 sm_perror("cur_stree is read only.");
210 269
211 270 if (option_debug ||
212 271 strcmp(check_name(sm->owner), option_debug_check) == 0) {
213 272 struct smatch_state *s;
214 273
215 274 s = __get_state(sm->owner, sm->name, sm->sym);
216 275 if (!s)
217 276 sm_msg("%s new %s", __func__, show_sm(sm));
218 277 else
219 278 sm_msg("%s change %s (was %s)", __func__, show_sm(sm),
220 279 show_state(s));
221 280 }
222 281
223 282 if (unreachable())
224 283 return;
225 284
226 285 if (fake_cur_stree_stack)
227 286 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
228 287
229 288 overwrite_sm_state_stree(&cur_stree, sm);
230 289 }
231 290
232 291 void __set_sm_cur_stree(struct sm_state *sm)
233 292 {
234 293 if (read_only)
235 294 sm_perror("cur_stree is read only.");
236 295
237 296 if (option_debug ||
238 297 strcmp(check_name(sm->owner), option_debug_check) == 0) {
239 298 struct smatch_state *s;
240 299
241 300 s = __get_state(sm->owner, sm->name, sm->sym);
242 301 if (!s)
243 302 sm_msg("%s new %s", __func__, show_sm(sm));
244 303 else
245 304 sm_msg("%s change %s (was %s)",
246 305 __func__, show_sm(sm), show_state(s));
247 306 }
248 307
249 308 if (unreachable())
250 309 return;
251 310
252 311 overwrite_sm_state_stree(&cur_stree, sm);
253 312 }
254 313
255 314 void __set_sm_fake_stree(struct sm_state *sm)
256 315 {
257 316 if (read_only)
258 317 sm_perror("cur_stree is read only.");
259 318
260 319 if (option_debug ||
261 320 strcmp(check_name(sm->owner), option_debug_check) == 0) {
262 321 struct smatch_state *s;
263 322
264 323 s = __get_state(sm->owner, sm->name, sm->sym);
265 324 if (!s)
266 325 sm_msg("%s new %s", __func__, show_sm(sm));
267 326 else
268 327 sm_msg("%s change %s (was %s)",
269 328 __func__, show_sm(sm), show_state(s));
270 329 }
271 330
272 331 if (unreachable())
273 332 return;
274 333
275 334 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
276 335 }
277 336
278 337
279 338 typedef void (get_state_hook)(int owner, const char *name, struct symbol *sym);
280 339 DECLARE_PTR_LIST(fn_list, get_state_hook *);
281 340 static struct fn_list *get_state_hooks;
282 341
283 342 void add_get_state_hook(get_state_hook *fn)
284 343 {
285 344 get_state_hook **p = malloc(sizeof(get_state_hook *));
286 345 *p = fn;
287 346 add_ptr_list(&get_state_hooks, p);
288 347 }
289 348
290 349 static void call_get_state_hooks(int owner, const char *name, struct symbol *sym)
291 350 {
292 351 static int recursion;
293 352 get_state_hook **fn;
294 353
295 354 if (recursion)
296 355 return;
297 356 recursion = 1;
298 357
299 358 FOR_EACH_PTR(get_state_hooks, fn) {
300 359 (*fn)(owner, name, sym);
301 360 } END_FOR_EACH_PTR(fn);
302 361
303 362 recursion = 0;
304 363 }
305 364
306 365 struct smatch_state *__get_state(int owner, const char *name, struct symbol *sym)
307 366 {
308 367 struct sm_state *sm;
309 368
310 369 sm = get_sm_state(owner, name, sym);
311 370 if (!sm)
312 371 return NULL;
313 372 return sm->state;
314 373 }
315 374
316 375 struct smatch_state *get_state(int owner, const char *name, struct symbol *sym)
317 376 {
318 377 call_get_state_hooks(owner, name, sym);
319 378
320 379 return __get_state(owner, name, sym);
321 380 }
322 381
323 382 struct smatch_state *get_state_expr(int owner, struct expression *expr)
324 383 {
325 384 char *name;
326 385 struct symbol *sym;
327 386 struct smatch_state *ret = NULL;
328 387
329 388 expr = strip_expr(expr);
330 389 name = expr_to_var_sym(expr, &sym);
331 390 if (!name || !sym)
332 391 goto free;
333 392 ret = get_state(owner, name, sym);
334 393 free:
335 394 free_string(name);
336 395 return ret;
337 396 }
338 397
339 398 struct state_list *get_possible_states(int owner, const char *name, struct symbol *sym)
340 399 {
341 400 struct sm_state *sms;
342 401
343 402 sms = get_sm_state_stree(cur_stree, owner, name, sym);
344 403 if (sms)
345 404 return sms->possible;
346 405 return NULL;
347 406 }
348 407
349 408 struct state_list *get_possible_states_expr(int owner, struct expression *expr)
350 409 {
351 410 char *name;
352 411 struct symbol *sym;
353 412 struct state_list *ret = NULL;
354 413
355 414 expr = strip_expr(expr);
356 415 name = expr_to_var_sym(expr, &sym);
357 416 if (!name || !sym)
358 417 goto free;
359 418 ret = get_possible_states(owner, name, sym);
360 419 free:
361 420 free_string(name);
362 421 return ret;
363 422 }
364 423
365 424 struct sm_state *get_sm_state(int owner, const char *name, struct symbol *sym)
366 425 {
367 426 struct sm_state *ret;
368 427
369 428 ret = get_sm_state_stree(fast_overlay, owner, name, sym);
370 429 if (ret)
371 430 return ret;
372 431
373 432 return get_sm_state_stree(cur_stree, owner, name, sym);
374 433 }
375 434
376 435 struct sm_state *get_sm_state_expr(int owner, struct expression *expr)
377 436 {
378 437 char *name;
379 438 struct symbol *sym;
380 439 struct sm_state *ret = NULL;
381 440
382 441 expr = strip_expr(expr);
383 442 name = expr_to_var_sym(expr, &sym);
384 443 if (!name || !sym)
385 444 goto free;
386 445 ret = get_sm_state(owner, name, sym);
387 446 free:
388 447 free_string(name);
389 448 return ret;
390 449 }
391 450
392 451 void delete_state(int owner, const char *name, struct symbol *sym)
393 452 {
394 453 delete_state_stree(&cur_stree, owner, name, sym);
395 454 if (cond_true_stack) {
396 455 delete_state_stree_stack(&pre_cond_stack, owner, name, sym);
397 456 delete_state_stree_stack(&cond_true_stack, owner, name, sym);
398 457 delete_state_stree_stack(&cond_false_stack, owner, name, sym);
399 458 }
400 459 }
401 460
402 461 void delete_state_expr(int owner, struct expression *expr)
403 462 {
404 463 char *name;
405 464 struct symbol *sym;
406 465
407 466 expr = strip_expr(expr);
408 467 name = expr_to_var_sym(expr, &sym);
409 468 if (!name || !sym)
410 469 goto free;
411 470 delete_state(owner, name, sym);
412 471 free:
413 472 free_string(name);
414 473 }
415 474
416 475 static void delete_all_states_stree_sym(struct stree **stree, struct symbol *sym)
417 476 {
418 477 struct state_list *slist = NULL;
419 478 struct sm_state *sm;
420 479
421 480 FOR_EACH_SM(*stree, sm) {
422 481 if (sm->sym == sym)
423 482 add_ptr_list(&slist, sm);
424 483 } END_FOR_EACH_SM(sm);
425 484
426 485 FOR_EACH_PTR(slist, sm) {
427 486 delete_state_stree(stree, sm->owner, sm->name, sm->sym);
428 487 } END_FOR_EACH_PTR(sm);
429 488
430 489 free_slist(&slist);
431 490 }
432 491
433 492 static void delete_all_states_stree_stack_sym(struct stree_stack **stack, struct symbol *sym)
434 493 {
435 494 struct stree *stree;
436 495
437 496 if (!*stack)
438 497 return;
439 498
440 499 stree = pop_stree(stack);
441 500 delete_all_states_stree_sym(&stree, sym);
442 501 push_stree(stack, stree);
443 502 }
444 503
445 504 void __delete_all_states_sym(struct symbol *sym)
446 505 {
447 506 delete_all_states_stree_sym(&cur_stree, sym);
448 507
449 508 delete_all_states_stree_stack_sym(&true_stack, sym);
450 509 delete_all_states_stree_stack_sym(&true_stack, sym);
451 510 delete_all_states_stree_stack_sym(&false_stack, sym);
452 511 delete_all_states_stree_stack_sym(&pre_cond_stack, sym);
453 512 delete_all_states_stree_stack_sym(&cond_true_stack, sym);
454 513 delete_all_states_stree_stack_sym(&cond_false_stack, sym);
455 514 delete_all_states_stree_stack_sym(&fake_cur_stree_stack, sym);
456 515 delete_all_states_stree_stack_sym(&break_stack, sym);
457 516 delete_all_states_stree_stack_sym(&fake_break_stack, sym);
458 517 delete_all_states_stree_stack_sym(&switch_stack, sym);
459 518 delete_all_states_stree_stack_sym(&continue_stack, sym);
460 519
461 520 /*
462 521 * deleting from the goto stack is problematic because we don't know
463 522 * if the label is in scope and also we need the value for --two-passes.
464 523 */
465 524 }
466 525
467 526 struct stree *get_all_states_from_stree(int owner, struct stree *source)
468 527 {
469 528 struct stree *ret = NULL;
470 529 struct sm_state *tmp;
471 530
472 531 FOR_EACH_SM(source, tmp) {
473 532 if (tmp->owner == owner)
474 533 avl_insert(&ret, tmp);
475 534 } END_FOR_EACH_SM(tmp);
476 535
477 536 return ret;
478 537 }
479 538
480 539 struct stree *get_all_states_stree(int owner)
481 540 {
482 541 return get_all_states_from_stree(owner, cur_stree);
483 542 }
484 543
485 544 struct stree *__get_cur_stree(void)
486 545 {
487 546 return cur_stree;
488 547 }
489 548
490 549 int is_reachable(void)
491 550 {
492 551 if (cur_stree)
493 552 return 1;
494 553 return 0;
495 554 }
496 555
497 556 void set_true_false_states(int owner, const char *name, struct symbol *sym,
498 557 struct smatch_state *true_state,
499 558 struct smatch_state *false_state)
500 559 {
501 560 if (read_only)
502 561 sm_perror("cur_stree is read only.");
503 562
504 563 if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
505 564 struct smatch_state *tmp;
506 565
507 566 tmp = __get_state(owner, name, sym);
508 567 sm_msg("%s [%s] '%s'. Was %s. Now T:%s F:%s", __func__,
509 568 check_name(owner), name, show_state(tmp),
510 569 show_state(true_state), show_state(false_state));
511 570 }
512 571
513 572 if (unreachable())
514 573 return;
515 574
516 575 if (!cond_false_stack || !cond_true_stack) {
517 576 sm_perror("missing true/false stacks");
518 577 return;
519 578 }
520 579
521 580 if (true_state)
522 581 set_state_stree_stack(&cond_true_stack, owner, name, sym, true_state);
523 582 if (false_state)
524 583 set_state_stree_stack(&cond_false_stack, owner, name, sym, false_state);
525 584 }
526 585
527 586 void set_true_false_states_expr(int owner, struct expression *expr,
528 587 struct smatch_state *true_state,
529 588 struct smatch_state *false_state)
530 589 {
531 590 char *name;
532 591 struct symbol *sym;
533 592
534 593 expr = strip_expr(expr);
535 594 name = expr_to_var_sym(expr, &sym);
536 595 if (!name || !sym)
537 596 goto free;
538 597 set_true_false_states(owner, name, sym, true_state, false_state);
539 598 free:
540 599 free_string(name);
541 600 }
542 601
543 602 void __set_true_false_sm(struct sm_state *true_sm, struct sm_state *false_sm)
544 603 {
545 604 int owner;
546 605 const char *name;
547 606 struct symbol *sym;
548 607
549 608 if (!true_sm && !false_sm)
550 609 return;
551 610
552 611 if (unreachable())
553 612 return;
554 613
555 614 owner = true_sm ? true_sm->owner : false_sm->owner;
556 615 name = true_sm ? true_sm->name : false_sm->name;
557 616 sym = true_sm ? true_sm->sym : false_sm->sym;
558 617 if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
559 618 struct smatch_state *tmp;
560 619
561 620 tmp = __get_state(owner, name, sym);
562 621 sm_msg("%s [%s] '%s'. Was %s. Now T:%s F:%s", __func__,
563 622 check_name(owner), name, show_state(tmp),
564 623 show_state(true_sm ? true_sm->state : NULL),
565 624 show_state(false_sm ? false_sm->state : NULL));
566 625 }
567 626
568 627 if (!cond_false_stack || !cond_true_stack) {
569 628 sm_perror("missing true/false stacks");
570 629 return;
571 630 }
572 631
573 632 if (true_sm)
574 633 overwrite_sm_state_stree_stack(&cond_true_stack, true_sm);
575 634 if (false_sm)
576 635 overwrite_sm_state_stree_stack(&cond_false_stack, false_sm);
577 636 }
578 637
579 638 void nullify_path(void)
580 639 {
581 640 if (fake_cur_stree_stack) {
582 641 __free_fake_cur_stree();
583 642 __push_fake_cur_stree();
584 643 }
585 644 free_stree(&cur_stree);
586 645 }
587 646
588 647 void __match_nullify_path_hook(const char *fn, struct expression *expr,
589 648 void *unused)
590 649 {
591 650 nullify_path();
592 651 }
593 652
594 653 /*
595 654 * At the start of every function we mark the path
596 655 * as unnull. That way there is always at least one state
597 656 * in the cur_stree until nullify_path is called. This
598 657 * is used in merge_slist() for the first null check.
599 658 */
600 659 void __unnullify_path(void)
601 660 {
602 661 if (!cur_stree)
603 662 set_state(-1, "unnull_path", NULL, &true_state);
604 663 }
605 664
606 665 int __path_is_null(void)
607 666 {
608 667 if (cur_stree)
609 668 return 0;
610 669 return 1;
611 670 }
612 671
613 672 static void check_stree_stack_free(struct stree_stack **stack)
614 673 {
615 674 if (*stack) {
616 675 sm_perror("stack not empty");
617 676 free_stack_and_strees(stack);
618 677 }
619 678 }
620 679
621 680 void save_all_states(void)
622 681 {
623 682 __add_ptr_list(&backup, cur_stree);
624 683 cur_stree = NULL;
625 684
626 685 __add_ptr_list(&backup, true_stack);
627 686 true_stack = NULL;
628 687 __add_ptr_list(&backup, false_stack);
629 688 false_stack = NULL;
630 689 __add_ptr_list(&backup, pre_cond_stack);
631 690 pre_cond_stack = NULL;
632 691
633 692 __add_ptr_list(&backup, cond_true_stack);
634 693 cond_true_stack = NULL;
635 694 __add_ptr_list(&backup, cond_false_stack);
636 695 cond_false_stack = NULL;
637 696
638 697 __add_ptr_list(&backup, fake_cur_stree_stack);
639 698 fake_cur_stree_stack = NULL;
640 699
641 700 __add_ptr_list(&backup, break_stack);
642 701 break_stack = NULL;
643 702 __add_ptr_list(&backup, fake_break_stack);
644 703 fake_break_stack = NULL;
645 704
646 705 __add_ptr_list(&backup, switch_stack);
647 706 switch_stack = NULL;
648 707 __add_ptr_list(&backup, remaining_cases);
649 708 remaining_cases = NULL;
650 709 __add_ptr_list(&backup, default_stack);
651 710 default_stack = NULL;
652 711 __add_ptr_list(&backup, continue_stack);
653 712 continue_stack = NULL;
654 713
655 714 __add_ptr_list(&backup, goto_stack);
656 715 goto_stack = NULL;
657 716 }
658 717
659 718 static void *pop_backup(void)
660 719 {
661 720 void *ret;
662 721
663 722 ret = last_ptr_list(backup);
664 723 delete_ptr_list_last(&backup);
665 724 return ret;
666 725 }
667 726
668 727 void restore_all_states(void)
669 728 {
670 729 goto_stack = pop_backup();
671 730
672 731 continue_stack = pop_backup();
673 732 default_stack = pop_backup();
674 733 remaining_cases = pop_backup();
675 734 switch_stack = pop_backup();
676 735 fake_break_stack = pop_backup();
677 736 break_stack = pop_backup();
678 737
679 738 fake_cur_stree_stack = pop_backup();
680 739
681 740 cond_false_stack = pop_backup();
682 741 cond_true_stack = pop_backup();
683 742
684 743 pre_cond_stack = pop_backup();
685 744 false_stack = pop_backup();
686 745 true_stack = pop_backup();
687 746
688 747 cur_stree = pop_backup();
689 748 }
690 749
691 750 void free_goto_stack(void)
692 751 {
693 752 struct named_stree *named_stree;
694 753
695 754 FOR_EACH_PTR(goto_stack, named_stree) {
696 755 free_stree(&named_stree->stree);
697 756 } END_FOR_EACH_PTR(named_stree);
698 757 __free_ptr_list((struct ptr_list **)&goto_stack);
699 758 }
700 759
701 760 void clear_all_states(void)
702 761 {
703 762 nullify_path();
704 763 check_stree_stack_free(&true_stack);
705 764 check_stree_stack_free(&false_stack);
706 765 check_stree_stack_free(&pre_cond_stack);
707 766 check_stree_stack_free(&cond_true_stack);
708 767 check_stree_stack_free(&cond_false_stack);
709 768 check_stree_stack_free(&break_stack);
710 769 check_stree_stack_free(&fake_break_stack);
711 770 check_stree_stack_free(&switch_stack);
712 771 check_stree_stack_free(&continue_stack);
713 772 check_stree_stack_free(&fake_cur_stree_stack);
714 773
715 774 free_goto_stack();
716 775
717 776 free_every_single_sm_state();
718 777 free_tmp_expressions();
719 778 }
720 779
721 780 void __push_cond_stacks(void)
722 781 {
723 782 push_stree(&cond_true_stack, NULL);
724 783 push_stree(&cond_false_stack, NULL);
725 784 __push_fake_cur_stree();
726 785 }
727 786
728 787 void __fold_in_set_states(void)
729 788 {
730 789 struct stree *new_states;
731 790 struct sm_state *sm;
732 791
733 792 new_states = __pop_fake_cur_stree();
734 793 FOR_EACH_SM(new_states, sm) {
735 794 __set_sm(sm);
736 795 __set_true_false_sm(sm, sm);
737 796 } END_FOR_EACH_SM(sm);
738 797 free_stree(&new_states);
739 798 }
740 799
741 800 void __free_set_states(void)
742 801 {
743 802 struct stree *new_states;
744 803
745 804 new_states = __pop_fake_cur_stree();
746 805 free_stree(&new_states);
747 806 }
748 807
749 808 struct stree *__copy_cond_true_states(void)
750 809 {
751 810 struct stree *ret;
752 811
753 812 ret = pop_stree(&cond_true_stack);
754 813 push_stree(&cond_true_stack, clone_stree(ret));
755 814 return ret;
756 815 }
757 816
758 817 struct stree *__copy_cond_false_states(void)
759 818 {
760 819 struct stree *ret;
761 820
762 821 ret = pop_stree(&cond_false_stack);
763 822 push_stree(&cond_false_stack, clone_stree(ret));
764 823 return ret;
765 824 }
766 825
767 826 struct stree *__pop_cond_true_stack(void)
768 827 {
769 828 return pop_stree(&cond_true_stack);
770 829 }
771 830
772 831 struct stree *__pop_cond_false_stack(void)
773 832 {
774 833 return pop_stree(&cond_false_stack);
775 834 }
776 835
777 836 /*
778 837 * This combines the pre cond states with either the true or false states.
779 838 * For example:
780 839 * a = kmalloc() ; if (a !! foo(a)
781 840 * In the pre state a is possibly null. In the true state it is non null.
782 841 * In the false state it is null. Combine the pre and the false to get
783 842 * that when we call 'foo', 'a' is null.
784 843 */
785 844 static void __use_cond_stack(struct stree_stack **stack)
786 845 {
787 846 struct stree *stree;
788 847
789 848 free_stree(&cur_stree);
790 849
791 850 cur_stree = pop_stree(&pre_cond_stack);
792 851 push_stree(&pre_cond_stack, clone_stree(cur_stree));
793 852
794 853 stree = pop_stree(stack);
795 854 overwrite_stree(stree, &cur_stree);
796 855 push_stree(stack, stree);
797 856 }
798 857
799 858 void __use_pre_cond_states(void)
800 859 {
801 860 free_stree(&cur_stree);
802 861 cur_stree = pop_stree(&pre_cond_stack);
803 862 }
804 863
805 864 void __use_cond_true_states(void)
806 865 {
807 866 __use_cond_stack(&cond_true_stack);
808 867 }
809 868
810 869 void __use_cond_false_states(void)
811 870 {
812 871 __use_cond_stack(&cond_false_stack);
813 872 }
814 873
815 874 void __negate_cond_stacks(void)
816 875 {
817 876 struct stree *old_false, *old_true;
818 877
819 878 old_false = pop_stree(&cond_false_stack);
820 879 old_true = pop_stree(&cond_true_stack);
821 880 push_stree(&cond_false_stack, old_true);
822 881 push_stree(&cond_true_stack, old_false);
823 882 }
824 883
825 884 void __and_cond_states(void)
826 885 {
827 886 and_stree_stack(&cond_true_stack);
828 887 or_stree_stack(&pre_cond_stack, cur_stree, &cond_false_stack);
829 888 }
830 889
831 890 void __or_cond_states(void)
832 891 {
833 892 or_stree_stack(&pre_cond_stack, cur_stree, &cond_true_stack);
834 893 and_stree_stack(&cond_false_stack);
835 894 }
836 895
837 896 void __save_pre_cond_states(void)
838 897 {
839 898 push_stree(&pre_cond_stack, clone_stree(cur_stree));
840 899 }
841 900
842 901 void __discard_pre_cond_states(void)
843 902 {
844 903 struct stree *tmp;
845 904
846 905 tmp = pop_stree(&pre_cond_stack);
847 906 free_stree(&tmp);
848 907 }
849 908
850 909 struct stree *__get_true_states(void)
851 910 {
852 911 return clone_stree(top_stree(cond_true_stack));
853 912 }
854 913
855 914 struct stree *__get_false_states(void)
856 915 {
857 916 return clone_stree(top_stree(cond_false_stack));
858 917 }
859 918
860 919 void __use_cond_states(void)
861 920 {
862 921 struct stree *pre, *pre_clone, *true_states, *false_states;
863 922
864 923 pre = pop_stree(&pre_cond_stack);
865 924 pre_clone = clone_stree(pre);
866 925
867 926 true_states = pop_stree(&cond_true_stack);
868 927 overwrite_stree(true_states, &pre);
869 928 free_stree(&true_states);
870 929 /* we use the true states right away */
871 930 free_stree(&cur_stree);
872 931 cur_stree = pre;
873 932
874 933 false_states = pop_stree(&cond_false_stack);
875 934 overwrite_stree(false_states, &pre_clone);
876 935 free_stree(&false_states);
877 936 push_stree(&false_stack, pre_clone);
878 937 }
879 938
880 939 void __push_true_states(void)
881 940 {
882 941 push_stree(&true_stack, clone_stree(cur_stree));
883 942 }
884 943
885 944 void __use_false_states(void)
886 945 {
887 946 free_stree(&cur_stree);
888 947 cur_stree = pop_stree(&false_stack);
889 948 }
890 949
891 950 void __discard_false_states(void)
892 951 {
893 952 struct stree *stree;
894 953
895 954 stree = pop_stree(&false_stack);
896 955 free_stree(&stree);
897 956 }
898 957
899 958 void __merge_false_states(void)
900 959 {
901 960 struct stree *stree;
902 961
903 962 stree = pop_stree(&false_stack);
904 963 merge_stree(&cur_stree, stree);
905 964 free_stree(&stree);
906 965 }
907 966
908 967 /*
909 968 * This function probably seemed common sensical when I wrote it but, oh wow,
910 969 * does it look subtle in retrospect. Say we set a state on one side of the if
911 970 * else path but not on the other, then what we should record in the fake stree
912 971 * is the merged state.
913 972 *
914 973 * This function relies on the fact that the we always set the cur_stree as well
915 974 * and we already have the infrastructure to merge things correctly into the
916 975 * cur_stree.
917 976 *
918 977 * So instead of merging fake strees together which is probably a lot of work,
919 978 * we just use it as a list of set states and look up the actual current values
920 979 * in the cur_stree.
921 980 *
922 981 */
923 982 static void update_stree_with_merged(struct stree **stree)
924 983 {
925 984 struct state_list *slist = NULL;
926 985 struct sm_state *sm, *new;
927 986
928 987 FOR_EACH_SM(*stree, sm) {
929 988 new = get_sm_state(sm->owner, sm->name, sm->sym);
930 989 if (!new) /* This can happen if we go out of scope */
931 990 continue;
932 991 add_ptr_list(&slist, new);
933 992 } END_FOR_EACH_SM(sm);
934 993
935 994 FOR_EACH_PTR(slist, sm) {
936 995 overwrite_sm_state_stree(stree, sm);
937 996 } END_FOR_EACH_PTR(sm);
938 997
939 998 free_slist(&slist);
940 999 }
941 1000
942 1001 static void update_fake_stree_with_merged(void)
943 1002 {
944 1003 struct stree *stree;
945 1004
946 1005 if (!fake_cur_stree_stack)
947 1006 return;
948 1007 stree = pop_stree(&fake_cur_stree_stack);
949 1008 update_stree_with_merged(&stree);
950 1009 push_stree(&fake_cur_stree_stack, stree);
951 1010 }
952 1011
953 1012 void __merge_true_states(void)
954 1013 {
955 1014 struct stree *stree;
956 1015
957 1016 stree = pop_stree(&true_stack);
958 1017 merge_stree(&cur_stree, stree);
959 1018 update_fake_stree_with_merged();
960 1019 free_stree(&stree);
961 1020 }
962 1021
963 1022 void __push_continues(void)
964 1023 {
965 1024 push_stree(&continue_stack, NULL);
966 1025 }
967 1026
968 1027 void __discard_continues(void)
969 1028 {
970 1029 struct stree *stree;
971 1030
972 1031 stree = pop_stree(&continue_stack);
973 1032 free_stree(&stree);
974 1033 }
975 1034
976 1035 void __process_continues(void)
977 1036 {
978 1037 struct stree *stree;
979 1038
980 1039 stree = pop_stree(&continue_stack);
981 1040 if (!stree)
982 1041 stree = clone_stree(cur_stree);
983 1042 else
984 1043 merge_stree(&stree, cur_stree);
985 1044
986 1045 push_stree(&continue_stack, stree);
987 1046 }
988 1047
989 1048 void __merge_continues(void)
990 1049 {
991 1050 struct stree *stree;
992 1051
993 1052 stree = pop_stree(&continue_stack);
994 1053 merge_stree(&cur_stree, stree);
995 1054 free_stree(&stree);
996 1055 }
997 1056
998 1057 void __push_breaks(void)
999 1058 {
1000 1059 push_stree(&break_stack, NULL);
1001 1060 if (fake_cur_stree_stack)
1002 1061 push_stree(&fake_break_stack, NULL);
1003 1062 }
1004 1063
1005 1064 void __process_breaks(void)
1006 1065 {
1007 1066 struct stree *stree;
1008 1067
1009 1068 stree = pop_stree(&break_stack);
1010 1069 if (!stree)
1011 1070 stree = clone_stree(cur_stree);
1012 1071 else
1013 1072 merge_stree(&stree, cur_stree);
1014 1073 push_stree(&break_stack, stree);
1015 1074
1016 1075 if (!fake_cur_stree_stack)
1017 1076 return;
1018 1077
1019 1078 stree = pop_stree(&fake_break_stack);
1020 1079 if (!stree)
1021 1080 stree = clone_stree(top_stree(fake_cur_stree_stack));
1022 1081 else
1023 1082 merge_stree(&stree, top_stree(fake_cur_stree_stack));
1024 1083 push_stree(&fake_break_stack, stree);
1025 1084 }
1026 1085
1027 1086 int __has_breaks(void)
1028 1087 {
1029 1088 struct stree *stree;
1030 1089 int ret;
1031 1090
1032 1091 stree = pop_stree(&break_stack);
1033 1092 ret = !!stree;
1034 1093 push_stree(&break_stack, stree);
1035 1094 return ret;
1036 1095 }
1037 1096
1038 1097 void __merge_breaks(void)
1039 1098 {
1040 1099 struct stree *stree;
1041 1100 struct sm_state *sm;
1042 1101
1043 1102 stree = pop_stree(&break_stack);
1044 1103 merge_stree(&cur_stree, stree);
1045 1104 free_stree(&stree);
1046 1105
1047 1106 if (!fake_cur_stree_stack)
1048 1107 return;
1049 1108
1050 1109 stree = pop_stree(&fake_break_stack);
1051 1110 update_stree_with_merged(&stree);
1052 1111 FOR_EACH_SM(stree, sm) {
1053 1112 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
1054 1113 } END_FOR_EACH_SM(sm);
1055 1114 free_stree(&stree);
1056 1115 }
1057 1116
1058 1117 void __use_breaks(void)
1059 1118 {
1060 1119 struct stree *stree;
1061 1120 struct sm_state *sm;
1062 1121
1063 1122 free_stree(&cur_stree);
1064 1123 cur_stree = pop_stree(&break_stack);
1065 1124
1066 1125 if (!fake_cur_stree_stack)
1067 1126 return;
1068 1127 stree = pop_stree(&fake_break_stack);
1069 1128 FOR_EACH_SM(stree, sm) {
1070 1129 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
1071 1130 } END_FOR_EACH_SM(sm);
1072 1131 free_stree(&stree);
1073 1132
1074 1133
1075 1134 }
1076 1135
1077 1136 void __save_switch_states(struct expression *switch_expr)
1078 1137 {
1079 1138 struct range_list *rl;
1080 1139
1081 1140 get_absolute_rl(switch_expr, &rl);
1082 1141
1083 1142 push_rl(&remaining_cases, rl);
1084 1143 push_stree(&switch_stack, clone_stree(cur_stree));
1085 1144 }
1086 1145
1087 1146 int have_remaining_cases(void)
1088 1147 {
1089 1148 return !!top_rl(remaining_cases);
1090 1149 }
1091 1150
1092 1151 void __merge_switches(struct expression *switch_expr, struct range_list *case_rl)
1093 1152 {
1094 1153 struct stree *stree;
1095 1154 struct stree *implied_stree;
1096 1155
1097 1156 stree = pop_stree(&switch_stack);
1098 1157 if (!stree) {
1099 1158 /*
1100 1159 * If the cur_stree was NULL before the start of the switch
1101 1160 * statement then we don't want to unnullify it.
1102 1161 *
1103 1162 */
1104 1163 push_stree(&switch_stack, stree);
1105 1164 return;
1106 1165 }
1107 1166 implied_stree = __implied_case_stree(switch_expr, case_rl, &remaining_cases, &stree);
1108 1167 merge_stree(&cur_stree, implied_stree);
1109 1168 free_stree(&implied_stree);
1110 1169 push_stree(&switch_stack, stree);
1111 1170 }
1112 1171
1113 1172 void __discard_switches(void)
1114 1173 {
1115 1174 struct stree *stree;
1116 1175
1117 1176 pop_rl(&remaining_cases);
1118 1177 stree = pop_stree(&switch_stack);
1119 1178 free_stree(&stree);
1120 1179 }
1121 1180
1122 1181 void __push_default(void)
1123 1182 {
1124 1183 push_stree(&default_stack, NULL);
1125 1184 }
1126 1185
1127 1186 void __set_default(void)
1128 1187 {
1129 1188 set_state_stree_stack(&default_stack, 0, "has_default", NULL, &true_state);
1130 1189 }
1131 1190
1132 1191 int __pop_default(void)
1133 1192 {
1134 1193 struct stree *stree;
1135 1194
1136 1195 stree = pop_stree(&default_stack);
1137 1196 if (stree) {
1138 1197 free_stree(&stree);
1139 1198 return 1;
1140 1199 }
1141 1200 return 0;
1142 1201 }
1143 1202
1144 1203 static struct named_stree *alloc_named_stree(const char *name, struct symbol *sym, struct stree *stree)
1145 1204 {
1146 1205 struct named_stree *named_stree = __alloc_named_stree(0);
1147 1206
1148 1207 named_stree->name = (char *)name;
1149 1208 named_stree->stree = stree;
1150 1209 named_stree->sym = sym;
1151 1210 return named_stree;
1152 1211 }
1153 1212
1154 1213 void __save_gotos(const char *name, struct symbol *sym)
1155 1214 {
1156 1215 struct stree **stree;
1157 1216 struct stree *clone;
1158 1217
1159 1218 stree = get_named_stree(goto_stack, name, sym);
1160 1219 if (stree) {
1161 1220 merge_stree(stree, cur_stree);
1162 1221 return;
1163 1222 } else {
1164 1223 struct named_stree *named_stree;
1165 1224
1166 1225 clone = clone_stree(cur_stree);
1167 1226 named_stree = alloc_named_stree(name, sym, clone);
1168 1227 add_ptr_list(&goto_stack, named_stree);
1169 1228 }
1170 1229 }
1171 1230
1172 1231 void __merge_gotos(const char *name, struct symbol *sym)
1173 1232 {
1174 1233 struct stree **stree;
1175 1234
1176 1235 stree = get_named_stree(goto_stack, name, sym);
1177 1236 if (stree)
1178 1237 merge_stree(&cur_stree, *stree);
1179 1238 }
↓ open down ↓ |
1053 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX