/*
* This module derived from code donated to the FreeBSD Project by
* Matthew Dillon <dillon@backplane.com>
*
* Copyright (c) 1998 The FreeBSD Project
* 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.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``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 OR CONTRIBUTORS 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.
*/
#include <sys/cdefs.h>
__FBSDID("$FreeBSD$");
#include <sys/param.h>
/*
* LIB/MEMORY/ZALLOC.C - self contained low-overhead memory pool/allocation
* subsystem
*
* This subsystem implements memory pools and memory allocation
* routines.
*
* Pools are managed via a linked list of 'free' areas. Allocating
* memory creates holes in the freelist, freeing memory fills them.
* Since the freelist consists only of free memory areas, it is possible
* to allocate the entire pool without incuring any structural overhead.
*
* The system works best when allocating similarly-sized chunks of
* memory. Care must be taken to avoid fragmentation when
* allocating/deallocating dissimilar chunks.
*
* When a memory pool is first allocated, the entire pool is marked as
* allocated. This is done mainly because we do not want to modify any
* portion of a pool's data area until we are given permission. The
* caller must explicitly deallocate portions of the pool to make them
* available.
*
* z[n]xalloc() works like z[n]alloc() but the allocation is made from
* within the specified address range. If the segment could not be
* allocated, NULL is returned. WARNING! The address range will be
* aligned to an 8 or 16 byte boundry depending on the cpu so if you
* give an unaligned address range, unexpected results may occur.
*
* If a standard allocation fails, the reclaim function will be called
* to recover some space. This usually causes other portions of the
* same pool to be released. Memory allocations at this low level
* should not block but you can do that too in your reclaim function
* if you want. Reclaim does not function when z[n]xalloc() is used,
* only for z[n]alloc().
*
* Allocation and frees of 0 bytes are valid operations.
*/
#include "zalloc_defs.h"
/*
* Objects in the pool must be aligned to at least the size of struct MemNode.
* They must also be aligned to MALLOCALIGN, which should normally be larger
* than the struct, so assert that to be so at compile time.
*/
typedef char assert_align[(sizeof(struct MemNode) <= MALLOCALIGN) ? 1 : -1];
#define MEMNODE_SIZE_MASK MALLOCALIGN_MASK
/*
* znalloc() - allocate memory (without zeroing) from pool. Call reclaim
* and retry if appropriate, return NULL if unable to allocate
* memory.
*/
void *
znalloc(MemPool *mp, uintptr_t bytes, size_t align)
{
MemNode **pmn;
MemNode *mn;
/*
* align according to pool object size (can be 0). This is
* inclusive of the MEMNODE_SIZE_MASK minimum alignment.
*
*/
bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK;
if (bytes == 0)
return ((void *)-1);
/*
* locate freelist entry big enough to hold the object. If all objects
* are the same size, this is a constant-time function.
*/
if (bytes > mp->mp_Size - mp->mp_Used)
return (NULL);
for (pmn = &mp->mp_First; (mn = *pmn) != NULL; pmn = &mn->mr_Next) {
char *ptr = (char *)mn;
uintptr_t dptr;
char *aligned;
size_t extra;
dptr = (uintptr_t)(ptr + MALLOCALIGN); /* pointer to data */
aligned = (char *)(roundup2(dptr, align) - MALLOCALIGN);
extra = aligned - ptr;
if (bytes + extra > mn->mr_Bytes)
continue;
/*
* Cut extra from head and create new memory node from
* remainder.
*/
if (extra != 0) {
MemNode *new;
new = (MemNode *)aligned;
new->mr_Next = mn->mr_Next;
new->mr_Bytes = mn->mr_Bytes - extra;
/* And update current memory node */
mn->mr_Bytes = extra;
mn->mr_Next = new;
/* In next iteration, we will get our aligned address */
continue;
}
/*
* Cut a chunk of memory out of the beginning of this
* block and fixup the link appropriately.
*/
if (mn->mr_Bytes == bytes) {
*pmn = mn->mr_Next;
} else {
mn = (MemNode *)((char *)mn + bytes);
mn->mr_Next = ((MemNode *)ptr)->mr_Next;
mn->mr_Bytes = ((MemNode *)ptr)->mr_Bytes - bytes;
*pmn = mn;
}
mp->mp_Used += bytes;
return(ptr);
}
/*
* Memory pool is full, return NULL.
*/
return (NULL);
}
/*
* zfree() - free previously allocated memory
*/
void
zfree(MemPool *mp, void *ptr, uintptr_t bytes)
{
MemNode **pmn;
MemNode *mn;
/*
* align according to pool object size (can be 0). This is
* inclusive of the MEMNODE_SIZE_MASK minimum alignment.
*/
bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK;
if (bytes == 0)
return;
/*
* panic if illegal pointer
*/
if ((char *)ptr < (char *)mp->mp_Base ||
(char *)ptr + bytes > (char *)mp->mp_End ||
((uintptr_t)ptr & MEMNODE_SIZE_MASK) != 0)
panic("zfree(%p,%ju): wild pointer", ptr, (uintmax_t)bytes);
/*
* free the segment
*/
mp->mp_Used -= bytes;
for (pmn = &mp->mp_First; (mn = *pmn) != NULL; pmn = &mn->mr_Next) {
/*
* If area between last node and current node
* - check range
* - check merge with next area
* - check merge with previous area
*/
if ((char *)ptr <= (char *)mn) {
/*
* range check
*/
if ((char *)ptr + bytes > (char *)mn) {
panic("zfree(%p,%ju): corrupt memlist1", ptr,
(uintmax_t)bytes);
}
/*
* merge against next area or create independant area
*/
if ((char *)ptr + bytes == (char *)mn) {
((MemNode *)ptr)->mr_Next = mn->mr_Next;
((MemNode *)ptr)->mr_Bytes =
bytes + mn->mr_Bytes;
} else {
((MemNode *)ptr)->mr_Next = mn;
((MemNode *)ptr)->mr_Bytes = bytes;
}
*pmn = mn = (MemNode *)ptr;
/*
* merge against previous area (if there is a previous
* area).
*/
if (pmn != &mp->mp_First) {
if ((char *)pmn + ((MemNode*)pmn)->mr_Bytes ==
(char *)ptr) {
((MemNode *)pmn)->mr_Next = mn->mr_Next;
((MemNode *)pmn)->mr_Bytes +=
mn->mr_Bytes;
mn = (MemNode *)pmn;
}
}
return;
}
if ((char *)ptr < (char *)mn + mn->mr_Bytes) {
panic("zfree(%p,%ju): corrupt memlist2", ptr,
(uintmax_t)bytes);
}
}
/*
* We are beyond the last MemNode, append new MemNode. Merge against
* previous area if possible.
*/
if (pmn == &mp->mp_First ||
(char *)pmn + ((MemNode *)pmn)->mr_Bytes != (char *)ptr) {
((MemNode *)ptr)->mr_Next = NULL;
((MemNode *)ptr)->mr_Bytes = bytes;
*pmn = (MemNode *)ptr;
mn = (MemNode *)ptr;
} else {
((MemNode *)pmn)->mr_Bytes += bytes;
mn = (MemNode *)pmn;
}
}
/*
* zextendPool() - extend memory pool to cover additional space.
*
* Note: the added memory starts out as allocated, you
* must free it to make it available to the memory subsystem.
*
* Note: mp_Size may not reflect (mp_End - mp_Base) range
* due to other parts of the system doing their own sbrk()
* calls.
*/
void
zextendPool(MemPool *mp, void *base, uintptr_t bytes)
{
if (mp->mp_Size == 0) {
mp->mp_Base = base;
mp->mp_Used = bytes;
mp->mp_End = (char *)base + bytes;
mp->mp_Size = bytes;
} else {
void *pend = (char *)mp->mp_Base + mp->mp_Size;
if (base < mp->mp_Base) {
mp->mp_Size += (char *)mp->mp_Base - (char *)base;
mp->mp_Used += (char *)mp->mp_Base - (char *)base;
mp->mp_Base = base;
}
base = (char *)base + bytes;
if (base > pend) {
mp->mp_Size += (char *)base - (char *)pend;
mp->mp_Used += (char *)base - (char *)pend;
mp->mp_End = (char *)base;
}
}
}
#ifdef ZALLOCDEBUG
void
zallocstats(MemPool *mp)
{
int abytes = 0;
int hbytes = 0;
int fcount = 0;
MemNode *mn;
printf("%d bytes reserved", (int)mp->mp_Size);
mn = mp->mp_First;
if ((void *)mn != (void *)mp->mp_Base) {
abytes += (char *)mn - (char *)mp->mp_Base;
}
while (mn != NULL) {
if ((char *)mn + mn->mr_Bytes != mp->mp_End) {
hbytes += mn->mr_Bytes;
++fcount;
}
if (mn->mr_Next != NULL) {
abytes += (char *)mn->mr_Next -
((char *)mn + mn->mr_Bytes);
}
mn = mn->mr_Next;
}
printf(" %d bytes allocated\n%d fragments (%d bytes fragmented)\n",
abytes, fcount, hbytes);
}
#endif
