jpl@allegra.UUCP (John P. Linderman) (03/03/84)
To quote the manual page for malloc:
`Realloc' changes the size of the block pointed to by `ptr' to `size'
bytes and returns a pointer to the (possibly moved) block. The
contents will be unchanged up to the lesser of the new and old sizes.
In order to be compatible with older versions, `realloc' also works
if `ptr' points to a block freed since the last call of `malloc',
`realloc' or `calloc'; sequences of `free', `malloc' and `realloc'
were previously used to attempt storage compaction. This procedure
is no longer recommended.
It certainly isn't recommended. It doesn't work if there have been too
many calls to free() before the call to realloc(), as the following test
program demonstrates.
Repeat by:
Run this under 4.2:
#include <stdio.h>
main()
{
char *q, *p[20], *malloc(), *realloc();
int i;
for (i = 0; i < 20; i++) p[i] = malloc(10);
q = p[0];
for (i = 0; i < 10; *q++ = ++i);
q = p[0];
for (i = 0; i < 10; i++) printf("%d ", *q++);
printf("\n");
for (i = 0; i < 20; i++) free(p[i]);
q = realloc(p[0], 20);
for (i = 0; i < 10; i++) printf("%d ", *q++);
printf("\n");
}
The output will look like
1 2 3 4 5 6 7 8 9 10
1 2 3 4 0 0 0 0 0 0
Only the first four characters of p[0] are unchanged, not the original
10 bytes, as advertised.
Fix by:
The simplest fix is to change the initialization of realloc_srchlen in
/usr/src/lib/lic/gen/malloc.c from
int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */
to
int realloc_srchlen = -1; /* Let's be right, not fast: look everywhere */
The problems arise because realloc() tells findbucket() to look for
the freed block only among the first realloc_srchlen items in the
free chains, and when findbucket() fails to find it, realloc()
assumes the freed block was of minimal size, and ends up copying
only the first few bytes, regardless of the original size. The
suggested fix will cause findbucket() to find the free block and
use the correct size if it is found, defaulting to the minimum
size only if the block doesn't appear on the free list at all.
Comments (exercising great restraint to avoid undue sarcasm):
The new malloc is very conservative of cycles and very profligate
with space. If you allocate blocks whose sizes are exact powers
of 2, you'll get approximately 50% storage efficiency. If you
allocate a megabyte for temporary storage, then free it when you
are done, you'll never use that space unless you allocate another
area of comparable size.
There is a tolerable amount of dead code in the routine, considering
the preoccupation with efficiency. For example, in morecore(), one finds
rnu = (bucket <= 8) ? 11 : bucket + 3;
nblks = 1 << (rnu - (bucket + 3)); /* how many blocks to get */
if (rnu < bucket)
rnu = bucket;
Now,
(bucket <= 8) => (rnu == 11) => (rnu > bucket)
(bucket > 8) => (rnu == (bucket + 3)) => (rnu > bucket)
so the `if' is always false.
A little later in the same routine, one finds
/*
* Round up to minimum allocation size boundary
* and deduct from block count to reflect.
*/
if ((int)op & 7) {
op = (union overhead *)(((int)op + 8) &~ 7);
nblks--;
}
Fortunately, the code earlier in the routine ensures that this
conditional is also always false. If it were true, the size of
the area at op might no longer be large enough after rounding op
up, and an area of insufficient size could be returned.
On the other hand, morecore should (but doesn't) end with a
op->ov_next = NULL;
since sbrk() doesn't promise to clear the new space to 0's,
but malloc relies on the free chains being terminated by
NULL pointers.
John P. Linderman Space Cadet allegra!jplguido@mcvax.UUCP (Guido van Rossum) (03/05/84)
I generally agree with your evaluation of 4.2 malloc. However I think it is not fair to blame the author for the fact that realloc_srchlen is initialized to 4 rather than -1. After all it is a global variable, so those programs which use memory compaction (there can't be many, given the obscure description of this feature in the V7 manual) can be fixed quite easily to set it to -1 at initialization time. Of course, the length of your article probably reflects the time you spent to find the bug -- maybe you had been better off when realloc returned (char*)NULL if it can't find the original pointer. This should be a minor change. Guido (oh, and change the manual page, too) van Rossum, CWI, Amsterdam guido @ mcvax