Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!helios!bcm!dimacs.rutgers.edu!seismo!uunet!tut.cis.ohio-state.edu!iguana.cis.ohio-state.edu!meranda
From: meranda@iguana.cis.ohio-state.edu (deron meranda)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: Exec memory allocation
Message-ID: <89349@tut.cis.ohio-state.edu>
Date: 28 Feb 91 22:27:46 GMT
References: <1991Feb28.135502.933@kth.se>
Sender: news@tut.cis.ohio-state.edu
Reply-To: deron meranda <meranda@cis.ohio-state.edu>
Organization: Ohio State University Computer and Information Science
Lines: 53

In article <1991Feb28.135502.933@kth.se> d85-jmh@nada.kth.se (Jan-Olof Hendig) writes:
>1/ According to the 1.3 RKM exec maintains a linked list where all free
> regions inthe system are listed. When the system gets more fragmented
> this list must grow in size. My question is simply this, how does exec
> allocate space for the lisin the free memory list? 

The memory list all starts from the MemList entry in the exec base
(see header exec/execbase.h).  This list contains struct MemHeader's
(see exec/memory.h) - one for each main section of memory, i.e. chip,
fast, extended, etc.  These structures contain the attributes of that
section of memory, as well as an entry into the free list for that
piece of memory.  This free list is a simple linked list of struct
MemChunk's.  Exec does not keep track of any used memory, just what is
free.

Now, for each free chunk of memory, the first 8 bytes contains this
MemChunk structure with the fields appropriately filled in.  This is
why a memory chunk can never be smaller than 8 bytes :)  Therefore, the
list of free memory is not some separate list, it is kept right in
the free memory!  Therefore, this list does not eat up any extra space :)


>2/ What kind of allocation strategy does exec use? First fit? Best fit?

When a program requests a piece of memory (via AllocMem()), exec does
the following (roughly):

      1.  Forbid()   <-- Very important!
      2.  Start looking through the MemList for a MemHeader
            with compatible attributes (i.e. CHIP, etc.).
            If the end of the list is reached, fail (step 6).
      3.  Try to Allocate() the memory from that MemHeader
      4.  If the Allocate failed, go back to step 2.
      5.  If MEMF_CLEAR was given, zero out the new memory.
      6.  Permit()

So which memory (CHIP, FAST, etc.) is used depends in part upon the
order in which the MemHeaders are listed.  Now, the Allocate() function
of exec simply uses a first-fit strategy (under 1.3, they are allowed
to change this) of the list of MemChunks.  If the MemChunk is larger
than what is needed, then a new MemChunk will be linked into the list.

Note that Deallocate() will attempt to join contiguous MemChunks back
into a single MemChunk (as long as they are under the same MemHeader)!

Also note that although AllocMem() calls Allocate(), it does NOT
use the exec library vector table, so this is not easily patched
if you want to use a smarter strategy :(  Exec memory allocation
was built primarily with speed in mind.

I hope this gives you an overview of the exec memory allocation :)

Deron E. Meranda  ( meranda@cis.ohio-state.edu )