sample_vector.cc 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544
  1. // Copyright (c) 2012 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/sample_vector.h"
  5. #include "base/check_op.h"
  6. #include "base/lazy_instance.h"
  7. #include "base/memory/ptr_util.h"
  8. #include "base/metrics/persistent_memory_allocator.h"
  9. #include "base/notreached.h"
  10. #include "base/numerics/safe_conversions.h"
  11. #include "base/strings/stringprintf.h"
  12. #include "base/synchronization/lock.h"
  13. #include "base/threading/platform_thread.h"
  14. // This SampleVector makes use of the single-sample embedded in the base
  15. // HistogramSamples class. If the count is non-zero then there is guaranteed
  16. // (within the bounds of "eventual consistency") to be no allocated external
  17. // storage. Once the full counts storage is allocated, the single-sample must
  18. // be extracted and disabled.
  19. namespace base {
  20. typedef HistogramBase::Count Count;
  21. typedef HistogramBase::Sample Sample;
  22. SampleVectorBase::SampleVectorBase(uint64_t id,
  23. Metadata* meta,
  24. const BucketRanges* bucket_ranges)
  25. : HistogramSamples(id, meta), bucket_ranges_(bucket_ranges) {
  26. CHECK_GE(bucket_ranges_->bucket_count(), 1u);
  27. }
  28. SampleVectorBase::SampleVectorBase(uint64_t id,
  29. std::unique_ptr<Metadata> meta,
  30. const BucketRanges* bucket_ranges)
  31. : HistogramSamples(id, std::move(meta)), bucket_ranges_(bucket_ranges) {
  32. CHECK_GE(bucket_ranges_->bucket_count(), 1u);
  33. }
  34. SampleVectorBase::~SampleVectorBase() = default;
  35. void SampleVectorBase::Accumulate(Sample value, Count count) {
  36. const size_t bucket_index = GetBucketIndex(value);
  37. // Handle the single-sample case.
  38. if (!counts()) {
  39. // Try to accumulate the parameters into the single-count entry.
  40. if (AccumulateSingleSample(value, count, bucket_index)) {
  41. // A race condition could lead to a new single-sample being accumulated
  42. // above just after another thread executed the MountCountsStorage below.
  43. // Since it is mounted, it could be mounted elsewhere and have values
  44. // written to it. It's not allowed to have both a single-sample and
  45. // entries in the counts array so move the single-sample.
  46. if (counts())
  47. MoveSingleSampleToCounts();
  48. return;
  49. }
  50. // Need real storage to store both what was in the single-sample plus the
  51. // parameter information.
  52. MountCountsStorageAndMoveSingleSample();
  53. }
  54. // Handle the multi-sample case.
  55. Count new_value =
  56. subtle::NoBarrier_AtomicIncrement(&counts()[bucket_index], count);
  57. IncreaseSumAndCount(strict_cast<int64_t>(count) * value, count);
  58. // TODO(bcwhite) Remove after crbug.com/682680.
  59. Count old_value = new_value - count;
  60. if ((new_value >= 0) != (old_value >= 0) && count > 0)
  61. RecordNegativeSample(SAMPLES_ACCUMULATE_OVERFLOW, count);
  62. }
  63. Count SampleVectorBase::GetCount(Sample value) const {
  64. return GetCountAtIndex(GetBucketIndex(value));
  65. }
  66. Count SampleVectorBase::TotalCount() const {
  67. // Handle the single-sample case.
  68. SingleSample sample = single_sample().Load();
  69. if (sample.count != 0)
  70. return sample.count;
  71. // Handle the multi-sample case.
  72. if (counts() || MountExistingCountsStorage()) {
  73. Count count = 0;
  74. size_t size = counts_size();
  75. const HistogramBase::AtomicCount* counts_array = counts();
  76. for (size_t i = 0; i < size; ++i) {
  77. count += subtle::NoBarrier_Load(&counts_array[i]);
  78. }
  79. return count;
  80. }
  81. // And the no-value case.
  82. return 0;
  83. }
  84. Count SampleVectorBase::GetCountAtIndex(size_t bucket_index) const {
  85. DCHECK(bucket_index < counts_size());
  86. // Handle the single-sample case.
  87. SingleSample sample = single_sample().Load();
  88. if (sample.count != 0)
  89. return sample.bucket == bucket_index ? sample.count : 0;
  90. // Handle the multi-sample case.
  91. if (counts() || MountExistingCountsStorage())
  92. return subtle::NoBarrier_Load(&counts()[bucket_index]);
  93. // And the no-value case.
  94. return 0;
  95. }
  96. std::unique_ptr<SampleCountIterator> SampleVectorBase::Iterator() const {
  97. // Handle the single-sample case.
  98. SingleSample sample = single_sample().Load();
  99. if (sample.count != 0) {
  100. return std::make_unique<SingleSampleIterator>(
  101. bucket_ranges_->range(sample.bucket),
  102. bucket_ranges_->range(sample.bucket + 1), sample.count, sample.bucket);
  103. }
  104. // Handle the multi-sample case.
  105. if (counts() || MountExistingCountsStorage()) {
  106. return std::make_unique<SampleVectorIterator>(counts(), counts_size(),
  107. bucket_ranges_);
  108. }
  109. // And the no-value case.
  110. return std::make_unique<SampleVectorIterator>(nullptr, 0, bucket_ranges_);
  111. }
  112. bool SampleVectorBase::AddSubtractImpl(SampleCountIterator* iter,
  113. HistogramSamples::Operator op) {
  114. // Stop now if there's nothing to do.
  115. if (iter->Done())
  116. return true;
  117. // Get the first value and its index.
  118. HistogramBase::Sample min;
  119. int64_t max;
  120. HistogramBase::Count count;
  121. iter->Get(&min, &max, &count);
  122. size_t dest_index = GetBucketIndex(min);
  123. // The destination must be a superset of the source meaning that though the
  124. // incoming ranges will find an exact match, the incoming bucket-index, if
  125. // it exists, may be offset from the destination bucket-index. Calculate
  126. // that offset of the passed iterator; there are are no overflow checks
  127. // because 2's compliment math will work it out in the end.
  128. //
  129. // Because GetBucketIndex() always returns the same true or false result for
  130. // a given iterator object, |index_offset| is either set here and used below,
  131. // or never set and never used. The compiler doesn't know this, though, which
  132. // is why it's necessary to initialize it to something.
  133. size_t index_offset = 0;
  134. size_t iter_index;
  135. if (iter->GetBucketIndex(&iter_index))
  136. index_offset = dest_index - iter_index;
  137. if (dest_index >= counts_size())
  138. return false;
  139. // Post-increment. Information about the current sample is not available
  140. // after this point.
  141. iter->Next();
  142. // Single-value storage is possible if there is no counts storage and the
  143. // retrieved entry is the only one in the iterator.
  144. if (!counts()) {
  145. if (iter->Done()) {
  146. // Don't call AccumulateSingleSample because that updates sum and count
  147. // which was already done by the caller of this method.
  148. if (single_sample().Accumulate(
  149. dest_index, op == HistogramSamples::ADD ? count : -count)) {
  150. // Handle race-condition that mounted counts storage between above and
  151. // here.
  152. if (counts())
  153. MoveSingleSampleToCounts();
  154. return true;
  155. }
  156. }
  157. // The counts storage will be needed to hold the multiple incoming values.
  158. MountCountsStorageAndMoveSingleSample();
  159. }
  160. // Go through the iterator and add the counts into correct bucket.
  161. while (true) {
  162. // Ensure that the sample's min/max match the ranges min/max.
  163. if (min != bucket_ranges_->range(dest_index) ||
  164. max != bucket_ranges_->range(dest_index + 1)) {
  165. NOTREACHED() << "sample=" << min << "," << max
  166. << "; range=" << bucket_ranges_->range(dest_index) << ","
  167. << bucket_ranges_->range(dest_index + 1);
  168. return false;
  169. }
  170. // Sample's bucket matches exactly. Adjust count.
  171. subtle::NoBarrier_AtomicIncrement(
  172. &counts()[dest_index], op == HistogramSamples::ADD ? count : -count);
  173. // Advance to the next iterable sample. See comments above for how
  174. // everything works.
  175. if (iter->Done())
  176. return true;
  177. iter->Get(&min, &max, &count);
  178. if (iter->GetBucketIndex(&iter_index)) {
  179. // Destination bucket is a known offset from the source bucket.
  180. dest_index = iter_index + index_offset;
  181. } else {
  182. // Destination bucket has to be determined anew each time.
  183. dest_index = GetBucketIndex(min);
  184. }
  185. if (dest_index >= counts_size())
  186. return false;
  187. iter->Next();
  188. }
  189. }
  190. // Uses simple binary search or calculates the index directly if it's an "exact"
  191. // linear histogram. This is very general, but there are better approaches if we
  192. // knew that the buckets were linearly distributed.
  193. size_t SampleVectorBase::GetBucketIndex(Sample value) const {
  194. size_t bucket_count = bucket_ranges_->bucket_count();
  195. CHECK_GE(bucket_count, 1u);
  196. CHECK_GE(value, bucket_ranges_->range(0));
  197. CHECK_LT(value, bucket_ranges_->range(bucket_count));
  198. // For "exact" linear histograms, e.g. bucket_count = maximum + 1, their
  199. // minimum is 1 and bucket sizes are 1. Thus, we don't need to binary search
  200. // the bucket index. The bucket index for bucket |value| is just the |value|.
  201. Sample maximum = bucket_ranges_->range(bucket_count - 1);
  202. if (maximum == static_cast<Sample>(bucket_count - 1)) {
  203. // |value| is in the underflow bucket.
  204. if (value < 1)
  205. return 0;
  206. // |value| is in the overflow bucket.
  207. if (value > maximum)
  208. return bucket_count - 1;
  209. return static_cast<size_t>(value);
  210. }
  211. size_t under = 0;
  212. size_t over = bucket_count;
  213. size_t mid;
  214. do {
  215. DCHECK_GE(over, under);
  216. mid = under + (over - under)/2;
  217. if (mid == under)
  218. break;
  219. if (bucket_ranges_->range(mid) <= value)
  220. under = mid;
  221. else
  222. over = mid;
  223. } while (true);
  224. DCHECK_LE(bucket_ranges_->range(mid), value);
  225. CHECK_GT(bucket_ranges_->range(mid + 1), value);
  226. return mid;
  227. }
  228. void SampleVectorBase::MoveSingleSampleToCounts() {
  229. DCHECK(counts());
  230. // Disable the single-sample since there is now counts storage for the data.
  231. SingleSample sample = single_sample().Extract(/*disable=*/true);
  232. // Stop here if there is no "count" as trying to find the bucket index of
  233. // an invalid (including zero) "value" will crash.
  234. if (sample.count == 0)
  235. return;
  236. // Move the value into storage. Sum and redundant-count already account
  237. // for this entry so no need to call IncreaseSumAndCount().
  238. subtle::NoBarrier_AtomicIncrement(&counts()[sample.bucket], sample.count);
  239. }
  240. void SampleVectorBase::MountCountsStorageAndMoveSingleSample() {
  241. // There are many SampleVector objects and the lock is needed very
  242. // infrequently (just when advancing from single-sample to multi-sample) so
  243. // define a single, global lock that all can use. This lock only prevents
  244. // concurrent entry into the code below; access and updates to |counts_|
  245. // still requires atomic operations.
  246. static LazyInstance<Lock>::Leaky counts_lock = LAZY_INSTANCE_INITIALIZER;
  247. if (!counts_.load(std::memory_order_relaxed)) {
  248. AutoLock lock(counts_lock.Get());
  249. if (!counts_.load(std::memory_order_relaxed)) {
  250. // Create the actual counts storage while the above lock is acquired.
  251. HistogramBase::Count* counts = CreateCountsStorageWhileLocked();
  252. DCHECK(counts);
  253. // Point |counts_| to the newly created storage. This is done while
  254. // locked to prevent possible concurrent calls to CreateCountsStorage
  255. // but, between that call and here, other threads could notice the
  256. // existence of the storage and race with this to set_counts(). That's
  257. // okay because (a) it's atomic and (b) it always writes the same value.
  258. set_counts(counts);
  259. }
  260. }
  261. // Move any single-sample into the newly mounted storage.
  262. MoveSingleSampleToCounts();
  263. }
  264. SampleVector::SampleVector(const BucketRanges* bucket_ranges)
  265. : SampleVector(0, bucket_ranges) {}
  266. SampleVector::SampleVector(uint64_t id, const BucketRanges* bucket_ranges)
  267. : SampleVectorBase(id, std::make_unique<LocalMetadata>(), bucket_ranges) {}
  268. SampleVector::~SampleVector() = default;
  269. bool SampleVector::MountExistingCountsStorage() const {
  270. // There is never any existing storage other than what is already in use.
  271. return counts() != nullptr;
  272. }
  273. std::string SampleVector::GetAsciiHeader(StringPiece histogram_name,
  274. int32_t flags) const {
  275. Count sample_count = TotalCount();
  276. std::string output;
  277. StringAppendF(&output, "Histogram: %.*s recorded %d samples",
  278. static_cast<int>(histogram_name.size()), histogram_name.data(),
  279. sample_count);
  280. if (sample_count == 0) {
  281. DCHECK_EQ(sum(), 0);
  282. } else {
  283. double mean = static_cast<float>(sum()) / sample_count;
  284. StringAppendF(&output, ", mean = %.1f", mean);
  285. }
  286. if (flags)
  287. StringAppendF(&output, " (flags = 0x%x)", flags);
  288. return output;
  289. }
  290. std::string SampleVector::GetAsciiBody() const {
  291. Count sample_count = TotalCount();
  292. // Prepare to normalize graphical rendering of bucket contents.
  293. double max_size = 0;
  294. double scaling_factor = 1;
  295. max_size = GetPeakBucketSize();
  296. // Scale histogram bucket counts to take at most 72 characters.
  297. // Note: Keep in sync w/ kLineLength histogram_samples.cc
  298. const double kLineLength = 72;
  299. if (max_size > kLineLength)
  300. scaling_factor = kLineLength / max_size;
  301. // Calculate largest print width needed for any of our bucket range displays.
  302. size_t print_width = 1;
  303. for (uint32_t i = 0; i < bucket_count(); ++i) {
  304. if (GetCountAtIndex(i)) {
  305. size_t width =
  306. GetSimpleAsciiBucketRange(bucket_ranges()->range(i)).size() + 1;
  307. if (width > print_width)
  308. print_width = width;
  309. }
  310. }
  311. int64_t remaining = sample_count;
  312. int64_t past = 0;
  313. std::string output;
  314. // Output the actual histogram graph.
  315. for (uint32_t i = 0; i < bucket_count(); ++i) {
  316. Count current = GetCountAtIndex(i);
  317. remaining -= current;
  318. std::string range = GetSimpleAsciiBucketRange(bucket_ranges()->range(i));
  319. output.append(range);
  320. for (size_t j = 0; range.size() + j < print_width + 1; ++j)
  321. output.push_back(' ');
  322. if (0 == current && i < bucket_count() - 1 && 0 == GetCountAtIndex(i + 1)) {
  323. while (i < bucket_count() - 1 && 0 == GetCountAtIndex(i + 1)) {
  324. ++i;
  325. }
  326. output.append("... \n");
  327. continue; // No reason to plot emptiness.
  328. }
  329. Count current_size = round(current * scaling_factor);
  330. WriteAsciiBucketGraph(current_size, kLineLength, &output);
  331. WriteAsciiBucketContext(past, current, remaining, i, &output);
  332. output.append("\n");
  333. past += current;
  334. }
  335. DCHECK_EQ(sample_count, past);
  336. return output;
  337. }
  338. double SampleVector::GetPeakBucketSize() const {
  339. Count max = 0;
  340. for (uint32_t i = 0; i < bucket_count(); ++i) {
  341. Count current = GetCountAtIndex(i);
  342. if (current > max)
  343. max = current;
  344. }
  345. return max;
  346. }
  347. void SampleVector::WriteAsciiBucketContext(int64_t past,
  348. Count current,
  349. int64_t remaining,
  350. uint32_t current_bucket_index,
  351. std::string* output) const {
  352. double scaled_sum = (past + current + remaining) / 100.0;
  353. WriteAsciiBucketValue(current, scaled_sum, output);
  354. if (0 < current_bucket_index) {
  355. double percentage = past / scaled_sum;
  356. StringAppendF(output, " {%3.1f%%}", percentage);
  357. }
  358. }
  359. HistogramBase::AtomicCount* SampleVector::CreateCountsStorageWhileLocked() {
  360. local_counts_.resize(counts_size());
  361. return &local_counts_[0];
  362. }
  363. PersistentSampleVector::PersistentSampleVector(
  364. uint64_t id,
  365. const BucketRanges* bucket_ranges,
  366. Metadata* meta,
  367. const DelayedPersistentAllocation& counts)
  368. : SampleVectorBase(id, meta, bucket_ranges), persistent_counts_(counts) {
  369. // Only mount the full storage if the single-sample has been disabled.
  370. // Otherwise, it is possible for this object instance to start using (empty)
  371. // storage that was created incidentally while another instance continues to
  372. // update to the single sample. This "incidental creation" can happen because
  373. // the memory is a DelayedPersistentAllocation which allows multiple memory
  374. // blocks within it and applies an all-or-nothing approach to the allocation.
  375. // Thus, a request elsewhere for one of the _other_ blocks would make _this_
  376. // block available even though nothing has explicitly requested it.
  377. //
  378. // Note that it's not possible for the ctor to mount existing storage and
  379. // move any single-sample to it because sometimes the persistent memory is
  380. // read-only. Only non-const methods (which assume that memory is read/write)
  381. // can do that.
  382. if (single_sample().IsDisabled()) {
  383. bool success = MountExistingCountsStorage();
  384. DCHECK(success);
  385. }
  386. }
  387. PersistentSampleVector::~PersistentSampleVector() = default;
  388. bool PersistentSampleVector::MountExistingCountsStorage() const {
  389. // There is no early exit if counts is not yet mounted because, given that
  390. // this is a virtual function, it's more efficient to do that at the call-
  391. // site. There is no danger, however, should this get called anyway (perhaps
  392. // because of a race condition) because at worst the |counts_| value would
  393. // be over-written (in an atomic manner) with the exact same address.
  394. if (!persistent_counts_.reference())
  395. return false; // Nothing to mount.
  396. // Mount the counts array in position.
  397. set_counts(
  398. static_cast<HistogramBase::AtomicCount*>(persistent_counts_.Get()));
  399. // The above shouldn't fail but can if the data is corrupt or incomplete.
  400. return counts() != nullptr;
  401. }
  402. HistogramBase::AtomicCount*
  403. PersistentSampleVector::CreateCountsStorageWhileLocked() {
  404. void* mem = persistent_counts_.Get();
  405. if (!mem) {
  406. // The above shouldn't fail but can if Bad Things(tm) are occurring in the
  407. // persistent allocator. Crashing isn't a good option so instead just
  408. // allocate something from the heap and return that. There will be no
  409. // sharing or persistence but worse things are already happening.
  410. return new HistogramBase::AtomicCount[counts_size()];
  411. }
  412. return static_cast<HistogramBase::AtomicCount*>(mem);
  413. }
  414. SampleVectorIterator::SampleVectorIterator(
  415. const std::vector<HistogramBase::AtomicCount>* counts,
  416. const BucketRanges* bucket_ranges)
  417. : counts_(&(*counts)[0]),
  418. counts_size_(counts->size()),
  419. bucket_ranges_(bucket_ranges),
  420. index_(0) {
  421. DCHECK_GE(bucket_ranges_->bucket_count(), counts_size_);
  422. SkipEmptyBuckets();
  423. }
  424. SampleVectorIterator::SampleVectorIterator(
  425. const HistogramBase::AtomicCount* counts,
  426. size_t counts_size,
  427. const BucketRanges* bucket_ranges)
  428. : counts_(counts),
  429. counts_size_(counts_size),
  430. bucket_ranges_(bucket_ranges),
  431. index_(0) {
  432. DCHECK_GE(bucket_ranges_->bucket_count(), counts_size_);
  433. SkipEmptyBuckets();
  434. }
  435. SampleVectorIterator::~SampleVectorIterator() = default;
  436. bool SampleVectorIterator::Done() const {
  437. return index_ >= counts_size_;
  438. }
  439. void SampleVectorIterator::Next() {
  440. DCHECK(!Done());
  441. index_++;
  442. SkipEmptyBuckets();
  443. }
  444. void SampleVectorIterator::Get(HistogramBase::Sample* min,
  445. int64_t* max,
  446. HistogramBase::Count* count) const {
  447. DCHECK(!Done());
  448. if (min != nullptr)
  449. *min = bucket_ranges_->range(index_);
  450. if (max != nullptr)
  451. *max = strict_cast<int64_t>(bucket_ranges_->range(index_ + 1));
  452. if (count != nullptr)
  453. *count = subtle::NoBarrier_Load(&counts_[index_]);
  454. }
  455. bool SampleVectorIterator::GetBucketIndex(size_t* index) const {
  456. DCHECK(!Done());
  457. if (index != nullptr)
  458. *index = index_;
  459. return true;
  460. }
  461. void SampleVectorIterator::SkipEmptyBuckets() {
  462. if (Done())
  463. return;
  464. while (index_ < counts_size_) {
  465. if (subtle::NoBarrier_Load(&counts_[index_]) != 0)
  466. return;
  467. index_++;
  468. }
  469. }
  470. } // namespace base