Chameleon

Chameleon Svn Source Tree

Root/branches/xZenu/src/arch/i386/libsa/zalloc.c

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

Archive Download this file

Revision: 1274