1#!/usr/bin/perl
2
3use strict;
4
5sub usage()
6{
7    print "Usage: unlocked_paths.pl <call tree file> <lock> <function>\n";
8    print "Prints a list of paths to <function> which don't take the <lock>.\n";
9    print "Generate the call tree file by running smatch with --call-tree.\n";
10    exit(1);
11}
12
13my %f_map;
14
15sub add_to_map($)
16{
17    my $callee = shift;
18
19    if (!defined($f_map{$callee})) {
20	$f_map{$callee} = {visited => 0, called_by => {}};
21    }
22}
23
24sub add_called_by($$)
25{
26    my $caller = shift;
27    my $callee = shift;
28    my $tmp;
29
30    %{$f_map{$callee}->{called_by}}->{$caller} = 1;
31}
32
33sub load_all($$)
34{
35    my $file = shift;
36    my $lock = shift;
37
38    open(FILE, "<$file");
39    while (<FILE>) {
40	if (/.*?:\d+ (.*?)\(\) info: func_call \((.*)\) (.*)/) {
41	    my $caller = quotemeta $1;
42	    my $locks = quotemeta $2;
43	    my $callee = quotemeta $3;
44
45	    add_to_map($callee);
46	    if (!($locks =~ /$lock/)) {
47		add_called_by($caller, $callee);
48	    }
49	}
50    }
51}
52
53my @fstack;
54sub print_fstack()
55{
56    foreach my $f (reverse @fstack) {
57	printf "$f ";
58    }
59    printf "\n";
60}
61
62sub print_unlocked_paths($)
63{
64    my $function = shift;
65
66    if (! defined %{$f_map{$function}}->{called_by}) {
67	push @fstack, $function;
68	print_fstack();
69	pop @fstack;
70	return;
71    }
72
73    push @fstack, $function;
74
75    if (!%{$f_map{$function}}->{visited}) {
76	%{$f_map{$function}}->{visited} = 1;
77	foreach my $caller (keys %{%{$f_map{$function}}->{called_by}}){
78	    print_unlocked_paths($caller);
79	}
80	%{$f_map{$function}}->{visited} = 0;
81
82    }
83
84    pop @fstack;
85}
86
87my $file = shift;
88my $lock = shift;
89my $target = shift;
90
91if (!$file || !$lock || !$target) {
92    usage();
93}
94if (! -e $file) {
95    printf("Error:  $file does not exist.\n");
96    exit(1);
97}
98
99load_all($file, $lock);
100print_unlocked_paths($target);
101