kalloc.hh

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                           */
/*  This file is part of the library KASKADE 7                               */
/*  https://www.zib.de/research/projects/kaskade7-finite-element-toolbox     */
/*                                                                           */
/*  Copyright (C) 2013-2018 Zuse Institute Berlin                            */
/*                                                                           */
/*  KASKADE 7 is distributed under the terms of the ZIB Academic License.    */
/*    see $KASKADE/academic.txt                                              */
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef KALLOC_HH
#define KALLOC_HH
 
#include <map>
#include <mutex>
#include <vector>
 
 
 
 
namespace Kaskade 
{
  
  class Kalloc
  {
    // Meta-data for chunks of memory managed.
    // Currently this just contains a void pointer. Do we need this for future flexibility,
    // i.e. do we want to store some more metadata of chunks? Linked list of free chunks instead
    // of currently relying on system new for managing chunk pointers?
    // If not, we could remove this and simply work with void* internally.
    class Chunk
    {
    public:
      Chunk(void* mem_);
      
      bool operator==(Chunk const& c) const;
      
      void* mem; // pointer to memory chunk 
    };
    
  public:
    Kalloc(int node_, int align_=64, size_t blocksize_=2*1024*1024, bool checking=
#if defined(NDEBUG)
 false
#else
 true
#endif
    );
    
    Kalloc(Kalloc&& kalloc);  
    
    ~Kalloc();
    
    void* alloc(size_t n);
    
    void free(void* p, size_t n);
    
    void reserve(size_t n, size_t k);
    
    size_t alignment() const { return align; }
    
    std::ostream& print(std::ostream& out) const;
 
  protected:
    void* allocUnlocked(size_t n);
    
    void freeUnlocked(void* p, size_t n);
    
  private:
    // Conceptually constant parameters
    int node;                   // NUMA node on which to allocate 
    int align;                  // memory alignment
    size_t blocksize;           // NUMA memory block size
    mutable std::mutex mutex;   // mutex for protection against concurrent access
    
    size_t large;               // maximum size of ranges stored in lists
    size_t mid;                 // minimum size of mid ranges
    
    
    // The free memory ranges we manage
    std::vector<std::vector<Chunk>> freeChunks; // buckets of free memory chunks 
    
    // Statistic data for reporting and on-line performance optimization, e.g., range coalescence
    size_t                 nBlocks;        // number of memory blocks obtained from the system
    size_t                 nRangeBlocks;   // number of memory blocks used for smaller ranges
    std::vector<size_t>    nLentRanges;    // the number of lent memory ranges from that bucket
    std::map<void*,size_t> systemBlocks;   // keeps track of all memory blocks obtained from the system
    
    void* extract(int bucket);
    void insert(void* range, int bucket);
    size_t bucketsize(int bucket) const;
    int bucket(size_t n) const;
    
    size_t freeRangedMemory() const;       // computes the amount of free memory available in range lists
    void coalesce();                       // finds adjacent free ranges and  merges them
    template <class Iter>
    void merge(Iter first, Iter last);     // merges consecutive ranges
    void distribute(void* mem, size_t n);  // subidivides the given memory into chunks of suitable size and sort into buckets
    std::pair<void*,size_t> findFreePage(int b);  // find a bucket (at least b) with a free page, allocating one from system if needed
    
    size_t totalAllocations, globalAllocations, freedLocal, freedGlobal, bucketMiss; // statistics
    
    bool checkLent;                        // if true, enables keeping track of all memory ranges handed out
    std::map<void*,size_t> lent;           // for debugging only: can keep track of all memory ranges handed out
  };
  
  class KallocUnlocked: public Kalloc
  {
  public:
    KallocUnlocked(int node_, int align_=64, size_t blocksize_=2*1024*1024, bool checking=true): Kalloc(node_,align_,blocksize_,checking) {}
    
    void* alloc(size_t n) { return allocUnlocked(n); }
    
    void free(void* p, size_t n) { return freeUnlocked(p,n); }
  };
}
 
#endif