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