#!/usr/bin/env python2.7 # Copyright 2015 gRPC authors. # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # http://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. import hashlib import itertools import collections import os import sys import subprocess import re import perfection # Configuration: a list of either strings or 2-tuples of strings or 3-tuples of # strings. # A single string represents a static grpc_mdstr. # A 2-tuple represents a static grpc_mdelem (and appropriate grpc_mdstrs will # also be created). # A 3-tuple represents a static grpc_mdelem (and appropriate grpc_mdstrs will # also be created), with the last value equivalent to the mdelem's static hpack # table index as defined by RFC 7541 CONFIG = [ # metadata strings 'host', 'grpc-timeout', 'grpc-internal-encoding-request', 'grpc-internal-stream-encoding-request', 'grpc-payload-bin', ':path', 'grpc-encoding', 'grpc-accept-encoding', 'user-agent', ':authority', 'grpc-message', 'grpc-status', 'grpc-server-stats-bin', 'grpc-tags-bin', 'grpc-trace-bin', 'grpc-previous-rpc-attempts', 'grpc-retry-pushback-ms', '1', '2', '3', '4', '', # channel arg keys 'grpc.wait_for_ready', 'grpc.timeout', 'grpc.max_request_message_bytes', 'grpc.max_response_message_bytes', # well known method names '/grpc.lb.v1.LoadBalancer/BalanceLoad', # compression algorithm names 'deflate', 'gzip', 'stream/gzip', # metadata elements ('grpc-status', '0'), ('grpc-status', '1'), ('grpc-status', '2'), ('grpc-encoding', 'identity'), ('grpc-encoding', 'gzip'), ('grpc-encoding', 'deflate'), ('te', 'trailers'), ('content-type', 'application/grpc'), (':method', 'POST', 3), (':status', '200', 8), (':status', '404', 13), (':scheme', 'http', 6), (':scheme', 'https', 7), (':scheme', 'grpc', 0), (':authority', '', 1), (':method', 'GET', 2), (':method', 'PUT'), (':path', '/', 4), (':path', '/index.html', 5), (':status', '204', 9), (':status', '206', 10), (':status', '304', 11), (':status', '400', 12), (':status', '500', 14), ('accept-charset', '', 15), ('accept-encoding', ''), ('accept-encoding', 'gzip, deflate', 16), ('accept-language', '', 17), ('accept-ranges', '', 18), ('accept', '', 19), ('access-control-allow-origin', '', 20), ('age', '', 21), ('allow', '', 22), ('authorization', '', 23), ('cache-control', '', 24), ('content-disposition', '', 25), ('content-encoding', 'identity'), ('content-encoding', 'gzip'), ('content-encoding', '', 26), ('content-language', '', 27), ('content-length', '', 28), ('content-location', '', 29), ('content-range', '', 30), ('content-type', '', 31), ('cookie', '', 32), ('date', '', 33), ('etag', '', 34), ('expect', '', 35), ('expires', '', 36), ('from', '', 37), ('host', '', 38), ('if-match', '', 39), ('if-modified-since', '', 40), ('if-none-match', '', 41), ('if-range', '', 42), ('if-unmodified-since', '', 43), ('last-modified', '', 44), ('lb-token', ''), ('lb-cost-bin', ''), ('link', '', 45), ('location', '', 46), ('max-forwards', '', 47), ('proxy-authenticate', '', 48), ('proxy-authorization', '', 49), ('range', '', 50), ('referer', '', 51), ('refresh', '', 52), ('retry-after', '', 53), ('server', '', 54), ('set-cookie', '', 55), ('strict-transport-security', '', 56), ('transfer-encoding', '', 57), ('user-agent', '', 58), ('vary', '', 59), ('via', '', 60), ('www-authenticate', '', 61), ] # All entries here are ignored when counting non-default initial metadata that # prevents the chttp2 server from sending a Trailers-Only response. METADATA_BATCH_CALLOUTS = [ # (name) (':path'), (':method'), (':status'), (':authority'), (':scheme'), ('te'), ('grpc-message'), ('grpc-status'), ('grpc-payload-bin'), ('grpc-encoding'), ('grpc-accept-encoding'), ('grpc-server-stats-bin'), ('grpc-tags-bin'), ('grpc-trace-bin'), ('content-type'), ('content-encoding'), ('accept-encoding'), ('grpc-internal-encoding-request'), ('grpc-internal-stream-encoding-request'), ('user-agent'), ('host'), ('lb-token'), ('grpc-previous-rpc-attempts'), ('grpc-retry-pushback-ms'), ] COMPRESSION_ALGORITHMS = [ 'identity', 'deflate', 'gzip', ] STREAM_COMPRESSION_ALGORITHMS = [ 'identity', 'gzip', ] # utility: mangle the name of a config def mangle(elem, name=None): xl = { '-': '_', ':': '', '/': 'slash', '.': 'dot', ',': 'comma', ' ': '_', } def m0(x): if not x: return 'empty' r = '' for c in x: put = xl.get(c, c.lower()) if not put: continue last_is_underscore = r[-1] == '_' if r else True if last_is_underscore and put == '_': continue elif len(put) > 1: if not last_is_underscore: r += '_' r += put r += '_' else: r += put if r[-1] == '_': r = r[:-1] return r def n(default, name=name): if name is None: return 'grpc_%s_' % default if name == '': return '' return 'grpc_%s_' % name if isinstance(elem, tuple): return '%s%s_%s' % (n('mdelem'), m0(elem[0]), m0(elem[1])) else: return '%s%s' % (n('mdstr'), m0(elem)) # utility: generate some hash value for a string def fake_hash(elem): return hashlib.md5(elem).hexdigest()[0:8] # utility: print a big comment block into a set of files def put_banner(files, banner): for f in files: print >> f, '/*' for line in banner: print >> f, ' * %s' % line print >> f, ' */' print >> f # build a list of all the strings we need all_strs = list() all_elems = list() static_userdata = {} # put metadata batch callouts first, to make the check of if a static metadata # string is a callout trivial for elem in METADATA_BATCH_CALLOUTS: if elem not in all_strs: all_strs.append(elem) for elem in CONFIG: if isinstance(elem, tuple): if elem[0] not in all_strs: all_strs.append(elem[0]) if elem[1] not in all_strs: all_strs.append(elem[1]) if elem not in all_elems: all_elems.append(elem) else: if elem not in all_strs: all_strs.append(elem) compression_elems = [] for mask in range(1, 1 << len(COMPRESSION_ALGORITHMS)): val = ','.join(COMPRESSION_ALGORITHMS[alg] for alg in range(0, len(COMPRESSION_ALGORITHMS)) if (1 << alg) & mask) elem = ('grpc-accept-encoding', val) if val not in all_strs: all_strs.append(val) if elem not in all_elems: all_elems.append(elem) compression_elems.append(elem) static_userdata[elem] = 1 + (mask | 1) stream_compression_elems = [] for mask in range(1, 1 << len(STREAM_COMPRESSION_ALGORITHMS)): val = ','.join(STREAM_COMPRESSION_ALGORITHMS[alg] for alg in range(0, len(STREAM_COMPRESSION_ALGORITHMS)) if (1 << alg) & mask) elem = ('accept-encoding', val) if val not in all_strs: all_strs.append(val) if elem not in all_elems: all_elems.append(elem) stream_compression_elems.append(elem) static_userdata[elem] = 1 + (mask | 1) # output configuration args = sys.argv[1:] H = None C = None D = None if args: if 'header' in args: H = sys.stdout else: H = open('/dev/null', 'w') if 'source' in args: C = sys.stdout else: C = open('/dev/null', 'w') if 'dictionary' in args: D = sys.stdout else: D = open('/dev/null', 'w') else: H = open( os.path.join( os.path.dirname(sys.argv[0]), '../../../src/core/lib/transport/static_metadata.h'), 'w') C = open( os.path.join( os.path.dirname(sys.argv[0]), '../../../src/core/lib/transport/static_metadata.cc'), 'w') D = open( os.path.join( os.path.dirname(sys.argv[0]), '../../../test/core/end2end/fuzzers/hpack.dictionary'), 'w') HPACK_H = open( os.path.join( os.path.dirname(sys.argv[0]), '../../../src/core/ext/transport/chttp2/transport/hpack_mapping.h'), 'w') HPACK_C = open( os.path.join( os.path.dirname(sys.argv[0]), '../../../src/core/ext/transport/chttp2/transport/hpack_mapping.cc'), 'w') # copy-paste copyright notice from this file with open(sys.argv[0]) as my_source: copyright = [] for line in my_source: if line[0] != '#': break for line in my_source: if line[0] == '#': copyright.append(line) break for line in my_source: if line[0] != '#': break copyright.append(line) put_banner([H, C, HPACK_H, HPACK_C], [line[2:].rstrip() for line in copyright]) hex_bytes = [ord(c) for c in 'abcdefABCDEF0123456789'] def esc_dict(line): out = "\"" for c in line: if 32 <= c < 127: if c != ord('"'): out += chr(c) else: out += "\\\"" else: out += '\\x%02X' % c return out + "\"" put_banner([H, C], """WARNING: Auto-generated code. To make changes to this file, change tools/codegen/core/gen_static_metadata.py, and then re-run it. See metadata.h for an explanation of the interface here, and metadata.cc for an explanation of what's going on. """.splitlines()) put_banner([HPACK_H, HPACK_C], """WARNING: Auto-generated code. To make changes to this file, change tools/codegen/core/gen_static_metadata.py, and then re-run it. This file contains the mapping from the index of each metadata element in the grpc static metadata table to the index of that element in the hpack static metadata table. If the element is not contained in the static hpack table, then the returned index is 0. """.splitlines()) print >> H, '#ifndef GRPC_CORE_LIB_TRANSPORT_STATIC_METADATA_H' print >> H, '#define GRPC_CORE_LIB_TRANSPORT_STATIC_METADATA_H' print >> H print >> H, '#include ' print >> H print >> H, '#include "src/core/lib/transport/metadata.h"' print >> H print >> C, '#include ' print >> C print >> C, '#include "src/core/lib/transport/static_metadata.h"' print >> C print >> C, '#include "src/core/lib/slice/slice_internal.h"' print >> C print >> HPACK_H, ('#ifndef GRPC_CORE_EXT_TRANSPORT_CHTTP2_TRANSPORT_HPACK_' 'MAPPING_H') print >> HPACK_H, ('#define GRPC_CORE_EXT_TRANSPORT_CHTTP2_TRANSPORT_HPACK_' 'MAPPING_H') print >> HPACK_H print >> HPACK_H, '#include ' print >> HPACK_H print >> HPACK_H, '#include "src/core/lib/transport/static_metadata.h"' print >> HPACK_H print >> HPACK_C, '#include ' print >> HPACK_C print >> HPACK_C, ('#include ' '"src/core/ext/transport/chttp2/transport/hpack_mapping.h"') print >> HPACK_C str_ofs = 0 id2strofs = {} for i, elem in enumerate(all_strs): id2strofs[i] = str_ofs str_ofs += len(elem) def slice_def(i): return ('{&grpc_static_metadata_refcounts[%d],' ' {{g_bytes+%d, %d}}}') % (i, id2strofs[i], len(all_strs[i])) # validate configuration for elem in METADATA_BATCH_CALLOUTS: assert elem in all_strs print >> H, '#define GRPC_STATIC_MDSTR_COUNT %d' % len(all_strs) print >> H, ('extern const grpc_slice ' 'grpc_static_slice_table[GRPC_STATIC_MDSTR_COUNT];') for i, elem in enumerate(all_strs): print >> H, '/* "%s" */' % elem print >> H, '#define %s (grpc_static_slice_table[%d])' % ( mangle(elem).upper(), i) print >> H print >> C, 'static uint8_t g_bytes[] = {%s};' % (','.join( '%d' % ord(c) for c in ''.join(all_strs))) print >> C print >> C, 'static void static_ref(void *unused) {}' print >> C, 'static void static_unref(void *unused) {}' print >> C, ('static const grpc_slice_refcount_vtable static_sub_vtable = ' '{static_ref, static_unref, grpc_slice_default_eq_impl, ' 'grpc_slice_default_hash_impl};') print >> H, ('extern const grpc_slice_refcount_vtable ' 'grpc_static_metadata_vtable;') print >> C, ('const grpc_slice_refcount_vtable grpc_static_metadata_vtable = ' '{static_ref, static_unref, grpc_static_slice_eq, ' 'grpc_static_slice_hash};') print >> C, ('static grpc_slice_refcount static_sub_refcnt = ' '{&static_sub_vtable, &static_sub_refcnt};') print >> H, ('extern grpc_slice_refcount ' 'grpc_static_metadata_refcounts[GRPC_STATIC_MDSTR_COUNT];') print >> C, ('grpc_slice_refcount ' 'grpc_static_metadata_refcounts[GRPC_STATIC_MDSTR_COUNT] = {') for i, elem in enumerate(all_strs): print >> C, ' {&grpc_static_metadata_vtable, &static_sub_refcnt},' print >> C, '};' print >> C print >> H, '#define GRPC_IS_STATIC_METADATA_STRING(slice) \\' print >> H, (' ((slice).refcount != NULL && (slice).refcount->vtable == ' '&grpc_static_metadata_vtable)') print >> H print >> C, ('const grpc_slice grpc_static_slice_table[GRPC_STATIC_MDSTR_COUNT]' ' = {') for i, elem in enumerate(all_strs): print >> C, slice_def(i) + ',' print >> C, '};' print >> C print >> H, '#define GRPC_STATIC_METADATA_INDEX(static_slice) \\' print >> H, (' ((int)((static_slice).refcount - ' 'grpc_static_metadata_refcounts))') print >> H print >> D, '# hpack fuzzing dictionary' for i, elem in enumerate(all_strs): print >> D, '%s' % (esc_dict([len(elem)] + [ord(c) for c in elem])) for i, elem in enumerate(all_elems): print >> D, '%s' % (esc_dict([0, len(elem[0])] + [ord(c) for c in elem[0]] + [len(elem[1])] + [ord(c) for c in elem[1]])) print >> H, '#define GRPC_STATIC_MDELEM_COUNT %d' % len(all_elems) print >> H, ('extern grpc_mdelem_data ' 'grpc_static_mdelem_table[GRPC_STATIC_MDELEM_COUNT];') print >> H, ('extern uintptr_t ' 'grpc_static_mdelem_user_data[GRPC_STATIC_MDELEM_COUNT];') for i, elem in enumerate(all_elems): print >> H, '/* "%s": "%s" */' % (elem[0], elem[1]) print >> H, ('#define %s (GRPC_MAKE_MDELEM(&grpc_static_mdelem_table[%d], ' 'GRPC_MDELEM_STORAGE_STATIC))') % (mangle(elem).upper(), i) print >> H # Print out the chttp2 mapping between static mdelem index and the hpack static # table index print >> HPACK_H, ('extern const uint8_t grpc_hpack_static_mdelem_indices[' 'GRPC_STATIC_MDELEM_COUNT];') print >> HPACK_H print >> HPACK_C, ('const uint8_t grpc_hpack_static_mdelem_indices[' 'GRPC_STATIC_MDELEM_COUNT] = {') indices = '' for elem in all_elems: index = 0 if len(elem) == 3: index = elem[2] indices += '%d,' % index print >> HPACK_C, ' %s' % indices print >> HPACK_C, '};' print >> HPACK_C print >> C, ('uintptr_t grpc_static_mdelem_user_data[GRPC_STATIC_MDELEM_COUNT] ' '= {') print >> C, ' %s' % ','.join( '%d' % static_userdata.get(elem, 0) for elem in all_elems) print >> C, '};' print >> C def str_idx(s): for i, s2 in enumerate(all_strs): if s == s2: return i def md_idx(m): for i, m2 in enumerate(all_elems): if m == m2: return i def offset_trials(mink): yield 0 for i in range(1, 100): for mul in [-1, 1]: yield mul * i def perfect_hash(keys, name): p = perfection.hash_parameters(keys) def f(i, p=p): i += p.offset x = i % p.t y = i / p.t return x + p.r[y] return { 'PHASHRANGE': p.t - 1 + max(p.r), 'PHASHNKEYS': len(p.slots), 'pyfunc': f, 'code': """ static const int8_t %(name)s_r[] = {%(r)s}; static uint32_t %(name)s_phash(uint32_t i) { i %(offset_sign)s= %(offset)d; uint32_t x = i %% %(t)d; uint32_t y = i / %(t)d; uint32_t h = x; if (y < GPR_ARRAY_SIZE(%(name)s_r)) { uint32_t delta = (uint32_t)%(name)s_r[y]; h += delta; } return h; } """ % { 'name': name, 'r': ','.join('%d' % (r if r is not None else 0) for r in p.r), 't': p.t, 'offset': abs(p.offset), 'offset_sign': '+' if p.offset > 0 else '-' } } elem_keys = [ str_idx(elem[0]) * len(all_strs) + str_idx(elem[1]) for elem in all_elems ] elem_hash = perfect_hash(elem_keys, 'elems') print >> C, elem_hash['code'] keys = [0] * int(elem_hash['PHASHRANGE']) idxs = [255] * int(elem_hash['PHASHNKEYS']) for i, k in enumerate(elem_keys): h = elem_hash['pyfunc'](k) assert keys[h] == 0 keys[h] = k idxs[h] = i print >> C, 'static const uint16_t elem_keys[] = {%s};' % ','.join( '%d' % k for k in keys) print >> C, 'static const uint8_t elem_idxs[] = {%s};' % ','.join( '%d' % i for i in idxs) print >> C print >> H, 'grpc_mdelem grpc_static_mdelem_for_static_strings(int a, int b);' print >> C, 'grpc_mdelem grpc_static_mdelem_for_static_strings(int a, int b) {' print >> C, ' if (a == -1 || b == -1) return GRPC_MDNULL;' print >> C, ' uint32_t k = (uint32_t)(a * %d + b);' % len(all_strs) print >> C, ' uint32_t h = elems_phash(k);' print >> C, ' return h < GPR_ARRAY_SIZE(elem_keys) && elem_keys[h] == k && elem_idxs[h] != 255 ? GRPC_MAKE_MDELEM(&grpc_static_mdelem_table[elem_idxs[h]], GRPC_MDELEM_STORAGE_STATIC) : GRPC_MDNULL;' print >> C, '}' print >> C print >> C, 'grpc_mdelem_data grpc_static_mdelem_table[GRPC_STATIC_MDELEM_COUNT] = {' for elem in all_elems: print >> C, '{%s,%s},' % (slice_def(str_idx(elem[0])), slice_def(str_idx(elem[1]))) print >> C, '};' print >> H, 'typedef enum {' for elem in METADATA_BATCH_CALLOUTS: print >> H, ' %s,' % mangle(elem, 'batch').upper() print >> H, ' GRPC_BATCH_CALLOUTS_COUNT' print >> H, '} grpc_metadata_batch_callouts_index;' print >> H print >> H, 'typedef union {' print >> H, ' struct grpc_linked_mdelem *array[GRPC_BATCH_CALLOUTS_COUNT];' print >> H, ' struct {' for elem in METADATA_BATCH_CALLOUTS: print >> H, ' struct grpc_linked_mdelem *%s;' % mangle(elem, '').lower() print >> H, ' } named;' print >> H, '} grpc_metadata_batch_callouts;' print >> H print >> H, '#define GRPC_BATCH_INDEX_OF(slice) \\' print >> H, ' (GRPC_IS_STATIC_METADATA_STRING((slice)) ? (grpc_metadata_batch_callouts_index)GPR_CLAMP(GRPC_STATIC_METADATA_INDEX((slice)), 0, GRPC_BATCH_CALLOUTS_COUNT) : GRPC_BATCH_CALLOUTS_COUNT)' print >> H print >> H, 'extern const uint8_t grpc_static_accept_encoding_metadata[%d];' % ( 1 << len(COMPRESSION_ALGORITHMS)) print >> C, 'const uint8_t grpc_static_accept_encoding_metadata[%d] = {' % ( 1 << len(COMPRESSION_ALGORITHMS)) print >> C, '0,%s' % ','.join('%d' % md_idx(elem) for elem in compression_elems) print >> C, '};' print >> C print >> H, '#define GRPC_MDELEM_ACCEPT_ENCODING_FOR_ALGORITHMS(algs) (GRPC_MAKE_MDELEM(&grpc_static_mdelem_table[grpc_static_accept_encoding_metadata[(algs)]], GRPC_MDELEM_STORAGE_STATIC))' print >> H print >> H, 'extern const uint8_t grpc_static_accept_stream_encoding_metadata[%d];' % ( 1 << len(STREAM_COMPRESSION_ALGORITHMS)) print >> C, 'const uint8_t grpc_static_accept_stream_encoding_metadata[%d] = {' % ( 1 << len(STREAM_COMPRESSION_ALGORITHMS)) print >> C, '0,%s' % ','.join( '%d' % md_idx(elem) for elem in stream_compression_elems) print >> C, '};' print >> H, '#define GRPC_MDELEM_ACCEPT_STREAM_ENCODING_FOR_ALGORITHMS(algs) (GRPC_MAKE_MDELEM(&grpc_static_mdelem_table[grpc_static_accept_stream_encoding_metadata[(algs)]], GRPC_MDELEM_STORAGE_STATIC))' print >> H, '#endif /* GRPC_CORE_LIB_TRANSPORT_STATIC_METADATA_H */' print >> HPACK_H, ('#endif /* GRPC_CORE_EXT_TRANSPORT_CHTTP2_TRANSPORT_HPACK_' 'MAPPING_H */') H.close() C.close()