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 sm_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 sm_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 nullify_path()
 120 {
 121         del_slist(&cur_slist);
 122 }
 123
 124 /*
 125  * At the start of every function we mark the path
 126  * as unnull.  That there is always at least one state
 127  * in the cur_slist until nullify_path is called.  This
 128  * is used in merge_slist() for the first null check.
 129  */
 130
 131 void __unnullify_path()
 132 {
 133         set_state("unnull_path", 0, NULL, 1);
 134 }
 135
 136 void clear_all_states()
 137 {
 138         struct named_slist *named_slist;
 139
 140         nullify_path();
 141         del_slist_stack(&true_stack);
 142         del_slist_stack(&false_stack);
 143         del_slist_stack(&false_only_stack);
 144         del_slist_stack(&pre_cond_stack);
 145         del_slist_stack(&cond_true_stack);
 146         del_slist_stack(&cond_false_stack);
 147         del_slist_stack(&break_stack);
 148         del_slist_stack(&switch_stack);
 149         del_slist_stack(&continue_stack);
 150
 151         FOR_EACH_PTR(goto_stack, named_slist) {
 152                 del_slist(&named_slist->slist);
 153         } END_FOR_EACH_PTR(named_slist);
 154         __free_ptr_list((struct ptr_list **)&goto_stack);
 155 }
 156
 157
 158 void __push_cond_stacks()
 159 {
 160         push_slist(&cond_true_stack, NULL);
 161         push_slist(&cond_false_stack, NULL);
 162 }
 163
 164 /*
 165  * This combines the pre cond states with either the true or false states.
 166  * For example:
 167  * a = kmalloc() ; if (a !! foo(a)
 168  * In the pre state a is possibly null.  In the true state it is non null.
 169  * In the false state it is null.  Combine the pre and the false to get
 170  * that when we call 'foo', 'a' is null.
 171  */
 172
 173 static void __use_cond_stack(struct state_list_stack **stack)
 174 {
 175         struct state_list *slist;
 176
 177         del_slist(&cur_slist);
 178
 179         cur_slist = pop_slist(&pre_cond_stack);
 180         push_slist(&pre_cond_stack, clone_slist(cur_slist));
 181
 182         slist = pop_slist(stack);
 183         overwrite_slist(slist, &cur_slist);
 184         push_slist(stack, slist);
 185 }
 186
 187
 188 void __use_cond_true_states()
 189 {
 190         __use_cond_stack(&cond_true_stack);
 191 }
 192
 193 void __use_cond_false_states()
 194 {
 195         __use_cond_stack(&cond_false_stack);
 196 }
 197
 198 void __negate_cond_stacks()
 199 {
 200         struct state_list *old_false, *old_true;
 201
 202         old_false = pop_slist(&cond_false_stack);
 203         old_true = pop_slist(&cond_true_stack);
 204
 205         overwrite_slist(old_false, &cur_slist);
 206
 207         push_slist(&cond_false_stack, old_true);
 208         push_slist(&cond_true_stack, old_false);
 209 }
 210
 211
 212 void __and_cond_states()
 213 {
 214         struct state_list *tmp_slist;
 215
 216         tmp_slist = pop_slist(&cond_true_stack);
 217         and_slist_stack(&cond_true_stack, tmp_slist);
 218         or_slist_stack(&cond_false_stack);
 219 }
 220
 221 void __or_cond_states()
 222 {
 223         struct state_list *tmp_slist;
 224
 225         or_slist_stack(&cond_true_stack);
 226         tmp_slist = pop_slist(&cond_false_stack);
 227         and_slist_stack(&cond_false_stack, tmp_slist);
 228 }
 229
 230
 231 void __save_pre_cond_states()
 232 {
 233         push_slist(&pre_cond_stack, clone_slist(cur_slist));
 234 }
 235
 236 void __pop_pre_cond_states()
 237 {
 238         struct state_list *tmp;
 239
 240         tmp = pop_slist(&pre_cond_stack);
 241         del_slist(&tmp);
 242 }
 243
 244 void __use_false_only_stack()
 245 {
 246         struct state_list *slist;
 247
 248         slist = pop_slist(&false_only_stack);
 249         overwrite_slist(slist, &cur_slist);
 250         del_slist(&slist);
 251 }
 252
 253 void __pop_false_only_stack()
 254 {
 255         struct state_list *slist;
 256
 257         slist = pop_slist(&false_only_stack);
 258         del_slist(&slist);
 259 }
 260
 261 void __use_cond_states()
 262 {
 263         struct state_list *pre, *pre_clone, *true_states, *false_states;
 264
 265         pre = pop_slist(&pre_cond_stack);
 266         pre_clone = clone_slist(pre);
 267
 268         true_states = pop_slist(&cond_true_stack);
 269         overwrite_slist(true_states, &pre);
 270         /* we use the true states right away */
 271         del_slist(&cur_slist);
 272         cur_slist = pre;
 273
 274         false_states = pop_slist(&cond_false_stack);
 275         push_slist(&false_only_stack, clone_slist(false_states));
 276         overwrite_slist(false_states, &pre_clone);
 277         push_slist(&false_stack, pre_clone);
 278 }
 279
 280 void __push_true_states()
 281 {
 282         push_slist(&true_stack, clone_slist(cur_slist));
 283 }
 284
 285 void __use_false_states()
 286 {
 287         del_slist(&cur_slist);
 288         cur_slist = pop_slist(&false_stack);
 289 }
 290
 291 void __pop_false_states()
 292 {
 293         struct state_list *slist;
 294
 295         slist = pop_slist(&false_stack);
 296         del_slist(&slist);
 297 }
 298
 299 void __merge_false_states()
 300 {
 301         struct state_list *slist;
 302
 303         slist = pop_slist(&false_stack);
 304         merge_slist(slist);
 305         del_slist(&slist);
 306 }
 307
 308 void __merge_true_states()
 309 {
 310         struct state_list *slist;
 311
 312         slist = pop_slist(&true_stack);
 313         merge_slist(slist);
 314         del_slist(&slist);
 315 }
 316
 317 void __push_continues()
 318 {
 319         push_slist(&continue_stack, NULL);
 320         set_state_stack(&continue_stack, "__smatch_continue_used", 0, NULL, 0);
 321 }
 322
 323 void __pop_continues()
 324 {
 325         struct state_list *slist;
 326
 327         slist = pop_slist(&continue_stack);
 328         del_slist(&slist);
 329 }
 330
 331 void __process_continues()
 332 {
 333         struct sm_state *state;
 334
 335         set_state_stack(&continue_stack, "__smatch_continue_used", 1, NULL, 0);
 336         FOR_EACH_PTR(cur_slist, state) {
 337                 merge_state_stack(&continue_stack, state->name, state->owner,
 338                                   state->sym, state->state);
 339         } END_FOR_EACH_PTR(state);
 340 }
 341
 342 void __merge_continues()
 343 {
 344         struct state_list *slist;
 345         int tmp;
 346
 347         slist = pop_slist(&continue_stack);
 348         tmp = get_state_slist(slist, "__smatch_continue_used", 0, NULL);
 349         delete_state_slist(&slist, "__smatch_continue_used", 0, NULL);
 350         if (tmp == 1)
 351                 merge_slist(slist);
 352         del_slist(&slist);
 353 }
 354
 355 void __push_breaks()
 356 {
 357         push_slist(&break_stack, NULL);
 358         set_state_stack(&break_stack, "__smatch_break_used", 0, NULL, 0);
 359 }
 360
 361 void __process_breaks()
 362 {
 363         struct sm_state *state;
 364
 365         set_state_stack(&break_stack, "__smatch_break_used", 0, NULL, 1);
 366         FOR_EACH_PTR(cur_slist, state) {
 367                 merge_state_stack(&break_stack, state->name, state->owner,
 368                                   state->sym, state->state);
 369         } END_FOR_EACH_PTR(state);
 370 }
 371
 372 void __merge_breaks()
 373 {
 374         struct state_list *slist;
 375         int tmp;
 376
 377         slist = pop_slist(&break_stack);
 378         tmp = get_state_slist(slist, "__smatch_break_used", 0, NULL);
 379         delete_state_slist(&slist, "__smatch_break_used", 0, NULL);
 380         if (tmp == 1)
 381                 merge_slist(slist);
 382         del_slist(&slist);
 383 }
 384
 385 void __use_breaks()
 386 {
 387         struct state_list *slist;
 388         int tmp;
 389
 390         del_slist(&cur_slist);
 391         slist = pop_slist(&break_stack);
 392
 393         tmp = get_state_slist(slist, "__smatch_break_used", 0, NULL);
 394         delete_state_slist(&slist, "__smatch_break_used", 0, NULL);
 395
 396         if (tmp == 1)
 397                 cur_slist = slist;
 398         else
 399                 del_slist(&slist);
 400 }
 401
 402 void __pop_breaks()
 403 {
 404         struct state_list *slist;
 405
 406         slist = pop_slist(&break_stack);
 407         del_slist(&slist);
 408 }
 409
 410 void __save_switch_states()
 411 {
 412         push_slist(&switch_stack, clone_slist(cur_slist));
 413 }
 414
 415 void __merge_switches()
 416 {
 417         struct state_list *slist;
 418
 419         slist = pop_slist(&switch_stack);
 420         merge_slist(slist);
 421         push_slist(&switch_stack, slist);
 422 }
 423
 424 void __pop_switches()
 425 {
 426         struct state_list *slist;
 427
 428         slist = pop_slist(&switch_stack);
 429         del_slist(&slist);
 430 }
 431
 432 void __push_default()
 433 {
 434         push_slist(&default_stack, NULL);
 435         set_state_stack(&default_stack, "has_default", 0, NULL, 0);
 436 }
 437
 438 void __set_default()
 439 {
 440         set_state_stack(&default_stack, "has_default", 0, NULL, 1);
 441 }
 442
 443 int __pop_default()
 444 {
 445         struct state_list *slist;
 446         struct sm_state *state;
 447
 448         int ret = -1;
 449         slist = pop_slist(&default_stack);
 450         FOR_EACH_PTR(slist, state) {
 451                 if (!strcmp(state->name, "has_default"))
 452                         ret = state->state;
 453         } END_FOR_EACH_PTR(state);
 454         del_slist(&slist);
 455         return ret;
 456 }
 457
 458 static struct named_slist *alloc_named_slist(const char *name,
 459                                          struct state_list *slist)
 460 {
 461         struct named_slist *named_slist = __alloc_named_slist(0);
 462
 463         named_slist->name = (char *)name;
 464         named_slist->slist = slist;
 465         return named_slist;
 466 }
 467
 468 void __save_gotos(const char *name)
 469 {
 470         struct state_list *slist;
 471
 472         slist = get_slist_from_slist_stack(goto_stack, name);
 473         if (slist) {
 474                 struct sm_state *state;
 475
 476                 FOR_EACH_PTR(cur_slist, state) {
 477                         merge_state_slist(&slist, state->name, state->owner,
 478                                           state->sym, state->state);
 479                 } END_FOR_EACH_PTR(state);
 480                 return;
 481         } else {
 482                 struct state_list *slist;
 483                 struct named_slist *named_slist;
 484
 485                 slist = clone_slist(cur_slist);
 486                 named_slist = alloc_named_slist(name, slist);
 487                 add_ptr_list(&goto_stack, named_slist);
 488         }
 489 }
 490
 491 void __merge_gotos(const char *name)
 492 {
 493         struct state_list *slist;
 494
 495         slist = get_slist_from_slist_stack(goto_stack, name);
 496         if (slist)
 497                 merge_slist(slist);
 498 }