hpacktable.cpp

Go to the documentation of this file.

// Copyright (C) 2016 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
 
#include "hpacktable_p.h"
 
#include <QtCore/qdebug.h>
 
#include <algorithm>
#include <cstddef>
#include <cstring>
#include <limits>
 
 
QT_BEGIN_NAMESPACE
 
namespace HPack
{
 
HeaderSize entry_size(QByteArrayView name, QByteArrayView value)
{
    // 32 comes from HPACK:
    // "4.1 Calculating Table Size
    // Note: The additional 32 octets account for an estimated overhead associated
    // with an entry. For example, an entry structure using two 64-bit pointers
    // to reference the name and the value of the entry and two 64-bit integers
    // for counting the number of references to the name and value would have
    // 32 octets of overhead."
 
    const unsigned sum = unsigned(name.size() + value.size());
    if (std::numeric_limits<unsigned>::max() - 32 < sum)
        return HeaderSize();
    return HeaderSize(true, quint32(sum + 32));
}
 
namespace
{
 
int compare(const QByteArray &lhs, const QByteArray &rhs)
{
    if (const int minLen = std::min(lhs.size(), rhs.size())) {
        // We use memcmp, since strings in headers are allowed
        // to contain '\0'.
        const int cmp = std::memcmp(lhs.constData(), rhs.constData(), std::size_t(minLen));
        if (cmp)
            return cmp;
    }
 
    return lhs.size() - rhs.size();
}
 
} // unnamed namespace
 
FieldLookupTable::SearchEntry::SearchEntry()
    : field(),
      chunk(),
      offset(),
      table()
{
}
 
FieldLookupTable::SearchEntry::SearchEntry(const HeaderField *f,
                                           const Chunk *c,
                                           quint32 o,
                                           const FieldLookupTable *t)
    : field(f),
      chunk(c),
      offset(o),
      table(t)
{
    Q_ASSERT(field);
}
 
bool FieldLookupTable::SearchEntry::operator < (const SearchEntry &rhs)const
{
    Q_ASSERT(field);
    Q_ASSERT(rhs.field);
 
    int cmp = compare(field->name, rhs.field->name);
    if (cmp)
        return cmp < 0;
 
    cmp = compare(field->value, rhs.field->value);
    if (cmp)
        return cmp < 0;
 
    if (!chunk) // 'this' is not in the searchIndex.
        return rhs.chunk;
 
    if (!rhs.chunk) // not in the searchIndex.
        return false;
 
    Q_ASSERT(table);
    Q_ASSERT(rhs.table == table);
 
    const quint32 leftChunkIndex = table->indexOfChunk(chunk);
    const quint32 rightChunkIndex = rhs.table->indexOfChunk(rhs.chunk);
 
    // Later added - smaller is chunk index (since we push_front).
    if (leftChunkIndex != rightChunkIndex)
        return leftChunkIndex > rightChunkIndex;
 
    // Later added - smaller is offset.
    return offset > rhs.offset;
}
 
FieldLookupTable::FieldLookupTable(quint32 maxSize, bool use)
    : maxTableSize(maxSize),
      tableCapacity(maxSize),
      useIndex(use),
      nDynamic(),
      begin(),
      end(),
      dataSize()
{
}
 
 
bool FieldLookupTable::prependField(const QByteArray &name, const QByteArray &value)
{
    const auto entrySize = entry_size(name, value);
    if (!entrySize.first)
        return false;
 
    if (entrySize.second > tableCapacity) {
        clearDynamicTable();
        return true;
    }
 
    while (nDynamic && tableCapacity - dataSize < entrySize.second)
        evictEntry();
 
    if (!begin) {
        // Either no more space or empty table ...
        chunks.push_front(ChunkPtr(new Chunk(ChunkSize)));
        end += ChunkSize;
        begin = ChunkSize;
    }
 
    --begin;
 
    dataSize += entrySize.second;
    ++nDynamic;
 
    auto &newField = front();
    newField.name = name;
    newField.value = value;
 
    if (useIndex) {
        const auto result = searchIndex.insert(frontKey());
        Q_UNUSED(result);
        Q_ASSERT(result.second);
    }
 
    return true;
}
 
void FieldLookupTable::evictEntry()
{
    if (!nDynamic)
        return;
 
    Q_ASSERT(end != begin);
 
    if (useIndex) {
        const auto res = searchIndex.erase(backKey());
        Q_UNUSED(res);
        Q_ASSERT(res == 1);
    }
 
    const HeaderField &field = back();
    const auto entrySize = entry_size(field);
    Q_ASSERT(entrySize.first);
    Q_ASSERT(dataSize >= entrySize.second);
    dataSize -= entrySize.second;
 
    --nDynamic;
    --end;
 
    if (end == begin) {
        Q_ASSERT(chunks.size() == 1);
        end = ChunkSize;
        begin = end;
    } else if (!(end % ChunkSize)) {
        chunks.pop_back();
    }
}
 
quint32 FieldLookupTable::numberOfEntries() const
{
    return quint32(staticPart().size()) + nDynamic;
}
 
quint32 FieldLookupTable::numberOfStaticEntries() const
{
    return quint32(staticPart().size());
}
 
quint32 FieldLookupTable::numberOfDynamicEntries() const
{
    return nDynamic;
}
 
quint32 FieldLookupTable::dynamicDataSize() const
{
    return dataSize;
}
 
void FieldLookupTable::clearDynamicTable()
{
    searchIndex.clear();
    chunks.clear();
    begin = 0;
    end = 0;
    nDynamic = 0;
    dataSize = 0;
}
 
bool FieldLookupTable::indexIsValid(quint32 index) const
{
    return index && index <= staticPart().size() + nDynamic;
}
 
quint32 FieldLookupTable::indexOf(const QByteArray &name, const QByteArray &value)const
{
    // Start from the static part first:
    const auto &table = staticPart();
    const HeaderField field(name, value);
    const auto staticPos = findInStaticPart(field, CompareMode::nameAndValue);
    if (staticPos != table.end()) {
        if (staticPos->name == name && staticPos->value == value)
            return quint32(staticPos - table.begin() + 1);
    }
 
    // Now we have to lookup in our dynamic part ...
    if (!useIndex) {
        qCritical("lookup in dynamic table requires search index enabled");
        return 0;
    }
 
    const SearchEntry key(&field, nullptr, 0, this);
    const auto pos = searchIndex.lower_bound(key);
    if (pos != searchIndex.end()) {
        const HeaderField &found = *pos->field;
        if (found.name == name && found.value == value)
            return keyToIndex(*pos);
    }
 
    return 0;
}
 
quint32 FieldLookupTable::indexOf(const QByteArray &name) const
{
    // Start from the static part first:
    const auto &table = staticPart();
    const HeaderField field(name, QByteArray());
    const auto staticPos = findInStaticPart(field, CompareMode::nameOnly);
    if (staticPos != table.end()) {
        if (staticPos->name == name)
            return quint32(staticPos - table.begin() + 1);
    }
 
    // Now we have to lookup in our dynamic part ...
    if (!useIndex) {
        qCritical("lookup in dynamic table requires search index enabled");
        return 0;
    }
 
    const SearchEntry key(&field, nullptr, 0, this);
    const auto pos = searchIndex.lower_bound(key);
    if (pos != searchIndex.end()) {
        const HeaderField &found = *pos->field;
        if (found.name == name)
            return keyToIndex(*pos);
    }
 
    return 0;
}
 
bool FieldLookupTable::field(quint32 index, QByteArray *name, QByteArray *value) const
{
    Q_ASSERT(name);
    Q_ASSERT(value);
 
    if (!indexIsValid(index))
        return false;
 
    const auto &table = staticPart();
    if (index - 1 < table.size()) {
        *name = table[index - 1].name;
        *value = table[index - 1].value;
        return true;
    }
 
    index = index - 1 - quint32(table.size()) + begin;
    const auto chunkIndex = index / ChunkSize;
    Q_ASSERT(chunkIndex < chunks.size());
    const auto offset = index % ChunkSize;
    const HeaderField &found = (*chunks[chunkIndex])[offset];
    *name = found.name;
    *value = found.value;
 
    return true;
}
 
bool FieldLookupTable::fieldName(quint32 index, QByteArray *dst) const
{
    Q_ASSERT(dst);
    return field(index, dst, &dummyDst);
}
 
bool FieldLookupTable::fieldValue(quint32 index, QByteArray *dst) const
{
    Q_ASSERT(dst);
    return field(index, &dummyDst, dst);
}
 
const HeaderField &FieldLookupTable::front() const
{
    Q_ASSERT(nDynamic && begin != end && chunks.size());
    return (*chunks[0])[begin];
}
 
HeaderField &FieldLookupTable::front()
{
    Q_ASSERT(nDynamic && begin != end && chunks.size());
    return (*chunks[0])[begin];
}
 
const HeaderField &FieldLookupTable::back() const
{
    Q_ASSERT(nDynamic && end && end != begin);
 
    const quint32 absIndex = end - 1;
    const quint32 chunkIndex = absIndex / ChunkSize;
    Q_ASSERT(chunkIndex < chunks.size());
    const quint32 offset = absIndex % ChunkSize;
    return (*chunks[chunkIndex])[offset];
}
 
quint32 FieldLookupTable::indexOfChunk(const Chunk *chunk) const
{
    Q_ASSERT(chunk);
 
    for (size_type i = 0; i < chunks.size(); ++i) {
        if (chunks[i].get() == chunk)
            return quint32(i);
    }
 
    Q_UNREACHABLE_RETURN(0);
}
 
quint32 FieldLookupTable::keyToIndex(const SearchEntry &key) const
{
    Q_ASSERT(key.chunk);
 
    const auto chunkIndex = indexOfChunk(key.chunk);
    const auto offset = key.offset;
    Q_ASSERT(offset < ChunkSize);
    Q_ASSERT(chunkIndex || offset >= begin);
 
    return quint32(offset + chunkIndex * ChunkSize - begin + 1 + staticPart().size());
}
 
FieldLookupTable::SearchEntry FieldLookupTable::frontKey() const
{
    Q_ASSERT(chunks.size() && end != begin);
    return SearchEntry(&front(), chunks.front().get(), begin, this);
}
 
FieldLookupTable::SearchEntry FieldLookupTable::backKey() const
{
    Q_ASSERT(chunks.size() && end != begin);
 
    const HeaderField &field = back();
    const quint32 absIndex = end - 1;
    const auto offset = absIndex % ChunkSize;
    const auto chunk = chunks[absIndex / ChunkSize].get();
 
    return SearchEntry(&field, chunk, offset, this);
}
 
bool FieldLookupTable::updateDynamicTableSize(quint32 size)
{
    if (!size) {
        clearDynamicTable();
        return true;
    }
 
    if (size > maxTableSize)
        return false;
 
    tableCapacity = size;
    while (nDynamic && dataSize > tableCapacity)
        evictEntry();
 
    return true;
}
 
void FieldLookupTable::setMaxDynamicTableSize(quint32 size)
{
    // This is for an external user, for example, HTTP2 protocol
    // layer that can receive SETTINGS frame from its peer.
    // No validity checks here, up to this external user.
    // We update max size and capacity (this can also result in
    // items evicted or even dynamic table completely cleared).
    maxTableSize = size;
    updateDynamicTableSize(size);
}
 
// This data is from the HPACK's specs and it's quite conveniently sorted,
// except ... 'accept' is in the wrong position, see how we handle it below.
const std::vector<HeaderField> &FieldLookupTable::staticPart()
{
    static std::vector<HeaderField> table = {
    {":authority", ""},
    {":method", "GET"},
    {":method", "POST"},
    {":path", "/"},
    {":path", "/index.html"},
    {":scheme", "http"},
    {":scheme", "https"},
    {":status", "200"},
    {":status", "204"},
    {":status", "206"},
    {":status", "304"},
    {":status", "400"},
    {":status", "404"},
    {":status", "500"},
    {"accept-charset", ""},
    {"accept-encoding", "gzip, deflate"},
    {"accept-language", ""},
    {"accept-ranges", ""},
    {"accept", ""},
    {"access-control-allow-origin", ""},
    {"age", ""},
    {"allow", ""},
    {"authorization", ""},
    {"cache-control", ""},
    {"content-disposition", ""},
    {"content-encoding", ""},
    {"content-language", ""},
    {"content-length", ""},
    {"content-location", ""},
    {"content-range", ""},
    {"content-type", ""},
    {"cookie", ""},
    {"date", ""},
    {"etag", ""},
    {"expect", ""},
    {"expires", ""},
    {"from", ""},
    {"host", ""},
    {"if-match", ""},
    {"if-modified-since", ""},
    {"if-none-match", ""},
    {"if-range", ""},
    {"if-unmodified-since", ""},
    {"last-modified", ""},
    {"link", ""},
    {"location", ""},
    {"max-forwards", ""},
    {"proxy-authenticate", ""},
    {"proxy-authorization", ""},
    {"range", ""},
    {"referer", ""},
    {"refresh", ""},
    {"retry-after", ""},
    {"server", ""},
    {"set-cookie", ""},
    {"strict-transport-security", ""},
    {"transfer-encoding", ""},
    {"user-agent", ""},
    {"vary", ""},
    {"via", ""},
    {"www-authenticate", ""}
    };
 
    return table;
}
 
std::vector<HeaderField>::const_iterator FieldLookupTable::findInStaticPart(const HeaderField &field, CompareMode mode)
{
    const auto &table = staticPart();
    const auto acceptPos = table.begin() + 18;
    if (field.name == "accept") {
        if (mode == CompareMode::nameAndValue && field.value != "")
            return table.end();
        return acceptPos;
    }
 
    auto predicate = [mode](const HeaderField &lhs, const HeaderField &rhs) {
        const int cmp = compare(lhs.name, rhs.name);
        if (cmp)
            return cmp < 0;
        else if (mode == CompareMode::nameAndValue)
            return compare(lhs.value, rhs.value) < 0;
        return false;
    };
 
    const auto staticPos = std::lower_bound(table.begin(), acceptPos, field, predicate);
    if (staticPos != acceptPos)
        return staticPos;
 
    return std::lower_bound(acceptPos + 1, table.end(), field, predicate);
}
 
}
 
QT_END_NAMESPACE