Print this page
12724 update smatch to 0.6.1-rc1-il-5
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/tools/smatch/src/smatch_extra.c
+++ new/usr/src/tools/smatch/src/smatch_extra.c
1 1 /*
2 2 * Copyright (C) 2008 Dan Carpenter.
3 3 *
4 4 * This program is free software; you can redistribute it and/or
5 5 * modify it under the terms of the GNU General Public License
6 6 * as published by the Free Software Foundation; either version 2
7 7 * of the License, or (at your option) any later version.
8 8 *
9 9 * This program is distributed in the hope that it will be useful,
10 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 12 * GNU General Public License for more details.
13 13 *
14 14 * You should have received a copy of the GNU General Public License
15 15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16 16 */
17 17
18 18 /*
19 19 * smatch_extra.c is supposed to track the value of every variable.
20 20 *
21 21 */
22 22
23 23 #define _GNU_SOURCE
24 24 #include <string.h>
25 25
26 26 #include <stdlib.h>
27 27 #include <errno.h>
28 28 #ifndef __USE_ISOC99
|
↓ open down ↓ |
28 lines elided |
↑ open up ↑ |
29 29 #define __USE_ISOC99
30 30 #endif
31 31 #include <limits.h>
32 32 #include "parse.h"
33 33 #include "smatch.h"
34 34 #include "smatch_slist.h"
35 35 #include "smatch_extra.h"
36 36
37 37 static int my_id;
38 38 static int link_id;
39 -extern int check_assigned_expr_id;
40 39
41 40 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr);
42 41
43 42 struct string_list *__ignored_macros = NULL;
44 43 int in_warn_on_macro(void)
45 44 {
46 45 struct statement *stmt;
47 46 char *tmp;
48 47 char *macro;
49 48
50 49 stmt = get_current_statement();
51 50 if (!stmt)
52 51 return 0;
53 52 macro = get_macro_name(stmt->pos);
54 53 if (!macro)
55 54 return 0;
56 55
57 56 FOR_EACH_PTR(__ignored_macros, tmp) {
58 57 if (!strcmp(tmp, macro))
59 58 return 1;
60 59 } END_FOR_EACH_PTR(tmp);
61 60 return 0;
62 61 }
63 62
64 63 typedef void (mod_hook)(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state);
65 64 DECLARE_PTR_LIST(void_fn_list, mod_hook *);
66 65 static struct void_fn_list *extra_mod_hooks;
67 66 static struct void_fn_list *extra_nomod_hooks;
68 67
69 68 void add_extra_mod_hook(mod_hook *fn)
70 69 {
71 70 mod_hook **p = malloc(sizeof(mod_hook *));
72 71 *p = fn;
73 72 add_ptr_list(&extra_mod_hooks, p);
74 73 }
75 74
76 75 void add_extra_nomod_hook(mod_hook *fn)
77 76 {
78 77 mod_hook **p = malloc(sizeof(mod_hook *));
79 78 *p = fn;
80 79 add_ptr_list(&extra_nomod_hooks, p);
81 80 }
82 81
83 82 void call_extra_hooks(struct void_fn_list *hooks, const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
84 83 {
85 84 mod_hook **fn;
86 85
87 86 FOR_EACH_PTR(hooks, fn) {
88 87 (*fn)(name, sym, expr, state);
89 88 } END_FOR_EACH_PTR(fn);
90 89 }
91 90
92 91 void call_extra_mod_hooks(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
93 92 {
94 93 call_extra_hooks(extra_mod_hooks, name, sym, expr, state);
95 94 }
96 95
97 96 void call_extra_nomod_hooks(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
98 97 {
99 98 call_extra_hooks(extra_nomod_hooks, name, sym, expr, state);
100 99 }
101 100
102 101 static void set_union_info(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
103 102 {
104 103 struct symbol *type, *tmp, *inner_type, *inner, *new_type;
105 104 struct expression *deref, *member_expr;
106 105 struct smatch_state *new;
107 106 int offset, inner_offset;
108 107 static bool in_recurse;
109 108 char *member_name;
110 109
111 110 if (__in_fake_assign)
112 111 return;
113 112
114 113 if (in_recurse)
115 114 return;
116 115 in_recurse = true;
117 116
118 117 if (!expr || expr->type != EXPR_DEREF || !expr->member)
119 118 goto done;
120 119 offset = get_member_offset_from_deref(expr);
121 120 if (offset < 0)
122 121 goto done;
123 122
124 123 deref = strip_expr(expr->deref);
125 124 type = get_type(deref);
126 125 if (type_is_ptr(type))
127 126 type = get_real_base_type(type);
128 127 if (!type || type->type != SYM_STRUCT)
129 128 goto done;
130 129
131 130 FOR_EACH_PTR(type->symbol_list, tmp) {
132 131 inner_type = get_real_base_type(tmp);
133 132 if (!inner_type || inner_type->type != SYM_UNION)
134 133 continue;
135 134
136 135 inner = first_ptr_list((struct ptr_list *)inner_type->symbol_list);
137 136 if (!inner || !inner->ident)
138 137 continue;
139 138
140 139 inner_offset = get_member_offset(type, inner->ident->name);
141 140 if (inner_offset < offset)
142 141 continue;
143 142 if (inner_offset > offset)
144 143 goto done;
145 144
146 145 FOR_EACH_PTR(inner_type->symbol_list, inner) {
147 146 struct symbol *tmp_type;
148 147
149 148 if (!inner->ident || inner->ident == expr->member)
150 149 continue;
151 150 tmp_type = get_real_base_type(inner);
152 151 if (tmp_type && tmp_type->type == SYM_STRUCT)
153 152 continue;
154 153 member_expr = deref;
155 154 if (tmp->ident)
156 155 member_expr = member_expression(member_expr, '.', tmp->ident);
157 156 member_expr = member_expression(member_expr, expr->op, inner->ident);
158 157 member_name = expr_to_var(member_expr);
159 158 if (!member_name)
160 159 continue;
161 160 new_type = get_real_base_type(inner);
162 161 new = alloc_estate_rl(cast_rl(new_type, estate_rl(state)));
163 162 set_extra_mod_helper(member_name, sym, member_expr, new);
164 163 free_string(member_name);
|
↓ open down ↓ |
115 lines elided |
↑ open up ↑ |
165 164 } END_FOR_EACH_PTR(inner);
166 165 } END_FOR_EACH_PTR(tmp);
167 166
168 167 done:
169 168 in_recurse = false;
170 169 }
171 170
172 171 static bool in_param_set;
173 172 void set_extra_mod_helper(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
174 173 {
174 + struct expression *faked;
175 +
175 176 if (!expr)
176 177 expr = gen_expression_from_name_sym(name, sym);
177 178 remove_from_equiv(name, sym);
178 179 set_union_info(name, sym, expr, state);
179 180 call_extra_mod_hooks(name, sym, expr, state);
180 - update_mtag_data(expr, state);
181 + faked = get_faked_expression();
182 + if (!faked ||
183 + (faked->type == EXPR_ASSIGNMENT && is_fresh_alloc(faked->right)))
184 + update_mtag_data(expr, state);
181 185 if (in_param_set &&
182 186 estate_is_unknown(state) && !get_state(SMATCH_EXTRA, name, sym))
183 187 return;
184 188 set_state(SMATCH_EXTRA, name, sym, state);
185 189 }
186 190
187 191 static void set_extra_nomod_helper(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
188 192 {
189 193 call_extra_nomod_hooks(name, sym, expr, state);
190 194 set_state(SMATCH_EXTRA, name, sym, state);
191 195 }
192 196
193 197 static char *get_pointed_at(const char *name, struct symbol *sym, struct symbol **new_sym)
194 198 {
195 199 struct expression *assigned;
196 200
197 201 /*
198 202 * Imagine we have an assignment: "foo = &addr;" then the other name
199 203 * of "*foo" is addr.
200 204 */
201 205
202 206 if (name[0] != '*')
203 207 return NULL;
204 208 if (strcmp(name + 1, sym->ident->name) != 0)
205 209 return NULL;
206 210
207 211 assigned = get_assigned_expr_name_sym(sym->ident->name, sym);
208 212 if (!assigned)
209 213 return NULL;
210 214 assigned = strip_parens(assigned);
211 215 if (assigned->type != EXPR_PREOP || assigned->op != '&')
212 216 return NULL;
213 217
214 218 return expr_to_var_sym(assigned->unop, new_sym);
215 219 }
216 220
217 221 char *get_other_name_sym_from_chunk(const char *name, const char *chunk, int len, struct symbol *sym, struct symbol **new_sym)
218 222 {
219 223 struct expression *assigned;
220 224 char *orig_name = NULL;
221 225 char buf[256];
222 226 char *ret;
223 227
224 228 assigned = get_assigned_expr_name_sym(chunk, sym);
225 229 if (!assigned)
226 230 return NULL;
227 231 if (assigned->type == EXPR_CALL)
228 232 return map_call_to_other_name_sym(name, sym, new_sym);
229 233 if (assigned->type == EXPR_PREOP && assigned->op == '&') {
230 234
231 235 orig_name = expr_to_var_sym(assigned, new_sym);
232 236 if (!orig_name || !*new_sym)
233 237 goto free;
234 238
235 239 snprintf(buf, sizeof(buf), "%s.%s", orig_name + 1, name + len);
236 240 ret = alloc_string(buf);
237 241 free_string(orig_name);
238 242 return ret;
239 243 }
240 244
241 245 orig_name = expr_to_var_sym(assigned, new_sym);
242 246 if (!orig_name || !*new_sym)
243 247 goto free;
244 248
245 249 snprintf(buf, sizeof(buf), "%s->%s", orig_name, name + len);
246 250 ret = alloc_string(buf);
247 251 free_string(orig_name);
248 252 return ret;
249 253 free:
250 254 free_string(orig_name);
251 255 return NULL;
252 256 }
253 257
254 258 static char *get_long_name_sym(const char *name, struct symbol *sym, struct symbol **new_sym, bool use_stack)
255 259 {
256 260 struct expression *tmp;
257 261 struct sm_state *sm;
258 262 char buf[256];
259 263
260 264 /*
261 265 * Just prepend the name with a different name/sym and return that.
262 266 * For example, if we set "foo->bar = bar;" then the other name
263 267 * for "bar->baz" is "foo->bar->baz". Or if we have "foo = bar;" then
264 268 * the other name for "bar" is "foo". A third option is if we have
265 269 * "foo = bar;" then another name for "*bar" is "*foo".
266 270 */
267 271
268 272 FOR_EACH_MY_SM(check_assigned_expr_id, __get_cur_stree(), sm) {
269 273 tmp = sm->state->data;
270 274 if (!tmp || tmp->type != EXPR_SYMBOL)
271 275 continue;
272 276 if (tmp->symbol == sym)
273 277 goto found;
274 278 } END_FOR_EACH_SM(sm);
275 279
276 280 return NULL;
277 281
278 282 found:
279 283 if (!use_stack && name[tmp->symbol->ident->len] != '-')
280 284 return NULL;
281 285
282 286 if (name[0] == '*' && strcmp(name + 1, tmp->symbol_name->name) == 0)
283 287 snprintf(buf, sizeof(buf), "*%s", sm->name);
284 288 else if (name[tmp->symbol->ident->len] == '-' ||
285 289 name[tmp->symbol->ident->len] == '.')
286 290 snprintf(buf, sizeof(buf), "%s%s", sm->name, name + tmp->symbol->ident->len);
287 291 else if (strcmp(name, tmp->symbol_name->name) == 0)
288 292 snprintf(buf, sizeof(buf), "%s", sm->name);
289 293 else
290 294 return NULL;
291 295
292 296 *new_sym = sm->sym;
293 297 return alloc_string(buf);
294 298 }
295 299
296 300 char *get_other_name_sym_helper(const char *name, struct symbol *sym, struct symbol **new_sym, bool use_stack)
297 301 {
298 302 char buf[256];
299 303 char *ret;
300 304 int len;
301 305
302 306 *new_sym = NULL;
303 307
304 308 if (!sym || !sym->ident)
305 309 return NULL;
306 310
307 311 ret = get_pointed_at(name, sym, new_sym);
308 312 if (ret)
309 313 return ret;
310 314
311 315 ret = map_long_to_short_name_sym(name, sym, new_sym, use_stack);
312 316 if (ret)
313 317 return ret;
314 318
315 319 len = snprintf(buf, sizeof(buf), "%s", name);
316 320 if (len >= sizeof(buf) - 2)
317 321 return NULL;
318 322
319 323 while (use_stack && len >= 1) {
320 324 if (buf[len] == '>' && buf[len - 1] == '-') {
321 325 len--;
322 326 buf[len] = '\0';
323 327 ret = get_other_name_sym_from_chunk(name, buf, len + 2, sym, new_sym);
324 328 if (ret)
325 329 return ret;
326 330 }
327 331 len--;
328 332 }
329 333
330 334 ret = get_long_name_sym(name, sym, new_sym, use_stack);
331 335 if (ret)
332 336 return ret;
333 337
334 338 return NULL;
335 339 }
336 340
337 341 char *get_other_name_sym(const char *name, struct symbol *sym, struct symbol **new_sym)
338 342 {
339 343 return get_other_name_sym_helper(name, sym, new_sym, true);
340 344 }
341 345
342 346 char *get_other_name_sym_nostack(const char *name, struct symbol *sym, struct symbol **new_sym)
343 347 {
344 348 return get_other_name_sym_helper(name, sym, new_sym, false);
345 349 }
346 350
347 351 void set_extra_mod(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
348 352 {
349 353 char *new_name;
350 354 struct symbol *new_sym;
351 355
352 356 set_extra_mod_helper(name, sym, expr, state);
353 357 new_name = get_other_name_sym_nostack(name, sym, &new_sym);
354 358 if (new_name && new_sym)
355 359 set_extra_mod_helper(new_name, new_sym, NULL, state);
356 360 free_string(new_name);
357 361 }
358 362
359 363 static struct expression *chunk_get_array_base(struct expression *expr)
360 364 {
361 365 /*
362 366 * The problem with is_array() is that it only returns true for things
363 367 * like foo[1] but not for foo[1].bar.
364 368 *
365 369 */
366 370 expr = strip_expr(expr);
367 371 while (expr && expr->type == EXPR_DEREF)
368 372 expr = strip_expr(expr->deref);
369 373 return get_array_base(expr);
370 374 }
371 375
372 376 static int chunk_has_array(struct expression *expr)
373 377 {
374 378 return !!chunk_get_array_base(expr);
375 379 }
376 380
377 381 static void clear_array_states(struct expression *array)
378 382 {
379 383 struct sm_state *sm;
380 384
381 385 sm = get_sm_state_expr(link_id, array);
382 386 if (sm)
383 387 match_link_modify(sm, NULL);
384 388 }
385 389
386 390 static void set_extra_array_mod(struct expression *expr, struct smatch_state *state)
387 391 {
388 392 struct expression *array;
389 393 struct var_sym_list *vsl;
390 394 struct var_sym *vs;
391 395 char *name;
392 396 struct symbol *sym;
393 397
394 398 array = chunk_get_array_base(expr);
395 399
396 400 name = expr_to_chunk_sym_vsl(expr, &sym, &vsl);
397 401 if (!name || !vsl) {
398 402 clear_array_states(array);
399 403 goto free;
400 404 }
401 405
402 406 FOR_EACH_PTR(vsl, vs) {
403 407 store_link(link_id, vs->var, vs->sym, name, sym);
404 408 } END_FOR_EACH_PTR(vs);
405 409
406 410 call_extra_mod_hooks(name, sym, expr, state);
407 411 set_state(SMATCH_EXTRA, name, sym, state);
408 412 free:
409 413 free_string(name);
410 414 }
411 415
412 416 void set_extra_expr_mod(struct expression *expr, struct smatch_state *state)
413 417 {
414 418 struct symbol *sym;
415 419 char *name;
416 420
417 421 if (chunk_has_array(expr)) {
418 422 set_extra_array_mod(expr, state);
419 423 return;
420 424 }
421 425
422 426 expr = strip_expr(expr);
423 427 name = expr_to_var_sym(expr, &sym);
424 428 if (!name || !sym)
425 429 goto free;
426 430 set_extra_mod(name, sym, expr, state);
427 431 free:
428 432 free_string(name);
429 433 }
430 434
431 435 void set_extra_nomod(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
432 436 {
433 437 char *new_name;
434 438 struct symbol *new_sym;
435 439 struct relation *rel;
436 440 struct smatch_state *orig_state;
437 441
438 442 orig_state = get_state(SMATCH_EXTRA, name, sym);
439 443
440 444 /* don't save unknown states if leaving it blank is the same */
441 445 if (!orig_state && estate_is_unknown(state))
442 446 return;
443 447
444 448 new_name = get_other_name_sym(name, sym, &new_sym);
445 449 if (new_name && new_sym)
446 450 set_extra_nomod_helper(new_name, new_sym, expr, state);
447 451 free_string(new_name);
448 452
449 453 if (!estate_related(orig_state)) {
450 454 set_extra_nomod_helper(name, sym, expr, state);
451 455 return;
452 456 }
453 457
454 458 set_related(state, estate_related(orig_state));
455 459 FOR_EACH_PTR(estate_related(orig_state), rel) {
456 460 struct smatch_state *estate;
457 461
458 462 estate = get_state(SMATCH_EXTRA, rel->name, rel->sym);
459 463 if (!estate)
460 464 continue;
461 465 set_extra_nomod_helper(rel->name, rel->sym, expr, clone_estate_cast(estate_type(estate), state));
462 466 } END_FOR_EACH_PTR(rel);
463 467 }
464 468
465 469 void set_extra_nomod_vsl(const char *name, struct symbol *sym, struct var_sym_list *vsl, struct expression *expr, struct smatch_state *state)
466 470 {
467 471 struct var_sym *vs;
468 472
469 473 FOR_EACH_PTR(vsl, vs) {
470 474 store_link(link_id, vs->var, vs->sym, name, sym);
471 475 } END_FOR_EACH_PTR(vs);
472 476
473 477 set_extra_nomod(name, sym, expr, state);
474 478 }
475 479
476 480 /*
477 481 * This is for return_implies_state() hooks which modify a SMATCH_EXTRA state
478 482 */
479 483 void set_extra_expr_nomod(struct expression *expr, struct smatch_state *state)
480 484 {
481 485 struct var_sym_list *vsl;
482 486 struct var_sym *vs;
483 487 char *name;
484 488 struct symbol *sym;
485 489
486 490 name = expr_to_chunk_sym_vsl(expr, &sym, &vsl);
487 491 if (!name || !vsl)
488 492 goto free;
489 493 FOR_EACH_PTR(vsl, vs) {
490 494 store_link(link_id, vs->var, vs->sym, name, sym);
491 495 } END_FOR_EACH_PTR(vs);
492 496
493 497 set_extra_nomod(name, sym, expr, state);
494 498 free:
495 499 free_string(name);
496 500 }
497 501
498 502 static void set_extra_true_false(const char *name, struct symbol *sym,
499 503 struct smatch_state *true_state,
500 504 struct smatch_state *false_state)
501 505 {
502 506 char *new_name;
503 507 struct symbol *new_sym;
504 508 struct relation *rel;
505 509 struct smatch_state *orig_state;
506 510
507 511 if (!true_state && !false_state)
508 512 return;
509 513
510 514 if (in_warn_on_macro())
511 515 return;
512 516
513 517 new_name = get_other_name_sym(name, sym, &new_sym);
514 518 if (new_name && new_sym)
515 519 set_true_false_states(SMATCH_EXTRA, new_name, new_sym, true_state, false_state);
516 520 free_string(new_name);
517 521
518 522 orig_state = get_state(SMATCH_EXTRA, name, sym);
519 523
520 524 if (!estate_related(orig_state)) {
521 525 set_true_false_states(SMATCH_EXTRA, name, sym, true_state, false_state);
522 526 return;
523 527 }
524 528
525 529 if (true_state)
526 530 set_related(true_state, estate_related(orig_state));
527 531 if (false_state)
528 532 set_related(false_state, estate_related(orig_state));
529 533
530 534 FOR_EACH_PTR(estate_related(orig_state), rel) {
531 535 set_true_false_states(SMATCH_EXTRA, rel->name, rel->sym,
532 536 true_state, false_state);
533 537 } END_FOR_EACH_PTR(rel);
534 538 }
535 539
536 540 static void set_extra_chunk_true_false(struct expression *expr,
537 541 struct smatch_state *true_state,
538 542 struct smatch_state *false_state)
539 543 {
540 544 struct var_sym_list *vsl;
541 545 struct var_sym *vs;
542 546 struct symbol *type;
543 547 char *name;
544 548 struct symbol *sym;
545 549
546 550 if (in_warn_on_macro())
547 551 return;
548 552
549 553 type = get_type(expr);
550 554 if (!type)
551 555 return;
552 556
553 557 name = expr_to_chunk_sym_vsl(expr, &sym, &vsl);
554 558 if (!name || !vsl)
555 559 goto free;
556 560 FOR_EACH_PTR(vsl, vs) {
557 561 store_link(link_id, vs->var, vs->sym, name, sym);
558 562 } END_FOR_EACH_PTR(vs);
559 563
560 564 set_true_false_states(SMATCH_EXTRA, name, sym,
561 565 clone_estate(true_state),
562 566 clone_estate(false_state));
563 567 free:
564 568 free_string(name);
565 569 }
566 570
567 571 static void set_extra_expr_true_false(struct expression *expr,
568 572 struct smatch_state *true_state,
569 573 struct smatch_state *false_state)
570 574 {
571 575 char *name;
572 576 struct symbol *sym;
573 577 sval_t sval;
574 578
575 579 if (!true_state && !false_state)
576 580 return;
577 581
578 582 if (get_value(expr, &sval))
579 583 return;
580 584
581 585 expr = strip_expr(expr);
582 586 name = expr_to_var_sym(expr, &sym);
583 587 if (!name || !sym) {
584 588 free_string(name);
585 589 set_extra_chunk_true_false(expr, true_state, false_state);
586 590 return;
587 591 }
588 592 set_extra_true_false(name, sym, true_state, false_state);
589 593 free_string(name);
590 594 }
591 595
592 596 static int get_countdown_info(struct expression *condition, struct expression **unop, int *op, sval_t *right)
593 597 {
594 598 struct expression *unop_expr;
595 599 int comparison;
596 600 sval_t limit;
597 601
598 602 right->type = &int_ctype;
599 603 right->value = 0;
600 604
601 605 condition = strip_expr(condition);
602 606
603 607 if (condition->type == EXPR_COMPARE) {
604 608 comparison = remove_unsigned_from_comparison(condition->op);
605 609
606 610 if (comparison != SPECIAL_GTE && comparison != '>')
607 611 return 0;
608 612 if (!get_value(condition->right, &limit))
609 613 return 0;
610 614
611 615 unop_expr = condition->left;
612 616 if (unop_expr->type != EXPR_PREOP && unop_expr->type != EXPR_POSTOP)
613 617 return 0;
614 618 if (unop_expr->op != SPECIAL_DECREMENT)
615 619 return 0;
616 620
617 621 *unop = unop_expr;
618 622 *op = comparison;
619 623 *right = limit;
620 624
621 625 return 1;
622 626 }
623 627
624 628 if (condition->type != EXPR_PREOP && condition->type != EXPR_POSTOP)
625 629 return 0;
626 630 if (condition->op != SPECIAL_DECREMENT)
627 631 return 0;
628 632
629 633 *unop = condition;
630 634 *op = '>';
631 635
632 636 return 1;
633 637 }
634 638
635 639 static struct sm_state *handle_canonical_while_count_down(struct statement *loop)
636 640 {
637 641 struct expression *iter_var;
638 642 struct expression *condition, *unop;
639 643 struct symbol *type;
640 644 struct sm_state *sm;
641 645 struct smatch_state *estate;
642 646 int op;
643 647 sval_t start, right;
644 648
645 649 right.type = &int_ctype;
646 650 right.value = 0;
647 651
648 652 condition = strip_expr(loop->iterator_pre_condition);
649 653 if (!condition)
650 654 return NULL;
651 655
652 656 if (!get_countdown_info(condition, &unop, &op, &right))
653 657 return NULL;
654 658
655 659 iter_var = unop->unop;
656 660
657 661 sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
658 662 if (!sm)
659 663 return NULL;
660 664 if (sval_cmp(estate_min(sm->state), right) < 0)
661 665 return NULL;
662 666 start = estate_max(sm->state);
663 667
664 668 type = get_type(iter_var);
665 669 right = sval_cast(type, right);
666 670 start = sval_cast(type, start);
667 671
668 672 if (sval_cmp(start, right) <= 0)
669 673 return NULL;
670 674 if (!sval_is_max(start))
671 675 start.value--;
672 676
673 677 if (op == SPECIAL_GTE)
674 678 right.value--;
675 679
676 680 if (unop->type == EXPR_PREOP) {
677 681 right.value++;
678 682 estate = alloc_estate_range(right, start);
679 683 if (estate_has_hard_max(sm->state))
680 684 estate_set_hard_max(estate);
681 685 estate_copy_fuzzy_max(estate, sm->state);
682 686 set_extra_expr_mod(iter_var, estate);
683 687 }
684 688 if (unop->type == EXPR_POSTOP) {
685 689 estate = alloc_estate_range(right, start);
686 690 if (estate_has_hard_max(sm->state))
687 691 estate_set_hard_max(estate);
688 692 estate_copy_fuzzy_max(estate, sm->state);
689 693 set_extra_expr_mod(iter_var, estate);
690 694 }
691 695 return get_sm_state_expr(SMATCH_EXTRA, iter_var);
692 696 }
693 697
694 698 static struct sm_state *handle_canonical_for_inc(struct expression *iter_expr,
695 699 struct expression *condition)
696 700 {
697 701 struct expression *iter_var;
698 702 struct sm_state *sm;
699 703 struct smatch_state *estate;
700 704 sval_t start, end, max;
701 705 struct symbol *type;
702 706
703 707 iter_var = iter_expr->unop;
704 708 sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
705 709 if (!sm)
706 710 return NULL;
707 711 if (!estate_get_single_value(sm->state, &start))
708 712 return NULL;
709 713 if (!get_implied_value(condition->right, &end))
710 714 return NULL;
711 715
712 716 if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm)
713 717 return NULL;
714 718
715 719 switch (condition->op) {
716 720 case SPECIAL_UNSIGNED_LT:
717 721 case SPECIAL_NOTEQUAL:
718 722 case '<':
719 723 if (!sval_is_min(end))
720 724 end.value--;
721 725 break;
722 726 case SPECIAL_UNSIGNED_LTE:
723 727 case SPECIAL_LTE:
724 728 break;
725 729 default:
726 730 return NULL;
727 731 }
728 732 if (sval_cmp(end, start) < 0)
729 733 return NULL;
730 734 type = get_type(iter_var);
731 735 start = sval_cast(type, start);
732 736 end = sval_cast(type, end);
733 737 estate = alloc_estate_range(start, end);
734 738 if (get_hard_max(condition->right, &max)) {
735 739 if (!get_macro_name(condition->pos))
736 740 estate_set_hard_max(estate);
737 741 if (condition->op == '<' ||
738 742 condition->op == SPECIAL_UNSIGNED_LT ||
739 743 condition->op == SPECIAL_NOTEQUAL)
740 744 max.value--;
741 745 max = sval_cast(type, max);
742 746 estate_set_fuzzy_max(estate, max);
743 747 }
744 748 set_extra_expr_mod(iter_var, estate);
745 749 return get_sm_state_expr(SMATCH_EXTRA, iter_var);
746 750 }
747 751
748 752 static struct sm_state *handle_canonical_for_dec(struct expression *iter_expr,
749 753 struct expression *condition)
750 754 {
751 755 struct expression *iter_var;
752 756 struct sm_state *sm;
753 757 struct smatch_state *estate;
754 758 sval_t start, end;
755 759
756 760 iter_var = iter_expr->unop;
757 761 sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
758 762 if (!sm)
759 763 return NULL;
760 764 if (!estate_get_single_value(sm->state, &start))
761 765 return NULL;
762 766 if (!get_implied_min(condition->right, &end))
763 767 end = sval_type_min(get_type(iter_var));
764 768 end = sval_cast(estate_type(sm->state), end);
765 769 if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm)
766 770 return NULL;
767 771
768 772 switch (condition->op) {
769 773 case SPECIAL_NOTEQUAL:
770 774 case '>':
771 775 if (!sval_is_max(end))
772 776 end.value++;
773 777 break;
774 778 case SPECIAL_GTE:
775 779 break;
776 780 default:
777 781 return NULL;
778 782 }
779 783 if (sval_cmp(end, start) > 0)
780 784 return NULL;
781 785 estate = alloc_estate_range(end, start);
782 786 estate_set_hard_max(estate);
783 787 estate_set_fuzzy_max(estate, estate_get_fuzzy_max(estate));
784 788 set_extra_expr_mod(iter_var, estate);
785 789 return get_sm_state_expr(SMATCH_EXTRA, iter_var);
786 790 }
787 791
788 792 static struct sm_state *handle_canonical_for_loops(struct statement *loop)
789 793 {
790 794 struct expression *iter_expr;
791 795 struct expression *condition;
792 796
793 797 if (!loop->iterator_post_statement)
794 798 return NULL;
795 799 if (loop->iterator_post_statement->type != STMT_EXPRESSION)
796 800 return NULL;
797 801 iter_expr = loop->iterator_post_statement->expression;
798 802 if (!loop->iterator_pre_condition)
799 803 return NULL;
800 804 if (loop->iterator_pre_condition->type != EXPR_COMPARE)
801 805 return NULL;
802 806 condition = loop->iterator_pre_condition;
803 807
804 808 if (iter_expr->op == SPECIAL_INCREMENT)
805 809 return handle_canonical_for_inc(iter_expr, condition);
806 810 if (iter_expr->op == SPECIAL_DECREMENT)
807 811 return handle_canonical_for_dec(iter_expr, condition);
808 812 return NULL;
809 813 }
810 814
811 815 struct sm_state *__extra_handle_canonical_loops(struct statement *loop, struct stree **stree)
812 816 {
813 817 struct sm_state *ret;
814 818
815 819 /*
816 820 * Canonical loops are a hack. The proper way to handle this is to
817 821 * use two passes, but unfortunately, doing two passes makes parsing
818 822 * code twice as slow.
819 823 *
820 824 * What we do is we set the inside state here, which overwrites whatever
821 825 * __extra_match_condition() does. Then we set the outside state in
822 826 * __extra_pre_loop_hook_after().
823 827 *
824 828 */
825 829 __push_fake_cur_stree();
826 830 if (!loop->iterator_post_statement)
827 831 ret = handle_canonical_while_count_down(loop);
828 832 else
829 833 ret = handle_canonical_for_loops(loop);
830 834 *stree = __pop_fake_cur_stree();
831 835 return ret;
832 836 }
833 837
834 838 int __iterator_unchanged(struct sm_state *sm)
835 839 {
836 840 if (!sm)
837 841 return 0;
838 842 if (get_sm_state(my_id, sm->name, sm->sym) == sm)
839 843 return 1;
840 844 return 0;
841 845 }
842 846
843 847 static void while_count_down_after(struct sm_state *sm, struct expression *condition)
844 848 {
845 849 struct expression *unop;
846 850 int op;
847 851 sval_t limit, after_value;
848 852
849 853 if (!get_countdown_info(condition, &unop, &op, &limit))
850 854 return;
851 855 after_value = estate_min(sm->state);
852 856 after_value.value--;
853 857 set_extra_mod(sm->name, sm->sym, condition->unop, alloc_estate_sval(after_value));
854 858 }
855 859
856 860 void __extra_pre_loop_hook_after(struct sm_state *sm,
857 861 struct statement *iterator,
858 862 struct expression *condition)
859 863 {
860 864 struct expression *iter_expr;
861 865 sval_t limit;
862 866 struct smatch_state *state;
863 867
864 868 if (!iterator) {
865 869 while_count_down_after(sm, condition);
866 870 return;
867 871 }
868 872
869 873 iter_expr = iterator->expression;
870 874
871 875 if (condition->type != EXPR_COMPARE)
872 876 return;
873 877 if (iter_expr->op == SPECIAL_INCREMENT) {
874 878 limit = sval_binop(estate_max(sm->state), '+',
875 879 sval_type_val(estate_type(sm->state), 1));
876 880 } else {
877 881 limit = sval_binop(estate_min(sm->state), '-',
878 882 sval_type_val(estate_type(sm->state), 1));
879 883 }
880 884 limit = sval_cast(estate_type(sm->state), limit);
881 885 if (!estate_has_hard_max(sm->state) && !__has_breaks()) {
882 886 if (iter_expr->op == SPECIAL_INCREMENT)
883 887 state = alloc_estate_range(estate_min(sm->state), limit);
884 888 else
885 889 state = alloc_estate_range(limit, estate_max(sm->state));
886 890 } else {
887 891 state = alloc_estate_sval(limit);
888 892 }
889 893 if (!estate_has_hard_max(sm->state)) {
890 894 estate_clear_hard_max(state);
891 895 }
892 896 if (estate_has_fuzzy_max(sm->state)) {
893 897 sval_t hmax = estate_get_fuzzy_max(sm->state);
894 898 sval_t max = estate_max(sm->state);
895 899
896 900 if (sval_cmp(hmax, max) != 0)
897 901 estate_clear_fuzzy_max(state);
898 902 } else if (!estate_has_fuzzy_max(sm->state)) {
899 903 estate_clear_fuzzy_max(state);
900 904 }
901 905
902 906 set_extra_mod(sm->name, sm->sym, iter_expr, state);
903 907 }
904 908
905 909 static bool get_global_rl(const char *name, struct symbol *sym, struct range_list **rl)
906 910 {
907 911 struct expression *expr;
908 912
909 913 if (!sym || !(sym->ctype.modifiers & MOD_TOPLEVEL) || !sym->ident)
910 914 return false;
911 915 if (strcmp(sym->ident->name, name) != 0)
912 916 return false;
913 917
914 918 expr = symbol_expression(sym);
915 919 return get_implied_rl(expr, rl);
916 920 }
917 921
918 922 static struct stree *unmatched_stree;
919 923 static struct smatch_state *unmatched_state(struct sm_state *sm)
920 924 {
921 925 struct smatch_state *state;
922 926 struct range_list *rl;
923 927
924 928 if (unmatched_stree) {
925 929 state = get_state_stree(unmatched_stree, SMATCH_EXTRA, sm->name, sm->sym);
926 930 if (state)
927 931 return state;
928 932 }
929 933 if (parent_is_gone_var_sym(sm->name, sm->sym))
930 934 return alloc_estate_empty();
931 935 if (get_global_rl(sm->name, sm->sym, &rl))
932 936 return alloc_estate_rl(rl);
933 937 return alloc_estate_whole(estate_type(sm->state));
934 938 }
935 939
936 940 static void clear_the_pointed_at(struct expression *expr)
937 941 {
938 942 struct stree *stree;
939 943 char *name;
940 944 struct symbol *sym;
941 945 struct sm_state *tmp;
942 946
943 947 name = expr_to_var_sym(expr, &sym);
944 948 if (!name || !sym)
945 949 goto free;
946 950
947 951 stree = __get_cur_stree();
948 952 FOR_EACH_MY_SM(SMATCH_EXTRA, stree, tmp) {
949 953 if (tmp->name[0] != '*')
950 954 continue;
951 955 if (tmp->sym != sym)
952 956 continue;
953 957 if (strcmp(tmp->name + 1, name) != 0)
954 958 continue;
955 959 set_extra_mod(tmp->name, tmp->sym, expr, alloc_estate_whole(estate_type(tmp->state)));
956 960 } END_FOR_EACH_SM(tmp);
957 961
958 962 free:
959 963 free_string(name);
960 964 }
961 965
962 966 static int is_const_param(struct expression *expr, int param)
963 967 {
964 968 struct symbol *type;
965 969
966 970 type = get_arg_type(expr, param);
967 971 if (!type)
968 972 return 0;
969 973 if (type->ctype.modifiers & MOD_CONST)
970 974 return 1;
971 975 return 0;
972 976 }
973 977
974 978 static void match_function_call(struct expression *expr)
975 979 {
976 980 struct expression *arg;
977 981 struct expression *tmp;
978 982 int param = -1;
979 983
980 984 /* if we have the db this is handled in smatch_function_hooks.c */
981 985 if (!option_no_db)
982 986 return;
983 987 if (inlinable(expr->fn))
984 988 return;
985 989
986 990 FOR_EACH_PTR(expr->args, arg) {
987 991 param++;
988 992 if (is_const_param(expr->fn, param))
989 993 continue;
990 994 tmp = strip_expr(arg);
991 995 if (tmp->type == EXPR_PREOP && tmp->op == '&')
992 996 set_extra_expr_mod(tmp->unop, alloc_estate_whole(get_type(tmp->unop)));
993 997 else
994 998 clear_the_pointed_at(tmp);
995 999 } END_FOR_EACH_PTR(arg);
996 1000 }
997 1001
998 1002 int values_fit_type(struct expression *left, struct expression *right)
999 1003 {
1000 1004 struct range_list *rl;
1001 1005 struct symbol *type;
1002 1006
1003 1007 type = get_type(left);
1004 1008 if (!type)
1005 1009 return 0;
1006 1010 get_absolute_rl(right, &rl);
1007 1011 if (type == rl_type(rl))
1008 1012 return 1;
1009 1013 if (type_unsigned(type) && sval_is_negative(rl_min(rl)))
1010 1014 return 0;
1011 1015 if (sval_cmp(sval_type_min(type), rl_min(rl)) > 0)
1012 1016 return 0;
1013 1017 if (sval_cmp(sval_type_max(type), rl_max(rl)) < 0)
1014 1018 return 0;
1015 1019 return 1;
1016 1020 }
1017 1021
1018 1022 static void save_chunk_info(struct expression *left, struct expression *right)
1019 1023 {
1020 1024 struct var_sym_list *vsl;
1021 1025 struct var_sym *vs;
1022 1026 struct expression *add_expr;
1023 1027 struct symbol *type;
1024 1028 sval_t sval;
1025 1029 char *name;
1026 1030 struct symbol *sym;
1027 1031
1028 1032 if (right->type != EXPR_BINOP || right->op != '-')
1029 1033 return;
1030 1034 if (!get_value(right->left, &sval))
1031 1035 return;
1032 1036 if (!expr_to_sym(right->right))
1033 1037 return;
1034 1038
1035 1039 add_expr = binop_expression(left, '+', right->right);
1036 1040 type = get_type(add_expr);
1037 1041 if (!type)
1038 1042 return;
1039 1043 name = expr_to_chunk_sym_vsl(add_expr, &sym, &vsl);
1040 1044 if (!name || !vsl)
1041 1045 goto free;
1042 1046 FOR_EACH_PTR(vsl, vs) {
1043 1047 store_link(link_id, vs->var, vs->sym, name, sym);
1044 1048 } END_FOR_EACH_PTR(vs);
1045 1049
1046 1050 set_state(SMATCH_EXTRA, name, sym, alloc_estate_sval(sval_cast(type, sval)));
1047 1051 free:
1048 1052 free_string(name);
1049 1053 }
1050 1054
1051 1055 static void do_array_assign(struct expression *left, int op, struct expression *right)
1052 1056 {
1053 1057 struct range_list *rl;
1054 1058
1055 1059 if (op == '=') {
1056 1060 get_absolute_rl(right, &rl);
1057 1061 rl = cast_rl(get_type(left), rl);
1058 1062 } else {
1059 1063 rl = alloc_whole_rl(get_type(left));
1060 1064 }
1061 1065
1062 1066 set_extra_array_mod(left, alloc_estate_rl(rl));
1063 1067 }
1064 1068
1065 1069 static void match_vanilla_assign(struct expression *left, struct expression *right)
1066 1070 {
1067 1071 struct range_list *orig_rl = NULL;
1068 1072 struct range_list *rl = NULL;
1069 1073 struct symbol *right_sym;
1070 1074 struct symbol *left_type;
1071 1075 struct symbol *right_type;
1072 1076 char *right_name = NULL;
1073 1077 struct symbol *sym;
1074 1078 char *name;
1075 1079 sval_t sval, max;
1076 1080 struct smatch_state *state;
1077 1081 int comparison;
1078 1082
1079 1083 if (is_struct(left))
1080 1084 return;
1081 1085
1082 1086 save_chunk_info(left, right);
1083 1087
1084 1088 name = expr_to_var_sym(left, &sym);
1085 1089 if (!name) {
1086 1090 if (chunk_has_array(left))
1087 1091 do_array_assign(left, '=', right);
1088 1092 return;
1089 1093 }
1090 1094
1091 1095 left_type = get_type(left);
1092 1096 right_type = get_type(right);
1093 1097
1094 1098 right_name = expr_to_var_sym(right, &right_sym);
1095 1099
1096 1100 if (!__in_fake_assign &&
1097 1101 !(right->type == EXPR_PREOP && right->op == '&') &&
1098 1102 right_name && right_sym &&
1099 1103 values_fit_type(left, strip_expr(right)) &&
1100 1104 !has_symbol(right, sym)) {
1101 1105 set_equiv(left, right);
1102 1106 goto free;
1103 1107 }
1104 1108
1105 1109 if (get_implied_value(right, &sval)) {
1106 1110 state = alloc_estate_sval(sval_cast(left_type, sval));
1107 1111 goto done;
1108 1112 }
1109 1113
1110 1114 if (__in_fake_assign) {
1111 1115 struct smatch_state *right_state;
1112 1116 sval_t sval;
1113 1117
1114 1118 if (get_value(right, &sval)) {
1115 1119 sval = sval_cast(left_type, sval);
1116 1120 state = alloc_estate_sval(sval);
1117 1121 goto done;
1118 1122 }
1119 1123
1120 1124 right_state = get_state(SMATCH_EXTRA, right_name, right_sym);
1121 1125 if (right_state) {
1122 1126 /* simple assignment */
1123 1127 state = clone_estate(right_state);
1124 1128 goto done;
1125 1129 }
1126 1130
1127 1131 state = alloc_estate_rl(alloc_whole_rl(left_type));
1128 1132 goto done;
1129 1133 }
1130 1134
1131 1135 comparison = get_comparison_no_extra(left, right);
1132 1136 if (comparison) {
1133 1137 comparison = flip_comparison(comparison);
1134 1138 get_implied_rl(left, &orig_rl);
1135 1139 }
1136 1140
1137 1141 if (get_implied_rl(right, &rl)) {
1138 1142 rl = cast_rl(left_type, rl);
1139 1143 if (orig_rl)
1140 1144 filter_by_comparison(&rl, comparison, orig_rl);
1141 1145 state = alloc_estate_rl(rl);
1142 1146 if (get_hard_max(right, &max)) {
1143 1147 estate_set_hard_max(state);
1144 1148 estate_set_fuzzy_max(state, max);
1145 1149 }
1146 1150 } else {
1147 1151 rl = alloc_whole_rl(right_type);
1148 1152 rl = cast_rl(left_type, rl);
1149 1153 if (orig_rl)
1150 1154 filter_by_comparison(&rl, comparison, orig_rl);
1151 1155 state = alloc_estate_rl(rl);
1152 1156 }
1153 1157
1154 1158 done:
1155 1159 set_extra_mod(name, sym, left, state);
1156 1160 free:
1157 1161 free_string(right_name);
1158 1162 }
1159 1163
1160 1164 static void match_assign(struct expression *expr)
1161 1165 {
1162 1166 struct range_list *rl = NULL;
1163 1167 struct expression *left;
1164 1168 struct expression *right;
1165 1169 struct expression *binop_expr;
1166 1170 struct symbol *left_type;
1167 1171 struct symbol *sym;
1168 1172 char *name;
1169 1173
1170 1174 left = strip_expr(expr->left);
1171 1175
1172 1176 right = strip_parens(expr->right);
1173 1177 if (right->type == EXPR_CALL && sym_name_is("__builtin_expect", right->fn))
1174 1178 right = get_argument_from_call_expr(right->args, 0);
1175 1179 while (right->type == EXPR_ASSIGNMENT && right->op == '=')
1176 1180 right = strip_parens(right->left);
1177 1181
1178 1182 if (expr->op == '=' && is_condition(expr->right))
1179 1183 return; /* handled in smatch_condition.c */
1180 1184 if (expr->op == '=' && right->type == EXPR_CALL)
1181 1185 return; /* handled in smatch_function_hooks.c */
1182 1186 if (expr->op == '=') {
1183 1187 match_vanilla_assign(left, right);
1184 1188 return;
1185 1189 }
1186 1190
1187 1191 name = expr_to_var_sym(left, &sym);
1188 1192 if (!name)
1189 1193 return;
1190 1194
1191 1195 left_type = get_type(left);
1192 1196
1193 1197 switch (expr->op) {
1194 1198 case SPECIAL_ADD_ASSIGN:
1195 1199 case SPECIAL_SUB_ASSIGN:
1196 1200 case SPECIAL_AND_ASSIGN:
1197 1201 case SPECIAL_MOD_ASSIGN:
1198 1202 case SPECIAL_SHL_ASSIGN:
1199 1203 case SPECIAL_SHR_ASSIGN:
1200 1204 case SPECIAL_OR_ASSIGN:
1201 1205 case SPECIAL_XOR_ASSIGN:
1202 1206 case SPECIAL_MUL_ASSIGN:
1203 1207 case SPECIAL_DIV_ASSIGN:
1204 1208 binop_expr = binop_expression(expr->left,
1205 1209 op_remove_assign(expr->op),
1206 1210 expr->right);
1207 1211 get_absolute_rl(binop_expr, &rl);
1208 1212 rl = cast_rl(left_type, rl);
1209 1213 if (inside_loop()) {
1210 1214 if (expr->op == SPECIAL_ADD_ASSIGN)
1211 1215 add_range(&rl, rl_max(rl), sval_type_max(rl_type(rl)));
1212 1216
1213 1217 if (expr->op == SPECIAL_SUB_ASSIGN &&
1214 1218 !sval_is_negative(rl_min(rl))) {
1215 1219 sval_t zero = { .type = rl_type(rl) };
1216 1220
1217 1221 add_range(&rl, rl_min(rl), zero);
1218 1222 }
1219 1223 }
1220 1224 set_extra_mod(name, sym, left, alloc_estate_rl(rl));
1221 1225 goto free;
1222 1226 }
1223 1227 set_extra_mod(name, sym, left, alloc_estate_whole(left_type));
1224 1228 free:
1225 1229 free_string(name);
1226 1230 }
1227 1231
1228 1232 static struct smatch_state *increment_state(struct smatch_state *state)
1229 1233 {
1230 1234 sval_t min = estate_min(state);
1231 1235 sval_t max = estate_max(state);
1232 1236
1233 1237 if (!estate_rl(state))
1234 1238 return NULL;
1235 1239
1236 1240 if (inside_loop())
1237 1241 max = sval_type_max(max.type);
1238 1242
1239 1243 if (!sval_is_min(min) && !sval_is_max(min))
1240 1244 min.value++;
1241 1245 if (!sval_is_min(max) && !sval_is_max(max))
1242 1246 max.value++;
1243 1247 return alloc_estate_range(min, max);
1244 1248 }
1245 1249
1246 1250 static struct smatch_state *decrement_state(struct smatch_state *state)
1247 1251 {
1248 1252 sval_t min = estate_min(state);
1249 1253 sval_t max = estate_max(state);
1250 1254
1251 1255 if (!estate_rl(state))
1252 1256 return NULL;
1253 1257
1254 1258 if (inside_loop())
1255 1259 min = sval_type_min(min.type);
1256 1260
1257 1261 if (!sval_is_min(min) && !sval_is_max(min))
1258 1262 min.value--;
1259 1263 if (!sval_is_min(max) && !sval_is_max(max))
1260 1264 max.value--;
1261 1265 return alloc_estate_range(min, max);
1262 1266 }
1263 1267
1264 1268 static void clear_pointed_at_state(struct expression *expr)
1265 1269 {
1266 1270 struct symbol *type;
1267 1271
1268 1272 /*
1269 1273 * ALERT: This is sort of a mess. If it's is a struct assigment like
1270 1274 * "foo = bar;", then that's handled by smatch_struct_assignment.c.
1271 1275 * the same thing for p++ where "p" is a struct. Most modifications
1272 1276 * are handled by the assignment hook or the db. Smatch_extra.c doesn't
1273 1277 * use smatch_modification.c because we have to get the ordering right
1274 1278 * or something. So if you have p++ where p is a pointer to a standard
1275 1279 * c type then we handle that here. What a mess.
1276 1280 */
1277 1281 expr = strip_expr(expr);
1278 1282 type = get_type(expr);
1279 1283 if (!type || type->type != SYM_PTR)
1280 1284 return;
1281 1285 type = get_real_base_type(type);
1282 1286 if (!type || type->type != SYM_BASETYPE)
1283 1287 return;
1284 1288 set_extra_expr_nomod(deref_expression(expr), alloc_estate_whole(type));
1285 1289 }
1286 1290
1287 1291 static void unop_expr(struct expression *expr)
1288 1292 {
1289 1293 struct smatch_state *state;
1290 1294
1291 1295 if (expr->smatch_flags & Handled)
1292 1296 return;
1293 1297
1294 1298 switch (expr->op) {
1295 1299 case SPECIAL_INCREMENT:
1296 1300 state = get_state_expr(SMATCH_EXTRA, expr->unop);
1297 1301 state = increment_state(state);
1298 1302 if (!state)
1299 1303 state = alloc_estate_whole(get_type(expr));
1300 1304 set_extra_expr_mod(expr->unop, state);
1301 1305 clear_pointed_at_state(expr->unop);
1302 1306 break;
1303 1307 case SPECIAL_DECREMENT:
1304 1308 state = get_state_expr(SMATCH_EXTRA, expr->unop);
1305 1309 state = decrement_state(state);
1306 1310 if (!state)
1307 1311 state = alloc_estate_whole(get_type(expr));
1308 1312 set_extra_expr_mod(expr->unop, state);
1309 1313 clear_pointed_at_state(expr->unop);
1310 1314 break;
1311 1315 default:
1312 1316 return;
1313 1317 }
1314 1318 }
1315 1319
1316 1320 static void asm_expr(struct statement *stmt)
1317 1321 {
1318 1322
1319 1323 struct expression *expr;
1320 1324 struct symbol *type;
1321 1325
1322 1326 FOR_EACH_PTR(stmt->asm_outputs, expr) {
1323 1327 if (expr->type != EXPR_ASM_OPERAND) {
1324 1328 sm_perror("unexpected asm param type %d", expr->type);
1325 1329 continue;
1326 1330 }
1327 1331 type = get_type(strip_expr(expr->expr));
1328 1332 set_extra_expr_mod(expr->expr, alloc_estate_whole(type));
1329 1333 } END_FOR_EACH_PTR(expr);
1330 1334 }
1331 1335
1332 1336 static void check_dereference(struct expression *expr)
1333 1337 {
1334 1338 struct smatch_state *state;
1335 1339
1336 1340 if (__in_fake_assign)
1337 1341 return;
1338 1342 if (outside_of_function())
1339 1343 return;
1340 1344 state = get_extra_state(expr);
1341 1345 if (state) {
1342 1346 struct range_list *rl;
1343 1347
1344 1348 rl = rl_intersection(estate_rl(state), valid_ptr_rl);
1345 1349 if (rl_equiv(rl, estate_rl(state)))
1346 1350 return;
1347 1351 set_extra_expr_nomod(expr, alloc_estate_rl(rl));
1348 1352 } else {
1349 1353 struct range_list *rl;
1350 1354
1351 1355 if (get_mtag_rl(expr, &rl))
1352 1356 rl = rl_intersection(rl, valid_ptr_rl);
1353 1357 else
1354 1358 rl = clone_rl(valid_ptr_rl);
1355 1359
1356 1360 set_extra_expr_nomod(expr, alloc_estate_rl(rl));
1357 1361 }
1358 1362 }
1359 1363
1360 1364 static void match_dereferences(struct expression *expr)
1361 1365 {
1362 1366 if (expr->type != EXPR_PREOP)
1363 1367 return;
1364 1368 if (getting_address(expr))
1365 1369 return;
1366 1370 /* it's saying that foo[1] = bar dereferences foo[1] */
1367 1371 if (is_array(expr))
1368 1372 return;
1369 1373 check_dereference(expr->unop);
1370 1374 }
1371 1375
1372 1376 static void match_pointer_as_array(struct expression *expr)
1373 1377 {
1374 1378 if (!is_array(expr))
1375 1379 return;
1376 1380 check_dereference(get_array_base(expr));
1377 1381 }
1378 1382
1379 1383 static void find_dereferences(struct expression *expr)
1380 1384 {
1381 1385 while (expr->type == EXPR_PREOP) {
1382 1386 if (expr->op == '*')
1383 1387 check_dereference(expr->unop);
1384 1388 expr = strip_expr(expr->unop);
1385 1389 }
1386 1390 }
1387 1391
1388 1392 static void set_param_dereferenced(struct expression *call, struct expression *arg, char *key, char *unused)
1389 1393 {
1390 1394 struct symbol *sym;
1391 1395 char *name;
1392 1396
1393 1397 name = get_variable_from_key(arg, key, &sym);
1394 1398 if (name && sym) {
1395 1399 struct smatch_state *orig, *new;
1396 1400 struct range_list *rl;
1397 1401
1398 1402 orig = get_state(SMATCH_EXTRA, name, sym);
1399 1403 if (orig) {
1400 1404 rl = rl_intersection(estate_rl(orig),
1401 1405 alloc_rl(valid_ptr_min_sval,
1402 1406 valid_ptr_max_sval));
1403 1407 new = alloc_estate_rl(rl);
1404 1408 } else {
1405 1409 new = alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval);
1406 1410 }
1407 1411
1408 1412 set_extra_nomod(name, sym, NULL, new);
1409 1413 }
1410 1414 free_string(name);
1411 1415
1412 1416 find_dereferences(arg);
1413 1417 }
1414 1418
1415 1419 static sval_t add_one(sval_t sval)
1416 1420 {
1417 1421 sval.value++;
1418 1422 return sval;
1419 1423 }
1420 1424
1421 1425 static int handle_postop_inc(struct expression *left, int op, struct expression *right)
1422 1426 {
1423 1427 struct statement *stmt;
1424 1428 struct expression *cond;
1425 1429 struct smatch_state *true_state, *false_state;
1426 1430 struct symbol *type;
1427 1431 sval_t start;
1428 1432 sval_t limit;
1429 1433
1430 1434 /*
1431 1435 * If we're decrementing here then that's a canonical while count down
1432 1436 * so it's handled already. We're only handling loops like:
1433 1437 * i = 0;
1434 1438 * do { ... } while (i++ < 3);
1435 1439 */
1436 1440
1437 1441 if (left->type != EXPR_POSTOP || left->op != SPECIAL_INCREMENT)
1438 1442 return 0;
1439 1443
1440 1444 stmt = __cur_stmt->parent;
1441 1445 if (!stmt)
1442 1446 return 0;
1443 1447 if (stmt->type == STMT_COMPOUND)
1444 1448 stmt = stmt->parent;
1445 1449 if (!stmt || stmt->type != STMT_ITERATOR || !stmt->iterator_post_condition)
1446 1450 return 0;
1447 1451
1448 1452 cond = strip_expr(stmt->iterator_post_condition);
1449 1453 if (cond->type != EXPR_COMPARE || cond->op != op)
1450 1454 return 0;
1451 1455 if (left != strip_expr(cond->left) || right != strip_expr(cond->right))
1452 1456 return 0;
1453 1457
1454 1458 if (!get_implied_value(left->unop, &start))
1455 1459 return 0;
1456 1460 if (!get_implied_value(right, &limit))
1457 1461 return 0;
1458 1462 type = get_type(left->unop);
1459 1463 limit = sval_cast(type, limit);
1460 1464 if (sval_cmp(start, limit) > 0)
1461 1465 return 0;
1462 1466
1463 1467 switch (op) {
1464 1468 case '<':
1465 1469 case SPECIAL_UNSIGNED_LT:
1466 1470 break;
1467 1471 case SPECIAL_LTE:
1468 1472 case SPECIAL_UNSIGNED_LTE:
1469 1473 limit = add_one(limit);
1470 1474 default:
1471 1475 return 0;
1472 1476
1473 1477 }
1474 1478
1475 1479 true_state = alloc_estate_range(add_one(start), limit);
1476 1480 false_state = alloc_estate_range(add_one(limit), add_one(limit));
1477 1481
1478 1482 /* Currently we just discard the false state but when two passes is
1479 1483 * implimented correctly then it will use it.
1480 1484 */
1481 1485
1482 1486 set_extra_expr_true_false(left->unop, true_state, false_state);
1483 1487
1484 1488 return 1;
1485 1489 }
1486 1490
1487 1491 bool is_impossible_variable(struct expression *expr)
1488 1492 {
1489 1493 struct smatch_state *state;
1490 1494
1491 1495 state = get_extra_state(expr);
1492 1496 if (state && !estate_rl(state))
1493 1497 return true;
1494 1498 return false;
1495 1499 }
1496 1500
1497 1501 static bool in_macro(struct expression *left, struct expression *right)
1498 1502 {
1499 1503 if (!left || !right)
1500 1504 return 0;
1501 1505 if (left->pos.line != right->pos.line || left->pos.pos != right->pos.pos)
1502 1506 return 0;
1503 1507 if (get_macro_name(left->pos))
1504 1508 return 1;
1505 1509 return 0;
1506 1510 }
1507 1511
1508 1512 static void handle_comparison(struct symbol *type, struct expression *left, int op, struct expression *right)
1509 1513 {
1510 1514 struct range_list *left_orig;
1511 1515 struct range_list *left_true;
1512 1516 struct range_list *left_false;
1513 1517 struct range_list *right_orig;
1514 1518 struct range_list *right_true;
1515 1519 struct range_list *right_false;
1516 1520 struct smatch_state *left_true_state;
1517 1521 struct smatch_state *left_false_state;
1518 1522 struct smatch_state *right_true_state;
1519 1523 struct smatch_state *right_false_state;
1520 1524 sval_t dummy, hard_max;
1521 1525 int left_postop = 0;
1522 1526 int right_postop = 0;
1523 1527
1524 1528 if (left->op == SPECIAL_INCREMENT || left->op == SPECIAL_DECREMENT) {
1525 1529 if (left->type == EXPR_POSTOP) {
1526 1530 left->smatch_flags |= Handled;
1527 1531 left_postop = left->op;
1528 1532 if (handle_postop_inc(left, op, right))
1529 1533 return;
1530 1534 }
1531 1535 left = strip_parens(left->unop);
1532 1536 }
1533 1537 while (left->type == EXPR_ASSIGNMENT)
1534 1538 left = strip_parens(left->left);
1535 1539
1536 1540 if (right->op == SPECIAL_INCREMENT || right->op == SPECIAL_DECREMENT) {
1537 1541 if (right->type == EXPR_POSTOP) {
1538 1542 right->smatch_flags |= Handled;
1539 1543 right_postop = right->op;
1540 1544 }
1541 1545 right = strip_parens(right->unop);
1542 1546 }
1543 1547
1544 1548 if (is_impossible_variable(left) || is_impossible_variable(right))
1545 1549 return;
1546 1550
1547 1551 get_real_absolute_rl(left, &left_orig);
1548 1552 left_orig = cast_rl(type, left_orig);
1549 1553
1550 1554 get_real_absolute_rl(right, &right_orig);
1551 1555 right_orig = cast_rl(type, right_orig);
1552 1556
1553 1557 split_comparison_rl(left_orig, op, right_orig, &left_true, &left_false, &right_true, &right_false);
1554 1558
1555 1559 left_true = rl_truncate_cast(get_type(strip_expr(left)), left_true);
1556 1560 left_false = rl_truncate_cast(get_type(strip_expr(left)), left_false);
1557 1561 right_true = rl_truncate_cast(get_type(strip_expr(right)), right_true);
1558 1562 right_false = rl_truncate_cast(get_type(strip_expr(right)), right_false);
1559 1563
1560 1564 if (!left_true || !left_false) {
1561 1565 struct range_list *tmp_true, *tmp_false;
1562 1566
1563 1567 split_comparison_rl(alloc_whole_rl(type), op, right_orig, &tmp_true, &tmp_false, NULL, NULL);
1564 1568 tmp_true = rl_truncate_cast(get_type(strip_expr(left)), tmp_true);
1565 1569 tmp_false = rl_truncate_cast(get_type(strip_expr(left)), tmp_false);
1566 1570 if (tmp_true && tmp_false)
1567 1571 __save_imaginary_state(left, tmp_true, tmp_false);
1568 1572 }
1569 1573
1570 1574 if (!right_true || !right_false) {
1571 1575 struct range_list *tmp_true, *tmp_false;
1572 1576
1573 1577 split_comparison_rl(alloc_whole_rl(type), op, right_orig, NULL, NULL, &tmp_true, &tmp_false);
1574 1578 tmp_true = rl_truncate_cast(get_type(strip_expr(right)), tmp_true);
1575 1579 tmp_false = rl_truncate_cast(get_type(strip_expr(right)), tmp_false);
1576 1580 if (tmp_true && tmp_false)
1577 1581 __save_imaginary_state(right, tmp_true, tmp_false);
1578 1582 }
1579 1583
1580 1584 left_true_state = alloc_estate_rl(left_true);
1581 1585 left_false_state = alloc_estate_rl(left_false);
1582 1586 right_true_state = alloc_estate_rl(right_true);
1583 1587 right_false_state = alloc_estate_rl(right_false);
1584 1588
1585 1589 switch (op) {
1586 1590 case '<':
1587 1591 case SPECIAL_UNSIGNED_LT:
1588 1592 case SPECIAL_UNSIGNED_LTE:
1589 1593 case SPECIAL_LTE:
1590 1594 if (get_implied_value(right, &dummy) && !in_macro(left, right))
1591 1595 estate_set_hard_max(left_true_state);
1592 1596 if (get_implied_value(left, &dummy) && !in_macro(left, right))
1593 1597 estate_set_hard_max(right_false_state);
1594 1598 break;
1595 1599 case '>':
1596 1600 case SPECIAL_UNSIGNED_GT:
1597 1601 case SPECIAL_UNSIGNED_GTE:
1598 1602 case SPECIAL_GTE:
1599 1603 if (get_implied_value(left, &dummy) && !in_macro(left, right))
1600 1604 estate_set_hard_max(right_true_state);
1601 1605 if (get_implied_value(right, &dummy) && !in_macro(left, right))
1602 1606 estate_set_hard_max(left_false_state);
1603 1607 break;
1604 1608 }
1605 1609
1606 1610 switch (op) {
1607 1611 case '<':
1608 1612 case SPECIAL_UNSIGNED_LT:
1609 1613 case SPECIAL_UNSIGNED_LTE:
1610 1614 case SPECIAL_LTE:
1611 1615 if (get_hard_max(right, &hard_max)) {
1612 1616 if (op == '<' || op == SPECIAL_UNSIGNED_LT)
1613 1617 hard_max.value--;
1614 1618 estate_set_fuzzy_max(left_true_state, hard_max);
1615 1619 }
1616 1620 if (get_implied_value(right, &hard_max)) {
1617 1621 if (op == SPECIAL_UNSIGNED_LTE ||
1618 1622 op == SPECIAL_LTE)
1619 1623 hard_max.value++;
1620 1624 estate_set_fuzzy_max(left_false_state, hard_max);
1621 1625 }
1622 1626 if (get_hard_max(left, &hard_max)) {
1623 1627 if (op == SPECIAL_UNSIGNED_LTE ||
1624 1628 op == SPECIAL_LTE)
1625 1629 hard_max.value--;
1626 1630 estate_set_fuzzy_max(right_false_state, hard_max);
1627 1631 }
1628 1632 if (get_implied_value(left, &hard_max)) {
1629 1633 if (op == '<' || op == SPECIAL_UNSIGNED_LT)
1630 1634 hard_max.value++;
1631 1635 estate_set_fuzzy_max(right_true_state, hard_max);
1632 1636 }
1633 1637 break;
1634 1638 case '>':
1635 1639 case SPECIAL_UNSIGNED_GT:
1636 1640 case SPECIAL_UNSIGNED_GTE:
1637 1641 case SPECIAL_GTE:
1638 1642 if (get_hard_max(left, &hard_max)) {
1639 1643 if (op == '>' || op == SPECIAL_UNSIGNED_GT)
1640 1644 hard_max.value--;
1641 1645 estate_set_fuzzy_max(right_true_state, hard_max);
1642 1646 }
1643 1647 if (get_implied_value(left, &hard_max)) {
1644 1648 if (op == SPECIAL_UNSIGNED_GTE ||
1645 1649 op == SPECIAL_GTE)
1646 1650 hard_max.value++;
1647 1651 estate_set_fuzzy_max(right_false_state, hard_max);
1648 1652 }
1649 1653 if (get_hard_max(right, &hard_max)) {
1650 1654 if (op == SPECIAL_UNSIGNED_LTE ||
1651 1655 op == SPECIAL_LTE)
1652 1656 hard_max.value--;
1653 1657 estate_set_fuzzy_max(left_false_state, hard_max);
1654 1658 }
1655 1659 if (get_implied_value(right, &hard_max)) {
1656 1660 if (op == '>' ||
1657 1661 op == SPECIAL_UNSIGNED_GT)
1658 1662 hard_max.value++;
1659 1663 estate_set_fuzzy_max(left_true_state, hard_max);
1660 1664 }
1661 1665 break;
1662 1666 case SPECIAL_EQUAL:
1663 1667 if (get_hard_max(left, &hard_max))
1664 1668 estate_set_fuzzy_max(right_true_state, hard_max);
1665 1669 if (get_hard_max(right, &hard_max))
1666 1670 estate_set_fuzzy_max(left_true_state, hard_max);
1667 1671 break;
1668 1672 }
1669 1673
1670 1674 if (get_hard_max(left, &hard_max)) {
1671 1675 estate_set_hard_max(left_true_state);
1672 1676 estate_set_hard_max(left_false_state);
1673 1677 }
1674 1678 if (get_hard_max(right, &hard_max)) {
1675 1679 estate_set_hard_max(right_true_state);
1676 1680 estate_set_hard_max(right_false_state);
1677 1681 }
1678 1682
1679 1683 if (left_postop == SPECIAL_INCREMENT) {
1680 1684 left_true_state = increment_state(left_true_state);
1681 1685 left_false_state = increment_state(left_false_state);
1682 1686 }
1683 1687 if (left_postop == SPECIAL_DECREMENT) {
1684 1688 left_true_state = decrement_state(left_true_state);
1685 1689 left_false_state = decrement_state(left_false_state);
1686 1690 }
1687 1691 if (right_postop == SPECIAL_INCREMENT) {
1688 1692 right_true_state = increment_state(right_true_state);
1689 1693 right_false_state = increment_state(right_false_state);
1690 1694 }
1691 1695 if (right_postop == SPECIAL_DECREMENT) {
1692 1696 right_true_state = decrement_state(right_true_state);
1693 1697 right_false_state = decrement_state(right_false_state);
1694 1698 }
1695 1699
1696 1700 if (estate_rl(left_true_state) && estates_equiv(left_true_state, left_false_state)) {
1697 1701 left_true_state = NULL;
1698 1702 left_false_state = NULL;
1699 1703 }
1700 1704
1701 1705 if (estate_rl(right_true_state) && estates_equiv(right_true_state, right_false_state)) {
1702 1706 right_true_state = NULL;
1703 1707 right_false_state = NULL;
1704 1708 }
1705 1709
1706 1710 /* Don't introduce new states for known true/false conditions */
1707 1711 if (rl_equiv(left_orig, estate_rl(left_true_state)))
1708 1712 left_true_state = NULL;
1709 1713 if (rl_equiv(left_orig, estate_rl(left_false_state)))
1710 1714 left_false_state = NULL;
1711 1715 if (rl_equiv(right_orig, estate_rl(right_true_state)))
1712 1716 right_true_state = NULL;
1713 1717 if (rl_equiv(right_orig, estate_rl(right_false_state)))
1714 1718 right_false_state = NULL;
1715 1719
1716 1720 set_extra_expr_true_false(left, left_true_state, left_false_state);
1717 1721 set_extra_expr_true_false(right, right_true_state, right_false_state);
1718 1722 }
1719 1723
1720 1724 static int is_simple_math(struct expression *expr)
1721 1725 {
1722 1726 if (!expr)
1723 1727 return 0;
1724 1728 if (expr->type != EXPR_BINOP)
1725 1729 return 0;
1726 1730 switch (expr->op) {
1727 1731 case '+':
1728 1732 case '-':
1729 1733 case '*':
1730 1734 return 1;
1731 1735 }
1732 1736 return 0;
1733 1737 }
1734 1738
1735 1739 static int flip_op(int op)
1736 1740 {
1737 1741 /* We only care about simple math */
1738 1742 switch (op) {
1739 1743 case '+':
1740 1744 return '-';
1741 1745 case '-':
1742 1746 return '+';
1743 1747 case '*':
1744 1748 return '/';
1745 1749 }
1746 1750 return 0;
1747 1751 }
1748 1752
1749 1753 static void move_known_to_rl(struct expression **expr_p, struct range_list **rl_p)
1750 1754 {
1751 1755 struct expression *expr = *expr_p;
1752 1756 struct range_list *rl = *rl_p;
1753 1757 sval_t sval;
1754 1758
1755 1759 if (!is_simple_math(expr))
1756 1760 return;
1757 1761
1758 1762 if (get_implied_value(expr->right, &sval)) {
1759 1763 *expr_p = expr->left;
1760 1764 *rl_p = rl_binop(rl, flip_op(expr->op), alloc_rl(sval, sval));
1761 1765 move_known_to_rl(expr_p, rl_p);
1762 1766 return;
1763 1767 }
1764 1768 if (expr->op == '-')
1765 1769 return;
1766 1770 if (get_implied_value(expr->left, &sval)) {
1767 1771 *expr_p = expr->right;
1768 1772 *rl_p = rl_binop(rl, flip_op(expr->op), alloc_rl(sval, sval));
1769 1773 move_known_to_rl(expr_p, rl_p);
1770 1774 return;
1771 1775 }
1772 1776 }
1773 1777
1774 1778 static void move_known_values(struct expression **left_p, struct expression **right_p)
1775 1779 {
1776 1780 struct expression *left = *left_p;
1777 1781 struct expression *right = *right_p;
1778 1782 sval_t sval, dummy;
1779 1783
1780 1784 if (get_implied_value(left, &sval)) {
1781 1785 if (!is_simple_math(right))
1782 1786 return;
1783 1787 if (get_implied_value(right, &dummy))
1784 1788 return;
1785 1789 if (right->op == '*') {
1786 1790 sval_t divisor;
1787 1791
1788 1792 if (!get_value(right->right, &divisor))
1789 1793 return;
1790 1794 if (divisor.value == 0)
1791 1795 return;
1792 1796 *left_p = binop_expression(left, invert_op(right->op), right->right);
1793 1797 *right_p = right->left;
1794 1798 return;
1795 1799 }
1796 1800 if (right->op == '+' && get_value(right->left, &sval)) {
1797 1801 *left_p = binop_expression(left, invert_op(right->op), right->left);
1798 1802 *right_p = right->right;
1799 1803 return;
1800 1804 }
1801 1805 if (get_value(right->right, &sval)) {
1802 1806 *left_p = binop_expression(left, invert_op(right->op), right->right);
1803 1807 *right_p = right->left;
1804 1808 return;
1805 1809 }
1806 1810 return;
1807 1811 }
1808 1812 if (get_implied_value(right, &sval)) {
1809 1813 if (!is_simple_math(left))
1810 1814 return;
1811 1815 if (get_implied_value(left, &dummy))
1812 1816 return;
1813 1817 if (left->op == '*') {
1814 1818 sval_t divisor;
1815 1819
1816 1820 if (!get_value(left->right, &divisor))
1817 1821 return;
1818 1822 if (divisor.value == 0)
1819 1823 return;
1820 1824 *right_p = binop_expression(right, invert_op(left->op), left->right);
1821 1825 *left_p = left->left;
1822 1826 return;
1823 1827 }
1824 1828 if (left->op == '+' && get_value(left->left, &sval)) {
1825 1829 *right_p = binop_expression(right, invert_op(left->op), left->left);
1826 1830 *left_p = left->right;
1827 1831 return;
1828 1832 }
1829 1833
1830 1834 if (get_value(left->right, &sval)) {
1831 1835 *right_p = binop_expression(right, invert_op(left->op), left->right);
1832 1836 *left_p = left->left;
1833 1837 return;
1834 1838 }
1835 1839 return;
1836 1840 }
1837 1841 }
1838 1842
1839 1843 /*
1840 1844 * The reason for do_simple_algebra() is to solve things like:
1841 1845 * if (foo > 66 || foo + bar > 64) {
1842 1846 * "foo" is not really a known variable so it won't be handled by
1843 1847 * move_known_variables() but it's a super common idiom.
1844 1848 *
1845 1849 */
1846 1850 static int do_simple_algebra(struct expression **left_p, struct expression **right_p)
1847 1851 {
1848 1852 struct expression *left = *left_p;
1849 1853 struct expression *right = *right_p;
1850 1854 struct range_list *rl;
1851 1855 sval_t tmp;
1852 1856
1853 1857 if (left->type != EXPR_BINOP || left->op != '+')
1854 1858 return 0;
1855 1859 if (can_integer_overflow(get_type(left), left))
1856 1860 return 0;
1857 1861 if (!get_implied_value(right, &tmp))
1858 1862 return 0;
1859 1863
1860 1864 if (!get_implied_value(left->left, &tmp) &&
1861 1865 get_implied_rl(left->left, &rl) &&
1862 1866 !is_whole_rl(rl)) {
1863 1867 *right_p = binop_expression(right, '-', left->left);
1864 1868 *left_p = left->right;
1865 1869 return 1;
1866 1870 }
1867 1871 if (!get_implied_value(left->right, &tmp) &&
1868 1872 get_implied_rl(left->right, &rl) &&
1869 1873 !is_whole_rl(rl)) {
1870 1874 *right_p = binop_expression(right, '-', left->right);
1871 1875 *left_p = left->left;
1872 1876 return 1;
1873 1877 }
1874 1878
1875 1879 return 0;
1876 1880 }
1877 1881
1878 1882 static int match_func_comparison(struct expression *expr)
1879 1883 {
1880 1884 struct expression *left = strip_expr(expr->left);
1881 1885 struct expression *right = strip_expr(expr->right);
1882 1886
1883 1887 if (left->type == EXPR_CALL || right->type == EXPR_CALL) {
1884 1888 function_comparison(left, expr->op, right);
1885 1889 return 1;
1886 1890 }
1887 1891
1888 1892 return 0;
1889 1893 }
1890 1894
1891 1895 /* Handle conditions like "if (foo + bar < foo) {" */
1892 1896 static int handle_integer_overflow_test(struct expression *expr)
1893 1897 {
1894 1898 struct expression *left, *right;
1895 1899 struct symbol *type;
1896 1900 sval_t left_min, right_min, min, max;
1897 1901
1898 1902 if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
1899 1903 return 0;
1900 1904
1901 1905 left = strip_parens(expr->left);
1902 1906 right = strip_parens(expr->right);
1903 1907
1904 1908 if (left->op != '+')
1905 1909 return 0;
1906 1910
1907 1911 type = get_type(expr);
1908 1912 if (!type)
1909 1913 return 0;
1910 1914 if (type_positive_bits(type) == 32) {
1911 1915 max.type = &uint_ctype;
1912 1916 max.uvalue = (unsigned int)-1;
1913 1917 } else if (type_positive_bits(type) == 64) {
1914 1918 max.type = &ulong_ctype;
1915 1919 max.value = (unsigned long long)-1;
1916 1920 } else {
1917 1921 return 0;
1918 1922 }
1919 1923
1920 1924 if (!expr_equiv(left->left, right) && !expr_equiv(left->right, right))
1921 1925 return 0;
1922 1926
1923 1927 get_absolute_min(left->left, &left_min);
1924 1928 get_absolute_min(left->right, &right_min);
1925 1929 min = sval_binop(left_min, '+', right_min);
1926 1930
1927 1931 type = get_type(left);
1928 1932 min = sval_cast(type, min);
1929 1933 max = sval_cast(type, max);
1930 1934
1931 1935 set_extra_chunk_true_false(left, NULL, alloc_estate_range(min, max));
1932 1936 return 1;
1933 1937 }
1934 1938
1935 1939 static void match_comparison(struct expression *expr)
1936 1940 {
1937 1941 struct expression *left_orig = strip_parens(expr->left);
1938 1942 struct expression *right_orig = strip_parens(expr->right);
1939 1943 struct expression *left, *right, *tmp;
1940 1944 struct expression *prev;
1941 1945 struct symbol *type;
1942 1946 int redo, count;
1943 1947
1944 1948 if (match_func_comparison(expr))
1945 1949 return;
1946 1950
1947 1951 type = get_type(expr);
1948 1952 if (!type)
1949 1953 type = &llong_ctype;
1950 1954
1951 1955 if (handle_integer_overflow_test(expr))
1952 1956 return;
1953 1957
1954 1958 left = left_orig;
1955 1959 right = right_orig;
1956 1960 move_known_values(&left, &right);
1957 1961 handle_comparison(type, left, expr->op, right);
1958 1962
1959 1963 left = left_orig;
1960 1964 right = right_orig;
1961 1965 if (do_simple_algebra(&left, &right))
1962 1966 handle_comparison(type, left, expr->op, right);
1963 1967
1964 1968 prev = get_assigned_expr(left_orig);
1965 1969 if (is_simple_math(prev) && has_variable(prev, left_orig) == 0) {
1966 1970 left = prev;
1967 1971 right = right_orig;
1968 1972 move_known_values(&left, &right);
1969 1973 handle_comparison(type, left, expr->op, right);
1970 1974 }
1971 1975
1972 1976 prev = get_assigned_expr(right_orig);
1973 1977 if (is_simple_math(prev) && has_variable(prev, right_orig) == 0) {
1974 1978 left = left_orig;
1975 1979 right = prev;
1976 1980 move_known_values(&left, &right);
1977 1981 handle_comparison(type, left, expr->op, right);
1978 1982 }
1979 1983
1980 1984 redo = 0;
1981 1985 left = left_orig;
1982 1986 right = right_orig;
1983 1987 if (get_last_expr_from_expression_stmt(left_orig)) {
1984 1988 left = get_last_expr_from_expression_stmt(left_orig);
1985 1989 redo = 1;
1986 1990 }
1987 1991 if (get_last_expr_from_expression_stmt(right_orig)) {
1988 1992 right = get_last_expr_from_expression_stmt(right_orig);
1989 1993 redo = 1;
1990 1994 }
1991 1995
1992 1996 if (!redo)
1993 1997 return;
1994 1998
1995 1999 count = 0;
1996 2000 while ((tmp = get_assigned_expr(left))) {
1997 2001 if (count++ > 3)
1998 2002 break;
1999 2003 left = strip_expr(tmp);
2000 2004 }
2001 2005 count = 0;
2002 2006 while ((tmp = get_assigned_expr(right))) {
2003 2007 if (count++ > 3)
2004 2008 break;
2005 2009 right = strip_expr(tmp);
2006 2010 }
2007 2011
2008 2012 handle_comparison(type, left, expr->op, right);
2009 2013 }
2010 2014
2011 2015 static sval_t get_high_mask(sval_t known)
2012 2016 {
2013 2017 sval_t ret;
2014 2018 int i;
2015 2019
2016 2020 ret = known;
2017 2021 ret.value = 0;
2018 2022
2019 2023 for (i = type_bits(known.type) - 1; i >= 0; i--) {
2020 2024 if (known.uvalue & (1ULL << i))
2021 2025 ret.uvalue |= (1ULL << i);
2022 2026 else
2023 2027 return ret;
2024 2028
2025 2029 }
2026 2030 return ret;
2027 2031 }
2028 2032
2029 2033 static bool handle_bit_test(struct expression *expr)
2030 2034 {
2031 2035 struct range_list *orig_rl, *rl;
2032 2036 struct expression *shift, *mask, *var;
2033 2037 struct bit_info *bit_info;
2034 2038 sval_t sval;
2035 2039 sval_t high = { .type = &int_ctype };
2036 2040 sval_t low = { .type = &int_ctype };
2037 2041
2038 2042 shift = strip_expr(expr->right);
2039 2043 mask = strip_expr(expr->left);
2040 2044 if (shift->type != EXPR_BINOP || shift->op != SPECIAL_LEFTSHIFT) {
2041 2045 shift = strip_expr(expr->left);
2042 2046 mask = strip_expr(expr->right);
2043 2047 if (shift->type != EXPR_BINOP || shift->op != SPECIAL_LEFTSHIFT)
2044 2048 return false;
2045 2049 }
2046 2050 if (!get_implied_value(shift->left, &sval) || sval.value != 1)
2047 2051 return false;
2048 2052 var = strip_expr(shift->right);
2049 2053
2050 2054 bit_info = get_bit_info(mask);
2051 2055 if (!bit_info)
2052 2056 return false;
2053 2057 if (!bit_info->possible)
2054 2058 return false;
2055 2059
2056 2060 get_absolute_rl(var, &orig_rl);
2057 2061 if (sval_is_negative(rl_min(orig_rl)) ||
2058 2062 rl_max(orig_rl).uvalue > type_bits(get_type(shift->left)))
2059 2063 return false;
2060 2064
2061 2065 low.value = ffsll(bit_info->possible);
2062 2066 high.value = sm_fls64(bit_info->possible);
2063 2067 rl = alloc_rl(low, high);
2064 2068 rl = cast_rl(get_type(var), rl);
2065 2069 rl = rl_intersection(orig_rl, rl);
2066 2070 if (!rl)
2067 2071 return false;
2068 2072
2069 2073 set_extra_expr_true_false(shift->right, alloc_estate_rl(rl), NULL);
2070 2074
2071 2075 return true;
2072 2076 }
2073 2077
2074 2078 static void handle_AND_op(struct expression *var, sval_t known)
2075 2079 {
2076 2080 struct range_list *orig_rl;
2077 2081 struct range_list *true_rl = NULL;
2078 2082 struct range_list *false_rl = NULL;
2079 2083 int bit;
2080 2084 sval_t low_mask = known;
2081 2085 sval_t high_mask;
2082 2086 sval_t max;
2083 2087
2084 2088 get_absolute_rl(var, &orig_rl);
2085 2089
2086 2090 if (known.value > 0) {
2087 2091 bit = ffsll(known.value) - 1;
2088 2092 low_mask.uvalue = (1ULL << bit) - 1;
2089 2093 true_rl = remove_range(orig_rl, sval_type_val(known.type, 0), low_mask);
2090 2094 }
2091 2095 high_mask = get_high_mask(known);
2092 2096 if (high_mask.value) {
2093 2097 bit = ffsll(high_mask.value) - 1;
2094 2098 low_mask.uvalue = (1ULL << bit) - 1;
2095 2099
2096 2100 false_rl = orig_rl;
2097 2101 if (sval_is_negative(rl_min(orig_rl)))
2098 2102 false_rl = remove_range(false_rl, sval_type_min(known.type), sval_type_val(known.type, -1));
2099 2103 false_rl = remove_range(false_rl, low_mask, sval_type_max(known.type));
2100 2104 if (type_signed(high_mask.type) && type_unsigned(rl_type(false_rl))) {
2101 2105 false_rl = remove_range(false_rl,
2102 2106 sval_type_val(rl_type(false_rl), sval_type_max(known.type).uvalue),
2103 2107 sval_type_val(rl_type(false_rl), -1));
2104 2108 }
2105 2109 } else if (known.value == 1 &&
2106 2110 get_hard_max(var, &max) &&
2107 2111 sval_cmp(max, rl_max(orig_rl)) == 0 &&
2108 2112 max.value & 1) {
2109 2113 false_rl = remove_range(orig_rl, max, max);
2110 2114 }
2111 2115 set_extra_expr_true_false(var,
2112 2116 true_rl ? alloc_estate_rl(true_rl) : NULL,
2113 2117 false_rl ? alloc_estate_rl(false_rl) : NULL);
2114 2118 }
2115 2119
2116 2120 static void handle_AND_condition(struct expression *expr)
2117 2121 {
2118 2122 sval_t known;
2119 2123
2120 2124 if (handle_bit_test(expr))
2121 2125 return;
2122 2126
2123 2127 if (get_implied_value(expr->left, &known))
2124 2128 handle_AND_op(expr->right, known);
2125 2129 else if (get_implied_value(expr->right, &known))
2126 2130 handle_AND_op(expr->left, known);
2127 2131 }
2128 2132
2129 2133 static void handle_MOD_condition(struct expression *expr)
2130 2134 {
2131 2135 struct range_list *orig_rl;
2132 2136 struct range_list *true_rl;
2133 2137 struct range_list *false_rl = NULL;
2134 2138 sval_t right;
2135 2139 sval_t zero = { 0, };
2136 2140
2137 2141 if (!get_implied_value(expr->right, &right) || right.value == 0)
2138 2142 return;
2139 2143 get_absolute_rl(expr->left, &orig_rl);
2140 2144
2141 2145 zero.value = 0;
2142 2146 zero.type = rl_type(orig_rl);
2143 2147
2144 2148 /* We're basically dorking around the min and max here */
2145 2149 true_rl = remove_range(orig_rl, zero, zero);
2146 2150 if (!sval_is_max(rl_max(true_rl)) &&
2147 2151 !(rl_max(true_rl).value % right.value))
2148 2152 true_rl = remove_range(true_rl, rl_max(true_rl), rl_max(true_rl));
2149 2153
2150 2154 if (rl_equiv(true_rl, orig_rl))
2151 2155 true_rl = NULL;
2152 2156
2153 2157 if (sval_is_positive(rl_min(orig_rl)) &&
2154 2158 (rl_max(orig_rl).value - rl_min(orig_rl).value) / right.value < 5) {
2155 2159 sval_t add;
2156 2160 int i;
2157 2161
2158 2162 add = rl_min(orig_rl);
2159 2163 add.value += right.value - (add.value % right.value);
2160 2164 add.value -= right.value;
2161 2165
2162 2166 for (i = 0; i < 5; i++) {
2163 2167 add.value += right.value;
2164 2168 if (add.value > rl_max(orig_rl).value)
2165 2169 break;
2166 2170 add_range(&false_rl, add, add);
2167 2171 }
2168 2172 } else {
2169 2173 if (rl_min(orig_rl).uvalue != 0 &&
2170 2174 rl_min(orig_rl).uvalue < right.uvalue) {
2171 2175 sval_t chop = right;
2172 2176 chop.value--;
2173 2177 false_rl = remove_range(orig_rl, zero, chop);
2174 2178 }
2175 2179
2176 2180 if (!sval_is_max(rl_max(orig_rl)) &&
2177 2181 (rl_max(orig_rl).value % right.value)) {
2178 2182 sval_t chop = rl_max(orig_rl);
2179 2183 chop.value -= chop.value % right.value;
2180 2184 chop.value++;
2181 2185 if (!false_rl)
2182 2186 false_rl = clone_rl(orig_rl);
2183 2187 false_rl = remove_range(false_rl, chop, rl_max(orig_rl));
2184 2188 }
2185 2189 }
2186 2190
2187 2191 set_extra_expr_true_false(expr->left,
2188 2192 true_rl ? alloc_estate_rl(true_rl) : NULL,
2189 2193 false_rl ? alloc_estate_rl(false_rl) : NULL);
2190 2194 }
2191 2195
2192 2196 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
2193 2197 void __extra_match_condition(struct expression *expr)
2194 2198 {
2195 2199 expr = strip_expr(expr);
2196 2200 switch (expr->type) {
2197 2201 case EXPR_CALL:
2198 2202 function_comparison(expr, SPECIAL_NOTEQUAL, zero_expr());
2199 2203 return;
2200 2204 case EXPR_PREOP:
2201 2205 case EXPR_SYMBOL:
2202 2206 case EXPR_DEREF:
2203 2207 handle_comparison(get_type(expr), expr, SPECIAL_NOTEQUAL, zero_expr());
2204 2208 return;
2205 2209 case EXPR_COMPARE:
2206 2210 match_comparison(expr);
2207 2211 return;
2208 2212 case EXPR_ASSIGNMENT:
2209 2213 __extra_match_condition(expr->left);
2210 2214 return;
2211 2215 case EXPR_BINOP:
2212 2216 if (expr->op == '&')
2213 2217 handle_AND_condition(expr);
2214 2218 if (expr->op == '%')
2215 2219 handle_MOD_condition(expr);
2216 2220 return;
2217 2221 }
2218 2222 }
2219 2223
2220 2224 static void assume_indexes_are_valid(struct expression *expr)
2221 2225 {
2222 2226 struct expression *array_expr;
2223 2227 int array_size;
2224 2228 struct expression *offset;
2225 2229 struct symbol *offset_type;
2226 2230 struct range_list *rl_before;
2227 2231 struct range_list *rl_after;
2228 2232 struct range_list *filter = NULL;
2229 2233 sval_t size;
2230 2234
2231 2235 expr = strip_expr(expr);
2232 2236 if (!is_array(expr))
2233 2237 return;
2234 2238
2235 2239 offset = get_array_offset(expr);
2236 2240 offset_type = get_type(offset);
2237 2241 if (offset_type && type_signed(offset_type)) {
2238 2242 filter = alloc_rl(sval_type_min(offset_type),
2239 2243 sval_type_val(offset_type, -1));
2240 2244 }
2241 2245
2242 2246 array_expr = get_array_base(expr);
2243 2247 array_size = get_real_array_size(array_expr);
2244 2248 if (array_size > 1) {
2245 2249 size = sval_type_val(offset_type, array_size);
2246 2250 add_range(&filter, size, sval_type_max(offset_type));
2247 2251 }
2248 2252
2249 2253 if (!filter)
2250 2254 return;
2251 2255 get_absolute_rl(offset, &rl_before);
2252 2256 rl_after = rl_filter(rl_before, filter);
2253 2257 if (rl_equiv(rl_before, rl_after))
2254 2258 return;
2255 2259 set_extra_expr_nomod(offset, alloc_estate_rl(rl_after));
2256 2260 }
2257 2261
2258 2262 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
2259 2263 int implied_not_equal(struct expression *expr, long long val)
2260 2264 {
2261 2265 return !possibly_false(expr, SPECIAL_NOTEQUAL, value_expr(val));
2262 2266 }
2263 2267
2264 2268 int implied_not_equal_name_sym(char *name, struct symbol *sym, long long val)
2265 2269 {
2266 2270 struct smatch_state *estate;
2267 2271
2268 2272 estate = get_state(SMATCH_EXTRA, name, sym);
2269 2273 if (!estate)
2270 2274 return 0;
2271 2275 if (!rl_has_sval(estate_rl(estate), sval_type_val(estate_type(estate), 0)))
2272 2276 return 1;
2273 2277 return 0;
2274 2278 }
2275 2279
2276 2280 int parent_is_null_var_sym(const char *name, struct symbol *sym)
2277 2281 {
2278 2282 char buf[256];
2279 2283 char *start;
2280 2284 char *end;
2281 2285 struct smatch_state *state;
2282 2286
2283 2287 strncpy(buf, name, sizeof(buf) - 1);
2284 2288 buf[sizeof(buf) - 1] = '\0';
2285 2289
2286 2290 start = &buf[0];
2287 2291 while (*start == '*') {
2288 2292 start++;
2289 2293 state = __get_state(SMATCH_EXTRA, start, sym);
2290 2294 if (!state)
2291 2295 continue;
2292 2296 if (!estate_rl(state))
2293 2297 return 1;
2294 2298 if (estate_min(state).value == 0 &&
2295 2299 estate_max(state).value == 0)
2296 2300 return 1;
2297 2301 }
2298 2302
2299 2303 start = &buf[0];
2300 2304 while (*start == '&')
2301 2305 start++;
2302 2306
2303 2307 while ((end = strrchr(start, '-'))) {
2304 2308 *end = '\0';
2305 2309 state = __get_state(SMATCH_EXTRA, start, sym);
2306 2310 if (!state)
2307 2311 continue;
2308 2312 if (estate_min(state).value == 0 &&
2309 2313 estate_max(state).value == 0)
2310 2314 return 1;
2311 2315 }
2312 2316 return 0;
2313 2317 }
2314 2318
2315 2319 int parent_is_null(struct expression *expr)
2316 2320 {
2317 2321 struct symbol *sym;
2318 2322 char *var;
2319 2323 int ret = 0;
2320 2324
2321 2325 expr = strip_expr(expr);
2322 2326 var = expr_to_var_sym(expr, &sym);
2323 2327 if (!var || !sym)
2324 2328 goto free;
2325 2329 ret = parent_is_null_var_sym(var, sym);
2326 2330 free:
2327 2331 free_string(var);
2328 2332 return ret;
2329 2333 }
2330 2334
2331 2335 static int param_used_callback(void *found, int argc, char **argv, char **azColName)
2332 2336 {
2333 2337 *(int *)found = 1;
2334 2338 return 0;
2335 2339 }
2336 2340
2337 2341 static int is_kzalloc_info(struct sm_state *sm)
2338 2342 {
2339 2343 sval_t sval;
2340 2344
2341 2345 /*
2342 2346 * kzalloc() information is treated as special because so there is just
2343 2347 * a lot of stuff initialized to zero and it makes building the database
2344 2348 * take hours and hours.
2345 2349 *
2346 2350 * In theory, we should just remove this line and not pass any unused
2347 2351 * information, but I'm not sure enough that this code works so I want
2348 2352 * to hold off on that for now.
2349 2353 */
2350 2354 if (!estate_get_single_value(sm->state, &sval))
2351 2355 return 0;
2352 2356 if (sval.value != 0)
2353 2357 return 0;
2354 2358 return 1;
2355 2359 }
2356 2360
2357 2361 static int is_really_long(struct sm_state *sm)
2358 2362 {
2359 2363 const char *p;
2360 2364 int cnt = 0;
2361 2365
2362 2366 p = sm->name;
2363 2367 while ((p = strstr(p, "->"))) {
2364 2368 p += 2;
2365 2369 cnt++;
2366 2370 }
2367 2371
2368 2372 if (cnt < 3 ||
2369 2373 strlen(sm->name) < 40)
2370 2374 return 0;
2371 2375 return 1;
2372 2376 }
2373 2377
2374 2378 static int filter_unused_param_value_info(struct expression *call, int param, char *printed_name, struct sm_state *sm)
2375 2379 {
2376 2380 int found = 0;
2377 2381
2378 2382 /* for function pointers assume everything is used */
2379 2383 if (call->fn->type != EXPR_SYMBOL)
2380 2384 return 0;
2381 2385
2382 2386 /*
2383 2387 * This is to handle __builtin_mul_overflow(). In an ideal world we
2384 2388 * would only need this for invalid code.
2385 2389 *
2386 2390 */
2387 2391 if (!call->fn->symbol)
2388 2392 return 0;
2389 2393
2390 2394 if (!is_kzalloc_info(sm) && !is_really_long(sm))
2391 2395 return 0;
2392 2396
2393 2397 run_sql(¶m_used_callback, &found,
2394 2398 "select * from return_implies where %s and type = %d and parameter = %d and key = '%s';",
2395 2399 get_static_filter(call->fn->symbol), PARAM_USED, param, printed_name);
2396 2400 if (found)
2397 2401 return 0;
2398 2402
2399 2403 /* If the database is not built yet, then assume everything is used */
2400 2404 run_sql(¶m_used_callback, &found,
2401 2405 "select * from return_implies where %s and type = %d;",
2402 2406 get_static_filter(call->fn->symbol), PARAM_USED);
2403 2407 if (!found)
2404 2408 return 0;
2405 2409
2406 2410 return 1;
2407 2411 }
2408 2412
2409 2413 struct range_list *intersect_with_real_abs_var_sym(const char *name, struct symbol *sym, struct range_list *start)
2410 2414 {
2411 2415 struct smatch_state *state;
2412 2416
2413 2417 /*
2414 2418 * Here is the difference between implied value and real absolute, say
2415 2419 * you have:
2416 2420 *
2417 2421 * int a = (u8)x;
2418 2422 *
2419 2423 * Then you know that a is 0-255. That's real absolute. But you don't
2420 2424 * know for sure that it actually goes up to 255. So it's not implied.
2421 2425 * Implied indicates a degree of certainty.
2422 2426 *
2423 2427 * But then say you cap "a" at 8. That means you know it goes up to
2424 2428 * 8. So now the implied value is s32min-8. But you can combine it
2425 2429 * with the real absolute to say that actually it's 0-8.
2426 2430 *
2427 2431 * We are combining it here. But now that I think about it, this is
2428 2432 * probably not the ideal place to combine it because it should proably
2429 2433 * be done earlier. Oh well, this is an improvement on what was there
2430 2434 * before so I'm going to commit this code.
2431 2435 *
2432 2436 */
2433 2437
2434 2438 state = get_real_absolute_state_var_sym(name, sym);
2435 2439 if (!state || !estate_rl(state))
2436 2440 return start;
2437 2441
2438 2442 return rl_intersection(estate_rl(state), start);
2439 2443 }
2440 2444
2441 2445 struct range_list *intersect_with_real_abs_expr(struct expression *expr, struct range_list *start)
2442 2446 {
2443 2447 struct smatch_state *state;
2444 2448 struct range_list *abs_rl;
2445 2449
2446 2450 state = get_real_absolute_state(expr);
2447 2451 if (!state || !estate_rl(state))
2448 2452 return start;
2449 2453
2450 2454 abs_rl = cast_rl(rl_type(start), estate_rl(state));
2451 2455 return rl_intersection(abs_rl, start);
2452 2456 }
2453 2457
2454 2458 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
2455 2459 {
2456 2460 struct range_list *rl;
2457 2461 sval_t dummy;
2458 2462
2459 2463 if (estate_is_whole(sm->state) || !estate_rl(sm->state))
2460 2464 return;
2461 2465 if (filter_unused_param_value_info(call, param, printed_name, sm))
2462 2466 return;
2463 2467 rl = estate_rl(sm->state);
2464 2468 rl = intersect_with_real_abs_var_sym(sm->name, sm->sym, rl);
2465 2469 if (!rl)
2466 2470 return;
2467 2471 sql_insert_caller_info(call, PARAM_VALUE, param, printed_name, show_rl(rl));
2468 2472 if (!estate_get_single_value(sm->state, &dummy)) {
2469 2473 if (estate_has_hard_max(sm->state))
2470 2474 sql_insert_caller_info(call, HARD_MAX, param, printed_name,
2471 2475 sval_to_str(estate_max(sm->state)));
2472 2476 if (estate_has_fuzzy_max(sm->state))
2473 2477 sql_insert_caller_info(call, FUZZY_MAX, param, printed_name,
2474 2478 sval_to_str(estate_get_fuzzy_max(sm->state)));
2475 2479 }
2476 2480 }
2477 2481
2478 2482 static void returned_struct_members(int return_id, char *return_ranges, struct expression *expr)
2479 2483 {
2480 2484 struct symbol *returned_sym;
2481 2485 char *returned_name;
2482 2486 struct sm_state *sm;
2483 2487 char *compare_str;
2484 2488 char name_buf[256];
2485 2489 char val_buf[256];
2486 2490 int len;
2487 2491
2488 2492 // FIXME handle *$
2489 2493
2490 2494 if (!is_pointer(expr))
2491 2495 return;
2492 2496
2493 2497 returned_name = expr_to_var_sym(expr, &returned_sym);
2494 2498 if (!returned_name || !returned_sym)
2495 2499 goto free;
2496 2500 len = strlen(returned_name);
2497 2501
2498 2502 FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
2499 2503 if (!estate_rl(sm->state))
2500 2504 continue;
2501 2505 if (returned_sym != sm->sym)
2502 2506 continue;
2503 2507 if (strncmp(returned_name, sm->name, len) != 0)
2504 2508 continue;
2505 2509 if (sm->name[len] != '-')
2506 2510 continue;
2507 2511
2508 2512 snprintf(name_buf, sizeof(name_buf), "$%s", sm->name + len);
2509 2513
2510 2514 compare_str = name_sym_to_param_comparison(sm->name, sm->sym);
2511 2515 if (!compare_str && estate_is_whole(sm->state))
2512 2516 continue;
2513 2517 snprintf(val_buf, sizeof(val_buf), "%s%s", sm->state->name, compare_str ?: "");
2514 2518
2515 2519 sql_insert_return_states(return_id, return_ranges, PARAM_VALUE,
2516 2520 -1, name_buf, val_buf);
2517 2521 } END_FOR_EACH_SM(sm);
2518 2522
2519 2523 free:
2520 2524 free_string(returned_name);
2521 2525 }
2522 2526
2523 2527 static void db_limited_before(void)
2524 2528 {
2525 2529 unmatched_stree = clone_stree(__get_cur_stree());
2526 2530 }
2527 2531
2528 2532 static void db_limited_after(void)
2529 2533 {
2530 2534 free_stree(&unmatched_stree);
2531 2535 }
2532 2536
2533 2537 static int basically_the_same(struct range_list *orig, struct range_list *new)
2534 2538 {
2535 2539 if (rl_equiv(orig, new))
2536 2540 return 1;
2537 2541
2538 2542 /*
2539 2543 * The whole range is essentially the same as 0,4096-27777777777 so
2540 2544 * don't overwrite the implications just to store that.
2541 2545 *
2542 2546 */
2543 2547 if (rl_type(orig)->type == SYM_PTR &&
2544 2548 is_whole_rl(orig) &&
2545 2549 rl_min(new).value == 0 &&
2546 2550 rl_max(new).value == valid_ptr_max)
2547 2551 return 1;
2548 2552 return 0;
2549 2553 }
2550 2554
2551 2555 static void db_param_limit_binops(struct expression *arg, char *key, struct range_list *rl)
2552 2556 {
2553 2557 struct range_list *left_rl;
2554 2558 sval_t zero = { .type = rl_type(rl), };
2555 2559 sval_t sval;
2556 2560
2557 2561 if (arg->op != '*')
2558 2562 return;
2559 2563 if (!get_implied_value(arg->right, &sval))
2560 2564 return;
2561 2565 if (can_integer_overflow(get_type(arg), arg))
2562 2566 return;
2563 2567
2564 2568 left_rl = rl_binop(rl, '/', alloc_rl(sval, sval));
2565 2569 if (!rl_has_sval(rl, zero))
2566 2570 left_rl = remove_range(left_rl, zero, zero);
2567 2571
2568 2572 set_extra_expr_nomod(arg->left, alloc_estate_rl(left_rl));
2569 2573 }
2570 2574
2571 2575 static void db_param_limit_filter(struct expression *expr, int param, char *key, char *value, enum info_type op)
2572 2576 {
2573 2577 struct expression *arg;
2574 2578 char *name;
2575 2579 struct symbol *sym;
2576 2580 struct var_sym_list *vsl = NULL;
2577 2581 struct sm_state *sm;
2578 2582 struct symbol *compare_type, *var_type;
2579 2583 struct range_list *rl;
2580 2584 struct range_list *limit;
2581 2585 struct range_list *new;
2582 2586 char *other_name;
2583 2587 struct symbol *other_sym;
2584 2588
2585 2589 while (expr->type == EXPR_ASSIGNMENT)
2586 2590 expr = strip_expr(expr->right);
2587 2591 if (expr->type != EXPR_CALL)
2588 2592 return;
2589 2593
2590 2594 arg = get_argument_from_call_expr(expr->args, param);
2591 2595 if (!arg)
2592 2596 return;
2593 2597
2594 2598 if (strcmp(key, "$") == 0)
2595 2599 compare_type = get_arg_type(expr->fn, param);
2596 2600 else
2597 2601 compare_type = get_member_type_from_key(arg, key);
2598 2602
2599 2603 call_results_to_rl(expr, compare_type, value, &limit);
2600 2604 if (strcmp(key, "$") == 0)
2601 2605 move_known_to_rl(&arg, &limit);
2602 2606 name = get_chunk_from_key(arg, key, &sym, &vsl);
2603 2607 if (!name)
2604 2608 return;
2605 2609 if (op != PARAM_LIMIT && !sym)
2606 2610 goto free;
2607 2611
2608 2612 sm = get_sm_state(SMATCH_EXTRA, name, sym);
2609 2613 if (sm)
2610 2614 rl = estate_rl(sm->state);
2611 2615 else
2612 2616 rl = alloc_whole_rl(compare_type);
2613 2617
2614 2618 if (op == PARAM_LIMIT && !rl_fits_in_type(rl, compare_type))
2615 2619 goto free;
2616 2620
2617 2621 new = rl_intersection(rl, limit);
2618 2622
2619 2623 var_type = get_member_type_from_key(arg, key);
2620 2624 new = cast_rl(var_type, new);
2621 2625
2622 2626 /* We want to preserve the implications here */
2623 2627 if (sm && basically_the_same(rl, new))
2624 2628 goto free;
2625 2629 other_name = get_other_name_sym(name, sym, &other_sym);
2626 2630
2627 2631 if (op == PARAM_LIMIT)
2628 2632 set_extra_nomod_vsl(name, sym, vsl, NULL, alloc_estate_rl(new));
2629 2633 else
2630 2634 set_extra_mod(name, sym, NULL, alloc_estate_rl(new));
2631 2635
2632 2636 if (other_name && other_sym) {
2633 2637 if (op == PARAM_LIMIT)
2634 2638 set_extra_nomod_vsl(other_name, other_sym, vsl, NULL, alloc_estate_rl(new));
2635 2639 else
2636 2640 set_extra_mod(other_name, other_sym, NULL, alloc_estate_rl(new));
2637 2641 }
2638 2642
2639 2643 if (op == PARAM_LIMIT && arg->type == EXPR_BINOP)
2640 2644 db_param_limit_binops(arg, key, new);
2641 2645 free:
2642 2646 free_string(name);
2643 2647 }
2644 2648
2645 2649 static void db_param_limit(struct expression *expr, int param, char *key, char *value)
2646 2650 {
2647 2651 db_param_limit_filter(expr, param, key, value, PARAM_LIMIT);
2648 2652 }
2649 2653
2650 2654 static void db_param_filter(struct expression *expr, int param, char *key, char *value)
2651 2655 {
2652 2656 db_param_limit_filter(expr, param, key, value, PARAM_FILTER);
2653 2657 }
2654 2658
2655 2659 static void db_param_add_set(struct expression *expr, int param, char *key, char *value, enum info_type op)
2656 2660 {
2657 2661 struct expression *arg, *gen_expr;
2658 2662 char *name;
2659 2663 char *other_name = NULL;
2660 2664 struct symbol *sym, *other_sym;
2661 2665 struct symbol *param_type, *arg_type;
2662 2666 struct smatch_state *state;
2663 2667 struct range_list *new = NULL;
2664 2668 struct range_list *added = NULL;
2665 2669
2666 2670 while (expr->type == EXPR_ASSIGNMENT)
2667 2671 expr = strip_expr(expr->right);
2668 2672 if (expr->type != EXPR_CALL)
2669 2673 return;
2670 2674
2671 2675 arg = get_argument_from_call_expr(expr->args, param);
2672 2676 if (!arg)
2673 2677 return;
2674 2678
2675 2679 arg_type = get_arg_type_from_key(expr->fn, param, arg, key);
2676 2680 param_type = get_member_type_from_key(arg, key);
2677 2681 if (param_type && param_type->type == SYM_STRUCT)
2678 2682 return;
2679 2683 name = get_variable_from_key(arg, key, &sym);
2680 2684 if (!name || !sym)
2681 2685 goto free;
2682 2686 gen_expr = gen_expression_from_key(arg, key);
2683 2687
2684 2688 state = get_state(SMATCH_EXTRA, name, sym);
2685 2689 if (state)
2686 2690 new = estate_rl(state);
2687 2691
2688 2692 call_results_to_rl(expr, arg_type, value, &added);
2689 2693 added = cast_rl(param_type, added);
2690 2694 if (op == PARAM_SET)
2691 2695 new = added;
2692 2696 else
2693 2697 new = rl_union(new, added);
2694 2698
2695 2699 other_name = get_other_name_sym_nostack(name, sym, &other_sym);
2696 2700 set_extra_mod(name, sym, gen_expr, alloc_estate_rl(new));
2697 2701 if (other_name && other_sym)
2698 2702 set_extra_mod(other_name, other_sym, gen_expr, alloc_estate_rl(new));
2699 2703 free:
2700 2704 free_string(other_name);
2701 2705 free_string(name);
2702 2706 }
2703 2707
2704 2708 static void db_param_add(struct expression *expr, int param, char *key, char *value)
2705 2709 {
2706 2710 in_param_set = true;
2707 2711 db_param_add_set(expr, param, key, value, PARAM_ADD);
2708 2712 in_param_set = false;
2709 2713 }
2710 2714
2711 2715 static void db_param_set(struct expression *expr, int param, char *key, char *value)
2712 2716 {
2713 2717 in_param_set = true;
2714 2718 db_param_add_set(expr, param, key, value, PARAM_SET);
2715 2719 in_param_set = false;
2716 2720 }
2717 2721
2718 2722 static void match_lost_param(struct expression *call, int param)
2719 2723 {
2720 2724 struct expression *arg;
2721 2725
2722 2726 if (is_const_param(call->fn, param))
2723 2727 return;
2724 2728
2725 2729 arg = get_argument_from_call_expr(call->args, param);
2726 2730 if (!arg)
2727 2731 return;
2728 2732
2729 2733 arg = strip_expr(arg);
2730 2734 if (arg->type == EXPR_PREOP && arg->op == '&')
2731 2735 set_extra_expr_mod(arg->unop, alloc_estate_whole(get_type(arg->unop)));
2732 2736 else
2733 2737 ; /* if pointer then set struct members, maybe?*/
2734 2738 }
2735 2739
2736 2740 static void db_param_value(struct expression *expr, int param, char *key, char *value)
2737 2741 {
2738 2742 struct expression *call;
2739 2743 char *name;
2740 2744 struct symbol *sym;
2741 2745 struct symbol *type;
2742 2746 struct range_list *rl = NULL;
2743 2747
2744 2748 if (param != -1)
2745 2749 return;
2746 2750
2747 2751 call = expr;
2748 2752 while (call->type == EXPR_ASSIGNMENT)
2749 2753 call = strip_expr(call->right);
2750 2754 if (call->type != EXPR_CALL)
2751 2755 return;
2752 2756
2753 2757 type = get_member_type_from_key(expr->left, key);
2754 2758 name = get_variable_from_key(expr->left, key, &sym);
2755 2759 if (!name || !sym)
2756 2760 goto free;
2757 2761
2758 2762 call_results_to_rl(call, type, value, &rl);
2759 2763
2760 2764 set_extra_mod(name, sym, NULL, alloc_estate_rl(rl));
2761 2765 free:
2762 2766 free_string(name);
2763 2767 }
2764 2768
2765 2769 static void match_call_info(struct expression *expr)
2766 2770 {
2767 2771 struct smatch_state *state;
2768 2772 struct range_list *rl = NULL;
2769 2773 struct expression *arg;
2770 2774 struct symbol *type;
2771 2775 sval_t dummy;
2772 2776 int i = 0;
2773 2777
2774 2778 FOR_EACH_PTR(expr->args, arg) {
2775 2779 type = get_arg_type(expr->fn, i);
2776 2780
2777 2781 get_absolute_rl(arg, &rl);
2778 2782 rl = cast_rl(type, rl);
2779 2783
2780 2784 if (!is_whole_rl(rl)) {
2781 2785 rl = intersect_with_real_abs_expr(arg, rl);
2782 2786 sql_insert_caller_info(expr, PARAM_VALUE, i, "$", show_rl(rl));
2783 2787 }
2784 2788 state = get_state_expr(SMATCH_EXTRA, arg);
2785 2789 if (!estate_get_single_value(state, &dummy) && estate_has_hard_max(state)) {
2786 2790 sql_insert_caller_info(expr, HARD_MAX, i, "$",
2787 2791 sval_to_str(estate_max(state)));
2788 2792 }
2789 2793 if (estate_has_fuzzy_max(state)) {
2790 2794 sql_insert_caller_info(expr, FUZZY_MAX, i, "$",
2791 2795 sval_to_str(estate_get_fuzzy_max(state)));
2792 2796 }
|
↓ open down ↓ |
2602 lines elided |
↑ open up ↑ |
2793 2797 i++;
2794 2798 } END_FOR_EACH_PTR(arg);
2795 2799 }
2796 2800
2797 2801 static void set_param_value(const char *name, struct symbol *sym, char *key, char *value)
2798 2802 {
2799 2803 struct expression *expr;
2800 2804 struct range_list *rl = NULL;
2801 2805 struct smatch_state *state;
2802 2806 struct symbol *type;
2803 - char fullname[256];
2804 2807 char *key_orig = key;
2805 - bool add_star = false;
2808 + char *fullname;
2806 2809 sval_t dummy;
2807 2810
2808 - if (key[0] == '*') {
2809 - add_star = true;
2810 - key++;
2811 - }
2812 -
2813 - snprintf(fullname, 256, "%s%s%s", add_star ? "*" : "", name, key + 1);
2814 -
2815 2811 expr = symbol_expression(sym);
2812 + fullname = get_variable_from_key(expr, key, NULL);
2813 + if (!fullname)
2814 + return;
2815 +
2816 2816 type = get_member_type_from_key(expr, key_orig);
2817 2817 str_to_rl(type, value, &rl);
2818 2818 state = alloc_estate_rl(rl);
2819 2819 if (estate_get_single_value(state, &dummy))
2820 2820 estate_set_hard_max(state);
2821 2821 set_state(SMATCH_EXTRA, fullname, sym, state);
2822 2822 }
2823 2823
2824 2824 static void set_param_fuzzy_max(const char *name, struct symbol *sym, char *key, char *value)
2825 2825 {
2826 + struct expression *expr;
2826 2827 struct range_list *rl = NULL;
2827 2828 struct smatch_state *state;
2828 2829 struct symbol *type;
2829 - char fullname[256];
2830 + char *fullname;
2830 2831 sval_t max;
2831 2832
2832 - if (strcmp(key, "*$") == 0)
2833 - snprintf(fullname, sizeof(fullname), "*%s", name);
2834 - else if (strncmp(key, "$", 1) == 0)
2835 - snprintf(fullname, 256, "%s%s", name, key + 1);
2836 - else
2833 + expr = symbol_expression(sym);
2834 + fullname = get_variable_from_key(expr, key, NULL);
2835 + if (!fullname)
2837 2836 return;
2838 2837
2839 2838 state = get_state(SMATCH_EXTRA, fullname, sym);
2840 2839 if (!state)
2841 2840 return;
2842 2841 type = estate_type(state);
2843 2842 str_to_rl(type, value, &rl);
2844 2843 if (!rl_to_sval(rl, &max))
2845 2844 return;
2846 2845 estate_set_fuzzy_max(state, max);
2847 2846 }
2848 2847
2849 2848 static void set_param_hard_max(const char *name, struct symbol *sym, char *key, char *value)
2850 2849 {
2851 2850 struct smatch_state *state;
2852 - char fullname[256];
2851 + struct expression *expr;
2852 + char *fullname;
2853 2853
2854 - if (strcmp(key, "*$") == 0)
2855 - snprintf(fullname, sizeof(fullname), "*%s", name);
2856 - else if (strncmp(key, "$", 1) == 0)
2857 - snprintf(fullname, 256, "%s%s", name, key + 1);
2858 - else
2854 + expr = symbol_expression(sym);
2855 + fullname = get_variable_from_key(expr, key, NULL);
2856 + if (!fullname)
2859 2857 return;
2860 2858
2861 2859 state = get_state(SMATCH_EXTRA, fullname, sym);
2862 2860 if (!state)
2863 2861 return;
2864 2862 estate_set_hard_max(state);
2865 2863 }
2866 2864
2867 2865 struct sm_state *get_extra_sm_state(struct expression *expr)
2868 2866 {
2869 2867 char *name;
2870 2868 struct symbol *sym;
2871 2869 struct sm_state *ret = NULL;
2872 2870
2873 2871 name = expr_to_known_chunk_sym(expr, &sym);
2874 2872 if (!name)
2875 2873 goto free;
2876 2874
2877 2875 ret = get_sm_state(SMATCH_EXTRA, name, sym);
2878 2876 free:
2879 2877 free_string(name);
2880 2878 return ret;
2881 2879 }
2882 2880
2883 2881 struct smatch_state *get_extra_state(struct expression *expr)
2884 2882 {
2885 2883 struct sm_state *sm;
2886 2884
2887 2885 sm = get_extra_sm_state(expr);
2888 2886 if (!sm)
2889 2887 return NULL;
2890 2888 return sm->state;
2891 2889 }
2892 2890
2893 2891 void register_smatch_extra(int id)
2894 2892 {
2895 2893 my_id = id;
2896 2894
2897 2895 set_dynamic_states(my_id);
2898 2896 add_merge_hook(my_id, &merge_estates);
2899 2897 add_unmatched_state_hook(my_id, &unmatched_state);
2900 2898 select_caller_info_hook(set_param_value, PARAM_VALUE);
2901 2899 select_caller_info_hook(set_param_fuzzy_max, FUZZY_MAX);
2902 2900 select_caller_info_hook(set_param_hard_max, HARD_MAX);
2903 2901 select_return_states_before(&db_limited_before);
2904 2902 select_return_states_hook(PARAM_LIMIT, &db_param_limit);
2905 2903 select_return_states_hook(PARAM_FILTER, &db_param_filter);
2906 2904 select_return_states_hook(PARAM_ADD, &db_param_add);
2907 2905 select_return_states_hook(PARAM_SET, &db_param_set);
2908 2906 add_lost_param_hook(&match_lost_param);
2909 2907 select_return_states_hook(PARAM_VALUE, &db_param_value);
2910 2908 select_return_states_after(&db_limited_after);
2911 2909 }
2912 2910
2913 2911 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr)
2914 2912 {
2915 2913 struct var_sym_list *links;
2916 2914 struct var_sym *tmp;
2917 2915 struct smatch_state *state;
2918 2916
2919 2917 links = sm->state->data;
2920 2918
2921 2919 FOR_EACH_PTR(links, tmp) {
2922 2920 if (sm->sym == tmp->sym &&
2923 2921 strcmp(sm->name, tmp->var) == 0)
2924 2922 continue;
2925 2923 state = get_state(SMATCH_EXTRA, tmp->var, tmp->sym);
2926 2924 if (!state)
2927 2925 continue;
2928 2926 set_state(SMATCH_EXTRA, tmp->var, tmp->sym, alloc_estate_whole(estate_type(state)));
2929 2927 } END_FOR_EACH_PTR(tmp);
2930 2928 set_state(link_id, sm->name, sm->sym, &undefined);
2931 2929 }
2932 2930
2933 2931 void register_smatch_extra_links(int id)
2934 2932 {
2935 2933 link_id = id;
2936 2934 set_dynamic_states(link_id);
2937 2935 }
2938 2936
2939 2937 void register_smatch_extra_late(int id)
2940 2938 {
2941 2939 add_merge_hook(link_id, &merge_link_states);
2942 2940 add_modification_hook(link_id, &match_link_modify);
2943 2941 add_hook(&match_dereferences, DEREF_HOOK);
2944 2942 add_hook(&match_pointer_as_array, OP_HOOK);
2945 2943 select_return_implies_hook(DEREFERENCE, &set_param_dereferenced);
2946 2944 add_hook(&match_function_call, FUNCTION_CALL_HOOK);
2947 2945 add_hook(&match_assign, ASSIGNMENT_HOOK);
2948 2946 add_hook(&match_assign, GLOBAL_ASSIGNMENT_HOOK);
2949 2947 add_hook(&unop_expr, OP_HOOK);
2950 2948 add_hook(&asm_expr, ASM_HOOK);
2951 2949
2952 2950 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
2953 2951 add_member_info_callback(my_id, struct_member_callback);
2954 2952 add_split_return_callback(&returned_struct_members);
2955 2953
2956 2954 // add_hook(&assume_indexes_are_valid, OP_HOOK);
2957 2955 }
|
↓ open down ↓ |
89 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX