summaryrefslogtreecommitdiffstats
path: root/Mac/mwerks/malloc/malloc.c
blob: 38bd32a857b7e4a171133cd0b58f3b16e015526e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
/*
 * Attempt at a memory allocator for the Mac, Jack Jansen, CWI, 1995-1997.
 *
 * Code adapted from BSD malloc, which is:
 *
 * Copyright (c) 1983 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#if defined(LIBC_SCCS) && !defined(lint)
/*static char *sccsid = "from: @(#)malloc.c	5.11 (Berkeley) 2/23/91";*/
static char *rcsid = "$Id$";
#endif /* LIBC_SCCS and not lint */

/*
 * malloc.c (Caltech) 2/21/82
 * Chris Kingsley, kingsley@cit-20. Modified by Jack Jansen, CWI.
 *
 * This is a very fast storage allocator.  It allocates blocks of a small 
 * number of different sizes, and keeps free lists of each size.  Blocks that
 * don't exactly fit are passed up to the next larger size.
 *
 * Blocks over a certain size are directly allocated by calling NewPtr.
 * 
 */
 
#ifdef USE_MALLOC_DEBUG
/* You may also selectively enable some of these (but some are interdependent) */
#define DEBUG
#define DEBUG2
#define MSTATS
#define RCHECK
#define VCHECK
#endif /* USE_MALLOC_DEBUG */

/* 
 * Set the next define if you want to return memory that is aligned to 32-byte
 * boundaries. This allows 604 (and, to a lesser extent, any PPC) programs to
 * make better use of the L1 cache.
 */
/* #define USE_CACHE_ALIGNED 8	/* The alignment (in 4-byte words) */

typedef unsigned char u_char;
typedef unsigned long u_long;
typedef unsigned int u_int;
typedef unsigned short u_short;
typedef u_long caddr_t;

#include <Memory.h>
#include <stdlib.h>
#include <string.h>

#ifndef NULL
#define	NULL 0
#endif

static void morecore();

/*
 * The overhead on a block is at least 4 bytes.  When free, this space
 * contains a pointer to the next free block, and the bottom two bits must
 * be zero.  When in use, the first byte is set to MAGIC, and the second
 * byte is the size index.  The remaining bytes are for alignment.
 * If range checking is enabled then a second word holds the size of the
 * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
 * The order of elements is critical: ov_magic must overlay the low order
 * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
 */
union	overhead {
	union	overhead *ov_next;	/* when free */
	struct {
		u_char	ovu_magic0;	/* magic number */
		u_char	ovu_index;	/* bucket # */
		u_char	ovu_unused;	/* unused */
		u_char	ovu_magic1;	/* other magic number */
#ifdef RCHECK
		u_short	ovu_rmagic;	/* range magic number */
		u_long	ovu_size;	/* actual block size */
#endif
	} ovu;
#define	ov_magic0	ovu.ovu_magic0
#define	ov_magic1	ovu.ovu_magic1
#define	ov_index	ovu.ovu_index
#define	ov_rmagic	ovu.ovu_rmagic
#define	ov_size		ovu.ovu_size
#ifdef USE_CACHE_ALIGNED
	struct cachealigner {
		u_long	ovalign[USE_CACHE_ALIGNED];
	} ovu_aligner;
#endif /* USE_CACHE_ALIGN */
};

#define	MAGIC		0xef		/* magic # on accounting info */
#define RMAGIC		0x5555		/* magic # on range info */

#ifdef RCHECK
#define	RSLOP		sizeof (u_short)
#else
#define	RSLOP		0
#endif

#define OVERHEAD (sizeof(union overhead) + RSLOP)

/*
 * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
 * smallest allocatable block is 8 bytes.  The overhead information
 * precedes the data area returned to the user.
 */
#define	NBUCKETS 11
#define MAXMALLOC (1<<(NBUCKETS+2))
static	union overhead *nextf[NBUCKETS];

#ifdef MSTATS
/*
 * nmalloc[i] is the difference between the number of mallocs and frees
 * for a given block size.
 */
static	u_int nmalloc[NBUCKETS+1];
#include <stdio.h>
#endif

#if defined(DEBUG) || defined(RCHECK) || defined(DEBUG2)
#define	ASSERT(p)   if (!(p)) botch(# p)
#include <stdio.h>
static
botch(s)
	char *s;
{
	fprintf(stderr, "\r\nmalloc assertion botched: %s\r\n", s);
 	(void) fflush(stderr);		/* just in case user buffered it */
	abort();
}
#else
#define	ASSERT(p)
#endif

void *
malloc(nbytes)
	size_t nbytes;
{
  	register union overhead *op;
  	register long bucket;
	register unsigned amt;

	/*
	** First the simple case: we simple allocate big blocks directly
	*/
	if ( nbytes + OVERHEAD >= MAXMALLOC ) {
		op = (union overhead *)NewPtr(nbytes+OVERHEAD);
		if ( op == NULL )
			return NULL;
		op->ov_magic0 = op->ov_magic1 = MAGIC;
		op->ov_index = 0xff;
#ifdef MSTATS
 	 	nmalloc[NBUCKETS]++;
#endif
#ifdef RCHECK
		/*
		 * Record allocated size of block and
		 * bound space with magic numbers.
		 */
		op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
		op->ov_rmagic = RMAGIC;
  		*(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
#endif
		return (void *)(op+1);
	}
	/*
	 * Convert amount of memory requested into closest block size
	 * stored in hash buckets which satisfies request.
	 * Account for space used per block for accounting.
	 */
#ifndef RCHECK
	amt = 8;	/* size of first bucket */
	bucket = 0;
#else
	amt = 16;	/* size of first bucket */
	bucket = 1;
#endif
	while (nbytes + OVERHEAD > amt) {
		amt <<= 1;
		if (amt == 0)
			return (NULL);
		bucket++;
	}
#ifdef DEBUG2
	ASSERT( bucket < NBUCKETS );
#endif
	/*
	 * If nothing in hash bucket right now,
	 * request more memory from the system.
	 */
  	if ((op = nextf[bucket]) == NULL) {
  		morecore(bucket);
  		if ((op = nextf[bucket]) == NULL)
  			return (NULL);
	}
	/* remove from linked list */
  	nextf[bucket] = op->ov_next;
	op->ov_magic0 = op->ov_magic1 = MAGIC;
	op->ov_index = bucket;
#ifdef MSTATS
  	nmalloc[bucket]++;
#endif
#ifdef RCHECK
	/*
	 * Record allocated size of block and
	 * bound space with magic numbers.
	 */
	op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
	op->ov_rmagic = RMAGIC;
  	*(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
#endif
#ifdef VCHECK
	memset((char *)(op+1), 0x41, nbytes);
#endif
  	return ((char *)(op + 1));
}

/*
 * Allocate more memory to the indicated bucket.
 */
static void
morecore(bucket)
	int bucket;
{
  	register union overhead *op;
	register long sz;		/* size of desired block */
  	long amt;			/* amount to allocate */
  	int nblks;			/* how many blocks we get */

	/*
	 * sbrk_size <= 0 only for big, FLUFFY, requests (about
	 * 2^30 bytes on a VAX, I think) or for a negative arg.
	 */
	sz = 1 << (bucket + 3);
#ifdef DEBUG2
	ASSERT(sz > 0);
#endif
	amt = MAXMALLOC;
	nblks = amt / sz;
#ifdef DEBUG2
	ASSERT(nblks*sz == amt);
#endif
#ifdef USE_CACHE_ALIGNED
	op = (union overhead *)NewPtr(amt+4*USE_CACHE_ALIGNED);
#else
	op = (union overhead *)NewPtr(amt);
#endif
	/* no more room! */
  	if (op == NULL)
  		return;
#ifdef USE_CACHE_ALIGNED
#define ALIGN_MASK (4*USE_CACHE_ALIGNED-1)
	while ((long)op & ALIGN_MASK )
		op = (union overhead *)((long)op+1);
#endif /* USE_CACHE_ALIGNED */
	/*
	 * Add new memory allocated to that on
	 * free list for this hash bucket.
	 */
  	nextf[bucket] = op;
  	while (--nblks > 0) {
		op->ov_next = (union overhead *)((caddr_t)op + sz);
		op = (union overhead *)((caddr_t)op + sz);
  	}
  	op->ov_next = (union overhead *)NULL;
}

void
free(cp)
	void *cp;
{   
  	register long size;
	register union overhead *op;

  	if (cp == NULL)
  		return;
	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
#ifdef DEBUG
  	ASSERT(op->ov_magic0 == MAGIC);		/* make sure it was in use */
  	ASSERT(op->ov_magic1 == MAGIC);
#else
	if (op->ov_magic0 != MAGIC || op->ov_magic1 != MAGIC)
		return;				/* sanity */
#endif
#ifdef RCHECK
  	ASSERT(op->ov_rmagic == RMAGIC);
	ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
#endif
#ifdef VCHECK
	memset(cp, 43, op->ov_size);
#endif
  	size = op->ov_index;
  	if ( size == 0xff ) {
#ifdef MSTATS
		nmalloc[NBUCKETS]--;
#endif
  		DisposePtr((Ptr)op);
  		return;
  	}
  	ASSERT(size < NBUCKETS);
	op->ov_next = nextf[size];	/* also clobbers ov_magic */
  	nextf[size] = op;
#ifdef MSTATS
  	nmalloc[size]--;
#endif
}

void *
realloc(cp, nbytes)
	void *cp; 
	size_t nbytes;
{   
	int i;
	union overhead *op;
	int expensive;
	u_long maxsize;

  	if (cp == NULL)
  		return (malloc(nbytes));
	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
#ifdef DEBUG
  	ASSERT(op->ov_magic0 == MAGIC);		/* make sure it was in use */
  	ASSERT(op->ov_magic1 == MAGIC);
#else
	if (op->ov_magic0 != MAGIC || op->ov_magic1 != MAGIC)
		return NULL;				/* sanity */
#endif
#ifdef RCHECK
  	ASSERT(op->ov_rmagic == RMAGIC);
	ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
#endif
	i = op->ov_index;
	/*
	** First the malloc/copy cases
	*/
	expensive = 0;
	if ( i == 0xff ) {
		/* Big block. See if it has to stay big */
		if (nbytes+OVERHEAD > MAXMALLOC) {
			/* Yup, try to resize it first */
			SetPtrSize((Ptr)op, nbytes+OVERHEAD);
			if ( MemError() == 0 ) {
#ifdef RCHECK
				op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
				*(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
#endif
				return cp;
			}
			/* Nope, failed. Take the long way */
		}
		maxsize = GetPtrSize((Ptr)op);
		expensive = 1;
	} else {
		maxsize = 1 << (i+3);
		if ( nbytes + OVERHEAD > maxsize )
			expensive = 1;
		else if ( i > 0 && nbytes + OVERHEAD < (maxsize/2) )
			expensive = 1;
	}
	if ( expensive ) {
		void *newp;
		
		newp = malloc(nbytes);
		if ( newp == NULL ) {
			return NULL;
		}
		maxsize -= OVERHEAD;
		if ( maxsize < nbytes )
			nbytes = maxsize;
		memcpy(newp, cp, nbytes);
		free(cp);
		return newp;
	}
	/*
	** Ok, we don't have to copy, it fits as-is
	*/
#ifdef RCHECK
	op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
	*(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
#endif
	return(cp);
}


#ifdef MSTATS
/*
 * mstats - print out statistics about malloc
 * 
 * Prints two lines of numbers, one showing the length of the free list
 * for each size category, the second showing the number of mallocs -
 * frees for each size category.
 */
mstats(s)
	char *s;
{
  	register int i, j;
  	register union overhead *p;
  	int totfree = 0,
  	totused = 0;

  	fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
  	for (i = 0; i < NBUCKETS; i++) {
  		for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  			;
  		fprintf(stderr, " %d", j);
  		totfree += j * (1 << (i + 3));
  	}
  	fprintf(stderr, "\nused:\t");
  	for (i = 0; i < NBUCKETS; i++) {
  		fprintf(stderr, " %d", nmalloc[i]);
  		totused += nmalloc[i] * (1 << (i + 3));
  	}
  	fprintf(stderr, "\n\tTotal small in use: %d, total free: %d\n",
	    totused, totfree);
	fprintf(stderr, "\n\tNumber of big (>%d) blocks in use: %d\n", MAXMALLOC, nmalloc[NBUCKETS]);
}
#endif