smatch_ranges.c

   1 /*
   2  * sparse/smatch_ranges.c
   3  *
   4  * Copyright (C) 2009 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include "parse.h"
  11 #include "smatch.h"
  12 #include "smatch_extra.h"
  13 #include "smatch_slist.h"
  14
  15 ALLOCATOR(data_info, "smatch extra data");
  16 ALLOCATOR(data_range, "data range");
  17 __DO_ALLOCATOR(struct data_range, sizeof(struct data_range), __alignof__(struct data_range),
  18                          "permanent ranges", perm_data_range);
  19
  20 struct data_range whole_range = {
  21         .min = LLONG_MIN,
  22         .max = LLONG_MAX,
  23 };
  24
  25 static char *show_num(long long num)
  26 {
  27         static char buff[256];
  28
  29         if (num == whole_range.min)
  30                 snprintf(buff, 255, "min");
  31         else if (num == whole_range.max)
  32                 snprintf(buff, 255, "max");
  33         else if (num < 0)
  34                 snprintf(buff, 255, "(%lld)", num);
  35         else
  36                 snprintf(buff, 255, "%lld", num);
  37
  38         buff[255] = '\0';
  39         return buff;
  40 }
  41
  42 char *show_ranges(struct range_list *list)
  43 {
  44         struct data_range *tmp;
  45         char full[256];
  46         int i = 0;
  47
  48         full[0] = '\0';
  49         full[255] = '\0';
  50         FOR_EACH_PTR(list, tmp) {
  51                 if (i++)
  52                         strncat(full, ",", 254 - strlen(full));
  53                 if (tmp->min == tmp->max) {
  54                         strncat(full, show_num(tmp->min), 254 - strlen(full));
  55                         continue;
  56                 }
  57                 strncat(full, show_num(tmp->min), 254 - strlen(full));
  58                 strncat(full, "-", 254 - strlen(full));
  59                 strncat(full, show_num(tmp->max), 254 - strlen(full));
  60         } END_FOR_EACH_PTR(tmp);
  61         return alloc_sname(full);
  62 }
  63
  64 void get_value_ranges(char *value, struct range_list **rl)
  65 {
  66         long long val1, val2;
  67         char *start;
  68         char *c;
  69
  70         *rl = NULL;
  71
  72         c = value;
  73         while (*c) {
  74                 if (*c == '(')
  75                         c++;
  76                 start = c;
  77                 if (!strncmp(start, "min", 3)) {
  78                         val1 = LLONG_MIN;
  79                         c += 3;
  80                 } else {
  81                         while (*c && *c != ',' && *c != '-')
  82                                 c++;
  83                         val1 = strtoll(start, &c, 10);
  84                 }
  85                 if (*c == ')')
  86                         c++;
  87                 if (!*c) {
  88                         add_range(rl, val1, val1);
  89                         break;
  90                 }
  91                 if (*c == ',') {
  92                         add_range(rl, val1, val1);
  93                         c++;
  94                         start = c;
  95                         continue;
  96                 }
  97                 c++; /* skip the dash in eg. 4-5 */
  98                 if (*c == '(')
  99                         c++;
 100                 start = c;
 101                 if (!strncmp(start, "max", 3)) {
 102                         val2 = LLONG_MAX;
 103                         c += 3;
 104                 } else {
 105
 106                         while (*c && *c != ',' && *c != '-')
 107                                 c++;
 108                         val2 = strtoll(start, &c, 10);
 109                 }
 110                 add_range(rl, val1, val2);
 111                 if (!*c)
 112                         break;
 113                 if (*c == ')')
 114                         c++;
 115                 c++; /* skip the comma in eg: 4-5,7 */
 116         }
 117
 118 }
 119
 120 static struct data_range range_zero = {
 121         .min = 0,
 122         .max = 0,
 123 };
 124
 125 static struct data_range range_one = {
 126         .min = 1,
 127         .max = 1,
 128 };
 129
 130 int is_whole_range_rl(struct range_list *rl)
 131 {
 132         struct data_range *drange;
 133
 134         if (ptr_list_empty(rl))
 135                 return 1;
 136         drange = first_ptr_list((struct ptr_list *)rl);
 137         if (drange->min == whole_range.min && drange->max == whole_range.max)
 138                 return 1;
 139         return 0;
 140 }
 141
 142 long long rl_min(struct range_list *rl)
 143 {
 144         struct data_range *drange;
 145
 146         if (ptr_list_empty(rl))
 147                 return whole_range.min;
 148         drange = first_ptr_list((struct ptr_list *)rl);
 149         return drange->min;
 150 }
 151
 152 long long rl_max(struct range_list *rl)
 153 {
 154         struct data_range *drange;
 155
 156         if (ptr_list_empty(rl))
 157                 return whole_range.max;
 158         drange = last_ptr_list((struct ptr_list *)rl);
 159         return drange->max;
 160 }
 161
 162 static struct data_range *alloc_range_helper(long long min, long long max, int perm)
 163 {
 164         struct data_range *ret;
 165
 166         if (min > max) {
 167                 sm_msg("Error invalid range %lld to %lld", min, max);
 168                 min = whole_range.min;
 169                 max = whole_range.max;
 170         }
 171         if (min == whole_range.min && max == whole_range.max)
 172                 return &whole_range;
 173         if (min == 0 && max == 0)
 174                 return &range_zero;
 175         if (min == 1 && max == 1)
 176                 return &range_one;
 177
 178         if (perm)
 179                 ret = __alloc_perm_data_range(0);
 180         else
 181                 ret = __alloc_data_range(0);
 182         ret->min = min;
 183         ret->max = max;
 184         return ret;
 185 }
 186
 187 struct data_range *alloc_range(long long min, long long max)
 188 {
 189         return alloc_range_helper(min, max, 0);
 190 }
 191
 192 struct data_range *alloc_range_perm(long long min, long long max)
 193 {
 194         return alloc_range_helper(min, max, 1);
 195 }
 196
 197 struct range_list *alloc_range_list(long long min, long long max)
 198 {
 199         struct range_list *rl = NULL;
 200
 201         add_range(&rl, min, max);
 202         return rl;
 203 }
 204
 205 struct range_list *whole_range_list(void)
 206 {
 207         return alloc_range_list(whole_range.min, whole_range.max);
 208 }
 209
 210 void add_range(struct range_list **list, long long min, long long max)
 211 {
 212         struct data_range *tmp = NULL;
 213         struct data_range *new = NULL;
 214         int check_next = 0;
 215
 216         /*
 217          * FIXME:  This has a problem merging a range_list like: min-0,3-max
 218          * with a range like 1-2.  You end up with min-2,3-max instead of
 219          * just min-max.
 220          */
 221         FOR_EACH_PTR(*list, tmp) {
 222                 if (check_next) {
 223                         /* Sometimes we overlap with more than one range
 224                            so we have to delete or modify the next range. */
 225                         if (max + 1 == tmp->min) {
 226                                 /* join 2 ranges here */
 227                                 new->max = tmp->max;
 228                                 DELETE_CURRENT_PTR(tmp);
 229                                 return;
 230                         }
 231
 232                         /* Doesn't overlap with the next one. */
 233                         if (max < tmp->min)
 234                                 return;
 235                         /* Partially overlaps with the next one. */
 236                         if (max < tmp->max) {
 237                                 tmp->min = max + 1;
 238                                 return;
 239                         }
 240                         /* Completely overlaps with the next one. */
 241                         if (max >= tmp->max) {
 242                                 DELETE_CURRENT_PTR(tmp);
 243                                 /* there could be more ranges to delete */
 244                                 continue;
 245                         }
 246                 }
 247                 if (max != whole_range.max && max + 1 == tmp->min) {
 248                         /* join 2 ranges into a big range */
 249                         new = alloc_range(min, tmp->max);
 250                         REPLACE_CURRENT_PTR(tmp, new);
 251                         return;
 252                 }
 253                 if (max < tmp->min) {  /* new range entirely below */
 254                         new = alloc_range(min, max);
 255                         INSERT_CURRENT(new, tmp);
 256                         return;
 257                 }
 258                 if (min < tmp->min) { /* new range partially below */
 259                         if (max < tmp->max)
 260                                 max = tmp->max;
 261                         else
 262                                 check_next = 1;
 263                         new = alloc_range(min, max);
 264                         REPLACE_CURRENT_PTR(tmp, new);
 265                         if (!check_next)
 266                                 return;
 267                         continue;
 268                 }
 269                 if (max <= tmp->max) /* new range already included */
 270                         return;
 271                 if (min <= tmp->max) { /* new range partially above */
 272                         min = tmp->min;
 273                         new = alloc_range(min, max);
 274                         REPLACE_CURRENT_PTR(tmp, new);
 275                         check_next = 1;
 276                         continue;
 277                 }
 278                 if (min != whole_range.min && min - 1 == tmp->max) {
 279                         /* join 2 ranges into a big range */
 280                         new = alloc_range(tmp->min, max);
 281                         REPLACE_CURRENT_PTR(tmp, new);
 282                         check_next = 1;
 283                         continue;
 284                 }
 285                 /* the new range is entirely above the existing ranges */
 286         } END_FOR_EACH_PTR(tmp);
 287         if (check_next)
 288                 return;
 289         new = alloc_range(min, max);
 290         add_ptr_list(list, new);
 291 }
 292
 293 struct range_list *clone_range_list(struct range_list *list)
 294 {
 295         struct data_range *tmp;
 296         struct range_list *ret = NULL;
 297
 298         FOR_EACH_PTR(list, tmp) {
 299                 add_ptr_list(&ret, tmp);
 300         } END_FOR_EACH_PTR(tmp);
 301         return ret;
 302 }
 303
 304 struct range_list *clone_permanent(struct range_list *list)
 305 {
 306         struct data_range *tmp;
 307         struct data_range *new;
 308         struct range_list *ret = NULL;
 309
 310         FOR_EACH_PTR(list, tmp) {
 311                 new = alloc_range_perm(tmp->min, tmp->max);
 312                 add_ptr_list(&ret, new);
 313         } END_FOR_EACH_PTR(tmp);
 314         return ret;
 315 }
 316
 317 struct range_list *range_list_union(struct range_list *one, struct range_list *two)
 318 {
 319         struct data_range *tmp;
 320         struct range_list *ret = NULL;
 321
 322         FOR_EACH_PTR(one, tmp) {
 323                 add_range(&ret, tmp->min, tmp->max);
 324         } END_FOR_EACH_PTR(tmp);
 325         FOR_EACH_PTR(two, tmp) {
 326                 add_range(&ret, tmp->min, tmp->max);
 327         } END_FOR_EACH_PTR(tmp);
 328         return ret;
 329 }
 330
 331 struct range_list *remove_range(struct range_list *list, long long min, long long max)
 332 {
 333         struct data_range *tmp;
 334         struct range_list *ret = NULL;
 335
 336         FOR_EACH_PTR(list, tmp) {
 337                 if (tmp->max < min) {
 338                         add_range(&ret, tmp->min, tmp->max);
 339                         continue;
 340                 }
 341                 if (tmp->min > max) {
 342                         add_range(&ret, tmp->min, tmp->max);
 343                         continue;
 344                 }
 345                 if (tmp->min >= min && tmp->max <= max)
 346                         continue;
 347                 if (tmp->min >= min) {
 348                         add_range(&ret, max + 1, tmp->max);
 349                 } else if (tmp->max <= max) {
 350                         add_range(&ret, tmp->min, min - 1);
 351                 } else {
 352                         add_range(&ret, tmp->min, min - 1);
 353                         add_range(&ret, max + 1, tmp->max);
 354                 }
 355         } END_FOR_EACH_PTR(tmp);
 356         return ret;
 357 }
 358
 359 struct range_list *invert_range_list(struct range_list *orig)
 360 {
 361         struct range_list *ret = NULL;
 362         struct data_range *tmp;
 363         long long gap_min;
 364
 365         if (!orig)
 366                 return NULL;
 367
 368         gap_min = whole_range.min;
 369         FOR_EACH_PTR(orig, tmp) {
 370                 if (tmp->min > gap_min)
 371                         add_range(&ret, gap_min, tmp->min - 1);
 372                 gap_min = tmp->max + 1;
 373                 if (tmp->max == whole_range.max)
 374                         gap_min = whole_range.max;
 375         } END_FOR_EACH_PTR(tmp);
 376
 377         if (gap_min != whole_range.max)
 378                 add_range(&ret, gap_min, whole_range.max);
 379
 380         return ret;
 381 }
 382
 383 /*
 384  * if it can be only one and only value return 1, else return 0
 385  */
 386 int estate_get_single_value(struct smatch_state *state, long long *val)
 387 {
 388         struct data_info *dinfo;
 389         struct data_range *tmp;
 390         int count = 0;
 391
 392         dinfo = get_dinfo(state);
 393         if (!dinfo || dinfo->type != DATA_RANGE)
 394                 return 0;
 395
 396         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 397                 if (!count++) {
 398                         if (tmp->min != tmp->max)
 399                                 return 0;
 400                         *val = tmp->min;
 401                 } else {
 402                         return 0;
 403                 }
 404         } END_FOR_EACH_PTR(tmp);
 405         return count;
 406 }
 407
 408 int range_lists_equiv(struct range_list *one, struct range_list *two)
 409 {
 410         struct data_range *one_range;
 411         struct data_range *two_range;
 412
 413         PREPARE_PTR_LIST(one, one_range);
 414         PREPARE_PTR_LIST(two, two_range);
 415         for (;;) {
 416                 if (!one_range && !two_range)
 417                         return 1;
 418                 if (!one_range || !two_range)
 419                         return 0;
 420                 if (one_range->min != two_range->min)
 421                         return 0;
 422                 if (one_range->max != two_range->max)
 423                         return 0;
 424                 NEXT_PTR_LIST(one_range);
 425                 NEXT_PTR_LIST(two_range);
 426         }
 427         FINISH_PTR_LIST(two_range);
 428         FINISH_PTR_LIST(one_range);
 429
 430         return 1;
 431 }
 432
 433 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
 434 {
 435         switch (comparison) {
 436         case '<':
 437         case SPECIAL_UNSIGNED_LT:
 438                 if (left->min < right->max)
 439                         return 1;
 440                 return 0;
 441         case SPECIAL_UNSIGNED_LTE:
 442         case SPECIAL_LTE:
 443                 if (left->min <= right->max)
 444                         return 1;
 445                 return 0;
 446         case SPECIAL_EQUAL:
 447                 if (left->max < right->min)
 448                         return 0;
 449                 if (left->min > right->max)
 450                         return 0;
 451                 return 1;
 452         case SPECIAL_UNSIGNED_GTE:
 453         case SPECIAL_GTE:
 454                 if (left->max >= right->min)
 455                         return 1;
 456                 return 0;
 457         case '>':
 458         case SPECIAL_UNSIGNED_GT:
 459                 if (left->max > right->min)
 460                         return 1;
 461                 return 0;
 462         case SPECIAL_NOTEQUAL:
 463                 if (left->min != left->max)
 464                         return 1;
 465                 if (right->min != right->max)
 466                         return 1;
 467                 if (left->min != right->min)
 468                         return 1;
 469                 return 0;
 470         default:
 471                 sm_msg("unhandled comparison %d\n", comparison);
 472                 return 0;
 473         }
 474         return 0;
 475 }
 476
 477 int true_comparison_range_lr(int comparison, struct data_range *var, struct data_range *val, int left)
 478 {
 479         if (left)
 480                 return true_comparison_range(var, comparison, val);
 481         else
 482                 return true_comparison_range(val, comparison, var);
 483 }
 484
 485 static int false_comparison_range(struct data_range *left, int comparison, struct data_range *right)
 486 {
 487         switch (comparison) {
 488         case '<':
 489         case SPECIAL_UNSIGNED_LT:
 490                 if (left->max >= right->min)
 491                         return 1;
 492                 return 0;
 493         case SPECIAL_UNSIGNED_LTE:
 494         case SPECIAL_LTE:
 495                 if (left->max > right->min)
 496                         return 1;
 497                 return 0;
 498         case SPECIAL_EQUAL:
 499                 if (left->min != left->max)
 500                         return 1;
 501                 if (right->min != right->max)
 502                         return 1;
 503                 if (left->min != right->min)
 504                         return 1;
 505                 return 0;
 506         case SPECIAL_UNSIGNED_GTE:
 507         case SPECIAL_GTE:
 508                 if (left->min < right->max)
 509                         return 1;
 510                 return 0;
 511         case '>':
 512         case SPECIAL_UNSIGNED_GT:
 513                 if (left->min <= right->max)
 514                         return 1;
 515                 return 0;
 516         case SPECIAL_NOTEQUAL:
 517                 if (left->max < right->min)
 518                         return 0;
 519                 if (left->min > right->max)
 520                         return 0;
 521                 return 1;
 522         default:
 523                 sm_msg("unhandled comparison %d\n", comparison);
 524                 return 0;
 525         }
 526         return 0;
 527 }
 528
 529 int false_comparison_range_lr(int comparison, struct data_range *var, struct data_range *val, int left)
 530 {
 531         if (left)
 532                 return false_comparison_range(var, comparison, val);
 533         else
 534                 return false_comparison_range(val, comparison, var);
 535 }
 536
 537 int possibly_true(struct expression *left, int comparison, struct expression *right)
 538 {
 539         struct range_list *rl_left, *rl_right;
 540         struct data_range *tmp_left, *tmp_right;
 541
 542         if (!get_implied_range_list(left, &rl_left))
 543                 return 1;
 544         if (!get_implied_range_list(right, &rl_right))
 545                 return 1;
 546
 547         FOR_EACH_PTR(rl_left, tmp_left) {
 548                 FOR_EACH_PTR(rl_right, tmp_right) {
 549                         if (true_comparison_range(tmp_left, comparison, tmp_right))
 550                                 return 1;
 551                 } END_FOR_EACH_PTR(tmp_right);
 552         } END_FOR_EACH_PTR(tmp_left);
 553         return 0;
 554 }
 555
 556 int possibly_false(struct expression *left, int comparison, struct expression *right)
 557 {
 558         struct range_list *rl_left, *rl_right;
 559         struct data_range *tmp_left, *tmp_right;
 560
 561         if (!get_implied_range_list(left, &rl_left))
 562                 return 1;
 563         if (!get_implied_range_list(right, &rl_right))
 564                 return 1;
 565
 566         FOR_EACH_PTR(rl_left, tmp_left) {
 567                 FOR_EACH_PTR(rl_right, tmp_right) {
 568                         if (false_comparison_range(tmp_left, comparison, tmp_right))
 569                                 return 1;
 570                 } END_FOR_EACH_PTR(tmp_right);
 571         } END_FOR_EACH_PTR(tmp_left);
 572         return 0;
 573 }
 574
 575 int possibly_true_range_lists(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 576 {
 577         struct data_range *left_tmp, *right_tmp;
 578
 579         if (!left_ranges || !right_ranges)
 580                 return 1;
 581
 582         FOR_EACH_PTR(left_ranges, left_tmp) {
 583                 FOR_EACH_PTR(right_ranges, right_tmp) {
 584                         if (true_comparison_range(left_tmp, comparison, right_tmp))
 585                                 return 1;
 586                 } END_FOR_EACH_PTR(right_tmp);
 587         } END_FOR_EACH_PTR(left_tmp);
 588         return 0;
 589 }
 590
 591 int possibly_false_range_lists(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 592 {
 593         struct data_range *left_tmp, *right_tmp;
 594
 595         if (!left_ranges || !right_ranges)
 596                 return 1;
 597
 598         FOR_EACH_PTR(left_ranges, left_tmp) {
 599                 FOR_EACH_PTR(right_ranges, right_tmp) {
 600                         if (false_comparison_range(left_tmp, comparison, right_tmp))
 601                                 return 1;
 602                 } END_FOR_EACH_PTR(right_tmp);
 603         } END_FOR_EACH_PTR(left_tmp);
 604         return 0;
 605 }
 606
 607 int possibly_true_range_lists_rl(int comparison, struct range_list *a, struct range_list *b, int left)
 608 {
 609         if (left)
 610                 return possibly_true_range_lists(a, comparison, b);
 611         else
 612                 return possibly_true_range_lists(b, comparison, a);
 613 }
 614
 615 int possibly_false_range_lists_rl(int comparison, struct range_list *a, struct range_list *b, int left)
 616 {
 617         if (left)
 618                 return possibly_false_range_lists(a, comparison, b);
 619         else
 620                 return possibly_false_range_lists(b, comparison, a);
 621 }
 622
 623 void tack_on(struct range_list **list, struct data_range *drange)
 624 {
 625         add_ptr_list(list, drange);
 626 }
 627
 628 int in_list_exact(struct range_list *list, struct data_range *drange)
 629 {
 630         struct data_range *tmp;
 631
 632         FOR_EACH_PTR(list, tmp) {
 633                 if (tmp->min == drange->min && tmp->max == drange->max)
 634                         return 1;
 635         } END_FOR_EACH_PTR(tmp);
 636         return 0;
 637
 638 }
 639
 640 void push_range_list(struct range_list_stack **rl_stack, struct range_list *rl)
 641 {
 642         add_ptr_list(rl_stack, rl);
 643 }
 644
 645 struct range_list *pop_range_list(struct range_list_stack **rl_stack)
 646 {
 647         struct range_list *rl;
 648
 649         rl = last_ptr_list((struct ptr_list *)*rl_stack);
 650         delete_ptr_list_last((struct ptr_list **)rl_stack);
 651         return rl;
 652 }
 653
 654 struct range_list *top_range_list(struct range_list_stack *rl_stack)
 655 {
 656         struct range_list *rl;
 657
 658         rl = last_ptr_list((struct ptr_list *)rl_stack);
 659         return rl;
 660 }
 661
 662 void filter_top_range_list(struct range_list_stack **rl_stack, long long num)
 663 {
 664         struct range_list *rl;
 665
 666         rl = pop_range_list(rl_stack);
 667         rl = remove_range(rl, num, num);
 668         push_range_list(rl_stack, rl);
 669 }
 670
 671 void free_range_list(struct range_list **rlist)
 672 {
 673         __free_ptr_list((struct ptr_list **)rlist);
 674 }
 675
 676 static void free_single_dinfo(struct data_info *dinfo)
 677 {
 678         if (dinfo->type == DATA_RANGE)
 679                 free_range_list(&dinfo->value_ranges);
 680 }
 681
 682 static void free_dinfos(struct allocation_blob *blob)
 683 {
 684         unsigned int size = sizeof(struct data_info);
 685         unsigned int offset = 0;
 686
 687         while (offset < blob->offset) {
 688                 free_single_dinfo((struct data_info *)(blob->data + offset));
 689                 offset += size;
 690         }
 691 }
 692
 693 void free_data_info_allocs(void)
 694 {
 695         struct allocator_struct *desc = &data_info_allocator;
 696         struct allocation_blob *blob = desc->blobs;
 697
 698         desc->blobs = NULL;
 699         desc->allocations = 0;
 700         desc->total_bytes = 0;
 701         desc->useful_bytes = 0;
 702         desc->freelist = NULL;
 703         while (blob) {
 704                 struct allocation_blob *next = blob->next;
 705                 free_dinfos(blob);
 706                 blob_free(blob, desc->chunking);
 707                 blob = next;
 708         }
 709         clear_data_range_alloc();
 710 }
 711