Category : Assembly Language Source Code
Archive   : RHSTDLIB.ZIP
Filename : MEMORY.ASM

extrn PSP:word
stdlib segment para public 'slcode'
assume cs:stdlib
;
; Memory allocation routines: MemInit, malloc, and free.
;
;
; Local variables:
;
StartOfHeap dw ?
SizeOfHeap dw ?
FreeSpace dw ?
;
; Memory manager data structure:
;
mmstruct struc
blksize dw ?
bwdptr dw ?
fwdptr dw ?
refcnt dw ?
freebwdptr dw ? ;Only if in the free list.
freefwdptr dw ? ;Only if in the free list.
ends
;
; When using es and ds as pointers into the heap, the following equates
; come in handy.
;
esptr equ word ptr es:[0]
dsptr equ word ptr ds:[0]
;
NIL equ 0
;
;
; MemInit- Initializes the memory manager.
;
; On entry- DX contains the number of paragraphs of memory to reserve
; for other programs. The default (in shell.asm) is 0. If
; you intend to execute other programs from the program you're
; writing, you will have to reserve an appropriate amount of
; space for that program. If you attempt to reserve too
; much space, then this code splits the available free memory
; in half and gives half to the heap and reserves half for
; other programs. If this is desirable, simply set DX to
; 0ffffh before calling MemInit.
;
; On Exit- No error if carry is clear. In such a case, CX contains
; the number of paragraphs of memory actually allocated.
; AX contains the starting segment address of the free
; memory block.
;
; If carry is set, then an error occurred, AX contains the
; error code (DOS).
;
; WARNING: for this routine to work properly, the calling program has to
; declare (and initialize) a word variable by the name PSP which contains
; the program's program segment prefix value. Furthermore, the last segment
; in the program must be "zzzzzzseg" and this guy should NOT contain any
; valid data.
;
public sl_MemInit
sl_MemInit proc far
push bx
push dx
push es
;
; Compute program size, in paragraphs:
;
mov ax, seg PSP
mov es, ax
mov bx, es:PSP
mov es, bx
mov ax, seg zzzzzzseg
sub ax, bx
inc bx ;Safety margin
inc bx
mov ah, 4ah ;Memory block resize opcode
int 21h
;
; Now ask for a ridiculous amount of memory so we can find out how much is
; available.
;
mov bx, 0ffffh
mov ah, 48h ;Alloc block opcode
int 21h
;
;
; Allocate storage for the heap.
;
cmp bx, dx ;See if DX is too large.
ja GoodHeap
shr bx, 1 ;Use half remaining space.
jmp short SetNewAlloc
;
GoodHeap: sub bx, dx ;Make room for other apps.
SetNewAlloc: cmp bx, 10h ;Make sure there is some room.
jbe ErrorAlloc2
mov ah, 48h ;Alloc block opcode
int 21h
jc ErrorAlloc ;Shouldn't happen, but...
;
; Okay, we've just allocated the block, now set up our own local variables
; so we can keep track of the data.
;
mov cs:StartOfHeap, ax ;Save pointer to memory.
mov cs:FreeSpace, ax ;Save pointer to 1st free blk.
mov cs:SizeOfHeap, bx ;Size of heap in paragraphs.
mov es, ax ;Init pointer to heap.
xor ax, ax
mov esptr.blksize, bx ;Size of this block (paras).
mov esptr.bwdptr, ax ;Back pointer is NIL.
mov esptr.fwdptr, ax ;Fwd pointer is NIL.
mov esptr.refcnt, ax ;Reference Count is zero.
mov esptr.freebwdptr, ax ;Free list bwd ptr is NIL.
mov esptr.freefwdptr, ax ;Free list fwd ptr is NIL.
mov cx, bx ;Return size in CX
mov ax, cs:StartOfHeap
clc
jmp MemInitDone
;
ErrorAlloc2: mov ax, 8 ;Insufficient memory error.
ErrorAlloc: stc
MemInitDone: pop es
pop dx
pop bx
ret
sl_MemInit endp
;
;
;
;
;============================================================================
;
; * * * * * ***** *****
; ** ** * * * * * * * *
; * * * * * * * * * * *
; * * * ***** * * * * *
; * * * * * * * * *
; * * * * * * * * * *
; * * * * ***** ***** ***** *****
;
;============================================================================
;
;
; malloc- On entry, CX contains a byte count. Malloc allocates a block
; of storage of the given size and returns a pointer to this block
; in ES:DI. The value in ES:DI is always normalized, so you can
; compare pointers allocated via malloc as 32-bit values. Note
; that malloc always allocates memory in paragraph chunks.
; Therefore, this routine returns the actual number of bytes of
; memory allocated in the CX register (this may be as much as 15
; greater than the actual number asked for).
;
; Malloc returns carry clear if it allocated the storage without
; error. It returns carry set if it could not find a block large
; enough to satisfy the request.
;
;
; Data structure for memory allocation blocks:
;
; offset:
;
; 0 Size of Blk
; 2 Back link
; 4 Fwd Link
; 6 Reference Count
; 8 Data, if this block is allocated, prev link if on free list.
; 10 Data, if this block is allocated, next link if on free list.
;
;
;
public sl_malloc
sl_malloc proc far
push ax
push si
push ds
;
; Convert byte count to paragraph count, since we always allocate whole
; paragraphs.
;
add cx, 8 ;We have six bytes of overhead!
rcr cx, 1 ;Use rcr because of add above.
adc cx, 0
shr cx, 1
adc cx, 0
shr cx, 1
adc cx, 0
shr cx, 1
adc cx, 0
;
; Go find a block in the free list which is large enough.
;
; Uses the following algorithm:
;
;
cmp cs:FreeSpace, 0 ;See if no free space.
jz MemoryFull
mov ds, cs:FreeSpace
mov ax, ds ;In case first block is it.
FindBlk: cmp cx, dsptr.blksize ;See if blk is large enuf.
jbe FoundBlk ;Go for it!
mov ax, dsptr.freefwdptr ;Get ptr to next free block.
mov ds, ax ;Set up pointer.
or ax, ax ;See if NIL
jnz FindBlk ;Repeat until NIL.
;
; If we drop down here, we've got some big problems.
;
MemoryFull: stc
pop ds
pop si
pop ax
mov es, cs:StartOfHeap ;In case they use this ptr
mov di, 8 ; anyway.
ret
;
; When we come down here, we've found a block large enough to satisfy the
; current memory request. If necessary, split the block up into two
; pieces and return the unused half back to the free pool.
;
FoundBlk: jne SplitBlock
;
;
;
;***************************************************************************
; Exact fit, remove this guy from the free list and go for it!
;***************************************************************************
;
; There are four cases to deal with if this is an exact fit:
;
; 1) The block we're allocating is the first block in the free list.
; In this case, FreeSpace points at this block and the freebwdptr
; entry is NIL.
;
; 2) The block we're allocating is neither the first or last in the
; free list.
;
; 3) The block we're allocating is the last block in the free list.
; In this case, the freefwdptr will be NIL.
;
; 4) The block is both the first and last (i.e., only) block in the
; the free list.
;
; At this point, DS points at the block we're going to allocate.
;
mov ax, dsptr.freefwdptr ;Pointer to next free block.
cmp dsptr.freebwdptr, NIL ;First item in list?
jnz NotFirst
;
; Case (1) and (4) drop down here.
;
; If this is the first free block in the free link list, point FreeSpace
; beyond this guy rather than going through the usual linked list stuff.
;
; AX contains a pointer to the next free block (after this one) if it exists.
; DS points at the current free block.
;
; Since we are removing the first free block, we need to update the FreeSpace
; pointer so that it points at the next free block in the free block list.
;
mov cs:FreeSpace, ax ;Note: AX may be NIL if case (4).
;
; See if there is another block after this one. If not (case 4) then jump
; off to FixThisBlk.
;
or ax, ax ;Is there another free blk?
jz FixThisBlk ;If not, don't patch next adrs.
;
; Case (1), only, down here. The current block is the one we want and
; there is another free block after this one. AX Points at the next free
; block. DS points at the current block.
;
mov es, ax ;Point ES at next free block.
mov esptr.freebwdptr, NIL ;Set next guy's back link to NIL.
jmp short FixThisBlk
;
; If the current block is not the first free block in the free block list
; handle it down here. This corresponds to cases 2 or 3. On entry, DS
; points at the current block, AX points at the next free block (if present).
;
NotFirst: mov es, dsptr.freebwdptr ;Get ptr to prev blk.
mov esptr.freefwdptr, ax ;Skip over current blk.
mov ax, es ;Load AX with prev blk adrs.
;
; Now we need to figure out if there is a next free block (is this case 2?).
;
cmp dsptr.freefwdptr, NIL
jz FixThisBlk
;
; Definitely Case (2) here. Patch the next free block's prev field with
; the address of the previous block.
;
mov es, dsptr.freefwdptr ;Point ES at next block.
mov esptr.freebwdptr, ax ;Save link to prior block.
;
; All four cases converge down here to clean up things and store the
; overhead info for the newly allocated block.
;
FixThisBlk: mov dsptr.blksize, cx ;Save its size.
mov dsptr.refcnt, 1 ;Reference count = 1.
mov di, 8 ;Pointer to data area.
mov ax, ds
mov es, ax
shl cx, 1 ;Convert paragraph size to
shl cx, 1 ; bytes.
shl cx, 1
shl cx, 1
pop ds
pop si
pop ax
clc
ret
;
;****************************************************************************
; The current free block is bigger than we need, SPLIT it in half down here.
;****************************************************************************
;
;
; If allocating this block splits a free block in half, we handle that
; down here.
;
SplitBlock: mov ax, ds ;Get start of block.
add ax, dsptr.blksize ;Add in size of block.
sub ax, cx ;Subtract part we're keeping.
mov es, ax ;Point at data block.
mov esptr.blksize, cx ;Save size of block
mov esptr.bwdptr, ds ;Save back pointer.
mov esptr.refcnt, 1 ;Init reference count.
mov ax, dsptr.fwdptr ;Get prev fwd ptr.
mov dsptr.fwdptr, es ;Save new fwd point in free blk.
mov esptr.fwdptr, ax ;New forward pointer for us.
mov si, es ;Save ptr to this blk.
mov es, ax ;Point es at last blk.
mov esptr.bwdptr, si ;Chain it in properly.
mov es, si ;Restore so we can return it.
mov ax, dsptr.blksize ;Compute new size of free blk.
sub ax, cx
mov dsptr.blksize, ax
mov di, 8 ;Init pointer to data.
shl cx, 1 ;Convert paragraph size to
shl cx, 1 ; bytes.
shl cx, 1
shl cx, 1
pop ds
pop si
pop ax
clc
ret
;
sl_malloc endp
;
;
;
;===========================================================================
;
; ****** ***** ****** ******
; * * * * *
; * * * * *
; **** * *** **** ****
; * * * * *
; * * * * *
; * * * ****** ******
;
;===========================================================================
;
; Free- Returns a block of storage to the free list.
;
; On Entry- ES:DI points at the block to free.
; On Exit- Carry is clear if free was okay, set if invalid pointer.
;
;
public sl_free
sl_free proc far
push ax
push si
push ds
push es
mov si, di
;
; See if this is a valid pointer:
;
cmp si, 8
jne BadPointer
mov si, es ;Make seg ptr convenient.
mov ds, cs:StartOfHeap
cmp si, cs:StartOfHeap ;Special case if first block.
jne Not1stBlock
;
; The block the user wants to free up is the very first block. Handle that
; right here.
;
cmp dsptr.refcnt, 0
je BadPointer
dec dsptr.refcnt ;Decrement reference count.
jnz QuitFree ;Done if other references.
;
; Call coalesce to possibly join this block with the next block. We do not
; have to check to see if this call joins the current block with the prev
; block because the current block is the very first block in the memory
; space.
;
call Coalesce
;
; Adjust all the pointers as appropriate:
;
mov dsptr.freebwdptr, NIL
mov ax, cs:FreeSpace ;Get and set up the fwd ptr.
mov dsptr.freefwdptr, ax
mov es, cs:FreeSpace
mov esptr.freebwdptr, ds ;Set up other back pointer.
mov cs:FreeSpace, ds ;Fix FreeSpace.
jmp short QuitFree
;
;
BadPointer: stc
jmp short Quit2
;
QuitFree: clc
Quit2: pop es
pop ds
pop si
pop ax
ret
;
; If this is not the first block in the list, see if we can coalesce any
; free blocks immediately around this guy.
;
Not1stBlock: cmp esptr.refcnt, 0
je BadPointer
dec esptr.refcnt ;Decrement reference count.
jnz QuitFree ;Done if other references.
;
call Coalesce
jc QuitFree
;
; Okay, let's put this free block back into the free list.
;
mov ax, cs:FreeSpace
mov esptr.freefwdptr, ax ;Set as pointer to next item.
mov esptr.freebwdptr, NIL ;NIL back pointer.
mov cs:FreeSpace, es
jmp QuitFree
;
sl_free endp
;
;
; Coalesce routine: On entry, ES points at the block we're going to free.
; This routine coalesces the current block with any free blocks immediately
; around it and then returns ES pointing at the new free block.
; This routine returns the carry flag set if it was able to coalesce the
; current free block with a block immediately in front of it.
; It returns the carry clear if this was not the case.
;
;
Coalesce proc near
push ds
push es
;
mov ds, esptr.fwdptr ;Get next contiguous block.
cmp dsptr.refcnt, 0 ;Is that block free?
jnz NextBlkNotFree
;
; If the next block is free, merge it into the current block here.
;
; Memory arrangement is currently something like this:
;
; +------------------------+ +---------+ <-These are dbl links.
; | | | |
; |prevfree| |CurFreeBlk| |FollowingBlk| |NextFreeBlk|
;
; We want to wind up with:
;
;
; +------------------------------------------+ <-These are dbl links.
; | |
; |prevfree| |CurFreeBlk| |FollowingBlk| |NextFreeBlk|
;
;
; First, merge the current free block and the following block together.
;
mov ax, dsptr.blksize ;Get size of next block.
add esptr.blksize, ax ; Join the blocks together.
mov ax, dsptr.fwdptr
mov esptr.fwdptr, ax
or ax, ax
jz DontSetBwd
push ds
mov ds, ax
mov dsptr.bwdptr, es
pop ds
;
; Make sure that there is a |prevfree| block.
;
DontSetBwd: mov ax, dsptr.freebwdptr
or ax, ax
jz SetFreeSpcPtr
;
; prevfree.fwd := following.fwd;
;
mov es, dsptr.freebwdptr ;Point ES at previous guy.
mov ax, dsptr.freefwdptr
mov esptr.freefwdptr, ax ;Skip over current guy.
;
; If the fwd pointer is NIL, no need to continue.
;
or ax, ax ;See if end of list.
jz NextBlkNotFree
;
; nextfree.bwd := following.bwd (prevfree).
;
mov ax, es ;Save ptr to this guy.
mov es, dsptr.freefwdptr
mov esptr.freebwdptr, ax
jmp short NextBlkNotFree
;
; If FollowingBlk is the first free block in the free list, we have to
; execute the following code.
;
SetFreeSpcPtr: mov es, dsptr.freefwdptr
mov esptr.freebwdptr, NIL
mov cs:FreeSpace, es
;
;
;
; After processing the block following this block, or if the next block
; was not free, come down here and check to see if the previous block
; was free.
;
NextBlkNotFree: pop es ;Restore pointer to current block.
push es
mov ax, esptr.bwdptr
or ax, ax ;Is it a NIL pointer
jz NoPrevBlock
mov ds, ax
cmp dsptr.refcnt, 0 ;Is that block free?
jnz NoPrevBlock
;
; Okay, the block in front is free. Merge the current block into that one.
;
mov ax, esptr.blksize
add dsptr.blksize, ax
mov ax, esptr.fwdptr
mov dsptr.fwdptr, ax
or ax, ax ;See if there is a next blk.
jz NoNextBlk
mov es, ax
mov esptr.bwdptr, ds
NoNextBlk: stc
pop es
pop ds
ret
;
NoPrevBlock: clc
pop es
pop ds
ret
Coalesce endp
;
;
;============================================================================
;
; ***** ******* * * * ***** *****
; * * * * * * * * * * *
; * * * * * * * * * *
; ***** ***** ***** * * * * *
; * * * * * * * * * *
; * * * * * * * * * * *
; * * ******* * * ***** ***** ***** *****
;
;============================================================================
;
;
; REALLOC - This routine expects a pointer in ES:DI and a new size in CX.
; If the specified block is larger than the value in CX then
; realloc shrinks the size of the block and returns the left over
; information to the system heap. If CX is larger than the speci-
; fied block then realloc allocates a new block and copies the
; data from the old block to the new block and then frees the
; old block. In any case, realloc returns a pointer to the
; (possibly new) block in ES:DI. Carry=0 on return if no error,
; carry=1 on return if there wasn't enough room on the heap to
; reallocate a larger block.
;
public sl_realloc
sl_realloc proc far
cmp di, 8 ;Is this a realistic pointer?
jz DoREALLOC
stc ;Return with error, if not.
ret
;
DoREALLOC: push ax
push cx
push ds
push si
;
;
; Convert byte count to paragraph count, since we always allocate whole
; paragraphs.
;
add cx, 8 ;We have eight bytes of overhead!
rcr cx, 1 ;Use rcr because of add above.
adc cx, 0
shr cx, 1
adc cx, 0
shr cx, 1
adc cx, 0
shr cx, 1
adc cx, 0
;
; See if the new block size is larger or smaller than the old block size.
;
cmp cx, esptr.BlkSize
ja MakeBigger
;
; New desired size is less than or equal to the current size. If no more
; than 32 bytes larger, don't even bother with the operation.
;
inc cx
inc cx
cmp cx, esptr.BlkSize
jae ReallocDone
dec cx
dec cx
;
; Okay, the new block size is seriously smaller here. Turn the last group
; of bytes into a free block.
;
mov ax, es ;Get ptr to block
add ax, cx ;Add in new length
mov ds, ax ;Point at new block.
mov ax, esptr.BlkSize ;Compute the size of the
sub ax, cx ; new block.
mov dsptr.BlkSize, ax ;Save away the link.
mov dsptr.bwdptr, es ;Set up back pointer.
mov ax, esptr.fwdptr ;Copy old fwd ptr to new
mov dsptr.fwdptr, ax ; fwd ptr.
mov dsptr.refcnt, 1 ;Init reference count to 1.
mov esptr.fwdptr, ds ;Set up new fwd ptr.
mov esptr.BlkSize, cx ;Set up new length.
push es
mov di, 8
mov ax, ds
mov es, ax
call sl_free ;Free the new block.
mov di, 8
pop es ;Get pointer to original blk
;
ReAllocDone: pop si
pop ds
pop cx
pop ax
clc
ret
;
;
;
; If they had the nerve to want this block larger, come down here and allocate
; a new block, copy the old data to the new block, and then free the old block.
;
;
MakeBigger: mov ax, es ;Preserve pointer to old blk.
mov ds, ax
mov si, di ;Contains "8".
call sl_malloc ;Allocate new block.
jc BadRealloc
;
; Okay, copy the old block to the new block. Note that both SI and DI
; contain 8 at this point. We can make this assumption here because,
; after all, this is the memory manager code and it knows the internal
; representation.
;
mov cx, dsptr.BlkSize ;Get original block size
shl cx, 1 ;Convert from paragraphs
shl cx, 1 ; to word count.
shl cx, 1
pushf
cld
rep movsw ;Note we're moving words!
popf
;
; Okay, free up the old block and we're done.
;
mov di, 8
push es ;Save ptr to new block.
mov ax, ds
mov es, ax
call sl_free
clc
mov di, 8 ;Restore new block ptr.
pop es
pop si
pop ds
pop cx
pop ax
ret
;
BadRealloc: stc
pop si
pop ds
pop cx
pop ax
ret
sl_realloc endp
;
;
;
;
;============================================================================
;
; ******** * * ******** ******** ******* *******
; * * * * * * * * * * *
; * * * * * * * * * * *
; * * * * ******** ******** * *******
; * * * * * * * * *
; * * * * * * * * *
; * * * * * * * * *
; ******** ******** * * * * *
;
;============================================================================
;
;
; Dupptr - Bumps up the reference count for a particular pointer by one.
; Returns carry = 1 if initial pointer is illegal, returns carry=0
; if no error. Returns pointer in ES:DI. You must pass the pointer
; to increment in ES:DI.
;
public sl_DupPtr
sl_DupPtr proc far
cmp di, 8 ;See if this is a valid ptr.
je GoodPtr
stc
ret
;
GoodPtr: inc esptr.refcnt ;Bump up the reference cnt.
clc
ret
sl_DupPtr endp
;
;
;============================================================================
;
; ***** ***** ***** * * * * ***** * *****
; * * * ** * * * * * * *
; * *** * * * * ***** *** ***** * *
; * * * * ** * * * * * *****
; * * * * * * * * * * *
; ***** ***** ***** * * * * ***** * * *
;
;============================================================================
;
; IsInHeap- Returns carry clear if the pointer passed in es:di is within
; the heap. Returns carry set if this pointer is outside the
; heap.
;
public sl_IsInHeap
sl_IsInHeap proc far
push ax
push bx
mov bx, es
mov ax, cs:StartOfHeap
cmp bx, ax
jb Outside
add ax, cs:SizeOfHeap
mov bx, es
cmp bx, ax
ja Outside
clc
pop bx
pop ax
ret
;
Outside: stc
pop bx
pop ax
ret
sl_IsInHeap endp
;
;
;
;
;============================================================================
;
; ***** ***** ***** ***** *****
; * * * * * * *
; * *** ***** * *****
; * * * * * *
; * * * * * *
; ***** ***** * * * *
;
;============================================================================
;
; IsPtr- Returns the carry flag clear if es:di points at the beginning
; of an allocated block in the heap. Returns with the carry
; flag clear if es:di points at a deallocated block.
;
public sl_IsPtr
sl_IsPtr proc far
cmp di, 8 ;All of our ptrs have an offset of 8.
jne NotPtr2
push ax
push bx
push es
mov ax, es
;
mov bx, cs:StartOfHeap
CmpLoop: cmp bx, ax
je MightBe
ja NotPtr
mov es, bx
mov bx, esptr.fwdptr
or bx, bx ;See if NIL link.
jnz CmpLoop
;
NotPtr: pop es
pop bx
pop ax
NotPtr2: stc
ret
;
; Might be the pointer, let's see if this guy's allocation count is greater
; than zero.
;
MightBe: mov es, bx
cmp esptr.blksize, 0
je NotPtr
clc
pop es
pop bx
pop ax
ret
sl_IsPtr endp
;
;
;
stdlib ends
;
;
zzzzzzseg segment para public 'zzzzzz'
LastBytes db 16 dup (?)
zzzzzzseg ends
end