1 // Copyright 2021 gRPC authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 //     http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #include <grpc/support/port_platform.h>
16 
17 #include "src/core/ext/transport/chttp2/transport/hpack_encoder_table.h"
18 
19 #include <algorithm>
20 
21 #include <grpc/support/log.h>
22 
23 namespace grpc_core {
24 
AllocateIndex(size_t element_size)25 uint32_t HPackEncoderTable::AllocateIndex(size_t element_size) {
26   GPR_DEBUG_ASSERT(element_size >= 32);
27 
28   uint32_t new_index = tail_remote_index_ + table_elems_ + 1;
29   GPR_DEBUG_ASSERT(element_size <= MaxEntrySize());
30 
31   if (element_size > max_table_size_) {
32     while (table_size_ > 0) {
33       EvictOne();
34     }
35     return 0;
36   }
37 
38   // Reserve space for this element in the remote table: if this overflows
39   // the current table, drop elements until it fits, matching the decompressor
40   // algorithm.
41   while (table_size_ + element_size > max_table_size_) {
42     EvictOne();
43   }
44   GPR_ASSERT(table_elems_ < elem_size_.size());
45   elem_size_[new_index % elem_size_.size()] =
46       static_cast<uint16_t>(element_size);
47   table_size_ += element_size;
48   table_elems_++;
49 
50   return new_index;
51 }
52 
SetMaxSize(uint32_t max_table_size)53 bool HPackEncoderTable::SetMaxSize(uint32_t max_table_size) {
54   if (max_table_size == max_table_size_) {
55     return false;
56   }
57   while (table_size_ > 0 && table_size_ > max_table_size) {
58     EvictOne();
59   }
60   max_table_size_ = max_table_size;
61   const size_t max_table_elems =
62       hpack_constants::EntriesForBytes(max_table_size);
63   // TODO(ctiller): integrate with ResourceQuota to rebuild smaller when we can.
64   if (max_table_elems > elem_size_.size()) {
65     Rebuild(static_cast<uint32_t>(
66         std::max(max_table_elems, 2 * elem_size_.size())));
67   }
68   return true;
69 }
70 
EvictOne()71 void HPackEncoderTable::EvictOne() {
72   tail_remote_index_++;
73   GPR_ASSERT(tail_remote_index_ > 0);
74   GPR_ASSERT(table_elems_ > 0);
75   auto removing_size = elem_size_[tail_remote_index_ % elem_size_.size()];
76   GPR_ASSERT(table_size_ >= removing_size);
77   table_size_ -= removing_size;
78   table_elems_--;
79 }
80 
Rebuild(uint32_t capacity)81 void HPackEncoderTable::Rebuild(uint32_t capacity) {
82   decltype(elem_size_) new_elem_size(capacity);
83   GPR_ASSERT(table_elems_ <= capacity);
84   for (uint32_t i = 0; i < table_elems_; i++) {
85     uint32_t ofs = tail_remote_index_ + i + 1;
86     new_elem_size[ofs % capacity] = elem_size_[ofs % elem_size_.size()];
87   }
88   elem_size_.swap(new_elem_size);
89 }
90 
91 }  // namespace grpc_core
92