Line data Source code
1 : /*
2 : *
3 : * Copyright 2015, Google Inc.
4 : * All rights reserved.
5 : *
6 : * Redistribution and use in source and binary forms, with or without
7 : * modification, are permitted provided that the following conditions are
8 : * met:
9 : *
10 : * * Redistributions of source code must retain the above copyright
11 : * notice, this list of conditions and the following disclaimer.
12 : * * Redistributions in binary form must reproduce the above
13 : * copyright notice, this list of conditions and the following disclaimer
14 : * in the documentation and/or other materials provided with the
15 : * distribution.
16 : * * Neither the name of Google Inc. nor the names of its
17 : * contributors may be used to endorse or promote products derived from
18 : * this software without specific prior written permission.
19 : *
20 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 : * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 : * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 : * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 : * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 : * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 : * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 : *
32 : */
33 :
34 : #include "src/core/iomgr/alarm_heap.h"
35 :
36 : #include <stdlib.h>
37 : #include <string.h>
38 :
39 : #include <grpc/support/alloc.h>
40 : #include <grpc/support/log.h>
41 : #include "test/core/util/test_config.h"
42 :
43 31302 : static gpr_timespec random_deadline(void) {
44 : gpr_timespec ts;
45 31302 : ts.tv_sec = rand();
46 31302 : ts.tv_nsec = rand();
47 31302 : ts.clock_type = GPR_CLOCK_REALTIME;
48 31302 : return ts;
49 : }
50 :
51 5561 : static grpc_alarm *create_test_elements(size_t num_elements) {
52 5561 : grpc_alarm *elems = gpr_malloc(num_elements * sizeof(grpc_alarm));
53 : size_t i;
54 12117 : for (i = 0; i < num_elements; i++) {
55 6556 : elems[i].deadline = random_deadline();
56 : }
57 5561 : return elems;
58 : }
59 :
60 0 : static int cmp_elem(const void *a, const void *b) {
61 0 : int i = *(const int *)a;
62 0 : int j = *(const int *)b;
63 0 : return i - j;
64 : }
65 :
66 51005 : static size_t *all_top(grpc_alarm_heap *pq, size_t *n) {
67 51005 : size_t *vec = NULL;
68 : size_t *need_to_check_children;
69 51005 : size_t num_need_to_check_children = 0;
70 :
71 51005 : *n = 0;
72 51005 : if (pq->alarm_count == 0) return vec;
73 51005 : need_to_check_children =
74 51005 : gpr_malloc(pq->alarm_count * sizeof(*need_to_check_children));
75 51005 : need_to_check_children[num_need_to_check_children++] = 0;
76 51005 : vec = gpr_malloc(pq->alarm_count * sizeof(*vec));
77 153015 : while (num_need_to_check_children > 0) {
78 51005 : size_t ind = need_to_check_children[0];
79 : size_t leftchild, rightchild;
80 51005 : num_need_to_check_children--;
81 51005 : memmove(need_to_check_children, need_to_check_children + 1,
82 : num_need_to_check_children * sizeof(*need_to_check_children));
83 51005 : vec[(*n)++] = ind;
84 51005 : leftchild = 1u + 2u * ind;
85 51005 : if (leftchild < pq->alarm_count) {
86 51000 : if (gpr_time_cmp(pq->alarms[leftchild]->deadline,
87 51000 : pq->alarms[ind]->deadline) >= 0) {
88 0 : need_to_check_children[num_need_to_check_children++] = leftchild;
89 : }
90 51000 : rightchild = leftchild + 1;
91 101995 : if (rightchild < pq->alarm_count &&
92 50995 : gpr_time_cmp(pq->alarms[rightchild]->deadline,
93 50995 : pq->alarms[ind]->deadline) >= 0) {
94 0 : need_to_check_children[num_need_to_check_children++] = rightchild;
95 : }
96 : }
97 : }
98 :
99 51005 : gpr_free(need_to_check_children);
100 :
101 51005 : return vec;
102 : }
103 :
104 51005 : static void check_pq_top(grpc_alarm *elements, grpc_alarm_heap *pq,
105 : gpr_uint8 *inpq, size_t num_elements) {
106 51005 : gpr_timespec max_deadline = gpr_inf_past(GPR_CLOCK_REALTIME);
107 51005 : size_t *max_deadline_indices =
108 51005 : gpr_malloc(num_elements * sizeof(*max_deadline_indices));
109 : size_t *top_elements;
110 51005 : size_t num_max_deadline_indices = 0;
111 : size_t num_top_elements;
112 : size_t i;
113 10252005 : for (i = 0; i < num_elements; ++i) {
114 10201000 : if (inpq[i] && gpr_time_cmp(elements[i].deadline, max_deadline) >= 0) {
115 262536 : if (gpr_time_cmp(elements[i].deadline, max_deadline) > 0) {
116 262536 : num_max_deadline_indices = 0;
117 262536 : max_deadline = elements[i].deadline;
118 : }
119 262536 : max_deadline_indices[num_max_deadline_indices++] = elements[i].heap_index;
120 : }
121 : }
122 51005 : qsort(max_deadline_indices, num_max_deadline_indices,
123 : sizeof(*max_deadline_indices), cmp_elem);
124 51005 : top_elements = all_top(pq, &num_top_elements);
125 51005 : GPR_ASSERT(num_top_elements == num_max_deadline_indices);
126 102010 : for (i = 0; i < num_top_elements; i++) {
127 51005 : GPR_ASSERT(max_deadline_indices[i] == top_elements[i]);
128 : }
129 51005 : gpr_free(max_deadline_indices);
130 51005 : gpr_free(top_elements);
131 51005 : }
132 :
133 103000 : static int contains(grpc_alarm_heap *pq, grpc_alarm *el) {
134 : size_t i;
135 8706279 : for (i = 0; i < pq->alarm_count; i++) {
136 8655279 : if (pq->alarms[i] == el) return 1;
137 : }
138 51000 : return 0;
139 : }
140 :
141 52397 : static void check_valid(grpc_alarm_heap *pq) {
142 : size_t i;
143 5465925 : for (i = 0; i < pq->alarm_count; ++i) {
144 5413528 : size_t left_child = 1u + 2u * i;
145 5413528 : size_t right_child = left_child + 1u;
146 5413528 : if (left_child < pq->alarm_count) {
147 2693667 : GPR_ASSERT(gpr_time_cmp(pq->alarms[i]->deadline,
148 : pq->alarms[left_child]->deadline) >= 0);
149 : }
150 5413528 : if (right_child < pq->alarm_count) {
151 2667474 : GPR_ASSERT(gpr_time_cmp(pq->alarms[i]->deadline,
152 : pq->alarms[right_child]->deadline) >= 0);
153 : }
154 : }
155 52397 : }
156 :
157 5 : static void test1(void) {
158 : grpc_alarm_heap pq;
159 5 : const size_t num_test_elements = 200;
160 5 : const size_t num_test_operations = 10000;
161 : size_t i;
162 5 : grpc_alarm *test_elements = create_test_elements(num_test_elements);
163 5 : gpr_uint8 *inpq = gpr_malloc(num_test_elements);
164 :
165 5 : grpc_alarm_heap_init(&pq);
166 5 : memset(inpq, 0, num_test_elements);
167 5 : GPR_ASSERT(grpc_alarm_heap_is_empty(&pq));
168 5 : check_valid(&pq);
169 1005 : for (i = 0; i < num_test_elements; ++i) {
170 1000 : GPR_ASSERT(!contains(&pq, &test_elements[i]));
171 1000 : grpc_alarm_heap_add(&pq, &test_elements[i]);
172 1000 : check_valid(&pq);
173 1000 : GPR_ASSERT(contains(&pq, &test_elements[i]));
174 1000 : inpq[i] = 1;
175 1000 : check_pq_top(test_elements, &pq, inpq, num_test_elements);
176 : }
177 1005 : for (i = 0; i < num_test_elements; ++i) {
178 : /* Test that check still succeeds even for element that wasn't just
179 : inserted. */
180 1000 : GPR_ASSERT(contains(&pq, &test_elements[i]));
181 : }
182 :
183 5 : GPR_ASSERT(pq.alarm_count == num_test_elements);
184 :
185 5 : check_pq_top(test_elements, &pq, inpq, num_test_elements);
186 :
187 50005 : for (i = 0; i < num_test_operations; ++i) {
188 50000 : size_t elem_num = (size_t)rand() % num_test_elements;
189 50000 : grpc_alarm *el = &test_elements[elem_num];
190 50000 : if (!inpq[elem_num]) { /* not in pq */
191 24746 : GPR_ASSERT(!contains(&pq, el));
192 24746 : el->deadline = random_deadline();
193 24746 : grpc_alarm_heap_add(&pq, el);
194 24746 : GPR_ASSERT(contains(&pq, el));
195 24746 : inpq[elem_num] = 1;
196 24746 : check_pq_top(test_elements, &pq, inpq, num_test_elements);
197 24746 : check_valid(&pq);
198 : } else {
199 25254 : GPR_ASSERT(contains(&pq, el));
200 25254 : grpc_alarm_heap_remove(&pq, el);
201 25254 : GPR_ASSERT(!contains(&pq, el));
202 25254 : inpq[elem_num] = 0;
203 25254 : check_pq_top(test_elements, &pq, inpq, num_test_elements);
204 25254 : check_valid(&pq);
205 : }
206 : }
207 :
208 5 : grpc_alarm_heap_destroy(&pq);
209 5 : gpr_free(test_elements);
210 5 : gpr_free(inpq);
211 5 : }
212 :
213 5 : static void shrink_test(void) {
214 : grpc_alarm_heap pq;
215 : size_t i;
216 : size_t expected_size;
217 :
218 : /* A large random number to allow for multiple shrinkages, at least 512. */
219 5 : const size_t num_elements = (size_t)rand() % 2000 + 512;
220 :
221 5 : grpc_alarm_heap_init(&pq);
222 :
223 : /* Create a priority queue with many elements. Make sure the Size() is
224 : correct. */
225 5561 : for (i = 0; i < num_elements; ++i) {
226 5556 : GPR_ASSERT(i == pq.alarm_count);
227 5556 : grpc_alarm_heap_add(&pq, create_test_elements(1));
228 : }
229 5 : GPR_ASSERT(num_elements == pq.alarm_count);
230 :
231 : /* Remove elements until the Size is 1/4 the original size. */
232 4179 : while (pq.alarm_count > num_elements / 4) {
233 4169 : grpc_alarm *const te = pq.alarms[pq.alarm_count - 1];
234 4169 : grpc_alarm_heap_remove(&pq, te);
235 4169 : gpr_free(te);
236 : }
237 5 : GPR_ASSERT(num_elements / 4 == pq.alarm_count);
238 :
239 : /* Expect that Capacity is in the right range:
240 : Size * 2 <= Capacity <= Size * 4 */
241 5 : GPR_ASSERT(pq.alarm_count * 2 <= pq.alarm_capacity);
242 5 : GPR_ASSERT(pq.alarm_capacity <= pq.alarm_count * 4);
243 5 : check_valid(&pq);
244 :
245 : /* Remove the rest of the elements. Check that the Capacity is not more than
246 : 4 times the Size and not less than 2 times, but never goes below 16. */
247 5 : expected_size = pq.alarm_count;
248 1397 : while (pq.alarm_count > 0) {
249 1387 : const size_t which = (size_t)rand() % pq.alarm_count;
250 1387 : grpc_alarm *te = pq.alarms[which];
251 1387 : grpc_alarm_heap_remove(&pq, te);
252 1387 : gpr_free(te);
253 1387 : expected_size--;
254 1387 : GPR_ASSERT(expected_size == pq.alarm_count);
255 1387 : GPR_ASSERT(pq.alarm_count * 2 <= pq.alarm_capacity);
256 1387 : if (pq.alarm_count >= 8) {
257 1347 : GPR_ASSERT(pq.alarm_capacity <= pq.alarm_count * 4);
258 : } else {
259 40 : GPR_ASSERT(16 <= pq.alarm_capacity);
260 : }
261 1387 : check_valid(&pq);
262 : }
263 :
264 5 : GPR_ASSERT(0 == pq.alarm_count);
265 5 : GPR_ASSERT(pq.alarm_capacity >= 16 && pq.alarm_capacity < 32);
266 :
267 5 : grpc_alarm_heap_destroy(&pq);
268 5 : }
269 :
270 1 : int main(int argc, char **argv) {
271 : int i;
272 :
273 1 : grpc_test_init(argc, argv);
274 :
275 6 : for (i = 0; i < 5; i++) {
276 5 : test1();
277 5 : shrink_test();
278 : }
279 :
280 1 : return 0;
281 : }
|
