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/ext/transport/chttp2/transport/stream_map.h"
20 #include <grpc/support/log.h>
21 #include "test/core/util/test_config.h"
22
23 #define LOG_TEST(x) gpr_log(GPR_INFO, "%s", x)
24
25 /* test creation & destruction */
test_no_op(void)26 static void test_no_op(void) {
27 grpc_chttp2_stream_map map;
28
29 LOG_TEST("test_no_op");
30
31 grpc_chttp2_stream_map_init(&map, 8);
32 grpc_chttp2_stream_map_destroy(&map);
33 }
34
35 /* test lookup on an empty map */
test_empty_find(void)36 static void test_empty_find(void) {
37 grpc_chttp2_stream_map map;
38
39 LOG_TEST("test_empty_find");
40
41 grpc_chttp2_stream_map_init(&map, 8);
42 GPR_ASSERT(nullptr == grpc_chttp2_stream_map_find(&map, 39128));
43 grpc_chttp2_stream_map_destroy(&map);
44 }
45
46 /* test it's safe to delete twice */
test_double_deletion(void)47 static void test_double_deletion(void) {
48 grpc_chttp2_stream_map map;
49
50 LOG_TEST("test_double_deletion");
51
52 grpc_chttp2_stream_map_init(&map, 8);
53 GPR_ASSERT(0 == grpc_chttp2_stream_map_size(&map));
54 grpc_chttp2_stream_map_add(&map, 1, (void*)1);
55 GPR_ASSERT((void*)1 == grpc_chttp2_stream_map_find(&map, 1));
56 GPR_ASSERT(1 == grpc_chttp2_stream_map_size(&map));
57 GPR_ASSERT((void*)1 == grpc_chttp2_stream_map_delete(&map, 1));
58 GPR_ASSERT(0 == grpc_chttp2_stream_map_size(&map));
59 GPR_ASSERT(nullptr == grpc_chttp2_stream_map_find(&map, 1));
60 GPR_ASSERT(nullptr == grpc_chttp2_stream_map_delete(&map, 1));
61 GPR_ASSERT(nullptr == grpc_chttp2_stream_map_find(&map, 1));
62 GPR_ASSERT(nullptr == grpc_chttp2_stream_map_delete(&map, 1));
63 GPR_ASSERT(nullptr == grpc_chttp2_stream_map_find(&map, 1));
64 GPR_ASSERT(nullptr == grpc_chttp2_stream_map_delete(&map, 1));
65 GPR_ASSERT(nullptr == grpc_chttp2_stream_map_find(&map, 1));
66 grpc_chttp2_stream_map_destroy(&map);
67 }
68
69 /* test add & lookup */
test_basic_add_find(uint32_t n)70 static void test_basic_add_find(uint32_t n) {
71 grpc_chttp2_stream_map map;
72 uint32_t i;
73 size_t got;
74
75 LOG_TEST("test_basic_add_find");
76 gpr_log(GPR_INFO, "n = %d", n);
77
78 grpc_chttp2_stream_map_init(&map, 8);
79 GPR_ASSERT(0 == grpc_chttp2_stream_map_size(&map));
80 for (i = 1; i <= n; i++) {
81 grpc_chttp2_stream_map_add(&map, i, (void*)static_cast<uintptr_t>(i));
82 }
83 GPR_ASSERT(n == grpc_chttp2_stream_map_size(&map));
84 GPR_ASSERT(nullptr == grpc_chttp2_stream_map_find(&map, 0));
85 GPR_ASSERT(nullptr == grpc_chttp2_stream_map_find(&map, n + 1));
86 for (i = 1; i <= n; i++) {
87 got = (uintptr_t)grpc_chttp2_stream_map_find(&map, i);
88 GPR_ASSERT(i == got);
89 }
90 grpc_chttp2_stream_map_destroy(&map);
91 }
92
93 /* verify that for_each gets the right values during test_delete_evens_XXX */
verify_for_each(void * user_data,uint32_t stream_id,void * ptr)94 static void verify_for_each(void* user_data, uint32_t stream_id, void* ptr) {
95 uint32_t* for_each_check = static_cast<uint32_t*>(user_data);
96 GPR_ASSERT(ptr);
97 GPR_ASSERT(*for_each_check == stream_id);
98 *for_each_check += 2;
99 }
100
check_delete_evens(grpc_chttp2_stream_map * map,uint32_t n)101 static void check_delete_evens(grpc_chttp2_stream_map* map, uint32_t n) {
102 uint32_t for_each_check = 1;
103 uint32_t i;
104 size_t got;
105
106 GPR_ASSERT(nullptr == grpc_chttp2_stream_map_find(map, 0));
107 GPR_ASSERT(nullptr == grpc_chttp2_stream_map_find(map, n + 1));
108 for (i = 1; i <= n; i++) {
109 if (i & 1) {
110 got = (uintptr_t)grpc_chttp2_stream_map_find(map, i);
111 GPR_ASSERT(i == got);
112 } else {
113 GPR_ASSERT(nullptr == grpc_chttp2_stream_map_find(map, i));
114 }
115 }
116
117 grpc_chttp2_stream_map_for_each(map, verify_for_each, &for_each_check);
118 if (n & 1) {
119 GPR_ASSERT(for_each_check == n + 2);
120 } else {
121 GPR_ASSERT(for_each_check == n + 1);
122 }
123 }
124
125 /* add a bunch of keys, delete the even ones, and make sure the map is
126 consistent */
test_delete_evens_sweep(uint32_t n)127 static void test_delete_evens_sweep(uint32_t n) {
128 grpc_chttp2_stream_map map;
129 uint32_t i;
130
131 LOG_TEST("test_delete_evens_sweep");
132 gpr_log(GPR_INFO, "n = %d", n);
133
134 grpc_chttp2_stream_map_init(&map, 8);
135 for (i = 1; i <= n; i++) {
136 grpc_chttp2_stream_map_add(&map, i, (void*)static_cast<uintptr_t>(i));
137 }
138 for (i = 1; i <= n; i++) {
139 if ((i & 1) == 0) {
140 GPR_ASSERT((void*)(uintptr_t)i == grpc_chttp2_stream_map_delete(&map, i));
141 }
142 }
143 check_delete_evens(&map, n);
144 grpc_chttp2_stream_map_destroy(&map);
145 }
146
147 /* add a bunch of keys, delete the even ones immediately, and make sure the map
148 is consistent */
test_delete_evens_incremental(uint32_t n)149 static void test_delete_evens_incremental(uint32_t n) {
150 grpc_chttp2_stream_map map;
151 uint32_t i;
152
153 LOG_TEST("test_delete_evens_incremental");
154 gpr_log(GPR_INFO, "n = %d", n);
155
156 grpc_chttp2_stream_map_init(&map, 8);
157 for (i = 1; i <= n; i++) {
158 grpc_chttp2_stream_map_add(&map, i, (void*)static_cast<uintptr_t>(i));
159 if ((i & 1) == 0) {
160 grpc_chttp2_stream_map_delete(&map, i);
161 }
162 }
163 check_delete_evens(&map, n);
164 grpc_chttp2_stream_map_destroy(&map);
165 }
166
167 /* add a bunch of keys, delete old ones after some time, ensure the
168 backing array does not grow */
test_periodic_compaction(uint32_t n)169 static void test_periodic_compaction(uint32_t n) {
170 grpc_chttp2_stream_map map;
171 uint32_t i;
172 uint32_t del;
173
174 LOG_TEST("test_periodic_compaction");
175 gpr_log(GPR_INFO, "n = %d", n);
176
177 grpc_chttp2_stream_map_init(&map, 16);
178 GPR_ASSERT(map.capacity == 16);
179 for (i = 1; i <= n; i++) {
180 grpc_chttp2_stream_map_add(&map, i, (void*)static_cast<uintptr_t>(i));
181 if (i > 8) {
182 del = i - 8;
183 GPR_ASSERT((void*)(uintptr_t)del ==
184 grpc_chttp2_stream_map_delete(&map, del));
185 }
186 }
187 GPR_ASSERT(map.capacity == 16);
188 grpc_chttp2_stream_map_destroy(&map);
189 }
190
main(int argc,char ** argv)191 int main(int argc, char** argv) {
192 uint32_t n = 1;
193 uint32_t prev = 1;
194 uint32_t tmp;
195
196 grpc_test_init(argc, argv);
197
198 test_no_op();
199 test_empty_find();
200 test_double_deletion();
201
202 while (n < 100000) {
203 test_basic_add_find(n);
204 test_delete_evens_sweep(n);
205 test_delete_evens_incremental(n);
206 test_periodic_compaction(n);
207
208 tmp = n;
209 n += prev;
210 prev = tmp;
211 }
212
213 return 0;
214 }
215