persistent_sample_map.cc 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305
  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. #include "base/metrics/persistent_sample_map.h"
  5. #include "base/check_op.h"
  6. #include "base/containers/contains.h"
  7. #include "base/metrics/histogram_macros.h"
  8. #include "base/metrics/persistent_histogram_allocator.h"
  9. #include "base/notreached.h"
  10. #include "base/numerics/safe_conversions.h"
  11. namespace base {
  12. typedef HistogramBase::Count Count;
  13. typedef HistogramBase::Sample Sample;
  14. namespace {
  15. // An iterator for going through a PersistentSampleMap. The logic here is
  16. // identical to that of SampleMapIterator but with different data structures.
  17. // Changes here likely need to be duplicated there.
  18. class PersistentSampleMapIterator : public SampleCountIterator {
  19. public:
  20. typedef std::map<HistogramBase::Sample, HistogramBase::Count*>
  21. SampleToCountMap;
  22. explicit PersistentSampleMapIterator(const SampleToCountMap& sample_counts);
  23. ~PersistentSampleMapIterator() override;
  24. // SampleCountIterator:
  25. bool Done() const override;
  26. void Next() override;
  27. void Get(HistogramBase::Sample* min,
  28. int64_t* max,
  29. HistogramBase::Count* count) const override;
  30. private:
  31. void SkipEmptyBuckets();
  32. SampleToCountMap::const_iterator iter_;
  33. const SampleToCountMap::const_iterator end_;
  34. };
  35. PersistentSampleMapIterator::PersistentSampleMapIterator(
  36. const SampleToCountMap& sample_counts)
  37. : iter_(sample_counts.begin()),
  38. end_(sample_counts.end()) {
  39. SkipEmptyBuckets();
  40. }
  41. PersistentSampleMapIterator::~PersistentSampleMapIterator() = default;
  42. bool PersistentSampleMapIterator::Done() const {
  43. return iter_ == end_;
  44. }
  45. void PersistentSampleMapIterator::Next() {
  46. DCHECK(!Done());
  47. ++iter_;
  48. SkipEmptyBuckets();
  49. }
  50. void PersistentSampleMapIterator::Get(Sample* min,
  51. int64_t* max,
  52. Count* count) const {
  53. DCHECK(!Done());
  54. if (min)
  55. *min = iter_->first;
  56. if (max)
  57. *max = strict_cast<int64_t>(iter_->first) + 1;
  58. if (count)
  59. *count = *iter_->second;
  60. }
  61. void PersistentSampleMapIterator::SkipEmptyBuckets() {
  62. while (!Done() && *iter_->second == 0) {
  63. ++iter_;
  64. }
  65. }
  66. // This structure holds an entry for a PersistentSampleMap within a persistent
  67. // memory allocator. The "id" must be unique across all maps held by an
  68. // allocator or they will get attached to the wrong sample map.
  69. struct SampleRecord {
  70. // SHA1(SampleRecord): Increment this if structure changes!
  71. static constexpr uint32_t kPersistentTypeId = 0x8FE6A69F + 1;
  72. // Expected size for 32/64-bit check.
  73. static constexpr size_t kExpectedInstanceSize = 16;
  74. uint64_t id; // Unique identifier of owner.
  75. Sample value; // The value for which this record holds a count.
  76. Count count; // The count associated with the above value.
  77. };
  78. } // namespace
  79. PersistentSampleMap::PersistentSampleMap(
  80. uint64_t id,
  81. PersistentHistogramAllocator* allocator,
  82. Metadata* meta)
  83. : HistogramSamples(id, meta), allocator_(allocator) {}
  84. PersistentSampleMap::~PersistentSampleMap() {
  85. if (records_)
  86. records_->Release(this);
  87. }
  88. void PersistentSampleMap::Accumulate(Sample value, Count count) {
  89. #if 0 // TODO(bcwhite) Re-enable efficient version after crbug.com/682680.
  90. *GetOrCreateSampleCountStorage(value) += count;
  91. #else
  92. Count* local_count_ptr = GetOrCreateSampleCountStorage(value);
  93. if (count < 0) {
  94. if (*local_count_ptr < -count)
  95. RecordNegativeSample(SAMPLES_ACCUMULATE_WENT_NEGATIVE, -count);
  96. else
  97. RecordNegativeSample(SAMPLES_ACCUMULATE_NEGATIVE_COUNT, -count);
  98. *local_count_ptr += count;
  99. } else {
  100. Sample old_value = *local_count_ptr;
  101. Sample new_value = old_value + count;
  102. *local_count_ptr = new_value;
  103. if ((new_value >= 0) != (old_value >= 0))
  104. RecordNegativeSample(SAMPLES_ACCUMULATE_OVERFLOW, count);
  105. }
  106. #endif
  107. IncreaseSumAndCount(strict_cast<int64_t>(count) * value, count);
  108. }
  109. Count PersistentSampleMap::GetCount(Sample value) const {
  110. // Have to override "const" to make sure all samples have been loaded before
  111. // being able to know what value to return.
  112. Count* count_pointer =
  113. const_cast<PersistentSampleMap*>(this)->GetSampleCountStorage(value);
  114. return count_pointer ? *count_pointer : 0;
  115. }
  116. Count PersistentSampleMap::TotalCount() const {
  117. // Have to override "const" in order to make sure all samples have been
  118. // loaded before trying to iterate over the map.
  119. const_cast<PersistentSampleMap*>(this)->ImportSamples(-1, true);
  120. Count count = 0;
  121. for (const auto& entry : sample_counts_) {
  122. count += *entry.second;
  123. }
  124. return count;
  125. }
  126. std::unique_ptr<SampleCountIterator> PersistentSampleMap::Iterator() const {
  127. // Have to override "const" in order to make sure all samples have been
  128. // loaded before trying to iterate over the map.
  129. const_cast<PersistentSampleMap*>(this)->ImportSamples(-1, true);
  130. return std::make_unique<PersistentSampleMapIterator>(sample_counts_);
  131. }
  132. // static
  133. PersistentMemoryAllocator::Reference
  134. PersistentSampleMap::GetNextPersistentRecord(
  135. PersistentMemoryAllocator::Iterator& iterator,
  136. uint64_t* sample_map_id) {
  137. const SampleRecord* record = iterator.GetNextOfObject<SampleRecord>();
  138. if (!record)
  139. return 0;
  140. *sample_map_id = record->id;
  141. return iterator.GetAsReference(record);
  142. }
  143. // static
  144. PersistentMemoryAllocator::Reference
  145. PersistentSampleMap::CreatePersistentRecord(
  146. PersistentMemoryAllocator* allocator,
  147. uint64_t sample_map_id,
  148. Sample value) {
  149. SampleRecord* record = allocator->New<SampleRecord>();
  150. if (!record) {
  151. NOTREACHED() << "full=" << allocator->IsFull()
  152. << ", corrupt=" << allocator->IsCorrupt();
  153. return 0;
  154. }
  155. record->id = sample_map_id;
  156. record->value = value;
  157. record->count = 0;
  158. PersistentMemoryAllocator::Reference ref = allocator->GetAsReference(record);
  159. allocator->MakeIterable(ref);
  160. return ref;
  161. }
  162. bool PersistentSampleMap::AddSubtractImpl(SampleCountIterator* iter,
  163. Operator op) {
  164. Sample min;
  165. int64_t max;
  166. Count count;
  167. for (; !iter->Done(); iter->Next()) {
  168. iter->Get(&min, &max, &count);
  169. if (count == 0)
  170. continue;
  171. if (strict_cast<int64_t>(min) + 1 != max)
  172. return false; // SparseHistogram only supports bucket with size 1.
  173. *GetOrCreateSampleCountStorage(min) +=
  174. (op == HistogramSamples::ADD) ? count : -count;
  175. }
  176. return true;
  177. }
  178. Count* PersistentSampleMap::GetSampleCountStorage(Sample value) {
  179. // If |value| is already in the map, just return that.
  180. auto it = sample_counts_.find(value);
  181. if (it != sample_counts_.end())
  182. return it->second;
  183. // Import any new samples from persistent memory looking for the value.
  184. return ImportSamples(value, false);
  185. }
  186. Count* PersistentSampleMap::GetOrCreateSampleCountStorage(Sample value) {
  187. // Get any existing count storage.
  188. Count* count_pointer = GetSampleCountStorage(value);
  189. if (count_pointer)
  190. return count_pointer;
  191. // Create a new record in persistent memory for the value. |records_| will
  192. // have been initialized by the GetSampleCountStorage() call above.
  193. DCHECK(records_);
  194. PersistentMemoryAllocator::Reference ref = records_->CreateNew(value);
  195. if (!ref) {
  196. // If a new record could not be created then the underlying allocator is
  197. // full or corrupt. Instead, allocate the counter from the heap. This
  198. // sample will not be persistent, will not be shared, and will leak...
  199. // but it's better than crashing.
  200. count_pointer = new Count(0);
  201. sample_counts_[value] = count_pointer;
  202. return count_pointer;
  203. }
  204. // A race condition between two independent processes (i.e. two independent
  205. // histogram objects sharing the same sample data) could cause two of the
  206. // above records to be created. The allocator, however, forces a strict
  207. // ordering on iterable objects so use the import method to actually add the
  208. // just-created record. This ensures that all PersistentSampleMap objects
  209. // will always use the same record, whichever was first made iterable.
  210. // Thread-safety within a process where multiple threads use the same
  211. // histogram object is delegated to the controlling histogram object which,
  212. // for sparse histograms, is a lock object.
  213. count_pointer = ImportSamples(value, false);
  214. DCHECK(count_pointer);
  215. return count_pointer;
  216. }
  217. PersistentSampleMapRecords* PersistentSampleMap::GetRecords() {
  218. // The |records_| pointer is lazily fetched from the |allocator_| only on
  219. // first use. Sometimes duplicate histograms are created by race conditions
  220. // and if both were to grab the records object, there would be a conflict.
  221. // Use of a histogram, and thus a call to this method, won't occur until
  222. // after the histogram has been de-dup'd.
  223. if (!records_)
  224. records_ = allocator_->UseSampleMapRecords(id(), this);
  225. return records_;
  226. }
  227. Count* PersistentSampleMap::ImportSamples(Sample until_value,
  228. bool import_everything) {
  229. Count* found_count = nullptr;
  230. PersistentMemoryAllocator::Reference ref;
  231. PersistentSampleMapRecords* records = GetRecords();
  232. while ((ref = records->GetNext()) != 0) {
  233. SampleRecord* record = records->GetAsObject<SampleRecord>(ref);
  234. if (!record)
  235. continue;
  236. DCHECK_EQ(id(), record->id);
  237. // Check if the record's value is already known.
  238. if (!Contains(sample_counts_, record->value)) {
  239. // No: Add it to map of known values.
  240. sample_counts_[record->value] = &record->count;
  241. } else {
  242. // Yes: Ignore it; it's a duplicate caused by a race condition -- see
  243. // code & comment in GetOrCreateSampleCountStorage() for details.
  244. // Check that nothing ever operated on the duplicate record.
  245. DCHECK_EQ(0, record->count);
  246. }
  247. // Check if it's the value being searched for and, if so, keep a pointer
  248. // to return later. Stop here unless everything is being imported.
  249. // Because race conditions can cause multiple records for a single value,
  250. // be sure to return the first one found.
  251. if (record->value == until_value) {
  252. if (!found_count)
  253. found_count = &record->count;
  254. if (!import_everything)
  255. break;
  256. }
  257. }
  258. return found_count;
  259. }
  260. } // namespace base