11f5207bJohn Levon/*
21f5207bJohn Levon * Copyright (C) 2012 Oracle.
31f5207bJohn Levon *
41f5207bJohn Levon * This program is free software; you can redistribute it and/or
51f5207bJohn Levon * modify it under the terms of the GNU General Public License
61f5207bJohn Levon * as published by the Free Software Foundation; either version 2
71f5207bJohn Levon * of the License, or (at your option) any later version.
81f5207bJohn Levon *
91f5207bJohn Levon * This program is distributed in the hope that it will be useful,
101f5207bJohn Levon * but WITHOUT ANY WARRANTY; without even the implied warranty of
121f5207bJohn Levon * GNU General Public License for more details.
131f5207bJohn Levon *
141f5207bJohn Levon * You should have received a copy of the GNU General Public License
151f5207bJohn Levon * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
161f5207bJohn Levon */
171f5207bJohn Levon
181f5207bJohn Levon/*
191f5207bJohn Levon * The point here is to store that a buffer has x bytes even if we don't know
201f5207bJohn Levon * the value of x.
211f5207bJohn Levon *
221f5207bJohn Levon */
231f5207bJohn Levon
241f5207bJohn Levon#include "smatch.h"
251f5207bJohn Levon#include "smatch_extra.h"
261f5207bJohn Levon#include "smatch_slist.h"
271f5207bJohn Levon
281f5207bJohn Levonstatic int size_id;
291f5207bJohn Levonstatic int link_id;
301f5207bJohn Levon
311f5207bJohn Levon/*
32efe51d0John Levon * There is a bunch of code which does this:
331f5207bJohn Levon *
341f5207bJohn Levon *     if (size)
351f5207bJohn Levon *         foo = malloc(size);
361f5207bJohn Levon *
37efe51d0John Levon * So if "size" is non-zero then the size of "foo" is size.  But really it's
38efe51d0John Levon * also true if size is zero.  It's just better to assume to not trample over
39efe51d0John Levon * the data that we have by merging &undefined states.
401f5207bJohn Levon *
411f5207bJohn Levon */
421f5207bJohn Levonstatic struct smatch_state *unmatched_state(struct sm_state *sm)
431f5207bJohn Levon{
441f5207bJohn Levon	return sm->state;
451f5207bJohn Levon}
461f5207bJohn Levon
471f5207bJohn Levonstatic struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
481f5207bJohn Levon{
491f5207bJohn Levon	struct expression *expr1, *expr2;
501f5207bJohn Levon
511f5207bJohn Levon	expr1 = s1->data;
521f5207bJohn Levon	expr2 = s2->data;
531f5207bJohn Levon
541f5207bJohn Levon	if (expr1 && expr2 && expr_equiv(expr1, expr2))
551f5207bJohn Levon		return s1;
561f5207bJohn Levon	return &merged;
571f5207bJohn Levon}
581f5207bJohn Levon
591f5207bJohn Levonstatic void match_link_modify(struct sm_state *sm, struct expression *mod_expr)
601f5207bJohn Levon{
611f5207bJohn Levon	struct expression *expr;
621f5207bJohn Levon	struct sm_state *tmp;
631f5207bJohn Levon
641f5207bJohn Levon	expr = sm->state->data;
651f5207bJohn Levon	if (expr) {
661f5207bJohn Levon		set_state_expr(size_id, expr, &undefined);
671f5207bJohn Levon		set_state(link_id, sm->name, sm->sym, &undefined);
681f5207bJohn Levon		return;
691f5207bJohn Levon	}
701f5207bJohn Levon
711f5207bJohn Levon	FOR_EACH_PTR(sm->possible, tmp) {
721f5207bJohn Levon		expr = tmp->state->data;
731f5207bJohn Levon		if (expr)
741f5207bJohn Levon			set_state_expr(size_id, expr, &undefined);
751f5207bJohn Levon	} END_FOR_EACH_PTR(tmp);
761f5207bJohn Levon	set_state(link_id, sm->name, sm->sym, &undefined);
771f5207bJohn Levon}
781f5207bJohn Levon
79efe51d0John Levonstatic const char *limit_map[] = {
80efe51d0John Levon	"byte_count",
81efe51d0John Levon	"elem_count",
82efe51d0John Levon	"elem_last",
83efe51d0John Levon	"used_count",
84efe51d0John Levon	"used_last",
85efe51d0John Levon};
86efe51d0John Levon
87efe51d0John Levonint state_to_limit(struct smatch_state *state)
88efe51d0John Levon{
89efe51d0John Levon	int i;
90efe51d0John Levon
91efe51d0John Levon	if (!state || !state->data)
92efe51d0John Levon		return -1;
93efe51d0John Levon
94efe51d0John Levon	for (i = 0; i < ARRAY_SIZE(limit_map); i++) {
95efe51d0John Levon		if (strncmp(state->name, limit_map[i], strlen(limit_map[i])) == 0)
96efe51d0John Levon			return i + BYTE_COUNT;
97efe51d0John Levon	}
98efe51d0John Levon
99efe51d0John Levon	return -1;
100efe51d0John Levon}
101efe51d0John Levon
102efe51d0John Levonconst char *limit_type_str(unsigned int limit_type)
103efe51d0John Levon{
104efe51d0John Levon	if (limit_type - BYTE_COUNT >= ARRAY_SIZE(limit_map)) {
105efe51d0John Levon		sm_msg("internal: wrong size type %u", limit_type);
106efe51d0John Levon		return "unknown";
107efe51d0John Levon	}
108efe51d0John Levon
109efe51d0John Levon	return limit_map[limit_type - BYTE_COUNT];
110efe51d0John Levon}
111efe51d0John Levon
112efe51d0John Levonstatic struct smatch_state *alloc_compare_size(int limit_type, struct expression *expr)
1131f5207bJohn Levon{
1141f5207bJohn Levon	struct smatch_state *state;
1151f5207bJohn Levon	char *name;
116efe51d0John Levon	char buf[256];
1171f5207bJohn Levon
1181f5207bJohn Levon	state = __alloc_smatch_state(0);
1191f5207bJohn Levon	expr = strip_expr(expr);
1201f5207bJohn Levon	name = expr_to_str(expr);
121efe51d0John Levon	snprintf(buf, sizeof(buf), "%s %s", limit_type_str(limit_type), name);
122efe51d0John Levon	state->name = alloc_sname(buf);
1231f5207bJohn Levon	free_string(name);
1241f5207bJohn Levon	state->data = expr;
1251f5207bJohn Levon	return state;
1261f5207bJohn Levon}
1271f5207bJohn Levon
1281f5207bJohn Levonstatic int bytes_per_element(struct expression *expr)
1291f5207bJohn Levon{
1301f5207bJohn Levon	struct symbol *type;
1311f5207bJohn Levon
1321f5207bJohn Levon	type = get_type(expr);
1331f5207bJohn Levon	if (!type)
1341f5207bJohn Levon		return 0;
1351f5207bJohn Levon
1361f5207bJohn Levon	if (type->type != SYM_PTR && type->type != SYM_ARRAY)
1371f5207bJohn Levon		return 0;
1381f5207bJohn Levon
1391f5207bJohn Levon	type = get_base_type(type);
1401f5207bJohn Levon	return type_bytes(type);
1411f5207bJohn Levon}
1421f5207bJohn Levon
143efe51d0John Levonstatic void db_save_type_links(struct expression *array, int type_limit, struct expression *size)
1441f5207bJohn Levon{
1451f5207bJohn Levon	const char *array_name;
1461f5207bJohn Levon
1471f5207bJohn Levon	array_name = get_data_info_name(array);
1481f5207bJohn Levon	if (!array_name)
1491f5207bJohn Levon		array_name = "";
150efe51d0John Levon	sql_insert_data_info(size, type_limit, array_name);
1511f5207bJohn Levon}
1521f5207bJohn Levon
1531f5207bJohn Levonstatic void match_alloc_helper(struct expression *pointer, struct expression *size)
1541f5207bJohn Levon{
1551f5207bJohn Levon	struct expression *tmp;
1561f5207bJohn Levon	struct sm_state *sm;
157efe51d0John Levon	int limit_type = ELEM_COUNT;
1581f5207bJohn Levon	sval_t sval;
1591f5207bJohn Levon	int cnt = 0;
1601f5207bJohn Levon
1611f5207bJohn Levon	pointer = strip_expr(pointer);
1621f5207bJohn Levon	size = strip_expr(size);
1631f5207bJohn Levon	if (!size || !pointer)
1641f5207bJohn Levon		return;
1651f5207bJohn Levon
1661f5207bJohn Levon	while ((tmp = get_assigned_expr(size))) {
1671f5207bJohn Levon		size = strip_expr(tmp);
1681f5207bJohn Levon		if (cnt++ > 5)
1691f5207bJohn Levon			break;
1701f5207bJohn Levon	}
1711f5207bJohn Levon
1721f5207bJohn Levon	if (size->type == EXPR_BINOP && size->op == '*') {
1731f5207bJohn Levon		struct expression *mult_left, *mult_right;
1741f5207bJohn Levon
1751f5207bJohn Levon		mult_left = strip_expr(size->left);
1761f5207bJohn Levon		mult_right = strip_expr(size->right);
1771f5207bJohn Levon
1781f5207bJohn Levon		if (get_implied_value(mult_left, &sval) &&
1791f5207bJohn Levon		    sval.value == bytes_per_element(pointer))
1801f5207bJohn Levon			size = mult_right;
1811f5207bJohn Levon		else if (get_implied_value(mult_right, &sval) &&
1821f5207bJohn Levon		    sval.value == bytes_per_element(pointer))
1831f5207bJohn Levon			size = mult_left;
1841f5207bJohn Levon		else
1851f5207bJohn Levon			return;
1861f5207bJohn Levon	}
1871f5207bJohn Levon
1881f5207bJohn Levon	/* Only save links to variables, not fixed sizes */
1891f5207bJohn Levon	if (get_value(size, &sval))
1901f5207bJohn Levon		return;
1911f5207bJohn Levon
192efe51d0John Levon	if (size->type == EXPR_BINOP && size->op == '+' &&
193efe51d0John Levon	    get_value(size->right, &sval) && sval.value == 1) {
194efe51d0John Levon		size = size->left;
195efe51d0John Levon		limit_type = ELEM_LAST;
196efe51d0John Levon	}
197efe51d0John Levon
198efe51d0John Levon	db_save_type_links(pointer, limit_type, size);
199efe51d0John Levon	sm = set_state_expr(size_id, pointer, alloc_compare_size(limit_type, size));
2001f5207bJohn Levon	if (!sm)
2011f5207bJohn Levon		return;
202efe51d0John Levon	set_state_expr(link_id, size, alloc_state_expr(pointer));
2031f5207bJohn Levon}
2041f5207bJohn Levon
2051f5207bJohn Levonstatic void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
2061f5207bJohn Levon{
2071f5207bJohn Levon	int size_arg = PTR_INT(_size_arg);
2081f5207bJohn Levon	struct expression *pointer, *call, *arg;
2091f5207bJohn Levon
2101f5207bJohn Levon	pointer = strip_expr(expr->left);
2111f5207bJohn Levon	call = strip_expr(expr->right);
2121f5207bJohn Levon	arg = get_argument_from_call_expr(call->args, size_arg);
2131f5207bJohn Levon	match_alloc_helper(pointer, arg);
2141f5207bJohn Levon}
2151f5207bJohn Levon
2161f5207bJohn Levonstatic void match_calloc(const char *fn, struct expression *expr, void *_start_arg)
2171f5207bJohn Levon{
2181f5207bJohn Levon	int start_arg = PTR_INT(_start_arg);
2191f5207bJohn Levon	struct expression *pointer, *call, *arg;
2201f5207bJohn Levon	struct sm_state *tmp;
221efe51d0John Levon	int limit_type = ELEM_COUNT;
2221f5207bJohn Levon	sval_t sval;
2231f5207bJohn Levon
2241f5207bJohn Levon	pointer = strip_expr(expr->left);
2251f5207bJohn Levon	call = strip_expr(expr->right);
2261f5207bJohn Levon	arg = get_argument_from_call_expr(call->args, start_arg);
2271f5207bJohn Levon	if (get_implied_value(arg, &sval) &&
2281f5207bJohn Levon	    sval.value == bytes_per_element(pointer))
2291f5207bJohn Levon		arg = get_argument_from_call_expr(call->args, start_arg + 1);
2301f5207bJohn Levon
231efe51d0John Levon	if (arg->type == EXPR_BINOP && arg->op == '+' &&
232efe51d0John Levon	    get_value(arg->right, &sval) && sval.value == 1) {
233efe51d0John Levon		arg = arg->left;
234efe51d0John Levon		limit_type = ELEM_LAST;
235efe51d0John Levon	}
236efe51d0John Levon
237efe51d0John Levon	db_save_type_links(pointer, limit_type, arg);
238efe51d0John Levon	tmp = set_state_expr(size_id, pointer, alloc_compare_size(limit_type, arg));
2391f5207bJohn Levon	if (!tmp)
2401f5207bJohn Levon		return;
241efe51d0John Levon	set_state_expr(link_id, arg, alloc_state_expr(pointer));
2421f5207bJohn Levon}
2431f5207bJohn Levon
244efe51d0John Levonstruct expression *get_size_variable(struct expression *buf, int *limit_type)
2451f5207bJohn Levon{
2461f5207bJohn Levon	struct smatch_state *state;
2471f5207bJohn Levon
2481f5207bJohn Levon	state = get_state_expr(size_id, buf);
249efe51d0John Levon	if (!state)
250efe51d0John Levon		return NULL;
251efe51d0John Levon	*limit_type = state_to_limit(state);
252efe51d0John Levon	return state->data;
2531f5207bJohn Levon}
2541f5207bJohn Levon
2551f5207bJohn Levonstruct expression *get_array_variable(struct expression *size)
2561f5207bJohn Levon{
2571f5207bJohn Levon	struct smatch_state *state;
2581f5207bJohn Levon
2591f5207bJohn Levon	state = get_state_expr(link_id, size);
2601f5207bJohn Levon	if (state)
2611f5207bJohn Levon		return state->data;
2621f5207bJohn Levon	return NULL;
2631f5207bJohn Levon}
2641f5207bJohn Levon
2651f5207bJohn Levonstatic void array_check(struct expression *expr)
2661f5207bJohn Levon{
2671f5207bJohn Levon	struct expression *array;
2681f5207bJohn Levon	struct expression *size;
2691f5207bJohn Levon	struct expression *offset;
2701f5207bJohn Levon	char *array_str, *offset_str;
271efe51d0John Levon	int limit_type;
2721f5207bJohn Levon
2731f5207bJohn Levon	expr = strip_expr(expr);
2741f5207bJohn Levon	if (!is_array(expr))
2751f5207bJohn Levon		return;
2761f5207bJohn Levon
2771f5207bJohn Levon	array = get_array_base(expr);
278efe51d0John Levon	size = get_size_variable(array, &limit_type);
2791f5207bJohn Levon	if (!size)
2801f5207bJohn Levon		return;
281efe51d0John Levon	if (limit_type != ELEM_COUNT)
282efe51d0John Levon		return;
2831f5207bJohn Levon	offset = get_array_offset(expr);
2841f5207bJohn Levon	if (!possible_comparison(size, SPECIAL_EQUAL, offset))
2851f5207bJohn Levon		return;
2861f5207bJohn Levon
2871f5207bJohn Levon	array_str = expr_to_str(array);
2881f5207bJohn Levon	offset_str = expr_to_str(offset);
2891f5207bJohn Levon	sm_warning("potentially one past the end of array '%s[%s]'", array_str, offset_str);
2901f5207bJohn Levon	free_string(array_str);
2911f5207bJohn Levon	free_string(offset_str);
2921f5207bJohn Levon}
2931f5207bJohn Levon
2941f5207bJohn Levonstruct db_info {
2951f5207bJohn Levon	char *name;
2961f5207bJohn Levon	int ret;
2971f5207bJohn Levon};
2981f5207bJohn Levon
2991f5207bJohn Levonstatic int db_limitter_callback(void *_info, int argc, char **argv, char **azColName)
3001f5207bJohn Levon{
3011f5207bJohn Levon	struct db_info *info = _info;
3021f5207bJohn Levon
3031f5207bJohn Levon	/*
3041f5207bJohn Levon	 * If possible the limitters are tied to the struct they limit.  If we
3051f5207bJohn Levon	 * aren't sure which struct they limit then we use them as limitters for
3061f5207bJohn Levon	 * everything.
3071f5207bJohn Levon	 */
3081f5207bJohn Levon	if (!info->name || argv[0][0] == '\0' || strcmp(info->name, argv[0]) == 0)
3091f5207bJohn Levon		info->ret = 1;
3101f5207bJohn Levon	return 0;
3111f5207bJohn Levon}
3121f5207bJohn Levon
3131f5207bJohn Levonstatic char *vsl_to_data_info_name(const char *name, struct var_sym_list *vsl)
3141f5207bJohn Levon{
3151f5207bJohn Levon	struct var_sym *vs;
3161f5207bJohn Levon	struct symbol *type;
3171f5207bJohn Levon	static char buf[80];
3181f5207bJohn Levon	const char *p;
3191f5207bJohn Levon
3201f5207bJohn Levon	if (ptr_list_size((struct ptr_list *)vsl) != 1)
3211f5207bJohn Levon		return NULL;
3221f5207bJohn Levon	vs = first_ptr_list((struct ptr_list *)vsl);
3231f5207bJohn Levon
3241f5207bJohn Levon	type = get_real_base_type(vs->sym);
3251f5207bJohn Levon	if (!type || type->type != SYM_PTR)
3261f5207bJohn Levon		goto top_level_name;
3271f5207bJohn Levon	type = get_real_base_type(type);
3281f5207bJohn Levon	if (!type || type->type != SYM_STRUCT)
3291f5207bJohn Levon		goto top_level_name;
3301f5207bJohn Levon	if (!type->ident)
3311f5207bJohn Levon		goto top_level_name;
3321f5207bJohn Levon
3331f5207bJohn Levon	p = name;
3341f5207bJohn Levon	while ((name = strstr(p, "->")))
3351f5207bJohn Levon		p = name + 2;
3361f5207bJohn Levon
3371f5207bJohn Levon	snprintf(buf, sizeof(buf),"(struct %s)->%s", type->ident->name, p);
3381f5207bJohn Levon	return alloc_sname(buf);
3391f5207bJohn Levon
3401f5207bJohn Levontop_level_name:
3411f5207bJohn Levon	if (!(vs->sym->ctype.modifiers & MOD_TOPLEVEL))
3421f5207bJohn Levon		return NULL;
3431f5207bJohn Levon	if (vs->sym->ctype.modifiers & MOD_STATIC)
3441f5207bJohn Levon		snprintf(buf, sizeof(buf),"static %s", name);
3451f5207bJohn Levon	else
3461f5207bJohn Levon		snprintf(buf, sizeof(buf),"global %s", name);
3471f5207bJohn Levon	return alloc_sname(buf);
3481f5207bJohn Levon}
3491f5207bJohn Levon
3501f5207bJohn Levonint db_var_is_array_limit(struct expression *array, const char *name, struct var_sym_list *vsl)
3511f5207bJohn Levon{
3521f5207bJohn Levon	char *size_name;
3531f5207bJohn Levon	char *array_name = get_data_info_name(array);
3541f5207bJohn Levon	struct db_info db_info = {.name = array_name,};
3551f5207bJohn Levon
3561f5207bJohn Levon	size_name = vsl_to_data_info_name(name, vsl);
3571f5207bJohn Levon	if (!size_name)
3581f5207bJohn Levon		return 0;
3591f5207bJohn Levon
3601f5207bJohn Levon	run_sql(db_limitter_callback, &db_info,
3611f5207bJohn Levon		"select value from data_info where type = %d and data = '%s';",
3621f5207bJohn Levon		ARRAY_LEN, size_name);
3631f5207bJohn Levon
3641f5207bJohn Levon	return db_info.ret;
3651f5207bJohn Levon}
3661f5207bJohn Levon
367efe51d0John Levonint buf_comparison_index_ok(struct expression *expr)
3681f5207bJohn Levon{
3691f5207bJohn Levon	struct expression *array;
3701f5207bJohn Levon	struct expression *size;
3711f5207bJohn Levon	struct expression *offset;
372efe51d0John Levon	int limit_type;
3731f5207bJohn Levon	int comparison;
3741f5207bJohn Levon
3751f5207bJohn Levon	array = get_array_base(expr);
376efe51d0John Levon	size = get_size_variable(array, &limit_type);
3771f5207bJohn Levon	if (!size)
3781f5207bJohn Levon		return 0;
3791f5207bJohn Levon	offset = get_array_offset(expr);
380efe51d0John Levon	comparison = get_comparison(offset, size);
381efe51d0John Levon	if (!comparison)
382efe51d0John Levon		return 0;
383efe51d0John Levon
384efe51d0John Levon	if ((limit_type == ELEM_COUNT || limit_type == ELEM_LAST) &&
385efe51d0John Levon	    (comparison == '<' || comparison == SPECIAL_UNSIGNED_LT))
386efe51d0John Levon		return 1;
387efe51d0John Levon	if (limit_type == ELEM_LAST &&
388efe51d0John Levon	    (comparison == SPECIAL_LTE ||
389efe51d0John Levon	     comparison == SPECIAL_UNSIGNED_LTE ||
390efe51d0John Levon	     comparison == SPECIAL_EQUAL))
3911f5207bJohn Levon		return 1;
3921f5207bJohn Levon
3931f5207bJohn Levon	return 0;
3941f5207bJohn Levon}
3951f5207bJohn Levon
3961f5207bJohn Levonstatic int known_access_ok_numbers(struct expression *expr)
3971f5207bJohn Levon{
3981f5207bJohn Levon	struct expression *array;
3991f5207bJohn Levon	struct expression *offset;
4001f5207bJohn Levon	sval_t max;
4011f5207bJohn Levon	int size;
4021f5207bJohn Levon
4031f5207bJohn Levon	array = get_array_base(expr);
4041f5207bJohn Levon	offset = get_array_offset(expr);
4051f5207bJohn Levon
4061f5207bJohn Levon	size = get_array_size(array);
4071f5207bJohn Levon	if (size <= 0)
4081f5207bJohn Levon		return 0;
4091f5207bJohn Levon
4101f5207bJohn Levon	get_absolute_max(offset, &max);
4111f5207bJohn Levon	if (max.uvalue < size)
4121f5207bJohn Levon		return 1;
4131f5207bJohn Levon	return 0;
4141f5207bJohn Levon}
4151f5207bJohn Levon
4161f5207bJohn Levonstatic void array_check_data_info(struct expression *expr)
4171f5207bJohn Levon{
4181f5207bJohn Levon	struct expression *array;
4191f5207bJohn Levon	struct expression *offset;
4201f5207bJohn Levon	struct state_list *slist;
4211f5207bJohn Levon	struct sm_state *sm;
4221f5207bJohn Levon	struct compare_data *comp;
4231f5207bJohn Levon	char *offset_name;
4241f5207bJohn Levon	const char *equal_name = NULL;
4251f5207bJohn Levon
4261f5207bJohn Levon	expr = strip_expr(expr);
4271f5207bJohn Levon	if (!is_array(expr))
4281f5207bJohn Levon		return;
4291f5207bJohn Levon
4301f5207bJohn Levon	if (known_access_ok_numbers(expr))
4311f5207bJohn Levon		return;
432efe51d0John Levon	if (buf_comparison_index_ok(expr))
4331f5207bJohn Levon		return;
4341f5207bJohn Levon
4351f5207bJohn Levon	array = get_array_base(expr);
4361f5207bJohn Levon	offset = get_array_offset(expr);
4371f5207bJohn Levon	offset_name = expr_to_var(offset);
4381f5207bJohn Levon	if (!offset_name)
4391f5207bJohn Levon		return;
4401f5207bJohn Levon	slist = get_all_possible_equal_comparisons(offset);
4411f5207bJohn Levon	if (!slist)
4421f5207bJohn Levon		goto free;
4431f5207bJohn Levon
4441f5207bJohn Levon	FOR_EACH_PTR(slist, sm) {
4451f5207bJohn Levon		comp = sm->state->data;
4461f5207bJohn Levon		if (strcmp(comp->left_var, offset_name) == 0) {
4471f5207bJohn Levon			if (db_var_is_array_limit(array, comp->right_var, comp->right_vsl)) {
4481f5207bJohn Levon				equal_name = comp->right_var;
4491f5207bJohn Levon				break;
4501f5207bJohn Levon			}
4511f5207bJohn Levon		} else if (strcmp(comp->right_var, offset_name) == 0) {
4521f5207bJohn Levon			if (db_var_is_array_limit(array, comp->left_var, comp->left_vsl)) {
4531f5207bJohn Levon				equal_name = comp->left_var;
4541f5207bJohn Levon				break;
4551f5207bJohn Levon			}
4561f5207bJohn Levon		}
4571f5207bJohn Levon	} END_FOR_EACH_PTR(sm);
4581f5207bJohn Levon
4591f5207bJohn Levon	if (equal_name) {
4601f5207bJohn Levon		char *array_name = expr_to_str(array);
4611f5207bJohn Levon
4621f5207bJohn Levon		sm_warning("potential off by one '%s[]' limit '%s'", array_name, equal_name);
4631f5207bJohn Levon		free_string(array_name);
4641f5207bJohn Levon	}
4651f5207bJohn Levon
4661f5207bJohn Levonfree:
4671f5207bJohn Levon	free_slist(&slist);
4681f5207bJohn Levon	free_string(offset_name);
4691f5207bJohn Levon}
4701f5207bJohn Levon
4711f5207bJohn Levonstatic void add_allocation_function(const char *func, void *call_back, int param)
4721f5207bJohn Levon{
4731f5207bJohn Levon	add_function_assign_hook(func, call_back, INT_PTR(param));
4741f5207bJohn Levon}
4751f5207bJohn Levon
476efe51d0John Levonstatic int is_sizeof(struct expression *expr)
4771f5207bJohn Levon{
478efe51d0John Levon	const char *name;
479efe51d0John Levon
480efe51d0John Levon	if (expr->type == EXPR_SIZEOF)
481efe51d0John Levon		return 1;
482efe51d0John Levon	name = pos_ident(expr->pos);
483efe51d0John Levon	if (name && strcmp(name, "sizeof") == 0)
484efe51d0John Levon		return 1;
485efe51d0John Levon	return 0;
486efe51d0John Levon}
487efe51d0John Levon
488efe51d0John Levonstatic int match_size_binop(struct expression *size, struct expression *expr, int *limit_type)
489efe51d0John Levon{
490efe51d0John Levon	int orig_type = *limit_type;
491efe51d0John Levon	struct expression *left;
492efe51d0John Levon	sval_t sval;
493efe51d0John Levon
494efe51d0John Levon	left = expr->left;
495efe51d0John Levon	if (!expr_equiv(size, left))
496efe51d0John Levon		return 0;
497efe51d0John Levon
498efe51d0John Levon	if (expr->op == '-' &&
499efe51d0John Levon	    get_value(expr->right, &sval) &&
500efe51d0John Levon	    sval.value == 1 &&
501efe51d0John Levon	    orig_type == ELEM_COUNT) {
502efe51d0John Levon		*limit_type = ELEM_LAST;
503efe51d0John Levon		return 1;
504efe51d0John Levon	}
505efe51d0John Levon
506efe51d0John Levon	if (expr->op == '+' &&
507efe51d0John Levon	    get_value(expr->right, &sval) &&
508efe51d0John Levon	    sval.value == 1 &&
509efe51d0John Levon	    orig_type == ELEM_LAST) {
510efe51d0John Levon		*limit_type = ELEM_COUNT;
511efe51d0John Levon		return 1;
512efe51d0John Levon	}
513efe51d0John Levon
514efe51d0John Levon	if (expr->op == '*' &&
515efe51d0John Levon	    is_sizeof(expr->right) &&
516efe51d0John Levon	    orig_type == ELEM_COUNT) {
517efe51d0John Levon		*limit_type = BYTE_COUNT;
518efe51d0John Levon		return 1;
519efe51d0John Levon	}
520efe51d0John Levon
521efe51d0John Levon	if (expr->op == '/' &&
522efe51d0John Levon	    is_sizeof(expr->right) &&
523efe51d0John Levon	    orig_type == BYTE_COUNT) {
524efe51d0John Levon		*limit_type = ELEM_COUNT;
525efe51d0John Levon		return 1;
526efe51d0John Levon	}
527efe51d0John Levon
528efe51d0John Levon	return 0;
529efe51d0John Levon}
530efe51d0John Levon
531efe51d0John Levonstatic char *buf_size_param_comparison(struct expression *array, struct expression_list *args, int *limit_type)
532efe51d0John Levon{
533efe51d0John Levon	struct expression *tmp, *arg;
5341f5207bJohn Levon	struct expression *size;
5351f5207bJohn Levon	static char buf[32];
5361f5207bJohn Levon	int i;
5371f5207bJohn Levon
538efe51d0John Levon	size = get_size_variable(array, limit_type);
5391f5207bJohn Levon	if (!size)
5401f5207bJohn Levon		return NULL;
5411f5207bJohn Levon
542efe51d0John Levon	if (*limit_type == USED_LAST)
543efe51d0John Levon		*limit_type = ELEM_LAST;
544efe51d0John Levon	if (*limit_type == USED_COUNT)
545efe51d0John Levon		*limit_type = ELEM_COUNT;
546efe51d0John Levon
5471f5207bJohn Levon	i = -1;
548efe51d0John Levon	FOR_EACH_PTR(args, tmp) {
5491f5207bJohn Levon		i++;
550efe51d0John Levon		arg = tmp;
5511f5207bJohn Levon		if (arg == array)
5521f5207bJohn Levon			continue;
553efe51d0John Levon		if (expr_equiv(arg, size) ||
554efe51d0John Levon		    (arg->type == EXPR_BINOP &&
555efe51d0John Levon		     match_size_binop(size, arg, limit_type))) {
556efe51d0John Levon			snprintf(buf, sizeof(buf), "==$%d", i);
557efe51d0John Levon			return buf;
558efe51d0John Levon		}
559efe51d0John Levon	} END_FOR_EACH_PTR(tmp);
5601f5207bJohn Levon
5611f5207bJohn Levon	return NULL;
5621f5207bJohn Levon}
5631f5207bJohn Levon
5641f5207bJohn Levonstatic void match_call(struct expression *call)
5651f5207bJohn Levon{
5661f5207bJohn Levon	struct expression *arg;
5671f5207bJohn Levon	char *compare;
5681f5207bJohn Levon	int param;
569efe51d0John Levon	char buf[5];
570efe51d0John Levon	int limit_type;
5711f5207bJohn Levon
5721f5207bJohn Levon	param = -1;
5731f5207bJohn Levon	FOR_EACH_PTR(call->args, arg) {
5741f5207bJohn Levon		param++;
5751f5207bJohn Levon		if (!is_pointer(arg))
5761f5207bJohn Levon			continue;
577efe51d0John Levon		compare = buf_size_param_comparison(arg, call->args, &limit_type);
5781f5207bJohn Levon		if (!compare)
5791f5207bJohn Levon			continue;
580efe51d0John Levon		snprintf(buf, sizeof(buf), "%d", limit_type);
581efe51d0John Levon		sql_insert_caller_info(call, limit_type, param, compare, buf);
5821f5207bJohn Levon	} END_FOR_EACH_PTR(arg);
5831f5207bJohn Levon}
5841f5207bJohn Levon
5851f5207bJohn Levonstatic int get_param(int param, char **name, struct symbol **sym)
5861f5207bJohn Levon{
5871f5207bJohn Levon	struct symbol *arg;
5881f5207bJohn Levon	int i;
5891f5207bJohn Levon
5901f5207bJohn Levon	i = 0;
5911f5207bJohn Levon	FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
5921f5207bJohn Levon		/*
5931f5207bJohn Levon		 * this is a temporary hack to work around a bug (I think in sparse?)
5941f5207bJohn Levon		 * 2.6.37-rc1:fs/reiserfs/journal.o
5951f5207bJohn Levon		 * If there is a function definition without parameter name found
5961f5207bJohn Levon		 * after a function implementation then it causes a crash.
5971f5207bJohn Levon		 * int foo() {}
5981f5207bJohn Levon		 * int bar(char *);
5991f5207bJohn Levon		 */
6001f5207bJohn Levon		if (arg->ident->name < (char *)100)
6011f5207bJohn Levon			continue;
6021f5207bJohn Levon		if (i == param) {
6031f5207bJohn Levon			*name = arg->ident->name;
6041f5207bJohn Levon			*sym = arg;
6051f5207bJohn Levon			return TRUE;
6061f5207bJohn Levon		}
6071f5207bJohn Levon		i++;
6081f5207bJohn Levon	} END_FOR_EACH_PTR(arg);
6091f5207bJohn Levon
6101f5207bJohn Levon	return FALSE;
6111f5207bJohn Levon}
6121f5207bJohn Levon
6131f5207bJohn Levonstatic void set_param_compare(const char *array_name, struct symbol *array_sym, char *key, char *value)
6141f5207bJohn Levon{
6151f5207bJohn Levon	struct expression *array_expr;
6161f5207bJohn Levon	struct expression *size_expr;
6171f5207bJohn Levon	struct symbol *size_sym;
6181f5207bJohn Levon	char *size_name;
6191f5207bJohn Levon	long param;
6201f5207bJohn Levon	struct sm_state *tmp;
621efe51d0John Levon	int limit_type;
6221f5207bJohn Levon
623efe51d0John Levon	if (strncmp(key, "==$", 3) != 0)
6241f5207bJohn Levon		return;
625efe51d0John Levon	param = strtol(key + 3, NULL, 10);
6261f5207bJohn Levon	if (!get_param(param, &size_name, &size_sym))
6271f5207bJohn Levon		return;
6281f5207bJohn Levon	array_expr = symbol_expression(array_sym);
6291f5207bJohn Levon	size_expr = symbol_expression(size_sym);
630efe51d0John Levon	limit_type = strtol(value, NULL, 10);
6311f5207bJohn Levon
632efe51d0John Levon	tmp = set_state_expr(size_id, array_expr, alloc_compare_size(limit_type, size_expr));
6331f5207bJohn Levon	if (!tmp)
6341f5207bJohn Levon		return;
635efe51d0John Levon	set_state_expr(link_id, size_expr, alloc_state_expr(array_expr));
6361f5207bJohn Levon}
6371f5207bJohn Levon
638efe51d0John Levonstatic void set_implied(struct expression *call, struct expression *array_expr, char *key, char *value)
6391f5207bJohn Levon{
6401f5207bJohn Levon	struct expression *size_expr;
6411f5207bJohn Levon	struct symbol *size_sym;
6421f5207bJohn Levon	char *size_name;
6431f5207bJohn Levon	long param;
6441f5207bJohn Levon	struct sm_state *tmp;
645efe51d0John Levon	int limit_type;
6461f5207bJohn Levon
647efe51d0John Levon	if (strncmp(key, "==$", 3) != 0)
648efe51d0John Levon		return;
649efe51d0John Levon	param = strtol(key + 3, NULL, 10);
6501f5207bJohn Levon	if (!get_param(param, &size_name, &size_sym))
6511f5207bJohn Levon		return;
6521f5207bJohn Levon	size_expr = symbol_expression(size_sym);
6531f5207bJohn Levon
654efe51d0John Levon	limit_type = strtol(value, NULL, 10);
655efe51d0John Levon	tmp = set_state_expr(size_id, array_expr, alloc_compare_size(limit_type, size_expr));
6561f5207bJohn Levon	if (!tmp)
6571f5207bJohn Levon		return;
658efe51d0John Levon	set_state_expr(link_id, size_expr, alloc_state_expr(array_expr));
6591f5207bJohn Levon}
6601f5207bJohn Levon
6611f5207bJohn Levonstatic void munge_start_states(struct statement *stmt)
6621f5207bJohn Levon{
6631f5207bJohn Levon	struct state_list *slist = NULL;
6641f5207bJohn Levon	struct sm_state *sm;
6651f5207bJohn Levon	struct sm_state *poss;
6661f5207bJohn Levon
6671f5207bJohn Levon	FOR_EACH_MY_SM(size_id, __get_cur_stree(), sm) {
6681f5207bJohn Levon		if (sm->state != &merged)
6691f5207bJohn Levon			continue;
6701f5207bJohn Levon		/*
6711f5207bJohn Levon		 * screw it.  let's just assume that if one caller passes the
6721f5207bJohn Levon		 * size then they all do.
6731f5207bJohn Levon		 */
6741f5207bJohn Levon		FOR_EACH_PTR(sm->possible, poss) {
6751f5207bJohn Levon			if (poss->state != &merged &&
6761f5207bJohn Levon			    poss->state != &undefined) {
6771f5207bJohn Levon				add_ptr_list(&slist, poss);
6781f5207bJohn Levon				break;
6791f5207bJohn Levon			}
6801f5207bJohn Levon		} END_FOR_EACH_PTR(poss);
6811f5207bJohn Levon	} END_FOR_EACH_SM(sm);
6821f5207bJohn Levon
6831f5207bJohn Levon	FOR_EACH_PTR(slist, sm) {
6841f5207bJohn Levon		set_state(size_id, sm->name, sm->sym, sm->state);
6851f5207bJohn Levon	} END_FOR_EACH_PTR(sm);
6861f5207bJohn Levon
6871f5207bJohn Levon	free_slist(&slist);
6881f5207bJohn Levon}
6891f5207bJohn Levon
690efe51d0John Levonstatic void set_used(struct expression *expr)
691efe51d0John Levon{
692efe51d0John Levon	struct expression *parent;
693efe51d0John Levon	struct expression *array;
694efe51d0John Levon	struct expression *offset;
695efe51d0John Levon	struct sm_state *tmp;
696efe51d0John Levon	int limit_type;
697efe51d0John Levon
698efe51d0John Levon	if (expr->op != SPECIAL_INCREMENT)
699efe51d0John Levon		return;
700efe51d0John Levon
701efe51d0John Levon	limit_type = USED_LAST;
702efe51d0John Levon	if (expr->type == EXPR_POSTOP)
703efe51d0John Levon		limit_type = USED_COUNT;
704efe51d0John Levon
705efe51d0John Levon	parent = expr_get_parent_expr(expr);
706efe51d0John Levon	if (!parent || parent->type != EXPR_BINOP)
707efe51d0John Levon		return;
708efe51d0John Levon	parent = expr_get_parent_expr(parent);
709efe51d0John Levon	if (!parent || !is_array(parent))
710efe51d0John Levon		return;
711efe51d0John Levon
712efe51d0John Levon	array = get_array_base(parent);
713efe51d0John Levon	offset = get_array_offset(parent);
714efe51d0John Levon	if (offset != expr)
715efe51d0John Levon		return;
716efe51d0John Levon
717efe51d0John Levon	tmp = set_state_expr(size_id, array, alloc_compare_size(limit_type, offset->unop));
718efe51d0John Levon	if (!tmp)
719efe51d0John Levon		return;
720efe51d0John Levon	set_state_expr(link_id, offset->unop, alloc_state_expr(array));
721efe51d0John Levon}
722efe51d0John Levon
723efe51d0John Levonstatic int match_assign_array(struct expression *expr)
724efe51d0John Levon{
725efe51d0John Levon	// FIXME: implement
726efe51d0John Levon	return 0;
727efe51d0John Levon}
728efe51d0John Levon
729efe51d0John Levonstatic int match_assign_size(struct expression *expr)
730efe51d0John Levon{
731efe51d0John Levon	struct expression *right, *size, *array;
732efe51d0John Levon	struct smatch_state *state;
733efe51d0John Levon	struct sm_state *tmp;
734efe51d0John Levon	int limit_type;
735efe51d0John Levon
736efe51d0John Levon	right = expr->right;
737efe51d0John Levon	size = right;
738efe51d0John Levon	if (size->type == EXPR_BINOP)
739efe51d0John Levon		size = size->left;
740efe51d0John Levon
741efe51d0John Levon	array = get_array_variable(size);
742efe51d0John Levon	if (!array)
743efe51d0John Levon		return 0;
744efe51d0John Levon	state = get_state_expr(size_id, array);
745efe51d0John Levon	if (!state || !state->data)
746efe51d0John Levon		return 0;
747efe51d0John Levon
748efe51d0John Levon	limit_type = state_to_limit(state);
749efe51d0John Levon	if (limit_type < 0)
750efe51d0John Levon		return 0;
751efe51d0John Levon
752efe51d0John Levon	if (right->type == EXPR_BINOP && !match_size_binop(size, right, &limit_type))
753efe51d0John Levon		return 0;
754efe51d0John Levon
755efe51d0John Levon	tmp = set_state_expr(size_id, array, alloc_compare_size(limit_type, expr->left));
756efe51d0John Levon	if (!tmp)
757efe51d0John Levon		return 0;
758efe51d0John Levon	set_state_expr(link_id, expr->left, alloc_state_expr(array));
759efe51d0John Levon	return 1;
760efe51d0John Levon}
761efe51d0John Levon
762efe51d0John Levonstatic void match_assign(struct expression *expr)
763efe51d0John Levon{
764efe51d0John Levon	if (expr->op != '=')
765efe51d0John Levon		return;
766efe51d0John Levon
767efe51d0John Levon	if (match_assign_array(expr))
768efe51d0John Levon		return;
769efe51d0John Levon	match_assign_size(expr);
770efe51d0John Levon}
771efe51d0John Levon
772efe51d0John Levonstatic void match_copy(const char *fn, struct expression *expr, void *unused)
773efe51d0John Levon{
774efe51d0John Levon	struct expression *src, *size;
775efe51d0John Levon	int src_param, size_param;
776efe51d0John Levon
777efe51d0John Levon	src = get_argument_from_call_expr(expr->args, 1);
778efe51d0John Levon	size = get_argument_from_call_expr(expr->args, 2);
779efe51d0John Levon	src = strip_expr(src);
780efe51d0John Levon	size = strip_expr(size);
781efe51d0John Levon	if (!src || !size)
782efe51d0John Levon		return;
783efe51d0John Levon	if (src->type != EXPR_SYMBOL || size->type != EXPR_SYMBOL)
784efe51d0John Levon		return;
785efe51d0John Levon
786efe51d0John Levon	src_param = get_param_num_from_sym(src->symbol);
787efe51d0John Levon	size_param = get_param_num_from_sym(size->symbol);
788efe51d0John Levon	if (src_param < 0 || size_param < 0)
789efe51d0John Levon		return;
790efe51d0John Levon
791efe51d0John Levon	sql_insert_cache(call_implies, "'%s', '%s', 0, %d, %d, %d, '==$%d', '%d'",
792efe51d0John Levon			 get_base_file(), get_function(), fn_static(),
793efe51d0John Levon			 BYTE_COUNT, src_param, size_param, BYTE_COUNT);
794efe51d0John Levon}
795efe51d0John Levon
7961f5207bJohn Levonvoid register_buf_comparison(int id)
7971f5207bJohn Levon{
798efe51d0John Levon	int i;
799efe51d0John Levon
8001f5207bJohn Levon	size_id = id;
8011f5207bJohn Levon
802efe51d0John Levon	set_dynamic_states(size_id);
803efe51d0John Levon
8041f5207bJohn Levon	add_unmatched_state_hook(size_id, &unmatched_state);
8051f5207bJohn Levon
8061f5207bJohn Levon	add_allocation_function("malloc", &match_alloc, 0);
8071f5207bJohn Levon	add_allocation_function("memdup", &match_alloc, 1);
8081f5207bJohn Levon	add_allocation_function("realloc", &match_alloc, 1);
8091f5207bJohn Levon	if (option_project == PROJ_KERNEL) {
8101f5207bJohn Levon		add_allocation_function("kmalloc", &match_alloc, 0);
8111f5207bJohn Levon		add_allocation_function("kzalloc", &match_alloc, 0);
8121f5207bJohn Levon		add_allocation_function("vmalloc", &match_alloc, 0);
8131f5207bJohn Levon		add_allocation_function("__vmalloc", &match_alloc, 0);
8141f5207bJohn Levon		add_allocation_function("sock_kmalloc", &match_alloc, 1);
8151f5207bJohn Levon		add_allocation_function("kmemdup", &match_alloc, 1);
8161f5207bJohn Levon		add_allocation_function("kmemdup_user", &match_alloc, 1);
8171f5207bJohn Levon		add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
8181f5207bJohn Levon		add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
8191f5207bJohn Levon		add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
8201f5207bJohn Levon		add_allocation_function("devm_kmalloc", &match_alloc, 1);
8211f5207bJohn Levon		add_allocation_function("devm_kzalloc", &match_alloc, 1);
8221f5207bJohn Levon		add_allocation_function("kcalloc", &match_calloc, 0);
8231f5207bJohn Levon		add_allocation_function("devm_kcalloc", &match_calloc, 1);
8241f5207bJohn Levon		add_allocation_function("kmalloc_array", &match_calloc, 0);
8251f5207bJohn Levon		add_allocation_function("krealloc", &match_alloc, 1);
826efe51d0John Levon
827efe51d0John Levon		add_function_hook("copy_from_user", &match_copy, NULL);
828efe51d0John Levon		add_function_hook("__copy_from_user", &match_copy, NULL);
8291f5207bJohn Levon	}
8301f5207bJohn Levon
8311f5207bJohn Levon	add_hook(&array_check, OP_HOOK);
8321f5207bJohn Levon	add_hook(&array_check_data_info, OP_HOOK);
833efe51d0John Levon	add_hook(&set_used, OP_HOOK);
8341f5207bJohn Levon
8351f5207bJohn Levon	add_hook(&match_call, FUNCTION_CALL_HOOK);
8361f5207bJohn Levon	add_hook(&munge_start_states, AFTER_DEF_HOOK);
837efe51d0John Levon
838efe51d0John Levon	add_hook(&match_assign, ASSIGNMENT_HOOK);
839efe51d0John Levon
840efe51d0John Levon	for (i = BYTE_COUNT; i <= USED_COUNT; i++) {
841efe51d0John Levon		select_call_implies_hook(i, &set_implied);
842efe51d0John Levon		select_caller_info_hook(set_param_compare, i);
843efe51d0John Levon		select_return_implies_hook(i, &set_implied);
844efe51d0John Levon	}
8451f5207bJohn Levon}
8461f5207bJohn Levon
8471f5207bJohn Levonvoid register_buf_comparison_links(int id)
8481f5207bJohn Levon{
8491f5207bJohn Levon	link_id = id;
850efe51d0John Levon	set_dynamic_states(link_id);
8511f5207bJohn Levon	add_merge_hook(link_id, &merge_links);
8521f5207bJohn Levon	add_modification_hook(link_id, &match_link_modify);
8531f5207bJohn Levon}