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

Archive Download this file

Revision: 1972