//===- Layout.cpp ---------------------------------------------------------===//
//
// The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#include <mcld/LD/Layout.h>
#include <cassert>
#include <llvm/ADT/Twine.h>
#include <mcld/ADT/SizeTraits.h>
#include <mcld/LD/LDContext.h>
#include <mcld/LD/LDFileFormat.h>
#include <mcld/LD/LDSection.h>
#include <mcld/LD/Fragment.h>
#include <mcld/LD/FillFragment.h>
#include <mcld/LD/AlignFragment.h>
#include <mcld/MC/MCLinker.h>
#include <mcld/MC/MCLDInfo.h>
#include <mcld/Support/MsgHandling.h>
#include <mcld/Target/TargetLDBackend.h>
using namespace mcld;
//===----------------------------------------------------------------------===//
// Range
//===----------------------------------------------------------------------===//
Layout::Range::Range()
: header(NULL),
prevRear(NULL) {
}
Layout::Range::Range(const LDSection& pHdr)
: header(const_cast<LDSection*>(&pHdr)),
prevRear(NULL) {
}
Layout::Range::~Range()
{
}
//===----------------------------------------------------------------------===//
// Layout
//===----------------------------------------------------------------------===//
Layout::Layout()
: m_FragRefFactory(32) /** magic number **/ {
}
Layout::~Layout()
{
}
void Layout::setFragmentLayoutOrder(Fragment* pFrag)
{
if (NULL == pFrag)
return;
/// find the most-recent fragment whose order was set.
Fragment* first = pFrag;
while (!hasLayoutOrder(*first)) {
if (NULL == first->getPrevNode())
break;
first = first->getPrevNode();
}
/// set all layout order
// find the first fragment who has no order.
// find the last order of the fragment
unsigned int layout_order = 0;
Fragment* frag_not_set = NULL;
if (NULL == first->getPrevNode()) {
layout_order = 0;
frag_not_set = first;
}
else {
layout_order = first->getLayoutOrder();
frag_not_set = first->getNextNode();
}
// for all fragments that has no order, set up its order
while(NULL != frag_not_set) {
frag_not_set->setLayoutOrder(layout_order);
++layout_order;
frag_not_set = frag_not_set->getNextNode();
}
}
/// setFragmentLayoutOffset - set the fragment's layout offset. This function
/// also set up the layout offsets of all the fragments in the same range.
/// If the offset of the fragment was set before, return immediately.
void Layout::setFragmentLayoutOffset(Fragment* pFrag)
{
if (NULL == pFrag)
return;
// find the most-recent fragment whose offset was set.
Fragment* first = pFrag;
while (!hasLayoutOffset(*first)) {
if (NULL == first->getPrevNode())
break;
first = first->getPrevNode();
}
// set all layout order
uint64_t offset = 0;
Fragment* frag_not_set = NULL;
if (NULL == first->getPrevNode()) {
offset = 0;
frag_not_set = first;
}
else {
offset = first->getOffset();
offset += computeFragmentSize(*this, *first);
frag_not_set = first->getNextNode();
}
while(NULL != frag_not_set) {
frag_not_set->setOffset(offset);
offset += computeFragmentSize(*this, *frag_not_set);
frag_not_set = frag_not_set->getNextNode();
}
}
/// addInputRange
/// 1. add a new range <pInputHdr, previous rear fragment>
/// 2. compute the layout order of all previous ranges.
/// 2. compute the layout offset of all previous ranges.
void Layout::addInputRange(const SectionData& pSD,
const LDSection& pInputHdr)
{
RangeList* range_list = NULL;
// get or create the range_list
if (pSD.getFragmentList().empty() || 0 == m_SDRangeMap.count(&pSD)) {
range_list = new RangeList();
m_SDRangeMap[&pSD] = range_list;
}
else {
range_list = m_SDRangeMap[&pSD];
}
// make a range and push it into the range list
Range* range = new Range(pInputHdr);
range_list->push_back(range);
// set up previous rear of the range.
// FIXME: in current design, we can not add a range before finishing adding
// fragments in the previous range. If the limitation keeps, we can set
// prevRear to the last fragment in the SectionData simply.
//
// if the pSD's fragment list is empty, the range.prevRear keeps NULL.
if (!pSD.getFragmentList().empty()) {
range->prevRear =
const_cast<Fragment*>(&pSD.getFragmentList().back());
}
// compute the layout order of the previous range.
if (!isFirstRange(*range)) {
setFragmentLayoutOrder(range->prevRear);
setFragmentLayoutOffset(range->prevRear);
}
}
/// appendFragment - append the given Fragment to the given SectionData,
/// and insert a MCAlignFragment to preserve the required align constraint if
/// needed
uint64_t Layout::appendFragment(Fragment& pFrag,
SectionData& pSD,
uint32_t pAlignConstraint)
{
// insert MCAlignFragment into SectionData first if needed
AlignFragment* align_frag = NULL;
if (pAlignConstraint > 1) {
align_frag = new AlignFragment(pAlignConstraint, // alignment
0x0, // the filled value
1u, // the size of filled value
pAlignConstraint - 1, // max bytes to emit
&pSD);
}
// append the fragment to the SectionData
pFrag.setParent(&pSD);
pSD.getFragmentList().push_back(&pFrag);
// update the alignment of associated output LDSection if needed
LDSection* output_sect = getOutputLDSection(pFrag);
assert(NULL != output_sect);
if (pAlignConstraint > output_sect->align())
output_sect->setAlign(pAlignConstraint);
// compute the fragment order and offset
setFragmentLayoutOrder(&pFrag);
setFragmentLayoutOffset(&pFrag);
if (NULL != align_frag)
return pFrag.getOffset() - align_frag->getOffset() + computeFragmentSize(*this, pFrag);
else
return computeFragmentSize(*this, pFrag);
}
/// getInputLDSection - give a Fragment, return the corresponding input
/// LDSection*
LDSection*
Layout::getInputLDSection(const Fragment& pFrag)
{
const SectionData* sect_data = pFrag.getParent();
// check the SectionData
if (NULL == sect_data) {
llvm::report_fatal_error(llvm::Twine("the fragment does not belong to") +
llvm::Twine(" any SectionData.\n"));
}
// check the SectionData's range list
if (0 == m_SDRangeMap.count(sect_data)) {
llvm::report_fatal_error(llvm::Twine("INTERNAL BACKEND ERROR: ") +
llvm::Twine("the input's SectionData is not ") +
llvm::Twine("registered in the Layout.\nPlease ") +
llvm::Twine("use MCLinker::getOrCreateSectData() ") +
llvm::Twine("to get input's SectionData.\n"));
}
RangeList* range_list = m_SDRangeMap[sect_data];
// the fragment who has the layout order is not in the last range.
if (hasLayoutOrder(pFrag)) {
Range range = range_list->back();
if (isFirstRange(range)) {
return range.header;
}
while(range.prevRear->getLayoutOrder() > pFrag.getLayoutOrder()) {
if (NULL != range.getPrevNode())
range = *range.getPrevNode();
else
return NULL;
}
return range.header;
}
// the fragment who has no layout order should be in the last range
else {
if (range_list->empty())
return NULL;
return range_list->back().header;
}
}
/// getInputLDSection - give a Fragment, return the corresponding input
/// LDSection*
const LDSection*
Layout::getInputLDSection(const Fragment& pFrag) const
{
const SectionData* sect_data = pFrag.getParent();
// check the SectionData
if (NULL == sect_data) {
llvm::report_fatal_error(llvm::Twine("the fragment does not belong to") +
llvm::Twine(" any SectionData.\n"));
}
// check the SectionData's range list
if (0 == m_SDRangeMap.count(sect_data)) {
llvm::report_fatal_error(llvm::Twine("INTERNAL BACKEND ERROR: ") +
llvm::Twine("the input's SectionData is not ") +
llvm::Twine("registered in the Layout.\nPlease ") +
llvm::Twine("use MCLinker::getOrCreateSectData() ") +
llvm::Twine("to get input's SectionData.\n"));
}
SDRangeMap::const_iterator range_list_iter = m_SDRangeMap.find(sect_data);
const RangeList* range_list = range_list_iter->second;
// the fragment who has the layout order is not in the last range.
if (hasLayoutOrder(pFrag)) {
Range range = range_list->back();
if (isFirstRange(range)) {
return range.header;
}
while(range.prevRear->getLayoutOrder() > pFrag.getLayoutOrder()) {
if (NULL != range.getPrevNode())
range = *range.getPrevNode();
else
return NULL;
}
return range.header;
}
// the fragment who has no layout order should be in the last range
else {
if (range_list->empty())
return NULL;
return range_list->back().header;
}
}
/// getOutputLDSection
LDSection* Layout::getOutputLDSection(const Fragment& pFrag)
{
SectionData* sect_data = pFrag.getParent();
if (NULL == sect_data)
return NULL;
return const_cast<LDSection*>(§_data->getSection());
}
/// getOutputLDSection
const LDSection* Layout::getOutputLDSection(const Fragment& pFrag) const
{
const SectionData* sect_data = pFrag.getParent();
if (NULL == sect_data)
return NULL;
return §_data->getSection();
}
/// getFragmentRef - assume the ragne exist, find the fragment reference
FragmentRef* Layout::getFragmentRef(Layout::Range& pRange, uint64_t pOffset)
{
if (isEmptyRange(pRange))
return NULL;
Fragment* front = getFront(pRange);
if (NULL == front)
return NULL;
Fragment* rear = getRear(pRange);
if (NULL == rear)
return NULL;
return getFragmentRef(*front, *rear, pOffset);
}
// @param pFront is the first fragment in the range.
// @param pRear is the last fragment in the range.
// @pOffset is the offset started from pFront.
FragmentRef*
Layout::getFragmentRef(Fragment& pFront, Fragment& pRear, uint64_t pOffset)
{
Fragment* front = &pFront;
Fragment* rear = &pRear;
if (!hasLayoutOffset(*rear)) {
// compute layout order, offset
setFragmentLayoutOrder(rear);
setFragmentLayoutOffset(rear);
}
// compute the offset from overall start fragment.
uint64_t target_offset = pFront.getOffset() + pOffset;
// from front to rear, find the offset which is as large as possible
// but smaller than the target_offset.
while (front != rear) {
if (Fragment::Alignment == front->getKind()) {
// alignment fragments were not counted in target_offset.
// Count in the size of alignment fragmen in target_offset here.
uint64_t align_size = 0x0;
if (NULL == front->getNextNode()) {
// If the alignment fragment is the last fragment, increase
// the target_offset by the alignment fragment's size.
align_size = computeFragmentSize(*this, *front);
}
else {
// If the alignment fragment is not the last fragment, the alignment
// fragment's size is the distance between the two fragment.
align_size = front->getNextNode()->getOffset() - front->getOffset();
}
target_offset += align_size;
front = front->getNextNode();
continue;
}
if (target_offset >= front->getNextNode()->getOffset()) {
front = front->getNextNode();
}
else {
// found
FragmentRef* result = m_FragRefFactory.allocate();
new (result) FragmentRef(*front, target_offset - front->getOffset());
return result;
}
}
if (front == rear) {
if (Fragment::Alignment == front->getKind())
return NULL;
if (!isValidOffset(*front, target_offset))
return NULL;
FragmentRef* result = m_FragRefFactory.allocate();
new (result) FragmentRef(*front, target_offset - front->getOffset());
return result;
}
return NULL;
}
/// getFragmentRef - give a LDSection in input file and an offset, return
/// the fragment reference.
FragmentRef*
Layout::getFragmentRef(const LDSection& pInputSection, uint64_t pOffset)
{
// find out which SectionData covers the range of input section header
const SectionData* sect_data = pInputSection.getSectionData();
// check range list
if (0 == m_SDRangeMap.count(sect_data))
return NULL;
if (sect_data->getFragmentList().empty())
return NULL;
RangeList* range_list = m_SDRangeMap[sect_data];
// find out the specific part in SectionData range
RangeList::iterator range, rangeEnd = range_list->end();
for (range = range_list->begin(); range != rangeEnd; ++range) {
// found the range
if (&pInputSection == range->header) {
break;
}
}
// range not found
if (range == rangeEnd) {
fatal(diag::err_section_not_laid_out) << pInputSection.name();
}
return getFragmentRef(*range, pOffset);
}
/// getFragmentRef - give a fragment and a big offset, return the fragment
/// reference in the section data.
///
/// @param pFrag - the given fragment
/// @param pBigOffset - the offset, can be larger than the fragment, but can
/// not larger than this input section.
/// @return if found, return the fragment. Otherwise, return NULL.
FragmentRef*
Layout::getFragmentRef(const Fragment& pFrag, uint64_t pBigOffset)
{
if (!hasLayoutOffset(pFrag)) {
// compute layout order, offset
setFragmentLayoutOrder(const_cast<Fragment*>(&pFrag));
setFragmentLayoutOffset(const_cast<Fragment*>(&pFrag));
}
// find out which SectionData covers the range of input section header
const SectionData* sect_data = pFrag.getParent();
// check range list
if (0 == m_SDRangeMap.count(sect_data)) {
llvm::report_fatal_error(llvm::Twine("SectionData has no") +
llvm::Twine(" correponding range list.\n"));
}
if (sect_data->getFragmentList().empty())
return NULL;
RangeList* range_list = m_SDRangeMap[sect_data];
// find out the specific part in SectionData range
uint64_t target_offset = pBigOffset + pFrag.getOffset();
RangeList::iterator range, rangeEnd = range_list->end();
for (range = range_list->begin(); range != rangeEnd; ++range) {
if (isEmptyRange(*range))
continue;
if (getRear(*range)->getOffset() >= target_offset) {
break;
}
}
// range not found
if (range == rangeEnd) {
llvm::report_fatal_error(llvm::Twine("the offset is too big that") +
llvm::Twine(" never be in the range list.\n"));
}
return getFragmentRef(*range, pBigOffset);
}
uint64_t Layout::getOutputOffset(const Fragment& pFrag)
{
if (!hasLayoutOffset(pFrag)) {
// compute layout order, offset
setFragmentLayoutOrder(const_cast<Fragment*>(&pFrag));
setFragmentLayoutOffset(const_cast<Fragment*>(&pFrag));
}
return pFrag.getOffset();
}
uint64_t Layout::getOutputOffset(const Fragment& pFrag) const
{
if (!hasLayoutOffset(pFrag)) {
llvm::report_fatal_error(llvm::Twine("INTERNAL BACKEND ERROR: ") +
llvm::Twine("the function ") +
llvm::Twine(__func__) +
llvm::Twine(" can not be used before layout().\n"));
}
return pFrag.getOffset();
}
uint64_t Layout::getOutputOffset(const FragmentRef& pFragRef)
{
return getOutputOffset(*(pFragRef.frag())) + pFragRef.offset();
}
uint64_t Layout::getOutputOffset(const FragmentRef& pFragRef) const
{
return getOutputOffset(*(pFragRef.frag())) + pFragRef.offset();
}
void Layout::sortSectionOrder(const Output& pOutput,
const TargetLDBackend& pBackend,
const MCLDInfo& pInfo)
{
typedef std::pair<LDSection*, unsigned int> SectOrder;
typedef std::vector<SectOrder > SectListTy;
SectListTy sect_list;
// get section order from backend
for (size_t index = 0; index < m_SectionOrder.size(); ++index)
sect_list.push_back(std::make_pair(
m_SectionOrder[index],
pBackend.getSectionOrder(pOutput, *m_SectionOrder[index], pInfo)));
// simple insertion sort should be fine for general cases such as so and exec
for (unsigned int i = 1; i < sect_list.size(); ++i) {
SectOrder order = sect_list[i];
int j = i - 1;
while (j >= 0 && sect_list[j].second > order.second) {
sect_list[j + 1] = sect_list[j];
--j;
}
sect_list[j + 1] = order;
}
// update the sorted ordering to m_SectionOrder
m_SectionOrder.clear();
for (size_t index = 0; index < sect_list.size(); ++index) {
m_SectionOrder.push_back(sect_list[index].first);
}
}
/// layout - layout the sections
/// 1. finalize fragment offset
/// 2. compute section order
/// 3. finalize section offset
bool Layout::layout(Output& pOutput,
const TargetLDBackend& pBackend,
const MCLDInfo& pInfo)
{
// determine what sections in output context will go into final output, and
// push the needed sections into m_SectionOrder for later processing
assert(pOutput.hasContext());
LDContext& output_context = *pOutput.context();
LDContext::sect_iterator it, itEnd = output_context.sectEnd();
for (it = output_context.sectBegin(); it != itEnd; ++it) {
// calculate 1. all fragment offset, and 2. the section order
LDSection* sect = *it;
switch (sect->kind()) {
// ignore if there is no SectionData for certain section kinds
case LDFileFormat::Regular:
case LDFileFormat::Target:
case LDFileFormat::MetaData:
case LDFileFormat::BSS:
case LDFileFormat::Debug:
case LDFileFormat::EhFrame:
case LDFileFormat::GCCExceptTable:
if (0 != sect->size()) {
if (NULL != sect->getSectionData() &&
!sect->getSectionData()->getFragmentList().empty()) {
// make sure that all fragments are valid
Fragment& frag = sect->getSectionData()->getFragmentList().back();
setFragmentLayoutOrder(&frag);
setFragmentLayoutOffset(&frag);
}
m_SectionOrder.push_back(sect);
}
break;
// take NULL directly
case LDFileFormat::Null:
m_SectionOrder.push_back(sect);
break;
// ignore if section size is 0
case LDFileFormat::NamePool:
case LDFileFormat::Relocation:
case LDFileFormat::Note:
case LDFileFormat::EhFrameHdr:
if (0 != sect->size())
m_SectionOrder.push_back(sect);
break;
case LDFileFormat::Group:
if (MCLDFile::Object == pOutput.type()) {
//TODO: support incremental linking
;
}
break;
case LDFileFormat::Version:
if (0 != sect->size()) {
m_SectionOrder.push_back(sect);
warning(diag::warn_unsupported_symbolic_versioning) << sect->name();
}
break;
default:
if (0 != sect->size()) {
error(diag::err_unsupported_section) << sect->name() << sect->kind();
}
break;
}
}
// perform sorting on m_SectionOrder to get a ordering for final layout
sortSectionOrder(pOutput, pBackend, pInfo);
// Backend defines the section start offset for section 1.
uint64_t offset = pBackend.sectionStartOffset();
for (size_t index = 1; index < m_SectionOrder.size(); ++index) {
// compute the section offset and handle alignment also. And ignore section 0
// (NULL in ELF/COFF), and MachO starts from section 1.
if (LDFileFormat::BSS != m_SectionOrder[index - 1]->kind()) {
// we should not preserve file space for the BSS section.
offset += m_SectionOrder[index - 1]->size();
}
alignAddress(offset, m_SectionOrder[index]->align());
m_SectionOrder[index]->setOffset(offset);
}
// FIXME: Currently Writer bases on the section table in output context to
// write out sections, so we have to update its content..
output_context.getSectionTable().clear();
for (size_t index = 0; index < m_SectionOrder.size(); ++index) {
output_context.getSectionTable().push_back(m_SectionOrder[index]);
// after sorting, update the correct output section indices
m_SectionOrder[index]->setIndex(index);
}
return true;
}
bool Layout::isValidOffset(const Fragment& pFrag, uint64_t pTargetOffset) const
{
uint64_t size = computeFragmentSize(*this, pFrag);
if (0x0 == size)
return (pTargetOffset == pFrag.getOffset());
if (NULL != pFrag.getNextNode())
return (pTargetOffset >= pFrag.getOffset() && pTargetOffset < pFrag.getNextNode()->getOffset());
return (pTargetOffset >= pFrag.getOffset() && pTargetOffset < (pFrag.getOffset() + size));
}