[RFC] sccache direct mode design discussion

[badumbatish]

sccache direct mode design discussion

Intro

Hi there, I'm starting this issue to discuss how to resolve the direct mode limitation about the silent stale cache issue to hopefully get the implementation merged into the codebase if it makes sense.

Currently, we still have the following situation within sccache (from https://bugzilla.samba.org/show_bug.cgi?id=8424#c4) when enabling direct mode

Simpler case to reproduce (using direct mode).

hello.c
inc2/hello.h

$ gcc -Iinc1 -Iinc2 -c hello.c 
# cache miss, result cached

add inc1/hello.h 

$ gcc -Iinc1 -Iinc2 -c hello.c 
# cache hit, inc1/hello.h ignored

From what i know, this is because sccache can only record the header file with the same name in inc2, resulting in silent stale cache when the same file name is added in inc1.

From the comment in the discussion of sccache design bug, I've decided to implement said strategy and measure said approach on real world codebases:

Running the compiler with -v prints the header search directories. You could use that to do your own scan. It would be difficult to differentiate files specified by the user with absolute paths from files found by the compiler.

Strategy

Setting up the preprocessor for include dir parser (First patch)

The strategy for implementing this is, in gcc.rs's preprocess_cmd', we first add -Wp,-v to the preprocessing, this causes gcc/clang to emit the minimal extra information about file search paths into stderr.

Example of said relevant stderr section:

#include "..." search starts here:
#include <...> search starts here:
 inc1
 inc2
 /nix/store/qxaq7jz61a6zkr2mq49i0zvqip2m2jj8-gcc-15.2.0/lib/gcc/x86_64-unknown-linux-gnu/15.2.0/include
...

We then implement a minimal parser to be called in c.rs's generate_hash_key to parse the stderr to collect the include paths.

This concludes the first stage of the series

Second patch

After we've parsed the include paths from "..." and <...>, within the same generate_hash_key, after process_preprocessed_file function call, we now have:

• The tracked include files being used as the preprocessor cache entry (this is the fact that sccache (and ccache before it) can only record the header files that were used).
• The recorded include directories that gcc/clang is searching for.

We can then start to whittle down the necessary directory to be scanned when we eventually use the direct mode cache.

First, supposed our header H lives in directory D, we only need to scan the directories that appear before D to detect the staleness of our header (anything directory appearing after D already obey the natural search path of the compiler).

Noting that process_preprocessed_file returns absolute paths for tracked header files, the algorithm for wittling down the necessary directory is as follows:

• for each included file H that was tracked by process_preprocessed_file
  • for each include dir D we've parsed via the parser , check if D has the prefix that's part of the path of H
    • Add all the include dirs before D (that doesn't contain H and hasn't been added yet) to the resulting vector

We don't break the for loop after we've found a particular D, consider the following example
H's absolute path is /a/b/c.h

D1 is /a/,
D2 is /a/b/

If we confirm D to be D1 and quit, we cant confirm D1 to be exactly the right dir that contains H, thus producing stale cache.

If we decide to elect the longest matching prefix as our breaker for the for loop, we also produce stale cache.

Consider D1 is /a/b/, D2/a/, then D is D1 again, we quit. The compiler might have resolved H through D2, at this point, we'll also be looking at a stale cache.

Thus, we decide to overshoot our looking into more directories instead of undershooting.

After we've trimmed down the necessary directories, the information is stored in the direct mode cache. This means

• updating the FORMAT version 0 -> 1.
• modifying PreprocessorCacheEntry to now include results: BTreeMap<String, ResultEntry> instead of results: BTreeMap<String, Vec<IncludeEntry>>

where ResultEntry is

pub struct ResultEntry {
    includes: Vec<IncludeEntry>,
    /// Paths in search dirs *earlier* than where each include resolved. If any
    /// appears, an include would now resolve to a different file and this
    /// result is stale. Basedir-relative, like [`IncludeEntry::path`].
    shadow_probes: Vec<OsString>,
}

Wiring this shadow_probes through out the call stacks to result_matches, before checking for hashed contents and so on, we check if any of the recorded included directories contains H, if so, it means we fall back to calling the preprocessor again.

False negatives

This section discusses the false negative in result_matches. Despite false negatives that might occur when we're checking for H in the recorded included directoies, we can confirm that the system will not fall into a perpetual state of direct mode misses.

Suppose the recorded shadow_probes is [A, B, C], and the true directory that houses the header H is between B and C on the search path. If we don't find H in A, and B, but C instead, we have to fall back to calling the preprocessor. This is a false negative.

Now, when we run the preprocessor again, in our trimming of directories, since C now also posesses H, it'll be excluded from the recorded shadow_probes, and we'll correctly hit the direct cache; thus achieving a self-healing loop.

Performance

Testing the new implementation on top of the existing direct mode for a large codebase (llvm and such), I observe a 10% reduction in build time, from 36s->40s. This seems acceptable in my opinion despite the O(n^2) complexity in checking for include dirs to be recorded.