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 #include "smatch.h"
19 #include "smatch_slist.h"
20 #include "smatch_extra.h"
21 
22 static int my_id;
23 static int param_id;
24 
get_param_from_container_of(struct expression * expr)25 int get_param_from_container_of(struct expression *expr)
26 {
27 	struct expression *param_expr;
28 	struct symbol *type;
29 	sval_t sval;
30 	int param;
31 
32 
33 	type = get_type(expr);
34 	if (!type || type->type != SYM_PTR)
35 		return -1;
36 
37 	expr = strip_expr(expr);
38 	if (expr->type != EXPR_BINOP || expr->op != '-')
39 		return -1;
40 
41 	if (!get_value(expr->right, &sval))
42 		return -1;
43 	if (sval.value < 0 || sval.value > 4096)
44 		return -1;
45 
46 	param_expr = get_assigned_expr(expr->left);
47 	if (!param_expr)
48 		return -1;
49 	param = get_param_num(param_expr);
50 	if (param < 0)
51 		return -1;
52 
53 	return param;
54 }
55 
get_offset_from_container_of(struct expression * expr)56 int get_offset_from_container_of(struct expression *expr)
57 {
58 	struct expression *param_expr;
59 	struct symbol *type;
60 	sval_t sval;
61 
62 	type = get_type(expr);
63 	if (!type || type->type != SYM_PTR)
64 		return -1;
65 
66 	expr = strip_expr(expr);
67 	if (expr->type != EXPR_BINOP || expr->op != '-')
68 		return -1;
69 
70 	if (!get_value(expr->right, &sval))
71 		return -1;
72 	if (sval.value < 0 || sval.value > 4096)
73 		return -1;
74 
75 	param_expr = get_assigned_expr(expr->left);
76 	if (!param_expr)
77 		return -1;
78 
79 	return sval.value;
80 }
81 
print_returns_container_of(int return_id,char * return_ranges,struct expression * expr)82 static void print_returns_container_of(int return_id, char *return_ranges, struct expression *expr)
83 {
84 	int offset;
85 	int param;
86 	char key[64];
87 	char value[64];
88 
89 	param = get_param_from_container_of(expr);
90 	if (param < 0)
91 		return;
92 	offset = get_offset_from_container_of(expr);
93 	if (offset < 0)
94 		return;
95 
96 	snprintf(key, sizeof(key), "%d", param);
97 	snprintf(value, sizeof(value), "-%d", offset);
98 
99 	/* no need to add it to return_implies because it's not really param_used */
100 	sql_insert_return_states(return_id, return_ranges, CONTAINER, -1,
101 			key, value);
102 }
103 
get_deref_count(struct expression * expr)104 static int get_deref_count(struct expression *expr)
105 {
106 	int cnt = 0;
107 
108 	while (expr && expr->type == EXPR_DEREF) {
109 		expr = expr->deref;
110 		if (expr->type == EXPR_PREOP && expr->op == '*')
111 			expr = expr->unop;
112 		cnt++;
113 		if (cnt > 100)
114 			return -1;
115 	}
116 	return cnt;
117 }
118 
get_partial_deref(struct expression * expr,int cnt)119 static struct expression *get_partial_deref(struct expression *expr, int cnt)
120 {
121 	while (--cnt >= 0) {
122 		if (!expr || expr->type != EXPR_DEREF)
123 			return expr;
124 		expr = expr->deref;
125 		if (expr->type == EXPR_PREOP && expr->op == '*')
126 			expr = expr->unop;
127 	}
128 	return expr;
129 }
130 
partial_deref_to_offset_str(struct expression * expr,int cnt,char op,char * buf,int size)131 static int partial_deref_to_offset_str(struct expression *expr, int cnt, char op, char *buf, int size)
132 {
133 	int n, offset;
134 
135 	if (cnt == 0)
136 		return snprintf(buf, size, "%c0", op);
137 
138 	n = 0;
139 	while (--cnt >= 0) {
140 		offset = get_member_offset_from_deref(expr);
141 		if (offset < 0)
142 			return -1;
143 		n += snprintf(buf + n, size - n, "%c%d", op, offset);
144 		if (expr->type != EXPR_DEREF)
145 			return -1;
146 		expr = expr->deref;
147 		if (expr->type == EXPR_PREOP && expr->op == '*')
148 			expr = expr->unop;
149 	}
150 
151 	return n;
152 }
153 
get_shared_str(struct expression * expr,struct expression * container)154 static char *get_shared_str(struct expression *expr, struct expression *container)
155 {
156 	struct expression *one, *two;
157 	int exp, cont, min, ret, n;
158 	static char buf[48];
159 
160 	exp = get_deref_count(expr);
161 	cont = get_deref_count(container);
162 	if (exp < 0 || cont < 0)
163 		return NULL;
164 
165 	min = (exp < cont) ? exp : cont;
166 	while (min >= 0) {
167 		one = get_partial_deref(expr, exp - min);
168 		two = get_partial_deref(container, cont - min);
169 		if (expr_equiv(one, two))
170 			goto found;
171 		min--;
172 	}
173 
174 	return NULL;
175 
176 found:
177 	ret = partial_deref_to_offset_str(expr, exp - min, '-', buf, sizeof(buf));
178 	if (ret < 0)
179 		return NULL;
180 	n = ret;
181 	ret = partial_deref_to_offset_str(container, cont - min, '+', buf + ret, sizeof(buf) - ret);
182 	if (ret < 0)
183 		return NULL;
184 	n += ret;
185 	if (n >= sizeof(buf))
186 		return NULL;
187 
188 	return buf;
189 }
190 
get_stored_container_name(struct expression * container,struct expression * expr)191 static char *get_stored_container_name(struct expression *container,
192 				       struct expression *expr)
193 {
194 	struct smatch_state *state;
195 	static char buf[64];
196 	char *p;
197 	int param;
198 
199 	if (!container || container->type != EXPR_SYMBOL)
200 		return NULL;
201 	if (!expr || expr->type != EXPR_SYMBOL)
202 		return NULL;
203 	state = get_state_expr(param_id, expr);
204 	if (!state)
205 		return NULL;
206 
207 	snprintf(buf, sizeof(buf), "%s", state->name);
208 	p = strchr(buf, '|');
209 	if (!p)
210 		return NULL;
211 	*p = '\0';
212 	param = atoi(p + 2);
213 	if (get_param_sym_from_num(param) == container->symbol)
214 		return buf;
215 	return NULL;
216 }
217 
get_container_name_helper(struct expression * container,struct expression * expr)218 static char *get_container_name_helper(struct expression *container, struct expression *expr)
219 {
220 	struct symbol *container_sym, *sym;
221 	static char buf[64];
222 	char *ret, *shared;
223 	bool star;
224 
225 	expr = strip_expr(expr);
226 	container = strip_expr(container);
227 	if (!expr || !container)
228 		return NULL;
229 
230 	ret = get_stored_container_name(container, expr);
231 	if (ret)
232 		return ret;
233 
234 	sym = expr_to_sym(expr);
235 	container_sym = expr_to_sym(container);
236 	if (!sym || !container_sym)
237 		return NULL;
238 	if (sym != container_sym)
239 		return NULL;
240 
241 	if (container->type == EXPR_DEREF)
242 		star = true;
243 	else
244 		star = false;
245 
246 	if (container->type == EXPR_PREOP && container->op == '&')
247 		container = strip_expr(container->unop);
248 	if (expr->type == EXPR_PREOP && expr->op == '&')
249 		expr = strip_expr(expr->unop);
250 
251 	shared = get_shared_str(expr, container);
252 	if (!shared)
253 		return NULL;
254 	if (star)
255 		snprintf(buf, sizeof(buf), "*(%s)", shared);
256 	else
257 		snprintf(buf, sizeof(buf), "%s", shared);
258 
259 	return buf;
260 }
261 
get_container_name(struct expression * container,struct expression * expr)262 char *get_container_name(struct expression *container, struct expression *expr)
263 {
264 	char *ret;
265 
266 	ret = get_container_name_helper(container, expr);
267 	if (ret)
268 		return ret;
269 
270 	ret = get_container_name_helper(get_assigned_expr(container), expr);
271 	if (ret)
272 		return ret;
273 
274 	ret = get_container_name_helper(container, get_assigned_expr(expr));
275 	if (ret)
276 		return ret;
277 
278 	ret = get_container_name_helper(get_assigned_expr(container),
279 					get_assigned_expr(expr));
280 	if (ret)
281 		return ret;
282 
283 	return NULL;
284 }
285 
is_fn_ptr(struct expression * expr)286 static bool is_fn_ptr(struct expression *expr)
287 {
288 	struct symbol *type;
289 
290 	if (!expr)
291 		return false;
292 	if (expr->type != EXPR_SYMBOL && expr->type != EXPR_DEREF)
293 		return false;
294 
295 	type = get_type(expr);
296 	if (!type || type->type != SYM_PTR)
297 		return false;
298 	type = get_real_base_type(type);
299 	if (!type || type->type != SYM_FN)
300 		return false;
301 	return true;
302 }
303 
match_call(struct expression * call)304 static void match_call(struct expression *call)
305 {
306 	struct expression *fn, *arg, *tmp;
307 	bool found = false;
308 	int fn_param, param;
309 	char buf[32];
310 	char *name;
311 
312 	/*
313 	 * We're trying to link the function with the parameter.  There are a
314 	 * couple ways this can be passed:
315 	 * foo->func(foo, ...);
316 	 * foo->func(foo->x, ...);
317 	 * foo->bar.func(&foo->bar, ...);
318 	 * foo->bar->baz->func(foo, ...);
319 	 *
320 	 * So the method is basically to subtract the offsets until we get to
321 	 * the common bit, then add the member offsets to get the parameter.
322 	 *
323 	 * If we're taking an address then the offset math is not stared,
324 	 * otherwise it is.  Starred means dereferenced.
325 	 */
326 	fn = strip_expr(call->fn);
327 
328 	param = -1;
329 	FOR_EACH_PTR(call->args, arg) {
330 		param++;
331 
332 		name = get_container_name(arg, fn);
333 		if (!name)
334 			continue;
335 
336 		found = true;
337 		sql_insert_caller_info(call, CONTAINER, param, name, "$(-1)");
338 	} END_FOR_EACH_PTR(arg);
339 
340 	if (found)
341 		return;
342 
343 	fn_param = -1;
344 	FOR_EACH_PTR(call->args, arg) {
345 		fn_param++;
346 		if (!is_fn_ptr(arg))
347 			continue;
348 		param = -1;
349 		FOR_EACH_PTR(call->args, tmp) {
350 			param++;
351 
352 			/* the function isn't it's own container */
353 			if (arg == tmp)
354 				continue;
355 
356 			name = get_container_name(tmp, arg);
357 			if (!name)
358 				continue;
359 
360 			snprintf(buf, sizeof(buf), "$%d", param);
361 			sql_insert_caller_info(call, CONTAINER, fn_param, name, buf);
362 			return;
363 		} END_FOR_EACH_PTR(tmp);
364 	} END_FOR_EACH_PTR(arg);
365 }
366 
db_passed_container(const char * name,struct symbol * sym,char * key,char * value)367 static void db_passed_container(const char *name, struct symbol *sym, char *key, char *value)
368 {
369 	char buf[64];
370 
371 	snprintf(buf, sizeof(buf), "%s|%s", key, value);
372 	set_state(param_id, name, sym, alloc_state_str(buf));
373 }
374 
375 struct db_info {
376 	struct symbol *arg;
377 	int prev_offset;
378 	struct range_list *rl;
379 	int star;
380 	struct stree *stree;
381 };
382 
get_member_from_offset(struct symbol * sym,int offset)383 static struct symbol *get_member_from_offset(struct symbol *sym, int offset)
384 {
385 	struct symbol *type, *tmp;
386 	int cur;
387 
388 	type = get_real_base_type(sym);
389 	if (!type || type->type != SYM_PTR)
390 		return NULL;
391 	type = get_real_base_type(type);
392 	if (!type || type->type != SYM_STRUCT)
393 		return NULL;
394 
395 	cur = 0;
396 	FOR_EACH_PTR(type->symbol_list, tmp) {
397 		cur = ALIGN(cur, tmp->ctype.alignment);
398 		if (offset == cur)
399 			return tmp;
400 		cur += type_bytes(tmp);
401 	} END_FOR_EACH_PTR(tmp);
402 	return NULL;
403 }
404 
get_member_type_from_offset(struct symbol * sym,int offset)405 static struct symbol *get_member_type_from_offset(struct symbol *sym, int offset)
406 {
407 	struct symbol *base_type;
408 	struct symbol *member;
409 
410 	base_type = get_real_base_type(sym);
411 	if (base_type && base_type->type == SYM_PTR)
412 		base_type = get_real_base_type(base_type);
413 	if (offset == 0 && base_type && base_type->type == SYM_BASETYPE)
414 		return base_type;
415 
416 	member = get_member_from_offset(sym, offset);
417 	if (!member)
418 		return NULL;
419 	return get_real_base_type(member);
420 }
421 
get_name_from_offset(struct symbol * arg,int offset)422 static const char *get_name_from_offset(struct symbol *arg, int offset)
423 {
424 	struct symbol *member, *type;
425 	const char *name;
426 	static char fullname[256];
427 
428 	name = arg->ident->name;
429 
430 	type = get_real_base_type(arg);
431 	if (!type || type->type != SYM_PTR)
432 		return name;
433 
434 	type = get_real_base_type(type);
435 	if (!type)
436 		return NULL;
437 	if (type->type != SYM_STRUCT) {
438 		snprintf(fullname, sizeof(fullname), "*%s", name);
439 		return fullname;
440 	}
441 
442 	member = get_member_from_offset(arg, offset);
443 	if (!member || !member->ident)
444 		return NULL;
445 
446 	snprintf(fullname, sizeof(fullname), "%s->%s", name, member->ident->name);
447 	return fullname;
448 }
449 
set_param_value(struct stree ** stree,struct symbol * arg,int offset,struct range_list * rl)450 static void set_param_value(struct stree **stree, struct symbol *arg, int offset, struct range_list *rl)
451 {
452 	const char *name;
453 
454 	name = get_name_from_offset(arg, offset);
455 	if (!name)
456 		return;
457 	set_state_stree(stree, SMATCH_EXTRA, name, arg, alloc_estate_rl(rl));
458 }
459 
save_vals(void * _db_info,int argc,char ** argv,char ** azColName)460 static int save_vals(void *_db_info, int argc, char **argv, char **azColName)
461 {
462 	struct db_info *db_info = _db_info;
463 	struct symbol *type;
464 	struct range_list *rl;
465 	int offset = 0;
466 	const char *value;
467 
468 	if (argc == 2) {
469 		offset = atoi(argv[0]);
470 		value = argv[1];
471 	} else {
472 		value = argv[0];
473 	}
474 
475 	if (db_info->prev_offset != -1 &&
476 	    db_info->prev_offset != offset) {
477 		set_param_value(&db_info->stree, db_info->arg, db_info->prev_offset, db_info->rl);
478 		db_info->rl = NULL;
479 	}
480 
481 	db_info->prev_offset = offset;
482 
483 	type = get_real_base_type(db_info->arg);
484 	if (db_info->star)
485 		goto found_type;
486 	if (type->type != SYM_PTR)
487 		return 0;
488 	type = get_real_base_type(type);
489 	if (type->type == SYM_BASETYPE)
490 		goto found_type;
491 	type = get_member_type_from_offset(db_info->arg, offset);
492 found_type:
493 	str_to_rl(type, (char *)value, &rl);
494 	if (db_info->rl)
495 		db_info->rl = rl_union(db_info->rl, rl);
496 	else
497 		db_info->rl = rl;
498 
499 	return 0;
500 }
501 
load_tag_info_sym(mtag_t tag,struct symbol * arg,int arg_offset,int star)502 static struct stree *load_tag_info_sym(mtag_t tag, struct symbol *arg, int arg_offset, int star)
503 {
504 	struct db_info db_info = {
505 		.arg = arg,
506 		.prev_offset = -1,
507 		.star = star,
508 	};
509 	struct symbol *type;
510 
511 	if (!tag || !arg->ident)
512 		return NULL;
513 
514 	type = get_real_base_type(arg);
515 	if (!type)
516 		return NULL;
517 	if (!star) {
518 		if (type->type != SYM_PTR)
519 			return NULL;
520 		type = get_real_base_type(type);
521 		if (!type)
522 			return NULL;
523 	}
524 
525 	if (star || type->type == SYM_BASETYPE) {
526 		run_sql(save_vals, &db_info,
527 			"select value from mtag_data where tag = %lld and offset = %d and type = %d;",
528 			tag, arg_offset, DATA_VALUE);
529 	} else {  /* presumably the parameter is a struct pointer */
530 		run_sql(save_vals, &db_info,
531 			"select offset, value from mtag_data where tag = %lld and type = %d order by offset;",
532 			tag, DATA_VALUE);
533 	}
534 
535 	if (db_info.prev_offset != -1)
536 		set_param_value(&db_info.stree, arg, db_info.prev_offset, db_info.rl);
537 
538 	// FIXME: handle an offset correctly
539 	if (!star && !arg_offset) {
540 		sval_t sval;
541 
542 		sval.type = get_real_base_type(arg);
543 		sval.uvalue = tag;
544 		set_state_stree(&db_info.stree, SMATCH_EXTRA, arg->ident->name, arg, alloc_estate_sval(sval));
545 	}
546 	return db_info.stree;
547 }
548 
load_container_data(struct symbol * arg,const char * info)549 static void load_container_data(struct symbol *arg, const char *info)
550 {
551 	mtag_t cur_tag, container_tag, arg_tag;
552 	int container_offset, arg_offset;
553 	struct sm_state *sm;
554 	struct stree *stree;
555 	char *p, *cont;
556 	char copy[64];
557 	bool star = 0;
558 
559 	snprintf(copy, sizeof(copy), "%s", info);
560 	p = strchr(copy, '|');
561 	if (!p)
562 		return;
563 	*p = '\0';
564 	cont = p + 1;
565 	p = copy;
566 	if (p[0] == '*') {
567 		star = 1;
568 		p += 2;
569 	}
570 
571 	if (strcmp(cont, "$(-1)") != 0)
572 		return;
573 
574 	if (!get_toplevel_mtag(cur_func_sym, &cur_tag))
575 		return;
576 
577 	while (true) {
578 		container_offset = strtoul(p, &p, 0);
579 		if (local_debug)
580 			sm_msg("%s: cur_tag = %llu container_offset = %d",
581 			       __func__, cur_tag, container_offset);
582 		if (!mtag_map_select_container(cur_tag, -container_offset, &container_tag))
583 			return;
584 		cur_tag = container_tag;
585 		if (local_debug)
586 			sm_msg("%s: container_tag = %llu p = '%s'",
587 			       __func__, container_tag, p);
588 		if (!p)
589 			return;
590 		if (p[0] != '-')
591 			break;
592 		p++;
593 	}
594 
595 	if (p[0] != '+')
596 		return;
597 
598 	p++;
599 	arg_offset = strtoul(p, &p, 0);
600 	if (p && *p && *p != ')')
601 		return;
602 
603 	if (!arg_offset || star) {
604 		arg_tag = container_tag;
605 	} else {
606 		if (!mtag_map_select_tag(container_tag, arg_offset, &arg_tag))
607 			return;
608 	}
609 
610 	stree = load_tag_info_sym(arg_tag, arg, arg_offset, star);
611 	FOR_EACH_SM(stree, sm) {
612 		set_state(sm->owner, sm->name, sm->sym, sm->state);
613 	} END_FOR_EACH_SM(sm);
614 	free_stree(&stree);
615 }
616 
handle_passed_container(struct symbol * sym)617 static void handle_passed_container(struct symbol *sym)
618 {
619 	struct symbol *arg;
620 	struct smatch_state *state;
621 
622 	FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
623 		state = get_state(param_id, arg->ident->name, arg);
624 		if (!state || state == &merged)
625 			continue;
626 		load_container_data(arg, state->name);
627 	} END_FOR_EACH_PTR(arg);
628 }
629 
register_container_of(int id)630 void register_container_of(int id)
631 {
632 	my_id = id;
633 
634 	add_split_return_callback(&print_returns_container_of);
635 	add_hook(&match_call, FUNCTION_CALL_HOOK);
636 }
637 
register_container_of2(int id)638 void register_container_of2(int id)
639 {
640 	param_id = id;
641 
642 	set_dynamic_states(param_id);
643 	select_caller_info_hook(db_passed_container, CONTAINER);
644 	add_merge_hook(param_id, &merge_str_state);
645 	add_hook(&handle_passed_container, AFTER_DEF_HOOK);
646 }
647 
648