• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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