jpl@allegra.UUCP (John P. Linderman) (11/30/86)
The version of malloc that is distributed with 4.3 BSD has changed in
several ways from the 4.2 version. Several old bugs have been
repaired, several new features and new bugs have been added.
A quick summary of the major problems, in decreasing order of severity:
1) Large free blocks will not be split to allocate smaller blocks,
even if that means returning NULL in response to a request.
2) Malloc can interact badly with sbrk, resulting in storage
allocations aligned on odd byte boundaries.
3) 512-byte allocations are only about 25% efficient in space.
The good news is that I have fixed these (and several other) problems,
and have been running the fixed version of malloc since early September,
with no sign of problems. The bad news is that the changes were rather
substantial. That means that a) ucb may (quite justifiably) be less than
eager to buy them back, and b) I can't post the diffs because it would
amount to posting the Berkeley malloc. There's enough of the original
source in my version that I dare not post just my version, lest the
Berkeley folks (again, justifiably) get upset. I have sent my version
to Berkeley, and they are welcome to redistribute it. I'm sorry I
can't be more helpful about this. Such is legal life.
The remainder of this article is a more detailed description of some
of the problems discovered and fixed, and some test programs and data
to demonstrate that the problems are real, not imagined. If you think
the problems are worth correcting, DON'T send mail to me. The logistics
will have to be worked out by Berkeley.
John P. Linderman Space Cadet allegra!jpl
Lint complains about the 4.3 malloc. The findbucket() routine that is
associated with reallocating freed blocks [sic] returns -1 to indicate
that the freed block wasn't found. The return value is assigned to an
unsigned integer, so a return value less than 0 cannot be detected.
The -1 return will turn into a VERY large and thoroughly meaningless
bucket index. The fact that this has not caused problems suggests that
the feature is not often used, a tribute to the good taste of 4.3
programmers. Forcing ``compaction'' is pretty much a no-op on every
malloc implementation I know of, and doing it by the artifice of
reallocating freed storage is unspeakable (even if documented). I have
simplified the compaction code. It will take longer, but it will work
correctly. The world would be a better place if manipulating freed
storage were disallowed altogether.
The 4.3 malloc attempts to align large allocations on page boundaries.
This is a feature. The kernel can do I/O operations into page-aligned
areas by simply fiddling with page tables. The alignment is
established on the first call to malloc, and is preserved by doing all
subsequent sbrk allocations in page multiples. This is a bug. If the
user does an sbrk allocation that is NOT a multiple of a page, all
subsequent malloc allocations will be aligned OFF page boundaries. If
the user does an sbrk of an odd number of bytes, all subsequent malloc
allocations will be aligned on odd byte boundaries. I have changed the
code to check for correct allocation each time malloc must do an sbrk.
The 4.2 malloc kept internal allocation buckets whose sizes were powers
of 2. A small amount of bookkeeping overhead was added to user
requests, and the resulting space was allocated from the smallest
bucket that could satisfy it. If the user asked for an area whose size
was a power of 2, like a stdio buffer, the bookkeeping overhead made
the request just a bit larger, and the request had to be satisfied out
of a block that was nearly twice the size the user asked for. Large
allocations in the 4.3 malloc come out of blocks that are a power of 2,
plus one page. Thus, requests for a power of 2 bytes waste only a
fraction of a page. This is a feature. Unfortunately, the bucket size
calculations are a little peculiar. A request for 512 bytes will come
out of a 2048-byte area, surpassing 4.2's unenviable record of 50%
storage waste. It is difficult to change the allocation policy, both
because it is slightly cryptic, and because it appears in several
routines. (Its appearance in the mstats routine is subtly different
from its appearance elsewhere, so if you allocate and then free 2000
bytes, mstats will tell you 1024 bytes are free.) I have changed the
allocation policy to create a 1024-byte bucket. I have also
consolidated the allocation policy into a single routine, so it can be
more easily modified. Mstats, using this policy routine, now reports
used and free figures that bear some relation to reality.
Both 4.2 and 4.3 malloc will return NULL if an sbrk fails, even if
there are large free blocks available that could satisfy the request.
I posted a fix for the 4.2 malloc to netnews. The new bucket sizes
make that fix unusable, so I have fixed the 4.3 version as well. The
fix is remarkably resistent to changes in bucket allocation policies,
and is quite conservative of large blocks. I'm rather proud of it,
even if most of the nice features were unintentional.
If a realloc of an allocated block fails under 4.3, the block is
freed as an unwanted side-effect. This has been fixed. If the
allocation fails, the original block remains allocated.
The test program and data that follow demonstrate a number of these
bugs. The scripts assume that both talloc.c and malloc.c have been
compiled with -DMSTATS.
# To unbundle, delete any lines before this one and sh this file.
echo unbundling talloc.c
#################### talloc.c Tue Sep 2 13:48:43 EDT 1986 ####################
sed -e 's/.//' > talloc.c <<'John P. Linderman allegra!jpl MH3D-435 x6427'
X#include <stdio.h>
X#include <ctype.h>
X
X#ifndef ASLOTS
X#define ASLOTS 1000
X#endif
X
Xchar *Me;
X
Xstruct {
X char *p;
X int z;
X} a[ASLOTS];
X
X#define SKIP(p) while (isspace(*p)) p++
X
Xchar *
Xcvnum(p, np)
X register char *p;
X int *np;
X{
X register int n;
X
X SKIP(p);
X if (isdigit(*p))
X for (n = 0; isdigit(*p);)
X n = 10 * n + *p++ - '0';
X else n = -1;
X *np = n;
X return (p);
X}
X
Xint
Xfindex()
X{
X register int i;
X
X for (i = 0; i < ASLOTS; i++) {
X if (a[i].z == 0)
X return (i);
X }
X (void) fprintf(stderr, "%s: %s %s %d\n",
X Me,
X "Pointer table full -- do some frees",
X "or recompile with ASLOTS >",
X ASLOTS);
X return (-1);
X}
X
Xmain(argc, argv)
X int argc;
X char **argv;
X{
X register char *p;
X register int i;
X char buf[256], *malloc(), *realloc(), *gets();
X int n, last = 4000000;
X extern int getpagesize();
X
X Me = argv[0];
X while (gets(buf)) {
X p = buf;
X SKIP(p);
X switch (*p) {
X case 'a': /* allocate: n, or last allocation; report index */
X if ((i = findex()) < 0) continue;
X (void) cvnum(p+1, &n);
X if (n > 0) last = n;
X if (p = malloc(last)) {
X (void) printf("%d: %d bytes at %#x\n", i, last, p);
X a[i].p = p;
X a[i].z = last;
X } else {
X (void) printf("Out of space looking for %d bytes\n", last);
X }
X break;
X case 'b':
X (void) cvnum(p+1, &n);
X if (n > 0) last = n;
X (void) printf("sbrk(%d) returned %#x\n", last, sbrk(last));
X break;
X case 'f':
X (void) cvnum(p+1, &n);
X i = n;
X if ((i < 0) || (i >= ASLOTS) || (a[i].z == 0)) {
X (void) printf("Slot invalid or already free\n");
X } else {
X free(p = a[i].p);
X (void) printf("%d: %d bytes at %#x\n", i, a[i].z, p);
X a[i].z = 0;
X a[i].p = NULL;
X }
X break;
X case 'r':
X p = cvnum(p+1, &n);
X i = n;
X if ((i < 0) || (i >= ASLOTS) || (a[i].z == 0)) {
X (void) printf("Slot invalid or free\n");
X } else {
X (void) cvnum(p, &n);
X if (n > 0) last = n;
X if (p = realloc(a[i].p, last)) {
X (void) printf("%d: %d=>%d bytes from %#x to %#x\n",
X i, a[i].z, last, a[i].p, p);
X a[i].p = p;
X a[i].z = last;
X } else {
X (void) printf("Out of space looking for %d bytes\n", last);
X }
X }
X break;
X case 'p':
X i = getpagesize();
X (void) printf("Page size is %d(%#x)\n", i, i);
X break;
X case 's':
X for (i = 0; i < ASLOTS; i++) {
X if (a[i].z) {
X (void) printf("%7d: %9d bytes at %#x\n",
X i, a[i].z, a[i].p);
X }
X }
X break;
X#ifdef MSTATS
X case 'm':
X (void) mstats(p+1);
X break;
X#endif
X case 'q':
X exit(0);
X case '#':
X (void) printf("%s\n", buf);
X break;
X case '?':
X (void) printf("a [N] => allocate N bytes, report index\n");
X (void) printf("b [N] => sbrk N bytes, report address\n");
X (void) printf("f index => free space at index\n");
X#ifdef MSTATS
X (void) printf("m [title] => print malloc statistics\n");
X#endif
X (void) printf("p => report page size\n");
X (void) printf("r index [N] => reallocate N bytes at index\n");
X (void) printf("s => print summary of allocated storage\n");
X (void) printf("q => quit\n");
X (void) printf("# => echo the input line\n");
X (void) printf("? => print this helpful summary\n");
X break;
X default:
X (void) fprintf(stderr, "%s: %s %s\n",
X Me, "Unrecognized command --",
X "enter ? for help");
X }
X }
X}
John P. Linderman allegra!jpl MH3D-435 x6427
echo unbundling testalign
#################### testalign Tue Sep 2 13:48:44 EDT 1986 ####################
sed -e 's/.//' > testalign <<'John P. Linderman allegra!jpl MH3D-435 x6427'
X# Show how user sbrk's interact with malloc alignment.
X# The 4.3 malloc only adjusts alignment when it is first called.
X# If the user invokes sbrk thereafter, alignment can get wierd.
X#
X# First, get a couple large chunks, which should be page aligned
Xp
Xa 4096
Xa 4096
X# Now, sbrk a single byte, and then see how other chunks are aligned
Xb 1
Xa 4096
Xa 4096
Xs
Xq
John P. Linderman allegra!jpl MH3D-435 x6427
echo unbundling testfunny
#################### testfunny Tue Sep 2 13:48:44 EDT 1986 ####################
sed -e 's/.//' > testfunny <<'John P. Linderman allegra!jpl MH3D-435 x6427'
X# Demonstrate funny bucket with 4.3 allocator.
X# There are two problems here:
X# 1) Because of the way bucket sizes are determined in the 4.3 malloc,
X# one bucket gets blocks with sizes (after malloc overhead) from
X# 512 bytes through 2048 bytes. That's pretty poor storage
X# efficiency for the 512-byte chunks.
X# 2) Mstats doesn't calculate block sizes in the same way that malloc
X# does. It's wrong about the size of the funny bucket. It never takes
X# the extra page overhead into consideration, either.
Xm Initial configuration
X# Allocate 2000 bytes, free it and see how much space mstats reports.
Xa2000
Xf0
Xm 2000 bytes allocated and freed
X# Reallocate the 2000 bytes, then allocate 512, and see if they end
X# up in the same bucket
Xa2000
Xa 512
Xm 2000 and 512 bytes allocated
Xq
John P. Linderman allegra!jpl MH3D-435 x6427
echo unbundling testrealloc
#################### testrealloc Tue Sep 2 13:48:45 EDT 1986 ####################
sed -e 's/.//' > testrealloc <<'John P. Linderman allegra!jpl MH3D-435 x6427'
X# If an attempt to reallocate a busy block fails, the block will
X# be freed as an (undesirable) side-effect
X#
X# First, run ourselves out of space
Xa1000000000
Xa 500000000
Xa 250000000
Xa 125000000
Xa 64000000
Xa 32000000
Xa 16000000
Xa 8000000
Xa 4000000
Xa 2000000
Xa 1000000
Xa 500000
Xa 256000
Xa 128000
Xa 65536
Xa 32768
Xa 16384
Xa 8192
Xa 4096
Xa 2048
Xa 1024
Xa 512
Xa 256
Xa 128
Xa 64
Xa 32
Xa 16
Xa 8
Xa 4
Xa 2
Xa 1
Xm After running out of space
X# Now, attempt to reallocate the biggest block and make it even bigger
Xr 0 2000000000
Xm After failing to reallocate
Xq
John P. Linderman allegra!jpl MH3D-435 x6427
echo unbundling testsalvage
#################### testsalvage Tue Sep 2 13:48:46 EDT 1986 ####################
sed -e 's/.//' > testsalvage <<'John P. Linderman allegra!jpl MH3D-435 x6427'
X# The 4.3 malloc will not split up a free block, even if it means
X# returning NULL from malloc.
X#
X# First, run ourselves out of space
Xa1000000000
Xa 500000000
Xa 250000000
Xa 125000000
Xa 64000000
Xa 32000000
Xa 16000000
Xa 8000000
Xa 4000000
Xa 2000000
Xa 1000000
Xa 500000
Xa 256000
Xa 128000
Xa 65536
Xa 32768
Xa 16384
Xa 8192
Xa 4096
Xa 2048
Xa 1024
Xa 512
Xa 256
Xa 128
Xa 64
Xa 32
Xa 16
Xa 8
Xa 4
Xa 2
Xa 1
X# Now, free the biggest block, and try for one more byte
Xf0
Xm After freeing biggest block
Xa
Xm After trying to allocate another byte
Xq
John P. Linderman allegra!jpl MH3D-435 x6427
echo To produce a test driver,
echo " cc -O -DMSTATS [-DRCHECK] -o talloc talloc.c /usr/src/lib/libc/gen/malloc.c"
echo To exercise it
echo ' for i in test*'
echo ' do ./talloc < $i'
echo ' done'
exit 0