source: CLRX/CLRadeonExtender/trunk/amdbin/ElfBinaries.cpp @ 2540

Last change on this file since 2540 was 2540, checked in by matszpk, 3 years ago

CLRadeonExtender: ElfBinaries?: Add skipFirst (skip STN_UNDEF) to hashtable routines.

File size: 39.7 KB
Line 
1/*
2 *  CLRadeonExtender - Unofficial OpenCL Radeon Extensions Library
3 *  Copyright (C) 2014-2016 Mateusz Szpakowski
4 *
5 *  This library is free software; you can redistribute it and/or
6 *  modify it under the terms of the GNU Lesser General Public
7 *  License as published by the Free Software Foundation; either
8 *  version 2.1 of the License, or (at your option) any later version.
9 *
10 *  This library is distributed in the hope that it will be useful,
11 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13 *  Lesser General Public License for more details.
14 *
15 *  You should have received a copy of the GNU Lesser General Public
16 *  License along with this library; if not, write to the Free Software
17 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
18 */
19
20#include <CLRX/Config.h>
21#include <cstdlib>
22#include <cstring>
23#include <cstdint>
24#include <climits>
25#include <utility>
26#include <string>
27#include <cassert>
28#include <CLRX/amdbin/Elf.h>
29#include <CLRX/utils/Utilities.h>
30#include <CLRX/utils/MemAccess.h>
31#include <CLRX/amdbin/AmdBinaries.h>
32
33static const uint32_t elfMagicValue = 0x464c457fU;
34
35/* INFO: in this file is used ULEV function for conversion
36 * from LittleEndian and unaligned access to other memory access policy and endianness
37 * Please use this function whenever you want to get or set word in ELF binary,
38 * because ELF binaries can be unaligned in memory (as inner binaries).
39 */
40
41using namespace CLRX;
42
43/* determine unfinished strings region in string table for checking further consistency */
44static size_t unfinishedRegionOfStringTable(const cxbyte* table, size_t size)
45{
46    if (size == 0) // if zero
47        return 0;
48    size_t k;
49    for (k = size-1; k>0 && table[k]!=0; k--);
50   
51    return (table[k]==0)?k+1:k;
52}
53
54/* elf32 types */
55
56const cxbyte CLRX::Elf32Types::ELFCLASS = ELFCLASS32;
57const uint32_t CLRX::Elf32Types::bitness = 32;
58const char* CLRX::Elf32Types::bitName = "32";
59
60/* elf64 types */
61
62const cxbyte CLRX::Elf64Types::ELFCLASS = ELFCLASS64;
63const cxuint CLRX::Elf64Types::bitness = 64;
64const char* CLRX::Elf64Types::bitName = "64";
65
66/* ElfBinaryTemplate */
67
68template<typename Types>
69ElfBinaryTemplate<Types>::ElfBinaryTemplate() : binaryCodeSize(0), binaryCode(nullptr),
70        sectionStringTable(nullptr), symbolStringTable(nullptr),
71        symbolTable(nullptr), dynSymStringTable(nullptr), dynSymTable(nullptr),
72        symbolsNum(0), dynSymbolsNum(0),
73        symbolEntSize(0), dynSymEntSize(0)
74{ }
75
76template<typename Types>
77ElfBinaryTemplate<Types>::~ElfBinaryTemplate()
78{ }
79
80template<typename Types>
81ElfBinaryTemplate<Types>::ElfBinaryTemplate(size_t _binaryCodeSize, cxbyte* _binaryCode,
82             Flags _creationFlags) : creationFlags(_creationFlags),
83        binaryCodeSize(_binaryCodeSize), binaryCode(_binaryCode),
84        sectionStringTable(nullptr), symbolStringTable(nullptr),
85        symbolTable(nullptr), dynSymStringTable(nullptr), dynSymTable(nullptr),
86        symbolsNum(0), dynSymbolsNum(0), symbolEntSize(0), dynSymEntSize(0)       
87{
88    if (binaryCodeSize < sizeof(typename Types::Ehdr))
89        throw Exception("Binary is too small!!!");
90   
91    const typename Types::Ehdr* ehdr =
92            reinterpret_cast<const typename Types::Ehdr*>(binaryCode);
93   
94    if (ULEV(*reinterpret_cast<const uint32_t*>(binaryCode)) != elfMagicValue)
95        throw Exception("This is not ELF binary");
96    if (ehdr->e_ident[EI_CLASS] != Types::ELFCLASS)
97        throw Exception(std::string("This is not ")+Types::bitName+"bit ELF binary");
98    if (ehdr->e_ident[EI_DATA] != ELFDATA2LSB)
99        throw Exception("Other than little-endian binaries are not supported!");
100   
101    if ((ULEV(ehdr->e_phoff) == 0 && ULEV(ehdr->e_phnum) != 0))
102        throw Exception("Elf invalid phoff and phnum combination");
103    if (ULEV(ehdr->e_phoff) != 0)
104    {   /* reading and checking program headers */
105        if (ULEV(ehdr->e_phoff) > binaryCodeSize)
106            throw Exception("ProgramHeaders offset out of range!");
107        if (usumGt(ULEV(ehdr->e_phoff),
108                   ((typename Types::Word)ULEV(ehdr->e_phentsize))*ULEV(ehdr->e_phnum),
109                   binaryCodeSize))
110            throw Exception("ProgramHeaders offset+size out of range!");
111       
112        cxuint phnum = ULEV(ehdr->e_phnum);
113        // checking program header segment offset ranges
114        for (cxuint i = 0; i < phnum; i++)
115        {
116            const typename Types::Phdr& phdr = getProgramHeader(i);
117            if (ULEV(phdr.p_offset) > binaryCodeSize)
118                throw Exception("Segment offset out of range!");
119            if (usumGt(ULEV(phdr.p_offset), ULEV(phdr.p_filesz), binaryCodeSize))
120                throw Exception("Segment offset+size out of range!");
121        }
122    }
123   
124    if ((ULEV(ehdr->e_shoff) == 0 && ULEV(ehdr->e_shnum) != 0))
125        throw Exception("Elf invalid shoff and shnum combination");
126    if (ULEV(ehdr->e_shoff) != 0 && ULEV(ehdr->e_shstrndx) != SHN_UNDEF)
127    {   /* indexing of sections */
128        if (ULEV(ehdr->e_shoff) > binaryCodeSize)
129            throw Exception("SectionHeaders offset out of range!");
130        if (usumGt(ULEV(ehdr->e_shoff),
131                  ((typename Types::Word)ULEV(ehdr->e_shentsize))*ULEV(ehdr->e_shnum),
132                  binaryCodeSize))
133            throw Exception("SectionHeaders offset+size out of range!");
134        if (ULEV(ehdr->e_shstrndx) >= ULEV(ehdr->e_shnum))
135            throw Exception("Shstrndx out of range!");
136       
137        typename Types::Shdr& shstrShdr = getSectionHeader(ULEV(ehdr->e_shstrndx));
138        sectionStringTable = binaryCode + ULEV(shstrShdr.sh_offset);
139        const size_t unfinishedShstrPos = unfinishedRegionOfStringTable(
140                    sectionStringTable, ULEV(shstrShdr.sh_size));
141       
142        const typename Types::Shdr* symTableHdr = nullptr;
143        const typename Types::Shdr* dynSymTableHdr = nullptr;
144       
145        cxuint shnum = ULEV(ehdr->e_shnum);
146        if ((creationFlags & ELF_CREATE_SECTIONMAP) != 0)
147            sectionIndexMap.resize(shnum);
148        for (cxuint i = 0; i < shnum; i++)
149        {
150            const typename Types::Shdr& shdr = getSectionHeader(i);
151            /// checking section offset ranges
152            if (ULEV(shdr.sh_offset) > binaryCodeSize)
153                throw Exception("Section offset out of range!");
154            if (ULEV(shdr.sh_type) != SHT_NOBITS)
155                if (usumGt(ULEV(shdr.sh_offset), ULEV(shdr.sh_size), binaryCodeSize))
156                    throw Exception("Section offset+size out of range!");
157            if (ULEV(shdr.sh_link) >= ULEV(ehdr->e_shnum))
158                throw Exception("Section link out of range!");
159           
160            const typename Types::Size sh_nameindx = ULEV(shdr.sh_name);
161            if (sh_nameindx >= ULEV(shstrShdr.sh_size))
162                throw Exception("Section name index out of range!");
163           
164            if (sh_nameindx >= unfinishedShstrPos)
165                throw Exception("Unfinished section name!");
166           
167            const char* shname =
168                reinterpret_cast<const char*>(sectionStringTable + sh_nameindx);
169           
170            if ((creationFlags & ELF_CREATE_SECTIONMAP) != 0)
171                sectionIndexMap[i] = std::make_pair(shname, i);
172            // set symbol table and dynamic symbol table pointers
173            if (ULEV(shdr.sh_type) == SHT_SYMTAB)
174                symTableHdr = &shdr;
175            if (ULEV(shdr.sh_type) == SHT_DYNSYM)
176                dynSymTableHdr = &shdr;
177        }
178        if ((creationFlags & ELF_CREATE_SECTIONMAP) != 0)
179            mapSort(sectionIndexMap.begin(), sectionIndexMap.end(), CStringLess());
180       
181        if (symTableHdr != nullptr)
182        {   // indexing symbols
183            if (ULEV(symTableHdr->sh_entsize) < sizeof(typename Types::Sym))
184                throw Exception("SymTable entry size is too small!");
185           
186            symbolEntSize = ULEV(symTableHdr->sh_entsize);
187            symbolTable = binaryCode + ULEV(symTableHdr->sh_offset);
188            if (ULEV(symTableHdr->sh_link) == SHN_UNDEF)
189                throw Exception("Symbol table doesn't have string table");
190           
191            typename Types::Shdr& symstrShdr = getSectionHeader(ULEV(symTableHdr->sh_link));
192            symbolStringTable = binaryCode + ULEV(symstrShdr.sh_offset);
193           
194            const size_t unfinishedSymstrPos = unfinishedRegionOfStringTable(
195                    symbolStringTable, ULEV(symstrShdr.sh_size));
196            symbolsNum = ULEV(symTableHdr->sh_size)/ULEV(symTableHdr->sh_entsize);
197            if ((creationFlags & ELF_CREATE_SYMBOLMAP) != 0)
198                symbolIndexMap.resize(symbolsNum);
199           
200            for (typename Types::Size i = 0; i < symbolsNum; i++)
201            {   /* verify symbol names */
202                const typename Types::Sym& sym = getSymbol(i);
203                const typename Types::Size symnameindx = ULEV(sym.st_name);
204                if (symnameindx >= ULEV(symstrShdr.sh_size))
205                    throw Exception("Symbol name index out of range!");
206                // check whether name is finished in string section content
207                if (symnameindx >= unfinishedSymstrPos)
208                    throw Exception("Unfinished symbol name!");
209               
210                const char* symname =
211                    reinterpret_cast<const char*>(symbolStringTable + symnameindx);
212                // add to symbol map
213                if ((creationFlags & ELF_CREATE_SYMBOLMAP) != 0)
214                    symbolIndexMap[i] = std::make_pair(symname, i);
215            }
216            if ((creationFlags & ELF_CREATE_SYMBOLMAP) != 0)
217                mapSort(symbolIndexMap.begin(), symbolIndexMap.end(), CStringLess());
218        }
219        if (dynSymTableHdr != nullptr)
220        {   // indexing dynamic symbols
221            if (ULEV(dynSymTableHdr->sh_entsize) < sizeof(typename Types::Sym))
222                throw Exception("DynSymTable entry size is too small!");
223           
224            dynSymEntSize = ULEV(dynSymTableHdr->sh_entsize);
225            dynSymTable = binaryCode + ULEV(dynSymTableHdr->sh_offset);
226            if (ULEV(dynSymTableHdr->sh_link) == SHN_UNDEF)
227                throw Exception("DynSymbol table doesn't have string table");
228           
229            typename Types::Shdr& dynSymstrShdr =
230                    getSectionHeader(ULEV(dynSymTableHdr->sh_link));
231            dynSymbolsNum = ULEV(dynSymTableHdr->sh_size)/ULEV(dynSymTableHdr->sh_entsize);
232           
233            dynSymStringTable = binaryCode + ULEV(dynSymstrShdr.sh_offset);
234            const size_t unfinishedSymstrPos = unfinishedRegionOfStringTable(
235                    dynSymStringTable, ULEV(dynSymstrShdr.sh_size));
236           
237            if ((creationFlags & ELF_CREATE_DYNSYMMAP) != 0)
238                dynSymIndexMap.resize(dynSymbolsNum);
239           
240            for (typename Types::Size i = 0; i < dynSymbolsNum; i++)
241            {   /* verify symbol names */
242                const typename Types::Sym& sym = getDynSymbol(i);
243                const typename Types::Size symnameindx = ULEV(sym.st_name);
244                if (symnameindx >= ULEV(dynSymstrShdr.sh_size))
245                    throw Exception("DynSymbol name index out of range!");
246                // check whether name is finished in string section content
247                if (symnameindx >= unfinishedSymstrPos)
248                    throw Exception("Unfinished dynsymbol name!");
249               
250                const char* symname =
251                    reinterpret_cast<const char*>(dynSymStringTable + symnameindx);
252                // add to symbol map
253                if ((creationFlags & ELF_CREATE_DYNSYMMAP) != 0)
254                    dynSymIndexMap[i] = std::make_pair(symname, i);
255            }
256            if ((creationFlags & ELF_CREATE_DYNSYMMAP) != 0)
257                mapSort(dynSymIndexMap.begin(), dynSymIndexMap.end(), CStringLess());
258        }
259    }
260}
261
262template<typename Types>
263uint16_t ElfBinaryTemplate<Types>::getSectionIndex(const char* name) const
264{
265    if (hasSectionMap())
266    {
267        SectionIndexMap::const_iterator it = binaryMapFind(
268                    sectionIndexMap.begin(), sectionIndexMap.end(), name, CStringLess());
269        if (it == sectionIndexMap.end())
270            throw Exception(std::string("Can't find Elf")+Types::bitName+" Section");
271        return it->second;
272    }
273    else
274    {
275        for (cxuint i = 0; i < getSectionHeadersNum(); i++)
276        {
277            if (::strcmp(getSectionName(i), name) == 0)
278                return i;
279        }
280        throw Exception(std::string("Can't find Elf")+Types::bitName+" Section");
281    }
282}
283
284template<typename Types>
285typename Types::Size ElfBinaryTemplate<Types>::getSymbolIndex(const char* name) const
286{
287    SymbolIndexMap::const_iterator it = binaryMapFind(
288                    symbolIndexMap.begin(), symbolIndexMap.end(), name, CStringLess());
289    if (it == symbolIndexMap.end())
290        throw Exception(std::string("Can't find Elf")+Types::bitName+" Symbol");
291    return it->second;
292}
293
294template<typename Types>
295typename Types::Size ElfBinaryTemplate<Types>::getDynSymbolIndex(const char* name) const
296{
297    SymbolIndexMap::const_iterator it = binaryMapFind(
298                    dynSymIndexMap.begin(), dynSymIndexMap.end(), name, CStringLess());
299    if (it == dynSymIndexMap.end())
300        throw Exception(std::string("Can't find Elf")+Types::bitName+" DynSymbol");
301    return it->second;
302}
303
304template class CLRX::ElfBinaryTemplate<CLRX::Elf32Types>;
305template class CLRX::ElfBinaryTemplate<CLRX::Elf64Types>;
306
307bool CLRX::isElfBinary(size_t binarySize, const cxbyte* binary)
308{
309    if (binarySize < sizeof(Elf32_Ehdr) ||
310        ULEV(*reinterpret_cast<const uint32_t*>(binary)) != elfMagicValue)
311        return false;
312    if ((binary[EI_CLASS] != ELFCLASS32 && binary[EI_CLASS] != ELFCLASS64) ||
313        binary[EI_DATA] != ELFDATA2LSB) // only LSB elf is supported
314        return false;
315    if ((binary[EI_CLASS] == ELFCLASS32 && binarySize < sizeof(Elf32_Ehdr)) ||
316        (binary[EI_CLASS] == ELFCLASS64 && binarySize < sizeof(Elf64_Ehdr)))
317        return false;
318    if (ULEV(*((const uint64_t*)(binary+8))) != 0)
319        return false;
320    return true;
321}
322
323/*
324 * Elf binary generator
325 */
326
327uint16_t CLRX::convertSectionId(cxuint sectionIndex, const uint16_t* builtinSections,
328                  cxuint maxBuiltinSection, cxuint extraSectionIndex)
329{
330    if (sectionIndex == ELFSECTID_NULL)
331        return 0;
332    if (sectionIndex == ELFSECTID_ABS)
333        return SHN_ABS;
334    if (sectionIndex == ELFSECTID_UNDEF)
335        return SHN_UNDEF;
336    if (sectionIndex < ELFSECTID_START)
337        return sectionIndex+extraSectionIndex;
338    else if (sectionIndex >= ELFSECTID_START && sectionIndex <= maxBuiltinSection)
339    {
340        const uint16_t shndx = builtinSections[sectionIndex-ELFSECTID_START];
341        if (shndx == SHN_UNDEF) // if table entry for sectionIndex is not defined
342            throw Exception("Wrong BinSection:sectionId");
343        return builtinSections[sectionIndex-ELFSECTID_START];
344    }
345    else // failed
346        throw Exception("Wrong BinSection:sectionId");
347}
348
349ElfRegionContent::~ElfRegionContent()
350{ }
351
352template<typename Types>
353ElfBinaryGenTemplate<Types>::ElfBinaryGenTemplate()
354        : sizeComputed(false), addNullSym(true), addNullDynSym(true), addNullSection(true),
355          addrStartRegion(0), shStrTab(0), strTab(0), dynStr(0), shdrTabRegion(0),
356          phdrTabRegion(0)
357{ }
358
359template<typename Types>
360ElfBinaryGenTemplate<Types>::ElfBinaryGenTemplate(const ElfHeaderTemplate<Types>& _header,
361            bool _addNullSym, bool _addNullDynSym, bool _addNullSection,
362            cxuint addrCountingFromRegion)
363        : sizeComputed(false), addNullSym(_addNullSym), addNullDynSym(_addNullDynSym),
364          addNullSection(_addNullSection),  addrStartRegion(addrCountingFromRegion),
365          shStrTab(0), strTab(0), dynStr(0), shdrTabRegion(0), phdrTabRegion(0),
366          header(_header)
367{ }
368
369template<typename Types>
370void ElfBinaryGenTemplate<Types>::addRegion(const ElfRegionTemplate<Types>& region)
371{ regions.push_back(region); }
372
373template<typename Types>
374void ElfBinaryGenTemplate<Types>::addProgramHeader(
375            const ElfProgramHeaderTemplate<Types>& progHeader)
376{ progHeaders.push_back(progHeader); }
377
378template<typename Types>
379void ElfBinaryGenTemplate<Types>::computeSize()
380{
381    if (sizeComputed) return;
382   
383    /* verify data */
384    if (header.entryRegion != UINT_MAX && header.entryRegion >= regions.size())
385        throw Exception("Header entry region out of range");
386   
387    regionOffsets.reset(new typename Types::Word[regions.size()]);
388    regionAddresses.reset(new typename Types::Word[regions.size()]);
389    size = sizeof(typename Types::Ehdr);
390    sectionsNum = addNullSection; // if add null section
391    for (const auto& region: regions)
392        if (region.type == ElfRegionType::SECTION)
393            sectionsNum++;
394    sectionRegions.reset(new cxuint[sectionsNum+1]);
395    sectionRegions[0] = UINT_MAX;
396    cxuint sectionCount = 1;
397    typename Types::Word address = 0;
398   
399    for (const auto& sym: symbols)
400        if (sym.sectionIndex >= sectionsNum)
401            throw Exception("Symbol section index out of range");
402    for (const auto& sym: dynSymbols)
403        if (sym.sectionIndex >= sectionsNum)
404            throw Exception("DynSymbol section index out of range");
405   
406    for (size_t i = 0; i < regions.size(); i++)
407    {
408        ElfRegionTemplate<Types>& region = regions[i];
409        if (region.align > 1)
410        {   // fix alignment
411            if ((size&(region.align-1))!=0)
412                size += region.align - (size&(region.align-1));
413            if ((address&(region.align-1))!=0)
414                address += region.align - (address&(region.align-1));
415        }
416       
417        regionOffsets[i] = size;
418        regionAddresses[i] = address;
419        // add region size
420        if (region.type == ElfRegionType::PHDR_TABLE)
421        {
422            size += uint64_t(progHeaders.size())*sizeof(typename Types::Phdr);
423            region.size = size-regionOffsets[i];
424            phdrTabRegion = i;
425            for (const auto& progHdr: progHeaders)
426            {
427                if (progHdr.regionStart >= regions.size())
428                    throw Exception("Region start out of range");
429                if (uint64_t(progHdr.regionStart) + progHdr.regionsNum > regions.size())
430                    throw Exception("Region end out of range");
431            }
432        }
433        else if (region.type == ElfRegionType::SHDR_TABLE)
434        {
435            size += uint64_t(sectionsNum)*sizeof(typename Types::Shdr);
436            region.size = size-regionOffsets[i];
437            shdrTabRegion = i;
438        }
439        else if (region.type == ElfRegionType::USER)
440            size += region.size;
441        else if (region.type == ElfRegionType::SECTION)
442        {   // if section
443            if (region.section.link >= sectionsNum)
444                throw Exception("Section link out of range");
445           
446            if (region.section.type != SHT_NOBITS && region.size != 0)
447                size += region.size;
448            else // otherwise get default size for symtab, dynsym, strtab, dynstr
449            {
450                if (region.section.type == SHT_SYMTAB)
451                    size += uint64_t(symbols.size()+addNullSym)*
452                                sizeof(typename Types::Sym);
453                else if (region.section.type == SHT_DYNSYM)
454                    size += uint64_t(dynSymbols.size()+addNullDynSym)*
455                                sizeof(typename Types::Sym);
456                else if (region.section.type == SHT_STRTAB)
457                {
458                    if (::strcmp(region.section.name, ".strtab") == 0)
459                    {
460                        size += (addNullSym);
461                        for (const auto& sym: symbols)
462                            if (sym.name != nullptr && sym.name[0] != 0)
463                                size += ::strlen(sym.name)+1;
464                    }
465                    else if (::strcmp(region.section.name, ".dynstr") == 0)
466                    {
467                        size += (addNullDynSym);
468                        for (const auto& sym: dynSymbols)
469                            if (sym.name != nullptr && sym.name[0] != 0)
470                                size += ::strlen(sym.name)+1;
471                    }
472                    else if (::strcmp(region.section.name, ".shstrtab") == 0)
473                    {
474                        size += (addNullSection);
475                        for (const auto& region2: regions)
476                        {
477                            if (region2.type == ElfRegionType::SECTION &&
478                                region2.section.name != nullptr &&
479                                region2.section.name[0] != 0)
480                                size += ::strlen(region2.section.name)+1;
481                        }
482                    }
483                }
484                if (region.section.type != SHT_NOBITS)
485                    region.size = size-regionOffsets[i];
486            }
487            if (i >= addrStartRegion) // begin counting address from that region
488                address += region.size;
489           
490            if (::strcmp(region.section.name, ".strtab") == 0)
491                strTab = sectionCount;
492            else if (::strcmp(region.section.name, ".dynstr") == 0)
493                dynStr = sectionCount;
494            else if (::strcmp(region.section.name, ".shstrtab") == 0)
495                shStrTab = sectionCount;
496            sectionRegions[sectionCount] = i;
497            sectionCount++;
498        }
499    }
500   
501    sizeComputed = true;
502}
503
504template<typename Types>
505uint64_t ElfBinaryGenTemplate<Types>::countSize()
506{
507    computeSize();
508    return size;
509}
510
511template<typename Types>
512static std::unique_ptr<uint32_t[]> calculateHashValuesForSymbols(bool addNullSymbol,
513            const std::vector<ElfSymbolTemplate<Types> >& symbols)
514{
515    const size_t symsNum = symbols.size() + addNullSymbol;
516    std::unique_ptr<uint32_t[]> hashCodes(new uint32_t[symsNum]);
517    if (addNullSymbol)
518        hashCodes[0] = 0;
519    for (size_t i = 0; i < symbols.size(); i++)
520    {
521        uint32_t h = 0, g;
522        const cxbyte* name = reinterpret_cast<const cxbyte*>(symbols[i].name);
523        while(*name!=0)
524        {
525            h = (h<<4) + *name++;
526            g = h & 0xf0000000U;
527            if (g) h ^= g>>24;
528            h &= ~g;
529        }
530        hashCodes[i+addNullSymbol] = h;
531    }
532    return hashCodes;
533}
534
535/// return bucket number
536static uint32_t optimizeHashBucketsNum(uint32_t hashNum, bool skipFirst,
537                           const uint32_t* hashCodes)
538{
539    uint32_t bestBucketNum = 0;
540    uint64_t bestValue = UINT64_MAX;
541    uint32_t firstStep = std::max(uint32_t(hashNum>>2), 1U);
542    uint64_t maxSteps = (uint64_t(hashNum)<<1) - (firstStep) + 1;
543    const uint32_t steps = (maxSteps<=1000U) ? hashNum : hashNum<<((32-CLZ32(hashNum))>>1);
544   
545    std::unique_ptr<uint32_t[]> chainLengths(new uint32_t[(hashNum<<2)+1]);
546    const uint32_t stepSize = maxSteps / steps;
547    for (uint32_t buckets = firstStep; buckets <= (hashNum<<1); buckets += stepSize)
548    {   //
549        std::fill(chainLengths.get(), chainLengths.get() + buckets, 0U);
550        // calculate chain lengths
551        for (size_t i = skipFirst; i < hashNum; i++)
552            chainLengths[hashCodes[i] % buckets]++;
553        /// value, smaller is better
554        uint64_t value = uint64_t(buckets);
555        for (uint32_t i = 0; i < buckets; i++)
556            value += chainLengths[i]*chainLengths[i];
557        if (value < bestValue)
558        {
559            bestBucketNum = buckets;
560            bestValue = value;
561        }
562    }
563    return bestBucketNum;
564}
565
566static void createHashTable(uint32_t bucketsNum, uint32_t hashNum, bool skipFirst,
567                           const uint32_t* hashCodes, uint32_t* output)
568{
569    SULEV(output[0], bucketsNum);
570    SULEV(output[1], hashNum);
571    uint32_t* buckets = output + 2;
572    uint32_t* chains = output + bucketsNum + 2;
573    std::fill(buckets, buckets + bucketsNum, 0U);
574    std::fill(chains, chains + hashNum, STN_UNDEF);
575   
576    std::unique_ptr<uint32_t[]> lastNodes(new uint32_t[bucketsNum]);
577    std::fill(lastNodes.get(), lastNodes.get() + bucketsNum, UINT32_MAX);
578    for (uint32_t i = skipFirst; i < hashNum; i++)
579    {
580        const uint32_t bucket = hashCodes[i] % bucketsNum;
581        if (lastNodes[bucket] == UINT32_MAX)
582        {   // first entry of chain
583            SULEV(buckets[bucket], i);
584            lastNodes[bucket] = i;
585        }
586        else
587        {
588            SULEV(chains[lastNodes[bucket]], i);
589            lastNodes[bucket] = i;
590        }
591    }
592}
593
594template<typename Types>
595void ElfBinaryGenTemplate<Types>::generate(FastOutputBuffer& fob)
596{
597    computeSize();
598    const uint64_t startOffset = fob.getWritten();
599    /* write elf header */
600    {
601        typename Types::Ehdr ehdr;
602        ::memset(ehdr.e_ident, 0, EI_NIDENT);
603        ehdr.e_ident[0] = 0x7f;
604        ehdr.e_ident[1] = 'E';
605        ehdr.e_ident[2] = 'L';
606        ehdr.e_ident[3] = 'F';
607        ehdr.e_ident[4] = Types::ELFCLASS;
608        ehdr.e_ident[5] = ELFDATA2LSB;
609        ehdr.e_ident[6] = EV_CURRENT;
610        ehdr.e_ident[EI_OSABI] = header.osABI;
611        ehdr.e_ident[EI_ABIVERSION] = header.abiVersion;
612        SLEV(ehdr.e_type, header.type);
613        SLEV(ehdr.e_machine, header.machine);
614        SLEV(ehdr.e_version, header.version);
615        SLEV(ehdr.e_flags, header.flags);
616        if (header.entryRegion != UINT_MAX)
617        {   // if have entry
618            typename Types::Word entry = regionOffsets[header.entryRegion] + header.entry;
619            if (regions[header.entryRegion].type == ElfRegionType::SECTION &&
620                regions[header.entryRegion].section.addrBase != 0)
621                entry += regions[header.entryRegion].section.addrBase;
622            else
623                entry += header.vaddrBase;
624           
625            SLEV(ehdr.e_entry, entry);
626        }
627        else
628            SLEV(ehdr.e_entry, 0);
629        SLEV(ehdr.e_ehsize, sizeof(typename Types::Ehdr));
630        if (!progHeaders.empty())
631        {
632            SLEV(ehdr.e_phentsize, sizeof(typename Types::Phdr));
633            SLEV(ehdr.e_phoff, regionOffsets[phdrTabRegion]);
634        }
635        else
636        {
637            SLEV(ehdr.e_phentsize, 0);
638            SLEV(ehdr.e_phoff, 0);
639        }
640        SLEV(ehdr.e_phnum, progHeaders.size());
641        SLEV(ehdr.e_shentsize, sizeof(typename Types::Shdr));
642        SLEV(ehdr.e_shnum, sectionsNum);
643        SLEV(ehdr.e_shoff, regionOffsets[shdrTabRegion]);
644        SLEV(ehdr.e_shstrndx, shStrTab);
645       
646        fob.writeObject(ehdr);
647    }
648   
649    size_t nullSymNameOffset = 0;
650    // if addNullSym is not set, then no empty symbol name added, then we
651    // find first null character
652    if (!addNullSym && !symbols.empty())
653        nullSymNameOffset = ::strlen(symbols[0].name);
654    size_t nullDynSymNameOffset = 0;
655    // if addNullDynSym is not set, then no empty dynamic symbol name added, then we
656    // find first null character
657    if (!addNullDynSym && !dynSymbols.empty())
658        nullDynSymNameOffset = ::strlen(dynSymbols[0].name);
659    // if addNullSection is not set, then no empty section name added, then we
660    // find first null character
661    size_t nullSectionNameOffset = 0;
662    if (!addNullSection)
663    {
664        for (const ElfRegionTemplate<Types>& reg: regions)
665            if (reg.type == ElfRegionType::SECTION)
666            {
667                nullSectionNameOffset = ::strlen(reg.section.name);
668                break;
669            }
670    }
671   
672    /* write regions */
673    for (size_t i = 0; i < regions.size(); i++)
674    {   
675        const ElfRegionTemplate<Types>& region = regions[i];
676        // fix alignment
677        uint64_t toFill = 0;
678        typename Types::Word ralign = (region.type==ElfRegionType::SECTION) ?
679                        region.section.align : 0;
680        ralign = std::max(region.align, ralign);
681        if (ralign > 1)
682        {
683            const uint64_t curOffset = (fob.getWritten()-startOffset);
684            if (ralign!=0 && (curOffset&(ralign-1))!=0)
685                toFill = ralign - (curOffset&(ralign-1));
686            fob.fill(toFill, 0);
687        }
688        assert(regionOffsets[i] == fob.getWritten()-startOffset);
689       
690        // write content
691        if (region.type == ElfRegionType::PHDR_TABLE)
692        {   /* write program headers */
693            for (const auto& progHeader: progHeaders)
694            {
695                typename Types::Phdr phdr;
696                SLEV(phdr.p_type, progHeader.type);
697                SLEV(phdr.p_flags, progHeader.flags);
698                const ElfRegionTemplate<Types>& sregion = regions[progHeader.regionStart];
699                bool zeroOffset = sregion.type == ElfRegionType::SECTION &&
700                        sregion.section.zeroOffset;
701                SLEV(phdr.p_offset, !zeroOffset ?
702                        regionOffsets[progHeader.regionStart] : 0);
703                typename Types::Word align = (sregion.type==ElfRegionType::SECTION) ?
704                        sregion.section.align : 0;
705                align = std::max(sregion.align, align);
706                SLEV(phdr.p_align, align);
707               
708                /* paddrBase and vaddrBase is base to program header virtual and physical
709                 * addresses for program header. if not defined then get address base
710                 * from ELF header */
711                if (progHeader.paddrBase == Types::nobase)
712                    SLEV(phdr.p_paddr, regionAddresses[progHeader.regionStart]);
713                else if (progHeader.paddrBase != 0)
714                    SLEV(phdr.p_paddr, progHeader.paddrBase +
715                                regionAddresses[progHeader.regionStart]);
716                else if (header.paddrBase != 0)
717                    SLEV(phdr.p_paddr, header.paddrBase +
718                                regionAddresses[progHeader.regionStart]);
719                else
720                    SLEV(phdr.p_paddr, 0);
721               
722                if (progHeader.vaddrBase == Types::nobase)
723                    SLEV(phdr.p_vaddr, regionAddresses[progHeader.regionStart]);
724                else if (progHeader.vaddrBase != 0)
725                    SLEV(phdr.p_vaddr, progHeader.vaddrBase +
726                                regionAddresses[progHeader.regionStart]);
727                else if (header.vaddrBase != 0)
728                    SLEV(phdr.p_vaddr, header.vaddrBase +
729                                regionAddresses[progHeader.regionStart]);
730                else
731                    SLEV(phdr.p_vaddr, 0);
732               
733                // last region size for file - if nobits section then we assume zero size
734                const auto& lastReg = regions[progHeader.regionStart+
735                            progHeader.regionsNum-1];
736                uint64_t fileLastRegSize =(lastReg.type!=ElfRegionType::SECTION ||
737                    lastReg.section.type!=SHT_NOBITS) ? lastReg.size : 0;
738                /// fileSize - add offset of first region to simulate region alignment
739                const typename Types::Word fileSize = regionOffsets[progHeader.regionStart+
740                        progHeader.regionsNum-1] + fileLastRegSize -
741                        regionOffsets[progHeader.regionStart];
742                const typename Types::Word phSize = regionAddresses[progHeader.regionStart+
743                        progHeader.regionsNum-1]+regions[progHeader.regionStart+
744                        progHeader.regionsNum-1].size -
745                        regionAddresses[progHeader.regionStart];
746                SLEV(phdr.p_filesz, phSize);
747               
748                if (progHeader.haveMemSize)
749                {
750                    if (progHeader.memSize != 0)
751                        SLEV(phdr.p_memsz, progHeader.memSize);
752                    else
753                        SLEV(phdr.p_memsz, phSize);
754                }
755                else
756                    SLEV(phdr.p_memsz, 0);
757                SLEV(phdr.p_filesz, fileSize);
758                fob.writeObject(phdr);
759            }
760        }
761        else if (region.type == ElfRegionType::SHDR_TABLE)
762        {   /* write section headers table */
763            if (addNullSection)
764                fob.fill(sizeof(typename Types::Shdr), 0);
765            uint32_t nameOffset = (addNullSection);
766            for (cxuint j = 0; j < regions.size(); j++)
767            {
768                const auto& region2 = regions[j];
769                if (region2.type == ElfRegionType::SECTION)
770                {
771                    typename Types::Shdr shdr;
772                    if (region2.section.name!=nullptr && region2.section.name[0]!=0)
773                        SLEV(shdr.sh_name, nameOffset);
774                    else // set empty name offset
775                        SLEV(shdr.sh_name, nullSectionNameOffset);
776                    SLEV(shdr.sh_type, region2.section.type);
777                    SLEV(shdr.sh_flags, region2.section.flags);
778                    SLEV(shdr.sh_offset, (!region2.section.zeroOffset) ?
779                                regionOffsets[j] : 0);
780                    /* addrBase is base address of first section. if not defined
781                     * use address base as virtual address base from elf header */
782                    if (region2.section.addrBase==Types::nobase)
783                        SLEV(shdr.sh_addr, regionAddresses[j]);
784                    else if (region2.section.addrBase != 0)
785                        SLEV(shdr.sh_addr, region2.section.addrBase+regionAddresses[j]);
786                    else if (header.vaddrBase != 0)
787                        SLEV(shdr.sh_addr, header.vaddrBase+regionAddresses[j]);
788                    else
789                        SLEV(shdr.sh_addr, 0);
790                   
791                    if (region2.align != 0 || j+1 >= regions.size() ||
792                        regionOffsets[j]+region2.size == regionOffsets[j+1])
793                        SLEV(shdr.sh_size, region2.size);
794                    else
795                        SLEV(shdr.sh_size, regionOffsets[j+1]-regionOffsets[j]);
796                    SLEV(shdr.sh_info, region2.section.info);
797                    SLEV(shdr.sh_addralign, region2.align);
798                    if (region2.section.link == 0)
799                    {
800                        if (::strcmp(region2.section.name, ".symtab") == 0)
801                            SLEV(shdr.sh_link, strTab);
802                        else if (::strcmp(region2.section.name, ".dynsym") == 0)
803                            SLEV(shdr.sh_link, dynStr);
804                        else
805                            SLEV(shdr.sh_link, region2.section.link);
806                    }
807                    else
808                        SLEV(shdr.sh_link, region2.section.link);
809                   
810                    if (region2.section.type == SHT_SYMTAB ||
811                        region2.section.type == SHT_DYNSYM)
812                        SLEV(shdr.sh_entsize, sizeof(typename Types::Sym));
813                    else
814                        SLEV(shdr.sh_entsize, region2.section.entSize);
815                    if (region2.section.name!=nullptr && region2.section.name[0]!=0)
816                        nameOffset += ::strlen(region2.section.name)+1;
817                    fob.writeObject(shdr);
818                }
819            }
820        }
821        else if (region.type == ElfRegionType::USER)
822        {
823            if (region.dataFromPointer)
824                fob.writeArray(region.size, region.data);
825            else
826                (*region.dataGen)(fob);
827        }
828        else if (region.type == ElfRegionType::SECTION)
829        {
830            if (region.data == nullptr)
831            {
832                if (region.section.type == SHT_SYMTAB || region.section.type == SHT_DYNSYM)
833                {
834                    uint32_t nameOffset = 0;
835                    if (region.section.type == SHT_SYMTAB && addNullSym)
836                    {
837                        fob.fill(sizeof(typename Types::Sym), 0);
838                        nameOffset = 1;
839                    }
840                    if (region.section.type == SHT_DYNSYM && addNullDynSym)
841                    {
842                        fob.fill(sizeof(typename Types::Sym), 0);
843                        nameOffset = 1;
844                    }
845                    const auto& symbolsList = (region.section.type == SHT_SYMTAB) ?
846                            symbols : dynSymbols;
847                    for (const auto& inSym: symbolsList)
848                    {
849                        typename Types::Sym sym;
850                        if (inSym.name != nullptr && inSym.name[0] != 0)
851                            SLEV(sym.st_name, nameOffset);
852                        else  // set empty name offset (symbol or dynamic symbol)
853                            SLEV(sym.st_name, (region.section.type == SHT_SYMTAB) ?
854                                        nullSymNameOffset : nullDynSymNameOffset);
855                       
856                        SLEV(sym.st_shndx, inSym.sectionIndex);
857                        SLEV(sym.st_size, inSym.size);
858                        /// if value defined as address
859                        if (!inSym.valueIsAddr)
860                            SLEV(sym.st_value, inSym.value);
861                        // if not use conversion to address with section addrBase
862                        else if (inSym.sectionIndex != 0 && regions[sectionRegions[
863                                    inSym.sectionIndex]].section.addrBase != 0)
864                            SLEV(sym.st_value, inSym.value + regionOffsets[
865                                    sectionRegions[inSym.sectionIndex]] +
866                                    regions[sectionRegions[inSym.sectionIndex]].
867                                            section.addrBase);
868                        else // use elf headerf virtual address base
869                            SLEV(sym.st_value, inSym.value + regionOffsets[
870                                sectionRegions[inSym.sectionIndex]] + header.vaddrBase);
871                        sym.st_other = inSym.other;
872                        sym.st_info = inSym.info;
873                        if (inSym.name != nullptr && inSym.name[0] != 0)
874                            nameOffset += ::strlen(inSym.name)+1;
875                        fob.writeObject(sym);
876                    }
877                }
878                else if (region.section.type == SHT_HASH)
879                {
880                    if (::strcmp(region.section.name, ".hash") != 0)
881                        continue;
882                }
883                else if (region.section.type == SHT_STRTAB)
884                {
885                    if (::strcmp(region.section.name, ".strtab") == 0)
886                    {
887                        if (addNullSym)
888                            fob.put(0);
889                        for (const auto& sym: symbols)
890                            if (sym.name != nullptr && sym.name[0] != 0)
891                                fob.write(::strlen(sym.name)+1, sym.name);
892                    }
893                    else if (::strcmp(region.section.name, ".dynstr") == 0)
894                    {
895                        if (addNullDynSym)
896                            fob.put(0);
897                        for (const auto& sym: dynSymbols)
898                            if (sym.name != nullptr && sym.name[0] != 0)
899                                fob.write(::strlen(sym.name)+1, sym.name);
900                    }
901                    else if (::strcmp(region.section.name, ".shstrtab") == 0)
902                    {
903                        if (addNullSection)
904                            fob.put(0);
905                        for (const auto& region2: regions)
906                            if (region2.type == ElfRegionType::SECTION &&
907                                region2.section.name != nullptr &&
908                                region2.section.name[0] != 0)
909                                fob.write(::strlen(region2.section.name)+1,
910                                          region2.section.name);
911                    }
912                }
913            }
914            else if (region.section.type != SHT_NOBITS)
915            {
916                if (region.dataFromPointer)
917                    fob.writeArray(region.size, region.data);
918                else
919                    (*region.dataGen)(fob);
920            }
921        }
922    }
923    fob.flush();
924    fob.getOStream().flush();
925    assert(size == fob.getWritten()-startOffset);
926}
927
928template class CLRX::ElfBinaryGenTemplate<CLRX::Elf32Types>;
929template class CLRX::ElfBinaryGenTemplate<CLRX::Elf64Types>;
Note: See TracBrowser for help on using the repository browser.