1 /*
2 * Copyright (C) 2012 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
24 struct {
25 const char *func;
26 int param;
27 } alloc_functions[] = {
28 {"kmalloc", 0},
29 {"kzalloc", 0},
30 {"__kmalloc", 0},
31 {"vmalloc", 0},
32 {"__vmalloc", 0},
33 {"__vmalloc_node", 0},
34 };
35
36 static struct range_list_stack *rl_stack;
37 static struct string_list *op_list;
38
39 static void push_op(char c)
40 {
41 char *p;
42
43 p = malloc(1);
44 p[0] = c;
45 add_ptr_list(&op_list, p);
46 }
47
48 static char pop_op(void)
49 {
50 char *p;
51 char c;
52
53 if (!op_list) {
54 sm_perror("%s: no op_list", __func__);
55 return '\0';
56 }
57
58 p = last_ptr_list((struct ptr_list *)op_list);
59
60 delete_ptr_list_last((struct ptr_list **)&op_list);
61 c = p[0];
62 free(p);
63
64 return c;
65 }
66
67 static int op_precedence(char c)
68 {
69 switch (c) {
70 case '+':
71 case '-':
72 return 1;
73 case '*':
74 case '/':
75 return 2;
76 default:
77 return 0;
78 }
79 }
80
81 static int top_op_precedence(void)
82 {
83 char *p;
84
85 if (!op_list)
86 return 0;
87
88 p = last_ptr_list((struct ptr_list *)op_list);
89 return op_precedence(p[0]);
90 }
91
92 static void rl_pop_until(char c)
93 {
94 char op;
95 struct range_list *left, *right;
96 struct range_list *res;
97
98 while (top_op_precedence() && op_precedence(c) <= top_op_precedence()) {
99 op = pop_op();
100 right = pop_rl(&rl_stack);
101 left = pop_rl(&rl_stack);
102 res = rl_binop(left, op, right);
103 if (!res)
104 res = alloc_whole_rl(&llong_ctype);
105 push_rl(&rl_stack, res);
106 }
107 }
108
109 static void rl_discard_stacks(void)
110 {
111 while (op_list)
112 pop_op();
113 while (rl_stack)
114 pop_rl(&rl_stack);
115 }
116
117 static int read_rl_from_var(struct expression *call, char *p, char **end, struct range_list **rl)
118 {
119 struct expression *arg;
120 struct smatch_state *state;
121 long param;
122 char *name;
123 struct symbol *sym;
124 char buf[256];
125 int star;
126
127 p++;
128 param = strtol(p, &p, 10);
129
130 arg = get_argument_from_call_expr(call->args, param);
131 if (!arg)
132 return 0;
133
134 if (*p != '-' && *p != '.') {
135 get_absolute_rl(arg, rl);
136 *end = p;
137 return 1;
138 }
139
140 *end = strchr(p, ' ');
141
142 if (arg->type == EXPR_PREOP && arg->op == '&') {
143 arg = strip_expr(arg->unop);
144 star = 0;
145 p++;
146 } else {
147 star = 1;
148 p += 2;
149 }
150
151 name = expr_to_var_sym(arg, &sym);
152 if (!name)
153 return 0;
154 snprintf(buf, sizeof(buf), "%s%s", name, star ? "->" : ".");
155 free_string(name);
156
157 if (*end - p + strlen(buf) >= sizeof(buf))
158 return 0;
159 strncat(buf, p, *end - p);
160
161 state = get_state(SMATCH_EXTRA, buf, sym);
162 if (!state)
163 return 0;
164 *rl = estate_rl(state);
165 return 1;
166 }
167
168 static int read_var_num(struct expression *call, char *p, char **end, struct range_list **rl)
169 {
170 sval_t sval;
171
172 while (*p == ' ')
173 p++;
174
175 if (*p == '$')
176 return read_rl_from_var(call, p, end, rl);
177
178 sval.type = &llong_ctype;
179 sval.value = strtoll(p, end, 10);
180 if (*end == p)
181 return 0;
182 *rl = alloc_rl(sval, sval);
183 return 1;
184 }
185
186 static char *read_op(char *p)
187 {
188 while (*p == ' ')
189 p++;
190
191 switch (*p) {
192 case '+':
193 case '-':
194 case '*':
195 case '/':
196 return p;
197 default:
198 return NULL;
199 }
200 }
201
202 int parse_call_math_rl(struct expression *call, char *math, struct range_list **rl)
203 {
204 struct range_list *tmp;
205 char *c;
206
207 /* try to implement shunting yard algorithm. */
208
209 c = (char *)math;
210 while (1) {
211 if (option_debug)
212 sm_msg("parsing %s", c);
213
214 /* read a number and push it onto the number stack */
215 if (!read_var_num(call, c, &c, &tmp))
216 goto fail;
217 push_rl(&rl_stack, tmp);
218
219 if (option_debug)
220 sm_msg("val = %s remaining = %s", show_rl(tmp), c);
221
222 if (!*c)
223 break;
224 if (*c == ']' && *(c + 1) == '\0')
225 break;
226
227 c = read_op(c);
228 if (!c)
229 goto fail;
230
231 if (option_debug)
232 sm_msg("op = %c remaining = %s", *c, c);
233
234 rl_pop_until(*c);
235 push_op(*c);
236 c++;
237 }
238
239 rl_pop_until(0);
240 *rl = pop_rl(&rl_stack);
241 return 1;
242 fail:
243 rl_discard_stacks();
244 return 0;
245 }
246
247 int parse_call_math(struct expression *call, char *math, sval_t *sval)
248 {
249 struct range_list *rl;
250
251 if (!parse_call_math_rl(call, math, &rl))
252 return 0;
253 if (!rl_to_sval(rl, sval))
254 return 0;
255 return 1;
256 }
257
258 static struct smatch_state *alloc_state_sname(char *sname)
259 {
260 struct smatch_state *state;
261
262 state = __alloc_smatch_state(0);
263 state->name = sname;
264 state->data = INT_PTR(1);
265 return state;
266 }
267
268 static int get_arg_number(struct expression *expr)
269 {
270 struct symbol *sym;
271 struct symbol *arg;
272 int i;
273
274 expr = strip_expr(expr);
275 if (expr->type != EXPR_SYMBOL)
276 return -1;
277 sym = expr->symbol;
278
279 i = 0;
280 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
281 if (arg == sym)
282 return i;
283 i++;
284 } END_FOR_EACH_PTR(arg);
285
286 return -1;
287 }
288
289 static int format_name_sym_helper(char *buf, int remaining, char *name, struct symbol *sym)
290 {
291 int ret = 0;
292 int arg;
293 char *param_name;
294 int name_len;
295
296 if (!name || !sym || !sym->ident)
297 goto free;
298 arg = get_param_num_from_sym(sym);
299 if (arg < 0)
300 goto free;
301 if (param_was_set_var_sym(name, sym))
302 goto free;
303
304 param_name = sym->ident->name;
305 name_len = strlen(param_name);
306
307 if (name[name_len] == '\0')
308 ret = snprintf(buf, remaining, "$%d", arg);
309 else if (name[name_len] == '-')
310 ret = snprintf(buf, remaining, "$%d%s", arg, name + name_len);
311 else
312 goto free;
313
314 remaining -= ret;
315 if (remaining <= 0)
316 ret = 0;
317
318 free:
319 free_string(name);
320
321 return ret;
322
323 }
324
325 static int format_variable_helper(char *buf, int remaining, struct expression *expr)
326 {
327 char *name;
328 struct symbol *sym;
329
330 name = expr_to_var_sym(expr, &sym);
331 if (param_was_set_var_sym(name, sym))
332 return 0;
333 return format_name_sym_helper(buf, remaining, name, sym);
334 }
335
336 static int format_call_to_param_mapping(char *buf, int remaining, struct expression *expr)
337 {
338 char *name;
339 struct symbol *sym;
340
341 name = map_call_to_param_name_sym(expr, &sym);
342 if (param_was_set_var_sym(name, sym))
343 return 0;
344 return format_name_sym_helper(buf, remaining, name, sym);
345 }
346
347 static int format_expr_helper(char *buf, int remaining, struct expression *expr)
348 {
349 sval_t sval;
350 int ret;
351 char *cur;
352
353 if (!expr)
354 return 0;
355
356 cur = buf;
357
358 if (expr->type == EXPR_BINOP) {
359 ret = format_expr_helper(cur, remaining, expr->left);
360 if (ret == 0)
361 return 0;
362 remaining -= ret;
363 if (remaining <= 0)
364 return 0;
365 cur += ret;
366
367 ret = snprintf(cur, remaining, " %s ", show_special(expr->op));
368 remaining -= ret;
369 if (remaining <= 0)
370 return 0;
371 cur += ret;
372
373 ret = format_expr_helper(cur, remaining, expr->right);
374 if (ret == 0)
375 return 0;
376 remaining -= ret;
377 if (remaining <= 0)
378 return 0;
379 cur += ret;
380 return cur - buf;
381 }
382
383 if (get_implied_value(expr, &sval)) {
384 ret = snprintf(cur, remaining, "%s", sval_to_str(sval));
385 remaining -= ret;
386 if (remaining <= 0)
387 return 0;
388 return ret;
389 }
390
391 if (expr->type == EXPR_CALL)
392 return format_call_to_param_mapping(cur, remaining, expr);
393
394 return format_variable_helper(cur, remaining, expr);
395 }
396
397 static char *format_expr(struct expression *expr)
398 {
399 char buf[256] = "";
400 int ret;
401
402 ret = format_expr_helper(buf, sizeof(buf), expr);
403 if (ret == 0)
404 return NULL;
405
406 return alloc_sname(buf);
407 }
408
409 char *get_value_in_terms_of_parameter_math(struct expression *expr)
410 {
411 struct expression *tmp;
412 char buf[256] = "";
413 sval_t dummy;
414 int ret;
415
416 tmp = get_assigned_expr(expr);
417 if (tmp)
418 expr = tmp;
419 if (param_was_set(expr))
420 return NULL;
421
422 if (get_implied_value(expr, &dummy))
423 return NULL;
424
425 ret = format_expr_helper(buf, sizeof(buf), expr);
426 if (ret == 0)
427 return NULL;
428
429 return alloc_sname(buf);
430 }
431
432 char *get_value_in_terms_of_parameter_math_var_sym(const char *name, struct symbol *sym)
433 {
434 struct expression *tmp, *expr;
435 char buf[256] = "";
436 int ret;
437 int cnt = 0;
438
439 expr = get_assigned_expr_name_sym(name, sym);
440 if (!expr)
441 return NULL;
442 while ((tmp = get_assigned_expr(expr))) {
443 expr = strip_expr(tmp);
444 if (++cnt > 3)
445 break;
446 }
447
448 ret = format_expr_helper(buf, sizeof(buf), expr);
449 if (ret == 0)
450 return NULL;
451
452 return alloc_sname(buf);
453
454 }
455
456 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
457 {
458 int size_arg = PTR_INT(_size_arg);
459 struct expression *right;
460 struct expression *size_expr;
461 char *sname;
462
463 right = strip_expr(expr->right);
464 size_expr = get_argument_from_call_expr(right->args, size_arg);
465
466 sname = format_expr(size_expr);
467 if (!sname)
468 return;
469 set_state_expr(my_id, expr->left, alloc_state_sname(sname));
470 }
471
472 static char *swap_format(struct expression *call, char *format)
473 {
474 char buf[256];
475 sval_t sval;
476 long param;
477 struct expression *arg;
478 char *p;
479 char *out;
480 int ret;
481
482 if (format[0] == '$' && format[2] == '\0') {
483 param = strtol(format + 1, NULL, 10);
484 arg = get_argument_from_call_expr(call->args, param);
485 if (!arg)
486 return NULL;
487 return format_expr(arg);
488 }
489
490 buf[0] = '\0';
491 p = format;
492 out = buf;
493 while (*p) {
494 if (*p == '$') {
495 p++;
496 param = strtol(p, &p, 10);
497 arg = get_argument_from_call_expr(call->args, param);
498 if (!arg)
499 return NULL;
500 param = get_arg_number(arg);
501 if (param >= 0) {
502 ret = snprintf(out, buf + sizeof(buf) - out, "$%ld", param);
503 out += ret;
504 if (out >= buf + sizeof(buf))
505 return NULL;
506 } else if (get_implied_value(arg, &sval)) {
507 ret = snprintf(out, buf + sizeof(buf) - out, "%s", sval_to_str(sval));
508 out += ret;
509 if (out >= buf + sizeof(buf))
510 return NULL;
511 } else {
512 return NULL;
513 }
514 }
515 *out = *p;
516 p++;
517 out++;
518 }
519 if (buf[0] == '\0')
520 return NULL;
521 *out = '\0';
522 return alloc_sname(buf);
523 }
524
525 static char *buf_size_recipe;
526 static int db_buf_size_callback(void *unused, int argc, char **argv, char **azColName)
527 {
528 if (argc != 1)
529 return 0;
530
531 if (!buf_size_recipe)
532 buf_size_recipe = alloc_sname(argv[0]);
533 else if (strcmp(buf_size_recipe, argv[0]) != 0)
534 buf_size_recipe = alloc_sname("invalid");
535 return 0;
536 }
537
538 static char *get_allocation_recipe_from_call(struct expression *expr)
539 {
540 struct symbol *sym;
541 static char sql_filter[1024];
542 int i;
543
544 if (is_fake_call(expr))
545 return NULL;
546 expr = strip_expr(expr);
547 if (expr->fn->type != EXPR_SYMBOL)
548 return NULL;
549 sym = expr->fn->symbol;
550 if (!sym)
551 return NULL;
552
553 for (i = 0; i < ARRAY_SIZE(alloc_functions); i++) {
554 if (strcmp(sym->ident->name, alloc_functions[i].func) == 0) {
555 char buf[32];
556
557 snprintf(buf, sizeof(buf), "$%d", alloc_functions[i].param);
558 buf_size_recipe = alloc_sname(buf);
559 return swap_format(expr, buf_size_recipe);
560 }
561 }
562
563 if (sym->ctype.modifiers & MOD_STATIC) {
564 snprintf(sql_filter, 1024, "file = '%s' and function = '%s';",
565 get_filename(), sym->ident->name);
566 } else {
567 snprintf(sql_filter, 1024, "function = '%s' and static = 0;",
568 sym->ident->name);
569 }
570
571 buf_size_recipe = NULL;
572 run_sql(db_buf_size_callback, NULL,
573 "select value from return_states where type=%d and %s",
574 BUF_SIZE, sql_filter);
575 if (!buf_size_recipe || strcmp(buf_size_recipe, "invalid") == 0)
576 return NULL;
577 return swap_format(expr, buf_size_recipe);
578 }
579
580 static void match_call_assignment(struct expression *expr)
581 {
582 char *sname;
583
584 sname = get_allocation_recipe_from_call(expr->right);
585 if (!sname)
586 return;
587 set_state_expr(my_id, expr->left, alloc_state_sname(sname));
588 }
589
590 static void match_returns_call(int return_id, char *return_ranges, struct expression *call)
591 {
592 char *sname;
593
594 sname = get_allocation_recipe_from_call(call);
595 if (option_debug)
596 sm_msg("sname = %s", sname);
597 if (!sname)
598 return;
599
600 sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "",
601 sname);
602 }
603
604 static void print_returned_allocations(int return_id, char *return_ranges, struct expression *expr)
605 {
606 struct expression *tmp;
607 struct smatch_state *state;
608 struct symbol *sym;
609 char *name;
610 int cnt = 0;
611
612 expr = strip_expr(expr);
613 while ((tmp = get_assigned_expr(expr))) {
614 if (cnt++ > 5) /* assignments to self cause infinite loops */
615 break;
616 expr = strip_expr(tmp);
617 }
618 if (!expr)
619 return;
620
621 if (expr->type == EXPR_CALL) {
622 match_returns_call(return_id, return_ranges, expr);
623 return;
624 }
625
626 name = expr_to_var_sym(expr, &sym);
627 if (!name || !sym)
628 goto free;
629
630 state = get_state(my_id, name, sym);
631 if (!state || !state->data)
632 goto free;
633
634 sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "",
635 state->name);
636 free:
637 free_string(name);
638 }
639
640 void register_parse_call_math(int id)
641 {
642 int i;
643
644 my_id = id;
645
646 for (i = 0; i < ARRAY_SIZE(alloc_functions); i++)
647 add_function_assign_hook(alloc_functions[i].func, &match_alloc,
648 INT_PTR(alloc_functions[i].param));
649 add_hook(&match_call_assignment, CALL_ASSIGNMENT_HOOK);
650 add_split_return_callback(print_returned_allocations);
651 }
652