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