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    :  // Implements a simple sharded quarantine.
  16    :  
  17    :  #ifndef SYZYGY_AGENT_ASAN_QUARANTINES_SHARDED_QUARANTINE_H_
  18    :  #define SYZYGY_AGENT_ASAN_QUARANTINES_SHARDED_QUARANTINE_H_
  19    :  
  20    :  #include "base/synchronization/lock.h"
  21    :  #include "syzygy/agent/asan/page_allocator.h"
  22    :  #include "syzygy/agent/asan/quarantines/size_limited_quarantine.h"
  23    :  
  24    :  namespace agent {
  25    :  namespace asan {
  26    :  namespace quarantines {
  27    :  
  28    :  // A simple sharded quarantine. This distributes objects among a configurable
  29    :  // number of shards using a lightweight threadsafe hashing mechanism. Each
  30    :  // shard has its own lock, greatly reducing lock contention for the quarantine.
  31    :  //
  32    :  // @tparam ObjectType The type of object being stored in the cache.
  33    :  // @tparam SizeFunctorType A functor for extracting the size associated with
  34    :  //     an object.
  35    :  // @tparam HashFunctorType A functor for calculating a hash value associated
  36    :  //     with an object. This does need to be deterministic. A single instance
  37    :  //     of this will be maintained per instance, so it can use internal state;
  38    :  //     however, it must be thread-safe. This should implement the method:
  39    :  //     size_t operator()(const ObjectType& o) const;
  40    :  // @tparam ShardingFactor The sharding factor. Must be greater than 1.
  41    :  template<typename ObjectType,
  42    :           typename SizeFunctorType,
  43    :           typename HashFunctorType,
  44    :           size_t ShardingFactor>
  45    :  class ShardedQuarantine
  46    :      : public SizeLimitedQuarantineImpl<ObjectType, SizeFunctorType> {
  47    :   public:
  48    :    typedef HashFunctorType HashFunctor;
  49    :  
  50    :    static const size_t kShardingFactor = ShardingFactor;
  51    :  
  52    :    // Constructor. The hash functor must have a default constructor.
  53    :    ShardedQuarantine();
  54    :  
  55    :    // Constructor with explicit hash functor. The hash functor must have
  56    :    // a copy constructor.
  57    :    explicit ShardedQuarantine(const HashFunctor& hash_functor);
  58    :  
  59    :    // Virtual destructor.
  60  E :    virtual ~ShardedQuarantine() { }
  61    :  
  62    :   protected:
  63    :    // @name SizeLimitedQuarantineImpl implementation.
  64    :    // @{
  65    :    bool PushImpl(const Object& object) override;
  66    :    bool PopImpl(Object* object) override;
  67    :    void EmptyImpl(ObjectVector* objects) override;
  68    :    size_t GetLockIdImpl(const Object& object) override;
  69    :    void LockImpl(size_t id) override;
  70    :    void UnlockImpl(size_t id) override;
  71    :    // @}
  72    :  
  73    :    // The internal type used for storing objects. This augments them with a
  74    :    // 'next' pointer for chaining them together in the cache. These live in
  75    :    // a simple page-allocator.
  76    :    struct Node {
  77    :      Object object;
  78    :      Node* next;
  79    :    };
  80    :  
  81    :    // A simple page allocator that can only allocate individual nodes, and
  82    :    // does no bookkeeping. This has its own synchronization primitives.
  83    :    // Typical quarantine sizes are 16MB, which is about 120K allocations
  84    :    // given Chrome's typical allocation size. This in turn translates to
  85    :    // about 1MB of Node data. Typical 16 way sharding means about 65KB.
  86    :    // All of this to justify a 32KB page size to balance fragmentation and
  87    :    // number of pages, and to respect the system allocation granularity.
  88    :    typedef TypedPageAllocator<Node, 1, 32 * 1024, false> NodeCache;
  89    :  
  90    :    // Linked lists containing quarantined objects. Each shard is under the
  91    :    // corresponding locks_ entry. Objects are inserted at the tail, and
  92    :    // removed from the head.
  93    :    Node* heads_[kShardingFactor];
  94    :    Node* tails_[kShardingFactor];
  95    :  
  96    :    // Storage for nodes, one per shard. Each is under its own internal lock.
  97    :    NodeCache node_caches_[kShardingFactor];
  98    :  
  99    :    // Locks, one per linked list.
 100    :    base::Lock locks_[kShardingFactor];
 101    :  
 102    :    // The hash functor that will be used to assign objects to shards.
 103    :    HashFunctor hash_functor_;
 104    :  
 105    :   private:
 106    :    DISALLOW_COPY_AND_ASSIGN(ShardedQuarantine);
 107    :  };
 108    :  
 109    :  }  // namespace quarantines
 110    :  }  // namespace asan
 111    :  }  // namespace agent
 112    :  
 113    :  #include "syzygy/agent/asan/quarantines/sharded_quarantine_impl.h"
 114    :  
 115    :  #endif  // SYZYGY_AGENT_ASAN_QUARANTINES_SHARDED_QUARANTINE_H_