smatch_parse_call_math.c

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