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