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