smatch_slist.c

   1 /*
   2  * sparse/smatch_slist.c
   3  *
   4  * Copyright (C) 2008,2009 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include <stdlib.h>
  11 #include <stdio.h>
  12 #include "smatch.h"
  13 #include "smatch_slist.h"
  14
  15 #undef CHECKORDER
  16
  17 ALLOCATOR(smatch_state, "smatch state");
  18 ALLOCATOR(sm_state, "sm state");
  19 ALLOCATOR(named_slist, "named slist");
  20 __DO_ALLOCATOR(char, 0, 1, "state names", sname);
  21
  22 void __print_slist(struct state_list *slist)
  23 {
  24         struct sm_state *state;
  25         struct sm_state *poss;
  26         int i;
  27
  28         printf("dumping slist at %d\n", get_lineno());
  29         FOR_EACH_PTR(slist, state) {
  30                 printf("%d '%s'=%s (", state->owner, state->name,
  31                         show_state(state->state));
  32                 i = 0;
  33                 FOR_EACH_PTR(state->possible, poss) {
  34                         if (i++)
  35                                 printf(", ");
  36                         printf("%s", show_state(poss->state));
  37                 } END_FOR_EACH_PTR(poss);
  38                 printf(")\n");
  39         } END_FOR_EACH_PTR(state);
  40         printf("---\n");
  41 }
  42
  43
  44 /* NULL states go at the end to simplify merge_slist */
  45 int cmp_tracker(const struct sm_state *a, const struct sm_state *b)
  46 {
  47         int ret;
  48
  49         if (a == b)
  50                 return 0;
  51         if (!b)
  52                 return -1;
  53         if (!a)
  54                 return 1;
  55
  56         if (a->owner > b->owner)
  57                 return -1;
  58         if (a->owner < b->owner)
  59                 return 1;
  60
  61         ret = strcmp(a->name, b->name);
  62         if (ret)
  63                 return ret;
  64
  65         if (!b->sym && a->sym)
  66                 return -1;
  67         if (!a->sym && b->sym)
  68                 return 1;
  69         if (a->sym > b->sym)
  70                 return -1;
  71         if (a->sym < b->sym)
  72                 return 1;
  73
  74         return 0;
  75 }
  76
  77 static int cmp_sm_states(const struct sm_state *a, const struct sm_state *b)
  78 {
  79         int ret;
  80
  81         ret = cmp_tracker(a, b);
  82         if (ret)
  83                 return ret;
  84
  85         /* todo:  add hook for smatch_extra.c */
  86         if (a->state > b->state)
  87                 return -1;
  88         if (a->state < b->state)
  89                 return 1;
  90         return 0;
  91 }
  92
  93 static struct sm_state *alloc_state_no_name(const char *name, int owner,
  94                                      struct symbol *sym,
  95                                      struct smatch_state *state)
  96 {
  97         struct sm_state *tmp;
  98
  99         tmp = alloc_state(NULL, owner, sym, state);
 100         tmp->name = name;
 101         return tmp;
 102 }
 103
 104 void add_sm_state_slist(struct state_list **slist, struct sm_state *new)
 105 {
 106         struct sm_state *tmp;
 107
 108         FOR_EACH_PTR(*slist, tmp) {
 109                 if (cmp_sm_states(tmp, new) < 0)
 110                         continue;
 111                 else if (cmp_sm_states(tmp, new) == 0) {
 112                         return;
 113                 } else {
 114                         INSERT_CURRENT(new, tmp);
 115                         return;
 116                 }
 117         } END_FOR_EACH_PTR(tmp);
 118         add_ptr_list(slist, new);
 119 }
 120
 121 static void add_possible(struct sm_state *sm, struct sm_state *new)
 122 {
 123         struct sm_state *tmp;
 124         struct sm_state *tmp2;
 125
 126         if (!new) {
 127                 struct smatch_state *s;
 128
 129                 s = merge_states(sm->name, sm->owner, sm->sym, sm->state, NULL);
 130                 tmp = alloc_state_no_name(sm->name, sm->owner, sm->sym, s);
 131                 add_sm_state_slist(&sm->possible, tmp);
 132                 return;
 133         }
 134
 135         FOR_EACH_PTR(new->possible, tmp) {
 136                 tmp2 = alloc_state_no_name(tmp->name, tmp->owner, tmp->sym,
 137                                            tmp->state);
 138                 add_sm_state_slist(&sm->possible, tmp2);
 139         } END_FOR_EACH_PTR(tmp);
 140 }
 141
 142 char *alloc_sname(const char *str)
 143 {
 144         char *tmp;
 145
 146         if (!str)
 147                 return NULL;
 148         tmp = __alloc_sname(strlen(str) + 1);
 149         strcpy(tmp, str);
 150         return tmp;
 151 }
 152
 153 struct sm_state *alloc_state(const char *name, int owner,
 154                              struct symbol *sym, struct smatch_state *state)
 155 {
 156         struct sm_state *sm_state = __alloc_sm_state(0);
 157
 158         sm_state->name = alloc_sname(name);
 159         sm_state->owner = owner;
 160         sm_state->sym = sym;
 161         sm_state->state = state;
 162         sm_state->line = get_lineno();
 163         sm_state->merged = 0;
 164         sm_state->my_pools = NULL;
 165         sm_state->pre_merge = NULL;
 166         sm_state->possible = NULL;
 167         add_ptr_list(&sm_state->possible, sm_state);
 168         return sm_state;
 169 }
 170
 171 static void free_sm_state(struct sm_state *sm)
 172 {
 173         free_slist(&sm->possible);
 174         free_slist(&sm->pre_merge);
 175         free_stack(&sm->my_pools);
 176         /*
 177          * fixme.  Free the actual state.
 178          * Right now we leave it until the end of the function
 179          * because we don't want to double free it.
 180          * Use the freelist to not double free things
 181          */
 182 }
 183
 184 static void free_all_sm_states(struct allocation_blob *blob)
 185 {
 186         unsigned int size = sizeof(struct sm_state);
 187         unsigned int offset = 0;
 188
 189         while (offset < blob->offset) {
 190                 free_sm_state((struct sm_state *)(blob->data + offset));
 191                 offset += size;
 192         }
 193 }
 194
 195 /* At the end of every function we free all the sm_states */
 196 void free_every_single_sm_state(void)
 197 {
 198         struct allocator_struct *desc = &sm_state_allocator;
 199         struct allocation_blob *blob = desc->blobs;
 200
 201         desc->blobs = NULL;
 202         desc->allocations = 0;
 203         desc->total_bytes = 0;
 204         desc->useful_bytes = 0;
 205         desc->freelist = NULL;
 206         while (blob) {
 207                 struct allocation_blob *next = blob->next;
 208                 free_all_sm_states(blob);
 209                 blob_free(blob, desc->chunking);
 210                 blob = next;
 211         }
 212         clear_sname_alloc();
 213 }
 214
 215 struct sm_state *clone_state(struct sm_state *s)
 216 {
 217         struct sm_state *ret;
 218
 219         ret = alloc_state_no_name(s->name, s->owner, s->sym, s->state);
 220         ret->line = s->line;
 221         ret->merged = s->merged;
 222         ret->my_pools = clone_stack(s->my_pools);
 223         ret->possible = clone_slist(s->possible);
 224         ret->pre_merge = clone_slist(s->pre_merge);
 225         return ret;
 226 }
 227
 228 int is_merged(struct sm_state *sm)
 229 {
 230         return sm->merged;
 231 }
 232
 233 int slist_has_state(struct state_list *slist, struct smatch_state *state)
 234 {
 235         struct sm_state *tmp;
 236
 237         FOR_EACH_PTR(slist, tmp) {
 238                 if (tmp->state == state)
 239                         return 1;
 240         } END_FOR_EACH_PTR(tmp);
 241         return 0;
 242 }
 243
 244 static void check_order(struct state_list *slist)
 245 {
 246 #ifdef CHECKORDER
 247         struct sm_state *state;
 248         struct sm_state *last = NULL;
 249         int printed = 0;
 250
 251         FOR_EACH_PTR(slist, state) {
 252                 if (last && cmp_tracker(state, last) <= 0) {
 253                         printf("Error.  Unsorted slist %d vs %d, %p vs %p, "
 254                                "%s vs %s\n", last->owner, state->owner,
 255                                last->sym, state->sym, last->name, state->name);
 256                         printed = 1;
 257                 }
 258                 last = state;
 259         } END_FOR_EACH_PTR(state);
 260
 261         if (printed)
 262                 printf("======\n");
 263 #endif
 264 }
 265
 266 struct state_list *clone_slist(struct state_list *from_slist)
 267 {
 268         struct sm_state *state;
 269         struct state_list *to_slist = NULL;
 270
 271         FOR_EACH_PTR(from_slist, state) {
 272                 add_ptr_list(&to_slist, state);
 273         } END_FOR_EACH_PTR(state);
 274         check_order(to_slist);
 275         return to_slist;
 276 }
 277
 278 struct state_list *clone_slist_and_states(struct state_list *from_slist)
 279 {
 280         struct sm_state *state;
 281         struct sm_state *tmp;
 282         struct state_list *to_slist = NULL;
 283
 284         FOR_EACH_PTR(from_slist, state) {
 285                 tmp = clone_state(state);
 286                 add_ptr_list(&to_slist, tmp);
 287         } END_FOR_EACH_PTR(state);
 288         check_order(to_slist);
 289         return to_slist;
 290 }
 291
 292 struct state_list_stack *clone_stack(struct state_list_stack *from_stack)
 293 {
 294         struct state_list *slist;
 295         struct state_list_stack *to_stack = NULL;
 296
 297         FOR_EACH_PTR(from_stack, slist) {
 298                 push_slist(&to_stack, slist);
 299         } END_FOR_EACH_PTR(slist);
 300         return to_stack;
 301 }
 302
 303 struct smatch_state *merge_states(const char *name, int owner,
 304                                   struct symbol *sym,
 305                                   struct smatch_state *state1,
 306                                   struct smatch_state *state2)
 307 {
 308         struct smatch_state *ret;
 309
 310         if (state1 == state2)
 311                 ret = state1;
 312         else if (__has_merge_function(owner))
 313                 ret = __client_merge_function(owner, name, sym, state1, state2);
 314         else if (!state1 || !state2)
 315                 ret = &undefined;
 316         else
 317                 ret = &merged;
 318         return ret;
 319 }
 320
 321 /*
 322  * add_pool() adds a slist to ->pools. If the slist has already been
 323  * added earlier then it doesn't get added a second time.
 324  */
 325 void add_pool(struct state_list_stack **pools, struct state_list *new)
 326 {
 327         struct state_list *tmp;
 328
 329         FOR_EACH_PTR(*pools, tmp) {
 330                 if (tmp < new)
 331                         continue;
 332                 else if (tmp == new) {
 333                         return;
 334                 } else {
 335                         INSERT_CURRENT(new, tmp);
 336                         return;
 337                 }
 338         } END_FOR_EACH_PTR(tmp);
 339         add_ptr_list(pools, new);
 340 }
 341
 342 void merge_pools(struct state_list_stack **to, struct state_list_stack *from)
 343 {
 344         struct state_list *tmp;
 345
 346         FOR_EACH_PTR(from, tmp) {
 347                 add_pool(to, tmp);
 348         } END_FOR_EACH_PTR(tmp);
 349 }
 350
 351 struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two)
 352 {
 353         struct smatch_state *s;
 354         struct sm_state *result;
 355
 356         if (one == two)
 357                 return one;
 358         s = merge_states(one->name, one->owner, one->sym, one->state,
 359                         (two?two->state:NULL));
 360         result = alloc_state_no_name(one->name, one->owner, one->sym, s);
 361         if (two && one->line == two->line)
 362                 result->line = one->line;
 363         result->merged = 1;
 364         add_ptr_list(&result->pre_merge, one);
 365         add_ptr_list(&result->pre_merge, two);
 366         add_possible(result, one);
 367         add_possible(result, two);
 368
 369         if (debug_states) {
 370                 struct sm_state *tmp;
 371                 int i = 0;
 372
 373                 printf("%d merge name='%s' owner=%d: %s + %s => %s (",
 374                         get_lineno(), one->name, one->owner,
 375                         show_state(one->state), show_state(two?two->state:NULL),
 376                         show_state(s));
 377
 378                 FOR_EACH_PTR(result->possible, tmp) {
 379                         if (i++) {
 380                                 printf(", ");
 381                         }
 382                         printf("%s", show_state(tmp->state));
 383                 } END_FOR_EACH_PTR(tmp);
 384                 printf(")\n");
 385         }
 386
 387         return result;
 388 }
 389
 390 struct sm_state *get_sm_state_slist(struct state_list *slist, const char *name,
 391                                 int owner, struct symbol *sym)
 392 {
 393         struct sm_state *state;
 394
 395         if (!name)
 396                 return NULL;
 397
 398         FOR_EACH_PTR(slist, state) {
 399                 if (state->owner == owner && state->sym == sym
 400                     && !strcmp(state->name, name))
 401                         return state;
 402         } END_FOR_EACH_PTR(state);
 403         return NULL;
 404 }
 405
 406 struct smatch_state *get_state_slist(struct state_list *slist,
 407                                 const char *name, int owner,
 408                                 struct symbol *sym)
 409 {
 410         struct sm_state *state;
 411
 412         state = get_sm_state_slist(slist, name, owner, sym);
 413         if (state)
 414                 return state->state;
 415         return NULL;
 416 }
 417
 418 void overwrite_sm_state(struct state_list **slist, struct sm_state *new)
 419 {
 420         struct sm_state *tmp;
 421
 422         FOR_EACH_PTR(*slist, tmp) {
 423                 if (cmp_tracker(tmp, new) < 0)
 424                         continue;
 425                 else if (cmp_tracker(tmp, new) == 0) {
 426                         REPLACE_CURRENT_PTR(tmp, new);
 427                         return;
 428                 } else {
 429                         INSERT_CURRENT(new, tmp);
 430                         return;
 431                 }
 432         } END_FOR_EACH_PTR(tmp);
 433         add_ptr_list(slist, new);
 434 }
 435
 436 void overwrite_sm_state_stack(struct state_list_stack **stack,
 437                         struct sm_state *state)
 438 {
 439         struct state_list *slist;
 440
 441         slist = pop_slist(stack);
 442         overwrite_sm_state(&slist, state);
 443         push_slist(stack, slist);
 444 }
 445
 446 void set_state_slist(struct state_list **slist, const char *name, int owner,
 447                      struct symbol *sym, struct smatch_state *state)
 448 {
 449         struct sm_state *tmp;
 450         struct sm_state *new = alloc_state(name, owner, sym, state);
 451
 452         FOR_EACH_PTR(*slist, tmp) {
 453                 if (cmp_tracker(tmp, new) < 0)
 454                         continue;
 455                 else if (cmp_tracker(tmp, new) == 0) {
 456                         REPLACE_CURRENT_PTR(tmp, new);
 457                         return;
 458                 } else {
 459                         INSERT_CURRENT(new, tmp);
 460                         return;
 461                 }
 462         } END_FOR_EACH_PTR(tmp);
 463         add_ptr_list(slist, new);
 464 }
 465
 466 void delete_state_slist(struct state_list **slist, const char *name, int owner,
 467                         struct symbol *sym)
 468 {
 469         struct sm_state *state;
 470
 471         FOR_EACH_PTR(*slist, state) {
 472                 if (state->owner == owner && state->sym == sym
 473                     && !strcmp(state->name, name)){
 474                         DELETE_CURRENT_PTR(state);
 475                         return;
 476                 }
 477         } END_FOR_EACH_PTR(state);
 478 }
 479
 480
 481 void push_slist(struct state_list_stack **list_stack, struct state_list *slist)
 482 {
 483         add_ptr_list(list_stack, slist);
 484 }
 485
 486 struct state_list *pop_slist(struct state_list_stack **list_stack)
 487 {
 488         struct state_list *slist;
 489
 490         slist = last_ptr_list((struct ptr_list *)*list_stack);
 491         delete_ptr_list_last((struct ptr_list **)list_stack);
 492         return slist;
 493 }
 494
 495 void free_slist(struct state_list **slist)
 496 {
 497         __free_ptr_list((struct ptr_list **)slist);
 498 }
 499
 500 void free_stack(struct state_list_stack **stack)
 501 {
 502         __free_ptr_list((struct ptr_list **)stack);
 503 }
 504
 505 void free_stack_and_slists(struct state_list_stack **slist_stack)
 506 {
 507         struct state_list *slist;
 508
 509         FOR_EACH_PTR(*slist_stack, slist) {
 510                 free_slist(&slist);
 511         } END_FOR_EACH_PTR(slist);
 512         free_stack(slist_stack);
 513 }
 514
 515 /*
 516  * set_state_stack() sets the state for the top slist on the stack.
 517  */
 518 void set_state_stack(struct state_list_stack **stack, const char *name,
 519                      int owner, struct symbol *sym, struct smatch_state *state)
 520 {
 521         struct state_list *slist;
 522
 523         slist = pop_slist(stack);
 524         set_state_slist(&slist, name, owner, sym, state);
 525         push_slist(stack, slist);
 526 }
 527
 528 /*
 529  * get_sm_state_stack() gets the state for the top slist on the stack.
 530  */
 531 struct sm_state *get_sm_state_stack(struct state_list_stack *stack,
 532                                     const char *name, int owner,
 533                                     struct symbol *sym)
 534 {
 535         struct state_list *slist;
 536         struct sm_state *ret;
 537
 538         slist = pop_slist(&stack);
 539         ret = get_sm_state_slist(slist, name, owner, sym);
 540         push_slist(&stack, slist);
 541         return ret;
 542 }
 543
 544
 545 struct smatch_state *get_state_stack(struct state_list_stack *stack,
 546                                      const char *name, int owner,
 547                                      struct symbol *sym)
 548 {
 549         struct sm_state *state;
 550
 551         state = get_sm_state_stack(stack, name, owner, sym);
 552         if (state)
 553                 return state->state;
 554         return NULL;
 555 }
 556
 557 static void match_states(struct state_list **one, struct state_list **two)
 558 {
 559         struct sm_state *one_state;
 560         struct sm_state *two_state;
 561         struct sm_state *tmp;
 562         struct smatch_state *tmp_state;
 563         struct state_list *add_to_one = NULL;
 564         struct state_list *add_to_two = NULL;
 565
 566         PREPARE_PTR_LIST(*one, one_state);
 567         PREPARE_PTR_LIST(*two, two_state);
 568         for (;;) {
 569                 if (!one_state && !two_state)
 570                         break;
 571                 if (cmp_tracker(one_state, two_state) < 0) {
 572                         tmp_state = __client_unmatched_state_function(one_state);
 573                         tmp = alloc_state_no_name(one_state->name,
 574                                                   one_state->owner,
 575                                                   one_state->sym, tmp_state);
 576                         add_ptr_list(&add_to_two, tmp);
 577                         NEXT_PTR_LIST(one_state);
 578                 } else if (cmp_tracker(one_state, two_state) == 0) {
 579                         NEXT_PTR_LIST(one_state);
 580                         NEXT_PTR_LIST(two_state);
 581                 } else {
 582                         tmp_state = __client_unmatched_state_function(two_state);
 583                         tmp = alloc_state_no_name(two_state->name,
 584                                                   two_state->owner,
 585                                                   two_state->sym, tmp_state);
 586                         add_ptr_list(&add_to_one, tmp);
 587                         NEXT_PTR_LIST(two_state);
 588                 }
 589         }
 590         FINISH_PTR_LIST(two_state);
 591         FINISH_PTR_LIST(one_state);
 592
 593         overwrite_slist(add_to_one, one);
 594         overwrite_slist(add_to_two, two);
 595 }
 596
 597 /*
 598  * merge_slist() is called whenever paths merge, such as after
 599  * an if statement.  It takes the two slists and creates one.
 600  */
 601 void merge_slist(struct state_list **to, struct state_list *slist)
 602 {
 603         struct sm_state *to_state, *state, *tmp;
 604         struct state_list *results = NULL;
 605         struct state_list *implied_to = NULL;
 606         struct state_list *implied_from = NULL;
 607
 608         check_order(*to);
 609         check_order(slist);
 610
 611         /* merging a null and nonnull path gives you only the nonnull path */
 612         if (!slist) {
 613                 return;
 614         }
 615         if (!*to) {
 616                 *to = clone_slist(slist);
 617                 return;
 618         }
 619
 620         implied_to = clone_slist(*to);
 621         implied_from = clone_slist(slist);
 622
 623         match_states(&implied_to, &implied_from);
 624
 625         PREPARE_PTR_LIST(implied_to, to_state);
 626         PREPARE_PTR_LIST(implied_from, state);
 627         for (;;) {
 628                 if (!to_state && !state)
 629                         break;
 630                 if (cmp_tracker(to_state, state) < 0) {
 631                         smatch_msg("error:  Internal smatch error.");
 632                         NEXT_PTR_LIST(to_state);
 633                 } else if (cmp_tracker(to_state, state) == 0) {
 634                         if (to_state != state) {
 635                                 add_pool(&to_state->my_pools, implied_to);
 636                                 add_pool(&state->my_pools, implied_from);
 637                         }
 638
 639                         tmp = merge_sm_states(to_state, state);
 640                         add_ptr_list(&results, tmp);
 641                         NEXT_PTR_LIST(to_state);
 642                         NEXT_PTR_LIST(state);
 643                 } else {
 644                         smatch_msg("error:  Internal smatch error.");
 645                         NEXT_PTR_LIST(state);
 646                 }
 647         }
 648         FINISH_PTR_LIST(state);
 649         FINISH_PTR_LIST(to_state);
 650
 651         free_slist(to);
 652         *to = results;
 653 }
 654
 655 /*
 656  * and_slist_stack() is basically the same as popping the top two slists,
 657  * overwriting the one with the other and pushing it back on the stack.
 658  * The difference is that it checks to see that a mutually exclusive
 659  * state isn't included in both stacks.  If smatch sees something like
 660  * "if (a && !a)" it prints a warning.
 661  */
 662 void and_slist_stack(struct state_list_stack **slist_stack)
 663 {
 664         struct sm_state *tmp;
 665         struct state_list *right_slist = pop_slist(slist_stack);
 666
 667         FOR_EACH_PTR(right_slist, tmp) {
 668                 overwrite_sm_state_stack(slist_stack, tmp);
 669         } END_FOR_EACH_PTR(tmp);
 670         free_slist(&right_slist);
 671 }
 672
 673 /*
 674  * or_slist_stack() is for if we have:  if (foo || bar) { foo->baz;
 675  * It pops the two slists from the top of the stack and merges them
 676  * together in a way that preserves the things they have in common
 677  * but creates a merged state for most of the rest.
 678  * You could have code that had:  if (foo || foo) { foo->baz;
 679  * It's this function which ensures smatch does the right thing.
 680  */
 681 void or_slist_stack(struct state_list_stack **pre_conds,
 682                     struct state_list *cur_slist,
 683                     struct state_list_stack **slist_stack)
 684 {
 685         struct state_list *new;
 686         struct state_list *old;
 687         struct state_list *res = NULL;
 688         struct state_list *tmp_slist;
 689
 690         new = pop_slist(slist_stack);
 691         old = pop_slist(slist_stack);
 692
 693         tmp_slist = pop_slist(pre_conds);
 694         res = clone_slist(tmp_slist);
 695         push_slist(pre_conds, tmp_slist);
 696         overwrite_slist(old, &res);
 697
 698         tmp_slist = clone_slist(cur_slist);
 699         overwrite_slist(new, &tmp_slist);
 700
 701         merge_slist(&res, tmp_slist);
 702
 703         push_slist(slist_stack, res);
 704         free_slist(&tmp_slist);
 705         free_slist(&new);
 706         free_slist(&old);
 707 }
 708
 709 /*
 710  * get_slist_from_named_stack() is only used for gotos.
 711  */
 712 struct state_list **get_slist_from_named_stack(struct named_stack *stack,
 713                                               const char *name)
 714 {
 715         struct named_slist *tmp;
 716
 717         FOR_EACH_PTR(stack, tmp) {
 718                 if (!strcmp(tmp->name, name))
 719                         return &tmp->slist;
 720         } END_FOR_EACH_PTR(tmp);
 721         return NULL;
 722 }
 723
 724 void overwrite_slist(struct state_list *from, struct state_list **to)
 725 {
 726         struct sm_state *tmp;
 727
 728         FOR_EACH_PTR(from, tmp) {
 729                 overwrite_sm_state(to, tmp);
 730         } END_FOR_EACH_PTR(tmp);
 731 }
 732
 733 unsigned int __get_allocations()
 734 {
 735         return sm_state_allocator.allocations;
 736 }