Subversion Repositories lxp32

/*

 * Copyright (c) 2016 by Alex I. Kuznetsov.

 *

 * Part of the LXP32 CPU IP core.

 *

 * This module implements members of the Linker class.

 */

#include "linker.h"

#include "linkableobject.h"

#include "utils.h"

#include <iostream>

#include <fstream>

#include <sstream>

#include <map>

#include <stdexcept>

#include <cassert>

#include <algorithm>

void Linker::addObject(LinkableObject &obj) {

        _objects.push_back(&obj);

}

void Linker::link(OutputWriter &writer) {

        if(_objects.empty()) throw std::runtime_error("Object set is empty");

// Merge symbol tables

        buildSymbolTable();

// Determine entry point

        if(_objects.size()==1) _entryObject=_objects[0];

        else if(_entryObject==nullptr)

                throw std::runtime_error("Entry point not defined: cannot find \"entry\" or \"Entry\" symbol");

// Assign virtual addresses

        placeObjects();

// Perform relocations

        for(auto &obj: _objects) relocateObject(obj);

// Write binary data

        writeObjects(writer);

        _bytesWritten=writer.size();

}

void Linker::setBase(LinkableObject::Word base) {

        _base=base;

}

void Linker::setAlignment(std::size_t align) {

        _align=align;

}

void Linker::setImageSize(std::size_t size) {

        _imageSize=size;

}

void Linker::generateMap(std::ostream &s) {

// Calculate the maximum length of a symbol name

        std::size_t len=0;

        for(auto const &obj: _objects) {

                for(auto const &sym: obj->symbols()) {

                        if(sym.second.type!=LinkableObject::Imported)

                                len=std::max(len,sym.first.size());

                }

        }

        len=std::max(len+3,std::size_t(8)); // width of the first column

        s<<"Image base address: "<<Utils::hex(_base)<<std::endl;

        s<<"Object alignment: "<<_align<<std::endl;

        s<<"Image size: "<<(_bytesWritten/4)<<" words"<<std::endl;

        s<<"Number of objects: "<<_objects.size()<<std::endl;

        s<<std::endl;

        for(auto const &obj: _objects) {

                s<<"Object \""<<obj->name()<<"\" at address "<<Utils::hex(obj->virtualAddress())<<std::endl;

                s<<std::endl;

                std::multimap<LinkableObject::Word,std::pair<std::string,LinkableObject::SymbolData> > sorted;

                for(auto const &sym: obj->symbols()) sorted.emplace(sym.second.rva,sym);

                for(auto const &sym: sorted) {

                        if(sym.second.second.type==LinkableObject::Imported) continue;

                        s<<sym.second.first;

                        s<<std::string(len-sym.second.first.size(),' ');

                        s<<Utils::hex(obj->virtualAddress()+sym.second.second.rva);

                        if(sym.second.second.type==LinkableObject::Local) s<<" Local";

                        else s<<" Exported";

                        s<<std::endl;

                }

                s<<std::endl;

        }

}

/*

 * Private members

 */

void Linker::buildSymbolTable() {

        _globalSymbolTable.clear();

// Build a table of exported symbols from all modules

        for(auto const &obj: _objects) {

                auto const &table=obj->symbols();

                for(auto const &item: table) {

                        if((item.first=="entry"||item.first=="Entry")&&item.second.type!=LinkableObject::Imported) {

                                if(_entryObject) {

                                        std::ostringstream msg;

                                        msg<<obj->name()<<": Duplicate definition of the entry symbol ";

                                        msg<<"(previously defined in "<<_entryObject->name()<<")";

                                        throw std::runtime_error(msg.str());

                                }

                                if(item.second.rva!=0) {

                                        std::ostringstream msg;

                                        msg<<obj->name()<<": ";

                                        msg<<"Entry point must refer to the start of the object";

                                        throw std::runtime_error(msg.str());

                                }

                                _entryObject=obj;

                        }

                        if(item.second.type==LinkableObject::Local) continue;

// Insert item to the global symbol table if it doesn't exist yet

                        auto it=_globalSymbolTable.emplace(item.first,GlobalSymbolData()).first;

// Check that the symbol has not been already defined in another object

                        if(item.second.type==LinkableObject::Exported) {

                                if(it->second.obj) {

                                        std::ostringstream msg;

                                        msg<<obj->name()<<": Duplicate definition of \""<<item.first;

                                        msg<<"\" (previously defined in "<<it->second.obj->name()<<")";

                                        throw std::runtime_error(msg.str());

                                }

                                it->second.obj=obj;

                                it->second.rva=item.second.rva;

                        }

                        if(!item.second.refs.empty()) it->second.refs.insert(obj);

                }

        }

// Check that local symbols don't shadow the public ones

        for(auto const &obj: _objects) {

                auto const &table=obj->symbols();

                for(auto const &item: table) {

                        if(item.second.type!=LinkableObject::Local) continue;

                        auto it=_globalSymbolTable.find(item.first);

                        if(it==_globalSymbolTable.end()) continue;

                        if(!it->second.obj) continue;

                        if(item.first==it->first) {

                                std::ostringstream msg;

                                msg<<obj->name()<<": Local symbol \""<<item.first<<"\" shadows the public one ";

                                msg<<"(defined in "<<it->second.obj->name()<<")";

                                throw std::runtime_error(msg.str());

                        }

                }

        }

// Check that no undefined symbols remain

        for(auto const &item: _globalSymbolTable) {

                if(item.second.obj==nullptr&&!item.second.refs.empty()) {

                        std::ostringstream msg;

                        msg<<"Undefined symbol: \""<<item.first<<"\"";

                        auto const it=item.second.refs.begin();

                        msg<<" (referenced from "<<(*it)->name()<<")";

                        throw std::runtime_error(msg.str());

                }

        }

}

void Linker::placeObjects() {

        auto currentBase=_base;

// Make entry object the first

        if(_objects.size()>1) {

                for(auto it=_objects.begin();it!=_objects.end();++it) {

                        if(*it==_entryObject) {

                                _objects.erase(it);

                                break;

                        }

                }

                _objects.insert(_objects.begin(),_entryObject);

        }

// Remove unreferenced objects

        if(_objects.size()>1) {

                std::set<const LinkableObject*> used;

                markAsUsed(_objects[0],used);

                for(auto it=_objects.begin();it!=_objects.end();) {

                        if(used.find(*it)==used.end()) {

                                std::cerr<<"Linker warning: skipping an unreferenced object \"";

                                std::cerr<<(*it)->name()<<"\""<<std::endl;

                                for(auto sym=_globalSymbolTable.begin();sym!=_globalSymbolTable.end();) {

                                        if(sym->second.obj==*it) sym=_globalSymbolTable.erase(sym);

                                        else ++sym;

                                }

                                it=_objects.erase(it);

                        }

                        else ++it;

                }

        }

// Set base addresses

        for(auto it=_objects.begin();it!=_objects.end();++it) {

                (*it)->setVirtualAddress(currentBase);

                if(it+1!=_objects.end()) (*it)->addPadding(_align);

                else (*it)->addPadding();

                currentBase+=static_cast<LinkableObject::Word>((*it)->codeSize());

        }

}

void Linker::relocateObject(LinkableObject *obj) {

        for(auto const &sym: obj->symbols()) {

                LinkableObject::Word addr;

                if(sym.second.refs.empty()) continue;

                if(sym.second.type==LinkableObject::Local) addr=obj->virtualAddress()+sym.second.rva;

                else {

                        auto it=_globalSymbolTable.find(sym.first);

                        assert(it!=_globalSymbolTable.end());

                        assert(it->second.obj);

                        addr=it->second.obj->virtualAddress()+it->second.rva;

                }

                for(auto const &ref: sym.second.refs) {

                        if(ref.type==LinkableObject::Regular) obj->replaceWord(ref.rva,addr+ref.offset);

                        else {

                                auto target=static_cast<LinkableObject::Word>(addr+ref.offset);

                                if(target>0xFFFFF&&target<0xFFF00000) {

                                        std::ostringstream msg;

                                        msg<<"Address 0x"<<Utils::hex(target)<<" is out of the range for a short reference";

                                        msg<<" (referenced from "<<ref.source<<":"<<ref.line<<")";

                                        throw std::runtime_error(msg.str());

                                }

                                target&=0x1FFFFF;

                                auto w=obj->getWord(ref.rva);

                                w|=(target&0xFFFF);

                                w|=((target<<8)&0x1F000000);

                                obj->replaceWord(ref.rva,w);

                        }

                }

        }

}

void Linker::writeObjects(OutputWriter &writer) {

        std::size_t currentSize=0;

// Write entry object

        writer.write(reinterpret_cast<const char*>(_entryObject->code()),_entryObject->codeSize());

        currentSize+=_entryObject->codeSize();

// Write other objects

        for(auto const &obj: _objects) {

                if(obj==_entryObject) continue;

                writer.write(reinterpret_cast<const char*>(obj->code()),obj->codeSize());

                currentSize+=obj->codeSize();

        }

// Pad file if requested

        if(_imageSize>0) {

                if(currentSize>_imageSize)

                        throw std::runtime_error("Image size exceeds the specified value");

                else if(currentSize<_imageSize) writer.pad(_imageSize-currentSize);

        }

}

void Linker::markAsUsed(const LinkableObject *obj,std::set<const LinkableObject*> &used) {

        if(used.find(obj)!=used.end()) return; // already processed

        used.insert(obj);

        for(auto const &sym: _globalSymbolTable) {

                for(auto const &ref: sym.second.refs) {

                        if(ref==obj) markAsUsed(sym.second.obj,used);

                }

        }

}