path: root/src/network/access/http2/hpacktable.cpp

/****************************************************************************
**
** Copyright (C) 2016 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtNetwork module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 3 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL3 included in the
** packaging of this file. Please review the following information to
** ensure the GNU Lesser General Public License version 3 requirements
** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 2.0 or (at your option) the GNU General
** Public license version 3 or any later version approved by the KDE Free
** Qt Foundation. The licenses are as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-2.0.html and
** https://www.gnu.org/licenses/gpl-3.0.html.
**
** $QT_END_LICENSE$
**
****************************************************************************/

#include "hpacktable_p.h"

#include <QtCore/qdebug.h>

#include <algorithm>
#include <cstddef>
#include <cstring>
#include <limits>


QT_BEGIN_NAMESPACE

namespace HPack
{

HeaderSize entry_size(const QByteArray &name, const QByteArray &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