1 : // Copyright 2014 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/agent/asan/quarantines/sharded_quarantine.h"
16 :
17 : #include <set>
18 :
19 : #include "gtest/gtest.h"
20 :
21 : namespace agent {
22 : namespace asan {
23 : namespace quarantines {
24 :
25 : namespace {
26 :
27 : struct DummyObject {
28 : size_t size;
29 : size_t hash;
30 :
31 E : DummyObject() : size(0), hash(0) { }
32 E : explicit DummyObject(size_t size) : size(size), hash(0) { }
33 : DummyObject(const DummyObject& o)
34 : : size(o.size),
35 E : hash(o.hash) {
36 E : }
37 E : DummyObject& operator=(const DummyObject& o) {
38 E : size = o.size;
39 E : hash = o.hash;
40 E : return *this;
41 E : }
42 : };
43 :
44 : struct DummyObjectSizeFunctor {
45 E : size_t operator()(const DummyObject& o) {
46 E : return o.size;
47 E : }
48 : };
49 :
50 : struct DummyObjectHashFunctor {
51 E : uint32 operator()(const DummyObject& o) {
52 E : return o.hash;
53 E : }
54 : };
55 :
56 : typedef std::vector<DummyObject> DummyObjectVector;
57 :
58 : class TestShardedQuarantine
59 : : public ShardedQuarantine<DummyObject,
60 : DummyObjectSizeFunctor,
61 : DummyObjectHashFunctor,
62 : 8> {
63 : public:
64 : typedef ShardedQuarantine<DummyObject,
65 : DummyObjectSizeFunctor,
66 : DummyObjectHashFunctor,
67 : 8> Super;
68 :
69 E : size_t ShardCount(size_t shard) {
70 E : Super::Node* node = heads_[shard];
71 E : size_t count = 0;
72 E : while (node) {
73 E : ++count;
74 E : node = node->next;
75 E : }
76 E : return count;
77 E : }
78 :
79 E : void LockImpl(size_t lock_id) override {
80 E : Super::LockImpl(lock_id);
81 E : lock_set_.insert(lock_id);
82 E : }
83 E : void UnlockImpl(size_t lock_id) override {
84 E : lock_set_.erase(lock_id);
85 E : Super::UnlockImpl(lock_id);
86 E : }
87 :
88 : std::set<size_t> lock_set_;
89 : };
90 :
91 : } // namespace
92 :
93 E : TEST(ShardedQuarantineTest, EvenLoading) {
94 E : TestShardedQuarantine q;
95 E : DummyObject d(1);
96 E : DummyObject popped;
97 :
98 : // No max object size. This logic is tested in SizeLimitedQuarantineImpl.
99 E : q.set_max_object_size(TestShardedQuarantine::kUnboundedSize);
100 E : q.set_max_quarantine_size(10000);
101 :
102 E : EXPECT_EQ(0u, q.size());
103 :
104 : // Stuff a bunch of things into the quarantine, but don't saturate it.
105 E : for (size_t i = 0; i < 9000; ++i) {
106 : {
107 E : TestShardedQuarantine::AutoQuarantineLock lock(&q, d);
108 E : EXPECT_TRUE(q.Push(d));
109 E : }
110 E : d.hash++;
111 E : EXPECT_EQ(i + 1, q.size());
112 :
113 E : EXPECT_FALSE(q.Pop(&popped));
114 E : EXPECT_EQ(i + 1, q.size());
115 E : }
116 :
117 : // Saturate the quarantine, invalidating the invariant.
118 E : while (q.size() <= q.max_quarantine_size()) {
119 : {
120 E : TestShardedQuarantine::AutoQuarantineLock lock(&q, d);
121 E : EXPECT_TRUE(q.Push(d));
122 E : }
123 E : d.hash++;
124 E : }
125 :
126 : // Now expect one element to be popped off before the invariant is satisfied.
127 E : EXPECT_TRUE(q.Pop(&popped));
128 E : EXPECT_EQ(d.size, popped.size);
129 E : EXPECT_EQ(q.max_quarantine_size(), q.size());
130 :
131 : // Expect there to be roughly even loading.
132 E : double expected_count = q.max_quarantine_size() / q.kShardingFactor;
133 E : for (size_t i = 0; i < q.kShardingFactor; ++i) {
134 E : size_t count = q.ShardCount(i);
135 E : EXPECT_LT(0.9 * expected_count, count);
136 E : EXPECT_GT(1.1 * expected_count, count);
137 E : }
138 E : }
139 :
140 E : TEST(ShardedQuarantineTest, StressTest) {
141 E : TestShardedQuarantine q;
142 :
143 : // Doesn't allow the largest of objects we generate.
144 E : q.set_max_object_size((1 << 10) - 1);
145 :
146 : // Is only 4 times as big as the largest element we generate.
147 E : q.set_max_quarantine_size(4 * (1 << 10));
148 :
149 E : for (size_t i = 0; i < 1000000; ++i) {
150 : // Generates a logarithmic distribution of element sizes.
151 E : size_t logsize = (1 << rand() % 11);
152 E : size_t size = (rand() & (logsize - 1)) | logsize;
153 E : DummyObject d(size);
154 :
155 E : size_t old_size = q.size();
156 E : size_t old_count = q.GetCount();
157 E : if (size > q.max_object_size()) {
158 : {
159 E : TestShardedQuarantine::AutoQuarantineLock lock(&q, d);
160 E : EXPECT_FALSE(q.Push(d));
161 E : }
162 E : EXPECT_EQ(old_size, q.size());
163 E : EXPECT_EQ(old_count, q.GetCount());
164 E : } else {
165 : {
166 E : TestShardedQuarantine::AutoQuarantineLock lock(&q, d);
167 E : EXPECT_TRUE(q.Push(d));
168 E : }
169 E : EXPECT_EQ(old_size + size, q.size());
170 E : EXPECT_EQ(old_count + 1, q.GetCount());
171 : }
172 :
173 E : DummyObject popped;
174 E : while (q.size() > q.max_quarantine_size()) {
175 E : old_size = q.size();
176 E : old_count = q.GetCount();
177 E : EXPECT_TRUE(q.Pop(&popped));
178 E : EXPECT_EQ(old_size - popped.size, q.size());
179 E : EXPECT_EQ(old_count - 1, q.GetCount());
180 E : }
181 E : EXPECT_FALSE(q.Pop(&popped));
182 E : }
183 :
184 E : size_t old_size = q.size();
185 E : size_t old_count = q.GetCount();
186 E : TestShardedQuarantine::ObjectVector os;
187 E : q.Empty(&os);
188 E : EXPECT_EQ(0u, q.size());
189 E : EXPECT_EQ(0u, q.GetCount());
190 E : EXPECT_EQ(old_count, os.size());
191 E : size_t emptied_size = 0;
192 E : for (size_t i = 0; i < os.size(); ++i)
193 E : emptied_size += os[i].size;
194 E : EXPECT_EQ(old_size, emptied_size);
195 E : }
196 :
197 E : TEST(ShardedQuarantineTest, LockUnlock) {
198 E : TestShardedQuarantine q;
199 E : DummyObject dummy;
200 E : size_t lock_id = q.GetLockId(dummy);
201 : {
202 E : TestShardedQuarantine::AutoQuarantineLock lock(&q, dummy);
203 :
204 E : EXPECT_TRUE(q.lock_set_.find(lock_id) != q.lock_set_.end());
205 E : }
206 :
207 E : EXPECT_TRUE(q.lock_set_.empty());
208 E : }
209 :
210 : } // namespace quarantines
211 : } // namespace asan
212 : } // namespace agent
|