2 * Copyright (C) 2017 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 * Basically I see constraints as a way of saying "x <= some_limit". The
20 * problem is that smatch_capped is not granullar enough.
22 * This is mostly for finding out of bounds errors. So there are different
23 * types of constraints. Quite often we have "foo->xxx[i] = 42;" and we want
24 * to verify that "i" is less than foo->size.
26 * My idea was that we could automatically figure out these constraints. And we
27 * could load them in the DB so that they are the same every time. As in a
28 * constraint could be "< (struct whatever)->size" and give that in ID that
29 * would be constant until you completely wiped the DB. So when you do a normal
30 * DB rebuild then the first thing it will do is preserve all the constraints.
31 * I guess the reason to do it this way is to save space... I sometimes suspect
32 * that worrying about saving space is premature optimization.
34 * The other thing that I want to do a little bit different here is how I merge
35 * constraints. If a constraint is true on both sides, then that's normal. If
36 * we merge constraint 23 and 67 then we get constraint 23|67. If we merge 23
37 * with &undefined then we get &undefined. We can also have two constraints
38 * that are both true so we could have (45&23)|12 which means either both 45 and
39 * 23 are true or 12 is true.
45 #include "smatch_extra.h"
46 #include "smatch_slist.h"
50 ALLOCATOR(constraint
, "constraints");
52 static void add_constraint(struct constraint_list
**list
, int op
, int constraint
)
54 struct constraint
*tmp
, *new;
56 FOR_EACH_PTR(*list
, tmp
) {
57 if (tmp
->id
< constraint
)
59 if (tmp
->id
== constraint
) {
60 if (tmp
->op
== SPECIAL_LTE
)
65 new = __alloc_constraint(0);
68 REPLACE_CURRENT_PTR(tmp
, new);
72 new = __alloc_constraint(0);
75 INSERT_CURRENT(new, tmp
);
77 } END_FOR_EACH_PTR(tmp
);
79 new = __alloc_constraint(0);
82 add_ptr_list(list
, new);
85 static struct constraint_list
*merge_constraint_lists(struct constraint_list
*one
, struct constraint_list
*two
)
87 struct constraint_list
*ret
= NULL
;
88 struct constraint
*tmp
;
90 // FIXME: not || but &&
91 FOR_EACH_PTR(one
, tmp
) {
92 add_constraint(&ret
, tmp
->op
, tmp
->id
);
93 } END_FOR_EACH_PTR(tmp
);
95 FOR_EACH_PTR(two
, tmp
) {
96 add_constraint(&ret
, tmp
->op
, tmp
->id
);
97 } END_FOR_EACH_PTR(tmp
);
102 static struct constraint_list
*clone_constraint_list(struct constraint_list
*list
)
104 struct constraint_list
*ret
= NULL
;
105 struct constraint
*tmp
;
107 FOR_EACH_PTR(list
, tmp
) {
108 add_constraint(&ret
, tmp
->op
, tmp
->id
);
109 } END_FOR_EACH_PTR(tmp
);
114 static struct smatch_state
*alloc_constraint_state(struct constraint_list
*list
)
116 struct smatch_state
*state
;
117 struct constraint
*con
;
118 static char buf
[256];
121 FOR_EACH_PTR(list
, con
) {
123 cnt
+= snprintf(buf
+ cnt
, sizeof(buf
) - cnt
, ", ");
124 cnt
+= snprintf(buf
+ cnt
, sizeof(buf
) - cnt
, "%s%d",
125 show_special(con
->op
), con
->id
);
126 } END_FOR_EACH_PTR(con
);
128 state
= __alloc_smatch_state(0);
129 state
->name
= alloc_string(buf
);
134 static struct smatch_state
*merge_func(struct smatch_state
*s1
, struct smatch_state
*s2
)
136 struct constraint_list
*list
;
138 // FIXME: use the dead code below instead
139 if (strcmp(s1
->name
, s2
->name
) == 0)
143 list
= merge_constraint_lists(s1
->data
, s2
->data
);
144 return alloc_constraint_state(list
);
147 static int negate_gt(int op
)
151 case SPECIAL_UNSIGNED_GT
:
153 case SPECIAL_UNSIGNED_GTE
:
154 return negate_comparison(op
);
159 static char *get_toplevel_name(struct expression
*expr
)
164 expr
= strip_expr(expr
);
165 if (expr
->type
!= EXPR_SYMBOL
|| !expr
->symbol
|| !expr
->symbol
->ident
)
169 if (!(sym
->ctype
.modifiers
& MOD_TOPLEVEL
))
172 if (sym
->ctype
.modifiers
& MOD_STATIC
)
173 snprintf(buf
, sizeof(buf
), "%s %s", get_base_file(), sym
->ident
->name
);
175 snprintf(buf
, sizeof(buf
), "extern %s", sym
->ident
->name
);
177 return alloc_string(buf
);
180 char *get_constraint_str(struct expression
*expr
)
184 name
= get_toplevel_name(expr
);
187 return get_member_name(expr
);
190 static int save_int_callback(void *_p
, int argc
, char **argv
, char **azColName
)
198 static int constraint_str_to_id(const char *str
)
202 run_sql(save_int_callback
, &id
,
203 "select id from constraints where str = '%s'", str
);
208 static int save_constraint_str(void *_str
, int argc
, char **argv
, char **azColName
)
212 *str
= alloc_string(argv
[0]);
216 static char *constraint_id_to_str(int id
)
220 run_sql(save_constraint_str
, &str
,
221 "select str from constraints where id = '%d'", id
);
226 static int save_op_callback(void *_p
, int argc
, char **argv
, char **azColName
)
230 if (argv
[0][0] == '<' && argv
[0][1] == '=')
237 static int save_str_callback(void *_p
, int argc
, char **argv
, char **azColName
)
242 *p
= alloc_string(argv
[0]);
246 snprintf(buf
, sizeof(buf
), "%s, %s", *p
, argv
[0]);
247 *p
= alloc_string(buf
);
252 char *get_required_constraint(const char *data_str
)
254 char *required
= NULL
;
256 run_sql(save_str_callback
, &required
,
257 "select bound from constraints_required where data = '%s'", data_str
);
262 static int get_required_op(char *data_str
, char *con_str
)
266 run_sql(save_op_callback
, &op
,
267 "select op from constraints_required where data = '%s' and bound = '%s'", data_str
, con_str
);
272 char *unmet_constraint(struct expression
*data
, struct expression
*offset
)
274 struct smatch_state
*state
;
275 struct constraint_list
*list
;
276 struct constraint
*con
;
282 state
= get_state_expr(my_id
, offset
);
287 data_str
= get_constraint_str(data
);
291 required
= get_required_constraint(data_str
);
295 /* check the list of bounds on our index against the list that work */
296 FOR_EACH_PTR(list
, con
) {
299 con_str
= constraint_id_to_str(con
->id
);
301 sm_msg("constraint %d not found", con
->id
);
305 req_op
= get_required_op(data_str
, con_str
);
306 free_string(con_str
);
309 if (con
->op
== '<' || con
->op
== req_op
) {
313 } END_FOR_EACH_PTR(con
);
317 free_string(required
);
320 free_string(data_str
);
324 struct string_list
*saved_constraints
;
325 static void save_new_constraint(const char *con
)
327 if (list_has_string(saved_constraints
, con
))
329 insert_string(&saved_constraints
, con
);
330 sql_save_constraint(con
);
333 static void match_condition(struct expression
*expr
)
335 struct expression
*left
, *right
;
336 struct constraint_list
*constraints
;
337 struct smatch_state
*state
;
342 if (expr
->type
!= EXPR_COMPARE
)
345 if (expr
->op
== SPECIAL_EQUAL
||
346 expr
->op
== SPECIAL_NOTEQUAL
)
352 constraint
= get_constraint_str(right
);
355 constraint_id
= constraint_str_to_id(constraint
);
356 if (constraint_id
< 0)
357 save_new_constraint(constraint
);
358 free_string(constraint
);
359 if (constraint_id
< 0)
362 constraints
= get_constraints(left
);
363 constraints
= clone_constraint_list(constraints
);
364 op
= negate_gt(expr
->op
);
365 add_constraint(&constraints
, op
, constraint_id
);
366 state
= alloc_constraint_state(constraints
);
369 set_true_false_states_expr(my_id
, left
, state
, NULL
);
371 set_true_false_states_expr(my_id
, left
, NULL
, state
);
374 struct constraint_list
*get_constraints(struct expression
*expr
)
376 struct smatch_state
*state
;
378 state
= get_state_expr(my_id
, expr
);
384 static void match_caller_info(struct expression
*expr
)
386 struct expression
*tmp
;
387 struct smatch_state
*state
;
391 FOR_EACH_PTR(expr
->args
, tmp
) {
393 state
= get_state_expr(my_id
, tmp
);
394 if (!state
|| state
== &merged
|| state
== &undefined
)
396 sql_insert_caller_info(expr
, CONSTRAINT
, i
, "$", state
->name
);
397 } END_FOR_EACH_PTR(tmp
);
400 static void struct_member_callback(struct expression
*call
, int param
, char *printed_name
, struct sm_state
*sm
)
402 if (sm
->state
== &merged
|| sm
->state
== &undefined
)
404 sql_insert_caller_info(call
, CONSTRAINT
, param
, printed_name
, sm
->state
->name
);
407 static void print_return_implies_constrained(int return_id
, char *return_ranges
, struct expression
*expr
)
409 struct smatch_state
*orig
;
411 const char *param_name
;
414 FOR_EACH_MY_SM(my_id
, __get_cur_stree(), sm
) {
415 if (sm
->state
== &merged
|| sm
->state
== &undefined
)
418 param
= get_param_num_from_sym(sm
->sym
);
422 orig
= get_state_stree(get_start_states(), my_id
, sm
->name
, sm
->sym
);
423 if (orig
&& strcmp(sm
->state
->name
, orig
->name
) == 0)
426 param_name
= get_param_name(sm
);
430 sql_insert_return_states(return_id
, return_ranges
, CONSTRAINT
,
431 param
, param_name
, sm
->state
->name
);
432 } END_FOR_EACH_SM(sm
);
435 static struct smatch_state
*constraint_str_to_state(char *value
)
437 struct constraint_list
*list
= NULL
;
451 id
= strtoll(p
, &p
, 10);
452 add_constraint(&list
, op
, id
);
460 return alloc_constraint_state(list
);
463 static void db_returns_constrained(struct expression
*expr
, int param
, char *key
, char *value
)
468 name
= return_state_to_var_sym(expr
, param
, key
, &sym
);
472 set_state(my_id
, name
, sym
, constraint_str_to_state(value
));
477 void register_constraints(int id
)
481 add_merge_hook(my_id
, &merge_func
);
482 add_hook(&match_condition
, CONDITION_HOOK
);
484 add_hook(&match_caller_info
, FUNCTION_CALL_HOOK
);
485 add_member_info_callback(my_id
, struct_member_callback
);
487 add_split_return_callback(print_return_implies_constrained
);
488 select_return_states_hook(CONSTRAINT
, &db_returns_constrained
);