I have just started re-implementing a physical memory manger (been a long time, been busy with college work) and I have quite a simple concept. I got it implemented, and in theory it should work. I've double-triple-quadruple-quituple checked it, and i just can't find the error. anyway...
I currently have 2 ordered arrays. they are used for storing allocated memory(so i don't lose track of it) and freed memory (so i know where the holes are). they are ordered by the address of the memory allocated.
my allocate function has 2 methods of allocating memory. if there are any entries in the freed memory array, it checks the size of the hole and if it fits; it allocates it, removes it from freemem, compares the size wanted with the size of the hole and adds (if necessary) the unneeded memory back to the freed memory array. if it doesn't fit, or there are no entries in the freed memory array, then it just allocates it from the end of known (i.e. pre-allocated) memory and notes it in the used memory array, ready to be added to the freed memory array.
now, my problem is that testing my code on paper it all works. whereas when I test in bochs and parallels it doesn't, although it does allocate off the end of the kernel properly
. upon a little digging i found that the size attribute of the ordered arrays never increase when i insert a value into them. once again, on paper the code works, in testing it doesn't.I may just be rushing in desperation to get it working, having developed the idea behind it for about a week now, but having spent 2 days away from coding; i still don't see the problem.
insert algorithm for ordered arrays:
Code: Select all
void insert(T newEntry){
int i = 0;
while(sort(array[i],newEntry) == true){ //while the array entry at i is less than the entry
i++; // ignore the entry
}
if(i > size){ // if i references a higher entry than has been recorded
array[++size] = newEntry; // add to the end of the array
}
else{ // otherwise...
T sortEntry;
while(i <= (size+1)){ //move everything along one
sortEntry = array[i];
array[i] = newEntry;
newEntry = sortEntry;
i++;
}
size += 1;
}
}
mem allocate algorithm:
Code: Select all
void * Memory::alloc(dWord size){
asm volatile("cli");
void *address; //address to be returned
if (freemem.getSize() == 0){ //if no known free memory
address = (void *)endmem; // allocate from the beginning of unknown memory
endmem += size; // adjust the pointer for the size of the allocation
}
else { // if there is some known free memory
int i=0;
while (freemem.getItem(i)->getSize() < size){ //find out if there is a hole big enough
i++;
if(i > freemem.getSize()){ //if there are no more entries
i = 4097; //confirm no entry
break; //break the loop
}
}
if(i <= freemem.getSize()){ //there there was an entry found
memoryAddress *hole = freemem.getItem(i); //the the info
address = hole->getSource(); //extract the address to be returned
freemem.remove(i); //remove from known free memory
if(hole->getSize() > size){ // if the hole is a bit big give some memory back
memoryAddress *newHole; //the new hole to be added
newHole->setSource ((void *)( //set the address of the hole to
((dWord)hole->getSource()) //the address of the hole we found
+ size)); // plus the size we wanted.
newHole->setSize(hole->getSize() - size); // the size is just the bit we didn't want
freemem.insert(newHole); //insert the new hole into known free memory
}
}
else{ // if there was no entry found
address = (void *)endmem; // allocate unknown memory
endmem += size; //adjust pointer as neccessary
}
}
memoryAddress *usedhole; // add the new allocated memory to used memory
usedhole->setSource(address); // address of the block
usedhole->setSize(size); // size we wanted/are using
usedmem.insert(usedhole); // insert
asm volatile("sti");
return address;
}
Code: Select all
void Memory::free(void *addr){
freemem.dumpSize(); // debug info. always returns 0!!!!!
memoryAddress *usedHole;
int i = 0;
while(i <= usedmem.getSize()){ //find all entries in used memory
if(usedmem.getItem(i)->getSource() != addr) { // if the addresses don't match
i++; // get the next entry
}
else //if it is
break; // i is the index in usedmem, so break the loop
}
usedHole = usedmem.getItem(i); // get the entry at i
freemem.insert(usedHole); // insert it into freemem
usedmem.remove(i); // remove it from usedmem
}
my testing code just allocates memory for 2 variables 4 bytes in length each, frees them, and then re allocates them. at the moment, they are just linearly allocated from the end of the kernel.
all help is very much appreciated.
Cheers,
James.
save me 
