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 GLOBAL_STATE(unit_bit);
  24 GLOBAL_STATE(unit_byte);
  25 GLOBAL_STATE(unit_array_size);
  26 GLOBAL_STATE(unit_long);
  27 GLOBAL_STATE(unit_page);
  28 GLOBAL_STATE(unit_msec);
  29 GLOBAL_STATE(unit_ns);
  30 GLOBAL_STATE(unit_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         { "unit_msecs_to_jiffies_timeout", UNITS, -1, "$", "unit_jiffy" },
  42         { "round_jiffies_up_relative", UNITS, -1, "$", "unit_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, "unit_bit") == 0)
  51                 return &unit_bit;
  52         if (strcmp(str, "unit_byte") == 0)
  53                 return &unit_byte;
  54         if (strcmp(str, "unit_page") == 0)
  55                 return &unit_page;
  56         if (strcmp(str, "unit_msec") == 0)
  57                 return &unit_msec;
  58         if (strcmp(str, "unit_jiffy") == 0)
  59                 return &unit_jiffy;
  60         if (strcmp(str, "unit_long") == 0)
  61                 return &unit_long;
  62         if (strcmp(str, "unit_array_size") == 0)
  63                 return &unit_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 struct smatch_state *merge_units(struct smatch_state *s1, struct smatch_state *s2)
  73 {
  74         if (s1 == &undefined)
  75                 return s2;
  76         if (s2 == &undefined)
  77                 return s1;
  78         return &merged;
  79 }
  80
  81 static bool is_ignored_type(char *name)
  82 {
  83         if (!name)
  84                 return false;
  85         if (strcmp(name, "(union anonymous)->__val") == 0)
  86                 return true;
  87         if (strncmp(name, "(struct fs_parse_result)", 24) == 0)
  88                 return true;
  89         return false;
  90 }
  91
  92 static bool ARRAY_SIZE_is_bytes(struct expression *expr)
  93 {
  94         sval_t sval;
  95
  96         expr = strip_expr(expr);
  97         if (!expr)
  98                 return false;
  99
 100         /*
 101          * The kernel ARRAY_SIZE() macro is sizeof(array)/sizeof(array[0]) + 0
 102          * where 0 does some fancy type checking.
 103          *
 104          */
 105         if (expr->type == EXPR_BINOP &&
 106             expr->op == '+' &&
 107             expr_is_zero(expr->right))
 108                 return ARRAY_SIZE_is_bytes(expr->left);
 109
 110         if (expr->type != EXPR_BINOP || expr->op != '/')
 111                 return false;
 112         if (!get_value(expr->right, &sval) || sval.value != 1)
 113                 return false;
 114         return true;
 115 }
 116
 117 static void store_type_in_db(struct expression *expr, struct smatch_state *state)
 118 {
 119         char *member;
 120
 121         member = get_member_name(expr);
 122         if (!member)
 123                 return;
 124         if (is_ignored_type(member))
 125                 return;
 126
 127         sql_insert_cache(type_info, "0x%llx, %d, '%s', '%s'", get_base_file_id(), UNITS, member, state->name);
 128 }
 129
 130 static void set_units(struct expression *expr, struct smatch_state *state)
 131 {
 132         if (!state)
 133                 return;
 134
 135         set_state_expr(my_id, expr, state);
 136         store_type_in_db(expr, state);
 137 }
 138
 139 static bool is_PAGE_SHIFT(struct expression *expr)
 140 {
 141         char *macro;
 142
 143         macro = get_macro_name(expr->pos);
 144         if (macro && strcmp(macro, "PAGE_SHIFT") == 0)
 145                 return true;
 146         return false;
 147 }
 148
 149 static bool is_PAGE_SIZE(struct expression *expr)
 150 {
 151         char *macro;
 152
 153         macro = get_macro_name(expr->pos);
 154         if (macro && strcmp(macro, "PAGE_SIZE") == 0)
 155                 return true;
 156         return false;
 157 }
 158
 159 static bool is_BITS_PER_LONG(struct expression *expr)
 160 {
 161         char *macro;
 162
 163         macro = get_macro_name(expr->pos);
 164         if (macro && strcmp(macro, "BITS_PER_LONG") == 0)
 165                 return true;
 166         return false;
 167 }
 168
 169 static struct smatch_state *binop_helper(struct expression *left, int op, struct expression *right)
 170 {
 171         struct smatch_state *left_state, *right_state;
 172         sval_t val;
 173
 174         switch(op) {
 175         case '-':
 176                 // subtracting pointers gives unit_byte
 177                 /* fall through */
 178         case '+':
 179                 left_state = get_units(left);
 180                 right_state = get_units(right);
 181                 if (left_state == &unit_array_size ||
 182                     right_state == &unit_array_size)
 183                         return NULL;
 184
 185                 return left_state ? left_state : right_state;
 186         case '*':
 187                 /* FIXME: A multiply is almost always bytes but it can be bits. */
 188                 if (is_PAGE_SIZE(right))
 189                         return &unit_byte;
 190                 if (!get_implied_value(right, &val))
 191                         return NULL;
 192                 /* 4096 is almost always a unit_page -> bytes converstion */
 193                 if (val.value == 4096)
 194                         return &unit_byte;
 195                 return NULL;
 196         case '/':
 197                 if (is_BITS_PER_LONG(right))
 198                         return &unit_long;
 199                 if (is_PAGE_SIZE(right))
 200                         return &unit_page;
 201                 if (!get_implied_value(right, &val))
 202                         return NULL;
 203                 if (val.value == 4096)
 204                         return &unit_page;
 205                 return NULL;
 206         case SPECIAL_LEFTSHIFT:
 207                 if (is_PAGE_SHIFT(right))
 208                         return &unit_byte;
 209                 return NULL;
 210         case SPECIAL_RIGHTSHIFT:
 211                 if (is_PAGE_SHIFT(right))
 212                         return &unit_page;
 213                 return NULL;
 214         }
 215         return NULL;
 216 }
 217
 218 static struct smatch_state *get_units_binop(struct expression *expr)
 219 {
 220         return binop_helper(expr->left, expr->op, expr->right);
 221 }
 222
 223 static struct smatch_state *get_units_call(struct expression *expr)
 224 {
 225         expr = strip_expr(expr);
 226         if (!expr || expr->type != EXPR_CALL)
 227                 return NULL;
 228
 229         if (sym_name_is("unit_msecs_to_jiffies", expr->fn))
 230                 return &unit_jiffy;
 231         if (sym_name_is("jiffies_to_unit_msecs", expr->fn))
 232                 return &unit_msec;
 233
 234         return NULL;
 235 }
 236
 237 static int db_units(void *_units, int argc, char **argv, char **azColName)
 238 {
 239         char **units = _units;
 240
 241         if (*units) {
 242                 if (strcmp(*units, argv[0]) == 0)
 243                         return 0;
 244                 free_string(*units);
 245                 *units = alloc_string("unknown");
 246                 return 0;
 247
 248         }
 249         *units = alloc_string(argv[0]);
 250         return 0;
 251 }
 252
 253 static struct smatch_state *get_units_from_type(struct expression *expr)
 254 {
 255         char *member;
 256         char *units = NULL;
 257         struct smatch_state *ret = NULL;
 258
 259         member = get_member_name(expr);
 260         if (!member)
 261                 return NULL;
 262         if (strcmp(member, "(struct vm_area_struct)->vm_pgoff") == 0)
 263                 return &unit_page;
 264         cache_sql(&db_units, &units, "select value from type_info where type = %d and key = '%s';",
 265                   UNITS, member);
 266         run_sql(&db_units, &units, "select value from type_info where type = %d and key = '%s';",
 267                 UNITS, member);
 268         free_string(member);
 269         if (!units)
 270                 return NULL;
 271
 272         ret = str_to_units(units);
 273
 274         free_string(units);
 275
 276         return ret;
 277 }
 278
 279 struct smatch_state *get_units(struct expression *expr)
 280 {
 281         struct smatch_state *state;
 282         char *ident;
 283
 284         expr = strip_expr(expr);
 285         if (!expr)
 286                 return NULL;
 287
 288         if (expr_is_zero(expr))
 289                 return NULL;
 290
 291         if (expr->type == EXPR_PTRSIZEOF ||
 292             expr->type == EXPR_SIZEOF)
 293                 return &unit_byte;
 294
 295         ident = pos_ident(expr->pos);
 296         if (ident) {
 297                 if (strcmp(ident, "sizeof") == 0 ||
 298                     strcmp(ident, "PAGE_SIZE") == 0)
 299                         return &unit_byte;
 300                 if (strcmp(ident, "jiffies") == 0)
 301                         return &unit_jiffy;
 302                 if (strcmp(ident, "BITS_PER_LONG") == 0)
 303                         return &unit_bit;
 304                 if (strcmp(ident, "BITS_PER_LONG_LONG") == 0)
 305                         return &unit_bit;
 306                 if (strcmp(ident, "ARRAY_SIZE") == 0) {
 307                         if (ARRAY_SIZE_is_bytes(expr))
 308                                 return &unit_byte;
 309                         return &unit_array_size;
 310                 }
 311         }
 312
 313         if (expr->type == EXPR_BINOP)
 314                 return get_units_binop(expr);
 315
 316         if (expr->type == EXPR_CALL)
 317                 return get_units_call(expr);
 318
 319         state = get_state_expr(my_id, expr);
 320         if (state == &merged || state == &undefined)
 321                 return NULL;
 322         if (state)
 323                 return state;
 324
 325         return get_units_from_type(expr);
 326 }
 327
 328 bool is_array_size_units(struct expression *expr)
 329 {
 330         return get_units(expr) == &unit_array_size;
 331 }
 332
 333 static void match_allocation(struct expression *expr,
 334                              const char *name, struct symbol *sym,
 335                              struct allocation_info *info)
 336 {
 337         struct expression *right, *left;
 338
 339         if (info->nr_elems && info->elem_size) {
 340                 left = info->nr_elems;
 341                 right = info->elem_size;
 342         } else if (info->total_size &&
 343                    info->total_size->type == EXPR_BINOP &&
 344                    info->total_size->op == '*') {
 345                 left = strip_expr(info->total_size->left);
 346                 right = strip_expr(info->total_size->right);
 347         } else {
 348                 return;
 349         }
 350
 351         if (get_units(left) == &unit_byte)
 352                 set_units(right, &unit_array_size);
 353         if (get_units(right) == &unit_byte)
 354                 set_units(left, &unit_array_size);
 355 }
 356
 357 static void match_binop_set(struct expression *expr)
 358 {
 359         struct smatch_state *left, *right;
 360         struct symbol *type;
 361
 362         if (expr->op == SPECIAL_LEFTSHIFT && is_PAGE_SHIFT(expr->right)) {
 363                 set_units(expr->left, &unit_page);
 364                 return;
 365         }
 366
 367         if (expr->op == SPECIAL_RIGHTSHIFT && is_PAGE_SHIFT(expr->right)) {
 368                 set_units(expr->left, &unit_byte);
 369                 return;
 370         }
 371
 372         if (expr->op != '+' && expr->op != '-')
 373                 return;
 374
 375         type = get_type(expr->left);
 376         if (type && (type->type == SYM_PTR || type->type == SYM_ARRAY))
 377                 return;
 378
 379         left = get_units(expr->left);
 380         right = get_units(expr->right);
 381
 382         if (left && !right)
 383                 set_units(expr->right, left);
 384         if (right && !left)
 385                 set_units(expr->left, right);
 386 }
 387
 388 static void match_condition_set(struct expression *expr)
 389 {
 390         struct smatch_state *left, *right;
 391
 392         if (expr->type != EXPR_COMPARE)
 393                 return;
 394
 395         left = get_units(expr->left);
 396         right = get_units(expr->right);
 397
 398         if (left && !right)
 399                 set_units(expr->right, left);
 400         if (right && !left)
 401                 set_units(expr->left, right);
 402 }
 403
 404 static void match_assign(struct expression *expr)
 405 {
 406         struct smatch_state *state = NULL;
 407
 408         if (__in_fake_assign)
 409                 return;
 410
 411         switch(expr->op) {
 412         case '=':
 413                 state = get_units(expr->right);
 414                 break;
 415         case SPECIAL_SHR_ASSIGN:
 416         case SPECIAL_SHL_ASSIGN:
 417         case SPECIAL_DIV_ASSIGN:
 418         case SPECIAL_MUL_ASSIGN:
 419                 state = binop_helper(expr->left, op_remove_assign(expr->op),
 420                                      expr->right);
 421         }
 422
 423         if (state)
 424                 set_units(expr->left, state);
 425 //      else
 426 //              clear_units(expr->left);
 427 }
 428
 429 static void set_implied_units(struct expression *call, struct expression *arg, char *key, char *value)
 430 {
 431         struct smatch_state *state;
 432         struct symbol *sym;
 433         char *name;
 434
 435         state = str_to_units(value);
 436         if (!state)
 437                 return;
 438         name = get_variable_from_key(arg, key, &sym);
 439         if (!name || !sym)
 440                 goto free;
 441         set_state(my_id, name, sym, state);
 442 free:
 443         free_string(name);
 444 }
 445
 446 static void set_param_units(const char *name, struct symbol *sym, char *key, char *value)
 447 {
 448         struct smatch_state *state;
 449
 450         state = str_to_units(value);
 451         if (!state)
 452                 return;
 453         set_state(my_id, sym->ident->name, sym, state);
 454 }
 455
 456 static void set_param_units_from_table(struct expression *expr, const char *name, struct symbol *sym, void *data)
 457 {
 458         const char *value = data;
 459         struct smatch_state *state;
 460
 461         state = str_to_units(value);
 462         if (!state)
 463                 return;
 464         set_state(my_id, name, sym, state);
 465 }
 466
 467 static void match_call_info(struct expression *expr)
 468 {
 469         struct expression *arg;
 470         struct smatch_state *state;
 471         char *fn_name;
 472         int param = -1;
 473
 474         if (expr->fn->type != EXPR_SYMBOL)
 475                 return;
 476         fn_name = expr_to_var(expr->fn);
 477         if (!fn_name)
 478                 return;
 479
 480         FOR_EACH_PTR(expr->args, arg) {
 481                 param++;
 482                 state = get_units(arg);
 483                 if (!state)
 484                         continue;
 485 //              sql_insert_cache(return_implies, "0x%llx, '%s', 0, %d, %d, %d, '%s', '%s'",
 486 //                               get_base_file_id(), fn_name, is_static(expr->fn), UNITS, param, "$", state->name);
 487                 sql_insert_caller_info(expr, UNITS, param, "$", state->name);
 488
 489         } END_FOR_EACH_PTR(arg);
 490
 491         free_string(fn_name);
 492 }
 493
 494 static void process_states(void)
 495 {
 496         struct symbol *arg;
 497         struct smatch_state *state, *start_state;
 498         int param = -1;
 499
 500         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
 501                 param++;
 502                 state = get_state(my_id, arg->ident->name, arg);
 503                 if (!state || state == &merged || state == &undefined)
 504                         continue;
 505                 start_state = get_state_stree(get_start_states(), my_id, arg->ident->name, arg);
 506                 if (state == start_state)
 507                         continue;
 508                 sql_insert_cache(return_implies, "0x%llx, '%s', 0, %d, %d, %d, '%s', '%s'",
 509                                  get_base_file_id(), get_function(), fn_static(), UNITS, param, "$", state->name);
 510         } END_FOR_EACH_PTR(arg);
 511 }
 512
 513 char *get_unit_str(struct expression *expr)
 514 {
 515         struct smatch_state *state;
 516
 517         state = get_units(expr);
 518         if (!state)
 519                 return NULL;
 520         return (char *)state->name;
 521 }
 522
 523 void register_units(int id)
 524 {
 525         struct type_info *info;
 526         int i;
 527
 528         my_id = id;
 529
 530         for (i = 0; i < ARRAY_SIZE(func_table); i++) {
 531                 info = &func_table[i];
 532                 add_function_param_key_hook(info->name,
 533                                             set_param_units_from_table,
 534                                             info->param, info->key,
 535                                             (void *)info->value);
 536         }
 537
 538         add_merge_hook(my_id, &merge_units);
 539
 540         add_hook(&match_binop_set, BINOP_HOOK);
 541         add_hook(&match_condition_set, CONDITION_HOOK);
 542         add_hook(&match_assign, ASSIGNMENT_HOOK);
 543         add_hook(&match_call_info, FUNCTION_CALL_HOOK);
 544         all_return_states_hook(&process_states);
 545
 546         select_return_implies_hook(UNITS, &set_implied_units);
 547         select_caller_info_hook(&set_param_units, UNITS);
 548
 549         add_allocation_hook(&match_allocation);
 550 }