1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef QUICHE_COMMON_HTTP_HTTP_HEADER_BLOCK_H_ 6 #define QUICHE_COMMON_HTTP_HTTP_HEADER_BLOCK_H_ 7 8 #include <stddef.h> 9 10 #include <functional> 11 #include <list> 12 #include <string> 13 #include <utility> 14 15 #include "absl/base/attributes.h" 16 #include "absl/container/inlined_vector.h" 17 #include "absl/strings/string_view.h" 18 #include "quiche/common/http/http_header_storage.h" 19 #include "quiche/common/platform/api/quiche_export.h" 20 #include "quiche/common/platform/api/quiche_logging.h" 21 #include "quiche/common/quiche_linked_hash_map.h" 22 #include "quiche/common/quiche_text_utils.h" 23 24 namespace quiche { 25 26 namespace test { 27 class HttpHeaderBlockPeer; 28 class ValueProxyPeer; 29 } // namespace test 30 31 #ifndef SPDY_HEADER_DEBUG 32 #if !defined(NDEBUG) || defined(ADDRESS_SANITIZER) 33 #define SPDY_HEADER_DEBUG 1 34 #else // !defined(NDEBUG) || defined(ADDRESS_SANITIZER) 35 #define SPDY_HEADER_DEBUG 0 36 #endif // !defined(NDEBUG) || defined(ADDRESS_SANITIZER) 37 #endif // SPDY_HEADER_DEBUG 38 39 // This class provides a key-value map that can be used to store SPDY header 40 // names and values. This data structure preserves insertion order. 41 // 42 // Under the hood, this data structure uses large, contiguous blocks of memory 43 // to store names and values. Lookups may be performed with absl::string_view 44 // keys, and values are returned as absl::string_views (via ValueProxy, below). 45 // Value absl::string_views are valid as long as the HttpHeaderBlock exists; 46 // allocated memory is never freed until HttpHeaderBlock's destruction. 47 // 48 // This implementation does not make much of an effort to minimize wasted space. 49 // It's expected that keys are rarely deleted from a HttpHeaderBlock. 50 class QUICHE_EXPORT HttpHeaderBlock { 51 private: 52 // Stores a list of value fragments that can be joined later with a 53 // key-dependent separator. 54 class QUICHE_EXPORT HeaderValue { 55 public: 56 HeaderValue(HttpHeaderStorage* storage, absl::string_view key, 57 absl::string_view initial_value); 58 59 // Moves are allowed. 60 HeaderValue(HeaderValue&& other); 61 HeaderValue& operator=(HeaderValue&& other); 62 63 void set_storage(HttpHeaderStorage* storage); 64 65 // Copies are not. 66 HeaderValue(const HeaderValue& other) = delete; 67 HeaderValue& operator=(const HeaderValue& other) = delete; 68 69 ~HeaderValue(); 70 71 // Consumes at most |fragment.size()| bytes of memory. 72 void Append(absl::string_view fragment); 73 value()74 absl::string_view value() const { return as_pair().second; } 75 const std::pair<absl::string_view, absl::string_view>& as_pair() const; 76 77 // Size estimate including separators. Used when keys are erased from 78 // HttpHeaderBlock. SizeEstimate()79 size_t SizeEstimate() const { return size_; } 80 81 private: 82 // May allocate a large contiguous region of memory to hold the concatenated 83 // fragments and separators. 84 absl::string_view ConsolidatedValue() const; 85 86 mutable HttpHeaderStorage* storage_; 87 mutable Fragments fragments_; 88 // The first element is the key; the second is the consolidated value. 89 mutable std::pair<absl::string_view, absl::string_view> pair_; 90 size_t size_ = 0; 91 size_t separator_size_ = 0; 92 }; 93 94 typedef quiche::QuicheLinkedHashMap<absl::string_view, HeaderValue, 95 quiche::StringPieceCaseHash, 96 quiche::StringPieceCaseEqual> 97 MapType; 98 99 public: 100 typedef std::pair<absl::string_view, absl::string_view> value_type; 101 102 enum class InsertResult { 103 kInserted, 104 kReplaced, 105 }; 106 107 // Provides iteration over a sequence of std::pair<absl::string_view, 108 // absl::string_view>, even though the underlying MapType::value_type is 109 // different. Dereferencing the iterator will result in memory allocation for 110 // multi-value headers. 111 class QUICHE_EXPORT iterator { 112 public: 113 // The following type definitions fulfill the requirements for iterator 114 // implementations. 115 typedef std::pair<absl::string_view, absl::string_view> value_type; 116 typedef value_type& reference; 117 typedef value_type* pointer; 118 typedef std::forward_iterator_tag iterator_category; 119 typedef MapType::iterator::difference_type difference_type; 120 121 // In practice, this iterator only offers access to const value_type. 122 typedef const value_type& const_reference; 123 typedef const value_type* const_pointer; 124 125 explicit iterator(MapType::const_iterator it); 126 iterator(const iterator& other); 127 ~iterator(); 128 129 // This will result in memory allocation if the value consists of multiple 130 // fragments. 131 const_reference operator*() const { 132 #if SPDY_HEADER_DEBUG 133 QUICHE_CHECK(!dereference_forbidden_); 134 #endif // SPDY_HEADER_DEBUG 135 return it_->second.as_pair(); 136 } 137 138 const_pointer operator->() const { return &(this->operator*()); } 139 bool operator==(const iterator& it) const { return it_ == it.it_; } 140 bool operator!=(const iterator& it) const { return !(*this == it); } 141 142 iterator& operator++() { 143 it_++; 144 return *this; 145 } 146 147 iterator operator++(int) { 148 auto ret = *this; 149 this->operator++(); 150 return ret; 151 } 152 153 #if SPDY_HEADER_DEBUG forbid_dereference()154 void forbid_dereference() { dereference_forbidden_ = true; } 155 #endif // SPDY_HEADER_DEBUG 156 157 private: 158 MapType::const_iterator it_; 159 #if SPDY_HEADER_DEBUG 160 bool dereference_forbidden_ = false; 161 #endif // SPDY_HEADER_DEBUG 162 }; 163 typedef iterator const_iterator; 164 165 HttpHeaderBlock(); 166 HttpHeaderBlock(const HttpHeaderBlock& other) = delete; 167 HttpHeaderBlock(HttpHeaderBlock&& other); 168 ~HttpHeaderBlock(); 169 170 HttpHeaderBlock& operator=(const HttpHeaderBlock& other) = delete; 171 HttpHeaderBlock& operator=(HttpHeaderBlock&& other); 172 HttpHeaderBlock Clone() const; 173 174 bool operator==(const HttpHeaderBlock& other) const; 175 bool operator!=(const HttpHeaderBlock& other) const; 176 177 // Provides a human readable multi-line representation of the stored header 178 // keys and values. 179 std::string DebugString() const; 180 begin()181 iterator begin() { return wrap_iterator(map_.begin()); } end()182 iterator end() { return wrap_iterator(map_.end()); } begin()183 const_iterator begin() const { return wrap_const_iterator(map_.begin()); } end()184 const_iterator end() const { return wrap_const_iterator(map_.end()); } empty()185 bool empty() const { return map_.empty(); } size()186 size_t size() const { return map_.size(); } find(absl::string_view key)187 iterator find(absl::string_view key) { return wrap_iterator(map_.find(key)); } find(absl::string_view key)188 const_iterator find(absl::string_view key) const { 189 return wrap_const_iterator(map_.find(key)); 190 } contains(absl::string_view key)191 bool contains(absl::string_view key) const { return find(key) != end(); } 192 void erase(absl::string_view key); 193 194 // Clears both our MapType member and the memory used to hold headers. 195 void clear(); 196 197 // The next few methods copy data into our backing storage. 198 199 // If key already exists in the block, replaces the value of that key and 200 // returns `kReplaced`. Else adds a new header to the end of the block and 201 // returns `kInserted`. 202 InsertResult insert(const value_type& value); 203 204 // If a header with the key is already present, then append the value to the 205 // existing header value, NUL ("\0") separated unless the key is cookie, in 206 // which case the separator is "; ". 207 // If there is no such key, a new header with the key and value is added. 208 void AppendValueOrAddHeader(const absl::string_view key, 209 const absl::string_view value); 210 211 // This object provides automatic conversions that allow HttpHeaderBlock to 212 // be nearly a drop-in replacement for a linked hash map with string keys and 213 // values. It reads data from or writes data to a HttpHeaderStorage. 214 class QUICHE_EXPORT ValueProxy { 215 public: 216 ~ValueProxy(); 217 218 // Moves are allowed. 219 ValueProxy(ValueProxy&& other); 220 ValueProxy& operator=(ValueProxy&& other); 221 222 // Copies are not. 223 ValueProxy(const ValueProxy& other) = delete; 224 ValueProxy& operator=(const ValueProxy& other) = delete; 225 226 // Assignment modifies the underlying HttpHeaderBlock. 227 ValueProxy& operator=(absl::string_view value); 228 229 // Provides easy comparison against absl::string_view. 230 bool operator==(absl::string_view value) const; 231 232 std::string as_string() const; 233 234 private: 235 friend class HttpHeaderBlock; 236 friend class test::ValueProxyPeer; 237 238 ValueProxy(HttpHeaderBlock* block, 239 HttpHeaderBlock::MapType::iterator lookup_result, 240 const absl::string_view key, 241 size_t* spdy_header_block_value_size); 242 243 HttpHeaderBlock* block_; 244 HttpHeaderBlock::MapType::iterator lookup_result_; 245 absl::string_view key_; 246 size_t* spdy_header_block_value_size_; 247 bool valid_; 248 }; 249 250 // Allows either lookup or mutation of the value associated with a key. 251 ABSL_MUST_USE_RESULT ValueProxy operator[](const absl::string_view key); 252 TotalBytesUsed()253 size_t TotalBytesUsed() const { return key_size_ + value_size_; } 254 255 private: 256 friend class test::HttpHeaderBlockPeer; 257 wrap_iterator(MapType::const_iterator inner_iterator)258 inline iterator wrap_iterator(MapType::const_iterator inner_iterator) const { 259 #if SPDY_HEADER_DEBUG 260 iterator outer_iterator(inner_iterator); 261 if (inner_iterator == map_.end()) { 262 outer_iterator.forbid_dereference(); 263 } 264 return outer_iterator; 265 #else // SPDY_HEADER_DEBUG 266 return iterator(inner_iterator); 267 #endif // SPDY_HEADER_DEBUG 268 } 269 wrap_const_iterator(MapType::const_iterator inner_iterator)270 inline const_iterator wrap_const_iterator( 271 MapType::const_iterator inner_iterator) const { 272 #if SPDY_HEADER_DEBUG 273 const_iterator outer_iterator(inner_iterator); 274 if (inner_iterator == map_.end()) { 275 outer_iterator.forbid_dereference(); 276 } 277 return outer_iterator; 278 #else // SPDY_HEADER_DEBUG 279 return iterator(inner_iterator); 280 #endif // SPDY_HEADER_DEBUG 281 } 282 283 void AppendHeader(const absl::string_view key, const absl::string_view value); 284 absl::string_view WriteKey(const absl::string_view key); 285 size_t bytes_allocated() const; 286 287 // absl::string_views held by |map_| point to memory owned by |storage_|. 288 MapType map_; 289 HttpHeaderStorage storage_; 290 291 size_t key_size_ = 0; 292 size_t value_size_ = 0; 293 }; 294 295 inline bool operator==(absl::string_view lhs, 296 const HttpHeaderBlock::ValueProxy& rhs) { 297 return rhs == lhs; 298 } 299 300 } // namespace quiche 301 302 #endif // QUICHE_COMMON_HTTP_HTTP_HEADER_BLOCK_H_ 303