SlamAllocator.h

/*
 * Copyright (c) 2008-2014, Pedigree Developers
 *
 * Please see the CONTRIB file in the root of the source tree for a full
 * list of contributors.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#ifndef SLAM_ALLOCATOR_H
#define SLAM_ALLOCATOR_H

#include "pedigree/kernel/Spinlock.h"
#include "pedigree/kernel/compiler.h"
#include "pedigree/kernel/processor/types.h"

#ifdef PEDIGREE_BENCHMARK
namespace SlamSupport
{
uintptr_t getHeapBase();
uintptr_t getHeapEnd();
void getPageAt(void *addr);
void unmapPage(void *page);
void unmapAll();
}  // namespace SlamSupport
#endif

class SlamAllocator;
class SlamCache;

#define SLAB_SIZE 1

#define SLAB_MINIMUM_SIZE (4096 * SLAB_SIZE)

#define USING_MAGIC 1

#define MAGIC_TYPE uintptr_t

#define MAGIC_VALUE 0xb00b1e55ULL

#define ABSOLUTE_MINIMUM_SIZE 64
#define ALL_HEADERS_SIZE                                            \
    (sizeof(SlamCache::Node) + sizeof(SlamAllocator::AllocHeader) + \
     sizeof(SlamAllocator::AllocFooter))
#define OBJECT_MINIMUM_SIZE                                             \
    (ALL_HEADERS_SIZE < ABSOLUTE_MINIMUM_SIZE ? ABSOLUTE_MINIMUM_SIZE : \
                                                ALL_HEADERS_SIZE)

#define DEBUGGING_SLAB_ALLOCATOR 0

#define TEMP_MAGIC 0x67845753

#ifdef USE_DEBUG_ALLOCATOR
#define OVERRUN_CHECK 0
#else
#define OVERRUN_CHECK 1
#endif

#define VIGILANT_OVERRUN_CHECK 0

#define VIGILANT_MAGIC 0x1337cafe

#define CRIPPLINGLY_VIGILANT 0

#define BOCHS_MAGIC_WATCHPOINTS 0

#define SCRIBBLE_FREED_BLOCKS 1

#define WARN_PAGE_SIZE_OR_LARGER 0

#define SLABS_FOR_HUGE_ALLOCS 0

#define VERBOSE_ISPOINTERVALID 0

#define EVERY_ALLOCATION_IS_A_SLAB 0

#ifdef SLAM_USE_DEBUG_ALLOCATOR
#define SLAM_LOCKED 1  // need the lock for the debug allocator
#elif !defined(THREADS)
#define SLAM_LOCKED 0  // never use if no threading
#else
#define SLAM_LOCKED 0
#endif

// Define this to enable the debug allocator (which is basically placement new).
// #define SLAM_USE_DEBUG_ALLOCATOR

class SlamCache
{
    // struct Node must be public so that sizeof(SlamCache::Node) is available.
  public:
    struct Node
    {
        Node *next;
#if USING_MAGIC
        MAGIC_TYPE magic;
#endif
    } __attribute__((aligned(16)));

    SlamCache();
    virtual ~SlamCache();

    void initialise(SlamAllocator *parent, size_t objectSize);

    uintptr_t allocate();

    void free(uintptr_t object);

    size_t recovery(size_t maxSlabs);

    bool isPointerValid(uintptr_t object) const;

    inline size_t objectSize() const
    {
        return m_ObjectSize;
    }

    inline size_t slabSize() const
    {
        return m_SlabSize;
    }

#if CRIPPLINGLY_VIGILANT
    void trackSlab(uintptr_t slab);
    void check();
#endif

  private:
    SlamCache(const SlamCache &);
    const SlamCache &operator=(const SlamCache &);

#ifdef MULTIPROCESSOR
#define NUM_LISTS 255
#else
#define NUM_LISTS 1
#endif
    typedef volatile Node *alignedNode;
    alignedNode m_PartialLists[NUM_LISTS];

    Node *pop(alignedNode *head);
    /* newHead = 0 to use newTail. */
    void push(alignedNode *head, Node *newTail, Node *newHead = 0);

    uintptr_t getSlab();
    void freeSlab(uintptr_t slab);

    Node *initialiseSlab(uintptr_t slab);

    size_t m_ObjectSize;
    size_t m_SlabSize;

    // This version of the allocator doesn't have a free list, instead
    // the reap() function returns memory directly to the VMM. This
    // avoids needing to lock the free list on MP systems.

    uintptr_t m_FirstSlab;

#ifdef THREADS

    Spinlock m_RecoveryLock;
#endif

    SlamAllocator *m_pParentAllocator;

    struct Node m_EmptyNode;
};

class SlamAllocator
{
  public:
    SlamAllocator();
    virtual ~SlamAllocator();

    void initialise();

#ifdef PEDIGREE_BENCHMARK
    // quickly clear all allocations from the allocator
    void clearAll();
#endif

    uintptr_t allocate(size_t nBytes);
    void free(uintptr_t mem);

    size_t recovery(size_t maxSlabs = 1);

    bool isPointerValid(uintptr_t mem)
#if !SLAM_LOCKED
        const
#endif
        ;
    bool isWithinHeap(uintptr_t mem) const;

    size_t allocSize(uintptr_t mem);

    static SlamAllocator &instance()
    {
#ifdef PEDIGREE_BENCHMARK
        static SlamAllocator instance;
        return instance;
#else
        return m_Instance;
#endif
    }

    size_t heapPageCount() const
    {
        return m_HeapPageCount;
    }

    uintptr_t getSlab(size_t fullSize);
    void freeSlab(uintptr_t address, size_t length);

#ifdef USE_DEBUG_ALLOCATOR
    inline size_t headerSize() const
    {
        return sizeof(AllocHeader);
    }
    inline size_t footerSize() const
    {
        return sizeof(AllocFooter);
    }
#endif

    void setVigilance(bool b)
    {
        m_bVigilant = b;
    }
    bool getVigilance() const
    {
        return m_bVigilant;
    }

  private:
    SlamAllocator(const SlamAllocator &);
    const SlamAllocator &operator=(const SlamAllocator &);

#ifndef PEDIGREE_BENCHMARK
    EXPORTED_PUBLIC static SlamAllocator m_Instance;
#endif

    void wipe();

    SlamCache m_Caches[32];

  public:
    struct AllocHeader
    {
        // Already-present and embedded Node fields.
        SlamCache::Node node;
#if OVERRUN_CHECK
#if BOCHS_MAGIC_WATCHPOINTS
        uint32_t catcher;
#endif
        size_t magic;
#if VIGILANT_OVERRUN_CHECK
        uintptr_t backtrace[NUM_SLAM_BT_FRAMES];
        size_t requested;
#endif
#endif
        SlamCache *cache;
    } __attribute__((aligned(16)));

    struct AllocFooter
    {
#if OVERRUN_CHECK
#if BOCHS_MAGIC_WATCHPOINTS
        uint32_t catcher;
#endif
        size_t magic;
#endif
    } __attribute__((aligned(16)));

  private:
    bool m_bInitialised;

    bool m_bVigilant;

#ifdef THREADS
    Spinlock m_SlabRegionLock;
#endif

    size_t m_HeapPageCount;

    uint64_t *m_SlabRegionBitmap;
    size_t m_SlabRegionBitmapEntries;

    uintptr_t m_Base;

#if SLAM_LOCKED
    Spinlock m_Lock;
#endif
};

#endif