| /* |
| * HPACK header table management (RFC7541) - type definitions |
| * |
| * Copyright (C) 2014-2020 Willy Tarreau <willy@haproxy.org> |
| * Copyright (C) 2017 HAProxy Technologies |
| * |
| * 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_HPACK_TBL_T_H |
| #define _HAPROXY_HPACK_TBL_T_H |
| |
| #include <inttypes.h> |
| |
| /* Dynamic Headers Table, usable for tables up to 4GB long and values of 64kB-1. |
| * The model can be improved by using offsets relative to the table entry's end |
| * or to the end of the area, or by moving the descriptors at the end of the |
| * table and the data at the beginning. This entry is 8 bytes long, which is 1/4 |
| * of the bookkeeping planned by the HPACK spec. Thus it saves 24 bytes per |
| * header field, meaning that even with a single header, 24 extra bytes can be |
| * stored (ie one such descriptor). At 29.2 average bytes per header field as |
| * found in the hpack test case, that's slightly more than 1.5kB of space saved |
| * from a 4kB block, resulting in contiguous space almost always being |
| * available. |
| * |
| * Principle: the table is stored in a contiguous array containing both the |
| * descriptors and the contents. Descriptors are stored at the beginning of the |
| * array while contents are stored starting from the end. Most of the time there |
| * is enough room left in the table to insert a new header field, thanks to the |
| * savings on the descriptor size. Thus by inserting headers from the end it's |
| * possible to maximize the delay before a collision of DTEs and data. In order |
| * to always insert from the right, we need to keep a reference to the latest |
| * inserted element and look before it. The last inserted cell's address defines |
| * the lowest known address still in use, unless the area wraps in which case |
| * the available space lies between the end of the tail and the beginning of the |
| * head. |
| * |
| * In order to detect collisions between data blocks and DTEs, we also maintain |
| * an index to the lowest element facing the DTE table, called "front". This one |
| * is updated each time an element is inserted before it. Once the buffer wraps, |
| * this element doesn't have to be updated anymore until it is released, in |
| * which case the buffer doesn't wrap anymore and the front element becomes the |
| * head again. |
| * |
| * Various heuristics are possible concerning the opportunity to wrap the |
| * entries to limit the risk of collisions with the DTE, but experimentation |
| * shows that thanks to the important savings made on the descriptors, the |
| * likeliness of finding a large amount of free space at the end of the area is |
| * much higher than the risk of colliding, so in the end the most naive |
| * algorithms work pretty fine. Typical ratios of 1 collision per 2000 requests |
| * have been observed. |
| * |
| * The defragmentation should be rare ; a study on live data shows on average |
| * 29.2 bytes used per header field. This plus the 32 bytes overhead fix an |
| * average of 66.9 header fields per 4kB table. This brings a 1606 bytes saving |
| * using the current storage description, ensuring that oldest headers are |
| * linearly removed by the sender before fragmentation occurs. This means that |
| * for all smaller header fields there will not be any requirement to defragment |
| * the area and most of the time it will even be possible to copy the old values |
| * directly within the buffer after creating a new entry. On average within the |
| * available space there will be enough room to store 1606/(29.2+8)=43 extra |
| * header fields without switching to another place. |
| * |
| * The table header fits in the table itself, it only takes 16 bytes, so in the |
| * worst case (1 single header) it's possible to store 4096 - 16 - 8 = 4072 |
| * data bytes, which is larger than the 4064 the protocol requires (4096 - 32). |
| */ |
| |
| /* |
| * 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 hpack_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 hpack_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 hpack_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 hpack_dte dte[VAR_ARRAY]; /* dynamic table entries */ |
| }; |
| |
| /* supported hpack encoding/decoding errors */ |
| enum { |
| HPACK_ERR_NONE = 0, /* no error */ |
| HPACK_ERR_ALLOC_FAIL, /* memory allocation error */ |
| HPACK_ERR_UNKNOWN_OPCODE, /* invalid first byte */ |
| HPACK_ERR_TRUNCATED, /* truncated stream */ |
| HPACK_ERR_HUFFMAN, /* huffman decoding error */ |
| HPACK_ERR_INVALID_PHDR, /* invalid pseudo header field name */ |
| HPACK_ERR_MISPLACED_PHDR, /* pseudo header field after a regular header field */ |
| HPACK_ERR_DUPLICATE_PHDR, /* duplicate pseudo header field */ |
| HPACK_ERR_DHT_INSERT_FAIL, /* failed to insert into DHT */ |
| HPACK_ERR_TOO_LARGE, /* decoded request/response is too large */ |
| HPACK_ERR_MISSING_METHOD, /* :method is missing */ |
| HPACK_ERR_MISSING_SCHEME, /* :scheme is missing */ |
| HPACK_ERR_MISSING_PATH, /* :path is missing */ |
| HPACK_ERR_MISSING_AUTHORITY, /* :authority is missing with CONNECT */ |
| HPACK_ERR_SCHEME_NOT_ALLOWED, /* :scheme not allowed with CONNECT */ |
| HPACK_ERR_PATH_NOT_ALLOWED, /* :path not allowed with CONNECT */ |
| HPACK_ERR_INVALID_ARGUMENT, /* an invalid argument was passed */ |
| }; |
| |
| /* static header table as in RFC7541 Appendix A. [0] unused. */ |
| #define HPACK_SHT_SIZE 62 |
| |
| #endif /* _HAPROXY_HPACK_TBL_T_H */ |