[OSy] test1
Eva Semanová
evi.semanova at gmail.com
Wed Oct 24 17:35:23 CEST 2018
toto je riesenie, ktore povazujem za hotove, este ho musim nahadzat naspat
do VIM editoru
st 24. 10. 2018 o 17:19 Eva Semanová <evi.semanova at gmail.com> napísal(a):
> ešte mi treba dokončiť free funkciu
>
> Eva Semanová
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://d3s.mff.cuni.cz/pipermail/nswi004/attachments/20181024/324d7e05/attachment.html>
-------------- next part --------------
/*this was alocated as global*/
static heap_block_head_t * position = NULL;
void *malloc (const size_t size)
{
/*
* Checking for maximum size avoids errors due to
* overflow, which would be hard to debug.
*/
assert (size <= HEAP_BLOCK_SIZE_MAX);
/* Disable interrupts while accessing shared structures. */
ipl_t state = query_and_disable_interrupts ();
/*
* We have to allocate a bit more to have room for
* header and footer. The size of the memory block
* also has to be 4 bytes aligned to avoid unaligned
* memory access exception while accessing the
* footer structure.
*/
size_t real_size = ALIGN_UP (size, ALIGNMENT) +
sizeof (heap_block_head_t) + sizeof (heap_block_foot_t);
void *result = NULL;
/* Iterate over all heaps */
list_foreach (heap_list, heap_t, link, heap) {
if ((position != NULL) && (heap != position->heap)) {
continue;
}
heap_block_head_t *pos;
if(heap == position->heap) {
pos = position;
} else {
pos = (heap_block_head_t *) heap->heap_start;
}
while ((result == NULL) && ((void *) pos < heap->heap_end)) {
/* Make sure the heap is not corrupted. */
block_check (pos);
/* Try to find a block that is free and large enough. */
if ((pos->free) && (pos->size >= real_size)) {
/*
* We have found a suitable block.
* See if we should split it.
*/
size_t split_limit = real_size +
sizeof (heap_block_head_t) + sizeof (heap_block_foot_t);
if (pos->size > split_limit) {
/* Block big enough -> split. */
void *next = ((void *) pos) + real_size;
block_init (next, pos->size - real_size, true, heap);
block_init (pos, real_size, false, heap);
} else {
/* Block too small -> use as is. */
pos->free = false;
}
/* Either way we have our result. */
result = ((void *) pos) + sizeof (heap_block_head_t);
}
/* Advance to the next block. */
pos = (heap_block_head_t *) (((void *) pos) + pos->size);
if(result != NULL) {
if((void *) pos < heap->heap_end)) {
position = pos; //this is the new place where to start searching
}
else {
position = (heap_block_head_t*) (heap->link.next);
}
}
}
if (result != NULL)
break;
}
/*second foreach*/
list_foreach(heap_list, heap_t, link, heap) {
if ((result != NULL) || (position == NULL)) {
break;
}
/*if (heap == position->heap) */
heap_block_head_t *pos= (heap_block_head_t *) heap->heap_start;
while ((result == NULL) && ((void *) pos < heap->heap_end) && (pos != position) {
/* Make sure the heap is not corrupted. */
block_check (pos);
/* Try to find a block that is free and large enough. */
if ((pos->free) && (pos->size >= real_size)) {
/*
* We have found a suitable block.
* See if we should split it.
*/
size_t split_limit = real_size +
sizeof (heap_block_head_t) + sizeof (heap_block_foot_t);
if (pos->size > split_limit) {
/* Block big enough -> split. */
void *next = ((void *) pos) + real_size;
block_init (next, pos->size - real_size, true, heap);
block_init (pos, real_size, false, heap);
} else {
/* Block too small -> use as is. */
pos->free = false;
}
/* Either way we have our result. */
result = ((void *) pos) + sizeof (heap_block_head_t);
}
/* Advance to the next block. */
pos = (heap_block_head_t *) (((void *) pos) + pos->size);
if(result != NULL) {
if((void *) pos < heap->heap_end)) {
position = pos; //this is the new place where to start searching
}
else {
position = (heap_block_head_t*) (heap->link.next);
}
}
}
if (result != NULL)
break;
}
/*
* There is not enough empty space in the existing
* heaps. Try to acquire a new heap and allocate the
* block from it.
*/
if (result == NULL)
result = malloc_heap (size);
conditionally_enable_interrupts (state);
return result;
}
static void *malloc_heap (const size_t size)
{
/*
* Calculate the proper size of the new heap
* (with appropriate headers and alignment).
*/
size_t real_size = ALIGN_UP (size, ALIGNMENT) +
sizeof (heap_block_head_t) + sizeof (heap_block_foot_t);
size_t split_limit = real_size +
sizeof (heap_block_head_t) + sizeof (heap_block_foot_t);
size_t heap_size =
ALIGN_UP (real_size + sizeof (heap_t), FRAME_SIZE);
/*
* Calcutate the number of frames required from
* the frame allocator. The new heap should be at
* least HEAP_FRAMES large.
*/
size_t frames = heap_size >> FRAME_WIDTH;
if (frames < HEAP_FRAMES) {
frames = HEAP_FRAMES;
heap_size = frames << FRAME_WIDTH;
}
/*
* Ask the frame allocator for a continuous physical
* memory area for the new heap.
*/
uintptr_t phys;
int rc = frame_alloc (&phys, frames, VF_VA_AUTO | VF_AT_KSEG0);
if (rc != EOK)
return NULL;
/*
* Initialize the heap structure.
*/
heap_t *heap = (heap_t *) ADDR_IN_KSEG0 (phys);
link_init (&heap->link);
heap->heap_start = ((void *) heap) + sizeof (heap_t);
heap->heap_end = ((void *) heap) + heap_size;
heap->frames = frames;
heap_block_head_t *cur = (heap_block_head_t *) heap->heap_start;
size_t payload_heap_size = heap_size - sizeof (heap_t);
/*
* Allocate the block from the newly created heap.
*/
if (payload_heap_size > split_limit) {
void *next = ((void *) cur) + real_size;
block_init (next, payload_heap_size - real_size, true, heap);
block_init (cur, real_size, false, heap);
position = (heap_block_head_t *)next;
} else {
block_init (cur, payload_heap_size, false, heap);
//heap is full, start searching from beginning
position = NULL;
}
list_append (&heap_list, &heap->link);
return ((void *) heap->heap_start + sizeof (heap_block_head_t));
}
void free (const void *addr)
{
/* Disable interrupts while accessing shared structures. */
ipl_t state = query_and_disable_interrupts ();
/* Calculate the position of the header. */
heap_block_head_t *head =
(heap_block_head_t *) (addr - sizeof (heap_block_head_t));
/* Make sure the block is not corrupted and not free. */
block_check (head);
assert (!head->free);
/* Get the heap the block belongs to. */
heap_t *heap = head->heap;
/* Mark the block itself as free. */
head->free = true;
/* Look at the next block. If it is free, merge the two. */
heap_block_head_t *next_head =
(heap_block_head_t *) (((void *) head) + head->size);
if ((void *) next_head < heap->heap_end) {
block_check (next_head);
if (next_head->free) {
block_init (head, head->size + next_head->size, true, heap);
position = (heap_block_head_t *) head;
}
}
/* Look at the previous block. If it is free, merge the two. */
if ((void *) head > heap->heap_start) {
heap_block_foot_t *prev_foot =
(heap_block_foot_t *) (((void *) head) - sizeof (heap_block_foot_t));
heap_block_head_t *prev_head =
(heap_block_head_t *) (((void *) head) - prev_foot->size);
block_check (prev_head);
if (prev_head->free) {
block_init (prev_head, prev_head->size + head->size, true, heap);
position = (heap_block_head_t *) prev_head;
}
}
/*
* Check whether the entire heap is just one free block.
* If this is the case then release it entirely.
*/
head = (heap_block_head_t *) heap->heap_start;
if ((head->free) && (heap->heap_start + head->size == heap->heap_end)) {
position = NULL;
/*
* We assume it will not happen often, therefore we can aford to start search from the beggining.
* In other case, we have to chose first block from next heap or last block from previous heap.
*/
list_remove (&heap->link);
/*
* Free the physical frames backing the heap.
*/
uintptr_t phys = ADDR_FROM_KSEG0 ((uintptr_t) heap);
int rc = frame_free (phys, heap->frames);
if (rc != EOK)
panic ("Unable to release heap.");
}
conditionally_enable_interrupts (state);
}
More information about the NSWI004
mailing list