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