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