smatch_units.c

   1 /*
   2  * Copyright (C) 2018 Oracle.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 #include "smatch.h"
  19 #include "smatch_slist.h"
  20
  21 static int my_id;
  22
  23 STATE(bit);
  24 STATE(byte);
  25 STATE(array_size);
  26 STATE(longs);
  27 STATE(page);
  28 STATE(msec);
  29 //STATE(ns);
  30 STATE(jiffy);
  31
  32 struct type_info {
  33         const char *name;
  34         int type;
  35         int param;
  36         const char *key;
  37         const char *value;
  38 };
  39
  40 static struct type_info func_table[] = {
  41         { "msecs_to_jiffies_timeout", UNITS, -1, "$", "jiffy" },
  42         { "round_jiffies_up_relative", UNITS, -1, "$", "jiffy" },
  43 };
  44
  45 static struct smatch_state *str_to_units(const char *str)
  46 {
  47         if (!str)
  48                 return NULL;
  49
  50         if (strcmp(str, "bit") == 0)
  51                 return &bit;
  52         if (strcmp(str, "byte") == 0)
  53                 return &byte;
  54         if (strcmp(str, "page") == 0)
  55                 return &page;
  56         if (strcmp(str, "msec") == 0)
  57                 return &msec;
  58         if (strcmp(str, "jiffy") == 0)
  59                 return &jiffy;
  60         if (strcmp(str, "longs") == 0)
  61                 return &longs;
  62         if (strcmp(str, "array_size") == 0)
  63                 return &array_size;
  64         if (strcmp(str, "unknown") == 0)
  65                 return NULL;
  66
  67         return NULL;
  68 }
  69
  70 static struct smatch_state *get_units_from_type(struct expression *expr);
  71
  72 static void pre_merge_hook(struct sm_state *cur, struct sm_state *other)
  73 {
  74         if (cur->state == other->state)
  75                 return;
  76
  77         if (cur->state == &undefined || cur->state == &merged ||
  78             other->state == &undefined || other->state == &merged)
  79                 return;
  80
  81         if (!__cur_stmt || __cur_stmt->type != STMT_RETURN)
  82                 sm_msg("warn: ambiguous units merge '%s' '%s' or '%s'",
  83                        cur->name, cur->state->name, other->state->name);
  84 }
  85
  86 static struct smatch_state *merge_units(struct smatch_state *s1, struct smatch_state *s2)
  87 {
  88         if (s1 == &undefined)
  89                 return s2;
  90         if (s2 == &undefined)
  91                 return s1;
  92         return &merged;
  93 }
  94
  95 static bool is_ignored_type(char *name)
  96 {
  97         if (!name)
  98                 return false;
  99         if (strcmp(name, "(union anonymous)->__val") == 0)
 100                 return true;
 101         if (strncmp(name, "(struct fs_parse_result)", 24) == 0)
 102                 return true;
 103         return false;
 104 }
 105
 106 static void store_type_in_db(struct expression *expr, struct smatch_state *state)
 107 {
 108         struct smatch_state *old_units;
 109         char *member;
 110
 111         member = get_member_name(expr);
 112         if (!member)
 113                 return;
 114         if (is_ignored_type(member))
 115                 return;
 116
 117         old_units = get_units_from_type(expr);
 118         if (old_units && old_units != state) {
 119                 sm_msg("warn: other places set '%s' to '%s' instead of '%s'",
 120                        member, old_units->name, state->name);
 121         }
 122 //      sm_msg("%s: insert: member='%s' units='%s'", __func__, member, state->name);
 123         sql_insert_cache(type_info, "0x%llx, %d, '%s', '%s'", get_base_file_id(), UNITS, member, state->name);
 124 }
 125
 126 static void set_units(struct expression *expr, struct smatch_state *state)
 127 {
 128         if (!state)
 129                 return;
 130
 131         set_state_expr(my_id, expr, state);
 132         store_type_in_db(expr, state);
 133 }
 134
 135 static bool is_PAGE_SHIFT(struct expression *expr)
 136 {
 137         char *macro;
 138
 139         macro = get_macro_name(expr->pos);
 140         if (macro && strcmp(macro, "PAGE_SHIFT") == 0)
 141                 return true;
 142         return false;
 143 }
 144
 145 static bool is_PAGE_SIZE(struct expression *expr)
 146 {
 147         char *macro;
 148
 149         macro = get_macro_name(expr->pos);
 150         if (macro && strcmp(macro, "PAGE_SIZE") == 0)
 151                 return true;
 152         return false;
 153 }
 154
 155 static bool is_BITS_PER_LONG(struct expression *expr)
 156 {
 157         char *macro;
 158
 159         macro = get_macro_name(expr->pos);
 160         if (macro && strcmp(macro, "BITS_PER_LONG") == 0)
 161                 return true;
 162         return false;
 163 }
 164
 165 static struct smatch_state *binop_helper(struct expression *left, int op, struct expression *right)
 166 {
 167         struct smatch_state *left_state, *right_state;
 168         sval_t val;
 169
 170         switch(op) {
 171         case '-':
 172                 // subtracting pointers gives byte units
 173                 /* fall through */
 174         case '+':
 175                 left_state = get_units(left);
 176                 right_state = get_units(right);
 177                 if (left_state == &array_size ||
 178                     right_state == &array_size)
 179                         return NULL;
 180
 181                 return left_state ? left_state : right_state;
 182         case '*':
 183                 /* FIXME: A multiply is almost always bytes but it can be bits. */
 184                 if (is_PAGE_SIZE(right))
 185                         return &byte;
 186                 if (!get_implied_value(right, &val))
 187                         return NULL;
 188                 /* 4096 is almost always a page -> bytes converstion */
 189                 if (val.value == 4096)
 190                         return &byte;
 191                 return NULL;
 192         case '/':
 193                 if (is_BITS_PER_LONG(right))
 194                         return &longs;
 195                 if (is_PAGE_SIZE(right))
 196                         return &page;
 197                 if (!get_implied_value(right, &val))
 198                         return NULL;
 199                 if (val.value == 4096)
 200                         return &page;
 201                 return NULL;
 202         case SPECIAL_LEFTSHIFT:
 203                 if (is_PAGE_SHIFT(right))
 204                         return &byte;
 205                 return NULL;
 206         case SPECIAL_RIGHTSHIFT:
 207                 if (is_PAGE_SHIFT(right))
 208                         return &page;
 209                 return NULL;
 210         }
 211         return NULL;
 212 }
 213
 214 static struct smatch_state *get_units_binop(struct expression *expr)
 215 {
 216         return binop_helper(expr->left, expr->op, expr->right);
 217 }
 218
 219 static struct smatch_state *get_units_call(struct expression *expr)
 220 {
 221         expr = strip_expr(expr);
 222         if (!expr || expr->type != EXPR_CALL)
 223                 return NULL;
 224
 225         if (sym_name_is("msecs_to_jiffies", expr->fn))
 226                 return &jiffy;
 227         if (sym_name_is("jiffies_to_msecs", expr->fn))
 228                 return &msec;
 229
 230         return NULL;
 231 }
 232
 233 static int db_units(void *_units, int argc, char **argv, char **azColName)
 234 {
 235         char **units = _units;
 236
 237         if (*units) {
 238                 if (strcmp(*units, argv[0]) == 0)
 239                         return 0;
 240                 free_string(*units);
 241                 *units = alloc_string("unknown");
 242                 return 0;
 243
 244         }
 245         *units = alloc_string(argv[0]);
 246         return 0;
 247 }
 248
 249 static struct smatch_state *get_units_from_type(struct expression *expr)
 250 {
 251         char *member;
 252         char *units = NULL;
 253         struct smatch_state *ret = NULL;
 254
 255         member = get_member_name(expr);
 256         if (!member)
 257                 return NULL;
 258         if (strcmp(member, "(struct vm_area_struct)->vm_pgoff") == 0)
 259                 return &page;
 260         cache_sql(&db_units, &units, "select value from type_info where type = %d and key = '%s';",
 261                   UNITS, member);
 262         run_sql(&db_units, &units, "select value from type_info where type = %d and key = '%s';",
 263                 UNITS, member);
 264         free_string(member);
 265         if (!units)
 266                 return NULL;
 267
 268         ret = str_to_units(units);
 269
 270         free_string(units);
 271
 272         return ret;
 273 }
 274
 275 struct smatch_state *get_units(struct expression *expr)
 276 {
 277         struct smatch_state *state;
 278         char *ident;
 279
 280         expr = strip_expr(expr);
 281         if (!expr)
 282                 return NULL;
 283
 284         if (expr->type == EXPR_PTRSIZEOF ||
 285             expr->type == EXPR_SIZEOF)
 286                 return &byte;
 287
 288         ident = pos_ident(expr->pos);
 289         if (ident) {
 290                 if (strcmp(ident, "sizeof") == 0 ||
 291                     strcmp(ident, "PAGE_SIZE") == 0)
 292                         return &byte;
 293                 if (strcmp(ident, "jiffies") == 0)
 294                         return &jiffy;
 295                 if (strcmp(ident, "BITS_PER_LONG") == 0)
 296                         return &bit;
 297                 if (strcmp(ident, "BITS_PER_LONG_LONG") == 0)
 298                         return &bit;
 299                 if (strcmp(ident, "ARRAY_SIZE") == 0)
 300                         return &array_size;
 301         }
 302
 303         if (expr->type == EXPR_BINOP)
 304                 return get_units_binop(expr);
 305
 306         if (expr->type == EXPR_CALL)
 307                 return get_units_call(expr);
 308
 309         state = get_state_expr(my_id, expr);
 310         if (state == &merged || state == &undefined)
 311                 return NULL;
 312         if (state)
 313                 return state;
 314
 315         return get_units_from_type(expr);
 316 }
 317
 318 bool is_array_size_units(struct expression *expr)
 319 {
 320         return get_units(expr) == &array_size;
 321 }
 322
 323 static void match_allocation(struct expression *expr,
 324                              const char *name, struct symbol *sym,
 325                              struct allocation_info *info)
 326 {
 327         struct expression *right, *left;
 328
 329         if (info->nr_elems && info->elem_size) {
 330                 left = info->nr_elems;
 331                 right = info->elem_size;
 332         } else if (info->total_size &&
 333                    info->total_size->type == EXPR_BINOP &&
 334                    info->total_size->op == '*') {
 335                 left = strip_expr(info->total_size->left);
 336                 right = strip_expr(info->total_size->right);
 337         } else {
 338                 return;
 339         }
 340
 341         if (get_units(left) == &byte)
 342                 set_units(right, &array_size);
 343         if (get_units(right) == &byte)
 344                 set_units(left, &array_size);
 345 }
 346
 347 static void check_mult(struct expression *expr)
 348 {
 349         struct smatch_state *left, *right;
 350         int bit_found = 0, byte_found = 0;
 351         char *name;
 352
 353         left = get_units(expr->left);
 354         right = get_units(expr->right);
 355
 356         if (left == &bit || right == &bit)
 357                 bit_found++;
 358         if (left == &byte || right == &byte)
 359                 byte_found++;
 360
 361         if (bit_found && byte_found) {
 362                 name = expr_to_str(expr);
 363                 sm_warning("multiplying bits * bytes '%s'", name);
 364                 free_string(name);
 365         }
 366 }
 367
 368 static void check_add_sub(struct expression *expr)
 369 {
 370         struct smatch_state *left, *right;
 371         struct symbol *type;
 372         char *str;
 373
 374         type = get_type(expr->left);
 375         if (type && (type->type == SYM_PTR || type->type == SYM_ARRAY))
 376                 return;
 377
 378         left = get_units(expr->left);
 379         right = get_units(expr->right);
 380
 381         if (!left || !right || left == right)
 382                 return;
 383         str = expr_to_str(expr);
 384         sm_warning("missing conversion: '%s' '%s %s %s'", str, left->name, show_special(expr->op), right->name);
 385         free_string(str);
 386
 387 }
 388
 389 static void match_binop_check(struct expression *expr)
 390 {
 391         switch (expr->op) {
 392         case '+':
 393         case '-':
 394                 check_add_sub(expr);
 395                 return;
 396         case '*':
 397                 check_mult(expr);
 398                 return;
 399         }
 400 }
 401
 402 static void match_binop_set(struct expression *expr)
 403 {
 404         struct smatch_state *left, *right;
 405         struct symbol *type;
 406
 407         if (expr->op == SPECIAL_LEFTSHIFT && is_PAGE_SHIFT(expr->right)) {
 408                 set_units(expr->left, &page);
 409                 return;
 410         }
 411
 412         if (expr->op == SPECIAL_RIGHTSHIFT && is_PAGE_SHIFT(expr->right)) {
 413                 set_units(expr->left, &byte);
 414                 return;
 415         }
 416
 417         if (expr->op != '+' && expr->op != '-')
 418                 return;
 419
 420         type = get_type(expr->left);
 421         if (type && (type->type == SYM_PTR || type->type == SYM_ARRAY))
 422                 return;
 423
 424         left = get_units(expr->left);
 425         right = get_units(expr->right);
 426
 427         if (left && !right)
 428                 set_units(expr->right, left);
 429         if (right && !left)
 430                 set_units(expr->left, right);
 431 }
 432
 433 static void match_condition_check(struct expression *expr)
 434 {
 435         struct smatch_state *left, *right;
 436         char *str;
 437
 438         if (expr->type != EXPR_COMPARE)
 439                 return;
 440
 441         left = get_units(expr->left);
 442         right = get_units(expr->right);
 443
 444         if (!left || !right)
 445                 return;
 446         if (left == right)
 447                 return;
 448
 449         str = expr_to_str(expr);
 450         sm_msg("warn: comparing different units: '%s' '%s %s %s'", str, left->name, show_special(expr->op), right->name);
 451         free_string(str);
 452 }
 453
 454 static void match_condition_set(struct expression *expr)
 455 {
 456         struct smatch_state *left, *right;
 457
 458         if (expr->type != EXPR_COMPARE)
 459                 return;
 460
 461         left = get_units(expr->left);
 462         right = get_units(expr->right);
 463
 464         if (left && !right)
 465                 set_units(expr->right, left);
 466         if (right && !left)
 467                 set_units(expr->left, right);
 468 }
 469
 470 static void match_assign(struct expression *expr)
 471 {
 472         struct smatch_state *state = NULL;
 473
 474         if (__in_fake_assign)
 475                 return;
 476
 477         switch(expr->op) {
 478         case '=':
 479                 state = get_units(expr->right);
 480                 break;
 481         case SPECIAL_SHR_ASSIGN:
 482         case SPECIAL_SHL_ASSIGN:
 483         case SPECIAL_DIV_ASSIGN:
 484         case SPECIAL_MUL_ASSIGN:
 485                 state = binop_helper(expr->left, op_remove_assign(expr->op),
 486                                      expr->right);
 487         }
 488
 489         if (state)
 490                 set_units(expr->left, state);
 491 //      else
 492 //              clear_units(expr->left);
 493 }
 494
 495 static void set_implied_units(struct expression *call, struct expression *arg, char *key, char *value)
 496 {
 497         struct smatch_state *state;
 498         struct symbol *sym;
 499         char *name;
 500
 501         state = str_to_units(value);
 502         if (!state)
 503                 return;
 504         name = get_variable_from_key(arg, key, &sym);
 505         if (!name || !sym)
 506                 goto free;
 507         set_state(my_id, name, sym, state);
 508 free:
 509         free_string(name);
 510 }
 511
 512 static void set_param_units(const char *name, struct symbol *sym, char *key, char *value)
 513 {
 514         struct smatch_state *state;
 515
 516         state = str_to_units(value);
 517         if (!state)
 518                 return;
 519         set_state(my_id, sym->ident->name, sym, state);
 520 }
 521
 522 static void set_param_units_from_table(struct expression *expr, const char *name, struct symbol *sym, void *data)
 523 {
 524         const char *value = data;
 525         struct smatch_state *state;
 526
 527         state = str_to_units(value);
 528         if (!state)
 529                 return;
 530         set_state(my_id, name, sym, state);
 531 }
 532
 533 static void match_call_info(struct expression *expr)
 534 {
 535         struct expression *arg;
 536         struct smatch_state *state;
 537         char *fn_name;
 538         int param = -1;
 539
 540         if (expr->fn->type != EXPR_SYMBOL)
 541                 return;
 542         fn_name = expr_to_var(expr->fn);
 543         if (!fn_name)
 544                 return;
 545
 546         FOR_EACH_PTR(expr->args, arg) {
 547                 param++;
 548                 state = get_units(arg);
 549                 if (!state)
 550                         continue;
 551 //              sql_insert_cache(return_implies, "0x%llx, '%s', 0, %d, %d, %d, '%s', '%s'",
 552 //                               get_base_file_id(), fn_name, is_static(expr->fn), UNITS, param, "$", state->name);
 553                 sql_insert_caller_info(expr, UNITS, param, "$", state->name);
 554
 555         } END_FOR_EACH_PTR(arg);
 556
 557         free_string(fn_name);
 558 }
 559
 560 static void process_states(void)
 561 {
 562         struct symbol *arg;
 563         struct smatch_state *state, *start_state;
 564         int param = -1;
 565
 566         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
 567                 param++;
 568                 state = get_state(my_id, arg->ident->name, arg);
 569                 if (!state || state == &merged || state == &undefined)
 570                         continue;
 571                 start_state = get_state_stree(get_start_states(), my_id, arg->ident->name, arg);
 572                 if (state == start_state)
 573                         continue;
 574                 sql_insert_cache(return_implies, "0x%llx, '%s', 0, %d, %d, %d, '%s', '%s'",
 575                                  get_base_file_id(), get_function(), fn_static(), UNITS, param, "$", state->name);
 576         } END_FOR_EACH_PTR(arg);
 577 }
 578
 579 char *get_unit_str(struct expression *expr)
 580 {
 581         struct smatch_state *state;
 582
 583         state = get_units(expr);
 584         if (!state)
 585                 return NULL;
 586         return (char *)state->name;
 587 }
 588
 589 void register_units(int id)
 590 {
 591         struct type_info *info;
 592         int i;
 593
 594         my_id = id;
 595
 596         for (i = 0; i < ARRAY_SIZE(func_table); i++) {
 597                 info = &func_table[i];
 598                 add_function_param_key_hook(info->name,
 599                                             set_param_units_from_table,
 600                                             info->param, info->key,
 601                                             (void *)info->value);
 602         }
 603
 604         add_pre_merge_hook(my_id, &pre_merge_hook);
 605         add_merge_hook(my_id, &merge_units);
 606
 607         add_hook(&match_binop_check, BINOP_HOOK);
 608         add_hook(&match_binop_set, BINOP_HOOK);
 609         add_hook(&match_condition_check, CONDITION_HOOK);
 610         add_hook(&match_condition_set, CONDITION_HOOK);
 611         add_hook(&match_assign, ASSIGNMENT_HOOK);
 612         add_hook(&match_call_info, FUNCTION_CALL_HOOK);
 613         all_return_states_hook(&process_states);
 614
 615         select_return_implies_hook(UNITS, &set_implied_units);
 616         select_caller_info_hook(&set_param_units, UNITS);
 617
 618         add_allocation_hook(&match_allocation);
 619 }