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"
49 #include <openssl/md5.h>
53 static mtag_t
str_to_tag(const char *str
)
55 unsigned char c
[MD5_DIGEST_LENGTH
];
56 unsigned long long *tag
= (unsigned long long *)&c
;
62 MD5_Update(&mdContext
, str
, len
);
63 MD5_Final(c
, &mdContext
);
65 *tag
&= ~MTAG_ALIAS_BIT
;
66 *tag
&= ~MTAG_OFFSET_MASK
;
74 } allocator_info
[] = {
81 static bool is_mtag_call(struct expression
*expr
)
83 struct expression
*arg
;
87 if (expr
->type
!= EXPR_CALL
||
88 expr
->fn
->type
!= EXPR_SYMBOL
||
92 for (i
= 0; i
< ARRAY_SIZE(allocator_info
); i
++) {
93 if (strcmp(expr
->fn
->symbol
->ident
->name
, allocator_info
[i
].name
) == 0)
96 if (i
== ARRAY_SIZE(allocator_info
))
99 arg
= get_argument_from_call_expr(expr
->args
, allocator_info
[i
].size_arg
);
100 if (!get_implied_value(arg
, &sval
))
106 struct smatch_state
*swap_mtag_return(struct expression
*expr
, struct smatch_state
*state
)
108 struct expression
*left
, *right
;
109 char *left_name
, *right_name
;
110 struct symbol
*left_sym
;
111 struct range_list
*rl
;
116 if (!expr
|| expr
->type
!= EXPR_ASSIGNMENT
|| expr
->op
!= '=')
119 if (!estate_rl(state
) || strcmp(state
->name
, "0,4096-ptr_max") != 0)
122 left
= strip_expr(expr
->left
);
123 right
= strip_expr(expr
->right
);
125 if (!is_mtag_call(right
))
128 left_name
= expr_to_str_sym(left
, &left_sym
);
129 if (!left_name
|| !left_sym
)
131 right_name
= expr_to_str(right
);
133 snprintf(buf
, sizeof(buf
), "%s %s %s %s", get_filename(), get_function(),
134 left_name
, right_name
);
135 tag
= str_to_tag(buf
);
136 tag_sval
.type
= estate_type(state
);
137 tag_sval
.uvalue
= tag
;
139 rl
= rl_filter(estate_rl(state
), valid_ptr_rl
);
141 add_range(&rl
, tag_sval
, tag_sval
);
143 sql_insert_mtag_about(tag
, left_name
, buf
);
145 free_string(left_name
);
146 free_string(right_name
);
148 return alloc_estate_rl(rl
);
151 int get_string_mtag(struct expression
*expr
, mtag_t
*tag
)
155 if (expr
->type
!= EXPR_STRING
|| !expr
->string
)
158 /* I was worried about collisions so I added a xor */
159 xor = str_to_tag("__smatch string");
160 *tag
= str_to_tag(expr
->string
->data
);
166 int get_toplevel_mtag(struct symbol
*sym
, mtag_t
*tag
)
174 !(sym
->ctype
.modifiers
& MOD_TOPLEVEL
))
177 snprintf(buf
, sizeof(buf
), "%s %s",
178 (sym
->ctype
.modifiers
& MOD_STATIC
) ? get_filename() : "extern",
180 *tag
= str_to_tag(buf
);
184 int get_deref_mtag(struct expression
*expr
, mtag_t
*tag
)
186 mtag_t container_tag
, member_tag
;
190 * I'm not totally sure what I'm doing...
192 * This is supposed to get something like "global_var->ptr", but I don't
193 * feel like it's complete at all.
197 if (!get_mtag(expr
->unop
, &container_tag
))
200 offset
= get_member_offset_from_deref(expr
);
204 if (!mtag_map_select_tag(container_tag
, -offset
, &member_tag
))
211 static void global_variable(struct symbol
*sym
)
215 if (!get_toplevel_mtag(sym
, &tag
))
218 sql_insert_mtag_about(tag
,
220 (sym
->ctype
.modifiers
& MOD_STATIC
) ? get_filename() : "extern");
223 static int get_array_mtag_offset(struct expression
*expr
, mtag_t
*tag
, int *offset
)
225 struct expression
*array
, *offset_expr
;
233 array
= get_array_base(expr
);
236 type
= get_type(array
);
237 if (!type
|| type
->type
!= SYM_ARRAY
)
239 type
= get_real_base_type(type
);
240 if (!type_bytes(type
))
243 if (!expr_to_mtag_offset(array
, tag
, &start_offset
))
246 offset_expr
= get_array_offset(expr
);
247 if (!get_value(offset_expr
, &sval
))
249 *offset
= start_offset
+ sval
.value
* type_bytes(type
);
254 static int get_implied_mtag_offset(struct expression
*expr
, mtag_t
*tag
, int *offset
)
256 struct smatch_state
*state
;
260 type
= get_type(expr
);
261 if (!type_is_ptr(type
))
263 state
= get_extra_state(expr
);
264 if (!state
|| !estate_get_single_value(state
, &sval
) || sval
.value
== 0)
267 *tag
= sval
.uvalue
& ~MTAG_OFFSET_MASK
;
268 *offset
= sval
.uvalue
& MTAG_OFFSET_MASK
;
272 static int get_mtag_cnt
;
273 int get_mtag(struct expression
*expr
, mtag_t
*tag
)
277 expr
= strip_expr(expr
);
281 if (get_mtag_cnt
> 0)
286 switch (expr
->type
) {
288 if (get_string_mtag(expr
, tag
)) {
294 if (get_toplevel_mtag(expr
->symbol
, tag
)) {
300 if (get_deref_mtag(expr
, tag
)) {
312 struct range_list
*swap_mtag_seed(struct expression
*expr
, struct range_list
*rl
)
319 if (!rl_to_sval(rl
, &sval
))
321 if (sval
.type
->type
!= SYM_PTR
|| sval
.uvalue
!= MTAG_SEED
)
324 name
= expr_to_str(expr
);
325 snprintf(buf
, sizeof(buf
), "%s %s %s", get_filename(), get_function(), name
);
327 tag
= str_to_tag(buf
);
329 return alloc_rl(sval
, sval
);
332 int create_mtag_alias(mtag_t tag
, struct expression
*expr
, mtag_t
*new)
335 int lines_from_start
;
339 * We need the alias to be unique. It's not totally required that it
340 * be the same from one DB build to then next, but it makes debugging
348 lines_from_start
= expr
->pos
.line
- cur_func_sym
->pos
.line
;
349 str
= expr_to_str(expr
);
350 snprintf(buf
, sizeof(buf
), "%lld %d %s", tag
, lines_from_start
, str
);
353 *new = str_to_tag(buf
);
354 sql_insert_mtag_alias(tag
, *new);
360 * The point of this function is to give you the mtag and the offset so
361 * you can look up the data in the DB. It takes an expression.
363 * So say you give it "foo->bar". Then it would give you the offset of "bar"
364 * and the implied value of "foo". Or if you lookup "*foo" then the offset is
365 * zero and we look up the implied value of "foo. But if the expression is
366 * foo, then if "foo" is a global variable, then we get the mtag and the offset
367 * is zero. If "foo" is a local variable, then there is nothing to look up in
368 * the mtag_data table because that's handled by smatch_extra.c to this returns
372 int expr_to_mtag_offset(struct expression
*expr
, mtag_t
*tag
, int *offset
)
377 expr
= strip_expr(expr
);
382 return get_array_mtag_offset(expr
, tag
, offset
);
384 if (expr
->type
== EXPR_PREOP
&& expr
->op
== '*') {
385 expr
= strip_expr(expr
->unop
);
386 if (get_implied_mtag_offset(expr
, tag
, offset
))
388 } else if (expr
->type
== EXPR_DEREF
) {
391 *offset
= get_member_offset_from_deref(expr
);
395 if (expr
->type
== EXPR_PREOP
&& expr
->op
== '*')
396 expr
= strip_expr(expr
->unop
);
398 if (get_implied_mtag_offset(expr
, tag
, &next_offset
)) {
399 // FIXME: look it up recursively?
406 switch (expr
->type
) {
408 return get_string_mtag(expr
, tag
);
410 return get_toplevel_mtag(expr
->symbol
, tag
);
415 int get_mtag_sval(struct expression
*expr
, sval_t
*sval
)
421 if (bits_in_pointer
!= 64)
424 expr
= strip_expr(expr
);
426 type
= get_type(expr
);
427 if (!type_is_ptr(type
))
430 * There are only three options:
432 * 1) An array address:
434 * 2) An address like so:
435 * p = &my_struct->member;
441 if (expr
->type
== EXPR_STRING
&& get_string_mtag(expr
, &tag
))
444 if (expr
->type
== EXPR_SYMBOL
&&
445 (type
->type
== SYM_ARRAY
|| type
->type
== SYM_FN
) &&
446 get_toplevel_mtag(expr
->symbol
, &tag
))
449 if (get_implied_mtag_offset(expr
, &tag
, &offset
))
452 if (expr
->type
!= EXPR_PREOP
|| expr
->op
!= '&')
454 expr
= strip_expr(expr
->unop
);
456 if (!expr_to_mtag_offset(expr
, &tag
, &offset
))
458 if (offset
> MTAG_OFFSET_MASK
)
459 offset
= MTAG_OFFSET_MASK
;
463 sval
->uvalue
= tag
| offset
;
468 void register_mtag(int id
)
474 * The mtag stuff only works on 64 systems because we store the
475 * information in the pointer itself.
476 * bit 63 : set for alias mtags
477 * bit 62-12: mtag hash
481 if (bits_in_pointer
!= 64)
484 add_hook(&global_variable
, BASE_HOOK
);