Chameleon

Chameleon Svn Source Tree

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

Archive Download this file

Revision: 2323