Line data Source code
1 : /*
2 : *
3 : * Copyright 2015, Google Inc.
4 : * All rights reserved.
5 : *
6 : * Redistribution and use in source and binary forms, with or without
7 : * modification, are permitted provided that the following conditions are
8 : * met:
9 : *
10 : * * Redistributions of source code must retain the above copyright
11 : * notice, this list of conditions and the following disclaimer.
12 : * * Redistributions in binary form must reproduce the above
13 : * copyright notice, this list of conditions and the following disclaimer
14 : * in the documentation and/or other materials provided with the
15 : * distribution.
16 : * * Neither the name of Google Inc. nor the names of its
17 : * contributors may be used to endorse or promote products derived from
18 : * this software without specific prior written permission.
19 : *
20 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 : * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 : * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 : * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 : * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 : * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 : * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 : *
32 : */
33 :
34 : #include "src/core/transport/metadata.h"
35 :
36 : #include <assert.h>
37 : #include <stddef.h>
38 : #include <string.h>
39 :
40 : #include <grpc/compression.h>
41 : #include <grpc/support/alloc.h>
42 : #include <grpc/support/atm.h>
43 : #include <grpc/support/log.h>
44 : #include <grpc/support/string_util.h>
45 : #include <grpc/support/time.h>
46 : #include "src/core/profiling/timers.h"
47 : #include "src/core/support/murmur_hash.h"
48 : #include "src/core/support/string.h"
49 : #include "src/core/transport/chttp2/bin_encoder.h"
50 : #include "src/core/transport/static_metadata.h"
51 :
52 : /* There are two kinds of mdelem and mdstr instances.
53 : * Static instances are declared in static_metadata.{h,c} and
54 : * are initialized by grpc_mdctx_global_init().
55 : * Dynamic instances are stored in hash tables on grpc_mdctx, and are backed
56 : * by internal_string and internal_element structures.
57 : * Internal helper functions here-in (is_mdstr_static, is_mdelem_static) are
58 : * used to determine which kind of element a pointer refers to.
59 : */
60 :
61 : #define INITIAL_STRTAB_CAPACITY 4
62 : #define INITIAL_MDTAB_CAPACITY 4
63 :
64 : #ifdef GRPC_METADATA_REFCOUNT_DEBUG
65 : #define DEBUG_ARGS , const char *file, int line
66 : #define FWD_DEBUG_ARGS , file, line
67 : #define REF_MD_LOCKED(shard, s) ref_md_locked((shard), (s), __FILE__, __LINE__)
68 : #else
69 : #define DEBUG_ARGS
70 : #define FWD_DEBUG_ARGS
71 : #define REF_MD_LOCKED(shard, s) ref_md_locked((shard), (s))
72 : #endif
73 :
74 : #define TABLE_IDX(hash, log2_shards, capacity) \
75 : (((hash) >> (log2_shards)) % (capacity))
76 : #define SHARD_IDX(hash, log2_shards) ((hash) & ((1 << (log2_shards)) - 1))
77 :
78 : typedef void (*destroy_user_data_func)(void *user_data);
79 :
80 : /* Shadow structure for grpc_mdstr for non-static values */
81 : typedef struct internal_string {
82 : /* must be byte compatible with grpc_mdstr */
83 : gpr_slice slice;
84 : gpr_uint32 hash;
85 :
86 : /* private only data */
87 : gpr_atm refcnt;
88 :
89 : gpr_uint8 has_base64_and_huffman_encoded;
90 : gpr_slice_refcount refcount;
91 :
92 : gpr_slice base64_and_huffman;
93 :
94 : struct internal_string *bucket_next;
95 : } internal_string;
96 :
97 : /* Shadow structure for grpc_mdelem for non-static elements */
98 : typedef struct internal_metadata {
99 : /* must be byte compatible with grpc_mdelem */
100 : internal_string *key;
101 : internal_string *value;
102 :
103 : /* private only data */
104 : gpr_atm refcnt;
105 :
106 : gpr_mu mu_user_data;
107 : gpr_atm destroy_user_data;
108 : gpr_atm user_data;
109 :
110 : struct internal_metadata *bucket_next;
111 : } internal_metadata;
112 :
113 : typedef struct strtab_shard {
114 : gpr_mu mu;
115 : internal_string **strs;
116 : size_t count;
117 : size_t capacity;
118 : } strtab_shard;
119 :
120 : typedef struct mdtab_shard {
121 : gpr_mu mu;
122 : internal_metadata **elems;
123 : size_t count;
124 : size_t capacity;
125 : size_t free;
126 : } mdtab_shard;
127 :
128 : #define LOG2_STRTAB_SHARD_COUNT 5
129 : #define LOG2_MDTAB_SHARD_COUNT 4
130 : #define STRTAB_SHARD_COUNT ((size_t)(1 << LOG2_STRTAB_SHARD_COUNT))
131 : #define MDTAB_SHARD_COUNT ((size_t)(1 << LOG2_MDTAB_SHARD_COUNT))
132 :
133 : /* hash seed: decided at initialization time */
134 : static gpr_uint32 g_hash_seed;
135 : static int g_forced_hash_seed = 0;
136 :
137 : /* linearly probed hash tables for static element lookup */
138 : static grpc_mdstr *g_static_strtab[GRPC_STATIC_MDSTR_COUNT * 2];
139 : static grpc_mdelem *g_static_mdtab[GRPC_STATIC_MDELEM_COUNT * 2];
140 : static size_t g_static_strtab_maxprobe;
141 : static size_t g_static_mdtab_maxprobe;
142 :
143 : static strtab_shard g_strtab_shard[STRTAB_SHARD_COUNT];
144 : static mdtab_shard g_mdtab_shard[MDTAB_SHARD_COUNT];
145 :
146 : static void gc_mdtab(mdtab_shard *shard);
147 :
148 1 : void grpc_test_only_set_metadata_hash_seed(gpr_uint32 seed) {
149 1 : g_hash_seed = seed;
150 1 : g_forced_hash_seed = 1;
151 1 : }
152 :
153 3452 : void grpc_mdctx_global_init(void) {
154 : size_t i, j;
155 3452 : if (!g_forced_hash_seed) {
156 3451 : g_hash_seed = (gpr_uint32)gpr_now(GPR_CLOCK_REALTIME).tv_nsec;
157 : }
158 3452 : g_static_strtab_maxprobe = 0;
159 3452 : g_static_mdtab_maxprobe = 0;
160 : /* build static tables */
161 3452 : memset(g_static_mdtab, 0, sizeof(g_static_mdtab));
162 3452 : memset(g_static_strtab, 0, sizeof(g_static_strtab));
163 303776 : for (i = 0; i < GRPC_STATIC_MDSTR_COUNT; i++) {
164 300237 : grpc_mdstr *elem = &grpc_static_mdstr_table[i];
165 300324 : const char *str = grpc_static_metadata_strings[i];
166 300324 : gpr_uint32 hash = gpr_murmur_hash3(str, strlen(str), g_hash_seed);
167 300324 : *(gpr_slice *)&elem->slice = gpr_slice_from_static_string(str);
168 300324 : *(gpr_uint32 *)&elem->hash = hash;
169 443242 : for (j = 0;; j++) {
170 443329 : size_t idx = (hash + j) % GPR_ARRAY_SIZE(g_static_strtab);
171 443329 : if (g_static_strtab[idx] == NULL) {
172 300324 : g_static_strtab[idx] = &grpc_static_mdstr_table[i];
173 300237 : break;
174 : }
175 143005 : }
176 300324 : if (j > g_static_strtab_maxprobe) {
177 13079 : g_static_strtab_maxprobe = j;
178 : }
179 : }
180 272707 : for (i = 0; i < GRPC_STATIC_MDELEM_COUNT; i++) {
181 269256 : grpc_mdelem *elem = &grpc_static_mdelem_table[i];
182 269256 : grpc_mdstr *key =
183 269256 : &grpc_static_mdstr_table[grpc_static_metadata_elem_indices[2 * i + 0]];
184 269256 : grpc_mdstr *value =
185 269256 : &grpc_static_mdstr_table[grpc_static_metadata_elem_indices[2 * i + 1]];
186 269256 : gpr_uint32 hash = GRPC_MDSTR_KV_HASH(key->hash, value->hash);
187 269256 : *(grpc_mdstr **)&elem->key = key;
188 269256 : *(grpc_mdstr **)&elem->value = value;
189 397711 : for (j = 0;; j++) {
190 397789 : size_t idx = (hash + j) % GPR_ARRAY_SIZE(g_static_mdtab);
191 397789 : if (g_static_mdtab[idx] == NULL) {
192 269256 : g_static_mdtab[idx] = elem;
193 269178 : break;
194 : }
195 128533 : }
196 269256 : if (j > g_static_mdtab_maxprobe) {
197 12649 : g_static_mdtab_maxprobe = j;
198 : }
199 : }
200 : /* initialize shards */
201 113915 : for (i = 0; i < STRTAB_SHARD_COUNT; i++) {
202 110432 : strtab_shard *shard = &g_strtab_shard[i];
203 110464 : gpr_mu_init(&shard->mu);
204 110464 : shard->count = 0;
205 110464 : shard->capacity = INITIAL_STRTAB_CAPACITY;
206 110464 : shard->strs = gpr_malloc(sizeof(*shard->strs) * shard->capacity);
207 110464 : memset(shard->strs, 0, sizeof(*shard->strs) * shard->capacity);
208 : }
209 58683 : for (i = 0; i < MDTAB_SHARD_COUNT; i++) {
210 55216 : mdtab_shard *shard = &g_mdtab_shard[i];
211 55232 : gpr_mu_init(&shard->mu);
212 55232 : shard->count = 0;
213 55232 : shard->free = 0;
214 55232 : shard->capacity = INITIAL_MDTAB_CAPACITY;
215 55232 : shard->elems = gpr_malloc(sizeof(*shard->elems) * shard->capacity);
216 55232 : memset(shard->elems, 0, sizeof(*shard->elems) * shard->capacity);
217 : }
218 3452 : }
219 :
220 3450 : void grpc_mdctx_global_shutdown(void) {
221 : size_t i;
222 58650 : for (i = 0; i < MDTAB_SHARD_COUNT; i++) {
223 55200 : mdtab_shard *shard = &g_mdtab_shard[i];
224 55200 : gpr_mu_destroy(&shard->mu);
225 55200 : gc_mdtab(shard);
226 : /* TODO(ctiller): GPR_ASSERT(shard->count == 0); */
227 55200 : if (shard->count != 0) {
228 40 : gpr_log(GPR_DEBUG, "WARNING: %d metadata elements were leaked",
229 : shard->count);
230 : }
231 55200 : gpr_free(shard->elems);
232 : }
233 113850 : for (i = 0; i < STRTAB_SHARD_COUNT; i++) {
234 110400 : strtab_shard *shard = &g_strtab_shard[i];
235 110400 : gpr_mu_destroy(&shard->mu);
236 : /* TODO(ctiller): GPR_ASSERT(shard->count == 0); */
237 110400 : if (shard->count != 0) {
238 46 : gpr_log(GPR_DEBUG, "WARNING: %d metadata strings were leaked",
239 : shard->count);
240 : }
241 110400 : gpr_free(shard->strs);
242 : }
243 3450 : }
244 :
245 58900763 : static int is_mdstr_static(grpc_mdstr *s) {
246 58915824 : return s >= &grpc_static_mdstr_table[0] &&
247 : s < &grpc_static_mdstr_table[GRPC_STATIC_MDSTR_COUNT];
248 : }
249 :
250 129403276 : static int is_mdelem_static(grpc_mdelem *e) {
251 129410320 : return e >= &grpc_static_mdelem_table[0] &&
252 : e < &grpc_static_mdelem_table[GRPC_STATIC_MDELEM_COUNT];
253 : }
254 :
255 6882595 : static void ref_md_locked(mdtab_shard *shard,
256 : internal_metadata *md DEBUG_ARGS) {
257 : #ifdef GRPC_METADATA_REFCOUNT_DEBUG
258 : gpr_log(file, line, GPR_LOG_SEVERITY_DEBUG,
259 : "ELM REF:%p:%d->%d: '%s' = '%s'", md,
260 : gpr_atm_no_barrier_load(&md->refcnt),
261 : gpr_atm_no_barrier_load(&md->refcnt) + 1,
262 : grpc_mdstr_as_c_string((grpc_mdstr *)md->key),
263 : grpc_mdstr_as_c_string((grpc_mdstr *)md->value));
264 : #endif
265 6882595 : if (0 == gpr_atm_no_barrier_fetch_add(&md->refcnt, 2)) {
266 613449 : shard->free--;
267 : } else {
268 6269146 : GPR_ASSERT(1 != gpr_atm_no_barrier_fetch_add(&md->refcnt, -1));
269 : }
270 6882595 : }
271 :
272 433 : static void grow_strtab(strtab_shard *shard) {
273 433 : size_t capacity = shard->capacity * 2;
274 : size_t i;
275 : internal_string **strtab;
276 : internal_string *s, *next;
277 :
278 : GPR_TIMER_BEGIN("grow_strtab", 0);
279 :
280 433 : strtab = gpr_malloc(sizeof(internal_string *) * capacity);
281 433 : memset(strtab, 0, sizeof(internal_string *) * capacity);
282 :
283 10281 : for (i = 0; i < shard->capacity; i++) {
284 29977 : for (s = shard->strs[i]; s; s = next) {
285 20129 : size_t idx = TABLE_IDX(s->hash, LOG2_STRTAB_SHARD_COUNT, capacity);
286 20129 : next = s->bucket_next;
287 20129 : s->bucket_next = strtab[idx];
288 20129 : strtab[idx] = s;
289 : }
290 : }
291 :
292 433 : gpr_free(shard->strs);
293 433 : shard->strs = strtab;
294 433 : shard->capacity = capacity;
295 :
296 : GPR_TIMER_END("grow_strtab", 0);
297 433 : }
298 :
299 2488764 : static void internal_destroy_string(strtab_shard *shard, internal_string *is) {
300 : internal_string **prev_next;
301 : internal_string *cur;
302 : GPR_TIMER_BEGIN("internal_destroy_string", 0);
303 2488764 : if (is->has_base64_and_huffman_encoded) {
304 108 : gpr_slice_unref(is->base64_and_huffman);
305 : }
306 8436895 : for (prev_next = &shard->strs[TABLE_IDX(is->hash, LOG2_STRTAB_SHARD_COUNT,
307 : shard->capacity)],
308 2488764 : cur = *prev_next;
309 970603 : cur != is; prev_next = &cur->bucket_next, cur = cur->bucket_next)
310 : ;
311 2488764 : *prev_next = cur->bucket_next;
312 2488764 : shard->count--;
313 2488764 : gpr_free(is);
314 : GPR_TIMER_END("internal_destroy_string", 0);
315 2488764 : }
316 :
317 1285421 : static void slice_ref(void *p) {
318 1285421 : internal_string *is =
319 : (internal_string *)((char *)p - offsetof(internal_string, refcount));
320 1285421 : GRPC_MDSTR_REF((grpc_mdstr *)(is));
321 1285421 : }
322 :
323 1285421 : static void slice_unref(void *p) {
324 1285421 : internal_string *is =
325 : (internal_string *)((char *)p - offsetof(internal_string, refcount));
326 1285421 : GRPC_MDSTR_UNREF((grpc_mdstr *)(is));
327 1285421 : }
328 :
329 8245962 : grpc_mdstr *grpc_mdstr_from_string(const char *str) {
330 8245962 : return grpc_mdstr_from_buffer((const gpr_uint8 *)str, strlen(str));
331 : }
332 :
333 52522 : grpc_mdstr *grpc_mdstr_from_slice(gpr_slice slice) {
334 78710 : grpc_mdstr *result = grpc_mdstr_from_buffer(GPR_SLICE_START_PTR(slice),
335 78710 : GPR_SLICE_LENGTH(slice));
336 52522 : gpr_slice_unref(slice);
337 52522 : return result;
338 : }
339 :
340 17902017 : grpc_mdstr *grpc_mdstr_from_buffer(const gpr_uint8 *buf, size_t length) {
341 17902017 : gpr_uint32 hash = gpr_murmur_hash3(buf, length, g_hash_seed);
342 : internal_string *s;
343 17903211 : strtab_shard *shard =
344 17903211 : &g_strtab_shard[SHARD_IDX(hash, LOG2_STRTAB_SHARD_COUNT)];
345 : size_t i;
346 : size_t idx;
347 :
348 : GPR_TIMER_BEGIN("grpc_mdstr_from_buffer", 0);
349 :
350 : /* search for a static string */
351 36467907 : for (i = 0; i <= g_static_strtab_maxprobe; i++) {
352 : grpc_mdstr *ss;
353 35707699 : idx = (hash + i) % GPR_ARRAY_SIZE(g_static_strtab);
354 35707699 : ss = g_static_strtab[idx];
355 35707699 : if (ss == NULL) break;
356 29567453 : if (ss->hash == hash && GPR_SLICE_LENGTH(ss->slice) == length &&
357 5501264 : 0 == memcmp(buf, GPR_SLICE_START_PTR(ss->slice), length)) {
358 : GPR_TIMER_END("grpc_mdstr_from_buffer", 0);
359 5501493 : return ss;
360 : }
361 : }
362 :
363 12401718 : gpr_mu_lock(&shard->mu);
364 :
365 : /* search for an existing string */
366 12402214 : idx = TABLE_IDX(hash, LOG2_STRTAB_SHARD_COUNT, shard->capacity);
367 19077010 : for (s = shard->strs[idx]; s; s = s->bucket_next) {
368 26501238 : if (s->hash == hash && GPR_SLICE_LENGTH(s->slice) == length &&
369 9913221 : 0 == memcmp(buf, GPR_SLICE_START_PTR(s->slice), length)) {
370 9913221 : GRPC_MDSTR_REF((grpc_mdstr *)s);
371 9913221 : gpr_mu_unlock(&shard->mu);
372 : GPR_TIMER_END("grpc_mdstr_from_buffer", 0);
373 9913221 : return (grpc_mdstr *)s;
374 : }
375 : }
376 :
377 : /* not found: create a new string */
378 2488993 : if (length + 1 < GPR_SLICE_INLINED_SIZE) {
379 : /* string data goes directly into the slice */
380 2478268 : s = gpr_malloc(sizeof(internal_string));
381 2478268 : gpr_atm_rel_store(&s->refcnt, 2);
382 2478268 : s->slice.refcount = NULL;
383 2478268 : memcpy(s->slice.data.inlined.bytes, buf, length);
384 2478268 : s->slice.data.inlined.bytes[length] = 0;
385 2478268 : s->slice.data.inlined.length = (gpr_uint8)length;
386 : } else {
387 : /* string data goes after the internal_string header, and we +1 for null
388 : terminator */
389 10725 : s = gpr_malloc(sizeof(internal_string) + length + 1);
390 10725 : gpr_atm_rel_store(&s->refcnt, 2);
391 10725 : s->refcount.ref = slice_ref;
392 10725 : s->refcount.unref = slice_unref;
393 10725 : s->slice.refcount = &s->refcount;
394 10725 : s->slice.data.refcounted.bytes = (gpr_uint8 *)(s + 1);
395 10725 : s->slice.data.refcounted.length = length;
396 10725 : memcpy(s->slice.data.refcounted.bytes, buf, length);
397 : /* add a null terminator for cheap c string conversion when desired */
398 10725 : s->slice.data.refcounted.bytes[length] = 0;
399 : }
400 2488993 : s->has_base64_and_huffman_encoded = 0;
401 2488993 : s->hash = hash;
402 2488993 : s->bucket_next = shard->strs[idx];
403 2488993 : shard->strs[idx] = s;
404 :
405 2488993 : shard->count++;
406 :
407 2488993 : if (shard->count > shard->capacity * 2) {
408 433 : grow_strtab(shard);
409 : }
410 :
411 2488993 : gpr_mu_unlock(&shard->mu);
412 : GPR_TIMER_END("grpc_mdstr_from_buffer", 0);
413 :
414 2488993 : return (grpc_mdstr *)s;
415 : }
416 :
417 180863 : static void gc_mdtab(mdtab_shard *shard) {
418 : size_t i;
419 : internal_metadata **prev_next;
420 : internal_metadata *md, *next;
421 :
422 : GPR_TIMER_BEGIN("gc_mdtab", 0);
423 1364531 : for (i = 0; i < shard->capacity; i++) {
424 1183668 : prev_next = &shard->elems[i];
425 3237940 : for (md = shard->elems[i]; md; md = next) {
426 2054272 : void *user_data = (void *)gpr_atm_no_barrier_load(&md->user_data);
427 2054272 : next = md->bucket_next;
428 2054272 : if (gpr_atm_acq_load(&md->refcnt) == 0) {
429 1485648 : GRPC_MDSTR_UNREF((grpc_mdstr *)md->key);
430 1485648 : GRPC_MDSTR_UNREF((grpc_mdstr *)md->value);
431 1485648 : if (md->user_data) {
432 1621 : ((destroy_user_data_func)gpr_atm_no_barrier_load(
433 : &md->destroy_user_data))(user_data);
434 : }
435 1485648 : gpr_free(md);
436 1485648 : *prev_next = next;
437 1485648 : shard->free--;
438 1485648 : shard->count--;
439 : } else {
440 568624 : prev_next = &md->bucket_next;
441 : }
442 : }
443 : }
444 : GPR_TIMER_END("gc_mdtab", 0);
445 180863 : }
446 :
447 182 : static void grow_mdtab(mdtab_shard *shard) {
448 182 : size_t capacity = shard->capacity * 2;
449 : size_t i;
450 : internal_metadata **mdtab;
451 : internal_metadata *md, *next;
452 : gpr_uint32 hash;
453 :
454 : GPR_TIMER_BEGIN("grow_mdtab", 0);
455 :
456 182 : mdtab = gpr_malloc(sizeof(internal_metadata *) * capacity);
457 182 : memset(mdtab, 0, sizeof(internal_metadata *) * capacity);
458 :
459 8652 : for (i = 0; i < shard->capacity; i++) {
460 25606 : for (md = shard->elems[i]; md; md = next) {
461 : size_t idx;
462 17126 : hash = GRPC_MDSTR_KV_HASH(md->key->hash, md->value->hash);
463 17126 : next = md->bucket_next;
464 17126 : idx = TABLE_IDX(hash, LOG2_MDTAB_SHARD_COUNT, capacity);
465 17126 : md->bucket_next = mdtab[idx];
466 17126 : mdtab[idx] = md;
467 : }
468 : }
469 :
470 182 : gpr_free(shard->elems);
471 182 : shard->elems = mdtab;
472 182 : shard->capacity = capacity;
473 :
474 : GPR_TIMER_END("grow_mdtab", 0);
475 182 : }
476 :
477 125845 : static void rehash_mdtab(mdtab_shard *shard) {
478 125845 : if (shard->free > shard->capacity / 4) {
479 125663 : gc_mdtab(shard);
480 : } else {
481 182 : grow_mdtab(shard);
482 : }
483 125845 : }
484 :
485 10522552 : grpc_mdelem *grpc_mdelem_from_metadata_strings(grpc_mdstr *mkey,
486 : grpc_mdstr *mvalue) {
487 10516601 : internal_string *key = (internal_string *)mkey;
488 10516601 : internal_string *value = (internal_string *)mvalue;
489 10522552 : gpr_uint32 hash = GRPC_MDSTR_KV_HASH(mkey->hash, mvalue->hash);
490 : internal_metadata *md;
491 10522552 : mdtab_shard *shard = &g_mdtab_shard[SHARD_IDX(hash, LOG2_MDTAB_SHARD_COUNT)];
492 : size_t i;
493 : size_t idx;
494 :
495 : GPR_TIMER_BEGIN("grpc_mdelem_from_metadata_strings", 0);
496 :
497 10528414 : if (is_mdstr_static(mkey) && is_mdstr_static(mvalue)) {
498 2919343 : for (i = 0; i <= g_static_mdtab_maxprobe; i++) {
499 : grpc_mdelem *smd;
500 2924462 : idx = (hash + i) % GPR_ARRAY_SIZE(g_static_mdtab);
501 2924462 : smd = g_static_mdtab[idx];
502 2924462 : if (smd == NULL) break;
503 2924056 : if (smd->key == mkey && smd->value == mvalue) {
504 : GPR_TIMER_END("grpc_mdelem_from_metadata_strings", 0);
505 2153988 : return smd;
506 : }
507 : }
508 : }
509 :
510 8368500 : gpr_mu_lock(&shard->mu);
511 :
512 8368456 : idx = TABLE_IDX(hash, LOG2_MDTAB_SHARD_COUNT, shard->capacity);
513 : /* search for an existing pair */
514 17615126 : for (md = shard->elems[idx]; md; md = md->bucket_next) {
515 16129265 : if (md->key == key && md->value == value) {
516 6882595 : REF_MD_LOCKED(shard, md);
517 6882595 : GRPC_MDSTR_UNREF((grpc_mdstr *)key);
518 6882595 : GRPC_MDSTR_UNREF((grpc_mdstr *)value);
519 6882595 : gpr_mu_unlock(&shard->mu);
520 : GPR_TIMER_END("grpc_mdelem_from_metadata_strings", 0);
521 6882595 : return (grpc_mdelem *)md;
522 : }
523 : }
524 :
525 : /* not found: create a new pair */
526 1485861 : md = gpr_malloc(sizeof(internal_metadata));
527 1485861 : gpr_atm_rel_store(&md->refcnt, 2);
528 1485861 : md->key = key;
529 1485861 : md->value = value;
530 1485861 : md->user_data = 0;
531 1485861 : md->destroy_user_data = 0;
532 1485861 : md->bucket_next = shard->elems[idx];
533 1485861 : shard->elems[idx] = md;
534 1485861 : gpr_mu_init(&md->mu_user_data);
535 : #ifdef GRPC_METADATA_REFCOUNT_DEBUG
536 : gpr_log(GPR_DEBUG, "ELM NEW:%p:%d: '%s' = '%s'", md,
537 : gpr_atm_no_barrier_load(&md->refcnt),
538 : grpc_mdstr_as_c_string((grpc_mdstr *)md->key),
539 : grpc_mdstr_as_c_string((grpc_mdstr *)md->value));
540 : #endif
541 1485861 : shard->count++;
542 :
543 1485861 : if (shard->count > shard->capacity * 2) {
544 125845 : rehash_mdtab(shard);
545 : }
546 :
547 1485861 : gpr_mu_unlock(&shard->mu);
548 :
549 : GPR_TIMER_END("grpc_mdelem_from_metadata_strings", 0);
550 :
551 1485861 : return (grpc_mdelem *)md;
552 : }
553 :
554 1413878 : grpc_mdelem *grpc_mdelem_from_strings(const char *key, const char *value) {
555 1413878 : return grpc_mdelem_from_metadata_strings(grpc_mdstr_from_string(key),
556 : grpc_mdstr_from_string(value));
557 : }
558 :
559 26185 : grpc_mdelem *grpc_mdelem_from_slices(gpr_slice key, gpr_slice value) {
560 26185 : return grpc_mdelem_from_metadata_strings(grpc_mdstr_from_slice(key),
561 : grpc_mdstr_from_slice(value));
562 : }
563 :
564 1565144 : grpc_mdelem *grpc_mdelem_from_string_and_buffer(const char *key,
565 : const gpr_uint8 *value,
566 : size_t value_length) {
567 1565144 : return grpc_mdelem_from_metadata_strings(
568 : grpc_mdstr_from_string(key), grpc_mdstr_from_buffer(value, value_length));
569 : }
570 :
571 45044945 : grpc_mdelem *grpc_mdelem_ref(grpc_mdelem *gmd DEBUG_ARGS) {
572 45042517 : internal_metadata *md = (internal_metadata *)gmd;
573 45044945 : if (is_mdelem_static(gmd)) return gmd;
574 : #ifdef GRPC_METADATA_REFCOUNT_DEBUG
575 : gpr_log(file, line, GPR_LOG_SEVERITY_DEBUG,
576 : "ELM REF:%p:%d->%d: '%s' = '%s'", md,
577 : gpr_atm_no_barrier_load(&md->refcnt),
578 : gpr_atm_no_barrier_load(&md->refcnt) + 1,
579 : grpc_mdstr_as_c_string((grpc_mdstr *)md->key),
580 : grpc_mdstr_as_c_string((grpc_mdstr *)md->value));
581 : #endif
582 : /* we can assume the ref count is >= 1 as the application is calling
583 : this function - meaning that no adjustment to mdtab_free is necessary,
584 : simplifying the logic here to be just an atomic increment */
585 : /* use C assert to have this removed in opt builds */
586 20919629 : assert(gpr_atm_no_barrier_load(&md->refcnt) >= 2);
587 20919629 : gpr_atm_no_barrier_fetch_add(&md->refcnt, 1);
588 20919629 : return gmd;
589 : }
590 :
591 79110995 : void grpc_mdelem_unref(grpc_mdelem *gmd DEBUG_ARGS) {
592 79106573 : internal_metadata *md = (internal_metadata *)gmd;
593 79110995 : if (!md) return;
594 79110995 : if (is_mdelem_static(gmd)) return;
595 : #ifdef GRPC_METADATA_REFCOUNT_DEBUG
596 : gpr_log(file, line, GPR_LOG_SEVERITY_DEBUG,
597 : "ELM UNREF:%p:%d->%d: '%s' = '%s'", md,
598 : gpr_atm_no_barrier_load(&md->refcnt),
599 : gpr_atm_no_barrier_load(&md->refcnt) - 1,
600 : grpc_mdstr_as_c_string((grpc_mdstr *)md->key),
601 : grpc_mdstr_as_c_string((grpc_mdstr *)md->value));
602 : #endif
603 29279824 : if (2 == gpr_atm_full_fetch_add(&md->refcnt, -1)) {
604 2099219 : gpr_uint32 hash = GRPC_MDSTR_KV_HASH(md->key->hash, md->value->hash);
605 2099188 : mdtab_shard *shard =
606 2099219 : &g_mdtab_shard[SHARD_IDX(hash, LOG2_MDTAB_SHARD_COUNT)];
607 : GPR_TIMER_BEGIN("grpc_mdelem_unref.to_zero", 0);
608 2099219 : gpr_mu_lock(&shard->mu);
609 2099219 : if (1 == gpr_atm_no_barrier_load(&md->refcnt)) {
610 2099219 : shard->free++;
611 2099219 : gpr_atm_no_barrier_store(&md->refcnt, 0);
612 : }
613 2099219 : gpr_mu_unlock(&shard->mu);
614 : GPR_TIMER_END("grpc_mdelem_unref.to_zero", 0);
615 : }
616 : }
617 :
618 9204428 : const char *grpc_mdstr_as_c_string(grpc_mdstr *s) {
619 9204428 : return (const char *)GPR_SLICE_START_PTR(s->slice);
620 : }
621 :
622 17331855 : grpc_mdstr *grpc_mdstr_ref(grpc_mdstr *gs DEBUG_ARGS) {
623 17330090 : internal_string *s = (internal_string *)gs;
624 17331855 : if (is_mdstr_static(gs)) return gs;
625 17187844 : GPR_ASSERT(gpr_atm_full_fetch_add(&s->refcnt, 1) != 0);
626 17186609 : return gs;
627 : }
628 :
629 24365450 : void grpc_mdstr_unref(grpc_mdstr *gs DEBUG_ARGS) {
630 24363967 : internal_string *s = (internal_string *)gs;
631 48730886 : if (is_mdstr_static(gs)) return;
632 19675450 : if (2 == gpr_atm_full_fetch_add(&s->refcnt, -1)) {
633 2488764 : strtab_shard *shard =
634 2488764 : &g_strtab_shard[SHARD_IDX(s->hash, LOG2_STRTAB_SHARD_COUNT)];
635 2488764 : gpr_mu_lock(&shard->mu);
636 2488764 : if (1 == gpr_atm_no_barrier_load(&s->refcnt)) {
637 2488764 : internal_destroy_string(shard, s);
638 : }
639 2488764 : gpr_mu_unlock(&shard->mu);
640 : }
641 : }
642 :
643 5907854 : void *grpc_mdelem_get_user_data(grpc_mdelem *md, void (*destroy_func)(void *)) {
644 5907667 : internal_metadata *im = (internal_metadata *)md;
645 : void *result;
646 5907854 : if (is_mdelem_static(md)) {
647 4335573 : return (void *)grpc_static_mdelem_user_data[md - grpc_static_mdelem_table];
648 : }
649 1571726 : if (gpr_atm_acq_load(&im->destroy_user_data) == (gpr_atm)destroy_func) {
650 1570081 : return (void *)gpr_atm_no_barrier_load(&im->user_data);
651 : } else {
652 1638 : return NULL;
653 : }
654 : return result;
655 : }
656 :
657 1647 : void grpc_mdelem_set_user_data(grpc_mdelem *md, void (*destroy_func)(void *),
658 : void *user_data) {
659 1640 : internal_metadata *im = (internal_metadata *)md;
660 1647 : GPR_ASSERT(!is_mdelem_static(md));
661 1647 : GPR_ASSERT((user_data == NULL) == (destroy_func == NULL));
662 1647 : gpr_mu_lock(&im->mu_user_data);
663 1647 : if (gpr_atm_no_barrier_load(&im->destroy_user_data)) {
664 : /* user data can only be set once */
665 1 : gpr_mu_unlock(&im->mu_user_data);
666 1 : if (destroy_func != NULL) {
667 1 : destroy_func(user_data);
668 : }
669 1648 : return;
670 : }
671 1646 : gpr_atm_no_barrier_store(&im->user_data, (gpr_atm)user_data);
672 1646 : gpr_atm_rel_store(&im->destroy_user_data, (gpr_atm)destroy_func);
673 1646 : gpr_mu_unlock(&im->mu_user_data);
674 : }
675 :
676 127 : gpr_slice grpc_mdstr_as_base64_encoded_and_huffman_compressed(grpc_mdstr *gs) {
677 123 : internal_string *s = (internal_string *)gs;
678 : gpr_slice slice;
679 123 : strtab_shard *shard =
680 127 : &g_strtab_shard[SHARD_IDX(s->hash, LOG2_STRTAB_SHARD_COUNT)];
681 127 : gpr_mu_lock(&shard->mu);
682 127 : if (!s->has_base64_and_huffman_encoded) {
683 112 : s->base64_and_huffman =
684 : grpc_chttp2_base64_encode_and_huffman_compress(s->slice);
685 112 : s->has_base64_and_huffman_encoded = 1;
686 : }
687 127 : slice = s->base64_and_huffman;
688 127 : gpr_mu_unlock(&shard->mu);
689 127 : return slice;
690 : }
691 :
692 3130158 : static int conforms_to(grpc_mdstr *s, const gpr_uint8 *legal_bits) {
693 3130158 : const gpr_uint8 *p = GPR_SLICE_START_PTR(s->slice);
694 3130158 : const gpr_uint8 *e = GPR_SLICE_END_PTR(s->slice);
695 39159932 : for (; p != e; p++) {
696 36029774 : int idx = *p;
697 36029774 : int byte = idx / 8;
698 36029774 : int bit = idx % 8;
699 36029774 : if ((legal_bits[byte] & (1 << bit)) == 0) return 0;
700 : }
701 3130016 : return 1;
702 : }
703 :
704 1565144 : int grpc_mdstr_is_legal_header(grpc_mdstr *s) {
705 : static const gpr_uint8 legal_header_bits[256 / 8] = {
706 : 0x00, 0x00, 0x00, 0x00, 0x00, 0x20, 0xff, 0x03, 0x00, 0x00, 0x00,
707 : 0x80, 0xfe, 0xff, 0xff, 0x07, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
708 : 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
709 1565144 : return conforms_to(s, legal_header_bits);
710 : }
711 :
712 1565014 : int grpc_mdstr_is_legal_nonbin_header(grpc_mdstr *s) {
713 : static const gpr_uint8 legal_header_bits[256 / 8] = {
714 : 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
715 : 0xff, 0xff, 0xff, 0xff, 0x7f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
716 : 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
717 1565014 : return conforms_to(s, legal_header_bits);
718 : }
719 :
720 1565144 : int grpc_mdstr_is_bin_suffixed(grpc_mdstr *s) {
721 : /* TODO(ctiller): consider caching this */
722 2086918 : return grpc_is_binary_header((const char *)GPR_SLICE_START_PTR(s->slice),
723 2086918 : GPR_SLICE_LENGTH(s->slice));
724 : }
|
