URL https://opencores.org/ocsvn/lxp32/lxp32/trunk

Subversion Repositories lxp32

[/] [lxp32/] [trunk/] [tools/] [src/] [lxp32asm/] [linker.cpp] - Blame information for rev 6

Go to most recent revision | Details | Compare with Previous | View Log


/*
 * 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);
                }
        }
}

Line No.	Rev	Author	Line
1	2	ring0_mipt	`/*`
2			`* Copyright (c) 2016 by Alex I. Kuznetsov.`
3			`*`
4			`* Part of the LXP32 CPU IP core.`
5			`*`
6			`* This module implements members of the Linker class.`
7			`*/`
8
9			`#include "linker.h"`
10
11			`#include "linkableobject.h"`
12	6	ring0_mipt	`#include "utils.h"`
13	2	ring0_mipt
14			`#include <iostream>`
15			`#include <fstream>`
16			`#include <sstream>`
17			`#include <map>`
18			`#include <stdexcept>`
19			`#include <cassert>`
20	6	ring0_mipt	`#include <algorithm>`
21	2	ring0_mipt
22			`void Linker::addObject(LinkableObject &obj) {`
23			`_objects.push_back(&obj);`
24			`}`
25
26			`void Linker::link(OutputWriter &writer) {`
27			`if(_objects.empty()) throw std::runtime_error("Object set is empty");`
28
29			`// Merge symbol tables`
30			`buildSymbolTable();`
31
32			`// Determine entry point`
33			`if(_objects.size()==1) _entryObject=_objects[0];`
34	6	ring0_mipt	`else if(_entryObject==nullptr)`
35			`throw std::runtime_error("Entry point not defined: cannot find \"entry\" or \"Entry\" symbol");`
36	2	ring0_mipt
37			`// Assign virtual addresses`
38			`placeObjects();`
39
40			`// Perform relocations`
41			`for(auto &obj: _objects) relocateObject(obj);`
42
43			`// Write binary data`
44			`writeObjects(writer);`
45	6	ring0_mipt	`_bytesWritten=writer.size();`
46	2	ring0_mipt	`}`
47
48			`void Linker::setBase(LinkableObject::Word base) {`
49			`_base=base;`
50			`}`
51
52			`void Linker::setAlignment(std::size_t align) {`
53			`_align=align;`
54			`}`
55
56			`void Linker::setImageSize(std::size_t size) {`
57			`_imageSize=size;`
58			`}`
59
60	6	ring0_mipt	`void Linker::generateMap(std::ostream &s) {`
61			`// Calculate the maximum length of a symbol name`
62			`std::size_t len=0;`
63			`for(auto const &obj: _objects) {`
64			`for(auto const &sym: obj->symbols()) {`
65			`if(sym.second.type!=LinkableObject::Imported)`
66			`len=std::max(len,sym.first.size());`
67			`}`
68			`}`
69			`len=std::max(len+3,std::size_t(8)); // width of the first column`
70
71			`s<<"Image base address: "<<Utils::hex(_base)<<std::endl;`
72			`s<<"Object alignment: "<<_align<<std::endl;`
73			`s<<"Image size: "<<(_bytesWritten/4)<<" words"<<std::endl;`
74			`s<<"Number of objects: "<<_objects.size()<<std::endl;`
75			`s<<std::endl;`
76
77			`for(auto const &obj: _objects) {`
78			`s<<"Object \""<<obj->name()<<"\" at address "<<Utils::hex(obj->virtualAddress())<<std::endl;`
79			`s<<std::endl;`
80			`std::multimap<LinkableObject::Word,std::pair<std::string,LinkableObject::SymbolData> > sorted;`
81			`for(auto const &sym: obj->symbols()) sorted.emplace(sym.second.rva,sym);`
82			`for(auto const &sym: sorted) {`
83			`if(sym.second.second.type==LinkableObject::Imported) continue;`
84			`s<<sym.second.first;`
85			`s<<std::string(len-sym.second.first.size(),' ');`
86			`s<<Utils::hex(obj->virtualAddress()+sym.second.second.rva);`
87			`if(sym.second.second.type==LinkableObject::Local) s<<" Local";`
88			`else s<<" Exported";`
89			`s<<std::endl;`
90			`}`
91			`s<<std::endl;`
92			`}`
93			`}`
94
95	2	ring0_mipt	`/*`
96			`* Private members`
97			`*/`
98
99			`void Linker::buildSymbolTable() {`
100			`_globalSymbolTable.clear();`
101
102	6	ring0_mipt	`// Build a table of exported symbols from all modules`
103	2	ring0_mipt	`for(auto const &obj: _objects) {`
104			`auto const &table=obj->symbols();`
105			`for(auto const &item: table) {`
106	6	ring0_mipt	`if((item.first=="entry"\|\|item.first=="Entry")&&item.second.type!=LinkableObject::Imported) {`
107			`if(_entryObject) {`
108			`std::ostringstream msg;`
109			`msg<<obj->name()<<": Duplicate definition of the entry symbol ";`
110			`msg<<"(previously defined in "<<_entryObject->name()<<")";`
111			`throw std::runtime_error(msg.str());`
112			`}`
113			`if(item.second.rva!=0) {`
114			`std::ostringstream msg;`
115			`msg<<obj->name()<<": ";`
116			`msg<<"Entry point must refer to the start of the object";`
117			`throw std::runtime_error(msg.str());`
118			`}`
119			`_entryObject=obj;`
120			`}`
121			`if(item.second.type==LinkableObject::Local) continue;`
122	2	ring0_mipt	`// Insert item to the global symbol table if it doesn't exist yet`
123			`auto it=_globalSymbolTable.emplace(item.first,GlobalSymbolData()).first;`
124
125	6	ring0_mipt	`// Check that the symbol has not been already defined in another object`
126			`if(item.second.type==LinkableObject::Exported) {`
127	2	ring0_mipt	`if(it->second.obj) {`
128			`std::ostringstream msg;`
129			`msg<<obj->name()<<": Duplicate definition of \""<<item.first;`
130			`msg<<"\" (previously defined in "<<it->second.obj->name()<<")";`
131			`throw std::runtime_error(msg.str());`
132			`}`
133			`it->second.obj=obj;`
134			`it->second.rva=item.second.rva;`
135			`}`
136	6	ring0_mipt
137			`if(!item.second.refs.empty()) it->second.refs.insert(obj);`
138	2	ring0_mipt	`}`
139			`}`
140
141	6	ring0_mipt	`// Check that local symbols don't shadow the public ones`
142			`for(auto const &obj: _objects) {`
143			`auto const &table=obj->symbols();`
144			`for(auto const &item: table) {`
145			`if(item.second.type!=LinkableObject::Local) continue;`
146			`auto it=_globalSymbolTable.find(item.first);`
147			`if(it==_globalSymbolTable.end()) continue;`
148			`if(!it->second.obj) continue;`
149			`if(item.first==it->first) {`
150			`std::ostringstream msg;`
151			`msg<<obj->name()<<": Local symbol \""<<item.first<<"\" shadows the public one ";`
152			`msg<<"(defined in "<<it->second.obj->name()<<")";`
153			`throw std::runtime_error(msg.str());`
154			`}`
155			`}`
156			`}`
157
158	2	ring0_mipt	`// Check that no undefined symbols remain`
159			`for(auto const &item: _globalSymbolTable) {`
160			`if(item.second.obj==nullptr&&!item.second.refs.empty()) {`
161			`std::ostringstream msg;`
162			`msg<<"Undefined symbol: \""<<item.first<<"\"";`
163			`auto const it=item.second.refs.begin();`
164	6	ring0_mipt	`msg<<" (referenced from "<<(*it)->name()<<")";`
165	2	ring0_mipt	`throw std::runtime_error(msg.str());`
166			`}`
167			`}`
168			`}`
169
170			`void Linker::placeObjects() {`
171			`auto currentBase=_base;`
172
173			`// Make entry object the first`
174			`if(_objects.size()>1) {`
175			`for(auto it=_objects.begin();it!=_objects.end();++it) {`
176			`if(*it==_entryObject) {`
177	6	ring0_mipt	`_objects.erase(it);`
178	2	ring0_mipt	`break;`
179			`}`
180			`}`
181	6	ring0_mipt	`_objects.insert(_objects.begin(),_entryObject);`
182	2	ring0_mipt	`}`
183
184	6	ring0_mipt	`// Remove unreferenced objects`
185			`if(_objects.size()>1) {`
186			`std::set<const LinkableObject*> used;`
187			`markAsUsed(_objects[0],used);`
188			`for(auto it=_objects.begin();it!=_objects.end();) {`
189			`if(used.find(*it)==used.end()) {`
190			`std::cerr<<"Linker warning: skipping an unreferenced object \"";`
191			`std::cerr<<(*it)->name()<<"\""<<std::endl;`
192			`for(auto sym=_globalSymbolTable.begin();sym!=_globalSymbolTable.end();) {`
193			`if(sym->second.obj==*it) sym=_globalSymbolTable.erase(sym);`
194			`else ++sym;`
195			`}`
196			`it=_objects.erase(it);`
197			`}`
198			`else ++it;`
199			`}`
200			`}`
201
202	2	ring0_mipt	`// Set base addresses`
203			`for(auto it=_objects.begin();it!=_objects.end();++it) {`
204			`(*it)->setVirtualAddress(currentBase);`
205			`if(it+1!=_objects.end()) (*it)->addPadding(_align);`
206			`else (*it)->addPadding();`
207			`currentBase+=static_cast<LinkableObject::Word>((*it)->codeSize());`
208			`}`
209			`}`
210
211			`void Linker::relocateObject(LinkableObject *obj) {`
212			`for(auto const &sym: obj->symbols()) {`
213	6	ring0_mipt	`LinkableObject::Word addr;`
214			`if(sym.second.refs.empty()) continue;`
215
216			`if(sym.second.type==LinkableObject::Local) addr=obj->virtualAddress()+sym.second.rva;`
217			`else {`
218			`auto it=_globalSymbolTable.find(sym.first);`
219			`assert(it!=_globalSymbolTable.end());`
220			`assert(it->second.obj);`
221			`addr=it->second.obj->virtualAddress()+it->second.rva;`
222			`}`
223
224	2	ring0_mipt	`for(auto const &ref: sym.second.refs) {`
225	6	ring0_mipt	`if(ref.type==LinkableObject::Regular) obj->replaceWord(ref.rva,addr+ref.offset);`
226			`else {`
227			`auto target=static_cast<LinkableObject::Word>(addr+ref.offset);`
228			`if(target>0xFFFFF&&target<0xFFF00000) {`
229			`std::ostringstream msg;`
230			`msg<<"Address 0x"<<Utils::hex(target)<<" is out of the range for a short reference";`
231			`msg<<" (referenced from "<<ref.source<<":"<<ref.line<<")";`
232			`throw std::runtime_error(msg.str());`
233			`}`
234			`target&=0x1FFFFF;`
235			`auto w=obj->getWord(ref.rva);`
236			`w\|=(target&0xFFFF);`
237			`w\|=((target<<8)&0x1F000000);`
238			`obj->replaceWord(ref.rva,w);`
239			`}`
240	2	ring0_mipt	`}`
241			`}`
242			`}`
243
244			`void Linker::writeObjects(OutputWriter &writer) {`
245			`std::size_t currentSize=0;`
246			`// Write entry object`
247			`writer.write(reinterpret_cast<const char*>(_entryObject->code()),_entryObject->codeSize());`
248			`currentSize+=_entryObject->codeSize();`
249			`// Write other objects`
250			`for(auto const &obj: _objects) {`
251			`if(obj==_entryObject) continue;`
252			`writer.write(reinterpret_cast<const char*>(obj->code()),obj->codeSize());`
253			`currentSize+=obj->codeSize();`
254			`}`
255
256			`// Pad file if requested`
257			`if(_imageSize>0) {`
258			`if(currentSize>_imageSize)`
259			`throw std::runtime_error("Image size exceeds the specified value");`
260			`else if(currentSize<_imageSize) writer.pad(_imageSize-currentSize);`
261			`}`
262			`}`
263	6	ring0_mipt
264			`void Linker::markAsUsed(const LinkableObject obj,std::set<const LinkableObject> &used) {`
265			`if(used.find(obj)!=used.end()) return; // already processed`
266			`used.insert(obj);`
267			`for(auto const &sym: _globalSymbolTable) {`
268			`for(auto const &ref: sym.second.refs) {`
269			`if(ref==obj) markAsUsed(sym.second.obj,used);`
270			`}`
271			`}`
272			`}`

Browse

Tools

Subversion Repositories lxp32

[/] [lxp32/] [trunk/] [tools/] [src/] [lxp32asm/] [linker.cpp] - Blame information for rev 6