Home | History | Annotate | Download | only in util 
      1 /*
      2  * Copyright (C) 2016 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #ifndef CHRE_UTIL_MEMORY_POOL_H_
     18 #define CHRE_UTIL_MEMORY_POOL_H_
     19 
     20 #include <cstddef>
     21 #include <type_traits>
     22 
     23 #include "chre/util/non_copyable.h"
     24 
     25 namespace chre {
     26 
     27 /**
     28  * A memory pool (slab allocator) used for very efficient allocation and
     29  * deallocation of objects with a uniform size. The goal is to avoid costly
     30  * malloc/free calls.
     31  *
     32  * This implementation is based on the following paper:
     33  *
     34  * Fast Efficient Fixed-Size Memory Pool
     35  * No Loops and No Overhead
     36  * Ben Kenwright
     37  *
     38  * Allocations and deallocation are handled in O(1) time and memory. The list
     39  * of unused blocks is stored in the space of unused blocks. This means that
     40  * this data structure has a minimum element size of sizeof(size_t) and means
     41  * it may not be suitable for very small objects (whose size is less than
     42  * sizeof(size_t)).
     43  *
     44  * One variation is made relative to the allocator described in the paper. To
     45  * minimize allocation/deallocation latency, the free list is built at
     46  * construction time.
     47  */
     48 template<typename ElementType, size_t kSize>
     49 class MemoryPool : public NonCopyable {
     50  public:
     51   /**
     52    * Constructs a MemoryPool and initializes the initial conditions of the
     53    * allocator.
     54    */
     55   MemoryPool();
     56 
     57   /**
     58    * Allocates space for an object, constructs it and returns the pointer to
     59    * that object.
     60    *
     61    * @param  The arguments to be forwarded to the constructor of the object.
     62    * @return A pointer to a constructed object or nullptr if the allocation
     63    *         fails.
     64    */
     65   template<typename... Args>
     66   ElementType *allocate(Args&&... args);
     67 
     68   /**
     69    * Releases the memory of a previously allocated element. The pointer provided
     70    * here must be one that was produced by a previous call to the allocate()
     71    * function. The destructor is invoked on the object.
     72    *
     73    * @param A pointer to an element that was previously allocated by the
     74    *        allocate() function.
     75    */
     76   void deallocate(ElementType *element);
     77 
     78   /**
     79    * @return the number of unused blocks in this memory pool.
     80    */
     81   size_t getFreeBlockCount() const;
     82 
     83  private:
     84   /**
     85    * The unused storage for this MemoryPool maintains the list of free slots.
     86    * As such, a union is used to allow storage of both the Element and the index
     87    * of the next free block in the same space.
     88    */
     89   union MemoryPoolBlock {
     90     //! Intentionally not destructing any leaked blocks, will consider doing
     91     //! this differently later if required.
     92     ~MemoryPoolBlock() = delete;
     93 
     94     //! The element stored in the slot.
     95     ElementType mElement;
     96 
     97     //! The index of the next free block in the unused storage.
     98     size_t mNextFreeBlockIndex;
     99   };
    100 
    101   /**
    102    * Obtains a pointer to the underlying storage for the memory pool blocks.
    103    *
    104    * @return A pointer to the memory pool block storage.
    105    */
    106   MemoryPoolBlock *blocks();
    107 
    108   //! Storage for memory pool blocks. To avoid static initialization of members,
    109   //! std::aligned_storage is used.
    110   typename std::aligned_storage<sizeof(MemoryPoolBlock),
    111       alignof(MemoryPoolBlock)>::type mBlocks[kSize];
    112 
    113   //! The index of the head of the free slot list.
    114   size_t mNextFreeBlockIndex = 0;
    115 
    116   //! The number of free slots available.
    117   size_t mFreeBlockCount = kSize;
    118 };
    119 
    120 }  // namespace chre
    121 
    122 #include "chre/util/memory_pool_impl.h"
    123 
    124 #endif  // CHRE_UTIL_MEMORY_POOL_H_
    125