src/core/lib/slice/slice_intern.cc

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