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_sval, "data range sval");
  17 __DO_ALLOCATOR(struct data_range_sval, sizeof(struct data_range_sval), __alignof__(struct data_range_sval),
  18                          "permanent ranges sval", perm_data_range_sval);
  19
  20 char *show_ranges_sval(struct range_list_sval *list)
  21 {
  22         struct data_range_sval *tmp;
  23         char full[256];
  24         int i = 0;
  25
  26         full[0] = '\0';
  27         full[255] = '\0';
  28         FOR_EACH_PTR(list, tmp) {
  29                 if (i++)
  30                         strncat(full, ",", 254 - strlen(full));
  31                 if (sval_cmp(tmp->min, tmp->max) == 0) {
  32                         strncat(full, sval_to_str(tmp->min), 254 - strlen(full));
  33                         continue;
  34                 }
  35                 strncat(full, sval_to_str(tmp->min), 254 - strlen(full));
  36                 strncat(full, "-", 254 - strlen(full));
  37                 strncat(full, sval_to_str(tmp->max), 254 - strlen(full));
  38         } END_FOR_EACH_PTR(tmp);
  39         return alloc_sname(full);
  40 }
  41
  42 void get_value_ranges_sval(char *value, struct range_list_sval **rl)
  43 {
  44         long long val1, val2;
  45         char *start;
  46         char *c;
  47
  48         *rl = NULL;
  49
  50         c = value;
  51         while (*c) {
  52                 if (*c == '(')
  53                         c++;
  54                 start = c;
  55
  56                 if (!strncmp(start, "max", 3)) {
  57                         val1 = LLONG_MAX;
  58                         c += 3;
  59                 } else if (!strncmp(start, "u64max", 6)) {
  60                         val1 = LLONG_MAX; // FIXME
  61                         c += 6;
  62                 } else if (!strncmp(start, "s64max", 6)) {
  63                         val1 = LLONG_MAX;
  64                         c += 6;
  65                 } else if (!strncmp(start, "u32max", 6)) {
  66                         val1 = UINT_MAX;
  67                         c += 6;
  68                 } else if (!strncmp(start, "s32max", 6)) {
  69                         val1 = INT_MAX;
  70                         c += 6;
  71                 } else if (!strncmp(start, "u16max", 6)) {
  72                         val1 = USHRT_MAX;
  73                         c += 6;
  74                 } else if (!strncmp(start, "s16max", 6)) {
  75                         val1 = SHRT_MAX;
  76                         c += 6;
  77                 } else if (!strncmp(start, "min", 3)) {
  78                         val1 = LLONG_MIN;
  79                         c += 3;
  80                 } else if (!strncmp(start, "s64min", 6)) {
  81                         val1 = LLONG_MIN;
  82                         c += 6;
  83                 } else if (!strncmp(start, "s32min", 6)) {
  84                         val1 = INT_MIN;
  85                         c += 6;
  86                 } else if (!strncmp(start, "s16min", 6)) {
  87                         val1 = SHRT_MIN;
  88                         c += 6;
  89                 } else {
  90                         while (*c && *c != ',' && *c != '-')
  91                                 c++;
  92                         val1 = strtoll(start, &c, 10);
  93                 }
  94                 if (*c == ')')
  95                         c++;
  96                 if (!*c) {
  97                         add_range_sval(rl, ll_to_sval(val1), ll_to_sval(val1));
  98                         break;
  99                 }
 100                 if (*c == ',') {
 101                         add_range_sval(rl, ll_to_sval(val1), ll_to_sval(val1));
 102                         c++;
 103                         start = c;
 104                         continue;
 105                 }
 106                 c++; /* skip the dash in eg. 4-5 */
 107                 if (*c == '(')
 108                         c++;
 109                 start = c;
 110                 if (!strncmp(start, "max", 3)) {
 111                         val2 = LLONG_MAX;
 112                         c += 3;
 113                 } else {
 114
 115                         while (*c && *c != ',' && *c != '-')
 116                                 c++;
 117                         val2 = strtoll(start, &c, 10);
 118                 }
 119                 add_range_sval(rl, ll_to_sval(val1), ll_to_sval(val2));
 120                 if (!*c)
 121                         break;
 122                 if (*c == ')')
 123                         c++;
 124                 c++; /* skip the comma in eg: 4-5,7 */
 125         }
 126 }
 127
 128 int is_whole_range_rl_sval(struct range_list_sval *rl)
 129 {
 130         struct data_range_sval *drange;
 131
 132         if (ptr_list_empty(rl))
 133                 return 1;
 134         drange = first_ptr_list((struct ptr_list *)rl);
 135         if (sval_is_min(drange->min) && sval_is_max(drange->max))
 136                 return 1;
 137         return 0;
 138 }
 139
 140 sval_t rl_min_sval(struct range_list_sval *rl)
 141 {
 142         struct data_range_sval *drange;
 143         sval_t ret;
 144
 145         ret.type = &llong_ctype;
 146         ret.value = LLONG_MIN;
 147         if (ptr_list_empty(rl))
 148                 return ret;
 149         drange = first_ptr_list((struct ptr_list *)rl);
 150         return drange->min;
 151 }
 152
 153 sval_t rl_max_sval(struct range_list_sval *rl)
 154 {
 155         struct data_range_sval *drange;
 156         sval_t ret;
 157
 158         ret.type = &llong_ctype;
 159         ret.value = LLONG_MAX;
 160         if (ptr_list_empty(rl))
 161                 return ret;
 162         drange = last_ptr_list((struct ptr_list *)rl);
 163         return drange->max;
 164 }
 165
 166 static struct data_range_sval *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
 167 {
 168         struct data_range_sval *ret;
 169
 170         if (sval_cmp(min, max) > 0) {
 171                 // sm_msg("debug invalid range %lld to %lld", min, max);
 172                 min.value = LLONG_MIN;  /* fixme: need a way to represent unknown svals */
 173                 max.value = LLONG_MAX;
 174         }
 175
 176         if (perm)
 177                 ret = __alloc_perm_data_range_sval(0);
 178         else
 179                 ret = __alloc_data_range_sval(0);
 180         ret->min = min;
 181         ret->max = max;
 182         return ret;
 183 }
 184
 185 struct data_range_sval *alloc_range_sval(sval_t min, sval_t max)
 186 {
 187         return alloc_range_helper_sval(min, max, 0);
 188 }
 189
 190 struct data_range_sval *alloc_range_perm_sval(sval_t min, sval_t max)
 191 {
 192         return alloc_range_helper_sval(min, max, 1);
 193 }
 194
 195 struct range_list_sval *alloc_range_list_sval(sval_t min, sval_t max)
 196 {
 197         struct range_list_sval *rl = NULL;
 198
 199         add_range_sval(&rl, min, max);
 200         return rl;
 201 }
 202
 203 struct range_list_sval *whole_range_list_sval(struct symbol *type)
 204 {
 205         if (!type)
 206                 type = &llong_ctype;
 207
 208         return alloc_range_list_sval(sval_type_min(type), sval_type_max(type));
 209 }
 210
 211 void add_range_sval(struct range_list_sval **list, sval_t min, sval_t max)
 212 {
 213         struct data_range_sval *tmp = NULL;
 214         struct data_range_sval *new = NULL;
 215         int check_next = 0;
 216
 217         /*
 218          * FIXME:  This has a problem merging a range_list like: min-0,3-max
 219          * with a range like 1-2.  You end up with min-2,3-max instead of
 220          * just min-max.
 221          */
 222         FOR_EACH_PTR(*list, tmp) {
 223                 if (check_next) {
 224                         /* Sometimes we overlap with more than one range
 225                            so we have to delete or modify the next range. */
 226                         if (max.value + 1 == tmp->min.value) {
 227                                 /* join 2 ranges here */
 228                                 new->max = tmp->max;
 229                                 DELETE_CURRENT_PTR(tmp);
 230                                 return;
 231                         }
 232
 233                         /* Doesn't overlap with the next one. */
 234                         if (sval_cmp(max, tmp->min) < 0)
 235                                 return;
 236                         /* Partially overlaps with the next one. */
 237                         if (sval_cmp(max, tmp->max) < 0) {
 238                                 tmp->min.value = max.value + 1;
 239                                 return;
 240                         }
 241                         /* Completely overlaps with the next one. */
 242                         if (sval_cmp(max, tmp->max) >= 0) {
 243                                 DELETE_CURRENT_PTR(tmp);
 244                                 /* there could be more ranges to delete */
 245                                 continue;
 246                         }
 247                 }
 248                 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
 249                         /* join 2 ranges into a big range */
 250                         new = alloc_range_sval(min, tmp->max);
 251                         REPLACE_CURRENT_PTR(tmp, new);
 252                         return;
 253                 }
 254                 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
 255                         new = alloc_range_sval(min, max);
 256                         INSERT_CURRENT(new, tmp);
 257                         return;
 258                 }
 259                 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
 260                         if (sval_cmp(max, tmp->max) < 0)
 261                                 max = tmp->max;
 262                         else
 263                                 check_next = 1;
 264                         new = alloc_range_sval(min, max);
 265                         REPLACE_CURRENT_PTR(tmp, new);
 266                         if (!check_next)
 267                                 return;
 268                         continue;
 269                 }
 270                 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
 271                         return;
 272                 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
 273                         min = tmp->min;
 274                         new = alloc_range_sval(min, max);
 275                         REPLACE_CURRENT_PTR(tmp, new);
 276                         check_next = 1;
 277                         continue;
 278                 }
 279                 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
 280                         /* join 2 ranges into a big range */
 281                         new = alloc_range_sval(tmp->min, max);
 282                         REPLACE_CURRENT_PTR(tmp, new);
 283                         check_next = 1;
 284                         continue;
 285                 }
 286                 /* the new range is entirely above the existing ranges */
 287         } END_FOR_EACH_PTR(tmp);
 288         if (check_next)
 289                 return;
 290         new = alloc_range_sval(min, max);
 291         add_ptr_list(list, new);
 292 }
 293
 294 struct range_list_sval *clone_range_list_sval(struct range_list_sval *list)
 295 {
 296         struct data_range_sval *tmp;
 297         struct range_list_sval *ret = NULL;
 298
 299         FOR_EACH_PTR(list, tmp) {
 300                 add_ptr_list(&ret, tmp);
 301         } END_FOR_EACH_PTR(tmp);
 302         return ret;
 303 }
 304
 305 struct range_list_sval *clone_permanent_sval(struct range_list_sval *list)
 306 {
 307         struct data_range_sval *tmp;
 308         struct data_range_sval *new;
 309         struct range_list_sval *ret = NULL;
 310
 311         FOR_EACH_PTR(list, tmp) {
 312                 new = alloc_range_perm_sval(tmp->min, tmp->max);
 313                 add_ptr_list(&ret, new);
 314         } END_FOR_EACH_PTR(tmp);
 315         return ret;
 316 }
 317
 318 struct range_list_sval *range_list_union_sval(struct range_list_sval *one, struct range_list_sval *two)
 319 {
 320         struct data_range_sval *tmp;
 321         struct range_list_sval *ret = NULL;
 322
 323         FOR_EACH_PTR(one, tmp) {
 324                 add_range_sval(&ret, tmp->min, tmp->max);
 325         } END_FOR_EACH_PTR(tmp);
 326         FOR_EACH_PTR(two, tmp) {
 327                 add_range_sval(&ret, tmp->min, tmp->max);
 328         } END_FOR_EACH_PTR(tmp);
 329         return ret;
 330 }
 331
 332 struct range_list_sval *remove_range_sval(struct range_list_sval *list, sval_t min, sval_t max)
 333 {
 334         struct data_range_sval *tmp;
 335         struct range_list_sval *ret = NULL;
 336
 337         FOR_EACH_PTR(list, tmp) {
 338                 if (sval_cmp(tmp->max, min) < 0) {
 339                         add_range_sval(&ret, tmp->min, tmp->max);
 340                         continue;
 341                 }
 342                 if (sval_cmp(tmp->min, max) > 0) {
 343                         add_range_sval(&ret, tmp->min, tmp->max);
 344                         continue;
 345                 }
 346                 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
 347                         continue;
 348                 if (sval_cmp(tmp->min, min) >= 0) {
 349                         max.value++;
 350                         add_range_sval(&ret, max, tmp->max);
 351                 } else if (sval_cmp(tmp->max, max) <= 0) {
 352                         min.value--;
 353                         add_range_sval(&ret, tmp->min, min);
 354                 } else {
 355                         min.value--;
 356                         max.value++;
 357                         add_range_sval(&ret, tmp->min, min);
 358                         add_range_sval(&ret, max, tmp->max);
 359                 }
 360         } END_FOR_EACH_PTR(tmp);
 361         return ret;
 362 }
 363
 364 int estate_get_single_value_sval(struct smatch_state *state, sval_t *sval)
 365 {
 366         sval_t min, max;
 367
 368         min = rl_min_sval(estate_ranges_sval(state));
 369         max = rl_max_sval(estate_ranges_sval(state));
 370         if (sval_cmp(min, max) != 0)
 371                 return 0;
 372         *sval = min;
 373         return 1;
 374 }
 375
 376 int ranges_equiv_sval(struct data_range_sval *one, struct data_range_sval *two)
 377 {
 378         if (!one && !two)
 379                 return 1;
 380         if (!one || !two)
 381                 return 0;
 382         if (sval_cmp(one->min, two->min) != 0)
 383                 return 0;
 384         if (sval_cmp(one->max, two->max) != 0)
 385                 return 0;
 386         return 1;
 387 }
 388
 389 int range_lists_equiv_sval(struct range_list_sval *one, struct range_list_sval *two)
 390 {
 391         struct data_range_sval *one_range;
 392         struct data_range_sval *two_range;
 393
 394         PREPARE_PTR_LIST(one, one_range);
 395         PREPARE_PTR_LIST(two, two_range);
 396         for (;;) {
 397                 if (!one_range && !two_range)
 398                         return 1;
 399                 if (!ranges_equiv_sval(one_range, two_range))
 400                         return 0;
 401                 NEXT_PTR_LIST(one_range);
 402                 NEXT_PTR_LIST(two_range);
 403         }
 404         FINISH_PTR_LIST(two_range);
 405         FINISH_PTR_LIST(one_range);
 406
 407         return 1;
 408 }
 409
 410 int true_comparison_range_sval(struct data_range_sval *left, int comparison, struct data_range_sval *right)
 411 {
 412         switch (comparison) {
 413         case '<':
 414         case SPECIAL_UNSIGNED_LT:
 415                 if (sval_cmp(left->min, right->max) < 0)
 416                         return 1;
 417                 return 0;
 418         case SPECIAL_UNSIGNED_LTE:
 419         case SPECIAL_LTE:
 420                 if (sval_cmp(left->min, right->max) <= 0)
 421                         return 1;
 422                 return 0;
 423         case SPECIAL_EQUAL:
 424                 if (sval_cmp(left->max, right->min) < 0)
 425                         return 0;
 426                 if (sval_cmp(left->min, right->max) > 0)
 427                         return 0;
 428                 return 1;
 429         case SPECIAL_UNSIGNED_GTE:
 430         case SPECIAL_GTE:
 431                 if (sval_cmp(left->max, right->min) >= 0)
 432                         return 1;
 433                 return 0;
 434         case '>':
 435         case SPECIAL_UNSIGNED_GT:
 436                 if (sval_cmp(left->max, right->min) > 0)
 437                         return 1;
 438                 return 0;
 439         case SPECIAL_NOTEQUAL:
 440                 if (sval_cmp(left->min, left->max) != 0)
 441                         return 1;
 442                 if (sval_cmp(right->min, right->max) != 0)
 443                         return 1;
 444                 if (sval_cmp(left->min, right->min) != 0)
 445                         return 1;
 446                 return 0;
 447         default:
 448                 sm_msg("unhandled comparison %d\n", comparison);
 449                 return 0;
 450         }
 451         return 0;
 452 }
 453
 454 int true_comparison_range_lr_sval(int comparison, struct data_range_sval *var, struct data_range_sval *val, int left)
 455 {
 456         if (left)
 457                 return true_comparison_range_sval(var, comparison, val);
 458         else
 459                 return true_comparison_range_sval(val, comparison, var);
 460 }
 461
 462 static int false_comparison_range_sval(struct data_range_sval *left, int comparison, struct data_range_sval *right)
 463 {
 464         switch (comparison) {
 465         case '<':
 466         case SPECIAL_UNSIGNED_LT:
 467                 if (sval_cmp(left->max, right->min) >= 0)
 468                         return 1;
 469                 return 0;
 470         case SPECIAL_UNSIGNED_LTE:
 471         case SPECIAL_LTE:
 472                 if (sval_cmp(left->max, right->min) > 0)
 473                         return 1;
 474                 return 0;
 475         case SPECIAL_EQUAL:
 476                 if (sval_cmp(left->min, left->max) != 0)
 477                         return 1;
 478                 if (sval_cmp(right->min, right->max) != 0)
 479                         return 1;
 480                 if (sval_cmp(left->min, right->min) != 0)
 481                         return 1;
 482                 return 0;
 483         case SPECIAL_UNSIGNED_GTE:
 484         case SPECIAL_GTE:
 485                 if (sval_cmp(left->min, right->max) < 0)
 486                         return 1;
 487                 return 0;
 488         case '>':
 489         case SPECIAL_UNSIGNED_GT:
 490                 if (sval_cmp(left->min, right->max) <= 0)
 491                         return 1;
 492                 return 0;
 493         case SPECIAL_NOTEQUAL:
 494                 if (sval_cmp(left->max, right->min) < 0)
 495                         return 0;
 496                 if (sval_cmp(left->min, right->max) > 0)
 497                         return 0;
 498                 return 1;
 499         default:
 500                 sm_msg("unhandled comparison %d\n", comparison);
 501                 return 0;
 502         }
 503         return 0;
 504 }
 505
 506 int false_comparison_range_lr_sval(int comparison, struct data_range_sval *var, struct data_range_sval *val, int left)
 507 {
 508         if (left)
 509                 return false_comparison_range_sval(var, comparison, val);
 510         else
 511                 return false_comparison_range_sval(val, comparison, var);
 512 }
 513
 514 int possibly_true(struct expression *left, int comparison, struct expression *right)
 515 {
 516         struct range_list_sval *rl_left, *rl_right;
 517         struct data_range_sval *tmp_left, *tmp_right;
 518
 519         if (!get_implied_range_list_sval(left, &rl_left))
 520                 return 1;
 521         if (!get_implied_range_list_sval(right, &rl_right))
 522                 return 1;
 523
 524         FOR_EACH_PTR(rl_left, tmp_left) {
 525                 FOR_EACH_PTR(rl_right, tmp_right) {
 526                         if (true_comparison_range_sval(tmp_left, comparison, tmp_right))
 527                                 return 1;
 528                 } END_FOR_EACH_PTR(tmp_right);
 529         } END_FOR_EACH_PTR(tmp_left);
 530         return 0;
 531 }
 532
 533 int possibly_false(struct expression *left, int comparison, struct expression *right)
 534 {
 535         struct range_list_sval *rl_left, *rl_right;
 536         struct data_range_sval *tmp_left, *tmp_right;
 537
 538         if (!get_implied_range_list_sval(left, &rl_left))
 539                 return 1;
 540         if (!get_implied_range_list_sval(right, &rl_right))
 541                 return 1;
 542
 543         FOR_EACH_PTR(rl_left, tmp_left) {
 544                 FOR_EACH_PTR(rl_right, tmp_right) {
 545                         if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
 546                                 return 1;
 547                 } END_FOR_EACH_PTR(tmp_right);
 548         } END_FOR_EACH_PTR(tmp_left);
 549         return 0;
 550 }
 551
 552 int possibly_true_range_lists_sval(struct range_list_sval *left_ranges, int comparison, struct range_list_sval *right_ranges)
 553 {
 554         struct data_range_sval *left_tmp, *right_tmp;
 555
 556         if (!left_ranges || !right_ranges)
 557                 return 1;
 558
 559         FOR_EACH_PTR(left_ranges, left_tmp) {
 560                 FOR_EACH_PTR(right_ranges, right_tmp) {
 561                         if (true_comparison_range_sval(left_tmp, comparison, right_tmp))
 562                                 return 1;
 563                 } END_FOR_EACH_PTR(right_tmp);
 564         } END_FOR_EACH_PTR(left_tmp);
 565         return 0;
 566 }
 567
 568 int possibly_false_range_lists_sval(struct range_list_sval *left_ranges, int comparison, struct range_list_sval *right_ranges)
 569 {
 570         struct data_range_sval *left_tmp, *right_tmp;
 571
 572         if (!left_ranges || !right_ranges)
 573                 return 1;
 574
 575         FOR_EACH_PTR(left_ranges, left_tmp) {
 576                 FOR_EACH_PTR(right_ranges, right_tmp) {
 577                         if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
 578                                 return 1;
 579                 } END_FOR_EACH_PTR(right_tmp);
 580         } END_FOR_EACH_PTR(left_tmp);
 581         return 0;
 582 }
 583
 584 /* FIXME: the _rl here stands for right left so really it should be _lr */
 585 int possibly_true_range_lists_rl_sval(int comparison, struct range_list_sval *a, struct range_list_sval *b, int left)
 586 {
 587         if (left)
 588                 return possibly_true_range_lists_sval(a, comparison, b);
 589         else
 590                 return possibly_true_range_lists_sval(b, comparison, a);
 591 }
 592
 593 int possibly_false_range_lists_rl_sval(int comparison, struct range_list_sval *a, struct range_list_sval *b, int left)
 594 {
 595         if (left)
 596                 return possibly_false_range_lists_sval(a, comparison, b);
 597         else
 598                 return possibly_false_range_lists_sval(b, comparison, a);
 599 }
 600
 601 void tack_on_sval(struct range_list_sval **list, struct data_range_sval *drange)
 602 {
 603         add_ptr_list(list, drange);
 604 }
 605
 606 void push_range_list_sval(struct range_list_stack_sval **rl_stack, struct range_list_sval *rl)
 607 {
 608         add_ptr_list(rl_stack, rl);
 609 }
 610
 611 struct range_list_sval *pop_range_list_sval(struct range_list_stack_sval **rl_stack)
 612 {
 613         struct range_list_sval *rl;
 614
 615         rl = last_ptr_list((struct ptr_list *)*rl_stack);
 616         delete_ptr_list_last((struct ptr_list **)rl_stack);
 617         return rl;
 618 }
 619
 620 struct range_list_sval *top_range_list_sval(struct range_list_stack_sval *rl_stack)
 621 {
 622         struct range_list_sval *rl;
 623
 624         rl = last_ptr_list((struct ptr_list *)rl_stack);
 625         return rl;
 626 }
 627
 628 void filter_top_range_list_sval(struct range_list_stack_sval **rl_stack, sval_t sval)
 629 {
 630         struct range_list_sval *rl;
 631
 632         rl = pop_range_list_sval(rl_stack);
 633         rl = remove_range_sval(rl, sval, sval);
 634         push_range_list_sval(rl_stack, rl);
 635 }
 636
 637 struct range_list_sval *cast_rl(struct range_list_sval *rl, struct symbol *type)
 638 {
 639         struct data_range_sval *tmp;
 640         struct data_range_sval *new;
 641         struct range_list_sval *ret = NULL;
 642         int set_min, set_max;
 643
 644         if (!rl)
 645                 return NULL;
 646
 647         if (!type)
 648                 return clone_range_list_sval(rl);
 649
 650         if (sval_cmp(rl_min_sval(rl), rl_max_sval(rl)) == 0) {
 651                 sval_t sval = sval_cast(rl_min_sval(rl), type);
 652                 return alloc_range_list_sval(sval, sval);
 653         }
 654
 655         set_max = 0;
 656         if (type_unsigned(type) && sval_cmp_val(rl_min_sval(rl), 0) < 0)
 657                 set_max = 1;
 658
 659         set_min = 0;
 660         if (type_signed(type) && sval_cmp(rl_max_sval(rl), sval_type_max(type)) > 0)
 661                 set_min = 1;
 662
 663         FOR_EACH_PTR(rl, tmp) {
 664                 if (sval_cmp_t(type, tmp->max, sval_type_min(type)) < 0)
 665                         continue;
 666                 if (sval_cmp_t(type, tmp->min, sval_type_max(type)) > 0)
 667                         continue;
 668                 new = alloc_range_sval(sval_cast(tmp->min, type), sval_cast(tmp->max, type));
 669                 add_ptr_list(&ret, new);
 670         } END_FOR_EACH_PTR(tmp);
 671
 672         if (!ret)
 673                 return whole_range_list_sval(type);
 674
 675         if (set_min) {
 676                 tmp = first_ptr_list((struct ptr_list *)ret);
 677                 tmp->min = sval_type_min(type);
 678         }
 679         if (set_max) {
 680                 tmp = last_ptr_list((struct ptr_list *)ret);
 681                 tmp->min = sval_type_max(type);
 682         }
 683
 684         return ret;
 685 }
 686
 687 void free_range_list_sval(struct range_list_sval **rlist)
 688 {
 689         __free_ptr_list((struct ptr_list **)rlist);
 690 }
 691
 692 static void free_single_dinfo(struct data_info *dinfo)
 693 {
 694         if (dinfo->type == DATA_RANGE)
 695                 free_range_list_sval(&dinfo->value_ranges);
 696 }
 697
 698 static void free_dinfos(struct allocation_blob *blob)
 699 {
 700         unsigned int size = sizeof(struct data_info);
 701         unsigned int offset = 0;
 702
 703         while (offset < blob->offset) {
 704                 free_single_dinfo((struct data_info *)(blob->data + offset));
 705                 offset += size;
 706         }
 707 }
 708
 709 void free_data_info_allocs(void)
 710 {
 711         struct allocator_struct *desc = &data_info_allocator;
 712         struct allocation_blob *blob = desc->blobs;
 713
 714         desc->blobs = NULL;
 715         desc->allocations = 0;
 716         desc->total_bytes = 0;
 717         desc->useful_bytes = 0;
 718         desc->freelist = NULL;
 719         while (blob) {
 720                 struct allocation_blob *next = blob->next;
 721                 free_dinfos(blob);
 722                 blob_free(blob, desc->chunking);
 723                 blob = next;
 724         }
 725         clear_data_range_sval_alloc();
 726 }
 727