10c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers/* 20c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers * Copyright (C) 2012 The Android Open Source Project 30c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers * 40c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers * Licensed under the Apache License, Version 2.0 (the "License"); 50c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers * you may not use this file except in compliance with the License. 60c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers * You may obtain a copy of the License at 70c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers * 80c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers * http://www.apache.org/licenses/LICENSE-2.0 90c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers * 100c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers * Unless required by applicable law or agreed to in writing, software 110c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers * distributed under the License is distributed on an "AS IS" BASIS, 120c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 130c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers * See the License for the specific language governing permissions and 140c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers * limitations under the License. 150c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers */ 160c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 17fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#ifndef ART_RUNTIME_GC_MAP_H_ 18fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#define ART_RUNTIME_GC_MAP_H_ 190c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 200c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers#include <stdint.h> 210c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 2207ed66b5ae659c452cbe1ab20c3dbf1d6f546461Elliott Hughes#include "base/logging.h" 2307ed66b5ae659c452cbe1ab20c3dbf1d6f546461Elliott Hughes#include "base/macros.h" 2407ed66b5ae659c452cbe1ab20c3dbf1d6f546461Elliott Hughes 250c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogersnamespace art { 260c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 270c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers// Lightweight wrapper for native PC offset to reference bit maps. 280c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogersclass NativePcOffsetToReferenceMap { 290c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers public: 3093ba893c20532990a430741e0a97212900094e8cBrian Carlstrom explicit NativePcOffsetToReferenceMap(const uint8_t* data) : data_(data) { 310c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers CHECK(data_ != NULL); 320c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers } 330c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 340c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers // The number of entries in the table. 350c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers size_t NumEntries() const { 360c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers return data_[2] | (data_[3] << 8); 370c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers } 380c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 390c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers // Return address of bitmap encoding what are live references. 400c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers const uint8_t* GetBitMap(size_t index) const { 410c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers size_t entry_offset = index * EntryWidth(); 420c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers return &Table()[entry_offset + NativeOffsetWidth()]; 430c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers } 440c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 450c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers // Get the native PC encoded in the table at the given index. 460c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers uintptr_t GetNativePcOffset(size_t index) const { 470c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers size_t entry_offset = index * EntryWidth(); 480c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers uintptr_t result = 0; 490c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers for (size_t i = 0; i < NativeOffsetWidth(); ++i) { 500c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers result |= Table()[entry_offset + i] << (i * 8); 510c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers } 520c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers return result; 530c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers } 540c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 55b23a7729cf7855fa05345d03a4d84111d5ec7172Ian Rogers // Does the given offset have an entry? 56b23a7729cf7855fa05345d03a4d84111d5ec7172Ian Rogers bool HasEntry(uintptr_t native_pc_offset) { 57b23a7729cf7855fa05345d03a4d84111d5ec7172Ian Rogers for (size_t i = 0; i < NumEntries(); ++i) { 58b23a7729cf7855fa05345d03a4d84111d5ec7172Ian Rogers if (GetNativePcOffset(i) == native_pc_offset) { 59b23a7729cf7855fa05345d03a4d84111d5ec7172Ian Rogers return true; 60b23a7729cf7855fa05345d03a4d84111d5ec7172Ian Rogers } 61b23a7729cf7855fa05345d03a4d84111d5ec7172Ian Rogers } 62b23a7729cf7855fa05345d03a4d84111d5ec7172Ian Rogers return false; 63b23a7729cf7855fa05345d03a4d84111d5ec7172Ian Rogers } 64b23a7729cf7855fa05345d03a4d84111d5ec7172Ian Rogers 650c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers // Finds the bitmap associated with the native pc offset. 660c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers const uint8_t* FindBitMap(uintptr_t native_pc_offset) { 670c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers size_t num_entries = NumEntries(); 680c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers size_t index = Hash(native_pc_offset) % num_entries; 6962d6c772205b8859f0ebf7ad105402ec4c3e2e01Ian Rogers size_t misses = 0; 700c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers while (GetNativePcOffset(index) != native_pc_offset) { 710c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers index = (index + 1) % num_entries; 7262d6c772205b8859f0ebf7ad105402ec4c3e2e01Ian Rogers misses++; 7362d6c772205b8859f0ebf7ad105402ec4c3e2e01Ian Rogers DCHECK_LT(misses, num_entries) << "Failed to find offset: " << native_pc_offset; 740c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers } 750c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers return GetBitMap(index); 760c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers } 770c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 780c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers static uint32_t Hash(uint32_t native_offset) { 790c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers uint32_t hash = native_offset; 800c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers hash ^= (hash >> 20) ^ (hash >> 12); 810c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers hash ^= (hash >> 7) ^ (hash >> 4); 820c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers return hash; 830c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers } 840c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 850c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers // The number of bytes used to encode registers. 860c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers size_t RegWidth() const { 87cbd6d44c0a94f3d26671b5325aa21bbf1335ffe8buzbee return (static_cast<size_t>(data_[0]) | (static_cast<size_t>(data_[1]) << 8)) >> 3; 880c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers } 890c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 900c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers private: 910c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers // Skip the size information at the beginning of data. 920c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers const uint8_t* Table() const { 930c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers return data_ + 4; 940c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers } 950c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 960c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers // Number of bytes used to encode a native offset. 970c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers size_t NativeOffsetWidth() const { 98000d724207b4ff32fcbc9744da76d2f594675eedIan Rogers return data_[0] & 7; 990c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers } 1000c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 1010c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers // The width of an entry in the table. 1020c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers size_t EntryWidth() const { 1030c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers return NativeOffsetWidth() + RegWidth(); 1040c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers } 1050c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 1060c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers const uint8_t* const data_; // The header and table data 1070c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers}; 1080c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 1090c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers} // namespace art 1100c7abda482f53db3d153c073d1c7a145f84e0626Ian Rogers 111fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#endif // ART_RUNTIME_GC_MAP_H_ 112