Chameleon

Chameleon Svn Source Tree

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

Source at commit 1297 created 12 years 8 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 {␊
36␉char * start;␊
37␉size_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_NODES␉16384␊
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;␊
67␉totalNodes = nodes ? nodes : ZALLOC_NODES;␊
68␉zalloced = (zmem *) zalloc_base;␊
69␉zavailable = (zmem *) zalloc_base + sizeof(zmem) * totalNodes;␊
70␉zavailable[0].start = (char *)zavailable + sizeof(zmem) * totalNodes;␊
71 if (size == 0) size = ZALLOC_LEN;␊
72␉zavailable[0].size = size - (zavailable[0].start - zalloc_base);␊
73 zalloc_end = zalloc_base + size;␊
74␉availableNodes = 1;␊
75␉allocedNodes = 0;␊
76 zerror = malloc_err_fn ? malloc_err_fn : malloc_error;␊
77 */␊
78␉␊
79␉zalloc_base = start;␊
80␉totalNodes = nodes;␊
81␉zalloced = (zmem *) zalloc_base;␊
82␉zavailable = (zmem *) zalloc_base + sizeof(zmem) * totalNodes;␊
83␉zavailable[0].start = (char *)zavailable + sizeof(zmem) * totalNodes;␊
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␊
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{␊
98␉return safe_malloc(size, __FILE__, __LINE__);␊
99}␊
100␊
101void * safe_malloc(size_t size, const char *file, int line)␊
102{␊
103␉int i;␊
104#if BEST_FIT␊
105 int bestFit;␊
106 size_t smallestSize;␊
107#endif␊
108␉char * ret = 0;␊
109␊
110␉if ( !zalloc_base )␊
111␉{␊
112␉␉printf("malloc_init not called.\n");␊
113␉␉while(1);␊
114␉}␊
115␊
116␉size = ((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 ␊
126␉for (i = 0; i < availableNodes; i++)␊
127␉{␊
128␉␉// find node with equal size, or if not found,␊
129 // then smallest node that fits.␊
130␉␉if ( zavailable[i].size == size )␊
131␉␉{␊
132␉␉␉zallocate(ret = zavailable[i].start, size);␊
133␉␉␉zdelete(zavailable, i); availableNodes--;␊
134␉␉␉goto 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␊
149␉␉else if ( zavailable[i].size > size )␊
150␉␉{␊
151␉␉␉zallocate(ret = zavailable[i].start, size);␊
152␉␉␉zavailable[i].start += size;␊
153␉␉␉zavailable[i].size -= size;␊
154␉␉␉goto 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:␊
168␉if ((ret == 0) || (ret + size >= zalloc_end))␊
169 {␊
170␉␉if (zerror) (*zerror)(ret, size, file, line);␊
171 }␊
172␉if (ret != 0)␊
173 {␊
174␉␉memset(ret, 0, size);␊
175 }␊
176␉return (void *) ret;␊
177}␊
178␊
179void free(void * pointer)␊
180{␊
181 unsigned long rp;␊
182␉int i, found = 0;␊
183 size_t tsize = 0;␊
184␉char * 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␊
196␉if ( !start ) return;␊
197␊
198␉for (i = 0; i < allocedNodes; i++)␊
199␉{␊
200␉␉if ( zalloced[i].start == start )␊
201␉␉{␊
202␉␉␉tsize = zalloced[i].size;␊
203␉␉␉zdelete(zalloced, i); allocedNodes--;␊
204␉␉␉found = 1;␊
205␉␉␉break;␊
206␉␉}␊
207␉}␊
208␉if ( !found ) {␊
209 if (zerror) (*zerror)(pointer, rp, "free", 0);␊
210 else return;␊
211 }␊
212␊
213␉for (i = 0; i < availableNodes; i++)␊
214␉{␊
215␉␉if ((start + tsize) == zavailable[i].start) // merge it in␊
216␉␉{␊
217␉␉␉zavailable[i].start = start;␊
218␉␉␉zavailable[i].size += tsize;␊
219␉␉␉zcoalesce();␊
220␉␉␉return;␊
221␉␉}␊
222␊
223␉␉if ((i > 0) &&␊
224 (zavailable[i-1].start + zavailable[i-1].size == start))␊
225␉␉{␊
226␉␉␉zavailable[i-1].size += tsize;␊
227␉␉␉zcoalesce();␊
228␉␉␉return;␊
229␉␉}␊
230␊
231␉␉if ((start + tsize) < zavailable[i].start)␊
232␉␉{␊
233 if (++availableNodes > totalNodes) {␊
234 if (zerror) (*zerror)((char *)0xf000f000, 0, "free", 0);␊
235 }␊
236␉␉␉zinsert(zavailable, i); ␊
237␉␉␉zavailable[i].start = start;␊
238␉␉␉zavailable[i].size = tsize;␊
239␉␉␉return;␊
240␉␉}␊
241␉}␊
242␊
243 if (++availableNodes > totalNodes) {␊
244 if (zerror) (*zerror)((char *)0xf000f000, 1, "free", 0);␊
245 }␊
246␉zavailable[i].start = start;␊
247␉zavailable[i].size = tsize;␊
248␉zcoalesce();␊
249␉return;␊
250}␊
251␊
252static void␊
253zallocate(char * start,int size)␊
254{␊
255␉zalloced[allocedNodes].start = start;␊
256␉zalloced[allocedNodes].size = size;␊
257␉if (++allocedNodes > totalNodes) {␊
258 if (zerror) (*zerror)((char *)0xf000f000, 2, "zallocate", 0);␊
259 };␊
260}␊
261␊
262static void␊
263zinsert(zmem * zp, int ndx)␊
264{␊
265␉int i;␊
266␉zmem *z1, *z2;␊
267␊
268␉i = totalNodes-2;␊
269␉z1 = zp + i;␊
270␉z2 = z1 + 1;␊
271␊
272␉for (; i >= ndx; i--, z1--, z2--)␊
273␉{␊
274 *z2 = *z1;␊
275␉}␊
276}␊
277␊
278static void␊
279zdelete(zmem * zp, int ndx)␊
280{␊
281␉int i;␊
282␉zmem *z1, *z2;␊
283␊
284␉z1 = zp + ndx;␊
285␉z2 = z1 + 1;␊
286␊
287␉for (i = ndx; i < totalNodes-1; i++, z1++, z2++)␊
288␉{␊
289 *z1 = *z2;␊
290␉}␊
291}␊
292␊
293static void␊
294zcoalesce(void)␊
295{␊
296␉int i;␊
297␊
298␉for (i = 0; i < availableNodes-1; i++)␊
299␉{␊
300␉␉if ( zavailable[i].start + zavailable[i].size == ␊
301 zavailable[i+1].start )␊
302␉␉{␊
303␉␉␉zavailable[i].size += zavailable[i+1].size;␊
304␉␉␉zdelete(zavailable, i+1); availableNodes--;␊
305␉␉␉return;␊
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