Guix includes a mechanism called grafts that allows us to provide
users with security
updates
in a timely fashion, even for core packages deep down in the dependency
graph. Most users value the benefits of grafts, but newcomers were also
unavoidably struck by what turned out to be the undesirable side effect
of our graft implementation on user experience. This had been a
well-known problem for a while, but 1.1.0 finally addressed these
issues.
This article recaps how grafts are implemented, what problems that
caused, and how we solved it. It’s a deep dive into core Guix, and I
hope it’ll be insightful to all and intriguing to the functional
programming geeks among us!
What’s this “graft” thing anyway?
Grafts were introduced in the early days of Guix to address probably
the main practical shortcomings of functional software
deployment.
In a nutshell, functional deployment as implemented by Nix and Guix
means that, when a package changes, everything that depends on it must
be rebuilt (or re-downloaded). To deploy a security fix in the C
library or in Bash, you would thus need to rebuild everything. Even
with a huge build farm, that can significantly delay the deployment of
fixes; users would find themselves either rebuilding things locally or,
at best, re-downloading binaries of everything.
To address this, Guix developers can instead specify a replacement in
a package
definition.
If we have a bug-fix for, say, libc, developers would (1) define a
package for the fixed libc, and (2) add a replacement field in the
original libc package pointing to that fixed package. The effect is
that only the bug-fix libc needs to be built. When building a
package, the bug-fix libc is automatically grafted onto that package,
such that the resulting package refers to the bug-fix libc. See the
manual
for more.
When “lowering” a high-level package
definition
to a low-level
derivation,
Guix traverses the package dependency graph and identifies a set of
potentially applicable grafts. Why “potentially applicable”? Consider
this scenario: assume perl has a replacement; coreutils has a
dependency on perl, but it’s a build-time dependency: coreutils does
not depend on perl at run time. Thus, coreutils can be used as is,
there is no need to graft it.
But how do we know whether a dependency is a built-time-only dependency?
The native-inputs
field
of a package usually lists build-time dependencies, but it’s more of a
hint. Ultimately, the set of run-time dependencies, which we call the
references, is the subset of the build-time dependencies that the
garbage collector (GC) in the build daemon finds in the build
result—Section 5.5.1 of Eelco Dolstra’s PhD
thesis describes how the
GC
scans for references. In our example, we first have to actually build
coreutils before we can tell whether it depends on perl at
run time.
Guix arranges to graft only when necessary. In this example, guix build coreutils would return the same as guix build coreutils --no-grafts. Conversely, since inkscape has a run-time dependency on
perl, guix build inkscape returns a derivation that grafts the
perl replacement onto the original inkscape build result, the one
returned by guix build inkscape --no-grafts. The (simplified)
dependency graph of the derivation for the grafted inkscape looks like
this:
Grafts are a form of what Build Systems à la
Carte
by Mokhov et al. (a good read!) refers to as dynamic dependencies:
grafting depends on intermediate build results.
Still here? With the background in place, let’s look at the problems
that arose.
Grafts, the user interface, and performance
Conceptually, to decide whether to graft a package, we examine the
references of the build result of the ungrafted package. However, we
usually want guix install & co. to first display an overall build
plan, especially when invoked with --dry-run:
$ guix install inkscape
The following package will be installed:
inkscape 1.0
71.3 MB will be downloaded:
/gnu/store/xq64iaxx2gmlcgnipj31wjxlf1yd2g2p-gsl-2.6
/gnu/store/zrmhnj3pwchn2msphgnwzwd3q89m46rn-aspell-0.60.8
/gnu/store/5g31zf21lk8nrfd2b8qrm19nwdm9gir9-potrace-1.16
/gnu/store/qpr7387bsjs7rpl6flrwdvn2zbzh5bch-ghostscript-with-cups-9.52
/gnu/store/7y3lvk3xf4im8n44337mc6y0ccysvfia-font-dejavu-2.37
/gnu/store/95n3zvzxzq2bxvdvz292cg04757ij30x-cups-minimal-2.3.1
…
To accommodate that, the pre-1.1.0 implementation of grafts did the
following: when
substitutes
were enabled, it would get the list of references of ungrafted packages
from substitutes; only when substitutes for an ungrafted package are
missing would it first try to build that package. Thus, when
substitutes are available, guix install and similar commands would be
able to display the build plan upfront. However, when a packages had no
substitutes, you’d see Guix start building it without saying a word
about the build plan, which was arguably
confusing.
But it’s worse than that. Grafting is per-package, so every time you
would lower a package to a derivation, you would need to answer the
question “does this specific package have substitutes, and if so,
should it be grafted?” The end result was poor resource usage and
terrible user interface
feedback. For every package
that is a graft candidate, the user would see that infamous line:
updating substitutes from 'https://ci.guix.gnu.org'...
The problem was particularly acute when building whole systems with
guix system because there would typically be a large number of such
packages. Furthermore, each of these lines would correspond to
(roughly) a single HTTP GET request on a fresh TLS connection. That can
be slow… and annoying. Perhaps to some users this updating substitutes stuttering was the proof of the developers’ incompetence
and perhaps, truth be told, to some of us developers it was a small
price to pay for the sophistication of grafts.
For users who disable substitutes and build everything locally, the
situation wasn’t much better: all the packages candidate for grafting
would be built one by one, thereby missing parallelization opportunities
as specified by
--max-jobs.
Gathering dynamic dependencies
To address this, all these individual dynamic dependencies need to be
gathered somehow instead of being treated one by one. Conceptually, we
would like to, roughly, do a first pass lowering packages to derivations
as if grafting was disabled, build all these derivations, and then do a
second pass to determine which packages in the graph need to be grafted and
to compute the relevant grafting derivation. That would address the
performance issue: we’d now have as much parallelism as possible, so we
wouldn’t query substitutes or build packages one by one. If we reify
that second pass to the user interface code, it also addresses the user
interface issue by allowing it to display, possibly, two build plans:
the “ungrafted” one followed by the grafted one.
The problem is that our API is inherently serial: the
package-derivation function takes one package, lowers it, and
returns its derivation:
(use-modules (guix)
(gnu packages base)
(gnu packages inkscape))
(define s (open-connection))
(package-derivation s coreutils)
⇒ #<derivation /gnu/store/rpfdbax1py483m9ydhvp73s7dgmn6xh4-coreutils-8.31.drv => /gnu/store/jkj7wxybgcpdamkl6fz7wwbb1ak5wxvk-coreutils-8.31-debug /gnu/store/zibwkb5xavnv6z3gzknfqjsxb9b0izh0-coreutils-8.31 7f6c92e3a000>
(package-derivation s coreutils #:graft? #f)
⇒ #<derivation /gnu/store/rpfdbax1py483m9ydhvp73s7dgmn6xh4-coreutils-8.31.drv => /gnu/store/jkj7wxybgcpdamkl6fz7wwbb1ak5wxvk-coreutils-8.31-debug /gnu/store/zibwkb5xavnv6z3gzknfqjsxb9b0izh0-coreutils-8.31 7f6c92e3a000>
(package-derivation s inkscape)
⇒ #<derivation /gnu/store/jzm2zsq8m0rj8wdsmikc0p2ik0cprrcf-inkscape-0.92.4.drv => /gnu/store/clj8rjnsip8a35hyd9nf4l65w7ahn0gs-inkscape-0.92.4 7f6c9c15b730>
(package-derivation s inkscape #:graft? #f)
⇒ #<derivation /gnu/store/psd31x1fq0v2g594z217mh56xzg21dym-inkscape-0.92.4.drv => /gnu/store/zz28ckjwfxwkx3gsm8sc452kmvfiky6y-inkscape-0.92.4 7f6c90ad4f50>
Lowering includes dealing with grafts, and
that’s why we ended up with one-by-one inefficiencies. An option would
be to make all the API “plural”: have package-derivation and its
friends accept a list of packages instead of a single one. That would
be a huge amount of work and the end result would be unpleasant to use:
it’s easier to reason one-by-one.
The solution implemented in 1.1.0 instead starts from this observation:
the call graph of package-derivation mirrors the package graph. Thus,
we could gather dynamic dependencies using monad
trickery
or using “control effects”. We went for the latter, which didn’t have
the “contamination” problem of monads and led to simpler code.
The starting point is that, by definition, code with dynamic
dependencies necessarily calls
build-derivations.
Taking advantage of delimited continuations in
Guile,
build-derivations is instrumented to abort to a “build handler”
prompt
when it’s called. The build handler receives the list of derivations to
build along with a continuation to invoke to resume the aborted
computation and start building things. User interface code can install
a build handler that displays what’s going to be built:
(with-build-handler (lambda (continue store things mode)
(show-what-to-build store things)
(continue #t))
…)
To implement dry runs, simply omit the call to continue and nothing
will be built. (This is a slightly simplified artist view, see
build-notifier
for the real thing.)
Now, we need to take advantage of this mechanism to gather the
individual build-derivations calls so we can later emit a single
build-derivations call for all the gathered derivations. The goal is
to effectively gather all the calls for ungrafted packages, build them
all at once, and then resume graft computation.
To achieve that, we write a build handler that, when invoked, returns an
<unresolved> object that captures what to build and the continuation.
In addition, we provide a primitive to introduce parallelism such
that, if a dynamic dependency is encountered, we keep going and attempt
to compute as much as possible without resolving that dynamic
dependency. These are build-accumulator and
map/accumulate-builds.
map/accumulate-builds is like map, except that it accumulates and
gathers build-derivations request.
By using map/accumulate-builds instead of map in a few
key
places,
we obtain a good approximation of what we wanted, as illustrated in this
run:
$ guix install zile-on-guile vim-full
The following packages will be installed:
zile-on-guile 2.4.14-0.fd09781
vim-full 8.2.0411
9.4 MB will be downloaded:
/gnu/store/vf7w4yiax38ra7x8aqqvbnc38c0ldgpm-zile-on-guile-2.4.14-0.fd09781
/gnu/store/dnj9wljcck9vdwgp7dwxk00qnnk1g3c5-vim-full-8.2.0411
downloading from https://ci.guix.gnu.org/nar/lzip/dnj9wljcck9vdwgp7dwxk00qnnk1g3c5-vim-full-8.2.0411...
vim-full-8.2.0411 8.9MiB 7.6MiB/s 00:01 [##################] 100.0%
downloading from https://ci.guix.gnu.org/nar/lzip/vf7w4yiax38ra7x8aqqvbnc38c0ldgpm-zile-on-guile-2.4.14-0.fd09781...
zile-on-guile-2.4.14-0.fd09781 140KiB 1.8MiB/s 00:00 [##################] 100.0%
The following derivation will be built:
/gnu/store/d9xms78917w67xq71pqsx5x9s6dmq6d7-profile.drv
The following graft will be made:
/gnu/store/4n6dmg6iwjg0adpcvqygr9wgsnclswss-vim-full-8.2.0411.drv
applying 8 grafts for /gnu/store/4n6dmg6iwjg0adpcvqygr9wgsnclswss-vim-full-8.2.0411.drv...
building /gnu/store/d9xms78917w67xq71pqsx5x9s6dmq6d7-profile.drv...
What we see above is first a build plan that downloads binaries for the
two ungrafted packages, followed by a build plan for one grafting
derivations: we have successfully preserved parallelism.
The solution resembles the suspending scheduler discussed in the à
la Carte paper, though decomposition is not as principled as what the
paper describes. It remains an approximation and not the
optimal way to deal with dynamic dependencies. There are still
situations where that shows,
but overall, it’s a significant improvement. Unlike other solutions
prototyped before, this one
has the advantage of being orthogonal and simple: less than 100 new
lines of
code,
and even about 30 lines
removed
from the graft implementation. That alone contributes a lot to the
author’s satisfaction. :-)
Interlude: a scatter/gather pattern?
In the end, we’re just gathering all the build-derivations calls,
turning them into a single call, and finally calling all the original
site continuations with the result. The same kind of issue shows up
when dealing with sequences of remote procedure calls (RPCs) and HTTP
requests, and it seems there’s a more general pattern lurking here.
Consider code like this:
(map (lambda (thing)
(http-get (thing->url thing)))
lst)
Wouldn’t it be nice if we could somehow capture all the http-get
calls, turn them into a series of pipelined GET
requests, and resume the
continuations with their result?
I haven’t found a standard functional pattern to address this and would
welcome ideas!
Dynamic dependencies of all shapes
We have seen how Guix deals with dynamic dependencies. Nix supports a
similar but limited form of dynamic dependencies through
the import primitive of the
Nix language, which can take the result of a derivation
build;
it does not attempt to gather the resulting buildPaths calls.
If we take a step back, we can see that Nix and Guix actually support
other forms of dynamic dependencies. For example, it’s possible to
write derivations whose result is a function of the reference graph of
another derivation’s build result. This is achieved in Guix by passing
the #:references-graphs argument of
gexp->derivation,
which leads the build daemon to include the reference graph in the
build
environment.
Another form of dynamic dependency is derivation-building derivations
or recursive derivations, which were recently implemented in
Nix. It supports another form
of dynamic dependency where the build process of a derivation can itself
create and build derivations (these are moldable
tasks
in scheduling parlance). It’s a great feature because in a nutshell, it
allows Nix to be used not only to compose packages, but also at a finer
grain as part of a package build process.
Guix supports yet another form of dynamic dependencies. The newfangled
guix deploy
tool
works by evaluating g-expressions (gexps)
remotely.
For example, before actually deploying an operating system, it first
runs code on the remote node to perform sanity checks: checking whether
the declared file system UUIDs or labels are valid, checking whether
additional kernel modules should be added to the initial RAM disk, and
so forth. To do that,
remote-eval
first builds a derivation that produces a Scheme program, deploys it
along with all its dependencies on that target machine, runs it, and
retrieves the result. This form of dynamic dependency also benefits
from the gathering machinery discussed above.
Conclusion
This is a long article on what may look like a fine point of Guix design
and implementation, but there’s much to say about it! Grafts are key to
the use of functional deployment in production because they enable quick
security updates, and it’s a lot better if they don’t harm the user
experience.
The pre-1.1.0 implementation of grafts had a negative impact on the user
interface and on performance, which was due to the sequential handling
of grafts, one package at a time. In 1.1.0 we addressed it by using
delimited continuations to gather dynamic dependencies such as grafts,
perform builds in bulk, and resume each derivation computation.
As it turned out, the implementation of dynamic dependencies raises lots
of interesting design and implementation issues, and it’s probably not
the end of the road!
About GNU Guix
GNU Guix is a transactional package
manager and an advanced distribution of the GNU system that respects
user
freedom.
Guix can be used on top of any system running the kernel Linux, or it
can be used as a standalone operating system distribution for i686,
x86_64, ARMv7, and AArch64 machines.
In addition to standard package management features, Guix supports
transactional upgrades and roll-backs, unprivileged package management,
per-user profiles, and garbage collection. When used as a standalone
GNU/Linux distribution, Guix offers a declarative, stateless approach to
operating system configuration management. Guix is highly customizable
and hackable through Guile
programming interfaces and extensions to the
Scheme language.
