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