Adding upstream version 2.9.5.upstream/2.9.5

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 415 insertions, 0 deletions

diff --git a/src/qpack-tbl.c b/src/qpack-tbl.c
new file mode 100644
index 0000000..7c59fd2
--- /dev/null
+++ b/src/qpack-tbl.c
@@ -0,0 +1,415 @@
+/*
+ * QPACK header table management (draft-ietf-quic-qpack-20)
+ *
+ * Copyright 2020 HAProxy Technologies, Frederic Lecaille <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.
+ */
+
+#include <inttypes.h>
+#include <stdio.h>
+
+#include <import/ist.h>
+#include <haproxy/http-hdr-t.h>
+#include <haproxy/qpack-tbl.h>
+
+/* static header table as in draft-ietf-quic-qpack-20 Appendix A. */
+const struct http_hdr qpack_sht[QPACK_SHT_SIZE] = {
+	[ 0] = { .n = IST(":authority"),                       .v = IST("")                         },
+	[ 1] = { .n = IST(":path"),                            .v = IST("/")                        },
+	[ 2] = { .n = IST("age"),                              .v = IST("0")                        },
+	[ 3] = { .n = IST("content-disposition"),              .v = IST("")                         },
+	[ 4] = { .n = IST("content-length"),                   .v = IST("0")                        },
+	[ 5] = { .n = IST("cookie"),                           .v = IST("")                         },
+	[ 6] = { .n = IST("date"),                             .v = IST("")                         },
+	[ 7] = { .n = IST("etag"),                             .v = IST("")                         },
+	[ 8] = { .n = IST("if-modified-since"),                .v = IST("")                         },
+	[ 9] = { .n = IST("if-none-match"),                    .v = IST("")                         },
+	[10] = { .n = IST("last-modified"),                    .v = IST("")                         },
+	[11] = { .n = IST("link"),                             .v = IST("")                         },
+	[12] = { .n = IST("location"),                         .v = IST("")                         },
+	[13] = { .n = IST("referer"),                          .v = IST("")                         },
+	[14] = { .n = IST("set-cookie"),                       .v = IST("")                         },
+	[15] = { .n = IST(":method"),                          .v = IST("CONNECT")                  },
+	[16] = { .n = IST(":method"),                          .v = IST("DELETE")                   },
+	[17] = { .n = IST(":method"),                          .v = IST("GET")                      },
+	[18] = { .n = IST(":method"),                          .v = IST("HEAD")                     },
+	[19] = { .n = IST(":method"),                          .v = IST("OPTIONS")                  },
+	[20] = { .n = IST(":method"),                          .v = IST("POST")                     },
+	[21] = { .n = IST(":method"),                          .v = IST("PUT")                      },
+	[22] = { .n = IST(":scheme"),                          .v = IST("http")                     },
+	[23] = { .n = IST(":scheme"),                          .v = IST("https")                    },
+	[24] = { .n = IST(":status"),                          .v = IST("103")                      },
+	[25] = { .n = IST(":status"),                          .v = IST("200")                      },
+	[26] = { .n = IST(":status"),                          .v = IST("304")                      },
+	[27] = { .n = IST(":status"),                          .v = IST("404")                      },
+	[28] = { .n = IST(":status"),                          .v = IST("503")                      },
+	[29] = { .n = IST("accept"),                           .v = IST("*/*")                      },
+	[30] = { .n = IST("accept"),                           .v = IST("application/dns-message")  },
+	[31] = { .n = IST("accept-encoding"),                  .v = IST("gzip, deflate, br")        },
+	[32] = { .n = IST("accept-ranges"),                    .v = IST("bytes")                    },
+	[33] = { .n = IST("access-control-allow-headers"),     .v = IST("cache-control")            },
+	[34] = { .n = IST("access-control-allow-headers"),     .v = IST("content-type")             },
+	[35] = { .n = IST("access-control-allow-origin"),      .v = IST("*")                        },
+	[36] = { .n = IST("cache-control"),                    .v = IST("max-age=0")                },
+	[37] = { .n = IST("cache-control"),                    .v = IST("max-age=2592000")          },
+	[38] = { .n = IST("cache-control"),                    .v = IST("max-age=604800")           },
+	[39] = { .n = IST("cache-control"),                    .v = IST("no-cache")                 },
+	[40] = { .n = IST("cache-control"),                    .v = IST("no-store")                 },
+	[41] = { .n = IST("cache-control"),                    .v = IST("public, max-age=31536000") },
+	[42] = { .n = IST("content-encoding"),                 .v = IST("br")                       },
+	[43] = { .n = IST("content-encoding"),                 .v = IST("gzip")                     },
+	[44] = { .n = IST("content-type"),                     .v = IST("application/dns-message")  },
+	[45] = { .n = IST("content-type"),                     .v = IST("application/javascript")   },
+	[46] = { .n = IST("content-type"),                     .v = IST("application/json")         },
+	[47] = { .n = IST("content-type"),                     .v = IST("application/"
+	                                                                "x-www-form-urlencoded")    },
+	[48] = { .n = IST("content-type"),                     .v = IST("image/gif")                },
+	[49] = { .n = IST("content-type"),                     .v = IST("image/jpeg")               },
+	[50] = { .n = IST("content-type"),                     .v = IST("image/png")                },
+	[51] = { .n = IST("content-type"),                     .v = IST("text/css")                 },
+	[52] = { .n = IST("content-type"),                     .v = IST("text/html;"
+	                                                                " charset=utf-8")           },
+	[53] = { .n = IST("content-type"),                     .v = IST("text/plain")               },
+	[54] = { .n = IST("content-type"),                     .v = IST("text/plain;"
+	                                                                "charset=utf-8")            },
+	[55] = { .n = IST("range"),                            .v = IST("bytes=0-")                 },
+	[56] = { .n = IST("strict-transport-security"),        .v = IST("max-age=31536000")         },
+	[57] = { .n = IST("strict-transport-security"),        .v = IST("max-age=31536000;"
+	                                                                " includesubdomains")       },
+	[58] = { .n = IST("strict-transport-security"),        .v = IST("max-age=31536000;"
+	                                                                " includesubdomains;"
+	                                                                " preload")                 },
+	[59] = { .n = IST("vary"),                             .v = IST("accept-encoding")          },
+	[60] = { .n = IST("vary"),                             .v = IST("origin")                   },
+	[61] = { .n = IST("x-content-type-options"),           .v = IST("nosniff")                  },
+	[62] = { .n = IST("x-xss-protection"),                 .v = IST("1; mode=block")            },
+	[63] = { .n = IST(":status"),                          .v = IST("100")                      },
+	[64] = { .n = IST(":status"),                          .v = IST("204")                      },
+	[65] = { .n = IST(":status"),                          .v = IST("206")                      },
+	[66] = { .n = IST(":status"),                          .v = IST("302")                      },
+	[67] = { .n = IST(":status"),                          .v = IST("400")                      },
+	[68] = { .n = IST(":status"),                          .v = IST("403")                      },
+	[69] = { .n = IST(":status"),                          .v = IST("421")                      },
+	[70] = { .n = IST(":status"),                          .v = IST("425")                      },
+	[71] = { .n = IST(":status"),                          .v = IST("500")                      },
+	[72] = { .n = IST("accept-language"),                  .v = IST("")                         },
+	[73] = { .n = IST("access-control-allow-credentials"), .v = IST("FALSE")                    },
+	[74] = { .n = IST("access-control-allow-credentials"), .v = IST("TRUE")                     },
+	[75] = { .n = IST("access-control-allow-headers"),     .v = IST("*")                        },
+	[76] = { .n = IST("access-control-allow-methods"),     .v = IST("get")                      },
+	[77] = { .n = IST("access-control-allow-methods"),     .v = IST("get, post, options")       },
+	[78] = { .n = IST("access-control-allow-methods"),     .v = IST("options")                  },
+	[79] = { .n = IST("access-control-expose-headers"),    .v = IST("content-length")           },
+	[80] = { .n = IST("access-control-request-headers"),   .v = IST("content-type")             },
+	[81] = { .n = IST("access-control-request-method"),    .v = IST("get")                      },
+	[82] = { .n = IST("access-control-request-method"),    .v = IST("post")                     },
+	[83] = { .n = IST("alt-svc"),                          .v = IST("clear")                    },
+	[84] = { .n = IST("authorization"),                    .v = IST("")                         },
+	[85] = { .n = IST("content-security-policy"),          .v = IST("script-src 'none';"
+	                                                                " object-src 'none';"
+	                                                                " base-uri 'none'")         },
+	[86] = { .n = IST("early-data"),                       .v = IST("1")                        },
+	[87] = { .n = IST("expect-ct"),                        .v = IST("")                         },
+	[88] = { .n = IST("forwarded"),                        .v = IST("")                         },
+	[89] = { .n = IST("if-range"),                         .v = IST("")                         },
+	[90] = { .n = IST("origin"),                           .v = IST("")                         },
+	[91] = { .n = IST("purpose"),                          .v = IST("prefetch")                 },
+	[92] = { .n = IST("server"),                           .v = IST("")                         },
+	[93] = { .n = IST("timing-allow-origin"),              .v = IST("*")                        },
+	[94] = { .n = IST("upgrade-insecure-requests"),        .v = IST("1")                        },
+	[95] = { .n = IST("user-agent"),                       .v = IST("")                         },
+	[96] = { .n = IST("x-forwarded-for"),                  .v = IST("")                         },
+	[97] = { .n = IST("x-frame-options"),                  .v = IST("deny")                     },
+	[98] = { .n = IST("x-frame-options"),                  .v = IST("sameorigin")               },
+};
+
+struct pool_head *pool_head_qpack_tbl = NULL;
+
+#ifdef DEBUG_QPACK
+/* 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 = QPACK_SHT_SIZE; i < QPACK_SHT_SIZE + dht->used; i++) {
+		slot = (qpack_get_dte(dht, i - QPACK_SHT_SIZE + 1) - dht->dte);
+		fprintf(out, "idx=%u 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_QPACK
+
+/* 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;
+}