/*****************************************************************************************
 Copyright (c) 2002-2004 The UbixOS Project
 All rights reserved.

 Redistribution and use in source and binary forms, with or without modification, are
 permitted provided that the following conditions are met:

 Redistributions of source code must retain the above copyright notice, this list of
 conditions, the following disclaimer and the list of authors.  Redistributions in binary
 form must reproduce the above copyright notice, this list of conditions, the following
 disclaimer and the list of authors in the documentation and/or other materials provided
 with the distribution. Neither the name of the UbixOS Project nor the names of its
 contributors may be used to endorse or promote products derived from this software
 without specific prior written permission.

 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
 THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
 OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
 TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 $Id$

*****************************************************************************************/

#include <lib/kmalloc.h>
#include <lib/kprintf.h>
#include <ubixos/kpanic.h>
#include <ubixos/sched.h>
#include <ubixos/spinlock.h>
#include <vmm/vmm.h>
#include <string.h>
#include <assert.h>

/*
 Set up three descriptor tables:
 
 kernDesc      - The inuse descriptor table 
 freeKernDesc  - The free descriptor table (descriptors with memory backing just not in use)
 emptyKernDesc - The empty descriptor table (descriptors with out a memory backing)
 
*/
static struct memDescriptor *usedKernDesc  = 0x0;
static struct memDescriptor *freeKernDesc  = 0x0;
static struct memDescriptor *emptyKernDesc = 0x0;

/*
 Set up our spinlocks so we do not corrupt linked lists if we have re-entrancy
*/
static spinLock_t mallocSpinLock    = SPIN_LOCK_INITIALIZER;
static spinLock_t emptyDescSpinLock = SPIN_LOCK_INITIALIZER;

/************************************************************************

Function: void *getEmptyDesc()
Description: Find An Empty Descriptor

Notes:

02/17/03 - Is This Efficient?

************************************************************************/    
static void *getEmptyDesc() {
  int i = 0x0;
  struct memDescriptor *tmpDesc = 0x0;

  spinLock(&emptyDescSpinLock);
  
  tmpDesc = emptyKernDesc;
  
  if (tmpDesc != 0x0) {
    emptyKernDesc       = tmpDesc->next;
    if (emptyKernDesc != 0x0) 
      emptyKernDesc->prev = 0x0;
      
     
    tmpDesc->next       = 0x0;
    tmpDesc->prev       = 0x0;
    spinUnlock(&emptyDescSpinLock);
    return(tmpDesc);
    }
    
  if ((emptyKernDesc = (struct memDescriptor *)vmm_getFreeMallocPage(4)) == 0x0)
    kpanic("Error: vmmGetFreeKernelPage returned NULL\n");
    
  /* zero out the memory so we know there is no garbage */
  memset(emptyKernDesc,0x0,0x4000);

  emptyKernDesc[0].next = &emptyKernDesc[1];

  for (i = 0x1;i < ((0x4000/sizeof(struct memDescriptor)));i++) {
    if (i+1 < (0x4000/sizeof(struct memDescriptor)))
      emptyKernDesc[i].next = &emptyKernDesc[i+1];
    else
      emptyKernDesc[i].next = 0x0;
    emptyKernDesc[i].prev = &emptyKernDesc[i-1];
    }

  tmpDesc = &emptyKernDesc[0];

  emptyKernDesc       = tmpDesc->next;
  emptyKernDesc->prev = 0x0;
  tmpDesc->next       = 0x0;
  tmpDesc->prev       = 0x0;
  spinUnlock(&emptyDescSpinLock);
  return(tmpDesc);
  }

/************************************************************************

Function: void insertFreeDesc(struct memDescriptor *freeDesc)
Description: This Function Inserts A Free Descriptor On The List Which Is
             Kept In Size Order

Notes:

02/17/03 - This Was Inspired By TCA's Great Wisdom -
           "[20:20:59] <TCA> You should just insert it in order"

************************************************************************/
static int insertFreeDesc(struct memDescriptor *freeDesc) {
  struct memDescriptor *tmpDesc = 0x0;
  
  assert(freeDesc);
  
  if (freeDesc->limit <= 0x0)
    kpanic("Inserting Descriptor with no limit\n");
  
  if (freeKernDesc != 0x0) {
    /*
    */  
    freeDesc->next = freeKernDesc;
    freeDesc->prev = 0x0;
    freeKernDesc->prev = freeDesc;
    freeKernDesc = freeDesc;
    /*
    */
    /*
    for (tmpDesc = freeKernDesc;tmpDesc != 0x0;tmpDesc = tmpDesc->next) {
      if (freeDesc->limit <= tmpDesc->limit) {
        freeDesc->prev = tmpDesc->prev;
        tmpDesc->prev  = freeDesc;
        freeDesc->next = tmpDesc;
        
        if (tmpDesc == freeKernDesc)
          freeKernDesc = freeDesc;
        return(0x0);
        }
       if (tmpDesc->next == 0x0) {
         tmpDesc->next = freeDesc;
         freeDesc->prev = tmpDesc;
         freeDesc->next = 0x0;
         return(0x0);
         }
      }
    kpanic("didnt Insert\n");
    */
    return(0x0);
    }
  else {
    freeDesc->prev = 0x0;
    freeDesc->next = 0x0;
    freeKernDesc = freeDesc;
    return(0x0);
    }

  return(0x1);
  }

/************************************************************************

Function: void mergeMemBlocks()
Description: This Function Will Merge Free Blocks And Free Pages

Notes:

03/05/03 - We Have A Problem It Seems The First Block Is Limit 0x0

************************************************************************/
static void mergeMemBlocks() {
  struct memDescriptor *tmpDesc1 = 0x0;
  struct memDescriptor *tmpDesc2 = 0x0;
  uInt32               baseAddr  = 0x0;

  return;

  //Loop The Free Descriptors See If We Can Merge Them
  mergeStart:
  for (tmpDesc1=freeKernDesc;tmpDesc1 != 0x0;tmpDesc1=tmpDesc1->next) {
    /*
     Compare The Base Addr With The Other Descriptors If You Find The One
     That You Are Looking For Lets Merge Them
    */
    if (tmpDesc1->limit != 0x0) {
      baseAddr = (uInt32)tmpDesc1->baseAddr + (uInt32)tmpDesc1->limit;
      for (tmpDesc2=freeKernDesc;tmpDesc2;tmpDesc2=tmpDesc2->next) {
        if ((uInt32)tmpDesc2->baseAddr == baseAddr) {
          tmpDesc1->limit += tmpDesc2->limit;
          tmpDesc2->baseAddr = 0x0;
          tmpDesc2->limit    = 0x0;
          if (tmpDesc2->prev) {
            tmpDesc2->prev->next = tmpDesc2->next;
            }
          if (tmpDesc2->next) {
            tmpDesc2->next->prev = tmpDesc2->prev;
            }
          tmpDesc2->prev      = 0x0;
          tmpDesc2->next      = emptyKernDesc;
          emptyKernDesc->prev = tmpDesc2;
          emptyKernDesc       = tmpDesc2;
          if (tmpDesc1->prev) {
            tmpDesc1->prev->next = tmpDesc1->next;
            }
          if (tmpDesc1->next) {
            tmpDesc1->next->prev = tmpDesc1->prev;
            }
          tmpDesc1->prev = 0x0;
          tmpDesc1->next = 0x0;
	  kprintf("mergememBlocks: [%i]\n",tmpDesc1->limit);
          insertFreeDesc(tmpDesc1);
          //tmpDesc1 = freeKernDesc;
	  goto mergeStart;
          break;
          }
        }
      }
    }
  return;
  }

/************************************************************************

Function: void *kmalloc(uInt32 len)
Description: Allocate Kernel Memory

Notes:

02/17/03 - Do I Still Need To Pass In The Pid?

************************************************************************/    
void *kmalloc(uInt32 len) {
  struct memDescriptor *tmpDesc1 = 0x0;
  struct memDescriptor *tmpDesc2 = 0x0;
  char                  *buf      = 0x0;
  int                    i         = 0x0;

  spinLock(&mallocSpinLock);
  
  len = MALLOC_ALIGN(len);
  
  if (len == 0x0) {
    spinUnlock(&mallocSpinLock);
    return(0x0);
    }
  for (tmpDesc1 = freeKernDesc;tmpDesc1 != 0x0;tmpDesc1=tmpDesc1->next) {
    assert(tmpDesc1);
    if (tmpDesc1->limit >= len) {
      if (tmpDesc1->prev != 0x0)
        tmpDesc1->prev->next = tmpDesc1->next;
      if (tmpDesc1->next != 0x0)
        tmpDesc1->next->prev = tmpDesc1->prev;

      if (tmpDesc1 == freeKernDesc)
        freeKernDesc = tmpDesc1->next;

      tmpDesc1->prev = 0x0;
      tmpDesc1->next = usedKernDesc;
      if (usedKernDesc != 0x0)
        usedKernDesc->prev = tmpDesc1;
      usedKernDesc = tmpDesc1;
      if (tmpDesc1->limit > (len + 32)) {
        tmpDesc2 = getEmptyDesc();
        assert(tmpDesc2);
        tmpDesc2->limit = tmpDesc1->limit - len;
        tmpDesc1->limit = len;
        tmpDesc2->baseAddr = tmpDesc1->baseAddr + len;
        tmpDesc2->next = 0x0;
        tmpDesc2->prev = 0x0;
	if (tmpDesc2->limit <= 0x0)
	  //kprintf("kmalloc-1 tmpDesc2: [%i:%i:%i]\n",tmpDesc2->limit,tmpDesc1->limit,len);
        insertFreeDesc(tmpDesc2);
        }
      buf = (char *)tmpDesc1->baseAddr;
      for (i=0;i<tmpDesc1->limit;i++) {
        (char)buf[i] = (char)0x0;
        }
      spinUnlock(&mallocSpinLock);
      //kprintf("baseAddr1[0x%X:0x%X]",tmpDesc1,tmpDesc1->baseAddr);
      return(tmpDesc1->baseAddr);
      }
    }
  tmpDesc1 = getEmptyDesc();
  //kprintf("no empty desc\n");
  if (tmpDesc1 != 0x0) {
    tmpDesc1->baseAddr = (struct memDescriptor *)vmm_getFreeMallocPage((len + 4095)/4096);
    tmpDesc1->limit    = len;
    tmpDesc1->next     = usedKernDesc;
    tmpDesc1->prev     = 0x0;
    if (usedKernDesc != 0x0)
      usedKernDesc->prev       = tmpDesc1;
    usedKernDesc             = tmpDesc1;
 
    if ((len%0x1000) > 0x0) {
      tmpDesc2           = getEmptyDesc();
      assert(tmpDesc2);
      tmpDesc2->baseAddr = tmpDesc1->baseAddr + tmpDesc1->limit;
      tmpDesc2->limit    = ((len + 4095)/0x1000)*0x1000 - tmpDesc1->limit;
      tmpDesc2->prev     = 0x0;
      tmpDesc2->next     = 0x0;
      if (tmpDesc2->limit <= 0x0)
        kprintf("kmalloc-2 tmpDesc2: [%i]\n",tmpDesc2->limit);
      insertFreeDesc(tmpDesc2);
      }
      buf = (char *)tmpDesc1->baseAddr;
      for (i=0;i<tmpDesc1->limit;i++) {
        (char)buf[i] = (char)0x0;
        }
    spinUnlock(&mallocSpinLock);
    //kprintf("baseAddr2[0x%X:0x%X]",tmpDesc1,tmpDesc1->baseAddr);
    return(tmpDesc1->baseAddr);
    }
  //Return Null If Unable To Malloc
  spinUnlock(&mallocSpinLock);
  //kprintf("baseAddr3[0x0]");
  return(0x0);
  }
  
/************************************************************************

Function: void kfree(void *baseAddr)
Description: This Will Find The Descriptor And Free It

Notes:

02/17/03 - I need To Make It Join Descriptors

************************************************************************/
void kfree(void *baseAddr) {
  struct memDescriptor *tmpDesc1 = 0x0;

  spinLock(&mallocSpinLock);
  assert(baseAddr);

  assert(usedKernDesc);
  
  for (tmpDesc1 = usedKernDesc;tmpDesc1 != 0x0;tmpDesc1 = tmpDesc1->next) {
    
    if (tmpDesc1->baseAddr == baseAddr) {
    
      if (usedKernDesc == tmpDesc1)
        usedKernDesc = tmpDesc1->next;

      if (tmpDesc1->prev != 0x0)
        tmpDesc1->prev->next = tmpDesc1->next;

      if (tmpDesc1->next != 0x0)
        tmpDesc1->next->prev = tmpDesc1->prev;


      tmpDesc1->next = 0x0;
      tmpDesc1->prev = 0x0;
      
      if (tmpDesc1->limit <= 0x0)
        kprintf("kfree tmpDesc1: [%i]\n",tmpDesc1->limit);
      insertFreeDesc(tmpDesc1);

      //mergeMemBlocks();
      spinUnlock(&mallocSpinLock);
      return;
      }
    }
  kprintf("Kernel: Error Freeing Descriptor! [0x%X]\n",(uInt32)baseAddr);
  spinUnlock(&mallocSpinLock);
  return;
  }

/***
 $Log$
 Revision 1.20  2004/07/28 00:17:05  reddawg
 Major:
   Disconnected page 0x0 from the system... Unfortunately this broke many things
   all of which have been fixed. This was good because nothing deferences NULL
   any more.

 Things affected:
   malloc,kmalloc,getfreepage,getfreevirtualpage,pagefault,fork,exec,ld,ld.so,exec,file

 Revision 1.19  2004/07/26 19:15:49  reddawg
 test code, fixes and the like

 Revision 1.18  2004/07/26 16:52:45  reddawg
 here we go

 Revision 1.17  2004/07/24 23:04:44  reddawg
 Changes... mark let me know if you fault at pid 185 when you type stress

 Revision 1.16  2004/07/21 10:02:09  reddawg
 devfs: renamed functions
 device system: renamed functions
 fdc: fixed a few potential bugs and cleaned up some unused variables
 strol: fixed definition
 endtask: made it print out freepage debug info
 kmalloc: fixed a huge memory leak we had some unhandled descriptor insertion so some descriptors were lost
 ld: fixed a pointer conversion
 file: cleaned up a few unused variables
 sched: broke task deletion
 kprintf: fixed ogPrintf definition

 Revision 1.15  2004/07/20 23:20:50  reddawg
 kmalloc: forgot to remove an assert

 Revision 1.14  2004/07/20 23:18:11  reddawg
 Made malloc a little more robust but we have a serious memory leak somewhere

 Revision 1.13  2004/07/20 22:29:55  reddawg
 assert: remade assert

 Revision 1.12  2004/07/20 18:58:24  reddawg
 Few fixes

 Revision 1.11  2004/07/18 05:24:15  reddawg
 Fixens

 Revision 1.10  2004/07/17 18:00:47  reddawg
 kmalloc: added assert()

 Revision 1.9  2004/07/17 15:54:52  reddawg
 kmalloc: added assert()
 bioscall: fixed some potential problem by not making 16bit code
 paging: added assert()

 Revision 1.8  2004/06/17 14:50:32  reddawg
 kmalloc: converted some variables to static

 Revision 1.7  2004/06/17 02:54:54  flameshadow
 chg: fixed cast

 Revision 1.6  2004/05/26 11:56:51  reddawg
 kmalloc: fixed memrgeMemBlocks hopefully it will prevent future segfault issues
          by not having any more overlapping blocks

 Revision 1.5  2004/05/25 14:01:14  reddawg
 Implimented Better Spinlocking No More Issues With KMALLOC which actually
 was causing bizzare problems

 END
 ***/

