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