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/circular_queue.h"
16 :
17 : #include "gmock/gmock.h"
18 : #include "gtest/gtest.h"
19 : #include "syzygy/agent/asan/allocators.h"
20 : #include "syzygy/agent/asan/unittest_util.h"
21 :
22 : namespace agent {
23 : namespace asan {
24 :
25 : namespace {
26 : using testing::MockMemoryNotifier;
27 :
28 : using ::testing::_;
29 : using ::testing::AtLeast;
30 : }
31 :
32 E : TEST(CircularQueue, MaxCapacity) {
33 E : size_t capacity = 100;
34 E : CircularQueue<int> q(capacity);
35 E : EXPECT_EQ(capacity, q.max_capacity());
36 E : }
37 :
38 E : TEST(CircularQueue, PushIncreasesSize) {
39 E : size_t capacity = 100;
40 E : CircularQueue<int> q(capacity);
41 :
42 E : for (size_t i = 0; i < capacity; ++i) {
43 E : EXPECT_EQ(i, q.size());
44 E : q.push(i);
45 E : EXPECT_EQ(i + 1, q.size());
46 E : }
47 E : }
48 :
49 E : TEST(CircularQueue, PopDecreasesSize) {
50 E : size_t capacity = 100;
51 E : CircularQueue<int> q(capacity);
52 :
53 E : for (size_t i = 0; i < capacity; ++i) {
54 E : for (size_t j = 0; j < i; ++j)
55 E : q.push(i);
56 E : for (size_t j = 0; j < i; ++j) {
57 E : EXPECT_EQ(i - j, q.size());
58 E : q.pop();
59 E : EXPECT_EQ(i - j - 1, q.size());
60 E : }
61 E : }
62 E : }
63 :
64 E : TEST(CircularQueue, ComplyWithLIFO) {
65 E : size_t capacity = 100;
66 E : CircularQueue<int> q(capacity);
67 :
68 E : size_t initial = 10;
69 E : for (size_t i = 0; i < initial; ++i)
70 E : EXPECT_TRUE(q.push(i));
71 :
72 E : for (size_t i = initial; i < 1000 * capacity; ++i) {
73 E : EXPECT_TRUE(q.push(i));
74 E : EXPECT_EQ(i - initial, q.front());
75 E : EXPECT_TRUE(q.pop());
76 E : }
77 E : }
78 :
79 E : TEST(CircularQueue, Stress) {
80 E : size_t capacity = 100;
81 E : CircularQueue<int> q(capacity);
82 E : EXPECT_TRUE(q.empty());
83 :
84 E : for (size_t i = 0; i < capacity; ++i) {
85 E : for (size_t j = 0; j < i; ++j) {
86 E : EXPECT_TRUE(q.push(i));
87 E : EXPECT_FALSE(q.empty());
88 E : }
89 E : for (size_t j = 0; j < i; ++j) {
90 E : EXPECT_FALSE(q.empty());
91 E : EXPECT_TRUE(q.pop());
92 E : }
93 E : EXPECT_TRUE(q.empty());
94 E : }
95 E : EXPECT_TRUE(q.empty());
96 E : }
97 :
98 E : TEST(CircularQueue, PushWhenFull) {
99 E : size_t capacity = 100;
100 E : CircularQueue<int> q(capacity);
101 E : EXPECT_TRUE(q.empty());
102 :
103 E : for (size_t i = 0; i < capacity; ++i) {
104 E : EXPECT_TRUE(q.push(i));
105 E : EXPECT_FALSE(q.empty());
106 E : }
107 :
108 E : EXPECT_EQ(capacity, q.size());
109 :
110 E : EXPECT_FALSE(q.push(1));
111 E : EXPECT_FALSE(q.push(2));
112 E : EXPECT_FALSE(q.push(3));
113 :
114 E : EXPECT_EQ(capacity, q.size());
115 E : }
116 :
117 E : TEST(CircularQueue, PopWhenEmpty) {
118 E : size_t capacity = 100;
119 E : CircularQueue<int> q(capacity);
120 E : EXPECT_FALSE(q.pop());
121 E : EXPECT_TRUE(q.push(0));
122 E : EXPECT_TRUE(q.pop());
123 E : EXPECT_TRUE(q.empty());
124 E : }
125 :
126 E : TEST(CircularQueue, PopUntilEmpty) {
127 E : size_t capacity = 100;
128 E : CircularQueue<int> q(capacity);
129 :
130 E : for (size_t i = 0; i < capacity; ++i) {
131 E : EXPECT_TRUE(q.push(i));
132 E : EXPECT_FALSE(q.empty());
133 E : }
134 :
135 E : while (q.pop()) { }
136 E : EXPECT_TRUE(q.empty());
137 E : EXPECT_EQ(0u, q.size());
138 E : }
139 :
140 E : TEST(CircularQueue, EmptyAndZeroSize) {
141 E : size_t capacity = 100;
142 E : CircularQueue<int> q(capacity);
143 :
144 E : EXPECT_TRUE(q.empty());
145 E : EXPECT_EQ(0u, q.size());
146 :
147 E : EXPECT_TRUE(q.push(1));
148 E : EXPECT_TRUE(q.pop());
149 :
150 E : EXPECT_TRUE(q.empty());
151 E : EXPECT_EQ(0u, q.size());
152 E : }
153 :
154 E : TEST(CircularQueue, MemoryNotifierIsCalled) {
155 E : MockMemoryNotifier mock_notifier;
156 :
157 : // Should be called by the underlying container.
158 : EXPECT_CALL(mock_notifier,
159 : NotifyInternalUse(_, _))
160 E : .Times(AtLeast(1));
161 :
162 : // Ensure no calls to NotifyFutureHeapUse.
163 : EXPECT_CALL(mock_notifier,
164 : NotifyFutureHeapUse(_, _))
165 E : .Times(0);
166 :
167 : // Should be called by the underlying container.
168 : EXPECT_CALL(mock_notifier,
169 : NotifyReturnedToOS(_, _))
170 E : .Times(AtLeast(1));
171 :
172 E : size_t capacity = 100000;
173 : CircularQueue<int, MemoryNotifierAllocator<int>> q(
174 : capacity,
175 E : MemoryNotifierAllocator<int>(&mock_notifier));
176 E : }
177 :
178 :
179 : } // namespace asan
180 : } // namespace agent
|