win: Add memory map range intersection helper

win: Add memory map range intersection helper

To be used for improved version of ReadMemory() that is memory-map
aware, in particular for reading the environment block in
https://codereview.chromium.org/1360863006/.

R=mark@chromium.org
BUG=crashpad:20, crashpad:46
Committed: https://chromium.googlesource.com/crashpad/crashpad/+/4df538f283d36f4984592236a6174af1641b75de

[Mark Mentovai, 2015-09-29 21:35:50]

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.cc
File util/win/process_info.cc (right):

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.c...
util/win/process_info.cc:445: if (mi.base_address + mi.region_size <= address)
Optional, but since you’re using CheckedRange in here, it’s not unreasonable to
add a (tested) OverlapsRange method to that class and use it here.

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.c...
util/win/process_info.cc:457: if (front.base_address < address) {
Everything should be valid without this if, and without the one at line 464.

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.c...
util/win/process_info.cc:469:
overlapping.erase(std::remove_if(overlapping.begin(),
I like seeing the standard library being used so nicely!

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.c...
util/win/process_info.cc:482: as_ranges.push_back(Range(mi.base_address,
mi.region_size));
You’re not actually using any of the checking features of CheckedRange.
Intentional? Put a comment at the “using” if so.

Since these numbers come from the OS and ought to be trustworthy, you can also
do some debug-mode DCHECK(range.IsValid()) to take advantage of the checking
features.

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h
File util/win/process_info.h (right):

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h...
util/win/process_info.h:162: //! \brief Given a process memory map, gets a set
of regions that correspond to
“set” is slightly confusing when this returns a vector and there’s also
std::set.

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h...
util/win/process_info.h:168: //!     ProcessInfo::MemoryInformation().
Since you mention MemoryInformation() and otherwise discuss the memory map, you
should also discuss coalescing.

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h...
util/win/process_info.h:170: //! \return A list of ranges corresponding to the
portion of the range
If the first mapping starts lower than address, will its base address be
adjusted upwards (and size adjusted downwards) to start at the address specified
by the user? If the last mapping ends higher than address + size, will its size
be adjusted downwards?

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h...
util/win/process_info.h:173: std::vector<CheckedRange<WinVMAddress, WinVMSize>>
I’m definitely cool with CheckedRange in the implementation, but I’m not so sure
about using it for the return value, especially when you haven’t really used
much of the range features or checked features of it. Maybe you’d be better off
with a simple std::pair<>. I can probably be talked into/out of however you want
to handle this, though.

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h...
util/win/process_info.h:174: GetAccessibleRangesInMemoryMap(
Accessible → Readable? Based on the documentation above, I’d expect “readable”,
but based on the implementation, not so much.

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h...
util/win/process_info.h:177: const std::vector<ProcessInfo::MemoryInfo>&
memory_info);
It’s quirky for this to be a loose function that takes a vector<MemoryInfo>
instead of being a member of ProcessInfo that can get the memory map itself. I
can see that you probably did that for testability, but outside of testing, I
don’t know if that’s a great design. (As always, speak up if you had other
reasons.)

An alternative that still keeps the flexibility for testing would be to make
this a nonstatic method that’s backed by either
 - a private static helper using FRIEND_TEST (but that probably won’t work in
our configuration)
 - this function, advertising why it’s exposed in its documentation, and
advising the use of the member function instead

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info_t...
File util/win/process_info_test.cc (right):

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info_t...
util/win/process_info_test.cc:214: EXPECT_EQ(0u, result.size());
For the zeroes, EXPECT_TRUE(result.empty()) reads more clearly.

[Mark Mentovai, 2015-09-29 21:41:17]

Do you need or want to deal with PAGE_NOACCESS in this too?

[scottmg, 2015-09-30 17:40:26]

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.cc
File util/win/process_info.cc (right):

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.c...
util/win/process_info.cc:445: if (mi.base_address + mi.region_size <= address)
On 2015/09/29 21:35:50, Mark Mentovai - August is over wrote:
> Optional, but since you’re using CheckedRange in here, it’s not unreasonable
to
> add a (tested) OverlapsRange method to that class and use it here.

Done. (Sadly std::copy_if is more unwieldy than a plain loop.)

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.c...
util/win/process_info.cc:457: if (front.base_address < address) {
On 2015/09/29 21:35:50, Mark Mentovai - August is over wrote:
> Everything should be valid without this if, and without the one at line 464.

Done.

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.c...
util/win/process_info.cc:482: as_ranges.push_back(Range(mi.base_address,
mi.region_size));
On 2015/09/29 21:35:50, Mark Mentovai - August is over wrote:
> You’re not actually using any of the checking features of CheckedRange.
> Intentional? Put a comment at the “using” if so.
> 
> Since these numbers come from the OS and ought to be trustworthy, you can also
> do some debug-mode DCHECK(range.IsValid()) to take advantage of the checking
> features.

Yeah, it was just a handy representation of a range. But added a few DCHECKs.

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h
File util/win/process_info.h (right):

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h...
util/win/process_info.h:162: //! \brief Given a process memory map, gets a set
of regions that correspond to
On 2015/09/29 21:35:50, Mark Mentovai - August is over wrote:
> “set” is slightly confusing when this returns a vector and there’s also
> std::set.

Done.

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h...
util/win/process_info.h:168: //!     ProcessInfo::MemoryInformation().
On 2015/09/29 21:35:50, Mark Mentovai - August is over wrote:
> Since you mention MemoryInformation() and otherwise discuss the memory map,
you
> should also discuss coalescing.

After renaming the function, I tried to rephrase the description so that it
makes it clear that it's retrieving the parts of the target process's memory
that are part of the input range, so that they'd be expected to be coalesced.

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h...
util/win/process_info.h:170: //! \return A list of ranges corresponding to the
portion of the range
On 2015/09/29 21:35:50, Mark Mentovai - August is over wrote:
> If the first mapping starts lower than address, will its base address be
> adjusted upwards (and size adjusted downwards) to start at the address
specified
> by the user? If the last mapping ends higher than address + size, will its
size
> be adjusted downwards?

I think this is addressed by the rename/description too.

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h...
util/win/process_info.h:173: std::vector<CheckedRange<WinVMAddress, WinVMSize>>
On 2015/09/29 21:35:50, Mark Mentovai - August is over wrote:
> I’m definitely cool with CheckedRange in the implementation, but I’m not so
sure
> about using it for the return value, especially when you haven’t really used
> much of the range features or checked features of it. Maybe you’d be better
off
> with a simple std::pair<>. I can probably be talked into/out of however you
want
> to handle this, though.

The main reason is that I don't like pair.first/.second in the receiving code. I
could make another (unchecked) Range, but there doesn't seem to be much upside?

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h...
util/win/process_info.h:174: GetAccessibleRangesInMemoryMap(
On 2015/09/29 21:35:50, Mark Mentovai - August is over wrote:
> Accessible → Readable? Based on the documentation above, I’d expect
“readable”,
> but based on the implementation, not so much.

Renamed.

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h...
util/win/process_info.h:177: const std::vector<ProcessInfo::MemoryInfo>&
memory_info);
On 2015/09/29 21:35:50, Mark Mentovai - August is over wrote:
> It’s quirky for this to be a loose function that takes a vector<MemoryInfo>
> instead of being a member of ProcessInfo that can get the memory map itself. I
> can see that you probably did that for testability, but outside of testing, I
> don’t know if that’s a great design. (As always, speak up if you had other
> reasons.)
> 
> An alternative that still keeps the flexibility for testing would be to make
> this a nonstatic method that’s backed by either
>  - a private static helper using FRIEND_TEST (but that probably won’t work in
> our configuration)
>  - this function, advertising why it’s exposed in its documentation, and
> advising the use of the member function instead

Yes, it was primarily for testing. Added a member and noted that it should be
preferred.

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info_t...
File util/win/process_info_test.cc (right):

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info_t...
util/win/process_info_test.cc:214: EXPECT_EQ(0u, result.size());
On 2015/09/29 21:35:50, Mark Mentovai - August is over wrote:
> For the zeroes, EXPECT_TRUE(result.empty()) reads more clearly.

Done.

[scottmg, 2015-09-30 17:41:13]

On 2015/09/29 21:41:17, Mark Mentovai - August is over wrote:
> Do you need or want to deal with PAGE_NOACCESS in this too?

Checks for PAGE_NOACCESS or PAGE_GUARD now. I confirmed that despite the name
PAGE_EXECUTE is also readable.

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

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h
File util/win/process_info.h (right):

https://codereview.chromium.org/1372183002/diff/20001/util/win/process_info.h...
util/win/process_info.h:173: std::vector<CheckedRange<WinVMAddress, WinVMSize>>
scottmg wrote:
> The main reason is that I don't like pair.first/.second in the receiving code.
I
> could make another (unchecked) Range, but there doesn't seem to be much
upside?

It’s OK, now that you’re using the checking features of CheckedRange, it makes
more sense.

https://codereview.chromium.org/1372183002/diff/60001/util/numeric/checked_ra...
File util/numeric/checked_range.h (right):

https://codereview.chromium.org/1372183002/diff/60001/util/numeric/checked_ra...
util/numeric/checked_range.h:114: //! Ranges are considered to be open-closed
[base, end) for this test.
Isn’t that closed-open?

https://codereview.chromium.org/1372183002/diff/60001/util/numeric/checked_ra...
File util/numeric/checked_range_test.cc (right):

https://codereview.chromium.org/1372183002/diff/60001/util/numeric/checked_ra...
util/numeric/checked_range_test.cc:253: bool valid;
This is more “overlaps” than valid. The member names for the ContainsValue and
ContainsRange tests should also be updated to “contains”.

https://codereview.chromium.org/1372183002/diff/60001/util/numeric/checked_ra...
util/numeric/checked_range_test.cc:266: {0x2800, 0, true},
This one might be a little weird. Should a 0-sized range be treated as
overlapping anything? It matches what ContainsRange() does, but now I’m
second-guessing that too.

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.cc
File util/win/process_info.cc (right):

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.c...
util/win/process_info.cc:109: bool PageIsReadable(const ProcessInfo::MemoryInfo&
memory_info) {
This operates on MemoryInfo objects, which represent contiguous ranges of pages
(RegionIsReadable()?), not on pages proper.

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.c...
util/win/process_info.cc:109: bool PageIsReadable(const ProcessInfo::MemoryInfo&
memory_info) {
The function name, PageIsReadable(), doesn’t match the implementation, which
actually does the opposite.

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.c...
util/win/process_info.cc:463: WinVMAddress original_base = front.base_address;
Since there are several ranges in play here, this will be easier to follow if
it’s original_front_base_address.

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.c...
util/win/process_info.cc:464: front.base_address = range.base();
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())

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.c...
util/win/process_info.cc:465: front.region_size = (original_base +
front.region_size) - range.base();
and then this one will need to become - front.base_address.

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.c...
util/win/process_info.cc:468: back.region_size = range.end() -
back.base_address;
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.

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.h
File util/win/process_info.h (right):

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.h...
util/win/process_info.h:56: MemoryInfo();
We killed this in
https://codereview.chromium.org/1369833002/diff/60001/util/win/process_info.h....
Since it’s only used in the test, maybe it’d be better to debloat by not having
this and instead moving the bloat to the test by building MemoryInfo objects
from MEMORY_BASIC_INFORMATION.

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.h...
util/win/process_info.h:179: //! \sa ProcessInfo::GetReadableRanges()
I don’t think you need to say \sa when you just gave the name of the alternative
in full above.

[scottmg, 2015-10-01 18:10:03]

Thanks!

https://codereview.chromium.org/1372183002/diff/60001/util/numeric/checked_ra...
File util/numeric/checked_range.h (right):

https://codereview.chromium.org/1372183002/diff/60001/util/numeric/checked_ra...
util/numeric/checked_range.h:114: //! Ranges are considered to be open-closed
[base, end) for this test.
On 2015/10/01 17:38:58, Mark Mentovai wrote:
> Isn’t that closed-open?

Oops, done.

https://codereview.chromium.org/1372183002/diff/60001/util/numeric/checked_ra...
File util/numeric/checked_range_test.cc (right):

https://codereview.chromium.org/1372183002/diff/60001/util/numeric/checked_ra...
util/numeric/checked_range_test.cc:253: bool valid;
On 2015/10/01 17:38:58, Mark Mentovai wrote:
> This is more “overlaps” than valid. The member names for the ContainsValue and
> ContainsRange tests should also be updated to “contains”.

Done.

https://codereview.chromium.org/1372183002/diff/60001/util/numeric/checked_ra...
util/numeric/checked_range_test.cc:266: {0x2800, 0, true},
On 2015/10/01 17:38:58, Mark Mentovai wrote:
> This one might be a little weird. Should a 0-sized range be treated as
> overlapping anything? It matches what ContainsRange() does, but now I’m
> second-guessing that too.

Yeah, the other weird case is <0x2000, 0> = false which is also odd when
compared with this one.

Maybe the most sane thing is that 0-length ranges never overlap anything?

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.cc
File util/win/process_info.cc (right):

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.c...
util/win/process_info.cc:109: bool PageIsReadable(const ProcessInfo::MemoryInfo&
memory_info) {
On 2015/10/01 17:38:58, Mark Mentovai wrote:
> The function name, PageIsReadable(), doesn’t match the implementation, which
> actually does the opposite.

Done.

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.c...
util/win/process_info.cc:109: bool PageIsReadable(const ProcessInfo::MemoryInfo&
memory_info) {
On 2015/10/01 17:38:58, Mark Mentovai wrote:
> This operates on MemoryInfo objects, which represent contiguous ranges of
pages
> (RegionIsReadable()?), not on pages proper.

Done.

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.c...
util/win/process_info.cc:463: WinVMAddress original_base = front.base_address;
On 2015/10/01 17:38:58, Mark Mentovai wrote:
> Since there are several ranges in play here, this will be easier to follow if
> it’s original_front_base_address.

Done.

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.c...
util/win/process_info.cc:464: front.base_address = range.base();
On 2015/10/01 17:38:59, Mark Mentovai wrote:
> 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())

Good catch. Done and added test.

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.c...
util/win/process_info.cc:465: front.region_size = (original_base +
front.region_size) - range.base();
On 2015/10/01 17:38:58, Mark Mentovai wrote:
> and then this one will need to become - front.base_address.

Done.

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.c...
util/win/process_info.cc:468: back.region_size = range.end() -
back.base_address;
On 2015/10/01 17:38:58, Mark Mentovai wrote:
> 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.

Done and added test.

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.h
File util/win/process_info.h (right):

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.h...
util/win/process_info.h:56: MemoryInfo();
On 2015/10/01 17:38:59, Mark Mentovai wrote:
> We killed this in
>
https://codereview.chromium.org/1369833002/diff/60001/util/win/process_info.h....
> Since it’s only used in the test, maybe it’d be better to debloat by not
having
> this and instead moving the bloat to the test by building MemoryInfo objects
> from MEMORY_BASIC_INFORMATION.

Done.

https://codereview.chromium.org/1372183002/diff/60001/util/win/process_info.h...
util/win/process_info.h:179: //! \sa ProcessInfo::GetReadableRanges()
On 2015/10/01 17:38:59, Mark Mentovai wrote:
> I don’t think you need to say \sa when you just gave the name of the
alternative
> in full above.

Done.

[Mark Mentovai, 2015-10-01 18:29:12]

LGTM

https://codereview.chromium.org/1372183002/diff/60001/util/numeric/checked_ra...
File util/numeric/checked_range_test.cc (right):

https://codereview.chromium.org/1372183002/diff/60001/util/numeric/checked_ra...
util/numeric/checked_range_test.cc:266: {0x2800, 0, true},
scottmg wrote:
> On 2015/10/01 17:38:58, Mark Mentovai wrote:
> > This one might be a little weird. Should a 0-sized range be treated as
> > overlapping anything? It matches what ContainsRange() does, but now I’m
> > second-guessing that too.
> 
> Yeah, the other weird case is <0x2000, 0> = false which is also odd when
> compared with this one.
> 
> Maybe the most sane thing is that 0-length ranges never overlap anything?

That works for me. The “contains” case is more of an academic stumper than this
(do you have any thoughts?) but the new “overlaps” looks great now.

https://codereview.chromium.org/1372183002/diff/80001/util/win/process_info.h
File util/win/process_info.h (right):

https://codereview.chromium.org/1372183002/diff/80001/util/win/process_info.h...
util/win/process_info.h:138: //! \return A vector of ranges corresponding to the
portion of the range
“Trains, trains, trains. I like trains!”

That’s one of Avery’s favorite books, and this reminds me of that. “Ranges,
ranges, ranges. I like ranges!”

We can get rid of one of the occurrences by making this “corresponding to the
portion of \a range that is readable”.

https://codereview.chromium.org/1372183002/diff/80001/util/win/process_info_t...
File util/win/process_info_test.cc (right):

https://codereview.chromium.org/1372183002/diff/80001/util/win/process_info_t...
util/win/process_info_test.cc:340: TEST(ProcessInfo, RequestedBeforeMap) {
Awesome.

[scottmg, 2015-10-01 18:43:44]

https://codereview.chromium.org/1372183002/diff/80001/util/win/process_info.h
File util/win/process_info.h (right):

https://codereview.chromium.org/1372183002/diff/80001/util/win/process_info.h...
util/win/process_info.h:138: //! \return A vector of ranges corresponding to the
portion of the range
On 2015/10/01 18:29:12, Mark Mentovai wrote:
> “Trains, trains, trains. I like trains!”
> 
> That’s one of Avery’s favorite books, and this reminds me of that. “Ranges,
> ranges, ranges. I like ranges!”
> 
> We can get rid of one of the occurrences by making this “corresponding to the
> portion of \a range that is readable”.

:-) Roger, Roger.

[scottmg, 2015-10-01 18:47:38]

Committed patchset #6 (id:100001) manually as
4df538f283d36f4984592236a6174af1641b75de (presubmit successful).