Incremental binary build enabling in edk2 - shijunjing/edk2 GitHub Wiki

Incremental binary build is a extension work of the compiler cache enabling, and apply more build cache beyond the compiling step. The incremental binary build overall is also a kind of build cache based method. For the compiler cache enabling work, see below links:

What's the incremental binary build

In a clean build, after a change to a firmware source or configuration file, the build system identifies and executes only those build operations whose result has been invalidated by the change, while other parts can be reused and produced from the cache of a previous run.

History

Edk2 tried to support the incremental binary build in before, but failed to get expected efficiency. E.g. current edk2 build command has option to enable the hash-based caching in process as blow, which is to skip unchanged build part. But the build time duration is nearly same after enable it.

  • build --help
  • --hash Enable hash-based caching during build process.

Problem statements:

Compared with state-of-art incremental build techniques in academia and industry, e.g. pluto[1] hybrid[2] Bazel[5,6], the edk2 build has below problems to limit the incremental build efficiency as well as build cache efficiency:

  1. Biggest problem: No fine-grained Dependency Graph (DG) native support to track the build targets dependency internally[1,2,3,4,5,6]. No dependency graph model, then no easy way to decide what is need to rebuild in fine-grained level if a source artifact is changed. People often think it should be easy and strait-forward to use the build cache. But before to check cache hitting or missing, you need to know what are the complete dependencies of the cached target. Current edk2 doesn't maintain any DG info internally, which is very cache unfriendly and also cause the next "Top-down" problem in parsing phase.

  1. Only Top-down in build parsing phase, and no Bottom-up algorithm [2]. Top-down parsing is always to start at the root to parse all platform info first, then decide the needed incremental build action for new changed part. But unfortunately, parsing the all platform info need spend nearly 1/3 of overall build time in many server platforms. The Bottom-up parsing is to start at changed file(think about the result of "git status"), and only parse the new changed part and its consequence. OK, it is obvious that the Bottom-up parsing need to know the platform Dependency Graph in advance(think about if we have saved the old DG). The current edk2 Top-down parsing approach is actually force to regenerate the complete platform DG in every build, even there is nothing changed, which is very inefficient.

  2. No dynamic Dependencies support[1]. Since Edk2 is bases on Make system, so all file and build dependencies must be declared statically as part of a build rule. As consequence, build rules often have to approximate their dependencies, as a missing dependency makes the build script unsound: A rule fails to execute despite a change to a file that is actually needed. On the other hand, an over approximation of dependencies limits incremental rebuilding: A rule executes because a file changed that is actually not needed. A good build system should allow all dependencies of a build rule to be dynamically discovered and support advanced dependency mechanisms that further reduce the over approximation of dependency declarations. [1]

  3. Monolithic platform build scripts (dsc, fdf, dec). We cannot directly use these monolithic scripts as the build cache inputs. Because they are too coarse-gained and will cause too many cache missing. We need break down them to pieces according to the DG granularity in build tool internally.

  • Please Note: We don't need to fix all the limitations at once, e.g. limitation 3 is a optional if we are ok for some over approximation of dependencies.

Design Goals

  1. Fine-grained Dependency Graph (DG) native support (file level)
  2. Build target dependency query support
  3. Bottom-up build model based on DG (against current Top-down)
  4. Multiple-layered build cache (model + file levels)

Reference Papers and Build Tools:

Useful implementation info:

Investigation history notes

  • 20190225
  1. Confirm the below incremental issue is fixed.

  • current Edk2 incremental build is not sound either, because the head files are not added as C file build require entities in make file at all. If the head file is updated, the incremental rebuild will fail to recompile the C file. Have submitted BZ for this issue: Header changes don’t result in incremental rebuild https://bugzilla.tianocore.org/show_bug.cgi?id=1540

  • 20190227

Begin to design the multiple-layered and distributed build cache:

  1. Two layers: module level + file level.
  1. Sharable build cache.
  • The sharable build cache need change all absolute paths to relative paths in the build result. This might only be possible for parsing tool result, but very hard for 3rd party tools, e.g. compiler, linker, etc.
  • A very simple and strait-forward way is define the identical build "base directory" and assume all the CI build agents have the same build "base directory". In fact, this hard code "base directory" method is widely adopt in many CI systme, e.g. MS CouldBuild [4]. So, I will go this way firstly.