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