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