#!/usr/bin/env python
-# Script to arrange sections to ensure fixed offsets.
+# Script to analyze code and arrange ld sections.
#
-# Copyright (C) 2008 Kevin O'Connor <kevin@koconnor.net>
+# Copyright (C) 2008-2010 Kevin O'Connor <kevin@koconnor.net>
#
# This file may be distributed under the terms of the GNU GPLv3 license.
import sys
-def main():
- # Get output name
- outname = sys.argv[1]
+# LD script headers/trailers
+COMMONHEADER = """
+/* DO NOT EDIT! This is an autogenerated file. See tools/layoutrom.py. */
+OUTPUT_FORMAT("elf32-i386")
+OUTPUT_ARCH("i386")
+SECTIONS
+{
+"""
+COMMONTRAILER = """
+
+ /* Discard regular data sections to force a link error if
+ * code attempts to access data not marked with VAR16 (or other
+ * appropriate macro)
+ */
+ /DISCARD/ : {
+ *(.text*) *(.data*) *(.bss*) *(.rodata*)
+ *(COMMON) *(.discard*) *(.eh_frame)
+ }
+}
+"""
- # Read in section names and sizes
- # sections = [(size, align, name), ...]
- sections = []
- for line in sys.stdin.readlines():
- try:
- idx, name, size, vma, lma, fileoff, align = line.split()
- if align[:3] != '2**':
- continue
- sections.append((int(size, 16), 2**int(align[3:]), name))
- except:
- pass
- doLayout(sections, outname)
+######################################################################
+# Determine section locations
+######################################################################
+# Align 'pos' to 'alignbytes' offset
def alignpos(pos, alignbytes):
mask = alignbytes - 1
return (pos + mask) & ~mask
-MAXPOS = 0x10000
+# Determine the final addresses for a list of sections that end at an
+# address.
+def setSectionsStart(sections, endaddr, minalign=1):
+ totspace = 0
+ for section in sections:
+ if section.align > minalign:
+ minalign = section.align
+ totspace = alignpos(totspace, section.align) + section.size
+ startaddr = (endaddr - totspace) / minalign * minalign
+ curaddr = startaddr
+ # out = [(addr, sectioninfo), ...]
+ out = []
+ for section in sections:
+ curaddr = alignpos(curaddr, section.align)
+ section.finalloc = curaddr
+ curaddr += section.size
+ return startaddr
-def doLayout(sections, outname):
- textsections = []
- rodatasections = []
- datasections = []
- # fixedsections = [(addr, sectioninfo, extasectionslist), ...]
- fixedsections = []
- # canrelocate = [(sectioninfo, list), ...]
- canrelocate = []
+# The 16bit code can't exceed 64K of space.
+BUILD_BIOS_ADDR = 0xf0000
+BUILD_BIOS_SIZE = 0x10000
- # Find desired sections.
+# Layout the 16bit code. This ensures sections with fixed offset
+# requirements are placed in the correct location. It also places the
+# 16bit code as high as possible in the f-segment.
+def fitSections(sections, fillsections):
+ # fixedsections = [(addr, section), ...]
+ fixedsections = []
for section in sections:
- size, align, name = section
- if name[:11] == '.fixedaddr.':
- addr = int(name[11:], 16)
- fixedsections.append((addr, section, []))
- if align != 1:
+ if section.name.startswith('.fixedaddr.'):
+ addr = int(section.name[11:], 16)
+ section.finalloc = addr
+ fixedsections.append((addr, section))
+ if section.align != 1:
print "Error: Fixed section %s has non-zero alignment (%d)" % (
- name, align)
+ section.name, section.align)
sys.exit(1)
- if name[:6] == '.text.':
- textsections.append(section)
- canrelocate.append((section, textsections))
- if name[:17] == '.rodata.__func__.' or name == '.rodata.str1.1':
- rodatasections.append(section)
- #canrelocate.append((section, rodatasections))
- if name[:8] == '.data16.':
- datasections.append(section)
- #canrelocate.append((section, datasections))
+ fixedsections.sort()
+ firstfixed = fixedsections[0][0]
# Find freespace in fixed address area
- fixedsections.sort()
- # fixedAddr = [(freespace, sectioninfo), ...]
+ # fixedAddr = [(freespace, section), ...]
fixedAddr = []
for i in range(len(fixedsections)):
fixedsectioninfo = fixedsections[i]
- addr, section, extrasectionslist = fixedsectioninfo
+ addr, section = fixedsectioninfo
if i == len(fixedsections) - 1:
- nextaddr = MAXPOS
+ nextaddr = BUILD_BIOS_SIZE
else:
nextaddr = fixedsections[i+1][0]
- avail = nextaddr - addr - section[0]
- fixedAddr.append((avail, fixedsectioninfo))
+ avail = nextaddr - addr - section.size
+ fixedAddr.append((avail, section))
+ fixedAddr.sort()
# Attempt to fit other sections into fixed area
- fixedAddr.sort()
+ canrelocate = [(section.size, section.align, section.name, section)
+ for section in fillsections]
canrelocate.sort()
+ canrelocate = [section for size, align, name, section in canrelocate]
totalused = 0
- for freespace, fixedsectioninfo in fixedAddr:
- fixedaddr, fixedsection, extrasections = fixedsectioninfo
- addpos = fixedaddr + fixedsection[0]
- totalused += fixedsection[0]
+ for freespace, fixedsection in fixedAddr:
+ addpos = fixedsection.finalloc + fixedsection.size
+ totalused += fixedsection.size
nextfixedaddr = addpos + freespace
# print "Filling section %x uses %d, next=%x, available=%d" % (
-# fixedaddr, fixedsection[0], nextfixedaddr, freespace)
+# fixedsection.finalloc, fixedsection.size, nextfixedaddr, freespace)
while 1:
canfit = None
- for fixedaddrinfo in canrelocate:
- fitsection, inlist = fixedaddrinfo
- fitsize, fitalign, fitname = fitsection
- if addpos + fitsize > nextfixedaddr:
+ for fitsection in canrelocate:
+ if addpos + fitsection.size > nextfixedaddr:
# Can't fit and nothing else will fit.
break
- fitnextaddr = alignpos(addpos, fitalign) + fitsize
+ fitnextaddr = alignpos(addpos, fitsection.align) + fitsection.size
# print "Test %s - %x vs %x" % (
-# fitname, fitnextaddr, nextfixedaddr)
+# fitsection.name, fitnextaddr, nextfixedaddr)
if fitnextaddr > nextfixedaddr:
# This item can't fit.
continue
- canfit = (fitnextaddr, fixedaddrinfo)
+ canfit = (fitnextaddr, fitsection)
if canfit is None:
break
# Found a section that can fit.
- fitnextaddr, fixedaddrinfo = canfit
- canrelocate.remove(fixedaddrinfo)
- fitsection, inlist = fixedaddrinfo
- inlist.remove(fitsection)
- extrasections.append(fitsection)
+ fitnextaddr, fitsection = canfit
+ canrelocate.remove(fitsection)
+ fitsection.finalloc = addpos
addpos = fitnextaddr
- totalused += fitsection[0]
+ totalused += fitsection.size
# print " Adding %s (size %d align %d) pos=%x avail=%d" % (
# fitsection[2], fitsection[0], fitsection[1]
# , fitnextaddr, nextfixedaddr - fitnextaddr)
- firstfixed = fixedsections[0][0]
- total = MAXPOS-firstfixed
- print "Fixed space: 0x%x-0x%x total: %d used: %d Percent used: %.1f%%" % (
- firstfixed, MAXPOS, total, totalused,
- (float(totalused) / total) * 100.0)
-
- # Write regular sections
- output = open(outname, 'wb')
- for section in textsections:
- name = section[2]
- output.write("*(%s)\n" % (name,))
- output.write("code16_rodata = . ;\n")
- for section in rodatasections:
- name = section[2]
- output.write("*(%s)\n" % (name,))
- for section in datasections:
- name = section[2]
- output.write("*(%s)\n" % (name,))
-
- # Write fixed sections
- output.write("freespace1_start = . ;\n")
- first = 1
- for addr, section, extrasections in fixedsections:
- name = section[2]
- output.write(". = ( 0x%x - code16_start ) ;\n" % (addr,))
- if first:
- first = 0
- output.write("freespace1_end = . ;\n")
- output.write("*(%s)\n" % (name,))
- for extrasection in extrasections:
- name = extrasection[2]
- output.write("*(%s)\n" % (name,))
+ # Report stats
+ total = BUILD_BIOS_SIZE-firstfixed
+ slack = total - totalused
+ print ("Fixed space: 0x%x-0x%x total: %d slack: %d"
+ " Percent slack: %.1f%%" % (
+ firstfixed, BUILD_BIOS_SIZE, total, slack,
+ (float(slack) / total) * 100.0))
+
+ return firstfixed
+
+# Return the subset of sections with a given name prefix
+def getSectionsPrefix(sections, category, prefix):
+ return [section for section in sections
+ if section.category == category and section.name.startswith(prefix)]
+
+def doLayout(sections):
+ # Determine 16bit positions
+ textsections = getSectionsPrefix(sections, '16', '.text.')
+ rodatasections = (getSectionsPrefix(sections, '16', '.rodata.str1.1')
+ + getSectionsPrefix(sections, '16', '.rodata.__func__.'))
+ datasections = getSectionsPrefix(sections, '16', '.data16.')
+ fixedsections = getSectionsPrefix(sections, '16', '.fixedaddr.')
+
+ firstfixed = fitSections(fixedsections, textsections)
+ remsections = [s for s in textsections+rodatasections+datasections
+ if s.finalloc is None]
+ code16_start = setSectionsStart(remsections, firstfixed)
+
+ # Determine 32seg positions
+ textsections = getSectionsPrefix(sections, '32seg', '.text.')
+ rodatasections = (getSectionsPrefix(sections, '32seg', '.rodata.str1.1')
+ +getSectionsPrefix(sections, '32seg', '.rodata.__func__.'))
+ datasections = getSectionsPrefix(sections, '32seg', '.data32seg.')
+
+ code32seg_start = setSectionsStart(
+ textsections + rodatasections + datasections, code16_start)
+
+ # Determine 32flat runtime positions
+ textsections = getSectionsPrefix(sections, '32flat', '.text.')
+ rodatasections = getSectionsPrefix(sections, '32flat', '.rodata')
+ datasections = getSectionsPrefix(sections, '32flat', '.data.')
+ bsssections = getSectionsPrefix(sections, '32flat', '.bss.')
+
+ code32flat_start = setSectionsStart(
+ textsections + rodatasections + datasections + bsssections
+ , code32seg_start + BUILD_BIOS_ADDR, 16)
+
+ # Determine 32flat init positions
+ textsections = getSectionsPrefix(sections, '32init', '.text.')
+ rodatasections = getSectionsPrefix(sections, '32init', '.rodata')
+ datasections = getSectionsPrefix(sections, '32init', '.data.')
+ bsssections = getSectionsPrefix(sections, '32init', '.bss.')
+
+ code32init_start = setSectionsStart(
+ textsections + rodatasections + datasections + bsssections
+ , code32flat_start, 16)
+
+ # Print statistics
+ size16 = BUILD_BIOS_SIZE - code16_start
+ size32seg = code16_start - code32seg_start
+ size32flat = code32seg_start + BUILD_BIOS_ADDR - code32flat_start
+ size32init = code32flat_start - code32init_start
+ print "16bit size: %d" % size16
+ print "32bit segmented size: %d" % size32seg
+ print "32bit flat size: %d" % size32flat
+ print "32bit flat init size: %d" % size32init
+
+
+######################################################################
+# Linker script output
+######################################################################
+
+# Write LD script includes for the given cross references
+def outXRefs(sections):
+ xrefs = {}
+ out = ""
+ for section in sections:
+ for reloc in section.relocs:
+ symbol = reloc.symbol
+ if (symbol.section is None
+ or (symbol.section.fileid == section.fileid
+ and symbol.name == reloc.symbolname)
+ or reloc.symbolname in xrefs):
+ continue
+ xrefs[reloc.symbolname] = 1
+ addr = symbol.section.finalloc + symbol.offset
+ if (section.fileid == '32flat'
+ and symbol.section.fileid in ('16', '32seg')):
+ addr += BUILD_BIOS_ADDR
+ out += "%s = 0x%x ;\n" % (reloc.symbolname, addr)
+ return out
+
+# Write LD script includes for the given sections using relative offsets
+def outRelSections(sections, startsym):
+ out = ""
+ for section in sections:
+ out += ". = ( 0x%x - %s ) ;\n" % (section.finalloc, startsym)
+ if section.name == '.rodata.str1.1':
+ out += "_rodata = . ;\n"
+ out += "*(%s)\n" % (section.name,)
+ return out
+
+def getSectionsFile(sections, fileid, defaddr=0):
+ sections = [(section.finalloc, section)
+ for section in sections if section.fileid == fileid]
+ sections.sort()
+ sections = [section for addr, section in sections]
+ pos = defaddr
+ if sections:
+ pos = sections[0].finalloc
+ return sections, pos
+
+# Layout the 32bit segmented code. This places the code as high as possible.
+def writeLinkerScripts(sections, entrysym, genreloc, out16, out32seg, out32flat):
+ # Write 16bit linker script
+ sections16, code16_start = getSectionsFile(sections, '16')
+ output = open(out16, 'wb')
+ output.write(COMMONHEADER + outXRefs(sections16) + """
+ code16_start = 0x%x ;
+ .text16 code16_start : {
+""" % (code16_start)
+ + outRelSections(sections16, 'code16_start')
+ + """
+ }
+"""
+ + COMMONTRAILER)
+ output.close()
+
+ # Write 32seg linker script
+ sections32seg, code32seg_start = getSectionsFile(
+ sections, '32seg', code16_start)
+ output = open(out32seg, 'wb')
+ output.write(COMMONHEADER + outXRefs(sections32seg) + """
+ code32seg_start = 0x%x ;
+ .text32seg code32seg_start : {
+""" % (code32seg_start)
+ + outRelSections(sections32seg, 'code32seg_start')
+ + """
+ }
+"""
+ + COMMONTRAILER)
+ output.close()
+
+ # Write 32flat linker script
+ sections32flat, code32flat_start = getSectionsFile(
+ sections, '32flat', code32seg_start)
+ relocstr = ""
+ relocminalign = 0
+ if genreloc:
+ # Generate relocations
+ relocstr, size, relocminalign = genRelocs(sections)
+ code32flat_start -= size
+ output = open(out32flat, 'wb')
+ output.write(COMMONHEADER
+ + outXRefs(sections32flat) + """
+ %s = 0x%x ;
+ _reloc_min_align = 0x%x ;
+ code32flat_start = 0x%x ;
+ .text code32flat_start : {
+""" % (entrysym.name,
+ entrysym.section.finalloc + entrysym.offset + BUILD_BIOS_ADDR,
+ relocminalign, code32flat_start)
+ + relocstr
+ + """
+ code32init_start = ABSOLUTE(.) ;
+"""
+ + outRelSections(getSectionsPrefix(sections32flat, '32init', '')
+ , 'code32flat_start')
+ + """
+ code32init_end = ABSOLUTE(.) ;
+"""
+ + outRelSections(getSectionsPrefix(sections32flat, '32flat', '')
+ , 'code32flat_start')
+ + """
+ . = ( 0x%x - code32flat_start ) ;
+ *(.text32seg)
+ . = ( 0x%x - code32flat_start ) ;
+ *(.text16)
+ code32flat_end = ABSOLUTE(.) ;
+ } :text
+""" % (code32seg_start + BUILD_BIOS_ADDR, code16_start + BUILD_BIOS_ADDR)
+ + COMMONTRAILER
+ + """
+ENTRY(%s)
+PHDRS
+{
+ text PT_LOAD AT ( code32flat_start ) ;
+}
+""" % (entrysym.name,))
+ output.close()
+
+
+######################################################################
+# Detection of init code
+######################################################################
+
+# Determine init section relocations
+def genRelocs(sections):
+ absrelocs = []
+ relrelocs = []
+ initrelocs = []
+ minalign = 16
+ for section in sections:
+ if section.category == '32init' and section.align > minalign:
+ minalign = section.align
+ for reloc in section.relocs:
+ symbol = reloc.symbol
+ if symbol.section is None:
+ continue
+ relocpos = section.finalloc + reloc.offset
+ if (reloc.type == 'R_386_32' and section.category == '32init'
+ and symbol.section.category == '32init'):
+ # Absolute relocation
+ absrelocs.append(relocpos)
+ elif (reloc.type == 'R_386_PC32' and section.category == '32init'
+ and symbol.section.category != '32init'):
+ # Relative relocation
+ relrelocs.append(relocpos)
+ elif (section.category != '32init'
+ and symbol.section.category == '32init'):
+ # Relocation to the init section
+ if section.fileid in ('16', '32seg'):
+ relocpos += BUILD_BIOS_ADDR
+ initrelocs.append(relocpos)
+ absrelocs.sort()
+ relrelocs.sort()
+ initrelocs.sort()
+ out = (" _reloc_abs_start = ABSOLUTE(.) ;\n"
+ + "".join(["LONG(0x%x - code32init_start)\n" % (pos,)
+ for pos in absrelocs])
+ + " _reloc_abs_end = ABSOLUTE(.) ;\n"
+ + " _reloc_rel_start = ABSOLUTE(.) ;\n"
+ + "".join(["LONG(0x%x - code32init_start)\n" % (pos,)
+ for pos in relrelocs])
+ + " _reloc_rel_end = ABSOLUTE(.) ;\n"
+ + " _reloc_init_start = ABSOLUTE(.) ;\n"
+ + "".join(["LONG(0x%x - code32flat_start)\n" % (pos,)
+ for pos in initrelocs])
+ + " _reloc_init_end = ABSOLUTE(.) ;\n")
+ return out, len(absrelocs + relrelocs + initrelocs) * 4, minalign
+
+def markRuntime(section, sections):
+ if (section is None or not section.keep or section.category is not None
+ or '.init.' in section.name or section.fileid != '32flat'):
+ return
+ section.category = '32flat'
+ # Recursively mark all sections this section points to
+ for reloc in section.relocs:
+ markRuntime(reloc.symbol.section, sections)
+
+def findInit(sections):
+ # Recursively find and mark all "runtime" sections.
+ for section in sections:
+ if '.runtime.' in section.name or '.export.' in section.name:
+ markRuntime(section, sections)
+ for section in sections:
+ if section.category is not None:
+ continue
+ if section.fileid == '32flat':
+ section.category = '32init'
+ else:
+ section.category = section.fileid
+
+
+######################################################################
+# Section garbage collection
+######################################################################
+
+CFUNCPREFIX = [('_cfunc16_', 0), ('_cfunc32seg_', 1), ('_cfunc32flat_', 2)]
+
+# Find and keep the section associated with a symbol (if available).
+def keepsymbol(reloc, infos, pos, isxref):
+ symbolname = reloc.symbolname
+ mustbecfunc = 0
+ for symprefix, needpos in CFUNCPREFIX:
+ if symbolname.startswith(symprefix):
+ if needpos != pos:
+ return -1
+ symbolname = symbolname[len(symprefix):]
+ mustbecfunc = 1
+ break
+ symbol = infos[pos][1].get(symbolname)
+ if (symbol is None or symbol.section is None
+ or symbol.section.name.startswith('.discard.')):
+ return -1
+ isdestcfunc = (symbol.section.name.startswith('.text.')
+ and not symbol.section.name.startswith('.text.asm.'))
+ if ((mustbecfunc and not isdestcfunc)
+ or (not mustbecfunc and isdestcfunc and isxref)):
+ return -1
+
+ reloc.symbol = symbol
+ keepsection(symbol.section, infos, pos)
+ return 0
+
+# Note required section, and recursively set all referenced sections
+# as required.
+def keepsection(section, infos, pos=0):
+ if section.keep:
+ # Already kept - nothing to do.
+ return
+ section.keep = 1
+ # Keep all sections that this section points to
+ for reloc in section.relocs:
+ ret = keepsymbol(reloc, infos, pos, 0)
+ if not ret:
+ continue
+ # Not in primary sections - it may be a cross 16/32 reference
+ ret = keepsymbol(reloc, infos, (pos+1)%3, 1)
+ if not ret:
+ continue
+ ret = keepsymbol(reloc, infos, (pos+2)%3, 1)
+ if not ret:
+ continue
+
+# Determine which sections are actually referenced and need to be
+# placed into the output file.
+def gc(info16, info32seg, info32flat):
+ # infos = ((sections16, symbols16), (sect32seg, sym32seg)
+ # , (sect32flat, sym32flat))
+ infos = (info16, info32seg, info32flat)
+ # Start by keeping sections that are globally visible.
+ for section in info16[0]:
+ if section.name.startswith('.fixedaddr.') or '.export.' in section.name:
+ keepsection(section, infos)
+ return [section for section in info16[0]+info32seg[0]+info32flat[0]
+ if section.keep]
+
+
+######################################################################
+# Startup and input parsing
+######################################################################
+
+class Section:
+ name = size = alignment = fileid = relocs = None
+ finalloc = category = keep = None
+class Reloc:
+ offset = type = symbolname = symbol = None
+class Symbol:
+ name = offset = section = None
+
+# Read in output from objdump
+def parseObjDump(file, fileid):
+ # sections = [section, ...]
+ sections = []
+ sectionmap = {}
+ # symbols[symbolname] = symbol
+ symbols = {}
+
+ state = None
+ for line in file.readlines():
+ line = line.rstrip()
+ if line == 'Sections:':
+ state = 'section'
+ continue
+ if line == 'SYMBOL TABLE:':
+ state = 'symbol'
+ continue
+ if line.startswith('RELOCATION RECORDS FOR ['):
+ sectionname = line[24:-2]
+ if sectionname.startswith('.debug_'):
+ # Skip debugging sections (to reduce parsing time)
+ state = None
+ continue
+ state = 'reloc'
+ relocsection = sectionmap[sectionname]
+ continue
+
+ if state == 'section':
+ try:
+ idx, name, size, vma, lma, fileoff, align = line.split()
+ if align[:3] != '2**':
+ continue
+ section = Section()
+ section.name = name
+ section.size = int(size, 16)
+ section.align = 2**int(align[3:])
+ section.fileid = fileid
+ section.relocs = []
+ sections.append(section)
+ sectionmap[name] = section
+ except ValueError:
+ pass
+ continue
+ if state == 'symbol':
+ try:
+ sectionname, size, name = line[17:].split()
+ symbol = Symbol()
+ symbol.size = int(size, 16)
+ symbol.offset = int(line[:8], 16)
+ symbol.name = name
+ symbol.section = sectionmap.get(sectionname)
+ symbols[name] = symbol
+ except ValueError:
+ pass
+ continue
+ if state == 'reloc':
+ try:
+ off, type, symbolname = line.split()
+ reloc = Reloc()
+ reloc.offset = int(off, 16)
+ reloc.type = type
+ reloc.symbolname = symbolname
+ reloc.symbol = symbols.get(symbolname)
+ if reloc.symbol is None:
+ # Some binutils (2.20.1) give section name instead
+ # of a symbol - create a dummy symbol.
+ reloc.symbol = symbol = Symbol()
+ symbol.size = 0
+ symbol.offset = 0
+ symbol.name = symbolname
+ symbol.section = sectionmap.get(symbolname)
+ symbols[symbolname] = symbol
+ relocsection.relocs.append(reloc)
+ except ValueError:
+ pass
+ return sections, symbols
+
+def main():
+ # Get output name
+ in16, in32seg, in32flat, out16, out32seg, out32flat = sys.argv[1:]
+
+ # Read in the objdump information
+ infile16 = open(in16, 'rb')
+ infile32seg = open(in32seg, 'rb')
+ infile32flat = open(in32flat, 'rb')
+
+ # infoX = (sections, symbols)
+ info16 = parseObjDump(infile16, '16')
+ info32seg = parseObjDump(infile32seg, '32seg')
+ info32flat = parseObjDump(infile32flat, '32flat')
+
+ # Figure out which sections to keep.
+ sections = gc(info16, info32seg, info32flat)
+
+ # Separate 32bit flat into runtime and init parts
+ findInit(sections)
+
+ # Determine the final memory locations of each kept section.
+ doLayout(sections)
+
+ # Write out linker script files.
+ entrysym = info16[1]['entry_elf']
+ genreloc = '_reloc_abs_start' in info32flat[1]
+ writeLinkerScripts(sections, entrysym, genreloc, out16, out32seg, out32flat)
if __name__ == '__main__':
main()