1 /*
2 * Copyright (C) 2013 Oracle.
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 * The plan here is to save all the possible values store to a given struct
20 * member.
21 *
22 * We will load all the values in to the function_type_val table first then
23 * run a script on that and load all the resulting values into the type_val
24 * table.
25 *
26 * So in this file we want to take the union of everything assigned to the
27 * struct member and insert it into the function_type_val at the end.
28 *
29 * You would think that we could use smatch_modification_hooks.c or
30 * extra_modification_hook() here to get the information here but in the end we
31 * need to code everything again a third time.
32 *
33 */
34
35 #include "smatch.h"
36 #include "smatch_slist.h"
37 #include "smatch_extra.h"
38
39 static int my_id;
40
41 struct stree_stack *fn_type_val_stack;
42 struct stree *fn_type_val;
43 struct stree *global_type_val;
44
45 static int get_vals(void *_db_vals, int argc, char **argv, char **azColName)
46 {
47 char **db_vals = _db_vals;
48
49 *db_vals = alloc_string(argv[0]);
50 return 0;
51 }
52
53 static void match_inline_start(struct expression *expr)
54 {
55 push_stree(&fn_type_val_stack, fn_type_val);
56 fn_type_val = NULL;
57 }
58
59 static void match_inline_end(struct expression *expr)
60 {
61 free_stree(&fn_type_val);
62 fn_type_val = pop_stree(&fn_type_val_stack);
63 }
64
65 struct expr_rl {
66 struct expression *expr;
67 struct range_list *rl;
68 };
69 static struct expr_rl cached_results[10];
70 static int res_idx;
71
72 static int get_cached(struct expression *expr, struct range_list **rl, int *ret)
73 {
74 int i;
75
76 *ret = 0;
77
78 for (i = 0; i < ARRAY_SIZE(cached_results); i++) {
79 if (expr == cached_results[i].expr) {
80 if (cached_results[i].rl) {
81 *rl = clone_rl(cached_results[i].rl);
82 *ret = 1;
83 }
84 return 1;
85 }
86 }
87
88 return 0;
89 }
90
91 int get_db_type_rl(struct expression *expr, struct range_list **rl)
92 {
93 char *db_vals = NULL;
94 char *member;
95 struct range_list *tmp;
96 struct symbol *type;
97 int ret;
98
99 if (get_cached(expr, rl, &ret))
100 return ret;
101
102 member = get_member_name(expr);
103 if (!member)
104 return 0;
105
106 res_idx = (res_idx + 1) % ARRAY_SIZE(cached_results);
107 cached_results[res_idx].expr = expr;
108 cached_results[res_idx].rl = NULL;
109
110 run_sql(get_vals, &db_vals,
111 "select value from type_value where type = '%s';", member);
112 free_string(member);
113 if (!db_vals)
114 return 0;
115 type = get_type(expr);
116 str_to_rl(type, db_vals, &tmp);
117 free_string(db_vals);
118 if (is_whole_rl(tmp))
119 return 0;
120
121 *rl = tmp;
122 cached_results[res_idx].rl = clone_rl(tmp);
123
124 return 1;
125 }
126
127 static void add_type_val(char *member, struct range_list *rl)
128 {
129 struct smatch_state *old, *add, *new;
130
131 member = alloc_string(member);
132 old = get_state_stree(fn_type_val, my_id, member, NULL);
133 add = alloc_estate_rl(rl);
134 if (old)
135 new = merge_estates(old, add);
136 else
137 new = add;
138 set_state_stree(&fn_type_val, my_id, member, NULL, new);
139 }
140
141 static void add_fake_type_val(char *member, struct range_list *rl, int ignore)
142 {
143 struct smatch_state *old, *add, *new;
144
145 member = alloc_string(member);
146 old = get_state_stree(fn_type_val, my_id, member, NULL);
147 if (old && strcmp(old->name, "min-max") == 0)
148 return;
149 if (ignore && old && strcmp(old->name, "ignore") == 0)
150 return;
151 add = alloc_estate_rl(rl);
152 if (old) {
153 new = merge_estates(old, add);
154 } else {
155 new = add;
156 if (ignore)
157 new->name = alloc_string("ignore");
158 else
159 new->name = alloc_string("min-max");
160 }
161 set_state_stree(&fn_type_val, my_id, member, NULL, new);
162 }
163
164 static void add_global_type_val(char *member, struct range_list *rl)
165 {
166 struct smatch_state *old, *add, *new;
167
168 member = alloc_string(member);
169 old = get_state_stree(global_type_val, my_id, member, NULL);
170 add = alloc_estate_rl(rl);
171 if (old)
172 new = merge_estates(old, add);
173 else
174 new = add;
175 new = clone_estate_perm(new);
176 set_state_stree_perm(&global_type_val, my_id, member, NULL, new);
177 }
178
179 static int has_link_cb(void *has_link, int argc, char **argv, char **azColName)
180 {
181 *(int *)has_link = 1;
182 return 0;
183 }
184
185 static int is_ignored_fake_assignment(void)
186 {
187 struct expression *expr;
188 struct symbol *type;
189 char *member_name;
190 int has_link = 0;
191
192 expr = get_faked_expression();
193 if (!expr || expr->type != EXPR_ASSIGNMENT)
194 return 0;
195 if (!is_void_pointer(expr->right))
196 return 0;
197 member_name = get_member_name(expr->right);
198 if (!member_name)
199 return 0;
200
201 type = get_type(expr->left);
202 if (!type || type->type != SYM_PTR)
203 return 0;
204 type = get_real_base_type(type);
205 if (!type || type->type != SYM_STRUCT)
206 return 0;
207
208 run_sql(has_link_cb, &has_link,
209 "select * from data_info where type = %d and data = '%s' and value = '%s';",
210 TYPE_LINK, member_name, type_to_str(type));
211 return has_link;
212 }
213
214 static int is_container_of(void)
215 {
216 /* We already check the macro name in is_ignored_macro() */
217 struct expression *expr;
218 int offset;
219
220 expr = get_faked_expression();
221 if (!expr || expr->type != EXPR_ASSIGNMENT)
222 return 0;
223
224 offset = get_offset_from_container_of(expr->right);
225 if (offset < 0)
226 return 0;
227 return 1;
228 }
229
230 static bool is_driver_data(void)
231 {
232 static struct expression *prev_expr;
233 struct expression *expr;
234 char *name;
235 static bool prev_ret;
236 bool ret = false;
237
238 expr = get_faked_expression();
239 if (!expr || expr->type != EXPR_ASSIGNMENT)
240 return false;
241
242 if (expr == prev_expr)
243 return prev_ret;
244 prev_expr = expr;
245
246 name = expr_to_str(expr->right);
247 if (!name) {
248 prev_ret = false;
249 return false;
250 }
251
252 if (strstr(name, "get_drvdata(") ||
253 strstr(name, "dev.driver_data") ||
254 strstr(name, "dev->driver_data"))
255 ret = true;
256
257 free_string(name);
258
259 prev_ret = ret;
260 return ret;
261 }
262
263 static int is_ignored_macro(void)
264 {
265 struct expression *expr;
266 char *name;
267
268 expr = get_faked_expression();
269 if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=')
270 return 0;
271 name = get_macro_name(expr->right->pos);
272 if (!name)
273 return 0;
274 if (strcmp(name, "container_of") == 0)
275 return 1;
276 if (strcmp(name, "rb_entry") == 0)
277 return 1;
278 if (strcmp(name, "list_entry") == 0)
279 return 1;
280 if (strcmp(name, "list_first_entry") == 0)
281 return 1;
282 if (strcmp(name, "hlist_entry") == 0)
283 return 1;
284 if (strcmp(name, "per_cpu_ptr") == 0)
285 return 1;
286 if (strcmp(name, "raw_cpu_ptr") == 0)
287 return 1;
288 if (strcmp(name, "this_cpu_ptr") == 0)
289 return 1;
290
291 if (strcmp(name, "TRACE_EVENT") == 0)
292 return 1;
293 if (strcmp(name, "DECLARE_EVENT_CLASS") == 0)
294 return 1;
295 if (strcmp(name, "DEFINE_EVENT") == 0)
296 return 1;
297
298 if (strstr(name, "for_each"))
299 return 1;
300 return 0;
301 }
302
303 static int is_ignored_function(void)
304 {
305 struct expression *expr;
306
307 expr = get_faked_expression();
308 if (!expr || expr->type != EXPR_ASSIGNMENT)
309 return 0;
310 expr = strip_expr(expr->right);
311 if (!expr || expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL)
312 return 0;
313
314 if (sym_name_is("kmalloc", expr->fn))
315 return 1;
316 if (sym_name_is("vmalloc", expr->fn))
317 return 1;
318 if (sym_name_is("kvmalloc", expr->fn))
319 return 1;
320 if (sym_name_is("kmalloc_array", expr->fn))
321 return 1;
322 if (sym_name_is("vmalloc_array", expr->fn))
323 return 1;
324 if (sym_name_is("kvmalloc_array", expr->fn))
325 return 1;
326
327 if (sym_name_is("mmu_memory_cache_alloc", expr->fn))
328 return 1;
329 if (sym_name_is("kmem_alloc", expr->fn))
330 return 1;
331 if (sym_name_is("alloc_pages", expr->fn))
332 return 1;
333
334 if (sym_name_is("netdev_priv", expr->fn))
335 return 1;
336 if (sym_name_is("dev_get_drvdata", expr->fn))
337 return 1;
338 if (sym_name_is("i2c_get_clientdata", expr->fn))
339 return 1;
340 if (sym_name_is("idr_find", expr->fn))
341 return 1;
342
343 return 0;
344 }
345
346 static int is_uncasted_pointer_assign(void)
347 {
348 struct expression *expr;
349 struct symbol *left_type, *right_type;
350
351 expr = get_faked_expression();
352 if (!expr)
353 return 0;
354 if (expr->type == EXPR_PREOP || expr->type == EXPR_POSTOP) {
355 if (expr->op == SPECIAL_INCREMENT || expr->op == SPECIAL_DECREMENT)
356 return 1;
357 }
358 if (expr->type != EXPR_ASSIGNMENT)
359 return 0;
360 left_type = get_type(expr->left);
361 right_type = get_type(expr->right);
362
363 if (!left_type || !right_type)
364 return 0;
365
366 if (left_type->type == SYM_STRUCT && left_type == right_type)
367 return 1;
368
369 if (left_type->type != SYM_PTR &&
370 left_type->type != SYM_ARRAY)
371 return 0;
372 if (right_type->type != SYM_PTR &&
373 right_type->type != SYM_ARRAY)
374 return 0;
375 left_type = get_real_base_type(left_type);
376 right_type = get_real_base_type(right_type);
377
378 if (left_type == right_type)
379 return 1;
380 return 0;
381 }
382
383 static int set_param_type(void *_type_str, int argc, char **argv, char **azColName)
384 {
385 char **type_str = _type_str;
386 static char type_buf[128];
387
388 if (*type_str) {
389 if (strcmp(*type_str, argv[0]) == 0)
390 return 0;
391 strncpy(type_buf, "unknown", sizeof(type_buf));
392 return 0;
393 }
394 strncpy(type_buf, argv[0], sizeof(type_buf));
395 *type_str = type_buf;
396
397 return 0;
398 }
399
400 static char *db_get_parameter_type(int param)
401 {
402 char *ret = NULL;
403
404 if (!cur_func_sym)
405 return NULL;
406
407 run_sql(set_param_type, &ret,
408 "select value from fn_data_link where "
409 "file = '%s' and function = '%s' and static = %d and type = %d and parameter = %d and key = '$';",
410 (cur_func_sym->ctype.modifiers & MOD_STATIC) ? get_base_file() : "extern",
411 cur_func_sym->ident->name,
412 !!(cur_func_sym->ctype.modifiers & MOD_STATIC),
413 PASSES_TYPE, param);
414
415 return ret;
416 }
417
418 static int is_uncasted_fn_param_from_db(void)
419 {
420 struct expression *expr, *right;
421 struct symbol *left_type;
422 char left_type_name[128];
423 int param;
424 char *right_type_name;
425 static struct expression *prev_expr;
426 static int prev_ans;
427
428 expr = get_faked_expression();
429
430 if (expr == prev_expr)
431 return prev_ans;
432 prev_expr = expr;
433 prev_ans = 0;
434
435 if (!expr || expr->type != EXPR_ASSIGNMENT)
436 return 0;
437 left_type = get_type(expr->left);
438 if (!left_type || left_type->type != SYM_PTR)
439 return 0;
440 left_type = get_real_base_type(left_type);
441 if (!left_type || left_type->type != SYM_STRUCT)
442 return 0;
443 snprintf(left_type_name, sizeof(left_type_name), "%s", type_to_str(left_type));
444
445 right = strip_expr(expr->right);
446 param = get_param_num(right);
447 if (param < 0)
448 return 0;
449 right_type_name = db_get_parameter_type(param);
450 if (!right_type_name)
451 return 0;
452
453 if (strcmp(right_type_name, left_type_name) == 0) {
454 prev_ans = 1;
455 return 1;
456 }
457
458 return 0;
459 }
460
461 static void match_assign_value(struct expression *expr)
462 {
463 char *member, *right_member;
464 struct range_list *rl;
465 struct symbol *type;
466
467 if (!cur_func_sym)
468 return;
469
470 type = get_type(expr->left);
471 if (type && type->type == SYM_STRUCT)
472 return;
473 member = get_member_name(expr->left);
474 if (!member)
475 return;
476
477 /* if we're saying foo->mtu = bar->mtu then that doesn't add information */
478 right_member = get_member_name(expr->right);
479 if (right_member && strcmp(right_member, member) == 0)
480 goto free;
481
482 if (is_fake_call(expr->right)) {
483 if (is_ignored_macro())
484 goto free;
485 if (is_ignored_function())
486 goto free;
487 if (is_uncasted_pointer_assign())
488 goto free;
489 if (is_uncasted_fn_param_from_db())
490 goto free;
491 if (is_container_of())
492 goto free;
493 if (is_driver_data())
494 goto free;
495 add_fake_type_val(member, alloc_whole_rl(get_type(expr->left)), is_ignored_fake_assignment());
496 goto free;
497 }
498
499 if (expr->op == '=') {
500 get_absolute_rl(expr->right, &rl);
501 rl = cast_rl(type, rl);
502 } else {
503 /*
504 * This is a bit cheating. We order it so this will already be set
505 * by smatch_extra.c and we just look up the value.
506 */
507 get_absolute_rl(expr->left, &rl);
508 }
509 add_type_val(member, rl);
510 free:
511 free_string(right_member);
512 free_string(member);
513 }
514
515 /*
516 * If we too: int *p = &my_struct->member then abandon all hope of tracking
517 * my_struct->member.
518 */
519 static void match_assign_pointer(struct expression *expr)
520 {
521 struct expression *right;
522 char *member;
523 struct range_list *rl;
524 struct symbol *type;
525
526 right = strip_expr(expr->right);
527 if (right->type != EXPR_PREOP || right->op != '&')
528 return;
529 right = strip_expr(right->unop);
530
531 member = get_member_name(right);
532 if (!member)
533 return;
534 type = get_type(right);
535 rl = alloc_whole_rl(type);
536 add_type_val(member, rl);
537 free_string(member);
538 }
539
540 static void match_global_assign(struct expression *expr)
541 {
542 char *member;
543 struct range_list *rl;
544 struct symbol *type;
545
546 type = get_type(expr->left);
547 if (type && (type->type == SYM_ARRAY || type->type == SYM_STRUCT))
548 return;
549 member = get_member_name(expr->left);
550 if (!member)
551 return;
552 get_absolute_rl(expr->right, &rl);
553 rl = cast_rl(type, rl);
554 add_global_type_val(member, rl);
555 free_string(member);
556 }
557
558 static void unop_expr(struct expression *expr)
559 {
560 struct range_list *rl;
561 char *member;
562
563 if (expr->op != SPECIAL_DECREMENT && expr->op != SPECIAL_INCREMENT)
564 return;
565
566 expr = strip_expr(expr->unop);
567 member = get_member_name(expr);
568 if (!member)
569 return;
570 rl = alloc_whole_rl(get_type(expr));
571 add_type_val(member, rl);
572 free_string(member);
573 }
574
575 static void asm_expr(struct statement *stmt)
576 {
577 struct expression *expr;
578 struct range_list *rl;
579 char *member;
580
581 FOR_EACH_PTR(stmt->asm_outputs, expr) {
582 member = get_member_name(expr->expr);
583 if (!member)
584 continue;
585 rl = alloc_whole_rl(get_type(expr->expr));
586 add_type_val(member, rl);
587 free_string(member);
588 } END_FOR_EACH_PTR(expr);
589 }
590
591 static void db_param_add(struct expression *expr, int param, char *key, char *value)
592 {
593 struct expression *arg;
594 struct symbol *type;
595 struct range_list *rl;
596 char *member;
597
598 if (strcmp(key, "*$") != 0)
599 return;
600
601 while (expr->type == EXPR_ASSIGNMENT)
602 expr = strip_expr(expr->right);
603 if (expr->type != EXPR_CALL)
604 return;
605
606 arg = get_argument_from_call_expr(expr->args, param);
607 arg = strip_expr(arg);
608 if (!arg)
609 return;
610 type = get_member_type_from_key(arg, key);
611 /*
612 * The situation here is that say we memset() a void pointer to zero
613 * then that's returned to the called as "*$ = 0;" but on the caller's
614 * side it's not void, it's a struct.
615 *
616 * So the question is should we be passing that slightly bogus
617 * information back to the caller? Maybe, maybe not, but either way we
618 * are not going to record it here because a struct can't be zero.
619 *
620 */
621 if (type && type->type == SYM_STRUCT)
622 return;
623
624 if (arg->type != EXPR_PREOP || arg->op != '&')
625 return;
626 arg = strip_expr(arg->unop);
627
628 member = get_member_name(arg);
629 if (!member)
630 return;
631 call_results_to_rl(expr, type, value, &rl);
632 add_type_val(member, rl);
633 free_string(member);
634 }
635
636 static void match_end_func_info(struct symbol *sym)
637 {
638 struct sm_state *sm;
639
640 FOR_EACH_SM(fn_type_val, sm) {
641 sql_insert_function_type_value(sm->name, sm->state->name);
642 } END_FOR_EACH_SM(sm);
643 }
644
645 static void clear_cache(struct symbol *sym)
646 {
647 memset(cached_results, 0, sizeof(cached_results));
648 }
649
650 static void match_after_func(struct symbol *sym)
651 {
652 free_stree(&fn_type_val);
653 }
654
655 static void match_end_file(struct symbol_list *sym_list)
656 {
657 struct sm_state *sm;
658
659 FOR_EACH_SM(global_type_val, sm) {
660 sql_insert_function_type_value(sm->name, sm->state->name);
661 } END_FOR_EACH_SM(sm);
662 }
663
664 void register_type_val(int id)
665 {
666 my_id = id;
667 add_hook(&clear_cache, AFTER_FUNC_HOOK);
668
669 if (!option_info)
670 return;
671
672 add_hook(&match_assign_value, ASSIGNMENT_HOOK_AFTER);
673 add_hook(&match_assign_pointer, ASSIGNMENT_HOOK);
674 add_hook(&unop_expr, OP_HOOK);
675 add_hook(&asm_expr, ASM_HOOK);
676 select_return_states_hook(PARAM_ADD, &db_param_add);
677 select_return_states_hook(PARAM_SET, &db_param_add);
678
679
680 add_hook(&match_inline_start, INLINE_FN_START);
681 add_hook(&match_inline_end, INLINE_FN_END);
682
683 add_hook(&match_end_func_info, END_FUNC_HOOK);
684 add_hook(&match_after_func, AFTER_FUNC_HOOK);
685
686 add_hook(&match_global_assign, GLOBAL_ASSIGNMENT_HOOK);
687 add_hook(&match_end_file, END_FILE_HOOK);
688 }