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
 213                 c = read_op(c);
 214                 if (!c)
 215                         goto fail;
 216
 217                 if (option_debug)
 218                         sm_msg("op = %c remaining = %s", *c, c);
 219
 220                 pop_until(*c);
 221                 push_op(*c);
 222                 c++;
 223         }
 224
 225         pop_until(0);
 226         *sval = pop_val();
 227         return 1;
 228 fail:
 229         discard_stacks();
 230         return 0;
 231 }
 232
 233 static struct smatch_state *alloc_state_sname(char *sname)
 234 {
 235         struct smatch_state *state;
 236
 237         state = __alloc_smatch_state(0);
 238         state->name = sname;
 239         state->data = INT_PTR(1);
 240         return state;
 241 }
 242
 243 static int get_arg_number(struct expression *expr)
 244 {
 245         struct symbol *sym;
 246         struct symbol *arg;
 247         int i;
 248
 249         expr = strip_expr(expr);
 250         if (expr->type != EXPR_SYMBOL)
 251                 return -1;
 252         sym = expr->symbol;
 253
 254         i = 0;
 255         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
 256                 if (arg == sym)
 257                         return i;
 258                 i++;
 259         } END_FOR_EACH_PTR(arg);
 260
 261         return -1;
 262 }
 263
 264 static int format_expr_helper(char *buf, int remaining, struct expression *expr)
 265 {
 266         int arg;
 267         sval_t sval;
 268         int ret;
 269         char *cur;
 270
 271         if (!expr)
 272                 return 0;
 273
 274         cur = buf;
 275
 276         if (expr->type == EXPR_BINOP) {
 277                 ret = format_expr_helper(cur, remaining, expr->left);
 278                 if (ret == 0)
 279                         return 0;
 280                 remaining -= ret;
 281                 if (remaining <= 0)
 282                         return 0;
 283                 cur += ret;
 284
 285                 ret = snprintf(cur, remaining, " %s ", show_special(expr->op));
 286                 remaining -= ret;
 287                 if (remaining <= 0)
 288                         return 0;
 289                 cur += ret;
 290
 291                 ret = format_expr_helper(cur, remaining, expr->right);
 292                 if (ret == 0)
 293                         return 0;
 294                 remaining -= ret;
 295                 if (remaining <= 0)
 296                         return 0;
 297                 cur += ret;
 298                 return cur - buf;
 299         }
 300
 301         arg = get_arg_number(expr);
 302         if (arg >= 0) {
 303                 ret = snprintf(cur, remaining, "$%d", arg);
 304                 remaining -= ret;
 305                 if (remaining <= 0)
 306                         return 0;
 307                 return ret;
 308         }
 309
 310         if (get_implied_value(expr, &sval)) {
 311                 ret = snprintf(cur, remaining, "%s", sval_to_str(sval));
 312                 remaining -= ret;
 313                 if (remaining <= 0)
 314                         return 0;
 315                 return ret;
 316         }
 317
 318         return 0;
 319 }
 320
 321 static char *format_expr(struct expression *expr)
 322 {
 323         char buf[256];
 324         int ret;
 325
 326         ret = format_expr_helper(buf, sizeof(buf), expr);
 327         if (ret == 0)
 328                 return NULL;
 329
 330         return alloc_sname(buf);
 331 }
 332
 333 char *get_value_in_terms_of_parameter_math(struct expression *expr)
 334 {
 335         struct expression *tmp;
 336         char buf[256];
 337         int ret;
 338
 339         tmp = get_assigned_expr(expr);
 340         if (tmp)
 341                 expr = tmp;
 342
 343         ret = format_expr_helper(buf, sizeof(buf), expr);
 344         if (ret == 0)
 345                 return NULL;
 346
 347         return alloc_sname(buf);
 348 }
 349
 350 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 351 {
 352         int size_arg = PTR_INT(_size_arg);
 353         struct expression *right;
 354         struct expression *size_expr;
 355         char *sname;
 356
 357         right = strip_expr(expr->right);
 358         size_expr = get_argument_from_call_expr(right->args, size_arg);
 359
 360         sname = format_expr(size_expr);
 361         if (!sname)
 362                 return;
 363         set_state_expr(my_id, expr->left, alloc_state_sname(sname));
 364 }
 365
 366 static char *swap_format(struct expression *call, char *format)
 367 {
 368         static char buf[256];
 369         sval_t sval;
 370         long param;
 371         struct expression *arg;
 372         char *p;
 373         char *out;
 374         int ret;
 375
 376         if (format[0] == '<' && format[2] == '>' && format[3] == '\0') {
 377                 param = strtol(format + 1, NULL, 10);
 378                 arg = get_argument_from_call_expr(call->args, param);
 379                 if (!arg)
 380                         return NULL;
 381                 return format_expr(arg);
 382         }
 383
 384         buf[0] = '\0';
 385         p = format;
 386         out = buf;
 387         while (*p) {
 388                 if (*p == '<') {
 389                         p++;
 390                         param = strtol(p, &p, 10);
 391                         if (*p != '>')
 392                                 return NULL;
 393                         p++;
 394                         arg = get_argument_from_call_expr(call->args, param);
 395                         if (!arg)
 396                                 return NULL;
 397                         param = get_arg_number(arg);
 398                         if (param >= 0) {
 399                                 ret = snprintf(out, buf + sizeof(buf) - out, "$%ld", param);
 400                                 out += ret;
 401                                 if (out >= buf + sizeof(buf))
 402                                         return NULL;
 403                         } else if (get_implied_value(arg, &sval)) {
 404                                 ret = snprintf(out, buf + sizeof(buf) - out, "%s", sval_to_str(sval));
 405                                 out += ret;
 406                                 if (out >= buf + sizeof(buf))
 407                                         return NULL;
 408                         } else {
 409                                 return NULL;
 410                         }
 411                 }
 412                 *out = *p;
 413                 p++;
 414                 out++;
 415         }
 416         if (buf[0] == '\0')
 417                 return NULL;
 418         return alloc_sname(buf);
 419 }
 420
 421 static char *buf_size_recipe;
 422 static int db_buf_size_callback(void *unused, int argc, char **argv, char **azColName)
 423 {
 424         if (argc != 1)
 425                 return 0;
 426
 427         if (!buf_size_recipe)
 428                 buf_size_recipe = alloc_sname(argv[0]);
 429         else if (strcmp(buf_size_recipe, argv[0]) != 0)
 430                 buf_size_recipe = alloc_sname("invalid");
 431         return 0;
 432 }
 433
 434 static char *get_allocation_recipe_from_call(struct expression *expr)
 435 {
 436         struct symbol *sym;
 437         static char sql_filter[1024];
 438         int i;
 439
 440         if (is_fake_call(expr))
 441                 return NULL;
 442         expr = strip_expr(expr);
 443         if (expr->fn->type != EXPR_SYMBOL)
 444                 return NULL;
 445         sym = expr->fn->symbol;
 446         if (!sym)
 447                 return NULL;
 448
 449         for (i = 0; i < ARRAY_SIZE(alloc_functions); i++) {
 450                 if (strcmp(sym->ident->name, alloc_functions[i].func) == 0) {
 451                         char buf[32];
 452
 453                         snprintf(buf, sizeof(buf), "$%d", alloc_functions[i].param);
 454                         buf_size_recipe = alloc_sname(buf);
 455                         return swap_format(expr, buf_size_recipe);
 456                 }
 457         }
 458
 459         if (sym->ctype.modifiers & MOD_STATIC) {
 460                 snprintf(sql_filter, 1024, "file = '%s' and function = '%s';",
 461                          get_filename(), sym->ident->name);
 462         } else {
 463                 snprintf(sql_filter, 1024, "function = '%s' and static = 0;",
 464                                 sym->ident->name);
 465         }
 466
 467         buf_size_recipe = NULL;
 468         run_sql(db_buf_size_callback, "select value from return_states where type=%d and %s",
 469                  BUF_SIZE, sql_filter);
 470         if (!buf_size_recipe || strcmp(buf_size_recipe, "invalid") == 0)
 471                 return NULL;
 472         return swap_format(expr, buf_size_recipe);
 473 }
 474
 475 static void match_call_assignment(struct expression *expr)
 476 {
 477         char *sname;
 478
 479         sname = get_allocation_recipe_from_call(expr->right);
 480         if (!sname)
 481                 return;
 482         set_state_expr(my_id, expr->left, alloc_state_sname(sname));
 483 }
 484
 485 static void match_returns_call(int return_id, char *return_ranges, struct expression *call)
 486 {
 487         char *sname;
 488
 489         sname = get_allocation_recipe_from_call(call);
 490         if (option_debug)
 491                 sm_msg("sname = %s", sname);
 492         if (!sname)
 493                 return;
 494
 495         sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "",
 496                         sname);
 497 }
 498
 499 static void print_returned_allocations(int return_id, char *return_ranges, struct expression *expr)
 500 {
 501         struct smatch_state *state;
 502         struct symbol *sym;
 503         char *name;
 504
 505         expr = strip_expr(expr);
 506         if (!expr)
 507                 return;
 508
 509         if (expr->type == EXPR_CALL) {
 510                 match_returns_call(return_id, return_ranges, expr);
 511                 return;
 512         }
 513
 514         name = expr_to_var_sym(expr, &sym);
 515         if (!name || !sym)
 516                 goto free;
 517
 518         state = get_state(my_id, name, sym);
 519         if (!state || !state->data)
 520                 goto free;
 521
 522         sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "",
 523                         state->name);
 524 free:
 525         free_string(name);
 526 }
 527
 528 void register_parse_call_math(int id)
 529 {
 530         int i;
 531
 532         my_id = id;
 533
 534         for (i = 0; i < ARRAY_SIZE(alloc_functions); i++)
 535                 add_function_assign_hook(alloc_functions[i].func, &match_alloc,
 536                                          INT_PTR(alloc_functions[i].param));
 537         add_hook(&match_call_assignment, CALL_ASSIGNMENT_HOOK);
 538         add_split_return_callback(print_returned_allocations);
 539 }
 540