xref: /minix3/sys/lib/libsa/alloc.c (revision 58a2b0008e28f606a7f7f5faaeaba4faac57a1ea)
1*58a2b000SEvgeniy Ivanov /*	$NetBSD: alloc.c,v 1.26 2011/07/30 03:43:20 jakllsch Exp $	*/
2*58a2b000SEvgeniy Ivanov 
3*58a2b000SEvgeniy Ivanov /*
4*58a2b000SEvgeniy Ivanov  * Copyright (c) 1993
5*58a2b000SEvgeniy Ivanov  *	The Regents of the University of California.  All rights reserved.
6*58a2b000SEvgeniy Ivanov  *
7*58a2b000SEvgeniy Ivanov  * This code is derived from software contributed to Berkeley by
8*58a2b000SEvgeniy Ivanov  * The Mach Operating System project at Carnegie-Mellon University.
9*58a2b000SEvgeniy Ivanov  *
10*58a2b000SEvgeniy Ivanov  * Redistribution and use in source and binary forms, with or without
11*58a2b000SEvgeniy Ivanov  * modification, are permitted provided that the following conditions
12*58a2b000SEvgeniy Ivanov  * are met:
13*58a2b000SEvgeniy Ivanov  * 1. Redistributions of source code must retain the above copyright
14*58a2b000SEvgeniy Ivanov  *    notice, this list of conditions and the following disclaimer.
15*58a2b000SEvgeniy Ivanov  * 2. Redistributions in binary form must reproduce the above copyright
16*58a2b000SEvgeniy Ivanov  *    notice, this list of conditions and the following disclaimer in the
17*58a2b000SEvgeniy Ivanov  *    documentation and/or other materials provided with the distribution.
18*58a2b000SEvgeniy Ivanov  * 3. Neither the name of the University nor the names of its contributors
19*58a2b000SEvgeniy Ivanov  *    may be used to endorse or promote products derived from this software
20*58a2b000SEvgeniy Ivanov  *    without specific prior written permission.
21*58a2b000SEvgeniy Ivanov  *
22*58a2b000SEvgeniy Ivanov  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23*58a2b000SEvgeniy Ivanov  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24*58a2b000SEvgeniy Ivanov  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25*58a2b000SEvgeniy Ivanov  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26*58a2b000SEvgeniy Ivanov  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27*58a2b000SEvgeniy Ivanov  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28*58a2b000SEvgeniy Ivanov  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29*58a2b000SEvgeniy Ivanov  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30*58a2b000SEvgeniy Ivanov  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31*58a2b000SEvgeniy Ivanov  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32*58a2b000SEvgeniy Ivanov  * SUCH DAMAGE.
33*58a2b000SEvgeniy Ivanov  *
34*58a2b000SEvgeniy Ivanov  *	@(#)alloc.c	8.1 (Berkeley) 6/11/93
35*58a2b000SEvgeniy Ivanov  *
36*58a2b000SEvgeniy Ivanov  *
37*58a2b000SEvgeniy Ivanov  * Copyright (c) 1997 Christopher G. Demetriou.  All rights reserved.
38*58a2b000SEvgeniy Ivanov  * Copyright (c) 1996
39*58a2b000SEvgeniy Ivanov  *	Matthias Drochner.  All rights reserved.
40*58a2b000SEvgeniy Ivanov  *
41*58a2b000SEvgeniy Ivanov  * This code is derived from software contributed to Berkeley by
42*58a2b000SEvgeniy Ivanov  * The Mach Operating System project at Carnegie-Mellon University.
43*58a2b000SEvgeniy Ivanov  *
44*58a2b000SEvgeniy Ivanov  * Redistribution and use in source and binary forms, with or without
45*58a2b000SEvgeniy Ivanov  * modification, are permitted provided that the following conditions
46*58a2b000SEvgeniy Ivanov  * are met:
47*58a2b000SEvgeniy Ivanov  * 1. Redistributions of source code must retain the above copyright
48*58a2b000SEvgeniy Ivanov  *    notice, this list of conditions and the following disclaimer.
49*58a2b000SEvgeniy Ivanov  * 2. Redistributions in binary form must reproduce the above copyright
50*58a2b000SEvgeniy Ivanov  *    notice, this list of conditions and the following disclaimer in the
51*58a2b000SEvgeniy Ivanov  *    documentation and/or other materials provided with the distribution.
52*58a2b000SEvgeniy Ivanov  * 3. All advertising materials mentioning features or use of this software
53*58a2b000SEvgeniy Ivanov  *    must display the following acknowledgement:
54*58a2b000SEvgeniy Ivanov  *	This product includes software developed by the University of
55*58a2b000SEvgeniy Ivanov  *	California, Berkeley and its contributors.
56*58a2b000SEvgeniy Ivanov  * 4. Neither the name of the University nor the names of its contributors
57*58a2b000SEvgeniy Ivanov  *    may be used to endorse or promote products derived from this software
58*58a2b000SEvgeniy Ivanov  *    without specific prior written permission.
59*58a2b000SEvgeniy Ivanov  *
60*58a2b000SEvgeniy Ivanov  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
61*58a2b000SEvgeniy Ivanov  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
62*58a2b000SEvgeniy Ivanov  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
63*58a2b000SEvgeniy Ivanov  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
64*58a2b000SEvgeniy Ivanov  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
65*58a2b000SEvgeniy Ivanov  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
66*58a2b000SEvgeniy Ivanov  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
67*58a2b000SEvgeniy Ivanov  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
68*58a2b000SEvgeniy Ivanov  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
69*58a2b000SEvgeniy Ivanov  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
70*58a2b000SEvgeniy Ivanov  * SUCH DAMAGE.
71*58a2b000SEvgeniy Ivanov  *
72*58a2b000SEvgeniy Ivanov  *	@(#)alloc.c	8.1 (Berkeley) 6/11/93
73*58a2b000SEvgeniy Ivanov  *
74*58a2b000SEvgeniy Ivanov  *
75*58a2b000SEvgeniy Ivanov  * Copyright (c) 1989, 1990, 1991 Carnegie Mellon University
76*58a2b000SEvgeniy Ivanov  * All Rights Reserved.
77*58a2b000SEvgeniy Ivanov  *
78*58a2b000SEvgeniy Ivanov  * Author: Alessandro Forin
79*58a2b000SEvgeniy Ivanov  *
80*58a2b000SEvgeniy Ivanov  * Permission to use, copy, modify and distribute this software and its
81*58a2b000SEvgeniy Ivanov  * documentation is hereby granted, provided that both the copyright
82*58a2b000SEvgeniy Ivanov  * notice and this permission notice appear in all copies of the
83*58a2b000SEvgeniy Ivanov  * software, derivative works or modified versions, and any portions
84*58a2b000SEvgeniy Ivanov  * thereof, and that both notices appear in supporting documentation.
85*58a2b000SEvgeniy Ivanov  *
86*58a2b000SEvgeniy Ivanov  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
87*58a2b000SEvgeniy Ivanov  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
88*58a2b000SEvgeniy Ivanov  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
89*58a2b000SEvgeniy Ivanov  *
90*58a2b000SEvgeniy Ivanov  * Carnegie Mellon requests users of this software to return to
91*58a2b000SEvgeniy Ivanov  *
92*58a2b000SEvgeniy Ivanov  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
93*58a2b000SEvgeniy Ivanov  *  School of Computer Science
94*58a2b000SEvgeniy Ivanov  *  Carnegie Mellon University
95*58a2b000SEvgeniy Ivanov  *  Pittsburgh PA 15213-3890
96*58a2b000SEvgeniy Ivanov  *
97*58a2b000SEvgeniy Ivanov  * any improvements or extensions that they make and grant Carnegie the
98*58a2b000SEvgeniy Ivanov  * rights to redistribute these changes.
99*58a2b000SEvgeniy Ivanov  */
100*58a2b000SEvgeniy Ivanov 
101*58a2b000SEvgeniy Ivanov /*
102*58a2b000SEvgeniy Ivanov  * Dynamic memory allocator.
103*58a2b000SEvgeniy Ivanov  *
104*58a2b000SEvgeniy Ivanov  * Compile options:
105*58a2b000SEvgeniy Ivanov  *
106*58a2b000SEvgeniy Ivanov  *	ALLOC_TRACE	enable tracing of allocations/deallocations
107*58a2b000SEvgeniy Ivanov 
108*58a2b000SEvgeniy Ivanov  *	ALLOC_FIRST_FIT	use a first-fit allocation algorithm, rather than
109*58a2b000SEvgeniy Ivanov  *			the default best-fit algorithm.
110*58a2b000SEvgeniy Ivanov  *
111*58a2b000SEvgeniy Ivanov  *	HEAP_LIMIT	heap limit address (defaults to "no limit").
112*58a2b000SEvgeniy Ivanov  *
113*58a2b000SEvgeniy Ivanov  *	HEAP_START	start address of heap (defaults to '&end').
114*58a2b000SEvgeniy Ivanov  *
115*58a2b000SEvgeniy Ivanov  *	DEBUG		enable debugging sanity checks.
116*58a2b000SEvgeniy Ivanov  */
117*58a2b000SEvgeniy Ivanov 
118*58a2b000SEvgeniy Ivanov #include <sys/param.h>
119*58a2b000SEvgeniy Ivanov #include "stand.h"
120*58a2b000SEvgeniy Ivanov 
121*58a2b000SEvgeniy Ivanov /*
122*58a2b000SEvgeniy Ivanov  * Each block actually has ALIGN(unsigned int) + ALIGN(size) bytes allocated
123*58a2b000SEvgeniy Ivanov  * to it, as follows:
124*58a2b000SEvgeniy Ivanov  *
125*58a2b000SEvgeniy Ivanov  * 0 ... (sizeof(unsigned int) - 1)
126*58a2b000SEvgeniy Ivanov  *	allocated or unallocated: holds size of user-data part of block.
127*58a2b000SEvgeniy Ivanov  *
128*58a2b000SEvgeniy Ivanov  * sizeof(unsigned int) ... (ALIGN(sizeof(unsigned int)) - 1)
129*58a2b000SEvgeniy Ivanov  *	allocated: unused
130*58a2b000SEvgeniy Ivanov  *	unallocated: depends on packing of struct fl
131*58a2b000SEvgeniy Ivanov  *
132*58a2b000SEvgeniy Ivanov  * ALIGN(sizeof(unsigned int)) ...
133*58a2b000SEvgeniy Ivanov  *     (ALIGN(sizeof(unsigned int)) + ALIGN(data size) - 1)
134*58a2b000SEvgeniy Ivanov  *	allocated: user data
135*58a2b000SEvgeniy Ivanov  *	unallocated: depends on packing of struct fl
136*58a2b000SEvgeniy Ivanov  *
137*58a2b000SEvgeniy Ivanov  * 'next' is only used when the block is unallocated (i.e. on the free list).
138*58a2b000SEvgeniy Ivanov  * However, note that ALIGN(sizeof(unsigned int)) + ALIGN(data size) must
139*58a2b000SEvgeniy Ivanov  * be at least 'sizeof(struct fl)', so that blocks can be used as structures
140*58a2b000SEvgeniy Ivanov  * when on the free list.
141*58a2b000SEvgeniy Ivanov  */
142*58a2b000SEvgeniy Ivanov struct fl {
143*58a2b000SEvgeniy Ivanov 	unsigned int	size;
144*58a2b000SEvgeniy Ivanov 	struct fl	*next;
145*58a2b000SEvgeniy Ivanov } *freelist;
146*58a2b000SEvgeniy Ivanov 
147*58a2b000SEvgeniy Ivanov #ifdef HEAP_VARIABLE
148*58a2b000SEvgeniy Ivanov static char *top, *heapstart, *heaplimit;
149*58a2b000SEvgeniy Ivanov void
setheap(void * start,void * limit)150*58a2b000SEvgeniy Ivanov setheap(void *start, void *limit)
151*58a2b000SEvgeniy Ivanov {
152*58a2b000SEvgeniy Ivanov 	heapstart = top = start;
153*58a2b000SEvgeniy Ivanov 	heaplimit = limit;
154*58a2b000SEvgeniy Ivanov }
155*58a2b000SEvgeniy Ivanov #define HEAP_START heapstart
156*58a2b000SEvgeniy Ivanov #define HEAP_LIMIT heaplimit
157*58a2b000SEvgeniy Ivanov #else /* !HEAP_VARIABLE */
158*58a2b000SEvgeniy Ivanov #ifndef HEAP_START
159*58a2b000SEvgeniy Ivanov extern char end[];
160*58a2b000SEvgeniy Ivanov #define HEAP_START end
161*58a2b000SEvgeniy Ivanov #endif
162*58a2b000SEvgeniy Ivanov static char *top = (char *)HEAP_START;
163*58a2b000SEvgeniy Ivanov #endif /* HEAP_VARIABLE */
164*58a2b000SEvgeniy Ivanov 
165*58a2b000SEvgeniy Ivanov __compactcall void *
alloc(size_t size)166*58a2b000SEvgeniy Ivanov alloc(size_t size)
167*58a2b000SEvgeniy Ivanov {
168*58a2b000SEvgeniy Ivanov 	struct fl **f = &freelist, **bestf = NULL;
169*58a2b000SEvgeniy Ivanov #ifndef ALLOC_FIRST_FIT
170*58a2b000SEvgeniy Ivanov 	unsigned int bestsize = 0xffffffff;	/* greater than any real size */
171*58a2b000SEvgeniy Ivanov #endif
172*58a2b000SEvgeniy Ivanov 	char *help;
173*58a2b000SEvgeniy Ivanov 	int failed;
174*58a2b000SEvgeniy Ivanov 
175*58a2b000SEvgeniy Ivanov #ifdef ALLOC_TRACE
176*58a2b000SEvgeniy Ivanov 	printf("alloc(%zu)", size);
177*58a2b000SEvgeniy Ivanov #endif
178*58a2b000SEvgeniy Ivanov 
179*58a2b000SEvgeniy Ivanov #ifdef ALLOC_FIRST_FIT
180*58a2b000SEvgeniy Ivanov 	while (*f != (struct fl *)0 && (size_t)(*f)->size < size)
181*58a2b000SEvgeniy Ivanov 		f = &((*f)->next);
182*58a2b000SEvgeniy Ivanov 	bestf = f;
183*58a2b000SEvgeniy Ivanov 	failed = (*bestf == (struct fl *)0);
184*58a2b000SEvgeniy Ivanov #else
185*58a2b000SEvgeniy Ivanov 	/* scan freelist */
186*58a2b000SEvgeniy Ivanov 	while (*f) {
187*58a2b000SEvgeniy Ivanov 		if ((size_t)(*f)->size >= size) {
188*58a2b000SEvgeniy Ivanov 			if ((size_t)(*f)->size == size) /* exact match */
189*58a2b000SEvgeniy Ivanov 				goto found;
190*58a2b000SEvgeniy Ivanov 
191*58a2b000SEvgeniy Ivanov 			if ((*f)->size < bestsize) {
192*58a2b000SEvgeniy Ivanov 				/* keep best fit */
193*58a2b000SEvgeniy Ivanov 				bestf = f;
194*58a2b000SEvgeniy Ivanov 				bestsize = (*f)->size;
195*58a2b000SEvgeniy Ivanov 			}
196*58a2b000SEvgeniy Ivanov 		}
197*58a2b000SEvgeniy Ivanov 		f = &((*f)->next);
198*58a2b000SEvgeniy Ivanov 	}
199*58a2b000SEvgeniy Ivanov 
200*58a2b000SEvgeniy Ivanov 	/* no match in freelist if bestsize unchanged */
201*58a2b000SEvgeniy Ivanov 	failed = (bestsize == 0xffffffff);
202*58a2b000SEvgeniy Ivanov #endif
203*58a2b000SEvgeniy Ivanov 
204*58a2b000SEvgeniy Ivanov 	if (failed) { /* nothing found */
205*58a2b000SEvgeniy Ivanov 		/*
206*58a2b000SEvgeniy Ivanov 		 * allocate from heap, keep chunk len in
207*58a2b000SEvgeniy Ivanov 		 * first word
208*58a2b000SEvgeniy Ivanov 		 */
209*58a2b000SEvgeniy Ivanov 		help = top;
210*58a2b000SEvgeniy Ivanov 
211*58a2b000SEvgeniy Ivanov 		/* make _sure_ the region can hold a struct fl. */
212*58a2b000SEvgeniy Ivanov 		if (size < ALIGN(sizeof (struct fl *)))
213*58a2b000SEvgeniy Ivanov 			size = ALIGN(sizeof (struct fl *));
214*58a2b000SEvgeniy Ivanov 		top += ALIGN(sizeof(unsigned int)) + ALIGN(size);
215*58a2b000SEvgeniy Ivanov #ifdef HEAP_LIMIT
216*58a2b000SEvgeniy Ivanov 		if (top > (char *)HEAP_LIMIT)
217*58a2b000SEvgeniy Ivanov 			panic("heap full (%p+%zu)", help, size);
218*58a2b000SEvgeniy Ivanov #endif
219*58a2b000SEvgeniy Ivanov 		*(unsigned int *)(void *)help = (unsigned int)ALIGN(size);
220*58a2b000SEvgeniy Ivanov #ifdef ALLOC_TRACE
221*58a2b000SEvgeniy Ivanov 		printf("=%lx\n", (u_long)help + ALIGN(sizeof(unsigned int)));
222*58a2b000SEvgeniy Ivanov #endif
223*58a2b000SEvgeniy Ivanov 		return help + ALIGN(sizeof(unsigned int));
224*58a2b000SEvgeniy Ivanov 	}
225*58a2b000SEvgeniy Ivanov 
226*58a2b000SEvgeniy Ivanov 	/* we take the best fit */
227*58a2b000SEvgeniy Ivanov 	f = bestf;
228*58a2b000SEvgeniy Ivanov 
229*58a2b000SEvgeniy Ivanov #ifndef ALLOC_FIRST_FIT
230*58a2b000SEvgeniy Ivanov found:
231*58a2b000SEvgeniy Ivanov #endif
232*58a2b000SEvgeniy Ivanov 	/* remove from freelist */
233*58a2b000SEvgeniy Ivanov 	help = (char *)(void *)*f;
234*58a2b000SEvgeniy Ivanov 	*f = (*f)->next;
235*58a2b000SEvgeniy Ivanov #ifdef ALLOC_TRACE
236*58a2b000SEvgeniy Ivanov 	printf("=%lx (origsize %u)\n",
237*58a2b000SEvgeniy Ivanov 	    (u_long)help + ALIGN(sizeof(unsigned int)), *(unsigned int *)help);
238*58a2b000SEvgeniy Ivanov #endif
239*58a2b000SEvgeniy Ivanov 	return help + ALIGN(sizeof(unsigned int));
240*58a2b000SEvgeniy Ivanov }
241*58a2b000SEvgeniy Ivanov 
242*58a2b000SEvgeniy Ivanov __compactcall void
243*58a2b000SEvgeniy Ivanov /*ARGSUSED*/
dealloc(void * ptr,size_t size)244*58a2b000SEvgeniy Ivanov dealloc(void *ptr, size_t size)
245*58a2b000SEvgeniy Ivanov {
246*58a2b000SEvgeniy Ivanov 	struct fl *f =
247*58a2b000SEvgeniy Ivanov 	    (struct fl *)(void *)((char *)(void *)ptr -
248*58a2b000SEvgeniy Ivanov 	    ALIGN(sizeof(unsigned int)));
249*58a2b000SEvgeniy Ivanov #ifdef ALLOC_TRACE
250*58a2b000SEvgeniy Ivanov 	printf("dealloc(%lx, %zu) (origsize %u)\n", (u_long)ptr, size, f->size);
251*58a2b000SEvgeniy Ivanov #endif
252*58a2b000SEvgeniy Ivanov #ifdef DEBUG
253*58a2b000SEvgeniy Ivanov 	if (size > (size_t)f->size) {
254*58a2b000SEvgeniy Ivanov 		printf("dealloc %zu bytes @%lx, should be <=%u\n",
255*58a2b000SEvgeniy Ivanov 			size, (u_long)ptr, f->size);
256*58a2b000SEvgeniy Ivanov 	}
257*58a2b000SEvgeniy Ivanov 
258*58a2b000SEvgeniy Ivanov 	if (ptr < (void *)HEAP_START)
259*58a2b000SEvgeniy Ivanov 		printf("dealloc: %lx before start of heap.\n", (u_long)ptr);
260*58a2b000SEvgeniy Ivanov 
261*58a2b000SEvgeniy Ivanov #ifdef HEAP_LIMIT
262*58a2b000SEvgeniy Ivanov 	if (ptr > (void *)HEAP_LIMIT)
263*58a2b000SEvgeniy Ivanov 		printf("dealloc: %lx beyond end of heap.\n", (u_long)ptr);
264*58a2b000SEvgeniy Ivanov #endif
265*58a2b000SEvgeniy Ivanov #endif /* DEBUG */
266*58a2b000SEvgeniy Ivanov 	/* put into freelist */
267*58a2b000SEvgeniy Ivanov 	f->next = freelist;
268*58a2b000SEvgeniy Ivanov 	freelist = f;
269*58a2b000SEvgeniy Ivanov }
270