smatch_ranges.c

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