192cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray/* 292cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray * Copyright (C) 2014 The Android Open Source Project 392cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray * 492cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray * Licensed under the Apache License, Version 2.0 (the "License"); 592cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray * you may not use this file except in compliance with the License. 692cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray * You may obtain a copy of the License at 792cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray * 892cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray * http://www.apache.org/licenses/LICENSE-2.0 992cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray * 1092cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray * Unless required by applicable law or agreed to in writing, software 1192cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray * distributed under the License is distributed on an "AS IS" BASIS, 1292cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1392cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray * See the License for the specific language governing permissions and 1492cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray * limitations under the License. 1592cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray */ 1692cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray 1792cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray#ifndef ART_COMPILER_GC_MAP_BUILDER_H_ 1892cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray#define ART_COMPILER_GC_MAP_BUILDER_H_ 1992cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray 2092cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray#include <vector> 2192cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray 2292cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray#include "gc_map.h" 2331806a3e1e55cb68ea03b1b3b8edd8441c090d82Vladimir Marko#include "utils.h" 2492cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray 2592cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffraynamespace art { 2692cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray 2792cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffrayclass GcMapBuilder { 2892cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray public: 2931806a3e1e55cb68ea03b1b3b8edd8441c090d82Vladimir Marko GcMapBuilder(std::vector<uint8_t>* table, size_t entries, uint32_t max_native_offset, 3031806a3e1e55cb68ea03b1b3b8edd8441c090d82Vladimir Marko size_t references_width) 3131806a3e1e55cb68ea03b1b3b8edd8441c090d82Vladimir Marko : entries_(entries), references_width_(entries != 0u ? references_width : 0u), 3231806a3e1e55cb68ea03b1b3b8edd8441c090d82Vladimir Marko native_offset_width_(entries != 0 && max_native_offset != 0 3331806a3e1e55cb68ea03b1b3b8edd8441c090d82Vladimir Marko ? sizeof(max_native_offset) - CLZ(max_native_offset) / 8u 3431806a3e1e55cb68ea03b1b3b8edd8441c090d82Vladimir Marko : 0u), 3531806a3e1e55cb68ea03b1b3b8edd8441c090d82Vladimir Marko in_use_(entries), table_(table) { 3692cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray // Resize table and set up header. 3792cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray table->resize((EntryWidth() * entries) + sizeof(uint32_t)); 3892cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray CHECK_LT(native_offset_width_, 1U << 3); 3992cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray (*table)[0] = native_offset_width_ & 7; 4092cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray CHECK_LT(references_width_, 1U << 13); 4192cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray (*table)[0] |= (references_width_ << 3) & 0xFF; 4292cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray (*table)[1] = (references_width_ >> 5) & 0xFF; 4392cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray CHECK_LT(entries, 1U << 16); 4492cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray (*table)[2] = entries & 0xFF; 4592cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray (*table)[3] = (entries >> 8) & 0xFF; 4692cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray } 4792cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray 4892cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray void AddEntry(uint32_t native_offset, const uint8_t* references) { 4992cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray size_t table_index = TableIndex(native_offset); 5092cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray while (in_use_[table_index]) { 5192cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray table_index = (table_index + 1) % entries_; 5292cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray } 5392cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray in_use_[table_index] = true; 5492cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray SetCodeOffset(table_index, native_offset); 5592cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray DCHECK_EQ(native_offset, GetCodeOffset(table_index)); 5692cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray SetReferences(table_index, references); 5792cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray } 5892cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray 5992cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray private: 6092cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray size_t TableIndex(uint32_t native_offset) { 6192cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray return NativePcOffsetToReferenceMap::Hash(native_offset) % entries_; 6292cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray } 6392cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray 6492cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray uint32_t GetCodeOffset(size_t table_index) { 6592cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray uint32_t native_offset = 0; 6692cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray size_t table_offset = (table_index * EntryWidth()) + sizeof(uint32_t); 6792cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray for (size_t i = 0; i < native_offset_width_; i++) { 6892cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray native_offset |= (*table_)[table_offset + i] << (i * 8); 6992cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray } 7092cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray return native_offset; 7192cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray } 7292cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray 7392cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray void SetCodeOffset(size_t table_index, uint32_t native_offset) { 7492cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray size_t table_offset = (table_index * EntryWidth()) + sizeof(uint32_t); 7592cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray for (size_t i = 0; i < native_offset_width_; i++) { 7692cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray (*table_)[table_offset + i] = (native_offset >> (i * 8)) & 0xFF; 7792cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray } 7892cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray } 7992cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray 8092cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray void SetReferences(size_t table_index, const uint8_t* references) { 8192cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray size_t table_offset = (table_index * EntryWidth()) + sizeof(uint32_t); 8292cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray memcpy(&(*table_)[table_offset + native_offset_width_], references, references_width_); 8392cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray } 8492cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray 8592cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray size_t EntryWidth() const { 8692cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray return native_offset_width_ + references_width_; 8792cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray } 8892cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray 8992cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray // Number of entries in the table. 9092cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray const size_t entries_; 9192cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray // Number of bytes used to encode the reference bitmap. 9292cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray const size_t references_width_; 9392cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray // Number of bytes used to encode a native offset. 9431806a3e1e55cb68ea03b1b3b8edd8441c090d82Vladimir Marko const size_t native_offset_width_; 9592cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray // Entries that are in use. 9692cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray std::vector<bool> in_use_; 9792cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray // The table we're building. 9892cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray std::vector<uint8_t>* const table_; 9992cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray}; 10092cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray 10192cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray} // namespace art 10292cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray 10392cf83e001357329cbf41fa15a6e053fab6f4933Nicolas Geoffray#endif // ART_COMPILER_GC_MAP_BUILDER_H_ 104