1 /*
2 * Copyright (C) 2014 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 * This file started out by saying that if you have:
20 *
21 * struct foo one, two;
22 * ...
23 * one = two;
24 *
25 * That's equivalent to saying:
26 *
27 * one.x = two.x;
28 * one.y = two.y;
29 *
30 * Turning an assignment like that into a bunch of small fake assignments is
31 * really useful.
32 *
33 * The call to memcpy(&one, &two, sizeof(foo)); is the same as "one = two;" so
34 * we can re-use the code. And we may as well use it for memset() too.
35 * Assigning pointers is almost the same:
36 *
37 * p1 = p2;
38 *
39 * Is the same as:
40 *
41 * p1->x = p2->x;
42 * p1->y = p2->y;
43 *
44 * The problem is that you can go a bit crazy with pointers to pointers.
45 *
46 * p1->x->y->z->one->two->three = p2->x->y->z->one->two->three;
47 *
48 * I don't have a proper solution for this problem right now. I just copy one
49 * level and don't nest. It should handle limitted nesting but intelligently.
50 *
51 * The other thing is that you end up with a lot of garbage assignments where
52 * we record "x could be anything. x->y could be anything. x->y->z->a->b->c
53 * could *also* be anything!". There should be a better way to filter this
54 * useless information.
55 *
56 */
57
58 #include "scope.h"
59 #include "smatch.h"
60 #include "smatch_slist.h"
61 #include "smatch_extra.h"
62
63 enum {
64 COPY_NORMAL,
65 COPY_MEMCPY,
66 COPY_MEMSET,
67 };
68
69 static struct symbol *get_struct_type(struct expression *expr)
70 {
71 struct symbol *type;
72
73 type = get_type(expr);
74 if (!type)
75 return NULL;
76 if (type->type == SYM_PTR) {
77 type = get_real_base_type(type);
78 if (!type)
79 return NULL;
80 }
81 if (type->type == SYM_STRUCT)
82 return type;
83 if (type->type == SYM_UNION)
84 return type;
85 return NULL;
86 }
87
88 static struct expression *get_right_base_expr(struct symbol *left_type, struct expression *right)
89 {
90 struct symbol *struct_type;
91
92 if (!right)
93 return NULL;
94
95 struct_type = get_struct_type(right);
96 if (!struct_type)
97 return NULL;
98 if (struct_type != left_type)
99 return NULL;
100
101 if (right->type == EXPR_PREOP && right->op == '&')
102 right = strip_expr(right->unop);
103
104 if (right->type == EXPR_CALL)
105 return NULL;
106
107 if (is_pointer(right))
108 right = deref_expression(right);
109
110 return right;
111 }
112
113 static struct expression *remove_addr(struct expression *expr)
114 {
115 struct symbol *type;
116
117 expr = strip_expr(expr);
118 if (!expr)
119 return NULL;
120
121 if (expr->type == EXPR_PREOP && expr->op == '&')
122 return strip_expr(expr->unop);
123 type = get_type(expr);
124 if (!type)
125 return expr;
126 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
127 return expr;
128
129 return deref_expression(expr);
130 }
131
132 static struct expression *faked_expression;
133 struct expression *get_faked_expression(void)
134 {
135 if (!__in_fake_assign)
136 return NULL;
137 return faked_expression;
138 }
139
140 static void split_fake_expr(struct expression *expr)
141 {
142 __in_fake_assign++;
143 __in_fake_struct_assign++;
144 __split_expr(expr);
145 __in_fake_struct_assign--;
146 __in_fake_assign--;
147 }
148
149 static void handle_non_struct_assignments(struct expression *left, struct expression *right)
150 {
151 struct symbol *type;
152 struct expression *assign;
153
154 type = get_type(left);
155 if (!type)
156 return;
157 if (type->type == SYM_PTR) {
158 left = deref_expression(left);
159 if (right)
160 right = deref_expression(right);
161 else
162 right = unknown_value_expression(left);
163 assign = assign_expression(left, '=', right);
164 split_fake_expr(assign);
165 return;
166 }
167 if (type->type != SYM_BASETYPE)
168 return;
169 right = strip_expr(right);
170 if (!right)
171 right = unknown_value_expression(left);
172 assign = assign_expression(left, '=', right);
173 split_fake_expr(assign);
174 }
175
176 static void set_inner_struct_members(int mode, struct expression *faked, struct expression *left, struct expression *right, struct symbol *member)
177 {
178 struct expression *left_member;
179 struct expression *right_member = NULL; /* silence GCC */
180 struct expression *assign;
181 struct symbol *base = get_real_base_type(member);
182 struct symbol *tmp;
183
184 if (member->ident) {
185 left = member_expression(left, '.', member->ident);
186 if (mode != COPY_MEMSET && right)
187 right = member_expression(right, '.', member->ident);
188 }
189
190 FOR_EACH_PTR(base->symbol_list, tmp) {
191 struct symbol *type;
192
193 type = get_real_base_type(tmp);
194 if (!type)
195 continue;
196
197 if (type->type == SYM_ARRAY)
198 continue;
199 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
200 set_inner_struct_members(mode, faked, left, right, tmp);
201 continue;
202 }
203 if (!tmp->ident)
204 continue;
205
206 left_member = member_expression(left, '.', tmp->ident);
207
208 switch (mode) {
209 case COPY_NORMAL:
210 case COPY_MEMCPY:
211 if (right)
212 right_member = member_expression(right, '.', tmp->ident);
213 else
214 right_member = unknown_value_expression(left_member);
215 break;
216 case COPY_MEMSET:
217 right_member = right;
218 break;
219 }
220
221 assign = assign_expression(left_member, '=', right_member);
222 split_fake_expr(assign);
223 } END_FOR_EACH_PTR(tmp);
224 }
225
226 static void __struct_members_copy(int mode, struct expression *faked,
227 struct expression *left,
228 struct expression *right)
229 {
230 struct symbol *struct_type, *tmp, *type;
231 struct expression *left_member;
232 struct expression *right_member;
233 struct expression *assign;
234 int op = '.';
235
236
237 if (__in_fake_assign)
238 return;
239 faked_expression = faked;
240
241 left = strip_expr(left);
242 right = strip_expr(right);
243
244 struct_type = get_struct_type(left);
245 if (!struct_type) {
246 /*
247 * This is not a struct assignment obviously. But this is where
248 * memcpy() is handled so it feels like a good place to add this
249 * code.
250 */
251 handle_non_struct_assignments(left, right);
252 goto done;
253 }
254
255 if (is_pointer(left)) {
256 left = deref_expression(left);
257 op = '*';
258 }
259 if (mode != COPY_MEMSET)
260 right = get_right_base_expr(struct_type, right);
261
262 FOR_EACH_PTR(struct_type->symbol_list, tmp) {
263 type = get_real_base_type(tmp);
264 if (!type)
265 continue;
266 if (type->type == SYM_ARRAY)
267 continue;
268
269 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
270 set_inner_struct_members(mode, faked, left, right, tmp);
271 continue;
272 }
273
274 if (!tmp->ident)
275 continue;
276
277 left_member = member_expression(left, op, tmp->ident);
278 right_member = NULL;
279
280 switch (mode) {
281 case COPY_NORMAL:
282 case COPY_MEMCPY:
283 if (right)
284 right_member = member_expression(right, op, tmp->ident);
285 else
286 right_member = unknown_value_expression(left_member);
287 break;
288 case COPY_MEMSET:
289 right_member = right;
290 break;
291 }
292 if (!right_member) {
293 sm_perror("No right member");
294 continue;
295 }
296 assign = assign_expression(left_member, '=', right_member);
297 split_fake_expr(assign);
298 } END_FOR_EACH_PTR(tmp);
299
300 done:
301 faked_expression = NULL;
302 }
303
304 static int returns_zeroed_mem(struct expression *expr)
305 {
306 char *fn;
307
308 if (expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL)
309 return 0;
310 fn = expr_to_var(expr->fn);
311 if (!fn)
312 return 0;
313 if (strcmp(fn, "kcalloc") == 0)
314 return 1;
315 if (option_project == PROJ_KERNEL && strstr(fn, "zalloc"))
316 return 1;
317 return 0;
318 }
319
320 static int copy_containter_states(struct expression *left, struct expression *right, int offset)
321 {
322 char *left_name = NULL, *right_name = NULL;
323 struct symbol *left_sym, *right_sym;
324 struct sm_state *sm, *new_sm;
325 int ret = 0;
326 int len;
327 char buf[64];
328 char new_name[128];
329
330 right_name = expr_to_var_sym(right, &right_sym);
331 if (!right_name || !right_sym)
332 goto free;
333 left_name = expr_to_var_sym(left, &left_sym);
334 if (!left_name || !left_sym)
335 goto free;
336
337 len = snprintf(buf, sizeof(buf), "%s(-%d)", right_name, offset);
338 if (len >= sizeof(buf))
339 goto free;
340
341 FOR_EACH_SM(__get_cur_stree(), sm) {
342 if (sm->sym != right_sym)
343 continue;
344 if (strncmp(sm->name, buf, len) != 0)
345 continue;
346 snprintf(new_name, sizeof(new_name), "%s%s", left_name, sm->name + len);
347 new_sm = clone_sm(sm);
348 new_sm->name = alloc_sname(new_name);
349 new_sm->sym = left_sym;
350 __set_sm(new_sm);
351 ret = 1;
352 } END_FOR_EACH_SM(sm);
353 free:
354 free_string(left_name);
355 free_string(right_name);
356 return ret;
357 }
358
359 static int handle_param_offsets(struct expression *expr)
360 {
361 struct expression *right;
362 sval_t sval;
363
364 right = strip_expr(expr->right);
365
366 if (right->type != EXPR_BINOP || right->op != '-')
367 return 0;
368
369 if (!get_value(right->right, &sval))
370 return 0;
371
372 right = get_assigned_expr(right->left);
373 if (!right)
374 return 0;
375 return copy_containter_states(expr->left, right, sval.value);
376 }
377
378 static void returns_container_of(struct expression *expr, int param, char *key, char *value)
379 {
380 struct expression *call, *arg;
381 int offset;
382
383 if (expr->type != EXPR_ASSIGNMENT || expr->op != '=')
384 return;
385 call = strip_expr(expr->right);
386 if (call->type != EXPR_CALL)
387 return;
388 if (param != -1)
389 return;
390 param = atoi(key);
391 offset = atoi(value);
392
393 arg = get_argument_from_call_expr(call->args, param);
394 if (!arg)
395 return;
396
397 copy_containter_states(expr->left, arg, -offset);
398 }
399
400 void __fake_struct_member_assignments(struct expression *expr)
401 {
402 struct symbol *left_type;
403
404 if (expr->op != '=')
405 return;
406
407 if (is_zero(expr->right))
408 return;
409
410 left_type = get_type(expr->left);
411 if (!left_type ||
412 (left_type->type != SYM_PTR &&
413 left_type->type != SYM_STRUCT))
414 return;
415
416 if (handle_param_offsets(expr))
417 return;
418
419 if (returns_zeroed_mem(expr->right))
420 __struct_members_copy(COPY_MEMSET, expr, expr->left, zero_expr());
421 else
422 __struct_members_copy(COPY_NORMAL, expr, expr->left, expr->right);
423 }
424
425 static void match_memset(const char *fn, struct expression *expr, void *_size_arg)
426 {
427 struct expression *buf;
428 struct expression *val;
429
430 buf = get_argument_from_call_expr(expr->args, 0);
431 val = get_argument_from_call_expr(expr->args, 1);
432
433 buf = strip_expr(buf);
434 __struct_members_copy(COPY_MEMSET, expr, remove_addr(buf), val);
435 }
436
437 static void match_memcpy(const char *fn, struct expression *expr, void *_arg)
438 {
439 struct expression *dest;
440 struct expression *src;
441
442 dest = get_argument_from_call_expr(expr->args, 0);
443 src = get_argument_from_call_expr(expr->args, 1);
444
445 __struct_members_copy(COPY_MEMCPY, expr, remove_addr(dest), remove_addr(src));
446 }
447
448 static void match_memcpy_unknown(const char *fn, struct expression *expr, void *_arg)
449 {
450 struct expression *dest;
451
452 dest = get_argument_from_call_expr(expr->args, 0);
453 __struct_members_copy(COPY_MEMCPY, expr, remove_addr(dest), NULL);
454 }
455
456 static void match_sscanf(const char *fn, struct expression *expr, void *unused)
457 {
458 struct expression *arg;
459 int i;
460
461 i = -1;
462 FOR_EACH_PTR(expr->args, arg) {
463 if (++i < 2)
464 continue;
465 __struct_members_copy(COPY_MEMCPY, expr, remove_addr(arg), NULL);
466 } END_FOR_EACH_PTR(arg);
467 }
468
469 static void unop_expr(struct expression *expr)
470 {
471 if (expr->op != SPECIAL_INCREMENT &&
472 expr->op != SPECIAL_DECREMENT)
473 return;
474
475 if (!is_pointer(expr))
476 return;
477 faked_expression = expr;
478 __struct_members_copy(COPY_MEMCPY, expr, expr->unop, NULL);
479 faked_expression = NULL;
480 }
481
482 static void register_clears_param(void)
483 {
484 struct token *token;
485 char name[256];
486 const char *function;
487 int param;
488
489 if (option_project == PROJ_NONE)
490 return;
491
492 snprintf(name, 256, "%s.clears_argument", option_project_str);
493
494 token = get_tokens_file(name);
495 if (!token)
496 return;
497 if (token_type(token) != TOKEN_STREAMBEGIN)
498 return;
499 token = token->next;
500 while (token_type(token) != TOKEN_STREAMEND) {
501 if (token_type(token) != TOKEN_IDENT)
502 return;
503 function = show_ident(token->ident);
504 token = token->next;
505 if (token_type(token) != TOKEN_NUMBER)
506 return;
507 param = atoi(token->number);
508 add_function_hook(function, &match_memcpy_unknown, INT_PTR(param));
509 token = token->next;
510 }
511 clear_token_alloc();
512 }
513
514 static void db_param_cleared(struct expression *expr, int param, char *key, char *value)
515 {
516 struct expression *arg;
517
518 while (expr->type == EXPR_ASSIGNMENT)
519 expr = strip_expr(expr->right);
520 if (expr->type != EXPR_CALL)
521 return;
522
523 /*
524 * FIXME: __struct_members_copy() requires an expression but
525 * get_variable_from_key() returns a name/sym pair so that doesn't
526 * work here.
527 */
528 if (strcmp(key, "$") != 0)
529 return;
530
531 arg = get_argument_from_call_expr(expr->args, param);
532 if (!arg)
533 return;
534
535 if (strcmp(value, "0") == 0)
536 __struct_members_copy(COPY_MEMSET, expr, remove_addr(arg), zero_expr());
537 else
538 __struct_members_copy(COPY_MEMCPY, expr, remove_addr(arg), NULL);
539 }
540
541 void register_struct_assignment(int id)
542 {
543 add_function_hook("memset", &match_memset, NULL);
544 add_function_hook("__memset", &match_memset, NULL);
545
546 add_function_hook("memcpy", &match_memcpy, INT_PTR(0));
547 add_function_hook("memmove", &match_memcpy, INT_PTR(0));
548 add_function_hook("__memcpy", &match_memcpy, INT_PTR(0));
549 add_function_hook("__memmove", &match_memcpy, INT_PTR(0));
550
551 add_function_hook("sscanf", &match_sscanf, NULL);
552
553 add_hook(&unop_expr, OP_HOOK);
554 register_clears_param();
555 select_return_states_hook(PARAM_CLEARED, &db_param_cleared);
556
557 select_return_states_hook(CONTAINER, &returns_container_of);
558 }