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_variable_helper(char *buf, int remaining, struct expression *expr)
 287 {
 288         int ret = 0;
 289         char *name;
 290         struct symbol *sym;
 291         int arg;
 292         char *param_name;
 293         int name_len;
 294
 295         name = expr_to_var_sym(expr, &sym);
 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(expr))
 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         }
 312         else
 313                 goto free;
 314
 315         remaining -= ret;
 316         if (remaining <= 0)
 317                 ret = 0;
 318 free:
 319         free_string(name);
 320
 321         return ret;
 322 }
 323
 324 static int format_expr_helper(char *buf, int remaining, struct expression *expr)
 325 {
 326         sval_t sval;
 327         int ret;
 328         char *cur;
 329
 330         if (!expr)
 331                 return 0;
 332
 333         cur = buf;
 334
 335         if (expr->type == EXPR_BINOP) {
 336                 ret = format_expr_helper(cur, remaining, expr->left);
 337                 if (ret == 0)
 338                         return 0;
 339                 remaining -= ret;
 340                 if (remaining <= 0)
 341                         return 0;
 342                 cur += ret;
 343
 344                 ret = snprintf(cur, remaining, " %s ", show_special(expr->op));
 345                 remaining -= ret;
 346                 if (remaining <= 0)
 347                         return 0;
 348                 cur += ret;
 349
 350                 ret = format_expr_helper(cur, remaining, expr->right);
 351                 if (ret == 0)
 352                         return 0;
 353                 remaining -= ret;
 354                 if (remaining <= 0)
 355                         return 0;
 356                 cur += ret;
 357                 return cur - buf;
 358         }
 359
 360         if (get_implied_value(expr, &sval)) {
 361                 ret = snprintf(cur, remaining, "%s", sval_to_str(sval));
 362                 remaining -= ret;
 363                 if (remaining <= 0)
 364                         return 0;
 365                 return ret;
 366         }
 367
 368         return format_variable_helper(cur, remaining, expr);
 369 }
 370
 371 static char *format_expr(struct expression *expr)
 372 {
 373         char buf[256];
 374         int ret;
 375
 376         ret = format_expr_helper(buf, sizeof(buf), expr);
 377         if (ret == 0)
 378                 return NULL;
 379
 380         return alloc_sname(buf);
 381 }
 382
 383 char *get_value_in_terms_of_parameter_math(struct expression *expr)
 384 {
 385         struct expression *tmp;
 386         char buf[256];
 387         sval_t dummy;
 388         int ret;
 389
 390         tmp = get_assigned_expr(expr);
 391         if (tmp)
 392                 expr = tmp;
 393
 394         if (get_implied_value(expr, &dummy))
 395                 return NULL;
 396
 397         ret = format_expr_helper(buf, sizeof(buf), expr);
 398         if (ret == 0)
 399                 return NULL;
 400
 401         return alloc_sname(buf);
 402 }
 403
 404 char *get_value_in_terms_of_parameter_math_var_sym(const char *name, struct symbol *sym)
 405 {
 406         struct expression *expr;
 407         char buf[256];
 408         int ret;
 409
 410         expr = get_assigned_expr_name_sym(name, sym);
 411         if (!expr)
 412                 return NULL;
 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
 422 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 423 {
 424         int size_arg = PTR_INT(_size_arg);
 425         struct expression *right;
 426         struct expression *size_expr;
 427         char *sname;
 428
 429         right = strip_expr(expr->right);
 430         size_expr = get_argument_from_call_expr(right->args, size_arg);
 431
 432         sname = format_expr(size_expr);
 433         if (!sname)
 434                 return;
 435         set_state_expr(my_id, expr->left, alloc_state_sname(sname));
 436 }
 437
 438 static char *swap_format(struct expression *call, char *format)
 439 {
 440         char buf[256];
 441         sval_t sval;
 442         long param;
 443         struct expression *arg;
 444         char *p;
 445         char *out;
 446         int ret;
 447
 448         if (format[0] == '$' && format[2] == '\0') {
 449                 param = strtol(format + 1, NULL, 10);
 450                 arg = get_argument_from_call_expr(call->args, param);
 451                 if (!arg)
 452                         return NULL;
 453                 return format_expr(arg);
 454         }
 455
 456         buf[0] = '\0';
 457         p = format;
 458         out = buf;
 459         while (*p) {
 460                 if (*p == '$') {
 461                         p++;
 462                         param = strtol(p, &p, 10);
 463                         arg = get_argument_from_call_expr(call->args, param);
 464                         if (!arg)
 465                                 return NULL;
 466                         param = get_arg_number(arg);
 467                         if (param >= 0) {
 468                                 ret = snprintf(out, buf + sizeof(buf) - out, "$%ld", param);
 469                                 out += ret;
 470                                 if (out >= buf + sizeof(buf))
 471                                         return NULL;
 472                         } else if (get_implied_value(arg, &sval)) {
 473                                 ret = snprintf(out, buf + sizeof(buf) - out, "%s", sval_to_str(sval));
 474                                 out += ret;
 475                                 if (out >= buf + sizeof(buf))
 476                                         return NULL;
 477                         } else {
 478                                 return NULL;
 479                         }
 480                 }
 481                 *out = *p;
 482                 p++;
 483                 out++;
 484         }
 485         if (buf[0] == '\0')
 486                 return NULL;
 487         *out = '\0';
 488         return alloc_sname(buf);
 489 }
 490
 491 static char *buf_size_recipe;
 492 static int db_buf_size_callback(void *unused, int argc, char **argv, char **azColName)
 493 {
 494         if (argc != 1)
 495                 return 0;
 496
 497         if (!buf_size_recipe)
 498                 buf_size_recipe = alloc_sname(argv[0]);
 499         else if (strcmp(buf_size_recipe, argv[0]) != 0)
 500                 buf_size_recipe = alloc_sname("invalid");
 501         return 0;
 502 }
 503
 504 static char *get_allocation_recipe_from_call(struct expression *expr)
 505 {
 506         struct symbol *sym;
 507         static char sql_filter[1024];
 508         int i;
 509
 510         if (is_fake_call(expr))
 511                 return NULL;
 512         expr = strip_expr(expr);
 513         if (expr->fn->type != EXPR_SYMBOL)
 514                 return NULL;
 515         sym = expr->fn->symbol;
 516         if (!sym)
 517                 return NULL;
 518
 519         for (i = 0; i < ARRAY_SIZE(alloc_functions); i++) {
 520                 if (strcmp(sym->ident->name, alloc_functions[i].func) == 0) {
 521                         char buf[32];
 522
 523                         snprintf(buf, sizeof(buf), "$%d", alloc_functions[i].param);
 524                         buf_size_recipe = alloc_sname(buf);
 525                         return swap_format(expr, buf_size_recipe);
 526                 }
 527         }
 528
 529         if (sym->ctype.modifiers & MOD_STATIC) {
 530                 snprintf(sql_filter, 1024, "file = '%s' and function = '%s';",
 531                          get_filename(), sym->ident->name);
 532         } else {
 533                 snprintf(sql_filter, 1024, "function = '%s' and static = 0;",
 534                                 sym->ident->name);
 535         }
 536
 537         buf_size_recipe = NULL;
 538         run_sql(db_buf_size_callback, NULL,
 539                 "select value from return_states where type=%d and %s",
 540                 BUF_SIZE, sql_filter);
 541         if (!buf_size_recipe || strcmp(buf_size_recipe, "invalid") == 0)
 542                 return NULL;
 543         return swap_format(expr, buf_size_recipe);
 544 }
 545
 546 static void match_call_assignment(struct expression *expr)
 547 {
 548         char *sname;
 549
 550         sname = get_allocation_recipe_from_call(expr->right);
 551         if (!sname)
 552                 return;
 553         set_state_expr(my_id, expr->left, alloc_state_sname(sname));
 554 }
 555
 556 static void match_returns_call(int return_id, char *return_ranges, struct expression *call)
 557 {
 558         char *sname;
 559
 560         sname = get_allocation_recipe_from_call(call);
 561         if (option_debug)
 562                 sm_msg("sname = %s", sname);
 563         if (!sname)
 564                 return;
 565
 566         sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "",
 567                         sname);
 568 }
 569
 570 static void print_returned_allocations(int return_id, char *return_ranges, struct expression *expr)
 571 {
 572         struct smatch_state *state;
 573         struct symbol *sym;
 574         char *name;
 575
 576         expr = strip_expr(expr);
 577         if (!expr)
 578                 return;
 579
 580         if (expr->type == EXPR_CALL) {
 581                 match_returns_call(return_id, return_ranges, expr);
 582                 return;
 583         }
 584
 585         name = expr_to_var_sym(expr, &sym);
 586         if (!name || !sym)
 587                 goto free;
 588
 589         state = get_state(my_id, name, sym);
 590         if (!state || !state->data)
 591                 goto free;
 592
 593         sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "",
 594                         state->name);
 595 free:
 596         free_string(name);
 597 }
 598
 599 void register_parse_call_math(int id)
 600 {
 601         int i;
 602
 603         my_id = id;
 604
 605         for (i = 0; i < ARRAY_SIZE(alloc_functions); i++)
 606                 add_function_assign_hook(alloc_functions[i].func, &match_alloc,
 607                                          INT_PTR(alloc_functions[i].param));
 608         add_hook(&match_call_assignment, CALL_ASSIGNMENT_HOOK);
 609         add_split_return_callback(print_returned_allocations);
 610 }
 611