Chameleon

Chameleon Svn Source Tree

Root/branches/ErmaC/Trunk/i386/libsa/zalloc.c

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

Archive Download this file

Revision: 2045