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