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