/* MMHeapMemory.c, Copyright (c) by George Fankhauser, Swiss Federal Institute of Technology, Computer Engineering and Networks Laboratory. TOPSY -- A Teachable Operating System. Implementation of a tiny and simple micro kernel for teaching purposes. For further information, please visit http://www.tik.ee.ethz.ch/~topsy This software is provided under the terms of the GNU General Public Licence. A full copy of the GNU GPL is provided in the file COPYING found in the development root of Topsy. */ /* File: $Source: /usr/drwho/vault/cvs/topsy/Topsy/Memory/MMHeapMemory.c,v $ Author(s): George Fankhauser Affiliation: ETH Zuerich, TIK Version: $Revision: 1.22 $ Creation Date: Last Date of Change: $Date: 2000/07/13 09:41:01 $ by: $Author: gfa $ $Log: MMHeapMemory.c,v $ Revision 1.22 2000/07/13 09:41:01 gfa fixed bug: last element was beyond HEAPSIZE Revision 1.21 1999/12/13 21:48:29 ruf GNU General Public Licence Update Revision 1.20 1999/02/13 16:27:20 gfa *** empty log message *** Revision 1.19 1997/03/31 20:35:34 gfa adapted for global name changes (syscalls) * Revision 1.18 1997/03/27 14:14:03 gfa * changed trylock to correct lock() * * Revision 1.17 1997/03/26 09:31:00 gfa * rewrote the heap allocator. produces 50% less overhead, is much faster, * fully checked/reliable and written 3 pages source (1 less). all boils * down to a ridiculous 880 bytes of mips machine code :-) * * Revision 1.16 1997/03/24 19:15:28 gfa * removed debugging code * * Revision 1.15 1997/03/22 14:29:43 conrad * locks replace msg for heap * * Revision 1.14 1997/03/22 12:50:53 conrad * return of correct errorCode in case of failure of hmAlloc * * Revision 1.13 1997/03/19 21:42:06 conrad * debugging comments added * * Revision 1.12 1997/03/16 22:16:11 gfa * fixed almost unusable initial version (split/merge and free) * tried to add a bit reliability... * * Revision 1.11 1997/03/14 17:20:30 gfa * *** empty log message *** * * Revision 1.10 1997/03/14 11:24:44 conrad * Adding of a debugging message for hmFree * * Revision 1.9 1997/03/14 09:25:48 gfa * fixed expectedFrom bug (ThreadId* vs ThreadId) * this type-unsafety was not catched by -Wall ! * * Revision 1.8 1997/03/13 23:58:43 gfa * fixed hmAlloc * * Revision 1.7 1997/03/12 17:56:36 conrad * debugging version * * Revision 1.6 1997/03/11 08:13:34 gfa * fixed hmInit() * * Revision 1.5 1997/03/10 13:55:39 gfa * changes for HeapMemory made * * Revision 1.4 1997/03/09 20:48:22 gfa * *** empty log message *** * * Revision 1.3 1997/02/14 11:44:04 zitzler * syntax error in mergeFreeEntries deleted * * Revision 1.2 1997/02/13 16:06:45 zitzler * first implementation without error checking * * Revision 1.1 1997/02/12 16:19:04 zitzler * Initial revision * */ #include "Topsy.h" #include "Configuration.h" #include "Threads.h" #include "Syscall.h" #include "MMHeapMemory.h" #include "MMVirtualMemory.h" #include "MMMapping.h" #include "Lock.h" typedef enum {HM_FREED, HM_ALLOCATED} AreaStatus; typedef struct HmEntryDesc_t { AreaStatus status; struct HmEntryDesc_t* next; } HmEntryDesc; typedef HmEntryDesc* HmEntry; static HmEntry start = NULL; static HmEntry end = NULL; /* internal function prototypes */ static HmEntry findFree(unsigned long size); static void split(HmEntry entry, unsigned long int); static void compact(HmEntry at); /* a lock is needed in order to keep the heap pointers consistent. only * one kernel thread may be in hmAlloc and hmFree at a time */ static LockDesc hmLockDesc; static Lock hmLock; #define ALIGN 4 #define LEFTOVER (ALIGN*2) #define ENTRYSIZE(ptr) ((unsigned long)(ptr->next) - \ (unsigned long)ptr - sizeof(HmEntryDesc)) Error hmInit(Address addr) { start = (HmEntry)addr; start->next = (HmEntry)((unsigned long)addr + KERNELHEAPSIZE - sizeof(HmEntryDesc)); start->status = HM_FREED; end = start->next; end->next = NULL; end->status = HM_ALLOCATED; hmLock = &hmLockDesc; lockInit( hmLock); return HM_INITOK; } Error hmAlloc(Address* addressPtr, unsigned long int size) { HmEntry entry; if (size == 4) WARNING("Four bytes allocated. Possible pointer problem?"); size = size + (ALIGN - size % ALIGN); /* round up to multiple of words */ entry = start; *addressPtr = NULL; /*** here we enter a critical section */ lock(hmLock); /* try to find a free piece of memory */ entry = findFree(size); if (entry == NULL) { /* compact and try again */ compact(start); entry = findFree(size); } if (entry == NULL) { unlock( hmLock); return HM_ALLOCFAILED; } split(entry, size); *addressPtr = (Address)((unsigned long)entry + sizeof(HmEntryDesc)); unlock(hmLock); return HM_ALLOCOK; } Error hmFree(Address address) { HmEntry entry, addressEntry; /* check first if pointer is inside the heap */ if (((unsigned long)start > (unsigned long)address) || ((unsigned long)address >= ((unsigned long)end - LEFTOVER))) { WARNING("hmFree got non-heap pointer"); return HM_FREEFAILED; } /*** here we enter a critical section */ lock(hmLock); entry = start; addressEntry = (HmEntry)((unsigned long)address - sizeof(HmEntryDesc)); while (entry != NULL) { if (entry == addressEntry) break; entry = entry->next; } if (entry == NULL) { unlock( hmLock); return HM_FREEFAILED; } entry->status = HM_FREED; unlock( hmLock); return HM_FREEOK; } static HmEntry findFree(unsigned long size) { HmEntry entry = start; while (entry != NULL) { if (entry->status == HM_FREED && ENTRYSIZE(entry) >= size) break; entry = entry->next; } return entry; } static void split(HmEntry entry, unsigned long int size) { HmEntry new; if (ENTRYSIZE(entry) >= (size + sizeof(HmEntryDesc) + LEFTOVER)) { new = (HmEntry)((unsigned long)(entry) + sizeof(HmEntryDesc) + size); new->next = entry->next; new->status = HM_FREED; entry->next = new; } entry->status = HM_ALLOCATED; } static void compact(HmEntry at) { HmEntry atNext; while (at != NULL) { atNext = at->next; while ((at->status == HM_FREED) && (atNext != NULL)) { if (atNext->status != HM_FREED) break; at->next = atNext->next; /* collapse two free entries into one */ atNext = atNext->next; } at = at->next; } }