MINOR: qpack: Add QPACK compression.
Implement QPACK used for HTTP header compression by h3.
diff --git a/include/haproxy/qpack-dec.h b/include/haproxy/qpack-dec.h
new file mode 100644
index 0000000..517d617
--- /dev/null
+++ b/include/haproxy/qpack-dec.h
@@ -0,0 +1,50 @@
+/*
+ * QPACK decompressor
+ *
+ * Copyright 2021 HAProxy Technologies, Frédéric Lécaille <flecaille@haproxy.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation, version 2.1
+ * exclusively.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef _HAPROXY_QPACK_DEC_H
+#define _HAPROXY_QPACK_DEC_H
+
+#include <haproxy/mux_quic-t.h>
+
+struct h3_uqs;
+
+/* Internal QPACK processing errors.
+ *Nothing to see with the RFC.
+ */
+enum {
+ QPACK_ERR_NONE = 0,
+ QPACK_ERR_RIC,
+ QPACK_ERR_DB,
+ QPACK_ERR_TRUNCATED,
+ QPACK_ERR_HUFFMAN,
+};
+
+struct qpack_dec {
+ /* Insert count */
+ uint64_t ic;
+ /* Known received count */
+ uint64_t krc;
+};
+
+int qpack_decode_fs(const unsigned char *buf, uint64_t len, struct buffer *tmp);
+int qpack_decode_enc(struct h3_uqs *h3_uqs, void *ctx);
+int qpack_decode_dec(struct h3_uqs *h3_uqs, void *ctx);
+
+#endif /* _HAPROXY_QPACK_DEC_H */
diff --git a/include/haproxy/qpack-t.h b/include/haproxy/qpack-t.h
new file mode 100644
index 0000000..832094e
--- /dev/null
+++ b/include/haproxy/qpack-t.h
@@ -0,0 +1,47 @@
+/*
+ * include/haproxy/qpack-t.h
+ * This file containts types for QPACK
+ *
+ * Copyright 2021 HAProxy Technologies, Frédéric Lécaille <flecaille@haproxy.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation, version 2.1
+ * exclusively.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef _HAPROXY_QPACK_T_H
+#define _HAPROXY_QPACK_T_H
+#ifdef USE_QUIC
+#ifndef USE_OPENSSL
+#error "Must define USE_OPENSSL"
+#endif
+
+/* Encoder */
+/* Instruction bitmask */
+#define QPACK_ENC_INST_BITMASK 0xf0
+/* Instructions */
+#define QPACK_ENC_INST_DUP 0x00 // Duplicate
+#define QPACK_ENC_INST_SDTC_BIT 0x20 // Set Dynamic Table Capacity
+#define QPACK_ENC_INST_IWLN_BIT 0x40 // Insert With Literal Name
+#define QPACK_ENC_INST_IWNR_BIT 0x80 // Insert With Name Reference
+
+/* Decoder */
+/* Instructions bitmask */
+#define QPACK_DEC_INST_BITMASK 0xf0
+/* Instructions */
+#define QPACK_DEC_INST_ICINC 0x00 // Insert Count Increment
+#define QPACK_DEC_INST_SCCL 0x40 // Stream Cancellation
+#define QPACK_DEC_INST_SACK 0x80 // Section Acknowledgment
+
+#endif /* USE_QUIC */
+#endif /* _HAPROXY_QPACK_T_H */
diff --git a/include/haproxy/qpack-tbl-t.h b/include/haproxy/qpack-tbl-t.h
index fd498ee..88f996e 100644
--- a/include/haproxy/qpack-tbl-t.h
+++ b/include/haproxy/qpack-tbl-t.h
@@ -26,6 +26,39 @@
#ifndef _HAPROXY_QPACK_TBL_T_H
#define _HAPROXY_QPACK_TBL_T_H
+/*
+ * Gcc before 3.0 needs [0] to declare a variable-size array
+ */
+#ifndef VAR_ARRAY
+#if defined(__GNUC__) && (__GNUC__ < 3)
+#define VAR_ARRAY 0
+#else
+#define VAR_ARRAY
+#endif
+#endif
+
+/* One dynamic table entry descriptor */
+struct qpack_dte {
+ uint32_t addr; /* storage address, relative to the dte address */
+ uint16_t nlen; /* header name length */
+ uint16_t vlen; /* header value length */
+};
+
+/* Note: the table's head plus a struct qpack_dte must be smaller than or equal to 32
+ * bytes so that a single large header can always fit. Here that's 16 bytes for
+ * the header, plus 8 bytes per slot.
+ * Note that when <used> == 0, front, head, and wrap are undefined.
+ */
+struct qpack_dht {
+ uint32_t size; /* allocated table size in bytes */
+ uint32_t total; /* sum of nlen + vlen in bytes */
+ uint16_t front; /* slot number of the first node after the idx table */
+ uint16_t wrap; /* number of allocated slots, wraps here */
+ uint16_t head; /* last inserted slot number */
+ uint16_t used; /* number of slots in use */
+ struct qpack_dte dte[VAR_ARRAY]; /* dynamic table entries */
+};
+
/* static header table as in draft-ietf-quic-qpack-20 Appendix A. [0] unused. */
#define QPACK_SHT_SIZE 99
diff --git a/include/haproxy/qpack-tbl.h b/include/haproxy/qpack-tbl.h
new file mode 100644
index 0000000..53ab889
--- /dev/null
+++ b/include/haproxy/qpack-tbl.h
@@ -0,0 +1,170 @@
+/*
+ * QPACK header table management - prototypes
+ *
+ * Copyright 2021 HAProxy Technologies, Frédéric Lécaille <flecaille@haproxy.com>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+#ifndef _HAPROXY_QPACK_TBL_H
+#define _HAPROXY_QPACK_TBL_H
+
+#include <import/ist.h>
+#include <haproxy/api.h>
+#include <haproxy/qpack-tbl-t.h>
+#include <haproxy/http-hdr-t.h>
+
+/* when built outside of haproxy, QPACK_STANDALONE must be defined, and
+ * pool_head_qpack_tbl->size must be set to the DHT size.
+ */
+#ifndef QPACK_STANDALONE
+#include <haproxy/pool.h>
+#define qpack_alloc(pool) pool_alloc(pool)
+#define qpack_free(pool, ptr) pool_free(pool, ptr)
+#else
+#include <stdlib.h>
+#include <haproxy/pool-t.h>
+#define qpack_alloc(pool) malloc(pool->size)
+#define qpack_free(pool, ptr) free(ptr)
+#endif
+
+extern const struct http_hdr qpack_sht[QPACK_SHT_SIZE];
+extern struct pool_head *pool_head_qpack_tbl;
+
+int __qpack_dht_make_room(struct qpack_dht *dht, unsigned int needed);
+int qpack_dht_insert(struct qpack_dht *dht, struct ist name, struct ist value);
+
+#ifdef DEBUG_QPACK
+void qpack_dht_dump(FILE *out, const struct qpack_dht *dht);
+void qpack_dht_check_consistency(const struct qpack_dht *dht);
+#endif
+
+/* return a pointer to the entry designated by index <idx> (starting at 0) or
+ * NULL if this index is not there.
+ */
+static inline const struct qpack_dte *qpack_get_dte(const struct qpack_dht *dht, uint16_t idx)
+{
+ if (idx >= dht->used)
+ return NULL;
+
+ return &dht->dte[idx];
+}
+
+/* returns non-zero if <idx> is valid for table <dht> */
+static inline int qpack_valid_idx(const struct qpack_dht *dht, uint32_t idx)
+{
+ return idx < dht->used;
+}
+
+/* return a pointer to the header name for entry <dte>. */
+static inline struct ist qpack_get_name(const struct qpack_dht *dht, const struct qpack_dte *dte)
+{
+ struct ist ret = {
+ .ptr = (void *)dht + dte->addr,
+ .len = dte->nlen,
+ };
+ return ret;
+}
+
+/* return a pointer to the header value for entry <dte>. */
+static inline struct ist qpack_get_value(const struct qpack_dht *dht, const struct qpack_dte *dte)
+{
+ struct ist ret = {
+ .ptr = (void *)dht + dte->addr + dte->nlen,
+ .len = dte->vlen,
+ };
+ return ret;
+}
+
+/* takes an idx, returns the associated name */
+static inline struct ist qpack_idx_to_name(const struct qpack_dht *dht, uint32_t idx)
+{
+ const struct qpack_dte *dte;
+
+ dte = qpack_get_dte(dht, idx);
+ if (!dte)
+ return ist("### ERR ###"); // error
+
+ return qpack_get_name(dht, dte);
+}
+
+/* takes an idx, returns the associated value */
+static inline struct ist qpack_idx_to_value(const struct qpack_dht *dht, uint32_t idx)
+{
+ const struct qpack_dte *dte;
+
+ dte = qpack_get_dte(dht, idx);
+ if (!dte)
+ return ist("### ERR ###"); // error
+
+ return qpack_get_value(dht, dte);
+}
+
+/* returns the slot number of the oldest entry (tail). Must not be used on an
+ * empty table.
+ */
+static inline unsigned int qpack_dht_get_tail(const struct qpack_dht *dht)
+{
+ return ((dht->head + 1U < dht->used) ? dht->wrap : 0) + dht->head + 1U - dht->used;
+}
+
+/* Purges table dht until a header field of <needed> bytes fits according to
+ * the protocol (adding 32 bytes overhead). Returns non-zero on success, zero
+ * on failure (ie: table empty but still not sufficient).
+ */
+static inline int qpack_dht_make_room(struct qpack_dht *dht, unsigned int needed)
+{
+ if (dht->used * 32 + dht->total + needed + 32 <= dht->size)
+ return 1;
+ else if (!dht->used)
+ return 0;
+
+ return __qpack_dht_make_room(dht, needed);
+}
+
+/* allocate a dynamic headers table of <size> bytes and return it initialized */
+static inline void qpack_dht_init(struct qpack_dht *dht, uint32_t size)
+{
+ dht->size = size;
+ dht->total = 0;
+ dht->used = 0;
+}
+
+/* allocate a dynamic headers table from the pool and return it initialized */
+static inline struct qpack_dht *qpack_dht_alloc()
+{
+ struct qpack_dht *dht;
+
+ if (unlikely(!pool_head_qpack_tbl))
+ return NULL;
+
+ dht = qpack_alloc(pool_head_qpack_tbl);
+ if (dht)
+ qpack_dht_init(dht, pool_head_qpack_tbl->size);
+ return dht;
+}
+
+/* free a dynamic headers table */
+static inline void qpack_dht_free(struct qpack_dht *dht)
+{
+ qpack_free(pool_head_qpack_tbl, dht);
+}
+
+#endif /* _HAPROXY_QPACK_TBL_H */
diff --git a/src/qpack-dec.c b/src/qpack-dec.c
new file mode 100644
index 0000000..95ec720
--- /dev/null
+++ b/src/qpack-dec.c
@@ -0,0 +1,344 @@
+/*
+ * QPACK decompressor
+ *
+ * Copyright 2021 HAProxy Technologies, Frédéric Lécaille <flecaille@haproxy.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation, version 2.1
+ * exclusively.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <import/ist.h>
+#include <haproxy/buf.h>
+#include <haproxy/chunk.h>
+#include <haproxy/h3.h>
+#include <haproxy/qpack-t.h>
+#include <haproxy/qpack-dec.h>
+#include <haproxy/hpack-huff.h>
+#include <haproxy/hpack-tbl.h>
+#include <haproxy/tools.h>
+
+#define DEBUG_HPACK
+
+#if defined(DEBUG_HPACK)
+#define qpack_debug_printf fprintf
+#define qpack_debug_hexdump debug_hexdump
+#else
+#define qpack_debug_printf(...) do { } while (0)
+#define qpack_debug_hexdump(...) do { } while (0)
+#endif
+
+/* Encoded field line bitmask */
+#define QPACK_EFL_BITMASK 0xf0
+#define QPACK_LFL_WPBNM 0x00 // Literal field line with post-base name reference
+#define QPACK_IFL_WPBI 0x10 // Indexed field line with post-based index
+#define QPACK_LFL_WLN_BIT 0x20 // Literal field line with literal name
+#define QPACK_LFL_WNR_BIT 0x40 // Literal field line with name reference
+#define QPACK_IFL_BIT 0x80 // Indexed field line
+
+/* reads a varint from <raw>'s lowest <b> bits and <len> bytes max (raw included).
+ * returns the 64-bit value on success after updating buf and len_in. Forces
+ * len_in to (uint64_t)-1 on truncated input.
+ * Note that this function is similar to the one used for HPACK (except that is supports
+ * up to 62-bits integers).
+ */
+static uint64_t qpack_get_varint(const unsigned char **buf, uint64_t *len_in, int b)
+{
+ uint64_t ret = 0;
+ int len = *len_in;
+ const uint8_t *raw = *buf;
+ uint8_t shift = 0;
+
+ len--;
+ ret = *raw++ & ((1 << b) - 1);
+ if (ret != (uint64_t)((1 << b) - 1))
+ goto end;
+
+ while (len && (*raw & 128)) {
+ ret += ((uint64_t)*raw++ & 127) << shift;
+ shift += 7;
+ len--;
+ }
+
+ /* last 7 bits */
+ if (!len)
+ goto too_short;
+
+ len--;
+ ret += ((uint64_t)*raw++ & 127) << shift;
+
+ end:
+ *buf = raw;
+ *len_in = len;
+ return ret;
+
+ too_short:
+ *len_in = (uint64_t)-1;
+ return 0;
+}
+
+/* Decode an encoder stream */
+int qpack_decode_enc(struct h3_uqs *h3_uqs, void *ctx)
+{
+ size_t len;
+ struct buffer *rxbuf;
+ unsigned char inst;
+
+ rxbuf = &h3_uqs->qcs->rx.buf;
+ len = b_data(rxbuf);
+ qpack_debug_hexdump(stderr, "[QPACK-DEC-ENC] ", b_head(rxbuf), 0, len);
+
+ if (!len) {
+ qpack_debug_printf(stderr, "[QPACK-DEC-ENC] empty stream\n");
+ return 0;
+ }
+
+ inst = (unsigned char)*b_head(rxbuf) & QPACK_ENC_INST_BITMASK;
+ if (inst == QPACK_ENC_INST_DUP) {
+ /* Duplicate */
+ }
+ else if (inst & QPACK_ENC_INST_IWNR_BIT) {
+ /* Insert With Name Reference */
+ }
+ else if (inst & QPACK_ENC_INST_IWLN_BIT) {
+ /* Insert with literal name */
+ }
+ else if (inst & QPACK_ENC_INST_SDTC_BIT) {
+ /* Set dynamic table capacity */
+ }
+
+ return 1;
+}
+
+/* Decode an decoder stream */
+int qpack_decode_dec(struct h3_uqs *h3_uqs, void *ctx)
+{
+ size_t len;
+ struct buffer *rxbuf;
+ unsigned char inst;
+
+ rxbuf = &h3_uqs->qcs->rx.buf;
+ len = b_data(rxbuf);
+ qpack_debug_hexdump(stderr, "[QPACK-DEC-DEC] ", b_head(rxbuf), 0, len);
+
+ if (!len) {
+ qpack_debug_printf(stderr, "[QPACK-DEC-DEC] empty stream\n");
+ return 0;
+ }
+
+ inst = (unsigned char)*b_head(rxbuf) & QPACK_DEC_INST_BITMASK;
+ if (inst == QPACK_DEC_INST_ICINC) {
+ /* Insert count increment */
+ }
+ else if (inst & QPACK_DEC_INST_SACK) {
+ /* Section Acknowledgment */
+ }
+ else if (inst & QPACK_DEC_INST_SCCL) {
+ /* Stream cancellation */
+ }
+
+ return 1;
+}
+
+/* Decode a field section prefix made of <enc_ric> and <db> two varints.
+ * Also set the 'S' sign bit for <db>.
+ * Return a negative error if failed, 0 if not.
+ */
+static int qpack_decode_fs_pfx(uint64_t *enc_ric, uint64_t *db, int *sign_bit,
+ const unsigned char **raw, size_t *len)
+{
+ *enc_ric = qpack_get_varint(raw, len, 8);
+ if (*len == (uint64_t)-1)
+ return -QPACK_ERR_RIC;
+
+ *sign_bit = **raw & 0x8;
+ *db = qpack_get_varint(raw, len, 7);
+ if (*len == (uint64_t)-1)
+ return -QPACK_ERR_DB;
+
+ return 0;
+}
+
+/* Decode a field section from <len> bytes length <raw> buffer.
+ * Produces the output into <tmp> buffer.
+ */
+int qpack_decode_fs(const unsigned char *raw, size_t len, struct buffer *tmp)
+{
+ uint64_t enc_ric, db;
+ int s;
+ unsigned int efl_type;
+ int ret;
+
+ qpack_debug_hexdump(stderr, "[QPACK-DEC-FS] ", (const char *)raw, 0, len);
+
+ ret = qpack_decode_fs_pfx(&enc_ric, &db, &s, &raw, &len);
+ if (ret < 0) {
+ qpack_debug_printf(stderr, "##ERR@%d(%d)\n", __LINE__, ret);
+ goto out;
+ }
+
+ chunk_reset(tmp);
+ qpack_debug_printf(stderr, "enc_ric: %llu db: %llu s=%d\n",
+ (unsigned long long)enc_ric, (unsigned long long)db, !!s);
+ /* Decode field lines */
+ while (len) {
+ qpack_debug_hexdump(stderr, "raw ", (const char *)raw, 0, len);
+ efl_type = *raw & QPACK_EFL_BITMASK;
+ qpack_debug_printf(stderr, "efl_type=0x%02x\n", efl_type);
+ if (efl_type == QPACK_LFL_WPBNM) {
+ /* Literal field line with post-base name reference */
+ uint64_t index, length;
+ unsigned int n, h;
+
+ qpack_debug_printf(stderr, "literal field line with post-base name reference:");
+ n = *raw & 0x08;
+ index = qpack_get_varint(&raw, &len, 3);
+ if (len == (uint64_t)-1) {
+ qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__);
+ ret = -QPACK_ERR_TRUNCATED;
+ goto out;
+ }
+
+ qpack_debug_printf(stderr, " n=%d index=%llu", !!n, (unsigned long long)index);
+ h = *raw & 0x80;
+ length = qpack_get_varint(&raw, &len, 7);
+ if (len == (uint64_t)-1) {
+ qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__);
+ ret = -QPACK_ERR_TRUNCATED;
+ goto out;
+ }
+
+ qpack_debug_printf(stderr, " h=%d length=%llu", !!h, (unsigned long long)length);
+ /* XXX Value string XXX */
+ raw += length;
+ len -= length;
+ } else if (efl_type == QPACK_IFL_WPBI) {
+ /* Indexed field line with post-base index */
+ uint64_t index;
+
+ qpack_debug_printf(stderr, "indexed field line with post-base index:");
+ index = qpack_get_varint(&raw, &len, 4);
+ if (len == (uint64_t)-1) {
+ qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__);
+ ret = -QPACK_ERR_TRUNCATED;
+ goto out;
+ }
+
+ qpack_debug_printf(stderr, " index=%llu", (unsigned long long)index);
+ } else if (efl_type & QPACK_IFL_BIT) {
+ /* Indexed field line */
+ uint64_t index;
+ unsigned int t;
+
+ qpack_debug_printf(stderr, "indexed field line:");
+ t = efl_type & 0x40;
+ index = qpack_get_varint(&raw, &len, 6);
+ if (len == (uint64_t)-1) {
+ qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__);
+ ret = -QPACK_ERR_TRUNCATED;
+ goto out;
+ }
+
+ qpack_debug_printf(stderr, " t=%d index=%llu", !!t, (unsigned long long)index);
+ } else if (efl_type & QPACK_LFL_WNR_BIT) {
+ /* Literal field line with name reference */
+ uint64_t index, length;
+ unsigned int t, n, h;
+
+ qpack_debug_printf(stderr, "Literal field line with name reference:");
+ n = efl_type & 0x20;
+ t = efl_type & 0x10;
+ index = qpack_get_varint(&raw, &len, 4);
+ if (len == (uint64_t)-1) {
+ qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__);
+ ret = -QPACK_ERR_TRUNCATED;
+ goto out;
+ }
+
+ qpack_debug_printf(stderr, " n=%d t=%d index=%llu", !!n, !!t, (unsigned long long)index);
+ h = *raw & 0x80;
+ length = qpack_get_varint(&raw, &len, 7);
+ if (len == (uint64_t)-1) {
+ qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__);
+ ret = -QPACK_ERR_TRUNCATED;
+ goto out;
+ }
+
+ qpack_debug_printf(stderr, " h=%d length=%llu", !!h, (unsigned long long)length);
+ if (h) {
+ char *trash;
+ int nlen;
+
+ trash = chunk_newstr(tmp);
+ if (!trash) {
+ qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__);
+ ret = -QPACK_DECOMPRESSION_FAILED;
+ goto out;
+ }
+ nlen = huff_dec(raw, length, trash, tmp->size - tmp->data);
+ if (nlen == (uint32_t)-1) {
+ qpack_debug_printf(stderr, " can't decode huffman.\n");
+ ret = -QPACK_ERR_HUFFMAN;
+ goto out;
+ }
+
+ qpack_debug_printf(stderr, " [name huff %d->%d '%s']", (int)length, (int)nlen, trash);
+ }
+ /* XXX Value string XXX */
+ raw += length;
+ len -= length;
+ } else if (efl_type & QPACK_LFL_WLN_BIT) {
+ /* Literal field line with literal name */
+ unsigned int n, hname, hvalue;
+ uint64_t name_len, value_len;
+
+ qpack_debug_printf(stderr, "Literal field line with literal name:");
+ n = *raw & 0x10;
+ hname = *raw & 0x08;
+ name_len = qpack_get_varint(&raw, &len, 3);
+ if (len == (uint64_t)-1) {
+ qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__);
+ ret = -QPACK_ERR_TRUNCATED;
+ goto out;
+ }
+
+ qpack_debug_printf(stderr, " n=%d hanme=%d name_len=%llu", !!n, !!hname, (unsigned long long)name_len);
+ /* Name string */
+ raw += name_len;
+ len -= name_len;
+ hvalue = *raw & 0x80;
+ value_len = qpack_get_varint(&raw, &len, 7);
+ if (len == (uint64_t)-1) {
+ qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__);
+ ret = -QPACK_ERR_TRUNCATED;
+ goto out;
+ }
+
+ qpack_debug_printf(stderr, " hvalue=%d value_len=%llu", !!hvalue, (unsigned long long)value_len);
+
+ /* XXX Value string XXX */
+ raw += value_len;
+ len -= value_len;
+ }
+ qpack_debug_printf(stderr, "\n");
+ }
+
+ out:
+ qpack_debug_printf(stderr, "-- done: ret=%d\n", ret);
+ return ret;
+}
diff --git a/src/qpack-tbl.c b/src/qpack-tbl.c
index b30dc74..777ed8a 100644
--- a/src/qpack-tbl.c
+++ b/src/qpack-tbl.c
@@ -24,9 +24,12 @@
* OTHER DEALINGS IN THE SOFTWARE.
*/
+#include <inttypes.h>
+#include <stdio.h>
+
#include <import/ist.h>
#include <haproxy/http-hdr-t.h>
-#include <haproxy/qpack-tbl-t.h>
+#include <haproxy/qpack-tbl.h>
/* static header table as in draft-ietf-quic-qpack-20 Appendix A. [0] unused. */
const struct http_hdr qpack_sht[QPACK_SHT_SIZE] = {
@@ -139,3 +142,274 @@
[98] = { .n = IST("x-frame-options"), .v = IST("sameorigin") },
};
+struct pool_head *pool_head_qpack_tbl = NULL;
+
+#ifdef DEBUG_HPACK
+/* dump the whole dynamic header table */
+void qpack_dht_dump(FILE *out, const struct qpack_dht *dht)
+{
+ unsigned int i;
+ unsigned int slot;
+ char name[4096], value[4096];
+
+ for (i = HPACK_SHT_SIZE; i < HPACK_SHT_SIZE + dht->used; i++) {
+ slot = (qpack_get_dte(dht, i - HPACK_SHT_SIZE + 1) - dht->dte);
+ fprintf(out, "idx=%d slot=%u name=<%s> value=<%s> addr=%u-%u\n",
+ i, slot,
+ istpad(name, qpack_idx_to_name(dht, i)).ptr,
+ istpad(value, qpack_idx_to_value(dht, i)).ptr,
+ dht->dte[slot].addr, dht->dte[slot].addr+dht->dte[slot].nlen+dht->dte[slot].vlen-1);
+ }
+}
+
+/* check for the whole dynamic header table consistency, abort on failures */
+void qpack_dht_check_consistency(const struct qpack_dht *dht)
+{
+ unsigned slot = qpack_dht_get_tail(dht);
+ unsigned used2 = dht->used;
+ unsigned total = 0;
+
+ if (!dht->used)
+ return;
+
+ if (dht->front >= dht->wrap)
+ abort();
+
+ if (dht->used > dht->wrap)
+ abort();
+
+ if (dht->head >= dht->wrap)
+ abort();
+
+ while (used2--) {
+ total += dht->dte[slot].nlen + dht->dte[slot].vlen;
+ slot++;
+ if (slot >= dht->wrap)
+ slot = 0;
+ }
+
+ if (total != dht->total) {
+ fprintf(stderr, "%d: total=%u dht=%u\n", __LINE__, total, dht->total);
+ abort();
+ }
+}
+#endif // DEBUG_HPACK
+
+/* rebuild a new dynamic header table from <dht> with an unwrapped index and
+ * contents at the end. The new table is returned, the caller must not use the
+ * previous one anymore. NULL may be returned if no table could be allocated.
+ */
+static struct qpack_dht *qpack_dht_defrag(struct qpack_dht *dht)
+{
+ struct qpack_dht *alt_dht;
+ uint16_t old, new;
+ uint32_t addr;
+
+ /* Note: for small tables we could use alloca() instead but
+ * portability especially for large tables can be problematic.
+ */
+ alt_dht = qpack_dht_alloc();
+ if (!alt_dht)
+ return NULL;
+
+ alt_dht->total = dht->total;
+ alt_dht->used = dht->used;
+ alt_dht->wrap = dht->used;
+
+ new = 0;
+ addr = alt_dht->size;
+
+ if (dht->used) {
+ /* start from the tail */
+ old = qpack_dht_get_tail(dht);
+ do {
+ alt_dht->dte[new].nlen = dht->dte[old].nlen;
+ alt_dht->dte[new].vlen = dht->dte[old].vlen;
+ addr -= dht->dte[old].nlen + dht->dte[old].vlen;
+ alt_dht->dte[new].addr = addr;
+
+ memcpy((void *)alt_dht + alt_dht->dte[new].addr,
+ (void *)dht + dht->dte[old].addr,
+ dht->dte[old].nlen + dht->dte[old].vlen);
+
+ old++;
+ if (old >= dht->wrap)
+ old = 0;
+ new++;
+ } while (new < dht->used);
+ }
+
+ alt_dht->front = alt_dht->head = new - 1;
+
+ memcpy(dht, alt_dht, dht->size);
+ qpack_dht_free(alt_dht);
+
+ return dht;
+}
+
+/* Purges table dht until a header field of <needed> bytes fits according to
+ * the protocol (adding 32 bytes overhead). Returns non-zero on success, zero
+ * on failure (ie: table empty but still not sufficient). It must only be
+ * called when the table is not large enough to suit the new entry and there
+ * are some entries left. In case of doubt, use dht_make_room() instead.
+ */
+int __qpack_dht_make_room(struct qpack_dht *dht, unsigned int needed)
+{
+ unsigned int used = dht->used;
+ unsigned int wrap = dht->wrap;
+ unsigned int tail;
+
+ do {
+ tail = ((dht->head + 1U < used) ? wrap : 0) + dht->head + 1U - used;
+ dht->total -= dht->dte[tail].nlen + dht->dte[tail].vlen;
+ if (tail == dht->front)
+ dht->front = dht->head;
+ used--;
+ } while (used && used * 32 + dht->total + needed + 32 > dht->size);
+
+ dht->used = used;
+
+ /* realign if empty */
+ if (!used)
+ dht->front = dht->head = 0;
+
+ /* pack the table if it doesn't wrap anymore */
+ if (dht->head + 1U >= used)
+ dht->wrap = dht->head + 1;
+
+ /* no need to check for 'used' here as if it doesn't fit, used==0 */
+ return needed + 32 <= dht->size;
+}
+
+/* tries to insert a new header <name>:<value> in front of the current head. A
+ * negative value is returned on error.
+ */
+int qpack_dht_insert(struct qpack_dht *dht, struct ist name, struct ist value)
+{
+ unsigned int used;
+ unsigned int head;
+ unsigned int prev;
+ unsigned int wrap;
+ unsigned int tail;
+ uint32_t headroom, tailroom;
+
+ if (!qpack_dht_make_room(dht, name.len + value.len))
+ return 0;
+
+ /* Now there is enough room in the table, that's guaranteed by the
+ * protocol, but not necessarily where we need it.
+ */
+
+ used = dht->used;
+ if (!used) {
+ /* easy, the table was empty */
+ dht->front = dht->head = 0;
+ dht->wrap = dht->used = 1;
+ dht->total = 0;
+ head = 0;
+ dht->dte[head].addr = dht->size - (name.len + value.len);
+ goto copy;
+ }
+
+ /* compute the new head, used and wrap position */
+ prev = head = dht->head;
+ wrap = dht->wrap;
+ tail = qpack_dht_get_tail(dht);
+
+ used++;
+ head++;
+
+ if (head >= wrap) {
+ /* head is leading the entries, we either need to push the
+ * table further or to loop back to released entries. We could
+ * force to loop back when at least half of the allocatable
+ * entries are free but in practice it never happens.
+ */
+ if ((sizeof(*dht) + (wrap + 1) * sizeof(dht->dte[0]) <= dht->dte[dht->front].addr))
+ wrap++;
+ else if (head >= used) /* there's a hole at the beginning */
+ head = 0;
+ else {
+ /* no more room, head hits tail and the index cannot be
+ * extended, we have to realign the whole table.
+ */
+ if (!qpack_dht_defrag(dht))
+ return -1;
+
+ wrap = dht->wrap + 1;
+ head = dht->head + 1;
+ prev = head - 1;
+ tail = 0;
+ }
+ }
+ else if (used >= wrap) {
+ /* we've hit the tail, we need to reorganize the index so that
+ * the head is at the end (but not necessarily move the data).
+ */
+ if (!qpack_dht_defrag(dht))
+ return -1;
+
+ wrap = dht->wrap + 1;
+ head = dht->head + 1;
+ prev = head - 1;
+ tail = 0;
+ }
+
+ /* Now we have updated head, used and wrap, we know that there is some
+ * available room at least from the protocol's perspective. This space
+ * is split in two areas :
+ *
+ * 1: if the previous head was the front cell, the space between the
+ * end of the index table and the front cell's address.
+ * 2: if the previous head was the front cell, the space between the
+ * end of the tail and the end of the table ; or if the previous
+ * head was not the front cell, the space between the end of the
+ * tail and the head's address.
+ */
+ if (prev == dht->front) {
+ /* the area was contiguous */
+ headroom = dht->dte[dht->front].addr - (sizeof(*dht) + wrap * sizeof(dht->dte[0]));
+ tailroom = dht->size - dht->dte[tail].addr - dht->dte[tail].nlen - dht->dte[tail].vlen;
+ }
+ else {
+ /* it's already wrapped so we can't store anything in the headroom */
+ headroom = 0;
+ tailroom = dht->dte[prev].addr - dht->dte[tail].addr - dht->dte[tail].nlen - dht->dte[tail].vlen;
+ }
+
+ /* We can decide to stop filling the headroom as soon as there's enough
+ * room left in the tail to suit the protocol, but tests show that in
+ * practice it almost never happens in other situations so the extra
+ * test is useless and we simply fill the headroom as long as it's
+ * available and we don't wrap.
+ */
+ if (prev == dht->front && headroom >= name.len + value.len) {
+ /* install upfront and update ->front */
+ dht->dte[head].addr = dht->dte[dht->front].addr - (name.len + value.len);
+ dht->front = head;
+ }
+ else if (tailroom >= name.len + value.len) {
+ dht->dte[head].addr = dht->dte[tail].addr + dht->dte[tail].nlen + dht->dte[tail].vlen + tailroom - (name.len + value.len);
+ }
+ else {
+ /* need to defragment the table before inserting upfront */
+ dht = qpack_dht_defrag(dht);
+ wrap = dht->wrap + 1;
+ head = dht->head + 1;
+ dht->dte[head].addr = dht->dte[dht->front].addr - (name.len + value.len);
+ dht->front = head;
+ }
+
+ dht->wrap = wrap;
+ dht->head = head;
+ dht->used = used;
+
+ copy:
+ dht->total += name.len + value.len;
+ dht->dte[head].nlen = name.len;
+ dht->dte[head].vlen = value.len;
+
+ memcpy((void *)dht + dht->dte[head].addr, name.ptr, name.len);
+ memcpy((void *)dht + dht->dte[head].addr + name.len, value.ptr, value.len);
+ return 0;
+}