/*
|
/*
|
* Copyright (c) 2016 by Alex I. Kuznetsov.
|
* Copyright (c) 2016 by Alex I. Kuznetsov.
|
*
|
*
|
* Part of the LXP32 CPU IP core.
|
* Part of the LXP32 CPU IP core.
|
*
|
*
|
* This module implements members of the Linker class.
|
* This module implements members of the Linker class.
|
*/
|
*/
|
|
|
#include "linker.h"
|
#include "linker.h"
|
|
|
#include "linkableobject.h"
|
#include "linkableobject.h"
|
#include "utils.h"
|
#include "utils.h"
|
|
|
#include <iostream>
|
#include <iostream>
|
#include <fstream>
|
#include <fstream>
|
#include <sstream>
|
#include <sstream>
|
#include <map>
|
#include <map>
|
#include <stdexcept>
|
#include <stdexcept>
|
#include <cassert>
|
#include <cassert>
|
#include <algorithm>
|
#include <algorithm>
|
|
|
void Linker::addObject(LinkableObject &obj) {
|
void Linker::addObject(LinkableObject &obj) {
|
_objects.push_back(&obj);
|
_objects.push_back(&obj);
|
}
|
}
|
|
|
void Linker::link(OutputWriter &writer) {
|
void Linker::link(OutputWriter &writer) {
|
if(_objects.empty()) throw std::runtime_error("Object set is empty");
|
if(_objects.empty()) throw std::runtime_error("Object set is empty");
|
|
|
// Merge symbol tables
|
// Merge symbol tables
|
buildSymbolTable();
|
buildSymbolTable();
|
|
|
// Determine entry point
|
// Determine entry point
|
if(_objects.size()==1) _entryObject=_objects[0];
|
if(_objects.size()==1) _entryObject=_objects[0];
|
else if(_entryObject==nullptr)
|
else if(_entryObject==nullptr)
|
throw std::runtime_error("Entry point not defined: cannot find \"entry\" or \"Entry\" symbol");
|
throw std::runtime_error("Entry point not defined: cannot find \"entry\" or \"Entry\" symbol");
|
|
|
// Assign virtual addresses
|
// Assign virtual addresses
|
placeObjects();
|
placeObjects();
|
|
|
// Perform relocations
|
// Perform relocations
|
for(auto &obj: _objects) relocateObject(obj);
|
for(auto &obj: _objects) relocateObject(obj);
|
|
|
// Write binary data
|
// Write binary data
|
writeObjects(writer);
|
writeObjects(writer);
|
_bytesWritten=writer.size();
|
_bytesWritten=writer.size();
|
}
|
}
|
|
|
void Linker::setBase(LinkableObject::Word base) {
|
void Linker::setBase(LinkableObject::Word base) {
|
_base=base;
|
_base=base;
|
}
|
}
|
|
|
void Linker::setAlignment(std::size_t align) {
|
void Linker::setAlignment(std::size_t align) {
|
_align=align;
|
_align=align;
|
}
|
}
|
|
|
void Linker::setImageSize(std::size_t size) {
|
void Linker::setImageSize(std::size_t size) {
|
_imageSize=size;
|
_imageSize=size;
|
}
|
}
|
|
|
void Linker::generateMap(std::ostream &s) {
|
void Linker::generateMap(std::ostream &s) {
|
// Calculate the maximum length of a symbol name
|
// Calculate the maximum length of a symbol name
|
std::size_t len=0;
|
std::size_t len=0;
|
for(auto const &obj: _objects) {
|
for(auto const &obj: _objects) {
|
for(auto const &sym: obj->symbols()) {
|
for(auto const &sym: obj->symbols()) {
|
if(sym.second.type!=LinkableObject::Imported)
|
if(sym.second.type!=LinkableObject::Imported)
|
len=std::max(len,sym.first.size());
|
len=std::max(len,sym.first.size());
|
}
|
}
|
}
|
}
|
len=std::max(len+3,std::size_t(8)); // width of the first column
|
len=std::max(len+3,std::size_t(8)); // width of the first column
|
|
|
s<<"Image base address: "<<Utils::hex(_base)<<std::endl;
|
s<<"Image base address: "<<Utils::hex(_base)<<std::endl;
|
s<<"Object alignment: "<<_align<<std::endl;
|
s<<"Object alignment: "<<_align<<std::endl;
|
s<<"Image size: "<<(_bytesWritten/4)<<" words"<<std::endl;
|
s<<"Image size: "<<(_bytesWritten/4)<<" words"<<std::endl;
|
s<<"Number of objects: "<<_objects.size()<<std::endl;
|
s<<"Number of objects: "<<_objects.size()<<std::endl;
|
s<<std::endl;
|
s<<std::endl;
|
|
|
for(auto const &obj: _objects) {
|
for(auto const &obj: _objects) {
|
s<<"Object \""<<obj->name()<<"\" at address "<<Utils::hex(obj->virtualAddress())<<std::endl;
|
s<<"Object \""<<obj->name()<<"\" at address "<<Utils::hex(obj->virtualAddress())<<std::endl;
|
s<<std::endl;
|
s<<std::endl;
|
std::multimap<LinkableObject::Word,std::pair<std::string,LinkableObject::SymbolData> > sorted;
|
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: obj->symbols()) sorted.emplace(sym.second.rva,sym);
|
for(auto const &sym: sorted) {
|
for(auto const &sym: sorted) {
|
if(sym.second.second.type==LinkableObject::Imported) continue;
|
if(sym.second.second.type==LinkableObject::Imported) continue;
|
s<<sym.second.first;
|
s<<sym.second.first;
|
s<<std::string(len-sym.second.first.size(),' ');
|
s<<std::string(len-sym.second.first.size(),' ');
|
s<<Utils::hex(obj->virtualAddress()+sym.second.second.rva);
|
s<<Utils::hex(obj->virtualAddress()+sym.second.second.rva);
|
if(sym.second.second.type==LinkableObject::Local) s<<" Local";
|
if(sym.second.second.type==LinkableObject::Local) s<<" Local";
|
else s<<" Exported";
|
else s<<" Exported";
|
s<<std::endl;
|
s<<std::endl;
|
}
|
}
|
s<<std::endl;
|
s<<std::endl;
|
}
|
}
|
}
|
}
|
|
|
/*
|
/*
|
* Private members
|
* Private members
|
*/
|
*/
|
|
|
void Linker::buildSymbolTable() {
|
void Linker::buildSymbolTable() {
|
_globalSymbolTable.clear();
|
_globalSymbolTable.clear();
|
|
|
// Build a table of exported symbols from all modules
|
// Build a table of exported symbols from all modules
|
for(auto const &obj: _objects) {
|
for(auto const &obj: _objects) {
|
auto const &table=obj->symbols();
|
auto const &table=obj->symbols();
|
for(auto const &item: table) {
|
for(auto const &item: table) {
|
if((item.first=="entry"||item.first=="Entry")&&item.second.type!=LinkableObject::Imported) {
|
if((item.first=="entry"||item.first=="Entry")&&item.second.type!=LinkableObject::Imported) {
|
if(_entryObject) {
|
if(_entryObject) {
|
std::ostringstream msg;
|
std::ostringstream msg;
|
msg<<obj->name()<<": Duplicate definition of the entry symbol ";
|
msg<<obj->name()<<": Duplicate definition of the entry symbol ";
|
msg<<"(previously defined in "<<_entryObject->name()<<")";
|
msg<<"(previously defined in "<<_entryObject->name()<<")";
|
throw std::runtime_error(msg.str());
|
throw std::runtime_error(msg.str());
|
}
|
}
|
if(item.second.rva!=0) {
|
if(item.second.rva!=0) {
|
std::ostringstream msg;
|
std::ostringstream msg;
|
msg<<obj->name()<<": ";
|
msg<<obj->name()<<": ";
|
msg<<"Entry point must refer to the start of the object";
|
msg<<"Entry point must refer to the start of the object";
|
throw std::runtime_error(msg.str());
|
throw std::runtime_error(msg.str());
|
}
|
}
|
_entryObject=obj;
|
_entryObject=obj;
|
}
|
}
|
if(item.second.type==LinkableObject::Local) continue;
|
if(item.second.type==LinkableObject::Local) continue;
|
// Insert item to the global symbol table if it doesn't exist yet
|
// Insert item to the global symbol table if it doesn't exist yet
|
auto it=_globalSymbolTable.emplace(item.first,GlobalSymbolData()).first;
|
auto it=_globalSymbolTable.emplace(item.first,GlobalSymbolData()).first;
|
|
|
// Check that the symbol has not been already defined in another object
|
// Check that the symbol has not been already defined in another object
|
if(item.second.type==LinkableObject::Exported) {
|
if(item.second.type==LinkableObject::Exported) {
|
if(it->second.obj) {
|
if(it->second.obj) {
|
std::ostringstream msg;
|
std::ostringstream msg;
|
msg<<obj->name()<<": Duplicate definition of \""<<item.first;
|
msg<<obj->name()<<": Duplicate definition of \""<<item.first;
|
msg<<"\" (previously defined in "<<it->second.obj->name()<<")";
|
msg<<"\" (previously defined in "<<it->second.obj->name()<<")";
|
throw std::runtime_error(msg.str());
|
throw std::runtime_error(msg.str());
|
}
|
}
|
it->second.obj=obj;
|
it->second.obj=obj;
|
it->second.rva=item.second.rva;
|
it->second.rva=item.second.rva;
|
}
|
}
|
|
|
if(!item.second.refs.empty()) it->second.refs.insert(obj);
|
if(!item.second.refs.empty()) it->second.refs.insert(obj);
|
}
|
}
|
}
|
}
|
|
|
// Check that local symbols don't shadow the public ones
|
// Check that local symbols don't shadow the public ones
|
for(auto const &obj: _objects) {
|
for(auto const &obj: _objects) {
|
auto const &table=obj->symbols();
|
auto const &table=obj->symbols();
|
for(auto const &item: table) {
|
for(auto const &item: table) {
|
if(item.second.type!=LinkableObject::Local) continue;
|
if(item.second.type!=LinkableObject::Local) continue;
|
auto it=_globalSymbolTable.find(item.first);
|
auto it=_globalSymbolTable.find(item.first);
|
if(it==_globalSymbolTable.end()) continue;
|
if(it==_globalSymbolTable.end()) continue;
|
if(!it->second.obj) continue;
|
if(!it->second.obj) continue;
|
if(item.first==it->first) {
|
if(item.first==it->first) {
|
std::ostringstream msg;
|
std::ostringstream msg;
|
msg<<obj->name()<<": Local symbol \""<<item.first<<"\" shadows the public one ";
|
msg<<obj->name()<<": Local symbol \""<<item.first<<"\" shadows the public one ";
|
msg<<"(defined in "<<it->second.obj->name()<<")";
|
msg<<"(defined in "<<it->second.obj->name()<<")";
|
throw std::runtime_error(msg.str());
|
throw std::runtime_error(msg.str());
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
// Check that no undefined symbols remain
|
// Check that no undefined symbols remain
|
for(auto const &item: _globalSymbolTable) {
|
for(auto const &item: _globalSymbolTable) {
|
if(item.second.obj==nullptr&&!item.second.refs.empty()) {
|
if(item.second.obj==nullptr&&!item.second.refs.empty()) {
|
std::ostringstream msg;
|
std::ostringstream msg;
|
msg<<"Undefined symbol: \""<<item.first<<"\"";
|
msg<<"Undefined symbol: \""<<item.first<<"\"";
|
auto const it=item.second.refs.begin();
|
auto const it=item.second.refs.begin();
|
msg<<" (referenced from "<<(*it)->name()<<")";
|
msg<<" (referenced from "<<(*it)->name()<<")";
|
throw std::runtime_error(msg.str());
|
throw std::runtime_error(msg.str());
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
void Linker::placeObjects() {
|
void Linker::placeObjects() {
|
auto currentBase=_base;
|
auto currentBase=_base;
|
|
|
// Make entry object the first
|
// Make entry object the first
|
if(_objects.size()>1) {
|
if(_objects.size()>1) {
|
for(auto it=_objects.begin();it!=_objects.end();++it) {
|
for(auto it=_objects.begin();it!=_objects.end();++it) {
|
if(*it==_entryObject) {
|
if(*it==_entryObject) {
|
_objects.erase(it);
|
_objects.erase(it);
|
break;
|
break;
|
}
|
}
|
}
|
}
|
_objects.insert(_objects.begin(),_entryObject);
|
_objects.insert(_objects.begin(),_entryObject);
|
}
|
}
|
|
|
// Remove unreferenced objects
|
// Remove unreferenced objects
|
if(_objects.size()>1) {
|
if(_objects.size()>1) {
|
std::set<const LinkableObject*> used;
|
std::set<const LinkableObject*> used;
|
markAsUsed(_objects[0],used);
|
markAsUsed(_objects[0],used);
|
for(auto it=_objects.begin();it!=_objects.end();) {
|
for(auto it=_objects.begin();it!=_objects.end();) {
|
if(used.find(*it)==used.end()) {
|
if(used.find(*it)==used.end()) {
|
std::cerr<<"Linker warning: skipping an unreferenced object \"";
|
std::cerr<<"Linker warning: skipping an unreferenced object \"";
|
std::cerr<<(*it)->name()<<"\""<<std::endl;
|
std::cerr<<(*it)->name()<<"\""<<std::endl;
|
for(auto sym=_globalSymbolTable.begin();sym!=_globalSymbolTable.end();) {
|
for(auto sym=_globalSymbolTable.begin();sym!=_globalSymbolTable.end();) {
|
if(sym->second.obj==*it) sym=_globalSymbolTable.erase(sym);
|
if(sym->second.obj==*it) sym=_globalSymbolTable.erase(sym);
|
else ++sym;
|
else ++sym;
|
}
|
}
|
it=_objects.erase(it);
|
it=_objects.erase(it);
|
}
|
}
|
else ++it;
|
else ++it;
|
}
|
}
|
}
|
}
|
|
|
// Set base addresses
|
// Set base addresses
|
for(auto it=_objects.begin();it!=_objects.end();++it) {
|
for(auto it=_objects.begin();it!=_objects.end();++it) {
|
(*it)->setVirtualAddress(currentBase);
|
(*it)->setVirtualAddress(currentBase);
|
if(it+1!=_objects.end()) (*it)->addPadding(_align);
|
if(it+1!=_objects.end()) (*it)->addPadding(_align);
|
else (*it)->addPadding();
|
else (*it)->addPadding();
|
currentBase+=static_cast<LinkableObject::Word>((*it)->codeSize());
|
currentBase+=static_cast<LinkableObject::Word>((*it)->codeSize());
|
}
|
}
|
}
|
}
|
|
|
void Linker::relocateObject(LinkableObject *obj) {
|
void Linker::relocateObject(LinkableObject *obj) {
|
for(auto const &sym: obj->symbols()) {
|
for(auto const &sym: obj->symbols()) {
|
LinkableObject::Word addr;
|
LinkableObject::Word addr;
|
if(sym.second.refs.empty()) continue;
|
if(sym.second.refs.empty()) continue;
|
|
|
if(sym.second.type==LinkableObject::Local) addr=obj->virtualAddress()+sym.second.rva;
|
if(sym.second.type==LinkableObject::Local) addr=obj->virtualAddress()+sym.second.rva;
|
else {
|
else {
|
auto it=_globalSymbolTable.find(sym.first);
|
auto it=_globalSymbolTable.find(sym.first);
|
assert(it!=_globalSymbolTable.end());
|
assert(it!=_globalSymbolTable.end());
|
assert(it->second.obj);
|
assert(it->second.obj);
|
addr=it->second.obj->virtualAddress()+it->second.rva;
|
addr=it->second.obj->virtualAddress()+it->second.rva;
|
}
|
}
|
|
|
for(auto const &ref: sym.second.refs) {
|
for(auto const &ref: sym.second.refs) {
|
if(ref.type==LinkableObject::Regular) obj->replaceWord(ref.rva,addr+ref.offset);
|
if(ref.type==LinkableObject::Regular) obj->replaceWord(ref.rva,addr+ref.offset);
|
else {
|
else {
|
auto target=static_cast<LinkableObject::Word>(addr+ref.offset);
|
auto target=static_cast<LinkableObject::Word>(addr+ref.offset);
|
if(target>0xFFFFF&&target<0xFFF00000) {
|
if(target>0xFFFFF&&target<0xFFF00000) {
|
std::ostringstream msg;
|
std::ostringstream msg;
|
msg<<"Address 0x"<<Utils::hex(target)<<" is out of the range for a short reference";
|
msg<<"Address 0x"<<Utils::hex(target)<<" is out of the range for a short reference";
|
msg<<" (referenced from "<<ref.source<<":"<<ref.line<<")";
|
msg<<" (referenced from "<<ref.source<<":"<<ref.line<<")";
|
throw std::runtime_error(msg.str());
|
throw std::runtime_error(msg.str());
|
}
|
}
|
target&=0x1FFFFF;
|
target&=0x1FFFFF;
|
auto w=obj->getWord(ref.rva);
|
auto w=obj->getWord(ref.rva);
|
w|=(target&0xFFFF);
|
w|=(target&0xFFFF);
|
w|=((target<<8)&0x1F000000);
|
w|=((target<<8)&0x1F000000);
|
obj->replaceWord(ref.rva,w);
|
obj->replaceWord(ref.rva,w);
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
void Linker::writeObjects(OutputWriter &writer) {
|
void Linker::writeObjects(OutputWriter &writer) {
|
std::size_t currentSize=0;
|
std::size_t currentSize=0;
|
// Write entry object
|
// Write entry object
|
writer.write(reinterpret_cast<const char*>(_entryObject->code()),_entryObject->codeSize());
|
writer.write(reinterpret_cast<const char*>(_entryObject->code()),_entryObject->codeSize());
|
currentSize+=_entryObject->codeSize();
|
currentSize+=_entryObject->codeSize();
|
// Write other objects
|
// Write other objects
|
for(auto const &obj: _objects) {
|
for(auto const &obj: _objects) {
|
if(obj==_entryObject) continue;
|
if(obj==_entryObject) continue;
|
writer.write(reinterpret_cast<const char*>(obj->code()),obj->codeSize());
|
writer.write(reinterpret_cast<const char*>(obj->code()),obj->codeSize());
|
currentSize+=obj->codeSize();
|
currentSize+=obj->codeSize();
|
}
|
}
|
|
|
// Pad file if requested
|
// Pad file if requested
|
if(_imageSize>0) {
|
if(_imageSize>0) {
|
if(currentSize>_imageSize)
|
if(currentSize>_imageSize)
|
throw std::runtime_error("Image size exceeds the specified value");
|
throw std::runtime_error("Image size exceeds the specified value");
|
else if(currentSize<_imageSize) writer.pad(_imageSize-currentSize);
|
else if(currentSize<_imageSize) writer.pad(_imageSize-currentSize);
|
}
|
}
|
}
|
}
|
|
|
void Linker::markAsUsed(const LinkableObject *obj,std::set<const LinkableObject*> &used) {
|
void Linker::markAsUsed(const LinkableObject *obj,std::set<const LinkableObject*> &used) {
|
if(used.find(obj)!=used.end()) return; // already processed
|
if(used.find(obj)!=used.end()) return; // already processed
|
used.insert(obj);
|
used.insert(obj);
|
for(auto const &sym: _globalSymbolTable) {
|
for(auto const &sym: _globalSymbolTable) {
|
for(auto const &ref: sym.second.refs) {
|
for(auto const &ref: sym.second.refs) {
|
if(ref==obj) markAsUsed(sym.second.obj,used);
|
if(ref==obj) markAsUsed(sym.second.obj,used);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
