Revert "Revert "Metadata handling rewrite""

This reverts commit 5e01e2ac977655aa074faf7fde0a74298f5e4c55.

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 */