1 /*
2 *
3 * Copyright 2015 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/transport/metadata.h"
22
23 #include <assert.h>
24 #include <inttypes.h>
25 #include <stddef.h>
26 #include <string.h>
27
28 #include <grpc/compression.h>
29 #include <grpc/grpc.h>
30 #include <grpc/support/alloc.h>
31 #include <grpc/support/atm.h>
32 #include <grpc/support/log.h>
33 #include <grpc/support/string_util.h>
34 #include <grpc/support/time.h>
35
36 #include "src/core/lib/gpr/murmur_hash.h"
37 #include "src/core/lib/gpr/string.h"
38 #include "src/core/lib/iomgr/iomgr_internal.h"
39 #include "src/core/lib/profiling/timers.h"
40 #include "src/core/lib/slice/slice_internal.h"
41 #include "src/core/lib/slice/slice_string_helpers.h"
42 #include "src/core/lib/transport/static_metadata.h"
43
44 /* There are two kinds of mdelem and mdstr instances.
45 * Static instances are declared in static_metadata.{h,c} and
46 * are initialized by grpc_mdctx_global_init().
47 * Dynamic instances are stored in hash tables on grpc_mdctx, and are backed
48 * by internal_string and internal_element structures.
49 * Internal helper functions here-in (is_mdstr_static, is_mdelem_static) are
50 * used to determine which kind of element a pointer refers to.
51 */
52
53 grpc_core::DebugOnlyTraceFlag grpc_trace_metadata(false, "metadata");
54
55 #ifndef NDEBUG
56 #define DEBUG_ARGS , const char *file, int line
57 #define FWD_DEBUG_ARGS , file, line
58 #define REF_MD_LOCKED(shard, s) ref_md_locked((shard), (s), __FILE__, __LINE__)
59 #else
60 #define DEBUG_ARGS
61 #define FWD_DEBUG_ARGS
62 #define REF_MD_LOCKED(shard, s) ref_md_locked((shard), (s))
63 #endif
64
65 #define INITIAL_SHARD_CAPACITY 8
66 #define LOG2_SHARD_COUNT 4
67 #define SHARD_COUNT ((size_t)(1 << LOG2_SHARD_COUNT))
68
69 #define TABLE_IDX(hash, capacity) (((hash) >> (LOG2_SHARD_COUNT)) % (capacity))
70 #define SHARD_IDX(hash) ((hash) & ((1 << (LOG2_SHARD_COUNT)) - 1))
71
72 typedef void (*destroy_user_data_func)(void* user_data);
73
74 /* Shadow structure for grpc_mdelem_data for interned elements */
75 typedef struct interned_metadata {
76 /* must be byte compatible with grpc_mdelem_data */
77 grpc_slice key;
78 grpc_slice value;
79
80 /* private only data */
81 gpr_atm refcnt;
82
83 gpr_mu mu_user_data;
84 gpr_atm destroy_user_data;
85 gpr_atm user_data;
86
87 struct interned_metadata* bucket_next;
88 } interned_metadata;
89
90 /* Shadow structure for grpc_mdelem_data for allocated elements */
91 typedef struct allocated_metadata {
92 /* must be byte compatible with grpc_mdelem_data */
93 grpc_slice key;
94 grpc_slice value;
95
96 /* private only data */
97 gpr_atm refcnt;
98 } allocated_metadata;
99
100 typedef struct mdtab_shard {
101 gpr_mu mu;
102 interned_metadata** elems;
103 size_t count;
104 size_t capacity;
105 /** Estimate of the number of unreferenced mdelems in the hash table.
106 This will eventually converge to the exact number, but it's instantaneous
107 accuracy is not guaranteed */
108 gpr_atm free_estimate;
109 } mdtab_shard;
110
111 static mdtab_shard g_shards[SHARD_COUNT];
112
113 static void gc_mdtab(mdtab_shard* shard);
114
grpc_mdctx_global_init(void)115 void grpc_mdctx_global_init(void) {
116 /* initialize shards */
117 for (size_t i = 0; i < SHARD_COUNT; i++) {
118 mdtab_shard* shard = &g_shards[i];
119 gpr_mu_init(&shard->mu);
120 shard->count = 0;
121 gpr_atm_no_barrier_store(&shard->free_estimate, 0);
122 shard->capacity = INITIAL_SHARD_CAPACITY;
123 shard->elems = static_cast<interned_metadata**>(
124 gpr_zalloc(sizeof(*shard->elems) * shard->capacity));
125 }
126 }
127
grpc_mdctx_global_shutdown()128 void grpc_mdctx_global_shutdown() {
129 for (size_t i = 0; i < SHARD_COUNT; i++) {
130 mdtab_shard* shard = &g_shards[i];
131 gpr_mu_destroy(&shard->mu);
132 gc_mdtab(shard);
133 /* TODO(ctiller): GPR_ASSERT(shard->count == 0); */
134 if (shard->count != 0) {
135 gpr_log(GPR_DEBUG, "WARNING: %" PRIuPTR " metadata elements were leaked",
136 shard->count);
137 if (grpc_iomgr_abort_on_leaks()) {
138 abort();
139 }
140 }
141 gpr_free(shard->elems);
142 }
143 }
144
is_mdelem_static(grpc_mdelem e)145 static int is_mdelem_static(grpc_mdelem e) {
146 return GRPC_MDELEM_DATA(e) >= &grpc_static_mdelem_table[0] &&
147 GRPC_MDELEM_DATA(e) <
148 &grpc_static_mdelem_table[GRPC_STATIC_MDELEM_COUNT];
149 }
150
ref_md_locked(mdtab_shard * shard,interned_metadata * md DEBUG_ARGS)151 static void ref_md_locked(mdtab_shard* shard,
152 interned_metadata* md DEBUG_ARGS) {
153 #ifndef NDEBUG
154 if (grpc_trace_metadata.enabled()) {
155 char* key_str = grpc_slice_to_c_string(md->key);
156 char* value_str = grpc_slice_to_c_string(md->value);
157 gpr_log(file, line, GPR_LOG_SEVERITY_DEBUG,
158 "ELM REF:%p:%" PRIdPTR "->%" PRIdPTR ": '%s' = '%s'", (void*)md,
159 gpr_atm_no_barrier_load(&md->refcnt),
160 gpr_atm_no_barrier_load(&md->refcnt) + 1, key_str, value_str);
161 gpr_free(key_str);
162 gpr_free(value_str);
163 }
164 #endif
165 if (0 == gpr_atm_no_barrier_fetch_add(&md->refcnt, 1)) {
166 gpr_atm_no_barrier_fetch_add(&shard->free_estimate, -1);
167 }
168 }
169
gc_mdtab(mdtab_shard * shard)170 static void gc_mdtab(mdtab_shard* shard) {
171 GPR_TIMER_SCOPE("gc_mdtab", 0);
172
173 size_t i;
174 interned_metadata** prev_next;
175 interned_metadata *md, *next;
176 gpr_atm num_freed = 0;
177
178 for (i = 0; i < shard->capacity; i++) {
179 prev_next = &shard->elems[i];
180 for (md = shard->elems[i]; md; md = next) {
181 void* user_data = (void*)gpr_atm_no_barrier_load(&md->user_data);
182 next = md->bucket_next;
183 if (gpr_atm_acq_load(&md->refcnt) == 0) {
184 grpc_slice_unref_internal(md->key);
185 grpc_slice_unref_internal(md->value);
186 if (md->user_data) {
187 ((destroy_user_data_func)gpr_atm_no_barrier_load(
188 &md->destroy_user_data))(user_data);
189 }
190 gpr_free(md);
191 *prev_next = next;
192 num_freed++;
193 shard->count--;
194 } else {
195 prev_next = &md->bucket_next;
196 }
197 }
198 }
199 gpr_atm_no_barrier_fetch_add(&shard->free_estimate, -num_freed);
200 }
201
grow_mdtab(mdtab_shard * shard)202 static void grow_mdtab(mdtab_shard* shard) {
203 GPR_TIMER_SCOPE("grow_mdtab", 0);
204
205 size_t capacity = shard->capacity * 2;
206 size_t i;
207 interned_metadata** mdtab;
208 interned_metadata *md, *next;
209 uint32_t hash;
210
211 mdtab = static_cast<interned_metadata**>(
212 gpr_zalloc(sizeof(interned_metadata*) * capacity));
213
214 for (i = 0; i < shard->capacity; i++) {
215 for (md = shard->elems[i]; md; md = next) {
216 size_t idx;
217 hash = GRPC_MDSTR_KV_HASH(grpc_slice_hash(md->key),
218 grpc_slice_hash(md->value));
219 next = md->bucket_next;
220 idx = TABLE_IDX(hash, capacity);
221 md->bucket_next = mdtab[idx];
222 mdtab[idx] = md;
223 }
224 }
225 gpr_free(shard->elems);
226 shard->elems = mdtab;
227 shard->capacity = capacity;
228 }
229
rehash_mdtab(mdtab_shard * shard)230 static void rehash_mdtab(mdtab_shard* shard) {
231 if (gpr_atm_no_barrier_load(&shard->free_estimate) >
232 static_cast<gpr_atm>(shard->capacity / 4)) {
233 gc_mdtab(shard);
234 } else {
235 grow_mdtab(shard);
236 }
237 }
238
grpc_mdelem_create(grpc_slice key,grpc_slice value,grpc_mdelem_data * compatible_external_backing_store)239 grpc_mdelem grpc_mdelem_create(
240 grpc_slice key, grpc_slice value,
241 grpc_mdelem_data* compatible_external_backing_store) {
242 if (!grpc_slice_is_interned(key) || !grpc_slice_is_interned(value)) {
243 if (compatible_external_backing_store != nullptr) {
244 return GRPC_MAKE_MDELEM(compatible_external_backing_store,
245 GRPC_MDELEM_STORAGE_EXTERNAL);
246 }
247
248 allocated_metadata* allocated =
249 static_cast<allocated_metadata*>(gpr_malloc(sizeof(*allocated)));
250 allocated->key = grpc_slice_ref_internal(key);
251 allocated->value = grpc_slice_ref_internal(value);
252 gpr_atm_rel_store(&allocated->refcnt, 1);
253 #ifndef NDEBUG
254 if (grpc_trace_metadata.enabled()) {
255 char* key_str = grpc_slice_to_c_string(allocated->key);
256 char* value_str = grpc_slice_to_c_string(allocated->value);
257 gpr_log(GPR_DEBUG, "ELM ALLOC:%p:%" PRIdPTR ": '%s' = '%s'",
258 (void*)allocated, gpr_atm_no_barrier_load(&allocated->refcnt),
259 key_str, value_str);
260 gpr_free(key_str);
261 gpr_free(value_str);
262 }
263 #endif
264 return GRPC_MAKE_MDELEM(allocated, GRPC_MDELEM_STORAGE_ALLOCATED);
265 }
266
267 if (GRPC_IS_STATIC_METADATA_STRING(key) &&
268 GRPC_IS_STATIC_METADATA_STRING(value)) {
269 grpc_mdelem static_elem = grpc_static_mdelem_for_static_strings(
270 GRPC_STATIC_METADATA_INDEX(key), GRPC_STATIC_METADATA_INDEX(value));
271 if (!GRPC_MDISNULL(static_elem)) {
272 return static_elem;
273 }
274 }
275
276 uint32_t hash =
277 GRPC_MDSTR_KV_HASH(grpc_slice_hash(key), grpc_slice_hash(value));
278 interned_metadata* md;
279 mdtab_shard* shard = &g_shards[SHARD_IDX(hash)];
280 size_t idx;
281
282 GPR_TIMER_SCOPE("grpc_mdelem_from_metadata_strings", 0);
283
284 gpr_mu_lock(&shard->mu);
285
286 idx = TABLE_IDX(hash, shard->capacity);
287 /* search for an existing pair */
288 for (md = shard->elems[idx]; md; md = md->bucket_next) {
289 if (grpc_slice_eq(key, md->key) && grpc_slice_eq(value, md->value)) {
290 REF_MD_LOCKED(shard, md);
291 gpr_mu_unlock(&shard->mu);
292 return GRPC_MAKE_MDELEM(md, GRPC_MDELEM_STORAGE_INTERNED);
293 }
294 }
295
296 /* not found: create a new pair */
297 md = static_cast<interned_metadata*>(gpr_malloc(sizeof(interned_metadata)));
298 gpr_atm_rel_store(&md->refcnt, 1);
299 md->key = grpc_slice_ref_internal(key);
300 md->value = grpc_slice_ref_internal(value);
301 md->user_data = 0;
302 md->destroy_user_data = 0;
303 md->bucket_next = shard->elems[idx];
304 shard->elems[idx] = md;
305 gpr_mu_init(&md->mu_user_data);
306 #ifndef NDEBUG
307 if (grpc_trace_metadata.enabled()) {
308 char* key_str = grpc_slice_to_c_string(md->key);
309 char* value_str = grpc_slice_to_c_string(md->value);
310 gpr_log(GPR_DEBUG, "ELM NEW:%p:%" PRIdPTR ": '%s' = '%s'", (void*)md,
311 gpr_atm_no_barrier_load(&md->refcnt), key_str, value_str);
312 gpr_free(key_str);
313 gpr_free(value_str);
314 }
315 #endif
316 shard->count++;
317
318 if (shard->count > shard->capacity * 2) {
319 rehash_mdtab(shard);
320 }
321
322 gpr_mu_unlock(&shard->mu);
323
324 return GRPC_MAKE_MDELEM(md, GRPC_MDELEM_STORAGE_INTERNED);
325 }
326
grpc_mdelem_from_slices(grpc_slice key,grpc_slice value)327 grpc_mdelem grpc_mdelem_from_slices(grpc_slice key, grpc_slice value) {
328 grpc_mdelem out = grpc_mdelem_create(key, value, nullptr);
329 grpc_slice_unref_internal(key);
330 grpc_slice_unref_internal(value);
331 return out;
332 }
333
grpc_mdelem_from_grpc_metadata(grpc_metadata * metadata)334 grpc_mdelem grpc_mdelem_from_grpc_metadata(grpc_metadata* metadata) {
335 bool changed = false;
336 grpc_slice key_slice =
337 grpc_slice_maybe_static_intern(metadata->key, &changed);
338 grpc_slice value_slice =
339 grpc_slice_maybe_static_intern(metadata->value, &changed);
340 return grpc_mdelem_create(
341 key_slice, value_slice,
342 changed ? nullptr : reinterpret_cast<grpc_mdelem_data*>(metadata));
343 }
344
grpc_mdelem_ref(grpc_mdelem gmd DEBUG_ARGS)345 grpc_mdelem grpc_mdelem_ref(grpc_mdelem gmd DEBUG_ARGS) {
346 switch (GRPC_MDELEM_STORAGE(gmd)) {
347 case GRPC_MDELEM_STORAGE_EXTERNAL:
348 case GRPC_MDELEM_STORAGE_STATIC:
349 break;
350 case GRPC_MDELEM_STORAGE_INTERNED: {
351 interned_metadata* md =
352 reinterpret_cast<interned_metadata*> GRPC_MDELEM_DATA(gmd);
353 #ifndef NDEBUG
354 if (grpc_trace_metadata.enabled()) {
355 char* key_str = grpc_slice_to_c_string(md->key);
356 char* value_str = grpc_slice_to_c_string(md->value);
357 gpr_log(file, line, GPR_LOG_SEVERITY_DEBUG,
358 "ELM REF:%p:%" PRIdPTR "->%" PRIdPTR ": '%s' = '%s'",
359 (void*)md, gpr_atm_no_barrier_load(&md->refcnt),
360 gpr_atm_no_barrier_load(&md->refcnt) + 1, key_str, value_str);
361 gpr_free(key_str);
362 gpr_free(value_str);
363 }
364 #endif
365 /* we can assume the ref count is >= 1 as the application is calling
366 this function - meaning that no adjustment to mdtab_free is necessary,
367 simplifying the logic here to be just an atomic increment */
368 /* use C assert to have this removed in opt builds */
369 GPR_ASSERT(gpr_atm_no_barrier_load(&md->refcnt) >= 1);
370 gpr_atm_no_barrier_fetch_add(&md->refcnt, 1);
371 break;
372 }
373 case GRPC_MDELEM_STORAGE_ALLOCATED: {
374 allocated_metadata* md =
375 reinterpret_cast<allocated_metadata*> GRPC_MDELEM_DATA(gmd);
376 #ifndef NDEBUG
377 if (grpc_trace_metadata.enabled()) {
378 char* key_str = grpc_slice_to_c_string(md->key);
379 char* value_str = grpc_slice_to_c_string(md->value);
380 gpr_log(file, line, GPR_LOG_SEVERITY_DEBUG,
381 "ELM REF:%p:%" PRIdPTR "->%" PRIdPTR ": '%s' = '%s'",
382 (void*)md, gpr_atm_no_barrier_load(&md->refcnt),
383 gpr_atm_no_barrier_load(&md->refcnt) + 1, key_str, value_str);
384 gpr_free(key_str);
385 gpr_free(value_str);
386 }
387 #endif
388 /* we can assume the ref count is >= 1 as the application is calling
389 this function - meaning that no adjustment to mdtab_free is necessary,
390 simplifying the logic here to be just an atomic increment */
391 /* use C assert to have this removed in opt builds */
392 gpr_atm_no_barrier_fetch_add(&md->refcnt, 1);
393 break;
394 }
395 }
396 return gmd;
397 }
398
grpc_mdelem_unref(grpc_mdelem gmd DEBUG_ARGS)399 void grpc_mdelem_unref(grpc_mdelem gmd DEBUG_ARGS) {
400 switch (GRPC_MDELEM_STORAGE(gmd)) {
401 case GRPC_MDELEM_STORAGE_EXTERNAL:
402 case GRPC_MDELEM_STORAGE_STATIC:
403 break;
404 case GRPC_MDELEM_STORAGE_INTERNED: {
405 interned_metadata* md =
406 reinterpret_cast<interned_metadata*> GRPC_MDELEM_DATA(gmd);
407 #ifndef NDEBUG
408 if (grpc_trace_metadata.enabled()) {
409 char* key_str = grpc_slice_to_c_string(md->key);
410 char* value_str = grpc_slice_to_c_string(md->value);
411 gpr_log(file, line, GPR_LOG_SEVERITY_DEBUG,
412 "ELM UNREF:%p:%" PRIdPTR "->%" PRIdPTR ": '%s' = '%s'",
413 (void*)md, gpr_atm_no_barrier_load(&md->refcnt),
414 gpr_atm_no_barrier_load(&md->refcnt) - 1, key_str, value_str);
415 gpr_free(key_str);
416 gpr_free(value_str);
417 }
418 #endif
419 uint32_t hash = GRPC_MDSTR_KV_HASH(grpc_slice_hash(md->key),
420 grpc_slice_hash(md->value));
421 const gpr_atm prev_refcount = gpr_atm_full_fetch_add(&md->refcnt, -1);
422 GPR_ASSERT(prev_refcount >= 1);
423 if (1 == prev_refcount) {
424 /* once the refcount hits zero, some other thread can come along and
425 free md at any time: it's unsafe from this point on to access it */
426 mdtab_shard* shard = &g_shards[SHARD_IDX(hash)];
427 gpr_atm_no_barrier_fetch_add(&shard->free_estimate, 1);
428 }
429 break;
430 }
431 case GRPC_MDELEM_STORAGE_ALLOCATED: {
432 allocated_metadata* md =
433 reinterpret_cast<allocated_metadata*> GRPC_MDELEM_DATA(gmd);
434 #ifndef NDEBUG
435 if (grpc_trace_metadata.enabled()) {
436 char* key_str = grpc_slice_to_c_string(md->key);
437 char* value_str = grpc_slice_to_c_string(md->value);
438 gpr_log(file, line, GPR_LOG_SEVERITY_DEBUG,
439 "ELM UNREF:%p:%" PRIdPTR "->%" PRIdPTR ": '%s' = '%s'",
440 (void*)md, gpr_atm_no_barrier_load(&md->refcnt),
441 gpr_atm_no_barrier_load(&md->refcnt) - 1, key_str, value_str);
442 gpr_free(key_str);
443 gpr_free(value_str);
444 }
445 #endif
446 const gpr_atm prev_refcount = gpr_atm_full_fetch_add(&md->refcnt, -1);
447 GPR_ASSERT(prev_refcount >= 1);
448 if (1 == prev_refcount) {
449 grpc_slice_unref_internal(md->key);
450 grpc_slice_unref_internal(md->value);
451 gpr_free(md);
452 }
453 break;
454 }
455 }
456 }
457
grpc_mdelem_get_user_data(grpc_mdelem md,void (* destroy_func)(void *))458 void* grpc_mdelem_get_user_data(grpc_mdelem md, void (*destroy_func)(void*)) {
459 switch (GRPC_MDELEM_STORAGE(md)) {
460 case GRPC_MDELEM_STORAGE_EXTERNAL:
461 case GRPC_MDELEM_STORAGE_ALLOCATED:
462 return nullptr;
463 case GRPC_MDELEM_STORAGE_STATIC:
464 return (void*)grpc_static_mdelem_user_data[GRPC_MDELEM_DATA(md) -
465 grpc_static_mdelem_table];
466 case GRPC_MDELEM_STORAGE_INTERNED: {
467 interned_metadata* im =
468 reinterpret_cast<interned_metadata*> GRPC_MDELEM_DATA(md);
469 void* result;
470 if (gpr_atm_acq_load(&im->destroy_user_data) == (gpr_atm)destroy_func) {
471 return (void*)gpr_atm_no_barrier_load(&im->user_data);
472 } else {
473 return nullptr;
474 }
475 return result;
476 }
477 }
478 GPR_UNREACHABLE_CODE(return nullptr);
479 }
480
grpc_mdelem_set_user_data(grpc_mdelem md,void (* destroy_func)(void *),void * user_data)481 void* grpc_mdelem_set_user_data(grpc_mdelem md, void (*destroy_func)(void*),
482 void* user_data) {
483 switch (GRPC_MDELEM_STORAGE(md)) {
484 case GRPC_MDELEM_STORAGE_EXTERNAL:
485 case GRPC_MDELEM_STORAGE_ALLOCATED:
486 destroy_func(user_data);
487 return nullptr;
488 case GRPC_MDELEM_STORAGE_STATIC:
489 destroy_func(user_data);
490 return (void*)grpc_static_mdelem_user_data[GRPC_MDELEM_DATA(md) -
491 grpc_static_mdelem_table];
492 case GRPC_MDELEM_STORAGE_INTERNED: {
493 interned_metadata* im =
494 reinterpret_cast<interned_metadata*> GRPC_MDELEM_DATA(md);
495 GPR_ASSERT(!is_mdelem_static(md));
496 GPR_ASSERT((user_data == nullptr) == (destroy_func == nullptr));
497 gpr_mu_lock(&im->mu_user_data);
498 if (gpr_atm_no_barrier_load(&im->destroy_user_data)) {
499 /* user data can only be set once */
500 gpr_mu_unlock(&im->mu_user_data);
501 if (destroy_func != nullptr) {
502 destroy_func(user_data);
503 }
504 return (void*)gpr_atm_no_barrier_load(&im->user_data);
505 }
506 gpr_atm_no_barrier_store(&im->user_data, (gpr_atm)user_data);
507 gpr_atm_rel_store(&im->destroy_user_data, (gpr_atm)destroy_func);
508 gpr_mu_unlock(&im->mu_user_data);
509 return user_data;
510 }
511 }
512 GPR_UNREACHABLE_CODE(return nullptr);
513 }
514
grpc_mdelem_eq(grpc_mdelem a,grpc_mdelem b)515 bool grpc_mdelem_eq(grpc_mdelem a, grpc_mdelem b) {
516 if (a.payload == b.payload) return true;
517 if (GRPC_MDELEM_IS_INTERNED(a) && GRPC_MDELEM_IS_INTERNED(b)) return false;
518 if (GRPC_MDISNULL(a) || GRPC_MDISNULL(b)) return false;
519 return grpc_slice_eq(GRPC_MDKEY(a), GRPC_MDKEY(b)) &&
520 grpc_slice_eq(GRPC_MDVALUE(a), GRPC_MDVALUE(b));
521 }
522