Page MenuHomePhabricator

Fix incorrect L1 inferior memory cache flushing
AbandonedPublic

Authored by jarin on Apr 8 2020, 4:38 PM.

Details

Reviewers
labath
Summary

As discussed in https://reviews.llvm.org/D74398, the L1 memory cache flushing is incorrect.

For instance, if the L1 cache contains two chunks (10, 10) and (30, 10) and we call MemoryCache::Flush(25, 10), the current code does not flush anything (because it just tries to flush the previous range (10, 10) and if that is not intersecting, it will bail out).

With this patch, if the previous chunk is not overlapping, we still try the next chunk, and only if that one is not overlapping, we bail out.

This also adds some unit tests for the cache (some of the tests fail with the current code). The unit tests required some changes for testability.

Diff Detail

Unit TestsFailed

TimeTest
420 msLLVM.Transforms/Attributor::Unknown Unit Message ("")
Script: -- : 'RUN: at line 2'; /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/bin/opt -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=7 -S < /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/llvm/test/Transforms/Attributor/liveness.ll | /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/bin/FileCheck /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/llvm/test/Transforms/Attributor/liveness.ll --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM
280 msLLVM.Transforms/Attributor::Unknown Unit Message ("")
Script: -- : 'RUN: at line 2'; /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/bin/opt -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=7 -S < /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/llvm/test/Transforms/Attributor/noalias.ll | /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/bin/FileCheck /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/llvm/test/Transforms/Attributor/noalias.ll --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM
80 msLLVM.Transforms/Attributor/ArgumentPromotion::Unknown Unit Message ("")
Script: -- : 'RUN: at line 2'; /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/bin/opt -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=3 -S < /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/llvm/test/Transforms/Attributor/ArgumentPromotion/fp80.ll | /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/bin/FileCheck /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/llvm/test/Transforms/Attributor/ArgumentPromotion/fp80.ll --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM

Event Timeline

jarin created this revision.Apr 8 2020, 4:38 PM
jarin retitled this revision from Fix incorrect L1 cache flushing to Fix incorrect L1 inferior memory cache flushing.Apr 8 2020, 4:39 PM

I am not a pro at the gtest stuff, but this was very hard to follow and figure out what these tests are doing.

lldb/source/Target/Memory.cpp
23–25

Might be cleaner to add getting the cache line size from the MemoryFromInferiorReader as a second virtual function. This would avoid having to add the extra parameter here and to the clear method.

31

remove "cache_line_size" if we add a new virtual function to MemoryFromInferiorReader

37

Change to:

m_L2_cache_line_byte_size = m_reader.GetCacheLineSize();

if we add virtual function to MemoryFromInferiorReader

65–66

This can just be:

BlockMap::iterator previous = pos - 1;
67–68

name "chunk_range" like in the while loop below for consistency?

lldb/source/Target/Process.cpp
488–491

remove GetMemoryCacheLineSize() if we add virtual method to MemoryFromInferiorReader

612

remove GetMemoryCacheLineSize() if we add virtual method to MemoryFromInferiorReader

1456

remove GetMemoryCacheLineSize() if we add virtual method to MemoryFromInferiorReader

5575

remove GetMemoryCacheLineSize() if we add virtual method to MemoryFromInferiorReader

lldb/unittests/Target/MemoryCacheTest.cpp
33–70

Just inline these to avoid having to have a declaration inside the class and then these functions outside of the class?

35–36

Comment maybe saying something like:

// Fill memory from [0x0 - 0x256) with byte values that match the index. We will use this memory in each test and each test will start with a fresh copy.
76–77

So we are reading 10 bytes, but only verifying the first byte in the 10 bytes we read? Why not verify all of them to be sure it worked with a for loop?

for (int i=0; i<result.size(); ++i) 
  ASSERT_EQ(i+10, result[i]);

or just do manual asserts:

ASSERT_EQ(10, result[0]);
ASSERT_EQ(11, result[1]);
ASSERT_EQ(12, result[2]);
...
82

So with "IncrementAndFlushRange(10, 1);" we are modifying one byte at index 10 by incrementing it right? It isn't clear from the:

ASSERT_EQ(m_memory[10], result[0]);

What we are verifying here. Wouldn't it be simpler to do:

ASSERT_EQ(11, result[0]);

And also verify that all of the other 9 bytes we read were unchanged?

ASSERT_EQ(11, result[1]);
ASSERT_EQ(12, result[2]);
...
93

seems weird to use AddRangeToL1Cache instead of just reading memory from these locations and it makes it less of a real world kind a test if we are mucking with the L1 cache directly. Makes the test a bit harder to follow. Maybe just reading from memory is easier to follow?:

// Read ranges from memory to populate the L1 cache
std::vector<uint8_t> result(10);
for (std::pair<lldb::addr_t, size_t> p : cached)
  ReadByBytes(p.first, p.second);
99–101

I can't tell what these three lines are doing. Very hard to follow

122

Same comment as last test about just reading from memory to populate the cache?

128–130

How do we know this won't try and read any memory? Are we assured that IncrementAndFlushRange won't touch any ranges we are trying to read here?

133–135

What is this checking?

jarin updated this revision to Diff 256207.Apr 9 2020, 12:47 AM
jarin marked 10 inline comments as done.

Addressed some of the reviewer comments.

jarin added a comment.Apr 9 2020, 12:49 AM

I rewrote parts of the test, hopefully making it a bit clearer. Please let me know if this made it better.

lldb/source/Target/Memory.cpp
23–25

That's what I thought originally, but it does not logically belong there - it does not feel like inferior's memory should control cache line sizes. I also like that the extra parameter makes it clear when we reflect changes in the cache line size setting in the cache itself rather than having to guess when the cache might do a callback. I had trouble understanding that part before.

Also, note that Process::GetMemoryCacheLineSize would have to be some ugly forwarder method because the existing GetMemoryCacheLineSize method is in ProcessProperties.

I am happy to put the method there if you insist, but I do not think it is a good idea. I would like to hear Pavel's opinion, too.

65–66

It cannot because map::iterator does not have operator-.

lldb/source/Target/Process.cpp
488–491

Is not calling virtual functions in constructors dangerous? Note that this is going to be called during the construction of process.

lldb/unittests/Target/MemoryCacheTest.cpp
76–77

Ouch, this test does not make sense because we do not put anything into L1. Fixed now.

Changed this to test just one byte.

82

What we really care about is that the value that Read returns is the same as the real one in memory, no? I actually do not really care how the IncrementAndFlushRange method modifies the memory as long as Read returns the correct value.

Nevertheless, I rewrote the code to read just one byte and to assert both the value and the invariant.

93

I am quite confused by this comment. What the test does is precisely what we do in the real world.

As far as I can see, reading from memory does not update L1 cache (only L2). The only way to update L1 is what is done here.

99–101

I agree, this was a mess. Changed to check in a loop.

122

See above.

128–130

Because this test is only called with range that won't flush L1. I merged the test with the test above, hopefully making it clearer.

133–135

This just checks that the read return the real contents of the memory. Changed that to a check in a loop.

labath added a comment.Apr 9 2020, 1:36 AM

Thanks for tackling this. I believe this should be split into two patches: an NFC patch which makes it possible to unit test this code, and then a follow-up patch to fix the actual bug. The first patch can include the general testing infrastructure, and a some tests for the functionality which *is* working at the moment.

lldb/source/Target/Memory.cpp
31

I agree with @jarin that cache_line_size looks out of place on the MemoryFromInferiorReader inferface. Maybe this would look better if Clear is renamed to Reset ?

jarin added a comment.Apr 9 2020, 6:44 AM

As labath@ suggested, I have teased apart the test and the testability refactoring into a separate patch. The patch lives at https://reviews.llvm.org/D77790, could you please take a look?

jarin added a comment.Apr 11 2020, 1:28 AM

Abandoning the patch since we cannot reach agreement on how this should be tested.

jarin abandoned this revision.Apr 11 2020, 1:29 AM