1 /*
2 * Copyright (C) 2006,2008 Dan Carpenter.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16 */
17
18 /*
19 * The simplest type of condition is
20 * if (a) { ...
21 *
22 * The next simplest kind of conditions is
23 * if (a && b) { c;
24 * In that case 'a' is true when we get to 'b' and both are true
25 * when we get to c.
26 *
27 * Or's are a little more complicated.
28 * if (a || b) { c;
29 * We know 'a' is not true when we get to 'b' but it may be true
30 * when we get to c.
31 *
32 * If we mix and's and or's that's even more complicated.
33 * if (a && b && c || a && d) { d ;
34 * 'a' is true when we evaluate 'b', and 'd'.
35 * 'b' is true when we evaluate 'c' but otherwise we don't.
36 *
37 * The other thing that complicates matters is if we negate
38 * some if conditions.
39 * if (!a) { ...
40 * Smatch has passes the un-negated version to the client and flip
41 * the true and false values internally. This makes it easier
42 * to write checks.
43 *
44 * And negations can be part of a compound.
45 * if (a && !(b || c)) { d;
46 * In that situation we multiply the negative through to simplify
47 * stuff so that we can remove the parens like this:
48 * if (a && !b && !c) { d;
49 *
50 * One other thing is that:
51 * if ((a) != 0){ ...
52 * that's basically the same as testing for just 'a' and we simplify
53 * comparisons with zero before passing it to the script.
54 *
55 */
56
57 #include "smatch.h"
58 #include "smatch_slist.h"
59 #include "smatch_extra.h"
60 #include "smatch_expression_stacks.h"
61
62 extern int __expr_stmt_count;
63
64 struct expression_list *big_condition_stack;
65
66 static void split_conditions(struct expression *expr);
67
68 static int is_logical_and(struct expression *expr)
69 {
70 if (expr->op == SPECIAL_LOGICAL_AND)
71 return 1;
72 return 0;
73 }
74
75 static int handle_zero_comparisons(struct expression *expr)
76 {
77 struct expression *tmp = NULL;
78 struct expression *zero;
79
80 // if left is zero or right is zero
81 if (is_zero(expr->left)) {
82 zero = strip_expr(expr->left);
83 if (zero->type != EXPR_VALUE)
84 __split_expr(expr->left);
85 tmp = expr->right;
86 } else if (is_zero(expr->right)) {
87 zero = strip_expr(expr->left);
88 if (zero->type != EXPR_VALUE)
89 __split_expr(expr->right);
90 tmp = expr->left;
91 } else {
92 return 0;
93 }
94
95 // "if (foo != 0)" is the same as "if (foo)"
96 if (expr->op == SPECIAL_NOTEQUAL) {
97 split_conditions(tmp);
98 return 1;
99 }
100
101 // "if (foo == 0)" is the same as "if (!foo)"
102 if (expr->op == SPECIAL_EQUAL) {
103 split_conditions(tmp);
104 __negate_cond_stacks();
105 return 1;
106 }
107
108 return 0;
109 }
110
111 /*
112 * This function is for handling calls to likely/unlikely
113 */
114
115 static int ignore_builtin_expect(struct expression *expr)
116 {
117 if (sym_name_is("__builtin_expect", expr->fn)) {
118 split_conditions(first_ptr_list((struct ptr_list *) expr->args));
119 return 1;
120 }
121 return 0;
122 }
123
124 /*
125 * handle_compound_stmt() is for: foo = ({blah; blah; blah; 1})
126 */
127
128 static void handle_compound_stmt(struct statement *stmt)
129 {
130 struct expression *expr = NULL;
131 struct statement *last;
132 struct statement *s;
133
134 last = last_ptr_list((struct ptr_list *)stmt->stmts);
135 if (last->type == STMT_LABEL) {
136 if (last->label_statement &&
137 last->label_statement->type == STMT_EXPRESSION)
138 expr = last->label_statement->expression;
139 else
140 last = NULL;
141 } else if (last->type != STMT_EXPRESSION) {
142 last = NULL;
143 } else {
144 expr = last->expression;
145 }
146
147 FOR_EACH_PTR(stmt->stmts, s) {
148 if (s != last)
149 __split_stmt(s);
150 } END_FOR_EACH_PTR(s);
151 if (last && last->type == STMT_LABEL)
152 __split_label_stmt(last);
153 split_conditions(expr);
154 }
155
156 static int handle_preop(struct expression *expr)
157 {
158 struct statement *stmt;
159
160 if (expr->op == '!') {
161 split_conditions(expr->unop);
162 __negate_cond_stacks();
163 return 1;
164 }
165 stmt = get_expression_statement(expr);
166 if (stmt) {
167 handle_compound_stmt(stmt);
168 return 1;
169 }
170 return 0;
171 }
172
173 static void handle_logical(struct expression *expr)
174 {
175 /*
176 * If we come to an "and" expr then:
177 * We split the left side.
178 * We keep all the current states.
179 * We split the right side.
180 * We keep all the states from both true sides.
181 *
182 * If it's an "or" expr then:
183 * We save the current slist.
184 * We split the left side.
185 * We use the false states for the right side.
186 * We split the right side.
187 * We save all the states that are the same on both sides.
188 */
189
190 split_conditions(expr->left);
191
192 if (is_logical_and(expr))
193 __use_cond_true_states();
194 else
195 __use_cond_false_states();
196
197 __push_cond_stacks();
198
199 __save_pre_cond_states();
200 split_conditions(expr->right);
201 __discard_pre_cond_states();
202
203 if (is_logical_and(expr))
204 __and_cond_states();
205 else
206 __or_cond_states();
207
208 __use_cond_true_states();
209 }
210
211 static struct stree *combine_strees(struct stree *orig, struct stree *fake, struct stree *new)
212 {
213 struct stree *ret = NULL;
214
215 overwrite_stree(orig, &ret);
216 overwrite_stree(fake, &ret);
217 overwrite_stree(new, &ret);
218 free_stree(&new);
219
220 return ret;
221 }
222
223 /*
224 * handle_select()
225 * if ((aaa()?bbb():ccc())) { ...
226 *
227 * This is almost the same as:
228 * if ((aaa() && bbb()) || (!aaa() && ccc())) { ...
229 *
230 * It's a bit complicated because we shouldn't pass aaa()
231 * to the clients more than once.
232 */
233
234 static void handle_select(struct expression *expr)
235 {
236 struct stree *a_T = NULL;
237 struct stree *a_F = NULL;
238 struct stree *a_T_b_T = NULL;
239 struct stree *a_T_b_F = NULL;
240 struct stree *a_T_b_fake = NULL;
241 struct stree *a_F_c_T = NULL;
242 struct stree *a_F_c_F = NULL;
243 struct stree *a_F_c_fake = NULL;
244 struct stree *tmp;
245 struct sm_state *sm;
246
247 /*
248 * Imagine we have this: if (a ? b : c) { ...
249 *
250 * The condition is true if "a" is true and "b" is true or
251 * "a" is false and "c" is true. It's false if "a" is true
252 * and "b" is false or "a" is false and "c" is false.
253 *
254 * The variable name "a_T_b_T" stands for "a true b true" etc.
255 *
256 * But if we know "b" is true then we can simpilify things.
257 * The condition is true if "a" is true or if "a" is false and
258 * "c" is true. The only way the condition can be false is if
259 * "a" is false and "c" is false.
260 *
261 * The remaining thing is the "a_T_b_fake". When we simplify
262 * the equations we have to take into consideration that other
263 * states may have changed that don't play into the true false
264 * equation. Take the following example:
265 * if ({
266 * (flags) = __raw_local_irq_save();
267 * _spin_trylock(lock) ? 1 :
268 * ({ raw_local_irq_restore(flags); 0; });
269 * })
270 * Smatch has to record that the irq flags were restored on the
271 * false path.
272 *
273 */
274
275 __save_pre_cond_states();
276
277 split_conditions(expr->conditional);
278
279 a_T = __copy_cond_true_states();
280 a_F = __copy_cond_false_states();
281
282 __use_cond_true_states();
283
284 __push_cond_stacks();
285 __push_fake_cur_stree();
286 split_conditions(expr->cond_true);
287 __process_post_op_stack();
288 a_T_b_fake = __pop_fake_cur_stree();
289 a_T_b_T = combine_strees(a_T, a_T_b_fake, __pop_cond_true_stack());
290 a_T_b_F = combine_strees(a_T, a_T_b_fake, __pop_cond_false_stack());
291
292 __use_cond_false_states();
293
294 __push_cond_stacks();
295 __push_fake_cur_stree();
296 split_conditions(expr->cond_false);
297 a_F_c_fake = __pop_fake_cur_stree();
298 a_F_c_T = combine_strees(a_F, a_F_c_fake, __pop_cond_true_stack());
299 a_F_c_F = combine_strees(a_F, a_F_c_fake, __pop_cond_false_stack());
300
301 /* We have to restore the pre condition states so that
302 implied_condition_true() will use the right cur_stree */
303 __use_pre_cond_states();
304
305 if (implied_condition_true(expr->cond_true)) {
306 free_stree(&a_T_b_T);
307 free_stree(&a_T_b_F);
308 a_T_b_T = clone_stree(a_T);
309 overwrite_stree(a_T_b_fake, &a_T_b_T);
310 }
311 if (implied_condition_false(expr->cond_true)) {
312 free_stree(&a_T_b_T);
313 free_stree(&a_T_b_F);
314 a_T_b_F = clone_stree(a_T);
315 overwrite_stree(a_T_b_fake, &a_T_b_F);
316 }
317 if (implied_condition_true(expr->cond_false)) {
318 free_stree(&a_F_c_T);
319 free_stree(&a_F_c_F);
320 a_F_c_T = clone_stree(a_F);
321 overwrite_stree(a_F_c_fake, &a_F_c_T);
322 }
323 if (implied_condition_false(expr->cond_false)) {
324 free_stree(&a_F_c_T);
325 free_stree(&a_F_c_F);
326 a_F_c_F = clone_stree(a_F);
327 overwrite_stree(a_F_c_fake, &a_F_c_F);
328 }
329
330 merge_stree(&a_T_b_T, a_F_c_T);
331 merge_stree(&a_T_b_F, a_F_c_F);
332
333 tmp = __pop_cond_true_stack();
334 free_stree(&tmp);
335 tmp = __pop_cond_false_stack();
336 free_stree(&tmp);
337
338 __push_cond_stacks();
339 FOR_EACH_SM(a_T_b_T, sm) {
340 __set_true_false_sm(sm, NULL);
341 } END_FOR_EACH_SM(sm);
342 FOR_EACH_SM(a_T_b_F, sm) {
343 __set_true_false_sm(NULL, sm);
344 } END_FOR_EACH_SM(sm);
345 __free_set_states();
346
347 free_stree(&a_T_b_fake);
348 free_stree(&a_F_c_fake);
349 free_stree(&a_F_c_T);
350 free_stree(&a_F_c_F);
351 free_stree(&a_T_b_T);
352 free_stree(&a_T_b_F);
353 free_stree(&a_T);
354 free_stree(&a_F);
355 }
356
357 static void handle_comma(struct expression *expr)
358 {
359 __split_expr(expr->left);
360 split_conditions(expr->right);
361 }
362
363 static int make_op_unsigned(int op)
364 {
365 switch (op) {
366 case '<':
367 return SPECIAL_UNSIGNED_LT;
368 case SPECIAL_LTE:
369 return SPECIAL_UNSIGNED_LTE;
370 case '>':
371 return SPECIAL_UNSIGNED_GT;
372 case SPECIAL_GTE:
373 return SPECIAL_UNSIGNED_GTE;
374 }
375 return op;
376 }
377
378 static void hackup_unsigned_compares(struct expression *expr)
379 {
380 if (expr->type != EXPR_COMPARE)
381 return;
382
383 if (type_unsigned(get_type(expr)))
384 expr->op = make_op_unsigned(expr->op);
385 }
386
387 static void do_condition(struct expression *expr)
388 {
389 __fold_in_set_states();
390 __push_fake_cur_stree();
391 __pass_to_client(expr, CONDITION_HOOK);
392 __fold_in_set_states();
393 }
394
395 static void split_conditions(struct expression *expr)
396 {
397 if (option_debug) {
398 char *cond = expr_to_str(expr);
399
400 sm_msg("%d in split_conditions (%s)", get_lineno(), cond);
401 free_string(cond);
402 }
403
404 expr = strip_expr_set_parent(expr);
405 if (!expr) {
406 __fold_in_set_states();
407 return;
408 }
409
410 /*
411 * On fast paths (and also I guess some people think it's cool) people
412 * sometimes use | instead of ||. It works the same basically except
413 * that || implies a memory barrier between conditions. The easiest way
414 * to handle it is by pretending that | also has a barrier and re-using
415 * all the normal condition code. This potentially hides some bugs, but
416 * people who write code like this should just be careful or they
417 * deserve bugs.
418 *
419 * We could potentially treat boolean bitwise & this way but that seems
420 * too complicated to deal with.
421 */
422 if (expr->type == EXPR_BINOP && expr->op == '|') {
423 handle_logical(expr);
424 return;
425 }
426
427 switch (expr->type) {
428 case EXPR_LOGICAL:
429 expr_set_parent_expr(expr->left, expr);
430 expr_set_parent_expr(expr->right, expr);
431 __pass_to_client(expr, LOGIC_HOOK);
432 handle_logical(expr);
433 return;
434 case EXPR_COMPARE:
435 expr_set_parent_expr(expr->left, expr);
436 expr_set_parent_expr(expr->right, expr);
437 hackup_unsigned_compares(expr);
438 if (handle_zero_comparisons(expr))
439 return;
440 break;
441 case EXPR_CALL:
442 if (ignore_builtin_expect(expr))
443 return;
444 break;
445 case EXPR_PREOP:
446 expr_set_parent_expr(expr->unop, expr);
447 if (handle_preop(expr))
448 return;
449 break;
450 case EXPR_CONDITIONAL:
451 case EXPR_SELECT:
452 expr_set_parent_expr(expr->conditional, expr);
453 expr_set_parent_expr(expr->cond_true, expr);
454 expr_set_parent_expr(expr->cond_false, expr);
455 handle_select(expr);
456 return;
457 case EXPR_COMMA:
458 expr_set_parent_expr(expr->left, expr);
459 expr_set_parent_expr(expr->right, expr);
460 handle_comma(expr);
461 return;
462 }
463
464 /* fixme: this should be in smatch_flow.c
465 but because of the funny stuff we do with conditions
466 it's awkward to put it there. We would need to
467 call CONDITION_HOOK in smatch_flow as well.
468 */
469 push_expression(&big_expression_stack, expr);
470 push_expression(&big_condition_stack, expr);
471
472 if (expr->type == EXPR_COMPARE) {
473 if (expr->left->type != EXPR_POSTOP)
474 __split_expr(expr->left);
475 if (expr->right->type != EXPR_POSTOP)
476 __split_expr(expr->right);
477 } else if (expr->type != EXPR_POSTOP) {
478 __split_expr(expr);
479 }
480 do_condition(expr);
481 if (expr->type == EXPR_COMPARE) {
482 if (expr->left->type == EXPR_POSTOP)
483 __split_expr(expr->left);
484 if (expr->right->type == EXPR_POSTOP)
485 __split_expr(expr->right);
486 } else if (expr->type == EXPR_POSTOP) {
487 __split_expr(expr);
488 }
489 __push_fake_cur_stree();
490 __process_post_op_stack();
491 __fold_in_set_states();
492 pop_expression(&big_condition_stack);
493 pop_expression(&big_expression_stack);
494 }
495
496 static int inside_condition;
497 void __split_whole_condition(struct expression *expr)
498 {
499 sm_debug("%d in __split_whole_condition\n", get_lineno());
500 inside_condition++;
501 __save_pre_cond_states();
502 __push_cond_stacks();
503 /* it's a hack, but it's sometimes handy to have this stuff
504 on the big_expression_stack. */
505 push_expression(&big_expression_stack, expr);
506 split_conditions(expr);
507 __use_cond_states();
508 __pass_to_client(expr, WHOLE_CONDITION_HOOK);
509 pop_expression(&big_expression_stack);
510 inside_condition--;
511 sm_debug("%d done __split_whole_condition\n", get_lineno());
512 }
513
514 void __handle_logic(struct expression *expr)
515 {
516 sm_debug("%d in __handle_logic\n", get_lineno());
517 inside_condition++;
518 __save_pre_cond_states();
519 __push_cond_stacks();
520 /* it's a hack, but it's sometimes handy to have this stuff
521 on the big_expression_stack. */
522 push_expression(&big_expression_stack, expr);
523 if (expr)
524 split_conditions(expr);
525 __use_cond_states();
526 __pass_to_client(expr, WHOLE_CONDITION_HOOK);
527 pop_expression(&big_expression_stack);
528 __merge_false_states();
529 inside_condition--;
530 sm_debug("%d done __handle_logic\n", get_lineno());
531 }
532
533 int is_condition(struct expression *expr)
534 {
535
536 expr = strip_expr(expr);
537 if (!expr)
538 return 0;
539
540 switch (expr->type) {
541 case EXPR_LOGICAL:
542 case EXPR_COMPARE:
543 return 1;
544 case EXPR_PREOP:
545 if (expr->op == '!')
546 return 1;
547 }
548 return 0;
549 }
550
551 int __handle_condition_assigns(struct expression *expr)
552 {
553 struct expression *right;
554 struct stree *true_stree, *false_stree, *fake_stree;
555 struct sm_state *sm;
556
557 if (expr->op != '=')
558 return 0;
559 right = strip_expr(expr->right);
560 if (!is_condition(expr->right))
561 return 0;
562
563 sm_debug("%d in __handle_condition_assigns\n", get_lineno());
564 inside_condition++;
565 __save_pre_cond_states();
566 __push_cond_stacks();
567 /* it's a hack, but it's sometimes handy to have this stuff
568 on the big_expression_stack. */
569 push_expression(&big_expression_stack, right);
570 split_conditions(right);
571 true_stree = __get_true_states();
572 false_stree = __get_false_states();
573 __use_cond_states();
574 __push_fake_cur_stree();
575 set_extra_expr_mod(expr->left, alloc_estate_sval(sval_type_val(get_type(expr->left), 1)));
576 __pass_to_client(right, WHOLE_CONDITION_HOOK);
577
578 fake_stree = __pop_fake_cur_stree();
579 FOR_EACH_SM(fake_stree, sm) {
580 overwrite_sm_state_stree(&true_stree, sm);
581 } END_FOR_EACH_SM(sm);
582 free_stree(&fake_stree);
583
584 pop_expression(&big_expression_stack);
585 inside_condition--;
586
587 __push_true_states();
588
589 __use_false_states();
590 __push_fake_cur_stree();
591 set_extra_expr_mod(expr->left, alloc_estate_sval(sval_type_val(get_type(expr->left), 0)));
592
593 fake_stree = __pop_fake_cur_stree();
594 FOR_EACH_SM(fake_stree, sm) {
595 overwrite_sm_state_stree(&false_stree, sm);
596 } END_FOR_EACH_SM(sm);
597 free_stree(&fake_stree);
598
599 __merge_true_states();
600 merge_fake_stree(&true_stree, false_stree);
601 free_stree(&false_stree);
602 FOR_EACH_SM(true_stree, sm) {
603 __set_sm(sm);
604 } END_FOR_EACH_SM(sm);
605
606 __pass_to_client(expr, ASSIGNMENT_HOOK);
607 sm_debug("%d done __handle_condition_assigns\n", get_lineno());
608 return 1;
609 }
610
611 static int is_select_assign(struct expression *expr)
612 {
613 struct expression *right;
614
615 if (expr->op != '=')
616 return 0;
617 right = strip_expr(expr->right);
618 if (right->type == EXPR_CONDITIONAL)
619 return 1;
620 if (right->type == EXPR_SELECT)
621 return 1;
622 return 0;
623 }
624
625 int __handle_select_assigns(struct expression *expr)
626 {
627 struct expression *right;
628 struct stree *final_states = NULL;
629 struct sm_state *sm;
630 int is_true;
631 int is_false;
632
633 if (!is_select_assign(expr))
634 return 0;
635 sm_debug("%d in __handle_ternary_assigns\n", get_lineno());
636 right = strip_expr(expr->right);
637 __pass_to_client(right, SELECT_HOOK);
638
639 is_true = implied_condition_true(right->conditional);
640 is_false = implied_condition_false(right->conditional);
641
642 /* hah hah. the ultra fake out */
643 __save_pre_cond_states();
644 __split_whole_condition(right->conditional);
645
646 if (!is_false) {
647 struct expression *fake_expr;
648
649 if (right->cond_true)
650 fake_expr = assign_expression(expr->left, expr->op, right->cond_true);
651 else
652 fake_expr = assign_expression(expr->left, expr->op, right->conditional);
653 __split_expr(fake_expr);
654 final_states = clone_stree(__get_cur_stree());
655 }
656
657 __use_false_states();
658 if (!is_true) {
659 struct expression *fake_expr;
660
661 fake_expr = assign_expression(expr->left, expr->op, right->cond_false);
662 __split_expr(fake_expr);
663 merge_stree(&final_states, __get_cur_stree());
664 }
665
666 __use_pre_cond_states();
667
668 FOR_EACH_SM(final_states, sm) {
669 __set_sm(sm);
670 } END_FOR_EACH_SM(sm);
671
672 free_stree(&final_states);
673
674 sm_debug("%d done __handle_ternary_assigns\n", get_lineno());
675
676 return 1;
677 }
678
679 static struct statement *split_then_return_last(struct statement *stmt)
680 {
681 struct statement *tmp;
682 struct statement *last_stmt;
683
684 last_stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
685 if (!last_stmt)
686 return NULL;
687
688 __push_scope_hooks();
689 FOR_EACH_PTR(stmt->stmts, tmp) {
690 if (tmp == last_stmt) {
691 if (tmp->type == STMT_LABEL) {
692 __split_label_stmt(tmp);
693 return tmp->label_statement;
694 }
695 return last_stmt;
696 }
697 __split_stmt(tmp);
698 } END_FOR_EACH_PTR(tmp);
699 return NULL;
700 }
701
702 int __handle_expr_statement_assigns(struct expression *expr)
703 {
704 struct expression *right;
705 struct statement *stmt;
706
707 right = expr->right;
708 if (right->type == EXPR_PREOP && right->op == '(')
709 right = right->unop;
710 if (right->type != EXPR_STATEMENT)
711 return 0;
712
713 __expr_stmt_count++;
714 stmt = right->statement;
715 if (stmt->type == STMT_COMPOUND) {
716 struct statement *last_stmt;
717 struct expression *fake_assign;
718 struct expression fake_expr_stmt = { .smatch_flags = Fake, };
719
720 last_stmt = split_then_return_last(stmt);
721 if (!last_stmt) {
722 __expr_stmt_count--;
723 return 0;
724 }
725
726 fake_expr_stmt.pos = last_stmt->pos;
727 fake_expr_stmt.type = EXPR_STATEMENT;
728 fake_expr_stmt.op = 0;
729 fake_expr_stmt.statement = last_stmt;
730
731 fake_assign = assign_expression(expr->left, expr->op, &fake_expr_stmt);
732 __split_expr(fake_assign);
733
734 __pass_to_client(stmt, STMT_HOOK_AFTER);
735 __call_scope_hooks();
736 } else if (stmt->type == STMT_EXPRESSION) {
737 struct expression *fake_assign;
738
739 fake_assign = assign_expression(expr->left, expr->op, stmt->expression);
740 __split_expr(fake_assign);
741
742 } else {
743 __split_stmt(stmt);
744 }
745 __expr_stmt_count--;
746 return 1;
747 }
748
749 int in_condition(void)
750 {
751 return inside_condition;
752 }