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