#include "clib.h"
#include "i386.h"
#include "paging.h"
#include "kmalloc.h"

/*
 * allocazione dinamica di memoria nello spazio kernel condiviso.
 * l'allocazione e` veramente dinamica, nel senso che le pagine
 * principali sono allocate con valloc, percio` non consuma memoria.
 *
 * non so come ho fatto, ma le proc sono incredibilmente corte e semplici
 * e anche abbastanza efficienti, visto che la fusione dei blocchi la
 * faccio solo quando e` necessario, e non ad ogni kfree.
 *
 * ho fatto alcune prove e sembra funzionare bene [18/09/1997]
 *
 * [24/09/97] aggiunto kcalloc e krealloc, che pero` non e` molto
 *            efficiente ;)
 */

#define FREE_NODE 0x12345678
#define USED_NODE 0x87654321

typedef struct _heap {
	struct _heap*	next;  /* nodo successivo */
        struct _heap*	prev;  /* precedente */
        dword		magic; /* free/used */
        dword		size;  /* dimensione COMPRESA sizeof(heap_node) */
} heap_node;

static heap_node* main_node;
static heap_node* node_limit;


addr_t kmalloc(size_t size)
{
	heap_node* node = main_node;
        bool prev_was_free = false;

        ASSERT(size != 0);

        size = (size + 7 + sizeof(heap_node)) & (~7);

	while (node && node < node_limit) {

		ASSERT(node->magic == FREE_NODE || node->magic == USED_NODE);
        	if (prev_was_free && node->magic == FREE_NODE) {

                	/*
                         * fonde 2 nodi liberi consecutivi
                         */
                	heap_node* prev = node->prev;
                        heap_node* next = node->next;

                        ASSERT(prev != NULL);
                        prev->next = next;
                        if (next) next->prev = prev;
                        prev->size += node->size;
                        node = prev;
                }

                if (node->magic == FREE_NODE) prev_was_free = true;
		if (prev_was_free && node->size >= size) {
                	/*
                         * trovato un nodo abbastanza grande
                         */

                	if (node->size > size+sizeof(heap_node)+16) {
                        	/*
                                 * se il nodo e` troppo grande, dividilo
                                 */
                        	heap_node* next;

                                // marca il blocco successivo come libero
                                next = (heap_node*)((u8*)node + size);
                                next->prev = node;
                                next->next = node->next;
                                next->magic = FREE_NODE;
                                next->size = node->size - size;
                                node->next = next;
                                node->size = size;
                        }
                	node->magic = USED_NODE;

                    //    kprintf("kmalloc ritorna %xh", (addr_t)node + sizeof(heap_node));
                        return (addr_t)node + sizeof(heap_node);
                }
                node = node->next;
        }
        WARNING("NULL from kmalloc\n");
        return 0;
}

void kfree(addr_t addr)
{
	heap_node* node;
        ASSERT(addr != NULL);
        node = (heap_node*)(addr - sizeof(heap_node));
        ASSERT(node->magic == USED_NODE);
	node->magic = FREE_NODE;
}

addr_t kcalloc(size_t size)
{
	addr_t a = kmalloc(size);
        if (a) {
        	memset(a, 0, size);
        }
        return a;
}

addr_t krealloc(addr_t a, size_t size)
{
	heap_node* node;
        size_t nsize;
        size_t asize;

        node = (heap_node*)(a - sizeof(heap_node));
        nsize = node->size;

        if (node->magic != USED_NODE) goto _ret;

        asize = (size + 7 + sizeof(heap_node)) & (~7);

        if (asize > node->size+sizeof(heap_node)+16) {
        	heap_node* next;

        	/* diminuisco la memoria allocata */

                node->size = asize;
                next = (heap_node*)((u8*)node + asize);
                next->size = node->size - asize;
                next->magic = FREE_NODE;
                if (node->next) {
                	node->next->prev = next;
                }
                next->next = node->next;
                next->prev = node;
                node->next = next;
                return a;
        }

        if (node->size >= asize) return a;  // caso stupido
        else {
        	/* aumento la memoria allocata */
                /* caso + frequente, e - efficiente .. */
        	addr_t na;
        	na = kmalloc(size);
                if (na) {
			memcpy(na, a, nsize);
                        memset(na+nsize, 0, size-nsize);
                        kfree(a);
                } else {
                	WARNING("return NULL");
                }
                return a;
        }



_ret:
	WARNING("return NULL");
        return NULL;
}

/*
 * pagine da destinare all'heap. si puo` anche esagerare, tanto la
 * memoria e` veramente allocata solo quando serve.
 * 64K sono + che sufficienti.
 */

void kmalloc_startup(int npages)
{

        main_node = valloc(npages);
        ASSERT(main_node != NULL);
        node_limit = (heap_node*)((u8*)main_node + npages*4096);
        main_node->size = npages*4096;
        main_node->prev = NULL;
        main_node->next = NULL;
        main_node->magic = FREE_NODE;

}