Chameleon

Chameleon Svn Source Tree

Root/branches/xZenu/src/modules/klibc/zalloc.c

Source at commit 1406 created 12 years 10 months ago.
By meklort, Revert drivers.c so that kexts are only loaded when OSBundleRequired is set and that value is not safe mode. Added some comments about it too.
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 <stdio.h>␊
33#include <string.h>␊
34␊
35typedef struct {␊
36␉char * start;␊
37␉size_t size;␊
38} zmem;␊
39␊
40static zmem * zalloced;␊
41static zmem * zavailable;␊
42static short availableNodes, allocedNodes, totalNodes;␊
43static char * zalloc_base;␊
44static char * zalloc_end;␊
45static void (*zerror)(char *, size_t, const char *, int);␊
46␊
47static void zallocate(char * start,int size);␊
48static void zinsert(zmem * zp, int ndx);␊
49static void zdelete(zmem * zp, int ndx);␊
50static void zcoalesce(void);␊
51␊
52#define ZALLOC_NODES␉16384␊
53␊
54static void malloc_error(char *addr, size_t size, const char *file, int line)␊
55{␊
56#ifdef i386␊
57 asm volatile ("hlt");␊
58#endif␊
59}␊
60␊
61␊
62␊
63// define the block of memory that the allocator will use␊
64void malloc_init(char * start, int size, int nodes, void (*malloc_err_fn)(char *, size_t, const char *, int))␊
65{␊
66/*␉zalloc_base = start ? start : (char *)ZALLOC_ADDR;␊
67␉totalNodes = nodes ? nodes : ZALLOC_NODES;␊
68␉zalloced = (zmem *) zalloc_base;␊
69␉zavailable = (zmem *) zalloc_base + sizeof(zmem) * totalNodes;␊
70␉zavailable[0].start = (char *)zavailable + sizeof(zmem) * totalNodes;␊
71 if (size == 0) size = ZALLOC_LEN;␊
72␉zavailable[0].size = size - (zavailable[0].start - zalloc_base);␊
73 zalloc_end = zalloc_base + size;␊
74␉availableNodes = 1;␊
75␉allocedNodes = 0;␊
76 zerror = malloc_err_fn ? malloc_err_fn : malloc_error;␊
77 */␊
78␉␊
79␉zalloc_base = start;␊
80␉totalNodes = nodes;␊
81␉zalloced = (zmem *) zalloc_base;␊
82␉zavailable = (zmem *) zalloc_base + sizeof(zmem) * totalNodes;␊
83␉zavailable[0].start = (char *)zavailable + sizeof(zmem) * totalNodes;␊
84␉zavailable[0].size = size - (zavailable[0].start - zalloc_base);␊
85␉zalloc_end = zalloc_base + size;␊
86␉availableNodes = 1;␊
87␉allocedNodes = 0;␊
88␉zerror = malloc_err_fn ? malloc_err_fn : malloc_error;␊
89␉␊
90}␊
91␊
92#define BEST_FIT 1␊
93␊
94#undef malloc␊
95void * safe_malloc(size_t size, const char *file, int line);␊
96void *malloc(size_t size)␊
97{␊
98␉return safe_malloc(size, __FILE__, __LINE__);␊
99}␊
100␊
101void * safe_malloc(size_t size, const char *file, int line)␊
102{␊
103␉int i;␊
104#if BEST_FIT␊
105 int bestFit;␊
106 size_t smallestSize;␊
107#endif␊
108␉char * ret = 0;␊
109␊
110␉if ( !zalloc_base )␊
111␉{␊
112␉␉printf("malloc_init not called.\n");␊
113␉␉while(1);␊
114␉}␊
115␊
116␉size = ((size + 0xf) & ~0xf);␊
117␊
118 if (size == 0) {␊
119 if (zerror) (*zerror)((char *)0xdeadbeef, 0, file, line);␊
120 }␊
121#if BEST_FIT␊
122 smallestSize = 0;␊
123 bestFit = -1;␊
124#endif␊
125 ␊
126␉for (i = 0; i < availableNodes; i++)␊
127␉{␊
128␉␉// find node with equal size, or if not found,␊
129 // then smallest node that fits.␊
130␉␉if ( zavailable[i].size == size )␊
131␉␉{␊
132␉␉␉zallocate(ret = zavailable[i].start, size);␊
133␉␉␉zdelete(zavailable, i); availableNodes--;␊
134␉␉␉goto done;␊
135␉␉}␊
136#if BEST_FIT␊
137 else␊
138 {␊
139 if ((zavailable[i].size > size) &&␊
140 ((smallestSize == 0) ||␊
141 (zavailable[i].size < smallestSize)))␊
142 {␊
143 bestFit = i;␊
144 smallestSize = zavailable[i].size;␊
145 }␊
146 }␊
147 ␊
148#else␊
149␉␉else if ( zavailable[i].size > size )␊
150␉␉{␊
151␉␉␉zallocate(ret = zavailable[i].start, size);␊
152␉␉␉zavailable[i].start += size;␊
153␉␉␉zavailable[i].size -= size;␊
154␉␉␉goto done;␊
155␉␉}␊
156#endif␊
157 }␊
158#if BEST_FIT␊
159 if (bestFit != -1)␊
160 {␊
161 zallocate(ret = zavailable[bestFit].start, size);␊
162 zavailable[bestFit].start += size;␊
163 zavailable[bestFit].size -= size;␊
164 }␊
165#endif␊
166␊
167done:␊
168␉if ((ret == 0) || (ret + size >= zalloc_end))␊
169 {␊
170␉␉if (zerror) (*zerror)(ret, size, file, line);␊
171 }␊
172␉if (ret != 0)␊
173 {␊
174␉␉memset(ret, 0, size);␊
175 }␊
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␉␉␉zdelete(zalloced, i); allocedNodes--;␊
204␉␉␉found = 1;␊
205␉␉␉break;␊
206␉␉}␊
207␉}␊
208␉if ( !found ) {␊
209 if (zerror) (*zerror)(pointer, rp, "free", 0);␊
210 else return;␊
211 }␊
212␊
213␉for (i = 0; i < availableNodes; i++)␊
214␉{␊
215␉␉if ((start + tsize) == zavailable[i].start) // merge it in␊
216␉␉{␊
217␉␉␉zavailable[i].start = start;␊
218␉␉␉zavailable[i].size += tsize;␊
219␉␉␉zcoalesce();␊
220␉␉␉return;␊
221␉␉}␊
222␊
223␉␉if ((i > 0) &&␊
224 (zavailable[i-1].start + zavailable[i-1].size == start))␊
225␉␉{␊
226␉␉␉zavailable[i-1].size += tsize;␊
227␉␉␉zcoalesce();␊
228␉␉␉return;␊
229␉␉}␊
230␊
231␉␉if ((start + tsize) < zavailable[i].start)␊
232␉␉{␊
233 if (++availableNodes > totalNodes) {␊
234 if (zerror) (*zerror)((char *)0xf000f000, 0, "free", 0);␊
235 }␊
236␉␉␉zinsert(zavailable, i); ␊
237␉␉␉zavailable[i].start = start;␊
238␉␉␉zavailable[i].size = tsize;␊
239␉␉␉return;␊
240␉␉}␊
241␉}␊
242␊
243 if (++availableNodes > totalNodes) {␊
244 if (zerror) (*zerror)((char *)0xf000f000, 1, "free", 0);␊
245 }␊
246␉zavailable[i].start = start;␊
247␉zavailable[i].size = tsize;␊
248␉zcoalesce();␊
249␉return;␊
250}␊
251␊
252static void␊
253zallocate(char * start,int size)␊
254{␊
255␉zalloced[allocedNodes].start = start;␊
256␉zalloced[allocedNodes].size = size;␊
257␉if (++allocedNodes > totalNodes) {␊
258 if (zerror) (*zerror)((char *)0xf000f000, 2, "zallocate", 0);␊
259 };␊
260}␊
261␊
262static void␊
263zinsert(zmem * zp, int ndx)␊
264{␊
265␉int i;␊
266␉zmem *z1, *z2;␊
267␊
268␉i = totalNodes-2;␊
269␉z1 = zp + i;␊
270␉z2 = z1 + 1;␊
271␊
272␉for (; i >= ndx; i--, z1--, z2--)␊
273␉{␊
274 *z2 = *z1;␊
275␉}␊
276}␊
277␊
278static void␊
279zdelete(zmem * zp, int ndx)␊
280{␊
281␉int i;␊
282␉zmem *z1, *z2;␊
283␊
284␉z1 = zp + ndx;␊
285␉z2 = z1 + 1;␊
286␊
287␉for (i = ndx; i < totalNodes-1; i++, z1++, z2++)␊
288␉{␊
289 *z1 = *z2;␊
290␉}␊
291}␊
292␊
293static void␊
294zcoalesce(void)␊
295{␊
296␉int i;␊
297␊
298␉for (i = 0; i < availableNodes-1; i++)␊
299␉{␊
300␉␉if ( zavailable[i].start + zavailable[i].size == ␊
301 zavailable[i+1].start )␊
302␉␉{␊
303␉␉␉zavailable[i].size += zavailable[i+1].size;␊
304␉␉␉zdelete(zavailable, i+1); availableNodes--;␊
305␉␉␉return;␊
306␉␉}␊
307␉}␉␊
308}␊
309␊
310/* This is the simplest way possible. Should fix this. */␊
311void * realloc(void * start, size_t newsize)␊
312{␊
313 void * newstart = safe_malloc(newsize, __FILE__, __LINE__);␊
314 memcpy(start, newstart, newsize);␊
315 free(start);␊
316 return newstart;␊
317}␊
318

Archive Download this file

Revision: 1406