From ba150c37d582eeeb8c11ba5245edc281cf31793c Mon Sep 17 00:00:00 2001 From: Brian Carlstrom Date: Tue, 27 Aug 2013 17:31:03 -0700 Subject: Omit OatMethodOffsets for classes without compiled code Change-Id: If0d290f4aebc778ff12d8fed017c270ad2ac3220 --- runtime/base/allocator.cc | 74 +++++++++++++++++ runtime/base/allocator.h | 41 ++++++++++ runtime/base/bit_vector.cc | 177 ++++++++++++++++++++++++++++++++++++++++ runtime/base/bit_vector.h | 134 ++++++++++++++++++++++++++++++ runtime/base/bit_vector_test.cc | 122 +++++++++++++++++++++++++++ 5 files changed, 548 insertions(+) create mode 100644 runtime/base/allocator.cc create mode 100644 runtime/base/allocator.h create mode 100644 runtime/base/bit_vector.cc create mode 100644 runtime/base/bit_vector.h create mode 100644 runtime/base/bit_vector_test.cc (limited to 'runtime/base') diff --git a/runtime/base/allocator.cc b/runtime/base/allocator.cc new file mode 100644 index 0000000..4f7753d --- /dev/null +++ b/runtime/base/allocator.cc @@ -0,0 +1,74 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "allocator.h" + +#include +#include + +#include "base/logging.h" + +namespace art { + +class MallocAllocator : public Allocator { + public: + explicit MallocAllocator() {} + ~MallocAllocator() {} + + virtual void* Alloc(size_t size) { + return calloc(sizeof(uint8_t), size); + } + + virtual void Free(void* p) { + free(p); + } + + private: + DISALLOW_COPY_AND_ASSIGN(MallocAllocator); +}; + +MallocAllocator g_malloc_allocator; + +class NoopAllocator : public Allocator { + public: + explicit NoopAllocator() {} + ~NoopAllocator() {} + + virtual void* Alloc(size_t size) { + LOG(FATAL) << "NoopAllocator::Alloc should not be called"; + return NULL; + } + + virtual void Free(void* p) { + // Noop. + } + + private: + DISALLOW_COPY_AND_ASSIGN(NoopAllocator); +}; + +NoopAllocator g_noop_allocator; + +Allocator* Allocator::GetMallocAllocator() { + return &g_malloc_allocator; +} + +Allocator* Allocator::GetNoopAllocator() { + return &g_noop_allocator; +} + + +} // namespace art diff --git a/runtime/base/allocator.h b/runtime/base/allocator.h new file mode 100644 index 0000000..917bf0b --- /dev/null +++ b/runtime/base/allocator.h @@ -0,0 +1,41 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ART_RUNTIME_BASE_ALLOCATOR_H_ +#define ART_RUNTIME_BASE_ALLOCATOR_H_ + +#include "base/macros.h" + +namespace art { + +class Allocator { + public: + static Allocator* GetMallocAllocator(); + static Allocator* GetNoopAllocator(); + + Allocator() {} + virtual ~Allocator() {} + + virtual void* Alloc(size_t) = 0; + virtual void Free(void*) = 0; + + private: + DISALLOW_COPY_AND_ASSIGN(Allocator); +}; + +} // namespace art + +#endif // ART_RUNTIME_BASE_ALLOCATOR_H_ diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc new file mode 100644 index 0000000..3b82651 --- /dev/null +++ b/runtime/base/bit_vector.cc @@ -0,0 +1,177 @@ +/* + * Copyright (C) 2011 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "bit_vector.h" + +namespace art { + +// TODO: profile to make sure this is still a win relative to just using shifted masks. +static uint32_t check_masks[32] = { + 0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, + 0x00000020, 0x00000040, 0x00000080, 0x00000100, 0x00000200, + 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000, + 0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000, + 0x00100000, 0x00200000, 0x00400000, 0x00800000, 0x01000000, + 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, + 0x40000000, 0x80000000 }; + +static inline uint32_t BitsToWords(uint32_t bits) { + return (bits + 31) >> 5; +} + +// TODO: replace excessive argument defaulting when we are at gcc 4.7 +// or later on host with delegating constructor support. Specifically, +// starts_bits and storage_size/storage are mutually exclusive. +BitVector::BitVector(uint32_t start_bits, + bool expandable, + Allocator* allocator, + uint32_t storage_size, + uint32_t* storage) + : allocator_(allocator), + expandable_(expandable), + storage_size_(storage_size), + storage_(storage) { + DCHECK_EQ(sizeof(storage_[0]), 4U); // Assuming 32-bit units. + if (storage_ == NULL) { + storage_size_ = BitsToWords(start_bits); + storage_ = static_cast(allocator_->Alloc(storage_size_ * sizeof(uint32_t))); + } +} + +BitVector::~BitVector() { + allocator_->Free(storage_); +} + +/* + * Determine whether or not the specified bit is set. + */ +bool BitVector::IsBitSet(uint32_t num) const { + DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8); + + uint32_t val = storage_[num >> 5] & check_masks[num & 0x1f]; + return (val != 0); +} + +// Mark all bits bit as "clear". +void BitVector::ClearAllBits() { + memset(storage_, 0, storage_size_ * sizeof(uint32_t)); +} + +// Mark the specified bit as "set". +/* + * TUNING: this could have pathologically bad growth/expand behavior. Make sure we're + * not using it badly or change resize mechanism. + */ +void BitVector::SetBit(uint32_t num) { + if (num >= storage_size_ * sizeof(uint32_t) * 8) { + DCHECK(expandable_) << "Attempted to expand a non-expandable bitmap to position " << num; + + /* Round up to word boundaries for "num+1" bits */ + uint32_t new_size = BitsToWords(num + 1); + DCHECK_GT(new_size, storage_size_); + uint32_t *new_storage = + static_cast(allocator_->Alloc(new_size * sizeof(uint32_t))); + memcpy(new_storage, storage_, storage_size_ * sizeof(uint32_t)); + // Zero out the new storage words. + memset(&new_storage[storage_size_], 0, (new_size - storage_size_) * sizeof(uint32_t)); + // TOTO: collect stats on space wasted because of resize. + storage_ = new_storage; + storage_size_ = new_size; + } + + storage_[num >> 5] |= check_masks[num & 0x1f]; +} + +// Mark the specified bit as "unset". +void BitVector::ClearBit(uint32_t num) { + DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8); + storage_[num >> 5] &= ~check_masks[num & 0x1f]; +} + +// Intersect with another bit vector. Sizes and expandability must be the same. +void BitVector::Intersect(const BitVector* src) { + DCHECK_EQ(storage_size_, src->GetStorageSize()); + DCHECK_EQ(expandable_, src->IsExpandable()); + for (uint32_t idx = 0; idx < storage_size_; idx++) { + storage_[idx] &= src->GetRawStorageWord(idx); + } +} + +/* + * Union with another bit vector. Sizes and expandability must be the same. + */ +void BitVector::Union(const BitVector* src) { + DCHECK_EQ(storage_size_, src->GetStorageSize()); + DCHECK_EQ(expandable_, src->IsExpandable()); + for (uint32_t idx = 0; idx < storage_size_; idx++) { + storage_[idx] |= src->GetRawStorageWord(idx); + } +} + +// Count the number of bits that are set. +uint32_t BitVector::NumSetBits() const { + uint32_t count = 0; + for (uint32_t word = 0; word < storage_size_; word++) { + count += __builtin_popcount(storage_[word]); + } + return count; +} + +// Count the number of bits that are set up through and including num. +uint32_t BitVector::NumSetBits(uint32_t num) const { + DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8); + uint32_t last_word = num >> 5; + uint32_t partial_word_bits = num & 0x1f; + + // partial_word_bits | # | | | partial_word_mask + // 00000 | 0 | 0xffffffff >> (31 - 0) | (1 << (0 + 1)) - 1 | 0x00000001 + // 00001 | 1 | 0xffffffff >> (31 - 1) | (1 << (1 + 1)) - 1 | 0x00000003 + // 00010 | 2 | 0xffffffff >> (31 - 2) | (1 << (2 + 1)) - 1 | 0x00000007 + // ..... | + // 11110 | 30 | 0xffffffff >> (31 - 30) | (1 << (30 + 1)) - 1 | 0x7fffffff + // 11111 | 31 | 0xffffffff >> (31 - 31) | last_full_word++ | 0xffffffff + uint32_t partial_word_mask = 0xffffffff >> (0x1f - partial_word_bits); + + uint32_t count = 0; + for (uint32_t word = 0; word < last_word; word++) { + count += __builtin_popcount(storage_[word]); + } + count += __builtin_popcount(storage_[last_word] & partial_word_mask); + return count; +} + +BitVector::Iterator* BitVector::GetIterator() const { + return new (allocator_) Iterator(this); +} + +/* + * Mark specified number of bits as "set". Cannot set all bits like ClearAll + * since there might be unused bits - setting those to one will confuse the + * iterator. + */ +void BitVector::SetInitialBits(uint32_t num_bits) { + DCHECK_LE(BitsToWords(num_bits), storage_size_); + uint32_t idx; + for (idx = 0; idx < (num_bits >> 5); idx++) { + storage_[idx] = -1; + } + uint32_t rem_num_bits = num_bits & 0x1f; + if (rem_num_bits) { + storage_[idx] = (1 << rem_num_bits) - 1; + } +} + +} // namespace art diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h new file mode 100644 index 0000000..74bec08 --- /dev/null +++ b/runtime/base/bit_vector.h @@ -0,0 +1,134 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ART_RUNTIME_BASE_BIT_VECTOR_H_ +#define ART_RUNTIME_BASE_BIT_VECTOR_H_ + +#include +#include + +#include "allocator.h" +#include "base/logging.h" +#include "utils.h" + +namespace art { + +/* + * Expanding bitmap, used for tracking resources. Bits are numbered starting + * from zero. All operations on a BitVector are unsynchronized. + */ +class BitVector { + public: + class Iterator { + public: + explicit Iterator(const BitVector* bit_vector) + : p_bits_(bit_vector), + bit_storage_(bit_vector->GetRawStorage()), + bit_index_(0), + bit_size_(p_bits_->storage_size_ * sizeof(uint32_t) * 8) {} + + // Return the position of the next set bit. -1 means end-of-element reached. + int32_t Next() { + // Did anything obviously change since we started? + DCHECK_EQ(bit_size_, p_bits_->GetStorageSize() * sizeof(uint32_t) * 8); + DCHECK_EQ(bit_storage_, p_bits_->GetRawStorage()); + + if (UNLIKELY(bit_index_ >= bit_size_)) return -1; + + uint32_t word_index = bit_index_ / 32; + uint32_t word = bit_storage_[word_index]; + // Mask out any bits in the first word we've already considered. + word >>= bit_index_ & 0x1f; + if (word == 0) { + bit_index_ &= ~0x1f; + do { + word_index++; + if (UNLIKELY((word_index * 32) >= bit_size_)) { + bit_index_ = bit_size_; + return -1; + } + word = bit_storage_[word_index]; + bit_index_ += 32; + } while (word == 0); + } + bit_index_ += CTZ(word) + 1; + return bit_index_ - 1; + } + + static void* operator new(size_t size, Allocator* allocator) { + return allocator->Alloc(sizeof(BitVector::Iterator)); + }; + static void operator delete(void* p) { + Iterator* it = reinterpret_cast(p); + it->p_bits_->allocator_->Free(p); + } + + private: + const BitVector* const p_bits_; + const uint32_t* const bit_storage_; + uint32_t bit_index_; // Current index (size in bits). + const uint32_t bit_size_; // Size of vector in bits. + + friend class BitVector; + }; + + BitVector(uint32_t start_bits, + bool expandable, + Allocator* allocator, + uint32_t storage_size = 0, + uint32_t* storage = NULL); + + virtual ~BitVector(); + + void SetBit(uint32_t num); + void ClearBit(uint32_t num); + bool IsBitSet(uint32_t num) const; + void ClearAllBits(); + void SetInitialBits(uint32_t num_bits); + void Copy(BitVector* src) { + memcpy(storage_, src->GetRawStorage(), sizeof(uint32_t) * storage_size_); + } + void Intersect(const BitVector* src2); + void Union(const BitVector* src); + // Are we equal to another bit vector? Note: expandability attributes must also match. + bool Equal(const BitVector* src) { + return (storage_size_ == src->GetStorageSize()) && + (expandable_ == src->IsExpandable()) && + (memcmp(storage_, src->GetRawStorage(), storage_size_ * sizeof(uint32_t)) == 0); + } + uint32_t NumSetBits() const; + uint32_t NumSetBits(uint32_t num) const; + + Iterator* GetIterator() const; + + uint32_t GetStorageSize() const { return storage_size_; } + bool IsExpandable() const { return expandable_; } + uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; } + uint32_t* GetRawStorage() { return storage_; } + const uint32_t* GetRawStorage() const { return storage_; } + size_t GetSizeOf() const { return storage_size_ * sizeof(uint32_t); } + + private: + Allocator* const allocator_; + const bool expandable_; // expand bitmap if we run out? + uint32_t storage_size_; // current size, in 32-bit words. + uint32_t* storage_; +}; + + +} // namespace art + +#endif // ART_RUNTIME_BASE_BIT_VECTOR_H_ diff --git a/runtime/base/bit_vector_test.cc b/runtime/base/bit_vector_test.cc new file mode 100644 index 0000000..d99d059 --- /dev/null +++ b/runtime/base/bit_vector_test.cc @@ -0,0 +1,122 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "UniquePtr.h" +#include "bit_vector.h" +#include "gtest/gtest.h" + +namespace art { + +TEST(BitVector, Test) { + const size_t kBits = 32; + + BitVector bv(kBits, false, Allocator::GetMallocAllocator()); + EXPECT_EQ(1U, bv.GetStorageSize()); + EXPECT_EQ(kWordSize, bv.GetSizeOf()); + EXPECT_FALSE(bv.IsExpandable()); + + EXPECT_EQ(0U, bv.NumSetBits()); + EXPECT_EQ(0U, bv.NumSetBits(0)); + EXPECT_EQ(0U, bv.NumSetBits(kBits - 1)); + for (size_t i = 0; i < kBits; i++) { + EXPECT_FALSE(bv.IsBitSet(i)); + } + EXPECT_EQ(0U, bv.GetRawStorageWord(0)); + EXPECT_EQ(0U, *bv.GetRawStorage()); + + BitVector::Iterator empty_iterator(&bv); + EXPECT_EQ(-1, empty_iterator.Next()); + + UniquePtr empty_iterator_on_heap(bv.GetIterator()); + EXPECT_EQ(-1, empty_iterator_on_heap->Next()); + + bv.SetBit(0); + bv.SetBit(kBits - 1); + EXPECT_EQ(2U, bv.NumSetBits()); + EXPECT_EQ(1U, bv.NumSetBits(0)); + EXPECT_EQ(2U, bv.NumSetBits(kBits - 1)); + EXPECT_TRUE(bv.IsBitSet(0)); + for (size_t i = 1; i < kBits - 1; i++) { + EXPECT_FALSE(bv.IsBitSet(i)); + } + EXPECT_TRUE(bv.IsBitSet(kBits - 1)); + EXPECT_EQ(0x80000001U, bv.GetRawStorageWord(0)); + EXPECT_EQ(0x80000001U, *bv.GetRawStorage()); + + BitVector::Iterator iterator(&bv); + EXPECT_EQ(0, iterator.Next()); + EXPECT_EQ(static_cast(kBits - 1), iterator.Next()); + EXPECT_EQ(-1, iterator.Next()); +} + +TEST(BitVector, NoopAllocator) { + const uint32_t kWords = 2; + + uint32_t bits[kWords]; + memset(bits, 0, sizeof(bits)); + + BitVector bv(0U, false, Allocator::GetNoopAllocator(), kWords, bits); + EXPECT_EQ(kWords, bv.GetStorageSize()); + EXPECT_EQ(kWords * kWordSize, bv.GetSizeOf()); + EXPECT_EQ(bits, bv.GetRawStorage()); + EXPECT_EQ(0U, bv.NumSetBits()); + + bv.SetBit(8); + EXPECT_EQ(1U, bv.NumSetBits()); + EXPECT_EQ(0x00000100U, bv.GetRawStorageWord(0)); + EXPECT_EQ(0x00000000U, bv.GetRawStorageWord(1)); + EXPECT_EQ(1U, bv.NumSetBits()); + + bv.SetBit(16); + EXPECT_EQ(2U, bv.NumSetBits()); + EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0)); + EXPECT_EQ(0x00000000U, bv.GetRawStorageWord(1)); + EXPECT_EQ(2U, bv.NumSetBits()); + + bv.SetBit(32); + EXPECT_EQ(3U, bv.NumSetBits()); + EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0)); + EXPECT_EQ(0x00000001U, bv.GetRawStorageWord(1)); + EXPECT_EQ(3U, bv.NumSetBits()); + + bv.SetBit(48); + EXPECT_EQ(4U, bv.NumSetBits()); + EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0)); + EXPECT_EQ(0x00010001U, bv.GetRawStorageWord(1)); + EXPECT_EQ(4U, bv.NumSetBits()); + + EXPECT_EQ(0U, bv.NumSetBits(0)); + + EXPECT_EQ(0U, bv.NumSetBits(7)); + EXPECT_EQ(1U, bv.NumSetBits(8)); + EXPECT_EQ(1U, bv.NumSetBits(9)); + + EXPECT_EQ(1U, bv.NumSetBits(15)); + EXPECT_EQ(2U, bv.NumSetBits(16)); + EXPECT_EQ(2U, bv.NumSetBits(17)); + + EXPECT_EQ(2U, bv.NumSetBits(31)); + EXPECT_EQ(3U, bv.NumSetBits(32)); + EXPECT_EQ(3U, bv.NumSetBits(33)); + + EXPECT_EQ(3U, bv.NumSetBits(47)); + EXPECT_EQ(4U, bv.NumSetBits(48)); + EXPECT_EQ(4U, bv.NumSetBits(49)); + + EXPECT_EQ(4U, bv.NumSetBits(63)); +} + +} // namespace art -- cgit v1.1