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 
24 #include <stdint.h>
25 
26 #include <string>
27 #include <vector>
28 
29 #include "absl/functional/function_ref.h"
30 
31 #include "src/core/ext/transport/chttp2/transport/hpack_constants.h"
32 #include "src/core/ext/transport/chttp2/transport/hpack_parse_result.h"
33 #include "src/core/lib/gprpp/no_destruct.h"
34 #include "src/core/lib/transport/metadata_batch.h"
35 #include "src/core/lib/transport/parsed_metadata.h"
36 
37 namespace grpc_core {
38 
39 // HPACK header table
40 class HPackTable {
41  public:
42   HPackTable() = default;
43   ~HPackTable() = default;
44 
45   HPackTable(const HPackTable&) = delete;
46   HPackTable& operator=(const HPackTable&) = delete;
47 
48   void SetMaxBytes(uint32_t max_bytes);
49   bool SetCurrentTableSize(uint32_t bytes);
current_table_size()50   uint32_t current_table_size() { return current_table_bytes_; }
51 
52   struct Memento {
53     ParsedMetadata<grpc_metadata_batch> md;
54     HpackParseResult parse_status;
55   };
56 
57   // Lookup, but don't ref.
Lookup(uint32_t index)58   const Memento* Lookup(uint32_t index) const {
59     // Static table comes first, just return an entry from it.
60     // NB: This imposes the constraint that the first
61     // GRPC_CHTTP2_LAST_STATIC_ENTRY entries in the core static metadata table
62     // must follow the hpack standard. If that changes, we *must* not rely on
63     // reading the core static metadata table here; at that point we'd need our
64     // own singleton static metadata in the correct order.
65     if (index <= hpack_constants::kLastStaticEntry) {
66       return &static_mementos_->memento[index - 1];
67     } else {
68       return LookupDynamic(index);
69     }
70   }
71 
72   // add a table entry to the index
73   bool Add(Memento md) GRPC_MUST_USE_RESULT;
74   void AddLargerThanCurrentTableSize();
75 
76   // Current entry count in the table.
num_entries()77   uint32_t num_entries() const { return entries_.num_entries(); }
78 
79   // Current size of the table.
test_only_table_size()80   uint32_t test_only_table_size() const { return mem_used_; }
81 
82   // Maximum allowed size of the table currently
max_bytes()83   uint32_t max_bytes() const { return max_bytes_; }
current_table_bytes()84   uint32_t current_table_bytes() const { return current_table_bytes_; }
85 
86   // Dynamic table entries, stringified
87   std::string TestOnlyDynamicTableAsString() const;
88 
89  private:
90   struct StaticMementos {
91     StaticMementos();
92     Memento memento[hpack_constants::kLastStaticEntry];
93   };
94 
95   class MementoRingBuffer {
96    public:
97     // Rebuild this buffer with a new max_entries_ size.
98     void Rebuild(uint32_t max_entries);
99 
100     // Put a new memento.
101     // REQUIRES: num_entries < max_entries
102     void Put(Memento m);
103 
104     // Pop the oldest memento.
105     // REQUIRES: num_entries > 0
106     Memento PopOne();
107 
108     // Lookup the entry at index, or return nullptr if none exists.
109     const Memento* Lookup(uint32_t index) const;
110 
111     void ForEach(absl::FunctionRef<void(uint32_t dynamic_index, const Memento&)>
112                      f) const;
113 
max_entries()114     uint32_t max_entries() const { return max_entries_; }
num_entries()115     uint32_t num_entries() const { return num_entries_; }
116 
117    private:
118     // The index of the first entry in the buffer. May be greater than
119     // max_entries_, in which case a wraparound has occurred.
120     uint32_t first_entry_ = 0;
121     // How many entries are in the table.
122     uint32_t num_entries_ = 0;
123     // Maximum number of entries we could possibly fit in the table, given
124     // defined overheads.
125     uint32_t max_entries_ = hpack_constants::kInitialTableEntries;
126 
127     std::vector<Memento> entries_;
128   };
129 
LookupDynamic(uint32_t index)130   const Memento* LookupDynamic(uint32_t index) const {
131     // Not static - find the value in the list of valid entries
132     const uint32_t tbl_index = index - (hpack_constants::kLastStaticEntry + 1);
133     return entries_.Lookup(tbl_index);
134   }
135 
136   void EvictOne();
137 
GetStaticMementos()138   static const StaticMementos* GetStaticMementos() {
139     static const NoDestruct<StaticMementos> static_mementos;
140     return static_mementos.get();
141   }
142 
143   // The amount of memory used by the table, according to the hpack algorithm
144   uint32_t mem_used_ = 0;
145   // The max memory allowed to be used by the table, according to the hpack
146   // algorithm.
147   uint32_t max_bytes_ = hpack_constants::kInitialTableSize;
148   // The currently agreed size of the table, according to the hpack algorithm.
149   uint32_t current_table_bytes_ = hpack_constants::kInitialTableSize;
150   // HPack table entries
151   MementoRingBuffer entries_;
152   // Static mementos
153   const StaticMementos* const static_mementos_ = GetStaticMementos();
154 };
155 
156 }  // namespace grpc_core
157 
158 #endif  // GRPC_SRC_CORE_EXT_TRANSPORT_CHTTP2_TRANSPORT_HPACK_PARSER_TABLE_H
159