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 stree *stree;
 122         struct sm_state *tmp;
 123
 124         if (__inline_fn)
 125                 return;
 126
 127         stree = __get_cur_stree();
 128         FOR_EACH_MY_SM(my_id, stree, tmp) {
 129                 if (tmp->state == &merged)
 130                         check_possible(tmp);
 131         } END_FOR_EACH_SM(tmp);
 132 }
 133
 134 static void clear_lists(void)
 135 {
 136         free_trackers_and_list(&starts_left);
 137         free_trackers_and_list(&starts_right);
 138 }
 139
 140 static void match_func_end(struct symbol *sym)
 141 {
 142         if (__inline_fn)
 143                 return;
 144         if (is_reachable())
 145                 match_return(NULL);
 146         clear_lists();
 147 }
 148
 149 static void get_left_funcs(const char *name, struct token **token)
 150 {
 151         const char *func;
 152
 153         while (token_type(*token) == TOKEN_IDENT) {
 154                 func = show_ident((*token)->ident);
 155                 add_function_hook(func, &match_left, (char *)name);
 156                 *token = (*token)->next;
 157         }
 158         if (token_type(*token) == TOKEN_SPECIAL)
 159                 *token = (*token)->next;
 160 }
 161
 162 static void get_right_funcs(const char *name, struct token **token)
 163 {
 164         const char *func;
 165
 166         while (token_type(*token) == TOKEN_IDENT) {
 167                 func = show_ident((*token)->ident);
 168                 add_function_hook(func, &match_right, (char *)name);
 169                 *token = (*token)->next;
 170         }
 171         if (token_type(*token) == TOKEN_SPECIAL)
 172                 *token = (*token)->next;
 173 }
 174
 175 static void register_funcs_from_file(void)
 176 {
 177         struct token *token;
 178         char *name;
 179
 180         token = get_tokens_file("kernel.balanced_funcs");
 181         if (!token)
 182                 return;
 183         if (token_type(token) != TOKEN_STREAMBEGIN)
 184                 return;
 185         token = token->next;
 186         while (token_type(token) != TOKEN_STREAMEND) {
 187                 if (token_type(token) != TOKEN_IDENT)
 188                         return;
 189                 name = alloc_string(show_ident(token->ident));
 190                 token = token->next;
 191                 get_left_funcs(name, &token);
 192                 get_right_funcs(name, &token);
 193         }
 194         clear_token_alloc();
 195 }
 196
 197 void check_balanced(int id)
 198 {
 199         my_id = id;
 200         add_unmatched_state_hook(my_id, &unmatched_state);
 201         add_hook(&match_return, RETURN_HOOK);
 202         add_hook(&match_func_end, END_FUNC_HOOK);
 203         register_funcs_from_file();
 204 }