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