/*****************************************************************************************
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: kmalloc.c 54 2016-01-11 01:29:55Z reddawg $
*****************************************************************************************/
#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 struct spinLock mallocSpinLock = SPIN_LOCK_INITIALIZER;
static struct spinLock 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) {
#if 0
freeDesc->next = freeKernDesc;
freeDesc->prev = 0x0;
freeKernDesc->prev = freeDesc;
freeKernDesc = freeDesc;
#endif
for (tmpDesc = freeKernDesc;tmpDesc != 0x0;tmpDesc = tmpDesc->next) {
if (freeDesc->limit <= tmpDesc->limit) {
freeDesc->prev = tmpDesc->prev;
if (tmpDesc->prev != 0x0)
tmpDesc->prev->next = freeDesc;
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;
uInt16 pages = 0x0;
spinLock(&mallocSpinLock);
len = MALLOC_ALIGN(len);
if (len == 0x0) {
spinUnlock(&mallocSpinLock);
kprintf("kmalloc: len = 0!\n");
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) {
tmpDesc2 = getEmptyDesc();
assert(tmpDesc2);
tmpDesc2->limit = tmpDesc1->limit - len;
tmpDesc1->limit = len;
tmpDesc2->baseAddr = tmpDesc1->baseAddr + len;
tmpDesc2->next = 0x0;
tmpDesc2->prev = 0x0;
insertFreeDesc(tmpDesc2);
}
buf = (char *)tmpDesc1->baseAddr;
for (i=0;i<tmpDesc1->limit;i++) {
buf[i] = (char)0x0;
}
spinUnlock(&mallocSpinLock);
//kprintf("m1[%i:%i:0x%X]",tmpDesc1->limit,len,tmpDesc1->baseAddr);
assert(tmpDesc1->baseAddr);
return(tmpDesc1->baseAddr);
}
}
tmpDesc1 = getEmptyDesc();
//kprintf("no empty desc\n");
if (tmpDesc1 != 0x0) {
pages = ((len + 4095)/4096);
tmpDesc1->baseAddr = (struct memDescriptor *)vmm_getFreeMallocPage(pages);
tmpDesc1->limit = len;
tmpDesc1->next = usedKernDesc;
tmpDesc1->prev = 0x0;
if (usedKernDesc != 0x0)
usedKernDesc->prev = tmpDesc1;
usedKernDesc = tmpDesc1;
if (((pages * 4096)-len) > 0x0) {
tmpDesc2 = getEmptyDesc();
assert(tmpDesc2);
tmpDesc2->baseAddr = tmpDesc1->baseAddr + tmpDesc1->limit;
tmpDesc2->limit = ((pages * 4096)-len);
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++) {
buf[i] = (char)0x0;
}
spinUnlock(&mallocSpinLock);
//kprintf("baseAddr2[0x%X:0x%X]",tmpDesc1,tmpDesc1->baseAddr);
//kprintf("m2[%i:%i:0x%X]",tmpDesc1->limit,len,tmpDesc1->baseAddr);
assert(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 *tmpDesc = 0x0;
if (baseAddr == 0x0) return;
assert(baseAddr);
assert(usedKernDesc);
spinLock(&mallocSpinLock);
for (tmpDesc = usedKernDesc;tmpDesc != 0x0;tmpDesc = tmpDesc->next) {
if (tmpDesc->baseAddr == baseAddr) {
memset(tmpDesc->baseAddr,0xBE,tmpDesc->limit);
if (usedKernDesc == tmpDesc)
usedKernDesc = tmpDesc->next;
if (tmpDesc->prev != 0x0)
tmpDesc->prev->next = tmpDesc->next;
if (tmpDesc->next != 0x0)
tmpDesc->next->prev = tmpDesc->prev;
tmpDesc->next = 0x0;
tmpDesc->prev = 0x0;
if (tmpDesc->limit <= 0x0)
kprintf("kfree tmpDesc1: [%i]\n",tmpDesc->limit);
//kprintf("{0x%X}",tmpDesc->baseAddr);
insertFreeDesc(tmpDesc);
// mergeMemBlocks();
spinUnlock(&mallocSpinLock);
return;
}
}
spinUnlock(&mallocSpinLock);
kprintf("Kernel: Error Freeing Descriptor! [0x%X]\n",(uInt32)baseAddr);
return;
}
/***
$Log: kmalloc.c,v $
Revision 1.3 2006/12/05 14:10:21 reddawg
Workign Distro
Revision 1.2 2006/10/06 15:48:01 reddawg
Starting to make ubixos work with UFS2
Revision 1.1.1.1 2006/06/01 12:46:16 reddawg
ubix2
Revision 1.4 2006/06/01 12:42:09 reddawg
Getting back to the basics
Revision 1.3 2006/06/01 03:58:33 reddawg
wondering about this stuff here
Revision 1.2 2005/10/12 00:13:37 reddawg
Removed
Revision 1.1.1.1 2005/09/26 17:24:11 reddawg
no message
Revision 1.35 2005/08/04 18:32:59 fsdfs
added error reporting
Revision 1.34 2005/08/04 18:23:41 reddawg
BUG: Assert has issues that must be looked into
Revision 1.33 2005/08/04 17:11:11 fsdfs
----------------------------------------
-------------------
Revision 1.32 2004/09/28 21:50:04 reddawg
kmalloc: now when we kfree memory is filled with 0xBE so it is easy to debug if we continue to use free'd memory
Revision 1.31 2004/09/19 16:17:25 reddawg
fixed memory leak we now lose no memory....
Revision 1.30 2004/09/14 21:51:24 reddawg
Debug info
Revision 1.29 2004/09/11 23:39:31 reddawg
ok time for bed
Revision 1.28 2004/09/11 23:21:26 reddawg
run now do you get fegfaults with BB?
Revision 1.27 2004/09/11 22:49:28 reddawg
pat look at lines 276-285 does the math seem right?
Revision 1.26 2004/09/11 22:33:13 reddawg
minor changes
Revision 1.25 2004/09/11 12:11:11 reddawg
Cleaning up the VFS more changes to follow...
Revision 1.24 2004/09/08 23:19:58 reddawg
hmm
Revision 1.23 2004/09/06 15:13:25 reddawg
Last commit before FreeBSD 6.0
Revision 1.22 2004/08/26 22:51:18 reddawg
TCA touched me :( i think he likes men....
sched.h: kTask_t added parentPid
endtask.c: fixed term back to parentPid
exec.c: cleaned warnings
fork.c: fixed term to childPid
sched.c: clean up for dead tasks
systemtask.c: clean up dead tasks
kmalloc.c: cleaned up warnings
udp.c: cleaned up warnings
bot.c: cleaned up warnings
shell.c: cleaned up warnings
tcpdump.c: took a dump
hd.c: cleaned up warnings
ubixfs.c: stopped prning debug info
Revision 1.21 2004/07/28 15:05:43 reddawg
Major:
Pages now have strict security enforcement.
Many null dereferences have been resolved.
When apps loaded permissions set for pages rw and ro
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
***/
Charlie Root