diff options
Diffstat (limited to 'src/core/transport/metadata.c')
| -rw-r--r-- | src/core/transport/metadata.c | 525 |
1 files changed, 525 insertions, 0 deletions
diff --git a/src/core/transport/metadata.c b/src/core/transport/metadata.c new file mode 100644 index 0000000000..ceb77df34d --- /dev/null +++ b/src/core/transport/metadata.c @@ -0,0 +1,525 @@ +/* + * + * Copyright 2014, 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/transport/metadata.h" + +#include <stddef.h> +#include <string.h> + +#include <grpc/support/alloc.h> +#include <grpc/support/log.h> +#include "src/core/support/murmur_hash.h" +#include <grpc/support/time.h> + +#define INITIAL_STRTAB_CAPACITY 4 +#define INITIAL_MDTAB_CAPACITY 4 + +#define KV_HASH(key, value) ((key)->hash ^ (value)->hash) + +typedef struct internal_string { + /* must be byte compatible with grpc_mdstr */ + gpr_slice slice; + gpr_uint32 hash; + + /* private only data */ + gpr_uint32 refs; + gpr_slice_refcount refcount; + + grpc_mdctx *context; + + struct internal_string *bucket_next; +} internal_string; + +typedef struct internal_metadata { + /* must be byte compatible with grpc_mdelem */ + internal_string *key; + internal_string *value; + + /* private only data */ + void *user_data; + void (*destroy_user_data)(void *user_data); + + gpr_uint32 refs; + grpc_mdctx *context; + struct internal_metadata *bucket_next; +} internal_metadata; + +struct grpc_mdctx { + gpr_uint32 hash_seed; + int orphaned; + + gpr_mu mu; + + internal_string **strtab; + size_t strtab_count; + size_t strtab_capacity; + + internal_metadata **mdtab; + size_t mdtab_count; + size_t mdtab_free; + size_t mdtab_capacity; +}; + +static void internal_string_ref(internal_string *s); +static void internal_string_unref(internal_string *s); +static void discard_metadata(grpc_mdctx *ctx); +static void gc_mdtab(grpc_mdctx *ctx); +static void metadata_context_destroy(grpc_mdctx *ctx); + +static void lock(grpc_mdctx *ctx) { gpr_mu_lock(&ctx->mu); } + +static void unlock(grpc_mdctx *ctx) { + /* If the context has been orphaned we'd like to delete it soon. We check + conditions in unlock as it signals the end of mutations on a context. + + We need to ensure all grpc_mdelem and grpc_mdstr elements have been deleted + first. This is equivalent to saying that both tables have zero counts, + which is equivalent to saying that strtab_count is zero (as mdelem's MUST + reference an mdstr for their key and value slots). + + To encourage that to happen, we start discarding zero reference count + mdelems on every unlock (instead of the usual 'I'm too loaded' trigger + case), since otherwise we can be stuck waiting for a garbage collection + that will never happen. */ + if (ctx->orphaned) { + /* uncomment if you're having trouble diagnosing an mdelem leak to make + things clearer (slows down destruction a lot, however) */ + /* gc_mdtab(ctx); */ + if (ctx->mdtab_count && ctx->mdtab_count == ctx->mdtab_free) { + discard_metadata(ctx); + } + if (ctx->strtab_count == 0) { + gpr_mu_unlock(&ctx->mu); + metadata_context_destroy(ctx); + return; + } + } + gpr_mu_unlock(&ctx->mu); +} + +static void ref_md(internal_metadata *md) { + if (0 == md->refs++) { + md->context->mdtab_free--; + } +} + +grpc_mdctx *grpc_mdctx_create_with_seed(gpr_uint32 seed) { + grpc_mdctx *ctx = gpr_malloc(sizeof(grpc_mdctx)); + + ctx->orphaned = 0; + ctx->hash_seed = seed; + gpr_mu_init(&ctx->mu); + ctx->strtab = gpr_malloc(sizeof(internal_string *) * INITIAL_STRTAB_CAPACITY); + memset(ctx->strtab, 0, sizeof(grpc_mdstr *) * INITIAL_STRTAB_CAPACITY); + ctx->strtab_count = 0; + ctx->strtab_capacity = INITIAL_STRTAB_CAPACITY; + ctx->mdtab = gpr_malloc(sizeof(internal_metadata *) * INITIAL_MDTAB_CAPACITY); + memset(ctx->mdtab, 0, sizeof(grpc_mdelem *) * INITIAL_MDTAB_CAPACITY); + ctx->mdtab_count = 0; + ctx->mdtab_capacity = INITIAL_MDTAB_CAPACITY; + ctx->mdtab_free = 0; + + return ctx; +} + +grpc_mdctx *grpc_mdctx_create() { + /* This seed is used to prevent remote connections from controlling hash table + * collisions. It needs to be somewhat unpredictable to a remote connection. + */ + return grpc_mdctx_create_with_seed(gpr_now().tv_nsec); +} + +static void discard_metadata(grpc_mdctx *ctx) { + size_t i; + internal_metadata *next, *cur; + + for (i = 0; i < ctx->mdtab_capacity; i++) { + cur = ctx->mdtab[i]; + while (cur) { + GPR_ASSERT(cur->refs == 0); + next = cur->bucket_next; + internal_string_unref(cur->key); + internal_string_unref(cur->value); + if (cur->user_data) { + cur->destroy_user_data(cur->user_data); + } + gpr_free(cur); + cur = next; + ctx->mdtab_free--; + ctx->mdtab_count--; + } + ctx->mdtab[i] = NULL; + } +} + +static void metadata_context_destroy(grpc_mdctx *ctx) { + gpr_mu_lock(&ctx->mu); + GPR_ASSERT(ctx->strtab_count == 0); + GPR_ASSERT(ctx->mdtab_count == 0); + GPR_ASSERT(ctx->mdtab_free == 0); + gpr_free(ctx->strtab); + gpr_free(ctx->mdtab); + gpr_mu_unlock(&ctx->mu); + gpr_mu_destroy(&ctx->mu); + gpr_free(ctx); +} + +void grpc_mdctx_orphan(grpc_mdctx *ctx) { + lock(ctx); + GPR_ASSERT(!ctx->orphaned); + ctx->orphaned = 1; + unlock(ctx); +} + +static void grow_strtab(grpc_mdctx *ctx) { + size_t capacity = ctx->strtab_capacity * 2; + size_t i; + internal_string **strtab = gpr_malloc(sizeof(internal_string *) * capacity); + internal_string *s, *next; + memset(strtab, 0, sizeof(internal_string *) * capacity); + + for (i = 0; i < ctx->strtab_capacity; i++) { + for (s = ctx->strtab[i]; s; s = next) { + next = s->bucket_next; + s->bucket_next = strtab[s->hash % capacity]; + strtab[s->hash % capacity] = s; + } + } + + gpr_free(ctx->strtab); + ctx->strtab = strtab; + ctx->strtab_capacity = capacity; +} + +static void internal_destroy_string(internal_string *is) { + internal_string **prev_next; + internal_string *cur; + grpc_mdctx *ctx = is->context; + for (prev_next = &ctx->strtab[is->hash % ctx->strtab_capacity], + cur = *prev_next; + cur != is; prev_next = &cur->bucket_next, cur = cur->bucket_next) + ; + *prev_next = cur->bucket_next; + ctx->strtab_count--; + gpr_free(is); +} + +static void internal_string_ref(internal_string *s) { ++s->refs; } + +static void internal_string_unref(internal_string *s) { + GPR_ASSERT(s->refs > 0); + if (0 == --s->refs) { + internal_destroy_string(s); + } +} + +static void slice_ref(void *p) { + internal_string *is = + (internal_string *)((char *)p - offsetof(internal_string, refcount)); + grpc_mdctx *ctx = is->context; + lock(ctx); + internal_string_ref(is); + unlock(ctx); +} + +static void slice_unref(void *p) { + internal_string *is = + (internal_string *)((char *)p - offsetof(internal_string, refcount)); + grpc_mdctx *ctx = is->context; + lock(ctx); + internal_string_unref(is); + unlock(ctx); +} + +grpc_mdstr *grpc_mdstr_from_string(grpc_mdctx *ctx, const char *str) { + return grpc_mdstr_from_buffer(ctx, (const gpr_uint8 *)str, strlen(str)); +} + +grpc_mdstr *grpc_mdstr_from_slice(grpc_mdctx *ctx, gpr_slice slice) { + grpc_mdstr *result = grpc_mdstr_from_buffer(ctx, GPR_SLICE_START_PTR(slice), + GPR_SLICE_LENGTH(slice)); + gpr_slice_unref(slice); + return result; +} + +grpc_mdstr *grpc_mdstr_from_buffer(grpc_mdctx *ctx, const gpr_uint8 *buf, + size_t length) { + gpr_uint32 hash = gpr_murmur_hash3(buf, length, ctx->hash_seed); + internal_string *s; + + lock(ctx); + + /* search for an existing string */ + for (s = ctx->strtab[hash % ctx->strtab_capacity]; s; s = s->bucket_next) { + if (s->hash == hash && GPR_SLICE_LENGTH(s->slice) == length && + 0 == memcmp(buf, GPR_SLICE_START_PTR(s->slice), length)) { + internal_string_ref(s); + unlock(ctx); + return (grpc_mdstr *)s; + } + } + + /* not found: create a new string */ + if (length + 1 < GPR_SLICE_INLINED_SIZE) { + /* string data goes directly into the slice */ + s = gpr_malloc(sizeof(internal_string)); + s->refs = 1; + s->slice.refcount = NULL; + memcpy(s->slice.data.inlined.bytes, buf, length); + s->slice.data.inlined.bytes[length] = 0; + s->slice.data.inlined.length = length; + } else { + /* string data goes after the internal_string header, and we +1 for null + terminator */ + s = gpr_malloc(sizeof(internal_string) + length + 1); + s->refs = 1; + s->refcount.ref = slice_ref; + s->refcount.unref = slice_unref; + s->slice.refcount = &s->refcount; + s->slice.data.refcounted.bytes = (gpr_uint8 *)(s + 1); + s->slice.data.refcounted.length = length; + memcpy(s->slice.data.refcounted.bytes, buf, length); + /* add a null terminator for cheap c string conversion when desired */ + s->slice.data.refcounted.bytes[length] = 0; + } + s->hash = hash; + s->context = ctx; + s->bucket_next = ctx->strtab[hash % ctx->strtab_capacity]; + ctx->strtab[hash % ctx->strtab_capacity] = s; + + ctx->strtab_count++; + + if (ctx->strtab_count > ctx->strtab_capacity * 2) { + grow_strtab(ctx); + } + + unlock(ctx); + + return (grpc_mdstr *)s; +} + +static void gc_mdtab(grpc_mdctx *ctx) { + size_t i; + internal_metadata **prev_next; + internal_metadata *md, *next; + + for (i = 0; i < ctx->mdtab_capacity; i++) { + prev_next = &ctx->mdtab[i]; + for (md = ctx->mdtab[i]; md; md = next) { + next = md->bucket_next; + if (md->refs == 0) { + internal_string_unref(md->key); + internal_string_unref(md->value); + if (md->user_data) { + md->destroy_user_data(md->user_data); + } + gpr_free(md); + *prev_next = next; + ctx->mdtab_free--; + ctx->mdtab_count--; + } else { + prev_next = &md->bucket_next; + } + } + } + + GPR_ASSERT(ctx->mdtab_free == 0); +} + +static void grow_mdtab(grpc_mdctx *ctx) { + size_t capacity = ctx->mdtab_capacity * 2; + size_t i; + internal_metadata **mdtab = + gpr_malloc(sizeof(internal_metadata *) * capacity); + internal_metadata *md, *next; + gpr_uint32 hash; + memset(mdtab, 0, sizeof(internal_metadata *) * capacity); + + for (i = 0; i < ctx->mdtab_capacity; i++) { + for (md = ctx->mdtab[i]; md; md = next) { + hash = KV_HASH(md->key, md->value); + next = md->bucket_next; + md->bucket_next = mdtab[hash % capacity]; + mdtab[hash % capacity] = md; + } + } + + gpr_free(ctx->mdtab); + ctx->mdtab = mdtab; + ctx->mdtab_capacity = capacity; +} + +static void rehash_mdtab(grpc_mdctx *ctx) { + if (ctx->mdtab_free > ctx->mdtab_capacity / 4) { + gc_mdtab(ctx); + } else { + grow_mdtab(ctx); + } +} + +grpc_mdelem *grpc_mdelem_from_metadata_strings(grpc_mdctx *ctx, + grpc_mdstr *mkey, + grpc_mdstr *mvalue) { + internal_string *key = (internal_string *)mkey; + internal_string *value = (internal_string *)mvalue; + gpr_uint32 hash = KV_HASH(mkey, mvalue); + internal_metadata *md; + + GPR_ASSERT(key->context == ctx); + GPR_ASSERT(value->context == ctx); + + lock(ctx); + + /* search for an existing pair */ + for (md = ctx->mdtab[hash % ctx->mdtab_capacity]; md; md = md->bucket_next) { + if (md->key == key && md->value == value) { + ref_md(md); + internal_string_unref(key); + internal_string_unref(value); + unlock(ctx); + return (grpc_mdelem *)md; + } + } + + /* not found: create a new pair */ + md = gpr_malloc(sizeof(internal_metadata)); + md->refs = 1; + md->context = ctx; + md->key = key; + md->value = value; + md->user_data = NULL; + md->destroy_user_data = NULL; + md->bucket_next = ctx->mdtab[hash % ctx->mdtab_capacity]; + ctx->mdtab[hash % ctx->mdtab_capacity] = md; + ctx->mdtab_count++; + + if (ctx->mdtab_count > ctx->mdtab_capacity * 2) { + rehash_mdtab(ctx); + } + + unlock(ctx); + + return (grpc_mdelem *)md; +} + +grpc_mdelem *grpc_mdelem_from_strings(grpc_mdctx *ctx, const char *key, + const char *value) { + return grpc_mdelem_from_metadata_strings(ctx, + grpc_mdstr_from_string(ctx, key), + grpc_mdstr_from_string(ctx, value)); +} + +grpc_mdelem *grpc_mdelem_from_slices(grpc_mdctx *ctx, gpr_slice key, + gpr_slice value) { + return grpc_mdelem_from_metadata_strings(ctx, grpc_mdstr_from_slice(ctx, key), + grpc_mdstr_from_slice(ctx, value)); +} + +grpc_mdelem *grpc_mdelem_from_string_and_buffer(grpc_mdctx *ctx, + const char *key, + const gpr_uint8 *value, + size_t value_length) { + return grpc_mdelem_from_metadata_strings( + ctx, grpc_mdstr_from_string(ctx, key), + grpc_mdstr_from_buffer(ctx, value, value_length)); +} + +grpc_mdelem *grpc_mdelem_ref(grpc_mdelem *gmd) { + internal_metadata *md = (internal_metadata *)gmd; + grpc_mdctx *ctx = md->context; + lock(ctx); + ref_md(md); + unlock(ctx); + return gmd; +} + +void grpc_mdelem_unref(grpc_mdelem *gmd) { + internal_metadata *md = (internal_metadata *)gmd; + grpc_mdctx *ctx = md->context; + lock(ctx); + GPR_ASSERT(md->refs); + if (0 == --md->refs) { + ctx->mdtab_free++; + } + unlock(ctx); +} + +const char *grpc_mdstr_as_c_string(grpc_mdstr *s) { + return (const char *)GPR_SLICE_START_PTR(s->slice); +} + +grpc_mdstr *grpc_mdstr_ref(grpc_mdstr *gs) { + internal_string *s = (internal_string *)gs; + grpc_mdctx *ctx = s->context; + lock(ctx); + internal_string_ref(s); + unlock(ctx); + return gs; +} + +void grpc_mdstr_unref(grpc_mdstr *gs) { + internal_string *s = (internal_string *)gs; + grpc_mdctx *ctx = s->context; + lock(ctx); + internal_string_unref(s); + unlock(ctx); +} + +size_t grpc_mdctx_get_mdtab_capacity_test_only(grpc_mdctx *ctx) { + return ctx->mdtab_capacity; +} + +size_t grpc_mdctx_get_mdtab_count_test_only(grpc_mdctx *ctx) { + return ctx->mdtab_count; +} + +size_t grpc_mdctx_get_mdtab_free_test_only(grpc_mdctx *ctx) { + return ctx->mdtab_free; +} + +void *grpc_mdelem_get_user_data(grpc_mdelem *md, + void (*if_destroy_func)(void *)) { + internal_metadata *im = (internal_metadata *)md; + return im->destroy_user_data == if_destroy_func ? im->user_data : NULL; +} + +void grpc_mdelem_set_user_data(grpc_mdelem *md, void (*destroy_func)(void *), + void *user_data) { + internal_metadata *im = (internal_metadata *)md; + GPR_ASSERT((user_data == NULL) == (destroy_func == NULL)); + if (im->destroy_user_data) { + im->destroy_user_data(im->user_data); + } + im->destroy_user_data = destroy_func; + im->user_data = user_data; +} |