[Impact]
apt-ftparchive used a custom tree data structure and statically sized buffers, causing
1. buffer overflows in the statically sized buffers
2. exponential complexity on insertion as the per-directory binary trees were unbalanced (and debs are sorted, so they _always_ cause exponential complexity, building a linked list), causing contents generation to take hours instead of seconds.
3. stack overflow by recursion when trying to generate Contents for oracular with distribution-gpg-keys-copr included (as we are recursing the tree on the stack, we were over 30k stack frames deep at a cursory check of distribution-gpg-keys-copr alone).
This can lead to crashes and hence denial of service in apt-ftparchive when generating Contents files. The denial of service is not of significant concern, as it only affects a single repository and owners of repositories must have reasonable trust in the packages in said repositories, otherwise they would not be accepting them and plan to offer them to clients. An easier and more worthwhile denial of service can be achieved using zip bombs, that is, compressing multiple TBs of zeroes inside the deb, leading apt-ftparchive to spend hours in the Contents generation decompressing and ignoring the file data at probably 100% CPU usage.
This does not affect the apt library, nor does it affect other bits of apt-ftparchive outside the contents generation.
Hence we see the value of this mainly in functional terms, both making it significant faster and able to work with many files in the same directory, or deep file paths, in the first place.
[Test Plan]
The autopkgtests should prevent any regressions. We have added additional checks for apt-ftparchive contents, checking deep directories and directories with many files with valgrind. These also in particular check the correctness of the output of the Contents file generation.
The directory with many files did not cause a crash previously locally, it's unclear how to exactly reproduce the launchpad side; it probably needs the exact same set of debs as the Ubuntu archive.
[Where problems could occur]
We have rewritten the Contents file generation, removing the broken custom search tree in favor of a simple std::set of (path, package) pairs (where paths and packages are allocated in larger blocks for memory efficiency).
One notable change in behavior is that the list of packages is now sorted. It should be considered a bug that the list of packages was not ordered before, but it is a change in behavior.
[Other information]
Be advised that this is hard to review as a diff, given that it removes the old
implementation and adds the new one but keeps the function names. Particularly GenContents::Print() diff is sadly broken up into multiple chunks. It may be more suitable to just look at the new GenContents::Print() instead.
We have increased the size of the memory pools from 40960 byte to 4 MiB and added an abort() if we were to run out of memory there, so there still is a limit for path and package names, we do not anticipate reaching that though.
A simple change to apt-pkg/pkgcachegen.cc is included to pacify valgrind as needed for the stronger valgrind testing integration that is used to verify no buffer overflows in the test-apt-ftparchive-corner-cases test, as otherwise the other test using valgrind would fail.
This bug should remain open until apt is fixed, it's not clear what the security impact is.