trace_processor: move stringpool to new containers folder

This allows us to remove the ugly "common" target which has existed for
a long time.

Context: go/perfetto-tp-refactor
Bug: 135177627
Change-Id: I6dd03c22f0b42f818a9a53ad9bfa1e7f382a05f4
diff --git a/src/trace_processor/containers/BUILD.gn b/src/trace_processor/containers/BUILD.gn
index c6c5d73..32e0d28 100644
--- a/src/trace_processor/containers/BUILD.gn
+++ b/src/trace_processor/containers/BUILD.gn
@@ -20,15 +20,18 @@
     "bit_vector.h",
     "bit_vector_iterators.cc",
     "bit_vector_iterators.h",
+    "null_term_string_view.h",
     "row_map.cc",
     "row_map.h",
     "sparse_vector.h",
+    "string_pool.cc",
+    "string_pool.h",
   ]
   deps = [
-    "../:common",
     "../../../gn:default_deps",
     "../../../include/perfetto/base",
     "../../../include/perfetto/ext/base",
+    "../../../include/perfetto/protozero",
   ]
 }
 
@@ -36,8 +39,10 @@
   testonly = true
   sources = [
     "bit_vector_unittest.cc",
+    "null_term_string_view_unittest.cc",
     "row_map_unittest.cc",
     "sparse_vector_unittest.cc",
+    "string_pool_unittest.cc",
   ]
   deps = [
     ":containers",
diff --git a/src/trace_processor/containers/null_term_string_view.h b/src/trace_processor/containers/null_term_string_view.h
new file mode 100644
index 0000000..5ae5a29
--- /dev/null
+++ b/src/trace_processor/containers/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_CONTAINERS_NULL_TERM_STRING_VIEW_H_
+#define SRC_TRACE_PROCESSOR_CONTAINERS_NULL_TERM_STRING_VIEW_H_
+
+#include "perfetto/ext/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_CONTAINERS_NULL_TERM_STRING_VIEW_H_
diff --git a/src/trace_processor/containers/null_term_string_view_unittest.cc b/src/trace_processor/containers/null_term_string_view_unittest.cc
new file mode 100644
index 0000000..eb4d23f
--- /dev/null
+++ b/src/trace_processor/containers/null_term_string_view_unittest.cc
@@ -0,0 +1,69 @@
+/*
+ * 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/containers/null_term_string_view.h"
+
+#include "test/gtest_and_gmock.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("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("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("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("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/containers/string_pool.cc b/src/trace_processor/containers/string_pool.cc
new file mode 100644
index 0000000..020de1c
--- /dev/null
+++ b/src/trace_processor/containers/string_pool.cc
@@ -0,0 +1,150 @@
+/*
+ * 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/containers/string_pool.h"
+
+#include <limits>
+
+#include "perfetto/base/logging.h"
+#include "perfetto/ext/base/utils.h"
+
+namespace perfetto {
+namespace trace_processor {
+
+StringPool::StringPool(size_t block_size_bytes)
+    : block_size_bytes_(block_size_bytes > 0 ? block_size_bytes
+                                             : kDefaultBlockSize) {
+  blocks_.emplace_back(block_size_bytes_);
+
+  // 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) {
+  // Try and find enough space in the current block for the string and the
+  // metadata (varint-encoded size + the string data + the null terminator).
+  const uint8_t* ptr = blocks_.back().TryInsert(str);
+  if (PERFETTO_UNLIKELY(!ptr)) {
+    // This means the block did not have enough space. This should only happen
+    // if the block size is small.
+    PERFETTO_CHECK(block_size_bytes_ <= std::numeric_limits<uint32_t>::max());
+
+    // Add a new block to store the data. If the string is larger that the
+    // default block size, add a bigger block exlusively for this string.
+    if (str.size() + kMaxMetadataSize > block_size_bytes_) {
+      blocks_.emplace_back(str.size() +
+                           base::AlignUp<base::kPageSize>(kMaxMetadataSize));
+    } else {
+      blocks_.emplace_back(block_size_bytes_);
+    }
+
+    // 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;
+}
+
+const uint8_t* StringPool::Block::TryInsert(base::StringView str) {
+  auto str_size = str.size();
+  size_t max_pos = static_cast<size_t>(pos_) + str_size + kMaxMetadataSize;
+  if (max_pos > size_)
+    return nullptr;
+
+  // Ensure that we commit up until the end of the string to memory.
+  mem_.EnsureCommitted(max_pos);
+
+  // Get where we should start writing this string.
+  uint8_t* begin = Get(pos_);
+
+  // First write the size of the string using varint encoding.
+  uint8_t* end = protozero::proto_utils::WriteVarInt(str_size, begin);
+
+  // Next the string itself.
+  if (PERFETTO_LIKELY(str_size > 0)) {
+    memcpy(end, str.data(), str_size);
+    end += str_size;
+  }
+
+  // Finally add a null terminator.
+  *(end++) = '\0';
+
+  // Update the end of the block and return the pointer to the string.
+  pos_ = OffsetOf(end);
+
+  return begin;
+}
+
+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.
+  uint32_t str_size = 0;
+  const uint8_t* ptr = block.Get(block_offset_);
+  ptr = ReadSize(ptr, &str_size);
+  ptr += str_size + 1;
+  block_offset_ = block.OffsetOf(ptr);
+
+  // If we're out of bounds for this block, go to 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/containers/string_pool.h b/src/trace_processor/containers/string_pool.h
new file mode 100644
index 0000000..bdfc39f
--- /dev/null
+++ b/src/trace_processor/containers/string_pool.h
@@ -0,0 +1,253 @@
+/*
+ * 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_CONTAINERS_STRING_POOL_H_
+#define SRC_TRACE_PROCESSOR_CONTAINERS_STRING_POOL_H_
+
+#include <stddef.h>
+#include <stdint.h>
+
+#include <unordered_map>
+#include <vector>
+
+#include "perfetto/ext/base/optional.h"
+#include "perfetto/ext/base/paged_memory.h"
+#include "perfetto/protozero/proto_utils.h"
+#include "src/trace_processor/containers/null_term_string_view.h"
+
+namespace perfetto {
+namespace trace_processor {
+
+// 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.
+constexpr size_t kDefaultBlockSize =
+    sizeof(void*) == 8
+        ? static_cast<size_t>(4ull * 1024ull * 1024ull * 1024ull) /* 4GB */
+        : 32ull * 1024ull * 1024ull /* 32MB */;
+
+// Interns strings in a string pool and hands out compact StringIds which can
+// be used to retrieve the string in O(1).
+class StringPool {
+ public:
+  struct Id {
+    Id() = default;
+    constexpr Id(uint32_t i) : id(i) {}
+
+    bool operator==(const Id& other) const { return other.id == id; }
+    bool operator!=(const Id& other) const { return !(other == *this); }
+    bool operator<(const Id& other) const { return id < other.id; }
+
+    bool is_null() const { return id == 0u; }
+
+    uint32_t id;
+  };
+
+  // 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(size_t block_size_bytes = kDefaultBlockSize);
+  ~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 Id(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);
+  }
+
+  base::Optional<Id> GetId(base::StringView str) const {
+    if (str.data() == nullptr)
+      return Id(0u);
+
+    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 base::nullopt;
+  }
+
+  NullTermStringView Get(Id id) const {
+    if (id.id == 0)
+      return NullTermStringView();
+    return GetFromPtr(IdToPtr(id));
+  }
+
+  Iterator CreateIterator() const { return Iterator(this); }
+
+  size_t size() const { return string_index_.size(); }
+
+ private:
+  using StringHash = uint64_t;
+
+  struct Block {
+    explicit Block(size_t size)
+        : mem_(base::PagedMemory::Allocate(size,
+                                           base::PagedMemory::kDontCommit)),
+          size_(size) {}
+    ~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;
+    }
+
+    const uint8_t* TryInsert(base::StringView str);
+
+    uint32_t OffsetOf(const uint8_t* ptr) const {
+      PERFETTO_DCHECK(Get(0) < ptr &&
+                      ptr < Get(static_cast<uint32_t>(size_ - 1)));
+      return static_cast<uint32_t>(ptr - Get(0));
+    }
+
+    uint32_t pos() const { return pos_; }
+
+   private:
+    base::PagedMemory mem_;
+    uint32_t pos_ = 0;
+    size_t size_ = 0;
+  };
+
+  friend class Iterator;
+
+  // Number of bytes to reserve for size and null terminator.
+  // This is the upper limit on metadata size: 5 bytes for max uint32,
+  // plus 1 byte for null terminator. The actual size may be lower.
+  static constexpr uint8_t kMaxMetadataSize = 6;
+
+  // 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(const 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 Id(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 Id(static_cast<uint32_t>(reinterpret_cast<uintptr_t>(ptr)));
+  }
+
+  // The returned pointer points to the start of the string metadata (i.e. the
+  // first byte of the size).
+  const 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.id);
+    }
+    // On a 32 bit architecture, the pointer is the same as the id.
+    return reinterpret_cast<uint8_t*>(id.id);
+  }
+
+  // |ptr| should point to the start of the string metadata (i.e. the first byte
+  // of the size).
+  // Returns pointer to the start of the string.
+  static const uint8_t* ReadSize(const uint8_t* ptr, uint32_t* size) {
+    uint64_t value = 0;
+    const uint8_t* str_ptr = protozero::proto_utils::ParseVarInt(
+        ptr, ptr + kMaxMetadataSize, &value);
+    PERFETTO_DCHECK(str_ptr != ptr);
+    PERFETTO_DCHECK(value < std::numeric_limits<uint32_t>::max());
+    *size = static_cast<uint32_t>(value);
+    return str_ptr;
+  }
+
+  // |ptr| should point to the start of the string metadata (i.e. the first byte
+  // of the size).
+  static NullTermStringView GetFromPtr(const uint8_t* ptr) {
+    uint32_t size = 0;
+    const uint8_t* str_ptr = ReadSize(ptr, &size);
+    return NullTermStringView(reinterpret_cast<const char*>(str_ptr), size);
+  }
+
+  // The minimum size of a new block. A larger block may be created if a string
+  // is added that is larger than this size.
+  size_t block_size_bytes_;
+
+  // 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
+
+namespace std {
+
+template <>
+struct hash< ::perfetto::trace_processor::StringPool::Id> {
+  using argument_type = ::perfetto::trace_processor::StringPool::Id;
+  using result_type = size_t;
+
+  result_type operator()(const argument_type& r) const {
+    return std::hash<uint32_t>{}(r.id);
+  }
+};
+
+}  // namespace std
+
+#endif  // SRC_TRACE_PROCESSOR_CONTAINERS_STRING_POOL_H_
diff --git a/src/trace_processor/containers/string_pool_unittest.cc b/src/trace_processor/containers/string_pool_unittest.cc
new file mode 100644
index 0000000..0144d7c
--- /dev/null
+++ b/src/trace_processor/containers/string_pool_unittest.cc
@@ -0,0 +1,148 @@
+/*
+ * 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/containers/string_pool.h"
+
+#include <random>
+
+#include "test/gtest_and_gmock.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, 0u);
+  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, ConstIterator) {
+  StringPool pool;
+  static char kString[] = "Test String";
+  pool.InternString(kString);
+
+  const StringPool& const_pool = pool;
+
+  auto it = const_pool.CreateIterator();
+  ASSERT_TRUE(it);
+  ASSERT_TRUE(++it);
+  ASSERT_STREQ(it.StringView().c_str(), kString);
+  ASSERT_FALSE(++it);
+}
+
+TEST(StringPoolTest, StressTest) {
+  // First create a buffer with 8MB of random characters.
+  constexpr size_t kBufferSize = 8 * 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(), 0u);
+}
+
+TEST(StringPoolTest, BigString) {
+  constexpr size_t kBigStringSize = 33 * 1024 * 1024;
+  std::unique_ptr<char[]> str1(new char[kBigStringSize + 1]);
+  std::unique_ptr<char[]> str2(new char[kBigStringSize + 1]);
+  for (size_t i = 0; i < kBigStringSize; i++) {
+    str1.get()[i] = 'A' + static_cast<char>(i % 32);
+    str2.get()[i] = 'A' + static_cast<char>((i + 7) % 32);
+  }
+  str1.get()[kBigStringSize] = '\0';
+  str2.get()[kBigStringSize] = '\0';
+
+  StringPool pool;
+  StringPool::Id id1 =
+      pool.InternString(base::StringView(str1.get(), kBigStringSize));
+  StringPool::Id id2 =
+      pool.InternString(base::StringView(str2.get(), kBigStringSize));
+
+  ASSERT_EQ(str1.get(), pool.Get(id1));
+  ASSERT_EQ(str2.get(), pool.Get(id2));
+}
+
+}  // namespace
+}  // namespace trace_processor
+}  // namespace perfetto