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 #include "src/core/lib/slice/slice_utils.h"
  23
  24 #include <inttypes.h>
  25 #include <string.h>
  26
  27 #include <grpc/support/alloc.h>
  28 #include <grpc/support/log.h>
  29
  30 #include "src/core/lib/gpr/murmur_hash.h"
  31 #include "src/core/lib/gprpp/sync.h"
  32 #include "src/core/lib/iomgr/iomgr_internal.h" /* for iomgr_abort_on_leaks() */
  33 #include "src/core/lib/profiling/timers.h"
  34 #include "src/core/lib/slice/slice_string_helpers.h"
  35 #include "src/core/lib/transport/static_metadata.h"
  36
  37 #define LOG2_SHARD_COUNT 5
  38 #define SHARD_COUNT (1 << LOG2_SHARD_COUNT)
  39 #define INITIAL_SHARD_CAPACITY 8
  40
  41 #define TABLE_IDX(hash, capacity) (((hash) >> LOG2_SHARD_COUNT) % (capacity))
  42 #define SHARD_IDX(hash) ((hash) & ((1 << LOG2_SHARD_COUNT) - 1))
  43
  44 using grpc_core::InternedSliceRefcount;
  45
  46 typedef struct slice_shard {
  47   gpr_mu mu;
  48   InternedSliceRefcount** strs;
  49   size_t count;
  50   size_t capacity;
  51 } slice_shard;
  52
  53 static slice_shard g_shards[SHARD_COUNT];
  54
  55 struct static_metadata_hash_ent {
  56   uint32_t hash;
  57   uint32_t idx;
  58 };
  59 static static_metadata_hash_ent
  60     static_metadata_hash[4 * GRPC_STATIC_MDSTR_COUNT];
  61 static uint32_t max_static_metadata_hash_probe;
  62 uint32_t grpc_static_metadata_hash_values[GRPC_STATIC_MDSTR_COUNT];
  63
  64 namespace grpc_core {
  65
  66 /* hash seed: decided at initialization time */
  67 uint32_t g_hash_seed;
  68 static bool g_forced_hash_seed = false;
  69
  70 InternedSliceRefcount::~InternedSliceRefcount() {
  71   slice_shard* shard = &g_shards[SHARD_IDX(this->hash)];
  72   MutexLock lock(&shard->mu);
  73   InternedSliceRefcount** prev_next;
  74   InternedSliceRefcount* cur;
  75   for (prev_next = &shard->strs[TABLE_IDX(this->hash, shard->capacity)],
  76       cur = *prev_next;
  77        cur != this; prev_next = &cur->bucket_next, cur = cur->bucket_next) {
  78   }
  79   *prev_next = cur->bucket_next;
  80   shard->count--;
  81 }
  82
  83 }  // namespace grpc_core
  84
  85 static void grow_shard(slice_shard* shard) {
  86   GPR_TIMER_SCOPE("grow_strtab", 0);
  87
  88   size_t capacity = shard->capacity * 2;
  89   size_t i;
  90   InternedSliceRefcount** strtab;
  91   InternedSliceRefcount *s, *next;
  92
  93   strtab = static_cast<InternedSliceRefcount**>(
  94       gpr_zalloc(sizeof(InternedSliceRefcount*) * capacity));
  95
  96   for (i = 0; i < shard->capacity; i++) {
  97     for (s = shard->strs[i]; s; s = next) {
  98       size_t idx = TABLE_IDX(s->hash, capacity);
  99       next = s->bucket_next;
 100       s->bucket_next = strtab[idx];
 101       strtab[idx] = s;
 102     }
 103   }
 104   gpr_free(shard->strs);
 105   shard->strs = strtab;
 106   shard->capacity = capacity;
 107 }
 108
 109 grpc_core::InternedSlice::InternedSlice(InternedSliceRefcount* s) {
 110   refcount = &s->base;
 111   data.refcounted.bytes = reinterpret_cast<uint8_t*>(s + 1);
 112   data.refcounted.length = s->length;
 113 }
 114
 115 uint32_t grpc_slice_default_hash_impl(grpc_slice s) {
 116   return gpr_murmur_hash3(GRPC_SLICE_START_PTR(s), GRPC_SLICE_LENGTH(s),
 117                           grpc_core::g_hash_seed);
 118 }
 119
 120 uint32_t grpc_static_slice_hash(grpc_slice s) {
 121   return grpc_static_metadata_hash_values[GRPC_STATIC_METADATA_INDEX(s)];
 122 }
 123
 124 int grpc_static_slice_eq(grpc_slice a, grpc_slice b) {
 125   return GRPC_STATIC_METADATA_INDEX(a) == GRPC_STATIC_METADATA_INDEX(b);
 126 }
 127
 128 uint32_t grpc_slice_hash(grpc_slice s) { return grpc_slice_hash_internal(s); }
 129
 130 grpc_slice grpc_slice_maybe_static_intern(grpc_slice slice,
 131                                           bool* returned_slice_is_different) {
 132   if (GRPC_IS_STATIC_METADATA_STRING(slice)) {
 133     return slice;
 134   }
 135
 136   uint32_t hash = grpc_slice_hash_internal(slice);
 137   for (uint32_t i = 0; i <= max_static_metadata_hash_probe; i++) {
 138     static_metadata_hash_ent ent =
 139         static_metadata_hash[(hash + i) % GPR_ARRAY_SIZE(static_metadata_hash)];
 140     const grpc_core::StaticMetadataSlice* static_slice_table =
 141         grpc_static_slice_table();
 142     if (ent.hash == hash && ent.idx < GRPC_STATIC_MDSTR_COUNT &&
 143         grpc_slice_eq_static_interned(slice, static_slice_table[ent.idx])) {
 144       *returned_slice_is_different = true;
 145       return static_slice_table[ent.idx];
 146     }
 147   }
 148
 149   return slice;
 150 }
 151
 152 grpc_slice grpc_slice_intern(grpc_slice slice) {
 153   /* TODO(arjunroy): At present, this is capable of returning either a static or
 154      an interned slice. This yields weirdness like the constructor for
 155      ManagedMemorySlice instantiating itself as an instance of a derived type
 156      (StaticMetadataSlice or InternedSlice). Should reexamine. */
 157   return grpc_core::ManagedMemorySlice(&slice);
 158 }
 159
 160 // Attempt to see if the provided slice or string matches a static slice.
 161 // SliceArgs is either a const grpc_slice& or const pair<const char*, size_t>&.
 162 // In either case, hash is the pre-computed hash value.
 163 //
 164 // Returns: a matching static slice, or null.
 165 template <typename SliceArgs>
 166 static const grpc_core::StaticMetadataSlice* MatchStaticSlice(
 167     uint32_t hash, const SliceArgs& args) {
 168   for (uint32_t i = 0; i <= max_static_metadata_hash_probe; i++) {
 169     static_metadata_hash_ent ent =
 170         static_metadata_hash[(hash + i) % GPR_ARRAY_SIZE(static_metadata_hash)];
 171     const grpc_core::StaticMetadataSlice* static_slice_table =
 172         grpc_static_slice_table();
 173     if (ent.hash == hash && ent.idx < GRPC_STATIC_MDSTR_COUNT &&
 174         static_slice_table[ent.idx] == args) {
 175       return &static_slice_table[ent.idx];
 176     }
 177   }
 178   return nullptr;
 179 }
 180
 181 // Helper methods to enable us to select appropriately overloaded slice methods
 182 // whether we're dealing with a slice, or a buffer with length, when interning
 183 // strings. Helpers for FindOrCreateInternedSlice().
 184 static const char* GetBuffer(const std::pair<const char*, size_t>& buflen) {
 185   return buflen.first;
 186 }
 187 static size_t GetLength(const std::pair<const char*, size_t>& buflen) {
 188   return buflen.second;
 189 }
 190 static const void* GetBuffer(const grpc_slice& slice) {
 191   return GRPC_SLICE_START_PTR(slice);
 192 }
 193 static size_t GetLength(const grpc_slice& slice) {
 194   return GRPC_SLICE_LENGTH(slice);
 195 }
 196
 197 // Creates an interned slice for a string that does not currently exist in the
 198 // intern table. SliceArgs is either a const grpc_slice& or a const
 199 // pair<const char*, size_t>&. Hash is the pre-computed hash value. We must
 200 // already hold the shard lock. Helper for FindOrCreateInternedSlice().
 201 //
 202 // Returns: a newly interned slice.
 203 template <typename SliceArgs>
 204 static InternedSliceRefcount* InternNewStringLocked(slice_shard* shard,
 205                                                     size_t shard_idx,
 206                                                     uint32_t hash,
 207                                                     const SliceArgs& args) {
 208   /* string data goes after the internal_string header */
 209   size_t len = GetLength(args);
 210   const void* buffer = GetBuffer(args);
 211   InternedSliceRefcount* s =
 212       static_cast<InternedSliceRefcount*>(gpr_malloc(sizeof(*s) + len));
 213   new (s) grpc_core::InternedSliceRefcount(len, hash, shard->strs[shard_idx]);
 214   // TODO(arjunroy): Investigate why hpack tried to intern the nullptr string.
 215   // https://github.com/grpc/grpc/pull/20110#issuecomment-526729282
 216   if (len > 0) {
 217     memcpy(reinterpret_cast<char*>(s + 1), buffer, len);
 218   }
 219   shard->strs[shard_idx] = s;
 220   shard->count++;
 221   if (shard->count > shard->capacity * 2) {
 222     grow_shard(shard);
 223   }
 224   return s;
 225 }
 226
 227 // Attempt to see if the provided slice or string matches an existing interned
 228 // slice. SliceArgs... is either a const grpc_slice& or a string and length. In
 229 // either case, hash is the pre-computed hash value.  We must already hold the
 230 // shard lock. Helper for FindOrCreateInternedSlice().
 231 //
 232 // Returns: a pre-existing matching static slice, or null.
 233 template <typename SliceArgs>
 234 static InternedSliceRefcount* MatchInternedSliceLocked(uint32_t hash,
 235                                                        size_t idx,
 236                                                        const SliceArgs& args) {
 237   InternedSliceRefcount* s;
 238   slice_shard* shard = &g_shards[SHARD_IDX(hash)];
 239   /* search for an existing string */
 240   for (s = shard->strs[idx]; s; s = s->bucket_next) {
 241     if (s->hash == hash && grpc_core::InternedSlice(s) == args) {
 242       if (s->refcnt.RefIfNonZero()) {
 243         return s;
 244       }
 245     }
 246   }
 247   return nullptr;
 248 }
 249
 250 // Attempt to see if the provided slice or string matches an existing interned
 251 // slice, and failing that, create an interned slice with its contents. Returns
 252 // either the existing matching interned slice or the newly created one.
 253 // SliceArgs is either a const grpc_slice& or const pair<const char*, size_t>&.
 254 // In either case, hash is the pre-computed hash value. We do not hold the
 255 // shard lock here, but do take it.
 256 //
 257 // Returns: an interned slice, either pre-existing/matched or newly created.
 258 template <typename SliceArgs>
 259 static InternedSliceRefcount* FindOrCreateInternedSlice(uint32_t hash,
 260                                                         const SliceArgs& args) {
 261   slice_shard* shard = &g_shards[SHARD_IDX(hash)];
 262   gpr_mu_lock(&shard->mu);
 263   const size_t idx = TABLE_IDX(hash, shard->capacity);
 264   InternedSliceRefcount* s = MatchInternedSliceLocked(hash, idx, args);
 265   if (s == nullptr) {
 266     s = InternNewStringLocked(shard, idx, hash, args);
 267   }
 268   gpr_mu_unlock(&shard->mu);
 269   return s;
 270 }
 271
 272 grpc_core::ManagedMemorySlice::ManagedMemorySlice(const char* string)
 273     : grpc_core::ManagedMemorySlice::ManagedMemorySlice(string,
 274                                                         strlen(string)) {}
 275
 276 grpc_core::ManagedMemorySlice::ManagedMemorySlice(const char* string,
 277                                                   size_t len) {
 278   GPR_TIMER_SCOPE("grpc_slice_intern", 0);
 279   const uint32_t hash = gpr_murmur_hash3(string, len, g_hash_seed);
 280   const StaticMetadataSlice* static_slice =
 281       MatchStaticSlice(hash, std::pair<const char*, size_t>(string, len));
 282   if (static_slice) {
 283     *this = *static_slice;
 284   } else {
 285     *this = grpc_core::InternedSlice(FindOrCreateInternedSlice(
 286         hash, std::pair<const char*, size_t>(string, len)));
 287   }
 288 }
 289
 290 grpc_core::ManagedMemorySlice::ManagedMemorySlice(const grpc_slice* slice_ptr) {
 291   GPR_TIMER_SCOPE("grpc_slice_intern", 0);
 292   const grpc_slice& slice = *slice_ptr;
 293   if (GRPC_IS_STATIC_METADATA_STRING(slice)) {
 294     *this = static_cast<const grpc_core::StaticMetadataSlice&>(slice);
 295     return;
 296   }
 297   const uint32_t hash = grpc_slice_hash_internal(slice);
 298   const StaticMetadataSlice* static_slice = MatchStaticSlice(hash, slice);
 299   if (static_slice) {
 300     *this = *static_slice;
 301   } else {
 302     *this = grpc_core::InternedSlice(FindOrCreateInternedSlice(hash, slice));
 303   }
 304 }
 305
 306 void grpc_test_only_set_slice_hash_seed(uint32_t seed) {
 307   grpc_core::g_hash_seed = seed;
 308   grpc_core::g_forced_hash_seed = true;
 309 }
 310
 311 void grpc_slice_intern_init(void) {
 312   if (!grpc_core::g_forced_hash_seed) {
 313     grpc_core::g_hash_seed =
 314         static_cast<uint32_t>(gpr_now(GPR_CLOCK_REALTIME).tv_nsec);
 315   }
 316   for (size_t i = 0; i < SHARD_COUNT; i++) {
 317     slice_shard* shard = &g_shards[i];
 318     gpr_mu_init(&shard->mu);
 319     shard->count = 0;
 320     shard->capacity = INITIAL_SHARD_CAPACITY;
 321     shard->strs = static_cast<InternedSliceRefcount**>(
 322         gpr_zalloc(sizeof(*shard->strs) * shard->capacity));
 323   }
 324   for (size_t i = 0; i < GPR_ARRAY_SIZE(static_metadata_hash); i++) {
 325     static_metadata_hash[i].hash = 0;
 326     static_metadata_hash[i].idx = GRPC_STATIC_MDSTR_COUNT;
 327   }
 328   max_static_metadata_hash_probe = 0;
 329   const grpc_core::StaticMetadataSlice* static_slice_table =
 330       grpc_static_slice_table();
 331   for (size_t i = 0; i < GRPC_STATIC_MDSTR_COUNT; i++) {
 332     grpc_static_metadata_hash_values[i] =
 333         grpc_slice_default_hash_internal(static_slice_table[i]);
 334     for (size_t j = 0; j < GPR_ARRAY_SIZE(static_metadata_hash); j++) {
 335       size_t slot = (grpc_static_metadata_hash_values[i] + j) %
 336                     GPR_ARRAY_SIZE(static_metadata_hash);
 337       if (static_metadata_hash[slot].idx == GRPC_STATIC_MDSTR_COUNT) {
 338         static_metadata_hash[slot].hash = grpc_static_metadata_hash_values[i];
 339         static_metadata_hash[slot].idx = static_cast<uint32_t>(i);
 340         if (j > max_static_metadata_hash_probe) {
 341           max_static_metadata_hash_probe = static_cast<uint32_t>(j);
 342         }
 343         break;
 344       }
 345     }
 346   }
 347   // Handle KV hash for all static mdelems.
 348   for (size_t i = 0; i < GRPC_STATIC_MDELEM_COUNT; ++i) {
 349     grpc_static_mdelem_table()[i].HashInit();
 350   }
 351 }
 352
 353 void grpc_slice_intern_shutdown(void) {
 354   for (size_t i = 0; i < SHARD_COUNT; i++) {
 355     slice_shard* shard = &g_shards[i];
 356     gpr_mu_destroy(&shard->mu);
 357     /* TODO(ctiller): GPR_ASSERT(shard->count == 0); */
 358     if (shard->count != 0) {
 359       gpr_log(GPR_DEBUG, "WARNING: %" PRIuPTR " metadata strings were leaked",
 360               shard->count);
 361       for (size_t j = 0; j < shard->capacity; j++) {
 362         for (InternedSliceRefcount* s = shard->strs[j]; s; s = s->bucket_next) {
 363           char* text = grpc_dump_slice(grpc_core::InternedSlice(s),
 364                                        GPR_DUMP_HEX | GPR_DUMP_ASCII);
 365           gpr_log(GPR_DEBUG, "LEAKED: %s", text);
 366           gpr_free(text);
 367         }
 368       }
 369       if (grpc_iomgr_abort_on_leaks()) {
 370         abort();
 371       }
 372     }
 373     gpr_free(shard->strs);
 374   }
 375 }