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