1 : // Copyright 2015 Google Inc. All Rights Reserved.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 :
15 : #include "syzygy/refinery/detectors/lfh_entry_detector.h"
16 :
17 : #include <vector>
18 :
19 : #include "gtest/gtest.h"
20 : #include "syzygy/refinery/unittest_util.h"
21 : #include "syzygy/refinery/detectors/unittest_util.h"
22 :
23 : namespace refinery {
24 :
25 : namespace {
26 :
27 : class LFHEntryDetectorTest : public testing::LFHDetectorTest {
28 : protected:
29 : // TODO(siggi): This code is 32 bit heap specific - amend this for 64 bit
30 : // heap support.
31 E : void ResetTestData(size_t byte_size) {
32 : // Set with 0x80 as that signals "lfh entry" at certain byte positions.
33 E : test_data_.assign(byte_size, 0x80);
34 E : }
35 :
36 E : void WriteSubseg(size_t byte_offset, uintptr_t subseg_code) {
37 E : ASSERT_LT(byte_offset + sizeof(subseg_code), test_data_.size());
38 E : void* dst_addr = &test_data_.at(byte_offset);
39 E : subseg_code ^= (testing::ToAddress(dst_addr) >> 3);
40 :
41 E : ::memcpy(dst_addr, &subseg_code, sizeof(subseg_code));
42 E : }
43 :
44 E : void DetectTestData(LFHEntryDetector::LFHEntryRuns* found_runs) {
45 E : ASSERT_TRUE(found_runs);
46 :
47 E : LFHEntryDetector detector;
48 E : ASSERT_TRUE(detector.Init(repo().get(), bit_source()));
49 E : ASSERT_TRUE(detector.Detect(
50 : AddressRange(testing::ToAddress(&test_data_.at(0)), test_data_.size()),
51 : found_runs));
52 E : }
53 :
54 : private:
55 : std::vector<uint8_t> test_data_;
56 : };
57 :
58 : } // namespace
59 :
60 E : TEST_F(LFHEntryDetectorTest, InitSuccess) {
61 E : LFHEntryDetector detector;
62 :
63 E : ASSERT_TRUE(detector.Init(repo().get(), bit_source()));
64 E : ASSERT_TRUE(detector.entry_type());
65 E : }
66 :
67 E : TEST_F(LFHEntryDetectorTest, FailsOnEmptyTypeRepo) {
68 E : LFHEntryDetector detector;
69 :
70 E : scoped_refptr<TypeRepository> empty_type_repo = new TypeRepository;
71 E : ASSERT_FALSE(detector.Init(empty_type_repo.get(), bit_source()));
72 E : ASSERT_FALSE(detector.entry_type());
73 E : }
74 :
75 E : TEST_F(LFHEntryDetectorTest, Detect) {
76 E : if (testing::IsAppVerifierActive()) {
77 i : LOG(WARNING) << "LFHEntryDetectorTest.Detect is incompatible with AV.";
78 i : return;
79 : }
80 :
81 E : LFHEntryDetector detector;
82 :
83 E : ASSERT_TRUE(detector.Init(repo().get(), bit_source()));
84 :
85 E : const size_t kBlockSize = 17;
86 : // Allocate blocks until we get an LFH bucket.
87 E : Address bucket = AllocateLFHBucket(kBlockSize);
88 E : if (bucket == 0) {
89 i : LOG(ERROR) << "Couldn't find an LFH bucket - is AppVerifier enabled?";
90 i : return;
91 : }
92 :
93 : // Form a range covering the LFH bucket start and perform detection on it.
94 E : AddressRange range(bucket - 256, 1024);
95 E : LFHEntryDetector::LFHEntryRuns found_runs;
96 E : ASSERT_TRUE(detector.Detect(range, &found_runs));
97 :
98 E : ASSERT_LE(1, found_runs.size());
99 :
100 E : bool suitable_size_found = false;
101 E : for (const auto& found_run : found_runs) {
102 E : ASSERT_NE(0U, found_run.entries_found);
103 E : ASSERT_LE(found_run.entry_distance_bytes * (found_run.entries_found - 1),
104 : found_run.last_entry - found_run.first_entry);
105 E : ASSERT_NE(0U, found_run.size_votes);
106 E : ASSERT_GT(found_run.entries_found, found_run.size_votes);
107 :
108 : // Technically it's possible for the subsegment mask to be zero, but this
109 : // at least tests that it's set with a 1/2^32 odds of flaking.
110 E : ASSERT_NE(0ULL, found_run.subsegment_code);
111 :
112 E : const size_t kEntrySize = 8;
113 E : if (found_run.entry_distance_bytes > kBlockSize + kEntrySize)
114 E : suitable_size_found = true;
115 :
116 : AddressRange found_span(found_run.first_entry,
117 E : found_run.last_entry - found_run.first_entry);
118 E : ASSERT_TRUE(found_span.IsValid());
119 : // All found spans should be contained within the range we constrain the
120 : // search to.
121 E : ASSERT_TRUE(range.Contains(found_span));
122 E : }
123 :
124 E : ASSERT_TRUE(suitable_size_found);
125 E : }
126 :
127 E : TEST_F(LFHEntryDetectorTest, VotingPicksMinimumDistance) {
128 : // Make some test data.
129 E : ResetTestData(1024);
130 :
131 E : const uintptr_t kSubsegCode = 0xCAFEBABE;
132 E : WriteSubseg(16 * 1, kSubsegCode);
133 E : WriteSubseg(16 * 2, kSubsegCode);
134 E : WriteSubseg(16 * 4, kSubsegCode);
135 :
136 E : LFHEntryDetector::LFHEntryRuns found_runs;
137 E : ASSERT_NO_FATAL_FAILURE(DetectTestData(&found_runs));
138 :
139 E : ASSERT_EQ(1U, found_runs.size());
140 E : EXPECT_EQ(kSubsegCode, found_runs[0].subsegment_code);
141 : // The smaller size should have been selected.
142 E : EXPECT_EQ(16, found_runs[0].entry_distance_bytes);
143 :
144 E : ResetTestData(1024);
145 :
146 : // Now try starting with the larger span.
147 E : WriteSubseg(16 * 1, kSubsegCode);
148 E : WriteSubseg(16 * 3, kSubsegCode);
149 E : WriteSubseg(16 * 4, kSubsegCode);
150 :
151 E : ASSERT_NO_FATAL_FAILURE(DetectTestData(&found_runs));
152 E : ASSERT_EQ(1U, found_runs.size());
153 E : EXPECT_EQ(kSubsegCode, found_runs[0].subsegment_code);
154 : // The smaller size should have been selected.
155 E : EXPECT_EQ(16, found_runs[0].entry_distance_bytes);
156 E : }
157 :
158 : } // namespace refinery
|