1// Copyright 2016 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "base/trace_event/memory_usage_estimator.h"
6
7#include <stdlib.h>
8
9#include "base/memory/ptr_util.h"
10#include "base/strings/string16.h"
11#include "build/build_config.h"
12#include "testing/gtest/include/gtest/gtest.h"
13
14#if defined(ARCH_CPU_64_BITS)
15#define EXPECT_EQ_32_64(_, e, a) EXPECT_EQ(e, a)
16#else
17#define EXPECT_EQ_32_64(e, _, a) EXPECT_EQ(e, a)
18#endif
19
20namespace base {
21namespace trace_event {
22
23namespace {
24
25// Test class with predictable memory usage.
26class Data {
27 public:
28  explicit Data(size_t size = 17): size_(size) {
29  }
30
31  size_t size() const { return size_; }
32
33  size_t EstimateMemoryUsage() const {
34    return size_;
35  }
36
37  bool operator < (const Data& other) const {
38    return size_ < other.size_;
39  }
40  bool operator == (const Data& other) const {
41    return size_ == other.size_;
42  }
43
44  struct Hasher {
45    size_t operator () (const Data& data) const {
46      return data.size();
47    }
48  };
49
50 private:
51  size_t size_;
52};
53
54}  // namespace
55
56namespace internal {
57
58// This kills variance of bucket_count across STL implementations.
59template <>
60size_t HashMapBucketCountForTesting<Data>(size_t) {
61  return 10;
62}
63template <>
64size_t HashMapBucketCountForTesting<std::pair<const Data, short>>(size_t) {
65  return 10;
66}
67
68}  // namespace internal
69
70TEST(EstimateMemoryUsageTest, String) {
71  std::string string(777, 'a');
72  EXPECT_EQ(string.capacity() + 1, EstimateMemoryUsage(string));
73}
74
75TEST(EstimateMemoryUsageTest, String16) {
76  string16 string(777, 'a');
77  EXPECT_EQ(sizeof(char16) * (string.capacity() + 1),
78            EstimateMemoryUsage(string));
79}
80
81TEST(EstimateMemoryUsageTest, Arrays) {
82  // std::array
83  {
84    std::array<Data, 10> array;
85    EXPECT_EQ(170u, EstimateMemoryUsage(array));
86  }
87
88  // T[N]
89  {
90    Data array[10];
91    EXPECT_EQ(170u, EstimateMemoryUsage(array));
92  }
93
94  // C array
95  {
96    struct Item {
97      char payload[10];
98    };
99    Item* array = new Item[7];
100    EXPECT_EQ(70u, EstimateMemoryUsage(array, 7));
101    delete[] array;
102  }
103}
104
105TEST(EstimateMemoryUsageTest, UniquePtr) {
106  // Empty
107  {
108    std::unique_ptr<Data> ptr;
109    EXPECT_EQ(0u, EstimateMemoryUsage(ptr));
110  }
111
112  // Not empty
113  {
114    std::unique_ptr<Data> ptr(new Data());
115    EXPECT_EQ_32_64(21u, 25u, EstimateMemoryUsage(ptr));
116  }
117
118  // With a pointer
119  {
120    std::unique_ptr<Data*> ptr(new Data*());
121    EXPECT_EQ(sizeof(void*), EstimateMemoryUsage(ptr));
122  }
123
124  // With an array
125  {
126    struct Item {
127      uint32_t payload[10];
128    };
129    std::unique_ptr<Item[]> ptr(new Item[7]);
130    EXPECT_EQ(280u, EstimateMemoryUsage(ptr, 7));
131  }
132}
133
134TEST(EstimateMemoryUsageTest, Vector) {
135  std::vector<Data> vector;
136  vector.reserve(1000);
137
138  // For an empty vector we should return memory usage of its buffer
139  size_t capacity = vector.capacity();
140  size_t expected_size = capacity * sizeof(Data);
141  EXPECT_EQ(expected_size, EstimateMemoryUsage(vector));
142
143  // If vector is not empty, its size should also include memory usages
144  // of all elements.
145  for (size_t i = 0; i != capacity / 2; ++i) {
146    vector.push_back(Data(i));
147    expected_size += EstimateMemoryUsage(vector.back());
148  }
149  EXPECT_EQ(expected_size, EstimateMemoryUsage(vector));
150}
151
152TEST(EstimateMemoryUsageTest, List) {
153  struct POD {
154    short data;
155  };
156  std::list<POD> list;
157  for (int i = 0; i != 1000; ++i) {
158    list.push_back(POD());
159  }
160  EXPECT_EQ_32_64(12000u, 24000u, EstimateMemoryUsage(list));
161}
162
163TEST(EstimateMemoryUsageTest, Set) {
164  std::set<std::pair<int, Data>> set;
165  for (int i = 0; i != 1000; ++i) {
166    set.insert({i, Data(i)});
167  }
168  EXPECT_EQ_32_64(523500u, 547500u, EstimateMemoryUsage(set));
169}
170
171TEST(EstimateMemoryUsageTest, MultiSet) {
172  std::multiset<bool> set;
173  for (int i = 0; i != 1000; ++i) {
174    set.insert((i & 1) != 0);
175  }
176  EXPECT_EQ_32_64(16000u, 32000u, EstimateMemoryUsage(set));
177}
178
179TEST(EstimateMemoryUsageTest, Map) {
180  std::map<Data, int> map;
181  for (int i = 0; i != 1000; ++i) {
182    map.insert({Data(i), i});
183  }
184  EXPECT_EQ_32_64(523500u, 547500u, EstimateMemoryUsage(map));
185}
186
187TEST(EstimateMemoryUsageTest, MultiMap) {
188  std::multimap<char, Data> map;
189  for (int i = 0; i != 1000; ++i) {
190    map.insert({static_cast<char>(i), Data(i)});
191  }
192  EXPECT_EQ_32_64(523500u, 547500u, EstimateMemoryUsage(map));
193}
194
195TEST(EstimateMemoryUsageTest, UnorderedSet) {
196  std::unordered_set<Data, Data::Hasher> set;
197  for (int i = 0; i != 1000; ++i) {
198    set.insert(Data(i));
199  }
200  EXPECT_EQ_32_64(511540u, 523580u, EstimateMemoryUsage(set));
201}
202
203TEST(EstimateMemoryUsageTest, UnorderedMultiSet) {
204  std::unordered_multiset<Data, Data::Hasher> set;
205  for (int i = 0; i != 500; ++i) {
206    set.insert(Data(i));
207    set.insert(Data(i));
208  }
209  EXPECT_EQ_32_64(261540u, 273580u, EstimateMemoryUsage(set));
210}
211
212TEST(EstimateMemoryUsageTest, UnorderedMap) {
213  std::unordered_map<Data, short, Data::Hasher> map;
214  for (int i = 0; i != 1000; ++i) {
215    map.insert({Data(i), static_cast<short>(i)});
216  }
217  EXPECT_EQ_32_64(515540u, 531580u, EstimateMemoryUsage(map));
218}
219
220TEST(EstimateMemoryUsageTest, UnorderedMultiMap) {
221  std::unordered_multimap<Data, short, Data::Hasher> map;
222  for (int i = 0; i != 1000; ++i) {
223    map.insert({Data(i), static_cast<short>(i)});
224  }
225  EXPECT_EQ_32_64(515540u, 531580u, EstimateMemoryUsage(map));
226}
227
228TEST(EstimateMemoryUsageTest, Deque) {
229  std::deque<Data> deque;
230
231  // Pick a large value so that platform-specific accounting
232  // for deque's blocks is small compared to usage of all items.
233  constexpr size_t kDataSize = 100000;
234  for (int i = 0; i != 1500; ++i) {
235    deque.push_back(Data(kDataSize));
236  }
237
238  // Compare against a reasonable minimum (i.e. no overhead).
239  size_t min_expected_usage = deque.size() * (sizeof(Data) + kDataSize);
240  EXPECT_LE(min_expected_usage, EstimateMemoryUsage(deque));
241}
242
243}  // namespace trace_event
244}  // namespace base
245