label_manager.cc 5.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176
  1. // Copyright 2015 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 "courgette/label_manager.h"
  5. #include <stddef.h>
  6. #include <stdint.h>
  7. #include <algorithm>
  8. #include "base/check.h"
  9. #include "base/check_op.h"
  10. #include "base/logging.h"
  11. #include "base/numerics/safe_conversions.h"
  12. #include "base/numerics/safe_math.h"
  13. #include "courgette/consecutive_range_visitor.h"
  14. namespace courgette {
  15. LabelManager::SimpleIndexAssigner::SimpleIndexAssigner(LabelVector* labels)
  16. : labels_(labels) {
  17. // Initialize |num_index_| and |available_|.
  18. num_index_ = std::max(base::checked_cast<int>(labels_->size()),
  19. GetLabelIndexBound(*labels_));
  20. available_.resize(num_index_, true);
  21. size_t used = 0;
  22. for (const Label& label : *labels_) {
  23. if (label.index_ != Label::kNoIndex) {
  24. available_.at(label.index_) = false;
  25. ++used;
  26. }
  27. }
  28. VLOG(1) << used << " of " << labels_->size() << " labels pre-assigned.";
  29. }
  30. LabelManager::SimpleIndexAssigner::~SimpleIndexAssigner() = default;
  31. void LabelManager::SimpleIndexAssigner::DoForwardFill() {
  32. size_t count = 0;
  33. // Inside the loop, if |prev_index| == |kNoIndex| then we try to assign 0.
  34. // This allows 0 (if unused) to be assigned in middle of |labels_|.
  35. int prev_index = Label::kNoIndex;
  36. for (auto p = labels_->begin(); p != labels_->end(); ++p) {
  37. if (p->index_ == Label::kNoIndex) {
  38. int index = (prev_index == Label::kNoIndex) ? 0 : prev_index + 1;
  39. if (index < num_index_ && available_.at(index)) {
  40. p->index_ = index;
  41. available_.at(index) = false;
  42. ++count;
  43. }
  44. }
  45. prev_index = p->index_;
  46. }
  47. VLOG(1) << " fill forward " << count;
  48. }
  49. void LabelManager::SimpleIndexAssigner::DoBackwardFill() {
  50. size_t count = 0;
  51. // This is asymmetric from DoForwardFill(), to preserve old behavior.
  52. // Inside the loop, if |prev_index| == |kNoIndex| then we skip assignment.
  53. // But we initilaize |prev_index| = |num_index_|, so if the last element in
  54. // |labels_| has no index, then can use |num_index_| - 1 (if unused). We don't
  55. // try this assignment elsewhere.
  56. int prev_index = num_index_;
  57. for (auto p = labels_->rbegin(); p != labels_->rend(); ++p) {
  58. if (p->index_ == Label::kNoIndex && prev_index != Label::kNoIndex) {
  59. int index = prev_index - 1;
  60. if (index >= 0 && available_.at(index)) {
  61. p->index_ = index;
  62. available_.at(index) = false;
  63. ++count;
  64. }
  65. }
  66. prev_index = p->index_;
  67. }
  68. VLOG(1) << " fill backward " << count;
  69. }
  70. void LabelManager::SimpleIndexAssigner::DoInFill() {
  71. size_t count = 0;
  72. int index = 0;
  73. for (Label& label : *labels_) {
  74. if (label.index_ == Label::kNoIndex) {
  75. while (!available_.at(index))
  76. ++index;
  77. label.index_ = index;
  78. available_.at(index) = false;
  79. ++index;
  80. ++count;
  81. }
  82. }
  83. VLOG(1) << " infill " << count;
  84. }
  85. LabelManager::LabelManager() = default;
  86. LabelManager::~LabelManager() = default;
  87. // static
  88. int LabelManager::GetLabelIndexBound(const LabelVector& labels) {
  89. int max_index = -1;
  90. for (const Label& label : labels) {
  91. if (label.index_ != Label::kNoIndex)
  92. max_index = std::max(max_index, label.index_);
  93. }
  94. return max_index + 1;
  95. }
  96. // Uses binary search to find |rva|.
  97. Label* LabelManager::Find(RVA rva) {
  98. auto it = std::lower_bound(
  99. labels_.begin(), labels_.end(), Label(rva),
  100. [](const Label& l1, const Label& l2) { return l1.rva_ < l2.rva_; });
  101. return it == labels_.end() || it->rva_ != rva ? nullptr : &(*it);
  102. }
  103. void LabelManager::UnassignIndexes() {
  104. for (Label& label : labels_)
  105. label.index_ = Label::kNoIndex;
  106. }
  107. void LabelManager::DefaultAssignIndexes() {
  108. int cur_index = 0;
  109. for (Label& label : labels_) {
  110. CHECK_EQ(Label::kNoIndex, label.index_);
  111. label.index_ = cur_index++;
  112. }
  113. }
  114. void LabelManager::AssignRemainingIndexes() {
  115. // This adds some memory overhead, about 1 bit per Label (more if indexes >=
  116. // |labels_.size()| get used).
  117. SimpleIndexAssigner assigner(&labels_);
  118. assigner.DoForwardFill();
  119. assigner.DoBackwardFill();
  120. assigner.DoInFill();
  121. }
  122. // We wish to minimize peak memory usage here. Analysis: Let
  123. // m = number of (RVA) elements in |rva_visitor|,
  124. // n = number of distinct (RVA) elements in |rva_visitor|.
  125. // The final storage is n * sizeof(Label) bytes. During computation we uniquify
  126. // m RVAs, and count repeats. Taking sizeof(RVA) = 4, an implementation using
  127. // std::map or std::unordered_map would consume additionally 32 * n bytes.
  128. // Meanwhile, our std::vector implementation consumes additionally 4 * m bytes
  129. // For our typical usage (i.e. Chrome) we see m = ~4n, so we use 16 * n bytes of
  130. // extra contiguous memory during computation. Assuming memory fragmentation
  131. // would not be an issue, this is much better than using std::map.
  132. void LabelManager::Read(RvaVisitor* rva_visitor) {
  133. // Write all values in |rva_visitor| to |rvas|.
  134. size_t num_rva = rva_visitor->Remaining();
  135. std::vector<RVA> rvas(num_rva);
  136. for (size_t i = 0; i < num_rva; ++i, rva_visitor->Next())
  137. rvas[i] = rva_visitor->Get();
  138. // Sort |rvas|, then count the number of distinct values.
  139. using CRV = ConsecutiveRangeVisitor<std::vector<RVA>::iterator>;
  140. std::sort(rvas.begin(), rvas.end());
  141. DCHECK(rvas.empty() || rvas.back() != kUnassignedRVA);
  142. size_t num_distinct_rva = 0;
  143. for (CRV it(rvas.begin(), rvas.end()); it.has_more(); it.advance())
  144. ++num_distinct_rva;
  145. // Reserve space for |labels_|, populate with sorted RVA and repeats.
  146. DCHECK(labels_.empty());
  147. labels_.reserve(num_distinct_rva);
  148. for (CRV it(rvas.begin(), rvas.end()); it.has_more(); it.advance()) {
  149. labels_.push_back(Label(*it.cur()));
  150. labels_.back().count_ =
  151. base::checked_cast<decltype(labels_.back().count_)>(it.repeat());
  152. }
  153. }
  154. } // namespace courgette