1 /*
2  * Copyright (C) 2013 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_COMPILER_UTILS_DEDUPE_SET_H_
18 #define ART_COMPILER_UTILS_DEDUPE_SET_H_
19 
20 #include <algorithm>
21 #include <inttypes.h>
22 #include <memory>
23 #include <set>
24 #include <string>
25 
26 #include "base/mutex.h"
27 #include "base/stl_util.h"
28 #include "base/stringprintf.h"
29 #include "base/time_utils.h"
30 #include "utils/swap_space.h"
31 
32 namespace art {
33 
34 // A set of Keys that support a HashFunc returning HashType. Used to find duplicates of Key in the
35 // Add method. The data-structure is thread-safe through the use of internal locks, it also
36 // supports the lock being sharded.
37 template <typename InKey, typename StoreKey, typename HashType, typename HashFunc,
38           HashType kShard = 1>
39 class DedupeSet {
40   typedef std::pair<HashType, const InKey*> HashedInKey;
41   struct HashedKey {
42     StoreKey* store_ptr;
43     union {
44       HashType store_hash;        // Valid if store_ptr != null.
45       const HashedInKey* in_key;  // Valid if store_ptr == null.
46     };
47   };
48 
49   class Comparator {
50    public:
operator()51     bool operator()(const HashedKey& a, const HashedKey& b) const {
52       HashType a_hash = (a.store_ptr != nullptr) ? a.store_hash : a.in_key->first;
53       HashType b_hash = (b.store_ptr != nullptr) ? b.store_hash : b.in_key->first;
54       if (a_hash != b_hash) {
55         return a_hash < b_hash;
56       }
57       if (a.store_ptr != nullptr && b.store_ptr != nullptr) {
58         return std::lexicographical_compare(a.store_ptr->begin(), a.store_ptr->end(),
59                                             b.store_ptr->begin(), b.store_ptr->end());
60       } else if (a.store_ptr != nullptr && b.store_ptr == nullptr) {
61         return std::lexicographical_compare(a.store_ptr->begin(), a.store_ptr->end(),
62                                             b.in_key->second->begin(), b.in_key->second->end());
63       } else if (a.store_ptr == nullptr && b.store_ptr != nullptr) {
64         return std::lexicographical_compare(a.in_key->second->begin(), a.in_key->second->end(),
65                                             b.store_ptr->begin(), b.store_ptr->end());
66       } else {
67         return std::lexicographical_compare(a.in_key->second->begin(), a.in_key->second->end(),
68                                             b.in_key->second->begin(), b.in_key->second->end());
69       }
70     }
71   };
72 
73  public:
Add(Thread * self,const InKey & key)74   StoreKey* Add(Thread* self, const InKey& key) {
75     uint64_t hash_start;
76     if (kIsDebugBuild) {
77       hash_start = NanoTime();
78     }
79     HashType raw_hash = HashFunc()(key);
80     if (kIsDebugBuild) {
81       uint64_t hash_end = NanoTime();
82       hash_time_ += hash_end - hash_start;
83     }
84     HashType shard_hash = raw_hash / kShard;
85     HashType shard_bin = raw_hash % kShard;
86     HashedInKey hashed_in_key(shard_hash, &key);
87     HashedKey hashed_key;
88     hashed_key.store_ptr = nullptr;
89     hashed_key.in_key = &hashed_in_key;
90     MutexLock lock(self, *lock_[shard_bin]);
91     auto it = keys_[shard_bin].find(hashed_key);
92     if (it != keys_[shard_bin].end()) {
93       DCHECK(it->store_ptr != nullptr);
94       return it->store_ptr;
95     }
96     hashed_key.store_ptr = CreateStoreKey(key);
97     hashed_key.store_hash = shard_hash;
98     keys_[shard_bin].insert(hashed_key);
99     return hashed_key.store_ptr;
100   }
101 
DedupeSet(const char * set_name,SwapAllocator<void> & alloc)102   explicit DedupeSet(const char* set_name, SwapAllocator<void>& alloc)
103       : allocator_(alloc), hash_time_(0) {
104     for (HashType i = 0; i < kShard; ++i) {
105       std::ostringstream oss;
106       oss << set_name << " lock " << i;
107       lock_name_[i] = oss.str();
108       lock_[i].reset(new Mutex(lock_name_[i].c_str()));
109     }
110   }
111 
~DedupeSet()112   ~DedupeSet() {
113     // Have to manually free all pointers.
114     for (auto& shard : keys_) {
115       for (const auto& hashed_key : shard) {
116         DCHECK(hashed_key.store_ptr != nullptr);
117         DeleteStoreKey(hashed_key.store_ptr);
118       }
119     }
120   }
121 
DumpStats()122   std::string DumpStats() const {
123     size_t collision_sum = 0;
124     size_t collision_max = 0;
125     for (HashType shard = 0; shard < kShard; ++shard) {
126       HashType last_hash = 0;
127       size_t collision_cur_max = 0;
128       for (const HashedKey& key : keys_[shard]) {
129         DCHECK(key.store_ptr != nullptr);
130         if (key.store_hash == last_hash) {
131           collision_cur_max++;
132           if (collision_cur_max > 1) {
133             collision_sum++;
134             if (collision_cur_max > collision_max) {
135               collision_max = collision_cur_max;
136             }
137           }
138         } else {
139           collision_cur_max = 1;
140           last_hash = key.store_hash;
141         }
142       }
143     }
144     return StringPrintf("%zu collisions, %zu max bucket size, %" PRIu64 " ns hash time",
145                         collision_sum, collision_max, hash_time_);
146   }
147 
148  private:
CreateStoreKey(const InKey & key)149   StoreKey* CreateStoreKey(const InKey& key) {
150     StoreKey* ret = allocator_.allocate(1);
151     allocator_.construct(ret, key.begin(), key.end(), allocator_);
152     return ret;
153   }
154 
DeleteStoreKey(StoreKey * key)155   void DeleteStoreKey(StoreKey* key) {
156     SwapAllocator<StoreKey> alloc(allocator_);
157     alloc.destroy(key);
158     alloc.deallocate(key, 1);
159   }
160 
161   std::string lock_name_[kShard];
162   std::unique_ptr<Mutex> lock_[kShard];
163   std::set<HashedKey, Comparator> keys_[kShard];
164   SwapAllocator<StoreKey> allocator_;
165   uint64_t hash_time_;
166 
167   DISALLOW_COPY_AND_ASSIGN(DedupeSet);
168 };
169 
170 }  // namespace art
171 
172 #endif  // ART_COMPILER_UTILS_DEDUPE_SET_H_
173