1 : // Copyright 2014 Google Inc. All Rights Reserved.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 : //
15 : // Internal implementation of a sharded quarantine. This file is not
16 : // meant to be included directly.
17 :
18 : #ifndef SYZYGY_AGENT_ASAN_QUARANTINES_SHARDED_QUARANTINE_IMPL_H_
19 : #define SYZYGY_AGENT_ASAN_QUARANTINES_SHARDED_QUARANTINE_IMPL_H_
20 :
21 : #include "string.h"
22 :
23 : namespace agent {
24 : namespace asan {
25 : namespace quarantines {
26 :
27 : namespace detail {
28 :
29 : // Given a 32-bit integer, converts it to an integer in the range
30 : // [0, kShardingFactor). Since the input range is unknown and may not use
31 : // the entirety of the 32-bits, this first uses a bit mixing function.
32 : template<size_t kShardingFactor>
33 E : size_t ShardedQuarantineHash(size_t a) {
34 : // Simple full-avalanche (any input bit can affect every output bit)
35 : // bit mixing. See: http://burtleburtle.net/bob/hash/integer.html
36 E : a -= (a << 6);
37 E : a ^= (a >> 17);
38 E : a -= (a << 9);
39 E : a ^= (a << 4);
40 E : a -= (a << 3);
41 E : a ^= (a << 10);
42 E : a ^= (a >> 15);
43 E : return a % kShardingFactor;
44 E : }
45 :
46 : } // namespace detail
47 :
48 : template<typename OT, typename SFT, typename HFT, size_t SF>
49 E : ShardedQuarantine<OT, SFT, HFT, SF>::ShardedQuarantine() {
50 : static_assert(kShardingFactor >= 1, "Invalid sharding factor.");
51 E : ::memset(heads_, 0, sizeof(heads_));
52 E : ::memset(tails_, 0, sizeof(tails_));
53 E : }
54 :
55 : template<typename OT, typename SFT, typename HFT, size_t SF>
56 : ShardedQuarantine<OT, SFT, HFT, SF>::ShardedQuarantine(
57 : const HashFunctor& hash_functor)
58 : : hash_functor_(hash_functor) {
59 : static_assert(kShardingFactor >= 1, "Invalid sharding factor.");
60 : ::memset(heads_, 0, sizeof(heads_));
61 : ::memset(tails_, 0, sizeof(tails_));
62 : }
63 :
64 : template<typename OT, typename SFT, typename HFT, size_t SF>
65 E : bool ShardedQuarantine<OT, SFT, HFT, SF>::PushImpl(const Object& object) {
66 E : size_t hash = hash_functor_(object);
67 E : size_t shard = detail::ShardedQuarantineHash<kShardingFactor>(hash);
68 : // Make sure the corresponding lock is held.
69 E : locks_[shard].AssertAcquired();
70 :
71 E : Node* node = node_caches_[shard].Allocate(1);
72 E : if (node == NULL)
73 i : return false;
74 E : node->object = object;
75 E : node->next = NULL;
76 :
77 : // Append the node to the tail of this shard.
78 E : if (tails_[shard] != NULL) {
79 E : DCHECK_NE(static_cast<Node*>(NULL), heads_[shard]);
80 E : tails_[shard]->next = node;
81 E : tails_[shard] = node;
82 E : } else {
83 E : DCHECK_EQ(static_cast<Node*>(NULL), heads_[shard]);
84 E : heads_[shard] = node;
85 E : tails_[shard] = node;
86 : }
87 :
88 E : return true;
89 E : }
90 :
91 : template<typename OT, typename SFT, typename HFT, size_t SF>
92 E : bool ShardedQuarantine<OT, SFT, HFT, SF>::PopImpl(Object* object) {
93 E : DCHECK_NE(static_cast<Object*>(NULL), object);
94 :
95 : // Extract a node from this shard. If the shard is empty then scan linearly
96 : // until finding a non-empty one.
97 E : Node* node = NULL;
98 E : size_t shard = rand() % kShardingFactor;
99 E : size_t orig_shard = shard;
100 E : while (true) {
101 E : base::AutoLock lock(locks_[shard]);
102 E : node = heads_[shard];
103 E : if (node == NULL) {
104 E : shard = (shard + 1) % kShardingFactor;
105 :
106 : // If there's no non-empty shard then this means that another thread
107 : // emptied out all the buckets while we were in this function.
108 E : if (shard == orig_shard)
109 i : return false;
110 E : continue;
111 : }
112 :
113 : // We've found an element to evict so we can stop looking.
114 E : heads_[shard] = node->next;
115 E : if (heads_[shard] == NULL)
116 E : tails_[shard] = NULL;
117 E : break;
118 i : }
119 E : DCHECK_NE(static_cast<Node*>(NULL), node);
120 :
121 E : *object = node->object;
122 E : node_caches_[shard].Free(node, 1);
123 :
124 E : return true;
125 E : }
126 :
127 : template<typename OT, typename SFT, typename HFT, size_t SF>
128 E : void ShardedQuarantine<OT, SFT, HFT, SF>::EmptyImpl(ObjectVector* objects) {
129 E : DCHECK_NE(static_cast<ObjectVector*>(NULL), objects);
130 :
131 : // Iterate over each shard and add the objects to the vector.
132 E : for (size_t i = 0; i < kShardingFactor; ++i) {
133 E : base::AutoLock lock(locks_[i]);
134 :
135 E : Node* node = heads_[i];
136 E : while (node) {
137 E : objects->push_back(node->object);
138 E : Node* next_node = node->next;
139 E : node_caches_[i].Free(node, 1);
140 E : node = next_node;
141 E : }
142 E : heads_[i] = NULL;
143 E : tails_[i] = NULL;
144 E : }
145 :
146 : return;
147 E : }
148 :
149 : template<typename OT, typename SFT, typename HFT, size_t SF>
150 : size_t ShardedQuarantine<OT, SFT, HFT, SF>::GetLockIdImpl(
151 E : const Object& object) {
152 E : size_t hash = hash_functor_(object);
153 E : size_t shard = detail::ShardedQuarantineHash<kShardingFactor>(hash);
154 E : return shard;
155 E : }
156 :
157 : template<typename OT, typename SFT, typename HFT, size_t SF>
158 E : void ShardedQuarantine<OT, SFT, HFT, SF>::LockImpl(size_t id) {
159 E : DCHECK_LT(id, kShardingFactor);
160 E : locks_[id].Acquire();
161 E : }
162 :
163 : template<typename OT, typename SFT, typename HFT, size_t SF>
164 E : void ShardedQuarantine<OT, SFT, HFT, SF>::UnlockImpl(size_t id) {
165 E : DCHECK_LT(id, kShardingFactor);
166 E : locks_[id].AssertAcquired();
167 E : locks_[id].Release();
168 E : }
169 :
170 : } // namespace quarantines
171 : } // namespace asan
172 : } // namespace agent
173 :
174 : #endif // SYZYGY_AGENT_ASAN_QUARANTINES_SHARDED_QUARANTINE_IMPL_H_
|