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