// Copyright (c) 2013 The Chromium OS Authors. All rights reserved.
|
// Use of this source code is governed by a BSD-style license that can be
|
// found in the LICENSE file.
|
|
#include "address_mapper.h"
|
|
#include <stdint.h>
|
|
#include <vector>
|
|
#include "base/logging.h"
|
|
namespace quipper {
|
|
AddressMapper::AddressMapper(const AddressMapper& other) {
|
// Copy over most members naively.
|
mappings_ = other.mappings_;
|
page_alignment_ = other.page_alignment_;
|
|
// Reconstruct mapping of real addresses to mapped ranges.
|
for (auto iter = mappings_.begin(); iter != mappings_.end(); ++iter) {
|
real_addr_to_mapped_range_[iter->real_addr] = iter;
|
}
|
}
|
|
bool AddressMapper::MapWithID(const uint64_t real_addr, const uint64_t size,
|
const uint64_t id, const uint64_t offset_base,
|
bool remove_existing_mappings) {
|
if (size == 0) {
|
LOG(ERROR) << "Must allocate a nonzero-length address range.";
|
return false;
|
}
|
|
// Check that this mapping does not overflow the address space.
|
if (real_addr + size - 1 != UINT64_MAX && !(real_addr + size > real_addr)) {
|
DumpToLog();
|
LOG(ERROR) << "Address mapping at " << std::hex << real_addr
|
<< " with size " << std::hex << size << " overflows.";
|
return false;
|
}
|
|
MappedRange range;
|
range.real_addr = real_addr;
|
range.size = size;
|
range.id = id;
|
range.offset_base = offset_base;
|
|
// Check for collision with an existing mapping. This must be an overlap that
|
// does not result in one range being completely covered by another.
|
|
// First determine the range of mappings that could overlap with the new
|
// mapping in real space.
|
|
// lower_bound returns the first range with starting addr >= |real_addr|. The
|
// preceding range could also possibly overlap with the new range.
|
auto map_iter_start = real_addr_to_mapped_range_.lower_bound(real_addr);
|
if (map_iter_start != real_addr_to_mapped_range_.begin()) --map_iter_start;
|
// lower_bound returns the first range with starting addr beyond the end of
|
// the new mapping range.
|
auto map_iter_end = real_addr_to_mapped_range_.lower_bound(real_addr + size);
|
|
std::vector<MappingList::iterator> mappings_to_delete;
|
MappingList::iterator old_range_iter = mappings_.end();
|
for (auto map_iter = map_iter_start; map_iter != map_iter_end; ++map_iter) {
|
auto iter = map_iter->second;
|
if (!iter->Intersects(range)) continue;
|
// Quit if existing ranges that collide aren't supposed to be removed.
|
if (!remove_existing_mappings) return false;
|
if (old_range_iter == mappings_.end() && iter->Covers(range) &&
|
iter->size > range.size) {
|
old_range_iter = iter;
|
continue;
|
}
|
mappings_to_delete.push_back(iter);
|
}
|
|
for (MappingList::iterator mapping_iter : mappings_to_delete)
|
Unmap(mapping_iter);
|
mappings_to_delete.clear();
|
|
// Otherwise check for this range being covered by another range. If that
|
// happens, split or reduce the existing range to make room.
|
if (old_range_iter != mappings_.end()) {
|
// Make a copy of the old mapping before removing it.
|
const MappedRange old_range = *old_range_iter;
|
Unmap(old_range_iter);
|
|
uint64_t gap_before = range.real_addr - old_range.real_addr;
|
uint64_t gap_after =
|
(old_range.real_addr + old_range.size) - (range.real_addr + range.size);
|
|
// If the new mapping is not aligned to a page boundary at either its start
|
// or end, it will require the end of the old mapping range to be moved,
|
// which is not allowed.
|
if (page_alignment_) {
|
if ((gap_before && GetAlignedOffset(range.real_addr)) ||
|
(gap_after && GetAlignedOffset(range.real_addr + range.size))) {
|
LOG(ERROR) << "Split mapping must result in page-aligned mappings.";
|
return false;
|
}
|
}
|
|
if (gap_before) {
|
if (!MapWithID(old_range.real_addr, gap_before, old_range.id,
|
old_range.offset_base, false)) {
|
LOG(ERROR) << "Could not map old range from " << std::hex
|
<< old_range.real_addr << " to "
|
<< old_range.real_addr + gap_before;
|
return false;
|
}
|
}
|
|
if (!MapWithID(range.real_addr, range.size, id, offset_base, false)) {
|
LOG(ERROR) << "Could not map new range at " << std::hex << range.real_addr
|
<< " to " << range.real_addr + range.size << " over old range";
|
return false;
|
}
|
|
if (gap_after) {
|
if (!MapWithID(range.real_addr + range.size, gap_after, old_range.id,
|
old_range.offset_base + gap_before + range.size, false)) {
|
LOG(ERROR) << "Could not map old range from " << std::hex
|
<< old_range.real_addr << " to "
|
<< old_range.real_addr + gap_before;
|
return false;
|
}
|
}
|
|
return true;
|
}
|
|
// Now search for a location for the new range. It should be in the first
|
// free block in quipper space.
|
|
uint64_t page_offset =
|
page_alignment_ ? GetAlignedOffset(range.real_addr) : 0;
|
|
// If there is no existing mapping, add it to the beginning of quipper space.
|
if (IsEmpty()) {
|
range.mapped_addr = page_offset;
|
range.unmapped_space_after = UINT64_MAX - range.size - page_offset;
|
mappings_.push_back(range);
|
real_addr_to_mapped_range_.insert(
|
std::make_pair(range.real_addr, mappings_.begin()));
|
return true;
|
}
|
|
// If there is space before the first mapped range in quipper space, use it.
|
if (mappings_.begin()->mapped_addr >= range.size + page_offset) {
|
range.mapped_addr = page_offset;
|
range.unmapped_space_after =
|
mappings_.begin()->mapped_addr - range.size - page_offset;
|
mappings_.push_front(range);
|
MappingList::iterator iter = mappings_.begin();
|
real_addr_to_mapped_range_.insert(std::make_pair(range.real_addr, iter));
|
return true;
|
}
|
|
// Otherwise, search through the existing mappings for a free block after one
|
// of them.
|
for (auto iter = mappings_.begin(); iter != mappings_.end(); ++iter) {
|
MappedRange& existing_mapping = *iter;
|
if (page_alignment_) {
|
uint64_t end_of_existing_mapping =
|
existing_mapping.mapped_addr + existing_mapping.size;
|
|
// Find next page boundary after end of this existing mapping.
|
uint64_t existing_page_offset = GetAlignedOffset(end_of_existing_mapping);
|
uint64_t next_page_boundary =
|
existing_page_offset
|
? end_of_existing_mapping - existing_page_offset + page_alignment_
|
: end_of_existing_mapping;
|
// Compute where the new mapping would end if it were aligned to this
|
// page boundary.
|
uint64_t mapping_offset = GetAlignedOffset(range.real_addr);
|
uint64_t end_of_new_mapping =
|
next_page_boundary + mapping_offset + range.size;
|
uint64_t end_of_unmapped_space_after =
|
end_of_existing_mapping + existing_mapping.unmapped_space_after;
|
|
// Check if there's enough room in the unmapped space following the
|
// current existing mapping for the page-aligned mapping.
|
if (end_of_new_mapping > end_of_unmapped_space_after) continue;
|
|
range.mapped_addr = next_page_boundary + mapping_offset;
|
range.unmapped_space_after =
|
end_of_unmapped_space_after - end_of_new_mapping;
|
existing_mapping.unmapped_space_after =
|
range.mapped_addr - end_of_existing_mapping;
|
} else {
|
if (existing_mapping.unmapped_space_after < range.size) continue;
|
// Insert the new mapping range immediately after the existing one.
|
range.mapped_addr = existing_mapping.mapped_addr + existing_mapping.size;
|
range.unmapped_space_after =
|
existing_mapping.unmapped_space_after - range.size;
|
existing_mapping.unmapped_space_after = 0;
|
}
|
|
mappings_.insert(++iter, range);
|
--iter;
|
real_addr_to_mapped_range_.insert(std::make_pair(range.real_addr, iter));
|
return true;
|
}
|
|
// If it still hasn't succeeded in mapping, it means there is no free space in
|
// quipper space large enough for a mapping of this size.
|
DumpToLog();
|
LOG(ERROR) << "Could not find space to map addr=" << std::hex << real_addr
|
<< " with size " << std::hex << size;
|
return false;
|
}
|
|
void AddressMapper::DumpToLog() const {
|
MappingList::const_iterator it;
|
for (it = mappings_.begin(); it != mappings_.end(); ++it) {
|
LOG(INFO) << " real_addr: " << std::hex << it->real_addr
|
<< " mapped: " << std::hex << it->mapped_addr
|
<< " id: " << std::hex << it->id
|
<< " size: " << std::hex << it->size;
|
}
|
}
|
|
bool AddressMapper::GetMappedAddressAndListIterator(
|
const uint64_t real_addr, uint64_t* mapped_addr,
|
MappingList::const_iterator* iter) const {
|
CHECK(mapped_addr);
|
CHECK(iter);
|
|
*iter = GetRangeContainingAddress(real_addr);
|
if (*iter == mappings_.end()) return false;
|
*mapped_addr = (*iter)->mapped_addr + real_addr - (*iter)->real_addr;
|
return true;
|
}
|
|
void AddressMapper::GetMappedIDAndOffset(
|
const uint64_t real_addr, MappingList::const_iterator real_addr_iter,
|
uint64_t* id, uint64_t* offset) const {
|
CHECK(real_addr_iter != mappings_.end());
|
CHECK(id);
|
CHECK(offset);
|
|
*id = real_addr_iter->id;
|
*offset = real_addr - real_addr_iter->real_addr + real_addr_iter->offset_base;
|
}
|
|
uint64_t AddressMapper::GetMaxMappedLength() const {
|
if (IsEmpty()) return 0;
|
|
uint64_t min = mappings_.begin()->mapped_addr;
|
|
MappingList::const_iterator iter = mappings_.end();
|
--iter;
|
uint64_t max = iter->mapped_addr + iter->size;
|
|
return max - min;
|
}
|
|
void AddressMapper::Unmap(MappingList::iterator mapping_iter) {
|
// Add the freed up space to the free space counter of the previous
|
// mapped region, if it exists.
|
if (mapping_iter != mappings_.begin()) {
|
const MappedRange& range = *mapping_iter;
|
MappingList::iterator previous_range_iter = std::prev(mapping_iter);
|
previous_range_iter->unmapped_space_after +=
|
range.size + range.unmapped_space_after;
|
}
|
real_addr_to_mapped_range_.erase(mapping_iter->real_addr);
|
mappings_.erase(mapping_iter);
|
}
|
|
AddressMapper::MappingList::const_iterator
|
AddressMapper::GetRangeContainingAddress(uint64_t real_addr) const {
|
// Find the first range that has a higher real address than the given one.
|
MappingMap::const_iterator target_map_iter =
|
real_addr_to_mapped_range_.upper_bound(real_addr);
|
|
if (target_map_iter == real_addr_to_mapped_range_.begin()) {
|
// The lowest real address in existing mappings is higher than the new
|
// mapping address, so |real_addr| does not fall into any mapping.
|
return mappings_.end();
|
}
|
|
// Otherwise, the previous mapping could possibly contain |real_addr|.
|
--target_map_iter;
|
MappingList::const_iterator list_iter = target_map_iter->second;
|
if (!list_iter->ContainsAddress(real_addr)) return mappings_.end();
|
|
return list_iter;
|
}
|
|
} // namespace quipper
|
