199767f8919635c4928607450d9e0abb932109ceToomas Soome * This module derived from code donated to the FreeBSD Project by
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Matthew Dillon <dillon@backplane.com>
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Copyright (c) 1998 The FreeBSD Project
199767f8919635c4928607450d9e0abb932109ceToomas Soome * All rights reserved.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Redistribution and use in source and binary forms, with or without
199767f8919635c4928607450d9e0abb932109ceToomas Soome * modification, are permitted provided that the following conditions
199767f8919635c4928607450d9e0abb932109ceToomas Soome * 1. Redistributions of source code must retain the above copyright
199767f8919635c4928607450d9e0abb932109ceToomas Soome * notice, this list of conditions and the following disclaimer.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * 2. Redistributions in binary form must reproduce the above copyright
199767f8919635c4928607450d9e0abb932109ceToomas Soome * notice, this list of conditions and the following disclaimer in the
199767f8919635c4928607450d9e0abb932109ceToomas Soome * documentation and/or other materials provided with the distribution.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
199767f8919635c4928607450d9e0abb932109ceToomas Soome * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
199767f8919635c4928607450d9e0abb932109ceToomas Soome * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
199767f8919635c4928607450d9e0abb932109ceToomas Soome * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
199767f8919635c4928607450d9e0abb932109ceToomas Soome * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
199767f8919635c4928607450d9e0abb932109ceToomas Soome * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
199767f8919635c4928607450d9e0abb932109ceToomas Soome * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
199767f8919635c4928607450d9e0abb932109ceToomas Soome * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
199767f8919635c4928607450d9e0abb932109ceToomas Soome * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
199767f8919635c4928607450d9e0abb932109ceToomas Soome * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
199767f8919635c4928607450d9e0abb932109ceToomas Soome * SUCH DAMAGE.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * LIB/MEMORY/ZALLOC.C - self contained low-overhead memory pool/allocation
199767f8919635c4928607450d9e0abb932109ceToomas Soome * This subsystem implements memory pools and memory allocation
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Pools are managed via a linked list of 'free' areas. Allocating
199767f8919635c4928607450d9e0abb932109ceToomas Soome * memory creates holes in the freelist, freeing memory fills them.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Since the freelist consists only of free memory areas, it is possible
199767f8919635c4928607450d9e0abb932109ceToomas Soome * to allocate the entire pool without incuring any structural overhead.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * The system works best when allocating similarly-sized chunks of
199767f8919635c4928607450d9e0abb932109ceToomas Soome * memory. Care must be taken to avoid fragmentation when
199767f8919635c4928607450d9e0abb932109ceToomas Soome * allocating/deallocating dissimilar chunks.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * When a memory pool is first allocated, the entire pool is marked as
199767f8919635c4928607450d9e0abb932109ceToomas Soome * allocated. This is done mainly because we do not want to modify any
199767f8919635c4928607450d9e0abb932109ceToomas Soome * portion of a pool's data area until we are given permission. The
199767f8919635c4928607450d9e0abb932109ceToomas Soome * caller must explicitly deallocate portions of the pool to make them
199767f8919635c4928607450d9e0abb932109ceToomas Soome * available.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * z[n]xalloc() works like z[n]alloc() but the allocation is made from
199767f8919635c4928607450d9e0abb932109ceToomas Soome * within the specified address range. If the segment could not be
199767f8919635c4928607450d9e0abb932109ceToomas Soome * allocated, NULL is returned. WARNING! The address range will be
199767f8919635c4928607450d9e0abb932109ceToomas Soome * aligned to an 8 or 16 byte boundry depending on the cpu so if you
199767f8919635c4928607450d9e0abb932109ceToomas Soome * give an unaligned address range, unexpected results may occur.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * If a standard allocation fails, the reclaim function will be called
199767f8919635c4928607450d9e0abb932109ceToomas Soome * to recover some space. This usually causes other portions of the
199767f8919635c4928607450d9e0abb932109ceToomas Soome * same pool to be released. Memory allocations at this low level
199767f8919635c4928607450d9e0abb932109ceToomas Soome * should not block but you can do that too in your reclaim function
199767f8919635c4928607450d9e0abb932109ceToomas Soome * if you want. Reclaim does not function when z[n]xalloc() is used,
199767f8919635c4928607450d9e0abb932109ceToomas Soome * only for z[n]alloc().
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Allocation and frees of 0 bytes are valid operations.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Objects in the pool must be aligned to at least the size of struct MemNode.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * They must also be aligned to MALLOCALIGN, which should normally be larger
199767f8919635c4928607450d9e0abb932109ceToomas Soome * than the struct, so assert that to be so at compile time.
199767f8919635c4928607450d9e0abb932109ceToomas Soometypedef char assert_align[(sizeof(struct MemNode) <= MALLOCALIGN) ? 1 : -1];
199767f8919635c4928607450d9e0abb932109ceToomas Soome * znalloc() - allocate memory (without zeroing) from pool. Call reclaim
199767f8919635c4928607450d9e0abb932109ceToomas Soome * and retry if appropriate, return NULL if unable to allocate
199767f8919635c4928607450d9e0abb932109ceToomas Soome * align according to pool object size (can be 0). This is
199767f8919635c4928607450d9e0abb932109ceToomas Soome * inclusive of the MEMNODE_SIZE_MASK minimum alignment.
199767f8919635c4928607450d9e0abb932109ceToomas Soome bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK;
199767f8919635c4928607450d9e0abb932109ceToomas Soome return((void *)-1);
199767f8919635c4928607450d9e0abb932109ceToomas Soome * locate freelist entry big enough to hold the object. If all objects
199767f8919635c4928607450d9e0abb932109ceToomas Soome * are the same size, this is a constant-time function.
199767f8919635c4928607450d9e0abb932109ceToomas Soome for (pmn = &mp->mp_First; (mn=*pmn) != NULL; pmn = &mn->mr_Next) {
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Cut a chunk of memory out of the beginning of this
199767f8919635c4928607450d9e0abb932109ceToomas Soome * block and fixup the link appropriately.
199767f8919635c4928607450d9e0abb932109ceToomas Soome mn->mr_Bytes = ((MemNode *)ptr)->mr_Bytes - bytes;
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Memory pool is full, return NULL.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * zfree() - free previously allocated memory
199767f8919635c4928607450d9e0abb932109ceToomas Soome * align according to pool object size (can be 0). This is
199767f8919635c4928607450d9e0abb932109ceToomas Soome * inclusive of the MEMNODE_SIZE_MASK minimum alignment.
199767f8919635c4928607450d9e0abb932109ceToomas Soome bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK;
199767f8919635c4928607450d9e0abb932109ceToomas Soome * panic if illegal pointer
199767f8919635c4928607450d9e0abb932109ceToomas Soome panic("zfree(%p,%ju): wild pointer", ptr, (uintmax_t)bytes);
199767f8919635c4928607450d9e0abb932109ceToomas Soome * free the segment
199767f8919635c4928607450d9e0abb932109ceToomas Soome for (pmn = &mp->mp_First; (mn = *pmn) != NULL; pmn = &mn->mr_Next) {
199767f8919635c4928607450d9e0abb932109ceToomas Soome * If area between last node and current node
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - check range
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - check merge with next area
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - check merge with previous area
199767f8919635c4928607450d9e0abb932109ceToomas Soome * range check
199767f8919635c4928607450d9e0abb932109ceToomas Soome * merge against next area or create independant area
199767f8919635c4928607450d9e0abb932109ceToomas Soome ((MemNode *)ptr)->mr_Bytes= bytes + mn->mr_Bytes;
199767f8919635c4928607450d9e0abb932109ceToomas Soome * merge against previous area (if there is a previous
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((char*)pmn + ((MemNode*)pmn)->mr_Bytes == (char*)ptr) {
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* NOT REACHED */
199767f8919635c4928607450d9e0abb932109ceToomas Soome * We are beyond the last MemNode, append new MemNode. Merge against
199767f8919635c4928607450d9e0abb932109ceToomas Soome * previous area if possible.
199767f8919635c4928607450d9e0abb932109ceToomas Soome (char *)pmn + ((MemNode *)pmn)->mr_Bytes != (char *)ptr
199767f8919635c4928607450d9e0abb932109ceToomas Soome * zextendPool() - extend memory pool to cover additional space.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Note: the added memory starts out as allocated, you
199767f8919635c4928607450d9e0abb932109ceToomas Soome * must free it to make it available to the memory subsystem.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Note: mp_Size may not reflect (mp_End - mp_Base) range
199767f8919635c4928607450d9e0abb932109ceToomas Soome * due to other parts of the system doing their own sbrk()
199767f8919635c4928607450d9e0abb932109ceToomas SoomezextendPool(MemPool *mp, void *base, uintptr_t bytes)
199767f8919635c4928607450d9e0abb932109ceToomas Soome void *pend = (char *)mp->mp_Base + mp->mp_Size;
199767f8919635c4928607450d9e0abb932109ceToomas Soome mp->mp_Size += (char *)mp->mp_Base - (char *)base;
199767f8919635c4928607450d9e0abb932109ceToomas Soome mp->mp_Used += (char *)mp->mp_Base - (char *)base;
199767f8919635c4928607450d9e0abb932109ceToomas Soome printf("%d bytes reserved", (int) mp->mp_Size);
199767f8919635c4928607450d9e0abb932109ceToomas Soome abytes += (char *)mn->mr_Next - ((char *)mn + mn->mr_Bytes);
199767f8919635c4928607450d9e0abb932109ceToomas Soome printf(" %d bytes allocated\n%d fragments (%d bytes fragmented)\n",