Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 1 | /* |
| 2 | * |
| 3 | * Copyright 2016, 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/lib/slice/slice_internal.h" |
| 35 | |
| 36 | #include <string.h> |
| 37 | |
| 38 | #include <grpc/support/alloc.h> |
| 39 | #include <grpc/support/log.h> |
| 40 | |
| 41 | #include "src/core/lib/iomgr/iomgr_internal.h" /* for iomgr_abort_on_leaks() */ |
| 42 | #include "src/core/lib/profiling/timers.h" |
| 43 | #include "src/core/lib/slice/slice_string_helpers.h" |
| 44 | #include "src/core/lib/support/murmur_hash.h" |
| 45 | #include "src/core/lib/transport/static_metadata.h" |
| 46 | |
| 47 | #define LOG2_SHARD_COUNT 5 |
| 48 | #define SHARD_COUNT (1 << LOG2_SHARD_COUNT) |
| 49 | #define INITIAL_SHARD_CAPACITY 8 |
| 50 | |
| 51 | #define TABLE_IDX(hash, capacity) (((hash) >> LOG2_SHARD_COUNT) % (capacity)) |
| 52 | #define SHARD_IDX(hash) ((hash) & ((1 << LOG2_SHARD_COUNT) - 1)) |
| 53 | |
| 54 | typedef struct interned_slice_refcount { |
| 55 | grpc_slice_refcount base; |
| 56 | grpc_slice_refcount sub; |
| 57 | size_t length; |
| 58 | gpr_atm refcnt; |
| 59 | uint32_t hash; |
| 60 | struct interned_slice_refcount *bucket_next; |
| 61 | } interned_slice_refcount; |
| 62 | |
| 63 | typedef struct slice_shard { |
| 64 | gpr_mu mu; |
| 65 | interned_slice_refcount **strs; |
| 66 | size_t count; |
| 67 | size_t capacity; |
| 68 | } slice_shard; |
| 69 | |
| 70 | /* hash seed: decided at initialization time */ |
| 71 | static uint32_t g_hash_seed; |
| 72 | static int g_forced_hash_seed = 0; |
| 73 | |
| 74 | static slice_shard g_shards[SHARD_COUNT]; |
| 75 | |
| 76 | typedef struct { |
| 77 | uint32_t hash; |
| 78 | uint32_t idx; |
| 79 | } static_metadata_hash_ent; |
| 80 | |
| 81 | static static_metadata_hash_ent |
| 82 | static_metadata_hash[4 * GRPC_STATIC_MDSTR_COUNT]; |
| 83 | static uint32_t max_static_metadata_hash_probe; |
| 84 | static uint32_t static_metadata_hash_values[GRPC_STATIC_MDSTR_COUNT]; |
| 85 | |
| 86 | static void interned_slice_ref(void *p) { |
| 87 | interned_slice_refcount *s = p; |
| 88 | GPR_ASSERT(gpr_atm_no_barrier_fetch_add(&s->refcnt, 1) > 0); |
| 89 | } |
| 90 | |
| 91 | static void interned_slice_destroy(interned_slice_refcount *s) { |
| 92 | slice_shard *shard = &g_shards[SHARD_IDX(s->hash)]; |
| 93 | gpr_mu_lock(&shard->mu); |
| 94 | GPR_ASSERT(0 == gpr_atm_no_barrier_load(&s->refcnt)); |
| 95 | interned_slice_refcount **prev_next; |
| 96 | interned_slice_refcount *cur; |
| 97 | for (prev_next = &shard->strs[TABLE_IDX(s->hash, shard->capacity)], |
| 98 | cur = *prev_next; |
| 99 | cur != s; prev_next = &cur->bucket_next, cur = cur->bucket_next) |
| 100 | ; |
| 101 | *prev_next = cur->bucket_next; |
| 102 | shard->count--; |
| 103 | gpr_free(s); |
| 104 | gpr_mu_unlock(&shard->mu); |
| 105 | } |
| 106 | |
| 107 | static void interned_slice_unref(grpc_exec_ctx *exec_ctx, void *p) { |
| 108 | interned_slice_refcount *s = p; |
| 109 | if (1 == gpr_atm_full_fetch_add(&s->refcnt, -1)) { |
| 110 | interned_slice_destroy(s); |
| 111 | } |
| 112 | } |
| 113 | |
| 114 | static void interned_slice_sub_ref(void *p) { |
| 115 | interned_slice_ref(((char *)p) - offsetof(interned_slice_refcount, sub)); |
| 116 | } |
| 117 | |
| 118 | static void interned_slice_sub_unref(grpc_exec_ctx *exec_ctx, void *p) { |
| 119 | interned_slice_unref(exec_ctx, |
| 120 | ((char *)p) - offsetof(interned_slice_refcount, sub)); |
| 121 | } |
| 122 | |
| 123 | static uint32_t interned_slice_hash(grpc_slice slice) { |
| 124 | interned_slice_refcount *s = (interned_slice_refcount *)slice.refcount; |
| 125 | return s->hash; |
| 126 | } |
| 127 | |
| 128 | static int interned_slice_eq(grpc_slice a, grpc_slice b) { |
| 129 | return a.refcount == b.refcount; |
| 130 | } |
| 131 | |
| 132 | static const grpc_slice_refcount_vtable interned_slice_vtable = { |
| 133 | interned_slice_ref, interned_slice_unref, interned_slice_eq, |
| 134 | interned_slice_hash}; |
| 135 | static const grpc_slice_refcount_vtable interned_slice_sub_vtable = { |
| 136 | interned_slice_sub_ref, interned_slice_sub_unref, |
| 137 | grpc_slice_default_eq_impl, grpc_slice_default_hash_impl}; |
| 138 | |
| 139 | static void grow_shard(slice_shard *shard) { |
| 140 | size_t capacity = shard->capacity * 2; |
| 141 | size_t i; |
| 142 | interned_slice_refcount **strtab; |
| 143 | interned_slice_refcount *s, *next; |
| 144 | |
| 145 | GPR_TIMER_BEGIN("grow_strtab", 0); |
| 146 | |
Craig Tiller | 6f41788 | 2017-02-16 14:09:39 -0800 | [diff] [blame] | 147 | strtab = gpr_zalloc(sizeof(interned_slice_refcount *) * capacity); |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 148 | |
| 149 | for (i = 0; i < shard->capacity; i++) { |
| 150 | for (s = shard->strs[i]; s; s = next) { |
| 151 | size_t idx = TABLE_IDX(s->hash, capacity); |
| 152 | next = s->bucket_next; |
| 153 | s->bucket_next = strtab[idx]; |
| 154 | strtab[idx] = s; |
| 155 | } |
| 156 | } |
| 157 | |
| 158 | gpr_free(shard->strs); |
| 159 | shard->strs = strtab; |
| 160 | shard->capacity = capacity; |
| 161 | |
| 162 | GPR_TIMER_END("grow_strtab", 0); |
| 163 | } |
| 164 | |
| 165 | static grpc_slice materialize(interned_slice_refcount *s) { |
| 166 | grpc_slice slice; |
| 167 | slice.refcount = &s->base; |
| 168 | slice.data.refcounted.bytes = (uint8_t *)(s + 1); |
| 169 | slice.data.refcounted.length = s->length; |
| 170 | return slice; |
| 171 | } |
| 172 | |
| 173 | uint32_t grpc_slice_default_hash_impl(grpc_slice s) { |
| 174 | return gpr_murmur_hash3(GRPC_SLICE_START_PTR(s), GRPC_SLICE_LENGTH(s), |
| 175 | g_hash_seed); |
| 176 | } |
| 177 | |
| 178 | uint32_t grpc_static_slice_hash(grpc_slice s) { |
| 179 | return static_metadata_hash_values[GRPC_STATIC_METADATA_INDEX(s)]; |
| 180 | } |
| 181 | |
| 182 | int grpc_static_slice_eq(grpc_slice a, grpc_slice b) { |
| 183 | return GRPC_STATIC_METADATA_INDEX(a) == GRPC_STATIC_METADATA_INDEX(b); |
| 184 | } |
| 185 | |
| 186 | uint32_t grpc_slice_hash(grpc_slice s) { |
| 187 | return s.refcount == NULL ? grpc_slice_default_hash_impl(s) |
| 188 | : s.refcount->vtable->hash(s); |
| 189 | } |
| 190 | |
| 191 | grpc_slice grpc_slice_maybe_static_intern(grpc_slice slice, |
| 192 | bool *returned_slice_is_different) { |
| 193 | if (GRPC_IS_STATIC_METADATA_STRING(slice)) { |
| 194 | return slice; |
| 195 | } |
| 196 | |
| 197 | uint32_t hash = grpc_slice_hash(slice); |
| 198 | for (uint32_t i = 0; i <= max_static_metadata_hash_probe; i++) { |
| 199 | static_metadata_hash_ent ent = |
| 200 | static_metadata_hash[(hash + i) % GPR_ARRAY_SIZE(static_metadata_hash)]; |
| 201 | if (ent.hash == hash && ent.idx < GRPC_STATIC_MDSTR_COUNT && |
| 202 | grpc_slice_eq(grpc_static_slice_table[ent.idx], slice)) { |
| 203 | *returned_slice_is_different = true; |
| 204 | return grpc_static_slice_table[ent.idx]; |
| 205 | } |
| 206 | } |
| 207 | |
| 208 | return slice; |
| 209 | } |
| 210 | |
| 211 | bool grpc_slice_is_interned(grpc_slice slice) { |
| 212 | return (slice.refcount && slice.refcount->vtable == &interned_slice_vtable) || |
| 213 | GRPC_IS_STATIC_METADATA_STRING(slice); |
| 214 | } |
| 215 | |
| 216 | grpc_slice grpc_slice_intern(grpc_slice slice) { |
Craig Tiller | f7af2a9 | 2017-01-31 15:08:31 -0800 | [diff] [blame] | 217 | GPR_TIMER_BEGIN("grpc_slice_intern", 0); |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 218 | if (GRPC_IS_STATIC_METADATA_STRING(slice)) { |
Craig Tiller | f7af2a9 | 2017-01-31 15:08:31 -0800 | [diff] [blame] | 219 | GPR_TIMER_END("grpc_slice_intern", 0); |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 220 | return slice; |
| 221 | } |
| 222 | |
| 223 | uint32_t hash = grpc_slice_hash(slice); |
| 224 | for (uint32_t i = 0; i <= max_static_metadata_hash_probe; i++) { |
| 225 | static_metadata_hash_ent ent = |
| 226 | static_metadata_hash[(hash + i) % GPR_ARRAY_SIZE(static_metadata_hash)]; |
| 227 | if (ent.hash == hash && ent.idx < GRPC_STATIC_MDSTR_COUNT && |
| 228 | grpc_slice_eq(grpc_static_slice_table[ent.idx], slice)) { |
Craig Tiller | f7af2a9 | 2017-01-31 15:08:31 -0800 | [diff] [blame] | 229 | GPR_TIMER_END("grpc_slice_intern", 0); |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 230 | return grpc_static_slice_table[ent.idx]; |
| 231 | } |
| 232 | } |
| 233 | |
| 234 | interned_slice_refcount *s; |
| 235 | slice_shard *shard = &g_shards[SHARD_IDX(hash)]; |
| 236 | |
| 237 | gpr_mu_lock(&shard->mu); |
| 238 | |
| 239 | /* search for an existing string */ |
| 240 | size_t idx = TABLE_IDX(hash, shard->capacity); |
| 241 | for (s = shard->strs[idx]; s; s = s->bucket_next) { |
| 242 | if (s->hash == hash && grpc_slice_eq(slice, materialize(s))) { |
| 243 | if (gpr_atm_no_barrier_fetch_add(&s->refcnt, 1) == 0) { |
| 244 | /* If we get here, we've added a ref to something that was about to |
| 245 | * die - drop it immediately. |
| 246 | * The *only* possible path here (given the shard mutex) should be to |
| 247 | * drop from one ref back to zero - assert that with a CAS */ |
| 248 | GPR_ASSERT(gpr_atm_rel_cas(&s->refcnt, 1, 0)); |
| 249 | /* and treat this as if we were never here... sshhh */ |
| 250 | } else { |
| 251 | gpr_mu_unlock(&shard->mu); |
Craig Tiller | f7af2a9 | 2017-01-31 15:08:31 -0800 | [diff] [blame] | 252 | GPR_TIMER_END("grpc_slice_intern", 0); |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 253 | return materialize(s); |
| 254 | } |
| 255 | } |
| 256 | } |
| 257 | |
| 258 | /* not found: create a new string */ |
| 259 | /* string data goes after the internal_string header */ |
| 260 | s = gpr_malloc(sizeof(*s) + GRPC_SLICE_LENGTH(slice)); |
| 261 | gpr_atm_rel_store(&s->refcnt, 1); |
| 262 | s->length = GRPC_SLICE_LENGTH(slice); |
| 263 | s->hash = hash; |
| 264 | s->base.vtable = &interned_slice_vtable; |
| 265 | s->base.sub_refcount = &s->sub; |
| 266 | s->sub.vtable = &interned_slice_sub_vtable; |
| 267 | s->sub.sub_refcount = &s->sub; |
| 268 | s->bucket_next = shard->strs[idx]; |
| 269 | shard->strs[idx] = s; |
| 270 | memcpy(s + 1, GRPC_SLICE_START_PTR(slice), GRPC_SLICE_LENGTH(slice)); |
| 271 | |
| 272 | shard->count++; |
| 273 | |
| 274 | if (shard->count > shard->capacity * 2) { |
| 275 | grow_shard(shard); |
| 276 | } |
| 277 | |
| 278 | gpr_mu_unlock(&shard->mu); |
| 279 | |
Craig Tiller | f7af2a9 | 2017-01-31 15:08:31 -0800 | [diff] [blame] | 280 | GPR_TIMER_END("grpc_slice_intern", 0); |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 281 | return materialize(s); |
| 282 | } |
| 283 | |
| 284 | void grpc_test_only_set_slice_hash_seed(uint32_t seed) { |
| 285 | g_hash_seed = seed; |
| 286 | g_forced_hash_seed = 1; |
| 287 | } |
| 288 | |
| 289 | void grpc_slice_intern_init(void) { |
| 290 | if (!g_forced_hash_seed) { |
| 291 | g_hash_seed = (uint32_t)gpr_now(GPR_CLOCK_REALTIME).tv_nsec; |
| 292 | } |
| 293 | for (size_t i = 0; i < SHARD_COUNT; i++) { |
| 294 | slice_shard *shard = &g_shards[i]; |
| 295 | gpr_mu_init(&shard->mu); |
| 296 | shard->count = 0; |
| 297 | shard->capacity = INITIAL_SHARD_CAPACITY; |
Craig Tiller | 6f41788 | 2017-02-16 14:09:39 -0800 | [diff] [blame] | 298 | shard->strs = gpr_zalloc(sizeof(*shard->strs) * shard->capacity); |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 299 | } |
| 300 | for (size_t i = 0; i < GPR_ARRAY_SIZE(static_metadata_hash); i++) { |
| 301 | static_metadata_hash[i].hash = 0; |
| 302 | static_metadata_hash[i].idx = GRPC_STATIC_MDSTR_COUNT; |
| 303 | } |
| 304 | max_static_metadata_hash_probe = 0; |
| 305 | for (size_t i = 0; i < GRPC_STATIC_MDSTR_COUNT; i++) { |
| 306 | static_metadata_hash_values[i] = |
| 307 | grpc_slice_default_hash_impl(grpc_static_slice_table[i]); |
| 308 | for (size_t j = 0; j < GPR_ARRAY_SIZE(static_metadata_hash); j++) { |
| 309 | size_t slot = (static_metadata_hash_values[i] + j) % |
| 310 | GPR_ARRAY_SIZE(static_metadata_hash); |
| 311 | if (static_metadata_hash[slot].idx == GRPC_STATIC_MDSTR_COUNT) { |
| 312 | static_metadata_hash[slot].hash = static_metadata_hash_values[i]; |
| 313 | static_metadata_hash[slot].idx = (uint32_t)i; |
| 314 | if (j > max_static_metadata_hash_probe) { |
| 315 | max_static_metadata_hash_probe = (uint32_t)j; |
| 316 | } |
| 317 | break; |
| 318 | } |
| 319 | } |
| 320 | } |
| 321 | } |
| 322 | |
| 323 | void grpc_slice_intern_shutdown(void) { |
| 324 | for (size_t i = 0; i < SHARD_COUNT; i++) { |
| 325 | slice_shard *shard = &g_shards[i]; |
| 326 | gpr_mu_destroy(&shard->mu); |
| 327 | /* TODO(ctiller): GPR_ASSERT(shard->count == 0); */ |
| 328 | if (shard->count != 0) { |
| 329 | gpr_log(GPR_DEBUG, "WARNING: %" PRIuPTR " metadata strings were leaked", |
| 330 | shard->count); |
| 331 | for (size_t j = 0; j < shard->capacity; j++) { |
| 332 | for (interned_slice_refcount *s = shard->strs[j]; s; |
| 333 | s = s->bucket_next) { |
| 334 | char *text = |
| 335 | grpc_dump_slice(materialize(s), GPR_DUMP_HEX | GPR_DUMP_ASCII); |
| 336 | gpr_log(GPR_DEBUG, "LEAKED: %s", text); |
| 337 | gpr_free(text); |
| 338 | } |
| 339 | } |
| 340 | if (grpc_iomgr_abort_on_leaks()) { |
| 341 | abort(); |
| 342 | } |
| 343 | } |
| 344 | gpr_free(shard->strs); |
| 345 | } |
| 346 | } |