* Copyright (c) 1983, 1991 The Regents of the University of California.
* %sccs.include.redist.c%
static char sccsid
[] = "@(#)alloc.c 5.6 (Berkeley) %G%";
* tc.alloc.c from 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.
char *memtop
= NULL
; /* PWP: top of current memory */
char *membot
= NULL
; /* PWP: bottom of allocatable memory */
typedef unsigned char U_char
; /* we don't really have signed chars */
typedef unsigned int U_int
;
typedef unsigned short U_short
;
* 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.
* SunOS localtime() overwrites the 9th byte on an 8 byte malloc()....
* So we align to 16 bytes...
#define ALIGN(a) (((a) + ROUNDUP) & ~ROUNDUP)
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 0xfd /* 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 CHECK(a, str, p) \
xprintf("memtop = %lx membot = %lx.\n", memtop, membot); \
#define CHECK(a, str, p) \
xprintf("memtop = %lx membot = %lx.\n", memtop, membot); \
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
nbytes
= ALIGN(ALIGN(sizeof(union overhead
)) + nbytes
+ RSLOP
);
shiftr
= (nbytes
- 1) >> 2;
/* apart from this loop, this is O(1) */
* If nothing in hash bucket right now, request more memory from the
if (nextf
[bucket
] == NULL
)
if ((p
= (union overhead
*) nextf
[bucket
]) == NULL
) {
xprintf("nbytes=%d: Out of memory\n", nbytes
);
/* 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 ((ptr_t
) (((caddr_t
) p
) + ALIGN(sizeof(union overhead
))));
* 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 make getpageize
op
= (union overhead
*) sbrk(0);
memtop
= (char *) sbrk(1024 - ((int) op
& 0x3ff));
memtop
+= 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 */
memtop
= (char *) sbrk(1 << rnu
); /* PWP */
op
= (union overhead
*) memtop
;
* Round up to minimum allocation size boundary and deduct from block count
if (((U_int
) op
) & ROUNDUP
) {
op
= (union overhead
*) (((U_int
) op
+ (ROUNDUP
+ 1)) & ~ROUNDUP
);
* 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
;
CHECK(!memtop
|| !membot
, "free(%lx) called before any allocations.", cp
);
CHECK(cp
> (ptr_t
) memtop
, "free(%lx) above top of memory.", cp
);
CHECK(cp
< (ptr_t
) membot
, "free(%lx) above top of memory.", cp
);
op
= (union overhead
*) (((caddr_t
) cp
) - ALIGN(sizeof(union overhead
)));
CHECK(op
->ov_magic
!= MAGIC
, "free(%lx) bad block.", cp
);
CHECK(*(U_int
*) ((caddr_t
) op
+ op
->ov_size
+ 1 - RSLOP
) != RMAGIC
,
"free(%lx) bad range check.", cp
);
CHECK(op
->ov_index
>= NBUCKETS
, "free(%lx) bad block index.", cp
);
op
->ov_next
= nextf
[size
];
scp
= cp
= (char *) xmalloc((size_t) i
);
* 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
) - ALIGN(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 smallest
if ((i
= findbucket(op
, 1)) < 0 &&
(i
= findbucket(op
, realloc_srchlen
)) < 0)
onb
= ALIGN(nbytes
+ ALIGN(sizeof(union overhead
)) + RSLOP
);
/* avoid the copy if same size block */
if (was_alloced
&& (onb
< (1 << (i
+ 3))) && (onb
>= (1 << (i
+ 2))))
if ((res
= malloc(nbytes
)) == NULL
)
if (cp
!= res
) /* common optimization */
* 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
) {
** ``Protected versions'' of malloc, realloc, calloc, and free
** 3. realloc(0, n) is bad
** 4. realloc(n, 0) is bad
** Also we call our error routine if we run out of memory.
if ((ptr
= malloc(n
)) == (ptr_t
) 0) {
if ((ptr
= (p
? realloc(p
, n
) : malloc(n
))) == (ptr_t
) 0) {
if ((ptr
= malloc(n
)) == (ptr_t
) 0) {
* 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
;
int totfree
= 0, totused
= 0;
xprintf("csh current memory allocation:\nfree:\t");
for (i
= 0; i
< NBUCKETS
; i
++) {
for (j
= 0, p
= nextf
[i
]; p
; p
= p
->ov_next
, j
++);
totfree
+= j
* (1 << (i
+ 3));
for (i
= 0; i
< NBUCKETS
; i
++) {
xprintf(" %4d", nmalloc
[i
]);
totused
+= nmalloc
[i
] * (1 << (i
+ 3));
xprintf("\n\tTotal in use: %d, total free: %d\n",
xprintf("\tAllocated memory from 0x%lx to 0x%lx. Real top at 0x%lx\n",
membot
, memtop
, (char *) sbrk(0));
xprintf("Allocated memory from 0x%lx to 0x%lx (%ld).\n",
membot
, memtop
= (char *) sbrk(0), memtop
- membot
);