When portage installs a package onto your system, it caches information about that package in a directory at /var/db/pkg/<cat>/<pkg>/, where <cat> is the category (ie ${CATEGORY}) and <pkg> is the package name, version number and revision number (ie. ${P}). This information can then be used at a later time to tell portage information about what’s installed on a system: what packages were installed, what USE flags are set on each package, what CFLAGS were used, etc. Even the ebuild itself is cached so that if it is removed from the tree, and consequently from your system upon `emerge –sync`, you have a local copy in VDB to uninstall or otherwise continue working with the package. If you take look under /var/db/pkg, you’ll find some interesting and some not so interesting files for each <cat>/<pkg>. Among the less interesting are files like DEPEND, RDPENED, FEATURES, IUSE, USE, which just contain the same values as the ebuild variables by the same name. This is redundant because that information is in the ebuild itself which is also cached but it is more readily available since one doesn’t have to re-parse the ebuild to obtain them. More interesting is information gathered about the package as it is installed, like CONTENTS, which contains a list of all the regular files, directories, and sym link which belong to the package, along with their MD5SUM. This list is used to remove files from the system when uninstalling the package. Environment information is also cached, like CBUILD, CHOST, CFLAGS, CXXFLAGS and LDFLAGS which affects the build of compiled packages, and environment.bz2 which contains the entire shell environment that portage ran in, including all shell variables and functions from inherited eclasses. But perhaps the most interesting information, and the most expensive to recalculate is, cached in NEEDED and NEEDED.ELF.2. The later supersedes the former which is only kept for backward compatibility, so let’s just concentrate on NEEDED.ELF.2. Its a list of every ELF object that is installed for a package, along with its ARCH/ABI information, its SONAME if it is a shared object (readelf -d <obj> | grep SONAME, or scanelf -S), any RPATH used to search for its needed shared objects (readelf -d <obj> | grep RPATH, or scanelf -r), and any NEEDED shared objects (the SONAMES of libraries) that it links against (readelf -d <obj> | grep NEEDED or scanelf -n). [1] Unless you’re working with some exotic systems, like an embedded image where everything is statically linked, your user land utilities and applications depend on dynamic linking, meaning that when a process is loaded from the executable on your hard drive, the linker has to make sure that its needed libraries are also loaded and then do some relocation magic to make sure that unresolved symbols in your executable get mapped to appropriate memory locations in the libraries.
The subtleties of linking are beyond the scope of this blog posting [2], but I think its clear from the previous paragraph that one can construct a “directed linkage graph” [3] of dependencies between all the ELF objects on a system. An executable can link to a library which in turn links to another, and so on, usually back to your libc [4]. `readelf -d <obj> | grep NEEDED` only give you the immediate dependencies, but if you follow these through recursively, you’ll get all the needed libraries that an executable needs to run. `ldd <obj>` is a shell script which provides this information, as does ldd.py from the pax-utils package, which also does some pretty indentation to show the depth of the dependency. If this is sounding vaguely familiar, its because portage’s dependency rules “mimic” the underlying linking which is needed at both compile time and at run time. Let’s take an example, curl compiled with polarssl as its SSL backend:
# ldd /usr/bin/curl | grep ssl
libpolarssl.so.6 => /usr/lib64/libpolarssl.so.6 (0x000003a3d06cd000)
# ldd /usr/lib64/libpolarssl.so.6
linux-vdso.so.1 (0x0000029c1ae12000)
libz.so.1 => /lib64/libz.so.1 (0x0000029c1a929000)
libc.so.6 => /lib64/libc.so.6 (0x0000029c1a56a000)
/lib64/ld-linux-x86-64.so.2 (0x0000029c1ae13000)
Now let’s see this dependency reflected in the ebuild:
# cat net-misc/curl/curl-7.36.0.ebuild
RDEPEND="
...
ssl? (
...
curl_ssl_polarssl? ( net-libs/polarssl:= app-misc/ca-certificates )
...
)
...
Nothing surprising. However, there is one subtlety. What happens if you update polarssl to a version which is not exactly backwards compatible. Then curl which properly linked against the old version of polarssl doesn’t quite work with the new version. This can happen when the library changes its public interface by either adding new functions, removing older ones and/or changing the behavior of existing functions. Usually upstream indicates this change in the library itself by bumping the SONAME:
# readelf -d /usr/lib64/libpolarssl.so.1.3.7 | grep SONAME
0x000000000000000e (SONAME) Library soname: [libpolarssl.so.6]
But how does curl know about the change when emerging an updated version of polarssl? That’s where subslotting comes in. To communicate the reverse dependency, the DEPEND string in curl’s ebuild has := as the slot indicator for polarssl. This means that upgrading polarssl to a new subslot will trigger a recompile of curl:
# emerge =net-libs/polarssl-1.3.8 -vp
These are the packages that would be merged, in order:
Calculating dependencies... done!
[ebuild r U ] net-libs/polarssl-1.3.8:0/7 [1.3.7:0/6] USE="doc sse2 static-libs threads%* zlib -havege -programs {-test}" ABI_X86="(64) (-32) (-x32)" 1,686 kB
[ebuild rR ] net-misc/curl-7.36.0 USE="ipv6 ldap rtmp ssl static-libs threads -adns -idn -kerberos -metalink -ssh {-test}" CURL_SSL="polarssl -axtls -gnutls -nss -openssl" 0 kB
Here the onus is on the downstream maintainer to know when the API breaks backwards compatibility and subslot accordingly. Going through with this build and then checking the new SONAME we find:
# readelf -d /usr/lib/libpolarssl.so.1.3.8 | grep SONAME
0x000000000000000e (SONAME) Library soname: [libpolarssl.so.7]
Aha! Notice the SONAME jumped from .6 for polarssl-1.3.7 to .7 for 1.3.8. Also notice the SONAME version number also follows the subslotting value. I’m sure this was a conscious effort by hasufell and tommyd, the ebuild maintainers, to make life easy.
So I hope my example has shown the importance of tracing forward and reverse linkage between the ELF objects in on a system [5]. Subslotting is relatively new but the need to trace linking has always been there. There was, and still is, revdep-rebuild (from gentoolkit) which uses output from ldd to construct a “directed linkage graph” [6] but is is relatively slow. Unfortunately, it recalculates all the NEEDED.ELF.2 information on the system in order to reconstruct and invert the directed linkage graph. Subslotting has partially obsoleted revdep-rebuild because portage can now track the reverse dependencies, but it has not completely obsoleted it. revdep-rebuild falls back on the SONAMEs in the shared objects themselves — an error here is an upstream error in which the maintainers of the library overlooked updating the value of CURRENT in the build system, usually in a line of some Makefile.am that looks like
LDFLAGS += -version-info $(CURRENT):$(REVISION):$(AGE)
But an error in subslotting is an downstream error where the maintainers didn’t properly subslot their package and any dependencies to reflect upstream’s changing API. So in some ways, these tools complement each other.
Now we come to the real point of the blog: there is no reason for revdep-rebuild to run ldd on every ELF object on the system when it can obtain that information from VDB. This doesn’t save time on inverting the directed graph, but it does save time on running ldd (effectively /lib64/ld-linux-x86-64.so.2 –list) on every ELF object in the system. So guess what the python version does, revdep-rebuild.py? You guessed it, it uses VDB information which is exported by portage via something like
import portage
vardb = portage.db[portage.root]["vartree"].dbapi
So what’s the difference in time? On my system right now, we’re looking at a difference between approximately 5 minutes for revdep-rebuild versus about 20 seconds for revdep-rebuild.py. [7] Since this information is gathered at build time, there is no reason for any Package Management System (PMS) to not export it via some standarized API. portage does so in an awkward fashion but it does export it. paludis does not export NEEDED.ELF.2 although it does export other VDB stuff. I can’t speak to future PMS’s but I don’t see why they should not be held to a standard.
Above I argued that exporting VDB is useful for utilities that maintain consistency between executibles and the shared objects that they consume. I suspect one could counter-argue that it doesn’t need to be exported because “revdep-rebuild” can be made part of portage or whatever your PMS, but I hope my next point will show that exporting NEEDED.ELF.2 information has other uses besides “consistant linking”. So a stronger point is that, not only should PMS export this information, but that it should provide some well documented API for use by other tools. It would be nice for every PMS to have the same API, preferably via python bindings, but as long as it is well documented, it will be useful. (Eg. webapp-config supports both portage and paludis. WebappConfig/wrapper.py has a simple little switch between “import portage; ... portage.settings['CONFIG_PROTECT'] ... ” and “cave print-id-environment-variable -b --format '%%v\n' --variable-name CONFIG_PROTECT %s/%s ...“.)
So besides consistent linking, what else could make use of NEEDED.ELF.2? In the world of Hardened Gentoo, to increase security, a PaX-patched kernel holds processes to much higher standards with respect to their use of memory. [8] Unfortunately, this breaks some packages which want to implement insecure methods, like RWX mmap-ings. Code is compiled “on-the-fly” by JIT compilers which typically create such mappings as an area to which they first write and then execute. However, this is dangerous because it can open up pathways by which arbitrary code can be injected into a running process. So, PaX does not allow RWX mmap-ings — it doesn’t allow it unless that kernel is told otherwise. This is where the PaX flags come in. In the JIT example, marking the executables with `paxctl-ng -m` will turn off PaX’s MPROTECT and allow the RWX mmap-ing. The issue of consistent PaX markings between executable and their libraries arises when it is the library that needs the markings. But when loaded, it is the markings of the executable, not the library, which set the PaX restrictions on the running process. [9] So if its the library needs the markings, you have to migrate the markings from the library to the executable. Aha! Here we go again: we need to answer the question “what are all the consumers of a particular library so we can migrate its flags to them?” We can, as revdep-rebuild does, re-read all the ELF objects on the system, reconstruct the directed linkage graph, then invert it; or we can just start from the already gathered VDB information and save some time. Like revdep-rebuild and revdep-rebuild.py, I wrote two utilities. The original, revdep-pax, did forward and reverse migration of PaX flags by gathering information with ldd. It was horribly slow, 5 to 10 minutes depending on the number of objects in $PATH and shared object reported by `ldconfig -p`. I then rewrote it to use VDB information and it accomplished the same task in a fraction of the time [10]. Since constructing and inverting the directed linkage graph is such a useful operation, I figured I’d abstract the bare essential code into a python class which you can get at [11]. The data structure containing the entire graph is a compound python dictionary of the form
{
abi1 : { path_to_elf1 : [ soname1, soname2, ... ], ... },
abi2 : { path_to_elf2 : [ soname3, soname4, ... ], ... },
...
}
whereas the inverted graph has form
{
abi1 : { soname1 : [ path_to_elf1, path_to_elf2, ... ], ... },
abi2 : { soname2 : [ path_to_elf3, path_to_elf4, ... ], ... },
...
}
Simple!
Okay, up to now I concentrated on exporting NEEDED.ELF.2 information. So what about rest of the VDB information? Is it useful? A lot of questions regarding Gentoo packages can be answered by “grepping the tree.” If you use portage as your PMS, then the same sort of grep-sed-awk foo magic can be performed on /var/db/pkg to answer similar questions. However, this assumes that the PMS’s cached information is in plain ASCII format. If a PMS decides to use something like Berkeley DB or sqlite, then we’re going to need a tool to read the db format which the PMS itself should provide. Because I do a lot of release engineering of uclibc and musl stages, one need that often comes up is the need to compare of what’s installed in the stage3 tarballs for the various arches and alternative libc’s. So, I run some variation of the following script
#!/usr/bin/env python
import portage, re
portdb = portage.db[portage.root]["vartree"].dbapi
arm_stable = open('arm-stable.txt', 'w')
arm_testing = open('arm-testing.txt', 'w')
for pkg in portdb.cpv_all():
keywords = portdb.aux_get(pkg, ["KEYWORDS"])[0]
arches = re.split('\s+', keywords)
for a in arches:
if re.match('^arm$', a):
arm_stable.write("%s\n" % pkg)
if re.match('^~arm$', a):
arm_testing.write("%s\n" % pkg)
arm_stable.close()
arm_testing.close()
in a stage3-amd64-uclibc-hardened chroot to see what stable packages in the amd64 tarball are ~arm. [12] I run similar scripts in other chroots to do pairwise comparisons. This gives me some clue as to what may be falling behind in which arches — to keep some consistency between my various stage3 tarballs. Of course there are other utilities to do the same, like eix, gentoolkit etc, but then one still has to resort to parsing the output of those utilities to get the answers you want. An API for VDB information allows you to write your own custom utility to answer the precise questions you need answers. I’m sure you can multiply these examples.
Let me close with a confession. The above is propaganda for the upcoming GLEP 64 which I just wrote [13]. The purpose of the GLEP is to delineate what information should be exported by all PMS’s with particular emphasis on NEEDED.ELF.2 for the reasons stated above. Currently portage does provide NEEDED.ELF.2 but paludis does not. I’m not sure what future PMS’s might or might not provide, so let’s set a standard now for an important feature.
Notes:
[1] You can see where NEEDED.ELF.2 is generated for details. Take a look at line ~520 of /usr/lib/portage/bin/misc-functions.sh, or search for the comment “Create NEEDED.ELF.2 regardless of RESTRICT=binchecks”.
[2] A simple hands on tutorial can be found at http://www.yolinux.com/TUTORIALS/LibraryArchives-StaticAndDynamic.html. It also includes dynamic linking via dlopen() which complicates the nice neat graph that can be constructed from NEEDED.ELF.2.
[3] I’m using the term “directed graph” as defined in graph theory. See http://en.wikipedia.org/wiki/Directed_graph. The nodes of the graph are each ELF object and the directed edges are from the consumer of the shared object to the shared object.
[4] Well, not quite. If you run readelf -d on readelf -d /lib/libc.so.6 you’ll see that it links back to /lib/ld-linux-x86-64.so.2 which doesn’t NEED anything else. The former is stricly your standard C library (man 7 libc) while the later is the dynamic linker/loader (man 8 ld.so).
[5] I should mention parenthatically that there are other executable/library file formats such as Mach-O used on MacOS X. The above arguments translate over to any executable formats which permit shared libraries and dynamic linking. My prejudice for ELF is because it is the primary executable format used on Linux and BSD systems.
[6] I’m coining this term here. If you read the revdep-rebuild code, you won’t see reference to any graph there. Bash doesn’t readily lend itself to the neat data structures that python does.
[7] Just a word of caution, revdep-rebuild.py is still in development and does warn when you run it “This is a development version, so it may not work correctly. The original revdep-rebuild script is installed as revdep-rebuild.sh”.
[8] See https://wiki.gentoo.org/wiki/Hardened/PaX_Quickstart for an explanation of what PaX does as well as how it works.
[9] grep the contents of fs/binfmt_elf.c for PT_PAX_FLAGS and CONFIG_PAX_XATTR_PAX_FLAGS to see how these markings are used when the process is loaded from the ELF object. You can see the PaX protection on a running process by using `cat /proc/<pid>/maps | grep ^PaX` or `pspax` form the pax-utils package.
[10] The latest version off the git repo is at http://git.overlays.gentoo.org/gitweb/?p=proj/elfix.git;a=blob;f=scripts/revdep-pax.
[11] http://git.overlays.gentoo.org/gitweb/?p=proj/elfix.git;a=blob;f=pocs/link-graph/link_graph.py.
[12] These stages are distributed at http://distfiles.gentoo.org/releases/amd64/autobuilds/current-stage3-amd64-uclibc-hardened/ and http://distfiles.gentoo.org/experimental/arm/uclibc/.
[13] https://bugs.gentoo.org/show_bug.cgi?id=518630