"Fossies" - the Fresh Open Source Software Archive

Member "Hoard-3.13/src/include/hoard/thresholdheap.h" (2 Jan 2019, 6597 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 "thresholdheap.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.org
    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_THRESHOLDHEAP_H
   29 #define HOARD_THRESHOLDHEAP_H
   30 
   31 #include <map>
   32 #include <list>
   33 
   34 #include "debugprint.h"
   35 
   36 #include "heaplayers.h"
   37 #include "mmapalloc.h"
   38 //#include "exactlyoneheap.h"
   39 
   40 using namespace std;
   41 
   42 // Free objects to the superheap if the utilization drops below a
   43 // threshold.  For example (assuming Allocated - InUse > MinWaste):
   44 //
   45 //   ThresholdN/D = 1 => always free memory (since InUse/Allocated is always less than 1).
   46 //   ThresholdN/D = 1/3 => free only when caching 1/3 of max memory ever used
   47 //   ThresholdN/D = 0 => never free memory
   48 
   49 namespace Hoard {
   50 
   51   template <int ThresholdMinWaste,
   52         int ThresholdNumerator,
   53         int ThresholdDenominator,
   54         class SuperHeap>
   55   class ThresholdHeap : public SuperHeap {
   56   public:
   57 
   58     enum { Alignment = SuperHeap::Alignment };
   59 
   60     ThresholdHeap()
   61       : _inUse (0),
   62     _allocated (0),
   63     _maxAllocated (0)
   64     {}
   65 
   66     inline void * malloc (size_t sz) {
   67       // Look for an object of this size (exactly? larger?)
   68       // in the cache.
   69 
   70       void * ptr = _cache.remove(sz);
   71       if (ptr == nullptr) {
   72     // If none found, allocate one and return it.
   73     ptr = SuperHeap::malloc (sz);
   74     _allocated += SuperHeap::getSize(ptr);
   75     if (_allocated > _maxAllocated) {
   76       _maxAllocated = _allocated;
   77     }
   78       }
   79       _inUse += SuperHeap::getSize(ptr);
   80       assert (SuperHeap::getSize(ptr) >= sz);
   81       assert ((size_t) ptr % Alignment == 0);
   82       return ptr;
   83     }
   84 
   85     inline void free (void * ptr) {
   86       size_t sz = SuperHeap::getSize(ptr);
   87       DEBUG_PRINT3("freeing an object of size %d: inUse = %d, allocated = %d\n", sz, _inUse, _allocated);
   88       _inUse -= sz;
   89       // Add it to the cache.
   90       _cache.add (sz, ptr);
   91       // Now decide whether to free up some memory.
   92       // Note that total cached = _allocated - _inUse.
   93       // We will free memory whenever total cached > N/D * max allocated,
   94       // which is (_allocated - _inUse) > N/D * _maxAllocated
   95       // = D * (_allocated - _inUse) > N * _maxAllocated.
   96       while ((ThresholdMinWaste < (_allocated - _inUse)) && 
   97          (ThresholdDenominator * (_allocated - _inUse) > ThresholdNumerator * _maxAllocated)) {
   98 
   99     DEBUG_PRINT3("crossing threshold: inUse = %d, allocated = %d, max allocated = %d\n", _inUse, _allocated, _maxAllocated);
  100 
  101     // Find an object to free.
  102     // To minimize the number of calls to the superheap,
  103     // start with the largest objects and work our way down.
  104     void * obj = _cache.removeLargest();
  105     if (!obj) {
  106       break;
  107     }
  108     size_t objSz = SuperHeap::getSize (obj);
  109     DEBUG_PRINT1("found a big object in the cache of size %lu.\n", objSz);
  110     // Free it.
  111     DEBUG_PRINT3("Freeing %d: inUse = %d, allocated = %d\n", objSz, _inUse, _allocated);
  112     _allocated -= objSz;
  113     SuperHeap::free (obj);
  114       }
  115       DEBUG_PRINT("Threshold done.\n");
  116     }
  117 
  118   private:
  119 
  120     class TopHeap : public SizeHeap<BumpAlloc<65536, MmapAlloc> > {
  121     public:
  122 #if 0
  123       void * malloc (size_t sz) {
  124     void * ptr = SizeHeap<BumpAlloc<65536, MmapAlloc> >::malloc (sz);
  125     char buf[255];
  126     sprintf (buf, "TopHeap malloc %ld = %p\n", sz, ptr);
  127     fprintf (stderr, buf);
  128     return ptr;
  129       }
  130 #endif
  131     };
  132   
  133     // A heap for local allocations for the containers below.
  134     class LocalHeap :
  135       public ExactlyOneHeap<KingsleyHeap<AdaptHeap<DLList, TopHeap>, TopHeap> > {};
  136 
  137     template <class K, class V>
  138     class CacheHelper {
  139     private:
  140       typedef list<V, STLAllocator<V, LocalHeap> > listType;
  141       typedef pair<const K, listType> mapObject;
  142       typedef map<K, listType, less<K>, STLAllocator<mapObject, LocalHeap> > mapType;
  143 
  144       /// A map (sz -> list[ptr])
  145       mapType theMap;
  146 
  147     public:
  148 
  149       // Add an object of the given size.
  150       // NOTE: Perhaps we should round to the next power of two?
  151       void add (K sz, V ptr) {
  152     theMap[sz].push_front (ptr);
  153       }
  154 
  155       // Remove one object of the given size.
  156       V remove (K sz) {
  157     // First, check to see if that exact size exists.
  158     typename mapType::iterator i = theMap.find (sz);
  159     if (i != theMap.end()) {
  160       V ptr = theMap[sz].front();
  161       theMap[sz].pop_front();
  162       if (theMap[sz].empty()) {
  163         // Last item: free this key.
  164         theMap.erase (sz);
  165       }
  166       return ptr;
  167     }
  168 
  169     // Otherwise, do first fit: find the first object that is big
  170     // enough to fit the request, searching from smallest to largest
  171     // size.
  172 
  173     for (i = theMap.begin();
  174          i != theMap.end();
  175          ++i) {
  176       K key = (*i).first;
  177       listType& theList = (*i).second;
  178       if (key >= sz) {
  179         V ptr = theList.front();
  180         theList.pop_front();
  181         // If we have just removed the last element from the list,
  182         // erase the key entry.
  183         if (theList.empty()) {
  184           theMap.erase (key);
  185         }
  186         return ptr;
  187       }
  188     }
  189     return nullptr;
  190       }
  191 
  192       // Remove one of the largest available objects.
  193       V removeLargest() {
  194     // Get the last (largest) element.
  195     typename mapType::reverse_iterator i;
  196     i = theMap.rbegin();
  197     // If we found one (in other words, the list is non-empty),
  198     // remove it.
  199     if (i != theMap.rend()) {
  200       K key = (*i).first;
  201       listType& theList = (*i).second;
  202       V ptr = theList.front();
  203       theList.pop_front();
  204       // If we have just removed the last element from the list,
  205       // erase the key entry.
  206       if (theList.empty()) {
  207         theMap.erase (key);
  208       }
  209       return ptr;
  210     }
  211     return nullptr;
  212       }
  213     };
  214 
  215     class Cache : public CacheHelper<size_t, void *> {};
  216 
  217 
  218     /// Amount of memory in use by a client.
  219     unsigned long _inUse;
  220 
  221     /// Amount of memory currently allocated from the OS (we can free some).
  222     unsigned long _allocated;
  223 
  224     /// The most memory we have ever allocated from the OS.
  225     unsigned long _maxAllocated;
  226 
  227     /// Saved chunks of memory from the OS.
  228     Cache _cache;
  229 
  230   };
  231 
  232 }
  233 #endif