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