1 /* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_RUNTIME_GC_MAP_H_ 18 #define ART_RUNTIME_GC_MAP_H_ 19 20 #include <stdint.h> 21 22 #include "base/logging.h" 23 #include "base/macros.h" 24 25 namespace art { 26 27 // Lightweight wrapper for native PC offset to reference bit maps. 28 class NativePcOffsetToReferenceMap { 29 public: NativePcOffsetToReferenceMap(const uint8_t * data)30 explicit NativePcOffsetToReferenceMap(const uint8_t* data) : data_(data) { 31 CHECK(data_ != NULL); 32 } 33 34 // The number of entries in the table. NumEntries()35 size_t NumEntries() const { 36 return data_[2] | (data_[3] << 8); 37 } 38 39 // Return address of bitmap encoding what are live references. GetBitMap(size_t index)40 const uint8_t* GetBitMap(size_t index) const { 41 size_t entry_offset = index * EntryWidth(); 42 return &Table()[entry_offset + NativeOffsetWidth()]; 43 } 44 45 // Get the native PC encoded in the table at the given index. GetNativePcOffset(size_t index)46 uintptr_t GetNativePcOffset(size_t index) const { 47 size_t entry_offset = index * EntryWidth(); 48 uintptr_t result = 0; 49 for (size_t i = 0; i < NativeOffsetWidth(); ++i) { 50 result |= Table()[entry_offset + i] << (i * 8); 51 } 52 return result; 53 } 54 55 // Does the given offset have an entry? HasEntry(uintptr_t native_pc_offset)56 bool HasEntry(uintptr_t native_pc_offset) { 57 for (size_t i = 0; i < NumEntries(); ++i) { 58 if (GetNativePcOffset(i) == native_pc_offset) { 59 return true; 60 } 61 } 62 return false; 63 } 64 65 // Finds the bitmap associated with the native pc offset. FindBitMap(uintptr_t native_pc_offset)66 const uint8_t* FindBitMap(uintptr_t native_pc_offset) { 67 size_t num_entries = NumEntries(); 68 size_t index = Hash(native_pc_offset) % num_entries; 69 size_t misses = 0; 70 while (GetNativePcOffset(index) != native_pc_offset) { 71 index = (index + 1) % num_entries; 72 misses++; 73 DCHECK_LT(misses, num_entries) << "Failed to find offset: " << native_pc_offset; 74 } 75 return GetBitMap(index); 76 } 77 Hash(uint32_t native_offset)78 static uint32_t Hash(uint32_t native_offset) { 79 uint32_t hash = native_offset; 80 hash ^= (hash >> 20) ^ (hash >> 12); 81 hash ^= (hash >> 7) ^ (hash >> 4); 82 return hash; 83 } 84 85 // The number of bytes used to encode registers. RegWidth()86 size_t RegWidth() const { 87 return (static_cast<size_t>(data_[0]) | (static_cast<size_t>(data_[1]) << 8)) >> 3; 88 } 89 90 private: 91 // Skip the size information at the beginning of data. Table()92 const uint8_t* Table() const { 93 return data_ + 4; 94 } 95 96 // Number of bytes used to encode a native offset. NativeOffsetWidth()97 size_t NativeOffsetWidth() const { 98 return data_[0] & 7; 99 } 100 101 // The width of an entry in the table. EntryWidth()102 size_t EntryWidth() const { 103 return NativeOffsetWidth() + RegWidth(); 104 } 105 106 const uint8_t* const data_; // The header and table data 107 }; 108 109 } // namespace art 110 111 #endif // ART_RUNTIME_GC_MAP_H_ 112