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

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