1 /*
2 * Copyright (c) Facebook, Inc. and its affiliates.
3 * All rights reserved.
4 *
5 * This source code is licensed under the BSD-style license found in the
6 * LICENSE file in the root directory of this source tree.
7 */
8
9 #include <folly/portability/GTest.h>
10 #include <memory>
11 #include <proxygen/lib/http/codec/compress/Logging.h>
12 #include <proxygen/lib/http/codec/compress/QPACKHeaderTable.h>
13 #include <sstream>
14
15 namespace proxygen {
16
17 class QPACKHeaderTableTests : public testing::Test {
18 public:
19 protected:
20 QPACKHeaderTable table_{320, true};
21 };
22
TEST_F(QPACKHeaderTableTests,Indexing)23 TEST_F(QPACKHeaderTableTests, Indexing) {
24 HPACKHeader accept("accept-encoding", "gzip");
25 HPACKHeader agent("user-agent", "SeaMonkey");
26
27 EXPECT_EQ(table_.getInsertCount(), 0);
28 table_.add(accept.copy());
29 EXPECT_EQ(table_.getInsertCount(), 1);
30 // Vulnerable - in the table
31 EXPECT_EQ(table_.getIndex(accept, false),
32 std::numeric_limits<uint32_t>::max());
33 // Allow vulnerable, get the index
34 EXPECT_EQ(table_.getIndex(accept, true), 1);
35 EXPECT_TRUE(table_.onInsertCountIncrement(1));
36 EXPECT_EQ(table_.getIndex(accept, false), 1);
37 table_.add(agent.copy());
38 // Indexes move
39 EXPECT_EQ(table_.getIndex(agent, true), 1);
40 EXPECT_EQ(table_.getIndex(accept, true), 2);
41 }
42
TEST_F(QPACKHeaderTableTests,Eviction)43 TEST_F(QPACKHeaderTableTests, Eviction) {
44 HPACKHeader accept("accept-encoding", "gzip");
45
46 int32_t max = 4;
47 uint32_t capacity = accept.bytes() * max;
48 table_.setCapacity(capacity);
49
50 for (auto i = 0; i < max; i++) {
51 EXPECT_TRUE(table_.add(accept.copy()));
52 }
53 for (auto i = 1; i <= max; i++) {
54 table_.addRef(i);
55 }
56 table_.setAcknowledgedInsertCount(max);
57 EXPECT_FALSE(table_.canIndex(accept.name, accept.value));
58 EXPECT_FALSE(table_.add(accept.copy()));
59 table_.subRef(1);
60 EXPECT_TRUE(table_.canIndex(accept.name, accept.value));
61 EXPECT_TRUE(table_.add(accept.copy()));
62
63 table_.subRef(3);
64 EXPECT_FALSE(table_.canIndex(accept.name, accept.value));
65 table_.subRef(2);
66 EXPECT_TRUE(table_.canIndex(accept.name, accept.value));
67 }
68
TEST_F(QPACKHeaderTableTests,BadEviction)69 TEST_F(QPACKHeaderTableTests, BadEviction) {
70 HPACKHeader accept("accept-encoding", "gzip");
71
72 int32_t max = 4;
73 uint32_t capacity = accept.bytes() * max;
74 table_.setCapacity(capacity);
75
76 for (auto i = 0; i < max; i++) {
77 EXPECT_TRUE(table_.add(accept.copy()));
78 }
79 EXPECT_EQ(table_.size(), max);
80 EXPECT_FALSE(table_.setCapacity(capacity / 2));
81 EXPECT_EQ(table_.size(), max);
82
83 // Ack all headers but mark the first as in use
84 table_.setAcknowledgedInsertCount(max);
85 table_.addRef(1);
86 EXPECT_FALSE(table_.setCapacity(capacity / 2));
87
88 // Clear all refs
89 table_.subRef(1);
90 EXPECT_TRUE(table_.setCapacity(capacity / 2));
91 EXPECT_EQ(table_.size(), max / 2);
92 }
93
TEST_F(QPACKHeaderTableTests,Wrapcount)94 TEST_F(QPACKHeaderTableTests, Wrapcount) {
95 HPACKHeader accept("accept-encoding", "gzip");
96 HPACKHeader agent("user-agent", "SeaMonkey");
97 HPACKHeader cookie("Cookie", "choco=chip");
98
99 for (auto i = 0; i < 10; i++) {
100 EXPECT_TRUE(table_.add(accept.copy()));
101 table_.setAcknowledgedInsertCount(i + 1);
102 }
103 EXPECT_TRUE(table_.add(cookie.copy()));
104 EXPECT_TRUE(table_.add(agent.copy()));
105
106 EXPECT_EQ(table_.getInsertCount(), 12);
107 EXPECT_EQ(table_.getIndex(agent, true), 1);
108 EXPECT_EQ(table_.getIndex(cookie, true), 2);
109 EXPECT_EQ(table_.getIndex(accept, true), 3);
110 EXPECT_EQ(table_.getHeader(1, table_.getInsertCount()), agent);
111 EXPECT_EQ(table_.getHeader(2, table_.getInsertCount()), cookie);
112 EXPECT_EQ(table_.getHeader(table_.size(), table_.getInsertCount()), accept);
113 }
114
TEST_F(QPACKHeaderTableTests,NameIndex)115 TEST_F(QPACKHeaderTableTests, NameIndex) {
116 HPACKHeader accept("accept-encoding", "gzip");
117 EXPECT_EQ(table_.nameIndex(accept.name), 0);
118 EXPECT_TRUE(table_.add(accept.copy()));
119 EXPECT_EQ(table_.nameIndex(accept.name), 1);
120 }
121
TEST_F(QPACKHeaderTableTests,GetIndex)122 TEST_F(QPACKHeaderTableTests, GetIndex) {
123 HPACKHeader accept1("accept-encoding", "gzip");
124 HPACKHeader accept2("accept-encoding", "blarf");
125 EXPECT_EQ(table_.getIndex(accept1), 0);
126 EXPECT_TRUE(table_.add(accept1.copy()));
127 EXPECT_EQ(table_.getIndex(accept1), 1);
128 EXPECT_EQ(table_.getIndex(accept2), 0);
129 }
130
TEST_F(QPACKHeaderTableTests,Duplication)131 TEST_F(QPACKHeaderTableTests, Duplication) {
132 HPACKHeader accept("accept-encoding", "gzip");
133
134 EXPECT_TRUE(table_.add(accept.copy()));
135
136 // Unnecessary duplicate
137 auto res = table_.maybeDuplicate(1, true);
138 EXPECT_FALSE(res.first);
139 EXPECT_EQ(res.second, 1);
140
141 for (auto i = 0; i < 6; i++) {
142 EXPECT_TRUE(table_.add(accept.copy()));
143 // Ack the first few entries so they can be evicted
144 table_.setAcknowledgedInsertCount(std::min(3u, table_.getInsertCount()));
145 }
146
147 // successful duplicate, vulnerable allowed
148 EXPECT_TRUE(table_.isDraining(table_.size()));
149 res = table_.maybeDuplicate(table_.size(), true);
150 EXPECT_TRUE(res.first);
151 EXPECT_EQ(res.second, 8);
152 EXPECT_EQ(table_.size(), 6); // evicted 1
153
154 // successful duplicate, vulnerable disallowed
155 EXPECT_TRUE(table_.onInsertCountIncrement(3));
156 res = table_.maybeDuplicate(table_.size(), false);
157 EXPECT_TRUE(res.first);
158 EXPECT_EQ(res.second, 0);
159 EXPECT_EQ(table_.size(), 6); // evicted 2
160
161 // Attempt to duplicate UNACKED
162 res = table_.maybeDuplicate(QPACKHeaderTable::UNACKED, true);
163 EXPECT_FALSE(res.first);
164 EXPECT_EQ(res.second, 0);
165 EXPECT_EQ(table_.size(), 6); // nothing changed
166 EXPECT_EQ(table_.getInsertCount(), 9);
167
168 // Hold a ref to oldest entry, prevents eviction
169 auto oldestAbsolute = table_.getInsertCount() - table_.size() + 1;
170 table_.addRef(oldestAbsolute);
171
172 // Table should be full
173 EXPECT_FALSE(table_.canIndex(accept.name, accept.value));
174
175 res = table_.maybeDuplicate(table_.size(), true);
176 EXPECT_FALSE(res.first);
177 EXPECT_EQ(res.second, 0);
178 }
179
TEST_F(QPACKHeaderTableTests,CanEvictWithRoom)180 TEST_F(QPACKHeaderTableTests, CanEvictWithRoom) {
181 HPACKHeader thirtyNineBytes("abcd", "efg");
182 HPACKHeader fortySevenBytes("abcd", "efghijklmno");
183 for (auto i = 0; i < 8; i++) {
184 EXPECT_TRUE(table_.add(thirtyNineBytes.copy()));
185 }
186 table_.setAcknowledgedInsertCount(table_.getInsertCount());
187 // abs index = 1 is evictable, but index = 2 is referenced, so we can
188 // insert up to (320 - 8 * 39) + 39 = 47
189 table_.addRef(2);
190 EXPECT_TRUE(table_.canIndex(fortySevenBytes.name, fortySevenBytes.value));
191 EXPECT_TRUE(table_.add(fortySevenBytes.copy()));
192 }
193
TEST_F(QPACKHeaderTableTests,EvictNonDrained)194 TEST_F(QPACKHeaderTableTests, EvictNonDrained) {
195 HPACKHeader small("ab", "cd"); // 36 bytes
196 HPACKHeader small2("abcd", std::string(14, 'b')); // 50 bytes
197 HPACKHeader med(std::string(20, 'a'), std::string(20, 'b')); // 72
198 HPACKHeader large(std::string(34, 'a'), std::string(34, 'b')); // 100
199
200 table_.setCapacity(220);
201 EXPECT_TRUE(table_.add(small.copy()));
202 EXPECT_TRUE(table_.add(med.copy()));
203 EXPECT_TRUE(table_.add(large.copy()));
204 EXPECT_TRUE(table_.isDraining(3));
205 EXPECT_FALSE(table_.isDraining(2));
206
207 table_.setAcknowledgedInsertCount(3);
208 // Evicts small and med
209 EXPECT_TRUE(table_.add(small2.copy()));
210 EXPECT_EQ(table_.size(), 2);
211 EXPECT_FALSE(table_.isDraining(1));
212 EXPECT_FALSE(table_.isDraining(2));
213
214 // Now lg should be draining
215 EXPECT_TRUE(table_.add(small.copy()));
216 EXPECT_TRUE(table_.isDraining(3));
217
218 // Evict large
219 EXPECT_TRUE(table_.add(small.copy()));
220 }
221
TEST_F(QPACKHeaderTableTests,BadSync)222 TEST_F(QPACKHeaderTableTests, BadSync) {
223 // Can't ack more than is in the table
224 EXPECT_FALSE(table_.onInsertCountIncrement(1));
225 }
226
TEST_F(QPACKHeaderTableTests,TinyTable)227 TEST_F(QPACKHeaderTableTests, TinyTable) {
228 // This table will tell you it can't hold any headers, but it can!
229 QPACKHeaderTable table(0, true);
230 table.setCapacity(63);
231 HPACKHeader foo("F", "");
232 EXPECT_FALSE(table.canIndex(foo.name, foo.value));
233 EXPECT_TRUE(table.add(foo.copy()));
234 EXPECT_EQ(table.size(), 1);
235 EXPECT_EQ(table.length(), 1);
236 EXPECT_TRUE(table.isDraining(1));
237 }
238 } // namespace proxygen
239