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 /*
19 * The point here is to store that a buffer has x bytes even if we don't know
20 * the value of x.
21 *
22 */
23
24 #include "smatch.h"
25 #include "smatch_extra.h"
26 #include "smatch_slist.h"
27
28 static int size_id;
29 static int link_id;
30
31 /*
32 * We need this for code which does:
33 *
34 * if (size)
35 * foo = malloc(size);
36 *
37 * We want to record that the size of "foo" is "size" even after the merge.
38 *
39 */
40 static struct smatch_state *unmatched_state(struct sm_state *sm)
41 {
42 struct expression *size_expr;
43 sval_t sval;
44
45 if (!sm->state->data)
46 return &undefined;
47 size_expr = sm->state->data;
48 if (!get_implied_value(size_expr, &sval) || sval.value != 0)
49 return &undefined;
50 return sm->state;
51 }
52
53 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
54 {
55 struct expression *expr1, *expr2;
56
57 expr1 = s1->data;
58 expr2 = s2->data;
59
60 if (expr1 && expr2 && expr_equiv(expr1, expr2))
61 return s1;
62 return &merged;
63 }
64
65 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr)
66 {
67 struct expression *expr;
68 struct sm_state *tmp;
69
70 expr = sm->state->data;
71 if (expr) {
72 set_state_expr(size_id, expr, &undefined);
73 set_state(link_id, sm->name, sm->sym, &undefined);
74 return;
75 }
76
77 FOR_EACH_PTR(sm->possible, tmp) {
78 expr = tmp->state->data;
79 if (expr)
80 set_state_expr(size_id, expr, &undefined);
81 } END_FOR_EACH_PTR(tmp);
82 set_state(link_id, sm->name, sm->sym, &undefined);
83 }
84
85 static struct smatch_state *alloc_expr_state(struct expression *expr)
86 {
87 struct smatch_state *state;
88 char *name;
89
90 state = __alloc_smatch_state(0);
91 expr = strip_expr(expr);
92 name = expr_to_str(expr);
93 state->name = alloc_sname(name);
94 free_string(name);
95 state->data = expr;
96 return state;
97 }
98
99 static int bytes_per_element(struct expression *expr)
100 {
101 struct symbol *type;
102
103 type = get_type(expr);
104 if (!type)
105 return 0;
106
107 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
108 return 0;
109
110 type = get_base_type(type);
111 return type_bytes(type);
112 }
113
114 static void db_save_type_links(struct expression *array, struct expression *size)
115 {
116 const char *array_name;
117
118 array_name = get_data_info_name(array);
119 if (!array_name)
120 array_name = "";
121 sql_insert_data_info(size, ARRAY_LEN, array_name);
122 }
123
124 static void match_alloc_helper(struct expression *pointer, struct expression *size)
125 {
126 struct expression *tmp;
127 struct sm_state *sm;
128 sval_t sval;
129 int cnt = 0;
130
131 pointer = strip_expr(pointer);
132 size = strip_expr(size);
133 if (!size || !pointer)
134 return;
135
136 while ((tmp = get_assigned_expr(size))) {
137 size = strip_expr(tmp);
138 if (cnt++ > 5)
139 break;
140 }
141
142 if (size->type == EXPR_BINOP && size->op == '*') {
143 struct expression *mult_left, *mult_right;
144
145 mult_left = strip_expr(size->left);
146 mult_right = strip_expr(size->right);
147
148 if (get_implied_value(mult_left, &sval) &&
149 sval.value == bytes_per_element(pointer))
150 size = mult_right;
151 else if (get_implied_value(mult_right, &sval) &&
152 sval.value == bytes_per_element(pointer))
153 size = mult_left;
154 else
155 return;
156 }
157
158 /* Only save links to variables, not fixed sizes */
159 if (get_value(size, &sval))
160 return;
161
162 db_save_type_links(pointer, size);
163 sm = set_state_expr(size_id, pointer, alloc_expr_state(size));
164 if (!sm)
165 return;
166 set_state_expr(link_id, size, alloc_expr_state(pointer));
167 }
168
169 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
170 {
171 int size_arg = PTR_INT(_size_arg);
172 struct expression *pointer, *call, *arg;
173
174 pointer = strip_expr(expr->left);
175 call = strip_expr(expr->right);
176 arg = get_argument_from_call_expr(call->args, size_arg);
177 match_alloc_helper(pointer, arg);
178 }
179
180 static void match_calloc(const char *fn, struct expression *expr, void *_start_arg)
181 {
182 int start_arg = PTR_INT(_start_arg);
183 struct expression *pointer, *call, *arg;
184 struct sm_state *tmp;
185 sval_t sval;
186
187 pointer = strip_expr(expr->left);
188 call = strip_expr(expr->right);
189 arg = get_argument_from_call_expr(call->args, start_arg);
190 if (get_implied_value(arg, &sval) &&
191 sval.value == bytes_per_element(pointer))
192 arg = get_argument_from_call_expr(call->args, start_arg + 1);
193
194 db_save_type_links(pointer, arg);
195 tmp = set_state_expr(size_id, pointer, alloc_expr_state(arg));
196 if (!tmp)
197 return;
198 set_state_expr(link_id, arg, alloc_expr_state(pointer));
199 }
200
201 struct expression *get_size_variable(struct expression *buf)
202 {
203 struct smatch_state *state;
204
205 state = get_state_expr(size_id, buf);
206 if (state)
207 return state->data;
208 return NULL;
209 }
210
211 struct expression *get_array_variable(struct expression *size)
212 {
213 struct smatch_state *state;
214
215 state = get_state_expr(link_id, size);
216 if (state)
217 return state->data;
218 return NULL;
219 }
220
221 static void array_check(struct expression *expr)
222 {
223 struct expression *array;
224 struct expression *size;
225 struct expression *offset;
226 char *array_str, *offset_str;
227
228 expr = strip_expr(expr);
229 if (!is_array(expr))
230 return;
231
232 array = get_array_base(expr);
233 size = get_size_variable(array);
234 if (!size)
235 return;
236 offset = get_array_offset(expr);
237 if (!possible_comparison(size, SPECIAL_EQUAL, offset))
238 return;
239
240 array_str = expr_to_str(array);
241 offset_str = expr_to_str(offset);
242 sm_warning("potentially one past the end of array '%s[%s]'", array_str, offset_str);
243 free_string(array_str);
244 free_string(offset_str);
245 }
246
247 struct db_info {
248 char *name;
249 int ret;
250 };
251
252 static int db_limitter_callback(void *_info, int argc, char **argv, char **azColName)
253 {
254 struct db_info *info = _info;
255
300 return alloc_sname(buf);
301 }
302
303 int db_var_is_array_limit(struct expression *array, const char *name, struct var_sym_list *vsl)
304 {
305 char *size_name;
306 char *array_name = get_data_info_name(array);
307 struct db_info db_info = {.name = array_name,};
308
309 size_name = vsl_to_data_info_name(name, vsl);
310 if (!size_name)
311 return 0;
312
313 run_sql(db_limitter_callback, &db_info,
314 "select value from data_info where type = %d and data = '%s';",
315 ARRAY_LEN, size_name);
316
317 return db_info.ret;
318 }
319
320 static int known_access_ok_comparison(struct expression *expr)
321 {
322 struct expression *array;
323 struct expression *size;
324 struct expression *offset;
325 int comparison;
326
327 array = get_array_base(expr);
328 size = get_size_variable(array);
329 if (!size)
330 return 0;
331 offset = get_array_offset(expr);
332 comparison = get_comparison(size, offset);
333 if (comparison == '>' || comparison == SPECIAL_UNSIGNED_GT)
334 return 1;
335
336 return 0;
337 }
338
339 static int known_access_ok_numbers(struct expression *expr)
340 {
341 struct expression *array;
342 struct expression *offset;
343 sval_t max;
344 int size;
345
346 array = get_array_base(expr);
347 offset = get_array_offset(expr);
348
349 size = get_array_size(array);
350 if (size <= 0)
351 return 0;
352
353 get_absolute_max(offset, &max);
354 if (max.uvalue < size)
355 return 1;
356 return 0;
357 }
358
359 static void array_check_data_info(struct expression *expr)
360 {
361 struct expression *array;
362 struct expression *offset;
363 struct state_list *slist;
364 struct sm_state *sm;
365 struct compare_data *comp;
366 char *offset_name;
367 const char *equal_name = NULL;
368
369 expr = strip_expr(expr);
370 if (!is_array(expr))
371 return;
372
373 if (known_access_ok_numbers(expr))
374 return;
375 if (known_access_ok_comparison(expr))
376 return;
377
378 array = get_array_base(expr);
379 offset = get_array_offset(expr);
380 offset_name = expr_to_var(offset);
381 if (!offset_name)
382 return;
383 slist = get_all_possible_equal_comparisons(offset);
384 if (!slist)
385 goto free;
386
387 FOR_EACH_PTR(slist, sm) {
388 comp = sm->state->data;
389 if (strcmp(comp->left_var, offset_name) == 0) {
390 if (db_var_is_array_limit(array, comp->right_var, comp->right_vsl)) {
391 equal_name = comp->right_var;
392 break;
393 }
394 } else if (strcmp(comp->right_var, offset_name) == 0) {
395 if (db_var_is_array_limit(array, comp->left_var, comp->left_vsl)) {
399 }
400 } END_FOR_EACH_PTR(sm);
401
402 if (equal_name) {
403 char *array_name = expr_to_str(array);
404
405 sm_warning("potential off by one '%s[]' limit '%s'", array_name, equal_name);
406 free_string(array_name);
407 }
408
409 free:
410 free_slist(&slist);
411 free_string(offset_name);
412 }
413
414 static void add_allocation_function(const char *func, void *call_back, int param)
415 {
416 add_function_assign_hook(func, call_back, INT_PTR(param));
417 }
418
419 static char *buf_size_param_comparison(struct expression *array, struct expression_list *args)
420 {
421 struct expression *arg;
422 struct expression *size;
423 static char buf[32];
424 int i;
425
426 size = get_size_variable(array);
427 if (!size)
428 return NULL;
429
430 i = -1;
431 FOR_EACH_PTR(args, arg) {
432 i++;
433 if (arg == array)
434 continue;
435 if (!expr_equiv(arg, size))
436 continue;
437 snprintf(buf, sizeof(buf), "==$%d", i);
438 return buf;
439 } END_FOR_EACH_PTR(arg);
440
441 return NULL;
442 }
443
444 static void match_call(struct expression *call)
445 {
446 struct expression *arg;
447 char *compare;
448 int param;
449
450 param = -1;
451 FOR_EACH_PTR(call->args, arg) {
452 param++;
453 if (!is_pointer(arg))
454 continue;
455 compare = buf_size_param_comparison(arg, call->args);
456 if (!compare)
457 continue;
458 sql_insert_caller_info(call, ARRAY_LEN, param, "$", compare);
459 } END_FOR_EACH_PTR(arg);
460 }
461
462 static int get_param(int param, char **name, struct symbol **sym)
463 {
464 struct symbol *arg;
465 int i;
466
467 i = 0;
468 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
469 /*
470 * this is a temporary hack to work around a bug (I think in sparse?)
471 * 2.6.37-rc1:fs/reiserfs/journal.o
472 * If there is a function definition without parameter name found
473 * after a function implementation then it causes a crash.
474 * int foo() {}
475 * int bar(char *);
476 */
477 if (arg->ident->name < (char *)100)
478 continue;
479 if (i == param) {
480 *name = arg->ident->name;
481 *sym = arg;
482 return TRUE;
483 }
484 i++;
485 } END_FOR_EACH_PTR(arg);
486
487 return FALSE;
488 }
489
490 static void set_param_compare(const char *array_name, struct symbol *array_sym, char *key, char *value)
491 {
492 struct expression *array_expr;
493 struct expression *size_expr;
494 struct symbol *size_sym;
495 char *size_name;
496 long param;
497 struct sm_state *tmp;
498
499 if (strncmp(value, "==$", 3) != 0)
500 return;
501 param = strtol(value + 3, NULL, 10);
502 if (!get_param(param, &size_name, &size_sym))
503 return;
504 array_expr = symbol_expression(array_sym);
505 size_expr = symbol_expression(size_sym);
506
507 tmp = set_state_expr(size_id, array_expr, alloc_expr_state(size_expr));
508 if (!tmp)
509 return;
510 set_state_expr(link_id, size_expr, alloc_expr_state(array_expr));
511 }
512
513 static void set_arraysize_arg(const char *array_name, struct symbol *array_sym, char *key, char *value)
514 {
515 struct expression *array_expr;
516 struct expression *size_expr;
517 struct symbol *size_sym;
518 char *size_name;
519 long param;
520 struct sm_state *tmp;
521
522 param = strtol(key, NULL, 10);
523 if (!get_param(param, &size_name, &size_sym))
524 return;
525 array_expr = symbol_expression(array_sym);
526 size_expr = symbol_expression(size_sym);
527
528 tmp = set_state_expr(size_id, array_expr, alloc_expr_state(size_expr));
529 if (!tmp)
530 return;
531 set_state_expr(link_id, size_expr, alloc_expr_state(array_expr));
532 }
533
534 static void munge_start_states(struct statement *stmt)
535 {
536 struct state_list *slist = NULL;
537 struct sm_state *sm;
538 struct sm_state *poss;
539
540 FOR_EACH_MY_SM(size_id, __get_cur_stree(), sm) {
541 if (sm->state != &merged)
542 continue;
543 /*
544 * screw it. let's just assume that if one caller passes the
545 * size then they all do.
546 */
547 FOR_EACH_PTR(sm->possible, poss) {
548 if (poss->state != &merged &&
549 poss->state != &undefined) {
550 add_ptr_list(&slist, poss);
551 break;
552 }
553 } END_FOR_EACH_PTR(poss);
554 } END_FOR_EACH_SM(sm);
555
556 FOR_EACH_PTR(slist, sm) {
557 set_state(size_id, sm->name, sm->sym, sm->state);
558 } END_FOR_EACH_PTR(sm);
559
560 free_slist(&slist);
561 }
562
563 void register_buf_comparison(int id)
564 {
565 size_id = id;
566
567 add_unmatched_state_hook(size_id, &unmatched_state);
568
569 add_allocation_function("malloc", &match_alloc, 0);
570 add_allocation_function("memdup", &match_alloc, 1);
571 add_allocation_function("realloc", &match_alloc, 1);
572 if (option_project == PROJ_KERNEL) {
573 add_allocation_function("kmalloc", &match_alloc, 0);
574 add_allocation_function("kzalloc", &match_alloc, 0);
575 add_allocation_function("vmalloc", &match_alloc, 0);
576 add_allocation_function("__vmalloc", &match_alloc, 0);
577 add_allocation_function("sock_kmalloc", &match_alloc, 1);
578 add_allocation_function("kmemdup", &match_alloc, 1);
579 add_allocation_function("kmemdup_user", &match_alloc, 1);
580 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
581 add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
582 add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
583 add_allocation_function("devm_kmalloc", &match_alloc, 1);
584 add_allocation_function("devm_kzalloc", &match_alloc, 1);
585 add_allocation_function("kcalloc", &match_calloc, 0);
586 add_allocation_function("devm_kcalloc", &match_calloc, 1);
587 add_allocation_function("kmalloc_array", &match_calloc, 0);
588 add_allocation_function("krealloc", &match_alloc, 1);
589 }
590
591 add_hook(&array_check, OP_HOOK);
592 add_hook(&array_check_data_info, OP_HOOK);
593
594 add_hook(&match_call, FUNCTION_CALL_HOOK);
595 select_caller_info_hook(set_param_compare, ARRAY_LEN);
596 select_caller_info_hook(set_arraysize_arg, ARRAYSIZE_ARG);
597 add_hook(&munge_start_states, AFTER_DEF_HOOK);
598 }
599
600 void register_buf_comparison_links(int id)
601 {
602 link_id = id;
603 add_merge_hook(link_id, &merge_links);
604 add_modification_hook(link_id, &match_link_modify);
605 }
|
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 /*
19 * The point here is to store that a buffer has x bytes even if we don't know
20 * the value of x.
21 *
22 */
23
24 #include "smatch.h"
25 #include "smatch_extra.h"
26 #include "smatch_slist.h"
27
28 static int size_id;
29 static int link_id;
30
31 /*
32 * There is a bunch of code which does this:
33 *
34 * if (size)
35 * foo = malloc(size);
36 *
37 * So if "size" is non-zero then the size of "foo" is size. But really it's
38 * also true if size is zero. It's just better to assume to not trample over
39 * the data that we have by merging &undefined states.
40 *
41 */
42 static struct smatch_state *unmatched_state(struct sm_state *sm)
43 {
44 return sm->state;
45 }
46
47 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
48 {
49 struct expression *expr1, *expr2;
50
51 expr1 = s1->data;
52 expr2 = s2->data;
53
54 if (expr1 && expr2 && expr_equiv(expr1, expr2))
55 return s1;
56 return &merged;
57 }
58
59 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr)
60 {
61 struct expression *expr;
62 struct sm_state *tmp;
63
64 expr = sm->state->data;
65 if (expr) {
66 set_state_expr(size_id, expr, &undefined);
67 set_state(link_id, sm->name, sm->sym, &undefined);
68 return;
69 }
70
71 FOR_EACH_PTR(sm->possible, tmp) {
72 expr = tmp->state->data;
73 if (expr)
74 set_state_expr(size_id, expr, &undefined);
75 } END_FOR_EACH_PTR(tmp);
76 set_state(link_id, sm->name, sm->sym, &undefined);
77 }
78
79 static const char *limit_map[] = {
80 "byte_count",
81 "elem_count",
82 "elem_last",
83 "used_count",
84 "used_last",
85 };
86
87 int state_to_limit(struct smatch_state *state)
88 {
89 int i;
90
91 if (!state || !state->data)
92 return -1;
93
94 for (i = 0; i < ARRAY_SIZE(limit_map); i++) {
95 if (strncmp(state->name, limit_map[i], strlen(limit_map[i])) == 0)
96 return i + BYTE_COUNT;
97 }
98
99 return -1;
100 }
101
102 const char *limit_type_str(unsigned int limit_type)
103 {
104 if (limit_type - BYTE_COUNT >= ARRAY_SIZE(limit_map)) {
105 sm_msg("internal: wrong size type %u", limit_type);
106 return "unknown";
107 }
108
109 return limit_map[limit_type - BYTE_COUNT];
110 }
111
112 static struct smatch_state *alloc_compare_size(int limit_type, struct expression *expr)
113 {
114 struct smatch_state *state;
115 char *name;
116 char buf[256];
117
118 state = __alloc_smatch_state(0);
119 expr = strip_expr(expr);
120 name = expr_to_str(expr);
121 snprintf(buf, sizeof(buf), "%s %s", limit_type_str(limit_type), name);
122 state->name = alloc_sname(buf);
123 free_string(name);
124 state->data = expr;
125 return state;
126 }
127
128 static int bytes_per_element(struct expression *expr)
129 {
130 struct symbol *type;
131
132 type = get_type(expr);
133 if (!type)
134 return 0;
135
136 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
137 return 0;
138
139 type = get_base_type(type);
140 return type_bytes(type);
141 }
142
143 static void db_save_type_links(struct expression *array, int type_limit, struct expression *size)
144 {
145 const char *array_name;
146
147 array_name = get_data_info_name(array);
148 if (!array_name)
149 array_name = "";
150 sql_insert_data_info(size, type_limit, array_name);
151 }
152
153 static void match_alloc_helper(struct expression *pointer, struct expression *size)
154 {
155 struct expression *tmp;
156 struct sm_state *sm;
157 int limit_type = ELEM_COUNT;
158 sval_t sval;
159 int cnt = 0;
160
161 pointer = strip_expr(pointer);
162 size = strip_expr(size);
163 if (!size || !pointer)
164 return;
165
166 while ((tmp = get_assigned_expr(size))) {
167 size = strip_expr(tmp);
168 if (cnt++ > 5)
169 break;
170 }
171
172 if (size->type == EXPR_BINOP && size->op == '*') {
173 struct expression *mult_left, *mult_right;
174
175 mult_left = strip_expr(size->left);
176 mult_right = strip_expr(size->right);
177
178 if (get_implied_value(mult_left, &sval) &&
179 sval.value == bytes_per_element(pointer))
180 size = mult_right;
181 else if (get_implied_value(mult_right, &sval) &&
182 sval.value == bytes_per_element(pointer))
183 size = mult_left;
184 else
185 return;
186 }
187
188 /* Only save links to variables, not fixed sizes */
189 if (get_value(size, &sval))
190 return;
191
192 if (size->type == EXPR_BINOP && size->op == '+' &&
193 get_value(size->right, &sval) && sval.value == 1) {
194 size = size->left;
195 limit_type = ELEM_LAST;
196 }
197
198 db_save_type_links(pointer, limit_type, size);
199 sm = set_state_expr(size_id, pointer, alloc_compare_size(limit_type, size));
200 if (!sm)
201 return;
202 set_state_expr(link_id, size, alloc_state_expr(pointer));
203 }
204
205 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
206 {
207 int size_arg = PTR_INT(_size_arg);
208 struct expression *pointer, *call, *arg;
209
210 pointer = strip_expr(expr->left);
211 call = strip_expr(expr->right);
212 arg = get_argument_from_call_expr(call->args, size_arg);
213 match_alloc_helper(pointer, arg);
214 }
215
216 static void match_calloc(const char *fn, struct expression *expr, void *_start_arg)
217 {
218 int start_arg = PTR_INT(_start_arg);
219 struct expression *pointer, *call, *arg;
220 struct sm_state *tmp;
221 int limit_type = ELEM_COUNT;
222 sval_t sval;
223
224 pointer = strip_expr(expr->left);
225 call = strip_expr(expr->right);
226 arg = get_argument_from_call_expr(call->args, start_arg);
227 if (get_implied_value(arg, &sval) &&
228 sval.value == bytes_per_element(pointer))
229 arg = get_argument_from_call_expr(call->args, start_arg + 1);
230
231 if (arg->type == EXPR_BINOP && arg->op == '+' &&
232 get_value(arg->right, &sval) && sval.value == 1) {
233 arg = arg->left;
234 limit_type = ELEM_LAST;
235 }
236
237 db_save_type_links(pointer, limit_type, arg);
238 tmp = set_state_expr(size_id, pointer, alloc_compare_size(limit_type, arg));
239 if (!tmp)
240 return;
241 set_state_expr(link_id, arg, alloc_state_expr(pointer));
242 }
243
244 struct expression *get_size_variable(struct expression *buf, int *limit_type)
245 {
246 struct smatch_state *state;
247
248 state = get_state_expr(size_id, buf);
249 if (!state)
250 return NULL;
251 *limit_type = state_to_limit(state);
252 return state->data;
253 }
254
255 struct expression *get_array_variable(struct expression *size)
256 {
257 struct smatch_state *state;
258
259 state = get_state_expr(link_id, size);
260 if (state)
261 return state->data;
262 return NULL;
263 }
264
265 static void array_check(struct expression *expr)
266 {
267 struct expression *array;
268 struct expression *size;
269 struct expression *offset;
270 char *array_str, *offset_str;
271 int limit_type;
272
273 expr = strip_expr(expr);
274 if (!is_array(expr))
275 return;
276
277 array = get_array_base(expr);
278 size = get_size_variable(array, &limit_type);
279 if (!size)
280 return;
281 if (limit_type != ELEM_COUNT)
282 return;
283 offset = get_array_offset(expr);
284 if (!possible_comparison(size, SPECIAL_EQUAL, offset))
285 return;
286
287 array_str = expr_to_str(array);
288 offset_str = expr_to_str(offset);
289 sm_warning("potentially one past the end of array '%s[%s]'", array_str, offset_str);
290 free_string(array_str);
291 free_string(offset_str);
292 }
293
294 struct db_info {
295 char *name;
296 int ret;
297 };
298
299 static int db_limitter_callback(void *_info, int argc, char **argv, char **azColName)
300 {
301 struct db_info *info = _info;
302
347 return alloc_sname(buf);
348 }
349
350 int db_var_is_array_limit(struct expression *array, const char *name, struct var_sym_list *vsl)
351 {
352 char *size_name;
353 char *array_name = get_data_info_name(array);
354 struct db_info db_info = {.name = array_name,};
355
356 size_name = vsl_to_data_info_name(name, vsl);
357 if (!size_name)
358 return 0;
359
360 run_sql(db_limitter_callback, &db_info,
361 "select value from data_info where type = %d and data = '%s';",
362 ARRAY_LEN, size_name);
363
364 return db_info.ret;
365 }
366
367 int buf_comparison_index_ok(struct expression *expr)
368 {
369 struct expression *array;
370 struct expression *size;
371 struct expression *offset;
372 int limit_type;
373 int comparison;
374
375 array = get_array_base(expr);
376 size = get_size_variable(array, &limit_type);
377 if (!size)
378 return 0;
379 offset = get_array_offset(expr);
380 comparison = get_comparison(offset, size);
381 if (!comparison)
382 return 0;
383
384 if ((limit_type == ELEM_COUNT || limit_type == ELEM_LAST) &&
385 (comparison == '<' || comparison == SPECIAL_UNSIGNED_LT))
386 return 1;
387 if (limit_type == ELEM_LAST &&
388 (comparison == SPECIAL_LTE ||
389 comparison == SPECIAL_UNSIGNED_LTE ||
390 comparison == SPECIAL_EQUAL))
391 return 1;
392
393 return 0;
394 }
395
396 static int known_access_ok_numbers(struct expression *expr)
397 {
398 struct expression *array;
399 struct expression *offset;
400 sval_t max;
401 int size;
402
403 array = get_array_base(expr);
404 offset = get_array_offset(expr);
405
406 size = get_array_size(array);
407 if (size <= 0)
408 return 0;
409
410 get_absolute_max(offset, &max);
411 if (max.uvalue < size)
412 return 1;
413 return 0;
414 }
415
416 static void array_check_data_info(struct expression *expr)
417 {
418 struct expression *array;
419 struct expression *offset;
420 struct state_list *slist;
421 struct sm_state *sm;
422 struct compare_data *comp;
423 char *offset_name;
424 const char *equal_name = NULL;
425
426 expr = strip_expr(expr);
427 if (!is_array(expr))
428 return;
429
430 if (known_access_ok_numbers(expr))
431 return;
432 if (buf_comparison_index_ok(expr))
433 return;
434
435 array = get_array_base(expr);
436 offset = get_array_offset(expr);
437 offset_name = expr_to_var(offset);
438 if (!offset_name)
439 return;
440 slist = get_all_possible_equal_comparisons(offset);
441 if (!slist)
442 goto free;
443
444 FOR_EACH_PTR(slist, sm) {
445 comp = sm->state->data;
446 if (strcmp(comp->left_var, offset_name) == 0) {
447 if (db_var_is_array_limit(array, comp->right_var, comp->right_vsl)) {
448 equal_name = comp->right_var;
449 break;
450 }
451 } else if (strcmp(comp->right_var, offset_name) == 0) {
452 if (db_var_is_array_limit(array, comp->left_var, comp->left_vsl)) {
456 }
457 } END_FOR_EACH_PTR(sm);
458
459 if (equal_name) {
460 char *array_name = expr_to_str(array);
461
462 sm_warning("potential off by one '%s[]' limit '%s'", array_name, equal_name);
463 free_string(array_name);
464 }
465
466 free:
467 free_slist(&slist);
468 free_string(offset_name);
469 }
470
471 static void add_allocation_function(const char *func, void *call_back, int param)
472 {
473 add_function_assign_hook(func, call_back, INT_PTR(param));
474 }
475
476 static int is_sizeof(struct expression *expr)
477 {
478 const char *name;
479
480 if (expr->type == EXPR_SIZEOF)
481 return 1;
482 name = pos_ident(expr->pos);
483 if (name && strcmp(name, "sizeof") == 0)
484 return 1;
485 return 0;
486 }
487
488 static int match_size_binop(struct expression *size, struct expression *expr, int *limit_type)
489 {
490 int orig_type = *limit_type;
491 struct expression *left;
492 sval_t sval;
493
494 left = expr->left;
495 if (!expr_equiv(size, left))
496 return 0;
497
498 if (expr->op == '-' &&
499 get_value(expr->right, &sval) &&
500 sval.value == 1 &&
501 orig_type == ELEM_COUNT) {
502 *limit_type = ELEM_LAST;
503 return 1;
504 }
505
506 if (expr->op == '+' &&
507 get_value(expr->right, &sval) &&
508 sval.value == 1 &&
509 orig_type == ELEM_LAST) {
510 *limit_type = ELEM_COUNT;
511 return 1;
512 }
513
514 if (expr->op == '*' &&
515 is_sizeof(expr->right) &&
516 orig_type == ELEM_COUNT) {
517 *limit_type = BYTE_COUNT;
518 return 1;
519 }
520
521 if (expr->op == '/' &&
522 is_sizeof(expr->right) &&
523 orig_type == BYTE_COUNT) {
524 *limit_type = ELEM_COUNT;
525 return 1;
526 }
527
528 return 0;
529 }
530
531 static char *buf_size_param_comparison(struct expression *array, struct expression_list *args, int *limit_type)
532 {
533 struct expression *tmp, *arg;
534 struct expression *size;
535 static char buf[32];
536 int i;
537
538 size = get_size_variable(array, limit_type);
539 if (!size)
540 return NULL;
541
542 if (*limit_type == USED_LAST)
543 *limit_type = ELEM_LAST;
544 if (*limit_type == USED_COUNT)
545 *limit_type = ELEM_COUNT;
546
547 i = -1;
548 FOR_EACH_PTR(args, tmp) {
549 i++;
550 arg = tmp;
551 if (arg == array)
552 continue;
553 if (expr_equiv(arg, size) ||
554 (arg->type == EXPR_BINOP &&
555 match_size_binop(size, arg, limit_type))) {
556 snprintf(buf, sizeof(buf), "==$%d", i);
557 return buf;
558 }
559 } END_FOR_EACH_PTR(tmp);
560
561 return NULL;
562 }
563
564 static void match_call(struct expression *call)
565 {
566 struct expression *arg;
567 char *compare;
568 int param;
569 char buf[5];
570 int limit_type;
571
572 param = -1;
573 FOR_EACH_PTR(call->args, arg) {
574 param++;
575 if (!is_pointer(arg))
576 continue;
577 compare = buf_size_param_comparison(arg, call->args, &limit_type);
578 if (!compare)
579 continue;
580 snprintf(buf, sizeof(buf), "%d", limit_type);
581 sql_insert_caller_info(call, limit_type, param, compare, buf);
582 } END_FOR_EACH_PTR(arg);
583 }
584
585 static int get_param(int param, char **name, struct symbol **sym)
586 {
587 struct symbol *arg;
588 int i;
589
590 i = 0;
591 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
592 /*
593 * this is a temporary hack to work around a bug (I think in sparse?)
594 * 2.6.37-rc1:fs/reiserfs/journal.o
595 * If there is a function definition without parameter name found
596 * after a function implementation then it causes a crash.
597 * int foo() {}
598 * int bar(char *);
599 */
600 if (arg->ident->name < (char *)100)
601 continue;
602 if (i == param) {
603 *name = arg->ident->name;
604 *sym = arg;
605 return TRUE;
606 }
607 i++;
608 } END_FOR_EACH_PTR(arg);
609
610 return FALSE;
611 }
612
613 static void set_param_compare(const char *array_name, struct symbol *array_sym, char *key, char *value)
614 {
615 struct expression *array_expr;
616 struct expression *size_expr;
617 struct symbol *size_sym;
618 char *size_name;
619 long param;
620 struct sm_state *tmp;
621 int limit_type;
622
623 if (strncmp(key, "==$", 3) != 0)
624 return;
625 param = strtol(key + 3, NULL, 10);
626 if (!get_param(param, &size_name, &size_sym))
627 return;
628 array_expr = symbol_expression(array_sym);
629 size_expr = symbol_expression(size_sym);
630 limit_type = strtol(value, NULL, 10);
631
632 tmp = set_state_expr(size_id, array_expr, alloc_compare_size(limit_type, size_expr));
633 if (!tmp)
634 return;
635 set_state_expr(link_id, size_expr, alloc_state_expr(array_expr));
636 }
637
638 static void set_implied(struct expression *call, struct expression *array_expr, char *key, char *value)
639 {
640 struct expression *size_expr;
641 struct symbol *size_sym;
642 char *size_name;
643 long param;
644 struct sm_state *tmp;
645 int limit_type;
646
647 if (strncmp(key, "==$", 3) != 0)
648 return;
649 param = strtol(key + 3, NULL, 10);
650 if (!get_param(param, &size_name, &size_sym))
651 return;
652 size_expr = symbol_expression(size_sym);
653
654 limit_type = strtol(value, NULL, 10);
655 tmp = set_state_expr(size_id, array_expr, alloc_compare_size(limit_type, size_expr));
656 if (!tmp)
657 return;
658 set_state_expr(link_id, size_expr, alloc_state_expr(array_expr));
659 }
660
661 static void munge_start_states(struct statement *stmt)
662 {
663 struct state_list *slist = NULL;
664 struct sm_state *sm;
665 struct sm_state *poss;
666
667 FOR_EACH_MY_SM(size_id, __get_cur_stree(), sm) {
668 if (sm->state != &merged)
669 continue;
670 /*
671 * screw it. let's just assume that if one caller passes the
672 * size then they all do.
673 */
674 FOR_EACH_PTR(sm->possible, poss) {
675 if (poss->state != &merged &&
676 poss->state != &undefined) {
677 add_ptr_list(&slist, poss);
678 break;
679 }
680 } END_FOR_EACH_PTR(poss);
681 } END_FOR_EACH_SM(sm);
682
683 FOR_EACH_PTR(slist, sm) {
684 set_state(size_id, sm->name, sm->sym, sm->state);
685 } END_FOR_EACH_PTR(sm);
686
687 free_slist(&slist);
688 }
689
690 static void set_used(struct expression *expr)
691 {
692 struct expression *parent;
693 struct expression *array;
694 struct expression *offset;
695 struct sm_state *tmp;
696 int limit_type;
697
698 if (expr->op != SPECIAL_INCREMENT)
699 return;
700
701 limit_type = USED_LAST;
702 if (expr->type == EXPR_POSTOP)
703 limit_type = USED_COUNT;
704
705 parent = expr_get_parent_expr(expr);
706 if (!parent || parent->type != EXPR_BINOP)
707 return;
708 parent = expr_get_parent_expr(parent);
709 if (!parent || !is_array(parent))
710 return;
711
712 array = get_array_base(parent);
713 offset = get_array_offset(parent);
714 if (offset != expr)
715 return;
716
717 tmp = set_state_expr(size_id, array, alloc_compare_size(limit_type, offset->unop));
718 if (!tmp)
719 return;
720 set_state_expr(link_id, offset->unop, alloc_state_expr(array));
721 }
722
723 static int match_assign_array(struct expression *expr)
724 {
725 // FIXME: implement
726 return 0;
727 }
728
729 static int match_assign_size(struct expression *expr)
730 {
731 struct expression *right, *size, *array;
732 struct smatch_state *state;
733 struct sm_state *tmp;
734 int limit_type;
735
736 right = expr->right;
737 size = right;
738 if (size->type == EXPR_BINOP)
739 size = size->left;
740
741 array = get_array_variable(size);
742 if (!array)
743 return 0;
744 state = get_state_expr(size_id, array);
745 if (!state || !state->data)
746 return 0;
747
748 limit_type = state_to_limit(state);
749 if (limit_type < 0)
750 return 0;
751
752 if (right->type == EXPR_BINOP && !match_size_binop(size, right, &limit_type))
753 return 0;
754
755 tmp = set_state_expr(size_id, array, alloc_compare_size(limit_type, expr->left));
756 if (!tmp)
757 return 0;
758 set_state_expr(link_id, expr->left, alloc_state_expr(array));
759 return 1;
760 }
761
762 static void match_assign(struct expression *expr)
763 {
764 if (expr->op != '=')
765 return;
766
767 if (match_assign_array(expr))
768 return;
769 match_assign_size(expr);
770 }
771
772 static void match_copy(const char *fn, struct expression *expr, void *unused)
773 {
774 struct expression *src, *size;
775 int src_param, size_param;
776
777 src = get_argument_from_call_expr(expr->args, 1);
778 size = get_argument_from_call_expr(expr->args, 2);
779 src = strip_expr(src);
780 size = strip_expr(size);
781 if (!src || !size)
782 return;
783 if (src->type != EXPR_SYMBOL || size->type != EXPR_SYMBOL)
784 return;
785
786 src_param = get_param_num_from_sym(src->symbol);
787 size_param = get_param_num_from_sym(size->symbol);
788 if (src_param < 0 || size_param < 0)
789 return;
790
791 sql_insert_cache(call_implies, "'%s', '%s', 0, %d, %d, %d, '==$%d', '%d'",
792 get_base_file(), get_function(), fn_static(),
793 BYTE_COUNT, src_param, size_param, BYTE_COUNT);
794 }
795
796 void register_buf_comparison(int id)
797 {
798 int i;
799
800 size_id = id;
801
802 set_dynamic_states(size_id);
803
804 add_unmatched_state_hook(size_id, &unmatched_state);
805
806 add_allocation_function("malloc", &match_alloc, 0);
807 add_allocation_function("memdup", &match_alloc, 1);
808 add_allocation_function("realloc", &match_alloc, 1);
809 if (option_project == PROJ_KERNEL) {
810 add_allocation_function("kmalloc", &match_alloc, 0);
811 add_allocation_function("kzalloc", &match_alloc, 0);
812 add_allocation_function("vmalloc", &match_alloc, 0);
813 add_allocation_function("__vmalloc", &match_alloc, 0);
814 add_allocation_function("sock_kmalloc", &match_alloc, 1);
815 add_allocation_function("kmemdup", &match_alloc, 1);
816 add_allocation_function("kmemdup_user", &match_alloc, 1);
817 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
818 add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
819 add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
820 add_allocation_function("devm_kmalloc", &match_alloc, 1);
821 add_allocation_function("devm_kzalloc", &match_alloc, 1);
822 add_allocation_function("kcalloc", &match_calloc, 0);
823 add_allocation_function("devm_kcalloc", &match_calloc, 1);
824 add_allocation_function("kmalloc_array", &match_calloc, 0);
825 add_allocation_function("krealloc", &match_alloc, 1);
826
827 add_function_hook("copy_from_user", &match_copy, NULL);
828 add_function_hook("__copy_from_user", &match_copy, NULL);
829 }
830
831 add_hook(&array_check, OP_HOOK);
832 add_hook(&array_check_data_info, OP_HOOK);
833 add_hook(&set_used, OP_HOOK);
834
835 add_hook(&match_call, FUNCTION_CALL_HOOK);
836 add_hook(&munge_start_states, AFTER_DEF_HOOK);
837
838 add_hook(&match_assign, ASSIGNMENT_HOOK);
839
840 for (i = BYTE_COUNT; i <= USED_COUNT; i++) {
841 select_call_implies_hook(i, &set_implied);
842 select_caller_info_hook(set_param_compare, i);
843 select_return_implies_hook(i, &set_implied);
844 }
845 }
846
847 void register_buf_comparison_links(int id)
848 {
849 link_id = id;
850 set_dynamic_states(link_id);
851 add_merge_hook(link_id, &merge_links);
852 add_modification_hook(link_id, &match_link_modify);
853 }
|