1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#include "hpacktable_p.h"
5
6#include <QtCore/qdebug.h>
7
8#include <algorithm>
9#include <cstddef>
10#include <cstring>
11#include <limits>
12
13
14QT_BEGIN_NAMESPACE
15
16namespace HPack
17{
18
19HeaderSize entry_size(QByteArrayView name, QByteArrayView value)
20{
21 // 32 comes from HPACK:
22 // "4.1 Calculating Table Size
23 // Note: The additional 32 octets account for an estimated overhead associated
24 // with an entry. For example, an entry structure using two 64-bit pointers
25 // to reference the name and the value of the entry and two 64-bit integers
26 // for counting the number of references to the name and value would have
27 // 32 octets of overhead."
28
29 const unsigned sum = unsigned(name.size() + value.size());
30 if (std::numeric_limits<unsigned>::max() - 32 < sum)
31 return HeaderSize();
32 return HeaderSize(true, quint32(sum + 32));
33}
34
35namespace
36{
37
38int compare(const QByteArray &lhs, const QByteArray &rhs)
39{
40 if (const int minLen = std::min(a: lhs.size(), b: rhs.size())) {
41 // We use memcmp, since strings in headers are allowed
42 // to contain '\0'.
43 const int cmp = std::memcmp(s1: lhs.constData(), s2: rhs.constData(), n: std::size_t(minLen));
44 if (cmp)
45 return cmp;
46 }
47
48 return lhs.size() - rhs.size();
49}
50
51} // unnamed namespace
52
53FieldLookupTable::SearchEntry::SearchEntry()
54 : field(),
55 chunk(),
56 offset(),
57 table()
58{
59}
60
61FieldLookupTable::SearchEntry::SearchEntry(const HeaderField *f,
62 const Chunk *c,
63 quint32 o,
64 const FieldLookupTable *t)
65 : field(f),
66 chunk(c),
67 offset(o),
68 table(t)
69{
70 Q_ASSERT(field);
71}
72
73bool FieldLookupTable::SearchEntry::operator < (const SearchEntry &rhs)const
74{
75 Q_ASSERT(field);
76 Q_ASSERT(rhs.field);
77
78 int cmp = compare(lhs: field->name, rhs: rhs.field->name);
79 if (cmp)
80 return cmp < 0;
81
82 cmp = compare(lhs: field->value, rhs: rhs.field->value);
83 if (cmp)
84 return cmp < 0;
85
86 if (!chunk) // 'this' is not in the searchIndex.
87 return rhs.chunk;
88
89 if (!rhs.chunk) // not in the searchIndex.
90 return false;
91
92 Q_ASSERT(table);
93 Q_ASSERT(rhs.table == table);
94
95 const quint32 leftChunkIndex = table->indexOfChunk(chunk);
96 const quint32 rightChunkIndex = rhs.table->indexOfChunk(chunk: rhs.chunk);
97
98 // Later added - smaller is chunk index (since we push_front).
99 if (leftChunkIndex != rightChunkIndex)
100 return leftChunkIndex > rightChunkIndex;
101
102 // Later added - smaller is offset.
103 return offset > rhs.offset;
104}
105
106FieldLookupTable::FieldLookupTable(quint32 maxSize, bool use)
107 : maxTableSize(maxSize),
108 tableCapacity(maxSize),
109 useIndex(use),
110 nDynamic(),
111 begin(),
112 end(),
113 dataSize()
114{
115}
116
117
118bool FieldLookupTable::prependField(const QByteArray &name, const QByteArray &value)
119{
120 const auto entrySize = entry_size(name, value);
121 if (!entrySize.first)
122 return false;
123
124 if (entrySize.second > tableCapacity) {
125 clearDynamicTable();
126 return true;
127 }
128
129 while (nDynamic && tableCapacity - dataSize < entrySize.second)
130 evictEntry();
131
132 if (!begin) {
133 // Either no more space or empty table ...
134 chunks.push_front(x: ChunkPtr(new Chunk(ChunkSize)));
135 end += ChunkSize;
136 begin = ChunkSize;
137 }
138
139 --begin;
140
141 dataSize += entrySize.second;
142 ++nDynamic;
143
144 auto &newField = front();
145 newField.name = name;
146 newField.value = value;
147
148 if (useIndex) {
149 const auto result = searchIndex.insert(x: frontKey());
150 Q_UNUSED(result);
151 Q_ASSERT(result.second);
152 }
153
154 return true;
155}
156
157void FieldLookupTable::evictEntry()
158{
159 if (!nDynamic)
160 return;
161
162 Q_ASSERT(end != begin);
163
164 if (useIndex) {
165 const auto res = searchIndex.erase(x: backKey());
166 Q_UNUSED(res);
167 Q_ASSERT(res == 1);
168 }
169
170 const HeaderField &field = back();
171 const auto entrySize = entry_size(entry: field);
172 Q_ASSERT(entrySize.first);
173 Q_ASSERT(dataSize >= entrySize.second);
174 dataSize -= entrySize.second;
175
176 --nDynamic;
177 --end;
178
179 if (end == begin) {
180 Q_ASSERT(chunks.size() == 1);
181 end = ChunkSize;
182 begin = end;
183 } else if (!(end % ChunkSize)) {
184 chunks.pop_back();
185 }
186}
187
188quint32 FieldLookupTable::numberOfEntries() const
189{
190 return quint32(staticPart().size()) + nDynamic;
191}
192
193quint32 FieldLookupTable::numberOfStaticEntries() const
194{
195 return quint32(staticPart().size());
196}
197
198quint32 FieldLookupTable::numberOfDynamicEntries() const
199{
200 return nDynamic;
201}
202
203quint32 FieldLookupTable::dynamicDataSize() const
204{
205 return dataSize;
206}
207
208void FieldLookupTable::clearDynamicTable()
209{
210 searchIndex.clear();
211 chunks.clear();
212 begin = 0;
213 end = 0;
214 nDynamic = 0;
215 dataSize = 0;
216}
217
218bool FieldLookupTable::indexIsValid(quint32 index) const
219{
220 return index && index <= staticPart().size() + nDynamic;
221}
222
223quint32 FieldLookupTable::indexOf(const QByteArray &name, const QByteArray &value)const
224{
225 // Start from the static part first:
226 const auto &table = staticPart();
227 const HeaderField field(name, value);
228 const auto staticPos = findInStaticPart(field, mode: CompareMode::nameAndValue);
229 if (staticPos != table.end()) {
230 if (staticPos->name == name && staticPos->value == value)
231 return quint32(staticPos - table.begin() + 1);
232 }
233
234 // Now we have to lookup in our dynamic part ...
235 if (!useIndex) {
236 qCritical(msg: "lookup in dynamic table requires search index enabled");
237 return 0;
238 }
239
240 const SearchEntry key(&field, nullptr, 0, this);
241 const auto pos = searchIndex.lower_bound(x: key);
242 if (pos != searchIndex.end()) {
243 const HeaderField &found = *pos->field;
244 if (found.name == name && found.value == value)
245 return keyToIndex(key: *pos);
246 }
247
248 return 0;
249}
250
251quint32 FieldLookupTable::indexOf(const QByteArray &name) const
252{
253 // Start from the static part first:
254 const auto &table = staticPart();
255 const HeaderField field(name, QByteArray());
256 const auto staticPos = findInStaticPart(field, mode: CompareMode::nameOnly);
257 if (staticPos != table.end()) {
258 if (staticPos->name == name)
259 return quint32(staticPos - table.begin() + 1);
260 }
261
262 // Now we have to lookup in our dynamic part ...
263 if (!useIndex) {
264 qCritical(msg: "lookup in dynamic table requires search index enabled");
265 return 0;
266 }
267
268 const SearchEntry key(&field, nullptr, 0, this);
269 const auto pos = searchIndex.lower_bound(x: key);
270 if (pos != searchIndex.end()) {
271 const HeaderField &found = *pos->field;
272 if (found.name == name)
273 return keyToIndex(key: *pos);
274 }
275
276 return 0;
277}
278
279bool FieldLookupTable::field(quint32 index, QByteArray *name, QByteArray *value) const
280{
281 Q_ASSERT(name);
282 Q_ASSERT(value);
283
284 if (!indexIsValid(index))
285 return false;
286
287 const auto &table = staticPart();
288 if (index - 1 < table.size()) {
289 *name = table[index - 1].name;
290 *value = table[index - 1].value;
291 return true;
292 }
293
294 index = index - 1 - quint32(table.size()) + begin;
295 const auto chunkIndex = index / ChunkSize;
296 Q_ASSERT(chunkIndex < chunks.size());
297 const auto offset = index % ChunkSize;
298 const HeaderField &found = (*chunks[chunkIndex])[offset];
299 *name = found.name;
300 *value = found.value;
301
302 return true;
303}
304
305bool FieldLookupTable::fieldName(quint32 index, QByteArray *dst) const
306{
307 Q_ASSERT(dst);
308 return field(index, name: dst, value: &dummyDst);
309}
310
311bool FieldLookupTable::fieldValue(quint32 index, QByteArray *dst) const
312{
313 Q_ASSERT(dst);
314 return field(index, name: &dummyDst, value: dst);
315}
316
317const HeaderField &FieldLookupTable::front() const
318{
319 Q_ASSERT(nDynamic && begin != end && chunks.size());
320 return (*chunks[0])[begin];
321}
322
323HeaderField &FieldLookupTable::front()
324{
325 Q_ASSERT(nDynamic && begin != end && chunks.size());
326 return (*chunks[0])[begin];
327}
328
329const HeaderField &FieldLookupTable::back() const
330{
331 Q_ASSERT(nDynamic && end && end != begin);
332
333 const quint32 absIndex = end - 1;
334 const quint32 chunkIndex = absIndex / ChunkSize;
335 Q_ASSERT(chunkIndex < chunks.size());
336 const quint32 offset = absIndex % ChunkSize;
337 return (*chunks[chunkIndex])[offset];
338}
339
340quint32 FieldLookupTable::indexOfChunk(const Chunk *chunk) const
341{
342 Q_ASSERT(chunk);
343
344 for (size_type i = 0; i < chunks.size(); ++i) {
345 if (chunks[i].get() == chunk)
346 return quint32(i);
347 }
348
349 Q_UNREACHABLE_RETURN(0);
350}
351
352quint32 FieldLookupTable::keyToIndex(const SearchEntry &key) const
353{
354 Q_ASSERT(key.chunk);
355
356 const auto chunkIndex = indexOfChunk(chunk: key.chunk);
357 const auto offset = key.offset;
358 Q_ASSERT(offset < ChunkSize);
359 Q_ASSERT(chunkIndex || offset >= begin);
360
361 return quint32(offset + chunkIndex * ChunkSize - begin + 1 + staticPart().size());
362}
363
364FieldLookupTable::SearchEntry FieldLookupTable::frontKey() const
365{
366 Q_ASSERT(chunks.size() && end != begin);
367 return SearchEntry(&front(), chunks.front().get(), begin, this);
368}
369
370FieldLookupTable::SearchEntry FieldLookupTable::backKey() const
371{
372 Q_ASSERT(chunks.size() && end != begin);
373
374 const HeaderField &field = back();
375 const quint32 absIndex = end - 1;
376 const auto offset = absIndex % ChunkSize;
377 const auto chunk = chunks[absIndex / ChunkSize].get();
378
379 return SearchEntry(&field, chunk, offset, this);
380}
381
382bool FieldLookupTable::updateDynamicTableSize(quint32 size)
383{
384 if (!size) {
385 clearDynamicTable();
386 return true;
387 }
388
389 if (size > maxTableSize)
390 return false;
391
392 tableCapacity = size;
393 while (nDynamic && dataSize > tableCapacity)
394 evictEntry();
395
396 return true;
397}
398
399void FieldLookupTable::setMaxDynamicTableSize(quint32 size)
400{
401 // This is for an external user, for example, HTTP2 protocol
402 // layer that can receive SETTINGS frame from its peer.
403 // No validity checks here, up to this external user.
404 // We update max size and capacity (this can also result in
405 // items evicted or even dynamic table completely cleared).
406 maxTableSize = size;
407 updateDynamicTableSize(size);
408}
409
410// This data is from the HPACK's specs and it's quite conveniently sorted,
411// except ... 'accept' is in the wrong position, see how we handle it below.
412const std::vector<HeaderField> &FieldLookupTable::staticPart()
413{
414 static std::vector<HeaderField> table = {
415 {":authority", ""},
416 {":method", "GET"},
417 {":method", "POST"},
418 {":path", "/"},
419 {":path", "/index.html"},
420 {":scheme", "http"},
421 {":scheme", "https"},
422 {":status", "200"},
423 {":status", "204"},
424 {":status", "206"},
425 {":status", "304"},
426 {":status", "400"},
427 {":status", "404"},
428 {":status", "500"},
429 {"accept-charset", ""},
430 {"accept-encoding", "gzip, deflate"},
431 {"accept-language", ""},
432 {"accept-ranges", ""},
433 {"accept", ""},
434 {"access-control-allow-origin", ""},
435 {"age", ""},
436 {"allow", ""},
437 {"authorization", ""},
438 {"cache-control", ""},
439 {"content-disposition", ""},
440 {"content-encoding", ""},
441 {"content-language", ""},
442 {"content-length", ""},
443 {"content-location", ""},
444 {"content-range", ""},
445 {"content-type", ""},
446 {"cookie", ""},
447 {"date", ""},
448 {"etag", ""},
449 {"expect", ""},
450 {"expires", ""},
451 {"from", ""},
452 {"host", ""},
453 {"if-match", ""},
454 {"if-modified-since", ""},
455 {"if-none-match", ""},
456 {"if-range", ""},
457 {"if-unmodified-since", ""},
458 {"last-modified", ""},
459 {"link", ""},
460 {"location", ""},
461 {"max-forwards", ""},
462 {"proxy-authenticate", ""},
463 {"proxy-authorization", ""},
464 {"range", ""},
465 {"referer", ""},
466 {"refresh", ""},
467 {"retry-after", ""},
468 {"server", ""},
469 {"set-cookie", ""},
470 {"strict-transport-security", ""},
471 {"transfer-encoding", ""},
472 {"user-agent", ""},
473 {"vary", ""},
474 {"via", ""},
475 {"www-authenticate", ""}
476 };
477
478 return table;
479}
480
481std::vector<HeaderField>::const_iterator FieldLookupTable::findInStaticPart(const HeaderField &field, CompareMode mode)
482{
483 const auto &table = staticPart();
484 const auto acceptPos = table.begin() + 18;
485 if (field.name == "accept") {
486 if (mode == CompareMode::nameAndValue && field.value != "")
487 return table.end();
488 return acceptPos;
489 }
490
491 auto predicate = [mode](const HeaderField &lhs, const HeaderField &rhs) {
492 const int cmp = compare(lhs: lhs.name, rhs: rhs.name);
493 if (cmp)
494 return cmp < 0;
495 else if (mode == CompareMode::nameAndValue)
496 return compare(lhs: lhs.value, rhs: rhs.value) < 0;
497 return false;
498 };
499
500 const auto staticPos = std::lower_bound(first: table.begin(), last: acceptPos, val: field, comp: predicate);
501 if (staticPos != acceptPos)
502 return staticPos;
503
504 return std::lower_bound(first: acceptPos + 1, last: table.end(), val: field, comp: predicate);
505}
506
507}
508
509QT_END_NAMESPACE
510

source code of qtbase/src/network/access/http2/hpacktable.cpp