| // Copyright 2014 Google Inc. All Rights Reserved. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| // |
| // Implements a simple sharded quarantine. |
| |
| #ifndef SYZYGY_AGENT_ASAN_QUARANTINES_SHARDED_QUARANTINE_H_ |
| #define SYZYGY_AGENT_ASAN_QUARANTINES_SHARDED_QUARANTINE_H_ |
| |
| #include "base/synchronization/lock.h" |
| #include "syzygy/agent/asan/page_allocator.h" |
| #include "syzygy/agent/asan/quarantines/size_limited_quarantine.h" |
| |
| namespace agent { |
| namespace asan { |
| namespace quarantines { |
| |
| // A simple sharded quarantine. This distributes objects among a configurable |
| // number of shards using a lightweight threadsafe hashing mechanism. Each |
| // shard has its own lock, greatly reducing lock contention for the quarantine. |
| // |
| // @tparam ObjectType The type of object being stored in the cache. |
| // @tparam SizeFunctorType A functor for extracting the size associated with |
| // an object. |
| // @tparam HashFunctorType A functor for calculating a hash value associated |
| // with an object. This does need to be deterministic. A single instance |
| // of this will be maintained per instance, so it can use internal state; |
| // however, it must be thread-safe. This should implement the method: |
| // size_t operator()(const ObjectType& o) const; |
| // @tparam ShardingFactor The sharding factor. Must be greater than 1. |
| template<typename ObjectType, |
| typename SizeFunctorType, |
| typename HashFunctorType, |
| size_t ShardingFactor> |
| class ShardedQuarantine |
| : public SizeLimitedQuarantineImpl<ObjectType, SizeFunctorType> { |
| public: |
| typedef HashFunctorType HashFunctor; |
| |
| static const size_t kShardingFactor = ShardingFactor; |
| |
| // Constructor. The hash functor must have a default constructor. |
| ShardedQuarantine(); |
| |
| // Constructor with explicit hash functor. The hash functor must have |
| // a copy constructor. |
| explicit ShardedQuarantine(const HashFunctor& hash_functor); |
| |
| // Virtual destructor. |
| virtual ~ShardedQuarantine() { } |
| |
| protected: |
| // @name SizeLimitedQuarantineImpl implementation. |
| // @{ |
| virtual bool PushImpl(const Object& object); |
| virtual void PopImpl(Object* object); |
| virtual void EmptyImpl(ObjectVector* objects); |
| // @} |
| |
| // The internal type used for storing objects. This augments them with a |
| // 'next' pointer for chaining them together in the cache. These live in |
| // a simple page-allocator. |
| struct Node { |
| Object object; |
| Node* next; |
| }; |
| |
| // A simple page allocator that can only allocate individual nodes, and |
| // does no bookkeeping. This has its own synchronization primitives. |
| // Typical quarantine sizes are 16MB, which is about 120K allocations |
| // given Chrome's typical allocation size. This in turn translates to |
| // about 1MB of Node data. Typical 16 way sharding means about 65KB. |
| // All of this to justify a 32KB page size to balance fragmentation and |
| // number of pages. |
| typedef TypedPageAllocator<Node, 1, 32 * 1024, false> NodeCache; |
| |
| // Linked lists containing quarantined objects. Each shard is under the |
| // corresponding locks_ entry. Objects are inserted at the tail, and |
| // removed from the head. |
| Node* heads_[kShardingFactor]; |
| Node* tails_[kShardingFactor]; |
| |
| // Storage for nodes, one per shard. Each is under its own internal lock. |
| NodeCache node_caches_[kShardingFactor]; |
| |
| // Locks, one per linked list. |
| base::Lock locks_[kShardingFactor]; |
| |
| // The hash functor that will be used to assign objects to shards. |
| HashFunctor hash_functor_; |
| |
| private: |
| DISALLOW_COPY_AND_ASSIGN(ShardedQuarantine); |
| }; |
| |
| } // namespace quarantines |
| } // namespace asan |
| } // namespace agent |
| |
| #include "syzygy/agent/asan/quarantines/sharded_quarantine_impl.h" |
| |
| #endif // SYZYGY_AGENT_ASAN_QUARANTINES_SHARDED_QUARANTINE_H_ |