1 /* 2 * Copyright (C) 2010 Dan Carpenter. 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 * smatch_dinfo.c has helper functions for handling data_info structs 20 * 21 */ 22 23 #include <stdlib.h> 24 #ifndef __USE_ISOC99 25 #define __USE_ISOC99 26 #endif 27 #include <limits.h> 28 #include "parse.h" 29 #include "smatch.h" 30 #include "smatch_slist.h" 31 #include "smatch_extra.h" 32 33 struct smatch_state *merge_estates(struct smatch_state *s1, struct smatch_state *s2) 34 { 35 struct smatch_state *tmp; 36 struct range_list *value_ranges; 37 struct related_list *rlist; 38 39 if (estates_equiv(s1, s2)) 40 return s1; 41 42 value_ranges = rl_union(estate_rl(s1), estate_rl(s2)); 43 tmp = alloc_estate_rl(value_ranges); 44 rlist = get_shared_relations(estate_related(s1), estate_related(s2)); 45 set_related(tmp, rlist); 46 47 if ((estate_has_hard_max(s1) && (!estate_rl(s2) || estate_has_hard_max(s2))) || 48 (estate_has_hard_max(s2) && (!estate_rl(s1) || estate_has_hard_max(s1)))) 49 estate_set_hard_max(tmp); 50 51 estate_set_fuzzy_max(tmp, sval_max(estate_get_fuzzy_max(s1), estate_get_fuzzy_max(s2))); 52 53 if (estate_capped(s1) && estate_capped(s2)) 54 estate_set_capped(tmp); 55 56 if (estate_treat_untagged(s1) && estate_treat_untagged(s2)) 57 estate_set_treat_untagged(tmp); 58 59 if (estate_new(s1) || estate_new(s2)) 60 estate_set_new(tmp); 61 62 return tmp; 63 } 64 65 struct data_info *get_dinfo(struct smatch_state *state) 66 { 67 if (!state) 68 return NULL; 69 return (struct data_info *)state->data; 70 } 71 72 struct range_list *estate_rl(struct smatch_state *state) 73 { 74 if (!state) 75 return NULL; 76 return get_dinfo(state)->value_ranges; 77 } 78 79 struct related_list *estate_related(struct smatch_state *state) 80 { 81 if (!state) 82 return NULL; 83 return get_dinfo(state)->related; 84 } 85 86 sval_t estate_get_fuzzy_max(struct smatch_state *state) 87 { 88 sval_t empty = {}; 89 90 if (!state || !get_dinfo(state)) 91 return empty; 92 return get_dinfo(state)->fuzzy_max; 93 } 94 95 int estate_has_fuzzy_max(struct smatch_state *state) 96 { 97 if (estate_get_fuzzy_max(state).type) 98 return 1; 99 return 0; 100 } 101 102 void estate_set_fuzzy_max(struct smatch_state *state, sval_t fuzzy_max) 103 { 104 if (!rl_has_sval(estate_rl(state), fuzzy_max)) 105 return; 106 get_dinfo(state)->fuzzy_max = fuzzy_max; 107 } 108 109 void estate_copy_fuzzy_max(struct smatch_state *new, struct smatch_state *old) 110 { 111 if (!estate_has_fuzzy_max(old)) 112 return; 113 estate_set_fuzzy_max(new, estate_get_fuzzy_max(old)); 114 } 115 116 void estate_clear_fuzzy_max(struct smatch_state *state) 117 { 118 sval_t empty = {}; 119 120 get_dinfo(state)->fuzzy_max = empty; 121 } 122 123 int estate_has_hard_max(struct smatch_state *state) 124 { 125 if (!state || !estate_rl(state)) 126 return 0; 127 return get_dinfo(state)->hard_max; 128 } 129 130 void estate_set_hard_max(struct smatch_state *state) 131 { 132 /* pointers don't have a hard max */ 133 if (is_ptr_type(estate_type(state))) 134 return; 135 get_dinfo(state)->hard_max = 1; 136 } 137 138 void estate_clear_hard_max(struct smatch_state *state) 139 { 140 get_dinfo(state)->hard_max = 0; 141 } 142 143 int estate_get_hard_max(struct smatch_state *state, sval_t *sval) 144 { 145 if (!state || !get_dinfo(state)->hard_max || !estate_rl(state)) 146 return 0; 147 *sval = rl_max(estate_rl(state)); 148 return 1; 149 } 150 151 bool estate_capped(struct smatch_state *state) 152 { 153 if (!state) 154 return false; 155 /* impossible states are capped */ 156 if (!estate_rl(state)) 157 return true; 158 return get_dinfo(state)->capped; 159 } 160 161 void estate_set_capped(struct smatch_state *state) 162 { 163 get_dinfo(state)->capped = true; 164 } 165 166 bool estate_treat_untagged(struct smatch_state *state) 167 { 168 if (!state) 169 return false; 170 171 /* impossible states are capped */ 172 if (!estate_rl(state)) 173 return true; 174 175 return get_dinfo(state)->treat_untagged; 176 } 177 178 void estate_set_treat_untagged(struct smatch_state *state) 179 { 180 get_dinfo(state)->treat_untagged = true; 181 } 182 183 bool estate_new(struct smatch_state *state) 184 { 185 if (!estate_rl(state)) 186 return false; 187 return get_dinfo(state)->set; 188 } 189 190 void estate_set_new(struct smatch_state *state) 191 { 192 get_dinfo(state)->set = true; 193 } 194 195 sval_t estate_min(struct smatch_state *state) 196 { 197 return rl_min(estate_rl(state)); 198 } 199 200 sval_t estate_max(struct smatch_state *state) 201 { 202 return rl_max(estate_rl(state)); 203 } 204 205 struct symbol *estate_type(struct smatch_state *state) 206 { 207 return rl_max(estate_rl(state)).type; 208 } 209 210 static int rlists_equiv(struct related_list *one, struct related_list *two) 211 { 212 struct relation *one_rel; 213 struct relation *two_rel; 214 215 PREPARE_PTR_LIST(one, one_rel); 216 PREPARE_PTR_LIST(two, two_rel); 217 for (;;) { 218 if (!one_rel && !two_rel) 219 return 1; 220 if (!one_rel || !two_rel) 221 return 0; 222 if (one_rel->sym != two_rel->sym) 223 return 0; 224 if (strcmp(one_rel->name, two_rel->name)) 225 return 0; 226 NEXT_PTR_LIST(one_rel); 227 NEXT_PTR_LIST(two_rel); 228 } 229 FINISH_PTR_LIST(two_rel); 230 FINISH_PTR_LIST(one_rel); 231 232 return 1; 233 } 234 235 int estates_equiv(struct smatch_state *one, struct smatch_state *two) 236 { 237 if (!one || !two) 238 return 0; 239 if (one == two) 240 return 1; 241 if (!rlists_equiv(estate_related(one), estate_related(two))) 242 return 0; 243 if (estate_capped(one) != estate_capped(two)) 244 return 0; 245 if (estate_treat_untagged(one) != estate_treat_untagged(two)) 246 return 0; 247 if (estate_has_hard_max(one) != estate_has_hard_max(two)) 248 return 0; 249 if (estate_new(one) != estate_new(two)) 250 return 0; 251 if (strcmp(one->name, two->name) == 0) 252 return 1; 253 return 0; 254 } 255 256 int estate_is_whole(struct smatch_state *state) 257 { 258 return is_whole_rl(estate_rl(state)); 259 } 260 261 int estate_is_empty(struct smatch_state *state) 262 { 263 return state && !estate_rl(state); 264 } 265 266 int estate_is_unknown(struct smatch_state *state) 267 { 268 if (!estate_is_whole(state)) 269 return 0; 270 if (estate_related(state)) 271 return 0; 272 if (estate_has_fuzzy_max(state)) 273 return 0; 274 return 1; 275 } 276 277 int estate_get_single_value(struct smatch_state *state, sval_t *sval) 278 { 279 sval_t min, max; 280 281 if (!estate_rl(state)) 282 return 0; 283 min = rl_min(estate_rl(state)); 284 max = rl_max(estate_rl(state)); 285 if (sval_cmp(min, max) != 0) 286 return 0; 287 *sval = min; 288 return 1; 289 } 290 291 static struct data_info *alloc_dinfo(void) 292 { 293 struct data_info *ret; 294 295 ret = __alloc_data_info(0); 296 memset(ret, 0, sizeof(*ret)); 297 return ret; 298 } 299 300 static struct data_info *alloc_dinfo_range(sval_t min, sval_t max) 301 { 302 struct data_info *ret; 303 304 ret = alloc_dinfo(); 305 add_range(&ret->value_ranges, min, max); 306 return ret; 307 } 308 309 static struct data_info *alloc_dinfo_range_list(struct range_list *rl) 310 { 311 struct data_info *ret; 312 313 ret = alloc_dinfo(); 314 ret->value_ranges = rl; 315 return ret; 316 } 317 318 static struct data_info *clone_dinfo(struct data_info *dinfo) 319 { 320 struct data_info *ret; 321 322 ret = alloc_dinfo(); 323 ret->related = clone_related_list(dinfo->related); 324 ret->value_ranges = clone_rl(dinfo->value_ranges); 325 ret->hard_max = dinfo->hard_max; 326 ret->fuzzy_max = dinfo->fuzzy_max; 327 return ret; 328 } 329 330 struct smatch_state *clone_estate(struct smatch_state *state) 331 { 332 struct smatch_state *ret; 333 334 if (!state) 335 return NULL; 336 337 ret = __alloc_smatch_state(0); 338 ret->name = state->name; 339 ret->data = clone_dinfo(get_dinfo(state)); 340 return ret; 341 } 342 343 struct smatch_state *clone_partial_estate(struct smatch_state *state, struct range_list *rl) 344 { 345 struct smatch_state *ret; 346 347 if (!state) 348 return NULL; 349 350 rl = cast_rl(estate_type(state), rl); 351 352 ret = alloc_estate_rl(rl); 353 set_related(ret, clone_related_list(estate_related(state))); 354 if (estate_has_hard_max(state)) 355 estate_set_hard_max(ret); 356 if (estate_has_fuzzy_max(state)) 357 estate_set_fuzzy_max(ret, estate_get_fuzzy_max(state)); 358 359 return ret; 360 } 361 362 struct smatch_state *alloc_estate_empty(void) 363 { 364 struct smatch_state *state; 365 struct data_info *dinfo; 366 367 dinfo = alloc_dinfo(); 368 state = __alloc_smatch_state(0); 369 state->data = dinfo; 370 state->name = ""; 371 return state; 372 } 373 374 struct smatch_state *alloc_estate_whole(struct symbol *type) 375 { 376 return alloc_estate_rl(alloc_whole_rl(type)); 377 } 378 379 struct smatch_state *extra_empty(void) 380 { 381 struct smatch_state *ret; 382 383 ret = __alloc_smatch_state(0); 384 ret->name = "empty"; 385 ret->data = alloc_dinfo(); 386 return ret; 387 } 388 389 struct smatch_state *alloc_estate_sval(sval_t sval) 390 { 391 struct smatch_state *state; 392 393 state = __alloc_smatch_state(0); 394 state->data = alloc_dinfo_range(sval, sval); 395 state->name = show_rl(get_dinfo(state)->value_ranges); 396 estate_set_hard_max(state); 397 estate_set_fuzzy_max(state, sval); 398 return state; 399 } 400 401 struct smatch_state *alloc_estate_range(sval_t min, sval_t max) 402 { 403 struct smatch_state *state; 404 405 state = __alloc_smatch_state(0); 406 state->data = alloc_dinfo_range(min, max); 407 state->name = show_rl(get_dinfo(state)->value_ranges); 408 return state; 409 } 410 411 struct smatch_state *alloc_estate_rl(struct range_list *rl) 412 { 413 struct smatch_state *state; 414 415 if (!rl) 416 return extra_empty(); 417 418 state = __alloc_smatch_state(0); 419 state->data = alloc_dinfo_range_list(rl); 420 state->name = show_rl(rl); 421 return state; 422 } 423 424 struct smatch_state *clone_estate_cast(struct symbol *type, struct smatch_state *state) 425 { 426 struct smatch_state *ret; 427 struct data_info *dinfo; 428 429 if (!state) 430 return NULL; 431 432 dinfo = alloc_dinfo(); 433 dinfo->value_ranges = clone_rl(cast_rl(type, estate_rl(state))); 434 435 ret = __alloc_smatch_state(0); 436 ret->name = show_rl(dinfo->value_ranges); 437 ret->data = dinfo; 438 439 return ret; 440 } 441 442 struct smatch_state *get_implied_estate(struct expression *expr) 443 { 444 struct smatch_state *state; 445 struct range_list *rl; 446 447 state = get_state_expr(SMATCH_EXTRA, expr); 448 if (state) 449 return state; 450 if (!get_implied_rl(expr, &rl)) 451 rl = alloc_whole_rl(get_type(expr)); 452 return alloc_estate_rl(rl); 453 } 454 455 /* 456 * One of the complications is that smatch tries to free a bunch of data at the 457 * end of every function. 458 */ 459 struct data_info *clone_dinfo_perm(struct data_info *dinfo) 460 { 461 struct data_info *ret; 462 463 ret = malloc(sizeof(*ret)); 464 memset(ret, 0, sizeof(*ret)); 465 ret->related = NULL; 466 ret->value_ranges = clone_rl_permanent(dinfo->value_ranges); 467 ret->hard_max = 0; 468 ret->fuzzy_max = dinfo->fuzzy_max; 469 return ret; 470 } 471 472 struct smatch_state *clone_estate_perm(struct smatch_state *state) 473 { 474 struct smatch_state *ret; 475 476 ret = malloc(sizeof(*ret)); 477 ret->name = alloc_string(state->name); 478 ret->data = clone_dinfo_perm(get_dinfo(state)); 479 return ret; 480 } 481 482 483