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