xref: /trafficserver/proxy/http3/QPACK.h (revision 763aa8e1)
1 /** @file
2  *
3  *  A brief file description
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 #pragma once
25 
26 #include <map>
27 
28 #include "I_EventSystem.h"
29 #include "I_Event.h"
30 #include "I_IOBuffer.h"
31 #include "tscore/Arena.h"
32 #include "tscpp/util/IntrusiveDList.h"
33 #include "MIME.h"
34 #include "HTTP.h"
35 #include "QUICApplication.h"
36 #include "QUICConnection.h"
37 
38 class HTTPHdr;
39 
40 enum {
41   QPACK_EVENT_DECODE_COMPLETE = QPACK_EVENT_EVENTS_START,
42   QPACK_EVENT_DECODE_FAILED,
43 };
44 
45 class QPACK : public QUICApplication
46 {
47 public:
48   QPACK(QUICConnection *qc, uint32_t max_header_list_size, uint16_t max_table_size, uint16_t max_blocking_streams);
49   virtual ~QPACK();
50 
51   int event_handler(int event, Event *data);
52 
53   /*
54    * header_block must have enough size to store all headers in header_set.
55    * The maximum size can be estimated with QPACK::estimate_header_block_size().
56    */
57   int encode(uint64_t stream_id, HTTPHdr &header_set, MIOBuffer *header_block, uint64_t &header_block_len);
58 
59   /*
60    * This will emit either of two events below:
61    * - QPACK_EVENT_DECODE_COMPLETE (Data: *HTTPHdr)
62    * - QPACK_EVENT_DECODE_FAILED (Data: nullptr)
63    */
64   int decode(uint64_t stream_id, const uint8_t *header_block, size_t header_block_len, HTTPHdr &hdr, Continuation *cont,
65              EThread *thread = this_ethread());
66 
67   int cancel(uint64_t stream_id);
68 
69   void set_encoder_stream(QUICStreamIO *stream_io);
70   void set_decoder_stream(QUICStreamIO *stream_io);
71 
72   void update_max_header_list_size(uint32_t max_header_list_size);
73   void update_max_table_size(uint16_t max_table_size);
74   void update_max_blocking_streams(uint16_t max_blocking_streams);
75 
76   static size_t estimate_header_block_size(const HTTPHdr &header_set);
77 
78 private:
79   struct LookupResult {
80     uint16_t index                                  = 0;
81     enum MatchType { NONE, NAME, EXACT } match_type = MatchType::NONE;
82   };
83 
84   struct Header {
HeaderQPACK::Header85     Header(const char *n, const char *v) : name(n), value(v), name_len(strlen(name)), value_len(strlen(value)) {}
86     const char *name;
87     const char *value;
88     const int name_len;
89     const int value_len;
90   };
91 
92   class StaticTable
93   {
94   public:
95     static const LookupResult lookup(uint16_t index, const char **name, int *name_len, const char **value, int *value_len);
96     static const LookupResult lookup(const char *name, int name_len, const char *value, int value_len);
97 
98   private:
99     static const Header STATIC_HEADER_FIELDS[];
100   };
101 
102   struct DynamicTableEntry {
103     uint16_t index     = 0;
104     uint16_t offset    = 0;
105     uint16_t name_len  = 0;
106     uint16_t value_len = 0;
107     uint16_t ref_count = 0;
108   };
109 
110   class DynamicTableStorage
111   {
112   public:
113     DynamicTableStorage(uint16_t size);
114     ~DynamicTableStorage();
115     void read(uint16_t offset, const char **name, uint16_t name_len, const char **value, uint16_t value_len);
116     uint16_t write(const char *name, uint16_t name_len, const char *value, uint16_t value_len);
117     void erase(uint16_t name_len, uint16_t value_len);
118 
119   private:
120     uint16_t _overwrite_threshold = 0;
121     uint8_t *_data                = nullptr;
122     uint16_t _data_size           = 0;
123     uint16_t _head                = 0;
124     uint16_t _tail                = 0;
125   };
126 
127   class DynamicTable
128   {
129   public:
130     DynamicTable(uint16_t size);
131     ~DynamicTable();
132 
133     const LookupResult lookup(uint16_t index, const char **name, int *name_len, const char **value, int *value_len);
134     const LookupResult lookup(const char *name, int name_len, const char *value, int value_len);
135     const LookupResult insert_entry(bool is_static, uint16_t index, const char *value, uint16_t value_len);
136     const LookupResult insert_entry(const char *name, uint16_t name_len, const char *value, uint16_t value_len);
137     const LookupResult duplicate_entry(uint16_t current_index);
138     bool should_duplicate(uint16_t index);
139     void update_size(uint16_t max_size);
140     void ref_entry(uint16_t index);
141     void unref_entry(uint16_t index);
142     uint16_t largest_index();
143 
144   private:
145     uint16_t _available        = 0;
146     uint16_t _entries_inserted = 0;
147 
148     // FIXME It may be better to split this array into small arrays to reduce memory footprint
149     struct DynamicTableEntry *_entries = nullptr;
150     uint16_t _max_entries              = 0;
151     uint16_t _entries_head             = 0;
152     uint16_t _entries_tail             = 0;
153     DynamicTableStorage *_storage      = nullptr;
154   };
155 
156   class DecodeRequest
157   {
158   public:
DecodeRequest(uint16_t largest_reference,EThread * thread,Continuation * continuation,uint64_t stream_id,const uint8_t * header_block,size_t header_block_len,HTTPHdr & hdr)159     DecodeRequest(uint16_t largest_reference, EThread *thread, Continuation *continuation, uint64_t stream_id,
160                   const uint8_t *header_block, size_t header_block_len, HTTPHdr &hdr)
161       : _largest_reference(largest_reference),
162         _thread(thread),
163         _continuation(continuation),
164         _stream_id(stream_id),
165         _header_block(header_block),
166         _header_block_len(header_block_len),
167         _hdr(hdr)
168     {
169     }
170 
171     uint16_t
largest_reference()172     largest_reference()
173     {
174       return this->_largest_reference;
175     }
176 
177     EThread *
thread()178     thread()
179     {
180       return this->_thread;
181     }
182 
183     Continuation *
continuation()184     continuation()
185     {
186       return this->_continuation;
187     }
188 
189     uint64_t
stream_id()190     stream_id()
191     {
192       return this->_stream_id;
193     }
194 
195     const uint8_t *
header_block()196     header_block()
197     {
198       return this->_header_block;
199     }
200 
201     size_t
header_block_len()202     header_block_len()
203     {
204       return this->_header_block_len;
205     }
206 
207     HTTPHdr &
hdr()208     hdr()
209     {
210       return this->_hdr;
211     }
212 
213     class Linkage
214     {
215     public:
216       static DecodeRequest *&
next_ptr(DecodeRequest * t)217       next_ptr(DecodeRequest *t)
218       {
219         return *reinterpret_cast<DecodeRequest **>(&t->_next);
220       }
221       static DecodeRequest *&
prev_ptr(DecodeRequest * t)222       prev_ptr(DecodeRequest *t)
223       {
224         return *reinterpret_cast<DecodeRequest **>(&t->_prev);
225       }
226     };
227 
228   private:
229     uint16_t _largest_reference;
230     EThread *_thread;
231     Continuation *_continuation;
232     uint64_t _stream_id;
233     const uint8_t *_header_block;
234     size_t _header_block_len;
235     HTTPHdr &_hdr;
236 
237     // For IntrusiveDList support
238     DecodeRequest *_next = nullptr;
239     DecodeRequest *_prev = nullptr;
240   };
241 
242   struct EntryReference {
243     uint16_t smallest;
244     uint16_t largest;
245   };
246 
247   DynamicTable _dynamic_table;
248   std::map<uint64_t, struct EntryReference> _references;
249   uint32_t _max_header_list_size = 0;
250   uint16_t _max_table_size       = 0;
251   uint16_t _max_blocking_streams = 0;
252 
253   Continuation *_event_handler = nullptr;
254   void _resume_decode();
255   void _abort_decode();
256 
257   bool _invalid = false;
258 
259   ts::IntrusiveDList<DecodeRequest::Linkage> _blocked_list;
260   bool _add_to_blocked_list(DecodeRequest *decode_request);
261 
262   uint16_t _largest_known_received_index = 0;
263   void _update_largest_known_received_index_by_insert_count(uint16_t insert_count);
264   void _update_largest_known_received_index_by_stream_id(uint64_t stream_id);
265 
266   void _update_reference_counts(uint64_t stream_id);
267 
268   // Encoder Stream
269   int _read_insert_with_name_ref(QUICStreamIO &stream_io, bool &is_static, uint16_t &index, Arena &arena, char **value,
270                                  uint16_t &value_len);
271   int _read_insert_without_name_ref(QUICStreamIO &stream_io, Arena &arena, char **name, uint16_t &name_len, char **value,
272                                     uint16_t &value_len);
273   int _read_duplicate(QUICStreamIO &stream_io, uint16_t &index);
274   int _read_dynamic_table_size_update(QUICStreamIO &stream_io, uint16_t &max_size);
275   int _write_insert_with_name_ref(uint16_t index, bool dynamic, const char *value, uint16_t value_len);
276   int _write_insert_without_name_ref(const char *name, int name_len, const char *value, uint16_t value_len);
277   int _write_duplicate(uint16_t index);
278   int _write_dynamic_table_size_update(uint16_t max_size);
279 
280   // Decoder Stream
281   int _read_table_state_synchronize(QUICStreamIO &stream_io, uint16_t &insert_count);
282   int _read_header_acknowledgement(QUICStreamIO &stream_io, uint64_t &stream_id);
283   int _read_stream_cancellation(QUICStreamIO &stream_io, uint64_t &stream_id);
284   int _write_table_state_syncrhonize(uint16_t insert_count);
285   int _write_header_acknowledgement(uint64_t stream_id);
286   int _write_stream_cancellation(uint64_t stream_id);
287 
288   // Request and Push Streams
289   int _encode_prefix(uint16_t largest_reference, uint16_t base_index, IOBufferBlock *prefix);
290   int _encode_header(const MIMEField &field, uint16_t base_index, IOBufferBlock *compressed_header, uint16_t &referred_index);
291   int _encode_indexed_header_field(uint16_t index, uint16_t base_index, bool dynamic_table, IOBufferBlock *compressed_header);
292   int _encode_indexed_header_field_with_postbase_index(uint16_t index, uint16_t base_index, bool never_index,
293                                                        IOBufferBlock *compressed_header);
294   int _encode_literal_header_field_with_name_ref(uint16_t index, bool dynamic_table, uint16_t base_index, const char *value,
295                                                  int value_len, bool never_index, IOBufferBlock *compressed_header);
296   int _encode_literal_header_field_without_name_ref(const char *name, int name_len, const char *value, int value_len,
297                                                     bool never_index, IOBufferBlock *compressed_header);
298   int _encode_literal_header_field_with_postbase_name_ref(uint16_t index, uint16_t base_index, const char *value, int value_len,
299                                                           bool never_index, IOBufferBlock *compressed_header);
300 
301   void _decode(EThread *ethread, Continuation *cont, uint64_t stream_id, const uint8_t *header_block, size_t header_block_len,
302                HTTPHdr &hdr);
303   int _decode_header(const uint8_t *header_block, size_t header_block_len, HTTPHdr &hdr);
304   int _decode_indexed_header_field(int16_t base_index, const uint8_t *buf, size_t buf_len, HTTPHdr &hdr, uint32_t &header_len);
305   int _decode_indexed_header_field_with_postbase_index(int16_t base_index, const uint8_t *buf, size_t buf_len, HTTPHdr &hdr,
306                                                        uint32_t &header_len);
307   int _decode_literal_header_field_with_name_ref(int16_t base_index, const uint8_t *buf, size_t buf_len, HTTPHdr &hdr,
308                                                  uint32_t &header_len);
309   int _decode_literal_header_field_without_name_ref(const uint8_t *buf, size_t buf_len, HTTPHdr &hdr, uint32_t &header_len);
310   int _decode_literal_header_field_with_postbase_name_ref(int16_t base_index, const uint8_t *buf, size_t buf_len, HTTPHdr &hdr,
311                                                           uint32_t &header_len);
312 
313   // Utilities
314   uint16_t _calc_absolute_index_from_relative_index(uint16_t base_index, uint16_t relative_index);
315   uint16_t _calc_absolute_index_from_postbase_index(uint16_t base_index, uint16_t postbase_index);
316   uint16_t _calc_relative_index_from_absolute_index(uint16_t base_index, uint16_t absolute_index);
317   uint16_t _calc_postbase_index_from_absolute_index(uint16_t base_index, uint16_t absolute_index);
318   void _attach_header(HTTPHdr &hdr, const char *name, int name_len, const char *value, int value_len, bool never_index);
319 
320   int _on_read_ready(QUICStreamIO &stream_io);
321   int _on_decoder_stream_read_ready(QUICStreamIO &stream_io);
322   int _on_encoder_stream_read_ready(QUICStreamIO &stream_io);
323 
324   int _on_write_ready(QUICStreamIO &stream_io);
325   int _on_decoder_write_ready(QUICStreamIO &stream_io);
326   int _on_encoder_write_ready(QUICStreamIO &stream_io);
327 
328   // Stream numbers
329   // FIXME How are these stream ids negotiated? In interop, encoder stream id have to be 0 and decoder stream id must not be used.
330   uint64_t _encoder_stream_id = 0;
331   uint64_t _decoder_stream_id = 9999;
332 
333   // Chain of sending instructions
334   MIOBuffer *_encoder_stream_sending_instructions;
335   MIOBuffer *_decoder_stream_sending_instructions;
336   IOBufferReader *_encoder_stream_sending_instructions_reader;
337   IOBufferReader *_decoder_stream_sending_instructions_reader;
338 };
339