Chameleon

Chameleon Svn Source Tree

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

Archive Download this file

Revision: 1468