Path: utzoo!attcan!uunet!ginosko!gem.mps.ohio-state.edu!csd4.csd.uwm.edu!bionet!agate!saturn!ucscc.ucsc.edu!gorn!filbo
From: filbo@gorn.santa-cruz.ca.us (Bela Lubkin)
Newsgroups: comp.lang.pascal
Subject: Turbo 5.x heap management
Summary: more than you wanted to know
Keywords: long, implementation-specific Turbo heap management
Message-ID: <7.filbo@gorn.santa-cruz.ca.us>
Date: 23 Aug 89 15:02:57 GMT
References: <1392@lafcol.UUCP> <6.filbo@gorn.santa-cruz.ca.us> <208300011@s.cs.uiuc.edu>
Organization: R Pentomino
Lines: 77

My previous posting on this subject was insufficiently clear.  This one may
not be much better, as I still haven't extracted my Turbo Pascal manual from
the detritus of moving (the only active use I'm currently making of obscure
TP features is in helping people over the net -- if these postings can indeed
be construed as "help"), but let me try...

The heap code, residing in the System unit, has a number of (semi-) private
variables by which it maintains the heap.  Among others, HeapPtr and FreePtr
point to the "top" and "bottom" of the "free area" on the heap, respectively.
(HeapOrg points to the initial bottom of the heap).  This single "free area"
(not Borland's nomenclature) is distinct from any other free blocks that may
be created by deallocation of memory blocks.  The heap exists above the
program's stack and below the end of the memory DOS has allocated to the
program.  The free list, >when it exists<, occupies the top of this heap
area.  Before any allocations, there is NO free list.  There is only the
single, large, implied free block which is found between HeapPtr and FreePtr.

In the following diagrams, O, P and F designate the locations pointed to by
HeapOrg, HeapPtr and FreePtr.  In a clean heap, HeapOrg and HeapPtr point to
the beginning; FreePtr points beyond the end of the "heap area":
  ---------------------------------------------------    [1]
  O,P                                                F

After one allocation, HeapPtr points past the allocated block:
  1111-----------------------------------------------    [2]
  O   P                                              F

After a second allocation, HeapPtr points past both allocated blocks:
  11112222222----------------------------------------    [3]
  O          P                                       F

If the first block is deallocated, HeapPtr still points past the >highest<
allocated block; FreePtr now moves down to denote the existence of an item on
the free list:
  ----2222222---------------------------------------f    [4]
  O          P                                      F
Item "f" is an 8-byte record: a pointer to the free block and a size, both
stored in pointer format.  These are the 8 "missing" bytes sought in the
original posting of this discussion.

If the second block is deallocated, the heap returns to its initial
condition.  Once again there is no free list, and the 8 missing bytes return:
  ---------------------------------------------------    [5]
  O,P                                                F

If, after step 3, the second block were deallocated, rather than the first,
no free block would be created; the freed memory would be coalesced with the
>implicit< free block demarcated by HeapPtr and FreePtr:
  1111-----------------------------------------------    [4a]
  O   P                                              F

What is confusing (and, I think, poor design) is that the free list never
explicitly notes the space between the highest allocated heap block and the
free list.  Also note that this is not a standard heap design where free
blocks list themselves (i.e. where the free list is actually a linked list
maintained >within< the free blocks themselves).  In the TP5 implementation,
the free list is a contiguous, sorted array of free block pointers; this
array's size floats according to how many free blocks there are.  This was
apparently done to allow free blocks that would be too small to hold a free
list record, and for speed.  It also has the side-effect of making the free
list less susceptible to corruption by bad array references etc.

MemAvail refers to all the memory that's available on the heap -- which is
the sum of all items on the free list plus the implicit free block; and the
implicit free block can be diminished by the free list.  (It >can< be
impossible to deallocate a block if doing so would add a new free block,
and if the memory immediately below the free list is already allocated).

I hope this is clear.  If not, you might seek a Turbo Pascal Reference
manual; they're all over the place.  (Mine's all under the place).

Bela Lubkin     * *   filbo@gorn.santa-cruz.ca.us   CIS: 73047,1112
     @        * *     ...ucbvax!ucscc!gorn!filbo    ^^^  REALLY slow [months]
R Pentomino     *     Filbo @ Pyrzqxgl (408) 476-4633 & XBBS (408) 476-4945

** gorn's MX record is currently broken; you MUST use UUCP routing
** via ...ucbvax!ucscc!gorn!filbo or gorn!filbo@ucscc.ucsc.edu