text: // 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.
    // @{
    bool PushImpl(const Object& object) override;
    bool PopImpl(Object* object) override;
    void EmptyImpl(ObjectVector* objects) override;
    size_t GetLockIdImpl(const Object& object) override;
    void LockImpl(size_t id) override;
    void UnlockImpl(size_t id) override;
    // @}
  
    // 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, and to respect the system allocation granularity.
    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_
  