xref: /illumos-gate/usr/src/tools/smatch/src/smatch_constraints.c (revision efe51d0cc2398b9ac179568b63a44e4bf295b8e2)
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 
add_constraint(struct constraint_list ** list,int op,int constraint)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 
merge_constraint_lists(struct constraint_list * one,struct constraint_list * two)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 
clone_constraint_list(struct constraint_list * list)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 
alloc_constraint_state(struct constraint_list * list)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 
merge_func(struct smatch_state * s1,struct smatch_state * s2)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 
negate_gt(int op)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 
get_func_constraint(struct expression * expr)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 
get_toplevel_name(struct expression * expr)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 
get_constraint_str(struct expression * expr)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 
save_int_callback(void * _p,int argc,char ** argv,char ** azColName)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 
constraint_str_to_id(const char * str)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 
save_constraint_str(void * _str,int argc,char ** argv,char ** azColName)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 
constraint_id_to_str(int id)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 
save_op_callback(void * _p,int argc,char ** argv,char ** azColName)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 
save_str_callback(void * _p,int argc,char ** argv,char ** azColName)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 
get_required_constraint(const char * data_str)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 
get_required_op(char * data_str,char * con_str)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 
unmet_constraint(struct expression * data,struct expression * offset)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;
save_new_constraint(const char * con)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 
handle_comparison(struct expression * left,int op,struct expression * right)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 
match_condition(struct expression * expr)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 
get_constraints(struct expression * expr)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 
match_caller_info(struct expression * expr)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 
struct_member_callback(struct expression * call,int param,char * printed_name,struct sm_state * sm)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 
constraint_str_to_state(char * value)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 
set_param_constrained(const char * name,struct symbol * sym,char * key,char * value)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 
print_return_implies_constrained(int return_id,char * return_ranges,struct expression * expr)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 
db_returns_constrained(struct expression * expr,int param,char * key,char * value)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 
register_constraints(int id)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 }
530