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
21 static int my_id;
22
23 struct allocator {
24 const char *func;
25 int param;
26 int param2;
27 };
28
29 static struct allocator generic_allocator_table[] = {
30 {"malloc", 0},
31 {"memdup", 1},
32 {"realloc", 1},
33 };
34
35 static 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
52 static struct allocator calloc_table[] = {
53 {"calloc", 0, 1},
54 {"kcalloc", 0, 1},
55 {"kmalloc_array", 0, 1},
56 {"devm_kcalloc", 1, 2},
57 };
58
59 static 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
74 static 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);
93 free_data:
94 free_string(data);
95 }
96
97 static 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
163 static 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
214 static 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
225 static 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
252 static 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
257 static 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);
277 free_data:
278 free_string(data);
279 }
280
281 static 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
298 static 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
352 found:
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
361 static 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
391 free:
392 free_string(data);
393 free_string(limit);
394 }
395
396 static 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
409 static 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
417 static 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
431 static 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);
452 free:
453 free_string(right);
454 free_string(left);
455 }
456
457 void 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 }