src/range_map.cc - third_party/bloaty - Git at Google

 // 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.

 #include "range_map.h"

 #include "bloaty.h"

 namespace bloaty {

 constexpr uint64_t RangeMap::kUnknownSize;

 template <class T>
 uint64_t RangeMap::TranslateWithEntry(T iter, uint64_t addr) const {
   assert(EntryContains(iter, addr));
   assert(iter->second.HasTranslation());
   return addr - iter->first + iter->second.other_start;
 }

 template <class T>
 bool RangeMap::TranslateAndTrimRangeWithEntry(T iter, uint64_t addr,
                                               uint64_t size, uint64_t* trimmed_addr,
                                               uint64_t* translated_addr,
                                               uint64_t* trimmed_size) const {
   addr = std::max(addr, iter->first);
   *trimmed_addr = addr;

   if (size == kUnknownSize) {
     *trimmed_size = kUnknownSize;
   } else {
     uint64_t end = std::min(addr + size, iter->first + iter->second.size);
     if (addr >= end) {
       *trimmed_size = 0;
       return false;
     }
     *trimmed_size = end - addr;
   }

   if (!iter->second.HasTranslation()) {
     return false;
   }

   *translated_addr = TranslateWithEntry(iter, addr);
   return true;
 }

 RangeMap::Map::const_iterator RangeMap::FindContaining(uint64_t addr) const {
   auto it = mappings_.upper_bound(addr);  // Entry directly after.
   if (it == mappings_.begin() || (--it, !EntryContains(it, addr))) {
     return mappings_.end();
   } else {
     return it;
   }
 }

 RangeMap::Map::iterator RangeMap::FindContainingOrAfter(uint64_t addr) {
   auto after = mappings_.upper_bound(addr);
   auto it = after;
   if (it != mappings_.begin() && (--it, EntryContains(it, addr))) {
     return it;  // Containing
   } else {
     return after;  // May be end().
   }
 }

 RangeMap::Map::const_iterator RangeMap::FindContainingOrAfter(
     uint64_t addr) const {
   auto after = mappings_.upper_bound(addr);
   auto it = after;
   if (it != mappings_.begin() && (--it, EntryContains(it, addr))) {
     return it;  // Containing
   } else {
     return after;  // May be end().
   }
 }

 bool RangeMap::Translate(uint64_t addr, uint64_t* translated) const {
   auto iter = FindContaining(addr);
   if (iter == mappings_.end() || !iter->second.HasTranslation()) {
     return false;
   } else {
     *translated = TranslateWithEntry(iter, addr);
     return true;
   }
 }

 bool RangeMap::TryGetLabel(uint64_t addr, std::string* label) const {
   auto iter = FindContaining(addr);
   if (iter == mappings_.end()) {
     return false;
   } else {
     *label = iter->second.label;
     return true;
   }
 }

 bool RangeMap::TryGetLabelForRange(uint64_t addr, uint64_t size,
                                    std::string* label) const {
   uint64_t end = addr + size;
   if (end < addr) {
     return false;
   }
   auto iter = FindContaining(addr);
   if (iter == mappings_.end()) {
     return false;
   } else {
     *label = iter->second.label;
     while (iter != mappings_.end() && iter->first + iter->second.size < end) {
       if (iter->second.label != *label) {
         return false;
       }
       ++iter;
     }
     return iter != mappings_.end();
   }
 }

 bool RangeMap::TryGetSize(uint64_t addr, uint64_t* size) const {
   auto iter = mappings_.find(addr);
   if (iter == mappings_.end()) {
     return false;
   } else {
     *size = iter->second.size;
     return true;
   }
 }

 std::string RangeMap::DebugString() const {
   std::string ret;
   for (auto it = mappings_.begin(); it != mappings_.end(); ++it) {
     absl::StrAppend(&ret, EntryDebugString(it), "\n");
   }
   return ret;
 }

 void RangeMap::AddRange(uint64_t addr, uint64_t size, const std::string& val) {
   AddDualRange(addr, size, kNoTranslation, val);
 }

 template <class T>
 void RangeMap::MaybeSetLabel(T iter, const std::string& label, uint64_t addr,
                              uint64_t size) {
   assert(EntryContains(iter, addr));
   if (iter->second.size == kUnknownSize && size != kUnknownSize) {
     assert(addr + size >= addr);
     assert(addr + size >= iter->first);
     assert(addr >= iter->first);
     if (addr == iter->first) {
       T next = std::next(iter);
       uint64_t end = addr + size;
       if (!IterIsEnd(next)) {
         end = std::min(end, next->first);
       }
       uint64_t new_size = end - iter->first;
       if (verbose_level > 2) {
         printf("  updating mapping (%s) with new size %" PRIx64 "\n",
                EntryDebugString(addr, size, UINT64_MAX, label).c_str(),
                new_size);
       }
       // This new defined range encompassess all of the unknown-length range, so
       // just define the range to have our end.
       iter->second.size = new_size;
       CheckConsistency(iter);
     }
   } else if (verbose_level > 2) {
     printf("  skipping existing mapping (%s)\n",
            EntryDebugString(iter).c_str());
   }
 }

 void RangeMap::AddDualRange(uint64_t addr, uint64_t size, uint64_t otheraddr,
                             const std::string& label) {
   if (verbose_level > 2) {
     printf("%p AddDualRange([%" PRIx64 ", %" PRIx64 "], %" PRIx64 ", %s)\n",
            this, addr, size, otheraddr, label.c_str());
   }

   if (size == 0) return;

   auto it = FindContainingOrAfter(addr);

   if (size == kUnknownSize) {
     assert(otheraddr == kNoTranslation);
     if (it != mappings_.end() && EntryContainsStrict(it, addr)) {
       MaybeSetLabel(it, label, addr, kUnknownSize);
     } else {
       auto iter = mappings_.emplace_hint(
           it, std::make_pair(addr, Entry(label, kUnknownSize, kNoTranslation)));
       if (verbose_level > 2) {
         printf("  added entry: %s\n", EntryDebugString(iter).c_str());
       }
     }
     return;
   }

   const uint64_t base = addr;
   uint64_t end = addr + size;
   assert(end >= addr);

   while (1) {
     // Advance past existing entries that intersect this range until we find a
     // gap.
     while (addr < end && !IterIsEnd(it) && EntryContains(it, addr)) {
       assert(end >= addr);
       MaybeSetLabel(it, label, addr, end - addr);
       addr = RangeEndUnknownLimit(it, addr);
       ++it;
     }

     if (addr >= end) {
       return;
     }

     // We found a gap and need to create an entry.  Need to make sure the new
     // entry doesn't extend into a range that was previously defined.
     uint64_t this_end = end;
     if (it != mappings_.end() && end > it->first) {
       assert(it->first >= addr);
       this_end = std::min(end, it->first);
     }

     uint64_t other = (otheraddr == kNoTranslation) ? kNoTranslation
                                                    : addr - base + otheraddr;
     assert(this_end >= addr);
     auto iter = mappings_.emplace_hint(
         it, std::make_pair(addr, Entry(label, this_end - addr, other)));
     if (verbose_level > 2) {
       printf("  added entry: %s\n", EntryDebugString(iter).c_str());
     }
     CheckConsistency(iter);
     addr = this_end;
   }
 }

 // In most cases we don't expect the range we're translating to span mappings
 // in the translator.  For example, we would never expect a symbol to span
 // sections.
 //
 // However there are some examples.  An archive member (in the file domain) can
 // span several section mappings.  If we really wanted to get particular here,
 // we could pass a parameter indicating whether such spanning is expected, and
 // warn if not.
 bool RangeMap::AddRangeWithTranslation(uint64_t addr, uint64_t size,
                                        const std::string& val,
                                        const RangeMap& translator,
                                        bool verbose,
                                        RangeMap* other) {
   auto it = translator.FindContaining(addr);
   uint64_t end;
   if (size == kUnknownSize) {
     end = addr + 1;
   } else {
     end = addr + size;
     assert(end >= addr);
   }
   uint64_t total_size = 0;

   // TODO: optionally warn about when we span ranges of the translator.  In some
   // cases this would be a bug (ie. symbols VM->file).  In other cases it's
   // totally normal (ie. archive members file->VM).
   while (!translator.IterIsEnd(it) && it->first < end) {
     uint64_t translated_addr;
     uint64_t trimmed_addr;
     uint64_t trimmed_size;
     if (translator.TranslateAndTrimRangeWithEntry(
             it, addr, size, &trimmed_addr, &translated_addr, &trimmed_size)) {
       if (verbose_level > 2 || verbose) {
         printf("  -> translates to: [%" PRIx64 " %" PRIx64 "]\n", translated_addr,
                trimmed_size);
       }
       other->AddRange(translated_addr, trimmed_size, val);
     }
     AddRange(trimmed_addr, trimmed_size, val);
     total_size += trimmed_size;
     ++it;
   }

   return total_size == size;
 }

 void RangeMap::Compress() {
   auto prev = mappings_.begin();
   auto it = prev;
   while (it != mappings_.end()) {
     if (prev->first + prev->second.size == it->first &&
         (prev->second.label == it->second.label ||
          (!prev->second.HasFallbackLabel() && it->second.IsShortFallback()))) {
       prev->second.size += it->second.size;
       mappings_.erase(it++);
     } else {
       prev = it;
       ++it;
     }
   }
 }

 bool RangeMap::CoversRange(uint64_t addr, uint64_t size) const {
   auto it = FindContaining(addr);
   uint64_t end = addr + size;
   assert(end >= addr);

   while (true) {
     if (addr >= end) {
       return true;
     } else if (it == mappings_.end() || !EntryContains(it, addr)) {
       return false;
     }
     addr = RangeEnd(it);
     it++;
   }
 }

 uint64_t RangeMap::GetMaxAddress() const {
   if (mappings_.empty()) {
     return 0;
   } else {
     auto& entry = *mappings_.rbegin();
     return entry.first + entry.second.size;
   }
 }

 }  // namespace bloaty
	// 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.

	#include "range_map.h"

	#include "bloaty.h"

	namespace bloaty {

	constexpr uint64_t RangeMap::kUnknownSize;

	template <class T>
	uint64_t RangeMap::TranslateWithEntry(T iter, uint64_t addr) const {
	assert(EntryContains(iter, addr));
	assert(iter->second.HasTranslation());
	return addr - iter->first + iter->second.other_start;
	}

	template <class T>
	bool RangeMap::TranslateAndTrimRangeWithEntry(T iter, uint64_t addr,
	uint64_t size, uint64_t* trimmed_addr,
	uint64_t* translated_addr,
	uint64_t* trimmed_size) const {
	addr = std::max(addr, iter->first);
	*trimmed_addr = addr;

	if (size == kUnknownSize) {
	*trimmed_size = kUnknownSize;
	} else {
	uint64_t end = std::min(addr + size, iter->first + iter->second.size);
	if (addr >= end) {
	*trimmed_size = 0;
	return false;
	}
	*trimmed_size = end - addr;
	}

	if (!iter->second.HasTranslation()) {
	return false;
	}

	*translated_addr = TranslateWithEntry(iter, addr);
	return true;
	}

	RangeMap::Map::const_iterator RangeMap::FindContaining(uint64_t addr) const {
	auto it = mappings_.upper_bound(addr); // Entry directly after.
	if (it == mappings_.begin() \|\| (--it, !EntryContains(it, addr))) {
	return mappings_.end();
	} else {
	return it;
	}
	}

	RangeMap::Map::iterator RangeMap::FindContainingOrAfter(uint64_t addr) {
	auto after = mappings_.upper_bound(addr);
	auto it = after;
	if (it != mappings_.begin() && (--it, EntryContains(it, addr))) {
	return it; // Containing
	} else {
	return after; // May be end().
	}
	}

	RangeMap::Map::const_iterator RangeMap::FindContainingOrAfter(
	uint64_t addr) const {
	auto after = mappings_.upper_bound(addr);
	auto it = after;
	if (it != mappings_.begin() && (--it, EntryContains(it, addr))) {
	return it; // Containing
	} else {
	return after; // May be end().
	}
	}

	bool RangeMap::Translate(uint64_t addr, uint64_t* translated) const {
	auto iter = FindContaining(addr);
	if (iter == mappings_.end() \|\| !iter->second.HasTranslation()) {
	return false;
	} else {
	*translated = TranslateWithEntry(iter, addr);
	return true;
	}
	}

	bool RangeMap::TryGetLabel(uint64_t addr, std::string* label) const {
	auto iter = FindContaining(addr);
	if (iter == mappings_.end()) {
	return false;
	} else {
	*label = iter->second.label;
	return true;
	}
	}

	bool RangeMap::TryGetLabelForRange(uint64_t addr, uint64_t size,
	std::string* label) const {
	uint64_t end = addr + size;
	if (end < addr) {
	return false;
	}
	auto iter = FindContaining(addr);
	if (iter == mappings_.end()) {
	return false;
	} else {
	*label = iter->second.label;
	while (iter != mappings_.end() && iter->first + iter->second.size < end) {
	if (iter->second.label != *label) {
	return false;
	}
	++iter;
	}
	return iter != mappings_.end();
	}
	}

	bool RangeMap::TryGetSize(uint64_t addr, uint64_t* size) const {
	auto iter = mappings_.find(addr);
	if (iter == mappings_.end()) {
	return false;
	} else {
	*size = iter->second.size;
	return true;
	}
	}

	std::string RangeMap::DebugString() const {
	std::string ret;
	for (auto it = mappings_.begin(); it != mappings_.end(); ++it) {
	absl::StrAppend(&ret, EntryDebugString(it), "\n");
	}
	return ret;
	}

	void RangeMap::AddRange(uint64_t addr, uint64_t size, const std::string& val) {
	AddDualRange(addr, size, kNoTranslation, val);
	}

	template <class T>
	void RangeMap::MaybeSetLabel(T iter, const std::string& label, uint64_t addr,
	uint64_t size) {
	assert(EntryContains(iter, addr));
	if (iter->second.size == kUnknownSize && size != kUnknownSize) {
	assert(addr + size >= addr);
	assert(addr + size >= iter->first);
	assert(addr >= iter->first);
	if (addr == iter->first) {
	T next = std::next(iter);
	uint64_t end = addr + size;
	if (!IterIsEnd(next)) {
	end = std::min(end, next->first);
	}
	uint64_t new_size = end - iter->first;
	if (verbose_level > 2) {
	printf(" updating mapping (%s) with new size %" PRIx64 "\n",
	EntryDebugString(addr, size, UINT64_MAX, label).c_str(),
	new_size);
	}
	// This new defined range encompassess all of the unknown-length range, so
	// just define the range to have our end.
	iter->second.size = new_size;
	CheckConsistency(iter);
	}
	} else if (verbose_level > 2) {
	printf(" skipping existing mapping (%s)\n",
	EntryDebugString(iter).c_str());
	}
	}

	void RangeMap::AddDualRange(uint64_t addr, uint64_t size, uint64_t otheraddr,
	const std::string& label) {
	if (verbose_level > 2) {
	printf("%p AddDualRange([%" PRIx64 ", %" PRIx64 "], %" PRIx64 ", %s)\n",
	this, addr, size, otheraddr, label.c_str());
	}

	if (size == 0) return;

	auto it = FindContainingOrAfter(addr);

	if (size == kUnknownSize) {
	assert(otheraddr == kNoTranslation);
	if (it != mappings_.end() && EntryContainsStrict(it, addr)) {
	MaybeSetLabel(it, label, addr, kUnknownSize);
	} else {
	auto iter = mappings_.emplace_hint(
	it, std::make_pair(addr, Entry(label, kUnknownSize, kNoTranslation)));
	if (verbose_level > 2) {
	printf(" added entry: %s\n", EntryDebugString(iter).c_str());
	}
	}
	return;
	}

	const uint64_t base = addr;
	uint64_t end = addr + size;
	assert(end >= addr);

	while (1) {
	// Advance past existing entries that intersect this range until we find a
	// gap.
	while (addr < end && !IterIsEnd(it) && EntryContains(it, addr)) {
	assert(end >= addr);
	MaybeSetLabel(it, label, addr, end - addr);
	addr = RangeEndUnknownLimit(it, addr);
	++it;
	}

	if (addr >= end) {
	return;
	}

	// We found a gap and need to create an entry. Need to make sure the new
	// entry doesn't extend into a range that was previously defined.
	uint64_t this_end = end;
	if (it != mappings_.end() && end > it->first) {
	assert(it->first >= addr);
	this_end = std::min(end, it->first);
	}

	uint64_t other = (otheraddr == kNoTranslation) ? kNoTranslation
	: addr - base + otheraddr;
	assert(this_end >= addr);
	auto iter = mappings_.emplace_hint(
	it, std::make_pair(addr, Entry(label, this_end - addr, other)));
	if (verbose_level > 2) {
	printf(" added entry: %s\n", EntryDebugString(iter).c_str());
	}
	CheckConsistency(iter);
	addr = this_end;
	}
	}

	// In most cases we don't expect the range we're translating to span mappings
	// in the translator. For example, we would never expect a symbol to span
	// sections.
	//
	// However there are some examples. An archive member (in the file domain) can
	// span several section mappings. If we really wanted to get particular here,
	// we could pass a parameter indicating whether such spanning is expected, and
	// warn if not.
	bool RangeMap::AddRangeWithTranslation(uint64_t addr, uint64_t size,
	const std::string& val,
	const RangeMap& translator,
	bool verbose,
	RangeMap* other) {
	auto it = translator.FindContaining(addr);
	uint64_t end;
	if (size == kUnknownSize) {
	end = addr + 1;
	} else {
	end = addr + size;
	assert(end >= addr);
	}
	uint64_t total_size = 0;

	// TODO: optionally warn about when we span ranges of the translator. In some
	// cases this would be a bug (ie. symbols VM->file). In other cases it's
	// totally normal (ie. archive members file->VM).
	while (!translator.IterIsEnd(it) && it->first < end) {
	uint64_t translated_addr;
	uint64_t trimmed_addr;
	uint64_t trimmed_size;
	if (translator.TranslateAndTrimRangeWithEntry(
	it, addr, size, &trimmed_addr, &translated_addr, &trimmed_size)) {
	if (verbose_level > 2 \|\| verbose) {
	printf(" -> translates to: [%" PRIx64 " %" PRIx64 "]\n", translated_addr,
	trimmed_size);
	}
	other->AddRange(translated_addr, trimmed_size, val);
	}
	AddRange(trimmed_addr, trimmed_size, val);
	total_size += trimmed_size;
	++it;
	}

	return total_size == size;
	}

	void RangeMap::Compress() {
	auto prev = mappings_.begin();
	auto it = prev;
	while (it != mappings_.end()) {
	if (prev->first + prev->second.size == it->first &&
	(prev->second.label == it->second.label \|\|
	(!prev->second.HasFallbackLabel() && it->second.IsShortFallback()))) {
	prev->second.size += it->second.size;
	mappings_.erase(it++);
	} else {
	prev = it;
	++it;
	}
	}
	}

	bool RangeMap::CoversRange(uint64_t addr, uint64_t size) const {
	auto it = FindContaining(addr);
	uint64_t end = addr + size;
	assert(end >= addr);

	while (true) {
	if (addr >= end) {
	return true;
	} else if (it == mappings_.end() \|\| !EntryContains(it, addr)) {
	return false;
	}
	addr = RangeEnd(it);
	it++;
	}
	}

	uint64_t RangeMap::GetMaxAddress() const {
	if (mappings_.empty()) {
	return 0;
	} else {
	auto& entry = *mappings_.rbegin();
	return entry.first + entry.second.size;
	}
	}

	} // namespace bloaty