--- ray/src/common/malloc.c	1990/09/25 17:14:04	1.1
+++ ray/src/common/malloc.c	1990/09/26 08:26:11	1.4
@@ -7,11 +7,14 @@ static char SCCSid[] = "$SunId$ LBL";
 /*
  * Fast malloc for memory hogs and VM environments.
  * Performs a minimum of searching through free lists.
- * bmalloc() doesn't keep track of free lists -- it's basically
- *	just a buffered call to sbrk().
- * bfree() puts memory from any source into malloc() free lists.
  * malloc(), realloc() and free() use buckets
  *	containing blocks in powers of two, similar to CIT routines.
+ * bfree() puts memory from any source into malloc free lists.
+ * bmalloc() doesn't keep track of free lists -- it's usually
+ *	just a buffered call to sbrk(2).  However, bmalloc will
+ *	call mscrounge() if sbrk fails.
+ * mscrounge() returns whatever memory it can find to satisfy the
+ *	request along with the number of bytes (modified).
  *
  *	Greg Ward	Lawrence Berkeley Laboratory
  */
@@ -23,10 +26,11 @@ static char SCCSid[] = "$SunId$ LBL";
 #endif
 #define  BYTES_WORD	sizeof(ALIGN)
 
+#define  MAXINCR	(1<<18)			/* largest sbrk(2) increment */
+
 #ifdef  NOVMEM
 #define  getpagesize()	BYTES_WORD
 #endif
-
 					/* malloc free lists */
 typedef union m_head {
 	union m_head	*next;
@@ -41,18 +45,40 @@ static M_HEAD	*free_list[NBUCKETS];
 
 
 char *
+mscrounge(np)		/* search free lists to satisfy request */
+register unsigned	*np;
+{
+	char	*p;
+	register int	bucket;
+	register unsigned	bsiz;
+
+	for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
+			bucket < NBUCKETS; bucket++, bsiz <<= 1)
+		if (free_list[bucket] != NULL && bsiz+sizeof(M_HEAD) >= *np) {
+			*np = bsiz+sizeof(M_HEAD);
+			p = (char *)free_list[bucket];
+			free_list[bucket] = free_list[bucket]->next;
+			return(p);
+		}
+	*np = 0;
+	return(NULL);
+}
+
+
+char *
 bmalloc(n)		/* allocate a block of n bytes, sans header */
 register unsigned  n;
 {
 	extern char  *sbrk();
-	static int  pagesz = 0;
-	static int  amnt;
+	static unsigned  pagesz = 0;
+	static unsigned  amnt;
 	static char  *bpos;
-	static int  nrem;
+	static unsigned  nrem;
+	unsigned  thisamnt;
 	register char	*p;
 
 	if (pagesz == 0) {				/* initialize */
-		amnt = pagesz = getpagesize();
+		pagesz = amnt = getpagesize();
 		nrem = (int)sbrk(0);			/* page align break */
 		nrem = pagesz - (nrem&(pagesz-1));
 		bpos = sbrk(nrem);			/* word aligned! */
@@ -63,17 +89,25 @@ register unsigned  n;
 	n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1);		/* word align rqst. */
 
 	if (n > nrem) {					/* need more core */
-		if (n > amnt)			/* increase amount */
-			amnt = (n+(pagesz-1))&~(pagesz-1);
-		p = sbrk(amnt);
-		if ((int)p == -1)
-			return(NULL);
-		if (p != bpos+nrem) {		/* someone called sbrk()! */
-			bfree(bpos, nrem);
-			bpos = p;
-			nrem = amnt;
+		if (n > amnt) {				/* big chunk */
+			thisamnt = (n+(pagesz-1))&~(pagesz-1);
+			if (thisamnt <= MAXINCR)	/* increase amnt */
+				amnt = thisamnt;
 		} else
-			nrem += amnt;
+			thisamnt = amnt;
+		p = sbrk(thisamnt);
+		if ((int)p == -1) {			/* uh-oh, ENOMEM */
+			thisamnt = n;			/* search free lists */
+			p = mscrounge(&thisamnt);
+			if (p == NULL)			/* we're really out */
+				return(NULL);
+		}
+		if (p != bpos+nrem) {			/* not an increment */
+			bfree(bpos, nrem);		/* free what we have */
+			bpos = p;
+			nrem = thisamnt;
+		} else					/* otherwise tack on */
+			nrem += thisamnt;
 	}
 	p = bpos;
 	bpos += n;					/* advance */
@@ -83,27 +117,26 @@ register unsigned  n;
 
 
 bfree(p, n)			/* free n bytes of random memory */
-char  *p;
-unsigned  n;
+register char  *p;
+register unsigned  n;
 {
-	register M_HEAD	*mp;
 	register int	bucket;
 	register unsigned	bsiz;
-					/* find largest bucket */
-	bucket = 0;
-	for (bsiz = 1; bsiz+sizeof(M_HEAD) <= n; bsiz <<= 1)
-		bucket++;
-	mp = (M_HEAD *)p;
-	while (bucket > FIRSTBUCKET) {
-		bsiz >>= 1;
-		bucket--;
-		if (n < bsiz+sizeof(M_HEAD))	/* nothing for this bucket */
-			continue;
-		mp->next = free_list[bucket];
-		free_list[bucket] = mp;
-		(char *)mp += bsiz+sizeof(M_HEAD);
-		n -= bsiz+sizeof(M_HEAD);
+					/* align pointer */
+	bsiz = BYTES_WORD - ((unsigned)p&~(BYTES_WORD-1));
+	if (bsiz < BYTES_WORD) {
+		p += bsiz;
+		n -= bsiz;
 	}
+					/* fill big buckets first */
+	for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
+			bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
+		if (n >= bsiz+sizeof(M_HEAD)) {
+			((M_HEAD *)p)->next = free_list[bucket];
+			free_list[bucket] = (M_HEAD *)p;
+			p += bsiz+sizeof(M_HEAD);
+			n -= bsiz+sizeof(M_HEAD);
+		}
 }
 
 
@@ -115,18 +148,21 @@ unsigned	n;
 	register int	bucket;
 	register unsigned	bsiz;
 
+	if (n == 0)
+		return(NULL);
+					/* find first bucket that fits */
 	bucket = FIRSTBUCKET;
 	for (bsiz = 1<<FIRSTBUCKET; bsiz < n; bsiz <<= 1)
 		bucket++;
-	if (free_list[bucket] == NULL) {
+	if (free_list[bucket] == NULL) {	/* need more core */
 		mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
 		if (mp == NULL)
 			return(NULL);
-	} else {
+	} else {				/* got it */
 		mp = free_list[bucket];
 		free_list[bucket] = mp->next;
 	}
-	mp->bucket = bucket;
+	mp->bucket = bucket;			/* tag block */
 	return((char *)(mp+1));
 }
 
@@ -136,24 +172,20 @@ realloc(op, n)			/* reallocate memory using malloc() *
 char	*op;
 unsigned	n;
 {
+	extern char	*memcpy();
 	register char	*p;
 	register unsigned	on;
 
-	if (op != NULL)
-		on = 1 << ((M_HEAD *)op-1)->bucket;
-	else
-		on = 0;
-	if (n <= on && n > on>>1)
-		return(op);		/* same bucket */
-	p = malloc(n);
+	free(op);			/* free it first */
+	p = malloc(n);			/* p==op if same bucket */
 	if (p == NULL)
 		return(NULL);
+	if (p != op)			/* different bucket, do copy */
 #ifdef  BSD
-	bcopy(op, p, n>on ? on : n);
+		bcopy(op, p, n>on ? on : n);
 #else
-	(void)memcpy(p, op, n>on ? on : n);
+		(void)memcpy(p, op, n>on ? on : n);
 #endif
-	free(op);
 	return(p);
 }
 
@@ -164,6 +196,8 @@ char	*p;
 	register M_HEAD	*mp;
 	register int	bucket;
 
+	if (p == NULL)
+		return;
 	mp = (M_HEAD *)p - 1;
 	bucket = mp->bucket;
 	mp->next = free_list[bucket];