4.2 malloc bug and fix

[John P. Linderman]

>> ...  Another ``gotcha'' to beware of is that space, once allocated,
>> is never broken into smaller pieces. [...] Dunno if this is fixed
>> under 4.3.
>
>I doubt it will be; it has not yet been done.  It might create yet
>another ``gotcha'', however, as coalescing smaller blocks is fairly
>tricky.
>-- 
>In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 4251)

I agree that the 4.2 malloc is in need of a major rewrite, but it's
easy enough to fix the problem of refusing to turn over 8 bytes of
memory when it has a quarter-meg in its hip pocket.  The changes below
apply to the situation when malloc would have given up and returned
NULL, so even though they are lightly tested (see below), they are
probably better than the alternative.  In essence, when sbrk fails,
the changed code looks for a larger block to split before giving up.

TWO WARNINGS!!!  First, this fix is like trimming a hangnail on a
person who has just been run over by a truck... the real problems
remain to be addressed.  Second, when I wrote an interactive routine
to test the fixes, they worked just fine on a lightly loaded machine,
but the kernel panicked twice on a heavily loaded system.  Since I
was running my test program during both panics, I'm assuming I'm at
fault, and I'm now plowing through the crash dumps to see what was
the matter.  If I uncover something interesting, I'll report it,
but I hate to crash our machines, so the code remains only lightly
tested.

The diffs follow.  Bug reports will no doubt follow shortly thereafter.

John P. Linderman  Space Cadet  allegra!jpl

*** malloc.c	Tue Sep 17 08:58:29 1985
--- /usr/src/lib/libc/gen/malloc.c	Mon Oct 15 11:10:58 1984
***************
*** 160,182
  		rnu = bucket;
  	op = (union overhead *)sbrk(1 << rnu);
  	/* no more room! */
!   	if ((int)op == -1) {
! 		for (rnu=bucket; rnu < NBUCKETS; rnu++) {
! 			if (nextf[rnu]) break;
! 		}
! 		if (rnu >= NBUCKETS)
! 			return;
! 		/* Split into halves until bucket-sized */
! 		op = nextf[rnu];
! 		nextf[rnu] = op->ov_next;
! 		while (--rnu > bucket) {
! 			siz = 1 << (rnu + 3);
! 			op->ov_next = nextf[rnu]; /* == NULL */
! 			nextf[rnu] = op;
! 			op = (union overhead *)((caddr_t) op + siz);
! 		}
! 		nblks = 2;
! 	}
  	/*
  	 * Round up to minimum allocation size boundary
  	 * and deduct from block count to reflect.

--- 160,167 -----
  		rnu = bucket;
  	op = (union overhead *)sbrk(1 << rnu);
  	/* no more room! */
!   	if ((int)op == -1)
!   		return;
  	/*
  	 * Round up to minimum allocation size boundary
  	 * and deduct from block count to reflect.
***************
*** 195,201
  		op->ov_next = (union overhead *)((caddr_t)op + siz);
  		op = (union overhead *)((caddr_t)op + siz);
    	}
- 	op->ov_next = NULL;
  }
  
  free(cp)

--- 180,185 -----
  		op->ov_next = (union overhead *)((caddr_t)op + siz);
  		op = (union overhead *)((caddr_t)op + siz);
    	}
  }