Chameleon

Chameleon Svn Source Tree

Root/branches/xZenu/src/modules/klibc/zalloc.c

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

Archive Download this file

Revision: 1297