* Copyright (c) 1980 Regents of the University of California.
* All rights reserved. The Berkeley software License Agreement
* specifies the terms and conditions for redistribution.
static char sccsid
[] = "@(#)malloc.c 5.1 (Berkeley) %G%";
* malloc.c (Caltech) 2/21/82
* Chris Kingsley, kingsley@cit-20.
* 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. In this
* implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
* This is designed for use in a program that uses vast quantities of memory,
* but bombs when it runs out.
* 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 and the size of the block fits
* in two bytes, then the top two bytes hold the size of the requested block
* plus the range checking words, and the header word MINUS ONE.
union overhead
*ov_next
; /* when free */
u_char ovu_magic
; /* magic number */
u_char ovu_index
; /* bucket # */
u_int ovu_size
; /* actual block size */
u_char ovu_magic
; /* magic number */
u_char ovu_index
; /* bucket # */
u_short ovu_rmagic
; /* range magic number */
#define ov_magic ovu.ovu_magic
#define ov_index ovu.ovu_index
#define ov_rmagic ovu.ovu_rmagic
#define ov_size ovu.ovu_size
#define MAGIC 0xef /* magic # on accounting info */
#define RMAGIC 0x5555 /* magic # on range info */
#define RSLOP sizeof (u_short)
* 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.
static union overhead
*nextf
[NBUCKETS
];
static int pagesz
; /* page size */
static int pagebucket
; /* page size bucket */
* nmalloc[i] is the difference between the number of mallocs and frees
* for a given block size.
static u_int nmalloc
[NBUCKETS
];
#define ASSERT(p) if (!(p)) botch("p")
printf("assertion botched: %s\n", s
);
register union overhead
*op
;
register unsigned amt
, n
;
* First time malloc is called, setup page size and
* align break pointer so all data will be page aligned.
pagesz
= n
= getpagesize();
op
= (union overhead
*)sbrk(0);
n
= n
- sizeof (*op
) - ((int)op
& (n
- 1));
if (sbrk(n
) == (char *)-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.
if (nbytes
<= (n
= pagesz
- sizeof (*op
) - RSLOP
)) {
amt
= 8; /* size of first bucket */
amt
= 16; /* size of first bucket */
n
= -(sizeof (*op
) + RSLOP
);
while (nbytes
> amt
+ n
) {
* If nothing in hash bucket right now,
* request more memory from the system.
if ((op
= nextf
[bucket
]) == NULL
) {
if ((op
= nextf
[bucket
]) == NULL
)
/* remove from linked list */
nextf
[bucket
] = op
->ov_next
;
* Record allocated size of block and
* bound space with magic numbers.
op
->ov_size
= (nbytes
+ RSLOP
- 1) & ~(RSLOP
- 1);
*(u_short
*)((caddr_t
)(op
+ 1) + op
->ov_size
) = RMAGIC
;
return ((char *)(op
+ 1));
* Allocate more memory to the indicated bucket.
register union overhead
*op
;
register int sz
; /* size of desired block */
register int amt
; /* amount to allocate */
register int nblks
; /* how many blocks we get */
op
= (union overhead
*)sbrk(amt
);
* Add new memory allocated to that on
* free list for this hash bucket.
op
->ov_next
= (union overhead
*)((caddr_t
)op
+ sz
);
op
= (union overhead
*)((caddr_t
)op
+ sz
);
register union overhead
*op
;
op
= (union overhead
*)((caddr_t
)cp
- sizeof (union overhead
));
ASSERT(op
->ov_magic
== MAGIC
); /* make sure it was in use */
if (op
->ov_magic
!= MAGIC
)
ASSERT(op
->ov_rmagic
== RMAGIC
);
ASSERT(*(u_short
*)((caddr_t
)(op
+ 1) + op
->ov_size
) == RMAGIC
);
op
->ov_next
= nextf
[size
];
* When a program attempts "storage compaction" as mentioned in the
* old malloc man page, it realloc's an already freed block. Usually
* this is the last block it freed; occasionally it might be farther
* back. We have to search all the free lists for the block in order
* to determine its bucket: 1st we make one pass thru the lists
* checking only the first block in each; if that fails we search
* ``realloc_srchlen'' blocks in each list for a match (the variable
* is extern so the caller can modify it). If that fails we just copy
* however many bytes was given to realloc() and hope it's not huge.
int realloc_srchlen
= 4; /* 4 should be plenty, -1 =>'s whole list */
op
= (union overhead
*)((caddr_t
)cp
- sizeof (union overhead
));
if (op
->ov_magic
== MAGIC
) {
* Already free, doing "compaction".
* Search for the old block of memory on the
* free list. First, check the most common
* case (last element free'd), then (this failing)
* the last ``realloc_srchlen'' items free'd.
* If all lookups fail, then assume the size of
* the memory block being realloc'd is the
if ((i
= findbucket(op
, 1)) < 0 &&
(i
= findbucket(op
, realloc_srchlen
)) < 0)
i
= 1; /* smallest possible w/ RCHECK */
onb
-= sizeof (*op
) + RSLOP
;
onb
+= pagesz
- sizeof (*op
) - RSLOP
;
/* avoid the copy if same size block */
i
-= sizeof (*op
) + RSLOP
;
i
+= pagesz
- sizeof (*op
) - RSLOP
;
if (nbytes
<= onb
&& nbytes
> i
) {
op
->ov_size
= (nbytes
+ RSLOP
- 1) & ~(RSLOP
- 1);
*(u_short
*)((caddr_t
)(op
+ 1) + op
->ov_size
) = RMAGIC
;
if ((res
= malloc(nbytes
)) == NULL
)
if (cp
!= res
) /* common optimization */
bcopy(cp
, res
, (nbytes
< onb
) ? nbytes
: onb
);
* Search ``srchlen'' elements of each free list for a block whose
* header starts at ``freep''. If srchlen is -1 search the whole list.
* Return bucket number, or -1 if not found.
findbucket(freep
, srchlen
)
register union overhead
*p
;
for (i
= 0; i
< NBUCKETS
; i
++) {
for (p
= nextf
[i
]; p
&& j
!= srchlen
; p
= p
->ov_next
) {
* 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.
register union overhead
*p
;
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 in use: %d, total free: %d\n",