Remove BPatch_process::setMutationsActive, disable test1_15, and remove associated...
[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()) {
545                         if(regionName.compare(".toc") == 0){
546                                 // For every symbol in toc
547                                 // Get data of the region and split it into symbols
548                                 char *rawRegionData = reinterpret_cast<char *>((*reg_it)->getPtrToRawData());
549                                 unsigned long numSymbols = (*reg_it)->getMemSize()/8;
550                                 for (Offset entry = 0; entry < numSymbols; entry++ ) {  
551                                 // If symbol has relocation, add that 
552                                         bool relExist = false;
553                                         vector<relocationEntry> &region_rels = (*reg_it)->getRelocations();
554                                         vector<relocationEntry>::iterator rel_it;
555                                         for( rel_it = region_rels.begin(); rel_it != region_rels.end(); ++rel_it) {
556                                                 if(entry*8 == rel_it->rel_addr()) {
557                                                         lmap.gotSymbolTable.push_back(make_pair(rel_it->getDynSym(), rel_it->addend()));  
558                                                         lmap.gotSymbols.insert(make_pair(rel_it->getDynSym(), rel_it->addend()));
559                                                         relExist = true;
560
561                                                         break;
562                                                 }
563                                         }
564                                         if(!relExist) {
565                                                 // else create a new symbol 
566                                                 // Offset and name is all we care - offset should be value of the symbol
567                                               Offset soffset = *((unsigned long *) (rawRegionData + entry*8));
568                                               Symbol *newsym = new Symbol("dyntoc_entry",
569                                                                           Symbol::ST_UNKNOWN,
570                                                                           Symbol::SL_UNKNOWN,
571                                                                           Symbol::SV_UNKNOWN,
572                                                                           soffset);
573
574                                             lmap.gotSymbolTable.push_back(make_pair(newsym, 0));  
575                                             lmap.gotSymbols.insert(make_pair(newsym, 0));
576                                                 
577                                         }
578                                 }
579
580                         }
581
582                 } 
583 #endif
584                 vector<relocationEntry> &region_rels = (*reg_it)->getRelocations();
585                 vector<relocationEntry>::iterator rel_it;
586                 for( rel_it = region_rels.begin(); rel_it != region_rels.end(); ++rel_it) {
587
588                     if(isGOTRelocation(rel_it->getRelType()) ) {
589                                 lmap.gotSymbolTable.push_back(make_pair(rel_it->getDynSym(), rel_it->addend()));
590                                                                         lmap.gotSymbols.insert(make_pair(rel_it->getDynSym(), 0));
591                         
592                     }
593                         
594                 }
595             } // isLoadable
596            
597         } //for regions
598
599         vector<Symbol *> definedSyms;
600         if( (*obj_it)->getAllDefinedSymbols(definedSyms) ) {
601             vector<Symbol *>::iterator sym_it;
602             for(sym_it = definedSyms.begin(); sym_it != definedSyms.end(); ++sym_it) {
603                 // Note: the assumption is made that a Symbol cannot 
604                 // be both TLS and COMMON
605                 if( (*sym_it)->isCommonStorage() ) {
606                     // For a symbol in common storage, the offset/value is the alignment
607                     commonAlignments.insert(make_pair((*sym_it)->getOffset(), *sym_it));
608
609                     // The alignment of a COMMON Region is the maximum alignment
610                     // needed by one of its symbols
611                     if( (*sym_it)->getOffset() > commonRegionAlign ) {
612                         commonRegionAlign = (*sym_it)->getOffset();
613                     }
614                 }else if( (*sym_it)->getType() == Symbol::ST_TLS ) {
615                     lmap.tlsSymbols.push_back(*sym_it);
616                 }
617             }
618         }
619     }
620
621     // Determine how all the Regions in the relocatable objects will be 
622     // placed in the rewritten target
623     Offset currentOffset = 0;
624
625     // Allocate code regions 
626
627     // Since this is the first new Region, the actual globalOffset should be 
628     // the passed globalOffset plus the padding for this Region
629     
630     Offset maxAlign = getGOTAlign(lmap);
631     if(maxAlign < lmap.codeRegionAlign) maxAlign = lmap.codeRegionAlign;
632
633     globalOffset += computePadding(globalOffset + currentOffset,
634             maxAlign);
635
636     // Allocate space for a GOT Region, if necessary
637     lmap.gotSize = getGOTSize(lmap);
638     if( lmap.gotSize > 0 ) {
639         lmap.gotRegionAlign = getGOTAlign(lmap);
640         lmap.gotRegionOffset = currentOffset;
641         currentOffset += lmap.gotSize;
642         layoutRegions(lmap.gotRegions, lmap.regionAllocs,
643             lmap.gotRegionOffset, globalOffset);
644     } 
645
646     lmap.codeRegionOffset = currentOffset;
647     lmap.codeRegionOffset += computePadding(globalOffset + lmap.codeRegionOffset,
648             lmap.codeRegionAlign);
649     currentOffset = layoutRegions(lmap.codeRegions, lmap.regionAllocs,
650             lmap.codeRegionOffset, globalOffset);
651     if( currentOffset == ~0UL ) {
652         err = Storage_Allocation_Failure;
653         errMsg = "assumption failed while creating link map";
654         return false;
655     }
656     lmap.codeSize = currentOffset - lmap.codeRegionOffset;
657
658     // Allocate data regions 
659     lmap.dataRegionOffset = currentOffset;
660     lmap.dataRegionOffset += computePadding(globalOffset + lmap.dataRegionOffset,
661             lmap.dataRegionAlign);
662     currentOffset = layoutRegions(lmap.dataRegions, lmap.regionAllocs, 
663             lmap.dataRegionOffset, globalOffset);
664     if( currentOffset == ~0UL ) {
665         err = Storage_Allocation_Failure;
666         errMsg = "assumption failed while creating link map";
667         return false;
668     }
669     lmap.dataSize = currentOffset - lmap.dataRegionOffset;
670
671     /* 
672      * Find current TLS Regions in target, also check for multiple TLS Regions
673      * of the same type => knowing how to construct the TLS image would be
674      * undefined for multiple TLS Regions of the same type
675      *
676      * Find current constructor Regions and destructor Regions.
677      */
678     Region *dataTLS = NULL, *bssTLS = NULL;
679     lmap.tlsSize = 0;
680     
681     vector<Region *> regions;
682     if( !target->getAllRegions(regions) ) {
683         err = Storage_Allocation_Failure;
684         errMsg = "failed to retrieve regions from target";
685         return false;
686     }
687     
688     vector<Region *>::iterator reg_it;
689     for(reg_it = regions.begin(); reg_it != regions.end(); ++reg_it) {
690         if( (*reg_it)->isTLS() ) {
691             if( (*reg_it)->getRegionType() == Region::RT_DATA ) {
692                 if( dataTLS != NULL ) {
693                     err = Storage_Allocation_Failure;
694                     errMsg = "found more than one TLS data region";
695                     return false;
696                 }
697                 dataTLS = *reg_it;
698                 lmap.tlsSize += dataTLS->getMemSize();
699                 if( dataTLS->getMemAlignment() > lmap.tlsRegionAlign ) {
700                     lmap.tlsRegionAlign = dataTLS->getMemAlignment();
701                 }
702             }else if( (*reg_it)->getRegionType() == Region::RT_BSS ) {
703                 if( bssTLS != NULL ) {
704                     err = Storage_Allocation_Failure;
705                     errMsg = "found more than one TLS bss region";
706                     return false;
707                 }
708                 bssTLS = *reg_it;
709                 lmap.tlsSize += bssTLS->getMemSize();
710                 if( bssTLS->getMemAlignment() > lmap.tlsRegionAlign ) {
711                     lmap.tlsRegionAlign = bssTLS->getMemAlignment();
712                 }
713             }
714         }else if( isConstructorRegion(*reg_it) ) {
715             lmap.originalCtorRegion = *reg_it;
716         }else if( isDestructorRegion(*reg_it) ){
717             lmap.originalDtorRegion = *reg_it;
718         }
719     }
720 #if defined(arch_x86) || defined(arch_x86_64) || defined(arch_power)
721     // Allocate the new TLS region, if necessary
722     if( lmap.tlsRegions.size() > 0 ) {
723         lmap.tlsRegionOffset = currentOffset;
724
725         lmap.tlsRegionOffset += computePadding(lmap.tlsRegionOffset + globalOffset,
726                 lmap.tlsRegionAlign);
727         currentOffset = layoutTLSImage(globalOffset, dataTLS, bssTLS, lmap);
728
729         if( currentOffset == lmap.tlsRegionOffset ) {
730             err = Storage_Allocation_Failure;
731             errMsg = "failed to create TLS initialization image";
732             return false;
733         }
734
735         /*
736          *  The size of this Region is counted twice: once when collecting the
737          *  original TLS Regions and once when laying out the image. This is
738          *  necessary to maintain consistency with the case where there are no
739          *  new TLS regions in the relocatable objects but existing TLS symbols
740          *  are used.
741          */
742         if( dataTLS != NULL ) {
743             lmap.tlsSize -= dataTLS->getMemSize();
744         }
745
746         lmap.tlsSize += currentOffset - lmap.tlsRegionOffset;
747
748         // Adjust offsets for all existing TLS symbols, as their offset
749         // in the TLS block could have changed
750         vector<Symbol *> definedSyms;
751         if( target->getAllDefinedSymbols(definedSyms) ) {
752             vector<Symbol *>::iterator sym_it;
753             for(sym_it = definedSyms.begin(); sym_it != definedSyms.end(); ++sym_it) {
754                 if( (*sym_it)->getType() == Symbol::ST_TLS ) {
755
756                     map<Region *, LinkMap::AllocPair>::iterator result;
757                     result = lmap.regionAllocs.find((*sym_it)->getRegion());
758
759                     if( result != lmap.regionAllocs.end() ) {
760                         Offset regionOffset = result->second.second;
761                         Offset symbolOffset = (*sym_it)->getOffset();
762                         lmap.origSymbols.push_back(make_pair(*sym_it, symbolOffset));
763
764                         symbolOffset += regionOffset - lmap.tlsRegionOffset;
765                         symbolOffset = adjustTLSOffset(symbolOffset, lmap.tlsSize);
766
767                         (*sym_it)->setOffset(symbolOffset);
768                     }
769                 }
770             }
771         }
772
773         cleanupTLSRegionOffsets(lmap.regionAllocs, dataTLS, bssTLS);
774         if( bssTLS != NULL ) lmap.tlsSize -= bssTLS->getMemSize();
775
776         hasRewrittenTLS_ = true;
777     }else{
778         // Adjust offsets for all existing TLS symbols, as the offsets required
779         // by relocation processing are TLS variant dependent
780         vector<Symbol *> definedSyms;
781         if( target->getAllDefinedSymbols(definedSyms) ) {
782             vector<Symbol *>::iterator sym_it;
783             for(sym_it = definedSyms.begin(); sym_it != definedSyms.end(); ++sym_it) {
784                 if( (*sym_it)->getType() == Symbol::ST_TLS ) {
785                     Offset symbolOffset = (*sym_it)->getOffset();
786                     lmap.origSymbols.push_back(make_pair(*sym_it, symbolOffset));
787
788                     symbolOffset = adjustTLSOffset(symbolOffset, lmap.tlsSize);
789                     (*sym_it)->setOffset(symbolOffset);
790                 }
791             }
792         }
793
794         // The size of the original TLS image is no longer needed
795         lmap.tlsSize = 0;
796     }
797
798 #endif
799     // Allocate space for a new constructor region, if necessary
800     if( lmap.newCtorRegions.size() > 0 ) {
801         lmap.ctorRegionOffset = currentOffset;
802         lmap.ctorRegionOffset += computePadding(globalOffset + lmap.ctorRegionOffset,
803                 lmap.ctorRegionAlign);
804         currentOffset = layoutNewCtorRegion(lmap);
805         if( currentOffset == ~0UL ) {
806             err = Storage_Allocation_Failure;
807             errMsg = "assumption failed while creating link map";
808             return false;
809         }
810         lmap.ctorSize = currentOffset - lmap.ctorRegionOffset;
811     }
812
813     // Allocate space for a new destructor region, if necessary
814     if( lmap.newDtorRegions.size() > 0 ) {
815         lmap.dtorRegionOffset = currentOffset;
816         lmap.dtorRegionOffset += computePadding(globalOffset + lmap.dtorRegionOffset,
817                 lmap.dtorRegionAlign);
818         currentOffset = layoutNewDtorRegion(lmap);
819         if( currentOffset == ~0UL ) {
820             err = Storage_Allocation_Failure;
821             errMsg = "assumption failed while creating link map";
822             return false;
823         }
824         lmap.dtorSize = currentOffset - lmap.dtorRegionOffset;
825     }
826
827     /* Combine all COMMON symbols into a single block */
828     if( commonAlignments.size() > 0 ) {
829         // The alignment of the COMMON Region could be the alignment 
830         // for the bss Region
831         if( commonRegionAlign > lmap.bssRegionAlign ) {
832             lmap.bssRegionAlign = commonRegionAlign;
833         }
834
835         // The following approach to laying out the COMMON symbols is greedy and
836         // suboptimal (in terms of space in the target), but it's quick...
837         Offset commonOffset = currentOffset;
838
839         // Make sure the COMMON Region's alignment is satisfied
840         commonOffset += computePadding(globalOffset + commonOffset, lmap.bssRegionAlign);
841         Offset commonStartOffset = commonOffset;
842
843         multimap<Offset, Symbol *>::iterator align_it;
844         for(align_it = commonAlignments.begin(); 
845             align_it != commonAlignments.end(); ++align_it)
846         {
847             commonOffset += computePadding(commonOffset, align_it->first);
848             lmap.origSymbols.push_back(make_pair(align_it->second, align_it->first));
849
850             // Update symbol with place in new linked data
851             align_it->second->setOffset(globalOffset + commonOffset);
852             commonOffset += align_it->second->getSize();
853         }
854
855         // Update the size of COMMON storage
856         if( commonAlignments.size() > 0 ) {
857             // A COMMON region is not really complete
858             lmap.commonStorage = Region::createRegion(0, Region::RP_RW,
859                     Region::RT_BSS, commonOffset - commonStartOffset, 0, 
860                     commonOffset - commonStartOffset,
861                     DEFAULT_COM_NAME, NULL, true, false, commonRegionAlign);
862             lmap.bssRegions.push_front(lmap.commonStorage);
863         }
864     }
865
866     // Allocate bss regions
867     lmap.bssRegionOffset = currentOffset;
868     lmap.bssRegionOffset += computePadding(globalOffset + lmap.bssRegionOffset,
869             lmap.bssRegionAlign);
870     currentOffset = layoutRegions(lmap.bssRegions, lmap.regionAllocs,
871             lmap.bssRegionOffset, globalOffset);
872     if( currentOffset == ~0UL ) {
873         err = Storage_Allocation_Failure;
874         errMsg = "assumption failed while creating link map";
875         return false;
876     }
877
878     lmap.bssSize = currentOffset - lmap.bssRegionOffset;
879
880     // Update all relevant symbols with their offsets in the new target
881     for(obj_it = relocatableObjects.begin(); obj_it != relocatableObjects.end(); ++obj_it) {
882         vector<Symbol *> definedSyms;
883         if( (*obj_it)->getAllDefinedSymbols(definedSyms) ) {
884             vector<Symbol *>::iterator sym_it;
885             for(sym_it = definedSyms.begin(); sym_it != definedSyms.end(); ++sym_it) {
886                 if(    !(*sym_it)->isCommonStorage() 
887                     && (*sym_it)->getType() != Symbol::ST_TLS) 
888                 {
889                     map<Region *, LinkMap::AllocPair>::iterator result;
890                     result = lmap.regionAllocs.find((*sym_it)->getRegion());
891                     if( result != lmap.regionAllocs.end() ) {
892                         Offset regionOffset = result->second.second;
893                         Offset symbolOffset = (*sym_it)->getOffset();
894                         lmap.origSymbols.push_back(make_pair(*sym_it, symbolOffset));
895
896                         symbolOffset += globalOffset + regionOffset;
897 // If region has relocations, set offset to got 
898                         vector<relocationEntry> region_rels = result->first->getRelocations();
899                         if(region_rels.size() > 0) {
900 //                      printf(" region %s has relocations %d \n", result->first->getRegionName().c_str(), region_rels.size()); 
901 /*
902                                 result = lmap.regionAllocs.find((*sym_it)->getRegion());
903                                 regionOffset = result->second.second;
904 */
905                         }
906                         
907                 
908                         (*sym_it)->setOffset(symbolOffset);
909                     }
910                 }
911             }
912         }
913     }
914
915     /* ASSUMPTION
916      * At this point, the layout of the new regions is fixed, and
917      * addresses of all symbols are known (excluding Constructor/Destructor Regions)
918      */
919
920     // Allocate storage space
921     lmap.allocatedData = new char[currentOffset];
922     lmap.allocatedSize = currentOffset;
923
924     // Copy the Regions from the relocatable objects into the new storage space
925     copyRegions(lmap);
926
927     return true;
928 }
929
930 /**
931  * Lays out the specified regions, storing the layout info in the 
932  * passed map.
933  *
934  * regions              A collection of Regions to layout
935  * regionAllocs         A map of Regions to their layout information
936  * currentOffset        The starting offset for the passed Regions in
937  *                      the new storage space
938  * globalOffset         The location of the new storage space in the
939  *                      target (used for padding calculation)
940  */
941 Offset emitElfStatic::layoutRegions(deque<Region *> &regions, 
942                                     map<Region *, LinkMap::AllocPair> &regionAllocs,
943                                     Offset currentOffset, Offset globalOffset) 
944 {
945     Offset retOffset = currentOffset;
946
947     deque<Region *>::iterator copyReg_it;
948     for(copyReg_it = regions.begin(); copyReg_it != regions.end(); ++copyReg_it) {
949         // Skip empty Regions
950         if( (*copyReg_it)->getMemSize() == 0 ) continue;
951
952         // Make sure the Region is aligned correctly in the new aggregate Region
953         Offset padding = computePadding(globalOffset + retOffset, (*copyReg_it)->getMemAlignment());
954         retOffset += padding;
955
956         // Set up mapping for a new Region in the specified storage space
957         pair<map<Region *, LinkMap::AllocPair>::iterator, bool> result;
958         result = regionAllocs.insert(make_pair(*copyReg_it, make_pair(padding, retOffset)));
959
960         // If the map already contains this Region, this is a logic error
961         if( !result.second ) {
962             retOffset = ~0UL;
963             break;
964         }
965                        
966         retOffset += (*copyReg_it)->getMemSize();
967     }
968
969     return retOffset;
970 }
971
972 /*
973  * Adds new combined Regions to the target at the specified globalOffset
974  *
975  * target       The Symtab object to which the new Regions will be added
976  * globalOffset The offset of the first new Region in the target
977  * lmap         Contains all the information about the LinkMap
978  */
979 bool emitElfStatic::addNewRegions(Symtab *target, Offset globalOffset, LinkMap &lmap) {
980     char *newTargetData = lmap.allocatedData;
981  
982 #if defined(arch_x86) || defined(arch_x86_64)  || (defined(arch_power) && defined(arch_64bit))
983     if( lmap.gotSize > 0 ) {
984         buildGOT(lmap);
985         target->addRegion(globalOffset + lmap.gotRegionOffset,
986                 reinterpret_cast<void *>(&newTargetData[lmap.gotRegionOffset]),
987                 static_cast<unsigned int>(lmap.gotSize),
988                 GOT_NAME, Region::RT_DATA, true, lmap.gotRegionAlign);
989     }   
990 #endif
991     if( lmap.codeSize > 0 ) {
992         target->addRegion(globalOffset + lmap.codeRegionOffset,
993                 reinterpret_cast<void *>(&newTargetData[lmap.codeRegionOffset]),
994                 static_cast<unsigned int>(lmap.codeSize),
995                 CODE_NAME, Region::RT_TEXTDATA, true, lmap.codeRegionAlign);
996     }
997
998     if( lmap.dataSize > 0 ) {
999         target->addRegion(globalOffset + lmap.dataRegionOffset, 
1000                 reinterpret_cast<void *>(&newTargetData[lmap.dataRegionOffset]),
1001                 static_cast<unsigned int>(lmap.dataSize),
1002                 DATA_NAME, Region::RT_DATA, true, lmap.dataRegionAlign);
1003     }
1004
1005 #if defined(arch_x86) || defined(arch_x86_64)  || defined(arch_power) 
1006     if( lmap.tlsSize > 0 ) {
1007         target->addRegion(globalOffset + lmap.tlsRegionOffset,
1008                 reinterpret_cast<void *>(&newTargetData[lmap.tlsRegionOffset]),
1009                 static_cast<unsigned int>(lmap.tlsSize),
1010                 TLS_DATA_NAME, Region::RT_DATA, true, lmap.tlsRegionAlign, true);
1011     }
1012 #endif
1013     if( lmap.newCtorRegions.size() > 0 ) {
1014         if( !createNewCtorRegion(lmap) ) {
1015             return false;
1016         }
1017
1018         target->addRegion(globalOffset + lmap.ctorRegionOffset,
1019                 reinterpret_cast<void *>(&newTargetData[lmap.ctorRegionOffset]),
1020                 static_cast<unsigned int>(lmap.ctorSize),
1021                 CTOR_NAME, Region::RT_DATA, true, 
1022                 lmap.ctorRegionAlign);
1023     }
1024
1025     if( lmap.newDtorRegions.size() > 0 ) {
1026         if( !createNewDtorRegion(lmap) ) {
1027             return false;
1028         }
1029
1030         target->addRegion(globalOffset + lmap.dtorRegionOffset,
1031                 reinterpret_cast<void *>(&newTargetData[lmap.dtorRegionOffset]),
1032                 static_cast<unsigned int>(lmap.dtorSize),
1033                 DTOR_NAME, Region::RT_DATA, true,
1034                 lmap.dtorRegionAlign);
1035     }
1036
1037     if( lmap.bssSize > 0 ) {
1038         target->addRegion(globalOffset + lmap.bssRegionOffset, 
1039                 reinterpret_cast<void *>(&newTargetData[lmap.bssRegionOffset]),
1040                 static_cast<unsigned int>(lmap.bssSize),
1041                 BSS_NAME, Region::RT_BSS, true, lmap.bssRegionAlign);
1042     }
1043
1044     return true;
1045 }
1046
1047 /**
1048  * Copys the new Regions, as indicated by the LinkMap, into the
1049  * allocated storage space
1050  *
1051  * lmap         Contains all the information necessary to perform the copy
1052  */
1053 void emitElfStatic::copyRegions(LinkMap &lmap) {
1054     char *targetData = lmap.allocatedData;
1055
1056     map<Region *, LinkMap::AllocPair>::iterator regOff_it;
1057     for(regOff_it = lmap.regionAllocs.begin(); regOff_it != lmap.regionAllocs.end(); ++regOff_it) {
1058         Region *depRegion = regOff_it->first;
1059         Offset regionOffset = regOff_it->second.second;
1060         Offset padding = regOff_it->second.first;
1061
1062         // Copy in the Region data
1063         char *rawRegionData = reinterpret_cast<char *>(depRegion->getPtrToRawData());
1064
1065         if( !depRegion->isBSS() ) {
1066             memcpy(&targetData[regionOffset], rawRegionData, depRegion->getMemSize());
1067         }
1068
1069         // Set the padded space to a meaningful value
1070         memset(&targetData[regionOffset - padding], getPaddingValue(depRegion->getRegionType()), padding);
1071     }
1072 }
1073
1074 /**
1075  * Computes the padding necessary to satisfy the specified alignment
1076  *
1077  * candidateOffset      A possible offset for an item
1078  * alignment            The alignment for an item
1079  */
1080 inline
1081 Offset emitElfStatic::computePadding(Offset candidateOffset, Offset alignment) {
1082     Offset padding = 0;
1083     if( alignment != 0 && (candidateOffset % alignment) != 0 ) {
1084         padding = alignment - (candidateOffset % alignment);
1085     }
1086     return padding;
1087 }
1088
1089 /**
1090  * Given a collection of newly allocated regions in the specified storage space, 
1091  * computes relocations and places the values at the location specified by the
1092  * relocation entry (stored with the Regions)
1093  *
1094  * target               The Symtab object being rewritten
1095  * relocatableObjects   A list of relocatable files being linked into target
1096  * globalOffset         The location of the new storage space in target
1097  * lmap                 Contains all the information necessary to apply relocations
1098  */
1099 bool emitElfStatic::applyRelocations(Symtab *target, vector<Symtab *> &relocatableObjects,
1100         Offset globalOffset, LinkMap &lmap,
1101         StaticLinkError &err, string &errMsg) 
1102 {
1103     // Iterate over all relocations in all relocatable files
1104     vector<Symtab *>::iterator depObj_it;
1105     for(depObj_it = relocatableObjects.begin(); depObj_it != relocatableObjects.end(); ++depObj_it) {
1106         vector<Region *> allRegions;
1107         (*depObj_it)->getAllRegions(allRegions);
1108
1109         // Relocations are stored with the Region to which they will be applied
1110         // As an ELF example, .rel.text relocations are stored with the Region .text
1111         vector<Region *>::iterator region_it;
1112         for(region_it = allRegions.begin(); region_it != allRegions.end(); ++region_it) {
1113             // Only compute relocations for the new Regions
1114                         if ((*region_it)->getRegionName().compare(".text") && (*region_it)->getRegionName().compare(".toc") ) {
1115                                 continue;
1116         }
1117         map<Region *, LinkMap::AllocPair>::iterator result;
1118         result = lmap.regionAllocs.find(*region_it);
1119         if( result != lmap.regionAllocs.end() ) { 
1120
1121                 Offset regionOffset = result->second.second;
1122                 vector<relocationEntry> region_rels = (*region_it)->getRelocations();
1123
1124                 vector<relocationEntry>::iterator rel_it;
1125                 for(rel_it = region_rels.begin(); rel_it != region_rels.end(); ++rel_it) {
1126                     // Compute destination of relocation
1127                     Offset dest = regionOffset + rel_it->rel_addr();
1128                     Offset relOffset = globalOffset + dest;
1129                         
1130                    rewrite_printf("\tComputing relocations to apply to region: %s @ 0x%lx reloffset %d 0x%lx dest %d 0x%lx  \n\n",
1131                         (*region_it)->getRegionName().c_str(), regionOffset, relOffset,relOffset, dest,dest);
1132                     char *targetData = lmap.allocatedData;
1133                     if( !archSpecificRelocation(target, *depObj_it, targetData, *rel_it, dest, 
1134                                 relOffset, globalOffset, lmap, errMsg) ) 
1135                     {
1136                         err = Relocation_Computation_Failure;
1137                         errMsg = "Failed to compute relocation: " + errMsg;
1138                         return false;
1139                     }
1140 /*
1141                    if((*region_it)->getRegionName().compare(".toc") == 0){
1142                         Offset regOffset = lmap.gotRegionOffset; 
1143                         dest = regOffset + rel_it->rel_addr();
1144                         relOffset = globalOffset + dest;
1145
1146                     if((*rel_it).name().compare("__SYMTABAPI_CTOR_LIST__") == 0) 
1147                         {
1148                         printf("\n\tComputing relocations to apply to region: %s @ 0x%lx reloffset %d 0x%lx dest %d 0x%lx  \n\n",
1149                         (*region_it)->getRegionName().c_str(), regOffset, relOffset,relOffset, dest,dest);
1150                     if( !archSpecificRelocation(target, *depObj_it, targetData, *rel_it, dest, 
1151                                 relOffset, globalOffset, lmap, errMsg) ) 
1152                     {
1153                         err = Relocation_Computation_Failure;
1154                         errMsg = "Failed to compute relocation: " + errMsg;
1155                         return false;
1156                     }
1157                         }
1158                 
1159                    }  
1160 */
1161                 }
1162             }
1163         }
1164     }
1165
1166     rewrite_printf("\n*** Computing relocations added to target.\n\n");
1167
1168     // Compute relocations added to target 
1169     vector<Region *> allRegions;
1170     target->getAllRegions(allRegions);
1171
1172     vector<Region *>::iterator reg_it;
1173     for(reg_it = allRegions.begin(); reg_it != allRegions.end(); ++reg_it) {
1174        cerr << "Calculating relocations for region at " << hex << (*reg_it)->getRegionAddr()
1175             << dec << endl;
1176           
1177         char *regionData = reinterpret_cast<char *>((*reg_it)->getPtrToRawData());
1178         
1179         vector<relocationEntry>::iterator rel_it;
1180         for(rel_it = (*reg_it)->getRelocations().begin();
1181             rel_it != (*reg_it)->getRelocations().end();
1182             ++rel_it)
1183         {
1184            cerr << "Generating relocation at offset "
1185                 << hex << rel_it->rel_addr() - (*reg_it)->getRegionAddr()
1186                 << "(" << rel_it->rel_addr() 
1187                 << " - " << (*reg_it)->getRegionAddr() << ")"
1188                 << dec << endl;
1189             if( !archSpecificRelocation(target, target, regionData, *rel_it,
1190                         rel_it->rel_addr() - (*reg_it)->getRegionAddr(),
1191                         rel_it->rel_addr(), globalOffset, lmap, errMsg) )
1192             {
1193                 err = Relocation_Computation_Failure;
1194                 errMsg = "Failed to compute relocation: " + errMsg;
1195                 return false;
1196             }
1197         }
1198     }
1199
1200     return true;
1201 }
1202
1203 /**
1204  * A string representation of the StaticLinkError returned by
1205  * other functions
1206  */
1207 string emitElfStatic::printStaticLinkError(StaticLinkError err) {
1208     switch(err) {
1209         CASE_RETURN_STR(No_Static_Link_Error);
1210         CASE_RETURN_STR(Symbol_Resolution_Failure);
1211         CASE_RETURN_STR(Relocation_Computation_Failure);
1212         CASE_RETURN_STR(Storage_Allocation_Failure);
1213         default:
1214             return "unknown error";
1215     }
1216 }
1217
1218 /**
1219  * Indicates if a new TLS initialization image has been created
1220  */
1221 bool emitElfStatic::hasRewrittenTLS() const {
1222     return hasRewrittenTLS_;
1223 }
1224
1225 /** The following functions are all somewhat architecture-specific */
1226
1227 /* TLS Info
1228  *
1229  * TLS handling is pseudo-architecture dependent. The implementation of the TLS
1230  * functions depend on the implementation of TLS on a specific architecture.
1231  *
1232  * The following material is documented in more detail in the 
1233  * "ELF Handling For TLS" white paper. According to this paper, their are 
1234  * two variants w.r.t. creating a TLS initialization image.
1235  *
1236  * ======================
1237  *
1238  * The first is:
1239  *
1240  *            beginning of image
1241  *            |
1242  *            V                              high address
1243  * +----+-----+----------+---------+---------+
1244  * |    | TCB | image 1  | image 2 | image 3 |
1245  * +----+---- +----------+---------+---------+
1246  *
1247  * where TCB = thread control block, and each image is the
1248  * TLS initialization image for an object (in this context an executable or 
1249  * shared library).
1250  *
1251  * ========================
1252  *
1253  * The second is:
1254  * 
1255  * beginning of image
1256  * | 
1257  * V                                        high address
1258  * +---------+----------+---------+---------+
1259  * | image 3 | image 2  | image 1 |  TCB    |
1260  * +---------+----------+---------+---------+
1261  *
1262  * An image is:
1263  *
1264  * +--------+--------+
1265  * | DATA   |  BSS   |
1266  * +--------+--------+
1267  *
1268  * New TLS data and bss is added to the original initialization image as follows:
1269  *
1270  * +----------+------------------+-------------+------------+-----+
1271  * | NEW DATA | EXPANDED NEW BSS | TARGET DATA | TARGET BSS | TCB |
1272  * +----------+------------------+-------------+------------+-----+
1273  *
1274  * It is important to note that the TARGET DATA and TARGET BSS blocks are not moved.
1275  * This ensures that the modifications to the TLS image are safe.
1276  *
1277  * ==========================
1278  * 
1279  * These are the two variants one would see when working with ELF files. So, an
1280  * architecture either uses variant 1 or 2.
1281  *
1282  */
1283
1284 /* See architecture specific functions that call these for descriptions of function interface */
1285
1286 Offset emitElfStatic::tlsLayoutVariant1(Offset globalOffset, Region *dataTLS, Region *bssTLS, LinkMap &lmap)
1287 {
1288     // The original init. image needs to remain in the image 1 slot because
1289     // the TLS data references are relative to that position
1290     unsigned long tlsBssSize = 0;
1291     if( dataTLS != NULL ) lmap.tlsRegions.push_back(dataTLS);
1292     if( bssTLS != NULL ) tlsBssSize = bssTLS->getMemSize();
1293     deque<Region *> tlsRegionsVar;
1294
1295     deque<Region *>::iterator copyReg_it;
1296     for(copyReg_it = lmap.tlsRegions.begin(); copyReg_it != lmap.tlsRegions.end(); ++copyReg_it) {
1297          tlsRegionsVar.push_front(*copyReg_it);
1298     }
1299
1300     // Create the image, note new BSS regions are expanded
1301     Offset endOffset = layoutRegions(lmap.tlsRegions,
1302             lmap.regionAllocs, lmap.tlsRegionOffset, globalOffset);
1303     if( endOffset == ~0UL ) return lmap.tlsRegionOffset;
1304     Offset adjustedEnd = endOffset - lmap.tlsRegionOffset;
1305
1306     // This is necessary so the offsets of existing TLS symbols can be updated
1307     // in a uniform, architecture independent way
1308     if( bssTLS != NULL ) {
1309         if( dataTLS != NULL ) {
1310             lmap.regionAllocs.insert(make_pair(bssTLS, lmap.regionAllocs[dataTLS]));
1311         }else{
1312             lmap.regionAllocs.insert(make_pair(bssTLS, make_pair(0, endOffset)));
1313         }
1314     }
1315
1316     // Update the symbols with their offsets relative to the TCB address
1317     vector<Symbol *>::iterator sym_it;
1318     for(sym_it = lmap.tlsSymbols.begin(); sym_it != lmap.tlsSymbols.end(); ++sym_it) {
1319         map<Region *, LinkMap::AllocPair>::iterator result;
1320         result = lmap.regionAllocs.find((*sym_it)->getRegion());
1321
1322         // It is a programming error if the region for the symbol
1323         // was not passed to this function
1324         if( result == lmap.regionAllocs.end() ) {
1325             endOffset = lmap.tlsRegionOffset;
1326             break;
1327         }
1328
1329         Offset regionOffset = result->second.second;
1330         Offset symbolOffset = (*sym_it)->getOffset();
1331         lmap.origSymbols.push_back(make_pair((*sym_it), symbolOffset));
1332
1333         symbolOffset += (regionOffset - lmap.tlsRegionOffset) - (adjustedEnd + tlsBssSize);
1334         (*sym_it)->setOffset(symbolOffset);
1335     }
1336
1337     return endOffset;
1338 }
1339
1340 Offset emitElfStatic::tlsLayoutVariant2(Offset globalOffset, Region *dataTLS, Region *bssTLS,
1341         LinkMap &lmap)
1342 {
1343     // The original init. image needs to remain in the image 1 slot because
1344     // the TLS data references are relative to that position
1345     unsigned long tlsBssSize = 0;
1346     if( dataTLS != NULL ) lmap.tlsRegions.push_back(dataTLS);
1347     if( bssTLS != NULL ) tlsBssSize = bssTLS->getMemSize();
1348
1349     // Create the image, note new BSS regions are expanded
1350     Offset endOffset = layoutRegions(lmap.tlsRegions,
1351             lmap.regionAllocs, lmap.tlsRegionOffset, globalOffset);
1352     if( endOffset == ~0UL ) return lmap.tlsRegionOffset;
1353     Offset adjustedEnd = endOffset - lmap.tlsRegionOffset;
1354
1355     // This is necessary so the offsets of existing TLS symbols can be updated
1356     // in a uniform, architecture independent way
1357     if( bssTLS != NULL ) {
1358         if( dataTLS != NULL ) {
1359             lmap.regionAllocs.insert(make_pair(bssTLS, lmap.regionAllocs[dataTLS]));
1360         }else{
1361             lmap.regionAllocs.insert(make_pair(bssTLS, make_pair(0, endOffset)));
1362         }
1363     }
1364
1365     // Update the symbols with their offsets relative to the TCB address
1366     vector<Symbol *>::iterator sym_it;
1367     for(sym_it = lmap.tlsSymbols.begin(); sym_it != lmap.tlsSymbols.end(); ++sym_it) {
1368         map<Region *, LinkMap::AllocPair>::iterator result;
1369         result = lmap.regionAllocs.find((*sym_it)->getRegion());
1370
1371         // It is a programming error if the region for the symbol
1372         // was not passed to this function
1373         if( result == lmap.regionAllocs.end() ) {
1374             endOffset = lmap.tlsRegionOffset;
1375             break;
1376         }
1377
1378         Offset regionOffset = result->second.second;
1379         Offset symbolOffset = (*sym_it)->getOffset();
1380         lmap.origSymbols.push_back(make_pair((*sym_it), symbolOffset));
1381
1382         symbolOffset += (regionOffset - lmap.tlsRegionOffset) - (adjustedEnd + tlsBssSize);
1383         (*sym_it)->setOffset(symbolOffset);
1384     }
1385
1386     return endOffset;
1387 }
1388
1389 // Note: Variant 1 does not require any modifications, so a separate
1390 // function is not necessary
1391 Offset emitElfStatic::tlsAdjustVariant2(Offset curOffset, Offset tlsSize) {
1392     // For Variant 2, offsets relative to the TCB need to be negative
1393     Offset retOffset = curOffset;
1394     retOffset -= tlsSize;
1395     return retOffset;
1396 }
1397
1398 void emitElfStatic::tlsCleanupVariant1(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 void emitElfStatic::tlsCleanupVariant2(map<Region *, LinkMap::AllocPair> &regionAllocs,
1406         Region *, Region *bssTLS) 
1407 {
1408     // Existing BSS TLS region is not copied to the new target data
1409     if( bssTLS != NULL ) regionAllocs.erase(bssTLS);
1410 }
1411
1412 bool 
1413 emitElfUtils::sort_reg(const Region* a, const Region* b)
1414 {   
1415     if (a->getMemOffset() == b->getMemOffset())
1416         return a->getMemSize() < b->getMemSize();
1417     return a->getMemOffset() < b->getMemOffset();
1418 }
1419
1420 /*
1421  * Sort the sections array so that sections with a non-zero
1422  * memory offset come first (and are sorted in increasing
1423  * order of offset). Preserves the ordering of zero-offset
1424  * sections.
1425  *
1426  * If no section has a non-zero offset, the return value will
1427  * be an address in the virtual memory space big enough to
1428  * hold all the loadable sections. Otherwise it will be the
1429  * address of the first non-zero offset section.
1430  *
1431  * NB if we need to create a new segment to hold these sections,
1432  * it needs to be clear up to the next page boundary to avoid
1433  * potentially clobbering other loadable segments.
1434  */
1435 Address 
1436 emitElfUtils::orderLoadableSections(Symtab *obj, vector<Region*> & sections)
1437 {
1438     Address ret = 0;
1439     Address sz = 0;
1440     vector<Region*> nonzero;
1441     vector<Region*> copy(sections);
1442     unsigned insert = sections.size()-1;
1443
1444     for(int i=copy.size()-1;i>=0;--i) {
1445         if(!copy[i]->getMemOffset())
1446             sections[insert--] = copy[i];
1447         else
1448             nonzero.push_back(copy[i]);
1449         sz += copy[i]->getMemSize();
1450     }
1451
1452     assert(nonzero.size() == (insert+1));
1453
1454     std::sort(nonzero.begin(),nonzero.end(),sort_reg);
1455     for(unsigned i=0;i<nonzero.size();++i)
1456         sections[i] = nonzero[i];
1457
1458     if(nonzero.size() > 0)
1459         ret = nonzero[0]->getMemOffset();
1460     else {
1461         // find a `hole' of appropriate size
1462         sz = (sz + 4096 - 1) & ~(4096-1);
1463         ret = obj->getFreeOffset(sz);
1464         if(!ret) {
1465             fprintf(stderr,"Failed to finde hole of size %lx, bailing\n",sz);
1466         }
1467     }
1468     return ret;
1469 }
1470
1471 // There are also some known variables that point to the heap 
1472 bool emitElfUtils::updateHeapVariables(Symtab *obj, unsigned long newSecsEndAddress ) {
1473     unsigned pgSize = (unsigned)getpagesize();
1474     const std::string minbrk(".minbrk");
1475     const std::string curbrk(".curbrk");
1476     std::vector<Symbol *> heapSyms;
1477     obj->findSymbol(heapSyms, minbrk, Symbol::ST_NOTYPE);
1478     obj->findSymbol(heapSyms, curbrk, Symbol::ST_NOTYPE);
1479
1480     std::vector<Symbol *>::iterator heapSymsIter;
1481     for(heapSymsIter = heapSyms.begin();
1482       heapSymsIter != heapSyms.end();
1483       ++heapSymsIter)
1484     {
1485         Region *symRegion = (*heapSymsIter)->getRegion();
1486         Offset symOffset = (*heapSymsIter)->getOffset(); 
1487         if( symOffset < symRegion->getRegionAddr() ) continue;
1488
1489         Offset regOffset = symOffset - symRegion->getRegionAddr();
1490         unsigned char *regData = reinterpret_cast<unsigned char *>(symRegion->getPtrToRawData());
1491         Offset heapAddr;
1492         memcpy(&heapAddr, &regData[regOffset], sizeof(Offset));
1493
1494         heapAddr = (newSecsEndAddress & ~(pgSize-1)) + pgSize;
1495
1496         if( !symRegion->patchData(regOffset, &heapAddr, sizeof(Offset)) ) {
1497             rewrite_printf("Failed to update heap address\n");
1498             return false;
1499         }
1500     }
1501
1502     return true;
1503 }
1504
1505 inline
1506 static bool adjustValInRegion(Region *reg, Offset offInReg, Offset addressWidth, int adjust) {
1507     Offset newValue;
1508     unsigned char *oldValues;
1509
1510     oldValues = reinterpret_cast<unsigned char *>(reg->getPtrToRawData());
1511     memcpy(&newValue, &oldValues[offInReg], addressWidth);
1512     newValue += adjust;
1513     return reg->patchData(offInReg, &newValue, addressWidth);
1514 }
1515
1516 bool emitElfUtils::updateRelocation(Symtab *obj, relocationEntry &rel, int library_adjust) {
1517     // Currently, only verified on x86 and x86_64 -- this may work on other architectures
1518 #if defined(arch_x86) || defined(arch_x86_64)
1519     Region *targetRegion = obj->findEnclosingRegion(rel.rel_addr());
1520     if( NULL == targetRegion ) {
1521         rewrite_printf("Failed to find enclosing Region for relocation");
1522         return false;
1523     }
1524
1525     // Used to update a Region
1526     unsigned addressWidth = obj->getAddressWidth();
1527     if( addressWidth == 8 ) {
1528         switch(rel.getRelType()) {
1529             case R_X86_64_RELATIVE:
1530                 rel.setAddend(rel.addend() + library_adjust);
1531                 break;
1532             case R_X86_64_JUMP_SLOT:
1533                 if( !adjustValInRegion(targetRegion, 
1534                            rel.rel_addr() - targetRegion->getRegionAddr(),
1535                            addressWidth, library_adjust) )
1536                 {
1537                     rewrite_printf("Failed to update relocation\n");
1538                     return false;
1539                 }
1540                 break;
1541             default:
1542                 // Do nothing
1543                 break;
1544         }
1545     }else{
1546         switch(rel.getRelType()) {
1547             case R_386_RELATIVE:
1548                 // On x86, addends are stored in their target location
1549                 if( !adjustValInRegion(targetRegion, 
1550                            rel.rel_addr() - targetRegion->getRegionAddr(),
1551                            addressWidth, library_adjust) )
1552                 {
1553                     rewrite_printf("Failed to update relocation\n");
1554                     return false;
1555                 }
1556                 break;
1557             case R_386_JMP_SLOT:
1558                 if( !adjustValInRegion(targetRegion, 
1559                            rel.rel_addr() - targetRegion->getRegionAddr(),
1560                            addressWidth, library_adjust) )
1561                 {
1562                     rewrite_printf("Failed to update relocation\n");
1563                     return false;
1564                 }
1565                 break;
1566             default:
1567                 // Do nothing
1568                 break;
1569         }
1570     }
1571
1572     // XXX The GOT also holds a pointer to the DYNAMIC segment -- this is currently not
1573     // updated. However, this appears to be unneeded for regular shared libraries.
1574     
1575     // From the SYS V ABI x86 supplement
1576     // "The table's entry zero is reserved to hold the address of the dynamic structure,
1577     // referenced with the symbol _DYNAMIC. This allows a program, such as the
1578     // dynamic linker, to find its own dynamic structure without having yet processed
1579     // its relocation entries. This is especially important for the dynamic linker, because
1580     // it must initialize itself without relying on other programs to relocate its memory
1581     // image."
1582     
1583     // In order to implement this, would have determine the final address of a new .dynamic
1584     // section before outputting the patched GOT data -- this will require some refactoring.
1585 #else
1586     rewrite_printf("WARNING: updateRelocation is not implemented on this architecture\n");
1587 #endif
1588
1589     return true;
1590 }