• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
interned_slice_ref(void * p)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 
interned_slice_destroy(interned_slice_refcount * s)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 
interned_slice_unref(void * p)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 
interned_slice_sub_ref(void * p)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 
interned_slice_sub_unref(void * p)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 
interned_slice_hash(grpc_slice slice)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 
interned_slice_eq(grpc_slice a,grpc_slice b)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 
grow_shard(slice_shard * shard)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 
materialize(interned_slice_refcount * s)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 
grpc_slice_default_hash_impl(grpc_slice s)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 
grpc_static_slice_hash(grpc_slice s)166 uint32_t grpc_static_slice_hash(grpc_slice s) {
167   return static_metadata_hash_values[GRPC_STATIC_METADATA_INDEX(s)];
168 }
169 
grpc_static_slice_eq(grpc_slice a,grpc_slice b)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 
grpc_slice_hash(grpc_slice s)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 
grpc_slice_maybe_static_intern(grpc_slice slice,bool * returned_slice_is_different)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 
grpc_slice_is_interned(grpc_slice slice)199 bool grpc_slice_is_interned(grpc_slice slice) {
200   return (slice.refcount && slice.refcount->vtable == &interned_slice_vtable) ||
201          GRPC_IS_STATIC_METADATA_STRING(slice);
202 }
203 
grpc_slice_intern(grpc_slice slice)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 
grpc_test_only_set_slice_hash_seed(uint32_t seed)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 
grpc_slice_intern_init(void)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 
grpc_slice_intern_shutdown(void)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 }
333