win: Add memory map range intersection helper

util/win/process_info.cc

 // Copyright 2015 The Crashpad Authors. 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 "util/win/process_info.h"
 
 #include <winternl.h>
 
+#include <algorithm>
+
 #include "base/logging.h"
 #include "base/strings/stringprintf.h"
 #include "build/build_config.h"
 #include "util/numeric/safe_assignment.h"
 #include "util/win/ntstatus_logging.h"
 #include "util/win/process_structs.h"
 
 namespace crashpad {
 
 namespace {
@@ skipping 68 matching lines @@
     PLOG(ERROR) << "ReadProcessMemory " << __FUNCSIG__;
     return false;
   }
   if (bytes_read != sizeof(T)) {
     LOG(ERROR) << "ReadProcessMemory " << __FUNCSIG__ << " incorrect size";
     return false;
   }
   return true;
 }
 
+bool PageIsReadable(const ProcessInfo::MemoryInfo& memory_info) {

[Mark Mentovai, 2015/10/01 17:38:58]

The function name, PageIsReadable(), doesn’t match the implementation, which
actually does the opposite.

[Mark Mentovai, 2015/10/01 17:38:58]

This operates on MemoryInfo objects, which represent contiguous ranges of pages
(RegionIsReadable()?), not on pages proper.

[scottmg, 2015/10/01 18:10:02]

Done.

[scottmg, 2015/10/01 18:10:02]

Done.

+  return memory_info.state == MEM_FREE ||
+         (memory_info.state == MEM_COMMIT &&
+          ((memory_info.protect & PAGE_NOACCESS) ||
+           (memory_info.protect & PAGE_GUARD)));
+}
+
 }  // namespace
 
 template <class Traits>
 bool GetProcessBasicInformation(HANDLE process,
                                 bool is_wow64,
                                 ProcessInfo* process_info,
                                 WinVMAddress* peb_address,
                                 WinVMSize* peb_size) {
   ULONG bytes_returned;
   process_types::PROCESS_BASIC_INFORMATION<Traits> process_basic_information;
@@ skipping 168 matching lines @@
 
   return true;
 }
 
 ProcessInfo::Module::Module() : name(), dll_base(0), size(0), timestamp() {
 }
 
 ProcessInfo::Module::~Module() {
 }
 
+ProcessInfo::MemoryInfo::MemoryInfo()
+    : base_address(0),
+      region_size(0),
+      allocation_base(0),
+      state(0),
+      allocation_protect(0),
+      protect(0),
+      type(0) {
+}
+
 ProcessInfo::MemoryInfo::MemoryInfo(const MEMORY_BASIC_INFORMATION& mbi)
     : base_address(reinterpret_cast<WinVMAddress>(mbi.BaseAddress)),
       region_size(mbi.RegionSize),
       allocation_base(reinterpret_cast<WinVMAddress>(mbi.AllocationBase)),
       state(mbi.State),
       allocation_protect(mbi.AllocationProtect),
       protect(mbi.Protect),
       type(mbi.Type) {
 }
 
@@ skipping 103 matching lines @@
 }
 
 bool ProcessInfo::Modules(std::vector<Module>* modules) const {
   INITIALIZATION_STATE_DCHECK_VALID(initialized_);
   *modules = modules_;
   return true;
 }
 
 const std::vector<ProcessInfo::MemoryInfo>& ProcessInfo::MemoryInformation()
     const {
+  INITIALIZATION_STATE_DCHECK_VALID(initialized_);
   return memory_info_;
 }
 
+std::vector<CheckedRange<WinVMAddress, WinVMSize>>
+ProcessInfo::GetReadableRanges(
+    const CheckedRange<WinVMAddress, WinVMSize>& range) const {
+  return GetReadableRangesOfMemoryMap(range, MemoryInformation());
+}
+
+std::vector<CheckedRange<WinVMAddress, WinVMSize>> GetReadableRangesOfMemoryMap(
+    const CheckedRange<WinVMAddress, WinVMSize>& range,
+    const std::vector<ProcessInfo::MemoryInfo>& memory_info) {
+  using Range = CheckedRange<WinVMAddress, WinVMSize>;
+
+  // Find all the ranges that overlap the target range, maintaining their order.
+  std::vector<ProcessInfo::MemoryInfo> overlapping;
+  for (const auto& mi : memory_info) {
+    if (range.OverlapsRange(Range(mi.base_address, mi.region_size)))
+      overlapping.push_back(mi);
+  }
+  if (overlapping.empty())
+    return std::vector<Range>();
+
+  // For the first and last, trim to the boundary of the incoming range.
+  ProcessInfo::MemoryInfo& front = overlapping.front();
+  WinVMAddress original_base = front.base_address;

[Mark Mentovai, 2015/10/01 17:38:58]

Since there are several ranges in play here, this will be easier to follow if
it’s original_front_base_address.

[scottmg, 2015/10/01 18:10:02]

Done.

+  front.base_address = range.base();

[Mark Mentovai, 2015/10/01 17:38:59]

Since this requires that front.base_address <= range.base() and you’re relying
on that being true because you’re not expecting the memory to be sparse, you
should have a DCHECK on the assumption. But if there’s any possibility that the
map might be sparse (you mentioned something about not having the full 2^32
represented), perhaps this should be std::max(front.base_address, range.base())

[scottmg, 2015/10/01 18:10:02]

Good catch. Done and added test.

+  front.region_size = (original_base + front.region_size) - range.base();

[Mark Mentovai, 2015/10/01 17:38:58]

and then this one will need to become - front.base_address.

[scottmg, 2015/10/01 18:10:02]

Done.

+
+  ProcessInfo::MemoryInfo& back = overlapping.back();
+  back.region_size = range.end() - back.base_address;

[Mark Mentovai, 2015/10/01 17:38:58]

The same kind of problem might show up here if the map might be sparse or
otherwise not capture all of the 2^32/2^64 address space.

[scottmg, 2015/10/01 18:10:02]

Done and added test.

+
+  // Discard all non-accessible.
+  overlapping.erase(std::remove_if(overlapping.begin(),
+                                   overlapping.end(),
+                                   [](const ProcessInfo::MemoryInfo& mi) {
+                                     return PageIsReadable(mi);
+                                   }),
+                    overlapping.end());
+  if (overlapping.empty())
+    return std::vector<Range>();
+
+  // Convert to return type.
+  std::vector<Range> as_ranges;
+  for (const auto& mi : overlapping) {
+    as_ranges.push_back(Range(mi.base_address, mi.region_size));
+    DCHECK(as_ranges.back().IsValid());
+  }
+
+  // Coalesce remaining regions.
+  std::vector<Range> result;
+  result.push_back(as_ranges[0]);
+  for (size_t i = 1; i < as_ranges.size(); ++i) {
+    if (result.back().end() == as_ranges[i].base()) {
+      result.back().SetRange(result.back().base(),
+                             result.back().size() + as_ranges[i].size());
+    } else {
+      result.push_back(as_ranges[i]);
+    }
+    DCHECK(result.back().IsValid());
+  }
+
+  return result;
+}
+
 }  // namespace crashpad