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

Archive Download this file

Revision: 1654