[Openembedded-architecture] [openembedded-architecture] sstate equivalency

[Richard Purdie]

On Tue, 2018-05-01 at 15:28 -0500, Joshua Watt wrote:
> I have some interest it looking into the sstate equivalency as
> discussed in the Yocto Project Technical Meeting. I know there have
> been a few discussions about how to handle this problem, so please
> chime in with any information or background you may have.
> 
> To start things off, I figured I would try to briefly summarize the
> problem so that we have a clear idea what we are trying to solve.
> 
> My understanding is that there are many changes that can be made to a
> recipe that don't actually have any affect on what the recipe
> generates (comments in shell tasks(?), that sort of thing), but still
> figure into the sstate task hashes. When such changes are detected,
> it would be convenient to users if the build could detect that these
> task hashes are actually equivalent, and allow one sstate cache
> object to be used in place of the other (e.g. If you have sstate
> object A and your build calculates the hash as B, you can ask
> somewhere, "is A equivalent to B?", and if so, use A in lieu of
> rebuilding to produce B).

That sums up the problem, yes.

> I think one of the biggest open questions I have is the mechanism for
> detecting if some new task hash is equivalent to an old one (known)
> one. I think there are two basic options:
> 
> 1) Do an actual build and determine equivalence afterward. This seems
> the easiest option in my mind, but it does require at least one build
> of the new hash to determine that it is functionally equivalent to an
> old hash, and then a mechanism to publish this result so that
> hopefully no one else has to do it also.

As I understand it, this is the only practical mechanism we have.

> 2) Try to calculate if the new hash is going to be equivalent without
> doing a build. This seems *much* harder, IMHO... but also eliminates
> the need for a "central" database of equivalent hashes (because
> everyone can determine it themselves).

There are probably some cases we could optimise, such as stripping out
comments from shell code but I don't think this is a problem we could
solve generally and the corner cases we could solve wouldn't be real
wins. I'd therefore propose focusing on 1) above.


> I *think* based on what I have heard, everyone is leaning toward
> option #1, which makes a lot of sense. In that regard, I think that
> this is very doable. As a simplistic first approach, I think it
> should be entirely possible to piggyback on the reproducable build
> effort that has been on-going to solve the question of "when are two
> tasks identical". Essentially, if the outputs from two tasks are
> equivalent, the two input task hashes can be considered to be
> equivalent. You could of course perhaps get more intelligent than
> that, but I don't have a clear idea of what that would look like.

Exactly, the reproducible work puts us in a position where we can now
realistically look at this. The equivalence test could be as simple as
comparing the checksums of the tarballs in sstate.


> After that, the other question I can think of right now is "how are
> results published". I'm a little less clear on what ideas people had
> there, so please chime in. I think you could go a simple as "symlinks
> in the sstate cache", and as complicated as a dedicated hierarchy of
> server with authentication and signing.

Symlinks would only buy us so much and it gets complicated very quickly
since A can depend on B which can depend on C. If A and D are
equivalent, we'd write a symlink for D to A, B using D's checksum, C
using B+D and so on. It scales as NxN which isn't good.

My suggested approach having given this some thought is this idea of an
equivalence server.

The build computes what its going to build as normal. It submits those
sstate checksums to a server. That server "canonicalizes" them if it
has entries for them to some standard parent value (the artefact that
is in sstate). The build then proceeds with the canonicalized version
of the checksum for the purposes of fetching from sstate.

The equivalence server therefore just needs to maintain mappings for
sets of sstate checksums back to a canonical value.

Whatever is populating the sstate cache would also upload equivalence
mappings. The mappings could be postprocessed into place, or done as
part of a build.

For a first pass, I'd not try and be any cleverer about it than this.

For a second level improvement, we could consider artefact comparison
at the end of each task completion, then it would short cut the build
if artefacts were found to be equivalent part way through a build.

This second level is fairly complicated and invasive as the current
bitbake runqueue has no mechanism to rework its dependency trees/build
queue on the fly. Adding such a mechanism would be hard as in theory
things currently building may suddenly not be needed and so on.

We should be able to make something really useful with just the first
pass approach though.

Does that make sense?

Cheers,

Richard