static char sccsid
[] = "@(#)malloc.c 4.3 (Berkeley) 9/16/83";
* 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_short ovu_size
; /* actual block size */
u_int ovu_rmagic
; /* range magic number */
#define ov_magic ovu.ovu_magic
#define ov_index ovu.ovu_index
#define ov_size ovu.ovu_size
#define ov_rmagic ovu.ovu_rmagic
#define MAGIC 0xff /* magic # on accounting info */
#define RMAGIC 0x55555555 /* magic # on range info */
#define RSLOP sizeof (u_int)
* 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
];
* 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"); else
printf("assertion botched: %s\n", s
);
register unsigned nbytes
;
register union overhead
*p
;
register unsigned shiftr
;
* Convert amount of memory requested into
* closest block size stored in hash buckets
* which satisfies request. Account for
* space used per block for accounting.
nbytes
+= sizeof (union overhead
) + RSLOP
;
nbytes
= (nbytes
+ 3) &~ 3;
shiftr
= (nbytes
- 1) >> 2;
/* apart from this loop, this is O(1) */
* If nothing in hash bucket right now,
* request more memory from the system.
if (nextf
[bucket
] == NULL
)
if ((p
= (union overhead
*)nextf
[bucket
]) == NULL
)
/* remove from linked list */
nextf
[bucket
] = nextf
[bucket
]->ov_next
;
* Record allocated size of block and
* bound space with magic numbers.
*((u_int
*)((caddr_t
)p
+ nbytes
- RSLOP
)) = RMAGIC
;
return ((char *)(p
+ 1));
* Allocate more memory to the indicated bucket.
register union overhead
*op
;
register int rnu
; /* 2^rnu bytes will be requested */
register int nblks
; /* become nblks blocks of the desired size */
* Insure memory is allocated
* on a page boundary. Should
op
= (union overhead
*)sbrk(0);
sbrk(1024 - ((int)op
& 0x3ff));
/* take 2k unless the block is bigger than that */
rnu
= (bucket
<= 8) ? 11 : bucket
+ 3;
nblks
= 1 << (rnu
- (bucket
+ 3)); /* how many blocks to get */
op
= (union overhead
*)sbrk(1 << rnu
);
* Round up to minimum allocation size boundary
* and deduct from block count to reflect.
op
= (union overhead
*)(((int)op
+ 8) &~ 7);
* Add new memory allocated to that on
* free list for this hash bucket.
op
->ov_next
= (union overhead
*)((caddr_t
)op
+ siz
);
op
= (union overhead
*)((caddr_t
)op
+ siz
);
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_int
*)((caddr_t
)op
+ op
->ov_size
+ 1 - RSLOP
) == RMAGIC
);
ASSERT(op
->ov_index
< NBUCKETS
);
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)
onb
= (1 << (i
+ 3)) - sizeof (*op
) - RSLOP
;
/* avoid the copy if same size block */
nbytes
<= onb
&& nbytes
> (onb
>> 1) - sizeof(*op
) - RSLOP
)
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",