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
push_op(char c)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
pop_op(void)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
op_precedence(char c)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
top_op_precedence(void)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
rl_pop_until(char c)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
rl_discard_stacks(void)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
read_rl_from_var(struct expression * call,const char * p,const char ** end,struct range_list ** rl)117 static int read_rl_from_var(struct expression *call, const char *p, const 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, (char **)&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
read_var_num(struct expression * call,const char * p,const char ** end,struct range_list ** rl)168 static int read_var_num(struct expression *call, const char *p, const 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, (char **)end, 10);
180 if (*end == p)
181 return 0;
182 *rl = alloc_rl(sval, sval);
183 return 1;
184 }
185
read_op(const char * p)186 static const char *read_op(const 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
parse_call_math_rl(struct expression * call,const char * math,struct range_list ** rl)202 int parse_call_math_rl(struct expression *call, const char *math, struct range_list **rl)
203 {
204 struct range_list *tmp;
205 const char *c;
206
207 /* try to implement shunting yard algorithm. */
208
209 c = 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
parse_call_math(struct expression * call,char * math,sval_t * sval)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
alloc_state_sname(char * sname)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
get_arg_number(struct expression * expr)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
format_name_sym_helper(char * buf,int remaining,char * name,struct symbol * sym)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
format_variable_helper(char * buf,int remaining,struct expression * expr)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
format_call_to_param_mapping(char * buf,int remaining,struct expression * expr)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
is_mtag_sval(sval_t sval)347 static int is_mtag_sval(sval_t sval)
348 {
349 if (!is_ptr_type(sval.type))
350 return 0;
351 if (sval_cmp(sval, valid_ptr_min_sval) >= 0 &&
352 sval_cmp(sval, valid_ptr_max_sval) <= 0)
353 return 1;
354 return 0;
355 }
356
format_expr_helper(char * buf,int remaining,struct expression * expr)357 static int format_expr_helper(char *buf, int remaining, struct expression *expr)
358 {
359 sval_t sval;
360 int ret;
361 char *cur;
362
363 if (!expr)
364 return 0;
365
366 cur = buf;
367
368 if (expr->type == EXPR_BINOP) {
369 ret = format_expr_helper(cur, remaining, expr->left);
370 if (ret == 0)
371 return 0;
372 remaining -= ret;
373 if (remaining <= 0)
374 return 0;
375 cur += ret;
376
377 ret = snprintf(cur, remaining, " %s ", show_special(expr->op));
378 remaining -= ret;
379 if (remaining <= 0)
380 return 0;
381 cur += ret;
382
383 ret = format_expr_helper(cur, remaining, expr->right);
384 if (ret == 0)
385 return 0;
386 remaining -= ret;
387 if (remaining <= 0)
388 return 0;
389 cur += ret;
390 return cur - buf;
391 }
392
393 if (!param_was_set(expr) && get_implied_value(expr, &sval) && !is_mtag_sval(sval)) {
394 ret = snprintf(cur, remaining, "%s", sval_to_str(sval));
395 remaining -= ret;
396 if (remaining <= 0)
397 return 0;
398 return ret;
399 }
400
401 if (expr->type == EXPR_CALL)
402 return format_call_to_param_mapping(cur, remaining, expr);
403
404 return format_variable_helper(cur, remaining, expr);
405 }
406
format_expr(struct expression * expr)407 static char *format_expr(struct expression *expr)
408 {
409 char buf[256] = "";
410 int ret;
411
412 ret = format_expr_helper(buf, sizeof(buf), expr);
413 if (ret == 0)
414 return NULL;
415
416 return alloc_sname(buf);
417 }
418
get_value_in_terms_of_parameter_math(struct expression * expr)419 char *get_value_in_terms_of_parameter_math(struct expression *expr)
420 {
421 struct expression *tmp;
422 char buf[256] = "";
423 sval_t dummy;
424 int ret;
425
426 tmp = get_assigned_expr(expr);
427 if (tmp)
428 expr = tmp;
429 if (param_was_set(expr))
430 return NULL;
431
432 if (get_implied_value(expr, &dummy))
433 return NULL;
434
435 ret = format_expr_helper(buf, sizeof(buf), expr);
436 if (ret == 0)
437 return NULL;
438
439 return alloc_sname(buf);
440 }
441
get_value_in_terms_of_parameter_math_var_sym(const char * name,struct symbol * sym)442 char *get_value_in_terms_of_parameter_math_var_sym(const char *name, struct symbol *sym)
443 {
444 struct expression *tmp, *expr;
445 char buf[256] = "";
446 int ret;
447 int cnt = 0;
448 sval_t sval;
449
450 expr = get_assigned_expr_name_sym(name, sym);
451 if (!expr)
452 return NULL;
453 while ((tmp = get_assigned_expr(expr))) {
454 expr = strip_expr(tmp);
455 if (++cnt > 3)
456 break;
457 }
458
459 if (get_implied_value(expr, &sval))
460 return NULL;
461
462 ret = format_expr_helper(buf, sizeof(buf), expr);
463 if (ret == 0)
464 return NULL;
465
466 return alloc_sname(buf);
467
468 }
469
match_alloc(const char * fn,struct expression * expr,void * _size_arg)470 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
471 {
472 int size_arg = PTR_INT(_size_arg);
473 struct expression *right;
474 struct expression *size_expr;
475 char *sname;
476
477 right = strip_expr(expr->right);
478 size_expr = get_argument_from_call_expr(right->args, size_arg);
479
480 sname = format_expr(size_expr);
481 if (!sname)
482 return;
483 set_state_expr(my_id, expr->left, alloc_state_sname(sname));
484 }
485
swap_format(struct expression * call,char * format)486 static char *swap_format(struct expression *call, char *format)
487 {
488 char buf[256];
489 sval_t sval;
490 long param;
491 struct expression *arg;
492 char *p;
493 char *out;
494 int ret;
495
496 if (format[0] == '$' && format[2] == '\0') {
497 param = strtol(format + 1, NULL, 10);
498 arg = get_argument_from_call_expr(call->args, param);
499 if (!arg)
500 return NULL;
501 return format_expr(arg);
502 }
503
504 buf[0] = '\0';
505 p = format;
506 out = buf;
507 while (*p) {
508 if (*p == '$') {
509 p++;
510 param = strtol(p, (char **)&p, 10);
511 arg = get_argument_from_call_expr(call->args, param);
512 if (!arg)
513 return NULL;
514 param = get_arg_number(arg);
515 if (param >= 0) {
516 ret = snprintf(out, buf + sizeof(buf) - out, "$%ld", param);
517 out += ret;
518 if (out >= buf + sizeof(buf))
519 return NULL;
520 } else if (get_implied_value(arg, &sval)) {
521 ret = snprintf(out, buf + sizeof(buf) - out, "%s", sval_to_str(sval));
522 out += ret;
523 if (out >= buf + sizeof(buf))
524 return NULL;
525 } else {
526 return NULL;
527 }
528 }
529 *out = *p;
530 p++;
531 out++;
532 }
533 if (buf[0] == '\0')
534 return NULL;
535 *out = '\0';
536 return alloc_sname(buf);
537 }
538
539 static char *buf_size_recipe;
db_buf_size_callback(void * unused,int argc,char ** argv,char ** azColName)540 static int db_buf_size_callback(void *unused, int argc, char **argv, char **azColName)
541 {
542 if (argc != 1)
543 return 0;
544
545 if (!buf_size_recipe)
546 buf_size_recipe = alloc_sname(argv[0]);
547 else if (strcmp(buf_size_recipe, argv[0]) != 0)
548 buf_size_recipe = alloc_sname("invalid");
549 return 0;
550 }
551
get_allocation_recipe_from_call(struct expression * expr)552 static char *get_allocation_recipe_from_call(struct expression *expr)
553 {
554 struct symbol *sym;
555 static char sql_filter[1024];
556 int i;
557
558 if (is_fake_call(expr))
559 return NULL;
560 expr = strip_expr(expr);
561 if (expr->fn->type != EXPR_SYMBOL)
562 return NULL;
563 sym = expr->fn->symbol;
564 if (!sym)
565 return NULL;
566
567 for (i = 0; i < ARRAY_SIZE(alloc_functions); i++) {
568 if (strcmp(sym->ident->name, alloc_functions[i].func) == 0) {
569 char buf[32];
570
571 snprintf(buf, sizeof(buf), "$%d", alloc_functions[i].param);
572 buf_size_recipe = alloc_sname(buf);
573 return swap_format(expr, buf_size_recipe);
574 }
575 }
576
577 if (sym->ctype.modifiers & MOD_STATIC) {
578 snprintf(sql_filter, 1024, "file = '%s' and function = '%s';",
579 get_filename(), sym->ident->name);
580 } else {
581 snprintf(sql_filter, 1024, "function = '%s' and static = 0;",
582 sym->ident->name);
583 }
584
585 buf_size_recipe = NULL;
586 run_sql(db_buf_size_callback, NULL,
587 "select value from return_states where type=%d and %s",
588 BUF_SIZE, sql_filter);
589 if (!buf_size_recipe || strcmp(buf_size_recipe, "invalid") == 0)
590 return NULL;
591 /* Known sizes should be handled in smatch_buf_size.c */
592 if (!strchr(buf_size_recipe, '$'))
593 return NULL;
594 return swap_format(expr, buf_size_recipe);
595 }
596
match_call_assignment(struct expression * expr)597 static void match_call_assignment(struct expression *expr)
598 {
599 char *sname;
600
601 sname = get_allocation_recipe_from_call(expr->right);
602 if (!sname)
603 return;
604 set_state_expr(my_id, expr->left, alloc_state_sname(sname));
605 }
606
get_allocation_math(struct expression * expr)607 const char *get_allocation_math(struct expression *expr)
608 {
609 struct expression *tmp;
610 struct smatch_state *state;
611 int cnt = 0;
612
613 expr = strip_expr(expr);
614 while ((tmp = get_assigned_expr(expr))) {
615 if (cnt++ > 5) /* assignments to self cause infinite loops */
616 break;
617 expr = strip_expr(tmp);
618 }
619 if (!expr)
620 return NULL;
621
622 if (expr->type == EXPR_CALL)
623 return get_allocation_recipe_from_call(expr);
624
625 state = get_state_expr(my_id, expr);
626 if (!state || !state->data)
627 return NULL;
628
629 return state->name;
630 }
631
register_parse_call_math(int id)632 void register_parse_call_math(int id)
633 {
634 int i;
635
636 my_id = id;
637
638 set_dynamic_states(my_id);
639
640 for (i = 0; i < ARRAY_SIZE(alloc_functions); i++)
641 add_function_assign_hook(alloc_functions[i].func, &match_alloc,
642 INT_PTR(alloc_functions[i].param));
643 add_hook(&match_call_assignment, CALL_ASSIGNMENT_HOOK);
644 }
645
646