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