From 5afa08f95d43dd24fb4b3d7a08aa1ec23386ad54 Mon Sep 17 00:00:00 2001
From: Jean Christophe Beyler <jean.christophe.beyler@intel.com>
Date: Tue, 15 Apr 2014 15:54:35 -0700
Subject: ART: Bitvector extensions for dumping and size handling

- Added dumping functions and the ensure size and clear function.
- Fixed a bug in union where if a bit is not set in the source, an buffer
   overflow can occur later down.

Change-Id: Iff40529f3a8970a1ce2dd5c591f659f71924dea3
Signed-off-by: Jean Christophe Beyler <jean.christophe.beyler@intel.com>
Signed-off-by: Razvan A Lupusoru <razvan.a.lupusoru@intel.com>
Signed-off-by: Yixin Shou <yixin.shou@intel.com>
Signed-off-by: Chao-ying Fu <chao-ying.fu@intel.com>
Signed-off-by: Udayan Banerji <udayan.banerji@intel.com>
---
 runtime/base/bit_vector.cc | 80 ++++++++++++++++++++++++++++++++++++----------
 runtime/base/bit_vector.h  |  8 +++++
 2 files changed, 72 insertions(+), 16 deletions(-)

(limited to 'runtime/base')

diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc
index d8ef962..12c0352 100644
--- a/runtime/base/bit_vector.cc
+++ b/runtime/base/bit_vector.cc
@@ -157,33 +157,27 @@ void BitVector::Intersect(const BitVector* src) {
  * Union with another bit vector.
  */
 void BitVector::Union(const BitVector* src) {
-  uint32_t src_size = src->storage_size_;
+  // Get the highest bit to determine how much we need to expand.
+  int highest_bit = src->GetHighestBitSet();
+
+  // If src has no bit set, we are done: there is no need for a union with src.
+  if (highest_bit == -1) {
+    return;
+  }
 
-  // Get our size, we use this variable for the last loop of the method:
-  //   - It can change in the if block if src is of a different size.
-  uint32_t size = storage_size_;
+  // Update src_size to how many cells we actually care about: where the bit is + 1.
+  uint32_t src_size = BitsToWords(highest_bit + 1);
 
   // Is the storage size smaller than src's?
   if (storage_size_ < src_size) {
-    // Get the highest bit to determine how much we need to expand.
-    int highest_bit = src->GetHighestBitSet();
-
-    // If src has no bit set, we are done: there is no need for a union with src.
-    if (highest_bit == -1) {
-      return;
-    }
-
     // Set it to reallocate.
     SetBit(highest_bit);
 
     // Paranoid: storage size should be big enough to hold this bit now.
     DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * sizeof(*(storage_)) * 8);
-
-    //  Update the size, our size can now not be bigger than the src size
-    size = storage_size_;
   }
 
-  for (uint32_t idx = 0; idx < size; idx++) {
+  for (uint32_t idx = 0; idx < src_size; idx++) {
     storage_[idx] |= src->GetRawStorageWord(idx);
   }
 }
@@ -284,6 +278,23 @@ int BitVector::GetHighestBitSet() const {
   return -1;
 }
 
+bool BitVector::EnsureSizeAndClear(unsigned int num) {
+  // Check if the bitvector is expandable.
+  if (IsExpandable() == false) {
+    return false;
+  }
+
+  if (num > 0) {
+    // Now try to expand by setting the last bit.
+    SetBit(num - 1);
+  }
+
+  // We must clear all bits as per our specification.
+  ClearAllBits();
+
+  return true;
+}
+
 void BitVector::Copy(const BitVector *src) {
   // Get highest bit set, we only need to copy till then.
   int highest_bit = src->GetHighestBitSet();
@@ -328,4 +339,41 @@ uint32_t BitVector::NumSetBits(const uint32_t* storage, uint32_t end) {
   return count;
 }
 
+void BitVector::Dump(std::ostream& os, const char *prefix) {
+  std::ostringstream buffer;
+  DumpHelper(buffer, prefix);
+  os << buffer << std::endl;
+}
+
+void BitVector::DumpDot(FILE* file, const char* prefix, bool last_entry) {
+  std::ostringstream buffer;
+  Dump(buffer, prefix);
+
+  // Now print it to the file.
+  fprintf(file, "    {%s}", buffer.str().c_str());
+
+  // If it isn't the last entry, add a |.
+  if (last_entry == false) {
+    fprintf(file, "|");
+  }
+
+  // Add the \n.
+  fprintf(file, "\\\n");
+}
+
+void BitVector::DumpHelper(std::ostringstream& buffer, const char* prefix) {
+  // Initialize it.
+  if (prefix != nullptr) {
+    buffer << prefix;
+  }
+
+  int max = GetHighestBitSet();
+
+  for (int i = 0; i <= max; i++) {
+    if (IsBitSet(i)) {
+      buffer << i << " ";
+    }
+  }
+}
+
 }  // namespace art
diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h
index a496dbd..db29c49 100644
--- a/runtime/base/bit_vector.h
+++ b/runtime/base/bit_vector.h
@@ -142,6 +142,14 @@ class BitVector {
     // Number of bits set in range [0, end) in storage. (No range check.)
     static uint32_t NumSetBits(const uint32_t* storage, uint32_t end);
 
+    bool EnsureSizeAndClear(unsigned int num);
+
+    void Dump(std::ostream& os, const char* prefix);
+    void DumpDot(FILE* file, const char* prefix, bool last_entry = false);
+
+  protected:
+    void DumpHelper(std::ostringstream& buffer, const char* prefix);
+
   private:
     Allocator* const allocator_;
     const bool expandable_;         // expand bitmap if we run out?
-- 
cgit v1.1