1 | /*␊ |
2 | * Copyright (c) 1999-2003 Apple Computer, Inc. All rights reserved.␊ |
3 | *␊ |
4 | * ␊ |
5 | * Portions Copyright (c) 1999-2003 Apple Computer, Inc. All Rights␊ |
6 | * Reserved. This file contains Original Code and/or Modifications of␊ |
7 | * Original Code as defined in and that are subject to the Apple Public␊ |
8 | * Source License Version 2.0 (the "License"). You may not use this file␊ |
9 | * except in compliance with the License. Please obtain a copy of the␊ |
10 | * License at http://www.apple.com/publicsource and read it before using␊ |
11 | * this file.␊ |
12 | * ␊ |
13 | * The Original Code and all software distributed under the License are␊ |
14 | * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER␊ |
15 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,␊ |
16 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,␊ |
17 | * FITNESS FOR A PARTICULAR PURPOSE OR NON- INFRINGEMENT. Please see the␊ |
18 | * License for the specific language governing rights and limitations␊ |
19 | * under the License.␊ |
20 | * ␊ |
21 | *␊ |
22 | * Copyright 1993 NeXT Computer, Inc.␊ |
23 | * All rights reserved.␊ |
24 | *␊ |
25 | * Sam's simple memory allocator.␊ |
26 | *␊ |
27 | */␊ |
28 | ␊ |
29 | #include "libsa.h"␊ |
30 | //#include "saio_internal.h" - Azi: needed for ZDEBUG (printf)␊ |
31 | #include "memory.h"␊ |
32 | ␊ |
33 | #define ZDEBUG 0 //Azi: booter doesn't load with this enabled; instant reboot at "boot1: ..."␊ |
34 | ␊ |
35 | #if ZDEBUG␊ |
36 | int zout;␊ |
37 | #endif␊ |
38 | ␊ |
39 | typedef struct␊ |
40 | {␊ |
41 | ␉char * start;␊ |
42 | ␉size_t size;␊ |
43 | } zmem;␊ |
44 | ␊ |
45 | static zmem * zalloced;␊ |
46 | static zmem * zavailable;␊ |
47 | static short availableNodes, allocedNodes, totalNodes;␊ |
48 | static char * zalloc_base;␊ |
49 | static char * zalloc_end;␊ |
50 | static void (*zerror)(char *, size_t, const char *, int);␊ |
51 | ␊ |
52 | static void zallocate(char * start,int size);␊ |
53 | static void zinsert(zmem * zp, int ndx);␊ |
54 | static void zdelete(zmem * zp, int ndx);␊ |
55 | static void zcoalesce(void);␊ |
56 | ␊ |
57 | #if ZDEBUG␊ |
58 | size_t zalloced_size;␊ |
59 | #endif␊ |
60 | ␊ |
61 | #define ZALLOC_NODES␉32767 /* was 16384 */␊ |
62 | ␊ |
63 | static void malloc_error(char *addr, size_t size, const char *file, int line)␊ |
64 | {␊ |
65 | #ifdef i386␊ |
66 | ␉asm volatile ("hlt");␊ |
67 | #endif␊ |
68 | }␊ |
69 | ␊ |
70 | // define the block of memory that the allocator will use␊ |
71 | void malloc_init(char * start, int size, int nodes, void (*malloc_err_fn)(char *, size_t, const char *, int))␊ |
72 | {␊ |
73 | ␉zalloc_base = start ? start : (char *)ZALLOC_ADDR;␊ |
74 | ␉totalNodes = nodes ? nodes : ZALLOC_NODES;␊ |
75 | ␉zalloced = (zmem *) zalloc_base;␊ |
76 | ␉zavailable = (zmem *) zalloc_base + sizeof(zmem) * totalNodes;␊ |
77 | ␉zavailable[0].start = (char *)zavailable + sizeof(zmem) * totalNodes;␊ |
78 | ␊ |
79 | ␉if (size == 0)␊ |
80 | ␉{␊ |
81 | ␉␉size = ZALLOC_LEN;␊ |
82 | ␉}␊ |
83 | ␊ |
84 | ␉zavailable[0].size = size - (zavailable[0].start - zalloc_base);␊ |
85 | ␉zalloc_end = zalloc_base + size;␊ |
86 | ␉availableNodes = 1;␊ |
87 | ␉allocedNodes = 0;␊ |
88 | ␉zerror = malloc_err_fn ? malloc_err_fn : malloc_error;␊ |
89 | }␊ |
90 | ␊ |
91 | #define BEST_FIT 1␊ |
92 | ␊ |
93 | void * safe_malloc(size_t size, const char *file, int line)␊ |
94 | {␊ |
95 | ␉int i;␊ |
96 | #if BEST_FIT␊ |
97 | ␉int bestFit;␊ |
98 | ␉size_t smallestSize;␊ |
99 | #endif␊ |
100 | ␉char * ret = 0;␊ |
101 | ␊ |
102 | ␉if ( !zalloc_base )␊ |
103 | ␉{␊ |
104 | ␉␉// this used to follow the bss but some bios' corrupted it...␊ |
105 | ␉␉malloc_init((char *)ZALLOC_ADDR, ZALLOC_LEN, ZALLOC_NODES, malloc_error);␊ |
106 | ␉}␊ |
107 | ␊ |
108 | ␉size = ((size + 0xf) & ~0xf);␊ |
109 | ␊ |
110 | if (size == 0)␊ |
111 | ␉{␊ |
112 | ␉␉if (zerror)␊ |
113 | ␉␉{␊ |
114 | ␉␉␉(*zerror)((char *)0xdeadbeef, 0, file, line);␊ |
115 | ␉}␊ |
116 | }␊ |
117 | #if BEST_FIT␊ |
118 | ␉smallestSize = 0;␊ |
119 | ␉bestFit = -1;␊ |
120 | #endif␊ |
121 | ␊ |
122 | ␉for (i = 0; i < availableNodes; i++)␊ |
123 | ␉{␊ |
124 | ␉␉// find node with equal size, or if not found,␊ |
125 | // then smallest node that fits.␊ |
126 | ␉␉if (zavailable[i].size == size)␊ |
127 | ␉␉{␊ |
128 | ␉␉␉zallocate(ret = zavailable[i].start, size);␊ |
129 | ␉␉␉zdelete(zavailable, i); availableNodes--;␊ |
130 | ␉␉␉goto done;␊ |
131 | ␉␉}␊ |
132 | #if BEST_FIT␊ |
133 | ␉␉else␊ |
134 | ␉␉{␊ |
135 | ␉␉␉if ((zavailable[i].size > size) && ((smallestSize == 0) || (zavailable[i].size < smallestSize)))␊ |
136 | ␉␉␉{␊ |
137 | ␉␉␉␉bestFit = i;␊ |
138 | ␉␉␉␉smallestSize = zavailable[i].size;␊ |
139 | ␉␉␉}␊ |
140 | ␉␉}␊ |
141 | ␊ |
142 | #else␊ |
143 | ␉␉else if (zavailable[i].size > size)␊ |
144 | ␉␉{␊ |
145 | ␉␉␉zallocate(ret = zavailable[i].start, size);␊ |
146 | ␉␉␉zavailable[i].start += size;␊ |
147 | ␉␉␉zavailable[i].size -= size;␊ |
148 | ␉␉␉goto done;␊ |
149 | ␉␉}␊ |
150 | #endif␊ |
151 | ␉}␊ |
152 | #if BEST_FIT␊ |
153 | ␉if (bestFit != -1)␊ |
154 | ␉{␊ |
155 | ␉␉zallocate(ret = zavailable[bestFit].start, size);␊ |
156 | ␉␉zavailable[bestFit].start += size;␊ |
157 | ␉␉zavailable[bestFit].size -= size;␊ |
158 | ␉}␊ |
159 | #endif␊ |
160 | ␊ |
161 | done:␊ |
162 | ␉if ((ret == 0) || (ret + size >= zalloc_end))␊ |
163 | ␉{␊ |
164 | ␉␉if (zerror)␊ |
165 | ␉␉{␊ |
166 | ␉␉␉(*zerror)(ret, size, file, line);␊ |
167 | ␉␉}␊ |
168 | ␉}␊ |
169 | ␊ |
170 | ␉if (ret != 0)␊ |
171 | ␉{␊ |
172 | ␉␉bzero(ret, size);␊ |
173 | ␉}␊ |
174 | #if ZDEBUG␊ |
175 | ␉zalloced_size += size;␊ |
176 | #endif␊ |
177 | ␉return (void *) ret;␊ |
178 | }␊ |
179 | ␊ |
180 | void free(void * pointer)␊ |
181 | {␊ |
182 | ␉unsigned long rp;␊ |
183 | ␉int i, found = 0;␊ |
184 | ␉size_t tsize = 0;␊ |
185 | ␉char * start = pointer;␊ |
186 | ␊ |
187 | #if i386 ␊ |
188 | ␉// Get return address of our caller,␊ |
189 | ␉// in case we have to report an error below.␊ |
190 | ␉asm volatile ("movl %%esp, %%eax\n\t"␊ |
191 | "subl $4, %%eax\n\t"␊ |
192 | "movl 0(%%eax), %%eax" : "=a" (rp));␊ |
193 | #else␊ |
194 | rp = 0;␊ |
195 | #endif␊ |
196 | ␊ |
197 | ␉if (!start)␊ |
198 | ␉{␊ |
199 | ␉␉return;␊ |
200 | ␉}␊ |
201 | ␊ |
202 | ␉for (i = 0; i < allocedNodes; i++)␊ |
203 | ␉{␊ |
204 | ␉␉if (zalloced[i].start == start)␊ |
205 | ␉␉{␊ |
206 | ␉␉␉tsize = zalloced[i].size;␊ |
207 | #if ZDEBUG␊ |
208 | ␉␉␉zout -= tsize;␊ |
209 | ␉␉␉printf(" zz out %d\n", zout);␊ |
210 | #endif␊ |
211 | ␉␉␉zdelete(zalloced, i); allocedNodes--;␊ |
212 | ␉␉␉found = 1;␊ |
213 | #if ZDEBUG␊ |
214 | ␉␉␉memset(pointer, 0x5A, tsize);␊ |
215 | #endif␊ |
216 | ␉␉␉break;␊ |
217 | ␉␉}␊ |
218 | ␉}␊ |
219 | ␉if (!found)␊ |
220 | ␉{␊ |
221 | ␉␉if (zerror)␊ |
222 | ␉␉{␊ |
223 | ␉␉␉(*zerror)(pointer, rp, "free", 0);␊ |
224 | ␉␉}␊ |
225 | ␉␉else␊ |
226 | ␉␉{␊ |
227 | ␉␉␉return;␊ |
228 | ␉␉}␊ |
229 | ␉}␊ |
230 | #if ZDEBUG␊ |
231 | zalloced_size -= tsize;␊ |
232 | #endif␊ |
233 | ␊ |
234 | ␉for (i = 0; i < availableNodes; i++)␊ |
235 | ␉{␊ |
236 | ␉␉if ((start + tsize) == zavailable[i].start) // merge it in␊ |
237 | ␉␉{␊ |
238 | ␉␉␉zavailable[i].start = start;␊ |
239 | ␉␉␉zavailable[i].size += tsize;␊ |
240 | ␉␉␉zcoalesce();␊ |
241 | ␉␉␉return;␊ |
242 | ␉␉}␊ |
243 | ␊ |
244 | ␉␉if ((i > 0) && (zavailable[i-1].start + zavailable[i-1].size == start))␊ |
245 | ␉␉{␊ |
246 | ␉␉␉zavailable[i-1].size += tsize;␊ |
247 | ␉␉␉zcoalesce();␊ |
248 | ␉␉␉return;␊ |
249 | ␉␉}␊ |
250 | ␊ |
251 | ␉␉if ((start + tsize) < zavailable[i].start)␊ |
252 | ␉␉{␊ |
253 | if (++availableNodes > totalNodes)␊ |
254 | ␉␉␉{␊ |
255 | ␉␉␉␉if (zerror)␊ |
256 | ␉␉␉␉{␊ |
257 | ␉␉␉␉␉(*zerror)((char *)0xf000f000, 0, "free", 0);␊ |
258 | ␉␉␉␉}␊ |
259 | ␉␉␉}␊ |
260 | ␉␉␉zinsert(zavailable, i); ␊ |
261 | ␉␉␉zavailable[i].start = start;␊ |
262 | ␉␉␉zavailable[i].size = tsize;␊ |
263 | ␉␉␉return;␊ |
264 | ␉␉}␊ |
265 | ␉}␊ |
266 | ␊ |
267 | ␉if (++availableNodes > totalNodes)␊ |
268 | ␉{␊ |
269 | ␉␉if (zerror)␊ |
270 | ␉␉{␊ |
271 | ␉␉␉(*zerror)((char *)0xf000f000, 1, "free", 0);␊ |
272 | ␉␉}␊ |
273 | ␉}␊ |
274 | ␉zavailable[i].start = start;␊ |
275 | ␉zavailable[i].size = tsize;␊ |
276 | ␉zcoalesce();␊ |
277 | ␊ |
278 | ␉return;␊ |
279 | }␊ |
280 | ␊ |
281 | static void zallocate(char * start,int size)␊ |
282 | {␊ |
283 | ␊ |
284 | #if ZDEBUG␊ |
285 | ␉zout += size;␊ |
286 | ␉printf(" alloc %d, total 0x%x\n",size,zout);␊ |
287 | #endif␊ |
288 | ␊ |
289 | ␉zalloced[allocedNodes].start = start;␊ |
290 | ␉zalloced[allocedNodes].size = size;␊ |
291 | ␊ |
292 | ␉if (++allocedNodes > totalNodes)␊ |
293 | ␉{␊ |
294 | ␉␉if (zerror)␊ |
295 | ␉␉{␊ |
296 | ␉␉␉(*zerror)((char *)0xf000f000, 2, "zallocate", 0);␊ |
297 | ␉␉}␊ |
298 | ␉};␊ |
299 | }␊ |
300 | ␊ |
301 | static void zinsert(zmem * zp, int ndx)␊ |
302 | {␊ |
303 | ␉int i;␊ |
304 | ␉zmem *z1, *z2;␊ |
305 | ␊ |
306 | ␉i = totalNodes-2;␊ |
307 | ␉z1 = zp + i;␊ |
308 | ␉z2 = z1 + 1;␊ |
309 | ␊ |
310 | ␉for (; i >= ndx; i--, z1--, z2--)␊ |
311 | ␉{␊ |
312 | ␉␉*z2 = *z1;␊ |
313 | ␉}␊ |
314 | }␊ |
315 | ␊ |
316 | static void zdelete(zmem * zp, int ndx)␊ |
317 | {␊ |
318 | ␉int i;␊ |
319 | ␉zmem *z1, *z2;␊ |
320 | ␊ |
321 | ␉z1 = zp + ndx;␊ |
322 | ␉z2 = z1 + 1;␊ |
323 | ␊ |
324 | ␉for (i = ndx; i < totalNodes - 1; i++, z1++, z2++)␊ |
325 | ␉{␊ |
326 | ␉␉*z1 = *z2;␊ |
327 | ␉}␊ |
328 | }␊ |
329 | ␊ |
330 | static void zcoalesce(void)␊ |
331 | {␊ |
332 | ␉int i;␊ |
333 | ␊ |
334 | ␉for (i = 0; i < availableNodes-1; i++)␊ |
335 | ␉{␊ |
336 | ␉␉if ( zavailable[i].start + zavailable[i].size == zavailable[i + 1].start )␊ |
337 | ␉␉{␊ |
338 | ␉␉␉zavailable[i].size += zavailable[i + 1].size;␊ |
339 | ␉␉␉zdelete(zavailable, i + 1); availableNodes--;␊ |
340 | ␉␉␉return;␊ |
341 | ␉␉}␊ |
342 | ␉}␉␊ |
343 | }␊ |
344 | ␊ |
345 | /* This is the simplest way possible. Should fix this. */␊ |
346 | void * realloc(void * start, size_t newsize)␊ |
347 | {␊ |
348 | void * newstart = safe_malloc(newsize, __FILE__, __LINE__);␊ |
349 | bcopy(start, newstart, newsize);␊ |
350 | free(start);␊ |
351 | return newstart;␊ |
352 | }␊ |
353 | |