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 int get_implied_param(struct expression *call, int param, sval_t *sval)
 129 {
 130         struct expression *arg;
 131
 132         arg = get_argument_from_call_expr(call->args, param);
 133         return get_implied_value(arg, sval);
 134 }
 135
 136 static int read_number(struct expression *call, char *p, char **end, sval_t *sval)
 137 {
 138         long param;
 139
 140         while (*p == ' ')
 141                 p++;
 142
 143         if (*p == '<') {
 144                 p++;
 145                 param = strtol(p, &p, 10);
 146                 if (!get_implied_param(call, param, sval))
 147                         return 0;
 148                 *end = p + 1;
 149         } else {
 150                 sval->type = &llong_ctype;
 151                 sval->value = strtoll(p, end, 10);
 152                 if (*end == p)
 153                         return 0;
 154         }
 155         return 1;
 156 }
 157
 158 static char *read_op(char *p)
 159 {
 160         while (*p == ' ')
 161                 p++;
 162
 163         switch (*p) {
 164         case '+':
 165         case '-':
 166         case '*':
 167         case '/':
 168                 return p;
 169         default:
 170                 return NULL;
 171         }
 172 }
 173
 174 int parse_call_math(struct expression *call, char *math, sval_t *sval)
 175 {
 176         sval_t tmp;
 177         char *c;
 178
 179         /* try to implement shunting yard algorithm. */
 180
 181         c = (char *)math;
 182         while (1) {
 183                 if (option_debug)
 184                         sm_msg("parsing %s", c);
 185
 186                 /* read a number and push it onto the number stack */
 187                 if (!read_number(call, c, &c, &tmp))
 188                         goto fail;
 189                 push_val(tmp);
 190
 191                 if (option_debug)
 192                         sm_msg("val = %s remaining = %s", sval_to_str(tmp), c);
 193
 194                 if (!*c)
 195                         break;
 196
 197                 c = read_op(c);
 198                 if (!c)
 199                         goto fail;
 200
 201                 if (option_debug)
 202                         sm_msg("op = %c remaining = %s", *c, c);
 203
 204                 pop_until(*c);
 205                 push_op(*c);
 206                 c++;
 207         }
 208
 209         pop_until(0);
 210         *sval = pop_val();
 211         return 1;
 212 fail:
 213         pop_until(0);  /* discard stack */
 214         return 0;
 215 }
 216
 217 static struct smatch_state *alloc_state_sname(char *sname)
 218 {
 219         struct smatch_state *state;
 220
 221         state = __alloc_smatch_state(0);
 222         state->name = sname;
 223         state->data = INT_PTR(1);
 224         return state;
 225 }
 226
 227 static int get_arg_number(struct expression *expr)
 228 {
 229         struct symbol *sym;
 230         struct symbol *arg;
 231         int i;
 232
 233         expr = strip_expr(expr);
 234         if (expr->type != EXPR_SYMBOL)
 235                 return -1;
 236         sym = expr->symbol;
 237
 238         i = 0;
 239         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
 240                 if (arg == sym)
 241                         return i;
 242                 i++;
 243         } END_FOR_EACH_PTR(arg);
 244
 245         return -1;
 246 }
 247
 248 static int format_expr_helper(char *buf, int remaining, struct expression *expr)
 249 {
 250         int arg;
 251         sval_t sval;
 252         int ret;
 253         char *cur;
 254
 255         cur = buf;
 256
 257         if (expr->type == EXPR_BINOP) {
 258                 ret = format_expr_helper(cur, remaining, expr->left);
 259                 if (ret == 0)
 260                         return 0;
 261                 remaining -= ret;
 262                 if (remaining <= 0)
 263                         return 0;
 264                 cur += ret;
 265
 266                 ret = snprintf(cur, remaining, " %s ", show_special(expr->op));
 267                 remaining -= ret;
 268                 if (remaining <= 0)
 269                         return 0;
 270                 cur += ret;
 271
 272                 ret = format_expr_helper(cur, remaining, expr->right);
 273                 if (ret == 0)
 274                         return 0;
 275                 remaining -= ret;
 276                 if (remaining <= 0)
 277                         return 0;
 278                 cur += ret;
 279                 return cur - buf;
 280         }
 281
 282         arg = get_arg_number(expr);
 283         if (arg >= 0) {
 284                 ret = snprintf(cur, remaining, "<%d>", arg);
 285                 remaining -= ret;
 286                 if (remaining <= 0)
 287                         return 0;
 288                 return ret;
 289         }
 290
 291         if (get_implied_value(expr, &sval)) {
 292                 ret = snprintf(cur, remaining, "%s", sval_to_str(sval));
 293                 remaining -= ret;
 294                 if (remaining <= 0)
 295                         return 0;
 296                 return ret;
 297         }
 298
 299         return 0;
 300 }
 301
 302 static char *format_expr(struct expression *expr)
 303 {
 304         char buf[256];
 305         int ret;
 306
 307         ret = format_expr_helper(buf, sizeof(buf), expr);
 308         if (ret == 0)
 309                 return NULL;
 310
 311         return alloc_sname(buf);
 312 }
 313
 314 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 315 {
 316         int size_arg = PTR_INT(_size_arg);
 317         struct expression *right;
 318         struct expression *size_expr;
 319         char *sname;
 320
 321         right = strip_expr(expr->right);
 322         size_expr = get_argument_from_call_expr(right->args, size_arg);
 323
 324         sname = format_expr(size_expr);
 325         if (!sname)
 326                 return;
 327         set_state_expr(my_id, expr->left, alloc_state_sname(sname));
 328 }
 329
 330 static char *swap_format(struct expression *call, char *format)
 331 {
 332         static char buf[256];
 333         sval_t sval;
 334         long param;
 335         struct expression *arg;
 336         char *p;
 337         char *out;
 338         int ret;
 339
 340         if (format[0] == '<' && format[2] == '>' && format[3] == '\0') {
 341                 param = strtol(format + 1, NULL, 10);
 342                 arg = get_argument_from_call_expr(call->args, param);
 343                 if (!arg)
 344                         return NULL;
 345                 return format_expr(arg);
 346         }
 347
 348         buf[0] = '\0';
 349         p = format;
 350         out = buf;
 351         while (*p) {
 352                 if (*p == '<') {
 353                         p++;
 354                         param = strtol(p, &p, 10);
 355                         if (*p != '>')
 356                                 return NULL;
 357                         p++;
 358                         arg = get_argument_from_call_expr(call->args, param);
 359                         if (!arg)
 360                                 return NULL;
 361                         param = get_arg_number(arg);
 362                         if (param >= 0) {
 363                                 ret = snprintf(out, buf + sizeof(buf) - out, "<%ld>", param);
 364                                 out += ret;
 365                                 if (out >= buf + sizeof(buf))
 366                                         return NULL;
 367                         } else if (get_implied_value(arg, &sval)) {
 368                                 ret = snprintf(out, buf + sizeof(buf) - out, "%s", sval_to_str(sval));
 369                                 out += ret;
 370                                 if (out >= buf + sizeof(buf))
 371                                         return NULL;
 372                         } else {
 373                                 return NULL;
 374                         }
 375                 }
 376                 *out = *p;
 377                 p++;
 378                 out++;
 379         }
 380         if (buf[0] == '\0')
 381                 return NULL;
 382         return alloc_sname(buf);
 383 }
 384
 385 static char *buf_size_recipe;
 386 static int db_buf_size_callback(void *unused, int argc, char **argv, char **azColName)
 387 {
 388         if (argc != 1)
 389                 return 0;
 390
 391         if (!buf_size_recipe)
 392                 buf_size_recipe = alloc_sname(argv[0]);
 393         else if (strcmp(buf_size_recipe, argv[0]) != 0)
 394                 buf_size_recipe = alloc_sname("invalid");
 395         return 0;
 396 }
 397
 398 static char *get_allocation_recipe_from_call(struct expression *expr)
 399 {
 400         struct symbol *sym;
 401         static char sql_filter[1024];
 402         int i;
 403
 404         expr = strip_expr(expr);
 405         if (expr->fn->type != EXPR_SYMBOL)
 406                 return NULL;
 407         sym = expr->fn->symbol;
 408         if (!sym)
 409                 return NULL;
 410
 411         for (i = 0; i < ARRAY_SIZE(alloc_functions); i++) {
 412                 if (strcmp(sym->ident->name, alloc_functions[i].func) == 0) {
 413                         char buf[32];
 414
 415                         snprintf(buf, sizeof(buf), "<%d>", alloc_functions[i].param);
 416                         buf_size_recipe = alloc_sname(buf);
 417                         return swap_format(expr, buf_size_recipe);
 418                 }
 419         }
 420
 421         if (sym->ctype.modifiers & MOD_STATIC) {
 422                 snprintf(sql_filter, 1024, "file = '%s' and function = '%s';",
 423                          get_filename(), sym->ident->name);
 424         } else {
 425                 snprintf(sql_filter, 1024, "function = '%s' and static = 0;",
 426                                 sym->ident->name);
 427         }
 428
 429         buf_size_recipe = NULL;
 430         run_sql(db_buf_size_callback, "select value from return_states where type=%d and %s",
 431                  BUF_SIZE, sql_filter);
 432         if (!buf_size_recipe || strcmp(buf_size_recipe, "invalid") == 0)
 433                 return NULL;
 434         return swap_format(expr, buf_size_recipe);
 435 }
 436
 437 static void match_call_assignment(struct expression *expr)
 438 {
 439         char *sname;
 440
 441         sname = get_allocation_recipe_from_call(expr->right);
 442         if (!sname)
 443                 return;
 444         set_state_expr(my_id, expr->left, alloc_state_sname(sname));
 445 }
 446
 447 static void match_returns_call(struct expression *call)
 448 {
 449         char *sname;
 450         struct range_list *rl;
 451
 452         sname = get_allocation_recipe_from_call(call);
 453         if (option_debug)
 454                 sm_msg("sname = %s", sname);
 455         if (!sname)
 456                 return;
 457         get_implied_range_list(call, &rl);
 458         rl = cast_rl(cur_func_return_type(), rl);
 459         sm_msg("info: return_allocation %d '%s' '%s' %s",
 460                get_return_id(), show_ranges(rl), sname, global_static());
 461 }
 462
 463 static void match_return(struct expression *expr)
 464 {
 465         struct smatch_state *state;
 466         struct range_list *rl;
 467
 468         expr = strip_expr(expr);
 469         if (!expr)
 470                 return;
 471
 472         if (expr->type == EXPR_CALL) {
 473                 match_returns_call(expr);
 474                 return;
 475         }
 476
 477         state = get_state_expr(my_id, expr);
 478         if (!state || !state->data)
 479                 return;
 480         get_implied_range_list(expr, &rl);
 481         rl = cast_rl(cur_func_return_type(), rl);
 482         sm_msg("info: return_allocation %d '%s' '%s' %s",
 483                get_return_id(), show_ranges(rl), state->name, global_static());
 484 }
 485
 486 void register_parse_call_math(int id)
 487 {
 488         int i;
 489         if (!option_info)
 490                 return;
 491
 492         my_id = id;
 493         for (i = 0; i < ARRAY_SIZE(alloc_functions); i++)
 494                 add_function_assign_hook(alloc_functions[i].func, &match_alloc,
 495                                          INT_PTR(alloc_functions[i].param));
 496         add_hook(&match_call_assignment, CALL_ASSIGNMENT_HOOK);
 497         add_hook(&match_return, RETURN_HOOK);
 498 }
 499