Project import generated by Copybara.
PiperOrigin-RevId: 229942388
Change-Id: Ib5a23c152c95ed4294cece9f902227c21ce531ef
diff --git a/spdy/core/spdy_header_block.cc b/spdy/core/spdy_header_block.cc
new file mode 100644
index 0000000..dcf84b9
--- /dev/null
+++ b/spdy/core/spdy_header_block.cc
@@ -0,0 +1,401 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/spdy_header_block.h"
+
+#include <string.h>
+
+#include <algorithm>
+#include <utility>
+
+#include "base/logging.h"
+#include "base/macros.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_ptr_util.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_utils.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_unsafe_arena.h"
+
+namespace spdy {
+namespace {
+
+// By default, linked_hash_map's internal map allocates space for 100 map
+// buckets on construction, which is larger than necessary. Standard library
+// unordered map implementations use a list of prime numbers to set the bucket
+// count for a particular capacity. |kInitialMapBuckets| is chosen to reduce
+// memory usage for small header blocks, at the cost of having to rehash for
+// large header blocks.
+const size_t kInitialMapBuckets = 11;
+
+// SpdyHeaderBlock::Storage allocates blocks of this size by default.
+const size_t kDefaultStorageBlockSize = 2048;
+
+const char kCookieKey[] = "cookie";
+const char kNullSeparator = 0;
+
+SpdyStringPiece SeparatorForKey(SpdyStringPiece key) {
+ if (key == kCookieKey) {
+ static SpdyStringPiece cookie_separator = "; ";
+ return cookie_separator;
+ } else {
+ return SpdyStringPiece(&kNullSeparator, 1);
+ }
+}
+
+} // namespace
+
+// This class provides a backing store for SpdyStringPieces. It previously used
+// custom allocation logic, but now uses an UnsafeArena instead. It has the
+// property that SpdyStringPieces that refer to data in Storage are never
+// invalidated until the Storage is deleted or Clear() is called.
+//
+// Write operations always append to the last block. If there is not enough
+// space to perform the write, a new block is allocated, and any unused space
+// is wasted.
+class SpdyHeaderBlock::Storage {
+ public:
+ Storage() : arena_(kDefaultStorageBlockSize) {}
+ Storage(const Storage&) = delete;
+ Storage& operator=(const Storage&) = delete;
+
+ SpdyStringPiece Write(const SpdyStringPiece s) {
+ return SpdyStringPiece(arena_.Memdup(s.data(), s.size()), s.size());
+ }
+
+ // If |s| points to the most recent allocation from arena_, the arena will
+ // reclaim the memory. Otherwise, this method is a no-op.
+ void Rewind(const SpdyStringPiece s) {
+ arena_.Free(const_cast<char*>(s.data()), s.size());
+ }
+
+ void Clear() { arena_.Reset(); }
+
+ // Given a list of fragments and a separator, writes the fragments joined by
+ // the separator to a contiguous region of memory. Returns a SpdyStringPiece
+ // pointing to the region of memory.
+ SpdyStringPiece WriteFragments(const std::vector<SpdyStringPiece>& fragments,
+ SpdyStringPiece separator) {
+ if (fragments.empty()) {
+ return SpdyStringPiece();
+ }
+ size_t total_size = separator.size() * (fragments.size() - 1);
+ for (const auto fragment : fragments) {
+ total_size += fragment.size();
+ }
+ char* dst = arena_.Alloc(total_size);
+ size_t written = Join(dst, fragments, separator);
+ DCHECK_EQ(written, total_size);
+ return SpdyStringPiece(dst, total_size);
+ }
+
+ size_t bytes_allocated() const { return arena_.status().bytes_allocated(); }
+
+ // TODO(xunjieli): https://crbug.com/669108. Merge this with bytes_allocated()
+ size_t EstimateMemoryUsage() const {
+ return arena_.status().bytes_allocated();
+ }
+
+ private:
+ SpdyUnsafeArena arena_;
+};
+
+SpdyHeaderBlock::HeaderValue::HeaderValue(Storage* storage,
+ SpdyStringPiece key,
+ SpdyStringPiece initial_value)
+ : storage_(storage),
+ fragments_({initial_value}),
+ pair_({key, {}}),
+ size_(initial_value.size()),
+ separator_size_(SeparatorForKey(key).size()) {}
+
+SpdyHeaderBlock::HeaderValue::HeaderValue(HeaderValue&& other)
+ : storage_(other.storage_),
+ fragments_(std::move(other.fragments_)),
+ pair_(std::move(other.pair_)),
+ size_(other.size_),
+ separator_size_(other.separator_size_) {}
+
+SpdyHeaderBlock::HeaderValue& SpdyHeaderBlock::HeaderValue::operator=(
+ HeaderValue&& other) {
+ storage_ = other.storage_;
+ fragments_ = std::move(other.fragments_);
+ pair_ = std::move(other.pair_);
+ size_ = other.size_;
+ separator_size_ = other.separator_size_;
+ return *this;
+}
+
+SpdyHeaderBlock::HeaderValue::~HeaderValue() = default;
+
+SpdyStringPiece SpdyHeaderBlock::HeaderValue::ConsolidatedValue() const {
+ if (fragments_.empty()) {
+ return SpdyStringPiece();
+ }
+ if (fragments_.size() > 1) {
+ fragments_ = {
+ storage_->WriteFragments(fragments_, SeparatorForKey(pair_.first))};
+ }
+ return fragments_[0];
+}
+
+void SpdyHeaderBlock::HeaderValue::Append(SpdyStringPiece fragment) {
+ size_ += (fragment.size() + separator_size_);
+ fragments_.push_back(fragment);
+}
+
+const std::pair<SpdyStringPiece, SpdyStringPiece>&
+SpdyHeaderBlock::HeaderValue::as_pair() const {
+ pair_.second = ConsolidatedValue();
+ return pair_;
+}
+
+SpdyHeaderBlock::iterator::iterator(MapType::const_iterator it) : it_(it) {}
+
+SpdyHeaderBlock::iterator::iterator(const iterator& other) = default;
+
+SpdyHeaderBlock::iterator::~iterator() = default;
+
+SpdyHeaderBlock::ValueProxy::ValueProxy(
+ SpdyHeaderBlock::MapType* block,
+ SpdyHeaderBlock::Storage* storage,
+ SpdyHeaderBlock::MapType::iterator lookup_result,
+ const SpdyStringPiece key,
+ size_t* spdy_header_block_value_size)
+ : block_(block),
+ storage_(storage),
+ lookup_result_(lookup_result),
+ key_(key),
+ spdy_header_block_value_size_(spdy_header_block_value_size),
+ valid_(true) {}
+
+SpdyHeaderBlock::ValueProxy::ValueProxy(ValueProxy&& other)
+ : block_(other.block_),
+ storage_(other.storage_),
+ lookup_result_(other.lookup_result_),
+ key_(other.key_),
+ spdy_header_block_value_size_(other.spdy_header_block_value_size_),
+ valid_(true) {
+ other.valid_ = false;
+}
+
+SpdyHeaderBlock::ValueProxy& SpdyHeaderBlock::ValueProxy::operator=(
+ SpdyHeaderBlock::ValueProxy&& other) {
+ block_ = other.block_;
+ storage_ = other.storage_;
+ lookup_result_ = other.lookup_result_;
+ key_ = other.key_;
+ valid_ = true;
+ other.valid_ = false;
+ spdy_header_block_value_size_ = other.spdy_header_block_value_size_;
+ return *this;
+}
+
+SpdyHeaderBlock::ValueProxy::~ValueProxy() {
+ // If the ValueProxy is destroyed while lookup_result_ == block_->end(),
+ // the assignment operator was never used, and the block's Storage can
+ // reclaim the memory used by the key. This makes lookup-only access to
+ // SpdyHeaderBlock through operator[] memory-neutral.
+ if (valid_ && lookup_result_ == block_->end()) {
+ storage_->Rewind(key_);
+ }
+}
+
+SpdyHeaderBlock::ValueProxy& SpdyHeaderBlock::ValueProxy::operator=(
+ const SpdyStringPiece value) {
+ *spdy_header_block_value_size_ += value.size();
+ if (lookup_result_ == block_->end()) {
+ DVLOG(1) << "Inserting: (" << key_ << ", " << value << ")";
+ lookup_result_ =
+ block_
+ ->emplace(std::make_pair(
+ key_, HeaderValue(storage_, key_, storage_->Write(value))))
+ .first;
+ } else {
+ DVLOG(1) << "Updating key: " << key_ << " with value: " << value;
+ *spdy_header_block_value_size_ -= lookup_result_->second.SizeEstimate();
+ lookup_result_->second =
+ HeaderValue(storage_, key_, storage_->Write(value));
+ }
+ return *this;
+}
+
+SpdyString SpdyHeaderBlock::ValueProxy::as_string() const {
+ if (lookup_result_ == block_->end()) {
+ return "";
+ } else {
+ return SpdyString(lookup_result_->second.value());
+ }
+}
+
+SpdyHeaderBlock::SpdyHeaderBlock() : block_(kInitialMapBuckets) {}
+
+SpdyHeaderBlock::SpdyHeaderBlock(SpdyHeaderBlock&& other)
+ : block_(kInitialMapBuckets) {
+ block_.swap(other.block_);
+ storage_.swap(other.storage_);
+ key_size_ = other.key_size_;
+ value_size_ = other.value_size_;
+}
+
+SpdyHeaderBlock::~SpdyHeaderBlock() = default;
+
+SpdyHeaderBlock& SpdyHeaderBlock::operator=(SpdyHeaderBlock&& other) {
+ block_.swap(other.block_);
+ storage_.swap(other.storage_);
+ key_size_ = other.key_size_;
+ value_size_ = other.value_size_;
+ return *this;
+}
+
+SpdyHeaderBlock SpdyHeaderBlock::Clone() const {
+ SpdyHeaderBlock copy;
+ for (const auto& p : *this) {
+ copy.AppendHeader(p.first, p.second);
+ }
+ return copy;
+}
+
+bool SpdyHeaderBlock::operator==(const SpdyHeaderBlock& other) const {
+ return size() == other.size() && std::equal(begin(), end(), other.begin());
+}
+
+bool SpdyHeaderBlock::operator!=(const SpdyHeaderBlock& other) const {
+ return !(operator==(other));
+}
+
+SpdyString SpdyHeaderBlock::DebugString() const {
+ if (empty()) {
+ return "{}";
+ }
+
+ SpdyString output = "\n{\n";
+ for (auto it = begin(); it != end(); ++it) {
+ SpdyStrAppend(&output, " ", it->first, " ", it->second, "\n");
+ }
+ SpdyStrAppend(&output, "}\n");
+ return output;
+}
+
+void SpdyHeaderBlock::erase(SpdyStringPiece key) {
+ auto iter = block_.find(key);
+ if (iter != block_.end()) {
+ DVLOG(1) << "Erasing header with name: " << key;
+ key_size_ -= key.size();
+ value_size_ -= iter->second.SizeEstimate();
+ block_.erase(iter);
+ }
+}
+
+void SpdyHeaderBlock::clear() {
+ key_size_ = 0;
+ value_size_ = 0;
+ block_.clear();
+ storage_.reset();
+}
+
+void SpdyHeaderBlock::insert(const SpdyHeaderBlock::value_type& value) {
+ // TODO(birenroy): Write new value in place of old value, if it fits.
+ value_size_ += value.second.size();
+
+ auto iter = block_.find(value.first);
+ if (iter == block_.end()) {
+ DVLOG(1) << "Inserting: (" << value.first << ", " << value.second << ")";
+ AppendHeader(value.first, value.second);
+ } else {
+ DVLOG(1) << "Updating key: " << iter->first
+ << " with value: " << value.second;
+ value_size_ -= iter->second.SizeEstimate();
+ auto* storage = GetStorage();
+ iter->second =
+ HeaderValue(storage, iter->first, storage->Write(value.second));
+ }
+}
+
+SpdyHeaderBlock::ValueProxy SpdyHeaderBlock::operator[](
+ const SpdyStringPiece key) {
+ DVLOG(2) << "Operator[] saw key: " << key;
+ SpdyStringPiece out_key;
+ auto iter = block_.find(key);
+ if (iter == block_.end()) {
+ // We write the key first, to assure that the ValueProxy has a
+ // reference to a valid SpdyStringPiece in its operator=.
+ out_key = WriteKey(key);
+ DVLOG(2) << "Key written as: " << std::hex
+ << static_cast<const void*>(key.data()) << ", " << std::dec
+ << key.size();
+ } else {
+ out_key = iter->first;
+ }
+ return ValueProxy(&block_, GetStorage(), iter, out_key, &value_size_);
+}
+
+void SpdyHeaderBlock::AppendValueOrAddHeader(const SpdyStringPiece key,
+ const SpdyStringPiece value) {
+ value_size_ += value.size();
+
+ auto iter = block_.find(key);
+ if (iter == block_.end()) {
+ DVLOG(1) << "Inserting: (" << key << ", " << value << ")";
+
+ AppendHeader(key, value);
+ return;
+ }
+ DVLOG(1) << "Updating key: " << iter->first << "; appending value: " << value;
+ value_size_ += SeparatorForKey(key).size();
+ iter->second.Append(GetStorage()->Write(value));
+}
+
+size_t SpdyHeaderBlock::EstimateMemoryUsage() const {
+ // TODO(xunjieli): https://crbug.com/669108. Also include |block_| when EMU()
+ // supports linked_hash_map.
+ return SpdyEstimateMemoryUsage(storage_);
+}
+
+void SpdyHeaderBlock::AppendHeader(const SpdyStringPiece key,
+ const SpdyStringPiece value) {
+ auto backed_key = WriteKey(key);
+ auto* storage = GetStorage();
+ block_.emplace(std::make_pair(
+ backed_key, HeaderValue(storage, backed_key, storage->Write(value))));
+}
+
+SpdyHeaderBlock::Storage* SpdyHeaderBlock::GetStorage() {
+ if (storage_ == nullptr) {
+ storage_ = SpdyMakeUnique<Storage>();
+ }
+ return storage_.get();
+}
+
+SpdyStringPiece SpdyHeaderBlock::WriteKey(const SpdyStringPiece key) {
+ key_size_ += key.size();
+ return GetStorage()->Write(key);
+}
+
+size_t SpdyHeaderBlock::bytes_allocated() const {
+ if (storage_ == nullptr) {
+ return 0;
+ } else {
+ return storage_->bytes_allocated();
+ }
+}
+
+size_t Join(char* dst,
+ const std::vector<SpdyStringPiece>& fragments,
+ SpdyStringPiece separator) {
+ if (fragments.empty()) {
+ return 0;
+ }
+ auto* original_dst = dst;
+ auto it = fragments.begin();
+ memcpy(dst, it->data(), it->size());
+ dst += it->size();
+ for (++it; it != fragments.end(); ++it) {
+ memcpy(dst, separator.data(), separator.size());
+ dst += separator.size();
+ memcpy(dst, it->data(), it->size());
+ dst += it->size();
+ }
+ return dst - original_dst;
+}
+
+} // namespace spdy
