1199767f8SToomas Soome /*
2f5700834SToomas Soome * This module derived from code donated to the FreeBSD Project by
3199767f8SToomas Soome * Matthew Dillon <dillon@backplane.com>
4199767f8SToomas Soome *
5199767f8SToomas Soome * Copyright (c) 1998 The FreeBSD Project
6199767f8SToomas Soome * All rights reserved.
7199767f8SToomas Soome *
8199767f8SToomas Soome * Redistribution and use in source and binary forms, with or without
9199767f8SToomas Soome * modification, are permitted provided that the following conditions
10199767f8SToomas Soome * are met:
11199767f8SToomas Soome * 1. Redistributions of source code must retain the above copyright
12199767f8SToomas Soome * notice, this list of conditions and the following disclaimer.
13199767f8SToomas Soome * 2. Redistributions in binary form must reproduce the above copyright
14199767f8SToomas Soome * notice, this list of conditions and the following disclaimer in the
15199767f8SToomas Soome * documentation and/or other materials provided with the distribution.
16199767f8SToomas Soome *
17199767f8SToomas Soome * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18199767f8SToomas Soome * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19199767f8SToomas Soome * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20199767f8SToomas Soome * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21199767f8SToomas Soome * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22199767f8SToomas Soome * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23199767f8SToomas Soome * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24199767f8SToomas Soome * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25199767f8SToomas Soome * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26199767f8SToomas Soome * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27199767f8SToomas Soome * SUCH DAMAGE.
28199767f8SToomas Soome */
29199767f8SToomas Soome
30199767f8SToomas Soome #include <sys/cdefs.h>
31081aa5f6SToomas Soome #include <sys/param.h>
32199767f8SToomas Soome
33199767f8SToomas Soome /*
34f5700834SToomas Soome * LIB/MEMORY/ZALLOC.C - self contained low-overhead memory pool/allocation
35199767f8SToomas Soome * subsystem
36199767f8SToomas Soome *
37f5700834SToomas Soome * This subsystem implements memory pools and memory allocation
38199767f8SToomas Soome * routines.
39199767f8SToomas Soome *
40199767f8SToomas Soome * Pools are managed via a linked list of 'free' areas. Allocating
41199767f8SToomas Soome * memory creates holes in the freelist, freeing memory fills them.
42199767f8SToomas Soome * Since the freelist consists only of free memory areas, it is possible
43199767f8SToomas Soome * to allocate the entire pool without incuring any structural overhead.
44199767f8SToomas Soome *
45199767f8SToomas Soome * The system works best when allocating similarly-sized chunks of
46f5700834SToomas Soome * memory. Care must be taken to avoid fragmentation when
47199767f8SToomas Soome * allocating/deallocating dissimilar chunks.
48199767f8SToomas Soome *
49199767f8SToomas Soome * When a memory pool is first allocated, the entire pool is marked as
50199767f8SToomas Soome * allocated. This is done mainly because we do not want to modify any
51199767f8SToomas Soome * portion of a pool's data area until we are given permission. The
52199767f8SToomas Soome * caller must explicitly deallocate portions of the pool to make them
53199767f8SToomas Soome * available.
54199767f8SToomas Soome *
55199767f8SToomas Soome * z[n]xalloc() works like z[n]alloc() but the allocation is made from
56f5700834SToomas Soome * within the specified address range. If the segment could not be
57199767f8SToomas Soome * allocated, NULL is returned. WARNING! The address range will be
58199767f8SToomas Soome * aligned to an 8 or 16 byte boundry depending on the cpu so if you
59199767f8SToomas Soome * give an unaligned address range, unexpected results may occur.
60199767f8SToomas Soome *
61199767f8SToomas Soome * If a standard allocation fails, the reclaim function will be called
62199767f8SToomas Soome * to recover some space. This usually causes other portions of the
63199767f8SToomas Soome * same pool to be released. Memory allocations at this low level
64199767f8SToomas Soome * should not block but you can do that too in your reclaim function
65199767f8SToomas Soome * if you want. Reclaim does not function when z[n]xalloc() is used,
66199767f8SToomas Soome * only for z[n]alloc().
67199767f8SToomas Soome *
68199767f8SToomas Soome * Allocation and frees of 0 bytes are valid operations.
69199767f8SToomas Soome */
70199767f8SToomas Soome
71199767f8SToomas Soome #include "zalloc_defs.h"
72199767f8SToomas Soome
73199767f8SToomas Soome /*
74199767f8SToomas Soome * Objects in the pool must be aligned to at least the size of struct MemNode.
75199767f8SToomas Soome * They must also be aligned to MALLOCALIGN, which should normally be larger
76199767f8SToomas Soome * than the struct, so assert that to be so at compile time.
77199767f8SToomas Soome */
78f5700834SToomas Soome typedef char assert_align[(sizeof (struct MemNode) <= MALLOCALIGN) ? 1 : -1];
79199767f8SToomas Soome
80199767f8SToomas Soome #define MEMNODE_SIZE_MASK MALLOCALIGN_MASK
81199767f8SToomas Soome
82199767f8SToomas Soome /*
83199767f8SToomas Soome * znalloc() - allocate memory (without zeroing) from pool. Call reclaim
84199767f8SToomas Soome * and retry if appropriate, return NULL if unable to allocate
85199767f8SToomas Soome * memory.
86199767f8SToomas Soome */
87199767f8SToomas Soome
88199767f8SToomas Soome void *
znalloc(MemPool * mp,uintptr_t bytes,size_t align)89081aa5f6SToomas Soome znalloc(MemPool *mp, uintptr_t bytes, size_t align)
90199767f8SToomas Soome {
91199767f8SToomas Soome MemNode **pmn;
92199767f8SToomas Soome MemNode *mn;
93199767f8SToomas Soome
94f5700834SToomas Soome /*
95f5700834SToomas Soome * align according to pool object size (can be 0). This is
96f5700834SToomas Soome * inclusive of the MEMNODE_SIZE_MASK minimum alignment.
97f5700834SToomas Soome *
98f5700834SToomas Soome */
99f5700834SToomas Soome bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK;
100f5700834SToomas Soome
101f5700834SToomas Soome if (bytes == 0)
102f5700834SToomas Soome return ((void *)-1);
103f5700834SToomas Soome
104f5700834SToomas Soome /*
105f5700834SToomas Soome * locate freelist entry big enough to hold the object. If all objects
106f5700834SToomas Soome * are the same size, this is a constant-time function.
107f5700834SToomas Soome */
108199767f8SToomas Soome
109f5700834SToomas Soome if (bytes > mp->mp_Size - mp->mp_Used)
110f5700834SToomas Soome return (NULL);
111199767f8SToomas Soome
112f5700834SToomas Soome for (pmn = &mp->mp_First; (mn = *pmn) != NULL; pmn = &mn->mr_Next) {
113199767f8SToomas Soome char *ptr = (char *)mn;
114081aa5f6SToomas Soome uintptr_t dptr;
115081aa5f6SToomas Soome char *aligned;
116081aa5f6SToomas Soome size_t extra;
117199767f8SToomas Soome
118081aa5f6SToomas Soome dptr = (uintptr_t)(ptr + MALLOCALIGN); /* pointer to data */
119081aa5f6SToomas Soome aligned = (char *)(roundup2(dptr, align) - MALLOCALIGN);
120081aa5f6SToomas Soome extra = aligned - ptr;
121081aa5f6SToomas Soome
122081aa5f6SToomas Soome if (bytes + extra > mn->mr_Bytes)
123f5700834SToomas Soome continue;
124f5700834SToomas Soome
125081aa5f6SToomas Soome /*
126081aa5f6SToomas Soome * Cut extra from head and create new memory node from
127081aa5f6SToomas Soome * remainder.
128081aa5f6SToomas Soome */
129081aa5f6SToomas Soome
130081aa5f6SToomas Soome if (extra != 0) {
131081aa5f6SToomas Soome MemNode *new;
132081aa5f6SToomas Soome
133081aa5f6SToomas Soome new = (MemNode *)aligned;
134081aa5f6SToomas Soome new->mr_Next = mn->mr_Next;
135081aa5f6SToomas Soome new->mr_Bytes = mn->mr_Bytes - extra;
136081aa5f6SToomas Soome
137081aa5f6SToomas Soome /* And update current memory node */
138081aa5f6SToomas Soome mn->mr_Bytes = extra;
139081aa5f6SToomas Soome mn->mr_Next = new;
140081aa5f6SToomas Soome /* In next iteration, we will get our aligned address */
141081aa5f6SToomas Soome continue;
142081aa5f6SToomas Soome }
143081aa5f6SToomas Soome
144f5700834SToomas Soome /*
145f5700834SToomas Soome * Cut a chunk of memory out of the beginning of this
146f5700834SToomas Soome * block and fixup the link appropriately.
147f5700834SToomas Soome */
148081aa5f6SToomas Soome
149199767f8SToomas Soome if (mn->mr_Bytes == bytes) {
150f5700834SToomas Soome *pmn = mn->mr_Next;
151199767f8SToomas Soome } else {
152f5700834SToomas Soome mn = (MemNode *)((char *)mn + bytes);
153f5700834SToomas Soome mn->mr_Next = ((MemNode *)ptr)->mr_Next;
154f5700834SToomas Soome mn->mr_Bytes = ((MemNode *)ptr)->mr_Bytes - bytes;
155f5700834SToomas Soome *pmn = mn;
156199767f8SToomas Soome }
157199767f8SToomas Soome mp->mp_Used += bytes;
158f5700834SToomas Soome return (ptr);
159199767f8SToomas Soome }
160199767f8SToomas Soome
161f5700834SToomas Soome /*
162f5700834SToomas Soome * Memory pool is full, return NULL.
163f5700834SToomas Soome */
164199767f8SToomas Soome
165f5700834SToomas Soome return (NULL);
166199767f8SToomas Soome }
167199767f8SToomas Soome
168199767f8SToomas Soome /*
169199767f8SToomas Soome * zfree() - free previously allocated memory
170199767f8SToomas Soome */
171199767f8SToomas Soome
172199767f8SToomas Soome void
zfree(MemPool * mp,void * ptr,uintptr_t bytes)173199767f8SToomas Soome zfree(MemPool *mp, void *ptr, uintptr_t bytes)
174199767f8SToomas Soome {
175f5700834SToomas Soome MemNode **pmn;
176f5700834SToomas Soome MemNode *mn;
177199767f8SToomas Soome
178f5700834SToomas Soome /*
179f5700834SToomas Soome * align according to pool object size (can be 0). This is
180f5700834SToomas Soome * inclusive of the MEMNODE_SIZE_MASK minimum alignment.
181f5700834SToomas Soome */
182f5700834SToomas Soome bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK;
183199767f8SToomas Soome
184f5700834SToomas Soome if (bytes == 0)
185f5700834SToomas Soome return;
186199767f8SToomas Soome
187f5700834SToomas Soome /*
188f5700834SToomas Soome * panic if illegal pointer
189f5700834SToomas Soome */
190199767f8SToomas Soome
191f5700834SToomas Soome if ((char *)ptr < (char *)mp->mp_Base ||
192f5700834SToomas Soome (char *)ptr + bytes > (char *)mp->mp_End ||
193f5700834SToomas Soome ((uintptr_t)ptr & MEMNODE_SIZE_MASK) != 0)
194f5700834SToomas Soome panic("zfree(%p,%ju): wild pointer", ptr, (uintmax_t)bytes);
195199767f8SToomas Soome
196f5700834SToomas Soome /*
197f5700834SToomas Soome * free the segment
198f5700834SToomas Soome */
199199767f8SToomas Soome mp->mp_Used -= bytes;
200199767f8SToomas Soome
201199767f8SToomas Soome for (pmn = &mp->mp_First; (mn = *pmn) != NULL; pmn = &mn->mr_Next) {
202199767f8SToomas Soome /*
203f5700834SToomas Soome * If area between last node and current node
204f5700834SToomas Soome * - check range
205f5700834SToomas Soome * - check merge with next area
206f5700834SToomas Soome * - check merge with previous area
207199767f8SToomas Soome */
208f5700834SToomas Soome if ((char *)ptr <= (char *)mn) {
209f5700834SToomas Soome /*
210f5700834SToomas Soome * range check
211f5700834SToomas Soome */
212f5700834SToomas Soome if ((char *)ptr + bytes > (char *)mn) {
213f5700834SToomas Soome panic("zfree(%p,%ju): corrupt memlist1", ptr,
214f5700834SToomas Soome (uintmax_t)bytes);
215f5700834SToomas Soome }
216f5700834SToomas Soome
217f5700834SToomas Soome /*
218f5700834SToomas Soome * merge against next area or create independant area
219f5700834SToomas Soome */
220f5700834SToomas Soome
221f5700834SToomas Soome if ((char *)ptr + bytes == (char *)mn) {
222f5700834SToomas Soome ((MemNode *)ptr)->mr_Next = mn->mr_Next;
223f5700834SToomas Soome ((MemNode *)ptr)->mr_Bytes =
224f5700834SToomas Soome bytes + mn->mr_Bytes;
225f5700834SToomas Soome } else {
226f5700834SToomas Soome ((MemNode *)ptr)->mr_Next = mn;
227f5700834SToomas Soome ((MemNode *)ptr)->mr_Bytes = bytes;
228f5700834SToomas Soome }
229f5700834SToomas Soome *pmn = mn = (MemNode *)ptr;
230f5700834SToomas Soome
231f5700834SToomas Soome /*
232f5700834SToomas Soome * merge against previous area (if there is a previous
233f5700834SToomas Soome * area).
234f5700834SToomas Soome */
235f5700834SToomas Soome
236f5700834SToomas Soome if (pmn != &mp->mp_First) {
237f5700834SToomas Soome if ((char *)pmn + ((MemNode*)pmn)->mr_Bytes ==
238f5700834SToomas Soome (char *)ptr) {
239f5700834SToomas Soome ((MemNode *)pmn)->mr_Next = mn->mr_Next;
240f5700834SToomas Soome ((MemNode *)pmn)->mr_Bytes +=
241f5700834SToomas Soome mn->mr_Bytes;
242f5700834SToomas Soome mn = (MemNode *)pmn;
243f5700834SToomas Soome }
244f5700834SToomas Soome }
245f5700834SToomas Soome return;
246199767f8SToomas Soome }
247f5700834SToomas Soome if ((char *)ptr < (char *)mn + mn->mr_Bytes) {
248f5700834SToomas Soome panic("zfree(%p,%ju): corrupt memlist2", ptr,
249f5700834SToomas Soome (uintmax_t)bytes);
250199767f8SToomas Soome }
251199767f8SToomas Soome }
252199767f8SToomas Soome /*
253199767f8SToomas Soome * We are beyond the last MemNode, append new MemNode. Merge against
254199767f8SToomas Soome * previous area if possible.
255199767f8SToomas Soome */
256f5700834SToomas Soome if (pmn == &mp->mp_First ||
257f5700834SToomas Soome (char *)pmn + ((MemNode *)pmn)->mr_Bytes != (char *)ptr) {
258f5700834SToomas Soome ((MemNode *)ptr)->mr_Next = NULL;
259f5700834SToomas Soome ((MemNode *)ptr)->mr_Bytes = bytes;
260f5700834SToomas Soome *pmn = (MemNode *)ptr;
261f5700834SToomas Soome mn = (MemNode *)ptr;
262199767f8SToomas Soome } else {
263f5700834SToomas Soome ((MemNode *)pmn)->mr_Bytes += bytes;
264f5700834SToomas Soome mn = (MemNode *)pmn;
265199767f8SToomas Soome }
266199767f8SToomas Soome }
267199767f8SToomas Soome
268199767f8SToomas Soome /*
269199767f8SToomas Soome * zextendPool() - extend memory pool to cover additional space.
270199767f8SToomas Soome *
271199767f8SToomas Soome * Note: the added memory starts out as allocated, you
272199767f8SToomas Soome * must free it to make it available to the memory subsystem.
273199767f8SToomas Soome *
274199767f8SToomas Soome * Note: mp_Size may not reflect (mp_End - mp_Base) range
275199767f8SToomas Soome * due to other parts of the system doing their own sbrk()
276199767f8SToomas Soome * calls.
277199767f8SToomas Soome */
278199767f8SToomas Soome
279199767f8SToomas Soome void
zextendPool(MemPool * mp,void * base,uintptr_t bytes)280199767f8SToomas Soome zextendPool(MemPool *mp, void *base, uintptr_t bytes)
281199767f8SToomas Soome {
282f5700834SToomas Soome if (mp->mp_Size == 0) {
283f5700834SToomas Soome mp->mp_Base = base;
284f5700834SToomas Soome mp->mp_Used = bytes;
285f5700834SToomas Soome mp->mp_End = (char *)base + bytes;
286f5700834SToomas Soome mp->mp_Size = bytes;
287f5700834SToomas Soome } else {
288f5700834SToomas Soome void *pend = (char *)mp->mp_Base + mp->mp_Size;
289f5700834SToomas Soome
290f5700834SToomas Soome if (base < mp->mp_Base) {
291f5700834SToomas Soome mp->mp_Size += (char *)mp->mp_Base - (char *)base;
292f5700834SToomas Soome mp->mp_Used += (char *)mp->mp_Base - (char *)base;
293f5700834SToomas Soome mp->mp_Base = base;
294f5700834SToomas Soome }
295f5700834SToomas Soome base = (char *)base + bytes;
296f5700834SToomas Soome if (base > pend) {
297f5700834SToomas Soome mp->mp_Size += (char *)base - (char *)pend;
298f5700834SToomas Soome mp->mp_Used += (char *)base - (char *)pend;
299f5700834SToomas Soome mp->mp_End = (char *)base;
300f5700834SToomas Soome }
301199767f8SToomas Soome }
302199767f8SToomas Soome }
303199767f8SToomas Soome
304199767f8SToomas Soome #ifdef ZALLOCDEBUG
305199767f8SToomas Soome
306199767f8SToomas Soome void
zallocstats(MemPool * mp)307199767f8SToomas Soome zallocstats(MemPool *mp)
308199767f8SToomas Soome {
309f5700834SToomas Soome int abytes = 0;
310f5700834SToomas Soome int hbytes = 0;
311f5700834SToomas Soome int fcount = 0;
312f5700834SToomas Soome MemNode *mn;
313199767f8SToomas Soome
314f5700834SToomas Soome printf("%d bytes reserved", (int)mp->mp_Size);
315199767f8SToomas Soome
316f5700834SToomas Soome mn = mp->mp_First;
317199767f8SToomas Soome
318f5700834SToomas Soome if ((void *)mn != (void *)mp->mp_Base) {
319f5700834SToomas Soome abytes += (char *)mn - (char *)mp->mp_Base;
320f5700834SToomas Soome }
321199767f8SToomas Soome
322f5700834SToomas Soome while (mn != NULL) {
323f5700834SToomas Soome if ((char *)mn + mn->mr_Bytes != mp->mp_End) {
324f5700834SToomas Soome hbytes += mn->mr_Bytes;
325f5700834SToomas Soome ++fcount;
326f5700834SToomas Soome }
327f5700834SToomas Soome if (mn->mr_Next != NULL) {
328f5700834SToomas Soome abytes += (char *)mn->mr_Next -
329f5700834SToomas Soome ((char *)mn + mn->mr_Bytes);
330f5700834SToomas Soome }
331f5700834SToomas Soome mn = mn->mr_Next;
332199767f8SToomas Soome }
333f5700834SToomas Soome printf(" %d bytes allocated\n%d fragments (%d bytes fragmented)\n",
334f5700834SToomas Soome abytes, fcount, hbytes);
335199767f8SToomas Soome }
336199767f8SToomas Soome
337199767f8SToomas Soome #endif
338