xref: /trafficserver/proxy/http2/HPACK.cc (revision 323d5b59)
1 /** @file
2 
3   [RFC 7541] HPACK: Header Compression for HTTP/2
4 
5   @section license License
6 
7   Licensed to the Apache Software Foundation (ASF) under one
8   or more contributor license agreements.  See the NOTICE file
9   distributed with this work for additional information
10   regarding copyright ownership.  The ASF licenses this file
11   to you under the Apache License, Version 2.0 (the
12   "License"); you may not use this file except in compliance
13   with the License.  You may obtain a copy of the License at
14 
15       http://www.apache.org/licenses/LICENSE-2.0
16 
17   Unless required by applicable law or agreed to in writing, software
18   distributed under the License is distributed on an "AS IS" BASIS,
19   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
20   See the License for the specific language governing permissions and
21   limitations under the License.
22  */
23 
24 #include "HPACK.h"
25 #include "HuffmanCodec.h"
26 
27 // [RFC 7541] 4.1. Calculating Table Size
28 // The size of an entry is the sum of its name's length in octets (as defined in Section 5.2),
29 // its value's length in octets, and 32.
30 const static unsigned ADDITIONAL_OCTETS = 32;
31 
32 typedef enum {
33   TS_HPACK_STATIC_TABLE_0 = 0,
34   TS_HPACK_STATIC_TABLE_AUTHORITY,
35   TS_HPACK_STATIC_TABLE_METHOD_GET,
36   TS_HPACK_STATIC_TABLE_METHOD_POST,
37   TS_HPACK_STATIC_TABLE_PATH_ROOT,
38   TS_HPACK_STATIC_TABLE_PATH_INDEX,
39   TS_HPACK_STATIC_TABLE_SCHEME_HTTP,
40   TS_HPACK_STATIC_TABLE_SCHEME_HTTPS,
41   TS_HPACK_STATIC_TABLE_STATUS_200,
42   TS_HPACK_STATIC_TABLE_STATUS_204,
43   TS_HPACK_STATIC_TABLE_STATUS_206,
44   TS_HPACK_STATIC_TABLE_STATUS_304,
45   TS_HPACK_STATIC_TABLE_STATUS_400,
46   TS_HPACK_STATIC_TABLE_STATUS_404,
47   TS_HPACK_STATIC_TABLE_STATUS_500,
48   TS_HPACK_STATIC_TABLE_ACCEPT_CHARSET,
49   TS_HPACK_STATIC_TABLE_ACCEPT_ENCODING,
50   TS_HPACK_STATIC_TABLE_ACCEPT_LANGUAGE,
51   TS_HPACK_STATIC_TABLE_ACCEPT_RANGES,
52   TS_HPACK_STATIC_TABLE_ACCEPT,
53   TS_HPACK_STATIC_TABLE_ACCESS_CONTROL_ALLOW_ORIGIN,
54   TS_HPACK_STATIC_TABLE_AGE,
55   TS_HPACK_STATIC_TABLE_ALLOW,
56   TS_HPACK_STATIC_TABLE_AUTHORIZATION,
57   TS_HPACK_STATIC_TABLE_CACHE_CONTROL,
58   TS_HPACK_STATIC_TABLE_CONTENT_DISPOSITION,
59   TS_HPACK_STATIC_TABLE_CONTENT_ENCODING,
60   TS_HPACK_STATIC_TABLE_CONTENT_LANGUAGE,
61   TS_HPACK_STATIC_TABLE_CONTENT_LENGTH,
62   TS_HPACK_STATIC_TABLE_CONTENT_LOCATION,
63   TS_HPACK_STATIC_TABLE_CONTENT_RANGE,
64   TS_HPACK_STATIC_TABLE_CONTENT_TYPE,
65   TS_HPACK_STATIC_TABLE_COOKIE,
66   TS_HPACK_STATIC_TABLE_DATE,
67   TS_HPACK_STATIC_TABLE_ETAG,
68   TS_HPACK_STATIC_TABLE_EXPECT,
69   TS_HPACK_STATIC_TABLE_EXPIRES,
70   TS_HPACK_STATIC_TABLE_FROM,
71   TS_HPACK_STATIC_TABLE_HOST,
72   TS_HPACK_STATIC_TABLE_IF_MATCH,
73   TS_HPACK_STATIC_TABLE_IF_MODIFIED_SINCE,
74   TS_HPACK_STATIC_TABLE_IF_NONE_MATCH,
75   TS_HPACK_STATIC_TABLE_IF_RANGE,
76   TS_HPACK_STATIC_TABLE_IF_UNMODIFIED_SINCE,
77   TS_HPACK_STATIC_TABLE_LAST_MODIFIED,
78   TS_HPACK_STATIC_TABLE_LINK,
79   TS_HPACK_STATIC_TABLE_LOCATION,
80   TS_HPACK_STATIC_TABLE_MAX_FORWARDS,
81   TS_HPACK_STATIC_TABLE_PROXY_AUTHENTICATE,
82   TS_HPACK_STATIC_TABLE_PROXY_AUTHORIZATION,
83   TS_HPACK_STATIC_TABLE_RANGE,
84   TS_HPACK_STATIC_TABLE_REFERER,
85   TS_HPACK_STATIC_TABLE_REFRESH,
86   TS_HPACK_STATIC_TABLE_RETRY_AFTER,
87   TS_HPACK_STATIC_TABLE_SERVER,
88   TS_HPACK_STATIC_TABLE_SET_COOKIE,
89   TS_HPACK_STATIC_TABLE_STRICT_TRANSPORT_SECURITY,
90   TS_HPACK_STATIC_TABLE_TRANSFER_ENCODING,
91   TS_HPACK_STATIC_TABLE_USER_AGENT,
92   TS_HPACK_STATIC_TABLE_VARY,
93   TS_HPACK_STATIC_TABLE_VIA,
94   TS_HPACK_STATIC_TABLE_WWW_AUTHENTICATE,
95   TS_HPACK_STATIC_TABLE_ENTRY_NUM
96 } TS_HPACK_STATIC_TABLE_ENTRY;
97 
98 struct StaticTable {
StaticTableStaticTable99   StaticTable(const char *n, const char *v) : name(n), value(v), name_size(strlen(name)), value_size(strlen(value)) {}
100   const char *name;
101   const char *value;
102   const int name_size;
103   const int value_size;
104 };
105 
106 static const StaticTable STATIC_TABLE[] = {{"", ""},
107                                            {":authority", ""},
108                                            {":method", "GET"},
109                                            {":method", "POST"},
110                                            {":path", "/"},
111                                            {":path", "/index.html"},
112                                            {":scheme", "http"},
113                                            {":scheme", "https"},
114                                            {":status", "200"},
115                                            {":status", "204"},
116                                            {":status", "206"},
117                                            {":status", "304"},
118                                            {":status", "400"},
119                                            {":status", "404"},
120                                            {":status", "500"},
121                                            {"accept-charset", ""},
122                                            {"accept-encoding", "gzip, deflate"},
123                                            {"accept-language", ""},
124                                            {"accept-ranges", ""},
125                                            {"accept", ""},
126                                            {"access-control-allow-origin", ""},
127                                            {"age", ""},
128                                            {"allow", ""},
129                                            {"authorization", ""},
130                                            {"cache-control", ""},
131                                            {"content-disposition", ""},
132                                            {"content-encoding", ""},
133                                            {"content-language", ""},
134                                            {"content-length", ""},
135                                            {"content-location", ""},
136                                            {"content-range", ""},
137                                            {"content-type", ""},
138                                            {"cookie", ""},
139                                            {"date", ""},
140                                            {"etag", ""},
141                                            {"expect", ""},
142                                            {"expires", ""},
143                                            {"from", ""},
144                                            {"host", ""},
145                                            {"if-match", ""},
146                                            {"if-modified-since", ""},
147                                            {"if-none-match", ""},
148                                            {"if-range", ""},
149                                            {"if-unmodified-since", ""},
150                                            {"last-modified", ""},
151                                            {"link", ""},
152                                            {"location", ""},
153                                            {"max-forwards", ""},
154                                            {"proxy-authenticate", ""},
155                                            {"proxy-authorization", ""},
156                                            {"range", ""},
157                                            {"referer", ""},
158                                            {"refresh", ""},
159                                            {"retry-after", ""},
160                                            {"server", ""},
161                                            {"set-cookie", ""},
162                                            {"strict-transport-security", ""},
163                                            {"transfer-encoding", ""},
164                                            {"user-agent", ""},
165                                            {"vary", ""},
166                                            {"via", ""},
167                                            {"www-authenticate", ""}};
168 
169 /**
170   Threshold for total HdrHeap size which used by HPAK Dynamic Table.
171   The HdrHeap is filled by MIMEHdrImpl and MIMEFieldBlockImpl like below.
172   This threshold allow to allocate 3 HdrHeap at maximum.
173 
174                      +------------------+-----------------------------+
175    HdrHeap 1 (2048): | MIMEHdrImpl(592) | MIMEFieldBlockImpl(528) x 2 |
176                      +------------------+-----------------------------+--...--+
177    HdrHeap 2 (4096): | MIMEFieldBlockImpl(528) x 7                            |
178                      +------------------------------------------------+--...--+--...--+
179    HdrHeap 3 (8192): | MIMEFieldBlockImpl(528) x 15                                   |
180                      +------------------------------------------------+--...--+--...--+
181 */
182 static constexpr uint32_t HPACK_HDR_HEAP_THRESHOLD = sizeof(MIMEHdrImpl) + sizeof(MIMEFieldBlockImpl) * (2 + 7 + 15);
183 
184 /******************
185  * Local functions
186  ******************/
187 static inline bool
hpack_field_is_literal(HpackField ftype)188 hpack_field_is_literal(HpackField ftype)
189 {
190   return ftype == HpackField::INDEXED_LITERAL || ftype == HpackField::NOINDEX_LITERAL || ftype == HpackField::NEVERINDEX_LITERAL;
191 }
192 
193 //
194 // The first byte of an HPACK field unambiguously tells us what
195 // kind of field it is. Field types are specified in the high 4 bits
196 // and all bits are defined, so there's no way to get an invalid field type.
197 //
198 HpackField
hpack_parse_field_type(uint8_t ftype)199 hpack_parse_field_type(uint8_t ftype)
200 {
201   if (ftype & 0x80) {
202     return HpackField::INDEX;
203   }
204 
205   if (ftype & 0x40) {
206     return HpackField::INDEXED_LITERAL;
207   }
208 
209   if (ftype & 0x20) {
210     return HpackField::TABLESIZE_UPDATE;
211   }
212 
213   if (ftype & 0x10) {
214     return HpackField::NEVERINDEX_LITERAL;
215   }
216 
217   ink_assert((ftype & 0xf0) == 0x0);
218   return HpackField::NOINDEX_LITERAL;
219 }
220 
221 /************************
222  * HpackIndexingTable
223  ************************/
224 HpackLookupResult
lookup(const MIMEFieldWrapper & field) const225 HpackIndexingTable::lookup(const MIMEFieldWrapper &field) const
226 {
227   int target_name_len = 0, target_value_len = 0;
228   const char *target_name  = field.name_get(&target_name_len);
229   const char *target_value = field.value_get(&target_value_len);
230   return lookup(target_name, target_name_len, target_value, target_value_len);
231 }
232 
233 HpackLookupResult
lookup(const char * name,int name_len,const char * value,int value_len) const234 HpackIndexingTable::lookup(const char *name, int name_len, const char *value, int value_len) const
235 {
236   HpackLookupResult result;
237   const unsigned int entry_num = TS_HPACK_STATIC_TABLE_ENTRY_NUM + _dynamic_table->length();
238 
239   for (unsigned int index = 1; index < entry_num; ++index) {
240     const char *table_name, *table_value;
241     int table_name_len = 0, table_value_len = 0;
242 
243     if (index < TS_HPACK_STATIC_TABLE_ENTRY_NUM) {
244       // static table
245       table_name      = STATIC_TABLE[index].name;
246       table_value     = STATIC_TABLE[index].value;
247       table_name_len  = STATIC_TABLE[index].name_size;
248       table_value_len = STATIC_TABLE[index].value_size;
249     } else {
250       // dynamic table
251       const MIMEField *m_field = _dynamic_table->get_header_field(index - TS_HPACK_STATIC_TABLE_ENTRY_NUM);
252 
253       table_name  = m_field->name_get(&table_name_len);
254       table_value = m_field->value_get(&table_value_len);
255     }
256 
257     // Check whether name (and value) are matched
258     if (ptr_len_casecmp(name, name_len, table_name, table_name_len) == 0) {
259       if ((value_len == table_value_len) && (memcmp(value, table_value, value_len) == 0)) {
260         result.index      = index;
261         result.match_type = HpackMatch::EXACT;
262         break;
263       } else if (!result.index) {
264         result.index      = index;
265         result.match_type = HpackMatch::NAME;
266       }
267     }
268   }
269   if (result.match_type != HpackMatch::NONE) {
270     if (result.index < TS_HPACK_STATIC_TABLE_ENTRY_NUM) {
271       result.index_type = HpackIndex::STATIC;
272     } else {
273       result.index_type = HpackIndex::DYNAMIC;
274     }
275   }
276 
277   return result;
278 }
279 
280 int
get_header_field(uint32_t index,MIMEFieldWrapper & field) const281 HpackIndexingTable::get_header_field(uint32_t index, MIMEFieldWrapper &field) const
282 {
283   // Index Address Space starts at 1, so index == 0 is invalid.
284   if (!index) {
285     return HPACK_ERROR_COMPRESSION_ERROR;
286   }
287 
288   if (index < TS_HPACK_STATIC_TABLE_ENTRY_NUM) {
289     // static table
290     field.name_set(STATIC_TABLE[index].name, STATIC_TABLE[index].name_size);
291     field.value_set(STATIC_TABLE[index].value, STATIC_TABLE[index].value_size);
292   } else if (index < TS_HPACK_STATIC_TABLE_ENTRY_NUM + _dynamic_table->length()) {
293     // dynamic table
294     const MIMEField *m_field = _dynamic_table->get_header_field(index - TS_HPACK_STATIC_TABLE_ENTRY_NUM);
295 
296     int name_len, value_len;
297     const char *name  = m_field->name_get(&name_len);
298     const char *value = m_field->value_get(&value_len);
299 
300     field.name_set(name, name_len);
301     field.value_set(value, value_len);
302   } else {
303     // [RFC 7541] 2.3.3. Index Address Space
304     // Indices strictly greater than the sum of the lengths of both tables
305     // MUST be treated as a decoding error.
306     return HPACK_ERROR_COMPRESSION_ERROR;
307   }
308 
309   return 0;
310 }
311 
312 void
add_header_field(const MIMEField * field)313 HpackIndexingTable::add_header_field(const MIMEField *field)
314 {
315   _dynamic_table->add_header_field(field);
316 }
317 
318 uint32_t
maximum_size() const319 HpackIndexingTable::maximum_size() const
320 {
321   return _dynamic_table->maximum_size();
322 }
323 
324 uint32_t
size() const325 HpackIndexingTable::size() const
326 {
327   return _dynamic_table->size();
328 }
329 
330 bool
update_maximum_size(uint32_t new_size)331 HpackIndexingTable::update_maximum_size(uint32_t new_size)
332 {
333   return _dynamic_table->update_maximum_size(new_size);
334 }
335 
336 //
337 // HpackDynamicTable
338 //
~HpackDynamicTable()339 HpackDynamicTable::~HpackDynamicTable()
340 {
341   this->_headers.clear();
342 
343   this->_mhdr->fields_clear();
344   this->_mhdr->destroy();
345   delete this->_mhdr;
346 
347   if (this->_mhdr_old != nullptr) {
348     this->_mhdr_old->fields_clear();
349     this->_mhdr_old->destroy();
350     delete this->_mhdr_old;
351   }
352 }
353 
354 const MIMEField *
get_header_field(uint32_t index) const355 HpackDynamicTable::get_header_field(uint32_t index) const
356 {
357   return this->_headers.at(index);
358 }
359 
360 void
add_header_field(const MIMEField * field)361 HpackDynamicTable::add_header_field(const MIMEField *field)
362 {
363   int name_len, value_len;
364   const char *name     = field->name_get(&name_len);
365   const char *value    = field->value_get(&value_len);
366   uint32_t header_size = ADDITIONAL_OCTETS + name_len + value_len;
367 
368   if (header_size > _maximum_size) {
369     // [RFC 7541] 4.4. Entry Eviction When Adding New Entries
370     // It is not an error to attempt to add an entry that is larger than
371     // the maximum size; an attempt to add an entry larger than the entire
372     // table causes the table to be emptied of all existing entries.
373     this->_headers.clear();
374     this->_mhdr->fields_clear();
375     this->_current_size = 0;
376   } else {
377     this->_current_size += header_size;
378     this->_evict_overflowed_entries();
379 
380     MIMEField *new_field = this->_mhdr->field_create(name, name_len);
381     new_field->value_set(this->_mhdr->m_heap, this->_mhdr->m_mime, value, value_len);
382     this->_mhdr->field_attach(new_field);
383     this->_headers.push_front(new_field);
384   }
385 }
386 
387 uint32_t
maximum_size() const388 HpackDynamicTable::maximum_size() const
389 {
390   return _maximum_size;
391 }
392 
393 uint32_t
size() const394 HpackDynamicTable::size() const
395 {
396   return _current_size;
397 }
398 
399 //
400 // [RFC 7541] 4.3. Entry Eviction when Header Table Size Changes
401 //
402 // Whenever the maximum size for the header table is reduced, entries
403 // are evicted from the end of the header table until the size of the
404 // header table is less than or equal to the maximum size.
405 //
406 bool
update_maximum_size(uint32_t new_size)407 HpackDynamicTable::update_maximum_size(uint32_t new_size)
408 {
409   this->_maximum_size = new_size;
410   return this->_evict_overflowed_entries();
411 }
412 
413 uint32_t
length() const414 HpackDynamicTable::length() const
415 {
416   return this->_headers.size();
417 }
418 
419 bool
_evict_overflowed_entries()420 HpackDynamicTable::_evict_overflowed_entries()
421 {
422   if (this->_current_size <= this->_maximum_size) {
423     // Do nothing
424     return true;
425   }
426 
427   for (auto h = this->_headers.rbegin(); h != this->_headers.rend(); ++h) {
428     int name_len, value_len;
429     (*h)->name_get(&name_len);
430     (*h)->value_get(&value_len);
431 
432     this->_current_size -= ADDITIONAL_OCTETS + name_len + value_len;
433     this->_mhdr->field_delete(*h, false);
434     this->_headers.pop_back();
435 
436     if (this->_current_size <= this->_maximum_size) {
437       break;
438     }
439   }
440 
441   if (this->_headers.size() == 0) {
442     return false;
443   }
444 
445   this->_mime_hdr_gc();
446 
447   return true;
448 }
449 
450 /**
451    When HdrHeap size of current MIMEHdr exceeds the threshold, allocate new MIMEHdr and HdrHeap.
452    The old MIMEHdr and HdrHeap will be freed, when all MIMEFiled are deleted by HPACK Entry Eviction.
453  */
454 void
_mime_hdr_gc()455 HpackDynamicTable::_mime_hdr_gc()
456 {
457   if (this->_mhdr_old == nullptr) {
458     if (this->_mhdr->m_heap->total_used_size() >= HPACK_HDR_HEAP_THRESHOLD) {
459       this->_mhdr_old = this->_mhdr;
460       this->_mhdr     = new MIMEHdr();
461       this->_mhdr->create();
462     }
463   } else {
464     if (this->_mhdr_old->fields_count() == 0) {
465       this->_mhdr_old->destroy();
466       this->_mhdr_old = nullptr;
467     }
468   }
469 }
470 
471 int64_t
encode_indexed_header_field(uint8_t * buf_start,const uint8_t * buf_end,uint32_t index)472 encode_indexed_header_field(uint8_t *buf_start, const uint8_t *buf_end, uint32_t index)
473 {
474   if (buf_start >= buf_end) {
475     return -1;
476   }
477 
478   uint8_t *p = buf_start;
479 
480   // Index
481   const int64_t len = xpack_encode_integer(p, buf_end, index, 7);
482   if (len == -1) {
483     return -1;
484   }
485 
486   // Representation type
487   if (p + 1 >= buf_end) {
488     return -1;
489   }
490 
491   *p |= 0x80;
492   p += len;
493 
494   Debug("hpack_encode", "Encoded field: %d", index);
495   return p - buf_start;
496 }
497 
498 int64_t
encode_literal_header_field_with_indexed_name(uint8_t * buf_start,const uint8_t * buf_end,const MIMEFieldWrapper & header,uint32_t index,HpackIndexingTable & indexing_table,HpackField type)499 encode_literal_header_field_with_indexed_name(uint8_t *buf_start, const uint8_t *buf_end, const MIMEFieldWrapper &header,
500                                               uint32_t index, HpackIndexingTable &indexing_table, HpackField type)
501 {
502   uint8_t *p = buf_start;
503   int64_t len;
504   uint8_t prefix = 0, flag = 0;
505 
506   ink_assert(hpack_field_is_literal(type));
507 
508   switch (type) {
509   case HpackField::INDEXED_LITERAL:
510     indexing_table.add_header_field(header.field_get());
511     prefix = 6;
512     flag   = 0x40;
513     break;
514   case HpackField::NOINDEX_LITERAL:
515     prefix = 4;
516     flag   = 0x00;
517     break;
518   case HpackField::NEVERINDEX_LITERAL:
519     prefix = 4;
520     flag   = 0x10;
521     break;
522   default:
523     return -1;
524   }
525 
526   // Index
527   *p  = 0;
528   len = xpack_encode_integer(p, buf_end, index, prefix);
529   if (len == -1) {
530     return -1;
531   }
532 
533   // Representation type
534   if (p + 1 >= buf_end) {
535     return -1;
536   }
537   *p |= flag;
538   p += len;
539 
540   // Value String
541   int value_len;
542   const char *value = header.value_get(&value_len);
543   len               = xpack_encode_string(p, buf_end, value, value_len);
544   if (len == -1) {
545     return -1;
546   }
547   p += len;
548 
549   Debug("hpack_encode", "Encoded field: %d: %.*s", index, value_len, value);
550   return p - buf_start;
551 }
552 
553 int64_t
encode_literal_header_field_with_new_name(uint8_t * buf_start,const uint8_t * buf_end,const MIMEFieldWrapper & header,HpackIndexingTable & indexing_table,HpackField type)554 encode_literal_header_field_with_new_name(uint8_t *buf_start, const uint8_t *buf_end, const MIMEFieldWrapper &header,
555                                           HpackIndexingTable &indexing_table, HpackField type)
556 {
557   uint8_t *p = buf_start;
558   int64_t len;
559   uint8_t flag = 0;
560 
561   ink_assert(hpack_field_is_literal(type));
562 
563   switch (type) {
564   case HpackField::INDEXED_LITERAL:
565     indexing_table.add_header_field(header.field_get());
566     flag = 0x40;
567     break;
568   case HpackField::NOINDEX_LITERAL:
569     flag = 0x00;
570     break;
571   case HpackField::NEVERINDEX_LITERAL:
572     flag = 0x10;
573     break;
574   default:
575     return -1;
576   }
577   if (p + 1 >= buf_end) {
578     return -1;
579   }
580   *(p++) = flag;
581 
582   // Convert field name to lower case to follow HTTP2 spec.
583   // This conversion is needed because WKSs in MIMEFields is old fashioned
584   Arena arena;
585   int name_len;
586   const char *name = header.name_get(&name_len);
587   char *lower_name = arena.str_store(name, name_len);
588   for (int i = 0; i < name_len; i++) {
589     lower_name[i] = ParseRules::ink_tolower(lower_name[i]);
590   }
591 
592   // Name String
593   len = xpack_encode_string(p, buf_end, lower_name, name_len);
594   if (len == -1) {
595     return -1;
596   }
597   p += len;
598 
599   // Value String
600   int value_len;
601   const char *value = header.value_get(&value_len);
602   len               = xpack_encode_string(p, buf_end, value, value_len);
603   if (len == -1) {
604     return -1;
605   }
606 
607   p += len;
608 
609   Debug("hpack_encode", "Encoded field: %.*s: %.*s", name_len, name, value_len, value);
610   return p - buf_start;
611 }
612 
613 int64_t
encode_dynamic_table_size_update(uint8_t * buf_start,const uint8_t * buf_end,uint32_t size)614 encode_dynamic_table_size_update(uint8_t *buf_start, const uint8_t *buf_end, uint32_t size)
615 {
616   buf_start[0]      = 0x20;
617   const int64_t len = xpack_encode_integer(buf_start, buf_end, size, 5);
618   if (len == -1) {
619     return -1;
620   }
621 
622   return len;
623 }
624 
625 //
626 // [RFC 7541] 6.1. Indexed Header Field Representation
627 //
628 int64_t
decode_indexed_header_field(MIMEFieldWrapper & header,const uint8_t * buf_start,const uint8_t * buf_end,HpackIndexingTable & indexing_table)629 decode_indexed_header_field(MIMEFieldWrapper &header, const uint8_t *buf_start, const uint8_t *buf_end,
630                             HpackIndexingTable &indexing_table)
631 {
632   uint64_t index = 0;
633   int64_t len    = 0;
634 
635   len = xpack_decode_integer(index, buf_start, buf_end, 7);
636   if (len == XPACK_ERROR_COMPRESSION_ERROR) {
637     return HPACK_ERROR_COMPRESSION_ERROR;
638   }
639 
640   if (indexing_table.get_header_field(index, header) == HPACK_ERROR_COMPRESSION_ERROR) {
641     return HPACK_ERROR_COMPRESSION_ERROR;
642   }
643 
644   if (is_debug_tag_set("hpack_decode")) {
645     int decoded_name_len;
646     const char *decoded_name = header.name_get(&decoded_name_len);
647     int decoded_value_len;
648     const char *decoded_value = header.value_get(&decoded_value_len);
649 
650     Arena arena;
651     Debug("hpack_decode", "Decoded field: %s: %s", arena.str_store(decoded_name, decoded_name_len),
652           arena.str_store(decoded_value, decoded_value_len));
653   }
654 
655   return len;
656 }
657 
658 //
659 // [RFC 7541] 6.2. Literal Header Field Representation
660 // Decode Literal Header Field Representation based on HpackFieldType
661 //
662 int64_t
decode_literal_header_field(MIMEFieldWrapper & header,const uint8_t * buf_start,const uint8_t * buf_end,HpackIndexingTable & indexing_table)663 decode_literal_header_field(MIMEFieldWrapper &header, const uint8_t *buf_start, const uint8_t *buf_end,
664                             HpackIndexingTable &indexing_table)
665 {
666   const uint8_t *p         = buf_start;
667   bool isIncremental       = false;
668   uint64_t index           = 0;
669   int64_t len              = 0;
670   HpackField ftype         = hpack_parse_field_type(*p);
671   bool has_http2_violation = false;
672 
673   if (ftype == HpackField::INDEXED_LITERAL) {
674     len           = xpack_decode_integer(index, p, buf_end, 6);
675     isIncremental = true;
676   } else if (ftype == HpackField::NEVERINDEX_LITERAL) {
677     len = xpack_decode_integer(index, p, buf_end, 4);
678   } else {
679     ink_assert(ftype == HpackField::NOINDEX_LITERAL);
680     len = xpack_decode_integer(index, p, buf_end, 4);
681   }
682 
683   if (len == XPACK_ERROR_COMPRESSION_ERROR) {
684     return HPACK_ERROR_COMPRESSION_ERROR;
685   }
686 
687   p += len;
688 
689   Arena arena;
690 
691   // Decode header field name
692   if (index) {
693     indexing_table.get_header_field(index, header);
694   } else {
695     char *name_str        = nullptr;
696     uint64_t name_str_len = 0;
697 
698     len = xpack_decode_string(arena, &name_str, name_str_len, p, buf_end);
699     if (len == XPACK_ERROR_COMPRESSION_ERROR) {
700       return HPACK_ERROR_COMPRESSION_ERROR;
701     }
702 
703     // Check whether header field name is lower case
704     // XXX This check shouldn't be here because this rule is not a part of HPACK but HTTP2.
705     for (uint32_t i = 0; i < name_str_len; i++) {
706       if (ParseRules::is_upalpha(name_str[i])) {
707         has_http2_violation = true;
708         break;
709       }
710     }
711 
712     p += len;
713     header.name_set(name_str, name_str_len);
714   }
715 
716   // Decode header field value
717   char *value_str        = nullptr;
718   uint64_t value_str_len = 0;
719 
720   len = xpack_decode_string(arena, &value_str, value_str_len, p, buf_end);
721   if (len == XPACK_ERROR_COMPRESSION_ERROR) {
722     return HPACK_ERROR_COMPRESSION_ERROR;
723   }
724 
725   p += len;
726   header.value_set(value_str, value_str_len);
727 
728   // Incremental Indexing adds header to header table as new entry
729   if (isIncremental) {
730     indexing_table.add_header_field(header.field_get());
731   }
732 
733   // Print decoded header field
734   if (is_debug_tag_set("hpack_decode")) {
735     int decoded_name_len;
736     const char *decoded_name = header.name_get(&decoded_name_len);
737     int decoded_value_len;
738     const char *decoded_value = header.value_get(&decoded_value_len);
739 
740     Debug("hpack_decode", "Decoded field: %s: %s", arena.str_store(decoded_name, decoded_name_len),
741           arena.str_store(decoded_value, decoded_value_len));
742   }
743 
744   if (has_http2_violation) {
745     // XXX Need to return the length to continue decoding
746     return -(p - buf_start);
747   } else {
748     return p - buf_start;
749   }
750 }
751 
752 //
753 // [RFC 7541] 6.3. Dynamic Table Size Update
754 //
755 int64_t
update_dynamic_table_size(const uint8_t * buf_start,const uint8_t * buf_end,HpackIndexingTable & indexing_table,uint32_t maximum_table_size)756 update_dynamic_table_size(const uint8_t *buf_start, const uint8_t *buf_end, HpackIndexingTable &indexing_table,
757                           uint32_t maximum_table_size)
758 {
759   if (buf_start == buf_end) {
760     return HPACK_ERROR_COMPRESSION_ERROR;
761   }
762 
763   // Update header table size if its required.
764   uint64_t size = 0;
765   int64_t len   = xpack_decode_integer(size, buf_start, buf_end, 5);
766   if (len == XPACK_ERROR_COMPRESSION_ERROR) {
767     return HPACK_ERROR_COMPRESSION_ERROR;
768   }
769 
770   if (size > maximum_table_size) {
771     return HPACK_ERROR_COMPRESSION_ERROR;
772   }
773 
774   if (indexing_table.update_maximum_size(size) == false) {
775     return HPACK_ERROR_COMPRESSION_ERROR;
776   }
777 
778   return len;
779 }
780 
781 int64_t
hpack_decode_header_block(HpackIndexingTable & indexing_table,HTTPHdr * hdr,const uint8_t * in_buf,const size_t in_buf_len,uint32_t max_header_size,uint32_t maximum_table_size)782 hpack_decode_header_block(HpackIndexingTable &indexing_table, HTTPHdr *hdr, const uint8_t *in_buf, const size_t in_buf_len,
783                           uint32_t max_header_size, uint32_t maximum_table_size)
784 {
785   const uint8_t *cursor           = in_buf;
786   const uint8_t *const in_buf_end = in_buf + in_buf_len;
787   HdrHeap *heap                   = hdr->m_heap;
788   HTTPHdrImpl *hh                 = hdr->m_http;
789   bool header_field_started       = false;
790   bool has_http2_violation        = false;
791   uint32_t total_header_size      = 0;
792 
793   while (cursor < in_buf_end) {
794     int64_t read_bytes = 0;
795 
796     // decode a header field encoded by HPACK
797     MIMEField *field = mime_field_create(heap, hh->m_fields_impl);
798     MIMEFieldWrapper header(field, heap, hh->m_fields_impl);
799     HpackField ftype = hpack_parse_field_type(*cursor);
800 
801     switch (ftype) {
802     case HpackField::INDEX:
803       read_bytes = decode_indexed_header_field(header, cursor, in_buf_end, indexing_table);
804       if (read_bytes == HPACK_ERROR_COMPRESSION_ERROR) {
805         return HPACK_ERROR_COMPRESSION_ERROR;
806       }
807       cursor += read_bytes;
808       header_field_started = true;
809       break;
810     case HpackField::INDEXED_LITERAL:
811     case HpackField::NOINDEX_LITERAL:
812     case HpackField::NEVERINDEX_LITERAL:
813       read_bytes = decode_literal_header_field(header, cursor, in_buf_end, indexing_table);
814       if (read_bytes == HPACK_ERROR_COMPRESSION_ERROR) {
815         return HPACK_ERROR_COMPRESSION_ERROR;
816       }
817       if (read_bytes < 0) {
818         has_http2_violation = true;
819         read_bytes          = -read_bytes;
820       }
821       cursor += read_bytes;
822       header_field_started = true;
823       break;
824     case HpackField::TABLESIZE_UPDATE:
825       if (header_field_started) {
826         return HPACK_ERROR_COMPRESSION_ERROR;
827       }
828       read_bytes = update_dynamic_table_size(cursor, in_buf_end, indexing_table, maximum_table_size);
829       if (read_bytes == HPACK_ERROR_COMPRESSION_ERROR) {
830         return HPACK_ERROR_COMPRESSION_ERROR;
831       }
832       cursor += read_bytes;
833       continue;
834     }
835 
836     int name_len  = 0;
837     int value_len = 0;
838 
839     field->name_get(&name_len);
840     field->value_get(&value_len);
841     total_header_size += name_len + value_len;
842 
843     if (total_header_size > max_header_size) {
844       return HPACK_ERROR_SIZE_EXCEEDED_ERROR;
845     }
846 
847     // Store to HdrHeap
848     mime_hdr_field_attach(hh->m_fields_impl, field, 1, nullptr);
849   }
850   // Parsing all headers is done
851   if (has_http2_violation) {
852     return -(cursor - in_buf);
853   } else {
854     return cursor - in_buf;
855   }
856 }
857 
858 int64_t
hpack_encode_header_block(HpackIndexingTable & indexing_table,uint8_t * out_buf,const size_t out_buf_len,HTTPHdr * hdr,int32_t maximum_table_size)859 hpack_encode_header_block(HpackIndexingTable &indexing_table, uint8_t *out_buf, const size_t out_buf_len, HTTPHdr *hdr,
860                           int32_t maximum_table_size)
861 {
862   uint8_t *cursor                  = out_buf;
863   const uint8_t *const out_buf_end = out_buf + out_buf_len;
864   int64_t written                  = 0;
865 
866   ink_assert(http_hdr_type_get(hdr->m_http) != HTTP_TYPE_UNKNOWN);
867 
868   // Update dynamic table size
869   if (maximum_table_size >= 0) {
870     indexing_table.update_maximum_size(maximum_table_size);
871     written = encode_dynamic_table_size_update(cursor, out_buf_end, maximum_table_size);
872     if (written == HPACK_ERROR_COMPRESSION_ERROR) {
873       return HPACK_ERROR_COMPRESSION_ERROR;
874     }
875     cursor += written;
876   }
877 
878   MIMEFieldIter field_iter;
879   for (MIMEField *field = hdr->iter_get_first(&field_iter); field != nullptr; field = hdr->iter_get_next(&field_iter)) {
880     HpackField field_type;
881     MIMEFieldWrapper header(field, hdr->m_heap, hdr->m_http->m_fields_impl);
882     int name_len;
883     int value_len;
884     const char *name = header.name_get(&name_len);
885     header.value_get(&value_len);
886     // Choose field representation (See RFC7541 7.1.3)
887     // - Authorization header obviously should not be indexed
888     // - Short Cookie header should not be indexed because of low entropy
889     if ((ptr_len_casecmp(name, name_len, MIME_FIELD_COOKIE, MIME_LEN_COOKIE) == 0 && value_len < 20) ||
890         (ptr_len_casecmp(name, name_len, MIME_FIELD_AUTHORIZATION, MIME_LEN_AUTHORIZATION) == 0)) {
891       field_type = HpackField::NEVERINDEX_LITERAL;
892     } else {
893       field_type = HpackField::INDEXED_LITERAL;
894     }
895     const HpackLookupResult result = indexing_table.lookup(header);
896     switch (result.match_type) {
897     case HpackMatch::NONE:
898       written = encode_literal_header_field_with_new_name(cursor, out_buf_end, header, indexing_table, field_type);
899       break;
900     case HpackMatch::NAME:
901       written =
902         encode_literal_header_field_with_indexed_name(cursor, out_buf_end, header, result.index, indexing_table, field_type);
903       break;
904     case HpackMatch::EXACT:
905       written = encode_indexed_header_field(cursor, out_buf_end, result.index);
906       break;
907     default:
908       // Does it happen?
909       written = 0;
910       break;
911     }
912     if (written == HPACK_ERROR_COMPRESSION_ERROR) {
913       return HPACK_ERROR_COMPRESSION_ERROR;
914     }
915     cursor += written;
916   }
917   return cursor - out_buf;
918 }
919 
920 int32_t
hpack_get_maximum_table_size(HpackIndexingTable & indexing_table)921 hpack_get_maximum_table_size(HpackIndexingTable &indexing_table)
922 {
923   return indexing_table.maximum_size();
924 }
925