|
Memory fragmentation has given has given DOS programmers headaches for a long time. Steve prescribes a memory compaction scheme that can spell relief by, among other things, letting you allocate movable memory blocks.
April 01, 1989
URL:http://www.drdobbs.com/architecture-and-design/a-memory-allocation-compaction-system/184408119
Copyright © 1989, Dr. Dobb's Journal
Steve Peterson is a consultant with FOURTH SHIFT Corp. in Minneapolis. He can be reached at 3100 Boone Ave., North, Minneapolis, MN 55427.
With the popularity of the C programming language, the use of dynamic memory allocation in PC software has become common. Graphical interfaces and object-oriented programming techniques both rely heavily upon the ability to dynamically create and delete blocks of memory.
A natural by-product of the memory allocation tools provided by the standard C library is heap fragmentation. In an operating environment with virtual memory, fragmentation is a concern only to the extent that it degrades performance. Unfortunately, under MS-DOS, memory can become so fragmented that the program fails for lack of contiguous free memory. Microcomputer operating systems developed after MS-DOS provide solutions to this problem. Both Microsoft Windows and the Macintosh Toolbox provide support for compaction of memory. In addition, Microsoft OS/2 provides support for virtual memory.
This article describes a compacting memory management scheme that is implemented in C. The scheme's features include the allocation of memory blocks that can move in memory to minimize fragmentation, the ability to mark individual memory blocks as deleteable or nondeleteable and as fixed or moveable, and the availability of a function that can be associated with a block that is called whenever the block is moved or deleted. Furthermore, this scheme can easily be ported to other environments where an ANSI-standard C compiler is available.
For a memory compaction system to be useful, it must compress memory without disturbing pointers in the user program. Two approaches to this process are in general use. Both approaches maintain a master pointer table, which contains the master pointers to every allocated block. These approaches differ in the way that the user accesses the master pointer.
Under Microsoft Windows, the user program is given a handle to an allocated block of memory. To use the handle, a function must be called to lock the block in place and to retrieve a pointer to the block. The lock should be released when the program no longer needs to reference that block of memory. The advantage of this method is that a block will not move in memory while the block is being used. The disadvantage of this method is that you must call a function in order to get a pointer to a block.
The method implemented in this article is similar to that used on the Apple Macintosh. When a block of memory is allocated, the user program is given a pointer to the master pointer table entry that corresponds to the block. The user program can either reference the block by dereferencing the pointer twice, or it can copy the address from the master pointer table to a local pointer. This implementation requires careful programming. Consider the following example of a function that reads a record from a database where Rec is a double-indirect pointer to a block.
GetDbRec(BlockNum, *Rec)
If GetDbRec causes memory to be compacted, and Rec is moved to a different location, *Rec is no longer a valid pointer, and anything that GetDbRec writes to *Rec will overwrite other data. To overcome this problem, do one of the following:
By adhering to these rules, you can avoid memory corruption.
When the system is initialized, it creates one or more segments, a master segment table (MST), and a master pointer table (MPT). (See Figure 1.) Each segment has an entry in the MST. An MST entry contains the physical address of the segment, the number of blocks allocated, the amount of free space in the segment, and pointers to the first free block and to the most recent free block accessed. The pointer to the most recent free block is used to allocate blocks evenly throughout the segment.
Each segment contains one or more blocks, as shown in Figure 2. When the segment is created, it contains one block that is marked as free and encompasses the entire segment. As the user program requests memory, this free block is broken into smaller blocks that are marked as they are allocated. Each block has a header that is stored immediately prior to the block in memory. This header contains the length of the block, a pointer to the previous block in the segment, flags, the segment in which this block is located, the master pointer associated with this block, and the address of the block function. The meaning of the bits in the flag byte are shown in Table 1.
Block Structure
data of previous block
check byte flags
segment -----
previous block pointer
block length
master pointer number
block data
FLAG FUNCTION --------------------------------------------------------------- BLK_INUSE Block is allocated BLK_DELETED Block contents have been deleted BLK_DELETABLE Contents of block can be deleted if necessary BLK_LOCKED Block cannot be moved in memory BLK_FUNCDELETE Call block function before deleting block BLK_FUNCMOVE Call block function before moving block BLK_LAST Block is last one in the segment
When a block is allocated, the system places a pointer to the block into a free entry in the MPT. The user program receives a pointer to this table entry. The use of double pointer references lets the block move in memory without the user program's knowledge. Unused MPT entries point to NULL. The MPT is created when the system is initialized, and is not stored in a segment.
The compaction algorithm coalesces free space in the segment until a request for space is satisfied. If the amount of freed space is not sufficient, this algorithm begins removing deletable blocks until the request is satisfied.
When a block is deleted, the header portion of the block remains in memory. This allows the application to determine that the block has been deleted.
Listing One, page 82, contains the memory manager header file. Listing Two, page 82, contains the code that implements the module, including functions to initialize the module, allocate and deallocate memory, manually compact memory, and test the state of the module.
int MemInit(long Size, int Num MPTEntries) --This function initializes the module. Size specifies the number of bytes to be allocated to segments. NumMPTEntries is the number of entries to be allocated in the master pointer table. The function returns TRUE after successful initialization, and FALSE if not enough memory was available. For example, MemInit(2621441, 512); allocates 256K under the system and allows 512 master pointers.
The function first allocates an array large enough to hold the entire master pointer list, and it then allocates segments. The code tries to allocate segments of 64K - 1 bytes long. If the last segment is less than 16K bytes, its size is increased by 16K, and the size of the next-to-last segment is decreased correspondingly. This step helps avoid the allocation of segments that are too small to be useful.
Once the segments are created, a single free block is allocated inside of each one.
void **P = MemAlloc(unsigned int Size) --This function allocates a block of memory in the system. Size is the number of bytes to be allocated in the block. P points to the master pointer for the block, or to NULL if the block could not be allocated.
The memory allocator first searches the free list, starting at the last free block referenced, in order to find a free block that is large enough to hold the block to be allocated. If no free block is sufficiently large, the function compacts the segment that contains the most remaining free space, until that segment has a free block that can hold the block to be allocated. When a block is created, it is marked non-deletable and moveable.
void **P = MemAllocFunc (unsigned int Size, void (*Func)(void *b, unsigned int f, unsigned int Size, void *c), unsigned int Flags) --This function is similar to MemAlloc, except that you can specify a function (the "block function") to be called when the block is moved or deleted. Passing the flag BLK_FUNCMOVE causes the function to be called when the block is moved. Similarly, passing the flag BLK_FUNCDELETE causes the function to be called when the block is deleted. These flags can be ORed together to indicate both options.
The block function takes as parameters the block to be deleted, a flag that indicates if the block is being moved or deleted, and the length of the block. If BLK_FUNCMOVE is set, C points to the new location of the block. This function returns VOID.
void MemFree(void **P) --This function deallocates a block of memory. P points to the MPT entry for the block, and the deallocation routine combines the block with adjacent free blocks. The block function is not called when a block is deallocated.
MemCompact(void) --This function lets you manually compact memory. By calling CompactSeg( ) for each segment, memory is compacted completely.
CompactSeg(byte Segment, unsigned int Size, int Deletable) --The CompactSeg function performs the actual compaction of memory. Segment indicates the segment to be compacted. Size indicates how many bytes of contiguous space are required. Deleteable is TRUE if deletable blocks are to be deleted.
The function proceeds through memory, examining each block in turn, and looks for a free block where coalescing can begin. Once the first free block is found, the function begins the compaction of subsequent blocks. If a block is deletable, it is marked as deleted, and the function moves the block header to its new location. If a block is in use and moveable, that block is moved to its new location.
In MemAlloc( ), the function is called twice. It is called with Deletable FALSE, then called again with Deletable TRUE if there is still not enough free space.
MemLocked(void **P) -- The MemLocked function returns TRUE if a block is locked; otherwise it returns FALSE.
MemLock(void **P) -- locks a block into a location in memory.
MemUnlock(void **P) -- The function MemUnlock releases a lock on a block.
MemDeleted(void **P) -- This function returns TRUE if a block is deletable, or FALSE if the block is not deletable.
MemDeletable(void **P) -- This function makes a block deletable.
MemUndeletable(void **P) -- This function makes a block undeletable.
MemGetLargest(void) -- This function returns the size of the largest block that could be allocated.
MemGetCurrentLargest(void) -- The function MemGetCurrentLargest returns the size of the largest block that could be allocated without compaction.
Listing Three, page 89, shows a simple program designed to demonstrate the features of the module.
As in any module, many enhancements and improvements can be made, depending upon your needs. For example, if space is a critical consideration, you can decrease the block overhead. One way to do so is by replacing the pointer to the previous block with an offset, saving two bytes in the large memory model. Another way is to eliminate the block function, thus saving four bytes. Yet another tactic is to store the segment number in the unused bits of the flags field, or to compute the segment number from the master segment table entries. Finally, the master pointer number can be determined by searching the master pointer table.
If time is more important, you can copy contiguous allocated blocks in one operation during the compaction process, rather than copying them separately. Since the current compaction algorithm eliminates deletable blocks in a first-come, first-served order, another optimization is to add a mechanism for assigning priority to deleteable blocks in order to allow the application to control the order of deletion. You can also write the block configuration functions (MemLocked, MemLock, Mem Unlock, MemDeleted, MemDeletable, and MemUndeletable) as macros. Finally, under Microsoft C 5.1, in certain situations you can use the memcpy( ) function, which is more efficient.
Additional functions that you can implement are MemDelete( ), which allows a block to be deleted under program control, and MemReallocate( ), which reallocates a block that has been deleted.
_A MEMORY ALLOCATION COMPACTION SYSTEM_ by Steve Peterson
[LISTING ONE]
Copyright © 1989, Dr. Dobb's Journal
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.
/**** mem.h data structures for memory manager
S. Peterson programmer 12/88
*/
typedef unsigned char byte;
typedef unsigned int uint;
/* This structure is the header of a memory block. It lies before
the actual memory block. */
struct memBlkHdr {
char checkByte; /* Header validation */
byte flags; /* Flags (see below) */
byte segment;/* Segment of this block */
struct memBlkHdr *prev; /* Pointer-previous block */
uint size; /* size of block */
int pointerNum; /* Block master pointer */
void (*func)(void *, byte, uint, void *);
} ;
typedef struct memBlkHdr MEMBLK;
/* These are the definitions of each of the flags in the flags byte
of memBlkHdr. */
#define BLK_INUSE 0x01 /* Block is allocated */
#define BLK_DELETABLE 0x02 /* Block can be deleted */
#define BLK_LOCKED 0x04 /* Block is locked */
#define BLK_FUNCDELETE 0x08 /* Call block function on delete */
#define BLK_FUNCMOVE 0x10 /* Call block function on move */
#define BLK_DELETED 0x20 /* Block has been deleted */
#define BLK_LAST 0x40 /* Last block in segment */
/* freePtr is stored at the beginning of the user part of a
free block. It contains the links to next and previous free blocks
in the segment. prev is NULL if this is the first free block, and
next is NULL if this is the last block */
struct freePtr {
MEMBLK *prev; /* Pointer to previous free block */
MEMBLK *next; /* Pointer to next free block */
} ;
typedef struct freePtr FREEBLK;
/* Macro to return address of data area give block header address */
#define DATALOC(xx) ((byte *) (xx) + sizeof(MEMBLK))
/* Macro to return address of header given data area address */
#define HEADERLOC(xx) ((byte *) (xx) - sizeof(MEMBLK))
/* This is an entry in the master block table. */
struct masterSegmentEntry {
void *block; /* Address, associated block */
uint size; /* Size of block */
uint freeSpace; /* Amount of free space */
struct memBlkHdr *free; /* First free block */
struct memBlkHdr *last; /* Last reference free block */
} ;
#define DEFSEGSIZE 4096 /* Default segment size */
#define CB 'S'
/* MINREMAINDER is the smallest free block that can remain after
allocation. Making this larger reduces fragmentation but wastes
more space. */
#define MINREMAINDER 20
/* MINBLOCKDATA is the smallest block data area that can be created. This
must be at least sizeof(FREEBLK) bytes so there is space for the
next and prev pointers stored in a free block. */
#define MINBLOCKDATA (sizeof(FREEBLK))
/* Function prototypes */
#ifndef NOPROTO
int MemInit(long int, int);
int MemLocked(void **);
void MemLock(void **);
void MemUnlock(void **);
void MemDeletable(void **);
void MemUndeletable(void **);
int MemDeleted(void **);
void **MemAlloc(uint);
void **MemAllocFunc(uint,void (*)(void *,byte, uint, void *), uint);
void MemFree(void **);
uint MemGetLargest(void);
uint MemGetCurrentLargest(void);
void MemCompact(void);
#endif
[LISTING TWO]
/***** mem.c Compactible memory manager
S. Peterson programmer 12/88, 1/89
This module provides a memory management system with the following
features:
. Relocatable memory blocks
. Able to collapse fragemented free space
. Disposable blocks
. Lockable blocks
*/
#include <stdio.h>
#include <stddef.h>
#include <malloc.h>
#include <string.h>
#include <process.h>
#include <stdlib.h>
#include <conio.h>
#include "mem.h"
/* Static module data */
struct masterSegmentEntry *mst = NULL; /* Master segment table */
byte numSegs = -1; /* Number of whole & partial segments */
byte lastSeg = -1; /* Index of last segment used */
void **mpt = NULL; /* Master pointer table */
int numMP = -1; /* Number of master pointers allocated */
int mpFree = -1; /* Number of master pointers free */
int lastMP = -1; /* Last master pointer used */
/* Local function declarations */
#ifndef NOPROTO
static int FindFreeBlock(int, uint, void **);
static int AllocBlock(uint, void **, byte);
static int GetFreeMP(void);
static void ReleaseMP(int);
static void CompactSeg(byte, uint, int);
#endif
/** MemInit -- initalize memory manager
Entry lSize size of requested memory in bytes
nHandles number of block handles to allocate
Exit none
Returns TRUE worked
FALSE failed
**/
int
MemInit(lSize, nHandles)
long int lSize;
int nHandles;
{
byte numWhole; /* Number of whole segments to create */
uint numBytes; /* Size of partial segment */
uint createSize; /* Size to create */
MEMBLK *mbh; /* Work block header */
int i; /* Work */
FREEBLK *f; /* Free links */
/* Allocate handle list */
if ((mpt = (void **) malloc(sizeof(void *)*nHandles)) == NULL)
return FALSE;
numMP = nHandles;
for (i = 0; i < numMP; mpt[i] = NULL, i++) ;
mpFree = numMP;
lastMP = 0;
/* Determine size of segments to create */
numWhole = (byte) (lSize / (long) DEFSEGSIZE);
numBytes = (uint) (lSize % (long) DEFSEGSIZE);
numSegs = numWhole + 1;
lastSeg = 0;
if ((mst = (struct masterSegmentEntry *) malloc(sizeof
(struct masterSegmentEntry)*(numSegs))) == NULL)
return FALSE;
/* Allocate segments */
for(i = 0; i < numSegs; i++) {
if (i == numSegs - 2) { /* Second to last */
if (numBytes < DEFSEGSIZE / 4) { /* Last is small */
numBytes += DEFSEGSIZE / 4;
createSize = DEFSEGSIZE - (DEFSEGSIZE / 4);
} else {
createSize = DEFSEGSIZE;
}
} else if (i == numSegs - 1) { /* Last */
createSize = numBytes;
} else { /* Whole segment */
createSize = DEFSEGSIZE;
}
if (createSize < sizeof(MEMBLK) + 10)
return FALSE;
if ((mst[i].block = (void *) malloc(createSize)) == NULL)
return FALSE;
mst[i].size = createSize;
mst[i].freeSpace = createSize;
/* Allocate one block in segment */
mbh = (MEMBLK *) mst[i].block;
mst[i].free = mbh;
mst[i].last = mbh;
mbh->checkByte = CB;
mbh->prev = NULL;
mbh->flags = BLK_LAST;
mbh->size = mst[i].size;
mbh->segment = (byte) i;
/* Clear next and prev pointer area */
f = (FREEBLK *) DATALOC(mbh);
f->prev = NULL;
f->next = NULL;
}
return TRUE;
}
/** MemLocked -- test whether a block is locked
Entry block address of a block
Exit none
Returns TRUE block is locked
FALSE not locked
**/
int
MemLocked(block)
void **block;
{
return !(((MEMBLK *) HEADERLOC(*block))->flags & BLK_LOCKED);
}
/** MemLock -- locks a block into a particular location in memory
Entry block address of block to lock
Exit none
Returns void
**/
void
MemLock(block)
void **block;
{
((MEMBLK *) HEADERLOC(*block))->flags |= BLK_LOCKED;
}
/** MemUnlock -- unlocks a block
Entry block address of block to unlock
Exit none
Returns void
**/
void
MemUnlock(block)
void **block;
{
((MEMBLK *) HEADERLOC(*block))->flags &= ~BLK_LOCKED;
}
/** MemDeletable -- make a block deletable
Entry block address of block to mark as deletable
Exit none
Returns void
**/
void
MemDeletable(block)
void **block;
{
((MEMBLK *) HEADERLOC(*block))->flags |= BLK_DELETABLE;
}
/** MemUndeletable -- mark a block as undeletable
Entry block address of block to mark
Exit none
Returns void
**/
void
MemUndeletable(block)
void **block;
{
((MEMBLK *) HEADERLOC(*block))->flags &= ~BLK_LOCKED;
}
/** MemIsDeleted -- test whether a block has been deleted
Entry block address of a block
Exit none
Returns TRUE block is available
FALSE has been deleted
**/
int
MemDeleted(block)
void **block;
{
return (((MEMBLK *) HEADERLOC(*block))->flags & BLK_DELETED) != 0;
}
/** MemAlloc -- allocate memory block
Entry size size of block to allocate
Exit none
Returns pointer to created block, or NULL if not enough room to create
Notes The function operates by first examining the current segment
for a first fit to the requested size. It then proceeds to
the remaining blocks looking for a free block of adequate
size.
If no block exists that is large enough, it examines the
segment list looking for a segment that can be compacted
to produce enough room. The segment with the fewest
allocated blocks is favored for compaction.
Possible enhancement: if no segment has enough room, shuffle
blocks between segments.
If there is not enough room in any segment, the function
fails.
**/
void **
MemAlloc(size)
uint size;
{
byte curSeg; /* Current segment */
byte segIndex; /* Index of segment in list */
long ltotalFree = 0l; /* Total free space */
byte maxFreeSeg = 255; /* Segment, most free space */
uint maxFreeSize = 0; /* Segment space, most space */
MEMBLK *b; /* Block address to allocate */
int created = FALSE; /* Block created */
int mp; /* Master pointer */
if ((mp = GetFreeMP()) < 0)
return NULL;
if (size > DEFSEGSIZE - sizeof(MEMBLK))
return NULL;
if (size < MINBLOCKDATA) /* Smallest allocatable block */
size = MINBLOCKDATA;
size += sizeof(MEMBLK); /* Add header to block */
/* First pass -- try to allocate from current block structure */
for (segIndex = 0; (segIndex < numSegs) && (!created); segIndex++) {
curSeg = (lastSeg + segIndex) % numSegs;
/* Get stats */
ltotalFree += (long) mst[curSeg].freeSpace;
/* Is there enough space in the current segment to allocate? */
if (mst[curSeg].freeSpace >= size) {
if (maxFreeSize < mst[curSeg].freeSpace) {
maxFreeSize = mst[curSeg].freeSpace;
maxFreeSeg = curSeg;
}
/* Search free list for first fit */
if (FindFreeBlock(curSeg, size, &b)) {
/* Allocate */
if (!(created = AllocBlock(size, &b, curSeg)))
return FALSE;
}
}
}
/* Which segment could be compacted to create a block large enough?
We kept track of the segment with the most free space. This should
compact easily. */
if (!created && (maxFreeSeg != 255)) {
/* Compact to produce needed free space */
curSeg = maxFreeSeg;
CompactSeg(curSeg, size, FALSE);
if (!FindFreeBlock(curSeg, size, &b)) {
CompactSeg(curSeg, size, TRUE);
if (!FindFreeBlock(curSeg, size, &b))
return NULL;
}
if (!(created = AllocBlock(size, &b, curSeg)))
return FALSE;
}
if (created) {
mst[curSeg].freeSpace -= b->size;
mpt[mp] = DATALOC(b);
b->pointerNum = mp;
b->func = NULL;
lastSeg = curSeg;
return (void *) &(mpt[mp]);
} else {
ReleaseMP(mp);
return NULL;
}
}
/** MemAllocFunc -- allocate a memory block with an associated function
Entry size size of block to allocate
func function to call
flags following constants:
BLK_FUNCDELETE call function when block deleted
BLK_FUNMOVE call function when block moved
Exit none
Returns pointer to allocated block, or NULL if no space available
Notes Calls memAlloc to allocate memory
**/
void **
MemAllocFunc(size, func, flags)
uint size;
void (*func)(void *, byte, uint, void *);
uint flags;
{
void **aBlock; /* Allocated block */
MEMBLK *b; /* Dereferenced block header */
if ((aBlock = MemAlloc(size)) != NULL) {
b = (MEMBLK *) HEADERLOC(*aBlock);
b->flags |= flags & (BLK_FUNCMOVE | BLK_FUNCDELETE);
b->func = func;
return aBlock;
} else {
return NULL;
}
}
/** FindFreeBlock -- locate a free block in a segment
Entry seg segment to search
size bytes required for block including header
Exit b address of block header (if found)
Returns TRUE block found
FALSE no space
Notes Finds a free block in the current segment. Starts
with the last-referenced free block in the segment. This
spreads the allocations through the segment and combats
fragmentation.
The caller can save some time by first checking to see if
the segment has enough free space to allocate the block.
This algorithm uses the first-fit method, which is fast but
promotes fragmentation.
**/
static int
FindFreeBlock(seg, size, b)
int seg;
uint size;
void **b;
{
MEMBLK *m; /* Current memory block */
m = mst[seg].last;
if (m != NULL) {
while (m->size < size) {
if ((m = ((FREEBLK *) DATALOC(m))->next) == NULL) {
/* End of free list */
m = mst[seg].free;
}
if (m == mst[seg].last)
break;
}
if (m->size < size) { /* No block large enough */
*b = NULL;
return FALSE;
} else { /* Block found */
*b = m;
return TRUE;
}
} else { /* No block */
*b = NULL;
return FALSE;
}
}
/** AllocBlock -- allocate a block
Entry size size of block (including header) to allocate
b address of block where it will be allocated
Exit b Address of allocated block header (this is
different that the b input parameter)
Returns TRUE allocated
FALSE memory structure corrupt
Notes This function takes a block and splits it in two. If the
remaining free block is small, the entire block is allocated
and no free portion is created. This can waste some memory,
but avoids extreme fragmentation.
**/
static int
AllocBlock(size, b, segment)
uint size;
void **b;
byte segment;
{
MEMBLK *freeBlock; /* Free block */
MEMBLK *nextBlock; /* Next block */
MEMBLK *aBlock; /* Allocated block */
FREEBLK *curFree; /* Free pointers in block we are allocating */
FREEBLK *t; /* Pointer to free block we are adjusting */
freeBlock = (MEMBLK *) *b;
if ((freeBlock->size - MINREMAINDER < size)) {
/* Whole block will be allocated */
aBlock = freeBlock;
size = aBlock->size;
aBlock->flags |= BLK_INUSE;
curFree = (FREEBLK *) DATALOC(aBlock);
if (mst[segment].free == aBlock) {
/* Implicit: aBlock is first in list */
mst[segment].free = curFree->next;
}
if (curFree->next != NULL) {
t = (FREEBLK *) DATALOC(curFree->next);
t->prev = curFree->prev;
mst[segment].last = curFree->next;
} else if (curFree->prev != NULL) {
t = (FREEBLK *) DATALOC(curFree->prev);
t->next = curFree->next;
mst[segment].last = curFree->prev;
} else { /* No free block */
mst[segment].last = NULL;
mst[segment].free = NULL;
}
} else { /* Block will be split */
aBlock = (MEMBLK *) ((byte *) freeBlock +
(freeBlock->size - size));
aBlock->checkByte = CB;
aBlock->prev = freeBlock;
aBlock->flags = BLK_INUSE;
aBlock->size = size;
aBlock->segment = segment;
freeBlock->size -= size;
/* Is block last in segment? */
if ((freeBlock->flags & BLK_LAST) != 0) {
freeBlock->flags &= ~BLK_LAST;
aBlock->flags |= BLK_LAST;
} else {
nextBlock = (MEMBLK *) ((byte *) aBlock + (aBlock->size));
nextBlock->prev = aBlock;
}
}
*b = aBlock;
return TRUE;
}
/** GetFreeMP -- return next free master pointer
Entry none
Exit none
Returns index of next free master pointer
**/
static int
GetFreeMP()
{
int i;
if (mpFree == 0)
return -1;
for (i = 0; i < numMP; i++, lastMP++) {
if (lastMP >= numMP)
lastMP = 0;
if (mpt[lastMP] == 0) {
mpFree--;
return lastMP;
}
}
return -1;
}
/** ReleaseMP -- release a master pointer to free pool
Entry mp master pointer to release
Exit none
Returns void
**/
static void
ReleaseMP(mp)
int mp;
{
mpFree++;
mpt[mp] = NULL;
}
/** MemFree -- free a block of memory
Entry blockPtr pointer to mpt entry for block
Exit none
Returns none
**/
void
MemFree(blockPtr)
void **blockPtr;
{
MEMBLK *cur; /* Actual block */
FREEBLK *curFree; /* Free block in current block */
MEMBLK *workMem; /* Work block in memory */
FREEBLK *workFree; /* Work block in next block */
int combined = FALSE; /* Has been combined */
cur = (MEMBLK *) HEADERLOC(*blockPtr);
if (cur->checkByte != CB)
return;
ReleaseMP(cur->pointerNum); /* blockPtr no longer valid */
curFree = (FREEBLK *) DATALOC(cur);
/* Mark block as unallocated */
cur->flags &= ~BLK_INUSE;
mst[cur->segment].freeSpace += cur->size;
/* Combine with subsequent block? */
if ((cur->flags & BLK_LAST) == 0) {
workMem = (MEMBLK *) ((byte *) cur + cur->size);
if ((workMem->flags & BLK_INUSE) == 0) { /* unallocated */
combined = TRUE;
if ((workMem->flags & BLK_LAST) != 0)
cur->flags |= BLK_LAST;
workFree = (FREEBLK *) DATALOC(workMem);
curFree->next = workFree->next;
curFree->prev = workFree->prev;
cur->size += workMem->size;
/* New top of free list? */
if (workMem == mst[cur->segment].free)
mst[cur->segment].free = cur;
if (workMem == mst[cur->segment].last)
mst[cur->segment].last = cur;
/* Adjust pointers in free chain. Point to new block */
if (curFree->next != NULL) {
workFree = (FREEBLK *) DATALOC(curFree->next);
workFree->prev = cur;
}
if (curFree->prev != NULL) {
workFree = (FREEBLK *) DATALOC(curFree->prev);
workFree->next = cur;
}
/* Adjust previous block chain */
if ((cur->flags & BLK_LAST) == 0) {
workMem = (MEMBLK *) ((byte *) workMem +
workMem->size);
workMem->prev = cur;
}
}
}
/* Combine with previous block? */
if (cur->prev != NULL) {
workMem = cur->prev;
if ((workMem->flags & BLK_INUSE) == 0) { /* unallocated */
workMem->size += cur->size;
if ((cur->flags & BLK_LAST) != 0)
workMem->flags |= BLK_LAST;
cur->checkByte = '\0';
if (combined) {
/* Eliminate free block from links */
workFree = (FREEBLK *) DATALOC(workMem);
workFree->next = curFree->next;
if (workFree->next != NULL) {
workFree = (FREEBLK *)
DATALOC(workFree->next);
workFree->prev = workMem;
}
} else {
/* Free block already linked */
combined = TRUE;
}
/* Connect block chain */
if ((cur->flags & BLK_LAST) == 0) {
workMem = (MEMBLK *) ((byte *) cur + cur->size);
workMem->prev = cur->prev;
}
if (cur == mst[cur->segment].free)
mst[cur->segment].free = workMem;
if (cur == mst[cur->segment].last)
mst[cur->segment].last = workMem;
}
}
/* If not combined, link into free chain */
if (!combined) {
/* We scan backwards looking for the last block that
is free */
workMem = cur->prev;
while ((workMem != NULL) && ((workMem->flags &
BLK_INUSE) != 0)) {
workMem = workMem->prev;
}
/* A block is prior to the free block in memory */
if (workMem != NULL) {
workFree = (FREEBLK *) DATALOC(workMem);
curFree->prev = workMem;
curFree->next = workFree->next;
workFree->next = cur;
if (curFree->next != NULL) {
workFree = (FREEBLK *) DATALOC(curFree->next);
workFree->prev = cur;
}
} else { /* Place at beginning of list */
curFree->prev = NULL;
curFree->next = mst[cur->segment].free;
if (mst[cur->segment].free != NULL) {
workFree=(FREEBLK *) DATALOC(mst[cur->segment].free);
workFree->prev = cur;
}
mst[cur->segment].free = cur;
}
}
if (mst[cur->segment].last == NULL) {
mst[cur->segment].last = cur;
mst[cur->segment].free = cur;
}
}
/** MemGetLargest -- returns size of largest block available after
compaction
Entry none
Exit none
Returns Free space in segment with most free space, less the size of
one block header.
**/
uint
MemGetLargest()
{
byte seg; /* Current segment */
uint largest = 0; /* Free space */
for (seg = 0; seg < numSegs; seg++)
if (largest < mst[seg].freeSpace)
largest = mst[seg].freeSpace;
if (largest < sizeof(MEMBLK))
return 0;
else
return largest - sizeof(MEMBLK);
}
/** MemGetCurrentLargest -- returns size of largest available block
Entry none
Exit none
Returns size of largest available block
**/
uint
MemGetCurrentLargest()
{
byte seg; /* Current segment */
MEMBLK *curBlock; /* Current block */
FREEBLK *curFree; /* Current free block */
uint largest = 0; /* Largest block found */
for (seg = 0; seg < numSegs; seg++) {
curBlock = mst[seg].free;
while (curBlock != NULL) {
if (curBlock->size > largest) {
largest = curBlock->size;
}
curFree = (FREEBLK *) DATALOC(curBlock);
curBlock = curFree->next;
}
}
if (largest < sizeof(MEMBLK))
return 0;
else
return largest - sizeof(MEMBLK);
}
/** MemCompact -- invoke compaction routine
Entry none
Exit none
Returns none
**/
void
MemCompact()
{
byte seg;
for (seg = 0; seg < numSegs; seg++) {
CompactSeg(seg, DEFSEGSIZE, FALSE);
}
}
/** CompactSeg -- compact a segment
Entry seg segment to compact
size desired free block size
deletable TRUE if deletable segments should be deleted
FALSE otherwise
Exit none
Returns none
**/
static void
CompactSeg(seg, size, deletable)
byte seg;
uint size;
int deletable;
{
MEMBLK *copyLoc = NULL; /* Next place to copy */
FREEBLK *copyFree; /* Free pointers */
MEMBLK *curBlk; /* First block */
MEMBLK *saveBlk; /* Saved block location */
MEMBLK *prevBlk = NULL; /* Previous block */
MEMBLK *nextFree = NULL; /* Saved next free block */
MEMBLK *prevFree = NULL; /* Saved prev. free block */
FREEBLK *tmpFree; /* Temporary free pointer */
uint spaceRecovered = 0; /* Amount space recovered */
int last = FALSE; /* Last record found */
curBlk = mst[seg].block;
while ((spaceRecovered < size) && (!last)) {
last = (curBlk->flags & BLK_LAST) != 0;
if (((curBlk->flags & BLK_DELETABLE) != 0) && (deletable) &&
(curBlk->size > sizeof(MEMBLK) + MINBLOCKDATA)) {
spaceRecovered += curBlk->size - sizeof(MEMBLK) -
MINBLOCKDATA;
if (copyLoc != NULL) {
if ((curBlk->flags & BLK_FUNCDELETE) != 0)
(*(curBlk->func))(curBlk, BLK_FUNCDELETE
| BLK_FUNCMOVE, curBlk->size, copyLoc);
/* Save location of block */
saveBlk = curBlk;
/* Move block header to new location */
memmove(copyLoc, curBlk, sizeof(MEMBLK));
/* Set up new pointer to previous block */
copyLoc->prev = prevBlk;
copyLoc->flags &= ~BLK_LAST;
copyLoc->flags |= BLK_DELETED;
copyLoc->size = sizeof(MEMBLK) + MINBLOCKDATA;
mpt[copyLoc->pointerNum] = DATALOC(copyLoc);
prevBlk = copyLoc;
curBlk = (MEMBLK *) ((byte *) saveBlk +
copyLoc->size);
copyLoc = (MEMBLK *) ((byte *) copyLoc +
copyLoc->size);
} else {
if ((curBlk->flags & BLK_FUNCDELETE) != 0)
(*(curBlk->func))(curBlk,
BLK_FUNCDELETE, curBlk->size, NULL);
/* Initialize free area after block */
curBlk->flags &= ~BLK_LAST;
curBlk->flags |= BLK_DELETED;
saveBlk = curBlk;
prevBlk = curBlk;
curBlk = (MEMBLK *) ((byte *) curBlk +
curBlk->size);
saveBlk->size = sizeof(MEMBLK) + MINBLOCKDATA;
copyLoc = (MEMBLK *) DATALOC(saveBlk);
}
} else if ((curBlk->flags & BLK_INUSE) != 0) {
if (copyLoc == NULL) {
prevBlk = curBlk;
curBlk = (MEMBLK *) ((byte *) curBlk +
curBlk->size);
} else {
if ((curBlk->flags & BLK_LOCKED) == 0) {
if ((curBlk->flags & BLK_FUNCMOVE) != 0)
(*(curBlk->func))(curBlk,
BLK_FUNCMOVE, curBlk->size,
copyLoc);
/* Move block to new location */
saveBlk = curBlk;
memmove(copyLoc, curBlk, curBlk->size);
copyLoc->prev = prevBlk;
copyLoc->flags &= ~BLK_LAST;
prevBlk = copyLoc;
mpt[copyLoc->pointerNum] =
DATALOC(copyLoc);
/* Move pointer to next block */
curBlk = (MEMBLK *) ((byte *)saveBlk +
copyLoc->size);
copyLoc = (MEMBLK *) ((byte *)copyLoc +
copyLoc->size);
} else { /* Close up current free block */
curBlk = (MEMBLK *) ((byte *) curBlk +
curBlk->size);
copyLoc->flags = 0;
copyLoc->checkByte = CB;
copyLoc->prev = prevBlk;
copyLoc->size = spaceRecovered;
copyLoc->pointerNum = 0;
copyLoc->segment = seg;
saveBlk =(MEMBLK *) ((byte *)copyLoc +
copyLoc->size);
saveBlk->prev = copyLoc;
spaceRecovered = 0;
copyFree =(FREEBLK *)DATALOC(copyLoc);
copyFree->prev = prevFree;
if (prevFree != NULL) {
tmpFree = (FREEBLK *)
DATALOC(prevFree);
tmpFree->next = copyLoc;
}
copyFree->next = nextFree;
if (nextFree != NULL) {
tmpFree = (FREEBLK *)
DATALOC(nextFree);
tmpFree->prev = copyLoc;
}
prevBlk = copyLoc;
prevFree = copyLoc;
copyLoc = NULL;
}
}
} else { /* Free */
if (copyLoc == NULL)
copyLoc = curBlk;
spaceRecovered += curBlk->size;
nextFree = (MEMBLK *) (((FREEBLK *)
DATALOC(curBlk))->next);
curBlk = (MEMBLK *) ((byte *) curBlk + curBlk->size);
}
}
/* At this point copyLoc points to the beginning of the free area,
spaceRecovered is the size of the new free block, and saveBlk
points to the next free block in the segment */
if (copyLoc != NULL) {
copyLoc->checkByte = CB;
copyLoc->prev = prevBlk;
copyLoc->size = spaceRecovered;
copyLoc->pointerNum = 0;
copyLoc->segment = seg;
if (last) {
copyLoc->flags = BLK_LAST;
} else {
copyLoc->flags = 0;
saveBlk = (MEMBLK *)((byte *) copyLoc + copyLoc->size);
saveBlk->prev = copyLoc;
}
copyFree = (FREEBLK *) DATALOC(copyLoc);
copyFree->prev = prevFree;
if (prevFree != NULL) {
tmpFree = (FREEBLK *) DATALOC(prevFree);
tmpFree->next = copyLoc;
}
copyFree->next = nextFree;
if (nextFree != NULL) {
tmpFree = (FREEBLK *) DATALOC(nextFree);
tmpFree->prev = copyLoc;
}
mst[seg].free = copyLoc;
mst[seg].last = copyLoc;
}
}
[LISTING THREE]
/***** demo.c Demonstration program for memory manager
S. Peterson programmer 1/89
This program demonstrates the features of the memory manager.
**/
#include <stdio.h>
#include <stddef.h>
#include <process.h>
#include <memory.h>
#include "mem.h"
void blockFunc(void *, byte, uint, void *); /* Prototype, block function */
int main(void);
int
main()
{
void **p; /* Double pointer to block */
void *q; /* Single pointer to block */
/* Allocate a 30K buffer and 100 master pointers */
if (MemInit(30000l, 100) != TRUE)
exit(1);
/* Allocate a buffer of 1024 bytes. It is created as moveable and
undeletable */
if ((p = MemAlloc(1024)) == NULL)
printf("Error allocating 1024 bytes.\n");
MemLock(p); /* Make the block unmoveable */
q = *p; /* Get pointer to memory block */
memset(q, 0, 1024); /* Initialize block to 0 */
MemUnlock(p); /* Make the block moveable */
/* Note: q no longer valid */
MemCompact(); /* Cause memory to be compacted */
MemFree(p); /* Deallocate p */
/* Allocate a block with an associated function. */
if ((p = MemAllocFunc(1024, blockFunc, BLK_FUNCDELETE |
BLK_FUNCMOVE)) == NULL)
exit(2);
MemFree(p); /* Deallocate p */
return 0;
}
void
blockFunc(blockPtr, flags, length, newLoc)
void *blockPtr;
byte flags;
uint length;
void *newLoc;
{
if ((flags & BLK_FUNCMOVE) != 0) {
/* Perform some action when block moves */
}
if ((flags & BLK_FUNCDELETE) != 0) {
/* Perform some action when block is deleted */
}
}