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 + 1;
 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 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 334 {
 335         int size_arg = PTR_INT(_size_arg);
 336         struct expression *right;
 337         struct expression *size_expr;
 338         char *sname;
 339
 340         right = strip_expr(expr->right);
 341         size_expr = get_argument_from_call_expr(right->args, size_arg);
 342
 343         sname = format_expr(size_expr);
 344         if (!sname)
 345                 return;
 346         set_state_expr(my_id, expr->left, alloc_state_sname(sname));
 347 }
 348
 349 static char *swap_format(struct expression *call, char *format)
 350 {
 351         static char buf[256];
 352         sval_t sval;
 353         long param;
 354         struct expression *arg;
 355         char *p;
 356         char *out;
 357         int ret;
 358
 359         if (format[0] == '<' && format[2] == '>' && format[3] == '\0') {
 360                 param = strtol(format + 1, NULL, 10);
 361                 arg = get_argument_from_call_expr(call->args, param);
 362                 if (!arg)
 363                         return NULL;
 364                 return format_expr(arg);
 365         }
 366
 367         buf[0] = '\0';
 368         p = format;
 369         out = buf;
 370         while (*p) {
 371                 if (*p == '<') {
 372                         p++;
 373                         param = strtol(p, &p, 10);
 374                         if (*p != '>')
 375                                 return NULL;
 376                         p++;
 377                         arg = get_argument_from_call_expr(call->args, param);
 378                         if (!arg)
 379                                 return NULL;
 380                         param = get_arg_number(arg);
 381                         if (param >= 0) {
 382                                 ret = snprintf(out, buf + sizeof(buf) - out, "<%ld>", param);
 383                                 out += ret;
 384                                 if (out >= buf + sizeof(buf))
 385                                         return NULL;
 386                         } else if (get_implied_value(arg, &sval)) {
 387                                 ret = snprintf(out, buf + sizeof(buf) - out, "%s", sval_to_str(sval));
 388                                 out += ret;
 389                                 if (out >= buf + sizeof(buf))
 390                                         return NULL;
 391                         } else {
 392                                 return NULL;
 393                         }
 394                 }
 395                 *out = *p;
 396                 p++;
 397                 out++;
 398         }
 399         if (buf[0] == '\0')
 400                 return NULL;
 401         return alloc_sname(buf);
 402 }
 403
 404 static char *buf_size_recipe;
 405 static int db_buf_size_callback(void *unused, int argc, char **argv, char **azColName)
 406 {
 407         if (argc != 1)
 408                 return 0;
 409
 410         if (!buf_size_recipe)
 411                 buf_size_recipe = alloc_sname(argv[0]);
 412         else if (strcmp(buf_size_recipe, argv[0]) != 0)
 413                 buf_size_recipe = alloc_sname("invalid");
 414         return 0;
 415 }
 416
 417 static char *get_allocation_recipe_from_call(struct expression *expr)
 418 {
 419         struct symbol *sym;
 420         static char sql_filter[1024];
 421         int i;
 422
 423         if (is_fake_call(expr))
 424                 return NULL;
 425         expr = strip_expr(expr);
 426         if (expr->fn->type != EXPR_SYMBOL)
 427                 return NULL;
 428         sym = expr->fn->symbol;
 429         if (!sym)
 430                 return NULL;
 431
 432         for (i = 0; i < ARRAY_SIZE(alloc_functions); i++) {
 433                 if (strcmp(sym->ident->name, alloc_functions[i].func) == 0) {
 434                         char buf[32];
 435
 436                         snprintf(buf, sizeof(buf), "<%d>", alloc_functions[i].param);
 437                         buf_size_recipe = alloc_sname(buf);
 438                         return swap_format(expr, buf_size_recipe);
 439                 }
 440         }
 441
 442         if (sym->ctype.modifiers & MOD_STATIC) {
 443                 snprintf(sql_filter, 1024, "file = '%s' and function = '%s';",
 444                          get_filename(), sym->ident->name);
 445         } else {
 446                 snprintf(sql_filter, 1024, "function = '%s' and static = 0;",
 447                                 sym->ident->name);
 448         }
 449
 450         buf_size_recipe = NULL;
 451         run_sql(db_buf_size_callback, "select value from return_states where type=%d and %s",
 452                  BUF_SIZE, sql_filter);
 453         if (!buf_size_recipe || strcmp(buf_size_recipe, "invalid") == 0)
 454                 return NULL;
 455         return swap_format(expr, buf_size_recipe);
 456 }
 457
 458 static void match_call_assignment(struct expression *expr)
 459 {
 460         char *sname;
 461
 462         sname = get_allocation_recipe_from_call(expr->right);
 463         if (!sname)
 464                 return;
 465         set_state_expr(my_id, expr->left, alloc_state_sname(sname));
 466 }
 467
 468 static void match_returns_call(int return_id, char *return_ranges, struct expression *call)
 469 {
 470         char *sname;
 471
 472         sname = get_allocation_recipe_from_call(call);
 473         if (option_debug)
 474                 sm_msg("sname = %s", sname);
 475         if (!sname)
 476                 return;
 477
 478         sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "",
 479                         sname);
 480 }
 481
 482 static void print_returned_allocations(int return_id, char *return_ranges, struct expression *expr)
 483 {
 484         struct smatch_state *state;
 485         struct symbol *sym;
 486         char *name;
 487
 488         expr = strip_expr(expr);
 489         if (!expr)
 490                 return;
 491
 492         if (expr->type == EXPR_CALL) {
 493                 match_returns_call(return_id, return_ranges, expr);
 494                 return;
 495         }
 496
 497         name = expr_to_var_sym(expr, &sym);
 498         if (!name || !sym)
 499                 goto free;
 500
 501         state = get_state(my_id, name, sym);
 502         if (!state || !state->data)
 503                 goto free;
 504
 505         sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "",
 506                         state->name);
 507 free:
 508         free_string(name);
 509 }
 510
 511 void register_parse_call_math(int id)
 512 {
 513         int i;
 514
 515         my_id = id;
 516
 517         for (i = 0; i < ARRAY_SIZE(alloc_functions); i++)
 518                 add_function_assign_hook(alloc_functions[i].func, &match_alloc,
 519                                          INT_PTR(alloc_functions[i].param));
 520         add_hook(&match_call_assignment, CALL_ASSIGNMENT_HOOK);
 521         add_split_return_callback(print_returned_allocations);
 522 }
 523