tools/layoutrom.py

   1 #!/usr/bin/env python
   2 # Script to analyze code and arrange ld sections.
   3 #
   4 # Copyright (C) 2008  Kevin O'Connor <kevin@koconnor.net>
   5 #
   6 # This file may be distributed under the terms of the GNU GPLv3 license.
   7
   8 import sys
   9
  10 # LD script headers/trailers
  11 COMMONHEADER = """
  12 /* DO NOT EDIT!  This is an autogenerated file.  See tools/layoutrom.py. */
  13 OUTPUT_FORMAT("elf32-i386")
  14 OUTPUT_ARCH("i386")
  15 SECTIONS
  16 {
  17 """
  18 COMMONTRAILER = """
  19
  20         /* Discard regular data sections to force a link error if
  21          * code attempts to access data not marked with VAR16 (or other
  22          * appropriate macro)
  23          */
  24         /DISCARD/ : {
  25                 *(.text*) *(.data*) *(.bss*) *(.rodata*)
  26                 *(COMMON) *(.discard*) *(.eh_frame)
  27                 }
  28 }
  29 """
  30
  31
  32 ######################################################################
  33 # Determine section locations
  34 ######################################################################
  35
  36 # Align 'pos' to 'alignbytes' offset
  37 def alignpos(pos, alignbytes):
  38     mask = alignbytes - 1
  39     return (pos + mask) & ~mask
  40
  41 # Determine the final addresses for a list of sections that end at an
  42 # address.
  43 def getSectionsStart(sections, endaddr, minalign=1):
  44     totspace = 0
  45     for size, align, name in sections:
  46         if align > minalign:
  47             minalign = align
  48         totspace = alignpos(totspace, align) + size
  49     startaddr = (endaddr - totspace) / minalign * minalign
  50     curaddr = startaddr
  51     # out = [(addr, sectioninfo), ...]
  52     out = []
  53     for sectioninfo in sections:
  54         size, align, name = sectioninfo
  55         curaddr = alignpos(curaddr, align)
  56         out.append((curaddr, sectioninfo))
  57         curaddr += size
  58     return out, startaddr
  59
  60 # Return the subset of sections with a given name prefix
  61 def getSectionsPrefix(sections, prefix):
  62     lp = len(prefix)
  63     out = []
  64     for size, align, name in sections:
  65         if name[:lp] == prefix:
  66             out.append((size, align, name))
  67     return out
  68
  69 # The 16bit code can't exceed 64K of space.
  70 BUILD_BIOS_ADDR = 0xf0000
  71 BUILD_BIOS_SIZE = 0x10000
  72
  73 # Layout the 16bit code.  This ensures sections with fixed offset
  74 # requirements are placed in the correct location.  It also places the
  75 # 16bit code as high as possible in the f-segment.
  76 def fitSections(sections, fillsections):
  77     canrelocate = list(fillsections)
  78     # fixedsections = [(addr, sectioninfo), ...]
  79     fixedsections = []
  80     for sectioninfo in sections:
  81         size, align, name = sectioninfo
  82         if name[:11] == '.fixedaddr.':
  83             addr = int(name[11:], 16)
  84             fixedsections.append((addr, sectioninfo))
  85             if align != 1:
  86                 print "Error: Fixed section %s has non-zero alignment (%d)" % (
  87                     name, align)
  88                 sys.exit(1)
  89
  90     # Find freespace in fixed address area
  91     fixedsections.sort()
  92     # fixedAddr = [(freespace, sectioninfo), ...]
  93     fixedAddr = []
  94     for i in range(len(fixedsections)):
  95         fixedsectioninfo = fixedsections[i]
  96         addr, section = fixedsectioninfo
  97         if i == len(fixedsections) - 1:
  98             nextaddr = BUILD_BIOS_SIZE
  99         else:
 100             nextaddr = fixedsections[i+1][0]
 101         avail = nextaddr - addr - section[0]
 102         fixedAddr.append((avail, fixedsectioninfo))
 103
 104     # Attempt to fit other sections into fixed area
 105     extrasections = []
 106     fixedAddr.sort()
 107     canrelocate.sort()
 108     totalused = 0
 109     for freespace, fixedsectioninfo in fixedAddr:
 110         fixedaddr, fixedsection = fixedsectioninfo
 111         addpos = fixedaddr + fixedsection[0]
 112         totalused += fixedsection[0]
 113         nextfixedaddr = addpos + freespace
 114 #        print "Filling section %x uses %d, next=%x, available=%d" % (
 115 #            fixedaddr, fixedsection[0], nextfixedaddr, freespace)
 116         while 1:
 117             canfit = None
 118             for fitsection in canrelocate:
 119                 fitsize, fitalign, fitname = fitsection
 120                 if addpos + fitsize > nextfixedaddr:
 121                     # Can't fit and nothing else will fit.
 122                     break
 123                 fitnextaddr = alignpos(addpos, fitalign) + fitsize
 124 #                print "Test %s - %x vs %x" % (
 125 #                    fitname, fitnextaddr, nextfixedaddr)
 126                 if fitnextaddr > nextfixedaddr:
 127                     # This item can't fit.
 128                     continue
 129                 canfit = (fitnextaddr, fitsection)
 130             if canfit is None:
 131                 break
 132             # Found a section that can fit.
 133             fitnextaddr, fitsection = canfit
 134             canrelocate.remove(fitsection)
 135             extrasections.append((addpos, fitsection))
 136             addpos = fitnextaddr
 137             totalused += fitsection[0]
 138 #            print "    Adding %s (size %d align %d) pos=%x avail=%d" % (
 139 #                fitsection[2], fitsection[0], fitsection[1]
 140 #                , fitnextaddr, nextfixedaddr - fitnextaddr)
 141     firstfixed = fixedsections[0][0]
 142
 143     # Report stats
 144     total = BUILD_BIOS_SIZE-firstfixed
 145     slack = total - totalused
 146     print ("Fixed space: 0x%x-0x%x  total: %d  slack: %d"
 147            "  Percent slack: %.1f%%" % (
 148             firstfixed, BUILD_BIOS_SIZE, total, slack,
 149             (float(slack) / total) * 100.0))
 150
 151     return fixedsections + extrasections, firstfixed
 152
 153 def doLayout(sections16, sections32seg, sections32flat):
 154     # Determine 16bit positions
 155     textsections = getSectionsPrefix(sections16, '.text.')
 156     rodatasections = (getSectionsPrefix(sections16, '.rodata.str1.1')
 157                       + getSectionsPrefix(sections16, '.rodata.__func__.'))
 158     datasections = getSectionsPrefix(sections16, '.data16.')
 159     fixedsections = getSectionsPrefix(sections16, '.fixedaddr.')
 160
 161     locs16fixed, firstfixed = fitSections(fixedsections, textsections)
 162     prunesections = [i[1] for i in locs16fixed]
 163     remsections = [i for i in textsections+rodatasections+datasections
 164                    if i not in prunesections]
 165     locs16, code16_start = getSectionsStart(remsections, firstfixed)
 166     locs16 = locs16 + locs16fixed
 167     locs16.sort()
 168
 169     # Determine 32seg positions
 170     textsections = getSectionsPrefix(sections32seg, '.text.')
 171     rodatasections = (getSectionsPrefix(sections32seg, '.rodata.str1.1')
 172                       + getSectionsPrefix(sections32seg, '.rodata.__func__.'))
 173     datasections = getSectionsPrefix(sections32seg, '.data32seg.')
 174
 175     locs32seg, code32seg_start = getSectionsStart(
 176         textsections + rodatasections + datasections, code16_start)
 177
 178     # Determine 32flat positions
 179     textsections = getSectionsPrefix(sections32flat, '.text.')
 180     rodatasections = getSectionsPrefix(sections32flat, '.rodata')
 181     datasections = getSectionsPrefix(sections32flat, '.data.')
 182     bsssections = getSectionsPrefix(sections32flat, '.bss.')
 183
 184     locs32flat, code32flat_start = getSectionsStart(
 185         textsections + rodatasections + datasections + bsssections
 186         , code32seg_start + BUILD_BIOS_ADDR, 16)
 187
 188     # Print statistics
 189     size16 = BUILD_BIOS_SIZE - code16_start
 190     size32seg = code16_start - code32seg_start
 191     size32flat = code32seg_start + BUILD_BIOS_ADDR - code32flat_start
 192     print "16bit size:           %d" % size16
 193     print "32bit segmented size: %d" % size32seg
 194     print "32bit flat size:      %d" % size32flat
 195
 196     return locs16, locs32seg, locs32flat
 197
 198
 199 ######################################################################
 200 # Linker script output
 201 ######################################################################
 202
 203 # Write LD script includes for the given cross references
 204 def outXRefs(xrefs, finallocs, delta=0):
 205     out = ""
 206     for symbol, (fileid, section, addr) in xrefs.items():
 207         if fileid < 2:
 208             addr += delta
 209         out += "%s = 0x%x ;\n" % (symbol, finallocs[(fileid, section)] + addr)
 210     return out
 211
 212 # Write LD script includes for the given sections using relative offsets
 213 def outRelSections(locs, startsym):
 214     out = ""
 215     for addr, sectioninfo in locs:
 216         size, align, name = sectioninfo
 217         out += ". = ( 0x%x - %s ) ;\n" % (addr, startsym)
 218         if name == '.rodata.str1.1':
 219             out += "_rodata = . ;\n"
 220         out += "*(%s)\n" % (name,)
 221     return out
 222
 223 # Layout the 32bit segmented code.  This places the code as high as possible.
 224 def writeLinkerScripts(locs16, locs32seg, locs32flat
 225                        , xref16, xref32seg, xref32flat
 226                        , out16, out32seg, out32flat):
 227     # Index to final location for each section
 228     # finallocs[(fileid, section)] = addr
 229     finallocs = {}
 230     for fileid, locs in ((0, locs16), (1, locs32seg), (2, locs32flat)):
 231         for addr, sectioninfo in locs:
 232             finallocs[(fileid, sectioninfo[2])] = addr
 233
 234     # Write 16bit linker script
 235     code16_start = locs16[0][0]
 236     output = open(out16, 'wb')
 237     output.write(COMMONHEADER + outXRefs(xref16, finallocs) + """
 238     code16_start = 0x%x ;
 239     .text16 code16_start : {
 240 """ % (code16_start)
 241                  + outRelSections(locs16, 'code16_start')
 242                  + """
 243     }
 244 """
 245                  + COMMONTRAILER)
 246     output.close()
 247
 248     # Write 32seg linker script
 249     code32seg_start = code16_start
 250     if locs32seg:
 251         code32seg_start = locs32seg[0][0]
 252     output = open(out32seg, 'wb')
 253     output.write(COMMONHEADER + outXRefs(xref32seg, finallocs) + """
 254     code32seg_start = 0x%x ;
 255     .text32seg code32seg_start : {
 256 """ % (code32seg_start)
 257                  + outRelSections(locs32seg, 'code32seg_start')
 258                  + """
 259     }
 260 """
 261                  + COMMONTRAILER)
 262     output.close()
 263
 264     # Write 32flat linker script
 265     output = open(out32flat, 'wb')
 266     output.write(COMMONHEADER
 267                  + outXRefs(xref32flat, finallocs, BUILD_BIOS_ADDR) + """
 268     code32flat_start = 0x%x ;
 269     .text code32flat_start : {
 270 """ % (locs32flat[0][0])
 271                  + outRelSections(locs32flat, 'code32flat_start')
 272                  + """
 273         . = ( 0x%x - code32flat_start ) ;
 274         *(.text32seg)
 275         . = ( 0x%x - code32flat_start ) ;
 276         *(.text16)
 277         code32flat_end = ABSOLUTE(.) ;
 278     } :text
 279 """ % (code32seg_start + BUILD_BIOS_ADDR, code16_start + BUILD_BIOS_ADDR)
 280                  + COMMONTRAILER
 281                  + """
 282 ENTRY(post32)
 283 PHDRS
 284 {
 285         text PT_LOAD AT ( code32flat_start ) ;
 286 }
 287 """)
 288     output.close()
 289
 290
 291 ######################################################################
 292 # Section garbage collection
 293 ######################################################################
 294
 295 # Find and keep the section associated with a symbol (if available).
 296 def keepsymbol(symbol, infos, pos, callerpos=None):
 297     addr, section = infos[pos][1].get(symbol, (None, None))
 298     if section is None or '*' in section or section[:9] == '.discard.':
 299         return -1
 300     if callerpos is not None and symbol not in infos[callerpos][4]:
 301         # This symbol reference is a cross section reference (an xref).
 302         # xref[symbol] = (fileid, section, addr)
 303         infos[callerpos][4][symbol] = (pos, section, addr)
 304     keepsection(section, infos, pos)
 305     return 0
 306
 307 # Note required section, and recursively set all referenced sections
 308 # as required.
 309 def keepsection(name, infos, pos=0):
 310     if name in infos[pos][3]:
 311         # Already kept - nothing to do.
 312         return
 313     infos[pos][3].append(name)
 314     relocs = infos[pos][2].get(name)
 315     if relocs is None:
 316         return
 317     # Keep all sections that this section points to
 318     for symbol in relocs:
 319         ret = keepsymbol(symbol, infos, pos)
 320         if not ret:
 321             continue
 322         # Not in primary sections - it may be a cross 16/32 reference
 323         ret = keepsymbol(symbol, infos, (pos+1)%3, pos)
 324         if not ret:
 325             continue
 326         ret = keepsymbol(symbol, infos, (pos+2)%3, pos)
 327         if not ret:
 328             continue
 329
 330 # Return a list of kept sections.
 331 def getSectionsList(sections, names):
 332     return [i for i in sections if i[2] in names]
 333
 334 # Determine which sections are actually referenced and need to be
 335 # placed into the output file.
 336 def gc(info16, info32seg, info32flat):
 337     # infos = ((sections, symbols, relocs, keep sections, xrefs), ...)
 338     infos = ((info16[0], info16[1], info16[2], [], {}),
 339              (info32seg[0], info32seg[1], info32seg[2], [], {}),
 340              (info32flat[0], info32flat[1], info32flat[2], [], {}))
 341     # Start by keeping sections that are globally visible.
 342     for size, align, section in info16[0]:
 343         if section[:11] == '.fixedaddr.' or '.export.' in section:
 344             keepsection(section, infos)
 345     keepsymbol('post32', infos, 0, 2)
 346     # Return sections found.
 347     keep16 = getSectionsList(info16[0], infos[0][3]), infos[0][4]
 348     keep32seg = getSectionsList(info32seg[0], infos[1][3]), infos[1][4]
 349     keep32flat = getSectionsList(info32flat[0], infos[2][3]), infos[2][4]
 350     return keep16, keep32seg, keep32flat
 351
 352
 353 ######################################################################
 354 # Startup and input parsing
 355 ######################################################################
 356
 357 # Read in output from objdump
 358 def parseObjDump(file):
 359     # sections = [(size, align, section), ...]
 360     sections = []
 361     # symbols[symbol] = (addr, section)
 362     symbols = {}
 363     # relocs[section] = [symbol, ...]
 364     relocs = {}
 365
 366     state = None
 367     for line in file.readlines():
 368         line = line.rstrip()
 369         if line == 'Sections:':
 370             state = 'section'
 371             continue
 372         if line == 'SYMBOL TABLE:':
 373             state = 'symbol'
 374             continue
 375         if line[:24] == 'RELOCATION RECORDS FOR [':
 376             state = 'reloc'
 377             relocsection = line[24:-2]
 378             continue
 379
 380         if state == 'section':
 381             try:
 382                 idx, name, size, vma, lma, fileoff, align = line.split()
 383                 if align[:3] != '2**':
 384                     continue
 385                 sections.append((int(size, 16), 2**int(align[3:]), name))
 386             except:
 387                 pass
 388             continue
 389         if state == 'symbol':
 390             try:
 391                 section, size, symbol = line[17:].split()
 392                 size = int(size, 16)
 393                 addr = int(line[:8], 16)
 394                 symbols[symbol] = addr, section
 395             except:
 396                 pass
 397             continue
 398         if state == 'reloc':
 399             try:
 400                 off, type, symbol = line.split()
 401                 off = int(off, 16)
 402                 relocs.setdefault(relocsection, []).append(symbol)
 403             except:
 404                 pass
 405     return sections, symbols, relocs
 406
 407 def main():
 408     # Get output name
 409     in16, in32seg, in32flat, out16, out32seg, out32flat = sys.argv[1:]
 410
 411     # Read in the objdump information
 412     infile16 = open(in16, 'rb')
 413     infile32seg = open(in32seg, 'rb')
 414     infile32flat = open(in32flat, 'rb')
 415
 416     # infoX = (sections, symbols, relocs)
 417     info16 = parseObjDump(infile16)
 418     info32seg = parseObjDump(infile32seg)
 419     info32flat = parseObjDump(infile32flat)
 420
 421     # Figure out which sections to keep.
 422     # keepX = (sections, xrefs)
 423     keep16, keep32seg, keep32flat = gc(info16, info32seg, info32flat)
 424
 425     # Determine the final memory locations of each kept section.
 426     # locsX = [(addr, sectioninfo), ...]
 427     locs16, locs32seg, locs32flat = doLayout(
 428         keep16[0], keep32seg[0], keep32flat[0])
 429
 430     # Write out linker script files.
 431     writeLinkerScripts(locs16, locs32seg, locs32flat
 432                        , keep16[1], keep32seg[1], keep32flat[1]
 433                        , out16, out32seg, out32flat)
 434
 435 if __name__ == '__main__':
 436     main()