[v3,0/7] debuginfod: speed up extraction from kernel debuginfo packages by 200x

  From: Omar Sandoval <osandov@fb.com>

This is v3 of my patch series optimizing debuginfod for kernel
debuginfo.  v1 is here [7], v2 is here [8].  This version fixes a couple
of minor bugs and adds test cases.

Changes from v2 to v3:

- Added a test case with seekable rpm and deb files.
- Added a couple of independent fixes uncovered while adding tests.
- Added a few more prometheus metrics.
- Fixed passive mode.

Patches 1 and 2 fix existing bugs that the were uncovered by adding new
test package files.  Patch 3 is a preparatory refactor.  Patch 4 makes
the schema changes. Patch 5 implements the seekable xz extraction.
Patch 6 populates the table of seekable entries at scan time and adds a
test.  Patch 7 does it for pre-existing files at request time.

Here is the background copied and pasted from v1:

drgn [1] currently uses debuginfod with great success for debugging
userspace processes.  However, for debugging the Linux kernel (drgn's
main use case), we have had some performance issues with debuginfod, so
we intentionally avoid using it.  Specifically, it sometimes takes over
a minute for debuginfod to respond to queries for vmlinux and kernel
modules (not including the actual download time).

The reason for the slowness is that Linux kernel debuginfo packages are
very large and contain lots of files.  To respond to a query for a Linux
kernel debuginfo file, debuginfod has to decompress and iterate through
the whole package until it finds that file.  If the file is towards the
end of the package, this can take a very long time.  This was previously
reported for vdso files [2][3], which debuginfod was able to mitigate
with improved caching and prefetching.  However, kernel modules are far
greater in number, vary drastically by hardware and workload, and can be
spread all over the package, so in practice I've still been seeing long
delays.  This was also discussed on the drgn issue tracker [4].

The fundamental limitation is that Linux packages, which are essentially
compressed archives with extra metadata headers, don't support random
access to specific files.  However, the multi-threaded xz compression
format does actually support random access.  And, luckily, the kernel
debuginfo packages on Fedora, Debian, and Ubuntu all happen to use
multi-threaded xz compression!

debuginfod can take advantage of this: when it scans a package, if it is
a seekable xz archive, it can save the uncompressed offset and size of
each file.  Then, when it needs a file, it can seek to that offset and
extract it from there.  This requires some understanding of the xz
format and low-level liblzma code, but the speedup is massive: where the
worst case was previously about 50 seconds just to find a file in a
kernel debuginfo package, with this change the worst case is 0.25
seconds, a ~200x improvement! This works for both .rpm and .deb files.

I tested this by requesting and verifying the digest of every file from
a few kernel debuginfo rpms and debs [5].

P.S. The biggest downside of this change is that it depends on a very
specific compression format that is only used by kernel packages
incidentally.  I think this is something we should formalize with Linux
distributions: large debuginfo packages should use a seekable format.
Currently, xz in multi-threaded mode is the only option, but Zstandard
also has an experimental seekable format that is worth looking into [6].

Thanks,
Omar

1: https://github.com/osandov/drgn
2: https://sourceware.org/bugzilla/show_bug.cgi?id=29478
3: https://bugzilla.redhat.com/show_bug.cgi?id=1970578
4: https://github.com/osandov/drgn/pull/380
5: https://gist.github.com/osandov/89d521fdc6c9a07aa8bb0ebf91974346
6: https://github.com/facebook/zstd/tree/dev/contrib/seekable_format
7: https://sourceware.org/pipermail/elfutils-devel/2024q3/007191.html
8: https://sourceware.org/pipermail/elfutils-devel/2024q3/007208.html

Omar Sandoval (7):
  debuginfod: fix skipping <built-in> source file
  tests/run-debuginfod-fd-prefetch-caches.sh: disable fdcache limit
    check
  debuginfod: factor out common code for responding from an archive
  debugifod: add new table and views for seekable archives
  debuginfod: optimize extraction from seekable xz archives
  debuginfod: populate _r_seekable on scan
  debuginfod: populate _r_seekable on request

 configure.ac                                  |   5 +
 debuginfod/Makefile.am                        |   2 +-
 debuginfod/debuginfod.cxx                     | 928 +++++++++++++++---
 tests/Makefile.am                             |   4 +-
 ...pressme-seekable-xz-dbgsym_1.0-1_amd64.deb | Bin 0 -> 6288 bytes
 ...compressme-seekable-xz_1.0-1.debian.tar.xz | Bin 0 -> 1440 bytes
 .../compressme-seekable-xz_1.0-1.dsc          |  19 +
 .../compressme-seekable-xz_1.0-1_amd64.deb    | Bin 0 -> 6208 bytes
 .../compressme-seekable-xz_1.0.orig.tar.xz    | Bin 0 -> 7160 bytes
 .../compressme-seekable-xz-1.0-1.src.rpm      | Bin 0 -> 15880 bytes
 .../compressme-seekable-xz-1.0-1.x86_64.rpm   | Bin 0 -> 31873 bytes
 ...sme-seekable-xz-debuginfo-1.0-1.x86_64.rpm | Bin 0 -> 21917 bytes
 ...e-seekable-xz-debugsource-1.0-1.x86_64.rpm | Bin 0 -> 7961 bytes
 tests/run-debuginfod-archive-groom.sh         |   2 +-
 tests/run-debuginfod-extraction.sh            |   2 +-
 tests/run-debuginfod-fd-prefetch-caches.sh    |   4 +
 tests/run-debuginfod-seekable.sh              | 186 ++++
 17 files changed, 1007 insertions(+), 145 deletions(-)
 create mode 100644 tests/debuginfod-debs/seekable-xz/compressme-seekable-xz-dbgsym_1.0-1_amd64.deb
 create mode 100644 tests/debuginfod-debs/seekable-xz/compressme-seekable-xz_1.0-1.debian.tar.xz
 create mode 100644 tests/debuginfod-debs/seekable-xz/compressme-seekable-xz_1.0-1.dsc
 create mode 100644 tests/debuginfod-debs/seekable-xz/compressme-seekable-xz_1.0-1_amd64.deb
 create mode 100644 tests/debuginfod-debs/seekable-xz/compressme-seekable-xz_1.0.orig.tar.xz
 create mode 100644 tests/debuginfod-rpms/seekable-xz/compressme-seekable-xz-1.0-1.src.rpm
 create mode 100644 tests/debuginfod-rpms/seekable-xz/compressme-seekable-xz-1.0-1.x86_64.rpm
 create mode 100644 tests/debuginfod-rpms/seekable-xz/compressme-seekable-xz-debuginfo-1.0-1.x86_64.rpm
 create mode 100644 tests/debuginfod-rpms/seekable-xz/compressme-seekable-xz-debugsource-1.0-1.x86_64.rpm
 create mode 100755 tests/run-debuginfod-seekable.sh
  

Hi -

> This is v3 of my patch series optimizing debuginfod for kernel
> debuginfo.  v1 is here [7], v2 is here [8].  This version fixes a couple
> of minor bugs and adds test cases. [...]

Thanks, LGTM, running through try-buildbots to make sure.

- FChE
  

On Fri, Jul 19, 2024 at 01:34:48PM -0400, Frank Ch. Eigler wrote:
> Hi -
> 
> > This is v3 of my patch series optimizing debuginfod for kernel
> > debuginfo.  v1 is here [7], v2 is here [8].  This version fixes a couple
> > of minor bugs and adds test cases. [...]
> 
> Thanks, LGTM, running through try-buildbots to make sure.

Sorry about the distcheck failures, looks like I forgot to add the new
test files to EXTRA_DIST.  I'll be sure to run distcheck next time.

I'll send v4 shortly.

Thanks,
Omar