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