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