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