2 * Copyright (C) 2017 Oracle. All rights reserved.
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.
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.
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
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.
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.
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.
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).
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.
46 #include "smatch_slist.h"
47 #include "smatch_extra.h"
48 #include "cwchash/hashtable.h"
50 static DEFINE_HASHTABLE_INSERT(insert_sym
, mtag_t
, struct symbol
);
51 static DEFINE_HASHTABLE_SEARCH(search_sym
, mtag_t
, struct symbol
);
52 static struct hashtable
*tag_sym_map
;
56 static inline unsigned int rehash(void *_tag
)
59 return (unsigned int)*tag
;
62 static inline int equalkeys(void *_tag1
, void *_tag2
)
67 return *tag1
== *tag2
;
70 static void insert_tag_map(mtag_t tag
, struct symbol
*sym
)
74 p
= malloc(sizeof(tag
));
76 insert_sym(tag_sym_map
, p
, sym
);
79 static void store_hash(const char *str
, unsigned long long hash
)
81 sql_insert_cache_or_ignore(hash_string
, "0x%llx, '%s'", hash
, str
);
84 unsigned long long str_to_llu_hash(const char *str
)
86 unsigned long long hash
;
88 hash
= str_to_llu_hash_helper(str
);
89 store_hash(str
, hash
);
94 mtag_t
str_to_mtag(const char *str
)
96 unsigned long long tag
;
98 tag
= str_to_llu_hash_helper(str
);
100 tag
&= ~MTAG_OFFSET_MASK
;
101 tag
&= ulong_ULONG_MAX
.uvalue
;
106 static int save_allocator(void *_allocator
, int argc
, char **argv
, char **azColName
)
108 char **allocator
= _allocator
;
111 if (strcmp(*allocator
, argv
[0]) == 0)
113 /* should be impossible */
114 free_string(*allocator
);
115 *allocator
= alloc_string("unknown");
118 *allocator
= alloc_string(argv
[0]);
122 char *get_allocator_info_from_tag(mtag_t tag
)
124 char *allocator
= NULL
;
126 run_sql(save_allocator
, &allocator
,
127 "select value from mtag_info where tag = %lld and type = %d;",
133 static char *get_allocator_info(struct expression
*expr
, struct smatch_state
*state
)
137 if (expr
->type
!= EXPR_ASSIGNMENT
)
139 if (estate_get_single_value(state
, &sval
))
140 return get_allocator_info_from_tag(sval
.value
);
142 expr
= strip_expr(expr
->right
);
143 if (expr
->type
!= EXPR_CALL
||
145 expr
->fn
->type
!= EXPR_SYMBOL
)
147 return expr_to_str(expr
->fn
);
150 static void update_mtag_info(struct expression
*expr
, mtag_t tag
,
151 const char *left_name
, const char *tag_info
,
152 struct smatch_state
*state
)
156 sql_insert_mtag_about(tag
, left_name
, tag_info
);
158 allocator
= get_allocator_info(expr
, state
);
160 sql_insert_mtag_info(tag
, ALLOCATOR
, allocator
);
163 struct smatch_state
*get_mtag_return(struct expression
*expr
, struct smatch_state
*state
)
165 struct expression
*left
, *right
;
166 char *left_name
, *right_name
;
167 struct symbol
*left_sym
;
168 struct range_list
*rl
;
173 if (!expr
|| expr
->type
!= EXPR_ASSIGNMENT
|| expr
->op
!= '=')
175 if (!is_fresh_alloc(expr
->right
))
177 if (!rl_intersection(estate_rl(state
), valid_ptr_rl
))
180 left
= strip_expr(expr
->left
);
181 right
= strip_expr(expr
->right
);
183 left_name
= expr_to_str_sym(left
, &left_sym
);
184 if (!left_name
|| !left_sym
)
186 right_name
= expr_to_str(right
);
188 snprintf(buf
, sizeof(buf
), "%s %s %s %s", get_filename(), get_function(),
189 left_name
, right_name
);
190 tag
= str_to_mtag(buf
);
191 tag_sval
.type
= estate_type(state
);
192 tag_sval
.uvalue
= tag
;
194 rl
= rl_filter(estate_rl(state
), valid_ptr_rl
);
196 add_range(&rl
, tag_sval
, tag_sval
);
198 update_mtag_info(expr
, tag
, left_name
, buf
, state
);
200 free_string(left_name
);
201 free_string(right_name
);
203 return alloc_estate_rl(rl
);
206 int get_string_mtag(struct expression
*expr
, mtag_t
*tag
)
210 if (expr
->type
!= EXPR_STRING
|| !expr
->string
)
213 /* I was worried about collisions so I added a xor */
214 xor = str_to_mtag("__smatch string");
215 *tag
= str_to_mtag(expr
->string
->data
);
221 struct symbol
*get_symbol_from_mtag(mtag_t tag
)
225 sym
= search_sym(tag_sym_map
, &tag
);
229 int get_toplevel_mtag(struct symbol
*sym
, mtag_t
*tag
)
237 !(sym
->ctype
.modifiers
& MOD_TOPLEVEL
))
240 snprintf(buf
, sizeof(buf
), "%s %s",
241 (sym
->ctype
.modifiers
& MOD_STATIC
) ? get_filename() : "extern",
243 *tag
= str_to_mtag(buf
);
244 insert_tag_map(*tag
, sym
);
248 bool get_symbol_mtag(struct symbol
*sym
, mtag_t
*tag
)
252 if (!sym
|| !sym
->ident
)
255 if (get_toplevel_mtag(sym
, tag
))
258 if (get_param_num_from_sym(sym
) >= 0)
261 snprintf(buf
, sizeof(buf
), "%s %s %s",
262 get_filename(), get_function(), sym
->ident
->name
);
263 *tag
= str_to_mtag(buf
);
267 static void global_variable(struct symbol
*sym
)
271 if (!get_toplevel_mtag(sym
, &tag
))
274 sql_insert_mtag_about(tag
,
276 (sym
->ctype
.modifiers
& MOD_STATIC
) ? get_filename() : "extern");
279 static int get_array_mtag_offset(struct expression
*expr
, mtag_t
*tag
, int *offset
)
281 struct expression
*array
, *offset_expr
;
289 array
= get_array_base(expr
);
292 type
= get_type(array
);
293 if (!type
|| type
->type
!= SYM_ARRAY
)
295 type
= get_real_base_type(type
);
296 if (!type_bytes(type
))
299 if (!expr_to_mtag_offset(array
, tag
, &start_offset
))
302 offset_expr
= get_array_offset(expr
);
303 if (!get_value(offset_expr
, &sval
))
305 *offset
= start_offset
+ sval
.value
* type_bytes(type
);
310 struct range_list
*swap_mtag_seed(struct expression
*expr
, struct range_list
*rl
)
317 if (!rl_to_sval(rl
, &sval
))
319 if (sval
.type
->type
!= SYM_PTR
|| sval
.uvalue
!= MTAG_SEED
)
322 name
= expr_to_str(expr
);
323 snprintf(buf
, sizeof(buf
), "%s %s %s", get_filename(), get_function(), name
);
325 tag
= str_to_mtag(buf
);
327 return alloc_rl(sval
, sval
);
330 int create_mtag_alias(mtag_t tag
, struct expression
*expr
, mtag_t
*new)
333 int lines_from_start
;
337 * We need the alias to be unique. It's not totally required that it
338 * be the same from one DB build to then next, but it makes debugging
346 lines_from_start
= expr
->pos
.line
- cur_func_sym
->pos
.line
;
347 str
= expr_to_str(expr
);
348 snprintf(buf
, sizeof(buf
), "%lld %d %s", tag
, lines_from_start
, str
);
351 *new = str_to_mtag(buf
);
352 sql_insert_mtag_alias(tag
, *new);
357 static int get_implied_mtag_offset(struct expression
*expr
, mtag_t
*tag
, int *offset
)
359 struct smatch_state
*state
;
363 type
= get_type(expr
);
364 if (!type_is_ptr(type
))
366 state
= get_extra_state(expr
);
367 if (!state
|| !estate_get_single_value(state
, &sval
) || sval
.value
== 0)
370 *tag
= sval
.uvalue
& ~MTAG_OFFSET_MASK
;
371 *offset
= sval
.uvalue
& MTAG_OFFSET_MASK
;
376 * The point of this function is to give you the mtag and the offset so
377 * you can look up the data in the DB. It takes an expression.
379 * So say you give it "foo->bar". Then it would give you the offset of "bar"
380 * and the implied value of "foo". Or if you lookup "*foo" then the offset is
381 * zero and we look up the implied value of "foo. But if the expression is
382 * foo, then if "foo" is a global variable, then we get the mtag and the offset
383 * is zero. If "foo" is a local variable, then there is nothing to look up in
384 * the mtag_data table because that's handled by smatch_extra.c to this returns
388 int expr_to_mtag_offset(struct expression
*expr
, mtag_t
*tag
, int *offset
)
393 if (bits_in_pointer
!= 64)
396 expr
= strip_expr(expr
);
401 return get_array_mtag_offset(expr
, tag
, offset
);
403 if (expr
->type
== EXPR_PREOP
&& expr
->op
== '*') {
404 expr
= strip_expr(expr
->unop
);
405 return get_implied_mtag_offset(expr
, tag
, offset
);
406 } else if (expr
->type
== EXPR_DEREF
) {
407 int tmp
, tmp_offset
= 0;
409 while (expr
->type
== EXPR_DEREF
) {
410 tmp
= get_member_offset_from_deref(expr
);
414 expr
= strip_expr(expr
->deref
);
416 *offset
= tmp_offset
;
417 if (expr
->type
== EXPR_PREOP
&& expr
->op
== '*') {
418 expr
= strip_expr(expr
->unop
);
420 if (get_implied_mtag_offset(expr
, tag
, &tmp_offset
)) {
421 // FIXME: look it up recursively?
427 } else if (expr
->type
== EXPR_SYMBOL
) {
428 return get_symbol_mtag(expr
->symbol
, tag
);
431 } else if (expr
->type
== EXPR_SYMBOL
) {
432 return get_symbol_mtag(expr
->symbol
, tag
);
438 * This function takes an address and returns an sval. Let's take some
439 * example things you might pass to it:
441 * If we were only called from smatch_math, we wouldn't need to bother with
442 * this because it's already been looked up in smatch_extra.c but this is
443 * also called from other places so we have to check smatch_extra.c.
445 * If "foo" is global return the mtag for "foo".
447 * If "foo" is global return the mtag for "foo" + the offset of ".bar".
448 * It also handles string literals.
451 int get_mtag_sval(struct expression
*expr
, sval_t
*sval
)
457 if (bits_in_pointer
!= 64)
460 expr
= strip_expr(expr
);
462 type
= get_type(expr
);
463 if (!type_is_ptr(type
))
466 * There are several options:
468 * If the expr is a string literal, that's an address/mtag.
469 * SYM_ARRAY and SYM_FN are mtags. There are "&foo" type addresses.
470 * And there are saved pointers "p = &foo;"
474 if (expr
->type
== EXPR_STRING
&& get_string_mtag(expr
, &tag
))
477 if (expr
->type
== EXPR_SYMBOL
&&
478 (type
->type
== SYM_ARRAY
|| type
->type
== SYM_FN
) &&
479 get_toplevel_mtag(expr
->symbol
, &tag
))
482 if (expr
->type
== EXPR_PREOP
&& expr
->op
== '&') {
483 expr
= strip_expr(expr
->unop
);
484 if (expr_to_mtag_offset(expr
, &tag
, &offset
))
489 if (get_implied_mtag_offset(expr
, &tag
, &offset
))
494 if (offset
>= MTAG_OFFSET_MASK
)
498 sval
->uvalue
= tag
| offset
;
503 void register_mtag(int id
)
509 * The mtag stuff only works on 64 systems because we store the
510 * information in the pointer itself.
511 * bit 63 : set for alias mtags
512 * bit 62-12: mtag hash
517 add_hook(&global_variable
, BASE_HOOK
);
518 tag_sym_map
= create_hashtable(5000, rehash
, equalkeys
);