[OSy] test1

[Eva Semanová]

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/7fcaebc1/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));
}

/*I have to rewrite free function*/