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 static char *show_num(long long num)
  21 {
  22         static char buff[256];
  23
  24         if (num == whole_range.min) {
  25                 snprintf(buff, 255, "min");
  26         } else if (num == whole_range.max) {
  27                 snprintf(buff, 255, "max");
  28         } else if (num < 0) {
  29                 snprintf(buff, 255, "(%lld)", num);
  30         } else {
  31                 snprintf(buff, 255, "%lld", num);
  32         }
  33         buff[255] = '\0';
  34         return buff;
  35 }
  36
  37 char *show_ranges(struct range_list *list)
  38 {
  39         struct data_range *tmp;
  40         char full[256];
  41         int i = 0;
  42
  43         full[0] = '\0';
  44         full[255] = '\0';
  45         FOR_EACH_PTR(list, tmp) {
  46                 if (i++)
  47                         strncat(full, ",", 254 - strlen(full));
  48                 if (tmp->min == tmp->max) {
  49                         strncat(full, show_num(tmp->min), 254 - strlen(full));
  50                         continue;
  51                 }
  52                 strncat(full, show_num(tmp->min), 254 - strlen(full));
  53                 strncat(full, "-", 254 - strlen(full));
  54                 strncat(full, show_num(tmp->max), 254 - strlen(full));
  55         } END_FOR_EACH_PTR(tmp);
  56         return alloc_sname(full);
  57 }
  58
  59 static struct data_range range_zero = {
  60         .min = 0,
  61         .max = 0,
  62 };
  63
  64 static struct data_range range_one = {
  65         .min = 1,
  66         .max = 1,
  67 };
  68
  69 int is_whole_range_rl(struct range_list *rl)
  70 {
  71         struct data_range *drange;
  72
  73         if (ptr_list_empty(rl))
  74                 return 1;
  75         drange = first_ptr_list((struct ptr_list *)rl);
  76         if (drange->min == whole_range.min && drange->max == whole_range.max)
  77                 return 1;
  78         return 0;
  79 }
  80
  81 struct data_range *alloc_range(long long min, long long max)
  82 {
  83         struct data_range *ret;
  84
  85         if (min > max) {
  86                 sm_msg("Error invalid range %lld to %lld", min, max);
  87                 min = whole_range.min;
  88                 max = whole_range.max;
  89         }
  90         if (min == whole_range.min && max == whole_range.max)
  91                 return &whole_range;
  92         if (min == 0 && max == 0)
  93                 return &range_zero;
  94         if (min == 1 && max == 1)
  95                 return &range_one;
  96         ret = __alloc_data_range(0);
  97         ret->min = min;
  98         ret->max = max;
  99         return ret;
 100 }
 101
 102 struct data_range *alloc_range_perm(long long min, long long max)
 103 {
 104         struct data_range *ret;
 105
 106         if (min > max) {
 107                 sm_msg("Error invalid range %lld to %lld", min, max);
 108                 min = whole_range.min;
 109                 max = whole_range.max;
 110         }
 111         if (min == whole_range.min && max == whole_range.max)
 112                 return &whole_range;
 113         if (min == 0 && max == 0)
 114                 return &range_zero;
 115         if (min == 1 && max == 1)
 116                 return &range_one;
 117         ret = __alloc_perm_data_range(0);
 118         ret->min = min;
 119         ret->max = max;
 120         return ret;
 121 }
 122
 123 void add_range(struct range_list **list, long long min, long long max)
 124 {
 125         struct data_range *tmp = NULL;
 126         struct data_range *new = NULL;
 127         int check_next = 0;
 128
 129         FOR_EACH_PTR(*list, tmp) {
 130                 if (check_next) {
 131                         /* Sometimes we overlap with more than one range
 132                            so we have to delete or modify the next range. */
 133                         if (max + 1 == tmp->min) {
 134                                 /* join 2 ranges here */
 135                                 new->max = tmp->max;
 136                                 DELETE_CURRENT_PTR(tmp);
 137                                 return;
 138                         }
 139
 140                         /* Doesn't overlap with the next one. */
 141                         if (max < tmp->min)
 142                                 return;
 143                         /* Partially overlaps with the next one. */
 144                         if (max < tmp->max) {
 145                                 tmp->min = max + 1;
 146                                 return;
 147                         }
 148                         /* Completely overlaps with the next one. */
 149                         if (max >= tmp->max) {
 150                                 DELETE_CURRENT_PTR(tmp);
 151                                 /* there could be more ranges to delete */
 152                                 continue;
 153                         }
 154                 }
 155                 if (max != whole_range.max && max + 1 == tmp->min) {
 156                         /* join 2 ranges into a big range */
 157                         new = alloc_range(min, tmp->max);
 158                         REPLACE_CURRENT_PTR(tmp, new);
 159                         return;
 160                 }
 161                 if (max < tmp->min) {  /* new range entirely below */
 162                         new = alloc_range(min, max);
 163                         INSERT_CURRENT(new, tmp);
 164                         return;
 165                 }
 166                 if (min < tmp->min) { /* new range partially below */
 167                         if (max < tmp->max)
 168                                 max = tmp->max;
 169                         else
 170                                 check_next = 1;
 171                         new = alloc_range(min, max);
 172                         REPLACE_CURRENT_PTR(tmp, new);
 173                         if (!check_next)
 174                                 return;
 175                         continue;
 176                 }
 177                 if (max <= tmp->max) /* new range already included */
 178                         return;
 179                 if (min <= tmp->max) { /* new range partially above */
 180                         min = tmp->min;
 181                         new = alloc_range(min, max);
 182                         REPLACE_CURRENT_PTR(tmp, new);
 183                         check_next = 1;
 184                         continue;
 185                 }
 186                 if (min != whole_range.min && min - 1 == tmp->max) {
 187                         /* join 2 ranges into a big range */
 188                         new = alloc_range(tmp->min, max);
 189                         REPLACE_CURRENT_PTR(tmp, new);
 190                         check_next = 1;
 191                         continue;
 192                 }
 193                 /* the new range is entirely above the existing ranges */
 194         } END_FOR_EACH_PTR(tmp);
 195         if (check_next)
 196                 return;
 197         new = alloc_range(min, max);
 198         add_ptr_list(list, new);
 199 }
 200
 201 struct range_list *clone_range_list(struct range_list *list)
 202 {
 203         struct data_range *tmp;
 204         struct range_list *ret = NULL;
 205
 206         FOR_EACH_PTR(list, tmp) {
 207                 add_ptr_list(&ret, tmp);
 208         } END_FOR_EACH_PTR(tmp);
 209         return ret;
 210 }
 211
 212 struct range_list *range_list_union(struct range_list *one, struct range_list *two)
 213 {
 214         struct data_range *tmp;
 215         struct range_list *ret = NULL;
 216
 217         FOR_EACH_PTR(one, tmp) {
 218                 add_range(&ret, tmp->min, tmp->max);
 219         } END_FOR_EACH_PTR(tmp);
 220         FOR_EACH_PTR(two, tmp) {
 221                 add_range(&ret, tmp->min, tmp->max);
 222         } END_FOR_EACH_PTR(tmp);
 223         return ret;
 224 }
 225
 226 struct range_list *remove_range(struct range_list *list, long long min, long long max)
 227 {
 228         struct data_range *tmp;
 229         struct range_list *ret = NULL;
 230
 231         FOR_EACH_PTR(list, tmp) {
 232                 if (tmp->max < min) {
 233                         add_range(&ret, tmp->min, tmp->max);
 234                         continue;
 235                 }
 236                 if (tmp->min > max) {
 237                         add_range(&ret, tmp->min, tmp->max);
 238                         continue;
 239                 }
 240                 if (tmp->min >= min && tmp->max <= max)
 241                         continue;
 242                 if (tmp->min >= min) {
 243                         add_range(&ret, max + 1, tmp->max);
 244                 } else if (tmp->max <= max) {
 245                         add_range(&ret, tmp->min, min - 1);
 246                 } else {
 247                         add_range(&ret, tmp->min, min - 1);
 248                         add_range(&ret, max + 1, tmp->max);
 249                 }
 250         } END_FOR_EACH_PTR(tmp);
 251         return ret;
 252 }
 253
 254 long long get_dinfo_min(struct data_info *dinfo)
 255 {
 256         struct data_range *drange;
 257
 258         if (!dinfo || !dinfo->value_ranges)
 259                 return whole_range.min;
 260         drange = first_ptr_list((struct ptr_list *)dinfo->value_ranges);
 261         return drange->min;
 262 }
 263
 264 long long get_dinfo_max(struct data_info *dinfo)
 265 {
 266         struct data_range *drange;
 267
 268         if (!dinfo || !dinfo->value_ranges)
 269                 return whole_range.max;
 270         drange = last_ptr_list((struct ptr_list *)dinfo->value_ranges);
 271         return drange->max;
 272 }
 273
 274 /*
 275  * if it can be only one and only value return 1, else return 0
 276  */
 277 int get_single_value_from_dinfo(struct data_info *dinfo, long long *val)
 278 {
 279         struct data_range *tmp;
 280         int count = 0;
 281
 282         if (dinfo->type != DATA_RANGE)
 283                 return 0;
 284
 285         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 286                 if (!count++) {
 287                         if (tmp->min != tmp->max)
 288                                 return 0;
 289                         *val = tmp->min;
 290                 } else {
 291                         return 0;
 292                 }
 293         } END_FOR_EACH_PTR(tmp);
 294         return count;
 295 }
 296
 297 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
 298 {
 299         switch (comparison) {
 300         case '<':
 301         case SPECIAL_UNSIGNED_LT:
 302                 if (left->min < right->max)
 303                         return 1;
 304                 return 0;
 305         case SPECIAL_UNSIGNED_LTE:
 306         case SPECIAL_LTE:
 307                 if (left->min <= right->max)
 308                         return 1;
 309                 return 0;
 310         case SPECIAL_EQUAL:
 311                 if (left->max < right->min)
 312                         return 0;
 313                 if (left->min > right->max)
 314                         return 0;
 315                 return 1;
 316         case SPECIAL_UNSIGNED_GTE:
 317         case SPECIAL_GTE:
 318                 if (left->max >= right->min)
 319                         return 1;
 320                 return 0;
 321         case '>':
 322         case SPECIAL_UNSIGNED_GT:
 323                 if (left->max > right->min)
 324                         return 1;
 325                 return 0;
 326         case SPECIAL_NOTEQUAL:
 327                 if (left->min != left->max)
 328                         return 1;
 329                 if (right->min != right->max)
 330                         return 1;
 331                 if (left->min != right->min)
 332                         return 1;
 333                 return 0;
 334         default:
 335                 sm_msg("unhandled comparison %d\n", comparison);
 336                 return 0;
 337         }
 338         return 0;
 339 }
 340
 341 int true_comparison_range_lr(int comparison, struct data_range *var, struct data_range *val, int left)
 342 {
 343         if (left)
 344                 return true_comparison_range(var, comparison, val);
 345         else
 346                 return true_comparison_range(val, comparison, var);
 347 }
 348
 349 static int false_comparison_range(struct data_range *left, int comparison, struct data_range *right)
 350 {
 351         switch (comparison) {
 352         case '<':
 353         case SPECIAL_UNSIGNED_LT:
 354                 if (left->max >= right->min)
 355                         return 1;
 356                 return 0;
 357         case SPECIAL_UNSIGNED_LTE:
 358         case SPECIAL_LTE:
 359                 if (left->max > right->min)
 360                         return 1;
 361                 return 0;
 362         case SPECIAL_EQUAL:
 363                 if (left->min != left->max)
 364                         return 1;
 365                 if (right->min != right->max)
 366                         return 1;
 367                 if (left->min != right->min)
 368                         return 1;
 369                 return 0;
 370         case SPECIAL_UNSIGNED_GTE:
 371         case SPECIAL_GTE:
 372                 if (left->min < right->max)
 373                         return 1;
 374                 return 0;
 375         case '>':
 376         case SPECIAL_UNSIGNED_GT:
 377                 if (left->min <= right->max)
 378                         return 1;
 379                 return 0;
 380         case SPECIAL_NOTEQUAL:
 381                 if (left->max < right->min)
 382                         return 0;
 383                 if (left->min > right->max)
 384                         return 0;
 385                 return 1;
 386         default:
 387                 sm_msg("unhandled comparison %d\n", comparison);
 388                 return 0;
 389         }
 390         return 0;
 391 }
 392
 393 int false_comparison_range_lr(int comparison, struct data_range *var, struct data_range *val, int left)
 394 {
 395         if (left)
 396                 return false_comparison_range(var, comparison, val);
 397         else
 398                 return false_comparison_range(val, comparison, var);
 399 }
 400
 401 int possibly_true(int comparison, struct data_info *dinfo, long long num, int left)
 402 {
 403         struct data_range *tmp;
 404         struct data_range drange;
 405
 406         if (!dinfo)
 407                 return 1;
 408
 409         drange.min = num;
 410         drange.max = num;
 411
 412         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 413                 if (true_comparison_range_lr(comparison, tmp, &drange, left))
 414                         return 1;
 415         } END_FOR_EACH_PTR(tmp);
 416         return 0;
 417 }
 418
 419 int possibly_false(int comparison, struct data_info *dinfo, long long num, int left)
 420 {
 421         struct data_range *tmp;
 422         struct data_range drange;
 423
 424         if (!dinfo)
 425                 return 1;
 426
 427         drange.min = num;
 428         drange.max = num;
 429
 430         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 431                 if (false_comparison_range_lr(comparison, tmp, &drange, left))
 432                         return 1;
 433         } END_FOR_EACH_PTR(tmp);
 434         return 0;
 435 }
 436
 437 int possibly_true_range_lists(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 438 {
 439         struct data_range *left_tmp, *right_tmp;
 440
 441         if (!left_ranges || !right_ranges)
 442                 return 1;
 443
 444         FOR_EACH_PTR(left_ranges, left_tmp) {
 445                 FOR_EACH_PTR(right_ranges, right_tmp) {
 446                         if (true_comparison_range(left_tmp, comparison, right_tmp))
 447                                 return 1;
 448                 } END_FOR_EACH_PTR(right_tmp);
 449         } END_FOR_EACH_PTR(left_tmp);
 450         return 0;
 451 }
 452
 453 int possibly_true_range_list_lr(int comparison, struct data_info *dinfo, struct range_list *values, int left)
 454 {
 455         struct data_range *tmp, *tmp2;
 456
 457         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 458                 FOR_EACH_PTR(values, tmp2) {
 459                         if (true_comparison_range_lr(comparison, tmp, tmp2, left))
 460                                 return 1;
 461                 } END_FOR_EACH_PTR(tmp2);
 462         } END_FOR_EACH_PTR(tmp);
 463         return 0;
 464 }
 465
 466 int possibly_false_range_lists(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 467 {
 468         struct data_range *left_tmp, *right_tmp;
 469
 470         if (!left_ranges || !right_ranges)
 471                 return 1;
 472
 473         FOR_EACH_PTR(left_ranges, left_tmp) {
 474                 FOR_EACH_PTR(right_ranges, right_tmp) {
 475                         if (false_comparison_range(left_tmp, comparison, right_tmp))
 476                                 return 1;
 477                 } END_FOR_EACH_PTR(right_tmp);
 478         } END_FOR_EACH_PTR(left_tmp);
 479         return 0;
 480 }
 481
 482 int possibly_false_range_list_lr(int comparison, struct data_info *dinfo, struct range_list *values, int left)
 483 {
 484         struct data_range *tmp, *tmp2;
 485
 486         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 487                 FOR_EACH_PTR(values, tmp2) {
 488                         if (false_comparison_range_lr(comparison, tmp, tmp2, left))
 489                                 return 1;
 490                 } END_FOR_EACH_PTR(tmp2);
 491         } END_FOR_EACH_PTR(tmp);
 492         return 0;
 493 }
 494
 495 void tack_on(struct range_list **list, struct data_range *drange)
 496 {
 497         add_ptr_list(list, drange);
 498 }
 499
 500 int in_list_exact(struct range_list *list, struct data_range *drange)
 501 {
 502         struct data_range *tmp;
 503
 504         FOR_EACH_PTR(list, tmp) {
 505                 if (tmp->min == drange->min && tmp->max == drange->max)
 506                         return 1;
 507         } END_FOR_EACH_PTR(tmp);
 508         return 0;
 509
 510 }
 511
 512 void push_range_list(struct range_list_stack **rl_stack, struct range_list *rl)
 513 {
 514         add_ptr_list(rl_stack, rl);
 515 }
 516
 517 struct range_list *pop_range_list(struct range_list_stack **rl_stack)
 518 {
 519         struct range_list *rl;
 520
 521         rl = last_ptr_list((struct ptr_list *)*rl_stack);
 522         delete_ptr_list_last((struct ptr_list **)rl_stack);
 523         return rl;
 524 }
 525
 526 struct range_list *top_range_list(struct range_list_stack *rl_stack)
 527 {
 528         struct range_list *rl;
 529
 530         rl = last_ptr_list((struct ptr_list *)rl_stack);
 531         return rl;
 532 }
 533
 534 void filter_top_range_list(struct range_list_stack **rl_stack, long long num)
 535 {
 536         struct range_list *rl;
 537
 538         rl = pop_range_list(rl_stack);
 539         rl = remove_range(rl, num, num);
 540         push_range_list(rl_stack, rl);
 541 }
 542
 543 void free_range_list(struct range_list **rlist)
 544 {
 545         __free_ptr_list((struct ptr_list **)rlist);
 546 }
 547
 548 static void free_single_dinfo(struct data_info *dinfo)
 549 {
 550         if (dinfo->type == DATA_RANGE)
 551                 free_range_list(&dinfo->value_ranges);
 552 }
 553
 554 static void free_dinfos(struct allocation_blob *blob)
 555 {
 556         unsigned int size = sizeof(struct data_info);
 557         unsigned int offset = 0;
 558
 559         while (offset < blob->offset) {
 560                 free_single_dinfo((struct data_info *)(blob->data + offset));
 561                 offset += size;
 562         }
 563 }
 564
 565 void free_data_info_allocs(void)
 566 {
 567         struct allocator_struct *desc = &data_info_allocator;
 568         struct allocation_blob *blob = desc->blobs;
 569
 570         desc->blobs = NULL;
 571         desc->allocations = 0;
 572         desc->total_bytes = 0;
 573         desc->useful_bytes = 0;
 574         desc->freelist = NULL;
 575         while (blob) {
 576                 struct allocation_blob *next = blob->next;
 577                 free_dinfos(blob);
 578                 blob_free(blob, desc->chunking);
 579                 blob = next;
 580         }
 581         clear_data_range_alloc();
 582 }
 583