/*
    exDOS - Experimental 32 Bit protected mode scripted operating system
    (C) 2005 Jason Hunt
    
    This program is free software; you can redistribute it and/or
    modify it under the terms of the GNU General Public License
    as published by the Free Software Foundation; either version 2
    of the License, or (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

    Contact: nulluser@gmail.com
    
    File: mem.c
*/

#include "types.h"
#include "panic.h"
#include "stdio.h"
#include "mem.h"
#include "video.h"
#include "system.h"


// Reserved memory for vga and bios 

#define RESERVED_START  0xa0000
#define RESERVED_SIZE   0x60000
#define MEM_LIMIT       0x02000000    // 64 megs

#define BLOCK_USED      0x80000000 // block used flag
#define CHECKSUM_MASK   0x7fffffff // Used to extract used flag

#define NAME_SIZE       16

typedef struct _b
{
    dword  size;       // (4 bytes) Size of the block 
    struct _b *prev;  // (4 bytes) Pointer to previous block
    struct _b *next;  // (4 bytes) Pointer to next block
    dword checksum;   // (4 bytes) Used to make sure the block is not corrupt
    byte name[NAME_SIZE];          // used for named aloocation
                       // 16 the block used flag is storeed in the MSB
} block_type;          //(size 16+NAME_SIZE bytes)



extern dword kernel_end[];    // This gets the symbol from the compler that
                        // Represets the end of the kernel
                        // Any memory after this is fair game

dword free_start = (dword)kernel_end; // Starting address of free memory


block_type *start_block = NULL;  // no memory allocated yet


/* Display the current memory blocks */
void show_blocks( void )
{
    block_type *cur_block = start_block ;// Point to the first block

    puts("Memory blocks:\n");
    if (cur_block == NULL)
    {
        puts("No current blocks\n");
        return;
    }

    // Dump memory blocks
    while (cur_block)
    {
        puts(cur_block -> name);

        int l = NAME_SIZE - strlen(cur_block -> name);
        if (l) while(l--) putchar(' ');


        puts(" Start "); vga_put_hex_32((dword)cur_block);       puts(" ");
        puts("Size: ");   vga_put_hex_32(cur_block->size);        puts(" ");
        puts("Nx: ");   vga_put_hex_32((dword)cur_block->next); puts(" ");
        puts("Pr: ");   vga_put_hex_32((dword)cur_block->prev); puts(" ");

        if (cur_block->checksum & BLOCK_USED)
           puts("Used\n");
        else
            puts("Free\n");

        cur_block = (block_type *)cur_block->next;
    }

}
/* End of  show_blocks */


/* Attempt to break the memory manager */
void mem_test( void )
{
    puts("Kernel memory test\n");
    puts("This should show the most compacted state after deallocation\n");
    printd("Free memory start: ", (dword)free_start);

    const word test_size = 1000;

    word i;
    void *locations[test_size];

    // allocate random sizes
    for (i = 0; i < test_size; i++)
        locations[i] = kmallocn(rand() % 10000 + 10000, "mem test"); 

    word j = 10000;

    // This should fragment the shit out of it
    while (j--)
    {
        word l = rand() % test_size; // choose a random location

        kfree(locations[l]);

        locations[l] = kmallocn(rand() % 1000 + 100, "space");  // reallocate it

        if (!locations[l]) 
            puts("Unable to allocate\n");
    }

    // free all of them ( reverse)
    for (i = test_size  ;i; i--)
        kfree(locations[i-1]);

    //  free all of them (forward)
//    for (i = 0;i < test_size; i++)
//        kfree(locations[i]);

    show_blocks();
}
/* End of mem test */


/* Called once to route around system memory */
void setup_inital_blocks( void )
{
    // we nee to allocate around the reserved data areas

    block_type *cur_block = (block_type *) free_start;  // Point to start of free memory
    start_block = cur_block;                           // Update base pointer

    cur_block->prev = NULL;

    // point right before reserved
    cur_block->next = (block_type *)(RESERVED_START - sizeof(block_type));

    // The headers for both the first free, and the reserved area
    // are in the first free area, that where the 32 comes from
    
    cur_block->size = RESERVED_START - (dword)free_start - 2*sizeof(block_type) ; 

    cur_block->next->prev = cur_block; // save the pointer to this block
    strncpy(cur_block->name, "free", NAME_SIZE);

    // calculate the checksum, used flag clear
    cur_block->checksum = (cur_block->size * (dword)(cur_block)) & CHECKSUM_MASK;


    // Now we will setup the reserved area
    // cur_block = cur_block->next;
    cur_block = cur_block->next;

    cur_block->next = NULL;
    cur_block->size = RESERVED_SIZE; // point right before reserved

    strncpy(cur_block->name, "reserved", NAME_SIZE);

    // calculate the checksum, leave room for used flag
    cur_block->checksum = (cur_block->size* (dword)(cur_block)) & CHECKSUM_MASK;
    cur_block->checksum |= BLOCK_USED; // set used flag
}
/* End of etup_inital_blocks */


void * kmalloc( dword size )
{
    return(kmallocn(size, "unnamed"));
}

/* Allocate a block of memory */
void * kmallocn( dword size, char *name )
{
    if (!size) return(NULL);

    cli();

    block_type *cur_block = start_block ;// Point to the first block

   //  printd("adding: ", size);
    // search the blocks, This is passed if it's the first allocation
  
    while(cur_block)
    {
        // The block is free
        if ((cur_block->checksum & BLOCK_USED) == 0)
        {
          //  puts("found unused block\n");

            // See if block is exactly the same size
            if (cur_block->size == size)
            {
                strncpy(cur_block->name, name, NAME_SIZE);

                cur_block->checksum |= BLOCK_USED;       // Set used flag
                sti();                                   // The checksum is still valid
                return((void *)((dword)cur_block +  sizeof(block_type))); // Return the actual storage area
            }

            // See if there is room for the this block
            // The next bloxk, and a  sizeof(block_type) byte padding
            // There is no sense is squeezing a block in there 
            // if it can't hold any data
            if (cur_block->size > size +  sizeof(block_type) + 64)
            {
              //  puts("Size fit\n");

                block_type *save_block = cur_block;      // save the current block 

                block_type *save_next= cur_block->next;      // save the current block 

                dword save_size = cur_block->size;

                // Set the next pointer of this block 
                // to the address of the after the split
                cur_block->next = (block_type *)( (dword)cur_block + size + sizeof(block_type)  );
                
                // prev is still valid
                cur_block->size = size;
                 strncpy(cur_block->name, name, NAME_SIZE);

                // calculate the checksum, leave room for used flag
                cur_block->checksum = (size * (dword)(cur_block)) & CHECKSUM_MASK;
                cur_block->checksum |= BLOCK_USED; // set used flag    

                cur_block = (block_type *)cur_block->next; // now working with the new block

                cur_block->prev = save_block ;
                cur_block->next = save_next;
                cur_block->size = save_size - size - sizeof(block_type) ; // size of new block

  
                // Set the next block prev to the 2nd half of the split
                cur_block->next->prev = cur_block; 

                strncpy(cur_block->name, "free", NAME_SIZE);

                // calculate the checksum, leave room for used flag
                cur_block->checksum = (cur_block->size * (dword)(cur_block)) & CHECKSUM_MASK;

                // the used flag will not be set  
                sti(); 
                return((void *)((dword)save_block + sizeof(block_type) )); // Return the actual storage area

            }

        }

        // Check for end of block list
        if (cur_block->next == NULL && (dword)cur_block + size < MEM_LIMIT)  
            {           
                block_type *save_prev = cur_block;

                // Set the next point of this block to the address of our new block
                cur_block->next = (block_type *)((dword)cur_block + cur_block->size + sizeof(block_type) );

                cur_block = cur_block->next; // now working with the new block
  
                cur_block->prev = save_prev;
                cur_block->next = NULL;
                cur_block->size = size;
  
                // calculate the checksum, leave room for used flag
                cur_block->checksum = (size * (dword)(cur_block)) & CHECKSUM_MASK;

                cur_block->checksum |= BLOCK_USED; // set used flag    
                strncpy(cur_block->name, name, NAME_SIZE);

                sti(); 
                return((void *)((dword)cur_block + sizeof(block_type) )); // Return the actual storage area
            }
 
        cur_block = cur_block->next;
    }

    if (start_block == NULL) // This is the first allocation
    {
        setup_inital_blocks();          // Setup system reserved block
        return(kmallocn(size, name));          // Call again to allocate
    }

    //panic("kmalloc Unable to allocate memory\n");
    sti();
    return(NULL);
}
/* End of kmalloc */




/* Free a block of memory */
void kfree( void * addr )
{
    cli();

    block_type *cur_block = (block_type *)((dword)addr - sizeof(block_type) ); // Point to start of block

//    printd("Freeing location: ", (dword)addr);

    // Check block checksum
    if ((cur_block->checksum  & CHECKSUM_MASK )!= 
                (((dword)cur_block * cur_block->size) & CHECKSUM_MASK ))
        panic("kfree: Block checksum error, heap corrupt");

 //   block_type *cur_block = block; // Save origional block

    cur_block->checksum &= CHECKSUM_MASK ;       // Clear used flag

    // Preform reverse compaction
    if (cur_block->prev  && !(cur_block->prev->checksum & BLOCK_USED))
    {        // Seek to previous block to perform forward compaction

         cur_block->prev->next = cur_block->next;    // chain over the previous block
         cur_block->next->prev = cur_block->prev;

        // The previous block will become the new larger block
        cur_block->prev->size = cur_block->size + cur_block->prev->size + sizeof(block_type) ;

        // Calculate the checksum, leave room for used flag
        cur_block->prev->checksum = (cur_block->prev->size  * (dword)(cur_block->prev)) & CHECKSUM_MASK;

        // Seek to previous block
        cur_block = cur_block->prev;
    }

    // Preform forward compaction

    // See if next block exists and is free
    if (cur_block->next && !(cur_block->next->checksum & BLOCK_USED))
    {
        // The current block block will become the new larger block
        cur_block->size = cur_block->size + cur_block->next->size + sizeof(block_type) ;

        // Calculate the checksum, keep used flag clear
        cur_block->checksum = (cur_block->size  * (dword)(cur_block)) & CHECKSUM_MASK;
 
        cur_block->next = cur_block->next->next;

        if (cur_block->next) // make sure this is not the last block
            cur_block->next->prev = cur_block;    // chain over the next block
    }

    sti();
}
/* End of kfree */



















