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