smatch_estate.c

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