1/*
2 * Copyright (C) 2017 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 "smatch.h"
19#include "smatch_extra.h"
20
21static int my_id;
22
23struct allocator {
24	const char *func;
25	int param;
26	int param2;
27};
28
29static struct allocator generic_allocator_table[] = {
30	{"malloc", 0},
31	{"memdup", 1},
32	{"realloc", 1},
33};
34
35static struct allocator kernel_allocator_table[] = {
36	{"kmalloc", 0},
37	{"kzalloc", 0},
38	{"vmalloc", 0},
39	{"__vmalloc", 0},
40	{"vzalloc", 0},
41	{"sock_kmalloc", 1},
42	{"kmemdup", 1},
43	{"kmemdup_user", 1},
44	{"dma_alloc_attrs", 1},
45	{"pci_alloc_consistent", 1},
46	{"pci_alloc_coherent", 1},
47	{"devm_kmalloc", 1},
48	{"devm_kzalloc", 1},
49	{"krealloc", 1},
50};
51
52static struct allocator calloc_table[] = {
53	{"calloc", 0, 1},
54	{"kcalloc", 0, 1},
55	{"kmalloc_array", 0, 1},
56	{"devm_kcalloc", 1, 2},
57};
58
59static int bytes_per_element(struct expression *expr)
60{
61	struct symbol *type;
62
63	type = get_type(expr);
64	if (!type)
65		return 0;
66
67	if (type->type != SYM_PTR && type->type != SYM_ARRAY)
68		return 0;
69
70	type = get_base_type(type);
71	return type_bytes(type);
72}
73
74static void save_constraint_required(struct expression *pointer, int op, struct expression *constraint)
75{
76	char *data, *limit;
77
78	data = get_constraint_str(pointer);
79	if (!data)
80		return;
81
82	limit = get_constraint_str(constraint);
83	if (!limit) {
84		// FIXME deal with <= also
85		if (op == '<')
86			set_state_expr(my_id, constraint, alloc_state_expr(pointer));
87		goto free_data;
88	}
89
90	sql_save_constraint_required(data, op, limit);
91
92	free_string(limit);
93free_data:
94	free_string(data);
95}
96
97static int handle_zero_size_arrays(struct expression *pointer, struct expression *size)
98{
99	struct expression *left, *right;
100	struct symbol *type, *array, *array_type;
101	sval_t struct_size;
102	char *limit;
103	char data[128];
104
105	if (size->type != EXPR_BINOP || size->op != '+')
106		return 0;
107
108	type = get_type(pointer);
109	if (!type || type->type != SYM_PTR)
110		return 0;
111	type = get_real_base_type(type);
112	if (!type || !type->ident || type->type != SYM_STRUCT)
113		return 0;
114	if (!last_member_is_resizable(type))
115		return 0;
116	array = last_ptr_list((struct ptr_list *)type->symbol_list);
117	if (!array || !array->ident)
118		return 0;
119	array_type = get_real_base_type(array);
120	if (!array_type || array_type->type != SYM_ARRAY)
121		return 0;
122	array_type = get_real_base_type(array_type);
123
124	left = strip_expr(size->left);
125	right = strip_expr(size->right);
126
127	if (!get_implied_value(left, &struct_size))
128		return 0;
129	if (struct_size.value != type_bytes(type))
130		return 0;
131
132	if (right->type == EXPR_BINOP && right->op == '*') {
133		struct expression *mult_left, *mult_right;
134		sval_t sval;
135
136		mult_left = strip_expr(right->left);
137		mult_right = strip_expr(right->right);
138
139		if (get_implied_value(mult_left, &sval) &&
140		    sval.value == type_bytes(array_type))
141			size = mult_right;
142		else if (get_implied_value(mult_right, &sval) &&
143		    sval.value == type_bytes(array_type))
144			size = mult_left;
145		else
146			return 0;
147	}
148
149	snprintf(data, sizeof(data), "(struct %s)->%s", type->ident->name, array->ident->name);
150	limit = get_constraint_str(size);
151	if (!limit) {
152		set_state_expr(my_id, size, alloc_state_expr(
153			       member_expression(deref_expression(pointer), '*', array->ident)));
154		return 1;
155	}
156
157	sql_save_constraint_required(data, '<', limit);
158
159	free_string(limit);
160	return 1;
161}
162
163static void match_alloc_helper(struct expression *pointer, struct expression *size, int recurse)
164{
165	struct expression *size_orig, *tmp;
166	sval_t sval;
167	int cnt = 0;
168
169	pointer = strip_expr(pointer);
170	size = strip_expr(size);
171	if (!size || !pointer)
172		return;
173
174	size_orig = size;
175	if (recurse) {
176		while ((tmp = get_assigned_expr(size))) {
177			size = strip_expr(tmp);
178			if (cnt++ > 5)
179				break;
180		}
181		if (size != size_orig) {
182			match_alloc_helper(pointer, size, 0);
183			size = size_orig;
184		}
185	}
186
187	if (handle_zero_size_arrays(pointer, size))
188		return;
189
190	if (size->type == EXPR_BINOP && size->op == '*') {
191		struct expression *mult_left, *mult_right;
192
193		mult_left = strip_expr(size->left);
194		mult_right = strip_expr(size->right);
195
196		if (get_implied_value(mult_left, &sval) &&
197		    sval.value == bytes_per_element(pointer))
198			size = mult_right;
199		else if (get_implied_value(mult_right, &sval) &&
200		    sval.value == bytes_per_element(pointer))
201			size = mult_left;
202		else
203			return;
204	}
205
206	if (size->type == EXPR_BINOP && size->op == '+' &&
207	    get_implied_value(size->right, &sval) &&
208	    sval.value == 1)
209		save_constraint_required(pointer, SPECIAL_LTE, size->left);
210	else
211		save_constraint_required(pointer, '<', size);
212}
213
214static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
215{
216	int size_arg = PTR_INT(_size_arg);
217	struct expression *call, *arg;
218
219	call = strip_expr(expr->right);
220	arg = get_argument_from_call_expr(call->args, size_arg);
221
222	match_alloc_helper(expr->left, arg, 1);
223}
224
225static void match_calloc(const char *fn, struct expression *expr, void *_start_arg)
226{
227	struct expression *pointer, *call, *size;
228	struct expression *count = NULL;
229	int start_arg = PTR_INT(_start_arg);
230	sval_t sval;
231
232	pointer = strip_expr(expr->left);
233	call = strip_expr(expr->right);
234
235	size = get_argument_from_call_expr(call->args, start_arg);
236	if (get_implied_value(size, &sval) &&
237	    sval.value == bytes_per_element(pointer))
238		count = get_argument_from_call_expr(call->args, start_arg + 1);
239	else {
240		size = get_argument_from_call_expr(call->args, start_arg + 1);
241		if (get_implied_value(size, &sval) &&
242		    sval.value == bytes_per_element(pointer))
243			count = get_argument_from_call_expr(call->args, start_arg);
244	}
245
246	if (!count)
247		return;
248
249	save_constraint_required(pointer, '<', count);
250}
251
252static void add_allocation_function(const char *func, void *call_back, int param)
253{
254	add_function_assign_hook(func, call_back, INT_PTR(param));
255}
256
257static void match_assign_size(struct expression *expr)
258{
259	struct smatch_state *state;
260	char *data, *limit;
261
262	state = get_state_expr(my_id, expr->right);
263	if (!state || !state->data)
264		return;
265
266	data = get_constraint_str(state->data);
267	if (!data)
268		return;
269
270	limit = get_constraint_str(expr->left);
271	if (!limit)
272		goto free_data;
273
274	sql_save_constraint_required(data, '<', limit);
275
276	free_string(limit);
277free_data:
278	free_string(data);
279}
280
281static void match_assign_has_buf_comparison(struct expression *expr)
282{
283	struct expression *size;
284	int limit_type;
285
286	if (expr->op != '=')
287		return;
288	if (expr->right->type == EXPR_CALL)
289		return;
290	size = get_size_variable(expr->right, &limit_type);
291	if (!size)
292		return;
293	if (limit_type != ELEM_COUNT)
294		return;
295	match_alloc_helper(expr->left, size, 1);
296}
297
298static void match_assign_data(struct expression *expr)
299{
300	struct expression *right, *arg, *tmp;
301	int i;
302	int size_arg;
303	int size_arg2 = -1;
304
305	if (expr->op != '=')
306		return;
307
308	/* Direct calls are handled else where (for now at least) */
309	tmp = get_assigned_expr(expr->right);
310	if (!tmp)
311		return;
312
313	right = strip_expr(tmp);
314	if (right->type != EXPR_CALL)
315		return;
316
317	if (right->fn->type != EXPR_SYMBOL ||
318	    !right->fn->symbol ||
319	    !right->fn->symbol->ident)
320		return;
321
322	for (i = 0; i < ARRAY_SIZE(generic_allocator_table); i++) {
323		if (strcmp(right->fn->symbol->ident->name,
324			   generic_allocator_table[i].func) == 0) {
325			size_arg = generic_allocator_table[i].param;
326			goto found;
327		}
328	}
329
330	if (option_project != PROJ_KERNEL)
331		return;
332
333	for (i = 0; i < ARRAY_SIZE(kernel_allocator_table); i++) {
334		if (strcmp(right->fn->symbol->ident->name,
335			   kernel_allocator_table[i].func) == 0) {
336			size_arg = kernel_allocator_table[i].param;
337			goto found;
338		}
339	}
340
341	for (i = 0; i < ARRAY_SIZE(calloc_table); i++) {
342		if (strcmp(right->fn->symbol->ident->name,
343			   calloc_table[i].func) == 0) {
344			size_arg = calloc_table[i].param;
345			size_arg2 = calloc_table[i].param2;
346			goto found;
347		}
348	}
349
350	return;
351
352found:
353	arg = get_argument_from_call_expr(right->args, size_arg);
354	match_alloc_helper(expr->left, arg, 1);
355	if (size_arg2 == -1)
356		return;
357	arg = get_argument_from_call_expr(right->args, size_arg2);
358	match_alloc_helper(expr->left, arg, 1);
359}
360
361static void match_assign_ARRAY_SIZE(struct expression *expr)
362{
363	struct expression *array;
364	char *data, *limit;
365	const char *macro;
366
367	macro = get_macro_name(expr->right->pos);
368	if (!macro || strcmp(macro, "ARRAY_SIZE") != 0)
369		return;
370	array = strip_expr(expr->right);
371	if (array->type != EXPR_BINOP || array->op != '+')
372		return;
373	array = strip_expr(array->left);
374	if (array->type != EXPR_BINOP || array->op != '/')
375		return;
376	array = strip_expr(array->left);
377	if (array->type != EXPR_SIZEOF)
378		return;
379	array = strip_expr(array->cast_expression);
380	if (array->type != EXPR_PREOP || array->op != '*')
381		return;
382	array = strip_expr(array->unop);
383
384	data = get_constraint_str(array);
385	limit = get_constraint_str(expr->left);
386	if (!data || !limit)
387		goto free;
388
389	sql_save_constraint_required(data, '<', limit);
390
391free:
392	free_string(data);
393	free_string(limit);
394}
395
396static void match_assign_buf_comparison(struct expression *expr)
397{
398	struct expression *pointer;
399
400	if (expr->op != '=')
401		return;
402	pointer = get_array_variable(expr->right);
403	if (!pointer)
404		return;
405
406	match_alloc_helper(pointer, expr->right, 1);
407}
408
409static int constraint_found(void *_found, int argc, char **argv, char **azColName)
410{
411	int *found = _found;
412
413	*found = 1;
414	return 0;
415}
416
417static int has_constraint(struct expression *expr, const char *constraint)
418{
419	int found = 0;
420
421	if (get_state_expr(my_id, expr))
422		return 1;
423
424	run_sql(constraint_found, &found,
425		"select data from constraints_required where bound = '%q' limit 1",
426		escape_newlines(constraint));
427
428	return found;
429}
430
431static void match_assign_constraint(struct expression *expr)
432{
433	struct symbol *type;
434	char *left, *right;
435
436	if (expr->op != '=')
437		return;
438
439	type = get_type(expr->left);
440	if (!type || type->type != SYM_BASETYPE)
441		return;
442
443	left = get_constraint_str(expr->left);
444	if (!left)
445		return;
446	right = get_constraint_str(expr->right);
447	if (!right)
448		goto free;
449	if (!has_constraint(expr->right, right))
450		return;
451	sql_copy_constraint_required(left, right);
452free:
453	free_string(right);
454	free_string(left);
455}
456
457void register_constraints_required(int id)
458{
459	my_id = id;
460
461	set_dynamic_states(my_id);
462	add_hook(&match_assign_size, ASSIGNMENT_HOOK);
463	add_hook(&match_assign_data, ASSIGNMENT_HOOK);
464	add_hook(&match_assign_has_buf_comparison, ASSIGNMENT_HOOK);
465
466	add_hook(&match_assign_ARRAY_SIZE, ASSIGNMENT_HOOK);
467	add_hook(&match_assign_ARRAY_SIZE, GLOBAL_ASSIGNMENT_HOOK);
468	add_hook(&match_assign_buf_comparison, ASSIGNMENT_HOOK);
469	add_hook(&match_assign_constraint, ASSIGNMENT_HOOK);
470
471	add_allocation_function("malloc", &match_alloc, 0);
472	add_allocation_function("memdup", &match_alloc, 1);
473	add_allocation_function("realloc", &match_alloc, 1);
474	add_allocation_function("realloc", &match_calloc, 0);
475	if (option_project == PROJ_KERNEL) {
476		add_allocation_function("kmalloc", &match_alloc, 0);
477		add_allocation_function("kzalloc", &match_alloc, 0);
478		add_allocation_function("vmalloc", &match_alloc, 0);
479		add_allocation_function("__vmalloc", &match_alloc, 0);
480		add_allocation_function("vzalloc", &match_alloc, 0);
481		add_allocation_function("sock_kmalloc", &match_alloc, 1);
482		add_allocation_function("kmemdup", &match_alloc, 1);
483		add_allocation_function("kmemdup_user", &match_alloc, 1);
484		add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
485		add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
486		add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
487		add_allocation_function("devm_kmalloc", &match_alloc, 1);
488		add_allocation_function("devm_kzalloc", &match_alloc, 1);
489		add_allocation_function("kcalloc", &match_calloc, 0);
490		add_allocation_function("kmalloc_array", &match_calloc, 0);
491		add_allocation_function("devm_kcalloc", &match_calloc, 1);
492		add_allocation_function("krealloc", &match_alloc, 1);
493	}
494}
495