Re: A89: Re: memory management routines.
[Prev][Next][Index][Thread]
Re: A89: Re: memory management routines.
Heh, I just tried to run my memory manager code... ;)
Here's some that will actually work. Previously, it wouldn't even
compile!
--robin
Niklas Brunlid wrote:
>
> > I just finished writing a memory manager in C, providing support for the
> > normal malloc(), calloc(), realloc(), and free(). Because it's entirely
> > in C, it should compile for any of the ti calculators. This doesn't
> > provide support for things like memory protection, however, because that
> > gets into protected mode programming, which the z80 doesn't have, and i
> > have no idea how to do on the m68k.
>
> The TI-89/92+ have:
> #define malloc HeapAllocPtr
> #define free HeapFreePtr
> #define HeapAvail _ROM_CALL_8F
> #define HeapAlloc _ROM_CALL_90
> #define HeapAllocESTACK _ROM_CALL_91
> #define HeapAllocHigh _ROM_CALL_92
> #define HeapAllocThrow _ROM_CALL_93
> #define HeapAllocHighThrow _ROM_CALL_94
> #define HeapCompress _ROM_CALL_95
> #define HeapDeref _ROM_CALL_96
> #define HeapFree _ROM_CALL_97
> #define HeapFreeIndir _ROM_CALL_98
> #define HLock _ROM_CALL_99
> #define HeapLock _ROM_CALL_9A
> #define HeapGetLock _ROM_CALL_9B
> #define HeapMax _ROM_CALL_9C
> #define HeapRealloc _ROM_CALL_9D
> #define HeapSize _ROM_CALL_9E
> #define HeapUnlock _ROM_CALL_9F
> #define HeapMoveHigh _ROM_CALL_A0
> #define HeapEnd _ROM_CALL_A1
> #define HeapAllocPtr _ROM_CALL_A2
> #define HeapFreePtr _ROM_CALL_A3
>
> This can, however, be very useful anyway, since with these routines we have full
> control over what's happening... TI:s system happily moves stuff around.
>
> > I'm sure something like this hasn't been written for the ti86, and I
> > have no idea about the ti89.
> >
> > Anyways, i just thought these routines would be helpfull for all the
> > programmers out there who use C compilers
> > for their TI calculators.
> > Documentation is in the file header.
> >
> > The thing is thouroghly commented, so it shouldn't be too hard to
> > understand.
> >
> > --robin
>
> --------------------------------------------------------------------------------
>
<-- code snipped -->
> >
> > */
>
> / Niklas Brunlid
> Check out Prosit for the TI-89 / TI-92+ at http://prosit.ticalc.org
> Random PQF Quote follows:
>
> "This is Lord Mountjoy Quickfang Winterforth IV, the hottest dragon in the
> city. It could burn your head clean off."
> -- Captain Vimes addresses a band of rioters
> (Terry Pratchett, Guards! Guards!)
/*
Machine Independant Memory Management
by Robin Kirkman
email: misty@drrobin.yi.org
Version 1.0.2 <--- Seems to actually work now ;)
These routines provide trust-based memory management for those of you writing
code out there for bare systems. I wrote them for my ti89, which doesn't have
these calls, to my knowledge. If it does, well, I'm sure these will be usefull
for all those z80 programmers, cause the TI calcs w/ z80's i am -certain- do
not have this stuff. Happy Days!
This is just the standard malloc(), calloc(), realloc(), and free().
The one exception is _initialize_malloc(void *ram_start), which you need to call.
ram_start is assumed to be the bottom of a memory block, which is assumed to be
without an upper bound. If you don't call _initialize_malloc before you use any
of these calls, then your system will crash very quickly.
Feel free to use these routines in anything you like. All I want in return is a
copy of whatever you use them in.
This code is copyrighted Nov 21, 1999, by Robin Kirkman.
Modify it all you want, but you best be leaving my name in here ;)
Funtion Prototypes:
void _initlialize_malloc(void *ramstart);
void _set_start_ram(void *ramstart);
void _free_all();
void *malloc(size_t size);
void *calloc(num_t num, size_t size);
void *realloc(void *ptr, size_t size);
void *free(void *ptr);
_initialize_ram(void *ramstart);
Sets the starting address and clears any allocations.
_set_start_ram(void *ramstart);
Sets the starting ram. If you use this while your program is running, you can
have different areas with different allocations.
_free_all();
Frees all allocated blocks.
malloc(size_t size);
Allocates size bytes, and returns a pointer to them. If size is zero, does nothing.
calloc(num_t num, size_t size);
Allocates num*size bytes, and returns a pointer to them. If size or num is zero, does nothing.
realloc(void *ptr, size_t size);
Reallocates the block at ptr to size bytes, and returns a new pointer. All data is retained.
If ptr is null, then realloc acts like malloc.
If size is null, then realloc acts like free.
free(void *ptr);
Frees an allocated block. If the block is not found, free() returns a -1. If found, returns null.
NOTE: This is different from ANSI! In ansi, free() is typed as void (not void pointer), and it
has 'undefined behavior' (read: crashes) when ptr isn't an allocated block.
*/
typedef struct __malloc_block {
void *data;
size_t size;
struct __malloc_block *next;
} _malloc_block;
/*
_malloc_block is an element in a linked list which the memory manager uses to keep
track of where the allocated blocks are.
*/
static void *_ramstart;
// Where is the bottom of our ram?
static void *_first_malloc_block=0;
// Where is the first _malloc_block structure? This is set by the initialization routine.
void _set_start_ram(void *ramstart) {
_ramstart=ramstart;
}
void _free_all(){
_first_malloc_block=0;
}
void _initialize_malloc(void *ramstart) {
_set_start_ram(ramstart);
_free_all();
}
void *_find_free_ram(size_t size) {
/*
_find_free_ram is used internally to find a block that is big enough for size.
This is used in malloc, first to find space for another malloc_block, then
to find space for the data.
*/
_malloc_block *mblock,*mtmp;
void *f_address=0; // Our address that we are finding
int found_block=0; // Have we found it yet?
int mtmp_search_ok;
mblock=_first_malloc_block; // Get the first block. Assume we have been initialized.
if(!mblock) // If we have no blocks, the first chunk must be the beginning of ram
return _ramstart;
while(!found_block) {
f_address=0;
while(mblock->next) { // Search for a chunk of ram that is big enough
if((mblock->data)+(mblock->size)+size<((mblock->next)->data)) {
f_address=mblock->data+mblock->size; // Use this chunk.
// We know that this chunk is acceptable because the linked list of _malloc_block's
// are organized ascending by the data element.
break;
}
mblock=mblock->next; // Check next malloc_block...
}
if(!f_address)
f_address=mblock->data+mblock->size; // Otherwise, use the end of the last chunk
// The above check sees if our chunk address interrupted by a data block.
// Now we need to see if it is interrupted by a malloc_block
mtmp=_first_malloc_block;
mtmp_search_ok=1;
while(mtmp && mtmp_search_ok) {
if(mtmp+sizeof(_malloc_block)-1 >= f_address && mtmp < f_address+size) {
// Bogus block, it's interrupted by a malloc_block.
if(mtmp+sizeof(_malloc_block)+size<(mblock->next)->data) {
// If there's enough space at the end of this malloc_block for data block, shift it
// and restart the search
f_address=mtmp+sizeof(_malloc_block);
mtmp=_first_malloc_block;
if(mtmp+sizeof(_malloc_block)-1 >= f_address && mtmp < f_address+size) {
// What if the new location interferes with the first element?
if(mtmp+sizeof(_malloc_block)+size>(mblock->next)->data) {
// What if there's no room for it?
mtmp_search_ok=0;
// Restart the search for a block.
} else {
// If there -is- room for it...
f_address=mtmp+sizeof(_malloc_block);
}
}
// By setting mtmp to _first_malloc_block, we are going to not be able to
// check the first malloc_block in the next cycle. However, this is not a
// problem because either the block didn't interfere with the first
// malloc_block, or it has just been adjusted so that it doesn't. :)
} else {
// If there isn't space, then we have to continue searching between data blocks
mtmp_search_ok=0;
}
}
// If our block isn't interrupted by a malloc_block, then continue checking
mtmp=mtmp->next;
}
if(mtmp_search_ok) {
//Our data block has passed all tests, we can return it
found_block=1;
}
// If our block isn't okay, then go search for another candidate between the data blocks
}
// f_address now points to a block of ram at least size big. Happy days!
return f_address;
}
void *malloc(size_t size) {
_malloc_block *mblock,*mtmp;
void *t;
mblock=_find_free_ram(sizeof(_malloc_block));
// Find a place to put another _malloc_block structure
mtmp=_first_malloc_block;
if(!mtmp) {
// What if there are no _malloc_block's yet? IE- this is the first call to malloc
_first_malloc_block=mblock;
mblock->next=0;
mblock->size=size;
mblock->data=_find_free_ram(size);
return mblock;
}
while(mtmp->next) {
if((mtmp->next)->data > mblock)
break;
// Find the largest value of mtmp->data that is less than mblock.
// since the linked list is -always- organized ascending by mtmp->data,
// we can be assured that this is correct
}
t=mtmp->next;
mtmp->next=mblock;
mblock->next=t;
mblock->size=size;
mblock->data=_find_free_ram(size);
// We have just inserted the element. Or appended, if it was at the end of the list.
return mblock;
}
void *calloc(num_t num, size_t size)
{
// Calloc is silly, it wants two arguments. Stupid ancient ansi stuff. Oh well...
void *t,*i;
// If either one of our arguments is null, do nothing.
if(!(num*size))
return 0;
// Wipe the ram. That's the only good thing about calloc().
t=malloc(size*num);
for(i=t;i<t+size;i++)
*((char *)i)=0;
return t;
}
void *free(void *ptr) {
// If an unallocated pointer is passed, return a -1. Otherwise return null.
// This is against the ANSI typedef of free() !!!!!!
// ANSI says this: void free(void *ptr)
// Making free() an int shouldn't cause any problems anywhere.
// However, it -does- allow us to not have 'undefined' behavior when
// you attempt to free an unallocated pointer.
_malloc_block *mtmp,*mtp=0;
// If we are passed a NULL, we aren't sposed to do anything...
if(!ptr)
return 0;
// Go search for ptr...
mtmp=_first_malloc_block;
while(mtmp) {
if(mtmp->data = ptr)
break;
mtp=mtmp;
mtmp=mtmp->next;
}
if(!mtmp)
return -1; // Nope, you been passing me some shit...
if(!mtp) {
// There is only one allocated block, which we are removing...
_first_malloc_block=mtmp->next;
return 0;
}
mtp->next=mtmp->next;
// To remove the block, all we have to do is cut the _malloc_block structure out of the list.
return 0;
}
void *realloc(void *ptr, size_t size)
{
// Remember, we must return a null if ptr isn't allocated!
_malloc_block *mtmp;
void *t;
size_t i;
// If ptr is null, then do a malloc...
if(!ptr)
return malloc(size);
// If size is null, then free this junx.
if(!size)
return free(ptr);
mtmp=_first_malloc_block;
while(mtmp) {
if(mtmp->data = ptr)
break;
mtmp=mtmp->next;
}
if(!mtmp)
return 0; // We didn't find it. ANSI says that behavior should be 'undefined' in this case.
// I'm being nice and telling you it didn't work.
t=malloc(size);
for(i=0;i<size;i++)
*((char *)t+i)=*((char *)ptr+i);
// Copy over the old ram...
free(ptr);
return t;
}
References: