A tool for verifying build dependencies

1,339 views
Skip to first unread message

Maxim Kalaev

unread,
May 18, 2013, 11:20:20 AM5/18/13
to ninja...@googlegroups.com
Sorry if this is slightly off the group topic...

If this helps anybody, I wrote a small tool in python for verifying correctness of build dependencies: 'depslint'.

It works by running a full build under 'strace' to figure out the "real" dependencies,
and uses this information to verify dependency graph constructed from ninja manifest
and corresponding depfiles.
I was considering to propose it be a part of 'ninja' project,
but IMO it's not small enough to be contained (but I'd be happy to know I was wrong).

It's not a big entertainment to use this on e.g., small repositories, but it can be helpful for large projects.

For demonstration, running it on ninja repository produces the following output (e.g., no issues found):
ubuntu: ninja> ../depslint/depslint.py --stats=all
INFO: Parsing Ninja manifest..
INFO: Parsing Trace log..
INFO: Building order-only graph for 'build.ninja'..
INFO: Building dependency graph for 'build.ninja'..
INFO: Building dependency graph for 'deps.lst'..

INFO: === Pass #1: checking clean build order constraints ===
INFO: === (may lead to clean build failure or, rarely, to incorrect builds) ===
INFO: No issues!

INFO: === Pass #2: checking for missing dependencies ===
INFO: === (may lead to incomlete incremental builds if any) ===
INFO: No issues!
...

But if I will maliciously modify build.ninja and remove some of the necessary dependencies:
ubuntu: ninja> diff build.ninja.bak build.ninja
33c33
< build $builddir/browse_py.h: inline src/browse.py | src/inline.sh
---
> build $builddir/browse_py.h: inline src/browse.py
36c36
< build $builddir/browse.o: cxx src/browse.cc || $builddir/browse_py.h
---
> build $builddir/browse.o: cxx src/browse.cc

then the output will be:
INFO: Parsing Ninja manifest..
INFO: Parsing Trace log..
INFO: Building order-only graph for 'build.ninja'..
INFO: Building dependency graph for 'build.ninja'..
INFO: Building dependency graph for 'deps.lst'..

INFO: === Pass #1: checking clean build order constraints ===
INFO: === (may lead to clean build failure or, rarely, to incorrect builds) ===
INFO: Errors: 1, Ignored: 0
ERROR: target 'build/browse.o' is missing ORDER dependencies on: ['build/browse_py.h']

INFO: === Pass #2: checking for missing dependencies ===
INFO: === (may lead to incomlete incremental builds if any) ===
INFO: Errors: 1, Ignored: 0
ERROR: target 'build/browse_py.h' is missing dependencies on: ['src/inline.sh']
INFO: === That's all! ===


Also, it prints some nice statistics for build rules optimizations support:
...
INFO: === Statistics ===
INFO: === Listing targets in manifest, not in the traces ===
INFO: === (these are adding an unnecessary overhead on the build system) ===
INFO: === (or indicating incomplete trace file - have you traced a clean build?) ===
INFO: No issues!

INFO: === Targets rank histograms ===
INFO: === ('rank' is target distance from the bottom of the graph) ===
INFO: === (e.g., a minimal number of sequential tasks to rebuild a target) ===
=== Targets from 'build.ninja' by order-dependencies rank ===
Rank  4:     1 targets) [ninja]
Rank  3:     1 targets) [build/libninja.a]
Rank  2:     3 targets) [build/browse.o, build/depfile_parser.o, build/lexer.o]
Rank  1:    19 targets) [build/graph.o, build/version.o, build/ninja.o, build/disk_interface.o, build/clean.o, build/util.o, build/build....
Rank  0:    21 targets) [src/state.cc, src/browse.py, src/ninja.cc, src/edit_distance.cc, src/graphviz.cc, src/subprocess-posix.cc, src/e...
=== Targets from 'build.ninja' by rebuild-dependencies rank ===
Rank  4:     1 targets) [ninja]
Rank  3:     1 targets) [build/libninja.a]
Rank  2:     3 targets) [build/browse.o, build/depfile_parser.o, build/lexer.o]
Rank  1:    19 targets) [build/graph.o, build/version.o, build/ninja.o, build/disk_interface.o, build/clean.o, build/util.o, build/build....
Rank  0:    43 targets) [src/explain.h, src/string_piece.h, src/inline.sh, src/browse.h, src/disk_interface.h, src/state.h, src/disk_inte...
=== Targets from TRACE by rank ===
Rank  4:     6 targets) [build_log_perftest, hash_collision_bench, ninja_test, parser_perftest, canon_perftest, ninja]
Rank  3:     2 targets) [build/stes1eDG, build/libninja.a]
Rank  2:     3 targets) [build/browse.o, build/depfile_parser.o, build/lexer.o]
Rank  1:    38 targets) [build/hash_collision_bench.o, build/explain.o, build/disk_interface_test.o, build/build_log_test.o, build/graph_...
Rank  0:    61 targets) [src/explain.h, src/hash_collision_bench.cc, src/disk_interface_test.cc, src/build_log_test.cc, src/string_piece....

INFO: === Targets by number of products ===
INFO: === (e.g., how many targets are rebuilt if 'x' is touched) ===
[ 0-10%]:     1 targets [src/ninja.cc(8%)]
[10-20%]:    26 targets [src/explain.h(16%), src/inline.sh(16%), src/browse.h(16%), src/depfile_parser.h(16%), src/subprocess.h(16%), src...
[20-30%]:     8 targets [src/disk_interface.h(29%), src/exit_status.h(29%), src/build.h(25%), src/lexer.h(25%), src/build_log.h(25%), src...
[30-40%]:     2 targets [src/hash_map.h(37%), src/state.h(33%)]
[40-50%]:     3 targets [src/timestamp.h(45%), src/metrics.h(45%), src/graph.h(41%)]
[50-60%]:     1 targets [src/eval_env.h(50%)]
[60-70%]:     2 targets [src/string_piece.h(62%), src/util.h(62%)]
INFO: === That's all! ===

Evan Martin

unread,
May 18, 2013, 10:39:20 PM5/18/13
to Maxim Kalaev, ninja-build
Sounds neat!  I think the tup build system has a feature that uses ptrace to identify build dependencies too.

(Did you intend to link to your script?)



--
You received this message because you are subscribed to the Google Groups "ninja-build" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ninja-build...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

Maxim Kalaev

unread,
May 19, 2013, 3:38:29 AM5/19/13
to Evan Martin, ninja-build
IMO, Tup now uses 'fuse' to intercept filesystem IO to discover dependencies dynamically. Using fuse is a way faster than using ptrace (and 2 ways faster when parsing strace output), but all approaches have their own issues.
Other alternatives are LD_PRELOAD to hook on libc interfaces, this was used in the earlier versions of Tup, or something from ftrace/prof family on Linux.

Clean build of my project takes ~ x8 times when runs under depstrace.py, but this is tolerable since you only do this "once" to find and fix your build problems, and from here you may just run it as part of nightly builds if you like.

--

Maxim

Marc-Antoine Ruel

unread,
May 21, 2013, 5:45:34 PM5/21/13
to Maxim Kalaev, Evan Martin, ninja-build, Christopher Sharp, Vadim Shtayura
+Chris and Vadim who are working with me on higher level components.

Thanks Maxim, that's a very interesting idea;

I wrote a similar tool to depstrace.py named trace_inputs.py to figure out the runtime dependencies of chromium tests for test isolation purposes but I hadn't thought about using it for ninja. The reason I'm shamelessly plugging it is that trace_inputs.py also works on OSX via dtrace and Windows via the NT Kernel Logger, in addition to strace support. trace_inputs.py was tested against chromium test cases, some start over 50 child processes and kill some children before they even have the chance to finish initializing. A lot of strace corner cases were found this way. I also have a branch here that enables running strace under sudo, which is necessary with some of the chromium sandbox + nacl subprocesses. I may kick myself to complete it sooner if there's interest in this.

To clarify about trace_inputs' goal when I designed it last summer: get a complete view of the files accessed by the process tree created by potentially somewhat aggressive processes, e.g. test cases. In addition, the generated data is in the same format independent of the OS or the tracing infrastructure that was used. It handles nasty things like case insensitivity on OSX and Windows, cwd handling in strace like it's done in depstrace.py, screwed up path handling in Windows and strace broken -f support due to internal race conditions in it. By no mean I claim trace_inputs.py is bug free but it works pretty well and is well tested.

Another reason I'm noting it here is that trace_inputs.py is designed to be used as a stand-alone library. As an example,  trace_test_cases.py can traces multiple chromium test cases simultaneously, and that even if the tracer is usermode based (like strace) or kernel mode based (like dtrace). I think the resulting client code is quite easy to manage, as shown in trace_test_cases.py or isolate_test_cases.py. This makes it possible to trace multiple build steps concurrently, even on Windows! Note that on on both OSX and Windows, it is preferable to keep tracing session relatively short because of the sluggishness with the current D dtrace code and the overwhelming amount of data generated by the NT Kernel Logger. Sadly, this means tracing a large project like chromium could take hours on these OSes.


To get more practical, the following works on Windows, OSX or linux:
<checkout chromium, sync past r201347>
cd src
# Replace $(which ninja) with the absolute path.
# For consistency across OSes, an absolute executable path is required. 
python tools/swarm_client/trace_inputs.py trace -l foo $(which ninja) -C out/Release obj/base/base.cpu.o
# Chromium built with ninja on Windows uses .obj instead
# of .o and won't accept / for target paths, but it does for -C (?):
python tools/swarm_client/trace_inputs.py trace -l foo c:\path\to\depot_tools\ninja.exe -C out/Release obj\base\base.cpu.obj
# --root-dir strips any file outside the specified directory.
# Try with and without to see the difference. Replace 'less' with 'more' on Windows:
python tools/swarm_client/trace_inputs.py read -l foo --root-dir . | less
python tools/swarm_client/trace_inputs.py read -l foo | less
# Prints to stdout the whole data as json, including the process tree:
python tools/swarm_client/trace_inputs.py read -l foo --root-dir . --json | less

I have another code branch at home that loads the json data as an interactive web page but I'm really a slacker and it's not complete yet.

In practice, you don't need the whole chromium checkout. You can only get the relevant code with:

and I kept trace_inputs.py usable as a stand-alone file so you don't even need the whole swarm_client checkout, just download trace_inputs.py and you can use it as-is. In the specific case of your tool, it'd only replace depstrace.py. Here a functional basic example:

import os, pprint
import trace_inputs
cmd = ['/path/to/depot_tools/ninja', '-C', 'out/Release', 'obj/base/base.cpu.o']
logname = os.path.join(os.getcwd(), 'my_first_trace')
tracename = 'trace_1'
api = trace_inputs.get_api()
api.clean_trace(logname)
# 'tracer' lifetime determines the active tracing lifetime on kernel based
# tracers. It is insignificant for strace.
with api.get_tracer(logname) as tracer:
  tracer.trace(cmd, os.getcwd(), tracename, True)

data = api.parse_log(logname, lambda _: False, tracename)
pprint.pprint(data[0]['results'].flatten())


So my question is: Maxim, do you think you would accept a merge request that would make depslint.py use trace_inputs.get_api(), so that it could be used on other platforms? I think it would be much more valuable since it'd work across most OSes. I don't think trace_inputs covers everything, it's really designed to trace files read, not written to but I think it's mostly fixable.

Thanks,

M-A


References
Sources:
Strace implementation is around line 1106:
Example of using trace_inputs as a multithreaded library:

The docs are somewhat stale but the general idea still hold:




2013/5/19 Maxim Kalaev <maxim...@gmail.com>

Maxim Kalaev

unread,
May 22, 2013, 4:45:01 PM5/22/13
to ninja...@googlegroups.com, Maxim Kalaev, Evan Martin, Christopher Sharp, Vadim Shtayura
I am glad to hear you like the idea. trace_inputs.py looks like an impressive piece of work, my main concern now is that it is probably more complex then it is required for the specific case.
Gentlemen, I propose to continue the discussion at github, if you like, as its not directly relevant to this forum.


On Wednesday, May 22, 2013 12:45:34 AM UTC+3, Marc-Antoine Ruel wrote:
+Chris and Vadim who are working with me on higher level components.

Thanks Maxim, that's a very interesting idea;

I wrote a similar tool to depstrace.py named trace_inputs.py to figure out the runtime dependencies of chromium tests for test isolation purposes but I hadn't thought about using it for ninja. The reason I'm shamelessly plugging it is that trace_inputs.py also works on OSX via dtrace and Windows via the NT Kernel Logger, in addition to strace support. trace_inputs.py was tested against chromium test cases, some start over 50 child processes and kill some children before they even have the chance to finish initializing. A lot of strace corner cases were found this way. I also have a branch here that enables running strace under sudo, which is necessary with some of the chromium sandbox + nacl subprocesses. I may kick myself to complete it sooner if there's interest in this.
...

Michael Ainsworth

unread,
Aug 19, 2018, 1:17:03 PM8/19/18
to ninja-build
I know I'm coming to this conversation very late, but I have been writing a
build tool that automatically tracks dependencies in a similar fashion to that
described by the author of Tup in the linked article. The tool is meant to be
used in "daemon mode" only. It's called "lmake" for "Linux Make", but the
architecture could allow it to be used on other platforms as well.

The architecture is as follows:

There are three components: the "builder", the "watcher" and the "coordinator".
Following the UNIX tradition, each of these components is run as a separate
process and all communication is via simple text-based protocol on (pipe'd)
stdin, stdout and stderr.

Builders read on standard input a "build" command (e.g., "build gcc -c hello.c
-o hello.c.o"), write to standard output dependencies ("input hello.c \n output
hello.c.o") and status messages ("success" or "failure"), and writes to
standard error command output (like compiler errors). The default "builder" is
"lmake-builder-ptrace", and, as the name suggests, uses the "ptrace()" system
call to track dependencies. Another builder is "lmake-builder-ldpreload", which
- again as the name suggests - uses LD_PRELOAD to intercept calls.

Watchers read on standard input files to watch (e.g., "watch hello.c"), write
to standard output events ("changed hello.c") and write to standard error any
issues that occur (e.g., "Unable to watch hello.c: file does not exist"). The
default watcher is "lmake-watcher-inotify", and uses the "inotify()" system
call on Linux to monitor the file system. Another watcher is
"lmake-watcher-timer", which periodically scans the file system to see if any
files have changed.

There is only one coordinator ("lmake"), which interfaces between the watcher
and the various builders. That is, when the watcher says "Hey, just so you
know, the file 'hello.c' was just changed" the coordinator can automatically
distribute work to each of the builders in order to compile only what is
necessary, and only when necessary.

Having three separate processes allows flexibility and testability. That is,
you can easily run "echo build gcc -c main.c | lmake-builder-ptrace" (without
the coordinator) to see what files are used by a process. Likewise, you can
easily run "echo watch hello.c | lmake-watcher-inotify" and see what events are
produced. Again, you could have a OS-specific builder for other platforms.
Perhaps fswatch for macOS? Something hacky and horribly slow for Windows?
(Jks).

Three separate processes could also allow distributed builds. E.g., you can
pipe the build commands to builders on other computers. Of course, the builder
protocol would need to be enhanced in order to allow file distribution.

There are two reasons why I started working on "lmake". Firstly, I wanted a
daemon-like build system. That is, as soon as I saved a file, I wanted the
project rebuilt. The "watcher" component solves this first problem.
(Incidentally, one complaint against using compiled languages for web
applications is the long edit/compile/test build cycle, which, when using a
daemon, is effectively reduced to that of interpreted languages).  Secondly, I
wanted accurate dependency tracking. I dislike GNU Make dependencies, because
implicit/explicit dependencies are hacky (e.g., the "$<" vs "$^" inputs). Ninja
does this in a much better way using explicit ("$in"), implicit ("|") and
order-only dependencies ("||"), but you still have to manually list the
dependencies. The "builder" component solves this second problem, and also
allows rather minimal configuration files (and ones that can be executed
directly in the shell in case the user doesn't have "lmake" installed). E.g.:
the configuration file below can be executed by "lmake" or can be executed
directly in the shell by typing "source lmake.config".

    gcc -c foo.c -o foo.c.o
    gcc -c bar.c -o bar.c.o
    gcc foo.c.o bar.c.o -o hello-world

Anyway, "lmake" still has a lot of work before it's production ready. I
recently stopped work on it because it was distracting me from getting any
actual work done. Instead I decided to write a small utility "wexec", which
executes a program (e.g., "ninja") after a period of inactivity on standard
input, which, when combined with a tool like "inotifywait", effectively solves
problem 1 above (automatic rebuilds). However, problem 2 above (automatic
dependency trakcing) is still not well managed.

I'd like to make clear that I LOVE ninja. I'm not trying to hijack this thread
and I'm not suggesting a "better tool" (lmake is a rather garbage
implementation of the idea). Among a plethora of goodies, ninja is incredibly
fast, easy to use, and has a very simple configuration file format. Would there
be any interest in implementing a feature to automatically track dependencies?
Among ninja's features, this would be - in my opinion - the best.

(Also, I couldn't find the github discussion and I don't know how much overlap
this has with what others have written.)
Reply all
Reply to author
Forward
0 new messages