1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
/*
* 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 */
|
