| // Copyright 2016 Google Inc. All Rights Reserved. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| // RagneMap maps |
| // |
| // [uint64_t, uint64_t) -> std::string, [optional other range base] |
| // |
| // where ranges must be non-overlapping. |
| // |
| // This is used to map the address space (either pointer offsets or file |
| // offsets). |
| // |
| // The other range base allows us to use this RangeMap to translate addresses |
| // from this domain to another one (like vm_addr -> file_addr or vice versa). |
| // |
| // This type is only exposed in the .h file for unit testing purposes. |
| |
| #ifndef BLOATY_RANGE_MAP_H_ |
| #define BLOATY_RANGE_MAP_H_ |
| |
| #include <assert.h> |
| #include <stdint.h> |
| |
| #include <exception> |
| #include <map> |
| #include <stdexcept> |
| #include <vector> |
| |
| #include "absl/strings/str_cat.h" |
| |
| namespace bloaty { |
| |
| class RangeMapTest; |
| |
| class RangeMap { |
| public: |
| RangeMap() = default; |
| RangeMap(RangeMap&& other) = default; |
| RangeMap& operator=(RangeMap&& other) = default; |
| RangeMap(RangeMap& other) = delete; |
| RangeMap& operator=(RangeMap& other) = delete; |
| |
| // Adds a range to this map. |
| void AddRange(uint64_t addr, uint64_t size, const std::string& val); |
| |
| // Adds a range to this map (in domain D1) that also corresponds to a |
| // different range in a different map (in domain D2). The correspondance will |
| // be noted to allow us to translate into the other domain later. |
| void AddDualRange(uint64_t addr, uint64_t size, uint64_t otheraddr, |
| const std::string& val); |
| |
| // Adds a range to this map (in domain D1), and also adds corresponding ranges |
| // to |other| (in domain D2), using |translator| (in domain D1) to translate |
| // D1->D2. The translation is performed using information from previous |
| // AddDualRange() calls on |translator|. |
| // |
| // Returns true if the entire range [addr, size] was present in the |
| // |translator| map. (This does not necessarily mean that every part of the |
| // range was actually translated). If the return value is false, then the |
| // contents of |this| and |other| are undefined (Bloaty will bail in this |
| // case). |
| bool AddRangeWithTranslation(uint64_t addr, uint64_t size, |
| const std::string& val, |
| const RangeMap& translator, bool verbose, |
| RangeMap* other); |
| |
| // Collapses adjacent ranges with the same label. This reduces memory usage |
| // and removes redundant noise from the output when dumping a full memory map |
| // (in normal Bloaty output it makes no difference, because all labels with |
| // the same name are added together). |
| // |
| // TODO(haberman): see if we can do this at insertion time instead, so it |
| // doesn't require a second pass. |
| void Compress(); |
| |
| // Returns whether this RangeMap fully covers the given range. |
| bool CoversRange(uint64_t addr, uint64_t size) const; |
| |
| // Returns the maximum address contained in this map. |
| uint64_t GetMaxAddress() const; |
| |
| // Translates |addr| into the other domain, returning |true| if this was |
| // successful. |
| bool Translate(uint64_t addr, uint64_t *translated) const; |
| |
| // Looks for a range within this map that contains |addr|. If found, returns |
| // true and sets |label| to the corresponding label, and |offset| to the |
| // offset from the beginning of this range. |
| bool TryGetLabel(uint64_t addr, std::string* label) const; |
| bool TryGetLabelForRange(uint64_t addr, uint64_t size, |
| std::string* label) const; |
| |
| // Looks for a range that starts exactly on |addr|. If it exists, returns |
| // true and sets |size| to its size. |
| bool TryGetSize(uint64_t addr, uint64_t* size) const; |
| |
| std::string DebugString() const; |
| |
| static std::string EntryDebugString(uint64_t addr, uint64_t size, |
| uint64_t other_start, |
| const std::string& label) { |
| std::string end = |
| size == kUnknownSize ? "?" : absl::StrCat(absl::Hex(addr + size)); |
| std::string ret = absl::StrCat("[", absl::Hex(addr), ", ", end, |
| "] (size=", absl::Hex(size), "): ", label); |
| if (other_start != UINT64_MAX) { |
| absl::StrAppend(&ret, ", other_start=", absl::Hex(other_start)); |
| } |
| return ret; |
| } |
| |
| template <class T> |
| std::string EntryDebugString(T it) const { |
| if (it == mappings_.end()) { |
| return "[end]"; |
| } else { |
| return EntryDebugString(it->first, it->second.size, |
| it->second.other_start, it->second.label); |
| } |
| } |
| |
| template <class Func> |
| static void ComputeRollup(const std::vector<const RangeMap*>& range_maps, |
| Func func); |
| |
| template <class Func> |
| void ForEachRange(Func func) const { |
| for (auto iter = mappings_.begin(); iter != mappings_.end(); ++iter) { |
| func(iter->first, RangeEnd(iter) - iter->first); |
| } |
| } |
| |
| template <class Func> |
| void ForEachRangeWithStart(uint64_t start, Func func) const { |
| for (auto iter = FindContaining(start); iter != mappings_.end(); ++iter) { |
| if (!func(iter->second.label, iter->first, |
| RangeEnd(iter) - iter->first)) { |
| return; |
| } |
| } |
| } |
| |
| static constexpr uint64_t kUnknownSize = UINT64_MAX; |
| |
| private: |
| friend class RangeMapTest; |
| static const uint64_t kNoTranslation = UINT64_MAX; |
| |
| struct Entry { |
| Entry(const std::string& label_, uint64_t size_, uint64_t other_) |
| : label(label_), size(size_), other_start(other_) {} |
| std::string label; |
| uint64_t size; |
| uint64_t other_start; // kNoTranslation if there is no mapping. |
| |
| bool HasTranslation() const { return other_start != kNoTranslation; } |
| bool HasFallbackLabel() const { return !label.empty() && label[0] == '['; } |
| |
| // We assume that short regions that were unattributed (have fallback |
| // labels) are actually padding. We could probably make this heuristic |
| // a bit more robust. |
| bool IsShortFallback() const { return size <= 16 && HasFallbackLabel(); } |
| }; |
| |
| typedef std::map<uint64_t, Entry> Map; |
| Map mappings_; |
| |
| template <class T> |
| void CheckConsistency(T iter) const { |
| assert(iter->first + iter->second.size > iter->first); |
| assert(iter == mappings_.begin() || |
| RangeEnd(std::prev(iter)) <= iter->first); |
| assert(std::next(iter) == mappings_.end() || |
| RangeEnd(iter) <= std::next(iter)->first); |
| } |
| |
| template <class T> |
| bool EntryContains(T iter, uint64_t addr) const { |
| return addr >= iter->first && addr < RangeEnd(iter); |
| } |
| |
| template <class T> |
| bool EntryContainsStrict(T iter, uint64_t addr) const { |
| if (iter->second.size == kUnknownSize) { |
| return iter->first == addr; |
| } else { |
| return addr >= iter->first && addr < RangeEnd(iter); |
| } |
| } |
| |
| template <class T> |
| void MaybeSetLabel(T iter, const std::string& label, uint64_t addr, |
| uint64_t end); |
| |
| // When the size is unknown return |unknown| for the end. |
| uint64_t RangeEndUnknownLimit(Map::const_iterator iter, |
| uint64_t unknown) const { |
| if (iter->second.size == kUnknownSize) { |
| Map::const_iterator next = std::next(iter); |
| if (IterIsEnd(next) || next->first > unknown) { |
| return unknown; |
| } else { |
| return next->first; |
| } |
| } else { |
| uint64_t ret = iter->first + iter->second.size; |
| assert(ret > iter->first); |
| return ret; |
| } |
| } |
| |
| uint64_t RangeEnd(Map::const_iterator iter) const { |
| return RangeEndUnknownLimit(iter, UINT64_MAX); |
| } |
| |
| bool IterIsEnd(Map::const_iterator iter) const { |
| return iter == mappings_.end(); |
| } |
| |
| template <class T> |
| uint64_t TranslateWithEntry(T iter, uint64_t addr) const; |
| |
| template <class T> |
| bool TranslateAndTrimRangeWithEntry(T iter, uint64_t addr, uint64_t size, |
| uint64_t* trimmed_addr, |
| uint64_t* translated_addr, |
| uint64_t* trimmed_size) const; |
| |
| // Finds the entry that contains |addr|. If no such mapping exists, returns |
| // mappings_.end(). |
| Map::const_iterator FindContaining(uint64_t addr) const; |
| |
| // Finds the entry that contains |addr|, or the very next entry (which may be |
| // mappings_.end()). |
| Map::iterator FindContainingOrAfter(uint64_t addr); |
| Map::const_iterator FindContainingOrAfter(uint64_t addr) const; |
| }; |
| |
| template <class Func> |
| void RangeMap::ComputeRollup(const std::vector<const RangeMap*>& range_maps, |
| Func func) { |
| assert(range_maps.size() > 0); |
| std::vector<Map::const_iterator> iters; |
| |
| if (range_maps[0]->mappings_.empty()) { |
| for (int i = 0; i < range_maps.size(); i++) { |
| const RangeMap* range_map = range_maps[i]; |
| if (!range_map->mappings_.empty()) { |
| printf( |
| "Error, range (%s) exists at index %d, but base map is empty\n", |
| range_map->EntryDebugString(range_map->mappings_.begin()).c_str(), |
| i); |
| assert(false); |
| throw std::runtime_error("Range extends beyond base map."); |
| } |
| } |
| return; |
| } |
| |
| iters.reserve(range_maps.size()); |
| for (auto range_map : range_maps) { |
| iters.push_back(range_map->mappings_.begin()); |
| } |
| |
| // Iterate over all ranges in parallel to perform this transformation: |
| // |
| // ----- ----- ----- --------------- |
| // | | 1 A,X,1 |
| // | X ----- --------------- |
| // | | | A,X,2 |
| // A ----- | --------------- |
| // | | | | |
| // | | 2 -----> | |
| // | Y | A,Y,2 |
| // | | | | |
| // ----- | | --------------- |
| // B | | B,Y,2 |
| // ----- ----- ----- --------------- |
| // |
| // |
| // ----- ----- ----- --------------- |
| // C Z 3 C,Z,3 |
| // ----- ----- ----- --------------- |
| // |
| // All input maps must cover exactly the same domain. |
| |
| // Outer loop: once per continuous (gapless) region. |
| while (true) { |
| std::vector<std::string> keys; |
| uint64_t current = 0; |
| |
| if (range_maps[0]->IterIsEnd(iters[0])) { |
| // Termination condition: all iterators must be at end. |
| for (int i = 0; i < range_maps.size(); i++) { |
| if (!range_maps[i]->IterIsEnd(iters[i])) { |
| printf( |
| "Error, range (%s) extends beyond final base map range " |
| "(%s)\n", |
| range_maps[i]->EntryDebugString(iters[i]).c_str(), |
| range_maps[0]->EntryDebugString(std::prev(iters[0])).c_str()); |
| assert(false); |
| throw std::runtime_error("Range extends beyond base map."); |
| } |
| } |
| return; |
| } else { |
| // Starting a new continuous range: all iterators must start at the same |
| // place. |
| current = iters[0]->first; |
| for (int i = 0; i < range_maps.size(); i++) { |
| if (range_maps[i]->IterIsEnd(iters[i])) { |
| printf( |
| "Error, no more ranges for index %d but we need one " |
| "to match (%s)\n", |
| i, range_maps[0]->EntryDebugString(iters[0]).c_str()); |
| assert(false); |
| throw std::runtime_error("No more ranges."); |
| } else if (iters[i]->first != current) { |
| printf( |
| "Error, range (%s) doesn't match the beginning of base range " |
| "(%s)\n", |
| range_maps[i]->EntryDebugString(iters[i]).c_str(), |
| range_maps[0]->EntryDebugString(iters[0]).c_str()); |
| assert(false); |
| throw std::runtime_error("No more ranges."); |
| } |
| keys.push_back(iters[i]->second.label); |
| } |
| } |
| |
| bool continuous = true; |
| |
| // Inner loop: once per range within the continuous region. |
| while (continuous) { |
| uint64_t next_break = UINT64_MAX; |
| |
| for (int i = 0; i < iters.size(); i++) { |
| next_break = std::min(next_break, range_maps[i]->RangeEnd(iters[i])); |
| } |
| |
| func(keys, current, next_break); |
| |
| // Advance all iterators with ranges ending at next_break. |
| for (int i = 0; i < iters.size(); i++) { |
| const RangeMap& map = *range_maps[i]; |
| Map::const_iterator& iter = iters[i]; |
| uint64_t end = continuous ? map.RangeEnd(iter) |
| : map.RangeEndUnknownLimit(iter, next_break); |
| |
| if (end != next_break) { |
| continue; |
| } |
| ++iter; |
| |
| // Test for discontinuity. |
| if (map.IterIsEnd(iter) || iter->first != next_break) { |
| if (i > 0 && continuous) { |
| printf( |
| "Error, gap between ranges (%s) and (%s) fails to cover base " |
| "range (%s)\n", |
| map.EntryDebugString(std::prev(iter)).c_str(), |
| map.EntryDebugString(iter).c_str(), |
| range_maps[0]->EntryDebugString(iters[0]).c_str()); |
| assert(false); |
| throw std::runtime_error("Entry range extends beyond base range"); |
| } |
| assert(i == 0 || !continuous); |
| continuous = false; |
| } else { |
| assert(continuous); |
| keys[i] = iter->second.label; |
| } |
| } |
| current = next_break; |
| } |
| } |
| } |
| |
| } // namespace bloaty |
| |
| #endif // BLOATY_RANGE_MAP_H_ |
