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
210void FieldLookupTable::clearDynamicTable()
211{
212 searchIndex.clear();
213 chunks.clear();
214 begin = 0;
215 end = 0;
216 nDynamic = 0;
217 dataSize = 0;
218}
219
220bool FieldLookupTable::indexIsValid(quint32 index) const
221{
222 return index && index <= staticPart().size() + nDynamic;
223}
224
225quint32 FieldLookupTable::indexOf(const QByteArray &name, const QByteArray &value)const
226{
227 // Start from the static part first:
228 const auto &table = staticPart();
229 const HeaderField field(name, value);
230 const auto staticPos = findInStaticPart(field, mode: CompareMode::nameAndValue);
231 if (staticPos != table.end()) {
232 if (staticPos->name == name && staticPos->value == value)
233 return quint32(staticPos - table.begin() + 1);
234 }
235
236 // Now we have to lookup in our dynamic part ...
237 if (!useIndex) {
238 qCritical(msg: "lookup in dynamic table requires search index enabled");
239 return 0;
240 }
241
242 const SearchEntry key(&field, nullptr, 0, this);
243 const auto pos = searchIndex.lower_bound(x: key);
244 if (pos != searchIndex.end()) {
245 const HeaderField &found = *pos->field;
246 if (found.name == name && found.value == value)
247 return keyToIndex(key: *pos);
248 }
249
250 return 0;
251}
252
253quint32 FieldLookupTable::indexOf(const QByteArray &name) const
254{
255 // Start from the static part first:
256 const auto &table = staticPart();
257 const HeaderField field(name, QByteArray());
258 const auto staticPos = findInStaticPart(field, mode: CompareMode::nameOnly);
259 if (staticPos != table.end()) {
260 if (staticPos->name == name)
261 return quint32(staticPos - table.begin() + 1);
262 }
263
264 // Now we have to lookup in our dynamic part ...
265 if (!useIndex) {
266 qCritical(msg: "lookup in dynamic table requires search index enabled");
267 return 0;
268 }
269
270 const SearchEntry key(&field, nullptr, 0, this);
271 const auto pos = searchIndex.lower_bound(x: key);
272 if (pos != searchIndex.end()) {
273 const HeaderField &found = *pos->field;
274 if (found.name == name)
275 return keyToIndex(key: *pos);
276 }
277
278 return 0;
279}
280
281bool FieldLookupTable::field(quint32 index, QByteArray *name, QByteArray *value) const
282{
283 Q_ASSERT(name);
284 Q_ASSERT(value);
285
286 if (!indexIsValid(index))
287 return false;
288
289 const auto &table = staticPart();
290 if (index - 1 < table.size()) {
291 *name = table[index - 1].name;
292 *value = table[index - 1].value;
293 return true;
294 }
295
296 index = index - 1 - quint32(table.size()) + begin;
297 const auto chunkIndex = index / ChunkSize;
298 Q_ASSERT(chunkIndex < chunks.size());
299 const auto offset = index % ChunkSize;
300 const HeaderField &found = (*chunks[chunkIndex])[offset];
301 *name = found.name;
302 *value = found.value;
303
304 return true;
305}
306
307bool FieldLookupTable::fieldName(quint32 index, QByteArray *dst) const
308{
309 Q_ASSERT(dst);
310 return field(index, name: dst, value: &dummyDst);
311}
312
313bool FieldLookupTable::fieldValue(quint32 index, QByteArray *dst) const
314{
315 Q_ASSERT(dst);
316 return field(index, name: &dummyDst, value: dst);
317}
318
319const HeaderField &FieldLookupTable::front() const
320{
321 Q_ASSERT(nDynamic && begin != end && chunks.size());
322 return (*chunks[0])[begin];
323}
324
325HeaderField &FieldLookupTable::front()
326{
327 Q_ASSERT(nDynamic && begin != end && chunks.size());
328 return (*chunks[0])[begin];
329}
330
331const HeaderField &FieldLookupTable::back() const
332{
333 Q_ASSERT(nDynamic && end && end != begin);
334
335 const quint32 absIndex = end - 1;
336 const quint32 chunkIndex = absIndex / ChunkSize;
337 Q_ASSERT(chunkIndex < chunks.size());
338 const quint32 offset = absIndex % ChunkSize;
339 return (*chunks[chunkIndex])[offset];
340}
341
342quint32 FieldLookupTable::indexOfChunk(const Chunk *chunk) const
343{
344 Q_ASSERT(chunk);
345
346 for (size_type i = 0; i < chunks.size(); ++i) {
347 if (chunks[i].get() == chunk)
348 return quint32(i);
349 }
350
351 Q_UNREACHABLE_RETURN(0);
352}
353
354quint32 FieldLookupTable::keyToIndex(const SearchEntry &key) const
355{
356 Q_ASSERT(key.chunk);
357
358 const auto chunkIndex = indexOfChunk(chunk: key.chunk);
359 const auto offset = key.offset;
360 Q_ASSERT(offset < ChunkSize);
361 Q_ASSERT(chunkIndex || offset >= begin);
362
363 return quint32(offset + chunkIndex * ChunkSize - begin + 1 + staticPart().size());
364}
365
366FieldLookupTable::SearchEntry FieldLookupTable::frontKey() const
367{
368 Q_ASSERT(chunks.size() && end != begin);
369 return SearchEntry(&front(), chunks.front().get(), begin, this);
370}
371
372FieldLookupTable::SearchEntry FieldLookupTable::backKey() const
373{
374 Q_ASSERT(chunks.size() && end != begin);
375
376 const HeaderField &field = back();
377 const quint32 absIndex = end - 1;
378 const auto offset = absIndex % ChunkSize;
379 const auto chunk = chunks[absIndex / ChunkSize].get();
380
381 return SearchEntry(&field, chunk, offset, this);
382}
383
384bool FieldLookupTable::updateDynamicTableSize(quint32 size)
385{
386 if (!size) {
387 clearDynamicTable();
388 return true;
389 }
390
391 if (size > maxTableSize)
392 return false;
393
394 tableCapacity = size;
395 while (nDynamic && dataSize > tableCapacity)
396 evictEntry();
397
398 return true;
399}
400
401void FieldLookupTable::setMaxDynamicTableSize(quint32 size)
402{
403 // This is for an external user, for example, HTTP2 protocol
404 // layer that can receive SETTINGS frame from its peer.
405 // No validity checks here, up to this external user.
406 // We update max size and capacity (this can also result in
407 // items evicted or even dynamic table completely cleared).
408 maxTableSize = size;
409 updateDynamicTableSize(size);
410}
411
412// This data is from the HPACK's specs and it's quite conveniently sorted,
413// except ... 'accept' is in the wrong position, see how we handle it below.
414const std::vector<HeaderField> &FieldLookupTable::staticPart()
415{
416 static std::vector<HeaderField> table = {
417 {":authority", ""},
418 {":method", "GET"},
419 {":method", "POST"},
420 {":path", "/"},
421 {":path", "/index.html"},
422 {":scheme", "http"},
423 {":scheme", "https"},
424 {":status", "200"},
425 {":status", "204"},
426 {":status", "206"},
427 {":status", "304"},
428 {":status", "400"},
429 {":status", "404"},
430 {":status", "500"},
431 {"accept-charset", ""},
432 {"accept-encoding", "gzip, deflate"},
433 {"accept-language", ""},
434 {"accept-ranges", ""},
435 {"accept", ""},
436 {"access-control-allow-origin", ""},
437 {"age", ""},
438 {"allow", ""},
439 {"authorization", ""},
440 {"cache-control", ""},
441 {"content-disposition", ""},
442 {"content-encoding", ""},
443 {"content-language", ""},
444 {"content-length", ""},
445 {"content-location", ""},
446 {"content-range", ""},
447 {"content-type", ""},
448 {"cookie", ""},
449 {"date", ""},
450 {"etag", ""},
451 {"expect", ""},
452 {"expires", ""},
453 {"from", ""},
454 {"host", ""},
455 {"if-match", ""},
456 {"if-modified-since", ""},
457 {"if-none-match", ""},
458 {"if-range", ""},
459 {"if-unmodified-since", ""},
460 {"last-modified", ""},
461 {"link", ""},
462 {"location", ""},
463 {"max-forwards", ""},
464 {"proxy-authenticate", ""},
465 {"proxy-authorization", ""},
466 {"range", ""},
467 {"referer", ""},
468 {"refresh", ""},
469 {"retry-after", ""},
470 {"server", ""},
471 {"set-cookie", ""},
472 {"strict-transport-security", ""},
473 {"transfer-encoding", ""},
474 {"user-agent", ""},
475 {"vary", ""},
476 {"via", ""},
477 {"www-authenticate", ""}
478 };
479
480 return table;
481}
482
483std::vector<HeaderField>::const_iterator FieldLookupTable::findInStaticPart(const HeaderField &field, CompareMode mode)
484{
485 const auto &table = staticPart();
486 const auto acceptPos = table.begin() + 18;
487 if (field.name == "accept") {
488 if (mode == CompareMode::nameAndValue && field.value != "")
489 return table.end();
490 return acceptPos;
491 }
492
493 auto predicate = [mode](const HeaderField &lhs, const HeaderField &rhs) {
494 const int cmp = compare(lhs: lhs.name, rhs: rhs.name);
495 if (cmp)
496 return cmp < 0;
497 else if (mode == CompareMode::nameAndValue)
498 return compare(lhs: lhs.value, rhs: rhs.value) < 0;
499 return false;
500 };
501
502 const auto staticPos = std::lower_bound(first: table.begin(), last: acceptPos, val: field, comp: predicate);
503 if (staticPos != acceptPos)
504 return staticPos;
505
506 return std::lower_bound(first: acceptPos + 1, last: table.end(), val: field, comp: predicate);
507}
508
509}
510
511QT_END_NAMESPACE
512

Provided by KDAB

Privacy Policy
Learn to use CMake with our Intro Training
Find out more

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