Print this page
11506 smatch resync
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/tools/smatch/src/smatch_slist.c
+++ new/usr/src/tools/smatch/src/smatch_slist.c
1 1 /*
2 2 * Copyright (C) 2008,2009 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 #include <stdlib.h>
19 19 #include <stdio.h>
20 20 #include "smatch.h"
21 21 #include "smatch_slist.h"
22 22
23 23 #undef CHECKORDER
24 24
25 25 ALLOCATOR(smatch_state, "smatch state");
26 26 ALLOCATOR(sm_state, "sm state");
27 27 ALLOCATOR(named_stree, "named slist");
28 28 __DO_ALLOCATOR(char, 1, 4, "state names", sname);
29 29
30 30 int sm_state_counter;
31 31
32 32 static struct stree_stack *all_pools;
33 33
34 34 const char *show_sm(struct sm_state *sm)
35 35 {
36 36 static char buf[256];
37 37 struct sm_state *tmp;
38 38 int pos;
39 39 int i;
40 40
41 41 if (!sm)
42 42 return "<none>";
43 43
44 44 pos = snprintf(buf, sizeof(buf), "[%s] '%s' = '%s'",
45 45 check_name(sm->owner), sm->name, show_state(sm->state));
46 46 if (pos > sizeof(buf))
47 47 goto truncate;
48 48
49 49 if (ptr_list_size((struct ptr_list *)sm->possible) == 1)
50 50 return buf;
51 51
52 52 pos += snprintf(buf + pos, sizeof(buf) - pos, " (");
53 53 if (pos > sizeof(buf))
54 54 goto truncate;
55 55 i = 0;
56 56 FOR_EACH_PTR(sm->possible, tmp) {
57 57 if (i++)
58 58 pos += snprintf(buf + pos, sizeof(buf) - pos, ", ");
59 59 if (pos > sizeof(buf))
60 60 goto truncate;
61 61 pos += snprintf(buf + pos, sizeof(buf) - pos, "%s",
62 62 show_state(tmp->state));
63 63 if (pos > sizeof(buf))
64 64 goto truncate;
65 65 } END_FOR_EACH_PTR(tmp);
66 66 snprintf(buf + pos, sizeof(buf) - pos, ")");
67 67
68 68 return buf;
69 69
70 70 truncate:
71 71 for (i = 0; i < 3; i++)
72 72 buf[sizeof(buf) - 2 - i] = '.';
73 73 return buf;
74 74 }
75 75
76 76 void __print_stree(struct stree *stree)
77 77 {
78 78 struct sm_state *sm;
79 79
80 80 printf("dumping stree at %d [%ld states]\n", get_lineno(), stree_count(stree));
81 81 FOR_EACH_SM(stree, sm) {
82 82 printf("%s\n", show_sm(sm));
83 83 } END_FOR_EACH_SM(sm);
84 84 printf("---\n");
85 85 }
86 86
87 87 /* NULL states go at the end to simplify merge_slist */
88 88 int cmp_tracker(const struct sm_state *a, const struct sm_state *b)
|
↓ open down ↓ |
88 lines elided |
↑ open up ↑ |
89 89 {
90 90 int ret;
91 91
92 92 if (a == b)
93 93 return 0;
94 94 if (!b)
95 95 return -1;
96 96 if (!a)
97 97 return 1;
98 98
99 - if (a->owner > b->owner)
100 - return -1;
101 99 if (a->owner < b->owner)
100 + return -1;
101 + if (a->owner > b->owner)
102 102 return 1;
103 103
104 104 ret = strcmp(a->name, b->name);
105 105 if (ret < 0)
106 106 return -1;
107 107 if (ret > 0)
108 108 return 1;
109 109
110 110 if (!b->sym && a->sym)
111 111 return -1;
112 112 if (!a->sym && b->sym)
113 113 return 1;
114 114 if (a->sym < b->sym)
115 115 return -1;
116 116 if (a->sym > b->sym)
117 117 return 1;
118 118
119 119 return 0;
120 120 }
121 121
122 -static int cmp_sm_states(const struct sm_state *a, const struct sm_state *b, int preserve)
122 +int *dynamic_states;
123 +void allocate_dynamic_states_array(int num_checks)
123 124 {
125 + dynamic_states = calloc(num_checks + 1, sizeof(int));
126 +}
127 +
128 +void set_dynamic_states(unsigned short owner)
129 +{
130 + dynamic_states[owner] = true;
131 +}
132 +
133 +bool has_dynamic_states(unsigned short owner)
134 +{
135 + if (owner >= num_checks)
136 + return false;
137 + return dynamic_states[owner];
138 +}
139 +
140 +static int cmp_possible_sm(const struct sm_state *a, const struct sm_state *b, int preserve)
141 +{
124 142 int ret;
125 143
126 - ret = cmp_tracker(a, b);
127 - if (ret)
128 - return ret;
144 + if (a == b)
145 + return 0;
129 146
130 - /* todo: add hook for smatch_extra.c */
131 - if (a->state > b->state)
132 - return -1;
133 - if (a->state < b->state)
134 - return 1;
135 - /* This is obviously a massive disgusting hack but we need to preserve
136 - * the unmerged states for smatch extra because we use them in
137 - * smatch_db.c. Meanwhile if we preserve all the other unmerged states
138 - * then it uses a lot of memory and we don't use it. Hence this hack.
139 - *
140 - * Also sometimes even just preserving every possible SMATCH_EXTRA state
141 - * takes too much resources so we have to cap that. Capping is probably
142 - * not often a problem in real life.
143 - */
144 - if (a->owner == SMATCH_EXTRA && preserve) {
145 - if (a == b)
146 - return 0;
147 - if (a->merged == 1 && b->merged == 0)
147 + if (!has_dynamic_states(a->owner)) {
148 + if (a->state > b->state)
148 149 return -1;
149 - if (a->merged == 0)
150 + if (a->state < b->state)
150 151 return 1;
152 + return 0;
151 153 }
152 154
153 - return 0;
155 + if (a->owner == SMATCH_EXTRA) {
156 + /*
157 + * In Smatch extra you can have borrowed implications.
158 + *
159 + * FIXME: review how borrowed implications work and if they
160 + * are the best way. See also smatch_implied.c.
161 + *
162 + */
163 + ret = cmp_tracker(a, b);
164 + if (ret)
165 + return ret;
166 +
167 + /*
168 + * We want to preserve leaf states. They're use to split
169 + * returns in smatch_db.c.
170 + *
171 + */
172 + if (preserve) {
173 + if (a->merged && !b->merged)
174 + return -1;
175 + if (!a->merged)
176 + return 1;
177 + }
178 + }
179 + if (!a->state->name || !b->state->name)
180 + return 0;
181 +
182 + return strcmp(a->state->name, b->state->name);
154 183 }
155 184
156 185 struct sm_state *alloc_sm_state(int owner, const char *name,
157 186 struct symbol *sym, struct smatch_state *state)
158 187 {
159 188 struct sm_state *sm_state = __alloc_sm_state(0);
160 189
161 190 sm_state_counter++;
162 191
163 192 sm_state->name = alloc_sname(name);
164 193 sm_state->owner = owner;
165 194 sm_state->sym = sym;
166 195 sm_state->state = state;
167 196 sm_state->line = get_lineno();
168 197 sm_state->merged = 0;
169 198 sm_state->pool = NULL;
170 199 sm_state->left = NULL;
171 200 sm_state->right = NULL;
172 - sm_state->nr_children = 1;
173 201 sm_state->possible = NULL;
174 202 add_ptr_list(&sm_state->possible, sm_state);
175 203 return sm_state;
176 204 }
177 205
178 206 static struct sm_state *alloc_state_no_name(int owner, const char *name,
179 207 struct symbol *sym,
180 208 struct smatch_state *state)
181 209 {
182 210 struct sm_state *tmp;
183 211
184 212 tmp = alloc_sm_state(owner, NULL, sym, state);
185 213 tmp->name = name;
186 214 return tmp;
187 215 }
188 216
189 217 int too_many_possible(struct sm_state *sm)
|
↓ open down ↓ |
7 lines elided |
↑ open up ↑ |
190 218 {
191 219 if (ptr_list_size((struct ptr_list *)sm->possible) >= 100)
192 220 return 1;
193 221 return 0;
194 222 }
195 223
196 224 void add_possible_sm(struct sm_state *to, struct sm_state *new)
197 225 {
198 226 struct sm_state *tmp;
199 227 int preserve = 1;
228 + int cmp;
200 229
201 230 if (too_many_possible(to))
202 231 preserve = 0;
203 232
204 233 FOR_EACH_PTR(to->possible, tmp) {
205 - if (cmp_sm_states(tmp, new, preserve) < 0)
234 + cmp = cmp_possible_sm(tmp, new, preserve);
235 + if (cmp < 0)
206 236 continue;
207 - else if (cmp_sm_states(tmp, new, preserve) == 0) {
237 + else if (cmp == 0) {
208 238 return;
209 239 } else {
210 240 INSERT_CURRENT(new, tmp);
211 241 return;
212 242 }
213 243 } END_FOR_EACH_PTR(tmp);
214 244 add_ptr_list(&to->possible, new);
215 245 }
216 246
217 -static void copy_possibles(struct sm_state *to, struct sm_state *from)
247 +static void copy_possibles(struct sm_state *to, struct sm_state *one, struct sm_state *two)
218 248 {
249 + struct sm_state *large = one;
250 + struct sm_state *small = two;
219 251 struct sm_state *tmp;
220 252
221 - FOR_EACH_PTR(from->possible, tmp) {
253 + /*
254 + * We spend a lot of time copying the possible lists. I've tried to
255 + * optimize the process a bit.
256 + *
257 + */
258 +
259 + if (ptr_list_size((struct ptr_list *)two->possible) >
260 + ptr_list_size((struct ptr_list *)one->possible)) {
261 + large = two;
262 + small = one;
263 + }
264 +
265 + to->possible = clone_slist(large->possible);
266 + add_possible_sm(to, to);
267 + FOR_EACH_PTR(small->possible, tmp) {
222 268 add_possible_sm(to, tmp);
223 269 } END_FOR_EACH_PTR(tmp);
224 270 }
225 271
226 272 char *alloc_sname(const char *str)
227 273 {
228 274 char *tmp;
229 275
230 276 if (!str)
231 277 return NULL;
232 278 tmp = __alloc_sname(strlen(str) + 1);
233 279 strcpy(tmp, str);
234 280 return tmp;
235 281 }
236 282
283 +static struct symbol *oom_func;
284 +static int oom_limit = 3000000; /* Start with a 3GB limit */
237 285 int out_of_memory(void)
238 286 {
287 + if (oom_func)
288 + return 1;
289 +
239 290 /*
240 291 * I decided to use 50M here based on trial and error.
241 292 * It works out OK for the kernel and so it should work
242 293 * for most other projects as well.
243 294 */
244 295 if (sm_state_counter * sizeof(struct sm_state) >= 100000000)
245 296 return 1;
297 +
298 + /*
299 + * We're reading from statm to figure out how much memory we
300 + * are using. The problem is that at the end of the function
301 + * we release the memory, so that it can be re-used but it
302 + * stays in cache, it's not released to the OS. So then if
303 + * we allocate memory for different purposes we can easily
304 + * hit the 3GB limit on the next function, so that's why I give
305 + * the next function an extra 100MB to work with.
306 + *
307 + */
308 + if (get_mem_kb() > oom_limit) {
309 + oom_func = cur_func_sym;
310 + final_pass++;
311 + sm_perror("OOM: %luKb sm_state_count = %d", get_mem_kb(), sm_state_counter);
312 + final_pass--;
313 + return 1;
314 + }
315 +
246 316 return 0;
247 317 }
248 318
249 319 int low_on_memory(void)
250 320 {
251 321 if (sm_state_counter * sizeof(struct sm_state) >= 25000000)
252 322 return 1;
253 323 return 0;
254 324 }
255 325
256 326 static void free_sm_state(struct sm_state *sm)
257 327 {
258 328 free_slist(&sm->possible);
259 329 /*
260 330 * fixme. Free the actual state.
261 331 * Right now we leave it until the end of the function
262 332 * because we don't want to double free it.
263 333 * Use the freelist to not double free things
264 334 */
265 335 }
266 336
267 337 static void free_all_sm_states(struct allocation_blob *blob)
268 338 {
269 339 unsigned int size = sizeof(struct sm_state);
270 340 unsigned int offset = 0;
271 341
272 342 while (offset < blob->offset) {
273 343 free_sm_state((struct sm_state *)(blob->data + offset));
274 344 offset += size;
275 345 }
276 346 }
277 347
278 348 /* At the end of every function we free all the sm_states */
279 349 void free_every_single_sm_state(void)
280 350 {
281 351 struct allocator_struct *desc = &sm_state_allocator;
282 352 struct allocation_blob *blob = desc->blobs;
283 353
284 354 desc->blobs = NULL;
285 355 desc->allocations = 0;
286 356 desc->total_bytes = 0;
287 357 desc->useful_bytes = 0;
288 358 desc->freelist = NULL;
289 359 while (blob) {
|
↓ open down ↓ |
34 lines elided |
↑ open up ↑ |
290 360 struct allocation_blob *next = blob->next;
291 361 free_all_sm_states(blob);
292 362 blob_free(blob, desc->chunking);
293 363 blob = next;
294 364 }
295 365 clear_sname_alloc();
296 366 clear_smatch_state_alloc();
297 367
298 368 free_stack_and_strees(&all_pools);
299 369 sm_state_counter = 0;
370 + if (oom_func) {
371 + oom_limit += 100000;
372 + oom_func = NULL;
373 + }
300 374 }
301 375
302 376 unsigned long get_pool_count(void)
303 377 {
304 378 return ptr_list_size((struct ptr_list *)all_pools);
305 379 }
306 380
307 381 struct sm_state *clone_sm(struct sm_state *s)
308 382 {
309 383 struct sm_state *ret;
310 384
311 385 ret = alloc_state_no_name(s->owner, s->name, s->sym, s->state);
312 386 ret->merged = s->merged;
313 387 ret->line = s->line;
314 388 /* clone_sm() doesn't copy the pools. Each state needs to have
315 389 only one pool. */
316 390 ret->possible = clone_slist(s->possible);
317 391 ret->left = s->left;
318 392 ret->right = s->right;
319 - ret->nr_children = s->nr_children;
320 393 return ret;
321 394 }
322 395
323 396 int is_merged(struct sm_state *sm)
324 397 {
325 398 return sm->merged;
326 399 }
327 400
328 401 int is_leaf(struct sm_state *sm)
329 402 {
330 403 return !sm->merged;
331 404 }
332 405
333 406 int slist_has_state(struct state_list *slist, struct smatch_state *state)
334 407 {
335 408 struct sm_state *tmp;
336 409
337 410 FOR_EACH_PTR(slist, tmp) {
338 411 if (tmp->state == state)
339 412 return 1;
340 413 } END_FOR_EACH_PTR(tmp);
341 414 return 0;
342 415 }
343 416
344 417 struct state_list *clone_slist(struct state_list *from_slist)
345 418 {
346 419 struct sm_state *sm;
347 420 struct state_list *to_slist = NULL;
348 421
349 422 FOR_EACH_PTR(from_slist, sm) {
350 423 add_ptr_list(&to_slist, sm);
351 424 } END_FOR_EACH_PTR(sm);
352 425 return to_slist;
353 426 }
354 427
355 428 static struct smatch_state *merge_states(int owner, const char *name,
356 429 struct symbol *sym,
357 430 struct smatch_state *state1,
358 431 struct smatch_state *state2)
359 432 {
360 433 struct smatch_state *ret;
361 434
362 435 if (state1 == state2)
363 436 ret = state1;
364 437 else if (__has_merge_function(owner))
365 438 ret = __client_merge_function(owner, state1, state2);
366 439 else if (state1 == &ghost)
367 440 ret = state2;
368 441 else if (state2 == &ghost)
369 442 ret = state1;
370 443 else if (!state1 || !state2)
371 444 ret = &undefined;
372 445 else
373 446 ret = &merged;
374 447 return ret;
375 448 }
376 449
377 450 struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two)
378 451 {
379 452 struct smatch_state *s;
380 453 struct sm_state *result;
381 454 static int warned;
382 455
383 456 if (one == two)
384 457 return one;
385 458 if (out_of_memory()) {
386 459 if (!warned)
|
↓ open down ↓ |
57 lines elided |
↑ open up ↑ |
387 460 sm_warning("Function too hairy. No more merges.");
388 461 warned = 1;
389 462 return one;
390 463 }
391 464 warned = 0;
392 465 s = merge_states(one->owner, one->name, one->sym, one->state, two->state);
393 466 result = alloc_state_no_name(one->owner, one->name, one->sym, s);
394 467 result->merged = 1;
395 468 result->left = one;
396 469 result->right = two;
397 - result->nr_children = one->nr_children + two->nr_children;
398 - copy_possibles(result, one);
399 - copy_possibles(result, two);
400 470
471 + copy_possibles(result, one, two);
472 +
401 473 /*
402 474 * The ->line information is used by deref_check where we complain about
403 475 * checking pointers that have already been dereferenced. Let's say we
404 476 * dereference a pointer on both the true and false paths and then merge
405 477 * the states here. The result state is &derefed, but the ->line number
406 478 * is on the line where the pointer is merged not where it was
407 479 * dereferenced..
408 480 *
409 481 * So in that case, let's just pick one dereference and set the ->line
410 482 * to point at it.
411 483 *
412 484 */
413 485
414 486 if (result->state == one->state)
415 487 result->line = one->line;
416 488 if (result->state == two->state)
417 489 result->line = two->line;
418 490
419 491 if (option_debug ||
420 492 strcmp(check_name(one->owner), option_debug_check) == 0) {
421 493 struct sm_state *tmp;
422 494 int i = 0;
423 495
424 496 printf("%s:%d %s() merge [%s] '%s' %s(L %d) + %s(L %d) => %s (",
425 497 get_filename(), get_lineno(), get_function(),
426 498 check_name(one->owner), one->name,
427 499 show_state(one->state), one->line,
428 500 show_state(two->state), two->line,
429 501 show_state(s));
430 502
431 503 FOR_EACH_PTR(result->possible, tmp) {
432 504 if (i++)
433 505 printf(", ");
434 506 printf("%s", show_state(tmp->state));
435 507 } END_FOR_EACH_PTR(tmp);
436 508 printf(")\n");
437 509 }
438 510
439 511 return result;
440 512 }
441 513
442 514 struct sm_state *get_sm_state_stree(struct stree *stree, int owner, const char *name,
443 515 struct symbol *sym)
444 516 {
445 517 struct tracker tracker = {
446 518 .owner = owner,
447 519 .name = (char *)name,
448 520 .sym = sym,
449 521 };
450 522
451 523 if (!name)
452 524 return NULL;
453 525
454 526
455 527 return avl_lookup(stree, (struct sm_state *)&tracker);
456 528 }
457 529
458 530 struct smatch_state *get_state_stree(struct stree *stree,
459 531 int owner, const char *name,
460 532 struct symbol *sym)
461 533 {
462 534 struct sm_state *sm;
463 535
464 536 sm = get_sm_state_stree(stree, owner, name, sym);
465 537 if (sm)
466 538 return sm->state;
467 539 return NULL;
468 540 }
469 541
470 542 /* FIXME: this is almost exactly the same as set_sm_state_slist() */
471 543 void overwrite_sm_state_stree(struct stree **stree, struct sm_state *new)
472 544 {
473 545 avl_insert(stree, new);
474 546 }
475 547
476 548 void overwrite_sm_state_stree_stack(struct stree_stack **stack,
477 549 struct sm_state *sm)
478 550 {
479 551 struct stree *stree;
480 552
481 553 stree = pop_stree(stack);
482 554 overwrite_sm_state_stree(&stree, sm);
483 555 push_stree(stack, stree);
484 556 }
485 557
486 558 struct sm_state *set_state_stree(struct stree **stree, int owner, const char *name,
487 559 struct symbol *sym, struct smatch_state *state)
488 560 {
489 561 struct sm_state *new = alloc_sm_state(owner, name, sym, state);
490 562
491 563 avl_insert(stree, new);
492 564 return new;
493 565 }
494 566
495 567 void set_state_stree_perm(struct stree **stree, int owner, const char *name,
496 568 struct symbol *sym, struct smatch_state *state)
497 569 {
498 570 struct sm_state *sm;
499 571
500 572 sm = malloc(sizeof(*sm) + strlen(name) + 1);
501 573 memset(sm, 0, sizeof(*sm));
502 574 sm->owner = owner;
503 575 sm->name = (char *)(sm + 1);
504 576 strcpy((char *)sm->name, name);
505 577 sm->sym = sym;
506 578 sm->state = state;
507 579
508 580 overwrite_sm_state_stree(stree, sm);
509 581 }
510 582
511 583 void delete_state_stree(struct stree **stree, int owner, const char *name,
512 584 struct symbol *sym)
513 585 {
514 586 struct tracker tracker = {
515 587 .owner = owner,
516 588 .name = (char *)name,
517 589 .sym = sym,
518 590 };
519 591
520 592 avl_remove(stree, (struct sm_state *)&tracker);
521 593 }
522 594
523 595 void delete_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
524 596 struct symbol *sym)
525 597 {
526 598 struct stree *stree;
527 599
528 600 stree = pop_stree(stack);
529 601 delete_state_stree(&stree, owner, name, sym);
530 602 push_stree(stack, stree);
531 603 }
532 604
533 605 void push_stree(struct stree_stack **stack, struct stree *stree)
534 606 {
535 607 add_ptr_list(stack, stree);
536 608 }
537 609
538 610 struct stree *pop_stree(struct stree_stack **stack)
539 611 {
540 612 struct stree *stree;
541 613
542 614 stree = last_ptr_list((struct ptr_list *)*stack);
543 615 delete_ptr_list_last((struct ptr_list **)stack);
544 616 return stree;
545 617 }
546 618
547 619 struct stree *top_stree(struct stree_stack *stack)
548 620 {
549 621 return last_ptr_list((struct ptr_list *)stack);
550 622 }
551 623
552 624 void free_slist(struct state_list **slist)
553 625 {
554 626 __free_ptr_list((struct ptr_list **)slist);
555 627 }
556 628
557 629 void free_stree_stack(struct stree_stack **stack)
558 630 {
559 631 __free_ptr_list((struct ptr_list **)stack);
560 632 }
561 633
562 634 void free_stack_and_strees(struct stree_stack **stree_stack)
563 635 {
564 636 struct stree *stree;
565 637
566 638 FOR_EACH_PTR(*stree_stack, stree) {
567 639 free_stree(&stree);
568 640 } END_FOR_EACH_PTR(stree);
569 641 free_stree_stack(stree_stack);
570 642 }
571 643
572 644 struct sm_state *set_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
573 645 struct symbol *sym, struct smatch_state *state)
574 646 {
575 647 struct stree *stree;
576 648 struct sm_state *sm;
577 649
578 650 stree = pop_stree(stack);
579 651 sm = set_state_stree(&stree, owner, name, sym, state);
580 652 push_stree(stack, stree);
581 653
582 654 return sm;
583 655 }
584 656
585 657 /*
586 658 * get_sm_state_stack() gets the state for the top slist on the stack.
587 659 */
588 660 struct sm_state *get_sm_state_stree_stack(struct stree_stack *stack,
589 661 int owner, const char *name,
590 662 struct symbol *sym)
591 663 {
592 664 struct stree *stree;
593 665 struct sm_state *ret;
594 666
595 667 stree = pop_stree(&stack);
596 668 ret = get_sm_state_stree(stree, owner, name, sym);
597 669 push_stree(&stack, stree);
598 670 return ret;
599 671 }
600 672
601 673 struct smatch_state *get_state_stree_stack(struct stree_stack *stack,
602 674 int owner, const char *name,
603 675 struct symbol *sym)
604 676 {
605 677 struct sm_state *sm;
606 678
607 679 sm = get_sm_state_stree_stack(stack, owner, name, sym);
608 680 if (sm)
609 681 return sm->state;
610 682 return NULL;
611 683 }
612 684
613 685 static void match_states_stree(struct stree **one, struct stree **two)
614 686 {
615 687 struct smatch_state *tmp_state;
616 688 struct sm_state *sm;
617 689 struct state_list *add_to_one = NULL;
618 690 struct state_list *add_to_two = NULL;
619 691 AvlIter one_iter;
620 692 AvlIter two_iter;
621 693
622 694 avl_iter_begin(&one_iter, *one, FORWARD);
623 695 avl_iter_begin(&two_iter, *two, FORWARD);
624 696
625 697 for (;;) {
626 698 if (!one_iter.sm && !two_iter.sm)
627 699 break;
628 700 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
629 701 __set_fake_cur_stree_fast(*two);
630 702 tmp_state = __client_unmatched_state_function(one_iter.sm);
631 703 __pop_fake_cur_stree_fast();
632 704 sm = alloc_state_no_name(one_iter.sm->owner, one_iter.sm->name,
633 705 one_iter.sm->sym, tmp_state);
634 706 add_ptr_list(&add_to_two, sm);
635 707 avl_iter_next(&one_iter);
636 708 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
637 709 avl_iter_next(&one_iter);
638 710 avl_iter_next(&two_iter);
639 711 } else {
640 712 __set_fake_cur_stree_fast(*one);
641 713 tmp_state = __client_unmatched_state_function(two_iter.sm);
642 714 __pop_fake_cur_stree_fast();
643 715 sm = alloc_state_no_name(two_iter.sm->owner, two_iter.sm->name,
644 716 two_iter.sm->sym, tmp_state);
645 717 add_ptr_list(&add_to_one, sm);
646 718 avl_iter_next(&two_iter);
647 719 }
648 720 }
649 721
650 722 FOR_EACH_PTR(add_to_one, sm) {
651 723 avl_insert(one, sm);
652 724 } END_FOR_EACH_PTR(sm);
653 725
654 726 FOR_EACH_PTR(add_to_two, sm) {
655 727 avl_insert(two, sm);
656 728 } END_FOR_EACH_PTR(sm);
657 729
658 730 free_slist(&add_to_one);
659 731 free_slist(&add_to_two);
660 732 }
661 733
662 734 static void call_pre_merge_hooks(struct stree **one, struct stree **two)
663 735 {
664 736 struct sm_state *sm, *other;
665 737
666 738 save_all_states();
667 739
668 740 __swap_cur_stree(*one);
669 741 FOR_EACH_SM(*two, sm) {
670 742 other = get_sm_state(sm->owner, sm->name, sm->sym);
671 743 if (other == sm)
672 744 continue;
673 745 call_pre_merge_hook(sm);
674 746 } END_FOR_EACH_SM(sm);
675 747 *one = clone_stree(__get_cur_stree());
676 748
677 749 __swap_cur_stree(*two);
678 750 FOR_EACH_SM(*one, sm) {
679 751 other = get_sm_state(sm->owner, sm->name, sm->sym);
680 752 if (other == sm)
681 753 continue;
682 754 call_pre_merge_hook(sm);
683 755 } END_FOR_EACH_SM(sm);
684 756 *two = clone_stree(__get_cur_stree());
685 757
686 758 restore_all_states();
687 759 }
688 760
689 761 static void clone_pool_havers_stree(struct stree **stree)
690 762 {
691 763 struct sm_state *sm, *tmp;
692 764 struct state_list *slist = NULL;
693 765
694 766 FOR_EACH_SM(*stree, sm) {
695 767 if (sm->pool) {
696 768 tmp = clone_sm(sm);
697 769 add_ptr_list(&slist, tmp);
698 770 }
699 771 } END_FOR_EACH_SM(sm);
700 772
701 773 FOR_EACH_PTR(slist, sm) {
702 774 avl_insert(stree, sm);
703 775 } END_FOR_EACH_PTR(sm);
704 776
705 777 free_slist(&slist);
706 778 }
707 779
708 780 int __stree_id;
709 781
710 782 /*
|
↓ open down ↓ |
300 lines elided |
↑ open up ↑ |
711 783 * merge_slist() is called whenever paths merge, such as after
712 784 * an if statement. It takes the two slists and creates one.
713 785 */
714 786 static void __merge_stree(struct stree **to, struct stree *stree, int add_pool)
715 787 {
716 788 struct stree *results = NULL;
717 789 struct stree *implied_one = NULL;
718 790 struct stree *implied_two = NULL;
719 791 AvlIter one_iter;
720 792 AvlIter two_iter;
721 - struct sm_state *tmp_sm;
793 + struct sm_state *one, *two, *res;
722 794
723 795 if (out_of_memory())
724 796 return;
725 797
726 798 /* merging a null and nonnull path gives you only the nonnull path */
727 799 if (!stree)
728 800 return;
729 801 if (*to == stree)
730 802 return;
731 803
732 804 if (!*to) {
733 805 *to = clone_stree(stree);
734 806 return;
735 807 }
736 808
737 809 implied_one = clone_stree(*to);
738 810 implied_two = clone_stree(stree);
739 811
740 812 match_states_stree(&implied_one, &implied_two);
741 813 call_pre_merge_hooks(&implied_one, &implied_two);
742 814
743 815 if (add_pool) {
744 816 clone_pool_havers_stree(&implied_one);
745 817 clone_pool_havers_stree(&implied_two);
746 818
747 819 set_stree_id(&implied_one, ++__stree_id);
748 820 set_stree_id(&implied_two, ++__stree_id);
749 821 if (implied_one->base_stree)
750 822 set_stree_id(&implied_one->base_stree, ++__stree_id);
751 823 if (implied_two->base_stree)
752 824 set_stree_id(&implied_two->base_stree, ++__stree_id);
753 825 }
|
↓ open down ↓ |
22 lines elided |
↑ open up ↑ |
754 826
755 827 push_stree(&all_pools, implied_one);
756 828 push_stree(&all_pools, implied_two);
757 829
758 830 avl_iter_begin(&one_iter, implied_one, FORWARD);
759 831 avl_iter_begin(&two_iter, implied_two, FORWARD);
760 832
761 833 for (;;) {
762 834 if (!one_iter.sm || !two_iter.sm)
763 835 break;
764 - if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
765 - sm_perror(" in %s", __func__);
766 - avl_iter_next(&one_iter);
767 - } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
768 - if (add_pool && one_iter.sm != two_iter.sm) {
769 - one_iter.sm->pool = implied_one;
770 - if (implied_one->base_stree)
771 - one_iter.sm->pool = implied_one->base_stree;
772 - two_iter.sm->pool = implied_two;
773 - if (implied_two->base_stree)
774 - two_iter.sm->pool = implied_two->base_stree;
775 - }
776 - tmp_sm = merge_sm_states(one_iter.sm, two_iter.sm);
777 - add_possible_sm(tmp_sm, one_iter.sm);
778 - add_possible_sm(tmp_sm, two_iter.sm);
779 - avl_insert(&results, tmp_sm);
780 - avl_iter_next(&one_iter);
781 - avl_iter_next(&two_iter);
782 - } else {
783 - sm_perror(" in %s", __func__);
784 - avl_iter_next(&two_iter);
836 +
837 + one = one_iter.sm;
838 + two = two_iter.sm;
839 +
840 + if (one == two) {
841 + avl_insert(&results, one);
842 + goto next;
785 843 }
844 +
845 + if (add_pool) {
846 + one->pool = implied_one;
847 + if (implied_one->base_stree)
848 + one->pool = implied_one->base_stree;
849 + two->pool = implied_two;
850 + if (implied_two->base_stree)
851 + two->pool = implied_two->base_stree;
852 + }
853 + res = merge_sm_states(one, two);
854 + add_possible_sm(res, one);
855 + add_possible_sm(res, two);
856 + avl_insert(&results, res);
857 +next:
858 + avl_iter_next(&one_iter);
859 + avl_iter_next(&two_iter);
786 860 }
787 861
788 862 free_stree(to);
789 863 *to = results;
790 864 }
791 865
792 866 void merge_stree(struct stree **to, struct stree *stree)
793 867 {
794 868 __merge_stree(to, stree, 1);
795 869 }
796 870
797 871 void merge_stree_no_pools(struct stree **to, struct stree *stree)
798 872 {
799 873 __merge_stree(to, stree, 0);
800 874 }
801 875
802 876 /*
803 877 * This is unfortunately a bit subtle... The problem is that if a
804 878 * state is set on one fake stree but not the other then we should
805 879 * look up the the original state and use that as the unset state.
806 880 * Fortunately, after you pop your fake stree then the cur_slist should
807 881 * reflect the original state.
808 882 */
809 883 void merge_fake_stree(struct stree **to, struct stree *stree)
810 884 {
811 885 struct stree *one = *to;
812 886 struct stree *two = stree;
813 887 struct sm_state *sm;
814 888 struct state_list *add_to_one = NULL;
815 889 struct state_list *add_to_two = NULL;
816 890 AvlIter one_iter;
817 891 AvlIter two_iter;
818 892
819 893 if (!stree)
820 894 return;
821 895 if (*to == stree)
822 896 return;
823 897 if (!*to) {
824 898 *to = clone_stree(stree);
825 899 return;
826 900 }
827 901
828 902 avl_iter_begin(&one_iter, one, FORWARD);
829 903 avl_iter_begin(&two_iter, two, FORWARD);
830 904
831 905 for (;;) {
832 906 if (!one_iter.sm && !two_iter.sm)
833 907 break;
834 908 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
835 909 sm = get_sm_state(one_iter.sm->owner, one_iter.sm->name,
836 910 one_iter.sm->sym);
837 911 if (sm)
838 912 add_ptr_list(&add_to_two, sm);
839 913 avl_iter_next(&one_iter);
840 914 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
841 915 avl_iter_next(&one_iter);
842 916 avl_iter_next(&two_iter);
843 917 } else {
844 918 sm = get_sm_state(two_iter.sm->owner, two_iter.sm->name,
845 919 two_iter.sm->sym);
846 920 if (sm)
847 921 add_ptr_list(&add_to_one, sm);
848 922 avl_iter_next(&two_iter);
849 923 }
850 924 }
851 925
852 926 FOR_EACH_PTR(add_to_one, sm) {
853 927 avl_insert(&one, sm);
854 928 } END_FOR_EACH_PTR(sm);
855 929
856 930 FOR_EACH_PTR(add_to_two, sm) {
857 931 avl_insert(&two, sm);
858 932 } END_FOR_EACH_PTR(sm);
859 933
860 934 one->base_stree = clone_stree(__get_cur_stree());
861 935 FOR_EACH_SM(one, sm) {
862 936 avl_insert(&one->base_stree, sm);
863 937 } END_FOR_EACH_SM(sm);
864 938
865 939 two->base_stree = clone_stree(__get_cur_stree());
866 940 FOR_EACH_SM(two, sm) {
867 941 avl_insert(&two->base_stree, sm);
868 942 } END_FOR_EACH_SM(sm);
869 943
870 944 free_slist(&add_to_one);
871 945 free_slist(&add_to_two);
872 946
873 947 __merge_stree(&one, two, 1);
874 948
875 949 *to = one;
876 950 }
877 951
878 952 /*
879 953 * filter_slist() removes any sm states "slist" holds in common with "filter"
880 954 */
881 955 void filter_stree(struct stree **stree, struct stree *filter)
882 956 {
883 957 struct stree *results = NULL;
884 958 AvlIter one_iter;
885 959 AvlIter two_iter;
886 960
887 961 avl_iter_begin(&one_iter, *stree, FORWARD);
888 962 avl_iter_begin(&two_iter, filter, FORWARD);
889 963
890 964 /* FIXME: This should probably be re-written with trees in mind */
891 965
892 966 for (;;) {
893 967 if (!one_iter.sm && !two_iter.sm)
894 968 break;
895 969 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
896 970 avl_insert(&results, one_iter.sm);
897 971 avl_iter_next(&one_iter);
898 972 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
899 973 if (one_iter.sm != two_iter.sm)
900 974 avl_insert(&results, one_iter.sm);
901 975 avl_iter_next(&one_iter);
902 976 avl_iter_next(&two_iter);
903 977 } else {
904 978 avl_iter_next(&two_iter);
905 979 }
906 980 }
907 981
908 982 free_stree(stree);
909 983 *stree = results;
910 984 }
911 985
912 986
913 987 /*
914 988 * and_slist_stack() pops the top two slists, overwriting the one with
915 989 * the other and pushing it back on the stack.
916 990 */
917 991 void and_stree_stack(struct stree_stack **stack)
918 992 {
919 993 struct sm_state *tmp;
920 994 struct stree *right_stree = pop_stree(stack);
921 995
922 996 FOR_EACH_SM(right_stree, tmp) {
923 997 overwrite_sm_state_stree_stack(stack, tmp);
924 998 } END_FOR_EACH_SM(tmp);
925 999 free_stree(&right_stree);
926 1000 }
927 1001
928 1002 /*
929 1003 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
930 1004 * It pops the two slists from the top of the stack and merges them
931 1005 * together in a way that preserves the things they have in common
932 1006 * but creates a merged state for most of the rest.
933 1007 * You could have code that had: if (foo || foo) { foo->baz;
934 1008 * It's this function which ensures smatch does the right thing.
935 1009 */
936 1010 void or_stree_stack(struct stree_stack **pre_conds,
937 1011 struct stree *cur_stree,
938 1012 struct stree_stack **stack)
939 1013 {
940 1014 struct stree *new;
941 1015 struct stree *old;
942 1016 struct stree *pre_stree;
943 1017 struct stree *res;
944 1018 struct stree *tmp_stree;
945 1019
946 1020 new = pop_stree(stack);
947 1021 old = pop_stree(stack);
948 1022
949 1023 pre_stree = pop_stree(pre_conds);
950 1024 push_stree(pre_conds, clone_stree(pre_stree));
951 1025
952 1026 res = clone_stree(pre_stree);
953 1027 overwrite_stree(old, &res);
954 1028
955 1029 tmp_stree = clone_stree(cur_stree);
956 1030 overwrite_stree(new, &tmp_stree);
957 1031
958 1032 merge_stree(&res, tmp_stree);
959 1033 filter_stree(&res, pre_stree);
960 1034
961 1035 push_stree(stack, res);
962 1036 free_stree(&tmp_stree);
963 1037 free_stree(&pre_stree);
964 1038 free_stree(&new);
965 1039 free_stree(&old);
966 1040 }
967 1041
968 1042 /*
969 1043 * get_named_stree() is only used for gotos.
970 1044 */
971 1045 struct stree **get_named_stree(struct named_stree_stack *stack,
972 1046 const char *name,
973 1047 struct symbol *sym)
974 1048 {
975 1049 struct named_stree *tmp;
976 1050
977 1051 FOR_EACH_PTR(stack, tmp) {
978 1052 if (tmp->sym == sym &&
979 1053 strcmp(tmp->name, name) == 0)
980 1054 return &tmp->stree;
981 1055 } END_FOR_EACH_PTR(tmp);
982 1056 return NULL;
983 1057 }
984 1058
985 1059 /* FIXME: These parameters are in a different order from expected */
986 1060 void overwrite_stree(struct stree *from, struct stree **to)
987 1061 {
988 1062 struct sm_state *tmp;
989 1063
990 1064 FOR_EACH_SM(from, tmp) {
991 1065 overwrite_sm_state_stree(to, tmp);
992 1066 } END_FOR_EACH_SM(tmp);
993 1067 }
994 1068
|
↓ open down ↓ |
199 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX