2 * Copyright (C) 2015 Oracle.
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.
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.
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
19 * This is to track when variables are masked away.
24 #include "smatch_extra.h"
25 #include "smatch_slist.h"
29 ALLOCATOR(bit_info
, "bit data");
30 struct bit_info
*alloc_bit_info(unsigned long long set
, unsigned long long possible
)
32 struct bit_info
*bit_info
= __alloc_bit_info(0);
35 bit_info
->possible
= possible
;
40 void set_bits_modified_expr(struct expression
*expr
, struct smatch_state
*state
)
42 __set_param_modified_helper(expr
, state
);
43 set_state_expr(my_id
, expr
, state
);
46 void set_bits_modified_expr_sym(const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
48 __set_param_modified_helper_sym(name
, sym
, state
);
49 set_state(my_id
, name
, sym
, state
);
51 struct smatch_state
*alloc_bstate(unsigned long long set
, unsigned long long possible
)
53 struct smatch_state
*state
;
56 state
= __alloc_smatch_state(0);
57 snprintf(buf
, sizeof(buf
), "0x%llx + 0x%llx", set
, possible
);
58 state
->name
= alloc_sname(buf
);
59 state
->data
= alloc_bit_info(set
, possible
);
64 struct bit_info
*rl_to_binfo(struct range_list
*rl
)
66 struct bit_info
*ret
= __alloc_bit_info(0);
69 if (rl_to_sval(rl
, &sval
)) {
70 ret
->set
= sval
.uvalue
;
71 ret
->possible
= sval
.uvalue
;
77 ret
->possible
= sval_fls_mask(rl_max(rl
));
78 // FIXME: what about negatives?
83 static int is_unknown_binfo(struct symbol
*type
, struct bit_info
*binfo
)
90 if (binfo
->possible
< (-1ULL >> (64 - type_bits(type
))))
96 static struct smatch_state
*unmatched_state(struct sm_state
*sm
)
98 struct smatch_state
*estate
;
100 unsigned long long possible
;
103 estate
= get_state(SMATCH_EXTRA
, sm
->name
, sm
->sym
);
104 if (estate_rl(estate
)) {
105 p
= rl_to_binfo(estate_rl(estate
));
106 return alloc_bstate(p
->set
, p
->possible
);
109 type
= estate_type(estate
);
111 return alloc_bstate(0, -1ULL);
113 if (type_bits(type
) == 64)
116 possible
= (1ULL << type_bits(type
)) - 1;
118 return alloc_bstate(0, possible
);
121 static bool is_loop_iterator(struct expression
*expr
)
123 struct statement
*pre_stmt
, *loop_stmt
;
125 pre_stmt
= expr_get_parent_stmt(expr
);
126 if (!pre_stmt
|| pre_stmt
->type
!= STMT_EXPRESSION
)
129 loop_stmt
= stmt_get_parent_stmt(pre_stmt
);
130 if (!loop_stmt
|| loop_stmt
->type
!= STMT_ITERATOR
)
132 if (loop_stmt
->iterator_pre_statement
!= pre_stmt
)
138 static bool handled_by_assign_hook(struct expression
*expr
)
140 if (!expr
|| expr
->type
!= EXPR_ASSIGNMENT
)
142 if (__in_fake_assign
)
144 if (is_loop_iterator(expr
))
147 if (expr
->op
== '=' ||
148 expr
->op
== SPECIAL_OR_ASSIGN
||
149 expr
->op
== SPECIAL_AND_ASSIGN
)
155 static void match_modify(struct sm_state
*sm
, struct expression
*mod_expr
)
157 // FIXME: we really need to store the type
159 if (handled_by_assign_hook(mod_expr
))
162 set_bits_modified_expr_sym(sm
->name
, sm
->sym
, alloc_bstate(0, -1ULL));
165 int binfo_equiv(struct bit_info
*one
, struct bit_info
*two
)
167 if (one
->set
== two
->set
&&
168 one
->possible
== two
->possible
)
173 struct smatch_state
*merge_bstates(struct smatch_state
*one_state
, struct smatch_state
*two_state
)
175 struct bit_info
*one
, *two
;
177 one
= one_state
->data
;
178 two
= two_state
->data
;
180 if (binfo_equiv(one
, two
))
183 return alloc_bstate(one
->set
& two
->set
, one
->possible
| two
->possible
);
187 * The combine_bit_info() takes two bit_infos and takes creates the most
188 * accurate picture we can assuming both are true. Or it returns unknown if
189 * the information is logically impossible.
191 * Which means that it takes the | of the ->set bits and the & of the possibly
192 * set bits, which is the opposite of what merge_bstates() does.
195 static struct bit_info
*combine_bit_info(struct bit_info
*one
, struct bit_info
*two
)
197 struct bit_info
*ret
= __alloc_bit_info(0);
199 if ((one
->set
& two
->possible
) != one
->set
)
200 return alloc_bit_info(0, -1ULL);
201 if ((two
->set
& one
->possible
) != two
->set
)
202 return alloc_bit_info(0, -1ULL);
204 ret
->set
= one
->set
| two
->set
;
205 ret
->possible
= one
->possible
& two
->possible
;
210 static struct bit_info
*binfo_AND(struct bit_info
*left
, struct bit_info
*right
)
212 unsigned long long set
= 0;
213 unsigned long long possible
= -1ULL;
215 if (!left
&& !right
) {
218 possible
= right
->possible
;
220 possible
= left
->possible
;
222 set
= left
->set
& right
->set
;
223 possible
= left
->possible
& right
->possible
;
226 return alloc_bit_info(set
, possible
);
229 static struct bit_info
*binfo_OR(struct bit_info
*left
, struct bit_info
*right
)
231 unsigned long long set
= 0;
232 unsigned long long possible
= -1ULL;
234 if (!left
&& !right
) {
241 set
= left
->set
| right
->set
;
242 possible
= left
->possible
| right
->possible
;
245 return alloc_bit_info(set
, possible
);
248 static unsigned long long get_type_possible(struct symbol
*type
)
251 type
= &ullong_ctype
;
253 if (type_bits(type
) == 64)
256 return (1ULL << type_bits(type
)) - 1;
259 struct bit_info
*get_bit_info(struct expression
*expr
)
261 struct range_list
*rl
;
262 struct smatch_state
*bstate
;
263 struct bit_info
*extra_info
;
264 struct bit_info
*bit_info
;
265 struct bit_info unknown_bit_info
= { };
268 expr
= strip_parens(expr
);
270 if (get_implied_value(expr
, &known
))
271 return alloc_bit_info(known
.value
, known
.value
);
273 if (expr
->type
== EXPR_BINOP
) {
275 return binfo_AND(get_bit_info(expr
->left
),
276 get_bit_info(expr
->right
));
278 return binfo_OR(get_bit_info(expr
->left
),
279 get_bit_info(expr
->right
));
282 unknown_bit_info
.possible
= get_type_possible(get_type(expr
));
284 if (get_implied_rl(expr
, &rl
))
285 extra_info
= rl_to_binfo(rl
);
287 extra_info
= &unknown_bit_info
;
289 bstate
= get_state_expr(my_id
, expr
);
291 bit_info
= bstate
->data
;
293 bit_info
= &unknown_bit_info
;
295 return combine_bit_info(extra_info
, bit_info
);
298 static int is_single_bit(sval_t sval
)
303 for (i
= 0; i
< 64; i
++) {
304 if (sval
.uvalue
& 1ULL << i
&&
313 static void match_compare(struct expression
*expr
)
317 if (expr
->type
!= EXPR_COMPARE
)
319 if (expr
->op
!= SPECIAL_EQUAL
&&
320 expr
->op
!= SPECIAL_NOTEQUAL
)
323 if (!get_implied_value(expr
->right
, &val
))
326 set_true_false_states_expr(my_id
, expr
->left
,
327 (expr
->op
== SPECIAL_EQUAL
) ? alloc_bstate(val
.uvalue
, val
.uvalue
) : NULL
,
328 (expr
->op
== SPECIAL_EQUAL
) ? NULL
: alloc_bstate(val
.uvalue
, val
.uvalue
));
331 static void match_assign(struct expression
*expr
)
333 struct bit_info
*start
, *binfo
;
334 struct smatch_state
*new;
336 if (!handled_by_assign_hook(expr
))
339 binfo
= get_bit_info(expr
->right
);
342 if (expr
->op
== '=') {
343 if (is_unknown_binfo(get_type(expr
->left
), binfo
))
345 set_bits_modified_expr(expr
->left
, alloc_bstate(binfo
->set
, binfo
->possible
));
346 } else if (expr
->op
== SPECIAL_OR_ASSIGN
) {
347 start
= get_bit_info(expr
->left
);
348 new = alloc_bstate(start
->set
| binfo
->set
, start
->possible
| binfo
->possible
);
349 set_bits_modified_expr(expr
->left
, new);
350 } else if (expr
->op
== SPECIAL_AND_ASSIGN
) {
351 start
= get_bit_info(expr
->left
);
352 new = alloc_bstate(start
->set
& binfo
->set
, start
->possible
& binfo
->possible
);
353 set_bits_modified_expr(expr
->left
, new);
357 static void match_condition(struct expression
*expr
)
359 struct bit_info
*orig
;
360 struct bit_info true_info
;
361 struct bit_info false_info
;
364 if (expr
->type
!= EXPR_BINOP
||
368 if (!get_value(expr
->right
, &right
))
371 orig
= get_bit_info(expr
->left
);
375 if (right
.uvalue
== 0 || is_single_bit(right
))
376 true_info
.set
&= right
.uvalue
;
378 true_info
.possible
&= right
.uvalue
;
379 false_info
.possible
&= ~right
.uvalue
;
381 set_true_false_states_expr(my_id
, expr
->left
,
382 alloc_bstate(true_info
.set
, true_info
.possible
),
383 alloc_bstate(false_info
.set
, false_info
.possible
));
386 static void match_call_info(struct expression
*expr
)
388 struct bit_info
*binfo
, *rl_binfo
;
389 struct expression
*arg
;
390 struct range_list
*rl
;
395 FOR_EACH_PTR(expr
->args
, arg
) {
397 binfo
= get_bit_info(arg
);
400 if (is_unknown_binfo(get_type(arg
), binfo
))
402 if (get_implied_rl(arg
, &rl
)) {
403 rl_binfo
= rl_to_binfo(rl
);
404 if (binfo_equiv(rl_binfo
, binfo
))
407 // If is just non-negative continue
408 // If ->set == ->possible continue
409 snprintf(buf
, sizeof(buf
), "0x%llx,0x%llx", binfo
->set
, binfo
->possible
);
410 sql_insert_caller_info(expr
, BIT_INFO
, i
, "$", buf
);
411 } END_FOR_EACH_PTR(arg
);
414 static void struct_member_callback(struct expression
*call
, int param
, char *printed_name
, struct sm_state
*sm
)
416 struct bit_info
*binfo
= sm
->state
->data
;
417 struct smatch_state
*estate
;
418 struct bit_info
*implied_binfo
;
424 /* This means it can only be one value, so it's handled by smatch_extra. */
425 if (binfo
->set
== binfo
->possible
)
428 estate
= get_state(SMATCH_EXTRA
, sm
->name
, sm
->sym
);
429 if (is_unknown_binfo(estate_type(estate
), binfo
))
432 if (estate_rl(estate
)) {
435 if (estate_get_single_value(estate
, &sval
))
438 implied_binfo
= rl_to_binfo(estate_rl(estate
));
439 if (binfo_equiv(implied_binfo
, binfo
))
443 snprintf(buf
, sizeof(buf
), "0x%llx,0x%llx", binfo
->set
, binfo
->possible
);
444 sql_insert_caller_info(call
, BIT_INFO
, param
, printed_name
, buf
);
447 static void set_param_bits(const char *name
, struct symbol
*sym
, char *key
, char *value
)
450 unsigned long long set
, possible
;
452 if (strcmp(key
, "*$") == 0)
453 snprintf(fullname
, sizeof(fullname
), "*%s", name
);
454 else if (strncmp(key
, "$", 1) == 0)
455 snprintf(fullname
, 256, "%s%s", name
, key
+ 1);
459 set
= strtoull(value
, &value
, 16);
463 possible
= strtoull(value
, &value
, 16);
465 set_bits_modified_expr_sym(fullname
, sym
, alloc_bstate(set
, possible
));
468 static void returns_bit_set(struct expression
*expr
, int param
, char *key
, char *value
)
472 unsigned long long set
;
475 name
= get_name_sym_from_key(expr
, param
, key
, &sym
);
480 set
= strtoull(value
, &pEnd
, 16);
481 set_state(my_id
, name
, sym
, alloc_bstate(set
, -1ULL));
484 static void returns_bit_clear(struct expression
*expr
, int param
, char *key
, char *value
)
488 unsigned long long possible
;
490 struct bit_info
*binfo
;
492 name
= get_name_sym_from_key(expr
, param
, key
, &sym
);
497 binfo
= get_bit_info(expr
);
498 possible
= strtoull(value
, &pEnd
, 16);
499 set_state(my_id
, name
, sym
, alloc_bstate(possible
& binfo
->set
,
500 possible
& binfo
->possible
));
503 void register_bits(int id
)
507 set_dynamic_states(my_id
);
509 add_unmatched_state_hook(my_id
, &unmatched_state
);
510 add_merge_hook(my_id
, &merge_bstates
);
512 add_hook(&match_condition
, CONDITION_HOOK
);
513 add_hook(&match_compare
, CONDITION_HOOK
);
514 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
515 add_modification_hook(my_id
, &match_modify
);
517 add_hook(&match_call_info
, FUNCTION_CALL_HOOK
);
518 add_member_info_callback(my_id
, struct_member_callback
);
519 select_caller_info_hook(set_param_bits
, BIT_INFO
);
521 select_return_states_hook(BIT_SET
, &returns_bit_set
);
522 select_return_states_hook(BIT_CLEAR
, &returns_bit_clear
);