diff -cr perl5.002/malloc.c perl5.002.new/malloc.c
*** perl5.002/malloc.c	Sat Jan 27 23:18:22 1996
--- perl5.002.new/malloc.c	Thu Feb 29 01:25:54 1996
***************
*** 14,19 ****
--- 14,20 ----
   * number of different sizes, and keeps free lists of each size.  Blocks that
   * don't exactly fit are passed up to the next larger size.  In this 
   * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
+  * If PACK_MALLOC is defined, small blocks are 2^n bytes long.
   * This is designed for use in a program that uses vast quantities of memory,
   * but bombs when it runs out. 
   */
***************
*** 27,33 ****
--- 28,42 ----
  #define u_int unsigned int
  #define u_short unsigned short
  
+ /* 286 and atarist like big chunks, which gives too much overhead. */
+ #if (defined(RCHECK) || defined(I286) || defined(atarist)) && defined(PACK_MALLOC)
+ #undef PACK_MALLOC
+ #endif 
+ 
+ 
  /*
+  * The description below is applicable if PACK_MALLOC is not defined.
+  *
   * The overhead on a block is at least 4 bytes.  When free, this space
   * contains a pointer to the next free block, and the bottom two bits must
   * be zero.  When in use, the first byte is set to MAGIC, and the second
***************
*** 69,74 ****
--- 78,144 ----
  #define	RSLOP		0
  #endif
  
+ #ifdef PACK_MALLOC
+ /*
+  * In this case it is assumed that if we do sbrk() in 2K units, we
+  * will get 2K aligned blocks. The bucket number of the given subblock is
+  * on the boundary of 2K block which contains the subblock.
+  * Several following bytes contain the magic numbers for the subblocks
+  * in the block.
+  *
+  * Sizes of chunks are powers of 2 for chunks in buckets <=
+  * MAX_PACKED, after this they are (2^n - sizeof(union overhead)) (to
+  * get alignment right).
+  *
+  * We suppose that starts of all the chunks in a 2K block are in
+  * different 2^n-byte-long chunks.  If the top of the last chunk is
+  * aligned on a boundary of 2K block, this means that
+  * sizeof(union overhead)*"number of chunks" < 2^n, or
+  * sizeof(union overhead)*2K < 4^n, or n > 6 + log2(sizeof()/2)/2, if a
+  * chunk of size 2^n - overhead is used. Since this rules out n = 7
+  * for 8 byte alignment, we specialcase allocation of the first of 16
+  * 128-byte-long chunks.
+  *
+  * Note that with the above assumption we automatically have enough
+  * place for MAGIC at the start of 2K block.  Note also that we
+  * overlay union overhead over the chunk, thus the start of the chunk
+  * is immediately overwritten after freeing.
+  */
+ #  define MAX_PACKED 6
+ #  define MAX_2_POT_ALGO ((1<<(MAX_PACKED + 1)) - M_OVERHEAD)
+ #  define TWOK_MASK ((1<<11) - 1)
+ #  define TWOK_MASKED(x) ((int)x & ~TWOK_MASK)
+ #  define TWOK_SHIFT(x) ((int)x & TWOK_MASK)
+ #  define OV_INDEXp(block) ((u_char*)(TWOK_MASKED(block)))
+ #  define OV_INDEX(block) (*OV_INDEXp(block))
+ #  define OV_MAGIC(block,bucket) (*(OV_INDEXp(block) +			\
+ 				    (TWOK_SHIFT(block)>>(bucket + 3)) + \
+ 				    (bucket > MAX_NONSHIFT ? 1 : 0)))
+ #  define CHUNK_SHIFT 0
+ 
+ static u_char n_blks[11 - 3]	 = {224, 120, 62, 31, 16, 8, 4, 2};
+ static u_short blk_shift[11 - 3] = {256, 128, 64, 32, 
+ 				    16*sizeof(union overhead), 
+ 				    8*sizeof(union overhead), 
+ 				    4*sizeof(union overhead), 
+ 				    2*sizeof(union overhead), 
+ #  define MAX_NONSHIFT 2	/* Shift 64 greater than chunk 32. */
+ };
+ 
+ #  ifdef DEBUGGING_MSTATS
+ static u_int sbrk_slack;
+ static u_int start_slack;
+ #  endif
+ 
+ #else  /* !PACK_MALLOC */
+ 
+ #  define OV_MAGIC(block,bucket) (block)->ov_magic
+ #  define OV_INDEX(block) (block)->ov_index
+ #  define CHUNK_SHIFT 1
+ #endif /* !PACK_MALLOC */
+ 
+ #  define M_OVERHEAD (sizeof(union overhead) + RSLOP)
+ 
  /*
   * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
   * smallest allocatable block is 8 bytes.  The overhead information
***************
*** 132,139 ****
  	 * which satisfies request.  Account for
  	 * space used per block for accounting.
  	 */
!   	nbytes += sizeof (union overhead) + RSLOP;
!   	nbytes = (nbytes + 3) &~ 3; 
    	shiftr = (nbytes - 1) >> 2;
  	/* apart from this loop, this is O(1) */
    	while (shiftr >>= 1)
--- 202,215 ----
  	 * which satisfies request.  Account for
  	 * space used per block for accounting.
  	 */
! #ifdef PACK_MALLOC
! 	if (nbytes > MAX_2_POT_ALGO) {
! #endif
! 	    nbytes += M_OVERHEAD;
! 	    nbytes = (nbytes + 3) &~ 3; 
! #ifdef PACK_MALLOC
! 	}
! #endif
    	shiftr = (nbytes - 1) >> 2;
  	/* apart from this loop, this is O(1) */
    	while (shiftr >>= 1)
***************
*** 167,174 ****
  		(unsigned long)*((int*)p),(unsigned long)p);
  #endif
    	nextf[bucket] = p->ov_next;
! 	p->ov_magic = MAGIC;
! 	p->ov_index= bucket;
  #ifdef DEBUGGING_MSTATS
    	nmalloc[bucket]++;
  #endif
--- 243,252 ----
  		(unsigned long)*((int*)p),(unsigned long)p);
  #endif
    	nextf[bucket] = p->ov_next;
! 	OV_MAGIC(p, bucket) = MAGIC;
! #ifndef PACK_MALLOC
! 	OV_INDEX(p) = bucket;
! #endif
  #ifdef DEBUGGING_MSTATS
    	nmalloc[bucket]++;
  #endif
***************
*** 182,188 ****
  	p->ov_rmagic = RMAGIC;
    	*((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
  #endif
!   	return ((Malloc_t)(p + 1));
  }
  
  /*
--- 260,266 ----
  	p->ov_rmagic = RMAGIC;
    	*((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
  #endif
!   	return ((Malloc_t)(p + CHUNK_SHIFT));
  }
  
  /*
***************
*** 196,201 ****
--- 274,280 ----
    	register int rnu;       /* 2^rnu bytes will be requested */
    	register int nblks;     /* become nblks blocks of the desired size */
  	register MEM_SIZE siz;
+ 	int slack = 0;
  
    	if (nextf[bucket])
    		return;
***************
*** 206,217 ****
  	 */
  #ifndef atarist /* on the atari we dont have to worry about this */
    	op = (union overhead *)sbrk(0);
! #ifndef I286
    	if ((int)op & 0x3ff)
!   		(void)sbrk(1024 - ((int)op & 0x3ff));
! #else
  	/* The sbrk(0) call on the I286 always returns the next segment */
! #endif
  #endif /* atarist */
  
  #if !(defined(I286) || defined(atarist))
--- 285,304 ----
  	 */
  #ifndef atarist /* on the atari we dont have to worry about this */
    	op = (union overhead *)sbrk(0);
! #  ifndef I286
! #    ifdef PACK_MALLOC
!   	if ((int)op & 0x7ff)
!   		(void)sbrk(slack = 2048 - ((int)op & 0x7ff));
! #    else
    	if ((int)op & 0x3ff)
!   		(void)sbrk(slack = 1024 - ((int)op & 0x3ff));
! #    endif
! #    if defined(DEBUGGING_MSTATS) && defined(PACK_MALLOC)
! 	sbrk_slack += slack;
! #    endif
! #  else
  	/* The sbrk(0) call on the I286 always returns the next segment */
! #  endif
  #endif /* atarist */
  
  #if !(defined(I286) || defined(atarist))
***************
*** 223,230 ****
    	rnu = (bucket <= 11) ? 14 : bucket + 3;
  #endif
    	nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
!   	if (rnu < bucket)
! 		rnu = bucket;
  	op = (union overhead *)sbrk(1L << rnu);
  	/* no more room! */
    	if ((int)op == -1)
--- 310,317 ----
    	rnu = (bucket <= 11) ? 14 : bucket + 3;
  #endif
    	nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
!   	/* if (rnu < bucket)
! 		rnu = bucket;	Why anyone needs this? */
  	op = (union overhead *)sbrk(1L << rnu);
  	/* no more room! */
    	if ((int)op == -1)
***************
*** 234,239 ****
--- 321,330 ----
  	 * and deduct from block count to reflect.
  	 */
  #ifndef I286
+ #  ifdef PACK_MALLOC
+ 	if ((int)op & 0x7ff)
+ 		croak("panic: Off-page sbrk");
+ #  endif
    	if ((int)op & 7) {
    		op = (union overhead *)(((MEM_SIZE)op + 8) &~ 7);
    		nblks--;
***************
*** 245,256 ****
  	 * Add new memory allocated to that on
  	 * free list for this hash bucket.
  	 */
-   	nextf[bucket] = op;
    	siz = 1 << (bucket + 3);
    	while (--nblks > 0) {
  		op->ov_next = (union overhead *)((caddr_t)op + siz);
  		op = (union overhead *)((caddr_t)op + siz);
    	}
  }
  
  Free_t
--- 336,369 ----
  	 * Add new memory allocated to that on
  	 * free list for this hash bucket.
  	 */
    	siz = 1 << (bucket + 3);
+ #ifdef PACK_MALLOC
+ 	*(u_char*)op = bucket;	/* Fill index. */
+ 	if (bucket <= MAX_PACKED - 3) {
+ 	    op = (union overhead *) ((char*)op + blk_shift[bucket]);
+ 	    nblks = n_blks[bucket];
+ #  ifdef DEBUGGING_MSTATS
+ 	    start_slack += blk_shift[bucket];
+ #  endif
+ 	} else if (bucket <= 11 - 1 - 3) {
+ 	    op = (union overhead *) ((char*)op + blk_shift[bucket]);
+ 	    /* nblks = n_blks[bucket]; */
+ 	    siz -= sizeof(union overhead);
+ 	} else op++;		/* One chunk per block. */
+ #endif /* !PACK_MALLOC */
+   	nextf[bucket] = op;
    	while (--nblks > 0) {
  		op->ov_next = (union overhead *)((caddr_t)op + siz);
  		op = (union overhead *)((caddr_t)op + siz);
    	}
+ #ifdef PACK_MALLOC
+ 	if (bucket == 7 - 3) {	/* Special case, explanation is above. */
+ 	    union overhead *n_op = nextf[7 - 3]->ov_next;
+ 	    nextf[7 - 3] = (union overhead *)((caddr_t)nextf[7 - 3] 
+ 					      - sizeof(union overhead));
+ 	    nextf[7 - 3]->ov_next = n_op;
+ 	}
+ #endif /* !PACK_MALLOC */
  }
  
  Free_t
***************
*** 260,265 ****
--- 373,381 ----
    	register MEM_SIZE size;
  	register union overhead *op;
  	char *cp = (char*)mp;
+ #ifdef PACK_MALLOC
+ 	u_char bucket;
+ #endif 
  
  #ifdef safemalloc
      DEBUG_m(fprintf(stderr,"0x%lx: (%05d) free\n",(unsigned long)cp,an++));
***************
*** 267,277 ****
  
    	if (cp == NULL)
    		return;
! 	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  #ifdef debug
!   	ASSERT(op->ov_magic == MAGIC);		/* make sure it was in use */
  #else
! 	if (op->ov_magic != MAGIC) {
  #ifdef RCHECK
  		warn("%s free() ignored",
  		    op->ov_rmagic == RMAGIC - 1 ? "Duplicate" : "Bad");
--- 383,397 ----
  
    	if (cp == NULL)
    		return;
! 	op = (union overhead *)((caddr_t)cp 
! 				- sizeof (union overhead) * CHUNK_SHIFT);
! #ifdef PACK_MALLOC
! 	bucket = OV_INDEX(op);
! #endif 
  #ifdef debug
!   	ASSERT(OV_MAGIC(op, bucket) == MAGIC); /* make sure it was in use */
  #else
! 	if (OV_MAGIC(op, bucket) != MAGIC) {
  #ifdef RCHECK
  		warn("%s free() ignored",
  		    op->ov_rmagic == RMAGIC - 1 ? "Duplicate" : "Bad");
***************
*** 283,294 ****
  #endif
  #ifdef RCHECK
    	ASSERT(op->ov_rmagic == RMAGIC);
! 	if (op->ov_index <= 13)
  		ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
  	op->ov_rmagic = RMAGIC - 1;
  #endif
!   	ASSERT(op->ov_index < NBUCKETS);
!   	size = op->ov_index;
  	op->ov_next = nextf[size];
    	nextf[size] = op;
  #ifdef DEBUGGING_MSTATS
--- 403,414 ----
  #endif
  #ifdef RCHECK
    	ASSERT(op->ov_rmagic == RMAGIC);
! 	if (OV_INDEX(op) <= 13)
  		ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
  	op->ov_rmagic = RMAGIC - 1;
  #endif
!   	ASSERT(OV_INDEX(op) < NBUCKETS);
!   	size = OV_INDEX(op);
  	op->ov_next = nextf[size];
    	nextf[size] = op;
  #ifdef DEBUGGING_MSTATS
***************
*** 340,349 ****
  #endif
  #endif /* safemalloc */
  
! 	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
! 	if (op->ov_magic == MAGIC) {
  		was_alloced++;
- 		i = op->ov_index;
  	} else {
  		/*
  		 * Already free, doing "compaction".
--- 460,470 ----
  #endif
  #endif /* safemalloc */
  
! 	op = (union overhead *)((caddr_t)cp 
! 				- sizeof (union overhead) * CHUNK_SHIFT);
! 	i = OV_INDEX(op);
! 	if (OV_MAGIC(op, i) == MAGIC) {
  		was_alloced++;
  	} else {
  		/*
  		 * Already free, doing "compaction".
***************
*** 360,382 ****
  		    (i = findbucket(op, reall_srchlen)) < 0)
  			i = 0;
  	}
! 	onb = (1L << (i + 3)) - sizeof (*op) - RSLOP;
  	/* avoid the copy if same size block */
  	if (was_alloced &&
! 	    nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP) {
  #ifdef RCHECK
  		/*
  		 * Record new allocated size of block and
  		 * bound space with magic numbers.
  		 */
! 		if (op->ov_index <= 13) {
  			/*
  			 * Convert amount of memory requested into
  			 * closest block size stored in hash buckets
  			 * which satisfies request.  Account for
  			 * space used per block for accounting.
  			 */
! 			nbytes += sizeof (union overhead) + RSLOP;
  			nbytes = (nbytes + 3) &~ 3; 
  			op->ov_size = nbytes - 1;
  			*((u_int *)((caddr_t)op + nbytes - RSLOP)) = RMAGIC;
--- 481,509 ----
  		    (i = findbucket(op, reall_srchlen)) < 0)
  			i = 0;
  	}
! 	onb = (1L << (i + 3)) - 
! #ifdef PACK_MALLOC
! 	    (i <= (MAX_PACKED - 3) ? 0 : M_OVERHEAD)
! #else
! 	    M_OVERHEAD
! #endif
! 	    ;
  	/* avoid the copy if same size block */
  	if (was_alloced &&
! 	    nbytes <= onb && nbytes > (onb >> 1) - M_OVERHEAD) {
  #ifdef RCHECK
  		/*
  		 * Record new allocated size of block and
  		 * bound space with magic numbers.
  		 */
! 		if (OV_INDEX(op) <= 13) {
  			/*
  			 * Convert amount of memory requested into
  			 * closest block size stored in hash buckets
  			 * which satisfies request.  Account for
  			 * space used per block for accounting.
  			 */
! 			nbytes += M_OVERHEAD;
  			nbytes = (nbytes + 3) &~ 3; 
  			op->ov_size = nbytes - 1;
  			*((u_int *)((caddr_t)op + nbytes - RSLOP)) = RMAGIC;
***************
*** 467,472 ****
--- 594,605 ----
    		fprintf(stderr, (i<5)?" %5d":" %3d", nmalloc[i]);
    	}
    	fprintf(stderr, "\n");
+ #ifdef PACK_MALLOC
+ 	if (sbrk_slack || start_slack) {
+   	    fprintf(stderr, "Odd ends: %7d bytes from sbrk(), %7d from malloc.\n",
+ 		    sbrk_slack, start_slack);
+ 	}
+ #endif
  }
  #else
  void
