smatch_bits.c

   1 /*
   2  * Copyright (C) 2015 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 /*
  19  * This is to track when variables are masked away.
  20  *
  21  */
  22
  23 #include "smatch.h"
  24 #include "smatch_extra.h"
  25 #include "smatch_slist.h"
  26
  27 static int my_id;
  28
  29 static const struct bit_info unknown_bit_info = {
  30         .possible = -1ULL,
  31 };
  32
  33 ALLOCATOR(bit_info, "bit data");
  34 struct bit_info *alloc_bit_info(unsigned long long set, unsigned long long possible)
  35 {
  36         struct bit_info *bit_info = __alloc_bit_info(0);
  37
  38         bit_info->set = set;
  39         bit_info->possible = possible;
  40
  41         return bit_info;
  42 }
  43
  44 void set_bits_modified_expr(struct expression *expr, struct smatch_state *state)
  45 {
  46         __set_param_modified_helper(expr, state);
  47         set_state_expr(my_id, expr, state);
  48 }
  49
  50 void set_bits_modified_expr_sym(const char *name, struct symbol *sym, struct smatch_state *state)
  51 {
  52         __set_param_modified_helper_sym(name, sym, state);
  53         set_state(my_id, name, sym, state);
  54 }
  55 struct smatch_state *alloc_bstate(unsigned long long set, unsigned long long possible)
  56 {
  57         struct smatch_state *state;
  58         char buf[64];
  59
  60         state = __alloc_smatch_state(0);
  61         snprintf(buf, sizeof(buf), "0x%llx + 0x%llx", set, possible);
  62         state->name = alloc_sname(buf);
  63         state->data = alloc_bit_info(set, possible);
  64
  65         return state;
  66 }
  67
  68 struct bit_info *rl_to_binfo(struct range_list *rl)
  69 {
  70         struct bit_info *ret = __alloc_bit_info(0);
  71         sval_t sval;
  72
  73         if (rl_to_sval(rl, &sval)) {
  74                 ret->set = sval.uvalue;
  75                 ret->possible = sval.uvalue;
  76
  77                 return ret;
  78         }
  79
  80         ret->set = 0;
  81         ret->possible = sval_fls_mask(rl_max(rl));
  82         // FIXME: what about negatives?
  83
  84         return ret;
  85 }
  86
  87 static int is_unknown_binfo(struct symbol *type, struct bit_info *binfo)
  88 {
  89         if (!type)
  90                 type = &ullong_ctype;
  91
  92         if (binfo->set != 0)
  93                 return 0;
  94         if (binfo->possible < (-1ULL >> (64 - type_bits(type))))
  95                 return 0;
  96
  97         return 1;
  98 }
  99
 100 static struct smatch_state *unmatched_state(struct sm_state *sm)
 101 {
 102         struct smatch_state *estate;
 103         struct symbol *type;
 104         unsigned long long possible;
 105         struct bit_info *p;
 106
 107         estate = get_state(SMATCH_EXTRA, sm->name, sm->sym);
 108         if (estate_rl(estate)) {
 109                 p = rl_to_binfo(estate_rl(estate));
 110                 return alloc_bstate(p->set, p->possible);
 111         }
 112
 113         type = estate_type(estate);
 114         if (!type)
 115                 return alloc_bstate(0, -1ULL);
 116
 117         if (type_bits(type) == 64)
 118                 possible = -1ULL;
 119         else
 120                 possible = (1ULL << type_bits(type)) - 1;
 121
 122         return alloc_bstate(0, possible);
 123 }
 124
 125 static bool is_loop_iterator(struct expression *expr)
 126 {
 127         struct statement *pre_stmt, *loop_stmt;
 128
 129         pre_stmt = expr_get_parent_stmt(expr);
 130         if (!pre_stmt || pre_stmt->type != STMT_EXPRESSION)
 131                 return false;
 132
 133         loop_stmt = stmt_get_parent_stmt(pre_stmt);
 134         if (!loop_stmt || loop_stmt->type != STMT_ITERATOR)
 135                 return false;
 136         if (loop_stmt->iterator_pre_statement != pre_stmt)
 137                 return false;
 138
 139         return true;
 140 }
 141
 142 static bool handled_by_assign_hook(struct expression *expr)
 143 {
 144         if (!expr || expr->type != EXPR_ASSIGNMENT)
 145                 return false;
 146         if (__in_fake_assign)
 147                 return false;
 148         if (is_loop_iterator(expr))
 149                 return false;
 150
 151         if (expr->op == '=' ||
 152             expr->op == SPECIAL_OR_ASSIGN ||
 153             expr->op == SPECIAL_AND_ASSIGN)
 154                 return true;
 155
 156         return false;
 157 }
 158
 159 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
 160 {
 161         // FIXME: we really need to store the type
 162
 163         if (handled_by_assign_hook(mod_expr))
 164                 return;
 165
 166         set_bits_modified_expr_sym(sm->name, sm->sym, alloc_bstate(0, -1ULL));
 167 }
 168
 169 int binfo_equiv(struct bit_info *one, struct bit_info *two)
 170 {
 171         if (one->set == two->set &&
 172             one->possible == two->possible)
 173                 return 1;
 174         return 0;
 175 }
 176
 177 struct smatch_state *merge_bstates(struct smatch_state *one_state, struct smatch_state *two_state)
 178 {
 179         struct bit_info *one, *two;
 180
 181         one = one_state->data;
 182         two = two_state->data;
 183
 184         if (binfo_equiv(one, two))
 185                 return one_state;
 186
 187         return alloc_bstate(one->set & two->set, one->possible | two->possible);
 188 }
 189
 190 /*
 191  * The combine_bit_info() takes two bit_infos and takes creates the most
 192  * accurate picture we can assuming both are true.  Or it returns unknown if
 193  * the information is logically impossible.
 194  *
 195  * Which means that it takes the | of the ->set bits and the & of the possibly
 196  * set bits, which is the opposite of what merge_bstates() does.
 197  *
 198  */
 199 static struct bit_info *combine_bit_info(struct bit_info *one, struct bit_info *two)
 200 {
 201         struct bit_info *ret = __alloc_bit_info(0);
 202
 203         if ((one->set & two->possible) != one->set)
 204                 return alloc_bit_info(0, -1ULL);
 205         if ((two->set & one->possible) != two->set)
 206                 return alloc_bit_info(0, -1ULL);
 207
 208         ret->set = one->set | two->set;
 209         ret->possible = one->possible & two->possible;
 210
 211         return ret;
 212 }
 213
 214 static struct bit_info *binfo_AND(struct bit_info *left, struct bit_info *right)
 215 {
 216         unsigned long long set = 0;
 217         unsigned long long possible = -1ULL;
 218
 219         if (!left && !right) {
 220                 /* nothing */
 221         } else if (!left) {
 222                 possible = right->possible;
 223         } else if (!right) {
 224                 possible = left->possible;
 225         } else {
 226                 set = left->set & right->set;
 227                 possible = left->possible & right->possible;
 228         }
 229
 230         return alloc_bit_info(set, possible);
 231 }
 232
 233 static struct bit_info *binfo_OR(struct bit_info *left, struct bit_info *right)
 234 {
 235         unsigned long long set = 0;
 236         unsigned long long possible = -1ULL;
 237
 238         if (!left && !right) {
 239                 /* nothing */
 240         } else if (!left) {
 241                 set = right->set;
 242         } else if (!right) {
 243                 set = left->set;
 244         } else {
 245                 set = left->set | right->set;
 246                 possible = left->possible | right->possible;
 247         }
 248
 249         return alloc_bit_info(set, possible);
 250 }
 251
 252 struct bit_info *get_bit_info(struct expression *expr)
 253 {
 254         struct range_list *rl;
 255         struct smatch_state *bstate;
 256         struct bit_info tmp;
 257         struct bit_info *extra_info;
 258         struct bit_info *bit_info;
 259         sval_t known;
 260
 261         expr = strip_parens(expr);
 262
 263         if (get_implied_value(expr, &known))
 264                 return alloc_bit_info(known.value, known.value);
 265
 266         if (expr->type == EXPR_BINOP) {
 267                 if (expr->op == '&')
 268                         return binfo_AND(get_bit_info(expr->left),
 269                                          get_bit_info(expr->right));
 270                 if (expr->op == '|')
 271                         return binfo_OR(get_bit_info(expr->left),
 272                                         get_bit_info(expr->right));
 273         }
 274
 275         if (get_implied_rl(expr, &rl))
 276                 extra_info = rl_to_binfo(rl);
 277         else {
 278                 struct symbol *type;
 279
 280                 tmp = unknown_bit_info;
 281                 extra_info = &tmp;
 282
 283                 type = get_type(expr);
 284                 if (!type)
 285                         type = &ullong_ctype;
 286                 if (type_bits(type) == 64)
 287                         extra_info->possible = -1ULL;
 288                 else
 289                         extra_info->possible = (1ULL << type_bits(type)) - 1;
 290         }
 291
 292         bstate = get_state_expr(my_id, expr);
 293         if (bstate)
 294                 bit_info = bstate->data;
 295         else
 296                 bit_info = (struct bit_info *)&unknown_bit_info;
 297
 298         return combine_bit_info(extra_info, bit_info);
 299 }
 300
 301 static int is_single_bit(sval_t sval)
 302 {
 303         int i;
 304         int count = 0;
 305
 306         for (i = 0; i < 64; i++) {
 307                 if (sval.uvalue & 1ULL << i &&
 308                     count++)
 309                         return 0;
 310         }
 311         if (count == 1)
 312                 return 1;
 313         return 0;
 314 }
 315
 316 static void match_compare(struct expression *expr)
 317 {
 318         sval_t val;
 319
 320         if (expr->type != EXPR_COMPARE)
 321                 return;
 322         if (expr->op != SPECIAL_EQUAL &&
 323             expr->op != SPECIAL_NOTEQUAL)
 324                 return;
 325
 326         if (!get_implied_value(expr->right, &val))
 327                 return;
 328
 329         set_true_false_states_expr(my_id, expr->left,
 330                         (expr->op == SPECIAL_EQUAL) ? alloc_bstate(val.uvalue, val.uvalue) : NULL,
 331                         (expr->op == SPECIAL_EQUAL) ? NULL : alloc_bstate(val.uvalue, val.uvalue));
 332 }
 333
 334 static void match_assign(struct expression *expr)
 335 {
 336         struct bit_info *start, *binfo;
 337         struct smatch_state *new;
 338
 339         if (!handled_by_assign_hook(expr))
 340                 return;
 341
 342         binfo = get_bit_info(expr->right);
 343         if (!binfo)
 344                 return;
 345         if (expr->op == '=') {
 346                 if (is_unknown_binfo(get_type(expr->left), binfo))
 347                         return;
 348                 set_bits_modified_expr(expr->left, alloc_bstate(binfo->set, binfo->possible));
 349         } else if (expr->op == SPECIAL_OR_ASSIGN) {
 350                 start = get_bit_info(expr->left);
 351                 new = alloc_bstate(start->set | binfo->set, start->possible | binfo->possible);
 352                 set_bits_modified_expr(expr->left, new);
 353         } else if (expr->op == SPECIAL_AND_ASSIGN) {
 354                 start = get_bit_info(expr->left);
 355                 new = alloc_bstate(start->set & binfo->set, start->possible & binfo->possible);
 356                 set_bits_modified_expr(expr->left, new);
 357         }
 358 }
 359
 360 static void match_condition(struct expression *expr)
 361 {
 362         struct bit_info *orig;
 363         struct bit_info true_info;
 364         struct bit_info false_info;
 365         sval_t right;
 366
 367         if (expr->type != EXPR_BINOP ||
 368             expr->op != '&')
 369                 return;
 370
 371         if (!get_value(expr->right, &right))
 372                 return;
 373
 374         orig = get_bit_info(expr->left);
 375         true_info = *orig;
 376         false_info = *orig;
 377
 378         if (right.uvalue == 0 || is_single_bit(right))
 379                 true_info.set &= right.uvalue;
 380
 381         true_info.possible &= right.uvalue;
 382         false_info.possible &= ~right.uvalue;
 383
 384         set_true_false_states_expr(my_id, expr->left,
 385                                    alloc_bstate(true_info.set, true_info.possible),
 386                                    alloc_bstate(false_info.set, false_info.possible));
 387 }
 388
 389 static void match_call_info(struct expression *expr)
 390 {
 391         struct bit_info *binfo, *rl_binfo;
 392         struct expression *arg;
 393         struct range_list *rl;
 394         char buf[64];
 395         int i;
 396
 397         i = -1;
 398         FOR_EACH_PTR(expr->args, arg) {
 399                 i++;
 400                 binfo = get_bit_info(arg);
 401                 if (!binfo)
 402                         continue;
 403                 if (is_unknown_binfo(get_type(arg), binfo))
 404                         continue;
 405                 if (get_implied_rl(arg, &rl)) {
 406                         rl_binfo = rl_to_binfo(rl);
 407                         if (binfo_equiv(rl_binfo, binfo))
 408                                 continue;
 409                 }
 410                 // If is just non-negative continue
 411                 // If ->set == ->possible continue
 412                 snprintf(buf, sizeof(buf), "0x%llx,0x%llx", binfo->set, binfo->possible);
 413                 sql_insert_caller_info(expr, BIT_INFO, i, "$", buf);
 414         } END_FOR_EACH_PTR(arg);
 415 }
 416
 417 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
 418 {
 419         struct bit_info *binfo = sm->state->data;
 420         struct smatch_state *estate;
 421         struct bit_info *implied_binfo;
 422         char buf[64];
 423
 424         if (!binfo)
 425                 return;
 426
 427         /* This means it can only be one value, so it's handled by smatch_extra. */
 428         if (binfo->set == binfo->possible)
 429                 return;
 430
 431         estate = get_state(SMATCH_EXTRA, sm->name, sm->sym);
 432         if (is_unknown_binfo(estate_type(estate), binfo))
 433                 return;
 434
 435         if (estate_rl(estate)) {
 436                 sval_t sval;
 437
 438                 if (estate_get_single_value(estate, &sval))
 439                         return;
 440
 441                 implied_binfo = rl_to_binfo(estate_rl(estate));
 442                 if (binfo_equiv(implied_binfo, binfo))
 443                         return;
 444         }
 445
 446         snprintf(buf, sizeof(buf), "0x%llx,0x%llx", binfo->set, binfo->possible);
 447         sql_insert_caller_info(call, BIT_INFO, param, printed_name, buf);
 448 }
 449
 450 static void set_param_bits(const char *name, struct symbol *sym, char *key, char *value)
 451 {
 452         char fullname[256];
 453         unsigned long long set, possible;
 454
 455         if (strcmp(key, "*$") == 0)
 456                 snprintf(fullname, sizeof(fullname), "*%s", name);
 457         else if (strncmp(key, "$", 1) == 0)
 458                 snprintf(fullname, 256, "%s%s", name, key + 1);
 459         else
 460                 return;
 461
 462         set = strtoull(value, &value, 16);
 463         if (*value != ',')
 464                 return;
 465         value++;
 466         possible = strtoull(value, &value, 16);
 467
 468         set_bits_modified_expr_sym(fullname, sym, alloc_bstate(set, possible));
 469 }
 470
 471 static void returns_bit_set(struct expression *expr, int param, char *key, char *value)
 472 {
 473         char *name;
 474         struct symbol *sym;
 475         unsigned long long set;
 476         char *pEnd;
 477
 478         name = get_name_sym_from_key(expr, param, key, &sym);
 479
 480         if (!name)
 481                 return;
 482
 483         set = strtoull(value, &pEnd, 16);
 484         set_state(my_id, name, sym, alloc_bstate(set, -1ULL));
 485 }
 486
 487 static void returns_bit_clear(struct expression *expr, int param, char *key, char *value)
 488 {
 489         char *name;
 490         struct symbol *sym;
 491         unsigned long long possible;
 492         char *pEnd;
 493         struct bit_info *binfo;
 494
 495         name = get_name_sym_from_key(expr, param, key, &sym);
 496
 497         if (!name)
 498                 return;
 499
 500         binfo = get_bit_info(expr);
 501         possible = strtoull(value, &pEnd, 16);
 502         set_state(my_id, name, sym, alloc_bstate(possible & binfo->set,
 503                                                  possible & binfo->possible));
 504 }
 505
 506 void register_bits(int id)
 507 {
 508         my_id = id;
 509
 510         set_dynamic_states(my_id);
 511
 512         add_unmatched_state_hook(my_id, &unmatched_state);
 513         add_merge_hook(my_id, &merge_bstates);
 514
 515         add_hook(&match_condition, CONDITION_HOOK);
 516         add_hook(&match_compare, CONDITION_HOOK);
 517         add_hook(&match_assign, ASSIGNMENT_HOOK);
 518         add_modification_hook(my_id, &match_modify);
 519
 520         add_hook(&match_call_info, FUNCTION_CALL_HOOK);
 521         add_member_info_callback(my_id, struct_member_callback);
 522         select_caller_info_hook(set_param_bits, BIT_INFO);
 523
 524         select_return_states_hook(BIT_SET, &returns_bit_set);
 525         select_return_states_hook(BIT_CLEAR, &returns_bit_clear);
 526 }