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