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