Home | History | Annotate | Download | only in internal 
      1 // Copyright 2015 The Gemmlowp Authors. 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 // allocator.h: a buffer allocator that allows avoiding most of the
     16 // malloc/free overhead, by:
     17 // 1. Requiring all N allocations to be reserved in advance, and
     18 //    then commited at once, turning N allocations into 1.
     19 // 2. Being persistent, the allocated storage is reused across commits,
     20 //    and only reallocated as needed when the commit size gets larger.
     21 //
     22 // This is driven by Android-specific needs:
     23 // 1. On Android, the default (Bionic) allocator tends to aggressively
     24 // unmap pages, which means that malloc/free can be surprisingly expensive.
     25 // 2. On Android, stack allocations with alloca() can't be as large as on
     26 // desktop platforms.
     27 //
     28 // General usage:
     29 // 1. Reserve blocks by calling Reserve(), which returns a Handle.
     30 // 2. Call Commit() once.
     31 // 3. Now it is possible to get pointers to allocated buffers by calling
     32 //    GetPointer().
     33 // 4. Call Decommit() once.
     34 // 5. The allocator is now reverted to its original state, except that
     35 //    it retained its allocated storage, so the next Commit() will be faster.
     36 //    The allocated storage is only freed when the Allocator object is
     37 //    destroyed.
     38 
     39 #ifndef GEMMLOWP_INTERNAL_ALLOCATOR_H_
     40 #define GEMMLOWP_INTERNAL_ALLOCATOR_H_
     41 
     42 #include "common.h"
     43 
     44 namespace gemmlowp {
     45 
     46 enum class TypeId : std::uint8_t { Uint8, Int8, Uint16, Int16, Uint32, Int32 };
     47 
     48 template <typename T>
     49 struct GetTypeIdImpl {};
     50 
     51 template <typename T>
     52 inline TypeId GetTypeId() {
     53   return GetTypeIdImpl<T>::Value;
     54 }
     55 
     56 template <typename T>
     57 struct GetTypeIdImpl<const T> : GetTypeIdImpl<T> {};
     58 
     59 #define GEMMLOWP_REGISTER_TYPEID(type_, id) \
     60   template <>                               \
     61   struct GetTypeIdImpl<type_> {             \
     62     static const TypeId Value = TypeId::id; \
     63   };
     64 
     65 GEMMLOWP_REGISTER_TYPEID(std::uint8_t, Uint8)
     66 GEMMLOWP_REGISTER_TYPEID(std::int8_t, Int8)
     67 GEMMLOWP_REGISTER_TYPEID(std::uint16_t, Uint16)
     68 GEMMLOWP_REGISTER_TYPEID(std::int16_t, Int16)
     69 GEMMLOWP_REGISTER_TYPEID(std::uint32_t, Uint32)
     70 GEMMLOWP_REGISTER_TYPEID(std::int32_t, Int32)
     71 
     72 class Allocator {
     73  public:
     74   Allocator()
     75       : committed_(false),
     76         storage_size_(0),
     77         storage_(nullptr),
     78         reserved_blocks_(0),
     79         reserved_bytes_(0),
     80         generation_(0) {}
     81 
     82   ~Allocator() {
     83     assert(!committed_);
     84     assert(!reserved_blocks_);
     85     DeallocateStorage();
     86   }
     87 
     88   // Alignment of allocated blocks.
     89   static const std::size_t kAlignment = kDefaultCacheLineSize;
     90 
     91   // This is all we need so far, and since the usage pattern is fixed,
     92   // there is no point in allowing more until we need to.
     93   static const std::size_t kMaxBlocks = 5;
     94 
     95   void Commit() {
     96     assert(!committed_);
     97 
     98     if (reserved_bytes_ > storage_size_) {
     99       DeallocateStorage();
    100       storage_size_ = RoundUpToPowerOfTwo(reserved_bytes_);
    101       storage_ = aligned_alloc(kAlignment, storage_size_);
    102     }
    103 
    104     ReleaseBuildAssertion(!storage_size_ || storage_, "allocation failure");
    105     committed_ = true;
    106   }
    107 
    108   void Decommit() {
    109     assert(committed_);
    110     committed_ = false;
    111     generation_++;
    112 
    113     reserved_blocks_ = 0;
    114     reserved_bytes_ = 0;
    115   }
    116 
    117   // See generation_
    118   typedef std::size_t generation_t;
    119 
    120   // A handle on a reserved block. The user obtains
    121   // one by calling Reserve() and, after committing,
    122   // passes it to GetPointer().
    123   class Handle {
    124     std::uint8_t index_;
    125     generation_t generation_;
    126     TypeId type_;
    127 
    128     friend class Allocator;
    129   };
    130 
    131   // Reserves a block sized for n elements of type T, and
    132   // returns a handle to it. Must be called before committing.
    133   template <typename T>
    134   Handle Reserve(std::size_t n) {
    135     assert(!committed_ && "can't reserve blocks while committed");
    136     assert(reserved_blocks_ < kMaxBlocks &&
    137            "didn't expect to allocate this many blocks");
    138     const std::size_t bytes = RoundUp<kAlignment>(n * sizeof(T));
    139     const std::size_t offset = reserved_bytes_;
    140     const std::size_t index = reserved_blocks_;
    141 
    142     reserved_blocks_offsets_[index] = offset;
    143     Handle h;
    144     h.index_ = index;
    145     h.generation_ = generation_;
    146     h.type_ = GetTypeId<T>();
    147 
    148     reserved_blocks_++;
    149     reserved_bytes_ += bytes;
    150 
    151     return h;
    152   }
    153 
    154   // Returns the pointer to the allocated buffer for the given handle.
    155   // Must be called after committing.
    156   template <typename T>
    157   T* GetPointer(const Handle& h) const {
    158     assert(committed_ && "can't get block pointers unless committed");
    159     assert(h.index_ < reserved_blocks_ &&
    160            "bad handle, points to inexistant block");
    161     assert(h.generation_ == generation_ &&
    162            "handle from earlier generation, have decommitted since");
    163     assert(h.type_ == GetTypeId<T>() && "type mismatch");
    164     std::size_t offset = reserved_blocks_offsets_[h.index_];
    165     std::uintptr_t addr = reinterpret_cast<std::uintptr_t>(storage_) + offset;
    166     return reinterpret_cast<T*>(addr);
    167   }
    168 
    169  private:
    170   void DeallocateStorage() {
    171     assert(!committed_);
    172     aligned_free(storage_);
    173     storage_size_ = 0;
    174   }
    175 
    176   // Set to true by Commit() and to false by Decommit(). Initially false.
    177   bool committed_;
    178 
    179   // The actually allocated storage size and buffer pointer.
    180   std::size_t storage_size_;
    181   mutable void* storage_;
    182 
    183   // The number of blocks that have been reserved by Reserve().
    184   std::size_t reserved_blocks_;
    185   // The number of bytes that have been reserved by Reserve().
    186   std::size_t reserved_bytes_;
    187   // The offsets of reserved blocks into the storage buffer.
    188   std::size_t reserved_blocks_offsets_[kMaxBlocks];
    189 
    190   // The 'generation' is incremented on Decommit() and allows catching
    191   // bad GetPointer() calls still referring to a previous commit.
    192   generation_t generation_;
    193 };
    194 
    195 }  // namespace gemmlowp
    196 
    197 #endif  // GEMMLOWP_INTERNAL_ALLOCATOR_H_
    198