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 ranges_equiv_sval(struct data_range_sval *one, struct data_range_sval *two)
 365 {
 366         if (!one && !two)
 367                 return 1;
 368         if (!one || !two)
 369                 return 0;
 370         if (sval_cmp(one->min, two->min) != 0)
 371                 return 0;
 372         if (sval_cmp(one->max, two->max) != 0)
 373                 return 0;
 374         return 1;
 375 }
 376
 377 int range_lists_equiv_sval(struct range_list_sval *one, struct range_list_sval *two)
 378 {
 379         struct data_range_sval *one_range;
 380         struct data_range_sval *two_range;
 381
 382         PREPARE_PTR_LIST(one, one_range);
 383         PREPARE_PTR_LIST(two, two_range);
 384         for (;;) {
 385                 if (!one_range && !two_range)
 386                         return 1;
 387                 if (!ranges_equiv_sval(one_range, two_range))
 388                         return 0;
 389                 NEXT_PTR_LIST(one_range);
 390                 NEXT_PTR_LIST(two_range);
 391         }
 392         FINISH_PTR_LIST(two_range);
 393         FINISH_PTR_LIST(one_range);
 394
 395         return 1;
 396 }
 397
 398 int true_comparison_range_sval(struct data_range_sval *left, int comparison, struct data_range_sval *right)
 399 {
 400         switch (comparison) {
 401         case '<':
 402         case SPECIAL_UNSIGNED_LT:
 403                 if (sval_cmp(left->min, right->max) < 0)
 404                         return 1;
 405                 return 0;
 406         case SPECIAL_UNSIGNED_LTE:
 407         case SPECIAL_LTE:
 408                 if (sval_cmp(left->min, right->max) <= 0)
 409                         return 1;
 410                 return 0;
 411         case SPECIAL_EQUAL:
 412                 if (sval_cmp(left->max, right->min) < 0)
 413                         return 0;
 414                 if (sval_cmp(left->min, right->max) > 0)
 415                         return 0;
 416                 return 1;
 417         case SPECIAL_UNSIGNED_GTE:
 418         case SPECIAL_GTE:
 419                 if (sval_cmp(left->max, right->min) >= 0)
 420                         return 1;
 421                 return 0;
 422         case '>':
 423         case SPECIAL_UNSIGNED_GT:
 424                 if (sval_cmp(left->max, right->min) > 0)
 425                         return 1;
 426                 return 0;
 427         case SPECIAL_NOTEQUAL:
 428                 if (sval_cmp(left->min, left->max) != 0)
 429                         return 1;
 430                 if (sval_cmp(right->min, right->max) != 0)
 431                         return 1;
 432                 if (sval_cmp(left->min, right->min) != 0)
 433                         return 1;
 434                 return 0;
 435         default:
 436                 sm_msg("unhandled comparison %d\n", comparison);
 437                 return 0;
 438         }
 439         return 0;
 440 }
 441
 442 int true_comparison_range_lr_sval(int comparison, struct data_range_sval *var, struct data_range_sval *val, int left)
 443 {
 444         if (left)
 445                 return true_comparison_range_sval(var, comparison, val);
 446         else
 447                 return true_comparison_range_sval(val, comparison, var);
 448 }
 449
 450 static int false_comparison_range_sval(struct data_range_sval *left, int comparison, struct data_range_sval *right)
 451 {
 452         switch (comparison) {
 453         case '<':
 454         case SPECIAL_UNSIGNED_LT:
 455                 if (sval_cmp(left->max, right->min) >= 0)
 456                         return 1;
 457                 return 0;
 458         case SPECIAL_UNSIGNED_LTE:
 459         case SPECIAL_LTE:
 460                 if (sval_cmp(left->max, right->min) > 0)
 461                         return 1;
 462                 return 0;
 463         case SPECIAL_EQUAL:
 464                 if (sval_cmp(left->min, left->max) != 0)
 465                         return 1;
 466                 if (sval_cmp(right->min, right->max) != 0)
 467                         return 1;
 468                 if (sval_cmp(left->min, right->min) != 0)
 469                         return 1;
 470                 return 0;
 471         case SPECIAL_UNSIGNED_GTE:
 472         case SPECIAL_GTE:
 473                 if (sval_cmp(left->min, right->max) < 0)
 474                         return 1;
 475                 return 0;
 476         case '>':
 477         case SPECIAL_UNSIGNED_GT:
 478                 if (sval_cmp(left->min, right->max) <= 0)
 479                         return 1;
 480                 return 0;
 481         case SPECIAL_NOTEQUAL:
 482                 if (sval_cmp(left->max, right->min) < 0)
 483                         return 0;
 484                 if (sval_cmp(left->min, right->max) > 0)
 485                         return 0;
 486                 return 1;
 487         default:
 488                 sm_msg("unhandled comparison %d\n", comparison);
 489                 return 0;
 490         }
 491         return 0;
 492 }
 493
 494 int false_comparison_range_lr_sval(int comparison, struct data_range_sval *var, struct data_range_sval *val, int left)
 495 {
 496         if (left)
 497                 return false_comparison_range_sval(var, comparison, val);
 498         else
 499                 return false_comparison_range_sval(val, comparison, var);
 500 }
 501
 502 int possibly_true(struct expression *left, int comparison, struct expression *right)
 503 {
 504         struct range_list_sval *rl_left, *rl_right;
 505         struct data_range_sval *tmp_left, *tmp_right;
 506
 507         if (!get_implied_range_list_sval(left, &rl_left))
 508                 return 1;
 509         if (!get_implied_range_list_sval(right, &rl_right))
 510                 return 1;
 511
 512         FOR_EACH_PTR(rl_left, tmp_left) {
 513                 FOR_EACH_PTR(rl_right, tmp_right) {
 514                         if (true_comparison_range_sval(tmp_left, comparison, tmp_right))
 515                                 return 1;
 516                 } END_FOR_EACH_PTR(tmp_right);
 517         } END_FOR_EACH_PTR(tmp_left);
 518         return 0;
 519 }
 520
 521 int possibly_false(struct expression *left, int comparison, struct expression *right)
 522 {
 523         struct range_list_sval *rl_left, *rl_right;
 524         struct data_range_sval *tmp_left, *tmp_right;
 525
 526         if (!get_implied_range_list_sval(left, &rl_left))
 527                 return 1;
 528         if (!get_implied_range_list_sval(right, &rl_right))
 529                 return 1;
 530
 531         FOR_EACH_PTR(rl_left, tmp_left) {
 532                 FOR_EACH_PTR(rl_right, tmp_right) {
 533                         if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
 534                                 return 1;
 535                 } END_FOR_EACH_PTR(tmp_right);
 536         } END_FOR_EACH_PTR(tmp_left);
 537         return 0;
 538 }
 539
 540 int possibly_true_range_lists_sval(struct range_list_sval *left_ranges, int comparison, struct range_list_sval *right_ranges)
 541 {
 542         struct data_range_sval *left_tmp, *right_tmp;
 543
 544         if (!left_ranges || !right_ranges)
 545                 return 1;
 546
 547         FOR_EACH_PTR(left_ranges, left_tmp) {
 548                 FOR_EACH_PTR(right_ranges, right_tmp) {
 549                         if (true_comparison_range_sval(left_tmp, comparison, right_tmp))
 550                                 return 1;
 551                 } END_FOR_EACH_PTR(right_tmp);
 552         } END_FOR_EACH_PTR(left_tmp);
 553         return 0;
 554 }
 555
 556 int possibly_false_range_lists_sval(struct range_list_sval *left_ranges, int comparison, struct range_list_sval *right_ranges)
 557 {
 558         struct data_range_sval *left_tmp, *right_tmp;
 559
 560         if (!left_ranges || !right_ranges)
 561                 return 1;
 562
 563         FOR_EACH_PTR(left_ranges, left_tmp) {
 564                 FOR_EACH_PTR(right_ranges, right_tmp) {
 565                         if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
 566                                 return 1;
 567                 } END_FOR_EACH_PTR(right_tmp);
 568         } END_FOR_EACH_PTR(left_tmp);
 569         return 0;
 570 }
 571
 572 /* FIXME: the _rl here stands for right left so really it should be _lr */
 573 int possibly_true_range_lists_rl_sval(int comparison, struct range_list_sval *a, struct range_list_sval *b, int left)
 574 {
 575         if (left)
 576                 return possibly_true_range_lists_sval(a, comparison, b);
 577         else
 578                 return possibly_true_range_lists_sval(b, comparison, a);
 579 }
 580
 581 int possibly_false_range_lists_rl_sval(int comparison, struct range_list_sval *a, struct range_list_sval *b, int left)
 582 {
 583         if (left)
 584                 return possibly_false_range_lists_sval(a, comparison, b);
 585         else
 586                 return possibly_false_range_lists_sval(b, comparison, a);
 587 }
 588
 589 void tack_on_sval(struct range_list_sval **list, struct data_range_sval *drange)
 590 {
 591         add_ptr_list(list, drange);
 592 }
 593
 594 void push_range_list_sval(struct range_list_stack_sval **rl_stack, struct range_list_sval *rl)
 595 {
 596         add_ptr_list(rl_stack, rl);
 597 }
 598
 599 struct range_list_sval *pop_range_list_sval(struct range_list_stack_sval **rl_stack)
 600 {
 601         struct range_list_sval *rl;
 602
 603         rl = last_ptr_list((struct ptr_list *)*rl_stack);
 604         delete_ptr_list_last((struct ptr_list **)rl_stack);
 605         return rl;
 606 }
 607
 608 struct range_list_sval *top_range_list_sval(struct range_list_stack_sval *rl_stack)
 609 {
 610         struct range_list_sval *rl;
 611
 612         rl = last_ptr_list((struct ptr_list *)rl_stack);
 613         return rl;
 614 }
 615
 616 void filter_top_range_list_sval(struct range_list_stack_sval **rl_stack, sval_t sval)
 617 {
 618         struct range_list_sval *rl;
 619
 620         rl = pop_range_list_sval(rl_stack);
 621         rl = remove_range_sval(rl, sval, sval);
 622         push_range_list_sval(rl_stack, rl);
 623 }
 624
 625 struct range_list_sval *cast_rl(struct range_list_sval *rl, struct symbol *type)
 626 {
 627         struct data_range_sval *tmp;
 628         struct data_range_sval *new;
 629         struct range_list_sval *ret = NULL;
 630         int set_min, set_max;
 631
 632         if (!rl)
 633                 return NULL;
 634
 635         if (!type)
 636                 return clone_range_list_sval(rl);
 637
 638         if (sval_cmp(rl_min_sval(rl), rl_max_sval(rl)) == 0) {
 639                 sval_t sval = sval_cast(rl_min_sval(rl), type);
 640                 return alloc_range_list_sval(sval, sval);
 641         }
 642
 643         set_max = 0;
 644         if (type_unsigned(type) && sval_cmp_val(rl_min_sval(rl), 0) < 0)
 645                 set_max = 1;
 646
 647         set_min = 0;
 648         if (type_signed(type) && sval_cmp(rl_max_sval(rl), sval_type_max(type)) > 0)
 649                 set_min = 1;
 650
 651         FOR_EACH_PTR(rl, tmp) {
 652                 sval_t min, max;
 653
 654                 min = tmp->min;
 655                 max = tmp->max;
 656
 657                 if (sval_cmp_t(type, max, sval_type_min(type)) < 0)
 658                         continue;
 659                 if (sval_cmp_t(type, min, sval_type_max(type)) > 0)
 660                         continue;
 661                 if (sval_cmp_val(min, 0) < 0 && type_unsigned(type))
 662                         min.value = 0;
 663                 new = alloc_range_sval(sval_cast(min, type), sval_cast(max, type));
 664                 add_ptr_list(&ret, new);
 665         } END_FOR_EACH_PTR(tmp);
 666
 667         if (!ret)
 668                 return whole_range_list_sval(type);
 669
 670         if (set_min) {
 671                 tmp = first_ptr_list((struct ptr_list *)ret);
 672                 tmp->min = sval_type_min(type);
 673         }
 674         if (set_max) {
 675                 tmp = last_ptr_list((struct ptr_list *)ret);
 676                 tmp->max = sval_type_max(type);
 677         }
 678
 679         return ret;
 680 }
 681
 682 void free_range_list_sval(struct range_list_sval **rlist)
 683 {
 684         __free_ptr_list((struct ptr_list **)rlist);
 685 }
 686
 687 static void free_single_dinfo(struct data_info *dinfo)
 688 {
 689         if (dinfo->type == DATA_RANGE)
 690                 free_range_list_sval(&dinfo->value_ranges);
 691 }
 692
 693 static void free_dinfos(struct allocation_blob *blob)
 694 {
 695         unsigned int size = sizeof(struct data_info);
 696         unsigned int offset = 0;
 697
 698         while (offset < blob->offset) {
 699                 free_single_dinfo((struct data_info *)(blob->data + offset));
 700                 offset += size;
 701         }
 702 }
 703
 704 void free_data_info_allocs(void)
 705 {
 706         struct allocator_struct *desc = &data_info_allocator;
 707         struct allocation_blob *blob = desc->blobs;
 708
 709         desc->blobs = NULL;
 710         desc->allocations = 0;
 711         desc->total_bytes = 0;
 712         desc->useful_bytes = 0;
 713         desc->freelist = NULL;
 714         while (blob) {
 715                 struct allocation_blob *next = blob->next;
 716                 free_dinfos(blob);
 717                 blob_free(blob, desc->chunking);
 718                 blob = next;
 719         }
 720         clear_data_range_sval_alloc();
 721 }
 722