1 /*
2 * Copyright (C) 2017 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 #include "smatch.h"
19 #include "smatch_slist.h"
20 #include "smatch_extra.h"
21
22 static int my_id;
23 static int param_id;
24
25 static struct stree *used_stree;
26 static struct stree_stack *saved_stack;
27
28 STATE(used);
29
30 int get_param_from_container_of(struct expression *expr)
31 {
32 struct expression *param_expr;
33 struct symbol *type;
34 sval_t sval;
35 int param;
36
37
38 type = get_type(expr);
39 if (!type || type->type != SYM_PTR)
40 return -1;
41
42 expr = strip_expr(expr);
43 if (expr->type != EXPR_BINOP || expr->op != '-')
44 return -1;
45
46 if (!get_value(expr->right, &sval))
47 return -1;
48 if (sval.value < 0 || sval.value > 4096)
49 return -1;
50
51 param_expr = get_assigned_expr(expr->left);
52 if (!param_expr)
53 return -1;
54 param = get_param_num(param_expr);
55 if (param < 0)
56 return -1;
57
58 return param;
59 }
60
61 int get_offset_from_container_of(struct expression *expr)
62 {
63 struct expression *param_expr;
64 struct symbol *type;
65 sval_t sval;
66
67 type = get_type(expr);
68 if (!type || type->type != SYM_PTR)
69 return -1;
70
71 expr = strip_expr(expr);
72 if (expr->type != EXPR_BINOP || expr->op != '-')
73 return -1;
74
75 if (!get_value(expr->right, &sval))
76 return -1;
77 if (sval.value < 0 || sval.value > 4096)
78 return -1;
79
80 param_expr = get_assigned_expr(expr->left);
81 if (!param_expr)
82 return -1;
83
84 return sval.value;
85 }
86
87 static int get_container_arg(struct symbol *sym)
88 {
89 struct expression *__mptr;
90 int param;
91
92 if (!sym || !sym->ident)
93 return -1;
94
95 __mptr = get_assigned_expr_name_sym(sym->ident->name, sym);
96 param = get_param_from_container_of(__mptr);
97
98 return param;
99 }
100
101 static int get_container_offset(struct symbol *sym)
102 {
103 struct expression *__mptr;
104 int offset;
105
106 if (!sym || !sym->ident)
107 return -1;
108
109 __mptr = get_assigned_expr_name_sym(sym->ident->name, sym);
110 offset = get_offset_from_container_of(__mptr);
111
112 return offset;
113 }
114
115 static char *get_container_name(struct sm_state *sm, int offset)
116 {
117 static char buf[256];
118 const char *name;
119
120 name = get_param_name(sm);
121 if (!name)
122 return NULL;
123
124 if (name[0] == '$')
125 snprintf(buf, sizeof(buf), "$(-%d)%s", offset, name + 1);
126 else if (name[0] == '*' || name[1] == '$')
127 snprintf(buf, sizeof(buf), "*$(-%d)%s", offset, name + 2);
128 else
129 return NULL;
130
131 return buf;
132 }
133
134 static void get_state_hook(int owner, const char *name, struct symbol *sym)
135 {
136 int arg;
137
138 if (!option_info)
139 return;
140 if (__in_fake_assign)
141 return;
142
143 arg = get_container_arg(sym);
144 if (arg >= 0)
145 set_state_stree(&used_stree, my_id, name, sym, &used);
146 }
147
148 static void set_param_used(struct expression *call, struct expression *arg, char *key, char *unused)
149 {
150 struct symbol *sym;
151 char *name;
152 int arg_nr;
153
154 name = get_variable_from_key(arg, key, &sym);
155 if (!name || !sym)
156 goto free;
157
158 arg_nr = get_container_arg(sym);
159 if (arg_nr >= 0)
160 set_state(my_id, name, sym, &used);
161 free:
162 free_string(name);
163 }
164
165 static void process_states(void)
166 {
167 struct sm_state *tmp;
168 int arg, offset;
169 const char *name;
170
171 FOR_EACH_SM(used_stree, tmp) {
172 arg = get_container_arg(tmp->sym);
173 offset = get_container_offset(tmp->sym);
174 if (arg < 0 || offset < 0)
175 continue;
176 name = get_container_name(tmp, offset);
177 if (!name)
178 continue;
179 sql_insert_return_implies(CONTAINER, arg, name, "");
180 } END_FOR_EACH_SM(tmp);
181
182 free_stree(&used_stree);
183 }
184
185 static void match_function_def(struct symbol *sym)
186 {
187 free_stree(&used_stree);
188 }
189
190 static void match_save_states(struct expression *expr)
191 {
192 push_stree(&saved_stack, used_stree);
193 used_stree = NULL;
194 }
195
196 static void match_restore_states(struct expression *expr)
197 {
198 free_stree(&used_stree);
199 used_stree = pop_stree(&saved_stack);
200 }
201
202 static void print_returns_container_of(int return_id, char *return_ranges, struct expression *expr)
203 {
204 int offset;
205 int param;
206 char key[64];
207 char value[64];
208
209 param = get_param_from_container_of(expr);
210 if (param < 0)
211 return;
212 offset = get_offset_from_container_of(expr);
213 if (offset < 0)
214 return;
215
216 snprintf(key, sizeof(key), "%d", param);
217 snprintf(value, sizeof(value), "-%d", offset);
218
219 /* no need to add it to return_implies because it's not really param_used */
220 sql_insert_return_states(return_id, return_ranges, CONTAINER, -1,
221 key, value);
222 }
223
224 static void returns_container_of(struct expression *expr, int param, char *key, char *value)
225 {
226 struct expression *call, *arg;
227 int offset;
228 char buf[64];
229
230 if (expr->type != EXPR_ASSIGNMENT || expr->op != '=')
231 return;
232 call = strip_expr(expr->right);
233 if (call->type != EXPR_CALL)
234 return;
235 if (param != -1)
236 return;
237 param = atoi(key);
238 offset = atoi(value);
239
240 arg = get_argument_from_call_expr(call->args, param);
241 if (!arg)
242 return;
243 if (arg->type != EXPR_SYMBOL)
244 return;
245 param = get_param_num(arg);
246 if (param < 0)
247 return;
248 snprintf(buf, sizeof(buf), "$(%d)", offset);
249 sql_insert_return_implies(CONTAINER, param, buf, "");
250 }
251
252 static int get_shared_cnt(const char *one, const char *two)
253 {
254 int i;
255 int on_end = false;
256
257 i = 0;
258 while (true) {
259 if (!one[i] || !two[i]) {
260 on_end = true;
261 break;
262 }
263 if (one[i] != two[i])
264 break;
265 i++;
266 }
267 if (i == 0)
268 return 0;
269 i--;
270 while (i > 0 && (one[i] == '>' || one[i] == '-' || one[i] == '.')) {
271 on_end = true;
272 i--;
273 }
274 if (!on_end)
275 return 0;
276
277 return i + 1;
278 }
279
280 static int build_offset_str(struct expression *expr, const char *name,
281 int shared, char *buf, int size, int op)
282 {
283 int chop = 0;
284 int offset;
285 int i;
286
287 i = shared;
288 while (name[i]) {
289 if (name[i] == '.' || name[i] == '-')
290 chop++;
291 i++;
292 }
293
294 // FIXME: Handle more chops
295 if (chop > 1)
296 return 0;
297
298 if (chop == 0) {
299 offset = 0;
300 } else {
301 offset = get_member_offset_from_deref(expr);
302 if (offset < 0)
303 return 0;
304 }
305
306 snprintf(buf, size, "%c%d", (op == '+') ? '+' : '-', offset);
307 return 1;
308 }
309
310 static void match_call(struct expression *call)
311 {
312 struct expression *fn, *arg;
313 char *fn_name, *arg_name;
314 int param, shared;
315 char minus_str[64];
316 char plus_str[64];
317 char offset_str[64];
318 bool star;
319
320 /*
321 * We're trying to link the function with the parameter. There are a
322 * couple ways this can be passed:
323 * foo->func(foo, ...);
324 * foo->func(foo->x, ...);
325 * foo->bar.func(&foo->bar, ...);
326 * foo->bar->baz->func(foo, ...);
327 *
328 * So the method is basically to subtract the offsets until we get to
329 * the common bit, then add the member offsets to get the parameter.
330 *
331 * If we're taking an address then the offset math is not stared,
332 * otherwise it is. Starred means dereferenced.
333 */
334 fn = strip_expr(call->fn);
335 fn_name = expr_to_var(fn);
336 if (!fn_name)
337 return;
338
339 param = -1;
340 FOR_EACH_PTR(call->args, arg) {
341 param++;
342
343 arg = strip_expr(arg);
344 star = true;
345 if (arg->type == EXPR_PREOP && arg->op == '&') {
346 arg = strip_expr(arg->unop);
347 star = false;
348 }
349
350 arg_name = expr_to_var(arg);
351 if (!arg_name)
352 continue;
353 shared = get_shared_cnt(fn_name, arg_name);
354 if (!shared)
355 goto free_arg_name;
356 if (!build_offset_str(fn, fn_name, shared, minus_str, sizeof(minus_str), '-'))
357 goto free_arg_name;
358 if (!build_offset_str(arg, arg_name, shared, plus_str, sizeof(plus_str), '+'))
359 goto free_arg_name;
360 if (star)
361 snprintf(offset_str, sizeof(offset_str), "*(%s%s)", minus_str, plus_str);
362 else
363 snprintf(offset_str, sizeof(offset_str), "%s%s", minus_str, plus_str);
364 sql_insert_caller_info(call, CONTAINER, param, offset_str, "$(-1)");
365 free_arg_name:
366 free_string(arg_name);
367 } END_FOR_EACH_PTR(arg);
368
369 free_string(fn_name);
370 }
371
372 static void db_passed_container(const char *name, struct symbol *sym, char *key, char *value)
373 {
374 sval_t offset = {
375 .type = &int_ctype,
376 };
377 const char *arg_offset;
378 int star = 0;
379 int val;
380
381 if (key[0] == '*') {
382 star = 1;
383 key += 2;
384 }
385
386 val = atoi(key);
387 if (val < -4095 || val > 0)
388 return;
389 offset.value = -val;
390 arg_offset = strchr(key, '+');
391 if (!arg_offset)
392 return;
393 val = atoi(arg_offset + 1);
394 if (val > 4095 || val < 0)
395 return;
396 offset.value |= val << 16;
397 if (star)
398 offset.value |= 1ULL << 31;
399
400 set_state(param_id, name, sym, alloc_estate_sval(offset));
401 }
402
403 struct db_info {
404 struct symbol *arg;
405 int prev_offset;
406 struct range_list *rl;
407 int star;
408 struct stree *stree;
409 };
410
411 static struct symbol *get_member_from_offset(struct symbol *sym, int offset)
412 {
413 struct symbol *type, *tmp;
414 int cur;
415
416 type = get_real_base_type(sym);
417 if (!type || type->type != SYM_PTR)
418 return NULL;
419 type = get_real_base_type(type);
420 if (!type || type->type != SYM_STRUCT)
421 return NULL;
422
423 cur = 0;
424 FOR_EACH_PTR(type->symbol_list, tmp) {
425 cur = ALIGN(cur, tmp->ctype.alignment);
426 if (offset == cur)
427 return tmp;
428 cur += type_bytes(tmp);
429 } END_FOR_EACH_PTR(tmp);
430 return NULL;
431 }
432
433 static struct symbol *get_member_type_from_offset(struct symbol *sym, int offset)
434 {
435 struct symbol *base_type;
436 struct symbol *member;
437
438 base_type = get_real_base_type(sym);
439 if (base_type && base_type->type == SYM_PTR)
440 base_type = get_real_base_type(base_type);
441 if (offset == 0 && base_type && base_type->type == SYM_BASETYPE)
442 return base_type;
443
444 member = get_member_from_offset(sym, offset);
445 if (!member)
446 return NULL;
447 return get_real_base_type(member);
448 }
449
450 static const char *get_name_from_offset(struct symbol *arg, int offset)
451 {
452 struct symbol *member, *type;
453 const char *name;
454 static char fullname[256];
455
456 name = arg->ident->name;
457
458 type = get_real_base_type(arg);
459 if (!type || type->type != SYM_PTR)
460 return name;
461
462 type = get_real_base_type(type);
463 if (!type)
464 return NULL;
465 if (type->type != SYM_STRUCT) {
466 snprintf(fullname, sizeof(fullname), "*%s", name);
467 return fullname;
468 }
469
470 member = get_member_from_offset(arg, offset);
471 if (!member)
472 return NULL;
473
474 snprintf(fullname, sizeof(fullname), "%s->%s", name, member->ident->name);
475 return fullname;
476 }
477
478 static void set_param_value(struct stree **stree, struct symbol *arg, int offset, struct range_list *rl)
479 {
480 const char *name;
481
482 name = get_name_from_offset(arg, offset);
483 if (!name)
484 return;
485 set_state_stree(stree, SMATCH_EXTRA, name, arg, alloc_estate_rl(rl));
486 }
487
488 static int save_vals(void *_db_info, int argc, char **argv, char **azColName)
489 {
490 struct db_info *db_info = _db_info;
491 struct symbol *type;
492 struct range_list *rl;
493 int offset = 0;
494 const char *value;
495
496 if (argc == 2) {
497 offset = atoi(argv[0]);
498 value = argv[1];
499 } else {
500 value = argv[0];
501 }
502
503 if (db_info->prev_offset != -1 &&
504 db_info->prev_offset != offset) {
505 set_param_value(&db_info->stree, db_info->arg, db_info->prev_offset, db_info->rl);
506 db_info->rl = NULL;
507 }
508
509 db_info->prev_offset = offset;
510
511 type = get_real_base_type(db_info->arg);
512 if (db_info->star)
513 goto found_type;
514 if (type->type != SYM_PTR)
515 return 0;
516 type = get_real_base_type(type);
517 if (type->type == SYM_BASETYPE)
518 goto found_type;
519 type = get_member_type_from_offset(db_info->arg, offset);
520 found_type:
521 str_to_rl(type, (char *)value, &rl);
522 if (db_info->rl)
523 db_info->rl = rl_union(db_info->rl, rl);
524 else
525 db_info->rl = rl;
526
527 return 0;
528 }
529
530 static struct stree *load_tag_info_sym(mtag_t tag, struct symbol *arg, int arg_offset, int star)
531 {
532 struct db_info db_info = {
533 .arg = arg,
534 .prev_offset = -1,
535 .star = star,
536 };
537 struct symbol *type;
538
539 if (!tag || !arg->ident)
540 return NULL;
541
542 type = get_real_base_type(arg);
543 if (!type)
544 return NULL;
545 if (!star) {
546 if (type->type != SYM_PTR)
547 return NULL;
548 type = get_real_base_type(type);
549 if (!type)
550 return NULL;
551 }
552
553 if (star || type->type == SYM_BASETYPE) {
554 run_sql(save_vals, &db_info,
555 "select value from mtag_data where tag = %lld and offset = %d and type = %d;",
556 tag, arg_offset, DATA_VALUE);
557 } else { /* presumably the parameter is a struct pointer */
558 run_sql(save_vals, &db_info,
559 "select offset, value from mtag_data where tag = %lld and type = %d;",
560 tag, DATA_VALUE);
561 }
562
563 if (db_info.prev_offset != -1)
564 set_param_value(&db_info.stree, arg, db_info.prev_offset, db_info.rl);
565
566 // FIXME: handle an offset correctly
567 if (!star && !arg_offset) {
568 sval_t sval;
569
570 sval.type = get_real_base_type(arg);
571 sval.uvalue = tag;
572 set_state_stree(&db_info.stree, SMATCH_EXTRA, arg->ident->name, arg, alloc_estate_sval(sval));
573 }
574 return db_info.stree;
575 }
576
577 static void handle_passed_container(struct symbol *sym)
578 {
579 struct symbol *arg;
580 struct smatch_state *state;
581 struct sm_state *sm;
582 struct stree *stree;
583 mtag_t fn_tag, container_tag, arg_tag;
584 sval_t offset;
585 int container_offset, arg_offset;
586 int star;
587
588 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
589 state = get_state(param_id, arg->ident->name, arg);
590 if (state)
591 goto found;
592 } END_FOR_EACH_PTR(arg);
593
594 return;
595 found:
596 if (!estate_get_single_value(state, &offset))
597 return;
598 container_offset = -(offset.value & 0xffff);
599 arg_offset = (offset.value & 0xfff0000) >> 16;
600 star = !!(offset.value & (1ULL << 31));
601
602 if (!get_toplevel_mtag(cur_func_sym, &fn_tag))
603 return;
604 if (!mtag_map_select_container(fn_tag, container_offset, &container_tag))
605 return;
606 if (!arg_offset || star) {
607 arg_tag = container_tag;
608 } else {
609 if (!mtag_map_select_tag(container_tag, -arg_offset, &arg_tag))
610 return;
611 }
612
613 stree = load_tag_info_sym(arg_tag, arg, arg_offset, star);
614 FOR_EACH_SM(stree, sm) {
615 set_state(sm->owner, sm->name, sm->sym, sm->state);
616 } END_FOR_EACH_SM(sm);
617 free_stree(&stree);
618 }
619
620 void register_container_of(int id)
621 {
622 my_id = id;
623
624 add_hook(&match_function_def, FUNC_DEF_HOOK);
625
626 add_get_state_hook(&get_state_hook);
627
628 add_hook(&match_save_states, INLINE_FN_START);
629 add_hook(&match_restore_states, INLINE_FN_END);
630
631 select_return_implies_hook(CONTAINER, &set_param_used);
632 all_return_states_hook(&process_states);
633
634 add_split_return_callback(&print_returns_container_of);
635 select_return_states_hook(CONTAINER, &returns_container_of);
636
637 add_hook(&match_call, FUNCTION_CALL_HOOK);
638 }
639
640 static struct smatch_state *unmatched_state(struct sm_state *sm)
641 {
642 return alloc_estate_whole(estate_type(sm->state));
643 }
644
645 void register_container_of2(int id)
646 {
647 param_id = id;
648
649 select_caller_info_hook(db_passed_container, CONTAINER);
650 add_hook(&handle_passed_container, AFTER_DEF_HOOK);
651 add_unmatched_state_hook(param_id, &unmatched_state);
652 add_merge_hook(param_id, &merge_estates);
653 }
654