lib/elf/elffileset.cpp

0001 /*
0002     Copyright (C) 2013-2014 Volker Krause <vkrause@kde.org>
0003
0004     This program is free software; you can redistribute it and/or modify it
0005     under the terms of the GNU Library General Public License as published by
0006     the Free Software Foundation; either version 2 of the License, or (at your
0007     option) any later version.
0008
0009     This program is distributed in the hope that it will be useful, but WITHOUT
0010     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0011     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
0012     License for more details.
0013
0014     You should have received a copy of the GNU General Public License
0015     along with this program.  If not, see <https://www.gnu.org/licenses/>.
0016 */
0017
0018 #include "elffileset.h"
0019 #include "elfheader.h"
0020 #include "elfgnudebuglinksection.h"
0021
0022 #include <QDebug>
0023 #include <QDir>
0024 #include <QFileInfo>
0025
0026 #include <cassert>
0027
0028 ElfFileSet::ElfFileSet(QObject* parent) : QObject(parent)
0029 {
0030     parseLdConf();
0031     foreach (const auto &path, qgetenv("LD_LIBRARY_PATH").split(':'))
0032         m_baseSearchPaths.push_back(path);
0033
0034     m_globalDebugSearchPath.push_back(QStringLiteral("/usr/lib/debug")); // seems hardcoded?
0035 }
0036
0037 ElfFileSet::~ElfFileSet()
0038 {
0039     qDeleteAll(m_files);
0040 }
0041
0042 void ElfFileSet::addFile(const QString& fileName)
0043 {
0044     ElfFile* f = new ElfFile(fileName);
0045     if (!f->open(QIODevice::ReadOnly) || !f->isValid()) {
0046         delete f;
0047         return;
0048     }
0049     addFile(f);
0050 }
0051
0052 static void resolvePlaceholder(QVector<QByteArray> &paths, const QByteArray &originPath)
0053 {
0054     for (auto it = paths.begin(); it != paths.end(); ++it)
0055         (*it).replace("$ORIGIN", originPath);
0056 }
0057
0058 void ElfFileSet::addFile(ElfFile* file)
0059 {
0060     assert(file);
0061     assert(file->isValid());
0062
0063     findSeparateDebugFile(file);
0064     m_files.push_back(file);
0065
0066     if (!file->dynamicSection())
0067         return;
0068
0069     auto rpaths = file->dynamicSection()->rpaths();
0070     auto runpaths = file->dynamicSection()->runpaths();
0071     auto originPath = QFileInfo(file->fileName()).absolutePath().toUtf8();
0072     resolvePlaceholder(rpaths, originPath);
0073     resolvePlaceholder(runpaths, originPath);
0074
0075     QVector<QByteArray> searchPaths;
0076     searchPaths.reserve(rpaths.size() + m_ldLibraryPaths.size() + runpaths.size() + m_baseSearchPaths.size());
0077     if (runpaths.isEmpty()) // DT_RPATH is supposed to be ignored if DT_RUNPATH is present
0078         searchPaths += rpaths;
0079     searchPaths += m_ldLibraryPaths;
0080     searchPaths += runpaths;
0081     searchPaths += m_baseSearchPaths;
0082
0083     foreach (const auto &lib, file->dynamicSection()->neededLibraries()) {
0084         if (std::find_if(m_files.cbegin(), m_files.cend(), [lib](ElfFile *file){ return file->dynamicSection()->soName() == lib; }) != m_files.cend())
0085             continue;
0086         bool dependencyFound = false;
0087         foreach (const auto &dir, searchPaths) {
0088             const auto fullPath = dir + '/' + lib;
0089             if (!QFile::exists(fullPath))
0090                 continue;
0091             ElfFile *dep = new ElfFile(fullPath);
0092             ElfFile *firstFile = m_files.at(0);
0093             if (dep->open(QIODevice::ReadOnly) && dep->isValid() && dep->type() == firstFile->type() && dep->header()->machine() == firstFile->header()->machine()) {
0094                 dependencyFound = true;
0095                 addFile(dep);
0096                 break;
0097             }
0098             delete dep;
0099         }
0100
0101         // deal with NEEDED entries containing absolute paths
0102         if (!dependencyFound && lib.startsWith('/')) {
0103             if (std::find_if(m_files.cbegin(), m_files.cend(), [lib](ElfFile *file){ return file->fileName() == lib; }) != m_files.cend())
0104                 continue;
0105             if (QFile::exists(lib)) {
0106                 ElfFile *dep = new ElfFile(lib);
0107                 ElfFile *firstFile = m_files.at(0);
0108                 if (dep->open(QIODevice::ReadOnly) && dep->isValid() && dep->type() == firstFile->type() && dep->header()->machine() == firstFile->header()->machine()) {
0109                     dependencyFound = true;
0110                     addFile(dep);
0111                 } else {
0112                     delete dep;
0113                 }
0114             }
0115         }
0116
0117         if (!dependencyFound)
0118             qWarning() << "Unable to locate dependency" << lib;
0119     }
0120 }
0121
0122 int ElfFileSet::size() const
0123 {
0124     return m_files.size();
0125 }
0126
0127 ElfFile* ElfFileSet::file(int index) const
0128 {
0129     return m_files.at(index);
0130 }
0131
0132 static bool hasUnresolvedDependencies(ElfFile *file, const QVector<ElfFile*> &resolved, int startIndex)
0133 {
0134     if (!file->dynamicSection())
0135         return false;
0136
0137     foreach (const auto &lib, file->dynamicSection()->neededLibraries()) {
0138         const auto it = std::find_if(resolved.constBegin() + startIndex, resolved.constEnd(), [lib](ElfFile *file){ return file->dynamicSection()->soName() == lib; });
0139         if (it == resolved.constEnd()) {
0140             return true;
0141         }
0142     }
0143     return false;
0144 }
0145
0146 void ElfFileSet::topologicalSort()
0147 {
0148     QVector<ElfFile*> sorted;
0149     sorted.resize(m_files.size());
0150
0151     QVector<ElfFile*> remaining = m_files;
0152
0153     for (int i = sorted.size() - 1; i >= 0; --i) {
0154         for (auto it = std::begin(remaining); it != std::end(remaining); ++it) {
0155             if (!hasUnresolvedDependencies(*it, sorted, i + 1)) {
0156                 sorted[i] = *it;
0157                 remaining.erase(it);
0158                 break;
0159             }
0160         }
0161
0162         // we did not find one with unresolved dependencies, shouldn't happen, unless there's a cycle
0163         // so just take one and see how far we get
0164         if (sorted.at(i) == nullptr)
0165             sorted[i] = remaining.takeFirst();
0166     }
0167
0168 #if 0
0169     qDebug() << "input";
0170     foreach(const auto f, m_files)
0171         qDebug() << f->displayName() << f->fileName();
0172     qDebug() << "sorted";
0173     foreach(const auto f, sorted)
0174         qDebug() << f->displayName();
0175     qDebug() << "remaining";
0176     foreach(const auto f, remaining)
0177         qDebug() << f->displayName();
0178 #endif
0179
0180     Q_ASSERT(remaining.isEmpty());
0181     if (sorted.first() != m_files.first()) {
0182         qWarning() << "FILE SET ORDER IS MESSED UP\nThis mostly happens due to missing dependencies. Let's try to ignore it for now...";
0183     }
0184
0185     m_files = sorted;
0186 }
0187
0188 void ElfFileSet::parseLdConf()
0189 {
0190     parseLdConf(QStringLiteral("/etc/ld.so.conf"));
0191
0192     // built-in defaults
0193     m_baseSearchPaths.push_back("/lib64");
0194     m_baseSearchPaths.push_back("/lib");
0195     m_baseSearchPaths.push_back("/usr/lib64");
0196     m_baseSearchPaths.push_back("/usr/lib");
0197 }
0198
0199 void ElfFileSet::parseLdConf(const QString& fileName)
0200 {
0201     QFile file(fileName);
0202     if (!file.open(QFile::ReadOnly)) {
0203         qWarning() << file.errorString();
0204         return;
0205     }
0206
0207     while (!file.atEnd()) {
0208         const auto line = file.readLine().trimmed();
0209         if (line.isEmpty())
0210             continue;
0211         if (line.startsWith('#'))
0212             continue;
0213         if (line.startsWith("include")) {
0214             const auto fileGlob = line.mid(8);
0215             if (QFileInfo::exists(fileGlob)) {
0216                 parseLdConf(fileGlob);
0217             } else {
0218                 const auto idx = fileGlob.lastIndexOf('/');
0219                 assert(idx >= 0);
0220                 QDir dir(fileGlob.left(idx));
0221                 foreach (const auto &file, dir.entryList(QStringList() << fileGlob.mid(idx + 1)))
0222                     parseLdConf(dir.absolutePath() + '/' + file);
0223             }
0224             continue;
0225         }
0226         if (line.startsWith('/')) {
0227             if (QFileInfo::exists(line))
0228                 m_baseSearchPaths.push_back(line);
0229             continue;
0230         }
0231         qWarning() << "unable to handle ld.so.conf line:" << line;
0232     }
0233 }
0234
0235 void ElfFileSet::findSeparateDebugFile(ElfFile* file) const
0236 {
0237     // (1) via build id
0238     const auto buildId = file->buildId().toHex();
0239     foreach (const auto &debugDir, m_globalDebugSearchPath) {
0240         auto debugFile = debugDir + "/.build-id/" + buildId.left(2) + "/" + buildId.mid(2) + ".debug";
0241         if (QFile::exists(debugFile)) {
0242             file->setSeparateDebugFile(debugFile);
0243             return;
0244         }
0245     }
0246
0247     // (2) via debug link
0248     const auto debugLinkIndex = file->indexOfSection(".gnu_debuglink");
0249     if (debugLinkIndex < 0)
0250         return;
0251     const auto debugLinkSection = file->section<ElfGnuDebugLinkSection>(debugLinkIndex);
0252     assert(debugLinkSection);
0253     if (debugLinkSection->fileName().isEmpty())
0254         return;
0255     const auto dir = QFileInfo(file->fileName()).absolutePath();
0256
0257     // (2a) next to file
0258     auto debugFile = dir + "/" + debugLinkSection->fileName();
0259     if (isValidDebugLinkFile(debugFile, debugLinkSection->crc())) {
0260         file->setSeparateDebugFile(debugFile);
0261         return;
0262     }
0263
0264     // (2b) in .debug sub-folder next to file
0265     debugFile = dir + "/.debug/" + debugLinkSection->fileName();
0266     if (isValidDebugLinkFile(debugFile, debugLinkSection->crc())) {
0267         file->setSeparateDebugFile(debugFile);
0268         return;
0269     }
0270
0271     // (2c) in global debug directories
0272     foreach (const auto &debugDir, m_globalDebugSearchPath) {
0273         debugFile = debugDir + dir + "/" + debugLinkSection->fileName();
0274         if (isValidDebugLinkFile(debugFile, debugLinkSection->crc())) {
0275             file->setSeparateDebugFile(debugFile);
0276             return;
0277         }
0278     }
0279 }
0280
0281 // from GDB manual
0282 static uint32_t gnu_debuglink_crc32 (uint32_t crc, unsigned char *buf, size_t len)
0283 {
0284     static const unsigned long crc32_table[256] =
0285     {
0286         0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419,
0287         0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4,
0288         0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07,
0289         0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
0290         0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856,
0291         0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
0292         0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4,
0293         0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
0294         0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3,
0295         0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a,
0296         0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599,
0297         0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
0298         0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190,
0299         0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f,
0300         0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e,
0301         0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
0302         0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed,
0303         0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
0304         0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3,
0305         0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
0306         0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a,
0307         0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5,
0308         0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010,
0309         0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
0310         0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17,
0311         0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6,
0312         0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615,
0313         0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
0314         0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344,
0315         0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
0316         0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a,
0317         0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
0318         0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1,
0319         0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c,
0320         0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef,
0321         0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
0322         0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe,
0323         0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31,
0324         0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c,
0325         0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
0326         0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b,
0327         0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
0328         0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1,
0329         0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
0330         0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278,
0331         0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7,
0332         0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66,
0333         0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
0334         0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605,
0335         0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8,
0336         0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b,
0337         0x2d02ef8d
0338     };
0339     unsigned char *end;
0340
0341     crc = ~crc & 0xffffffff;
0342     for (end = buf + len; buf < end; ++buf)
0343         crc = crc32_table[(crc ^ *buf) & 0xff] ^ (crc >> 8);
0344     return ~crc & 0xffffffff;
0345 }
0346
0347 bool ElfFileSet::isValidDebugLinkFile(const QString& fileName, uint32_t expectedCrc)
0348 {
0349     if (!QFile::exists(fileName))
0350         return false;
0351
0352     QFile f(fileName);
0353     if (!f.open(QFile::ReadOnly))
0354         return false;
0355
0356     auto data = f.map(0, f.size());
0357     if (!data)
0358         return false;
0359
0360     auto actualCrc = gnu_debuglink_crc32(0, data, f.size());
0361     qDebug() << fileName << expectedCrc << actualCrc;
0362     return actualCrc == expectedCrc;
0363 }