smatch_parse_call_math.c

   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, 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
 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
 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
 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
 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 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
 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 (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
 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
 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
 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
 449         expr = get_assigned_expr_name_sym(name, sym);
 450         if (!expr)
 451                 return NULL;
 452         while ((tmp = get_assigned_expr(expr))) {
 453                 expr = strip_expr(tmp);
 454                 if (++cnt > 3)
 455                         break;
 456         }
 457
 458         ret = format_expr_helper(buf, sizeof(buf), expr);
 459         if (ret == 0)
 460                 return NULL;
 461
 462         return alloc_sname(buf);
 463
 464 }
 465
 466 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 467 {
 468         int size_arg = PTR_INT(_size_arg);
 469         struct expression *right;
 470         struct expression *size_expr;
 471         char *sname;
 472
 473         right = strip_expr(expr->right);
 474         size_expr = get_argument_from_call_expr(right->args, size_arg);
 475
 476         sname = format_expr(size_expr);
 477         if (!sname)
 478                 return;
 479         set_state_expr(my_id, expr->left, alloc_state_sname(sname));
 480 }
 481
 482 static char *swap_format(struct expression *call, char *format)
 483 {
 484         char buf[256];
 485         sval_t sval;
 486         long param;
 487         struct expression *arg;
 488         char *p;
 489         char *out;
 490         int ret;
 491
 492         if (format[0] == '$' && format[2] == '\0') {
 493                 param = strtol(format + 1, NULL, 10);
 494                 arg = get_argument_from_call_expr(call->args, param);
 495                 if (!arg)
 496                         return NULL;
 497                 return format_expr(arg);
 498         }
 499
 500         buf[0] = '\0';
 501         p = format;
 502         out = buf;
 503         while (*p) {
 504                 if (*p == '$') {
 505                         p++;
 506                         param = strtol(p, (char **)&p, 10);
 507                         arg = get_argument_from_call_expr(call->args, param);
 508                         if (!arg)
 509                                 return NULL;
 510                         param = get_arg_number(arg);
 511                         if (param >= 0) {
 512                                 ret = snprintf(out, buf + sizeof(buf) - out, "$%ld", param);
 513                                 out += ret;
 514                                 if (out >= buf + sizeof(buf))
 515                                         return NULL;
 516                         } else if (get_implied_value(arg, &sval)) {
 517                                 ret = snprintf(out, buf + sizeof(buf) - out, "%s", sval_to_str(sval));
 518                                 out += ret;
 519                                 if (out >= buf + sizeof(buf))
 520                                         return NULL;
 521                         } else {
 522                                 return NULL;
 523                         }
 524                 }
 525                 *out = *p;
 526                 p++;
 527                 out++;
 528         }
 529         if (buf[0] == '\0')
 530                 return NULL;
 531         *out = '\0';
 532         return alloc_sname(buf);
 533 }
 534
 535 static char *buf_size_recipe;
 536 static int db_buf_size_callback(void *unused, int argc, char **argv, char **azColName)
 537 {
 538         if (argc != 1)
 539                 return 0;
 540
 541         if (!buf_size_recipe)
 542                 buf_size_recipe = alloc_sname(argv[0]);
 543         else if (strcmp(buf_size_recipe, argv[0]) != 0)
 544                 buf_size_recipe = alloc_sname("invalid");
 545         return 0;
 546 }
 547
 548 static char *get_allocation_recipe_from_call(struct expression *expr)
 549 {
 550         struct symbol *sym;
 551         static char sql_filter[1024];
 552         int i;
 553
 554         if (is_fake_call(expr))
 555                 return NULL;
 556         expr = strip_expr(expr);
 557         if (expr->fn->type != EXPR_SYMBOL)
 558                 return NULL;
 559         sym = expr->fn->symbol;
 560         if (!sym)
 561                 return NULL;
 562
 563         for (i = 0; i < ARRAY_SIZE(alloc_functions); i++) {
 564                 if (strcmp(sym->ident->name, alloc_functions[i].func) == 0) {
 565                         char buf[32];
 566
 567                         snprintf(buf, sizeof(buf), "$%d", alloc_functions[i].param);
 568                         buf_size_recipe = alloc_sname(buf);
 569                         return swap_format(expr, buf_size_recipe);
 570                 }
 571         }
 572
 573         if (sym->ctype.modifiers & MOD_STATIC) {
 574                 snprintf(sql_filter, 1024, "file = '%s' and function = '%s';",
 575                          get_filename(), sym->ident->name);
 576         } else {
 577                 snprintf(sql_filter, 1024, "function = '%s' and static = 0;",
 578                                 sym->ident->name);
 579         }
 580
 581         buf_size_recipe = NULL;
 582         run_sql(db_buf_size_callback, NULL,
 583                 "select value from return_states where type=%d and %s",
 584                 BUF_SIZE, sql_filter);
 585         if (!buf_size_recipe || strcmp(buf_size_recipe, "invalid") == 0)
 586                 return NULL;
 587         return swap_format(expr, buf_size_recipe);
 588 }
 589
 590 static void match_call_assignment(struct expression *expr)
 591 {
 592         char *sname;
 593
 594         sname = get_allocation_recipe_from_call(expr->right);
 595         if (!sname)
 596                 return;
 597         set_state_expr(my_id, expr->left, alloc_state_sname(sname));
 598 }
 599
 600 static void match_returns_call(int return_id, char *return_ranges, struct expression *call)
 601 {
 602         char *sname;
 603
 604         sname = get_allocation_recipe_from_call(call);
 605         if (option_debug)
 606                 sm_msg("sname = %s", sname);
 607         if (!sname)
 608                 return;
 609
 610         sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "",
 611                         sname);
 612 }
 613
 614 static void print_returned_allocations(int return_id, char *return_ranges, struct expression *expr)
 615 {
 616         struct expression *tmp;
 617         struct smatch_state *state;
 618         struct symbol *sym;
 619         char *name;
 620         int cnt = 0;
 621
 622         expr = strip_expr(expr);
 623         while ((tmp = get_assigned_expr(expr))) {
 624                 if (cnt++ > 5)  /* assignments to self cause infinite loops */
 625                         break;
 626                 expr = strip_expr(tmp);
 627         }
 628         if (!expr)
 629                 return;
 630
 631         if (expr->type == EXPR_CALL) {
 632                 match_returns_call(return_id, return_ranges, expr);
 633                 return;
 634         }
 635
 636         name = expr_to_var_sym(expr, &sym);
 637         if (!name || !sym)
 638                 goto free;
 639
 640         state = get_state(my_id, name, sym);
 641         if (!state || !state->data)
 642                 goto free;
 643
 644         sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "",
 645                         state->name);
 646 free:
 647         free_string(name);
 648 }
 649
 650 void register_parse_call_math(int id)
 651 {
 652         int i;
 653
 654         my_id = id;
 655
 656         for (i = 0; i < ARRAY_SIZE(alloc_functions); i++)
 657                 add_function_assign_hook(alloc_functions[i].func, &match_alloc,
 658                                          INT_PTR(alloc_functions[i].param));
 659         add_hook(&match_call_assignment, CALL_ASSIGNMENT_HOOK);
 660         add_split_return_callback(print_returned_allocations);
 661 }
 662