perfprofd/quipper/address_mapper.cc

   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