zalloc.c revision 223854
197049Speter/* 2166124Srafan * This module derived from code donated to the FreeBSD Project by 397049Speter * Matthew Dillon <dillon@backplane.com> 497049Speter * 597049Speter * Copyright (c) 1998 The FreeBSD Project 697049Speter * All rights reserved. 797049Speter * 897049Speter * Redistribution and use in source and binary forms, with or without 997049Speter * modification, are permitted provided that the following conditions 1097049Speter * are met: 1197049Speter * 1. Redistributions of source code must retain the above copyright 1297049Speter * notice, this list of conditions and the following disclaimer. 1397049Speter * 2. Redistributions in binary form must reproduce the above copyright 1497049Speter * notice, this list of conditions and the following disclaimer in the 1597049Speter * documentation and/or other materials provided with the distribution. 1697049Speter * 1797049Speter * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 1897049Speter * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1997049Speter * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2097049Speter * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 2197049Speter * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2297049Speter * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2397049Speter * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2497049Speter * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2597049Speter * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2697049Speter * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2797049Speter * SUCH DAMAGE. 2897049Speter */ 2997049Speter 3097049Speter#include <sys/cdefs.h> 3197049Speter__FBSDID("$FreeBSD: head/lib/libstand/zalloc.c 223854 2011-07-08 01:35:33Z avatar $"); 3297049Speter 3350276Speter/* 3450276Speter * LIB/MEMORY/ZALLOC.C - self contained low-overhead memory pool/allocation 3550276Speter * subsystem 3650276Speter * 3750276Speter * This subsystem implements memory pools and memory allocation 3850276Speter * routines. 3950276Speter * 4050276Speter * Pools are managed via a linked list of 'free' areas. Allocating 41166124Srafan * memory creates holes in the freelist, freeing memory fills them. 4250276Speter * Since the freelist consists only of free memory areas, it is possible 4397049Speter * to allocate the entire pool without incuring any structural overhead. 4497049Speter * 4597049Speter * The system works best when allocating similarly-sized chunks of 4697049Speter * memory. Care must be taken to avoid fragmentation when 4797049Speter * allocating/deallocating dissimilar chunks. 4897049Speter * 4997049Speter * When a memory pool is first allocated, the entire pool is marked as 5097049Speter * allocated. This is done mainly because we do not want to modify any 5197049Speter * portion of a pool's data area until we are given permission. The 5297049Speter * caller must explicitly deallocate portions of the pool to make them 5397049Speter * available. 5497049Speter * 5597049Speter * z[n]xalloc() works like z[n]alloc() but the allocation is made from 5697049Speter * within the specified address range. If the segment could not be 5797049Speter * allocated, NULL is returned. WARNING! The address range will be 5897049Speter * aligned to an 8 or 16 byte boundry depending on the cpu so if you 5997049Speter * give an unaligned address range, unexpected results may occur. 6097049Speter * 6197049Speter * If a standard allocation fails, the reclaim function will be called 6297049Speter * to recover some space. This usually causes other portions of the 6397049Speter * same pool to be released. Memory allocations at this low level 6497049Speter * should not block but you can do that too in your reclaim function 6597049Speter * if you want. Reclaim does not function when z[n]xalloc() is used, 6697049Speter * only for z[n]alloc(). 6797049Speter * 6897049Speter * Allocation and frees of 0 bytes are valid operations. 6997049Speter */ 7097049Speter 7197049Speter#include "zalloc_defs.h" 7297049Speter 7397049Speter/* 7497049Speter * znalloc() - allocate memory (without zeroing) from pool. Call reclaim 7597049Speter * and retry if appropriate, return NULL if unable to allocate 7697049Speter * memory. 7797049Speter */ 7897049Speter 7997049Spetervoid * 8097049Speterznalloc(MemPool *mp, iaddr_t bytes) 8197049Speter{ 8297049Speter /* 8397049Speter * align according to pool object size (can be 0). This is 8497049Speter * inclusive of the MEMNODE_SIZE_MASK minimum alignment. 8597049Speter * 8697049Speter */ 8797049Speter bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK; 8897049Speter 8997049Speter if (bytes == 0) 9097049Speter return((void *)-1); 9197049Speter 9297049Speter /* 9397049Speter * locate freelist entry big enough to hold the object. If all objects 9497049Speter * are the same size, this is a constant-time function. 9597049Speter */ 9697049Speter 9797049Speter if (bytes <= mp->mp_Size - mp->mp_Used) { 9897049Speter MemNode **pmn; 9997049Speter MemNode *mn; 10097049Speter 10197049Speter for (pmn = &mp->mp_First; (mn=*pmn) != NULL; pmn = &mn->mr_Next) { 10297049Speter if (bytes > mn->mr_Bytes) 10397049Speter continue; 10497049Speter 10597049Speter /* 10697049Speter * Cut a chunk of memory out of the beginning of this 10797049Speter * block and fixup the link appropriately. 10897049Speter */ 10997049Speter 11097049Speter { 11197049Speter char *ptr = (char *)mn; 11297049Speter 11397049Speter if (mn->mr_Bytes == bytes) { 11497049Speter *pmn = mn->mr_Next; 11597049Speter } else { 11697049Speter mn = (MemNode *)((char *)mn + bytes); 11797049Speter mn->mr_Next = ((MemNode *)ptr)->mr_Next; 11897049Speter mn->mr_Bytes = ((MemNode *)ptr)->mr_Bytes - bytes; 11997049Speter *pmn = mn; 12097049Speter } 12197049Speter mp->mp_Used += bytes; 12297049Speter return(ptr); 12397049Speter } 12497049Speter } 12597049Speter } 12697049Speter 12797049Speter /* 12897049Speter * Memory pool is full, return NULL. 12997049Speter */ 13097049Speter 13197049Speter return(NULL); 13297049Speter} 13397049Speter 13497049Speter/* 13597049Speter * zfree() - free previously allocated memory 13697049Speter */ 13797049Speter 13897049Spetervoid 13997049Speterzfree(MemPool *mp, void *ptr, iaddr_t bytes) 14097049Speter{ 14197049Speter /* 14297049Speter * align according to pool object size (can be 0). This is 14397049Speter * inclusive of the MEMNODE_SIZE_MASK minimum alignment. 14497049Speter */ 14597049Speter bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK; 14697049Speter 14797049Speter if (bytes == 0) 14897049Speter return; 14997049Speter 15097049Speter /* 15197049Speter * panic if illegal pointer 15297049Speter */ 15397049Speter 15497049Speter if ((char *)ptr < (char *)mp->mp_Base || 15597049Speter (char *)ptr + bytes > (char *)mp->mp_End || 15697049Speter ((iaddr_t)ptr & MEMNODE_SIZE_MASK) != 0) 15797049Speter panic("zfree(%p,%ju): wild pointer", ptr, (uintmax_t)bytes); 15897049Speter 15997049Speter /* 16097049Speter * free the segment 16197049Speter */ 16250276Speter 16376726Speter { 16497049Speter MemNode **pmn; 16550276Speter MemNode *mn; 16697049Speter 16776726Speter mp->mp_Used -= bytes; 16876726Speter 16976726Speter for (pmn = &mp->mp_First; (mn = *pmn) != NULL; pmn = &mn->mr_Next) { 17076726Speter /* 17150276Speter * If area between last node and current node 17276726Speter * - check range 17376726Speter * - check merge with next area 17476726Speter * - check merge with previous area 17576726Speter */ 17650276Speter if ((char *)ptr <= (char *)mn) { 17750276Speter /* 17876726Speter * range check 17950276Speter */ 18076726Speter if ((char *)ptr + bytes > (char *)mn) { 18150276Speter panic("zfree(%p,%ju): corrupt memlist1", ptr, 18250276Speter (uintmax_t)bytes); 18397049Speter } 18497049Speter 18597049Speter /* 18697049Speter * merge against next area or create independant area 18797049Speter */ 18897049Speter 18997049Speter if ((char *)ptr + bytes == (char *)mn) { 19097049Speter ((MemNode *)ptr)->mr_Next = mn->mr_Next; 19197049Speter ((MemNode *)ptr)->mr_Bytes= bytes + mn->mr_Bytes; 19276726Speter } else { 19397049Speter ((MemNode *)ptr)->mr_Next = mn; 19497049Speter ((MemNode *)ptr)->mr_Bytes= bytes; 19597049Speter } 19697049Speter *pmn = mn = (MemNode *)ptr; 19776726Speter 19897049Speter /* 19997049Speter * merge against previous area (if there is a previous 20097049Speter * area). 20197049Speter */ 20297049Speter 20397049Speter if (pmn != &mp->mp_First) { 20497049Speter if ((char*)pmn + ((MemNode*)pmn)->mr_Bytes == (char*)ptr) { 20597049Speter ((MemNode *)pmn)->mr_Next = mn->mr_Next; 20697049Speter ((MemNode *)pmn)->mr_Bytes += mn->mr_Bytes; 20797049Speter mn = (MemNode *)pmn; 20897049Speter } 20997049Speter } 21097049Speter return; 21197049Speter /* NOT REACHED */ 21297049Speter } 213166124Srafan if ((char *)ptr < (char *)mn + mn->mr_Bytes) { 214166124Srafan panic("zfree(%p,%ju): corrupt memlist2", ptr, 21597049Speter (uintmax_t)bytes); 21697049Speter } 21797049Speter } 21897049Speter /* 21997049Speter * We are beyond the last MemNode, append new MemNode. Merge against 22097049Speter * previous area if possible. 22197049Speter */ 22297049Speter if (pmn == &mp->mp_First || 22397049Speter (char *)pmn + ((MemNode *)pmn)->mr_Bytes != (char *)ptr 22497049Speter ) { 22597049Speter ((MemNode *)ptr)->mr_Next = NULL; 22697049Speter ((MemNode *)ptr)->mr_Bytes = bytes; 22797049Speter *pmn = (MemNode *)ptr; 22897049Speter mn = (MemNode *)ptr; 22997049Speter } else { 23097049Speter ((MemNode *)pmn)->mr_Bytes += bytes; 23197049Speter mn = (MemNode *)pmn; 23297049Speter } 233166124Srafan } 23497049Speter} 23597049Speter 23697049Speter/* 23797049Speter * zextendPool() - extend memory pool to cover additional space. 23897049Speter * 23997049Speter * Note: the added memory starts out as allocated, you 24097049Speter * must free it to make it available to the memory subsystem. 24197049Speter * 24297049Speter * Note: mp_Size may not reflect (mp_End - mp_Base) range 24397049Speter * due to other parts of the system doing their own sbrk() 24497049Speter * calls. 24597049Speter */ 24697049Speter 24797049Spetervoid 24897049SpeterzextendPool(MemPool *mp, void *base, iaddr_t bytes) 24997049Speter{ 25097049Speter if (mp->mp_Size == 0) { 25197049Speter mp->mp_Base = base; 25297049Speter mp->mp_Used = bytes; 25397049Speter mp->mp_End = (char *)base + bytes; 25497049Speter mp->mp_Size = bytes; 25597049Speter } else { 25697049Speter void *pend = (char *)mp->mp_Base + mp->mp_Size; 25797049Speter 25897049Speter if (base < mp->mp_Base) { 25997049Speter mp->mp_Size += (char *)mp->mp_Base - (char *)base; 26097049Speter mp->mp_Used += (char *)mp->mp_Base - (char *)base; 26197049Speter mp->mp_Base = base; 26297049Speter } 26397049Speter base = (char *)base + bytes; 26497049Speter if (base > pend) { 26597049Speter mp->mp_Size += (char *)base - (char *)pend; 26697049Speter mp->mp_Used += (char *)base - (char *)pend; 26797049Speter mp->mp_End = (char *)base; 26897049Speter } 269166124Srafan } 27097049Speter} 271166124Srafan 272166124Srafan#ifdef ZALLOCDEBUG 273166124Srafan 274166124Srafanvoid 27597049Speterzallocstats(MemPool *mp) 27697049Speter{ 27797049Speter int abytes = 0; 27897049Speter int hbytes = 0; 27997049Speter int fcount = 0; 28097049Speter MemNode *mn; 28197049Speter 28297049Speter printf("%d bytes reserved", (int) mp->mp_Size); 28397049Speter 28497049Speter mn = mp->mp_First; 28597049Speter 28697049Speter if ((void *)mn != (void *)mp->mp_Base) { 28797049Speter abytes += (char *)mn - (char *)mp->mp_Base; 28897049Speter } 28997049Speter 29097049Speter while (mn) { 29197049Speter if ((char *)mn + mn->mr_Bytes != mp->mp_End) { 29297049Speter hbytes += mn->mr_Bytes; 29397049Speter ++fcount; 29497049Speter } 29597049Speter if (mn->mr_Next) 29697049Speter abytes += (char *)mn->mr_Next - ((char *)mn + mn->mr_Bytes); 29797049Speter mn = mn->mr_Next; 29897049Speter } 29997049Speter printf(" %d bytes allocated\n%d fragments (%d bytes fragmented)\n", 30097049Speter abytes, 30197049Speter fcount, 30297049Speter hbytes 30397049Speter ); 30497049Speter} 30597049Speter 30697049Speter#endif 30797049Speter 30897049Speter