# HG changeset patch # User Jonathan Pevarnek # Date 1307887779 14400 # Node ID 967a56b96d13529b5f4db61c41c21a200907f426 # Parent 4473e746fe5ac7d81f7302c3475ea2766074135f first attempt at redoing malloc, seems to work. The program level is not currently functional. diff -r 4473e746fe5a -r 967a56b96d13 Makefile --- a/Makefile Sat Jun 11 16:40:48 2011 -0400 +++ b/Makefile Sun Jun 12 10:09:39 2011 -0400 @@ -14,7 +14,7 @@ OSBINS=shell PROGBINS=hello ls echo -shell_OBJS=src/os/shell.o src/os/std.o src/os/fs.o src/os/string.o src/os/stdio.o src/os/scall.o arch/arch.a +shell_OBJS=src/os/shell.o src/os/std.o src/os/fs.o src/os/string.o src/os/stdio.o src/os/scall.o src/os/heap.o arch/arch.a hello_OBJS=src/prog/hello.o src/prog/std.o src/prog/string.o ls_OBJS=src/prog/ls.o echo_OBJS=src/prog/echo.o src/prog/std.o src/prog/string.o @@ -119,8 +119,9 @@ # DO NOT DELETE -src/dynamic.o: include/std.h include/die.h include/string.h include/stack.h -src/sarpn.o: include/std.h include/die.h include/string.h +src/dynamic.o: include/std.h include/die.h include/memHead.h include/string.h +src/dynamic.o: include/stack.h +src/sarpn.o: include/std.h include/die.h include/memHead.h include/string.h src/sarpn.o: include/operations.h include/stack.h -src/testFS.o: include/std.h include/die.h include/os/fs.h include/error.h -src/testFS.o: include/os/fsStructs.h +src/testFS.o: include/std.h include/die.h include/memHead.h include/os/fs.h +src/testFS.o: include/error.h include/os/fsStructs.h diff -r 4473e746fe5a -r 967a56b96d13 include/memHead.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/include/memHead.h Sun Jun 12 10:09:39 2011 -0400 @@ -0,0 +1,10 @@ +#ifndef __MEMHEAD_H +#define __MEMHEAD_H + +struct HEADER{ + struct HEADER *next; + size_t size; +}; +typedef struct HEADER Header; + +#endif diff -r 4473e746fe5a -r 967a56b96d13 include/os/heap.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/include/os/heap.h Sun Jun 12 10:09:39 2011 -0400 @@ -0,0 +1,12 @@ +#ifndef __HEAP_H +#define __HEAP_H + +#include + +#define PageSize 4096 + +void heap_init(size_t memSize); +void* allocHeap(size_t size, size_t *ammt); +void freeHeap(void *ptr); + +#endif diff -r 4473e746fe5a -r 967a56b96d13 include/std.h --- a/include/std.h Sat Jun 11 16:40:48 2011 -0400 +++ b/include/std.h Sun Jun 12 10:09:39 2011 -0400 @@ -1,8 +1,9 @@ -#include - #ifndef __STD_H #define __STD_H +#include +#include + #define assert(x) do { if(!(x)) die(); } while (0) //min and max function definitions @@ -28,18 +29,11 @@ //MALLOC CODE -#ifdef OSLEVEL -struct HEADER{ - struct HEADER *next; - size_t size; -}; -typedef struct HEADER Header; - typedef Header blockUnit; void malloc_init(size_t memSize); void* malloc(size_t size); +void* moreMem(size_t blocks); void free(void *ptr); -#endif #endif diff -r 4473e746fe5a -r 967a56b96d13 src/os/heap.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/os/heap.c Sun Jun 12 10:09:39 2011 -0400 @@ -0,0 +1,59 @@ +#include +#include + +static Header base; +static Header *allocp = NULL; + +void heap_init(size_t memSize) +{ + allocp = &base; + allocp->size = 0; + allocp->next = (void*)HEAP_START; + allocp->next->next = &base; + allocp->next->size = (memSize - HEAP_START)/PageSize; +} + +//sets ammt to the amount of space that was allocated +void* allocHeap(size_t size, size_t *ammt) +{ + size_t nUnits = ((size + sizeof(Header)) + PageSize - 1)/PageSize; + Header *prev = allocp; + Header *cur, *temp; + for(cur = prev->next;; prev = cur, cur = cur->next) { + if(cur->size >= nUnits) { + if(cur->size == nUnits) { + prev->next = cur->next; + } else { + temp = cur + nUnits*PageSize/sizeof(Header); + temp->size = cur->size - nUnits; + temp->next = cur->next; + prev->next = temp; + cur->size = nUnits; + *ammt = cur->size*PageSize - sizeof(Header); + } + allocp = prev; + return (void*)(cur + 1); + } else if(cur == allocp) { //We went back to the start... + return NULL; + } + } +} + +void freeHeap(void *ptr) +{ + Header *toFree = (Header *)ptr - 1; + Header *scan; + for(scan = allocp; !(toFree > scan && toFree < scan->next); scan = scan->next) + if(scan->next <= scan && (toFree > scan || toFree < scan->next)) break; + toFree->next = scan->next; + scan->next = toFree; + if(scan + scan->size == toFree) { + scan->size += toFree->size; + scan->next = toFree->next; + toFree = scan; + } + if(toFree + toFree->size == toFree->next) { + toFree->size += toFree->next->size; + toFree->next = toFree->next->next; + } +} diff -r 4473e746fe5a -r 967a56b96d13 src/os/shell.c --- a/src/os/shell.c Sat Jun 11 16:40:48 2011 -0400 +++ b/src/os/shell.c Sun Jun 12 10:09:39 2011 -0400 @@ -2,8 +2,8 @@ #include #include #include +#include #include -//#include #include #include #include @@ -14,13 +14,13 @@ void start(u64 __memsize) { - init_all(__memsize); - if(isError(init_fs(0x100, __memsize))) die(); char buffer[1024]; ErrCode err; - //set up the svc call handler + init_all(__memsize); + if(isError(init_fs(0x100, __memsize))) die(); set_svc_handler(svc_handler, (void*)KERNEL_STACK_START); + sPrint("SOS online!\n"); while(1) { sPrint("$ "); sGet(buffer, 78); @@ -30,7 +30,10 @@ continue; } else { u32 fileSize; - if(isError(getFileSize(fid, &fileSize))); + if(isError(getFileSize(fid, &fileSize))) { //get the length of the file + sPrint("ERROR: could not read file size\n"); + continue; + } void *data = malloc(fileSize); if(!data) continue; if(isError(getFileData(fid, data))) goto loopCont; @@ -40,9 +43,9 @@ goto loopCont; if(eHdr->e_ident[EI_CLASS] != ELFCLASS64) goto loopCont; int i; - for(i = 0; i < eHdr->e_phnum; i++) { + for(i = 0; i < eHdr->e_phnum; i++) { //go through all the headers Elf64_Phdr *pHdr = ((Elf64_Phdr*)(data + eHdr->e_phoff) + i); - if(pHdr->p_type == PT_LOAD) { + if(pHdr->p_type == PT_LOAD) { //these segments get loaded into the memory void *fromLoc = data + pHdr->p_offset; void *toLoc = (void*)pHdr->p_vaddr; memcpy(toLoc, fromLoc, pHdr->p_filesz); diff -r 4473e746fe5a -r 967a56b96d13 src/os/std.c --- a/src/os/std.c Sat Jun 11 16:40:48 2011 -0400 +++ b/src/os/std.c Sun Jun 12 10:09:39 2011 -0400 @@ -1,6 +1,10 @@ #include #include -#ifndef OSLEVEL +#include + +#ifdef OSLEVEL +#include +#else #include #endif @@ -9,7 +13,7 @@ #ifdef OSLEVEL init_io_int(); init_console(); - malloc_init(__memsize - HEAP_START); + heap_init(__memsize); #endif } @@ -147,34 +151,23 @@ //DYNAMIC MEMORY -#ifdef OSLEVEL //TODO NOT JUST OS static Header base; static Header *allocp = NULL; //the location of the last known free block -void malloc_init(size_t memSize) //TODO get rid of this -{ - allocp = &base; - allocp->size = 0; - allocp->next = (void*)HEAP_START; - allocp->next->next = &base; - allocp->next->size = (memSize - HEAP_START)/sizeof(blockUnit); - if((sizeof(blockUnit)%sizeof(u64))) { - sPrint("WARNING: MEMORY NOT 8-BYTE ALIGNED\n"); - } -} - void* malloc(size_t size) { - if(allocp == NULL) return NULL; + Header *prev, *cur, *temp; size_t nUnits = ((size + sizeof(Header)) + sizeof(blockUnit) - 1)/sizeof(blockUnit); - Header *prev = allocp; - Header *cur, *temp; + if(!(prev = allocp)) { //setup malloc if it is the first call to it + base.size = 0; + prev = allocp = base.next = &base; + } for(cur = prev->next;; prev = cur, cur = cur->next) { if(cur->size >= nUnits) { if(cur->size == nUnits) { prev->next = cur->next; } else { - temp = cur + nUnits; //This requires sizeof(blockUnit) == sizeof(Header). TODO fix + temp = cur + nUnits*sizeof(blockUnit)/sizeof(Header); temp->size = cur->size - nUnits; temp->next = cur->next; prev->next = temp; @@ -183,18 +176,38 @@ allocp = prev; return (void*)(cur + 1); } else if(cur == allocp) { //We went back to the start... - //TODO ask the OS for more momory - return NULL; + cur = moreMem(nUnits); + if(!cur) return NULL; } } } +void* moreMem(size_t blocks) +{ + size_t size = blocks*sizeof(blockUnit); + size_t allocSize; + void *block = NULL; +#ifdef OSLEVEL + block = allocHeap(size, &allocSize); +#else + size = 0; + block = NULL; + sPrint("Program level malloc has not been implemented yet, sorry\n"); +#endif + if(!block) return NULL; + Header *blockH = block; + blockH->size = allocSize/sizeof(blockUnit); + free(blockH + 1); + return allocp; +} + void free(void *ptr) { Header *toFree = (Header *)ptr - 1; Header *scan; - for(scan = allocp; !(toFree > scan && toFree < scan->next); scan = scan->next) - if(scan->next < scan && (toFree > scan || toFree < scan->next)) break; + for(scan = allocp; !(toFree > scan && toFree < scan->next); scan = scan->next) { + if(scan->next <= scan && (toFree > scan || toFree < scan->next)) break; + } toFree->next = scan->next; scan->next = toFree; if(scan + scan->size == toFree) { @@ -207,5 +220,3 @@ toFree->next = toFree->next->next; } } - -#endif //OSLEVEL