src/core/transport/chttp2/hpack_table.c

/*
 *
 * Copyright 2014, Google Inc.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

#include "src/core/transport/chttp2/hpack_table.h"

#include <assert.h>
#include <string.h>

#include <grpc/support/log.h>
#include "src/core/support/murmur_hash.h"

static struct {
  const char *key;
  const char *value;
} static_table[] = {
    /* 0: */ {NULL, NULL},
    /* 1: */ {":authority", ""},
    /* 2: */ {":method", "GET"},
    /* 3: */ {":method", "POST"},
    /* 4: */ {":path", "/"},
    /* 5: */ {":path", "/index.html"},
    /* 6: */ {":scheme", "http"},
    /* 7: */ {":scheme", "https"},
    /* 8: */ {":status", "200"},
    /* 9: */ {":status", "204"},
    /* 10: */ {":status", "206"},
    /* 11: */ {":status", "304"},
    /* 12: */ {":status", "400"},
    /* 13: */ {":status", "404"},
    /* 14: */ {":status", "500"},
    /* 15: */ {"accept-charset", ""},
    /* 16: */ {"accept-encoding", "gzip, deflate"},
    /* 17: */ {"accept-language", ""},
    /* 18: */ {"accept-ranges", ""},
    /* 19: */ {"accept", ""},
    /* 20: */ {"access-control-allow-origin", ""},
    /* 21: */ {"age", ""},
    /* 22: */ {"allow", ""},
    /* 23: */ {"authorization", ""},
    /* 24: */ {"cache-control", ""},
    /* 25: */ {"content-disposition", ""},
    /* 26: */ {"content-encoding", ""},
    /* 27: */ {"content-language", ""},
    /* 28: */ {"content-length", ""},
    /* 29: */ {"content-location", ""},
    /* 30: */ {"content-range", ""},
    /* 31: */ {"content-type", ""},
    /* 32: */ {"cookie", ""},
    /* 33: */ {"date", ""},
    /* 34: */ {"etag", ""},
    /* 35: */ {"expect", ""},
    /* 36: */ {"expires", ""},
    /* 37: */ {"from", ""},
    /* 38: */ {"host", ""},
    /* 39: */ {"if-match", ""},
    /* 40: */ {"if-modified-since", ""},
    /* 41: */ {"if-none-match", ""},
    /* 42: */ {"if-range", ""},
    /* 43: */ {"if-unmodified-since", ""},
    /* 44: */ {"last-modified", ""},
    /* 45: */ {"link", ""},
    /* 46: */ {"location", ""},
    /* 47: */ {"max-forwards", ""},
    /* 48: */ {"proxy-authenticate", ""},
    /* 49: */ {"proxy-authorization", ""},
    /* 50: */ {"range", ""},
    /* 51: */ {"referer", ""},
    /* 52: */ {"refresh", ""},
    /* 53: */ {"retry-after", ""},
    /* 54: */ {"server", ""},
    /* 55: */ {"set-cookie", ""},
    /* 56: */ {"strict-transport-security", ""},
    /* 57: */ {"transfer-encoding", ""},
    /* 58: */ {"user-agent", ""},
    /* 59: */ {"vary", ""},
    /* 60: */ {"via", ""},
    /* 61: */ {"www-authenticate", ""},
};

void grpc_chttp2_hptbl_init(grpc_chttp2_hptbl *tbl, grpc_mdctx *mdctx) {
  size_t i;

  memset(tbl, 0, sizeof(*tbl));
  tbl->mdctx = mdctx;
  tbl->max_bytes = GRPC_CHTTP2_INITIAL_HPACK_TABLE_SIZE;
  for (i = 1; i <= GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) {
    tbl->static_ents[i - 1] = grpc_mdelem_from_strings(
        mdctx, static_table[i].key, static_table[i].value);
  }
}

void grpc_chttp2_hptbl_destroy(grpc_chttp2_hptbl *tbl) {
  size_t i;
  for (i = 0; i < GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) {
    grpc_mdelem_unref(tbl->static_ents[i]);
  }
  for (i = 0; i < tbl->num_ents; i++) {
    grpc_mdelem_unref(
        tbl->ents[(tbl->first_ent + i) % GRPC_CHTTP2_MAX_TABLE_COUNT]);
  }
}

grpc_mdelem *grpc_chttp2_hptbl_lookup(const grpc_chttp2_hptbl *tbl,
                                      gpr_uint32 index) {
  /* Static table comes first, just return an entry from it */
  if (index <= GRPC_CHTTP2_LAST_STATIC_ENTRY) {
    return tbl->static_ents[index - 1];
  }
  /* Otherwise, find the value in the list of valid entries */
  index -= (GRPC_CHTTP2_LAST_STATIC_ENTRY + 1);
  if (index < tbl->num_ents) {
    gpr_uint32 offset = (tbl->num_ents - 1 - index + tbl->first_ent) %
                        GRPC_CHTTP2_MAX_TABLE_COUNT;
    return tbl->ents[offset];
  }
  /* Invalid entry: return error */
  return NULL;
}

/* Evict one element from the table */
static void evict1(grpc_chttp2_hptbl *tbl) {
  grpc_mdelem *first_ent = tbl->ents[tbl->first_ent];
  tbl->mem_used -= GPR_SLICE_LENGTH(first_ent->key->slice) +
                   GPR_SLICE_LENGTH(first_ent->value->slice) +
                   GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
  tbl->first_ent = (tbl->first_ent + 1) % GRPC_CHTTP2_MAX_TABLE_COUNT;
  tbl->num_ents--;
  grpc_mdelem_unref(first_ent);
}

void grpc_chttp2_hptbl_add(grpc_chttp2_hptbl *tbl, grpc_mdelem *md) {
  /* determine how many bytes of buffer this entry represents */
  gpr_uint16 elem_bytes = GPR_SLICE_LENGTH(md->key->slice) +
                          GPR_SLICE_LENGTH(md->value->slice) +
                          GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;

  /* we can't add elements bigger than the max table size */
  assert(elem_bytes <= tbl->max_bytes);

  /* evict entries to ensure no overflow */
  while (elem_bytes > tbl->max_bytes - tbl->mem_used) {
    evict1(tbl);
  }

  /* copy the finalized entry in */
  tbl->ents[tbl->last_ent] = md;

  /* update accounting values */
  tbl->last_ent = (tbl->last_ent + 1) % GRPC_CHTTP2_MAX_TABLE_COUNT;
  tbl->num_ents++;
  tbl->mem_used += elem_bytes;
}

grpc_chttp2_hptbl_find_result grpc_chttp2_hptbl_find(
    const grpc_chttp2_hptbl *tbl, grpc_mdelem *md) {
  grpc_chttp2_hptbl_find_result r = {0, 0};
  int i;

  /* See if the string is in the static table */
  for (i = 0; i < GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) {
    grpc_mdelem *ent = tbl->static_ents[i];
    if (md->key != ent->key) continue;
    r.index = i + 1;
    r.has_value = md->value == ent->value;
    if (r.has_value) return r;
  }

  /* Scan the dynamic table */
  for (i = 0; i < tbl->num_ents; i++) {
    int idx = tbl->num_ents - i + GRPC_CHTTP2_LAST_STATIC_ENTRY;
    grpc_mdelem *ent =
        tbl->ents[(tbl->first_ent + i) % GRPC_CHTTP2_MAX_TABLE_COUNT];
    if (md->key != ent->key) continue;
    r.index = idx;
    r.has_value = md->value == ent->value;
    if (r.has_value) return r;
  }

  return r;
}