check_atomic_inc_dec.c

   1 /*
   2  * Copyright (C) 2016 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 #include <ctype.h>
  19
  20 #include "smatch.h"
  21 #include "smatch_extra.h"
  22 #include "smatch_slist.h"
  23
  24 static int my_id;
  25
  26 STATE(inc);
  27 STATE(orig);
  28 STATE(dec);
  29
  30 static struct smatch_state *unmatched_state(struct sm_state *sm)
  31 {
  32         if (parent_is_gone_var_sym(sm->name, sm->sym))
  33                 return sm->state;
  34         return &undefined;
  35 }
  36
  37 static struct stree *start_states;
  38 static struct stree_stack *saved_stack;
  39 static void set_start_state(const char *name, struct symbol *sym, struct smatch_state *start)
  40 {
  41         struct smatch_state *orig;
  42
  43         orig = get_state_stree(start_states, my_id, name, sym);
  44         if (!orig)
  45                 set_state_stree(&start_states, my_id, name, sym, start);
  46         else if (orig != start)
  47                 set_state_stree(&start_states, my_id, name, sym, &undefined);
  48 }
  49
  50 static struct sm_state *get_best_match(const char *key)
  51 {
  52         struct sm_state *sm;
  53         struct sm_state *match;
  54         int cnt = 0;
  55         int start_pos, state_len, key_len, chunks, i;
  56
  57         if (strncmp(key, "$->", 3) == 0)
  58                 key += 3;
  59
  60         key_len = strlen(key);
  61         chunks = 0;
  62         for (i = key_len - 1; i > 0; i--) {
  63                 if (key[i] == '>' || key[i] == '.')
  64                         chunks++;
  65                 if (chunks == 2) {
  66                         key += (i + 1);
  67                         key_len = strlen(key);
  68                         break;
  69                 }
  70         }
  71
  72         FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
  73                 state_len = strlen(sm->name);
  74                 if (state_len < key_len)
  75                         continue;
  76                 start_pos = state_len - key_len;
  77                 if ((start_pos == 0 || !isalnum(sm->name[start_pos - 1])) &&
  78                     strcmp(sm->name + start_pos, key) == 0) {
  79                         cnt++;
  80                         match = sm;
  81                 }
  82         } END_FOR_EACH_SM(sm);
  83
  84         if (cnt == 1)
  85                 return match;
  86         return NULL;
  87 }
  88
  89 static void db_inc_dec(struct expression *expr, int param, const char *key, const char *value, int inc_dec)
  90 {
  91         struct sm_state *start_sm;
  92         struct expression *arg;
  93         char *name;
  94         struct symbol *sym;
  95         bool free_at_end = true;
  96
  97         while (expr->type == EXPR_ASSIGNMENT)
  98                 expr = strip_expr(expr->right);
  99         if (expr->type != EXPR_CALL)
 100                 return;
 101
 102         arg = get_argument_from_call_expr(expr->args, param);
 103         if (!arg)
 104                 return;
 105
 106         name = get_variable_from_key(arg, key, &sym);
 107         if (!name || !sym)
 108                 goto free;
 109
 110         start_sm = get_sm_state(my_id, name, sym);
 111         if (!start_sm && inc_dec == ATOMIC_DEC) {
 112                 start_sm = get_best_match(key);
 113                 if (start_sm) {
 114                         free_string(name);
 115                         free_at_end = false;
 116                         name = (char *)start_sm->name;
 117                         sym = start_sm->sym;
 118                 }
 119         }
 120
 121         if (inc_dec == ATOMIC_INC) {
 122                 if (!start_sm)
 123                         set_start_state(name, sym, &dec);
 124                 set_state(my_id, name, sym, &inc);
 125         } else {
 126                 if (!start_sm)
 127                         set_start_state(name, sym, &inc);
 128
 129                 if (start_sm && start_sm->state == &inc)
 130                         set_state(my_id, name, sym, &orig);
 131                 else
 132                         set_state(my_id, name, sym, &dec);
 133         }
 134
 135 free:
 136         if (free_at_end)
 137                 free_string(name);
 138 }
 139
 140 static void db_inc(struct expression *expr, int param, char *key, char *value)
 141 {
 142         db_inc_dec(expr, param, key, value, ATOMIC_INC);
 143 }
 144
 145 static void db_dec(struct expression *expr, int param, char *key, char *value)
 146 {
 147         db_inc_dec(expr, param, key, value, ATOMIC_DEC);
 148 }
 149
 150 static void match_atomic_inc(const char *fn, struct expression *expr, void *_unused)
 151 {
 152         db_inc_dec(expr, 0, "$->counter", "", ATOMIC_INC);
 153 }
 154
 155 static void match_atomic_dec(const char *fn, struct expression *expr, void *_unused)
 156 {
 157         db_inc_dec(expr, 0, "$->counter", "", ATOMIC_DEC);
 158 }
 159
 160 static void match_atomic_add(const char *fn, struct expression *expr, void *_unused)
 161 {
 162         struct expression *amount;
 163         sval_t sval;
 164
 165         amount = get_argument_from_call_expr(expr->args, 0);
 166         if (get_implied_value(amount, &sval) && sval_is_negative(sval)) {
 167                 db_inc_dec(expr, 1, "$->counter", "", ATOMIC_DEC);
 168                 return;
 169         }
 170
 171         db_inc_dec(expr, 1, "$->counter", "", ATOMIC_INC);
 172 }
 173
 174 static void match_atomic_sub(const char *fn, struct expression *expr, void *_unused)
 175 {
 176         db_inc_dec(expr, 1, "$->counter", "", ATOMIC_DEC);
 177 }
 178
 179 static void refcount_inc(const char *fn, struct expression *expr, void *param)
 180 {
 181         db_inc_dec(expr, PTR_INT(param), "$->ref.counter", "", ATOMIC_INC);
 182 }
 183
 184 static void refcount_dec(const char *fn, struct expression *expr, void *param)
 185 {
 186         db_inc_dec(expr, PTR_INT(param), "$->ref.counter", "", ATOMIC_DEC);
 187 }
 188
 189 static void match_return_info(int return_id, char *return_ranges, struct expression *expr)
 190 {
 191         struct sm_state *sm;
 192         const char *param_name;
 193         int param;
 194
 195         FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
 196                 if (sm->state != &inc &&
 197                     sm->state != &dec)
 198                         continue;
 199                 if (parent_is_gone_var_sym(sm->name, sm->sym))
 200                         continue;
 201                 param = get_param_num_from_sym(sm->sym);
 202                 if (param < 0)
 203                         continue;
 204                 param_name = get_param_name(sm);
 205                 if (!param_name)
 206                         continue;
 207                 sql_insert_return_states(return_id, return_ranges,
 208                                          (sm->state == &inc) ? ATOMIC_INC : ATOMIC_DEC,
 209                                          param, param_name, "");
 210         } END_FOR_EACH_SM(sm);
 211 }
 212
 213 enum {
 214         EMPTY, NEGATIVE, ZERO, POSITIVE, NUM_BUCKETS
 215 };
 216
 217 static int success_fail_positive(struct range_list *rl)
 218 {
 219         if (!rl)
 220                 return EMPTY;
 221
 222         if (sval_is_negative(rl_min(rl)))
 223                 return NEGATIVE;
 224
 225         if (rl_min(rl).value == 0)
 226                 return ZERO;
 227
 228         return POSITIVE;
 229 }
 230
 231 static void check_counter(const char *name, struct symbol *sym)
 232 {
 233         struct range_list *inc_lines = NULL;
 234         struct range_list *dec_lines = NULL;
 235         int inc_buckets[NUM_BUCKETS] = {};
 236         int dec_buckets[NUM_BUCKETS] = {};
 237         struct stree *stree, *orig_stree;
 238         struct sm_state *return_sm;
 239         struct sm_state *sm;
 240         sval_t line = sval_type_val(&int_ctype, 0);
 241         int bucket;
 242
 243         FOR_EACH_PTR(get_all_return_strees(), stree) {
 244                 orig_stree = __swap_cur_stree(stree);
 245
 246                 return_sm = get_sm_state(RETURN_ID, "return_ranges", NULL);
 247                 if (!return_sm)
 248                         goto swap_stree;
 249                 line.value = return_sm->line;
 250
 251                 if (get_state_stree(start_states, my_id, name, sym) == &inc)
 252                         goto swap_stree;
 253
 254                 if (parent_is_gone_var_sym(name, sym))
 255                         goto swap_stree;
 256
 257                 sm = get_sm_state(my_id, name, sym);
 258                 if (!sm)
 259                         goto swap_stree;
 260
 261                 if (sm->state != &inc &&
 262                     sm->state != &dec &&
 263                     sm->state != &orig)
 264                         goto swap_stree;
 265
 266                 bucket = success_fail_positive(estate_rl(return_sm->state));
 267
 268                 if (sm->state == &inc) {
 269                         add_range(&inc_lines, line, line);
 270                         inc_buckets[bucket] = true;
 271                 }
 272                 if (sm->state == &dec || sm->state == &orig) {
 273                         add_range(&dec_lines, line, line);
 274                         dec_buckets[bucket] = true;
 275                 }
 276 swap_stree:
 277                 __swap_cur_stree(orig_stree);
 278         } END_FOR_EACH_PTR(stree);
 279
 280         if (inc_buckets[NEGATIVE] &&
 281             inc_buckets[ZERO]) {
 282                 // sm_warning("XXX '%s' not decremented on lines: %s.", name, show_rl(inc_lines));
 283         }
 284
 285 }
 286
 287 static void match_check_missed(struct symbol *sym)
 288 {
 289         struct sm_state *sm;
 290
 291         FOR_EACH_MY_SM(my_id, get_all_return_states(), sm) {
 292                 check_counter(sm->name, sm->sym);
 293         } END_FOR_EACH_SM(sm);
 294 }
 295
 296 int on_atomic_dec_path(void)
 297 {
 298         struct sm_state *sm;
 299
 300         FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
 301                 if (sm->state == &dec)
 302                         return 1;
 303         } END_FOR_EACH_SM(sm);
 304
 305         return 0;
 306 }
 307
 308 int was_inced(const char *name, struct symbol *sym)
 309 {
 310         return get_state(my_id, name, sym) == &inc;
 311 }
 312
 313 static void match_save_states(struct expression *expr)
 314 {
 315         push_stree(&saved_stack, start_states);
 316         start_states = NULL;
 317 }
 318
 319 static void match_restore_states(struct expression *expr)
 320 {
 321         start_states = pop_stree(&saved_stack);
 322 }
 323
 324 static void match_after_func(struct symbol *sym)
 325 {
 326         free_stree(&start_states);
 327 }
 328
 329 void check_atomic_inc_dec(int id)
 330 {
 331         my_id = id;
 332
 333         if (option_project != PROJ_KERNEL)
 334                 return;
 335
 336         add_unmatched_state_hook(my_id, &unmatched_state);
 337
 338         add_split_return_callback(match_return_info);
 339         select_return_states_hook(ATOMIC_INC, &db_inc);
 340         select_return_states_hook(ATOMIC_DEC, &db_dec);
 341
 342         add_function_hook("atomic_inc_return", &match_atomic_inc, NULL);
 343         add_function_hook("atomic_add_return", &match_atomic_add, NULL);
 344         add_function_hook("atomic_sub_return", &match_atomic_sub, NULL);
 345         add_function_hook("atomic_sub_and_test", &match_atomic_sub, NULL);
 346         add_function_hook("atomic_dec_and_test", &match_atomic_dec, NULL);
 347         add_function_hook("_atomic_dec_and_lock", &match_atomic_dec, NULL);
 348         add_function_hook("atomic_dec", &match_atomic_dec, NULL);
 349         add_function_hook("atomic_long_inc", &match_atomic_inc, NULL);
 350         add_function_hook("atomic_long_dec", &match_atomic_dec, NULL);
 351         add_function_hook("atomic_inc", &match_atomic_inc, NULL);
 352         add_function_hook("atomic_sub", &match_atomic_sub, NULL);
 353
 354         add_function_hook("refcount_inc", &refcount_inc, INT_PTR(0));
 355         add_function_hook("refcount_dec", &refcount_dec, INT_PTR(0));
 356         add_function_hook("refcount_add", &refcount_inc, INT_PTR(1));
 357         add_function_hook("refcount_add_not_zero", &refcount_inc, INT_PTR(1));
 358         add_function_hook("refcount_inc_not_zero", &refcount_inc, INT_PTR(0));
 359         add_function_hook("refcount_sub_and_test", &refcount_dec, INT_PTR(1));
 360         add_function_hook("refcount_dec_and_test", &refcount_dec, INT_PTR(0));
 361
 362         add_hook(&match_check_missed, END_FUNC_HOOK);
 363
 364         add_hook(&match_after_func, AFTER_FUNC_HOOK);
 365         add_hook(&match_save_states, INLINE_FN_START);
 366         add_hook(&match_restore_states, INLINE_FN_END);
 367 }