bug in realloc in 4.2 version of malloc

[John P. Linderman]

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!jpl