Linker limitations on 32-bit architectures

Before a program can be run, it needs to be built. It's a well-known fact that modern software, in general, consumes more runtime resources than before, sometimes to the point of forcing users to upgrade their computers. But it also consumes more resources at build time, forcing operators of the distributions' build farms to invest in new hardware, with faster CPUs and more memory. For 32-bit architectures, however, there exists a fundamental limit on the amount of virtual memory, which is never going to disappear. That is leading to some problems for distributions trying to build packages for those architectures.

Indeed, with only 32-bit addresses, there is no way for a process to refer to more than 4GB of memory. For some architectures, the limit is even less — for example, MIPS hardware without the Enhanced Virtual Addressing (EVA) extensions is hardwired to make the upper 2GB of the virtual address space accessible from the kernel or supervisor mode only. When linking large programs or libraries from object files, ld sometimes needs more than 2GB and therefore fails.

Building on 32-bit machines

This class of problems was recently brought up by Aurelien Jarno in a cross-post to multiple Debian mailing lists. Of course, he is not the first person to hit this; a good example would be in a Gentoo forum post about webkit-gtk from 2012. Let's follow through this example, even though there are other packages (Jarno mentions Firefox, Glasgow Haskell Compiler, Rust, and scientific software) where a 32-bit build has been reported to run out of virtual address space.

If one attempts to build webkit-gtk now, first the C++ source files are grouped and concatenated, producing so-called "unified sources". This is done in order to reduce compilation time. See this blog post by WebKit developer Michael Catanzaro for more details. Interestingly, a similar approach had been suggested for WebKit earlier, but it targeted reducing memory requirements at the linking stage.

Unified sources are compiled into the object code files by g++, which knows how to invoke the actual compiler (cc1plus) and assembler (as). At this stage, the most memory-hungry program is cc1plus, which usually consumes ~500-800MB of RAM, but there are some especially complex files that cause it to take more than 1.5GB. Therefore, on a system with 32-bit physical addresses, building webkit-gtk with parallelism greater than -j2 or maybe -j3 might well fail. In other words, due to insufficient memory, on "real" 32-bit systems one may not be able to take the full advantage of multi-processing. Thankfully, both on 32-bit x86 and MIPS, CPU architecture extensions exist that allow the system as a whole (but not an individual process) to use more than 4GB of physical RAM.

It is a policy of Debian, Fedora, and lots of other distributions (but, notably, not Gentoo) to generate debugging information while compiling C/C++ sources. This debugging information is useful when interpreting crash dumps — it allows seeing which line of the source code a failing instruction corresponds to, observing how exactly local and global variables are located in memory, and determining how to interpret various data structures that the program creates. If the -g compiler option is used to produce debugging information, the resulting object files have sizes between several KB and 10MB. For example, WebDriverService.cpp.o takes 2.1MB of disk space. Of that, only 208KB are left if debugging symbols are discarded. That's right — 90% of the size of this particular file is taken by debugging information.

When compilation has created all of the object files that go into an executable or library, ld is invoked to link them together. It combines code, data, and debug information from object files into a single ELF file and resolves cross-references. During the final link of libwebkit2gtk-4.0.so.37, 3GB of object files are passed to ld at once. This doesn't fail on x86 with Physical Address Extension (PAE), but comes quite close. According to the report produced with -Wl,--stats in LDFLAGS:

    ld.gold: total space allocated by malloc: 626630656 bytes
    total bytes mapped for read: 3050048838
    output file size: 1727812432 bytes

Adding the first two lines gives 3.6GB allocated by ld.gold. There are some legitimate questions here regarding resource usage. First, what is all this memory (or address space) used for? Second, can ld use less memory?

Well, there are two implementations of ld in the binutils package: ld.bfd (old, but still the default) and ld.gold (newer). By default, both implementations use mmap() to read object files as inputs. That is, ld associates a region of its virtual address space with every object file passed to it so that memory operations on these regions are redirected by the kernel, through page faults, to the files. This programming model is convenient and, in theory, reduces the physical memory requirements. That is because the kernel can, at its discretion, repurpose physical memory that keeps the cached content of object files for something else and then transparently reread bytes from the file again when ld needs them. Also, ld.gold, by default, uses mmap() to write to the output file. The downside is that there must be sufficient address space to assign to the input and output files or the mmap() operation will fail.

Both ld.bfd and ld.gold offer options that are intended to conserve memory, but actually help only sometimes:

    $ ld.bfd --help
      --no-keep-memory            Use less memory and more disk I/O
      --reduce-memory-overheads   Reduce memory overheads, possibly taking much longer
      --hash-size=<NUMBER>        Set default hash table size close to <NUMBER>
    $ ld.gold --help
      --no-keep-files-mapped      Release mapped files after each pass
      --no-map-whole-files        Map only relevant file parts to memory (default)
      --no-mmap-output-file       Do not map the output file for writing

When a distribution maintainer sees a build failure on a 32-bit architecture, and one of the options listed above helps, a patch gets quickly submitted upstream so that the option is used by default in the affected application or library. For webkit-gtk, that is indeed the case. In other words, all the low-hanging fruit is already collected.

A package without full debugging information is still better than no package at all. So, reluctantly, maintainers are forced to compress debugging information, reduce its level of detail, or, in extreme cases, completely remove it. Still, in Debian, some packages are excluded from some architectures because they cannot be built due to running out of virtual memory. "We are at a point were we should probably look for a real solution instead of relying on tricks", Jarno concluded.

Cross-compiling

A reader with some background in embedded systems might ask: why does Debian attempt to build packages on weak and limited 32-bit systems at all? Wouldn't it be better to cross-compile them on a much larger amd64 machine? Indeed, that's what the Yocto Project and Buildroot do, and they have no problem producing a webkit-gtk package with full debugging information for any architecture. However, cross-compilation (in the sense used by these projects) invariably means the inability to run compiled code. So packages that test properties of the target system by building and running small test programs are no longer able to do so; they are forced to rely on external hints, hard-coded information, or (often pessimistic) assumptions. Moreover, the maintainer is no longer able to run the test suite as a part of the package build. Such limitations are unacceptable for the Debian release team, and therefore native builds are required. And running tests under QEMU-based emulation is out of question, too, because of possible flaws in the emulator itself.

Jarno proposed to use Debian's existing support for "multiarch", which is the ability to co-install packages for different architectures. For example, on a system with an amd64 kernel, both i386 and amd64 packages can be installed and both types of programs will run. The same applies to 32-bit and 64-bit MIPS variants. It would be, therefore, enough to produce cross-compilers that are 64-bit executables but target the corresponding 32-bit architecture. For gcc it is as easy as creating a wrapper that adds the -m32 switch. However, gcc is not the only compiler — there are also compilers for Haskell, Rust, OCaml, and other languages not supported by gcc; they may need to be provided as well.

If one were to implement this plan, a question arises how to make those compilers available. That is, should a package that demands extraordinary amounts of memory at build time explicitly depend on the cross-compiler or should it be provided implicitly? Also, there is an obstacle on the RISC-V architectures: a 64-bit CPU does not implement the 32-bit instructions, so one cannot assume that just-compiled 32-bit programs will run. The same is sometimes true for Arm: there is arm64 hardware that does not implement 32-bit instructions. However, this obstacle is not really relevant, because Debian does not support 32-bit RISC-V systems anyway, and arm64 hardware that supports 32-bit instructions is readily available, is not going away, and thus can be used on the build systems. So, for the cases where this approach can work, Ivo De Decker (a member of the Debian release team) expressed readiness to reevaluate the policy.

On the other hand, Sam Hartman, the current Debian Project Leader, admitted that he is not convinced that it is a good idea to run the build tools (including compilers and linkers) on 32-bit systems natively. Of course, this viewpoint is at odds with the release team position, and the problem of getting accurate build-time test results still needs to be solved. One solution mentioned was a distcc setup, but this turned out to be a false lead, because with distcc, linking is done locally.

There was also a subthread started by Luke Kenneth Casson Leighton, where he brought up ecological concerns — namely, that perfectly good hardware is forced to go to landfills because of the resource-wasteful algorithms now employed in the toolchain. In Leighton's viewpoint, the toolchain must be fixed in order to be able to deal with files bigger than the available virtual memory, especially because it was able to deal with such files decades ago.

Right now, 32-bit systems are still useful and can run general-purpose operating systems. Only a few big packages are directly affected by the limitation of available address space at build time. But ultimately, we have to agree with Hartman's conclusion: "if no one does the work, then we will lose the 32-bit architectures" — at least for Debian.