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 <md5.h>
50 
51 static int my_id;
52 
str_to_mtag(const char * str)53 mtag_t str_to_mtag(const char *str)
54 {
55 	unsigned char c[MD5_DIGEST_LENGTH];
56 	unsigned long long *tag = (unsigned long long *)&c;
57 	int len;
58 
59 	len = strlen(str);
60 	md5_calc(c, str, len);
61 
62 	*tag &= ~MTAG_ALIAS_BIT;
63 	*tag &= ~MTAG_OFFSET_MASK;
64 
65 	return *tag;
66 }
67 
save_allocator(void * _allocator,int argc,char ** argv,char ** azColName)68 static int save_allocator(void *_allocator, int argc, char **argv, char **azColName)
69 {
70 	char **allocator = _allocator;
71 
72 	if (*allocator) {
73 		if (strcmp(*allocator, argv[0]) == 0)
74 			return 0;
75 		/* should be impossible */
76 		free_string(*allocator);
77 		*allocator = alloc_string("unknown");
78 		return 0;
79 	}
80 	*allocator = alloc_string(argv[0]);
81 	return 0;
82 }
83 
get_allocator_info_from_tag(mtag_t tag)84 char *get_allocator_info_from_tag(mtag_t tag)
85 {
86 	char *allocator = NULL;
87 
88 	run_sql(save_allocator, &allocator,
89 		"select value from mtag_info where tag = %lld and type = %d;",
90 		tag, ALLOCATOR);
91 
92 	return allocator;
93 }
94 
get_allocator_info(struct expression * expr,struct smatch_state * state)95 static char *get_allocator_info(struct expression *expr, struct smatch_state *state)
96 {
97 	sval_t sval;
98 
99 	if (expr->type != EXPR_ASSIGNMENT)
100 		return NULL;
101 	if (estate_get_single_value(state, &sval))
102 		return get_allocator_info_from_tag(sval.value);
103 
104 	expr = strip_expr(expr->right);
105 	if (expr->type != EXPR_CALL ||
106 	    !expr->fn ||
107 	    expr->fn->type != EXPR_SYMBOL)
108 		return NULL;
109 	return expr_to_str(expr->fn);
110 }
111 
update_mtag_info(struct expression * expr,mtag_t tag,const char * left_name,const char * tag_info,struct smatch_state * state)112 static void update_mtag_info(struct expression *expr, mtag_t tag,
113 			     const char *left_name, const char *tag_info,
114 			     struct smatch_state *state)
115 {
116 	char *allocator;
117 
118 	sql_insert_mtag_about(tag, left_name, tag_info);
119 
120 	allocator = get_allocator_info(expr, state);
121 	if (allocator)
122 		sql_insert_mtag_info(tag, ALLOCATOR, allocator);
123 }
124 
get_mtag_return(struct expression * expr,struct smatch_state * state)125 struct smatch_state *get_mtag_return(struct expression *expr, struct smatch_state *state)
126 {
127 	struct expression *left, *right;
128 	char *left_name, *right_name;
129 	struct symbol *left_sym;
130 	struct range_list *rl;
131 	char buf[256];
132 	mtag_t tag;
133 	sval_t tag_sval;
134 
135 	if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=')
136 		return NULL;
137 	if (!is_fresh_alloc(expr->right))
138 		return NULL;
139 	if (!rl_intersection(estate_rl(state), valid_ptr_rl))
140 		return NULL;
141 
142 	left = strip_expr(expr->left);
143 	right = strip_expr(expr->right);
144 
145 	left_name = expr_to_str_sym(left, &left_sym);
146 	if (!left_name || !left_sym)
147 		return NULL;
148 	right_name = expr_to_str(right);
149 
150 	snprintf(buf, sizeof(buf), "%s %s %s %s", get_filename(), get_function(),
151 		 left_name, right_name);
152 	tag = str_to_mtag(buf);
153 	tag_sval.type = estate_type(state);
154 	tag_sval.uvalue = tag;
155 
156 	rl = rl_filter(estate_rl(state), valid_ptr_rl);
157 	rl = clone_rl(rl);
158 	add_range(&rl, tag_sval, tag_sval);
159 
160 	update_mtag_info(expr, tag, left_name, buf, state);
161 
162 	free_string(left_name);
163 	free_string(right_name);
164 
165 	return alloc_estate_rl(rl);
166 }
167 
get_string_mtag(struct expression * expr,mtag_t * tag)168 int get_string_mtag(struct expression *expr, mtag_t *tag)
169 {
170 	mtag_t xor;
171 
172 	if (expr->type != EXPR_STRING || !expr->string)
173 		return 0;
174 
175 	/* I was worried about collisions so I added a xor */
176 	xor = str_to_mtag("__smatch string");
177 	*tag = str_to_mtag(expr->string->data);
178 	*tag = *tag ^ xor;
179 
180 	return 1;
181 }
182 
get_toplevel_mtag(struct symbol * sym,mtag_t * tag)183 int get_toplevel_mtag(struct symbol *sym, mtag_t *tag)
184 {
185 	char buf[256];
186 
187 	if (!sym)
188 		return 0;
189 
190 	if (!sym->ident ||
191 	    !(sym->ctype.modifiers & MOD_TOPLEVEL))
192 		return 0;
193 
194 	snprintf(buf, sizeof(buf), "%s %s",
195 		 (sym->ctype.modifiers & MOD_STATIC) ? get_filename() : "extern",
196 		 sym->ident->name);
197 	*tag = str_to_mtag(buf);
198 	return 1;
199 }
200 
get_symbol_mtag(struct symbol * sym,mtag_t * tag)201 bool get_symbol_mtag(struct symbol *sym, mtag_t *tag)
202 {
203 	char buf[256];
204 
205 	if (!sym || !sym->ident)
206 		return false;
207 
208 	if (get_toplevel_mtag(sym, tag))
209 		return true;
210 
211 	if (get_param_num_from_sym(sym) >= 0)
212 		return false;
213 
214 	snprintf(buf, sizeof(buf), "%s %s %s",
215 		 get_filename(), get_function(), sym->ident->name);
216 	*tag = str_to_mtag(buf);
217 	return true;
218 }
219 
global_variable(struct symbol * sym)220 static void global_variable(struct symbol *sym)
221 {
222 	mtag_t tag;
223 
224 	if (!get_toplevel_mtag(sym, &tag))
225 		return;
226 
227 	sql_insert_mtag_about(tag,
228 			      sym->ident->name,
229 			      (sym->ctype.modifiers & MOD_STATIC) ? get_filename() : "extern");
230 }
231 
get_array_mtag_offset(struct expression * expr,mtag_t * tag,int * offset)232 static int get_array_mtag_offset(struct expression *expr, mtag_t *tag, int *offset)
233 {
234 	struct expression *array, *offset_expr;
235 	struct symbol *type;
236 	sval_t sval;
237 	int start_offset;
238 
239 	if (!is_array(expr))
240 		return 0;
241 
242 	array = get_array_base(expr);
243 	if (!array)
244 		return 0;
245 	type = get_type(array);
246 	if (!type || type->type != SYM_ARRAY)
247 		return 0;
248 	type = get_real_base_type(type);
249 	if (!type_bytes(type))
250 		return 0;
251 
252 	if (!expr_to_mtag_offset(array, tag, &start_offset))
253 		return 0;
254 
255 	offset_expr = get_array_offset(expr);
256 	if (!get_value(offset_expr, &sval))
257 		return 0;
258 	*offset = start_offset + sval.value * type_bytes(type);
259 
260 	return 1;
261 }
262 
swap_mtag_seed(struct expression * expr,struct range_list * rl)263 struct range_list *swap_mtag_seed(struct expression *expr, struct range_list *rl)
264 {
265 	char buf[256];
266 	char *name;
267 	sval_t sval;
268 	mtag_t tag;
269 
270 	if (!rl_to_sval(rl, &sval))
271 		return rl;
272 	if (sval.type->type != SYM_PTR || sval.uvalue != MTAG_SEED)
273 		return rl;
274 
275 	name = expr_to_str(expr);
276 	snprintf(buf, sizeof(buf), "%s %s %s", get_filename(), get_function(), name);
277 	free_string(name);
278 	tag = str_to_mtag(buf);
279 	sval.value = tag;
280 	return alloc_rl(sval, sval);
281 }
282 
create_mtag_alias(mtag_t tag,struct expression * expr,mtag_t * new)283 int create_mtag_alias(mtag_t tag, struct expression *expr, mtag_t *new)
284 {
285 	char buf[256];
286 	int lines_from_start;
287 	char *str;
288 
289 	/*
290 	 * We need the alias to be unique.  It's not totally required that it
291 	 * be the same from one DB build to then next, but it makes debugging
292 	 * a bit simpler.
293 	 *
294 	 */
295 
296 	if (!cur_func_sym)
297 		return 0;
298 
299 	lines_from_start = expr->pos.line - cur_func_sym->pos.line;
300 	str = expr_to_str(expr);
301 	snprintf(buf, sizeof(buf), "%lld %d %s", tag, lines_from_start, str);
302 	free_string(str);
303 
304 	*new = str_to_mtag(buf);
305 	sql_insert_mtag_alias(tag, *new);
306 
307 	return 1;
308 }
309 
get_implied_mtag_offset(struct expression * expr,mtag_t * tag,int * offset)310 static int get_implied_mtag_offset(struct expression *expr, mtag_t *tag, int *offset)
311 {
312 	struct smatch_state *state;
313 	struct symbol *type;
314 	sval_t sval;
315 
316 	type = get_type(expr);
317 	if (!type_is_ptr(type))
318 		return 0;
319 	state = get_extra_state(expr);
320 	if (!state || !estate_get_single_value(state, &sval) || sval.value == 0)
321 		return 0;
322 
323 	*tag = sval.uvalue & ~MTAG_OFFSET_MASK;
324 	*offset = sval.uvalue & MTAG_OFFSET_MASK;
325 	return 1;
326 }
327 
328 /*
329  * The point of this function is to give you the mtag and the offset so
330  * you can look up the data in the DB.  It takes an expression.
331  *
332  * So say you give it "foo->bar".  Then it would give you the offset of "bar"
333  * and the implied value of "foo".  Or if you lookup "*foo" then the offset is
334  * zero and we look up the implied value of "foo.  But if the expression is
335  * foo, then if "foo" is a global variable, then we get the mtag and the offset
336  * is zero.  If "foo" is a local variable, then there is nothing to look up in
337  * the mtag_data table because that's handled by smatch_extra.c to this returns
338  * false.
339  *
340  */
expr_to_mtag_offset(struct expression * expr,mtag_t * tag,int * offset)341 int expr_to_mtag_offset(struct expression *expr, mtag_t *tag, int *offset)
342 {
343 	*tag = 0;
344 	*offset = 0;
345 
346 	if (bits_in_pointer != 64)
347 		return 0;
348 
349 	expr = strip_expr(expr);
350 	if (!expr)
351 		return 0;
352 
353 	if (is_array(expr))
354 		return get_array_mtag_offset(expr, tag, offset);
355 
356 	if (expr->type == EXPR_PREOP && expr->op == '*') {
357 		expr = strip_expr(expr->unop);
358 		return get_implied_mtag_offset(expr, tag, offset);
359 	} else if (expr->type == EXPR_DEREF) {
360 		int tmp, tmp_offset = 0;
361 
362 		while (expr->type == EXPR_DEREF) {
363 			tmp = get_member_offset_from_deref(expr);
364 			if (tmp < 0)
365 				return 0;
366 			tmp_offset += tmp;
367 			expr = strip_expr(expr->deref);
368 		}
369 		*offset = tmp_offset;
370 		if (expr->type == EXPR_PREOP && expr->op == '*') {
371 			expr = strip_expr(expr->unop);
372 
373 			if (get_implied_mtag_offset(expr, tag, &tmp_offset)) {
374 				// FIXME:  look it up recursively?
375 				if (tmp_offset)
376 					return 0;
377 				return 1;
378 			}
379 			return 0;
380 		} else if (expr->type == EXPR_SYMBOL) {
381 			return get_symbol_mtag(expr->symbol, tag);
382 		}
383 		return 0;
384 	} else if (expr->type == EXPR_SYMBOL) {
385 		return get_symbol_mtag(expr->symbol, tag);
386 	}
387 	return 0;
388 }
389 
390 /*
391  * This function takes an address and returns an sval.  Let's take some
392  * example things you might pass to it:
393  * foo->bar:
394  *   If we were only called from smatch_math, we wouldn't need to bother with
395  *   this because it's already been looked up in smatch_extra.c but this is
396  *   also called from other places so we have to check smatch_extra.c.
397  * &foo
398  *   If "foo" is global return the mtag for "foo".
399  * &foo.bar
400  *   If "foo" is global return the mtag for "foo" + the offset of ".bar".
401  * It also handles string literals.
402  *
403  */
get_mtag_sval(struct expression * expr,sval_t * sval)404 int get_mtag_sval(struct expression *expr, sval_t *sval)
405 {
406 	struct symbol *type;
407 	mtag_t tag;
408 	int offset = 0;
409 
410 	if (bits_in_pointer != 64)
411 		return 0;
412 
413 	expr = strip_expr(expr);
414 
415 	type = get_type(expr);
416 	if (!type_is_ptr(type))
417 		return 0;
418 	/*
419 	 * There are several options:
420 	 *
421 	 * If the expr is a string literal, that's an address/mtag.
422 	 * SYM_ARRAY and SYM_FN are mtags.  There are "&foo" type addresses.
423 	 * And there are saved pointers "p = &foo;"
424 	 *
425 	 */
426 
427 	if (expr->type == EXPR_STRING && get_string_mtag(expr, &tag))
428 		goto found;
429 
430 	if (expr->type == EXPR_SYMBOL &&
431 	    (type->type == SYM_ARRAY || type->type == SYM_FN) &&
432 	    get_toplevel_mtag(expr->symbol, &tag))
433 		goto found;
434 
435 	if (expr->type == EXPR_PREOP && expr->op == '&') {
436 		expr = strip_expr(expr->unop);
437 		if (expr_to_mtag_offset(expr, &tag, &offset))
438 			goto found;
439 		return 0;
440 	}
441 
442 	if (get_implied_mtag_offset(expr, &tag, &offset))
443 		goto found;
444 
445 	return 0;
446 found:
447 	if (offset >= MTAG_OFFSET_MASK)
448 		return 0;
449 
450 	sval->type = type;
451 	sval->uvalue = tag | offset;
452 
453 	return 1;
454 }
455 
register_mtag(int id)456 void register_mtag(int id)
457 {
458 	my_id = id;
459 
460 
461 	/*
462 	 * The mtag stuff only works on 64 systems because we store the
463 	 * information in the pointer itself.
464 	 * bit 63   : set for alias mtags
465 	 * bit 62-12: mtag hash
466 	 * bit 11-0 : offset
467 	 *
468 	 */
469 
470 	add_hook(&global_variable, BASE_HOOK);
471 }
472