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

Archive Download this file

Revision: 789