commands.c

/**
 * Copyright GOIDESCU Rares-Stefan 312CAb 2023-2024
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#include "headers/macros.h"
#include "headers/structs.h"
#include "headers/doubly_ll_ops.h"
#include "headers/basic_ops.h"
#include "headers/simply_ll_ops.h"

void init_heap(seg_free_list_t *heap,
			   U_INT start_addr,
			   U_INT n_lists,
			   U_INT bytes_per_list)
{
	U_INT last_addr = start_addr; // Tine minte prima adresa nemapata

	heap->blocks = malloc(n_lists * sizeof(doubly_ll_t *));
	DIE(!(heap->blocks), "Malloc failed\n");

	heap->curr_size = n_lists;
	heap->max_size = n_lists;

	U_INT pow_of_2 = 1 << 3;
	for (U_INT i = 0; i < n_lists; ++i) {
		heap->blocks[i] = create_dll(pow_of_2);
		heap->blocks[i]->data_size = pow_of_2;
		// nr de blocuri din lista curenta
		U_INT n_blocks = bytes_per_list / pow_of_2;
		heap->n_blocks += n_blocks;
		heap->blocks[i]->size = n_blocks;
		U_INT copy_n_blocks = n_blocks;

		while (copy_n_blocks) {
			// Creez lista corespunzatoare dimensiunii curente (putere de 2)
			create_last(&heap->blocks[i]->head, pow_of_2, last_addr);

			heap->mem_left += heap->blocks[i]->data_size;

			last_addr += pow_of_2;
			copy_n_blocks--;
		}

		pow_of_2 = pow_of_2 << 1;
	}
}

void dump_memory(heap_info_t heap_info, seg_free_list_t heap, allocd_t allocd)
{
	printf("+++++DUMP+++++\n");

	printf("Total memory: %u bytes\n", heap_info.total_mem);
	printf("Total allocated memory: %u bytes\n", allocd.allocd_mem);
	printf("Total free memory: %u bytes\n", heap.mem_left);

	printf("Free blocks: %u\n", heap.n_blocks);

	printf("Number of allocated blocks: %u\n", allocd.blocks->size);
	printf("Number of malloc calls: %u\n", heap_info.n_malloc_calls);
	printf("Number of fragmentations: %u\n", heap_info.n_fragmentations);
	printf("Number of free calls: %u\n", heap_info.n_free_calls);

	for (U_INT i = 0; i < heap.curr_size; ++i) {
		if (heap.blocks[i]->head) {
			printf("Blocks with %u bytes - %u free block(s) :",
				   heap.blocks[i]->data_size,
				   get_size_dll(heap.blocks[i]->head));

			dll_node_t *curr = heap.blocks[i]->head;
			while (curr) {
				printf(" 0x%x", ((block_info_t *)curr->data)->addr);
				curr = curr->next;
			}

			printf("\n");
		}
	}

	dll_node_t *curr = allocd.blocks->head;

	U_INT allocd_size = get_size_dll(allocd.blocks->head);
	printf("Allocated blocks :");
	for (U_INT i = 0; i < allocd_size; ++i) {
		block_info_t *_info = get_block_info(curr->data);
		printf(" (0x%x - %u)", _info->addr, _info->size);
		curr = curr->next;
	}
	printf("\n");
	printf("-----DUMP-----\n");
}

/*
 * Functie care se ocupa de alocarea unui block din vectorul de liste libere
 */
void malloc_cmd(seg_free_list_t *heap,
				U_INT fragment_size,
				allocd_t *allocd,
				heap_info_t *heap_info)
{
	dll_node_t *block_to_fragment;
	U_CHAR found = FALSE;
	U_INT idx = 0;

	// Cautam un block care sa fie destul de mare
	for (U_INT i = 0; i < heap->curr_size; ++i) {
		if (heap->blocks[i]->data_size >= fragment_size &&
			get_size_dll(heap->blocks[i]->head)) {
			// Remove the head (just like shrimps lol)
			block_to_fragment = heap->blocks[i]->head;
			heap->blocks[i]->head = heap->blocks[i]->head->next;
			if (heap->blocks[i]->head)
				heap->blocks[i]->head->prev = NULL;
			block_to_fragment->next = NULL;

			idx = i;
			found = TRUE;
			break;
		}
	}

	if (found)
		heap->blocks[idx]->size--;
	// Daca am gasit, vedem daca trebuie sa il fragmentam sau nu
	if (found) {
		block_info_t *block_tof_info = get_block_info(block_to_fragment->data);
		if (block_tof_info->size == fragment_size) {
			// Daca nu trebuie fragmentat, il marcam ca alocat pur si simplu
			move_block_from_sfl_to_allocd(&allocd, &block_to_fragment);
		} else if (block_tof_info->size > fragment_size) {
			// In caz contrar, il fragmentam, adaugam fragmentul marcat ca
			// alocat in lista de block-uri alocate, si fragmentul ramas liber
			// il vom insera in bucket-ul corespunzator daca exista,
			// sau vom crea alt bucket, in caz contrar.
			dll_node_t *left_shard;
			left_shard = fragment_block(&block_to_fragment, fragment_size,
										&heap_info->last_fragmentation_id);

			// insereaza right shard (block_to_fragment) acolo unde trebuie
			insert_block_in_arr(heap, block_to_fragment);

			move_block_from_sfl_to_allocd(&allocd, &left_shard);

			heap_info->n_fragmentations++;
			heap->n_blocks++;
		}

		heap_info->n_malloc_calls++;
		allocd->allocd_mem += fragment_size;
		allocd->blocks->size++;
		heap->mem_left -= fragment_size;
		heap->n_blocks--;
	} else {
		// In caz ca nu gasim un block suficient de mare
		printf("Out of memory\n");
		return;
	}
}

/*
 * Functie care marcheaza ca liber un block deja alocat si il baga inapoi
 * in vectorul de liste libere.
 */
void free_cmd_0(seg_free_list_t *heap,
				allocd_t *allocd,
				heap_info_t *h_info,
				U_INT addr)
{
	if (!addr)
		return;

	// Cautam nodul cu adresa data si ii pastram pozitia din lista
	U_INT idx = 0;
	dll_node_t *curr = allocd->blocks->head;
	block_info_t *curr_info;

	for (; curr; curr = curr->next, idx++) {
		curr_info = get_block_info(curr->data);
		if (curr_info->addr == addr)
			break;
	}

	if (!curr) {
		printf("Invalid free\n");
		return;
	}

	// Il scoatem din lista si il adaugam in heap
	curr = delete_block(&allocd->blocks->head, curr);

	allocd->allocd_mem -= curr_info->size;
	allocd->blocks->size--;
	heap->n_blocks++;
	heap->mem_left += curr_info->size;

	insert_block_in_arr(heap, curr);

	h_info->n_free_calls++;
}

/*
 * Functia de free (bonus) care cauta continuu daca poate sa faca
 * reconstructii, caz in care le face pana cand nu mai exista.
 * Daca nu se poate, pur si simplu marcheaza block-ul ca liber.
 */
void free_cmd_1(seg_free_list_t *heap, allocd_t *allocd,
				heap_info_t *h_info, U_INT addr)
{
	if (!addr)
		return;
	// Cautam nodul cu adresa data si ii pastram pozitia din lista
	U_INT idx = 0;
	dll_node_t *a_curr = allocd->blocks->head;
	for (; a_curr; a_curr = a_curr->next, idx++)
		if (get_block_info(a_curr->data)->addr == addr)
			break;
	if (!a_curr) {
		printf("Invalid free\n");
		return;
	}
	// Il scoatem din lista si il adaugam in heap
	a_curr = delete_block(&allocd->blocks->head, a_curr);
	U_INT freed_mem = get_block_info(a_curr->data)->size;

	// Cautam un block care sa fi rezultat din aceeasi fragmentare ca cel
	// pe care dorim sa il eliberam
	U_INT id_to_search = -2;
	if (get_block_info(a_curr->data)->frag_ids->head)
		id_to_search =
			*(unsigned int *)get_block_info(a_curr->data)->frag_ids->head->data;
	dll_node_t *heap_curr = NULL;
	U_CHAR found = FALSE;
	for (U_INT i = 0; i < heap->curr_size; ++i) {
		heap_curr = heap->blocks[i]->head;
		while (heap_curr) {
			block_info_t *info = get_block_info(heap_curr->data);
			U_INT curr_id = -1;
			if (info->frag_ids->head)
				curr_id = *(unsigned int *)info->frag_ids->head->data;
			if (curr_id == id_to_search) {
				found = TRUE;
				break;
			}
			heap_curr = heap_curr->next;
		}
	}
	// Reconstruim cat timp exista block-uri care au rezultat din aceeasi frgmt
	while (found) {
		found = FALSE, id_to_search = -2;
		block_info_t *a_info = get_block_info(a_curr->data);
		if (get_block_info(a_curr->data)->frag_ids->head)
			id_to_search = *(unsigned int *)a_info->frag_ids->head->data;
		for (U_INT i = 0; i < heap->curr_size; ++i) {
			heap_curr = heap->blocks[i]->head;
			while (heap_curr) {
				block_info_t *info = get_block_info(heap_curr->data);
				U_INT curr_id = -1;
				if (get_block_info(heap_curr->data)->frag_ids->head)
					curr_id = *(unsigned int *)info->frag_ids->head->data;
				if (curr_id == id_to_search) {
					found = TRUE;
					heap_curr = delete_block(&heap->blocks[i]->head, heap_curr);
					goto found_ticket;
				}
				heap_curr = heap_curr->next;
			}
		}

found_ticket:
		if (found) {
			a_curr = reconstruct_block(a_curr, heap_curr);
			heap->n_blocks--;
			s_ll_node_t *to_free =
				pop_sll(&get_block_info(a_curr->data)->frag_ids->head);
			free(to_free->data);
			free(to_free);
		}
	}
	insert_block_in_arr(heap, a_curr);
	allocd->allocd_mem -= freed_mem;
	heap->mem_left += freed_mem;
	heap->n_blocks++;
	allocd->blocks->size--;
	h_info->n_free_calls++;
}

/*
 * Functie care citeste octetii de pe blocurile alocate si verifica in acelasi
 * timp daca blocurile accesate sunt alocate.
 *
 * @return
 * -1 daca a fost accesata o zona invalida de memorie
 * 0 daca operatia a avut succes
 */
int read_cmd(allocd_t *allocd, U_INT addr, U_INT n_bytes)
{
	U_CHAR addr_exists = FALSE;

	block_info_t *curr_info;

	dll_node_t *curr = allocd->blocks->head;
	while (curr) {
		curr_info = get_block_info(curr->data);
		if (addr >= curr_info->addr &&
			addr < curr_info->addr + curr_info->size) {
			addr_exists = TRUE;
			break;
		}
		curr = curr->next;
	}

	if (!addr_exists) {
		printf("Segmentation fault (core dumped)\n");
		return -1;
	}

	// Calculam cati bytes se pot citi

	int max_bytes = 0;
	max_bytes -= addr - curr_info->addr;
	dll_node_t *temp = curr;
	while (temp) {
		block_info_t *temp_info = get_block_info(temp->data);
		max_bytes += temp_info->size;
		if (temp->next &&
			get_block_info(temp->next->data)->addr !=
			temp_info->addr + temp_info->size)
			break;
		temp = temp->next;
	}

#ifdef DEBUG
	printf("you can read %u bytes from here\n", max_bytes);
#endif

	if ((int)n_bytes > max_bytes) {
		printf("Segmentation fault (core dumped)\n");
		return -1;
	}

	U_INT idx = addr - curr_info->addr;
	curr_info = get_block_info(curr->data);
	while (n_bytes) {
		if (idx == curr_info->size) {
			idx = 0;
			curr = curr->next;
		}

		curr_info = get_block_info(curr->data);
		printf("%c", *((char *)curr_info->data + idx));

		idx++;
		n_bytes--;
	}
	printf("\n");

	return 0;
}

/*
 * @return (int) min between the two
 */
static int my_min(int a, int b)
{
	return (a < b) ? a : b;
}

/*
 * Functie care scrie octetii de pe blocurile alocate si verifica in acelasi
 * timp daca blocurile accesate sunt alocate.
 *
 * @return
 * 0 daca operatia a avut succes
 * -1 daca a fost accesata o zona invalida de memorie
 */
int write_cmd(allocd_t *allocd, U_INT addr, void *data, U_INT n_bytes)
{
	U_CHAR addr_exists = FALSE;

	dll_node_t *curr = allocd->blocks->head;
	block_info_t *curr_info;
	while (curr) {
		curr_info = get_block_info(curr->data);
		if (addr >= curr_info->addr &&
			addr < curr_info->addr + curr_info->size) {
			addr_exists = TRUE;
			break;
		}
		curr = curr->next;
	}

	if (!addr_exists) {
		printf("Segmentation fault (core dumped)\n");
		return -1;
	}

	// Calculam cati bytes se pot scrie
	int max_bytes = 0;
	max_bytes -= addr - curr_info->addr;
	dll_node_t *temp = curr;
	while (temp) {
		block_info_t *temp_info = get_block_info(temp->data);
		max_bytes += temp_info->size;
		if (temp->next &&
			get_block_info(temp->next->data)->addr !=
			temp_info->addr + temp_info->size) {
			break;
		}
		temp = temp->next;
	}

	n_bytes = my_min(n_bytes, strlen((char *)data));

	if ((int)n_bytes > max_bytes) {
		printf("Segmentation fault (core dumped)\n");
		return -1;
	}

	U_INT idx = addr - curr_info->addr;
	U_INT iter = 0;
	curr_info = get_block_info(curr->data);
	while (n_bytes) {
		if (idx == curr_info->size) {
			idx = 0;
			curr = curr->next;
		}

		curr_info = get_block_info(curr->data);
		*((char *)curr_info->data + idx) = *((char *)data + iter);

		idx++;
		iter++;
		n_bytes--;
	}
	return 0;
}

/*
 * Funny name
 * Funny function
 */
void destroy_heap(seg_free_list_t *heap, allocd_t *allocd)
{
	dll_free(&allocd->blocks);

	for (U_INT i = 0; i < heap->curr_size; ++i)
		dll_free(&heap->blocks[i]);

	free(heap->blocks);
}