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