Systems Research and Architecture System und Rechnerarchitektur SRA
a SRA Theses cHash FUSE

Implementierung und Evaluation eines FUSE-Dateisystems für Linux zur Integration erweiterter Änderungsdetektionsverfahren in Buildsystemen

Software written in a compiled language is normally build with the help of a build system. Initially, the build system invokes the compiler for every source file (.c file) in order to translate it to an object file. Later on, all object files are combined into a single binary. This partitioning of the source code into translation units allows the employment of incremental builds: When a source file, or any of its included headers, are changed only the corresponding object file is rebuild.

However, not every textual change in the source file, or any of its included headers, leads to an altered binary. For example, adding a type declaration that is nowhere used in the translation unit leads do an redundant build operation; the resulting object file will not change.

In previous work, we have developed a semantic hashing algorithm on the abstract-syntax-tree level of the compiler to generate a fingerprint of the actual translation unit. In case of an unused declaration, the type definition is not included into the hash value. By comparing the hash value with the hash from the previous compilation, we can determine, if we can abort the compiler execution directly after the parsing step, before the costly compiler optimization phases are started.

Other build systems use different metrics to determine whether a translation unit has to be recompiled or not. Make for example uses modification timestamps, which often leads to redundant build operations.

Goal of this thesis is to expose changed hashes of translation units as updated timestamps of the corresponding files to Make using a Filesystem in Userspace (FUSE). This allows to keep using Make, and therefore other build systems based on Make, while benefiting from cHash at the same time. After implementing the FUSE, redundant build operations and compatibility with Make-based build systems can be evaluated.

USENIX Conference A Best Paper Award
cHash: Detection of Redundant Compilations via AST Hashing
Christian Dietrich, Valentin Rothberg, Ludwig Füracker, Andreas Ziegler, Daniel LohmannProceedings of the 2017 USENIX Annual Technical Conference (USENIX '17)USENIX Association2017Best Paper Award.
PDF Details Slides Raw Data [BibTex]