1 /*
2 *
3 * Copyright 2015 gRPC authors.
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 *
17 */
18
19 #include "src/core/lib/iomgr/port.h"
20
21 #include "src/core/lib/iomgr/timer_heap.h"
22
23 #include <stdlib.h>
24 #include <string.h>
25
26 #include <grpc/support/alloc.h>
27 #include <grpc/support/log.h>
28
29 #include "src/core/lib/gpr/useful.h"
30 #include "test/core/util/test_config.h"
31
random_deadline(void)32 static gpr_atm random_deadline(void) { return rand(); }
33
create_test_elements(size_t num_elements)34 static grpc_timer* create_test_elements(size_t num_elements) {
35 grpc_timer* elems =
36 static_cast<grpc_timer*>(gpr_malloc(num_elements * sizeof(grpc_timer)));
37 size_t i;
38 for (i = 0; i < num_elements; i++) {
39 elems[i].deadline = random_deadline();
40 }
41 return elems;
42 }
43
contains(grpc_timer_heap * pq,grpc_timer * el)44 static int contains(grpc_timer_heap* pq, grpc_timer* el) {
45 size_t i;
46 for (i = 0; i < pq->timer_count; i++) {
47 if (pq->timers[i] == el) return 1;
48 }
49 return 0;
50 }
51
check_valid(grpc_timer_heap * pq)52 static void check_valid(grpc_timer_heap* pq) {
53 size_t i;
54 for (i = 0; i < pq->timer_count; ++i) {
55 size_t left_child = 1u + 2u * i;
56 size_t right_child = left_child + 1u;
57 if (left_child < pq->timer_count) {
58 GPR_ASSERT(pq->timers[i]->deadline <= pq->timers[left_child]->deadline);
59 }
60 if (right_child < pq->timer_count) {
61 GPR_ASSERT(pq->timers[i]->deadline <= pq->timers[right_child]->deadline);
62 }
63 }
64 }
65
66 /*******************************************************************************
67 * test1
68 */
69
test1(void)70 static void test1(void) {
71 grpc_timer_heap pq;
72 const size_t num_test_elements = 200;
73 const size_t num_test_operations = 10000;
74 size_t i;
75 grpc_timer* test_elements = create_test_elements(num_test_elements);
76 uint8_t* inpq = static_cast<uint8_t*>(gpr_malloc(num_test_elements));
77
78 gpr_log(GPR_INFO, "test1");
79
80 grpc_timer_heap_init(&pq);
81 memset(inpq, 0, num_test_elements);
82 GPR_ASSERT(grpc_timer_heap_is_empty(&pq));
83 check_valid(&pq);
84 for (i = 0; i < num_test_elements; ++i) {
85 GPR_ASSERT(!contains(&pq, &test_elements[i]));
86 grpc_timer_heap_add(&pq, &test_elements[i]);
87 check_valid(&pq);
88 GPR_ASSERT(contains(&pq, &test_elements[i]));
89 inpq[i] = 1;
90 }
91 for (i = 0; i < num_test_elements; ++i) {
92 /* Test that check still succeeds even for element that wasn't just
93 inserted. */
94 GPR_ASSERT(contains(&pq, &test_elements[i]));
95 }
96
97 GPR_ASSERT(pq.timer_count == num_test_elements);
98
99 check_valid(&pq);
100
101 for (i = 0; i < num_test_operations; ++i) {
102 size_t elem_num = static_cast<size_t>(rand()) % num_test_elements;
103 grpc_timer* el = &test_elements[elem_num];
104 if (!inpq[elem_num]) { /* not in pq */
105 GPR_ASSERT(!contains(&pq, el));
106 el->deadline = random_deadline();
107 grpc_timer_heap_add(&pq, el);
108 GPR_ASSERT(contains(&pq, el));
109 inpq[elem_num] = 1;
110 check_valid(&pq);
111 } else {
112 GPR_ASSERT(contains(&pq, el));
113 grpc_timer_heap_remove(&pq, el);
114 GPR_ASSERT(!contains(&pq, el));
115 inpq[elem_num] = 0;
116 check_valid(&pq);
117 }
118 }
119
120 grpc_timer_heap_destroy(&pq);
121 gpr_free(test_elements);
122 gpr_free(inpq);
123 }
124
125 /*******************************************************************************
126 * test2
127 */
128
129 typedef struct {
130 grpc_timer elem;
131 bool inserted;
132 } elem_struct;
133
search_elems(elem_struct * elems,size_t count,bool inserted)134 static elem_struct* search_elems(elem_struct* elems, size_t count,
135 bool inserted) {
136 size_t* search_order =
137 static_cast<size_t*>(gpr_malloc(count * sizeof(*search_order)));
138 for (size_t i = 0; i < count; i++) {
139 search_order[i] = i;
140 }
141 for (size_t i = 0; i < count * 2; i++) {
142 size_t a = static_cast<size_t>(rand()) % count;
143 size_t b = static_cast<size_t>(rand()) % count;
144 GPR_SWAP(size_t, search_order[a], search_order[b]);
145 }
146 elem_struct* out = nullptr;
147 for (size_t i = 0; out == nullptr && i < count; i++) {
148 if (elems[search_order[i]].inserted == inserted) {
149 out = &elems[search_order[i]];
150 }
151 }
152 gpr_free(search_order);
153 return out;
154 }
155
test2(void)156 static void test2(void) {
157 gpr_log(GPR_INFO, "test2");
158
159 grpc_timer_heap pq;
160
161 static const size_t elems_size = 1000;
162 elem_struct* elems =
163 static_cast<elem_struct*>(gpr_malloc(elems_size * sizeof(elem_struct)));
164 size_t num_inserted = 0;
165
166 grpc_timer_heap_init(&pq);
167 memset(elems, 0, elems_size);
168
169 for (size_t round = 0; round < 10000; round++) {
170 int r = rand() % 1000;
171 if (r <= 550) {
172 /* 55% of the time we try to add something */
173 elem_struct* el = search_elems(elems, GPR_ARRAY_SIZE(elems), false);
174 if (el != nullptr) {
175 el->elem.deadline = random_deadline();
176 grpc_timer_heap_add(&pq, &el->elem);
177 el->inserted = true;
178 num_inserted++;
179 check_valid(&pq);
180 }
181 } else if (r <= 650) {
182 /* 10% of the time we try to remove something */
183 elem_struct* el = search_elems(elems, GPR_ARRAY_SIZE(elems), true);
184 if (el != nullptr) {
185 grpc_timer_heap_remove(&pq, &el->elem);
186 el->inserted = false;
187 num_inserted--;
188 check_valid(&pq);
189 }
190 } else {
191 /* the remaining times we pop */
192 if (num_inserted > 0) {
193 grpc_timer* top = grpc_timer_heap_top(&pq);
194 grpc_timer_heap_pop(&pq);
195 for (size_t i = 0; i < elems_size; i++) {
196 if (top == &elems[i].elem) {
197 GPR_ASSERT(elems[i].inserted);
198 elems[i].inserted = false;
199 }
200 }
201 num_inserted--;
202 check_valid(&pq);
203 }
204 }
205
206 if (num_inserted) {
207 grpc_millis* min_deadline = nullptr;
208 for (size_t i = 0; i < elems_size; i++) {
209 if (elems[i].inserted) {
210 if (min_deadline == nullptr) {
211 min_deadline = &elems[i].elem.deadline;
212 } else {
213 if (elems[i].elem.deadline < *min_deadline) {
214 min_deadline = &elems[i].elem.deadline;
215 }
216 }
217 }
218 }
219 GPR_ASSERT(grpc_timer_heap_top(&pq)->deadline == *min_deadline);
220 }
221 }
222
223 grpc_timer_heap_destroy(&pq);
224 gpr_free(elems);
225 }
226
shrink_test(void)227 static void shrink_test(void) {
228 gpr_log(GPR_INFO, "shrink_test");
229
230 grpc_timer_heap pq;
231 size_t i;
232 size_t expected_size;
233
234 /* A large random number to allow for multiple shrinkages, at least 512. */
235 const size_t num_elements = static_cast<size_t>(rand()) % 2000 + 512;
236
237 grpc_timer_heap_init(&pq);
238
239 /* Create a priority queue with many elements. Make sure the Size() is
240 correct. */
241 for (i = 0; i < num_elements; ++i) {
242 GPR_ASSERT(i == pq.timer_count);
243 grpc_timer_heap_add(&pq, create_test_elements(1));
244 }
245 GPR_ASSERT(num_elements == pq.timer_count);
246
247 /* Remove elements until the Size is 1/4 the original size. */
248 while (pq.timer_count > num_elements / 4) {
249 grpc_timer* const te = pq.timers[pq.timer_count - 1];
250 grpc_timer_heap_remove(&pq, te);
251 gpr_free(te);
252 }
253 GPR_ASSERT(num_elements / 4 == pq.timer_count);
254
255 /* Expect that Capacity is in the right range:
256 Size * 2 <= Capacity <= Size * 4 */
257 GPR_ASSERT(pq.timer_count * 2 <= pq.timer_capacity);
258 GPR_ASSERT(pq.timer_capacity <= pq.timer_count * 4);
259 check_valid(&pq);
260
261 /* Remove the rest of the elements. Check that the Capacity is not more than
262 4 times the Size and not less than 2 times, but never goes below 16. */
263 expected_size = pq.timer_count;
264 while (pq.timer_count > 0) {
265 const size_t which = static_cast<size_t>(rand()) % pq.timer_count;
266 grpc_timer* te = pq.timers[which];
267 grpc_timer_heap_remove(&pq, te);
268 gpr_free(te);
269 expected_size--;
270 GPR_ASSERT(expected_size == pq.timer_count);
271 GPR_ASSERT(pq.timer_count * 2 <= pq.timer_capacity);
272 if (pq.timer_count >= 8) {
273 GPR_ASSERT(pq.timer_capacity <= pq.timer_count * 4);
274 } else {
275 GPR_ASSERT(16 <= pq.timer_capacity);
276 }
277 check_valid(&pq);
278 }
279
280 GPR_ASSERT(0 == pq.timer_count);
281 GPR_ASSERT(pq.timer_capacity >= 16 && pq.timer_capacity < 32);
282
283 grpc_timer_heap_destroy(&pq);
284 }
285
main(int argc,char ** argv)286 int main(int argc, char** argv) {
287 int i;
288
289 grpc_test_init(argc, argv);
290
291 for (i = 0; i < 5; i++) {
292 test1();
293 test2();
294 shrink_test();
295 }
296
297 return 0;
298 }
299