?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
smatch_kernel_host_data: enable additional debug
[smatch.git] / smatch_extra.c
blob579d425b9b3d8131b9f6fe8c5a183985d85d50a8
1 /*
2 * Copyright (C) 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 * smatch_extra.c is supposed to track the value of every variable.
20 *
21 */
22
23 #define _GNU_SOURCE
24 #include <string.h>
25
26 #include <stdlib.h>
27 #include <errno.h>
28 #ifndef __USE_ISOC99
29 #define __USE_ISOC99
30 #endif
31 #include <limits.h>
32 #include "parse.h"
33 #include "smatch.h"
34 #include "smatch_slist.h"
35 #include "smatch_extra.h"
36
37 static int my_id;
38 static int link_id;
39
40 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr);
41
42 struct string_list *__ignored_macros = NULL;
43 int in_warn_on_macro(void)
44 {
45 struct statement *stmt;
46 char *tmp;
47 char *macro;
48
49 stmt = get_current_statement();
50 if (!stmt)
51 return 0;
52 macro = get_macro_name(stmt->pos);
53 if (!macro)
54 return 0;
55
56 FOR_EACH_PTR(__ignored_macros, tmp) {
57 if (!strcmp(tmp, macro))
58 return 1;
59 } END_FOR_EACH_PTR(tmp);
60 return 0;
61 }
62
63 typedef void (mod_hook)(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state);
64 DECLARE_PTR_LIST(mod_hook_list, mod_hook *);
65 static struct mod_hook_list *extra_mod_hooks;
66 static struct mod_hook_list *extra_nomod_hooks;
67
68 void add_extra_mod_hook(mod_hook *fn)
69 {
70 mod_hook **p = malloc(sizeof(mod_hook *));
71 *p = fn;
72 add_ptr_list(&extra_mod_hooks, p);
73 }
74
75 void add_extra_nomod_hook(mod_hook *fn)
76 {
77 mod_hook **p = malloc(sizeof(mod_hook *));
78 *p = fn;
79 add_ptr_list(&extra_nomod_hooks, p);
80 }
81
82 void call_extra_hooks(struct mod_hook_list *hooks, const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
83 {
84 mod_hook **fn;
85
86 FOR_EACH_PTR(hooks, fn) {
87 (*fn)(name, sym, expr, state);
88 } END_FOR_EACH_PTR(fn);
89 }
90
91 void call_extra_mod_hooks(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
92 {
93 call_extra_hooks(extra_mod_hooks, name, sym, expr, state);
94 }
95
96 void call_extra_nomod_hooks(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
97 {
98 call_extra_hooks(extra_nomod_hooks, name, sym, expr, state);
99 }
100
101 static void set_union_info(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
102 {
103 struct symbol *type, *tmp, *inner_type, *inner, *new_type;
104 struct expression *deref, *member_expr;
105 struct smatch_state *new;
106 int offset, inner_offset;
107 static bool in_recurse;
108 char *member_name;
109
110 if (__in_fake_assign)
111 return;
112
113 if (in_recurse)
114 return;
115 in_recurse = true;
116
117 if (!expr || expr->type != EXPR_DEREF || !expr->member)
118 goto done;
119 offset = get_member_offset_from_deref(expr);
120 if (offset < 0)
121 goto done;
122
123 deref = strip_expr(expr->deref);
124 type = get_type(deref);
125 if (type_is_ptr(type))
126 type = get_real_base_type(type);
127 if (!type || type->type != SYM_STRUCT)
128 goto done;
129
130 FOR_EACH_PTR(type->symbol_list, tmp) {
131 inner_type = get_real_base_type(tmp);
132 if (!inner_type || inner_type->type != SYM_UNION)
133 continue;
134
135 inner = first_ptr_list((struct ptr_list *)inner_type->symbol_list);
136 if (!inner || !inner->ident)
137 continue;
138
139 inner_offset = get_member_offset(type, inner->ident->name);
140 if (inner_offset < offset)
141 continue;
142 if (inner_offset > offset)
143 goto done;
144
145 FOR_EACH_PTR(inner_type->symbol_list, inner) {
146 struct symbol *tmp_type;
147
148 if (!inner->ident || inner->ident == expr->member)
149 continue;
150 tmp_type = get_real_base_type(inner);
151 if (tmp_type && tmp_type->type == SYM_STRUCT)
152 continue;
153 member_expr = deref;
154 if (tmp->ident)
155 member_expr = member_expression(member_expr, '.', tmp->ident);
156 member_expr = member_expression(member_expr, expr->op, inner->ident);
157 member_name = expr_to_var(member_expr);
158 if (!member_name)
159 continue;
160 new_type = get_real_base_type(inner);
161 new = alloc_estate_rl(cast_rl(new_type, estate_rl(state)));
162 set_extra_mod_helper(member_name, sym, member_expr, new);
163 free_string(member_name);
164 } END_FOR_EACH_PTR(inner);
165 } END_FOR_EACH_PTR(tmp);
166
167 done:
168 in_recurse = false;
169 }
170
171 static void mark_sub_members_gone(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
172 {
173 struct sm_state *sm;
174
175 if (__in_fake_assign)
176 return;
177 if (is_fake_var_assign(expr))
178 return;
179
180 if (!estate_type(state) || estate_type(state)->type != SYM_PTR)
181 return;
182 if (!is_noderef_ptr_rl(estate_rl(state)))
183 return;
184
185 FOR_EACH_MY_SM(SMATCH_EXTRA, __get_cur_stree(), sm) {
186 if (sm->sym != sym)
187 continue;
188 if (strcmp(name, sm->name) == 0)
189 continue;
190 if (!is_sub_member(name, sym, sm))
191 continue;
192 set_extra_nomod(sm->name, sm->sym, NULL, alloc_estate_empty());
193 } END_FOR_EACH_SM(sm);
194 }
195
196 static void call_update_mtag_data(struct expression *expr,
197 struct smatch_state *state)
198 {
199 struct expression *faked;
200
201 faked = get_faked_expression();
202 if (!faked)
203 goto update;
204 if (faked->type == EXPR_ASSIGNMENT && is_fresh_alloc(faked->right))
205 goto update;
206 return;
207
208 update:
209 update_mtag_data(expr, state);
210 }
211
212 static bool in_param_set;
213 void set_extra_mod_helper(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
214 {
215 if (!expr)
216 expr = gen_expression_from_name_sym(name, sym);
217 remove_from_equiv(name, sym);
218 set_union_info(name, sym, expr, state);
219 mark_sub_members_gone(name, sym, expr, state);
220 call_extra_mod_hooks(name, sym, expr, state);
221 call_update_mtag_data(expr, state);
222 if ((__in_fake_assign || in_param_set) &&
223 estate_is_unknown(state) && !get_state(SMATCH_EXTRA, name, sym))
224 return;
225 set_state(SMATCH_EXTRA, name, sym, state);
226 }
227
228 static void set_extra_nomod_helper(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
229 {
230 call_extra_nomod_hooks(name, sym, expr, state);
231 set_state(SMATCH_EXTRA, name, sym, state);
232 }
233
234 static char *get_pointed_at(const char *name, struct symbol *sym, struct symbol **new_sym)
235 {
236 struct expression *assigned;
237
238 /*
239 * Imagine we have an assignment: "foo = &addr;" then the other name
240 * of "*foo" is addr.
241 */
242
243 if (name[0] != '*')
244 return NULL;
245 if (strcmp(name + 1, sym->ident->name) != 0)
246 return NULL;
247
248 assigned = get_assigned_expr_name_sym(sym->ident->name, sym);
249 if (!assigned)
250 return NULL;
251 assigned = strip_parens(assigned);
252 if (assigned->type != EXPR_PREOP || assigned->op != '&')
253 return NULL;
254
255 return expr_to_var_sym(assigned->unop, new_sym);
256 }
257
258 char *get_other_name_sym_from_chunk(const char *name, const char *chunk, int len, struct symbol *sym, struct symbol **new_sym)
259 {
260 struct expression *assigned;
261 char *orig_name = NULL;
262 char buf[256];
263 char *ret;
264
265 assigned = get_assigned_expr_name_sym(chunk, sym);
266 if (!assigned)
267 return NULL;
268 if (assigned->type == EXPR_CALL)
269 return map_call_to_other_name_sym(name, sym, new_sym);
270 if (assigned->type == EXPR_PREOP && assigned->op == '&') {
271
272 orig_name = expr_to_var_sym(assigned, new_sym);
273 if (!orig_name || !*new_sym)
274 goto free;
275
276 snprintf(buf, sizeof(buf), "%s.%s", orig_name + 1, name + len);
277 ret = alloc_string(buf);
278 free_string(orig_name);
279 return ret;
280 }
281
282 orig_name = expr_to_var_sym(assigned, new_sym);
283 if (!orig_name || !*new_sym)
284 goto free;
285
286 snprintf(buf, sizeof(buf), "%s->%s", orig_name, name + len);
287 ret = alloc_string(buf);
288 free_string(orig_name);
289 return ret;
290 free:
291 free_string(orig_name);
292 return NULL;
293 }
294
295 static char *get_long_name_sym(const char *name, struct symbol *sym, struct symbol **new_sym, bool use_stack)
296 {
297 struct expression *orig;
298 struct symbol *orig_sym;
299 char *orig_name, *ret;
300
301 if (!sym || !sym->ident)
302 return NULL;
303
304 orig = get_assigned_expr_name_sym(sym->ident->name, sym);
305 if (orig) {
306 orig_name = expr_to_var_sym(orig, &orig_sym);
307 if (!orig_name)
308 return NULL;
309
310 ret = swap_names(name, sym->ident->name, orig_name);
311 free_string(orig_name);
312 if (ret)
313 *new_sym = orig_sym;
314 return ret;
315 }
316
317 return NULL;
318 }
319
320 char *get_other_name_sym_helper(const char *name, struct symbol *sym, struct symbol **new_sym, bool use_stack)
321 {
322 char buf[256];
323 char *ret;
324 int len;
325
326 *new_sym = NULL;
327
328 if (!sym || !sym->ident)
329 return NULL;
330
331 ret = get_pointed_at(name, sym, new_sym);
332 if (ret)
333 return ret;
334
335 ret = map_long_to_short_name_sym(name, sym, new_sym, use_stack);
336 if (ret)
337 return ret;
338
339 len = snprintf(buf, sizeof(buf), "%s", name);
340 if (len >= sizeof(buf) - 2)
341 return NULL;
342
343 while (use_stack && len >= 1) {
344 if (buf[len] == '>' && buf[len - 1] == '-') {
345 len--;
346 buf[len] = '\0';
347 ret = get_other_name_sym_from_chunk(name, buf, len + 2, sym, new_sym);
348 if (ret)
349 return ret;
350 }
351 len--;
352 }
353
354 ret = get_long_name_sym(name, sym, new_sym, use_stack);
355 if (ret)
356 return ret;
357
358 return NULL;
359 }
360
361 char *get_other_name_sym(const char *name, struct symbol *sym, struct symbol **new_sym)
362 {
363 return get_other_name_sym_helper(name, sym, new_sym, true);
364 }
365
366 char *get_other_name_sym_nostack(const char *name, struct symbol *sym, struct symbol **new_sym)
367 {
368 return get_other_name_sym_helper(name, sym, new_sym, false);
369 }
370
371 void set_extra_mod(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
372 {
373 char *new_name;
374 struct symbol *new_sym;
375
376 set_extra_mod_helper(name, sym, expr, state);
377 new_name = get_other_name_sym_nostack(name, sym, &new_sym);
378 if (new_name && new_sym)
379 set_extra_mod_helper(new_name, new_sym, NULL, state);
380 free_string(new_name);
381 }
382
383 static struct expression *chunk_get_array_base(struct expression *expr)
384 {
385 /*
386 * The problem with is_array() is that it only returns true for things
387 * like foo[1] but not for foo[1].bar.
388 *
389 */
390 expr = strip_expr(expr);
391 while (expr && expr->type == EXPR_DEREF)
392 expr = strip_expr(expr->deref);
393 return get_array_base(expr);
394 }
395
396 static int chunk_has_array(struct expression *expr)
397 {
398 return !!chunk_get_array_base(expr);
399 }
400
401 static void clear_array_states(struct expression *array)
402 {
403 struct sm_state *sm;
404
405 sm = get_sm_state_expr(link_id, array);
406 if (sm)
407 match_link_modify(sm, NULL);
408 }
409
410 static void set_extra_array_mod(struct expression *expr, struct smatch_state *state)
411 {
412 struct expression *array;
413 struct var_sym_list *vsl;
414 struct var_sym *vs;
415 char *name;
416 struct symbol *sym;
417
418 array = chunk_get_array_base(expr);
419
420 name = expr_to_chunk_sym_vsl(expr, &sym, &vsl);
421 if (!name || !vsl) {
422 clear_array_states(array);
423 goto free;
424 }
425
426 FOR_EACH_PTR(vsl, vs) {
427 store_link(link_id, vs->var, vs->sym, name, sym);
428 } END_FOR_EACH_PTR(vs);
429
430 call_extra_mod_hooks(name, sym, expr, state);
431 set_state(SMATCH_EXTRA, name, sym, state);
432 free:
433 free_string(name);
434 }
435
436 void set_extra_expr_mod(struct expression *expr, struct smatch_state *state)
437 {
438 struct symbol *sym;
439 char *name;
440
441 if (chunk_has_array(expr)) {
442 set_extra_array_mod(expr, state);
443 return;
444 }
445
446 expr = strip_expr(expr);
447 name = expr_to_var_sym(expr, &sym);
448 if (!name || !sym)
449 goto free;
450 set_extra_mod(name, sym, expr, state);
451 free:
452 free_string(name);
453 }
454
455 void set_extra_nomod(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
456 {
457 char *new_name;
458 struct symbol *new_sym;
459 struct relation *rel;
460 struct smatch_state *orig_state;
461
462 orig_state = get_state(SMATCH_EXTRA, name, sym);
463
464 /* don't save unknown states if leaving it blank is the same */
465 if (!orig_state && estate_is_unknown(state))
466 return;
467
468 new_name = get_other_name_sym(name, sym, &new_sym);
469 if (new_name && new_sym)
470 set_extra_nomod_helper(new_name, new_sym, expr, state);
471 free_string(new_name);
472
473 if (!estate_related(orig_state)) {
474 set_extra_nomod_helper(name, sym, expr, state);
475 return;
476 }
477
478 set_related(state, estate_related(orig_state));
479 FOR_EACH_PTR(estate_related(orig_state), rel) {
480 struct smatch_state *estate;
481
482 estate = get_state(SMATCH_EXTRA, rel->name, rel->sym);
483 if (!estate)
484 continue;
485 set_extra_nomod_helper(rel->name, rel->sym, expr, clone_estate_cast(estate_type(estate), state));
486 } END_FOR_EACH_PTR(rel);
487 }
488
489 void set_extra_nomod_vsl(const char *name, struct symbol *sym, struct var_sym_list *vsl, struct expression *expr, struct smatch_state *state)
490 {
491 struct var_sym *vs;
492
493 FOR_EACH_PTR(vsl, vs) {
494 store_link(link_id, vs->var, vs->sym, name, sym);
495 } END_FOR_EACH_PTR(vs);
496
497 set_extra_nomod(name, sym, expr, state);
498 }
499
500 /*
501 * This is for return_implies_state() hooks which modify a SMATCH_EXTRA state
502 */
503 void set_extra_expr_nomod(struct expression *expr, struct smatch_state *state)
504 {
505 struct var_sym_list *vsl;
506 struct var_sym *vs;
507 char *name;
508 struct symbol *sym;
509
510 name = expr_to_chunk_sym_vsl(expr, &sym, &vsl);
511 if (!name || !vsl)
512 goto free;
513 FOR_EACH_PTR(vsl, vs) {
514 store_link(link_id, vs->var, vs->sym, name, sym);
515 } END_FOR_EACH_PTR(vs);
516
517 set_extra_nomod(name, sym, expr, state);
518 free:
519 free_string(name);
520 }
521
522 static void set_extra_true_false(const char *name, struct symbol *sym,
523 struct smatch_state *true_state,
524 struct smatch_state *false_state)
525 {
526 char *new_name;
527 struct symbol *new_sym;
528 struct relation *rel;
529 struct smatch_state *orig_state;
530
531 if (!true_state && !false_state)
532 return;
533
534 if (in_warn_on_macro())
535 return;
536
537 new_name = get_other_name_sym(name, sym, &new_sym);
538 if (new_name && new_sym)
539 set_true_false_states(SMATCH_EXTRA, new_name, new_sym, true_state, false_state);
540 free_string(new_name);
541
542 orig_state = get_state(SMATCH_EXTRA, name, sym);
543
544 if (!estate_related(orig_state)) {
545 set_true_false_states(SMATCH_EXTRA, name, sym, true_state, false_state);
546 return;
547 }
548
549 if (true_state)
550 set_related(true_state, estate_related(orig_state));
551 if (false_state)
552 set_related(false_state, estate_related(orig_state));
553
554 FOR_EACH_PTR(estate_related(orig_state), rel) {
555 set_true_false_states(SMATCH_EXTRA, rel->name, rel->sym,
556 true_state, false_state);
557 } END_FOR_EACH_PTR(rel);
558 }
559
560 static void set_extra_chunk_true_false(struct expression *expr,
561 struct smatch_state *true_state,
562 struct smatch_state *false_state)
563 {
564 struct var_sym_list *vsl;
565 struct var_sym *vs;
566 struct symbol *type;
567 char *name;
568 struct symbol *sym;
569
570 if (in_warn_on_macro())
571 return;
572
573 type = get_type(expr);
574 if (!type)
575 return;
576
577 name = expr_to_chunk_sym_vsl(expr, &sym, &vsl);
578 if (!name || !vsl)
579 goto free;
580 FOR_EACH_PTR(vsl, vs) {
581 store_link(link_id, vs->var, vs->sym, name, sym);
582 } END_FOR_EACH_PTR(vs);
583
584 set_true_false_states(SMATCH_EXTRA, name, sym,
585 clone_estate(true_state),
586 clone_estate(false_state));
587 free:
588 free_string(name);
589 }
590
591 static void set_extra_expr_true_false(struct expression *expr,
592 struct smatch_state *true_state,
593 struct smatch_state *false_state)
594 {
595 char *name;
596 struct symbol *sym;
597 sval_t sval;
598
599 if (!true_state && !false_state)
600 return;
601
602 if (get_value(expr, &sval))
603 return;
604
605 expr = strip_expr(expr);
606 name = expr_to_var_sym(expr, &sym);
607 if (!name || !sym) {
608 free_string(name);
609 set_extra_chunk_true_false(expr, true_state, false_state);
610 return;
611 }
612 set_extra_true_false(name, sym, true_state, false_state);
613 free_string(name);
614 }
615
616 static int get_countdown_info(struct expression *condition, struct expression **unop, int *op, sval_t *right)
617 {
618 struct expression *unop_expr;
619 int comparison;
620 sval_t limit;
621
622 right->type = &int_ctype;
623 right->value = 0;
624
625 condition = strip_expr(condition);
626
627 if (condition->type == EXPR_COMPARE) {
628 comparison = remove_unsigned_from_comparison(condition->op);
629
630 if (comparison != SPECIAL_GTE && comparison != '>')
631 return 0;
632 if (!get_value(condition->right, &limit))
633 return 0;
634
635 unop_expr = condition->left;
636 if (unop_expr->type != EXPR_PREOP && unop_expr->type != EXPR_POSTOP)
637 return 0;
638 if (unop_expr->op != SPECIAL_DECREMENT)
639 return 0;
640
641 *unop = unop_expr;
642 *op = comparison;
643 *right = limit;
644
645 return 1;
646 }
647
648 if (condition->type != EXPR_PREOP && condition->type != EXPR_POSTOP)
649 return 0;
650 if (condition->op != SPECIAL_DECREMENT)
651 return 0;
652
653 *unop = condition;
654 *op = '>';
655
656 return 1;
657 }
658
659 static struct sm_state *handle_canonical_while_count_down(struct statement *loop)
660 {
661 struct expression *iter_var;
662 struct expression *condition, *unop;
663 struct symbol *type;
664 struct sm_state *sm;
665 struct smatch_state *estate;
666 int op;
667 sval_t start, right;
668
669 right.type = &int_ctype;
670 right.value = 0;
671
672 condition = strip_expr(loop->iterator_pre_condition);
673 if (!condition)
674 return NULL;
675
676 if (!get_countdown_info(condition, &unop, &op, &right))
677 return NULL;
678
679 iter_var = unop->unop;
680
681 sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
682 if (!sm)
683 return NULL;
684 if (sval_cmp(estate_min(sm->state), right) < 0)
685 return NULL;
686 start = estate_max(sm->state);
687
688 type = get_type(iter_var);
689 right = sval_cast(type, right);
690 start = sval_cast(type, start);
691
692 if (sval_cmp(start, right) <= 0)
693 return NULL;
694 if (!sval_is_max(start))
695 start.value--;
696
697 if (op == SPECIAL_GTE)
698 right.value--;
699
700 if (unop->type == EXPR_PREOP) {
701 right.value++;
702 estate = alloc_estate_range(right, start);
703 if (estate_has_hard_max(sm->state))
704 estate_set_hard_max(estate);
705 estate_copy_fuzzy_max(estate, sm->state);
706 set_extra_expr_mod(iter_var, estate);
707 }
708 if (unop->type == EXPR_POSTOP) {
709 estate = alloc_estate_range(right, start);
710 if (estate_has_hard_max(sm->state))
711 estate_set_hard_max(estate);
712 estate_copy_fuzzy_max(estate, sm->state);
713 set_extra_expr_mod(iter_var, estate);
714 }
715 return get_sm_state_expr(SMATCH_EXTRA, iter_var);
716 }
717
718 static struct sm_state *handle_canonical_for_inc(struct expression *iter_expr,
719 struct expression *condition)
720 {
721 struct expression *iter_var;
722 struct sm_state *sm;
723 struct smatch_state *estate;
724 sval_t start, end, max;
725 bool unknown_end = false;
726
727 iter_var = iter_expr->unop;
728 sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
729 if (!sm)
730 return NULL;
731 if (!estate_get_single_value(sm->state, &start))
732 return NULL;
733 if (!get_implied_max(condition->right, &end)) {
734 end = sval_type_max(get_type(condition->right));
735 end = sval_cast(start.type, end);
736 if (sval_is_max(end))
737 unknown_end = true;
738 }
739
740 if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm)
741 return NULL;
742
743 switch (condition->op) {
744 case SPECIAL_UNSIGNED_LT:
745 case SPECIAL_NOTEQUAL:
746 case '<':
747 if (!sval_is_min(end) && !unknown_end)
748 end.value--;
749 break;
750 case SPECIAL_UNSIGNED_LTE:
751 case SPECIAL_LTE:
752 break;
753 default:
754 return NULL;
755 }
756 if (sval_cmp(end, start) < 0)
757 return NULL;
758 end = sval_cast(start.type, end);
759 estate = alloc_estate_range(start, end);
760 if (get_hard_max(condition->right, &max)) {
761 if (!get_macro_name(condition->pos))
762 estate_set_hard_max(estate);
763 if (condition->op == '<' ||
764 condition->op == SPECIAL_UNSIGNED_LT ||
765 condition->op == SPECIAL_NOTEQUAL)
766 max.value--;
767 max = sval_cast(start.type, max);
768 estate_set_fuzzy_max(estate, max);
769 }
770 set_extra_expr_mod(iter_var, estate);
771 return get_sm_state_expr(SMATCH_EXTRA, iter_var);
772 }
773
774 static struct sm_state *handle_canonical_for_dec(struct expression *iter_expr,
775 struct expression *condition)
776 {
777 struct expression *iter_var;
778 struct sm_state *sm;
779 struct smatch_state *estate;
780 sval_t start, end;
781
782 iter_var = iter_expr->unop;
783 sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
784 if (!sm)
785 return NULL;
786 if (!estate_get_single_value(sm->state, &start))
787 return NULL;
788 if (!get_implied_min(condition->right, &end))
789 end = sval_type_min(get_type(iter_var));
790 end = sval_cast(estate_type(sm->state), end);
791 if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm)
792 return NULL;
793
794 switch (condition->op) {
795 case SPECIAL_NOTEQUAL:
796 case '>':
797 if (!sval_is_max(end))
798 end.value++;
799 break;
800 case SPECIAL_GTE:
801 break;
802 default:
803 return NULL;
804 }
805 if (sval_cmp(end, start) > 0)
806 return NULL;
807 estate = alloc_estate_range(end, start);
808 estate_set_hard_max(estate);
809 estate_set_fuzzy_max(estate, estate_get_fuzzy_max(estate));
810 set_extra_expr_mod(iter_var, estate);
811 return get_sm_state_expr(SMATCH_EXTRA, iter_var);
812 }
813
814 static struct sm_state *handle_canonical_for_loops(struct statement *loop)
815 {
816 struct expression *iter_expr;
817 struct expression *condition;
818
819 if (!loop->iterator_post_statement)
820 return NULL;
821 if (loop->iterator_post_statement->type != STMT_EXPRESSION)
822 return NULL;
823 iter_expr = loop->iterator_post_statement->expression;
824 if (!loop->iterator_pre_condition)
825 return NULL;
826 if (loop->iterator_pre_condition->type != EXPR_COMPARE)
827 return NULL;
828 condition = loop->iterator_pre_condition;
829
830 if (iter_expr->op == SPECIAL_INCREMENT)
831 return handle_canonical_for_inc(iter_expr, condition);
832 if (iter_expr->op == SPECIAL_DECREMENT)
833 return handle_canonical_for_dec(iter_expr, condition);
834 return NULL;
835 }
836
837 struct sm_state *__extra_handle_canonical_loops(struct statement *loop, struct stree **stree)
838 {
839 struct sm_state *ret;
840
841 /*
842 * Canonical loops are a hack. The proper way to handle this is to
843 * use two passes, but unfortunately, doing two passes makes parsing
844 * code twice as slow.
845 *
846 * What we do is we set the inside state here, which overwrites whatever
847 * __extra_match_condition() does. Then we set the outside state in
848 * __extra_pre_loop_hook_after().
849 *
850 */
851 __push_fake_cur_stree();
852 if (!loop->iterator_post_statement)
853 ret = handle_canonical_while_count_down(loop);
854 else
855 ret = handle_canonical_for_loops(loop);
856 *stree = __pop_fake_cur_stree();
857 return ret;
858 }
859
860 int __iterator_unchanged(struct sm_state *sm)
861 {
862 if (!sm)
863 return 0;
864 if (get_sm_state(my_id, sm->name, sm->sym) == sm)
865 return 1;
866 return 0;
867 }
868
869 static void while_count_down_after(struct sm_state *sm, struct expression *condition)
870 {
871 struct expression *unop;
872 int op;
873 sval_t limit, after_value;
874
875 if (!get_countdown_info(condition, &unop, &op, &limit))
876 return;
877 after_value = estate_min(sm->state);
878 after_value.value--;
879 set_extra_mod(sm->name, sm->sym, condition->unop, alloc_estate_sval(after_value));
880 }
881
882 void __extra_pre_loop_hook_after(struct sm_state *sm,
883 struct statement *iterator,
884 struct expression *condition)
885 {
886 struct expression *iter_expr;
887 sval_t limit;
888 struct smatch_state *state;
889 sval_t end;
890
891 if (!iterator) {
892 while_count_down_after(sm, condition);
893 return;
894 }
895
896 iter_expr = iterator->expression;
897
898 if (condition->type != EXPR_COMPARE)
899 return;
900
901 if (iter_expr->op == SPECIAL_INCREMENT) {
902 if (!get_implied_value(condition->right, &end) &&
903 sval_is_max(estate_max(sm->state)))
904 limit = estate_max(sm->state);
905 else
906 limit = sval_binop(estate_max(sm->state), '+',
907 sval_type_val(estate_type(sm->state), 1));
908 } else {
909 limit = sval_binop(estate_min(sm->state), '-',
910 sval_type_val(estate_type(sm->state), 1));
911 }
912 limit = sval_cast(estate_type(sm->state), limit);
913 if (!estate_has_hard_max(sm->state) && !__has_breaks()) {
914 if (iter_expr->op == SPECIAL_INCREMENT)
915 state = alloc_estate_range(estate_min(sm->state), limit);
916 else
917 state = alloc_estate_range(limit, estate_max(sm->state));
918 } else {
919 state = alloc_estate_sval(limit);
920 }
921 if (!estate_has_hard_max(sm->state)) {
922 estate_clear_hard_max(state);
923 }
924 if (estate_has_fuzzy_max(sm->state)) {
925 sval_t hmax = estate_get_fuzzy_max(sm->state);
926 sval_t max = estate_max(sm->state);
927
928 if (sval_cmp(hmax, max) != 0)
929 estate_clear_fuzzy_max(state);
930 } else if (!estate_has_fuzzy_max(sm->state)) {
931 estate_clear_fuzzy_max(state);
932 }
933
934 set_extra_mod(sm->name, sm->sym, iter_expr, state);
935 }
936
937 static bool get_global_rl(const char *name, struct symbol *sym, struct range_list **rl)
938 {
939 struct expression *expr;
940
941 if (!sym || !(sym->ctype.modifiers & MOD_TOPLEVEL) || !sym->ident)
942 return false;
943 if (strcmp(sym->ident->name, name) != 0)
944 return false;
945
946 expr = symbol_expression(sym);
947 return get_implied_rl(expr, rl);
948 }
949
950 static struct stree *unmatched_stree;
951 static struct smatch_state *unmatched_state(struct sm_state *sm)
952 {
953 struct smatch_state *state;
954 struct expression *expr;
955 struct range_list *rl;
956
957 if (unmatched_stree) {
958 state = get_state_stree(unmatched_stree, SMATCH_EXTRA, sm->name, sm->sym);
959 if (state)
960 return state;
961 }
962 if (parent_is_gone_var_sym(sm->name, sm->sym))
963 return alloc_estate_empty();
964 if (get_global_rl(sm->name, sm->sym, &rl))
965 return alloc_estate_rl(rl);
966
967 expr = gen_expression_from_name_sym(sm->name, sm->sym);
968 if (!expr)
969 return alloc_estate_whole(estate_type(sm->state));
970 get_absolute_rl(expr, &rl);
971 return alloc_estate_rl(rl);
972 }
973
974 static void clear_the_pointed_at(struct expression *expr)
975 {
976 struct stree *stree;
977 char *name;
978 struct symbol *sym;
979 struct sm_state *tmp;
980
981 name = expr_to_var_sym(expr, &sym);
982 if (!name || !sym)
983 goto free;
984
985 stree = __get_cur_stree();
986 FOR_EACH_MY_SM(SMATCH_EXTRA, stree, tmp) {
987 if (tmp->name[0] != '*')
988 continue;
989 if (tmp->sym != sym)
990 continue;
991 if (strcmp(tmp->name + 1, name) != 0)
992 continue;
993 set_extra_mod(tmp->name, tmp->sym, expr, alloc_estate_whole(estate_type(tmp->state)));
994 } END_FOR_EACH_SM(tmp);
995
996 free:
997 free_string(name);
998 }
999
1000 static int is_const_param(struct expression *expr, int param)
1001 {
1002 struct symbol *type;
1003
1004 type = get_arg_type(expr, param);
1005 if (!type)
1006 return 0;
1007 if (type->ctype.modifiers & MOD_CONST)
1008 return 1;
1009 return 0;
1010 }
1011
1012 static void match_function_call(struct expression *expr)
1013 {
1014 struct expression *arg;
1015 struct expression *tmp;
1016 int param = -1;
1017
1018 /* if we have the db this is handled in smatch_function_hooks.c */
1019 if (!option_no_db)
1020 return;
1021 if (inlinable(expr->fn))
1022 return;
1023
1024 FOR_EACH_PTR(expr->args, arg) {
1025 param++;
1026 if (is_const_param(expr->fn, param))
1027 continue;
1028 tmp = strip_expr(arg);
1029 if (tmp->type == EXPR_PREOP && tmp->op == '&')
1030 set_extra_expr_mod(tmp->unop, alloc_estate_whole(get_type(tmp->unop)));
1031 else
1032 clear_the_pointed_at(tmp);
1033 } END_FOR_EACH_PTR(arg);
1034 }
1035
1036 int values_fit_type(struct expression *left, struct expression *right)
1037 {
1038 struct range_list *rl;
1039 struct symbol *type;
1040
1041 type = get_type(left);
1042 if (!type)
1043 return 0;
1044 get_absolute_rl(right, &rl);
1045 if (type == rl_type(rl))
1046 return 1;
1047 if (sval_is_negative(rl_min(rl))) {
1048 if (type_unsigned(type))
1049 return 0;
1050 if (sval_cmp(sval_type_min(type), rl_min(rl)) > 0)
1051 return 0;
1052 }
1053 if (sval_cmp(sval_type_max(type), rl_max(rl)) < 0)
1054 return 0;
1055 return 1;
1056 }
1057
1058 static void save_chunk_info(struct expression *left, struct expression *right)
1059 {
1060 struct var_sym_list *vsl;
1061 struct var_sym *vs;
1062 struct expression *add_expr;
1063 struct symbol *type;
1064 sval_t sval;
1065 char *name;
1066 struct symbol *sym;
1067
1068 if (right->type != EXPR_BINOP || right->op != '-')
1069 return;
1070 if (!get_value(right->left, &sval))
1071 return;
1072 if (!expr_to_sym(right->right))
1073 return;
1074
1075 add_expr = binop_expression(left, '+', right->right);
1076 type = get_type(add_expr);
1077 if (!type)
1078 return;
1079 name = expr_to_chunk_sym_vsl(add_expr, &sym, &vsl);
1080 if (!name || !vsl)
1081 goto free;
1082 FOR_EACH_PTR(vsl, vs) {
1083 store_link(link_id, vs->var, vs->sym, name, sym);
1084 } END_FOR_EACH_PTR(vs);
1085
1086 set_state(SMATCH_EXTRA, name, sym, alloc_estate_sval(sval_cast(type, sval)));
1087 free:
1088 free_string(name);
1089 }
1090
1091 static void do_array_assign(struct expression *left, int op, struct expression *right)
1092 {
1093 struct range_list *rl;
1094
1095 if (op == '=') {
1096 get_absolute_rl(right, &rl);
1097 rl = cast_rl(get_type(left), rl);
1098 } else {
1099 rl = alloc_whole_rl(get_type(left));
1100 }
1101
1102 set_extra_array_mod(left, alloc_estate_rl(rl));
1103 }
1104
1105 static void match_vanilla_assign(struct expression *left, struct expression *right)
1106 {
1107 struct range_list *orig_rl = NULL;
1108 struct range_list *rl = NULL;
1109 struct symbol *right_sym;
1110 struct symbol *left_type;
1111 struct symbol *right_type;
1112 char *right_name = NULL;
1113 struct symbol *sym;
1114 char *name;
1115 sval_t sval, max;
1116 struct smatch_state *state;
1117 int comparison;
1118
1119 if (is_struct(left))
1120 return;
1121
1122 if (expr_equiv(left, right))
1123 return;
1124
1125 save_chunk_info(left, right);
1126
1127 name = expr_to_var_sym(left, &sym);
1128 if (!name) {
1129 if (chunk_has_array(left))
1130 do_array_assign(left, '=', right);
1131 return;
1132 }
1133
1134 left_type = get_type(left);
1135 right_type = get_type(right);
1136
1137 right_name = expr_to_var_sym(right, &right_sym);
1138
1139 if (!__in_fake_assign &&
1140 !(right->type == EXPR_PREOP && right->op == '&') &&
1141 right_name && right_sym &&
1142 values_fit_type(left, strip_expr(right)) &&
1143 !has_symbol(right, sym)) {
1144 set_equiv(left, right);
1145 goto free;
1146 }
1147
1148 if (get_implied_value(right, &sval)) {
1149 state = alloc_estate_sval(sval_cast(left_type, sval));
1150 goto done;
1151 }
1152
1153 if (__in_fake_assign || is_fake_var(left)) {
1154 struct smatch_state *right_state;
1155 struct range_list *rl;
1156
1157 right_state = get_state(SMATCH_EXTRA, right_name, right_sym);
1158 if (right_state) {
1159 state = clone_estate_cast(left_type, right_state);
1160 goto done;
1161 }
1162
1163 if (get_implied_rl(right, &rl)) {
1164 rl = cast_rl(left_type, rl);
1165 state = alloc_estate_rl(rl);
1166 goto done;
1167 }
1168
1169 rl = alloc_whole_rl(right_type);
1170 rl = cast_rl(left_type, rl);
1171 state = alloc_estate_rl(rl);
1172 goto done;
1173 }
1174
1175 comparison = get_comparison_no_extra(left, right);
1176 if (comparison) {
1177 comparison = flip_comparison(comparison);
1178 get_implied_rl(left, &orig_rl);
1179 }
1180
1181 if (get_implied_rl(right, &rl)) {
1182 rl = cast_rl(left_type, rl);
1183 if (orig_rl)
1184 filter_by_comparison(&rl, comparison, orig_rl);
1185 state = alloc_estate_rl(rl);
1186 if (get_hard_max(right, &max)) {
1187 estate_set_hard_max(state);
1188 estate_set_fuzzy_max(state, max);
1189 }
1190 } else {
1191 rl = alloc_whole_rl(right_type);
1192 rl = cast_rl(left_type, rl);
1193 if (orig_rl)
1194 filter_by_comparison(&rl, comparison, orig_rl);
1195 state = alloc_estate_rl(rl);
1196 }
1197
1198 done:
1199 set_extra_mod(name, sym, left, state);
1200 free:
1201 free_string(right_name);
1202 }
1203
1204 static void match_assign(struct expression *expr)
1205 {
1206 struct range_list *rl = NULL;
1207 struct expression *left;
1208 struct expression *right;
1209 struct expression *binop_expr;
1210 struct symbol *left_type;
1211 struct symbol *sym;
1212 char *name;
1213
1214 left = strip_expr(expr->left);
1215
1216 right = strip_parens(expr->right);
1217 if (right->type == EXPR_CALL && sym_name_is("__builtin_expect", right->fn))
1218 right = get_argument_from_call_expr(right->args, 0);
1219 while (right->type == EXPR_ASSIGNMENT && right->op == '=')
1220 right = strip_parens(right->left);
1221
1222 if (expr->op == '=' && is_condition(expr->right))
1223 return; /* handled in smatch_condition.c */
1224 if (expr->op == '=' && right->type == EXPR_CALL &&
1225 !is_fake_call(right))
1226 return; /* handled in smatch_function_hooks.c */
1227 if (expr->op == '=') {
1228 match_vanilla_assign(left, right);
1229 return;
1230 }
1231
1232 name = expr_to_var_sym(left, &sym);
1233 if (!name)
1234 return;
1235
1236 left_type = get_type(left);
1237
1238 switch (expr->op) {
1239 case SPECIAL_ADD_ASSIGN:
1240 case SPECIAL_SUB_ASSIGN:
1241 case SPECIAL_AND_ASSIGN:
1242 case SPECIAL_MOD_ASSIGN:
1243 case SPECIAL_SHL_ASSIGN:
1244 case SPECIAL_SHR_ASSIGN:
1245 case SPECIAL_OR_ASSIGN:
1246 case SPECIAL_XOR_ASSIGN:
1247 case SPECIAL_MUL_ASSIGN:
1248 case SPECIAL_DIV_ASSIGN:
1249 binop_expr = binop_expression(expr->left,
1250 op_remove_assign(expr->op),
1251 expr->right);
1252 get_absolute_rl(binop_expr, &rl);
1253 rl = cast_rl(left_type, rl);
1254 if (inside_loop()) {
1255 if (expr->op == SPECIAL_ADD_ASSIGN)
1256 add_range(&rl, rl_max(rl), sval_type_max(rl_type(rl)));
1257
1258 if (expr->op == SPECIAL_SUB_ASSIGN &&
1259 !sval_is_negative(rl_min(rl))) {
1260 sval_t zero = { .type = rl_type(rl) };
1261
1262 add_range(&rl, rl_min(rl), zero);
1263 }
1264 }
1265 set_extra_mod(name, sym, left, alloc_estate_rl(rl));
1266 goto free;
1267 }
1268 set_extra_mod(name, sym, left, alloc_estate_whole(left_type));
1269 free:
1270 free_string(name);
1271 }
1272
1273 static struct smatch_state *increment_state(struct smatch_state *state)
1274 {
1275 sval_t min = estate_min(state);
1276 sval_t max = estate_max(state);
1277
1278 if (!estate_rl(state))
1279 return NULL;
1280
1281 if (inside_loop())
1282 max = sval_type_max(max.type);
1283
1284 if (!sval_is_min(min) && !sval_is_max(min))
1285 min.value++;
1286 if (!sval_is_min(max) && !sval_is_max(max))
1287 max.value++;
1288 return alloc_estate_range(min, max);
1289 }
1290
1291 static struct smatch_state *decrement_state(struct smatch_state *state)
1292 {
1293 sval_t min = estate_min(state);
1294 sval_t max = estate_max(state);
1295
1296 if (!estate_rl(state))
1297 return NULL;
1298
1299 if (inside_loop())
1300 min = sval_type_min(min.type);
1301
1302 if (!sval_is_min(min) && !sval_is_max(min))
1303 min.value--;
1304 if (!sval_is_min(max) && !sval_is_max(max))
1305 max.value--;
1306 return alloc_estate_range(min, max);
1307 }
1308
1309 static void clear_pointed_at_state(struct expression *expr)
1310 {
1311 struct symbol *type;
1312
1313 /*
1314 * ALERT: This is sort of a mess. If it's is a struct assigment like
1315 * "foo = bar;", then that's handled by smatch_struct_assignment.c.
1316 * the same thing for p++ where "p" is a struct. Most modifications
1317 * are handled by the assignment hook or the db. Smatch_extra.c doesn't
1318 * use smatch_modification.c because we have to get the ordering right
1319 * or something. So if you have p++ where p is a pointer to a standard
1320 * c type then we handle that here. What a mess.
1321 */
1322 expr = strip_expr(expr);
1323 type = get_type(expr);
1324 if (!type || type->type != SYM_PTR)
1325 return;
1326 type = get_real_base_type(type);
1327 if (!type || type->type != SYM_BASETYPE)
1328 return;
1329 set_extra_expr_nomod(deref_expression(expr), alloc_estate_whole(type));
1330 }
1331
1332 static void unop_expr(struct expression *expr)
1333 {
1334 struct smatch_state *state;
1335
1336 if (expr->smatch_flags & Handled)
1337 return;
1338
1339 switch (expr->op) {
1340 case SPECIAL_INCREMENT:
1341 state = get_state_expr(SMATCH_EXTRA, expr->unop);
1342 state = increment_state(state);
1343 if (!state)
1344 state = alloc_estate_whole(get_type(expr));
1345 set_extra_expr_mod(expr->unop, state);
1346 clear_pointed_at_state(expr->unop);
1347 break;
1348 case SPECIAL_DECREMENT:
1349 state = get_state_expr(SMATCH_EXTRA, expr->unop);
1350 state = decrement_state(state);
1351 if (!state)
1352 state = alloc_estate_whole(get_type(expr));
1353 set_extra_expr_mod(expr->unop, state);
1354 clear_pointed_at_state(expr->unop);
1355 break;
1356 default:
1357 return;
1358 }
1359 }
1360
1361 static void asm_expr(struct statement *stmt)
1362 {
1363 struct asm_operand *op;
1364 struct symbol *type;
1365
1366 FOR_EACH_PTR(stmt->asm_outputs, op) {
1367 type = get_type(strip_expr(op->expr));
1368 set_extra_expr_mod(op->expr, alloc_estate_whole(type));
1369 } END_FOR_EACH_PTR(op);
1370 }
1371
1372 static void check_dereference(struct expression *expr)
1373 {
1374 struct smatch_state *state;
1375
1376 if (__in_fake_assign)
1377 return;
1378 if (outside_of_function())
1379 return;
1380 state = get_extra_state(expr);
1381 if (state) {
1382 struct range_list *rl;
1383
1384 rl = rl_intersection(estate_rl(state), valid_ptr_rl);
1385 if (rl_equiv(rl, estate_rl(state)))
1386 return;
1387 set_extra_expr_nomod(expr, alloc_estate_rl(rl));
1388 } else {
1389 struct range_list *rl;
1390
1391 if (get_mtag_rl(expr, &rl))
1392 rl = rl_intersection(rl, valid_ptr_rl);
1393 else
1394 rl = clone_rl(valid_ptr_rl);
1395
1396 set_extra_expr_nomod(expr, alloc_estate_rl(rl));
1397 }
1398 }
1399
1400 static void match_dereferences(struct expression *expr)
1401 {
1402 if (expr->type != EXPR_PREOP)
1403 return;
1404 if (getting_address(expr))
1405 return;
1406 /* it's saying that foo[1] = bar dereferences foo[1] */
1407 if (is_array(expr))
1408 return;
1409 check_dereference(expr->unop);
1410 }
1411
1412 static void match_pointer_as_array(struct expression *expr)
1413 {
1414 if (!is_array(expr))
1415 return;
1416 check_dereference(get_array_base(expr));
1417 }
1418
1419 static void find_dereferences(struct expression *expr)
1420 {
1421 while (expr->type == EXPR_PREOP) {
1422 if (expr->op == '*')
1423 check_dereference(expr->unop);
1424 expr = strip_expr(expr->unop);
1425 }
1426 }
1427
1428 static void set_param_dereferenced(struct expression *call, struct expression *arg, char *key, char *unused)
1429 {
1430 struct symbol *sym;
1431 char *name;
1432
1433 name = get_variable_from_key(arg, key, &sym);
1434 if (name && sym) {
1435 struct smatch_state *orig, *new;
1436 struct range_list *rl;
1437
1438 orig = get_state(SMATCH_EXTRA, name, sym);
1439 if (orig) {
1440 rl = rl_intersection(estate_rl(orig),
1441 alloc_rl(valid_ptr_min_sval,
1442 valid_ptr_max_sval));
1443 new = alloc_estate_rl(rl);
1444 } else {
1445 new = alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval);
1446 }
1447
1448 set_extra_nomod(name, sym, NULL, new);
1449 }
1450 free_string(name);
1451
1452 find_dereferences(arg);
1453 }
1454
1455 static sval_t add_one(sval_t sval)
1456 {
1457 sval.value++;
1458 return sval;
1459 }
1460
1461 static int handle_postop_inc(struct expression *left, int op, struct expression *right)
1462 {
1463 struct statement *stmt;
1464 struct expression *cond;
1465 struct smatch_state *true_state, *false_state;
1466 struct symbol *type;
1467 sval_t start;
1468 sval_t limit;
1469
1470 /*
1471 * If we're decrementing here then that's a canonical while count down
1472 * so it's handled already. We're only handling loops like:
1473 * i = 0;
1474 * do { ... } while (i++ < 3);
1475 */
1476
1477 if (left->type != EXPR_POSTOP || left->op != SPECIAL_INCREMENT)
1478 return 0;
1479
1480 stmt = __cur_stmt->parent;
1481 if (!stmt)
1482 return 0;
1483 if (stmt->type == STMT_COMPOUND)
1484 stmt = stmt->parent;
1485 if (!stmt || stmt->type != STMT_ITERATOR || !stmt->iterator_post_condition)
1486 return 0;
1487
1488 cond = strip_expr(stmt->iterator_post_condition);
1489 if (cond->type != EXPR_COMPARE || cond->op != op)
1490 return 0;
1491 if (left != strip_expr(cond->left) || right != strip_expr(cond->right))
1492 return 0;
1493
1494 if (!get_implied_value(left->unop, &start))
1495 return 0;
1496 if (!get_implied_value(right, &limit))
1497 return 0;
1498 type = get_type(left->unop);
1499 limit = sval_cast(type, limit);
1500 if (sval_cmp(start, limit) > 0)
1501 return 0;
1502
1503 switch (op) {
1504 case '<':
1505 case SPECIAL_UNSIGNED_LT:
1506 break;
1507 case SPECIAL_LTE:
1508 case SPECIAL_UNSIGNED_LTE:
1509 limit = add_one(limit);
1510 default:
1511 return 0;
1512
1513 }
1514
1515 true_state = alloc_estate_range(add_one(start), limit);
1516 false_state = alloc_estate_range(add_one(limit), add_one(limit));
1517
1518 /* Currently we just discard the false state but when two passes is
1519 * implimented correctly then it will use it.
1520 */
1521
1522 set_extra_expr_true_false(left->unop, true_state, false_state);
1523
1524 return 1;
1525 }
1526
1527 bool is_impossible_variable(struct expression *expr)
1528 {
1529 struct smatch_state *state;
1530
1531 state = get_extra_state(expr);
1532 if (state && !estate_rl(state))
1533 return true;
1534 return false;
1535 }
1536
1537 static bool in_macro(struct expression *left, struct expression *right)
1538 {
1539 if (!left || !right)
1540 return 0;
1541 if (left->pos.line != right->pos.line || left->pos.pos != right->pos.pos)
1542 return 0;
1543 if (get_macro_name(left->pos))
1544 return 1;
1545 return 0;
1546 }
1547
1548 static void handle_comparison(struct symbol *type, struct expression *left, int op, struct expression *right)
1549 {
1550 struct smatch_state *left_state_orig, *right_state_orig;
1551 struct range_list *left_orig;
1552 struct range_list *left_true;
1553 struct range_list *left_false;
1554 struct range_list *right_orig;
1555 struct range_list *right_true;
1556 struct range_list *right_false;
1557 struct smatch_state *left_true_state;
1558 struct smatch_state *left_false_state;
1559 struct smatch_state *right_true_state;
1560 struct smatch_state *right_false_state;
1561 sval_t dummy, hard_max;
1562 int left_postop = 0;
1563 int right_postop = 0;
1564
1565 if (left->op == SPECIAL_INCREMENT || left->op == SPECIAL_DECREMENT) {
1566 if (left->type == EXPR_POSTOP) {
1567 left->smatch_flags |= Handled;
1568 left_postop = left->op;
1569 if (handle_postop_inc(left, op, right))
1570 return;
1571 }
1572 left = strip_parens(left->unop);
1573 }
1574 while (left->type == EXPR_ASSIGNMENT)
1575 left = strip_parens(left->left);
1576
1577 if (right->op == SPECIAL_INCREMENT || right->op == SPECIAL_DECREMENT) {
1578 if (right->type == EXPR_POSTOP) {
1579 right->smatch_flags |= Handled;
1580 right_postop = right->op;
1581 }
1582 right = strip_parens(right->unop);
1583 }
1584
1585 if (is_impossible_variable(left) || is_impossible_variable(right))
1586 return;
1587
1588 left_state_orig = get_extra_state(left);
1589 get_real_absolute_rl(left, &left_orig);
1590 left_orig = cast_rl(type, left_orig);
1591
1592 right_state_orig = get_extra_state(right);
1593 get_real_absolute_rl(right, &right_orig);
1594 right_orig = cast_rl(type, right_orig);
1595
1596 split_comparison_rl(left_orig, op, right_orig, &left_true, &left_false, &right_true, &right_false);
1597
1598 left_true = rl_truncate_cast(get_type(strip_expr(left)), left_true);
1599 left_false = rl_truncate_cast(get_type(strip_expr(left)), left_false);
1600 right_true = rl_truncate_cast(get_type(strip_expr(right)), right_true);
1601 right_false = rl_truncate_cast(get_type(strip_expr(right)), right_false);
1602
1603 if (!left_true || !left_false) {
1604 struct range_list *tmp_true, *tmp_false;
1605
1606 split_comparison_rl(alloc_whole_rl(type), op, right_orig, &tmp_true, &tmp_false, NULL, NULL);
1607 tmp_true = rl_truncate_cast(get_type(strip_expr(left)), tmp_true);
1608 tmp_false = rl_truncate_cast(get_type(strip_expr(left)), tmp_false);
1609 if (tmp_true && tmp_false)
1610 __save_imaginary_state(left, tmp_true, tmp_false);
1611 }
1612
1613 if (!right_true || !right_false) {
1614 struct range_list *tmp_true, *tmp_false;
1615
1616 split_comparison_rl(alloc_whole_rl(type), op, right_orig, NULL, NULL, &tmp_true, &tmp_false);
1617 tmp_true = rl_truncate_cast(get_type(strip_expr(right)), tmp_true);
1618 tmp_false = rl_truncate_cast(get_type(strip_expr(right)), tmp_false);
1619 if (tmp_true && tmp_false)
1620 __save_imaginary_state(right, tmp_true, tmp_false);
1621 }
1622
1623 left_true_state = alloc_estate_rl(left_true);
1624 left_false_state = alloc_estate_rl(left_false);
1625 right_true_state = alloc_estate_rl(right_true);
1626 right_false_state = alloc_estate_rl(right_false);
1627
1628 switch (op) {
1629 case '<':
1630 case SPECIAL_UNSIGNED_LT:
1631 case SPECIAL_UNSIGNED_LTE:
1632 case SPECIAL_LTE:
1633 if (get_hard_max(right, &dummy) && !in_macro(left, right))
1634 estate_set_hard_max(left_true_state);
1635 if (get_hard_max(left, &dummy) && !in_macro(left, right))
1636 estate_set_hard_max(right_false_state);
1637 break;
1638 case '>':
1639 case SPECIAL_UNSIGNED_GT:
1640 case SPECIAL_UNSIGNED_GTE:
1641 case SPECIAL_GTE:
1642 if (get_hard_max(left, &dummy) && !in_macro(left, right))
1643 estate_set_hard_max(right_true_state);
1644 if (get_hard_max(right, &dummy) && !in_macro(left, right))
1645 estate_set_hard_max(left_false_state);
1646 break;
1647 }
1648
1649 switch (op) {
1650 case '<':
1651 case SPECIAL_UNSIGNED_LT:
1652 case SPECIAL_UNSIGNED_LTE:
1653 case SPECIAL_LTE:
1654 if (get_hard_max(right, &hard_max)) {
1655 if (op == '<' || op == SPECIAL_UNSIGNED_LT)
1656 hard_max.value--;
1657 estate_set_fuzzy_max(left_true_state, hard_max);
1658 }
1659 if (get_implied_value(right, &hard_max)) {
1660 if (op == SPECIAL_UNSIGNED_LTE ||
1661 op == SPECIAL_LTE)
1662 hard_max.value++;
1663 estate_set_fuzzy_max(left_false_state, hard_max);
1664 }
1665 if (get_hard_max(left, &hard_max)) {
1666 if (op == SPECIAL_UNSIGNED_LTE ||
1667 op == SPECIAL_LTE)
1668 hard_max.value--;
1669 estate_set_fuzzy_max(right_false_state, hard_max);
1670 }
1671 if (get_implied_value(left, &hard_max)) {
1672 if (op == '<' || op == SPECIAL_UNSIGNED_LT)
1673 hard_max.value++;
1674 estate_set_fuzzy_max(right_true_state, hard_max);
1675 }
1676 break;
1677 case '>':
1678 case SPECIAL_UNSIGNED_GT:
1679 case SPECIAL_UNSIGNED_GTE:
1680 case SPECIAL_GTE:
1681 if (get_hard_max(left, &hard_max)) {
1682 if (op == '>' || op == SPECIAL_UNSIGNED_GT)
1683 hard_max.value--;
1684 estate_set_fuzzy_max(right_true_state, hard_max);
1685 }
1686 if (get_implied_value(left, &hard_max)) {
1687 if (op == SPECIAL_UNSIGNED_GTE ||
1688 op == SPECIAL_GTE)
1689 hard_max.value++;
1690 estate_set_fuzzy_max(right_false_state, hard_max);
1691 }
1692 if (get_hard_max(right, &hard_max)) {
1693 if (op == SPECIAL_UNSIGNED_LTE ||
1694 op == SPECIAL_LTE)
1695 hard_max.value--;
1696 estate_set_fuzzy_max(left_false_state, hard_max);
1697 }
1698 if (get_implied_value(right, &hard_max)) {
1699 if (op == '>' ||
1700 op == SPECIAL_UNSIGNED_GT)
1701 hard_max.value++;
1702 estate_set_fuzzy_max(left_true_state, hard_max);
1703 }
1704 break;
1705 case SPECIAL_EQUAL:
1706 if (get_hard_max(left, &hard_max))
1707 estate_set_fuzzy_max(right_true_state, hard_max);
1708 if (get_hard_max(right, &hard_max))
1709 estate_set_fuzzy_max(left_true_state, hard_max);
1710 break;
1711 }
1712
1713 if (get_hard_max(left, &hard_max)) {
1714 estate_set_hard_max(left_true_state);
1715 estate_set_hard_max(left_false_state);
1716 }
1717 if (get_hard_max(right, &hard_max)) {
1718 estate_set_hard_max(right_true_state);
1719 estate_set_hard_max(right_false_state);
1720 }
1721
1722 if (left_postop == SPECIAL_INCREMENT) {
1723 left_true_state = increment_state(left_true_state);
1724 left_false_state = increment_state(left_false_state);
1725 }
1726 if (left_postop == SPECIAL_DECREMENT) {
1727 left_true_state = decrement_state(left_true_state);
1728 left_false_state = decrement_state(left_false_state);
1729 }
1730 if (right_postop == SPECIAL_INCREMENT) {
1731 right_true_state = increment_state(right_true_state);
1732 right_false_state = increment_state(right_false_state);
1733 }
1734 if (right_postop == SPECIAL_DECREMENT) {
1735 right_true_state = decrement_state(right_true_state);
1736 right_false_state = decrement_state(right_false_state);
1737 }
1738
1739 if (estate_rl(left_true_state) && estates_equiv(left_true_state, left_false_state)) {
1740 left_true_state = NULL;
1741 left_false_state = NULL;
1742 }
1743
1744 if (estate_rl(right_true_state) && estates_equiv(right_true_state, right_false_state)) {
1745 right_true_state = NULL;
1746 right_false_state = NULL;
1747 }
1748
1749 /* Don't introduce new states for known true/false conditions */
1750 if (rl_equiv(estate_rl(left_state_orig), estate_rl(left_true_state)))
1751 left_true_state = NULL;
1752 if (rl_equiv(estate_rl(left_state_orig), estate_rl(left_false_state)))
1753 left_false_state = NULL;
1754 if (rl_equiv(estate_rl(right_state_orig), estate_rl(right_true_state)))
1755 right_true_state = NULL;
1756 if (rl_equiv(estate_rl(right_state_orig), estate_rl(right_false_state)))
1757 right_false_state = NULL;
1758
1759 set_extra_expr_true_false(left, left_true_state, left_false_state);
1760 set_extra_expr_true_false(right, right_true_state, right_false_state);
1761 }
1762
1763 static int is_simple_math(struct expression *expr)
1764 {
1765 if (!expr)
1766 return 0;
1767 if (expr->type != EXPR_BINOP)
1768 return 0;
1769 switch (expr->op) {
1770 case '+':
1771 case '-':
1772 case '*':
1773 return 1;
1774 }
1775 return 0;
1776 }
1777
1778 static int flip_op(int op)
1779 {
1780 /* We only care about simple math */
1781 switch (op) {
1782 case '+':
1783 return '-';
1784 case '-':
1785 return '+';
1786 case '*':
1787 return '/';
1788 }
1789 return 0;
1790 }
1791
1792 static void move_known_to_rl(struct expression **expr_p, struct range_list **rl_p)
1793 {
1794 struct expression *expr = *expr_p;
1795 struct range_list *rl = *rl_p;
1796 sval_t sval;
1797
1798 if (!is_simple_math(expr))
1799 return;
1800
1801 if (get_implied_value(expr->right, &sval)) {
1802 *expr_p = expr->left;
1803 *rl_p = rl_binop(rl, flip_op(expr->op), alloc_rl(sval, sval));
1804 move_known_to_rl(expr_p, rl_p);
1805 return;
1806 }
1807 if (expr->op == '-')
1808 return;
1809 if (get_implied_value(expr->left, &sval)) {
1810 *expr_p = expr->right;
1811 *rl_p = rl_binop(rl, flip_op(expr->op), alloc_rl(sval, sval));
1812 move_known_to_rl(expr_p, rl_p);
1813 return;
1814 }
1815 }
1816
1817 static void move_known_values(struct expression **left_p, struct expression **right_p)
1818 {
1819 struct expression *left = *left_p;
1820 struct expression *right = *right_p;
1821 sval_t sval, dummy;
1822
1823 if (get_implied_value(left, &sval)) {
1824 if (!is_simple_math(right))
1825 return;
1826 if (get_implied_value(right, &dummy))
1827 return;
1828 if (right->op == '*') {
1829 sval_t divisor;
1830
1831 if (!get_value(right->right, &divisor))
1832 return;
1833 if (divisor.value == 0)
1834 return;
1835 *left_p = binop_expression(left, invert_op(right->op), right->right);
1836 *right_p = right->left;
1837 return;
1838 }
1839 if (right->op == '+' && get_value(right->left, &sval)) {
1840 *left_p = binop_expression(left, invert_op(right->op), right->left);
1841 *right_p = right->right;
1842 return;
1843 }
1844 if (get_value(right->right, &sval)) {
1845 *left_p = binop_expression(left, invert_op(right->op), right->right);
1846 *right_p = right->left;
1847 return;
1848 }
1849 return;
1850 }
1851 if (get_implied_value(right, &sval)) {
1852 if (!is_simple_math(left))
1853 return;
1854 if (get_implied_value(left, &dummy))
1855 return;
1856 if (left->op == '*') {
1857 sval_t divisor;
1858
1859 if (!get_value(left->right, &divisor))
1860 return;
1861 if (divisor.value == 0)
1862 return;
1863 *right_p = binop_expression(right, invert_op(left->op), left->right);
1864 *left_p = left->left;
1865 return;
1866 }
1867 if (left->op == '+' && get_value(left->left, &sval)) {
1868 *right_p = binop_expression(right, invert_op(left->op), left->left);
1869 *left_p = left->right;
1870 return;
1871 }
1872
1873 if (get_value(left->right, &sval)) {
1874 *right_p = binop_expression(right, invert_op(left->op), left->right);
1875 *left_p = left->left;
1876 return;
1877 }
1878 return;
1879 }
1880 }
1881
1882 /*
1883 * The reason for do_simple_algebra() is to solve things like:
1884 * if (foo > 66 || foo + bar > 64) {
1885 * "foo" is not really a known variable so it won't be handled by
1886 * move_known_variables() but it's a super common idiom.
1887 *
1888 */
1889 static int do_simple_algebra(struct expression **left_p, struct expression **right_p)
1890 {
1891 struct expression *left = *left_p;
1892 struct expression *right = *right_p;
1893 struct range_list *rl;
1894 sval_t tmp;
1895
1896 if (left->type != EXPR_BINOP || left->op != '+')
1897 return 0;
1898 if (can_integer_overflow(get_type(left), left))
1899 return 0;
1900 if (!get_implied_value(right, &tmp))
1901 return 0;
1902
1903 if (!get_implied_value(left->left, &tmp) &&
1904 get_implied_rl(left->left, &rl) &&
1905 !is_whole_rl(rl)) {
1906 *right_p = binop_expression(right, '-', left->left);
1907 *left_p = left->right;
1908 return 1;
1909 }
1910 if (!get_implied_value(left->right, &tmp) &&
1911 get_implied_rl(left->right, &rl) &&
1912 !is_whole_rl(rl)) {
1913 *right_p = binop_expression(right, '-', left->right);
1914 *left_p = left->left;
1915 return 1;
1916 }
1917
1918 return 0;
1919 }
1920
1921 static int match_func_comparison(struct expression *expr)
1922 {
1923 struct expression *left = strip_expr(expr->left);
1924 struct expression *right = strip_expr(expr->right);
1925
1926 if (left->type == EXPR_CALL || right->type == EXPR_CALL) {
1927 // TODO: faked_assign this should be handled as a fake assignment instead
1928 function_comparison(left, expr->op, right);
1929 return 1;
1930 }
1931
1932 return 0;
1933 }
1934
1935 /* Handle conditions like "if (foo + bar < foo) {" */
1936 static int handle_integer_overflow_test(struct expression *expr)
1937 {
1938 struct expression *left, *right;
1939 struct symbol *type;
1940 sval_t left_min, right_min, min, max;
1941
1942 if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
1943 return 0;
1944
1945 left = strip_parens(expr->left);
1946 right = strip_parens(expr->right);
1947
1948 if (left->op != '+')
1949 return 0;
1950
1951 type = get_type(expr);
1952 if (!type)
1953 return 0;
1954 if (type_positive_bits(type) == 32) {
1955 max.type = &uint_ctype;
1956 max.uvalue = (unsigned int)-1;
1957 } else if (type_positive_bits(type) == 64) {
1958 max.type = &ulong_ctype;
1959 max.value = (unsigned long long)-1;
1960 } else {
1961 return 0;
1962 }
1963
1964 if (!expr_equiv(left->left, right) && !expr_equiv(left->right, right))
1965 return 0;
1966
1967 get_absolute_min(left->left, &left_min);
1968 get_absolute_min(left->right, &right_min);
1969 min = sval_binop(left_min, '+', right_min);
1970
1971 type = get_type(left);
1972 min = sval_cast(type, min);
1973 max = sval_cast(type, max);
1974
1975 set_extra_chunk_true_false(left, NULL, alloc_estate_range(min, max));
1976 return 1;
1977 }
1978
1979 static void match_comparison(struct expression *expr)
1980 {
1981 struct expression *left_orig = strip_parens(expr->left);
1982 struct expression *right_orig = strip_parens(expr->right);
1983 struct expression *left, *right, *tmp;
1984 struct expression *prev;
1985 struct symbol *type;
1986 int redo, count;
1987
1988 if (match_func_comparison(expr))
1989 return;
1990
1991 type = get_type(expr);
1992 if (!type)
1993 type = &llong_ctype;
1994
1995 if (handle_integer_overflow_test(expr))
1996 return;
1997
1998 left = left_orig;
1999 right = right_orig;
2000 move_known_values(&left, &right);
2001 handle_comparison(type, left, expr->op, right);
2002
2003 left = left_orig;
2004 right = right_orig;
2005 if (do_simple_algebra(&left, &right))
2006 handle_comparison(type, left, expr->op, right);
2007
2008 prev = get_assigned_expr(left_orig);
2009 if (is_simple_math(prev) && !has_variable(prev, left_orig)) {
2010 left = prev;
2011 right = right_orig;
2012 move_known_values(&left, &right);
2013 handle_comparison(type, left, expr->op, right);
2014 }
2015
2016 prev = get_assigned_expr(right_orig);
2017 if (is_simple_math(prev) && !has_variable(prev, right_orig)) {
2018 left = left_orig;
2019 right = prev;
2020 move_known_values(&left, &right);
2021 handle_comparison(type, left, expr->op, right);
2022 }
2023
2024 redo = 0;
2025 left = left_orig;
2026 right = right_orig;
2027 if (get_last_expr_from_expression_stmt(left_orig)) {
2028 left = get_last_expr_from_expression_stmt(left_orig);
2029 redo = 1;
2030 }
2031 if (get_last_expr_from_expression_stmt(right_orig)) {
2032 right = get_last_expr_from_expression_stmt(right_orig);
2033 redo = 1;
2034 }
2035
2036 if (!redo)
2037 return;
2038
2039 count = 0;
2040 while ((tmp = get_assigned_expr(left))) {
2041 if (count++ > 3)
2042 break;
2043 left = strip_expr(tmp);
2044 }
2045 count = 0;
2046 while ((tmp = get_assigned_expr(right))) {
2047 if (count++ > 3)
2048 break;
2049 right = strip_expr(tmp);
2050 }
2051
2052 handle_comparison(type, left, expr->op, right);
2053 }
2054
2055 static sval_t get_high_mask(sval_t known)
2056 {
2057 sval_t ret;
2058 int i;
2059
2060 ret = known;
2061 ret.value = 0;
2062
2063 for (i = type_bits(known.type) - 1; i >= 0; i--) {
2064 if (known.uvalue & (1ULL << i))
2065 ret.uvalue |= (1ULL << i);
2066 else
2067 return ret;
2068
2069 }
2070 return ret;
2071 }
2072
2073 static bool handle_bit_test(struct expression *expr)
2074 {
2075 struct range_list *orig_rl, *rlt, *rlf, *true_rl, *false_rl;
2076 struct expression *shift, *mask, *var;
2077 struct bit_info *bit_info;
2078 sval_t sval;
2079 sval_t high = { .type = &int_ctype };
2080 sval_t low = { .type = &int_ctype };
2081
2082 shift = strip_expr(expr->right);
2083 mask = strip_expr(expr->left);
2084 if (shift->type != EXPR_BINOP || shift->op != SPECIAL_LEFTSHIFT) {
2085 shift = strip_expr(expr->left);
2086 mask = strip_expr(expr->right);
2087 if (shift->type != EXPR_BINOP || shift->op != SPECIAL_LEFTSHIFT)
2088 return false;
2089 }
2090 if (!get_implied_value(shift->left, &sval) || sval.value != 1)
2091 return false;
2092 var = strip_expr(shift->right);
2093
2094 bit_info = get_bit_info(mask);
2095 if (!bit_info)
2096 return false;
2097 if (!bit_info->possible){
2098 set_true_false_states_expr(my_id, var, alloc_estate_empty(), NULL);
2099 return false;
2100 }
2101
2102 get_absolute_rl(var, &orig_rl);
2103 if (sval_is_negative(rl_min(orig_rl)) ||
2104 rl_max(orig_rl).uvalue > type_bits(get_type(shift->left)))
2105 return false;
2106
2107 low.value = ffsll(bit_info->possible) - 1;
2108 high.value = sm_fls64(bit_info->possible) - 1;
2109 rlt = alloc_rl(low, high);
2110 rlt = cast_rl(get_type(var), rlt);
2111 true_rl = rl_intersection(orig_rl, rlt);
2112
2113 low.value = ffsll(bit_info->set) - 1;
2114 high.value = sm_fls64(bit_info->set) - 1;
2115 rlf = alloc_rl(low, high);
2116 rlf = cast_rl(get_type(var), rlf);
2117 false_rl = rl_filter(orig_rl, rlf);
2118
2119 set_extra_expr_true_false(var, alloc_estate_rl(true_rl), alloc_estate_rl(false_rl));
2120
2121 return true;
2122 }
2123
2124 static void handle_AND_op(struct expression *var, sval_t known)
2125 {
2126 struct range_list *orig_rl;
2127 struct range_list *true_rl = NULL;
2128 struct range_list *false_rl = NULL;
2129 int bit;
2130 sval_t low_mask = known;
2131 sval_t high_mask;
2132 sval_t max;
2133
2134 get_absolute_rl(var, &orig_rl);
2135
2136 if (known.value > 0) {
2137 bit = ffsll(known.value) - 1;
2138 low_mask.uvalue = (1ULL << bit) - 1;
2139 true_rl = remove_range(orig_rl, sval_type_val(known.type, 0), low_mask);
2140 }
2141 high_mask = get_high_mask(known);
2142 if (high_mask.value) {
2143 bit = ffsll(high_mask.value) - 1;
2144 low_mask.uvalue = (1ULL << bit) - 1;
2145
2146 false_rl = orig_rl;
2147 if (sval_is_negative(rl_min(orig_rl)))
2148 false_rl = remove_range(false_rl, sval_type_min(known.type), sval_type_val(known.type, -1));
2149 false_rl = remove_range(false_rl, low_mask, sval_type_max(known.type));
2150 if (type_signed(high_mask.type) && type_unsigned(rl_type(false_rl))) {
2151 false_rl = remove_range(false_rl,
2152 sval_type_val(rl_type(false_rl), sval_type_max(known.type).uvalue),
2153 sval_type_val(rl_type(false_rl), -1));
2154 }
2155 } else if (known.value == 1 &&
2156 get_hard_max(var, &max) &&
2157 sval_cmp(max, rl_max(orig_rl)) == 0 &&
2158 max.value & 1) {
2159 false_rl = remove_range(orig_rl, max, max);
2160 }
2161 set_extra_expr_true_false(var,
2162 true_rl ? alloc_estate_rl(true_rl) : NULL,
2163 false_rl ? alloc_estate_rl(false_rl) : NULL);
2164 }
2165
2166 static void handle_AND_condition(struct expression *expr)
2167 {
2168 sval_t known;
2169
2170 if (handle_bit_test(expr))
2171 return;
2172
2173 if (get_implied_value(expr->left, &known))
2174 handle_AND_op(expr->right, known);
2175 else if (get_implied_value(expr->right, &known))
2176 handle_AND_op(expr->left, known);
2177 }
2178
2179 static void handle_MOD_condition(struct expression *expr)
2180 {
2181 struct range_list *orig_rl;
2182 struct range_list *true_rl;
2183 struct range_list *false_rl = NULL;
2184 sval_t right;
2185 sval_t zero = {
2186 .value = 0,
2187 };
2188
2189 if (!get_implied_value(expr->right, &right) || right.value == 0)
2190 return;
2191 get_absolute_rl(expr->left, &orig_rl);
2192
2193 zero.type = rl_type(orig_rl);
2194
2195 /* We're basically dorking around the min and max here */
2196 true_rl = remove_range(orig_rl, zero, zero);
2197 if (!sval_is_max(rl_max(true_rl)) &&
2198 !(rl_max(true_rl).value % right.value))
2199 true_rl = remove_range(true_rl, rl_max(true_rl), rl_max(true_rl));
2200
2201 if (rl_equiv(true_rl, orig_rl))
2202 true_rl = NULL;
2203
2204 if (sval_is_positive(rl_min(orig_rl)) &&
2205 (rl_max(orig_rl).value - rl_min(orig_rl).value) / right.value < 5) {
2206 sval_t add;
2207 int i;
2208
2209 add = rl_min(orig_rl);
2210 add.value += right.value - (add.value % right.value);
2211 add.value -= right.value;
2212
2213 for (i = 0; i < 5; i++) {
2214 add.value += right.value;
2215 if (add.value > rl_max(orig_rl).value)
2216 break;
2217 add_range(&false_rl, add, add);
2218 }
2219 } else {
2220 if (rl_min(orig_rl).uvalue != 0 &&
2221 rl_min(orig_rl).uvalue < right.uvalue) {
2222 sval_t chop = right;
2223 chop.value--;
2224 false_rl = remove_range(orig_rl, zero, chop);
2225 }
2226
2227 if (!sval_is_max(rl_max(orig_rl)) &&
2228 (rl_max(orig_rl).value % right.value)) {
2229 sval_t chop = rl_max(orig_rl);
2230 chop.value -= chop.value % right.value;
2231 chop.value++;
2232 if (!false_rl)
2233 false_rl = clone_rl(orig_rl);
2234 false_rl = remove_range(false_rl, chop, rl_max(orig_rl));
2235 }
2236 }
2237
2238 set_extra_expr_true_false(expr->left,
2239 true_rl ? alloc_estate_rl(true_rl) : NULL,
2240 false_rl ? alloc_estate_rl(false_rl) : NULL);
2241 }
2242
2243 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
2244 void __extra_match_condition(struct expression *expr)
2245 {
2246 expr = strip_expr(expr);
2247 switch (expr->type) {
2248 case EXPR_CALL:
2249 function_comparison(expr, SPECIAL_NOTEQUAL, zero_expr());
2250 return;
2251 case EXPR_PREOP:
2252 case EXPR_SYMBOL:
2253 case EXPR_DEREF:
2254 handle_comparison(get_type(expr), expr, SPECIAL_NOTEQUAL, zero_expr());
2255 return;
2256 case EXPR_COMPARE:
2257 match_comparison(expr);
2258 return;
2259 case EXPR_ASSIGNMENT:
2260 __extra_match_condition(expr->left);
2261 return;
2262 case EXPR_BINOP:
2263 if (expr->op == '&')
2264 handle_AND_condition(expr);
2265 if (expr->op == '%')
2266 handle_MOD_condition(expr);
2267 return;
2268 }
2269 }
2270
2271 static void assume_indexes_are_valid(struct expression *expr)
2272 {
2273 struct expression *array_expr;
2274 int array_size;
2275 struct expression *offset;
2276 struct symbol *offset_type;
2277 struct range_list *rl_before;
2278 struct range_list *rl_after;
2279 struct range_list *filter = NULL;
2280 sval_t size;
2281
2282 expr = strip_expr(expr);
2283 if (!is_array(expr))
2284 return;
2285
2286 offset = get_array_offset(expr);
2287 offset_type = get_type(offset);
2288 if (offset_type && type_signed(offset_type)) {
2289 filter = alloc_rl(sval_type_min(offset_type),
2290 sval_type_val(offset_type, -1));
2291 }
2292
2293 array_expr = get_array_base(expr);
2294 array_size = get_real_array_size(array_expr);
2295 if (array_size > 1) {
2296 size = sval_type_val(offset_type, array_size);
2297 add_range(&filter, size, sval_type_max(offset_type));
2298 }
2299
2300 if (!filter)
2301 return;
2302 get_absolute_rl(offset, &rl_before);
2303 rl_after = rl_filter(rl_before, filter);
2304 if (rl_equiv(rl_before, rl_after))
2305 return;
2306 set_extra_expr_nomod(offset, alloc_estate_rl(rl_after));
2307 }
2308
2309 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
2310 int implied_not_equal(struct expression *expr, long long val)
2311 {
2312 return !possibly_false(expr, SPECIAL_NOTEQUAL, value_expr(val));
2313 }
2314
2315 int implied_not_equal_name_sym(char *name, struct symbol *sym, long long val)
2316 {
2317 struct smatch_state *estate;
2318
2319 estate = get_state(SMATCH_EXTRA, name, sym);
2320 if (!estate)
2321 return 0;
2322 if (!rl_has_sval(estate_rl(estate), sval_type_val(estate_type(estate), 0)))
2323 return 1;
2324 return 0;
2325 }
2326
2327 bool is_noderef_ptr(struct expression *expr)
2328 {
2329 struct range_list *rl;
2330
2331 if (!get_implied_rl(expr, &rl))
2332 return false;
2333 return is_noderef_ptr_rl(rl);
2334 }
2335
2336 static int parent_is_err_or_null_var_sym_helper(const char *name, struct symbol *sym, bool check_err_ptr)
2337 {
2338 struct smatch_state *state;
2339 char buf[256];
2340 char *start;
2341 int len;
2342
2343 strncpy(buf, name, sizeof(buf) - 1);
2344 buf[sizeof(buf) - 1] = '\0';
2345
2346 start = &buf[0];
2347 while (*start == '*') {
2348 start++;
2349 state = __get_state(SMATCH_EXTRA, start, sym);
2350 if (!state)
2351 continue;
2352 if (!estate_rl(state))
2353 return 1;
2354 if (is_noderef_ptr_rl(estate_rl(state)))
2355 return 1;
2356 }
2357
2358 start = &buf[0];
2359 while (*start == '&')
2360 start++;
2361
2362 len = strlen(start);
2363 while (true) {
2364 while (len > 0) {
2365 len--;
2366 if (start[len] == '-' ||
2367 start[len] == '.') {
2368 start[len] = '\0';
2369 break;
2370 }
2371 }
2372 if (len == 0)
2373 return 0;
2374 state = __get_state(SMATCH_EXTRA, start, sym);
2375 if (!state)
2376 continue;
2377 if (is_noderef_ptr_rl(estate_rl(state)))
2378 return 1;
2379 }
2380 }
2381
2382 int parent_is_null_var_sym(const char *name, struct symbol *sym)
2383 {
2384 return parent_is_err_or_null_var_sym_helper(name, sym, false);
2385 }
2386
2387 int parent_is_err_or_null_var_sym(const char *name, struct symbol *sym)
2388 {
2389 return parent_is_err_or_null_var_sym_helper(name, sym, (option_project == PROJ_KERNEL));
2390 }
2391
2392 int parent_is_null(struct expression *expr)
2393 {
2394 struct symbol *sym;
2395 char *var;
2396 int ret = 0;
2397
2398 expr = strip_expr(expr);
2399 var = expr_to_var_sym(expr, &sym);
2400 if (!var || !sym)
2401 goto free;
2402 ret = parent_is_null_var_sym(var, sym);
2403 free:
2404 free_string(var);
2405 return ret;
2406 }
2407
2408 static int param_used_callback(void *found, int argc, char **argv, char **azColName)
2409 {
2410 *(int *)found = 1;
2411 return 0;
2412 }
2413
2414 static int is_kzalloc_info(struct sm_state *sm)
2415 {
2416 sval_t sval;
2417
2418 /*
2419 * kzalloc() information is treated as special because so there is just
2420 * a lot of stuff initialized to zero and it makes building the database
2421 * take hours and hours.
2422 *
2423 * In theory, we should just remove this line and not pass any unused
2424 * information, but I'm not sure enough that this code works so I want
2425 * to hold off on that for now.
2426 */
2427 if (!estate_get_single_value(sm->state, &sval))
2428 return 0;
2429 if (sval.value != 0)
2430 return 0;
2431 return 1;
2432 }
2433
2434 static int is_really_long(struct sm_state *sm)
2435 {
2436 const char *p;
2437 int cnt = 0;
2438
2439 p = sm->name;
2440 while ((p = strstr(p, "->"))) {
2441 p += 2;
2442 cnt++;
2443 }
2444
2445 if (cnt < 3 ||
2446 strlen(sm->name) < 40)
2447 return 0;
2448 return 1;
2449 }
2450
2451 static int filter_unused_param_value_info(struct expression *call, int param, char *printed_name, struct sm_state *sm)
2452 {
2453 int found = 0;
2454
2455 /* for function pointers assume everything is used */
2456 if (call->fn->type != EXPR_SYMBOL)
2457 return 0;
2458
2459 if (strcmp(printed_name, "$") == 0 ||
2460 strcmp(printed_name, "*$") == 0)
2461 return 0;
2462
2463 /*
2464 * This is to handle __builtin_mul_overflow(). In an ideal world we
2465 * would only need this for invalid code.
2466 *
2467 */
2468 if (!call->fn->symbol)
2469 return 0;
2470
2471 if (!is_kzalloc_info(sm) && !is_really_long(sm))
2472 return 0;
2473
2474 run_sql(&param_used_callback, &found,
2475 "select * from return_implies where %s and type = %d and parameter = %d and key = '%s';",
2476 get_static_filter(call->fn->symbol), PARAM_USED, param, printed_name);
2477 if (found)
2478 return 0;
2479
2480 /* If the database is not built yet, then assume everything is used */
2481 run_sql(&param_used_callback, &found,
2482 "select * from return_implies where %s and type = %d;",
2483 get_static_filter(call->fn->symbol), PARAM_USED);
2484 if (!found)
2485 return 0;
2486
2487 return 1;
2488 }
2489
2490 struct range_list *intersect_with_real_abs_var_sym(const char *name, struct symbol *sym, struct range_list *start)
2491 {
2492 struct smatch_state *state;
2493
2494 /*
2495 * Here is the difference between implied value and real absolute, say
2496 * you have:
2497 *
2498 * int a = (u8)x;
2499 *
2500 * Then you know that a is 0-255. That's real absolute. But you don't
2501 * know for sure that it actually goes up to 255. So it's not implied.
2502 * Implied indicates a degree of certainty.
2503 *
2504 * But then say you cap "a" at 8. That means you know it goes up to
2505 * 8. So now the implied value is s32min-8. But you can combine it
2506 * with the real absolute to say that actually it's 0-8.
2507 *
2508 * We are combining it here. But now that I think about it, this is
2509 * probably not the ideal place to combine it because it should proably
2510 * be done earlier. Oh well, this is an improvement on what was there
2511 * before so I'm going to commit this code.
2512 *
2513 */
2514
2515 state = get_real_absolute_state_var_sym(name, sym);
2516 if (!state || !estate_rl(state))
2517 return start;
2518
2519 return rl_intersection(estate_rl(state), start);
2520 }
2521
2522 struct range_list *intersect_with_real_abs_expr(struct expression *expr, struct range_list *start)
2523 {
2524 struct smatch_state *state;
2525 struct range_list *abs_rl;
2526
2527 state = get_real_absolute_state(expr);
2528 if (!state || !estate_rl(state))
2529 return start;
2530
2531 abs_rl = cast_rl(rl_type(start), estate_rl(state));
2532 return rl_intersection(abs_rl, start);
2533 }
2534
2535 static void caller_info_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
2536 {
2537 struct range_list *rl;
2538 sval_t dummy;
2539
2540 if (estate_is_whole(sm->state) || !estate_rl(sm->state))
2541 return;
2542 if (filter_unused_param_value_info(call, param, printed_name, sm))
2543 return;
2544 rl = estate_rl(sm->state);
2545 rl = intersect_with_real_abs_var_sym(sm->name, sm->sym, rl);
2546 if (!rl)
2547 return;
2548 sql_insert_caller_info(call, PARAM_VALUE, param, printed_name, show_rl(rl));
2549 if (!estate_get_single_value(sm->state, &dummy)) {
2550 if (estate_has_hard_max(sm->state))
2551 sql_insert_caller_info(call, HARD_MAX, param, printed_name,
2552 sval_to_str(estate_max(sm->state)));
2553 if (estate_has_fuzzy_max(sm->state))
2554 sql_insert_caller_info(call, FUZZY_MAX, param, printed_name,
2555 sval_to_str(estate_get_fuzzy_max(sm->state)));
2556 }
2557 }
2558
2559 static void returned_struct_members(int return_id, char *return_ranges, struct expression *expr)
2560 {
2561 struct symbol *returned_sym;
2562 char *returned_name;
2563 struct sm_state *sm;
2564 char *compare_str;
2565 char name_buf[256];
2566 char val_buf[256];
2567 int len;
2568
2569 // FIXME handle *$
2570
2571 if (!is_pointer(expr))
2572 return;
2573 if (return_ranges && strstr(return_ranges, "[==$"))
2574 return;
2575
2576 returned_name = expr_to_var_sym(expr, &returned_sym);
2577 if (!returned_name || !returned_sym)
2578 goto free;
2579 len = strlen(returned_name);
2580
2581 FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
2582 if (!estate_rl(sm->state))
2583 continue;
2584 if (returned_sym != sm->sym)
2585 continue;
2586 if (strncmp(returned_name, sm->name, len) != 0)
2587 continue;
2588 if (sm->name[len] != '-')
2589 continue;
2590
2591 snprintf(name_buf, sizeof(name_buf), "$%s", sm->name + len);
2592
2593 compare_str = name_sym_to_param_comparison(sm->name, sm->sym);
2594 if (!compare_str && estate_is_whole(sm->state))
2595 continue;
2596 snprintf(val_buf, sizeof(val_buf), "%s%s", sm->state->name, compare_str ?: "");
2597
2598 sql_insert_return_states(return_id, return_ranges, PARAM_VALUE,
2599 -1, name_buf, val_buf);
2600 } END_FOR_EACH_SM(sm);
2601
2602 free:
2603 free_string(returned_name);
2604 }
2605
2606 static void db_limited_before(void)
2607 {
2608 unmatched_stree = clone_stree(__get_cur_stree());
2609 }
2610
2611 static void db_limited_after(void)
2612 {
2613 free_stree(&unmatched_stree);
2614 }
2615
2616 static int basically_the_same(struct range_list *orig, struct range_list *new)
2617 {
2618 if (type_is_ptr(rl_type(orig)) &&
2619 is_whole_ptr_rl(orig) &&
2620 is_whole_ptr_rl(new))
2621 return true;
2622
2623 return rl_equiv(orig, new);
2624 }
2625
2626 static void db_param_limit_binops(struct expression *arg, char *key, struct range_list *rl)
2627 {
2628 struct range_list *left_rl;
2629 sval_t zero = { .type = rl_type(rl), };
2630 sval_t sval;
2631
2632 if (strcmp(key, "$") != 0)
2633 return;
2634 if (arg->op != '*')
2635 return;
2636 if (!get_implied_value(arg->right, &sval))
2637 return;
2638 if (can_integer_overflow(get_type(arg), arg))
2639 return;
2640
2641 left_rl = rl_binop(rl, '/', alloc_rl(sval, sval));
2642 if (!rl_has_sval(rl, zero))
2643 left_rl = remove_range(left_rl, zero, zero);
2644
2645 set_extra_expr_nomod(arg->left, alloc_estate_rl(left_rl));
2646 }
2647
2648 static void db_param_limit_filter(struct expression *expr, int param, char *key, char *value, enum info_type op)
2649 {
2650 struct smatch_state *state;
2651 struct expression *arg;
2652 char *name;
2653 struct symbol *sym;
2654 struct var_sym_list *vsl = NULL;
2655 struct sm_state *sm;
2656 struct symbol *compare_type, *var_type;
2657 struct range_list *rl;
2658 struct range_list *limit;
2659 struct range_list *new;
2660 char *other_name;
2661 struct symbol *other_sym;
2662
2663 while (expr->type == EXPR_ASSIGNMENT)
2664 expr = strip_expr(expr->right);
2665 if (expr->type != EXPR_CALL)
2666 return;
2667
2668 arg = get_argument_from_call_expr(expr->args, param);
2669 if (!arg)
2670 return;
2671
2672 if (strcmp(key, "$") == 0)
2673 compare_type = get_arg_type(expr->fn, param);
2674 else
2675 compare_type = get_member_type_from_key(arg, key);
2676
2677 call_results_to_rl(expr, compare_type, value, &limit);
2678 if (strcmp(key, "$") == 0)
2679 move_known_to_rl(&arg, &limit);
2680 name = get_chunk_from_key(arg, key, &sym, &vsl);
2681 if (!name)
2682 return;
2683 if (op != PARAM_LIMIT && !sym)
2684 goto free;
2685
2686 sm = get_sm_state(SMATCH_EXTRA, name, sym);
2687 if (sm)
2688 rl = estate_rl(sm->state);
2689 else
2690 rl = alloc_whole_rl(compare_type);
2691
2692 if (op == PARAM_LIMIT && !rl_fits_in_type(rl, compare_type))
2693 goto free;
2694
2695 new = rl_intersection(rl, limit);
2696
2697 var_type = get_member_type_from_key(arg, key);
2698 new = cast_rl(var_type, new);
2699
2700 /* We want to preserve the implications here */
2701 if (sm && basically_the_same(rl, new))
2702 goto free;
2703 other_name = get_other_name_sym(name, sym, &other_sym);
2704
2705 state = alloc_estate_rl(new);
2706 if (sm && estate_has_hard_max(sm->state))
2707 estate_set_hard_max(state);
2708
2709 if (op == PARAM_LIMIT) {
2710 set_extra_nomod_vsl(name, sym, vsl, NULL, state);
2711 } else
2712 set_extra_mod(name, sym, NULL, state);
2713
2714 if (other_name && other_sym) {
2715 state = clone_estate(state);
2716 if (op == PARAM_LIMIT)
2717 set_extra_nomod_vsl(other_name, other_sym, vsl, NULL, state);
2718 else
2719 set_extra_mod(other_name, other_sym, NULL, state);
2720 }
2721
2722 if (op == PARAM_LIMIT && arg->type == EXPR_BINOP)
2723 db_param_limit_binops(arg, key, new);
2724 free:
2725 free_string(name);
2726 }
2727
2728 static void db_param_limit(struct expression *expr, int param, char *key, char *value)
2729 {
2730 db_param_limit_filter(expr, param, key, value, PARAM_LIMIT);
2731 }
2732
2733 static void db_param_filter(struct expression *expr, int param, char *key, char *value)
2734 {
2735 db_param_limit_filter(expr, param, key, value, PARAM_FILTER);
2736 }
2737
2738 static void db_param_add_set(struct expression *expr, int param, char *key, char *value, enum info_type op)
2739 {
2740 struct expression *arg, *gen_expr;
2741 char *name;
2742 char *other_name = NULL;
2743 struct symbol *sym, *other_sym;
2744 struct symbol *param_type, *arg_type;
2745 struct smatch_state *state;
2746 struct range_list *new = NULL;
2747 struct range_list *added = NULL;
2748
2749 while (expr->type == EXPR_ASSIGNMENT)
2750 expr = strip_expr(expr->right);
2751 if (expr->type != EXPR_CALL)
2752 return;
2753
2754 arg = get_argument_from_call_expr(expr->args, param);
2755 if (!arg)
2756 return;
2757
2758 arg_type = get_arg_type_from_key(expr->fn, param, arg, key);
2759 param_type = get_member_type_from_key(arg, key);
2760 if (param_type && param_type->type == SYM_STRUCT)
2761 return;
2762 name = get_variable_from_key(arg, key, &sym);
2763 if (!name || !sym)
2764 goto free;
2765 gen_expr = gen_expression_from_key(arg, key);
2766
2767 state = get_state(SMATCH_EXTRA, name, sym);
2768 if (state)
2769 new = estate_rl(state);
2770
2771 call_results_to_rl(expr, arg_type, value, &added);
2772 added = cast_rl(param_type, added);
2773 if (op == PARAM_SET)
2774 new = added;
2775 else
2776 new = rl_union(new, added);
2777
2778 other_name = get_other_name_sym_nostack(name, sym, &other_sym);
2779 set_extra_mod(name, sym, gen_expr, alloc_estate_rl(new));
2780 if (other_name && other_sym)
2781 set_extra_mod(other_name, other_sym, gen_expr, alloc_estate_rl(new));
2782 free:
2783 free_string(other_name);
2784 free_string(name);
2785 }
2786
2787 static void db_param_add(struct expression *expr, int param, char *key, char *value)
2788 {
2789 in_param_set = true;
2790 db_param_add_set(expr, param, key, value, PARAM_ADD);
2791 in_param_set = false;
2792 }
2793
2794 static void db_param_set(struct expression *expr, int param, char *key, char *value)
2795 {
2796 in_param_set = true;
2797 db_param_add_set(expr, param, key, value, PARAM_SET);
2798 in_param_set = false;
2799 }
2800
2801 static void match_lost_param(struct expression *call, int param)
2802 {
2803 struct expression *arg;
2804
2805 if (is_const_param(call->fn, param))
2806 return;
2807
2808 arg = get_argument_from_call_expr(call->args, param);
2809 if (!arg)
2810 return;
2811
2812 arg = strip_expr(arg);
2813 if (arg->type == EXPR_PREOP && arg->op == '&')
2814 set_extra_expr_mod(arg->unop, alloc_estate_whole(get_type(arg->unop)));
2815 else
2816 ; /* if pointer then set struct members, maybe?*/
2817 }
2818
2819 static void db_param_value(struct expression *expr, int param, char *key, char *value)
2820 {
2821 struct expression *call;
2822 char *name;
2823 struct symbol *sym;
2824 struct symbol *type;
2825 struct range_list *rl = NULL;
2826
2827 if (param != -1)
2828 return;
2829
2830 call = expr;
2831 while (call->type == EXPR_ASSIGNMENT)
2832 call = strip_expr(call->right);
2833 if (call->type != EXPR_CALL)
2834 return;
2835
2836 type = get_member_type_from_key(expr->left, key);
2837 name = get_variable_from_key(expr->left, key, &sym);
2838 if (!name || !sym)
2839 goto free;
2840
2841 call_results_to_rl(call, type, value, &rl);
2842
2843 set_extra_mod(name, sym, NULL, alloc_estate_rl(rl));
2844 free:
2845 free_string(name);
2846 }
2847
2848 static void set_param_value(const char *name, struct symbol *sym, char *key, char *value)
2849 {
2850 struct expression *expr;
2851 struct range_list *rl = NULL;
2852 struct smatch_state *state;
2853 struct symbol *type;
2854 char *key_orig = key;
2855 char *fullname;
2856 sval_t dummy;
2857
2858 expr = symbol_expression(sym);
2859 fullname = get_variable_from_key(expr, key, NULL);
2860 if (!fullname)
2861 return;
2862
2863 type = get_member_type_from_key(expr, key_orig);
2864 str_to_rl(type, value, &rl);
2865 state = alloc_estate_rl(rl);
2866 if (estate_get_single_value(state, &dummy))
2867 estate_set_hard_max(state);
2868 set_state(SMATCH_EXTRA, fullname, sym, state);
2869 }
2870
2871 static void set_param_fuzzy_max(const char *name, struct symbol *sym, char *key, char *value)
2872 {
2873 struct expression *expr;
2874 struct range_list *rl = NULL;
2875 struct smatch_state *state;
2876 struct symbol *type;
2877 char *fullname;
2878 sval_t max;
2879
2880 expr = symbol_expression(sym);
2881 fullname = get_variable_from_key(expr, key, NULL);
2882 if (!fullname)
2883 return;
2884
2885 state = get_state(SMATCH_EXTRA, fullname, sym);
2886 if (!state)
2887 return;
2888 type = estate_type(state);
2889 str_to_rl(type, value, &rl);
2890 if (!rl_to_sval(rl, &max))
2891 return;
2892 estate_set_fuzzy_max(state, max);
2893 }
2894
2895 static void set_param_hard_max(const char *name, struct symbol *sym, char *key, char *value)
2896 {
2897 struct smatch_state *state;
2898 struct expression *expr;
2899 char *fullname;
2900
2901 expr = symbol_expression(sym);
2902 fullname = get_variable_from_key(expr, key, NULL);
2903 if (!fullname)
2904 return;
2905
2906 state = get_state(SMATCH_EXTRA, fullname, sym);
2907 if (!state)
2908 return;
2909 estate_set_hard_max(state);
2910 }
2911
2912 static struct sm_state *get_sm_from_call(struct expression *expr)
2913 {
2914 struct expression *fake;
2915 struct sm_state *ret;
2916 char buf[32];
2917
2918 if (is_fake_call(expr))
2919 return NULL;
2920
2921 fake = expr_get_fake_parent_expr(expr);
2922 if (fake && fake->type == EXPR_ASSIGNMENT) {
2923 ret = get_sm_state_expr(SMATCH_EXTRA, fake->left);
2924 if (ret)
2925 return ret;
2926 }
2927
2928 snprintf(buf, sizeof(buf), "return %p", expr);
2929 return get_sm_state(SMATCH_EXTRA, buf, NULL);
2930 }
2931
2932 struct sm_state *get_extra_sm_state(struct expression *expr)
2933 {
2934 char *name;
2935 struct symbol *sym;
2936 struct sm_state *ret = NULL;
2937
2938 expr = strip_expr(expr);
2939 if (!expr)
2940 return NULL;
2941
2942 if (expr->type == EXPR_CALL)
2943 return get_sm_from_call(expr);
2944
2945 name = expr_to_known_chunk_sym(expr, &sym);
2946 if (!name)
2947 goto free;
2948
2949 ret = get_sm_state(SMATCH_EXTRA, name, sym);
2950 free:
2951 free_string(name);
2952 return ret;
2953 }
2954
2955 struct smatch_state *get_extra_state(struct expression *expr)
2956 {
2957 struct sm_state *sm;
2958
2959 sm = get_extra_sm_state(expr);
2960 if (!sm)
2961 return NULL;
2962 return sm->state;
2963 }
2964
2965 void register_smatch_extra(int id)
2966 {
2967 my_id = id;
2968
2969 set_dynamic_states(my_id);
2970 add_merge_hook(my_id, &merge_estates);
2971 add_unmatched_state_hook(my_id, &unmatched_state);
2972 select_caller_info_hook(set_param_value, PARAM_VALUE);
2973 select_caller_info_hook(set_param_fuzzy_max, FUZZY_MAX);
2974 select_caller_info_hook(set_param_hard_max, HARD_MAX);
2975 select_return_states_before(&db_limited_before);
2976 select_return_states_hook(PARAM_LIMIT, &db_param_limit);
2977 select_return_states_hook(PARAM_FILTER, &db_param_filter);
2978 select_return_states_hook(PARAM_ADD, &db_param_add);
2979 select_return_states_hook(PARAM_SET, &db_param_set);
2980 add_lost_param_hook(&match_lost_param);
2981 select_return_states_hook(PARAM_VALUE, &db_param_value);
2982 select_return_states_after(&db_limited_after);
2983 }
2984
2985 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr)
2986 {
2987 struct var_sym_list *links;
2988 struct var_sym *tmp;
2989 struct smatch_state *state;
2990
2991 links = sm->state->data;
2992
2993 FOR_EACH_PTR(links, tmp) {
2994 if (sm->sym == tmp->sym &&
2995 strcmp(sm->name, tmp->var) == 0)
2996 continue;
2997 state = get_state(SMATCH_EXTRA, tmp->var, tmp->sym);
2998 if (!state)
2999 continue;
3000 set_state(SMATCH_EXTRA, tmp->var, tmp->sym, alloc_estate_whole(estate_type(state)));
3001 } END_FOR_EACH_PTR(tmp);
3002 set_state(link_id, sm->name, sm->sym, &undefined);
3003 }
3004
3005 void register_smatch_extra_links(int id)
3006 {
3007 link_id = id;
3008 set_dynamic_states(link_id);
3009 }
3010
3011 void register_smatch_extra_late(int id)
3012 {
3013 add_merge_hook(link_id, &merge_link_states);
3014 add_modification_hook(link_id, &match_link_modify);
3015 add_hook(&match_dereferences, DEREF_HOOK);
3016 add_hook(&match_pointer_as_array, OP_HOOK);
3017 select_return_implies_hook_early(DEREFERENCE, &set_param_dereferenced);
3018 add_hook(&match_function_call, FUNCTION_CALL_HOOK);
3019 add_hook(&match_assign, ASSIGNMENT_HOOK);
3020 add_hook(&match_assign, GLOBAL_ASSIGNMENT_HOOK);
3021 add_hook(&unop_expr, OP_HOOK);
3022 add_hook(&asm_expr, ASM_HOOK);
3023
3024 add_caller_info_callback(my_id, caller_info_callback);
3025 add_split_return_callback(&returned_struct_members);
3026
3027 // add_hook(&assume_indexes_are_valid, OP_HOOK);
3028 }
Static analysis for C