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