* Copyright (c) 1983 Regents of the University of California.
* Redistribution and use in source and binary forms are permitted
* provided that the above copyright notice and this paragraph are
* duplicated in all such forms and that any documentation,
* advertising materials, and other materials related to such
* distribution and use acknowledge that the software was developed
* by the University of California, Berkeley. The name of the
* University may not be used to endorse or promote products derived
* from this software without specific prior written permission.
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
* WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid
[] = "@(#)malloc.c 5.7 (Berkeley) %G%";
#endif /* LIBC_SCCS and not lint */
* 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-10) bytes long.
* This is designed for use in a virtual memory environment.
* 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
*ov_next
; /* when free */
u_char ovu_magic
; /* magic number */
u_char ovu_index
; /* bucket # */
u_short ovu_rmagic
; /* range magic number */
u_int ovu_size
; /* actual block size */
#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
];
#if defined(DEBUG) || defined(RCHECK)
#define ASSERT(p) if (!(p)) botch("p")
fprintf(stderr
, "\r\nassertion botched: %s\r\n", s
);
(void) fflush(stderr
); /* just in case user buffered it */
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 */
int 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.
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
]; /* also clobbers ov_magic */
* 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
* largest possible (so that all "nbytes" of new
* memory are copied into). Note that this could cause
* a memory fault if the old area was tiny, and the moon
* is gibbous. However, that is very unlikely.
if ((i
= findbucket(op
, 1)) < 0 &&
(i
= findbucket(op
, realloc_srchlen
)) < 0)
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 if "compacting" */
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",