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