1 /*
2 * Copyright (C) 2019 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "src/trace_processor/containers/string_pool.h"
18
19 #include <array>
20 #include <random>
21
22 #include "test/gtest_and_gmock.h"
23
24 namespace perfetto {
25 namespace trace_processor {
26
27 class StringPoolTest : public testing::Test {
28 protected:
29 static constexpr size_t kNumBlockOffsetBits = StringPool::kNumBlockOffsetBits;
30 static constexpr size_t kBlockIndexBitMask = StringPool::kBlockIndexBitMask;
31 static constexpr size_t kBlockSizeBytes = StringPool::kBlockSizeBytes;
32 static constexpr size_t kMinLargeStringSizeBytes =
33 StringPool::kMinLargeStringSizeBytes;
34
35 StringPool pool_;
36 };
37
38 namespace {
39
TEST_F(StringPoolTest,EmptyPool)40 TEST_F(StringPoolTest, EmptyPool) {
41 ASSERT_EQ(pool_.Get(StringPool::Id::Null()).c_str(), nullptr);
42
43 auto it = pool_.CreateIterator();
44 ASSERT_TRUE(it);
45 ASSERT_EQ(it.StringView().c_str(), nullptr);
46 ASSERT_FALSE(++it);
47 }
48
TEST_F(StringPoolTest,InternAndRetrieve)49 TEST_F(StringPoolTest, InternAndRetrieve) {
50 static char kString[] = "Test String";
51 auto id = pool_.InternString(kString);
52 ASSERT_STREQ(pool_.Get(id).c_str(), kString);
53 ASSERT_EQ(pool_.Get(id), kString);
54 ASSERT_EQ(id, pool_.InternString(kString));
55 }
56
TEST_F(StringPoolTest,NullPointerHandling)57 TEST_F(StringPoolTest, NullPointerHandling) {
58 auto id = pool_.InternString(NullTermStringView());
59 ASSERT_TRUE(id.is_null());
60 ASSERT_EQ(pool_.Get(id).c_str(), nullptr);
61 }
62
TEST_F(StringPoolTest,Iterator)63 TEST_F(StringPoolTest, Iterator) {
64 auto it = pool_.CreateIterator();
65 ASSERT_TRUE(it);
66 ASSERT_EQ(it.StringView().c_str(), nullptr);
67 ASSERT_FALSE(++it);
68
69 static char kString[] = "Test String";
70 pool_.InternString(kString);
71
72 it = pool_.CreateIterator();
73 ASSERT_TRUE(++it);
74 ASSERT_STREQ(it.StringView().c_str(), kString);
75 ASSERT_FALSE(++it);
76 }
77
TEST_F(StringPoolTest,ConstIterator)78 TEST_F(StringPoolTest, ConstIterator) {
79 static char kString[] = "Test String";
80 pool_.InternString(kString);
81
82 const StringPool& const_pool = pool_;
83
84 auto it = const_pool.CreateIterator();
85 ASSERT_TRUE(it);
86 ASSERT_TRUE(++it);
87 ASSERT_STREQ(it.StringView().c_str(), kString);
88 ASSERT_FALSE(++it);
89 }
90
TEST_F(StringPoolTest,StressTest)91 TEST_F(StringPoolTest, StressTest) {
92 // First create a buffer with 33MB of random characters, so that we insert
93 // into at least two chunks.
94 constexpr size_t kBufferSize = 33 * 1024 * 1024;
95 std::minstd_rand0 rnd_engine(0);
96 std::unique_ptr<char[]> buffer(new char[kBufferSize]);
97 for (size_t i = 0; i < kBufferSize; i++)
98 buffer.get()[i] = 'A' + (rnd_engine() % 26);
99
100 // Next create strings of length 0 to 16k in length from this buffer and
101 // intern them, storing their ids.
102 std::multimap<StringPool::Id, base::StringView> string_map;
103 constexpr uint16_t kMaxStrSize = 16u * 1024u - 1;
104 for (size_t i = 0;;) {
105 size_t length = static_cast<uint64_t>(rnd_engine()) % (kMaxStrSize + 1);
106 if (i + length > kBufferSize)
107 break;
108
109 auto str = base::StringView(&buffer.get()[i], length);
110 string_map.emplace(pool_.InternString(str), str);
111 i += length;
112 }
113
114 // Finally, iterate through each string in the string pool, check that all ids
115 // that match in the multimap are equal, and finish by checking we've removed
116 // every item in the multimap.
117 for (auto it = pool_.CreateIterator(); it; ++it) {
118 ASSERT_EQ(it.StringView(), pool_.Get(it.StringId()));
119
120 auto it_pair = string_map.equal_range(it.StringId());
121 for (auto in_it = it_pair.first; in_it != it_pair.second; ++in_it) {
122 ASSERT_EQ(it.StringView(), in_it->second)
123 << it.StringId().raw_id() << ": " << it.StringView().Hash() << " vs "
124 << in_it->second.Hash();
125 }
126 string_map.erase(it_pair.first, it_pair.second);
127 }
128 ASSERT_EQ(string_map.size(), 0u);
129 }
130
TEST_F(StringPoolTest,BigString)131 TEST_F(StringPoolTest, BigString) {
132 // Two of these should fit into one block, but the third one should go into
133 // the |large_strings_| list.
134 constexpr size_t kBigStringSize = 15 * 1024 * 1024;
135 // Will fit into block 1 after two kBigStringSize strings.
136 constexpr size_t kSmallStringSize = 16 * 1024;
137 // Will not fit into block 1 anymore after 2*kBigStringSize and
138 // 2*kSmallStringSize, but is smaller than kMinLargeStringSizeBytes, so will
139 // start a new block.
140 constexpr size_t kMediumStringSize = 2 * 1024 * 1024;
141 // Would not fit into a block at all, so ahs to go into |large_strings_|.
142 constexpr size_t kEnormousStringSize = 33 * 1024 * 1024;
143
144 constexpr std::array<size_t, 8> kStringSizes = {
145 kBigStringSize, // block 1
146 kBigStringSize, // block 1
147 kBigStringSize, // large strings
148 kSmallStringSize, // block 1
149 kSmallStringSize, // block 1
150 kMediumStringSize, // block 2
151 kEnormousStringSize, // large strings
152 kBigStringSize // block 2
153 };
154
155 static_assert(kBigStringSize * 2 + kSmallStringSize * 2 + kMediumStringSize >
156 kBlockSizeBytes,
157 "medium string shouldn't fit into block 1 for this test");
158 static_assert(kMediumStringSize < kMinLargeStringSizeBytes,
159 "medium string should cause a new block for this test");
160
161 std::array<std::unique_ptr<char[]>, kStringSizes.size()> big_strings;
162 for (size_t i = 0; i < big_strings.size(); i++) {
163 big_strings[i].reset(new char[kStringSizes[i] + 1]);
164 for (size_t j = 0; j < kStringSizes[i]; j++) {
165 big_strings[i].get()[j] = 'A' + static_cast<char>((j + i) % 26);
166 }
167 big_strings[i].get()[kStringSizes[i]] = '\0';
168 }
169
170 std::array<StringPool::Id, kStringSizes.size()> string_ids;
171 for (size_t i = 0; i < big_strings.size(); i++) {
172 string_ids[i] = pool_.InternString(
173 base::StringView(big_strings[i].get(), kStringSizes[i]));
174 // Interning it a second time should return the original id.
175 ASSERT_EQ(string_ids[i], pool_.InternString(base::StringView(
176 big_strings[i].get(), kStringSizes[i])));
177 }
178
179 ASSERT_FALSE(string_ids[0].is_large_string());
180 ASSERT_FALSE(string_ids[1].is_large_string());
181 ASSERT_TRUE(string_ids[2].is_large_string());
182 ASSERT_FALSE(string_ids[3].is_large_string());
183 ASSERT_FALSE(string_ids[4].is_large_string());
184 ASSERT_FALSE(string_ids[5].is_large_string());
185 ASSERT_TRUE(string_ids[6].is_large_string());
186 ASSERT_FALSE(string_ids[7].is_large_string());
187
188 ASSERT_EQ(string_ids[0].block_index(), 0u);
189 ASSERT_EQ(string_ids[1].block_index(), 0u);
190 ASSERT_EQ(string_ids[3].block_index(), 0u);
191 ASSERT_EQ(string_ids[4].block_index(), 0u);
192 ASSERT_EQ(string_ids[5].block_index(), 1u);
193 ASSERT_EQ(string_ids[7].block_index(), 1u);
194
195 for (size_t i = 0; i < big_strings.size(); i++) {
196 ASSERT_EQ(big_strings[i].get(), pool_.Get(string_ids[i]));
197 }
198 }
199
200 } // namespace
201 } // namespace trace_processor
202 } // namespace perfetto
203