/*-
* Copyright (c) 2002-2018 The UbixOS Project.
* All rights reserved.
*
* This was developed by Christopher W. Olsen for the UbixOS Project.
*
* Redistribution and use in source and binary forms, with or without modification, are permitted
* provided that the following conditions are met:
*
* 1) Redistributions of source code must retain the above copyright notice, this list of
* conditions, the following disclaimer and the list of authors.
* 2) 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.
* 3) 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 AUTHOR 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.
*/
#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>
#include <sys/types.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;
u_int32_t baseAddr = 0x0;
kprintf("[%s:%i] MMB", __FILE__, __LINE__);
//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) {
//kprintf("[bA: 0x%X]", tmpDesc->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
***/
