Chameleon

Chameleon Svn Source Tree

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

Archive Download this file

Revision: 676