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         int ret;
 388
 389         tmp = get_assigned_expr(expr);
 390         if (tmp)
 391                 expr = tmp;
 392
 393         ret = format_expr_helper(buf, sizeof(buf), expr);
 394         if (ret == 0)
 395                 return NULL;
 396
 397         return alloc_sname(buf);
 398 }
 399
 400 char *get_value_in_terms_of_parameter_math_var_sym(const char *name, struct symbol *sym)
 401 {
 402         struct expression *expr;
 403         char buf[256];
 404         int ret;
 405
 406         expr = get_assigned_expr_name_sym(name, sym);
 407         if (!expr)
 408                 return NULL;
 409
 410         ret = format_expr_helper(buf, sizeof(buf), expr);
 411         if (ret == 0)
 412                 return NULL;
 413
 414         return alloc_sname(buf);
 415
 416 }
 417
 418 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 419 {
 420         int size_arg = PTR_INT(_size_arg);
 421         struct expression *right;
 422         struct expression *size_expr;
 423         char *sname;
 424
 425         right = strip_expr(expr->right);
 426         size_expr = get_argument_from_call_expr(right->args, size_arg);
 427
 428         sname = format_expr(size_expr);
 429         if (!sname)
 430                 return;
 431         set_state_expr(my_id, expr->left, alloc_state_sname(sname));
 432 }
 433
 434 static char *swap_format(struct expression *call, char *format)
 435 {
 436         char buf[256];
 437         sval_t sval;
 438         long param;
 439         struct expression *arg;
 440         char *p;
 441         char *out;
 442         int ret;
 443
 444         if (format[0] == '$' && format[2] == '\0') {
 445                 param = strtol(format + 1, NULL, 10);
 446                 arg = get_argument_from_call_expr(call->args, param);
 447                 if (!arg)
 448                         return NULL;
 449                 return format_expr(arg);
 450         }
 451
 452         buf[0] = '\0';
 453         p = format;
 454         out = buf;
 455         while (*p) {
 456                 if (*p == '$') {
 457                         p++;
 458                         param = strtol(p, &p, 10);
 459                         arg = get_argument_from_call_expr(call->args, param);
 460                         if (!arg)
 461                                 return NULL;
 462                         param = get_arg_number(arg);
 463                         if (param >= 0) {
 464                                 ret = snprintf(out, buf + sizeof(buf) - out, "$%ld", param);
 465                                 out += ret;
 466                                 if (out >= buf + sizeof(buf))
 467                                         return NULL;
 468                         } else if (get_implied_value(arg, &sval)) {
 469                                 ret = snprintf(out, buf + sizeof(buf) - out, "%s", sval_to_str(sval));
 470                                 out += ret;
 471                                 if (out >= buf + sizeof(buf))
 472                                         return NULL;
 473                         } else {
 474                                 return NULL;
 475                         }
 476                 }
 477                 *out = *p;
 478                 p++;
 479                 out++;
 480         }
 481         if (buf[0] == '\0')
 482                 return NULL;
 483         *out = '\0';
 484         return alloc_sname(buf);
 485 }
 486
 487 static char *buf_size_recipe;
 488 static int db_buf_size_callback(void *unused, int argc, char **argv, char **azColName)
 489 {
 490         if (argc != 1)
 491                 return 0;
 492
 493         if (!buf_size_recipe)
 494                 buf_size_recipe = alloc_sname(argv[0]);
 495         else if (strcmp(buf_size_recipe, argv[0]) != 0)
 496                 buf_size_recipe = alloc_sname("invalid");
 497         return 0;
 498 }
 499
 500 static char *get_allocation_recipe_from_call(struct expression *expr)
 501 {
 502         struct symbol *sym;
 503         static char sql_filter[1024];
 504         int i;
 505
 506         if (is_fake_call(expr))
 507                 return NULL;
 508         expr = strip_expr(expr);
 509         if (expr->fn->type != EXPR_SYMBOL)
 510                 return NULL;
 511         sym = expr->fn->symbol;
 512         if (!sym)
 513                 return NULL;
 514
 515         for (i = 0; i < ARRAY_SIZE(alloc_functions); i++) {
 516                 if (strcmp(sym->ident->name, alloc_functions[i].func) == 0) {
 517                         char buf[32];
 518
 519                         snprintf(buf, sizeof(buf), "$%d", alloc_functions[i].param);
 520                         buf_size_recipe = alloc_sname(buf);
 521                         return swap_format(expr, buf_size_recipe);
 522                 }
 523         }
 524
 525         if (sym->ctype.modifiers & MOD_STATIC) {
 526                 snprintf(sql_filter, 1024, "file = '%s' and function = '%s';",
 527                          get_filename(), sym->ident->name);
 528         } else {
 529                 snprintf(sql_filter, 1024, "function = '%s' and static = 0;",
 530                                 sym->ident->name);
 531         }
 532
 533         buf_size_recipe = NULL;
 534         run_sql(db_buf_size_callback, NULL,
 535                 "select value from return_states where type=%d and %s",
 536                 BUF_SIZE, sql_filter);
 537         if (!buf_size_recipe || strcmp(buf_size_recipe, "invalid") == 0)
 538                 return NULL;
 539         return swap_format(expr, buf_size_recipe);
 540 }
 541
 542 static void match_call_assignment(struct expression *expr)
 543 {
 544         char *sname;
 545
 546         sname = get_allocation_recipe_from_call(expr->right);
 547         if (!sname)
 548                 return;
 549         set_state_expr(my_id, expr->left, alloc_state_sname(sname));
 550 }
 551
 552 static void match_returns_call(int return_id, char *return_ranges, struct expression *call)
 553 {
 554         char *sname;
 555
 556         sname = get_allocation_recipe_from_call(call);
 557         if (option_debug)
 558                 sm_msg("sname = %s", sname);
 559         if (!sname)
 560                 return;
 561
 562         sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "",
 563                         sname);
 564 }
 565
 566 static void print_returned_allocations(int return_id, char *return_ranges, struct expression *expr)
 567 {
 568         struct smatch_state *state;
 569         struct symbol *sym;
 570         char *name;
 571
 572         expr = strip_expr(expr);
 573         if (!expr)
 574                 return;
 575
 576         if (expr->type == EXPR_CALL) {
 577                 match_returns_call(return_id, return_ranges, expr);
 578                 return;
 579         }
 580
 581         name = expr_to_var_sym(expr, &sym);
 582         if (!name || !sym)
 583                 goto free;
 584
 585         state = get_state(my_id, name, sym);
 586         if (!state || !state->data)
 587                 goto free;
 588
 589         sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "",
 590                         state->name);
 591 free:
 592         free_string(name);
 593 }
 594
 595 void register_parse_call_math(int id)
 596 {
 597         int i;
 598
 599         my_id = id;
 600
 601         for (i = 0; i < ARRAY_SIZE(alloc_functions); i++)
 602                 add_function_assign_hook(alloc_functions[i].func, &match_alloc,
 603                                          INT_PTR(alloc_functions[i].param));
 604         add_hook(&match_call_assignment, CALL_ASSIGNMENT_HOOK);
 605         add_split_return_callback(print_returned_allocations);
 606 }
 607