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