Chameleon

Chameleon Svn Source Tree

Root/tags/2.3/i386/libsa/zalloc.c

Source at commit HEAD created 2 years 11 months ago.
By ifabio, Few update to kernelPatcher (Credits to CrazyBirdy)
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 "saio_internal.h" - Azi: needed for ZDEBUG (printf)
34#include "memory.h"
35
36#define ZDEBUG 0 //Azi: booter doesn't load with this enabled; instant reboot at "boot1: ..."
37
38#if ZDEBUG
39int zout;
40#endif
41
42typedef struct {
43char * start;
44size_t size;
45} zmem;
46
47static zmem * zalloced;
48static zmem * zavailable;
49static short availableNodes, allocedNodes, totalNodes;
50static char * zalloc_base;
51static char * zalloc_end;
52static void (*zerror)(char *, size_t, const char *, int);
53
54static void zallocate(char * start,int size);
55static void zinsert(zmem * zp, int ndx);
56static void zdelete(zmem * zp, int ndx);
57static void zcoalesce(void);
58
59#if ZDEBUG
60size_t zalloced_size;
61#endif
62
63#define ZALLOC_NODES32767 /* was 16384 */
64
65static void malloc_error(char *addr, size_t size, const char *file, int line)
66{
67#ifdef i386
68asm volatile ("hlt");
69#endif
70}
71
72// define the block of memory that the allocator will use
73void malloc_init(char * start, int size, int nodes, void (*malloc_err_fn)(char *, size_t, const char *, int))
74{
75zalloc_base = start ? start : (char *)ZALLOC_ADDR;
76totalNodes = nodes ? nodes : ZALLOC_NODES;
77zalloced = (zmem *) zalloc_base;
78zavailable = (zmem *) (zalloc_base + sizeof(zmem) * totalNodes);
79zavailable[0].start = (char *)zavailable + sizeof(zmem) * totalNodes;
80
81if (size == 0)
82{
83size = ZALLOC_LEN;
84}
85
86zavailable[0].size = size - (zavailable[0].start - zalloc_base);
87zalloc_end = zalloc_base + size;
88availableNodes = 1;
89allocedNodes = 0;
90zerror = malloc_err_fn ? malloc_err_fn : malloc_error;
91}
92
93#define BEST_FIT 1
94
95void * safe_malloc(size_t size, const char *file, int line)
96{
97int i;
98#if BEST_FIT
99int bestFit;
100size_t smallestSize;
101#endif
102char * ret = 0;
103
104if ( !zalloc_base )
105{
106// this used to follow the bss but some bios' corrupted it...
107malloc_init((char *)ZALLOC_ADDR, ZALLOC_LEN, ZALLOC_NODES, malloc_error);
108}
109
110size = ((size + 0xf) & ~0xf);
111
112if (size == 0 && zerror)
113{
114(*zerror)((char *)0xdeadbeef, 0, file, line);
115 }
116#if BEST_FIT
117smallestSize = 0;
118bestFit = -1;
119#endif
120
121for (i = 0; i < availableNodes; i++)
122{
123// find node with equal size, or if not found,
124 // then smallest node that fits.
125if (zavailable[i].size == size)
126{
127zallocate(ret = zavailable[i].start, size);
128zdelete(zavailable, i); availableNodes--;
129goto done;
130}
131#if BEST_FIT
132else {
133if ((zavailable[i].size > size) && ((smallestSize == 0) || (zavailable[i].size < smallestSize))) {
134bestFit = i;
135smallestSize = zavailable[i].size;
136}
137}
138#else
139else if (zavailable[i].size > size)
140{
141zallocate(ret = zavailable[i].start, size);
142zavailable[i].start += size;
143zavailable[i].size -= size;
144goto done;
145}
146#endif
147}
148#if BEST_FIT
149if (bestFit != -1) {
150zallocate(ret = zavailable[bestFit].start, size);
151zavailable[bestFit].start += size;
152zavailable[bestFit].size -= size;
153}
154#endif
155
156done:
157if ((ret == 0) || (ret + size >= zalloc_end))
158{
159if (zerror)
160{
161(*zerror)(ret, size, file, line);
162}
163}
164
165if (ret != 0)
166{
167bzero(ret, size);
168}
169#if ZDEBUG
170zalloced_size += size;
171#endif
172return (void *) ret;
173}
174
175void free(void * pointer)
176{
177unsigned long rp;
178int i, found = 0;
179size_t tsize = 0;
180char * start = pointer;
181
182#if i386
183// Get return address of our caller,
184// in case we have to report an error below.
185asm volatile ("movl %%esp, %%eax\n\t"
186 "subl $4, %%eax\n\t"
187 "movl 0(%%eax), %%eax" : "=a" (rp));
188#else
189 rp = 0;
190#endif
191
192if (!start)
193{
194return;
195}
196
197for (i = 0; i < allocedNodes; i++)
198{
199if (zalloced[i].start == start)
200{
201tsize = zalloced[i].size;
202#if ZDEBUG
203zout -= tsize;
204printf(" zz out %d\n", zout);
205#endif
206zdelete(zalloced, i); allocedNodes--;
207found = 1;
208#if ZDEBUG
209memset(pointer, 0x5A, tsize);
210#endif
211break;
212}
213}
214if (!found)
215{
216if (zerror)
217{
218(*zerror)(pointer, rp, "free", 0);
219} else {
220return;
221}
222}
223#if ZDEBUG
224 zalloced_size -= tsize;
225#endif
226
227for (i = 0; i < availableNodes; i++)
228{
229if ((start + tsize) == zavailable[i].start) // merge it in
230{
231zavailable[i].start = start;
232zavailable[i].size += tsize;
233zcoalesce();
234return;
235}
236
237if ((i > 0) && (zavailable[i-1].start + zavailable[i-1].size == start))
238{
239zavailable[i-1].size += tsize;
240zcoalesce();
241return;
242}
243
244if ((start + tsize) < zavailable[i].start)
245{
246 if (++availableNodes > totalNodes)
247{
248if (zerror)
249{
250(*zerror)((char *)0xf000f000, 0, "free", 0);
251}
252}
253zinsert(zavailable, i);
254zavailable[i].start = start;
255zavailable[i].size = tsize;
256return;
257}
258}
259
260if (++availableNodes > totalNodes)
261{
262if (zerror)
263{
264(*zerror)((char *)0xf000f000, 1, "free", 0);
265}
266}
267zavailable[i].start = start;
268zavailable[i].size = tsize;
269zcoalesce();
270
271return;
272}
273
274static void
275zallocate(char * start,int size)
276{
277
278#if ZDEBUG
279zout += size;
280printf(" alloc %d, total 0x%x\n",size,zout);
281#endif
282
283zalloced[allocedNodes].start = start;
284zalloced[allocedNodes].size = size;
285
286if (++allocedNodes > totalNodes)
287{
288if (zerror)
289{
290(*zerror)((char *)0xf000f000, 2, "zallocate", 0);
291}
292};
293}
294
295static void
296zinsert(zmem * zp, int ndx)
297{
298int i;
299zmem *z1, *z2;
300
301i = totalNodes-2;
302z1 = zp + i;
303z2 = z1 + 1;
304
305for (; i >= ndx; i--, z1--, z2--)
306{
307*z2 = *z1;
308}
309}
310
311static void
312zdelete(zmem * zp, int ndx)
313{
314int i;
315zmem *z1, *z2;
316
317z1 = zp + ndx;
318z2 = z1 + 1;
319
320for (i = ndx; i < totalNodes - 1; i++, z1++, z2++)
321{
322*z1 = *z2;
323}
324}
325
326static void
327zcoalesce(void)
328{
329int i;
330
331for (i = 0; i < availableNodes-1; i++)
332{
333if ( zavailable[i].start + zavailable[i].size == zavailable[i + 1].start )
334{
335zavailable[i].size += zavailable[i + 1].size;
336zdelete(zavailable, i + 1); availableNodes--;
337return;
338}
339}
340}
341
342/* This is the simplest way possible. Should fix this. */
343void * realloc(void * start, size_t newsize)
344{
345 void * newstart = safe_malloc(newsize, __FILE__, __LINE__);
346 bcopy(start, newstart, newsize);
347 free(start);
348 return newstart;
349}
350

Archive Download this file

Revision: HEAD