codegen/core/gen_static_metadata.py

#!/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 <grpc/support/port_platform.h>'
print >> H
print >> H, '#include "src/core/lib/transport/metadata.h"'
print >> H
print >> C, '#include <grpc/support/port_platform.h>'
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 <grpc/support/port_platform.h>'
print >> HPACK_H
print >> HPACK_H, '#include "src/core/lib/transport/static_metadata.h"'
print >> HPACK_H
print >> HPACK_C, '#include <grpc/support/port_platform.h>'
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()