check_balanced.c

   1 /*
   2  * Copyright (C) 2009 Dan Carpenter.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 /*
  19  * This test checks that prempt is enabled at the end of every function.
  20  */
  21
  22 #include "smatch.h"
  23 #include "smatch_slist.h"
  24
  25 static int my_id;
  26
  27 STATE(left);
  28 STATE(right);
  29 STATE(start_state);
  30
  31 static struct tracker_list *starts_left;
  32 static struct tracker_list *starts_right;
  33
  34 static struct smatch_state *get_start_state(struct sm_state *sm)
  35 {
  36        int is_left = 0;
  37        int is_right = 0;
  38
  39        if (in_tracker_list(starts_left, my_id, sm->name, sm->sym))
  40                is_left = 1;
  41        if (in_tracker_list(starts_right, my_id, sm->name, sm->sym))
  42                is_right = 1;
  43        if (is_left && is_right)
  44                return &undefined;
  45        if (is_left)
  46                return &left;
  47        if (is_right)
  48                return &right;
  49         return &undefined;
  50 }
  51
  52 static struct smatch_state *unmatched_state(struct sm_state *sm)
  53 {
  54         return &start_state;
  55 }
  56
  57 static void match_left(const char *fn, struct expression *expr, void *data)
  58 {
  59         struct sm_state *sm;
  60         char *name = (char *)data;
  61
  62         if (__inline_fn)
  63                 return;
  64
  65         sm = get_sm_state(my_id, name, NULL);
  66         if (!sm)
  67                 add_tracker(&starts_right, my_id, name, NULL);
  68         if (sm && slist_has_state(sm->possible, &left))
  69                 sm_msg("warn: double '%s'", fn);
  70         set_state(my_id, (char *)data, NULL, &left);
  71 }
  72
  73 static void match_right(const char *fn, struct expression *expr, void *data)
  74 {
  75         struct sm_state *sm;
  76         char *name = (char *)data;
  77
  78         if (__inline_fn)
  79                 return;
  80
  81         sm = get_sm_state(my_id, name, NULL);
  82         if (!sm)
  83                 add_tracker(&starts_left, my_id, name, NULL);
  84         if (sm && slist_has_state(sm->possible, &right))
  85                 sm_msg("warn: double '%s'", fn);
  86         set_state(my_id, (char *)data, NULL, &right);
  87 }
  88
  89 static void check_possible(struct sm_state *sm)
  90 {
  91         struct sm_state *tmp;
  92         int is_left = 0;
  93         int is_right = 0;
  94         int undef = 0;
  95
  96         FOR_EACH_PTR(sm->possible, tmp) {
  97                 if (tmp->state == &left)
  98                         is_left = 1;
  99                 if (tmp->state == &right)
 100                         is_right = 1;
 101                 if (tmp->state == &start_state) {
 102                         struct smatch_state *s;
 103
 104                         s = get_start_state(tmp);
 105                         if (s == &left)
 106                                 is_left = 1;
 107                         else if (s == &right)
 108                                 is_right = 1;
 109                         else
 110                                 undef = 1;
 111                 }
 112                 if (tmp->state == &undefined)
 113                         undef = 1;  // i don't think this is possible any more.
 114         } END_FOR_EACH_PTR(tmp);
 115         if ((is_left && is_right) || undef)
 116                 sm_msg("warn: returning with unbalanced %s", sm->name);
 117 }
 118
 119 static void match_return(struct expression *expr)
 120 {
 121         struct AVL *stree;
 122         struct sm_state *tmp;
 123
 124         if (__inline_fn)
 125                 return;
 126
 127         stree = get_all_states_stree(my_id);
 128         FOR_EACH_SM(stree, tmp) {
 129                 if (tmp->state == &merged)
 130                         check_possible(tmp);
 131         } END_FOR_EACH_SM(tmp);
 132         free_stree(&stree);
 133 }
 134
 135 static void clear_lists(void)
 136 {
 137         free_trackers_and_list(&starts_left);
 138         free_trackers_and_list(&starts_right);
 139 }
 140
 141 static void match_func_end(struct symbol *sym)
 142 {
 143         if (__inline_fn)
 144                 return;
 145         if (is_reachable())
 146                 match_return(NULL);
 147         clear_lists();
 148 }
 149
 150 static void get_left_funcs(const char *name, struct token **token)
 151 {
 152         const char *func;
 153
 154         while (token_type(*token) == TOKEN_IDENT) {
 155                 func = show_ident((*token)->ident);
 156                 add_function_hook(func, &match_left, (char *)name);
 157                 *token = (*token)->next;
 158         }
 159         if (token_type(*token) == TOKEN_SPECIAL)
 160                 *token = (*token)->next;
 161 }
 162
 163 static void get_right_funcs(const char *name, struct token **token)
 164 {
 165         const char *func;
 166
 167         while (token_type(*token) == TOKEN_IDENT) {
 168                 func = show_ident((*token)->ident);
 169                 add_function_hook(func, &match_right, (char *)name);
 170                 *token = (*token)->next;
 171         }
 172         if (token_type(*token) == TOKEN_SPECIAL)
 173                 *token = (*token)->next;
 174 }
 175
 176 static void register_funcs_from_file(void)
 177 {
 178         struct token *token;
 179         char *name;
 180
 181         token = get_tokens_file("kernel.balanced_funcs");
 182         if (!token)
 183                 return;
 184         if (token_type(token) != TOKEN_STREAMBEGIN)
 185                 return;
 186         token = token->next;
 187         while (token_type(token) != TOKEN_STREAMEND) {
 188                 if (token_type(token) != TOKEN_IDENT)
 189                         return;
 190                 name = alloc_string(show_ident(token->ident));
 191                 token = token->next;
 192                 get_left_funcs(name, &token);
 193                 get_right_funcs(name, &token);
 194         }
 195         clear_token_alloc();
 196 }
 197
 198 void check_balanced(int id)
 199 {
 200         my_id = id;
 201         add_unmatched_state_hook(my_id, &unmatched_state);
 202         add_hook(&match_return, RETURN_HOOK);
 203         add_hook(&match_func_end, END_FUNC_HOOK);
 204         register_funcs_from_file();
 205 }