Chameleon

Chameleon Svn Source Tree

Root/branches/JrCs/i386/libsa/zalloc.c

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

Archive Download this file

Revision: 1466