1 /*
2 * Copyright (C) 2017 Oracle.
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 * Basically I see constraints as a way of saying "x <= some_limit". The
20 * problem is that smatch_capped is not granullar enough.
21 *
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.
25 *
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.
33 *
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.
40 *
41 */
42
43
44 #include "smatch.h"
45 #include "smatch_extra.h"
46 #include "smatch_slist.h"
47
48 static int my_id;
49
50 ALLOCATOR(constraint, "constraints");
51
52 static void add_constraint(struct constraint_list **list, int op, int constraint)
53 {
54 struct constraint *tmp, *new;
55
56 FOR_EACH_PTR(*list, tmp) {
57 if (tmp->id < constraint)
58 continue;
59 if (tmp->id == constraint) {
60 if (tmp->op == '<')
61 return;
62 if (op == SPECIAL_LTE)
63 return;
64
65 new = __alloc_constraint(0);
66 new->op = op;
67 new->id = constraint;
68 REPLACE_CURRENT_PTR(tmp, new);
69 return;
70 }
71
72 new = __alloc_constraint(0);
73 new->op = op;
74 new->id = constraint;
75 INSERT_CURRENT(new, tmp);
76 return;
77 } END_FOR_EACH_PTR(tmp);
78
79 new = __alloc_constraint(0);
80 new->op = op;
81 new->id = constraint;
82 add_ptr_list(list, new);
83 }
84
85 static struct constraint_list *merge_constraint_lists(struct constraint_list *one, struct constraint_list *two)
86 {
87 struct constraint_list *ret = NULL;
88 struct constraint *tmp;
89
90 // FIXME: not || but &&
91 FOR_EACH_PTR(one, tmp) {
92 add_constraint(&ret, tmp->op, tmp->id);
93 } END_FOR_EACH_PTR(tmp);
94
95 FOR_EACH_PTR(two, tmp) {
96 add_constraint(&ret, tmp->op, tmp->id);
97 } END_FOR_EACH_PTR(tmp);
98
99 return ret;
100 }
101
102 static struct constraint_list *clone_constraint_list(struct constraint_list *list)
103 {
104 struct constraint_list *ret = NULL;
105 struct constraint *tmp;
106
107 FOR_EACH_PTR(list, tmp) {
108 add_constraint(&ret, tmp->op, tmp->id);
109 } END_FOR_EACH_PTR(tmp);
110
111 return ret;
112 }
113
114 static struct smatch_state *alloc_constraint_state(struct constraint_list *list)
115 {
116 struct smatch_state *state;
117 struct constraint *con;
118 static char buf[256];
119 int cnt = 0;
120
121 FOR_EACH_PTR(list, con) {
122 if (cnt != 0)
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);
127
128 state = __alloc_smatch_state(0);
129 state->name = alloc_string(buf);
130 state->data = list;
131 return state;
132 }
133
134 static struct smatch_state *merge_func(struct smatch_state *s1, struct smatch_state *s2)
135 {
136 struct constraint_list *list;
137
138 // FIXME: use the dead code below instead
139 if (strcmp(s1->name, s2->name) == 0)
140 return s1;
141 return &merged;
142
143 list = merge_constraint_lists(s1->data, s2->data);
144 return alloc_constraint_state(list);
145 }
146
147 static int negate_gt(int op)
148 {
149 switch (op) {
150 case '>':
151 case SPECIAL_UNSIGNED_GT:
152 case SPECIAL_GTE:
153 case SPECIAL_UNSIGNED_GTE:
154 return negate_comparison(op);
155 }
156 return op;
157 }
158
159 static char *get_func_constraint(struct expression *expr)
160 {
161 char buf[256];
162 char *name;
163
164 if (is_fake_call(expr))
165 return NULL;
166 name = expr_to_str(expr->fn);
167 if (!name)
168 return NULL;
169 snprintf(buf, sizeof(buf), "%s()", name);
170 free_string(name);
171 return alloc_string(buf);
172 }
173
174 static char *get_toplevel_name(struct expression *expr)
175 {
176 struct symbol *sym;
177 char buf[256];
178
179 expr = strip_expr(expr);
180 if (expr->type != EXPR_SYMBOL || !expr->symbol || !expr->symbol->ident)
181 return NULL;
182
183 sym = expr->symbol;
184 if (!(sym->ctype.modifiers & MOD_TOPLEVEL))
185 return NULL;
186
187 if (sym->ctype.modifiers & MOD_STATIC)
188 snprintf(buf, sizeof(buf), "%s %s", get_base_file(), sym->ident->name);
189 else
190 snprintf(buf, sizeof(buf), "extern %s", sym->ident->name);
191
192 return alloc_string(buf);
193 }
194
195 char *get_constraint_str(struct expression *expr)
196 {
197 char *name;
198
199 if (!expr)
200 return NULL;
201 if (expr->type == EXPR_CALL)
202 return get_func_constraint(expr);
203 if (expr->type == EXPR_BINOP)
204 return expr_to_str(expr);
205 name = get_toplevel_name(expr);
206 if (name)
207 return name;
208 return get_member_name(expr);
209 }
210
211 static int save_int_callback(void *_p, int argc, char **argv, char **azColName)
212 {
213 int *p = _p;
214
215 *p = atoi(argv[0]);
216 return 0;
217 }
218
219 static int constraint_str_to_id(const char *str)
220 {
221 int id = -1;
222
223 run_sql(save_int_callback, &id,
224 "select id from constraints where str = '%q'", str);
225
226 return id;
227 }
228
229 static int save_constraint_str(void *_str, int argc, char **argv, char **azColName)
230 {
231 char **str = _str;
232
233 *str = alloc_string(argv[0]);
234 return 0;
235 }
236
237 static char *constraint_id_to_str(int id)
238 {
239 char *str = NULL;
240
241 run_sql(save_constraint_str, &str,
242 "select str from constraints where id = '%d'", id);
243
244 return str;
245 }
246
247 static int save_op_callback(void *_p, int argc, char **argv, char **azColName)
248 {
249 int *p = _p;
250
251 if (argv[0][0] == '<' && argv[0][1] == '=')
252 *p = SPECIAL_LTE;
253 else
254 *p = '<';
255 return 0;
256 }
257
258 static int save_str_callback(void *_p, int argc, char **argv, char **azColName)
259 {
260 char **p = _p;
261
262 if (!*p) {
263 *p = alloc_string(argv[0]);
264 } else {
265 char buf[256];
266
267 snprintf(buf, sizeof(buf), "%s, %s", *p, argv[0]);
268 *p = alloc_string(buf);
269 }
270 return 0;
271 }
272
273 char *get_required_constraint(const char *data_str)
274 {
275 char *required = NULL;
276
277 run_sql(save_str_callback, &required,
278 "select bound from constraints_required where data = '%q'", data_str);
279
280 return required;
281 }
282
283 static int get_required_op(char *data_str, char *con_str)
284 {
285 int op = 0;
286
287 run_sql(save_op_callback, &op,
288 "select op from constraints_required where data = '%q' and bound = '%q'", data_str, con_str);
289
290 return op;
291 }
292
293 char *unmet_constraint(struct expression *data, struct expression *offset)
294 {
295 struct smatch_state *state;
296 struct constraint_list *list;
297 struct constraint *con;
298 char *data_str;
299 char *required;
300 int req_op;
301
302 data_str = get_constraint_str(data);
303 if (!data_str)
304 return NULL;
305
306 required = get_required_constraint(data_str);
307 if (!required)
308 goto free_data;
309
310 state = get_state_expr(my_id, offset);
311 if (!state)
312 goto free_data;
313 list = state->data;
314
315 /* check the list of bounds on our index against the list that work */
316 FOR_EACH_PTR(list, con) {
317 char *con_str;
318
319 con_str = constraint_id_to_str(con->id);
320 if (!con_str) {
321 sm_msg("constraint %d not found", con->id);
322 continue;
323 }
324
325 req_op = get_required_op(data_str, con_str);
326 free_string(con_str);
327 if (!req_op)
328 continue;
329 if (con->op == '<' || con->op == req_op) {
330 free_string(required);
331 required = NULL;
332 goto free_data;
333 }
334 } END_FOR_EACH_PTR(con);
335
336 free_data:
337 free_string(data_str);
338 return required;
339 }
340
341 struct string_list *saved_constraints;
342 static void save_new_constraint(const char *con)
343 {
344 if (list_has_string(saved_constraints, con))
345 return;
346 insert_string(&saved_constraints, con);
347 sql_save_constraint(con);
348 }
349
350 static void handle_comparison(struct expression *left, int op, struct expression *right)
351 {
352 struct constraint_list *constraints;
353 struct smatch_state *state;
354 char *constraint;
355 int constraint_id;
356 int orig_op = op;
357 sval_t sval;
358
359 /* known values are handled in smatch extra */
360 if (get_value(left, &sval) || get_value(right, &sval))
361 return;
362
363 if (local_debug)
364 sm_msg("COMPARE: %s %s %s", expr_to_str(left), show_special(op), expr_to_str(right));
365
366 constraint = get_constraint_str(right);
367 if (!constraint)
368 return;
369 if (local_debug)
370 sm_msg("EXPR: %s CONSTRAINT %s", expr_to_str(right), constraint);
371 constraint_id = constraint_str_to_id(constraint);
372 if (local_debug)
373 sm_msg("CONSTRAINT ID %d", constraint_id);
374 if (constraint_id < 0)
375 save_new_constraint(constraint);
376 free_string(constraint);
377 if (constraint_id < 0)
378 return;
379
380 constraints = get_constraints(left);
381 constraints = clone_constraint_list(constraints);
382 op = negate_gt(orig_op);
383 add_constraint(&constraints, remove_unsigned_from_comparison(op), constraint_id);
384 state = alloc_constraint_state(constraints);
385
386 if (op == orig_op) {
387 if (local_debug)
388 sm_msg("SETTING %s true %s", expr_to_str(left), state->name);
389 set_true_false_states_expr(my_id, left, state, NULL);
390 } else {
391 if (local_debug)
392 sm_msg("SETTING %s false %s", expr_to_str(left), state->name);
393
394 set_true_false_states_expr(my_id, left, NULL, state);
395 }
396 }
397
398 static void match_condition(struct expression *expr)
399 {
400 if (expr->type != EXPR_COMPARE)
401 return;
402
403 if (expr->op == SPECIAL_EQUAL ||
404 expr->op == SPECIAL_NOTEQUAL)
405 return;
406
407 handle_comparison(expr->left, expr->op, expr->right);
408 handle_comparison(expr->right, flip_comparison(expr->op), expr->left);
409 }
410
411 struct constraint_list *get_constraints(struct expression *expr)
412 {
413 struct smatch_state *state;
414
415 state = get_state_expr(my_id, expr);
416 if (!state)
417 return NULL;
418 return state->data;
419 }
420
421 static void match_caller_info(struct expression *expr)
422 {
423 struct expression *tmp;
424 struct smatch_state *state;
425 int i;
426
427 i = -1;
428 FOR_EACH_PTR(expr->args, tmp) {
429 i++;
430 state = get_state_expr(my_id, tmp);
431 if (!state || state == &merged || state == &undefined)
432 continue;
433 sql_insert_caller_info(expr, CONSTRAINT, i, "$", state->name);
434 } END_FOR_EACH_PTR(tmp);
435 }
436
437 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
438 {
439 if (sm->state == &merged || sm->state == &undefined)
440 return;
441 sql_insert_caller_info(call, CONSTRAINT, param, printed_name, sm->state->name);
442 }
443
444 static struct smatch_state *constraint_str_to_state(char *value)
445 {
446 struct constraint_list *list = NULL;
447 char *p = value;
448 int op;
449 long long id;
450
451 while (true) {
452 op = '<';
453 if (*p != '<')
454 return &undefined;
455 p++;
456 if (*p == '=') {
457 op = SPECIAL_LTE;
458 p++;
459 }
460 id = strtoll(p, &p, 10);
461 add_constraint(&list, op, id);
462 if (*p != ',')
463 break;
464 p++;
465 if (*p != ' ')
466 return &undefined;
467 }
468
469 return alloc_constraint_state(list);
470 }
471
472 static void set_param_constrained(const char *name, struct symbol *sym, char *key, char *value)
473 {
474 char fullname[256];
475
476 if (strcmp(key, "*$") == 0)
477 snprintf(fullname, sizeof(fullname), "*%s", name);
478 else if (strncmp(key, "$", 1) == 0)
479 snprintf(fullname, 256, "%s%s", name, key + 1);
480 else
481 return;
482
483 set_state(my_id, name, sym, constraint_str_to_state(value));
484 }
485
486 static void print_return_implies_constrained(int return_id, char *return_ranges, struct expression *expr)
487 {
488 struct smatch_state *orig;
489 struct sm_state *sm;
490 const char *param_name;
491 int param;
492
493 FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
494 if (sm->state == &merged || sm->state == &undefined)
495 continue;
496
497 param = get_param_num_from_sym(sm->sym);
498 if (param < 0)
499 continue;
500
501 orig = get_state_stree(get_start_states(), my_id, sm->name, sm->sym);
502 if (orig && strcmp(sm->state->name, orig->name) == 0)
503 continue;
504
505 param_name = get_param_name(sm);
506 if (!param_name)
507 continue;
508
509 sql_insert_return_states(return_id, return_ranges, CONSTRAINT,
510 param, param_name, sm->state->name);
511 } END_FOR_EACH_SM(sm);
512 }
513
514 static void db_returns_constrained(struct expression *expr, int param, char *key, char *value)
515 {
516 char *name;
517 struct symbol *sym;
518
519 name = return_state_to_var_sym(expr, param, key, &sym);
520 if (!name || !sym)
521 goto free;
522
523 set_state(my_id, name, sym, constraint_str_to_state(value));
524 free:
525 free_string(name);
526 }
527
528 void register_constraints(int id)
529 {
530 my_id = id;
531
532 add_merge_hook(my_id, &merge_func);
533 add_hook(&match_condition, CONDITION_HOOK);
534
535 add_hook(&match_caller_info, FUNCTION_CALL_HOOK);
536 add_member_info_callback(my_id, struct_member_callback);
537 select_caller_info_hook(&set_param_constrained, CONSTRAINT);
538
539 add_split_return_callback(print_return_implies_constrained);
540 select_return_states_hook(CONSTRAINT, &db_returns_constrained);
541 }