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