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 expr = strip_expr(expr);
200 if (!expr)
201 return NULL;
202 if (expr->type == EXPR_CALL)
203 return get_func_constraint(expr);
204 if (expr->type == EXPR_BINOP)
205 return expr_to_str(expr);
206 name = get_toplevel_name(expr);
207 if (name)
208 return name;
209 return get_member_name(expr);
210 }
211
212 static int save_int_callback(void *_p, int argc, char **argv, char **azColName)
213 {
214 int *p = _p;
215
216 *p = atoi(argv[0]);
217 return 0;
218 }
219
220 static int constraint_str_to_id(const char *str)
221 {
222 int id = -1;
223
224 run_sql(save_int_callback, &id,
225 "select id from constraints where str = '%q'", str);
226
227 return id;
228 }
229
230 static int save_constraint_str(void *_str, int argc, char **argv, char **azColName)
231 {
232 char **str = _str;
233
234 *str = alloc_string(argv[0]);
235 return 0;
236 }
237
238 static char *constraint_id_to_str(int id)
239 {
240 char *str = NULL;
241
242 run_sql(save_constraint_str, &str,
243 "select str from constraints where id = '%d'", id);
244
245 return str;
246 }
247
248 static int save_op_callback(void *_p, int argc, char **argv, char **azColName)
249 {
250 int *p = _p;
251
252 if (argv[0][0] == '<' && argv[0][1] == '=')
253 *p = SPECIAL_LTE;
254 else
255 *p = '<';
256 return 0;
257 }
258
259 static int save_str_callback(void *_p, int argc, char **argv, char **azColName)
260 {
261 char **p = _p;
262
263 if (!*p) {
264 *p = alloc_string(argv[0]);
265 } else {
266 char buf[256];
267
268 snprintf(buf, sizeof(buf), "%s, %s", *p, argv[0]);
269 *p = alloc_string(buf);
270 }
271 return 0;
272 }
273
274 char *get_required_constraint(const char *data_str)
275 {
276 char *required = NULL;
277
278 run_sql(save_str_callback, &required,
279 "select bound from constraints_required where data = '%q'", data_str);
280
281 return required;
282 }
283
284 static int get_required_op(char *data_str, char *con_str)
285 {
286 int op = 0;
287
288 run_sql(save_op_callback, &op,
289 "select op from constraints_required where data = '%q' and bound = '%q'", data_str, con_str);
290
291 return op;
292 }
293
294 char *unmet_constraint(struct expression *data, struct expression *offset)
295 {
296 struct smatch_state *state;
297 struct constraint_list *list;
298 struct constraint *con;
299 char *data_str;
300 char *required;
301 int req_op;
302
303 data_str = get_constraint_str(data);
304 if (!data_str)
305 return NULL;
306
307 required = get_required_constraint(data_str);
308 if (!required)
309 goto free_data;
310
311 state = get_state_expr(my_id, offset);
312 if (!state)
313 goto free_data;
314 list = state->data;
315
316 /* check the list of bounds on our index against the list that work */
317 FOR_EACH_PTR(list, con) {
318 char *con_str;
319
320 con_str = constraint_id_to_str(con->id);
321 if (!con_str) {
322 sm_msg("constraint %d not found", con->id);
323 continue;
324 }
325
326 req_op = get_required_op(data_str, con_str);
327 free_string(con_str);
328 if (!req_op)
329 continue;
330 if (con->op == '<' || con->op == req_op) {
331 free_string(required);
332 required = NULL;
333 goto free_data;
334 }
335 } END_FOR_EACH_PTR(con);
336
337 free_data:
338 free_string(data_str);
339 return required;
340 }
341
342 struct string_list *saved_constraints;
343 static void save_new_constraint(const char *con)
344 {
345 if (!insert_string(&saved_constraints, con))
346 return;
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 constraint = get_constraint_str(right);
364 if (!constraint)
365 return;
366 constraint_id = constraint_str_to_id(constraint);
367 if (constraint_id < 0)
368 save_new_constraint(constraint);
369 free_string(constraint);
370 if (constraint_id < 0)
371 return;
372
373 constraints = get_constraints(left);
374 constraints = clone_constraint_list(constraints);
375 op = negate_gt(orig_op);
376 add_constraint(&constraints, remove_unsigned_from_comparison(op), constraint_id);
377 state = alloc_constraint_state(constraints);
378
379 if (op == orig_op)
380 set_true_false_states_expr(my_id, left, state, NULL);
381 else
382 set_true_false_states_expr(my_id, left, NULL, state);
383 }
384
385 static void match_condition(struct expression *expr)
386 {
387 if (expr->type != EXPR_COMPARE)
388 return;
389
390 if (expr->op == SPECIAL_EQUAL ||
391 expr->op == SPECIAL_NOTEQUAL)
392 return;
393
394 handle_comparison(expr->left, expr->op, expr->right);
395 handle_comparison(expr->right, flip_comparison(expr->op), expr->left);
396 }
397
398 struct constraint_list *get_constraints(struct expression *expr)
399 {
400 struct smatch_state *state;
401
402 state = get_state_expr(my_id, expr);
403 if (!state)
404 return NULL;
405 return state->data;
406 }
407
408 static void match_caller_info(struct expression *expr)
409 {
410 struct expression *tmp;
411 struct smatch_state *state;
412 int i;
413
414 i = -1;
415 FOR_EACH_PTR(expr->args, tmp) {
416 i++;
417 state = get_state_expr(my_id, tmp);
418 if (!state || state == &merged || state == &undefined)
419 continue;
420 sql_insert_caller_info(expr, CONSTRAINT, i, "$", state->name);
421 } END_FOR_EACH_PTR(tmp);
422 }
423
424 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
425 {
426 if (sm->state == &merged || sm->state == &undefined)
427 return;
428 sql_insert_caller_info(call, CONSTRAINT, param, printed_name, sm->state->name);
429 }
430
431 static struct smatch_state *constraint_str_to_state(char *value)
432 {
433 struct constraint_list *list = NULL;
434 char *p = value;
435 int op;
436 long long id;
437
438 while (true) {
439 op = '<';
440 if (*p != '<')
441 return &undefined;
442 p++;
443 if (*p == '=') {
444 op = SPECIAL_LTE;
445 p++;
446 }
447 id = strtoll(p, &p, 10);
448 add_constraint(&list, op, id);
449 if (*p != ',')
450 break;
451 p++;
452 if (*p != ' ')
453 return &undefined;
454 }
455
456 return alloc_constraint_state(list);
457 }
458
459 static void set_param_constrained(const char *name, struct symbol *sym, char *key, char *value)
460 {
461 char fullname[256];
462
463 if (strcmp(key, "*$") == 0)
464 snprintf(fullname, sizeof(fullname), "*%s", name);
465 else if (strncmp(key, "$", 1) == 0)
466 snprintf(fullname, 256, "%s%s", name, key + 1);
467 else
468 return;
469
470 set_state(my_id, name, sym, constraint_str_to_state(value));
471 }
472
473 static void print_return_implies_constrained(int return_id, char *return_ranges, struct expression *expr)
474 {
475 struct smatch_state *orig;
476 struct sm_state *sm;
477 const char *param_name;
478 int param;
479
480 FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
481 if (sm->state == &merged || sm->state == &undefined)
482 continue;
483
484 param = get_param_num_from_sym(sm->sym);
485 if (param < 0)
486 continue;
487
488 orig = get_state_stree(get_start_states(), my_id, sm->name, sm->sym);
489 if (orig && strcmp(sm->state->name, orig->name) == 0)
490 continue;
491
492 param_name = get_param_name(sm);
493 if (!param_name)
494 continue;
495
496 sql_insert_return_states(return_id, return_ranges, CONSTRAINT,
497 param, param_name, sm->state->name);
498 } END_FOR_EACH_SM(sm);
499 }
500
501 static void db_returns_constrained(struct expression *expr, int param, char *key, char *value)
502 {
503 char *name;
504 struct symbol *sym;
505
506 name = return_state_to_var_sym(expr, param, key, &sym);
507 if (!name || !sym)
508 goto free;
509
510 set_state(my_id, name, sym, constraint_str_to_state(value));
511 free:
512 free_string(name);
513 }
514
515 void register_constraints(int id)
516 {
517 my_id = id;
518
519 set_dynamic_states(my_id);
520 add_merge_hook(my_id, &merge_func);
521 add_hook(&match_condition, CONDITION_HOOK);
522
523 add_hook(&match_caller_info, FUNCTION_CALL_HOOK);
524 add_member_info_callback(my_id, struct_member_callback);
525 select_caller_info_hook(&set_param_constrained, CONSTRAINT);
526
527 add_split_return_callback(print_return_implies_constrained);
528 select_return_states_hook(CONSTRAINT, &db_returns_constrained);
529 }