1 /* 2 * Copyright (C) 2022 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_DEX2OAT_LINKER_CODE_INFO_TABLE_DEDUPER_H_ 18 #define ART_DEX2OAT_LINKER_CODE_INFO_TABLE_DEDUPER_H_ 19 20 #include <vector> 21 22 #include "base/bit_memory_region.h" 23 #include "base/hash_set.h" 24 25 namespace art { 26 namespace linker { 27 28 class CodeInfoTableDeduper { 29 public: CodeInfoTableDeduper(std::vector<uint8_t> * output)30 explicit CodeInfoTableDeduper(std::vector<uint8_t>* output) 31 : writer_(output), 32 dedupe_set_(kMinLoadFactor, 33 kMaxLoadFactor, 34 DedupeSetEntryHash(output), 35 DedupeSetEntryEquals(output)) { 36 DCHECK_EQ(output->size(), 0u); 37 } 38 39 void ReserveDedupeBuffer(size_t num_code_infos); 40 41 // Copy CodeInfo into output while de-duplicating the internal bit tables. 42 // It returns the byte offset of the copied CodeInfo within the output. 43 size_t Dedupe(const uint8_t* code_info); 44 45 private: 46 struct DedupeSetEntry { 47 uint32_t bit_start; 48 uint32_t bit_size; 49 }; 50 51 class DedupeSetEntryEmpty { 52 public: MakeEmpty(DedupeSetEntry & item)53 void MakeEmpty(DedupeSetEntry& item) const { 54 item = {0u, 0u}; 55 } IsEmpty(const DedupeSetEntry & item)56 bool IsEmpty(const DedupeSetEntry& item) const { 57 return item.bit_size == 0u; 58 } 59 }; 60 61 class DedupeSetEntryHash { 62 public: DedupeSetEntryHash(std::vector<uint8_t> * output)63 explicit DedupeSetEntryHash(std::vector<uint8_t>* output) : output_(output) {} 64 operator()65 uint32_t operator()(const DedupeSetEntry& item) const { 66 return DataHash()(BitMemoryRegion(output_->data(), item.bit_start, item.bit_size)); 67 } 68 69 private: 70 std::vector<uint8_t>* const output_; 71 }; 72 73 class DedupeSetEntryEquals { 74 public: DedupeSetEntryEquals(std::vector<uint8_t> * output)75 explicit DedupeSetEntryEquals(std::vector<uint8_t>* output) : output_(output) {} 76 operator()77 bool operator()(const DedupeSetEntry& lhs, const DedupeSetEntry& rhs) const { 78 DCHECK_NE(lhs.bit_size, 0u); 79 DCHECK_NE(rhs.bit_size, 0u); 80 return lhs.bit_size == rhs.bit_size && 81 BitMemoryRegion::Equals( 82 BitMemoryRegion(output_->data(), lhs.bit_start, lhs.bit_size), 83 BitMemoryRegion(output_->data(), rhs.bit_start, rhs.bit_size)); 84 } 85 86 private: 87 std::vector<uint8_t>* const output_; 88 }; 89 90 using DedupeSet = 91 HashSet<DedupeSetEntry, DedupeSetEntryEmpty, DedupeSetEntryHash, DedupeSetEntryEquals>; 92 93 static constexpr double kMinLoadFactor = 0.5; 94 static constexpr double kMaxLoadFactor = 0.75; 95 96 BitMemoryWriter<std::vector<uint8_t>> writer_; 97 98 // Deduplicate at BitTable level. Entries describe ranges in `output`, see constructor. 99 DedupeSet dedupe_set_; 100 }; 101 102 } // namespace linker 103 } // namespace art 104 105 #endif // ART_DEX2OAT_LINKER_CODE_INFO_TABLE_DEDUPER_H_ 106