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 <limits>
20 #include <tuple>
21
22 #include "perfetto/base/logging.h"
23 #include "perfetto/ext/base/utils.h"
24
25 namespace perfetto {
26 namespace trace_processor {
27
StringPool()28 StringPool::StringPool() {
29 static_assert(
30 StringPool::kMinLargeStringSizeBytes <= StringPool::kBlockSizeBytes + 1,
31 "minimum size of large strings must be small enough to support any "
32 "string that doesn't fit in a Block.");
33
34 blocks_.emplace_back(kBlockSizeBytes);
35
36 // Reserve a slot for the null string.
37 PERFETTO_CHECK(blocks_.back().TryInsert(NullTermStringView()).first);
38 }
39
40 StringPool::~StringPool() = default;
41
42 StringPool::StringPool(StringPool&&) noexcept = default;
43 StringPool& StringPool::operator=(StringPool&&) noexcept = default;
44
InsertString(base::StringView str,uint64_t hash)45 StringPool::Id StringPool::InsertString(base::StringView str, uint64_t hash) {
46 // Try and find enough space in the current block for the string and the
47 // metadata (varint-encoded size + the string data + the null terminator).
48 bool success;
49 uint32_t offset;
50 std::tie(success, offset) = blocks_.back().TryInsert(str);
51 if (PERFETTO_UNLIKELY(!success)) {
52 // The block did not have enough space for the string. If the string is
53 // large, add it into the |large_strings_| vector, to avoid discarding a
54 // large portion of the current block's memory. This also enables us to
55 // support strings that wouldn't fit into a single block. Otherwise, add a
56 // new block to store the string.
57 if (str.size() + kMaxMetadataSize >= kMinLargeStringSizeBytes) {
58 return InsertLargeString(str, hash);
59 }
60 blocks_.emplace_back(kBlockSizeBytes);
61
62 // Try and reserve space again - this time we should definitely succeed.
63 std::tie(success, offset) = blocks_.back().TryInsert(str);
64 PERFETTO_CHECK(success);
65 }
66
67 // Compute the id from the block index and offset and add a mapping from the
68 // hash to the id.
69 Id string_id = Id::BlockString(blocks_.size() - 1, offset);
70
71 // Deliberately not adding |string_id| to |string_index_|. The caller
72 // (InternString()) must take care of this.
73 PERFETTO_DCHECK(string_index_.Find(hash));
74
75 return string_id;
76 }
77
InsertLargeString(base::StringView str,uint64_t hash)78 StringPool::Id StringPool::InsertLargeString(base::StringView str,
79 uint64_t hash) {
80 large_strings_.emplace_back(new std::string(str.begin(), str.size()));
81 // Compute id from the index and add a mapping from the hash to the id.
82 Id string_id = Id::LargeString(large_strings_.size() - 1);
83
84 // Deliberately not adding |string_id| to |string_index_|. The caller
85 // (InternString()) must take care of this.
86 PERFETTO_DCHECK(string_index_.Find(hash));
87
88 return string_id;
89 }
90
TryInsert(base::StringView str)91 std::pair<bool /*success*/, uint32_t /*offset*/> StringPool::Block::TryInsert(
92 base::StringView str) {
93 auto str_size = str.size();
94 size_t max_pos = static_cast<size_t>(pos_) + str_size + kMaxMetadataSize;
95 if (max_pos > size_)
96 return std::make_pair(false, 0u);
97
98 // Ensure that we commit up until the end of the string to memory.
99 mem_.EnsureCommitted(max_pos);
100
101 // Get where we should start writing this string.
102 uint32_t offset = pos_;
103 uint8_t* begin = Get(offset);
104
105 // First write the size of the string using varint encoding.
106 uint8_t* end = protozero::proto_utils::WriteVarInt(str_size, begin);
107
108 // Next the string itself.
109 if (PERFETTO_LIKELY(str_size > 0)) {
110 memcpy(end, str.data(), str_size);
111 end += str_size;
112 }
113
114 // Finally add a null terminator.
115 *(end++) = '\0';
116
117 // Update the end of the block and return the pointer to the string.
118 pos_ = OffsetOf(end);
119
120 return std::make_pair(true, offset);
121 }
122
Iterator(const StringPool * pool)123 StringPool::Iterator::Iterator(const StringPool* pool) : pool_(pool) {}
124
operator ++()125 StringPool::Iterator& StringPool::Iterator::operator++() {
126 if (block_index_ < pool_->blocks_.size()) {
127 // Try and go to the next string in the current block.
128 const auto& block = pool_->blocks_[block_index_];
129
130 // Find the size of the string at the current offset in the block
131 // and increment the offset by that size.
132 uint32_t str_size = 0;
133 const uint8_t* ptr = block.Get(block_offset_);
134 ptr = ReadSize(ptr, &str_size);
135 ptr += str_size + 1;
136 block_offset_ = block.OffsetOf(ptr);
137
138 // If we're out of bounds for this block, go to the start of the next block.
139 if (block.pos() <= block_offset_) {
140 block_index_++;
141 block_offset_ = 0;
142 }
143
144 return *this;
145 }
146
147 // Advance to the next string from |large_strings_|.
148 PERFETTO_DCHECK(large_strings_index_ < pool_->large_strings_.size());
149 large_strings_index_++;
150 return *this;
151 }
152
operator bool() const153 StringPool::Iterator::operator bool() const {
154 return block_index_ < pool_->blocks_.size() ||
155 large_strings_index_ < pool_->large_strings_.size();
156 }
157
StringView()158 NullTermStringView StringPool::Iterator::StringView() {
159 return pool_->Get(StringId());
160 }
161
StringId()162 StringPool::Id StringPool::Iterator::StringId() {
163 if (block_index_ < pool_->blocks_.size()) {
164 PERFETTO_DCHECK(block_offset_ < pool_->blocks_[block_index_].pos());
165
166 // If we're at (0, 0), we have the null string which has id 0.
167 if (block_index_ == 0 && block_offset_ == 0)
168 return Id::Null();
169 return Id::BlockString(block_index_, block_offset_);
170 }
171 PERFETTO_DCHECK(large_strings_index_ < pool_->large_strings_.size());
172 return Id::LargeString(large_strings_index_);
173 }
174
175 } // namespace trace_processor
176 } // namespace perfetto
177