///-*-C++-*-//////////////////////////////////////////////////////////////////
//
// Hoard: A Fast, Scalable, and Memory-Efficient Allocator
//        for Shared-Memory Multiprocessors
// Contact author: Emery Berger, http://www.cs.utexas.edu/users/emery
//
// Copyright (c) 1998-2000, The University of Texas at Austin.
//
// This library is free software; you can redistribute it and/or modify
// it under the terms of the GNU Library General Public License as
// published by the Free Software Foundation, http://www.fsf.org.
//
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Library General Public License for more details.
//
//////////////////////////////////////////////////////////////////////////////

/* hoardHeap, the base class for threadHeap and processHeap. */

#ifndef _HEAP_H_
#define _HEAP_H_

#include <OS.h>
#include <cstddef>

#include "config.h"

#include "arch-specific.h"
#include "superblock.h"
#include "heapstats.h"


namespace BPrivate {

class processHeap;

class hoardHeap {
        public:
                hoardHeap(void);

                // A superblock that holds more than one object must hold at least
                // this many bytes.
                enum { SUPERBLOCK_SIZE = 8192 };

                // A thread heap must be at least 1/EMPTY_FRACTION empty before we
                // start returning superblocks to the process heap.
                enum { EMPTY_FRACTION = SUPERBLOCK_FULLNESS_GROUP - 1 };

                // Reset value for the least-empty bin.  The last bin
                // (SUPERBLOCK_FULLNESS_GROUP-1) is for completely full superblocks,
                // so we use the next-to-last bin.
                enum { RESET_LEAST_EMPTY_BIN = SUPERBLOCK_FULLNESS_GROUP - 2 };

                // The number of empty superblocks that we allow any thread heap to
                // hold once the thread heap has fallen below 1/EMPTY_FRACTION
                // empty.
                enum { MAX_EMPTY_SUPERBLOCKS = EMPTY_FRACTION };

                //
                // The number of size classes.  This combined with the
                // SIZE_CLASS_BASE determine the maximum size of an object.
                //
                // NB: Once this is changed, you must execute maketable.cpp and put
                // the generated values into heap.cpp.

#if MAX_INTERNAL_FRAGMENTATION == 2
                enum { SIZE_CLASSES = 115 };
#elif MAX_INTERNAL_FRAGMENTATION == 6
                enum { SIZE_CLASSES = 46 };
#elif MAX_INTERNAL_FRAGMENTATION == 10
                enum { SIZE_CLASSES = 32 };
#else
#       error "Undefined size class base."
#endif

                // Every object is aligned so that it can always hold any type.
                enum { ALIGNMENT = HAIKU_MEMORY_ALIGNMENT };

                // ANDing with this rounds to ALIGNMENT.
                enum { ALIGNMENT_MASK = ALIGNMENT - 1 };

                // Used for sanity checking.
                enum { HEAP_MAGIC = 0x0badcafe };

                // Get the usage and allocated statistics.
                inline void getStats(int sizeclass, int &U, int &A);


#if HEAP_STATS
                // How much is the maximum ever in use for this size class?
                inline int maxInUse(int sizeclass);

                // How much is the maximum memory allocated for this size class?
                inline int maxAllocated(int sizeclass);
#endif

                // Insert a superblock into our list.
                void insertSuperblock(int sizeclass, superblock *sb, processHeap *pHeap);

                // Remove the superblock with the most free space.
                superblock *removeMaxSuperblock(int sizeclass);

                // Find an available superblock (i.e., with some space in it).
                inline superblock *findAvailableSuperblock(int sizeclass,
                                                                block * &b, processHeap * pHeap);

                // Lock this heap.
                inline void lock(void);

                // Unlock this heap.
                inline void unlock(void);

                // Init this heap lock.
                inline void initLock(void);

                // Set our index number (which heap we are).
                inline void setIndex(int i);

                // Get our index number (which heap we are).
                inline int getIndex(void);

                // Free a block into a superblock.
                // This is used by processHeap::free().
                // Returns 1 iff the superblock was munmapped.
                int freeBlock(block * &b, superblock * &sb, int sizeclass,
                                processHeap * pHeap);

                //// Utility functions ////

                // Return the size class for a given size.
                inline static int sizeClass(const size_t sz);

                // Return the size corresponding to a given size class.
                inline static size_t sizeFromClass(const int sizeclass);

                // Return the release threshold corresponding to a given size class.
                inline static int getReleaseThreshold(const int sizeclass);

                // Return how many blocks of a given size class fit into a superblock.
                inline static int numBlocks(const int sizeclass);

                // Align a value.
                inline static size_t align(const size_t sz);

        private:
                // Disable copying and assignment.

                hoardHeap(const hoardHeap &);
                const hoardHeap & operator=(const hoardHeap &);

                // Recycle a superblock.
                inline void recycle(superblock *);

                // Reuse a superblock (if one is available).
                inline superblock *reuse(int sizeclass);

                // Remove a particular superblock.
                void removeSuperblock(superblock *, int sizeclass);

                // Move a particular superblock from one bin to another.
                void moveSuperblock(superblock *,
                                                        int sizeclass, int fromBin, int toBin);

                // Update memory in-use and allocated statistics.
                // (*UStats = just update U.)
                inline void incStats(int sizeclass, int updateU, int updateA);
                inline void incUStats(int sizeclass);

                inline void decStats(int sizeclass, int updateU, int updateA);
                inline void decUStats(int sizeclass);

                //// Members ////

                // Heap statistics.
                heapStats _stats[SIZE_CLASSES];

                // The per-heap lock.
                hoardLockType _lock;

                // Which heap this is (0 = the process (global) heap).
                int _index;

                // Reusable superblocks.
                superblock *_reusableSuperblocks;
                int _reusableSuperblocksCount;

                // Lists of superblocks.
                superblock *_superblocks[SUPERBLOCK_FULLNESS_GROUP][SIZE_CLASSES];

                // The current least-empty superblock bin.
                int _leastEmptyBin[SIZE_CLASSES];

#if HEAP_DEBUG
                // For sanity checking.
                const unsigned long _magic;
#else
#       define _magic HEAP_MAGIC
#endif

                // The lookup table for size classes.
                static size_t _sizeTable[SIZE_CLASSES];

                // The lookup table for release thresholds.
                static size_t _threshold[SIZE_CLASSES];

        public:
                static void initNumProcs(void);

        protected:
                // The maximum number of thread heaps we allow.  (NOT the maximum
                // number of threads -- Hoard imposes no such limit.)  This must be
                // a power of two! NB: This number is twice the maximum number of
                // PROCESSORS supported by Hoard.
                static int fMaxThreadHeaps;

                // number of CPUs, cached
                static int _numProcessors;
                static int _numProcessorsMask;
};



void
hoardHeap::incStats(int sizeclass, int updateU, int updateA)
{
        assert(_magic == HEAP_MAGIC);
        assert(updateU >= 0);
        assert(updateA >= 0);
        assert(sizeclass >= 0);
        assert(sizeclass < SIZE_CLASSES);
        _stats[sizeclass].incStats(updateU, updateA);
}


void
hoardHeap::incUStats(int sizeclass)
{
        assert(_magic == HEAP_MAGIC);
        assert(sizeclass >= 0);
        assert(sizeclass < SIZE_CLASSES);
        _stats[sizeclass].incUStats();
}


void
hoardHeap::decStats(int sizeclass, int updateU, int updateA)
{
        assert(_magic == HEAP_MAGIC);
        assert(updateU >= 0);
        assert(updateA >= 0);
        assert(sizeclass >= 0);
        assert(sizeclass < SIZE_CLASSES);
        _stats[sizeclass].decStats(updateU, updateA);
}


void
hoardHeap::decUStats(int sizeclass)
{
        assert(_magic == HEAP_MAGIC);
        assert(sizeclass >= 0);
        assert(sizeclass < SIZE_CLASSES);
        _stats[sizeclass].decUStats();
}


void
hoardHeap::getStats(int sizeclass, int &U, int &A)
{
        assert(_magic == HEAP_MAGIC);
        assert(sizeclass >= 0);
        assert(sizeclass < SIZE_CLASSES);
        _stats[sizeclass].getStats(U, A);
}


#if HEAP_STATS
int
hoardHeap::maxInUse(int sizeclass)
{
        assert(_magic == HEAP_MAGIC);
        return _stats[sizeclass].getUmax();
}


int
hoardHeap::maxAllocated(int sizeclass)
{
        assert(_magic == HEAP_MAGIC);
        return _stats[sizeclass].getAmax();
}
#endif  // HEAP_STATS


superblock *
hoardHeap::findAvailableSuperblock(int sizeclass,
        block * &b, processHeap * pHeap)
{
        assert(this);
        assert(_magic == HEAP_MAGIC);
        assert(sizeclass >= 0);
        assert(sizeclass < SIZE_CLASSES);

        superblock *sb = NULL;
        int reUsed = 0;

        // Look through the superblocks, starting with the almost-full ones
        // and going to the emptiest ones.  The Least Empty Bin for a
        // sizeclass is a conservative approximation (fixed after one
        // iteration) of the first bin that has superblocks in it, starting
        // with (surprise) the least-empty bin.

        for (int i = _leastEmptyBin[sizeclass]; i >= 0; i--) {
                sb = _superblocks[i][sizeclass];
                if (sb == NULL) {
                        if (i == _leastEmptyBin[sizeclass]) {
                                // There wasn't a superblock in this bin,
                                // so we adjust the least empty bin.
                                _leastEmptyBin[sizeclass]--;
                        }
                } else if (sb->getNumAvailable() > 0) {
                        assert(sb->getOwner() == this);
                        break;
                }
                sb = NULL;
        }

#if 1
        if (sb == NULL) {
                // Try to reuse a superblock.
                sb = reuse(sizeclass);
                if (sb) {
                        assert(sb->getOwner() == this);
                        reUsed = 1;
                }
        }
#endif

        if (sb != NULL) {
                // Sanity checks:
                //   This superblock is 'valid'.
                assert(sb->isValid());
                //   This superblock has the right ownership.
                assert(sb->getOwner() == this);

                int oldFullness = sb->getFullness();

                // Now get a block from the superblock.
                // This superblock must have space available.
                b = sb->getBlock();
                assert(b != NULL);

                // Update the stats.
                incUStats(sizeclass);

                if (reUsed) {
                        insertSuperblock(sizeclass, sb, pHeap);
                        // Fix the stats (since insert will just have incremented them
                        // by this amount).
                        decStats(sizeclass,
                                         sb->getNumBlocks() - sb->getNumAvailable(),
                                         sb->getNumBlocks());
                } else {
                        // If we've crossed a fullness group,
                        // move the superblock.
                        int fullness = sb->getFullness();

                        if (fullness != oldFullness) {
                                // Move the superblock.
                                moveSuperblock(sb, sizeclass, oldFullness, fullness);
                        }
                }
        }
        // Either we didn't find a superblock or we did and got a block.
        assert((sb == NULL) || (b != NULL));
        // Either we didn't get a block or we did and we also got a superblock.
        assert((b == NULL) || (sb != NULL));

        return sb;
}


int
hoardHeap::sizeClass(const size_t sz)
{
        // Find the size class for a given object size
        // (the smallest i such that _sizeTable[i] >= sz).
        int sizeclass = 0;
        while (_sizeTable[sizeclass] < sz) {
                sizeclass++;
                assert(sizeclass < SIZE_CLASSES);
        }
        return sizeclass;
}


size_t
hoardHeap::sizeFromClass(const int sizeclass)
{
        assert(sizeclass >= 0);
        assert(sizeclass < SIZE_CLASSES);
        return _sizeTable[sizeclass];
}


int
hoardHeap::getReleaseThreshold(const int sizeclass)
{
        assert(sizeclass >= 0);
        assert(sizeclass < SIZE_CLASSES);
        return _threshold[sizeclass];
}


int
hoardHeap::numBlocks(const int sizeclass)
{
        assert(sizeclass >= 0);
        assert(sizeclass < SIZE_CLASSES);
        const size_t s = sizeFromClass(sizeclass);
        assert(s > 0);
        const int blksize = align(sizeof(block) + s);
        // Compute the number of blocks that will go into this superblock.
        int nb = max_c(1, ((SUPERBLOCK_SIZE - sizeof(superblock)) / blksize));
        return nb;
}


void
hoardHeap::lock(void)
{
        assert(_magic == HEAP_MAGIC);
        hoardLock(_lock);
}


void
hoardHeap::unlock(void)
{
        assert(_magic == HEAP_MAGIC);
        hoardUnlock(_lock);
}


void
hoardHeap::initLock(void)
{
        // Initialize the per-heap lock.
        hoardLockInit(_lock, "hoard heap");
}


size_t
hoardHeap::align(const size_t sz)
{
        // Align sz up to the nearest multiple of ALIGNMENT.
        // This is much faster than using multiplication
        // and division.
        return (sz + ALIGNMENT_MASK) & ~ALIGNMENT_MASK;
}


void
hoardHeap::setIndex(int i)
{
        _index = i;
}


int
hoardHeap::getIndex(void)
{
        return _index;
}


void
hoardHeap::recycle(superblock *sb)
{
        assert(sb != NULL);
        assert(sb->getOwner() == this);
        assert(sb->getNumBlocks() > 1);
        assert(sb->getNext() == NULL);
        assert(sb->getPrev() == NULL);
        assert(hoardHeap::numBlocks(sb->getBlockSizeClass()) > 1);
        sb->insertBefore(_reusableSuperblocks);
        _reusableSuperblocks = sb;
        ++_reusableSuperblocksCount;
        // printf ("count: %d => %d\n", getIndex(), _reusableSuperblocksCount);
}


superblock *
hoardHeap::reuse(int sizeclass)
{
        if (_reusableSuperblocks == NULL)
                return NULL;

        // Make sure that we aren't using a sizeclass
        // that is too big for a 'normal' superblock.
        if (hoardHeap::numBlocks(sizeclass) <= 1)
                return NULL;

        // Pop off a superblock from the reusable-superblock list.
        assert(_reusableSuperblocksCount > 0);
        superblock *sb = _reusableSuperblocks;
        _reusableSuperblocks = sb->getNext();
        sb->remove();
        assert(sb->getNumBlocks() > 1);
        --_reusableSuperblocksCount;

        // Reformat the superblock if necessary.
        if (sb->getBlockSizeClass() != sizeclass) {
                decStats(sb->getBlockSizeClass(),
                        sb->getNumBlocks() - sb->getNumAvailable(),
                        sb->getNumBlocks());

                sb = new((char *)sb) superblock(numBlocks(sizeclass),
                        sizeclass, this);

                incStats(sizeclass,
                        sb->getNumBlocks() - sb->getNumAvailable(),
                        sb->getNumBlocks());
        }

        assert(sb->getOwner() == this);
        assert(sb->getBlockSizeClass() == sizeclass);
        return sb;
}

}       // namespace BPrivate

#endif // _HEAP_H_