Chameleon

Chameleon Svn Source Tree

Root/branches/azimutz/Chazi/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// Check other DEBUG's, i forgot those while messing with includes.␊
35#include "memory.h"␊
36␊
37#define ZDEBUG 0␊
38//Azi: this DEBUG is messed up; it hangs while "boot1: ..." with␊
39// black screen on my branch and instant reboot on trunk.␊
40␊
41#if ZDEBUG␊
42int zout;␊
43#endif␊
44␊
45typedef struct {␊
46␉char * start;␊
47␉size_t size;␊
48} zmem;␊
49␊
50static zmem * zalloced;␊
51static zmem * zavailable;␊
52static short availableNodes, allocedNodes, totalNodes;␊
53static char * zalloc_base;␊
54static char * zalloc_end;␊
55static void (*zerror)(char *, size_t, const char *, int);␊
56␊
57static void zallocate(char * start,int size);␊
58static void zinsert(zmem * zp, int ndx);␊
59static void zdelete(zmem * zp, int ndx);␊
60static void zcoalesce(void);␊
61␊
62#if ZDEBUG␊
63size_t zalloced_size;␊
64#endif␊
65␊
66#define ZALLOC_NODES␉16384␊
67␊
68static void malloc_error(char *addr, size_t size, const char *file, int line)␊
69{␊
70#ifdef i386␊
71 asm volatile ("hlt");␊
72#endif␊
73}␊
74␊
75// define the block of memory that the allocator will use␊
76void malloc_init(char * start, int size, int nodes, void (*malloc_err_fn)(char *, size_t, const char *, int))␊
77{␊
78␉zalloc_base = start ? start : (char *)ZALLOC_ADDR;␊
79␉totalNodes = nodes ? nodes : ZALLOC_NODES;␊
80␉zalloced = (zmem *) zalloc_base;␊
81␉zavailable = (zmem *) zalloc_base + sizeof(zmem) * totalNodes;␊
82␉zavailable[0].start = (char *)zavailable + sizeof(zmem) * totalNodes;␊
83 if (size == 0) size = ZALLOC_LEN;␊
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 if (zerror) (*zerror)((char *)0xdeadbeef, 0, file, line);␊
112 }␊
113#if BEST_FIT␊
114 smallestSize = 0;␊
115 bestFit = -1;␊
116#endif␊
117 ␊
118␉for (i = 0; i < availableNodes; i++)␊
119␉{␊
120␉␉// find node with equal size, or if not found,␊
121 // then smallest node that fits.␊
122␉␉if ( zavailable[i].size == size )␊
123␉␉{␊
124␉␉␉zallocate(ret = zavailable[i].start, size);␊
125␉␉␉zdelete(zavailable, i); availableNodes--;␊
126␉␉␉goto done;␊
127␉␉}␊
128#if BEST_FIT␊
129 else␊
130 {␊
131 if ((zavailable[i].size > size) &&␊
132 ((smallestSize == 0) ||␊
133 (zavailable[i].size < smallestSize)))␊
134 {␊
135 bestFit = i;␊
136 smallestSize = zavailable[i].size;␊
137 }␊
138 }␊
139 ␊
140#else␊
141␉␉else if ( zavailable[i].size > size )␊
142␉␉{␊
143␉␉␉zallocate(ret = zavailable[i].start, size);␊
144␉␉␉zavailable[i].start += size;␊
145␉␉␉zavailable[i].size -= size;␊
146␉␉␉goto done;␊
147␉␉}␊
148#endif␊
149 }␊
150#if BEST_FIT␊
151 if (bestFit != -1)␊
152 {␊
153 zallocate(ret = zavailable[bestFit].start, size);␊
154 zavailable[bestFit].start += size;␊
155 zavailable[bestFit].size -= size;␊
156 }␊
157#endif␊
158␊
159done:␊
160␉if ((ret == 0) || (ret + size >= zalloc_end))␊
161 {␊
162␉␉if (zerror) (*zerror)(ret, size, file, line);␊
163 }␊
164␉if (ret != 0)␊
165 {␊
166␉␉bzero(ret, size);␊
167 }␊
168#if ZDEBUG␊
169 zalloced_size += size;␊
170#endif␊
171␉return (void *) ret;␊
172}␊
173␊
174void free(void * pointer)␊
175{␊
176 unsigned long rp;␊
177␉int i, found = 0;␊
178 size_t tsize = 0;␊
179␉char * start = pointer;␊
180␊
181#if i386 ␊
182 // Get return address of our caller,␊
183 // in case we have to report an error below.␊
184 asm volatile ("movl %%esp, %%eax\n\t"␊
185 "subl $4, %%eax\n\t"␊
186 "movl 0(%%eax), %%eax" : "=a" (rp) );␊
187#else␊
188 rp = 0;␊
189#endif␊
190␊
191␉if ( !start ) return;␊
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) (*zerror)(pointer, rp, "free", 0);␊
212 else return;␊
213 }␊
214#if ZDEBUG␊
215 zalloced_size -= tsize;␊
216#endif␊
217␊
218␉for (i = 0; i < availableNodes; i++)␊
219␉{␊
220␉␉if ((start + tsize) == zavailable[i].start) // merge it in␊
221␉␉{␊
222␉␉␉zavailable[i].start = start;␊
223␉␉␉zavailable[i].size += tsize;␊
224␉␉␉zcoalesce();␊
225␉␉␉return;␊
226␉␉}␊
227␊
228␉␉if ((i > 0) &&␊
229 (zavailable[i-1].start + zavailable[i-1].size == start))␊
230␉␉{␊
231␉␉␉zavailable[i-1].size += tsize;␊
232␉␉␉zcoalesce();␊
233␉␉␉return;␊
234␉␉}␊
235␊
236␉␉if ((start + tsize) < zavailable[i].start)␊
237␉␉{␊
238 if (++availableNodes > totalNodes) {␊
239 if (zerror) (*zerror)((char *)0xf000f000, 0, "free", 0);␊
240 }␊
241␉␉␉zinsert(zavailable, i); ␊
242␉␉␉zavailable[i].start = start;␊
243␉␉␉zavailable[i].size = tsize;␊
244␉␉␉return;␊
245␉␉}␊
246␉}␊
247␊
248 if (++availableNodes > totalNodes) {␊
249 if (zerror) (*zerror)((char *)0xf000f000, 1, "free", 0);␊
250 }␊
251␉zavailable[i].start = start;␊
252␉zavailable[i].size = tsize;␊
253␉zcoalesce();␊
254␉return;␊
255}␊
256//Azi: static - Mek␊
257//static ␊
258void␊
259zallocate(char * start,int size)␊
260{␊
261#if ZDEBUG␊
262␉zout += size;␊
263␉printf(" alloc %d, total 0x%x\n",size,zout);␊
264#endif␊
265␉zalloced[allocedNodes].start = start;␊
266␉zalloced[allocedNodes].size = size;␊
267␉if (++allocedNodes > totalNodes) {␊
268 if (zerror) (*zerror)((char *)0xf000f000, 2, "zallocate", 0);␊
269 };␊
270}␊
271␊
272static void␊
273zinsert(zmem * zp, int ndx)␊
274{␊
275␉int i;␊
276␉zmem *z1, *z2;␊
277␊
278␉i = totalNodes-2;␊
279␉z1 = zp + i;␊
280␉z2 = z1 + 1;␊
281␊
282␉for (; i >= ndx; i--, z1--, z2--)␊
283␉{␊
284 *z2 = *z1;␊
285␉}␊
286}␊
287␊
288static void␊
289zdelete(zmem * zp, int ndx)␊
290{␊
291␉int i;␊
292␉zmem *z1, *z2;␊
293␊
294␉z1 = zp + ndx;␊
295␉z2 = z1 + 1;␊
296␊
297␉for (i = ndx; i < totalNodes-1; i++, z1++, z2++)␊
298␉{␊
299 *z1 = *z2;␊
300␉}␊
301}␊
302␊
303static void␊
304zcoalesce(void)␊
305{␊
306␉int i;␊
307␊
308␉for (i = 0; i < availableNodes-1; i++)␊
309␉{␊
310␉␉if ( zavailable[i].start + zavailable[i].size == ␊
311 zavailable[i+1].start )␊
312␉␉{␊
313␉␉␉zavailable[i].size += zavailable[i+1].size;␊
314␉␉␉zdelete(zavailable, i+1); availableNodes--;␊
315␉␉␉return;␊
316␉␉}␊
317␉}␉␊
318}␊
319␊
320/* This is the simplest way possible. Should fix this. */␊
321void * realloc(void * start, size_t newsize)␊
322{␊
323 void * newstart = safe_malloc(newsize, __FILE__, __LINE__);␊
324 bcopy(start, newstart, newsize);␊
325 free(start);␊
326 return newstart;␊
327}␊
328

Archive Download this file

Revision: 840