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 | |
14 | QT_BEGIN_NAMESPACE |
15 | |
16 | namespace HPack |
17 | { |
18 | |
19 | HeaderSize 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 | |
37 | namespace |
38 | { |
39 | |
40 | int 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 | |
55 | FieldLookupTable::SearchEntry::SearchEntry() |
56 | : field(), |
57 | chunk(), |
58 | offset(), |
59 | table() |
60 | { |
61 | } |
62 | |
63 | FieldLookupTable::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 | |
75 | bool 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 | |
108 | FieldLookupTable::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 | |
120 | bool 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 | |
159 | void 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 | |
190 | quint32 FieldLookupTable::numberOfEntries() const |
191 | { |
192 | return quint32(staticPart().size()) + nDynamic; |
193 | } |
194 | |
195 | quint32 FieldLookupTable::numberOfStaticEntries() const |
196 | { |
197 | return quint32(staticPart().size()); |
198 | } |
199 | |
200 | quint32 FieldLookupTable::numberOfDynamicEntries() const |
201 | { |
202 | return nDynamic; |
203 | } |
204 | |
205 | quint32 FieldLookupTable::dynamicDataSize() const |
206 | { |
207 | return dataSize; |
208 | } |
209 | |
210 | void FieldLookupTable::clearDynamicTable() |
211 | { |
212 | searchIndex.clear(); |
213 | chunks.clear(); |
214 | begin = 0; |
215 | end = 0; |
216 | nDynamic = 0; |
217 | dataSize = 0; |
218 | } |
219 | |
220 | bool FieldLookupTable::indexIsValid(quint32 index) const |
221 | { |
222 | return index && index <= staticPart().size() + nDynamic; |
223 | } |
224 | |
225 | quint32 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 | |
253 | quint32 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 | |
281 | bool 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 | |
307 | bool FieldLookupTable::fieldName(quint32 index, QByteArray *dst) const |
308 | { |
309 | Q_ASSERT(dst); |
310 | return field(index, name: dst, value: &dummyDst); |
311 | } |
312 | |
313 | bool FieldLookupTable::fieldValue(quint32 index, QByteArray *dst) const |
314 | { |
315 | Q_ASSERT(dst); |
316 | return field(index, name: &dummyDst, value: dst); |
317 | } |
318 | |
319 | const HeaderField &FieldLookupTable::front() const |
320 | { |
321 | Q_ASSERT(nDynamic && begin != end && chunks.size()); |
322 | return (*chunks[0])[begin]; |
323 | } |
324 | |
325 | HeaderField &FieldLookupTable::front() |
326 | { |
327 | Q_ASSERT(nDynamic && begin != end && chunks.size()); |
328 | return (*chunks[0])[begin]; |
329 | } |
330 | |
331 | const 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 | |
342 | quint32 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 | |
354 | quint32 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 | |
366 | FieldLookupTable::SearchEntry FieldLookupTable::frontKey() const |
367 | { |
368 | Q_ASSERT(chunks.size() && end != begin); |
369 | return SearchEntry(&front(), chunks.front().get(), begin, this); |
370 | } |
371 | |
372 | FieldLookupTable::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 | |
384 | bool 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 | |
401 | void 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. |
414 | const 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 | |
483 | std::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 | |
511 | QT_END_NAMESPACE |
512 |
Definitions
- entry_size
- compare
- SearchEntry
- SearchEntry
- operator <
- FieldLookupTable
- prependField
- evictEntry
- numberOfEntries
- numberOfStaticEntries
- numberOfDynamicEntries
- dynamicDataSize
- clearDynamicTable
- indexIsValid
- indexOf
- indexOf
- field
- fieldName
- fieldValue
- front
- front
- back
- indexOfChunk
- keyToIndex
- frontKey
- backKey
- updateDynamicTableSize
- setMaxDynamicTableSize
- staticPart
Start learning QML with our Intro Training
Find out more