1 /*
2  * Copyright (C) 2012 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 #include "smatch.h"
19 #include "smatch_slist.h"
20 #include "smatch_extra.h"
21 
22 static int my_id;
23 
24 struct {
25 	const char *func;
26 	int param;
27 } alloc_functions[] = {
28 	{"kmalloc", 0},
29 	{"kzalloc", 0},
30 	{"__kmalloc", 0},
31 	{"vmalloc", 0},
32 	{"__vmalloc", 0},
33 	{"__vmalloc_node", 0},
34 };
35 
36 static struct range_list_stack *rl_stack;
37 static struct string_list *op_list;
38 
push_op(char c)39 static void push_op(char c)
40 {
41 	char *p;
42 
43 	p = malloc(1);
44 	p[0] = c;
45 	add_ptr_list(&op_list, p);
46 }
47 
pop_op(void)48 static char pop_op(void)
49 {
50 	char *p;
51 	char c;
52 
53 	if (!op_list) {
54 		sm_perror("%s: no op_list", __func__);
55 		return '\0';
56 	}
57 
58 	p = last_ptr_list((struct ptr_list *)op_list);
59 
60 	delete_ptr_list_last((struct ptr_list **)&op_list);
61 	c = p[0];
62 	free(p);
63 
64 	return c;
65 }
66 
op_precedence(char c)67 static int op_precedence(char c)
68 {
69 	switch (c) {
70 	case '+':
71 	case '-':
72 		return 1;
73 	case '*':
74 	case '/':
75 		return 2;
76 	default:
77 		return 0;
78 	}
79 }
80 
top_op_precedence(void)81 static int top_op_precedence(void)
82 {
83 	char *p;
84 
85 	if (!op_list)
86 		return 0;
87 
88 	p = last_ptr_list((struct ptr_list *)op_list);
89 	return op_precedence(p[0]);
90 }
91 
rl_pop_until(char c)92 static void rl_pop_until(char c)
93 {
94 	char op;
95 	struct range_list *left, *right;
96 	struct range_list *res;
97 
98 	while (top_op_precedence() && op_precedence(c) <= top_op_precedence()) {
99 		op = pop_op();
100 		right = pop_rl(&rl_stack);
101 		left = pop_rl(&rl_stack);
102 		res = rl_binop(left, op, right);
103 		if (!res)
104 			res = alloc_whole_rl(&llong_ctype);
105 		push_rl(&rl_stack, res);
106 	}
107 }
108 
rl_discard_stacks(void)109 static void rl_discard_stacks(void)
110 {
111 	while (op_list)
112 		pop_op();
113 	while (rl_stack)
114 		pop_rl(&rl_stack);
115 }
116 
read_rl_from_var(struct expression * call,const char * p,const char ** end,struct range_list ** rl)117 static int read_rl_from_var(struct expression *call, const char *p, const char **end, struct range_list **rl)
118 {
119 	struct expression *arg;
120 	struct smatch_state *state;
121 	long param;
122 	char *name;
123 	struct symbol *sym;
124 	char buf[256];
125 	int star;
126 
127 	p++;
128 	param = strtol(p, (char **)&p, 10);
129 
130 	arg = get_argument_from_call_expr(call->args, param);
131 	if (!arg)
132 		return 0;
133 
134 	if (*p != '-' && *p != '.') {
135 		get_absolute_rl(arg, rl);
136 		*end = p;
137 		return 1;
138 	}
139 
140 	*end = strchr(p, ' ');
141 
142 	if (arg->type == EXPR_PREOP && arg->op == '&') {
143 		arg = strip_expr(arg->unop);
144 		star = 0;
145 		p++;
146 	} else {
147 		star = 1;
148 		p += 2;
149 	}
150 
151 	name = expr_to_var_sym(arg, &sym);
152 	if (!name)
153 		return 0;
154 	snprintf(buf, sizeof(buf), "%s%s", name, star ? "->" : ".");
155 	free_string(name);
156 
157 	if (*end - p + strlen(buf) >= sizeof(buf))
158 		return 0;
159 	strncat(buf, p, *end - p);
160 
161 	state = get_state(SMATCH_EXTRA, buf, sym);
162 	if (!state)
163 		return 0;
164 	*rl = estate_rl(state);
165 	return 1;
166 }
167 
read_var_num(struct expression * call,const char * p,const char ** end,struct range_list ** rl)168 static int read_var_num(struct expression *call, const char *p, const char **end, struct range_list **rl)
169 {
170 	sval_t sval;
171 
172 	while (*p == ' ')
173 		p++;
174 
175 	if (*p == '$')
176 		return read_rl_from_var(call, p, end, rl);
177 
178 	sval.type = &llong_ctype;
179 	sval.value = strtoll(p, (char **)end, 10);
180 	if (*end == p)
181 		return 0;
182 	*rl = alloc_rl(sval, sval);
183 	return 1;
184 }
185 
read_op(const char * p)186 static const char *read_op(const char *p)
187 {
188 	while (*p == ' ')
189 		p++;
190 
191 	switch (*p) {
192 	case '+':
193 	case '-':
194 	case '*':
195 	case '/':
196 		return p;
197 	default:
198 		return NULL;
199 	}
200 }
201 
parse_call_math_rl(struct expression * call,const char * math,struct range_list ** rl)202 int parse_call_math_rl(struct expression *call, const char *math, struct range_list **rl)
203 {
204 	struct range_list *tmp;
205 	const char *c;
206 
207 	/* try to implement shunting yard algorithm. */
208 
209 	c = math;
210 	while (1) {
211 		if (option_debug)
212 			sm_msg("parsing %s", c);
213 
214 		/* read a number and push it onto the number stack */
215 		if (!read_var_num(call, c, &c, &tmp))
216 			goto fail;
217 		push_rl(&rl_stack, tmp);
218 
219 		if (option_debug)
220 			sm_msg("val = %s remaining = %s", show_rl(tmp), c);
221 
222 		if (!*c)
223 			break;
224 		if (*c == ']' && *(c + 1) == '\0')
225 			break;
226 
227 		c = read_op(c);
228 		if (!c)
229 			goto fail;
230 
231 		if (option_debug)
232 			sm_msg("op = %c remaining = %s", *c, c);
233 
234 		rl_pop_until(*c);
235 		push_op(*c);
236 		c++;
237 	}
238 
239 	rl_pop_until(0);
240 	*rl = pop_rl(&rl_stack);
241 	return 1;
242 fail:
243 	rl_discard_stacks();
244 	return 0;
245 }
246 
parse_call_math(struct expression * call,char * math,sval_t * sval)247 int parse_call_math(struct expression *call, char *math, sval_t *sval)
248 {
249 	struct range_list *rl;
250 
251 	if (!parse_call_math_rl(call, math, &rl))
252 		return 0;
253 	if (!rl_to_sval(rl, sval))
254 		return 0;
255 	return 1;
256 }
257 
alloc_state_sname(char * sname)258 static struct smatch_state *alloc_state_sname(char *sname)
259 {
260 	struct smatch_state *state;
261 
262 	state = __alloc_smatch_state(0);
263 	state->name = sname;
264 	state->data = INT_PTR(1);
265 	return state;
266 }
267 
get_arg_number(struct expression * expr)268 static int get_arg_number(struct expression *expr)
269 {
270 	struct symbol *sym;
271 	struct symbol *arg;
272 	int i;
273 
274 	expr = strip_expr(expr);
275 	if (expr->type != EXPR_SYMBOL)
276 		return -1;
277 	sym = expr->symbol;
278 
279 	i = 0;
280 	FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
281 		if (arg == sym)
282 			return i;
283 		i++;
284 	} END_FOR_EACH_PTR(arg);
285 
286 	return -1;
287 }
288 
format_name_sym_helper(char * buf,int remaining,char * name,struct symbol * sym)289 static int format_name_sym_helper(char *buf, int remaining, char *name, struct symbol *sym)
290 {
291 	int ret = 0;
292 	int arg;
293 	char *param_name;
294 	int name_len;
295 
296 	if (!name || !sym || !sym->ident)
297 		goto free;
298 	arg = get_param_num_from_sym(sym);
299 	if (arg < 0)
300 		goto free;
301 	if (param_was_set_var_sym(name, sym))
302 		goto free;
303 
304 	param_name = sym->ident->name;
305 	name_len = strlen(param_name);
306 
307 	if (name[name_len] == '\0')
308 		ret = snprintf(buf, remaining, "$%d", arg);
309 	else if (name[name_len] == '-')
310 		ret = snprintf(buf, remaining, "$%d%s", arg, name + name_len);
311 	else
312 		goto free;
313 
314 	remaining -= ret;
315 	if (remaining <= 0)
316 		ret = 0;
317 
318 free:
319 	free_string(name);
320 
321 	return ret;
322 
323 }
324 
format_variable_helper(char * buf,int remaining,struct expression * expr)325 static int format_variable_helper(char *buf, int remaining, struct expression *expr)
326 {
327 	char *name;
328 	struct symbol *sym;
329 
330 	name = expr_to_var_sym(expr, &sym);
331 	if (param_was_set_var_sym(name, sym))
332 		return 0;
333 	return format_name_sym_helper(buf, remaining, name, sym);
334 }
335 
format_call_to_param_mapping(char * buf,int remaining,struct expression * expr)336 static int format_call_to_param_mapping(char *buf, int remaining, struct expression *expr)
337 {
338 	char *name;
339 	struct symbol *sym;
340 
341 	name = map_call_to_param_name_sym(expr, &sym);
342 	if (param_was_set_var_sym(name, sym))
343 		return 0;
344 	return format_name_sym_helper(buf, remaining, name, sym);
345 }
346 
is_mtag_sval(sval_t sval)347 static int is_mtag_sval(sval_t sval)
348 {
349 	if (!is_ptr_type(sval.type))
350 		return 0;
351 	if (sval_cmp(sval, valid_ptr_min_sval) >= 0 &&
352 	    sval_cmp(sval, valid_ptr_max_sval) <= 0)
353 		return 1;
354 	return 0;
355 }
356 
format_expr_helper(char * buf,int remaining,struct expression * expr)357 static int format_expr_helper(char *buf, int remaining, struct expression *expr)
358 {
359 	sval_t sval;
360 	int ret;
361 	char *cur;
362 
363 	if (!expr)
364 		return 0;
365 
366 	cur = buf;
367 
368 	if (expr->type == EXPR_BINOP) {
369 		ret = format_expr_helper(cur, remaining, expr->left);
370 		if (ret == 0)
371 			return 0;
372 		remaining -= ret;
373 		if (remaining <= 0)
374 			return 0;
375 		cur += ret;
376 
377 		ret = snprintf(cur, remaining, " %s ", show_special(expr->op));
378 		remaining -= ret;
379 		if (remaining <= 0)
380 			return 0;
381 		cur += ret;
382 
383 		ret = format_expr_helper(cur, remaining, expr->right);
384 		if (ret == 0)
385 			return 0;
386 		remaining -= ret;
387 		if (remaining <= 0)
388 			return 0;
389 		cur += ret;
390 		return cur - buf;
391 	}
392 
393 	if (!param_was_set(expr) && get_implied_value(expr, &sval) && !is_mtag_sval(sval)) {
394 		ret = snprintf(cur, remaining, "%s", sval_to_str(sval));
395 		remaining -= ret;
396 		if (remaining <= 0)
397 			return 0;
398 		return ret;
399 	}
400 
401 	if (expr->type == EXPR_CALL)
402 		return format_call_to_param_mapping(cur, remaining, expr);
403 
404 	return format_variable_helper(cur, remaining, expr);
405 }
406 
format_expr(struct expression * expr)407 static char *format_expr(struct expression *expr)
408 {
409 	char buf[256] = "";
410 	int ret;
411 
412 	ret = format_expr_helper(buf, sizeof(buf), expr);
413 	if (ret == 0)
414 		return NULL;
415 
416 	return alloc_sname(buf);
417 }
418 
get_value_in_terms_of_parameter_math(struct expression * expr)419 char *get_value_in_terms_of_parameter_math(struct expression *expr)
420 {
421 	struct expression *tmp;
422 	char buf[256] = "";
423 	sval_t dummy;
424 	int ret;
425 
426 	tmp = get_assigned_expr(expr);
427 	if (tmp)
428 		expr = tmp;
429 	if (param_was_set(expr))
430 		return NULL;
431 
432 	if (get_implied_value(expr, &dummy))
433 		return NULL;
434 
435 	ret = format_expr_helper(buf, sizeof(buf), expr);
436 	if (ret == 0)
437 		return NULL;
438 
439 	return alloc_sname(buf);
440 }
441 
get_value_in_terms_of_parameter_math_var_sym(const char * name,struct symbol * sym)442 char *get_value_in_terms_of_parameter_math_var_sym(const char *name, struct symbol *sym)
443 {
444 	struct expression *tmp, *expr;
445 	char buf[256] = "";
446 	int ret;
447 	int cnt = 0;
448 	sval_t sval;
449 
450 	expr = get_assigned_expr_name_sym(name, sym);
451 	if (!expr)
452 		return NULL;
453 	while ((tmp = get_assigned_expr(expr))) {
454 		expr = strip_expr(tmp);
455 		if (++cnt > 3)
456 			break;
457 	}
458 
459 	if (get_implied_value(expr, &sval))
460 		return NULL;
461 
462 	ret = format_expr_helper(buf, sizeof(buf), expr);
463 	if (ret == 0)
464 		return NULL;
465 
466 	return alloc_sname(buf);
467 
468 }
469 
match_alloc(const char * fn,struct expression * expr,void * _size_arg)470 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
471 {
472 	int size_arg = PTR_INT(_size_arg);
473 	struct expression *right;
474 	struct expression *size_expr;
475 	char *sname;
476 
477 	right = strip_expr(expr->right);
478 	size_expr = get_argument_from_call_expr(right->args, size_arg);
479 
480 	sname = format_expr(size_expr);
481 	if (!sname)
482 		return;
483 	set_state_expr(my_id, expr->left, alloc_state_sname(sname));
484 }
485 
swap_format(struct expression * call,char * format)486 static char *swap_format(struct expression *call, char *format)
487 {
488 	char buf[256];
489 	sval_t sval;
490 	long param;
491 	struct expression *arg;
492 	char *p;
493 	char *out;
494 	int ret;
495 
496 	if (format[0] == '$' && format[2] == '\0') {
497 		param = strtol(format + 1, NULL, 10);
498 		arg = get_argument_from_call_expr(call->args, param);
499 		if (!arg)
500 			return NULL;
501 		return format_expr(arg);
502 	}
503 
504 	buf[0] = '\0';
505 	p = format;
506 	out = buf;
507 	while (*p) {
508 		if (*p == '$') {
509 			p++;
510 			param = strtol(p, (char **)&p, 10);
511 			arg = get_argument_from_call_expr(call->args, param);
512 			if (!arg)
513 				return NULL;
514 			param = get_arg_number(arg);
515 			if (param >= 0) {
516 				ret = snprintf(out, buf + sizeof(buf) - out, "$%ld", param);
517 				out += ret;
518 				if (out >= buf + sizeof(buf))
519 					return NULL;
520 			} else if (get_implied_value(arg, &sval)) {
521 				ret = snprintf(out, buf + sizeof(buf) - out, "%s", sval_to_str(sval));
522 				out += ret;
523 				if (out >= buf + sizeof(buf))
524 					return NULL;
525 			} else {
526 				return NULL;
527 			}
528 		}
529 		*out = *p;
530 		p++;
531 		out++;
532 	}
533 	if (buf[0] == '\0')
534 		return NULL;
535 	*out = '\0';
536 	return alloc_sname(buf);
537 }
538 
539 static char *buf_size_recipe;
db_buf_size_callback(void * unused,int argc,char ** argv,char ** azColName)540 static int db_buf_size_callback(void *unused, int argc, char **argv, char **azColName)
541 {
542 	if (argc != 1)
543 		return 0;
544 
545 	if (!buf_size_recipe)
546 		buf_size_recipe = alloc_sname(argv[0]);
547 	else if (strcmp(buf_size_recipe, argv[0]) != 0)
548 		buf_size_recipe = alloc_sname("invalid");
549 	return 0;
550 }
551 
get_allocation_recipe_from_call(struct expression * expr)552 static char *get_allocation_recipe_from_call(struct expression *expr)
553 {
554 	struct symbol *sym;
555 	static char sql_filter[1024];
556 	int i;
557 
558 	if (is_fake_call(expr))
559 		return NULL;
560 	expr = strip_expr(expr);
561 	if (expr->fn->type != EXPR_SYMBOL)
562 		return NULL;
563 	sym = expr->fn->symbol;
564 	if (!sym)
565 		return NULL;
566 
567 	for (i = 0; i < ARRAY_SIZE(alloc_functions); i++) {
568 		if (strcmp(sym->ident->name, alloc_functions[i].func) == 0) {
569 			char buf[32];
570 
571 			snprintf(buf, sizeof(buf), "$%d", alloc_functions[i].param);
572 			buf_size_recipe = alloc_sname(buf);
573 			return swap_format(expr, buf_size_recipe);
574 		}
575 	}
576 
577 	if (sym->ctype.modifiers & MOD_STATIC) {
578 		snprintf(sql_filter, 1024, "file = '%s' and function = '%s';",
579 			 get_filename(), sym->ident->name);
580 	} else {
581 		snprintf(sql_filter, 1024, "function = '%s' and static = 0;",
582 				sym->ident->name);
583 	}
584 
585 	buf_size_recipe = NULL;
586 	run_sql(db_buf_size_callback, NULL,
587 		"select value from return_states where type=%d and %s",
588 		BUF_SIZE, sql_filter);
589 	if (!buf_size_recipe || strcmp(buf_size_recipe, "invalid") == 0)
590 		return NULL;
591 	/* Known sizes should be handled in smatch_buf_size.c */
592 	if (!strchr(buf_size_recipe, '$'))
593 		return NULL;
594 	return swap_format(expr, buf_size_recipe);
595 }
596 
match_call_assignment(struct expression * expr)597 static void match_call_assignment(struct expression *expr)
598 {
599 	char *sname;
600 
601 	sname = get_allocation_recipe_from_call(expr->right);
602 	if (!sname)
603 		return;
604 	set_state_expr(my_id, expr->left, alloc_state_sname(sname));
605 }
606 
get_allocation_math(struct expression * expr)607 const char *get_allocation_math(struct expression *expr)
608 {
609 	struct expression *tmp;
610 	struct smatch_state *state;
611 	int cnt = 0;
612 
613 	expr = strip_expr(expr);
614 	while ((tmp = get_assigned_expr(expr))) {
615 		if (cnt++ > 5)  /* assignments to self cause infinite loops */
616 			break;
617 		expr = strip_expr(tmp);
618 	}
619 	if (!expr)
620 		return NULL;
621 
622 	if (expr->type == EXPR_CALL)
623 		return get_allocation_recipe_from_call(expr);
624 
625 	state = get_state_expr(my_id, expr);
626 	if (!state || !state->data)
627 		return NULL;
628 
629 	return state->name;
630 }
631 
register_parse_call_math(int id)632 void register_parse_call_math(int id)
633 {
634 	int i;
635 
636 	my_id = id;
637 
638 	set_dynamic_states(my_id);
639 
640 	for (i = 0; i < ARRAY_SIZE(alloc_functions); i++)
641 		add_function_assign_hook(alloc_functions[i].func, &match_alloc,
642 				         INT_PTR(alloc_functions[i].param));
643 	add_hook(&match_call_assignment, CALL_ASSIGNMENT_HOOK);
644 }
645 
646