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