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