1 /*
2  * Copyright (C) 2017 Oracle.  All rights reserved.
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  * One problem that I have is that it's really hard to track how pointers are
20  * passed around.  For example, it would be nice to know that the probe() and
21  * remove() functions get the same pci_dev pointer.  It would be good to know
22  * what pointers we're passing to the open() and close() functions.  But that
23  * information gets lost in a call tree full of function pointer calls.
24  *
25  * I think the first step is to start naming specific pointers.  So when a
26  * pointer is allocated, then it gets a tag.  So calls to kmalloc() generate a
27  * tag.  But we might not use that, because there might be a better name like
28  * framebuffer_alloc(). The framebuffer_alloc() is interesting because there is
29  * one per driver and it's passed around to all the file operations.
30  *
31  * Perhaps we could make a list of functions like framebuffer_alloc() which take
32  * a size and say that those are the interesting alloc functions.
33  *
34  * Another place where we would maybe name the pointer is when they are passed
35  * to the probe().  Because that's an important pointer, since there is one
36  * per driver (sort of).
37  *
38  * My vision is that you could take a pointer and trace it back to a global.  So
39  * I'm going to track that pointer_tag - 28 bytes takes you to another pointer
40  * tag.  You could follow that one back and so on.  Also when we pass a pointer
41  * to a function that would be recorded as sort of a link or path or something.
42  *
43  */
44 
45 #include "smatch.h"
46 #include "smatch_slist.h"
47 #include "smatch_extra.h"
48 
49 #include <openssl/md5.h>
50 
51 static int my_id;
52 
53 static struct smatch_state *alloc_tag_state(mtag_t tag)
54 {
55 	struct smatch_state *state;
56 	char buf[64];
57 
58 	state = __alloc_smatch_state(0);
59 	snprintf(buf, sizeof(buf), "%lld", tag);
60 	state->name = alloc_sname(buf);
61 	state->data = malloc(sizeof(mtag_t));
62 	*(mtag_t *)state->data = tag;
63 
64 	return state;
65 }
66 
67 static mtag_t str_to_tag(const char *str)
68 {
69 	unsigned char c[MD5_DIGEST_LENGTH];
70 	unsigned long long *tag = (unsigned long long *)&c;
71 	MD5_CTX mdContext;
72 	int len;
73 
74 	len = strlen(str);
75 	MD5_Init(&mdContext);
76 	MD5_Update(&mdContext, str, len);
77 	MD5_Final(c, &mdContext);
78 
79 	*tag &= ~MTAG_ALIAS_BIT;
80 	*tag &= ~MTAG_OFFSET_MASK;
81 
82 	return *tag;
83 }
84 
85 static void alloc_assign(const char *fn, struct expression *expr, void *unused)
86 {
87 	struct expression *left, *right;
88 	char *left_name, *right_name;
89 	struct symbol *left_sym;
90 	char buf[256];
91 	mtag_t tag;
92 
93 
94 	// FIXME:  This should only happen when the size is not a paramter of
95 	// the caller
96 	return;
97 
98 	if (expr->type != EXPR_ASSIGNMENT || expr->op != '=')
99 		return;
100 	left = strip_expr(expr->left);
101 	right = strip_expr(expr->right);
102 	if (right->type != EXPR_CALL || right->fn->type != EXPR_SYMBOL)
103 		return;
104 
105 	left_name = expr_to_str_sym(left, &left_sym);
106 	right_name = expr_to_str(right);
107 
108 	snprintf(buf, sizeof(buf), "%s %s %s %s", get_filename(), get_function(),
109 		 left_name, right_name);
110 	tag = str_to_tag(buf);
111 
112 	sql_insert_mtag_about(tag, left_name, right_name);
113 
114 	if (left_name && left_sym)
115 		set_state(my_id, left_name, left_sym, alloc_tag_state(tag));
116 
117 	free_string(left_name);
118 	free_string(right_name);
119 }
120 
121 int get_string_mtag(struct expression *expr, mtag_t *tag)
122 {
123 	mtag_t xor;
124 
125 	if (expr->type != EXPR_STRING || !expr->string)
126 		return 0;
127 
128 	/* I was worried about collisions so I added a xor */
129 	xor = str_to_tag("__smatch string");
130 	*tag = str_to_tag(expr->string->data);
131 	*tag = *tag ^ xor;
132 
133 	return 1;
134 }
135 
136 int get_toplevel_mtag(struct symbol *sym, mtag_t *tag)
137 {
138 	char buf[256];
139 
140 	if (!sym)
141 		return 0;
142 
143 	if (!sym->ident ||
144 	    !(sym->ctype.modifiers & MOD_TOPLEVEL))
145 		return 0;
146 
147 	snprintf(buf, sizeof(buf), "%s %s",
148 		 (sym->ctype.modifiers & MOD_STATIC) ? get_filename() : "extern",
149 		 sym->ident->name);
150 	*tag = str_to_tag(buf);
151 	return 1;
152 }
153 
154 int get_deref_mtag(struct expression *expr, mtag_t *tag)
155 {
156 	mtag_t container_tag, member_tag;
157 	int offset;
158 
159 	/*
160 	 * I'm not totally sure what I'm doing...
161 	 *
162 	 * This is supposed to get something like "global_var->ptr", but I don't
163 	 * feel like it's complete at all.
164 	 *
165 	 */
166 
167 	if (!get_mtag(expr->unop, &container_tag))
168 		return 0;
169 
170 	offset = get_member_offset_from_deref(expr);
171 	if (offset < 0)
172 		return 0;
173 
174 	if (!mtag_map_select_tag(container_tag, -offset, &member_tag))
175 		return 0;
176 
177 	*tag = member_tag;
178 	return 1;
179 }
180 
181 static void global_variable(struct symbol *sym)
182 {
183 	mtag_t tag;
184 
185 	if (!get_toplevel_mtag(sym, &tag))
186 		return;
187 
188 	sql_insert_mtag_about(tag,
189 			      sym->ident->name,
190 			      (sym->ctype.modifiers & MOD_STATIC) ? get_filename() : "extern");
191 }
192 
193 static void db_returns_buf_size(struct expression *expr, int param, char *unused, char *math)
194 {
195 	struct expression *call;
196 	struct range_list *rl;
197 
198 	if (expr->type != EXPR_ASSIGNMENT)
199 		return;
200 	call = strip_expr(expr->right);
201 
202 	if (!parse_call_math_rl(call, math, &rl))
203 		return;
204 //	rl = cast_rl(&int_ctype, rl);
205 //	set_state_expr(my_size_id, expr->left, alloc_estate_rl(rl));
206 }
207 
208 static void db_returns_memory_tag(struct expression *expr, int param, char *key, char *value)
209 {
210 	struct expression *call, *arg;
211 	mtag_t tag, alias;
212 	char *name;
213 	struct symbol *sym;
214 
215 	call = strip_expr(expr);
216 	while (call->type == EXPR_ASSIGNMENT)
217 		call = strip_expr(call->right);
218 	if (call->type != EXPR_CALL)
219 		return;
220 
221 	tag = strtoul(value, NULL, 10);
222 
223 	if (!create_mtag_alias(tag, call, &alias))
224 		return;
225 
226 	arg = get_argument_from_call_expr(call->args, param);
227 	if (!arg)
228 		return;
229 
230 	name = get_variable_from_key(arg, key, &sym);
231 	if (!name || !sym)
232 		goto free;
233 
234 	set_state(my_id, name, sym, alloc_tag_state(alias));
235 free:
236 	free_string(name);
237 }
238 
239 static void match_call_info(struct expression *expr)
240 {
241 	struct smatch_state *state;
242 	struct expression *arg;
243 	int i = -1;
244 
245 	FOR_EACH_PTR(expr->args, arg) {
246 		i++;
247 		state = get_state_expr(my_id, arg);
248 		if (!state || !state->data)
249 			continue;
250 		sql_insert_caller_info(expr, MEMORY_TAG, i, "$", state->name);
251 	} END_FOR_EACH_PTR(arg);
252 }
253 
254 static void save_caller_info(const char *name, struct symbol *sym, char *key, char *value)
255 {
256 	struct smatch_state *state;
257 	char fullname[256];
258 	mtag_t tag;
259 
260 	if (strncmp(key, "$", 1) != 0)
261 		return;
262 
263 	tag = atoll(value);
264 	snprintf(fullname, 256, "%s%s", name, key + 1);
265 	state = alloc_tag_state(tag);
266 	set_state(my_id, fullname, sym, state);
267 }
268 
269 static int get_array_mtag_offset(struct expression *expr, mtag_t *tag, int *offset)
270 {
271 	struct expression *array, *offset_expr;
272 	struct symbol *type;
273 	sval_t sval;
274 
275 	if (!is_array(expr))
276 		return 0;
277 
278 	array = get_array_base(expr);
279 	if (!array)
280 		return 0;
281 	type = get_type(array);
282 	if (!type || type->type != SYM_ARRAY)
283 		return 0;
284 	type = get_real_base_type(type);
285 	if (!type_bytes(type))
286 		return 0;
287 
288 	if (!get_mtag(array, tag))
289 		return 0;
290 
291 	offset_expr = get_array_offset(expr);
292 	if (!get_value(offset_expr, &sval))
293 		return 0;
294 	*offset = sval.value * type_bytes(type);
295 
296 	return 1;
297 }
298 
299 static int get_implied_mtag_offset(struct expression *expr, mtag_t *tag, int *offset)
300 {
301 	struct smatch_state *state;
302 	struct symbol *type;
303 	sval_t sval;
304 
305 	type = get_type(expr);
306 	if (!type_is_ptr(type))
307 		return 0;
308 	state = get_extra_state(expr);
309 	if (!state || !estate_get_single_value(state, &sval) || sval.value == 0)
310 		return 0;
311 
312 	*tag = sval.uvalue & ~MTAG_OFFSET_MASK;
313 	*offset = sval.uvalue & MTAG_OFFSET_MASK;
314 	return 1;
315 }
316 
317 static int get_mtag_cnt;
318 int get_mtag(struct expression *expr, mtag_t *tag)
319 {
320 	struct smatch_state *state;
321 	int ret = 0;
322 
323 	expr = strip_expr(expr);
324 	if (!expr)
325 		return 0;
326 
327 	if (get_mtag_cnt > 0)
328 		return 0;
329 
330 	get_mtag_cnt++;
331 
332 	switch (expr->type) {
333 	case EXPR_STRING:
334 		if (get_string_mtag(expr, tag)) {
335 			ret = 1;
336 			goto dec_cnt;
337 		}
338 		break;
339 	case EXPR_SYMBOL:
340 		if (get_toplevel_mtag(expr->symbol, tag)) {
341 			ret = 1;
342 			goto dec_cnt;
343 		}
344 		break;
345 	case EXPR_DEREF:
346 		if (get_deref_mtag(expr, tag)) {
347 			ret = 1;
348 			goto dec_cnt;
349 		}
350 		break;
351 	}
352 
353 	state = get_state_expr(my_id, expr);
354 	if (!state)
355 		goto dec_cnt;
356 	if (state->data) {
357 		*tag = *(mtag_t *)state->data;
358 		ret = 1;
359 		goto dec_cnt;
360 	}
361 
362 dec_cnt:
363 	get_mtag_cnt--;
364 	return ret;
365 }
366 
367 int get_mtag_offset(struct expression *expr, mtag_t *tag, int *offset)
368 {
369 	int val;
370 
371 	if (!expr)
372 		return 0;
373 	if (expr->type == EXPR_PREOP && expr->op == '*')
374 		return get_mtag_offset(expr->unop, tag, offset);
375 	if (get_implied_mtag_offset(expr, tag, offset))
376 		return 1;
377 	if (!get_mtag(expr, tag))
378 		return 0;
379 	expr = strip_expr(expr);
380 	if (expr->type == EXPR_SYMBOL) {
381 		*offset = 0;
382 		return 1;
383 	}
384 	val = get_member_offset_from_deref(expr);
385 	if (val < 0)
386 		return 0;
387 	*offset = val;
388 	return 1;
389 }
390 
391 int create_mtag_alias(mtag_t tag, struct expression *expr, mtag_t *new)
392 {
393 	char buf[256];
394 	int lines_from_start;
395 	char *str;
396 
397 	/*
398 	 * We need the alias to be unique.  It's not totally required that it
399 	 * be the same from one DB build to then next, but it makes debugging
400 	 * a bit simpler.
401 	 *
402 	 */
403 
404 	if (!cur_func_sym)
405 		return 0;
406 
407 	lines_from_start = expr->pos.line - cur_func_sym->pos.line;
408 	str = expr_to_str(expr);
409 	snprintf(buf, sizeof(buf), "%lld %d %s", tag, lines_from_start, str);
410 	free_string(str);
411 
412 	*new = str_to_tag(buf);
413 	sql_insert_mtag_alias(tag, *new);
414 
415 	return 1;
416 }
417 
418 int expr_to_mtag_offset(struct expression *expr, mtag_t *tag, int *offset)
419 {
420 	*offset = 0;
421 
422 	expr = strip_expr(expr);
423 	if (!expr)
424 		return 0;
425 
426 	if (is_array(expr))
427 		return get_array_mtag_offset(expr, tag, offset);
428 
429 	if (expr->type ==  EXPR_DEREF) {
430 		*offset = get_member_offset_from_deref(expr);
431 		if (*offset < 0)
432 			return 0;
433 		return get_mtag(expr->deref, tag);
434 	}
435 
436 	if (get_implied_mtag_offset(expr, tag, offset))
437 		return 1;
438 
439 	return get_mtag(expr, tag);
440 }
441 
442 int get_mtag_sval(struct expression *expr, sval_t *sval)
443 {
444 	struct symbol *type;
445 	mtag_t tag;
446 	int offset = 0;
447 
448 	if (bits_in_pointer != 64)
449 		return 0;
450 
451 	expr = strip_expr(expr);
452 
453 	type = get_type(expr);
454 	if (!type_is_ptr(type))
455 		return 0;
456 	/*
457 	 * There are only three options:
458 	 *
459 	 * 1) An array address:
460 	 *    p = array;
461 	 * 2) An address like so:
462 	 *    p = &my_struct->member;
463 	 * 3) A pointer:
464 	 *    p = pointer;
465 	 *
466 	 */
467 
468 	if (expr->type == EXPR_STRING && get_string_mtag(expr, &tag))
469 		goto found;
470 
471 	if (type->type == SYM_ARRAY && get_toplevel_mtag(expr->symbol, &tag))
472 		goto found;
473 
474 	if (get_implied_mtag_offset(expr, &tag, &offset))
475 		goto found;
476 
477 	if (expr->type != EXPR_PREOP || expr->op != '&')
478 		return 0;
479 	expr = strip_expr(expr->unop);
480 
481 	if (!expr_to_mtag_offset(expr, &tag, &offset))
482 		return 0;
483 	if (offset > MTAG_OFFSET_MASK)
484 		offset = MTAG_OFFSET_MASK;
485 
486 found:
487 	sval->type = type;
488 	sval->uvalue = tag | offset;
489 
490 	return 1;
491 }
492 
493 static struct expression *remove_dereference(struct expression *expr)
494 {
495 	expr = strip_expr(expr);
496 
497 	if (expr->type == EXPR_PREOP && expr->op == '*')
498 		return strip_expr(expr->unop);
499 	return preop_expression(expr, '&');
500 }
501 
502 int get_mtag_addr_sval(struct expression *expr, sval_t *sval)
503 {
504 	return get_mtag_sval(remove_dereference(expr), sval);
505 }
506 
507 static void print_stored_to_mtag(int return_id, char *return_ranges, struct expression *expr)
508 {
509 	struct sm_state *sm;
510 	char buf[256];
511 	const char *param_name;
512 	int param;
513 
514 	FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
515 		if (!sm->state->data)
516 			continue;
517 
518 		param = get_param_num_from_sym(sm->sym);
519 		if (param < 0)
520 			continue;
521 		param_name = get_param_name(sm);
522 		if (!param_name)
523 			continue;
524 		if (strcmp(param_name, "$") == 0)
525 			continue;
526 
527 		snprintf(buf, sizeof(buf), "%lld", *(mtag_t *)sm->state->data);
528 		sql_insert_return_states(return_id, return_ranges, MEMORY_TAG, param, param_name, buf);
529 	} END_FOR_EACH_SM(sm);
530 }
531 
532 void register_mtag(int id)
533 {
534 	my_id = id;
535 
536 
537 	/*
538 	 * The mtag stuff only works on 64 systems because we store the
539 	 * information in the pointer itself.
540 	 * bit 63   : set for alias mtags
541 	 * bit 62-12: mtag hash
542 	 * bit 11-0 : offset
543 	 *
544 	 */
545 	if (bits_in_pointer != 64)
546 		return;
547 
548 	add_hook(&global_variable, BASE_HOOK);
549 
550 	add_function_assign_hook("kmalloc", &alloc_assign, NULL);
551 	add_function_assign_hook("kzalloc", &alloc_assign, NULL);
552 
553 	select_return_states_hook(BUF_SIZE, &db_returns_buf_size);
554 
555 	add_hook(&match_call_info, FUNCTION_CALL_HOOK);
556 	select_caller_info_hook(save_caller_info, MEMORY_TAG);
557 	add_split_return_callback(&print_stored_to_mtag);
558 	select_return_states_hook(MEMORY_TAG, db_returns_memory_tag);
559 }
560