aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/core/lib/slice/slice_intern.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/core/lib/slice/slice_intern.c')
-rw-r--r--src/core/lib/slice/slice_intern.c344
1 files changed, 0 insertions, 344 deletions
diff --git a/src/core/lib/slice/slice_intern.c b/src/core/lib/slice/slice_intern.c
deleted file mode 100644
index 7cbd17bffd..0000000000
--- a/src/core/lib/slice/slice_intern.c
+++ /dev/null
@@ -1,344 +0,0 @@
-/*
- *
- * Copyright 2016, Google Inc.
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions are
- * met:
- *
- * * Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above
- * copyright notice, this list of conditions and the following disclaimer
- * in the documentation and/or other materials provided with the
- * distribution.
- * * Neither the name of Google Inc. nor the names of its
- * contributors may be used to endorse or promote products derived from
- * this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
- * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- */
-
-#include "src/core/lib/slice/slice_internal.h"
-
-#include <string.h>
-
-#include <grpc/support/alloc.h>
-#include <grpc/support/log.h>
-
-#include "src/core/lib/iomgr/iomgr_internal.h" /* for iomgr_abort_on_leaks() */
-#include "src/core/lib/profiling/timers.h"
-#include "src/core/lib/slice/slice_string_helpers.h"
-#include "src/core/lib/support/murmur_hash.h"
-#include "src/core/lib/transport/static_metadata.h"
-
-#define LOG2_SHARD_COUNT 5
-#define SHARD_COUNT (1 << LOG2_SHARD_COUNT)
-#define INITIAL_SHARD_CAPACITY 8
-
-#define TABLE_IDX(hash, capacity) (((hash) >> LOG2_SHARD_COUNT) % (capacity))
-#define SHARD_IDX(hash) ((hash) & ((1 << LOG2_SHARD_COUNT) - 1))
-
-typedef struct interned_slice_refcount {
- grpc_slice_refcount base;
- grpc_slice_refcount sub;
- size_t length;
- gpr_atm refcnt;
- uint32_t hash;
- struct interned_slice_refcount *bucket_next;
-} interned_slice_refcount;
-
-typedef struct slice_shard {
- gpr_mu mu;
- interned_slice_refcount **strs;
- size_t count;
- size_t capacity;
-} slice_shard;
-
-/* hash seed: decided at initialization time */
-static uint32_t g_hash_seed;
-static int g_forced_hash_seed = 0;
-
-static slice_shard g_shards[SHARD_COUNT];
-
-typedef struct {
- uint32_t hash;
- uint32_t idx;
-} static_metadata_hash_ent;
-
-static static_metadata_hash_ent
- static_metadata_hash[4 * GRPC_STATIC_MDSTR_COUNT];
-static uint32_t max_static_metadata_hash_probe;
-static uint32_t static_metadata_hash_values[GRPC_STATIC_MDSTR_COUNT];
-
-static void interned_slice_ref(void *p) {
- interned_slice_refcount *s = p;
- GPR_ASSERT(gpr_atm_no_barrier_fetch_add(&s->refcnt, 1) > 0);
-}
-
-static void interned_slice_destroy(interned_slice_refcount *s) {
- slice_shard *shard = &g_shards[SHARD_IDX(s->hash)];
- gpr_mu_lock(&shard->mu);
- GPR_ASSERT(0 == gpr_atm_no_barrier_load(&s->refcnt));
- interned_slice_refcount **prev_next;
- interned_slice_refcount *cur;
- for (prev_next = &shard->strs[TABLE_IDX(s->hash, shard->capacity)],
- cur = *prev_next;
- cur != s; prev_next = &cur->bucket_next, cur = cur->bucket_next)
- ;
- *prev_next = cur->bucket_next;
- shard->count--;
- gpr_free(s);
- gpr_mu_unlock(&shard->mu);
-}
-
-static void interned_slice_unref(grpc_exec_ctx *exec_ctx, void *p) {
- interned_slice_refcount *s = p;
- if (1 == gpr_atm_full_fetch_add(&s->refcnt, -1)) {
- interned_slice_destroy(s);
- }
-}
-
-static void interned_slice_sub_ref(void *p) {
- interned_slice_ref(((char *)p) - offsetof(interned_slice_refcount, sub));
-}
-
-static void interned_slice_sub_unref(grpc_exec_ctx *exec_ctx, void *p) {
- interned_slice_unref(exec_ctx,
- ((char *)p) - offsetof(interned_slice_refcount, sub));
-}
-
-static uint32_t interned_slice_hash(grpc_slice slice) {
- interned_slice_refcount *s = (interned_slice_refcount *)slice.refcount;
- return s->hash;
-}
-
-static int interned_slice_eq(grpc_slice a, grpc_slice b) {
- return a.refcount == b.refcount;
-}
-
-static const grpc_slice_refcount_vtable interned_slice_vtable = {
- interned_slice_ref, interned_slice_unref, interned_slice_eq,
- interned_slice_hash};
-static const grpc_slice_refcount_vtable interned_slice_sub_vtable = {
- interned_slice_sub_ref, interned_slice_sub_unref,
- grpc_slice_default_eq_impl, grpc_slice_default_hash_impl};
-
-static void grow_shard(slice_shard *shard) {
- size_t capacity = shard->capacity * 2;
- size_t i;
- interned_slice_refcount **strtab;
- interned_slice_refcount *s, *next;
-
- GPR_TIMER_BEGIN("grow_strtab", 0);
-
- strtab = gpr_malloc(sizeof(interned_slice_refcount *) * capacity);
- memset(strtab, 0, sizeof(interned_slice_refcount *) * capacity);
-
- for (i = 0; i < shard->capacity; i++) {
- for (s = shard->strs[i]; s; s = next) {
- size_t idx = TABLE_IDX(s->hash, capacity);
- next = s->bucket_next;
- s->bucket_next = strtab[idx];
- strtab[idx] = s;
- }
- }
-
- gpr_free(shard->strs);
- shard->strs = strtab;
- shard->capacity = capacity;
-
- GPR_TIMER_END("grow_strtab", 0);
-}
-
-static grpc_slice materialize(interned_slice_refcount *s) {
- grpc_slice slice;
- slice.refcount = &s->base;
- slice.data.refcounted.bytes = (uint8_t *)(s + 1);
- slice.data.refcounted.length = s->length;
- return slice;
-}
-
-uint32_t grpc_slice_default_hash_impl(grpc_slice s) {
- return gpr_murmur_hash3(GRPC_SLICE_START_PTR(s), GRPC_SLICE_LENGTH(s),
- g_hash_seed);
-}
-
-uint32_t grpc_static_slice_hash(grpc_slice s) {
- return static_metadata_hash_values[GRPC_STATIC_METADATA_INDEX(s)];
-}
-
-int grpc_static_slice_eq(grpc_slice a, grpc_slice b) {
- return GRPC_STATIC_METADATA_INDEX(a) == GRPC_STATIC_METADATA_INDEX(b);
-}
-
-uint32_t grpc_slice_hash(grpc_slice s) {
- return s.refcount == NULL ? grpc_slice_default_hash_impl(s)
- : s.refcount->vtable->hash(s);
-}
-
-grpc_slice grpc_slice_maybe_static_intern(grpc_slice slice,
- bool *returned_slice_is_different) {
- if (GRPC_IS_STATIC_METADATA_STRING(slice)) {
- return slice;
- }
-
- uint32_t hash = grpc_slice_hash(slice);
- for (uint32_t i = 0; i <= max_static_metadata_hash_probe; i++) {
- static_metadata_hash_ent ent =
- static_metadata_hash[(hash + i) % GPR_ARRAY_SIZE(static_metadata_hash)];
- if (ent.hash == hash && ent.idx < GRPC_STATIC_MDSTR_COUNT &&
- grpc_slice_eq(grpc_static_slice_table[ent.idx], slice)) {
- *returned_slice_is_different = true;
- return grpc_static_slice_table[ent.idx];
- }
- }
-
- return slice;
-}
-
-bool grpc_slice_is_interned(grpc_slice slice) {
- return (slice.refcount && slice.refcount->vtable == &interned_slice_vtable) ||
- GRPC_IS_STATIC_METADATA_STRING(slice);
-}
-
-grpc_slice grpc_slice_intern(grpc_slice slice) {
- if (GRPC_IS_STATIC_METADATA_STRING(slice)) {
- return slice;
- }
-
- uint32_t hash = grpc_slice_hash(slice);
- for (uint32_t i = 0; i <= max_static_metadata_hash_probe; i++) {
- static_metadata_hash_ent ent =
- static_metadata_hash[(hash + i) % GPR_ARRAY_SIZE(static_metadata_hash)];
- if (ent.hash == hash && ent.idx < GRPC_STATIC_MDSTR_COUNT &&
- grpc_slice_eq(grpc_static_slice_table[ent.idx], slice)) {
- return grpc_static_slice_table[ent.idx];
- }
- }
-
- interned_slice_refcount *s;
- slice_shard *shard = &g_shards[SHARD_IDX(hash)];
-
- gpr_mu_lock(&shard->mu);
-
- /* search for an existing string */
- size_t idx = TABLE_IDX(hash, shard->capacity);
- for (s = shard->strs[idx]; s; s = s->bucket_next) {
- if (s->hash == hash && grpc_slice_eq(slice, materialize(s))) {
- if (gpr_atm_no_barrier_fetch_add(&s->refcnt, 1) == 0) {
- /* If we get here, we've added a ref to something that was about to
- * die - drop it immediately.
- * The *only* possible path here (given the shard mutex) should be to
- * drop from one ref back to zero - assert that with a CAS */
- GPR_ASSERT(gpr_atm_rel_cas(&s->refcnt, 1, 0));
- /* and treat this as if we were never here... sshhh */
- } else {
- gpr_mu_unlock(&shard->mu);
- GPR_TIMER_END("grpc_mdstr_from_buffer", 0);
- return materialize(s);
- }
- }
- }
-
- /* not found: create a new string */
- /* string data goes after the internal_string header */
- s = gpr_malloc(sizeof(*s) + GRPC_SLICE_LENGTH(slice));
- gpr_atm_rel_store(&s->refcnt, 1);
- s->length = GRPC_SLICE_LENGTH(slice);
- s->hash = hash;
- s->base.vtable = &interned_slice_vtable;
- s->base.sub_refcount = &s->sub;
- s->sub.vtable = &interned_slice_sub_vtable;
- s->sub.sub_refcount = &s->sub;
- s->bucket_next = shard->strs[idx];
- shard->strs[idx] = s;
- memcpy(s + 1, GRPC_SLICE_START_PTR(slice), GRPC_SLICE_LENGTH(slice));
-
- shard->count++;
-
- if (shard->count > shard->capacity * 2) {
- grow_shard(shard);
- }
-
- gpr_mu_unlock(&shard->mu);
-
- return materialize(s);
-}
-
-void grpc_test_only_set_slice_hash_seed(uint32_t seed) {
- g_hash_seed = seed;
- g_forced_hash_seed = 1;
-}
-
-void grpc_slice_intern_init(void) {
- if (!g_forced_hash_seed) {
- g_hash_seed = (uint32_t)gpr_now(GPR_CLOCK_REALTIME).tv_nsec;
- }
- for (size_t i = 0; i < SHARD_COUNT; i++) {
- slice_shard *shard = &g_shards[i];
- gpr_mu_init(&shard->mu);
- shard->count = 0;
- shard->capacity = INITIAL_SHARD_CAPACITY;
- shard->strs = gpr_malloc(sizeof(*shard->strs) * shard->capacity);
- memset(shard->strs, 0, sizeof(*shard->strs) * shard->capacity);
- }
- for (size_t i = 0; i < GPR_ARRAY_SIZE(static_metadata_hash); i++) {
- static_metadata_hash[i].hash = 0;
- static_metadata_hash[i].idx = GRPC_STATIC_MDSTR_COUNT;
- }
- max_static_metadata_hash_probe = 0;
- for (size_t i = 0; i < GRPC_STATIC_MDSTR_COUNT; i++) {
- static_metadata_hash_values[i] =
- grpc_slice_default_hash_impl(grpc_static_slice_table[i]);
- for (size_t j = 0; j < GPR_ARRAY_SIZE(static_metadata_hash); j++) {
- size_t slot = (static_metadata_hash_values[i] + j) %
- GPR_ARRAY_SIZE(static_metadata_hash);
- if (static_metadata_hash[slot].idx == GRPC_STATIC_MDSTR_COUNT) {
- static_metadata_hash[slot].hash = static_metadata_hash_values[i];
- static_metadata_hash[slot].idx = (uint32_t)i;
- if (j > max_static_metadata_hash_probe) {
- max_static_metadata_hash_probe = (uint32_t)j;
- }
- break;
- }
- }
- }
-}
-
-void grpc_slice_intern_shutdown(void) {
- for (size_t i = 0; i < SHARD_COUNT; i++) {
- slice_shard *shard = &g_shards[i];
- gpr_mu_destroy(&shard->mu);
- /* TODO(ctiller): GPR_ASSERT(shard->count == 0); */
- if (shard->count != 0) {
- gpr_log(GPR_DEBUG, "WARNING: %" PRIuPTR " metadata strings were leaked",
- shard->count);
- for (size_t j = 0; j < shard->capacity; j++) {
- for (interned_slice_refcount *s = shard->strs[j]; s;
- s = s->bucket_next) {
- char *text =
- grpc_dump_slice(materialize(s), GPR_DUMP_HEX | GPR_DUMP_ASCII);
- gpr_log(GPR_DEBUG, "LEAKED: %s", text);
- gpr_free(text);
- }
- }
- if (grpc_iomgr_abort_on_leaks()) {
- abort();
- }
- }
- gpr_free(shard->strs);
- }
-}
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-30 23:38:47 +0000