courgette/label_manager.cc

   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.
   4
   5 #include "courgette/label_manager.h"
   6
   7 #include <stddef.h>
   8 #include <stdint.h>
   9
  10 #include <algorithm>
  11
  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"
  18
  19 namespace courgette {
  20
  21 LabelManager::SimpleIndexAssigner::SimpleIndexAssigner(LabelVector* labels)
  22     : labels_(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);
  27   size_t used = 0;
  28   for (const Label& label : *labels_) {
  29     if (label.index_ != Label::kNoIndex) {
  30       available_.at(label.index_) = false;
  31       ++used;
  32     }
  33   }
  34   VLOG(1) << used << " of " << labels_->size() << " labels pre-assigned.";
  35 }
  36
  37 LabelManager::SimpleIndexAssigner::~SimpleIndexAssigner() = default;
  38
  39 void LabelManager::SimpleIndexAssigner::DoForwardFill() {
  40   size_t count = 0;
  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)) {
  48         p->index_ = index;
  49         available_.at(index) = false;
  50         ++count;
  51       }
  52     }
  53     prev_index = p->index_;
  54   }
  55   VLOG(1) << "  fill forward " << count;
  56 }
  57
  58 void LabelManager::SimpleIndexAssigner::DoBackwardFill() {
  59   size_t count = 0;
  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)) {
  70         p->index_ = index;
  71         available_.at(index) = false;
  72         ++count;
  73       }
  74     }
  75     prev_index = p->index_;
  76   }
  77   VLOG(1) << "  fill backward " << count;
  78 }
  79
  80 void LabelManager::SimpleIndexAssigner::DoInFill() {
  81   size_t count = 0;
  82   int index = 0;
  83   for (Label& label : *labels_) {
  84     if (label.index_ == Label::kNoIndex) {
  85       while (!available_.at(index))
  86         ++index;
  87       label.index_ = index;
  88       available_.at(index) = false;
  89       ++index;
  90       ++count;
  91     }
  92   }
  93   VLOG(1) << "  infill " << count;
  94 }
  95
  96 LabelManager::LabelManager() = default;
  97
  98 LabelManager::~LabelManager() = default;
  99
 100 // static
 101 int LabelManager::GetLabelIndexBound(const LabelVector& labels) {
 102   int max_index = -1;
 103   for (const Label& label : labels) {
 104     if (label.index_ != Label::kNoIndex)
 105       max_index = std::max(max_index, label.index_);
 106   }
 107   return max_index + 1;
 108 }
 109
 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);
 116 }
 117
 118 void LabelManager::UnassignIndexes() {
 119   for (Label& label : labels_)
 120     label.index_ = Label::kNoIndex;
 121 }
 122
 123 void LabelManager::DefaultAssignIndexes() {
 124   int cur_index = 0;
 125   for (Label& label : labels_) {
 126     CHECK_EQ(Label::kNoIndex, label.index_);
 127     label.index_ = cur_index++;
 128   }
 129 }
 130
 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();
 137   assigner.DoInFill();
 138 }
 139
 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();
 156
 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);
 161
 162   size_t num_distinct_rva = 0;
 163   for (CRV it(rvas.begin(), rvas.end()); it.has_more(); it.advance())
 164     ++num_distinct_rva;
 165
 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());
 173   }
 174 }
 175
 176 }  // namespace courgette