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

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