Chameleon

Chameleon Svn Source Tree

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

Archive Download this file

Revision: 2531