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