1 /*
2  * Copyright (c) 2014-2016 DeNA Co., Ltd., Kazuho Oku, Fastly, Inc.
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a copy
5  * of this software and associated documentation files (the "Software"), to
6  * deal in the Software without restriction, including without limitation the
7  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
8  * sell copies of the Software, and to permit persons to whom the Software is
9  * furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice shall be included in
12  * all copies or substantial portions of the Software.
13  *
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20  * IN THE SOFTWARE.
21  */
22 #include <stddef.h>
23 #include <stdint.h>
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include "h2o/hpack.h"
27 #include "h2o/http2_common.h"
28 
29 #define HEADER_TABLE_OFFSET 62
30 #define HEADER_TABLE_ENTRY_SIZE_OFFSET 32
31 #define DYNAMIC_TABLE_SIZE_UPDATE_MAX_SIZE 5
32 #define STATUS_HEADER_MAX_SIZE 5
33 #define CONTENT_LENGTH_HEADER_MAX_SIZE                                                                                             \
34     (3 + sizeof(H2O_SIZE_T_LONGEST_STR) - 1) /* uses Literal Header Field without Indexing (RFC7541 6.2.2) */
35 
36 #include "hpack_huffman_table.h"
37 
value_is_part_of_static_table(const h2o_iovec_t * value)38 static inline int value_is_part_of_static_table(const h2o_iovec_t *value)
39 {
40     return &h2o_hpack_static_table[0].value <= value &&
41            value <= &h2o_hpack_static_table[sizeof(h2o_hpack_static_table) / sizeof(h2o_hpack_static_table[0]) - 1].value;
42 }
43 
alloc_buf(h2o_mem_pool_t * pool,size_t len)44 static h2o_iovec_t *alloc_buf(h2o_mem_pool_t *pool, size_t len)
45 {
46     h2o_iovec_t *buf = h2o_mem_alloc_shared(pool, sizeof(h2o_iovec_t) + len + 1, NULL);
47     buf->base = (char *)buf + sizeof(h2o_iovec_t);
48     buf->len = len;
49     return buf;
50 }
51 
h2o_hpack_decode_int(const uint8_t ** src,const uint8_t * src_end,unsigned prefix_bits)52 int64_t h2o_hpack_decode_int(const uint8_t **src, const uint8_t *src_end, unsigned prefix_bits)
53 {
54     uint64_t value;
55     unsigned shift;
56     uint8_t prefix_max = (1 << prefix_bits) - 1;
57 
58     if (*src >= src_end)
59         return H2O_HTTP2_ERROR_INCOMPLETE;
60 
61     value = *(*src)++ & prefix_max;
62     if (value != prefix_max)
63         return (int64_t)value;
64 
65     /* decode upto 8 octets (excluding prefix), that are guaranteed not to cause overflow */
66     value = prefix_max;
67     for (shift = 0; shift < 56; shift += 7) {
68         if (*src == src_end)
69             return H2O_HTTP2_ERROR_INCOMPLETE;
70         value += (uint64_t)(**src & 127) << shift;
71         if ((*(*src)++ & 128) == 0)
72             return (int64_t)value;
73     }
74     /* handling the 9th octet */
75     if (*src == src_end)
76         return H2O_HTTP2_ERROR_INCOMPLETE;
77     if ((**src & 128) != 0)
78         return H2O_HTTP2_ERROR_COMPRESSION;
79     value += (uint64_t)(*(*src)++ & 127) << shift;
80     if (value > (uint64_t)INT64_MAX)
81         return H2O_HTTP2_ERROR_COMPRESSION;
82     return value;
83 }
84 
huffdecode4(char * dst,uint8_t in,uint8_t * state,int * maybe_eos,uint8_t * seen_char_types)85 static char *huffdecode4(char *dst, uint8_t in, uint8_t *state, int *maybe_eos, uint8_t *seen_char_types)
86 {
87     const nghttp2_huff_decode *entry = huff_decode_table[*state] + in;
88 
89     if ((entry->flags & NGHTTP2_HUFF_FAIL) != 0)
90         return NULL;
91     if ((entry->flags & NGHTTP2_HUFF_SYM) != 0) {
92         *dst++ = entry->sym;
93         *seen_char_types |= (entry->flags & NGHTTP2_HUFF_INVALID_CHARS);
94     }
95     *state = entry->state;
96     *maybe_eos = (entry->flags & NGHTTP2_HUFF_ACCEPTED) != 0;
97 
98     return dst;
99 }
100 
101 const char h2o_hpack_err_found_upper_case_in_header_name[] = "found an upper-case letter in header name";
102 const char h2o_hpack_soft_err_found_invalid_char_in_header_name[] = "found an invalid character in header name";
103 const char h2o_hpack_soft_err_found_invalid_char_in_header_value[] = "found an invalid character in header value";
104 
h2o_hpack_decode_huffman(char * _dst,unsigned * soft_errors,const uint8_t * src,size_t len,int is_name,const char ** err_desc)105 size_t h2o_hpack_decode_huffman(char *_dst, unsigned *soft_errors, const uint8_t *src, size_t len, int is_name,
106                                 const char **err_desc)
107 {
108     char *dst = _dst;
109     const uint8_t *src_end = src + len;
110     uint8_t state = 0, seen_char_types = 0;
111     int maybe_eos = 1;
112 
113     /* decode */
114     for (; src < src_end; src++) {
115         if ((dst = huffdecode4(dst, *src >> 4, &state, &maybe_eos, &seen_char_types)) == NULL)
116             return SIZE_MAX;
117         if ((dst = huffdecode4(dst, *src & 0xf, &state, &maybe_eos, &seen_char_types)) == NULL)
118             return SIZE_MAX;
119     }
120     if (!maybe_eos)
121         return SIZE_MAX;
122 
123     /* validate */
124     if (is_name) {
125         if (dst == _dst)
126             return SIZE_MAX;
127         /* pseudo-headers are checked later in `decode_header` */
128         if ((seen_char_types & NGHTTP2_HUFF_INVALID_FOR_HEADER_NAME) != 0 && _dst[0] != ':') {
129             if ((seen_char_types & NGHTTP2_HUFF_UPPER_CASE_CHAR) != 0) {
130                 *err_desc = h2o_hpack_err_found_upper_case_in_header_name;
131                 return SIZE_MAX;
132             } else {
133                 *soft_errors |= H2O_HPACK_SOFT_ERROR_BIT_INVALID_NAME;
134             }
135         }
136     } else {
137         if ((seen_char_types & NGHTTP2_HUFF_INVALID_FOR_HEADER_VALUE) != 0)
138             *soft_errors |= H2O_HPACK_SOFT_ERROR_BIT_INVALID_VALUE;
139     }
140 
141     return dst - _dst;
142 }
143 
144 /* validate a header name against https://tools.ietf.org/html/rfc7230#section-3.2,
145  * in addition to that, we disallow upper case chars as well.
146  * This sets @err_desc for all invalid characters, but only returns true
147  * for upper case characters, this is because we return a protocol error
148  * in that case. */
h2o_hpack_validate_header_name(unsigned * soft_errors,const char * s,size_t len,const char ** err_desc)149 int h2o_hpack_validate_header_name(unsigned *soft_errors, const char *s, size_t len, const char **err_desc)
150 {
151     /* all printable chars, except upper case and separator characters */
152     static const char valid_h2_header_name_char[] = {
153         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*    0-31 */
154         0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, /*   32-63 */
155         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, /*   64-95 */
156         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, /*  96-127 */
157         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 128-159 */
158         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 160-191 */
159         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 192-223 */
160         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 224-255 */
161     };
162 
163     for (; len != 0; ++s, --len) {
164         unsigned char ch = (unsigned char)*s;
165         if (!valid_h2_header_name_char[ch]) {
166             if (ch - 'A' < 26U) {
167                 *err_desc = h2o_hpack_err_found_upper_case_in_header_name;
168                 return 0;
169             }
170             *soft_errors |= H2O_HPACK_SOFT_ERROR_BIT_INVALID_NAME;
171         }
172     }
173     return 1;
174 }
175 
176 /* validate a header value against https://tools.ietf.org/html/rfc7230#section-3.2 */
h2o_hpack_validate_header_value(unsigned * soft_errors,const char * s,size_t len)177 void h2o_hpack_validate_header_value(unsigned *soft_errors, const char *s, size_t len)
178 {
179     /* all printable chars + horizontal tab */
180     static const char valid_h2_field_value_char[] = {
181         0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*    0-31 */
182         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /*   32-63 */
183         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /*   64-95 */
184         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, /*  96-127 */
185         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 128-159 */
186         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 160-191 */
187         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 192-223 */
188         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 224-255 */
189     };
190 
191     for (; len != 0; ++s, --len) {
192         unsigned char ch = (unsigned char)*s;
193         if (!valid_h2_field_value_char[ch]) {
194             *soft_errors |= H2O_HPACK_SOFT_ERROR_BIT_INVALID_VALUE;
195             break;
196         }
197     }
198 }
199 
decode_string(h2o_mem_pool_t * pool,unsigned * soft_errors,const uint8_t ** src,const uint8_t * src_end,int is_header_name,const char ** err_desc)200 static h2o_iovec_t *decode_string(h2o_mem_pool_t *pool, unsigned *soft_errors, const uint8_t **src, const uint8_t *src_end,
201                                   int is_header_name, const char **err_desc)
202 {
203     h2o_iovec_t *ret;
204     int is_huffman;
205     int64_t len;
206 
207     if (*src >= src_end)
208         return NULL;
209 
210     is_huffman = (**src & 0x80) != 0;
211     if ((len = h2o_hpack_decode_int(src, src_end, 7)) < 0)
212         return NULL;
213 
214     if (is_huffman) {
215         if (len > src_end - *src)
216             return NULL;
217         ret = alloc_buf(pool, len * 2); /* max compression ratio is >= 0.5 */
218         if ((ret->len = h2o_hpack_decode_huffman(ret->base, soft_errors, *src, len, is_header_name, err_desc)) == SIZE_MAX)
219             return NULL;
220         ret->base[ret->len] = '\0';
221     } else {
222         if (len > src_end - *src)
223             return NULL;
224         if (is_header_name) {
225             /* pseudo-headers are checked later in `decode_header` */
226             if (**src != (uint8_t)':' && !h2o_hpack_validate_header_name(soft_errors, (char *)*src, len, err_desc))
227                 return NULL;
228         } else {
229             h2o_hpack_validate_header_value(soft_errors, (char *)*src, len);
230         }
231         ret = alloc_buf(pool, len);
232         memcpy(ret->base, *src, len);
233         ret->base[len] = '\0';
234     }
235     *src += len;
236 
237     return ret;
238 }
239 
header_table_evict_one(h2o_hpack_header_table_t * table)240 static void header_table_evict_one(h2o_hpack_header_table_t *table)
241 {
242     struct st_h2o_hpack_header_table_entry_t *entry;
243     assert(table->num_entries != 0);
244 
245     entry = h2o_hpack_header_table_get(table, --table->num_entries);
246     table->hpack_size -= entry->name->len + entry->value->len + HEADER_TABLE_ENTRY_SIZE_OFFSET;
247     if (!h2o_iovec_is_token(entry->name))
248         h2o_mem_release_shared(entry->name);
249     if (!value_is_part_of_static_table(entry->value))
250         h2o_mem_release_shared(entry->value);
251     memset(entry, 0, sizeof(*entry));
252 }
253 
header_table_add(h2o_hpack_header_table_t * table,size_t size_add,size_t max_num_entries)254 static struct st_h2o_hpack_header_table_entry_t *header_table_add(h2o_hpack_header_table_t *table, size_t size_add,
255                                                                   size_t max_num_entries)
256 {
257     /* adjust the size */
258     while (table->num_entries != 0 && table->hpack_size + size_add > table->hpack_capacity)
259         header_table_evict_one(table);
260     while (max_num_entries <= table->num_entries)
261         header_table_evict_one(table);
262     if (table->num_entries == 0) {
263         assert(table->hpack_size == 0);
264         if (size_add > table->hpack_capacity)
265             return NULL;
266     }
267     table->hpack_size += size_add;
268 
269     /* grow the entries if full */
270     if (table->num_entries == table->entry_capacity) {
271         size_t new_capacity = table->num_entries * 2;
272         if (new_capacity < 16)
273             new_capacity = 16;
274         struct st_h2o_hpack_header_table_entry_t *new_entries =
275             h2o_mem_alloc(new_capacity * sizeof(struct st_h2o_hpack_header_table_entry_t));
276         if (table->num_entries != 0) {
277             size_t src_index = table->entry_start_index, dst_index = 0;
278             do {
279                 new_entries[dst_index] = table->entries[src_index];
280                 ++dst_index;
281                 src_index = (src_index + 1) % table->entry_capacity;
282             } while (dst_index != table->num_entries);
283         }
284         memset(new_entries + table->num_entries, 0, sizeof(*new_entries) * (new_capacity - table->num_entries));
285         free(table->entries);
286         table->entries = new_entries;
287         table->entry_capacity = new_capacity;
288         table->entry_start_index = 0;
289     }
290 
291     ++table->num_entries;
292     table->entry_start_index = (table->entry_start_index + table->entry_capacity - 1) % table->entry_capacity;
293     return table->entries + table->entry_start_index;
294 }
295 
h2o_hpack_decode_header(h2o_mem_pool_t * pool,void * _hpack_header_table,h2o_iovec_t ** _name,h2o_iovec_t * _value,const uint8_t ** const src,const uint8_t * src_end,const char ** err_desc)296 int h2o_hpack_decode_header(h2o_mem_pool_t *pool, void *_hpack_header_table, h2o_iovec_t **_name, h2o_iovec_t *_value,
297                             const uint8_t **const src, const uint8_t *src_end, const char **err_desc)
298 {
299     h2o_hpack_header_table_t *hpack_header_table = _hpack_header_table;
300     h2o_iovec_t *name = NULL, *value = NULL;
301     int64_t index = 0;
302     int value_is_indexed = 0, do_index = 0;
303 
304 Redo:
305     if (*src >= src_end)
306         return H2O_HTTP2_ERROR_COMPRESSION;
307 
308     /* determine the mode and handle accordingly */
309     if (**src >= 128) {
310         /* indexed header field representation */
311         if ((index = h2o_hpack_decode_int(src, src_end, 7)) <= 0)
312             return H2O_HTTP2_ERROR_COMPRESSION;
313         value_is_indexed = 1;
314     } else if (**src >= 64) {
315         /* literal header field with incremental handling */
316         if (**src == 64) {
317             ++*src;
318         } else if ((index = h2o_hpack_decode_int(src, src_end, 6)) <= 0) {
319             return H2O_HTTP2_ERROR_COMPRESSION;
320         }
321         do_index = 1;
322     } else if (**src < 32) {
323         /* literal header field without indexing / never indexed */
324         if ((**src & 0xf) == 0) {
325             ++*src;
326         } else if ((index = h2o_hpack_decode_int(src, src_end, 4)) <= 0) {
327             return H2O_HTTP2_ERROR_COMPRESSION;
328         }
329     } else {
330         /* size update */
331         int64_t new_capacity;
332         if ((new_capacity = h2o_hpack_decode_int(src, src_end, 5)) < 0) {
333             return H2O_HTTP2_ERROR_COMPRESSION;
334         }
335         if (new_capacity > hpack_header_table->hpack_max_capacity) {
336             return H2O_HTTP2_ERROR_COMPRESSION;
337         }
338         hpack_header_table->hpack_capacity = (size_t)new_capacity;
339         while (hpack_header_table->num_entries != 0 && hpack_header_table->hpack_size > hpack_header_table->hpack_capacity) {
340             header_table_evict_one(hpack_header_table);
341         }
342         goto Redo;
343     }
344 
345     /* determine the header */
346     unsigned soft_errors = 0;
347     if (index > 0) {
348         /* existing name (and value?) */
349         if (index < HEADER_TABLE_OFFSET) {
350             name = (h2o_iovec_t *)h2o_hpack_static_table[index - 1].name;
351             if (value_is_indexed)
352                 value = (h2o_iovec_t *)&h2o_hpack_static_table[index - 1].value;
353         } else if (index - HEADER_TABLE_OFFSET < hpack_header_table->num_entries) {
354             struct st_h2o_hpack_header_table_entry_t *entry =
355                 h2o_hpack_header_table_get(hpack_header_table, index - HEADER_TABLE_OFFSET);
356             soft_errors = entry->soft_errors;
357             name = entry->name;
358             if (!h2o_iovec_is_token(name))
359                 h2o_mem_link_shared(pool, name);
360             if (value_is_indexed) {
361                 value = entry->value;
362                 h2o_mem_link_shared(pool, value);
363             }
364         } else {
365             return H2O_HTTP2_ERROR_COMPRESSION;
366         }
367     } else {
368         /* non-existing name */
369         const h2o_token_t *name_token;
370         if ((name = decode_string(pool, &soft_errors, src, src_end, 1, err_desc)) == NULL) {
371             if (*err_desc == h2o_hpack_err_found_upper_case_in_header_name)
372                 return H2O_HTTP2_ERROR_PROTOCOL;
373             return H2O_HTTP2_ERROR_COMPRESSION;
374         }
375         /* predefined header names should be interned */
376         if ((name_token = h2o_lookup_token(name->base, name->len)) != NULL)
377             name = (h2o_iovec_t *)&name_token->buf;
378     }
379 
380     /* determine the value (if necessary) */
381     if (!value_is_indexed) {
382         soft_errors &= ~H2O_HPACK_SOFT_ERROR_BIT_INVALID_VALUE;
383         if ((value = decode_string(pool, &soft_errors, src, src_end, 0, err_desc)) == NULL)
384             return H2O_HTTP2_ERROR_COMPRESSION;
385     }
386 
387     /* add the decoded header to the header table if necessary */
388     if (do_index) {
389         struct st_h2o_hpack_header_table_entry_t *entry =
390             header_table_add(hpack_header_table, name->len + value->len + HEADER_TABLE_ENTRY_SIZE_OFFSET, SIZE_MAX);
391         if (entry != NULL) {
392             entry->soft_errors = soft_errors;
393             entry->name = name;
394             if (!h2o_iovec_is_token(entry->name))
395                 h2o_mem_addref_shared(entry->name);
396             entry->value = value;
397             if (!value_is_part_of_static_table(entry->value))
398                 h2o_mem_addref_shared(entry->value);
399         }
400     }
401 
402     *_name = name;
403     *_value = *value;
404     if (soft_errors != 0) {
405         *err_desc = (soft_errors & H2O_HPACK_SOFT_ERROR_BIT_INVALID_NAME) != 0
406                         ? h2o_hpack_soft_err_found_invalid_char_in_header_name
407                         : h2o_hpack_soft_err_found_invalid_char_in_header_value;
408         return H2O_HTTP2_ERROR_INVALID_HEADER_CHAR;
409     } else {
410         return 0;
411     }
412 }
413 
encode_status(uint8_t * dst,int status)414 static uint8_t *encode_status(uint8_t *dst, int status)
415 {
416     /* see also: STATUS_HEADER_MAX_SIZE */
417 
418     assert(100 <= status && status <= 999);
419 
420     switch (status) {
421 #define COMMON_CODE(code, st)                                                                                                      \
422     case st:                                                                                                                       \
423         *dst++ = 0x80 | code;                                                                                                      \
424         break
425         COMMON_CODE(8, 200);
426         COMMON_CODE(9, 204);
427         COMMON_CODE(10, 206);
428         COMMON_CODE(11, 304);
429         COMMON_CODE(12, 400);
430         COMMON_CODE(13, 404);
431         COMMON_CODE(14, 500);
432 #undef COMMON_CODE
433     default:
434         /* use literal header field without indexing - indexed name */
435         *dst++ = 8;
436         *dst++ = 3;
437         sprintf((char *)dst, "%d", status);
438         dst += 3;
439         break;
440     }
441 
442     return dst;
443 }
444 
encode_content_length(uint8_t * dst,size_t value)445 static uint8_t *encode_content_length(uint8_t *dst, size_t value)
446 {
447     char buf[32], *p = buf + sizeof(buf);
448     size_t l;
449 
450     do {
451         *--p = '0' + value % 10;
452     } while ((value /= 10) != 0);
453     l = buf + sizeof(buf) - p;
454     *dst++ = 0x0f;
455     *dst++ = 0x0d;
456     *dst++ = (uint8_t)l;
457     memcpy(dst, p, l);
458     dst += l;
459 
460     return dst;
461 }
462 
h2o_hpack_dispose_header_table(h2o_hpack_header_table_t * header_table)463 void h2o_hpack_dispose_header_table(h2o_hpack_header_table_t *header_table)
464 {
465     if (header_table->num_entries != 0) {
466         size_t index = header_table->entry_start_index;
467         do {
468             struct st_h2o_hpack_header_table_entry_t *entry = header_table->entries + index;
469             if (!h2o_iovec_is_token(entry->name))
470                 h2o_mem_release_shared(entry->name);
471             if (!value_is_part_of_static_table(entry->value))
472                 h2o_mem_release_shared(entry->value);
473             index = (index + 1) % header_table->entry_capacity;
474         } while (--header_table->num_entries != 0);
475     }
476     free(header_table->entries);
477 }
478 
h2o_hpack_parse_request(h2o_mem_pool_t * pool,h2o_hpack_decode_header_cb decode_cb,void * decode_ctx,h2o_iovec_t * method,const h2o_url_scheme_t ** scheme,h2o_iovec_t * authority,h2o_iovec_t * path,h2o_headers_t * headers,int * pseudo_header_exists_map,size_t * content_length,h2o_cache_digests_t ** digests,h2o_iovec_t * datagram_flow_id,const uint8_t * src,size_t len,const char ** err_desc)479 int h2o_hpack_parse_request(h2o_mem_pool_t *pool, h2o_hpack_decode_header_cb decode_cb, void *decode_ctx, h2o_iovec_t *method,
480                             const h2o_url_scheme_t **scheme, h2o_iovec_t *authority, h2o_iovec_t *path, h2o_headers_t *headers,
481                             int *pseudo_header_exists_map, size_t *content_length, h2o_cache_digests_t **digests,
482                             h2o_iovec_t *datagram_flow_id, const uint8_t *src, size_t len, const char **err_desc)
483 {
484     const uint8_t *src_end = src + len;
485 
486     *content_length = SIZE_MAX;
487 
488     while (src != src_end) {
489         h2o_iovec_t *name, value;
490         const char *decode_err = NULL;
491         int ret = decode_cb(pool, decode_ctx, &name, &value, &src, src_end, &decode_err);
492         if (ret != 0) {
493             if (ret == H2O_HTTP2_ERROR_INVALID_HEADER_CHAR) {
494                 /* this is a soft error, we continue parsing, but register only the first error */
495                 if (*err_desc == NULL) {
496                     *err_desc = decode_err;
497                 }
498             } else {
499                 *err_desc = decode_err;
500                 return ret;
501             }
502         }
503         if (name->base[0] == ':') {
504             if (pseudo_header_exists_map != NULL) {
505                 /* FIXME validate the chars in the value (e.g. reject SP in path) */
506                 if (name == &H2O_TOKEN_AUTHORITY->buf) {
507                     if (authority->base != NULL)
508                         return H2O_HTTP2_ERROR_PROTOCOL;
509                     *authority = value;
510                     *pseudo_header_exists_map |= H2O_HPACK_PARSE_HEADERS_AUTHORITY_EXISTS;
511                 } else if (name == &H2O_TOKEN_METHOD->buf) {
512                     if (method->base != NULL)
513                         return H2O_HTTP2_ERROR_PROTOCOL;
514                     *method = value;
515                     *pseudo_header_exists_map |= H2O_HPACK_PARSE_HEADERS_METHOD_EXISTS;
516                 } else if (name == &H2O_TOKEN_PATH->buf) {
517                     if (path->base != NULL)
518                         return H2O_HTTP2_ERROR_PROTOCOL;
519                     if (value.len == 0)
520                         return H2O_HTTP2_ERROR_PROTOCOL;
521                     *path = value;
522                     *pseudo_header_exists_map |= H2O_HPACK_PARSE_HEADERS_PATH_EXISTS;
523                 } else if (name == &H2O_TOKEN_SCHEME->buf) {
524                     if (*scheme != NULL)
525                         return H2O_HTTP2_ERROR_PROTOCOL;
526                     if (h2o_memis(value.base, value.len, H2O_STRLIT("https"))) {
527                         *scheme = &H2O_URL_SCHEME_HTTPS;
528                     } else if (h2o_memis(value.base, value.len, H2O_STRLIT("masque"))) {
529                         *scheme = &H2O_URL_SCHEME_MASQUE;
530                     } else {
531                         /* draft-16 8.1.2.3 suggests quote: ":scheme is not restricted to http and https schemed URIs" */
532                         *scheme = &H2O_URL_SCHEME_HTTP;
533                     }
534                     *pseudo_header_exists_map |= H2O_HPACK_PARSE_HEADERS_SCHEME_EXISTS;
535                 } else {
536                     return H2O_HTTP2_ERROR_PROTOCOL;
537                 }
538             } else {
539                 return H2O_HTTP2_ERROR_PROTOCOL;
540             }
541         } else {
542             pseudo_header_exists_map = NULL;
543             if (h2o_iovec_is_token(name)) {
544                 h2o_token_t *token = H2O_STRUCT_FROM_MEMBER(h2o_token_t, buf, name);
545                 if (token->flags.is_hpack_special) {
546                     if (token == H2O_TOKEN_CONTENT_LENGTH) {
547                         if ((*content_length = h2o_strtosize(value.base, value.len)) == SIZE_MAX)
548                             return H2O_HTTP2_ERROR_PROTOCOL;
549                         goto Next;
550                     } else if (token == H2O_TOKEN_HOST) {
551                         /* HTTP2 allows the use of host header (in place of :authority) */
552                         if (authority->base == NULL)
553                             *authority = value;
554                         goto Next;
555                     } else if (token == H2O_TOKEN_TE && h2o_lcstris(value.base, value.len, H2O_STRLIT("trailers"))) {
556                         /* do not reject */
557                     } else if (token == H2O_TOKEN_CACHE_DIGEST && digests != NULL) {
558                         /* TODO cache the decoded result in HPACK, as well as delay the decoding of the digest until being used */
559                         h2o_cache_digests_load_header(digests, value.base, value.len);
560                     } else if (token == H2O_TOKEN_DATAGRAM_FLOW_ID) {
561                         if (datagram_flow_id != NULL)
562                             *datagram_flow_id = value;
563                         goto Next;
564                     } else {
565                         /* rest of the header fields that are marked as special are rejected */
566                         return H2O_HTTP2_ERROR_PROTOCOL;
567                     }
568                 }
569                 h2o_add_header(pool, headers, token, NULL, value.base, value.len);
570             } else {
571                 h2o_add_header_by_str(pool, headers, name->base, name->len, 0, NULL, value.base, value.len);
572             }
573         }
574     Next:;
575     }
576 
577     if (*err_desc != NULL)
578         return H2O_HTTP2_ERROR_INVALID_HEADER_CHAR;
579     return 0;
580 }
581 
h2o_hpack_parse_response(h2o_mem_pool_t * pool,h2o_hpack_decode_header_cb decode_cb,void * decode_ctx,int * status,h2o_headers_t * headers,h2o_iovec_t * datagram_flow_id,const uint8_t * src,size_t len,const char ** err_desc)582 int h2o_hpack_parse_response(h2o_mem_pool_t *pool, h2o_hpack_decode_header_cb decode_cb, void *decode_ctx, int *status,
583                              h2o_headers_t *headers, h2o_iovec_t *datagram_flow_id, const uint8_t *src, size_t len,
584                              const char **err_desc)
585 {
586     *status = 0;
587 
588     const uint8_t *src_end = src + len;
589 
590     /* the response MUST contain a :status header as the first element */
591     if (src == src_end)
592         return H2O_HTTP2_ERROR_PROTOCOL;
593 
594     do {
595         h2o_iovec_t *name, value;
596         const char *decode_err = NULL;
597         int ret = decode_cb(pool, decode_ctx, &name, &value, &src, src_end, &decode_err);
598         if (ret != 0) {
599             if (ret == H2O_HTTP2_ERROR_INVALID_HEADER_CHAR) {
600                 /* this is a soft error, we continue parsing, but register only the first error */
601                 if (*err_desc == NULL) {
602                     *err_desc = decode_err;
603                 }
604             } else {
605                 *err_desc = decode_err;
606                 return ret;
607             }
608         }
609         if (name->base[0] == ':') {
610             if (name != &H2O_TOKEN_STATUS->buf)
611                 return H2O_HTTP2_ERROR_PROTOCOL;
612             if (*status != 0)
613                 return H2O_HTTP2_ERROR_PROTOCOL;
614             /* parse status */
615             if (value.len != 3)
616                 return H2O_HTTP2_ERROR_PROTOCOL;
617             char *c = value.base;
618 #define PARSE_DIGIT(mul, min_digit)                                                                                                \
619     do {                                                                                                                           \
620         if (*c < '0' + (min_digit) || '9' < *c)                                                                                    \
621             return H2O_HTTP2_ERROR_PROTOCOL;                                                                                       \
622         *status += (*c - '0') * mul;                                                                                               \
623         ++c;                                                                                                                       \
624     } while (0)
625             PARSE_DIGIT(100, 1);
626             PARSE_DIGIT(10, 0);
627             PARSE_DIGIT(1, 0);
628 #undef PARSE_DIGIT
629         } else {
630             if (*status == 0)
631                 return H2O_HTTP2_ERROR_PROTOCOL;
632             if (h2o_iovec_is_token(name)) {
633                 h2o_token_t *token = H2O_STRUCT_FROM_MEMBER(h2o_token_t, buf, name);
634                 /* reject headers as defined in draft-16 8.1.2.2 */
635                 if (token->flags.is_hpack_special) {
636                     if (token == H2O_TOKEN_CONTENT_LENGTH || token == H2O_TOKEN_CACHE_DIGEST) {
637                         /* pass them through when found in response headers (TODO reconsider?) */
638                     } else if (token == H2O_TOKEN_DATAGRAM_FLOW_ID) {
639                         if (datagram_flow_id != NULL)
640                             *datagram_flow_id = value;
641                         goto Next;
642                     } else {
643                         return H2O_HTTP2_ERROR_PROTOCOL;
644                     }
645                 }
646                 h2o_add_header(pool, headers, token, NULL, value.base, value.len);
647             } else {
648                 h2o_add_header_by_str(pool, headers, name->base, name->len, 0, NULL, value.base, value.len);
649             }
650         }
651     Next:;
652     } while (src != src_end);
653 
654     if (*err_desc) {
655         return H2O_HTTP2_ERROR_INVALID_HEADER_CHAR;
656     }
657     return 0;
658 }
659 
encode_int_is_onebyte(int64_t value,unsigned prefix_bits)660 static inline int encode_int_is_onebyte(int64_t value, unsigned prefix_bits)
661 {
662     return value < (1 << prefix_bits) - 1;
663 }
664 
h2o_hpack_encode_int(uint8_t * dst,int64_t value,unsigned prefix_bits)665 uint8_t *h2o_hpack_encode_int(uint8_t *dst, int64_t value, unsigned prefix_bits)
666 {
667     if (encode_int_is_onebyte(value, prefix_bits)) {
668         *dst++ |= value;
669     } else {
670         /* see also: MAX_ENCODE_INT_LENGTH */
671         assert(value >= 0);
672         value -= (1 << prefix_bits) - 1;
673         *dst++ |= (1 << prefix_bits) - 1;
674         for (; value >= 128; value >>= 7) {
675             *dst++ = 0x80 | value;
676         }
677         *dst++ = value;
678     }
679     return dst;
680 }
681 
h2o_hpack_encode_huffman(uint8_t * _dst,const uint8_t * src,size_t len)682 size_t h2o_hpack_encode_huffman(uint8_t *_dst, const uint8_t *src, size_t len)
683 {
684     uint8_t *dst = _dst, *dst_end = dst + len;
685     const uint8_t *src_end = src + len;
686     uint64_t bits = 0;
687     int bits_left = 40;
688 
689     while (src != src_end) {
690         const nghttp2_huff_sym *sym = huff_sym_table + *src++;
691         bits |= (uint64_t)sym->code << (bits_left - sym->nbits);
692         bits_left -= sym->nbits;
693         while (bits_left <= 32) {
694             *dst++ = bits >> 32;
695             bits <<= 8;
696             bits_left += 8;
697             if (dst == dst_end) {
698                 return SIZE_MAX;
699             }
700         }
701     }
702 
703     if (bits_left != 40) {
704         bits |= ((uint64_t)1 << bits_left) - 1;
705         *dst++ = bits >> 32;
706     }
707     if (dst == dst_end) {
708         return SIZE_MAX;
709     }
710 
711     return dst - _dst;
712 }
713 
encode_as_is(uint8_t * dst,const char * s,size_t len)714 static size_t encode_as_is(uint8_t *dst, const char *s, size_t len)
715 {
716     uint8_t *start = dst;
717     *dst = '\0';
718     dst = h2o_hpack_encode_int(dst, len, 7);
719     memcpy(dst, s, len);
720     dst += len;
721     return dst - start;
722 }
723 
h2o_hpack_encode_string(uint8_t * dst,const char * s,size_t len)724 size_t h2o_hpack_encode_string(uint8_t *dst, const char *s, size_t len)
725 {
726     if (H2O_LIKELY(len != 0)) {
727         /* try to encode using huffman */
728         size_t hufflen = h2o_hpack_encode_huffman(dst + 1, (const uint8_t *)s, len);
729         if (H2O_LIKELY(hufflen != SIZE_MAX)) {
730             size_t head_len;
731             if (H2O_LIKELY(encode_int_is_onebyte((uint32_t)hufflen, 7))) {
732                 dst[0] = (uint8_t)(0x80 | hufflen);
733                 head_len = 1;
734             } else {
735                 uint8_t head[8];
736                 head[0] = '\x80';
737                 head_len = h2o_hpack_encode_int(head, hufflen, 7) - head;
738                 memmove(dst + head_len, dst + 1, hufflen);
739                 memcpy(dst, head, head_len);
740             }
741             return head_len + hufflen;
742         }
743     }
744     return encode_as_is(dst, s, len);
745 }
746 
header_table_adjust_size(h2o_hpack_header_table_t * table,uint32_t new_capacity,uint8_t * dst)747 static uint8_t *header_table_adjust_size(h2o_hpack_header_table_t *table, uint32_t new_capacity, uint8_t *dst)
748 {
749     /* Do nothing if user-supplied value is greater than the current value. Because we never allow the peer to increase the table
750      * size here, there is no need to worry about using excess memory. */
751     if (new_capacity >= table->hpack_capacity)
752         return dst;
753 
754     /* update state */
755     table->hpack_capacity = new_capacity;
756     while (table->num_entries != 0 && table->hpack_size > table->hpack_capacity)
757         header_table_evict_one(table);
758 
759     /* encode Dynamic Table Size Update */
760     *dst = 0x20;
761     dst = h2o_hpack_encode_int(dst, table->hpack_capacity, 5);
762 
763     return dst;
764 }
765 
do_encode_header(h2o_hpack_header_table_t * header_table,uint8_t * dst,const h2o_iovec_t * name,const h2o_iovec_t * value,int dont_compress)766 static uint8_t *do_encode_header(h2o_hpack_header_table_t *header_table, uint8_t *dst, const h2o_iovec_t *name,
767                                  const h2o_iovec_t *value, int dont_compress)
768 {
769     int is_token = h2o_iovec_is_token(name);
770     int name_index = is_token ? ((const h2o_token_t *)name)->flags.http2_static_table_name_index : 0;
771 
772     /* try to send as indexed */
773     {
774         size_t header_table_index = header_table->entry_start_index, n;
775         for (n = header_table->num_entries; n != 0; --n) {
776             struct st_h2o_hpack_header_table_entry_t *entry = header_table->entries + header_table_index;
777             if (is_token) {
778                 if (name != entry->name)
779                     goto Next;
780             } else {
781                 if (!h2o_memis(name->base, name->len, entry->name->base, entry->name->len))
782                     goto Next;
783                 if (name_index == 0)
784                     name_index = (int)(header_table->num_entries - n + HEADER_TABLE_OFFSET);
785             }
786             /* name matched! */
787             if (!h2o_memis(value->base, value->len, entry->value->base, entry->value->len))
788                 goto Next;
789             /* name and value matched! */
790             *dst = 0x80;
791             dst = h2o_hpack_encode_int(dst, header_table->num_entries - n + HEADER_TABLE_OFFSET, 7);
792             return dst;
793         Next:
794             ++header_table_index;
795             if (header_table_index == header_table->entry_capacity)
796                 header_table_index = 0;
797         }
798     }
799 
800     if (!dont_compress && is_token)
801         dont_compress = ((const h2o_token_t *)name)->flags.dont_compress;
802     if (dont_compress)
803         dont_compress = value->len < 20;
804 
805     if (name_index != 0) {
806         /* literal header field with indexing (indexed name). */
807         if (dont_compress == 1) {
808             /* mark the field as 'never indexed' */
809             *dst = 0x10;
810             dst = h2o_hpack_encode_int(dst, name_index, 4);
811         } else {
812             *dst = 0x40;
813             dst = h2o_hpack_encode_int(dst, name_index, 6);
814         }
815     } else {
816         /* literal header field with indexing (new name) */
817         *dst++ = 0x40;
818         dst += h2o_hpack_encode_string(dst, name->base, name->len);
819     }
820     if (dont_compress == 1) {
821         /* bypass huffman encoding */
822         dst += encode_as_is(dst, value->base, value->len);
823     } else {
824         /* add to header table (maximum number of entries in output header table is limited to 32 so that the search (see above)
825            would
826            not take too long) */
827         dst += h2o_hpack_encode_string(dst, value->base, value->len);
828         struct st_h2o_hpack_header_table_entry_t *entry =
829             header_table_add(header_table, name->len + value->len + HEADER_TABLE_ENTRY_SIZE_OFFSET, 32);
830         if (entry != NULL) {
831             if (is_token) {
832                 entry->name = (h2o_iovec_t *)name;
833             } else {
834                 entry->name = alloc_buf(NULL, name->len);
835                 entry->name->base[name->len] = '\0';
836                 memcpy(entry->name->base, name->base, name->len);
837             }
838             entry->value = alloc_buf(NULL, value->len);
839             entry->value->base[value->len] = '\0';
840             memcpy(entry->value->base, value->base, value->len);
841         }
842     }
843 
844     return dst;
845 }
846 
encode_header(h2o_hpack_header_table_t * header_table,uint8_t * dst,const h2o_header_t * header)847 static uint8_t *encode_header(h2o_hpack_header_table_t *header_table, uint8_t *dst, const h2o_header_t *header)
848 {
849     return do_encode_header(header_table, dst, header->name, &header->value, header->flags.dont_compress);
850 }
851 
encode_header_token(h2o_hpack_header_table_t * header_table,uint8_t * dst,const h2o_token_t * token,const h2o_iovec_t * value)852 static uint8_t *encode_header_token(h2o_hpack_header_table_t *header_table, uint8_t *dst, const h2o_token_t *token,
853                                     const h2o_iovec_t *value)
854 {
855     return do_encode_header(header_table, dst, &token->buf, value, token->flags.dont_compress);
856 }
857 
encode_method(h2o_hpack_header_table_t * header_table,uint8_t * dst,h2o_iovec_t value)858 static uint8_t *encode_method(h2o_hpack_header_table_t *header_table, uint8_t *dst, h2o_iovec_t value)
859 {
860     if (h2o_memis(value.base, value.len, H2O_STRLIT("GET"))) {
861         *dst++ = 0x82;
862         return dst;
863     }
864     if (h2o_memis(value.base, value.len, H2O_STRLIT("POST"))) {
865         *dst++ = 0x83;
866         return dst;
867     }
868     return encode_header_token(header_table, dst, H2O_TOKEN_METHOD, &value);
869 }
870 
encode_scheme(h2o_hpack_header_table_t * header_table,uint8_t * dst,const h2o_url_scheme_t * scheme)871 static uint8_t *encode_scheme(h2o_hpack_header_table_t *header_table, uint8_t *dst, const h2o_url_scheme_t *scheme)
872 {
873     if (scheme == &H2O_URL_SCHEME_HTTPS) {
874         *dst++ = 0x87;
875         return dst;
876     }
877     if (scheme == &H2O_URL_SCHEME_HTTP) {
878         *dst++ = 0x86;
879         return dst;
880     }
881     return encode_header_token(header_table, dst, H2O_TOKEN_SCHEME, &scheme->name);
882 }
883 
encode_path(h2o_hpack_header_table_t * header_table,uint8_t * dst,h2o_iovec_t value)884 static uint8_t *encode_path(h2o_hpack_header_table_t *header_table, uint8_t *dst, h2o_iovec_t value)
885 {
886     if (h2o_memis(value.base, value.len, H2O_STRLIT("/"))) {
887         *dst++ = 0x84;
888         return dst;
889     }
890     if (h2o_memis(value.base, value.len, H2O_STRLIT("/index.html"))) {
891         *dst++ = 0x85;
892         return dst;
893     }
894     return encode_header_token(header_table, dst, H2O_TOKEN_PATH, &value);
895 }
896 
encode_literal_header_without_indexing(uint8_t * dst,const h2o_iovec_t * name,const h2o_iovec_t * value)897 static uint8_t *encode_literal_header_without_indexing(uint8_t *dst, const h2o_iovec_t *name, const h2o_iovec_t *value)
898 {
899     /* literal header field without indexing / never indexed */
900     *dst++ = 0;
901     dst += h2o_hpack_encode_string(dst, name->base, name->len);
902     dst += h2o_hpack_encode_string(dst, value->base, value->len);
903     return dst;
904 }
905 
calc_capacity(size_t name_len,size_t value_len)906 static size_t calc_capacity(size_t name_len, size_t value_len)
907 {
908     return name_len + value_len + 1 + H2O_HPACK_ENCODE_INT_MAX_LENGTH * 2;
909 }
910 
calc_headers_capacity(const h2o_header_t * headers,size_t num_headers)911 static size_t calc_headers_capacity(const h2o_header_t *headers, size_t num_headers)
912 {
913     const h2o_header_t *header;
914     size_t capacity = 0;
915     for (header = headers; num_headers != 0; ++header, --num_headers)
916         capacity += calc_capacity(header->name->len, header->value.len);
917     return capacity;
918 }
919 
fixup_frame_headers(h2o_buffer_t ** buf,size_t start_at,uint8_t type,uint32_t stream_id,size_t max_frame_size,int flags)920 static void fixup_frame_headers(h2o_buffer_t **buf, size_t start_at, uint8_t type, uint32_t stream_id, size_t max_frame_size,
921                                 int flags)
922 {
923     /* try to fit all data into single frame, using the preallocated space for the frame header */
924     size_t payload_size = (*buf)->size - start_at - H2O_HTTP2_FRAME_HEADER_SIZE;
925     if (payload_size <= max_frame_size) {
926         h2o_http2_encode_frame_header((uint8_t *)((*buf)->bytes + start_at), payload_size, type,
927                                       H2O_HTTP2_FRAME_FLAG_END_HEADERS | flags, stream_id);
928         return;
929     }
930 
931     /* need to setup continuation frames */
932     size_t off;
933     h2o_http2_encode_frame_header((uint8_t *)((*buf)->bytes + start_at), max_frame_size, type, flags, stream_id);
934     off = start_at + H2O_HTTP2_FRAME_HEADER_SIZE + max_frame_size;
935     while (1) {
936         size_t left = (*buf)->size - off;
937         h2o_buffer_reserve(buf, H2O_HTTP2_FRAME_HEADER_SIZE);
938         memmove((*buf)->bytes + off + H2O_HTTP2_FRAME_HEADER_SIZE, (*buf)->bytes + off, left);
939         (*buf)->size += H2O_HTTP2_FRAME_HEADER_SIZE;
940         if (left <= max_frame_size) {
941             h2o_http2_encode_frame_header((uint8_t *)((*buf)->bytes + off), left, H2O_HTTP2_FRAME_TYPE_CONTINUATION,
942                                           H2O_HTTP2_FRAME_FLAG_END_HEADERS, stream_id);
943             break;
944         } else {
945             h2o_http2_encode_frame_header((uint8_t *)((*buf)->bytes + off), max_frame_size, H2O_HTTP2_FRAME_TYPE_CONTINUATION, 0,
946                                           stream_id);
947             off += H2O_HTTP2_FRAME_HEADER_SIZE + max_frame_size;
948         }
949     }
950 }
951 
h2o_hpack_flatten_request(h2o_buffer_t ** buf,h2o_hpack_header_table_t * header_table,uint32_t hpack_capacity,uint32_t stream_id,size_t max_frame_size,h2o_iovec_t method,h2o_url_t * url,const h2o_header_t * headers,size_t num_headers,int is_end_stream)952 void h2o_hpack_flatten_request(h2o_buffer_t **buf, h2o_hpack_header_table_t *header_table, uint32_t hpack_capacity,
953                                uint32_t stream_id, size_t max_frame_size, h2o_iovec_t method, h2o_url_t *url,
954                                const h2o_header_t *headers, size_t num_headers, int is_end_stream)
955 {
956     int is_connect = h2o_memis(method.base, method.len, H2O_STRLIT("CONNECT"));
957 
958     size_t capacity = calc_headers_capacity(headers, num_headers);
959     capacity += H2O_HTTP2_FRAME_HEADER_SIZE;
960     capacity += DYNAMIC_TABLE_SIZE_UPDATE_MAX_SIZE;
961     capacity += calc_capacity(H2O_TOKEN_METHOD->buf.len, method.len);
962     if (!is_connect)
963         capacity += calc_capacity(H2O_TOKEN_SCHEME->buf.len, url->scheme->name.len);
964     capacity += calc_capacity(H2O_TOKEN_AUTHORITY->buf.len, url->authority.len);
965     if (!is_connect)
966         capacity += calc_capacity(H2O_TOKEN_PATH->buf.len, url->path.len);
967 
968     size_t start_at = (*buf)->size;
969     uint8_t *dst = (void *)(h2o_buffer_reserve(buf, capacity).base + H2O_HTTP2_FRAME_HEADER_SIZE);
970 
971     /* encode */
972     dst = header_table_adjust_size(header_table, hpack_capacity, dst);
973     dst = encode_method(header_table, dst, method);
974     if (!is_connect)
975         dst = encode_scheme(header_table, dst, url->scheme);
976     dst = encode_header_token(header_table, dst, H2O_TOKEN_AUTHORITY, &url->authority);
977     if (!is_connect)
978         dst = encode_path(header_table, dst, url->path);
979     for (size_t i = 0; i != num_headers; ++i) {
980         const h2o_header_t *header = headers + i;
981         if (header->name == &H2O_TOKEN_ACCEPT_ENCODING->buf &&
982             h2o_memis(header->value.base, header->value.len, H2O_STRLIT("gzip, deflate"))) {
983             *dst++ = 0x90;
984         } else {
985             dst = encode_header(header_table, dst, header);
986         }
987     }
988     (*buf)->size = (char *)dst - (*buf)->bytes;
989 
990     /* setup the frame headers */
991     fixup_frame_headers(buf, start_at, H2O_HTTP2_FRAME_TYPE_HEADERS, stream_id, max_frame_size,
992                         is_end_stream ? H2O_HTTP2_FRAME_FLAG_END_STREAM : 0);
993 }
994 
h2o_hpack_flatten_push_promise(h2o_buffer_t ** buf,h2o_hpack_header_table_t * header_table,uint32_t hpack_capacity,uint32_t stream_id,size_t max_frame_size,const h2o_url_scheme_t * scheme,h2o_iovec_t authority,h2o_iovec_t method,h2o_iovec_t path,const h2o_header_t * headers,size_t num_headers,uint32_t parent_stream_id)995 void h2o_hpack_flatten_push_promise(h2o_buffer_t **buf, h2o_hpack_header_table_t *header_table, uint32_t hpack_capacity,
996                                     uint32_t stream_id, size_t max_frame_size, const h2o_url_scheme_t *scheme,
997                                     h2o_iovec_t authority, h2o_iovec_t method, h2o_iovec_t path, const h2o_header_t *headers,
998                                     size_t num_headers, uint32_t parent_stream_id)
999 {
1000     size_t capacity = calc_headers_capacity(headers, num_headers);
1001     capacity += H2O_HTTP2_FRAME_HEADER_SIZE /* first frame header */
1002                 + 4;                        /* promised stream id */
1003     capacity += DYNAMIC_TABLE_SIZE_UPDATE_MAX_SIZE;
1004     capacity += calc_capacity(H2O_TOKEN_METHOD->buf.len, method.len);
1005     capacity += calc_capacity(H2O_TOKEN_SCHEME->buf.len, scheme->name.len);
1006     capacity += calc_capacity(H2O_TOKEN_AUTHORITY->buf.len, authority.len);
1007     capacity += calc_capacity(H2O_TOKEN_PATH->buf.len, path.len);
1008 
1009     size_t start_at = (*buf)->size;
1010     uint8_t *dst = (void *)(h2o_buffer_reserve(buf, capacity).base + H2O_HTTP2_FRAME_HEADER_SIZE);
1011 
1012     /* encode */
1013     dst = h2o_http2_encode32u(dst, stream_id);
1014     dst = header_table_adjust_size(header_table, hpack_capacity, dst);
1015     dst = encode_method(header_table, dst, method);
1016     dst = encode_scheme(header_table, dst, scheme);
1017     dst = encode_header_token(header_table, dst, H2O_TOKEN_AUTHORITY, &authority);
1018     dst = encode_path(header_table, dst, path);
1019     for (size_t i = 0; i != num_headers; ++i) {
1020         const h2o_header_t *header = headers + i;
1021         if (header->name == &H2O_TOKEN_ACCEPT_ENCODING->buf &&
1022             h2o_memis(header->value.base, header->value.len, H2O_STRLIT("gzip, deflate"))) {
1023             *dst++ = 0x90;
1024         } else {
1025             dst = encode_header(header_table, dst, header);
1026         }
1027     }
1028     (*buf)->size = (char *)dst - (*buf)->bytes;
1029 
1030     /* setup the frame headers */
1031     fixup_frame_headers(buf, start_at, H2O_HTTP2_FRAME_TYPE_PUSH_PROMISE, parent_stream_id, max_frame_size, 0);
1032 }
1033 
h2o_hpack_flatten_response(h2o_buffer_t ** buf,h2o_hpack_header_table_t * header_table,uint32_t hpack_capacity,uint32_t stream_id,size_t max_frame_size,int status,const h2o_header_t * headers,size_t num_headers,const h2o_iovec_t * server_name,size_t content_length)1034 void h2o_hpack_flatten_response(h2o_buffer_t **buf, h2o_hpack_header_table_t *header_table, uint32_t hpack_capacity,
1035                                 uint32_t stream_id, size_t max_frame_size, int status, const h2o_header_t *headers,
1036                                 size_t num_headers, const h2o_iovec_t *server_name, size_t content_length)
1037 {
1038     size_t capacity = calc_headers_capacity(headers, num_headers);
1039     capacity += H2O_HTTP2_FRAME_HEADER_SIZE; /* for the first header */
1040     capacity += DYNAMIC_TABLE_SIZE_UPDATE_MAX_SIZE;
1041     capacity += STATUS_HEADER_MAX_SIZE; /* for :status: */
1042 #ifndef H2O_UNITTEST
1043     if (server_name != NULL && server_name->len) {
1044         capacity += 5 + server_name->len; /* for Server: */
1045     }
1046 #endif
1047     if (content_length != SIZE_MAX)
1048         capacity += CONTENT_LENGTH_HEADER_MAX_SIZE; /* for content-length: UINT64_MAX (with huffman compression applied) */
1049 
1050     size_t start_at = (*buf)->size;
1051     uint8_t *dst = (void *)(h2o_buffer_reserve(buf, capacity).base + H2O_HTTP2_FRAME_HEADER_SIZE); /* skip frame header */
1052 
1053     /* encode */
1054     dst = header_table_adjust_size(header_table, hpack_capacity, dst);
1055     dst = encode_status(dst, status);
1056 #ifndef H2O_UNITTEST
1057     /* TODO keep some kind of reference to the indexed Server header, and reuse it */
1058     if (server_name != NULL && server_name->len) {
1059         dst = encode_header_token(header_table, dst, H2O_TOKEN_SERVER, server_name);
1060     }
1061 #endif
1062     for (size_t i = 0; i != num_headers; ++i)
1063         dst = encode_header(header_table, dst, headers + i);
1064     if (content_length != SIZE_MAX)
1065         dst = encode_content_length(dst, content_length);
1066     (*buf)->size = (char *)dst - (*buf)->bytes;
1067 
1068     /* setup the frame headers */
1069     fixup_frame_headers(buf, start_at, H2O_HTTP2_FRAME_TYPE_HEADERS, stream_id, max_frame_size, 0);
1070 }
1071 
h2o_hpack_flatten_trailers(h2o_buffer_t ** buf,h2o_hpack_header_table_t * header_table,uint32_t hpack_capacity,uint32_t stream_id,size_t max_frame_size,const h2o_header_t * headers,size_t num_headers)1072 void h2o_hpack_flatten_trailers(h2o_buffer_t **buf, h2o_hpack_header_table_t *header_table, uint32_t hpack_capacity,
1073                                 uint32_t stream_id, size_t max_frame_size, const h2o_header_t *headers, size_t num_headers)
1074 {
1075     size_t capacity = calc_headers_capacity(headers, num_headers);
1076     capacity += H2O_HTTP2_FRAME_HEADER_SIZE;
1077     capacity += DYNAMIC_TABLE_SIZE_UPDATE_MAX_SIZE;
1078 
1079     size_t start_at = (*buf)->size;
1080     uint8_t *dst = (void *)(h2o_buffer_reserve(buf, capacity).base + H2O_HTTP2_FRAME_HEADER_SIZE); /* skip frame header */
1081 
1082     dst = header_table_adjust_size(header_table, hpack_capacity, dst);
1083     for (size_t i = 0; i != num_headers; ++i)
1084         dst = encode_header(header_table, dst, headers + i);
1085     (*buf)->size = (char *)dst - (*buf)->bytes;
1086 
1087     /* setup the frame headers */
1088     fixup_frame_headers(buf, start_at, H2O_HTTP2_FRAME_TYPE_HEADERS, stream_id, max_frame_size, H2O_HTTP2_FRAME_FLAG_END_STREAM);
1089 }
1090