Moderator: MaxCoderz Staff
What do you mean by this?would something like a binning-system indexed by the log of the number of byte to be allocate be worth the complexity?
A bit of both, actually..benryves wrote:I guess the intended use is to rarely allocate memory in a batch (for example, at the start of a level) rather than constantly allocating and freeing memory during runtime?
Something like a part of Doug Lea's allocator except it would not necessarily need to be 8-byte alignedbenryves wrote:What do you mean by this?
Code: Select all
;; Vera - the calc lover's OS,
;; copyright (C) 2007 The Vera Development Team.
;;
;; This file provides memory allocation routines for handling the RAM.
;; It doesn't handle the Flash memory, in spite of it's name.
;
; This program is free software: you can redistribute it and/or modify
; it under the terms of the GNU General Public License as published by
; the Free Software Foundation, either version 3 of the License, or
; (at your option) any later version.
;
; This program is distributed in the hope that it will be useful,
; but WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
; GNU General Public License for more details.
;
; You should have received a copy of the GNU General Public License
; along with this program. If not, see <http://www.gnu.org/licenses/>.
; =====================
; The header structure is as follows:
;
; byte status; // Either MEM_TAKEN, MEM_FREE or MEM_END
; word size; // Also offset to next header
;
; Followed by <size> bytes of data. So an example of the data after
; RAMSTART would be:
;
; .db MEM_TAKEN ; Mark beginning of allocated memory
; .dw $XXXX ; Number of bytes allocated (also offset to next)
; .db <XXXX bytes of data>
;
; .db MEM_FREE ; Mark beginning of freed memory, but not end of list
; .dw $XXXX ; Number of freed bytes, offset to next
; .db <XXXX bytes of noise>
;
; .db MEM_TAKEN ; Mark beginnen of second block
; .dw $XXXX ; Number of bytes allocated (also offset to end)
; .db <XXXX bytes of data>
;
; .db MEM_END ; Anything other than FREE or TAKEN will do
;
; This assumes that three blocks have been allocated, and the second
; has yet been freed.
; ======================
MEM_TAKEN = $AA ; %10101010
MEM_FREE = $55 ; %01010101
MEM_END = $00 ; Anything other than FREE or TAKEN will do
MEM_EXECSTART = $8000
MEM_RAMSTART = $C000
MEM_RAMEND = STACKSTART - 300 ; Stay 300 bytes away from stack start
MIN_SPLIT_SIZE = 10 ; 3 bytes header + some payload
;; === memory_init ===
;;
;; Initialize the RAM for use (currently just clears it all, we could
;; consider doing something useful with it ;-))
;;
;; Authors:
;; Tim Franssen (mail@timendus.com)
memory_init:
push af
push hl
push de
push bc
ld hl,MEM_RAMSTART
ld de,MEM_RAMSTART+1
ld bc,MEM_RAMEND - MEM_RAMSTART - 1
xor a
ld (hl),a
ldir
pop bc
pop de
pop hl
pop af
ret
;; === memory_allocate ===
;;
;; Allocate a chunk of memory for data storage. The pointer you receive
;; can point to a memory block larger than you requested, but you can
;; not count on that. You also have no guarantee that the memory will be
;; executable (stored before $C000) or that it will be reset to zero (so
;; make sure you initialize it properly before using it).
;;
;; Also, make sure you store the received pointer away carefully, because
;; you'll be needing it to free the memory later.
;;
;; Authors:
;; Tim Franssen (mail@timendus.com)
;;
;; Pre:
;; bc = number of bytes that you want allocated
;;
;; Post:
;; c = set if memory was not available
;; hl = pointer to allocated memory if c is reset
;; The accumulator will be destroyed
memory_allocate:
push de
ld hl,MEM_RAMSTART ; Start searching for free space from
memory_allocate_search: ; beginning of data RAM
ld a,(hl)
cp MEM_TAKEN
jp z,memory_allocate_next ; No space free here
cp MEM_FREE
jp z,memory_allocate_checksize ; Space free here, but is it enough?
; It's neither taken nor freed, so we've reached the end of the list
memory_allocate_found:
; Allocate memory at hl as ours!
; TODO: Check if we've crossed MEM_RAMEND!
ld a,MEM_TAKEN
ld (hl),a ; Mark it as taken
inc hl
ld (hl),b ; Store it's size
inc hl
ld (hl),c
inc hl
push hl
add hl,bc ; Get a pointer to the next node
ld (hl),MEM_END ; And mark it as the end of the list
pop hl
or a ; Clear carry flag
pop de
ret ; Return pointer in hl
memory_allocate_next:
; This one is taken, advance pointer to next
inc hl
ld d,(hl) ; Get it's size
inc hl
ld e,(hl)
memory_allocate_next_go: ; Label used by checksize
inc hl
add hl,de ; Add it to the pointer
jp memory_allocate_search ; and move on
memory_allocate_checksize:
; We've found a freed space, is it big enough?
inc hl ; Get it's size
ld d,(hl)
inc hl
ld e,(hl)
; "cp de,bc" ; Compare it to requested size
ex de,hl
or a
sbc hl,bc
add hl,bc
ex de,hl
jp c,memory_allocate_next_go ; It doesn't fit, find next
; It does fit, mark it as taken
dec hl
dec hl
ld a,MEM_TAKEN
ld (hl),a
inc hl
; Split it up or use it whole?
; de = size of block
; bc = requested size
push hl
ld hl,MIN_SPLIT_SIZE-1
add hl,bc
sbc hl,de ; We know carry is reset
pop hl
; c = de >= bc+10 = split
; nc = de < bc+10 = use whole
jp c,memory_allocate_checksize_split
; Allocate the entire block, don't change it's size
inc hl
inc hl ; Fix pointer to return
pop de
ret ; We know carry is reset
memory_allocate_checksize_split:
; Split the block up in a TAKEN and a FREE block
; de = old block size
; bc = requested size
; hl = pointer to old block+1
; new FREE block size = old block size - requested size - 3
ld (hl),b ; Change size of old block
inc hl
ld (hl),c
inc hl
push hl ; Save pointer to data
add hl,bc ; Pointer to new FREE block
ld a,MEM_FREE
ld (hl),a
ex de,hl
dec hl ; hl = old block size - 3
dec hl
dec hl ; Carry should be reset by add hl,bc
sbc hl,bc ; hl -= requested size
ex de,hl
inc hl
ld (hl),d ; Store calculated size of new FREE block
inc hl
ld (hl),e
pop hl ; Restore pointer to return
pop de
ret ; Carry should be reset by sbc
;; === memory_allocate_exec ===
;;
;; Allocate a chunk of memory for a RAM application - TODO
;;
;; Authors:
;; Tim Franssen (mail@timendus.com)
;;
;; Pre:
;; hl = number of bytes that you want allocated
;;
;; Post:
;; c = set if memory was not available
;; specified number of bytes have been allocated for you at $8000 if c is reset
memory_allocate_exec:
or a ; clear carry flag
ret
;; === memory_free ===
;;
;; Free a chunk of previously allocated memory
;;
;; Authors:
;; Tim Franssen (mail@timendus.com)
;;
;; Pre:
;; hl = pointer to memory to free
;;
;; Post:
;; The accumulator will be destroyed
;;
;; Warning:
;; hl needs to point to the beginning of the allocated
;; memory, as you got it from memory_allocate, or
;; $8000 in case of memory_allocate_exec! Give it a wrong
;; pointer and things will go wrong badly! (Or, to use the
;; proper terminology: "the result is undefined" :-P)
memory_free:
; TODO: Check for allocate_exec memory
memory_free_RAM:
; Mark my block as FREE
dec hl
dec hl
dec hl
ld a,MEM_FREE
ld (hl),a
; And defragment the linked list
push de
push bc
call memory_defragment
pop bc
pop de
ret
; === memory_defragment ===
; Defragment the list from the start, joining adjecent FREE nodes
; Destroys de and bc
memory_defragment:
ld hl,MEM_RAMSTART
memory_defragment_loop:
ld a,(hl) ; What is my type?
inc hl
ld d,(hl) ; Already fetch the size while we're at it
inc hl
ld e,(hl)
inc hl
cp MEM_TAKEN ; If it's a TAKEN node, just skip it
jp z,memory_defragment_next
cp MEM_FREE ; If it's a FREE node, go and check it
jp z,memory_defragment_checknode
; It's neither taken nor freed, so we've reached the end of the list
; and we know that it's defragmented, so we're done
ret
memory_defragment_next:
; This node is taken, advance pointer to next
add hl,de
jp memory_defragment_loop
memory_defragment_checknode:
; This node is free, what about the next one?
push hl
add hl,de
ld a,(hl) ; What is the type of the next node?
cp MEM_TAKEN ; If it's taken, there's nothing more to
jp z,memory_defragment_checknode_done ; join here
cp MEM_FREE ; If it's free, join with this one
jp z,memory_defragment_checknode_join
; Otherwise, we've found the end of the list, so there's only empty space
; after us, and we should become empty space too
pop hl ; Get pointer to block type
dec hl
dec hl
dec hl
ld a,MEM_END ; Mark it as the end of the list
ld (hl),a
ret ; Done!
memory_defragment_checknode_done:
; We've added as many sizes to de as we can, and we should continue our
; main loop from the last checked place (hl)
ld b,h ; Save pointer to the next taken node
ld c,l
pop hl ; Restore pointer to the checked node
dec hl
ld (hl),e ; Store new calculated size of checked node
dec hl
ld (hl),d
ld h,b ; Restore pointer to next node
ld l,c
jp memory_defragment_loop ; And move on from there
memory_defragment_checknode_join:
; hl points to a node that is free, and that comes after us; calculate it's
; size and add it to our own size
inc hl
ld b,(hl) ; Get block size
inc hl
ld c,(hl)
inc bc ; Add header size
inc bc
inc bc
ex de,hl
add hl,bc ; Add it to our size
ex de,hl
pop hl ; Go and check the node that is now
jp memory_defragment_checknode ; after us, given the new size
; ===================
; End of file
; ===================
No, it's length+previous+next, 6 bytes, it only registers allocated blocksTimendus wrote:I thought that's how you implemented it. Shouldn't it be 5 bytes overhead then?