/** * The author disclaims copyright to this source code. In place of * a legal notice, here is a blessing: * * May you do good and not evil. * May you find forgiveness for yourself and forgive others. * May you share freely, never taking more than you give. * * This file contains the APIs that implement a memory allocation subsystem * based on SQLite's memsys5 memory subsystem. Refer to * http://www.sqlite.org/malloc.html for more info. * * This version of the memory allocation subsystem omits all * use of malloc(). The application gives a block of memory * from which allocations are made and returned by the mplite_malloc() * and mplite_realloc() implementations. * * This memory allocator uses the following algorithm: * * 1. All memory allocation sizes are rounded up to a power of 2. * * 2. If two adjacent free blocks are the halves of a larger block, * then the two blocks are coalesced into the single larger block. * * 3. New memory is allocated from the first available free block. * * This algorithm is described in: J. M. Robson. "Bounds for Some Functions * Concerning Dynamic Storage Allocation". Journal of the Association for * Computing Machinery, Volume 21, Number 8, July 1974, pages 491-499. * * Let n be the size of the largest allocation divided by the minimum * allocation size (after rounding all sizes up to a power of 2.) Let M * be the maximum amount of memory ever outstanding at one time. Let * N be the total amount of memory available for allocation. Robson * proved that this memory allocator will never breakdown due to * fragmentation as long as the following constraint holds: * * N >= M*(1 + log2(n)/2) - n + 1 */ #ifndef MPLITE_H #define MPLITE_H #include /** * @brief The function call returns success */ #define MPLITE_OK 0 /** * @brief Invalid parameters are passed to a function */ #define MPLITE_ERR_INVPAR -1 /** * @brief Macro to fix unused parameter compiler warning */ #define MPLITE_UNUSED_PARAM(param) (void)(param) /** * @brief Maximum size of any allocation is ((1 << @ref MPLITE_LOGMAX) * * mplite_t.szAtom). Since mplite_t.szAtom is always at least 8 and * 32-bit integers are used, it is not actually possible to reach this * limit. */ #define MPLITE_LOGMAX 30 /** * @brief Maximum allocation size of this memory pool library. All allocations * must be a power of two and must be expressed by a 32-bit signed * integer. Hence the largest allocation is 0x40000000 or 1073741824. */ #define MPLITE_MAX_ALLOC_SIZE 0x40000000 /** * @brief An indicator that a function is a public API */ #define MPLITE_API /** * @brief Lock object to be used in a threadsafe memory pool */ typedef struct mplite_lock { void *arg; /**< Argument to be passed to acquire and release function pointers */ int (*acquire)(void *arg); /**< Function pointer to acquire a lock */ int (*release)(void *arg); /**< Function pointer to release a lock */ } mplite_lock_t; /** * @brief Memory pool object */ typedef struct mplite { /*------------------------------- Memory available for allocation -------------------------------*/ int szAtom; /**< Smallest possible allocation in bytes */ int nBlock; /**< Number of szAtom sized blocks in zPool */ uint8_t *zPool; /**< Memory available to be allocated */ mplite_lock_t lock; /**< Lock to control access to the memory allocation subsystem. */ /*---------------------- Performance statistics ----------------------*/ uint64_t nAlloc; /**< Total number of calls to malloc */ uint64_t totalAlloc; /**< Total of all malloc calls - includes internal fragmentation */ uint64_t totalExcess; /**< Total internal fragmentation */ uint32_t currentOut; /**< Current checkout, including internal fragmentation */ uint32_t currentCount; /**< Current number of distinct checkouts */ uint32_t maxOut; /**< Maximum instantaneous currentOut */ uint32_t maxCount; /**< Maximum instantaneous currentCount */ uint32_t maxRequest; /**< Largest allocation (exclusive of internal frag) */ /** * Lists of free blocks. aiFreelist[0] is a list of free blocks of * size mplite_t.szAtom. aiFreelist[1] holds blocks of size szAtom*2. * aiFreelist[2] holds free blocks of size szAtom*4. And so forth. */ int aiFreelist[MPLITE_LOGMAX + 1]; uint8_t *aCtrl; /**< Space for tracking which blocks are checked out and the size of each block. One byte per block. */ } mplite_t; /** * @brief Print string function pointer to be passed to @ref mplite_print_stats * function. This must be same as stdio's puts function mechanism which * automatically appends a new line character in every call. */ typedef int (*mplite_putsfunc_t)(const char* stats); #ifdef __cplusplus extern "C" { #endif /** * @brief Initialize the memory pool object. * @param[in,out] handle Pointer to a @ref mplite_t object which is allocated * by the caller either from stack, heap, or application's * memory space. * @param[in] buf Pointer to a large, contiguous chunk of memory space that * @ref mplite_t will use to satisfy all of its memory * allocation needs. This might point to a static array or it * might be memory obtained from some other application-specific * mechanism. * @param[in] buf_size The number of bytes of memory space pointed to by @ref * buf * @param[in] min_alloc Minimum size of an allocation. Any call to @ref * mplite_malloc where nBytes is less than min_alloc will * be rounded up to min_alloc. min_alloc must be a power of * two. * @param[in] lock Pointer to a lock object to control access to the memory * allocation subsystem of @ref mplite_t object. If this is * @ref NULL, @ref mplite_t will be non-threadsafe and can only * be safely used by a single thread. It is safe to allocate * this in stack because it will be copied to @ref mplite_t * object. * @return @ref MPLITE_OK on success and @ref MPLITE_ERR_INVPAR on invalid * parameters error. */ MPLITE_API int mplite_init(mplite_t *handle, const void *buf, const int buf_size, const int min_alloc, const mplite_lock_t *lock); /** * @brief Allocate bytes of memory * @param[in,out] handle Pointer to an initialized @ref mplite_t object * @param[in] nBytes Number of bytes to allocate * @return Non-NULL on success, NULL otherwise */ MPLITE_API void *mplite_malloc(mplite_t *handle, const int nBytes); /** * @brief Free memory * @param[in,out] handle Pointer to an initialized @ref mplite_t object * @param[in] pPrior Allocated buffer */ MPLITE_API void mplite_free(mplite_t *handle, const void *pPrior); /** * @brief Change the size of an existing memory allocation. * @param[in,out] handle Pointer to an initialized @ref mplite_t object * @param[in] pPrior Existing allocated memory * @param[in] nBytes Size of the new memory allocation. This is always a value * obtained from a prior call to mplite_roundup(). Hence, * this is always a non-negative power of two. If nBytes == 0 * that means that an oversize allocation (an allocation * larger than @ref MPLITE_MAX_ALLOC_SIZE) was requested and * this routine should return NULL without freeing pPrior. * @return Non-NULL on success, NULL otherwise */ MPLITE_API void *mplite_realloc(mplite_t *handle, const void *pPrior, const int nBytes); MPLITE_API int mplite_resize(mplite_t *handle, const void *pPrior, const int nBytes); /** * @brief Round up a request size to the next valid allocation size. * @param[in,out] handle Pointer to an initialized @ref mplite_t object * @param[in] n Request size * @return Positive non-zero value if the size can be allocated or zero if the * allocation is too large to be handled. */ MPLITE_API int mplite_roundup(mplite_t *handle, const int n); /** * @brief Print the statistics of the memory pool object * @param[in,out] handle Pointer to an initialized @ref mplite_t object * @param[in] logfunc Non-NULL log function of the caller. Refer to * @ref mplite_logfunc_t for the prototype of this function. */ MPLITE_API void mplite_print_stats(const mplite_t * const handle, const mplite_putsfunc_t logfunc); /** * @brief Macro to return the number of times mplite_malloc() has been called. */ #define mplite_alloc_count(handle) (((handle) != NULL)? (handle)->nAlloc : 0) /* return the largest available block size */ MPLITE_API int mplite_maxmem(mplite_t *handle); /* return the total available memory */ MPLITE_API int mplite_freemem(mplite_t *handle); #ifdef __cplusplus } #endif #endif /* #ifndef MPLITE_H */