smatch_ranges.c

   1 /*
   2  * Copyright (C) 2009 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 #include "parse.h"
  19 #include "smatch.h"
  20 #include "smatch_extra.h"
  21 #include "smatch_slist.h"
  22
  23 ALLOCATOR(data_info, "smatch extra data");
  24 ALLOCATOR(data_range, "data range");
  25 __DO_ALLOCATOR(struct data_range, sizeof(struct data_range), __alignof__(struct data_range),
  26                          "permanent ranges", perm_data_range);
  27
  28 char *show_rl(struct range_list *list)
  29 {
  30         struct data_range *tmp;
  31         char full[256];
  32         int i = 0;
  33
  34         full[0] = '\0';
  35         full[255] = '\0';
  36         FOR_EACH_PTR(list, tmp) {
  37                 if (i++)
  38                         strncat(full, ",", 254 - strlen(full));
  39                 if (sval_cmp(tmp->min, tmp->max) == 0) {
  40                         strncat(full, sval_to_str(tmp->min), 254 - strlen(full));
  41                         continue;
  42                 }
  43                 strncat(full, sval_to_str(tmp->min), 254 - strlen(full));
  44                 strncat(full, "-", 254 - strlen(full));
  45                 strncat(full, sval_to_str(tmp->max), 254 - strlen(full));
  46         } END_FOR_EACH_PTR(tmp);
  47         return alloc_sname(full);
  48 }
  49
  50 static int str_to_comparison_arg_helper(const char *str,
  51                 struct expression *call, int *comparison,
  52                 struct expression **arg, char **endp)
  53 {
  54         int param;
  55         char *c = (char *)str;
  56
  57         if (*c != '[')
  58                 return 0;
  59         c++;
  60
  61         if (*c == '<') {
  62                 c++;
  63                 if (*c == '=') {
  64                         *comparison = SPECIAL_LTE;
  65                         c++;
  66                 } else {
  67                         *comparison = '<';
  68                 }
  69         } else if (*c == '=') {
  70                 c++;
  71                 c++;
  72                 *comparison = SPECIAL_EQUAL;
  73         } else if (*c == '>') {
  74                 c++;
  75                 if (*c == '=') {
  76                         *comparison = SPECIAL_GTE;
  77                         c++;
  78                 } else {
  79                         *comparison = '>';
  80                 }
  81         } else {
  82                 return 0;
  83         }
  84
  85         if (*c != 'p')
  86                 return 0;
  87         c++;
  88
  89         param = strtoll(c, &c, 10);
  90         c++; /* skip the ']' character */
  91         if (endp)
  92                 *endp = (char *)c;
  93
  94         if (!call)
  95                 return 0;
  96         *arg = get_argument_from_call_expr(call->args, param);
  97         if (!*arg)
  98                 return 0;
  99         return 1;
 100 }
 101
 102 int str_to_comparison_arg(const char *str, struct expression *call, int *comparison, struct expression **arg)
 103 {
 104         while (1) {
 105                 if (!*str)
 106                         return 0;
 107                 if (*str == '[')
 108                         break;
 109                 str++;
 110         }
 111         return str_to_comparison_arg_helper(str, call, comparison, arg, NULL);
 112 }
 113
 114 static sval_t get_val_from_key(int use_max, struct symbol *type, char *c, struct expression *call, char **endp)
 115 {
 116         struct expression *arg;
 117         int comparison;
 118         sval_t ret, tmp;
 119
 120         if (use_max)
 121                 ret = sval_type_max(type);
 122         else
 123                 ret = sval_type_min(type);
 124
 125         if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp))
 126                 return ret;
 127
 128         if (use_max && get_implied_max(arg, &tmp)) {
 129                 ret = tmp;
 130                 if (comparison == '<') {
 131                         tmp.value = 1;
 132                         ret = sval_binop(ret, '-', tmp);
 133                 }
 134         }
 135         if (!use_max && get_implied_min(arg, &tmp)) {
 136                 ret = tmp;
 137                 if (comparison == '>') {
 138                         tmp.value = 1;
 139                         ret = sval_binop(ret, '+', tmp);
 140                 }
 141         }
 142
 143         return ret;
 144 }
 145
 146 static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, char *c, char **endp)
 147 {
 148         char *start = c;
 149         sval_t ret;
 150
 151         if (!strncmp(start, "max", 3)) {
 152                 ret = sval_type_max(type);
 153                 c += 3;
 154         } else if (!strncmp(start, "u64max", 6)) {
 155                 ret = sval_type_val(type, ULLONG_MAX);
 156                 c += 6;
 157         } else if (!strncmp(start, "s64max", 6)) {
 158                 ret = sval_type_val(type, LLONG_MAX);
 159                 c += 6;
 160         } else if (!strncmp(start, "u32max", 6)) {
 161                 ret = sval_type_val(type, UINT_MAX);
 162                 c += 6;
 163         } else if (!strncmp(start, "s32max", 6)) {
 164                 ret = sval_type_val(type, INT_MAX);
 165                 c += 6;
 166         } else if (!strncmp(start, "u16max", 6)) {
 167                 ret = sval_type_val(type, USHRT_MAX);
 168                 c += 6;
 169         } else if (!strncmp(start, "s16max", 6)) {
 170                 ret = sval_type_val(type, SHRT_MAX);
 171                 c += 6;
 172         } else if (!strncmp(start, "min", 3)) {
 173                 ret = sval_type_min(type);
 174                 c += 3;
 175         } else if (!strncmp(start, "s64min", 6)) {
 176                 ret = sval_type_val(type, LLONG_MIN);
 177                 c += 6;
 178         } else if (!strncmp(start, "s32min", 6)) {
 179                 ret = sval_type_val(type, INT_MIN);
 180                 c += 6;
 181         } else if (!strncmp(start, "s16min", 6)) {
 182                 ret = sval_type_val(type, SHRT_MIN);
 183                 c += 6;
 184         } else if (start[0] == '[') {
 185                 /* this parses [==p0] comparisons */
 186                 ret = get_val_from_key(1, type, start, call, &c);
 187         } else {
 188                 ret = sval_type_val(type, strtoll(start, &c, 10));
 189         }
 190         *endp = c;
 191         return ret;
 192 }
 193
 194 static void str_to_rl_helper(struct expression *call, struct symbol *type, char *value, struct range_list **rl)
 195 {
 196         sval_t min, max, arg_max;
 197         char *c;
 198
 199         if (!type)
 200                 type = &llong_ctype;
 201         *rl = NULL;
 202
 203         if (value && strcmp(value, "empty") == 0)
 204                 return;
 205
 206         if (strncmp(value, "[==p", 4) == 0) {
 207                 struct expression *arg;
 208                 int comparison;
 209
 210                 if (!str_to_comparison_arg(value, call, &comparison, &arg))
 211                         goto out;
 212                 get_implied_rl(arg, rl);
 213                 goto out;
 214         }
 215
 216         c = value;
 217         while (*c) {
 218                 if (*c == '(')
 219                         c++;
 220                 min = parse_val(0, call, type, c, &c);
 221                 if (*c == ')')
 222                         c++;
 223                 if (*c == '\0' || *c == '[') {
 224                         add_range(rl, min, min);
 225                         break;
 226                 }
 227                 if (*c == ',') {
 228                         add_range(rl, min, min);
 229                         c++;
 230                         continue;
 231                 }
 232                 if (*c != '-') {
 233                         sm_msg("debug XXX: trouble parsing %s ", value);
 234                         break;
 235                 }
 236                 c++;
 237                 if (*c == '(')
 238                         c++;
 239                 max = parse_val(1, call, type, c, &c);
 240                 if (*c == ')')
 241                         c++;
 242                 if (*c == '[') {
 243                         arg_max = get_val_from_key(1, type, c, call, &c);
 244                         if (sval_cmp(arg_max, max) < 0)
 245                                 max = arg_max;
 246                 }
 247                 add_range(rl, min, max);
 248                 if (!*c)
 249                         break;
 250                 if (*c != ',') {
 251                         sm_msg("debug YYY: trouble parsing %s %s", value, c);
 252                         break;
 253                 }
 254                 c++;
 255         }
 256
 257 out:
 258         *rl = cast_rl(type, *rl);
 259 }
 260
 261 void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
 262 {
 263         return str_to_rl_helper(NULL, type, value, rl);
 264 }
 265
 266 void call_results_to_rl(struct expression *expr, struct symbol *type, char *value, struct range_list **rl)
 267 {
 268         return str_to_rl_helper(strip_expr(expr), type, value, rl);
 269 }
 270
 271 int is_whole_rl(struct range_list *rl)
 272 {
 273         struct data_range *drange;
 274
 275         if (ptr_list_empty(rl))
 276                 return 0;
 277         drange = first_ptr_list((struct ptr_list *)rl);
 278         if (sval_is_min(drange->min) && sval_is_max(drange->max))
 279                 return 1;
 280         return 0;
 281 }
 282
 283 sval_t rl_min(struct range_list *rl)
 284 {
 285         struct data_range *drange;
 286         sval_t ret;
 287
 288         ret.type = &llong_ctype;
 289         ret.value = LLONG_MIN;
 290         if (ptr_list_empty(rl))
 291                 return ret;
 292         drange = first_ptr_list((struct ptr_list *)rl);
 293         return drange->min;
 294 }
 295
 296 sval_t rl_max(struct range_list *rl)
 297 {
 298         struct data_range *drange;
 299         sval_t ret;
 300
 301         ret.type = &llong_ctype;
 302         ret.value = LLONG_MAX;
 303         if (ptr_list_empty(rl))
 304                 return ret;
 305         drange = last_ptr_list((struct ptr_list *)rl);
 306         return drange->max;
 307 }
 308
 309 int rl_to_sval(struct range_list *rl, sval_t *sval)
 310 {
 311         sval_t min, max;
 312
 313         if (!rl)
 314                 return 0;
 315
 316         min = rl_min(rl);
 317         max = rl_max(rl);
 318         if (sval_cmp(min, max) != 0)
 319                 return 0;
 320         *sval = min;
 321         return 1;
 322 }
 323
 324 struct symbol *rl_type(struct range_list *rl)
 325 {
 326         if (!rl)
 327                 return NULL;
 328         return rl_min(rl).type;
 329 }
 330
 331 static struct data_range *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
 332 {
 333         struct data_range *ret;
 334
 335         if (perm)
 336                 ret = __alloc_perm_data_range(0);
 337         else
 338                 ret = __alloc_data_range(0);
 339         ret->min = min;
 340         ret->max = max;
 341         return ret;
 342 }
 343
 344 struct data_range *alloc_range(sval_t min, sval_t max)
 345 {
 346         return alloc_range_helper_sval(min, max, 0);
 347 }
 348
 349 struct data_range *alloc_range_perm(sval_t min, sval_t max)
 350 {
 351         return alloc_range_helper_sval(min, max, 1);
 352 }
 353
 354 struct range_list *alloc_rl(sval_t min, sval_t max)
 355 {
 356         struct range_list *rl = NULL;
 357
 358         if (sval_cmp(min, max) > 0)
 359                 return alloc_whole_rl(min.type);
 360
 361         add_range(&rl, min, max);
 362         return rl;
 363 }
 364
 365 struct range_list *alloc_whole_rl(struct symbol *type)
 366 {
 367         if (!type || type_positive_bits(type) < 0)
 368                 type = &llong_ctype;
 369
 370         return alloc_rl(sval_type_min(type), sval_type_max(type));
 371 }
 372
 373 void add_range(struct range_list **list, sval_t min, sval_t max)
 374 {
 375         struct data_range *tmp = NULL;
 376         struct data_range *new = NULL;
 377         int check_next = 0;
 378
 379         /*
 380          * FIXME:  This has a problem merging a range_list like: min-0,3-max
 381          * with a range like 1-2.  You end up with min-2,3-max instead of
 382          * just min-max.
 383          */
 384         FOR_EACH_PTR(*list, tmp) {
 385                 if (check_next) {
 386                         /* Sometimes we overlap with more than one range
 387                            so we have to delete or modify the next range. */
 388                         if (max.value + 1 == tmp->min.value) {
 389                                 /* join 2 ranges here */
 390                                 new->max = tmp->max;
 391                                 DELETE_CURRENT_PTR(tmp);
 392                                 return;
 393                         }
 394
 395                         /* Doesn't overlap with the next one. */
 396                         if (sval_cmp(max, tmp->min) < 0)
 397                                 return;
 398                         /* Partially overlaps with the next one. */
 399                         if (sval_cmp(max, tmp->max) < 0) {
 400                                 tmp->min.value = max.value + 1;
 401                                 return;
 402                         }
 403                         /* Completely overlaps with the next one. */
 404                         if (sval_cmp(max, tmp->max) >= 0) {
 405                                 DELETE_CURRENT_PTR(tmp);
 406                                 /* there could be more ranges to delete */
 407                                 continue;
 408                         }
 409                 }
 410                 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
 411                         /* join 2 ranges into a big range */
 412                         new = alloc_range(min, tmp->max);
 413                         REPLACE_CURRENT_PTR(tmp, new);
 414                         return;
 415                 }
 416                 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
 417                         new = alloc_range(min, max);
 418                         INSERT_CURRENT(new, tmp);
 419                         return;
 420                 }
 421                 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
 422                         if (sval_cmp(max, tmp->max) < 0)
 423                                 max = tmp->max;
 424                         else
 425                                 check_next = 1;
 426                         new = alloc_range(min, max);
 427                         REPLACE_CURRENT_PTR(tmp, new);
 428                         if (!check_next)
 429                                 return;
 430                         continue;
 431                 }
 432                 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
 433                         return;
 434                 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
 435                         min = tmp->min;
 436                         new = alloc_range(min, max);
 437                         REPLACE_CURRENT_PTR(tmp, new);
 438                         check_next = 1;
 439                         continue;
 440                 }
 441                 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
 442                         /* join 2 ranges into a big range */
 443                         new = alloc_range(tmp->min, max);
 444                         REPLACE_CURRENT_PTR(tmp, new);
 445                         check_next = 1;
 446                         continue;
 447                 }
 448                 /* the new range is entirely above the existing ranges */
 449         } END_FOR_EACH_PTR(tmp);
 450         if (check_next)
 451                 return;
 452         new = alloc_range(min, max);
 453         add_ptr_list(list, new);
 454 }
 455
 456 struct range_list *clone_rl(struct range_list *list)
 457 {
 458         struct data_range *tmp;
 459         struct range_list *ret = NULL;
 460
 461         FOR_EACH_PTR(list, tmp) {
 462                 add_ptr_list(&ret, tmp);
 463         } END_FOR_EACH_PTR(tmp);
 464         return ret;
 465 }
 466
 467 struct range_list *clone_rl_permanent(struct range_list *list)
 468 {
 469         struct data_range *tmp;
 470         struct data_range *new;
 471         struct range_list *ret = NULL;
 472
 473         FOR_EACH_PTR(list, tmp) {
 474                 new = alloc_range_perm(tmp->min, tmp->max);
 475                 add_ptr_list(&ret, new);
 476         } END_FOR_EACH_PTR(tmp);
 477         return ret;
 478 }
 479
 480 struct range_list *rl_union(struct range_list *one, struct range_list *two)
 481 {
 482         struct data_range *tmp;
 483         struct range_list *ret = NULL;
 484
 485         FOR_EACH_PTR(one, tmp) {
 486                 add_range(&ret, tmp->min, tmp->max);
 487         } END_FOR_EACH_PTR(tmp);
 488         FOR_EACH_PTR(two, tmp) {
 489                 add_range(&ret, tmp->min, tmp->max);
 490         } END_FOR_EACH_PTR(tmp);
 491         return ret;
 492 }
 493
 494 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
 495 {
 496         struct data_range *tmp;
 497         struct range_list *ret = NULL;
 498
 499         FOR_EACH_PTR(list, tmp) {
 500                 if (sval_cmp(tmp->max, min) < 0) {
 501                         add_range(&ret, tmp->min, tmp->max);
 502                         continue;
 503                 }
 504                 if (sval_cmp(tmp->min, max) > 0) {
 505                         add_range(&ret, tmp->min, tmp->max);
 506                         continue;
 507                 }
 508                 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
 509                         continue;
 510                 if (sval_cmp(tmp->min, min) >= 0) {
 511                         max.value++;
 512                         add_range(&ret, max, tmp->max);
 513                 } else if (sval_cmp(tmp->max, max) <= 0) {
 514                         min.value--;
 515                         add_range(&ret, tmp->min, min);
 516                 } else {
 517                         min.value--;
 518                         max.value++;
 519                         add_range(&ret, tmp->min, min);
 520                         add_range(&ret, max, tmp->max);
 521                 }
 522         } END_FOR_EACH_PTR(tmp);
 523         return ret;
 524 }
 525
 526 int ranges_equiv(struct data_range *one, struct data_range *two)
 527 {
 528         if (!one && !two)
 529                 return 1;
 530         if (!one || !two)
 531                 return 0;
 532         if (sval_cmp(one->min, two->min) != 0)
 533                 return 0;
 534         if (sval_cmp(one->max, two->max) != 0)
 535                 return 0;
 536         return 1;
 537 }
 538
 539 int rl_equiv(struct range_list *one, struct range_list *two)
 540 {
 541         struct data_range *one_range;
 542         struct data_range *two_range;
 543
 544         if (one == two)
 545                 return 1;
 546
 547         PREPARE_PTR_LIST(one, one_range);
 548         PREPARE_PTR_LIST(two, two_range);
 549         for (;;) {
 550                 if (!one_range && !two_range)
 551                         return 1;
 552                 if (!ranges_equiv(one_range, two_range))
 553                         return 0;
 554                 NEXT_PTR_LIST(one_range);
 555                 NEXT_PTR_LIST(two_range);
 556         }
 557         FINISH_PTR_LIST(two_range);
 558         FINISH_PTR_LIST(one_range);
 559
 560         return 1;
 561 }
 562
 563 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
 564 {
 565         switch (comparison) {
 566         case '<':
 567         case SPECIAL_UNSIGNED_LT:
 568                 if (sval_cmp(left->min, right->max) < 0)
 569                         return 1;
 570                 return 0;
 571         case SPECIAL_UNSIGNED_LTE:
 572         case SPECIAL_LTE:
 573                 if (sval_cmp(left->min, right->max) <= 0)
 574                         return 1;
 575                 return 0;
 576         case SPECIAL_EQUAL:
 577                 if (sval_cmp(left->max, right->min) < 0)
 578                         return 0;
 579                 if (sval_cmp(left->min, right->max) > 0)
 580                         return 0;
 581                 return 1;
 582         case SPECIAL_UNSIGNED_GTE:
 583         case SPECIAL_GTE:
 584                 if (sval_cmp(left->max, right->min) >= 0)
 585                         return 1;
 586                 return 0;
 587         case '>':
 588         case SPECIAL_UNSIGNED_GT:
 589                 if (sval_cmp(left->max, right->min) > 0)
 590                         return 1;
 591                 return 0;
 592         case SPECIAL_NOTEQUAL:
 593                 if (sval_cmp(left->min, left->max) != 0)
 594                         return 1;
 595                 if (sval_cmp(right->min, right->max) != 0)
 596                         return 1;
 597                 if (sval_cmp(left->min, right->min) != 0)
 598                         return 1;
 599                 return 0;
 600         default:
 601                 sm_msg("unhandled comparison %d\n", comparison);
 602                 return 0;
 603         }
 604         return 0;
 605 }
 606
 607 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
 608 {
 609         if (left)
 610                 return true_comparison_range(var, comparison, val);
 611         else
 612                 return true_comparison_range(val, comparison, var);
 613 }
 614
 615 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
 616 {
 617         switch (comparison) {
 618         case '<':
 619         case SPECIAL_UNSIGNED_LT:
 620                 if (sval_cmp(left->max, right->min) >= 0)
 621                         return 1;
 622                 return 0;
 623         case SPECIAL_UNSIGNED_LTE:
 624         case SPECIAL_LTE:
 625                 if (sval_cmp(left->max, right->min) > 0)
 626                         return 1;
 627                 return 0;
 628         case SPECIAL_EQUAL:
 629                 if (sval_cmp(left->min, left->max) != 0)
 630                         return 1;
 631                 if (sval_cmp(right->min, right->max) != 0)
 632                         return 1;
 633                 if (sval_cmp(left->min, right->min) != 0)
 634                         return 1;
 635                 return 0;
 636         case SPECIAL_UNSIGNED_GTE:
 637         case SPECIAL_GTE:
 638                 if (sval_cmp(left->min, right->max) < 0)
 639                         return 1;
 640                 return 0;
 641         case '>':
 642         case SPECIAL_UNSIGNED_GT:
 643                 if (sval_cmp(left->min, right->max) <= 0)
 644                         return 1;
 645                 return 0;
 646         case SPECIAL_NOTEQUAL:
 647                 if (sval_cmp(left->max, right->min) < 0)
 648                         return 0;
 649                 if (sval_cmp(left->min, right->max) > 0)
 650                         return 0;
 651                 return 1;
 652         default:
 653                 sm_msg("unhandled comparison %d\n", comparison);
 654                 return 0;
 655         }
 656         return 0;
 657 }
 658
 659 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
 660 {
 661         if (left)
 662                 return false_comparison_range_sval(var, comparison, val);
 663         else
 664                 return false_comparison_range_sval(val, comparison, var);
 665 }
 666
 667 int possibly_true(struct expression *left, int comparison, struct expression *right)
 668 {
 669         struct range_list *rl_left, *rl_right;
 670         struct data_range *tmp_left, *tmp_right;
 671
 672         if (!get_implied_rl(left, &rl_left))
 673                 return 1;
 674         if (!get_implied_rl(right, &rl_right))
 675                 return 1;
 676
 677         FOR_EACH_PTR(rl_left, tmp_left) {
 678                 FOR_EACH_PTR(rl_right, tmp_right) {
 679                         if (true_comparison_range(tmp_left, comparison, tmp_right))
 680                                 return 1;
 681                 } END_FOR_EACH_PTR(tmp_right);
 682         } END_FOR_EACH_PTR(tmp_left);
 683         return 0;
 684 }
 685
 686 int possibly_false(struct expression *left, int comparison, struct expression *right)
 687 {
 688         struct range_list *rl_left, *rl_right;
 689         struct data_range *tmp_left, *tmp_right;
 690
 691         if (!get_implied_rl(left, &rl_left))
 692                 return 1;
 693         if (!get_implied_rl(right, &rl_right))
 694                 return 1;
 695
 696         FOR_EACH_PTR(rl_left, tmp_left) {
 697                 FOR_EACH_PTR(rl_right, tmp_right) {
 698                         if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
 699                                 return 1;
 700                 } END_FOR_EACH_PTR(tmp_right);
 701         } END_FOR_EACH_PTR(tmp_left);
 702         return 0;
 703 }
 704
 705 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 706 {
 707         struct data_range *left_tmp, *right_tmp;
 708
 709         if (!left_ranges || !right_ranges)
 710                 return 1;
 711
 712         FOR_EACH_PTR(left_ranges, left_tmp) {
 713                 FOR_EACH_PTR(right_ranges, right_tmp) {
 714                         if (true_comparison_range(left_tmp, comparison, right_tmp))
 715                                 return 1;
 716                 } END_FOR_EACH_PTR(right_tmp);
 717         } END_FOR_EACH_PTR(left_tmp);
 718         return 0;
 719 }
 720
 721 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 722 {
 723         struct data_range *left_tmp, *right_tmp;
 724
 725         if (!left_ranges || !right_ranges)
 726                 return 1;
 727
 728         FOR_EACH_PTR(left_ranges, left_tmp) {
 729                 FOR_EACH_PTR(right_ranges, right_tmp) {
 730                         if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
 731                                 return 1;
 732                 } END_FOR_EACH_PTR(right_tmp);
 733         } END_FOR_EACH_PTR(left_tmp);
 734         return 0;
 735 }
 736
 737 /* FIXME: the _rl here stands for right left so really it should be _lr */
 738 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
 739 {
 740         if (left)
 741                 return possibly_true_rl(a, comparison, b);
 742         else
 743                 return possibly_true_rl(b, comparison, a);
 744 }
 745
 746 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
 747 {
 748         if (left)
 749                 return possibly_false_rl(a, comparison, b);
 750         else
 751                 return possibly_false_rl(b, comparison, a);
 752 }
 753
 754 int rl_has_sval(struct range_list *rl, sval_t sval)
 755 {
 756         struct data_range *tmp;
 757
 758         FOR_EACH_PTR(rl, tmp) {
 759                 if (sval_cmp(tmp->min, sval) <= 0 &&
 760                     sval_cmp(tmp->max, sval) >= 0)
 761                         return 1;
 762         } END_FOR_EACH_PTR(tmp);
 763         return 0;
 764 }
 765
 766 void tack_on(struct range_list **list, struct data_range *drange)
 767 {
 768         add_ptr_list(list, drange);
 769 }
 770
 771 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
 772 {
 773         add_ptr_list(rl_stack, rl);
 774 }
 775
 776 struct range_list *pop_rl(struct range_list_stack **rl_stack)
 777 {
 778         struct range_list *rl;
 779
 780         rl = last_ptr_list((struct ptr_list *)*rl_stack);
 781         delete_ptr_list_last((struct ptr_list **)rl_stack);
 782         return rl;
 783 }
 784
 785 struct range_list *top_rl(struct range_list_stack *rl_stack)
 786 {
 787         struct range_list *rl;
 788
 789         rl = last_ptr_list((struct ptr_list *)rl_stack);
 790         return rl;
 791 }
 792
 793 void filter_top_rl(struct range_list_stack **rl_stack, sval_t sval)
 794 {
 795         struct range_list *rl;
 796
 797         rl = pop_rl(rl_stack);
 798         rl = remove_range(rl, sval, sval);
 799         push_rl(rl_stack, rl);
 800 }
 801
 802 static int sval_too_big(struct symbol *type, sval_t sval)
 803 {
 804         if (type_bits(type) == 64)
 805                 return 0;
 806         if (sval.uvalue > ((1ULL << type_bits(type)) - 1))
 807                 return 1;
 808         return 0;
 809 }
 810
 811 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
 812 {
 813         /* If we're just adding a number, cast it and add it */
 814         if (sval_cmp(min, max) == 0) {
 815                 add_range(rl, sval_cast(type, min), sval_cast(type, max));
 816                 return;
 817         }
 818
 819         /* If the range is within the type range then add it */
 820         if (sval_fits(type, min) && sval_fits(type, max)) {
 821                 add_range(rl, sval_cast(type, min), sval_cast(type, max));
 822                 return;
 823         }
 824
 825         /*
 826          * If the range we are adding has more bits than the range type then
 827          * add the whole range type.  Eg:
 828          * 0x8000000000000000 - 0xf000000000000000 -> cast to int
 829          * This isn't totally the right thing to do.  We could be more granular.
 830          */
 831         if (sval_too_big(type, min) || sval_too_big(type, max)) {
 832                 add_range(rl, sval_type_min(type), sval_type_max(type));
 833                 return;
 834         }
 835
 836         /* Cast negative values to high positive values */
 837         if (sval_is_negative(min) && type_unsigned(type)) {
 838                 if (sval_is_positive(max)) {
 839                         if (sval_too_high(type, max)) {
 840                                 add_range(rl, sval_type_min(type), sval_type_max(type));
 841                                 return;
 842                         }
 843                         add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
 844                         max = sval_type_max(type);
 845                 } else {
 846                         max = sval_cast(type, max);
 847                 }
 848                 min = sval_cast(type, min);
 849                 add_range(rl, min, max);
 850         }
 851
 852         /* Cast high positive numbers to negative */
 853         if (sval_unsigned(max) && sval_is_negative(sval_cast(type, max))) {
 854                 if (!sval_is_negative(sval_cast(type, min))) {
 855                         add_range(rl, sval_cast(type, min), sval_type_max(type));
 856                         min = sval_type_min(type);
 857                 } else {
 858                         min = sval_cast(type, min);
 859                 }
 860                 max = sval_cast(type, max);
 861                 add_range(rl, min, max);
 862         }
 863
 864         return;
 865 }
 866
 867 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
 868 {
 869         struct data_range *tmp;
 870         struct range_list *ret = NULL;
 871         sval_t min, max;
 872
 873         if (!rl)
 874                 return NULL;
 875
 876         if (!type || type == rl_type(rl))
 877                 return rl;
 878
 879         FOR_EACH_PTR(rl, tmp) {
 880                 min = tmp->min;
 881                 max = tmp->max;
 882                 if (type_bits(type) < type_bits(rl_type(rl))) {
 883                         min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
 884                         max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
 885                 }
 886                 if (sval_cmp(min, max) > 0) {
 887                         min = sval_cast(type, min);
 888                         max = sval_cast(type, max);
 889                 }
 890                 add_range_t(type, &ret, min, max);
 891         } END_FOR_EACH_PTR(tmp);
 892
 893         return ret;
 894 }
 895
 896 static int rl_is_sane(struct range_list *rl)
 897 {
 898         struct data_range *tmp;
 899         struct symbol *type;
 900
 901         type = rl_type(rl);
 902         FOR_EACH_PTR(rl, tmp) {
 903                 if (!sval_fits(type, tmp->min))
 904                         return 0;
 905                 if (!sval_fits(type, tmp->max))
 906                         return 0;
 907                 if (sval_cmp(tmp->min, tmp->max) > 0)
 908                         return 0;
 909         } END_FOR_EACH_PTR(tmp);
 910
 911         return 1;
 912 }
 913
 914 static int rl_type_consistent(struct range_list *rl)
 915 {
 916         struct data_range *tmp;
 917         struct symbol *type;
 918
 919         type = rl_type(rl);
 920         FOR_EACH_PTR(rl, tmp) {
 921                 if (type != tmp->min.type || type != tmp->max.type)
 922                         return 0;
 923         } END_FOR_EACH_PTR(tmp);
 924         return 1;
 925 }
 926
 927 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
 928 {
 929         struct data_range *tmp;
 930         struct range_list *ret = NULL;
 931
 932         if (!rl)
 933                 return NULL;
 934
 935         if (!type)
 936                 return rl;
 937         if (!rl_is_sane(rl))
 938                 return alloc_whole_rl(type);
 939         if (type == rl_type(rl) && rl_type_consistent(rl))
 940                 return rl;
 941
 942         FOR_EACH_PTR(rl, tmp) {
 943                 add_range_t(type, &ret, tmp->min, tmp->max);
 944         } END_FOR_EACH_PTR(tmp);
 945
 946         if (!ret)
 947                 return alloc_whole_rl(type);
 948
 949         return ret;
 950 }
 951
 952 struct range_list *rl_invert(struct range_list *orig)
 953 {
 954         struct range_list *ret = NULL;
 955         struct data_range *tmp;
 956         sval_t gap_min, abs_max, sval;
 957
 958         if (!orig)
 959                 return NULL;
 960
 961         gap_min = sval_type_min(rl_min(orig).type);
 962         abs_max = sval_type_max(rl_max(orig).type);
 963
 964         FOR_EACH_PTR(orig, tmp) {
 965                 if (sval_cmp(tmp->min, gap_min) > 0) {
 966                         sval = sval_type_val(tmp->min.type, tmp->min.value - 1);
 967                         add_range(&ret, gap_min, sval);
 968                 }
 969                 gap_min = sval_type_val(tmp->max.type, tmp->max.value + 1);
 970                 if (sval_cmp(tmp->max, abs_max) == 0)
 971                         gap_min = abs_max;
 972         } END_FOR_EACH_PTR(tmp);
 973
 974         if (sval_cmp(gap_min, abs_max) < 0)
 975                 add_range(&ret, gap_min, abs_max);
 976
 977         return ret;
 978 }
 979
 980 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
 981 {
 982         struct data_range *tmp;
 983
 984         FOR_EACH_PTR(filter, tmp) {
 985                 rl = remove_range(rl, tmp->min, tmp->max);
 986         } END_FOR_EACH_PTR(tmp);
 987
 988         return rl;
 989 }
 990
 991 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
 992 {
 993         if (!two)
 994                 return NULL;
 995         two = rl_invert(two);
 996         return rl_filter(one, two);
 997 }
 998
 999 void free_rl(struct range_list **rlist)
1000 {
1001         __free_ptr_list((struct ptr_list **)rlist);
1002 }
1003
1004 static void free_single_dinfo(struct data_info *dinfo)
1005 {
1006         free_rl(&dinfo->value_ranges);
1007 }
1008
1009 static void free_dinfos(struct allocation_blob *blob)
1010 {
1011         unsigned int size = sizeof(struct data_info);
1012         unsigned int offset = 0;
1013
1014         while (offset < blob->offset) {
1015                 free_single_dinfo((struct data_info *)(blob->data + offset));
1016                 offset += size;
1017         }
1018 }
1019
1020 void free_data_info_allocs(void)
1021 {
1022         struct allocator_struct *desc = &data_info_allocator;
1023         struct allocation_blob *blob = desc->blobs;
1024
1025         desc->blobs = NULL;
1026         desc->allocations = 0;
1027         desc->total_bytes = 0;
1028         desc->useful_bytes = 0;
1029         desc->freelist = NULL;
1030         while (blob) {
1031                 struct allocation_blob *next = blob->next;
1032                 free_dinfos(blob);
1033                 blob_free(blob, desc->chunking);
1034                 blob = next;
1035         }
1036         clear_data_range_alloc();
1037 }
1038