md-heap.h

Go to the documentation of this file.

#ifndef MD_HEAP_H_INCLUDED
#define MD_HEAP_H_INCLUDED
/**********************************************************************/
/*
 * Copyright (c) 2016, Jetro AS
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONRIBUTORS ``AS IS'' AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
 * SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
 * OF SUCH DAMAGE.
 *
 * This file is part of the EVE platform.
 */

/**
 * \file
 * @brief Movable and discardable heap.
 *
 * @author DT, Jetro AS
 */ /******************************************************************/

#ifdef __cplusplus
  extern "C" {
#endif /* __cplusplus */

/**
 * \defgroup mdheap Movable and discardable heap
 * \ingroup util
 * \{
 */

struct md_heap_t;

/**
 * Heap index type
 */
typedef uint8_t md_idx_t;

/**
 * Entry relocation handler
 *
 * @param Ptr     Address of a variable which contains a pointer to the allocated memory block
 * @param Addr    New value for the pointer
 */
typedef void (*md_reloc_handler_t)(void **Ptr, void *Addr);

/**
 * Swap-out user callback
 *
 * @param Heap    Heap instance pointer
 * @param Pos     Position in the external memory where data to be swapped out
 * @param Data    Address of the data in the internal memory
 * @param Size    Size of the data
 * @return        true if data was swapped out, false otherwise
 */
typedef bool (*md_swap_out_cb_t)(const struct md_heap_t *Heap, uint32_t Pos, const uint8_t **DataPtr, uint32_t Size);

/**
 * Swap-in user callback
 *
 * @param Heap    Heap instance pointer
 * @param Data    Address of the data buffer in the internal memory to be filled by data
 * @param Pos     Position in the external memory where data is located
 * @param Size    Size of the data
 * @return        true if data was swapped in, false otherwise
 */
typedef bool (*md_swap_in_cb_t)(const struct md_heap_t *Heap, uint8_t **DataPtr, uint32_t Pos, uint32_t Size);

/**
 * Tiny double-linked list
 */
struct md_list_t
{
  md_idx_t Prev;                    /*!< Index of the previous (left-hand) entry */
  md_idx_t Next;                    /*!< Index of the next (right-hand) entry */
};

/**
 * Memory block descriptor
 */
struct md_descriptor_t
{
  struct md_list_t Link;            /*!< "All blocks" linked list entry */
  struct md_list_t Free;            /*!< "Free blocks" linked list entry */
  uint16_t Size;                    /*!< Size of the block */
  uint16_t Pos;                     /*!< Offset of the block in the arena */
  void **RelocPtr;                  /*!< Client-defined relocation pointer */
  md_reloc_handler_t RelocHandler; /*!< Client-defined relocation handler */
};

/**
 * Heap statistics
 */
struct md_stat_t
{
  uint32_t AllocSize;               /*!< Amount of data allocated in the heap */
  uint32_t AllocMaxSize;            /*!< Max registered amount of data allocated in the heap */
  uint32_t SwappedOut;              /*!< Amount of data swapped out */
  uint8_t AllocCount;               /*!< Number of allocated blocks */
  uint8_t AllocMaxCount;            /*!< Max registered number of allocated blocks */
  uint8_t DescrCount;               /*!< Number of used descriptors */
  uint8_t DescrMaxCount;            /*!< Max registered number of used descriptors */
};

/**
 * Heap state
 */
struct md_state_t
{
  uint8_t FreeBlockIdx;             /*!< Index of a free block currently used for allocation */
  uint8_t ExternalRam;              /*!< Index of the first block in the external RAM */
  struct md_stat_t Stat;            /*!< Heap statistics */
};

/**
 * MD Heap instance
 */
struct md_heap_t
{
  struct md_descriptor_t *Entries;  /*!< Descriptor table */
  uint32_t NumEntries;              /*!< Number of entries in the descriptor table */
  uint8_t *RamBuffer;               /*!< Allocable memory region */
  uint32_t RamBufferSize;           /*!< Size of the allocable memory region */
  struct md_state_t *State;         /*!< Heap state */
  uint32_t ExtRamSize;              /*!< External RAM size */
  md_swap_out_cb_t SwapOut;         /*!< Swap out callback */
  md_swap_in_cb_t SwapIn;           /*!< Swap in callback */
};

/**
 * MD auto lock
 */
struct md_auto_lock_t
{
  const struct md_heap_t *Heap;     /*!< Pointer to the heap */
  md_reloc_handler_t Handler;       /*!< Relocation handler */
  void **Ptr;                       /*!< Address of a variable which contains
                                         a pointer to the allocated memory block */
};

void MemInit(const struct md_heap_t *Heap);
void *MemAlloc(const struct md_heap_t *Heap, uint32_t Size);
void MemFree(const struct md_heap_t *Heap, void *Ptr);
void MemUnlock(const struct md_heap_t *Heap, void *Ptr, md_reloc_handler_t Handler);
bool MemLock(const struct md_heap_t *Heap, void *Ptr, md_reloc_handler_t *PrevHandler);

/**
 * Compact the memory pool, collect small free blocks into a big one(s)
 *
 * @param Heap    Heap instance pointer
 */
void MemDefragment(const struct md_heap_t *Heap);

void MemGenericRelocator(void **ptr, void *addr);

static inline bool MemInHeap(const struct md_heap_t *Heap, void *Ptr)
{
  return ((uint8_t *) Ptr >= &Heap->RamBuffer[0])
      && ((uint8_t *) Ptr < &Heap->RamBuffer[Heap->RamBufferSize]);
}

__attribute__((always_inline))
static inline void MemAutoLockDestructor(struct md_auto_lock_t *Lock)
{
  MemUnlock(Lock->Heap, Lock->Ptr, Lock->Handler);
}

void MemPrintStat(const struct md_heap_t *Heap);
void MemPrint(const struct md_heap_t *Heap);
void MemPrintExt(const struct md_heap_t *Heap);

#define SYSTEM_HEAP(RequestedNumEntries) \
  extern uint32_t __HeapBase, __StackLimit;                               \
  static struct md_descriptor_t SystemHeapEntries[RequestedNumEntries];   \
  static struct md_state_t SystemHeapState;                               \
  struct md_heap_t SystemHeap;                                            \
  static void SystemHeapCtor(void) __attribute__((constructor));          \
  static void SystemHeapCtor(void)                                        \
  {                                                                       \
    SystemHeap.Entries = SystemHeapEntries;                               \
    SystemHeap.NumEntries = (RequestedNumEntries);                        \
    SystemHeap.RamBuffer = (uint8_t *) &__HeapBase;                       \
    SystemHeap.RamBufferSize =                                            \
        (uint32_t) &__StackLimit - (uint32_t) &__HeapBase;                \
    SystemHeap.State = &SystemHeapState;                                  \
    MemInit(&SystemHeap);                                                 \
    printf("[HEAP] %d bytes (%d entries) in system heap.\n",              \
        (unsigned) SystemHeap.RamBufferSize,                              \
        (unsigned) SystemHeap.NumEntries);                                \
  }                                                                       \
  struct md_heap_t SystemHeap

/** Auto lock */
#define MEM_AUTO_LOCK(TheName, TheHeap, ThePtr) \
  struct md_auto_lock_t TheName \
      __attribute__((cleanup(MemAutoLockDestructor))) \
      = { .Heap = TheHeap, .Ptr = (void **) ThePtr, }; \
  { \
    bool Ret = MemLock(TheHeap, ThePtr, &TheName.Handler); \
    assert(Ret); \
  } \
  do { } while (0)

/** \} */

#ifdef __cplusplus
  }
#endif /* __cplusplus */

#endif /* MD_HEAP_H_INCLUDED */