smatch_param_limit.c

   1 /*
   2  * Copyright (C) 2012 Oracle.
   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  * The PARAM_LIMIT code is for functions like this:
  20  *
  21  * int frob(int a)
  22  * {
  23  *        if (a >= 0 && a < 10) {
  24  *                 a = 42;
  25  *                 return 1;
  26  *        }
  27  *        return 0;
  28  * }
  29  *
  30  * If frob() returns 1, then we know that a must have been in the 0-9 range
  31  * at the start.  Or if we return 0 then a is outside that range.  So if the
  32  * caller passes a 5 then the function must return 1.
  33  *
  34  * The "a" variable gets set to 42 in the middle, but we don't care about
  35  * that, we only care about the passed in value.
  36  *
  37  * Originally, this code looked at the starting stree and the final stree and
  38  * asked was this variable set part way through?  (Over simplification).  This
  39  * approach works, but the problem is that it produces too many results.  For
  40  * example, if we dereference a pointer then we know that it must be non-NULL.
  41  * So that was recorded as a PARAM_LIMIT.  Another thing is that if we have
  42  * two callers and we do "if (caller_one) return true; else return false;".  The
  43  * if (caller_one) condition might have implications so maybe it sets twenty
  44  * different states instead of just the one.
  45  *
  46  * These extra PARAM_LIMITs are still correct, but the problem is that they
  47  * take up space in the database.  Perhaps more importantly parsing PARAM_LIMITS
  48  * is very expensive because we have to figure out the implications for that.
  49  * (2023: idea: Parse all the PARAM_LIMITS at once instead of sequentially).
  50  * The PARAM_LIMITS create a lot of sm_state history and use a lot of resources.
  51  *
  52  * So we need a more deliberate approach.
  53  */
  54
  55 #include "smatch.h"
  56 #include "smatch_extra.h"
  57 #include "smatch_slist.h"
  58
  59 static int my_id;
  60
  61 static struct stree *limit_states;
  62 static struct stree *ignore_states;
  63
  64 int __no_limits;
  65
  66 static struct smatch_state *unmatched_state(struct sm_state *sm)
  67 {
  68         struct smatch_state *state;
  69
  70         if (!param_was_set_var_sym(sm->name, sm->sym)) {
  71                 state = __get_state(SMATCH_EXTRA, sm->name, sm->sym);
  72                 if (state)
  73                         return state;
  74         }
  75         return alloc_estate_whole(estate_type(sm->state));
  76 }
  77
  78 struct smatch_state *get_orig_estate(const char *name, struct symbol *sym)
  79 {
  80         struct smatch_state *state;
  81
  82         state = get_state(my_id, name, sym);
  83         if (state)
  84                 return state;
  85
  86         state = get_state(SMATCH_EXTRA, name, sym);
  87         if (state)
  88                 return state;
  89         return alloc_estate_rl(alloc_whole_rl(get_real_base_type(sym)));
  90 }
  91
  92 static struct range_list *generify_mtag_range(struct smatch_state *state)
  93 {
  94         struct range_list *rl;
  95         struct data_range *drange;
  96
  97         if (!estate_type(state) || estate_type(state)->type != SYM_PTR)
  98                 return estate_rl(state);
  99
 100         /*
 101          * The problem is that we get too specific on our param limits when we
 102          * know exactly what pointers are passed to a function.  It gets to the
 103          * point where we say "pointer x will succeed, but everything else will
 104          * fail."  And then we introduce a new caller which passes a different
 105          * pointer and it's like, "Sorry bro, that's not possible."
 106          *
 107          */
 108         rl = estate_rl(state);
 109         FOR_EACH_PTR(rl, drange) {
 110                 if (drange->min.value != drange->max.value)
 111                         continue;
 112                 if (drange->min.value == 0)
 113                         continue;
 114                 if (is_err_ptr(drange->min))
 115                         continue;
 116                 return rl_union(valid_ptr_rl, rl);
 117         } END_FOR_EACH_PTR(drange);
 118
 119         return estate_rl(state);
 120 }
 121
 122 static bool sm_was_set(struct sm_state *sm)
 123 {
 124         struct relation *rel;
 125
 126         if (!estate_related(sm->state))
 127                 return param_was_set_var_sym(sm->name, sm->sym);
 128
 129         FOR_EACH_PTR(estate_related(sm->state), rel) {
 130                 if (param_was_set_var_sym(sm->name, sm->sym))
 131                         return true;
 132         } END_FOR_EACH_PTR(rel);
 133         return false;
 134 }
 135
 136 static bool is_boring_pointer_info(const char *name, struct range_list *rl)
 137 {
 138         char *rl_str;
 139
 140         /* addresses are always boring */
 141         if (name[0] == '&')
 142                 return true;
 143
 144         /*
 145          * One way that PARAM_LIMIT can be set is by dereferencing pointers.
 146          * It's not necessarily very valuable to track that a pointer must
 147          * be non-NULL.  It's even less valuable to know that it's either NULL
 148          * or valid.  It can be nice to know that it's not an error pointer, I
 149          * suppose.  But let's not pass that data back to all the callers
 150          * forever.
 151          *
 152          */
 153
 154         if (strlen(name) < 40)
 155                 return false;
 156
 157         rl_str = show_rl(rl);
 158         if (!rl_str)
 159                 return false;
 160
 161         if (strcmp(rl_str, "4096-ptr_max") == 0 ||
 162             strcmp(rl_str, "0,4096-ptr_max") == 0)
 163                 return true;
 164
 165         return false;
 166 }
 167
 168 static void print_return_value_param(int return_id, char *return_ranges, struct expression *expr)
 169 {
 170         struct smatch_state *state, *old;
 171         struct sm_state *tmp;
 172         struct range_list *rl;
 173         const char *orig_name, *key;
 174         struct symbol *sym;
 175         int param;
 176
 177         FOR_EACH_MY_SM(SMATCH_EXTRA, __get_cur_stree(), tmp) {
 178                 if (tmp->name[0] == '&')
 179                         continue;
 180
 181                 if (!get_state_stree(limit_states, my_id, tmp->name, tmp->sym) &&
 182                     get_state_stree(ignore_states, my_id, tmp->name, tmp->sym))
 183                         continue;
 184
 185                 orig_name = get_param_var_sym_var_sym(tmp->name, tmp->sym, NULL, &sym);
 186                 if (!orig_name || !sym)
 187                         continue;
 188                 param = get_param_key_from_var_sym(orig_name, sym, NULL, &key);
 189                 if (param < 0)
 190                         continue;
 191
 192                 state = __get_state(my_id, orig_name, sym);
 193                 if (!state) {
 194                         if (sm_was_set(tmp))
 195                                 continue;
 196                         state = tmp->state;
 197                 }
 198
 199                 if (estate_is_whole(state) || estate_is_empty(state))
 200                         continue;
 201                 old = get_state_stree(get_start_states(), SMATCH_EXTRA, tmp->name, tmp->sym);
 202                 if (old && rl_equiv(estate_rl(old), estate_rl(state)))
 203                         continue;
 204
 205                 if (is_ignored_kernel_data(key))
 206                         continue;
 207
 208                 rl = generify_mtag_range(state);
 209                 if (is_boring_pointer_info(key, rl))
 210                         continue;
 211
 212                 sql_insert_return_states(return_id, return_ranges, PARAM_LIMIT,
 213                                          param, key, show_rl(rl));
 214         } END_FOR_EACH_SM(tmp);
 215 }
 216
 217 static void extra_mod_hook(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
 218 {
 219         struct smatch_state *orig;
 220         struct symbol *param_sym;
 221         char *param_name;
 222
 223         if (expr && expr->smatch_flags & Fake)
 224                 return;
 225
 226         param_name = get_param_var_sym_var_sym(name, sym, NULL, &param_sym);
 227         if (!param_name || !param_sym)
 228                 goto free;
 229         if (get_param_num_from_sym(param_sym) < 0)
 230                 goto free;
 231
 232         /* already saved */
 233         if (get_state(my_id, param_name, param_sym))
 234                 goto free;
 235
 236         if (__in_buf_clear)
 237                 return;
 238
 239         orig = get_state(SMATCH_EXTRA, param_name, param_sym);
 240         if (!orig)
 241                 orig = alloc_estate_whole(estate_type(state));
 242
 243         set_state(my_id, param_name, param_sym, orig);
 244 free:
 245         free_string(param_name);
 246 }
 247
 248 static void extra_nomod_hook(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
 249 {
 250         if (__no_limits) {
 251                 set_state_stree(&ignore_states, my_id, name, sym, &undefined);
 252                 return;
 253         }
 254         set_state_stree(&limit_states, my_id, name, sym, &undefined);
 255 }
 256
 257 static void match_end_func(struct symbol *sym)
 258 {
 259         free_stree(&ignore_states);
 260         free_stree(&limit_states);
 261 }
 262
 263 void register_param_limit(int id)
 264 {
 265         my_id = id;
 266
 267         add_function_data((unsigned long *)&limit_states);
 268         add_function_data((unsigned long *)&ignore_states);
 269         add_hook(&match_end_func, END_FUNC_HOOK);
 270
 271         db_ignore_states(my_id);
 272         set_dynamic_states(my_id);
 273
 274         add_extra_mod_hook(&extra_mod_hook);
 275         add_extra_nomod_hook(&extra_nomod_hook);
 276         add_unmatched_state_hook(my_id, &unmatched_state);
 277         add_merge_hook(my_id, &merge_estates);
 278
 279         add_split_return_callback(&print_return_value_param);
 280 }
 281