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 int rl_contiguous(struct range_list *rl)
 143 {
 144         if (first_ptr_list((struct ptr_list *)rl) == last_ptr_list((struct ptr_list *)rl))
 145                 return 1;
 146         return 0;
 147 }
 148
 149 long long rl_min(struct range_list *rl)
 150 {
 151         struct data_range *drange;
 152
 153         if (ptr_list_empty(rl))
 154                 return whole_range.min;
 155         drange = first_ptr_list((struct ptr_list *)rl);
 156         return drange->min;
 157 }
 158
 159 long long rl_max(struct range_list *rl)
 160 {
 161         struct data_range *drange;
 162
 163         if (ptr_list_empty(rl))
 164                 return whole_range.max;
 165         drange = last_ptr_list((struct ptr_list *)rl);
 166         return drange->max;
 167 }
 168
 169 static struct data_range *alloc_range_helper(long long min, long long max, int perm)
 170 {
 171         struct data_range *ret;
 172
 173         if (min > max) {
 174                 sm_msg("Error invalid range %lld to %lld", min, max);
 175                 min = whole_range.min;
 176                 max = whole_range.max;
 177         }
 178         if (min == whole_range.min && max == whole_range.max)
 179                 return &whole_range;
 180         if (min == 0 && max == 0)
 181                 return &range_zero;
 182         if (min == 1 && max == 1)
 183                 return &range_one;
 184
 185         if (perm)
 186                 ret = __alloc_perm_data_range(0);
 187         else
 188                 ret = __alloc_data_range(0);
 189         ret->min = min;
 190         ret->max = max;
 191         return ret;
 192 }
 193
 194 struct data_range *alloc_range(long long min, long long max)
 195 {
 196         return alloc_range_helper(min, max, 0);
 197 }
 198
 199 struct data_range *alloc_range_perm(long long min, long long max)
 200 {
 201         return alloc_range_helper(min, max, 1);
 202 }
 203
 204 struct range_list *alloc_range_list(long long min, long long max)
 205 {
 206         struct range_list *rl = NULL;
 207
 208         add_range(&rl, min, max);
 209         return rl;
 210 }
 211
 212 struct range_list *whole_range_list(void)
 213 {
 214         return alloc_range_list(whole_range.min, whole_range.max);
 215 }
 216
 217 void add_range(struct range_list **list, long long min, long long max)
 218 {
 219         struct data_range *tmp = NULL;
 220         struct data_range *new = NULL;
 221         int check_next = 0;
 222
 223         /*
 224          * FIXME:  This has a problem merging a range_list like: min-0,3-max
 225          * with a range like 1-2.  You end up with min-2,3-max instead of
 226          * just min-max.
 227          */
 228         FOR_EACH_PTR(*list, tmp) {
 229                 if (check_next) {
 230                         /* Sometimes we overlap with more than one range
 231                            so we have to delete or modify the next range. */
 232                         if (max + 1 == tmp->min) {
 233                                 /* join 2 ranges here */
 234                                 new->max = tmp->max;
 235                                 DELETE_CURRENT_PTR(tmp);
 236                                 return;
 237                         }
 238
 239                         /* Doesn't overlap with the next one. */
 240                         if (max < tmp->min)
 241                                 return;
 242                         /* Partially overlaps with the next one. */
 243                         if (max < tmp->max) {
 244                                 tmp->min = max + 1;
 245                                 return;
 246                         }
 247                         /* Completely overlaps with the next one. */
 248                         if (max >= tmp->max) {
 249                                 DELETE_CURRENT_PTR(tmp);
 250                                 /* there could be more ranges to delete */
 251                                 continue;
 252                         }
 253                 }
 254                 if (max != whole_range.max && max + 1 == tmp->min) {
 255                         /* join 2 ranges into a big range */
 256                         new = alloc_range(min, tmp->max);
 257                         REPLACE_CURRENT_PTR(tmp, new);
 258                         return;
 259                 }
 260                 if (max < tmp->min) {  /* new range entirely below */
 261                         new = alloc_range(min, max);
 262                         INSERT_CURRENT(new, tmp);
 263                         return;
 264                 }
 265                 if (min < tmp->min) { /* new range partially below */
 266                         if (max < tmp->max)
 267                                 max = tmp->max;
 268                         else
 269                                 check_next = 1;
 270                         new = alloc_range(min, max);
 271                         REPLACE_CURRENT_PTR(tmp, new);
 272                         if (!check_next)
 273                                 return;
 274                         continue;
 275                 }
 276                 if (max <= tmp->max) /* new range already included */
 277                         return;
 278                 if (min <= tmp->max) { /* new range partially above */
 279                         min = tmp->min;
 280                         new = alloc_range(min, max);
 281                         REPLACE_CURRENT_PTR(tmp, new);
 282                         check_next = 1;
 283                         continue;
 284                 }
 285                 if (min != whole_range.min && min - 1 == tmp->max) {
 286                         /* join 2 ranges into a big range */
 287                         new = alloc_range(tmp->min, max);
 288                         REPLACE_CURRENT_PTR(tmp, new);
 289                         check_next = 1;
 290                         continue;
 291                 }
 292                 /* the new range is entirely above the existing ranges */
 293         } END_FOR_EACH_PTR(tmp);
 294         if (check_next)
 295                 return;
 296         new = alloc_range(min, max);
 297         add_ptr_list(list, new);
 298 }
 299
 300 struct range_list *clone_range_list(struct range_list *list)
 301 {
 302         struct data_range *tmp;
 303         struct range_list *ret = NULL;
 304
 305         FOR_EACH_PTR(list, tmp) {
 306                 add_ptr_list(&ret, tmp);
 307         } END_FOR_EACH_PTR(tmp);
 308         return ret;
 309 }
 310
 311 struct range_list *clone_permanent(struct range_list *list)
 312 {
 313         struct data_range *tmp;
 314         struct data_range *new;
 315         struct range_list *ret = NULL;
 316
 317         FOR_EACH_PTR(list, tmp) {
 318                 new = alloc_range_perm(tmp->min, tmp->max);
 319                 add_ptr_list(&ret, new);
 320         } END_FOR_EACH_PTR(tmp);
 321         return ret;
 322 }
 323
 324 struct range_list *range_list_union(struct range_list *one, struct range_list *two)
 325 {
 326         struct data_range *tmp;
 327         struct range_list *ret = NULL;
 328
 329         FOR_EACH_PTR(one, tmp) {
 330                 add_range(&ret, tmp->min, tmp->max);
 331         } END_FOR_EACH_PTR(tmp);
 332         FOR_EACH_PTR(two, tmp) {
 333                 add_range(&ret, tmp->min, tmp->max);
 334         } END_FOR_EACH_PTR(tmp);
 335         return ret;
 336 }
 337
 338 struct range_list *remove_range(struct range_list *list, long long min, long long max)
 339 {
 340         struct data_range *tmp;
 341         struct range_list *ret = NULL;
 342
 343         FOR_EACH_PTR(list, tmp) {
 344                 if (tmp->max < min) {
 345                         add_range(&ret, tmp->min, tmp->max);
 346                         continue;
 347                 }
 348                 if (tmp->min > max) {
 349                         add_range(&ret, tmp->min, tmp->max);
 350                         continue;
 351                 }
 352                 if (tmp->min >= min && tmp->max <= max)
 353                         continue;
 354                 if (tmp->min >= min) {
 355                         add_range(&ret, max + 1, tmp->max);
 356                 } else if (tmp->max <= max) {
 357                         add_range(&ret, tmp->min, min - 1);
 358                 } else {
 359                         add_range(&ret, tmp->min, min - 1);
 360                         add_range(&ret, max + 1, tmp->max);
 361                 }
 362         } END_FOR_EACH_PTR(tmp);
 363         return ret;
 364 }
 365
 366 struct range_list *invert_range_list(struct range_list *orig)
 367 {
 368         struct range_list *ret = NULL;
 369         struct data_range *tmp;
 370         long long gap_min;
 371
 372         if (!orig)
 373                 return NULL;
 374
 375         gap_min = whole_range.min;
 376         FOR_EACH_PTR(orig, tmp) {
 377                 if (tmp->min > gap_min)
 378                         add_range(&ret, gap_min, tmp->min - 1);
 379                 gap_min = tmp->max + 1;
 380                 if (tmp->max == whole_range.max)
 381                         gap_min = whole_range.max;
 382         } END_FOR_EACH_PTR(tmp);
 383
 384         if (gap_min != whole_range.max)
 385                 add_range(&ret, gap_min, whole_range.max);
 386
 387         return ret;
 388 }
 389
 390 /*
 391  * if it can be only one and only value return 1, else return 0
 392  */
 393 int estate_get_single_value(struct smatch_state *state, long long *val)
 394 {
 395         struct data_info *dinfo;
 396         struct data_range *tmp;
 397         int count = 0;
 398
 399         dinfo = get_dinfo(state);
 400         if (!dinfo || dinfo->type != DATA_RANGE)
 401                 return 0;
 402
 403         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 404                 if (!count++) {
 405                         if (tmp->min != tmp->max)
 406                                 return 0;
 407                         *val = tmp->min;
 408                 } else {
 409                         return 0;
 410                 }
 411         } END_FOR_EACH_PTR(tmp);
 412         return count;
 413 }
 414
 415 int range_lists_equiv(struct range_list *one, struct range_list *two)
 416 {
 417         struct data_range *one_range;
 418         struct data_range *two_range;
 419
 420         PREPARE_PTR_LIST(one, one_range);
 421         PREPARE_PTR_LIST(two, two_range);
 422         for (;;) {
 423                 if (!one_range && !two_range)
 424                         return 1;
 425                 if (!one_range || !two_range)
 426                         return 0;
 427                 if (one_range->min != two_range->min)
 428                         return 0;
 429                 if (one_range->max != two_range->max)
 430                         return 0;
 431                 NEXT_PTR_LIST(one_range);
 432                 NEXT_PTR_LIST(two_range);
 433         }
 434         FINISH_PTR_LIST(two_range);
 435         FINISH_PTR_LIST(one_range);
 436
 437         return 1;
 438 }
 439
 440 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
 441 {
 442         switch (comparison) {
 443         case '<':
 444         case SPECIAL_UNSIGNED_LT:
 445                 if (left->min < right->max)
 446                         return 1;
 447                 return 0;
 448         case SPECIAL_UNSIGNED_LTE:
 449         case SPECIAL_LTE:
 450                 if (left->min <= right->max)
 451                         return 1;
 452                 return 0;
 453         case SPECIAL_EQUAL:
 454                 if (left->max < right->min)
 455                         return 0;
 456                 if (left->min > right->max)
 457                         return 0;
 458                 return 1;
 459         case SPECIAL_UNSIGNED_GTE:
 460         case SPECIAL_GTE:
 461                 if (left->max >= right->min)
 462                         return 1;
 463                 return 0;
 464         case '>':
 465         case SPECIAL_UNSIGNED_GT:
 466                 if (left->max > right->min)
 467                         return 1;
 468                 return 0;
 469         case SPECIAL_NOTEQUAL:
 470                 if (left->min != left->max)
 471                         return 1;
 472                 if (right->min != right->max)
 473                         return 1;
 474                 if (left->min != right->min)
 475                         return 1;
 476                 return 0;
 477         default:
 478                 sm_msg("unhandled comparison %d\n", comparison);
 479                 return 0;
 480         }
 481         return 0;
 482 }
 483
 484 int true_comparison_range_lr(int comparison, struct data_range *var, struct data_range *val, int left)
 485 {
 486         if (left)
 487                 return true_comparison_range(var, comparison, val);
 488         else
 489                 return true_comparison_range(val, comparison, var);
 490 }
 491
 492 static int false_comparison_range(struct data_range *left, int comparison, struct data_range *right)
 493 {
 494         switch (comparison) {
 495         case '<':
 496         case SPECIAL_UNSIGNED_LT:
 497                 if (left->max >= right->min)
 498                         return 1;
 499                 return 0;
 500         case SPECIAL_UNSIGNED_LTE:
 501         case SPECIAL_LTE:
 502                 if (left->max > right->min)
 503                         return 1;
 504                 return 0;
 505         case SPECIAL_EQUAL:
 506                 if (left->min != left->max)
 507                         return 1;
 508                 if (right->min != right->max)
 509                         return 1;
 510                 if (left->min != right->min)
 511                         return 1;
 512                 return 0;
 513         case SPECIAL_UNSIGNED_GTE:
 514         case SPECIAL_GTE:
 515                 if (left->min < right->max)
 516                         return 1;
 517                 return 0;
 518         case '>':
 519         case SPECIAL_UNSIGNED_GT:
 520                 if (left->min <= right->max)
 521                         return 1;
 522                 return 0;
 523         case SPECIAL_NOTEQUAL:
 524                 if (left->max < right->min)
 525                         return 0;
 526                 if (left->min > right->max)
 527                         return 0;
 528                 return 1;
 529         default:
 530                 sm_msg("unhandled comparison %d\n", comparison);
 531                 return 0;
 532         }
 533         return 0;
 534 }
 535
 536 int false_comparison_range_lr(int comparison, struct data_range *var, struct data_range *val, int left)
 537 {
 538         if (left)
 539                 return false_comparison_range(var, comparison, val);
 540         else
 541                 return false_comparison_range(val, comparison, var);
 542 }
 543
 544 int possibly_true(struct expression *left, int comparison, struct expression *right)
 545 {
 546         struct range_list *rl_left, *rl_right;
 547         struct data_range *tmp_left, *tmp_right;
 548
 549         if (!get_implied_range_list(left, &rl_left))
 550                 return 1;
 551         if (!get_implied_range_list(right, &rl_right))
 552                 return 1;
 553
 554         FOR_EACH_PTR(rl_left, tmp_left) {
 555                 FOR_EACH_PTR(rl_right, tmp_right) {
 556                         if (true_comparison_range(tmp_left, comparison, tmp_right))
 557                                 return 1;
 558                 } END_FOR_EACH_PTR(tmp_right);
 559         } END_FOR_EACH_PTR(tmp_left);
 560         return 0;
 561 }
 562
 563 int possibly_false(struct expression *left, int comparison, struct expression *right)
 564 {
 565         struct range_list *rl_left, *rl_right;
 566         struct data_range *tmp_left, *tmp_right;
 567
 568         if (!get_implied_range_list(left, &rl_left))
 569                 return 1;
 570         if (!get_implied_range_list(right, &rl_right))
 571                 return 1;
 572
 573         FOR_EACH_PTR(rl_left, tmp_left) {
 574                 FOR_EACH_PTR(rl_right, tmp_right) {
 575                         if (false_comparison_range(tmp_left, comparison, tmp_right))
 576                                 return 1;
 577                 } END_FOR_EACH_PTR(tmp_right);
 578         } END_FOR_EACH_PTR(tmp_left);
 579         return 0;
 580 }
 581
 582 int possibly_true_range_lists(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 583 {
 584         struct data_range *left_tmp, *right_tmp;
 585
 586         if (!left_ranges || !right_ranges)
 587                 return 1;
 588
 589         FOR_EACH_PTR(left_ranges, left_tmp) {
 590                 FOR_EACH_PTR(right_ranges, right_tmp) {
 591                         if (true_comparison_range(left_tmp, comparison, right_tmp))
 592                                 return 1;
 593                 } END_FOR_EACH_PTR(right_tmp);
 594         } END_FOR_EACH_PTR(left_tmp);
 595         return 0;
 596 }
 597
 598 int possibly_false_range_lists(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 599 {
 600         struct data_range *left_tmp, *right_tmp;
 601
 602         if (!left_ranges || !right_ranges)
 603                 return 1;
 604
 605         FOR_EACH_PTR(left_ranges, left_tmp) {
 606                 FOR_EACH_PTR(right_ranges, right_tmp) {
 607                         if (false_comparison_range(left_tmp, comparison, right_tmp))
 608                                 return 1;
 609                 } END_FOR_EACH_PTR(right_tmp);
 610         } END_FOR_EACH_PTR(left_tmp);
 611         return 0;
 612 }
 613
 614 int possibly_true_range_lists_rl(int comparison, struct range_list *a, struct range_list *b, int left)
 615 {
 616         if (left)
 617                 return possibly_true_range_lists(a, comparison, b);
 618         else
 619                 return possibly_true_range_lists(b, comparison, a);
 620 }
 621
 622 int possibly_false_range_lists_rl(int comparison, struct range_list *a, struct range_list *b, int left)
 623 {
 624         if (left)
 625                 return possibly_false_range_lists(a, comparison, b);
 626         else
 627                 return possibly_false_range_lists(b, comparison, a);
 628 }
 629
 630 void tack_on(struct range_list **list, struct data_range *drange)
 631 {
 632         add_ptr_list(list, drange);
 633 }
 634
 635 int in_list_exact(struct range_list *list, struct data_range *drange)
 636 {
 637         struct data_range *tmp;
 638
 639         FOR_EACH_PTR(list, tmp) {
 640                 if (tmp->min == drange->min && tmp->max == drange->max)
 641                         return 1;
 642         } END_FOR_EACH_PTR(tmp);
 643         return 0;
 644
 645 }
 646
 647 void push_range_list(struct range_list_stack **rl_stack, struct range_list *rl)
 648 {
 649         add_ptr_list(rl_stack, rl);
 650 }
 651
 652 struct range_list *pop_range_list(struct range_list_stack **rl_stack)
 653 {
 654         struct range_list *rl;
 655
 656         rl = last_ptr_list((struct ptr_list *)*rl_stack);
 657         delete_ptr_list_last((struct ptr_list **)rl_stack);
 658         return rl;
 659 }
 660
 661 struct range_list *top_range_list(struct range_list_stack *rl_stack)
 662 {
 663         struct range_list *rl;
 664
 665         rl = last_ptr_list((struct ptr_list *)rl_stack);
 666         return rl;
 667 }
 668
 669 void filter_top_range_list(struct range_list_stack **rl_stack, long long num)
 670 {
 671         struct range_list *rl;
 672
 673         rl = pop_range_list(rl_stack);
 674         rl = remove_range(rl, num, num);
 675         push_range_list(rl_stack, rl);
 676 }
 677
 678 void free_range_list(struct range_list **rlist)
 679 {
 680         __free_ptr_list((struct ptr_list **)rlist);
 681 }
 682
 683 static void free_single_dinfo(struct data_info *dinfo)
 684 {
 685         if (dinfo->type == DATA_RANGE)
 686                 free_range_list(&dinfo->value_ranges);
 687 }
 688
 689 static void free_dinfos(struct allocation_blob *blob)
 690 {
 691         unsigned int size = sizeof(struct data_info);
 692         unsigned int offset = 0;
 693
 694         while (offset < blob->offset) {
 695                 free_single_dinfo((struct data_info *)(blob->data + offset));
 696                 offset += size;
 697         }
 698 }
 699
 700 void free_data_info_allocs(void)
 701 {
 702         struct allocator_struct *desc = &data_info_allocator;
 703         struct allocation_blob *blob = desc->blobs;
 704
 705         desc->blobs = NULL;
 706         desc->allocations = 0;
 707         desc->total_bytes = 0;
 708         desc->useful_bytes = 0;
 709         desc->freelist = NULL;
 710         while (blob) {
 711                 struct allocation_blob *next = blob->next;
 712                 free_dinfos(blob);
 713                 blob_free(blob, desc->chunking);
 714                 blob = next;
 715         }
 716         clear_data_range_alloc();
 717 }
 718