|
#include "memory_management.h" |
|
|
|
// The start of the linked list of blocks |
|
block *global_head = NULL; |
|
|
|
/** |
|
* @brief We will find a possible place to allocate the needed memory |
|
* If we have a bigger free space than we need, we will then divide the space |
|
* that we have. |
|
* |
|
* @param last a double pointer to the place we want the memory to allocate |
|
* @param size the size that we want to allocate |
|
* |
|
* @return A block pointer to the place that we found to be suitable. |
|
*/ |
|
block *find_free_block(block **last, int size) { |
|
block *current = global_head; |
|
|
|
// Find a block that has a >= size than we need and it's free |
|
while (current && !(current->free && current->size >= size)) { |
|
*last = current; |
|
current = current->next; |
|
} |
|
|
|
// Return the current pointer as it is if the size is the same |
|
// or we didn't get a suitable pointer |
|
if( current == NULL || current->size - size <= sizeof(block) + sizeof(int)) |
|
return current; |
|
|
|
// If we have more available space than needed |
|
// we can use just the needed size to allocate the needed memory |
|
|
|
// Find out the distance to the top of the heap |
|
block *looper = current->next; |
|
int size_of_movment = current->size - size; |
|
while(looper) { |
|
size_of_movment += looper->size + sizeof(block); |
|
looper = looper->next; |
|
} |
|
// Move the sbrk down |
|
sbrk(-size_of_movment); |
|
// Make the new block |
|
block *new_block = (block*) sbrk(0); |
|
//Move the sbrk back to the top |
|
sbrk(size_of_movment); |
|
|
|
new_block->size = current->size - size - sizeof(block); |
|
if (current->next) |
|
current->next->previous = new_block; |
|
new_block->free = true; |
|
new_block->next = current->next; |
|
new_block->previous = current; |
|
|
|
current->size -= new_block->size + sizeof(block); |
|
current->next = new_block; |
|
|
|
return current; |
|
} |
|
|
|
/** |
|
* @brief Will make space for a new memory and add it to the new list. |
|
* |
|
* @param last the block that we want to split |
|
* @param size the size of the new space that we want to allocate |
|
* |
|
* @return A pointer to the new block. |
|
*/ |
|
block *add_new_block(block *last, int size) { |
|
block *new; |
|
|
|
new = (block*) sbrk(0); |
|
|
|
void *request = sbrk(size + sizeof(block)); |
|
if (request == (void*) - 1) |
|
return NULL; // sbrk failed. |
|
|
|
if (last) // NULL on first request. |
|
last->next = new; |
|
|
|
new->size = size; |
|
new->free = false; |
|
new->next = NULL; |
|
new->previous = last; |
|
|
|
return new; |
|
} |
|
|
|
/** |
|
* @brief My malloc function. A block of memory will be freed. |
|
* If the block is at the end of the heap, the sbrk function will be called |
|
* and move the pointer down by the size of the heap + sizeof(block). |
|
* In case a block has another free adjacent block, the two blocks |
|
* will be merged. |
|
* |
|
* @param size the size of the block we want to allocate |
|
* |
|
* @return The pointer to the location that we allocated |
|
*/ |
|
void *_malloc(int size) { |
|
block *current; |
|
|
|
if (size <= 0) |
|
return NULL; |
|
|
|
// The first usage of the global_head |
|
if (!global_head) { |
|
current = add_new_block(NULL, size); |
|
if (!current) |
|
return NULL; |
|
|
|
global_head = current; |
|
return ++current; |
|
} |
|
|
|
block *last = global_head; |
|
current = find_free_block(&last, size); |
|
|
|
// If we do not find a free block, then we allocate one |
|
// to the end of the heap |
|
if (!current) { // Failed to find free block. |
|
current = add_new_block(last, size); |
|
if (!current) |
|
return NULL; |
|
} else { |
|
// If we find a suitable space we put the data in there |
|
current->free = false; |
|
} |
|
|
|
return ++current; |
|
} |
|
|
|
/** |
|
* @brief Will merge all neighboring blocks of a block to make room |
|
* for bigger spaces to be allocated. |
|
* |
|
* @param current The block that we want to merge |
|
* |
|
* @return The location of the new block |
|
*/ |
|
block *merge(block *current) { |
|
if (current->free == false) |
|
return NULL; |
|
|
|
if (current->next && current->next->free) { |
|
current->size += current->next->size + sizeof(block); |
|
current->next->next->previous = current; |
|
current->next = current->next->next; |
|
} |
|
|
|
if (current->previous && current->previous->free) { |
|
current->previous->size += current->size + sizeof(block); |
|
current->next->previous = current->previous; |
|
current->previous->next = current->next; |
|
return current->previous; |
|
} |
|
|
|
return current; |
|
} |
|
|
|
/** |
|
* @brief The free function frees the memory space pointed to by the parameter |
|
* which must have been returned by a previous call to malloc(). |
|
* Otherwise, or if free has already been called on the pointer before, |
|
* undefined behavior occurs. If the pointer is NULL, no operation is performed. |
|
* |
|
* @param ptr The pointer to the space that we want to free |
|
*/ |
|
void _free(void *ptr) { |
|
if (!ptr) |
|
return; |
|
|
|
block* block_ptr = ptr - sizeof(block); |
|
|
|
// Merge the blocks around the current current block |
|
block_ptr->free = true; |
|
block_ptr = merge(block_ptr); |
|
|
|
if (block_ptr == NULL) |
|
return; |
|
|
|
// If the only block that is left is the first block |
|
if (block_ptr->previous == NULL && block_ptr->next == NULL) { |
|
sbrk (- (block_ptr->size + sizeof(block) )); |
|
global_head = NULL; |
|
return; |
|
} |
|
|
|
// Check if the given block is the last block in the list |
|
if (block_ptr->next == NULL) { |
|
block_ptr->previous->next = NULL; |
|
sbrk (- (block_ptr->size + sizeof(block) )); |
|
} |
|
} |
|
|
|
void show_heap() { |
|
block *current = global_head; |
|
|
|
while (current) { |
|
printf("Free:%d Size:%d Current:%p Next:%p Prev:%p\n", current->free, current->size, current, current->next, current->previous); |
|
if(current->next != NULL) |
|
current = current->next; |
|
else |
|
return; |
|
} |
|
} |
|
|
|
int main(int argc, char *argv[]) { |
|
struct test{ |
|
int a; |
|
char b; |
|
unsigned int x; |
|
} *structure = _malloc(5 * sizeof(struct test)); |
|
|
|
int *a = _malloc(10 * sizeof(int)); |
|
int *b = _malloc(10 * sizeof(int)); |
|
int *c = _malloc(10 * sizeof(int)); |
|
int *d = _malloc(10 * sizeof(int)); |
|
printf("%d %d %d %d\n\n", a[0], b[0], c[0], d[0]); |
|
|
|
_free(b); |
|
show_heap(); |
|
|
|
structure[3].a = 5; |
|
structure[3].b = 'c'; |
|
printf("%d %c\n", structure[3].a, structure[3].b); |
|
|
|
int *f = _malloc(30 * sizeof(char)); |
|
int *e = _malloc(100 * sizeof(char)); |
|
printf("%c %c %p\n", e[0], f[0], &a[11]); |
|
|
|
show_heap(); |
|
|
|
exit(0); |
|
} |