typo fix
[dyninst.git] / symtabAPI / src / emitElfStatic.C
1 /*
2  * Copyright (c) 1996-2011 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 /*
33  * XXX
34  *
35  * This class is unnecessary. However, at the time of writing, emitElf was
36  * split into two different classes (one for 32-bit and 64-bit). Instead of
37  * duplicating code, this class was created to share code between the
38  * two emitElf classes.
39  *
40  * Once the emitElf classes are merged, this class can be merged with the new
41  * emitElf class.
42  */
43
44 #include <cstdlib>
45 #include <cstdio>
46 #include <iostream>
47
48 #include <algorithm>
49
50 #include "emitElfStatic.h"
51 #include "debug.h"
52
53 #if defined(os_freebsd)
54 #define R_X86_64_JUMP_SLOT R_X86_64_JMP_SLOT
55 #endif
56
57 using namespace Dyninst;
58 using namespace SymtabAPI;
59
60 // Section names
61 static const string CODE_NAME(".dyninstCode");
62 static const string DATA_NAME(".dyninstData");
63 static const string BSS_NAME(".dyninstBss");
64 static const string GOT_NAME(".dyninstGot");
65 static const string CTOR_NAME(".dyninstCtors");
66 static const string DTOR_NAME(".dyninstDtors");
67 static const string TLS_DATA_NAME(".dyninstTdata");
68 static const string DEFAULT_COM_NAME(".common");
69
70 /* Used by architecture specific functions, but not architecture specific */
71 const string Dyninst::SymtabAPI::SYMTAB_CTOR_LIST_REL("__SYMTABAPI_CTOR_LIST__");
72 const string Dyninst::SymtabAPI::SYMTAB_DTOR_LIST_REL("__SYMTABAPI_DTOR_LIST__");
73
74 emitElfStatic::emitElfStatic(unsigned addressWidth, bool isStripped) :
75     addressWidth_(addressWidth),
76     isStripped_(isStripped),
77     hasRewrittenTLS_(false)
78 {}
79
80 /**
81  * NOTE:
82  * Most of these functions take a reference to a StaticLinkError and a string
83  * for error reporting purposes. These should prove useful in identifying the
84  * cause of an error
85  */
86
87 /**
88  * Statically links relocatable files into the specified Symtab object, 
89  * as specified by state in the Symtab object
90  *
91  * target       relocatable files will be linked into this Symtab
92  *
93  * Returns a pointer to a block of data containing the results of the link
94  * The caller is responsible for delete'ing this block of data
95  */
96 char *emitElfStatic::linkStatic(Symtab *target, 
97         StaticLinkError &err, string &errMsg) 
98 {
99     /* 
100      * Basic algorithm is:
101      * - locate defined versions of symbols for undefined symbols in 
102      *   either the target or relocatable code, produces a list
103      *   of Symtab objects that contain the defined versions
104      *
105      * - Allocate space for all new code and data to be linked into 
106      *   the target, populates a LinkMap with all allocation 
107      *   information
108      *
109      * - Compute relocations and set their targets to these values
110      */
111
112     // Holds all information necessary to work with the block of data created by createLinkMap
113     LinkMap lmap;
114
115     rewrite_printf("START link map output\n");
116     
117     // Determine starting location of new Regions
118     Offset globalOffset = 0;
119     vector<Region *> newRegs;
120     if( target->getAllNewRegions(newRegs) ) {
121         // This is true, only if other regions have already been added
122         vector<Region *>::iterator newReg_it;
123         for(newReg_it = newRegs.begin(); newReg_it != newRegs.end(); ++newReg_it) {
124             Offset newRegEndAddr = (*newReg_it)->getRegionSize() + (*newReg_it)->getRegionAddr();
125             if( newRegEndAddr > globalOffset ) {
126                 globalOffset = newRegEndAddr;
127             }
128         }
129     }
130
131     if( globalOffset == 0 ) {
132         err = Link_Location_Error;
133         errMsg = "failed to find location for new code and data.";
134         return NULL;
135     }
136
137     // Holds all necessary dependencies, as determined by resolveSymbols
138     vector<Symtab *> relocatableObjects;
139     if( !resolveSymbols(target, relocatableObjects, lmap, err, errMsg) ) {
140         return NULL;
141     }
142
143     // Lays out all relocatable files into a single contiguous block of data
144     if( !createLinkMap(target, relocatableObjects, globalOffset, lmap, err, errMsg) ) {
145         return NULL;
146     }
147
148     // Copies the data from the relocatable files into the new block of data
149     if( !addNewRegions(target, globalOffset, lmap) ) {
150         err = Storage_Allocation_Failure;
151         errMsg = "Failed to create new Regions in original binary";
152         return NULL;
153     }
154
155     // Print out the link map for debugging
156     rewrite_printf("Global Offset = 0x%lx\n", globalOffset);
157     if( sym_debug_rewrite ) {
158         lmap.printAll(cerr, globalOffset);
159         lmap.printBySymtab(cerr, relocatableObjects, globalOffset);
160     }
161
162     // Now that all symbols are at their final locations, compute and apply relocations
163     if( !applyRelocations(target, relocatableObjects, globalOffset, lmap, err, errMsg) ) {
164         if( lmap.allocatedData ) delete lmap.allocatedData;
165         return NULL;
166     }
167
168     // Restore the offset of the modified symbols
169     vector< pair<Symbol *, Offset> >::iterator symOff_it;
170     for(symOff_it = lmap.origSymbols.begin();
171         symOff_it != lmap.origSymbols.end();
172         ++symOff_it)
173     {
174         symOff_it->first->setOffset(symOff_it->second);
175     }
176
177     // Restore the symbols of the modified relocations
178    vector< pair<relocationEntry *, Symbol *> >::iterator relSym_it;
179    for(relSym_it = lmap.origRels.begin();
180        relSym_it != lmap.origRels.end();
181        ++relSym_it)
182    {
183        relSym_it->first->addDynSym(relSym_it->second);
184    }
185
186     rewrite_printf("\n*** Finished static linking\n\n");
187
188     rewrite_printf("END link map output\n");
189
190     err = No_Static_Link_Error;
191     errMsg = "";
192     return lmap.allocatedData;
193 }
194
195 /**
196  * Resolves undefined symbols in the specified Symtab object, usually due
197  * to the addition of new Symbols to the Symtab object. The target Symtab
198  * object must have a collection of Archives associated with it. These
199  * Archives will be searched for the defined versions of the undefined 
200  * symbols in the specified Symtab objects.
201  *
202  * target               the Symtab containing the undefined symbols
203  * relocatableObjects   populated by this function, this collection specifies
204  *                      all the Symtabs needed to ensure that the target has
205  *                      no undefined Symbols once the link is performed
206  */
207 bool emitElfStatic::resolveSymbols(Symtab *target, 
208         vector<Symtab *> &relocatableObjects,
209         LinkMap &lmap,
210         StaticLinkError &err, string &errMsg) 
211 {
212     // Collection of Symtabs that currently need their symbols resolved
213     set<Symtab *> workSet;
214
215     // Collection of Symtabs that have already had their symbols resolved
216     // this is necessary to avoid errors related to circular dependencies
217     set<Symtab *> linkedSet;
218
219     set<string> excludeSymNames;
220     getExcludedSymbolNames(excludeSymNames);
221
222     // Establish list of libraries to search for symbols
223     vector<Archive *> libraries;
224     target->getLinkingResources(libraries);
225
226     // Add all relocatable files explicitly referenced by new symbols, these
227     // essentially fuel the symbol resolution process
228     set<Symtab *> explicitRefs;
229     target->getExplicitSymtabRefs(explicitRefs);
230
231     set<Symtab *>::iterator expObj_it;
232     for(expObj_it = explicitRefs.begin(); expObj_it != explicitRefs.end();
233             ++expObj_it) 
234     {
235         relocatableObjects.push_back(*expObj_it);
236         workSet.insert(*expObj_it);
237         linkedSet.insert(*expObj_it);
238     }
239
240     set<Symtab *>::iterator curObjFilePtr = workSet.begin();
241     while( curObjFilePtr != workSet.end() ) {
242         // Take a relocatable file off the working set
243         Symtab *curObjFile = *curObjFilePtr;
244         workSet.erase(curObjFile);
245
246         rewrite_printf("\n*** Resolving symbols for: %s\n\n",
247                 curObjFile->memberName().c_str());
248
249         // Build the map of symbols to their relocations
250         map<Symbol *, vector<relocationEntry *> > symToRels;
251         vector<Region *> allRegions;
252         curObjFile->getAllRegions(allRegions);
253
254         vector<Region *>::iterator region_it;
255         for(region_it = allRegions.begin(); region_it != allRegions.end();
256                 ++region_it)
257         {
258             vector<relocationEntry> &region_rels = (*region_it)->getRelocations();
259             vector<relocationEntry>::iterator rel_it;
260             for( rel_it = region_rels.begin(); rel_it != region_rels.end(); ++rel_it) {
261                 symToRels[rel_it->getDynSym()].push_back(&(*rel_it));
262                 lmap.origRels.push_back(make_pair(&(*rel_it), rel_it->getDynSym()));
263             }
264         }
265
266         // Iterate over all undefined symbols, attempting to resolve them
267         vector<Symbol *> undefSyms;
268         curObjFile->getAllUndefinedSymbols(undefSyms);
269
270         vector<Symbol *>::iterator undefSym_it;
271         for(undefSym_it = undefSyms.begin(); undefSym_it != undefSyms.end();
272                 ++undefSym_it) 
273         {
274             Symbol *curUndefSym = *undefSym_it;
275
276             // Skip symbols that are don't cares
277             if( excludeSymNames.count(curUndefSym->getPrettyName()) ) continue;
278
279             if( !checkSpecialCaseSymbols(curObjFile, curUndefSym) ) {
280                 err = Symbol_Resolution_Failure;
281                 errMsg = "special case check failed for symbol: " +
282                     curUndefSym->getMangledName();
283                 return false;
284             }
285
286             Symbol *extSymbol = NULL;
287
288             // First, attempt to search the target for the symbol
289             if( !isStripped_ ) {
290                  vector<Symbol *> foundSyms;
291                  if( target->findSymbol(foundSyms, curUndefSym->getMangledName(),
292                     curUndefSym->getType()) )
293                  {
294                     if( foundSyms.size() > 1 ) {
295                         err = Symbol_Resolution_Failure;
296                         errMsg = "ambiguous symbol definition: " + 
297                             curUndefSym->getMangledName();
298                         return false;
299                     }
300
301                     extSymbol = foundSyms[0];
302
303                     rewrite_printf("Found external symbol %s in target with address = 0x%lx\n",
304                             extSymbol->getPrettyName().c_str(), extSymbol->getOffset());
305                  }
306             }
307
308             if( extSymbol == NULL ) {
309                 // search loaded libraries and add any new reloctable files
310                 vector<Archive *>::iterator lib_it;
311                 Symtab *containingSymtab = NULL;
312                 for(lib_it = libraries.begin(); lib_it != libraries.end(); ++lib_it) {
313                     Symtab *tmpSymtab;
314                     if( (*lib_it)->getMemberByGlobalSymbol(tmpSymtab, 
315                                 const_cast<string&>(curUndefSym->getMangledName())) ) 
316                     {
317                         /** 
318                          * The GNU approach is to use the symbol that is defined first
319                          * in the list of libraries (in the order specified to the linker)
320                          *
321                          * I am choosing to use that same behavior here.
322                          */
323                         containingSymtab = tmpSymtab;
324                         break;
325                     }else{
326                         /* Regarding duplicate symbols in Archives:
327                          *
328                          * gcc/ld appear to ignore the case where an Archive
329                          * contains the same symbol in different members and
330                          * chooses the symbol that occurs first in the
331                          * Archive's symbol table. This could produce
332                          * unexpected results so it is better to alert the user
333                          * of this error
334                          */
335                         if( Archive::getLastError() == Duplicate_Symbol ) {
336                             err = Symbol_Resolution_Failure;
337                             errMsg = Archive::printError(Duplicate_Symbol);
338                             return false;
339                         }
340                     }
341                 }
342
343                 if( containingSymtab != NULL ) {
344                     vector<Symbol *> foundSyms;
345                     if( containingSymtab->findSymbol(foundSyms, curUndefSym->getMangledName(),
346                         curUndefSym->getType()) )
347                     {
348                         if( foundSyms.size() > 1 ) {
349                             err = Symbol_Resolution_Failure;
350                             errMsg = "ambiguous symbol definition: " + 
351                                 curUndefSym->getMangledName();
352                             return false;
353                         }
354
355                         extSymbol = foundSyms[0];
356                         if( !linkedSet.count(containingSymtab) ) {
357                             // Consistency check 
358                             if( containingSymtab->getAddressWidth() != addressWidth_ ) {
359                                 err = Symbol_Resolution_Failure;
360                                 errMsg = "symbol (" + curUndefSym->getMangledName() +
361                                     ") found in relocatable file that is not compatible"
362                                     + " with the target binary";
363                                 return false;
364                             }
365
366                             relocatableObjects.push_back(containingSymtab);
367
368                             // Resolve all symbols for this new Symtab, if it hasn't already
369                             // been done
370
371                             workSet.insert(containingSymtab);
372                             linkedSet.insert(containingSymtab);
373                         }
374
375                         rewrite_printf("Found external symbol %s in object %s(%s)\n",
376                                 extSymbol->getPrettyName().c_str(),
377                                 containingSymtab->getParentArchive()->name().c_str(),
378                                 containingSymtab->memberName().c_str());
379                     }else{
380                         err = Symbol_Resolution_Failure;
381                         errMsg = "inconsistency found between archive's symbol table and member's symbol table";
382                         return false;   
383                     }
384                 }
385             }
386
387             if( extSymbol == NULL ) {
388                 // If it is a weak symbol, it isn't an error that the symbol wasn't resolved
389                 if( curUndefSym->getLinkage() == Symbol::SL_WEAK ) {
390                     continue;
391                 }
392
393                 err = Symbol_Resolution_Failure;
394                 errMsg = "failed to locate symbol '" + curUndefSym->getMangledName()
395                     + "' for object '" + curObjFile->memberName() + "'";
396                 return false;
397             }
398
399             // Store the found symbol with the related relocations
400             map<Symbol *, vector<relocationEntry *> >::iterator relMap_it;
401             relMap_it = symToRels.find(curUndefSym);
402             if( relMap_it != symToRels.end() ) {
403                 vector<relocationEntry *>::iterator rel_it;
404                 for(rel_it = relMap_it->second.begin(); rel_it != relMap_it->second.end();
405                         ++rel_it)
406                 {
407                     (*rel_it)->addDynSym(extSymbol);
408                 }
409             }   /* else
410                  *
411                  * Some libraries define a reference to a symbol and then never
412                  * use it in order to ensure that the object that defines the
413                  * symbol is linked. Therefore, it is not an error if a symbol doesn't
414                  * have a relocation.
415                  */
416         }
417
418         curObjFilePtr = workSet.begin();
419     }
420     
421     return true;
422 }
423
424 /**
425  * Given a collection of Symtab objects, combines the code, data, bss and
426  * other miscellaneous Regions into groups and places them in a new block
427  * of data.
428  * 
429  * Allocates COMMON symbols in the collection of Symtab objects
430  * as bss
431  *
432  * Creates a new TLS initialization image, combining the target image
433  * and the image that exists in the collection of Symtab objects
434  *
435  * Creates a GOT used for indirect memory accesses that is required by some
436  * relocations
437  *
438  * Creates a new global constructor and/or destructor table if necessary,
439  * combining tables from the target and collection of Symtab objects
440  *
441  * target               New code/data/etc. will be linked into this Symtab
442  * relocatableObjects   The new code/data/etc.
443  * globalOffset         The location of the new block of data in the target
444  * lmap                 The LinkMap to be populated by this function
445  */
446 bool emitElfStatic::createLinkMap(Symtab *target,
447         vector<Symtab *> &relocatableObjects, 
448         Offset & globalOffset, 
449         LinkMap &lmap,
450         StaticLinkError &err, string &errMsg) 
451 {
452     rewrite_printf("\n*** Allocating storage for relocatable objects\n\n");
453
454     // Used to create a new COMMON block
455     multimap<Offset, Symbol *> commonAlignments;
456     Offset commonRegionAlign = 0;
457
458     // Collect all Regions that should be allocated in the new data block
459     vector<Symtab *>::iterator obj_it;
460     for(obj_it = relocatableObjects.begin(); obj_it != relocatableObjects.end(); ++obj_it) {
461         vector<Region *> regs;
462         if( !(*obj_it)->getAllRegions(regs) ) {
463             err = Storage_Allocation_Failure;
464             errMsg = "failed to locate regions in relocatable object";
465             return false;
466         }
467
468         vector<Region *>::iterator reg_it;
469         for(reg_it = regs.begin(); reg_it != regs.end(); ++reg_it) {
470             string regionName = (*reg_it)->getRegionName();
471             if( (*reg_it)->isLoadable() && (*reg_it)->getRegionSize() > 0) {
472                 if( (*reg_it)->isTLS() ) {
473                     switch((*reg_it)->getRegionType()) {
474                         case Region::RT_DATA:
475                         case Region::RT_BSS:
476                             lmap.tlsRegions.push_back(*reg_it);
477                             // Determine alignment of combined region
478                             if( (*reg_it)->getMemAlignment() > lmap.tlsRegionAlign ) {
479                                 lmap.tlsRegionAlign = (*reg_it)->getMemAlignment();
480                             }
481                             break;
482                         default:
483                             // ignore any other regions
484                             break;
485                     }
486                 }else if( isConstructorRegion(*reg_it) ) {
487                     lmap.newCtorRegions.push_back(*reg_it);
488                     if( (*reg_it)->getMemAlignment() > lmap.ctorRegionAlign ) {
489                         lmap.ctorRegionAlign = (*reg_it)->getMemAlignment();
490                     }
491                 }else if( isDestructorRegion(*reg_it) ) {
492                     lmap.newDtorRegions.push_back(*reg_it);
493                     if( (*reg_it)->getMemAlignment() > lmap.dtorRegionAlign ) {
494                         lmap.dtorRegionAlign = (*reg_it)->getMemAlignment();
495                     }
496                 }else{
497                     switch((*reg_it)->getRegionType()) {
498                         case Region::RT_TEXT:
499                             lmap.codeRegions.push_back(*reg_it);
500                             // Determine alignment of combined region
501                             if( (*reg_it)->getMemAlignment() > lmap.codeRegionAlign ) {
502                                 lmap.codeRegionAlign = (*reg_it)->getMemAlignment();
503                             }
504                             break;
505                         case Region::RT_DATA:
506                             lmap.dataRegions.push_back(*reg_it);
507                             // Determine alignment of combined region
508                             if( (*reg_it)->getMemAlignment() > lmap.dataRegionAlign ) {
509                                 lmap.dataRegionAlign = (*reg_it)->getMemAlignment();
510                             }
511                             break;
512                         case Region::RT_BSS:
513                             lmap.bssRegions.push_back(*reg_it);
514                             // Determine alignment of combined region
515                             if( (*reg_it)->getMemAlignment() > lmap.bssRegionAlign ) {
516                                 lmap.bssRegionAlign = (*reg_it)->getMemAlignment();
517                             }
518                             break;
519                         case Region::RT_TEXTDATA:
520                             lmap.codeRegions.push_back(*reg_it);
521                             // Determine alignment of combined region
522                             if( (*reg_it)->getMemAlignment() > lmap.codeRegionAlign ) {
523                                 lmap.codeRegionAlign = (*reg_it)->getMemAlignment();
524                             }
525                             break;
526                         default:
527                             // skip other regions
528                             continue;
529                     }
530                 }
531
532                 // Find symbols that need to be put in the GOT
533                 vector<relocationEntry> &region_rels = (*reg_it)->getRelocations();
534                 vector<relocationEntry>::iterator rel_it;
535                 for( rel_it = region_rels.begin(); rel_it != region_rels.end(); ++rel_it) {
536                     if( isGOTRelocation(rel_it->getRelType()) ) {
537                         // initialize mapping
538                         lmap.gotSymbols.insert(make_pair(rel_it->getDynSym(), 0));
539                     }
540                 }
541             }
542         }
543
544         vector<Symbol *> definedSyms;
545         if( (*obj_it)->getAllDefinedSymbols(definedSyms) ) {
546             vector<Symbol *>::iterator sym_it;
547             for(sym_it = definedSyms.begin(); sym_it != definedSyms.end(); ++sym_it) {
548                 // Note: the assumption is made that a Symbol cannot 
549                 // be both TLS and COMMON
550                 if( (*sym_it)->isCommonStorage() ) {
551                     // For a symbol in common storage, the offset/value is the alignment
552                     commonAlignments.insert(make_pair((*sym_it)->getOffset(), *sym_it));
553
554                     // The alignment of a COMMON Region is the maximum alignment
555                     // needed by one of its symbols
556                     if( (*sym_it)->getOffset() > commonRegionAlign ) {
557                         commonRegionAlign = (*sym_it)->getOffset();
558                     }
559                 }else if( (*sym_it)->getType() == Symbol::ST_TLS ) {
560                     lmap.tlsSymbols.push_back(*sym_it);
561                 }
562             }
563         }
564     }
565
566     // Determine how all the Regions in the relocatable objects will be 
567     // placed in the rewritten target
568     Offset currentOffset = 0;
569
570     // Allocate code regions 
571     
572     // Since this is the first new Region, the actual globalOffset should be 
573     // the passed globalOffset plus the padding for this Region
574     lmap.codeRegionOffset = currentOffset;
575     globalOffset += computePadding(globalOffset + lmap.codeRegionOffset,
576             lmap.codeRegionAlign);
577
578     currentOffset = layoutRegions(lmap.codeRegions, lmap.regionAllocs,
579             lmap.codeRegionOffset, globalOffset);
580     if( currentOffset == ~0UL ) {
581         err = Storage_Allocation_Failure;
582         errMsg = "assumption failed while creating link map";
583         return false;
584     }
585     lmap.codeSize = currentOffset - lmap.codeRegionOffset;
586
587     // Allocate data regions 
588     lmap.dataRegionOffset = currentOffset;
589     lmap.dataRegionOffset += computePadding(globalOffset + lmap.dataRegionOffset,
590             lmap.dataRegionAlign);
591     currentOffset = layoutRegions(lmap.dataRegions, lmap.regionAllocs, 
592             lmap.dataRegionOffset, globalOffset);
593     if( currentOffset == ~0UL ) {
594         err = Storage_Allocation_Failure;
595         errMsg = "assumption failed while creating link map";
596         return false;
597     }
598     lmap.dataSize = currentOffset - lmap.dataRegionOffset;
599
600     // Allocate space for a GOT Region, if necessary
601     lmap.gotSize = getGOTSize(lmap);
602     if( lmap.gotSize > 0 ) {
603         lmap.gotRegionAlign = getGOTAlign(lmap);
604         currentOffset += computePadding(globalOffset + currentOffset,
605                 lmap.gotRegionAlign);
606         lmap.gotRegionOffset = currentOffset;
607         currentOffset += lmap.gotSize;
608     }
609
610     /* 
611      * Find current TLS Regions in target, also check for multiple TLS Regions
612      * of the same type => knowing how to construct the TLS image would be
613      * undefined for multiple TLS Regions of the same type
614      *
615      * Find current constructor Regions and destructor Regions.
616      */
617     Region *dataTLS = NULL, *bssTLS = NULL;
618     lmap.tlsSize = 0;
619     
620     vector<Region *> regions;
621     if( !target->getAllRegions(regions) ) {
622         err = Storage_Allocation_Failure;
623         errMsg = "failed to retrieve regions from target";
624         return false;
625     }
626     
627     vector<Region *>::iterator reg_it;
628     for(reg_it = regions.begin(); reg_it != regions.end(); ++reg_it) {
629         if( (*reg_it)->isTLS() ) {
630             if( (*reg_it)->getRegionType() == Region::RT_DATA ) {
631                 if( dataTLS != NULL ) {
632                     err = Storage_Allocation_Failure;
633                     errMsg = "found more than one TLS data region";
634                     return false;
635                 }
636                 dataTLS = *reg_it;
637                 lmap.tlsSize += dataTLS->getRegionSize();
638                 if( dataTLS->getMemAlignment() > lmap.tlsRegionAlign ) {
639                     lmap.tlsRegionAlign = dataTLS->getMemAlignment();
640                 }
641             }else if( (*reg_it)->getRegionType() == Region::RT_BSS ) {
642                 if( bssTLS != NULL ) {
643                     err = Storage_Allocation_Failure;
644                     errMsg = "found more than one TLS bss region";
645                     return false;
646                 }
647                 bssTLS = *reg_it;
648                 lmap.tlsSize += bssTLS->getRegionSize();
649                 if( bssTLS->getMemAlignment() > lmap.tlsRegionAlign ) {
650                     lmap.tlsRegionAlign = bssTLS->getMemAlignment();
651                 }
652             }
653         }else if( isConstructorRegion(*reg_it) ) {
654             lmap.originalCtorRegion = *reg_it;
655         }else if( isDestructorRegion(*reg_it) ){
656             lmap.originalDtorRegion = *reg_it;
657         }
658     }
659 #if defined(arch_x86) || defined(arch_x86_64) || defined(arch_power)
660     // Allocate the new TLS region, if necessary
661     if( lmap.tlsRegions.size() > 0 ) {
662         lmap.tlsRegionOffset = currentOffset;
663
664         lmap.tlsRegionOffset += computePadding(lmap.tlsRegionOffset + globalOffset,
665                 lmap.tlsRegionAlign);
666         currentOffset = layoutTLSImage(globalOffset, dataTLS, bssTLS, lmap);
667
668         if( currentOffset == lmap.tlsRegionOffset ) {
669             err = Storage_Allocation_Failure;
670             errMsg = "failed to create TLS initialization image";
671             return false;
672         }
673
674         /*
675          *  The size of this Region is counted twice: once when collecting the
676          *  original TLS Regions and once when laying out the image. This is
677          *  necessary to maintain consistency with the case where there are no
678          *  new TLS regions in the relocatable objects but existing TLS symbols
679          *  are used.
680          */
681         if( dataTLS != NULL ) {
682             lmap.tlsSize -= dataTLS->getRegionSize();
683         }
684
685         lmap.tlsSize += currentOffset - lmap.tlsRegionOffset;
686
687         // Adjust offsets for all existing TLS symbols, as their offset
688         // in the TLS block could have changed
689         vector<Symbol *> definedSyms;
690         if( target->getAllDefinedSymbols(definedSyms) ) {
691             vector<Symbol *>::iterator sym_it;
692             for(sym_it = definedSyms.begin(); sym_it != definedSyms.end(); ++sym_it) {
693                 if( (*sym_it)->getType() == Symbol::ST_TLS ) {
694
695                     map<Region *, LinkMap::AllocPair>::iterator result;
696                     result = lmap.regionAllocs.find((*sym_it)->getRegion());
697
698                     if( result != lmap.regionAllocs.end() ) {
699                         Offset regionOffset = result->second.second;
700                         Offset symbolOffset = (*sym_it)->getOffset();
701                         lmap.origSymbols.push_back(make_pair(*sym_it, symbolOffset));
702
703                         symbolOffset += regionOffset - lmap.tlsRegionOffset;
704                         symbolOffset = adjustTLSOffset(symbolOffset, lmap.tlsSize);
705
706                         (*sym_it)->setOffset(symbolOffset);
707                     }
708                 }
709             }
710         }
711
712         cleanupTLSRegionOffsets(lmap.regionAllocs, dataTLS, bssTLS);
713         if( bssTLS != NULL ) lmap.tlsSize -= bssTLS->getRegionSize();
714
715         hasRewrittenTLS_ = true;
716     }else{
717         // Adjust offsets for all existing TLS symbols, as the offsets required
718         // by relocation processing are TLS variant dependent
719         vector<Symbol *> definedSyms;
720         if( target->getAllDefinedSymbols(definedSyms) ) {
721             vector<Symbol *>::iterator sym_it;
722             for(sym_it = definedSyms.begin(); sym_it != definedSyms.end(); ++sym_it) {
723                 if( (*sym_it)->getType() == Symbol::ST_TLS ) {
724                     Offset symbolOffset = (*sym_it)->getOffset();
725                     lmap.origSymbols.push_back(make_pair(*sym_it, symbolOffset));
726
727                     symbolOffset = adjustTLSOffset(symbolOffset, lmap.tlsSize);
728                     (*sym_it)->setOffset(symbolOffset);
729                 }
730             }
731         }
732
733         // The size of the original TLS image is no longer needed
734         lmap.tlsSize = 0;
735     }
736 #endif
737     // Allocate space for a new constructor region, if necessary
738     if( lmap.newCtorRegions.size() > 0 ) {
739         lmap.ctorRegionOffset = currentOffset;
740         lmap.ctorRegionOffset += computePadding(globalOffset + lmap.ctorRegionOffset,
741                 lmap.ctorRegionAlign);
742         currentOffset = layoutNewCtorRegion(lmap);
743         if( currentOffset == ~0UL ) {
744             err = Storage_Allocation_Failure;
745             errMsg = "assumption failed while creating link map";
746             return false;
747         }
748         lmap.ctorSize = currentOffset - lmap.ctorRegionOffset;
749     }
750
751     // Allocate space for a new destructor region, if necessary
752     if( lmap.newDtorRegions.size() > 0 ) {
753         lmap.dtorRegionOffset = currentOffset;
754         lmap.dtorRegionOffset += computePadding(globalOffset + lmap.dtorRegionOffset,
755                 lmap.dtorRegionAlign);
756         currentOffset = layoutNewDtorRegion(lmap);
757         if( currentOffset == ~0UL ) {
758             err = Storage_Allocation_Failure;
759             errMsg = "assumption failed while creating link map";
760             return false;
761         }
762         lmap.dtorSize = currentOffset - lmap.dtorRegionOffset;
763     }
764
765     /* Combine all COMMON symbols into a single block */
766     if( commonAlignments.size() > 0 ) {
767         // The alignment of the COMMON Region could be the alignment 
768         // for the bss Region
769         if( commonRegionAlign > lmap.bssRegionAlign ) {
770             lmap.bssRegionAlign = commonRegionAlign;
771         }
772
773         // The following approach to laying out the COMMON symbols is greedy and
774         // suboptimal (in terms of space in the target), but it's quick...
775         Offset commonOffset = currentOffset;
776
777         // Make sure the COMMON Region's alignment is satisfied
778         commonOffset += computePadding(globalOffset + commonOffset, lmap.bssRegionAlign);
779         Offset commonStartOffset = commonOffset;
780
781         multimap<Offset, Symbol *>::iterator align_it;
782         for(align_it = commonAlignments.begin(); 
783             align_it != commonAlignments.end(); ++align_it)
784         {
785             commonOffset += computePadding(commonOffset, align_it->first);
786             lmap.origSymbols.push_back(make_pair(align_it->second, align_it->first));
787
788             // Update symbol with place in new linked data
789             align_it->second->setOffset(globalOffset + commonOffset);
790             commonOffset += align_it->second->getSize();
791         }
792
793         // Update the size of COMMON storage
794         if( commonAlignments.size() > 0 ) {
795             // A COMMON region is not really complete
796             lmap.commonStorage = Region::createRegion(0, Region::RP_RW,
797                     Region::RT_BSS, commonOffset - commonStartOffset, 0, 
798                     commonOffset - commonStartOffset,
799                     DEFAULT_COM_NAME, NULL, true, false, commonRegionAlign);
800             lmap.bssRegions.push_front(lmap.commonStorage);
801         }
802     }
803
804     // Allocate bss regions
805     lmap.bssRegionOffset = currentOffset;
806     lmap.bssRegionOffset += computePadding(globalOffset + lmap.bssRegionOffset,
807             lmap.bssRegionAlign);
808     currentOffset = layoutRegions(lmap.bssRegions, lmap.regionAllocs,
809             lmap.bssRegionOffset, globalOffset);
810     if( currentOffset == ~0UL ) {
811         err = Storage_Allocation_Failure;
812         errMsg = "assumption failed while creating link map";
813         return false;
814     }
815     lmap.bssSize = currentOffset - lmap.bssRegionOffset;
816
817     // Update all relevant symbols with their offsets in the new target
818     for(obj_it = relocatableObjects.begin(); obj_it != relocatableObjects.end(); ++obj_it) {
819         vector<Symbol *> definedSyms;
820         if( (*obj_it)->getAllDefinedSymbols(definedSyms) ) {
821             vector<Symbol *>::iterator sym_it;
822             for(sym_it = definedSyms.begin(); sym_it != definedSyms.end(); ++sym_it) {
823                 if(    !(*sym_it)->isCommonStorage() 
824                     && (*sym_it)->getType() != Symbol::ST_TLS) 
825                 {
826                     map<Region *, LinkMap::AllocPair>::iterator result;
827                     result = lmap.regionAllocs.find((*sym_it)->getRegion());
828                     if( result != lmap.regionAllocs.end() ) {
829                         Offset regionOffset = result->second.second;
830                         Offset symbolOffset = (*sym_it)->getOffset();
831                         lmap.origSymbols.push_back(make_pair(*sym_it, symbolOffset));
832
833                         symbolOffset += globalOffset + regionOffset;
834
835                         (*sym_it)->setOffset(symbolOffset);
836                     }
837                 }
838             }
839         }
840     }
841
842     /* ASSUMPTION
843      * At this point, the layout of the new regions is fixed, and
844      * addresses of all symbols are known (excluding Constructor/Destructor Regions)
845      */
846
847     // Allocate storage space
848     lmap.allocatedData = new char[currentOffset];
849     lmap.allocatedSize = currentOffset;
850
851     // Copy the Regions from the relocatable objects into the new storage space
852     copyRegions(lmap);
853
854     return true;
855 }
856
857 /**
858  * Lays out the specified regions, storing the layout info in the 
859  * passed map.
860  *
861  * regions              A collection of Regions to layout
862  * regionAllocs         A map of Regions to their layout information
863  * currentOffset        The starting offset for the passed Regions in
864  *                      the new storage space
865  * globalOffset         The location of the new storage space in the
866  *                      target (used for padding calculation)
867  */
868 Offset emitElfStatic::layoutRegions(deque<Region *> &regions, 
869         map<Region *, LinkMap::AllocPair> &regionAllocs,
870         Offset currentOffset, Offset globalOffset) 
871 {
872     Offset retOffset = currentOffset;
873
874     deque<Region *>::iterator copyReg_it;
875     for(copyReg_it = regions.begin(); copyReg_it != regions.end(); ++copyReg_it) {
876         // Skip empty Regions
877         if( (*copyReg_it)->getRegionSize() == 0 ) continue;
878
879         // Make sure the Region is aligned correctly in the new aggregate Region
880         Offset padding = computePadding(globalOffset + retOffset, (*copyReg_it)->getMemAlignment());
881         retOffset += padding;
882
883         // Set up mapping for a new Region in the specified storage space
884         pair<map<Region *, LinkMap::AllocPair>::iterator, bool> result;
885         result = regionAllocs.insert(make_pair(*copyReg_it, make_pair(padding, retOffset)));
886
887         // If the map already contains this Region, this is a logic error
888         if( !result.second ) {
889             retOffset = ~0UL;
890             break;
891         }
892                        
893         retOffset += (*copyReg_it)->getRegionSize();
894     }
895
896     return retOffset;
897 }
898
899 /*
900  * Adds new combined Regions to the target at the specified globalOffset
901  *
902  * target       The Symtab object to which the new Regions will be added
903  * globalOffset The offset of the first new Region in the target
904  * lmap         Contains all the information about the LinkMap
905  */
906 bool emitElfStatic::addNewRegions(Symtab *target, Offset globalOffset, LinkMap &lmap) {
907     char *newTargetData = lmap.allocatedData;
908     
909     if( lmap.codeSize > 0 ) {
910         target->addRegion(globalOffset + lmap.codeRegionOffset,
911                 reinterpret_cast<void *>(&newTargetData[lmap.codeRegionOffset]),
912                 static_cast<unsigned int>(lmap.codeSize),
913                 CODE_NAME, Region::RT_TEXTDATA, true, lmap.codeRegionAlign);
914     }
915
916     if( lmap.dataSize > 0 ) {
917         target->addRegion(globalOffset + lmap.dataRegionOffset, 
918                 reinterpret_cast<void *>(&newTargetData[lmap.dataRegionOffset]),
919                 static_cast<unsigned int>(lmap.dataSize),
920                 DATA_NAME, Region::RT_DATA, true, lmap.dataRegionAlign);
921     }
922 #if defined(arch_x86) || defined(arch_x86_64) 
923
924     if( lmap.gotSize > 0 ) {
925         buildGOT(lmap);
926
927         target->addRegion(globalOffset + lmap.gotRegionOffset,
928                 reinterpret_cast<void *>(&newTargetData[lmap.gotRegionOffset]),
929                 static_cast<unsigned int>(lmap.gotSize),
930                 GOT_NAME, Region::RT_DATA, true, lmap.gotRegionAlign);
931     }
932 #endif
933 #if defined(arch_x86) || defined(arch_x86_64)  || defined(arch_power)
934     if( lmap.tlsSize > 0 ) {
935         target->addRegion(globalOffset + lmap.tlsRegionOffset,
936                 reinterpret_cast<void *>(&newTargetData[lmap.tlsRegionOffset]),
937                 static_cast<unsigned int>(lmap.tlsSize),
938                 TLS_DATA_NAME, Region::RT_DATA, true, lmap.tlsRegionAlign, true);
939     }
940 #endif
941     if( lmap.newCtorRegions.size() > 0 ) {
942         if( !createNewCtorRegion(lmap) ) {
943             return false;
944         }
945
946         target->addRegion(globalOffset + lmap.ctorRegionOffset,
947                 reinterpret_cast<void *>(&newTargetData[lmap.ctorRegionOffset]),
948                 static_cast<unsigned int>(lmap.ctorSize),
949                 CTOR_NAME, Region::RT_DATA, true, 
950                 lmap.ctorRegionAlign);
951     }
952
953     if( lmap.newDtorRegions.size() > 0 ) {
954         if( !createNewDtorRegion(lmap) ) {
955             return false;
956         }
957
958         target->addRegion(globalOffset + lmap.dtorRegionOffset,
959                 reinterpret_cast<void *>(&newTargetData[lmap.dtorRegionOffset]),
960                 static_cast<unsigned int>(lmap.dtorSize),
961                 DTOR_NAME, Region::RT_DATA, true,
962                 lmap.dtorRegionAlign);
963     }
964
965     if( lmap.bssSize > 0 ) {
966         target->addRegion(globalOffset + lmap.bssRegionOffset, 
967                 reinterpret_cast<void *>(&newTargetData[lmap.bssRegionOffset]),
968                 static_cast<unsigned int>(lmap.bssSize),
969                 BSS_NAME, Region::RT_BSS, true, lmap.bssRegionAlign);
970     }
971
972     return true;
973 }
974
975 /**
976  * Copys the new Regions, as indicated by the LinkMap, into the
977  * allocated storage space
978  *
979  * lmap         Contains all the information necessary to perform the copy
980  */
981 void emitElfStatic::copyRegions(LinkMap &lmap) {
982     char *targetData = lmap.allocatedData;
983
984     map<Region *, LinkMap::AllocPair>::iterator regOff_it;
985     for(regOff_it = lmap.regionAllocs.begin(); regOff_it != lmap.regionAllocs.end(); ++regOff_it) {
986         Region *depRegion = regOff_it->first;
987         Offset regionOffset = regOff_it->second.second;
988         Offset padding = regOff_it->second.first;
989
990         // Copy in the Region data
991         char *rawRegionData = reinterpret_cast<char *>(depRegion->getPtrToRawData());
992
993         if( !depRegion->isBSS() ) {
994             memcpy(&targetData[regionOffset], rawRegionData, depRegion->getRegionSize());
995         }
996
997         // Set the padded space to a meaningful value
998         memset(&targetData[regionOffset - padding], getPaddingValue(depRegion->getRegionType()), padding);
999     }
1000 }
1001
1002 /**
1003  * Computes the padding necessary to satisfy the specified alignment
1004  *
1005  * candidateOffset      A possible offset for an item
1006  * alignment            The alignment for an item
1007  */
1008 inline
1009 Offset emitElfStatic::computePadding(Offset candidateOffset, Offset alignment) {
1010     Offset padding = 0;
1011     if( alignment != 0 && (candidateOffset % alignment) != 0 ) {
1012         padding = alignment - (candidateOffset % alignment);
1013     }
1014     return padding;
1015 }
1016
1017 /**
1018  * Given a collection of newly allocated regions in the specified storage space, 
1019  * computes relocations and places the values at the location specified by the
1020  * relocation entry (stored with the Regions)
1021  *
1022  * target               The Symtab object being rewritten
1023  * relocatableObjects   A list of relocatable files being linked into target
1024  * globalOffset         The location of the new storage space in target
1025  * lmap                 Contains all the information necessary to apply relocations
1026  */
1027 bool emitElfStatic::applyRelocations(Symtab *target, vector<Symtab *> &relocatableObjects,
1028         Offset globalOffset, LinkMap &lmap,
1029         StaticLinkError &err, string &errMsg) 
1030 {
1031     // Iterate over all relocations in all relocatable files
1032     vector<Symtab *>::iterator depObj_it;
1033     for(depObj_it = relocatableObjects.begin(); depObj_it != relocatableObjects.end(); ++depObj_it) {
1034         vector<Region *> allRegions;
1035         (*depObj_it)->getAllRegions(allRegions);
1036
1037         rewrite_printf("\n*** Computing relocations for: %s\n\n",
1038                 (*depObj_it)->memberName().c_str());
1039
1040         // Relocations are stored with the Region to which they will be applied
1041         // As an ELF example, .rel.text relocations are stored with the Region .text
1042         vector<Region *>::iterator region_it;
1043         for(region_it = allRegions.begin(); region_it != allRegions.end(); ++region_it) {
1044             // Only compute relocations for the new Regions
1045             map<Region *, LinkMap::AllocPair>::iterator result;
1046             result = lmap.regionAllocs.find(*region_it);
1047             if( result != lmap.regionAllocs.end() ) {
1048                 rewrite_printf("\nComputing relocations to apply to region: %s\n\n",
1049                         (*region_it)->getRegionName().c_str());
1050                 Offset regionOffset = result->second.second;
1051
1052                 vector<relocationEntry> region_rels = (*region_it)->getRelocations();
1053
1054                 vector<relocationEntry>::iterator rel_it;
1055                 for(rel_it = region_rels.begin(); rel_it != region_rels.end(); ++rel_it) {
1056                     // Compute destination of relocation
1057                     Offset dest = regionOffset + rel_it->rel_addr();
1058                     Offset relOffset = globalOffset + dest;
1059
1060                     char *targetData = lmap.allocatedData;
1061                     if( !archSpecificRelocation(targetData, *rel_it, dest, 
1062                                 relOffset, globalOffset, lmap, errMsg) ) 
1063                     {
1064                         err = Relocation_Computation_Failure;
1065                         errMsg = "Failed to compute relocation: " + errMsg;
1066                         return false;
1067                     }
1068                 }
1069             }
1070         }
1071     }
1072
1073     rewrite_printf("\n*** Computing relocations added to target.\n\n");
1074
1075     // Compute relocations added to target 
1076     vector<Region *> allRegions;
1077     target->getAllRegions(allRegions);
1078
1079     vector<Region *>::iterator reg_it;
1080     for(reg_it = allRegions.begin(); reg_it != allRegions.end(); ++reg_it) {
1081         char *regionData = reinterpret_cast<char *>((*reg_it)->getPtrToRawData());
1082         
1083         vector<relocationEntry>::iterator rel_it;
1084         for(rel_it = (*reg_it)->getRelocations().begin();
1085             rel_it != (*reg_it)->getRelocations().end();
1086             ++rel_it)
1087         {
1088             if( !archSpecificRelocation(regionData, *rel_it,
1089                         rel_it->rel_addr() - (*reg_it)->getRegionAddr(),
1090                         rel_it->rel_addr(), globalOffset, lmap, errMsg) )
1091             {
1092                 err = Relocation_Computation_Failure;
1093                 errMsg = "Failed to compute relocation: " + errMsg;
1094                 return false;
1095             }
1096         }
1097     }
1098
1099     return true;
1100 }
1101
1102 /**
1103  * A string representation of the StaticLinkError returned by
1104  * other functions
1105  */
1106 string emitElfStatic::printStaticLinkError(StaticLinkError err) {
1107     switch(err) {
1108         CASE_RETURN_STR(No_Static_Link_Error);
1109         CASE_RETURN_STR(Symbol_Resolution_Failure);
1110         CASE_RETURN_STR(Relocation_Computation_Failure);
1111         CASE_RETURN_STR(Storage_Allocation_Failure);
1112         default:
1113             return "unknown error";
1114     }
1115 }
1116
1117 /**
1118  * Indicates if a new TLS initialization image has been created
1119  */
1120 bool emitElfStatic::hasRewrittenTLS() const {
1121     return hasRewrittenTLS_;
1122 }
1123
1124 /** The following functions are all somewhat architecture-specific */
1125
1126 /* TLS Info
1127  *
1128  * TLS handling is pseudo-architecture dependent. The implementation of the TLS
1129  * functions depend on the implementation of TLS on a specific architecture.
1130  *
1131  * The following material is documented in more detail in the 
1132  * "ELF Handling For TLS" white paper. According to this paper, their are 
1133  * two variants w.r.t. creating a TLS initialization image.
1134  *
1135  * ======================
1136  *
1137  * The first is:
1138  *
1139  *            beginning of image
1140  *            |
1141  *            V                              high address
1142  * +----+-----+----------+---------+---------+
1143  * |    | TCB | image 1  | image 2 | image 3 |
1144  * +----+---- +----------+---------+---------+
1145  *
1146  * where TCB = thread control block, and each image is the
1147  * TLS initialization image for an object (in this context an executable or 
1148  * shared library).
1149  *
1150  * ========================
1151  *
1152  * The second is:
1153  * 
1154  * beginning of image
1155  * | 
1156  * V                                        high address
1157  * +---------+----------+---------+---------+
1158  * | image 3 | image 2  | image 1 |  TCB    |
1159  * +---------+----------+---------+---------+
1160  *
1161  * An image is:
1162  *
1163  * +--------+--------+
1164  * | DATA   |  BSS   |
1165  * +--------+--------+
1166  *
1167  * New TLS data and bss is added to the original initialization image as follows:
1168  *
1169  * +----------+------------------+-------------+------------+-----+
1170  * | NEW DATA | EXPANDED NEW BSS | TARGET DATA | TARGET BSS | TCB |
1171  * +----------+------------------+-------------+------------+-----+
1172  *
1173  * It is important to note that the TARGET DATA and TARGET BSS blocks are not moved.
1174  * This ensures that the modifications to the TLS image are safe.
1175  *
1176  * ==========================
1177  * 
1178  * These are the two variants one would see when working with ELF files. So, an
1179  * architecture either uses variant 1 or 2.
1180  *
1181  */
1182
1183 /* See architecture specific functions that call these for descriptions of function interface */
1184
1185 Offset emitElfStatic::tlsLayoutVariant1(Offset, Region *, Region *, LinkMap &)
1186 {
1187     assert(!"Layout of TLS initialization image, Variant 1, currently not implemented.");
1188     return 0;
1189 }
1190
1191 Offset emitElfStatic::tlsLayoutVariant2(Offset globalOffset, Region *dataTLS, Region *bssTLS,
1192         LinkMap &lmap)
1193 {
1194     // The original init. image needs to remain in the image 1 slot because
1195     // the TLS data references are relative to that position
1196     unsigned long tlsBssSize = 0;
1197     if( dataTLS != NULL ) lmap.tlsRegions.push_back(dataTLS);
1198     if( bssTLS != NULL ) tlsBssSize = bssTLS->getRegionSize();
1199
1200     // Create the image, note new BSS regions are expanded
1201     Offset endOffset = layoutRegions(lmap.tlsRegions,
1202             lmap.regionAllocs, lmap.tlsRegionOffset, globalOffset);
1203     if( endOffset == ~0UL ) return lmap.tlsRegionOffset;
1204     Offset adjustedEnd = endOffset - lmap.tlsRegionOffset;
1205
1206     // This is necessary so the offsets of existing TLS symbols can be updated
1207     // in a uniform, architecture independent way
1208     if( bssTLS != NULL ) {
1209         if( dataTLS != NULL ) {
1210             lmap.regionAllocs.insert(make_pair(bssTLS, lmap.regionAllocs[dataTLS]));
1211         }else{
1212             lmap.regionAllocs.insert(make_pair(bssTLS, make_pair(0, endOffset)));
1213         }
1214     }
1215
1216     // Update the symbols with their offsets relative to the TCB address
1217     vector<Symbol *>::iterator sym_it;
1218     for(sym_it = lmap.tlsSymbols.begin(); sym_it != lmap.tlsSymbols.end(); ++sym_it) {
1219         map<Region *, LinkMap::AllocPair>::iterator result;
1220         result = lmap.regionAllocs.find((*sym_it)->getRegion());
1221
1222         // It is a programming error if the region for the symbol
1223         // was not passed to this function
1224         if( result == lmap.regionAllocs.end() ) {
1225             endOffset = lmap.tlsRegionOffset;
1226             break;
1227         }
1228
1229         Offset regionOffset = result->second.second;
1230         Offset symbolOffset = (*sym_it)->getOffset();
1231         lmap.origSymbols.push_back(make_pair((*sym_it), symbolOffset));
1232
1233         symbolOffset += (regionOffset - lmap.tlsRegionOffset) - (adjustedEnd + tlsBssSize);
1234         (*sym_it)->setOffset(symbolOffset);
1235     }
1236
1237     return endOffset;
1238 }
1239
1240 // Note: Variant 1 does not require any modifications, so a separate
1241 // function is not necessary
1242 Offset emitElfStatic::tlsAdjustVariant2(Offset curOffset, Offset tlsSize) {
1243     // For Variant 2, offsets relative to the TCB need to be negative
1244     Offset retOffset = curOffset;
1245     retOffset -= tlsSize;
1246     return retOffset;
1247 }
1248
1249 void emitElfStatic::tlsCleanupVariant1(map<Region *, LinkMap::AllocPair> &,
1250         Region *, Region *) 
1251 {
1252     assert(!"Cleanup of TLS Regions from allocation map currently unimplemented");
1253 }
1254
1255 void emitElfStatic::tlsCleanupVariant2(map<Region *, LinkMap::AllocPair> &regionAllocs,
1256         Region *, Region *bssTLS) 
1257 {
1258     // Existing BSS TLS region is not copied to the new target data
1259     if( bssTLS != NULL ) regionAllocs.erase(bssTLS);
1260 }
1261
1262 bool 
1263 emitElfUtils::sort_reg(const Region* a, const Region* b)
1264 {   
1265     if (a->getMemOffset() == b->getMemOffset())
1266         return a->getMemSize() < b->getMemSize();
1267     return a->getMemOffset() < b->getMemOffset();
1268 }
1269
1270 /*
1271  * Sort the sections array so that sections with a non-zero
1272  * memory offset come first (and are sorted in increasing
1273  * order of offset). Preserves the ordering of zero-offset
1274  * sections.
1275  *
1276  * If no section has a non-zero offset, the return value will
1277  * be an address in the virtual memory space big enough to
1278  * hold all the loadable sections. Otherwise it will be the
1279  * address of the first non-zero offset section.
1280  *
1281  * NB if we need to create a new segment to hold these sections,
1282  * it needs to be clear up to the next page boundary to avoid
1283  * potentially clobbering other loadable segments.
1284  */
1285 Address 
1286 emitElfUtils::orderLoadableSections(Symtab *obj, vector<Region*> & sections)
1287 {
1288     Address ret = 0;
1289     Address sz = 0;
1290     vector<Region*> nonzero;
1291     vector<Region*> copy(sections);
1292     unsigned insert = sections.size()-1;
1293
1294     for(int i=copy.size()-1;i>=0;--i) {
1295         if(!copy[i]->getMemOffset())
1296             sections[insert--] = copy[i];
1297         else
1298             nonzero.push_back(copy[i]);
1299         sz += copy[i]->getMemSize();
1300     }
1301
1302     assert(nonzero.size() == (insert+1));
1303
1304     std::sort(nonzero.begin(),nonzero.end(),sort_reg);
1305     for(unsigned i=0;i<nonzero.size();++i)
1306         sections[i] = nonzero[i];
1307
1308     if(nonzero.size() > 0)
1309         ret = nonzero[0]->getMemOffset();
1310     else {
1311         // find a `hole' of appropriate size
1312         sz = (sz + 4096 - 1) & ~(4096-1);
1313         ret = obj->getFreeOffset(sz);
1314         if(!ret) {
1315             fprintf(stderr,"Failed to finde hole of size %lx, bailing\n",sz);
1316         }
1317     }
1318     return ret;
1319 }
1320
1321 // There are also some known variables that point to the heap 
1322 bool emitElfUtils::updateHeapVariables(Symtab *obj, unsigned long newSecsEndAddress ) {
1323     unsigned pgSize = (unsigned)getpagesize();
1324     const std::string minbrk(".minbrk");
1325     const std::string curbrk(".curbrk");
1326     std::vector<Symbol *> heapSyms;
1327     obj->findSymbol(heapSyms, minbrk, Symbol::ST_NOTYPE);
1328     obj->findSymbol(heapSyms, curbrk, Symbol::ST_NOTYPE);
1329
1330     std::vector<Symbol *>::iterator heapSymsIter;
1331     for(heapSymsIter = heapSyms.begin();
1332       heapSymsIter != heapSyms.end();
1333       ++heapSymsIter)
1334     {
1335         Region *symRegion = (*heapSymsIter)->getRegion();
1336         Offset symOffset = (*heapSymsIter)->getOffset(); 
1337         if( symOffset < symRegion->getRegionAddr() ) continue;
1338
1339         Offset regOffset = symOffset - symRegion->getRegionAddr();
1340         unsigned char *regData = reinterpret_cast<unsigned char *>(symRegion->getPtrToRawData());
1341         Offset heapAddr;
1342         memcpy(&heapAddr, &regData[regOffset], sizeof(Offset));
1343
1344         heapAddr = (newSecsEndAddress & ~(pgSize-1)) + pgSize;
1345
1346         if( !symRegion->patchData(regOffset, &heapAddr, sizeof(Offset)) ) {
1347             rewrite_printf("Failed to update heap address\n");
1348             return false;
1349         }
1350     }
1351
1352     return true;
1353 }
1354
1355 inline
1356 static bool adjustValInRegion(Region *reg, Offset offInReg, Offset addressWidth, int adjust) {
1357     Offset newValue;
1358     unsigned char *oldValues;
1359
1360     oldValues = reinterpret_cast<unsigned char *>(reg->getPtrToRawData());
1361     memcpy(&newValue, &oldValues[offInReg], addressWidth);
1362     newValue += adjust;
1363     return reg->patchData(offInReg, &newValue, addressWidth);
1364 }
1365
1366 bool emitElfUtils::updateRelocation(Symtab *obj, relocationEntry &rel, int library_adjust) {
1367     // Currently, only verified on x86 and x86_64 -- this may work on other architectures
1368 #if defined(arch_x86) || defined(arch_x86_64)
1369     Region *targetRegion = obj->findEnclosingRegion(rel.rel_addr());
1370     if( NULL == targetRegion ) {
1371         rewrite_printf("Failed to find enclosing Region for relocation");
1372         return false;
1373     }
1374
1375     // Used to update a Region
1376     unsigned addressWidth = obj->getAddressWidth();
1377     if( addressWidth == 8 ) {
1378         switch(rel.getRelType()) {
1379             case R_X86_64_RELATIVE:
1380                 rel.setAddend(rel.addend() + library_adjust);
1381                 break;
1382             case R_X86_64_JUMP_SLOT:
1383                 if( !adjustValInRegion(targetRegion, 
1384                            rel.rel_addr() - targetRegion->getRegionAddr(),
1385                            addressWidth, library_adjust) )
1386                 {
1387                     rewrite_printf("Failed to update relocation\n");
1388                     return false;
1389                 }
1390                 break;
1391             default:
1392                 // Do nothing
1393                 break;
1394         }
1395     }else{
1396         switch(rel.getRelType()) {
1397             case R_386_RELATIVE:
1398                 // On x86, addends are stored in their target location
1399                 if( !adjustValInRegion(targetRegion, 
1400                            rel.rel_addr() - targetRegion->getRegionAddr(),
1401                            addressWidth, library_adjust) )
1402                 {
1403                     rewrite_printf("Failed to update relocation\n");
1404                     return false;
1405                 }
1406                 break;
1407             case R_386_JMP_SLOT:
1408                 if( !adjustValInRegion(targetRegion, 
1409                            rel.rel_addr() - targetRegion->getRegionAddr(),
1410                            addressWidth, library_adjust) )
1411                 {
1412                     rewrite_printf("Failed to update relocation\n");
1413                     return false;
1414                 }
1415                 break;
1416             default:
1417                 // Do nothing
1418                 break;
1419         }
1420     }
1421
1422     // XXX The GOT also holds a pointer to the DYNAMIC segment -- this is currently not
1423     // updated. However, this appears to be unneeded for regular shared libraries.
1424     
1425     // From the SYS V ABI x86 supplement
1426     // "The table's entry zero is reserved to hold the address of the dynamic structure,
1427     // referenced with the symbol _DYNAMIC. This allows a program, such as the
1428     // dynamic linker, to find its own dynamic structure without having yet processed
1429     // its relocation entries. This is especially important for the dynamic linker, because
1430     // it must initialize itself without relying on other programs to relocate its memory
1431     // image."
1432     
1433     // In order to implement this, would have determine the final address of a new .dynamic
1434     // section before outputting the patched GOT data -- this will require some refactoring.
1435 #else
1436     rewrite_printf("WARNING: updateRelocation is not implemented on this architecture\n");
1437 #endif
1438
1439     return true;
1440 }