Added some utility functions for register maps.

These should be useful for the garbage collector.

Change-Id: I9503af6338031dd8726498e11035758076530f68
diff --git a/src/dex_verifier.cc b/src/dex_verifier.cc
index b6739f8..b15e7bd 100644
--- a/src/dex_verifier.cc
+++ b/src/dex_verifier.cc
@@ -316,7 +316,6 @@
   const DexFile::CodeItem* code_item = vdata->code_item_;
   uint16_t registers_size = code_item->registers_size_;
   uint32_t insns_size = code_item->insns_size_;
-  bool generate_register_map = true;
   RegisterTable reg_table;
 
   if (registers_size * insns_size > 4*1024*1024) {
@@ -325,8 +324,7 @@
   }
 
   /* Create and initialize register lists. */
-  if (!InitRegisterTable(vdata, &reg_table,
-      generate_register_map ? kTrackRegsGcPoints : kTrackRegsBranches)) {
+  if (!InitRegisterTable(vdata, &reg_table, kTrackRegsGcPoints)) {
     return false;
   }
 
@@ -349,22 +347,16 @@
     return false;
   }
 
-  /* Generate a register map. */
-  if (generate_register_map) {
-    UniquePtr<RegisterMap> map(GenerateRegisterMapV(vdata));
-    /*
-     * Tuck the map into the Method. It will either get used directly or, if
-     * we're in dexopt, will be packed up and appended to the DEX file.
-     */
-    ByteArray* header = ByteArray::Alloc(sizeof(RegisterMapHeader));
-    ByteArray* data = ByteArray::Alloc(ComputeRegisterMapSize(map.get()));
+  /* Generate a register map and add it to the method. */
+  UniquePtr<RegisterMap> map(GenerateRegisterMapV(vdata));
+  ByteArray* header = ByteArray::Alloc(sizeof(RegisterMapHeader));
+  ByteArray* data = ByteArray::Alloc(ComputeRegisterMapSize(map.get()));
 
-    memcpy(header->GetData(), map.get()->header_, sizeof(RegisterMapHeader));
-    memcpy(data->GetData(), map.get()->data_, ComputeRegisterMapSize(map.get()));
+  memcpy(header->GetData(), map.get()->header_, sizeof(RegisterMapHeader));
+  memcpy(data->GetData(), map.get()->data_, ComputeRegisterMapSize(map.get()));
 
-    method->SetRegisterMapHeader(header);
-    method->SetRegisterMapData(data);
-  }
+  method->SetRegisterMapHeader(header);
+  method->SetRegisterMapData(data);
 
   return true;
 }
@@ -1610,7 +1602,6 @@
           break;
         if (res_class != NULL) {
           if (!decl_class->IsInterface() &&
-              //!res_class->InstanceOf(decl_class)) {
               !decl_class->IsAssignableFrom(res_class)) {
             LOG(ERROR) << "VFY: returning " << std::hex
                        << res_class->GetDescriptor()->ToModifiedUtf8()
@@ -3446,9 +3437,7 @@
     SetRegisterType(work_line, reg + 1, kRegTypeUnknown);
   }
 
-  /*
-   * Handle "continue". Tag the next consecutive instruction.
-   */
+  /* Handle "continue". Tag the next consecutive instruction. */
   if ((opcode_flag & Instruction::kContinue) != 0) {
     size_t insn_width = InsnGetWidth(insn_flags, insn_idx);
     if (insn_idx + insn_width >= insns_size) {
@@ -5305,7 +5294,7 @@
   uint32_t data_size = gc_point_count * (bytes_for_addr + reg_width);
 
   RegisterMap* map = new RegisterMap(format, reg_width, gc_point_count,
-      true, data_size);
+      data_size);
 
   /* Populate it. */
   uint8_t* map_data = map->data_;
@@ -5371,6 +5360,121 @@
   return map;
 }
 
+DexVerifier::RegisterMap* DexVerifier::GetExpandedRegisterMapHelper(
+    Method* method, RegisterMap* map) {
+  RegisterMap* new_map;
+
+  if (map == NULL)
+    return NULL;
+
+  /* TODO: sanity check to ensure this isn't called w/o external locking */
+
+  uint8_t format = map->header_->format_;
+  switch (format) {
+    case kRegMapFormatCompact8:
+    case kRegMapFormatCompact16:
+      /* already expanded */
+      return map;
+    case kRegMapFormatDifferential:
+      new_map = UncompressMapDifferential(map);
+      break;
+    default:
+      LOG(ERROR) << "Unknown format " << format
+                 << " in dvmGetExpandedRegisterMap";
+      return NULL;
+  }
+
+  if (new_map == NULL) {
+    LOG(ERROR) << "Map failed to uncompress (fmt=" << format << ") "
+               << method->GetDeclaringClass()->GetDescriptor()->ToModifiedUtf8()
+               << "." << method->GetName();
+    return NULL;
+  }
+
+  /* Update method, and free compressed map if it was sitting on the heap. */
+  ByteArray* header = ByteArray::Alloc(sizeof(RegisterMapHeader));
+  ByteArray* data = ByteArray::Alloc(ComputeRegisterMapSize(map));
+
+  memcpy(header->GetData(), map->header_, sizeof(RegisterMapHeader));
+  memcpy(data->GetData(), map->data_, ComputeRegisterMapSize(map));
+
+  method->SetRegisterMapHeader(header);
+  method->SetRegisterMapData(data);
+
+  delete map;
+  return new_map;
+}
+
+const uint8_t* DexVerifier::RegisterMapGetLine(const RegisterMap* map, int addr) {
+  int addr_width, line_width;
+  uint8_t format = map->header_->format_;
+  uint16_t num_entries = map->header_->num_entries_;
+
+  assert(num_entries > 0);
+
+  switch (format) {
+    case kRegMapFormatNone:
+      return NULL;
+    case kRegMapFormatCompact8:
+      addr_width = 1;
+      break;
+    case kRegMapFormatCompact16:
+      addr_width = 2;
+      break;
+    default:
+      LOG(ERROR) << "Unknown format " << format;
+      return NULL;
+  }
+
+  line_width = addr_width + map->header_->reg_width_;
+
+  /*
+   * Find the appropriate entry. Many maps are very small, some are very large.
+   */
+  static const int kSearchThreshold = 8;
+  const uint8_t* data = NULL;
+  int line_addr;
+
+  if (num_entries < kSearchThreshold) {
+    int i;
+    data = map->data_;
+    for (i = num_entries; i > 0; i--) {
+      line_addr = data[0];
+      if (addr_width > 1)
+        line_addr |= data[1] << 8;
+      if (line_addr == addr)
+        return data + addr_width;
+
+      data += line_width;
+    }
+    assert(data == map->data_ + line_width * num_entries);
+  } else {
+    int hi, lo, mid;
+
+    lo = 0;
+    hi = num_entries -1;
+
+    while (hi >= lo) {
+      mid = (hi + lo) / 2;
+      data = map->data_ + line_width * mid;
+
+      line_addr = data[0];
+      if (addr_width > 1)
+        line_addr |= data[1] << 8;
+
+      if (addr > line_addr) {
+        lo = mid + 1;
+      } else if (addr < line_addr) {
+        hi = mid - 1;
+      } else {
+        return data + addr_width;
+      }
+    }
+  }
+
+  return NULL;
+}
+
 void DexVerifier::OutputTypeVector(const RegType* regs, int insn_reg_count,
     uint8_t* data) {
   uint8_t val = 0;
@@ -5469,8 +5573,7 @@
 
   if (map1->header_->format_ != map2->header_->format_ ||
       map1->header_->reg_width_ != map2->header_->reg_width_ ||
-      map1->header_->num_entries_ != map2->header_->num_entries_ ||
-      map1->header_->format_on_heap_ != map2->header_->format_on_heap_) {
+      map1->header_->num_entries_ != map2->header_->num_entries_) {
     LOG(ERROR) << "CompareMaps: fields mismatch";
   }
   if (memcmp(map1->data_, map2->data_, size1) != 0) {
@@ -5719,7 +5822,7 @@
   }
 
   RegisterMap* new_map = new RegisterMap(kRegMapFormatDifferential, reg_width,
-      num_entries, true, new_map_size);
+      num_entries, new_map_size);
 
   tmp_ptr = new_map->data_;
   tmp_ptr = WriteUnsignedLeb128(tmp_ptr, new_data_size);
@@ -5761,7 +5864,7 @@
   /* Now we know enough to allocate the new map. */
   new_data_size = (new_addr_width + reg_width) * num_entries;
   RegisterMap* new_map = new RegisterMap(new_format, reg_width, num_entries,
-      true, new_data_size);
+      new_data_size);
 
   /* Write the start address and initial bits to the new map. */
   uint8_t* dst_ptr = new_map->data_;
diff --git a/src/dex_verifier.h b/src/dex_verifier.h
index 404227d..0170ebe 100644
--- a/src/dex_verifier.h
+++ b/src/dex_verifier.h
@@ -362,12 +362,9 @@
     uint8_t format_;          /* enum RegisterMapFormat; MUST be first entry */
     uint8_t reg_width_;       /* bytes per register line, 1+ */
     uint16_t num_entries_;    /* number of entries */
-    bool    format_on_heap_;  /* indicates allocation on heap */
 
-    RegisterMapHeader(uint8_t format, uint8_t reg_width, uint16_t num_entries,
-        bool format_on_heap)
-        : format_(format), reg_width_(reg_width), num_entries_(num_entries),
-          format_on_heap_(format_on_heap) {
+    RegisterMapHeader(uint8_t format, uint8_t reg_width, uint16_t num_entries)
+        : format_(format), reg_width_(reg_width), num_entries_(num_entries) {
     }
   };
 
@@ -395,9 +392,8 @@
     }
 
     RegisterMap(uint8_t format, uint8_t reg_width, uint16_t num_entries,
-        bool format_on_heap, uint32_t data_size) {
-      header_ = new RegisterMapHeader(format, reg_width, num_entries,
-          format_on_heap);
+        uint32_t data_size) {
+      header_ = new RegisterMapHeader(format, reg_width, num_entries);
       data_ = new uint8_t[data_size]();
       needs_free_ = true;
     }
@@ -561,6 +557,136 @@
     return (uint32_t) (kRegTypeUninit | (uidx << kRegTypeUninitShift));
   }
 
+  /*
+   * Generate the register map for a method that has just been verified
+   * (i.e. we're doing this as part of verification).
+   *
+   * For type-precise determination we have all the data we need, so we
+   * just need to encode it in some clever fashion.
+   *
+   * Returns a pointer to a newly-allocated RegisterMap, or NULL on failure.
+   */
+  static RegisterMap* GenerateRegisterMapV(VerifierData* vdata);
+
+  /*
+   * Get the expanded form of the register map associated with the specified
+   * method. May update the RegisterMap, possibly freeing the previous map.
+   *
+   * Returns NULL on failure (e.g. unable to expand map).
+   *
+   * NOTE: this function is not synchronized; external locking is mandatory.
+   * (This is expected to be called at GC time.)
+   */
+  static inline RegisterMap* GetExpandedRegisterMap(Method* method) {
+    if (method->GetRegisterMapHeader() == NULL ||
+        method->GetRegisterMapData() == NULL) {
+      return NULL;
+    }
+    RegisterMap* cur_map = new RegisterMap(method->GetRegisterMapHeader(),
+        method->GetRegisterMapData());
+    uint8_t format = cur_map->header_->format_;
+    if (format == kRegMapFormatCompact8 || format == kRegMapFormatCompact16) {
+      return cur_map;
+    } else {
+      return GetExpandedRegisterMapHelper(method, cur_map);
+    }
+  }
+
+  /*
+   * Get the expanded form of the register map associated with the method.
+   *
+   * If the map is already in one of the uncompressed formats, we return
+   * immediately.  Otherwise, we expand the map and replace method's register
+   * map pointer, freeing it if it was allocated on the heap.
+   *
+   * NOTE: this function is not synchronized; external locking is mandatory
+   * (unless we're in the zygote, where single-threaded access is guaranteed).
+   */
+  static RegisterMap* GetExpandedRegisterMapHelper(Method* method,
+      RegisterMap* map);
+
+  /* Return the data for the specified address, or NULL if not found. */
+  static const uint8_t* RegisterMapGetLine(const RegisterMap* map, int addr);
+
+  /*
+   * Determine if the RegType value is a reference type.
+   *
+   * Ordinarily we include kRegTypeZero in the "is it a reference"
+   * check. There's no value in doing so here, because we know
+   * the register can't hold anything but zero.
+   */
+  static inline bool IsReferenceType(RegType type) {
+    return (type > kRegTypeMAX || type == kRegTypeUninit);
+  }
+
+  /* Toggle the value of the "idx"th bit in "ptr". */
+  static inline void ToggleBit(uint8_t* ptr, int idx) {
+    ptr[idx >> 3] ^= 1 << (idx & 0x07);
+  }
+
+  /*
+   * Given a line of registers, output a bit vector that indicates whether
+   * or not the register holds a reference type (which could be null).
+   *
+   * We use '1' to indicate it's a reference, '0' for anything else (numeric
+   * value, uninitialized data, merge conflict). Register 0 will be found
+   * in the low bit of the first byte.
+   */
+  static void OutputTypeVector(const RegType* regs, int insn_reg_count,
+      uint8_t* data);
+
+  /*
+   * Double-check the map.
+   *
+   * We run through all of the data in the map, and compare it to the original.
+   * Only works on uncompressed data.
+   */
+  static bool VerifyMap(VerifierData* vdata, const RegisterMap* map);
+
+  /* Compare two register maps. Returns true if they're equal, false if not. */
+  static bool CompareMaps(const RegisterMap* map1, const RegisterMap* map2);
+
+  /* Compute the size, in bytes, of a register map. */
+  static size_t ComputeRegisterMapSize(const RegisterMap* map);
+
+  /*
+   * Compute the difference between two bit vectors.
+   *
+   * If "leb_out_buf" is non-NULL, we output the bit indices in ULEB128 format
+   * as we go. Otherwise, we just generate the various counts.
+   *
+   * The bit vectors are compared byte-by-byte, so any unused bits at the
+   * end must be zero.
+   *
+   * Returns the number of bytes required to hold the ULEB128 output.
+   *
+   * If "first_bit_changed_ptr" or "num_bits_changed_ptr" are non-NULL, they
+   * will receive the index of the first changed bit and the number of changed
+   * bits, respectively.
+   */
+  static int ComputeBitDiff(const uint8_t* bits1, const uint8_t* bits2,
+      int byte_width, int* first_bit_changed_ptr, int* num_bits_changed_ptr,
+      uint8_t* leb_out_buf);
+
+  /*
+   * Compress the register map with differential encoding.
+   *
+   * On success, returns a newly-allocated RegisterMap. If the map is not
+   * compatible for some reason, or fails to get smaller, this will return NULL.
+   */
+  static RegisterMap* CompressMapDifferential(const RegisterMap* map);
+
+  /*
+   * Expand a compressed map to an uncompressed form.
+   *
+   * Returns a newly-allocated RegisterMap on success, or NULL on failure.
+   *
+   * TODO: consider using the linear allocator or a custom allocator with
+   * LRU replacement for these instead of the native heap.
+   */
+  static RegisterMap* UncompressMapDifferential(const RegisterMap* map);
+
+
   /* Verify a class. Returns "true" on success. */
   static bool VerifyClass(Class* klass);
 
@@ -1543,95 +1669,6 @@
       const Instruction::DecodedInstruction* dec_insn, MethodType method_type,
       bool is_range, bool is_super, VerifyError* failure);
 
-  /*
-   * Generate the register map for a method that has just been verified
-   * (i.e. we're doing this as part of verification).
-   *
-   * For type-precise determination we have all the data we need, so we
-   * just need to encode it in some clever fashion.
-   *
-   * Returns a pointer to a newly-allocated RegisterMap, or NULL on failure.
-   */
-  static RegisterMap* GenerateRegisterMapV(VerifierData* vdata);
-
-  /*
-   * Determine if the RegType value is a reference type.
-   *
-   * Ordinarily we include kRegTypeZero in the "is it a reference"
-   * check. There's no value in doing so here, because we know
-   * the register can't hold anything but zero.
-   */
-  static inline bool IsReferenceType(RegType type) {
-    return (type > kRegTypeMAX || type == kRegTypeUninit);
-  }
-
-  /* Toggle the value of the "idx"th bit in "ptr". */
-  static inline void ToggleBit(uint8_t* ptr, int idx) {
-    ptr[idx >> 3] ^= 1 << (idx & 0x07);
-  }
-
-  /*
-   * Given a line of registers, output a bit vector that indicates whether
-   * or not the register holds a reference type (which could be null).
-   *
-   * We use '1' to indicate it's a reference, '0' for anything else (numeric
-   * value, uninitialized data, merge conflict). Register 0 will be found
-   * in the low bit of the first byte.
-   */
-  static void OutputTypeVector(const RegType* regs, int insn_reg_count,
-      uint8_t* data);
-
-  /*
-   * Double-check the map.
-   *
-   * We run through all of the data in the map, and compare it to the original.
-   * Only works on uncompressed data.
-   */
-  static bool VerifyMap(VerifierData* vdata, const RegisterMap* map);
-
-  /* Compare two register maps. Returns true if they're equal, false if not. */
-  static bool CompareMaps(const RegisterMap* map1, const RegisterMap* map2);
-
-  /* Compute the size, in bytes, of a register map. */
-  static size_t ComputeRegisterMapSize(const RegisterMap* map);
-
-  /*
-   * Compute the difference between two bit vectors.
-   *
-   * If "leb_out_buf" is non-NULL, we output the bit indices in ULEB128 format
-   * as we go. Otherwise, we just generate the various counts.
-   *
-   * The bit vectors are compared byte-by-byte, so any unused bits at the
-   * end must be zero.
-   *
-   * Returns the number of bytes required to hold the ULEB128 output.
-   *
-   * If "first_bit_changed_ptr" or "num_bits_changed_ptr" are non-NULL, they
-   * will receive the index of the first changed bit and the number of changed
-   * bits, respectively.
-   */
-  static int ComputeBitDiff(const uint8_t* bits1, const uint8_t* bits2,
-      int byte_width, int* first_bit_changed_ptr, int* num_bits_changed_ptr,
-      uint8_t* leb_out_buf);
-
-  /*
-   * Compress the register map with differential encoding.
-   *
-   * On success, returns a newly-allocated RegisterMap. If the map is not
-   * compatible for some reason, or fails to get smaller, this will return NULL.
-   */
-  static RegisterMap* CompressMapDifferential(const RegisterMap* map);
-
-  /*
-   * Expand a compressed map to an uncompressed form.
-   *
-   * Returns a newly-allocated RegisterMap on success, or NULL on failure.
-   *
-   * TODO: consider using the linear allocator or a custom allocator with
-   * LRU replacement for these instead of the native heap.
-   */
-  static RegisterMap* UncompressMapDifferential(const RegisterMap* map);
-
   DISALLOW_COPY_AND_ASSIGN(DexVerifier);
 };
 
diff --git a/src/object.h b/src/object.h
index 50da121..b57c0e9 100644
--- a/src/object.h
+++ b/src/object.h
@@ -588,11 +588,11 @@
 
   ByteArray* GetRegisterMapData() const;
 
-  void SetRegisterMapData(ByteArray* new_data);
+  void SetRegisterMapData(ByteArray* data);
 
   ByteArray* GetRegisterMapHeader() const;
 
-  void SetRegisterMapHeader(ByteArray* new_header);
+  void SetRegisterMapHeader(ByteArray* header);
 
   String* GetShorty() const;
 
@@ -2501,9 +2501,9 @@
       OFFSET_OF_OBJECT_MEMBER(Method, register_map_data_), false);
 }
 
-inline void Method::SetRegisterMapData(ByteArray* new_data) {
+inline void Method::SetRegisterMapData(ByteArray* data) {
   SetFieldObject(OFFSET_OF_OBJECT_MEMBER(Method, register_map_data_),
-                 new_data, false);
+                 data, false);
 }
 
 inline ByteArray* Method::GetRegisterMapHeader() const {
@@ -2511,9 +2511,9 @@
       OFFSET_OF_OBJECT_MEMBER(Method, register_map_header_), false);
 }
 
-inline void Method::SetRegisterMapHeader(ByteArray* new_header) {
+inline void Method::SetRegisterMapHeader(ByteArray* header) {
   SetFieldObject(OFFSET_OF_OBJECT_MEMBER(Method, register_map_header_),
-                 new_header, false);
+                 header, false);
 }
 
 inline String* Method::GetShorty() const {