11f5207b7SJohn Levon /*
21f5207b7SJohn Levon  * Copyright (C) 2013 Oracle.
31f5207b7SJohn Levon  *
41f5207b7SJohn Levon  * This program is free software; you can redistribute it and/or
51f5207b7SJohn Levon  * modify it under the terms of the GNU General Public License
61f5207b7SJohn Levon  * as published by the Free Software Foundation; either version 2
71f5207b7SJohn Levon  * of the License, or (at your option) any later version.
81f5207b7SJohn Levon  *
91f5207b7SJohn Levon  * This program is distributed in the hope that it will be useful,
101f5207b7SJohn Levon  * but WITHOUT ANY WARRANTY; without even the implied warranty of
121f5207b7SJohn Levon  * GNU General Public License for more details.
131f5207b7SJohn Levon  *
141f5207b7SJohn Levon  * You should have received a copy of the GNU General Public License
151f5207b7SJohn Levon  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
161f5207b7SJohn Levon  */
171f5207b7SJohn Levon 
181f5207b7SJohn Levon #include <stdlib.h>
191f5207b7SJohn Levon #include <errno.h>
201f5207b7SJohn Levon #include "parse.h"
211f5207b7SJohn Levon #include "smatch.h"
221f5207b7SJohn Levon #include "smatch_slist.h"
231f5207b7SJohn Levon #include "smatch_extra.h"
241f5207b7SJohn Levon 
251f5207b7SJohn Levon #define UNKNOWN_SIZE (-1)
261f5207b7SJohn Levon 
271f5207b7SJohn Levon static int my_strlen_id;
281f5207b7SJohn Levon /*
291f5207b7SJohn Levon  * The trick with the my_equiv_id is that if we have:
301f5207b7SJohn Levon  * foo = strlen(bar);
311f5207b7SJohn Levon  * We don't know at that point what the strlen() is but we know it's equivalent
321f5207b7SJohn Levon  * to "foo" so maybe we can find the value of "foo" later.
331f5207b7SJohn Levon  */
341f5207b7SJohn Levon static int my_equiv_id;
351f5207b7SJohn Levon 
size_to_estate(int size)361f5207b7SJohn Levon static struct smatch_state *size_to_estate(int size)
371f5207b7SJohn Levon {
381f5207b7SJohn Levon 	sval_t sval;
391f5207b7SJohn Levon 
401f5207b7SJohn Levon 	sval.type = &int_ctype;
411f5207b7SJohn Levon 	sval.value = size;
421f5207b7SJohn Levon 
431f5207b7SJohn Levon 	return alloc_estate_sval(sval);
441f5207b7SJohn Levon }
451f5207b7SJohn Levon 
unmatched_strlen_state(struct sm_state * sm)461f5207b7SJohn Levon static struct smatch_state *unmatched_strlen_state(struct sm_state *sm)
471f5207b7SJohn Levon {
481f5207b7SJohn Levon 	return size_to_estate(UNKNOWN_SIZE);
491f5207b7SJohn Levon }
501f5207b7SJohn Levon 
set_strlen_undefined(struct sm_state * sm,struct expression * mod_expr)511f5207b7SJohn Levon static void set_strlen_undefined(struct sm_state *sm, struct expression *mod_expr)
521f5207b7SJohn Levon {
531f5207b7SJohn Levon 	set_state(sm->owner, sm->name, sm->sym, size_to_estate(UNKNOWN_SIZE));
541f5207b7SJohn Levon }
551f5207b7SJohn Levon 
set_strlen_equiv_undefined(struct sm_state * sm,struct expression * mod_expr)561f5207b7SJohn Levon static void set_strlen_equiv_undefined(struct sm_state *sm, struct expression *mod_expr)
571f5207b7SJohn Levon {
581f5207b7SJohn Levon 	set_state(sm->owner, sm->name, sm->sym, &undefined);
591f5207b7SJohn Levon }
601f5207b7SJohn Levon 
match_string_assignment(struct expression * expr)611f5207b7SJohn Levon static void match_string_assignment(struct expression *expr)
621f5207b7SJohn Levon {
631f5207b7SJohn Levon 	struct range_list *rl;
641f5207b7SJohn Levon 
651f5207b7SJohn Levon 	if (expr->op != '=')
661f5207b7SJohn Levon 		return;
671f5207b7SJohn Levon 	if (!get_implied_strlen(expr->right, &rl))
681f5207b7SJohn Levon 		return;
691f5207b7SJohn Levon 	set_state_expr(my_strlen_id, expr->left, alloc_estate_rl(clone_rl(rl)));
701f5207b7SJohn Levon }
711f5207b7SJohn Levon 
match_strlen(const char * fn,struct expression * expr,void * unused)721f5207b7SJohn Levon static void match_strlen(const char *fn, struct expression *expr, void *unused)
731f5207b7SJohn Levon {
741f5207b7SJohn Levon 	struct expression *right;
751f5207b7SJohn Levon 	struct expression *str;
761f5207b7SJohn Levon 	struct expression *len_expr;
771f5207b7SJohn Levon 	char *len_name;
781f5207b7SJohn Levon 	struct smatch_state *state;
791f5207b7SJohn Levon 
801f5207b7SJohn Levon 	right = strip_expr(expr->right);
811f5207b7SJohn Levon 	str = get_argument_from_call_expr(right->args, 0);
821f5207b7SJohn Levon 	len_expr = strip_expr(expr->left);
831f5207b7SJohn Levon 
841f5207b7SJohn Levon 	len_name = expr_to_var(len_expr);
851f5207b7SJohn Levon 	if (!len_name)
861f5207b7SJohn Levon 		return;
871f5207b7SJohn Levon 
881f5207b7SJohn Levon 	state = __alloc_smatch_state(0);
891f5207b7SJohn Levon         state->name = len_name;
901f5207b7SJohn Levon 	state->data = len_expr;
911f5207b7SJohn Levon 
921f5207b7SJohn Levon 	set_state_expr(my_equiv_id, str, state);
931f5207b7SJohn Levon }
941f5207b7SJohn Levon 
match_strlen_condition(struct expression * expr)951f5207b7SJohn Levon static void match_strlen_condition(struct expression *expr)
961f5207b7SJohn Levon {
971f5207b7SJohn Levon 	struct expression *left;
981f5207b7SJohn Levon 	struct expression *right;
991f5207b7SJohn Levon 	struct expression *str = NULL;
1001f5207b7SJohn Levon 	int strlen_left = 0;
1011f5207b7SJohn Levon 	int strlen_right = 0;
1021f5207b7SJohn Levon 	sval_t sval;
1031f5207b7SJohn Levon 	struct smatch_state *true_state = NULL;
1041f5207b7SJohn Levon 	struct smatch_state *false_state = NULL;
1051f5207b7SJohn Levon 	int op;
1061f5207b7SJohn Levon 
1071f5207b7SJohn Levon 	if (expr->type != EXPR_COMPARE)
1081f5207b7SJohn Levon 		return;
1091f5207b7SJohn Levon 
1101f5207b7SJohn Levon 	left = strip_expr(expr->left);
1111f5207b7SJohn Levon 	right = strip_expr(expr->right);
1121f5207b7SJohn Levon 
1131f5207b7SJohn Levon 	if (left->type == EXPR_CALL && sym_name_is("strlen", left->fn)) {
1141f5207b7SJohn Levon 		str = get_argument_from_call_expr(left->args, 0);
1151f5207b7SJohn Levon 		strlen_left = 1;
1161f5207b7SJohn Levon 	}
1171f5207b7SJohn Levon 	if (right->type == EXPR_CALL && sym_name_is("strlen", right->fn)) {
1181f5207b7SJohn Levon 		str = get_argument_from_call_expr(right->args, 0);
1191f5207b7SJohn Levon 		strlen_right = 1;
1201f5207b7SJohn Levon 	}
1211f5207b7SJohn Levon 
1221f5207b7SJohn Levon 	if (!strlen_left && !strlen_right)
1231f5207b7SJohn Levon 		return;
1241f5207b7SJohn Levon 	if (strlen_left && strlen_right)
1251f5207b7SJohn Levon 		return;
1261f5207b7SJohn Levon 
1271f5207b7SJohn Levon 	op = expr->op;
1281f5207b7SJohn Levon 	if (strlen_left) {
1291f5207b7SJohn Levon 		if (!get_value(right, &sval))
1301f5207b7SJohn Levon 			return;
1311f5207b7SJohn Levon 	} else {
1321f5207b7SJohn Levon 		op = flip_comparison(op);
1331f5207b7SJohn Levon 		if (!get_value(left, &sval))
1341f5207b7SJohn Levon 			return;
1351f5207b7SJohn Levon 	}
1361f5207b7SJohn Levon 
1371f5207b7SJohn Levon 	switch (op) {
1381f5207b7SJohn Levon 	case '<':
1391f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_LT:
1401f5207b7SJohn Levon 		true_state = size_to_estate(sval.value - 1);
1411f5207b7SJohn Levon 		break;
1421f5207b7SJohn Levon 	case SPECIAL_LTE:
1431f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_LTE:
1441f5207b7SJohn Levon 		true_state = size_to_estate(sval.value);
1451f5207b7SJohn Levon 		break;
1461f5207b7SJohn Levon 	case SPECIAL_EQUAL:
1471f5207b7SJohn Levon 		true_state = size_to_estate(sval.value);
1481f5207b7SJohn Levon 		break;
1491f5207b7SJohn Levon 	case SPECIAL_NOTEQUAL:
1501f5207b7SJohn Levon 		false_state = size_to_estate(sval.value);
1511f5207b7SJohn Levon 		break;
1521f5207b7SJohn Levon 	case SPECIAL_GTE:
1531f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_GTE:
1541f5207b7SJohn Levon 		false_state = size_to_estate(sval.value - 1);
1551f5207b7SJohn Levon 		break;
1561f5207b7SJohn Levon 	case '>':
1571f5207b7SJohn Levon 	case SPECIAL_UNSIGNED_GT:
1581f5207b7SJohn Levon 		false_state = size_to_estate(sval.value);
1591f5207b7SJohn Levon 		break;
1601f5207b7SJohn Levon 	}
1611f5207b7SJohn Levon 
1621f5207b7SJohn Levon 	set_true_false_states_expr(my_strlen_id, str, true_state, false_state);
1631f5207b7SJohn Levon }
1641f5207b7SJohn Levon 
match_snprintf(const char * fn,struct expression * expr,void * unused)1651f5207b7SJohn Levon static void match_snprintf(const char *fn, struct expression *expr, void *unused)
1661f5207b7SJohn Levon {
1671f5207b7SJohn Levon 	struct expression *dest;
1681f5207b7SJohn Levon 	struct expression *dest_size_expr;
1691f5207b7SJohn Levon 	sval_t limit_size;
1701f5207b7SJohn Levon 
1711f5207b7SJohn Levon 	dest = get_argument_from_call_expr(expr->args, 0);
1721f5207b7SJohn Levon 	dest_size_expr = get_argument_from_call_expr(expr->args, 1);
1731f5207b7SJohn Levon 
1741f5207b7SJohn Levon 	if (!get_implied_value(dest_size_expr, &limit_size))
1751f5207b7SJohn Levon 		return;
1761f5207b7SJohn Levon 
1771f5207b7SJohn Levon 	if (limit_size.value <= 0)
1781f5207b7SJohn Levon 		return;
1791f5207b7SJohn Levon 
1801f5207b7SJohn Levon 	set_state_expr(my_strlen_id, dest, size_to_estate(limit_size.value - 1));
1811f5207b7SJohn Levon }
1821f5207b7SJohn Levon 
match_strlcpycat(const char * fn,struct expression * expr,void * unused)1831f5207b7SJohn Levon static void match_strlcpycat(const char *fn, struct expression *expr, void *unused)
1841f5207b7SJohn Levon {
1851f5207b7SJohn Levon 	struct expression *dest;
1861f5207b7SJohn Levon 	struct expression *src;
1871f5207b7SJohn Levon 	struct expression *limit_expr;
1881f5207b7SJohn Levon 	int src_len;
1891f5207b7SJohn Levon 	sval_t limit;
1901f5207b7SJohn Levon 
1911f5207b7SJohn Levon 	dest = get_argument_from_call_expr(expr->args, 0);
1921f5207b7SJohn Levon 	src = get_argument_from_call_expr(expr->args, 1);
1931f5207b7SJohn Levon 	limit_expr = get_argument_from_call_expr(expr->args, 2);
1941f5207b7SJohn Levon 
1951f5207b7SJohn Levon 	src_len = get_size_from_strlen(src);
1961f5207b7SJohn Levon 
1971f5207b7SJohn Levon 	if (!get_implied_max(limit_expr, &limit))
1981f5207b7SJohn Levon 		return;
1991f5207b7SJohn Levon 	if (limit.value < 0 || limit.value > INT_MAX)
2001f5207b7SJohn Levon 		return;
2011f5207b7SJohn Levon 	if (src_len != 0 && strcmp(fn, "strcpy") == 0 && src_len < limit.value)
2021f5207b7SJohn Levon 		limit.value = src_len;
2031f5207b7SJohn Levon 
2041f5207b7SJohn Levon 	set_state_expr(my_strlen_id, dest, size_to_estate(limit.value - 1));
2051f5207b7SJohn Levon }
2061f5207b7SJohn Levon 
match_strcpy(const char * fn,struct expression * expr,void * unused)2071f5207b7SJohn Levon static void match_strcpy(const char *fn, struct expression *expr, void *unused)
2081f5207b7SJohn Levon {
2091f5207b7SJohn Levon 	struct expression *dest;
2101f5207b7SJohn Levon 	struct expression *src;
2111f5207b7SJohn Levon 	int src_len;
2121f5207b7SJohn Levon 
2131f5207b7SJohn Levon 	dest = get_argument_from_call_expr(expr->args, 0);
2141f5207b7SJohn Levon 	src = get_argument_from_call_expr(expr->args, 1);
2151f5207b7SJohn Levon 
2161f5207b7SJohn Levon 	src_len = get_size_from_strlen(src);
2171f5207b7SJohn Levon 	if (src_len == 0)
2181f5207b7SJohn Levon 		return;
2191f5207b7SJohn Levon 
2201f5207b7SJohn Levon 	set_state_expr(my_strlen_id, dest, size_to_estate(src_len - 1));
2211f5207b7SJohn Levon }
2221f5207b7SJohn Levon 
get_strlen_from_string(struct expression * expr,struct range_list ** rl)2231f5207b7SJohn Levon static int get_strlen_from_string(struct expression *expr, struct range_list **rl)
2241f5207b7SJohn Levon {
2251f5207b7SJohn Levon 	sval_t sval;
2261f5207b7SJohn Levon 	int len;
2271f5207b7SJohn Levon 
2281f5207b7SJohn Levon 	len = expr->string->length;
2291f5207b7SJohn Levon 	sval = sval_type_val(&int_ctype, len - 1);
2301f5207b7SJohn Levon 	*rl = alloc_rl(sval, sval);
2311f5207b7SJohn Levon 	return 1;
2321f5207b7SJohn Levon }
2331f5207b7SJohn Levon 
2341f5207b7SJohn Levon 
get_strlen_from_state(struct expression * expr,struct range_list ** rl)2351f5207b7SJohn Levon static int get_strlen_from_state(struct expression *expr, struct range_list **rl)
2361f5207b7SJohn Levon {
2371f5207b7SJohn Levon 	struct smatch_state *state;
2381f5207b7SJohn Levon 
2391f5207b7SJohn Levon 	state = get_state_expr(my_strlen_id, expr);
2401f5207b7SJohn Levon 	if (!state)
2411f5207b7SJohn Levon 		return 0;
2421f5207b7SJohn Levon 	*rl = estate_rl(state);
2431f5207b7SJohn Levon 	return 1;
2441f5207b7SJohn Levon }
2451f5207b7SJohn Levon 
get_strlen_from_equiv(struct expression * expr,struct range_list ** rl)2461f5207b7SJohn Levon static int get_strlen_from_equiv(struct expression *expr, struct range_list **rl)
2471f5207b7SJohn Levon {
2481f5207b7SJohn Levon 	struct smatch_state *state;
2491f5207b7SJohn Levon 
2501f5207b7SJohn Levon 	state = get_state_expr(my_equiv_id, expr);
2511f5207b7SJohn Levon 	if (!state || !state->data)
2521f5207b7SJohn Levon 		return 0;
2531f5207b7SJohn Levon 	if (!get_implied_rl((struct expression *)state->data, rl))
2541f5207b7SJohn Levon 		return 0;
2551f5207b7SJohn Levon 	return 1;
2561f5207b7SJohn Levon }
2571f5207b7SJohn Levon 
2581f5207b7SJohn Levon /*
2591f5207b7SJohn Levon  * This returns the strlen() without the NUL char.
2601f5207b7SJohn Levon  */
get_implied_strlen(struct expression * expr,struct range_list ** rl)2611f5207b7SJohn Levon int get_implied_strlen(struct expression *expr, struct range_list **rl)
2621f5207b7SJohn Levon {
2631f5207b7SJohn Levon 
2641f5207b7SJohn Levon 	*rl = NULL;
2651f5207b7SJohn Levon 
2661f5207b7SJohn Levon 	expr = strip_expr(expr);
2671f5207b7SJohn Levon 	if (expr->type == EXPR_STRING)
2681f5207b7SJohn Levon 		return get_strlen_from_string(expr, rl);
2691f5207b7SJohn Levon 
2701f5207b7SJohn Levon 	if (get_strlen_from_state(expr, rl))
2711f5207b7SJohn Levon 		return 1;
2721f5207b7SJohn Levon 	if (get_strlen_from_equiv(expr, rl))
2731f5207b7SJohn Levon 		return 1;
2741f5207b7SJohn Levon 	return 0;
2751f5207b7SJohn Levon }
2761f5207b7SJohn Levon 
get_size_from_strlen(struct expression * expr)2771f5207b7SJohn Levon int get_size_from_strlen(struct expression *expr)
2781f5207b7SJohn Levon {
2791f5207b7SJohn Levon 	struct range_list *rl;
2801f5207b7SJohn Levon 	sval_t max;
2811f5207b7SJohn Levon 
2821f5207b7SJohn Levon 	if (!get_implied_strlen(expr, &rl))
2831f5207b7SJohn Levon 		return 0;
2841f5207b7SJohn Levon 	max = rl_max(rl);
2851f5207b7SJohn Levon 	if (sval_is_negative(max) || sval_is_max(max))
2861f5207b7SJohn Levon 		return 0;
2871f5207b7SJohn Levon 
2881f5207b7SJohn Levon 	return max.value + 1; /* add one because strlen doesn't include the NULL */
2891f5207b7SJohn Levon }
2901f5207b7SJohn Levon 
set_param_strlen(const char * name,struct symbol * sym,char * key,char * value)2911f5207b7SJohn Levon void set_param_strlen(const char *name, struct symbol *sym, char *key, char *value)
2921f5207b7SJohn Levon {
2931f5207b7SJohn Levon 	struct range_list *rl = NULL;
2941f5207b7SJohn Levon 	struct smatch_state *state;
2951f5207b7SJohn Levon 	char fullname[256];
2961f5207b7SJohn Levon 
2971f5207b7SJohn Levon 	if (strncmp(key, "$", 1) != 0)
2981f5207b7SJohn Levon 		return;
2991f5207b7SJohn Levon 
3001f5207b7SJohn Levon 	snprintf(fullname, 256, "%s%s", name, key + 1);
3011f5207b7SJohn Levon 
3021f5207b7SJohn Levon 	str_to_rl(&int_ctype, value, &rl);
3031f5207b7SJohn Levon 	if (!rl || is_whole_rl(rl))
3041f5207b7SJohn Levon 		return;
3051f5207b7SJohn Levon 	state = alloc_estate_rl(rl);
3061f5207b7SJohn Levon 	set_state(my_strlen_id, fullname, sym, state);
3071f5207b7SJohn Levon }
3081f5207b7SJohn Levon 
match_call(struct expression * expr)3091f5207b7SJohn Levon static void match_call(struct expression *expr)
3101f5207b7SJohn Levon {
3111f5207b7SJohn Levon 	struct expression *arg;
3121f5207b7SJohn Levon 	struct range_list *rl;
3131f5207b7SJohn Levon 	int i;
3141f5207b7SJohn Levon 
3151f5207b7SJohn Levon 	i = 0;
3161f5207b7SJohn Levon 	FOR_EACH_PTR(expr->args, arg) {
3171f5207b7SJohn Levon 		if (!get_implied_strlen(arg, &rl))
3181f5207b7SJohn Levon 			continue;
3191f5207b7SJohn Levon 		if (!is_whole_rl(rl))
3201f5207b7SJohn Levon 			sql_insert_caller_info(expr, STR_LEN, i, "$", show_rl(rl));
3211f5207b7SJohn Levon 		i++;
3221f5207b7SJohn Levon 	} END_FOR_EACH_PTR(arg);
3231f5207b7SJohn Levon }
3241f5207b7SJohn Levon 
struct_member_callback(struct expression * call,int param,char * printed_name,struct sm_state * sm)3251f5207b7SJohn Levon static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
3261f5207b7SJohn Levon {
3271f5207b7SJohn Levon 	if (sm->state == &merged)
3281f5207b7SJohn Levon 		return;
3291f5207b7SJohn Levon 	sql_insert_caller_info(call, STR_LEN, param, printed_name, sm->state->name);
3301f5207b7SJohn Levon }
3311f5207b7SJohn Levon 
register_strlen(int id)3321f5207b7SJohn Levon void register_strlen(int id)
3331f5207b7SJohn Levon {
3341f5207b7SJohn Levon 	my_strlen_id = id;
3351f5207b7SJohn Levon 
336*efe51d0cSJohn Levon 	set_dynamic_states(my_strlen_id);
337*efe51d0cSJohn Levon 
3381f5207b7SJohn Levon 	add_unmatched_state_hook(my_strlen_id, &unmatched_strlen_state);
3391f5207b7SJohn Levon 
3401f5207b7SJohn Levon 	select_caller_info_hook(set_param_strlen, STR_LEN);
3411f5207b7SJohn Levon 	add_hook(&match_string_assignment, ASSIGNMENT_HOOK);
3421f5207b7SJohn Levon 
3431f5207b7SJohn Levon 	add_modification_hook(my_strlen_id, &set_strlen_undefined);
3441f5207b7SJohn Levon 	add_merge_hook(my_strlen_id, &merge_estates);
3451f5207b7SJohn Levon 	add_hook(&match_call, FUNCTION_CALL_HOOK);
3461f5207b7SJohn Levon 	add_member_info_callback(my_strlen_id, struct_member_callback);
3471f5207b7SJohn Levon 	add_hook(&match_strlen_condition, CONDITION_HOOK);
3481f5207b7SJohn Levon 
3491f5207b7SJohn Levon 	add_function_hook("snprintf", &match_snprintf, NULL);
3501f5207b7SJohn Levon 
3511f5207b7SJohn Levon 	add_function_hook("strlcpy", &match_strlcpycat, NULL);
3521f5207b7SJohn Levon 	add_function_hook("strlcat", &match_strlcpycat, NULL);
3531f5207b7SJohn Levon 	add_function_hook("strcpy", &match_strcpy, NULL);
3541f5207b7SJohn Levon }
3551f5207b7SJohn Levon 
register_strlen_equiv(int id)3561f5207b7SJohn Levon void register_strlen_equiv(int id)
3571f5207b7SJohn Levon {
3581f5207b7SJohn Levon 	my_equiv_id = id;
359*efe51d0cSJohn Levon 	set_dynamic_states(my_equiv_id);
3601f5207b7SJohn Levon 	add_function_assign_hook("strlen", &match_strlen, NULL);
3611f5207b7SJohn Levon 	add_modification_hook(my_equiv_id, &set_strlen_equiv_undefined);
3621f5207b7SJohn Levon }
3631f5207b7SJohn Levon