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

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