d85-jmh@nada.kth.se (Jan-Olof Hendig) (02/28/91)
I have a few questions regarding how exec handles memory allocation. 1/ According to the 1.3 RKM exec maintains a linked list where all free regions in the 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 list nodes in the free memory list? 2/ What kind of allocation strategy does exec use? First fit? Best fit? Thankful for answers to these stupid questions. Jan-Olof Hendig (d85-jmh@nada.kth.se)
zap@lysator.liu.se (Zap Andersson) (02/28/91)
d85-jmh@nada.kth.se (Jan-Olof Hendig) writes: >I have a few questions regarding how exec handles memory allocation. >1/ According to the 1.3 RKM exec maintains a linked list where all free regions in > the 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 list nodes > in the free memory list? For all I know, the memory free list is in free memory! I.e. each free block begins with two longwords, the first pointing to the next free block, and the next describing the size of this block (or vice verca). This is why you can never allocate less than 8 bytes! >2/ What kind of allocation strategy does exec use? First fit? Best fit? I think it takes first that's big 'nuff... >Thankful for answers to these stupid questions. Yer welcome, chummer! >Jan-Olof Hendig (d85-jmh@nada.kth.se) -- * * * * * * * * * * * * * * * * * (This rent for space) * My signature is smaller than * Be warned! The letter 'Z' is Copyright 1991 * yours! - zap@lysator.liu.se * by Zap Inc. So are the colors Red, Green and * * * * * * * * * * * * * * * * * Greenish-yellow (Blue was taken by IBM) -- * * * * * * * * * * * * * * * * * (This rent for space) * My signature is smaller than * Be warned! The letter 'Z' is Copyright 1991 * yours! - zap@lysator.liu.se * by Zap Inc. So are the colors Red, Green and * * * * * * * * * * * * * * * * * Greenish-yellow (Blue was taken by IBM)
meranda@iguana.cis.ohio-state.edu (deron meranda) (03/01/91)
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 )