courgette/label_manager.cc

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