1 // 2 // 3 // Copyright 2015 gRPC authors. 4 // 5 // Licensed under the Apache License, Version 2.0 (the "License"); 6 // you may not use this file except in compliance with the License. 7 // You may obtain a copy of the License at 8 // 9 // http://www.apache.org/licenses/LICENSE-2.0 10 // 11 // Unless required by applicable law or agreed to in writing, software 12 // distributed under the License is distributed on an "AS IS" BASIS, 13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 // See the License for the specific language governing permissions and 15 // limitations under the License. 16 // 17 // 18 19 #ifndef GRPC_SRC_CORE_EXT_TRANSPORT_CHTTP2_TRANSPORT_HPACK_PARSER_TABLE_H 20 #define GRPC_SRC_CORE_EXT_TRANSPORT_CHTTP2_TRANSPORT_HPACK_PARSER_TABLE_H 21 22 #include <grpc/support/port_platform.h> 23 #include <stdint.h> 24 25 #include <cstdint> 26 #include <limits> 27 #include <memory> 28 #include <string> 29 #include <vector> 30 31 #include "absl/functional/function_ref.h" 32 #include "src/core/ext/transport/chttp2/transport/hpack_constants.h" 33 #include "src/core/ext/transport/chttp2/transport/hpack_parse_result.h" 34 #include "src/core/lib/transport/metadata_batch.h" 35 #include "src/core/lib/transport/parsed_metadata.h" 36 #include "src/core/util/no_destruct.h" 37 #include "src/core/util/unique_ptr_with_bitset.h" 38 39 namespace grpc_core { 40 41 // HPACK header table 42 class HPackTable { 43 public: 44 HPackTable() = default; 45 ~HPackTable() = default; 46 47 HPackTable(const HPackTable&) = delete; 48 HPackTable& operator=(const HPackTable&) = delete; 49 HPackTable(HPackTable&&) = default; 50 HPackTable& operator=(HPackTable&&) = default; 51 52 void SetMaxBytes(uint32_t max_bytes); 53 bool SetCurrentTableSize(uint32_t bytes); current_table_size()54 uint32_t current_table_size() { return current_table_bytes_; } 55 56 struct Memento { 57 ParsedMetadata<grpc_metadata_batch> md; 58 // Alongside parse_status we store one bit indicating whether this memento 59 // has been looked up (and therefore consumed) or not. 60 UniquePtrWithBitset<HpackParseResult, 1> parse_status; 61 static const int kUsedBit = 0; 62 }; 63 64 // Lookup, but don't ref. Lookup(uint32_t index)65 const Memento* Lookup(uint32_t index) { 66 // Static table comes first, just return an entry from it. 67 // NB: This imposes the constraint that the first 68 // GRPC_CHTTP2_LAST_STATIC_ENTRY entries in the core static metadata table 69 // must follow the hpack standard. If that changes, we *must* not rely on 70 // reading the core static metadata table here; at that point we'd need our 71 // own singleton static metadata in the correct order. 72 if (index <= hpack_constants::kLastStaticEntry) { 73 return &static_mementos_->memento[index - 1]; 74 } else { 75 return LookupDynamic(index); 76 } 77 } 78 79 // add a table entry to the index 80 GRPC_MUST_USE_RESULT bool Add(Memento md); 81 void AddLargerThanCurrentTableSize(); 82 83 // Current entry count in the table. num_entries()84 uint32_t num_entries() const { return entries_.num_entries(); } 85 86 // Current size of the table. test_only_table_size()87 uint32_t test_only_table_size() const { return mem_used_; } 88 89 // Maximum allowed size of the table currently max_bytes()90 uint32_t max_bytes() const { return max_bytes_; } current_table_bytes()91 uint32_t current_table_bytes() const { return current_table_bytes_; } 92 93 // Dynamic table entries, stringified 94 std::string TestOnlyDynamicTableAsString() const; 95 96 private: 97 struct StaticMementos { 98 StaticMementos(); 99 Memento memento[hpack_constants::kLastStaticEntry]; 100 }; 101 102 class MementoRingBuffer { 103 public: MementoRingBuffer()104 MementoRingBuffer() {} 105 ~MementoRingBuffer(); 106 107 MementoRingBuffer(const MementoRingBuffer&) = delete; 108 MementoRingBuffer& operator=(const MementoRingBuffer&) = delete; 109 MementoRingBuffer(MementoRingBuffer&&) = default; 110 MementoRingBuffer& operator=(MementoRingBuffer&&) = default; 111 112 // Rebuild this buffer with a new max_entries_ size. 113 void Rebuild(uint32_t max_entries); 114 115 // Put a new memento. 116 // REQUIRES: num_entries < max_entries 117 void Put(Memento m); 118 119 // Pop the oldest memento. 120 // REQUIRES: num_entries > 0 121 Memento PopOne(); 122 123 // Lookup the entry at index, or return nullptr if none exists. 124 const Memento* Lookup(uint32_t index); 125 const Memento* Peek(uint32_t index) const; 126 127 template <typename F> 128 void ForEach(F f) const; 129 max_entries()130 uint32_t max_entries() const { return max_entries_; } num_entries()131 uint32_t num_entries() const { return num_entries_; } 132 133 private: 134 // The index of the first entry in the buffer. May be greater than 135 // max_entries_, in which case a wraparound has occurred. 136 uint32_t first_entry_ = 0; 137 // How many entries are in the table. 138 uint32_t num_entries_ = 0; 139 // Maximum number of entries we could possibly fit in the table, given 140 // defined overheads. 141 uint32_t max_entries_ = hpack_constants::kInitialTableEntries; 142 // Which index holds a timestamp (or kNoTimestamp if none do). 143 static constexpr uint32_t kNoTimestamp = 144 std::numeric_limits<uint32_t>::max(); 145 uint32_t timestamp_index_ = kNoTimestamp; 146 // The timestamp associated with timestamp_entry_. 147 Timestamp timestamp_; 148 149 std::vector<Memento> entries_; 150 }; 151 LookupDynamic(uint32_t index)152 const Memento* LookupDynamic(uint32_t index) { 153 // Not static - find the value in the list of valid entries 154 const uint32_t tbl_index = index - (hpack_constants::kLastStaticEntry + 1); 155 return entries_.Lookup(tbl_index); 156 } 157 158 void EvictOne(); 159 GetStaticMementos()160 static const StaticMementos* GetStaticMementos() { 161 static const NoDestruct<StaticMementos> static_mementos; 162 return static_mementos.get(); 163 } 164 165 // The amount of memory used by the table, according to the hpack algorithm 166 uint32_t mem_used_ = 0; 167 // The max memory allowed to be used by the table, according to the hpack 168 // algorithm. 169 uint32_t max_bytes_ = hpack_constants::kInitialTableSize; 170 // The currently agreed size of the table, according to the hpack algorithm. 171 uint32_t current_table_bytes_ = hpack_constants::kInitialTableSize; 172 // HPack table entries 173 MementoRingBuffer entries_; 174 // Static mementos 175 const StaticMementos* static_mementos_ = GetStaticMementos(); 176 }; 177 178 } // namespace grpc_core 179 180 #endif // GRPC_SRC_CORE_EXT_TRANSPORT_CHTTP2_TRANSPORT_HPACK_PARSER_TABLE_H 181