smatch_states.c

   1 /*
   2  * sparse/smatch_states.c
   3  *
   4  * Copyright (C) 2006 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 struct state_list *cur_slist; /* current states */
  16
  17 static struct state_list_stack *true_stack; /* states after a t/f branch */
  18 static struct state_list_stack *false_stack;
  19 static struct state_list_stack *pre_cond_stack; /* states before a t/f branch */
  20
  21 static struct state_list_stack *cond_true_stack; /* states affected by a branch */
  22 static struct state_list_stack *cond_false_stack;
  23
  24 static struct state_list_stack *break_stack;
  25 static struct state_list_stack *switch_stack;
  26 static struct state_list_stack *default_stack;
  27 static struct state_list_stack *continue_stack;
  28 static struct state_list_stack *false_only_stack;
  29
  30 struct slist_stack *goto_stack;
  31
  32 int debug_states;
  33
  34 void __print_slist(struct state_list *slist)
  35 {
  36         struct smatch_state *state;
  37
  38         printf("dumping slist at %d\n", get_lineno());
  39         FOR_EACH_PTR(slist, state) {
  40                 printf("%s=%d\n", state->name, state->state);
  41         } END_FOR_EACH_PTR(state);
  42         printf("---\n");
  43 }
  44
  45 void __print_cur_slist()
  46 {
  47         __print_slist(cur_slist);
  48 }
  49
  50 void set_state(const char *name, int owner, struct symbol *sym, int state)
  51 {
  52         if (!name)
  53                 return;
  54
  55         if (debug_states) {
  56                 int s;
  57
  58                 s = get_state(name, owner, sym);
  59                 if (s == NOTFOUND)
  60                         printf("%d new state. name='%s' owner=%d: %d\n",
  61                                get_lineno(), name, owner, state);
  62                 else
  63                         printf("%d state change name='%s' owner=%d: %d => %d\n",
  64                                get_lineno(), name, owner, s, state);
  65         }
  66         set_state_slist(&cur_slist, name, owner, sym, state);
  67
  68         if (cond_true_stack) {
  69                 set_state_stack(&cond_true_stack, name, owner, sym, state);
  70                 set_state_stack(&cond_false_stack, name, owner, sym, state);
  71         }
  72 }
  73
  74 int get_state(const char *name, int owner, struct symbol *sym)
  75 {
  76         return get_state_slist(cur_slist, name, owner, sym);
  77 }
  78
  79 void delete_state(const char *name, int owner, struct symbol *sym)
  80 {
  81         delete_state_slist(&cur_slist, name, owner, sym);
  82 }
  83
  84 struct state_list *get_current_states(int owner)
  85 {
  86         struct state_list *slist;
  87         struct smatch_state *tmp;
  88
  89         FOR_EACH_PTR(cur_slist, tmp) {
  90                 if (tmp->owner == owner) {
  91                         add_ptr_list(&slist, tmp);
  92                 }
  93         } END_FOR_EACH_PTR(tmp);
  94
  95         return slist;
  96 }
  97
  98 void set_true_false_states(const char *name, int owner, struct symbol *sym,
  99                            int true_state, int false_state)
 100 {
 101
 102         /* fixme.  save history */
 103
 104         SM_DEBUG("%d set_true_false %s.  Was %d.  Now T:%d F:%d\n",
 105                  get_lineno(), name, get_state(name, owner, sym), true_state,
 106                  false_state);
 107
 108         if (!cond_false_stack || !cond_true_stack) {
 109                 printf("Error:  missing true/false stacks\n");
 110                 return;
 111         }
 112
 113         set_state_slist(&cur_slist, name, owner, sym, true_state);
 114         set_state_stack(&cond_true_stack, name, owner, sym, true_state);
 115         set_state_stack(&cond_false_stack, name, owner, sym, false_state);
 116
 117 }
 118
 119 void set_null_path()
 120 {
 121         set_state("null_path", 0, NULL, 1);
 122 }
 123
 124 void nullify_path()
 125 {
 126         del_slist(&cur_slist);
 127         set_null_path();
 128 }
 129
 130 void __unnullify_path()
 131 {
 132         set_state("null_path", 0, NULL, 0);
 133 }
 134
 135 void clear_all_states()
 136 {
 137         struct named_slist *named_slist;
 138
 139         nullify_path();
 140         del_slist_stack(&true_stack);
 141         del_slist_stack(&false_stack);
 142         del_slist_stack(&false_only_stack);
 143         del_slist_stack(&pre_cond_stack);
 144         del_slist_stack(&cond_true_stack);
 145         del_slist_stack(&cond_false_stack);
 146         del_slist_stack(&break_stack);
 147         del_slist_stack(&switch_stack);
 148         del_slist_stack(&continue_stack);
 149
 150         FOR_EACH_PTR(goto_stack, named_slist) {
 151                 del_slist(&named_slist->slist);
 152         } END_FOR_EACH_PTR(named_slist);
 153         __free_ptr_list((struct ptr_list **)&goto_stack);
 154 }
 155
 156
 157 void __push_cond_stacks()
 158 {
 159         push_slist(&cond_true_stack, NULL);
 160         push_slist(&cond_false_stack, NULL);
 161 }
 162
 163 /*
 164  * This combines the pre cond states with either the true or false states.
 165  * For example:
 166  * a = kmalloc() ; if (a !! foo(a)
 167  * In the pre state a is possibly null.  In the true state it is non null.
 168  * In the false state it is null.  Combine the pre and the false to get
 169  * that when we call 'foo', 'a' is null.
 170  */
 171
 172 static void __use_cond_stack(struct state_list_stack **stack)
 173 {
 174         struct state_list *slist;
 175
 176         del_slist(&cur_slist);
 177
 178         cur_slist = pop_slist(&pre_cond_stack);
 179         push_slist(&pre_cond_stack, clone_slist(cur_slist));
 180
 181         slist = pop_slist(stack);
 182         overwrite_slist(slist, &cur_slist);
 183         push_slist(stack, slist);
 184 }
 185
 186
 187 void __use_cond_true_states()
 188 {
 189         __use_cond_stack(&cond_true_stack);
 190 }
 191
 192 void __use_cond_false_states()
 193 {
 194         __use_cond_stack(&cond_false_stack);
 195 }
 196
 197 void __negate_cond_stacks()
 198 {
 199         struct state_list *old_false, *old_true;
 200
 201         old_false = pop_slist(&cond_false_stack);
 202         old_true = pop_slist(&cond_true_stack);
 203
 204         overwrite_slist(old_false, &cur_slist);
 205
 206         push_slist(&cond_false_stack, old_true);
 207         push_slist(&cond_true_stack, old_false);
 208 }
 209
 210
 211 void __and_cond_states()
 212 {
 213         struct state_list *tmp_slist;
 214
 215         tmp_slist = pop_slist(&cond_true_stack);
 216         and_slist_stack(&cond_true_stack, tmp_slist);
 217         or_slist_stack(&cond_false_stack);
 218 }
 219
 220 void __or_cond_states()
 221 {
 222         struct state_list *tmp_slist;
 223
 224         or_slist_stack(&cond_true_stack);
 225         tmp_slist = pop_slist(&cond_false_stack);
 226         and_slist_stack(&cond_false_stack, tmp_slist);
 227 }
 228
 229
 230 void __save_pre_cond_states()
 231 {
 232         push_slist(&pre_cond_stack, clone_slist(cur_slist));
 233 }
 234
 235 void __pop_pre_cond_states()
 236 {
 237         struct state_list *tmp;
 238
 239         tmp = pop_slist(&pre_cond_stack);
 240         del_slist(&tmp);
 241 }
 242
 243 void __use_false_only_stack()
 244 {
 245         struct state_list *slist;
 246
 247         slist = pop_slist(&false_only_stack);
 248         overwrite_slist(slist, &cur_slist);
 249         del_slist(&slist);
 250 }
 251
 252 void __pop_false_only_stack()
 253 {
 254         struct state_list *slist;
 255
 256         slist = pop_slist(&false_only_stack);
 257         del_slist(&slist);
 258 }
 259
 260 void __use_cond_states()
 261 {
 262         struct state_list *pre, *pre_clone, *true_states, *false_states;
 263
 264         pre = pop_slist(&pre_cond_stack);
 265         pre_clone = clone_slist(pre);
 266
 267         true_states = pop_slist(&cond_true_stack);
 268         overwrite_slist(true_states, &pre);
 269         /* we use the true states right away */
 270         del_slist(&cur_slist);
 271         cur_slist = pre;
 272
 273         false_states = pop_slist(&cond_false_stack);
 274         push_slist(&false_only_stack, clone_slist(false_states));
 275         overwrite_slist(false_states, &pre_clone);
 276         push_slist(&false_stack, pre_clone);
 277 }
 278
 279 void __push_true_states()
 280 {
 281         push_slist(&true_stack, clone_slist(cur_slist));
 282 }
 283
 284 void __use_false_states()
 285 {
 286         del_slist(&cur_slist);
 287         cur_slist = pop_slist(&false_stack);
 288 }
 289
 290 void __pop_false_states()
 291 {
 292         struct state_list *slist;
 293
 294         slist = pop_slist(&false_stack);
 295         del_slist(&slist);
 296 }
 297
 298 void __merge_false_states()
 299 {
 300         struct state_list *slist;
 301
 302         slist = pop_slist(&false_stack);
 303         merge_slist(slist);
 304         del_slist(&slist);
 305 }
 306
 307 void __merge_true_states()
 308 {
 309         struct state_list *slist;
 310
 311         slist = pop_slist(&true_stack);
 312         merge_slist(slist);
 313         del_slist(&slist);
 314 }
 315
 316 void __push_continues()
 317 {
 318         push_slist(&continue_stack, NULL);
 319         set_state_stack(&continue_stack, "__smatch_continue_used", 0, NULL, 0);
 320 }
 321
 322 void __pop_continues()
 323 {
 324         struct state_list *slist;
 325
 326         slist = pop_slist(&continue_stack);
 327         del_slist(&slist);
 328 }
 329
 330 void __process_continues()
 331 {
 332         struct smatch_state *state;
 333
 334         set_state_stack(&continue_stack, "__smatch_continue_used", 1, NULL, 0);
 335         FOR_EACH_PTR(cur_slist, state) {
 336                 merge_state_stack(&continue_stack, state->name, state->owner,
 337                                   state->sym, state->state);
 338         } END_FOR_EACH_PTR(state);
 339 }
 340
 341 void __merge_continues()
 342 {
 343         struct state_list *slist;
 344         int tmp;
 345
 346         slist = pop_slist(&continue_stack);
 347         tmp = get_state_slist(slist, "__smatch_continue_used", 0, NULL);
 348         delete_state_slist(&slist, "__smatch_continue_used", 0, NULL);
 349         if (tmp == 1)
 350                 merge_slist(slist);
 351         del_slist(&slist);
 352 }
 353
 354 int __break_called()
 355 {
 356         if (get_state_stack(break_stack, "__smatch_break_used", 0, NULL) == 1)
 357                 return 1;
 358         return 0;
 359 }
 360
 361 void __push_breaks()
 362 {
 363         push_slist(&break_stack, NULL);
 364         set_state_stack(&break_stack, "__smatch_break_used", 0, NULL, 0);
 365 }
 366
 367 void __process_breaks()
 368 {
 369         struct smatch_state *state;
 370
 371         set_state_stack(&break_stack, "__smatch_break_used", 0, NULL, 1);
 372         FOR_EACH_PTR(cur_slist, state) {
 373                 merge_state_stack(&break_stack, state->name, state->owner,
 374                                   state->sym, state->state);
 375         } END_FOR_EACH_PTR(state);
 376 }
 377
 378 void __merge_breaks()
 379 {
 380         struct state_list *slist;
 381         int tmp;
 382
 383         slist = pop_slist(&break_stack);
 384         tmp = get_state_slist(slist, "__smatch_break_used", 0, NULL);
 385         delete_state_slist(&slist, "__smatch_break_used", 0, NULL);
 386         if (tmp == 1)
 387                 merge_slist(slist);
 388         del_slist(&slist);
 389 }
 390
 391 void __use_breaks()
 392 {
 393         struct state_list *slist;
 394         int tmp;
 395
 396         del_slist(&cur_slist);
 397         slist = pop_slist(&break_stack);
 398
 399         tmp = get_state_slist(slist, "__smatch_break_used", 0, NULL);
 400         delete_state_slist(&slist, "__smatch_break_used", 0, NULL);
 401
 402         if (tmp == 1)
 403                 cur_slist = slist;
 404         else
 405                 del_slist(&slist);
 406 }
 407
 408 void __pop_breaks()
 409 {
 410         struct state_list *slist;
 411
 412         slist = pop_slist(&break_stack);
 413         del_slist(&slist);
 414 }
 415
 416 void __save_switch_states()
 417 {
 418         push_slist(&switch_stack, clone_slist(cur_slist));
 419 }
 420
 421 void __merge_switches()
 422 {
 423         struct state_list *slist;
 424
 425         slist = pop_slist(&switch_stack);
 426         merge_slist(slist);
 427         push_slist(&switch_stack, slist);
 428 }
 429
 430 void __pop_switches()
 431 {
 432         struct state_list *slist;
 433
 434         slist = pop_slist(&switch_stack);
 435         del_slist(&slist);
 436 }
 437
 438 void __push_default()
 439 {
 440         push_slist(&default_stack, NULL);
 441         set_state_stack(&default_stack, "has_default", 0, NULL, 0);
 442 }
 443
 444 void __set_default()
 445 {
 446         set_state_stack(&default_stack, "has_default", 0, NULL, 1);
 447 }
 448
 449 int __pop_default()
 450 {
 451         struct state_list *slist;
 452         struct smatch_state *state;
 453
 454         int ret = -1;
 455         slist = pop_slist(&default_stack);
 456         FOR_EACH_PTR(slist, state) {
 457                 if (!strcmp(state->name, "has_default"))
 458                         ret = state->state;
 459         } END_FOR_EACH_PTR(state);
 460         del_slist(&slist);
 461         return ret;
 462 }
 463
 464 static struct named_slist *alloc_named_slist(const char *name,
 465                                          struct state_list *slist)
 466 {
 467         struct named_slist *named_slist = __alloc_named_slist(0);
 468
 469         named_slist->name = (char *)name;
 470         named_slist->slist = slist;
 471         return named_slist;
 472 }
 473
 474 void __save_gotos(const char *name)
 475 {
 476         struct state_list *slist;
 477
 478         slist = get_slist_from_slist_stack(goto_stack, name);
 479         if (slist) {
 480                 struct smatch_state *state;
 481
 482                 FOR_EACH_PTR(cur_slist, state) {
 483                         merge_state_slist(&slist, state->name, state->owner,
 484                                           state->sym, state->state);
 485                 } END_FOR_EACH_PTR(state);
 486                 return;
 487         } else {
 488                 struct state_list *slist;
 489                 struct named_slist *named_slist;
 490
 491                 slist = clone_slist(cur_slist);
 492                 named_slist = alloc_named_slist(name, slist);
 493                 add_ptr_list(&goto_stack, named_slist);
 494         }
 495 }
 496
 497 void __merge_gotos(const char *name)
 498 {
 499         struct state_list *slist;
 500
 501         slist = get_slist_from_slist_stack(goto_stack, name);
 502         if (slist)
 503                 merge_slist(slist);
 504 }