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