smatch_ranges.c

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