diff options
Diffstat (limited to 'src/core/lib/slice')
-rw-r--r-- | src/core/lib/slice/slice.c | 130 | ||||
-rw-r--r-- | src/core/lib/slice/slice_hash_table.c | 127 | ||||
-rw-r--r-- | src/core/lib/slice/slice_hash_table.h | 77 | ||||
-rw-r--r-- | src/core/lib/slice/slice_intern.c | 344 | ||||
-rw-r--r-- | src/core/lib/slice/slice_internal.h | 15 | ||||
-rw-r--r-- | src/core/lib/slice/slice_string_helpers.c | 5 | ||||
-rw-r--r-- | src/core/lib/slice/slice_string_helpers.h | 5 | ||||
-rw-r--r-- | src/core/lib/slice/slice_traits.h | 44 |
8 files changed, 727 insertions, 20 deletions
diff --git a/src/core/lib/slice/slice.c b/src/core/lib/slice/slice.c index 76118102ec..1cddf062cd 100644 --- a/src/core/lib/slice/slice.c +++ b/src/core/lib/slice/slice.c @@ -41,23 +41,30 @@ #include "src/core/lib/iomgr/exec_ctx.h" -grpc_slice gpr_empty_slice(void) { +char *grpc_slice_to_c_string(grpc_slice slice) { + char *out = gpr_malloc(GRPC_SLICE_LENGTH(slice) + 1); + memcpy(out, GRPC_SLICE_START_PTR(slice), GRPC_SLICE_LENGTH(slice)); + out[GRPC_SLICE_LENGTH(slice)] = 0; + return out; +} + +grpc_slice grpc_empty_slice(void) { grpc_slice out; - out.refcount = 0; + out.refcount = NULL; out.data.inlined.length = 0; return out; } grpc_slice grpc_slice_ref_internal(grpc_slice slice) { if (slice.refcount) { - slice.refcount->ref(slice.refcount); + slice.refcount->vtable->ref(slice.refcount); } return slice; } void grpc_slice_unref_internal(grpc_exec_ctx *exec_ctx, grpc_slice slice) { if (slice.refcount) { - slice.refcount->unref(exec_ctx, slice.refcount); + slice.refcount->vtable->unref(exec_ctx, slice.refcount); } } @@ -78,16 +85,24 @@ void grpc_slice_unref(grpc_slice slice) { static void noop_ref(void *unused) {} static void noop_unref(grpc_exec_ctx *exec_ctx, void *unused) {} -static grpc_slice_refcount noop_refcount = {noop_ref, noop_unref}; +static const grpc_slice_refcount_vtable noop_refcount_vtable = { + noop_ref, noop_unref, grpc_slice_default_eq_impl, + grpc_slice_default_hash_impl}; +static grpc_slice_refcount noop_refcount = {&noop_refcount_vtable, + &noop_refcount}; -grpc_slice grpc_slice_from_static_string(const char *s) { +grpc_slice grpc_slice_from_static_buffer(const void *s, size_t len) { grpc_slice slice; slice.refcount = &noop_refcount; slice.data.refcounted.bytes = (uint8_t *)s; - slice.data.refcounted.length = strlen(s); + slice.data.refcounted.length = len; return slice; } +grpc_slice grpc_slice_from_static_string(const char *s) { + return grpc_slice_from_static_buffer(s, strlen(s)); +} + /* grpc_slice_new support structures - we create a refcount object extended with the user provided data pointer & destroy function */ typedef struct new_slice_refcount { @@ -110,14 +125,18 @@ static void new_slice_unref(grpc_exec_ctx *exec_ctx, void *p) { } } +static const grpc_slice_refcount_vtable new_slice_vtable = { + new_slice_ref, new_slice_unref, grpc_slice_default_eq_impl, + grpc_slice_default_hash_impl}; + grpc_slice grpc_slice_new_with_user_data(void *p, size_t len, void (*destroy)(void *), void *user_data) { grpc_slice slice; new_slice_refcount *rc = gpr_malloc(sizeof(new_slice_refcount)); gpr_ref_init(&rc->refs, 1); - rc->rc.ref = new_slice_ref; - rc->rc.unref = new_slice_unref; + rc->rc.vtable = &new_slice_vtable; + rc->rc.sub_refcount = &rc->rc; rc->user_destroy = destroy; rc->user_data = user_data; @@ -155,14 +174,18 @@ static void new_with_len_unref(grpc_exec_ctx *exec_ctx, void *p) { } } +static const grpc_slice_refcount_vtable new_with_len_vtable = { + new_with_len_ref, new_with_len_unref, grpc_slice_default_eq_impl, + grpc_slice_default_hash_impl}; + grpc_slice grpc_slice_new_with_len(void *p, size_t len, void (*destroy)(void *, size_t)) { grpc_slice slice; new_with_len_slice_refcount *rc = gpr_malloc(sizeof(new_with_len_slice_refcount)); gpr_ref_init(&rc->refs, 1); - rc->rc.ref = new_with_len_ref; - rc->rc.unref = new_with_len_unref; + rc->rc.vtable = &new_with_len_vtable; + rc->rc.sub_refcount = &rc->rc; rc->user_destroy = destroy; rc->user_data = p; rc->user_length = len; @@ -200,6 +223,10 @@ static void malloc_unref(grpc_exec_ctx *exec_ctx, void *p) { } } +static const grpc_slice_refcount_vtable malloc_vtable = { + malloc_ref, malloc_unref, grpc_slice_default_eq_impl, + grpc_slice_default_hash_impl}; + grpc_slice grpc_slice_malloc(size_t length) { grpc_slice slice; @@ -219,8 +246,8 @@ grpc_slice grpc_slice_malloc(size_t length) { this reference. */ gpr_ref_init(&rc->refs, 1); - rc->base.ref = malloc_ref; - rc->base.unref = malloc_unref; + rc->base.vtable = &malloc_vtable; + rc->base.sub_refcount = &rc->base; /* Build up the slice to be returned. */ /* The slices refcount points back to the allocated block. */ @@ -247,7 +274,7 @@ grpc_slice grpc_slice_sub_no_ref(grpc_slice source, size_t begin, size_t end) { GPR_ASSERT(source.data.refcounted.length >= end); /* Build the result */ - subset.refcount = source.refcount; + subset.refcount = source.refcount->sub_refcount; /* Point into the source array */ subset.data.refcounted.bytes = source.data.refcounted.bytes + begin; subset.data.refcounted.length = end - begin; @@ -273,7 +300,7 @@ grpc_slice grpc_slice_sub(grpc_slice source, size_t begin, size_t end) { } else { subset = grpc_slice_sub_no_ref(source, begin, end); /* Bump the refcount */ - subset.refcount->ref(subset.refcount); + subset.refcount->vtable->ref(subset.refcount); } return subset; } @@ -300,13 +327,14 @@ grpc_slice grpc_slice_split_tail(grpc_slice *source, size_t split) { tail_length); } else { /* Build the result */ - tail.refcount = source->refcount; + tail.refcount = source->refcount->sub_refcount; /* Bump the refcount */ - tail.refcount->ref(tail.refcount); + tail.refcount->vtable->ref(tail.refcount); /* Point into the source array */ tail.data.refcounted.bytes = source->data.refcounted.bytes + split; tail.data.refcounted.length = tail_length; } + source->refcount = source->refcount->sub_refcount; source->data.refcounted.length = split; } @@ -332,18 +360,20 @@ grpc_slice grpc_slice_split_head(grpc_slice *source, size_t split) { head.refcount = NULL; head.data.inlined.length = (uint8_t)split; memcpy(head.data.inlined.bytes, source->data.refcounted.bytes, split); + source->refcount = source->refcount->sub_refcount; source->data.refcounted.bytes += split; source->data.refcounted.length -= split; } else { GPR_ASSERT(source->data.refcounted.length >= split); /* Build the result */ - head.refcount = source->refcount; + head.refcount = source->refcount->sub_refcount; /* Bump the refcount */ - head.refcount->ref(head.refcount); + head.refcount->vtable->ref(head.refcount); /* Point into the source array */ head.data.refcounted.bytes = source->data.refcounted.bytes; head.data.refcounted.length = split; + source->refcount = source->refcount->sub_refcount; source->data.refcounted.bytes += split; source->data.refcounted.length -= split; } @@ -351,6 +381,19 @@ grpc_slice grpc_slice_split_head(grpc_slice *source, size_t split) { return head; } +int grpc_slice_default_eq_impl(grpc_slice a, grpc_slice b) { + return GRPC_SLICE_LENGTH(a) == GRPC_SLICE_LENGTH(b) && + 0 == memcmp(GRPC_SLICE_START_PTR(a), GRPC_SLICE_START_PTR(b), + GRPC_SLICE_LENGTH(a)); +} + +int grpc_slice_eq(grpc_slice a, grpc_slice b) { + if (a.refcount && b.refcount && a.refcount->vtable == b.refcount->vtable) { + return a.refcount->vtable->eq(a, b); + } + return grpc_slice_default_eq_impl(a, b); +} + int grpc_slice_cmp(grpc_slice a, grpc_slice b) { int d = (int)(GRPC_SLICE_LENGTH(a) - GRPC_SLICE_LENGTH(b)); if (d != 0) return d; @@ -367,8 +410,55 @@ int grpc_slice_str_cmp(grpc_slice a, const char *b) { int grpc_slice_is_equivalent(grpc_slice a, grpc_slice b) { if (a.refcount == NULL || b.refcount == NULL) { - return grpc_slice_cmp(a, b) == 0; + return grpc_slice_eq(a, b); } return a.data.refcounted.length == b.data.refcounted.length && a.data.refcounted.bytes == b.data.refcounted.bytes; } + +int grpc_slice_buf_start_eq(grpc_slice a, const void *b, size_t len) { + if (GRPC_SLICE_LENGTH(a) < len) return 0; + return 0 == memcmp(GRPC_SLICE_START_PTR(a), b, len); +} + +int grpc_slice_rchr(grpc_slice s, char c) { + const char *b = (const char *)GRPC_SLICE_START_PTR(s); + int i; + for (i = (int)GRPC_SLICE_LENGTH(s) - 1; i != -1 && b[i] != c; i--) + ; + return i; +} + +int grpc_slice_chr(grpc_slice s, char c) { + const char *b = (const char *)GRPC_SLICE_START_PTR(s); + const char *p = memchr(b, c, GRPC_SLICE_LENGTH(s)); + return p == NULL ? -1 : (int)(p - b); +} + +int grpc_slice_slice(grpc_slice haystack, grpc_slice needle) { + size_t haystack_len = GRPC_SLICE_LENGTH(haystack); + const uint8_t *haystack_bytes = GRPC_SLICE_START_PTR(haystack); + size_t needle_len = GRPC_SLICE_LENGTH(needle); + const uint8_t *needle_bytes = GRPC_SLICE_START_PTR(needle); + + if (haystack_len == 0 || needle_len == 0) return -1; + if (haystack_len < needle_len) return -1; + if (haystack_len == needle_len) + return grpc_slice_eq(haystack, needle) ? 0 : -1; + if (needle_len == 1) return grpc_slice_chr(haystack, (char)*needle_bytes); + + const uint8_t *last = haystack_bytes + haystack_len - needle_len; + for (const uint8_t *cur = haystack_bytes; cur != last; ++cur) { + if (0 == memcmp(cur, needle_bytes, needle_len)) { + return (int)(cur - haystack_bytes); + } + } + return -1; +} + +grpc_slice grpc_slice_dup(grpc_slice a) { + grpc_slice copy = grpc_slice_malloc(GRPC_SLICE_LENGTH(a)); + memcpy(GRPC_SLICE_START_PTR(copy), GRPC_SLICE_START_PTR(a), + GRPC_SLICE_LENGTH(a)); + return copy; +} diff --git a/src/core/lib/slice/slice_hash_table.c b/src/core/lib/slice/slice_hash_table.c new file mode 100644 index 0000000000..46f807f4a5 --- /dev/null +++ b/src/core/lib/slice/slice_hash_table.c @@ -0,0 +1,127 @@ +// +// 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_hash_table.h" + +#include <stdbool.h> +#include <string.h> + +#include <grpc/support/alloc.h> +#include <grpc/support/log.h> + +#include "src/core/lib/slice/slice_internal.h" +#include "src/core/lib/transport/metadata.h" + +struct grpc_slice_hash_table { + gpr_refcount refs; + size_t size; + grpc_slice_hash_table_entry* entries; +}; + +static bool is_empty(grpc_slice_hash_table_entry* entry) { + return entry->vtable == NULL; +} + +// Helper function for insert and get operations that performs quadratic +// probing (https://en.wikipedia.org/wiki/Quadratic_probing). +static size_t grpc_slice_hash_table_find_index( + const grpc_slice_hash_table* table, const grpc_slice key, bool find_empty) { + size_t hash = grpc_slice_hash(key); + for (size_t i = 0; i < table->size; ++i) { + const size_t idx = (hash + i * i) % table->size; + if (is_empty(&table->entries[idx])) { + return find_empty ? idx : table->size; + } + if (grpc_slice_eq(table->entries[idx].key, key)) { + return idx; + } + } + return table->size; // Not found. +} + +static void grpc_slice_hash_table_add( + grpc_slice_hash_table* table, grpc_slice key, void* value, + const grpc_slice_hash_table_vtable* vtable) { + GPR_ASSERT(value != NULL); + const size_t idx = + grpc_slice_hash_table_find_index(table, key, true /* find_empty */); + GPR_ASSERT(idx != table->size); // Table should never be full. + grpc_slice_hash_table_entry* entry = &table->entries[idx]; + entry->key = grpc_slice_ref_internal(key); + entry->value = vtable->copy_value(value); + entry->vtable = vtable; +} + +grpc_slice_hash_table* grpc_slice_hash_table_create( + size_t num_entries, grpc_slice_hash_table_entry* entries) { + grpc_slice_hash_table* table = gpr_malloc(sizeof(*table)); + memset(table, 0, sizeof(*table)); + gpr_ref_init(&table->refs, 1); + // Quadratic probing gets best performance when the table is no more + // than half full. + table->size = num_entries * 2; + const size_t entry_size = sizeof(grpc_slice_hash_table_entry) * table->size; + table->entries = gpr_malloc(entry_size); + memset(table->entries, 0, entry_size); + for (size_t i = 0; i < num_entries; ++i) { + grpc_slice_hash_table_entry* entry = &entries[i]; + grpc_slice_hash_table_add(table, entry->key, entry->value, entry->vtable); + } + return table; +} + +grpc_slice_hash_table* grpc_slice_hash_table_ref(grpc_slice_hash_table* table) { + if (table != NULL) gpr_ref(&table->refs); + return table; +} + +void grpc_slice_hash_table_unref(grpc_exec_ctx* exec_ctx, + grpc_slice_hash_table* table) { + if (table != NULL && gpr_unref(&table->refs)) { + for (size_t i = 0; i < table->size; ++i) { + grpc_slice_hash_table_entry* entry = &table->entries[i]; + if (!is_empty(entry)) { + grpc_slice_unref_internal(exec_ctx, entry->key); + entry->vtable->destroy_value(exec_ctx, entry->value); + } + } + gpr_free(table->entries); + gpr_free(table); + } +} + +void* grpc_slice_hash_table_get(const grpc_slice_hash_table* table, + const grpc_slice key) { + const size_t idx = + grpc_slice_hash_table_find_index(table, key, false /* find_empty */); + if (idx == table->size) return NULL; // Not found. + return table->entries[idx].value; +} diff --git a/src/core/lib/slice/slice_hash_table.h b/src/core/lib/slice/slice_hash_table.h new file mode 100644 index 0000000000..d0c27122d7 --- /dev/null +++ b/src/core/lib/slice/slice_hash_table.h @@ -0,0 +1,77 @@ +/* + * 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. + */ + +#ifndef GRPC_CORE_LIB_SLICE_SLICE_HASH_TABLE_H +#define GRPC_CORE_LIB_SLICE_SLICE_HASH_TABLE_H + +#include "src/core/lib/transport/metadata.h" + +/** Hash table implementation. + * + * This implementation uses open addressing + * (https://en.wikipedia.org/wiki/Open_addressing) with quadratic + * probing (https://en.wikipedia.org/wiki/Quadratic_probing). + * + * The keys are \a grpc_slice objects. The values are arbitrary pointers + * with a common vtable. + * + * Hash tables are intentionally immutable, to avoid the need for locking. + */ + +typedef struct grpc_slice_hash_table grpc_slice_hash_table; + +typedef struct grpc_slice_hash_table_vtable { + void (*destroy_value)(grpc_exec_ctx *exec_ctx, void *value); + void *(*copy_value)(void *value); +} grpc_slice_hash_table_vtable; + +typedef struct grpc_slice_hash_table_entry { + grpc_slice key; + void *value; /* Must not be NULL. */ + const grpc_slice_hash_table_vtable *vtable; +} grpc_slice_hash_table_entry; + +/** Creates a new hash table of containing \a entries, which is an array + of length \a num_entries. + Creates its own copy of all keys and values from \a entries. */ +grpc_slice_hash_table *grpc_slice_hash_table_create( + size_t num_entries, grpc_slice_hash_table_entry *entries); + +grpc_slice_hash_table *grpc_slice_hash_table_ref(grpc_slice_hash_table *table); +void grpc_slice_hash_table_unref(grpc_exec_ctx *exec_ctx, + grpc_slice_hash_table *table); + +/** Returns the value from \a table associated with \a key. + Returns NULL if \a key is not found. */ +void *grpc_slice_hash_table_get(const grpc_slice_hash_table *table, + const grpc_slice key); + +#endif /* GRPC_CORE_LIB_SLICE_SLICE_HASH_TABLE_H */ diff --git a/src/core/lib/slice/slice_intern.c b/src/core/lib/slice/slice_intern.c new file mode 100644 index 0000000000..7cbd17bffd --- /dev/null +++ b/src/core/lib/slice/slice_intern.c @@ -0,0 +1,344 @@ +/* + * + * 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); + } +} diff --git a/src/core/lib/slice/slice_internal.h b/src/core/lib/slice/slice_internal.h index 6185333ca7..6467b0a8d6 100644 --- a/src/core/lib/slice/slice_internal.h +++ b/src/core/lib/slice/slice_internal.h @@ -46,4 +46,19 @@ void grpc_slice_buffer_reset_and_unref_internal(grpc_exec_ctx *exec_ctx, void grpc_slice_buffer_destroy_internal(grpc_exec_ctx *exec_ctx, grpc_slice_buffer *sb); +/* Check if a slice is interned */ +bool grpc_slice_is_interned(grpc_slice slice); + +void grpc_slice_intern_init(void); +void grpc_slice_intern_shutdown(void); +void grpc_test_only_set_slice_hash_seed(uint32_t key); +// if slice matches a static slice, returns the static slice +// otherwise returns the passed in slice (without reffing it) +// used for surface boundaries where we might receive an un-interned static +// string +grpc_slice grpc_slice_maybe_static_intern(grpc_slice slice, + bool *returned_slice_is_different); +uint32_t grpc_static_slice_hash(grpc_slice s); +int grpc_static_slice_eq(grpc_slice a, grpc_slice b); + #endif /* GRPC_CORE_LIB_SLICE_SLICE_INTERNAL_H */ diff --git a/src/core/lib/slice/slice_string_helpers.c b/src/core/lib/slice/slice_string_helpers.c index 839c366b32..99695007cc 100644 --- a/src/core/lib/slice/slice_string_helpers.c +++ b/src/core/lib/slice/slice_string_helpers.c @@ -88,3 +88,8 @@ void grpc_slice_split(grpc_slice str, const char *sep, grpc_slice_buffer *dst) { grpc_slice_buffer_add_indexed(dst, grpc_slice_ref_internal(str)); } } + +bool grpc_parse_slice_to_uint32(grpc_slice str, uint32_t *result) { + return gpr_parse_bytes_to_uint32((const char *)GRPC_SLICE_START_PTR(str), + GRPC_SLICE_LENGTH(str), result) != 0; +} diff --git a/src/core/lib/slice/slice_string_helpers.h b/src/core/lib/slice/slice_string_helpers.h index 151c720777..4a4deec6e5 100644 --- a/src/core/lib/slice/slice_string_helpers.h +++ b/src/core/lib/slice/slice_string_helpers.h @@ -34,12 +34,15 @@ #ifndef GRPC_CORE_LIB_SLICE_SLICE_STRING_HELPERS_H #define GRPC_CORE_LIB_SLICE_SLICE_STRING_HELPERS_H +#include <stdbool.h> #include <stddef.h> #include <grpc/slice.h> #include <grpc/slice_buffer.h> #include <grpc/support/port_platform.h> +#include "src/core/lib/support/string.h" + #ifdef __cplusplus extern "C" { #endif @@ -51,6 +54,8 @@ char *grpc_dump_slice(grpc_slice slice, uint32_t flags); * should be a properly initialized instance. */ void grpc_slice_split(grpc_slice str, const char *sep, grpc_slice_buffer *dst); +bool grpc_parse_slice_to_uint32(grpc_slice str, uint32_t *result); + #ifdef __cplusplus } #endif diff --git a/src/core/lib/slice/slice_traits.h b/src/core/lib/slice/slice_traits.h new file mode 100644 index 0000000000..8a283dc65c --- /dev/null +++ b/src/core/lib/slice/slice_traits.h @@ -0,0 +1,44 @@ +/* + * + * 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. + * + */ + +#ifndef GRPC_CORE_LIB_SLICE_SLICE_TRAITS_H +#define GRPC_CORE_LIB_SLICE_SLICE_TRAITS_H + +#include <grpc/slice.h> +#include <stdbool.h> + +bool grpc_slice_is_legal_header(grpc_slice s); +bool grpc_slice_is_legal_nonbin_header(grpc_slice s); +bool grpc_slice_is_bin_suffixed(grpc_slice s); + +#endif /* GRPC_CORE_LIB_SLICE_SLICE_TRAITS_H */ |