xref: /illumos-gate/usr/src/tools/smatch/src/check_atomic_inc_dec.c (revision b3263c98)

/*
 * Copyright (C) 2016 Oracle.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
 */

#include <ctype.h>

#include "smatch.h"
#include "smatch_extra.h"
#include "smatch_slist.h"

static int my_id;

STATE(inc);
STATE(start_state);
STATE(dec);

static struct smatch_state *unmatched_state(struct sm_state *sm)
{
	/*
	 * We default to decremented.  For example, say we have:
	 * 	if (p)
	 *		atomic_dec(p);
	 *      <- p is decreemented.
	 *
	 */
	if ((sm->state == &dec) &&
	    parent_is_gone_var_sym(sm->name, sm->sym))
		return sm->state;
	return &start_state;
}

static struct stree *start_states;
static struct stree_stack *saved_stack;
static void set_start_state(const char *name, struct symbol *sym, struct smatch_state *start)
{
	struct smatch_state *orig;

	orig = get_state_stree(start_states, my_id, name, sym);
	if (!orig)
		set_state_stree(&start_states, my_id, name, sym, start);
	else if (orig != start)
		set_state_stree(&start_states, my_id, name, sym, &undefined);
}

static struct sm_state *get_best_match(const char *key)
{
	struct sm_state *sm;
	struct sm_state *match;
	int cnt = 0;
	int start_pos, state_len, key_len, chunks, i;

	if (strncmp(key, "$->", 3) == 0)
		key += 3;

	key_len = strlen(key);
	chunks = 0;
	for (i = key_len - 1; i > 0; i--) {
		if (key[i] == '>' || key[i] == '.')
			chunks++;
		if (chunks == 2) {
			key += (i + 1);
			key_len = strlen(key);
			break;
		}
	}

	FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
		state_len = strlen(sm->name);
		if (state_len < key_len)
			continue;
		start_pos = state_len - key_len;
		if ((start_pos == 0 || !isalnum(sm->name[start_pos - 1])) &&
		    strcmp(sm->name + start_pos, key) == 0) {
			cnt++;
			match = sm;
		}
	} END_FOR_EACH_SM(sm);

	if (cnt == 1)
		return match;
	return NULL;
}

static void db_inc_dec(struct expression *expr, int param, const char *key, int inc_dec)
{
	struct sm_state *start_sm;
	struct expression *arg;
	char *name;
	struct symbol *sym;
	bool free_at_end = true;

	while (expr->type == EXPR_ASSIGNMENT)
		expr = strip_expr(expr->right);
	if (expr->type != EXPR_CALL)
		return;

	arg = get_argument_from_call_expr(expr->args, param);
	if (!arg)
		return;

	name = get_variable_from_key(arg, key, &sym);
	if (!name || !sym)
		goto free;

	start_sm = get_sm_state(my_id, name, sym);
	if (!start_sm && inc_dec == ATOMIC_DEC) {
		start_sm = get_best_match(key);
		if (start_sm) {
			free_string(name);
			free_at_end = false;
			name = (char *)start_sm->name;
			sym = start_sm->sym;
		}
	}

	if (inc_dec == ATOMIC_INC) {
		if (!start_sm)
			set_start_state(name, sym, &dec);
//		set_refcount_inc(name, sym);
		set_state(my_id, name, sym, &inc);
	} else {
//		set_refcount_dec(name, sym);
		if (!start_sm)
			set_start_state(name, sym, &inc);

		if (start_sm && start_sm->state == &inc)
			set_state(my_id, name, sym, &start_state);
		else
			set_state(my_id, name, sym, &dec);
	}

free:
	if (free_at_end)
		free_string(name);
}

static const char *primitive_funcs[] = {
	"atomic_inc_return",
	"atomic_add_return",
	"atomic_sub_return",
	"atomic_sub_and_test",
	"atomic_dec_and_test",
	"_atomic_dec_and_lock",
	"atomic_dec",
	"atomic_long_inc",
	"atomic_long_dec",
	"atomic_inc",
	"atomic_sub",
	"refcount_inc",
	"refcount_dec",
	"refcount_add",
	"refcount_add_not_zero",
	"refcount_inc_not_zero",
	"refcount_sub_and_test",
	"refcount_dec_and_test",
	"atomic_dec_if_positive",
};

static bool is_inc_dec_primitive(struct expression *expr)
{
	int i;

	while (expr->type == EXPR_ASSIGNMENT)
		expr = strip_expr(expr->right);
	if (expr->type != EXPR_CALL)
		return false;

	if (expr->fn->type != EXPR_SYMBOL)
		return false;

	for (i = 0; i < ARRAY_SIZE(primitive_funcs); i++) {
		if (sym_name_is(primitive_funcs[i], expr->fn))
			return true;
	}

	return false;
}

static void db_inc(struct expression *expr, int param, char *key, char *value)
{
	if (is_inc_dec_primitive(expr))
		return;
	db_inc_dec(expr, param, key, ATOMIC_INC);
}

static void db_dec(struct expression *expr, int param, char *key, char *value)
{
	if (is_inc_dec_primitive(expr))
		return;
	db_inc_dec(expr, param, key, ATOMIC_DEC);
}

static void match_atomic_inc(const char *fn, struct expression *expr, void *_unused)
{
	db_inc_dec(expr, 0, "$->counter", ATOMIC_INC);
}

static void match_atomic_dec(const char *fn, struct expression *expr, void *_unused)
{
	db_inc_dec(expr, 0, "$->counter", ATOMIC_DEC);
}

static void match_atomic_add(const char *fn, struct expression *expr, void *_unused)
{
	struct expression *amount;
	sval_t sval;

	amount = get_argument_from_call_expr(expr->args, 0);
	if (get_implied_value(amount, &sval) && sval_is_negative(sval)) {
		db_inc_dec(expr, 1, "$->counter", ATOMIC_DEC);
		return;
	}

	db_inc_dec(expr, 1, "$->counter", ATOMIC_INC);
}

static void match_atomic_sub(const char *fn, struct expression *expr, void *_unused)
{
	db_inc_dec(expr, 1, "$->counter", ATOMIC_DEC);
}

static void refcount_inc(const char *fn, struct expression *expr, void *param)
{
	db_inc_dec(expr, PTR_INT(param), "$->ref.counter", ATOMIC_INC);
}

static void refcount_dec(const char *fn, struct expression *expr, void *param)
{
	db_inc_dec(expr, PTR_INT(param), "$->ref.counter", ATOMIC_DEC);
}

static void pm_runtime_get_sync(const char *fn, struct expression *expr, void *param)
{
	db_inc_dec(expr, PTR_INT(param), "$->power.usage_count.counter", ATOMIC_INC);
}

static void match_implies_inc(const char *fn, struct expression *call_expr,
			      struct expression *assign_expr, void *param)
{
	db_inc_dec(call_expr, PTR_INT(param), "$->ref.counter", ATOMIC_INC);
}

static void match_implies_atomic_dec(const char *fn, struct expression *call_expr,
			      struct expression *assign_expr, void *param)
{
	db_inc_dec(call_expr, PTR_INT(param), "$->counter", ATOMIC_DEC);
}

static bool is_maybe_dec(struct sm_state *sm)
{
	if (sm->state == &dec)
		return true;
	if (slist_has_state(sm->possible, &dec) &&
	    !slist_has_state(sm->possible, &inc))
		return true;
	return false;
}

static void match_return_info(int return_id, char *return_ranges, struct expression *expr)
{
	struct sm_state *sm;
	const char *param_name;
	int param;

	if (is_impossible_path())
		return;

	FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
		if (sm->state != &inc && !is_maybe_dec(sm))
			continue;
		if (sm->state == get_state_stree(start_states, my_id, sm->name, sm->sym))
			continue;
		if (parent_is_gone_var_sym(sm->name, sm->sym))
			continue;
		param = get_param_num_from_sym(sm->sym);
		if (param < 0)
			continue;
		param_name = get_param_name(sm);
		if (!param_name)
			continue;
		sql_insert_return_states(return_id, return_ranges,
					 (sm->state == &inc) ? ATOMIC_INC : ATOMIC_DEC,
					 param, param_name, "");
	} END_FOR_EACH_SM(sm);
}

enum {
	EMPTY, NEGATIVE, ZERO, POSITIVE, NUM_BUCKETS
};

static int success_fail_positive(struct range_list *rl)
{
	if (!rl)
		return EMPTY;

	if (!is_whole_rl(rl) && sval_is_negative(rl_min(rl)))
		return NEGATIVE;

	if (rl_min(rl).value == 0)
		return ZERO;

	return POSITIVE;
}

static void check_counter(const char *name, struct symbol *sym)
{
	struct range_list *inc_lines = NULL;
	struct range_list *dec_lines = NULL;
	int inc_buckets[NUM_BUCKETS] = {};
	int dec_buckets[NUM_BUCKETS] = {};
	struct stree *stree, *orig_stree;
	struct smatch_state *state;
	struct sm_state *return_sm;
	struct sm_state *sm;
	sval_t line = sval_type_val(&int_ctype, 0);
	int bucket;

	/* static variable are probably just counters */
	if (sym->ctype.modifiers & MOD_STATIC &&
	    !(sym->ctype.modifiers & MOD_TOPLEVEL))
		return;

	FOR_EACH_PTR(get_all_return_strees(), stree) {
		orig_stree = __swap_cur_stree(stree);

		if (is_impossible_path())
			goto swap_stree;

		return_sm = get_sm_state(RETURN_ID, "return_ranges", NULL);
		if (!return_sm)
			goto swap_stree;
		line.value = return_sm->line;

		if (get_state_stree(start_states, my_id, name, sym) == &inc)
			goto swap_stree;

		if (parent_is_gone_var_sym(name, sym))
			goto swap_stree;

		sm = get_sm_state(my_id, name, sym);
		if (sm)
			state = sm->state;
		else
			state = &start_state;

		if (state != &inc &&
		    state != &dec &&
		    state != &start_state)
			goto swap_stree;

		bucket = success_fail_positive(estate_rl(return_sm->state));

		if (state == &inc) {
			add_range(&inc_lines, line, line);
			inc_buckets[bucket] = true;
		}
		if (state == &dec || state == &start_state) {
			add_range(&dec_lines, line, line);
			dec_buckets[bucket] = true;
		}
swap_stree:
		__swap_cur_stree(orig_stree);
	} END_FOR_EACH_PTR(stree);

	if (inc_buckets[NEGATIVE] &&
	    inc_buckets[ZERO]) {
		// sm_warning("XXX '%s' not decremented on lines: %s.", name, show_rl(inc_lines));
	}

}

static void match_check_missed(struct symbol *sym)
{
	struct sm_state *sm;

	FOR_EACH_MY_SM(my_id, get_all_return_states(), sm) {
		check_counter(sm->name, sm->sym);
	} END_FOR_EACH_SM(sm);
}

int on_atomic_dec_path(void)
{
	struct sm_state *sm;

	FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
		if (sm->state == &dec)
			return 1;
	} END_FOR_EACH_SM(sm);

	return 0;
}

int was_inced(const char *name, struct symbol *sym)
{
	return get_state(my_id, name, sym) == &inc;
}

static void match_save_states(struct expression *expr)
{
	push_stree(&saved_stack, start_states);
	start_states = NULL;
}

static void match_restore_states(struct expression *expr)
{
	start_states = pop_stree(&saved_stack);
}

static void match_after_func(struct symbol *sym)
{
	free_stree(&start_states);
}

void check_atomic_inc_dec(int id)
{
	my_id = id;

	if (option_project != PROJ_KERNEL)
		return;

	add_unmatched_state_hook(my_id, &unmatched_state);

	add_split_return_callback(match_return_info);
	select_return_states_hook(ATOMIC_INC, &db_inc);
	select_return_states_hook(ATOMIC_DEC, &db_dec);

	add_function_hook("atomic_inc_return", &match_atomic_inc, NULL);
	add_function_hook("atomic_add_return", &match_atomic_add, NULL);
	add_function_hook("atomic_sub_return", &match_atomic_sub, NULL);
	add_function_hook("atomic_sub_and_test", &match_atomic_sub, NULL);
	add_function_hook("atomic_long_sub_and_test", &match_atomic_sub, NULL);
	add_function_hook("atomic64_sub_and_test", &match_atomic_sub, NULL);
	add_function_hook("atomic_dec_and_test", &match_atomic_dec, NULL);
	add_function_hook("atomic_long_dec_and_test", &match_atomic_dec, NULL);
	add_function_hook("atomic64_dec_and_test", &match_atomic_dec, NULL);
	add_function_hook("_atomic_dec_and_lock", &match_atomic_dec, NULL);
	add_function_hook("atomic_dec", &match_atomic_dec, NULL);
	add_function_hook("atomic_dec_return", &match_atomic_dec, NULL);
	add_function_hook("atomic_long_inc", &match_atomic_inc, NULL);
	add_function_hook("atomic_long_dec", &match_atomic_dec, NULL);
	add_function_hook("atomic_inc", &match_atomic_inc, NULL);
	add_function_hook("atomic_sub", &match_atomic_sub, NULL);

	add_function_hook("refcount_inc", &refcount_inc, INT_PTR(0));
	add_function_hook("refcount_dec", &refcount_dec, INT_PTR(0));
	add_function_hook("refcount_add", &refcount_inc, INT_PTR(1));

	return_implies_state("refcount_add_not_zero", 1, 1, &match_implies_inc, INT_PTR(1));
	return_implies_state("refcount_inc_not_zero", 1, 1, &match_implies_inc, INT_PTR(0));

	return_implies_state("atomic_dec_if_positive", 0, INT_MAX, &match_implies_atomic_dec, INT_PTR(0));

	add_function_hook("refcount_sub_and_test", &refcount_dec, INT_PTR(1));
	add_function_hook("refcount_dec_and_test", &refcount_dec, INT_PTR(0));

	add_function_hook("pm_runtime_get_sync", &pm_runtime_get_sync, INT_PTR(0));

	add_hook(&match_check_missed, END_FUNC_HOOK);

	add_hook(&match_after_func, AFTER_FUNC_HOOK);
	add_hook(&match_save_states, INLINE_FN_START);
	add_hook(&match_restore_states, INLINE_FN_END);
}