On Sat, May 03, 2008 at 10:27:18PM +0200, Vegard Nossum wrote:
> Hi,
>
> Here comes v2 of this tool. I've addressed most of your nitpicks and specific
> comments. Running 'make headerdep', will go through all headers (instead of
> source files as v1 did). Running with the --graph option will produce a
> dependency graph in the 'dot' language (GraphViz).
>
> Note that I am not really making an attempt to include this in the kernel
> itself; I am submitting it in the hope that somebody will find it useful.
>
> For Sam: Writing this in sparse is a waste of time. Sparse is good for parsing
> C code; this script only cares about a subset of the C _preprocessor_ parsing.
> Perl is good at this, and the script was finished in a couple of hours. Sparse
> is C and would require a bit more work, I'm sure.
>
> The most useful tool, as suggested by several people (Matthew Wilcox,
> Sam Ravnborg), would be the one that detects unused headers and missing
> (implicit) includes. That is indeed a job for sparse. But not a job for me,
> or at least not yet :-)
>
> So again, I have no expectations for this to go in the kernel -- but in my
> opinion a tool that could be used on the kernel headers with some advantage.
Hi Vegard.
Digging through my mailbox I found this patch of yours.
I tried to apply it and saw following output:
In file included from linux/mmzone.h,
from linux/topology.h
from linux/mmzone.h
from linux/gfp.h
from linux/slub_def.h
from linux/slab.h
from linux/percpu.h
from asm-generic/irq_regs.h
include/asm-xtensa/irq_regs.h: warning: recursive header inclusion
But looking at the file (include/asm-xtensa/irq_regs.h) did
not help me understand where to look to fix it.
Can you pinpoint the culprint better so this is becoming useful?
I would also like to see this integrated with checkincludes.pl
as both script do some simple static checks of the header files.
Additional bonus if we can reuse this to do better check of
our exported headers.
Sam
On Sat, Dec 13, 2008 at 11:22 PM, Sam Ravnborg <[email protected]> wrote:
> I tried to apply it and saw following output:
> In file included from linux/mmzone.h,
> from linux/topology.h
> from linux/mmzone.h
> from linux/gfp.h
> from linux/slub_def.h
> from linux/slab.h
> from linux/percpu.h
> from asm-generic/irq_regs.h
> include/asm-xtensa/irq_regs.h: warning: recursive header inclusion
>
> But looking at the file (include/asm-xtensa/irq_regs.h) did
> not help me understand where to look to fix it.
The program was run with include/asm-xtensa/irq_regs.h as input. So it
displays the whole chain of inclusion. The cycle is just the upper part:
> In file included from linux/mmzone.h,
> from linux/topology.h
> from linux/mmzone.h
...so that's where to look in general. I checked mmzone.h and topology.h,
and they do indeed include each other.
>
> Can you pinpoint the culprint better so this is becoming useful?
Line numbers would be nice, I agree. We can also have just the cycle stand
out a bit more. This is the new format:
$ perl scripts/headerdep.pl include/asm-xtensa/irq_regs.h
In file included from linux/mmzone.h,
from linux/topology.h:32
from linux/mmzone.h:763 <-- here
from linux/gfp.h:4
from linux/slub_def.h:10
from linux/slab.h:152
from linux/percpu.h:5
from asm-generic/irq_regs.h:15
include/asm-xtensa/irq_regs.h:1: warning: recursive header inclusion
> I would also like to see this integrated with checkincludes.pl
> as both script do some simple static checks of the header files.
>
> Additional bonus if we can reuse this to do better check of
> our exported headers.
This one is probably a bit too noisy? But if we can eliminate the existing
cycles, it would be nice, I agree. Thanks for the feedback! :)
Vegard
>From 24d6e19682ce2b7ffa6c032fb0199dbcabcc1a5b Mon Sep 17 00:00:00 2001
From: Vegard Nossum <[email protected]>
Date: Tue, 16 Dec 2008 12:33:43 +0100
Subject: [PATCH] headerdep: add a tool to detect inclusion cycles in header files #3
Signed-off-by: Vegard Nossum <[email protected]>
---
Makefile | 7 ++-
scripts/headerdep.pl | 193 ++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 199 insertions(+), 1 deletions(-)
create mode 100755 scripts/headerdep.pl
diff --git a/Makefile b/Makefile
index 9a49960..d4b13d9 100644
--- a/Makefile
+++ b/Makefile
@@ -1022,6 +1022,10 @@ include/linux/version.h: $(srctree)/Makefile FORCE
include/linux/utsrelease.h: include/config/kernel.release FORCE
$(call filechk,utsrelease.h)
+PHONY += headerdep
+headerdep:
+ @find include/ -name '*.h' | xargs --max-args 1 scripts/headerdep.pl
+
# ---------------------------------------------------------------------------
PHONY += depend dep
@@ -1270,7 +1274,8 @@ help:
@echo ' versioncheck - Sanity check on version.h usage'
@echo ' includecheck - Check for duplicate included header files'
@echo ' export_report - List the usages of all exported symbols'
- @echo ' headers_check - Sanity check on exported headers'; \
+ @echo ' headers_check - Sanity check on exported headers'
+ @echo ' headerdep - Detect inclusion cycles in headers'; \
echo ''
@echo 'Kernel packaging:'
@$(MAKE) $(build)=$(package-dir) help
diff --git a/scripts/headerdep.pl b/scripts/headerdep.pl
new file mode 100755
index 0000000..b3265f6
--- /dev/null
+++ b/scripts/headerdep.pl
@@ -0,0 +1,193 @@
+#! /usr/bin/perl
+#
+# Detect cycles in the header file dependency graph
+# Vegard Nossum <[email protected]>
+#
+
+use strict;
+use warnings;
+
+use Getopt::Long;
+
+my $opt_all;
+my @opt_include;
+my $opt_graph;
+
+&Getopt::Long::Configure(qw(bundling pass_through));
+&GetOptions(
+ help => \&help,
+ version => \&version,
+
+ all => \$opt_all,
+ I => \@opt_include,
+ graph => \$opt_graph,
+);
+
+push @opt_include, 'include';
+my %deps = ();
+my %linenos = ();
+
+my @headers = grep { strip($_) } @ARGV;
+
+parse_all(@headers);
+
+if($opt_graph) {
+ graph();
+} else {
+ detect_cycles(@headers);
+}
+
+
+sub help {
+ print "Usage: $0 [options] file...\n";
+ print "\n";
+ print "Options:\n";
+ print " --all\n";
+ print " --graph\n";
+ print "\n";
+ print " -I includedir\n";
+ print "\n";
+ print "To make nice graphs, try:\n";
+ print " $0 --graph include/linux/kernel.h | dot -Tpng -o graph.png\n";
+ exit;
+}
+
+sub version {
+ print "headerdep version 2\n";
+ exit;
+}
+
+# Get a file name that is relative to our include paths
+sub strip {
+ my $filename = shift;
+
+ for my $i (@opt_include) {
+ my $stripped = $filename;
+ $stripped =~ s/^$i\///;
+
+ return $stripped if $stripped ne $filename;
+ }
+
+ return $filename;
+}
+
+# Search for the file name in the list of include paths
+sub search {
+ my $filename = shift;
+ return $filename if -f $filename;
+
+ for my $i (@opt_include) {
+ my $path = "$i/$filename";
+ return $path if -f $path;
+ }
+
+ return undef;
+}
+
+sub parse_all {
+ # Parse all the headers.
+ my @queue = @_;
+ while(@queue) {
+ my $header = pop @queue;
+ next if exists $deps{$header};
+
+ $deps{$header} = [] unless exists $deps{$header};
+
+ my $path = search($header);
+ next unless $path;
+
+ open(my $file, '<', $path) or die($!);
+ chomp(my @lines = <$file>);
+ close($file);
+
+ for my $i (0 .. $#lines) {
+ my $line = $lines[$i];
+ if(my($dep) = ($line =~ m/^#\s*include\s*<(.*?)>/)) {
+ push @queue, $dep;
+ push @{$deps{$header}}, [$i + 1, $dep];
+ }
+ }
+ }
+}
+
+sub print_cycle {
+ # $cycle[n] includes $cycle[n + 1];
+ # $cycle[-1] will be the culprit
+ my $cycle = shift;
+
+ # Adjust the line numbers
+ for my $i (0 .. $#$cycle - 1) {
+ $cycle->[$i]->[0] = $cycle->[$i + 1]->[0];
+ }
+ $cycle->[-1]->[0] = 0;
+
+ my $first = shift @$cycle;
+ my $last = pop @$cycle;
+
+ my $msg = "In file included";
+ printf "%s from %s,\n", $msg, $last->[1] if defined $last;
+
+ for my $header (reverse @$cycle) {
+ printf "%s from %s:%d%s\n",
+ " " x length $msg,
+ $header->[1], $header->[0],
+ $header->[1] eq $last->[1] ? ' <-- here' : '';
+ }
+
+ printf "%s:%d: warning: recursive header inclusion\n",
+ $first->[1], $first->[0];
+}
+
+# Find and print the smallest cycle starting in the specified node.
+sub detect_cycles {
+ my @queue = map { [[0, $_]] } @_;
+ while(@queue) {
+ my $top = pop @queue;
+ my $name = $top->[-1]->[1];
+
+ for my $dep (@{$deps{$name}}) {
+ my $chain = [@$top, [$dep->[0], $dep->[1]]];
+
+ # If the dep already exists in the chain, we have a
+ # cycle...
+ if(grep { $_->[1] eq $dep->[1] } @$top) {
+ print_cycle($chain);
+ next if $opt_all;
+ return;
+ }
+
+ push @queue, $chain;
+ }
+ }
+}
+
+sub mangle {
+ $_ = shift;
+ s/\//__/g;
+ s/\./_/g;
+ s/-/_/g;
+ $_;
+}
+
+# Output dependency graph in GraphViz language.
+sub graph {
+ print "digraph {\n";
+
+ print "\t/* vertices */\n";
+ for my $header (keys %deps) {
+ printf "\t%s [label=\"%s\"];\n",
+ mangle($header), $header;
+ }
+
+ print "\n";
+
+ print "\t/* edges */\n";
+ for my $header (keys %deps) {
+ for my $dep (@{$deps{$header}}) {
+ printf "\t%s -> %s;\n",
+ mangle($header), mangle($dep->[1]);
+ }
+ }
+
+ print "}\n";
+}
--
1.5.6.5
>
> This one is probably a bit too noisy? But if we can eliminate the existing
> cycles, it would be nice, I agree. Thanks for the feedback! :)
Applied to kbuild-next.
Sam