tools/layoutrom.py

   1 #!/usr/bin/env python
   2 # Script to analyze code and arrange ld sections.
   3 #
   4 # Copyright (C) 2008-2010  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 setSectionsStart(sections, endaddr, minalign=1):
  44     totspace = 0
  45     for section in sections:
  46         if section.align > minalign:
  47             minalign = section.align
  48         totspace = alignpos(totspace, section.align) + section.size
  49     startaddr = (endaddr - totspace) / minalign * minalign
  50     curaddr = startaddr
  51     # out = [(addr, sectioninfo), ...]
  52     out = []
  53     for section in sections:
  54         curaddr = alignpos(curaddr, section.align)
  55         section.finalloc = curaddr
  56         curaddr += section.size
  57     return startaddr
  58
  59 # The 16bit code can't exceed 64K of space.
  60 BUILD_BIOS_ADDR = 0xf0000
  61 BUILD_BIOS_SIZE = 0x10000
  62
  63 # Layout the 16bit code.  This ensures sections with fixed offset
  64 # requirements are placed in the correct location.  It also places the
  65 # 16bit code as high as possible in the f-segment.
  66 def fitSections(sections, fillsections):
  67     # fixedsections = [(addr, section), ...]
  68     fixedsections = []
  69     for section in sections:
  70         if section.name.startswith('.fixedaddr.'):
  71             addr = int(section.name[11:], 16)
  72             section.finalloc = addr
  73             fixedsections.append((addr, section))
  74             if section.align != 1:
  75                 print "Error: Fixed section %s has non-zero alignment (%d)" % (
  76                     section.name, section.align)
  77                 sys.exit(1)
  78     fixedsections.sort()
  79     firstfixed = fixedsections[0][0]
  80
  81     # Find freespace in fixed address area
  82     # fixedAddr = [(freespace, section), ...]
  83     fixedAddr = []
  84     for i in range(len(fixedsections)):
  85         fixedsectioninfo = fixedsections[i]
  86         addr, section = fixedsectioninfo
  87         if i == len(fixedsections) - 1:
  88             nextaddr = BUILD_BIOS_SIZE
  89         else:
  90             nextaddr = fixedsections[i+1][0]
  91         avail = nextaddr - addr - section.size
  92         fixedAddr.append((avail, section))
  93     fixedAddr.sort()
  94
  95     # Attempt to fit other sections into fixed area
  96     canrelocate = [(section.size, section.align, section.name, section)
  97                    for section in fillsections]
  98     canrelocate.sort()
  99     canrelocate = [section for size, align, name, section in canrelocate]
 100     totalused = 0
 101     for freespace, fixedsection in fixedAddr:
 102         addpos = fixedsection.finalloc + fixedsection.size
 103         totalused += fixedsection.size
 104         nextfixedaddr = addpos + freespace
 105 #        print "Filling section %x uses %d, next=%x, available=%d" % (
 106 #            fixedsection.finalloc, fixedsection.size, nextfixedaddr, freespace)
 107         while 1:
 108             canfit = None
 109             for fitsection in canrelocate:
 110                 if addpos + fitsection.size > nextfixedaddr:
 111                     # Can't fit and nothing else will fit.
 112                     break
 113                 fitnextaddr = alignpos(addpos, fitsection.align) + fitsection.size
 114 #                print "Test %s - %x vs %x" % (
 115 #                    fitsection.name, fitnextaddr, nextfixedaddr)
 116                 if fitnextaddr > nextfixedaddr:
 117                     # This item can't fit.
 118                     continue
 119                 canfit = (fitnextaddr, fitsection)
 120             if canfit is None:
 121                 break
 122             # Found a section that can fit.
 123             fitnextaddr, fitsection = canfit
 124             canrelocate.remove(fitsection)
 125             fitsection.finalloc = addpos
 126             addpos = fitnextaddr
 127             totalused += fitsection.size
 128 #            print "    Adding %s (size %d align %d) pos=%x avail=%d" % (
 129 #                fitsection[2], fitsection[0], fitsection[1]
 130 #                , fitnextaddr, nextfixedaddr - fitnextaddr)
 131
 132     # Report stats
 133     total = BUILD_BIOS_SIZE-firstfixed
 134     slack = total - totalused
 135     print ("Fixed space: 0x%x-0x%x  total: %d  slack: %d"
 136            "  Percent slack: %.1f%%" % (
 137             firstfixed, BUILD_BIOS_SIZE, total, slack,
 138             (float(slack) / total) * 100.0))
 139
 140     return firstfixed
 141
 142 # Return the subset of sections with a given name prefix
 143 def getSectionsPrefix(sections, category, prefix):
 144     return [section for section in sections
 145             if section.category == category and section.name.startswith(prefix)]
 146
 147 def doLayout(sections):
 148     # Determine 16bit positions
 149     textsections = getSectionsPrefix(sections, '16', '.text.')
 150     rodatasections = (getSectionsPrefix(sections, '16', '.rodata.str1.1')
 151                       + getSectionsPrefix(sections, '16', '.rodata.__func__.'))
 152     datasections = getSectionsPrefix(sections, '16', '.data16.')
 153     fixedsections = getSectionsPrefix(sections, '16', '.fixedaddr.')
 154
 155     firstfixed = fitSections(fixedsections, textsections)
 156     remsections = [s for s in textsections+rodatasections+datasections
 157                    if s.finalloc is None]
 158     code16_start = setSectionsStart(remsections, firstfixed)
 159
 160     # Determine 32seg positions
 161     textsections = getSectionsPrefix(sections, '32seg', '.text.')
 162     rodatasections = (getSectionsPrefix(sections, '32seg', '.rodata.str1.1')
 163                       +getSectionsPrefix(sections, '32seg', '.rodata.__func__.'))
 164     datasections = getSectionsPrefix(sections, '32seg', '.data32seg.')
 165
 166     code32seg_start = setSectionsStart(
 167         textsections + rodatasections + datasections, code16_start)
 168
 169     # Determine 32flat runtime positions
 170     textsections = getSectionsPrefix(sections, '32flat', '.text.')
 171     rodatasections = getSectionsPrefix(sections, '32flat', '.rodata')
 172     datasections = getSectionsPrefix(sections, '32flat', '.data.')
 173     bsssections = getSectionsPrefix(sections, '32flat', '.bss.')
 174
 175     code32flat_start = setSectionsStart(
 176         textsections + rodatasections + datasections + bsssections
 177         , code32seg_start + BUILD_BIOS_ADDR, 16)
 178
 179     # Determine 32flat init positions
 180     textsections = getSectionsPrefix(sections, '32init', '.text.')
 181     rodatasections = getSectionsPrefix(sections, '32init', '.rodata')
 182     datasections = getSectionsPrefix(sections, '32init', '.data.')
 183     bsssections = getSectionsPrefix(sections, '32init', '.bss.')
 184
 185     code32init_start = setSectionsStart(
 186         textsections + rodatasections + datasections + bsssections
 187         , code32flat_start, 16)
 188
 189     # Print statistics
 190     size16 = BUILD_BIOS_SIZE - code16_start
 191     size32seg = code16_start - code32seg_start
 192     size32flat = code32seg_start + BUILD_BIOS_ADDR - code32flat_start
 193     size32init = code32flat_start - code32init_start
 194     print "16bit size:           %d" % size16
 195     print "32bit segmented size: %d" % size32seg
 196     print "32bit flat size:      %d" % size32flat
 197     print "32bit flat init size: %d" % size32init
 198
 199
 200 ######################################################################
 201 # Linker script output
 202 ######################################################################
 203
 204 # Write LD script includes for the given cross references
 205 def outXRefs(sections):
 206     xrefs = {}
 207     out = ""
 208     for section in sections:
 209         for reloc in section.relocs:
 210             symbol = reloc.symbol
 211             if (symbol.section is None
 212                 or (symbol.section.fileid == section.fileid
 213                     and symbol.name == reloc.symbolname)
 214                 or reloc.symbolname in xrefs):
 215                 continue
 216             xrefs[reloc.symbolname] = 1
 217             addr = symbol.section.finalloc + symbol.offset
 218             if (section.fileid == '32flat'
 219                 and symbol.section.fileid in ('16', '32seg')):
 220                 addr += BUILD_BIOS_ADDR
 221             out += "%s = 0x%x ;\n" % (reloc.symbolname, addr)
 222     return out
 223
 224 # Write LD script includes for the given sections using relative offsets
 225 def outRelSections(sections, startsym):
 226     out = ""
 227     for section in sections:
 228         out += ". = ( 0x%x - %s ) ;\n" % (section.finalloc, startsym)
 229         if section.name == '.rodata.str1.1':
 230             out += "_rodata = . ;\n"
 231         out += "*(%s)\n" % (section.name,)
 232     return out
 233
 234 def getSectionsFile(sections, fileid, defaddr=0):
 235     sections = [(section.finalloc, section)
 236                 for section in sections if section.fileid == fileid]
 237     sections.sort()
 238     sections = [section for addr, section in sections]
 239     pos = defaddr
 240     if sections:
 241         pos = sections[0].finalloc
 242     return sections, pos
 243
 244 # Layout the 32bit segmented code.  This places the code as high as possible.
 245 def writeLinkerScripts(sections, entrysym, genreloc, out16, out32seg, out32flat):
 246     # Write 16bit linker script
 247     sections16, code16_start = getSectionsFile(sections, '16')
 248     output = open(out16, 'wb')
 249     output.write(COMMONHEADER + outXRefs(sections16) + """
 250     code16_start = 0x%x ;
 251     .text16 code16_start : {
 252 """ % (code16_start)
 253                  + outRelSections(sections16, 'code16_start')
 254                  + """
 255     }
 256 """
 257                  + COMMONTRAILER)
 258     output.close()
 259
 260     # Write 32seg linker script
 261     sections32seg, code32seg_start = getSectionsFile(
 262         sections, '32seg', code16_start)
 263     output = open(out32seg, 'wb')
 264     output.write(COMMONHEADER + outXRefs(sections32seg) + """
 265     code32seg_start = 0x%x ;
 266     .text32seg code32seg_start : {
 267 """ % (code32seg_start)
 268                  + outRelSections(sections32seg, 'code32seg_start')
 269                  + """
 270     }
 271 """
 272                  + COMMONTRAILER)
 273     output.close()
 274
 275     # Write 32flat linker script
 276     sections32flat, code32flat_start = getSectionsFile(
 277         sections, '32flat', code32seg_start)
 278     relocstr = ""
 279     relocminalign = 0
 280     if genreloc:
 281         # Generate relocations
 282         relocstr, size, relocminalign = genRelocs(sections)
 283         code32flat_start -= size
 284     output = open(out32flat, 'wb')
 285     output.write(COMMONHEADER
 286                  + outXRefs(sections32flat) + """
 287     %s = 0x%x ;
 288     _reloc_min_align = 0x%x ;
 289     code32flat_start = 0x%x ;
 290     .text code32flat_start : {
 291 """ % (entrysym.name,
 292        entrysym.section.finalloc + entrysym.offset + BUILD_BIOS_ADDR,
 293        relocminalign, code32flat_start)
 294                  + relocstr
 295                  + """
 296         code32init_start = ABSOLUTE(.) ;
 297 """
 298                  + outRelSections(getSectionsPrefix(sections32flat, '32init', '')
 299                                   , 'code32flat_start')
 300                  + """
 301         code32init_end = ABSOLUTE(.) ;
 302 """
 303                  + outRelSections(getSectionsPrefix(sections32flat, '32flat', '')
 304                                   , 'code32flat_start')
 305                  + """
 306         . = ( 0x%x - code32flat_start ) ;
 307         *(.text32seg)
 308         . = ( 0x%x - code32flat_start ) ;
 309         *(.text16)
 310         code32flat_end = ABSOLUTE(.) ;
 311     } :text
 312 """ % (code32seg_start + BUILD_BIOS_ADDR, code16_start + BUILD_BIOS_ADDR)
 313                  + COMMONTRAILER
 314                  + """
 315 ENTRY(%s)
 316 PHDRS
 317 {
 318         text PT_LOAD AT ( code32flat_start ) ;
 319 }
 320 """ % (entrysym.name,))
 321     output.close()
 322
 323
 324 ######################################################################
 325 # Detection of init code
 326 ######################################################################
 327
 328 # Determine init section relocations
 329 def genRelocs(sections):
 330     absrelocs = []
 331     relrelocs = []
 332     initrelocs = []
 333     minalign = 16
 334     for section in sections:
 335         if section.category == '32init' and section.align > minalign:
 336             minalign = section.align
 337         for reloc in section.relocs:
 338             symbol = reloc.symbol
 339             if symbol.section is None:
 340                 continue
 341             relocpos = section.finalloc + reloc.offset
 342             if (reloc.type == 'R_386_32' and section.category == '32init'
 343                 and symbol.section.category == '32init'):
 344                 # Absolute relocation
 345                 absrelocs.append(relocpos)
 346             elif (reloc.type == 'R_386_PC32' and section.category == '32init'
 347                   and symbol.section.category != '32init'):
 348                 # Relative relocation
 349                 relrelocs.append(relocpos)
 350             elif (section.category != '32init'
 351                   and symbol.section.category == '32init'):
 352                 # Relocation to the init section
 353                 if section.fileid in ('16', '32seg'):
 354                     relocpos += BUILD_BIOS_ADDR
 355                 initrelocs.append(relocpos)
 356     absrelocs.sort()
 357     relrelocs.sort()
 358     initrelocs.sort()
 359     out = ("        _reloc_abs_start = ABSOLUTE(.) ;\n"
 360            + "".join(["LONG(0x%x - code32init_start)\n" % (pos,)
 361                       for pos in absrelocs])
 362            + "        _reloc_abs_end = ABSOLUTE(.) ;\n"
 363            + "        _reloc_rel_start = ABSOLUTE(.) ;\n"
 364            + "".join(["LONG(0x%x - code32init_start)\n" % (pos,)
 365                       for pos in relrelocs])
 366            + "        _reloc_rel_end = ABSOLUTE(.) ;\n"
 367            + "        _reloc_init_start = ABSOLUTE(.) ;\n"
 368            + "".join(["LONG(0x%x - code32flat_start)\n" % (pos,)
 369                       for pos in initrelocs])
 370            + "        _reloc_init_end = ABSOLUTE(.) ;\n")
 371     return out, len(absrelocs + relrelocs + initrelocs) * 4, minalign
 372
 373 def markRuntime(section, sections):
 374     if (section is None or not section.keep or section.category is not None
 375         or '.init.' in section.name or section.fileid != '32flat'):
 376         return
 377     section.category = '32flat'
 378     # Recursively mark all sections this section points to
 379     for reloc in section.relocs:
 380         markRuntime(reloc.symbol.section, sections)
 381
 382 def findInit(sections):
 383     # Recursively find and mark all "runtime" sections.
 384     for section in sections:
 385         if '.runtime.' in section.name or '.export.' in section.name:
 386             markRuntime(section, sections)
 387     for section in sections:
 388         if section.category is not None:
 389             continue
 390         if section.fileid == '32flat':
 391             section.category = '32init'
 392         else:
 393             section.category = section.fileid
 394
 395
 396 ######################################################################
 397 # Section garbage collection
 398 ######################################################################
 399
 400 CFUNCPREFIX = [('_cfunc16_', 0), ('_cfunc32seg_', 1), ('_cfunc32flat_', 2)]
 401
 402 # Find and keep the section associated with a symbol (if available).
 403 def keepsymbol(reloc, infos, pos, isxref):
 404     symbolname = reloc.symbolname
 405     mustbecfunc = 0
 406     for symprefix, needpos in CFUNCPREFIX:
 407         if symbolname.startswith(symprefix):
 408             if needpos != pos:
 409                 return -1
 410             symbolname = symbolname[len(symprefix):]
 411             mustbecfunc = 1
 412             break
 413     symbol = infos[pos][1].get(symbolname)
 414     if (symbol is None or symbol.section is None
 415         or symbol.section.name.startswith('.discard.')):
 416         return -1
 417     isdestcfunc = (symbol.section.name.startswith('.text.')
 418                    and not symbol.section.name.startswith('.text.asm.'))
 419     if ((mustbecfunc and not isdestcfunc)
 420         or (not mustbecfunc and isdestcfunc and isxref)):
 421         return -1
 422
 423     reloc.symbol = symbol
 424     keepsection(symbol.section, infos, pos)
 425     return 0
 426
 427 # Note required section, and recursively set all referenced sections
 428 # as required.
 429 def keepsection(section, infos, pos=0):
 430     if section.keep:
 431         # Already kept - nothing to do.
 432         return
 433     section.keep = 1
 434     # Keep all sections that this section points to
 435     for reloc in section.relocs:
 436         ret = keepsymbol(reloc, infos, pos, 0)
 437         if not ret:
 438             continue
 439         # Not in primary sections - it may be a cross 16/32 reference
 440         ret = keepsymbol(reloc, infos, (pos+1)%3, 1)
 441         if not ret:
 442             continue
 443         ret = keepsymbol(reloc, infos, (pos+2)%3, 1)
 444         if not ret:
 445             continue
 446
 447 # Determine which sections are actually referenced and need to be
 448 # placed into the output file.
 449 def gc(info16, info32seg, info32flat):
 450     # infos = ((sections16, symbols16), (sect32seg, sym32seg)
 451     #          , (sect32flat, sym32flat))
 452     infos = (info16, info32seg, info32flat)
 453     # Start by keeping sections that are globally visible.
 454     for section in info16[0]:
 455         if section.name.startswith('.fixedaddr.') or '.export.' in section.name:
 456             keepsection(section, infos)
 457     return [section for section in info16[0]+info32seg[0]+info32flat[0]
 458             if section.keep]
 459
 460
 461 ######################################################################
 462 # Startup and input parsing
 463 ######################################################################
 464
 465 class Section:
 466     name = size = alignment = fileid = relocs = None
 467     finalloc = category = keep = None
 468 class Reloc:
 469     offset = type = symbolname = symbol = None
 470 class Symbol:
 471     name = offset = section = None
 472
 473 # Read in output from objdump
 474 def parseObjDump(file, fileid):
 475     # sections = [section, ...]
 476     sections = []
 477     sectionmap = {}
 478     # symbols[symbolname] = symbol
 479     symbols = {}
 480
 481     state = None
 482     for line in file.readlines():
 483         line = line.rstrip()
 484         if line == 'Sections:':
 485             state = 'section'
 486             continue
 487         if line == 'SYMBOL TABLE:':
 488             state = 'symbol'
 489             continue
 490         if line.startswith('RELOCATION RECORDS FOR ['):
 491             sectionname = line[24:-2]
 492             if sectionname.startswith('.debug_'):
 493                 # Skip debugging sections (to reduce parsing time)
 494                 state = None
 495                 continue
 496             state = 'reloc'
 497             relocsection = sectionmap[sectionname]
 498             continue
 499
 500         if state == 'section':
 501             try:
 502                 idx, name, size, vma, lma, fileoff, align = line.split()
 503                 if align[:3] != '2**':
 504                     continue
 505                 section = Section()
 506                 section.name = name
 507                 section.size = int(size, 16)
 508                 section.align = 2**int(align[3:])
 509                 section.fileid = fileid
 510                 section.relocs = []
 511                 sections.append(section)
 512                 sectionmap[name] = section
 513             except ValueError:
 514                 pass
 515             continue
 516         if state == 'symbol':
 517             try:
 518                 sectionname, size, name = line[17:].split()
 519                 symbol = Symbol()
 520                 symbol.size = int(size, 16)
 521                 symbol.offset = int(line[:8], 16)
 522                 symbol.name = name
 523                 symbol.section = sectionmap.get(sectionname)
 524                 symbols[name] = symbol
 525             except ValueError:
 526                 pass
 527             continue
 528         if state == 'reloc':
 529             try:
 530                 off, type, symbolname = line.split()
 531                 reloc = Reloc()
 532                 reloc.offset = int(off, 16)
 533                 reloc.type = type
 534                 reloc.symbolname = symbolname
 535                 reloc.symbol = symbols.get(symbolname)
 536                 if reloc.symbol is None:
 537                     # Some binutils (2.20.1) give section name instead
 538                     # of a symbol - create a dummy symbol.
 539                     reloc.symbol = symbol = Symbol()
 540                     symbol.size = 0
 541                     symbol.offset = 0
 542                     symbol.name = symbolname
 543                     symbol.section = sectionmap.get(symbolname)
 544                     symbols[symbolname] = symbol
 545                 relocsection.relocs.append(reloc)
 546             except ValueError:
 547                 pass
 548     return sections, symbols
 549
 550 def main():
 551     # Get output name
 552     in16, in32seg, in32flat, out16, out32seg, out32flat = sys.argv[1:]
 553
 554     # Read in the objdump information
 555     infile16 = open(in16, 'rb')
 556     infile32seg = open(in32seg, 'rb')
 557     infile32flat = open(in32flat, 'rb')
 558
 559     # infoX = (sections, symbols)
 560     info16 = parseObjDump(infile16, '16')
 561     info32seg = parseObjDump(infile32seg, '32seg')
 562     info32flat = parseObjDump(infile32flat, '32flat')
 563
 564     # Figure out which sections to keep.
 565     sections = gc(info16, info32seg, info32flat)
 566
 567     # Separate 32bit flat into runtime and init parts
 568     findInit(sections)
 569
 570     # Determine the final memory locations of each kept section.
 571     doLayout(sections)
 572
 573     # Write out linker script files.
 574     entrysym = info16[1]['entry_elf']
 575     genreloc = '_reloc_abs_start' in info32flat[1]
 576     writeLinkerScripts(sections, entrysym, genreloc, out16, out32seg, out32flat)
 577
 578 if __name__ == '__main__':
 579     main()