1/*
2 * This module derived from code donated to the FreeBSD Project by
3 * Matthew Dillon <dillon@backplane.com>
4 *
5 * Copyright (c) 1998 The FreeBSD Project
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30#include <sys/cdefs.h>
31__FBSDID("$FreeBSD: releng/11.0/lib/libstand/zalloc.c 261530 2014-02-05 22:53:58Z ian $");
32
33/*
34 * LIB/MEMORY/ZALLOC.C	- self contained low-overhead memory pool/allocation
35 *			  subsystem
36 *
37 *	This subsystem implements memory pools and memory allocation
38 *	routines.
39 *
40 *	Pools are managed via a linked list of 'free' areas.  Allocating
41 *	memory creates holes in the freelist, freeing memory fills them.
42 *	Since the freelist consists only of free memory areas, it is possible
43 *	to allocate the entire pool without incuring any structural overhead.
44 *
45 *	The system works best when allocating similarly-sized chunks of
46 *	memory.  Care must be taken to avoid fragmentation when
47 *	allocating/deallocating dissimilar chunks.
48 *
49 *	When a memory pool is first allocated, the entire pool is marked as
50 *	allocated.  This is done mainly because we do not want to modify any
51 *	portion of a pool's data area until we are given permission.  The
52 *	caller must explicitly deallocate portions of the pool to make them
53 *	available.
54 *
55 *	z[n]xalloc() works like z[n]alloc() but the allocation is made from
56 *	within the specified address range.  If the segment could not be
57 *	allocated, NULL is returned.  WARNING!  The address range will be
58 *	aligned to an 8 or 16 byte boundry depending on the cpu so if you
59 *	give an unaligned address range, unexpected results may occur.
60 *
61 *	If a standard allocation fails, the reclaim function will be called
62 *	to recover some space.  This usually causes other portions of the
63 *	same pool to be released.  Memory allocations at this low level
64 *	should not block but you can do that too in your reclaim function
65 *	if you want.  Reclaim does not function when z[n]xalloc() is used,
66 *	only for z[n]alloc().
67 *
68 *	Allocation and frees of 0 bytes are valid operations.
69 */
70
71#include "zalloc_defs.h"
72
73/*
74 * Objects in the pool must be aligned to at least the size of struct MemNode.
75 * They must also be aligned to MALLOCALIGN, which should normally be larger
76 * than the struct, so assert that to be so at compile time.
77 */
78typedef char assert_align[(sizeof(struct MemNode) <= MALLOCALIGN) ? 1 : -1];
79
80#define	MEMNODE_SIZE_MASK	MALLOCALIGN_MASK
81
82/*
83 * znalloc() -	allocate memory (without zeroing) from pool.  Call reclaim
84 *		and retry if appropriate, return NULL if unable to allocate
85 *		memory.
86 */
87
88void *
89znalloc(MemPool *mp, uintptr_t bytes)
90{
91    /*
92     * align according to pool object size (can be 0).  This is
93     * inclusive of the MEMNODE_SIZE_MASK minimum alignment.
94     *
95     */
96    bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK;
97
98    if (bytes == 0)
99	return((void *)-1);
100
101    /*
102     * locate freelist entry big enough to hold the object.  If all objects
103     * are the same size, this is a constant-time function.
104     */
105
106    if (bytes <= mp->mp_Size - mp->mp_Used) {
107	MemNode **pmn;
108	MemNode *mn;
109
110	for (pmn = &mp->mp_First; (mn=*pmn) != NULL; pmn = &mn->mr_Next) {
111	    if (bytes > mn->mr_Bytes)
112		continue;
113
114	    /*
115	     *  Cut a chunk of memory out of the beginning of this
116	     *  block and fixup the link appropriately.
117	     */
118
119	    {
120		char *ptr = (char *)mn;
121
122		if (mn->mr_Bytes == bytes) {
123		    *pmn = mn->mr_Next;
124		} else {
125		    mn = (MemNode *)((char *)mn + bytes);
126		    mn->mr_Next  = ((MemNode *)ptr)->mr_Next;
127		    mn->mr_Bytes = ((MemNode *)ptr)->mr_Bytes - bytes;
128		    *pmn = mn;
129		}
130		mp->mp_Used += bytes;
131		return(ptr);
132	    }
133	}
134    }
135
136    /*
137     * Memory pool is full, return NULL.
138     */
139
140    return(NULL);
141}
142
143/*
144 * zfree() - free previously allocated memory
145 */
146
147void
148zfree(MemPool *mp, void *ptr, uintptr_t bytes)
149{
150    /*
151     * align according to pool object size (can be 0).  This is
152     * inclusive of the MEMNODE_SIZE_MASK minimum alignment.
153     */
154    bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK;
155
156    if (bytes == 0)
157	return;
158
159    /*
160     * panic if illegal pointer
161     */
162
163    if ((char *)ptr < (char *)mp->mp_Base ||
164	(char *)ptr + bytes > (char *)mp->mp_End ||
165	((uintptr_t)ptr & MEMNODE_SIZE_MASK) != 0)
166	panic("zfree(%p,%ju): wild pointer", ptr, (uintmax_t)bytes);
167
168    /*
169     * free the segment
170     */
171
172    {
173	MemNode **pmn;
174	MemNode *mn;
175
176	mp->mp_Used -= bytes;
177
178	for (pmn = &mp->mp_First; (mn = *pmn) != NULL; pmn = &mn->mr_Next) {
179	    /*
180	     * If area between last node and current node
181	     *  - check range
182	     *  - check merge with next area
183	     *  - check merge with previous area
184	     */
185	    if ((char *)ptr <= (char *)mn) {
186		/*
187		 * range check
188		 */
189		if ((char *)ptr + bytes > (char *)mn) {
190		    panic("zfree(%p,%ju): corrupt memlist1", ptr,
191			(uintmax_t)bytes);
192		}
193
194		/*
195		 * merge against next area or create independant area
196		 */
197
198		if ((char *)ptr + bytes == (char *)mn) {
199		    ((MemNode *)ptr)->mr_Next = mn->mr_Next;
200		    ((MemNode *)ptr)->mr_Bytes= bytes + mn->mr_Bytes;
201		} else {
202		    ((MemNode *)ptr)->mr_Next = mn;
203		    ((MemNode *)ptr)->mr_Bytes= bytes;
204		}
205		*pmn = mn = (MemNode *)ptr;
206
207		/*
208		 * merge against previous area (if there is a previous
209		 * area).
210		 */
211
212		if (pmn != &mp->mp_First) {
213		    if ((char*)pmn + ((MemNode*)pmn)->mr_Bytes == (char*)ptr) {
214			((MemNode *)pmn)->mr_Next = mn->mr_Next;
215			((MemNode *)pmn)->mr_Bytes += mn->mr_Bytes;
216			mn = (MemNode *)pmn;
217		    }
218		}
219		return;
220		/* NOT REACHED */
221	    }
222	    if ((char *)ptr < (char *)mn + mn->mr_Bytes) {
223		panic("zfree(%p,%ju): corrupt memlist2", ptr,
224		    (uintmax_t)bytes);
225	    }
226	}
227	/*
228	 * We are beyond the last MemNode, append new MemNode.  Merge against
229	 * previous area if possible.
230	 */
231	if (pmn == &mp->mp_First ||
232	    (char *)pmn + ((MemNode *)pmn)->mr_Bytes != (char *)ptr
233	) {
234	    ((MemNode *)ptr)->mr_Next = NULL;
235	    ((MemNode *)ptr)->mr_Bytes = bytes;
236	    *pmn = (MemNode *)ptr;
237	    mn = (MemNode *)ptr;
238	} else {
239	    ((MemNode *)pmn)->mr_Bytes += bytes;
240	    mn = (MemNode *)pmn;
241	}
242    }
243}
244
245/*
246 * zextendPool() - extend memory pool to cover additional space.
247 *
248 *		   Note: the added memory starts out as allocated, you
249 *		   must free it to make it available to the memory subsystem.
250 *
251 *		   Note: mp_Size may not reflect (mp_End - mp_Base) range
252 *		   due to other parts of the system doing their own sbrk()
253 *		   calls.
254 */
255
256void
257zextendPool(MemPool *mp, void *base, uintptr_t bytes)
258{
259    if (mp->mp_Size == 0) {
260	mp->mp_Base = base;
261	mp->mp_Used = bytes;
262	mp->mp_End = (char *)base + bytes;
263	mp->mp_Size = bytes;
264    } else {
265	void *pend = (char *)mp->mp_Base + mp->mp_Size;
266
267	if (base < mp->mp_Base) {
268	    mp->mp_Size += (char *)mp->mp_Base - (char *)base;
269	    mp->mp_Used += (char *)mp->mp_Base - (char *)base;
270	    mp->mp_Base = base;
271	}
272	base = (char *)base + bytes;
273	if (base > pend) {
274	    mp->mp_Size += (char *)base - (char *)pend;
275	    mp->mp_Used += (char *)base - (char *)pend;
276	    mp->mp_End = (char *)base;
277	}
278    }
279}
280
281#ifdef ZALLOCDEBUG
282
283void
284zallocstats(MemPool *mp)
285{
286    int abytes = 0;
287    int hbytes = 0;
288    int fcount = 0;
289    MemNode *mn;
290
291    printf("%d bytes reserved", (int) mp->mp_Size);
292
293    mn = mp->mp_First;
294
295    if ((void *)mn != (void *)mp->mp_Base) {
296	abytes += (char *)mn - (char *)mp->mp_Base;
297    }
298
299    while (mn) {
300	if ((char *)mn + mn->mr_Bytes != mp->mp_End) {
301	    hbytes += mn->mr_Bytes;
302	    ++fcount;
303	}
304	if (mn->mr_Next)
305	    abytes += (char *)mn->mr_Next - ((char *)mn + mn->mr_Bytes);
306	mn = mn->mr_Next;
307    }
308    printf(" %d bytes allocated\n%d fragments (%d bytes fragmented)\n",
309	abytes,
310	fcount,
311	hbytes
312    );
313}
314
315#endif
316
317