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