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