llvm-project 14 will be released soon. I added some lld/ELF notes to https://github.com/llvm/llvm-project/blob/release/14.x/lld/docs/ReleaseNotes.rst. Here I will elaborate on some changes.
All about COMMON symbols
Programming language behavior
FORTRAN 77 COMMON blocks compiled to COMMON symbols. You could declare a COMMON block in more than one file, with each specifying the number, type, and size of the variable. The linker allocated enough space to satisfy the largest size.
Compressed debug sections
Updated in 2024-03.
Binary sizes are important. Filesystem compression is ergonomic but typically does not leverage application information well. Compressing allocable sections (text, data) increases program startup time and introduces memory overhead. In addition, filesystem compression is not sufficiently portable.
Debug sections are large and contribute to a significant portion of the binary size. Therefore, it is appealing to compress debug sections.
Here is a -DCMAKE_BUILD_TYPE=Debug
build directory of
llvm-project where I just ran ninja clang
(on 2022-10-21).
Here are the total sizes of .o files, text sections, and debug sections.
It is typical that the debug information is often much larger than text
sections.
1 | % stat -c %s **/*.o | awk '{s+=$1} END{print s}' |
Some assemblers and linkers offer a feature to compress debug sections.
llvm-objcopy supports --compress-debug-sections=zlib
to
compress debug sections. We can use the option to check what if we
compress debug sections for the assembler. 1
2% for i in **/*.o; do /tmp/Rel/bin/llvm-objcopy --compress-debug-sections=zlib $i /tmp/c/o && readelf -WS /tmp/c/o | awk 'BEGIN{FPAT="\\[.*?\\]|\\S+"} $2~/\.debug_/{d += strtonum("0x"$6)} END{print d}'; done | awk '{s+=$1} END{print s}'
161691798
For debug sections, we have a compression ratio of 3.90! The total .o size is 995438992 bytes, 68% of the original.
Then let's check zstd. 1
2% for i in **/*.o; do /tmp/Rel/bin/llvm-objcopy --compress-debug-sections=zstd $i /tmp/c/o && readelf -WS /tmp/c/o | awk 'BEGIN{FPAT="\\[.*?\\]|\\S+"} $2~/\.debug_/{d += strtonum("0x"$6)} END{print d}'; done | awk '{s+=$1} END{print s}'
159341878
To check whether an object file has compressed debug sections, we can
use readelf
.
1 | % readelf -S a.o |
In the readelf -S
output, the Flg
column
describes sh_flags
where C
indicates the
SHF_COMPRESSED
flag.
1 | % readelf -t a.o |
History
In 2007-11, Craig Silverstein added
--compress-debug-sections=zlib
to gold. When the option
was specified, gold compressed the content of a .debug*
section with zlib and changed the section name to
.debug*.zlib.$uncompressed_size
.
Archives and --start-lib
.a archives
Unix-like systems represent static libraries as .a
archives. A .a
archive consists of a header and a
collection of files with metadata. Its usage is tightly coupled with the
linker. An archive almost always contains only relocatable object files
and the linker has built-in support for reading it.
1 | % as /dev/null -o a.o |
One may add other types of files to .a
but that is
almost assuredly a bad thing.
1 | % rm -f a.a && ar rc a.a a.o b.a # archive in archive, bad |
The original linker designers noticed that for many programs not every member was needed, so they tried to allow the linker to skip unused members. Therefore, they invented the interesting but confusing archive member extraction rule. See Symbol processing#Archive processing for details.
Why isn't ld.lld faster?
Updated in 2022-11.
LLD is the LLVM linker. Its ELF port is typically installed as
ld.lld
. This article makes an in-depth analysis of ld.lld's
performance. The topic has been in my mind for a while. Recently Rui
Ueyama released mold 1.0
and people wonder why with multi-threading its ELF port is faster than
ld.lld. So I finally completed the article.
First of all, I am very glad that Rui Ueyama started mold. Our world has a plethora of compilers, but not many people learn or write linkers. As its design documentation says, there are many drastically different designs which haven't been explored. In my view, mold is innovative in that it introduced parallel symbol table initialization, symbol resolution, and relocation scan which to my knowledge hadn't been implemented before, and showed us amazing results. The innovation gives existing and future linkers incentive to optimize further.
.init, .ctors, and .init_array
Updated in 2023-03.
In C++, dynamic initializations for non-local variables happen before
the first statement of the main
function. All (most?)
implementations just ensure such dynamic initializations happen before
main
.
As an extension, GCC supports
__attribute__((constructor))
which can make an arbitrary
function run before main
. A constructor function can have
an optional priority (__attribute__((constructor(N)))
).
Relative relocations and RELR
Updated in 2024-02.
(In celebration of my 2800th llvm-project commit) Happy Halloween!
This article describes relative relocations and how the RELR format can greatly decrease file sizes.
An ELF linker performs the following steps to process an absolute
relocation type whose width equals the word size (e.g.
R_AARCH64_ABS64
, R_X86_64_64
).
1 | if (undefined_weak || (!preemptible && (no_pie || is_shn_abs))) |
Note: in FDPIC
ABIs, there is no single base address. Relative relocations can
still be used, but the runtime operation is not simply
*loc += base
.
When can glibc be built with Clang?
In September, I wrote "So, dear glibc, will you be happy with my sending Clang patches?" in Build glibc with LLD 13. We have come to a turning point.
In Linux Plumbers Conference 2021, at the glibc Birds of a Feather session, I asked the Clang buildability question to the glibc stewards. (Interlude: I did not realize that I should attend the conference (it was a great opportunity from an outlier to meet some glibc folks). In Tuesday, Wei Wu (lazyparser) kindly gave me his account: "想去参加LPC么?我会议太多了今天参加不过来". I happily accepted it and typed the question during the glibc session.)
So I got positive responses. "Carlos: Yes, we could be happy with clang buildability." "Joseph: Patches should be split into logical changes." This is really great news! My unnesting patch had sat there for a while and I was unsure about the Clang buildability interest.
Competitive programming in Nim
Updated in 2022-10.
In the afternoon, I came cross the Nim programming language again on Lobsters. I first learned some basics of the language in 2015, but had not touched it since then.
"Nim is a statically typed compiled systems programming language. It combines successful concepts from mature languages like Python, Ada and Modula.", according to its website.
Basic features: parametric polymorphism. Advanced features: macros (including term-rewriting macros), compile-time function execution, effect system, concepts
An idea popped into my mind: why not solve some coding challenges in Nim?
As a niche language, it is not supported on many coding challenge websites. Fortunately, the Nim compiler generates C code. With a small amount of work, we can build a self-contained C source file suitable for submission.
Let's take a LeetCode challenge as an example. We write the main algorithm in Nim and use the emit pragma to write a C wrapper.