[Courgette] Simplify EncodedProgram Label addition code; removed "1.01 x" memory fix.

This CL simplifies how Labels get flattened to a list of RVAs. In the past
EncodedProgram used DefineAbs32Label() / DefineRel32Label(), which let callers
add one Label at a time. Complexity arose from:
- Function pointer usage to avoid duplicate code for abs32 and rel32.
- Need for EncodedProgram to dynamically adjust size of RVA list. This led to
  inefficient array resizing, which was fixed by the "1.01 x" memory growth.

Change: We now pass the collection of abs32 and rel32 Labels to EncodedProgram.
This simplifies the interface, and allows EncodedProgram to find the max indexes
and preallocated buffers. The trade-off is increased test code complexity, since
we'd need to create Label collection.

Other changes:
- Update namespace{} for EncodedProgram and its tests.
- Add more Label constructors (for testing).
- Add LabelManager::GetIndexBound(), for LabelVector and RVAToLabel.
- Add kUnassignedRVA in image_utils.h, with checks for its absence in images.

Review URL: https://codereview.chromium.org/1571913003

Cr-Commit-Position: refs/heads/master@{#370200}

1 files changed, 39 insertions, 52 deletions

diff --git a/courgette/encoded_program.cc b/courgette/encoded_program.cc
index 209fe2f..59800c5 100644
--- a/courgette/encoded_program.cc
+++ b/courgette/encoded_program.cc
@@ -26,11 +26,7 @@
 
 namespace courgette {
 
-// Constructor is here rather than in the header.  Although the constructor
-// appears to do nothing it is fact quite large because of the implicit calls to
-// field constructors.  Ditto for the destructor.
-EncodedProgram::EncodedProgram() : image_base_(0) {}
-EncodedProgram::~EncodedProgram() {}
+namespace {
 
 // Serializes a vector of integral values using Varint32 coding.
 template<typename V>
@@ -132,60 +128,49 @@ bool ReadVectorU8(V* items, SourceStream* buffer) {
   return ok;
 }
 
-////////////////////////////////////////////////////////////////////////////////
-
-CheckBool EncodedProgram::DefineRel32Label(int index, RVA value) {
-  return DefineLabelCommon(&rel32_rva_, index, value);
-}
+}  // namespace
 
-CheckBool EncodedProgram::DefineAbs32Label(int index, RVA value) {
-  return DefineLabelCommon(&abs32_rva_, index, value);
-}
-
-static const RVA kUnassignedRVA = static_cast<RVA>(-1);
-
-CheckBool EncodedProgram::DefineLabelCommon(RvaVector* rvas,
-                                            int index,
-                                            RVA rva) {
-  bool ok = true;
+////////////////////////////////////////////////////////////////////////////////
 
-  // Resize |rvas| to accommodate |index|. If we naively call resize(), in the
-  // worst case we'd encounter |index| in increasing order, and then we'd
-  // require reallocation every time. Turns out this worst case is the typical
-  // scenario, and noticeable slowness (~5x slow down) ensues. The solution is
-  // to exponentially increase capacity. We use a factor of 1.01 to be frugal.
-  if (static_cast<int>(rvas->capacity()) <= index)
-    ok = rvas->reserve((index + 1) * 1.01);
-  if (ok && static_cast<int>(rvas->size()) <= index)
-    ok = rvas->resize(index + 1, kUnassignedRVA);
+// Constructor is here rather than in the header. Although the constructor
+// appears to do nothing it is fact quite large because of the implicit calls to
+// field constructors. Ditto for the destructor.
+EncodedProgram::EncodedProgram() {}
+EncodedProgram::~EncodedProgram() {}
 
-  if (ok) {
-    DCHECK_EQ((*rvas)[index], kUnassignedRVA)
-        << "DefineLabel double assigned " << index;
-    (*rvas)[index] = rva;
-  }
+CheckBool EncodedProgram::DefineLabels(const RVAToLabel& abs32_labels,
+                                       const RVAToLabel& rel32_labels) {
+  // which == 0 => abs32; which == 1 => rel32.
+  for (int which = 0; which < 2; ++which) {
+    const RVAToLabel& labels = which == 0 ? abs32_labels : rel32_labels;
+    RvaVector& rvas = which == 0 ? abs32_rva_ : rel32_rva_;
 
-  return ok;
-}
+    if (!rvas.resize(LabelManager::GetIndexBound(labels), kUnassignedRVA))
+      return false;
 
-void EncodedProgram::EndLabels() {
-  FinishLabelsCommon(&abs32_rva_);
-  FinishLabelsCommon(&rel32_rva_);
-}
+    // For each Label, write its RVA to assigned index.
+    for (const auto& rva_and_label : labels) {
+      const Label& label = *rva_and_label.second;
+      DCHECK_EQ(rva_and_label.first, label.rva_);
+      DCHECK_NE(label.index_, Label::kNoIndex);
+      DCHECK_EQ(rvas[label.index_], kUnassignedRVA)
+          << "DefineLabels() double assigned " << label.index_;
+      rvas[label.index_] = label.rva_;
+    }
 
-void EncodedProgram::FinishLabelsCommon(RvaVector* rvas) {
-  // Replace all unassigned slots with the value at the previous index so they
-  // delta-encode to zero.  (There might be better values than zero.  The way to
-  // get that is have the higher level assembly program assign the unassigned
-  // slots.)
-  RVA previous = 0;
-  size_t size = rvas->size();
-  for (size_t i = 0;  i < size;  ++i) {
-    if ((*rvas)[i] == kUnassignedRVA)
-      (*rvas)[i] = previous;
-    else
-      previous = (*rvas)[i];
+    // Replace all unassigned slots with the value at the previous index so they
+    // delta-encode to zero. (There might be better values than zero. The way to
+    // get that is have the higher level assembly program assign the unassigned
+    // slots.)
+    RVA previous = 0;
+    for (RVA& rva : rvas) {
+      if (rva == kUnassignedRVA)
+        rva = previous;
+      else
+        previous = rva;
+    }
   }
+  return true;
 }
 
 CheckBool EncodedProgram::AddOrigin(RVA origin) {
@@ -752,6 +737,7 @@ class RelocBlock {
 CheckBool EncodedProgram::GeneratePeRelocations(SinkStream* buffer,
                                                 uint8_t type) {
   std::sort(abs32_relocs_.begin(), abs32_relocs_.end());
+  DCHECK(abs32_relocs_.empty() || abs32_relocs_.back() != kUnassignedRVA);
 
   RelocBlock block;
 
@@ -773,6 +759,7 @@ CheckBool EncodedProgram::GeneratePeRelocations(SinkStream* buffer,
 CheckBool EncodedProgram::GenerateElfRelocations(Elf32_Word r_info,
                                                  SinkStream* buffer) {
   std::sort(abs32_relocs_.begin(), abs32_relocs_.end());
+  DCHECK(abs32_relocs_.empty() || abs32_relocs_.back() != kUnassignedRVA);
 
   Elf32_Rel relocation_block;