From: "A.Appleyard" <A DOT APPLEYARD AT fs2 DOT mt DOT umist DOT ac DOT uk>
Organization: Materials Science Centre
To: Eli Zaretskii <eliz AT is DOT elta DOT co DOT il>, DJGPP AT delorie DOT com
Date: Tue, 28 Jan 1997 10:33:21 GMT
Subject: Re: A misfeature re malloc() and new
Message-ID: <A799BD7734@fs2.mt.umist.ac.uk>

Please semd me (a DOT appleyard AT fs2 DOT mt DOT umist DOT ac DOT uk) a copy of any reply, as I had
to unsubscribe from djgpp email group because of severe email intray overload.

On Mon, 27 Jan 1997, A.Appleyard wrote:
> That means that if a program once needs to malloc() a very big block (say a
> megabyte), and then to free() it, the store allegedly freed is not really
> free for reallocation to later small malloc() calls, but is dead space.

  Eli Zaretskii <eliz AT is DOT elta DOT co DOT il> replied:-
> Can you post a short program that exhibits this behavior?  I had on a few
> occasions thought I've found a severe bug in that algorithm, but malloc
> surprised me when I tried to write a program that would fail it.

  It is not something that will show on any PC alike. djgpp v2's malloc(n) and
free() seem to do this, as far as I can tell from the source form file
D:\DJGPP\SRC\LIBC\ANSI\STDLIB\MALLOC.C :-

  for(i=0;i<30;i++) nextf[i] is intended to point to a chain of spare blocks
each of pow(2,i+3) bytes (the first 4 bytes in each block are the pointer to
the next block). At the beginning of the program run, all nextf[i] == 0. These
chains of blocks seem to be called buckets.
  j = lowest integer so that pow(2,j+3) <= n+4; k = pow(2,j+3);
  If nextf[j] == 0, malloc() makes a new block of k bytes by moving the sbrk
pointer up.
  If nextf[j] != 0, malloc() takes a block of k bytes out of nextf[j]'s chain
of blocks and returns ((its start address) + 4).
  free() called on that block adds the freed block to nextf[j]'s chain of
blocks, where j is as above.

  If e.g. a program (by malloc() or new) calls for a block of 900000 bytes,
that is rounded up to pow(2,20) == a megabyte, and that is got by moving the
sbrk() (top of memory) pointer up. When the program calls free() or delete on
that block, it is added to nextf[20-3]'s chain of spare blocks, but is still
assigned to the program.
  If the program later need say to malloc() several blocks in the 100 to 1000
byte range, e.g. malloc(875) looks in nextf[7]'s chain for a free 1024-byte
block, which at first it gets new by calling sbrk() again each time, as there
is no way that it can get that store space by cannibalizing the previous 1
megabyte block, which is still chained to nextf[17].
  If the PC has plenty of RAM, no trouble occurs. If it is e.g. a laptop with
only about 5 meg of RAM, after malloc()'ing a megabyte block and several
blocks in the range of 10000 to 80000 bytes, it starts to `thrash' due to
excessive copying portions of heap between RAM and disk, and if also the hard
disk is nearly full, symptoms of running out of heap storage start to occur.

  Would it be safe to free the 1 megabyte block by breaking it up into smaller
more useful blocks like this, instead of calling free() on it?:-
/* free the block B and break it up into several blocks of size n */
  void myfree(void*B,int n){int i,j,k,l; void*p,*q;
  B-=4; /* now points to the block's header info */
  j=pow(2,((short*)B)[1]+3); /* actual size of big block B */
  p=malloc(n)-4; /* p now points into the chain for the desired small blocks */
  k=pow(2,((short*)p)[1]+3); /* actual size of a desired small block */
  free(p+4); if(k>=j) return; /* error, as j/k must be a power of 2 */
  l=k-j; for(i=0;i<l;i+=k) *((long**)&B[i])=(long*)&B[i+k];
    /* chain each new small block to the next */
  *((void**)&B[i])=0; /* end of chain */
  while((q=*(void**)p)) p=q; /* find end of existing chain */
  *(void**)p=B; /* link on the new blocks */}
  /* That assumes that D:\DJGPP\SRC\LIBC\ANSI\STDLIB\MALLOC.C was compiled
with RCHECK not defined */