Bold/linker.py

   1 # -*- coding: utf-8 -*-
   2 # kate: space-indent on; indent-width 2; mixedindent off; indent-mode python;
   3
   4 # Copyright (C) 2009 Amand 'alrj' Tihon <amand.tihon@alrj.org>
   5 #
   6 # This file is part of bold, the Byte Optimized Linker.
   7 #
   8 # You can redistribute this file and/or modify it under the terms of the
   9 # GNU General Public License as published by the Free Software Foundation,
  10 # either version 3 of the License or (at your option) any later version.
  11
  12 """
  13 Main entry point for the bold linker.
  14 """
  15
  16 from constants import *
  17 from BinArray import BinArray
  18 from elf import Elf64, Elf64_Phdr, Elf64_Shdr, TextSegment, DataSegment
  19 from elf import SStrtab, SSymtab, SProgBits, SNobits, Dynamic, Interpreter
  20 from errors import *
  21 from ctypes.util import find_library
  22 import struct
  23
  24
  25 def hash_name(name):
  26   """Caculate the hash of the function name.
  27   @param name: the string to hash
  28   @return: 32 bits hash value.
  29   """
  30   h = 0
  31   for c in name:
  32     h = ((h * 0x21) ^ ord(c)) & 0xffffffff
  33   return h
  34
  35
  36 class BoldLinker(object):
  37   """A Linker object takes one or more objects files, optional shared libs,
  38   and arranges all this in an executable.
  39   """
  40
  41   def __init__(self):
  42     object.__init__(self)
  43
  44     self.objs = []
  45     self.shlibs = []
  46     self.entry_point = "_start"
  47     self.output = Elf64()
  48     self.global_symbols = {}
  49     self.undefined_symbols = set()
  50
  51
  52   def add_object(self, filename):
  53     """Add a relocatable file as input.
  54     @param filename: path to relocatable object file to add
  55     """
  56     obj = Elf64(filename)
  57     obj.resolve_names()
  58     obj.find_symbols()
  59     self.objs.append(obj)
  60
  61
  62   def build_symbols_tables(self):
  63     """Find out the globally available symbols, as well as the globally
  64     undefined ones (which should be found in external libraries."""
  65
  66     # Gather the "extern" symbols from each input files.
  67     for i in self.objs:
  68       self.undefined_symbols.update(i.undefined_symbols)
  69
  70     # Make a dict with all the symbols declared globally.
  71     # Key is the symbol name, value will later be set to the final
  72     # virtual address. Currently, we're only interrested in the declaration.
  73     # The virtual addresses are set to None, they'll be resolved later.
  74     for i in self.objs:
  75       for s in i.global_symbols:
  76         if s in self.global_symbols:
  77           raise RedefinedSymbol(s)
  78         self.global_symbols[s] = None
  79
  80     # Add a few useful symbols. They'll be resolved ater as well.
  81     self.global_symbols["_dt_debug"] = None
  82     self.global_symbols["_DYNAMIC"] = None
  83
  84     # Find out which symbols aren't really defined anywhere
  85     self.undefined_symbols.difference_update(self.global_symbols)
  86
  87
  88   def build_external(self, with_jump=False, align_jump=False):
  89     """
  90     Generate a fake relocatable object, for dynamic linking.
  91     This object is then automatically added in the list of ebjects to link.
  92     TODO: This part is extremely non-portable.
  93     """
  94
  95     # Find out all the undefined symbols. They're the one we'll need to resolve
  96     # dynamically.
  97     symbols = sorted(list(self.undefined_symbols))
  98
  99     # Those three will soon be known...
 100     symbols.remove('_bold__functions_count')
 101     symbols.remove('_bold__functions_hash')
 102     symbols.remove('_bold__functions_pointers')
 103
 104     # Create the fake ELF object.
 105     fo = Elf64() # Don't care about most parts of ELF header (?)
 106     fo.filename = "Internal dynamic linker"
 107
 108     # We need a .data section, a .bss section and a possibly a .text section
 109     data_shdr = Elf64_Shdr()
 110     data_shdr.sh_type = SHT_PROGBITS
 111     data_shdr.sh_flags = (SHF_WRITE | SHF_ALLOC)
 112     data_shdr.sh_size = len(symbols) * 4
 113     fmt = "<" + "I" * len(symbols)
 114     data_shdr.content = BinArray(struct.pack(fmt, *[hash_name(s) for s in symbols]))
 115     fo.shdrs.append(data_shdr)
 116     fo.sections['.data'] = data_shdr
 117
 118     bss_shdr = Elf64_Shdr()
 119     bss_shdr.sh_type = SHT_NOBITS
 120     bss_shdr.sh_flags = (SHF_WRITE | SHF_ALLOC)
 121     bss_shdr.sh_size = len(symbols) * 8
 122     bss_shdr.content = BinArray("")
 123     fo.shdrs.append(bss_shdr)
 124     fo.sections['.bss'] = bss_shdr
 125
 126     if with_jump:
 127       text_shdr = Elf64_Shdr()
 128       text_shdr.sh_type = SHT_PROGBITS
 129       text_shdr.sh_flags = (SHF_ALLOC | SHF_EXECINSTR)
 130       text_shdr.sh_size = len(symbols) * 8
 131       if align_jump:
 132         fmt = '\xff\x25\x00\x00\x00\x00\x00\x00' # ff 25 = jmp [rel label]
 133         jmp_size = 8
 134       else:
 135         fmt = '\xff\x25\x00\x00\x00\x00'
 136         jmp_size = 6
 137       text_shdr.content = BinArray(fmt * len(symbols))
 138       fo.shdrs.append(text_shdr)
 139       fo.sections['.text'] = text_shdr
 140
 141     # Cheating here. All symbols declared as global so we don't need to create
 142     # a symtab from scratch.
 143     fo.global_symbols = {}
 144     fo.global_symbols['_bold__functions_count'] = (SHN_ABS, len(symbols))
 145     fo.global_symbols['_bold__functions_hash'] = (data_shdr, 0)
 146     fo.global_symbols['_bold__functions_pointers'] = (bss_shdr, 0)
 147
 148     for n, i in enumerate(symbols):
 149       # The hash is always in .data
 150       h = "_bold__hash_%s" % i
 151       fo.global_symbols[h] = (data_shdr, n * 4) # Section, offset
 152
 153       if with_jump:
 154         # the symbol is in .text, can be called directly
 155         fo.global_symbols[i] = (text_shdr, n * jmp_size)
 156         # another symbol can be used to reference the pointer, just in case.
 157         p = "_bold__%s" % i
 158         fo.global_symbols[p] = (bss_shdr, n * 8)
 159
 160       else:
 161         # The symbol is in .bss, must be called indirectly
 162         fo.global_symbols[i] = (bss_shdr, n * 8)
 163
 164     if with_jump:
 165       # Add relocation entries for the jumps
 166       # Relocation will be done for the .text, for every jmp instruction.
 167       class dummy: pass
 168       rela_shdr = Elf64_Shdr()
 169       rela_shdr.sh_type = SHT_RELA
 170       rela_shdr.target = text_shdr
 171       rela_shdr.sh_flags = 0
 172       rela_shdr._content = dummy() # We only need a container for relatab...
 173       relatab = []                      # Prepare a relatab
 174       rela_shdr.content.relatab = relatab
 175
 176       for n, i in enumerate(symbols):
 177         # Create a relocation entry for each symbol
 178         reloc = dummy()
 179         reloc.r_offset = (n * jmp_size) + 2   # Beginning of the cell to update
 180         reloc.r_addend = -4
 181         reloc.r_type = R_X86_64_PC32
 182         reloc.symbol = dummy()
 183         reloc.symbol.st_shndx = SHN_UNDEF
 184         reloc.symbol.name = "_bold__%s" % i
 185         relatab.append(reloc)
 186       fo.shdrs.append(rela_shdr)
 187       fo.sections['.rela.text'] = rela_shdr
 188
 189     # Ok, let's add this fake object
 190     self.objs.append(fo)
 191
 192
 193   def add_shlib(self, libname):
 194     """Add a shared library to link against."""
 195     # Note : we use ctypes' find_library to find the real name
 196     fullname = find_library(libname)
 197     if not fullname:
 198       raise LibNotFound(libname)
 199     self.shlibs.append(fullname)
 200
 201
 202   def link(self):
 203     """Do the actual linking."""
 204     # Prepare two segments. One for .text, the other for .data + .bss
 205     self.text_segment = TextSegment()
 206     # .data will be mapped 0x100000 bytes further
 207     self.data_segment = DataSegment(align=0x100000)
 208     self.output.add_segment(self.text_segment)
 209     self.output.add_segment(self.data_segment)
 210
 211     # Adjust the ELF header
 212     self.output.header.e_ident.make_default_amd64()
 213     self.output.header.e_phoff = self.output.header.size
 214     self.output.header.e_type = ET_EXEC
 215     # Elf header lies inside .text
 216     self.text_segment.add_content(self.output.header)
 217
 218     # Create the four Program Headers. They'll be inside .text
 219     # The first Program Header defines .text
 220     ph_text = Elf64_Phdr()
 221     ph_text.p_type = PT_LOAD
 222     ph_text.p_align = 0x100000
 223     self.output.add_phdr(ph_text)
 224     self.text_segment.add_content(ph_text)
 225
 226     # Second one defines .data + .bss
 227     ph_data = Elf64_Phdr()
 228     ph_data.p_type = PT_LOAD
 229     ph_data.p_align = 0x100000
 230     self.output.add_phdr(ph_data)
 231     self.text_segment.add_content(ph_data)
 232
 233     # Third one is only there to define the DYNAMIC section
 234     ph_dynamic = Elf64_Phdr()
 235     ph_dynamic.p_type = PT_DYNAMIC
 236     self.output.add_phdr(ph_dynamic)
 237     self.text_segment.add_content(ph_dynamic)
 238
 239     # Fourth one is for interp
 240     ph_interp = Elf64_Phdr()
 241     ph_interp.p_type = PT_INTERP
 242     self.output.add_phdr(ph_interp)
 243     self.text_segment.add_content(ph_interp)
 244
 245     # We have all the needed program headers, update ELF header
 246     self.output.header.ph_num = len(self.output.phdrs)
 247
 248     # Create the actual content for the interpreter section
 249     interp = Interpreter()
 250     self.text_segment.add_content(interp)
 251
 252     # Then the Dynamic section
 253     dynamic = Dynamic()
 254     # for all the requested libs, add a reference in the Dynamic table
 255     for lib in self.shlibs:
 256       dynamic.add_shlib(lib)
 257     # Add an empty symtab, symbol resolution is not done.
 258     dynamic.add_symtab(0)
 259     # And we need a DT_DEBUG
 260     dynamic.add_debug()
 261
 262     # This belongs to .data
 263     self.data_segment.add_content(dynamic)
 264     # The dynamic table links to a string table for the libs' names.
 265     self.text_segment.add_content(dynamic.strtab)
 266
 267     # We can now add the interesting sections to the corresponding segments
 268     for i in self.objs:
 269       for sh in i.shdrs:
 270         # Only ALLOC sections are worth it.
 271         # This might require change in the future
 272         if not (sh.sh_flags & SHF_ALLOC):
 273           continue
 274
 275         if (sh.sh_flags & SHF_EXECINSTR):
 276           self.text_segment.add_content(sh.content)
 277         else: # No exec, it's for .data or .bss
 278           if (sh.sh_type == SHT_NOBITS):
 279             self.data_segment.add_nobits(sh.content)
 280           else:
 281             self.data_segment.add_content(sh.content)
 282
 283     # Now, everything is at its place.
 284     # Knowing the base address, we can determine where everyone will fall
 285     self.output.layout(base_vaddr=0x400000)
 286
 287     # Knowing the addresses of all the parts, Program Headers can be filled
 288     # This will put the correct p_offset, p_vaddr, p_filesz and p_memsz
 289     ph_text.update_from_content(self.text_segment)
 290     ph_data.update_from_content(self.data_segment)
 291     ph_interp.update_from_content(interp)
 292     ph_dynamic.update_from_content(dynamic)
 293
 294     # All parts are at their final address, find out the symbols' addresses
 295     for i in self.objs:
 296       for s in i.global_symbols:
 297         # Final address is the section's base address + the symbol's offset
 298         if i.global_symbols[s][0] == SHN_ABS:
 299           addr = i.global_symbols[s][1]
 300         else:
 301           addr = i.global_symbols[s][0].content.virt_addr
 302           addr += i.global_symbols[s][1]
 303
 304         self.global_symbols[s] = addr
 305
 306     # Resolve the few useful symbols
 307     self.global_symbols["_dt_debug"] = dynamic.dt_debug_address
 308     self.global_symbols["_DYNAMIC"] = dynamic.virt_addr
 309
 310     # We can now do the actual relocation
 311     for i in self.objs:
 312       i.apply_relocation(self.global_symbols)
 313
 314     # And update the ELF header with the entry point
 315     if not self.entry_point in self.global_symbols:
 316       raise UndefinedSymbol(self.entry_point)
 317     self.output.header.e_entry = self.global_symbols[self.entry_point]
 318
 319     # DONE !
 320
 321
 322   def toBinArray(self):
 323     return self.output.toBinArray()
 324
 325
 326   def tofile(self, file_object):
 327     return self.output.toBinArray().tofile(file_object)
 328