trace_processor: implement string pooling class
This CL introduces string pooling functionality to the trace processor
backed by PagedMemory.
This class uses fixed pages of memory with the following
properties:
1. On 64-bit machines, we mmap a 4GB chunk of memory and then use the
offset into this chunk as the StringId.
2. On 32-bit machines, we mmap 32MB chunks (this is because the UI will
malloc anything we mmap so we want to be conservative). The raw pointer
is then used directly as the StringId.
The use of this class inside the trace processor will be carried out
in a follow up CL.
Change-Id: Id1ede4e626b0ec65041be7177a08d3b1fcdbdbbc
diff --git a/Android.bp b/Android.bp
index 54a9d23..320c21a 100644
--- a/Android.bp
+++ b/Android.bp
@@ -3165,6 +3165,7 @@
"src/trace_processor/storage_columns.cc",
"src/trace_processor/storage_schema.cc",
"src/trace_processor/storage_table.cc",
+ "src/trace_processor/string_pool.cc",
"src/trace_processor/string_table.cc",
"src/trace_processor/table.cc",
"src/trace_processor/thread_table.cc",
diff --git a/include/perfetto/base/string_view.h b/include/perfetto/base/string_view.h
index 994264c..55cbe0c 100644
--- a/include/perfetto/base/string_view.h
+++ b/include/perfetto/base/string_view.h
@@ -34,19 +34,25 @@
public:
static constexpr size_t npos = static_cast<size_t>(-1);
- StringView() : data_(""), size_(0) {}
+ StringView() : data_(nullptr), size_(0) {}
StringView(const StringView&) = default;
StringView& operator=(const StringView&) = default;
- StringView(const char* data, size_t size) : data_(data), size_(size) {}
+ StringView(const char* data, size_t size) : data_(data), size_(size) {
+ PERFETTO_DCHECK(data != nullptr);
+ }
// Allow implicit conversion from any class that has a |data| and |size| field
// and has the kConvertibleToStringView trait (e.g., protozero::ConstChars).
template <typename T, typename = std::enable_if<T::kConvertibleToStringView>>
- StringView(const T& x) : StringView(x.data, x.size) {}
+ StringView(const T& x) : StringView(x.data, x.size) {
+ PERFETTO_DCHECK(x.data != nullptr);
+ }
// Creates a StringView from a null-terminated C string.
// Deliberately not "explicit".
- StringView(const char* cstr) : data_(cstr), size_(strlen(cstr)) {}
+ StringView(const char* cstr) : data_(cstr), size_(strlen(cstr)) {
+ PERFETTO_DCHECK(cstr != nullptr);
+ }
// This instead has to be explicit, as creating a StringView out of a
// std::string can be subtle.
@@ -80,12 +86,14 @@
StringView substr(size_t pos, size_t count = npos) const {
if (pos >= size_)
- return StringView();
+ return StringView("", 0);
size_t rcount = std::min(count, size_ - pos);
return StringView(data_ + pos, rcount);
}
- std::string ToStdString() const { return std::string(data_, size_); }
+ std::string ToStdString() const {
+ return data_ == nullptr ? "" : std::string(data_, size_);
+ }
uint64_t Hash() const {
base::Hash hasher;
@@ -101,6 +109,8 @@
inline bool operator==(const StringView& x, const StringView& y) {
if (x.size() != y.size())
return false;
+ if (x.size() == 0)
+ return true;
return memcmp(x.data(), y.data(), x.size()) == 0;
}
@@ -108,6 +118,26 @@
return !(x == y);
}
+inline bool operator<(const StringView& x, const StringView& y) {
+ auto size = std::min(x.size(), y.size());
+ if (size == 0)
+ return x.size() < y.size();
+ int result = memcmp(x.data(), y.data(), size);
+ return result < 0 || (result == 0 && x.size() < y.size());
+}
+
+inline bool operator>=(const StringView& x, const StringView& y) {
+ return !(x < y);
+}
+
+inline bool operator>(const StringView& x, const StringView& y) {
+ return y < x;
+}
+
+inline bool operator<=(const StringView& x, const StringView& y) {
+ return !(y < x);
+}
+
} // namespace base
} // namespace perfetto
diff --git a/src/base/string_view_unittest.cc b/src/base/string_view_unittest.cc
index 5b1e492..61dd2a6 100644
--- a/src/base/string_view_unittest.cc
+++ b/src/base/string_view_unittest.cc
@@ -28,6 +28,7 @@
namespace {
TEST(StringViewTest, BasicCases) {
+ EXPECT_EQ(StringView(), StringView(""));
EXPECT_EQ(StringView(""), StringView(""));
EXPECT_EQ(StringView(""), StringView("", 0));
EXPECT_EQ(StringView("ab"), StringView("ab", 2));
@@ -38,6 +39,8 @@
EXPECT_TRUE(StringView("x") != StringView(""));
EXPECT_TRUE(StringView("") != StringView("y"));
EXPECT_TRUE(StringView("a") != StringView("b"));
+ EXPECT_EQ(StringView().size(), 0ul);
+ EXPECT_EQ(StringView().data(), nullptr);
EXPECT_EQ(StringView("").size(), 0ul);
EXPECT_NE(StringView("").data(), nullptr);
EXPECT_TRUE(StringView("").empty());
@@ -54,18 +57,22 @@
}
// Test find().
+ EXPECT_EQ(StringView().find('x'), StringView::npos);
EXPECT_EQ(StringView("").find('x'), StringView::npos);
EXPECT_EQ(StringView("foo").find('x'), StringView::npos);
EXPECT_EQ(StringView("foo").find('f'), 0u);
EXPECT_EQ(StringView("foo").find('o'), 1u);
// Test rfind().
+ EXPECT_EQ(StringView().rfind('x'), StringView::npos);
EXPECT_EQ(StringView("").rfind('x'), StringView::npos);
EXPECT_EQ(StringView("foo").rfind('x'), StringView::npos);
EXPECT_EQ(StringView("foo").rfind('f'), 0u);
EXPECT_EQ(StringView("foo").rfind('o'), 2u);
// Test substr().
+ EXPECT_EQ(StringView().substr(0, 0).ToStdString(), "");
+ EXPECT_EQ(StringView().substr(3, 1).ToStdString(), "");
EXPECT_EQ(StringView("foo").substr(3, 1).ToStdString(), "");
EXPECT_EQ(StringView("foo").substr(4, 0).ToStdString(), "");
EXPECT_EQ(StringView("foo").substr(4, 1).ToStdString(), "");
@@ -78,6 +85,50 @@
EXPECT_EQ(StringView("xyz").substr(0).ToStdString(), "xyz");
EXPECT_EQ(StringView("xyz").substr(2).ToStdString(), "z");
EXPECT_EQ(StringView("xyz").substr(3).ToStdString(), "");
+
+ // Test the < operator.
+ EXPECT_FALSE(StringView() < StringView());
+ EXPECT_FALSE(StringView() < StringView(""));
+ EXPECT_TRUE(StringView() < StringView("foo"));
+ EXPECT_TRUE(StringView("") < StringView("foo"));
+ EXPECT_FALSE(StringView() < StringView("foo", 0));
+ EXPECT_FALSE(StringView("foo") < StringView("foo"));
+ EXPECT_TRUE(StringView("foo") < StringView("fooo"));
+ EXPECT_FALSE(StringView("fooo") < StringView("foo"));
+ EXPECT_TRUE(StringView("bar") < StringView("foo"));
+
+ // Test the <= operator.
+ EXPECT_TRUE(StringView() <= StringView());
+ EXPECT_TRUE(StringView() <= StringView(""));
+ EXPECT_TRUE(StringView() <= StringView("foo"));
+ EXPECT_TRUE(StringView("") <= StringView("foo"));
+ EXPECT_TRUE(StringView() <= StringView("foo", 0));
+ EXPECT_TRUE(StringView("foo") <= StringView("foo"));
+ EXPECT_TRUE(StringView("foo") <= StringView("fooo"));
+ EXPECT_FALSE(StringView("fooo") <= StringView("foo"));
+ EXPECT_TRUE(StringView("bar") <= StringView("foo"));
+
+ // Test the > operator.
+ EXPECT_FALSE(StringView() > StringView());
+ EXPECT_FALSE(StringView() > StringView(""));
+ EXPECT_FALSE(StringView() > StringView("foo"));
+ EXPECT_FALSE(StringView("") > StringView("foo"));
+ EXPECT_FALSE(StringView() > StringView("foo", 0));
+ EXPECT_FALSE(StringView("foo") > StringView("foo"));
+ EXPECT_FALSE(StringView("foo") > StringView("fooo"));
+ EXPECT_TRUE(StringView("fooo") > StringView("foo"));
+ EXPECT_FALSE(StringView("bar") > StringView("foo"));
+
+ // Test the >= operator.
+ EXPECT_TRUE(StringView() >= StringView());
+ EXPECT_TRUE(StringView() >= StringView(""));
+ EXPECT_FALSE(StringView() >= StringView("foo"));
+ EXPECT_FALSE(StringView("") >= StringView("foo"));
+ EXPECT_TRUE(StringView() >= StringView("foo", 0));
+ EXPECT_TRUE(StringView("foo") >= StringView("foo"));
+ EXPECT_FALSE(StringView("foo") >= StringView("fooo"));
+ EXPECT_TRUE(StringView("fooo") >= StringView("foo"));
+ EXPECT_FALSE(StringView("bar") >= StringView("foo"));
}
TEST(StringViewTest, HashCollisions) {
diff --git a/src/trace_processor/BUILD.gn b/src/trace_processor/BUILD.gn
index c7f12a7..2b7790e 100644
--- a/src/trace_processor/BUILD.gn
+++ b/src/trace_processor/BUILD.gn
@@ -103,6 +103,8 @@
"storage_schema.h",
"storage_table.cc",
"storage_table.h",
+ "string_pool.cc",
+ "string_pool.h",
"string_table.cc",
"string_table.h",
"table.cc",
@@ -196,6 +198,7 @@
"event_tracker_unittest.cc",
"filtered_row_index_unittest.cc",
"ftrace_utils_unittest.cc",
+ "null_term_string_view_unittest.cc",
"process_table_unittest.cc",
"process_tracker_unittest.cc",
"proto_trace_parser_unittest.cc",
@@ -204,6 +207,7 @@
"slice_tracker_unittest.cc",
"span_join_operator_table_unittest.cc",
"sqlite3_str_split_unittest.cc",
+ "string_pool_unittest.cc",
"thread_table_unittest.cc",
"trace_processor_impl_unittest.cc",
"trace_sorter_unittest.cc",
diff --git a/src/trace_processor/null_term_string_view.h b/src/trace_processor/null_term_string_view.h
new file mode 100644
index 0000000..60a27f9
--- /dev/null
+++ b/src/trace_processor/null_term_string_view.h
@@ -0,0 +1,60 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef SRC_TRACE_PROCESSOR_NULL_TERM_STRING_VIEW_H_
+#define SRC_TRACE_PROCESSOR_NULL_TERM_STRING_VIEW_H_
+
+#include "perfetto/base/string_view.h"
+
+namespace perfetto {
+namespace trace_processor {
+
+// A string-like object that refers to a non-owned piece of memory which is
+// null terminated.
+class NullTermStringView : public base::StringView {
+ public:
+ // Creates an empty view.
+ NullTermStringView() : StringView() {}
+
+ // Make the view copy constructible.
+ NullTermStringView(const NullTermStringView&) = default;
+ NullTermStringView& operator=(const NullTermStringView&) = default;
+
+ // Creates a NullTermStringView from a null-terminated C string.
+ // Deliberately not "explicit".
+ NullTermStringView(const char* cstr) : StringView(cstr) {}
+
+ // Creates a NullTermStringView from a null terminated C-string where the
+ // size is known. This allows a call to strlen() to be avoided.
+ // Note: This string MUST be null terminated i.e. data[size] == '\0' MUST hold
+ // for this constructor to be valid.
+ NullTermStringView(const char* data, size_t size) : StringView(data, size) {
+ PERFETTO_DCHECK(data[size] == '\0');
+ }
+
+ // This instead has to be explicit, as creating a NullTermStringView out of a
+ // std::string can be subtle.
+ explicit NullTermStringView(const std::string& str) : StringView(str) {}
+
+ // Returns the null terminated C-string backing this string view. The same
+ // pointer as |data()| is returned.
+ const char* c_str() const { return data(); }
+};
+
+} // namespace trace_processor
+} // namespace perfetto
+
+#endif // SRC_TRACE_PROCESSOR_NULL_TERM_STRING_VIEW_H_
diff --git a/src/trace_processor/null_term_string_view_unittest.cc b/src/trace_processor/null_term_string_view_unittest.cc
new file mode 100644
index 0000000..2d24e06
--- /dev/null
+++ b/src/trace_processor/null_term_string_view_unittest.cc
@@ -0,0 +1,74 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "src/trace_processor/null_term_string_view.h"
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace {
+
+TEST(NullTermStringViewTest, Comparisions) {
+ // Test the < operator.
+ EXPECT_FALSE(NullTermStringView() < NullTermStringView());
+ EXPECT_FALSE(NullTermStringView() < NullTermStringView(""));
+ EXPECT_TRUE(NullTermStringView() < NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView("") < NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView() < NullTermStringView("foo", 0));
+ EXPECT_FALSE(NullTermStringView("foo") < NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView("foo") < NullTermStringView("fooo"));
+ EXPECT_FALSE(NullTermStringView("fooo") < NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView("bar") < NullTermStringView("foo"));
+
+ // Test the <= operator.
+ EXPECT_TRUE(NullTermStringView() <= NullTermStringView());
+ EXPECT_TRUE(NullTermStringView() <= NullTermStringView(""));
+ EXPECT_TRUE(NullTermStringView() <= NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView("") <= NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView() <= NullTermStringView("foo", 0));
+ EXPECT_TRUE(NullTermStringView("foo") <= NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView("foo") <= NullTermStringView("fooo"));
+ EXPECT_FALSE(NullTermStringView("fooo") <= NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView("bar") <= NullTermStringView("foo"));
+
+ // Test the > operator.
+ EXPECT_FALSE(NullTermStringView() > NullTermStringView());
+ EXPECT_FALSE(NullTermStringView() > NullTermStringView(""));
+ EXPECT_FALSE(NullTermStringView() > NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView("") > NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView() > NullTermStringView("foo", 0));
+ EXPECT_FALSE(NullTermStringView("foo") > NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView("foo") > NullTermStringView("fooo"));
+ EXPECT_TRUE(NullTermStringView("fooo") > NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView("bar") > NullTermStringView("foo"));
+
+ // Test the >= operator.
+ EXPECT_TRUE(NullTermStringView() >= NullTermStringView());
+ EXPECT_TRUE(NullTermStringView() >= NullTermStringView(""));
+ EXPECT_FALSE(NullTermStringView() >= NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView("") >= NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView() >= NullTermStringView("foo", 0));
+ EXPECT_TRUE(NullTermStringView("foo") >= NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView("foo") >= NullTermStringView("fooo"));
+ EXPECT_TRUE(NullTermStringView("fooo") >= NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView("bar") >= NullTermStringView("foo"));
+}
+
+} // namespace
+} // namespace trace_processor
+} // namespace perfetto
diff --git a/src/trace_processor/string_pool.cc b/src/trace_processor/string_pool.cc
new file mode 100644
index 0000000..fda57f5
--- /dev/null
+++ b/src/trace_processor/string_pool.cc
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "src/trace_processor/string_pool.h"
+
+#include "perfetto/base/logging.h"
+
+namespace perfetto {
+namespace trace_processor {
+
+StringPool::StringPool() {
+ blocks_.emplace_back();
+
+ // Reserve a slot for the null string.
+ PERFETTO_CHECK(blocks_.back().TryInsert(NullTermStringView()));
+}
+
+StringPool::~StringPool() = default;
+
+StringPool::StringPool(StringPool&&) noexcept = default;
+StringPool& StringPool::operator=(StringPool&&) = default;
+
+StringPool::Id StringPool::InsertString(base::StringView str, uint64_t hash) {
+ // We shouldn't be writing string with more than 2^16 characters to the pool.
+ PERFETTO_CHECK(str.size() < std::numeric_limits<uint16_t>::max());
+
+ // Try and find enough space in the current block for the string and the
+ // metadata (the size of the string + the null terminator + 2 bytes to encode
+ // the size itself).
+ auto* ptr = blocks_.back().TryInsert(str);
+ if (PERFETTO_UNLIKELY(!ptr)) {
+ // This means the block did not have enough space. This should only happen
+ // on 32-bit platforms as we allocate a 4GB mmap on 64 bit.
+ PERFETTO_CHECK(sizeof(uint8_t*) == 4);
+
+ // Add a new block to store the data.
+ blocks_.emplace_back();
+
+ // Try and reserve space again - this time we should definitely succeed.
+ ptr = blocks_.back().TryInsert(str);
+ PERFETTO_CHECK(ptr);
+ }
+
+ // Finish by computing the id of the pointer and adding a mapping from the
+ // hash to the string_id.
+ Id string_id = PtrToId(ptr);
+ string_index_.emplace(hash, string_id);
+ return string_id;
+}
+
+uint8_t* StringPool::Block::TryInsert(base::StringView str) {
+ auto str_size = str.size();
+ auto size = str_size + kMetadataSize;
+ if (static_cast<uint64_t>(pos_) + size >= kBlockSize)
+ return nullptr;
+
+ // Get where we should start writing this string.
+ uint8_t* ptr = Get(pos_);
+
+ // First memcpy the size of the string into the buffer.
+ memcpy(ptr, &str_size, sizeof(str_size));
+
+ // Next the string itself which starts at offset 2.
+ if (PERFETTO_LIKELY(str_size > 0))
+ memcpy(&ptr[2], str.data(), str_size);
+
+ // Finally add a null terminator.
+ ptr[2 + str_size] = '\0';
+
+ // Update the end of the block and return the pointer to the string.
+ pos_ += size;
+ return ptr;
+}
+
+StringPool::Iterator::Iterator(const StringPool* pool) : pool_(pool) {}
+
+StringPool::Iterator& StringPool::Iterator::operator++() {
+ PERFETTO_DCHECK(block_id_ < pool_->blocks_.size());
+
+ // Try and go to the next string in the current block.
+ const auto& block = pool_->blocks_[block_id_];
+
+ // Find the size of the string at the current offset in the block
+ // and increment the offset by that size.
+ auto str_size = GetSize(block.Get(block_offset_));
+ block_offset_ += kMetadataSize + str_size;
+
+ // If we're out of bounds for this block, go the the start of the next block.
+ if (block.pos() <= block_offset_) {
+ block_id_++;
+ block_offset_ = 0;
+ }
+ return *this;
+}
+
+StringPool::Iterator::operator bool() const {
+ return block_id_ < pool_->blocks_.size();
+}
+
+NullTermStringView StringPool::Iterator::StringView() {
+ PERFETTO_DCHECK(block_id_ < pool_->blocks_.size());
+ PERFETTO_DCHECK(block_offset_ < pool_->blocks_[block_id_].pos());
+
+ // If we're at (0, 0), we have the null string.
+ if (block_id_ == 0 && block_offset_ == 0)
+ return NullTermStringView();
+ return GetFromPtr(pool_->blocks_[block_id_].Get(block_offset_));
+}
+
+StringPool::Id StringPool::Iterator::StringId() {
+ PERFETTO_DCHECK(block_id_ < pool_->blocks_.size());
+ PERFETTO_DCHECK(block_offset_ < pool_->blocks_[block_id_].pos());
+
+ // If we're at (0, 0), we have the null string which has id 0.
+ if (block_id_ == 0 && block_offset_ == 0)
+ return 0;
+ return pool_->PtrToId(pool_->blocks_[block_id_].Get(block_offset_));
+}
+
+} // namespace trace_processor
+} // namespace perfetto
diff --git a/src/trace_processor/string_pool.h b/src/trace_processor/string_pool.h
new file mode 100644
index 0000000..a525dd1
--- /dev/null
+++ b/src/trace_processor/string_pool.h
@@ -0,0 +1,194 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef SRC_TRACE_PROCESSOR_STRING_POOL_H_
+#define SRC_TRACE_PROCESSOR_STRING_POOL_H_
+
+#include "perfetto/base/paged_memory.h"
+#include "src/trace_processor/null_term_string_view.h"
+
+#include <unordered_map>
+#include <vector>
+
+namespace perfetto {
+namespace trace_processor {
+
+// Interns strings in a string pool and hands out compact StringIds which can
+// be used to retrieve the string in O(1).
+// On 64-bit platforms, the string pool is implemented as a mmaped buffer
+// of 4GB with the id being equal ot the offset into this buffer of the string.
+// On 32-bit platforms instead, the implementation allocates 32MB blocks of
+// mmaped memory with the pointer being directly converted to the id.
+class StringPool {
+ public:
+ using Id = uint32_t;
+
+ // Iterator over the strings in the pool.
+ class Iterator {
+ public:
+ Iterator(const StringPool*);
+
+ explicit operator bool() const;
+ Iterator& operator++();
+
+ NullTermStringView StringView();
+ Id StringId();
+
+ private:
+ const StringPool* pool_ = nullptr;
+ uint32_t block_id_ = 0;
+ uint32_t block_offset_ = 0;
+ };
+
+ StringPool();
+ ~StringPool();
+
+ // Allow std::move().
+ StringPool(StringPool&&) noexcept;
+ StringPool& operator=(StringPool&&);
+
+ // Disable implicit copy.
+ StringPool(const StringPool&) = delete;
+ StringPool& operator=(const StringPool&) = delete;
+
+ Id InternString(base::StringView str) {
+ if (str.data() == nullptr)
+ return 0;
+
+ auto hash = str.Hash();
+ auto id_it = string_index_.find(hash);
+ if (id_it != string_index_.end()) {
+ PERFETTO_DCHECK(Get(id_it->second) == str);
+ return id_it->second;
+ }
+ return InsertString(str, hash);
+ }
+
+ NullTermStringView Get(Id id) const {
+ if (id == 0)
+ return NullTermStringView();
+ return GetFromPtr(IdToPtr(id));
+ }
+
+ Iterator CreateIterator() { return Iterator(this); }
+
+ size_t size() const { return string_index_.size(); }
+
+ private:
+ using StringHash = uint64_t;
+ struct Block {
+ Block() : mem_(base::PagedMemory::Allocate(kBlockSize)) {}
+ ~Block() = default;
+
+ // Allow std::move().
+ Block(Block&&) noexcept = default;
+ Block& operator=(Block&&) = default;
+
+ // Disable implicit copy.
+ Block(const Block&) = delete;
+ Block& operator=(const Block&) = delete;
+
+ uint8_t* Get(uint32_t offset) const {
+ return static_cast<uint8_t*>(mem_.Get()) + offset;
+ }
+
+ uint8_t* TryInsert(base::StringView str);
+
+ uint32_t OffsetOf(uint8_t* ptr) const {
+ PERFETTO_DCHECK(Get(0) < ptr && ptr < Get(kBlockSize - 1));
+ return static_cast<uint32_t>(ptr - Get(0));
+ }
+
+ uint32_t pos() const { return pos_; }
+
+ private:
+ static constexpr size_t kBlockSize =
+ sizeof(void*) == 8
+ ? static_cast<size_t>(4ull * 1024ull * 1024ull * 1024ull) /* 4GB */
+ : 32ull * 1024ull * 1024ull /* 32MB */;
+
+ base::PagedMemory mem_;
+ uint32_t pos_ = 0;
+ };
+
+ friend class Iterator;
+
+ // Number of bytes to reserve for size and null terminator.
+ static constexpr uint8_t kMetadataSize = 3;
+
+ // Inserts the string with the given hash into the pool
+ Id InsertString(base::StringView, uint64_t hash);
+
+ // |ptr| should point to the start of the string metadata (i.e. the first byte
+ // of the size).
+ Id PtrToId(uint8_t* ptr) const {
+ // For a 64 bit architecture, the id is the offset of the pointer inside
+ // the one and only 4GB block.
+ if (sizeof(void*) == 8) {
+ PERFETTO_DCHECK(blocks_.size() == 1);
+ return blocks_.back().OffsetOf(ptr);
+ }
+
+ // On 32 bit architectures, the size of the pointer is 32-bit so we simply
+ // use the pointer itself as the id.
+ // Double cast needed because, on 64 archs, the compiler complains that we
+ // are losing information.
+ return static_cast<Id>(reinterpret_cast<uintptr_t>(ptr));
+ }
+
+ // THe returned pointer points to the start of the string metadata (i.e. the
+ // first byte of the size).
+ uint8_t* IdToPtr(Id id) const {
+ // For a 64 bit architecture, the pointer is simply the found by taking
+ // the base of the 4GB block and adding the offset given by |id|.
+ if (sizeof(void*) == 8) {
+ PERFETTO_DCHECK(blocks_.size() == 1);
+ return blocks_.back().Get(id);
+ }
+ // On a 32 bit architecture, the pointer is the same as the id.
+ return reinterpret_cast<uint8_t*>(id);
+ }
+
+ // |ptr| should point to the start of the string metadata (i.e. the first byte
+ // of the size).
+ static uint16_t GetSize(uint8_t* ptr) {
+ // The size is simply memcpyed into the byte buffer when writing.
+ uint16_t size;
+ memcpy(&size, ptr, sizeof(uint16_t));
+ return size;
+ }
+
+ // |ptr| should point to the start of the string metadata (i.e. the first byte
+ // of the size).
+ static NullTermStringView GetFromPtr(uint8_t* ptr) {
+ // With the first two bytes being used for the size, the string starts from
+ // byte 3.
+ return NullTermStringView(reinterpret_cast<char*>(&ptr[2]), GetSize(ptr));
+ }
+
+ // The actual memory storing the strings.
+ std::vector<Block> blocks_;
+
+ // Maps hashes of strings to the Id in the string pool.
+ // TODO(lalitm): At some point we should benchmark just using a static
+ // hashtable of 1M elements, we can afford paying a fixed 8MB here
+ std::unordered_map<StringHash, Id> string_index_;
+};
+
+} // namespace trace_processor
+} // namespace perfetto
+
+#endif // SRC_TRACE_PROCESSOR_STRING_POOL_H_
diff --git a/src/trace_processor/string_pool_unittest.cc b/src/trace_processor/string_pool_unittest.cc
new file mode 100644
index 0000000..8a828c3
--- /dev/null
+++ b/src/trace_processor/string_pool_unittest.cc
@@ -0,0 +1,113 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "src/trace_processor/string_pool.h"
+
+#include <random>
+
+#include "gtest/gtest.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace {
+
+TEST(StringPoolTest, EmptyPool) {
+ StringPool pool;
+
+ ASSERT_EQ(pool.Get(0).c_str(), nullptr);
+
+ auto it = pool.CreateIterator();
+ ASSERT_TRUE(it);
+ ASSERT_EQ(it.StringView().c_str(), nullptr);
+ ASSERT_FALSE(++it);
+}
+
+TEST(StringPoolTest, InternAndRetrieve) {
+ StringPool pool;
+
+ static char kString[] = "Test String";
+ auto id = pool.InternString(kString);
+ ASSERT_STREQ(pool.Get(id).c_str(), kString);
+ ASSERT_EQ(pool.Get(id), kString);
+ ASSERT_EQ(id, pool.InternString(kString));
+}
+
+TEST(StringPoolTest, NullPointerHandling) {
+ StringPool pool;
+
+ auto id = pool.InternString(NullTermStringView());
+ ASSERT_EQ(id, 0);
+ ASSERT_EQ(pool.Get(id).c_str(), nullptr);
+}
+
+TEST(StringPoolTest, Iterator) {
+ StringPool pool;
+
+ auto it = pool.CreateIterator();
+ ASSERT_TRUE(it);
+ ASSERT_EQ(it.StringView().c_str(), nullptr);
+ ASSERT_FALSE(++it);
+
+ static char kString[] = "Test String";
+ pool.InternString(kString);
+
+ it = pool.CreateIterator();
+ ASSERT_TRUE(++it);
+ ASSERT_STREQ(it.StringView().c_str(), kString);
+ ASSERT_FALSE(++it);
+}
+
+TEST(StringPoolTest, StressTest) {
+ // First create a buffer with 128MB of random characters.
+ constexpr size_t kBufferSize = 128 * 1024 * 1024;
+ std::minstd_rand0 rnd_engine(0);
+ std::unique_ptr<char[]> buffer(new char[kBufferSize]);
+ for (size_t i = 0; i < kBufferSize; i++)
+ buffer.get()[i] = 'A' + (rnd_engine() % 26);
+
+ // Next create strings of length 0 to 16k in length from this buffer and
+ // intern them, storing their ids.
+ StringPool pool;
+ std::multimap<StringPool::Id, base::StringView> string_map;
+ constexpr uint16_t kMaxStrSize = 16u * 1024u - 1;
+ for (size_t i = 0;;) {
+ size_t length = static_cast<uint64_t>(rnd_engine()) % (kMaxStrSize + 1);
+ if (i + length > kBufferSize)
+ break;
+
+ auto str = base::StringView(&buffer.get()[i], length);
+ string_map.emplace(pool.InternString(str), str);
+ i += length;
+ }
+
+ // Finally, iterate through each string in the string pool, check that all ids
+ // that match in the multimap are equal, and finish by checking we've removed
+ // every item in the multimap.
+ for (auto it = pool.CreateIterator(); it; ++it) {
+ ASSERT_EQ(it.StringView(), pool.Get(it.StringId()));
+
+ auto it_pair = string_map.equal_range(it.StringId());
+ for (auto in_it = it_pair.first; in_it != it_pair.second; ++in_it) {
+ ASSERT_EQ(it.StringView(), in_it->second);
+ }
+ string_map.erase(it_pair.first, it_pair.second);
+ }
+ ASSERT_EQ(string_map.size(), 0);
+}
+
+} // namespace
+} // namespace trace_processor
+} // namespace perfetto
diff --git a/tools/gen_android_bp b/tools/gen_android_bp
index d1c0fc9..286253b 100755
--- a/tools/gen_android_bp
+++ b/tools/gen_android_bp
@@ -72,6 +72,7 @@
# Shared libraries which are directly translated to Android system equivalents.
library_whitelist = [
+ "android.hardware.atrace@1.0",
'android.hardware.health@2.0',
"android.hardware.power.stats@1.0",
'android',