1 // Copyright (c) 2013 The Chromium OS Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "address_mapper.h" 6 7 #include <stdint.h> 8 9 #include <vector> 10 11 #include "base/logging.h" 12 13 namespace quipper { 14 15 AddressMapper::AddressMapper(const AddressMapper& other) { 16 // Copy over most members naively. 17 mappings_ = other.mappings_; 18 page_alignment_ = other.page_alignment_; 19 20 // Reconstruct mapping of real addresses to mapped ranges. 21 for (auto iter = mappings_.begin(); iter != mappings_.end(); ++iter) { 22 real_addr_to_mapped_range_[iter->real_addr] = iter; 23 } 24 } 25 26 bool AddressMapper::MapWithID(const uint64_t real_addr, const uint64_t size, 27 const uint64_t id, const uint64_t offset_base, 28 bool remove_existing_mappings) { 29 if (size == 0) { 30 LOG(ERROR) << "Must allocate a nonzero-length address range."; 31 return false; 32 } 33 34 // Check that this mapping does not overflow the address space. 35 if (real_addr + size - 1 != UINT64_MAX && !(real_addr + size > real_addr)) { 36 DumpToLog(); 37 LOG(ERROR) << "Address mapping at " << std::hex << real_addr 38 << " with size " << std::hex << size << " overflows."; 39 return false; 40 } 41 42 MappedRange range; 43 range.real_addr = real_addr; 44 range.size = size; 45 range.id = id; 46 range.offset_base = offset_base; 47 48 // Check for collision with an existing mapping. This must be an overlap that 49 // does not result in one range being completely covered by another. 50 51 // First determine the range of mappings that could overlap with the new 52 // mapping in real space. 53 54 // lower_bound returns the first range with starting addr >= |real_addr|. The 55 // preceding range could also possibly overlap with the new range. 56 auto map_iter_start = real_addr_to_mapped_range_.lower_bound(real_addr); 57 if (map_iter_start != real_addr_to_mapped_range_.begin()) --map_iter_start; 58 // lower_bound returns the first range with starting addr beyond the end of 59 // the new mapping range. 60 auto map_iter_end = real_addr_to_mapped_range_.lower_bound(real_addr + size); 61 62 std::vector<MappingList::iterator> mappings_to_delete; 63 MappingList::iterator old_range_iter = mappings_.end(); 64 for (auto map_iter = map_iter_start; map_iter != map_iter_end; ++map_iter) { 65 auto iter = map_iter->second; 66 if (!iter->Intersects(range)) continue; 67 // Quit if existing ranges that collide aren't supposed to be removed. 68 if (!remove_existing_mappings) return false; 69 if (old_range_iter == mappings_.end() && iter->Covers(range) && 70 iter->size > range.size) { 71 old_range_iter = iter; 72 continue; 73 } 74 mappings_to_delete.push_back(iter); 75 } 76 77 for (MappingList::iterator mapping_iter : mappings_to_delete) 78 Unmap(mapping_iter); 79 mappings_to_delete.clear(); 80 81 // Otherwise check for this range being covered by another range. If that 82 // happens, split or reduce the existing range to make room. 83 if (old_range_iter != mappings_.end()) { 84 // Make a copy of the old mapping before removing it. 85 const MappedRange old_range = *old_range_iter; 86 Unmap(old_range_iter); 87 88 uint64_t gap_before = range.real_addr - old_range.real_addr; 89 uint64_t gap_after = 90 (old_range.real_addr + old_range.size) - (range.real_addr + range.size); 91 92 // If the new mapping is not aligned to a page boundary at either its start 93 // or end, it will require the end of the old mapping range to be moved, 94 // which is not allowed. 95 if (page_alignment_) { 96 if ((gap_before && GetAlignedOffset(range.real_addr)) || 97 (gap_after && GetAlignedOffset(range.real_addr + range.size))) { 98 LOG(ERROR) << "Split mapping must result in page-aligned mappings."; 99 return false; 100 } 101 } 102 103 if (gap_before) { 104 if (!MapWithID(old_range.real_addr, gap_before, old_range.id, 105 old_range.offset_base, false)) { 106 LOG(ERROR) << "Could not map old range from " << std::hex 107 << old_range.real_addr << " to " 108 << old_range.real_addr + gap_before; 109 return false; 110 } 111 } 112 113 if (!MapWithID(range.real_addr, range.size, id, offset_base, false)) { 114 LOG(ERROR) << "Could not map new range at " << std::hex << range.real_addr 115 << " to " << range.real_addr + range.size << " over old range"; 116 return false; 117 } 118 119 if (gap_after) { 120 if (!MapWithID(range.real_addr + range.size, gap_after, old_range.id, 121 old_range.offset_base + gap_before + range.size, false)) { 122 LOG(ERROR) << "Could not map old range from " << std::hex 123 << old_range.real_addr << " to " 124 << old_range.real_addr + gap_before; 125 return false; 126 } 127 } 128 129 return true; 130 } 131 132 // Now search for a location for the new range. It should be in the first 133 // free block in quipper space. 134 135 uint64_t page_offset = 136 page_alignment_ ? GetAlignedOffset(range.real_addr) : 0; 137 138 // If there is no existing mapping, add it to the beginning of quipper space. 139 if (IsEmpty()) { 140 range.mapped_addr = page_offset; 141 range.unmapped_space_after = UINT64_MAX - range.size - page_offset; 142 mappings_.push_back(range); 143 real_addr_to_mapped_range_.insert( 144 std::make_pair(range.real_addr, mappings_.begin())); 145 return true; 146 } 147 148 // If there is space before the first mapped range in quipper space, use it. 149 if (mappings_.begin()->mapped_addr >= range.size + page_offset) { 150 range.mapped_addr = page_offset; 151 range.unmapped_space_after = 152 mappings_.begin()->mapped_addr - range.size - page_offset; 153 mappings_.push_front(range); 154 MappingList::iterator iter = mappings_.begin(); 155 real_addr_to_mapped_range_.insert(std::make_pair(range.real_addr, iter)); 156 return true; 157 } 158 159 // Otherwise, search through the existing mappings for a free block after one 160 // of them. 161 for (auto iter = mappings_.begin(); iter != mappings_.end(); ++iter) { 162 MappedRange& existing_mapping = *iter; 163 if (page_alignment_) { 164 uint64_t end_of_existing_mapping = 165 existing_mapping.mapped_addr + existing_mapping.size; 166 167 // Find next page boundary after end of this existing mapping. 168 uint64_t existing_page_offset = GetAlignedOffset(end_of_existing_mapping); 169 uint64_t next_page_boundary = 170 existing_page_offset 171 ? end_of_existing_mapping - existing_page_offset + page_alignment_ 172 : end_of_existing_mapping; 173 // Compute where the new mapping would end if it were aligned to this 174 // page boundary. 175 uint64_t mapping_offset = GetAlignedOffset(range.real_addr); 176 uint64_t end_of_new_mapping = 177 next_page_boundary + mapping_offset + range.size; 178 uint64_t end_of_unmapped_space_after = 179 end_of_existing_mapping + existing_mapping.unmapped_space_after; 180 181 // Check if there's enough room in the unmapped space following the 182 // current existing mapping for the page-aligned mapping. 183 if (end_of_new_mapping > end_of_unmapped_space_after) continue; 184 185 range.mapped_addr = next_page_boundary + mapping_offset; 186 range.unmapped_space_after = 187 end_of_unmapped_space_after - end_of_new_mapping; 188 existing_mapping.unmapped_space_after = 189 range.mapped_addr - end_of_existing_mapping; 190 } else { 191 if (existing_mapping.unmapped_space_after < range.size) continue; 192 // Insert the new mapping range immediately after the existing one. 193 range.mapped_addr = existing_mapping.mapped_addr + existing_mapping.size; 194 range.unmapped_space_after = 195 existing_mapping.unmapped_space_after - range.size; 196 existing_mapping.unmapped_space_after = 0; 197 } 198 199 mappings_.insert(++iter, range); 200 --iter; 201 real_addr_to_mapped_range_.insert(std::make_pair(range.real_addr, iter)); 202 return true; 203 } 204 205 // If it still hasn't succeeded in mapping, it means there is no free space in 206 // quipper space large enough for a mapping of this size. 207 DumpToLog(); 208 LOG(ERROR) << "Could not find space to map addr=" << std::hex << real_addr 209 << " with size " << std::hex << size; 210 return false; 211 } 212 213 void AddressMapper::DumpToLog() const { 214 MappingList::const_iterator it; 215 for (it = mappings_.begin(); it != mappings_.end(); ++it) { 216 LOG(INFO) << " real_addr: " << std::hex << it->real_addr 217 << " mapped: " << std::hex << it->mapped_addr 218 << " id: " << std::hex << it->id 219 << " size: " << std::hex << it->size; 220 } 221 } 222 223 bool AddressMapper::GetMappedAddressAndListIterator( 224 const uint64_t real_addr, uint64_t* mapped_addr, 225 MappingList::const_iterator* iter) const { 226 CHECK(mapped_addr); 227 CHECK(iter); 228 229 *iter = GetRangeContainingAddress(real_addr); 230 if (*iter == mappings_.end()) return false; 231 *mapped_addr = (*iter)->mapped_addr + real_addr - (*iter)->real_addr; 232 return true; 233 } 234 235 void AddressMapper::GetMappedIDAndOffset( 236 const uint64_t real_addr, MappingList::const_iterator real_addr_iter, 237 uint64_t* id, uint64_t* offset) const { 238 CHECK(real_addr_iter != mappings_.end()); 239 CHECK(id); 240 CHECK(offset); 241 242 *id = real_addr_iter->id; 243 *offset = real_addr - real_addr_iter->real_addr + real_addr_iter->offset_base; 244 } 245 246 uint64_t AddressMapper::GetMaxMappedLength() const { 247 if (IsEmpty()) return 0; 248 249 uint64_t min = mappings_.begin()->mapped_addr; 250 251 MappingList::const_iterator iter = mappings_.end(); 252 --iter; 253 uint64_t max = iter->mapped_addr + iter->size; 254 255 return max - min; 256 } 257 258 void AddressMapper::Unmap(MappingList::iterator mapping_iter) { 259 // Add the freed up space to the free space counter of the previous 260 // mapped region, if it exists. 261 if (mapping_iter != mappings_.begin()) { 262 const MappedRange& range = *mapping_iter; 263 MappingList::iterator previous_range_iter = std::prev(mapping_iter); 264 previous_range_iter->unmapped_space_after += 265 range.size + range.unmapped_space_after; 266 } 267 real_addr_to_mapped_range_.erase(mapping_iter->real_addr); 268 mappings_.erase(mapping_iter); 269 } 270 271 AddressMapper::MappingList::const_iterator 272 AddressMapper::GetRangeContainingAddress(uint64_t real_addr) const { 273 // Find the first range that has a higher real address than the given one. 274 MappingMap::const_iterator target_map_iter = 275 real_addr_to_mapped_range_.upper_bound(real_addr); 276 277 if (target_map_iter == real_addr_to_mapped_range_.begin()) { 278 // The lowest real address in existing mappings is higher than the new 279 // mapping address, so |real_addr| does not fall into any mapping. 280 return mappings_.end(); 281 } 282 283 // Otherwise, the previous mapping could possibly contain |real_addr|. 284 --target_map_iter; 285 MappingList::const_iterator list_iter = target_map_iter->second; 286 if (!list_iter->ContainsAddress(real_addr)) return mappings_.end(); 287 288 return list_iter; 289 } 290 291 } // namespace quipper 292