grimlok@hubcap.clemson.edu (Mike Percy) (06/29/91)
There's been lot's of discussion lately about how TC++ does farmalloc().
Lots of people have said lots of incorrect things, including myself.
I was basing my postings on the TC implementation, which was
apparently re-worked in the TC++ compiler. My info was not valid
for TC++ (but was ok for TC). After spending the morning investigating,
I'm ready to give the real answers.
BTW, my method of investigating was to write some test programs, track
their execution with TDebugger, and basically copy down the asm code
and then work out what was going on. I'm not going to post the
machine code here, as that would likely get me in trouble, but anyone
can step through it if they want to. I'll be including a program
which illustrates the structure and workings of the farheap.
Note that I didn't use farheapcheck or farheapwalk, as they don't
_really_ let you know how things work. I also have not gone to the
trouble of examining malloc (near heap usage in small data memory
models). In large data memory models (compact, large, huge), malloc
is routed through farmalloc -- there is no near heap.
Observation 1:
overhead/request block is 4 bytes:
part of a far pointer, FP_SEG (FP_OFF is always 0)
2-byte int, size in 16-byte paragraphs
notice that the addresses returned are always SEG:0004
Observation 2:
allocation granularity is 16 bytes
Observation 3:
the apparent maximum request allowed is 0xFFFEC (1048556) bytes,
not that this would ever be satisfied, but anything over this
is thrown right out.
Farmalloc:
receives the long int size parameter
checks for size == 0, if so returns dx:ax = 0:0 (NULL)
checks to see if the request is too large; that is, if
request+overhead would result in size > FFFFF
if so, return dx:ax = 0:0 (NULL)
does a nifty bit of math to get number of 16-byte blocks needed
checks to see if this is first call to farmalloc
if first call, set up and call sbrk (more on sbrk later)
return address in dx:ax (might be NULL from sbrk)
checks to see if there are any farfree'd blocks
if there are no free'd blocks, set up and call sbrk
return address in dx:ax (might be NULL from sbrk)
/* there are free blocks */
walk the free block list searching for a block >= request size
a) if block size < request size, go to next free block
b) if block size = request size
remove from free list and put on allcoated list
return address in dx:ax
c) if block size > request size
split block to satisfy request, leave rest on free list
return address in dx:ax
/* no free blocks are large enough */
set up and call sbrk
return address in dx:ax (might be NULL from sbrk)
Sbrk is a function which manages the size of the heap. Basically,
sbrk track heaptop and brklvl. If the heap current has enough
space to satisfy the request, it does so, adjusting heaptop.
If there's not enough space, it asks DOS to resize the heap area,
increasing its size by brklvl. This is done by calling setblock.
If this all works, the heap is now big enough to meet the request,
so sbrk does so.
Farcoreleft() does not return the amount of free space! It returns
the amount of free memory which is not bounded by allocated heap
data. Not particularly useful, but if you wonder how much space you
allocate during runtime, calling farcoreleft before any free's will
tell you. If you want to know how much space is really free
(note that free is not the same as usable -- if the heap is fragmented
there might be lots of free memory, but no one chunk large enough
to satisfy a request), check out the farheapwalk function.
"I don't know about your brain, but mine is really...bossy."
Mike Percy grimlok@hubcap.clemson.edu
ISD, Clemson University mspercy@clemson.BITNET
(803)656-3780 mspercy@clemson.clemson.edu
--------------------------------------------------------------------
#include <alloc.h>
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
char far *blocks[5];
int i;
blocks[0] = (char far *)farcalloc(1,10);
blocks[1] = (char far *)farcalloc(1,10);
blocks[2] = (char far *)farcalloc(1,10);
blocks[3] = (char far *)farcalloc(1,20);
blocks[4] = (char far *)farcalloc(1,20);
for(i = 0; i < 5; i++)
{
printf("%d farmalloc gave %Fp prev is %4x size is %4x",
i,
blocks[i],
*((int far *)(blocks[i]-2)),
*((int far *)(blocks[i]-4))
);
if(*((int far *)(blocks[i]-2)) == 0) /* free block */
{
printf(" next free block is %4x", *((int far *)(blocks[i]+2)));
}
printf("\n");
}
printf("\nallocated\n");
farfree(blocks[1]);
farfree(blocks[3]);
for(i = 0; i < 5; i++)
{
printf("%d farmalloc gave %Fp prev is %4x size is %4x",
i,
blocks[i],
*((int far *)(blocks[i]-2)),
*((int far *)(blocks[i]-4))
);
if(*((int far *)(blocks[i]-2)) == 0) /* free block */
{
printf(" next free block is %4x", *((int far *)(blocks[i]+2)));
}
printf("\n");
}
printf("\nafter\n");
blocks[3] = (char far *)farmalloc(20);
for(i = 0; i < 5; i++)
{
printf("%d farmalloc gave %Fp prev is %4x size is %4x",
i,
blocks[i],
*((int far *)(blocks[i]-2)),
*((int far *)(blocks[i]-4))
);
if(*((int far *)(blocks[i]-2)) == 0) /* free block */
{
printf(" next free block is %4x", *((int far *)(blocks[i]+2)));
}
printf("\n");
}
return 0;
}