1 // Copyright 2015 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 #include "courgette/label_manager.h"
12 #include "base/check.h"
13 #include "base/check_op.h"
14 #include "base/logging.h"
15 #include "base/numerics/safe_conversions.h"
16 #include "base/numerics/safe_math.h"
17 #include "courgette/consecutive_range_visitor.h"
21 LabelManager::SimpleIndexAssigner::SimpleIndexAssigner(LabelVector* labels)
23 // Initialize |num_index_| and |available_|.
24 num_index_ = std::max(base::checked_cast<int>(labels_->size()),
25 GetLabelIndexBound(*labels_));
26 available_.resize(num_index_, true);
28 for (const Label& label : *labels_) {
29 if (label.index_ != Label::kNoIndex) {
30 available_.at(label.index_) = false;
34 VLOG(1) << used << " of " << labels_->size() << " labels pre-assigned.";
37 LabelManager::SimpleIndexAssigner::~SimpleIndexAssigner() = default;
39 void LabelManager::SimpleIndexAssigner::DoForwardFill() {
41 // Inside the loop, if |prev_index| == |kNoIndex| then we try to assign 0.
42 // This allows 0 (if unused) to be assigned in middle of |labels_|.
43 int prev_index = Label::kNoIndex;
44 for (auto p = labels_->begin(); p != labels_->end(); ++p) {
45 if (p->index_ == Label::kNoIndex) {
46 int index = (prev_index == Label::kNoIndex) ? 0 : prev_index + 1;
47 if (index < num_index_ && available_.at(index)) {
49 available_.at(index) = false;
53 prev_index = p->index_;
55 VLOG(1) << " fill forward " << count;
58 void LabelManager::SimpleIndexAssigner::DoBackwardFill() {
60 // This is asymmetric from DoForwardFill(), to preserve old behavior.
61 // Inside the loop, if |prev_index| == |kNoIndex| then we skip assignment.
62 // But we initilaize |prev_index| = |num_index_|, so if the last element in
63 // |labels_| has no index, then can use |num_index_| - 1 (if unused). We don't
64 // try this assignment elsewhere.
65 int prev_index = num_index_;
66 for (auto p = labels_->rbegin(); p != labels_->rend(); ++p) {
67 if (p->index_ == Label::kNoIndex && prev_index != Label::kNoIndex) {
68 int index = prev_index - 1;
69 if (index >= 0 && available_.at(index)) {
71 available_.at(index) = false;
75 prev_index = p->index_;
77 VLOG(1) << " fill backward " << count;
80 void LabelManager::SimpleIndexAssigner::DoInFill() {
83 for (Label& label : *labels_) {
84 if (label.index_ == Label::kNoIndex) {
85 while (!available_.at(index))
88 available_.at(index) = false;
93 VLOG(1) << " infill " << count;
96 LabelManager::LabelManager() = default;
98 LabelManager::~LabelManager() = default;
101 int LabelManager::GetLabelIndexBound(const LabelVector& labels) {
103 for (const Label& label : labels) {
104 if (label.index_ != Label::kNoIndex)
105 max_index = std::max(max_index, label.index_);
107 return max_index + 1;
110 // Uses binary search to find |rva|.
111 Label* LabelManager::Find(RVA rva) {
112 auto it = std::lower_bound(
113 labels_.begin(), labels_.end(), Label(rva),
114 [](const Label& l1, const Label& l2) { return l1.rva_ < l2.rva_; });
115 return it == labels_.end() || it->rva_ != rva ? nullptr : &(*it);
118 void LabelManager::UnassignIndexes() {
119 for (Label& label : labels_)
120 label.index_ = Label::kNoIndex;
123 void LabelManager::DefaultAssignIndexes() {
125 for (Label& label : labels_) {
126 CHECK_EQ(Label::kNoIndex, label.index_);
127 label.index_ = cur_index++;
131 void LabelManager::AssignRemainingIndexes() {
132 // This adds some memory overhead, about 1 bit per Label (more if indexes >=
133 // |labels_.size()| get used).
134 SimpleIndexAssigner assigner(&labels_);
135 assigner.DoForwardFill();
136 assigner.DoBackwardFill();
140 // We wish to minimize peak memory usage here. Analysis: Let
141 // m = number of (RVA) elements in |rva_visitor|,
142 // n = number of distinct (RVA) elements in |rva_visitor|.
143 // The final storage is n * sizeof(Label) bytes. During computation we uniquify
144 // m RVAs, and count repeats. Taking sizeof(RVA) = 4, an implementation using
145 // std::map or std::unordered_map would consume additionally 32 * n bytes.
146 // Meanwhile, our std::vector implementation consumes additionally 4 * m bytes
147 // For our typical usage (i.e. Chrome) we see m = ~4n, so we use 16 * n bytes of
148 // extra contiguous memory during computation. Assuming memory fragmentation
149 // would not be an issue, this is much better than using std::map.
150 void LabelManager::Read(RvaVisitor* rva_visitor) {
151 // Write all values in |rva_visitor| to |rvas|.
152 size_t num_rva = rva_visitor->Remaining();
153 std::vector<RVA> rvas(num_rva);
154 for (size_t i = 0; i < num_rva; ++i, rva_visitor->Next())
155 rvas[i] = rva_visitor->Get();
157 // Sort |rvas|, then count the number of distinct values.
158 using CRV = ConsecutiveRangeVisitor<std::vector<RVA>::iterator>;
159 std::sort(rvas.begin(), rvas.end());
160 DCHECK(rvas.empty() || rvas.back() != kUnassignedRVA);
162 size_t num_distinct_rva = 0;
163 for (CRV it(rvas.begin(), rvas.end()); it.has_more(); it.advance())
166 // Reserve space for |labels_|, populate with sorted RVA and repeats.
167 DCHECK(labels_.empty());
168 labels_.reserve(num_distinct_rva);
169 for (CRV it(rvas.begin(), rvas.end()); it.has_more(); it.advance()) {
170 labels_.push_back(Label(*it.cur()));
171 labels_.back().count_ =
172 base::checked_cast<decltype(labels_.back().count_)>(it.repeat());
176 } // namespace courgette