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 int is_ignored_macro(void)
231 {
232 struct expression *expr;
233 char *name;
234
235 expr = get_faked_expression();
236 if (!expr || expr->type != EXPR_ASSIGNMENT)
237 return 0;
238 name = get_macro_name(expr->right->pos);
239 if (!name)
240 return 0;
241 if (strcmp(name, "container_of") == 0)
242 return 1;
243 if (strcmp(name, "rb_entry") == 0)
244 return 1;
245 if (strcmp(name, "list_entry") == 0)
246 return 1;
247 if (strcmp(name, "list_first_entry") == 0)
248 return 1;
249 if (strcmp(name, "hlist_entry") == 0)
250 return 1;
251 if (strstr(name, "for_each"))
252 return 1;
253 return 0;
254 }
255
256 static int is_ignored_function(void)
257 {
258 struct expression *expr;
259
260 expr = get_faked_expression();
261 if (!expr || expr->type != EXPR_ASSIGNMENT)
262 return 0;
263 expr = strip_expr(expr->right);
264 if (!expr || expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL)
265 return 0;
266
267 if (sym_name_is("kmalloc", expr->fn))
268 return 1;
269 if (sym_name_is("netdev_priv", expr->fn))
270 return 1;
271 if (sym_name_is("dev_get_drvdata", expr->fn))
272 return 1;
273
274 return 0;
275 }
276
277 static int is_uncasted_pointer_assign(void)
278 {
279 struct expression *expr;
280 struct symbol *left_type, *right_type;
281
282 expr = get_faked_expression();
283 if (!expr)
284 return 0;
285 if (expr->type == EXPR_PREOP || expr->type == EXPR_POSTOP) {
286 if (expr->op == SPECIAL_INCREMENT || expr->op == SPECIAL_DECREMENT)
287 return 1;
288 }
289 if (expr->type != EXPR_ASSIGNMENT)
290 return 0;
291 left_type = get_type(expr->left);
292 right_type = get_type(expr->right);
293
294 if (!left_type || !right_type)
295 return 0;
296
297 if (left_type->type != SYM_PTR &&
298 left_type->type != SYM_ARRAY)
299 return 0;
300 if (right_type->type != SYM_PTR &&
301 right_type->type != SYM_ARRAY)
302 return 0;
303 left_type = get_real_base_type(left_type);
304 right_type = get_real_base_type(right_type);
305
306 if (left_type == right_type)
307 return 1;
308 return 0;
309 }
310
311 static int set_param_type(void *_type_str, int argc, char **argv, char **azColName)
312 {
313 char **type_str = _type_str;
314 static char type_buf[128];
315
316 if (*type_str) {
317 if (strcmp(*type_str, argv[0]) == 0)
318 return 0;
319 strncpy(type_buf, "unknown", sizeof(type_buf));
320 return 0;
321 }
322 strncpy(type_buf, argv[0], sizeof(type_buf));
323 *type_str = type_buf;
324
325 return 0;
326 }
327
328 static char *db_get_parameter_type(int param)
329 {
330 char *ret = NULL;
331
332 if (!cur_func_sym)
333 return NULL;
334
335 run_sql(set_param_type, &ret,
336 "select value from fn_data_link where "
337 "file = '%s' and function = '%s' and static = %d and type = %d and parameter = %d and key = '$';",
338 (cur_func_sym->ctype.modifiers & MOD_STATIC) ? get_base_file() : "extern",
339 cur_func_sym->ident->name,
340 !!(cur_func_sym->ctype.modifiers & MOD_STATIC),
341 PASSES_TYPE, param);
342
343 return ret;
344 }
345
346 static int is_uncasted_fn_param_from_db(void)
347 {
348 struct expression *expr, *right;
349 struct symbol *left_type;
350 char left_type_name[128];
351 int param;
352 char *right_type_name;
353 static struct expression *prev_expr;
354 static int prev_ans;
355
356 expr = get_faked_expression();
357
358 if (expr == prev_expr)
359 return prev_ans;
360 prev_expr = expr;
361 prev_ans = 0;
362
363 if (!expr || expr->type != EXPR_ASSIGNMENT)
364 return 0;
365 left_type = get_type(expr->left);
366 if (!left_type || left_type->type != SYM_PTR)
367 return 0;
368 left_type = get_real_base_type(left_type);
369 if (!left_type || left_type->type != SYM_STRUCT)
370 return 0;
371 snprintf(left_type_name, sizeof(left_type_name), "%s", type_to_str(left_type));
372
373 right = strip_expr(expr->right);
374 param = get_param_num(right);
375 if (param < 0)
376 return 0;
377 right_type_name = db_get_parameter_type(param);
378 if (!right_type_name)
379 return 0;
380
381 if (strcmp(right_type_name, left_type_name) == 0) {
382 prev_ans = 1;
383 return 1;
384 }
385
386 return 0;
387 }
388
389 static void match_assign_value(struct expression *expr)
390 {
391 char *member, *right_member;
392 struct range_list *rl;
393 struct symbol *type;
394
395 if (!cur_func_sym)
396 return;
397
398 type = get_type(expr->left);
399 member = get_member_name(expr->left);
400 if (!member)
401 return;
402
403 /* if we're saying foo->mtu = bar->mtu then that doesn't add information */
404 right_member = get_member_name(expr->right);
405 if (right_member && strcmp(right_member, member) == 0)
406 goto free;
407
408 if (is_fake_call(expr->right)) {
409 if (is_ignored_macro())
410 goto free;
411 if (is_ignored_function())
412 goto free;
413 if (is_uncasted_pointer_assign())
414 goto free;
415 if (is_uncasted_fn_param_from_db())
416 goto free;
417 if (is_container_of())
418 goto free;
419 add_fake_type_val(member, alloc_whole_rl(get_type(expr->left)), is_ignored_fake_assignment());
420 goto free;
421 }
422
423 if (expr->op == '=') {
424 get_absolute_rl(expr->right, &rl);
425 rl = cast_rl(type, rl);
426 } else {
427 /*
428 * This is a bit cheating. We order it so this will already be set
429 * by smatch_extra.c and we just look up the value.
430 */
431 get_absolute_rl(expr->left, &rl);
432 }
433 add_type_val(member, rl);
434 free:
435 free_string(right_member);
436 free_string(member);
437 }
438
439 /*
440 * If we too: int *p = &my_struct->member then abandon all hope of tracking
441 * my_struct->member.
442 */
443 static void match_assign_pointer(struct expression *expr)
444 {
445 struct expression *right;
446 char *member;
447 struct range_list *rl;
448 struct symbol *type;
449
450 right = strip_expr(expr->right);
451 if (right->type != EXPR_PREOP || right->op != '&')
452 return;
453 right = strip_expr(right->unop);
454
455 member = get_member_name(right);
456 if (!member)
457 return;
458 type = get_type(right);
459 rl = alloc_whole_rl(type);
460 add_type_val(member, rl);
461 free_string(member);
462 }
463
464 static void match_global_assign(struct expression *expr)
465 {
466 char *member;
467 struct range_list *rl;
468 struct symbol *type;
469
470 type = get_type(expr->left);
471 if (type && (type->type == SYM_ARRAY || type->type == SYM_STRUCT))
472 return;
473 member = get_member_name(expr->left);
474 if (!member)
475 return;
476 get_absolute_rl(expr->right, &rl);
477 rl = cast_rl(type, rl);
478 add_global_type_val(member, rl);
479 free_string(member);
480 }
481
482 static void unop_expr(struct expression *expr)
483 {
484 struct range_list *rl;
485 char *member;
486
487 if (expr->op != SPECIAL_DECREMENT && expr->op != SPECIAL_INCREMENT)
488 return;
489
490 expr = strip_expr(expr->unop);
491 member = get_member_name(expr);
492 if (!member)
493 return;
494 rl = alloc_whole_rl(get_type(expr));
495 add_type_val(member, rl);
496 free_string(member);
497 }
498
499 static void asm_expr(struct statement *stmt)
500 {
501 struct expression *expr;
502 struct range_list *rl;
503 char *member;
504 int state = 0;
505
506 FOR_EACH_PTR(stmt->asm_outputs, expr) {
507 switch (state) {
508 case 0: /* identifier */
509 case 1: /* constraint */
510 state++;
511 continue;
512 case 2: /* expression */
513 state = 0;
514 member = get_member_name(expr);
515 if (!member)
516 continue;
517 rl = alloc_whole_rl(get_type(expr));
518 add_type_val(member, rl);
519 free_string(member);
520 continue;
521 }
522 } END_FOR_EACH_PTR(expr);
523 }
524
525 static void db_param_add(struct expression *expr, int param, char *key, char *value)
526 {
527 struct expression *arg;
528 struct symbol *type;
529 struct range_list *rl;
530 char *member;
531
532 if (strcmp(key, "*$") != 0)
533 return;
534
535 while (expr->type == EXPR_ASSIGNMENT)
536 expr = strip_expr(expr->right);
537 if (expr->type != EXPR_CALL)
538 return;
539
540 arg = get_argument_from_call_expr(expr->args, param);
541 arg = strip_expr(arg);
542 if (!arg)
543 return;
544 type = get_member_type_from_key(arg, key);
545 if (arg->type != EXPR_PREOP || arg->op != '&')
546 return;
547 arg = strip_expr(arg->unop);
548
549 member = get_member_name(arg);
550 if (!member)
551 return;
552 call_results_to_rl(expr, type, value, &rl);
553 add_type_val(member, rl);
554 free_string(member);
555 }
556
557 static void match_end_func_info(struct symbol *sym)
558 {
559 struct sm_state *sm;
560
561 FOR_EACH_SM(fn_type_val, sm) {
562 sql_insert_function_type_value(sm->name, sm->state->name);
563 } END_FOR_EACH_SM(sm);
564 }
565
566 static void clear_cache(struct symbol *sym)
567 {
568 memset(cached_results, 0, sizeof(cached_results));
569 }
570
571 static void match_after_func(struct symbol *sym)
572 {
573 free_stree(&fn_type_val);
574 }
575
576 static void match_end_file(struct symbol_list *sym_list)
577 {
578 struct sm_state *sm;
579
580 FOR_EACH_SM(global_type_val, sm) {
581 sql_insert_function_type_value(sm->name, sm->state->name);
582 } END_FOR_EACH_SM(sm);
583 }
584
585 void register_type_val(int id)
586 {
587 my_id = id;
588 add_hook(&clear_cache, AFTER_FUNC_HOOK);
589
590 if (!option_info)
591 return;
592
593 add_hook(&match_assign_value, ASSIGNMENT_HOOK_AFTER);
594 add_hook(&match_assign_pointer, ASSIGNMENT_HOOK);
595 add_hook(&unop_expr, OP_HOOK);
596 add_hook(&asm_expr, ASM_HOOK);
597 select_return_states_hook(PARAM_ADD, &db_param_add);
598 select_return_states_hook(PARAM_SET, &db_param_add);
599
600
601 add_hook(&match_inline_start, INLINE_FN_START);
602 add_hook(&match_inline_end, INLINE_FN_END);
603
604 add_hook(&match_end_func_info, END_FUNC_HOOK);
605 add_hook(&match_after_func, AFTER_FUNC_HOOK);
606
607 add_hook(&match_global_assign, GLOBAL_ASSIGNMENT_HOOK);
608 add_hook(&match_end_file, END_FILE_HOOK);
609 }