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