Hash-based Checking

Introduction

There are a number of good reasons to prefer hashing over time stamps to determine which files have changes. See Build-Systems Should Use Hashes Over Timestamps for example.

(Although note that as tmake uses a cache for previous hashes/timestamps this mitigates some of the worst aspects of timestamp checking as it does not require time to always go forward to determine that a file has changed. Any change in timestamp is considered a change).

tmake provides both hash-based and time-based comparisons as suitable for the project. Hash-based comparison vs Time-based comparison can be enabled with UseHashes on|off in project.spec, or tmake --hash (for testing) . The default is time-based comparison.

When to use hashing

Use of hashing is a choice that will typically depend on whether the timestamps of files will often change without their contents changing. For example a revision control system may update the timestamp on many files when checking out versions/branches even if the contents don't change. If this is common for your project, adding UseHashes on to project.spec will use hashing within the project.

Hashing targets

As explained above, even with hashing enabled (UseHashes on), tmake still only hashes sources, not targets (build products) by default. However sometimes it can be useful to hash targets. Consider the following (contrived) example:

$ cat build.spec
use template

define? VAR1 1
define? VAR2 2

# Note that VAR2 isn't used in config.h.in so changing the value
# will cause the the rule to run but the file will be unchanged
Template config.h config.h.in VAR1 VAR2

Executable --test test-config test-config.c
$ cat config.h.in
#define VAR1 @VAR1@

Notice that VAR2 isn't used in config.h.in so changing the value won't change the value of the generated config.h. First build with the default value of VAR2=2

$ tmake 
    Template     config.h
    Cc           test-config.o
    Link         test-config
Built 3 of 3 target(s) in 0.25 seconds

Now build again, this time with VAR2=3

$ tmake VAR2=3
    Template     config.h
    Cc           test-config.o
    Link         test-config
Built 3 of 3 target(s) in 0.13 seconds

Notice that even though config.h didn't change test-config.o was rebuilt. This is true even if hashing is used. So now adding -hash to the template causes the checking on this target to use hashing rather than timestamps.

$ cat build.spec
use template

define? VAR1 1
define? VAR2 2

# Note that VAR2 isn't used in config.h.in so changing the value
# will cause the the rule to run but the file will be unchanged
target [Template config.h config.h.in VAR1 VAR2] -hash

Executable --test test-config test-config.c

The first time it is rebuilt, it is considered changed because the hash has changed from a timestamp to a hash:

$ tmake VAR2=4
    Template     config.h
    Cc           test-config.o
    Link         test-config
Built 3 of 3 target(s) in 0.11 seconds

However subsequent builds only cause the template to be regenerated. Because the hash is the same, and targets that depend on config.h are not rerun.

$ tmake VAR2=5 -dnh
    9ms [h m] Using md5 module for hashing
   10ms [n] test-config.c is not a target, but exists
   10ms [n] config.h.in is not a target, but exists
   10ms [n] Deps for config.h are unchanged, not building
    Template     config.h
   12ms [h] md5sum objdir/config.h => md5:2ae0ef2fbd474679034fd10cad3ff00c
   12ms [n] Deps for test-config.o are unchanged, not building
   12ms [n] Commands for test-config.o are unchanged
   12ms [n] Deps for test-config are unchanged, not building
   12ms [n] Commands for test-config are unchanged
Built 1 of 3 target(s) in 0.01 seconds

The use of target hashing can be particularly beneficial for generated header files that are included by many source files that may be regenerated often. For example the config header files generated by Kconfig

How tmake implements hashing

Consider the following rules (where ← means depends on):

a ← c d
b ← c d

When deciding whether to build a target, tmake looks at the previous hashes and the current hashes of c and d. Consider the case where the target previously ran and the hash dependency hashes were recorded in the cache.

dephashes(a) = c hash(c)|d hash(d)

Now when deciding whether to build a target, tmake computes hashes of all it's dependencies. If the result is the same answer as the saved dephashes(a), there is no need to build. If it is different, tmake updates dephashes(a) in the cache and continues to build. It is OK to update the cache and then have the build fail, because the build will rerun next time (for the same reason it ran this time).

There a few extra things to consider.

  • If the targets need to be built for some other reason (e.g. does not exist), the hash of dependents is not computed immediately. Rather the check is done after all the dependents are successfully created.

  • Rather than compute the hash every time, tmakes stores the mtime and hash of dependencies in the cache. If the mtime matches what is stored in the cache, the hash is used from the cache. Otherwise the hash is computed and the cache entry is updated.

  • PublishIncludes uses "Publish --hash" to add -hash to the publish rules. Since the published header files are targets, normally they would use time-based comparison rather than hash-based comparison. But these published headers are really source (unless generated), so hash-based comparison is used to prevent unecessary rebuilds.

  • It would be expensive to compute hashes of possibly large generated targets. Generated files are only be generated by the build system, so mtimes for these files will change when they are created/modified - thus tmake uses mtime as a proxy for the hash for targets. If the mtime changes (either forwards or backwards), the file is considered to have changed. If it is desired to use hashing on certain targets, -hash can be set on the target rule to force a hash check rather than a time check.

  • Switching from hash-based to time-based and back to hash-based builds could cause problems with out-of-date hashes as these are not updated when running time-based builds. For this reason, when switching to time-based, hashes are removed from the cache.

Hashes are computed by running 'md5sum' (or md5, for MacOS) because it is a fast hash with a low chance of collisions. If the 'md5' module is available for jimsh, this is used instead.

The results of the search are