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

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

CLRadeonExtender: ElfBinaries?. Add routine to create hash table. small fixes in hash 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, const uint32_t* hashCodes)
537{
538    uint32_t bestBucketNum = 0;
539    uint64_t bestValue = UINT64_MAX;
540    uint32_t firstStep = std::max(uint32_t(hashNum>>2), 1U);
541    uint64_t maxSteps = (uint64_t(hashNum)<<1) - (firstStep) + 1;
542    const uint32_t steps = (maxSteps<=1000U) ? hashNum : hashNum<<((32-CLZ32(hashNum))>>1);
543   
544    std::unique_ptr<uint32_t[]> chainLengths(new uint32_t[(hashNum<<2)+1]);
545    const uint32_t stepSize = maxSteps / steps;
546    for (uint32_t buckets = firstStep; buckets <= (hashNum<<1); buckets += stepSize)
547    {   //
548        std::fill(chainLengths.get(), chainLengths.get() + buckets, 0U);
549        // calculate chain lengths
550        for (size_t i = 0; i < hashNum; i++)
551            chainLengths[hashCodes[i] % buckets]++;
552        /// value, smaller is better
553        uint64_t value = uint64_t(buckets);
554        for (uint32_t i = 0; i < buckets; i++)
555            value += chainLengths[i]*chainLengths[i];
556        if (value < bestValue)
557        {
558            bestBucketNum = buckets;
559            bestValue = value;
560        }
561    }
562    return bestBucketNum;
563}
564
565static void createHashTable(uint32_t bucketsNum, uint32_t hashNum,
566                           const uint32_t* hashCodes, uint32_t* output)
567{
568    SULEV(output[0], bucketsNum);
569    SULEV(output[1], hashNum);
570    uint32_t* buckets = output + 2;
571    uint32_t* chains = output + bucketsNum + 2;
572    std::fill(buckets, buckets + bucketsNum, 0U);
573    std::fill(chains, chains + hashNum, STN_UNDEF);
574   
575    std::unique_ptr<uint32_t[]> lastNodes(new uint32_t[bucketsNum]);
576    std::fill(lastNodes.get(), lastNodes.get() + bucketsNum, UINT32_MAX);
577    for (uint32_t i = 0; i < hashNum; i++)
578    {
579        const uint32_t bucket = hashCodes[i] % bucketsNum;
580        if (lastNodes[bucket] == UINT32_MAX)
581        {   // first entry of chain
582            SULEV(buckets[bucket], i);
583            lastNodes[bucket] = i;
584        }
585        else
586        {
587            chains[lastNodes[bucket]] = i;
588            lastNodes[bucket] = i;
589        }
590    }
591}
592
593template<typename Types>
594void ElfBinaryGenTemplate<Types>::generate(FastOutputBuffer& fob)
595{
596    computeSize();
597    const uint64_t startOffset = fob.getWritten();
598    /* write elf header */
599    {
600        typename Types::Ehdr ehdr;
601        ::memset(ehdr.e_ident, 0, EI_NIDENT);
602        ehdr.e_ident[0] = 0x7f;
603        ehdr.e_ident[1] = 'E';
604        ehdr.e_ident[2] = 'L';
605        ehdr.e_ident[3] = 'F';
606        ehdr.e_ident[4] = Types::ELFCLASS;
607        ehdr.e_ident[5] = ELFDATA2LSB;
608        ehdr.e_ident[6] = EV_CURRENT;
609        ehdr.e_ident[EI_OSABI] = header.osABI;
610        ehdr.e_ident[EI_ABIVERSION] = header.abiVersion;
611        SLEV(ehdr.e_type, header.type);
612        SLEV(ehdr.e_machine, header.machine);
613        SLEV(ehdr.e_version, header.version);
614        SLEV(ehdr.e_flags, header.flags);
615        if (header.entryRegion != UINT_MAX)
616        {   // if have entry
617            typename Types::Word entry = regionOffsets[header.entryRegion] + header.entry;
618            if (regions[header.entryRegion].type == ElfRegionType::SECTION &&
619                regions[header.entryRegion].section.addrBase != 0)
620                entry += regions[header.entryRegion].section.addrBase;
621            else
622                entry += header.vaddrBase;
623           
624            SLEV(ehdr.e_entry, entry);
625        }
626        else
627            SLEV(ehdr.e_entry, 0);
628        SLEV(ehdr.e_ehsize, sizeof(typename Types::Ehdr));
629        if (!progHeaders.empty())
630        {
631            SLEV(ehdr.e_phentsize, sizeof(typename Types::Phdr));
632            SLEV(ehdr.e_phoff, regionOffsets[phdrTabRegion]);
633        }
634        else
635        {
636            SLEV(ehdr.e_phentsize, 0);
637            SLEV(ehdr.e_phoff, 0);
638        }
639        SLEV(ehdr.e_phnum, progHeaders.size());
640        SLEV(ehdr.e_shentsize, sizeof(typename Types::Shdr));
641        SLEV(ehdr.e_shnum, sectionsNum);
642        SLEV(ehdr.e_shoff, regionOffsets[shdrTabRegion]);
643        SLEV(ehdr.e_shstrndx, shStrTab);
644       
645        fob.writeObject(ehdr);
646    }
647   
648    size_t nullSymNameOffset = 0;
649    // if addNullSym is not set, then no empty symbol name added, then we
650    // find first null character
651    if (!addNullSym && !symbols.empty())
652        nullSymNameOffset = ::strlen(symbols[0].name);
653    size_t nullDynSymNameOffset = 0;
654    // if addNullDynSym is not set, then no empty dynamic symbol name added, then we
655    // find first null character
656    if (!addNullDynSym && !dynSymbols.empty())
657        nullDynSymNameOffset = ::strlen(dynSymbols[0].name);
658    // if addNullSection is not set, then no empty section name added, then we
659    // find first null character
660    size_t nullSectionNameOffset = 0;
661    if (!addNullSection)
662    {
663        for (const ElfRegionTemplate<Types>& reg: regions)
664            if (reg.type == ElfRegionType::SECTION)
665            {
666                nullSectionNameOffset = ::strlen(reg.section.name);
667                break;
668            }
669    }
670   
671    /* write regions */
672    for (size_t i = 0; i < regions.size(); i++)
673    {   
674        const ElfRegionTemplate<Types>& region = regions[i];
675        // fix alignment
676        uint64_t toFill = 0;
677        typename Types::Word ralign = (region.type==ElfRegionType::SECTION) ?
678                        region.section.align : 0;
679        ralign = std::max(region.align, ralign);
680        if (ralign > 1)
681        {
682            const uint64_t curOffset = (fob.getWritten()-startOffset);
683            if (ralign!=0 && (curOffset&(ralign-1))!=0)
684                toFill = ralign - (curOffset&(ralign-1));
685            fob.fill(toFill, 0);
686        }
687        assert(regionOffsets[i] == fob.getWritten()-startOffset);
688       
689        // write content
690        if (region.type == ElfRegionType::PHDR_TABLE)
691        {   /* write program headers */
692            for (const auto& progHeader: progHeaders)
693            {
694                typename Types::Phdr phdr;
695                SLEV(phdr.p_type, progHeader.type);
696                SLEV(phdr.p_flags, progHeader.flags);
697                const ElfRegionTemplate<Types>& sregion = regions[progHeader.regionStart];
698                bool zeroOffset = sregion.type == ElfRegionType::SECTION &&
699                        sregion.section.zeroOffset;
700                SLEV(phdr.p_offset, !zeroOffset ?
701                        regionOffsets[progHeader.regionStart] : 0);
702                typename Types::Word align = (sregion.type==ElfRegionType::SECTION) ?
703                        sregion.section.align : 0;
704                align = std::max(sregion.align, align);
705                SLEV(phdr.p_align, align);
706               
707                /* paddrBase and vaddrBase is base to program header virtual and physical
708                 * addresses for program header. if not defined then get address base
709                 * from ELF header */
710                if (progHeader.paddrBase == Types::nobase)
711                    SLEV(phdr.p_paddr, regionAddresses[progHeader.regionStart]);
712                else if (progHeader.paddrBase != 0)
713                    SLEV(phdr.p_paddr, progHeader.paddrBase +
714                                regionAddresses[progHeader.regionStart]);
715                else if (header.paddrBase != 0)
716                    SLEV(phdr.p_paddr, header.paddrBase +
717                                regionAddresses[progHeader.regionStart]);
718                else
719                    SLEV(phdr.p_paddr, 0);
720               
721                if (progHeader.vaddrBase == Types::nobase)
722                    SLEV(phdr.p_vaddr, regionAddresses[progHeader.regionStart]);
723                else if (progHeader.vaddrBase != 0)
724                    SLEV(phdr.p_vaddr, progHeader.vaddrBase +
725                                regionAddresses[progHeader.regionStart]);
726                else if (header.vaddrBase != 0)
727                    SLEV(phdr.p_vaddr, header.vaddrBase +
728                                regionAddresses[progHeader.regionStart]);
729                else
730                    SLEV(phdr.p_vaddr, 0);
731               
732                // last region size for file - if nobits section then we assume zero size
733                const auto& lastReg = regions[progHeader.regionStart+
734                            progHeader.regionsNum-1];
735                uint64_t fileLastRegSize =(lastReg.type!=ElfRegionType::SECTION ||
736                    lastReg.section.type!=SHT_NOBITS) ? lastReg.size : 0;
737                /// fileSize - add offset of first region to simulate region alignment
738                const typename Types::Word fileSize = regionOffsets[progHeader.regionStart+
739                        progHeader.regionsNum-1] + fileLastRegSize -
740                        regionOffsets[progHeader.regionStart];
741                const typename Types::Word phSize = regionAddresses[progHeader.regionStart+
742                        progHeader.regionsNum-1]+regions[progHeader.regionStart+
743                        progHeader.regionsNum-1].size -
744                        regionAddresses[progHeader.regionStart];
745                SLEV(phdr.p_filesz, phSize);
746               
747                if (progHeader.haveMemSize)
748                {
749                    if (progHeader.memSize != 0)
750                        SLEV(phdr.p_memsz, progHeader.memSize);
751                    else
752                        SLEV(phdr.p_memsz, phSize);
753                }
754                else
755                    SLEV(phdr.p_memsz, 0);
756                SLEV(phdr.p_filesz, fileSize);
757                fob.writeObject(phdr);
758            }
759        }
760        else if (region.type == ElfRegionType::SHDR_TABLE)
761        {   /* write section headers table */
762            if (addNullSection)
763                fob.fill(sizeof(typename Types::Shdr), 0);
764            uint32_t nameOffset = (addNullSection);
765            for (cxuint j = 0; j < regions.size(); j++)
766            {
767                const auto& region2 = regions[j];
768                if (region2.type == ElfRegionType::SECTION)
769                {
770                    typename Types::Shdr shdr;
771                    if (region2.section.name!=nullptr && region2.section.name[0]!=0)
772                        SLEV(shdr.sh_name, nameOffset);
773                    else // set empty name offset
774                        SLEV(shdr.sh_name, nullSectionNameOffset);
775                    SLEV(shdr.sh_type, region2.section.type);
776                    SLEV(shdr.sh_flags, region2.section.flags);
777                    SLEV(shdr.sh_offset, (!region2.section.zeroOffset) ?
778                                regionOffsets[j] : 0);
779                    /* addrBase is base address of first section. if not defined
780                     * use address base as virtual address base from elf header */
781                    if (region2.section.addrBase==Types::nobase)
782                        SLEV(shdr.sh_addr, regionAddresses[j]);
783                    else if (region2.section.addrBase != 0)
784                        SLEV(shdr.sh_addr, region2.section.addrBase+regionAddresses[j]);
785                    else if (header.vaddrBase != 0)
786                        SLEV(shdr.sh_addr, header.vaddrBase+regionAddresses[j]);
787                    else
788                        SLEV(shdr.sh_addr, 0);
789                   
790                    if (region2.align != 0 || j+1 >= regions.size() ||
791                        regionOffsets[j]+region2.size == regionOffsets[j+1])
792                        SLEV(shdr.sh_size, region2.size);
793                    else
794                        SLEV(shdr.sh_size, regionOffsets[j+1]-regionOffsets[j]);
795                    SLEV(shdr.sh_info, region2.section.info);
796                    SLEV(shdr.sh_addralign, region2.align);
797                    if (region2.section.link == 0)
798                    {
799                        if (::strcmp(region2.section.name, ".symtab") == 0)
800                            SLEV(shdr.sh_link, strTab);
801                        else if (::strcmp(region2.section.name, ".dynsym") == 0)
802                            SLEV(shdr.sh_link, dynStr);
803                        else
804                            SLEV(shdr.sh_link, region2.section.link);
805                    }
806                    else
807                        SLEV(shdr.sh_link, region2.section.link);
808                   
809                    if (region2.section.type == SHT_SYMTAB ||
810                        region2.section.type == SHT_DYNSYM)
811                        SLEV(shdr.sh_entsize, sizeof(typename Types::Sym));
812                    else
813                        SLEV(shdr.sh_entsize, region2.section.entSize);
814                    if (region2.section.name!=nullptr && region2.section.name[0]!=0)
815                        nameOffset += ::strlen(region2.section.name)+1;
816                    fob.writeObject(shdr);
817                }
818            }
819        }
820        else if (region.type == ElfRegionType::USER)
821        {
822            if (region.dataFromPointer)
823                fob.writeArray(region.size, region.data);
824            else
825                (*region.dataGen)(fob);
826        }
827        else if (region.type == ElfRegionType::SECTION)
828        {
829            if (region.data == nullptr)
830            {
831                if (region.section.type == SHT_SYMTAB || region.section.type == SHT_DYNSYM)
832                {
833                    uint32_t nameOffset = 0;
834                    if (region.section.type == SHT_SYMTAB && addNullSym)
835                    {
836                        fob.fill(sizeof(typename Types::Sym), 0);
837                        nameOffset = 1;
838                    }
839                    if (region.section.type == SHT_DYNSYM && addNullDynSym)
840                    {
841                        fob.fill(sizeof(typename Types::Sym), 0);
842                        nameOffset = 1;
843                    }
844                    const auto& symbolsList = (region.section.type == SHT_SYMTAB) ?
845                            symbols : dynSymbols;
846                    for (const auto& inSym: symbolsList)
847                    {
848                        typename Types::Sym sym;
849                        if (inSym.name != nullptr && inSym.name[0] != 0)
850                            SLEV(sym.st_name, nameOffset);
851                        else  // set empty name offset (symbol or dynamic symbol)
852                            SLEV(sym.st_name, (region.section.type == SHT_SYMTAB) ?
853                                        nullSymNameOffset : nullDynSymNameOffset);
854                       
855                        SLEV(sym.st_shndx, inSym.sectionIndex);
856                        SLEV(sym.st_size, inSym.size);
857                        /// if value defined as address
858                        if (!inSym.valueIsAddr)
859                            SLEV(sym.st_value, inSym.value);
860                        // if not use conversion to address with section addrBase
861                        else if (inSym.sectionIndex != 0 && regions[sectionRegions[
862                                    inSym.sectionIndex]].section.addrBase != 0)
863                            SLEV(sym.st_value, inSym.value + regionOffsets[
864                                    sectionRegions[inSym.sectionIndex]] +
865                                    regions[sectionRegions[inSym.sectionIndex]].
866                                            section.addrBase);
867                        else // use elf headerf virtual address base
868                            SLEV(sym.st_value, inSym.value + regionOffsets[
869                                sectionRegions[inSym.sectionIndex]] + header.vaddrBase);
870                        sym.st_other = inSym.other;
871                        sym.st_info = inSym.info;
872                        if (inSym.name != nullptr && inSym.name[0] != 0)
873                            nameOffset += ::strlen(inSym.name)+1;
874                        fob.writeObject(sym);
875                    }
876                }
877                else if (region.section.type == SHT_HASH)
878                {
879                    if (::strcmp(region.section.name, ".hash") != 0)
880                        continue;
881                }
882                else if (region.section.type == SHT_STRTAB)
883                {
884                    if (::strcmp(region.section.name, ".strtab") == 0)
885                    {
886                        if (addNullSym)
887                            fob.put(0);
888                        for (const auto& sym: symbols)
889                            if (sym.name != nullptr && sym.name[0] != 0)
890                                fob.write(::strlen(sym.name)+1, sym.name);
891                    }
892                    else if (::strcmp(region.section.name, ".dynstr") == 0)
893                    {
894                        if (addNullDynSym)
895                            fob.put(0);
896                        for (const auto& sym: dynSymbols)
897                            if (sym.name != nullptr && sym.name[0] != 0)
898                                fob.write(::strlen(sym.name)+1, sym.name);
899                    }
900                    else if (::strcmp(region.section.name, ".shstrtab") == 0)
901                    {
902                        if (addNullSection)
903                            fob.put(0);
904                        for (const auto& region2: regions)
905                            if (region2.type == ElfRegionType::SECTION &&
906                                region2.section.name != nullptr &&
907                                region2.section.name[0] != 0)
908                                fob.write(::strlen(region2.section.name)+1,
909                                          region2.section.name);
910                    }
911                }
912            }
913            else if (region.section.type != SHT_NOBITS)
914            {
915                if (region.dataFromPointer)
916                    fob.writeArray(region.size, region.data);
917                else
918                    (*region.dataGen)(fob);
919            }
920        }
921    }
922    fob.flush();
923    fob.getOStream().flush();
924    assert(size == fob.getWritten()-startOffset);
925}
926
927template class CLRX::ElfBinaryGenTemplate<CLRX::Elf32Types>;
928template class CLRX::ElfBinaryGenTemplate<CLRX::Elf64Types>;
Note: See TracBrowser for help on using the repository browser.