Home | History | Annotate | Download | only in quipper 
      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 "base/logging.h"
      8 
      9 namespace quipper {
     10 
     11 AddressMapper::AddressMapper(const AddressMapper& source) {
     12   mappings_ = source.mappings_;
     13 }
     14 
     15 bool AddressMapper::Map(const uint64_t real_addr,
     16                         const uint64_t size,
     17                         const bool remove_existing_mappings) {
     18   return MapWithID(real_addr, size, kuint64max, 0, remove_existing_mappings);
     19 }
     20 
     21 bool AddressMapper::MapWithID(const uint64_t real_addr,
     22                               const uint64_t size,
     23                               const uint64_t id,
     24                               const uint64_t offset_base,
     25                               bool remove_existing_mappings) {
     26   MappedRange range;
     27   range.real_addr = real_addr;
     28   range.size = size;
     29   range.id = id;
     30   range.offset_base = offset_base;
     31 
     32   if (size == 0) {
     33     LOG(ERROR) << "Must allocate a nonzero-length address range.";
     34     return false;
     35   }
     36 
     37   // Check that this mapping does not overflow the address space.
     38   if (real_addr + size - 1 != kuint64max &&
     39       !(real_addr + size > real_addr)) {
     40     DumpToLog();
     41     LOG(ERROR) << "Address mapping at " << std::hex << real_addr
     42                << " with size " << std::hex << size << " overflows.";
     43     return false;
     44   }
     45 
     46   // Check for collision with an existing mapping.  This must be an overlap that
     47   // does not result in one range being completely covered by another
     48   MappingList::iterator iter;
     49   MappingList mappings_to_delete;
     50   bool old_range_found = false;
     51   MappedRange old_range;
     52   for (iter = mappings_.begin(); iter != mappings_.end(); ++iter) {
     53     if (!iter->Intersects(range))
     54       continue;
     55     // Quit if existing ranges that collide aren't supposed to be removed.
     56     if (!remove_existing_mappings)
     57       return false;
     58     if (!old_range_found && iter->Covers(range) && iter->size > range.size) {
     59       old_range_found = true;
     60       old_range = *iter;
     61       continue;
     62     }
     63     mappings_to_delete.push_back(*iter);
     64   }
     65 
     66   while (!mappings_to_delete.empty()) {
     67     const MappedRange& range = mappings_to_delete.front();
     68     CHECK(Unmap(range));
     69     mappings_to_delete.pop_front();
     70   }
     71 
     72   // Otherwise check for this range being covered by another range.  If that
     73   // happens, split or reduce the existing range to make room.
     74   if (old_range_found) {
     75     CHECK(Unmap(old_range));
     76 
     77     uint64_t gap_before = range.real_addr - old_range.real_addr;
     78     uint64_t gap_after = (old_range.real_addr + old_range.size) -
     79                          (range.real_addr + range.size);
     80 
     81     if (gap_before) {
     82       CHECK(MapWithID(old_range.real_addr,
     83                       gap_before,
     84                       old_range.id,
     85                       old_range.offset_base,
     86                       false));
     87     }
     88 
     89     CHECK(MapWithID(range.real_addr, range.size, id, offset_base, false));
     90 
     91     if (gap_after) {
     92       CHECK(MapWithID(range.real_addr + range.size,
     93                       gap_after,
     94                       old_range.id,
     95                       old_range.offset_base + gap_before + range.size,
     96                       false));
     97     }
     98 
     99     return true;
    100   }
    101 
    102   // Now search for a location for the new range.  It should be in the first
    103   // free block in quipper space.
    104 
    105   // If there is no existing mapping, add it to the beginning of quipper space.
    106   if (mappings_.empty()) {
    107     range.mapped_addr = 0;
    108     range.unmapped_space_after = kuint64max - range.size;
    109     mappings_.push_back(range);
    110     return true;
    111   }
    112 
    113   // If there is space before the first mapped range in quipper space, use it.
    114   if (mappings_.begin()->mapped_addr >= range.size) {
    115     range.mapped_addr = 0;
    116     range.unmapped_space_after = mappings_.begin()->mapped_addr - range.size;
    117     mappings_.push_front(range);
    118     return true;
    119   }
    120 
    121   // Otherwise, search through the existing mappings for a free block after one
    122   // of them.
    123   for (iter = mappings_.begin(); iter != mappings_.end(); ++iter) {
    124     if (iter->unmapped_space_after < range.size)
    125       continue;
    126 
    127     range.mapped_addr = iter->mapped_addr + iter->size;
    128     range.unmapped_space_after = iter->unmapped_space_after - range.size;
    129     iter->unmapped_space_after = 0;
    130 
    131     mappings_.insert(++iter, range);
    132     return true;
    133   }
    134 
    135   // If it still hasn't succeeded in mapping, it means there is no free space in
    136   // quipper space large enough for a mapping of this size.
    137   DumpToLog();
    138   LOG(ERROR) << "Could not find space to map addr=" << std::hex << real_addr
    139              << " with size " << std::hex << size;
    140   return false;
    141 }
    142 
    143 void AddressMapper::DumpToLog() const {
    144   MappingList::const_iterator it;
    145   for (it = mappings_.begin(); it != mappings_.end(); ++it) {
    146     LOG(INFO) << " real_addr: " << std::hex << it->real_addr
    147               << " mapped: " << std::hex << it->mapped_addr
    148               << " id: " << std::hex << it->id
    149               << " size: " << std::hex << it->size;
    150   }
    151 }
    152 
    153 bool AddressMapper::GetMappedAddress(const uint64_t real_addr,
    154                                      uint64_t* mapped_addr) const {
    155   CHECK(mapped_addr);
    156   MappingList::const_iterator iter;
    157   for (iter = mappings_.begin(); iter != mappings_.end(); ++iter) {
    158     if (!iter->ContainsAddress(real_addr))
    159       continue;
    160     *mapped_addr = iter->mapped_addr + real_addr - iter->real_addr;
    161     return true;
    162   }
    163   return false;
    164 }
    165 
    166 bool AddressMapper::GetMappedIDAndOffset(const uint64_t real_addr,
    167                                          uint64_t* id,
    168                                          uint64_t* offset) const {
    169   CHECK(id);
    170   CHECK(offset);
    171   MappingList::const_iterator iter;
    172   for (iter = mappings_.begin(); iter != mappings_.end(); ++iter) {
    173     if (!iter->ContainsAddress(real_addr))
    174       continue;
    175     *id = iter->id;
    176     *offset = real_addr - iter->real_addr + iter->offset_base;
    177     return true;
    178   }
    179   return false;
    180 }
    181 
    182 uint64_t AddressMapper::GetMaxMappedLength() const {
    183   if (IsEmpty())
    184     return 0;
    185 
    186   uint64_t min = mappings_.begin()->mapped_addr;
    187 
    188   MappingList::const_iterator iter = mappings_.end();
    189   --iter;
    190   uint64_t max = iter->mapped_addr + iter->size;
    191 
    192   return max - min;
    193 }
    194 
    195 bool AddressMapper::Unmap(const MappedRange& range) {
    196   MappingList::iterator iter;
    197   // TODO(sque): this is highly inefficient since Unmap() is called from a
    198   // function that has already iterated to the right place within |mappings_|.
    199   // For a first revision, I am sacrificing efficiency for of clarity, due to
    200   // the trickiness of removing elements using iterators.
    201   for (iter = mappings_.begin(); iter != mappings_.end(); ++iter) {
    202     if (range.real_addr == iter->real_addr && range.size == iter->size) {
    203       // Add the freed up space to the free space counter of the previous
    204       // mapped region, if it exists.
    205       if (iter != mappings_.begin()) {
    206         --iter;
    207         iter->unmapped_space_after += range.size + range.unmapped_space_after;
    208         ++iter;
    209       }
    210       mappings_.erase(iter);
    211       return true;
    212     }
    213   }
    214   return false;
    215 }
    216 
    217 }  // namespace quipper
    218