"Fossies" - the Fresh Open Source Software Archive

Member "Hoard-3.13/src/include/hoard/hoardmanager.h" (2 Jan 2019, 11064 Bytes) of package /linux/misc/Hoard-3.13.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "hoardmanager.h" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 3.12_vs_3.13.

    1 // -*- C++ -*-
    2 
    3 /*
    4 
    5   The Hoard Multiprocessor Memory Allocator
    6   www.hoard.org
    7 
    8   Author: Emery Berger, http://www.emeryberger.com
    9  
   10   Copyright (c) 1998-2018 Emery Berger
   11   
   12   This program is free software; you can redistribute it and/or modify
   13   it under the terms of the GNU General Public License as published by
   14   the Free Software Foundation; either version 2 of the License, or
   15   (at your option) any later version.
   16   
   17   This program is distributed in the hope that it will be useful,
   18   but WITHOUT ANY WARRANTY; without even the implied warranty of
   19   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   20   GNU General Public License for more details.
   21   
   22   You should have received a copy of the GNU General Public License
   23   along with this program; if not, write to the Free Software
   24   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   25 
   26 */
   27 
   28 #ifndef HOARD_HOARDMANAGER_H
   29 #define HOARD_HOARDMANAGER_H
   30 
   31 #include <cstdlib>
   32 #include <new>
   33 #include <mutex>
   34 
   35 // Hoard-specific Heap Layers
   36 #include "statistics.h"
   37 #include "emptyclass.h"
   38 #include "array.h"
   39 #include "manageonesuperblock.h"
   40 #include "basehoardmanager.h"
   41 #include "emptyhoardmanager.h"
   42 
   43 
   44 #include "heaplayers.h"
   45 
   46 using namespace HL;
   47 
   48 /**
   49  *
   50  * @class HoardManager
   51  * @brief Manages superblocks by emptiness, returning them to the parent heap when empty enough.
   52  * @author Emery Berger <http://www.emeryberger.com>
   53  *
   54  **/
   55 
   56 namespace Hoard {
   57 
   58   template <class SourceHeap,
   59         class ParentHeap,
   60         class SuperblockType_,
   61         int EmptinessClasses,
   62         class LockType,
   63         class thresholdFunctionClass,
   64         class HeapType>
   65   class HoardManager : public BaseHoardManager<SuperblockType_>,
   66                public thresholdFunctionClass
   67   {
   68   public:
   69 
   70     HoardManager()
   71       : _magic (MAGIC_NUMBER),
   72     _cachedSize (binType::getClassSize(0)),
   73     _cachedRealSize (_cachedSize),
   74     _cachedSizeClass (0)
   75     {}
   76 
   77     virtual ~HoardManager() {}
   78 
   79     typedef SuperblockType_ SuperblockType;
   80 
   81     enum { Alignment = SuperblockType::Header::Alignment };
   82 
   83 
   84     MALLOC_FUNCTION INLINE void * malloc (size_t sz)
   85     {
   86       Check<HoardManager, sanityCheck> check (this);
   87       int binIndex;
   88       size_t realSize;
   89       if (false) { // sz == _cachedSize) {
   90     binIndex = _cachedSizeClass;
   91     realSize = _cachedRealSize;
   92       } else {
   93     binIndex = binType::getSizeClass(sz);
   94     realSize = binType::getClassSize (binIndex);
   95     _cachedSize = sz;
   96     _cachedSizeClass = binIndex;
   97     _cachedRealSize = realSize;
   98       }
   99       assert (realSize >= sz);
  100 
  101       // Iterate until we succeed in allocating memory.
  102       auto ptr = getObject (binIndex, realSize);
  103       if (!ptr) {
  104     ptr = slowPathMalloc (realSize);
  105       }
  106       assert (SuperHeap::getSize(ptr) >= sz);
  107       assert ((size_t) ptr % Alignment == 0);
  108       return ptr;
  109     }
  110 
  111 
  112     /// Put a superblock on this heap.
  113     NO_INLINE void put (SuperblockType * s, size_t sz) {
  114       std::lock_guard<LockType> l (_theLock);
  115 
  116       assert (s->getOwner() != this);
  117       Check<HoardManager, sanityCheck> check (this);
  118 
  119       const auto binIndex = binType::getSizeClass(sz);
  120 
  121       // Check to see whether this superblock puts us over.
  122       auto& stats = _stats(binIndex);
  123       auto a = stats.getAllocated() + s->getTotalObjects();
  124       auto u = stats.getInUse() + (s->getTotalObjects() - s->getObjectsFree());
  125 
  126       if (thresholdFunctionClass::function (u, a, sz)) {
  127     // We've crossed the threshold function,
  128     // so we move this superblock up to the parent.
  129     _ph.put (reinterpret_cast<typename ParentHeap::SuperblockType *>(s), sz);
  130       } else {
  131     unlocked_put (s, sz);
  132       }
  133     }
  134 
  135 
  136     /// Get an empty (or nearly-empty) superblock.
  137     NO_INLINE SuperblockType * get (size_t sz, HeapType * dest) {
  138       std::lock_guard<LockType> l (_theLock);
  139       Check<HoardManager, sanityCheck> check (this);
  140       const auto binIndex = binType::getSizeClass (sz);
  141       auto * s = _otherBins(binIndex).get();
  142       if (s) {
  143     assert (s->isValidSuperblock());
  144       
  145     // Update the statistics, removing objects in use and allocated for s.
  146     decStatsSuperblock (s, binIndex);
  147     s->setOwner (dest);
  148       }
  149       // printf ("getting sb %x (size %d) on %x\n", (void *) s, sz, (void *) this);
  150       return s;
  151     }
  152 
  153     /// Return one object to its superblock and update stats.
  154     INLINE void free (void * ptr) {
  155       Check<HoardManager, sanityCheck> check (this);
  156 
  157       // Get the corresponding superblock.
  158       SuperblockType * s = SuperHeap::getSuperblock (ptr);
  159  
  160       assert (s->getOwner() == this);
  161 
  162       // Find out which bin it belongs to.
  163       // Note that we assume that all pointers have been correctly
  164       // normalized at this point.
  165       assert (s->normalize (ptr) == ptr);
  166 
  167       auto sz = s->getObjectSize ();
  168       auto binIndex = (int) binType::getSizeClass (sz);
  169 
  170       // Free the object.
  171       _otherBins(binIndex).free (ptr);
  172 
  173 
  174       // Update statistics.
  175       auto& stats = _stats(binIndex);
  176       auto u = stats.getInUse();
  177       auto a = stats.getAllocated();
  178       u--;
  179       stats.setInUse (u);
  180 
  181       // Free up a superblock if we've crossed the emptiness threshold.
  182 
  183       if (thresholdFunctionClass::function (u, a, sz)) {
  184 
  185     slowPathFree (binIndex, u, a);
  186 
  187       }
  188     }
  189 
  190     INLINE void lock() {
  191       _theLock.lock();
  192     }
  193 
  194     INLINE void unlock() {
  195       _theLock.unlock();
  196     }
  197 
  198   private:
  199 
  200     typedef BaseHoardManager<SuperblockType_> SuperHeap;
  201 
  202     enum { SuperblockSize = sizeof(SuperblockType_) };
  203 
  204     /// Ensure that the superblock size is a power of two.
  205     static_assert((SuperblockSize & (SuperblockSize-1)) == 0,
  206           "Superblock size must be a power of two.");
  207 
  208     enum { MAGIC_NUMBER = 0xfeeddadd };
  209 
  210     /// A magic number used for debugging.
  211     const unsigned long _magic;
  212 
  213     size_t _cachedSize;
  214     size_t _cachedRealSize;
  215     int    _cachedSizeClass;
  216     
  217     inline int isValid() const {
  218       return (_magic == MAGIC_NUMBER);
  219     }
  220 
  221     static_assert(sizeof(typename SuperblockType::Header) % sizeof(double) == 0,
  222           "Header size must be a multiple of the size of a double.");
  223 
  224 
  225     /// The type of the bin manager.
  226     typedef HL::bins<typename SuperblockType::Header, SuperblockSize> binType;
  227 
  228     /// How many bins do we need to maintain?
  229     enum { NumBins = binType::NUM_BINS };
  230 
  231     NO_INLINE void slowPathFree (int binIndex, unsigned int u, unsigned int a) {
  232       // We've crossed the threshold.
  233       // Remove a superblock and give it to the 'parent heap.'
  234       Check<HoardManager, sanityCheck> check (this);
  235     
  236       //    printf ("HoardManager: this = %x, getting a superblock\n", this);
  237     
  238       SuperblockType * sb = _otherBins(binIndex).get ();
  239     
  240       // We should always get one.
  241       assert (sb);
  242       if (sb) {
  243 
  244     auto sz = binType::getClassSize (binIndex);
  245     auto& stats = _stats(binIndex);
  246     auto totalObjects = sb->getTotalObjects();
  247     stats.setInUse (u - (totalObjects - sb->getObjectsFree()));
  248     stats.setAllocated (a - totalObjects);
  249 
  250     // Give it to the parent heap.
  251     ///////// NOTE: We change the superblock type here!
  252     ///////// THIS HAD BETTER BE SAFE!
  253     _ph.put (reinterpret_cast<typename ParentHeap::SuperblockType *>(sb), sz);
  254     assert (sb->isValidSuperblock());
  255 
  256       }
  257     }
  258 
  259 
  260     NO_INLINE void unlocked_put (SuperblockType * s, size_t sz) {
  261       if (!s || !s->isValidSuperblock()) {
  262     return;
  263       }
  264 
  265       Check<HoardManager, sanityCheck> check (this);
  266 
  267       const auto binIndex = binType::getSizeClass(sz);
  268 
  269       // Now put it on this heap.
  270       s->setOwner (reinterpret_cast<HeapType *>(this));
  271       _otherBins(binIndex).put (s);
  272 
  273       // Update the heap statistics with the allocated and in use stats
  274       // for the superblock.
  275 
  276       addStatsSuperblock (s, binIndex);
  277       assert (s->isValidSuperblock());
  278 
  279     }
  280 
  281     void addStatsSuperblock (SuperblockType * s, int binIndex) {
  282       auto& stats = _stats(binIndex);
  283       auto a = stats.getAllocated();
  284       auto u = stats.getInUse();
  285       auto totalObjects = s->getTotalObjects();
  286       stats.setInUse (u + (totalObjects - s->getObjectsFree()));
  287       stats.setAllocated (a + totalObjects);
  288     }
  289 
  290 
  291     void decStatsSuperblock (SuperblockType * s, int binIndex) {
  292       auto& stats = _stats(binIndex);
  293       auto a = stats.getAllocated();
  294       auto u = stats.getInUse();
  295       auto totalObjects = s->getTotalObjects();
  296       stats.setInUse (u - (totalObjects - s->getObjectsFree()));
  297       stats.setAllocated (a - totalObjects);
  298     }
  299 
  300     MALLOC_FUNCTION NO_INLINE void * slowPathMalloc (size_t sz) {
  301       auto binIndex = binType::getSizeClass (sz);
  302       auto realSize = binType::getClassSize (binIndex);
  303       assert (realSize >= sz);
  304       for (;;) {
  305     Check<HoardManager, sanityCheck> check1 (this);
  306     auto * ptr = getObject (binIndex, realSize);
  307     if (ptr) {
  308       return ptr;
  309     } else {
  310       Check<HoardManager, sanityCheck> check2 (this);
  311       // Return null if we can't allocate another superblock.
  312       if (!getAnotherSuperblock (realSize)) {
  313         //    fprintf (stderr, "HoardManager::malloc - no memory.\n");
  314         return 0;
  315       }
  316     }
  317       }
  318     }
  319 
  320     /// Get one object of a particular size.
  321     MALLOC_FUNCTION INLINE void * getObject (int binIndex,
  322                          size_t sz) {
  323       Check<HoardManager, sanityCheck> check (this);
  324       void * ptr = _otherBins(binIndex).malloc (sz);
  325       if (ptr) {
  326     // We got one. Update stats.
  327     auto u = _stats(binIndex).getInUse();
  328     _stats(binIndex).setInUse (u+1);
  329       }
  330       return ptr;
  331     }
  332 
  333     friend class sanityCheck;
  334 
  335     class sanityCheck {
  336     public:
  337       inline static void precondition (HoardManager * h) {
  338     checkInvariant(h);
  339       }
  340       inline static void postcondition (HoardManager * h) {
  341     checkInvariant(h);
  342       }
  343     private:
  344       inline static void checkInvariant (HoardManager * h) {
  345     (void) h;
  346     assert (h->isValid());
  347       }
  348     };
  349 
  350   private:
  351 
  352     NO_INLINE void * getAnotherSuperblock (size_t sz) {
  353 
  354       // NB: This function should be on the slow path.
  355 
  356       // Try the parent heap.
  357       // NOTE: We change the superblock type here!
  358       auto * sb = reinterpret_cast<SuperblockType *>(_ph.get (sz, reinterpret_cast<ParentHeap *>(this)));
  359 
  360       if (sb) {
  361     if (!sb->isValidSuperblock()) {
  362       // As above - drop any invalid superblocks.
  363       sb = nullptr;
  364     }
  365 
  366       } else {
  367     // Nothing - get memory from the source.
  368     void * ptr = _sourceHeap.malloc (SuperblockSize);
  369     if (!ptr) {
  370       return 0;
  371     }
  372     sb = new (ptr) SuperblockType (sz);
  373       }
  374 
  375       // Put the superblock into its appropriate bin.
  376       if (sb) {
  377     unlocked_put (sb, sz);
  378       }
  379       return sb;
  380     }
  381 
  382     LockType _theLock;
  383 
  384     /// Usage statistics for each bin.
  385     Array<NumBins, Statistics> _stats;
  386 
  387     typedef SuperblockType * SuperblockTypePointer;
  388 
  389     typedef EmptyClass<SuperblockType, EmptinessClasses> OrganizedByEmptiness;
  390 
  391     typedef ManageOneSuperblock<OrganizedByEmptiness> BinManager;
  392 
  393     /// Bins that hold superblocks for each size class.
  394     Array<NumBins, BinManager> _otherBins;
  395 
  396     /// The parent heap.
  397     ParentHeap _ph;
  398 
  399     /// Where memory comes from.
  400     SourceHeap _sourceHeap;
  401 
  402   };
  403 
  404 } // namespace Hoard
  405 
  406 #endif